《并行程序设计与算法实践》要求学生在龙芯3A实验平台上设计并行算法并实现。实验平台由一块处理板、一块监控板和一块背板等组成。
实验平台的逻辑结构如图1所示。处理板承载4个处理单元，每个处理单元包括一个龙芯3A四核CPU、2GB DDR2内存、RTL8110千兆以太网卡芯片、BIOS Flash、串口收发芯片以及电源变换电路等。四个龙芯3A处理器通过网络实现互连。监控电路检测4个处理单元的状态，并实现对其控制。
图1 实验平台逻辑结构
实验平台的系统软件以开源软件为主（见图2），具有兼容性强、易维护、易升级、易使用等特点。处理单元操作系统为Debian GNU/Linux无盘系统，采用稳定高效的2.6.27内核。
图2 软件系统结构
要求同学在下面的实验中选一个题目，根据指导书实验方法和步骤独立完成某个实验内容。要求：
（1）记录实验过程，重要步骤或者结论必须拷屏；
（2）数据及结果分析：根据不同的实验内容，记录具体的实验数据或程序运行结果（要求拷屏）。实验数据量较大时，最好制成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释；
（3）分析和总结：对程序与算法性能改进结论，总结和体会。
附录《并行程序设计与算法实践》实验题目，也可以自选课程要求的题目：
实验一2–D Mesh互联网络构建及X–Y选路实现
实验二SMP系统中帧听高速缓存一致性协议的设计
实验三虚拟机内关键技术的研究
实验四多核处理器内部存储机制的研究
SMP系统中帧听高速缓存一致性协议的设计
1实验原理
SMP（SymmetricalMulti-Processing）又叫对称多处理机，是指在一个计算机上汇集了一组处理器(多CPU)，各CPU之间共享内存子系统以及总线结构。它是相对非对称多处理技术而言的、应用十分广泛的并行技术。在这种架构中，一台电脑不再由单个CPU组成，而同时由多个处理器运行操作系统的单一复本，并共享内存和一台计算机的其他资源。虽然同时使用多个CPU，但是从管理的角度来看，它们的表现就像一台单机一样。系统将任务队列对称地分布于多个CPU之上，从而极大地提高了整个系统的数据处理能力。所有的处理器都可以平等地访问内存、I/O和外部中断。在对称多处理系统中，系统资源被系统中所有CPU共享，工作负载能够均匀地分配到所有可用处理器之上。从而提高整个系统的数据处理能力。
1.1SMP的特点
如图1.1所示，SMP系统中任何处理器均可以对称地访问任何存储单元和I/O 设备，且具有相同的访存时间（故也称之为均匀存储访问UMA结构）；它具有单一的物理地址空间，所有处理器的存储单元按单一地址空间编址；它的多级高速缓存可支持数据局部性，且其一致性由硬件来实现；SMP系统中处理器间的通信用简单的读/写指令来完成，故具有低通信延迟的特点。
图1.1 SMP机器的结构图
1.2高速缓存一致性问题
多处理器中存在共享和私有数据的高速缓存，所有数据是被单个处理器使用的，而共享数据则是被多个处理器使用的，本质上是通过读写共享数据完成处理器之间的通信。把一个私有数据缓存之后，对该数据的访问就可以在高速缓存中进行。把共享数据装载到高速缓存中时，会在多个高速缓存中形成副本。一个内存系统应该能提供一组保存值的存储单元，当对一个存储单元执行读操作时，应该能返回“最近”一个对该存储单元的写操作所写入的值。然而，当两个运行在不同物理处理器上的进程通过不同的高速缓存层次来看共享内存时，其中一个进程可能会看到在它的高速缓存中的新值，而另一个则可能会看到旧值，这就引入了一个问题，多处理器的高速缓存一致性问题。
通常，按照高速缓存的写策略的不同，有写直达WT和写回WB两种高速缓存。写直达高速缓存采用的策略是一旦高速缓存中的一个字被修改，则在主存中要立即修改；而写回高速缓存策略是当被修改的字从高速缓存中被替换或消除时，才真正修改主存。
总之，造成高速缓存一致性问题的原因，主要是同一个内存块的拷贝可能同时出现在多个处理器的高速缓存中，多个处理器多这些拷贝的存取，可能会使这些拷贝的内容出现不一致。
图1.2 一个引起高速缓存一致性问题的例子
1.3总线侦听实现高速缓存一致性
由于基于总线的SMP机器是通过高速共享总线将商用的微处理器（包括高
速缓存）与共享存储器连接起来的，因此在设计中正好可以利用总线的特性来实现高速缓存一致性。总线上的每个处理单元的高速缓存控制器都能侦听到总线上出现的事务，一旦发现与自己相关的事务，就执行相应的动作来保证高速缓存一致性。而总线的事务对所有控制器以相同次序可见的这个特点就保证了侦听一致性协议的实现。于是，只要保证以下两点：
（1）与内存操作相关的所有的必要的事务都出现在总线上；
（2）控制器能采取适当的措施来处理相关的事务。
即可设计实现高速缓存一致性协议。
侦听协议可由三部分组成：
（1）状态集合：一个与本地高速缓存中内存块相关联的状态集合；
（2）状态转换图：以当前状态和处理器请求或观察到的总线作为输入，输出该块的下一个状态；
（3）动作：与每个状态转换相关的实际动作，这是由总线、高速缓存和处理器的具体设计来决定的。
1.4侦听高速缓存一致性协议
本实验中介绍的协议都是基于写回高速缓存中的写无效协议。写回，即主存的更新要到发生替换时才进行，因为它只需占有较少的总线周期；写无效，即当本地高速缓存中数据被更新后，会使所有其他高速缓存中的响应数据拷贝无效（如果有的话），接下来同一个处理器发出的对该内存块的写操作就不会在总线上引起任何通信，相应的还有写更新（一旦发生写操作，则更新所有数据拷贝）。
1.4.1MSI协议
该协议定义了数据块的三种状态：
（1）无效（I）状态：该块在高速缓存中是无效或未进入高速缓存的；
（2）共享（S）状态：该块在高速缓存中未被修改过，在主存中是最新的，其他高速缓存中可能有也可能没有该块的有效拷贝；
（3）修改过（M）状态：也叫做脏状态，即只有该高速缓存中有该块的最新拷贝，主存中的拷贝是过时的，其他高速缓存中没有该块的有效拷贝。
如下为MSI侦听协议中，控制每个高速缓存中的每个块的状态转换图：