據外媒MIT News最新報道，MIT CSAIL（麻省理工學院計算機科學與人工智能實驗室）已經開發出了一個新系統Fractal，這個系統不僅能使并行程序運行起來更有效率，也使得編碼更加容易。雷鋒網(公眾號：雷鋒網)對這篇新聞進行了翻譯，原文如下。
現在，大多數臺式電腦的芯片都會配置四核或者一些處理單元，這種配置能保證計算機可以并行運行不同的計算任務。在未來，芯片里可能會有幾十個甚至數百個核，如何利用并行性是一個艱巨的挑戰。
MIT CSAIL 的研究人員已經開發出了一種新系統，這個系統不僅能使并行程序提升運行效率，也使編碼更加簡單。
以一組基準算法測試作為標準時，當采用相同的并行策略，在大多數情況下，這個新系統比目前系統的速度快十多倍，最大能達到目前系統的88倍。
將最大流問題的算法進行并行處理是非常困難的。經過幾十年的研究，在256個并行處理器上，常見的最大流算法的并行計算最快也只能實現8倍的加速。而有了這個新系統，將能實現322倍的加速，并且代碼長度是之前代碼的三分之一。
這個新系統被稱為“Fractal”，它是通過一個叫做預測執行（speculative execution）的并行策略來實現加速的。
“在傳統的并行程序中，你需要將你的工作分成多個任務，” Daniel Sanchez表示。他是麻省理工學院電氣工程和計算機科學助理教授，另外也是這篇新論文（Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism）的資深作者。“但因為這些任務是使用共享數據，所以需要引入一些同步機制來保證數據具有相關性。從90年代中期到2000年代末，許多人對投機架構（speculative architectures）進行了一波又一波的研究。這些研究系統能并行執行不同的數據塊，一旦發現沖突，就會中止程序再重新執行。”"
在計算完成之前頻繁中止程序并不是一個很有效的并行化策略。不過對于許多應用程序，中止計算的情況并不常見，這比在傳統并行方案的同步任務中所需的檢查和更新浪費的時間少得多。去年， Sanchez的小組報導了一個稱為 Swarm 的系統，這個系統將投機并行擴展成一類重要的計算問題，涉及搜索數據結構，例如對圖表的搜索。
不能簡化的原子
然而，對投機架構的研究往往局限于原子性（atomicity）問題上。正如所有并行架構，投機架構要求程序員把程序分成多個任務，這樣就能同時運行。但是在投機架構中，每個任務都是“原子級的（atomic）”，這意味著它必須作為整體來執行。通常，每個原子任務都有一個獨立的處理單元，這樣能更有效地獨立運行。
原子級的任務通常有很多步驟。舉個例子，在線預訂機票的任務包含很多步，這些步驟都必須被看作不同的原子單元。如果要將兩個任務當作同一個原子單元，那么這兩個任務就無法被執行。例如，在這樣的程序下，僅僅只是因為第一位顧客還沒有完成支付，有可能座位就被分配給了另一位預訂的顧客。
在投機執行中，大的原子級任務有兩個地方效率比較低下。
第一是如果想中止任務，得花費大量的計算時間。中止小一點的任務花費的時間相對會少一點。
第二是大的原子級任務內部可能會有能并行運行的子程序，但是由于這些任務是在特定的處理單元獨立運行，因此這些子程序只能被連續執行。這樣一來，性能就得不到提升。
Fractal是由Sanchez與麻省理工學院的研究生Suvinay Subramanian、Mark Jeffrey、Maleen Abeydeera、Hyun Ryong Lee、Victor A. Ying，以及英偉達杰出的高級研究科學家Joel Emer共同研發的，這一系統解決了如上提到的兩個問題。這些研究人員在這周的ISCA上向麻省理工學院電氣工程和計算機科學部詳述了它的原理。
有了Fractal，程序員在原子任務里只需在每個子程序里添加一行代碼，就可以實現并行執行。程序的長度也只增加若干百分點。在以前，如果需要實現同步并行任務，程序長度得增加300—400個百分點。將電路嵌入分形芯片，就可以進行并行化處理了。
時間鏈
這個系統的關鍵是對電路的細微改進，這種改進在這些研究員的早期投機執行系統 Swarm 中已經實現了。
在Swarm中執行的每個任務都會分配一個時間戳，如果兩個任務嘗試訪問相同的存儲單元，時間戳晚一點的那個任務將會被中止，然后重新執行。
Fractal中的每個原子任務也會分配自己的時間戳。但如果原子任務里有并行子程序，子程序的時間戳里會包含這個任務的時間戳。另外，如果子程序里還有并行的子程序，那么后面那個子程序的時間戳里包含前面子程序的時間戳，以此類推。通過這種方式，子程序的排序里都包含原子任務的排序。
當一個任務里包含子程序，子程序里又不斷包含其他子程序，這對于存儲他們的專用電路來說，子程序里串聯的時間戳太長了。在這種情況下，Fractal只存儲時間戳序列的最前列。這意味著Fractal只執行定義好的最低級別、最細粒化的任務，這樣能避免中止大的、高級別的原子任務。
京公網安備 11010502049343號