面向多核競(jìng)爭(zhēng)環(huán)境的多線程應(yīng)用優(yōu)化方法研究.pdf

1、隨著多核處理器的迅猛普及，計(jì)算機(jī)編程模式由傳統(tǒng)串行編程模式向線程級(jí)并行編程模式轉(zhuǎn)變，以發(fā)揮出與核數(shù)量的增長(zhǎng)相一致的實(shí)際效果。由于多核機(jī)器具有充足的計(jì)算資源和內(nèi)存容量，為了最大化資源的利用率，單臺(tái)多核機(jī)器往往并發(fā)運(yùn)行多個(gè)多線程應(yīng)用，或者被多個(gè)運(yùn)行多線程應(yīng)用的虛擬機(jī)所共享，使多線程應(yīng)用陷于CPU資源的競(jìng)爭(zhēng)。例如，VMware于2010年發(fā)表的研究成果表明，在云計(jì)算環(huán)境下，平均每個(gè)處理器核被4個(gè)虛擬CPU（Virtual CPU，VCPU）時(shí)

2、分復(fù)用。在這種多核競(jìng)爭(zhēng)環(huán)境下，多線程應(yīng)用中的無(wú)用線程（比如同步操作中的忙等線程）會(huì)浪費(fèi)原本可以分配給有用線程的CPU資源，嚴(yán)重影響應(yīng)用的性能。因此，如何有效地利用寶貴的CPU資源，是使多線程應(yīng)用在多核競(jìng)爭(zhēng)環(huán)境下高效執(zhí)行的關(guān)鍵問(wèn)題。
　　首先，大量多線程應(yīng)用是基于單個(gè)程序多數(shù)據(jù)（Single Program Multiple Data，SPMD）編程模型實(shí)現(xiàn)的。SPMD編程模型由計(jì)算階段和強(qiáng)制障礙（Barrier）同步通信交替組成。

3、因此，多線程應(yīng)用的性能很大程度上取決于Barrier同步延時(shí)。但是，在多應(yīng)用并發(fā)執(zhí)行的環(huán)境下，Barrier同步延時(shí)會(huì)被極大延長(zhǎng)。這是因?yàn)楫?dāng)前大多數(shù)操作系統(tǒng)無(wú)法感知到多線程應(yīng)用中的同步操作，以至于尚未到達(dá)Barrier同步點(diǎn)的線程沒(méi)有被及時(shí)調(diào)度。在Barrier同步期間，處于忙等狀態(tài)的線程可能會(huì)浪費(fèi)CPU資源；當(dāng)忙等線程被阻塞后，它們又可能將自己的CPU資源讓給其它應(yīng)用。這會(huì)極大地影響系統(tǒng)的整體吞吐量和公平性。為了解決這些問(wèn)題，一種多核

4、競(jìng)爭(zhēng)環(huán)境下的Barrier同步策略（代號(hào)為T(mén)idon）將等待線程的時(shí)間片捐獻(xiàn)給它們被搶占、落后的姊妹線程。其中，姊妹線程是指來(lái)自相同應(yīng)用的線程。在這種方式下，等待線程可以直接輔助同步操作的完成。實(shí)驗(yàn)結(jié)果表明，在多應(yīng)用并發(fā)執(zhí)行的環(huán)境下，Tidon能夠?yàn)锽arrier密集型應(yīng)用帶來(lái)最高17.9倍的性能加速，同時(shí)不損害甚至提升非Barrier密集型應(yīng)用的性能，從而保障并發(fā)應(yīng)用之間的性能公平性。此外，Tidon在虛擬化環(huán)境下同樣有效。
　

5、　其次，平衡線程間的任務(wù)量是保障多線程應(yīng)用高效運(yùn)行于多核平臺(tái)的重要手段。這是因?yàn)槎嗑€程應(yīng)用通常要等待所有線程完成分配的任務(wù)后，才算運(yùn)行完畢。任務(wù)竊?。╓ork-stealing）技術(shù)是廣泛用于動(dòng)態(tài)保障多線程應(yīng)用負(fù)載均衡的方法。但是，前人的工作證明，Work-stealing技術(shù)在諸如傳統(tǒng)多應(yīng)用并發(fā)和虛擬化環(huán)境這樣的競(jìng)爭(zhēng)環(huán)境下，存在效率低下的問(wèn)題。這是因?yàn)閃ork-stealing中的小偷線程會(huì)浪費(fèi)CPU資源。盡管目前存在優(yōu)化Work-s

6、tealing在傳統(tǒng)多應(yīng)用并發(fā)環(huán)境下性能的方法，但是尚未存在改善Work-stealing在虛擬化環(huán)境下性能的有效方法。虛擬化引入的語(yǔ)義鴻溝和兩層調(diào)度問(wèn)題，增加了虛擬化環(huán)境下Work-stealing優(yōu)化的困難。為此，一種虛擬化環(huán)境下面向Work-stealing的性能優(yōu)化方法（代號(hào)為Robinhood）在客戶操作系統(tǒng)和虛擬機(jī)監(jiān)控器這兩個(gè)層面，利用小偷線程的CPU資源來(lái)加速有用線程的執(zhí)行進(jìn)度，以致于減少應(yīng)用的執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，與C

7、ilk++和BWS（Balanced Work Stealing）相比，Robinhood能夠分別為Work-stealing帶來(lái)最高90％和72%的性能提升。
　　最后，數(shù)據(jù)并行應(yīng)用是云計(jì)算環(huán)境下的典型應(yīng)用。多核平臺(tái)強(qiáng)大的處理能力和迅猛的發(fā)展趨勢(shì)使其在數(shù)據(jù)并行應(yīng)用領(lǐng)域有著極為廣闊的前景。MapReduce作為最初針對(duì)集群平臺(tái)設(shè)計(jì)和實(shí)現(xiàn)的數(shù)據(jù)并行編程模型，亦被許多研究者證明可作為單機(jī)多核環(huán)境下易用、高性能的并行編程模型。與此同時(shí)，

8、隨著云計(jì)算環(huán)境下運(yùn)行于單機(jī)多核平臺(tái)的虛擬機(jī)數(shù)量不斷增加，CPU資源變得越來(lái)越寶貴。但是，現(xiàn)有單機(jī)多核平臺(tái)上的MapReduce系統(tǒng)更多的關(guān)注于通用性而缺乏針對(duì)性，使其在某些應(yīng)用領(lǐng)域和計(jì)算需求下會(huì)產(chǎn)生不必要的開(kāi)銷，以至于浪費(fèi)CPU資源。為此，一種面向單機(jī)多核平臺(tái)的可定制MapReduce系統(tǒng)（代號(hào)為Peacock）通過(guò)建立一種應(yīng)用分類模型，將基于MapReduce的多線程應(yīng)用劃分為四種不同的類型，并為不同類型的應(yīng)用定制高效的執(zhí)行流程，從根