下载文档原格式
并行计算或称平行计算是相对于串行计算来说的；所谓并行计算可分为时间上的并行和空间上的并行。
吋间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。
并行计算科学中主要研究的是空间上的并行问题。
空间上的并行导致了两类并行机的产牛，按照Flynn的说法分为：单指令流多数据流(SIMD)和多指令流多数据流(MIMD)。
我们常用的串行机也叫做单指令流单数据流(SISD)。
MIMD类的机器又可分为以下常见的五类：并行向虽处理机(PVP),对称多处理机(SMP),大规模并行处理机(MPP),工作站机群(COW),分布式共享存储处理机(DSM)o单指令流多数据流:英文SIMD就是指Single Instruction Multiple Data,它用一个控制器來控制多个处理器，同时对一组数据(乂称“数据向量”)屮的每一个分别执行相同的操作来实现空间上的并行性——在微处理器屮实现的SIMD则是一个控制器控制多个平行的处理微元，例如Intel 的MMX或SSE,以及AMD的3D Now!技术。
多指令流多数据流：多指令流多数据流的英文是"Multiple Instruction Stream Multiple Data Stream1*,它使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性。
并行处理机pvp:并行向量处理机最大的特点是系统中的CPU是专门定制的向量处理器(VP)O系统述提供共享存储器以及与VP相连的高速交叉开关。
对称多处理机(SMP):对称多处理机(Symmetric Multiprocessor)最主要的特征是系统的对称性，即每个处理器可以以同等代价访问各个共亨存储器。
显然，SMP的访存模型一定是均匀访存模型(UMA)的。
kkkk优点是并行度很高，但是由于系统总线的带宽是有限的，故处理器的数冃是受限的。
大规模并行处理机(MPP):大规模并行处理机(Massively Parallel Processor)中，每一个节点由商品(微处理器)，局部存储器(分布式存储器)及网络接口电路构成；节点间以定制的高速网络互联。
深入了解计算机系统的并行计算原理计算机系统的并行计算原理计算机系统的并行计算原理是指通过同时执行多个任务或多个操作，以提高计算机系统的处理能力和效率。
并行计算可以分为硬件并行和软件并行两种形式，而它们都关键取决于计算机系统的结构和相应的原理。
一、硬件并行硬件并行是指通过多个处理器或处理器核心同时工作来实现并行计算。
常见的硬件并行结构有SIMD（单指令流多数据流）、MIMD（多指令流多数据流）和分布式计算系统等。
1. SIMD架构SIMD架构是指单指令流多数据流结构，即多个处理器核心执行同样的指令，但处理不同的数据。
这种结构适用于大规模的数据并行计算，如图像处理、视频编码等。
在SIMD架构中，一条指令同时处理多个数据元素，以提高计算效率。
2. MIMD架构MIMD架构是指多指令流多数据流结构，即多个处理器核心可以执行不同的指令，处理不同的数据。
这种结构适用于复杂任务和并发处理，如科学计算、数据库查询等。
在MIMD架构中，每个处理器核心都具有独立的指令和数据，可以根据需要分配任务和资源。
3. 分布式计算系统分布式计算系统是指由多个计算机节点组成的系统，在网络上相互连接和协作完成任务。
这种结构适用于大规模的计算和存储需求，如云计算、大数据处理等。
在分布式计算系统中，各个节点通过消息传递和数据交换实现并行计算。
二、软件并行软件并行是指通过编程和算法设计来实现并行计算，以充分利用计算机系统的性能。
常见的软件并行模型有进程并行和线程并行。
1. 进程并行进程并行是指将任务分解为多个独立的子任务，并通过多个进程来执行。
这种并行模型适用于分布式计算和多台计算机的场景，可以通过进程间的通信和同步来完成任务。
2. 线程并行线程并行是指将任务分解为多个独立的子任务，并通过多个线程来执行。
这种并行模型适用于共享内存计算机系统，可以通过线程间的协作和同步来完成任务。
三、并行计算的挑战与应用并行计算虽然可以提高计算机系统的处理能力，却也伴随着一些挑战和问题。
并行图计算模型与算法设计并行计算是一种用于处理大规模数据和复杂计算任务的计算模型。
在过去的几十年里，随着计算机硬件技术的不断发展，单个计算节点的计算能力已经开始达到瓶颈，因此人们开始寻找新的计算模型来提高计算效率。
并行图计算模型就是这样一种新的计算模型，它利用多个计算节点同时进行计算，从而实现了高效的并行计算。
一、并行图计算模型的基本原理并行图计算模型是基于图的并行计算模型。
其中，图是由节点和边组成的数据结构，节点表示计算任务，边表示计算任务之间的依赖关系。
在并行图计算模型中，任务被分布到多个计算节点上，每个计算节点处理自己负责的子图。
节点之间可以通过边来进行通信和数据交换。
并行图计算模型的基本原理是将整个计算过程划分为多个小的计算任务，并将这些任务分配给多个计算节点进行并行计算。
每个计算节点相互独立地计算自己负责的任务，并根据任务之间的依赖关系进行数据交换和通信。
通过并行计算，可以充分利用计算节点的计算能力，加速计算过程。
二、并行图计算模型的优势与传统的串行计算模型相比，并行图计算模型具有以下几个优势：1. 高效利用计算资源：通过将计算任务分配给多个计算节点并行执行，可以充分利用计算资源，提高计算效率。
2. 处理大规模数据：并行图计算模型适用于处理大规模数据和复杂计算任务的场景。
通过将计算任务分布到多个计算节点上，并行计算可以有效地减少计算时间。
3. 灵活的任务调度：并行图计算模型采用分布式任务调度的方式，可以根据计算节点的可用性和负载情况，动态调整任务的分配和调度，进一步提高计算效率。
4. 高容错性：由于并行图计算模型中的计算节点相互独立地执行任务，当某个节点出现故障时，可以通过将任务重新分配给其他节点来实现容错。
这使得并行图计算模型具有很高的容错性。
三、并行图计算算法设计并行图计算算法设计是指设计并行图计算模型中的具体算法，以实现高效的并行计算。
在设计并行图计算算法时，需要考虑以下几个方面：1. 任务划分：将整个计算任务划分为多个小的计算任务，并将这些任务分配给不同的计算节点进行并行计算。
并⾏计算机系统结构
并⾏计算机系统结构
1. 并⾏计算机结构模型
1. 单指令流多数据流机SIMD(Single Instruction Multiple Data)；
2. 并⾏向量计算机PVP(Parallel Vector Processor)；
3. 对称多处理机SMP(Symmetric MultiProcessor)；
4. ⼤规模并⾏处理机MPP(Massively Parallel Processor)；
5. 分布式共享存储DSM(Distributed Shared Memory)
6. 多处理机和⼯作站机群COW(Cluster Of Workstation)（现在常称之为机群）。
1. 并⾏计算机访存模型
1. UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。
2. NUMA(Nonuniform Memory Access)模型是⾮均匀存储访问模型的简称。
3. COMA(Cache-Only Memory Access)模型是全⾼速缓存存储访问的简称。
4. CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是⾼速缓存⼀致性⾮均匀存储访问模型的简称。
5. NORMA（No-Remote Memory Access）模型是⾮远程存储访问模型的简称。
第一章绪论什么是并行计算机答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信和协作，能快速高效求解大型的复杂的问题。
简述Flynn分类法：答：根据指令流和数据流的多重性将计算机分为：1）单指令单数据流SISD2）单指令多数据流SIMD3）多指令单数据流MISD4）多指令多数据流MIMD简述当代的并行机系统答：当代并行机系统主要有：1）并行向量机（PVP）2）对称多处理机（SMP）3）大规模并行处理机（MPP）4）分布式共享存储（DSM）处理机5）工作站机群（COW）为什么需要并行计算机答：1）加快计算速度2）提高计算精度3）满足快速时效要求4）进行无法替代的模拟计算简述处理器并行度的发展趋势答：1）位级并行2）指令级并行3）线程级并行简述SIMD阵列机的特点答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。
2）所有的处理单元（PE）必须是同步的。
21m 3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。
4）阵列机是一种专用的计算机，用于处理一些专门的问题。
简述多计算机系统的演变答：分为三个阶段：1）1983-1987年为第一代，代表机器有：Ipsc/1、Ameteks/14等。
2）1988-1992年为第二代，代表机器有：Paragon 、Intel delta 等。
3）1993-1997年为第三代，代表机器有：MIT 的J-machine 。
简述并行计算机的访存模型答：1）均匀存储访问模型（UMA ）2）非均匀存储访问模型（NUMA ）3）全高速缓存存储访问模型（COMA ）4）高速缓存一致性非均匀访问模型（CC-NUMA ）简述均匀存储访问模型的特点答：1）物理存储器被所有处理器均匀共享。
2）所有处理器访问任何存储字的时间相同。
3）每台处理器可带私有高速缓存。
4）外围设备也可以一定的形式共享。
简述非均匀存储访问模型的特点答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。
并行计算机体系结构讲义I、引入：一、计算机系统结构的分类（从计算机系统结构的并行性能出发）弗林（Flynn）分类法1966年；而数据流是指令执行过程中的一串数据。
）的不同组织方式，把计算机系统的结构分为以下4类：1. 单指令流，单数据流(SISD)——这就是一个单处理器。
2.单指令流，多数据流(SIMD)——同一指令由多个处理器执行，这些处理器使用不同数据流，有各自的数据内存，但共享一个指令内存和控制处理器（负责存取和发送指令）。
处理器通常是专用的，不要求通用性。
3. 多指令流，单数据流(MISD)——4. 多指令流，多数据流(MIMD)——每个处理器存取自己的指令，操作自己的数据。
处理器通常就采用普通的微处理器。
这是一个粗略的模型分类，许多机器是这些类型的混合体。
SISD是传统的顺序处理计算机。
SIMD以阵列处理机为代表。
MISD在实际中代表何种计算机，存在着不同的看法。
MIMD 的代表是多处理机。
二、并行性技术一个理想的计算机系统结构应在处理速度、存储容量和I/O吞吐能力三者之间取得平衡。
而并行性技术是实现这种平衡的主要手段。
并行性技术包括时间并行、空间并行、时间并行+空间并行、资源共享4种方法。
也就是说, 计算机系统中提高并行性的措施就其基本思想而言，可归纳如下4条途径：(1) 时间重叠：即多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转时间而赢得速度。
因此时间重叠可称为时间并行技术。
(2) 资源重复：在并行性概念中引入空间因素，以数量取胜的原则，通过重复设置硬件资源，大幅度提高计算机系统的性能。
随着硬件价格的降低，这种方式在单处理机中广泛使用，而多处理机本身就是实施“资源重复”原理的结果。
因此资源重复可称为空间并行技术。
(3) 时间重叠+资源重复：在计算机系统中同时运用时间并行和空间并行技术，这种方式在计算机系统中得到广泛使用，成为并行性主流技术。
(4) 资源共享：这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。
例如多道程序、分时系统就是遵循“资源共享”原理而产生的。
资源共享既降低了成本，又提高了计算机设备的利用率。
II、讲授内容：一、并行性的概念：并行性，是指计算机系统具有可以同时进行运算或操作的特性，它包括同时性与并发性两种含义。
同时性——两个或两个以上的事件在同一时刻发生。
并发性——两个或两个以上的事件在同一时间间隔发生。
计算机系统中的并行性有不同的等级。
从处理数据的角度看，并行性等级从低到高可分为：(1)字串位串：同时只对一个字的一位进行处理。
这是最基本的串行处理方式，不存在并行性。
(2)字串位并：同时对一个字的全部位进行处理，不同字之间是串行的。
这里已开始出现并行性。
(3)字并位串：同时对许多字的同一位进行处理。
这种方式有较高的并行性。
(4)全并行：同时对许多字的全部位进行处理。
这是最高一级的并行。
从执行程序的角度看，并行性等级从低到高可分为：(1)指令内部并行：一条指令执行时各微操作之间的并行。
(2)指令级并行：并行执行两条或多条指令。
(3)任务级或过程级并行：并行执行两个以上过程或任务(程序段)。
(4)作业或程序级并行：并行执行两个以上作业或程序。
在单处理机系统中，这种并行性升到某一级别后(如任务级或作业级并行)，则需要通过软件(如操作系统中的进程管理、作业管理)来实现。
而在多处理机系统中，由于已有了完成各个任务或作业的处理机，其并行性是由硬件实现的。
在一个计算机系统中，可以采取多种并行性措施。
既可以有数据处理方面的并行性，又可以有执行程序方面的并行性。
当并行性提高到一定级别时，则称之为进入并行处理领域。
并行处理着重挖掘计算过程中的并行事件，使并行性达到较高的级别。
因此，并行处理是系统结构、硬件、软件、算法、语言等多方面综合研究的领域。
二、单机系统中并行性的发展在发展高性能单处理机过程中，起着主导作用的是时间重叠原理。
实现时间重叠的物质基础是“部件功能专用化”，即把一件工作按功能分割为若干相互联系的部分，把每一部分指定给专门的部件完成；然后按时间重叠原理把各部分执行过程在时间上重叠起来，使所有部件依次分工完成一组同样的工作。
例如解释指令的5个子过程分别需要5个专用部件，即取指令部件(IF)、指令译码部件(ID)、指令执行部件(EX)、访问存储器部件(M)、写回结果部件(WB)。
将它们按流水方式连接起来，就满足时间重叠原理，从而使得处理机内部同时处理多条指令，提高了处理机的速度。
显然，时间重叠技术开发了计算机系统中的指令级并行。
在单处理机中，资源重复原理的运用也已经十分普遍。
例如不论是非流水线处理机，还是流水线处理机，多体存储器和多操作部件都是成功应用的结构形式。
在多操作部件处理机中，通用部件被分解成若干个专用操作部件，如加法部件、乘法部件、除法部件、逻辑运算部件等。
一条指令所需的操作部件只要空闲，就可以开始执行这条指令，这就是指令级并行。
在单处理机中，资源共享的概念实质上是用单处理机模拟多处理机的功能，形成所谓虚拟机的概念。
例如分时系统，在多终端情况下，每个终端上的用户感到好像自己有一台处理机一样。
三、多机系统中并行性的发展多机系统也遵循时间重叠、资源重复、资源共享原理，向着三种不同的多处理机方向发展。
但在采取的技术措施上与单处理机系统有些差别。
为了反映多机系统各机器之间物理连接的紧密程度与交互作用能力的强弱，使用了耦合度这样一个术语。
多机系统的耦合度，分为紧耦合系统和松耦合系统两大类。
紧耦合系统又称直接耦合系统，指计算机间物理连接的频带较高，一般是通过总线或高速开关实现计算机间的互连，可以共亨主存。
由于具有较高的信息传输率，因而可以快速并行处理作业或任务。
松耦合系统又称间接耦合系统，一般是通过通道或通信线路实现计算机间的互连，可以共享外存设备(磁盘、磁带等)。
机器之间的相互作用是在文件或数据集一级上进行。
松耦合系统表现为两种形式：一种是多台计算机和共享的外存设备连接，不同机器之间实现功能上的分工(功能专用化)，机器处理的结果以文件或数据集的形式送到共享外存设备，供其他机器继续处理。
另一种是计算机网，通过通信线路连接，以求得更大范围的资源共享。
多处理机中为了实现时间重叠，将处理功能分散给各专用处理机去完成，即功能专用化，各处理机之间则按时间重叠原理工作。
许多主要功能，如数组运算、高级语言编译、数据库管理等，也逐渐分离出来，交由专用处理机完成，机间的耦合程度逐渐加强，从而发展成为异构型多处理机系统。
通过设置多台相同类型的计算机而构成的容错系统，可使系统工作的可靠性在处理机一级得到提高。
各种不同的容错多处理机系统方案计算对计算机间互连网络的要求是不同的，但正确性、可靠性是首要要求。
如果提高对互连网络的要求，使其具有一定的灵活性、可靠性和可重构性，则可将其发展成一种可重构系统。
在这种系统中，平时几台计算机都正常工作，像通常的多处理机系统一样。
但一旦发生故障，就使系统重新组织，降低档次继续运行，直到排除故障为止。
随着硬件价格的降低，人们追求的目标是通过多处理机的并行处理来提高整个系统的速度。
为此，对机间互连网络的性能提出了更高要求。
高带宽、低延迟、低开销的机间互连网络，是高效实现程序段或任务一级并行处理的前提条件。
为了使并行处理的任务能在处理机之间随机地进行调度，就必须使各处理机具有同等的功能，从而成为同构型多处理机系统四、并行计算机系统1、多处理机的一般模型多处理机的系统结构由若干台独立的计算机组成，每台计算机能够独立执行自己的程序。
Flynn称这种结构为MIMD(多指令流多数据流)结构。
在多处理机系统中，处理机与处理机之间通过互连网络进行连接，从而实现程序之间的数据交换和同步。
上图给出了多处理机系统的一般模型。
系统中有n个处理机(P1到Pn)，它们通过一个处理机存储器互连网络(PMIN)连接到一个共享的主存储器上，这些处理机之间通过共享主存储器进行通信。
处理机间还可以有一个处理机处理机互连网络(PPIN)，PPIN通常用来从一台处理机向处理机发送中断信号，以达到进程同步的目的。
此外，这些处理机还通过处理机-I/O互连网络(PIOIN)同各I/O设备连接。
有时为了使系统简单，可以把全部I/O设备连接在一台I/O处理机或少数几台处理机上。
为了减少各处理机在访问主存储器时发生的冲突，把主存分为m个模块交叉工作，而且常使m大于n。
此外，还可以为每台处理机配备私有的存储器(PM)，在其中存放常用的操作系统和暂存受到阻塞或被中断了的进程，这样做还可以减少互连网络PMIN上的通信量。
但一个处理机的PM存储器不能为其他处理机所直接访问，因而，如要把一个受到阻塞的进程转给其他处理机去执行时，要花相当大的时间开销。
增加了处理机的私有存储器，尽管可以减少主存冲突和PMIN网络的通信量负担，但当整个系统中处理机数量比较多时，系统的吞吐量仍会因主存冲突和PMIN开关时间的限制受到很大影响。
为此，可以在每个处理机同PMIN 间设置Cache(CM)，以进一步减少访问主存的次数。
但有了Cache以后，又要产生系统中多个Cache之间以及Cache同主存间的数据一致性问题，这个问题孙彭敏讲解。
在共享存储器的多处理机中，处理机和存储器间的互连网络中信息传送非常频繁。
当互连的处理机数较多时，要求这个互连网络的频带很宽，所以频带宽度往往限制了处理机数目的增加，因而对多处理机系统，希望能设计成具有好的可缩放性。
在一个具有可缩放性的多处理机系统中，当增加其处理机结点数目时，整个多处理机系统的处理能力随结点数线性地增长，以满足不同用户的需要。
2、多处理机分类多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。
它有多种分类方法。
按多处理机各机器之间物理连接的紧密程度与交互作用能力的强弱来分，多处理机分为紧耦合系统和松耦合系统两大类。
按处理机的结构是否相同来分，如果每个处理机是同类型的，且完成同样的功能，我们称为同构型多处理机系统。
如果多处理机是由多个不同类型，且担负不同功能的处理机组成，我们称为异构型多处理机系统。
按多处理机系统的组成结构来分，现有的MIMD计算机分为如下五种类型：并行向量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、分布共享存储器多处理机(DSM)、工作站机群(COW)，如图所示。
图 (a)是并行向量处理机，它是由少数几台巨型向量处理机采用共享存储器方式互连而成，第六章中提到的CRAY X-MP等属于这种类型。
在这种类型中，处理机数目不可能很多。
图 (b)是对称多处理机，它由一组处理机和一组存储器模块经过互连网络连接而成。
有多个处理机且是对称的，每台处理机的能力都完全相同。
