并行計算機的同步與通信

第6章并行計算機的同步與

通信

計算機系統(tǒng)結(jié)構(gòu)

胡越明

計算機系

Agenda

■6.1并行計算機系統(tǒng)的通信

■6.2Cache與存儲器數(shù)據(jù)一致性

■6.3并行計算機的同步

■6.4并行計算機程序設(shè)計

上再文囪尤孝

6.1并行計算機系統(tǒng)的通信

■并行計算機對程序的要求

□代碼的可重入

□并行線程之間的競態(tài)現(xiàn)象

■線程之間對共享變量的不同的讀-寫和寫-寫訪問順序?qū)е?/p>

不同的程序執(zhí)行結(jié)果

■源自線程間的數(shù)據(jù)相關(guān)性

■并行計算機的通信方式

□共享存儲器

□互連網(wǎng)絡(luò)的消息傳遞

上再文囪尤孝

I共享存儲器通信

■共享變量

□最簡單的通信方式

□沒有同步功能

■信號（signal）

□一個二進(jìn)制變量

□可以表示條件、狀態(tài)、鎖和其它同步信息

□不能傳遞數(shù)據(jù)內(nèi)容

■信箱

:固定格式的通信結(jié)構(gòu)

□通常包含一個標(biāo)志位

■在發(fā)送方和接收方之間起到同步的作用

□尋址和管理比較簡單，不夠靈活

-消息

□具有靈活格式的通信單位

上再文囪尤孝

I共享存儲器通信

■線程同步

□給線程執(zhí)行順序施加約束的機制

□控制線程執(zhí)行的相對順序

□建立在互斥機制的基礎(chǔ)上

■互斥機制

□使得一次只有一個線程對共享變量進(jìn)行訪問

□以保證每個線程對于共享變量訪問的完整性

■常見的互斥機制

□鎖

□信號量

□臨界區(qū)

上再文囪尤孝

I共享存儲器通信

■鎖

□一種互斥變量

□一次只能被一個線程獲得

■信號量

□通過PV操作在線程間傳遞同步信息

■原子操作

□P操作將一個變量減1

■減后的變量小于0時線程被阻塞

□V操作將一個變量加1

■加后的變量大于或等于0時釋放一個線程

上再文囪尤孝

I共享存儲器通信

■臨界區(qū)

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

□進(jìn)入的線程數(shù)量是有限制的

□通常只允許一個線程進(jìn)入臨界區(qū)

□可以采用鎖機制來實現(xiàn)

上再文囪尤孝

I鎖

■兩個基本的原子操作

□Acquire

■原子地等待鎖的狀態(tài)變成打開的狀態(tài)

■將打開的鎖狀態(tài)變成關(guān)閉的狀態(tài)

□這時該線程獲得了鎖

□Release

■原子地將鎖的狀態(tài)從關(guān)閉狀態(tài)變成打開的狀態(tài)

□這時線程釋放了鎖

上再文囪尤孝

鎖的類型

■互斥量

□用PV操作上鎖和解鎖

□有阻塞

□可以加上時間屬性

■遞歸鎖

□可以遞歸地獲得的鎖

□用于遞歸程序

■讀寫鎖

□多讀單寫鎖

■限制寫操作只能由一個線程執(zhí)行

□用于對共享變量的讀寫操作

■自旋鎖

□非阻塞的鎖

□用于多處理機系統(tǒng)和多核系統(tǒng)

上再文囪尤孝

阻塞型鎖機制的問題

■優(yōu)先級的顛倒lorityinversion

□當(dāng)一個低優(yōu)先級的線程占用了一個鎖之后，需要同

一個鎖的高優(yōu)先級線程就只能等待。

■護(hù)航Convoying

□當(dāng)一個線程擁有一個鎖而被切換出去時其他的線程

如果需要同一個鎖的話都不能運行下去

□其他線程都圍著擁有鎖的線程團團轉(zhuǎn)

■死鎖adlock

□鎖的擁有和依賴關(guān)系形成一個環(huán)

上再文囪尤孝

死鎖及其解決

■死鎖的原因

□對資源（鎖）的訪問是獨占的

