串行算法并行化基礎

前言

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

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

《串行算法并行化基礎》由科學出版社出版。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    串行算法并行化基礎 PDF格式下載

---