并行程序設(shè)計(jì)導(dǎo)論

內(nèi)容概要

《并行程序設(shè)計(jì)導(dǎo)論/計(jì)算機(jī)科學(xué)叢書》編著者Peter S.Pacheco。
本書全面涵蓋了并行軟件和硬件的方方面面，深入淺出地介紹如何使用MPI（分布式內(nèi)存編程）、Pthreads和OpenMP（共享內(nèi)存編程）編寫高效的并行程序。各章節(jié)包含了難易程度不同的編程習(xí)題。本書可以用做計(jì)算機(jī)科學(xué)專業(yè)低年級(jí)本科生的專業(yè)課程的教材，也可以作為軟件開發(fā)人員學(xué)習(xí)并行程序設(shè)計(jì)的專業(yè)參考書。

作者簡(jiǎn)介

作者：（美國(guó)）帕切克（Peter S.Pacheco） 鄧倩妮  Peter S.Pacheco 擁有佛羅里達(dá)州立大學(xué)數(shù)學(xué)專業(yè)博士學(xué)位。曾擔(dān)任舊金山大學(xué)計(jì)算機(jī)系主任，目前是舊金山大學(xué)數(shù)學(xué)系主任。近20年來，一直為本科生和研究生講授并行計(jì)算課程。

書籍目錄

出版者的話
 譯者序
 本書贊譽(yù)
 前言
 致謝
第1章 為什么要并行計(jì)算
 1.1 為什么需要不斷提升的性能
 1.2 為什么需要構(gòu)建并行系統(tǒng)
 1.3 為什么需要編寫并行程序
 1.4 怎樣編寫并行程序
 1.5 我們將做什么
 1.6 并發(fā)、并行、分布式
 1.7 本書的其余部分
 1.8 警告
 1.9 字體約定
 1.10 小結(jié)
 1.11 習(xí)題
第2章 并行硬件和并行軟件
 2.1 背景知識(shí)
 2.1.1 馮·諾依曼結(jié)構(gòu)
 2.1.2 進(jìn)程、多任務(wù)及線程
 2.2 對(duì)馮·諾依曼模型的改進(jìn)
 2.2.1 Cache基礎(chǔ)知識(shí)
 2.2.2 Cache映射
 2.2.3 Cache和程序:一個(gè)實(shí)例
 2.2.4 虛擬存儲(chǔ)器
 2.2.5 指令級(jí)并行
 2.2.6 硬件多線程
 2.3 并行硬件
 2.3.1 SIMD系統(tǒng)
 2.3.2 MIMD系統(tǒng)
 2.3.3 互連網(wǎng)絡(luò)
 2.3.4 Cache一致性
 2.3.5 共享內(nèi)存與分布式內(nèi)存
 2.4 并行軟件
 2.4.1 注意事項(xiàng)
 2.4.2 進(jìn)程或線程的協(xié)調(diào)
 2.4.3 共享內(nèi)存
 2.4.4 分布式內(nèi)存
 2.4.5 混合系統(tǒng)編程
 2.5 輸入和輸出
 2.6 性能
 2.6.1 加速比和效率
 2.6.2 阿姆達(dá)爾定律
 2.6.3 可擴(kuò)展性
 2.6.4 計(jì)時(shí)
 2.7 并行程序設(shè)計(jì)
 2.8 編寫和運(yùn)行并行程序
 2.9 假設(shè)
 2.10 小結(jié)
 2.10.1 串行系統(tǒng)
 2.10.2 并行硬件
 2.10.3 并行軟件
 2.10.4 輸入和輸出
 2.10.5 性能
 2.10.6 并行程序設(shè)計(jì)
 2.10.7 假設(shè)
 2.11 習(xí)題