□線程在已經(jīng)持有一個資源時繼續(xù)請求其他資源

□所有線程都不放棄已經(jīng)持有的資源

□線程對資源的請求形成一個環(huán)

■解決方法

□復(fù)制需要獨占訪問的資源

□按照一定的順序獲取資源

■有序嵌套

□無法獲取其他資源時放棄已持有的資源

□調(diào)用構(gòu)件時避免使用鎖

上再文囪尤孝

信號

■硬件信號

□一種黏滯性的邏輯電平

■一旦被設(shè)置就一直保持不變

■直到被清除

□如訪存完成、cache失效、時鐘信號

□可以表示為一個寄存器變量

■對于信號變量的讀操作清除這個信號

■軟件信號

□表示為共享變量

□如進(jìn)程中止信號

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

■消息

□結(jié)點間通信的基本邏輯單位

□消息頭

■目標(biāo)結(jié)點號、源結(jié)點號、消息類型和消息長度等

□消息體

■通信數(shù)據(jù)

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

?1閂心、°?1口心、卜?in心、汽i

目標(biāo)結(jié)點號序號消息類型消息長度數(shù)據(jù)校驗和

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

■數(shù)據(jù)包?存儲轉(zhuǎn)發(fā)

□數(shù)據(jù)傳輸?shù)奈锢韱挝?store-and-forward

■尋徑信息?電路交換

■序號?circuitswitching

■數(shù)據(jù)內(nèi)容?虛擬切換

■校驗位?virtualcut-through

■協(xié)議號?蟲孔尋徑

■時間戳?wormhole

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

存儲轉(zhuǎn)發(fā)store?and?forward

■問題：延遲大，緩存多

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

電路交換circuitswitching

問題：沖突多，利用率低

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

虛擬切換virtualcut-through

上再文囪尤孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

蟲孔尋徑wormhole

問題：死鎖和活鎖

I互連網(wǎng)絡(luò)的消息傳遞通信方式

■蟲孔尋徑與存儲轉(zhuǎn)發(fā)的比較

Ni

N2

N4

結(jié)點"

日寸向

序列-(a)存儲轉(zhuǎn)發(fā):

結(jié)點

-寸奇

序列(b)蟲孑L尋徑13I

上再文EH孝

I互連網(wǎng)絡(luò)的消息傳遞通信方式

衡量指標(biāo)

□通信帶寬

□單位時間能夠傳輸?shù)臄?shù)據(jù)量

□取決于處理器的通信處理吞吐率、存儲器的吞吐率和互連網(wǎng)絡(luò)的傳

輸帶寬

■通信延遲

□發(fā)送的時間開銷

□信號傳輸時間

□傳輸持續(xù)時間

□接收方的時間開銷

■通信延遲隱藏能力

□通信時間與計算時間或者其他通信時間的重疊程度

上再文囪尤孝

I例6-2

■1個計算任務(wù)在單個核的計算機上運行的啟動時間為1

秒，運算時間為10秒，數(shù)據(jù)結(jié)果匯總的時間為1秒。

如果將該計算任務(wù)放在多核處理器的計算機上運行，

將運算部分分解成多個線程并行執(zhí)行。

■(D假如任務(wù)的啟動和數(shù)據(jù)匯總操作不能并行執(zhí)行,

運算部分可以進(jìn)行任意的任務(wù)分解，任務(wù)之間的通信

量可以忽略，也不考慮任務(wù)分解后存儲系統(tǒng)對性能的

影響。問在處理器核的數(shù)量分別為2、4、8、16時的

任務(wù)執(zhí)行時間和加速比。

■(2)上述情況下，假如每兩個處理器核之間的通信

時間為0.1秒，每對處理器核的通信串行進(jìn)行，問在

核的數(shù)量分別為2、4、8、16時的任務(wù)執(zhí)行時間和加

I解：（1）

任務(wù)在單個核的計算機上運行時間為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)

■任務(wù)在單個核的計算機上沒有通信時間，運行時間為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孝

習(xí)題

■6

6.2Cache與存儲器數(shù)據(jù)一致性

