并行算法實踐

定　價：￥49.50

作　者：	陳國良[等]編著
出版社：	高等教育出版社
叢編項：	并行計算系列叢書
標　簽：	算法

購買這本書可以去

ISBN：	9787040133066	出版時間：	2004-01-01	包裝：	膠版紙
開本：	24cm	頁數(shù)：	619	字數(shù)：

內(nèi)容簡介

　　本書是并行計算系列叢書之四，旨在介紹并行程序設(shè)計的有關(guān)知識和并行算法的具體編程實現(xiàn)。.本書從內(nèi)容安排上分為上篇和下篇。其中，上篇為并行程序設(shè)計導(dǎo)論，主要包括并行程序設(shè)計基礎(chǔ)（并行計算機系統(tǒng)與結(jié)構(gòu)模型、PC機群搭建和并行程序設(shè)計簡介等）、并行程序編程指南（MPI、PVM、HPF和OpenMP等）和并行程序開發(fā)方法（可視化并行程序設(shè)計環(huán)境、并行程序調(diào)試和并行程序性能分析及優(yōu)化等）；下篇為并行算法編程實現(xiàn)，主要包括非數(shù)值并行算法（排序、串匹配、圖論、組合優(yōu)化和計算幾何等）及其MPI編程實現(xiàn)和數(shù)值計算并行算法（矩陣運算、線性方程組求解、矩陣特征值計算和傅氏及小波變換等）及其MPI編程實現(xiàn)。書后所附的光盤中包含了第Ⅳ單元和第Ⅴ單元中所有并行算法的MPI源程序。..書中內(nèi)容精煉、實用，體現(xiàn)了并行算法的設(shè)計與實現(xiàn)相結(jié)合，可作為高等學(xué)校計算機及相關(guān)專業(yè)的本科高年級學(xué)生和研究生的教材，其中上篇和下篇也可分別作為“并行程序設(shè)計導(dǎo)論”和“并行算法編程指南”單獨使用。本書也可供從事并行程序設(shè)計及其實現(xiàn)的科技人員參考閱讀。...

作者簡介

