并行計算：模型與算法( 簡體 字) | |
| 作者：張云泉 袁良 著 | 類別：1. -> 程式設計 -> 綜合 |
| 出版社：機械工業出版社 |  3dWoo書號： 44682詢問書籍請說出此書號！ 有庫存 NT售價： 245 元 |
| 出版日：7/1/2016 | |
| 頁數：201 | |
| 光碟數：0 | |
站長推薦：   | |
| 印刷：黑白印刷 | 語系： ( 簡體 字 ) |
| ISBN：9787111533405 | 加入購物車 │加到我的最愛 (請先登入會員) |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證, 繁體書的下載亦請直接連絡出版社) | |
前言
第1章緒論1 1.1模型1 1.1.1白盒模型1 1.1.2黑盒模型2 1.2計算模型3 1.2.1計算能力模型3 1.2.2算法設計模型7 1.3并行計算模型8 1.3.1基本度量參數9 1.3.2基本并行計算模型11 1.4相關概念13 1.4.1系統結構模型13 1.4.2并行編程模型18 1.4.3并行編程模式22 1.4.4基準測試程序23 1.4.5數據一致性模型25 1.4.6并行、并發與分布式27 1.5并行算法設計30 1.5.1并行算法表示30 1.5.2算法復雜度31 1.5.3問題31 1.6小結33 第2章固定結構并行計算模型34 2.1邏輯電路35 2.1.1定義35 2.1.2加法器35 2.2比較器電路39 2.2.1定義39 2.2.2歸并39 2.2.3排序44 2.2.4選擇46 2.3代數電路48 2.3.1定義48 2.3.2FFT48 2.3.3前綴和51 2.4線性陣列53 2.4.1定義53 2.4.2排序54 2.4.3三角矩陣求解57 2.5混洗連接59 2.5.1定義59 2.5.2排序60 2.5.3FFT62 2.5.4矩陣轉置62 2.6網格64 2.6.1定義64 2.6.2歸并64 2.6.3排序66 2.6.4矩陣乘68 2.6.5迭代法70 2.7樹形71 2.7.1定義71 2.7.2排序73 2.7.3前綴和74 2.7.4圖的連通分量75 2.8超立方76 2.8.1定義76 2.8.2排序77 2.8.3通信78 2.9小結79 2.10習題80 第3章共享存儲并行計算模型(計算復雜度)83 3.1PRAM模型83 3.1.1定義83 3.1.2模型的能力84 3.1.3算法設計技術85 3.1.4問題下界85 3.2PRAM變體86 3.2.1APRAM86 3.2.2分相PRAM87 3.3選擇88 3.3.1EREW上的成本最優算法88 3.3.2CRCW上的常數時間算法89 3.3.3縮減處理器90 3.3.4算法級聯91 3.3.5下界92 3.4歸并93 3.4.1CREW上的常數時間算法93 3.4.2縮減處理器94 3.5查找95 3.5.1CREW上的最優時間算法95 3.5.2下界95 3.6排序95 3.6.1枚舉排序96 3.6.2Preparata排序96 3.6.3下界97 3.7前綴和98 3.7.1倍增法98 3.7.2算法級聯98 3.8圖算法99 3.8.1分層倍增法99 3.8.2歐拉回路101 3.8.3Ear分解103 3.8.4破對稱方法104 3.9小結105 3.10習題106 第4章分布式存儲并行計算模型(通信復雜度)107 4.1通信復雜度模型107 4.1.1LPRAM模型107 4.1.2Yao模型109 4.2延遲帶寬模型110 4.2.1LogP模型110 4.2.2Postal模型111 4.2.3LogGP模型115 4.3其他模型116 4.3.1BSP116 4.3.2QSM116 4.3.3BPRAM模型117 4.4小結117 第5章存儲層次并行計算模型(存儲復雜度)118 5.1單層存儲層次118 5.2兩層存儲層次121 5.2.1紅藍卵石模型121 5.2.2分塊傳輸模型124 5.3多層存儲層次126 5.3.1多層卵石模型127 5.3.2HMM128 5.3.3分塊HMM131 5.3.4RAM(h)模型132 5.4緩存無關模型133 5.4.1串行模型134 5.4.2并行模型136 5.5小結138 5.6習題139 第6章并行程序性能模型141 6.1性能模型與計算模型141 6.2加速比模型142 6.2.1Amdahl模型142 6.2.2Gustafson模型142 6.2.3Karp-Flatt模型144 6.2.4Sun-Ni模型145 6.2.5等效率模型145 6.2.6DAG模型146 6.3訪存序列模型147 6.3.1缺失率147 6.3.2重用距離148 6.3.3平均足跡149 6.3.4多進程模型150 6.4軟硬協同模型151 6.4.1計算密集度151 6.4.2串行平衡模型152 6.4.3并行平衡模型152 6.4.4Hill-Marty模型153 6.5算法優化模型154 6.5.1算法級聯154 6.5.2參數優化155 6.6小結156 第7章并發與分布式算法157 7.1互斥算法157 7.1.1共享存儲算法157 7.1.2分布式存儲算法164 7.1.3基于硬件操作170 7.1.4基于信號量操作172 7.2鎖算法174 7.2.1自旋鎖174 7.2.2讀寫鎖177 7.3同步算法179 7.3.1分布式存儲算法179 7.3.2共享存儲算法181 7.4隊列算法183 7.4.1有界隊列184 7.4.2無界隊列185 7.5廣播算法188 7.5.1洪水算法188 7.5.2生成樹算法188 7.6小結189 7.7習題189 參考文獻191 本書系統介紹了三代并行計算模型及其并行算法、并行程序性能模型以及并發和分布式算法，書中算法均用精簡的偽碼實現，利于讀者掌握最為精髓的并行算法設計思路。
本書特點 結合具體算法，展現并行計算技術的魅力，書中的許多內容來源于作者的科研和工作成果。 前沿、實用的內容，總結了并行算法的新技術和新理念，梳理了當前并行計算中的模型和算法。 清晰、嚴謹的敘述，針對并行計算中的主要方法，從原理、算法等多個角度進行闡述，講解算法設計精髓。 內容簡介 第1章是緒論，首先對模型、計算模型和并行計算模型進行簡要介紹，然后介紹并行計算領域中的一些相關概念，以及本書所用到的并行算法表述方法和問題定義；第2章介紹固定結構并行計算模型，抽象程度相對較低，是后續章節的基礎，重點討論處理器構成的固定結構網絡的計算性能；第3章介紹共享存儲并行計算模型，重點討論計算復雜度；第4章介紹分布式存儲并行計算模型，著重討論通信復雜度；第5章介紹存儲層次并行計算模型，重點關注存儲復雜度；第6章綜合討論并行程序的性能模型；第7章討論并發與分布式算法。 處理器是計算機系統的核心。由于摩爾定律的作用，對于體系結構的設計可以利用更多數量的晶體管來開發并行性，這使得處理器性能在2005年之前一直保持指數級增長，并且程序無須改變即可享用“免費的午餐”。但是，首先，時鐘頻率的提升已逼近物理極限，無法像以前一樣從升級的高頻單核處理器中獲得免費的性能提升；其次，指令級并行，例如超標量發射和流水線技術對性能提升的潛力已基本發揮到極致，多年來沒有更為顯著的技術突破；最后，數據級并行，例如處理器的單指令多數據(SIMD)指令集，可以在一定程度上繼續增加處理器的絕對峰值性能，但受限于帶寬和片上硬件的資源，以及算法和編譯的軟件優化難度。總之，多核、眾核處理器等利用線程級并行繼續提升片上計算能力的方法已成為硬件發展的唯一道路。
算法是計算機科學的核心。由上所述，處理器體系結構的趨勢是更多地利用線程級并行性，這一轉變使得程序員必須設計過去只有在大型并行系統上才用到的并行算法，才能充分利用硬件計算能力。串行算法教科書通常使用RAM作為串行計算模型，并多以具體問題（排序、圖算法、字符串等）或算法設計技巧（分而治之、動態規劃、隨機方法等）來組織內容。但并行算法的設計與底層并行機制緊密相關，因此我們以并行計算模型組織本書內容。首先，不同的模型適用于不同的問題；其次，對于同一問題在不同模型下從不同角度研究算法特征。 好算法不言自明，這是撰寫本書時的核心思想。Knuth認為計算機程序設計是一門藝術而非科學，因此每個好算法都是一件精美的藝術品。相比于文字解釋，作者相信使用精致優美的偽碼表述的算法能進行自我說明，是藝術品最原始、最真實的展現。我們鼓勵讀者以算法偽碼為中心閱讀本書，而將文字看作對偽碼的簡要說明。然而，限于作者水平，加之時間倉促，書中定有不少欠妥和錯誤之處，懇請讀者批評指正。 | |
