新系統：讓非專家也能優化在多核晶元上運行的程序

由麻省理工學院和石溪大學的研究人員開發的系統，使用針對多核晶元的動態編程優化，解決複雜的計算問題，而無需這種編程的專業知識。

圖片來源於：麻省理工學院新聞（圖像來源於研究人員）

引言

來自麻省理工學院計算機科學和人工智慧實驗室（CSAIL）和石溪大學的研究人員設計了一種新系統，讓用戶可以自己描述希望程序做什麼，然後自動生成這些程序的優化版本，可以在多核晶元上高效的運行，比專業人員編寫的手動多核晶元程序更具優勢。研究人員在上周的計算協會關於「系統、編程、語言和應用：軟體為人類服務」的會議上展示了新系統。

新型系統簡介

動態編程技術，對於解決經濟、基因組分析和其他領域問題，是一種相對高效的解決方法。但是，如果將它應用到具有多「核」的計算機晶元或者處理器單元上，這就需要一種專業的編程技能水平，很少有經濟學家和生物學家可以具備這項技能。

來自麻省理工學院計算機科學和人工智慧實驗室（CSAIL）和石溪大學的研究人員旨在改變這種狀況，他們設計了一種新系統，它讓用戶可以使用非常通用的術語描述他們希望程序做什麼。系統然後自動生成這些程序的各種優化版本，以便在多核晶元上運行。這些版本可以和單核版本產生一樣的結果，但是速度快很多。

在實驗中，研究人員使用系統「並行化」幾個使用動態編程的演算法，將它們拆分後在多核晶元上運行。這些程序的運行速度，是早期使用自動化並行處理技術的在3到11倍。程序的效率和計算機科學家手動並行化處理的程序一樣高。

動態編程解決特定類型的問題，速度的提高是指數級的，因為它存儲和復用計算結果，而不是按照需求每次都重新進行計算。

新系統面臨的挑戰

這項研究的第一作者、Armando Solar-Lezama 項目組的博士後、麻省理工學院電氣工程和計算機科學專業的副教授 Shachar Itzhaky 說道：

「但是，你需要更多的存儲器，因為你需要存儲中間計算的結果。當你要實現這個方案時，你會意識到你無法獲取想要的加速，因為存儲器速度慢。如果當你存儲和獲取數據的時候，當然它比重新進行計算的速度要快，但是它並沒有想像中的那麼快。」

應對挑戰的方法

計算機科學家通過重新排序計算來避免這個問題，它要求特別存儲的數值按順序執行，最小化數值必須從內存中調用的次數。這對於單核晶元相對容易操作，但是對於多核計算機，當多個核在不同位置存儲共用的數據，內存管理變得更加複雜。手動優化的並行版本的動態編程代碼長度是單核版本的10倍，並且每行的代碼更加複雜。

CSAIL 研究人員開發的新系統 「Bellmania」（由應用數學家 Richard Bellman 命名，他是開創了動態編程。）採用了一種稱為「遞歸分治」的並行策略。假設並行演算法任務要執行一些列矩陣的計算，它的首要任務就是將矩陣分為四部分，每個都可以單獨執行。

然後，它將會拆分這四個部分的其中一個再成為四個部分，然後再將其中的一個部分再拆分為另外四個部分，如此循環往複。因為這個遞歸方案涉及到將問題拆分為更小的問題，它自然地適合并行化處理。

這項新論文的研究人員包括：Itzhaky、Solar-Lezama、電氣工程和計算機科學專業的Edwin Sibley Webster 教授 Charles Leiserson、麻省理工學院的電氣工程和計算機科學專業的兩個研究生 Rohit Singh 和 Kuat Yessenov 、麻省理工學院的大學生 Yongquan Lu 通過麻省理工學院的校本科生研究項目參與這個項目、 石溪大學計算機科學專業的副教授 Rezaul Chowdhury，他同時也是 Leiserson 的小組之前的助理研究員。

