多核處理器并行計算模型研究

摘 要：針對并行計算機體系結構中沒有通用的計算模型這一問題，分析了一些現有的典型計算模型，在同步性、通信方式、參數方面進行比較，以ＬｏｇＧＰ模型為基礎提出一種改進的ｍｚＬｏｇＧＰ模型。利用ＭＰＩ并行算法對滿足節點計算資源非獨占、網絡存在擁塞條件下的并行程序進行分析與測試，通過增加ｍｅｍｏｒｙ層次化層數和網絡擁塞指數這兩個參數，計算其計算開銷和通信開銷，將實測時間與預測時間進行比較，可知隨節點數的增加系統誤差不斷減小，說明該新模型能改善并行應用在多核處理器集群平臺上運行的性能，具有較好的可擴展性．

關鍵詞：

中圖分類號： ＴＰ３０１ 文獻標識碼： Ａ 文章編號：２０９５－２１６３（２０１１）０３－０００９－０５

Ｒｅｓｅａｒｃｈ ｏｆ Ｐａｒａｌｌｅｌ Ｃｏｍｐｕｔｉｎｇ Ｍｏｄｅｌ ｂａｓｅｄ ｏｎ Ｍｕｌｔｉ－ｃｏｒｅ Ｐｒｏｃｅｓｓｏｒ

ＬＩ Ｊｉｎｇｍｅｉ， ＺＨＡＮＧ Ｑｉ， ＷＡＮＧ Ｊｕｎｆｅｎｇ

Ａｂｓｔｒａｃｔ， As there is not a universal model in parallel computer architecture， the paper analyzes some existing typical models ， comparing them in synchronization， communication， parameters， then proposes a new model: mzLogGP based on LogGP . After that， the paper analyzes and tests the parallel process using the MPI parallel algorithm in the environment of non-exclusive nodes on the computing resources and existing network congestion， and calculates the computational overhead and communication overhead by increasing two parameters: network congestion and layers of memory hierarchy. In the end， by comparing the measured time with the predicted time， the paper shows that with the increase in the number of nodes， the system error decreases. The results demonstrate that the new model can improve running performance of parallel application in the platform of multi-core processor cluster， and has better scalability.

Ｋｅｙ ｗｏｒｄｓ，

０ 引言

在單核處理器中，通過提升ＣＰＵ頻率來提高ＣＰＵ性能的方法，已經促使ＣＰＵ頻率達到了極限，功耗問題達到瓶頸。因此，目前處理器的發展已由純粹的頻率提升逐漸轉向了多核和并行應用的研究方向上。截止２００７年１１月排名世界Ｔｏｐ５００的超級計算機中，約８７．６％的處理器采用多核芯片，并且約８１．２％的超級計算機采用了集群[１]結構—以ＭＰＩ為主導的并行應用的主流計算平臺。并行計算的應用需要一個統一的計算模型來與硬件所匹配。因此，如何提高并行計算在多核處理器上的應用，更好地發揮處理器的性能優勢成為當前面臨的主要問題。本文通過分析與研究各種典型的并行計算模型的優缺點以及對一些經典常用模型的擴展分析，提出一種改進的基于多核處理器機群平臺的橫向ｍｅｍｏｒｙ層次化的ＬｏｇＧＰ[２]并行計算模型，并采用典型并行算法對其進行性能測試。

１ 典型并行計算模型

并行計算模型[３]是并行算法設計的基礎，是從不同的并行計算機體系結構模型中抽象出來的。針對這種新的并行體系結構，解決并行應用面臨的問題，需要與之適應的并行計算模型。然而，不像串行計算機那樣，全世界基本上都在使用馮#8226;諾伊曼的計算模型；并行計算機沒有統一的計算模型。

理想的并行計算模型應該具有以下特征：獨立的體系結構；提供軟件開發方法；使用簡單；性能有保障；可計算成本。根據上述特征，現有計算模型按照其通訊方式可分為共享存儲類模型、消息傳遞模型和層次模型．

１．１ 共享存儲類模型

早先的并行計算模型為共享存儲類模型，分為ＰＲＡＭ模型、ＱＳＭ模型等。

