并行程序设计

为了提高计算机的运行速度和系统的处理能力,在总体设计和逻辑设计中广泛采用并行操作技术,使各部件并行工作。要求操作系统具有并发性及资源共享,于是采用了并行程序设计,它是能够同时执行2个以上运算或逻辑操作的程序设计技术。采用了并行程序设计技术后,可使分时和多道程序更全面地利用计算机资源,使系统效率提高,开销减小 (所占内存小,花费的处理时间短) 。

能同时执行两个以上运臭套盼算或脚颈逻辑操作的程序设计方法。所谓并行性,严格地说,有两种含义:一是同时性,亦即平行性,指两个或多个事件在同一时刻发生;二是并发性,指两个或多个事件在同一时间间隔内发生。程序并行性分为控制并行性和数据并行性。并行程序的基本计算单位是进程。并行程序有多种模型,包括: 共享存储; 分布存储 (消息传递); 数据并行;面向对象。与并行程序设计相适应的硬件也有不同类型,如多处理机,向量机,大规模并行机和记巴舟机群系统等,相应有不同的并行程序设计方法。具体解题效率还与并行算法有关 。

并行编程类型逐渐汇聚于两类:用于PVP,SMP和DSW的共享变量的单地址空间模型和用于MPP和机群的消息传递的多地址空间模型.

并行编程模型逐渐汇聚于三类标准模型:数据并行(如:HPF),消息传递(如:MPI和PVM),和共享变量(如OpenMp).

人们希望高性能的并行机应是 具有单一系统映像的巨大的工作站,使得很多用户都能利用增强处理能力和储存容量来运行多个串行作业,这就是所谓的串行程序并行系统SPPS.

当我们在实际的并行机上设计并行程序时,绝大部分均是采用扩展Fortran和C语言的办法,有三种扩展的办法:一是库函数法:除了串行语言所包含的库函数外,一组新的支持并行性和交互操作的库函数(如MPI消息传递库和POSIXPthreads多线程库)引入到并行程序设计中。二是阿乐阀新语言结构法:采用某些新的语言结构来帮助并行程序设计以支持并行性和交互操作(如Fortran 90 中的聚集数组操作); 三是编译制导法:程序设计语言保持不变,但是将称之为编译制导的格式注释引入到并行程序中.

为了对实际的或逻辑的并行性编程,必须有一 些用以建立(create)与消灭(destroy ) (即, 设立与终止)进程的一些手段和用于这些进程彼此 间通信与同步的一种方法。许多系统与语言提供了 这样的并行程序设计设施。显式地提供这样一些机 构的操作系统是DEC PDP-11与DEC VAX 计算机上的UNIX(q.v)系统。并行Pascal与 Modula都运行在DEC PDP-11上,Mesa语言 是在Xerox开发的,Ada (q.v.)语言是为美 国国防部开发的,它们都是含有并行程序设计结构的现代程序设计语言的例子 。

FORK与JOIN语句是一组可用于动态地建 立与消灭进程的语句。用于说明并行性的静态设施 是cobegin/coend结构。它具有如下形式:

cobegin S1//S2//…//Sncoend

它表示(可能是复合的)语句S1、S2、……与Sn可并行执行。

同步机构有TEST AND SET这样的机器 语言指令,它不可分割地执行下列操作序列: 检查 一个存储单元为0还是1,把检查结果存储在一个寄存器中,使该单元置位为1; 对于实现锁定或象 对信号量的Dijkstra P与V操作达多应旬这样的低级同步原语,TEST AND SET是方便的。在较高级是监督程序。这一设施用来说明表示一资源的共享数据 结构与定义用于获得、释放与存取该资源的过程; 监督程序容许封闭与调度可被若干进程使用的资源 目标。

获得同步的另一种常用的方法是通过信息发送原语。简单的例子是send(p,m)与receive (p,m)。send(p.m)导致信息m传送到进 程p,receive(p.m)等待讲蜜重来自进程p的信息, 把该信息插入m中。因为它并不依赖通过公用存储器中的共享变量进行通信,信息传递对于分布式计算是有用的,在分布式计算中,各任务通过通信线路连接。

仍在进行笑迁汗全精炼与测试的Ada语言具有把过程调 用与信息发送两者结合起来的通信与同步语句。在 两个进程之间的通信通常进行如下。

一个进程用含有输入与输出参数的任务入口调 用来调用另一个进程,而被调用的进程发出一个等 待这样一个调用的accept语句;accept语句还包 括一个任意的语句序列,该语句序列作为接受此任 务入口调用时出现的集结的一部分执行。在这个交互作用之后,调用进程与被调用进程两者可再并行 执行。Ada还提供一个选择等待语句,在其中有 在处于“开路”的一组accept语句之间的不确定 选择(即,如果发出一个相应的任务入口调用,其中一个集结是可能的)。

作为并行程序设计的一个例子,我们给出对于 一个公用缓冲问题的解决方法。假设我们要为一个 二进程系统编程,其中一个进程是生产者进程,它 把一些记录添加到一个存储区,另一进程是消费者 进程,它把这些记录移走。生产者进程可以是一个 与输入设备关联的进程,它把输入记录添加到存储 缓冲器中,而消费者进程负责检索记录并处理它 们;另一方面,生产者进程可产生用于与一输出设 备关联的消费者进程的输出记录。

公用缓冲区有N个记录(N≥1)的存储。主 要问题是使缓冲器的处理同步,因而:

1.如果有空间的话,生产者进程可以只添加 一个记录到缓冲器;如果存在一个记录的 话,消费者进程可以只移走一个记录。

2.一次仅一个进程可处理缓冲区。

我们假设生产者进程与消费者进程两者均是 “永远”循环的循环进程。采用信号量与cobegin/ coend,程序的轮廓如下:

Semaphore empty(N),{缓冲器中空槽的 数目,初始为N}

full(0),{缓冲器中满记 录的数目,初 始为0}

lock(1); {在缓冲器处理期 间,保证互斥}

Cobegin producer:

loop

begin produce Next Record;

P(empty); {只有在缓冲器中 可得到一个空槽 的情况下才进 行}

P(lock); {设置锁定到0,避 免缓冲器被Consumer存取}

Add Record To Buffer;

V(lock); {设置锁定到1,允 许被producer 或Consumer存 取}

V(full) {增加缓冲器中满 记录的数目

end consumer:

loop begin P(full); {只有在缓冲器中 有一个满记录时 进行}

P(lock); {对producer锁 住缓冲器}

Take Record From Buffer;

V(lock); {缓冲器开锁}

V(empty); {增加缓冲器中可 用槽的数目}

process Record end Coend

相关词汇

运行速度
系统
总体设计
操作系统
程序设计
并行性
同时性
并发性
处理机
地址空间
机群
系统映像
串行程序
并行性
并行性
数组
程序设计语言
UNIX
Mesa
信号量
Dijkstra
原语
分布式计算
进程
消费者
输入设备
电脑版