并行算法的設(shè)計(jì)與分析

前言

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

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

插圖：

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    并行算法的設(shè)計(jì)與分析 PDF格式下載

---