（１）ＰＲＡＭ模型

ＰＲＡＭ（Ｐａｒａｌｌｅｌ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍａｃｈｉｎｅ）模型也稱之為共享存儲的ＳＩＭＤ模型，是早期最有影響力的理論模型之一，作為一種抽象的并行計算模型，被廣泛地用來評估并行算法的理論性能。ＰＲＡＭ模型由若干具有本地存儲器的處理器和一個具有無限容量的共享存儲器組成，處理器由公共的時鐘進行控制，以同步方式運行。

（２）ＱＳＭ模型

ＱＳＭ（Ｑｕｅｕｅ Ｓｈａｒｅｄ Ｍｅｍｏｒｙ）[４]模型是一個多指令、多數據流(ＭＩＭＤ)機器的共享存儲模型，由若干個處理機組成，適用于同步算法，每個處理機都執行一個同步操作隊列，每個同步操作包含：讀、計算、寫三個步驟。

１．２ 消息傳遞模型

隨著分布存儲并行機的發展，提出了各類消息傳遞模型：ＢＳＰ、ＬｏｇＰ、Ｃ３等。

（１）ＢＳＰ模型

ＢＳＰ[５](Ｂｕｌｋ Ｓｙｎｃｈｒｏｎｏｕｓ Ｐａｒａｌｌｅｌ)模型是由哈佛大學Ｖａｌｉｄａｔｅ提出的，作為體系結構和計算機語言之間的橋梁，是一種由一系列超級步組成的、分布存儲的ＭＩＭＤ計算模型。ＢＳＰ模型的計算機由三部分組成：計算單元（處理器－存儲器對）；單元間點對點通信；組件之間的同步機制。

（２）ＬｏｇＰ模型

ＬｏｇＰ[６]是１９９３年Ｃｕｌｌｅｒ等人提出的以ＭＰＣ為背景的多處理機模型，具有分布存儲、點到點通信等特點。其通信網絡有一組參數來描述： Ｌ表示通信延遲； ｏ表示通信開銷； ｇ表示通信時間間隔； ｐ表示處理器／存儲模塊個數。

（３）Ｃ３模型

Ｃ３(Ｃｏｍｐｕｔａｔｉｏｎ， Ｃｏｍｍｕｎｉｃａｔｉｏｎ， Ｃｏｎｇｅｓｔｉｏｎ)模型是有Ｈａｍｂｒｕｓｃｈ和Ｋｈｏｋｈａｒ等人提出的一個用于粗粒度并行算法設計和分析的并行計算模型，此模型分析計算通信和通信中出現的潛在擁擠。

１．３ 層次模型

ＵＭＨ(Ｕｎｉｆｏｒｍ Ｍｅｍｏｒｙ Ｈｉｅｒａｒｃｈｙ)模型是Ａｌｐｅｒｎ等人提出的，該模型是抽象化的存儲層次結構，概括了計算機層次訪問技術中與性能有關的特征。

２ 常用并行計算模型的擴展

２．１ 異步ＰＲＡＭ模型

由于ＰＲＡＭ模型是同步模型，用戶雖然感覺不到，但是所有指令均是按照同步方式操作的，浪費時間；分布式存儲的異步ＭＩＭＤ機器，超出了共享單一存儲器的作用范圍；未能描述當今并行體系結構使用的最普遍的兩種技術：線程技術和流水線預取技術。所以對ＰＲＡＭ進行擴展，得到異步ＰＲＡＭ模型[７]，簡記為ＡＰＲＡＭ，計算過程如圖１所示。該模型由ｐ個處理器組成，每個處理器都有其局部時鐘和局部程序，通過添加同步路障（Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ Ｂａｒｒｉｅｒ）來控制程序的執行；共享全局存儲器；取消全局時鐘，各處理器一步、獨立地執行各自的指令。定量化的成本參數是ＡＰＲＡＭ模型比ＰＲＡＭ更接近于實際的并行機。

２．２ ＣＳＡ－ＢＳＰ模型

ＢＳＰ模型中，超步即連續的兩個同步之間的周期，如圖２所示。

