位置相关查询中基于最小访问代价的缓存替换方法

在位置相关查询（LDQ）中由于用户的移动性和数据的位置相关性,给缓存替换策略带来了新的挑战。在详细分析位置相关数据(LDD)的空间位置特性和几种典型的位置相关缓存替换策略的基础上,提出一种基于最小访问代价的缓存替换策略（PLAC）,一些重要的缓存替换因素如访问概率、更新频率、数据距离和有效范围等都包含在代价函数里,PLAC根据代价函数值的大小来决定被替换的数据,由此来保证有限缓存的最大使用率。通过实验对比,PLAC比其他位置相关缓存替换策略更为有效地提高了缓存命中率,缩短了查询平均响应时间。     

移动数据库中改进的CMIP数据预取策略研究

数据预取是移动数据库缓存技术中的关键,CMIP预取策略通过客户端历史访问记录关联规则的挖掘得到预取数据,使系统性能得到了提高。但由于没考虑到数据的更新率及数据大小,将会经常发生缓存失效。在此算法的基础上增加对数据更新率及大小的判断并对所选数据排序,然后进行预取数据的选择。通过改进降低了缓存的失效率、减少了数据访问的时间及电能的消耗。     

网格虚拟组织副本协作预取机制

副本复制是数据网格中提高数据访问效率的有效方法,如何提高副本复制的效率是一个关键性问题.现有的复制策略大多基于文件访问历史选择高价值副本进行复制,但其针对的都是节点已经访问过的文件.通过对虚拟组织文件访问特性进行深入分析,引入隐性高价值文件概念,提出虚拟组织副本协作预取机制(cooperative replica prefetching mechanism,简称CoRPM),使得本地节点通过与虚拟组织中其他节点进行协作来获取隐性高价值文件副本.该机制首先给出了副本协作预取架构,各个虚拟组织节点上的文件预取模块以协作的方式为虚拟组织内节点提供文件预取服务;然后,在副本协作预取架构的基础上设计了副本协作预取流程,其核心算法包括以作业类型为中心的本地文件预取算法和预取文件选择算法.模拟实验结果表明,CoRPM与已有的基于文件访问历史的副本复制策略相结合,可以更加有效地降低数据访问延迟.     

移动P2P网络中协同缓存的研究

在移动园区网环境中部署了P2P系统并提出了一种协同缓存策略。接入控制策略利用"阈值"和节点的位置关系选择缓存的数据。缓存替换策略利用价值函数"Cost"选择要替换掉的数据,该函数考虑了数据的被访问频率、大小及区域之间的距离这三个因素。数据一致性策略结合了Plain-Push和Pull-Every-time方案的优点并做了改进。通过两组模拟实验验证了这种协同缓存策略在降低时延、减少网络通信开销、提高缓存命中率方面具有较好的性能。     

移动环境下支持实时事务处理的数据预取

随着移动通信技术的迅速发展,人们提出了新的应用要求:在移动环境下处理实时事务.而移动通信带宽有限性引起较大的数据访问延迟,有时甚至由于网络传输的断接使得事务得不到所需要的数据,数据预取能够很好地解决这个问题.已有的移动环境下数据预取没有考虑到数据的流行性和事务的时间特性.该文分析影响实时事务数据预取的因素,首先考虑数据易变性、活跃性等因素,获得高价值预取数据集合;然后考虑访问预取数据的事务优先级、数据流行性等因素,构造预取数据的选择函数,通过该函数在前面选取的集合中筛选出对满足实时事务截止期更有价值的数据对象进行预取.实验表明,该数据预取策略能降低移动实时事务满足截止期的比率,更好地支持移动实时事务处理.     

基于hybrid拓扑的数据网格副本创建策略*

