An SPN-Based Integrated Model for Web Prefetching and Caching

The World Wide Web has become the primary means for information dissemination. Due to the limited resources of the network bandwidth, users always suffer from long time waiting. Web prefetching and web caching are the primary approaches to reducing the user perceived access latency and improving the quality of services. In this paper, a Stochastic Petri Nets （SPN） based integrated web prefetching and caching model （IWPCM） is presented and the performance evaluation of IWPCM is made. The performance metrics, access latency, throughput, HR （hit ratio） and BHR （byte hit ratio） are analyzed and discussed. Simulations show that compared with caching only model （CM）, IWPCM can further improve the throughput, HR and BHR efficiently and reduce the access latency. The performance evaluation based on the SPN model can provide a basis for implementation of web prefetching and caching and the combination of web prefetching and caching holds the promise of improving the QoS of web systems.     

并行文件系统中适度贪婪的Cache预取一体化算法

传统文件系统中的Ｃａｃｈｅ和预取技术是两种降低访问延迟的有效方法。在并行科学计算应用的Ｉ／Ｏ访问模式下,简单的Ｃａｃｈｅ和预取技术已无法提供较高的Ｃａｃｈｅ命中率,该文在分析该Ｉ／Ｏ模式的基础上提出了适度贪婪的Ｃａｃｈｅ和预取一体化算法（ＰＧＩ）,该算法充分利用了并行文件系统环境的特点,采用了适度贪婪的动态滑模技术,可以有铲地消除预取时的抖动,降低系统处理开锁,并同时采用了Ｃａｃｈｅ和预取一体化的     

多线程环境下基于多预取点的文件预取

为解决当前Linux内核的预取算法在多线程情况下出现预取误判的问题,依据多线程环境下进程对磁盘文件的访问特点,提出一种基于多预取点的预取算法。在Linux内核原有的预取算法的基础上,结合多线程环境下应用程序对数据的访问模式,在Linux内核的页面缓存层进行了实现。实验和分析表明,在IOzone单线程测试中,该算法和Linux内核原预取算法性能相当;在多线程测试中,读取相同大小的文件,耗时比Linux内核原预取算法至少少1/3。新算法对于提高I/O并行度,从而提高整个计算机系统并行化很有帮助。     

Reference implementation of scalable I/O low-level API on Intel Paragon

The Scalable I/O(SIO)Initiative‘s Low-Level Application Programming Interface(SIO LLAP)provides file system implementers with a simple low-Level interface to support high-level parallel /O interfaces efficiently and effectively.This paper describes a reference implementation and the evaluation of the SIO LLAPI on the Intel Paragon multicomputer.The implementation provides the file system structure and striping algorithm compatible with the Parallel File System(PFS)of Intel Paragon ,and runs either inside the kernel or as a user level library.The scatter-gather addressing read/write,asynchronous I/O,client caching and prefetching mechanism,file access hint mechanism,collective I/O and highly efficient file copy have been implemented.The preliminary experience shows that the SIO LLAPI provides opportunities of significant performance improvement and is easy to implement.Some high level file system interfaces and applications such as PFS,ADIO and Hartree-Fock application,are also implemented on top of SIO.The performance of PFS is at least the same as that of Intel‘s native pfs,and in many cases,such as small sequential file access,huge I/O requests and collective I/O,it is stable and much better,The SIO features help to support high level interfaces easily,quickly and more efficiently,and the cache,prefetching,hints are useful to get better performance based on different access models.The scalability and performance of SIO are limited by the network latency,network scalable bandwidth,memory copy bandwidth,memory size and pattern of I/O requests.The tadeoff between generality and efficienc should be considered in implementation.     

An adaptive cache coherence protocol specification for parallel input/output systems

