基于對(duì)象的隱式并行編程眾核體系結(jié)構(gòu)研究

譚 海

(1.北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京100081;2.東華理工大學(xué)信息工程學(xué)院，江西南昌330013;3.東華理工大學(xué)核技術(shù)應(yīng)用教育部工程研究中心，江西南昌330013)

0 引言

目前芯片制造工藝已經(jīng)具備百億晶體管的整合能力，且每過(guò)兩年繼續(xù)翻倍，出現(xiàn)功耗、片上網(wǎng)絡(luò)延遲和存儲(chǔ)帶寬等問(wèn)題，如何利用芯片上集成的海量晶體管資源設(shè)計(jì)高性能處理器成為研究的熱點(diǎn)。采用多核結(jié)構(gòu)在一定程度有效能夠減緩了上述問(wèn)題，但是晶體管規(guī)模數(shù)變的過(guò)大時(shí)，出現(xiàn)過(guò)多的亞閾值漏電，導(dǎo)致供應(yīng)電壓按比例下降，系統(tǒng)性能達(dá)不到按照摩爾定律所昭示的應(yīng)有提升，反而產(chǎn)生大功耗問(wèn)題，多核結(jié)構(gòu)隨之遇到瓶頸，唯一的方法就是采用更多的較小單核 (眾核)來(lái)解決瓶頸問(wèn)題。

當(dāng)前的軟件結(jié)構(gòu)可以在多核結(jié)構(gòu)上得到較好的擴(kuò)展，但如果超過(guò)八個(gè)處理器核，當(dāng)前軟件結(jié)構(gòu)的擴(kuò)展能力將會(huì)很差［1］。Berkele認(rèn)為未來(lái)的并行計(jì)算必須有利于傳統(tǒng)科學(xué)計(jì)算的并行化［2］，范東睿研究員指出眾核的挑戰(zhàn)是供數(shù)受限于片外帶寬、并行系統(tǒng)難以高效率擴(kuò)展、并行編程困難［3］，提高應(yīng)用程序開(kāi)發(fā)產(chǎn)能同時(shí)獲得并行性能收益是多核大眾化并行計(jì)算研究的核心目標(biāo)。微軟公司在2007年6月25日在美國(guó)西雅圖召開(kāi)第一個(gè)以Many-Core為主題的Workshop，討論眾核軟件設(shè)計(jì)應(yīng)如何開(kāi)展，并于該年11月發(fā)表了THE MANYCORE SHIFT:Microsoft Parallel Computing Initiative Ushers Computing into the Next Era宣言，宣布轉(zhuǎn)入對(duì)眾核系統(tǒng)軟件的研究，基于眾核的軟件設(shè)計(jì)成為研究的熱點(diǎn)之一。

跟現(xiàn)有多核計(jì)算強(qiáng)調(diào)專(zhuān)門(mén)領(lǐng)域、需要專(zhuān)門(mén)知識(shí)的程序員不同，眾核計(jì)算關(guān)注通用平臺(tái)，基本涉及到所有應(yīng)用領(lǐng)域，支持所有普通程序員進(jìn)行眾核編程開(kāi)發(fā)，即大眾化通用并行［4］。具體來(lái)說(shuō)，多核計(jì)算關(guān)注高性能計(jì)算和服務(wù)計(jì)算領(lǐng)域、采用自底向上的硬件驅(qū)動(dòng)方法、追求性能最大化目標(biāo);而眾核計(jì)算關(guān)注個(gè)人移動(dòng)計(jì)算、采用自頂向下的應(yīng)用驅(qū)動(dòng)開(kāi)發(fā)方法、追求最大化產(chǎn)能目標(biāo)。

1 顯式并行編程模式及缺陷

國(guó)內(nèi)外對(duì)多核的研究主要是面向計(jì)算密集型和數(shù)據(jù)密集型的專(zhuān)用計(jì)算領(lǐng)域，對(duì)處理器核的基本結(jié)構(gòu) (包括指令系統(tǒng)、粒度等)、處理器核之間的互連通信和同步機(jī)制 (共享內(nèi)存、消息傳遞和數(shù)據(jù)并行等)、片上存儲(chǔ)器的組織形式(局部/全局、Cache/可尋址存儲(chǔ)器、SRAM/DRAM等)和多線程的基本機(jī)制等的研究［5］。由于一個(gè)時(shí)鐘周期內(nèi)信號(hào)可傳輸?shù)木嚯x非常有限，處理器核不可能在指令執(zhí)行期間就完成與其它處理器核的數(shù)據(jù)通信，不同核處理器之間的通信應(yīng)該盡可能的采用異步機(jī)制且能容忍較長(zhǎng)的延遲，不同專(zhuān)用并行機(jī)底層硬件和系統(tǒng)軟件之間差別較大，這些因素造成了目前的并行程序開(kāi)發(fā)與現(xiàn)有的大眾化程序開(kāi)發(fā)之間很大的不同，前者需要通曉底層硬件結(jié)構(gòu)，編譯器和專(zhuān)用的并行開(kāi)發(fā)語(yǔ)言的“專(zhuān)家級(jí)”程序員，程序開(kāi)發(fā)和維護(hù)成本高，并行程序開(kāi)發(fā)過(guò)程容易出錯(cuò)，且編寫(xiě)出來(lái)的程序不通用，只能在固定的計(jì)算機(jī)上去運(yùn)行，程序移植性差，這類(lèi)需要使用諸如MPI、Charm++等專(zhuān)門(mén)并行編程工具的模式稱(chēng)之為顯式并行編程模式［6］。在顯式編程模式下，為了適應(yīng)眾核硬件并行程序設(shè)計(jì)，得分別在算法、編程模型、編程語(yǔ)言、編譯器和操作系統(tǒng)等方面全套重新設(shè)計(jì)，這樣的變革將是巨大的，成本很大，對(duì)普通程序員要求太高，將嚴(yán)重影響眾核的推廣和使用，顯式并行編程模式是多核乃至眾核將來(lái)發(fā)展的瓶頸。

如何繼續(xù)使用而不是拋棄現(xiàn)有的大量程序 (軟件)代碼，如何并行現(xiàn)有串行代碼及提高程序執(zhí)行效率;如何利用而不是拋棄現(xiàn)有的開(kāi)發(fā)環(huán)境和工具等問(wèn)題是通用眾核技術(shù)發(fā)展必須要解決的問(wèn)題。

2 隱式并行編程模式

針對(duì)現(xiàn)有顯式編程模式成本大、容易出錯(cuò)且不能兼容現(xiàn)有開(kāi)發(fā)工具和程序的不足，我們提出了面向?qū)ο蟮幕趯?duì)象粒度的隱式編程模式，在底層硬件和編譯技術(shù)的支撐下，兼容現(xiàn)有的串行程序開(kāi)發(fā)模式、開(kāi)發(fā)技術(shù)和開(kāi)發(fā)工具，降低并行程序的開(kāi)發(fā)成本和開(kāi)發(fā)風(fēng)險(xiǎn)，并通過(guò)反編譯技術(shù)和軟件逆分析手段，實(shí)現(xiàn)對(duì)現(xiàn)有的串行二進(jìn)制代碼并行化，使將來(lái)的眾核時(shí)代不至于拋棄現(xiàn)有的這些代碼成果。

