张斯伟

摘要: 通过分析存储器的层次结构，引出了从单处理器系统到多处理器系统存储器层次结构的新问题，即高速缓存一致性的问题。因此，在多线程同时对共享内存进行读写操作时，Cache缺失和多处理器数据不一致会带来的相应的内存读写性能损耗。该文基于这个问题，设计了面向多线程内存读写延时的内存读写效率的测试方法。并通过的实验，指出了绑定同一个处理器，会使得对共享内存数据访问的效率提高。并基于这个测试结果给出了对并行程序的优化建议。

关键词:多处理器系统；内存性能；性能评估

中图分类号：TP316 文献标识码：A 文章编号：1009-3044(2012)36-8814-04

从单处理器系统到多处理器系统，是一次里程碑式的飞跃。而随着电子器件成本的减少，多核系统的应用也变得越来越广泛。但是，多处理器系统比单处理器系统更负责，从而带来了很多问题。在现在在单机系统中比较流行的SMP多核结构，在内存性能上，与单处理器系统就有很大不同。其中比较重要的一项就是高速缓存的数据一致性[1]。高速缓存的数据一致性问题表现在程序上，就是当多处理器并行的处理同一个内存中的数据，会造成L2 Cache的缺失，从而使得高速缓存的同步消耗掉一定的性能。而在以前的很多测试方法中，是没有考虑在不同处理器上访问同一个内存的性能损耗，比如Lmbench测试套件[2]，Lmbench是对内存从低地址到高地址，依次测量不同地址位的读写延时，而没有考虑并行状态下，数据同步的开销。该文考虑到多处理器在数据一致性上的开销，以及L2 Cache缺失率的影响，提出一种面向多线程内存读写延时的内存性能评估方法。

1 存储器的层次结构

在理想情况下，编程者总是希望存储容量无限大，而访存速度又是尽量快。解决这个问题的一个较经济的方法就是采用存储器层次结构，其依据是程序访问的局部性原理和内存技术的性能价格比原则。所谓程序的局部性原理，就是认为大部分程序不是均衡的访问所有代码和数据。而内存技术的性能价格比原则是，存储技术越快，价格越低，因此存储读写越快，存储器容量越小。为了解决存储器读写速度与存储器存储大小之间的矛盾，依据程序的局部性理论，计算机的学者们提出了一种较为经济的解决办法，就是存储器的层次结构。如图1所示。

为了匹配CPU的高速计算，越是快速的存储器，离CPU越近，当然，考虑到性价比，存储量也越小。当CPU计算需要访问数据的时候，则在离自己最近的存储器层次读取数据。当相应的存储器层次访问不到相应的数据，则在更远更慢存储量更大的存储层次访问数据，如果依然访问不到，则再往更远的一层访问，以此类推。我们称在相应的存储器层次能访问到目标数据称为命中，不能访问到目标数据称为不命中。由于程序的局部性原理，在低层次离CPU较近的存储器层次命中的概率非常的高。在现代计算机系统中，大部分程序的低层次存储器Cache命中率高达90%以上[3]。

随着CPU性能的提高，存取效率和计算速度之间的不平衡性变得越来越显著，因此存储层次的重要性不断增加。例如，在1980年，微处理器是不带Cache的，但是到了2001年，处理器内部通常带有两级Cache。随着多级存储结构的发展，数据的一致性问题也变得越来越复杂。所谓的数据的一致性问题，就是不同存储器层次数据不一致的问题。举个例子，当CPU要读写数据时，总是操作离自己最近的存储器，而当CPU改变了低层次存储器，比如Cache，中的数据时，由于存储总线的速度较慢，因此大部分的系统结构，都不会立即把Cache中相应的数据块写入高一层的存储器，比如内存。那么在CPU改变Cache后，到Cache把相应数据块写入内存中这段时间。Cache中的数据和内存中的数据时不一致的。这就是多级存储层次中的数据一致性问题

2 多处理器的高速缓存一致性

在多处理器系统中，数据的一致性问题的影响变得更为严重[4]。因为多处理器系统中，并行程序并非像单处理器系统中的“伪并行”运行，而由于多处理器能够同时执行不同的指令流，并行程序变成了“真并行”运行。而此时，数据的不一致性造成的影响会更为严重，而相对的Cache性能成为影响多处理器系统的关键资源[5-6]。

举个例子，CPU1修改内存地址为A的数据，由X1变为X2。而此时CPU1发现地址A的数据由于最近读写过，存在于L1 Cache中。那么CPU1会把L1 Cache中地址A的数据由X1修改为X2。假设此时CPU2要读地址A的数据，并且L1 Cache中也存在地址A的数据。而由于存储器层次的数据不一致性，如果CPU L1 Cache中的数据还未来得及写回，会导致L2 Cache的数据与CPU1的数据不同。进而导致CPU2中L1 Cache中地址A上的值还是X1，并未修改为X2。这样就会造成多处理器结构中的高速缓存一致性问题。

