虛擬內(nèi)存密集型多線程程序的性能改進(jìn)方法

陳健康,張 昱

(中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230027)

1 引 言

隨著多核處理器越來(lái)越普及,基于共享內(nèi)存的多線程程序被大量地開發(fā)出來(lái).其中,虛擬內(nèi)存密集型多線程程序作為常見的一類多線程應(yīng)用而大量存在;主要特征是存在大量而且頻繁的地址空間操作[1].這些地址空間操作主要包括page faults 和 mmap、munmap等系統(tǒng)調(diào)用.由于多線程共享地址空間,為了保證這些并發(fā)地址空間操作的正確性,Linux系統(tǒng)使用一個(gè)全局讀寫鎖(mmap_sem)來(lái)同步這些操作.然而,mmap_sem會(huì)串行化page faults 和內(nèi)存映射操作.對(duì)于虛擬內(nèi)存密集型程序,在高并發(fā)時(shí),線程串行執(zhí)行地址空間操作將會(huì)導(dǎo)致這類程序性能下降.

目前,一種比較好的解決方案是使用更加高效的鎖來(lái)替換該全局讀寫鎖.Clements等人就使用了并發(fā)性更加好的Read-Copy-Update(RCU)鎖來(lái)替換該讀寫鎖[1],但是這種解決方案并不能完全消除應(yīng)用的地址空間競(jìng)爭(zhēng).另外一些解決方案是將具有共享地址空間的多線程修改為具有私有地址空間的多進(jìn)程,例如Psearch(來(lái)自MOSBENCH[2]的應(yīng)用),但是將應(yīng)用從多線程修改為多進(jìn)程通常是比較困難的.

本文提出了一個(gè)性能和擴(kuò)展性較好的線程模型PMthreads.PMthreads采用線程地址空間隔離的策略,能夠完全消除多線程競(jìng)爭(zhēng)mmap_sem.然而,線程地址空間隔離卻引起了如下三個(gè)問(wèn)題:無(wú)法保持共享變量、現(xiàn)有堆分配器無(wú)法適用、無(wú)法直接支持Pthreads接口.通過(guò)自定義字符設(shè)備驅(qū)動(dòng)輕量級(jí)更改Linux內(nèi)核中進(jìn)程全局?jǐn)?shù)據(jù)區(qū)域,PMthreads保持線程共享全局變量;通過(guò)設(shè)計(jì)實(shí)現(xiàn)IAmalloc堆分配器,PMthreads保持了堆變量的共享并且避免分配上的競(jìng)爭(zhēng);通過(guò)在隔離棧空間的線程模型上實(shí)現(xiàn)同步算法并支持Pthreads接口,Pthreads程序可以無(wú)修改的使用PMthreads.

在32核機(jī)器上,本文使用PARSEC[3]和Phoenix[4]中的5個(gè)程序,來(lái)評(píng)測(cè)PMthreads和Pthreads的性能和可擴(kuò)展性,其中包括兩個(gè)虛擬內(nèi)存密集型程序:histogram以及dedup.

本文主要貢獻(xiàn)如下:

· 詳細(xì)分析了虛擬內(nèi)存密集型多線程程序在共享地址空間上存在性能瓶頸的原因.

· 提出了一個(gè)基于隔離地址空間的線程模型,可以完全消除線程在mmap_sem上的競(jìng)爭(zhēng),同時(shí)可以保持線程共享變量.

· 實(shí)現(xiàn)了原型系統(tǒng)PMthreads:以自定義字符設(shè)備驅(qū)動(dòng)輕量級(jí)修改Linux內(nèi)核中進(jìn)程的全局?jǐn)?shù)據(jù)區(qū)域來(lái)保持線程共享變量;以設(shè)計(jì)和實(shí)現(xiàn)IAmalloc堆分配器來(lái)保持共享堆變量的分配和釋放;以實(shí)現(xiàn)同步算法并支持Pthreads接口,Pthreads多線程應(yīng)用可以無(wú)修改地調(diào)用PMthreads.

· 使用了5個(gè)應(yīng)用評(píng)估比較PMthreads和Pthreads的性能.對(duì)于虛擬內(nèi)存密集型應(yīng)用histogram和dedup,實(shí)驗(yàn)結(jié)果表明,在32線程時(shí)PMthreads相對(duì)于Pthreads性能提升了2.17倍和3.19倍;在16線程時(shí),非此類應(yīng)用的linear_regression也因削減假共享獲得8.15倍性能提升.

本文其余部分的組織如下:第2節(jié)是問(wèn)題分析與基本知識(shí);第3節(jié)是線程模型特征介紹.第4節(jié)是相關(guān)難點(diǎn)的實(shí)現(xiàn).第5節(jié)是實(shí)驗(yàn)和分析.第6節(jié)將會(huì)對(duì)全文進(jìn)行總結(jié).

