第5章 并行处理技术

第5章并行处理技术第5章并行处理技术5.1计算机系统结构中并行性的发展5.2SIMD并行处理机5.3SIMD计算机的互连网络5.4网络特性5.5静态连接网络5.6动态连接网络习题5第5章并行处理技术5.1计算机系统结构中并行性的发展5.1.1并行性的基本概念1.并行性的定义所谓并行性(parallelism)是指在数值计算、数据处理、信息处理或是人工智能求解过程中可能存在某些可同时进行运算或操作的部分。开发并行性的目的是为了能进行并行处理，以提高计算机系统求解问题的效率。第5章并行处理技术例如单体多字存储器，每次访存时能同时读出多个字，以加快CPU的访存操作。再如超标量流水线，它通过在CPU中重复设置多条流水线，由多个相同的流水线子部件来同时完成对多条指令的解释。这些都是靠器件简单的重复来实现的。并行性有更广义的定义，如单处理机中指令的重叠解释方式和流水方式，操作系统中的多道程序分时并行，都是广义上的并行。第5章并行处理技术由此可以看出，并行性有二重含义，即同时性(simultaneity)和并发性(concurrency)。同时性是指多个事件在同一时刻发生，如SIMD阵列处理机中各PE的并行操作、超标量流水处理机中多条指令的并行解释。并发性是指多个事件在同一时间段内发生。如操作系统中的多道程序分时并行、指令的流水解释过程和运算操作的流水处理过程等。第5章并行处理技术2.并行处理的概念所谓并行处理是指一种相对于串行处理的信息处理方式，它着重开发计算过程中存在的并发事件。在进行并行处理时，其每次处理的规模大小可能是不同的，这可用并行性颗粒度(granularity)来表示。第5章并行处理技术颗粒度是衡量软件进程所含计算量的大小，最简单的方法是用程序段中指令的条数来表示。粒度的大小决定了并行处理的基本程序段是指令、循环，还是子任务、任务或作业。颗粒度的大小一般分为细粒度、中粒度和粗粒度三种，若程序段中指令条数小于500条，则称为细粒度，500条到2000条指令之间则称为中粒度，大于2000条则称为粗粒度。假定系统中共有n个处理器，颗粒度大小G还可用以下公式来表示：G=TWTC第5章并行处理技术式中，TW表示所有处理器工作负载(workload)的总和，即TW=∑twi，这里的工作负载实际上就是进行计算的时间；TC表示所有处理器的通信开销(communicationoverhead)的总和，即TC=∑tci，这里的通信开销实际上就是进行通信的时间。由G的表达式可见，当工作负载一定时，粒度愈细，表明通信开销愈大；反之，粒度愈粗，表明通信开销愈小。nni=1i=1第5章并行处理技术3.并行性的等级并行性有不同的等级，而且从不同角度来观察时，会有不同的划分方法。在程序执行过程中，根据并行进程中颗粒度的大小不同，通常可划分成以下五个等级：作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级，如图5.1所示。第5章并行处理技术图5.1程序执行过程中的不同层次的并行性层次1作业级（程序）层次2任务级（程序段或过程）层次3子任务级（例行程序，子程序）层次4循环和迭代层次5语句和指令第5章并行处理技术通常，并行处理是指在这些层次上的任何一级或多级上的并行性开发。层次越高的并行处理粒度就越粗，而低层上的并行处理粒度就较细。粗粒度并行性的开发主要采用MIMD方式，它开发的主要是功能并行性。而细粒度并行性的开发则主要采用SIMD方式，它开发的主要是数据并行性。第5章并行处理技术5.1.2实现并行性技术的途径计算机系统中实现并行性技术的途径多种多样，但就其基本思想而言，可归纳为以下三种途径：1.时间重叠（time-interleaving）时间重叠是指在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。第5章并行处理技术例如指令的流水解释过程，它通过把指令的解释过程划分成若干个相互联系的子过程，每一个子过程由专门的子部件来完成，利用时间重叠的方式解释不同的指令。采用时间重叠的方式基本上不需要增加硬件设备就可提高系统的速度和性能价格比。第5章并行处理技术2.资源重复（resource-replication）资源重复是指在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。随着硬件价格的降低，这种方式在单处理机中被广泛使用，而多处理机本身就是资源重复的结果。例如热备用系统、容错系统等，它们根据不同性能和成本的要求，利用资源重复的方式组织冗余部件，以提高系统的可靠性。第5章并行处理技术再例如阵列处理机，它通过设置多个处理单元，在同一控制器的控制下，各执行部件同时对分配给自己的数据完成同一种运算，利用资源重复的方式来提高整个系统的性能。第5章并行处理技术3.资源共享（resource-sharing）资源共享是指利用软件的方法让多个任务按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地也可以提高整个系统的性能。例如利用共享CPU、主存资源、大容量的磁盘存储器等，以降低系统价格，提高设备利用率，如多道程序、分时系统、计算机网络等。第5章并行处理技术5.1.3计算机系统结构中并行性的发展计算机系统结构中的并行性已从顺序标量计算机中的完全顺序处理，逐步向重叠、流水、多功能部件并行、多数据并行、多任务并行的并行处理方向发展，如图5.2所示。第5章并行处理技术图5.2从顺序处理到多数据、多任务并行处理的发展标量顺序的先行I/E重叠功能并行多功能部件流水线隐式向量显式向量存储器-寄存器-存储器型寄存器型SIMDMIMD相联处理机处理机阵列多计算机多处理机大规模并行处理机(MPP)第5章并行处理技术标量处理机只能进行指令的顺序解释，先行技术的出现，使I/E（指令读取/译码和执行）操作重叠起来，从而能实现功能并行性。支持功能并行性的方法有两种：一种是同时使用多个功能部件，另一种是在不同处理级别实施流水线技术。流水线技术对处理向量数据元素的重复相同的操作表现出强大的威力，从而产生了向量流水处理机，主要用于向量数据的并行处理。并行性的开发主要有两种途径，即隐式并行性与显式并行性。第5章并行处理技术隐式并行性的开发是指采用传统的C、Fortran、Lisp或Pascal等语言来编写源程序。顺序编码的源程序可用并行化编译器编译成并行目标代码，此编译器必须能检测并行性，并能分配机器资源。显式并行性的开发是指程序员直接利用并行程序设计语言C、Fortran、Lisp或Pascal等开发出并行语言源程序。并行性在用户程序中显式说明，这将大大减轻编译器的负担，而编译器只需根据程序并行性说明，将资源分配给目标机器。第5章并行处理技术向量处理机包括存储器-存储器工作方式的向量处理机和寄存器-寄存器工作方式的向量处理机，两者的不同之处在于源向量和结果向量是来自于存储器还是寄存器。1976年以后开发的向量处理机基本上都属于寄存器-寄存器工作方式的向量处理机，它通过在处理机中设置有较大容量的向量寄存器，让大多数操作都在向量寄存器间进行，从而提高了向量处理的速度。第5章并行处理技术并行处理机从整体上可分为两类，一类是用于数据并行处理的SIMD并行处理机，典型的SIMD并行处理机有相联处理机和阵列处理机，以及早期的大规模并行处理机；另一类是用于作业和任务级并行处理的MIMD并行处理机。MIMD并行处理机可分为两大类，即共享存储器多处理机和消息传递型多计算机。多处理机和多计算机之间的主要差别在于存储器共享和处理机间通信机制的不同。第5章并行处理技术5.2SIMD并行处理机本节将讨论以SIMD方式工作、采用资源重复的并行性措施的SIMD并行处理机，主要介绍SIMD并行处理机的结构与特点、阵列处理机ILLIAC-IV的处理单元阵列结构，以及适合于在阵列机上进行加工的并行算法。第5章并行处理技术5.2.1SIMD并行处理机的基本结构与特点SIMD并行处理机由于存储器采用的组成方式不同，有两种基本结构，即具有分布式存储器结构的SIMD并行处理机和具有集中式共享存储器结构的SIMD并行处理机。1.分布式存储器结构分布式存储器结构的SIMD并行处理机如图5.3所示。它包含重复设置的多个相同的处理单元PE(ProcessingElement)，每个PE都拥有自己独用的本地存储器LM(LocalMemory)。第5章并行处理技术图5.3分布式存储器结构的阵列处理机LMN-1LM0主机控制部件存储器（程序与数据）标量处理机大容量存储器阵列控制部件互连网络PE0LM1PE1PEN-1标量指令向量指令指令广播总线网络控制数据总线I/O用户···第5章并行处理技术计算机全部工作所用的程序和数据由一个与用户相连的主机提供，主机的工作与一般计算机完全相同，即控制I/O操作，从外设获得程序和待处理的数据，存入一个大容量存储器，将处理结果进行图示或其它形式输出。当启动处理机阵列工作时，主机就将程序和数据取入控制部件存储器中。先将要处理的数据通过数据总线存入各个PE所带的本地存储器LM，PE所处理的数据就从本地存储器中取得，并将结果写回本地存储器。第5章并行处理技术本地存储器中的内容根据需要通过数据总线与主机进行交换。控制部件存储器中的指令逐条地送入阵列控制部件译码，将其中的标量指令送入一个专设的标量处理机处理。而将向量指令用广播总线送到各PE中，使各PE同时执行同一条指令。从执行指令的过程看出，SIMD计算机每次只能执行一条指令，即仍然是串行的，但是从执行数据的过程来看，由于多个处理单元在同时执行一条指令时，产生了多个数据流，因此具有数据并行性。第5章并行处理技术各个PE通过互连网络ICN(InterconnectionNetwork)实现相互连接。控制部件对控制程序进行译码，其结果用以控制网络的寻径，以便完成如点对点通信、广播、聚集等功能。PE之间的同步是由控制部件的硬件实现的，即保证各PE在同一周期中执行同一条指令。并且可以通过对屏蔽位的设置，控制一个PE是否执行当前指令。现在出现的SIMD计算机，几乎都是基于分布式存储器结构的系统。各种系统之间的主要差别在于采用了不同的互连网络。第5章并行处理技术2.集中式共享存储器结构集中式共享存储器结构的SIMD并行处理机如图5.4所示。与图5.3相比，两者只是在存储器的结构上有明显的区别，其它部分基本上是相同的。共享存储器结构中将系统的存储器作集中管理，为了提高各PE访问存储器的速度，在组成上将存储器设计成多模块交叉存储器，如图中的SM0～SMK-1。这些存储器模块为各PE所共享，即任一个PE都可以访问任一个存储体。图5.4中的互连网络用来实现各PE与共享存储器SM(SharedMemory)的各个模块之间的通信，互连网络由阵列控制部件根据对控制指令的译码进行控制。第5章并行处理技术SMK-1SM0主机控制部件存储器（程序与数据）标量处理机大容量存储器阵列控制部件互连网络PE0SM1PE1PEN-1标量指令向量指令指令广播总线网络控制数据总线I/O用户······图5.4集中式共享存储器结构的阵列处理机第5章并行处理技术这种结构形式比较适合于用在处理单元数目不太大的情况下。当处理单元增加时，为了获得互不冲突的存储器分配就将耗费大量的系统资源，大大降低系统的性能价格比。BSP(BurroughsScientificProcessor)计算机采用了这种共享存储器结构，系统中的16个处理单元通过一个16×17的对准网络访问17个共享存储器模块。对准网络包含完全交叉开关以及用来实现数据从一个源PE广播至几个目的PE以及当几个源PE寻找一个目的PE时能分解冲突的硬件。根据存储器设计的理论可知，在PE与存储器数目互质的情况下，就有可能实现无冲突访问。第5章并行处理技术无论是哪一种结构的SIMD并行处理机，其基本结构都由用于数组和向量运算的处理单元阵列、用于标量处理的标量处理机、用于PE和互连网络控制的阵列控制部件、用于系统输入输出及操作系统管理的主机，以及用于PE之间、PE和存储