　　陳國良，中國科學(xué)技術(shù)大學(xué)教授，1938年6月生，安徽穎上人。1961年畢業(yè)于西安交通大學(xué)無線電系計算機專業(yè)?，F(xiàn)任國家高性能計算中心（合肥）主任，博士生導(dǎo)師，國家教育部高等學(xué)校計算機科學(xué)技術(shù)教學(xué)指導(dǎo)委員會副主任，全國高等教育電子、電工與信息類專業(yè)自考指導(dǎo)委員會副主任，中國計算機學(xué)會理事，中國計算機學(xué)會開放系統(tǒng)專業(yè)委員會副主任，中國數(shù)學(xué)會計算數(shù)學(xué)并行計算專業(yè)委員會委員，中國計算機學(xué)會數(shù)據(jù)通信與計算機網(wǎng)絡(luò)專業(yè)委員會委員，全國自然科學(xué)名詞審定委員會委員。曾任中國科學(xué)技術(shù)大學(xué)計算機系主任和安徽省計算機學(xué)會理事長。享受國家政府特殊津貼。陳國良教授長期從事計算機科學(xué)技術(shù)的教學(xué)與研究工作。主要研究領(lǐng)域為并行算法、計算機體系結(jié)構(gòu)、計算機網(wǎng)絡(luò)和神經(jīng)計算等。先后主持完成了10多項國家863計劃、國家攀登計劃、國家973計劃、國家自然基金、教育部博士基金等科研項目。取得了多項被國內(nèi)外廣泛引用的、達到國際先進水平的科研成果，發(fā)表論文100多篇，出版著作7部、譯著5部，參與主編計算機類詞典、詞匯5部，主審、主編計算機類各種教材8部。曾獲國家級二等獎以及部、省、院級一等、二等、三等獎共11項。十幾年來，陳國良教授先后指導(dǎo)計算機專業(yè)碩士研究生40余名和博士研究生30余名，率先創(chuàng)建了我國第一個國家高性能計算中心，為我國培養(yǎng)了一批在國內(nèi)外從事算法研究的高級人才。日前，水利部淮河水利委員會在致中國科學(xué)技術(shù)大學(xué)的感謝信中說：“特別感謝陳國良教授項目組，在淮河今夏防洪戰(zhàn)斗中親臨防洪調(diào)度第一線以及提供高性能計算支持，使我們?nèi)〉昧藨?zhàn)勝特大洪水的勝利?！备兄x信中提到的陳國良，人稱“神算子”，現(xiàn)為中國科學(xué)技術(shù)大學(xué)教授，博士生導(dǎo)師，國家高性能計算中心（合肥）主任，國際高性能計算（亞洲）常務(wù)理事。不計名利，振興國貨陳國良教授是安徽省潁上人，父母都是地地道道的莊稼人，大字不識一個。由于家里困難，陳教授靠國家的助學(xué)金讀完了中學(xué)。1956年考入上海交通大學(xué)電力系，成為方圓幾十里的第一個大學(xué)生。進入大學(xué)不久，隨大學(xué)整體搬遷到西安，他又成了西安交通大學(xué)的學(xué)生。1961年畢業(yè)后，參軍從事國防科研工作，1973年，陳教授調(diào)入科大，至今在科大從事教育科研事業(yè)整整30年。從大學(xué)時代起，陳教授就參加了電子管計算機和晶體管計算機等兩代國產(chǎn)計算機的研制，對民族計算機事業(yè)深有感情。由于文革的影響，我國自行研制的計算機與世界水平的差距在不斷加大，國內(nèi)計算機市場幾乎被國外壟斷，硬軟件幾乎全部進口，對于搞硬件出身、親自做了兩代計算機的陳教授來說，感到很失落，只好“下崗”而“再就業(yè)”于并行算法的研究?！拔覀冇心芰υ诟咝阅苡嬎慵夹g(shù)上趕超世界先進水平，在世界高性能計算機領(lǐng)域占有一席之地”。近些年，經(jīng)過幾代科學(xué)家和研制者的不懈努力和刻苦攻關(guān)，我國已研制出不少高性能計算機。然而研制出來后面臨推廣應(yīng)用的困難，有人甚至對國產(chǎn)并行機表示懷疑。但陳教授認為國家研制出了先進的計算機不應(yīng)用，那用來干嘛呢！他堅持不怕國產(chǎn)機不好用，就怕你不用，通過用可以發(fā)現(xiàn)不好用的地方，有毛病可以找專家來幫助解決。陳教授平時不愛與人爭執(zhí)，但在推行“曙光1000”受到阻力時卻極力抗爭，并在自己的實驗室購置了“曙光1000”。他提出的“扶君上馬，送君一程”的服務(wù)口號，得到了許多人支持，同時也為推動國產(chǎn)計算機的應(yīng)用起到了樣板作用。研制并行計算機最終是為了應(yīng)用，但在安徽，什么地方才能用到這么大的一個機器呢？陳教授是在淮河邊上長大的，深知淮河的厲害。江淮之間氣候復(fù)雜，災(zāi)害性天氣時常發(fā)生，那么能不能用這臺大型計算機來做安徽省的數(shù)值氣象預(yù)報、淮河水情預(yù)測和水庫調(diào)度服務(wù)于江淮百姓呢？于是陳教授憑借自己多年從事并行算法研究的技術(shù)和人才優(yōu)勢，自愿請纓，組織第一批“敢死隊”，先后五次到蚌埠與淮委聯(lián)系，不厭其煩地教用戶怎樣使用并行機，義務(wù)幫助用戶并行化串行程序等，直到用戶能夠自行獨立使用為止，最后以三顧茅廬的誠意和愚公移山的毅力感動了用戶。淮委領(lǐng)導(dǎo)說，象中國科大這位白發(fā)蒼蒼的教授，屢屢登門，不計報酬，還賠上學(xué)生和設(shè)備，到哪里去找？我們有什么理由不與他們合作而將其拒之門外？就這樣，陳老師打開了曙光并行機在安徽省防災(zāi)減災(zāi)中的應(yīng)用。“精誠所至，金石為開”，如今國產(chǎn)并行機在我國計算機產(chǎn)業(yè)中占有了一席之地。1995年陳國良創(chuàng)建了我國第一個國家高性能計算中心，先后承擔(dān)了國家863重大項目“安徽省防災(zāi)減災(zāi)智能信息與決策支持系統(tǒng)”和“淮河流域防洪防污智能調(diào)度系統(tǒng)”。他還與淮委成立了水科學(xué)與工程聯(lián)合實驗室，并在寧波成立了國家高性能計算中心分中心，努力將并行機用于杭州灣數(shù)字化大橋建設(shè)管理中，拓展國產(chǎn)機的應(yīng)用領(lǐng)域。學(xué)以致用，情系淮河淮河，本是一條尾閭通暢的河流?！白咔ё呷f，不如淮河兩岸”，這曾是千百年來淮河兒女美好生活的生動寫照，但是黃河多次潰決奪淮，使淮河喪失了入?？?，淮河也就經(jīng)常桀驁不馴，泛濫成災(zāi)。僅新中國成立以來，淮河流域平均10年左右就發(fā)生一次大洪水。早在新中國成立不久，毛澤東主席就含淚寫下“一定要把淮河修好”的題詞，后來幾代水利專家都傾注心血治理淮河，但是淮河水系復(fù)雜，水庫繁多，如何對這些大型水庫進行全局優(yōu)化調(diào)度，利用“蓄泄兼施”，達到“上控、中暢、下泄”，這就需要精密計算，科學(xué)調(diào)度。這位喝著淮河水長大的淮河之子，對母親河有著與生俱來的情感。他的母校鳳臺中學(xué)就挨著淮河大堤，陳教授從小就對淮河水患感同身受。每逢暴風(fēng)驟雨，一夜醒來，學(xué)校周圍一片汪洋。在汛期如注暴雨的肆虐之下，萬頃良田頓時變成茫茫澤國，父老鄉(xiāng)親無奈舉家逃荒，這在陳國良心頭留下難以抹去的陰影。多年來，陳教授與淮委緊密合作，成功研制了“安徽省防災(zāi)減災(zāi)智能信息與決策支持系統(tǒng)”。該系統(tǒng)使用曙光1000作為服務(wù)器，將中尺度數(shù)值氣象預(yù)報模式MM4的計算結(jié)果作為水情預(yù)測和群庫優(yōu)化調(diào)度的決策參考依據(jù)，在汛期對淮河中上游九大水庫進行防洪調(diào)度，取得了顯著的社會和經(jīng)濟效益，獲得2001年度國家科技進步二等獎。今年夏天，淮河流域遭受了50年一遇的特大洪澇災(zāi)害，水情、災(zāi)情時刻牽動著陳教授的心。6月28日至7月15日是淮河抗洪工作最緊張的時刻，陳教授帶領(lǐng)中國科大師生一行10人親臨防洪現(xiàn)場，為防洪調(diào)度決策提供高性能計算支持。同時，為了確保計算參數(shù)的準確性，他還與淮委相關(guān)技術(shù)人員一同對“方邱湖”、“西大壩”等防洪重點區(qū)域進行了實地考察，提出了洪水演進計算方案，為該區(qū)域的防洪調(diào)度工作提供了科學(xué)依據(jù)。

