位置相关信息服务中的一种数据预取方法

位置相关信息服务中访问数据涉及到复杂的空间计算,导致访问数据的延迟时间较长,而数据预取能够显著提高数据的访问速度,缩短访问数据的时间。基于LDD的预取策略如DDP考虑了数据距离,但是没有考虑数据的访问概率和更新频率及数据大小。针对以上问题提出基于价值的数据预取（CDP）策略,一些重要的数据预取因素如访问概率、更新频率、数据项大小、数据距离和有效范围等都包含在价值函数里,根据价值函数值的大小来选择被预取的数据。通过实验对比,CDP比DDP策略能更有效的提高缓存命中率。     

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

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

一种基于模板的数据预取和缓存算法

针对专题型应用中普遍存在的大数据查询的频繁性和模式固定性特点,提出一种基于模板的数据预取和缓存算法,用于加快数据查询响应速度并减轻服务器端负载压力。通过构建数据查询模板,在触发器被激发时调用模板以构建预取数据,提出基于模板的数据预取方法和基于触发器的预取算法;考虑缓存空间中一些大数据的存在对查询响应速度的优化性,建立缓存对象模型并提出改进的Hybrid算法。以东方红湿地环境监测平台为例进行算法实验与分析,实验结果表明,在不同的缓存百分比下,较之典型的缓存算法,改进的Hybrid算法在访问延迟率上均有改进,且在大数据量查询时表现出了优越的应用效果。     

一种智能终端数据共享中的预取缓存技术

针对智能终端数据共享中的网络延迟问题,本文提出一种两阶段,主动预取与被动预取相结合的数据预取缓存方法,减少网络延迟,提高用户体验。该方法利用网络空闲时间预取数据,减少用户等待时间;通过两阶段预取策略减少网络带宽消耗;通过主被动配合的预取算法来预取数据,提高预取准确率和预取效率;通过一种权重更新函数来更新客户端的缓存,减少对智能终端存储空间的消耗。实验表明使用此方法能减少用户等待时间58.2%,预取命中率为92%,带来的带宽损耗小于5%。     

混合架构下多请求模式的缓存替换模型研究

针对多类型多访问模式应用的需求,在GDSF算法的基础上,引入平均访问间隔和最近访问间隔两个特性以增强算法的适应性;建立缓存结构模型,通过双关键字索引机制,快速索引缓存对象,降低系统开销;对超过一定大小的文件采取后缀预取策略以增加缓存中数据对象的个数.在课题应用背景下,与传统算法的对比实验表明,该方法能够减少缓存的平均请求等待时间,提高对象命中率和字节命中率,增强了缓存替换算法对多类型多请求模式应用的适应性.     

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

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

基于频繁序列挖掘的文件系统缓存算法设计

传统缓存算法存在命中率低、交换率高等问题,且现有缓存算法在分布式大数据存储系统中并不适用,为此提出了一种基于频繁序列挖掘的自适应缓存策略。该方法使用数据挖掘算法挖掘历史访问窗口内的频繁序列,将频繁序列模糊合并后构建匹配模式集合以供查询。当新的访问来临时,将固定访问长度内的子序列与匹配模式集合进行匹配,然后根据匹配结果预取数据,同时结合修改后的S4LRU(4-segmented least recently used)数据结构进行缓存数据换出。在公开的大数据处理trace集上进行了仿真实验,实验结果表明,在不同的缓存大小下,提出算法与现有典型缓存算法相比,平均命中率提高了0.327倍,平均交换率降低了0.33倍,同时具有低开销和高时效的特点。此结果表明,该方法较传统替换算法而言是一个更为有效的缓存策略。     

多维数据的Z-Ordering存储映射算法及其缓存调度优化

多维数据以线性形式在存储系统中进行访问操作,二维及以上维度空间中的相邻节点被不同的映射算法映射到一维空间的不相邻位置。高维空间中进行相邻节点访问时,其一维存储映射位置有着不同的访问距离和访问延迟。提出了基于空间填充曲线Z-Ordering的存储映射方法及其访问距离的度量指标,并和常规优先算法进行了对比,发现能更好地将高维相邻的数据节点簇集到一维存储位置,加强了局部性。调整缓存空间中用于预取的空间大小,可以利用增强的局部性,提高了缓存命中率。实验结果表明,改善了多维数据的访问速度,优化了系统性能。     

