并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制的探討

王婧

摘 要：多核CPU的存儲(chǔ)層次越來(lái)越深而且越來(lái)越復(fù)雜，這已經(jīng)成為優(yōu)化大規(guī)模并行應(yīng)用程序性能的關(guān)鍵瓶頸。目前并行程序設(shè)計(jì)語(yǔ)言和多核CPU有兩種局部性設(shè)計(jì)方法，一個(gè)是橫向局部性，另一個(gè)是縱向局部性，通過(guò)這兩種視角可以進(jìn)一步了解現(xiàn)在并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制的特點(diǎn)。文章就并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制進(jìn)行探討，深入分析其優(yōu)缺點(diǎn)，探究未來(lái)并行程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)的方向，指出新語(yǔ)言可以考慮這兩種局部性設(shè)計(jì)機(jī)制，希望能為相關(guān)從業(yè)者帶來(lái)一些參考。

關(guān)鍵詞：并行程序;設(shè)計(jì)語(yǔ)言;局部性機(jī)制

0 引言

為了解決訪問(wèn)延遲與處理器速度之間的差距變大的問(wèn)題，體系架構(gòu)設(shè)計(jì)者在硬件上引入了存儲(chǔ)層次概念。同時(shí)，想要充分挖掘出存儲(chǔ)層次的硬件設(shè)計(jì)優(yōu)點(diǎn)，并行程序設(shè)計(jì)語(yǔ)言要具備優(yōu)秀的局部性機(jī)制，才能得到更高的性能。并行程序設(shè)計(jì)語(yǔ)言領(lǐng)域中，技術(shù)人員會(huì)逐步加入不同的局部性機(jī)制，進(jìn)一步增強(qiáng)語(yǔ)言挖掘局部性的力度?？蒲腥藛T若要寫(xiě)出性能高的代碼，需要考慮在并行程序設(shè)計(jì)語(yǔ)言和編程模型的設(shè)計(jì)中加入局部性的描述和表示機(jī)制，以方便科研人員利用這些機(jī)制來(lái)描述和挖掘算法及程序中的局部性[1]。

1 并行編程語(yǔ)言發(fā)展趨勢(shì)

隨著科技發(fā)展，多路多核處理器的出現(xiàn)使得MPI（Message Passing Interface）在優(yōu)化設(shè)計(jì)并行算法時(shí)遇到困難，MPI是基于分布式存儲(chǔ)最受歡迎的編程方式。雖然MPI在節(jié)點(diǎn)間運(yùn)行，OpenMP在節(jié)點(diǎn)內(nèi)運(yùn)行，這樣可以實(shí)現(xiàn)混合并行，但是這是兩種不一樣的并行語(yǔ)言，設(shè)計(jì)人員在設(shè)計(jì)時(shí)難度會(huì)增加。所以新并行編程語(yǔ)言一定要考慮到多層次并行的支持，進(jìn)一步優(yōu)化硬件層次的設(shè)計(jì)、訪存的延遲和帶寬等。數(shù)據(jù)局部性會(huì)成為重要的因素，新設(shè)計(jì)的編程語(yǔ)言要給技術(shù)人員定義數(shù)據(jù)局部性的機(jī)制，盡量減少訪存和通信次數(shù)，提高程序運(yùn)行性能。存儲(chǔ)層次的復(fù)雜，使得并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制更加重要，目前人們?nèi)找骊P(guān)注針對(duì)多核的存儲(chǔ)訪問(wèn)局部性的算法研究，所以未來(lái)并行編程語(yǔ)言的研究重點(diǎn)是設(shè)計(jì)容易表達(dá)算法局部性的機(jī)制。

2 新設(shè)計(jì)的并行編程語(yǔ)言要具備的要點(diǎn)

首先要有具備縱向局部性和橫向局部性的顯式管理機(jī)制?，F(xiàn)在并行計(jì)算系統(tǒng)的存儲(chǔ)層次越來(lái)越復(fù)雜，如果只靠運(yùn)行時(shí)系統(tǒng)和編譯器來(lái)處理局部性問(wèn)題和并行性開(kāi)發(fā)，不是最佳的處理方法，還要依靠技術(shù)人員的顯式管理。

新開(kāi)發(fā)的并行編程語(yǔ)言要能夠應(yīng)用在不一樣的并行編程模式中，比如任務(wù)并行、數(shù)據(jù)并行等。

