转载 编写并行程序的一般步骤

jingjingpei

【 原文由 Gryffindor 所发表 】
1.将计算分解为任务（Decomposition）
2.把任务分配到各进程（Assignment）
3.协调各进程之间的通信（Orchestration）
4.把进程映射到处理器 （Mapping）
1.在这个阶段，只考虑问题本身，忽略具体的编程模型和体系结构。
  目标：负载平衡，减少同步互斥的开销
        减少通信
        减少由于任务分配所带来的附加开销
  但这些目标往往是有矛盾的。Trade Off !
2.发掘问题中的并行性
    数据并行：相同操作同时作用在不同的数据上，其并行度往往随着问题规模的
增大而增大。
    任务并行：同时有多个不同任务并行执行，并行度随问题规模的变化影响较小
。（两种形式）
    一个具体的问题中往往包含多个层次的并行，例如洋流问题。
任务分配
    静态分配：只有对问题的运行有充分的预测，才能获得较好性能。（拉普拉斯方程）
    半静态分配：运行前先分配任务，运行过程中周期性的计算负载情况，调整任务在
各进程的分配。（星系演化问题）
    动态分配：对于问题的运行过程无法预知；通常用任务池和任务队列实现，有利于
获得良好的负载平衡，但增加了维护任务队列的开销，并且可能增加通信，减少数据局
部性。（光线跟踪问题）
3.程序执行过程中除了程序内在（inherent）通信外的其它所有通信。
    1.  数据的不合理分配
    2.  传输中的不必要数据  （figure 3.9）
    3.  由于别的系统不同的粒度造成的不必要传输
    4.  冗余的数据传输
    5.  有限的复制容量 （replication capacity）
            （cache size 或 memory size）
      four C’s: 冷启，冲突，容量，通信失效
      工作集：在一段时间内密集访问的程序代码或数据。
      应尽可能地使复制容量大于程序的工作集（figure 3.6）。
      通信结构：通信消息的大小；通信的频繁程度；通信开销能否被计算或其它通信
      重叠；互联网络的拓扑结构是否与通信模式匹配。
4.减少 o:  大消息
  减少 l:  更好地把并行算法映射到网络拓扑结构 ( f*h*t )
  减少 t:  竞争的危害性；网络上的两类竞争（network & endpoint）；树结构来减少
竞争（barrier）；原则：避免多个进程同时与一个进程通信，在时间上错开发往同一目
的地的消息。
  增加 overlap: 4类方法；非堵塞的send & receive 原语

kartwall

不错的文章
支持楼主