《番茄花园-九章多处理机.ppt》由会员分享，可在线阅读，更多相关《番茄花园-九章多处理机.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、番茄花园-九章多处理机 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 并行性并行性(parallelism)：指同一时刻或同一时间间隔内完成两种或两种：指同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。只要在时间上相互重叠，均存在并行性。以上性质相同或不同的工作。只要在时间上相互重叠，均存在并行性。并行性分：同时性、并发性。并行性分：同时性、并发性。并行性等级（执行的角度，从低到高）：并行性等级（执行的角度，从低到高）：1）指令内部并行性，即指令
2、内部的微操作之间的并行。）指令内部并行性，即指令内部的微操作之间的并行。2）指令间并行，即并行执行两条或多条指令。）指令间并行，即并行执行两条或多条指令。3）任务级或过程级并行，即并行执行两个或多个过程或任务（程序段）任务级或过程级并行，即并行执行两个或多个过程或任务（程序段）4）作业或程序级并行，即在多个作业或程序间的并行。）作业或程序级并行，即在多个作业或程序间的并行。阵列处理机（阵列处理机（SIMD）实现的是指令内部并行性（多数据流执行同一指）实现的是指令内部并行性（多数据流执行同一指令）。令）。多处理机系统（多处理机系统（MIMD）实现指令以上级（任务级、作业级）并行。实现指令以上级（
3、任务级、作业级）并行。并行性概念并行性概念并行性概念并行性概念多处理机系统的基本结构多处理机系统的基本结构多处理机系统的基本结构多处理机系统的基本结构互连网络处理机1处理机2处理机N存储器存储器存储器I/OI/O互连网络处理机1处理机2处理机N存储器存储器存储器I/OI/OI/O两种多处理机系统基本结构两种多处理机系统基本结构2）分布式存储器多处理机结构）分布式存储器多处理机结构（每台处理器有自己的处理器和（每台处理器有自己的处理器和I/O设备，处理器之间通过互连网设备，处理器之间通过互连网络实现点对点信息交换）络实现点对点信息交换）1）共享存储器多处理机结构）共享存储器多处理机结构（存储器和
4、（存储器和I/O设备是独立的子设备是独立的子系统，通过互连网络为所有处理系统，通过互连网络为所有处理器共享，任何两台处理器可以通器共享，任何两台处理器可以通过共享存储器单元实现通信）过共享存储器单元实现通信）两种多处理机系统基本结构：两种多处理机系统基本结构：1）共享存储器使多处理机拥有同一的寻址空间，一方面便于处理机之间的）共享存储器使多处理机拥有同一的寻址空间，一方面便于处理机之间的信息交换，另一方面使程序员无需在程序中显式地控制数据的分布和传输，信息交换，另一方面使程序员无需在程序中显式地控制数据的分布和传输，因而易于编程。因而易于编程。2）分布式存储器可以采用虚拟共享存储器技术。虚拟共
5、享存储器（）分布式存储器可以采用虚拟共享存储器技术。虚拟共享存储器（Virtual Shared Memory）对分布在各处理机的局部存储器在逻辑上统一编址，形）对分布在各处理机的局部存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟地址空间（成一个为所有处理机共享的虚拟地址空间（Virtual Address Space）。虚）。虚拟共享存储器技术方便了程序员编程，但是，处理机之间信息交换的物理实拟共享存储器技术方便了程序员编程，但是，处理机之间信息交换的物理实现仍然是通过点对点的通信。现仍然是通过点对点的通信。多处理机系统的基本结构多处理机系统的基本结构多处理机系统的基本结构多处理机系
6、统的基本结构MIMD结构特点（与结构特点（与SIMD比较）：比较）：1）MIMD结构有多个控制器，至少有多个指令部件，对各个结构有多个控制器，至少有多个指令部件，对各个PE实现单独控实现单独控制，而又相互协调配合。制，而又相互协调配合。2）MIMD结构的外围设备要能够被多个结构的外围设备要能够被多个PE分别调用，因而要通过互连网络分别调用，因而要通过互连网络转接。转接。3）MIMD互连网络必须满足各个互连网络必须满足各个PE随机访问主存储器的要求，必须有存储随机访问主存储器的要求，必须有存储映射部件，满足存储空间动态分配和处理机共享数据的需要。映射部件，满足存储空间动态分配和处理机共享数据的需
7、要。共享存储器共享存储器=共享存储器共享存储器+虚拟共享存储器虚拟共享存储器 共享存储多处理机共享存储多处理机(Shared Memory mulptiProcessors)，也称为对，也称为对称多处理机称多处理机SMP(Symmetry MultiProcessors)有三种模型：有三种模型：1)UMA多处理机多处理机 均匀存储器存取模型均匀存储器存取模型(Uniform Memory Access)存储器被所有处理机均匀共享存储器被所有处理机均匀共享 所有处理机对所有存储单元具有相同的存取时间所有处理机对所有存储单元具有相同的存取时间 每台处理机有局部每台处理机有局部Cache 外围设备可
8、以共享外围设备可以共享2)NUMA多处理机多处理机 非均匀存储器存取非均匀存储器存取(Nonuniform Memory Access)模型模型 存储器访问时间随存储单元的位置不同而变化。存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部存储器地址空间的集合就组成了全局地址空间。存储器地址空间的集合就组成了全局地址空间。处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟
9、。则比较慢，因为通过互连网络会产生附加的时间延迟。共享存储多处理机共享存储多处理机共享存储多处理机共享存储多处理机 系统互连网络系统互连网络NUMA多处理机模型多处理机模型P1LM1P2LM2PnLMn系统互连网络系统互连网络（总线、交叉开关、多级网络）（总线、交叉开关、多级网络）UMA多处理机模型多处理机模型P1P2PnSM1SM2SM2I/O3)COMA多处理机多处理机 只有只有Cache的存储器结构的存储器结构(Cache-Only Memory Architecture)模型，模型，COMA是一种只用是一种只用Cache的多处理机系统，实际上，的多处理机系统，实际上，COMA模型是模型
10、是NUMA模模型的一种特例。后者分布存储器换成了型的一种特例。后者分布存储器换成了Cache。在每个处理机结点上没有主存储器，全部在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址组成了全局虚拟地址空间。空间。远程远程Cache访问通过分布访问通过分布Cache目录进行。目录进行。共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。互连网络互连网络COMA多处理机模型多处理机模型目录目录1Cache1P1目录目录2Cache2P2目录目录nCachenPn多处理机系统的特点多处理机系统的特点多处理机系统的特点
11、多处理机系统的特点1）结构灵活性）结构灵活性 SIMD从解决专用问题发展而来，其结构针对数组向量处理算法而设计，特点是：从解决专用问题发展而来，其结构针对数组向量处理算法而设计，特点是：处理单元很多，但只需设置有限和固定的互连通路，即可满足并行性很高的算法需要，处理单元很多，但只需设置有限和固定的互连通路，即可满足并行性很高的算法需要，是以解决大型数组计算问题为主的计算机。用库克分类标准，属于数组单执行（是以解决大型数组计算问题为主的计算机。用库克分类标准，属于数组单执行（SEA）一类。一类。MIMD有较强的通用性，即使对数组运算，也可以同时对多个数组进行不同的处理，有较强的通用性，即使对数组
12、运算，也可以同时对多个数组进行不同的处理，称为数组多执行（称为数组多执行（MEA）；它可以同时对多个标量数据进行处理，称为标量多执行）；它可以同时对多个标量数据进行处理，称为标量多执行（MES）。要求能适应更多样的算法，更灵活的结构，实现各种复杂的互连模式，同时）。要求能适应更多样的算法，更灵活的结构，实现各种复杂的互连模式，同时解决共享资源冲突问题，因此，解决共享资源冲突问题，因此，MIMD中处理单元数量不多。中处理单元数量不多。SIMD：专用，：专用，PE数很多（几千个），固定有限的通信数很多（几千个），固定有限的通信MIMD：通用，通用，PE几十个，高速灵活的通信几十个，高速灵活的通信2
13、）程序并行性）程序并行性 SIMD实现操作级的并行，其并行性存在于指令内部，由于结构固定，加上系统专实现操作级的并行，其并行性存在于指令内部，由于结构固定，加上系统专用，因此并行性易于实现。用，因此并行性易于实现。MIMD不限于解决数组向量问题，其并行性存在于指令外部，表现在多个任务之间，不限于解决数组向量问题，其并行性存在于指令外部，表现在多个任务之间，加上通用性要求，从而使程序并行性的识别难度较大，需要利用多种途径，如算法、程加上通用性要求，从而使程序并行性的识别难度较大，需要利用多种途径，如算法、程序语言、编译、操作系统直至指令、硬件，尽量挖掘各种潜在的并行性，而且程序并行序语言、编译、
14、操作系统直至指令、硬件，尽量挖掘各种潜在的并行性，而且程序并行化的主要任务不应放在程序员肩上。化的主要任务不应放在程序员肩上。3）并行任务派生）并行任务派生SIMD把同种操作集中在一起，由指令直接启动各把同种操作集中在一起，由指令直接启动各PE同时工作。同时工作。MIMD用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器并行执行的另一些任务，如果任务数多于处理机数，多余的任务进入排队器等待。等待。4）进程同步）进程同步 SIMD仅一个仅一个CU，自然是同步的，
15、自然是同步的 MIMD执行不同的指令，工作进度不会也不必保持相同，先做完的要停执行不同的指令，工作进度不会也不必保持相同，先做完的要停下来等待。有数据相关和控制相关也要停下来等待，要采取特殊的同步措施下来等待。有数据相关和控制相关也要停下来等待，要采取特殊的同步措施来保持程序所要求的正确顺序。来保持程序所要求的正确顺序。一个简单的例子：一个简单的例子：Y=A+B*C*D/E+F用两个处理机：用两个处理机：CPU1：CPU2：B*C，D/E，A+F，B*C*D/E，A+B*C*D/E+F5）资源分配和进程调度）资源分配和进程调度 SIMD的的PE数目固定，受同一控制器控制，程序员采用屏蔽手段改变
16、实数目固定，受同一控制器控制，程序员采用屏蔽手段改变实际参加操作的际参加操作的PE数目。数目。MIMD执行并发任务，需用处理机的数目不固定，各个处理机进入或退执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化。因此，如何出任务的时刻不相同，所需共享资源的品种、数量又随时变化。因此，如何进行资源分配和进程调度对整个系统的效率有直接的影响。进行资源分配和进程调度对整个系统的效率有直接的影响。多处理机的多处理机的多处理机的多处理机的CacheCache一致性问题一致性问题一致性问题一致性问题问题由来问题由来 由于一般的由于一般的MIMD中处
17、理机除了拥有共享存储器外，还有自己的中处理机除了拥有共享存储器外，还有自己的Cache，因此，因此，MIMD的一般模型可描述如下（假设两个处理机）：的一般模型可描述如下（假设两个处理机）：P1P2总线总线共享共享存储器存储器处理机处理机高速缓冲高速缓冲存储器存储器 数据分布在数据分布在P1的的Cache1、P2的的Cache2和共享存储器中。多处理机的和共享存储器中。多处理机的Cache的不一致包括的不一致包括Cache1与与Cache2之间的数据不一致以及之间的数据不一致以及Cache1、Cache2与共享存储器之间的数据不一致。与共享存储器之间的数据不一致。问题是有哪些因素会引起上述数据不
18、一致？问题是有哪些因素会引起上述数据不一致？1）共享可写数据引起的不一致）共享可写数据引起的不一致 假设有两个处理机假设有两个处理机P1、P2，它们私有的，它们私有的Cache分别为分别为C1、C2，C1、C2中保存共享存储器某个数据中保存共享存储器某个数据X的拷贝，其初始状态如下图所示。的拷贝，其初始状态如下图所示。假设假设P1改写改写C1，使，使X变为变为X，如果，如果P1采用采用“写通过写通过WT(Write Through)”策略，那么，主存对应的数据也改为策略，那么，主存对应的数据也改为X，但是，但是C2中的对应数据仍中的对应数据仍然为然为X，这时如果，这时如果P2读读C2，那么读取
19、的数据将是，那么读取的数据将是X，而非，而非X，即与主存对应，即与主存对应数据不一致；如果采用数据不一致；如果采用“写回写回WB(Write Back)”策略，即策略，即P1更新更新C1后主存后主存数据不立即更新，而是当该数据从数据不立即更新，而是当该数据从C1调出时才更新主存数据，那么，主存调出时才更新主存数据，那么，主存数据仍然是数据仍然是X，这就导致了，这就导致了C1中的数据与主存数据不一致。中的数据与主存数据不一致。多处理机的多处理机的多处理机的多处理机的CacheCache一致性问题一致性问题一致性问题一致性问题P1P2XXX共享存储器处理机高速缓冲存储器初始状态P1P2XXX写通过
20、P1P2XXX总线写回2）进程迁移引起的不一致）进程迁移引起的不一致 假设假设P1的的C1保存共享数据保存共享数据X的拷贝，而的拷贝，而P2的的C2没有该共享数据。若没有该共享数据。若P1的进程对的进程对C1中的中的X进行了修改，使其变为进行了修改，使其变为X，且采用，且采用“写回写回”策略，内存中策略，内存中的数据仍然是的数据仍然是X。由于某种原因，该进程从。由于某种原因，该进程从P1迁移到迁移到P2上运行，修改的上运行，修改的X仍仍在在P1的的C1中，中，P2上的进程从主存读取数据上的进程从主存读取数据X到到C2，即迁移了的进程读取的，即迁移了的进程读取的数据是数据是“过时过时”了的了的X
21、，而非迁移前修改过的，而非迁移前修改过的X。若若C1、C2都有共享数据都有共享数据X的拷贝，的拷贝，P2进程修改了进程修改了C2中中X，使其变为，使其变为X，且采用，且采用“写通过写通过”策略，使主存中的策略，使主存中的X也修改为也修改为X。由于某种原因，该进。由于某种原因，该进程从程从P2迁移到迁移到P1上运行，此时，上运行，此时，C1中仍然是中仍然是X，而不是修改过的，而不是修改过的X。P1P2XXX共享存储器处理机调整缓冲存储器迁移之前P1P2XXX写通过P1P2XXX总线写回3）I/O传输引起的不一致传输引起的不一致 若若C1、C2都有共享数据都有共享数据X的拷贝，当的拷贝，当I/O处
22、理机将一个新的数据处理机将一个新的数据X输入输入内存时，导致了主存与内存时，导致了主存与Cache之间的数据不一致。之间的数据不一致。若若C1、C2都有共享数据都有共享数据X的拷贝，当的拷贝，当P1运行过程中修改了运行过程中修改了X的值，使其的值，使其变为变为X，P1采用采用“写回写回”策略，那么，主存的策略，那么，主存的X与与C1中的中的X不一致。这时，不一致。这时，若若I/O处理机要求输出，输出的将是主存的处理机要求输出，输出的将是主存的X，而非修改后的，而非修改后的X。P1P2XX存储器处理机高速缓冲存储器P1P2XX（写通过）P1P2XX总线（写回）XI/O存储器XX（输入）存储器XX
23、（输出）多处理机的多处理机的多处理机的多处理机的CacheCache不一致性解决办法不一致性解决办法不一致性解决办法不一致性解决办法1）监听协议）监听协议(Snoopy Protocol)：适用基于总线互连结构的系统。：适用基于总线互连结构的系统。2）基于目录的协议：适用非总线互连结构的系统。）基于目录的协议：适用非总线互连结构的系统。监听协议监听协议 通过总线监听机制实现高速缓冲和共享存储器之间的数据一致性。通过总线监听机制实现高速缓冲和共享存储器之间的数据一致性。策略：策略：Cache与主存之间与主存之间：“写通过写通过WT”和和“写回写回WB”Cache与与Cache之间之间：“写无效写
24、无效WI(Write Invalidate)”和和“写更新写更新WU(Write Update)”1）“写通过写通过WT”：改写：改写Cache时同时改写主存数据。时同时改写主存数据。2）“写回写回WB”：改写：改写Cache时不立即改写主存数据，而是等时不立即改写主存数据，而是等Cache数据调数据调出时才改写主存数据。出时才改写主存数据。3）“写无效写无效WI”：本地：本地Cache数据改写时，使远程数据块拷贝无效。数据改写时，使远程数据块拷贝无效。4）“写更新写更新WU”：本地：本地Cache数据改写时，通过总线把改写的数据块广播数据改写时，通过总线把改写的数据块广播到含有该数据块拷贝的
25、所有其它到含有该数据块拷贝的所有其它Cache。上述上述4中策略可组合起来使用，即：中策略可组合起来使用，即：“写通过写通过WT”+“写无效写无效WI”、“写通过写通过WT”+“写更新写更新WU”“写回写回WB”+“写无效写无效WI”、“写回写回WB”+“写更新写更新WU”P1P2XX共享存储器处理机高速缓冲存储器更新之前P1P2XI写无效P1P2XX总线写更新 由于写更新策略在本地由于写更新策略在本地Cache修改时要通过总线将修改过的数据块内容修改时要通过总线将修改过的数据块内容广播给所有含有该数据块拷贝的其它广播给所有含有该数据块拷贝的其它Cache，增加了总线的负担，所以，一，增加了总
26、线的负担，所以，一般系统中，很少使用写更新策略，而是采用写无效策略。基于此，以下只讨般系统中，很少使用写更新策略，而是采用写无效策略。基于此，以下只讨论写无效策略的监听协议。论写无效策略的监听协议。1.采用写通过策略的采用写通过策略的Cache 1）数据块状态）数据块状态：有效和无效。有效表示数据块内容正确，无效表示数：有效和无效。有效表示数据块内容正确，无效表示数据块内容已据块内容已“过时过时”或不在本地或不在本地Cache中。需要注意的是：有效和无效分别中。需要注意的是：有效和无效分别表示本地处理机对应数据块状态，而非整个表示本地处理机对应数据块状态，而非整个Cache状态。状态。2）状态
27、图）状态图有效有效无效无效R1,W1WrRr,WrR1,W1,Rr说明（假设本地处理机说明（假设本地处理机P1，对应的，对应的Cache为为C1；其它处理机；其它处理机Pr，对应的，对应的Cache为为Cr）：）：R1本地读本地读(P1读读C1),W1本地写本地写;RrPr读读Cr,WrPr写写Cr。远程读，引起本地写回操作2.采用写回策略的采用写回策略的Cache 1）数据块状态）数据块状态：读写、只读和无效。只读状态表示整个系统中不止一：读写、只读和无效。只读状态表示整个系统中不止一个数据块拷贝是正确的；读写状态表示数据块至少被修改过一次，存储器中个数据块拷贝是正确的；读写状态表示数据块至
28、少被修改过一次，存储器中相应数据块还没有被修改，即在整个系统中只有一个数据块拷贝是正确的。相应数据块还没有被修改，即在整个系统中只有一个数据块拷贝是正确的。2）状态图）状态图读写读写无效无效W1RrR1,RrR1,W1只读只读Rr,WrW1WrWrR13.写一次写一次(Writeonce)协议协议 结合写通过和写回的优点，为减少总线流量，结合写通过和写回的优点，为减少总线流量，Cache第一次写采用第一次写采用写通过写通过策略，策略，尔后的写采用尔后的写采用写回写回策略，此时，整个系统只有一份正确的拷贝。策略，此时，整个系统只有一份正确的拷贝。1）数据块状态）数据块状态：有效、无效、保留、重写
29、。为了区分是否第一次写，将读写状：有效、无效、保留、重写。为了区分是否第一次写，将读写状态分成态分成“保留保留”和和“重写重写”两种状态。其中，两种状态。其中，“保留保留”状态表示数据从存储器读入状态表示数据从存储器读入Cache后只修改过一次，这时，后只修改过一次，这时，Cache中的拷贝与存储器中的拷贝一致，而且是正中的拷贝与存储器中的拷贝一致，而且是正确的；确的；“重写重写”状态表示数据块不止一次被修改过，此时，存储器中的数据块不正状态表示数据块不止一次被修改过，此时，存储器中的数据块不正确。确。“有效有效”状态表示从存储器读入数据块，状态表示从存储器读入数据块，Cache中的数据与存储
30、器中的一致，中的数据与存储器中的一致，相当于写回的相当于写回的“只读只读”状态。状态。2）状态图）状态图无效无效重写重写R1WrR1,RrRr,Wr有效有效RrW1WrW1R1保留保留W1RrR1,W1Wr中心思想：中心思想：1）使用）使用Cache目录目录2）记录有关数据块拷贝驻留）记录有关数据块拷贝驻留Cache位置和状态信息位置和状态信息3）无效命令只发给保存有关数据块拷贝）无效命令只发给保存有关数据块拷贝Cache基于目录的协议分类基于目录的协议分类(目录如何维护和目录存放位置目录如何维护和目录存放位置)：1）全映射）全映射(full-map)目录目录2）有限）有限(limited)目
31、录目录3）链式）链式(chained)目录目录1.全映射目录协议全映射目录协议数据结构数据结构1）共享存储器中目录项）共享存储器中目录项2）Cache状态位状态位基于目录的协议基于目录的协议基于目录的协议基于目录的协议C-数据数据X共享存储器共享存储器有效位有效位允许写允许写数据数据XCache重写位(数据是否已重写)1:已重写0:末重写处理机位(每一位对应一台处理机)1:处理机有数据块拷贝0:处理机无数据块拷贝注：注：Cache的一致性协议必须保证目录状态位与的一致性协议必须保证目录状态位与Cache数据块状态位一致。数据块状态位一致。P1 P2PN全映射目录协议保持全映射目录协议保持Cac
32、he一致性原理一致性原理C-数据数据X共享存储器共享存储器C 111 数据数据X共享存储器共享存储器C-1 数据数据X共享存储器共享存储器C1C2C3P1P2P3C1C2C3P1P2P3C1C2C3P1P2P3Read X Read X Read XWrite X从第二种状态到第三种状态（P3要写单元X时）：1)C3发现包含X单元的块有效，但不允许写。2)C3向包含X单元的存储器模块发写请求，并暂停P3的工作。3)该存储器模块发无效请求至C1、C2。4)C1、C2接到无效请求后，将对应块置无效状态，并发回答信号给存储器模块。5)存储器模块接到C1、C2的回答信号后，置重写位为“1”，清除指向C
33、1、C2的指针，发允许信号给C3。6)C3接到允许写信号，更新Cache状态，激活P3。全映射目录特点：全映射目录特点：1）不具有可扩展性。）不具有可扩展性。2）效率高，但开销与处理器数目的平方成正比（因为目录项数与处理器数）效率高，但开销与处理器数目的平方成正比（因为目录项数与处理器数目成正比，项的大小也与处理器数目成正比）。目成正比，项的大小也与处理器数目成正比）。2.有限目录有限目录C数据数据X共享存储器共享存储器C数据数据X共享存储器共享存储器C1C2C3P1P2P3C1C2C3P1P2P3Read X注：注：当目录项指针域均建立指针后，再有一处理机需要装入该数据，则目录项需要实当目录
34、项指针域均建立指针后，再有一处理机需要装入该数据，则目录项需要实施指针替换，指针替换过程称为驱逐。驱逐算法与施指针替换，指针替换过程称为驱逐。驱逐算法与Cache替换算法相似。替换算法相似。有限目录特点：有限目录特点：1）目录指针域数目固定，但指针域并不与处理机一一对应，任何一个指针域）目录指针域数目固定，但指针域并不与处理机一一对应，任何一个指针域可以为任何需要装如入该数据块的处理机建立指针，因此，具有可扩展性。可以为任何需要装如入该数据块的处理机建立指针，因此，具有可扩展性。3.链式目录链式目录 链式目录特点是既不限制共享数据块拷贝数目，又保持可扩展性。链式目录特点是既不限制共享数据块拷贝
35、数目，又保持可扩展性。实现方法：通过建立目录指针链跟踪共享数据拷贝。实现方法：通过建立目录指针链跟踪共享数据拷贝。1）单向链法）单向链法 2）双向链法）双向链法C数据数据X共享存储器共享存储器C1C2C3P1P2P3Read XCTXC数据数据X共享存储器共享存储器C1C2C3P1P2P3CTXX假设假设C1没有单元没有单元X的共享拷贝，这时处理机的共享拷贝，这时处理机P1要读单元要读单元X，则：，则：1）存储器送一份拷贝给）存储器送一份拷贝给C1，同时附加一个链结束指针（，同时附加一个链结束指针（CT），存储器保持），存储器保持一个指向一个指向C1的指针。的指针。尔后，当尔后，当P2要读单元
36、要读单元X时，时，2）存储器送一个拷贝给）存储器送一个拷贝给C2，同时送给，同时送给C2一个指向一个指向C1的指针，存储器保持一的指针，存储器保持一个指向个指向C2的指针。的指针。链式目录项目删除问题（假设删链式目录项目删除问题（假设删Ci目录）：目录）：1）沿链发消息，使得）沿链发消息，使得Ci+1的指针指向的指针指向Ci-1，把，把Ci从链中去掉。从链中去掉。2）使）使Ci及链中位于其后的所有及链中位于其后的所有Cache中的单元中的单元X无效。无效。链式目录特点：链式目录特点：1）可扩展性。）可扩展性。多处理机性能指标：多处理机性能指标：1）程序并行度）程序并行度 一个程序在各时间范围内
37、执行程序的处理机数目称为程序的并行度一个程序在各时间范围内执行程序的处理机数目称为程序的并行度（DOP）。）。DOP是在假设可对该程序提供无限数量的处理机和其它所需资源条件下是在假设可对该程序提供无限数量的处理机和其它所需资源条件下确定的，因此，确定的，因此，DOP表示程序本身并行化程度，由程序相关性决定。表示程序本身并行化程度，由程序相关性决定。DOP是一个离散时间函数，是一个离散时间函数，DOP的时间函数曲线的时间函数曲线DOP(t)称为程序并行性称为程序并行性分布图。平均并行性分布图。平均并行性A表示程序单位时间平均可使用的处理机数目，其表达表示程序单位时间平均可使用的处理机数目，其表达
38、式如下：式如下：A=1t2-t1DOP(t)dtt2t1若程序在时间段若程序在时间段ti使用使用ji台处理机，那么：台处理机，那么：A=(ti.ji)/(ti)mi=1mi=12）调和均值加速比）调和均值加速比 加速比是衡量并行系统优劣的一个重要指标，等于一个程序在一台处理加速比是衡量并行系统优劣的一个重要指标，等于一个程序在一台处理机上运行时间与在并行系统上运行时间的比值。包括多个加速比，调和均值机上运行时间与在并行系统上运行时间的比值。包括多个加速比，调和均值加速比是其中一种。加速比是其中一种。在多处理机上，在不同时间段，程序可以在多处理机上，在不同时间段，程序可以不同执行模式不同执行模式
39、运行，不同执行运行，不同执行模式对应程序中的标量计算或向量计算、顺序处理或并行处理。模式对应程序中的标量计算或向量计算、顺序处理或并行处理。假设程序以执行模式假设程序以执行模式i执行时指令执行速率为执行时指令执行速率为Ri，程序以模式，程序以模式i执行的概率执行的概率为为fi，那么，程序指令加权均值速率为：那么，程序指令加权均值速率为：R*=(Ri.fi)ni=1假设模式假设模式i每条指令平均执行时间每条指令平均执行时间Ti=1/Ri，则程序指令加权均值执行时间为：，则程序指令加权均值执行时间为：T*=(fi/Ri)ni=1假设程序在单台处理机上顺序执行时，每条指令的执行时间假设程序在单台处理
40、机上顺序执行时，每条指令的执行时间T1i=1，那么，那么，在资源不受限制的情况下，程序调和均值加速比：在资源不受限制的情况下，程序调和均值加速比：S=T1/T*=1/(fi/Ri)ni=1题：题：设设为一个计算机系统中为一个计算机系统中n台处理机可同时执行的程序代码的百分比，其台处理机可同时执行的程序代码的百分比，其余代码必须由单台处理机顺序执行。假设所有处理机的处理能力相同，每台余代码必须由单台处理机顺序执行。假设所有处理机的处理能力相同，每台处理机执行速率均为处理机执行速率均为xMIPS。1）试用参数）试用参数n、x推导出程序执行速率的表达式。推导出程序执行速率的表达式。2）假设）假设n=
41、16、x=4，要求程序执行速率达到，要求程序执行速率达到40MIPS，求，求值。值。解：解：1）设程序总工作量为）设程序总工作量为W=W1+Wn，其中，其中，W1是必须由一台处理机顺序是必须由一台处理机顺序执行的程序工作量，执行的程序工作量，Wn是可由是可由n台处理机并行执行的程序工作量。并行执台处理机并行执行的程序工作量。并行执行时每台处理机平均工作量行时每台处理机平均工作量Wn/n 程序执行总时间程序执行总时间T=T1+Tn，其中，其中，T1是是W1在一台处理机顺序执行时间，在一台处理机顺序执行时间，Tn是是Wn在在n台处理机并行执行时间。已知每台处理机执行速率为台处理机并行执行时间。已知每台处理机执行速率为xMIPS，故，故有：有：T1=W1/x Tn=(Wn/n)/x=Wn/nx T=T1+Tn=W1/x+Wn/nx=(nW1+Wn)/nx程序执行速率为：程序执行速率为：V=W/T=(W1+Wn)/(nW1+Wn)/nx=nx(W1+Wn)/(nW1+Wn)因为因为=Wn/(W1+Wn)，即，即Wn=W1/(1-)代入代入v表达式，可得表达式，可得v=nx/n+(1-n)2）将）将n=16，x=4，v=40MIPS代入代入v表达式，有：表达式，有：40=164/16+(1-16)可得：可得：=90%