http://news.mit.edu/2016/parallel-programming-easy-0620
新晶片設計使得平行運作的程式速度快上許多倍，且所需程式碼不到原本的十分之一。
Larry Hardesty | MIT News Office
June 20, 2016
電腦晶片已停止變得更快。過去 10 年來，晶片效能的改善來自於處理單元，也就是「核心」數量的增加。
理論上，一支在 64 核心機器上執行的程式，應該比單核心機器要快 64 倍。不過在真實情況下並非如此。絕大多數的電腦程式都是循序性（sequential），將之分割，並讓每個程式區塊（chunks）可以平行方式運行，則引發了各種程度的複雜性。
在五月╱六月號的 IEEE 期刊 Micro 中，來自 MIT 電腦科學與人工智慧實驗室（CSAIL）的研究者將發表一款新的晶片設計，他們稱為「群（Swarm，下文使用原文）」，能使平行運作的程式不僅更有效率，且更容易撰寫。
在模擬中，研究者將 Swarm 版本的六種常見演算法與現有最佳的平行版本進行比較，這些版本都經過經驗老道的軟體開發者個別調校過。結果 Swarm 的版本比平行版本快了 3 到 18 倍，而其程式碼不到平行版本的十分之一，甚至更少。而且在某一例中，Swarm 甚至達到 75 倍的加速，而且那支程式，電腦科學家到目前為止都尚未能平行化。
"多核系統程式真的很難寫，" Daniel Sanchez 表示，MIT 電機工程與電腦科學系助理教授，他領導此計畫。"你得將目前正在進行的工作明確地分割成任務，接著你需要迫使那些存取共享資料的任務之間進行某種同步化。而基本上，這個（Swarm）架構所做的是，移除各種明確的同步化，使得平行程式設計變得更容易。這有一組特別難搞的應用，無法平行化非常非常多年，而這些正是我們在此論文中所關注的應用。"
這些應用之中有許多涉及探索電腦科學家稱之為「圖（graphs）」的東西。圖由「節點（nodes）」所組成，通常被描繪成圓形（circles）與邊（edges），通常被描繪成連結節點的線段。而這些「邊」通常與不同的數字產生關聯，稱為「權重（weights）」，那可以代表，例如某一資料組中資料點之間的關聯強度（http://news.mit.edu/2014/new-algorithm-tells-which-data-to-collect-0724），或是城市之間的距離。
「圖」會產生一籮筐電腦科學問題（http://news.mit.edu/2013/algorithm-extends-artificial-intelligence-technique-1114 、 http://news.mit.edu/2015/integer-overflow-debugger-outperforms-predecessors-0324），不過它們最直觀的用途也許是描述幾何學關係。事實上，CSAIL 研究者所評估的演算法之一是在二點間尋找最快駕駛路線的標準演算法。
設定優先權
原則上，探索「圖」看似某種可以被平行化的東西：不同的核心可以在同一時間分析整個圖的不同區域或穿越圖的不同路徑。問題是，從絕大多數的圖探索演算法來看，可以漸漸明白，圖的整個區域與手邊的問題不相干。如果眾核心直接被派去探索這些區域，它們的努力終將白費。
當然，不相干區域的無關分析對於循序性圖探索演算法來說也是個問題，不只平行那一部份。所以電腦科學家開發出一堆使用特殊技術的應用來優先化圖的搜尋。例如，某種演算法也許從那些具有最低權重的邊開始探索路徑，或著它也許會先找那些邊界數量最低的節點。
使 Swarm 有別於其他多核心晶片之處，在於它擁有額外的電路來處理這種類型的優先化。它會依據任務的優先性賦予時間戳記，並開始針對最優先的任務進行平行處理。高優先任務也許會產生它們自己的低優先任務，不過 Swarm 會將這些自動排入它的任務佇列（queue）中。
有時候，平行運行的任務也許會產生衝突。例如，具低優先權的任務在高優先權任務要讀取某個特定的記憶體位置之前，也許就先將資料寫入該位置。在這些例子中，Swarm 會動放棄低優先任務的結果。它因而維持那些存取相同資料的核心之間的同步性，這些是程式設計師之前得要自己擔心的部份。
事實上，從程式設計師的觀點來看，使用 Swarm 相當「無痛」。當程式設計師定義一個函數後，他或她只要增加一行程式碼，將函數載入到 Swarm 的任務佇列中。程式設計師得要明確定義特定的度量（metric） -- 例如邊的權重或是邊的數量 -- 供程式用以優先化任務，而且無論如何，那是必要的。一般來說，在 Swarm 上採用現有的循序性演算法只要添加幾行程式碼即可。
關照
工作重擔則落在晶片本身，那是 Sanchez 與下面幾位合作設計： Mark Jeffrey 以及 Suvinay Subramanian，二位均是 MIT 電機工程與電腦科學系畢業生；成員 Cong Yan 在 Sanchez 小組中修她的碩士學位，現在則是華盛頓大學博士生；以及 Joel Emer，MIT 電機工程與電腦科學系的專業應用教授、晶片製造商 NVidia 的資深名譽研究科學家。
Swarm 晶片具有額外電路來儲存與管理它的任務佇列。它也有電路記錄所有核心目前正在運行的記憶體位置資料。該電路實作了某種稱為 Bloom filter 的東西，那將資料填入一個固定的配發空間，並對其內容回達 yes╱no 的問題。如果有太多位址被載入到這個過濾器，它不時會產生誤報（false positives，假陽性）-- 指稱："是的，我正在儲存那個位址" -- 不過它從來不會產生漏報（false negatives，假陰性）。
Bloom filter 是數個協助 Swarm 確認記體體存取衝突的電路之一。研究者能證明時間戳記使得核心間的同步化更容易執行。例如，每個資料項目都標有時間戳記，那由最新的任務更新之，故具有較新的時間戳記的任務知道它們能夠讀取資料，而不用費心操煩誰該使用它。
最終，所有的核心都會偶爾報告它們仍在執行的最高優先任務之時間戳記。如果某核心已完成任務，其時間戳記早於後續所報告的，那麼它知道，它可以將其結果寫入記憶體內而不遇到任何衝突。
"我認為它們的結構只是對於過去在交換式記憶體（transactional memory）以及執行緒層級推測（thread-level speculation）研究上的正確觀點，" Luis Ceze 表示，華盛頓大學電腦科學與工程副教授。"交換式記憶體指涉一種確保多核處理器能夠平行運作，不會對彼此造成不便的機制。它保證在一種有序的情況下，對共享記憶體位置進行更新。執行緒層級推測是一種相關的技術，使用交換式記憶體的點子達到平行化：在不需要確認任務是平行的情況下執行，如果它不是平行的，那麼取消並連續地重新執行。Sanchez 的結構以一種聰明的方式，運用到這些點子與技術裡許多優良的部份。"
※ 相關報導：
＊ Unlocking Ordered Parallelism with the Swarm Architecture
http://dx.doi.org/10.1109/MM.2016.12
Mark C. Jeffrey; Suvinay Subramanian; Cong Yan;＊ 最佳化電腦速度的新技術
Joel Emer; Daniel Sanchez
IEEE Micro
Year: 2016, Volume: 36, Issue: 3,
Pages: 105 - 117,
doi: 10.1109/MM.2016.12
＊ 新演算法顯著提升路由效率
＊ 快速光子控制使量子光學技術更接近現實
＊ 光學天線能朝不同方向散射不同顏色的光
沒有留言:
張貼留言