第3章 用MPI進(jìn)行分布式內(nèi)存編程
 3.1 預(yù)備知識(shí)
 3.1.1 編譯與執(zhí)行
 3.1.2 MPI程序
 3.1.3 MPI_Init和MPI_Finalize
 3.1.4 通信子、MPI_Comm_size和MPI_Comm_rank
 3.1.5 SPMD程序
 3.1.6 通信
 3.1.7 MPI_Send
 3.1.8 MPI_Recv
 3.1.9 消息匹配
 3.1.10 status_p參數(shù)
 3.1.11 MPI_Send和MPI_Recv的語(yǔ)義
 3.1.12 潛在的陷阱
 3.2 用MPI來實(shí)現(xiàn)梯形積分法
 3.2.1 梯形積分法
 3.2.2 并行化梯形積分法
 3.3 I/O處理
 3.3.1 輸出
 3.3.2 輸入
 3.4 集合通信
 3.4.1 樹形結(jié)構(gòu)通信
 3.4.2 MPI_Reduce
 3.4.3 集合通信與點(diǎn)對(duì)點(diǎn)通信
 3.4.4 MPI_Allreduce
 3.4.5 廣播
 3.4.6 數(shù)據(jù)分發(fā)
 3.4.7 散射
 3.4.8 聚集
 3.4.9 全局聚集
 3.5 MPI的派生數(shù)據(jù)類型
 3.6 MPI程序的性能評(píng)估
 3.6.1 計(jì)時(shí)
 3.6.2 結(jié)果
 3.6.3 加速比和效率
 3.6.4 可擴(kuò)展性
 3.7 并行排序算法
 3.7.1 簡(jiǎn)單的串行排序算法
 3.7.2 并行奇偶交換排序
 3.7.3 MPI程序的安全性
 3.7.4 并行奇偶交換排序算法的重要內(nèi)容
 3.8 小結(jié)
 3.9 習(xí)題
 3.10 編程作業(yè)
第4章 用Pthreads進(jìn)行共享內(nèi)存編程
 4.1 進(jìn)程、線程和Pthreads
 4.2 “Hello，World”程序
 4.2.1 執(zhí)行
 4.2.2 準(zhǔn)備工作
 4.2.3 啟動(dòng)線程
 4.2.4 運(yùn)行線程
 4.2.5 停止線程
 4.2.6 錯(cuò)誤檢查
 4.2.7 啟動(dòng)線程的其他方法
 4.3 矩陣-向量乘法
 4.4 臨界區(qū)
 4.5 忙等待
 4.6 互斥量
 4.7 生產(chǎn)者-消費(fèi)者同步和信號(hào)量
 4.8 路障和條件變量
 4.8.1 忙等待和互斥量
 4.8.2 信號(hào)量
 4.8.3 條件變量
 4.8.4 Pthreads路障
 4.9 讀寫鎖
 4.9.1 鏈表函數(shù)
 4.9.2 多線程鏈表
 4.9.3 Pthreads讀寫鎖
 4.9.4 不同實(shí)現(xiàn)方案的性能
 4.9.5 實(shí)現(xiàn)讀寫鎖
 4.10 緩存、緩存一致性和偽共享
 4.11 線程安全性
 4.12 小結(jié)
 4.13 習(xí)題
 4.14 編程作業(yè)
第5章 用OpenMP進(jìn)行共享內(nèi)存編程
 5.1 預(yù)備知識(shí)
 5.1.1 編譯和運(yùn)行OpenMP程序
 5.1.2 程序
 5.1.3 錯(cuò)誤檢查
 5.2 梯形積分法
 5.3 變量的作用域
 5.4 歸約子句
 5.5 parallelfor指令
 5.5.1 警告
 5.5.2 數(shù)據(jù)依賴性
 5.5.3 尋找循環(huán)依賴
 5.5.4 π值估計(jì)
 5.5.5 關(guān)于作用域的更多問題
 5.6 更多關(guān)于OpenMP的循環(huán)：排序
 5.6.1 冒泡排序
 5.6.2 奇偶變換排序
 5.7 循環(huán)調(diào)度
 5.7.1 schedule子句
 5.7.2 static調(diào)度類型
 5.7.3 dynamic和guided調(diào)度類型
 5.7.4 runtime調(diào)度類型
 5.7.5 調(diào)度選擇
 5.8 生產(chǎn)者和消費(fèi)者問題
 5.8.1 隊(duì)列
 5.8.2 消息傳遞
 5.8.3 發(fā)送消息
 5.8.4 接收消息
 5.8.5 終止檢測(cè)
 5.8.6 啟動(dòng)
 5.8.7 atomic指令
 5.8.8 臨界區(qū)和鎖
 5.8.9 在消息傳遞程序中使用鎖
 5.8.10 critical指令、atomic指令、鎖的比較
 5.8.11 經(jīng)驗(yàn)
 5.9 緩存、緩存一致性、偽共享
 5.10 線程安全性
 5.11 小結(jié)
 5.12 習(xí)題
 5.13 編程作業(yè)
