《高性能計算機系統(tǒng)導(dǎo)論》教學(xué)大綱
課程名稱：
| 高性能計算機系統(tǒng)導(dǎo)論
|
|
|
課程編號：
| 408420
| 420418
| 436420
|
適用專業(yè)：
| 計算機科學(xué)與技術(shù)
| 網(wǎng)絡(luò)工程
| 軟件工程
|
課程類別：
| 專業(yè)任選
| 專業(yè)任選
| 專業(yè)任選
|
課程學(xué)分：
| 2
|
|
|
總學(xué)時：
| 36
|
|
|
其中：理論學(xué)時
| 24
|
|
|
實驗學(xué)時
| 12
|
|
|
先修課程：
| C語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、計算機體系結(jié)構(gòu)
|
一、課程的性質(zhì)、目的與任務(wù)
本課程是為計算機科學(xué)與技術(shù)專業(yè)、網(wǎng)絡(luò)工程和軟件工程的高年級本科生開設(shè)的專業(yè)課，也可作為面向科學(xué)和工程計算的非計算機專業(yè)的高年級本科生和研究生的選修課程。通過此課程的學(xué)習(xí)，可使學(xué)生了解和掌握計算機學(xué)科中以及大型科學(xué)與工程問題中的基本的并行與分布計算方法及其軟硬基礎(chǔ)。
二、課程教學(xué)基本內(nèi)容
第一篇 并行計算硬件基礎(chǔ)
第一章 并行計算機系統(tǒng)及其結(jié)構(gòu)模型
1.1 并行計算
1.1.1 并行計算與計算科學(xué)
1.1.2 當(dāng)代科學(xué)與工程問題的計算需求
1.2 并行計算機系統(tǒng)互連
1.2.1 系統(tǒng)互連
1.2.2 靜態(tài)互連網(wǎng)絡(luò)
1.2.3 動態(tài)互連網(wǎng)絡(luò)
1.2.4 標(biāo)準(zhǔn)互連網(wǎng)絡(luò)
1.3 并行計算機系統(tǒng)結(jié)構(gòu)
1.3.1 并行計算機結(jié)構(gòu)模型
1.3.2 并行計算機訪存模型
1.3.3 并行計算機存儲組織
第二章 當(dāng)代并行計算機系統(tǒng)介紹
2.1 共享存儲多處理機系統(tǒng)
2.1.1 對稱多處理機SMP結(jié)構(gòu)特性
2.1.2 CC-NUMA Origin 2000超級服務(wù)器
2.2 分布存儲多計算機系統(tǒng)
2.2.1 大規(guī)模并行處理機MPP結(jié)構(gòu)特性
2.2.2 ASCI Option Red MPP系統(tǒng)
2.3 機群系統(tǒng)
2.3.1 大規(guī)模并行處理系統(tǒng)MPP機群SP2
2.3.2 工作站機群COW
2.3.3 Berkeley的NOW計劃
第三章 并行計算性能評測
3.1 并行計算機的一些基本性能指標(biāo)
3.1.1 CPU和存儲器的某些基本性能指標(biāo)
3.1.2 通信開銷
3.1.3 機器的成本、價格與性能/價格比
3.2 加速比性能定律
3.2.1 Amdahl定律
3.2.2 Gustafson定律
3.2.3 Sun和Ni定律
3.2.4 有關(guān)加速的討論
3.3 可擴放性評測標(biāo)準(zhǔn)
3.3.1 并行計算的可擴放性
3.3.2 等效率度量標(biāo)準(zhǔn)
3.3.3 等速度度量標(biāo)準(zhǔn)
3.3.4 平均延遲度量標(biāo)準(zhǔn)
3.3.5 有關(guān)可擴放性標(biāo)準(zhǔn)的討論
3.4 基準(zhǔn)測試程序
3.4.1 基本的測試程序
3.4.2 數(shù)學(xué)庫測試程序
3.4.3 并行測試程序
第二篇 并行算法的設(shè)計
第四章 并行算法的設(shè)計基礎(chǔ)
4.1 并行算法的基礎(chǔ)知識
4.1.1 并行算法的定義和分類
4.1.2 并行算法的表達(dá)
4.1.3 并行算法的復(fù)雜性度量
4.1.4 并行算法中的同步與通信
4.2 并行計算模型
4.2.1 PRAM模型
4.2.2 異步PRAM模型
4.2.3 BSP模型
4.2.4 logP模型
4.2.5 對BSP和logP的評注
第五章 并行算法的一般設(shè)計策略
5.1 串行算法的直接并行化
5.1.1 設(shè)計策略描述
5.1.2 快排序算法的并行化
5.2 從問題描述開始設(shè)計并行算法
5.2.1 串匹配算法
5.2.2 KMP串行串匹配算法
5.2.3 并行串匹配算法的設(shè)計思路
5.3 借用已有算法求解新問題
5.3.1 設(shè)計策略描述
5.3.2 利用矩陣乘法求所有點對間最短路徑
第六章 并行算法的基本設(shè)計技術(shù)
6.1 劃分設(shè)計技術(shù)
6.1.1 均勻劃分技術(shù)
6.1.2 方根劃分技術(shù)
6.1.3 對數(shù)劃分技術(shù)
6.1.4 功能劃分技術(shù)
6.2 分治設(shè)計技術(shù)
6.2.1 雙調(diào)歸并網(wǎng)絡(luò)
6.2.2 凸殼問題
6.3 平衡樹設(shè)計技術(shù)
6.3.1 求取最大值
6.3.2 計算前綴和
6.4 倍增設(shè)計技術(shù)
6.4.1 表序問題的計算
6.4.2 求森林的根
6.5 流水線設(shè)計技術(shù)
6.5.1 一維心動陣列上的DFT計算
6.5.2 一維心動陣列上的卷積計算
第七章 并行算法的一般設(shè)計過程
7.1 PCAM設(shè)計方法學(xué)
7.2 劃分
7.2.1 域分解
7.2.2 功能分解
7.2.3 劃分判據(jù)
7.3 通信
7.3.1 局部通信
7.3.2 全局通信
7.3.3 非結(jié)構(gòu)化、動態(tài)和異步通信
7.3.4 通信判據(jù)
7.4 組合
7.4.1 增加粒度
7.4.2 保持靈活性和減少軟件工程成本
7.4.3 組合判據(jù)
7.5 映射
7.5.1 負(fù)載平衡算法
7.5.2 任務(wù)調(diào)度算法
7.5.3 映射判據(jù)
第三篇 并行數(shù)值算法
第八章 基本通信操作
8.1 選路方法與開關(guān)技術(shù)
8.1.1 選路方法
8.1.2 開關(guān)技術(shù)
8.2 單一信包一到一傳輸
8.3 一到多播送
8.3.1 使用SF進(jìn)行一到多播送
8.3.2 使用CT進(jìn)行一到多播送
8.4 多到多播送
8.4.1 使用SF進(jìn)行多到多播送
8.4.2 使用CT進(jìn)行多到多播送
第九章 稠密矩陣運算
9.1 矩陣的劃分
9.1.1 帶狀劃分
9.1.2 棋盤劃分
9.2 矩陣轉(zhuǎn)置
9.2.1 棋盤劃分的矩陣轉(zhuǎn)置
9.2.2 帶狀劃分的矩陣轉(zhuǎn)置
9.3 矩陣-向量乘法
9.3.1 帶狀劃分的矩陣-向量乘法
9.3.2 棋盤劃分的矩陣-向量乘法
9.4 矩陣乘法
9.4.1 簡單并行分塊乘法
9.4.2 Cannon乘法
9.4.3 Fox乘法
9.4.4 DNS乘法
第十章 線性方程組的求解
10.1 三角形方程組的求解
10.1.1 基本術(shù)語
10.1.2 上三角方程組的求解
10.2 三對角方程組的求解
10.2.1 三對角方程組直接求解法
10.2.2 三對角方程組奇偶?xì)w約求解法
10.3 稠密線性方程組的求解
10.3.1 有回代的高斯消去法
10.3.2 無回代的高斯-約旦法
10.3.3 迭代求解的高斯-賽德爾法
10.4 稀疏線性方程組的求解
10.4.1 稀疏矩陣的存儲方式
10.4.2 雅可比迭代法
10.4.3 高斯-賽德爾迭代法
10.4.4 超松弛迭代法
10.4.5 多重網(wǎng)格法
10.4.6 共軛梯度法
第十一章 快速傅里葉變換
11.1 離散傅氏變換
11.1.1 預(yù)備知識
11.1.2 離散傅里葉變換
11.1.3 離散傅里葉逆變換
11.1.4 離散傅氏變換的蝶式計算
11.2 快速傅氏變換串行算法
11.2.1 串行FFT迭代算法
11.2.2 串行FFT遞歸算法
11.3 并行FFT算法
11.3.1 SIMD-MC2上FFT算法
11.3.2 SIMD-BF上FFT算法
11.3.3 SIMD-CC上FFT算法
11.3.4 MIMD-DM上FFT算法
第四篇 并行程序設(shè)計
第十二章 并行程序設(shè)計基礎(chǔ)
12.1 并行程序設(shè)計概述
12.1.1 串行程序設(shè)計與并行程序設(shè)計
12.1.2 并行程序設(shè)計環(huán)境與工具
12.1.3 并行程序設(shè)計方法
12.1.4 并行編程風(fēng)范
12.2 進(jìn)程
12.2.1 進(jìn)程的基本概念
12.2.2 進(jìn)程的并行執(zhí)行
12.2.3 進(jìn)程的相互作用
12.3 線程
12.3.1 線程的基本概念
12.3.2 線程的管理
12.3.3 線程的同步
12.4 同步
12.4.1 原子與互斥
12.4.2 高級同步結(jié)構(gòu)
12.4.3 低級同步原語
12.5 通信
12.5.1 影響通信系統(tǒng)性能的因素
12.5.2 低級通信支持
12.5.3 TCP / IP通信協(xié)議組簡介
12.6 并行程序設(shè)計模型
12.6.1 計算π樣本程序
12.6.2 隱式并行模型
12.6.3 數(shù)據(jù)并行模型
12.6.4 消息傳遞模型
12.6.5 共享變量模型
12.6.6 并行程序設(shè)計模型比較
第十三章 共享存儲系統(tǒng)并行編程
13.1 基于共享變量的共享存儲并行編程
13.1.1 共享存儲并行編程的基本問題
13.1.2 共享存儲編程環(huán)境
13.2 早期共享存儲并行編程模型
13.2.1 ANSI X3H5共享存儲模型
13.2.2 POSIX線程模型
13.3 OpenMP編程簡介
13.3.1 OpenMP概述
13.3.2 OpenMP編程風(fēng)格
13.3.3 OpenMP編程要素
13.3.4 OpenMP計算實例
13.3.5 運行庫例程與環(huán)境變量
第十四章 分布存儲系統(tǒng)并行編程
14.1 基于消息傳遞的并行編程
14.1.1 SPMD并行程序
14.1.2 MPMD并行程序
14.2 MPI并行編程
14.2.1 最基本的MPI
14.2.2 群體通信
14.2.3 通信體
14.2.4 導(dǎo)出數(shù)據(jù)類型
14.2.5 點到點通信
14.3 PVM并行編程
14.3.1 PVM概貌
14.3.2 PVM消息傳遞庫
14.4 基于數(shù)據(jù)并行的并行編程
14.4.1 數(shù)據(jù)并行模型的特點
14.4.2 數(shù)據(jù)并行編程的基本問題
14.5 HPF并行編程
14.5.1 HPF的語言特點
14.5.2 HPF的數(shù)據(jù)并行機制
14.5.3 HPF使用中的若干問題
第十五章 并行程序設(shè)計環(huán)境與工具
15.1 軟件工具與環(huán)境
15.1.1 編碼工具
15.1.2 軟件工程工具
15.1.3 集成工具
15.1.4 將來的工具與環(huán)境
15.2 并行編譯器
15.2.1 編譯及其并行化
15.2.2 相關(guān)分析
15.2.3 代碼優(yōu)化
15.2.4 代碼生成
15.3 并行程序調(diào)試
15.3.1 并行程序調(diào)試的方法與步驟
15.3.2 并行程序的調(diào)試技術(shù)
15.3.3 并行程序的性能調(diào)試
15.4 并行程序性能分析
15.4.1 并行程序的性能預(yù)測
15.4.2 并行程序的性能監(jiān)控
15.4.3 并行程序的性能可視化
15.5 圖形化并行程序集成開發(fā)環(huán)境
15.5.1 并行程序的可視化設(shè)計環(huán)境與工具
15.5.2 圖形應(yīng)用開發(fā)環(huán)境GRADE的組成
15.5.3 GRADE中開發(fā)并行程序過程
三、課程各章節(jié)學(xué)時分配
序號
| 內(nèi)容
| 理論學(xué)時
| 實驗學(xué)時
|
計科
| 網(wǎng)工
| 軟工
| 計科
| 網(wǎng)工
| 軟工
|
1
| 并行計算機系統(tǒng)結(jié)構(gòu)和模型
| 2
| 2
| 2
| 0
| 0
| 0
|
2
| 并行計算機系統(tǒng)互連
| 2
| 2
| 2
| 0
| 0
| 0
|
3
| 并行系統(tǒng)性能評價
| 2
| 2
| 2
| 2
| 2
| 2
|
4
| 并行計算模型(PRAM，APRAM，BSP，LogP，C3)
| 2
| 2
| 2
| 0
| 0
| 0
|
5
| 并行算法的常用設(shè)計方法
| 4
| 4
| 4
| 2
| 2
| 2
|
6
| 并行算法的基本設(shè)計技術(shù)
| 4
| 4
| 4
| 2
| 2
| 2
|
7
| 并行程序設(shè)計模型
| 2
| 2
| 2
| 0
| 0
| 0
|
8
| 共享存儲編程
| 2
| 2
| 2
| 2
| 2
| 2
|
9
| 消息傳遞編程
| 4
| 4
| 4
| 4
| 4
| 4
|
合計
| 24
| 24
| 24
| 12
| 12
| 12
|
四、本課程課外學(xué)習(xí)與修學(xué)指導(dǎo)
由于該課程涉及高性能計算機系統(tǒng)中各種軟硬件資源的管理，內(nèi)容復(fù)雜，難度較大，且具有很強的實踐性，所以要學(xué)好本課程，必須做到理論與實踐緊密結(jié)合，才能達(dá)到較好的學(xué)習(xí)效果。要求學(xué)生多參閱相關(guān)書籍，多做練習(xí)，多上機實驗，掌握高性能計算機系統(tǒng)的基本原理、主要算法及其實現(xiàn)過程。
五、本課程考核方式及成績評定標(biāo)準(zhǔn)
考核方式：閉卷考試
成績評定方法：本課程的考核是平時成績、實驗成績和期終考試成績相結(jié)合。具體比例為：上課出勤、作業(yè)占20%，實驗占20%，期末考試成績占60%。
其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%?？荚囶}型主要有：選擇題、填空題、簡答題、計算題、算法題、分析題、綜合應(yīng)用題等。
六、教材及參考書
教材：陳國良，《并行計算：結(jié)構(gòu)，算法，編程》，北京：高教出版社，1999(初版)，2003(修訂版)
主要參考書：
[1]陳國良等，《并行計算機體系結(jié)構(gòu)》，北京：高教出版社，2002
[2]陳國良，《并行算法的設(shè)計與分析》，北京：高教出版社，2002 (修訂版)
[3]陳國良等，《并行算法實踐》，北京：高教出版社，2003
大綱撰寫人：彭東海
大綱審閱人：袁輝勇
教學(xué)副主任：易葉青
編寫日期：2012.6
