第一章第一章 并行計算機系統(tǒng)及其結(jié)構(gòu)模型并行計算機系統(tǒng)及其結(jié)構(gòu)模型 習題例題：習題例題： 1. 查閱資料， 找出一個并行計算的典型應用， 詳細描述該應用在并行化方面成功和失敗之 處以及遇到的困難： （從下列方面考慮：該應用是針對什么科學或者工程上的具體問題 設計的；對于要解決的問題，該應用實際效果怎樣，模擬結(jié)果和物理結(jié)果進行比較的結(jié) 果如何；該應用的運行在什么并行計算平臺上； （比如分布式或共享內(nèi)存，向量機）這 個應用使用那種開發(fā)工具開發(fā)的； 該應用的實際工作性能怎樣， 和運行平臺最佳性能相 比較；該應用的可擴展性如何？如果不好，你認為它的擴展性的瓶頸在何處？） 2. 一個 n N2= 個節(jié)點的洗牌交換網(wǎng)絡如圖所示。試問：此節(jié)點度=？網(wǎng)絡直徑=？和網(wǎng)絡 對剖寬度=？ 45672301 N=8 的洗牌交換網(wǎng)絡 3. 一個 k kN2) 1( += 個節(jié)點的蝶形網(wǎng)絡如圖所示。試問：此網(wǎng)節(jié)點度=？網(wǎng)絡直徑=？和 網(wǎng)絡對剖寬度=？ 行 0 行 1 行 2 行 3 k=3 的蝶型網(wǎng)絡 4. 參照圖，試解釋為什么：當 IO 處理器將一個新的數(shù)據(jù) X寫回主存而繞過采用 WT 策略的高速緩存時會造成高速緩存和主存間的不一致； 當直接從主存輸出數(shù)據(jù)而繞過 高速緩存采用 WB 策略時也會造成不一致。 5. 將一種互連網(wǎng)絡中的結(jié)點映射到另一種網(wǎng)絡的過程叫做嵌入（Embedding） 。研究嵌入 是很重要的， 因為設計在某一特定網(wǎng)絡連接的并行機上的算法， 如果實際運行在另一種 與之不同的互連網(wǎng)絡的并行機上時，我們要重新分析其通信（即選路）時間。試問： 如何將一個環(huán)形網(wǎng)絡嵌入到帶環(huán)繞的二維網(wǎng)孔中去？ 被嵌入到帶環(huán)繞的二維網(wǎng)孔上的原設計的算法其選路時間有何變化？ 第二章第二章 當代并行計算機系統(tǒng)介紹當代并行計算機系統(tǒng)介紹 習題例題：習題例題： 1. 請盡可能訪問以下有關高性能并行計算的網(wǎng)址： IEEE/CS ParaScope (/parascope/)，world-wide parallel computing sites High Performance Computing Lists (/homes/mcbryan/public_html/bb/2/summary.html) The Language List (http:/cuiwww.unige.ch/langlist) enumerate programming languages TOP 500 (/benchmark/top500.html) Worlds TOP 500 most powerful computing sites (at Netlib，University of Tennessee) Myrinet () DSM bibliography (http:/www.cs.ualberta.ca/rasit/dsmbiblio.html) Berkeley Active Message page (/AM/active_messages.html) The Cray Research system page ( SGI/Cray Origin 2000 ( Cray T3E ( PetaFLOPS web site (/hpcc/) NASA HPCC Program (/hpcc/) Cray T3E ( IBM SP ( Intel Paragon (/Services/ Consult/Paragon/paragon.html) Kai Li (/li/) SP2 at MHPCC (/doc/SP2.general/SP2.general.html) MPI Standard site (/mpi/index.html) MIT Parallel and Distributed Operating Systems Group (/). National Center for Supercomputer Applications at UIUC (NCSA) (/) Cornell Theory Center (CTC) (/ctc.html) Argonne Natl Laboratory，Mathematics C(I,J)=A(I,J)+D(I+1,J) S3 D(I,J)=0.1 Enddo Enddo DO I= 1,N S1: A(I)=B(I) S2: C(I)=A(I)+B(I) S3: D(l) = C(I+1) Enddo DO I=1,N DO J=2,N S1: A(I,J) = B(I,J) + C(I,J) S2: C(I, J)=D(I,J)/2 S3: E(I,J)=A(I,J-1) *2+E(I,J-1) Enddo Enddo 2、令 N= 5 10和 N= 8 10 ，試編寫計算的 SPMD 并行程序，并在您現(xiàn)有的共享存 儲的平臺上調(diào)試之;同時應執(zhí)行在 1，2，3,4,5，6,7 和 8 個處理器上。 3、試用 X3H5 模型，寫出計算的并行程序。 4、下面是使用 Pthreads 方法計算的一種并行代碼段: 5、下面是使用經(jīng)理員工模型（即主從模型）求解 N-皇后問題的并行代碼段： 試解釋上述代碼段的計算過程。 第十四章第十四章 分布存儲系統(tǒng)并行編程分布存儲系統(tǒng)并行編程 習題例題：習題例題： 1、試考慮下述代碼段中通信體的使用; process 0: MPI_Send(msg1,count1,MPI_INT,tag1,comm1); parallel_fft(.); process 1: MPI_Recv(msg1,count1,MPI_INT,tag1,comm1); parallel_fft(.); 試分析上述代碼段的計算功能。 如果在 parallel_fft(.)中又包含了另一個發(fā)送程序： If(my_rank = = 0) MPI_Send(msg2,count1,MPI_INT,1,tag2,comm2); 如果沒有通信體則會發(fā)生什么情況？ 2、填上空白處，使下面兩代碼段完全等效： float data1024; MPI_Datatype floattype; MPI_Type_vector(10,1,32,MPI_FLOAT, MPI_Type_commit( MPI_Send(data,1,floattype,dest,tag,MPI_COMM_WORLD); MPI_Type_free( float data1024,buff10; for( _ ; _ ; i+) buffi = data _ MPI_Send(buff,_ , MPI_FLOAT,_ ,_ ,_ ); 3、下面是 PVM 環(huán)境下的 hello 程序，它是一個 host/node 程序，試分析其工作過程。 /*PVM 主機主機/節(jié)點編程的節(jié)點編程的 hello 代碼段代碼段*/ /*host 程序 hello.c*/ #include #include “pvm3.h” main() int cc, tid; char buf100; printf(“im t%x n”, pvm_myid(); cc=pvm_spwan(“hello_other”, (char *)0, 0, “”, 1, if (cc = = 1) cc=pvm_recv(-1, -1); pvm_bufinfo(cc, (int *)0, (int *)0, pvm_upkstr(buf); printf(”from t%x: %s n”, tid, buf); else printf(“cant start hello_other n”); pvm_exit(); /*node 程序 hello_other.c*/ #include “pvm3.h” #include “string.h” main() int ptid; char buf100; ptid=pvm_parent(); strcpy(buf, “hello, world from”); gethostname(buf+strlen(buf), 64); pvm_initsend(PvmDataDefault); pvm_pkstr(buf); pvm_send(ptid, 1); pvm_exit(); exit(0); 4、計算可以通過 MPI 程序。為了加深讀者對 MPI 的學習和理解，下面給出用 FORTRAN 90 語言的實現(xiàn)版本。試分析其工作過程。 /*計算的 MPI（F90）編程代碼段*/ program main use mpi double precision PI25DT parameter (PI25DT=3.141592653589793238462643d0) double precision mypi, pi, h, sum, x, f, a integer n, myid, numprocs, i, rc ! function to integrate f(a) = 4.d0/(1.d0a*a) call MPI_INIT(ierr) call MPI_COMM_RANK(MPI_COMM_WORLD, myid, ierr) call MPI_COMM_SIZE(MPI_COMM_WORLD, numprocs, ierr) print *, process, myid, of, numprocs, is alive sizetype=1 sumtype=2 do if (myid.eq.0) then write(6, 98) 98 format(Enter the number of intervals: (0 quit) read(5, 99)n 99 format(i10) endif call MPI_BCAST(n, 1, MPI_INTEGER, 0, MPI_COMM_WORLD, ierr) ! check for quit signal if (n.le.0) exit ! calculate the interval size h=1.0d0/n sum=0.0d0 do i=myid+1, n, numprocs x=h*(dble(i)-0.5d0) sum=sum+f(x) enddo mypi=h*sum ! collect all the partial sums call MPI_REDUCE(mypi, pi, 1, MPI_DOUBLE_PRECISION, MPI_SUM, 0, 給出相應的相關方向向量和相關 距離向量: DO I=I,N DO J=2,N S1: A(I,J)=A(1,J-1)+B(I,J) S2: c(r,J)=A(I,J)+D(I+1,J) S3: D(I,J)=0.1 ENDDO ENDDO 2、判定下列的循環(huán)，哪些是可向量化的: DO I=1，N S1: A(I)=B(I) S2: C(I)=A(I) + B(I) S3: E(I) =C(I+1) ENDDO DO 1=1,N S1; AM -B(I)+C(I+1) S2: C(I)=A(I) * D (I) ENDDO DO I=1,N Sl: A(I)=A(1-1)+1 ENDDO Do I=1,N Sl: A(I)=A(I+1)+1 ENDDO DO I=2,N DO J =2,M A(I, J)=A(t,J-I)+1 ENDDO ENDDO 3、試向量化下列代碼段： DIMENSION A(200,200),B(200,200),C(200,200) DO I =1, 200 DO J =1, 200 A(I,J) = B(I,J) * C(I.J) ENDDO ENDDO DO i=1,100 C(I)=0.0 DO J=1,100 C(I)=C(I) +A(I,J) * B(J) ENDDO ENDDO DO 1=1,N B(1,1)=0 DO 1=1,M A(I) =A(I) + B(I, J) * C(I,J) ENDDO D(I)=E(I)+A(I) ENDDO DO I=2,N S1: T(I)=A(I-1)+A(I+1) S2: A(I)=B(I)+C(I) ENDDO 4、分析下列循環(huán)，那些是可并行化的： DO I=2,N A(I) =B(I)-A(I-1) ENDDO DO I=2,N,2 A(I) =B(I)-A(I-1) ENDDO DO I=I,N X= SQRT(A(I) ) B(I)=X*C(I)+X*D(I) ENDDO INDX=O DO I=A,N INDX= INDX+ 1 A(I) = B(I) + C(INDX) ENDDO DO I=I,N IF(A(I ) LT EPSILON) GOTO 320 A(I)=A(I) * B(I) ENDDO 320 CONTINUE 5、分析下列循環(huán)的語句數(shù)據(jù)相關性；如何進行循環(huán)調(diào)度并行化： DO I=I,N DO J=2,N S1: A(1,J)=B(1,J)+C(I,J) S2: C(I,J)=D(I,J)/2 S3: E(I,J)=A(I,J-1) * *2+E(I,J-1) ENDDO ENDDO - 1 - 一、一、 填空題填空題 1常用的并行算法設計的基本技術有_ _，_， _，_ _，_， _等。 2常見的并行計算模型有_ _，_， _，_ _等。 3PCAM 設計過程分為_，_，_ 和_四步。 4常見的并行程序設計模型包括_ _，_ _， _，_等。 二、二、 問答問答題題 1請簡述從上個世紀 80 年代至今，主流并行計算機體系結(jié)構(gòu)的變化趨勢。 2基于蝶式計算原理的 FFT 在二維 mesh 連接和蝶式網(wǎng)絡連接的處理器上均可并行實 現(xiàn)。 （1）請問哪種實現(xiàn)效率較好？并給出原因。 （2）蝶式網(wǎng)絡連接的處理器在實際的并行計算機系統(tǒng)并不常見，這是否會影響 FFT 在 蝶式網(wǎng)絡連接上的并行實現(xiàn)在實際中的使用？為什么？ 3基本的開關技術有哪兩種？各具有什么特點？ 三、三、 閱讀閱讀題題 1閱讀以下新聞報道，回答問題。 2004 年 6 月 29 日 國家科技部今日在人民大會堂宣布： “863 計劃重點項目曙光 4000A 通 過鑒定驗收，曙光 4000A 實現(xiàn)了對每秒 10 萬億次運算速度的技術和應用的雙跨越，成為國內(nèi)計算能 力最強的商品化超級計算機” 。在今年 6 月 22 日剛剛公布的全球高性能計算機 TOP500 排行榜中，曙 光 4000A 以每秒 11 萬億次的峰值速度和 80610 億次 Linpack 計算值位列全球第十，這是中國超級計 算機得到國際同行認可的最好成績。隨著曙光 4000A 的推出，中國已經(jīng)成為繼美、日之后第三個跨 越了 10 萬億次計算機研發(fā)、應用的國家。 曙光 4000A 擁有自主研制的機群系統(tǒng)軟件包括機群管理系統(tǒng)、機群部署系統(tǒng)、機群作業(yè)管理系 統(tǒng)、并行文件系統(tǒng)、機群監(jiān)控系統(tǒng)、機群并行通信系統(tǒng)、機群高可用系統(tǒng)、機群負載均衡系統(tǒng)等。 （1）請問文中提到的“TOP500 排行榜”是按照什么方法對高性能計算機進行排序的？ 這種方法具有什么樣的優(yōu)點和不足？ （2）結(jié)合高性能計算的應用，談談為什么中國需要研制高性能計算機。 （3）文中所說的機群系統(tǒng)指的是什么？它具有什么樣的特點？ 2以下是一段用 MPI 實現(xiàn)的并行程序代碼，用來并行求一組數(shù)的和。 #include #include - 2 - #include #define SIZE 10 void main(int argc, char *argv) int myid, numprocs; int dataSIZE, i, x, low, high, myresult, result; char fn255; char *fp; MPI_Init( MPI_Comm_size(MPI_COMM_WORLD, MPI_Comm_rank(MPI_COMM_WORLD, if (myid = 0) /* Open input file and initialize data */ strcpy(fn,getenv(HOME); strcat(fn,/data); if (fp = fopen(fn,r) = NULL) printf(Cant open the input file: %snn, fn); exit(1); for(i = 0; i SIZE; i+) fscanf(fp,%d, /* broadcast data */ MPI_Bcast(data, SIZE, MPI_INT, 0, MPI_COMM_WORLD); /* Add my portion Of data */ x = SIZE/numprocs; low = myid * x; high = low + x; if(myid = numprocs - 1) high = SIZE; myresult = 0; for(i = low; i high; i+) myresult += datai; /* Compute global sum */ MPI_Reduce( if (myid = 0) printf(The sum is %d.n, result); MPI_Finalize(); 請回答以下問題： (1) 請問上述并行程序的并行執(zhí)行的進程數(shù)是何時指定的，如何確定的？在程序中， 使用什么函數(shù)得到了進程數(shù)的信息。 - 3 - (2) 試分析上述并行程序?qū)牟⑿兴惴ǖ臅r間復雜度。 (3) 說明上述并行程序是如何對計算任務進行劃分的。 請問這種劃分方式是循環(huán)劃分 還是塊劃分？試寫出另一種劃分方式的代碼。 (4) 試對上述并行程序的加速比進行分析，并以此為例簡要說明 Amdahl 定律和 Gustafson 定律的不同。 (5) 結(jié)合上述并行程序的輸入輸出部分，說明 SPMD 程序的特點。 (6) 請問上述程序中使用了 MPI 哪些群集通信的函數(shù)？它們實現(xiàn)了什么功能? 四、四、 綜合題綜合題 1假定 44 A和 44 B已加載到如下所示的44處理器陣列上，試用圖表示 Cannon 矩陣乘 法或者 Fox 矩陣乘法的具體過程（任選一種即可） 。 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB 2以下是上三角方程組回代解法的串行算法的形式化描述。 Begin (1)for i=n downto 1 do (1.1)xi=bi/a (1.2)for j=1 to i-1 do ii bj=bj-ajix a i ji endfor =0 endfor End 請指出串行算法哪些部分可以并行化。寫出并行算法的形式化描述（需要注明 計算模型類型） ，分析你的算法的時間復雜度。 - 1 - 一、一、 名詞解釋名詞解釋 1 請給出下列縮寫的全稱，并加以解釋。 MPP、PCAM、APRAM 2請簡要解釋下列術語的含義。 共享變量模型、NUMA、加速比、logP 二、二、 問答問答題題 1現(xiàn)在市場上常見的雙 CPU 的計算機采用的是什么結(jié)構(gòu)？簡述該結(jié)構(gòu)的特性。 2何謂高速緩存一致性問題？請簡述一致性維護的基本策略。 3請簡述并舉例說明 Amdahl 定律。 4請問如何將一個 MPMD 程序改寫為 SPMD 程序？ 三、三、 綜合題綜合題 1閱讀以下題為“占據(jù)半壁江山 IBM 繼續(xù)統(tǒng)治超級計算機排行榜”大眾新聞報道，回 答問題。 根據(jù)超級計算機 500 強組織最近發(fā)布的調(diào)查報告， IBM 繼續(xù)在超級計算機領域處于絕對的統(tǒng) 治地位。此調(diào)查每半年進行一次，這是自 1993 年以來的第 26 次調(diào)查。 目前， 世界上500臺最強悍的超級計算機中有219臺屬于IBM， 其中前三名更是全部出自IBM 之手。位列第二的 HP 擁有 169 臺。位列榜首的依舊是大名鼎鼎的藍色基因Blue Gene/L，運 算速度為每秒 280.6 萬億次浮點運算。這一速度不久前剛剛刷新了世界記錄。這臺超級計算機是 為美國國家核安全局打造的，主要用于模擬核試驗。緊隨其后的也是藍色基因，不過是 IBM 自 己的 Watson Blue Gene(WBG)系統(tǒng)，運算速度為每秒 91.29 萬億次浮點運算。第三名是位于勞倫 斯-利沃莫爾國家實驗室的 ASC Purple， 運算速度為每秒 63.39 萬億次浮點運算。 IBM 這 219 臺超 級計算機的總運算速度為每秒 1.214 千萬億次浮點運算，占 500 強總運算能力的 53，遠遠甩開 了競爭對手。這是第一次一家公司的總速度突破千萬億次大關。 IBM 將自己成功的原因歸結(jié)于富有彈性的操作平臺和強大的 Power 處理器等因素， 其中藍色 基因使用的就是 Power 處理器。 （1）請問文中提到的“排行榜”是按照什么方法對高性能計算機進行排序的？這種方法 具有什么樣的優(yōu)點和不足？ （2）結(jié)合文中提到的高性能計算的應用，談談為什么中國需要自行研制高性能計算機， 并請舉出兩種國產(chǎn)系列高性能計算機品牌。 （3）結(jié)合課程所學知識，請對文中 “IBM 將自己成功的原因歸結(jié)于富有彈性的操作平 臺和強大的 Power 處理器等因素”進行分析評論。 2假定 44 A和 44 B已加載到如下所示的44處理器陣列上，試用圖表示 Cannon 矩陣乘 法的具體過程。 - 2 - 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3 AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB AAAABBBB 3MIMD 機器上 PSRS 排序算法描述如下： 輸入：長度為 n 的無序序列，p 臺處理器，每臺處理器有pn個元素 輸出：長度為 n 的有序序列 Begin （1） 均勻劃分：n 個元素均勻地劃分成 p 段，每臺處理器有 n/p 個元素。 （2） 局部排序：各個處理器利用串行排序算法，排序 n/p 個數(shù)。 （3） 選擇樣本：每臺處理器各從自己的有序段中選取 p 個樣本元素。 （4） 樣本排序：用一臺處理器將所有p2 （5） 選擇主元：用一臺處理器選取 p-1 個主元，并將其播送給其余處理器。 個樣本元素用串行排序算法排序之。 （6） 主元劃分：各處理器按主元將各自的有序段劃分成 p 段。 （7） 全局交換：各處理器將其轄段按段號交換到相應的處理器。 （8） 歸并排序：處理器使用歸并排序?qū)⑺邮盏闹T段施行排序。 End 試證明：當 3 np時，上述算法的時間復雜度為(log ) n On p 。 令 j i w表示 i P 中第 j 段中的元素數(shù)，試證明上述算法在執(zhí)行過程中，處理器中所積累 的元素數(shù)目不會超過2 /n p，即 1 2 p j i j n w p = 。 4PRAM 上對數(shù)劃分算法描述如下： 輸入： 兩非降有序序列),.,( 1n aaA =,),.,( 1n bbB =,假定mlog和mmmklog)(=均為整數(shù) 輸出：將 A 和 B 劃分成)(mk對段組),( ii BA，使得mBilog|=，nAi= |，且對于所 有1)(1mki， i A和 i B中的每一個 i 元素均大于 1i A和 1i B中的每一個元素 Begin （1） 0)0(=j；nmkj=)( - 3 - （2） for 1=i to 1)(mk par-do （2.1）求):( log Abrank mi （2.2）):()( log Abrankij mi = end for （3） for 0=i to 1)(mk par-do （3.1）),.,( log)1(1logmimii bbB + = （3.2）),.,( )1(1)(+ = ijiji aaA end for End 試分析上述算法的時間復雜度。 令(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34)A = (3,4,5,6,8,10,12,13,14,15,20,21,22,26,29,31)B =。 按上述算法，將其進行對數(shù)劃分，并最終將它們歸并。 第一章小結(jié) 本章從并行計算的角度出發(fā)， 著重討論當代科學和工程計算問題所要求的高性 能并行計算系統(tǒng)，包括并行計算機系統(tǒng)的互連技術、并行計算機的系統(tǒng)結(jié)構(gòu)模型、存儲訪問 模型和存儲結(jié)構(gòu)組織等。值得注意的是，所介紹的并行計算機系統(tǒng)，與計算機體系結(jié)構(gòu)或并 行處理技術等課程所講的出發(fā)點不一樣， 在此著重介紹一類并行計算機的體系結(jié)構(gòu)， 而不是 某一具體并行機的詳細介紹；著重介紹當代能滿足高速并行計算要求的主流并行計算機類 (SMP、MPP、COW 等等)，而對歷史上曾占主導地位的 SMD 和 PVP 則不作重點介紹；同 時所選講的內(nèi)容和敘述的深淺程度都是為了并行算法的設計和并行編程的需要， 而對有些相 關知識的介紹，也只能點到為止不能深入全面展開討論，尤望讀者能以此為線索，進一步 迫蹤和深入地學習。 第二章小結(jié) 本章討論了當代共享存儲多處理機、 分布存儲多計算機和機群三種并行計算機 系統(tǒng)。MPP 和 COW 之間的界線漸趨模糊，例如 IBM SP2 被視為 MPP，但它具有機群結(jié)構(gòu) (除了使用高性能開關網(wǎng)絡作為通信網(wǎng)絡外)。COW 的性能/價格比優(yōu)于 MPP，所以機群技術 是發(fā)展可擴放并行計算的主流趨勢。 第三章小結(jié) 并行計算的性能與所使用的并行計算機本身的性能有關， 所以研究并行計算的 性能先了解以下并行機的一些基本性能指標也是很必要的。 在并行系統(tǒng)上進行計算的主要目 的就是要加速整個計算的過程，所以研究并行計算（并行算法、并行程序）的加速比性能是 最根本的。 隨著計算負載的增加和機器規(guī)模的擴大， 研究并行計算的性能是否能隨處理器書 目的增加而按比例的增加（這就是所謂的可擴放性）也是很重要的。為了客觀、公正的評估 計算機性能，提高并行機的使用水平和效率，減少用戶引進和購買高性能計算機的盲目性， 所以了解掌握一些基本的基準測試程序也是很必需的。 本章對以上四方面的問題逐一做了簡 要討論。 第四章小結(jié) 并行計算模型是設計和分析并行算法的基礎。 PRAM模型由于過于抽象而不能 很好地反映并行算法的實際運行性能， 所以研究考慮通信、 同步等因素從而能較真實反映并 行算法運行性能的所謂更實際的計算模型更實際的計算模型(More Realistic Computation Models)成為當今并行 算法研究的主要動向之一。本節(jié)所討論的APRAM、BSP和LogP等模型就是屬于這種模型， 此外還有C3 模型。但過去幾年來，主要是從理論分析的角度，來研究它們之上的一些典型的 并行算法的設計與分析； 而近期的研究熱點卻從這些模型上的算法研究轉(zhuǎn)向這些模型的編程 的研究， 即從理論研究轉(zhuǎn)向?qū)嶋H應用。 因為任何并行算法的應用都最終落實到具體的編程上， 所以這種轉(zhuǎn)變是順應應用要求的。例如，一些研究考就為BSP模型構(gòu)造了一些函數(shù)庫，這些 BSP庫就是一些為程序員編寫B(tài)sP應用程序(這些應用程序按照BSP的超級計算步的風格進行 編寫)所提供的一組簡單有力的編程界面函數(shù)，此函數(shù)可改善程序的可移植性而不依賴于具 體的并行機結(jié)構(gòu)。 盡管PVM和MPI等也是目前可供使用的開發(fā)可移植并行代碼的方法， 但它 們的功能過于復雜而不易被掌捏，且它們均沒有為編程者提供能設計高效代碼的成本函數(shù)， 而像BSP模型卻提供了簡單和可定量分析程序運行時間的成本函數(shù)。 因此研究基于這些實用 計算模型的并行編程方法是非常有意義的。 第六章小結(jié) 本章所介紹的都是并行算法設計的最基本的技術， 遠非所有的設計技術。 這些 技術雖具有一定的普適性，但也并非對所有問題均行之有效，況且也不全面，同時也只能作 為設計并行算法的一般性指南，絕非是可直接引用的手冊。其它的設計技術還有破對稱破對稱 (Symmetry Breaking)技術，它是打破某些問題的對稱性的一種設計方法，在圖論問題和隨機 算法中經(jīng)常使用；加速級聯(lián)加速級聯(lián)(Accelerated Cascading)技術，它試圖將一個最優(yōu)但相對不快的算 法與另一個非?？斓亲顑?yōu)的算法“串接”起來，形成一個快速最優(yōu)的算法，此法雖不具有 普適性 但對有些問題卻效果甚佳； 隨機法是在算法設計時， 引入隨機性使得算法在執(zhí)行時， 可以隨機地選擇下一執(zhí)行步，從而可望得到平均性能較好的算法(即其復雜度比同一問題的 確定性算法的最壞情況的復雜度要好)，隨機算法設計簡單，但分析較復雜，經(jīng)常要分析算 法可在多少時間步內(nèi)以多大的概率結(jié)束， 用隨機法設計的算法， 其運行結(jié)果也可能是不正確 的，但這種錯誤的概率應是很小的；貪心法貪心法(Greedy Method)是一種最直接的設計技術，其設 計特點是 在算法的每一步都力圖確保獲得局部最優(yōu)， 這種設計方法的副作用是容易陷入局 部最優(yōu)。對于組合問題的算法設計技術，有動態(tài)規(guī)劃法動態(tài)規(guī)劃法(Dynamic Programming)，它是在每 一判定步， 列出多種可能的解， 然后按照某種條件， 舍棄那些肯定不能導致最優(yōu)解的局部解， 它和貪心法的區(qū)別在于， 貪心法僅產(chǎn)生一個判定序列， 而動態(tài)規(guī)劃法可能產(chǎn)生很多判定序列， 但依據(jù)“最優(yōu)性原理“，非局部最優(yōu)解的序列肯定不是最優(yōu)的，所以不予考慮：回溯法回溯法 (Backtracking)是一種窮舉法，在問題求解時常使用深度優(yōu)先搜索深度優(yōu)先搜索(Depth-First Searching)快， 在搜索過程中，一旦碰到某個無法搜索下去的分支，就向其父節(jié)點回溯，再搜索該父節(jié)點的 其它分支，如果所有的分支節(jié)點均無希望的解，則再向上追溯，如此等等，回溯法雖提供了 一種規(guī)律性求解的方法，但其時間復雜度較高；分支界限法分支界限法(Branch and Bound)與回溯法頗 類似但它是基于廣度優(yōu)先搜索廣度優(yōu)先搜索(Breadth-First Searching)法，它利用部分解的最優(yōu)性信息， 避免考慮那些不能導致最優(yōu)的解，以加快問題的求解，其解題過程是：對解集合反復進行分 支，即反復構(gòu)造其子集合，每次分支時都對所得到的子集合計算最優(yōu)解的界，若它不能優(yōu)于 當前已知的最優(yōu)解，則對此子集合就不再進行分支，否則繼續(xù)分支，以探索更好的解，直到 所得的子集合僅有一個解為止。 第七章小結(jié) 本章已經(jīng)描述了并行算法設計的四個步驟： 首先將給定問題劃分成一些小的任 務，劃分方法可以使用域分解法或功能分解法；其次分析諸任務之間的通信需求，通信可以 是局部的和全局的，靜態(tài)的和動態(tài)的，結(jié)構(gòu)化的和非結(jié)構(gòu)化的以及同步的和異步的；然后使 用組合方法在盡可能保持靈活性的同時，減少通信和開發(fā)成本；最終以最小化總執(zhí)行時間 為目標將諸任務分配給處理器， 使用負載平衡和任務調(diào)度技術可以改善映射的質(zhì)量， 在每個 設計步驟之后均列出了相應的設計檢驗推則以評價設計的好壞。 經(jīng)過上述四個步驟設計出的并行算法， 在開始編碼實現(xiàn)之前尚須考慮以下幾件事： 對算 法進行性能分析以選得好的算法， 根據(jù)要求證實所作的設計是否滿意， 考慮算法具體實現(xiàn)時 的代價和代碼重用的可能性；最終考慮如何將算法裝配到一個更大的系統(tǒng)中去。 第十章小結(jié) 線性代數(shù)方程組的求解在科學和工程計算中應用非常廣泛， 這是因為很多科學 與工程問題的計算， 最終大都可以化為線性代數(shù)方程組的求解。 本章主要討論最基本的線性 方程組的求解，包括三角形方程組、三對角方程組、稠密和稀疏線性方程組等的經(jīng)典解法。 線性代數(shù)方程組的數(shù)值解法通常有兩種：直接法和迭代法。直接法，又稱消元法，是利 用矩陣變換技巧，將一般的系數(shù)矩陣化為特殊形式(如上三角和對角形式)的矩陣以對方程組 消解。其優(yōu)點是可以預先估計運算量，并可得到問題的推確解，但由于實際計算過程中總存 在著舍入誤差， 因此直接法得到的結(jié)果并非絕對精確， 并且還存在著計算過程的穩(wěn)定性問題。 迭代法是一種逐步求精的近似求解過程，此法一般總是假定方程組中的系數(shù)aii 應改善前一次的計算結(jié)果。 迭代過程由預先給定的精度要求來控制， 但由于方程組的準確解 一般是不知道的， 因此判斷某次迭代是否滿足精度要求是困難的， 通常我們總是認為當相鄰 兩次迭代值x 0 (i = 1,n)。其優(yōu)點是簡單，易于計算機編程，但它存在著迭代是否收斂和收斂快慢的問題。 迭代求解的過程是，先給定初始解，然后逐次迭代下去，且理論上講，每次迭代的結(jié)果都 i(k)與xi(k-1)也很接近時，xi與xi(k)也很接近，因此就可直接用條件 1 ( )(1) max i n x kx k ii =0)，求 n 個數(shù)和的并行算法 算法運行時間：t(n)=O(logn) 總運算量: W(n)=W(1)(n)+W(2)(n)+W(3)(n)=n+n/2 h 由 Brent 定理知: t(n)=O(n/p+logn) +1=O(n) 例例 3 3 設設 A A 為為矩矩陣陣，有有如如下下串串行行程程序序段段： f fo or r i i= =1 1 t to o n n d do o f fo or r j j= =1 1 t to o n n d do o a a 3 3i i, ,2 2j j = = a a 3 3i i- -2 2, ,2 2j j- -1 1 e en nd df fo or r e en nd df fo or r 其其相相關關方方向向向向量量為為，可可知知行行和和列列間間同同時時存存在在數(shù)數(shù)據(jù)據(jù)相相關關。在在此此我我們們可可以以試試用用行行劃劃分分、列列劃劃分分和和 方方塊塊劃劃分分. .在在行行劃劃分分的的情情況況下下令令 m m= =n/p , ,例例 1 1 的的串串行行程程序序段段可可以以轉(zhuǎn)轉(zhuǎn)化化為為如如下下的的并并行行程程序序 段段： f fo or r k k= =1 1 t to o P P P Pa ar r- -d do o f fo or r i i1 1= =1 1 t to o m m d do o f fo or r j j= =1 1 t to o n n d do o a a 3 3( (k k- -1 1) )m m+ +3 3i i1 1, ,2 2j j = =a a 3 3( (k k- -1 1) )m m+ +3 3i i1 1- -2 2 , ,2 2j j- -1 1 e en nd df fo or r e en nd df fo or r e en nd df fo or r 例例 4 設設 A A 為為一一個個 n n 階階方方陣陣，有有如如下下串串行行程程序序段段： f fo or r i i= =1 1 t to o n n d do o f fo or r j j= =1 1 t to o n n d do o a a i i, ,j j = = a a i i- -1 1, ,j j e en nd df fo or r e en nd df fo or r 分分析析矩矩陣陣 A A 的的元元素素下下標標 i i 和和 j j，則則 i i 和和 j j 的的相相關關方方向向向向量量為為，各各列列之之間間數(shù)數(shù)據(jù)據(jù)無無任任何何相相關關 關關系系。因因此此對對矩矩陣陣 A A 可可按按列列劃劃分分。 串串行行程程序序段段可可轉(zhuǎn)轉(zhuǎn)化化為為如如下下并并行行程程序序段段： f fo or r k k= =1 1 t to o P P P Pa ar r- -d do o f fo or r j j1 1= =1 1 t to o m m d do o f fo or r i i= =1 1 t to o n n d do o a a i i, ,( (k k- -1 1) )m m+ +j j1 1 = =a a i i- -1 1, ,( (k k- -1 1) )m m+ +j j1 1 e en nd df fo or r e en nd df fo or r e en nd df fo or r 例 5 注：本例無鏈路競爭和死鎖現(xiàn)象 例 6 E 立方選路 0110(S) 1101(D) 1011(R) 例 7 DNS 乘法示例 C00=1(-5)+27=9 C01=1(-6)+28=10 C10=3(-5)+47=13 C11=3(-6)+48=14 例 8 上三角方程組的回代解法并行化 (1)SISD 上的回代算法 Begin (1)for i=n downto 1 do (1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor endfor End (2)SIMD-CREW 上的并行回代算法 - 劃分: p 個處理器行循環(huán)帶狀劃分 - 算法 Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1jp do for k=j to i-1 step p do bk=bk-akixi aki=0 endfor endfor endfor End / p(n)=n, t(n)=n 例 9 n=8 的 BF 網(wǎng)絡表示 Pr,i與上層 Pr-1,i, Pr-1,j相連, 這里 j 與 i 僅在第 r 位不同 例 10 一一個個在在 M MP PI I 中中創(chuàng) 創(chuàng)建建新新通通信信域 域的的例例子子 M MP PI I_ _C Co om mm m M My yW Wo or rl ld d, , S Sp pl li it tW Wo or rl ld d; ; i in nt t m my y_ _r ra an nk k, ,g gr ro ou up p_ _s si iz ze e, , C Co ol lo or r, , K Ke ey y; ;