数据复制技术被广泛应用于数据网格中,以缩短数据访问时间和传输时间、降低网络带宽消耗.针对包含树型拓扑和环型拓扑的混合式网格拓扑结构,提出了一种考虑网络带宽、网络传输延迟、用户请求频率和站点可用存储空间大小等因素的副本创建策略,并引入评估函数衡量各因素的影响大小,具有良好的可靠性、可扩展性和自适应性.模拟实验的结果显示此副本创建策略可以有效降低数据平均访问时间.     

视频访问负载的分级存储及迁移算法研究

为了使分布式分级混合存储系统高效、快速响应的工作,达到优化系统性能和减少系统资源消耗的目标,通过研究负载的模式,同时考虑数据访问局部性和系统响应时间,提出了相应于负载识别、以及基于频率策略和带宽策略的分级存储迁移算法,提出了一种目标函数为(带宽节省率/命中率)的新评价标准。频率策略是根据访问的周期频率特性来进行数据分级存储迁移,带宽策略是根据在访问中考虑迁移带宽消耗特性来进行数据分级存储迁移。结合实例,模拟仿真实验结果表明,两种策略都能有效地到达目标。频率策略带来的访问次数及命中率较高,而带宽策略可以减少分级存储并发瓶颈数量。     

基于变周期数据广播的缓存一致性维护

为了提高移动计算环境中缓存数据效率,在分析现有成果的基础上,提出了基于变周期数据广播的缓存一致性维护的策略。该策略根据数据的访问用户数目以及数据更新的频率等方法来动态调整服务器广播数据更新报告的频率及内容,在客户端接收服务器广播的数据更新报告后将缓存中已被更新过数据项的值用新值替换掉,而不直接将该数据项立即移出缓存。通过对该方法进行性能的分析,表明该方法能良好地适应数据更新频率不断变化的移动数据计算环境。     

基于变周期数据广播的缓存一致性维护

为了提高移动计算环境中缓存数据效率，在分析现有成果的基础上，提出了基于变周期数据广播的缓存一致性维护的策略。该策略根据数据的访问用户数目以及数据更新的频率等方法来动态调整服务器广播数据更新报告的频率及内容，在客户端接收服务器广播的数据更新报告后将缓存中已被更新过数据项的值用新值替换掉，而不直接将该数据项立即移出缓存。通过对该方法进行性能的分析，表明该方法能良好地适应数据更新频率不断变化的移动数据计算环境。     

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

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

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

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

Estimating Effective Prefetch Distance in Threaded Prefetching for Linked Data Structures

Helper threaded prefetching based on chip multiprocessor has been shown to reduce memory latency and improve overall system performance, and has been explored in linked data structures accesses. In our earlier work, we had proposed an effective threaded prefetching technique that balances delinquent loads between main thread and helper thread to improve effectiveness of prefetching. In this paper, we analyze memory access characteristic of specific application to estimate effective prefetch distance range for our proposed threaded prefetching technique. The effect of hardware prefetchers on the estimation is also exploited. We discuss key design issues of our proposed method and present preliminary experimental results. Our experimental evaluations indicated that the bounded range of effective prefetch distance can be determined using our method, and the optimal prefetch distances can be determined based on the estimated effective prefetch distance range by few trial runs.     

预取机制在WebGIS中的应用

在当前网络地理信息系统(以下简称WebGIS)中,空间数据等大型数据在用户访问请求下,从远程服务器端向客户端传输时,往往引起传输延迟,延长了响应请求的时间,降低了效率.预取本来是用在操作系统中提高高速缓存存储器(Cache)性能的一种技术,但在WebGIS中,采用适当的预取机制可以减少用户在浏览器端的等待时间,提高客户端的工作效率.本文分析了几种预取机制,并根据GIS空间对象的特点,对预取机制在WebGIS上的应用作了讨论,以期提高WebGIS的性能.     

Performance optimization problem in speculative prefetching

