第7章并行处理技术与 SMD阵列机 内容提要 本章首先介绍并行处理技术的基本概念、性能及并行 性开发策略,然后讲述SIMD阵列机的基本组成原理、类 型、特点、常用算法和几种常见SⅠMD阵列机的结构。重 点是SIMD阵列机的基本组成原理、常用算法和结构;难 点是阵列机的基本组成原理与常用算法
第7章 并行处理技术与 SIMD阵列机 • 内容提要: 本章首先介绍并行处理技术的基本概念、性能及并行 性开发策略，然后讲述SIMD阵列机的基本组成原理、类 型、特点、常用算法和几种常见SIMD阵列机的结构。重 点是SIMD阵列机的基本组成原理、常用算法和结构；难 点是阵列机的基本组成原理与常用算法
第7章并行处理技术与 S|MD阵列机 7.1并行处理技术 7.2SIMD阵列机 7.3典型SIMD阵列机举例
第7章 并行处理技术与 SIMD阵列机 7.1 并行处理技术 7.2 SIMD阵列机 7.3 典型SIMD阵列机举例
7.1并行处理技术 7.1.1并行处理的基本概念 7.1.2并行性的开发途径
7.1 并行处理技术 7.1.1 并行处理的基本概念 7.1.2 并行性的开发途径
7.1.1并行处理的基本概念 1并行性的基本概念 并行性( Parallelism)也称为同时性或并发性,是指在数值计算 数据处理、信息处理或人工智能求解的过程中存在许多可以同时处理 的部分,提交给计算机,同时迸行处理。例如存储器猝发存取方式 就是对多个字节(或者字)同时写入或者读出;又如超标量流水线就 是让多条指令同时执行。 广义地讲,并行性还可以理解为多个程序同时执行。例如,操 作系统中的多道程序处理,用户屏幕操作时的后台处理等。这些都可 以认为是多个程序在并行执行
7.1.1 并行处理的基本概念 1.并行性的基本概念 并行性(Parallelism)也称为同时性或并发性，是指在数值计算、 数据处理、信息处理或人工智能求解的过程中存在许多可以同时处理 的部分，提交给计算机，同时进行处理。例如存储器猝发存取方式， 就是对多个字节（或者字）同时写入或者读出；又如超标量流水线就 是让多条指令同时执行。 广义地讲，并行性还可以理解为多个程序同时执行。例如，操 作系统中的多道程序处理，用户屏幕操作时的后台处理等。这些都可 以认为是多个程序在并行执行
2并行性的表示方法 并行处理着重开发计算过程中存在的并发事件,使之并行处理。在 并行处理时,一次处理事件的大小或者规模不尽相同,常用粒度( Granularity)来表示。 所谓粒度,是衡量软件进程中所含计算量的大小,常用程序段中指 令数来表示。但在实际应用中,而是假设一个并行处理系统中有P个处 理器,同时执行某一任务,用八表示所有处理器进行计算时所用时间的 总和,7表示所有处理器通信时间的总和,若用表示并行处理中的粒 度,则 (7.1) 式中 7=∑t 式中显示7增大时,(减小。相反,当粒度较粗时,各处理 器之间的通信量减小
G = Tw Tc （7.1） 2.并行性的表示方法 并行处理着重开发计算过程中存在的并发事件，使之并行处理。在 并行处理时，一次处理事件的大小或者规模不尽相同，常用粒度（ Granularity）来表示。 所谓粒度，是衡量软件进程中所含计算量的大小，常用程序段中指 令数来表示。但在实际应用中，而是假设一个并行处理系统中有P个处 理器，同时执行某一任务，用Tw表示所有处理器进行计算时所用时间的 总和，Tc表示所有处理器通信时间的总和，若用G表示并行处理中的粒 度，则 Tw =∑twi P i=1 Tc =∑t ci P i=1 式中 式中显示Tc增大时，G减小。相反，当粒度较粗时，各处理 器之间的通信量减小
3并行性的等级 并行处理中的粒度可分为五个等级,即作业级、任务级、例行程序 或子程序级、循环和迭代级及谲句和拎令级,妪图λ.1所示。 层次1 作业级(程序) 层次2 任务级(程序段或过程) 层次3子任务级(例行程序或子程序) 层次4 循环和迭代 层次5 语句和指令 图7.1不同层次的并行性
3.并行性的等级 并行处理中的粒度可分为五个等级，即作业级、任务级、例行程序 或子程序级、循环和迭代级及语句和指令级，如图7.1所示。 图7.1 不同层次的并行性
通常,并行处理就是在这些层次的任何级或多级上开发并行 性。层次越高,并行处理的粒度也就越大;相反,层次越低,并行处理 的粒度也就越小。一般而言,粗粒度的并行开发主要采用MIMD方式 细粒度的并行性开发主要采用SⅠIMD方式 并行处理技术是从单处理机的并行处理逐步发展而来,包括采用 多功能部件、使CPU与O重叠操作、流水线方式、多道程序技术以及 分时等
通常，并行处理就是在这些层次的任何一级或多级上开发并行 性。层次越高，并行处理的粒度也就越大；相反，层次越低，并行处理 的粒度也就越小。一般而言，粗粒度的并行开发主要采用MIMD方式； 细粒度的并行性开发主要采用SIMD方式。 并行处理技术是从单处理机的并行处理逐步发展而来，包括采用 多功能部件、使CPU与I/O重叠操作、流水线方式、多道程序技术以及 分时等
7.1.2并行性的开发途径 在一个计算机系统中,开发并行性的途径有多种,大体上可归纳为 以下三种。 1时间重叠 时间重叠( Time interleaving)是在并行性概念中引入时间因素 使多个处理过程在时间上相互错开,轮流重叠使用同一套硬件设备的各个 部分,以加快程序的执行过程。细粒度流水线就是这种并行性的典型代表。 2资源重复 资源重复( Resource replication)是在并行性概念中引入空间因素 即重复设置硬件设备来提供并行操作的途径和系统可靠性。例如后面所要 介绍的使用∧个完全相同的处理器构成的SIMD阵列机就是具体的例子。另 外,人们常说的热备份和多机容错技术也是重复使用某些资源,组成冗余 部件,以提高系统的可靠性
7.1.2 并行性的开发途径 在一个计算机系统中，开发并行性的途径有多种，大体上可归纳为 以下三种。 1.时间重叠 时间重叠（Time interleaving）是在并行性概念中引入时间因素， 使多个处理过程在时间上相互错开，轮流重叠使用同一套硬件设备的各个 部分，以加快程序的执行过程。细粒度流水线就是这种并行性的典型代表。 2.资源重复 资源重复（Resource replication）是在并行性概念中引入空间因素， 即重复设置硬件设备来提供并行操作的途径和系统可靠性。例如后面所要 介绍的使用n个完全相同的处理器构成的SIMD阵列机就是具体的例子。另 外，人们常说的热备份和多机容错技术也是重复使用某些资源，组成冗余 部件，以提高系统的可靠性
3.资源共享 资源共享( Resource sharing)是用软件的办法让多个任务 按定的时间顺序轮流使用同一套资源,以提高利用率。例如操作 系统中的多道程序和分时系统就是利用软件的方法使多个用户或程 序共享CPU、主存储器和外部设备等硬件资源。 并行性的开发可分为粗粒度和细粒度两种。粗粒度并行性开 发主要采用的是软件方法。比如在作业(或程序)级,通过对并行 算法的分析来确定可以并行操作的作业(或程序);在任务级,是 通过软件对任务进行分解,将其中的子任务,乃至子任务中的例行 程序、子程序及可以并行操作的循环找出来,分配给不同的处理器 并行处理。 开发细粒度的并行性主要涉及到指令级及指令的内部操作 因而与处理器的外特性和内特性紧密相关,因此主要采用硬件的方 法来实现。随着RISC技术的发展,超级标量机、超长指令字、超级 流水线等技术成为这一方向的发展趋势
3. 资源共享 资源共享（Resource sharing）是用软件的办法让多个任务 按一定的时间顺序轮流使用同一套资源，以提高利用率。例如操作 系统中的多道程序和分时系统就是利用软件的方法使多个用户或程 序共享CPU、主存储器和外部设备等硬件资源。 并行性的开发可分为粗粒度和细粒度两种。粗粒度并行性开 发主要采用的是软件方法。比如在作业（或程序）级，通过对并行 算法的分析来确定可以并行操作的作业（或程序）；在任务级，是 通过软件对任务进行分解，将其中的子任务，乃至子任务中的例行 程序、子程序及可以并行操作的循环找出来，分配给不同的处理器 并行处理。 开发细粒度的并行性主要涉及到指令级及指令的内部操作， 因而与处理器的外特性和内特性紧密相关，因此主要采用硬件的方 法来实现。随着RISC技术的发展，超级标量机、超长指令字、超级 流水线等技术成为这一方向的发展趋势
7.2SMD阵列机 7.2.1SIMD阵列机的基本结构 7.2.2阵列机并行算法 7.2.3SIMD阵列机的特点 7.24并行存储器无冲突访问
7.2 SIMD阵列机 7.2.1 SIMD阵列机的基本结构 7.2.2 阵列机并行算法 7.2.3 SIMD阵列机的特点 7.2.4 并行存储器无冲突访问