9.4 mimd共享儲存模型的並行演算法
（一） 非同步列舉排序演算法
列舉排序(enumeration sort)是一種最簡單的排序演算法，通常也稱為秩排序(rank sort)。對於基於列舉比較原理的非同步排序演算法，為了排序n個數的序列s= (x1,x2,…,xn) ，演算法要生成n個程序。程序i (1≤i≤n)將xi與s中其餘元素進行比較，並且使用區域性變數k及下所有小於xi的元素的數目。
當所有的比較都完成時，就將xi置入排序序列中的k+1的位置上，因此每個程序都可能彼此獨立地執行，而無通訊的要求。令x是存在共享儲存器中長度為n的陣列，開始時放入被排序的序列，當演算法結束時，結果置於共享儲存器中的t陣列內，變數i,j,k是演算法生成的每個程序的區域性變數[1007]。該並行演算法的描述如下：
在該並行演算法中有，由於每個處理器至多確定陣列x中的個元素的位置，而每確定乙個元素的位置需o(n)時間，因此對x進行排序需×o(n)時間。
例9_8設s=(8,6,6,9,7)，p(n)=2。建立程序的過程中，假定由p1生成5個程序，此後所有的程序均等待開始。假定使用「先進先出」的排程策略。
程序1和2分別由p1和p2執行，它們同時計算元素8和6的次第，然後將其分別置於t陣列的相應位置上，如圖9_19 (a)所示。欲知下一程序有哪乙個處理器啟動執行，需研究程序1和2的執行時間。假定比較操作和賦值操作大致用相同的時間，當執行x(i)>x(j), x(i)=x(j) 和i>j以及k=0 ,k=k+1和t(k+1)=x(i)時，程序1和2分別需要14和17各時間步，如圖9_19 (b)所示。
所以程序3應由p1啟動執行，之後3個時間步p2啟動執行程序4。這兩個程序負責將元素6和9分別置於陣列t的相應位置上，此時程序3需要18個時間步，程序4需要13個時間步，所以程序4比程序3早結束。下一程序5由p2啟動。
之後當程序3執行完後，因無等待的程序，所以p1變為空閒。當程序5執行15個時間步後，元素7便放到陣列t的相應位置上。演算法總共需要45個時間步。
圖9_19 非同步列舉排序陣列變化及程序排程
（二） 單源點最短路徑並行演算法
假設一有向圖各邊賦於非負整數，某條路徑的長度就是沿該路徑所有邊權之和。最短路徑問題，就是對每一點對i和j，丘照期間任何最短長度的路徑。單源點最短路徑，即在乙個圖中尋找從乙個指定頂點到所有其他定點的最短路徑。
(a) 單處理機上的moore演算法。
在moore演算法中，設源點為s∈v。從s到其他各頂點的最短路徑長度用一維陣列dist儲存。首先置dist(s)=0,dist(v)=∞，其中v≠s，且v∈v。
演算法使用了乙個佇列queue。開始執行時佇列中僅含有源點s；以後每次只要佇列非空，就將排頭頂點u從佇列中移去，令其作為本次搜尋的頂點，然後檢查u的所有射出邊(u,v)∈e：若dist(u)+w(u,v)(b) moore演算法的並行化
deo等人基於mimd緊耦合共享儲存模型實現了moore演算法的並行化。直觀上講，演算法9.4.
2_1有兩處可並行化的地方：一是search的第(3.2)步；二是主演算法的第(3)步。
前者，任何乙個頂點均可能有多條射出邊，它們都可並行地被檢查；後者，在任何時候都可能有多個頂點在佇列中，因此有可能每次檢查多個頂點的射出邊。由於後者可產生較大的加速，而且當g是個稀疏圖時，並行度受定點射出變得影響，所以選用後者。首先，佇列用源點初始化。
然後建立了許多非同步程序，每個程序都從佇列中刪除乙個頂點，檢查其射出邊，將已發現有更短路徑的頂點加入到佇列。演算法的第(1)步採用預排程方法很容易並行化。而第(3)步的while迴圈需作適當的修改，以能反映並執行search過程時一些非同步程序的存在。
顯然，當乙個程序發現隊列為空時，就停止執行是不合適的。因而必須採用兩個變數聯合使用的辦法，以決定什麼時候無工作可做：第乙個是陣列變數waiting，它記住哪乙個程序正處於等待狀態；第二個是布林變數halt，僅當隊列為空和所有程序處於等待狀態時為真。
initialize過程置陣列waiting中的第乙個元素為假。search過程也必須作適當的修改。因為佇列的插入、刪除操作不是原子操作，所以執行上述操作時必須給佇列上鎖：
其次，在乙個程序將剛找到的v路徑new_dist與當前的最短路徑dist(v)比較之前，變數dist(v)也必須上鎖，否則兩個程序有可能同時修改它；最後，若乙個程序發現隊列為空時，則置waiting中的相應元素為真。若程序1處於等待狀態，則它要檢查每個程序是否都處在等待狀態，如果是，則halt置為真，而程序1檢查每個程序是否處於等待狀態時，佇列也必須上鎖。
該並行演算法的描述如下：
（二） 最小生成樹並行演算法
乙個無向連通圖g的生成樹是指滿足如下條件的g的子圖t：
(1)g和t具有相同的頂點數；
(2)在t中有足夠的邊能連線g所有的頂點，但不出現迴路。最小生成樹，即最小代價生成樹(minimum cost spanning tree)，它是加權連通無向圖的所有生成樹中權值最小的生成樹。
(a) sollin順序求mst演算法
演算法開始時，圖的n個孤立頂點視為一片森林，而每個頂點均視為一棵樹；演算法共迭代log n次，每次迭代時，森林中的每棵樹，同時決定其最小的鄰邊，並將它們加入到森林中(即合併各棵樹)；此過程重複到森林中只剩下一棵樹。因為森林中樹的數目，每次都以2的倍數減少，所以迭代至多需要次就可找到mst；而每次迭代時，找頂點的最小鄰邊至多執行o(n2)次比較。因此sollin的順序演算法的複雜度為o(n2log n)。
函式find(v)找頂點v所在的樹的名字，union(v,u)合併包括頂點v和u的兩棵樹。
(b) quinn的並行化演算法
在共享儲存的mimd機系統上，sollin演算法可按如下思路並行化：首先，應設法對第(3)步while迴圈進行並行化，但遺憾的是因迴圈之間存在著先後制約關係，即在第k+1次迴圈之前，第k次迴圈的子樹必須同乙個有最小權值的邊關聯的另一棵子樹歸併，所以while語句的並行化是有限的。其次，考慮迴圈體內的並行化。
演算法的第(3.1)步通過適當的預排程可以使其並行化，設第t次迴圈時已有nt棵子樹：若nt>p，則把nt棵子樹較均勻的分配到p個處理器中，每個處理器約有棵子樹；否則，這nt棵子樹就分配給nt個處理器。
演算法的第(3.2)步並行化的最有效做法是：首先，每個處理器檢查它內部的頂點的邊，然後再檢查不在同一處理器上樹之間的邊。
演算法的第(3.3)步並行化稍微複雜些。圖9_20示出了此情況，假定乙個處理器企圖將樹b與其最近的樹a進行歸併，變數edge(a)有一條權值為k的邊(va,ua)，變數edge(b)也有一條權值為k的邊(vb,ub)。
然而假定兩處理器都在實行union之前執行了第(ii)步的測試，則(va,ua)和(vb,ub)都將加入到樹t中，結果形成乙個環，顯然這是錯的。因此，欲使第(3.3)步並行化，必須在執行第(3.
3.2)步之前上鎖，執行完第(3.3.
2.2)步後再開鎖。每次僅允許乙個處理器進入臨界區。
為了避免死鎖的產生，當有多個請求上鎖的程序申請臨界區時，僅僅讓標號最小的子樹上鎖。在mimd-sm模型上，所法所需的時間為，處理器數為o(p)[1007]。
圖9_20 並行化sollin演算法所引起的複雜情況
i. gauss-seidel演算法
gauss-seidel演算法是求解ax=b的一種演算法。先將係數矩陣a分解為a=e+d+f，其中d、e和f均為n×n的矩陣，它們的元素分別定義如下：
，， 這樣，ax=(d+e+f)x=b，從而dx=b-ex-fx。
94評估報告
附件2 7 工程工程質量評估報告 單位技術負責人 總監理工程師 建設監理公司 年月日前言 建設監理公司受公司的委託對工程實施監理工作，專案監理部於年月日開始對進行施工階段監理，經建設單位 設計單位 施工單位 監理單位的共同努力下，於年月日的建築工程達到基本竣工條件，下面對該工程進行工程質量評估。一 ...
94區首段總結
237省道寶應段三期建設工程 路基填築94區試驗段總結報告 一 工程概況 237省道寶應段三期建設工程，貫穿江蘇省揚州市寶應縣全境，跨越臨城已施工部分，分為南 北段。南段由臨城段南端起 k78 819.088 接老沿廣路 終點位於界首鎮與老s332平交 k98 931.3 接高郵段 線路大致呈南北走...
9 4感恩教育總結
感恩教育活動總結 感恩是中華民族的優良傳統。感恩是一種文明，感恩是一種品德，更是一種責任。感恩應是社會上每個人都應該有的基本道德準則，是做人的起碼的修養，也是人之常情。對於今天的廣大青少年來說，感恩意識絕不是簡單的回報父母養育之恩，回報老師的教育之恩。它更是一種責任意識 自立意識 自尊意識和健全人格...