2 基本知識(shí)與問(wèn)題分析

2.1 Linux地址空間組織

Linux中多線程共享父進(jìn)程的地址空間.進(jìn)程的地址空間主要是由大量的內(nèi)存映射區(qū)域組成,例如棧區(qū)域、代碼段區(qū)域等.Linux內(nèi)核以一個(gè)稱之為內(nèi)存描述符的數(shù)據(jù)結(jié)構(gòu)(mm_struct)來(lái)表示一個(gè)進(jìn)程的地址空間及其映射.mm_struct主要通過(guò)兩種結(jié)構(gòu)來(lái)保存這些內(nèi)存映射區(qū)域:一個(gè)是紅黑樹,紅黑樹的主要目的是為了能夠快速地通過(guò)地址找到對(duì)應(yīng)的內(nèi)存映射區(qū)域.另外一個(gè)是內(nèi)存區(qū)域映射鏈表,如圖 1 所示,其中的VMAs list就是管理所有內(nèi)存映射區(qū)域的內(nèi)存映射鏈表.

圖1 Linux 地址空間組織結(jié)構(gòu)Fig.1 Address space structure of Linux

Linux中,每一個(gè)內(nèi)存映射區(qū)域(VMA)都是通過(guò)一個(gè)vm_area_struct結(jié)構(gòu)來(lái)描述.如圖1所示,在內(nèi)存映射鏈表中的每一個(gè)VMA中,vm_start代表了該內(nèi)存映射區(qū)域的起始地址,而vm_end代表了該內(nèi)存映射區(qū)域的結(jié)束地址.除此之外,VMA中還包括該內(nèi)存映射區(qū)域的讀寫和映射屬性的相關(guān)信息.

2.2 地址空間操作及其同步

操作系統(tǒng)提供了mmap、munmap(統(tǒng)一稱之為內(nèi)存映射操作)以及page faults等地址空間操作:page faults負(fù)責(zé)分配物理頁(yè)面和建立對(duì)應(yīng)該頁(yè)面的頁(yè)表項(xiàng).mmap系統(tǒng)調(diào)用主要是從虛擬內(nèi)存區(qū)域中分配一個(gè)空閑的地址空間段.隨后mmap將該地址空間段的VMA插入到mm_struct所管理的映射鏈表中;munmap操作從映射鏈表中刪除一個(gè)內(nèi)存映射區(qū)域,并且撤銷頁(yè)表中相關(guān)的頁(yè)表項(xiàng).

多個(gè)線程會(huì)觸發(fā)page faults以及并發(fā)調(diào)用內(nèi)存映射操作.為了保證執(zhí)行正確性,Linux操作系統(tǒng)采用一個(gè)全局讀寫鎖mmap_sem(如圖1)來(lái)同步這些并發(fā)操作.在執(zhí)行內(nèi)存映射操作之前,線程需要作為寫者來(lái)競(jìng)爭(zhēng)mmap_sem,多個(gè)寫者必須串行執(zhí)行.page faults會(huì)作為讀者來(lái)競(jìng)爭(zhēng)mmap_sem,并且同一時(shí)刻可以允許多個(gè)讀者一起獲得該鎖.當(dāng)mmap作為寫者獲得mmap_sem的時(shí)候,其會(huì)阻塞讀者獲得該鎖.此外,當(dāng)多個(gè)page faults作為讀者獲得鎖時(shí),寫者必須陷入睡眠,直到所有讀者都完成操作之后寫者才可以獲得該鎖.

2.3 虛擬內(nèi)存密集型程序性能瓶頸分析

虛擬內(nèi)存密集型多線程程序是非常重要的一類多線程程序.這類應(yīng)用的主要特征是包含大量的地址空間操作.例如應(yīng)用頻繁地觸發(fā)page faults,或者應(yīng)用包含頻繁而且大量的堆分配操作導(dǎo)致應(yīng)用頻繁地調(diào)用內(nèi)存映射操作.然而,全局讀寫鎖mmap_sem將串行化page faults和內(nèi)存映射操作,并且多個(gè)內(nèi)存映射操作之間也必須串行執(zhí)行,例如mmap、munmap之間必須串行執(zhí)行.對(duì)于虛擬內(nèi)存密集型多線程應(yīng)用,這種串行化將極大地限制應(yīng)用的性能和可擴(kuò)展性.

圖2 應(yīng)用histogram 中mmap_sem開銷Fig.2 Mmap_sem overhead in histogram

圖2是測(cè)試的虛擬內(nèi)存密集型程序histogram中mmap_sem開銷占總執(zhí)行時(shí)間的比重.當(dāng)超過(guò)8核時(shí),mmap_sem引起的開銷不斷增加,在32核的時(shí)候更是達(dá)到了總運(yùn)行時(shí)間的49.32%.所以對(duì)于虛擬內(nèi)存密集型多線程程序,在高并發(fā)時(shí)全局讀寫鎖mmap_sem將導(dǎo)致應(yīng)用極大的性能下降.本文主要致力于解決該問(wèn)題.