基于磁光虚拟存储系统的文件调度算法

基于光盘库的Hadoop分布式文件系统（HDFS光盘库）在单位存储成本、数据安全性、使用寿命等方面非常符合当前大数据存储要求，但是HDFS不适合存储大量小文件和实时数据读取。为了使HDFS光盘库能更好地运用到更多大数据存储场景，本文提出一种更加适合大数据存储的磁光虚拟存储系统（MOVS, Magneto-optical Virtual Storage System）。系统在HDFS光盘库与用户之间加入磁盘缓存，并在磁盘缓存内通过文件标签分类、虚拟存储、小文件合并等技术将磁盘缓存内小文件合并为适合HDFS光盘库存储的大文件，提高系统的数据传输速度。系统还使用了文件预取、缓存替换等文件调度算法对磁盘缓存内文件进行动态更新，减少用户访问HDFS光盘库次数。实验结果表明，MOVS相对HDFS光盘库在响应时间和数据传输速度方面得到很大改善。     

层次编码视频传输中代理缓存技术的研究

分析了在Internet上进行实时视频流传输的不足,提出了将层次编码技术与代理缓存技术相结合的方法,对基于层次编码的缓存预取方法和替换方法进行了研究。根据视频流数据的特点,对缓存的命中率和访问频度进行了改进。     

Scalable cache invalidation algorithms for mobile data access

In this paper, we address the problem of cache invalidation in mobile and wireless client/server environments. We present cache invalidation techniques that can scale not only to a large number of mobile clients, but also to a large number of data items that can be cached in the mobile clients. We propose two scalable algorithms: the Multidimensional Bit-Sequence (MD-BS) algorithm and the Multilevel Bit-Sequence (ML-BS) algorithm. Both algorithms are based on our prior work on the Basic Bit-Sequences (BS) algorithm. Our study shows that the proposed algorithms are effective for a large number of cached data items with low update rates. The study also illustrates that the algorithms ran be used with other complementary techniques to address the problem of cache invalidation for data items with varied update and access rates.     

同步数据触发体系结构中指令预取技术研究

同步数据触发体系结构SDTA将传统指令级并行细化到微操作级并行,具有较高的数据处理能力,但其特殊的指令格式及指令特性,给指令Cache访问带来了挑战。指令预取技术能够有效地降低指令Cache的访问失效率,增强处理器取指能力,提高性能。本文分析了SDTA指令集特性,提出了一种适合SDTA指令集特性的软硬件相结合的混合指令预取机制,采用硬件预取引擎和软件提示相结合进行预取。该方法能够有效地提高指令Cache命中率,且具有实现简单、无效预取率低、不会增加代码体积等特点。     

Combining data prefetching with non-blocking loads to alleviate cache pollution effects

Data prefetching is a useful approach for reduction of memory access stalls in many scientific applications. However, it suffers from cache pollution severly in some applications. In this paper, we study the effectiveness of combining data prefetching with non-blocking loads on cache pollution and explain why it shows good result in our simulation.     

基于存取模式的Cache预取自适应策略研究

不同的Cache预取策略适用于不同的存取模式。本文介绍了存储系统Cache预取技术的研究现状，从分析存取模式出发，构造了存取模式三元组模型，并在磁盘阵列上测试了适 用于复杂环境下的Cache预取自适应策略，结果证明，自适应策略能够在不同环境上获得磁盘阵列的最优性能。     

Cache invalidation strategies for Internet-based vehicular ad hoc networks

