并行算法基本概念

本文主要包含如下内容：

• 并行算法基本概念
  • 并行算法的分類
  • 并行算法的特征
  • 并行算法的速度和效率

并行算法的分類

Task parallelism and Data parallelism　任務并行和資料并行

  

Task parallelism

：對任務進行并行化處理，每個核進行不同的操作。

  

Data parallelism

：對資料進行并行化處理，每個核對不同資料進行類似的操作。

Shared-memory and Distributed-memory 共享記憶體與分離式記憶體

  

Shared-memory

：核心可以共享計算機的記憶體

  

Distributed-memory

：核心隻能夠通路自己的私有記憶體

并行算法的特征

Communication　通信

  每個核心需要對該核的算法輸入資料和計算結果的資料進行通信、傳輸。

Load balancing 負載均衡

  為了加快運算速度，希望每個核完成運算時間基本一緻，是以希望達到負載均衡。

Synchronization　同步

  因為每個核心之間存在資料通信，是以需要等待所需資料的計算結果。

并行算法的速度和效率

Speedup

  p= Number of cores （核心數目）

  T serial = Serial run-time （串行運作時間）

  T parallel = Parallel run-time （并行運作時間）

Tparallel=TserialP 

S=TserialTparallel 

Efficiency

E=SP=TserialTparallelP=TserialP∗Tparallel

Tparallel=TserialP+Toverhead

  許多并行程式是通過将程序/線程之間的串行程式的工作分開，并添加必要的“并行開銷”，例如互斥或通信來開發的。此外，随着問題大小的增加，T_overhead通常比T_serial慢得多。 程序/線程有更多的工作要做，是以協調程序/線程工作的相對時間應該更少。