2.4 Pthreads線程模型

Pthreads是基于共享地址空間實(shí)現(xiàn)的、廣泛使用的多線程編程模型.和進(jìn)程相比,Pthreads可以保持多線程共享變量.同時(shí)Pthreads也提供了一些編程接口,使得用戶可以管理共享內(nèi)存.

如圖3所示,圖左邊代表Pthreads線程模型.從圖中可以看到線程T1和T2擁有共享的地址空間,并且在共享地址空間中,線程T1和T2各自擁有獨(dú)立的棧空間.地址空間中每一個(gè)內(nèi)存區(qū)域映射的物理內(nèi)存都屬于進(jìn)程私有.線程T1和T2通過(guò)共享的內(nèi)存描述符來(lái)訪問(wèn)這些物理內(nèi)存,以達(dá)到共享內(nèi)存的目的.線程T1和T2會(huì)并發(fā)執(zhí)行內(nèi)存映射操作,用于分配或者刪除內(nèi)存映射區(qū)域,同時(shí)線程T1和T2也會(huì)觸發(fā)page faults來(lái)分配物理頁(yè)面.

圖3 兩種線程模型對(duì)比Fig.3 Comparing the two kinds of thread models

然而,如2.2和2.3分析可知,當(dāng)T1和T2大量并發(fā)執(zhí)行內(nèi)存映射操作以及觸發(fā)page faults時(shí),Pthreads多線程程序必然會(huì)因?yàn)楣蚕淼刂房臻g而引起性能下降.對(duì)于虛擬內(nèi)存密集型應(yīng)用來(lái)說(shuō),這種性能下降更加明顯.

3 PMthreads線程模型特征

本節(jié)首先討論P(yáng)Mthreads線程模型的特征.其中,本文將討論P(yáng)Mthreads線程地址空間隔離的特征,以及PMthreads線程共享變量的原理.最后本節(jié)將討論實(shí)現(xiàn)難點(diǎn).

3.1 PMthreads線程模型

3.1.1 線程地址空間隔離

為了完全避免線程競(jìng)爭(zhēng)地址空間,本文采用隔離地址空間的做法,從而使線程擁有各自獨(dú)立的地址空間.當(dāng)線程調(diào)用內(nèi)存映射操作和觸發(fā)page faults時(shí),并不會(huì)和其他線程產(chǎn)生任何競(jìng)爭(zhēng).如圖3,圖右邊代表PMthreads線程模型.線程T1和線程T2各自擁有私有的地址空間.當(dāng)線程T1和T2并發(fā)地執(zhí)行內(nèi)存映射操作和page faults的時(shí)候,T1和T2僅僅會(huì)在自己的私有地址空間上執(zhí)行操作.因此,線程之間并不需要競(jìng)爭(zhēng)mmap_sem讀寫信號(hào)量,同時(shí)這種隔離地址空間天然地保證了線程私有棧特征,如圖3所示.

3.1.2 線程共享變量

在通過(guò)Pthreads運(yùn)行的多線程應(yīng)用中,多線程共享主線程的全部地址空間.多線程主要包括兩種共享變量,一個(gè)是共享的全局變量,另外一個(gè)是共享的堆變量.一個(gè)線程在這些共享變量上修改以后,修改后的數(shù)據(jù)可以立即被其他的線程所見,并且代碼也是線程重要的共享數(shù)據(jù).

地址空間隔離導(dǎo)致線程無(wú)法通過(guò)共享內(nèi)存描述符來(lái)共享內(nèi)存.為了保證線程可以共享全局變量、堆變量、代碼,如圖3虛線框key所示,PMthreads將這些虛擬內(nèi)存區(qū)域映射到共享的物理內(nèi)存.當(dāng)調(diào)用fork創(chuàng)建子線程的時(shí)候,子線程的虛擬內(nèi)存相關(guān)區(qū)域也可以映射到對(duì)應(yīng)的物理內(nèi)存中.

3.2 地址空間隔離引起的問(wèn)題以及實(shí)現(xiàn)難點(diǎn)

無(wú)法保持共享變量:每一個(gè)進(jìn)程的全局?jǐn)?shù)據(jù)區(qū)域都是被映射到一個(gè)私有可寫的文件.為了完全消除地址空間競(jìng)爭(zhēng),PMthreads給每一個(gè)線程一個(gè)隔離的地址空間.然而,由于私有文件映射特征,地址空間隔離將導(dǎo)致線程執(zhí)行寫時(shí)復(fù)制(copy-on-write),而產(chǎn)生私有的物理內(nèi)存.因此無(wú)法保持PMthreads線程共享全局?jǐn)?shù)據(jù).為了保持線程共享全局變量,PMthreads提供了共享的物理內(nèi)存.但是,Linux內(nèi)核通過(guò)一個(gè)VMA來(lái)管理進(jìn)程的全局?jǐn)?shù)據(jù)區(qū)域.因此,必須修改內(nèi)核中相關(guān)數(shù)據(jù)結(jié)構(gòu)才能保證共享全局變量.本文需要在不做太多Linux內(nèi)核改動(dòng)的前提下,確保線程共享全局?jǐn)?shù)據(jù)區(qū)域的物理內(nèi)存.

