《并行程序设计方法和模型研究》由会员分享，可在线阅读，更多相关《并行程序设计方法和模型研究（29页珍藏版）》请在金锄头文库上搜索。
1、并行程序设计方法和模型研究并行程序设计方法和模型研究摘要摘要随着并行硬件系统的发展，并行编程愈趋重要。本文主要研究了并行程序的模型、设计方法以及并行编程的一些标准。另外，随着通用GPU（GPGPU）的发展，本文还讨论了利用GPU进行并行计算，其中重点讲述了CUDA（通用并行计算架构）。1. 并行系统划分并行系统划分要实现软件并行执行的目标，就必须为多个线程同时执行提供一个硬件平台。对计算机体系结构分类的经典方法就是费林分类法。费林分类法（Flynns Taxonomy）是一种高效能计算机的分类方式，1972提出，把计算机分为四种类型：单指令流单数据流（SISD）、单指令流多数据流（SIMD）、
2、多指令流单数据流（MISD）、多指令流多数据流（MIMD）。 SISD (Single Instruction Single Data)：单处理指令单数据，一条指令处理一个数据，所有的冯诺依曼体系结构的“单处理器计算机”都是这类，其硬件不支持任何形式的并行，所有的指令都串行执行。在某个时钟周期内，CPU只能处理一个数据流。SIMD (Single Instruction Multiple Data)：单指令多数据，用一个指令流同时处理多个数据流。此类机器在诸如数字信号处理、多媒体信息处理、向量运算处理等应用领域非常有效。时至今日，几乎所有的计算机都以各种形式的指令集形式实现SIMD功能，例如I
3、ntel处理器中实现的MMX、SSE、SSE2、SSE3等扩展指令集。这些扩展指令集都能够在单个时钟周期内处理多个数据单元，这些数据单元存储在浮点寄存器中。MISD (Multiple Instruction Single Data)：多指令单数据，采用多个指令流同时对一个数据流进行处理。但是在大多数情况下，多个指令流处理多个数据流才是更加有效的处理方式，因此，MISD并行计算机一般只是作为一种理论模型出现。MIMD (Multiple Instruction Multiple Data)：多指令多数据，每个处理单元有独立指令和数据。能够同时执行多个指令流，这些指令流分别对不同的数据流进行操作
4、。MIMD是目前最流行的并行计算平台，现代流行的并行处理结构都可以划入到这一类。1.1 MIMD 型计算机体系结构型计算机体系结构MIMD性计算机体系结构细分的标准是内存结构，即内存是如何组织的。内存结构可以简单的分为两大类：共享内存和消息驱动。共享内存就是指所有处理器共享内存，所有CPU由一个操作系统控制，通过共享内存进行通信；消息驱动就是处理器之间不共享内存，靠消息驱动来进行通信，就是分布式内存，CPU由不同的操作系统控制，不同的CPU之间通过网络通信。1.1.1 共享内存型共享内存型共享内存型体系结构可以分为对称多处理机SMP，非一致内存访问NUMA。对称多处理机SMP(symmetri
5、c multiprocessors): 所有CPU都共享同一内存。图 1-1 对称多处理机内存模式目前Intel和AMD推出的多核CPU应该都划归到对称多处理机这一类。非一致内存访问NUMA (nonuniform memory access):所有CPU共享所有的内存，但不同的CPU访问不同的内存时速度不一样。图 1-2 非一致内存访问内存模式CPU访问离自己近的内存是本地直接访问的，访问离自己远的内存是通过总线访问的，因此两者速度差别很大，这也是之所以叫做非一致内存访问的原因。与非一致内存访问NUMA类似的还有一个叫ccNUMA，前缀cc是cache-coherent（一致性高速缓存）的缩
6、写，它其实就是为了解决访问不同内存速度不一样的问题。1.1.2 消息驱动型消息驱动型消息驱动型体系结构比较典型的就是分布式内存（DM）结构。分布式内存DM (Distributed memory)：每个CPU都有自己的内存，CPU之间通过消息来通信。图 1-3 分布式内存结构根据interconnect network的不同，分布式内存可分为三种：大规模并行处理系统（MPP）、集群（Cluster）、网格系统（Grid）。三者的差别简单的来说就是：MPP是一台机器，Cluster是一群相同或者类似的机器，Grid是一堆任意的机器。大规模并行处理系统MPP (massively parallel
7、 processors)：这样的系统是由许多松耦合的处理单元组成的，每个处理单元内的CPU都有自己私有的资源，如总线，内存，硬盘等。在每个单元内都有操作系统和管理数据库的实例复本。这种结构最大的特点在于不共享资源。 集群Cluster：集群应该是大家最常见的，就是一堆相同或者类似的机器通过网络连起来组成一个计算机群，相互之间通过网络进行通信。 网格系统Grid：网格系统其实和集群差不多，都是一堆机器通过网络连接起来，但两者还是有不同的地方：1）集群中机器都是同质的，而网格中是异质的，可能一个大型机、一台PC机、一台手机都是网格系统中的一个机器；2）集群中的机器都是属于某一个实体的，需要“集中管
8、理”，例如一个公司、一个组织、一个人；而网格中的机器属于不同的实体的，只需要“分散管理”即可，甚至大家都不知道有哪些机器在这个网格中。3）大部分情况下，集群是通过局域网进行连接，网格是通过互联网连接。2. 并行编程模式并行编程模式并发与并行的区别：并发是指多个线程在某段时间内能够同时被执行，并发可以在串行处理器上通过交错执行的方式来实现，但是在同一时刻，只能有一个活动线程；并行是指多个线程在任何时间点都同时执行。图 2-1 在单核平台上的线程并发图 2-2 在多核平台上的线程并行并行可以分为数据并行和任务并行:数据并行非常简单，它是指您有大量数据需要处理例如图像中的像素，大量工资支票等。把这些
9、数据进行分解并交给多个核进行处理，这就是一种数据并行方法。任务并行性则是指有多个任务需要完成。例如求一个数据集的最小值、最大值和平均值，就可以让不同的核针对同一个数据集分别计算其最大、最小和平均值的答案。从并行的层次上看，还可以把并行分为指令级并行和线程级并行。指令级并行是指在单个 CPU 中，利用超标量、超级流水线、超长指令字、超线程、分支预测等方法，使得多条指令在同一个 CPU 上同时运行，以提高系统的吞吐率。线程级并行是指在多核结构中，将多个线程分别分配到不同的核上执行。指令级并行和线程级并行的一个很重要的区别在于，指令级并行对于程序员来讲是透明的，相反，线程级并行则需要程序员自己来分配
10、执行单元，受到程序员的控制,因而更加灵活。超标量：通过在CPU上内置多条流水线，使CPU在一个时钟周期内可以执行多条指令，以空间换取时间。超级流水线：也叫深度流水线。通过细化流水、提高主频，使得在一个周期内完成一个或多个操作，以时间换取空间。超长指令字：这里的指令是由编译器提取出来的可并行的若干指令组成的长指令，一条长指令用来实现多个操作的并行。这减少了内存访问，提高了执行单元的利用率。超线程：超线程技术就是利用特殊的硬件指令，把两个逻辑内核模拟成两个物理芯片，减少了CPU的闲置时间，提高的CPU的运行效率。虽然采用超线程技术能同时执行两个线程，但它并不像两个真正的CPU那样，每个CPU都具有
11、独立的资源。当两个线程都同时需要某一个资源时，其中一个要暂时停止，并让出资源，直到这些资源闲置后才能继续。并行计算的功能：降低单个问题求解的时间；增加问题求解规模、提高问题求解精度、(多机同时执行多个串行程序)容错、更高的可用性、提高吞吐率。并行程序设计需要注意的四个方面：同步、通信、负载平衡、可扩展性。同步(Synchronization)：指两个或者多个线程协调各自行为的过程。例如一个线程停下来等待另一个线程完成某项任务。通信(Communication):指线程之间交换数据相关的带宽和延迟问题。负载平衡(Load Balancing)：指多个线程之间工作量分布的情况。负载平衡能够使各线程
12、的工作量大致平均分配。可扩展性(Scalability)：是衡量在性能更强劲的系统上运行软件时能够有效利用更多线程的指标。例如，如果一个应用程序是面向四核系统编写的，那么当该程序在八核系统上运行时，其性能是否能够线性增长。并行程序设计方法：隐式并行程序设计与显式并行程序设计。隐式并行程序设计：常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行。程序的自动并行化是一个理想目标，存在难以克服的困难。隐士并行程序设计的特点是语言容易，编译器难。显式并行程序设计：在用户程序中出现“并行”的调度语句。显式的并行程序开发则是解决并行程序开发困难的切实可行的方法。特点是语言难，编译器容易。并行
13、程序设计模型：隐式并行（Implicit Parallel）、数据并行（Data Parallel）、共享变量（Shared Variable）、消息传递（Message Passing）。隐式并行(Implicit Parallel)：程序员用熟悉的串行语言编程(未作明确的制定并行性)，编译器和运行支持系统自动转化为并行代码。特点：语义简单、可移植性好、易于调试和验证正确性、细粒度并行、效率很低。数据并行（Data Parallel）:类似于 SIMD的自然模型。特点：单线程、并行操作于聚合数据结构（数组）、松散同步、单一地址空间、隐式交互作用、显式数据分布；优点:编程相对简单,串并行程序一
14、致。缺点:程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解。并行粒度局限于数据级并行,粒度较小。共享变量（Shared Variable）：对称多处理机的自然模型。特点：多线程、异步、单一地址空间、显式同步、隐式数据分布、隐式通信。消息传递(Message Passing)：集群的自然模型。特点：多线程、异步、多地址空间、显式同步、显式数据映射和负载分配、显式通信。分解要采用并行程序设计模式来设计应用程序，设计人员应该将应用程序中能够并行执行的部分识别出来。要做到这样，程序员必须将应用程序看做是众多相互依赖关系任务集合。将应用程序划分成多个独立的任务，并确定这些任务之间的相互关
15、系的过程称为分解（Decomposition）。主要的分解方式有三种：任务分解、数据分解、数据流分解。表 2-1 分解方式任务分解：对应用程序根据其执行功能进行分解的过程称为任务分解，使独立任务能够同时运行。如果两个任务能够同时运行，则对其进行调度，形成二者之间的并发执行。一般而言，需要对分解出来的任务进行修改，避免各个任务之间的冲突，同时标记不再是串行执行的。以园艺工作举例：如果两个园丁到达一个客户家，一个修剪草坪，另一个铲除杂草。修剪草坪和铲除杂草是两个被分开的功能。要完成这两个功能，园丁们需要确保他们之间相互协调，这样铲除杂草的园丁就不会坐在待修剪草坪的中间。数据分解：也称为数据级并行（
16、data-level parallelism)。将应用程序根据各任务所处理的数据而非按照任务的天然特性来进行分解的方法。一般而言，能够按照数据分解方式进行分解的应用程序都包含多个线程，这些线程分别对不同的数据对象执行相同的操作。数据分解所能够处理的问题规模随着处理器核数量的增长而增长。如果园丁应用数据分解来分解他们的任务，他们两个会同时修剪一半的草坪，然后两个人分别铲除一半的杂草。数据流分解：更关心数据在各个任务间是如何流动的。典型的是生产者/消费者模型，一个任务的输出是另一个任务的输入。许多时候，当分解一个问题时，关键不是任务应该做什么事情，而是数据在不同任务中怎样传递。在这些情况下，数据流分解将问题按数据在任务中传递的方式来分解。生产者与消费者两个任务被不同的线程执行，直到生产者完成他的部分工作，消费者不能开始工作。依然引用园丁的例子，一个园丁准备工具，譬如他承担为割草机加油，清扫剪刀等类似的任务来提供这些工具给另两个园丁使用。直到这个准备步骤基本结束，其他园丁的园艺工作才能开始。由第一个任务引起的延迟为第二个任务产生一个暂停，在此之后两个任务才能并
