新系統大大加速一般並行計算方法

現在大部分台式機都有4核，可以並行處理不同計算任務。但未來的晶元可以有數十核乃至數百核，要利用所有這些核進行並行計算較為困難。

來自麻省理工學院計算機科學與人工智慧實驗室的研究者提出了一個新系統，不僅使並行程序的效率大大提升，並且也使得更容易進行並行程序編程。

credit: 自己仿照原圖畫的

在該領域的標準檢查程序集測試中，研究者的新系統相比採用相同並行策略的現有系統，速度提升了10倍，最大提升88倍。

例如，解決最大流問題的演算法已被證實非常難以並行化。經過數十年的研究，一個常見最大流演算法的最好並行實現也只能在256個並行處理器上實現8倍加速。而利用研究者的新系統，可實現322倍加速，並且只需要3分之1的代碼量。

這一新系統被稱為Fractal，基於推測執行這一併行策略實現加速。

MIT電子工程與計算科學助理教授、新論文資深作者Daniel Sanchez說道：「在傳統的並行程序中，你需要將工作分解為多個任務。但由於這些任務在共享數據上進行操作，因此需要引入某些同步機制來確保慎重處理這些任務之間的數據依賴性。從1990年代中期到2000年代末，出現了幾波關於推測結構的研究熱潮。這類系統所做的就是並行執行這些不同的塊，如果檢測到衝突，就取消並回滾其中某一個。」

在完成之前不斷取消計算並非一個很有效的並行策略。但對於很多應用而言，取消計算出現的次數可能會很少，以至於相比更為傳統的並行演算法中同步任務所需的複雜檢查和更新花費的時間更少。去年，Sanchez的小組提出了一個名為Swarm的系統，將推測並行計算擴展到一類重要的計算問題，涉及圖這種搜索數據結構。

不可分的原子

但關於推測架構的研究往往止步於「原子性」問題。正如所有的並行架構那樣，推測架構要求程序員將程序劃分為多個能同時運行的任務。但在推測架構中，每個這種任務被稱為「原子」，意味著似乎應當作為單個整體執行。典型的，每個原子任務被分配給單獨處理單元。

原子任務一般相當多。例如網上訂一張飛機票，就由多個分離的操作組成，但必須被當成一個原子單元處理。否則就有可能出現程序將一個座位提供給一名顧客然後又提供給了另一個顧客，因為第一名顧客還沒有完成支付。

在推測執行中，大型原子任務會引起兩方面的低效。第一個是如果必須取消任務，可能必須經過大量計算循環後才行。取消小一點的任務可以花更少的時間。

另一個方面是一個大型原子任務可能包含可以有效並行的內部子程序。但由於這一任務被自身的處理單元所孤立，這些子程序就必須串列運行，浪費了性能改進的機會。

Sanchez 與MIT研究生Suvinay Subramanian、Mark Jeffrey、Maleen Abeydeera、Hyun Ryong Lee、Victor A. Ying以及晶元製造商英偉達的資深傑出研究科學家Joel Emer教授一起研發了Fractal，解決了上述所有問題。該研究已在計算架構國際研討會(ISCA)上作了報告。

利用Fractal，程序員就能在原子任務的每個子程序中增加一行代碼，使這些子程序可以被並行執行。這一般會少許增加程序串列實現的長度，而同步並行任務的實現則會使程序長度增大到3到4倍。Fractal晶元上的電路則處理了這個並行化問題。

時間鏈

系統的關鍵是在研究者早先提出的名為Swarm的推測執行系統的電路基礎上進行了稍微修改。Swarm被設計來以並行程序執行某些順序的概念。Swarm中執行的每個任務都會打上一個時間戳，如果兩個任務試圖訪問同一個存儲位置，時間戳較晚的那個就會被取消並重新執行。

Fractal也給每個原子任務分配自身的時間戳。但如果原子任務中還有可並行的子程序，子程序的時間戳就包含所在任務的時間戳。另外如果這個子程序還包含可並行的子程序，第二級子程序的時間戳就包含第一級子程序的時間戳，以此類推。按照這種方式，子程序的順序就保留了原子任務的順序。

由於任務會不斷向下級衍生子程序，串聯的時間戳就可能變得特別長以致於特殊設計的存儲電路都無法處理。但在這種情況下，Fractal就簡單地將時間戳火車的前部移到存儲中。這就意味著Fractal總是工作在其已經鑒定的最低一級、最細化的任務，避免了取消大型、高層原子任務的問題。

論文原文：Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism

本文譯自 phys，由譯者 CliffBao 基於創作共用協議(BY-NC)發布。Larry Hardesty

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！