第十一章 同步與OpenMP內(nèi)存模型

內(nèi)存一致性模型

OpenMP線程在共享內(nèi)存中執(zhí)行,共享內(nèi)存是組中所有線程都可以訪問的地址空間,其中存儲(chǔ)著變量.使共享內(nèi)存系統(tǒng)高效運(yùn)行的唯一方法是允許線程保持一個(gè)臨時(shí)的內(nèi)存視圖,該視圖駐留在處理器和內(nèi)存RAM之間的內(nèi)存結(jié)構(gòu)中.

當(dāng)線程通過共享內(nèi)存中的變量進(jìn)行交互時(shí),線程必須使它們對(duì)內(nèi)存的臨時(shí)試圖與共享視圖一致.線程通過 flush構(gòu)造 來(lái)實(shí)現(xiàn)這點(diǎn).

沖刷集(flush-set) 是應(yīng)用于沖刷的共享變量的集合.默認(rèn)情況下,沖刷集是線程可用的所有共享變量.

• 進(jìn)行顯式?jīng)_刷的構(gòu)造:

#pragma omp flush [(flush-set)]

除了解決內(nèi)存一致性的問題,沖刷還和管理編譯器何時(shí)可以重新排序指令的規(guī)則進(jìn)行交互.如果指令使用了沖刷集的變量,編譯器是不允許圍繞沖刷來(lái)重新排序指令的.

• sequenced-before關(guān)系:
  單個(gè)線程執(zhí)行的事件之間的偏序.A排序在B之前,則A sequenced-before B.

順序點(diǎn)(sequenced point): 程序執(zhí)行中的點(diǎn),在此處所涉及的有關(guān)語(yǔ)句以及與語(yǔ)句相關(guān)的任何附帶后果均已完成.如果A的評(píng)估(包括A所隱含的任何附帶后果)在B的執(zhí)行之前完成,那么我們說(shuō)A被排序在B之前.

常見的順序點(diǎn):

• 一個(gè)完整表達(dá)式的結(jié)束.包括if,while,for和return等.
• 在邏輯運(yùn)算符,條件運(yùn)算符以及逗號(hào)運(yùn)算符處.
• 在函數(shù)調(diào)用時(shí),所有參數(shù)的評(píng)估之后,但在調(diào)用前.
• 在函數(shù)返回之前.

事實(shí)上對(duì)于程序中順序點(diǎn)的排序,我們有三種情況:

• sequenced-before:順序點(diǎn)之間的關(guān)系是一個(gè)順序點(diǎn)接著另一個(gè)順序點(diǎn).舉例:

int a=1,b=2;
//由于賦值操作和逗號(hào)運(yùn)算符為順序點(diǎn),所以該式為順序點(diǎn)
//由于逗號(hào)運(yùn)算符有順序,因而兩個(gè)順序點(diǎn)之間有sequenced-before關(guān)系

• indeterminately sequenced:順序點(diǎn)之間的關(guān)系是,它們以某種順序執(zhí)行,但這個(gè)順序沒有被定義.例如:

c = func(a)+func(b);
//由于函數(shù)調(diào)用與賦值為順序點(diǎn),但是加法不為順序點(diǎn),所以func(a)與func(b)之間順序不確定
//所以在func(a)+func(b)中,兩個(gè)順序點(diǎn)之間順序不確定,存在indeterminately sequenced關(guān)系

• unsequenced:當(dāng)順序點(diǎn)發(fā)生沖突并導(dǎo)致未定義的結(jié)果時(shí),該情況成立.例如:

a=a++;
//由于賦值為順序點(diǎn),完整的表達(dá)式為一個(gè)順序點(diǎn),對(duì)a的增量操作與加法卻不是
//子表達(dá)式是無(wú)序的,對(duì)a的賦值與增量操作可能沖突,存在unsequenced關(guān)系

而對(duì)于單個(gè)線程,有一種happens-before關(guān)系直接沿用了sequenced-before關(guān)系的概念.

