第七章 多处理机

7.1 多处理机的概念、问题和硬件结构

7.1.2 多处理机的硬件结构

3.存储器的组织

多处理机主存一般都采用由多个模块构成的并行存储器,由m个存储器模块构成的并行存储器,存储单元的地址是按交叉方式编址的。这种地址交叉编址主要有低位交叉和高位交叉两种。

m个模块的低位交叉编址方式是由主存物理地址的低log2m位代码选择模块,高log2n位代码选择模块内的单元。整个存储器存储单元按物理地址顺序轮流地分布在各个存储器模块中。模块颞部顺序单元的物理地址不连续,其步距为m。

m个模块的高位交叉编址方式是由主存物理地址的高log2m位选择模块,低log2n位代码选择模块内的单元。整个存储器存储器单元按物理地址顺序从模块0到模块m-1依次连续分布,且模块内部顺序单元的物理地址也是连续的。

在流水、向量或阵列处理机中,主存一般不采用高位交叉编址。

在多处理机中,当各个处理机上的活跃的进程是共享同一集中连续物理地址空间中的数据时,主存采用低位交叉编址是有利的。当他们只是较少或基本不共享集中的数据时,主存采用低位交叉编址反倒会引起不希望的访存冲突,不如采用高位交叉编址好。

在高位交叉编址时,可以在给定的寄存器模块中为某个进程集中一定数量的页面,一边有效地减少访存冲突。这时将放置处理机i执行进程要用到的绝大多数页面的那么存储器模块i称为处理机i 的本地存储器(Home Memory)

当每个处理机上运行的进程都将其所用的活跃页面放在自己的本地存储器中时,各处理机也就不会发生访存冲突。

当每个处理机设有自己的专用Cache时,主存采用低位交叉编址会使Cache中每块信息分散到不同的多个存储器模块之中,这样,Cache在传送一个信息块的过程中,需频繁地经互联网络去转接,严重减低信息块的传输效率。因此在多处理中,长采用一种二维的并行存储器构形。

7.2 紧耦合多处理机多Cache的一致性问题

7.2.1 多Cache的一致性问题的产生

1.当主存中一个信息块在多个Cache中都有时,会出现多个Cache之间的相应信息块的内容不一致。

2.在多处理机上,为提高系统的效率,有时允许进程转移,将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行,均衡系统负载,这样做也会造成Cache与主存见的不一致。

3.当系统发生绕过Cache的I/O操作时,也会导致多个Cache块之间与Cahce与主存对应块的内容不一致。

7.2.2 多个Cache的一致性问题的解决办法

1.解决进程迁移引起的多Cache不一致性

可以通过禁止进程迁移的办法予以解决,也可以在进程被挂起时,靠硬件办法将Cache中改进程改写过的信息块强制写回主存相应位置的办法解决。

2.以硬件为基础实现Cache的一致性

1.监视Cache协议(Snoopy Protocol)法

即各个处理机中的Cache控制器随时都在监视其他Cahce的行动。对于采用总线互连共享主存的多处理机,可利用总线的播送来实现。

2.写作废法

当某个处理机首次将数据写入自身Cache中某一信息块的同时,也将其写入主存,并且利用这个写主存操作信号通知总线上所有其他处理机的Cache,将总线上给出的地址与各自的Cache目录中的信息块地址比较,存在副本,将副本作废,以便处理机访问信息块时,按缺块处理,到主存中去调。

3.播写法(写更新法)

通知总线上所有其他处理机的Cache控制器,如有次副本的,都进行更新。


 

监视Cache协议法实现简单,但只适用于总线互连的多处理机,而且不管是写作废还是写更新,都占用总线不少时间。

当多处理机的机数很多,或不采用总线式互连时,监视Cache协议法就不适用了。

