并行计算机的同步与通信

第6章并行计算机的同步与

通信

计算机系统结构

胡越明

计算机系

Agenda

■6.1并行计算机系统的通信

■6.2Cache与存储器数据一致性

■6.3并行计算机的同步

■6.4并行计算机程序设计

上再文囱尤孝

6.1并行计算机系统的通信

■并行计算机对程序的要求

□代码的可重入

□并行线程之间的竞态现象

■线程之间对共享变量的不同的读-写和写-写访问顺序导致

不同的程序执行结果

■源自线程间的数据相关性

■并行计算机的通信方式

□共享存储器

□互连网络的消息传递

上再文囱尤孝

I共享存储器通信

■共享变量

□最简单的通信方式

□没有同步功能

■信号（signal）

□一个二进制变量

□可以表示条件、状态、锁和其它同步信息

□不能传递数据内容

■信箱

:固定格式的通信结构

□通常包含一个标志位

■在发送方和接收方之间起到同步的作用

□寻址和管理比较简单，不够灵活

-消息

□具有灵活格式的通信单位

上再文囱尤孝

I共享存储器通信

■线程同步

□给线程执行顺序施加约束的机制

□控制线程执行的相对顺序

□建立在互斥机制的基础上

■互斥机制

□使得一次只有一个线程对共享变量进行访问

□以保证每个线程对于共享变量访问的完整性

■常见的互斥机制

□锁

□信号量

□临界区

上再文囱尤孝

I共享存储器通信

■锁

□一种互斥变量

□一次只能被一个线程获得

■信号量

□通过PV操作在线程间传递同步信息

■原子操作

□P操作将一个变量减1

■减后的变量小于0时线程被阻塞

□V操作将一个变量加1

■加后的变量大于或等于0时释放一个线程

上再文囱尤孝

I共享存储器通信

■临界区

□短小的、不能被中断的程序段

□进入的线程数量是有限制的

□通常只允许一个线程进入临界区

□可以采用锁机制来实现

上再文囱尤孝

I锁

■两个基本的原子操作

□Acquire

■原子地等待锁的状态变成打开的状态

■将打开的锁状态变成关闭的状态

□这时该线程获得了锁

□Release

■原子地将锁的状态从关闭状态变成打开的状态

□这时线程释放了锁

上再文囱尤孝

锁的类型

■互斥量

□用PV操作上锁和解锁

□有阻塞

□可以加上时间属性

■递归锁

□可以递归地获得的锁

□用于递归程序

■读写锁

□多读单写锁

■限制写操作只能由一个线程执行

□用于对共享变量的读写操作

■自旋锁

□非阻塞的锁

□用于多处理机系统和多核系统

上再文囱尤孝

阻塞型锁机制的问题

■优先级的颠倒lorityinversion

□当一个低优先级的线程占用了一个锁之后，需要同

一个锁的高优先级线程就只能等待。

■护航Convoying

□当一个线程拥有一个锁而被切换出去时其他的线程

如果需要同一个锁的话都不能运行下去

□其他线程都围着拥有锁的线程团团转

■死锁adlock

□锁的拥有和依赖关系形成一个环

上再文囱尤孝

死锁及其解决

■死锁的原因

□对资源（锁）的访问是独占的

□线程在已经持有一个资源时继续请求其他资源

□所有线程都不放弃已经持有的资源

□线程对资源的请求形成一个环

■解决方法

□复制需要独占访问的资源

□按照一定的顺序获取资源

■有序嵌套

□无法获取其他资源时放弃已持有的资源

□调用构件时避免使用锁

上再文囱尤孝

信号

■硬件信号

□一种黏滞性的逻辑电平

■一旦被设置就一直保持不变

■直到被清除

□如访存完成、cache失效、时钟信号

□可以表示为一个寄存器变量

■对于信号变量的读操作清除这个信号

■软件信号

□表示为共享变量

□如进程中止信号

上再文囱尤孝

I互连网络的消息传递通信方式

■消息

□结点间通信的基本逻辑单位

□消息头

■目标结点号、源结点号、消息类型和消息长度等

□消息体

■通信数据

<__________________消自买_________________L________滔自休______>消自昆

・1闩心、°・1口心、卜・in心、汽i

目标结点号序号消息类型消息长度数据校验和

上再文囱尤孝

I互连网络的消息传递通信方式

■数据包•存储转发