現(xiàn)有堆分配器無(wú)法適用:同樣,共享的堆變量是基于共享內(nèi)存的多線程進(jìn)行線程通信的一類重要的共享變量.在Pthreads線程模型中,線程通過(guò)堆分配器在地址空間上進(jìn)行共享堆變量的空間分配.然而,在PMthreads中,由于線程具有私有的地址空間,現(xiàn)有的堆分配器具有兩方面限制:一方面是現(xiàn)有堆分配器仍然從私有地址空間中分配內(nèi)存,例如mmap分配一個(gè)私有chunk,無(wú)法保證堆變量在線程之間共享.另一方面是堆分配器本身具有大量的共享數(shù)據(jù)結(jié)構(gòu),這些共享數(shù)據(jù)結(jié)構(gòu)(堆初始化時(shí)mmap分配)將因?yàn)榈刂房臻g隔離而私有化.因此本文提供了IAmalloc堆分配器,以解決現(xiàn)有堆分配器無(wú)法適用PMthreads的問(wèn)題.

無(wú)法支持Pthreads接口:Pthreads多線程程序往往需要調(diào)用許多同步管理接口,用于多線程間的同步操作.這些接口包括:互斥量、條件變量、barrier等.Pthreads底層實(shí)現(xiàn)這些互斥量、條件變量、barrier算法時(shí),需要采用全局?jǐn)?shù)據(jù)和共享?xiàng)?shù)據(jù).但是PMthreads線程地址空間完全隔離,導(dǎo)致線程無(wú)法共享?xiàng)?shù)據(jù).因此,為了保證Pthreads應(yīng)用可以無(wú)修改地被支持,本文在PMthreads上實(shí)現(xiàn)了互斥量、條件變量以及barrier算法,并保持和Pthreads相關(guān)接口與語(yǔ)義的一致.

4 PMthreads線程模型

本節(jié)主要討論P(yáng)Mthreads的實(shí)現(xiàn).首先本討論如何實(shí)現(xiàn)共享變量;其次將討論IAmalloc堆分配的特點(diǎn)及其實(shí)現(xiàn);最后討論P(yáng)Mthreads如何支持Pthreads接口.

4.1 共享變量實(shí)現(xiàn)

4.1.1 全局變量共享

Linux內(nèi)核僅僅使用一個(gè)VMA來(lái)管理一個(gè)進(jìn)程的全局?jǐn)?shù)據(jù)區(qū)域.通過(guò)VMA中的相關(guān)標(biāo)識(shí),Linux內(nèi)核確定一個(gè)進(jìn)程的全局?jǐn)?shù)據(jù)區(qū)域是一個(gè)私有可寫的內(nèi)存映射區(qū)域.同時(shí)該VMA記錄了可執(zhí)行文件的描述符,來(lái)確定進(jìn)程全局?jǐn)?shù)據(jù)區(qū)域是一個(gè)私有可寫的文件映射.為了確保被隔離地址空間的線程能夠共享全局變量,PMthreads采用共享文件映射策略.但是,這需要將PMthreads線程的全局?jǐn)?shù)據(jù)區(qū)從私有文件修改為共享文件映射.因此,內(nèi)核中進(jìn)程全局?jǐn)?shù)據(jù)區(qū)域的VMA必須要修改.然而,直接修改Linux內(nèi)核并不是一個(gè)可以被廣泛使用的方式.因此本文通過(guò)實(shí)現(xiàn)一種了字符設(shè)備驅(qū)動(dòng)來(lái)完成修改工作.用戶僅僅需要將該模塊安裝到他們自己的內(nèi)核中,而不需要修改內(nèi)核.

該字符設(shè)備驅(qū)動(dòng)攔截了write系統(tǒng)調(diào)用.當(dāng)應(yīng)用開始執(zhí)行的時(shí)候,在主函數(shù)之前,線程會(huì)調(diào)用該write系統(tǒng)調(diào)用.通過(guò)傳入的主線程的PID以及設(shè)備驅(qū)動(dòng)號(hào),該系統(tǒng)調(diào)用會(huì)將主線程的PID傳入對(duì)應(yīng)的設(shè)備驅(qū)動(dòng).設(shè)備驅(qū)動(dòng)隨后會(huì)查找到主線程得的mm_struct,將主線程的全局?jǐn)?shù)據(jù)區(qū)域由私有文件映射修改為共享文件映射.不同線程可以通過(guò)共享文件映射達(dá)到共享全局?jǐn)?shù)據(jù)區(qū)域的物理內(nèi)存的目的.

