热门问题
时间线
聊天
视角
过易并行
来自维基百科，自由的百科全书
Remove ads
并行计算中，过易并行（embarrassingly parallel，也称作embarrassingly parallelizable、完美并行perfectly parallel、delightfully parallel、pleasingly parallel）是指（几乎）不需要努力就能拆分成若干并行任务的问题。[1]这是因为，并行任务之间的通信或结果的相互依赖（几乎）为零。[2]
这些问题与分布式计算问题不同，后者需要任务间的通信，尤其是中间结果的通信。过易并行问题更容易在缺乏超级计算机集群所需的特殊设施的服务器集群执行，非常适合基于互联网的志愿计算平台，如BOINC等，且受并行减速影响较小。同过易并行相反的是本质上无法并行化的连贯串行问题。
过易并行问题的常见例子如GPU处理的3D视频渲染，每帧（前向法）或像素（光线追踪法）都可单独处理，没有任何相互依赖关系。[3]某些形式的密码破解也过易并行的，很容易分布在CPU、多核处理器或集群中。
Remove ads
词源
英语中，过易并行称作“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]
Remove ads
实现
另见
参考文献
外部链接
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads