本書是*本并行計算領(lǐng)域中,注意力完全集中在并行數(shù)據(jù)結(jié)構(gòu)、算法、軟件工具及數(shù)據(jù)科學中具體應用的書。書中的例子不僅有經(jīng)典的n 個樣本,p 個變量的矩陣形式,還有時間序列、網(wǎng)絡圖模型,以及各種其他的在數(shù)據(jù)科學中常見的結(jié)構(gòu)。本書同時也討論了適用于多種硬件、多種編程語言的的軟件包。特點關(guān)注數(shù)據(jù)科學中的應用,包括統(tǒng)計學、數(shù)據(jù)挖掘和機器學習。討論了數(shù)據(jù)科學中的常見數(shù)據(jù)結(jié)構(gòu),如網(wǎng)絡圖模型。通篇強調(diào)了普遍的原理,如避免降低并行程序速度的因素。覆蓋了主流的計算平臺:多核、集群以及圖像處理單元(GPU)。解釋了 Thrust 包如何降低多核機器和GPU編程的難度,并使得同一份代碼能夠在不同的平臺上工作。在作者網(wǎng)站上提供了樣例代碼。
感謝你對本書感興趣。我很享受寫書的過程,也希望這本書對你非常有用。為達此目的,這里有幾點事情我希望說清楚。本書目標:我很希望這本書能充分體現(xiàn)它標題的含義數(shù)據(jù)科學中的并行計算。和我所知道的其他并行計算的書籍不同,這本書里你不會碰到任何一個求解偏微分方程或其他物理學上的應用。這本書真的是為了數(shù)據(jù)科學所寫無論你怎樣定義數(shù)據(jù)科學,是統(tǒng)計學、數(shù)據(jù)挖掘、機器學習、模式識別、數(shù)據(jù)分析或其他的內(nèi)容。這不僅僅意味著書里的實例包括了從數(shù)據(jù)科學領(lǐng)域中選取的應用,這也意味著能夠反映這一主題的數(shù)據(jù)結(jié)構(gòu)、算法和其他內(nèi)容。從經(jīng)典的n 個觀測,p 個變量 的矩陣形式,到時間序列,到網(wǎng)絡圖模型和其他數(shù)據(jù)科學中常見的結(jié)構(gòu)都會囊括其中。本書包含了大量實例,以用于強調(diào)普遍的原理。因此,在第1 章介紹了入門的代碼實例后(沒有配套的實例,這些普遍的原理也就沒有任何意義),我決定在第2 章里解釋可以影響并行計算速度的一般因素,而不是集中介紹如何寫并行代碼。這是一個至關(guān)重要的章節(jié),在后續(xù)的章節(jié)中會經(jīng)常提到它。事實上,你可以把整本書看成如何解決第2 章開頭所描述的那個可憐的家伙的困境:這里有一個很常見的情景:一個分析師拿到了一臺嶄新的多核機器,這臺機器能做各種神奇的事情。帶著激動的心情,他在這臺新機器上寫代碼求解他最喜歡的大規(guī)模的問題,卻發(fā)現(xiàn)并行版本的運行速度比串行的還慢。太令人失望了!現(xiàn)在讓我來看看究竟什么因素導致了這種情形……本書標題里的計算一詞反映了本書的重點真的是在計算上。這和諸如以Hadoop 為代表的分布式文件存儲等的并行數(shù)據(jù)處理不同,盡管我還是為相關(guān)話題專門寫了一個章節(jié)。本書主要涵蓋的計算平臺是多核平臺、集群和GPU。另外,對Thrust 也有相當程度的介紹。Thrust 極大地簡化了在多核機器和GPU 上的編程任務,并且同樣的代碼在兩種平臺上都可以運行。我相信讀者會發(fā)現(xiàn)這部分材料非常有價值。需要指出一點,這本書不是一本用戶手冊。盡管書中使用了諸如R 的parallel和Rmpi 擴展包、OpenMP、CUDA 等特定工具,但這么做僅僅是為了讓問題具體化。本書會給讀者帶來有關(guān)這些工具的非常扎實的入門介紹,但不會提供諸如不同函數(shù)的參數(shù)、環(huán)境選項等內(nèi)容。本書的目的是,希望讀者閱讀完本書后,為進一步學習這些工具打下良好基礎(chǔ),更重要的是,讀者今后可以使用多種語言編寫高效的并行代碼,無論是Python、Julia,還是任何其他語言。必要的背景知識:如果你認為你已經(jīng)可以相對熟練地使用R,那本書的大多數(shù)內(nèi)容你應該都可以讀懂。在一些章節(jié)里,我們需要使用C/C ,如果你想仔細閱讀學習相關(guān)章節(jié),需要具備相關(guān)的背景知識。然而,即使你不怎么了解C/C ,你也應該會發(fā)現(xiàn)這些章節(jié)很容易讀懂,并且相當有價值。附錄里包括了針對C 程序員的R 簡介和針對R 用戶的C 語言簡介。你需要熟悉基礎(chǔ)的矩陣運算,主要是相乘和相加。有時我們也會使用一些更高級的運算,比如求逆(以及與之相關(guān)的QR 分解)和對角化。這些內(nèi)容在附錄A 中有涉及。機器設(shè)備:除了特別說明的地方,本書中所有的計時實例都運行在一臺16 核允許兩個超線程的Ubuntu 機器上。我一般使用2 到24 個核,這應該和多數(shù)讀者可以使用的平臺類似。希望讀者可以使用4 到16 核的多核系統(tǒng),或者一個有幾十個節(jié)點的集群。但即使你只有一個雙核機器,應該仍會發(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 博士出生于洛杉磯,在東洛杉磯和圣蓋博谷兩個地方長大。他在加州大學洛杉磯分校獲得了純粹數(shù)學的博士學位,學術(shù)研究方向為概率論和統(tǒng)計。他在計算機科學和統(tǒng)計學方向發(fā)表了大量論文,現(xiàn)在的研究方向是并行處理、統(tǒng)計計算和回歸方法。他也是Journal of Statistical Software 的編委之一。Matloff 教授曾是國際信息處理聯(lián)合會11.3 工作組的成員,該組織是聯(lián)合國教科文組織(UNESCO)下設(shè)的一個數(shù)據(jù)庫軟件安全國際委員會。他也是加州大學戴維斯分校統(tǒng)計系的創(chuàng)始人之一,并參與了該校計算機科學系的建立。他在戴維斯分校被授予了杰出教學獎和杰出公眾服務獎。
第1章 R語言中的并行處理入門1
1.1 反復出現(xiàn)的主題:良好并行所具有的標準. . . . . . . . . . . . 1
1.2 關(guān)于機器. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 2
1.3 反復出現(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)絡基礎(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 易并行的應用. . . . . . . . . . . . . . . . . . . . . . . . . 29
第3章 并行循環(huán)調(diào)度的準則31
3.1 循環(huán)調(diào)度的通用記法. . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 snow 中的分塊. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 關(guān)于代碼復雜度. . . . . . . . . . . . . . . . . . . . . . . . . . . 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)度方案:隨機任務置換. . . . . . . . . . . . . . . . . . 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