?共享存儲器多處理機系統(tǒng)的問題

□訪存沖突與數(shù)據(jù)一致性

□數(shù)據(jù)多個副本之間的相同性

CacheCacheMemorv■r

contentscontentsforcontentsfor

TimeEventforCPUACPUBlocationX

01

1CPUAreadsX11

2CPUBreadsX111

3CPUAstores0intoX010

上再文囪尤孝

數(shù)據(jù)一致性的實現(xiàn)

■軟件方法

□編譯分析

□避免cache共享數(shù)據(jù)

■總線監(jiān)測

□各cache設(shè)置監(jiān)測部件

■MESI協(xié)議

■目錄表法

□全映射

□有限目錄

□鏈?zhǔn)侥夸?/p>

■SCI

上再文囪尤孝

總線監(jiān)測

■所有cache不斷監(jiān)測總線上的每一個地址

□總線使得寫操作變成串行的

□Cache失效時需要確定數(shù)據(jù)塊的位置

■writeinvalidateprotocol

□invalidatesothercopiesonawrite.

■writeupdateorwritebroadcastprotocol

□updateallthecachedcopiesofadataitemwhenitiswritten

上再文aa孝

總線監(jiān)測

■寫無效方式

□多次寫操作時只需一次invalidate

□對于整個cache數(shù)據(jù)塊進(jìn)行

■寫更新方式

□對于數(shù)據(jù)塊中的個別字進(jìn)行

□讀操作的命中率高

□所有寫操作通過總線寫入所以相關(guān)的其他cache中

■寫操作的開銷較大

上再文囪尤孝

總線監(jiān)測

■每個處理器的cache中設(shè)置一個監(jiān)測部件

□監(jiān)測總線上的寫操作

□根據(jù)監(jiān)測的情況改變本地cache塊的狀態(tài)

■無效、修改、獨占、共享

■監(jiān)測條件

□主存中有一個單元被其他處理器所修改

□而這個單元在本地cache中也有一個副本

■對于寫更新方法

□擁有數(shù)據(jù)最新版本的cache需向其他cache提供數(shù)據(jù)塊內(nèi)容

□阻止其他處理器從共享存儲器的讀操作

上再文囪尤孝

MESJ協(xié)議

SHR

RH:讀命中

RMS:讀失效，共享

RME:讀失效，獨占

WH:寫命中

WM:寫失效

SHR:讀時檢測命中

SHW:寫時檢測命中或

旨在修改的讀

①濁行復(fù)制回來

RH

Q無效事務(wù)

十旨在修改的讀WH

J填充cache行

上再文囪尤孝

I例6.3

■設(shè)單總線連接的兩個CPU中采用MESI協(xié)議進(jìn)行一致性操作，初始

時某cache塊都在無效狀態(tài)，然后兩個CPU對該存儲塊分別進(jìn)行如

下操作：

■CPUA讀，CPUB讀，CPUA寫，CPUB讀，CPUB寫

■試寫出每次訪問后兩個塊的狀態(tài)變化情況。

事件狀態(tài)A狀態(tài)B說明

初始無效無效(I)數(shù)據(jù)未裝入

CPUA讀獨占無效(I)讀操作cache失效，裝入

CPUB讀共享共享(S)讀操作cache失效，裝入后共享

CPUA寫修改無效(I)寫操作命中

CPUB讀共享共享(S)讀操作失效，裝入

CPUB寫無效修改(M)寫操作命中

I例6.4

■在一個共享L2cache的雙核處理器芯片中，兩

個L1cache通過片內(nèi)總線與L2cache連接，并

采用MESI協(xié)議保持一致性。假設(shè)L1cache各

有4個塊，采用全相聯(lián)地址映像和LRU替換策

略，每個塊的初始狀態(tài)都是無效的。在以下讀

訪問塊地址序列下，試畫出兩個L1cache中塊

的分配情況，并標(biāo)出每個塊的狀態(tài)。

■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為系統(tǒng)中處理器的個數(shù)

□指示位段構(gòu)成一個位向量

■0表示相應(yīng)的處理器cache沒有該塊

■1表示有該塊

■有限目錄

