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