Speculative prefetching has been proposed to improve the response time of network access. Previous studies in speculative prefetching focus on building and evaluating access models for the purpose of access prediction. This paper investigates a complementary area which has been largely ignored, that of performance modeling. We analyze the performance of a prefetcher that has uncertain knowledge about future accesses. Our performance metric is the improvement in access time, for which we derive a formula in terms of resource parameters (time available and time required for prefetching) and speculative parameters (probabilities for next access). We develop a prefetch algorithm to maximize the improvement in access time. The algorithm is based on finding the best solution to a stretch knapsack problem, using theoretically proven apparatus to reduce the search space. An integration between speculative prefetching and caching is also investigated     

树形网络中的副本更新策略及算法

树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一。面对网络中数据访问需求的动态变化,好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本。针对此问题提出了两种贪心的动态副本更新策略,最大重用策略和请求覆盖策略。通过算法复杂度分析和仿真实验可以看出,所提出的两种算法的最坏时间复杂度为O(nlog n),远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5),而网络运行及副本更新成本与最优解相差不超过11%。在极大地缩短了运算时间的同时,保持了尽可能低的网络运行及副本更新成本。     

A novel dynamic network data replication scheme based on historical access record and proactive deletion

Data replication is becoming a popular technology in many fields such as cloud storage, Data grids and P2P systems. By replicating files to other servers/nodes, we can reduce network traffic and file access time and increase data availability to react natural and man-made disasters. However, it does not mean that more replicas can always have a better system performance. Replicas indeed decrease read access time and provide better fault-tolerance, but if we consider write access, maintaining a large number of replications will result in a huge update overhead. Hence, a trade-off between read access time and write updating cost is needed. File popularity is an important factor in making decisions about data replication. To avoid data access fluctuations, historical file popularity can be used for selecting really popular files. In this research, a dynamic data replication strategy is proposed based on two ideas. The first one employs historical access records which are useful for picking up a file to replicate. The second one is a proactive deletion method, which is applied to control the replica number to reach an optimal balance between the read access time and the write update overhead. A unified cost model is used as a means to measure and compare the performance of our data replication algorithm and other existing algorithms. The results indicate that our new algorithm performs much better than those algorithms.     

Pentium4处理器的内存层次分析

处理器存储系统的效率对其整体性能有着十分重要的作用。文中介绍了P4处理器内存的体系结构，它包括一级数据Cache、二级Cache、Trace Cache；各部分完成的功能以及为提高命中率和降低存取时间，从而提高效率而采取的预取处理机制；P4处理器主要采取具有层次结构的内存设计、大容量的二级Cache和在跟踪Cache中采用预取处理机制的方法来提高Cache的命中率和降低未命中的代价来缩短处理器的访问时间，最终达到提高处理器整体性能的目的。     

Compiler Controlled Prefetching for Multiprocessors Using Low-Overhead Traps and Prefetch Engines

In this paper we propose and evaluate a new data-prefetching technique for cache coherent multiprocessors. Prefetches are issued by a functional unit called a prefetch engine which is controlled by the compiler. We let second-level cache misses generate cache miss traps and start the prefetch engine in a trap handler. The trap handler is fast (40–50 cycles) and does not normally delay the program beyond the memory latency of the miss. Once started, the prefetch engine executes on its own and causes no instruction overhead. The only instruction overhead in our approach is when a trap handler completes after data arrives. The advantages of this technique are (1) it exploits static compiler analysis to determine what to prefetch, which is hard to do in hardware, (2) it uses prefetching with very little instruction overhead, which is a limitation for traditional software-controlled prefetching, and (3) it is accurate in the sense that it generates very little useless traffic while maintaining a high prefetching coverage. We also study whether one could emulate the prefetch engine in software, which would not require any additional hardware beyond support for generating cache miss traps and ordinary prefetch instructions. In this paper we present the functionality of the prefetch engine and a compiler algorithm to control it. We evaluate our technique on six parallel scientific and engineering applications using an optimizing compiler with our algorithm and a simulated multiprocessor. We find that the prefetch engine removes up to 67% of the memory access stall time at an instruction overhead less than 0.42%. The emulated prefetch engine removes in general less stall time at a higher instruction overhead.