每個超步由計算、通信和同步組成，但是同步操作使得超步之間相互無關，限制了處理機之間的異步執行 ，可能導致出現互相等待，降低了處理機的執行效率。為改進ＢＳＰ程序的性能，提出了一些建立在ＢＳＰ模型基礎上的擴展模型：異步ＢＳＰ模型（Ａ－ＢＳＰ）；ＨＢＳＰ模型；計算－發送段ＢＳＰ模型（ＣＳＡ－ＢＳＰ）。ＣＳＡ－ＢＳＰ模型中一個計算－發送段（ＣＳ段）由計算部分和數據部分組成，ＣＳ－超步是由一系列計算－發送段和接受語句組成的。相對于Ａ－ＢＳＰ模型，ＣＳＰ－ＢＳＰ模型中，進程執行超步時，不必完成其所有計算，只需完成發送數據所在的ＣＳ－段的計算，即可執行下一條指令。

２．３ ＬｏｇＰ模型擴展

ＬｏｇＰ模型是帶有緩沖的異步消息傳遞機制，采用異步通信的互聯網絡，具有良好的移植性，能體現出多線程技術。通過參數ｌ、ｏ和ｇ刻畫了通信網絡的特性，屏蔽了網絡拓撲、選路算法和通信協議等細節，加上參數ｐ刻畫了并行機的主要瓶頸。對于每個節點處理器，接收和發送消息時均要付出開銷ｏ，但由于并行機的硬件效率問題，ＬｏｇＰ模型不支持長消息處理；在共享主存模式中，遠距離讀寫操作視為兩次消息傳遞，沒有考慮計算機硬件與軟件的影響：Ｃａｃｈｅ命中率、進程同步和流水線預取技術等。基于對ＬｏｇＰ模型的改進，又提出了很多擴展模型，如：ＬｏｇＧＰ、ＬｏｇＧＰＳ、ＬｏｇＧＰＣ、ＬｏｇＰＱ等。ＬｏｇＧＰ模型對長消息做了特別處理，添加參數Ｇ，代表長消息每字節間距，如圖３所示。

ＬｏｇＧＰＳ是對ＬｏｇＧＰ的擴展，添加同步機制，定義一個表示消息長度閾值的參數Ｓ。ＬｏｇＧＰＣ是在ＬｏｇＧＰ的基礎上添加通信網絡和網絡接口。ＬｏｇＰＱ則是添加消息隊列，處理機發送和接收隊列。

多核處理器，將多個相對簡單、同構的處理器核集成到同一塊芯片上，而且這些處理器核都共享片上高速緩存（Ｃａｃｈｅ）。其中，片上多核處理器（ＣＭＰ）技術的主要特點有：功耗低、延遲小、線程級并行等。隨著多核處理器的普遍應用，大規模并行計算機都采用了多核處理器，構件集群平臺，多核處理器集群的比較見表１。所以，在并行體系結構上，需要與之相適應的并行計算模型。第一節介紹的計算模型大多是以單核處理器為基礎開發的，針對共享存儲器結構和分布式存儲結構的。近代計算機中，由于寄存器、高速緩存、主存對并行計算機性能影響越來越大，不同層次ｍｅｍｏｒｙ間流動的性能受數分布的影響，存在系統通信開銷。Ｍｅｍｏｒｙ層次化并行計算模型也越來越少重視，如：ｍｅｍｏｒｙ ＬｏｇＰ、ＬｏｇｎＰ／Ｌｏｇ３Ｐ。

現代的并行計算平臺大多是建立在多核處理器機群平臺上的，基于此原因，本文提出一個新的并行計算模型ｍｚＬｏｇＧＰ，這是基于多核機群平臺的、考慮異構性和節點計算能力的非獨占性的模型，充分考慮了網絡擁塞對節點間通信存在的影響以及ｍｅｍｏｒｙ層次化對多核處理器機群消息通信性能的影響。其中，ｍ代表多核環境下ｍｅｍｏｒｙ層次化的深度， ｚ代表考慮網絡擁塞指數，表示消息在當前網絡存在擁塞和不存在擁塞時傳遞所消耗的時間比，用于反映網絡擁塞的程度。

