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

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