相對(duì)于顯式并行編程模式，隱式并行編程模式盡量利用現(xiàn)有的開(kāi)發(fā)工具、開(kāi)發(fā)環(huán)境和程序開(kāi)發(fā)語(yǔ)言等技術(shù)手段和成果，通過(guò)在計(jì)算機(jī)體系結(jié)構(gòu)底層的硬件支撐進(jìn)行專(zhuān)門(mén)設(shè)計(jì)、編譯器優(yōu)化等技術(shù)手段，使在現(xiàn)有的開(kāi)發(fā)環(huán)境和開(kāi)發(fā)工具下開(kāi)發(fā)出來(lái)的程序 (比如面向?qū)ο蟮某绦?能夠無(wú)縫的運(yùn)行在多核/眾核系統(tǒng)上，這樣開(kāi)發(fā)的程序成本低、開(kāi)發(fā)過(guò)程不容易出錯(cuò)、程序移植性好，對(duì)程序員要求低，并能同時(shí)獲得較好的應(yīng)用性能和產(chǎn)能目標(biāo)。

目前軟件技術(shù)的高度發(fā)展，以C++和Java為代表的面向?qū)ο蟾呒?jí)程序設(shè)計(jì)語(yǔ)言的產(chǎn)生，遵循人類(lèi)思維方式，采用適合人類(lèi)的處理問(wèn)題的思考模式，以對(duì)象作為編程單元來(lái)編制程序，對(duì)象和對(duì)象之間相對(duì)獨(dú)立，對(duì)象具有封裝、繼承和多態(tài)性的特點(diǎn)，對(duì)象的方法和數(shù)據(jù)具有私有、公有和保護(hù)三種訪問(wèn)模式，程序的代碼段主要由對(duì)象的方法調(diào)用組成，對(duì)象和對(duì)象之間通過(guò)消息機(jī)制完成通信。雖然在單核模式下，這些程序是串行執(zhí)行的，對(duì)象的方法調(diào)用根據(jù)編制的代碼序列串行順序依次調(diào)用，顯然這些對(duì)象及其方法的調(diào)用是能夠并行進(jìn)行。這些對(duì)象作為一種高度并行化的顆粒，能夠直接映射到眾核中的不同核去運(yùn)行，通過(guò)處理器核間的通信鏈路來(lái)完成對(duì)象間的消息傳遞。現(xiàn)有的并 行 粒 度 有 循 環(huán)［7］、 函 數(shù)［8］、 代 碼 復(fù) 用［9］和 軟 件 流水［10-11］，需要程序員進(jìn)行專(zhuān)門(mén)處理，對(duì)程序員要求較高，不通用，且不能解決現(xiàn)有代碼的并行問(wèn)題，屬于顯式編程模式，面向?qū)ο蟮幕趯?duì)象并行粒度編程模式屬于隱式編程模式，易于實(shí)現(xiàn)，并行度高，能夠較好的解決現(xiàn)有代碼的并行問(wèn)題，是眾核發(fā)展技術(shù)的出路。

3 基于對(duì)象的隱式并行編程模式研究

通過(guò)編譯器和底層硬件支撐，現(xiàn)有的大眾化程序員能夠利用現(xiàn)有的面向?qū)ο箝_(kāi)發(fā)技術(shù)和開(kāi)發(fā)工具輕松開(kāi)發(fā)出對(duì)象級(jí)粒度的并行程序，達(dá)到應(yīng)用程序開(kāi)發(fā)產(chǎn)能和并行性能收益同步提高的大眾化并行計(jì)算研究的核心目標(biāo)，完成對(duì)高級(jí)語(yǔ)言對(duì)象級(jí)并行粒度的隱式編程模式的研究;應(yīng)用反編譯技術(shù)和軟件逆向分析，對(duì)現(xiàn)有二進(jìn)制代碼 (面向?qū)ο蟪绦蛩鶎?xiě))中的對(duì)象級(jí)粒度進(jìn)行識(shí)別和重構(gòu)。

3.1 研究目標(biāo)