Caching has been intensively used in memory and traditional file systems to improve system performance. However, the use of caching in parallel file systems and I/O libraries has been limited to I/O nodes to avoid cache coherence problems. We specify an adaptive cache coherence protocol that is very suitable for parallel file systems and parallel I/O libraries. This model exploits the use of caching, both at processing and I/O nodes, providing performance improvement mechanisms such as aggressive prefetching and delayed-write techniques. The cache coherence problem is solved by using a dynamic scheme of cache coherence protocols with different sizes and shapes of granularity. The proposed model is very appropriate for parallel I/O interfaces, such as MPI-IO. Performance results, obtained on an IBM SP2, are presented to demonstrate the advantages offered by the cache management methods proposed.     

Practical prefetching techniques for multiprocessor file systems

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have thepotential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments withpractical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of those policies across a range of architectural parameters.     

Automatic ARIMA time series modeling for adaptive I/O prefetching

Inadequate I/O performance remains a major challenge in using high-end computing systems effectively. To address this problem, we present TsModeler, an automatic time series modeling and prediction framework for adaptive I/O prefetching that uses ARIMA time series models to predict the temporal patterns of I/O requests. These online pattern analysis techniques and cutoff indicators for autocorrelation patterns enable multistep online predictions suitable for multiblock prefetching. This work also combines time series predictions with spatial Markov model predictions to determine when, what, and how many blocks to prefetch. Experimental results show reductions in execution time compared to the standard Linux file system across various hardware configurations.     

Threaded Prefetching: A New Instruction Memory Hierarchy for Real-Time Systems

Cache memories have been extensively used to bridge the speed gap between high speed processors and relatively slow main memory. However, they are not widely used in real-time systems due to their unpredictable performance. This paper proposes an instruction prefetching scheme called threaded prefetching as an alternative to instruction caching in real-time systems. In the proposed threaded prefetching, an instruction block pointer called a thread is assigned to each instruction memory block and is made to point to the next block on the worst case execution path that is determined by a compile-time analysis. Also, the thread is not updated throughout the entire program execution to guarantee predictability. This paper also compares the worst case performances of various previous instruction prefetching schemes with that of the proposed threaded prefetching. By analyzing several benchmark programs, we show that the worst case performance of the proposed scheme is significantly better than those of previous instruction prefetching schemes. The results also show that when the block size is large enough the worst case performance of the proposed threaded prefetching scheme is almost as good as that of an instruction cache with 100 % hit ratio.     

基于查询热度的密钥索引缓存

在当前的分布式文件系统（HDFS,Hadoop distributed file system）密钥管理系统中,加密区密钥在启动时全部加载至内存,提供密钥服务。随着密钥资源的增加,占据的内存空间也随之增长,带来内存空间不足和密钥索引瓶颈,如何组织缓存数据、高效处理未命中密钥的查询,如何调整缓存中的密钥资源,如何精准预测密钥的使用这三大要点是解决该瓶颈的关键所在。为了实现细粒度高效缓存,提高密钥使用效率,从密钥索引数据结构、密钥置换算法、密钥预取策略分析3个方面出发,设计了密钥缓存置换的模块架构,计算密钥热度,设置密钥置换算法。具体地,在密钥热度计算与缓存置换方面,从密钥所绑定的文件系统和用户出发,分析影响密钥缓存热度的潜在影响要素,构建密钥使用热度的基本模型,采用哈希表与小顶堆链表组合的方式,维护在用密钥的热度,基于热度识别设置淘汰算法,由时间控制器调整密钥使用,动态更新缓存中的密钥,从而实现基于热度计算的密钥差异化置换。在密钥预取策略分析方面,综合考虑业务流程和用户访问存在时间周期维度的规律,通过日志挖掘获取密钥使用规律,分析密钥预置策略。实验表明,所提密钥置换算法可在降低内存占用的...     

无线Web访问的缓存和预取机制

缓存和预取在提高无线环境下的Web访问性能方面发挥着重要作用。文章研究针对无线局域网的Web缓存和预取机制,分别基于数据挖掘和信息论提出了采用序列挖掘和延迟更新的预测算法,设计了上下文感知的预取算法和获益驱动的缓存替换机制,上述算法已在Web缓存系统OnceEasyCache中实现。性能评估实验结果表明,上述算法的集成能有效地提高缓存命中率和延迟节省率。     