□每個快表目錄項包含固定數(shù)量的指示位段

□指示位段的位數(shù)與處理器數(shù)量無關(guān)

■鏈?zhǔn)侥夸?/p>

上再文囪尤孝

I例6?5

■設(shè)4個CPU的并行計算機中采用全映射的目錄表法進(jìn)行一致性操作,

初始時某cache塊都在無效狀態(tài)，然后4個CPU對該存儲塊分別進(jìn)

行如下操作：

■CPU0讀，CPU1讀，CPU2讀，CPU1替換，CPUO寫

-試寫出每次訪問后該塊的有效指示位段的變化情況，假設(shè)一致性

操作采用寫無效策略。

事件指示狀態(tài)位段

初始0000

CPU0讀0001

CPU1讀0011

CPU2讀0111

CPU1替換0101

CPUO寫0001

上再文囪尤孝

I例6.6

■在一個由2個CPU構(gòu)成的并行計算機中采用全

映射的目錄表法進(jìn)行一致性操作。假設(shè)各CPU

的cache都只有4個塊，采用全相聯(lián)地址映像和

LRU替換策略，每個塊的初始狀態(tài)都是無效的。

在以下讀訪問塊地址序列下，試畫出兩個L1

cache中塊的分配情況，并標(biāo)出每個塊的指示

狀態(tài)位段。

■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孝

目錄表法

■鏈?zhǔn)侥夸?/p>

□將目錄分布到各

個cache頭項中間項中間項尾項

□每個cache的塊

表中只需存放一

個cache指針

□單鏈或雙鏈

□SCI

上再文囪尤孝

數(shù)據(jù)一致性對cache性能的影響

■影響cache性能的因素

□單個處理器cache失效的數(shù)據(jù)傳輸

□數(shù)據(jù)通信引起的傳輸

■導(dǎo)致invalidations和后繼cache失效

■一致性失效

/處理機數(shù)量

/Cache容量

/塊大小

上再文囪尤孝

數(shù)據(jù)一致性對cache性能的影響

一致性失效

■真共享失效truesharingmisses

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

□對共享數(shù)據(jù)的第一個寫操作引起invalidation

■偽共享失效fa/sesharingmisses

□由每個cache塊只有一個有效位引起

□一個塊中其他數(shù)據(jù)的寫操作引起cache塊讀操作的

失效

□Cache塊是共享的，但是數(shù)據(jù)字并沒有共享

數(shù)據(jù)一致性對cache性能的影響

■一致性失效的例子

□假定數(shù)據(jù)字x1和x2在同一個數(shù)據(jù)塊中

■數(shù)據(jù)塊在P1和P2之間共享

□假定以下事件序列

TimePlP2

1Writexl

2Readx2

3Writexl

4Wntex2

5Readx2

上再文囪尤孝

I存儲器數(shù)據(jù)的一致性

時間一致性(consistency)

□一個寫操作寫入共享存儲器中的數(shù)值什么時候能夠被讀到

■串行一致性

■弱化一致性

■處理機一致性

■松散一致性

上再文囪尤孝

I存儲器數(shù)據(jù)的一致性

串行一致性sequentialconsistency

■處理機P對于存儲單元x的寫操作之后進(jìn)行的讀操作，其

間如果沒有其它處理機對x進(jìn)行寫訪問，則總是返回由P

寫入的數(shù)值。

■在一個處理機P1對于單元X進(jìn)行寫操作之后，另一處理

機P2對于單元X的讀操作只要兩者足夠分離并且沒有其

它對于X的寫操作發(fā)生，就能夠返回P1寫入的數(shù)值。

■對于同一單元的寫操作是順序進(jìn)行的，即兩個處理機對

于相同單元進(jìn)行的寫操作的順序從任何處理機看都相同。

如果數(shù)值1和2依次寫入一個位置，處理機不可能先讀得

2,再讀得1。

I存儲器數(shù)據(jù)的一致性

■弱化一致性weakconsistency

□程序通過同步操作強調(diào)一致性，使得在這些同步點

上數(shù)據(jù)保持一致，而不要求數(shù)據(jù)隨時都是一致的。