• happens-before:如果事件A是排序在事件B之前的.那么就說(shuō):A happens-befor B.

為了定義多個(gè)線程之間的happens-before關(guān)系,我們必須同步線程,于是我們將同步視為兩個(gè)或多個(gè)線程之間的特定事件.我們通過一個(gè)synchronized-with關(guān)系來(lái)實(shí)現(xiàn).

• synchronized-with:當(dāng)線程圍繞一個(gè)事件協(xié)調(diào)執(zhí)行,以定義其執(zhí)行的順序約束時(shí),synchronized-with關(guān)系在線程之間成立.可以將線程的執(zhí)行看作是一個(gè)事件序列,將每個(gè)事件看作是一個(gè)順序點(diǎn).

線程中事件的同步用$\leftrightarrow$表示.

成對(duì)同步

在前面的第八章中,我們注意到OpenMP通用核心中并不支持成對(duì)的或點(diǎn)對(duì)點(diǎn)(point-to-point)的同步.我們將考慮通過 生產(chǎn)者-消費(fèi)者模式 來(lái)推動(dòng)這一討論,這是并行計(jì)算中常用的模式.

在該模式下,生產(chǎn)者進(jìn)行一些工作以產(chǎn)生一些結(jié)果;消費(fèi)者等待生產(chǎn)者完成工作,然后消費(fèi)結(jié)果.將這兩個(gè)步驟之間的處理序列化在流水線中十分常見.

流水線并行 中,將生產(chǎn)者與消費(fèi)者步驟顯示為兩個(gè)線性序列:一個(gè)線程用于運(yùn)行生產(chǎn)者任務(wù),另一個(gè)線程用于運(yùn)行消費(fèi)者任務(wù),只要流水線階段的數(shù)量足夠大,這些流水線并行程序的性能就會(huì)不錯(cuò).

先觀察下面這樣的一個(gè)生產(chǎn)者-消費(fèi)者模式程序:

bool flag=false;
#pragma omp parallel shared(A,B,flag)
{
    int id = omp_get_thread_num();
    int nthrds = omp_get_num_threads();

    if((id==0)&&(nthrds<2))
        exit(-1);

    if(id==0){//生產(chǎn)者
        produce(A);
        flag=true;
    }
    if(id==1){//消費(fèi)者
        while(!flag)
            //自旋鎖(spin mutex)結(jié)構(gòu)
        consume(A);
    }
}

該程序邏輯上是正確的,但是實(shí)際上卻是錯(cuò)誤的.

在并行中,同步 有兩個(gè)方面: 數(shù)據(jù)同步 和 線程同步.

對(duì)于 數(shù)據(jù)同步 ,我們需要兩個(gè)線程在內(nèi)存中看到同一個(gè)變量的一致值.我們通過 完全沖刷 實(shí)現(xiàn).

在OpenMP通用核心中,以下幾點(diǎn)都隱含了沖刷:

• 當(dāng)一個(gè)新的線程組被parallel構(gòu)造fork時(shí).
• 當(dāng)一個(gè)critical構(gòu)造被線程加入時(shí).
• 當(dāng)一個(gè)線程完成一個(gè)critical構(gòu)造并退出臨界區(qū)時(shí).
• 進(jìn)入task區(qū)域時(shí).
• 從task區(qū)域退出時(shí).
• 在退出taskwait時(shí).
• 在退出顯式barrier構(gòu)造時(shí).
• 在退出隱式柵欄構(gòu)造時(shí).(無(wú)nowait)

對(duì)于 線程同步 ,我們需要在兩個(gè)線程之間建立synchronized-with關(guān)系.我們通過 自旋鎖 實(shí)現(xiàn).

于是,在調(diào)整后,我們得到了下面的又一個(gè)邏輯上似乎沒有錯(cuò)誤的程序:

int flag=0;
omp_set_num_threads(2);