4.1.2 共享代碼段特征

在PMthreads中每一個(gè)線程擁有獨(dú)立的地址空間,并且每一個(gè)線程的代碼段是只讀的內(nèi)存映射區(qū)域.對(duì)于只讀映射區(qū)域的物理內(nèi)存,PMthreads中的多線程可以直接共享.

4.2 共享堆分配器

為了保證多線程進(jìn)行正常的動(dòng)態(tài)內(nèi)存分配,本文設(shè)計(jì)了一個(gè)堆分配器,稱為IAmalloc,可以直接適用于PMthreads.IAmalloc主要解決如下幾個(gè)問(wèn)題:首先,在隔離地址空間的線程之間,如何共享堆變量;其次,IAmalloc如何保證高效的堆分配;最后,IAmalloc如何保證線程釋放堆空間中的任何變量.

堆變量共享:如圖3,每一個(gè)線程的地址空間都包含一個(gè)固定大小的內(nèi)存映射區(qū)域作為堆區(qū)域.該區(qū)域是一個(gè)匿名共享映射區(qū)域.當(dāng)PMthreads初始化時(shí),該區(qū)域由主線程調(diào)用mmap系統(tǒng)調(diào)用創(chuàng)建.多進(jìn)程可以共享匿名共享映射區(qū)域的物理內(nèi)存.雖然PMthreads線程位于隔離的地址空間,但是線程之間通過(guò)此匿名共享映射區(qū)域可以保持堆變量共享.

堆分配效率提升:堆分配器的效率是一個(gè)影響應(yīng)用性能和可擴(kuò)展性的重要因素.在頻繁進(jìn)行堆分配的應(yīng)用中,高效的堆分配器能夠極大地提高應(yīng)用的性能.為了保證堆分配效率,IAmalloc將整個(gè)堆空間分成了若干個(gè)子堆.每一個(gè)線程會(huì)占有一個(gè)子堆,并且規(guī)定每一個(gè)線程僅僅被允許在自己的子堆中分配堆空間.因此,IAmalloc并沒(méi)有使用任何鎖保護(hù)分配.這有兩方面的好處,一方面是消除了堆變量分配重疊的嚴(yán)重錯(cuò)誤;另一方面,當(dāng)線程從子堆中分配的時(shí)候,線程并不需要競(jìng)爭(zhēng)性地獲得堆空間.雖然采用子堆策略,但是線程仍然可以訪問(wèn)所有線程的子堆.這種子堆策略能夠極大地提高上層應(yīng)用分配堆空間的效率.

釋放規(guī)則和堆算法:IAmalloc將堆釋放進(jìn)行了加鎖處理,以保證線程可以釋放其他線程子堆中的堆變量.同時(shí),為了保證釋放時(shí)的性能,IAmalloc僅僅在子堆上進(jìn)行細(xì)粒度鎖處理.IAmalloc的分配和釋放算法來(lái)自dlmalloc[6].*http://gee.cs.oswego.edu/dl/html/malloc.html

4.3 同步算法和接口支持

在大量的Pthreads應(yīng)用程序中,僅僅使用兩類常用接口:一類是線程管理相關(guān)接口,一類是同步相關(guān)接口.其中同步相關(guān)接口,主要有三種,分別是互斥量、條件變量以及barrier.為了保證不用修改應(yīng)用代碼,PMthreads對(duì)這些接口進(jìn)行了實(shí)現(xiàn)支持.

4.3.1 線程管理

由于PMthreasds采用隔離地址空間的做法,所以在PMthreads中,pthread_create通過(guò)調(diào)用fork系統(tǒng)調(diào)用來(lái)實(shí)現(xiàn)輕量級(jí)進(jìn)程的創(chuàng)建,并且PMthreads給每一線程一個(gè)確定的ID號(hào).在pthread_join中,我們通過(guò)waitpid來(lái)等待線程.

4.3.2 同步算法和接口

PMthreads將同步變量(互斥量、條件變量、barrier)中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行重新設(shè)計(jì)和組織.在初始化同步變量時(shí),其關(guān)鍵的共享數(shù)據(jù)將會(huì)被組織在共享的堆中.例如,PMthreads采用睡眠喚醒的同步策略,因此在堆中每一個(gè)同步變量都將會(huì)被包含一個(gè)共享的睡眠隊(duì)列.在此基礎(chǔ)上,PMthreads實(shí)現(xiàn)了同步算法.

其中,互斥量和barrier算法來(lái)自[7],對(duì)于條件變量算法本文采用[9]中的算法.基于這些同步算法,PMthreads實(shí)現(xiàn)了Pthreaads中的互斥量、條件變量以及barrier管理接口.Pthreads多線程應(yīng)用可以不經(jīng)過(guò)任何修改地調(diào)用PMthreads.