Internet-based vehicular ad hoc network (Ivanet) is an emerging technique that combines a wired Internet and a vehicular ad hoc network (Vanet) for developing an ubiquitous communication infrastructure and improving universal information and service accessibility. A key design optimization technique in Ivanets is to cache the frequently accessed data items in a local storage of vehicles. Since vehicles are not critically limited by the storage/memory space and power consumption, selecting proper data items for caching is not very critical. Rather, an important design issue is how to keep the cached copies valid when the original data items are updated. This is essential to provide fast access to valid data for fast moving vehicles. In this paper, we propose a cooperative cache invalidation (CCI) scheme and its enhancement (ECCI) that take advantage of the underlying location management scheme to reduce the number of broadcast operations and the corresponding query delay. We develop an analytical model for CCI and ECCI techniques for fasthand estimate of performance trends and critical design parameters. Then, we modify two prior cache invalidation techniques to work in Ivanets: a poll-each-read (PER) scheme, and an extended asynchronous (EAS) scheme. We compare the performance of four cache invalidation schemes as a function of query interval, cache update interval, and data size through extensive simulation. Our simulation results indicate that the proposed schemes can reduce the query delay up to 69% and increase the cache hit rate up to 57%, and have the lowest communication overhead compared to the prior PER and EAS schemes.     

结合访存失效队列状态的预取策略

随着存储系统的访问速度与处理器的运算速度的差距越来越显著,访存性能已成为提高计算机系统性能的瓶颈.通过对指令Cache和数据Cache失效行为的分析,提出一种预取策略--结合访存失效队列状态的预取策略.该预取策略保持了指令和数据访问的次序,有利于预取流的提取.并将指令流和数据流的预取相分离,避免相互替换.在预取发起时机的选择上,不但考虑当前总线是否空闲,而且结合访存失效队列的状态,减小对处理器正常访存请求的影响.通过流过滤机制提高预取准确性,降低预取对访存带宽的需求.结果表明,采用结合访存失效队列状态的预取策略,处理器的平均访存延时减少30%,SPEC CPU2000程序的IPC值平均提高8.3%.     

代理服务器中基于对象的限定预取策略研究

预取作为一种主动缓存技术可用于提高缓存命中率,但其效果好坏很大程度上取决于所采用的预取策略。本文提出了一种代理服务器下基于对象的限定预取策略,通过调整代理服务器中预取空间的大小,防止无效页面占用过多的缓存空间,提高了缓存的利用率,从而获得较高的命中率。实验表明,基于对象的限定预取策略命中率远远高于LRU策略,并且相对于基于对象的LRU策略也有明显的改善。     

Lease-based consistency schemes in the web environment

There are many methods to maintain consistency in the distributed computing environment. Ideally, efficient schemes for maintaining consistency should take into account the following factors: lease duration of replicated data, data access pattern and system parameters. One method used to supply strong consistency in the web environment is the lease method. During the proxy’s lease time from a web server, the web server can notify the modification to the proxy by invalidation or update. In this paper, we analyze lease protocol performance by the varying update/invalidation scheme, lease duration and read rates. By using these analyses, we can choose the adaptive lease time and proper protocol (invalidation or update scheme of the modification for each proxy in the web environment). As the number of proxies for web caching increases exponentially, a more efficient method for maintaining consistency needs to be designed. We also present three-tier hierarchies on which each group and node independently and adaptively choose the proper lease time and protocol for each proxy cache. These classifications of the scheme make proxy caching adaptive to client access pattern and system parameters.     

Neighbor cache prefetching for multimedia image and video processing

Cache performance is strongly influenced by the type of locality embodied in programs. In particular, multimedia programs handling images and videos are characterized by a bidimensional spatial locality, which is not adequately exploited by standard caches. In this paper we propose novel cache prefetching techniques for image data, called neighbor prefetching, able to improve exploitation of bidimensional spatial locality. A performance comparison is provided against other assessed prefetching techniques on a multimedia workload (with MPEG-2 and MPEG-4 decoding, image processing, and visual object segmentation), including a detailed evaluation of both the miss rate and the memory access time. Results prove that neighbor prefetching achieves a significant reduction in the time due to delayed memory cycles (more than 97% on MPEG-4 with respect to 75% of the second performing technique). This reduction leads to a substantial speedup on the overall memory access time (up to 140% for MPEG-4). Performance has been measured with the PRIMA trace-driven simulator, specifically devised to support cache prefetching.