读请求的空间与时间特征建模

为了改善并行应用程序和并行文件系统的I/O性能，对读请求的空间与时间特征进行建模。使用自相关函数分析和Haar小波变换来自动识别自回归、集成的移动平均的模型结构，通过该模型来预测读请求的时间特征；使用马尔可夫模型对读请求的空间特征进行建模、预测。该模型可以将自回归、集成的移动平均时间预测模型与马尔可夫空间预测模型结合，并自适应地预测什么时间、取哪些数据块、取多少数据块。     

Web缓存命中率与字节命中率关系

在研究Web缓存性能时,一般考虑2个评价指标：命中率HR和字节命中率BHR。目前大多侧重于2个指标之一,或仅通过测试2个指标的数值来评价缓存替换算法优劣,没有从2个指标关系的角度来评价缓存替换算法的性能。该文讨论了Web缓存系统中命中率与字节命中率之间的关系,提出了一种Web缓存性能评价指标——命中比（FBR）,讨论了该指标在Web缓存替换算法及Web预取性能评价中的应用,为度量缓存系统的性能提供了参考依据。     

集群下Cholesky分解的核外预取算法

核外计算中,由于I/O操作速度比较慢,所以对文件的访阿时间占的比例较大.如果使文件操作和计算重叠则可以大幅度地提高运行效率.软件数据预取是一种有效的隐藏存储延迟的技术,通过预取使数据在实际使用之前从硬盘读到缓存中,提高了缓存(cache)的命中率,降低了读取数据的时间.通过设置两个缓冲区来轮流存放本次和下一次读入的数据块,实现访存完全命中cache的效果,使Cholesky分解并行程序执行核外计算的效率得到了大幅度的提高.同时,I/O操作的时间与CPU的执行时间的比例也是影响效率的主要因素.     

Fine-grained management of I/O optimizations based on workload characteristics

With the advent of new computing paradigms, parallel file systems serve not only traditional scientific computing applications but also non-scientific computing applications, such as financial computing, business, and public administration. Parallel file systems provide storage services for multiple applications. As a result, various requirements need to be met. However, parallel file systems usually provide a unified storage solution, which cannot meet specific application needs. In this paper, an extended file handle scheme is proposed to deal with this problem. The original file handle is extended to record I/O optimization information, which allows file systems to specify optimizations for a file or directory based on workload characteristics. Therefore, fine-grained management of I/O optimizations can be achieved. On the basis of the extended file handle scheme, data prefetching and small file optimization mechanisms are proposed for parallel file systems. The experimental results show that the proposed approach improves the aggregate throughput of the overall system by up to 189.75%.     

SAC: Exploiting Stable Set Model to Enhance CacheFiles

Client cache is an important technology for the optimization of distributed and centralized storage systems. As a representative client cache system, the performance of CacheFiles is limited by transition faults. Furthermore, CacheFiles just supports a simple LRU policy with a tightly-coupled design. To overcome these limitations, we propose to employ Stable Set Model （SSM） to improve CacheFiles and design an enhanced CacheFiles, SAC. SSM assumes that data access can be decomposed to access on some stable sets, in which elements are always repeatedly accessed or not accessed together. Using SSM methods can improve the cache management and reduce the effect of transition faults. We also adopt loosely- coupled methods to design prefetch and replacement policies. We implement our scheme on Linux 2.6.32 and measure the execution time of the scheme with various file I/O benchmarks. Experiments show that SAC can significantly improve I/O performance and reduce execution time up to 84%0, compared with the existing CacheFiles.     

浅析缓存预取技术

