并行性问题课件

並行性問題一、進程中的同構性

指並行程式中各分進程的類似性。有3種可能的基本類似：SPMD：在單程序多數據(SPMD)程式中的分進程是同構的。因為多個進程在不同的數據範疇內執行相同代碼。MPMD：在多程式多數據(MPMD)程式中的分進程是異構的。因為多個進程可以執行不同代碼。SPMD和MPMD程式，兩者都是MIMD類型的。SIMD：SIMD程式與SPMD有區別，SIMD程式是SPMD程式的一個特例。將著重MPMD程式的研究。數據並行程式--是指SPMD程式，尤其是此程式只用數據並行構造(如Fortran90中所採用的)時。功能並行程式(也稱為任務並行或控制並行程式)--通常是MPMD程式的同義詞。在一個並行程式中，MPMD(功能並行)和SPMD(數據並行)風格可以混合使用。1.並行塊(parallelblock)表達MPMD程式的方法是：使用parbegin和parend構造。這種結構化的構造最初是由DUkstra提議的，也稱為cobegin和coend。ParbeginS1，S2，…，Sn

Parend當並行塊執行時，它的n個分進程S1，S2，…，Sn就開始同時執行。它們的執行是互相獨立的，以不同速率進行。當所有n個分進程終止時，並行塊也就終止。2、並行迴圈(Parallelloop)當並行塊中的所有進程共用相同代碼時，用一個稱為並行迴圈的速記記號來標明並行塊如下：

ParbeginProcess(1)······Process(n)Parend可簡化成如下的並行迴圈：Parfor(i=1；i<=n：i++){Process(i)}並行迴圈常用來說明SPMD並行程式。可以用SPMD來仿真MPMD。例如MPMD代碼：ParbeginA；B；C；parend表示成一個SPMD的並行迴圈parfor(i=0；i<3；i++){if(i=0)A；If(i=1)B；If(i=2)C；}3.多代碼與單代碼(Multi-CodeversusSingleCode)

MPP和COW上，許多編程語言不提供並行塊或並行迴圈構造。例如，ParbeginA；B；C；parend，用多代碼進行說明：runAOnnode1runBOnnode2runCOnnode3程式A、B和C僅是順序程式加上進行交互的庫調用。SPMD程式可用單代碼方法加以說明。例如，要說明並行迴圈parfor(i=0：i<N；i++){foo(i)}，用戶只需編寫如下的一個程式：Pid=my_processid()；Numproc=number_of_processes();for(i：=pid；i<N；i=i+numproc)foo(i)；數據並行構造在Fortran90和HPF中，SPMD並行性可用數據並行構造加以說明。例如，一個並行迴圈：parlor(i:=1;i<=N;++){c[i]=A[i]+B[i];}用戶可用1條數組賦值語句：C=A+B或用以下迴圈來表示:

forall(i=1，N)C[i]=A[i]+B[i]

二、靜態和動態並行性1.靜態並行性如果一個程式的結構以及組成進程的個數在運行時間之前(如在編譯時間，連接時間或裝載時間)就可確定。2.動態並行性這就蘊含著那些進程要在運行時間內創建和終止。3.動態並行性通常使用某些操作：fork/join(派生和匯合）fork/join操作加以表示。它們也可用單代碼或多代碼方法加以說明。

一般構思。下列程式有3個進程，其中A是主進程，當程式開始執行時，它是自動被創建的：ProcessA:BeginZ:=1Fork(B);T:=foo(3)endProcessB:BeginFork(C);X:=foo(3);Join(C);Output(X+Y);endProcessC:BeginY:=boo(Z);end三、進程編組一個進程組是進程的一個有序集。進程中的成員數稱為組的大小。每個組有一個組識別字(ID)，它唯一地識別並行程式中的組。為支持組的概念，並行編程語言需要提供管理進程組的功能，如創建和毀滅組、詢問組的ID、組的成員以及組員的排序等。四、分配問題任何並行程式必須在某些數據對象上完成某些計算(工作負載)。分配是指將數據和工作負載劃分到進程中並將進程映射到結點(處理器)上。1.並行性平均並行性的量化指標:並行程式的並行度(degreeofparalle

lism，DOP)通常定義為可同時執行的分進程數。2.顆粒度

是指在兩次並行性操作或交互操作之間所執行的計算負載。粒度大小分為細(小)、中、粗(大)3種。按計算的運算元大小,可粗略地估計。3.隱式和顯式分配

顯式分配用戶需要顯式說明如何分配數據和工作負載。隱式分配此任務將由編譯器和運行