并行算法實踐

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