第6章 并行程序開發(fā)
 6.1 n體問題的兩種解決方法
 6.1.1 問題
 6.1.2 兩個(gè)串行程序
 6.1.3 并行化n體算法
 6.1.4 關(guān)于I/O
 6.1.5 用OpenMP并行化基本算法
 6.1.6 用OpenMP并行化簡(jiǎn)化算法
 6.1.7 評(píng)估OpenMP程序
 6.1.8 用Pthreads并行化算法
 6.1.9 用MPI并行化基本算法
 6.1.10 用MPI并行化簡(jiǎn)化算法
 6.1.11 MPI程序的性能
 6.2 樹形搜索
 6.2.1 遞歸的深度優(yōu)先搜索
 6.2.2 非遞歸的深度優(yōu)先搜索
 6.2.3 串行實(shí)現(xiàn)所用的數(shù)據(jù)結(jié)構(gòu)
 6.2.4 串行實(shí)現(xiàn)的性能
 6.2.5 樹形搜索的并行化
 6.2.6 采用Pthreads實(shí)現(xiàn)的靜態(tài)并行化樹搜索
 6.2.7 采用Pthreads實(shí)現(xiàn)的動(dòng)態(tài)并行化樹搜索
 6.2.8 Pthreads樹搜索程序的評(píng)估
 6.2.9 采用OpenMp實(shí)現(xiàn)的并行化樹搜索程序
 6.2.10 OpenMp實(shí)現(xiàn)的性能
 6.2.11采用MPI和靜態(tài)劃分來實(shí)現(xiàn)樹搜索
 6.2.12 采用MPI和動(dòng)態(tài)劃分來實(shí)現(xiàn)樹搜索
 6.3 忠告
 6.4 選擇哪個(gè)API
 6.5 小結(jié)
 6.5.1 Pthreads和OpenMP
 6.5.2 MPI
 6.6 習(xí)題
 6.7 編程作業(yè)
第7章 接下來的學(xué)習(xí)方向
 參考文獻(xiàn)
 索引

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   接下來，我們仔細(xì)研究最后兩個(gè)參數(shù)，由pthread_create生成并運(yùn)行的函數(shù)應(yīng)該有一個(gè)類似于下面函數(shù)的原型： void*.thread_function（void* arga_p）； 因?yàn)轭愋蛌oi d*可以轉(zhuǎn)換為C語(yǔ)言中任意指針類型，所以args_P可以指向一個(gè)列表，該列表包含一個(gè)或多個(gè)thread_function函數(shù)需要的數(shù)值。類似地，thread_function返回的值也可以是一個(gè)包含一個(gè)或多個(gè)值的列表。在我們的代碼中，調(diào)用pthread_create函數(shù)時(shí)，傳入最后一個(gè)參數(shù)采用了一個(gè)常用的技巧：為每一個(gè)線程賦予了唯一的int型參數(shù)rank，表示線程的編號(hào)。首先，我們先解釋一下這么做的理由，然后再具體探討如何做。 考慮以下問題：運(yùn)行一個(gè)生成了兩個(gè)線程的Pthreads程序，當(dāng)其中一個(gè)線程遇到了錯(cuò)誤時(shí)，我們或者用戶如何才能知道是哪個(gè)線程出了問題呢？我們不能簡(jiǎn)單地輸出pthread_t對(duì)象，因?yàn)樗遣煌该鞯?。如果我們啟?dòng)線程時(shí)賦予第一個(gè)線程編號(hào)為0，第二個(gè)線程編號(hào)為1，那么通過錯(cuò)誤信息中線程的編號(hào)就能非常容易地判斷是哪個(gè)線程出錯(cuò)了。 既然線程函數(shù)可以接收voi d*類型的參數(shù)，我們就可以在main函數(shù)中為每個(gè)線程分配一個(gè)int類型的整數(shù)，并為這些整數(shù)賦予不同的數(shù)值。當(dāng)啟動(dòng)線程時(shí)，把指向該int型參數(shù)的指針傳遞給pthread_create函數(shù)。然而，程序員會(huì)用類型轉(zhuǎn)換來處理此問題：不是在main函數(shù)中生成int型的進(jìn)程號(hào)，而是把循環(huán)變量thread轉(zhuǎn)化為voi d*類型，然后在線程函數(shù)hello中，把這個(gè)參數(shù)的類型轉(zhuǎn)換為long型（第33行）。 類型轉(zhuǎn)換的結(jié)果是“系統(tǒng)定義”的，但大多數(shù)C編譯器允許這么做。不過，如果指針類型的大小和表示進(jìn)程編號(hào)的整數(shù)類型不同，在編譯時(shí)就會(huì)收到警告。在我們使用的機(jī)器上，指針類型是64位，而int型是32位，為了避免警告，我們用long型替代了int型。 需要注意的是，我們?yōu)槊恳粋€(gè)線程分配不同的編號(hào)只是為了方便使用。事實(shí)上，pthread_create創(chuàng)建線程時(shí)沒有要求必須傳遞線程號(hào)，也沒有要求必須要分配線程號(hào)給一個(gè)線程。 還需要注意的是，并非由于技術(shù)上的原因而規(guī)定每個(gè)線程都要運(yùn)行同樣的函數(shù)。一個(gè)線程運(yùn)行hello函數(shù)的同時(shí)，另一個(gè)線程可以運(yùn)行g(shù)oodbye函數(shù)。但與編寫MPI程序的方法類似，Pthreads程序也采用“單程序，多數(shù)據(jù)”的并行模式，即每個(gè)線程都執(zhí)行同樣的線程函數(shù)，但可以在線程內(nèi)用條件轉(zhuǎn)移來獲得不同線程有不同功能的效果。 4.2.4運(yùn)行線程 運(yùn)行main函數(shù)的線程一般稱為主線程。所以，在線程啟動(dòng)后，會(huì)打印一句： Hello from the main thread 同時(shí)，調(diào)用pthread_create所生成的線程也在運(yùn)行。這些線程通過第33行的類型轉(zhuǎn)換代碼獲得各自的編號(hào)，然后打印各自的消息。注意，當(dāng)線程結(jié)束時(shí)，由于它的函數(shù)的類型有一個(gè)返回值，那么線程就應(yīng)該返回一個(gè)值。在本例中，線程沒有需要特別返回的值，所以只返回NULL。 在Pthreads中，程序員不直接控制線程在哪個(gè)核上運(yùn)行。在pthread_create函數(shù)中，沒有參數(shù)用于指定在哪個(gè)核上運(yùn)行線程。線程的調(diào)度是由操作系統(tǒng)來控制的。在負(fù)載很重的系統(tǒng)上，所有線程可能都運(yùn)行在同一個(gè)核上。事實(shí)上，如果線程個(gè)數(shù)大于核的個(gè)數(shù)，就會(huì)出現(xiàn)多個(gè)線程運(yùn)行在一個(gè)核上。當(dāng)然，如果某個(gè)核處于空閑狀態(tài)，操作系統(tǒng)就會(huì)將一個(gè)新線程分配給這個(gè)核。

