1、第 七 講第七章啥叫粒度（非并行計算版）打個比方，100個學生要進行管理。細粒度：4個學生一個班25個班；粗粒度：50個學生一個班2個班。大學寢室八個人中午吃飯細粒度：每個人都要出寢室，去食堂打份飯回來。 粗粒度：派個代表，或者找個別的寢室的，把所有飯帶回來。程序也是一樣，事情定下來的功能就那么多細粒度：定義了100個類；粗粒度：定義了2個類。啥叫粒度（并行計算版）粒度（granularity）各個多處理機可獨立并行執行的任務大小的度量。粗粒度所含計算任務有較大計算量和較復雜計算程序。任務級并行的粒度大于語句級的并行。細粒度所含計算任務有較小的計算量和較短的計算程序。向量機主要是對內層Do循環

2、語句作向量化，所以向量化是一種小粒度（細粒度）并行。指令級并行等則是小粒度并行，亦稱為細粒度。中粒度所含計算任務的大小和計算程序的長短在粗粒度和細粒度兩種類型的算法之間粒度細粒度的并行1）通信處理時只能完成很少量的可計算工作。2）低的計算通信率3）促進負載平衡意味著高通信開銷，降低了性能提升的可能性。如果粒度太小很可能任務間的通信和同步所須要的花費時間比用在計算上的還長。粗粒度并行1）在每次通信同步之間完成相當多的計算任務。2）高計算通信率意味著更加可能執行性能提升。更難執行有效的負載平衡調度哪個更好？最高效的粒度是由算法和當前硬件平臺決定的。通常情況下，通信和同步的開銷很大程度上取決于執行速

3、度，這樣運用粗粒度較好。 細粒度并行機制可以減少負載不平衡所帶來的開銷。粒度（2）并行編程涉及不同的層次：指令層：非常細的粒度；數據層：細粒度；控制層：中粒度；任務層：大粒度。前兩層大都由硬件和編譯器負責處理，程序員通常處理后兩層的并行。第七章 并行算法的一般設計過程 7.1 PCAM設計方法學 7.2 劃分 7.3 通信 7.4 組合 7.5 映射 7.6 小結設計目標從給定問題的描述出發，通過一系列步驟，最終設計出一個能展示并發性可擴放性局部性和模塊性的并行算法設計原則PCAM設計方法學首先盡量開拓算法的并發性和滿足算法的可擴放性(與算法相關的特性)；然后著重優化算法的通信成本和全局執行時

4、間(與機器相關的特性)；同時通過必要的整個過程的反復回溯，以期望達到一個滿意的設計選擇； PCAM設計方法學設計并行算法(PCAM)的四個階段劃分(Partitioning)通信(Communication)組合(Agglomeration)映射(Mapping)設計的前期(第1,2步)：考慮與機器特性無關的特性：并行性和可擴放性，尋求具有這些特性的算法；設計的后期(第3,4步) ：考慮與機器特性相關的特性：局部性等與性能有關的問題； PCAM設計過程劃分通信組合映射劃分：分解成小的任務，開拓并發性；通信：確定諸任務間的數據交換，監測劃分的合理性；組合：依據任務的局部性，組合成更大的任務；映射

5、：將每個任務分配到處理器上，提高算法的性能。第七章 并行算法的一般設計過程 7.1 PCAM設計方法學 7.2 劃分 7.3 通信 7.4 組合 7.5 映射 7.6 小結 劃分方法描述充分開拓算法的并發性和可擴放性；先進行數據分解(稱域分解)，再進行計算功能的分解(稱功能分解)；先集中數據的分解（域分解），然后是計算功能的分解（功能分解），兩者互為補充使數據集和計算集互補相交，以避免數據和計算的復制；劃分方法描述劃分階段忽略處理器數目和目標機器的體系結構；能分為兩類劃分：域分解(domain decomposition)功能分解(functional decomposition)域分解 劃分

6、的對象是數據，可以是算法的輸入數據、中間處理數據和輸出數據；將數據分解成大致相等的小數據片；劃分時考慮數據上的相應操作；如果一個任務需要別的任務中的數據，則會產生任務間的通信；域分解 示例：三維網格的域分解，各格點上計算都是重復的。下圖是三種分解方法：域分解 不規則區域的分解示例：功能分解 劃分的對象是計算，將計算劃分為不同的任務，其出發點不同于域分解；劃分后，研究不同任務所需的數據。如果這些數據不相交的，則劃分是成功的；如果數據有相當的重疊， 意味著要重新進行域分解和功能分解；功能分解是一種更深層次的分解。示例1：搜索樹示例2：氣候模型功能分解 劃分判據 劃分是否具有靈活性？劃分是否避免了冗

