基于MPI的大數據高性能計算導論

目錄
譯者序
前言
致謝
部分基于消息傳遞接口的高性能計算
第1章走進高性能計算
1.1什么是高性能計算
1.2為什么我們需要HPC
1.3大數據：四個特性（數據量、多樣性、生成速度、價值）
1.4并行編程范式：MPI和MapReduce
1.5粒度：細粒度并行與粗粒度并行
1.6超級計算架構：內存和網絡
1.7加速比
1.7.1擴展性和等效率分析
1.7.2Amdahl定律：描述數據規(guī)模固定時漸近加速比的變化趨勢
1.7.3Gustafson定律：可擴展的加速比，隨著資源的增加不斷擴大數據量
1.7.4在串行計算機上模擬并行機
1.7.5大數據和并行輸入/輸出
1.8關于分布式系統(tǒng)的八個常見誤區(qū)
1.9注釋和參考
1.10總結
1.11練習
參考文獻
第2章MPI簡介：消息傳遞接口
2.1基于MPI的并行程序設計：基于消息通信
2.2并行編程模型、線程和進程
2.3進程之間的全局通信
2.3.1四個基本的MPI原語：廣播、收集、歸約和全交換
2.3.2阻塞與非阻塞和同步與異步通信
2.3.3阻塞通信產生的死鎖
2.3.4并發(fā)性：局部計算可以與通信重疊執(zhí)行
2.3.5單向與雙向通信
2.3.6MPI中的全局計算：歸約和并行前綴（掃描）
2.3.7采用通信器定義通信組
2.4同步屏障：進程的交匯點
2.4.1MPI中的一個同步示例：測量運行時間
2.4.2整體同步并行計算模型
2.5開始使用MPI：使用OpenMPI
2.5.1用MPI C++編寫“Hello World”程序
2.5.2用C綁定進行MPI編程
2.5.3通過C++ Boost使用MPI
2.6通過OpenMP使用MPI
2.7MPI中的主要原語
2.7.1廣播、散播、收集、歸約和全歸約的MPI語法
2.7.2其余混雜的MPI原語
2.8環(huán)形拓撲上利用MPI進行的通信
2.9MPI程序示例及其加速比分析
2.9.1MPI中的矩陣向量積
2.9.2MPI歸約操作示例：計算數組的階乘和小值
2.9.3MonteCarlo隨機積分算法估算π
2.9.4MonteCarlo隨機積分算法估算分子體積
2.10注釋和參考
2.11總結
2.12練習
參考文獻
第3章互聯網絡的拓撲結構
3.1兩個重要概念：靜態(tài)與動態(tài)網絡，以及邏輯與物理網絡
3.2互聯網絡：圖建模
3.3一些描述拓撲結構的屬性
3.3.1度和直徑
3.3.2連通性和對分
3.3.3一個好的網絡拓撲結構的標準
3.4常見的拓撲結構：簡單的靜態(tài)網絡
3.4.1完全圖：團
3.4.2星形圖
3.4.3環(huán)和帶弦環(huán)
3.4.4網（網格）與環(huán)面簇（環(huán)面的集合）
3.4.5三維立方體與循環(huán)連接立方體
3.4.6樹與胖樹
3.5超立方體拓撲結構以及使用格雷碼進行節(jié)點標識
3.5.1超立方體的遞歸構造
3.5.2使用格雷碼對超立方體節(jié)點編號
3.5.3使用C++生成格雷碼
3.5.4格雷碼和二進制碼的相互轉換
3.5.5圖的笛卡兒乘積
3.6一些拓撲結構上的通信算法
3.6.1有向環(huán)上的通信原語
3.6.2超立方體上的廣播：樹狀通信
3.7將（邏輯）拓撲結構嵌入到其他（物理）拓撲結構中
3.8復雜規(guī)則拓撲結構
3.9芯片上的互聯網絡
3.10注釋和參考
3.11總結
參考文獻
第4章并行排序
4.1串行排序快速回顧
4.1.1主要的串行排序算法
4.1.2排序的復雜性：下界
4.2通過合并列表實現并行排序
4.3利用秩實現并行排序
4.4并行快速排序
4.5超快速排序
4.6正則采樣并行排序
4.7基于網格的排序：ShearSort
4.8使用比較網絡排序：奇偶排序
4.9使用比較網絡合并有序列表
4.10雙調歸并排序
4.11注釋和參考
4.12總結
4.13練習
參考文獻
第5章并行線性代數
5.1分布式線性代數
5.1.1數據科學中的線性代數
5.1.2經典線性代數
5.1.3矩陣向量乘法：y=Ax
5.1.4并行數據模式
5.2有向環(huán)拓撲上的矩陣向量乘積
5.3網格上的矩陣乘法：外積算法
5.4二維環(huán)面拓撲上的矩陣乘積
5.4.1Cannon算法
5.4.2Fox算法：廣播相乘循環(huán)移位矩陣乘積
5.4.3Snyder算法：在對角線上進行本地乘積累加
5.4.4Cannon、Fox和Snyder算法的比較
5.5注釋和參考
5.6總結
5.7練習
參考文獻
第6章MapReduce范式
6.1快速處理大數據的挑戰(zhàn)
6.2MapReduce的基本原理
6.2.1map和reduce過程
6.2.2歷史視角：函數式編程語言中的map和reduce
6.3數據類型和MapReduce機制
6.4MapReduce在C ++中的完整示例
6.5啟動MapReduce作業(yè)和MapReduce架構概述
6.6基于MRMPI庫在MPI中使用MapReduce
6.7注釋和參考
6.8總結
參考文獻
第二部分面向數據科學的高性能計算
第7章基于k均值的劃分聚類
7.1探索性數據分析與聚類
7.1.1硬聚類：劃分數據集
7.1.2成本函數和模型聚類
7.2k均值目標函數
7.2.1重寫k均值成本函數以對聚類效果進行雙重解釋：聚類簇內數據或分離簇間數據
7.2.2k均值優(yōu)化問題的復雜性和可計算性
7.3Lloyd批量k均值局部啟發(fā)式方法
7.4基于全局啟發(fā)式的k均值初始化方法
7.4.1基于隨機種子的初始化方法
7.4.2全局k均值：貪心初始化
7.4.3kmeans ++：一種簡單的概率保證的初始化方法
7.5k均值向量量化中的應用
7.5.1向量量化
7.5.2Lloyd的局部小值和穩(wěn)定Voronoi劃分
7.6k均值的物理解釋：慣性分解
7.7k均值中k的選擇：模型選擇
7.7.1基于肘部法則的模型選擇
7.7.2模型選擇：用k解釋方差減少
7.8集群上的并行k均值聚類
7.9評估聚類劃分
7.9.1蘭德指數
7.9.2歸一化互信息
7.10注釋和參考
7.11總結