編輯推薦

《并行程序設(shè)計(jì)導(dǎo)論》是一本精心撰寫的、全面介紹并行計(jì)算的書籍。作者循序漸進(jìn)地展示了如何利用MPI、Pthreads和OpenMP開發(fā)高效的并行程序，教給那些專業(yè)知識(shí)有限、沒有并行化經(jīng)驗(yàn)的讀者如何開發(fā)、調(diào)試分布式內(nèi)存和共享內(nèi)存的程序，以及對(duì)程序進(jìn)行性能評(píng)估。

名人推薦

毫無疑問，隨著多核處理器和云計(jì)算系統(tǒng)的廣泛應(yīng)用，并行計(jì)算不再是計(jì)算世界中被束之高閣的偏門領(lǐng)域。并行性已經(jīng)成為有效利用資源的首要因素。Peter Pachec0撰寫的這本新教材對(duì)于初學(xué)者了解并行計(jì)算的藝術(shù)和實(shí)踐很有幫助。 ——Duncan Buell，南卡羅來納大學(xué)計(jì)算機(jī)科學(xué)與工程系 本書闡述了兩個(gè)越來越重要的領(lǐng)域：使用Plhreads和OpenMP進(jìn)行共享內(nèi)存編程。以及使用MPl進(jìn)行分布式內(nèi)存編程。更重要的是。通過指出可能出現(xiàn)的性能錯(cuò)誤，強(qiáng)調(diào)好的編程實(shí)現(xiàn)的重要性。這些主題包含在計(jì)算機(jī)科學(xué)、物理學(xué)和數(shù)學(xué)等多個(gè)學(xué)科中。各章包含了大量不同難易程度的編程習(xí)題。對(duì)于希望學(xué)習(xí)并行編程技巧、更新知識(shí)面的學(xué)生或?qū)I(yè)人士來說，本書是一本理想的參考書。 ——Leigh Little，紐約州立大學(xué)布羅科波特學(xué)院計(jì)算機(jī)科學(xué)系

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    并行程序設(shè)計(jì)導(dǎo)論 PDF格式下載

---