串行算法并行化基礎（簡體書）

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

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