5 實(shí)驗(yàn)評(píng)估

5.1 實(shí)驗(yàn)平臺(tái)和實(shí)驗(yàn)方法

我們?cè)?×Intel Xeon E7-4820處理器(總共為32核)、128GB內(nèi)存的64位Ubuntu 12.04(內(nèi)核版本為3.2.0)上測(cè)試,所有程序用gcc-4.4.7編譯,glibc為glibc-2.15.每一個(gè)核數(shù)上僅僅運(yùn)行一個(gè)線程,所以下文全部采用核數(shù)代表線程數(shù).

表1 測(cè)試程序特征和數(shù)據(jù)集合Table 1 Workloads feature and dataset

表1給出了測(cè)試程序和相應(yīng)的數(shù)據(jù)集,并且本文也評(píng)測(cè)了在應(yīng)用中發(fā)生的malloc的總次數(shù).除了 dedup 外,其他均是 Phoenix 提供的測(cè)試程序.對(duì)于實(shí)驗(yàn)的每個(gè)測(cè)試程序,我們收集了它 10 次運(yùn)行的時(shí)間,并去掉最大值和最小值,將剩下 8 個(gè)的平均值作為程序的運(yùn)行時(shí)間[10].其中,histogram 和 dedup屬于虛擬內(nèi)存密集型程序,其他是普通程序.

5.2 性能結(jié)果分析

圖4顯示了在不同核數(shù)上運(yùn)行測(cè)試程序時(shí),原Pthreads版本相對(duì)于PMthreads版本的執(zhí)行時(shí)間對(duì)比.從圖4中可以看出來(lái),mm 和 sm 在兩種線程模型上的執(zhí)行性能相當(dāng);當(dāng)在32核時(shí),hist在PMthreads上執(zhí)行速度是Pthreads上的2.17倍.同時(shí)在32核上,dedup在PMthreads上性能提升了3.19倍.除了單核以外,lr的性能在其他核數(shù)上都有所提升,并且在16核上,性能提升了8.15倍.

mm 和 sm這兩個(gè)應(yīng)用程序都不屬于虛擬內(nèi)存密集型程序,一方面這兩個(gè)應(yīng)用在多核下沒(méi)有較多的物理內(nèi)存開銷,其次在多核下并沒(méi)有多線程調(diào)用大量的mmap或者mprotect等等.由于PMthreads采用隔離地址空間,在創(chuàng)建線程上開銷要比Pthreads要多,但是在一些耗時(shí)較多的計(jì)算密集型應(yīng)用上,例如mm和sm等應(yīng)用,PMthreads的開銷幾乎不會(huì)有較多的影響,因此mm和sm會(huì)有相當(dāng)?shù)男阅?

圖4 原Pthreads 程序相對(duì)于PMthreads版本的時(shí)間開銷Fig.4 Runtime overhead of Pthreads relative to the PMthreads

5.3 可擴(kuò)展性展示

圖5給出了測(cè)試程序在Pthreads上和PMthreads上的可擴(kuò)展性對(duì)比,其中p代表應(yīng)用運(yùn)行在Pthreads下,pm代表應(yīng)用運(yùn)行在PMthreads下.從圖中可以看出,對(duì)于dedup,從8核開始dedup-p加速比不斷地下降.而對(duì)于dedup-pm,其加速比

圖5 應(yīng)用程序相比于單核時(shí)的并行加速比Fig.5 Parallel speedup over its own single-CPU

在不斷地上升.對(duì)于histogram應(yīng)用,hist-p從16核開始加速比不斷地下降,到32核下降最明顯.然而,hist-pm從1核到32核加速比在不斷地上升.對(duì)于應(yīng)用linear_regression,在Pthreads線程模型下,其加速比幾乎沒(méi)有提升,而在PMthreads線程模型下,其加速比在不斷地上升.在string_match和matrix_multiply上PMthreads和Pthreads表現(xiàn)出了相當(dāng)?shù)募铀俦?

5.4 虛擬內(nèi)存密集型程序性能分析

在這些測(cè)試應(yīng)用中,histogram和dedup屬于比較常見的虛擬內(nèi)存密集型應(yīng)用.接下來(lái),本文給出關(guān)于這兩個(gè)虛擬內(nèi)存密集型應(yīng)用的詳細(xì)性能分析,以證明PMthreads可以提高這類應(yīng)用的性能.

5.4.1 histogram 應(yīng)用

