15新系統大大加速一般平行計算方法
現在大部分桌上型電腦都有4核，可以並行處理不同計算任務。但未來的晶片可以有數十核乃至數百核，要利用所有這些核進行平行計算較為困難。
來自麻省理工學院計算機科學與人工智慧實驗室的研究者提出了一個新系統，不僅使並行程式的效率大大提升，並且也使得更容易實現並行程式設計。
在該領域的標準檢查程式集測試中，研究者的新系統相比採用相同並行策略的現有系統，速度提升了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總是工作在其已經鑑定的最低一級、最細化的任務，避免了取消大型、高層原子任務的問題。