３ ｍｚＬｏｇＧＰ模型

并行系統由多個計算節點通過網絡連接組成。任何兩個計算節點之間可以進行通信，當網絡中存在過多的數據包時，網絡性能會下降，由此而引發網絡擁塞。 ｍｚＬｏｇＧＰ模型是應用于多核處理器機群平臺的模型，考慮到了網絡方面對通信開銷所帶來的影響，使測得進程通訊開銷更精確。網絡擁塞程度，延時大小和帶寬都是造成網絡損耗主要原因，所以，可以選擇更高性能的硬件資源，使得集群系統盡可能地減少網絡損耗。

ｍｚＬｏｇＧＰ模型的參數有：Ｐ，ｏ，ｌ，ｇ４個ＬｏｇＰ的基本參數，根據第一節所講，Ｐ代表處理器／存儲器模塊個數（節點個數），由多核處理器組成的并行系統一般有Ｐ個計算節點個數；ｏ表示程序執行時互聯網絡的通信開銷，包括發送開銷和接收開銷；Ｌ表示網絡中消息傳遞所產生的延遲；ｇ表示處理器可連續進行消息發送或接收的最小時間間隔。對于一個具體的并行機，網絡傳送一個Ｍ位的消息所花的時間為

Ｔ（Ｍ，Ｈ）＝Ｔｓｅｎｄ＋[Ｍ／ｗ]＋Ｈ?觹ｒ＋Ｔｒｅｖ （１）

其中，ｗ為通道帶寬；Ｈ表示Ｈ個跨步(Ｈｏｐｓ)；Ｔｓｅｎｄ為接收開銷，即處理器向網絡傳輸數據前為網絡接口準備數據的時間；Ｔｒｅｖ為接收開銷，即處理器收到最后一條數據的處理時間；[Ｍ／ｗ]為處理器發送消息到網上所需的時間；Ｈ?觹ｒ為最后一個數據通過網絡到達目標節點的時間。在ＬｏｇＰ模型中，對網絡的容量增加了限制，以防止網絡重載，出現資源競爭而浪費時間，模型參數選取如下：系統通訊開銷ｏ＝( Ｔｓｅｎｄ＋Ｔｒｅｖ)／２，Ｌ＝Ｈ?觹ｒ＋[Ｍ／ｗ]，ｇ＝[Ｍ／ｂ]，ｂ為處理器對剖寬度。

ＬｏｇＰ模型擴展參數：Ｇ，Ｓ，ｌ，ｍ，ｚ。由于ＬｏｇＰ模型中不支持長消息傳遞，引入參數Ｇ，代表節點發送或接收消息時單位長度數據的時間間隔；Ｓ表示單位時間內處理器處理的消息數，即計算速度；ｌ表示同步時間機制，用于各個超步之間路障同步對并行程序執行時間影響的描述；ｚ為網絡擁塞的程度，表示消息在當前網絡存在擁塞和不存在擁塞時傳遞所消耗的時間比， 用于考慮網絡中傳遞消息的額外時間開銷。

在多核處理器機群平臺上，由于多核處理器中ＣＰＵ和存儲器能量提升失衡，不能滿足高性能計算對硬件資源的需求，導致需要更多的核供計算使用，使多核不斷地向眾核發展，從而使處理器墻問題更加嚴重，非一致性訪問內存成為必然的發展趨勢；因存儲器的差異而導致的帶寬和通信延遲不匹配，使得并行更加層次化。因此，這里引入ｍ參數，表示ｍｅｍｏｒｙ層次化深度，方便計算因ｍｅｍｏｒｙ存取過程而產生的通訊開銷。

ｍｚＬｏｇＧＰ并行計算模型中，考慮影響系統通信開銷的兩大因素：ｍｅｍｏｒｙ和ｎｅｔｗｏｒｋ。引入參數ｍ計算ｍｅｍｏｒｙ中的通信開銷；引入參數ｚ計算網路中的通信開銷。結構如圖４所示。