□数据传输的物理单位•store-and-forward

■寻径信息•电路交换

■序号•circuitswitching

■数据内容•虚拟切换

■校验位•virtualcut-through

■协议号•虫孔寻径

■时间戳•wormhole

上再文囱尤孝

I互连网络的消息传递通信方式

存储转发store・and・forward

■问题：延迟大，缓存多

上再文囱尤孝

I互连网络的消息传递通信方式

电路交换circuitswitching

问题：冲突多，利用率低

上再文囱尤孝

I互连网络的消息传递通信方式

虚拟切换virtualcut-through

上再文囱尤孝

I互连网络的消息传递通信方式

虫孔寻径wormhole

问题：死锁和活锁

I互连网络的消息传递通信方式

■虫孔寻径与存储转发的比较

Ni

N2

N4

结点"

日寸向

序列-(a)存储转发:

结点

-寸奇

序列(b)虫孑L寻径13I

上再文EH孝

I互连网络的消息传递通信方式

衡量指标

□通信带宽

□单位时间能够传输的数据量

□取决于处理器的通信处理吞吐率、存储器的吞吐率和互连网络的传

输带宽

■通信延迟

□发送的时间开销

□信号传输时间

□传输持续时间

□接收方的时间开销

■通信延迟隐藏能力

□通信时间与计算时间或者其他通信时间的重叠程度

上再文囱尤孝

I例6-2

■1个计算任务在单个核的计算机上运行的启动时间为1

秒，运算时间为10秒，数据结果汇总的时间为1秒。

如果将该计算任务放在多核处理器的计算机上运行，

将运算部分分解成多个线程并行执行。

