基于MPI的大數(shù)據(jù)高性能計算導論

目錄
譯者序
前言
致謝
部分基于消息傳遞接口的高性能計算
第1章走進高性能計算
1.1什么是高性能計算
1.2為什么我們需要HPC
1.3大數(shù)據(jù)：四個特性（數(shù)據(jù)量、多樣性、生成速度、價值）
1.4并行編程范式：MPI和MapReduce
1.5粒度：細粒度并行與粗粒度并行
1.6超級計算架構：內存和網(wǎng)絡
1.7加速比
1.7.1擴展性和等效率分析
1.7.2Amdahl定律：描述數(shù)據(jù)規(guī)模固定時漸近加速比的變化趨勢
1.7.3Gustafson定律：可擴展的加速比，隨著資源的增加不斷擴大數(shù)據(jù)量
1.7.4在串行計算機上模擬并行機
1.7.5大數(shù)據(jù)和并行輸入/輸出
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阻塞通信產(chǎn)生的死鎖
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歸約操作示例：計算數(shù)組的階乘和小值
2.9.3MonteCarlo隨機積分算法估算π
2.9.4MonteCarlo隨機積分算法估算分子體積
2.10注釋和參考
2.11總結
2.12練習
參考文獻
第3章互聯(lián)網(wǎng)絡的拓撲結構
3.1兩個重要概念：靜態(tài)與動態(tài)網(wǎng)絡，以及邏輯與物理網(wǎng)絡
3.2互聯(lián)網(wǎng)絡：圖建模
3.3一些描述拓撲結構的屬性
3.3.1度和直徑
3.3.2連通性和對分
3.3.3一個好的網(wǎng)絡拓撲結構的標準
3.4常見的拓撲結構：簡單的靜態(tài)網(wǎng)絡
3.4.1完全圖：團
3.4.2星形圖
3.4.3環(huán)和帶弦環(huán)
3.4.4網(wǎng)（網(wǎng)格）與環(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芯片上的互聯(lián)網(wǎng)絡
3.10注釋和參考
3.11總結
參考文獻
第4章并行排序
4.1串行排序快速回顧
4.1.1主要的串行排序算法
4.1.2排序的復雜性：下界
4.2通過合并列表實現(xiàn)并行排序
4.3利用秩實現(xiàn)并行排序
4.4并行快速排序
4.5超快速排序
4.6正則采樣并行排序
4.7基于網(wǎng)格的排序：ShearSort
4.8使用比較網(wǎng)絡排序：奇偶排序
4.9使用比較網(wǎng)絡合并有序列表
4.10雙調歸并排序
4.11注釋和參考
4.12總結
4.13練習
參考文獻
第5章并行線性代數(shù)
5.1分布式線性代數(shù)
5.1.1數(shù)據(jù)科學中的線性代數(shù)
5.1.2經(jīng)典線性代數(shù)
5.1.3矩陣向量乘法：y=Ax
5.1.4并行數(shù)據(jù)模式
5.2有向環(huán)拓撲上的矩陣向量乘積
5.3網(wǎng)格上的矩陣乘法：外積算法
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快速處理大數(shù)據(jù)的挑戰(zhàn)
6.2MapReduce的基本原理
6.2.1map和reduce過程
6.2.2歷史視角：函數(shù)式編程語言中的map和reduce
6.3數(shù)據(jù)類型和MapReduce機制
6.4MapReduce在C ++中的完整示例
6.5啟動MapReduce作業(yè)和MapReduce架構概述
6.6基于MRMPI庫在MPI中使用MapReduce
6.7注釋和參考
6.8總結
參考文獻
第二部分面向數(shù)據(jù)科學的高性能計算
第7章基于k均值的劃分聚類
7.1探索性數(shù)據(jù)分析與聚類
7.1.1硬聚類：劃分數(shù)據(jù)集
7.1.2成本函數(shù)和模型聚類
7.2k均值目標函數(shù)
7.2.1重寫k均值成本函數(shù)以對聚類效果進行雙重解釋：聚類簇內數(shù)據(jù)或分離簇間數(shù)據(jù)
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蘭德指數(shù)
7.9.2歸一化互信息
7.10注釋和參考
7.11總結