由于緩存和主存互聯結構的差異，多核處理器中片內通信、片間通信以及處理器節點間通信帶寬和延遲不同，導致ｍｅｍｏｒｙ層次化加深，這一過程中的通信統稱為節點內通信。對于短消息的傳遞，節點內通信較小，處理器各個核之間通信延遲較小；當傳送較長消息，處理器負荷增加，核間通信延遲增大，與節點間通信接近。劃分通信等級使測得的程序實際執行時間更加精確，以減小誤差。

并行程序可劃分為若干個超級步[７](Ｓｕｐｅｒｓｔｅｐ)，用路障(Ｂ－ａｒｒｉｅｒ)分隔兩個相鄰的超級步，每個超級步中計算節點之間互相進行點對點通信。并行程序執行的總時間是所有計算節點的運行時間和節點間的通信時間的總和。一個超級步中包含若干個計算節點，所有超級步的計算時間和通信時間的總和為程序執行時間。假設一個并行程序由ｎ個超級步組成，則預測模型的通信時間開銷為：

Ｔ＝Ｔｉ＋Ｔｊ＋ｎｌｎｅｔ （２）

其中，Ｔｉ為超級步的節點內計算時間；Ｔｊ為超級步節點間通信時間；ｌｎｅｔ為互聯網絡中的通信延遲。節點間通信時間受互聯網絡中帶寬和延遲的影響，而節點內的計算時間為：

Ｔｉ＝ｏｍ＋ｌｍ （３）

ｏｍ表示處理器／存儲器處理時間；ｌｍ為消息在處理器和存儲器內的執行開銷，減小這個開銷的有效方法是改變中間件、硬件的性能，提高數據的吞吐率或帶寬。由于多核處理器機群平臺上，消息傳遞包括網絡傳遞、ＣＰＵ／ｍｅｍｏｒｙ處理、內存拷貝和緩存操作等，這些通信中間件的性能關系著這條消息傳遞的效率，通信層次明顯。軟件層次的ｍｅｍｏｒｙ層次化反映在中間件的性能上，網絡通信開銷從硬件層次反映了通信網絡的性能。ｍｚＬｏｇＧＰ模型刻畫了多核處理器機群計算平臺處理器通信和網絡通信的性能瓶頸和特征。

ｍｚＬｏｇＧＰ模型節點間通信與ＬｏｇＧＰ差別不大，其特征是可能存在網絡擁塞；是否獨自占有計算資源，節點是同構還是異構。首先考慮網絡中不存在擁塞，節點獨占計算資源，這是理想的網絡信息傳遞模式。

這種情況下，節點處理器向另一節點處理器發送一條短消息，需要的時間為：ｏｍ＋ｌｍ＋ｏｎｅｔ＋Ｌ，其中，ｏｎｅｔ是網絡中接受或發送消息的通信開銷。當發送長消息時，需要考慮參數Ｇ，假設一條消息長度為ｘ字節，消息的通信開銷為：ｏｍ＋ｌｍ＋ｏｎｅｔ＋(ｘ－１)Ｇ＋Ｌ，其中，處理器在第一個字節發送前，為網絡接口的準備時間即為消息的發送時間，消息分為ｘ等分，每個字節的發送需要Ｇ時間；網絡的通信延遲為Ｌ。接收方的處理器和發送方的處理器在接收或發送消息時不能進行其他操作。

當發送多條消息時，處理器發送完一條消息后，至少要等待ｇ時間才能發送第二條消息，第二條消息進入網絡的時間為ｏｍ＋ｌｍ＋(ｘ１－１)Ｇ＋ｇ，由于處理器連續處理消息的最小時間間隔的限制，處理器不能不間斷地連續發送或接收數據。

理想的無網絡擁塞情況下，消息傳遞效率最高，現實中很難實現，當網絡中存在擁塞時，節點不能享有全部的計算資源，需要一定的時間來處理網絡擁塞所造成的延遲。消息在網絡中傳遞會出現等待現象，所以考慮了網絡擁塞指數ｚ，消息的通信開銷為ｏｍ＋ｌｍ＋(ｘ１－１)ｚ?觹Ｇ＋ｇ＋ｚＬ。

