Designning Parallel Algorithm

• Foster’s methodology
• Steps
  • Partitioning
  • Communication
  • Agglomeration
  • Mapping

Partitioning（分区）

• Domain decomposition（按地方分）
  • Decompose the data associated with a problem
  • We divide these data into small pieces of approximately equal size if possible.
• Functional decomposition（按功能分）
  • Divide the computation into disjoint tasks

Communication（通讯器）

• Work out messages that are to be sent and received.
• In domain decomposition problems, communication requirements can be difficult
  to determine.
• In contrast, communication requirements in parallel algorithms obtained by functional decomposition are often straightforward.
  
  通讯器定义了一组能够互相发消息的进程。在这组进程中，每个进程会被分配一个序号，称作 秩（rank） ，进程间显性地通过指定秩来进行通信。

Agglomeration（聚集）

• Combine tasks and communications identified in the first step into larger tasks.
  
  用已经确定的分区和通信进行合并。

Mapping（映射）

• Assign the composite tasks identified in the previous step to processes/threads.
  
  将上一步中确定的复合任务分配给进程/线程。
• This should be done so that the communication is minimised, and each processes/threads gets roughly the same amount of work.
• Many algorithms developed using domain decomposition techniques feature a fixed number of equal-sized tasks and structured local and global communication. In such cases, an efficient mapping is straightforward.

Distributed Memory Programming with Message Passing

版权属于：KevinBean

本文链接：https://www.kevinbean.top/index.php/default/344.html

转载时须注明出处及本声明