基于對象的隱式并行編程眾核體系結構研究

譚 海

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

0 引言

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

當前的軟件結構可以在多核結構上得到較好的擴展，但如果超過八個處理器核，當前軟件結構的擴展能力將會很差［1］。Berkele認為未來的并行計算必須有利于傳統科學計算的并行化［2］，范東睿研究員指出眾核的挑戰是供數受限于片外帶寬、并行系統難以高效率擴展、并行編程困難［3］，提高應用程序開發產能同時獲得并行性能收益是多核大眾化并行計算研究的核心目標。微軟公司在2007年6月25日在美國西雅圖召開第一個以Many-Core為主題的Workshop，討論眾核軟件設計應如何開展，并于該年11月發表了THE MANYCORE SHIFT:Microsoft Parallel Computing Initiative Ushers Computing into the Next Era宣言，宣布轉入對眾核系統軟件的研究，基于眾核的軟件設計成為研究的熱點之一。

跟現有多核計算強調專門領域、需要專門知識的程序員不同，眾核計算關注通用平臺，基本涉及到所有應用領域，支持所有普通程序員進行眾核編程開發，即大眾化通用并行［4］。具體來說，多核計算關注高性能計算和服務計算領域、采用自底向上的硬件驅動方法、追求性能最大化目標;而眾核計算關注個人移動計算、采用自頂向下的應用驅動開發方法、追求最大化產能目標。

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

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

如何繼續使用而不是拋棄現有的大量程序 (軟件)代碼，如何并行現有串行代碼及提高程序執行效率;如何利用而不是拋棄現有的開發環境和工具等問題是通用眾核技術發展必須要解決的問題。

2 隱式并行編程模式

針對現有顯式編程模式成本大、容易出錯且不能兼容現有開發工具和程序的不足，我們提出了面向對象的基于對象粒度的隱式編程模式，在底層硬件和編譯技術的支撐下，兼容現有的串行程序開發模式、開發技術和開發工具，降低并行程序的開發成本和開發風險，并通過反編譯技術和軟件逆分析手段，實現對現有的串行二進制代碼并行化，使將來的眾核時代不至于拋棄現有的這些代碼成果。

相對于顯式并行編程模式，隱式并行編程模式盡量利用現有的開發工具、開發環境和程序開發語言等技術手段和成果，通過在計算機體系結構底層的硬件支撐進行專門設計、編譯器優化等技術手段，使在現有的開發環境和開發工具下開發出來的程序 (比如面向對象的程序)能夠無縫的運行在多核/眾核系統上，這樣開發的程序成本低、開發過程不容易出錯、程序移植性好，對程序員要求低，并能同時獲得較好的應用性能和產能目標。

目前軟件技術的高度發展，以C++和Java為代表的面向對象高級程序設計語言的產生，遵循人類思維方式，采用適合人類的處理問題的思考模式，以對象作為編程單元來編制程序，對象和對象之間相對獨立，對象具有封裝、繼承和多態性的特點，對象的方法和數據具有私有、公有和保護三種訪問模式，程序的代碼段主要由對象的方法調用組成，對象和對象之間通過消息機制完成通信。雖然在單核模式下，這些程序是串行執行的，對象的方法調用根據編制的代碼序列串行順序依次調用，顯然這些對象及其方法的調用是能夠并行進行。這些對象作為一種高度并行化的顆粒，能夠直接映射到眾核中的不同核去運行，通過處理器核間的通信鏈路來完成對象間的消息傳遞。現有的并 行 粒 度 有 循 環［7］、 函 數［8］、 代 碼 復 用［9］和 軟 件 流水［10-11］，需要程序員進行專門處理，對程序員要求較高，不通用，且不能解決現有代碼的并行問題，屬于顯式編程模式，面向對象的基于對象并行粒度編程模式屬于隱式編程模式，易于實現，并行度高，能夠較好的解決現有代碼的并行問題，是眾核發展技術的出路。

3 基于對象的隱式并行編程模式研究

通過編譯器和底層硬件支撐，現有的大眾化程序員能夠利用現有的面向對象開發技術和開發工具輕松開發出對象級粒度的并行程序，達到應用程序開發產能和并行性能收益同步提高的大眾化并行計算研究的核心目標，完成對高級語言對象級并行粒度的隱式編程模式的研究;應用反編譯技術和軟件逆向分析，對現有二進制代碼 (面向對象程序所寫)中的對象級粒度進行識別和重構。

3.1 研究目標

