經(jīng)典并行與量子并行：提升并挖掘計(jì)算系統(tǒng)的潛在性能

推薦序一
推薦序二
前言
第1章　計(jì)算概念的譜系
1.1　引言/ 2　
1.2　計(jì)算概念譜系化的意義/ 3　
1.3　計(jì)算概念的譜系/ 4　
1.3.1　算勢(shì)/ 5　
1.3.2　算力/ 7　
1.3.3　算術(shù)/ 10　
1.3.4　算法/ 11　
1.3.5　算禮/ 13　
1.4　計(jì)算概念譜系組分的相互關(guān)系/ 14　
1.5　從場的角度認(rèn)識(shí)算勢(shì)與算力的異同/ 16　
1.6　證明與計(jì)算之間的關(guān)系/ 20　
1.7　本章小結(jié)/ 23　
1.8　思考題/ 23　
參考文獻(xiàn)/ 23　
第2章　并行處理的意義及挑戰(zhàn)
2.1　引言/ 26　
2.2　并行計(jì)算機(jī)與應(yīng)用和工藝的關(guān)系/ 26　
2.3　并行處理的普遍性/ 28　
2.4　多核微處理器技術(shù)/ 31　
2.5　并行處理需要應(yīng)對(duì)的挑戰(zhàn)/ 35　
2.6　并行處理的學(xué)科任務(wù)/ 40　
2.7　本章小結(jié)/ 41　
2.8　思考題/ 41　
參考文獻(xiàn)/ 41　
第3章　并行處理的一般原理
3.1　引言/ 44　
3.2　馮·諾依曼結(jié)構(gòu)/ 44　
3.3　通過實(shí)例說明指令級(jí)并行與數(shù)據(jù)依賴/ 47　
3.4　通過實(shí)例說明線程級(jí)并行/ 49　
3.5　延遲隱藏和延遲減少/ 55　
3.6　并行處理技術(shù)的圖形化表示/ 60　
3.7　費(fèi)林分類法/ 63　
3.8　指令級(jí)并行/ 65　
3.8.1　流水線技術(shù)/ 65　
3.8.2　指令的動(dòng)態(tài)調(diào)度/ 65　
3.8.3　多發(fā)射技術(shù)/ 66　
3.9　并行計(jì)算機(jī)系統(tǒng)的分類/ 67　
3.9.1　向量計(jì)算機(jī)/ 67　
3.9.2　多處理機(jī)/ 68　
3.9.3　多主機(jī)/ 68　
3.9.4　大規(guī)模并行處理計(jì)算機(jī)/ 68　
3.10　并行結(jié)構(gòu)的類型/ 69　
3.10.1　單處理器的并行結(jié)構(gòu)/ 69　
3.10.2　多處理器的并行結(jié)構(gòu)/ 69　
3.10.3　處理機(jī)結(jié)構(gòu)創(chuàng)新的歷史/ 70　
3.10.4　多核共享內(nèi)存模型/ 73　
3.10.5　多核消息傳遞模型/ 76　
3.11　本章小結(jié)/ 80　
3.12　思考題/ 81　
參考文獻(xiàn)/ 81　
第4章　計(jì)算性能模型和存儲(chǔ)性能模型
4.1　引言/ 84　
4.2　并行執(zhí)行時(shí)間效率模型/ 85　
4.3　可擴(kuò)展定律/ 103　
4.3.1　阿姆達(dá)爾定律/ 103　
4.3.2　古斯塔夫森-巴西斯定律/ 104　
4.3.3　存儲(chǔ)受限的擴(kuò)展定律（孫-倪定律）/ 106　
4.4　并行計(jì)算模型/ 112　
4.4.1　PRAM模型/ 112　
4.4.2　BSP模型/ 114　
4.4.3　LogP模型/ 117　
4.5　程序性能指標(biāo)/ 120　
4.5.1　單道程序工作負(fù)載的性能指標(biāo)/ 120　
4.5.2　多道程序工作負(fù)載的性能指標(biāo)/ 122　
4.6　存儲(chǔ)系統(tǒng)的性能指標(biāo)/ 123　
4.6.1　平均存儲(chǔ)訪問時(shí)間/ 123　
4.6.2　存儲(chǔ)延遲與存儲(chǔ)帶寬/ 124　
4.6.3　單位時(shí)鐘周期完成的存儲(chǔ)訪問數(shù)量/ 126　
4.6.4　并發(fā)平均存儲(chǔ)訪問時(shí)間/ 127　
4.6.5　存儲(chǔ)級(jí)并行性/ 130　
4.6.6　并發(fā)感知的局部性/ 131　
4.7　基準(zhǔn)測(cè)試/ 133　
4.7.1　基準(zhǔn)測(cè)試的定義和分類/ 133　
4.7.2　基準(zhǔn)測(cè)試運(yùn)行的規(guī)范/ 134　
4.7.3　基準(zhǔn)測(cè)試程序組的要求/ 134　
4.7.4　基準(zhǔn)測(cè)試的開發(fā)者/ 135　
4.7.5　性能測(cè)試結(jié)果的總結(jié)/ 136　
4.8　性能評(píng)估方式/ 136　
4.8.1　Roofline模型/ 136　
4.8.2　模擬器/ 151　
4.8.3　需要避免的4個(gè)陷阱/ 160　
4.9　本章小結(jié)/ 161　
4.10　思考題/ 161　
參考文獻(xiàn)/ 161　
第5章　共享存儲(chǔ)結(jié)構(gòu)與編程
5.1　引言/ 164　
5.2　共享存儲(chǔ)體系結(jié)構(gòu)的類型/ 165　
5.3　并行編程模型/ 168　
5.3.1　抽象與實(shí)現(xiàn)的區(qū)別及其實(shí)例/ 168　
5.3.2　通信與協(xié)作/ 176　
5.3.3　通信層面三種并行編程模型的特點(diǎn)/ 187　
5.3.4　混合編程模型/ 188　
5.4　并行處理的流程/ 189　
5.4.1　思路和實(shí)例/ 189　
5.4.2　問題分解/ 193　
5.4.3　任務(wù)分配/ 193　
5.4.4　協(xié)調(diào)/ 194　
5.4.5　進(jìn)程映射/ 194　
5.5　并行編程優(yōu)化/ 205　
5.5.1　靜態(tài)分配與動(dòng)態(tài)分配/ 206　
5.5.2　延遲與帶寬/ 214　
5.5.3　內(nèi)在通信與人為通信/ 217　
5.6　減少通信的技術(shù)/ 221　
5.6.1　利用時(shí)間局部性/ 221　
5.6.2　利用空間局部性/ 222　
5.7　共享內(nèi)存體系結(jié)構(gòu)/ 228　
5.8　共享內(nèi)存體系結(jié)構(gòu)編程——OpenMP/ 242　
5.9　實(shí)驗(yàn)——OpenMP/ 274
5.9.1　實(shí)驗(yàn)——OpenMP求sinx/ 274　
5.9.2　實(shí)驗(yàn)——OpenMP求π值/ 278　
5.9.3　實(shí)驗(yàn)——OpenMP求斐波那契數(shù)列第n項(xiàng)/ 283　
5.9.4　實(shí)驗(yàn)——Gauss-Seidel迭代算法的并行實(shí)現(xiàn)及其優(yōu)化/ 291　
5.10　本章小結(jié)/ 296　
5.11　思考題/ 296　參考文獻(xiàn)/ 296　
第6章　分布式存儲(chǔ)結(jié)構(gòu)與編程
6.1　引言/ 300　
6.2　向量處理機(jī)體系結(jié)構(gòu)/ 300　
6.2.1　結(jié)構(gòu)特點(diǎn)/ 300　
6.2.2　性能分析/ 305　
6.2.3　向量指令并行/ 307　
6.2.4　向量鏈/ 307　
6.2.5　向量分解strip-mining技術(shù)/ 308　
6.2.6　向量條件執(zhí)行/ 308　
6.2.7　壓縮/展開操作/ 309　
6.2.8　向量歸約/ 310　
6.2.9　存儲(chǔ)訪問/ 311　
6.2.10　分散和聚集/ 312　
6.3　SIMD編程/ 327　
6.3.1　SIMD簡介/ 327　
6.3.2　實(shí)現(xiàn)向量化的幾種方法/ 327　
6.3.3　向量化編譯指令/ 328　
6.3.4　向量化過程中的主要挑戰(zhàn)/ 330　
6.3.5　編譯器向量化方式/ 335　
6.3.6　循環(huán)變換/ 339　
6.3.7　數(shù)據(jù)地址對(duì)齊/ 341　
6.3.8　別名/ 341　
6.3.9　條件語句/ 342　
6.3.10　原生SIMD支持/ 342　
6.4　CUDA編程/ 343　
6.4.1　異構(gòu)計(jì)算的定義/ 344　
6.4.2　CUDA/ 345　
6.4.3　GPU的并發(fā)控制/ 346　
6.4.4　GPU的內(nèi)存管理/ 347　
6.4.5　SIMT/ 348　
6.4.6　CUDA編程/ 349　
6.4.7　CUDA與GPU硬件之間的映射/ 355　
6.4.8　深流水線設(shè)計(jì)/ 356　
6.4.9　GPU內(nèi)存/ 356　
6.4.10　GPU并發(fā)策略/ 358　
6.4.11　庫函數(shù)介紹/ 358　
6.5　MPI編程/ 363　
6.5.1　MPI在編程模型內(nèi)的分類定位/ 363　
6.5.2　信息交互模型與通信方式/ 364　
6.5.3　MPI基本函數(shù)/ 367　
6.5.4　MPI程序執(zhí)行（以C on linux為例）/ 370　
6.5.5　MPI集群通信函數(shù)/ 370　
6.6　實(shí)驗(yàn)——編寫MPI并行程序/ 379　
6.6.1　編寫MPI程序并行計(jì)算平均值/ 379　
6.6.2　編寫MPI程序并行計(jì)算矩陣向量乘法/ 381　
6.6.3　編寫MPI程序并行計(jì)算圓周率/ 383　
6.7　實(shí)驗(yàn)——基于CUDA并發(fā)的矩陣乘法/ 386　
6.8　本章小結(jié)/ 391　
6.9　思考題/ 392　
第7章　并行計(jì)算機(jī)系統(tǒng)的互連網(wǎng)絡(luò)
7.1　引言/ 394　
7.2　互連網(wǎng)絡(luò)的基本概念/ 394　
7.2.1　互連網(wǎng)絡(luò)分層架構(gòu)/ 394　
7.2.2　互連網(wǎng)絡(luò)相關(guān)參數(shù)/ 395　
7.3　互連網(wǎng)絡(luò)物理層/ 397　
7.3.1　消息結(jié)構(gòu)/ 397　
7.3.2　物理層流控制/ 397　
7.4　互連網(wǎng)絡(luò)交換層/ 398　
7.4.1　互連網(wǎng)絡(luò)交換層功能與架構(gòu)/ 398　
7.4.2　互連網(wǎng)絡(luò)交換層技術(shù)/ 399　
7.5　互連網(wǎng)絡(luò)路由層/ 402　
7.5.1　互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)/ 402　
7.5.2　互連網(wǎng)絡(luò)路由方式/ 409　
7.5.3　路由協(xié)議結(jié)構(gòu)/ 410　
7.5.4　蝴蝶形拓?fù)浣Y(jié)構(gòu)路由算法/ 411　
7.5.5　維序路由算法/ 412　
7.5.6　死鎖問題/ 413　
7.6　互連網(wǎng)絡(luò)軟件層/ 415　
7.6.1　互連網(wǎng)絡(luò)軟件層架構(gòu)/ 415　
7.6.2　性能分析/ 417　
7.7　本章小結(jié)/ 418　
7.8　思考題/ 419　
第8章　并行計(jì)算機(jī)系統(tǒng)的資源調(diào)度
8.1　引言/ 422　
8.2　相關(guān)工作/ 425　
8.2.1　延遲敏感型應(yīng)用延遲測(cè)量與建模/ 426　
8.2.2　數(shù)據(jù)中心干擾的測(cè)度方法/ 427　
8.2.3　資源管理使能技術(shù)/ 427
8.2.4　資源調(diào)度策略/ 429
8.3　延遲敏感型應(yīng)用分析與建模/ 432　
8.3.1　延遲敏感型應(yīng)用概述/ 433　
8.3.2　延遲敏感型應(yīng)用延遲的組成及影響因素/ 435　
8.3.3　平均延遲與尾延遲的關(guān)系/ 436　
8.3.4　Littles law的尾延遲形式/ 441　
8.4　數(shù)據(jù)中心干擾的測(cè)度/ 444　
8.4.1　信息熵與系統(tǒng)熵/ 445　
8.4.2　場景1：僅存在延遲敏感型應(yīng)用時(shí)/ 445　
8.4.3　場景2：僅存在盡力交付型應(yīng)用時(shí)/ 446　
8.4.4　場景3：延遲敏感型和盡力交付型應(yīng)用混合運(yùn)行時(shí)/ 447　
8.4.5　系統(tǒng)熵的優(yōu)點(diǎn)/ 447　
8.5　資源調(diào)度策略/ 449　
8.5.1　調(diào)度方法/ 450　
8.5.2　實(shí)驗(yàn)驗(yàn)證/ 453　
8.6　本章小結(jié)/ 459　
8.7　思考題/ 460　
參考文獻(xiàn)/ 460　
第9章　并行輸入輸出
9.1　引言/ 468　
9.2　I/O軟件棧/ 468　
9.3　并行文件系統(tǒng)/ 469　
9.4　常見并行文件系統(tǒng)/ 475　
9.4.1　并行虛擬文件系統(tǒng)PVFS/ 475　
9.4.2　通用并行文件系統(tǒng)GPFS/ 478　
9.4.3　集群文件系統(tǒng)Lustre/ 479　
9.5　POSIX/ 482　
9.6　MPI-I/O/ 483　
9.6.1　MPI-I/O的特性/ 483　
9.6.2　MPI-I/O示例/ 485　
9.6.3　MPI-I/O的底層讀寫優(yōu)化/ 487　
9.7　PnetCDF/ 490　
9.8　本章小結(jié)/ 495　
9.9　思考題/ 496　
參考文獻(xiàn)/ 496　
第10章　高速緩存一致性、同步和事務(wù)性內(nèi)存
10.1　引言/ 498　
10.2　高速緩存一致性/ 498　
10.2.1　基于總線的一致性協(xié)議/ 500　
10.2.2　基于目錄的一致性協(xié)議/ 502　
10.3　目錄結(jié)構(gòu)/ 503　
10.3.1　全映射位向量目錄/ 503　
10.3.2　有限指針目錄/ 504　
10.3.3　鏈?zhǔn)侥夸? 505　
10.3.4　粗糙向量目錄/ 506　
10.3.5　樹形壓縮向量目錄/ 506　
10.3.6　單級(jí)混合目錄/ 507　
10.3.7　多級(jí)目錄/ 508　
10.4　實(shí)現(xiàn)高速緩存一致的典型系統(tǒng)/ 511　
10.4.1　Dash/ 511　
10.4.2　Origin 2000/ 512　
10.4.3　Alewife/ 513　
10.4.4　Exemplar X/ 514　
10.4.5　NUMA-Q/ 514　
10.5　同步原語和鎖機(jī)制/ 515　
10.5.1　同步原語/ 515　
10.5.2　互斥鎖的實(shí)現(xiàn)/ 516　
10.5.3　柵障/ 520　
10.5.4　實(shí)驗(yàn)——無鎖算法/ 524　
10.5.5　并行軟件優(yōu)化/ 533　
10.6　事務(wù)性內(nèi)存/ 537　
10.6.1　事務(wù)性內(nèi)存的特性/ 537　
10.6.2　事務(wù)性內(nèi)存的優(yōu)點(diǎn)/ 538　
10.6.3　事務(wù)性內(nèi)存的實(shí)現(xiàn)/ 543　
10.7　本章小結(jié)/ 549　
10.8　思考題/ 549　
參考文獻(xiàn)/ 550　
第11章　量子并行計(jì)算
11.1　引言/ 554　
11.2　對(duì)量子力學(xué)的基本理解/ 555　
11.2.1　量子力學(xué)與經(jīng)典力學(xué)有本質(zhì)區(qū)別/ 555　
11.2.2　量子計(jì)算的優(yōu)勢(shì)在于并行/ 555　
11.2.3　量子的概念/ 555　
11.2.4　不確定性原理/ 556　
11.2.5　對(duì)疊加態(tài)的理解/ 558　
11.2.6　張量積/ 561　
11.2.7　左矢與右矢/ 561　
11.3　幾種重要的熵及其聯(lián)系/ 563　
11.3.1