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

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

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

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

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

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

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

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

不能簡化的原子

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

原子級(jí)的任務(wù)通常有很多步驟。舉個(gè)例子，在線預(yù)訂機(jī)票的任務(wù)包含很多步，這些步驟都必須被看作不同的原子單元。如果要將兩個(gè)任務(wù)當(dāng)作同一個(gè)原子單元，那么這兩個(gè)任務(wù)就無法被執(zhí)行。例如，在這樣的程序下，僅僅只是因?yàn)榈谝晃活櫩瓦€沒有完成支付，有可能座位就被分配給了另一位預(yù)訂的顧客。

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

• 第一是如果想中止任務(wù)，得花費(fèi)大量的計(jì)算時(shí)間。中止小一點(diǎn)的任務(wù)花費(fèi)的時(shí)間相對會(huì)少一點(diǎn)。

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

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

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

時(shí)間鏈

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

在Swarm中執(zhí)行的每個(gè)任務(wù)都會(huì)分配一個(gè)時(shí)間戳，如果兩個(gè)任務(wù)嘗試訪問相同的存儲(chǔ)單元，時(shí)間戳晚一點(diǎn)的那個(gè)任務(wù)將會(huì)被中止，然后重新執(zhí)行。

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

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

新聞地址：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)載須知。