并行计算如何用于科学问题研究

2022-09-10

1 研究背景

进行并行计算, 目的是为了节约计算时间, 快速地解决运算规模比较宏大的问题。从算法设计的角度, 并行计算可分为数据并行和任务并行, 数据并行是将大任务划分成相同的各个子任务, 任务并行是将大任务划分成相互独立的任务模块。

并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生, 按照Flynn可分为:单指令流多数据流 (S I M D) 和多指令流多数据流 (MIMD) 。

目前的研究文献主要集中在算法本身的优劣, 以及如何在特定领域提高算法的精度等, 对科研过程中如何运用并行算法论述较少。这对于初学者是不利的。本文通过对文献调研, 补充和完善这个方面的知识。

2 适合并行计算的任务的特征

通过并行计算的特点可以看出, 研究问题应用并行算法需要考虑到其本身的特性, 不同的问题应用并行算法的效果不一样, 具体情况如下。

2.1 数据或者计算量大的任务

并行计算和串行计算的差别在于同时进行, 这样可以减少计算时间, 但是会增加通信时间。并行计算适用于解决数据粒度大的问题, 能够极大地提高效率。数据粒度小的问题, 适合用串行计算解决问题。

2.2 数据重复性高的任务

数据量较大、数据处理方法相类似的研究问题适合用并行计算解决。通常来说, 遥感观测、理化实验、经济统计等领域, 数据观测周期相对较长, 获取周期可能是年或月, 数据量大, 但是这些海量数据可能在不同时间的格式相同, 处理流程也是相同的, 可以运用并行计算中的数据并行模式。

2.3 操作间通信少的任务

对于特定的任务, 往往不是一步就能够完成的, 需要进行多步操作。如果一个操作的输入参数来源于前一个操作的输出, 就需要对数据进行同步;如果一个操作的完成需要别的操作提供参数, 那么就需要进行数据传输。

由于网络的问题, 通信成为制约并行计算的瓶颈。能够划分成多个松散耦合模块的问题, 非常适合并行计算。一般来说, 适合面向对象编程技术解决的问题, 比较适合并行计算。例如决策系统 (如交通指挥系统、灾害指挥系统) 的底层信息处理, 需要对很多不同的参数进行处理, 每一类数据就如同一个对象一样, 处理方法是不同的, 往往不需要进行通信, 选择并行计算, 可以节约很多时间。

3 并行计算解决问题的基本思路

利用并行计算解决实际问题, 需要从事数据划分、任务分解、算法设计、问题解决几个步骤。前期的数据划分、任务分解、算法设计, 会影响到并行计算效用的发挥。每个操作步骤需要考虑的因素不同, 下面进行简单论述。

3.1 数据划分

数据划分的效果和质量, 会影响到并行计算的效率。进行数据划分, 要考虑到任务的特点, 对原始数据依赖越强的应用, 划分越简单;对抽象数据 (所谓抽象数据, 是指需要对原始数据进行处理, 得出一些含有知识的数据, 例如通过对图像进行处理, 得出道路的信息, 道路是原始数据中不具备的数据, 因此成为抽象数据) 依赖很强的数据, 划分需要考虑应用的特点。整个过程需要遵循是MIMD的思路。

划分分为两步, 首先将数据的功能进行分类, 得到单独的数据模块, 保证数据模块间的耦合性最低。然后对每个数据模块的数据, 划分成很多等份的数据, 使每个处理器处理的数据量较小。因此, 同一个问题, 可以先按照功能进行数据分来, 再按照数据量大小分成小分数据。

3.2 任务分解

对于每一份数据, 都有特定的处理方法, 因此会产生很多任务, 将这些任务进行分解, 可以很好地用于问题解决和并行算法设计。对于特定数据, 处理过程一般有流水线和并发访问两种模式, 整个过程需要遵循是MISD的思路。

将数据处理, 按照一定的逻辑关系进行划分成很多步骤, 尽量做到每一个操作, 仅仅与另一个操作存在着输入输出的关系, 操作执行过程和别的操作同步和通信的需求最小。操作的抽象程度越高, 与前面操作的同步要求越高, 因此设计也越困难。

3.3 算法设计

将数据和任务划分清楚以后, 就需要设计并行算法实现高效的并行计算了。并行算法编写, 有以下问题需要注意。

3.3.1 选择编程模式

一般并行算法有主从模式 (Masters l a v e) 、对称模式 (S P M D) 、多程序模式 (MPMD) 。这要根据问题的复杂程度、数据的特点和任务的分解结果进行处理。如果任务需要划分很多次, 并且需要随时调整, 那么最好选择主从模式;如果数据比较简单, 任务分好一次之后, 就可以出结果了, 可以选择对称模式;如果数据比较复杂, 能够划分出不同模块, 那么可以选择多程序模式。当然, 也可以根据实际问题, 进行混合选择。

3.3.2 实现并行算法

实现并行算法, 需要考虑很多因素。下面以比较流行的SPMD模式, 论述需要考虑的因素。

进程控制:在SPMD并行程序的编写过程中, 因为只有一份程序, 每个处理机上执行的是相同的程序。因此, 对于每个进程来说, 需要知道自己是属于哪个进程, 从而来确定该进程需要完成的任务。进程控制是并行程序的重要组成部分, 所有的数据处理和交换过程都离不开进程标识, 是在实现过程中必须时刻要牢记的。

数据交换:在SPMD模式中, 数据交换是其主要特征。进程之间的协同工作, 信息沟通等都离不开数据交换。如何合理地实现数据交换, 是提高并行计算程序性能的关键之一。对于一个给定的并行计算方法, 为了高效率的实现, 需要仔细分析数据依赖关系, 尽可能减少不必要的数据交换, 同时也要尽最大努力使数据交换在最少的次数内完成。

面向对象化:建立自己的通讯库, 使程序具有更加直观的可读性。比如说, 在处理机中要进行矩阵传输, 那就需要定制一个子程序来完成这项任务。