本書是*本并行計算領(lǐng)域中,注意力完全集中在并行數(shù)據(jù)結(jié)構(gòu)、算法、軟件工具及數(shù)據(jù)科學(xué)中具體應(yīng)用的書。書中的例子不僅有經(jīng)典的n 個樣本,p 個變量的矩陣形式,還有時間序列、網(wǎng)絡(luò)圖模型,以及各種其他的在數(shù)據(jù)科學(xué)中常見的結(jié)構(gòu)。本書同時也討論了適用于多種硬件、多種編程語言的的軟件包。特點關(guān)注數(shù)據(jù)科學(xué)中的應(yīng)用,包括統(tǒng)計學(xué)、數(shù)據(jù)挖掘和機器學(xué)習(xí)。討論了數(shù)據(jù)科學(xué)中的常見數(shù)據(jù)結(jié)構(gòu),如網(wǎng)絡(luò)圖模型。通篇強調(diào)了普遍的原理,如避免降低并行程序速度的因素。覆蓋了主流的計算平臺:多核、集群以及圖像處理單元(GPU)。解釋了 Thrust 包如何降低多核機器和GPU編程的難度,并使得同一份代碼能夠在不同的平臺上工作。在作者網(wǎng)站上提供了樣例代碼。
感謝你對本書感興趣。我很享受寫書的過程,也希望這本書對你非常有用。為達此目的,這里有幾點事情我希望說清楚。本書目標:我很希望這本書能充分體現(xiàn)它標題的含義數(shù)據(jù)科學(xué)中的并行計算。和我所知道的其他并行計算的書籍不同,這本書里你不會碰到任何一個求解偏微分方程或其他物理學(xué)上的應(yīng)用。這本書真的是為了數(shù)據(jù)科學(xué)所寫無論你怎樣定義數(shù)據(jù)科學(xué),是統(tǒng)計學(xué)、數(shù)據(jù)挖掘、機器學(xué)習(xí)、模式識別、數(shù)據(jù)分析或其他的內(nèi)容。這不僅僅意味著書里的實例包括了從數(shù)據(jù)科學(xué)領(lǐng)域中選取的應(yīng)用,這也意味著能夠反映這一主題的數(shù)據(jù)結(jié)構(gòu)、算法和其他內(nèi)容。從經(jīng)典的n 個觀測,p 個變量 的矩陣形式,到時間序列,到網(wǎng)絡(luò)圖模型和其他數(shù)據(jù)科學(xué)中常見的結(jié)構(gòu)都會囊括其中。本書包含了大量實例,以用于強調(diào)普遍的原理。因此,在第1 章介紹了入門的代碼實例后(沒有配套的實例,這些普遍的原理也就沒有任何意義),我決定在第2 章里解釋可以影響并行計算速度的一般因素,而不是集中介紹如何寫并行代碼。這是一個至關(guān)重要的章節(jié),在后續(xù)的章節(jié)中會經(jīng)常提到它。事實上,你可以把整本書看成如何解決第2 章開頭所描述的那個可憐的家伙的困境:這里有一個很常見的情景:一個分析師拿到了一臺嶄新的多核機器,這臺機器能做各種神奇的事情。帶著激動的心情,他在這臺新機器上寫代碼求解他最喜歡的大規(guī)模的問題,卻發(fā)現(xiàn)并行版本的運行速度比串行的還慢。太令人失望了!現(xiàn)在讓我來看看究竟什么因素導(dǎo)致了這種情形……本書標題里的計算一詞反映了本書的重點真的是在計算上。這和諸如以Hadoop 為代表的分布式文件存儲等的并行數(shù)據(jù)處理不同,盡管我還是為相關(guān)話題專門寫了一個章節(jié)。本書主要涵蓋的計算平臺是多核平臺、集群和GPU。另外,對Thrust 也有相當(dāng)程度的介紹。Thrust 極大地簡化了在多核機器和GPU 上的編程任務(wù),并且同樣的代碼在兩種平臺上都可以運行。我相信讀者會發(fā)現(xiàn)這部分材料非常有價值。需要指出一點,這本書不是一本用戶手冊。盡管書中使用了諸如R 的parallel和Rmpi 擴展包、OpenMP、CUDA 等特定工具,但這么做僅僅是為了讓問題具體化。本書會給讀者帶來有關(guān)這些工具的非常扎實的入門介紹,但不會提供諸如不同函數(shù)的參數(shù)、環(huán)境選項等內(nèi)容。本書的目的是,希望讀者閱讀完本書后,為進一步學(xué)習(xí)這些工具打下良好基礎(chǔ),更重要的是,讀者今后可以使用多種語言編寫高效的并行代碼,無論是Python、Julia,還是任何其他語言。必要的背景知識:如果你認為你已經(jīng)可以相對熟練地使用R,那本書的大多數(shù)內(nèi)容你應(yīng)該都可以讀懂。在一些章節(jié)里,我們需要使用C/C ,如果你想仔細閱讀學(xué)習(xí)相關(guān)章節(jié),需要具備相關(guān)的背景知識。然而,即使你不怎么了解C/C ,你也應(yīng)該會發(fā)現(xiàn)這些章節(jié)很容易讀懂,并且相當(dāng)有價值。附錄里包括了針對C 程序員的R 簡介和針對R 用戶的C 語言簡介。你需要熟悉基礎(chǔ)的矩陣運算,主要是相乘和相加。有時我們也會使用一些更高級的運算,比如求逆(以及與之相關(guān)的QR 分解)和對角化。這些內(nèi)容在附錄A 中有涉及。機器設(shè)備:除了特別說明的地方,本書中所有的計時實例都運行在一臺16 核允許兩個超線程的Ubuntu 機器上。我一般使用2 到24 個核,這應(yīng)該和多數(shù)讀者可以使用的平臺類似。希望讀者可以使用4 到16 核的多核系統(tǒng),或者一個有幾十個節(jié)點的集群。但即使你只有一個雙核機器,應(yīng)該仍會發(fā)現(xiàn)本書的材料非常有用。對于那些少數(shù)有幸可以使用擁有幾千個內(nèi)核的集群的讀者,書中的內(nèi)容仍然適用。依據(jù)本書中對這種系統(tǒng)的觀點,那個著名問題這可擴展嗎? 的答案一般是否定的。CRAN 擴展包和代碼:本書使用了我在CRAN,即R 的軟件貢獻庫(http://cran.r-project.org)上的幾個擴展包:Rdsm、partools 和matpow。本書的示例代碼都可以從作者的網(wǎng)站下載,http://heather.cs.ucdavis.edu/pardatasci.html。
作者簡介Matloff 博士出生于洛杉磯,在東洛杉磯和圣蓋博谷兩個地方長大。他在加州大學(xué)洛杉磯分校獲得了純粹數(shù)學(xué)的博士學(xué)位,學(xué)術(shù)研究方向為概率論和統(tǒng)計。他在計算機科學(xué)和統(tǒng)計學(xué)方向發(fā)表了大量論文,現(xiàn)在的研究方向是并行處理、統(tǒng)計計算和回歸方法。他也是Journal of Statistical Software 的編委之一。Matloff 教授曾是國際信息處理聯(lián)合會11.3 工作組的成員,該組織是聯(lián)合國教科文組織(UNESCO)下設(shè)的一個數(shù)據(jù)庫軟件安全國際委員會。他也是加州大學(xué)戴維斯分校統(tǒng)計系的創(chuàng)始人之一,并參與了該校計算機科學(xué)系的建立。他在戴維斯分校被授予了杰出教學(xué)獎和杰出公眾服務(wù)獎。
第1章 R語言中的并行處理入門1
1.1 反復(fù)出現(xiàn)的主題:良好并行所具有的標準. . . . . . . . . . . . 1
1.2 關(guān)于機器. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 2
1.3 反復(fù)出現(xiàn)的主題:不要把雞蛋放在一個籃子里. . . . . . . . . . 3
1.4 擴展示例:相互網(wǎng)頁外鏈. . . . . . . . . . . . . . . . . . . . . 3
第2章 我的程序為什么這么慢?:速度的障礙15
2.1 速度的障礙. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2 性能和硬件結(jié)構(gòu). . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 內(nèi)存的基礎(chǔ)知識. . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 網(wǎng)絡(luò)基礎(chǔ). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 20
2.5 延遲和帶寬. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.6 線程調(diào)度. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 26
2.7 多少個進程/線程? . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 示例:相互外鏈問題. . . . . . . . . . . . . . . . . . . . . . . . 27
2.9 大O標記法. . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.10 數(shù)據(jù)序列化. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.11 易并行的應(yīng)用. . . . . . . . . . . . . . . . . . . . . . . . . 29
第3章 并行循環(huán)調(diào)度的準則31
3.1 循環(huán)調(diào)度的通用記法. . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 snow 中的分塊. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 關(guān)于代碼復(fù)雜度. . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 示例:所有可能回歸. . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 partools 包. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.6 示例:所有可能回歸,改進版本. . . . . . . . . . . . . . . . . . 48
3.7 引入另一個工具:multicore . . . . . . . . . . . . . . . . . . . . 54
3.8 塊大小的問題. . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
3.9 示例:并行距離計算. . . . . . . . . . . . . . . . . . . . . . . . 62
3.10 foreach 包. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
3.11 跨度. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 71
3.12 另一種調(diào)度方案:隨機任務(wù)置換. . . . . . . . . . . . . . . . . . 71
3.13 調(diào)試snow 和multicore 的代碼. . . . . . . . . . . . . . . . . . 74
第4章 共享內(nèi)存范式:基于R 的簡單介紹76
第5章 共享內(nèi)存范式:C 語言層面112
第6章 共享內(nèi)存范式:GPU 157
第7章 Thrust 與Rth 176
第8章 消息傳遞范式186
第9章 MapReduce 計算204
第10章 并行排序和歸并214
第11章 并行前綴掃描227
第12章 并行矩陣運算244
第13章 原生統(tǒng)計方法:子集方法266
附錄A 回顧矩陣代數(shù)275