隨著計算機技術的發展，毫無疑問現代計算機的處理速度和計算能力也越來越強。然而細心的同學們可能早已注意到，從2005年起，單核的 CPU 效能就沒有顯著的提升了（見下圖）。究其原因，是人們發現單純的提高單核 CPU 的效能無論從潛力上還是功耗上都是不合算的。隨著 Intel 的 NetBurst 架構退出江湖，處理器徹底進入了多核時代，從最初的雙核一路飆升到現在的動輒上百核的 CPU，效能的提升不以裡計。同時一系列針對特殊計算的 accelerator 的出現，並行硬體的發展現在正是百花齊放。多年以前要用許多臺電腦才能並行處理的“大資料”問題，現在大多都可以用一臺多核電腦解決了。

圖1，來源：“The free lunch is over” by Sutter 2010

然而一方面是硬體的日新月異，另一方面對於如何高效而正確的使用這些硬體進行並行演算法的設計和實現卻一直是長久存在的問題。對於序列演算法，所有科班出身的計算機人都應該再熟悉不過了，畢竟演算法和資料結構是所有低年級本科生的必修課。然而當我們試圖並行這些再熟悉不過的演算法的時候，事情卻往往並沒有這麼簡單。就拿一個非常簡單的排序問題舉例，在序列的背景下我們學過很多種特點不同的演算法，大多數虛擬碼只要幾行到十幾行。然而直接並行這些演算法卻很難得到令人滿意的加速比。很多時候，“學習並行程式設計”只是學習使用了 OpenMP/MPI/CUDA 等並行工具，而僅僅這樣並不能保證寫出真正 scalable 的並行演算法。從另一個角度來講，並行程式設計的臭名昭著之處在於，執行結果常常是難以預測的也難以控制的。比如這個著名的笑話：

如果你有一個問題，就用並行解決它。這你樣就有個兩問題了。

這給debug也帶來了額外的難度（如果你還想看關於並行程式設計的笑話，這裡和這裡還有兩個，所有笑話均為轉載）。但是隨著我們對並行演算法研究的加深和理論的完善，我們相信，寫並行演算法應該和寫序列演算法一樣容易（回顧計算機的歷史，你會發現傳統序列演算法程式設計也是經歷了幾十年理論和系統的發展才像今天一樣簡單的）。

就拿快排舉例。快排本身使用的分治方法是非常適合於並行的。當我們使用一個 pivot 將陣列分為左右兩部分之後，兩邊就可以同時進行排序。然而這麼簡單就能得到一個高效的快排演算法嗎？考慮將數組裡的數分成左右兩邊的過程（partition），如果我們依然使用傳統序列演算法的經典的 partition 演算法，也就是基於兩個或者三個指標對應的元素的比較和交換，這一過程是非常序列的（快排的高效也是有賴於這個序列掃描中的訪存 pattern）。如果僅僅第一步的 partition 就使用了 O（n） 的操作，即便後續的分支過程的代價都忽略不計，核數再多，執行時間也不可能快於第一步的 partition 的開銷。因此如果只是瞭解掌握了使用並行工具，但是侷限在“並行”現有的序列快排中，是很難寫出高效的並行排序演算法的。至於如何並行快排其實並不困難，我在 17 年在清華暑期課程中講過，有興趣的同學可以參考課件（連結）。或者我們的後續文章裡：

也有介紹。同時這個演算法的實現也非常簡單，在整個演算法中都不存在兩個核同時對一個元素進行操作。換句話說，演算法雖然並行（parallel），利用了多核進行計算，但是不會需要併發（concurrency），這使得演算法的效果變得 predictable，也不難 debug。

事實上許多並行演算法和快排一樣，本質上並不複雜，但需要的只是摒棄我們對於傳統演算法的理解而做到使用並行的思維去思考問題，也就是我們稱之為 Parallel Thinking 。當然其實在並行的大背景下，快排也並不是最有效率的排序演算法和實現，還有同樣很簡單但是效能更好的演算法 ［1］ 。這些演算法並不複雜，只是需要理解的方式和普通的序列演算法有很大的不同。反過來看，Parallel Thinking 的新角度也會給序列演算法的設計帶來新的啟發。“寫並行演算法和序列演算法一樣容易”這件事看起來有些天馬行空，但卻是在實踐中被證明是可行的。

比較前衛的學校，比如 CMU，早在很多年前就已經在演算法入門課（本科二年級）直接教授本科生並行演算法而不再侷限於序列演算法了——因為序列演算法就是並行演算法在一個核上跑嘛！

