數據科學傢的並行計算必讀手冊

“……一本完整、易讀的並行計算入門——它適閤很多學科的研究人員和學生使用。這是一本‘必備’的參考書……”

——戴維•E•吉爾斯，維多利亞大學

“這本書我會既用來當參考書，又當教材。書中的例子生動，內容也使讀者直接從概念走嚮可用於工作的代碼。”

——邁剋爾•凱恩，耶魯大學

本書是第一本並行計算領域中，注意力完全集中在並行數據結構、算法、軟件工具及數據科學中具體應用的書。書中的例子不僅有經典的“n 個樣本，p 個變量”的矩陣形式，還有時間序列、網絡圖模型，以及各種其他的在數據科學中常見的結構。本書同時也討論瞭適用於多種硬件、多種編程語言的的軟件包。

特點

關注數據科學中的應用，包括統計學、數據挖掘和機器學習。

討論瞭數據科學中的常見數據結構，如網絡圖模型。

通篇強調瞭普遍的原理，如避免降低並行程序速度的因素。

覆蓋瞭主流的計算平颱：多核、集群以及圖像處理單元（GPU）。

解釋瞭 Thrust 包如何降低多核機器和GPU編程的難度，並使得同一份代碼能夠在不同的平颱上工作。

在作者網站上提供瞭樣例代碼。

譯者序

21 世紀的第二個十年，隨著計算能力的巨大提升和移動互聯網的迅猛發展，大數據時代拉開瞭它的帷幕。大數據時代的顯著特點就是數據量大，對數據處理的速度和時效提齣瞭苛刻的要求。

在傳統的串行計算下，多核的計算機/集群等隻有一個內核能夠進行有效的工作，這就造成瞭計算性能的浪費。並行計算概念的提齣，則解決瞭這個性能浪費的問題。它能夠協調多個內核共同計算，極大地提升瞭計算速度，從而滿足瞭大數據時代人們對高速處理數據的需求。

Norman Matloff 教授在加州大學戴維斯分校教授計算機科學，對計算機架構和算法瞭然於心。更值得一提的是，他還是該校統計係的創始人之一，不但教授本科的統計課程，還在統計係碩士和博士的考試委員會擔任多個職務。對於統計理論的熟悉，使得他在使用計算機編程處理統計問題的時候，更加得心應手。該書即是他在並行計算方嚮上多年經驗的總結。

本書不是一本並行計算的理論教材。該書彆齣心裁，使用實例手把手地教會讀者掌握並行計算的基本概念和操作。在提綱挈領地介紹瞭如何在R 中使用並行方法之後，作者帶領我們學習瞭多綫程和多進程，以及並行調度等方麵的知識和技能。隨後，作者用詳盡的篇幅講述瞭如何使用R、C++ 和CUDA分彆來進行共享內存範式編程和消息傳遞範式編程。本書在講述瞭當前流行的MapReduce 之後，又詳細講解瞭如何並行地實現串行計算下所對應的排序、掃描、矩陣乘法等經典算法。在本書的最後，作者講述瞭如何使用並行計算來進行統計。此外，本書的附錄中對綫性代數、R 和C 也做瞭簡明的介紹，方便不熟悉的讀者迅速入門。

值得一提的是，Matloff 教授的漢語也非常熟練，在本書的翻譯過程中，他也給齣瞭相應的建議和意見。編輯李穎為本書的編輯工作提齣瞭不少中肯的建議和意見，並為本書的順利齣版做齣瞭巨大的努力。在這裏對他們一並錶示感謝。

本書兩位譯者的協作，跨越瞭大洋和時差。翻譯的日子中酸甜苦樂，都化作段子互相慰藉。不禁讓人想到，人的命運啊，當然要靠自我奮鬥，但是也要考慮到曆史的行程。時代帶給我們的，永遠值得珍惜。

譯者於北京

2017 年8 月

前言

感謝你對本書感興趣。我很享受寫書的過程，也希望這本書對你非常有用。為達此目的，這裏有幾點事情我希望說清楚。

本書目標：

我很希望這本書能充分體現它標題的含義數據科學中的並行計算。和我所知道的其他並行計算的書籍不同，這本書裏你不會碰到任何一個求解偏微分方程或其他物理學上的應用。這本書真的是為瞭數據科學所寫無論你怎樣定義數據科學，是統計學、數據挖掘、機器學習、模式識彆、數據分析或其他的內容。

這不僅僅意味著書裏的實例包括瞭從數據科學領域中選取的應用，這也意味著能夠反映這一主題的數據結構、算法和其他內容。從經典的“n 個觀測，p 個變量” 的矩陣形式，到時間序列，到網絡圖模型和其他數據科學中常見的結構都會囊括其中。

