过易并行

并行计算中，过易并行（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]

例子

[编辑]

过易并行问题的例子有

实现

[编辑]
  • R语言 – 工作站简单网络（SNOW）包实现了一种简单机制，可使用一组工作站或贝奥武夫机群进行过易并行问题的并行计算。[16]类似的R包还有“future”“parallel”等。

另见

[编辑]

参考文献

[编辑]
  1. ^ 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. 
  2. ^ Section 1.4.4 of: Foster, Ian. Designing and Building Parallel Programs. Addison–Wesley. 1995. ISBN 9780201575941. （原始内容存档于2011-03-01）. 
  3. ^ Alan Chalmers; Erik Reinhard; Tim Davis. Practical Parallel Rendering. CRC Press. 21 March 2011. ISBN 978-1-4398-6380-0. 
  4. ^ Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. ISBN 9781593274108.
  5. ^ 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. 
  6. ^ Moler, Cleve. Matrix Computation on Distributed Memory Multiprocessors. Heath, Michael T. (编). Hypercube Multiprocessors. Society for Industrial and Applied Mathematics, Philadelphia. 1986. ISBN 978-0898712094. 
  7. ^ The Intel hypercube part 2 reposted on Cleve's Corner blog on The MathWorks website
  8. ^ Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. ISBN 9780898716733.
  9. ^ Erricos John Kontoghiorghes. Handbook of Parallel Computing and Statistics. CRC Press. 2005-11-21. ISBN 978-1-4200-2868-3. 
  10. ^ Yuefan Deng. Applied Parallel Computing. World Scientific. 2013. ISBN 978-981-4307-60-4. 
  11. ^ Josefsson, Simon; Percival, Colin. The scrypt Password-Based Key Derivation Function. tools.ietf.org. August 2016 [2016-12-12]. doi:10.17487/RFC7914. 
  12. ^ Mathog, DR. Parallel BLAST on split databases.. Bioinformatics. 22 September 2003, 19 (14): 1865–6. PMID 14512366. doi:10.1093/bioinformatics/btg250 可免费查阅. 
  13. ^ How we made our face recognizer 25 times faster (developer blog post)
  14. ^ Shigeyoshi Tsutsui; Pierre Collet. Massively Parallel Evolutionary Computation on GPGPUs. Springer Science & Business Media. 2013-12-05. ISBN 978-3-642-37959-8. 
  15. ^ Youssef Hamadi; Lakhdar Sais. Handbook of Parallel Constraint Reasoning. Springer. 2018-04-05. ISBN 978-3-319-63516-3. 
  16. ^ Simple Network of Workstations (SNOW) package

外部链接

[编辑]