并行算法的設計與分析

前言

高性能計算機是一個國家經濟和科技實力的綜合體現(xiàn)，也是促進經濟、科技發(fā)展，社會進步和國防安全的重要工具，已成為世界各國競相爭奪的戰(zhàn)略制高點。一些發(fā)達國家紛紛制定戰(zhàn)略計劃，提出很高目標，投入大量資金，加速研究開發(fā)步伐。多年來，隨著大規(guī)模集成電路技術的不斷進步，以多CPU為基礎的高性能并行計算機得到了迅速的發(fā)展，其高端系統(tǒng)正向百萬億次、千萬億次邁進。我國近十年來，對高性能并行計算的研究開發(fā)也給予了很大重視，取得了長足進步和可貴經驗，研制出了具有相當水平的并行機系統(tǒng)，但與發(fā)達國家相比，差距仍然甚大，在高性能并行計算的應用開發(fā)與相關的人才培養(yǎng)教育方面尤顯不足。如何使高性能并行機系統(tǒng)深入充分地在國民經濟、科研和社會應用的發(fā)展中發(fā)揮作用，實為當務之急，引起人們的普遍關心。由中國科技大學陳國良教授主編的這套叢書，正適應了我國高性能并行計算研究、開發(fā)、應用、教育之需。本叢書由《并行算法的設計與分析》、《并行計算機體系結構》和《并行算法實踐》三大部分組成，而以《并行計算——結構·算法·編程》為全叢書之提要。該叢書以并行計算為主題，對并行計算的硬件平臺（當代主流并行計算機系統(tǒng)）、并行計算的理論基礎（并行算法的設計與分析）和并行計算的軟件支撐（并行程序設計）全面系統(tǒng)地展開了討論，內容豐富，取材新近，具有相當?shù)纳疃群蛷V度，涵蓋了并行計算機體系結構和并行算法的理論、設計和實踐的各個方面，是國內外不多見的優(yōu)秀著作。陳國良教授是國家高性能計算中心（合肥）主任，長期從事并行算法和并行計算機體系結構的研究，本套叢書是作者幾十年從事教學與科研工作的結晶，是目前國內該領域內容涵蓋最為全面的系列著作。它的出版必將對進一步推動我國并行計算學科的發(fā)展與應用推廣產生深遠的影響。

內容概要

　　《并行算法的設計與分析（修訂版）》在初版基礎上，對個別章節(jié)進行了修改補充，并在每章的開頭，除原有的“內容提要”外，又新增加，“講授要點”，可作為授課教師的教學指導和參考?！恫⑿兴惴ǖ脑O計與分析（修訂版）》系統(tǒng)全面地討論了各種專用和通用并行計算模型上的算法的設計和分析方法。書中以并行計算模型為線索，強調算法、結構和模型三者之間的密切關系，著重介紹了各種最基本、常用和典型的并行算法，同時也力圖反映本學科的最新成就和發(fā)展趨勢。　　全書共分二十章，主要內容包括并行算法基礎，并行算法的基本設計技術，各種計算模型上的計算機領域中諸多常用計算問題的并行算法的設計和分析方法，最后還討論了各種并行計算模型的能力、限制、等價性以及與并行計算有關的NC一理論問題。　　《并行算法的設計與分析（修訂版）》取材豐富，內容系統(tǒng)全面，可作為高等學校計算機及其他信息科學類有關專業(yè)高年級學生或研究生的教材．也可供從事計算機科學理論和算法研究的科技人員閱讀參考?！　　恫⑿兴惴ǖ脑O計與分析（修訂版）》初版于1994年，曾獲教育部高等學校優(yōu)秀教材一等獎。

作者簡介