针对计算机系统中CPU与I/O性能差距持续扩大的的问题,引出缓存及预取的概念,并分析预取技术需要处理的几个关键问题。根据预取的发展,介绍并比较几类典型的预取算法。针对目前的各种软硬件新技术,探讨预取技术所面临的困难及其发展趋势。     

面向流媒体业务的存储设备性能改进策略

本文分析了RAID、I/O调度和预读等技术在提高流媒体存储系统性能方面的局限性。为突破这些传统策略的限制,本文针对存储设备的特点,挖掘磁盘设备的寻道延迟和旋转延迟的提升空间,提出了流的独立存储、潜伏缓存和排练等方法,从多个角度为进一步提升存储系统服务性能提出了新思路。理论分析和实测评估验证了新方法对系统性能的提升效果。     

倒排文件索引缓存机制的优化

为了有效提高搜索引擎检索服务系统的整体性能,提出了一种基于倒排文件索引的缓存机制优化方法。具体研究过程是：首先分析倒排文件缓存的体系结构和数据加载,接着讨论负载数据对倒排文件缓存和缓存替换算法的影响,最后通过设计仿真实验研究倒排文件的缓存优化。研究结果表明,采用倒排文件索引的缓存机制优化方法可以明显减少磁盘系统I/O访问次数,提高磁盘系统带宽的利用率。     

基于时空局部性的层次化查询结果缓存机制

查询结果缓存可以对查询结果的文档标识符集合或者实际的返回页面进行缓存,以提高用户查询的响应速度,相应的缓存形式可以分别称之为标识符缓存或页面缓存。对于固定大小的内存,标识符缓存可以获得更高的命中率,而页面缓存可以达到更高的响应速度。该文根据用户查询访问的时间局部性和空间局部性,提出了一种新颖的基于时空局部性的层次化结果缓存机制。首先,该机制将固定大小的结果缓存划分为两层:页面缓存和标识符缓存。对于用户提交的查询,该机制会首先使用第一层的页面缓存进行应答,如果未能命中,则继续尝试使用第二层的标识符缓存。实验显示这种层次化的缓存机制较传统的仅依赖于单一缓存形式的机制,在平均查询响应时间上,取得了可观的性能提升:例如,相对单纯的页面缓存,平均达到9%,最好情况下达到11%。其次,该机制在标识符缓存的基础上,设计了一种启发式的预取策略,对用户查询检索的空间局部性进行挖掘。实验显示,这种预取策略的融合,能进一步促进检索系统性能的有效提升,从而最终建立起一套时空完备的、有效的结果缓存机制。     

Segment-based streaming media proxy: modeling and optimization

Researchers often use segment-based proxy caching strategies to deliver streaming media by partially caching media objects. The existing strategies mainly consider increasing the byte hit ratio and/or reducing the client perceived startup latency (denoted by the metric delayed startup ratio). However, these efforts do not guarantee continuous media delivery because the to-be-viewed object segments may not be cached in the proxy when they are demanded. The potential consequence is playback jitter at the client side due to proxy delay in fetching the uncached segments, which we call proxy jitter. Thus, for the best interests of clients, a correct model for streaming proxy system design should aim to minimize proxy jitter subject to reducing the delayed startup ratio and increasing the byte hit ratio. However, we have observed two major pairs of conflicting interests inherent in this model: (1) one between improving the byte hit ratio and reducing proxy jitter, and (2) the other between improving the byte hit ratio and reducing the delayed startup ratio. In this study, we first propose and analyze prefetching methods for in-time prefetching of uncached segments, which provides insights into the first pair of conflicting interests. Second, to address the second pair of the conflicting interests, we build a general model to analyze the performance tradeoff between the second pair of conflicting performance objectives. Finally, considering our main objective of minimizing proxy jitter and optimizing the two tradeoffs, we propose a new streaming proxy system called Hyper Proxy. Synthetic and real workloads are used to evaluate our system. The performance results show that Hyper Proxy generates minimum proxy jitter with a low delayed startup ratio and a small decrease of byte hit ratio compared with existing schemes.