并行算法實(shí)踐

上篇并行程序設(shè)計(jì)導(dǎo)論
單元I并行程序設(shè)計(jì)基礎(chǔ).
第一章并行計(jì)算機(jī)系統(tǒng)與結(jié)構(gòu)模型(5)
1.1典型并行計(jì)算機(jī)系統(tǒng)簡(jiǎn)介(5)
1.1.1陣列處理機(jī)(5)
1.1.2向量處理機(jī)(7)
1.1.3共享存儲(chǔ)多處理機(jī)(9)
1.1.4分布存儲(chǔ)多計(jì)算機(jī)(10)
1.1.5分布共享存儲(chǔ)多處理機(jī)(12)
1.2當(dāng)代并行計(jì)算機(jī)體系結(jié)構(gòu)(14)
1.2.1并行計(jì)算機(jī)體系結(jié)構(gòu)模型(14)
1.2.2并行計(jì)算機(jī)存儲(chǔ)結(jié)構(gòu)模型(17)
1.2.3分布式高速緩存與主存體系結(jié)構(gòu)(19)
1.3小結(jié)(22)
參考文獻(xiàn)(23)
第二章PC機(jī)群的搭建(24)
2.1機(jī)群系統(tǒng)概述(24)
2.1.1機(jī)群系統(tǒng)原理與技術(shù)(24)
2.1.2典型機(jī)群系統(tǒng)簡(jiǎn)介(26)
2.2硬件的選擇與安裝(27)
2.2.1節(jié)點(diǎn)構(gòu)建(28)
2.2.2系統(tǒng)構(gòu)建(31)
2.2.3機(jī)群系統(tǒng)示例(33)
2.3軟件的選擇與安裝(33)
2.3.1OS的選擇(33)
2.3.2SSI的構(gòu)建(35)
2.3.3編程環(huán)境的選擇(38)
2.3.4作業(yè)管理系統(tǒng)的選擇(42)
2.4機(jī)群系統(tǒng)性能評(píng)測(cè)(49)
2.4.1基準(zhǔn)測(cè)試程序(49)
2.4.2性能分析工具(53)
2.5小結(jié)(56)
參考文獻(xiàn)(56)
第三章并行程序設(shè)計(jì)簡(jiǎn)介(58)
3.1并行程序開(kāi)發(fā)方法(58)
3.1.1并行層次與代碼粒度(58)
3.1.2并行程序開(kāi)發(fā)策略(59)
3.1.3并行編程模式(61)
3.1.4并行應(yīng)用編程過(guò)程(63)
3.2并行程序設(shè)計(jì)模型(68)
3.2.1計(jì)算π樣本程序(68)
3.2.2數(shù)據(jù)并行模型(69)
3.2.3消息傳遞模型(71)
3.2.4共享變量模型(72)
3.3并行編程語(yǔ)言和環(huán)境概述(73)
3.3.1早期并行編程語(yǔ)言(74)
3.3.2近代并行編程語(yǔ)言與環(huán)境(75)
3.3.3并行說(shuō)明性語(yǔ)言環(huán)境(78)
3.4循環(huán)程序并行化的一般方法(78)
3.4.1數(shù)據(jù)相關(guān)分析(78)
3.4.2數(shù)據(jù)劃分與處理器指派(80)
3.4.3循環(huán)重構(gòu)(87)
3.5小結(jié)(96)
參考文獻(xiàn)(96)
單元I習(xí)題(98)
單元II并行程序編程指南
第四章MPI編程指南(105)
4.1引言(105)
4.1.1MPI的產(chǎn)生(105)
4.1.2MPI的語(yǔ)言綁定(106)
4.1.3MPI的實(shí)現(xiàn)(107)
4.26個(gè)基本函數(shù)組成的MPI子集(107)
4.3MPI消息(109)
4.3.1消息數(shù)據(jù)類(lèi)型(110)
4.3.2消息標(biāo)簽(113)
4.3.3通信域(115)
4.3.4消息狀態(tài)(117)
4.4點(diǎn)對(duì)點(diǎn)通信(117)
4.4.1MPI通信模式(118)
4.4.2阻塞和非阻塞通信(119)
4.4.3通信和計(jì)算的重疊(119)
4.5群集通信(121)
4.5.1群集通信的通信功能(122)
4.5.2群集通信的同步功能(125)
4.5.3群集通信的聚合功能(125)
4.5.4群集通信例程的共同特點(diǎn)(126)
4.5.5計(jì)算π的MPI程序(127)
4.6MPI擴(kuò)展(127)
4.6.1動(dòng)態(tài)進(jìn)程(128)
4.6.2遠(yuǎn)程存儲(chǔ)訪(fǎng)問(wèn)(129)
4.6.3并行I/O(131)
4.7小結(jié)(132)
參考文獻(xiàn)(132)
第五章PVM編程指南(133)
5.1引言(133)
5.1.1開(kāi)發(fā)歷史(133)
5.1.2PVM的特點(diǎn)(134)
5.1.3與MPI的比較(134)
5.2PVM的啟動(dòng)和命令(135)
5.3一個(gè)簡(jiǎn)單的PVM程序(136)
5.3.1程序介紹(136)
5.3.2編譯和運(yùn)行(138)
5.4PVM任務(wù)(139)
5.4.1任務(wù)派生(139)
5.4.2任務(wù)組(140)
5.4.3任務(wù)標(biāo)識(shí)符(141)
5.4.4任務(wù)管理(141)
5.5PVM通信(142)
5.5.1點(diǎn)對(duì)點(diǎn)通信(142)
5.5.2群集通信(142)
5.5.3消息的打包/解包(143)
5.5.4通信函數(shù)(144)
5.5.5計(jì)算π的PVM程序(145)
5.6PVM虛擬機(jī)結(jié)構(gòu)(146)
5.6.1結(jié)構(gòu)分析(147)
5.6.2動(dòng)態(tài)配置(147)
5.6.3PVM虛擬機(jī)的構(gòu)建過(guò)程(148)
5.7小結(jié)(149)
參考文獻(xiàn)(149)
第六章HPF編程指南(150)
6.1HPF概述(151)
6.1.1引言(151)
6.1.2HPF的語(yǔ)言特點(diǎn)(152)
6.1.3HPF的語(yǔ)言模型(153)
6.2HPF編程簡(jiǎn)介(154)
6.2.1一個(gè)簡(jiǎn)單的HPF程序?qū)嵗?154)
6.2.2HPF的基本特性(155)
6.3數(shù)據(jù)映射(159)
6.3.1數(shù)據(jù)映射說(shuō)明語(yǔ)句(159)
6.3.2一個(gè)數(shù)據(jù)映射的HPF程序段分析(164)
6.4數(shù)據(jù)并行結(jié)構(gòu)(165)
6.4.1數(shù)組運(yùn)算(165)
6.4.2FORALL語(yǔ)句和FORALL結(jié)構(gòu)(167)
6.4.3INDEPENDENT指示(169)
6.5HPF語(yǔ)言的過(guò)程(171)
6.5.1HPF語(yǔ)言的一般函數(shù)和子程序(171)
6.5.2HPF語(yǔ)言?xún)?nèi)部函數(shù)(172)
6.5.3HPF語(yǔ)言的庫(kù)函數(shù)(174)
6.6HPF實(shí)例分析：2DFFT(176)
6.7HPF語(yǔ)言其他特性(178)
6.7.1HPF對(duì)FORTRAN90語(yǔ)言的限制(178)
6.7.2HPF1.1子集(179)
6.7.3HPF2.0與HPF1.1的不同點(diǎn)(180)
6.8小結(jié)(180)
參考文獻(xiàn)(181)
附錄一HPF指令語(yǔ)法(182)
附錄二一般的內(nèi)部函數(shù)及庫(kù)函數(shù)(184)
附錄三HPF網(wǎng)絡(luò)資源(187)
第七章OpenMP編程指南(189)
7.1OpenMP概述(189)
7.1.1什么是OpenMP(190)
7.1.2OpenMP的歷史(191)
7.1.3OpenMP的目標(biāo)(191)
7.2OpenMP編程風(fēng)格(191)
7.2.1OpenMP并行編程模型(191)
7.2.2OpenMP程序結(jié)構(gòu)(192)
7.3OpenMP編程簡(jiǎn)介(193)
7.3.1一個(gè)簡(jiǎn)單的OpenMP程序?qū)嵗?194)
7.3.2編譯制導(dǎo)(195)
7.3.3并行域結(jié)構(gòu)(196)
7.3.4共享任務(wù)結(jié)構(gòu)(197)
7.3.5組合的并行共享任務(wù)結(jié)構(gòu)(201)
7.3.6同步結(jié)構(gòu)(202)
7.3.7threadprIvate編譯制導(dǎo)語(yǔ)句(205)
7.3.8數(shù)據(jù)域?qū)傩宰泳?206)
7.3.9子句/編譯制導(dǎo)語(yǔ)句總結(jié)(208)
7.3.10語(yǔ)句的綁定和嵌套規(guī)則(209)
7.4運(yùn)行庫(kù)例程與環(huán)境變量(210)
7.5OpenMP計(jì)算實(shí)例(210)
7.6小結(jié)(213)
參考文獻(xiàn)(214)
附錄運(yùn)行庫(kù)例程(215)
單元II習(xí)題(217)
單元III并行程序開(kāi)發(fā)方法
第八章可視化并行程序設(shè)計(jì)環(huán)境(223)
8.1引言(223)
8.1.1并行軟件工程(223)
8.1.2并行程序開(kāi)發(fā)環(huán)境的要求(224)
8.1.3工具集成(225)
8.2SEPP/HPCTI簡(jiǎn)介(225)
8.2.1SEPP/HPCTI方法(225)
8.2.2SEPP/HPCTI組成(226)
8.3可視化并行語(yǔ)言的分類(lèi)(228)
8.3.1通用編程模型(229)
8.3.2進(jìn)程模型(232)
8.3.3進(jìn)程交互(233)
8.3.4正則并行結(jié)構(gòu)(234)
8.3.5分層設(shè)計(jì)和代碼復(fù)用(235)
8.4可視化環(huán)境實(shí)例(236)
8.4.1FrameWorks系統(tǒng)(236)
8.4.2EnterprIse并行編程系統(tǒng)(237)
8.4.3CODE2.0語(yǔ)言(238)
8.4.4HeNCE編程環(huán)境(239)
8.4.5TRAPPER編程環(huán)境(240)
8.4.6Meander環(huán)境(241)
8.5小結(jié)(243)
參考文獻(xiàn)(244)
第九章并行程序的調(diào)試(245)
9.1并行調(diào)試的方法與步驟(245)
9.1.1并行調(diào)試的困難(245)
9.1.2并行調(diào)試的方法(246)
9.1.3并行調(diào)試的步驟(247)
9.2并行調(diào)試器的設(shè)計(jì)與實(shí)現(xiàn)(254)
9.2.1前期設(shè)計(jì)(254)
9.2.2初步實(shí)現(xiàn)(256)
9.2.3功能開(kāi)發(fā)(258)
9.2.4維護(hù)(260)
9.3高級(jí)并行調(diào)試技術(shù)簡(jiǎn)介(260)
9.3.1全局?jǐn)帱c(diǎn)(261)
9.3.2漸增檢查點(diǎn)(261)
9.3.3事件分析(261)
9.3.4靜態(tài)分析(262)
9.4并行程序的性能調(diào)試(262)
9.4.1性能調(diào)試的一般步驟(262)
9.4.2性能分析工具舉例：VAMPIR和GuIdeVIew(263)
9.5小結(jié)(267)
參考文獻(xiàn)(267)
第十章并行程序的性能分析(269)
10.1并行程序性能監(jiān)控(269)
10.1.1監(jiān)控的應(yīng)用和分類(lèi)(269)
10.1.2并行跟蹤的實(shí)現(xiàn)(271)
10.1.3侵?jǐn)_的模型和補(bǔ)償處理(273)
10.1.4并行監(jiān)控和操作系統(tǒng)的結(jié)合與交互(275)
10.2并行程序性能預(yù)測(cè)(275)
10.2.1并行系統(tǒng)中的性能預(yù)測(cè)(275)
10.2.2并行系統(tǒng)建模(278)
10.2.3并行系統(tǒng)模擬仿真(281)
10.3性能可視化..(282)
10.3.1可視化的概念(283)
10.3.2數(shù)據(jù)生成(284)
10.3.3數(shù)據(jù)顯示(285)
10.3.4數(shù)據(jù)分析和用戶(hù)交互(289)
10.3.5用戶(hù)界面(291)
10.4小結(jié)(291)
參考文獻(xiàn)(292)
第十一章并行程序的性能優(yōu)化(294)
11.1引言(294)
11.1.1調(diào)度問(wèn)題的一般模型(294)
11.1.2并行計(jì)算中的任務(wù)調(diào)度(295)
11.1.3并行計(jì)算中任務(wù)調(diào)度的分類(lèi)(297)
11.1.4并行計(jì)算中任務(wù)調(diào)度的模型(299)
11.2靜態(tài)任務(wù)調(diào)度的NP完全性及其最優(yōu)算法(302)
11.2.1靜態(tài)任務(wù)調(diào)度的NP完全性(302)
11.2.2靜態(tài)任務(wù)調(diào)度的最優(yōu)算法(304)
11.3靜態(tài)任務(wù)調(diào)度的啟發(fā)式算法(305)
11.3.1貪心算法(305)
11.3.2隨機(jī)算法(306)
11.3.3聚簇策略(307)
11.4動(dòng)態(tài)負(fù)載平衡(308)
11.4.1基本概念(308)
11.4.2負(fù)載信息收集(309)
11.4.3負(fù)載遷移決策(310)
11.4.4負(fù)載遷移執(zhí)行(315)
11.5小結(jié)(317)
參考文獻(xiàn)(318)
第十二章圖形化并行程序集成開(kāi)發(fā)環(huán)境GRADE簡(jiǎn)介(320)
12.1GRADE并行程序集成開(kāi)發(fā)環(huán)境(320)
12.1.1GRADE的組成(321)
12.1.2在GRADE環(huán)境中開(kāi)發(fā)并行程序的步驟(321)
12.2可視化并行程序設(shè)計(jì)(323)
12.2.1可視化并行程序設(shè)計(jì)語(yǔ)言GRAPNEL(323)
12.2.2圖形編輯器GRED(328)
12.3映射和調(diào)度以及負(fù)載平衡工具(330)
12.3.1DSM&S和DLB與GRADE環(huán)境的集成(330)
12.3.2調(diào)度和映射工具(331)
12.3.3動(dòng)態(tài)負(fù)載平衡系統(tǒng)(332)
12.4并行分布式程序調(diào)試器(333)
12.4.1DDBG與GRADE的集成(334)
12.4.2DDBG的體系結(jié)構(gòu)與接口庫(kù)(334)
12.4.3GRED與DDBG的集成(336)
12.5Tape/PVM監(jiān)控器和PROVE可視化工具(337)
12.5.1源代碼插樁(337)
12.5.2數(shù)據(jù)獲取和跟蹤分析(339)
12.5.3可視化(340)
12.6小結(jié)(341)
參考文獻(xiàn)(341)
單元III習(xí)題(343)
下篇并行算法編程實(shí)現(xiàn)
單元IV非數(shù)值并行算法MPI編程實(shí)現(xiàn)
第十三章排序(351)
13.1枚舉排序(351)
13.1.1枚舉排序及其串行算法(351)
13.1.2枚舉排序的并行算法(352)
13.2快速排序(353)
13.2.1快速排序及其串行算法(353)
13.2.2快速排序的并行算法(354)
13.3并行正則采樣排序PSRS(356)
13.3.1PSRS算法原理(356)
13.3.2PSRS算法形式化描述(356)
13.4小結(jié)(357)
參考文獻(xiàn)(357)
附錄PSRS算法MPI源程序(358)
第十四章串匹配(364)
14.1KMP串匹配算法(364)
14.1.1KMP串匹配及其串行算法(364)
14.1.2KMP串匹配的并行算法(368)
14.2隨機(jī)串匹配算法(372)
14.2.1隨機(jī)串匹配及其串行算法(372)
14.2.2隨機(jī)串匹配的并行算法(374)
14.3近似串匹配算法(375)
14.3.1近似串匹配及其串行算法(375)
14.3.2近似串匹配的并行算法(381)
14.4小結(jié)(383)
參考文獻(xiàn)(383)
附錄KMP串匹配并行算法的MPI源程序(385)
第十五章圖論(392)
15.1傳遞閉包(392)
15.1.1傳遞閉包串行算法(392)
15.1.2傳遞閉包并行算法(394)
15.2連通分量(396)
15.2.1頂點(diǎn)倒塌法算法原理描述(396)
15.2.2連通分量并行算法(396)
15.3單源最短路徑(398)
15.3.1最短路徑串行算法(398)
15.3.2最短路徑并行算法(399)
15.4最小生成樹(shù)(402)
15.4.1最小生成樹(shù)串行算法(402)
15.4.2最小生成樹(shù)并行算法(403)
15.5小結(jié)(406)
參考文獻(xiàn)(406)
附錄連通分量并行算法的MPI源程序(407)
第十六章組合優(yōu)化(411)
16.1八皇后問(wèn)題(411)
16.1.1八皇后問(wèn)題及其串行算法(411)
16.1.2八皇后問(wèn)題的并行算法(412)
16.2SAT問(wèn)題(414)
16.2.1SAT問(wèn)題及其串行算法(414)
16.2.2SAT問(wèn)題的并行算法(415)
16.3裝箱問(wèn)題(418)
16.3.1裝箱問(wèn)題及其串行算法(418)
16.3.2裝箱問(wèn)題的并行算法(419)
16.4背包問(wèn)題(420)
16.4.1背包問(wèn)題及其串行算法(420)
16.4.2背包問(wèn)題的并行算法(422)
16.5TSP問(wèn)題(423)
16.5.1TSP問(wèn)題及其串行算法(423)
16.5.2TSP問(wèn)題的并行算法(423)
16.6小結(jié)(425)
參考文獻(xiàn)(426)
附錄八皇后問(wèn)題并行算法的MPI源程序(427)
第十七章計(jì)算幾何(432)
17.1包含問(wèn)題(432)
17.1.1包含問(wèn)題及其串行算法(432)
17.1.2包含問(wèn)題并行算法(433)
17.2相交問(wèn)題(435)
17.2.1兩多邊形相交問(wèn)題及其串行算法(435)
17.2.2相交問(wèn)題的并行算法(436)
17.3凸殼問(wèn)題(437)
17.3.1凸殼問(wèn)題及其串行算法(438)
17.3.2凸殼問(wèn)題并行算法(439)
17.4小結(jié)(440)
參考文獻(xiàn)(440)
附錄包含問(wèn)題并行算法的MPI源程序(441)
單元IV習(xí)題(444)
單元V數(shù)值并行算法MPI編程實(shí)現(xiàn)
第十八章矩陣運(yùn)算(455)
18.1矩陣轉(zhuǎn)置(455)
18.1.1矩陣轉(zhuǎn)置及其串行算法(455)
18.1.2矩陣轉(zhuǎn)置并行算法(456)
18.2矩陣-向量乘法(458)
18.2.1矩陣-向量乘法及其串行算法(458)
18.2.2矩陣-向量乘法的并行算法(458)
18.3行列劃分矩陣乘法(459)
18.3.1矩陣相乘及其串行算法(459)
18.3.2簡(jiǎn)單的矩陣并行分塊乘法算法(460)
18.4Cannon乘法(462)
18.4.1Cannon乘法的原理(462)
18.4.2Cannon乘法的并行算法(462)
18.5LU分解(466)
18.5.1矩陣的LU分解及其串行算法(466)
18.5.2矩陣LU分解的并行算法(467)
18.6QR分解(469)
18.6.1矩陣QR分解的串行算法(469)
18.6.2矩陣QR分解的并行算法(471)
18.7奇異值分解(474)
18.7.1矩陣奇異值分解的串行算法(474)
18.7.2矩陣奇異值分解的并行算法(477)
18.8Cholesky分解(480)
18.8.1矩陣Cholesky分解的串行算法(480)
18.8.2矩陣Cholesky分解的并行算法(481)
18.9矩陣求逆(483)
18.9.1求矩陣的逆的串行算法(483)
18.9.2矩陣求逆的并行算法(484)
18.10小結(jié)(486)
參考文獻(xiàn)(486)
附錄一Cannon乘法并行算法的MPI源程序(488)
附錄二矩陣LU分解并行算法的MPI源程序(494)
附錄三矩陣求逆并行算法的MPI源程序(498)
第十九章線(xiàn)性方程組的直接解法(504)
19.1高斯消去法解線(xiàn)性方程組(504)
19.1.1高斯消去及其串行算法(504)
19.1.2并行高斯消去算法(507)
19.2約當(dāng)消去法解線(xiàn)性方程組(512)
19.2.1約當(dāng)消去及其串行算法(512)
19.2.2約當(dāng)消去法的并行算法(514)
19.3小結(jié)(517)參考文獻(xiàn)(518)
附錄全主元高斯消去法并行算法的MPI源程序(519)
第二十章線(xiàn)性方程組的迭代解法(524)
20.1雅可比迭代(524)
20.1.1雅可比迭代及其串行算法(524)
20.1.2雅可比迭代并行算法(526)
20.2高斯-塞德?tīng)柕?527)
20.2.1高斯-塞德?tīng)柕捌浯兴惴?527)
20.2.2高斯-塞德?tīng)柕⑿兴惴?528)
20.3松弛法(531)
20.3.1松弛法及其串行算法(531)
20.3.2松弛法并行算法(532)
20.4小結(jié)(534)
參考文獻(xiàn)(534)
附錄高斯-塞德?tīng)柕⑿兴惴ǖ腗PI源程序(535)
第二十一章矩陣特征值計(jì)算(540)
21.1求解矩陣最大特征值的乘冪法(540)
21.1.1乘冪法及其串行算法(540)
21.1.2乘冪法并行算法(541)
21.2求對(duì)稱(chēng)矩陣特征值的雅可比法(543)
21.2.1雅可比法求對(duì)稱(chēng)矩陣特征值的串行算法(543)
21.2.2雅可比法求對(duì)稱(chēng)矩陣特征值的并行算法(546)
21.3求對(duì)稱(chēng)矩陣特征值的單側(cè)旋轉(zhuǎn)法(556)
21.3.1單側(cè)旋轉(zhuǎn)法的算法描述(556)
21.3.2求對(duì)稱(chēng)矩陣特征值的單側(cè)旋轉(zhuǎn)法的并行計(jì)算(559)
21.4求一般矩陣全部特征值的QR方法(562)
21.4.1QR方法求一般矩陣全部特征值的串行算法(562)
21.4.2QR方法求一般矩陣全部特征值的并行算法(563)
21.5小結(jié)(565)
參考文獻(xiàn)(566)
附錄求對(duì)稱(chēng)矩陣特征值的雅可比并行算法MPI源程序(567)
第二十二章快速傅氏變換和離散小波變換(581)
22.1快速傅里葉變換FFT(581)
22.1.1串行FFT迭代算法(581)
22.1.2并行FFT算法(583)
22.2離散小波變換DWT(585)
22.2.1離散小波變換DWT及其串行算法(585)
22.2.2離散小波變換并行算法(588)
22.3小結(jié)(590)
參考文獻(xiàn)(590)
附錄FFT并行算法的MPI源程序(591)
單元V習(xí)題(598)
算法索引(607)
MPI源程序清單...(609)
專(zhuān)業(yè)術(shù)語(yǔ)中英文對(duì)照及索引(611)