Leiserson 的小組專門致力於「遞歸分治」的並行技術，Solar-Lezama 專門從事項目合成，或者從高級文檔自動產生代碼。通過 Bellmania 項目，用戶只要簡單的描述過程的第一步：拆分矩陣以及生成這些片段的流程。Bellmania 然後就會決定如何繼續細分這個問題，以便更加有效地利用內存。

快速搜索

在遞歸的每一個級別，產生了更小的細分矩陣。由 Bellmania 生成的程序會對每個矩陣部分進行一些特殊操作，將剩下的部分交給子常式處理，這樣的操作可以並行化。每個子常式，輪流地對於一些數據片段進行操作，然後將剩下的部分交給更小的子常式，如此往複。

Bellmania 決定在每個級別需要處理多少數據，以及子常式如何處理剩下的數據。Itzhaky說：

「我們的目標是為了有效組織內存訪問，這樣當你訪問矩陣的一個單元時，你可以使用它做儘可能多的運算，而不需要再次訪問它。」

尋找任務的優化劃分，需要覆蓋廣泛的可能性。Solar-Lezama 的小組開發了一套工具，可以讓這種搜索更加有效。儘管這樣，Bellmania 需要15分鐘並行化特殊的動態編程演算法，然而這比一個人類程序員完成同樣的任務要快很多，並且它可以保證結果正確，而手動優化的代碼十分複雜，很容易發生錯誤。

研究的意義

喬治亞理工學院的計算機科學和工程專業的教授 David Bader 說：

「他們正在進行的研究，為在多核和並行處理器上運行的一些應用奠定了基礎。這方面的主要的挑戰來自於讓程序的高級代碼，可以在目前的多核處理器上有效。目前為止，達成這個目標需要誇張的、低級手動編程。」

他們可以為一些類型的程序，提供更加簡單、高級別的技術，讓它可以十分容易便攜，通過系統自動指導拆分工作。創建出的高級代碼可以手動編寫的，低級別的代碼相媲美。

他補充道：

「這項技術的應用領域包括：計算生物學、蛋白質組學、網路安全、排序、各種調度問題、管理網路流量。使用更加有效的代碼實現真實世界中的無數真實演算法，這個成就是舉世矚目的。」

參考資料

【1】http://news.mit.edu/2016/faster-programs-easier-programming-multiprocessor-chips-1107

【2】Deriving Divide-and-Conquer Dynamic Programming Algorithms using Solver-Aided Transformations: people.csail.mit.edu/shachari/dl/oopsla2016.pdf

更多精彩內容，請關注微信公眾號：IntelligentThings

TAG:IntelligentThings |

※中國真的造不出核動力航母嗎？專家稱我們不缺技術只是在等時機
※中國有沒能力造核動力航母？專家稱不缺技術只等一事
※養老金入市又有新進展 業內專家：虧損可能性不大
※他憑藉一紙感謝信而被關注和熟知 技術超群的空冷系專家 終獲全國技術能手大獎
※俄專家揭開日真實核能力，讓國人頓悟，二次元技能強大
※劉德華演的到底專不專業？真正的拆彈專家表態了
※專家：塑造國際秩序需超強國力 中國還有差距
※英國專家促增加核聚變投資，否則將在商業應用上輸給中國
※專家：人工智慧的發展將帶來色情行業的深刻變革
※人工智慧新演算法，預測人類的心臟病和中風可能性，比專家還要准
※俄專家復活遠古細菌植入人體，可能引發生化危機
※特種兵不全都是神射手和武器專家，可能跟你想像中的真的不大一樣
※中國到底能不能建核動力航母？專家稱不缺技術只等一件事
※為何中國能造核潛艇卻不能造核動力航母:軍事專家一句話道破天機
※外媒：中國軍事專家認為有必要增強核力量
※中國到底能不能建核動力航母？專家稱技術全有隻等一件事
※不服中國軍力排行第三？專家稱實力在這，不服不行
※中國大中型新水面艦艇的中堅 專家詳細剖析性能戰技
※美國神秘的天空村，村民都是各行業專家，這裡的規矩是不能開燈