PCAM是Partitioning(划分)、Communication(通信)、Agglomeration(组合)和Mapping(映射)的缩写,它们表示了使用此法设计并行算法的四个阶段:任务划分、通信分析、任务组合和处理器映射,简称划分、通信、组合、映射。PCAM是一种设计方法学,是实际设计并行算法的自然过程。PCAM设计方法的思想是:先尽量开拓算法的并发性和满足算法的可扩展性,然后着重优化算法的通信成本和全局执行时间。具体来说,在任务划分和通信分析阶段主要考虑算法的并发性和可扩展性等与机器无关的特性。在任务组合和处理器映射阶段主要考虑局部性和其它与性能有关的问题。各阶段的任务如下:
划分:将整个计算任务分解成一些小任务,其目的是尽量开拓并行执行的可能性;
通信:确定小任务执行中需要进行的通信,为组合做准备;
组合:按性能要求和实现的代价来考察前两阶段的结果,适当地将一些小任务组合成更大的任务以提高性能、减少通信开销;
映射:将组合后的任务分配到处理器上,其目标是使全局执行时间和通信开销尽量小,使处理器的利用率尽量高。
下图表现了PCAM设计过程。
PCAM设计方法的四个阶段虽然是一步一步进行的,但实际上它们可以同时一并考虑。并且在设计过程中可能需要回溯反复,不断调整。
|