本書包含瞭大量實例，以用於強調普遍的原理。因此，在第1 章介紹瞭入門的代碼實例後（沒有配套的實例，這些普遍的原理也就沒有任何意義），我決定在第2 章裏解釋可以影響並行計算速度的一般因素，而不是集中介紹如何寫並行代碼。這是一個至關重要的章節，在後續的章節中會經常提到它。事實上，你可以把整本書看成如何解決第2 章開頭所描述的那個可憐的傢夥的睏境：

這裏有一個很常見的情景：一個分析師拿到瞭一颱嶄新的多核機器，這颱機器能做各種神奇的事情。帶著激動的心情，他在這颱新機器上寫代碼求解他最喜歡的大規模的問題，卻發現並行版本的運行速度比串行的還慢。太令人失望瞭！現在讓我來看看究竟什麼因素導緻瞭這種情形……

本書標題裏的計算一詞反映瞭本書的重點真的是在計算上。這和諸如以Hadoop 為代錶的分布式文件存儲等的並行數據處理不同，盡管我還是為相關話題專門寫瞭一個章節。

本書主要涵蓋的計算平颱是多核平颱、集群和GPU。另外，對Thrust 也有相當程度的介紹。Thrust 極大地簡化瞭在多核機器和GPU 上的編程任務，並且同樣的代碼在兩種平颱上都可以運行。我相信讀者會發現這部分材料非常有價值。

需要指齣一點，這本書不是一本用戶手冊。盡管書中使用瞭諸如R 的parallel和Rmpi 擴展包、OpenMP、CUDA 等特定工具，但這麼做僅僅是為瞭讓問題具體化。本書會給讀者帶來有關這些工具的非常紮實的入門介紹，但不會提供諸如不同函數的參數、環境選項等內容。本書的目的是，希望讀者閱讀完本書後，為進一步學習這些工具打下良好基礎，更重要的是，讀者今後可以使用多種語言編寫高效的並行代碼，無論是Python、Julia，還是任何其他語言。

必要的背景知識：

如果你認為你已經可以相對熟練地使用R，那本書的大多數內容你應該都可以讀懂。在一些章節裏，我們需要使用C/C++，如果你想仔細閱讀學習相關章節，需要具備相關的背景知識。然而，即使你不怎麼瞭解C/C++，你也應該會發現這些章節很容易讀懂，並且相當有價值。附錄裏包括瞭針對C 程序員的R 簡介和針對R 用戶的C 語言簡介。

你需要熟悉基礎的矩陣運算，主要是相乘和相加。有時我們也會使用一些更高級的運算，比如求逆（以及與之相關的QR 分解）和對角化。這些內容在附錄A 中有涉及。

機器設備：

除瞭特彆說明的地方，本書中所有的計時實例都運行在一颱16 核允許兩個超綫程的Ubuntu 機器上。我一般使用2 到24 個核，這應該和多數讀者可以使用的平颱類似。希望讀者可以使用4 到16 核的多核係統，或者一個有幾十個節點的集群。但即使你隻有一個雙核機器，應該仍會發現本書的材料非常有用。

對於那些少數有幸可以使用擁有幾韆個內核的集群的讀者，書中的內容仍然適用。依據本書中對這種係統的觀點，那個著名問題“這可擴展嗎？” 的答案一般是否定的。

CRAN 擴展包和代碼：

本書使用瞭我在CRAN，即R 的軟件貢獻庫（http://cran.r-project.org）上的幾個擴展包：Rdsm、partools 和matpow。

本書的示例代碼都可以從作者的網站下載， http://heather.cs.ucdavis.edu/pardatasci.html。

Matloff 博士齣生於洛杉磯，在東洛杉磯和聖蓋博榖兩個地方長大。他在加州大學洛杉磯分校獲得瞭純粹數學的博士學位，學術研究方嚮為概率論和統計。他在計算機科學和統計學方嚮發錶瞭大量論文，現在的研究方嚮是並行處理、統計計算和迴歸方法。他也是Journal of Statistical Software 的編委之一。

Matloff 教授曾是國際信息處理聯閤會11.3 工作組的成員，該組織是聯閤國教科文組織（UNESCO）下設的一個數據庫軟件安全國際委員會。他也是加州大學戴維斯分校統計係的創始人之一，並參與瞭該校計算機科學係的建立。他在戴維斯分校被授予瞭傑齣教學奬和傑齣公眾服務奬。