通過(guò)研究，對(duì)編譯器進(jìn)行改進(jìn)，完成在二進(jìn)制代碼中對(duì)同一對(duì)象的方法和變量的統(tǒng)一存放，并加以標(biāo)注，片上處理器調(diào)度時(shí)根據(jù)該標(biāo)注識(shí)別對(duì)象，完成核間數(shù)據(jù)通信和參數(shù)傳遞的研究;完成現(xiàn)有二進(jìn)制代碼中對(duì)象粒度的識(shí)別和重構(gòu)，實(shí)現(xiàn)串行程序并行化;構(gòu)建硬件支撐模塊，根據(jù)程序并發(fā)度調(diào)度二進(jìn)制代碼中標(biāo)注的對(duì)象，并將這些對(duì)象調(diào)度到不同核上運(yùn)行;分析并找出對(duì)象間所有可能存在的數(shù)據(jù)共享方式。

3.2 關(guān)鍵問(wèn)題

為了解決上述關(guān)鍵問(wèn)題，主要需完成下面幾個(gè)方面的研究:

(1)通過(guò)對(duì)現(xiàn)有面向?qū)ο缶幾g器的改進(jìn)，完成將現(xiàn)有面向?qū)ο笳Z(yǔ)言中對(duì)象間的消息機(jī)制改進(jìn)為核間通信手段的研究，進(jìn)行不同對(duì)象 (核間)方法執(zhí)行時(shí)參數(shù)傳遞及結(jié)果返回機(jī)制的研究，并在二進(jìn)制代碼中對(duì)對(duì)象加以標(biāo)記，同一對(duì)象的不同方法放在一起 (正文段)，同一對(duì)象的不同變量放置在一起 (數(shù)據(jù)段);

(2)由于對(duì)象存在封裝性，完成對(duì)象級(jí)并行粒度所有可能存在的共享數(shù)據(jù)及對(duì)其沖突類(lèi)型進(jìn)行評(píng)估;

(3)通過(guò)構(gòu)建合適的底層硬件模塊，完成對(duì)二進(jìn)制代碼中的對(duì)象及其方法的識(shí)別 (現(xiàn)在的串行二進(jìn)制代碼，改造后的工具寫(xiě)出來(lái)的程序中對(duì)象已有標(biāo)注)，增加處理器對(duì)象訪存指令，分析程序并發(fā)度，每個(gè)程序的對(duì)象被調(diào)度到3-8個(gè)核上運(yùn)行，并實(shí)現(xiàn)完成片上計(jì)算時(shí)間和傳輸時(shí)間的錯(cuò)開(kāi)、調(diào)度管理。

4 體系結(jié)構(gòu)設(shè)計(jì)

我們采用圖1所示的三維眾核體系結(jié)構(gòu)，由一層處理核層和多層cache層組成，層間采用3D疊片技術(shù)互連，處理核層各核間采用2D Mesh互連，cache層各cache塊節(jié)點(diǎn)間采用半互連長(zhǎng)互連線互連，處理核由L1 T-cache、I/D-cache和路由器組成，其中T-cache是L1級(jí)事務(wù)內(nèi)存，該體系結(jié)構(gòu)存儲(chǔ)架構(gòu)采用如圖2所示結(jié)構(gòu)，支持對(duì)象直接訪問(wèn)。

每個(gè)面向?qū)ο蟪绦蚋鶕?jù)程序規(guī)模大小，把它的對(duì)象分別調(diào)度到3-8個(gè)核上，完成對(duì)象到處理器核的分配，為了利于指令緩存和數(shù)據(jù)緩存的命中率和實(shí)施局部性原理，把該對(duì)象的方法存儲(chǔ)在離核較近的地址空間段中，由對(duì)象所分配的核負(fù)責(zé)該對(duì)象所有方法的運(yùn)行 (有的對(duì)象的方法調(diào)用頻率高，調(diào)度時(shí)需要考慮到這些對(duì)象在不同核上的負(fù)載平衡)，對(duì)象實(shí)例生成時(shí)，變量部分考慮存儲(chǔ)在離處理器核較近的內(nèi)存空間段;程序運(yùn)行時(shí)，先經(jīng)由硬件支撐機(jī)構(gòu)遍歷2-3遍代碼，分析其合適的并發(fā)度，完成程序中對(duì)象的識(shí)別后再分配對(duì)象于不同核，通過(guò)這些核并發(fā)執(zhí)行這些對(duì)象。