陳國良，中國科學技術大學教授，博士生導師，中國科學院院士，1938年6月生于安徽省潁上縣，1961年畢業(yè)于西安交通大學無線電系計算機專業(yè)。1981-1983年在美國普度大學作訪問學者，1984年至今曾多次應邀赴東京大學、普度大學、澳大利亞國立大學、新南威爾士大學、昆士蘭大學、格里福斯大學、堪薩斯城市大學、依阿華大學、威斯康星大學、Mahat‘ish國際大學、香港理工大學、澳門大學、北京大學、國防科技大學等講學交流?，F(xiàn)任國家高性能計算中心（合肥）主任，國際高性能計算（亞洲）常務理事，中國計算機學會開放系統(tǒng)專業(yè)委員會副主任，中國數(shù)學會計算數(shù)學并行計算專業(yè)委員會委員。曾任國家教育部高等學校計算機科學與技術教學指導委員會副主任，全國高等教育電子、電工和信息類專業(yè)自考指導委員會副主任，安徽省高校計算機基礎課程教學指導委員會副主任，中國計算機學會理事，安徽省計算機學會理事長，全國自然科學名詞審定委員會委員，中國科學技術大學計算機系主任。陳國良教授長期從事計算機科學技術的研究與教學工作。主要研究領域為并行算法、并行計算機體系結構和智能計算等。先后承擔10多項國家863計劃、國家攀登計劃、國家自然科學基金、國家973計劃、教育部博士點基金等科研項目。取得了多項被國內外廣泛引用、達國際先進水平的科研成果，發(fā)表論文200多篇，出版著作9部、譯著5部，參與主編計算機類辭典、詞匯5部，主審、主編計算機類各種教材8部。曾獲國家科技進步二等獎、國家級教學成果二等獎、國家教育部科技進步一等獎、中國科學院科技進步二等獎和自然科學三等獎、全國優(yōu)秀教材一等獎、全國學術著作優(yōu)秀獎、安徽省科技進步二等獎、國家科委高技術研究與發(fā)展計劃三等獎、國家教委科技進步三等獎共18項，并獲2001年度“國家863計劃15周年先進個人重要貢獻獎”。陳國良教授在中國科學技術大學執(zhí)教30多年。長期以來，圍繞著并行算法的教學與研究，逐漸形成了一套完整的“算法理論一算法設計一算法實現(xiàn)一算法應用”的并行算法學科體系，營造了我國并行算法類的教學基地。他先后指導培養(yǎng)研究生100多名，其中博士生60名，為我國培養(yǎng)了一批在國內外從事算法研究的高級人才。曾榮獲1998年度安徽省教育系統(tǒng)勞動模范、安徽省優(yōu)秀教師稱號、2001年度寶鋼教育基金優(yōu)秀教師特等獎和2003年度第一屆高等學校教學名師獎。陳國良教授是我國非數(shù)值并行算法研究的學科帶頭人。他率先創(chuàng)建的我國第一個國家高性能計算中心是我國并行算法研究、環(huán)境科學與工程計算軟件的重要基地，在學術界和教育界有一定的影響和地位。

書籍目錄