histogram是一個(gè)來(lái)自于Phoenix的重要的數(shù)據(jù)并發(fā)應(yīng)用.其主要是將一張圖片的紅綠藍(lán)的像素的數(shù)量形成一個(gè)柱狀比例,其中所有的數(shù)據(jù)的空間全部由主線程從堆中分配.本文評(píng)估了histogram的物理內(nèi)存的消耗,實(shí)驗(yàn)結(jié)果展示其在32核的時(shí)候有將近1.4GB的物理內(nèi)存的開銷.大量的物理內(nèi)存開銷將導(dǎo)致頻繁的page faults.為了測(cè)試histogram性能提升的主要原因以及histogram的Pthreads版本性能損失的主要原因,本文通過(guò)Linux perf工具測(cè)試了熱點(diǎn)函數(shù)的分布情況.

histogram在Pthreads線程模型下,其熱點(diǎn)函數(shù)是dead_read_trylock()和up_read(),這兩個(gè)函數(shù)全部來(lái)自于Linux內(nèi)核.圖6,Pthreads版本的結(jié)果顯示隨著核數(shù)增加,兩個(gè)函數(shù)的開銷也在不斷地增加;而且,在32核的時(shí)候分別達(dá)到了總運(yùn)行時(shí)間的30%和20%.對(duì)于PMthreads版本,這兩個(gè)熱點(diǎn)函數(shù)的開銷在所有的核數(shù)下全部低于0.5%.隨后,本文檢查了這兩個(gè)熱點(diǎn)函數(shù)的調(diào)用路徑,這兩個(gè)函數(shù)全部來(lái)自于page faults處理函數(shù)中.其中down_read_trylock用于讀競(jìng)爭(zhēng)讀寫信號(hào)量mmap_sem.up_read用于釋放該讀寫信號(hào)量.在Pthreads下,雖然是讀競(jìng)爭(zhēng),由于線程共享讀寫鎖導(dǎo)致處理器需要不斷進(jìn)行cache 一致性處理,引起較大開銷;而PMthreads隔離了地址空間,產(chǎn)生私有的讀寫鎖,因此,線程并不會(huì)發(fā)生競(jìng)爭(zhēng).所以,PMthreads在削減信號(hào)量競(jìng)爭(zhēng)上具有很好的效果.

圖6 histogram 熱點(diǎn)函數(shù)開銷Fig.6 Hot function overhead of histogram

從圖6中可以看出PMthreads在down_read_trylock和up_read上呈現(xiàn)出不規(guī)則的結(jié)果,這兩個(gè)函數(shù)全部來(lái)自于page faults中,由于PMthreads采用私有地址空間的策略,所以每一個(gè)線程的地址空間都存在上下文切換,在測(cè)試時(shí)候存在一些誤差.但是,在這兩個(gè)函數(shù)上的開銷則全部非常的低.

5.4.2 dedup應(yīng)用

這是一個(gè)來(lái)自PARSEC中的應(yīng)用,這個(gè)應(yīng)用結(jié)合著局部壓縮和和全局壓縮對(duì)數(shù)據(jù)進(jìn)行充分的壓縮.本文中所有的針對(duì)該應(yīng)用的實(shí)驗(yàn)都使用的是large類型的數(shù)據(jù)集合.如表1所示,該應(yīng)用使用了大量的堆空間和進(jìn)行了非常頻繁的堆分配,該應(yīng)用是一個(gè)典型的虛擬內(nèi)存密集型應(yīng)用[1].

為了查找該應(yīng)用性能提升的根本原因,我們也使用perf來(lái)檢測(cè)該應(yīng)用在PMthreads和Pthreads不同模型下執(zhí)行時(shí)候的熱點(diǎn)函數(shù)的開銷.實(shí)驗(yàn)結(jié)果顯示,在Pthreads模型下,dedup的熱點(diǎn)函數(shù)是一個(gè)來(lái)自內(nèi)核中的自旋鎖__ticket_spin_lock;并且在32核CPU下,其開銷占了總運(yùn)行時(shí)間的24.7%,如圖6所示;而在PMthreads中運(yùn)行的情況顯示,該函數(shù)的開銷全部都在2.37%以下.同樣,我們查找了該函數(shù)的調(diào)用棧信息.

調(diào)用棧信息顯示,__ticket_spin_lock是一個(gè)內(nèi)核中函數(shù),其主要是被函數(shù)rwsem_down_failed_common調(diào)用.該函數(shù)主要來(lái)自兩個(gè)方面,一個(gè)是系統(tǒng)調(diào)用mmap等,另外一個(gè)是page faults.當(dāng)執(zhí)行page faults或者mmap競(jìng)爭(zhēng)mmap_sem失敗的時(shí)候,線程會(huì)調(diào)用該函數(shù)進(jìn)入共享隊(duì)列中睡眠.所以,可以得出結(jié)論,dedup的Pthreads版本在執(zhí)行時(shí)對(duì)讀寫信號(hào)量mmap_sem的競(jìng)爭(zhēng)是dedup開銷的重要一方面.這也證明PMthreads的隔離地址空間策略極大地降低了線程對(duì)地址空間的競(jìng)爭(zhēng),應(yīng)用由此獲得了性能提升.

