雷鋒網(wǎng)AI科技評論按：據(jù)外媒MIT News最新報道，MIT CSAIL（麻省理工學院計算機科學與人工智能實驗室）已經(jīng)開發(fā)出了一個新系統(tǒng)Fractal，這個系統(tǒng)不僅能使并行程序運行起來更有效率，也使得編碼更加容易。雷鋒網(wǎng)對這篇新聞進行了翻譯，原文如下。

現(xiàn)在，大多數(shù)臺式電腦的芯片都會配置四核或者一些處理單元，這種配置能保證計算機可以并行運行不同的計算任務。在未來，芯片里可能會有幾十個甚至數(shù)百個核，如何利用并行性是一個艱巨的挑戰(zhàn)。

MIT CSAIL 的研究人員已經(jīng)開發(fā)出了一種新系統(tǒng)，這個系統(tǒng)不僅能使并行程序提升運行效率，也使編碼更加簡單。

以一組基準算法測試作為標準時，當采用相同的并行策略，在大多數(shù)情況下，這個新系統(tǒng)比目前系統(tǒng)的速度快十多倍，最大能達到目前系統(tǒng)的88倍。

將最大流問題的算法進行并行處理是非常困難的。經(jīng)過幾十年的研究，在256個并行處理器上，常見的最大流算法的并行計算最快也只能實現(xiàn)8倍的加速。而有了這個新系統(tǒng)，將能實現(xiàn)322倍的加速，并且代碼長度是之前代碼的三分之一。

這個新系統(tǒng)被稱為“Fractal”，它是通過一個叫做預測執(zhí)行（speculative execution）的并行策略來實現(xiàn)加速的。

“在傳統(tǒng)的并行程序中，你需要將你的工作分成多個任務，”  Daniel Sanchez表示。他是麻省理工學院電氣工程和計算機科學助理教授，另外也是這篇新論文（Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism）的資深作者?！暗驗檫@些任務是使用共享數(shù)據(jù)，所以需要引入一些同步機制來保證數(shù)據(jù)具有相關(guān)性。從90年代中期到2000年代末，許多人對投機架構(gòu)（speculative architectures）進行了一波又一波的研究。這些研究系統(tǒng)能并行執(zhí)行不同的數(shù)據(jù)塊，一旦發(fā)現(xiàn)沖突，就會中止程序再重新執(zhí)行?！?quot;

在計算完成之前頻繁中止程序并不是一個很有效的并行化策略。不過對于許多應用程序，中止計算的情況并不常見，這比在傳統(tǒng)并行方案的同步任務中所需的檢查和更新浪費的時間少得多。去年， Sanchez的小組報導了一個稱為 Swarm 的系統(tǒng)，這個系統(tǒng)將投機并行擴展成一類重要的計算問題，涉及搜索數(shù)據(jù)結(jié)構(gòu)，例如對圖表的搜索。

不能簡化的原子

然而，對投機架構(gòu)的研究往往局限于原子性（atomicity）問題上。正如所有并行架構(gòu)，投機架構(gòu)要求程序員把程序分成多個任務，這樣就能同時運行。但是在投機架構(gòu)中，每個任務都是“原子級的（atomic）”，這意味著它必須作為整體來執(zhí)行。通常，每個原子任務都有一個獨立的處理單元，這樣能更有效地獨立運行。

原子級的任務通常有很多步驟。舉個例子，在線預訂機票的任務包含很多步，這些步驟都必須被看作不同的原子單元。如果要將兩個任務當作同一個原子單元，那么這兩個任務就無法被執(zhí)行。例如，在這樣的程序下，僅僅只是因為第一位顧客還沒有完成支付，有可能座位就被分配給了另一位預訂的顧客。

• 在投機執(zhí)行中，大的原子級任務有兩個地方效率比較低下。

• 第一是如果想中止任務，得花費大量的計算時間。中止小一點的任務花費的時間相對會少一點。

• 第二是大的原子級任務內(nèi)部可能會有能并行運行的子程序，但是由于這些任務是在特定的處理單元獨立運行，因此這些子程序只能被連續(xù)執(zhí)行。這樣一來，性能就得不到提升。

Fractal是由Sanchez與麻省理工學院的研究生Suvinay Subramanian、Mark Jeffrey、Maleen Abeydeera、Hyun Ryong Lee、Victor A. Ying，以及英偉達杰出的高級研究科學家Joel Emer共同研發(fā)的，這一系統(tǒng)解決了如上提到的兩個問題。這些研究人員在這周的ISCA上向麻省理工學院電氣工程和計算機科學部詳述了它的原理。

有了Fractal，程序員在原子任務里只需在每個子程序里添加一行代碼，就可以實現(xiàn)并行執(zhí)行。程序的長度也只增加若干百分點。在以前，如果需要實現(xiàn)同步并行任務，程序長度得增加300—400個百分點。將電路嵌入分形芯片，就可以進行并行化處理了。

時間鏈

這個系統(tǒng)的關(guān)鍵是對電路的細微改進，這種改進在這些研究員的早期投機執(zhí)行系統(tǒng) Swarm 中已經(jīng)實現(xiàn)了。

在Swarm中執(zhí)行的每個任務都會分配一個時間戳，如果兩個任務嘗試訪問相同的存儲單元，時間戳晚一點的那個任務將會被中止，然后重新執(zhí)行。

Fractal中的每個原子任務也會分配自己的時間戳。但如果原子任務里有并行子程序，子程序的時間戳里會包含這個任務的時間戳。另外，如果子程序里還有并行的子程序，那么后面那個子程序的時間戳里包含前面子程序的時間戳，以此類推。通過這種方式，子程序的排序里都包含原子任務的排序。

當一個任務里包含子程序，子程序里又不斷包含其他子程序，這對于存儲他們的專用電路來說，子程序里串聯(lián)的時間戳太長了。在這種情況下，F(xiàn)ractal只存儲時間戳序列的最前列。這意味著Fractal只執(zhí)行定義好的最低級別、最細粒化的任務，這樣能避免中止大的、高級別的原子任務。

新聞地址：http://news.mit.edu/2017/speedup-parallel-computing-algorithms-0630 ，雷鋒網(wǎng) AI 科技評論編譯

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。