基於MPI的大數據高性能計算導論（簡體書）

本書使用MPI標準介紹了數據科學中的高性能計算，幫助讀者瞭解分布式存儲模型中的並行編程的知識。全書分為兩部分，第一部分（第1～6章）基於消息傳遞接口介紹高性能計算，內容包括：阻塞與非阻塞的點對點通信、死鎖、全域通信函數（廣播、散播等）、協同計算（歸約）的基本概念；互聯網絡的拓撲結構（環、環面和超立方體）以及相應的全域通信程序；基於分布式內存的並行排序及其實現，涵蓋相關並行線性代數知識；MapReduce模型。第二部分（第7～11章）介紹計算機集群中的高性能數據分析，內容包括：數據聚類技術（平面劃分聚類、層次聚類）；基於k-NN的有監督分類；核心集以及相關降維技術；圖算法（稠密子圖、圖同構檢測）。每章章末附有各種難度的練習和參考文獻，可供讀者進行自測和深入學習。本書適合作為“高性能計算”相關課程的本科生教材。

目錄
譯者序
前言
致謝
第一部分基於消息傳遞接口的高性能計算
第1章走進高性能計算
1.1什麼是高性能計算
1.2為什麼我們需要HPC
1.3大數據：四個特性（數據量、多樣性、生成速度、價值）
1.4並行編程範式：MPI和MapReduce
1.5粒度：細粒度並行與粗粒度並行
1.6超級計算架構：內存和網絡
1.7加速比
1.7.1擴展性和等效率分析
1.7.2Amdahl定律：描述數據規模固定時漸近加速比的變化趨勢
1.7.3Gustafson定律：可擴展的加速比，隨著資源的增加不斷擴大數據量
1.7.4在串行計算機上模擬並行機
1.7.5大數據和並行輸入/輸出
1.8關於分布式系統的八個常見誤區
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併發性：局部計算可以與通信重疊執行
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環形拓撲上利用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兩個重要概念：靜態與動態網絡，以及邏輯與物理網絡
3.2互聯網絡：圖建模
3.3一些描述拓撲結構的屬性
3.3.1度和直徑
3.3.2連通性和對分
3.3.3一個好的網絡拓撲結構的標準
3.4常見的拓撲結構：簡單的靜態網絡
3.4.1完全圖：團
3.4.2星形圖
3.4.3環和帶弦環
3.4.4網（網格）與環面簇（環面的集合）
3.4.5三維立方體與循環連接立方體
3.4.6樹與胖樹
3.5超立方體拓撲結構以及使用格雷碼進行節點標識
3.5.1超立方體的遞歸構造
3.5.2使用格雷碼對超立方體節點編號
3.5.3使用C++生成格雷碼
3.5.4格雷碼和二進制碼的相互轉換
3.5.5圖的笛卡兒乘積
3.6一些拓撲結構上的通信算法
3.6.1有向環上的通信原語
3.6.2超立方體上的廣播：樹狀通信
3.7將（邏輯）拓撲結構嵌入到其他（物理）拓撲結構中
3.8複雜規則拓撲結構
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有向環拓撲上的矩陣向量乘積
5.3網格上的矩陣乘法：外積算法
5.4二維環面拓撲上的矩陣乘積
5.4.1Cannon算法
5.4.2Fox算法：廣播相乘循環移位矩陣乘積
5.4.3Snyder算法：在對角線上進行本地乘積累加
5.4.4Cannon、Fox和Snyder算法的比較
5.5注釋和參考
5.6總結
5.7練習
參考文獻
第6章MapReduce範式
6.1快速處理大數據的挑戰
6.2MapReduce的基本原理
6.2.1map和reduce過程
6.2.2歷史視角：函數式編程語言中的map和reduce
6.3數據類型和MapReduce機制
6.4MapReduce在C ++中的完整示例
6.5啟動MapReduce作業和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均值優化問題的複雜性和可計算性
7.3Lloyd批量k均值局部啟發式方法
7.4基於全域啟發式的k均值初始化方法
7.4.1基於隨機種子的初始化方法
7.4.2全域k均值：最佳貪心初始化
7.4.3kmeans ++：一種簡單的概率保證的初始化方法
7.5k均值向量量化中的應用
7.5.1向量量化
7.5.2Lloyd的局部最小值和穩定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總結