圖書目錄

上篇并行程序設(shè)計導(dǎo)論
單元I并行程序設(shè)計基礎(chǔ).
第一章并行計算機系統(tǒng)與結(jié)構(gòu)模型(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當代并行計算機體系結(jié)構(gòu)(14)
1.2.1并行計算機體系結(jié)構(gòu)模型(14)
1.2.2并行計算機存儲結(jié)構(gòu)模型(17)
1.2.3分布式高速緩存與主存體系結(jié)構(gòu)(19)
1.3小結(jié)(22)
參考文獻(23)
第二章PC機群的搭建(24)
2.1機群系統(tǒng)概述(24)
2.1.1機群系統(tǒng)原理與技術(shù)(24)
2.1.2典型機群系統(tǒng)簡介(26)
2.2硬件的選擇與安裝(27)
2.2.1節(jié)點構(gòu)建(28)
2.2.2系統(tǒng)構(gòu)建(31)
2.2.3機群系統(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機群系統(tǒng)性能評測(49)
2.4.1基準測試程序(49)
2.4.2性能分析工具(53)
2.5小結(jié)(56)
參考文獻(56)
第三章并行程序設(shè)計簡介(58)
3.1并行程序開發(fā)方法(58)
3.1.1并行層次與代碼粒度(58)
3.1.2并行程序開發(fā)策略(59)
3.1.3并行編程模式(61)
3.1.4并行應(yīng)用編程過程(63)
3.2并行程序設(shè)計模型(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ù)相關(guān)分析(78)
3.4.2數(shù)據(jù)劃分與處理器指派(80)
3.4.3循環(huán)重構(gòu)(87)
3.5小結(jié)(96)
參考文獻(96)
單元I習(xí)題(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小結(jié)(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任務(wù)(139)
5.4.1任務(wù)派生(139)
5.4.2任務(wù)組(140)
5.4.3任務(wù)標識符(141)
5.4.4任務(wù)管理(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虛擬機結(jié)構(gòu)(146)
5.6.1結(jié)構(gòu)分析(147)
5.6.2動態(tài)配置(147)
5.6.3PVM虛擬機的構(gòu)建過程(148)
5.7小結(jié)(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程序?qū)嵗?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ù)并行結(jié)構(gòu)(165)
6.4.1數(shù)組運算(165)
6.4.2FORALL語句和FORALL結(jié)構(gòu)(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小結(jié)(180)
參考文獻(181)
附錄一HPF指令語法(182)
附錄二一般的內(nèi)部函數(shù)及庫函數(shù)(184)
附錄三HPF網(wǎng)絡(luò)資源(187)
第七章OpenMP編程指南(189)
7.1OpenMP概述(189)
7.1.1什么是OpenMP(190)
7.1.2OpenMP的歷史(191)
7.1.3OpenMP的目標(191)
7.2OpenMP編程風(fēng)格(191)
7.2.1OpenMP并行編程模型(191)
7.2.2OpenMP程序結(jié)構(gòu)(192)
7.3OpenMP編程簡介(193)
7.3.1一個簡單的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)語句(205)
7.3.8數(shù)據(jù)域?qū)傩宰泳?206)
7.3.9子句/編譯制導(dǎo)語句總結(jié)(208)
7.3.10語句的綁定和嵌套規(guī)則(209)
7.4運行庫例程與環(huán)境變量(210)
7.5OpenMP計算實例(210)
7.6小結(jié)(213)
參考文獻(214)
附錄運行庫例程(215)
單元II習(xí)題(217)
單元III并行程序開發(fā)方法
第八章可視化并行程序設(shè)計環(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正則并行結(jié)構(gòu)(234)
8.3.5分層設(shè)計和代碼復(fù)用(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小結(jié)(243)
參考文獻(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è)計與實現(xiàn)(254)
9.2.1前期設(shè)計(254)
9.2.2初步實現(xiàn)(256)
9.2.3功能開發(fā)(258)
9.2.4維護(260)
9.3高級并行調(diào)試技術(shù)簡介(260)
9.3.1全局斷點(261)
9.3.2漸增檢查點(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)
參考文獻(267)
第十章并行程序的性能分析(269)
10.1并行程序性能監(jiān)控(269)
10.1.1監(jiān)控的應(yīng)用和分類(269)
10.1.2并行跟蹤的實現(xiàn)(271)
10.1.3侵擾的模型和補償處理(273)
10.1.4并行監(jiān)控和操作系統(tǒng)的結(jié)合與交互(275)
10.2并行程序性能預(yù)測(275)
10.2.1并行系統(tǒng)中的性能預(yù)測(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小結(jié)(291)
參考文獻(292)
第十一章并行程序的性能優(yōu)化(294)
11.1引言(294)
11.1.1調(diào)度問題的一般模型(294)
11.1.2并行計算中的任務(wù)調(diào)度(295)
11.1.3并行計算中任務(wù)調(diào)度的分類(297)
11.1.4并行計算中任務(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隨機算法(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小結(jié)(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可視化并行程序設(shè)計(323)
12.2.1可視化并行程序設(shè)計語言GRAPNEL(323)
12.2.2圖形編輯器GRED(328)
12.3映射和調(diào)度以及負載平衡工具(330)
12.3.1DSM&S和DLB與GRADE環(huán)境的集成(330)
12.3.2調(diào)度和映射工具(331)
12.3.3動態(tài)負載平衡系統(tǒng)(332)
12.4并行分布式程序調(diào)試器(333)
12.4.1DDBG與GRADE的集成(334)
12.4.2DDBG的體系結(jié)構(gòu)與接口庫(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)
參考文獻(341)
單元III習(xí)題(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小結(jié)(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小結(jié)(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小結(jié)(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小結(jié)(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小結(jié)(440)
參考文獻(440)
附錄包含問題并行算法的MPI源程序(441)
單元IV習(xí)題(444)
單元V數(shù)值并行算法MPI編程實現(xià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簡單的矩陣并行分塊乘法算法(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)
參考文獻(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小結(jié)(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小結(jié)(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求對稱矩陣特征值的單側(cè)旋轉(zhuǎn)法(556)
21.3.1單側(cè)旋轉(zhuǎn)法的算法描述(556)
21.3.2求對稱矩陣特征值的單側(cè)旋轉(zhuǎn)法的并行計算(559)
21.4求一般矩陣全部特征值的QR方法(562)
21.4.1QR方法求一般矩陣全部特征值的串行算法(562)
21.4.2QR方法求一般矩陣全部特征值的并行算法(563)
21.5小結(jié)(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小結(jié)(590)
參考文獻(590)
附錄FFT并行算法的MPI源程序(591)
單元V習(xí)題(598)
算法索引(607)
MPI源程序清單...(609)
專業(yè)術(shù)語中英文對照及索引(611)