串行算法并行化基礎(chǔ)

前言

當(dāng)今，高性能計(jì)算機(jī)系統(tǒng)令人注目?？上Ц咝阅苡?jì)算機(jī)系統(tǒng)兩個(gè)重要難點(diǎn)至今沒有解決：一是不好用，二是效率低。20世紀(jì)60年代研制的“單指令流一多數(shù)據(jù)流”ILLIAC-4機(jī)（最早的巨型機(jī)）就遇到了這樣的問題，因?yàn)樗谶\(yùn)行中的并行、存儲(chǔ)和通信等全部需要用戶進(jìn)行人工處理，因此很不好用?？蒲腥藛T通過改進(jìn)系統(tǒng)結(jié)構(gòu)、引入向量語言和高級(jí)編程語言自動(dòng)向量化，解決了“不好用”的問題，同時(shí)“效率低”的問題也得到了緩解。而當(dāng)今的高性能計(jì)算機(jī)系統(tǒng)是“多指令流一多數(shù)據(jù)流”，其在運(yùn)行中的并行、存儲(chǔ)和通信等還是由用戶來人工處理，所以“不好用”的問題依然存在，“效率低”的問題由于并行臺(tái)數(shù)激增而更加嚴(yán)重、更加突出了。本書一方面借助于“單指令流一多數(shù)據(jù)流”巨型機(jī)的歷史經(jīng)驗(yàn)，有助于尋找“多指令流一多數(shù)據(jù)流”高性能計(jì)算機(jī)系統(tǒng)“不好用”的問題的解決方法；另一方面通過串行算法并行化的基本方法的介紹，希望有助于讀者獨(dú)立處理各種實(shí)際問題的并行化，進(jìn)而有效地提高計(jì)算效率。借本書出版介紹一下“為什么研究串行算法并行化”，和回答一下一些研究生提問的問題：“如何尋找科研課題”。一、為什么研究串行算法并行化為什么研究串行算法并行化呢？這要從我們接受億次機(jī)設(shè)計(jì)任務(wù)說起。工973年3月中國科學(xué)院計(jì)算所老所長閻沛霖帶我到國防科工委錢學(xué)森那里接受億次機(jī)設(shè)計(jì)任務(wù)開始，兩個(gè)月后，也就是1973年5月我們提出了可行的解決方案，并正式承擔(dān)了億次巨型機(jī)設(shè)計(jì)任務(wù)及其模型機(jī)——中國第一臺(tái)向量計(jì)算機(jī)757的研制任務(wù)。

內(nèi)容概要

　　《串行算法并行化基礎(chǔ)》第1章首先介紹這些有關(guān)串行算法并行化基本概念。并行計(jì)算是在一定的并行計(jì)算系統(tǒng)的類型上實(shí)現(xiàn)的，所以第2章介紹一些基本并行計(jì)算系統(tǒng)類型。多指令流多數(shù)據(jù)流巨型機(jī)是當(dāng)今高性能計(jì)算機(jī)系統(tǒng)的主流，許多大部頭的書都有詳細(xì)論述，本專著就不重復(fù)。單指令流多數(shù)據(jù)流巨型機(jī)是20世紀(jì)60年代末到80年代并行計(jì)算的高性能計(jì)算機(jī)系統(tǒng)的主流，其中許多設(shè)計(jì)思路在當(dāng)今仍然不失其價(jià)值。它們很容易使用的原因是對(duì)應(yīng)的并行計(jì)算模式可以規(guī)范到十分自然的向量運(yùn)算形式，即有一個(gè)理想的描述語言：向量語言。第3章就介紹一種向量語言。多指令流多數(shù)據(jù)流巨型機(jī)的并行計(jì)算模式目前難于規(guī)范到十分自然的運(yùn)算形式，也就是尚不存在一個(gè)理想的描述語言。通過向量語言的了解，或許有助于今后多指令流多數(shù)據(jù)流高性能計(jì)算機(jī)系統(tǒng)理想的描述語言的誕生。第4章介紹串行算法并行化的各種類型。第5章到第7章介紹具體的、典型的串行算法的并行化，包括兩路歸并、多路歸并、排序和廣義一階遞推。最后一章（第8章）介紹一類廣函數(shù)一一縱橫矩陣加工廣數(shù)?！　∫氩⑿惺菫榱颂岣哂?jì)算速度，到底能不能有效提高計(jì)算速度？如何度量計(jì)算速度的提高及其有效性？這些需要通過一些基本概念來刻畫。

作者簡介

高慶獅，1957年畢業(yè)于北京大學(xué)數(shù)學(xué)力學(xué)系。歷任中國科學(xué)院計(jì)算技術(shù)研究所研究員、中科院技術(shù)科學(xué)部委員。擅長巨型電子計(jì)算機(jī)總體功能設(shè)計(jì)、并行算法和人工智能。完成了我國第一臺(tái)晶體管大型電子計(jì)算機(jī)的功能總體設(shè)計(jì)和邏輯設(shè)計(jì)。是我國自行設(shè)計(jì)的第一臺(tái)電子管大型計(jì)算機(jī)的體系功能設(shè)計(jì)和邏輯設(shè)計(jì)負(fù)責(zé)人之一。負(fù)責(zé)完成中國第一臺(tái)每秒十萬鎰以上的晶體管大型計(jì)算機(jī)的體系功能設(shè)計(jì)。1973年提出縱橫加工流水線向量機(jī)設(shè)計(jì)思想，領(lǐng)導(dǎo)完成了我國第一臺(tái)千萬次大型向量計(jì)算機(jī)的系統(tǒng)功能設(shè)計(jì)。著有《向量巨型機(jī)》等。

書籍目錄

第0章 緒論0.1 計(jì)算科學(xué)0.2 為什么要并行計(jì)算0.3 巨型機(jī)、高性能計(jì)算機(jī)本質(zhì)特征：并行計(jì)算0.4 巨型機(jī)、高性能計(jì)算機(jī)基本矛盾：臺(tái)數(shù)與計(jì)算效率的矛盾0.5 并行運(yùn)算和并行數(shù)據(jù)傳送0.6 并行執(zhí)行方式和重疊執(zhí)行方式0.7 并行算法與串行算法并行化0.8 巨型機(jī)、高性能計(jì)算機(jī)的關(guān)鍵技術(shù)0.9 數(shù)據(jù)相關(guān)和控制相關(guān)第1章 串行算法并行化的基本概念1.1 題目的規(guī)模與計(jì)算工作量N1.2 題目的計(jì)算時(shí)間T1.3 題目最快串行計(jì)算算法C01.4 題目在并行計(jì)算模型M（S）下并行計(jì)算算法B1.5 題目在M（S）下并行計(jì)算算法B的計(jì)算速度：Vb，M（s）（N）1.6 在并行計(jì)算模型M（S）下題目并行計(jì)算算法B的加速比1.7 在并行計(jì)算模型M（S）下題目并行計(jì)算算法B的效率1.8 并行算法B的計(jì)算復(fù)雜性1.9 常數(shù)效率并行算法1.10 在某些討論中的算法分類1.11 并行計(jì)算臺(tái)數(shù)S對(duì)并行計(jì)算速度的影響及串行算法并行化的意義第2章 執(zhí)行并行計(jì)算算法的并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型2.1 并行算法實(shí)現(xiàn)的兩要素之一：并行傳送2.2 單指令流一單數(shù)據(jù)流（SIMD）計(jì)算機(jī)2.3 SIMD二維陣列機(jī)2.4 流水線向量機(jī)2.5 第二代巨型機(jī)：縱橫加工（分段處理）流水線向量機(jī)2.6 細(xì)胞結(jié)構(gòu)化虛共存縱橫加工向量機(jī)2.7 多維立方體機(jī)2.8 多指令流一多數(shù)據(jù)流系統(tǒng)MIMD2.9 內(nèi)部互聯(lián)網(wǎng)絡(luò)2.10 通用或?qū)Ｓ糜?jì)算網(wǎng)絡(luò)2.11 PRAM并行隨機(jī)訪問計(jì)算機(jī)2.12 可變總線結(jié)構(gòu)2.13 素?cái)?shù)存儲(chǔ)系統(tǒng)2.14 分段線性變換存儲(chǔ)系統(tǒng)第3章 向量語言3.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)3.2 向量基本運(yùn)算3.3 向量或者數(shù)組中的向量3.4 可以用硬件實(shí)現(xiàn)的控制向量3.5 變長向量運(yùn)算3.6 向量語言的擴(kuò)充3.7 向量高級(jí)語言第4章 串行算法并行化方法綜述與比較4.1 串行算法并行化之一：多分法方法4.2 串行算法并行化之二：倍增法4.3 串行算法并行化之三：縱橫加工法4.4 串行算法并行化效率比較4.5 串行算法并行化之四：利用軟件、硬件和軟件硬件結(jié)合的優(yōu)化方法4.6 串行算法并行化之五：利用硬件直接實(shí)現(xiàn)的控制向量一第5章 兩路歸并與分類串行算法并行化5.1 歸并與排序的快速串行算法5.2 歸并基本定義與定理5.3 K E Batcher的Odd-even并行歸并網(wǎng)絡(luò)5.4 根據(jù)歸并基本定理所構(gòu)造的快速并行歸并算法5.5 K E Batcher的Bitonic歸并算法5.6 利用并行歸并來實(shí)現(xiàn)并行排序5.7 歸并與排序串行算法并行化的OPTIMAL并行算法之一：縱橫并行歸并算法5.8 歸并與分類串行算法并行化的OPTIMAL并行算法之二：k-維并行歸并算法5.9 在理論模型上的排序第6章 多路歸并串行算法并行化第7章 一類一階遞推串行算法并行化第8章 一類廣函數(shù)：縱橫矩加工廣函數(shù)附錄 （m,N）選擇問題的縱橫并行算法例子參考文獻(xiàn)

