<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
多核編程中的鎖競(jìng)爭(zhēng)現(xiàn)象
在前一篇講解多核編程的幾個(gè)難題及其對(duì)策(難題一)的文章中提到了鎖競(jìng)爭(zhēng)會(huì)讓串行化隨CPU的核數(shù)增多而加劇的現(xiàn)象,這篇文章就來(lái)對(duì)多核編程的鎖競(jìng)爭(zhēng)進(jìn)行深入的分析。
為了簡(jiǎn)化起見(jiàn),我們先看一個(gè)簡(jiǎn)單的情況,假設(shè)有4個(gè)對(duì)等的任務(wù)同時(shí)啟動(dòng)運(yùn)行,假設(shè)每個(gè)任務(wù)剛開(kāi)始時(shí)有一個(gè)需要鎖保護(hù)的操作,耗時(shí)為1,每個(gè)任務(wù)其他部分的耗時(shí)為25。這幾個(gè)任務(wù)啟動(dòng)運(yùn)行后的運(yùn)行情況如下圖所示:
圖1:對(duì)等任務(wù)的鎖競(jìng)爭(zhēng)示意圖
在上圖中,可以看出第1個(gè)任務(wù)直接執(zhí)行到結(jié)束,中間沒(méi)有等待,第2個(gè)任務(wù)等待了1個(gè)時(shí)間單位,第3個(gè)任務(wù)等待了2個(gè)時(shí)間單位,第3個(gè)任務(wù)等待了3個(gè)時(shí)間單位。
這樣有3個(gè)CPU總計(jì)等待了6個(gè)時(shí)間單位,如果這幾個(gè)任務(wù)是采用OpenMP里的所有任務(wù)都在同一點(diǎn)上進(jìn)行等待到全部任務(wù)執(zhí)行完再向下執(zhí)行時(shí),那么總的運(yùn)行時(shí)間將和第四個(gè)任務(wù)一樣為29個(gè)時(shí)間單位,加速系數(shù)為:(1+4×25)/ 29 = 3.48
即使以4個(gè)任務(wù)的平均時(shí)間27.5來(lái)進(jìn)行計(jì)算,加速系數(shù)=101/27.5 = 3.67
按照阿姆爾達(dá)定律來(lái)計(jì)算加速系數(shù)的話,上述應(yīng)用中,串行時(shí)間為1,并行處理的總時(shí)間轉(zhuǎn)化為串行后為100個(gè)時(shí)間單位,如果放在4核CPU上運(yùn)行的話,加速系數(shù)=p / (1 + (p-1)*f) = 4/(1+(4-1)*1/101) = 404/104 = 3.88
這就產(chǎn)生了一個(gè)奇怪的問(wèn)題,使用了鎖之后,加速系數(shù)連阿姆爾達(dá)定律計(jì)算出來(lái)的加速系數(shù)都不如,更別說(shuō)用
Gustafson
定律計(jì)算的加速系數(shù)了。
其實(shí)可以將上面
4
個(gè)任務(wù)的鎖競(jìng)爭(zhēng)情況推廣到更一般的情況,假設(shè)有鎖保護(hù)的串行化時(shí)間為
1
,可并行化部分在單核
CPU
上的運(yùn)行時(shí)間為
t
,
CPU
核數(shù)為
p
,那么在
p
個(gè)對(duì)成任務(wù)同時(shí)運(yùn)行情況下,鎖競(jìng)爭(zhēng)導(dǎo)致的總等待時(shí)間為:
1
+
2
+
…
+
p
=
p*(p-1)/2
耗時(shí)最多的一個(gè)任務(wù)所用時(shí)間為:
p + t/p
使用耗時(shí)最多的一個(gè)任務(wù)所用時(shí)間來(lái)當(dāng)作并行運(yùn)行時(shí)間的話,加速系數(shù)如下
S(p) = (t+1) / (p + t/p) = p*(t+1) / (p*p+t)
(鎖競(jìng)爭(zhēng)下的加速系數(shù)公式)
這個(gè)公式表明在有鎖競(jìng)爭(zhēng)情況下,如果核數(shù)固定情況下,可并行化部分越大,那么加速系數(shù)將越大。在并行化時(shí)間固定的情況下,如果
CPU
核數(shù)越多,那么加速系數(shù)將越小。
還是計(jì)算幾個(gè)實(shí)際的例子來(lái)說(shuō)明上面公式的效果:
令
t=100, p=4,
加速系數(shù)=
4
×(
100 +1)/ (4*4+100) = 3.48
令
t=100, p=16,
加速系數(shù)=
16
×(
100+1) / (16*16+100) = 4.54
令
t=100, p=64,
加速系數(shù)=
64
×(
100+1) / (64*64+100) = 1.54
令
t=100, p=128,
加速系數(shù)=
128
×(
100+1) / (128*128+100) = 0.78
從以上計(jì)算可以看出,當(dāng)核數(shù)多到一定的時(shí)候,加速系數(shù)不僅不增加反而下降,核數(shù)增加到
128
時(shí),加速系數(shù)只有
0.78
,還不如在單核
CPU
上運(yùn)行的速度。
上面的例子中,鎖保護(hù)導(dǎo)致的串行代碼是在任務(wù)啟動(dòng)時(shí)調(diào)用的,其實(shí)對(duì)等任務(wù)中在其他地方調(diào)用的鎖保護(hù)的串行代碼也是一樣的。
對(duì)等型任務(wù)的鎖競(jìng)爭(zhēng)現(xiàn)象在實(shí)際情況中是很常見(jiàn)的,比如服務(wù)器軟件,通常各個(gè)客戶端處理任務(wù)都是對(duì)等的,如果在里面使用了鎖的話,那么很容易造成上面說(shuō)的加速系數(shù)隨
CPU
核數(shù)增多而下降的現(xiàn)象。
以前的服務(wù)器軟件一般運(yùn)行在雙
CPU
或四
CPU
機(jī)器上,所以鎖競(jìng)爭(zhēng)導(dǎo)致的加速系數(shù)下降現(xiàn)象不明顯,進(jìn)入多核時(shí)代后,隨著
CPU
核數(shù)的增多,這個(gè)問(wèn)題將變得很嚴(yán)重,所以多核時(shí)代對(duì)程序設(shè)計(jì)提出了新的挑戰(zhàn)。以前的多任務(wù)下的編程思想放到多核編程上不一定行得通。
所以簡(jiǎn)單地認(rèn)為多核編程和以前的多任務(wù)編程或并行計(jì)算等同的話是不切實(shí)際的,在講串行化難題的那篇文章中提出了一些解決方面的對(duì)策,但是那些對(duì)策還有待業(yè)界繼續(xù)努力才能做得到。
當(dāng)然由于目前市面上銷售的多核CPU還是雙核和四核的,等到16核以上的CPU大規(guī)模進(jìn)入市場(chǎng)可能還有幾年時(shí)間,相信業(yè)界在未來(lái)的幾年內(nèi)能夠?qū)τ谏厦鎸?duì)等任務(wù)上的鎖競(jìng)爭(zhēng)問(wèn)題找到更好的解決方案。
作者介紹:
周偉明,自由職業(yè),從事軟件行業(yè)十年有余。目前主要關(guān)注軟件測(cè)試、多核編程、軟件設(shè)計(jì)等基礎(chǔ)方面的內(nèi)容。寫有《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》一書(shū),目前正在寫作《軟件測(cè)試實(shí)踐》一書(shū),計(jì)劃在不久的將來(lái)寫一本多核編程方面的書(shū)籍。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1559718