相信這也會成為未來世界上所有學校的大趨勢。這也同時意味著，我們需要以新的視角去理解，思考和設計算法。

就如同 5-60 年代計算機的興起帶來了 7-80 年代（序列）演算法研究的黃金時期，隨著近十幾年來並行硬體的普及，並行演算法的研究也開始了新的篇章。雖然早先的甚至上世紀的研究已經得到了很多的結果，現在還有更多的問題的面紗有待我們去揭開。相信就像 7-80 年代設計的演算法一樣，這些新的並行演算法也會出現在下一代計算機學生的教科書中。下面舉幾個我們近期研究的例子，希望大家能對於並行演算法和 Parallel Thinking 有一個大致的瞭解。

平衡二叉搜尋樹（Balanced BSTs）

平衡二叉搜尋樹是一種非常基礎的資料結構，用於動態維護任何有序的集合。常見的一些實現包括 AVL 樹，紅黑樹，weight-balanced tree（BB［α］ trees，加權平衡樹），treap 等等。很多更加高階的資料結構，比如 interval tree，segment tree，range tree，以及很多其他幾何問題、甚至許多型別的資料庫，都可以透過增廣（augment）BST的方式進行實現 ［2］。

我們都知道經典的BST是透過插入/刪除（insert/delete）進行維護的。然而在並行的背景下，這種抽象方式是

低效

的。舉例而言，如果同時向樹中插入多個節點，如何保證正確性呢？我們當然可以透過使用加鎖或者一些原子操作（ComareAndSwap 等），但是很多時候這會造成嚴重的阻塞，以及許多核處於等待狀態。倘若有100+核同時進行這些操作，考慮 memory consistency 和為了維持平衡要進行的旋轉，會出現許多衝突，甚至還有可能出現

核越多，速度越慢

的現象。因此基於插入/刪除的 BST 抽象在並行的前提下是不可取的。

為此我們提出了一種基於 join 操作的樹結構 ［3］。join 這個函式是說，給定兩棵樹 T1 和 T2，以及一個結點 k，返回一個合法的平衡樹 T = ［T1， k， T2］，它等價於用 k 連線 T1 和 T2，但是要求輸出樹滿足平衡條件。顯然對於 BST 來說，這個演算法只有在 k 大於 T1 裡所有數，並小於 T2 裡所有數時才有意義。當這個 join 演算法可以被正確地實現時，我們就可以把許多樹上的演算法並行。總體的思路依然是利用分治法。對於一棵樹，我們並行地遞迴地處理左子樹和右子樹，並把它們用樹根 join 起來。許多時候，操作後的左右子樹不再平衡，但是正如上面所說，join 會處理平衡問題。透過抽象出 join 這個元操作，並行別的演算法的思路就變得簡潔。

圖2：join 兩棵樹 TL、TR 和 k。

很有趣的一點是，抽象出 join 之後，別的平衡樹演算法們就不再需要進行任何旋轉操作來進行重平衡——這些事情都透過呼叫 join 實現了。換言之，AVL樹，紅黑樹，等等，這些不同平衡樹的操作（插入，刪除，合併，取交，等等）都可以用同一個演算法，只要它們各自有一個好用的 join 演算法就行了。拿一個插入操作舉例：

insert（T， k） {

if （T==null） return new_node（k）；

if （T’s root == k） return；

if （T’s root < k） return join（insert（T。left， k）， T。root， T。right）；

if （T’s root > k） return join（T。left， T。root， insert（T。right， k））；

}

這個插入演算法不需要知道 T 到底是一棵 AVL 還是紅黑樹。只要 join 正確，它就正確。從效率上來講，它對於常見的平衡樹來講時間複雜度依然是 O（log n） 的，當然，這是一個簡單的序列演算法。許多並行演算法也是同理。比如如果想並行地插一個數組的元素們進一棵樹裡要怎麼做呢？寫起來其實大概只需要十行的虛擬碼：

MultiInsert（T， A， n） {

A‘ = parallel_sort（A， n）；

return MultiInsertSorted（T， A’， n）；

}

MultiInsertSorted（T， A， n） {

if （|T|==0 || n==0） return；

x = binary_searching（A， T。root）；

b = （A［x］==T。root）； //b is a bit （0 or 1） indicating if A［x］ is already in T。

in parallel：

L = MultiInsertSorted（T。left， A， x）；

R = MultiInsertSorted（T。right， A+x+b， n-x-b）；

return join（L， T。root， R）；

}

