MIT CSAIL提出并行計(jì)算系統(tǒng)Fractal,能實(shí)現(xiàn)88倍加速

責(zé)任編輯:editor004

作者:思穎

2017-07-05 11:30:09

摘自:雷鋒網(wǎng)

現(xiàn)在,大多數(shù)臺(tái)式電腦的芯片都會(huì)配置四核或者一些處理單元,這種配置能保證計(jì)算機(jī)可以并行運(yùn)行不同的計(jì)算任務(wù)。

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

MIT CSAIL提出并行計(jì)算系統(tǒng)Fractal,能實(shí)現(xiàn)88倍加速

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

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

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

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

這個(gè)新系統(tǒng)被稱為“Fractal”,它是通過(guò)一個(gè)叫做預(yù)測(cè)執(zhí)行(speculative execution)的并行策略來(lái)實(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ī)制來(lái)保證數(shù)據(jù)具有相關(guān)性。從90年代中期到2000年代末,許多人對(duì)投機(jī)架構(gòu)(speculative architectures)進(jìn)行了一波又一波的研究。這些研究系統(tǒng)能并行執(zhí)行不同的數(shù)據(jù)塊,一旦發(fā)現(xiàn)沖突,就會(huì)中止程序再重新執(zhí)行。”"

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

不能簡(jiǎn)化的原子

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

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

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

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

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

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

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

時(shí)間鏈

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

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

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

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

鏈接已復(fù)制,快去分享吧

企業(yè)網(wǎng)版權(quán)所有?2010-2024 京ICP備09108050號(hào)-6京公網(wǎng)安備 11010502049343號(hào)