对于采用多级网络互连的多处理机中,主要采用目录表法,建立一个目录表,目录表中的每一项中记录一个数据块的使用情况,包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否存在。还设置一个标志位记录是否已有Cache想这个信息块写入过。有了这个目录表之后,一个处理机在写入自身Cache的同时,只需有选择地通知所有其他存有此数据库的Cache将副本作废或更新即可。

目录表的具体做法又分成三种:

1.全映像目录表

表中每项有N个标志位对应于多个处理机全部N台处理机的Cache,系统中全部Cache均可同时存放同一个信息库的副本,但是这样的目录表庞大、硬件及控制都很复杂。

2.有限目录表法

表中每项的标志位少于N个,限制了一个数据块在各Cache中能存放的副本数目。

以上两种做法都是集中地存入在共享主存之中,因此需要由主存向各处理机广播

3.链式目录表法

将目录表分散存放在各个Cache中,主存只存有一个指针,指向一台处理机。要查找所有放同一个信息块的Cache时,先找到一台处理机的Cache,然后逐台查找,直到找到目录表中的指针为空。

3.以软件为基础实现多Cache的一致性

靠软件来限制,不把一些公用的可写数据存入Cache中。

优点是可以降低硬件的复杂性,降低对互连网络通信量的要求,因而性能价格比可以较高,比较适用于处理机数多的多处理机。

7.3 多处理机的并行性和性能

多处理机并行性既存在与指令内部,也存在于指令外部。

7.3.1 并行算法

1.并行算法的定义和分类

算法规定了求解某一特性问题时 的有穷的运算处理步骤。

并行算法:可同时执行的多个进程的集合,各进程可相互作用、协调和并发操作。

按运算基本对象,并行算法可分为数值型和非数值型。

按并行进程间的操作顺序不同,并行算法又分为同步型、异步型和独立型

同步型算法:并行的各进程由于相关,必须顺次等待。

异步型算法:并行的各进程执行相互独立,不会因相关而等待。根据执行情况决定终止还是继续。

独立型算法:并行的各进程完全独立,互不通信。

根据任务粒度分为:细粒度、中粒度和粗粒度。

细粒度:并行算法一般指向量或循环级的并行。

中粒度:较大的循环级并行,并确保这种病性的好处可以补偿因并行带来的额外开销。

粗粒度:子任务级并行。

用同构性来表示并行的各进程间的相似度,一般多程序多数据流的多处理机上运行的进场之间是异构性,而在单程序多数据流的多处理机上运行的多个并行进程则是同构性的。

2.多处理机并行算法的研究思路

将大的程序分解成可由足够多的并行处理的过程。每个过程被看成一个结点,将过程之间的关联关系用结点组成的树来描述。这样,程序内各过程之间的关系就可以被看成一种算术表达式中各项之间的运算,表达式中的每一项可看成是一个程序段的运行结果。

评价并行算法的性能效率:

P表示可并行处理的处理机机数。

Tp表示P台处理机运算的级数(树高)。

用多处理机的加速比Sp表示单处理机顺序运算的级数T1P台处理机并行运算的级数Tp之比。

Ep表示P台处理机的设备利用率。

可见Sp≥1时,会使Ep≤1,即运算的加速总是伴随着效率而下降。

算法必须适应具体的计算机结构。

结论:把运算过程表示成树形结构,提高运算的并行性就是如何对树进行变换,以减少运算的级数,即降低树高Tp。树形结构可以用交换律、结合律、分配律来交换树的形状。由于多处理机主要是为提高速度,因此,好的并行算法应竟可能增大树中每一层的结点数,即增大树的广度,使各处理机可宾星的过程书尽可能增大,以降低树的高度,既降低多处理机运算的技术,当最大限度的降低了数的高度后,就应再缩小树的广度,使之在达到一定的加速比Sp之后如果减少机数P来减少多处理机效率的降低。

7.3.2 程序并行性的分析

任务间并行很大程度上取决于程序的结构。在多处理机上,各处理机的程序段并行必然是异步的,因此会出现3中相关:

1.数据相关