上面的 parallel_sort 可以用任何已有的並行排序演算法，比如上述所說的快排（實際中我們用得更多的是 sample sort）。如上所述，這個演算法是把插入轉化成向左右子樹插入的兩個可並行的子問題，並用 join 最後將它們合併的。這個並行的 MultiInsert 演算法即便要進行排序和二分搜尋等額外操作，依然比現有的併發樹結構（concurrent trees）同時使用 p 個核呼叫插入演算法高效幾到十幾倍 ［4］。它的高效性很大程度上是因為它保證了演算法過程中沒有衝突（conflict）——分治法保證了任何時候任何結點最多隻有一個核在操作。

如上所述，這個演算法也是是對於多種平衡樹都成立的。曾經對於每種不同平衡樹，哪怕只是插入刪除操作我們都要記憶不同的演算法，但當我們用並行的眼光看問題的時候，我們竟然發現演算法設計變得更加簡單了。

基於這樣一個高效而簡單的並行樹結構 P-tree （parallel tree），我們可以對一些有趣的理論問題提出新的演算法，降低已有演算法的複雜度（尤其是並行複雜度），或者把已有的演算法變得更加簡潔。比如一些計算幾何問題，有序集合的操作問題，甚至排序問題，也可以解決許多現實中的應用問題，比如資料庫，索引搜尋，事物記憶體（transactional memory），等等。

圖3：基於 P-tree 的實現和已有演算法的比較，紅色為 P-tree。左圖為 Range tree 的實現，即使序列效率也比現有的計算幾何庫快。並行後的 P-tree 演算法有超過 100 倍的效能提升。中圖是和現有的併發樹的比較。右圖是基於P-tree 實現的資料庫，比起現有的 HyPer 和 MemSQL 效率有很大提升。

NVRAMs 和 Write-Efficient Algorithms

長久困擾計算機界的一大問題就是

處理器的效能增長是遠遠大於記憶體大小和頻寬的增長

的。還舉 2005 年到今天的例子，處理器從單核增長到了上百核，而且還有各種新單核技術的加成。然而記憶體從 DDR2 到 DDR4 的頻寬和容量增長都非常有限。固然新的高效能計算機通常可以透過裝很多很多的記憶體條在短時間內在一定程度上解決問題，但是長此以往肯定不是辦法。尤其是 DRAM 技術遇到瓶頸幾乎無法大幅度提升效能、且能耗散熱已經是很大的問題的前提下。這也對並行演算法本身提出了挑戰：即便有了高效的共享記憶體（shared-memory）並行演算法，如果記憶體不夠大，解決問題的規模就非常有限；同時隨著核數的增加，每個核分到的記憶體反而在減小。

然而我們人類站在地球之巔不是沒有道理的，遇到問題就一定會找到解決方案。在今年4月推出的 Intel® Optane™ DC Persistent Memory 就是基於完全不同技術的新記憶體解決方式，為了以示區分我們通常稱之為 NVRAM。新技術非常的震撼，初代產品就能達到最大 512GB per DIMM，只要 12 塊就可以在一臺機器上達到 6TB 的記憶體，遠遠超過現有的 DRAM 技術。同時新硬體在技術上有很強的的擴充套件性，在可以遇見的未來容量增長都有非常大的潛力。可以說 NVRAM 的出現對於多核並行和廣義的計算和資料儲存的幫助是非常決定性的。

圖4：Intel® Optane™ DC Persistent Memory

既然是新的技術，那就必然有一些新的 feature。一個 feature 是新硬體的 persistency，也就是說掉電後內容不會丟失，因此用新硬體就完全不需要之前的複雜的資料容錯機制（fault tolerance）。當然這不是本文的重點，這裡就不展開了。另一個 feature 是 NVRAM 的讀寫的非對稱性。在新硬體上，讀頻寬是不錯的，但是寫頻寬則相差數倍。同時這個差距可以認為在短期不會有所改善，因為這是由於新硬體的技術原因造成的。

圖4。左圖：新 NVRAM 的讀寫頻寬比較。右圖：物質的晶體態和無定形態，可以感受到兩者電阻差別會很大。

簡而言之，NVRAM透過

物質的狀態

來儲存資訊。特定物質可以在晶體和無定形體切換，而不同的相的電阻有明顯的區別，可以用來儲存資訊。對於讀只要加電壓測試電阻即可，但是寫則需要融化然後透過降溫控制。因此寫的開銷相較於讀會大很多。

