并行計(jì)算機(jī)體系結(jié)構(gòu)：硬件/軟件結(jié)合的設(shè)計(jì)與分析

第1章 引論
1. 1 為什么要用并行體系結(jié)構(gòu)
1. 1. 1 計(jì)算機(jī)應(yīng)用發(fā)展的趨勢(shì)
1. 1. 2 微電子技術(shù)趨勢(shì)
1. 1. 3 體系結(jié)構(gòu)趨勢(shì)
1. 1. 4 超級(jí)計(jì)算機(jī)
1. 1. 5 小結(jié)
1. 2 并行體系結(jié)構(gòu)的融合
1. 2. 1 通信體系結(jié)構(gòu)
1. 2. 2 共享地址空間
1. 2. 3 消息傳遞
1. 2. 4 融合
1. 2. 5 數(shù)據(jù)并行體系結(jié)構(gòu)
1. 2. 6 其他并行體系結(jié)構(gòu)
1. 2. 7 一個(gè)通用并行體系結(jié)構(gòu)
1. 3 基本的設(shè)計(jì)問(wèn)題
1. 3. 1 通信抽象
1. 3. 2 編程模型的要求
1. 3. 3 通信和復(fù)制
1. 3. 4 性能
1. 3. 5 小結(jié)
1. 4 結(jié)論
1. 5 歷史資料
習(xí)題
第2章 并行程序
2. 1 并行應(yīng)用的案例分析
2. 1. 1 洋流的模擬
2. 1. 2星系演化的模擬
2. 1. 3 用光線跟蹤法來(lái)實(shí)現(xiàn)復(fù)雜場(chǎng)景的可視化
2. 1. 4 針對(duì)關(guān)聯(lián)性的數(shù)據(jù)挖掘
1. 2 并行化過(guò)程
2. 2. 1 程序并行化過(guò)程中的幾個(gè)步驟
2. 2. 2 計(jì)算并行和數(shù)據(jù)并行
2. 2. 3 并行化過(guò)程的目標(biāo)
2. 3 一個(gè)例子程序的并行化
2. 3. 1 方程求解器的內(nèi)核
2. 3. 2 分解
2. 3. 3 分配
2. 3. 4 在數(shù)據(jù)并行模型下的協(xié)調(diào)
2. 3. 5 在共享地址空間模型下的協(xié)調(diào)
2. 3. 6 在消息傳遞模型下的協(xié)調(diào)
2. 4 結(jié)論
習(xí)題
第3章 面向性能的程序設(shè)計(jì)
3. 1 劃分階段的性能問(wèn)題
3. 1. 1 負(fù)載平衡和同步等待時(shí)間
3. 1. 2 減少固有的通信
3. 1. 3 減少額外的工作
3. 1. 4 小結(jié)
3. 2 在多存儲(chǔ)器系統(tǒng)中的數(shù)據(jù)訪問(wèn)和通信
3. 2. 1 看作擴(kuò)展的存儲(chǔ)層次結(jié)構(gòu)的多處理器系統(tǒng)
3. 2. 2 在擴(kuò)展的存儲(chǔ)層次結(jié)構(gòu)中的附加通信
3. 2. 3 用工作集的觀點(diǎn)看附加的通信和數(shù)據(jù)的復(fù)制
3. 3 性能的協(xié)調(diào)
3. 3. 1 減少附加通信
3. 3. 2 將通信結(jié)構(gòu)化以降低代價(jià)
3. 4 從處理器角度看到的性能因素
3. 5 并行應(yīng)用程序案例的深入分析
3. 5. 1　Ocean
3. 5. 2 Bames-Hut
3. 5. 3 光線跟蹤
3. 5. 4 數(shù)據(jù)挖掘
3. 6 編程模型涉及的問(wèn)題
3. 6. 1 命名
3. 6. 2 復(fù)制
3. 6. 3 通信的開(kāi)銷和粒度
3. 6. 4 塊數(shù)據(jù)傳送
3. 6. 5 同步
3. 6. 6 硬件代價(jià)和設(shè)計(jì)復(fù)雜性
3. 6. 7 性能模型
3. 6. 6 小結(jié)
3. 7 結(jié)論
習(xí)題
第4章 工作負(fù)載驅(qū)動(dòng)的性能評(píng)價(jià)
4. 1 改變工作負(fù)載和機(jī)器的規(guī)模
4. 1. 1 多處理器性能的基本測(cè)量
4. 1. 2 為什么要考慮擴(kuò)放性
4. 1. 3 擴(kuò)放的關(guān)鍵問(wèn)題
4. 1. 4 擴(kuò)放模型和加速比的測(cè)量
4. 1. 5 擴(kuò)放模型對(duì)方程求解器內(nèi)核的影響
4. 1. 6　擴(kuò)放工作負(fù)載參數(shù)
4. 2　評(píng)價(jià)一臺(tái)實(shí)際的機(jī)器
4. 2. 1 使用微基準(zhǔn)測(cè)試程序分離性能
4. 2. 2　選擇工作負(fù)載
4. 2. 3 評(píng)價(jià)一臺(tái)固定規(guī)模的機(jī)器
4. 2. 4　改變機(jī)器的規(guī)模
4. 2. 5　選擇性能指標(biāo)
4. 3　對(duì)一個(gè)體系結(jié)構(gòu)概念或設(shè)計(jì)權(quán)衡的評(píng)估
4. 3. 1 多處理器的模擬
4. 3. 2　縮小模擬的問(wèn)題和機(jī)器參女的規(guī)模
4. 3. 3 處理參數(shù)空間：評(píng)價(jià)舉例
4. 3. 4 小結(jié)
4. 4　說(shuō)明工作負(fù)載的特征
4. 4. 1 工作負(fù)載案例分析
4. 4. 2　工作負(fù)載的特征化
4. 5 結(jié)論
習(xí)題
第5章 共享存儲(chǔ)的多處理器
5. 1 高速緩存的一致性
5. 1. 1 高速緩存一致性問(wèn)題
5. 1. 2　通過(guò)總線偵聽(tīng)的高速緩存一致性
5. 2　存儲(chǔ)同一性
5. 2. 1 順序同一性
5. 2. 2　保證順序同一性的充分條件
5. 3 總線偵聽(tīng)協(xié)議的設(shè)計(jì)空間
5. 3. 1 一種三態(tài) MSI 回寫(xiě)作廢式協(xié)議
5. 3. 2 一種四態(tài) MESI 回寫(xiě)作廢式協(xié)議
5. 3. 3 一種四態(tài) Dragon 回寫(xiě)更新式協(xié)議
5. 4 關(guān)于協(xié)議設(shè)計(jì)中若干折中的評(píng)估
5. 4. 1 方法論
5. 4. 2 在MESI協(xié)議下的帶寬需求
5. 4. 3 協(xié)議優(yōu)化的影響
5. 4. 4 高速緩存中存儲(chǔ)塊大小的權(quán)衡
5. 4. 5 基于更新和基于作廢協(xié)議的對(duì)比
5. 5 同步
5. 5. 1 同步事件的組成部分
5. 5. 2 用戶和系統(tǒng)的角色
5. 5. 3 互斥
5. 5. 4 點(diǎn)對(duì)點(diǎn)事件同步
5. 5. 5 全局 柵障 事件的同步
5. 5. 6 同步問(wèn)題小結(jié)
5. 6 對(duì)軟件的影響
5. 7 結(jié)論
習(xí)題
第6章 基于偵聽(tīng)的多處理器的設(shè)計(jì)
6. 1 正確性需求
6. 2 基礎(chǔ)設(shè)計(jì)：采用原子總線的單級(jí)高速緩存
6. 2. 1 高速緩存控制器和標(biāo)記的設(shè)計(jì)
6. 2. 2 偵聽(tīng)結(jié)果的報(bào)告
6. 2. 3 對(duì)回寫(xiě)的處理
6. 2. 4 基礎(chǔ)系統(tǒng)組織
6. 2. 5 非原子性的狀態(tài)轉(zhuǎn)移
6. 2. 6 串行化
6. 2. 7 死鎖
6. 2. 8 活鎖和挨餓
6. 2. 9 原子操作的實(shí)現(xiàn)
6. 3 多級(jí)高速緩存層次結(jié)構(gòu)
6. 3. 1 包含性的維護(hù)
6. 3. 2 在高速緩存層次結(jié)構(gòu)中傳播一致性的事務(wù)
6. 4 事務(wù)拆分型總線
6. 4. 1 事務(wù)拆分型總線設(shè)計(jì)的一個(gè)例子
6. 4. 2 總線設(shè)計(jì)和請(qǐng)求-響應(yīng)的匹配
6. 4. 3 偵聽(tīng)結(jié)果和沖突的請(qǐng)求
6. 4. 4 流控制
6. 4. 5　一次緩存撲空的路線
6. 4. 6 串行化和順序同一性
6. 4. 7　其他設(shè)計(jì)選擇
6. 4. 8 帶有多級(jí)高速緩存的事務(wù)拆分型總線
6. 4. 9　對(duì)一個(gè)處理器有多個(gè)待完成撲空的支持
6. 5 實(shí)例分析：SGI Challenge 和Sun Enterprise 6000
6. 5. 1 SGI Powerpath-2系統(tǒng)總線
6. 5. 2 SGI處理器和內(nèi)存子系統(tǒng)
6. 5. 3 SGI I／O子系統(tǒng)
6. 5. 4 SGI Challenge內(nèi)存系統(tǒng)性能
6. 5. 5 Sun Gigaplane系統(tǒng)總線
6. 5. 6 Sun處理器和內(nèi)存系統(tǒng)
6. 5. 7 Sun I／O子系統(tǒng)
6. 5. 8 Sun Enterprise內(nèi)存系統(tǒng)性能
6. 5. 9 應(yīng)用程序性能
6. 6 高速緩存一致性的擴(kuò)充
6. 6. 1 共享緩存的設(shè)計(jì)
6. 6. 2 虛擬標(biāo)引緩存的一致性
6. 6. 3 轉(zhuǎn)換檢測(cè)緩沖器的一致性
6. 6. 4 環(huán)上基于偵聽(tīng)的高速緩存一致性
6. 6. 5 在基于總線的系統(tǒng)中的數(shù)據(jù)和偵聽(tīng)?zhēng)挼臄U(kuò)展
6. 7 結(jié)論
習(xí)題
第7章 可擴(kuò)展多處理器
7. 1 可擴(kuò)展性
7. 1. 1 帶寬的可擴(kuò)展性
7. 1. 2 時(shí)延的可擴(kuò)展性
7. 1. 3 成本的可擴(kuò)展性
7. 1. 4 物理可擴(kuò)展性
7. 1. 5 通用并行體系結(jié)構(gòu)的可擴(kuò)展性
7. 2 編程模型的實(shí)現(xiàn)
7. 2. 1 基本的網(wǎng)絡(luò)事務(wù)
7. 2. 2 共享地址空間
7. 2. 3 消息傳遞
7. 2. 4 主動(dòng)消息
7. 2. 5 共同的挑戰(zhàn)
7. 2. 6 通信體系結(jié)構(gòu)設(shè)計(jì)空間
7. 3 物理DMA
7. 3. 1 節(jié)點(diǎn)到網(wǎng)絡(luò)的接口
7. 3. 2 通信抽象的實(shí)現(xiàn)
7. 3. 3 案例分析：nCUBE／2
7. 3. 4 典型的局域網(wǎng)接口
7. 4 用戶級(jí)訪問(wèn)
7. 4. 1 節(jié)點(diǎn)到網(wǎng)絡(luò)的接口
7. 4. 2 案例分析：Thinking Machines CM-5
7. 4. 3 用戶級(jí)的處理程序
7. 5 專用消息處理
7. 5. 1 案例分析：Intel Paragon
7. 5. 2 案例分析：Meiko CS-2
7. 6 共享的物理地址空間
7. 6. 1 案例分析：CRAY T3D
7. 6. 2 案例分析：CRAY T3E
7. 6. 3 小結(jié)
7. 7 工作站機(jī)群和工作站網(wǎng)絡(luò)
7. 7. 1 案例分析：Myrinet SBUS Lanai
7. 7. 2 案例分析：PCI存儲(chǔ)器通道
7. 8 并行軟件涉及的問(wèn)題
7. 8. 1 網(wǎng)絡(luò)事務(wù)的性能
7. 8. 2 共享地址空間操作
7. 8. 3 消息傳遞操作
7. 8. 4 應(yīng)用層性能
7. 9 同步
7. 9. 1 加鎖算法
7. 9. 2 柵障算法
7. 10 結(jié)論
習(xí)題
第8章 基于目錄的高速緩存一致性
8. 1 可擴(kuò)展的高速緩存一致性
8. 2 基于目錄方法概述
8. 2. 1 簡(jiǎn)單目錄方案的操作
8. 2. 2 可擴(kuò)展性
8. 2. 3 組織目錄表的其他方法
8. 3 目錄協(xié)議和折中的評(píng)價(jià)
8. 3. 1 目錄方案的數(shù)據(jù)共享模式
8. 3. 2 本地和遠(yuǎn)程通信流量
8. 3. 3 高速緩存塊尺寸的影響
8. 4 目錄協(xié)議設(shè)計(jì)上的挑戰(zhàn)性問(wèn)題
8. 4. 1 性能
8. 4. 2 正確性
8. 5 基于存儲(chǔ)器的目錄協(xié)議：SGI的Origin系統(tǒng)
8. 5. 1 高速緩存一致性協(xié)議
8. 5. 2 關(guān)于正確性問(wèn)題
8. 5. 3 目錄結(jié)構(gòu)的細(xì)節(jié)
8. 5. 4 協(xié)議擴(kuò)展
8. 5. 5 Origin2000硬件概述
8. 5. 6 Hub的實(shí)現(xiàn)
8. 5. 7 性能特征
8. 6 基于高速緩存的目錄協(xié)議：Sequent的NUMA-Q
8. 6. 1 高速緩存一致性協(xié)議
8. 6. 2 關(guān)于正確性問(wèn)題
8. 6. 3 協(xié)議擴(kuò)展
8. 6. 4 NUMA-Q硬件一覽
8. 6. 5 協(xié)議和SMP節(jié)點(diǎn)的交互
8. 6. 6 IQ鏈路的實(shí)現(xiàn)
8. 6. 7 性能特征
8. 6. 8 對(duì)比案例分析：HAL S1多處理器
8. 7 性能參數(shù)和協(xié)議性能
8. 8 同步
8. 8. 1 幾種同步算法的性能
8. 8. 2 實(shí)現(xiàn)原子性原語(yǔ)
8. 9 對(duì)并行軟件的影響
8. 10 高級(jí)論題
8. 10. 1 減少目錄存儲(chǔ)的開(kāi)銷
8. 10. 2 層次式的一致性
8. 11 結(jié)論
習(xí)題
第9章 硬件／軟件功能的折中
9. 1 放松的存儲(chǔ)同一性模型
9. 1. 1 系統(tǒng)規(guī)范說(shuō)明
9. 1. 2 程序員接口
9. 1. 3 翻譯機(jī)制
9. 1. 4 真實(shí)的多處理器系統(tǒng)中的同一性模型
9. 2 克服容量限制
9. 2. 1 第三層高速緩存
9. 2. 2 惟有高速續(xù)存的存儲(chǔ)器體系結(jié)構(gòu)
9. 3 降低硬件成本
9. 3. 1 具有去耦輔助部件的硬件訪問(wèn)控制
9. 3. 2 通過(guò)代碼修改實(shí)現(xiàn)的訪問(wèn)控制
9. 3. 3 基于頁(yè)面的訪問(wèn)控制：共享虛擬存儲(chǔ)器
9. 3. 4 語(yǔ)言和編譯器支持的訪問(wèn)控制
9. 4 綜合：分類和簡(jiǎn)單的COMA
9. 4. 1 綜合：簡(jiǎn)單的COMA和Stache
9. 5 對(duì)并行軟件的影響
9. 6 高級(jí)論題
9. 6. 1 靈活性和CC-NUMA系統(tǒng)中的地址約束
9. 6. 2 以軟件實(shí)現(xiàn)放松的存儲(chǔ)同一性
9. 7 結(jié)論
習(xí)題
第10章 互連網(wǎng)絡(luò)設(shè)計(jì)
10. 1 基本定義
10. 2 基本的通信性能
10. 2. 1 時(shí)延
10. 2. 2 帶寬
10. 3 組織結(jié)構(gòu)
10. 3. 1 鏈路
10. 3. 2 交換機(jī)
10. 3. 3 網(wǎng)絡(luò)接口
10. 4 互連拓?fù)浣Y(jié)構(gòu)
10. 4. 1 全連接網(wǎng)絡(luò)
10. 4. 2 線性陣列和環(huán)
10. 4. 3 多維網(wǎng)格和多維花環(huán)
10. 4. 4 樹(shù)
10. 4. 5 蝶網(wǎng)
10. 4. 6 超立方體
10. 5 對(duì)網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)折中的評(píng)價(jià)
10. 5. 1 無(wú)負(fù)載時(shí)延
10. 5. 2 負(fù)載情況下的時(shí)延
10. 6 路由
10. 6. 1 路由機(jī)制
10. 6. 2 確定性路由
10. 6. 3 免死鎖
10. 6. 4 虛通道
10. 6. 5 上行-下行路由
10. 6. 6 折轉(zhuǎn)模型路由
10. 6. 7 自適應(yīng)路由
10. 7 交換機(jī)的設(shè)計(jì)
10. 7. 1 端口
10. 7. 2 內(nèi)部數(shù)據(jù)通路
10. 7. 3 通道緩沖
10. 7. 4 輸出調(diào)度
10. 7. 5 堆疊式維度交換機(jī)
10. 8 流控
10. 8. 1 并行計(jì)算機(jī)網(wǎng)絡(luò)與局域網(wǎng). 廣域網(wǎng)的對(duì)照
10. 8. 2 鏈路級(jí)的流控
10. 8. 3 端到端的流控
10. 9 案例分析
10. 9. 1 CRAY T3D網(wǎng)絡(luò)
10. 9. 2 IBM SP-1. SP-2網(wǎng)絡(luò)
10. 9. 3 可擴(kuò)展一致性接口
10. 9. 4 SCI的Origin網(wǎng)
10. 9. 5 Myricom網(wǎng)絡(luò)
10. 10 結(jié)論
習(xí)題
第11章 時(shí)延的包容
11. 1 時(shí)延包容技術(shù)概述
11. 1. 1 時(shí)延包容與通信流水線
11. 1. 2 采用技術(shù)
11. 1. 3 基本要求. 優(yōu)點(diǎn)與局限性
11. 2 顯式消息傳遞中的時(shí)延包容
11. 2. 1 通信結(jié)構(gòu)
11. 2. 2 塊數(shù)據(jù)傳送
11. 2. 3 預(yù)通信
11. 2. 4 跨越同一線程中的通信
11. 2. 5 多線程技術(shù)
11. 3 共享地址空間中的時(shí)延包容
11. 4 共享地址空間中的數(shù)據(jù)成塊傳送
11. 4. 1 技術(shù)和機(jī)制
11. 4. 2 策略問(wèn)題和折衷方案
11. 4. 3 性能收益
11. 5 跨越長(zhǎng)時(shí)延事件
11. 5. 1 跨越寫(xiě)操作
11. 5. 2 跨越讀操作
11. 5. 3 小結(jié)
11. 6 共享地址空間中的預(yù)通信
11. 6. 1 沒(méi)有共享數(shù)據(jù)高速緩存的共享地址空間
11. 6. 2 緩存一致的共享地址空間
11. 6. 3 性能收益
11. 6. 4 小結(jié)
11. 7 共享地址空間中的多線程技術(shù)
11. 7. 1 技術(shù)和機(jī)制
11. 7. 2 性能收益
11. 7. 3 阻塞方式的實(shí)現(xiàn)問(wèn)題
11. 7. 4 交替方式的實(shí)現(xiàn)問(wèn)題
11. 7. 5 在多發(fā)布處理器中集成多線程
11. 8 免鎖定的緩存設(shè)計(jì)
11. 9 結(jié)論
習(xí)題
第12章 將來(lái)的發(fā)展方向
12. 1 技術(shù)與體系結(jié)構(gòu)
12. 1. 1 演變趨勢(shì)
12. 1. 2 遇到的阻礙
12. 1. 3 潛在的突破
12. 2 應(yīng)用程序和系統(tǒng)軟件
12. 2. 1 演變趨勢(shì)
12. 2. 2 遇到的困難
12. 2. 3 潛在的突破
附錄 并行基準(zhǔn)測(cè)試程序集
參考文獻(xiàn)
索引