2.数据反相关

3.数据输出相关

结论: 两个程序段之间若有先写后读的数据相关,不能并行,只在特殊情况下可以交换串行;若有先读后写的数据反相关,可以并行执行,但必须保证其写入共享主存时的先读后写次序,不能交换串行;若有写-写的数据输出相关,可以并行执行,但同样需要保证其写入的先后次序,不能交换串行;若同时有先写后读和先读后写两种相关,以交换数据为目的时,必须并行执行,且读、写要完全同步,不许顺序串行和交换串行,若没有任何相关或仅有源数据相同时,可以并行、顺序串行和交换串行。

7.3.3 并行语言与并行编译

并行程序设计语言的基本要求:

能使程序员在其程序中灵活、封边地表示出各类并行性,能在各种并行/向量计算机系统中搞笑的实现

包含并行性的程序在多处理上运行时,需要有相应的控制机构来管理,其中包括并行任务的派生和汇合。

派生:一个任务在执行的同时,派生出可与它并行执行的其他一个或多个任务,分配给不同的处理机来完成。等它们全部完成后,再汇合起来进行后续的单任务或新的并行任务。如果是新的并行任务,就又要进行派生,然后汇合。直至整个程序结束。、

7.3.4 多处理机的性能

使用多处理机的主要目的是用多个处理机并发执行多个任务来提高解题速度。

E/C值:程序用于有效计算的执行时间E与处理机间的通信等辅助开销时间C的比值

在某一特定系统上,程序的执行时间与通信等额外开销时间的比值越大,对计算过程越有利,此时采用细粒度是可以提高处理的并行度的。但不能单纯靠增大处理机技术来制造出高性能的多处理机,就多处理机而言,结构设计者应考虑如何设计出一个使E/C值尽可能高,价格合理,处理机机数多,又能高效使用的多处理机。

机数多不能带来性能的线性提高。算法设计要考虑在特定多处理机上如果将一个具体问题进行任务分割,选择什么样的粒度,让有效的并行计算和通信等额外开销达到平衡,以实现高效利用系统资源的目的。

7.4 多处理机的操作系统

多处理机操作系统有3类,主从型(Master——Slave Configuration)、各自独立型(Separate Supervisor)以及浮动型(Floating Supervisor)

7.4.1 主从型操作系统

管理程序只在一个指定的处理机上运行,该主处理机可以使专门执行管理功能的控制处理机。也可以是与其他从处理机相同的通用机,除执行管理功能外,也能做其他方面的应用。由于主处理机是负责管理系统中所有其他从处理机的状态和工作分配,只把从处理机看成是一个可调度的资源,实现对整个系统的集中控制,因此,也称为集中控制或专门控制方式。从处理机是通过访管指令或自陷软中断来请求主处理机服务的。

优点:

结构比较简单,整个管理程序只在一个处理机上运行。一般都不必是可再入的,猪油一个处理机访问执行表,不存在系统管理控制表格的访问冲突和阻塞,简化了管理控制的实现。最大限度的利用已有单处理机多道程序分时操作系统的成果。只需要对其稍加扩充即可。实现简单、经济、方便。

缺点:

对主处理机的可靠性要求高,一旦发生故障,很容易使整个系统瘫痪,这时需要操作员干预。系统不够灵活,要求主处理机必须能快速执行其管理功能,提前等待请求,以便及时为从处理机分配任务。负荷过重,会影响整个系统的性能。特别是当大部分任务都很短时,由于频繁地要求主处理机完成大量的管理操作,系统效率会显著降低。

适用场合

适用于工作负荷固定,从处理剂能力明显低于主处理机,或由功能相差很大的处理机组成的异构型多处理机。

7.4.2 各自独立型操作系统

各自独立型操作系统是将控制功能分散给多台处理机,共同完成对整个系统的控制工作。

优点:

适应分布处理的模块化结构特点,减少对大型控制专用处理机的需求;某个处理机发生故障,不会引起整个系统瘫痪,有较高的可靠性,每台处理机都有其专用控制表格,使访问系统表格的冲突较少,也不会有许多公用的执行表,同时控制进程和用户进程一起调度,能取得较高的系统效率。

缺点:

实现复杂,尽管每台处理机都有自己的专用控制表格,但仍有一些共享表格,会增加共享表格的访问冲突,导致进程调度的复杂性和开销的加大。某台处理机一旦发生故障,要像恢复和重新执行未完成的工作比较困难,每台处理机都有自己专用的输入/输出设备和文件,使整个系统的输入/输出结构变换需要凑走远干预,各处理机的负载平衡比较困难,各台处理机需要局部存储器存放管理程序副本,降低存储器利用率。

适用场合

松耦合多处理机

7.4.3 浮动型操作系统

浮动型操作系统是介于主从型和各自独立型操作系统之间的每一种折中方式,其管理程序可以再处理机之间浮动。在一段较长的时间里指定某一台处理机为控制处理机。但是具体指定到哪一台处理机以及担任多长时间的控制处理都不固定。主控制程序可以从一台处理机转移到另一台处理机,其他处理机中可以同时有多台处理机执行同一个管理服务子程序。

多数管理都是可再入的,由于同一时间里可以有多台处理机处于管态,有可能发生访问表格和数据集冲突,一般采用互斥访问方法解决。服务请求冲突可通过静态分配或动态控制高优先级方法来解决。

优点:

各类资源可以较好地做到符合平衡,一些I/O中断等非专门的操作可交由在某段时间最闲的处理机去执行,在硬件结构和可靠性上具有分布控制的优点,而在操作系统的复杂性和经济型上则接近于主从型,如果操作系统设计得好,将不受处理机机数多少的影响,因而具有很高的灵活性。

缺点:

设计困难

适用场合:

紧耦合处理机,特别是公共贮存和I/O子系统的多个相同处理剂组成的同构型多处理机。

7.5 多处理机的发展

发展出分布式共享存储器多处理机、对称多处理机、多向量多处理机、并行向量处理机、大规模并行处理机和机群系统。

7.5.1 分布式共享存储器多处理机

采用分布式共享存储器,易于扩充系统规模,但,如果各处理机只经消息传递,不直接访问本地存储器,将使编程困难,通信开销增加,为此,目前多采用共享虚拟存储器的方法,即分布贡献存储器的方法来解决。

共享虚拟存储器:物理上分散的多台处理机所拥有的本地存储器在逻辑上统一编址,形成一个统一的虚拟地址空间以实现存储器的共享。

分布式共享存储器的多处理机采用Cache目录表来支持Cache的一致性。

7.5.2 对称多处理机

以大量高兴嫩微处理器芯片经互连网络互连,共享主存的多处理机系统已有很大的发展。

可提供每秒数百亿次的浮点运算,数百兆字节的内存和超过10GB/s的访存流量,I/O流量高,分时共享能力、容错能力均很强,用于频繁进行的中小规模的科学与工程计算,事务管理和数据库管理。

7.5.3 多向量处理机

配置多台处理机,多个向量流水部件和标量部件,它们共享主存

7.5.4 并行向量处理机

由若干数目不等的强功能的专用向量处理器经高带宽的纵横交叉开关互连到若干共享的存储器模块。每个处理机系统超过1GFLOPS,这类机器一般不适用Cache,而采用大量向量寄存器和指令缓冲存储器。

7.5.5 大规模并行处理

7.5.6机群系统

与本文相关的文章
版权声明
转载保留版权: 大D综合研究院 | 《《计算机系统结构》读书笔记(十九)》
本文链接地址:https://www.dadclab.com/archives/3246.jiecao
转载须知:如果您需要转载本文,请将版权信息,版权授权方式,以及本文的链接地址注明,谢谢合作。
本文被贴上了: , , , , , 标签