Parallel Computing Concepts

影響平行化速度的5個要素

1.       Converge

           -程式中可平行化的部份

2.       Granularity

           -程式中對資料的切割使得資料不太需要同步

3.       Balance

           -對處理資料的切割如何達到公平，使得不會因為某些thread的工作太多而使得其他人要  去等待它，可分為

I.             Static

在平行化前就將thread要做的工作分配，在homogenous multi-core的架構下有很好的效果，但在處理heterogeneous multi-core 時會因為核心的工作效率不同以及使用的function而產生麻煩

II.           Dynamic

當static處理很困難時，就要改採dynamic來處理

以動態的將值分配給不同thread，例如有很多不用處理的值0的話，如果以static分配，則會使得某些thread很忙碌而其他的thread的工作一下就結束

4.      Communication

           -Thread間的溝通，可分為

I.             All-to-All (each processor sends its data to all others)

II.           Point-to-point-

III.         Broadcast (one to all)

IV.        Reduction (all to one)

V.          Scatter (one to several)

VI.        Gather (several to one)

其中Reduction是Gather的特例

5.      Locality

I.             Temporal Locality (in time domain): 指某個會常常使用的值

(e.g., loops, reuse)

II.           Spatial Locality (in space domain): 指某個區塊會被常常使用(e.g., straight-line code, array access)

如果能將同一區的資料給thread，則可以使得thread在工作的效果更好

I.             UMA

           全部的處理器皆使用同一塊記憶體

II.           NUMA

           每個處理器有自己的cache，自己的memory，自己沒有的資料採memory-passing       network傳輸