過易並行
並行計算中，過易並行（embarrassingly parallel，也稱作embarrassingly parallelizable、完美並行perfectly parallel、delightfully parallel、pleasingly parallel）是指（幾乎）不需要努力就能拆分成若干並行任務的問題。[1]這是因為，並行任務之間的通信或結果的相互依賴（幾乎）為零。[2]
這些問題與分佈式計算問題不同，後者需要任務間的通信，尤其是中間結果的通信。過易並行問題更容易在缺乏超級計算機集群所需的特殊設施的伺服器集群執行，非常適合基於互聯網的志願計算平台，如BOINC等，且受並行減速影響較小。同過易並行相反的是本質上無法並行化的連貫串行問題。
過易並行問題的常見例子如GPU處理的3D視頻渲染，每幀（前向法）或像素（光線追蹤法）都可單獨處理，沒有任何相互依賴關係。[3]某些形式的密碼破解也過易並行的，很容易分佈在CPU、多核處理器或集群中。
詞源
[編輯]英語中，過易並行稱作「embarrassingly parallel」，即「令人尷尬的並行」。「Embarrassingly，令人尷尬」這裏是指處理起來「容易得尷尬」。[4]這個詞契合了很多開發者或編譯器的尷尬：很多重要問題因其固有的計算複雜性而未得到解決，不開發多項式同倫延拓法的並行實現將是令人尷尬的。[5]MATLAB的創立者克里夫·莫勒爾1986年譯本關於多處理器的書中最早出現了這個詞，[6]莫勒爾自稱是此術語的發明者。[7]
為迴避「embarrassing，尷尬」的負面含義，也有人用「pleasingly/perfectly parallel，令人愉悅/完美的並行」稱呼之。[8]
例子
[編輯]過易並行問題的例子有
- 蒙特卡洛分析[9]
- 分佈式集合處理的分佈式關係數據庫查詢
- 數值積分[10]
- 批量處理性質相似的無關文件，如圖庫的大小調整與轉換
- 曼德博集合、Perlin噪聲與相似的圖像，每個點都是獨立計算的
- 計算機圖形中的渲染。計算機動畫的每幀或像素都可以獨立渲染（見並行渲染）。
- 密碼學中的一些暴力搜索。[11]著名例子有加密貨幣中使用的distributed.net與工作量證明系統。
- 生物信息學中使用分裂數據庫進行BLAST搜索[12]
- 大規模人臉識別系統，將數千張任意獲取的人臉（如由閉路電視獲取的安全或監控視頻），與之前存儲的大量人臉進行比較[13]
- 計算機模擬，比較多個獨立場景
- 遺傳算法[14]
- 數值天氣預報的系綜計算
- 粒子物理學中的事件模擬與重建
- marching squares算法
- 二次篩選法和普通數域篩選法的篩選步驟
- 隨機森林機器學習技術的樹生長步驟
- 獨立計算各次諧波的離散傅里葉變換
- GPU上運行的卷積神經網絡
- 約束編程中的並行搜索[15]
實現
[編輯]另見
[編輯]參考文獻
[編輯]- ^ Herlihy, Maurice; Shavit, Nir. The Art of Multiprocessor Programming, Revised Reprint revised. Elsevier. 2012: 14 [28 February 2016]. ISBN 9780123977953.
Some computational problems are 「embarrassingly parallel」: they can easily be divided into components that can be executed concurrently.
- ^ Section 1.4.4 of: Foster, Ian. Designing and Building Parallel Programs. Addison–Wesley. 1995. ISBN 9780201575941. （原始內容存檔於2011-03-01）.
- ^ Alan Chalmers; Erik Reinhard; Tim Davis. Practical Parallel Rendering. CRC Press. 21 March 2011. ISBN 978-1-4398-6380-0.
- ^ Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. ISBN 9781593274108.
- ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan. Parallel Homotopy Algorithms to Solve Polynomial Systems. Mathematical Software - ICMS 2006. Lecture Notes in Computer Science 4151. 2006: 225–234. ISBN 978-3-540-38084-9. doi:10.1007/11832225_22.
- ^ Moler, Cleve. Matrix Computation on Distributed Memory Multiprocessors. Heath, Michael T. (編). Hypercube Multiprocessors. Society for Industrial and Applied Mathematics, Philadelphia. 1986. ISBN 978-0898712094.
- ^ The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website
- ^ Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. ISBN 9780898716733.
- ^ Erricos John Kontoghiorghes. Handbook of Parallel Computing and Statistics. CRC Press. 2005-11-21. ISBN 978-1-4200-2868-3.
- ^ Yuefan Deng. Applied Parallel Computing. World Scientific. 2013. ISBN 978-981-4307-60-4.
- ^ Josefsson, Simon; Percival, Colin. The scrypt Password-Based Key Derivation Function. tools.ietf.org. August 2016 [2016-12-12]. doi:10.17487/RFC7914.
- ^ Mathog, DR. Parallel BLAST on split databases.. Bioinformatics. 22 September 2003, 19 (14): 1865–6. PMID 14512366. doi:10.1093/bioinformatics/btg250
.
- ^ How we made our face recognizer 25 times faster (developer blog post)
- ^ Shigeyoshi Tsutsui; Pierre Collet. Massively Parallel Evolutionary Computation on GPGPUs. Springer Science & Business Media. 2013-12-05. ISBN 978-3-642-37959-8.
- ^ Youssef Hamadi; Lakhdar Sais. Handbook of Parallel Constraint Reasoning. Springer. 2018-04-05. ISBN 978-3-319-63516-3.
- ^ Simple Network of Workstations (SNOW) package
外部連結
[編輯]- Embarrassingly Parallel Computations, Engineering a Beowulf-style Compute Cluster
- "Star-P: High Productivity Parallel Computing"
