導(dǎo)讀：本周MIT最新發(fā)布新編程語言Milk，新的程序語言在大數(shù)據(jù)方面能實(shí)現(xiàn)比現(xiàn)有語言快四倍的處理速度。

在當(dāng)下的計(jì)算機(jī)芯片中，內(nèi)存管理是基于計(jì)算機(jī)科學(xué)家所稱的局部性原理（principle of locality）來實(shí)現(xiàn)的：

如果一個(gè)程序需要某個(gè)內(nèi)存位置的數(shù)據(jù)塊，它可能也需要數(shù)據(jù)塊臨近位置的數(shù)據(jù)。

但是在大數(shù)據(jù)時(shí)代，這種假設(shè)已不再成立。如今的計(jì)算機(jī)程序更多地是在大型數(shù)據(jù)集中離散地獲取一點(diǎn)點(diǎn)數(shù)據(jù)。由于從主要內(nèi)存位中獲取數(shù)據(jù)已成了當(dāng)下芯片的最大性能瓶頸，所以不得不更加頻繁地獲取數(shù)據(jù)，這也明顯拖慢了程序運(yùn)行的速度。

本周在國際并行體系結(jié)構(gòu)和編譯技術(shù)會(huì)議（International Conference on Parallel Architectures and Compilation Techniques）上，來自麻省理工學(xué)院計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室（CSAIL）的研究人員發(fā)布了一種新的編程語言——Milk，它能讓應(yīng)用程序開發(fā)者在處理大數(shù)據(jù)集里的離散數(shù)據(jù)點(diǎn)問題中更有效率地管理內(nèi)存。

通過測試幾種通用的算法，使用新語言Milk編寫的程序?qū)崿F(xiàn)了比現(xiàn)有編程語言快4倍的速度。但是研究者相信通過更進(jìn)一步的研究可以實(shí)現(xiàn)更好地結(jié)果。

電氣工程和計(jì)算機(jī)科學(xué)教授Saman Amarasinghe 說，當(dāng)下大數(shù)據(jù)集給已有的內(nèi)存管理技術(shù)帶來問題的原因不僅在于因?yàn)樗鼈兊囊?guī)模巨大，更多的是因?yàn)樗鼈兪?span style="color: rgb(255, 0, 0);">稀疏的（sparse）。也就是說，問題解決方案的規(guī)模并不一定是與問題的規(guī)模成正比增加。

“在社交環(huán)境中，我們通常傾向于注重更小的問題?！?Amarasinghe說“如果你只關(guān)注在這種建筑[CSAIL]內(nèi)的人的話，你能發(fā)現(xiàn)我們都是朋友的。但是如果你以地球的層面來看待的話，朋友的數(shù)量并不會(huì)增加。整個(gè)地球有幾十億人口，但是我也僅僅只有幾百個(gè)朋友。這就是一個(gè)很明顯的稀疏性問題?！?/p>

同樣Amarasinghe提到，一個(gè)在線書店可能為其1000名顧客提供最流行的20本書籍的書單。但是但其顧客數(shù)增加到100萬時(shí)，它并不會(huì)相應(yīng)地提供最流行的20000本書籍的書單。

局部思考（Thinking locally）

當(dāng)下的計(jì)算機(jī)芯片并沒有專門針對稀疏數(shù)據(jù)進(jìn)行優(yōu)化，而且可以說是完全相反。因?yàn)閺男酒闹饕獌?nèi)存位讀取數(shù)據(jù)是緩慢的，當(dāng)下的芯片中每個(gè)內(nèi)核或者每個(gè)處理器都有自己的“緩存”，一個(gè)相關(guān)的小型、本地、高速的內(nèi)存位。芯片中的內(nèi)核會(huì)一次讀取一個(gè)完整的數(shù)據(jù)塊，而不是在主內(nèi)存中每次提取一個(gè)單獨(dú)的數(shù)據(jù)。而讀取的數(shù)據(jù)塊是通過局部性原理來進(jìn)行選擇的。

通過圖像處理的例子可以很容易看清局部性原理的本質(zhì)：