因此，如果在計算中使用 NVRAM，那麼

如果演算法中的寫操作很多則效率就會很差

。這類新的體系結構的改變會對於演算法研究提出了全新的要求。舉例而言，在早期使用磁帶時隨機訪問很慢，因此在1970年 B-tree 就被提出以減小隨機訪存次數。而當 DRAM 技術普及和後期且 cacheline 大小僅有 64byte 的情況下，上文提到的二叉搜尋樹（BST）則會減小總的 memory footprint 進而達到更好的效果。在並行的要求下，則我們需要新的 P-tree 來處理資料。同理當 NVRAM 出現後，我們需要新的演算法以減少寫的次數來提高演算法的效率。

早在 2014 年我們就和 Intel 合作開始進行這類演算法的研究，我們稱之為 write-efficient algorithms。我們需要解決的第一個問題就是，如何設計計算模型將讀寫不對稱性加入複雜度分析中。本科演算法課我們通常使用 time complexity 分析演算法，雖然簡單但是非常不精確。有很多更加精確的計算模型可以將I/O、並行和其它方面的影響加入分析中，得到效能更優的演算法。同理對於NVRAM，我們設計了一系列新模型可以將運算元、I/O、caching和並行等因素，以及

額外的寫代價

考慮在內。在此基礎上，我們設計了新的基礎的演算法比如排序以及各種序列操作，以及關於圖、幾何和DP等演算法。這些演算法不僅能在新的模型中得到理論的提升，在實際測試中也與理論的預期值吻合。

還是拿排序演算法舉例，複雜度為 O（n log n） 的快排和歸併排序都需要對記憶體進行 O（n log n） 次寫（歸併排序要進行 log n 次合併操作，每次要操作整個陣列的 n 個數，快排的 partition 同樣是大致 O（log n） 次，每次操作所有 n 個數）。反而是複雜度 O（n^2） 的選擇排序只需要寫 O（n） 次記憶體（每次找到對應的數往記憶體寫一次）。那能不能有 O（n log n） 複雜度的排序演算法只需要寫 O（n） 次的呢？其實已有的演算法裡就有這樣的例子。感興趣的同學可以參考課件（連結），在這裡本文提到的。

對於這一類演算法有興趣的同學可以參考 ［5］。排序當然只是一個最簡單的例子，同時在上文的例子中我們也沒有考慮並行、I/O 等問題。對於很多其它的演算法，我們也需要重新設計以獲得更好的效能。下圖給了一個新的最短路演算法的實際測試的記憶體讀寫次數的加權和，在多數情況下效果要好於經典演算法。在最新的工作中我們給出了基於 NVRAM 寫最佳化的圖演算法庫，有興趣的同學可以參考相關論文 ［6］，甚至可以下載程式測試（如果大家能access這類新硬體的話 ）。

圖5：新的最短路演算法的加權讀寫代價。紅色為新演算法。ω 為寫比讀的代價倍數。

其它有趣的問題

上文給出了兩個關於現代的演算法研究的例子，實際上我們還有很多其它有趣的工作。理論上講，其它一些我們做過的演算法還有並行的增量三角剖分（Delaunay triangulation），並行強連通分支（strongly connected components），以及一個非常簡單的並行最短路演算法等等，這些都是並行演算法中長時間未能很好解決的問題。實現方面，上述三角剖分和強連通分支的演算法已經在我們維護的並行演算法庫中，效能要好於之前所有的演算法。我們既設計和實現最快的經典演算法如排序、半排序（semisort）、隨機排列（random permutation），也包括並行其它領域和實際問題中的演算法，比如資料庫索引（database indexing），垃圾回收（garbage collection）機制，各種聚類演算法等等。

希望上述的內容能對於大家瞭解新的演算法設計和平行計算中的挑戰有所幫助。對於有興趣的同學們，我們歡迎大家加入加州大學河濱分校（University of California - Riverside）計算機系演算法和平行計算的實驗室，一起設計不僅有理論價值且有實際應用的高效演算法。

關於 UC Riverside

UC Riverside 坐落於溫暖的加州，在洛杉磯市市郊、距離中心約一小時車程的 Riverside。計算機系排名在 US News 排名 61，不過 US News 排名是基於印象的打分。在根據科研水平的排名 CS Ranking 中，近五年資料總體排名在30-35名之間（連結，排名實時浮動），其中高效能計算方向排名高居第4（連結）。系裡有很多優勢研究方向，除了高效能計算，還有計算生物學，計算機安全，計算機系統，資料庫和資料探勘，等等。也歡迎對別的研究方向有興趣的同學們申請！