第一章 并行算法基礎1.1 并行算法的硬件基礎1.1.1 當代并行計算機體系結構1.1.2 并行計算機互連網(wǎng)絡1.2 并行計算模型1.2.1 SIMD同步并行計算模型1.2.2 MIMD異步并行計算模型1.2.3 其他并行計算模型1.3 并行算法編程模型1.3.1 數(shù)據(jù)并行模型1.3.2 消息傳遞模型1.3.3 共享變量模型1.4 并行算法的一般概念1.4.1 并行算法的定義和分類1.4.2 并行算法的表達1.4.3 并行算法的復雜性度量1.4.4 并行算法的WT表示1.4.5 并行算法的同步和通信習題參考文獻第二章 并行算法的基本設計技術2.1 平衡樹方法2.1.1 求取最大值2.1.2 計算前綴和2.2 倍增技術2.2.1 表序問題的計算2.2.2 求森林的根2.3 分治策略2.3.1 SIMD模型上分治算法的描述2.3.2 SIMD共享存儲模型上的FFT算法2.4 劃分原理2.4.1 歸并原理2.4.2 劃分算法與歸并算法2.5 流水線技術2.5.1 一維陣列上的流水線歸并排序原理2.5.2 一維陣列上的流水線歸并排序算法2.6 加速級聯(lián)策略2.6.1 常數(shù)時間求最大值算法2.6.2 雙對數(shù)時間算法2.6.3 加速級聯(lián)算法2.7 破對稱技術2.7.1 基本著色算法2.7.2 快速3-著色算法2.7.3 最優(yōu)3-著色算法習題參考文獻第三章 比較器網(wǎng)絡上的排序和選擇算法3.1 Batcher歸并和排序網(wǎng)絡3.1.1 比較操作和[0，1]原理3.1.2 奇偶歸并網(wǎng)絡3.1.3 雙調歸并網(wǎng)絡3.1.4 Bateher排序網(wǎng)絡3.2 （m，n）一選擇網(wǎng)絡3.2.1 分組選擇網(wǎng)絡3.2.2 平衡分組選擇網(wǎng)絡3.3 AKS排序網(wǎng)絡3.3.1 擴展圖和劃分網(wǎng)絡3.3.2 部分排序算法3.3.3 完全排序算法習題參考文獻第四章 排序和選擇的同步算法4.1 Stone雙調排序算法4.1.1 均勻洗牌函數(shù)及其性質4.1.2 Stone的觀察及其計算模型4.1.3 Stone的并行排序算法4.2 Thompson和Kung雙調排序算法4.2.1 處理器編號方式4.2.2 Thompon和Kung的觀察4.2.3 Thompon和Kung的雙調排序算法4.3 Preparata和Vuilemin雙調排序算法4.3.1 算法原理4.3.2 流水線技術4.3.3 算法描述4.4 Akl并行k-選擇算法4.4.1 算法原理及物理描述4.4.2 并行k-選擇算法4.4.3 算法分析4.5 Valiant并行歸并算法4.5.1 歸并算法的基本原理4.5.2 k=pq時Valiant歸并4.5.3 k=rpq時Valiant歸并4.6 Hirschberg并行桶排序算法4.6.1 并行桶排序算法原理4.6.2 并行桶排序算法描述4.7 Preparata并行枚舉排序算法4.7.1 枚舉排序及其實現(xiàn)方法4.7.2 排序算法的設計和分析4.8 Cole并行歸并排序算法4.8.1 使用覆蓋和位序的歸并方法4.8.2 Cole最佳排序算法4.8.3 算法的正確性證明及分析習題參考文獻第五章排序和選擇的異步和分布式算法5.1 MIMD-CREW模型上的異步枚舉排序算法5.1.1 算法原理和描述5.1.2 算法舉例和分析5.2 MIMD.TC模型上的異步快排序算法5.2.1 算法原理和描述5.2.2 算法舉例和分析5.3 分布式k-選擇算法5.3.1 隨機k-選擇算法5.3.2 確定k-選擇算法5.4 分布式求中值算法5.4.1 分布式中值5.4.2 分布式求中值算法5.5 分布式定序算法5.5.1 分布式計算模型5.5.2 分布式定序算法5.5.3 算法復雜度分析5.6 分布式排序算法5.6.1 模型和定義5.6.2 靜態(tài)排序算法5.6.3 算法復雜度分析習題參考文獻第六章并行搜索6.1 單處理機上的搜索6.1.1 單處理機上的順序搜索6.1.2 單處理機上有序表的對半搜索6.2 SIMD共享存儲模型上有序表的搜索6.2.1 SIMD-EREW模型上的搜索6.2.2 SIMD-CREW模型上的搜索6.3 SIMD共享存儲模型上隨機序列的搜索6.3.1 sIMD-SM模型上的隨機序列搜索.算法描述6.3.2 sIMDS-M模型上的隨機序列搜索算法分析6.4 樹連接的SIMD模型上隨機序列的搜索6.4.1 提問6.4.2 維護6.5 網(wǎng)孔連接的SIMD模型上隨機序列的搜索6.5.1 提問6.5.2 維護6.6 MIMD共享存儲模型上有序表的搜索6.6.1 AVL樹及其順序插入算法6.6.2 Ellis并行搜索和插入算法習題第七章排列和組合第八章數(shù)據(jù)傳輸與選路第九章并行串匹配第十章表達式求值第十一章上下文無關語富的并行識別與語法分析第十二章矩陣運算第十三章數(shù)值計算第四章腫和卷積與濾波

章節(jié)摘錄

插圖：

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    并行算法的設計與分析 PDF格式下載

---