一般情况下，如果在一个存储系统中读取的任意一个数据项返回的结果都是最近写入的数值，那么可以认为该存储器是一致的。简单来说，存储器行为包括两个方面，第一个方面叫做高速缓存一致性，它定义了读操作可以返回什么样的数值。第二个方面较存储器的一致性，它定义了写入的数值什么时候才能被读操作返回。第一个性质为了保证程序的顺序，第二个性质定义了所谓的存储器一致性是什么。

为了解决高速缓存一致性问题，处理器的设计人员在硬件上引入了一个协议，称为高速缓存一致性协议来，来解决该问题。采用比较广泛的有两类协议，目录式协议和监听式协议[7]。目录式协议是把所有物理块共享状态存放在一个地点，通过访问目录，来同步数据。监听式就是在每个含有物理存储器中数据块副本的高速缓存还要保留在该数据块的共享状态，但是并不集中保存状态。高速缓存通常放在共享存储总线上，所有高速缓存对总线进行监听，来确定是否含有自己请求数据块的副本。

因此在多处理器同时对同一块内存进行操作的时候，会造成L1 Cache的一致性同步开销和L2 Cache缺失，这与单处理器系统有本质上的不同。因此在多处理器系统中，多处理器对相同内存操作的效率，影响着多线程程序对内存的读写效率。

由测试结果，可以看出。不同线程绑定在同一个处理器上时，内存读写表现出了较高的效率，绑定在同一个处理器上，延时大概比绑定在不同的处理器上减少4%~5%。而线程绑定在不同处理器上时，也表现出更高的不稳定性，其标准偏差比绑定在同一个处理器上时高81.5%。

5 多处理器架构下并行程序优化建议

从单处理器系统到多处理器系统是一个飞跃，对编程者也是一个挑战。由上述测试结果可见，无论是在相同处理器上还是不同处理器上，多线程在访问共享内存时都会造成较大的性能损失。因此在进行并行程序的编写时，应提高线程的独立性，即减少线程间的数据相关。这样，每个线程的指令流访问独立的数据流，提高程序的并行性。

但是在多线程程序中很难保证每个线程之间的数据不重合。这样必然涉及共享内存的访问和数据访问的同步。由上述测试结果可得，在线程间共享数据较大时，尽量使共享数据的线程绑定在同一个内核上进行，这样不仅内存读写效率提升，而且效率也更加稳定。

6 结束语

相对于单处理器系统，多处理器系统虽然在性能上获得了大幅度的提升，但是也使得硬件和软件结构变得更加复杂。使得以前相对简单的性能问题，由于多处理器的并行，变得比以前复杂。

该文首先分析了存储器的层次结构，引出了在多处理器结构下，高速缓存一致性的问题，指出在多线程同时对共享内存进行操作的时候，会出现线程同步和多处理器数据一致性带来的性能损耗。基于这一点，设计了面向多线程内存读写延时的内存读写效率的测试方法。并通过在Linux平台上的实验，指出了绑定同一个处理器，会使得对共享内存数据访问的效率提高。并基于这个测试结果给出了对并行程序的优化建议。

参考文献 ：

[1] Jeffey K,David O,Mark H,et al.The stanford FLASH multiprocessor[C]// Chicago, Illinois, USA:Proceedings of the 21st Annual ACM/IEEE International Symposium on Computer Architecture,1994: 302-313.

[2] BROWN A,SELTZER M. Operating system benchmarking in the wake of lmbench：a case study of the performance of netbsd on the Intel x86 architecture[C]∥ACM SIGMETRICS International Conference on the Measurement and Modeling of Computer Systems.NewYork,USA:ACM,1997:214-224.

[3] 左琦,黄洋.嵌入式应用环境下的Cache性能分析[J].计算机工程,2006(1).

[4] Fedorova A, Seltzer M, Small C, et al. Throughput-oriented scheduling on chip multithreading systems, Technical ReportTR-17-04 [R]. Cambridge, USA: Harvard University,2004.

[5] 卢宇彤,杨学军,所光.一种面向多核系统的并行计算任务分配方法[J].计算机研究与发展,2009, 23(2): 359-364.

[6] Kandemir M, Chen G. Locality-aware process scheduling for embedded MPSoCs, 2005[C]//Proceedings-Design, Automation and Test in Europe, DATE 05, v Ⅱ, Munich, Germany, March 7-11, 2005. Munich, Germany: IEEE Conference Publications, 2005.

[7] Hennessy J L,Patterson D A.Computer Architecture: A Quantitative Approach[M]. 4th ed. Morgan Kaufmann, 2006.