■處理機一致性processorconsistency

□每個處理機發(fā)出的寫操作被其它處理機看到的都保

持原順序，但兩個不同處理機的寫操作順序可被其

他處理機以不同的順序看到。

■松散一致性releaseconsistency

□采用acquir一-r一1一as一同步操作使得數(shù)據(jù)保持一

致，從而減少對硬件一致性處理的要求。

SCI

■scalablecoherenceinterface

□IEEE1596-1992

■支持鏈?zhǔn)侥夸洷矸?/p>

□雙向鏈表

■采用雙向鏈路

■采用虛擬切換傳輸方式

-支持大規(guī)模并行系統(tǒng)

□不要求消息按順序提交

□使用64位固定長度地址的分布式存儲器的尋址方案

■高16位用于尋找結(jié)點

■低48位地址指定結(jié)點內(nèi)的存儲器地址

■采用16位差分ECL信號鏈路

□信號時鐘250MHz

□鏈路的數(shù)據(jù)傳輸帶寬為1GB/S

上再文囪尤孝

習(xí)題

■11

■12

■13

■14

6.3并行計算機的同步

■同步機制

□并行系統(tǒng)中保持各并行程序正確運行的控制機制

□建立在通信機制的基礎(chǔ)上

□需要采用的硬件提供的機制來實現(xiàn)

■硬件原語

上再文囪尤孝

硬件原語

■原子交換atomicexchange

□實現(xiàn)鎖

■測試并設(shè)置test?and?set

□實現(xiàn)鎖

■讀取并力口lfetch?and?inc「ement

□實現(xiàn)屏障

■讀取并更新test?and?update

□實現(xiàn)PV操作

上再文囪尤孝

原子交換

■將一個寄存器的數(shù)值與一個存儲器中的數(shù)值進(jìn)

行交換

■難以在并行機中實現(xiàn)

■要求存儲器讀寫操作在一條不可中斷的指令中完成

■硬件不能在讀寫操作之間響應(yīng)中斷

AB

上再文囪尤孝

原子交換

■解決方案

□用兩條指令實現(xiàn)

■鏈接裝載loadlinked

■條件存儲storeconditional

□返回一個數(shù)值

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

■兩條指令按順序執(zhí)行

□如果鏈接裝載指令指定的存儲單元在對應(yīng)的條件存儲指令執(zhí)

行之間被改變，則存儲指令執(zhí)行時失敗。

□如果處理機在這兩條指令之間進(jìn)行了上下文交換，則該條件

存儲指令也將失敗。

上再文囪尤孝

原子交換

原子交換的實現(xiàn)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派生原語

轉(zhuǎn)鎖spinlock

處理機用循環(huán)方法試圖得到的鎖

■沒有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派生原語

采用鏈接裝載/條件存儲實現(xiàn)轉(zhuǎn)鎖

lockit:11R2,0(RI);loadlinked

bn一zR2,lockit;notavailabl一一spin

liR2,#1;lockedvalue

scR2,0(RI);store

b一qzR2,lockit;branchifstorefailes

上再文aa孝

I派生原語

■屏障同步

□強制所有的線程等待

■直到所有的線程都到達(dá)屏障時釋放所有的線程

■用一個計數(shù)器對到達(dá)的線程計數(shù)（Ga加凹階段）

■用一個信號釋放所有的線程（re/ease階段）

□用兩個自旋鎖實現(xiàn)

■一個用于保護(hù)計數(shù)器

■一個用于鎖住線程

I派生原語

屏障同步的實現(xiàn)

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派生原語

■問題

□屏障可能循環(huán)使用

□從屏障離開的線程可能再次進(jìn)入屏障

□一個線程可能在另一個線程離開屏障之前又進(jìn)入屏

障

■代碼的bug

I派生原語

■解決方案

□對離開的線程計數(shù)

■不允許線程在其他線程都離開上一個屏障之前又進(jìn)入屏障

□從而又初始化屏障

□傳感反相屏障

-使用線程局部變量

□初始化為1

□交替地等待1和o

release-------------------------1?--------------------為/夭3rH孝

