【作者】 吴英杰；

【导师】 王晓东；

【作者基本信息】 福州大学 ， 计算机软件与理论， 2004， 硕士

【摘要】 现代计算机的存储系统变得越来越复杂，它是由多级高速缓存、内存和磁盘组成一个层次结构，指令也不再是以常数时间顺序执行。对该层次存储体系中较低且速度较快的层次中字的访问可立即得到响应，而对较高层次的访问可能导致数百万的处理器周期延迟。因此，近年来算法设计策略发展的重点在于，寻找对存储系统较高层次访问次数最小化的最优算法。目前人们已经设计出许多优秀的算法，但是这些算法的设计与实现都是基于一个特定的层次，这就使得它们无法灵活运用在多个层次，或有效地运用在不同的体系结构。为了克服这一点，1999年Prokop等人提出了高速缓存参数无关算法和理想高速缓存模型的概念。高速缓存参数无关算法的目标是，在不了解任何有关各层次参数的情况下，最优地使用存储系统。并自动使算法对多级存储体系的每一级都是有效的。然而，目前对这些类型算法在实验方面所做的工作还相当少。本文首先对高速缓存参数无关最优算法的理论基础进行全面的分析和阐述。接着通过性能测试，把高速缓存参数无关算法与传统的基于RAM模型的算法做了比较，最后，在深入研究的基础上提出了一个最优的子线性工作空间的高速缓存参数无关的排序算法。本文的主要结论是，当处理大数据量时，高速缓存参数无关算法显著优于传统的基于RAM模型的算法。更多还原

【Abstract】 The memory system of modern computer are becoming increasingly sophisticated, which is a hierarchy consisting of multilevel caches、main memory and disk, also instructions are not executed sequentially and in constant time. Accessing words in the lower, faster levels of this memory hierarchy can be done virtually immediately, but accessing the upper levels may cause delays of millions of processor cycles.Consequently, recent developments in algorithm design have had a focus on developing algorithms that sought to minimize accesses to the higher levels of the hierarchy. Now, a number of optimal algorithms have been designed. However, these algorithms are designed and implemented with a very specific level in mind, making it infeasible to adapt them to multiple levels or use them efficiently on different architectures.To alleviate this, the notion of cache-oblivious algorithm and the ideal-cache model were developed by Prokop etc. in 1999. The goal of a cache-oblivious algorithm is to be optimal in the use of the memory hierarchy, but without knowing any parameters of the hierarchy. This automatically makes the algorithm efficient on all levels of the hierarchy. The experimental work done with these types of algorithms remain sparse, however.In this thesis, we present a thorough theoretical analysis and explanation of optimal cache-oblivious algorithms. We then do a performance investigation, comparing cache-oblivious algorithms with traditional RAM-model algorithms. In the last, on the basis of thorough research, we present an optimal sub-linear working space cache-oblivious sorting algorithm.We conclude that cache-oblivious algorithms do outperform traditional RAM-model algorithms when working on large data sets.更多还原