【文章內(nèi)容簡(jiǎn)介】 器上 ? 假設(shè)待排序數(shù)最初均勻地 、 不按任何特殊順序地分布在節(jié)點(diǎn)上； ? 一個(gè) 2d個(gè)節(jié)點(diǎn)的超立方體由兩個(gè) 2d1個(gè)節(jié)點(diǎn)的超立方體組成 ， 它們通過(guò)每個(gè)立方體中第 d維節(jié)點(diǎn)之間的鏈路互聯(lián)； ? 快速排序并行算法的步驟：首先將超立方體看成兩個(gè)子立方體 ， 位于高端子立方體中的處理器的地址首位為 1， 位于低端子立方體中的處理器的地址首位為 0。 成對(duì)的地址分別為 0xxx和 1xxx的處理器稱為 “ 伙伴 ” ， 其中 x是相同的 。 40 具體步驟 ? 一個(gè)處理器 （ 如 p0） 選擇 （ 或計(jì)算 ） 一個(gè)合適的軸元素 ， 并通過(guò)廣播把它送到立方體中所有其它處理器； ? 低端子立方體中的處理器將大于該軸元素的數(shù)傳送給他們位于高端子立方體中的伙伴處理器 。 高端子立方體中的處理器將小于該軸元素的數(shù)傳送給他們位于低端子立方體中的伙伴處理器 。 ? 每個(gè)處理器將收到的序列和本身的序列拼接 。 給定一個(gè) d維超立方體 ， 經(jīng)過(guò)這些步驟以后 ， 低端 d1維子立方體中的數(shù)都小于或等于軸元素 ， 而高端 d1維子立方體中的數(shù)都大于軸元素 。 ? 兩個(gè) d1維子立方體重復(fù)遞歸調(diào)用第 3步 ， 其中每個(gè)子立方體中的一個(gè)進(jìn)程為該子立方體選擇軸元素并通過(guò)廣播傳送到子立方體中的其他進(jìn)程 ， 遞歸調(diào)用 d次后終止 。 ? 為了完成排序 ， 每個(gè)處理器中的數(shù)需要串行進(jìn)行排序 。 最后按數(shù)字順序訪問(wèn)處理器即可從處理器中檢索數(shù) 。 41 42 2 矩陣運(yùn)算（轉(zhuǎn)置、乘法） ? 矩陣運(yùn)算是數(shù)值計(jì)算中最重要的一類運(yùn)算 ,特別是在線性代數(shù)和數(shù)值分析中 ,它是一種最基本的運(yùn)算 。 ? 矩陣的劃分：條帶狀劃分和棋盤劃分 為了對(duì)一個(gè)矩陣進(jìn)行并行操作 ， 必須將其進(jìn)行劃分并映射到不同的處理器上 ， 尤其是科學(xué)計(jì)算中矩陣的規(guī)模一般都很龐大的情況下更是如此 。 ? 條帶狀劃分 （ Striped Partitioning） 條帶狀劃分 就是把矩陣按照行或列分成幾部分 ， 分別映射到各個(gè)處理器 。 如果分到每個(gè)處理器的各行或列是連續(xù)的 ， 則稱為 塊帶狀劃分 （ BlockStriped） ； 相對(duì)的 ， 如果是按照行號(hào)或者列號(hào)取模而進(jìn)行的矩陣劃分則稱為循環(huán)帶狀劃分 （ CyclicStriped ） 。 43 4個(gè)處理器上 16 16矩陣的均勻條帶狀劃分和映射 (a) 列方向上的塊帶狀劃分； (b) 行方向的循環(huán)帶狀劃分 44 棋盤劃分（ Checkerboard Partitioning） 棋盤劃分把矩陣劃分為若干個(gè)子矩陣并映射到不同的處理器上 ， 每個(gè)處理器都不包含完整的行和列 。 和條帶狀劃分類似 ， 棋盤劃分也可以分為塊棋盤劃分和循環(huán)棋盤劃分 。 45 16個(gè)處理器上 8 8矩陣的均勻塊棋盤劃分和映射 46 矩陣的轉(zhuǎn)置 ? 轉(zhuǎn)置 （ Transposition） 是基本的矩陣運(yùn)算 。 一個(gè)矩陣 A的轉(zhuǎn)置記為 AT， 它是將矩陣 A的元素沿對(duì)角線互換而得到的 。 ? 矩陣轉(zhuǎn)置的串行算法很簡(jiǎn)單 ， 只需要把上三角 （ 不包括對(duì)角線 ） 的元素循環(huán)一遍 ， 每個(gè)元素與其對(duì)稱位置的元素交換位置即可 ， 整個(gè)過(guò)程只需要一個(gè)單位的多余空間 ， 時(shí)間復(fù)雜度為 O(n2) 。 47 單處理器上矩陣轉(zhuǎn)置算法 輸入：矩陣 An n 輸出：矩陣 An n的轉(zhuǎn)置 ATn n Begin for i=2 to n do for j=1 to i1 do 交換 a[i,j]和 a[j,i] endfor endfor End 48 棋盤劃分的矩陣轉(zhuǎn)置 ? 二維網(wǎng)格互聯(lián)結(jié)構(gòu)上的矩陣轉(zhuǎn)置 ? 設(shè)處理器數(shù)目 p≤n2， 則整個(gè) n n的矩陣分成 p個(gè)大小為 的子塊 ， 這些子塊自然影射到網(wǎng)格互聯(lián)結(jié)構(gòu)的 p個(gè)處理器上 。 ? 算法可以分兩步來(lái)完成：第一步 ， 將各個(gè)子塊看作一個(gè)整體進(jìn)行子塊轉(zhuǎn)置 ， 這一步由各處理器互相通信；第二步 ， 各處理器分別對(duì)自己的內(nèi)部子塊進(jìn)行局部轉(zhuǎn)置 。 )/()/( pnpn ?49 16個(gè)處理器上塊棋盤劃分的 8 8矩陣的轉(zhuǎn)置 子塊間轉(zhuǎn)置 子塊內(nèi)轉(zhuǎn)置 50 ? 為了避免對(duì)應(yīng)子塊交換數(shù)據(jù)時(shí)處理器發(fā)生死鎖 ， 可令下三角子塊先向與之對(duì)應(yīng)的上三角子塊發(fā)送數(shù)據(jù) ， 然后從上三角子塊接收數(shù)據(jù)；上三角子塊先將數(shù)據(jù)存放在緩沖區(qū)buffer中 ， 然后從與之對(duì)應(yīng)的下三角子塊接收數(shù)據(jù)；最后再將緩沖區(qū)中的數(shù)據(jù)發(fā)送給下三角子塊 。 51 ? 算法 塊棋盤劃分的矩陣轉(zhuǎn)置算法 ? 輸入：矩陣 An n 輸出：矩陣 An n的轉(zhuǎn)置 ATn n ? Begin ? 對(duì)所有處理器 my_rank(my_rank=0,… ,p1)同時(shí)執(zhí)行如下的算法 : ? (1) 計(jì)算子塊的行號(hào) v=my_rank/ sqrt(p), 計(jì)算子塊的列號(hào) ? u=my_rank mod sqrt(p) ? (2) if (uv) then /*對(duì)存放下三角塊的處理器 */ ? ()將所存的子塊發(fā)送到其對(duì)角塊所在的處理器中 ? ()接收其對(duì)角塊所在的處理器中發(fā)來(lái)的子塊 ? else /*對(duì)存放上三角塊的處理器 */ ? ()將所存的子塊在緩沖區(qū) buffer中做備份 ? ()接收其對(duì)角塊所在的處理器中發(fā)來(lái)的子塊 ? ()將 buffer中所存的子塊發(fā)送到其對(duì)角塊所在的處理器中 ? end if ? (3)for i=1 to m do /*處理器內(nèi)部局部轉(zhuǎn)置 */ ? for j=1 to i do ? 交換 a[i,j]和 a[j,i] ? end for ? end for ? End 52 53 矩陣向量乘法 ? 一個(gè)矩陣與向量相乘 ， 結(jié)果得到一個(gè)向量 。 矩陣向量相乘的串行算法具有 O(n2)的時(shí)間復(fù)雜度 。 ? 單處理器上矩陣 向量乘算法 ? 輸入： An n， Bn 1 輸出： Cn 1 ? Begin ? for i=0 to n1 do ? c[i]= 0 ? for j=0 to n1 do ? c[i]=c[i] + a[i,j]*b[j] ? end for ? end for ? End 54 矩陣 向量乘法的并行算法 ? 矩陣 向量乘法同樣可以有帶狀劃分 (Striped Partitioning)和棋盤劃分 (Checker Board Partitioning)兩種并行算法 。 以下僅討論行帶狀劃分矩陣 向量乘法 , 列帶狀劃分矩陣 向量乘法是類似的 。 ? 設(shè)處理器個(gè)數(shù)為 p， 對(duì)矩陣 A按行劃分為 p塊 ， 每塊含有連續(xù)的 m行向量 ， ， 這些行塊依次記為 A0, A1, … , Ap1， 分別存放在標(biāo)號(hào)為 0,1,… ,p1的處理器中 ， 同時(shí)將向量 B 廣播給所有處理器 。各處理器并行地對(duì)存于局部數(shù)組 a中的行塊 Ai和向量 B做乘積操作 。 ? ?pnm /?55 行帶狀劃分的矩陣 向量乘并行算法 ? 輸入： An n， Bn 1 ? 輸出： Cn 1 ? Begin ? 對(duì)所有處理器 my_rank(my_rank=0,… , p1)同時(shí)執(zhí)行如下的算法 : ? for i=0 to m1 do ? c(i)= ? for j=0 to n1 do ? c[i] = c[i]+a[i,j]*b[j] ? end for ? end for ? End ? 假設(shè)一次乘法和加法運(yùn)算時(shí)間為一個(gè)單位時(shí)間 ， 不難得出行帶狀劃分的矩陣向量乘 算法并行計(jì)算時(shí)間 Tp=n2/p， 若處理器個(gè)數(shù)和向量維數(shù)相當(dāng) ， 則其時(shí)間復(fù)雜度為 O(n)。 56 矩陣相乘及其串行算法 ? 由矩陣乘法定義容易給出其串行算法 ， 若一次乘法和加法運(yùn)算時(shí)間為一個(gè)單位時(shí)間 ， 則顯然其時(shí)間復(fù)雜度為 O(mnk) 。 ? 單處理器上矩陣相乘算法 ? 輸入： Am n， Bn k ? 輸出： Cm k ? Begin ? for i=0 to m