統(tǒng)一管理程序的局部性和并行性，開(kāi)發(fā)設(shè)計(jì)人員利用編程語(yǔ)言可以整體設(shè)計(jì)這兩種特性，想辦法減輕人員的工作負(fù)擔(dān)，同時(shí)又能夠開(kāi)發(fā)高性能的并行程序，并且保證并行程序可在不同硬件平臺(tái)移植。

與Local View類(lèi)似，這些方法雖然能夠幫助開(kāi)發(fā)人員編程的效率，減輕他們的工作負(fù)擔(dān)，加快并行程序的開(kāi)發(fā)進(jìn)程，但是這種固定的處理數(shù)據(jù)方案也限制了更有效設(shè)計(jì)并行算法和數(shù)據(jù)劃分，而且也只能支持部分并行模式。雖然并行程序開(kāi)發(fā)人員管理局部性可以復(fù)用分布類(lèi)，但其實(shí)是有限的，就算是設(shè)計(jì)了大量的分布類(lèi)，都很難高效使用。

3 并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制

并行程序設(shè)計(jì)涉及多方面的知識(shí)，并非簡(jiǎn)單的并行算法的設(shè)計(jì)，只有綜合考慮各方面的因素，才能設(shè)計(jì)出高效率的并行程序[2]。并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制分為橫向局部性和縱向局部性?xún)煞N。對(duì)分布式并行程序設(shè)計(jì)而言，利用更多的局部性機(jī)制是橫向局部性，主要考慮怎么樣減少消息傳遞的開(kāi)銷(xiāo)。而串行程序相反，考慮更多的是縱向局部性，現(xiàn)在已經(jīng)有很多的文獻(xiàn)研究。

3.1? 并行程序設(shè)計(jì)語(yǔ)言中橫向局部性

橫向局部性是由于存儲(chǔ)位置的分布導(dǎo)致同一內(nèi)存層次上的數(shù)據(jù)通信，例如Jacobi算法就是因?yàn)榘褦?shù)組數(shù)據(jù)分塊造成不同塊間的邊界通信。一般來(lái)說(shuō)數(shù)據(jù)分布如果有不錯(cuò)的空間局部性，就會(huì)有不錯(cuò)的橫向局部性，但是橫向局部性不只有良好的空間局部性，還包括數(shù)據(jù)通信的開(kāi)銷(xiāo)。并行程序設(shè)計(jì)語(yǔ)言的橫向局部性分為兩種設(shè)計(jì)，一種是像OpenMP，編譯器自動(dòng)劃分和分配數(shù)據(jù)，另一種是像HPF，技術(shù)人員管理控制數(shù)據(jù)劃分和分配過(guò)程。

HPF編程模型和OpenMP，MPI都不一樣，前者為了管理并行程序設(shè)計(jì)語(yǔ)言中的橫向局部性，設(shè)計(jì)定義和它們不一樣的分布類(lèi)型。在管理橫向局部性方面，顯然HPF優(yōu)勢(shì)更大。開(kāi)發(fā)人員運(yùn)用HPF編寫(xiě)程序時(shí)，一般運(yùn)用編譯制導(dǎo)語(yǔ)句來(lái)進(jìn)行數(shù)據(jù)的分塊，并行操作不同數(shù)據(jù)塊則運(yùn)用forall語(yǔ)句，不過(guò)HPF描述數(shù)據(jù)局部性較單一。因?yàn)橛袆澐值膬?nèi)存地址空間，并行程序設(shè)計(jì)語(yǔ)言PGAS改進(jìn)了OpenMP的存儲(chǔ)模型，但是數(shù)據(jù)分塊方法略有差異，思想還是差不多，由開(kāi)發(fā)人員來(lái)管理數(shù)據(jù)分塊，運(yùn)行時(shí)系統(tǒng)和編譯器管理線程間的通信。

3.2? 并行程序設(shè)計(jì)語(yǔ)言中縱向局部性

不同存儲(chǔ)層次之間的局部性就是縱向局部性，比如內(nèi)存和Cache?？v向局部性還可以從時(shí)間和空間來(lái)分成兩種。隨著科技的發(fā)展，并行計(jì)算系統(tǒng)存儲(chǔ)層次越來(lái)越復(fù)雜，CPU性能和內(nèi)存訪問(wèn)性能之間的差距正在擴(kuò)大。想要提高計(jì)算程序的性能，就一定要考慮到數(shù)據(jù)的縱向局部性。同時(shí)，這種考慮往往不具備可移植性，所以在對(duì)并行編程模型重新設(shè)計(jì)時(shí)，一定要顯式管理存儲(chǔ)層次，尤其是出現(xiàn)多核處理器后，讓并行程序?qū)Υ鎯?chǔ)層次進(jìn)行顯式管理，進(jìn)一步優(yōu)化縱向局部性，是一種提升程序性能的重要方法。