■(D假如任务的启动和数据汇总操作不能并行执行,

运算部分可以进行任意的任务分解，任务之间的通信

量可以忽略，也不考虑任务分解后存储系统对性能的

影响。问在处理器核的数量分别为2、4、8、16时的

任务执行时间和加速比。

■(2)上述情况下，假如每两个处理器核之间的通信

时间为0.1秒，每对处理器核的通信串行进行，问在

核的数量分别为2、4、8、16时的任务执行时间和加

I解：（1）

任务在单个核的计算机上运行时间为12秒；

■在双核计算机上的运行时间为1+10/2+1=

7秒,加速比为12/7=1.71；

■在4核计算机上的运行时间为1+10/4+1=

4.5秒,加速比为12/4.5=2.67；

■在8核计算机上的运行时间为1+10/8+1=

3.25秒，力口速比为12/3.25=3.69；

■在16核计算机上的运行时间为1+10/16+1

=2.63秒，力口速比为12/2.63=4.56。

上再文囱尤孝

I解：(2)

■任务在单个核的计算机上没有通信时间，运行时间为12秒；

■在双核计算机上的通信时间为1x0.1,运行时间为

1+10/2+1+0.1=7.1秒，加速比为12/7.1=1.69；

■在4核计算机上的通信时间为6x0.1=0.6,运行时间为

1+10/4+1+0.6=5.W,加速比为12/5.1=2.35；

■在8核计算机上的通信时间为28x0.1=2.8,运行时间为

1+10/8+1+2.8=6.05秒，加速比为12/6.05=1.98；

■在16核计算机上的通信时间为120x0.1=12,运行时间为

1+10/16+1+12=14.63秒，力口速比为12/14.63=0.82,即比单核

计算机的计算时间更长。

上再文囱尤孝

I解

5

4.5

4

3.5

3

--无通信开销

2.5

一有通信开销

2__________________________■、__________________________________________________

1.5

1____________、y7

0.5

011t1

单核2核4核8核16核

加速比单核2核4核8核16核

无通信开销11.712.673.694.56

有通信开销11.692.351.980.82

上再文aa孝

习题

■6

6.2Cache与存储器数据一致性

・共享存储器多处理机系统的问题

□访存冲突与数据一致性

□数据多个副本之间的相同性

CacheCacheMemorv■r

contentscontentsforcontentsfor

TimeEventforCPUACPUBlocationX

01

1CPUAreadsX11

2CPUBreadsX111

3CPUAstores0intoX010

上再文囱尤孝

数据一致性的实现

■软件方法

□编译分析

□避免cache共享数据

■总线监测

□各cache设置监测部件

■MESI协议

■目录表法

□全映射

□有限目录

□链式目录

■SCI

上再文囱尤孝

总线监测

■所有cache不断监测总线上的每一个地址

□总线使得写操作变成串行的

□Cache失效时需要确定数据块的位置

■writeinvalidateprotocol

□invalidatesothercopiesonawrite.

■writeupdateorwritebroadcastprotocol

□updateallthecachedcopiesofadataitemwhenitiswritten

上再文aa孝

总线监测

■写无效方式

□多次写操作时只需一次invalidate

□对于整个cache数据块进行

■写更新方式

□对于数据块中的个别字进行

□读操作的命中率高

□所有写操作通过总线写入所以相关的其他cache中

■写操作的开销较大

上再文囱尤孝

总线监测

■每个处理器的cache中设置一个监测部件

□监测总线上的写操作

□根据监测的情况改变本地cache块的状态

■无效、修改、独占、共享

■监测条件

□主存中有一个单元被其他处理器所修改

□而这个单元在本地cache中也有一个副本

■对于写更新方法

□拥有数据最新版本的cache需向其他cache提供数据块内容

□阻止其他处理器从共享存储器的读操作

上再文囱尤孝

MESJ协议

SHR

RH:读命中

RMS:读失效，共享

RME:读失效，独占

WH:写命中

WM:写失效

SHR:读时检测命中

SHW:写时检测命中或

旨在修改的读

①浊行复制回来

RH

Q无效事务

㊉旨在修改的读WH

J填充cache行

上再文囱尤孝

I例6.3

■设单总线连接的两个CPU中采用MESI协议进行一致性操作，初始

时某cache块都在无效状态，然后两个CPU对该存储块分别进行如

下操作：

■CPUA读，CPUB读，CPUA写，CPUB读，CPUB写

■试写出每次访问后两个块的状态变化情况。

事件状态A状态B说明

初始无效无效(I)数据未装入

CPUA读独占无效(I)读操作cache失效，装入

CPUB读共享共享(S)读操作cache失效，装入后共享

CPUA写修改无效(I)写操作命中

CPUB读共享共享(S)读操作失效，装入

CPUB写无效修改(M)写操作命中

I例6.4

■在一个共享L2cache的双核处理器芯片中，两

个L1cache通过片内总线与L2cache连接，并

采用MESI协议保持一致性。假设L1cache各

有4个块，采用全相联地址映像和LRU替换策

略，每个块的初始状态都是无效的。在以下读

访问块地址序列下，试画出两个L1cache中块

的分配情况，并标出每个块的状态。

■A核：1,0,6,7,8,0,1

■B核：0,2,1,8,9,2,0

A核块地址

1067801

1E1E1E1E8S8S8S

A核LIcacheI0S0S0S0S0S0S

II6E6E6E6E1E

III7S7S7S7S

操作装入装入装入装入替换命中替换

B核块地址0278920

0E0S0S0S9E9E9E

B核LIcacheI2E2E2E2E2E2E

II7E7S7S7S0S

III8E8S8S8S

操作装入装入装入装入替换命中替换

上再文囱尤孝

目录表法

■全映射

□每个快表目录项包含N个指示位段

■N为系统中处理器的个数

□指示位段构成一个位向量

■0表示相应的处理器cache没有该块

■1表示有该块

■有限目录

□每个快表目录项包含固定数量的指示位段

□指示位段的位数与处理器数量无关

■链式目录

上再文囱尤孝

I例6・5

■设4个CPU的并行计算机中采用全映射的目录表法进行一致性操作,

初始时某cache块都在无效状态，然后4个CPU对该存储块分别进

行如下操作：

■CPU0读，CPU1读，CPU2读，CPU1替换，CPUO写

-试写出每次访问后该块的有效指示位段的变化情况，假设一致性

操作采用写无效策略。

事件指示状态位段

初始0000

CPU0读0001

CPU1读0011

CPU2读0111

CPU1替换0101

CPUO写0001

上再文囱尤孝

I例6.6

■在一个由2个CPU构成的并行计算机中采用全

映射的目录表法进行一致性操作。假设各CPU

的cache都只有4个块，采用全相联地址映像和

LRU替换策略，每个块的初始状态都是无效的。

在以下读访问块地址序列下，试画出两个L1

cache中块的分配情况，并标出每个块的指示

状态位段。

■CPUA：1,0,6,7,8,0,1

■CPUB：0,2,7,8,9,2,0

I解

CPUA块地址

1067801

101101101101811811811

CPUAcache00011011011001001011

0000601601601601101

000000711711711701

操作装入装入装入装入替换命中替换

CPUB块地址0278920

010011011011910910910

CPUBcache00210210210210210210

0000710711711711011

000000810811811811

操作装入装入装入装入替换命中替换

上再文aa孝

目录表法

■链式目录

□将目录分布到各

个cache头项中间项中间项尾项

□每个cache的块

表中只需存放一

个cache指针

□单链或双链

□SCI

上再文囱尤孝

数据一致性对cache性能的影响

■影响cache性能的因素

□单个处理器cache失效的数据传输

□数据通信引起的传输

■导致invalidations和后继cache失效

■一致性失效

/处理机数量

/Cache容量

/块大小

上再文囱尤孝

数据一致性对cache性能的影响

一致性失效

■真共享失效truesharingmisses

□由cache一致性操作的通信引起

□对共享数据的第一个写操作引起invalidation

■伪共享失效fa/sesharingmisses

□由每个cache块只有一个有效位引起

□一个块中其他数据的写操作引起cache块读操作的

失效

□Cache块是共享的，但是数据字并没有共享

数据一致性对cache性能的影响

■一致性失效的例子

□假定数据字x1和x2在同一个数据块中

■数据块在P1和P2之间共享

□假定以下事件序列

TimePlP2

1Writexl

2Readx2

3Writexl

4Wntex2

5Readx2

上再文囱尤孝

I存储器数据的一致性

时间一致性(consistency)

□一个写操作写入共享存储器中的数值什么时候能够被读到

■串行一致性

■弱化一致性

■处理机一致性

■松散一致性

上再文囱尤孝

I存储器数据的一致性

串行一致性sequentialconsistency

■处理机P对于存储单元x的写操作之后进行的读操作，其

间如果没有其它处理机对x进行写访问，则总是返回由P

写入的数值。

■在一个处理机P1对于单元X进行写操作之后，另一处理

机P2对于单元X的读操作只要两者足够分离并且没有其

它对于X的写操作发生，就能够返回P1写入的数值。

■对于同一单元的写操作是顺序进行的，即两个处理机对

于相同单元进行的写操作的顺序从任何处理机看都相同。

如果数值1和2依次写入一个位置，处理机不可能先读得

2,再读得1。

I存储器数据的一致性

■弱化一致性weakconsistency

□程序通过同步操作强调一致性，使得在这些同步点

上数据保持一致，而不要求数据随时都是一致的。

■处理机一致性processorconsistency

□每个处理机发出的写操作被其它处理机看到的都保

持原顺序，但两个不同处理机的写操作顺序可被其

他处理机以不同的顺序看到。

■松散一致性releaseconsistency

□采用acquir㊀-r㊀1㊀as㊀同步操作使得数据保持一

致，从而减少对硬件一致性处理的要求。

SCI

■scalablecoherenceinterface

□IEEE1596-1992

■支持链式目录表法

□双向链表

■采用双向链路

■采用虚拟切换传输方式

-支持大规模并行系统

□不要求消息按顺序提交

□使用64位固定长度地址的分布式存储器的寻址方案

■高16位用于寻找结点

■低48位地址指定结点内的存储器地址

■采用16位差分ECL信号链路

□信号时钟250MHz

□链路的数据传输带宽为1GB/S

上再文囱尤孝

习题

■11

■12

■13

■14

6.3并行计算机的同步

■同步机制

□并行系统中保持各并行程序正确运行的控制机制

□建立在通信机制的基础上

□需要采用的硬件提供的机制来实现

■硬件原语

上再文囱尤孝

硬件原语

■原子交换atomicexchange

□实现锁

■测试并设置test・and・set

□实现锁

■读取并力口lfetch・and・inc「ement

□实现屏障

■读取并更新test・and・update

□实现PV操作

上再文囱尤孝

原子交换

■将一个寄存器的数值与一个存储器中的数值进

行交换

■难以在并行机中实现

■要求存储器读写操作在一条不可中断的指令中完成

■硬件不能在读写操作之间响应中断

AB

上再文囱尤孝

原子交换

■解决方案

□用两条指令实现

■链接装载loadlinked

■条件存储storeconditional

□返回一个数值

□表示其存储操作是否成功

■两条指令按顺序执行

□如果链接装载指令指定的存储单元在对应的条件存储指令执

行之间被改变，则存储指令执行时失败。

□如果处理机在这两条指令之间进行了上下文交换，则该条件

存储指令也将失败。

上再文囱尤孝

原子交换

原子交换的实现exchR4,0(R1)

try:movR3,R4;mov㊀㊀xchang㊀valu㊀fromR4toR3

11R2,0(RI);loadlinked

scR3,0(RI);storeconditional

b㊀qzR3,try;branchstorefail㊀s

movR4,R2;putloadvalueinR4

宏指令

上再文aa孝

读隼并加1

try:11R2,0(R1);loadlinked

addiR2,R2,#1;incr㊀m㊀nt

scR2,0(RI);stor㊀conditional

beqzR2,try;branchstor㊀fails

R2

|+1

R2B

上再文aa孝

I派生原语

转锁spinlock

处理机用循环方法试图得到的锁

■没有cache一致性机制时

liR2,#1;loadimmediate

lockit:㊀xchR2,0(RI);atomic㊀xchang㊀

bnezR2,lockit;alr㊀adylocked?

■有cache一致性机制时

lockit:IwR2Z0(RI);loadoflock

bnezR2,lockit;notavailabl㊀一spin

liR2,#1;loadlockedvalu㊀

exchR2,0(RI);swap

bn㊀zR2,lockit;branchiflockwasn*t0

上再文囱尤孝

I派生原语

采用链接装载/条件存储实现转锁

lockit:11R2,0(RI);loadlinked

bn㊀zR2,lockit;notavailabl㊀一spin

liR2,#1;lockedvalue

scR2,0(RI);store

b㊀qzR2,lockit;branchifstorefailes

上再文aa孝

I派生原语

■屏障同步

□强制所有的线程等待

■直到所有的线程都到达屏障时释放所有的线程

■用一个计数器对到达的线程计数（Ga加凹阶段）

■用一个信号释放所有的线程（re/ease阶段）

□用两个自旋锁实现

■一个用于保护计数器

■一个用于锁住线程

I派生原语

屏障同步的实现

lock(count㊀rlock);/*ensureupdat㊀atomic

*/

if(count==0)r㊀1㊀as㊀=0;*firstarrivalr㊀s㊀tr㊀1㊀as㊀

*/

count=count+1;*countarrivals*/

unlock(counterlock);/*工㊀1㊀as㊀lock*/

if(count==total){/*allarrived*/

count=0;/*r㊀s㊀tcount㊀工*/

工㊀1㊀as㊀=1;*r㊀1㊀as㊀proc㊀ss㊀s*/

)

㊀Is㊀{*mor㊀tocom㊀*/

spin(r㊀1㊀as㊀==1);/*waitforarrivals*

)

上再文aa孝

I派生原语

■问题

□屏障可能循环使用

□从屏障离开的线程可能再次进入屏障

□一个线程可能在另一个线程离开屏障之前又进入屏

障

■代码的bug

I派生原语

■解决方案

□对离开的线程计数

■不允许线程在其他线程都离开上一个屏障之前又进入屏障

□从而又初始化屏障

□传感反相屏障

-使用线程局部变量

□初始化为1

□交替地等待1和o

release-------------------------1।--------------------为/夭3rH孝

I派生原语

■屏障同步的实现

□传感反相屏障

local_sense=!Iocal_sense;/*togglelocal_sense*/

lock(counterlock);/*ensureupdateatomic*/

count=count+1;/*countarrivals*/

if(count==total){/*allarrived*/

count=0;/*resetcounter*/

release=local_sense;/*releaseprocesses*/

}"

unlock(counterlock);/*unlock*/

spin(release==local_sense);/*waitforsignal*/

第一个到达屏障的线程并不改变release的值上再文囱尤孝

同步操作的性务邑问题

■Contentionforthelock

□Z⑵+1)=n2+2n

-锁变量访问的串行化

□大大增加完成同步操作的时间

■解决方案

□增量资源

■或分解资源

■如散列表的分割

□指数退避exponentialbackoff

■访问等待时间以指数增加

■防止活锁

□队列锁

■锁变量释放时通知下一个线程

□组合树

■树中每个结点组合k个线程的同步

■将对一个变量的竞争按树形结构分散

上再文囱尤孝

同步操作的性务邑问题

■指数等待

ADDUIR3,R0,#l；R3=initialdelay

lockit:LLR2,O(R1)；loadlinked

BNEZR2,lockit；notavailable-spin

DADDUIR2,R2,#1；getlockedvalue

SCR2,O(R1);storeconditional

BNEZR2,gotit；branchifstoresucceeds

DSLLR3,R3,#1;increasedelaybyfactorof2

PAUSER3；delaysbyvalueinR3

Jlockit

gotit：usedataprotectedbylock

同步操作的性务邑问题

■组合树

structnode{/*anodeinthecombiningtree*/

intcounterlock;/*lockforthisnode*/

intcount;/*counterforthisnode*/

intparent;/*parentinthetree=0..P-1exceptforroot*/

）；

structnodetree[0..P-1];/*thetreeofnodes*/

intlocal_sense;/*privateperprocessor*/

intrelease;/*globalreleaseflag*/

上再文aa孝

同步操作的性务邑问题

■组合树

/*functiontoimplementbarrier*/

barrier(intmynode,intlocal_sense){

lock(tree[mynode].counterlock);/*protectcount*/

tree[mynode].count=tree[mynode].count+1;

/*incrementcount*/

if(tree[mynode].count==k){/*allarrivedatmynode*/

if(tree[mynode].parent>=0){

barrier(tree[mynode].parent);/*recursivecall*/

}else{

release=local_sense;

)；~

tree[mynode].count=0;/*resetforthenexttime*/

unlock(tree[mynode].counterlock);/*unlock*/

spin(release==local_sense);/*wait*/

)；一

/*codeexecutedbyaprocessortojoinbarrier*/

local_sense=!Iocal_sense;

barrier(mynode);

上再文aa孝

I事务存储器

■同步机制的硬件解决方案

□非互锁的机制

□使得系统能够并行地执行原子操作

■事务

□锁的作用范围

□每个事务由一个线程推测性地执行而不请求锁

□没有遇到冲突时提交

■否则事务将放弃(abort)

■进行卷回(rollback)并重新开始

□事务没有成功提交之前不会对其它线程产生作用

上再文囱尤孝

I事务存储器

■事务

□由线程中的一组指令构成

□串行性

■从其他线程看来不会有不同的执行顺序

□原子性

■整体提交或者整体放弃

■提交之前对其它线程看不到

上再文囱尤孝

同步与多线程

多线程的程序的问题

■数据竞争

□由各线程对共享数据读-写访问和写-写访问顺序的不确定性

弓起

■同步

□同步机制会带来的开销

■线程停顿

□一个锁条解开使等待这个锁的线程停顿

■死锁

□线程的无限期的停顿现象

■伪共享

□①程之间的非真正的数据共享而引起的相关性

上再文囱尤孝

多线程的程序的问题

■数据竞争

□数据相关性险象

□以下两个if语句的表达式可能都为真吗?

Pl:A=0;P2:B=0;

A=1;B=1;

LI:if(B==0)L2:if(A==0)..

上再文aa孝

多线程的程序的问题

数据竞争之二

线程1线程2

原始代码t=X；U=X；

X=t+1;x=u+2;

并行情况1t=x;//xis0

u=X；

x=u+2;//xis2

x=t+1;//xis1

并行情况2u=x//xis0

t=X；

x=t+1;//xis1

x=u+2//xis2

并行情况3t=x;//xis0

x=t+1;//xis1

U=X；

x=u+2;//xis3

多线程的程序的问题

■数据竞争之三

■if(list->next==NULL)■if(list->next==NULL)

■insert(list->next,nodel)■insert(list->next,node2)

上再文aa孝

数据竞争的解决

■变量局部化

□将变量改为线程局部的

□如将全局和分解为部分和

■用临界区控制共享变量的访问

□通过锁、信号量等实现

□每个共享数据用一把锁

■互斥机制

上再文囱尤孝

同步与多线程

■并行线程与临界区I

□访问共享数据的程序段

□在某段时间内仅允许一定数目的线程访问I",,

的一段代码I

□大多数情况下一次只有一个线程能够进入同一个n

临界区।

□可采用互斥机制实现।

上再文囱尤孝

同步与多线程

-并行线程与屏障

习题

■16

■18

■20

■21

■22

6.5并行计算机程序的软件支持

并行程序的概念

□任务划分

□将一个任务划分成多个并行子任务

□使得处理器负载平衡

-数据划分

□将数据对象划分成多个并行子集

□提高访存的效率以及cache的命中率

-数据流划分

□根据数据处理的过程划分

□一个子任务的输出是另一个子任务的输入

♦划分的目标

•负载平衡

•降低调度开销、通信开销和同步开销

上再文囱尤孝

并行程序的概念

■任务task

□应用级的计算单位

■单任务线程

□为每个任务动态创建和终止

□创建和终止开销问题

□大量线程时的开销

■线程池

□预先创建的固定数量的线程

■与处理器数量匹配

□可完成多个任务

■应用程序中动态任务分配和调度

■线程中任意时刻只能运行一个纤程

上再文囱尤孝

并行程序的概念

■线程化的优点

□创建速度较进程快

□资源利用率高

□便于数据共享

■线程化的缺点

□增加程序设计的复杂性

□程序调试较难

■数据竞争、同步、死锁

上再文囱尤孝

多线程的执行

■硬件多线程

□每个线程运行在不同逻辑处理器上

□优先级相同

□硬件的通信开销

□真正的并行执行

■软件多线程

□运行在同一个逻辑处理器上

□OS动态改变优先级

□共享本地存储器

■通信开销小

■互斥容易解决

上再文囱尤孝

共享存储器系统程序设计例子

8个处理机，单总线连接

sum[Pn]=0;

for(i=8000*Pn;i<8000*(Pn+1);i=i+l)

sum[Pn]=sum[Pn]+A[i];/*sumtheassign㊀dar㊀as

half=8;/*8processorsinsingl㊀-busMIMD

do{

synch();/*waitforcompletionofpartialsums

half=half/2;/*dividinglin㊀ontwosums

if(Pn<half)sum[Pn]=sum[Pn]+sum[half+Pn];

}while(half〉l);/*㊀xitwithfinalsuminsum[0]

其中synch()函数是一个屏障同步函数。

上再文囱尤孝

分布消息传递型系统程序例子

■假设64个处理机，各处理机具有不同的地址空间。

■sum=O;

■for(i=0;i<1000;i=i+l)/*loopov㊀r㊀acharray*

■sum=sum+Al[i];/*sumth㊀localarrays*

■limit=64;

■half=64;/*64processorsinthisMIMD*

■do{

half=half/2;/*s㊀ndvs.r㊀c㊀iv㊀dividingline*

■if(Pn>=half&&Pn<limit)s㊀nd(Pn%ha1f,sum);

■if(Pn<half)sum=sum+r㊀c㊀iv㊀()；

■limit=half;/*upp㊀rlimitofs㊀nd㊀rs*

■}whil㊀(half〉l);/*㊀xitwithfinalsum*

上再文aa孝

I任务划分

■对数据进行划分

□使得不同的子任务对不同的数据子集进行处理

■对计算过程中的步骤进行

□使得每个线程具有不同的程序代码

■任务分解的一般方法

□根据数据运算流程图进行

上再文囱尤孝

I例6-8

■对于数组运算

E=A*(B+C*D);

■其中，A、B、C和D都是具有〃个元素的数组，

试画出其数据流程图，指出两种子任务划分方

式。

上再文囱尤孝

I解

■横向划分

■纵向划分

Cn

4

上再文囱尤孝

实现并行程序设计的方法

■库函数

□在串行程序的标准库的基础上增加支持并行操作的函数

□如MPI的消息传递库和POSIX的Pthread多线程库

□容易实现（不需要改变编译程序）

□程序中的并行性没有经过编译程序的检查、分析、优化

■新的语言构造

□程序设计语言中增加新的构造语句

□如Fortran90中增力口了向量运算语句

□编译程序可以进行并行性检查和优化

□增加了编译程序的复杂性。

■编译指导

□在原有的语言中增加表达并行运算的编译指导语句

□并行编译程序跟据指导语句将代码转换成在并行代码

□如OpenMP

□介于上述两种方法之间

上再文囱尤孝

I线程操作函数

■线程的创建和消除

□分叉和汇集(fork-join)机制

■线程的启动和终止

■线程同步机制的建立和删除

■线程通信机制的建立和删除

□如MPI

上再文囱尤孝

多线程并行程序设计方法

■将独立的循环程序变成多线程

□并行执行的线程可能改变相对执行的进度或顺序

□要求