並行縮減(例如如何對陣列求和)

並行約簡演算法通常是指組合元素陣列,產生單個結果的演算法。屬於此類別的典型問題是:

  • 總結陣列中的所有元素
  • 在陣列中找到最大值

通常,並行縮減可以應用於任何二元關聯運算子 ,即 (A*B)*C = A*(B*C)。使用這樣的運算子*,並行縮減演算法重複地成對地對陣列引數進行分組。每對與其他對平行計算,一步將整個陣列大小減半。重複該過程直到僅存在單個元素。

如果運算子除了是關聯的之外是可交換的 (即 A*B = B*A),則演算法可以以不同的模式配對。從理論的角度來看,它沒有任何區別,但在實踐中它提供了更好的記憶體訪問模式:

並非所有關聯運算子都是可交換的 - 例如採用矩陣乘法。