該體系結(jié)構(gòu)是一種可重構(gòu)的異構(gòu)多核系統(tǒng)，結(jié)點(diǎn)處理器核可以是異構(gòu)的，可以由眾多的處理器核組成構(gòu)成眾核系統(tǒng)，系統(tǒng)采用二級(jí)緩存系統(tǒng)，每個(gè)單核有自己的私有一級(jí)緩存L1，L1由指令緩存、數(shù)據(jù)緩存和事務(wù)緩存構(gòu)成，數(shù)據(jù)緩存和事務(wù)緩存采用多端口Cache，且數(shù)據(jù)緩存和事務(wù)緩存之間能夠進(jìn)行數(shù)據(jù)交換。具體的布局布線策略可采用斜布線和3D布線技術(shù)來(lái)實(shí)現(xiàn)，處理器核和存儲(chǔ)器DRAM間數(shù)據(jù)通信可以采用圖3所示的3D通路，處理器和存儲(chǔ)的組合示意圖如圖4所示。

5 眾核系統(tǒng)性能評(píng)價(jià)

并行程序在多個(gè)處理核執(zhí)行時(shí)需要在不同核間交互數(shù)據(jù)和信息，多個(gè)程序在多個(gè)核同時(shí)并行執(zhí)行時(shí)可以通過(guò)錯(cuò)開(kāi)片上計(jì)算時(shí)間和片上網(wǎng)絡(luò)通信時(shí)間，減少核間通信數(shù)據(jù)堵塞。由于眾核系統(tǒng)往往承載多個(gè)程序的運(yùn)行，當(dāng)處理器核數(shù)變多時(shí)，眾核系統(tǒng)的整體系統(tǒng)性能就能得到提升，具有同樣緩存和功耗，不同核數(shù)規(guī)模組成的系統(tǒng)性能比較如圖5所示 (左圖是大、中、小三個(gè)單核性能和規(guī)模的比較，右圖是在同晶體管數(shù)規(guī)模情況下，分別由少量大核、中量中核和多量小核組成的系統(tǒng)在單個(gè)、多個(gè)程序運(yùn)行系統(tǒng)整體性能的對(duì)比)，從圖中可以看出雖然小核晶體管規(guī)模只有大核的1/12，但是它的性能卻是大核的1/3，多個(gè)小核組成的系統(tǒng)整體吞吐量比少量大核組成的系統(tǒng)吞吐量要大得多，衡量眾核系統(tǒng)的性能不能只考慮某個(gè)應(yīng)用程序的并行度，而應(yīng)該考慮任務(wù)及應(yīng)用程序級(jí)別的并行性。

圖5 不同核數(shù)的系統(tǒng)性能比較

6 結(jié)論和展望

提出的基于對(duì)象的隱式并行編程眾核體系結(jié)構(gòu)，解決眾核時(shí)代繼續(xù)使用現(xiàn)有的二進(jìn)制代碼、現(xiàn)有的開(kāi)發(fā)技術(shù)和開(kāi)發(fā)工具，減少并行程序開(kāi)發(fā)成本和風(fēng)險(xiǎn)，提出的對(duì)象級(jí)并行粒度眾核軟件技術(shù)的研究，對(duì)眾核時(shí)代的程序并行化具有借鑒意義。

7 結(jié)束語(yǔ)