如果一個(gè)程序的目的是將視覺過濾器應(yīng)用到圖像中，且它每次只作用在圖像的一個(gè)數(shù)據(jù)塊上。那么每次芯片內(nèi)核請求一個(gè)區(qū)塊數(shù)據(jù)時(shí)，它應(yīng)該收到自身緩存能接受的所有臨近區(qū)塊數(shù)據(jù)。因此它可以一個(gè)一個(gè)區(qū)塊處理，且不再獲取更多的數(shù)據(jù)。

但是如果該算法的興趣是在線書店200萬數(shù)據(jù)庫中的20本書的話，該方式將不再適用。如果它請求與某一本書相鄰的數(shù)據(jù)，很有可能其相鄰的100種書的數(shù)據(jù)都是沒有關(guān)聯(lián)的。

從主內(nèi)存中每次只讀取一個(gè)數(shù)據(jù)是非常低效的，這篇論文的第一作者Vladimir Kiriansky 提到

就像是每次你想要一勺食品時(shí)，你都需要打開冰箱、打開牛奶盒、倒出一勺牛奶、蓋上牛奶盒、將它放回冰箱。

他是電氣工程和計(jì)算機(jī)科學(xué)的博士生。Amarasinghe 和 Yunming Zhang 是他的論文合作者，Zhang 也是一位電氣工程和計(jì)算機(jī)科學(xué)的博士生。

批處理（Batch processing）

Milk簡單地增加了一些命令到OpenMP中。其中OpenMP 是一種能夠用在C或Fortran等語言中的擴(kuò)展，可以用來更輕松地為多核處理器編寫代碼。使用Milk的話，程序員可以在任何指令附近插入幾行代碼，其可以在整個(gè)大數(shù)據(jù)集中進(jìn)行迭代，尋找相對較少數(shù)量的項(xiàng)。Milk 的編譯器（將高級代碼轉(zhuǎn)換成低級指令的程序）可以據(jù)此找到管理內(nèi)存的方法。

使用 Milk 程序時(shí)，如果一個(gè)內(nèi)核發(fā)現(xiàn)它需要一項(xiàng)數(shù)據(jù)時(shí)，它并不會(huì)請求從主內(nèi)存中讀取它（以及相鄰的數(shù)據(jù)）。它會(huì)將該數(shù)據(jù)的地址添加到一個(gè)本地存儲(chǔ)的地址列表中。當(dāng)這個(gè)列表足夠長時(shí)

• 芯片所有內(nèi)核將會(huì)池化（pool）它們的列表

• 將這些地址按臨近排布的形式組合到一起

• 重新分配給內(nèi)核

這樣一來，每個(gè)內(nèi)核都只請求了自己所需要的數(shù)據(jù)項(xiàng)，并且可以有效地進(jìn)行檢索。

這樣描述的話層級較高，但實(shí)際上細(xì)節(jié)會(huì)復(fù)雜得多。事實(shí)上大部分現(xiàn)代計(jì)算機(jī)芯片都有多級緩存，且一級比一級大（但效率也因此更低）。Milk編譯器不僅必須跟蹤內(nèi)存地址表，還要跟蹤這些地址中存儲(chǔ)的數(shù)據(jù)，而且它常常將這兩者在各級緩存之間進(jìn)行切換。它也必須決定哪些地址應(yīng)當(dāng)被保留（可能需要再次訪問），哪些應(yīng)當(dāng)被丟棄。研究學(xué)者希望能夠進(jìn)一步提升這種編排復(fù)雜數(shù)據(jù)的算法，從而進(jìn)一步提升性能表現(xiàn)。

「當(dāng)下許多重要的應(yīng)用都是數(shù)據(jù)密集型的，但不幸的是，內(nèi)存和CPU之間的性能差距越來越大，這意味著當(dāng)前的硬件還沒有發(fā)揮出它們的全部潛力?！顾固垢４髮W(xué)計(jì)算機(jī)科學(xué)助理教授 Matei Zaharia 說，「Milk 通過優(yōu)化常見編程架構(gòu)中的內(nèi)存訪問來幫助解決這一差距。這項(xiàng)成果結(jié)合了內(nèi)存控制器設(shè)計(jì)的詳細(xì)知識和相關(guān)編譯器的知識，能為當(dāng)前的硬件實(shí)現(xiàn)良好的優(yōu)化?！?/p>

PS : 本文由雷鋒網(wǎng)獨(dú)家編譯，未經(jīng)許可拒絕轉(zhuǎn)載！

via MIT

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