通過研究，對編譯器進行改進，完成在二進制代碼中對同一對象的方法和變量的統一存放，并加以標注，片上處理器調度時根據該標注識別對象，完成核間數據通信和參數傳遞的研究;完成現有二進制代碼中對象粒度的識別和重構，實現串行程序并行化;構建硬件支撐模塊，根據程序并發度調度二進制代碼中標注的對象，并將這些對象調度到不同核上運行;分析并找出對象間所有可能存在的數據共享方式。

3.2 關鍵問題

為了解決上述關鍵問題，主要需完成下面幾個方面的研究:

(1)通過對現有面向對象編譯器的改進，完成將現有面向對象語言中對象間的消息機制改進為核間通信手段的研究，進行不同對象 (核間)方法執行時參數傳遞及結果返回機制的研究，并在二進制代碼中對對象加以標記，同一對象的不同方法放在一起 (正文段)，同一對象的不同變量放置在一起 (數據段);

(2)由于對象存在封裝性，完成對象級并行粒度所有可能存在的共享數據及對其沖突類型進行評估;

(3)通過構建合適的底層硬件模塊，完成對二進制代碼中的對象及其方法的識別 (現在的串行二進制代碼，改造后的工具寫出來的程序中對象已有標注)，增加處理器對象訪存指令，分析程序并發度，每個程序的對象被調度到3-8個核上運行，并實現完成片上計算時間和傳輸時間的錯開、調度管理。

4 體系結構設計

我們采用圖1所示的三維眾核體系結構，由一層處理核層和多層cache層組成，層間采用3D疊片技術互連，處理核層各核間采用2D Mesh互連，cache層各cache塊節點間采用半互連長互連線互連，處理核由L1 T-cache、I/D-cache和路由器組成，其中T-cache是L1級事務內存，該體系結構存儲架構采用如圖2所示結構，支持對象直接訪問。

每個面向對象程序根據程序規模大小，把它的對象分別調度到3-8個核上，完成對象到處理器核的分配，為了利于指令緩存和數據緩存的命中率和實施局部性原理，把該對象的方法存儲在離核較近的地址空間段中，由對象所分配的核負責該對象所有方法的運行 (有的對象的方法調用頻率高，調度時需要考慮到這些對象在不同核上的負載平衡)，對象實例生成時，變量部分考慮存儲在離處理器核較近的內存空間段;程序運行時，先經由硬件支撐機構遍歷2-3遍代碼，分析其合適的并發度，完成程序中對象的識別后再分配對象于不同核，通過這些核并發執行這些對象。

該體系結構是一種可重構的異構多核系統，結點處理器核可以是異構的，可以由眾多的處理器核組成構成眾核系統，系統采用二級緩存系統，每個單核有自己的私有一級緩存L1，L1由指令緩存、數據緩存和事務緩存構成，數據緩存和事務緩存采用多端口Cache，且數據緩存和事務緩存之間能夠進行數據交換。具體的布局布線策略可采用斜布線和3D布線技術來實現，處理器核和存儲器DRAM間數據通信可以采用圖3所示的3D通路，處理器和存儲的組合示意圖如圖4所示。

5 眾核系統性能評價

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

圖5 不同核數的系統性能比較

6 結論和展望

提出的基于對象的隱式并行編程眾核體系結構，解決眾核時代繼續使用現有的二進制代碼、現有的開發技術和開發工具，減少并行程序開發成本和風險，提出的對象級并行粒度眾核軟件技術的研究，對眾核時代的程序并行化具有借鑒意義。

7 結束語

本文首先通過分析得出面向通用程序大眾化并行計算是將來眾核發展的方向，接著對其片上網絡、并行編程模式和存儲架構等關鍵技術進行深入研究，針對現有的顯式編程模式編程成本大、容易出錯且不能兼容現有開發工具和程序的不足，提出了面向對象的基于對象粒度的隱式編程模式，在底層硬件和編譯技術支撐下，兼容現有的串行程序開發模式、開發技術和開發工具，降低并行程序開發成本和開發風險，并通過反編譯和軟件逆分析技術手段，實現對現有的串行二進制代碼并行化，使將來的眾核時代不至于拋棄現有的這些代碼成果;并提出了相應的體系結構實現，這些關鍵技術解決了眾核技術發展的瓶頸。

［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).［曹仰杰，楊海兵，錢德沛，等.多核編程模型運行時環境的自適應性研究［J］.西安交通大學學報，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).［楊際祥，譚國真，王榮生.多核軟件的幾個關鍵問題及其研究進展 ［J］.電子學報，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，FU 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，Feng 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.