I派生原語

■屏障同步的實現(xiàn)

□傳感反相屏障

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*/

第一個到達(dá)屏障的線程并不改變release的值上再文囪尤孝

同步操作的性務(wù)邑問題

■Contentionforthelock

□Z⑵+1)=n2+2n

-鎖變量訪問的串行化

□大大增加完成同步操作的時間

■解決方案

□增量資源

■或分解資源

■如散列表的分割

□指數(shù)退避exponentialbackoff

■訪問等待時間以指數(shù)增加

■防止活鎖

□隊列鎖

■鎖變量釋放時通知下一個線程

□組合樹

■樹中每個結(jié)點組合k個線程的同步

■將對一個變量的競爭按樹形結(jié)構(gòu)分散

上再文囪尤孝

同步操作的性務(wù)邑問題

■指數(shù)等待

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

同步操作的性務(wù)邑問題

■組合樹

structnode{/*anodeinthecombiningtree*/

intcounterlock;/*lockforthisnode*/

intcount;/*counterforthisnode*/

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

）；

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

intlocal_sense;/*privateperprocessor*/

intrelease;/*globalreleaseflag*/

上再文aa孝

同步操作的性務(wù)邑問題

■組合樹

/*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事務(wù)存儲器

■同步機制的硬件解決方案

□非互鎖的機制

□使得系統(tǒng)能夠并行地執(zhí)行原子操作

■事務(wù)

□鎖的作用范圍

□每個事務(wù)由一個線程推測性地執(zhí)行而不請求鎖

□沒有遇到?jīng)_突時提交

■否則事務(wù)將放棄(abort)

■進(jìn)行卷回(rollback)并重新開始

□事務(wù)沒有成功提交之前不會對其它線程產(chǎn)生作用

上再文囪尤孝

I事務(wù)存儲器

■事務(wù)

□由線程中的一組指令構(gòu)成

□串行性

■從其他線程看來不會有不同的執(zhí)行順序

□原子性

■整體提交或者整體放棄

■提交之前對其它線程看不到

上再文囪尤孝

同步與多線程

多線程的程序的問題

■數(shù)據(jù)競爭

□由各線程對共享數(shù)據(jù)讀-寫訪問和寫-寫訪問順序的不確定性

弓起

■同步

□同步機制會帶來的開銷

■線程停頓

□一個鎖條解開使等待這個鎖的線程停頓

■死鎖

□線程的無限期的停頓現(xiàn)象

■偽共享

□①程之間的非真正的數(shù)據(jù)共享而引起的相關(guān)性

上再文囪尤孝

多線程的程序的問題

■數(shù)據(jù)競爭

□數(shù)據(jù)相關(guān)性險象

□以下兩個if語句的表達(dá)式可能都為真嗎?

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

A=1;B=1;

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

上再文aa孝

多線程的程序的問題

數(shù)據(jù)競爭之二

線程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

多線程的程序的問題

■數(shù)據(jù)競爭之三

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

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

上再文aa孝

數(shù)據(jù)競爭的解決

■變量局部化

□將變量改為線程局部的

□如將全局和分解為部分和

■用臨界區(qū)控制共享變量的訪問

□通過鎖、信號量等實現(xiàn)

□每個共享數(shù)據(jù)用一把鎖

■互斥機制

上再文囪尤孝

同步與多線程

■并行線程與臨界區(qū)I

□訪問共享數(shù)據(jù)的程序段

□在某段時間內(nèi)僅允許一定數(shù)目的線程訪問I",,

的一段代碼I

□大多數(shù)情況下一次只有一個線程能夠進(jìn)入同一個n

臨界區(qū)?

□可采用互斥機制實現(xiàn)?

上再文囪尤孝

同步與多線程

-并行線程與屏障

習(xí)題

■16

■18

■20

■21

■22

6.5并行計算機程序的軟件支持

并行程序的概念

□任務(wù)劃分

□將一個任務(wù)劃分成多個并行子任務(wù)

□使得處理器負(fù)載平衡

-數(shù)據(jù)劃分

□將數(shù)據(jù)對象劃分成多個并行子集

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

-數(shù)據(jù)流劃分

□根據(jù)數(shù)據(jù)處理的過程劃分

□一個子任務(wù)的輸出是另一個子任務(wù)的輸入

?劃分的目標(biāo)

?負(fù)載平衡

?降低調(diào)度開銷、通信開銷和同步開銷

上再文囪尤孝

并行程序的概念

■任務(wù)task

□應(yīng)用級的計算單位

■單任務(wù)線程

□為每個任務(wù)動態(tài)創(chuàng)建和終止

□創(chuàng)建和終止開銷問題

□大量線程時的開銷

■線程池

□預(yù)先創(chuàng)建的固定數(shù)量的線程

■與處理器數(shù)量匹配

□可完成多個任務(wù)

■應(yīng)用程序中動態(tài)任務(wù)分配和調(diào)度

■線程中任意時刻只能運行一個纖程

上再文囪尤孝

并行程序的概念

■線程化的優(yōu)點

□創(chuàng)建速度較進(jìn)程快

□資源利用率高

□便于數(shù)據(jù)共享

■線程化的缺點

□增加程序設(shè)計的復(fù)雜性

□程序調(diào)試較難

■數(shù)據(jù)競爭、同步、死鎖

上再文囪尤孝

多線程的執(zhí)行

■硬件多線程

□每個線程運行在不同邏輯處理器上

□優(yōu)先級相同

□硬件的通信開銷

□真正的并行執(zhí)行

■軟件多線程

□運行在同一個邏輯處理器上

□OS動態(tài)改變優(yōu)先級

□共享本地存儲器

■通信開銷小

■互斥容易解決

上再文囪尤孝

共享存儲器系統(tǒng)程序設(shè)計例子

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()函數(shù)是一個屏障同步函數(shù)。

上再文囪尤孝

分布消息傳遞型系統(tǒng)程序例子

■假設(shè)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任務(wù)劃分

■對數(shù)據(jù)進(jìn)行劃分

□使得不同的子任務(wù)對不同的數(shù)據(jù)子集進(jìn)行處理

■對計算過程中的步驟進(jìn)行

□使得每個線程具有不同的程序代碼

■任務(wù)分解的一般方法

□根據(jù)數(shù)據(jù)運算流程圖進(jìn)行

上再文囪尤孝

I例6-8

■對于數(shù)組運算

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

■其中，A、B、C和D都是具有〃個元素的數(shù)組，

試畫出其數(shù)據(jù)流程圖，指出兩種子任務(wù)劃分方

式。

上再文囪尤孝

I解

■橫向劃分

■縱向劃分

Cn

4

上再文囪尤孝

實現(xiàn)并行程序設(shè)計的方法

■庫函數(shù)

□在串行程序的標(biāo)準(zhǔn)庫的基礎(chǔ)上增加支持并行操作的函數(shù)

□如MPI的消息傳遞庫和POSIX的Pthread多線程庫

□容易實現(xiàn)（不需要改變編譯程序）

□程序中的并行性沒有經(jīng)過編譯程序的檢查、分析、優(yōu)化

■新的語言構(gòu)造

□程序設(shè)計語言中增加新的構(gòu)造語句

□如Fortran90中增力口了向量運算語句

□編譯程序可以進(jìn)行并行性檢查和優(yōu)化

□增加了編譯程序的復(fù)雜性。

■編譯指導(dǎo)

□在原有的語言中增加表達(dá)并行運算的編譯指導(dǎo)語句

□并行編譯程序跟據(jù)指導(dǎo)語句將代碼轉(zhuǎn)換成在并行代碼

□如OpenMP

□介于上述兩種方法之間

上再文囪尤孝

I線程操作函數(shù)

■線程的創(chuàng)建和消除

□分叉和匯集(fork-join)機制

■線程的啟動和終止

■線程同步機制的建立和刪除

■線程通信機制的建立和刪除

□如MPI

上再文囪尤孝

多線程并行程序設(shè)計方法

■將獨立的循環(huán)程序變成多線程

□并行執(zhí)行的線程可能改變相對執(zhí)行的進(jìn)度或順序

□要求