并行區(qū)重構(gòu)

OpenMP是一種用于共享內(nèi)存并行編程的多線程程序設(shè)計方案，適合在共享內(nèi)存編程下的多核系統(tǒng)上進(jìn)行并行程序設(shè)計。程序員在完成程序功能開發(fā)的基礎(chǔ)上，只需添加指導(dǎo)語句#pragma即可自動將串行執(zhí)行轉(zhuǎn)換為并行處理，當(dāng)編譯器不支持OpenMP時，程序會忽略#pragma語句，按照串行順序執(zhí)行。OpenMP的使用降低了多核并行編程的難度，優(yōu)化人員可以更多地考慮算法本身，而非具體的并行實(shí)現(xiàn)細(xì)節(jié)。

OpenMP Fork-Join模式程序運(yùn)行過程中線程的創(chuàng)建和合并比較頻繁，在并行性表達(dá)上處于一種低效狀態(tài)。并行區(qū)重構(gòu)是結(jié)合數(shù)據(jù)和計算劃分等信息，通過改變原并行區(qū)的結(jié)構(gòu)，降低串并行程序之間切換以及其他開銷。并行區(qū)重構(gòu)包括并行區(qū)擴(kuò)張和并行區(qū)合并兩種方式。

并行區(qū)擴(kuò)張

循環(huán)結(jié)構(gòu)并行區(qū)擴(kuò)張針對的是包含整個循環(huán)結(jié)構(gòu)的并行區(qū)，將此并行區(qū)擴(kuò)張到循環(huán)之外，若該循環(huán)迭代次數(shù)為N，則并行區(qū)擴(kuò)張后線程的創(chuàng)建和合并次數(shù)將減少N-1次。

并行區(qū)擴(kuò)張后j層循環(huán)對應(yīng)的并行區(qū)擴(kuò)張到i層循環(huán)之外，并行區(qū)構(gòu)建和合并由擴(kuò)張前的2000次減少為擴(kuò)張之后的1次，減少了1999次。對并行區(qū)擴(kuò)張前后的代碼進(jìn)行測試后結(jié)果如下，計算對比發(fā)現(xiàn)并行區(qū)擴(kuò)張后加速比達(dá)到了1.38，進(jìn)一步提升了程序的性能。

函數(shù)結(jié)構(gòu)并行區(qū)擴(kuò)張是指將函數(shù)結(jié)構(gòu)內(nèi)部的并行區(qū)擴(kuò)張到整個函數(shù)結(jié)構(gòu)的外部，并行區(qū)擴(kuò)張后能夠?qū)⒑瘮?shù)結(jié)構(gòu)內(nèi)部的全部語句包含在并行區(qū)中，進(jìn)一步獲得更多的并行區(qū)合并機(jī)會。函數(shù)結(jié)構(gòu)并行區(qū)擴(kuò)張可以改善程序的并行結(jié)構(gòu)，增大并行計算的粒度。但是函數(shù)結(jié)構(gòu)并行區(qū)擴(kuò)張會徹底改變線程的堆棧結(jié)構(gòu)，而且這種做法隱含著對函數(shù)結(jié)構(gòu)內(nèi)局部變量的數(shù)據(jù)屬性進(jìn)行私有化處理。為了保證并行區(qū)擴(kuò)張不修改原程序語義，必須保證函數(shù)結(jié)構(gòu)內(nèi)局部變量私有化的合法性，因此函數(shù)結(jié)構(gòu)并行區(qū)擴(kuò)張要求優(yōu)化人員清楚地理解函數(shù)的實(shí)現(xiàn)細(xì)節(jié)。

并行區(qū)合并

并行區(qū)合并不僅僅是將原有程序的多個并行區(qū)改寫至一個#pragma omp parallel區(qū)域，往往還需要考慮到并行區(qū)合并是否會修改原程序語義等問題。

為了確保并行區(qū)合并不修改原程序語義，就需要保證合并后各個子線程間數(shù)據(jù)更新順序和執(zhí)行順序與原程序保持一致性，前者可以通過指導(dǎo)語句flush來實(shí)現(xiàn)，后者可以通過指導(dǎo)語句barrier進(jìn)行同步來實(shí)現(xiàn)。

除此之外，還需要考慮合并過程中的變量數(shù)據(jù)屬性沖突以及并行區(qū)之間串行語句的處理等問題。

并行區(qū)合并操作經(jīng)常會遇到變量的數(shù)據(jù)屬性沖突問題，并行區(qū)1中聲明k為共享變量，并行區(qū)2中聲明k為私有變量，變量k存在數(shù)據(jù)屬性沖突問題將導(dǎo)致并行區(qū)1和2無法直接進(jìn)行合并。

針對這一問題，可以采用子句firstprivate修改共享變量的數(shù)據(jù)屬性后再合并。子句firstprivate將其參數(shù)列表中的變量屬性聲明為私有變量，并在每個線程創(chuàng)建私有變量副本時，初始化私有變量副本的值，使其與進(jìn)入并行區(qū)前串行區(qū)內(nèi)同名變量的值一致。由于代碼共享變量k在并行區(qū)1中引用，而k已經(jīng)在并行區(qū)1先前的程序段中被初始化，因此在并行區(qū)1需要對變量k進(jìn)行私有化處理，在引用前將初始化值傳入到并行區(qū)1中，可以使用firstprivate子句來實(shí)現(xiàn)，然后再將兩個并行區(qū)進(jìn)行合并。

在實(shí)際開發(fā)過程中建議盡可能合并小的并行區(qū)，當(dāng)達(dá)到一定數(shù)量時會帶來程序性能提升。此外需要注意對變量進(jìn)行私有化處理會屏蔽掉并行區(qū)中變量原有的初始化值，程序之間的引用關(guān)系有可能會改變。因此為了維持共享變量私有化之前程序之間的關(guān)系，需要保證進(jìn)行私有化處理的共享變量在并行區(qū)中沒有被初始化。

并行區(qū)合并后如代碼中，變量k為私有變量，其值在每個線程上都需要加1，因此不需要添加指導(dǎo)語句，由于sum2賦初值只需要執(zhí)行一次，添加指導(dǎo)語句single更為合適，最后的printf打印語句，添加指導(dǎo)語句master處理。