过易并行

并行计算中，过易并行（embarrassingly parallel，也称作embarrassingly parallelizable、完美并行perfectly parallel、delightfully parallel、pleasingly parallel）是指（几乎）不需要努力就能拆分成若干并行任务的问题。这是因为，并行任务之间的通信或结果的相互依赖（几乎）为零。Section 1.4.4 of: 

这些问题与分布式计算问题不同，后者需要任务间的通信，尤其是中间结果的通信。过易并行问题更容易在缺乏超级计算机集群所需的特殊设施的服务器集群执行，非常适合基于互联网的志愿计算平台，如BOINC等，且受并行减速影响较小。同过易并行相反的是本质上无法并行化的连贯串行问题。

过易并行问题的常见例子如GPU处理的3D视频渲染，每帧（前向法）或像素（光线追踪法）都可单独处理，没有任何相互依赖关系。某些形式的密码破解也过易并行的，很容易分布在CPU、多核处理器或集群中。

词源
英语中，过易并行称作“embarrassingly parallel”，即“令人尴尬的并行”。“Embarrassingly，令人尴尬”这里是指处理起来“容易得尴尬”。Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design, p.347. No Starch. .这个词契合了很多开发者或编译器的尴尬：很多重要问题因其固有的计算复杂性而未得到解决，不开发多项式同伦延拓法的并行实现将是令人尴尬的。MATLAB的创立者克里夫·莫勒尔1986年译本关于多处理器的书中最早出现了这个词，莫勒尔自称是此术语的发明者。

为回避“embarrassing，尴尬”的负面含义，也有人用“pleasingly/perfectly parallel，令人愉悦/完美的并行”称呼之。Kepner, Jeremy (2009). Parallel MATLAB for Multicore and Multinode Computers, p.12. SIAM. .

例子
过易并行问题的例子有
 蒙特卡洛分析
 分布式集合处理 的分布式关系数据库查询
 数值积分
 批量处理性质相似的无关文件，如图库的大小调整与转换
 曼德博集合、Perlin噪声与相似的图像，每个点都是独立计算的
 计算机图形中的渲染。计算机动画的每帧或像素都可以独立渲染（见并行渲染）。
 密码学中的一些暴力搜索。著名例子有加密货币中使用的distributed.net与工作量证明系统。
 生物信息学中使用分裂数据库进行BLAST搜索
 大规模人脸识别系统，将数千张任意获取的人脸（如由闭路电视获取的安全或监控视频），与之前存储的大量人脸进行比较How we made our face recognizer 25 times faster  (developer blog post)
 计算机模拟，比较多个独立场景
 遗传算法
 数值天气预报的系综计算
 粒子物理学中的事件模拟与重建
 marching squares算法
 二次筛选法和普通数域筛选法的筛选步骤
 随机森林机器学习技术的树生长步骤
 独立计算各次谐波的离散傅里叶变换
 GPU上运行的卷积神经网络
 约束编程中的并行搜索

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

另见
 阿姆达尔定律
 映射 (并行模式)
多元处理
大规模并行
并行计算
面向进程编程
独享型体系结构 (SN)
对称多处理 (SMP)
连接机
元胞自动机
CUDA
众核处理器
向量处理器

参考文献

外部链接
 Embarrassingly Parallel Computations , Engineering a Beowulf-style Compute Cluster
 "Star-P: High Productivity Parallel Computing "

Category:并行计算