#pragma omp parallel shared(A,flag)
{
    int id = omp_get_thread_num();
    int nthrds = omp_get_num_threads();

    if((id==0)&&(nthrds<2))
        exit(-1);

    if(id==0){
        produce(A);
        #pragma omp flush
        flag = 1;
        #pragma omp flush(flag);
    }

    if(id==1){
        #pragma omp flush(flag)
        while(flag==0)
            #pragma omp flush(flag)
        #pragma omp flush
        consume(A);
    }
}

然而這個(gè)程序?qū)嶋H上仍然是錯(cuò)誤的.

與現(xiàn)代程序設(shè)計(jì)語(yǔ)言一致, 只有通過原子操作才能建立synchronized-with關(guān)系 .而將flag設(shè)置為1及將其加載到內(nèi)存中都不是原子操作,存在數(shù)據(jù)競(jìng)爭(zhēng).

于是為了使得這個(gè)程序真正正確,關(guān)鍵是需要修改自旋鎖,以便通過原子加載和存儲(chǔ)操作建立synchronized-with關(guān)系.

首先,對(duì)于生產(chǎn)者,將flag變量的賦值放在一個(gè)atomic write構(gòu)造中.

然后,對(duì)于消費(fèi)者,先把while循環(huán)變成一個(gè)無(wú)限循環(huán),再為了避免變量flag上的任何讀寫沖突,將值存儲(chǔ)到一個(gè)臨時(shí)的flag變量中,并測(cè)試該變量的值來(lái)決定何時(shí)脫離循環(huán).

最終,我們得到一個(gè)如下的程序:

int flag=0;
omp_set_num_threads(2);

#pragma omp parallel shared(A,flag)
{
    int id = omp_get_thread_num();
    int nthrds = omp_get_num_threads();

    if((id==0)&&(nthrds<2))
        exit(-1);

    if(id==0){
        produce(A);
        #pragma omp flush
        #pragma atomic write
        flag = 1;
    }

    if(id==1){
        while(1){
            #pragma omp atomic read
                flag_temp=flag;
            if(flag_temp!=0)
                break;
        }
        #pragma omp flush
        consume(A);
    }
}

鎖(mutex)及其使用

OpenMP的鎖與pthreads的鎖功能基本相同,它是用來(lái)圍繞互斥建立同步協(xié)議的.

與critical構(gòu)造不同,OpenMP的鎖是作為庫(kù)例程來(lái)實(shí)現(xiàn)的. 在使用鎖之前必須對(duì)其進(jìn)行初始化.

• 使用鎖來(lái)保證互斥:

omp_lock_t lck;
omp_init_lock(&lck);

#pragma parallel shared(lck)
{
    omp_set_lock(&lck);
    //...do somethine
    omp_unset_lock(&lck);
}
omp_destroy_lock(&lck);

鎖的設(shè)置和解除設(shè)置意味著一次沖刷,它們隱含著所需的內(nèi)存移動(dòng),用相互排斥功能來(lái)支持內(nèi)存一致性.

當(dāng)設(shè)置鎖時(shí),意味著一次沖刷,這樣線程更新的值與內(nèi)存中的值一致;當(dāng)解鎖時(shí),值會(huì)被沖刷,所以當(dāng)下一個(gè)線程抓取鎖更新值時(shí),它將看到正確的值.

C++內(nèi)存模型與OpenMP

C++11定義了原子操作,用于定義synchronized-with關(guān)系.

C++中最常用的內(nèi)存順序包括以下幾種:

• seq_cst:對(duì)所有線程來(lái)說(shuō),內(nèi)存的加載和存儲(chǔ)將以相同的順序發(fā)生.這個(gè)順序?qū)⑹撬芯€程上執(zhí)行的任何語(yǔ)義上有效的指令交叉.
• release:在釋放操作R之前順序的存儲(chǔ)操作不得重新排序?yàn)槌霈F(xiàn)R之后.
• acquire:在獲取A之后順序的加載操作不得重新排序,使得其看起來(lái)發(fā)生在A后.
• acquire_release:圍繞一個(gè)acquire_release操作,加載和存儲(chǔ)操作不能重新排序.