并行程序的執行時間，在沒有重疊操作的情況下為：

Ｔ＝Ｔｃｏｍ＋Ｔｐ＋Ｔｃｏｎｎ （４）

其中，Ｔｃｏｍ＝Ｔｉ，為節點內的計算時間； Ｔｐ為并行執行的開銷時間，包括進程切換、結束等時間；Ｔｃｏｎｎ為網絡中的交互通信時間，受帶寬、路障、延遲等影響。層次化存儲器中，一個層次包含三個參數：帶寬、延遲和容量，分為縱向和橫向層次化，模型支持節點內和節點間通信互連拓撲，抽象化了ｍｅｍｏｒｙ橫向和縱向層次化，大大優化了節點內的計算時間。 因網絡擁塞所產生額外開銷，是造成并行執行的預測時間開銷和實測時間開銷的關鍵原因。ｍｚＬｏｇＧＰ模型即采用了ｍｅｍｏｒｙ層次化技術，減少了節點內執行計算因ＣＰＵ和ｍｅｍｏｒｙ速度不匹配而產生的額外開銷；考慮了網絡擁塞情況，驗證消息在網絡中傳遞時所帶來的額外損耗。

４ 模型評價與分析

本實驗采用４節點機群，每個節點有２顆４核處理器，操作系統內核版本是Ｌｉｎｕｘ ｋｅｒｎｅｌ ２．６．１８，開發環境為ｍｐｉｃｈ ２－１．３．２ｐ１＋ＶＣ６．０，采用ＭＰＩ－Ｓｅｎｄ、ＭＰＩ－Ｒｅｃｖ接口測試ＲＴＴ的方法獲取通信的時間開銷，分別對不同大小、不同步長的數據進行了點對點通信和一對多集合通信的測試。

實驗采用單字節消息的連續發送、連續Ｐｉｎｇ＿Ｐｏｎｇ、一次Ｐｉｎｇ＿Ｐｏｎｇ以及盡可能大數據的消息的Ｐｉｎｇ＿Ｐｏｎｇ等，得到ＭＰＩ環境下，節點參數如表２所示。

下面測試ｍｚＬｏｇＧＰ模型在網絡擁塞指數ｚ＝１．１的情況下的程序執行時間。實驗以Ｊａｃｏｂｉ 迭代算法[８]為例，用ｍｚ－ＬｏｇＧＰ模型對算法的執行過程進行分析，在搭建的多核處理器機群平臺上驗證模型的有效性和實用性。

Ｊａｃｏｂｉ 迭代具有良好的局部性，可取得很高的并行性，可將參加迭代的數據按塊分割，如圖５所示，各塊之間處理相鄰元素通信外，各塊內部也可進行獨立的并行計算，可降低計算的通信開銷，有利于并行效果。

假設需要迭代的數據是Ｍ?觹Ｍ的二維數組Ａ(Ｍ，Ｍ)，令Ｍ＝４?觹Ｎ，按圖５進行數據劃分，則分布在四個不同進程上的數據分別是：進程０，Ａ(Ｍ，１，Ｎ)， 進程１，Ａ(Ｍ，Ｎ＋１，２?觹Ｎ)，進程２，Ａ(Ｍ，２?觹Ｎ＋１，３?觹Ｎ)，進程３，Ａ(３?觹Ｎ＋１，Ｍ)。

根據ｍｚＬｏｇＧＰ模型的原理，在算法的每個步驟之間插入Ｂａｒｒｉｅｒ語句，將該算法分成４個超級步，以４級ｍｅｍｏｒｙ橫向層次化技術求出機群平臺上程序執行的節點內計算時間，再利用表２給出的參數，計算出Ｊａｃｏｂｉ 迭代算法在ｍｚＬｏｇＧＰ模型下的分別傳送５１２ＫＢ和２ＭＢ數據所運行的時間，并將實驗測得實際運行時間與預測時間作比較。上述算法考慮了在阻塞指數ｚ＝１．１的情況，ＭＰＩ環境下。