基于MPI的大數據高性能計算導論( 簡體 字) | |
| 作者：［法］弗蘭克·尼爾森(Frank Nielsen)著 | 類別：1. -> 程式設計 -> 大數據 |
| 出版社：機械工業出版社 |  3dWoo書號： 49477詢問書籍請說出此書號！ 有庫存 NT售價： 295 元 |
| 出版日：7/1/2018 | |
| 頁數：210 | |
| 光碟數：0 | |
站長推薦：   | |
| 印刷：黑白印刷 | 語系： ( 簡體 字 ) |
| ISBN：9787111602149 | 加入購物車 │加到我的最愛 (請先登入會員) |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證, 繁體書的下載亦請直接連絡出版社) | |
譯者序
前言 致謝 第一部分基于消息傳遞接口的高性能計算 第1章走進高性能計算 1-1什么是高性能計算 1-2為什么我們需要HPC 1-3大數據：四個特性（數據量、多樣性、生成速度、價值） 1-4并行編程范式：MPI和MapReduce 1-5粒度：細粒度并行與粗粒度并行 1-6超級計算架構：內存和網絡 1-7加速比 1-7-1擴展性和等效率分析 1-7-2Amdahl定律：描述數據規模固定時漸近加速比的變化趨勢 1-7-3Gustafson定律：可擴展的加速比，隨著資源的增加不斷擴大數據量 1-7-4在串行計算機上模擬并行機 1-7-5大數據和并行輸入/輸出 1-8關于分布式系統的八個常見誤區 1-9注釋和參考 1-10總結 1-11練習 參考文獻 第2章MPI簡介：消息傳遞接口 2-1基于MPI的并行程序設計：基于消息通信 2-2并行編程模型、線程和進程 2-3進程之間的全局通信 2-3-1四個基本的MPI原語：廣播、收集、歸約和全交換 2-3-2阻塞與非阻塞和同步與異步通信 2-3-3阻塞通信產生的死鎖 2-3-4并發性：局部計算可以與通信重疊執行 2-3-5單向與雙向通信 2-3-6MPI中的全局計算：歸約和并行前綴（掃描） 2-3-7采用通信器定義通信組 2-4同步屏障：進程的交匯點 2-4-1MPI中的一個同步示例：測量運行時間 2-4-2整體同步并行計算模型 2-5開始使用MPI：使用OpenMPI 2-5-1用MPI C++編寫“Hello World”程序 2-5-2用C綁定進行MPI編程 2-5-3通過C++ Boost使用MPI 2-6通過OpenMP使用MPI 2-7MPI中的主要原語 2-7-1廣播、散播、收集、歸約和全歸約的MPI語法 2-7-2其余混雜的MPI原語 2-8環形拓撲上利用MPI進行的通信 2-9MPI程序示例及其加速比分析 2-9-1MPI中的矩陣向量積 2-9-2MPI歸約操作示例：計算數組的階乘和最小值 2-9-3MonteCarlo隨機積分算法估算π 2-9-4MonteCarlo隨機積分算法估算分子體積 2-10注釋和參考 2-11總結 2-12練習 參考文獻 第3章互聯網絡的拓撲結構 3-1兩個重要概念：靜態與動態網絡，以及邏輯與物理網絡 3-2互聯網絡：圖建模 3-3一些描述拓撲結構的屬性 3-3-1度和直徑 3-3-2連通性和對分 3-3-3一個好的網絡拓撲結構的標準 3-4常見的拓撲結構：簡單的靜態網絡 3-4-1完全圖：團 3-4-2星形圖 3-4-3環和帶弦環 3-4-4網（網格）與環面簇（環面的集合） 3-4-5三維立方體與循環連接立方體 3-4-6樹與胖樹 3-5超立方體拓撲結構以及使用格雷碼進行節點標識 3-5-1超立方體的遞歸構造 3-5-2使用格雷碼對超立方體節點編號 3-5-3使用C++生成格雷碼 3-5-4格雷碼和二進制碼的相互轉換 3-5-5圖的笛卡兒乘積 3-6一些拓撲結構上的通信算法 3-6-1有向環上的通信原語 3-6-2超立方體上的廣播：樹狀通信 3-7將（邏輯）拓撲結構嵌入到其他（物理）拓撲結構中 3-8復雜規則拓撲結構 3-9芯片上的互聯網絡 3-10注釋和參考 3-11總結 參考文獻 第4章并行排序 4-1串行排序快速回顧 4-1-1主要的串行排序算法 4-1-2排序的復雜性：下界 4-2通過合并列表實現并行排序 4-3利用秩實現并行排序 4-4并行快速排序 4-5超快速排序 4-6正則采樣并行排序 4-7基于網格的排序：ShearSort 4-8使用比較網絡排序：奇偶排序 4-9使用比較網絡合并有序列表 4-10雙調歸并排序 4-11注釋和參考 4-12總結 4-13練習 參考文獻 第5章并行線性代數 5-1分布式線性代數 5-1-1數據科學中的線性代數 5-1-2經典線性代數 5-1-3矩陣向量乘法：y=Ax 5-1-4并行數據模式 5-2有向環拓撲上的矩陣向量乘積 5-3網格上的矩陣乘法：外積算法 5-4二維環面拓撲上的矩陣乘積 5-4-1Cannon算法 5-4-2Fox算法：廣播相乘循環移位矩陣乘積 5-4-3Snyder算法：在對角線上進行本地乘積累加 5-4-4Cannon、Fox和Snyder算法的比較 5-5注釋和參考 5-6總結 5-7練習 參考文獻 第6章MapReduce范式 6-1快速處理大數據的挑戰 6-2MapReduce的基本原理 6-2-1map和reduce過程 6-2-2歷史視角：函數式編程語言中的map和reduce 6-3數據類型和MapReduce機制 6-4MapReduce在C ++中的完整示例 6-5啟動MapReduce作業和MapReduce架構概述 6-6基于MRMPI庫在MPI中使用MapReduce 6-7注釋和參考 6-8總結 參考文獻 第二部分面向數據科學的高性能計算 第7章基于k均值的劃分聚類 7-1探索性數據分析與聚類 7-1-1硬聚類：劃分數據集 7-1-2成本函數和模型聚類 7-2k均值目標函數 7-2-1重寫k均值成本函數以對聚類效果進行雙重解釋：聚類簇內數據或分離簇間數據 7-2-2k均值優化問題的復雜性和可計算性 7-3Lloyd批量k均值局部啟發式方法 7-4基于全局啟發式的k均值初始化方法 7-4-1基于隨機種子的初始化方法 7-4-2全局k均值：最佳貪心初始化 7-4-3kmeans ++：一種簡單的概率保證的初始化方法 7-5k均值向量量化中的應用 7-5-1向量量化 7-5-2Lloyd的局部最小值和穩定Voronoi劃分 7-6k均值的物理解釋：慣性分解 7-7k均值中k的選擇：模型選擇 7-7-1基于肘部法則的模型選擇 7-7-2模型選擇：用k解釋方差減少 7-8集群上的并行k均值聚類 7-9評估聚類劃分 7-9-1蘭德指數 7-9-2歸一化互信息 7-10注釋和參考 7-11總結 7-12練習 參考文獻 第8章層次聚類 8-1凝聚式與分裂式層次聚類及其樹狀圖表示 8-2定義一個好的連接距離的幾種策略 8-2-1一個用于凝聚式層次聚類的通用算法 8-2-2為元素選擇合適的基本距離函數 8-3Ward合并準則和質心 8-4從樹狀圖中獲取平面劃分 8-5超度量距離和進化樹 8-6注釋和參考 8-7總結 8-8練習 參考文獻 第9章有監督學習: kNN規則分類的理論和實踐 9-1有監督學習 9-2最近鄰分類：NN規則 9-2-1最近鄰查詢中歐幾里得距離計算的優化方法 9-2-2最近鄰（NN）規則和Voronoi圖 9-2-3利用kNN規則通過表決來增強NN規則 9-3分類器性能評估 9-3-1誤判錯誤率 9-3-2混淆矩陣與真/假及陽性/陰性 9-4準確率、召回率和F值 9-5統計機器學習和貝葉斯最小誤差界 9-5-1非參數概率密度估計 9-5-2誤差概率和貝葉斯誤差 9-5-3kNN規則的誤差概率 9-6在計算機集群上實現最近鄰查詢 9-7注釋和參考 9-8總結 9-9練習 參考文獻 第10章基于核心集的高維快速近似優化和快速降維 10-1大規模數據集的近似優化 10-1-1高維度的必要性示例 10-1-2高維度上的一些距離現象 10-1-3核心集：從大數據集到小數據集 10-2核心集的定義 10-3最小閉包球的核心集 10-4一個用來近似最小閉包球的簡單迭代啟發式方法 10-4-1收斂性證明 10-4-2小閉包球和用于SVM的邊緣線性分離器 10-5k均值的核心集 10-6基于隨機投影矩陣的快速降維 10-6-1維數災難 10-6-2高維度任務的兩個示例 10-6-3線性降維 10-6-4JohnsonLindenstrauss定理 10-6-5隨機投影矩陣 10-7注釋和參考 10-8總結 10-9練習 參考文獻 第11章圖并行算法 11-1在大圖中尋找（最）稠密子圖 11-1-1問題描述 11-1-2最稠密子圖的復雜度和一個簡單的貪心啟發式算法 11-1-3最稠密子圖的并行啟發式算法 11-2判斷（子）圖同構 11-2-1枚舉算法的一般原則 11-2-2Ullman算法：檢測子圖同構性 11-2-3枚舉算法并行化 11-3注釋和參考 11-4總結 11-5練習 參考文獻 附錄A 筆試 附錄B SLURM:集群上的資源管理器和任務調度器 本書是關于高性能計算和數據科學的入門教材，面向有基本算法知識和編程能力的讀者，書中選擇C++語言來實現數據科學中的算法，并使用和C語言綁定的OpenMPI應用程序編程接口來編寫并行程序，使用MPI標準介紹數據科學中的高性能計算，幫助讀者了解分布式存儲模型中的并行編程知識。
本書分為兩部分，第一部分（第1~6章）基于MPI介紹高性能計算，第二部分（第7~11章）介紹計算機集群中的高性能數據分析。本書教輔資源豐富，書中相關的偽代碼可在對應網站下載，章末附有各種難度的練習和參考文獻，可供讀者進行自測和深入學習。 通過閱讀本書，你將學到： 阻塞與非阻塞的點對點通信、死鎖、全局通信函數（廣播、散播等）和協同計算（歸約）的基本概念。 互聯網絡的拓撲結構（環、環面和超立方體）以及相應的全局通信程序。 如何設計并實現基于分布式內存的并行排序，了解并行線性代數知識（如矩陣相乘）。 使用MPI框架計算適用于處理大數據的MapReduce模型。 數據聚類技術（平面劃分聚類、層次聚類）。 基于k-NN的有監督分類及其與k均值聚類算法的比較。 核心集以及相關降維技術。 圖算法（最稠密子圖、圖同構檢測）。 歡迎來到高性能計算的世界！歡迎來到高性能數據科學的世界！
在本書中，我們將介紹面向數據科學（Data Science，DS）的高性能計算（High Performance Computing，HPC）。因此，本書主要分為兩個部分：第一部分（前6章）涵蓋HPC的基本原理；第二部分（后5章）介紹了數據科學的基本知識，并展示了如何編寫面向基本串行算法的分布式程序，以應對大規模數據集。當前，許多大規模數據集都是公開的，這些數據集中蘊含了豐富的信息，但是這些信息需要通過精心設計才能被提取出來。 我們主要區分兩種并行算法的設計方法：在單個共享內存多核機器上使用多線程并行化算法；在分布式內存集群系統上并行化算法。 一方面，當在共享內存架構（如智能手機、平板電腦，以及智能手表和其他物聯網設備）上設計并行化算法時，所有的硬件計算單元（核）位于同一芯片上，我們可以使用多線程來輕松地對視頻解碼、渲染等任務進行并行化。這種并行是細粒度的（finegrained），但它受到芯片上物理核數的限制（2015年高端智能手機通常只有8個核）。另一方面，集群系統（即分布式內存架構）可以根據待處理的數據集規模來實時擴展資源。集群的構建具有很大的靈活性，例如可以選擇異構的計算機節點，然后確定最適合這些節點的互連拓撲結構。這種并行是粗粒度的（coarsegrained），因為在集群中發生節點間通信之前，每個節點可以獨立地進行大量的本地計算。 本書側重于在分布式內存系統上利用標準消息傳遞接口（Message Passing Interface，MPI）來設計并行算法。MPI是管理集群節點之間通信和全局協同計算的實際標準。目前存在多種MPI標準的供應商實現，它們可以與C、C++、Fortran、Python等多種編程語言綁定。我們選擇面向對象的語言C++來實現數據科學中的算法，并使用和C語言綁定的OpenMPI應用程序編程接口（Application Programming Interface，API）來編寫并行程序。 本書中兩部分內容的簡要介紹如下。 第一部分：基于消息傳遞接口的高性能計算 第1章首先簡單介紹了HPC世界，然后講解了Amdahl定律和Gustafson定律，這兩個定律刻畫了并行程序的理論最優加速比和擴展加速比。 第2章講解了MPI的主要概念和編程接口：阻塞/非阻塞通信的概念、死鎖和多種全局通信函數（例如broadcast、scatter、gather、alltoall、reduce、parallel prefix等）。 第3章著重介紹了互聯網絡拓撲的作用。我們首先區分物理拓撲和虛擬拓撲（或稱為邏輯拓撲），并在設計并行算法的時候考慮不同網絡拓撲對性能的影響。特別講解了環形（包括優化的流水線廣播）和超立方體形網絡拓撲上的通信過程，后者依賴于節點的特定編號，稱為格雷碼。 第4章講解了基于分布式內存的主要的并行排序算法。首先對著名的快速排序算法（Quicksort）進行了簡單的并行化，然后介紹實際中廣泛使用的HyperQuicksort和PSRS（Parallel Sorting by Regular Sampling）算法。 第5章研究了一些矩陣相乘和向量相乘的算法，并簡要介紹了在環和環面（torus）的拓撲結構中計算矩陣乘積的各種技術。 第6章介紹了一個比較熱門的并行編程范式，稱為MapReduce（通常與開源系統Hadoop一起使用）。 MapReduce可以通過兩個主要的用戶定義的函數（map和reduce）來構建程序，然后部署到大量的網絡互連的計算機上來完成計算任務。 然而，MapReduce也是一個完整的框架，包括一個主從架構。該主從架構能夠處理各種硬件故障，或者當一些機器執行得太慢時，將這些機器上的并行計算任務（作業）重新發送到其他的機器上執行。該章還講解了如何利用專門的名為MRMPI的軟件庫在MPI（MPI沒有容錯能力）中實現這些類型的MapReduce算法。 第二部分：面向數據科學的高性能計算 這部分簡要介紹了數據科學，并進一步講解了如何使用MPI并行化數據科學中的算法。 首先介紹了兩個最基本的數據聚類技術，分別是平面劃分聚類（第7章）和層次樹聚類（第8章）。聚類是探索性數據科學中一個非常重要的概念，用于發現數據集中的分類、同質數據中的分組。 第9章介紹了基于k最近鄰規則（knearest neighbor）的有監督分類，并和k均值（kmeans）聚類算法進行關聯。 第10章介紹了另一個計算科學中的新范式，允許人們在大型數據集（潛在的高維度）上解決優化問題。這種新范式就是尋找核心集（coreset），這些核心集就是原數據集的子集，而且和原數據集相比具有良好的近似性。這種技術最近變得非常流行，能夠將大數據（big data）縮小到小數據（tiny data）！由于數據通常具有高維度特征，所以還簡要介紹了一種有效的線性降維技術，其中講解了JohnsonLindenstrauss定理，并給出一個簡單的方法計算低失真嵌入，從而將數據從高維轉化為低維，并確保在規定的近似因子內數據點之間的距離保持不變。有趣的是，嵌入的維度與原始外在維度無關，而是依賴于數據集大小的對數和近似因子。 第11章涵蓋了一些圖（graph）算法。圖在社交網絡分析和其他應用領域中是比較常見的。因此首先介紹一個順序啟發式方法和一個并行啟發式方法來查找圖的稠密子圖，該子圖近似于“最稠密”子圖。 然后介紹了在計算機集群上利用分支限界法來進行圖同構檢測。圖同構檢測是一個備受關注的問題，因為它的理論復雜度還沒有得到解決（盡管對于圖的某些特定子類存在一些多項式算法）。 每章最后會對該章的一些要點進行總結。請讀者瀏覽這些總結，以便進行第一遍快速閱讀。在一些章節結束時會給出40多道練習題，這些練習標有各種難度，并允許讀者對練習所涵蓋內容的理解程度進行自測。以星號開頭的部分可以先跳過，稍后再進行閱讀。 本書的主要目的是幫助讀者設計并行算法，然后利用C++和C語言綁定的MPI編寫程序實現相應的并行算法。第二個目的是讓讀者對高性能計算和數據科學有更深刻的了解，并希望更好地促進兩者之間的交叉。 本書是關于高性能計算和數據科學的入門教材，面向具有基本算法知識和編程能力的讀者。因此，本書不包含（也沒有提及）高性能計算和數據科學領域的高級概念。例如，任務調度問題和嵌套循環的自動并行化雖然在高性能計算中很重要，但是本書并沒有涉及。類似地，本書也省略了數據科學領域中的回歸技術和核心機器學習方法。 教輔資源 本書的額外資源（包括超過35個用MPI/C++/R/Scilab/Gnuplot/Processing編寫的程序、幻燈片、相關鏈接和其他精彩內容）可以通過網址獲取。 程序的源代碼可以在上述網址以下列方式獲取： 祝閱讀愉快！ Frank Nielsen 2015年12月 | |
