基于MPI的大數(shù)據(jù)高性能計算導論
定 價:59 元
叢書名:華章IT
- 作者:[法] 弗蘭克·尼爾森(Frank Nielsen)
- 出版時間:2018/7/1
- ISBN:9787111602149
- 出 版 社:機械工業(yè)出版社
- 中圖法分類:TP274
- 頁碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
本書使用MPI標準介紹了數(shù)據(jù)科學中的高性能計算,幫助讀者了解分布式存儲模型中的并行編程的知識。全書分為兩部分,*部分(第1~6章)基于消息傳遞接口介紹高性能計算,內(nèi)容包括:阻塞與非阻塞的點對點通信、死鎖、全局通信函數(shù)(廣播、散播等)、協(xié)同計算(歸約)的基本概念;互聯(lián)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)(環(huán)、環(huán)面和超立方體)以及相應(yīng)的全局通信程序;基于分布式內(nèi)存的并行排序及其實現(xiàn),涵蓋相關(guān)并行線性代數(shù)知識;MapReduce模型。第二部分(第7~11章)介紹計算機集群中的高性能數(shù)據(jù)分析,內(nèi)容包括:數(shù)據(jù)聚類技術(shù)(平面劃分聚類、層次聚類);基于k-NN的有監(jiān)督分類;核心集以及相關(guān)降維技術(shù);圖算法(稠密子圖、圖同構(gòu)檢測)。每章章末附有各種難度的練習和參考文獻,可供讀者進行自測和深入學習。本書適合作為“高性能計算”相關(guān)課程的本科生教材。
前言歡迎來到高性能計算的世界!歡迎來到高性能數(shù)據(jù)科學的世界!
在本書中,我們將介紹面向數(shù)據(jù)科學(Data Science,DS)的高性能計算(High Performance Computing,HPC)。因此,本書主要分為兩個部分:第一部分(前6章)涵蓋HPC的基本原理;第二部分(后5章)介紹了數(shù)據(jù)科學的基本知識,并展示了如何編寫面向基本串行算法的分布式程序,以應(yīng)對大規(guī)模數(shù)據(jù)集。當前,許多大規(guī)模數(shù)據(jù)集都是公開的,這些數(shù)據(jù)集中蘊含了豐富的信息,但是這些信息需要通過精心設(shè)計才能被提取出來。
我們主要區(qū)分兩種并行算法的設(shè)計方法:在單個共享內(nèi)存多核機器上使用多線程并行化算法;在分布式內(nèi)存集群系統(tǒng)上并行化算法。
一方面,當在共享內(nèi)存架構(gòu)(如智能手機、平板電腦,以及智能手表和其他物聯(lián)網(wǎng)設(shè)備)上設(shè)計并行化算法時,所有的硬件計算單元(核)位于同一芯片上,我們可以使用多線程來輕松地對視頻解碼、渲染等任務(wù)進行并行化。這種并行是細粒度的(finegrained),但它受到芯片上物理核數(shù)的限制(2015年高端智能手機通常只有8個核)。另一方面,集群系統(tǒng)(即分布式內(nèi)存架構(gòu))可以根據(jù)待處理的數(shù)據(jù)集規(guī)模來實時擴展資源。集群的構(gòu)建具有很大的靈活性,例如可以選擇異構(gòu)的計算機節(jié)點,然后確定最適合這些節(jié)點的互連拓撲結(jié)構(gòu)。這種并行是粗粒度的(coarsegrained),因為在集群中發(fā)生節(jié)點間通信之前,每個節(jié)點可以獨立地進行大量的本地計算。
本書側(cè)重于在分布式內(nèi)存系統(tǒng)上利用標準消息傳遞接口(Message Passing Interface,MPI)來設(shè)計并行算法。MPI是管理集群節(jié)點之間通信和全局協(xié)同計算的實際標準。目前存在多種MPI標準的供應(yīng)商實現(xiàn),它們可以與C、C++、Fortran、Python等多種編程語言綁定。我們選擇面向?qū)ο蟮恼Z言C++來實現(xiàn)數(shù)據(jù)科學中的算法,并使用和C語言綁定的OpenMPI應(yīng)用程序編程接口(Application Programming Interface,API)來編寫并行程序。
本書中兩部分內(nèi)容的簡要介紹如下。
第一部分:基于消息傳遞接口的高性能計算第1章首先簡單介紹了HPC世界,然后講解了Amdahl定律和Gustafson定律,這兩個定律刻畫了并行程序的理論最優(yōu)加速比和擴展加速比。
第2章講解了MPI的主要概念和編程接口:阻塞/非阻塞通信的概念、死鎖和多種全局通信函數(shù)(例如broadcast、scatter、gather、alltoall、reduce、parallel prefix等)。
第3章著重介紹了互聯(lián)網(wǎng)絡(luò)拓撲的作用。我們首先區(qū)分物理拓撲和虛擬拓撲(或稱為邏輯拓撲),并在設(shè)計并行算法的時候考慮不同網(wǎng)絡(luò)拓撲對性能的影響。特別講解了環(huán)形(包括優(yōu)化的流水線廣播)和超立方體形網(wǎng)絡(luò)拓撲上的通信過程,后者依賴于節(jié)點的特定編號,稱為格雷碼。
第4章講解了基于分布式內(nèi)存的主要的并行排序算法。首先對著名的快速排序算法(Quicksort)進行了簡單的并行化,然后介紹實際中廣泛使用的HyperQuicksort和PSRS(Parallel Sorting by Regular Sampling)算法。
第5章研究了一些矩陣相乘和向量相乘的算法,并簡要介紹了在環(huán)和環(huán)面(torus)的拓撲結(jié)構(gòu)中計算矩陣乘積的各種技術(shù)。
第6章介紹了一個比較熱門的并行編程范式,稱為MapReduce(通常與開源系統(tǒng)Hadoop一起使用)。 MapReduce可以通過兩個主要的用戶定義的函數(shù)(map和reduce)來構(gòu)建程序,然后部署到大量的網(wǎng)絡(luò)互連的計算機上來完成計算任務(wù)。 然而,MapReduce也是一個完整的框架,包括一個主從架構(gòu)。該主從架構(gòu)能夠處理各種硬件故障,或者當一些機器執(zhí)行得太慢時,將這些機器上的并行計算任務(wù)(作業(yè))重新發(fā)送到其他的機器上執(zhí)行。該章還講解了如何利用專門的名為MRMPI的軟件庫在MPI(MPI沒有容錯能力)中實現(xiàn)這些類型的MapReduce算法。
第二部分:面向數(shù)據(jù)科學的高性能計算這部分簡要介紹了數(shù)據(jù)科學,并進一步講解了如何使用MPI并行化數(shù)據(jù)科學中的算法。
首先介紹了兩個最基本的數(shù)據(jù)聚類技術(shù),分別是平面劃分聚類(第7章)和層次樹聚類(第8章)。聚類是探索性數(shù)據(jù)科學中一個非常重要的概念,用于發(fā)現(xiàn)數(shù)據(jù)集中的分類、同質(zhì)數(shù)據(jù)中的分組。
第9章介紹了基于k最近鄰規(guī)則(knearest neighbor)的有監(jiān)督分類,并和k均值(kmeans)聚類算法進行關(guān)聯(lián)。
第10章介紹了另一個計算科學中的新范式,允許人們在大型數(shù)據(jù)集(潛在的高維度)上解決優(yōu)化問題。這種新范式就是尋找核心集(coreset),這些核心集就是原數(shù)據(jù)集的子集,而且和原數(shù)據(jù)集相比具有良好的近似性。這種技術(shù)最近變得非常流行,能夠?qū)⒋髷?shù)據(jù)(big data)縮小到小數(shù)據(jù)(tiny data)!由于數(shù)據(jù)通常具有高維度特征,所以還簡要介紹了一種有效的線性降維技術(shù),其中講解了JohnsonLindenstrauss定理,并給出一個簡單的方法計算低失真嵌入,從而將數(shù)據(jù)從高維轉(zhuǎn)化為低維,并確保在規(guī)定的近似因子內(nèi)數(shù)據(jù)點之間的距離保持不變。有趣的是,嵌入的維度與原始外在維度無關(guān),而是依賴于數(shù)據(jù)集大小的對數(shù)和近似因子。
第11章涵蓋了一些圖(graph)算法。圖在社交網(wǎng)絡(luò)分析和其他應(yīng)用領(lǐng)域中是比較常見的。因此首先介紹一個順序啟發(fā)式方法和一個并行啟發(fā)式方法來查找圖的稠密子圖,該子圖近似于“最稠密”子圖。 然后介紹了在計算機集群上利用分支限界法來進行圖同構(gòu)檢測。圖同構(gòu)檢測是一個備受關(guān)注的問題,因為它的理論復(fù)雜度還沒有得到解決(盡管對于圖的某些特定子類存在一些多項式算法)。
每章最后會對該章的一些要點進行總結(jié)。請讀者瀏覽這些總結(jié),以便進行第一遍快速閱讀。在一些章節(jié)結(jié)束時會給出40多道練習題,這些練習標有各種難度,并允許讀者對練習所涵蓋內(nèi)容的理解程度進行自測。以星號開頭的部分可以先跳過,稍后再進行閱讀。
本書的主要目的是幫助讀者設(shè)計并行算法,然后利用C++和C語言綁定的MPI編寫程序?qū)崿F(xiàn)相應(yīng)的并行算法。第二個目的是讓讀者對高性能計算和數(shù)據(jù)科學有更深刻的了解,并希望更好地促進兩者之間的交叉。
本書是關(guān)于高性能計算和數(shù)據(jù)科學的入門教材,面向具有基本算法知識和編程能力的讀者。因此,本書不包含(也沒有提及)高性能計算和數(shù)據(jù)科學領(lǐng)域的高級概念。例如,任務(wù)調(diào)度問題和嵌套循環(huán)的自動并行化雖然在高性能計算中很重要,但是本書并沒有涉及。類似地,本書也省略了數(shù)據(jù)科學領(lǐng)域中的回歸技術(shù)和核心機器學習方法。
教輔資源本書的額外資源(包括超過35個用MPI/C++/R/Scilab/Gnuplot/Processing編寫的程序、幻燈片、相關(guān)鏈接和其他精彩內(nèi)容)可以通過網(wǎng)址https://wwwlixpolytechniquefr/nielsen/HPC4DS/獲取。
程序的源代碼可以在上述網(wǎng)址以下列方式獲取:
祝閱讀愉快!
Frank Nielsen2015年12月致謝非常感謝以下這些有才華的同事,他們給了我非常寶貴的反饋意見(姓名按隨機順序排列)并幫助我完善了本書:Claudiad Ambrosio, Ulysse Beaugnon, Annal Bonneton, JeanBaptiste Bordes, PatriceCalégari, Henri Casanova, Antoine DelignatLavaud, Amélie Héliou, Alice Héliou, Léo Liberti, Frédéric Magoulès, Gautier Marti, Sameh Mohamed, Franois Morain, Richard Nock, PierreLouis Poirion, Stéphane Redon, Thomas SibutPinote, Benjamin Smith, Antoine Soulé, Bogdan Tomchuk, Sonia Toubaline和 Frédéric Vivien。除了以上這些同事,我還與其他很多同事進行了討論,當你們讀到這句話時,希望你們能夠知道,從這些寶貴的交談中,我受益匪淺。我還要感謝所有巴黎綜合理工大學INF442課程的學生,感謝他們富有成效的意見和反饋,并且感謝巴黎綜合理工大學計算機科學學院(DIX)的支持。
弗蘭克•尼爾森(Frank Nielsen) 巴黎綜合理工學院教授,負責教授研究生計算機視覺和圖形學方面的課程以及本科生的算法和Java課程。他是Sony計算機科學實驗室研究員。
目錄
譯者序
前言
致謝
第一部分基于消息傳遞接口的高性能計算
第1章走進高性能計算
1.1什么是高性能計算
1.2為什么我們需要HPC
1.3大數(shù)據(jù):四個特性(數(shù)據(jù)量、多樣性、生成速度、價值)
1.4并行編程范式:MPI和MapReduce
1.5粒度:細粒度并行與粗粒度并行
1.6超級計算架構(gòu):內(nèi)存和網(wǎng)絡(luò)
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關(guān)于分布式系統(tǒng)的八個常見誤區(qū)
1.9注釋和參考
1.10總結(jié)
1.11練習
參考文獻
第2章MPI簡介:消息傳遞接口
2.1基于MPI的并行程序設(shè)計:基于消息通信
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.3MonteCarlo隨機積分算法估算π
2.9.4MonteCarlo隨機積分算法估算分子體積
2.10注釋和參考
2.11總結(jié)
2.12練習
參考文獻
第3章互聯(lián)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)
3.1兩個重要概念:靜態(tài)與動態(tài)網(wǎng)絡(luò),以及邏輯與物理網(wǎng)絡(luò)
3.2互聯(lián)網(wǎng)絡(luò):圖建模
3.3一些描述拓撲結(jié)構(gòu)的屬性
3.3.1度和直徑
3.3.2連通性和對分
3.3.3一個好的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的標準
3.4常見的拓撲結(jié)構(gòu):簡單的靜態(tài)網(wǎng)絡(luò)
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é)構(gòu)以及使用格雷碼進行節(jié)點標識
3.5.1超立方體的遞歸構(gòu)造
3.5.2使用格雷碼對超立方體節(jié)點編號
3.5.3使用C++生成格雷碼
3.5.4格雷碼和二進制碼的相互轉(zhuǎn)換
3.5.5圖的笛卡兒乘積
3.6一些拓撲結(jié)構(gòu)上的通信算法
3.6.1有向環(huán)上的通信原語
3.6.2超立方體上的廣播:樹狀通信
3.7將(邏輯)拓撲結(jié)構(gòu)嵌入到其他(物理)拓撲結(jié)構(gòu)中
3.8復(fù)雜規(guī)則拓撲結(jié)構(gòu)
3.9芯片上的互聯(lián)網(wǎng)絡(luò)
3.10注釋和參考
3.11總結(jié)
參考文獻
第4章并行排序
4.1串行排序快速回顧
4.1.1主要的串行排序算法
4.1.2排序的復(fù)雜性:下界
4.2通過合并列表實現(xiàn)并行排序
4.3利用秩實現(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練習
參考文獻
第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總結(jié)
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架構(gòu)概述
6.6基于MRMPI庫在MPI中使用MapReduce
6.7注釋和參考
6.8總結(jié)
參考文獻
第二部分面向數(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ù)以對聚類效果進行雙重解釋:聚類簇內(nèi)數(shù)據(jù)或分離簇間數(shù)據(jù)
7.2.2k均值優(yōu)化問題的復(fù)雜性和可計算性
7.3Lloyd批量k均值局部啟發(fā)式方法
7.4基于全局啟發(fā)式的k均值初始化方法
7.4.1基于隨機種子的初始化方法
7.4.2全局k均值:最佳貪心初始化
7.4.3kmeans ++:一種簡單的概率保證的初始化方法
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評估聚類劃分
7.9.1蘭德指數(shù)
7.9.2歸一化互信息
7.10注釋和參考
7.11總結(jié)