第9章9.1程序并行性的分析

第9章并行组织1、计算机系统的分类一般采用1966年弗林（Flynn）根据指令流和数据流数量进行分类的方法。定义如下：指令流（InstructionStream）：是机器执行的指令序列；数据流（DataStream）：是由指令流调用的数据序列，包括输入数据和中间结果；多重性（Multiplicity）：在系统最受限制的元件上，同时处于同一执行阶段的指令或数据的最大可能个数。计算机系统结构的基本概念按照指令流和数据流的不同组织方式、多重性，将计算机系统分成四类：单指令流单数据流（SISD）计算机系统最常用的串行计算机，通常由一个处理器和一个存储器组成。每次执行一条指令，每次从存储器取（或存）一个数据单指令流多数据流（SIMD）计算机系统具有多个处理单元，所有处理单元执行同一条指令，多指令流单数据流（MISD）计算机系统有N个处理单元，按N条不同指令的要求对同一个数据进行不同的处理，多指令流多数据流（MIMD）计算机系统由多台处理器和多个存储器成，并有一个互连网络实现各处理器和各存储器之间的通信。2、如何提高计算机系统的运算速度从两个方面考虑提高计算机系统的运算速度：（1）微电子技术的发展和器件工艺的改进是提高集成度、提高工作频率的基础。计算机系统的发展又为微电子技术的发展带来更好的机遇；（2）CPU速度提高后，应注意内存存取速度的提高，通道速度的提高，采用DMA技术等，这些部件都与计算机系统的运算速度密切相关。3、开放系统遵循国际标准接口，使得计算机系统之间有“可移植性”和“互操作性”。可移植性是指将操作系统或应用软件放在不同厂家的各种不同型号的计算机上使用。互操作性是指不同厂家在不同平台上开发的多种应用软件通过网络共享数据和协同工作的能力。4、改进单机系统的系统结构的主要方法（1）CPU和输入输出设备并行工作，以减少CPU等待和空闲时间；（2）采用多个通用寄存器来暂存运算的中间结果，减少访问存储器次数；（3）采用多体交叉存储器和Cache，协调CPU和存储器之间的速度匹配；（4）操作重叠的流水线方式。5、计算机系统性能指标-----加速比最早由阿姆达尔(Amdahl)，因此系统加速比有时也称为阿姆达尔(Amdahl)定律。T0是指系统没有改进以前运行程序所用的时间；Te是指系统采用了改进措施以后运行程序所用的时间；阿姆达尔(Amdahl)定律这个定律就是一个公式：即Fe称为可改进比，是指系统中可改进部分占系统整体的百分数，因此0＜Fe＜1。（表示执行某个任务的总时间中改进部分的时间所占的百分比）Se称为部件加速比，是指改进部分采用了改进措施以后比没有采用改进措施以前性能提高的倍数。eeePSFFS/)1(1九、增加向量处理部件可提高计算机的运算速度。设计算机处理向量的速度比其通常的运算要快20倍。使用向量处理部件所花费的时间占总时间的百分比，称为可向量化百分比。①求出加速比S和可向量化百分比F之间的关系式。②当要得到加速比为4时的可向量化百分比F是多少？20/)1(1FFF192020F192020九、解：1）由Amdahl定律可知：S＝=2)由上式，S＝4，代入表达式4＝故F＝15/19=0.79=79%9.1.1并行性的概念包含两方面含义：（1）同时性（Simultaneity）：指两个或两个以上事件在同一时刻发生；（2）并发性（Concurrency）：指两个或两个以上事件在同一时间间隔内发生。并行性主要表现为时间重叠、资源重叠、资源重叠+时间重叠和资源共享。（1）时间重叠:即时间并行。多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得时间。（2）资源重叠:即空间并行。通过重复地设置硬件资源以大幅度提高计算机系统的性能，即以数量取胜的原则。（3）资源重叠+时间重叠：在计算机系统中同时运用时间并行和空间并行技术，这种方式在计算机系统中广泛应用，成为并行性主流技术。（4）资源共享：这是一种软件方法，多个用户按一定时间顺序轮流使用同一套硬件设备。计算机系统中的并行性有不同的等级。从处理数据的角度看，并行性等级从低到高可分为：字串位串：同时只对一个字的一位进行处理。这是最基本的串处理方式，不存在并行性。字串位并：同时对一个字的全部位进行处理，不同字之间是串行的。这里已开始出现并行性。字并位串：同时对许多字的一位进行处理。这种方式有较高的并行性。全并行：同时对许多字的全部位进行处理。这是最高一级的并行性。从执行程序的角度看，并行性等级从低到高可分为：指令内部并行：一条指令执行时各微操作之间的并行。指令级并行：并行执行两条或多条指令。任务级或过程级并行：并行执行两条以上过程或任务。（程序段）作业或程序级并行：并行执行两条以上作业或程序。紧耦合系统又称直接耦合系统，指计算机间物理连接的频带较高，一般是通过总线或高速开关实现计算机间的互连，可以共享主存。由于具有较高的信息传输率，因而可以快速并行处理作业或任务。松耦合系统又称间接耦合系统，一般是通过通道或通信线路实现计算机间的互连，可以共享外存设备（磁盘、磁带等）。机器之间的相互作用是在文件或数据集一级上进行。程序并行性的分析1.程序中数据相关性分析多处理机中的并行通常表现在程序级或任务级，能否将顺序执行的程序转换成语义等价的、可并行执行的程序，主要取决于程序的结构形式，特别是其中的数据相关性。由于在多处理机上并行运行的程序段是异步的，所以在程序段之间会出现下面的3种数据相关。为叙述简单起见，仅以赋值语句表示程序段P。(1)数据相关若P1左边变量出现在P2的右边变量集内时，则称P2数据相关于P1。例如：P1：A＝B+CP2：D＝A×B其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。显然，P1和P2不能并行执行。(2)数据反相关若P2的左边变量出现在P1的右边变量集内时，则称P1数据反相关于P2。例如：P1：A＝B×CP2：C＝E+DP1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。(3)数据输出相关若P1和P2的左边变量相同，则称P2数据输出相关于P1。例如：P1：A＝B+CP2：A＝D×E为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。2程序并行性检测程序并行性检测主要是判别程序中是否存在前述的各种数据相关。下面介绍由伯恩斯坦提出的一种自动判别数据相关的准则。每个程序段在执行过程中通常要使用输入和输出这两个分离的变量集。若用Ii表示Pi程序段中操作所要读取的存储单元集，用Oi表示要写入的存储单元集，则P1和P2两个程序段能并行执行的伯恩斯坦准则是：(1)I1∩O2＝Φ，即P1的输入变量集与P2的输出变量集不相交；(2)I2∩O1＝Φ，即P2的输入变量集与P1的输出变量集不相交；(3)O1∩O2＝Φ，即P1和P2的输出变量集不相交。【例1】假设两个处理机执行下面P1、P2程序，判断它们能否并行执行。P1：A＝B＋C＋DP2：E＝A*D[解]根据伯恩斯坦准则：I1={B，C，D}O1={A}I2={A，D}O2={E}所以有下式：I1∩O2={B，C，D}∩{E}=Φ；I2∩O1={A，D}∩{A}≠Φ不满足伯恩斯坦准则，出现数据相关，因此P1和P2不能并行执行。【例2】有两个处理机执行P1和P2程序，判断能否并行执行。P1：A=B*C*DP2：A＝E+F[解]根据伯恩斯坦准则，I1={B,C,D}O1={A}I2={E,F}O2={A}所以有下式：I1∩O2={B,C,D}∩{A}=Φ；I2∩O1={E,F}∩{A}=Φ；O1∩O2={A}∩{A}≠Φ不满足伯恩斯坦准则，出现数据相关，因此P1和P2不能并行执行。【例3】若有3个程序段P1，P2和P3，分别求3个矩阵算术表达式，判断3台处理机能否并行执行。P1：X＝(A＋B)×(A-B)P2：Y＝(C＋1)×（C＋D）－1P3：Z＝X+Y其中，A、B、C、D、X和Y均为N×N的矩阵。[解]:它们的输入、输出变量集分别为I1={A,B}I2={C,D}I3={X,Y}O1={X}O2={Y}O3={Z}由于I1∩O2＝Ф，I2∩O1＝Ф以及O1∩O2＝Ф，故P1和P2两个程序段可以并行执行；由于I3∩O1≠Ф和I3∩O2≠Ф，故P3程序段必须在P1和P2程序段执行完毕方可开始执行。【例4】3台处理机执行3个进程如下，请判断进程可否并行执行。P1：X＝A＋BP2：Y＝D×F＋AP3：Z＝C+E[解]根据伯恩斯坦准则可知I1＝{A,B}O1＝{X}I2＝{D,F,A}O2＝{Y}I3＝{C,E}O3＝{Z}对于P1与P2来说：I1∩O2＝{A,B}∩{Y}＝ΦI2∩O1＝{D,F,A}∩{X}＝ΦO1∩O2＝{X}∩{Y}＝Φ可知P1与P2可以并行执行。对于P3和P2来说：I2∩O3＝{D，F，A}∩{Z}＝ΦI3∩O2＝{C，E}∩{Y}＝ΦO3∩O2＝{Z}∩{Y}＝Φ可知P3与P2可以并行执行。对P3和P1来说：I1∩O3＝{A，B}∩{Z}＝ΦI3∩O1＝{C,E}∩{X}＝ΦO1∩O3＝{X]∩{Z}＝Φ可知P3和P1可以并行执行。故P1、P2、P3三个进程可以并7.4.2并行程序设计并行程序设计一般有两种形式，一种是隐式，主要由编译程序判别，将串行程序转换成并行程序。还有一种是显式，即选择并行程序设计语言，程序设计人员根据逻辑关系设计并行程序。下面简单介绍显式方法。并行程序设计语言通常是在高级语言基础上扩展的，常见的3种扩展并行语言是：(1)FORK-JOIN表示法；(2)块结构语言Cobegin-Coend表示法；(3)块结构语言Parbegin-Parend表示法。1FORK-JOIN表示法FORK语句是一个父进程派生出一个子进程并执行这个新进程，JOIN语句是等待FORK派生出来的新进程结束，具体过程如下：1.FORKA在地址A派生出一个新进程，当前进程继续执行。2.FORKA，J除了有FORKA的功能外，还在地址J将计数器内容加1。3.FORKA，J，N；除了有FORKA的功能外，在地址J将计数器内容置为N。4.JOINJ；表示将地址J处的计数器减1，当计数器的变为0时，将启动地址J＋1处的进程；否则释放执行JOIN语句的处理机。因此所有子进程以执行JOINJ作为终结，但是最后一个执行JOINJ语句的将是例外，此时进程将在J＋1处继续执行下去。2块结构语言Cobegin-Coend表示法与FORK-JOIN相比，块结构语言Cobegin-Coend描述简单明了，它是显式表达法。利用Cobegin-Coend将所有的可以并行的语句或进程前后扩起来，可以显示标明它们可并行执行。【例6】有进程S1，S2，S3，S4，Sn、Sn+1用Cobegin-Coend语言写出并行程序，其中S1，S2，S3，S4，Sn可并行执行。[解]beginSn+1；CobeginS1；S2；S3；S4；…；Sn；coendS；end【例5】嵌套并行进程优先图如图7.18所示，请用块结构语言Cobegin-Coend写出并行程序。[解]对应的并行程序如下：beginS0；CobeginS1；BeginS2；CobeginS3；S4；S5；coendS6；endS7；CoendS8；end3块结构Parbegin-Parend表示法块结构语言Parbegin-Parend与Cobegin-Coend一样，它也是显式表达法。利用Parbegin-Parend将所有的可以并行的语句或进程前后扩起来，可以显式标明它们可并行执行。【例6】有进程S0，S1，S2，S3，S4，……、S