局部性原理与高速缓存参数无关技术

在高速缓存参数无关的算法与数据结构的设计中,使用了许多技术,这些技术都是利用教据的时间和空间局部性,有效地使用计算机多级存储结构,进而提高算法与数据结构的效率。文中对若干利用局部性原理的高速缓存参数无关技术进行分析和总结。

高速缓存参数无关的高效算法

近年来,在高速缓存有效和磁盘有效的算法设计中提出了一个新的概念———高速缓存参数无关。在多级存储体系中,无需了解任何有关各层次的参数,高速缓存参数无关算法便可获得高的效率,且自动对所有各级存储体系都是有效的。本文主要讨论了多种不同的存储模型,并通过分析,证明了一些算法的高速缓存参数无关性。

高速缓存优化的并行连接算法

由于嵌套循环连接操作过程中存在较大的高速缓存缺失,严重影响了连接查询的性能。提出了一种基于缓冲的高速缓存参数无关的嵌套循环并行连接算法。通过高速缓存参数无关和缓冲技术,提高了连接算法的空间局部性和时间局部性。理论分析和实验结果表明,高速缓存优化后的串行连接算法的性能是原来的2倍,其并行算法效果近似线性加速比。

多核计算机上非递归并行计算矩阵乘积

提出"延迟隐藏"的数据预取模型,实现计算与访存的重叠操作,以达到共享二级缓存零缺失;给出"基本块"的概念,以简化算法的数据结构和减少存储开销;按基本块连续存储方式存储矩阵元素,从存储层次上优化算法,显著地减少页表缓冲缺失;采取非递归调度基本块的策略,充分利用多核计算机的共享二级缓存来减少访问主存的次数,并且不局限于某种特定的存储结构,实现算法缓存无关.多核计算机上的实验结果表明,给出的非递归计算矩阵乘积的线程级并行算法高效、可扩展.

一种通用的动态Web应用加速方案

在内容分发网络基础上,提出一个针对动态Web应用的数据库缓存应用模型。该应用模型采用内容无关缓存和部分复制的机制,通过内容无关缓存方法、基于主从协议模型的缓存一致性策略和基于相似关系的空间聚类算法等,可满足多种动态Web应用加速的需求。实验结果表明,该方法可有效地提高系统负载量,改善用户体验,抵御洪水用户的侵袭。