博士研究生在校第一年會獲得 Fellowship，在此之後由研究導師提供的科研崗位（RA）或者系內助教（TA）獲得學費和生活費。UC Riverside 地處加州，相對於許多學校對於實習和就業等有非常大的

地理優勢

。此外 UCR 計算機繫有許多優秀的華人老師和學生，Riverside 和洛杉磯附近有

非常好吃的中餐

（知道你們在申請的時候會關注這個！）。Riverside 生活成本不算太高，但是因為鄰近洛杉磯可以享受到各種方便的娛樂活動（演唱會等等），娛樂設施（各種主題公園，國家公園，好萊塢），機場（國內主要城市均有直飛、只要八至十個小時且機票通常非常便宜），中超等等。同時洛杉磯的各種運動隊近年表現很出色，對於體育感興趣的同學一定不會失望。

計算機系官網：

https：//

www1。cs。ucr。edu/

Ph。D。 專案簡介：

https：//

www1。cs。ucr。edu/graduat

e/programs/computer-science-phd

教授們的列表：

https：//

www1。cs。ucr。edu/people/

faculty

招生連結：

https：//

graduate。ucr。edu/admiss

ions

關於我們

Yan Gu（顧研）2012年畢業於清華計算機系，同年進入卡內基梅隆大學（Carnegie Mellon University，CMU）攻讀博士學位。2018年，顧研從 CMU 取得博士學位畢業，並開始在 MIT 進行了一年的博士後工作。他有多年的資訊學競賽和 ACM ICPC 經歷和經驗，並且曾經在計算機圖形學，計算機理論，並行演算法等多個研究方向都有成果和論文發表。

Yihan Sun（孫藝瀚）2014年畢業於清華計算機系，並進入卡內基梅隆大學（Carnegie Mellon University，CMU）攻讀博士學位。她在2019年從 CMU 取得博士學位畢業並進入 UC Riverside 成為助理教授。她曾在資料探勘，計算生物學，計算機理論，並行演算法，資料庫等多個研究方向都有成果和論文發表。

我們即將同時進入UC Riverside 計算機系，並希望和有興趣的同學們一起組建起演算法和平行計算實驗室。

如何聯絡我們

有興趣的同學們可以先看一下我們的主頁：

顧研：

http：//

people。csail。mit。edu/gu

yan/

孫藝瀚：

https：//www。

cs。cmu。edu/~yihans/

如果有興趣申請，可以直接給我們發郵件（郵箱地址見主頁）。請附上你的 CV，和任何你覺得對你申請有幫助的資料。這裡是申請連結：

https：//

graduate。ucr。edu/admiss

ions

我們希望能招到對演算法和平行計算方面有興趣，有能力的博士生們。我們希望學生可以有一定的演算法基礎（有過參加競賽的經歷會很有幫助）和程式設計基礎，有CS的本科背景或上過相關本科課程，此外如果有科研經歷也會優先考慮哦。

（本文歡迎轉載，但請註明出處）

本系列其它文章：

參考文獻

［1］ Guy Blelloch， Phillip Gibbons， and Harsha Vardhan Simhadri。 Low-depth cache-oblivious algorithms。 In ACM Symposium on Parallelism in Algorithms and Architectures （SPAA）， 2010。

［2］ Thomas Cormen， Charles Leiserson， Ronald Rivest， and Clifford Stein。 Introduction to Algorithms （3rd edition）。 MIT Press， 2009。

［3］ Guy Blelloch， Daniel Ferizovic， and Yihan Sun。 Just join for parallel ordered sets。 ACM Symposium on Parallelism in Algorithms and Architectures （SPAA）， 2016。

［4］ Yihan Sun， Guy E Blelloch， Wan Shen Lim， and Andrew Pavlo。 On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes， Proceedings of the VLDB Endowment （PVLDB）， 2019。

［5］ Yan Gu。 Write-Efficient Algorithms。 PhD Thesis， Carnegie Mellon University， 2018。

［6］ Laxman Dhulipala， Charles McGuffey， Hongbo Kang， Yan Gu， Guy E。 Blelloch， Phillip B。 Gibbons， Julian Shun。 Semi-Asymmetric Parallel Graph Algorithms for NVRAMs。 arXiv：1910。12310， 2019。