第一章引言
1.1问题的提出
计算机系统结构技术的飞速发展使得单体存储系统提供数据的速度无法满足处理器运算所需操作数存取速度的要求，而且这一差距还在不断加大.这是因为在处理器中采用了超标量体系结构、流水线体系结构、超长指令字技术和精简指令集等先进的处理器体系结构技术，使得单个处理器的峰值运算速度在以每两年左右翻一翻的速度在发展，而同期主要的主存储器件的存取速度的提高却较慢，如动态存储器(DRAM)每8一10年才能提高一倍.这样，在程序执行过程中，如果处理器不能从存储系统及时得到所需的数据，那么处理器就必须插人等待周期，从而造成处理器运算能力的浪费.所以，存储系统性能对于整个计算机系统变得越来越重要，已经成为提高计算机实际使用性能的一大瓶颈，在计算机系统整体性能中的关键性日益突出.在现在的计算机系统中，针对主存储器件的存取速度无法满足处理器存取速度要求的问题，人们设计了并行存储系统结构和层次存储系统结构.实践证明，它们可以提高存储系统的平均存取速度，是解决这一问题的有效方法.
在并行存储系统中，其存储系统由许多可并行访问的存储模块组成，如果单个存储模块的存取速度为坛、，当存储访问均匀分布在N个并行存储模块中，那么整个存储系统可以在编时间内提供N个数据，即平均存储时间为标卿.这样就可以通过增加并行存储系统的并行存储模块数来提高存储系统访问速度.这种并行存储系统在许多计算机系统中都得到了应用.即使在工作站和微型计算机系统中也可采样简单的并行存储技术来提高主存储系统的响应速度.
层次存储结构是另一种提高存储系统的存取速度的方法，在层次存储系统中，存储系统由多个具有不同存取速度的存储层次组成，其中上一层次的存储器件较下一层次的存储器件具有更快的存取速度，最接近运算单元的寄存器具有最快的存取速度.由于寄存器采用与运算单元相同的半导体工艺技术，且在芯片内与运算单元相邻，所以它基本上可以满足运算单元的存取速度要求，其它存储层次由于采用的存储器件的存取速度越来越慢，所以提供数据的速度就越来越慢.
层次存储结构的有效性是建立在处理器对存储系统访问的局部性原理基础上的.存储访问的局部性原理是指在程序运行过程中，处理器对数据的访问在时间上、空间上和顺序上表现为成簇的访问，即大多数程序在执行过程的某段时间内访问其地址空间的相对固定的某一部分.
高速缓存系统是层次存储结构中一个非常重要的组成部分，尤其是在主存储器的速度越来越无法满足高速处理器的存取要求的高性能计算机系统中，高速缓存技术得到了广泛的应用.同时为了最大限度地获得存储系统平均存取速度的提高，目前大多数处理器制造商都在处理器内部制作了一级高速缓存系统，以更高的速度向运算单元提供数据，有的厂家甚至在处理器内部制作了二级高速缓存系统.在高性能计算机中，人们还在主机板上设计了处理器片外的高速缓存系统，以期得到更好的存储系统性能.
1.2本文工作
然而，尽管人们期望通过在高性能计算机中应用并行存储系统和层次存储系统来解决存储系统的存取速度与处理器的存取速度要求之间不断加大的差距，在实际应用中发现并不是总能达到预期的目的。这是由于处理器的存取访问在并行存储系统结构中和高速缓存系统中存在存储体冲突和高速缓存行冲突.当在并行存储系统中出现存储体冲突或层次存储系统中出现不命中时，处理器所要等待的时间会比传统的主存储系统的存取时间更长.所以人们倾注了很大的精力来研究如何改进并行存储系统结构和高速缓存系统结构，以提高并行存储系统和层次存储系统的实际存储性能.
研究发现，并行存储系统和层次存储系统中的存储映射方法对它们的存储性能有很大的影响.
在并行存储系统研究中，人们设计了许多不同的数据分布技术，大致可分为交叉存储方法、线性斜排存储方法和非线性斜排存储方法.XOR斜排存储方法是一类非常有效的非线性斜排存储方法，作者设计和研究了许多具有实际使用价值的XOR存储方法.理论分析和模拟结果显示，这些XOR存储方法对科学计算，尤其是矩阵运算、线性方程求解、图象处理、数字信号处理等应用领域的科学计算和工程问题求解具有很好的效果.本文提出一种XOR并行存储方法，即叹一XOR斜排存储方法(详见第四章).在采用叹一XOR斜排存储方法的并行存储系统中，不仅可以并行存取在传统的交叉并行存储系统中可以并行存取的连续数据存取模式，而且可以并行存取许多其它在科学和工程应用程序中常用的数据存取模式，可以大幅度地提高存储系统的平均存取速度.
在高速缓存存储系统的设计中，受到硬件复杂度的限制，人们通常不采用全相联存储映射方法，而采用组相联、甚至直接映射的高速缓存映射技术.这就使得在传统的高速缓存系统中对程序运行中的存储访问的局部性利用得不够充分，在一些典型情况下，高速缓存技术甚至会降低系统的整体性能.本文对与高速缓存有关的问题进行了深人的分析，创造性地在高速缓存的映射中实现了XOR斜排存储方法，以使高速缓存系统可以充分利用程序执行过程中存储访问的局部性.在作者设计的P吧uim和平实验系统中，其二级高速缓存映射中使用了EE一XOR存储方法〔详见第五章).该实验系统的实际测试结果证明在高速缓存映射中采用XOR存储方法可以提高高速缓存的命中率，从而提高存储系统和计算机的整体性能.
本文分为七章.第一章引言部分介绍了在高性能计算机的存储系统设计中存在的问题;第二章回顾并行存储系统的研究概况;第三章回顾高速缓存系统设计;第四章详细介绍了作者设计的议一XOR斜排存储方法及其存储性质，与另夕LFJ种XOR斜排存储方法进行了比较，并在后半章分析了袱狠斜排存储方法应用于高速缓存系统时的存储特性;第五章介绍了一个在二级高速缓存系统中采用XOR斜排存储方法的Pnetium和平实验系统的设计过程;第六章对Pnetium和平实验系统中采用EE一XOR存储映射方法和采用常规存储映射方法的测试结果进行分析比较;在第七章，作者对XOR存储方法进行了总结，并提出了进一步的研究方向.最后，作者给出了参考文献和与系统设计和性能测试有关的附录A.
第二章并行存储技术回顾
随着半导体技术的不断发展，微处理器的结构越来越复杂，功能也越来越强大.但是，尽管处理器所采用的半导体技术和体系结构使其功能不断提高，而同期存储器件的性能提高相对较慢，这样在处理器性能和主存储器件性能之间的差距不断加大，对于高性能计算机来说尤其如此.在高性能计算机系统中，系统采用的处理器的运算单元具有高性能的流水线结构，每个处理器内部可以有多个处理单元，有的处理器还支持超长字指令技术和向量指令集，使得单个处理器的峰值运算速度不断提高.为了避免由于主存储系统的存取速度太慢而影响处理器发挥其潜在的高性能，系统设计者不仅在处理器和主存储系统之间增加了高速缓存系统，而且在主存储系统本身的系统结构上进行了重大改进.在主存储系统中采用多个并行存储模块就是一种最重要的主存储系统结构改进，这就是并行存储系统结构.
第三章 高速缓存.................................................. 25-48
3.1 层次存储系........................................................ 25-28
3.2 高速缓存的系统结构与........................................ 28-40
3.2.1 高速缓存的........................................................... 30-34
3.2.2 组相联高速缓存系统的存.................................... 34-36
3.2.3 高速缓存系统的............................................36
3.2.4 高速缓存系统的................................... 36-37
3.2.5 高速缓存一............................................. 37-40
3.3 提高高速缓存命中................................................ 40-48
3.3.1 改进程序的算..................................................... 43-48
第四章 XOR斜排...................................................................... 48-86
4.1 LR-XOR斜排存.................................................................. 48-61
4.1.1 LR-XOR斜排存储................................................ 48-50
4.1.2 LR-XOR斜排存储方法的并行.................................... 50-60
4.1.3 LR-XOR斜排存储方法的.......................................60
4.1.4 LR-XOR斜排存储................................................ 60-61
4.2 EE-XOR斜排....................................................... 61-65
4.3 几种XOR斜排存储方........................................................ 65-68
4.3.1 MG-XOR斜排存....................................................... 65-66
4.3.2 EE-MG-XOR斜排.................................................................. 66-67
4.3.3 几种XOR斜排存储................................................................ 67-68
4.4 斜排存储方法在数据高速缓......................................................... 68-86
4.4.1 并行存储系统和高速缓存........................................................... 69-71
4.4.2 斜排存储方法在数据高速缓存映射................................................. 71-86
4.4.2.1 在直接映射数据高速缓存映射....................................................... 71-73
4.4.2.2 在组相联数据高速缓存映射系................................................73-86
第五章 Pentium和平实................................... 86-117
总结
近年来，半导体工业技术的不断发展，使得计算机系统结构，尤其是作为计算机运算单元的微处理器体系结构得到了长足的发展，也使得与处理器峰值运算速度相关的时钟频率不断提高.在微处理器内部，采用了超标量体系结构、流水线体系结构、超长指令字体系结构、精简指令集结构和向量运算单元等先进的处理器体系结构技术，使得单个处理器本身具有同时进行多个运算的能力，处理器的峰值运算速度以接近每两年翻一翻的速度在迅速提高，但是，同期组成计算机主存储系统的器件的存取访问速度却没有得到与处理器运算速度相应幅度的提高，如动态存储器件的存取速度每8一10年才能翻一翻，所以在现代计算机系统设计中，存储系统的性能变得尤为重要.不论在大规模并行计算机系统中，还是在一般科学计算使用的工作站或微机系统中，存储系统都已经成为发挥处理器运算性能的主要瓶颈.基于这一认识，作者在对并行存储系统和层次存储结构中的高速缓存系统进行深人研究的基础上，提出了自己独到的见解，并设计实验系统进行了测试.
参考文献
l‘高勇，“采用斜移存储方案的向量”.中国科学院计算技术研究所硕士论文，l994.
2李惠安，，工服映象的分析”.中国科学院计算技术研究所硕士论文，l995.
3.郭晓涛，戈界分解的正利用率研究”，中国科学院计算技术研究所硕士论文，l996.
4刘志勇，李惠安.“并行和层次存储系统”，第八届全国信息存储学术会议论文集，第1一10页，西安，l994年10月.
5.熊劲，“单处理机系统的多级高速缓存”，中国科学院计算技术研究所硕士论文，l993.
6.胡伟武，“共享存储系统中的访存事件次序”，中国科学院计算技术研究所博士论文，1996.
7.乔香珍，.正性能与程序优化”，计算机学报，第19卷，第11期，996年11月.
8.陈国良、陈峻，计算理论与并行算法”，中国科学技术出版社，l99l年.
9.周祖成，“电子设计自动化(EDA)”，清华大学信息科学学院，l995月.
l0.“超大规模集成电路设计”.清华大学电子工程系，l989年3月.