7、余計算和存儲？劃分任務尺寸是否大致相當？任務數與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？劃分的標準劃分的任務數，是否至少高于目標機上處理器數的一個量級。（靈活性）若否，則后繼的設計步驟缺少靈活性是否避免冗于的計算和存儲要求。（可擴放性）若否，則產生的算法對大型問題可能是不可擴放的劃分的任務尺寸是否大致相當。（均衡）若否，分配處理器時很難做到工作量均衡任務數是否與問題尺寸成比例。理想情況下，問題尺寸的增加應引起任務數的增加而不是任務尺寸的增加是否采用了幾種不同的劃分法，多考慮幾種選擇可提高靈活性，同時既考慮域分解，又要考慮功能分解。第七章 并行算法的一般設計過程 7.1 PC

8、AM設計方法學 7.2 劃分 7.3 通信 7.4 組合 7.5 映射 7.6 小結 通信方法描述通信是PCAM設計過程的重要階段；劃分產生的諸任務，一般不能完全獨立執行，需要在任務間進行數據交流；從而產生了通信；功能分解確定了諸任務之間的數據流；諸任務是并發執行的，通信則限制了這種并發性； 四種通信模式局部/全局通信結構化/非結構化通信靜態/動態通信同步/異步通信局部通信通信限制在一個鄰域內，只與較少的幾個近鄰的通信全局通信通信非局部的，與很多任務通信例如：All to AllMaster-Worker53721結構化通信每個任務的通信模式是相同的；下面是否存在一個相同通信模式？非結構化通信

9、沒有一個統一的通信模式例如：無結構化網格靜態通信vs.動態通信靜態通信伙伴的身份不隨時間改變動態通信伙伴的身份可能由運行時所計算的數據決定且是可變的同步通信vs.異步通信同步雙方知道何時進行通信，發送方顯示的發給接收方異步不確定，接收的方明確地從發送者請求數據通信判據 所有任務是否執行大致相當的通信?是否盡可能的局部通信？通信操作是否能并行執行?同步任務的計算能否并行執行？通信標準所有任務是否執行大致同樣多的通信。(可擴放性)若否，則可擴放性可能不好每個任務是否只與少許近鄰通信若否，則可能導致全局通信；應設法將全局通信結構化為局部通信結構諸通信操作是否能并行執行若否，則可能是低效的和不可擴放的

10、不同任務的計算能否并行執行若否，則可能是低效的和不可擴放的可重新安排通信/計算次序第七章 并行算法的一般設計過程 7.1 PCAM設計方法學 7.2 劃分 7.3 通信 7.4 組合 7.5 映射 7.6 小結方法描述 組合是由抽象到具體的過程，是將組合的任務能在一類并行機上有效的執行；合并小尺寸任務，減少任務數。如果任務數恰好等于處理器數，則也完成了映射過程；通過增加任務的粒度和重復計算，可以減少通信成本；保持映射和擴展的靈活性，降低軟件工程成本；方法描述 （2）增加粒度：在劃分階段，致力于盡可能多的任務以增大并行執行的機會。但定義大量的細粒度任務不一定產生一個有效的算法，因為這有可能增加通

11、信的代價和任務創建的代價表面-容積效應：通信量比例于子域的表面積，而計算比例于容積；通信/計算之比隨任務的尺寸的增加而減少增加粒度重復計算(Replication Computation),也叫冗余計算，有時可用冗余計算來減少通信。同時也要保持靈活性和減少軟件成本、降低軟件工程代價表面-容積效應通信量與任務子集的表面成正比，計算量與任務子集的體積成正比；增加重復計算有可能減少通訊量；重復計算重復計算減少通訊量，但增加了計算量，應保持恰當的平衡；重復計算的目標應減少算法的總運算時間；示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 二叉樹上求和，共需2logN步重復計算重復計算

12、示例：二叉樹上N個處理器求N個數的全和，要求每個處理器均保持全和。 蝶式結構求和，使用了重復計算，共需logN步組合判據 增加粒度是否減少了通信成本？重復計算是否已權衡了其得益？是否保持了靈活性和可擴放性？組合的任務數是否與問題尺寸成比例?是否保持了類似的計算和通信？有沒有減少并行執行的機會？組合的標準組合造成的重復計算，是否平衡了其收益？造成重復數據，是否已證實不會因限制問題尺寸和處理機數目而影響可擴放性？組合產生的任務是否具有類似的計算、通信代價？任務數目是否仍與問題尺寸成比例？第七章 并行算法的一般設計過程 7.1 PCAM設計方法學 7.2 劃分 7.3 通信 7.4 組合 7.5 映射 7.6 小結方法描述 每個任務要映射到具體的處理器，定位到運行機器上；任務數大于處理器數時，存在負載平衡和任務調度問題；映射的目標：減少算法的執行時間并發的任務 不同的處理器任務之間存在高通訊的 同一處理器映射實際是一種權衡，屬于NP完全問題；負載平衡算法 靜態的：事先確定；概率的：隨機確定；動態的：執行期間動態負載；