章節(jié)摘錄

插圖：2.6.2 虛共存的提出由于器件迅速發(fā)展，不僅使得通過擴(kuò)大臺(tái)數(shù)解決某些類型大型計(jì)算問題的實(shí)現(xiàn)性不斷增加，而且也使得合理經(jīng)濟(jì)選擇臺(tái)數(shù)不斷增加。對(duì)集中存儲(chǔ)的向量機(jī)而言，擴(kuò)大臺(tái)數(shù)的主要困難是運(yùn)算細(xì)胞單元與公共存儲(chǔ)系統(tǒng)之間的數(shù)據(jù)傳輸，這是瓶子口。因此，要擴(kuò)大運(yùn)算并行臺(tái)數(shù)，最方便的方法是分散存儲(chǔ)。存儲(chǔ)系統(tǒng)分散到各個(gè)細(xì)胞單元，這就是通常的陣列機(jī)結(jié)構(gòu)。這樣做不僅便于擴(kuò)大并行臺(tái)數(shù)，而且還有利于適應(yīng)超大規(guī)模集成電路的發(fā)展，所以說，從物理結(jié)構(gòu)的角度，希望采用分散存儲(chǔ)的陣列機(jī)結(jié)構(gòu)。但是，通常的陣列機(jī)，程序編制比較困難，不僅要考慮數(shù)據(jù)從哪個(gè)細(xì)胞單元中取出，需要在細(xì)胞單元之間作怎么樣的移動(dòng)，而且還要考慮如何安排使得這種移動(dòng)最少。因此，可以說從使用的角度，希望使用具有集中統(tǒng)一的存儲(chǔ)系統(tǒng)的向量機(jī)，能夠使用高級(jí)語言編制程序，并能在一個(gè)統(tǒng)一的存儲(chǔ)空間中編制程序，而不考慮哪個(gè)分量在哪個(gè)細(xì)胞單元的存儲(chǔ)器中。能否設(shè)計(jì)一個(gè)計(jì)算系統(tǒng)，使其既具有陣列機(jī)便于擴(kuò)大臺(tái)數(shù)和適于超大規(guī)模集成電路的發(fā)展的優(yōu)點(diǎn)，又具有向量機(jī)便于使用高級(jí)向量語言和可以在一個(gè)統(tǒng)一的存儲(chǔ)空間編制程序的優(yōu)點(diǎn)，回答是肯定的。這就是說，可以設(shè)計(jì)一個(gè)計(jì)算機(jī)系統(tǒng)，它同時(shí)具有陣列機(jī)和向量機(jī)的優(yōu)點(diǎn)，而同時(shí)又克服了陣列機(jī)和向量機(jī)的缺點(diǎn)。單指令流一多數(shù)據(jù)流虛共存細(xì)胞結(jié)構(gòu)縱橫加工向量機(jī)方案，給這個(gè)肯定的回答一個(gè)構(gòu)造性的證明。具體請參考文獻(xiàn)（高慶獅1979）。2.6.3 單指令流一多指令流混合的向量語言中的函數(shù)向量在單指令流一多指令流混合的向量語言中“函數(shù)向量”的每一個(gè)分量可以是不同的標(biāo)量函數(shù)。在細(xì)胞結(jié)構(gòu)化虛共存縱橫加工向量機(jī)中，各個(gè)不同的標(biāo)量函數(shù)分量是通過多指令流的各個(gè)不同的指令流來實(shí)現(xiàn)（參看3.6 節(jié)）。進(jìn)一步研究請參考文獻(xiàn)（高慶獅1979），這里從略。

編輯推薦

《串行算法并行化基礎(chǔ)》由科學(xué)出版社出版。

圖書封面

圖書標(biāo)簽Tags

無

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

---

    串行算法并行化基礎(chǔ) PDF格式下載

---