本文首先通過(guò)分析得出面向通用程序大眾化并行計(jì)算是將來(lái)眾核發(fā)展的方向，接著對(duì)其片上網(wǎng)絡(luò)、并行編程模式和存儲(chǔ)架構(gòu)等關(guān)鍵技術(shù)進(jìn)行深入研究，針對(duì)現(xiàn)有的顯式編程模式編程成本大、容易出錯(cuò)且不能兼容現(xiàn)有開(kāi)發(fā)工具和程序的不足，提出了面向?qū)ο蟮幕趯?duì)象粒度的隱式編程模式，在底層硬件和編譯技術(shù)支撐下，兼容現(xiàn)有的串行程序開(kāi)發(fā)模式、開(kāi)發(fā)技術(shù)和開(kāi)發(fā)工具，降低并行程序開(kāi)發(fā)成本和開(kāi)發(fā)風(fēng)險(xiǎn)，并通過(guò)反編譯和軟件逆分析技術(shù)手段，實(shí)現(xiàn)對(duì)現(xiàn)有的串行二進(jìn)制代碼并行化，使將來(lái)的眾核時(shí)代不至于拋棄現(xiàn)有的這些代碼成果;并提出了相應(yīng)的體系結(jié)構(gòu)實(shí)現(xiàn)，這些關(guān)鍵技術(shù)解決了眾核技術(shù)發(fā)展的瓶頸。

［1］CAOYangjie，YANGHaibing，QIAN Depei，et al.On Adaptability of the runtime environment for emerging Multi-Core programming models［J］.Journal of Xi'an Jiaotong University，2011，45(6):130-134(in Chinese).［曹仰杰，楊海兵，錢(qián)德沛，等.多核編程模型運(yùn)行時(shí)環(huán)境的自適應(yīng)性研究［J］.西安交通大學(xué)學(xué)報(bào)，2011，45(6):130-134.］

［2］Kasanovic.The parallel computing laboratory at U.C.Berkeley:A research agenda based on the berkeley view［R］.Berkeley:UCB，2008:1-25.

［3］LIU Duo， SHAO Zili， WANG Meng， et al.Optimal loop parallelization for maximizing iteration-level parallelism ［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23(3):564-572.

［4］YANG Jixiang，TAN Guozhen，WANG Rongsheng.Some key issues and their research progress in multicore software［J］.Acta Electronica Sinica，2010，38(9):2140-2146(in Chinese).［楊際祥，譚國(guó)真，王榮生.多核軟件的幾個(gè)關(guān)鍵問(wèn)題及其研究進(jìn)展 ［J］.電子學(xué)報(bào)，2010，38(9):2140-2146.］

［5］Hill M D，Marty M R.Amdahl＇s law in the multicore era ［J］.Computer，2008，41(7):33-38.

［6］W Hwu，S Ryoo，SZ Ueng，et al.Implicitly parallel programming models for thousand-core microprocessors［C］//Design Automation Conference.San Diego，CA，USA:ACM，2007:754-759.

［7］ZHANG Wangyuan，F(xiàn)U Xin，LI Tao，et al.An analysis of microarchitecture vulnerability to soft errors on simultaneous multithreaded architectures［C］//IEEE International Symposium on Performance Analysis of Systems ＆ Software.San Jose，CA，USA:IEEE，2007:169-178.

［8］Balakrishnan S，Sohi G S.Program demultiplexing:Data-flow based speculative parallelization of methods in sequential programs［C］//Int＇l Symp.Computer Architecture.Boston，MA，USA:IEEE，2006:302-313.

［9］Ben Lee.Performance evaluation of dynamic speculative multithreading with the cascadia architecture［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21(1):47-59.

［10］Bridges M J，Vachharajani N，ZHANGY，et al.Revisiting the sequential programming model for multi-core［C］//Proc 40th IEEE/ACM Int'l Symp.Microarchitecture.Chicago，IL，USA:IEEE，2007:69-84.

［11］Tian C，F(xiàn)eng M，Nagarajan V.Copy or discard execution model for speculative parallelization on multicores ［C］//Proc 41st Int＇l IEEE/ACM Symp.Microarchitecture.Lake Como，Italy:IEEE，2008:300-341.