前言歡迎來到高性能計算的世界！歡迎來到高性能數(shù)據(jù)科學(xué)的世界！
在本書中，我們將介紹面向數(shù)據(jù)科學(xué)（Data Science，DS）的高性能計算（High Performance Computing，HPC）。因此，本書主要分為兩個部分：第一部分（前6章）涵蓋HPC的基本原理；第二部分（后5章）介紹了數(shù)據(jù)科學(xué)的基本知識，并展示了如何編寫面向基本串行算法的分布式程序，以應(yīng)對大規(guī)模數(shù)據(jù)集。當(dāng)前，許多大規(guī)模數(shù)據(jù)集都是公開的，這些數(shù)據(jù)集中蘊含了豐富的信息，但是這些信息需要通過精心設(shè)計才能被提取出來。
我們主要區(qū)分兩種并行算法的設(shè)計方法：在單個共享內(nèi)存多核機器上使用多線程并行化算法；在分布式內(nèi)存集群系統(tǒng)上并行化算法。
一方面，當(dāng)在共享內(nèi)存架構(gòu)（如智能手機、平板電腦，以及智能手表和其他物聯(lián)網(wǎng)設(shè)備）上設(shè)計并行化算法時，所有的硬件計算單元（核）位于同一芯片上，我們可以使用多線程來輕松地對視頻解碼、渲染等任務(wù)進行并行化。這種并行是細粒度的（fine�瞘rained），但它受到芯片上物理核數(shù)的限制（2015年高端智能手機通常只有8個核）。另一方面，集群系統(tǒng)（即分布式內(nèi)存架構(gòu)）可以根據(jù)待處理的數(shù)據(jù)集規(guī)模來實時擴展資源。集群的構(gòu)建具有很大的靈活性，例如可以選擇異構(gòu)的計算機節(jié)點，然后確定最適合這些節(jié)點的互連拓撲結(jié)構(gòu)。這種并行是粗粒度的（coarse�瞘rained），因為在集群中發(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ù)科學(xué)中的算法，并使用和C語言綁定的OpenMPI應(yīng)用程序編程接口（Application Programming Interface，API）來編寫并行程序。
本書中兩部分內(nèi)容的簡要介紹如下。
第一部分：基于消息傳遞接口的高性能計算第1章首先簡單介紹了HPC世界，然后講解了Amdahl定律和Gustafson定律，這兩個定律刻畫了并行程序的理論最優(yōu)加速比和擴展加速比。
第2章講解了MPI的主要概念和編程接口：阻塞/非阻塞通信的概念、死鎖和多種全局通信函數(shù)（例如broadcast、scatter、gather、all�瞭o�瞐ll、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)能夠處理各種硬件故障，或者當(dāng)一些機器執(zhí)行得太慢時，將這些機器上的并行計算任務(wù)（作業(yè)）重新發(fā)送到其他的機器上執(zhí)行。該章還講解了如何利用專門的名為MR�睲PI的軟件庫在MPI（MPI沒有容錯能力）中實現(xiàn)這些類型的MapReduce算法。
第二部分：面向數(shù)據(jù)科學(xué)的高性能計算這部分簡要介紹了數(shù)據(jù)科學(xué)，并進一步講解了如何使用MPI并行化數(shù)據(jù)科學(xué)中的算法。
首先介紹了兩個最基本的數(shù)據(jù)聚類技術(shù)，分別是平面劃分聚類（第7章）和層次樹聚類（第8章）。聚類是探索性數(shù)據(jù)科學(xué)中一個非常重要的概念，用于發(fā)現(xiàn)數(shù)據(jù)集中的分類、同質(zhì)數(shù)據(jù)中的分組。
第9章介紹了基于k最近鄰規(guī)則（k�瞡earest neighbor）的有監(jiān)督分類，并和k均值（k�瞞eans）聚類算法進行關(guān)聯(lián)。
第10章介紹了另一個計算科學(xué)中的新范式，允許人們在大型數(shù)據(jù)集（潛在的高維度）上解決優(yōu)化問題。這種新范式就是尋找核心集（core�瞫et），這些核心集就是原數(shù)據(jù)集的子集，而且和原數(shù)據(jù)集相比具有良好的近似性。這種技術(shù)最近變得非常流行，能夠?qū)⒋髷?shù)據(jù)（big data）縮小到小數(shù)據(jù)（tiny data）！由于數(shù)據(jù)通常具有高維度特征，所以還簡要介紹了一種有效的線性降維技術(shù)，其中講解了Johnson�睱indenstrauss定理，并給出一個簡單的方法計算低失真嵌入，從而將數(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多道練習(xí)題，這些練習(xí)標有各種難度，并允許讀者對練習(xí)所涵蓋內(nèi)容的理解程度進行自測。以星號開頭的部分可以先跳過，稍后再進行閱讀。
本書的主要目的是幫助讀者設(shè)計并行算法，然后利用C++和C語言綁定的MPI編寫程序?qū)崿F(xiàn)相應(yīng)的并行算法。第二個目的是讓讀者對高性能計算和數(shù)據(jù)科學(xué)有更深刻的了解，并希望更好地促進兩者之間的交叉。
本書是關(guān)于高性能計算和數(shù)據(jù)科學(xué)的入門教材，面向具有基本算法知識和編程能力的讀者。因此，本書不包含（也沒有提及）高性能計算和數(shù)據(jù)科學(xué)領(lǐng)域的高級概念。例如，任務(wù)調(diào)度問題和嵌套循環(huán)的自動并行化雖然在高性能計算中很重要，但是本書并沒有涉及。類似地，本書也省略了數(shù)據(jù)科學(xué)領(lǐng)域中的回歸技術(shù)和核心機器學(xué)習(xí)方法。
教輔資源本書的額外資源（包括超過35個用MPI/C++/R/Scilab/Gnuplot/Processing編寫的程序、幻燈片、相關(guān)鏈接和其他精彩內(nèi)容）可以通過網(wǎng)址https://www�眑ix�眕olytechnique�眆r/nielsen/HPC4DS/獲取。
程序的源代碼可以在上述網(wǎng)址以下列方式獲取：
祝閱讀愉快！
Frank Nielsen2015年12月致謝非常感謝以下這些有才華的同事，他們給了我非常寶貴的反饋意見（姓名按隨機順序排列）并幫助我完善了本書：Claudiad�� Ambrosio, Ulysse Beaugnon, Anna�僱 Bonneton, Jean�睟aptiste Bordes, PatriceCalégari, Henri Casanova, Antoine Delignat�睱avaud, Amélie Héliou, Alice Héliou, Léo Liberti, Frédéric Magoulès, Gautier Marti, Sameh Mohamed, Fran�搊is Morain, Richard Nock, Pierre�睱ouis Poirion, Stéphane Redon, Thomas Sibut�睵inote, Benjamin Smith, Antoine Soulé, Bogdan Tomchuk, Sonia Toubaline和 Frédéric Vivien。除了以上這些同事，我還與其他很多同事進行了討論，當(dāng)你們讀到這句話時，希望你們能夠知道，從這些寶貴的交談中，我受益匪淺。我還要感謝所有巴黎綜合理工大學(xué)INF442課程的學(xué)生，感謝他們富有成效的意見和反饋，并且感謝巴黎綜合理工大學(xué)計算機科學(xué)學(xué)院（DIX）的支持。