5.5 其他方面性能收益

linear_regression是一個(gè)針對(duì)給定點(diǎn)集合的線性回歸計(jì)算的應(yīng)用.該應(yīng)用需要頻繁地更新代表線性回歸的變量.我們通過(guò)perf給出linear_regresson在兩種不同模型下的L1緩存的load miss率和store miss的比值情況.如圖8所示,在Pthreads下load miss率最高是PMthreads下的8倍,store miss 率最高達(dá)到了52倍.所以,該應(yīng)用極端差的可擴(kuò)展性是由于需要不斷進(jìn)行L1級(jí)cache的一致性處理.

圖7 dedup應(yīng)用中ticket_spin_lock開銷Fig.7 Ticket_spin_lock overhead of dedup

圖8 L1 cache miss 率的比值,Pthreads比PMthreadsFig.8 Ratio of L1 cache miss rate,Pthreads/PMthreads

隨后,我們觀察了應(yīng)用本身的特征.應(yīng)用的計(jì)算結(jié)果被保存在一個(gè)共享的結(jié)構(gòu)體數(shù)組中,每一個(gè)線程會(huì)將計(jì)算的結(jié)果更新到數(shù)組中的對(duì)應(yīng)元素中.但是由于堆分配的特征導(dǎo)致該結(jié)構(gòu)體數(shù)組的地址并未按64B對(duì)齊,導(dǎo)致產(chǎn)生假共享.所以,當(dāng)線程頻繁地更新結(jié)構(gòu)體中元素時(shí),必然會(huì)產(chǎn)生大量的緩存一致性問(wèn)題.但是,在PMthreads中,由于對(duì)堆分配的地址進(jìn)行了處理,所以并不會(huì)發(fā)生假共享的情況;從而PMthreads減少了cache一致性處理,提高了應(yīng)用的性能和可擴(kuò)展性.這是堆分配器帶來(lái)的額外的性能提升.

6 總 結(jié)

本文首先分析了由共享地址空間引起的虛擬內(nèi)存密集型應(yīng)用的性能瓶頸問(wèn)題.隨后,本文給出了基于地址空間隔離的線程模型來(lái)提升應(yīng)用性能.最后對(duì)比了兩個(gè)線程模型在虛擬內(nèi)存密集型應(yīng)用上的性能特征.實(shí)驗(yàn)結(jié)果表明PMthreads可以極大的提升虛擬內(nèi)存密集型程序性能.然而,IAmalloc堆分配器分配不均衡,以及PMthreads需要支持更多的Pthreads接口.這些都是亟待解決的問(wèn)題.

：

[1] Austin T Clements,Frans Kaashoek M,Nickolai Zeldovich.Scalable address spaces using RCU balanced trees[C].In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII)，ACM,New York,NY,USA,2012:99-210.

[2] Boyd Wickizer S,Clements A T,Mao Y,et al.An analysis of Linux scalability to many cores[C].USENIX Symposium on Operating Systems Design and Implementation(OSDI′10),2010,10(13):86-93.

[3] Christian Bienia,Sanjeev Kumar,Jaswinder Pal Singh,et al.The PARSEC benchmark suite:characterization and architectural implications[C].In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques (PACT′08),ACM,New York,NY,USA,2008:72-81.

[4] Ranger C,Raghuraman R,Penmetsa A,et al.Evaluating mapreduce for multi-core and multiprocessor systems[C].In High Performance Computer Architecture(HPCA 2007),IEEE 13th International Symposium on.Ieee,2007:13-24.

[5] Weaver,Vincent M.Linux perf_event features and overhead[C].The 2nd International Workshop on Performance Analysis of Workload Optimized Systems,FastPath,Vol.13,2013.

[6] Lea D.A memory allocator[EB/OL].http://gee.cs.oswego.edu/dl/html/malloc.html,2000.

[7] Ulrich Drepper.Futexes are tricky[C].In Futexes are Tricky,Red Hat Inc,Japan,December,2005.

[8] Kai Lu,Xu Zhou,Tom Bergan,et al.Efficient deterministic multithreading without global barriers[C].In Proceedings of the 19th ACM SIGPLAN Sym,Posium on Principles and Practice of Parallel Programming (PPoPP′14),ACM,New York,NY,USA,2014:287-300.

[9] Birrell A.Implementing condition variables with semaphores[C].In Computer Systems Theory,Technology,and Applications,2004:29-37.

[10] Cao Hui-fang,Zhang Yu.Exploring the programmability and implementation performance for a deterministic multithreaded programming model[J].Journal of Chinese Computer Systems,2016,37(6):1126-1131.

附中文參考文獻(xiàn)：

[10] 曹慧芳,張 昱.確定性多線程編程模型的可編程性及其實(shí)現(xiàn)性能的探索[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(6):1126-1131.