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