在顯式管理縱向局部性方面，現(xiàn)在已經(jīng)有多個(gè)基于Cell處理器的編程模型?？v使Cell SDK可以位于Cell核內(nèi)部完成MPI編程，也可以位于獨(dú)立地址空間實(shí)施Pthread編程，然而Cell SDK在局部性管理上仍有缺陷，橫向局部性管理導(dǎo)致并行編程的難度大大增加，縱向局部性管理也只是實(shí)現(xiàn)了不同存儲(chǔ)層次間的通信，擴(kuò)展性和可移植性很差。

Sequoia是為了應(yīng)對(duì)Cell SDK的這些缺陷而出現(xiàn)的，現(xiàn)在是組成Cell的重要部分。開(kāi)發(fā)人員可以用Sequoia顯式管理存儲(chǔ)層次，設(shè)計(jì)出性能更加好的算法。在顯式管理縱向局部性時(shí)，Sequoia設(shè)置數(shù)據(jù)傳遞大小會(huì)考慮底層硬件平臺(tái)的不同存儲(chǔ)層次特征，更好地顯式管理縱向局部性。不過(guò)計(jì)算機(jī)集群系統(tǒng)卻沒(méi)有上面所說(shuō)的共享機(jī)制，它的計(jì)算節(jié)點(diǎn)是經(jīng)由高速網(wǎng)絡(luò)之后連接，Sequoia為實(shí)現(xiàn)物理內(nèi)存的抽象特意添加虛擬層。因此Sequoia不管是縱向局部性還是橫向局部性都可以管理，并且應(yīng)該允許技術(shù)人員的繼續(xù)優(yōu)化，不斷提升程序的性能。總之Cell SDK可以顯式管理每個(gè)層次，可以看成是具備兩個(gè)存儲(chǔ)層次的Sequoia。

3.3? 綜合兩種局部性

在算法設(shè)計(jì)和并行實(shí)現(xiàn)時(shí)，想要讓并行程序的性能更高，就需要對(duì)縱向局部性和橫向局部性加以考慮。并行編程語(yǔ)言設(shè)計(jì)好了關(guān)于橫向局部性的管理機(jī)制，比如PGAS和MPI，不管用哪個(gè)通信機(jī)制，都是為了讓開(kāi)發(fā)人員更好實(shí)現(xiàn)對(duì)橫向局部性的顯式管理，并且盡量減少通信開(kāi)銷(xiāo)。當(dāng)并行應(yīng)用程序采用了這些編程語(yǔ)言時(shí)，橫向局部性、并行性挖掘和并行模式等都會(huì)考慮到，因此可以將并行性完美融合橫向局部性。在縱向局部性方面，由Sequoia設(shè)計(jì)出來(lái)的task，便于編程語(yǔ)言管理并行和兩種局部性，它既能制定多層次的并行模式，又有管理縱向局部性和橫向局部性的機(jī)制。在開(kāi)發(fā)新的編程模型時(shí)可以考慮以上方式，編寫(xiě)出更高效和性能更好的應(yīng)用程序。

4 結(jié)語(yǔ)

現(xiàn)如今計(jì)算機(jī)存儲(chǔ)系統(tǒng)越來(lái)越復(fù)雜，尤其是多核處理器的出現(xiàn)，系統(tǒng)更加難以開(kāi)發(fā)局部性，所以更加顯出局部性的描述和表示機(jī)制的優(yōu)勢(shì)。局部性機(jī)制可以幫助研究人員寫(xiě)的代碼性能更好，進(jìn)一步挖掘算法。本文分析了并行程序設(shè)計(jì)語(yǔ)言和多核處理器的狀況，探討了未來(lái)并行程序設(shè)計(jì)語(yǔ)言的發(fā)展趨勢(shì)，詳細(xì)分析了并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制的各種定義和應(yīng)用。并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制主要是分為縱向局部性和橫向局部性?xún)煞N，文章分別從這兩個(gè)視角來(lái)著重分析了局部性機(jī)制，對(duì)設(shè)計(jì)并行編程模型的方向更加明確。

[參考文獻(xiàn)]

[1]袁良，張?jiān)迫籽┤?，?并行程序設(shè)計(jì)語(yǔ)言中局部性機(jī)制的研究[J].計(jì)算機(jī)科學(xué)，2020（1）：7-16.

[2]黃偉文，姚文慶.并行程序設(shè)計(jì)[J].寧波職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2002（2）：87-90.

（編輯 何 琳）