將並行計算納入演算法競賽，是否合適？

01-11

（題外話：很多其他回答對於並行演算法的認識很膚淺啊。說什麼並行演算法簡單粗暴的，依賴硬體的，真是呵呵了。說並行計算相關的演算法和普通的演算法競賽差距太大，也是因為並行演算法的學習門檻比較高。競賽中的問題（除了網路流）用到的演算法都能並行，不過以一般OI選手的學習能力，大概花半年到一年的時間還達不到學習到這類演算法的階段。而把這些時間花在學現在的競賽題，那早就可以在OJ上刷的風生水起了。這也從層面說明了並行演算法難度過大，不適合作為競賽內容。因此致力於簡化並行演算法也是我們目前主要的課題之一。）

我也是不太認同將並行加入程序競賽的，因為設計好的並行演算法需要對於architecture的了解，需要很多細節的考量，這個和ICPC之類抽象的層面解決問題的要求是背道而馳的。

其實對於並行演算法的競賽問題，我們業界內也是有過很多討論的。像現在ISC這種主要靠「搞」的比賽明顯是不可取的（因此你看除了中國之外，世界上並沒有主流學校參與，也沒有意願參與。ACM/ICPC世界上還是所有名牌大學都參與的）。但是由於並行演算法太難，簡單的問題都有現成的寫法，稍微有點難度的問題所需要的知識一般本科階段的理解力基本掌握不了，因此也是很頭疼的事情。

ps. 經評論指出，其實很多其他答案和評論說的是（並行編程/語言/實現），不是並行演算法。當然這些是學習並行演算法的基礎，但是不是一碼事。類比學習C++/Java語言和學習演算法。既然說到競賽，那肯定是指演算法，畢竟也沒有C++/Java語言比賽（除了混亂C大賽），只有演算法競賽。不過非常遺憾的是除了復旦的唐老師之外，我還不知道國內有誰還算是比較懂並行演算法的了，於是如此完善的一個演算法體系，並沒有任何中文的教材和中文的課程，所以大家根本不知道他的存在也就不足為奇了。（所以說中國的CS教育和美國的差距還有好幾光年啊！）

同意 @Yan Gu。

我並不希望並行演算法加入演算法競賽，因為本質上並行化是個工程學問題，並非計算機科學問題。

倒不是說並行化沒有計算機科學的部分，而是所有並行化直接試圖解決的是應用上的局限，而非理論上的。極端歸納地考慮，如果有一台理想計算機，那麼所有並行化都不需要，直接把運算交給最優的串列的演算法即可。可是演算法競賽要解決的問題都是具備理想計算機假設的。雖然操作中有各種實際限制，但要解決的問題是抽象的。

然而，如果要考察並行化演算法，必須要有場景，要有具體的環境和問題。因為如果用抽象問題和抽象環境的話，至少MapReduce模型證明所有並行化都可以簡化為幾個排序問題加最優的串列演算法，所有人解法可以都一樣，不具備競賽性。當然特定演算法可以有更多種並行化模型，但選出最優模型是環境相關的。

如果需要用一個競賽來推廣發展，那麼應該是一個類似於機器人大賽性質的工程學競賽，而非演算法競賽的模式。

這是今年Google code jam Distributed的例題

Frequently Asked Questions

我覺得有創新總是好的，而且現在並行計算這麼火。

等這個Distributed Code Jam比完了再來補充感受吧，當然前提是我得進得了~

反對「並行就是簡單粗暴地加快程序速度」的觀點。

如果去過WC2017就會知道，有的演算法直接做是不可並行的。

比如給 $n$ 個數排序，有 $m$ 台機器（ $n,m$ 分別是 $10^8$ 和 $10^2$ 數量級），用快速排序/歸併排序之類的 $O(nlog n)$ 演算法不好並行。假設這些數兩兩不同，從這些數中隨機選 $k$ 個（ $k$ 不需要很大）排序，再均勻選出 $m-1$ 個數，把 $n$ 個數均勻分成 $m$ 段，再讓每個機器對每一段進行排序，最後合併即可，這樣就能做到 $O(frac{nlog n}{m})$ 的期望複雜度。