異構(gòu)計(jì)算系統(tǒng)調(diào)度理論與方法

目錄
《博士后文庫(kù)》序言
前言
第1章 緒論 1
1.1 高性能計(jì)算機(jī)發(fā)展歷程 1
1.2 異構(gòu)計(jì)算系統(tǒng)概述 2
1.3 典型異構(gòu)計(jì)算 3
1.3.1 P2P計(jì)算 3
1.3.2 集群計(jì)算 4
1.3.3 網(wǎng)格計(jì)算 5
1.3.4 多核CPU與眾核協(xié)同計(jì)算 8
1.3.5 云計(jì)算 9
1.4 小結(jié) 12
第2章 異構(gòu)系統(tǒng)任務(wù)調(diào)度 13
2.1 異構(gòu)系統(tǒng)資源特征 13
2.2 資源管理與任務(wù)調(diào)度 13
2.3 異構(gòu)分布式系統(tǒng)資源管理 14
2.3.1 SLURM 14
2.3.2 PBS 14
2.3.3 YARN 15
2.4 調(diào)度問(wèn)題分類 15
2.5 任務(wù)間具有優(yōu)先約束DAG調(diào)度模型 17
2.5.1 DAG應(yīng)用程序?qū)嵗?17
2.5.2 基于DAG的應(yīng)用任務(wù)圖 18
2.5.3 目標(biāo)處理系統(tǒng) 19
2.6 基于DAG模型調(diào)度策略 19
2.7 啟發(fā)式調(diào)度算法 22
2.8 經(jīng)典啟發(fā)式調(diào)度算法 24
2.8.1 DLS算法 24
2.8.2 MH算法 25
2.8.3 HEFT算法 26
2.9 小結(jié) 27
第3章 基于動(dòng)態(tài)通信競(jìng)爭(zhēng)的調(diào)度算法 28
3.1 考慮通信競(jìng)爭(zhēng)調(diào)度技術(shù)概述 28
3.2 任意處理機(jī)網(wǎng)絡(luò)異構(gòu)系統(tǒng)優(yōu)先權(quán)計(jì)算問(wèn)題 29
3.3 動(dòng)態(tài)通信競(jìng)爭(zhēng)調(diào)度算法 30
3.3.1 表調(diào)度算法優(yōu)化目標(biāo)函數(shù) 30
3.3.2 考慮動(dòng)態(tài)通信競(jìng)爭(zhēng)的通信鏈路搜索算法 31
3.3.3 調(diào)度算法 32
3.3.4 算法時(shí)間復(fù)雜度分析 33
3.4 調(diào)度算法實(shí)例 34
3.5 實(shí)驗(yàn)與性能評(píng)價(jià) 35
3.5.1 隨機(jī)應(yīng)用程序任務(wù)圖 35
3.5.2 任意處理機(jī)網(wǎng)絡(luò)計(jì)算系統(tǒng) 36
3.5.3 隨機(jī)應(yīng)用程序?qū)嶒?yàn)結(jié)果 36
3.5.4 實(shí)際應(yīng)用問(wèn)題 39
3.6 考慮動(dòng)態(tài)通信競(jìng)爭(zhēng)并行調(diào)度策略 41
3.6.1 并行表調(diào)度算法概述 41
3.6.2 基于動(dòng)態(tài)通信競(jìng)爭(zhēng)的并行表調(diào)度算法 42
3.7 小結(jié) 43
第4章 任務(wù)復(fù)制調(diào)度策略 44
4.1 任務(wù)調(diào)度體系結(jié)構(gòu) 44
4.2 任務(wù)調(diào)度定義 45
4.2.1 基于異構(gòu)系統(tǒng)的DAG 任務(wù)調(diào)度權(quán)值 45
4.2.2 任務(wù)調(diào)度屬性 46
4.3 基于任務(wù)復(fù)制的表調(diào)度算法 47
4.3.1 任務(wù)優(yōu)先級(jí)計(jì)算 47
4.3.2 任務(wù)復(fù)制與調(diào)度 48
4.3.3 算法時(shí)間復(fù)雜度分析 49
4.4 性能評(píng)價(jià) 49
4.4.1 隨機(jī)應(yīng)用程序DAG任務(wù)圖 50
4.4.2 考慮異構(gòu)系統(tǒng)特性的優(yōu)先級(jí)計(jì)算方法實(shí)驗(yàn)結(jié)果 51
4.4.3 隨機(jī)DAG任務(wù)實(shí)驗(yàn)結(jié)果 52
4.4.4 實(shí)際應(yīng)用程序?qū)嶒?yàn)結(jié)果 54
4.5 小結(jié) 54
第5章 可靠性感知的任務(wù)調(diào)度 55
5.1 異構(gòu)系統(tǒng)可靠性 55
5.1.1 可靠性概述 55
5.1.2 計(jì)算系統(tǒng)故障特性 56
5.2 可靠性感知調(diào)度研究 57
5.2.1 系統(tǒng)可靠性與任務(wù)調(diào)度 57
5.2.2 軟件容錯(cuò)技術(shù) 58
5.2.3 可靠性分析技術(shù) 59
5.2.4 可靠容錯(cuò)調(diào)度 59
5.3 可靠性調(diào)度模型 60
5.3.1 計(jì)算資源模型 61
5.3.2 可靠性感知的調(diào)度體系結(jié)構(gòu) 62
5.3.3 并行任務(wù)執(zhí)行基本概念 62
5.4 可靠性分析 63
5.4.1 鏈路競(jìng)爭(zhēng)通信路經(jīng)查找 63
5.4.2 通信可靠性分析 64
5.4.3 任務(wù)可靠性分析 65
5.5 任務(wù)調(diào)度算法 66
5.5.1 任務(wù)優(yōu)先級(jí)計(jì)算 66
5.5.2 任務(wù)復(fù)制策略 67
5.6 仿真實(shí)驗(yàn)結(jié)果 68
5.6.1 性能評(píng)價(jià)指標(biāo) 68
5.6.2 仿真實(shí)驗(yàn)平臺(tái) 68
5.6.3 隨機(jī)產(chǎn)生應(yīng)用程序 69
5.6.4 隨機(jī)應(yīng)用程序?qū)嶒?yàn)結(jié)果 69
5.6.5 實(shí)際應(yīng)用問(wèn)題性能評(píng)價(jià) 72
5.7 小結(jié) 73
第6章 網(wǎng)格分層調(diào)度理論 74
6.1 網(wǎng)格分層調(diào)度模型 74
6.1.1 層次體系結(jié)構(gòu) 74
6.1.2 分布式并行應(yīng)用程序 75
6.2 虛擬節(jié)點(diǎn)局部任務(wù)調(diào)度 75
6.2.1 虛擬節(jié)點(diǎn) 76
6.2.2 任務(wù)執(zhí)行行為可靠性分析 76
6.2.3 局部調(diào)度算法 79
6.2.4 局部調(diào)度算法時(shí)間復(fù)雜度分析 81
6.3 全局任務(wù)調(diào)度 81
6.3.1 應(yīng)用程序可靠性分析 81
6.3.2 可靠性驅(qū)動(dòng)的層次調(diào)度算法 82
6.4 性能評(píng)價(jià) 83
6.4.1 性能評(píng)價(jià)標(biāo)準(zhǔn) 84
6.4.2 隨機(jī)產(chǎn)生的分布式應(yīng)用程序?qū)嶒?yàn)結(jié)果 84
6.4.3 實(shí)際應(yīng)用程序?qū)嶒?yàn)結(jié)果 88
6.5 小結(jié) 89
第7章 考慮任務(wù)執(zhí)行行為安全性調(diào)度方法 90
7.1 異構(gòu)計(jì)算系統(tǒng)安全可信性 90
7.2 可信計(jì)算與考慮安全性的調(diào)度研究 91
7.3 考慮安全性的應(yīng)用程序模型 94
7.4 信任值動(dòng)態(tài)量化計(jì)算 95
7.4.1 信任的定義 96
7.4.2 實(shí)體間信任的動(dòng)態(tài)特性 97
7.4.3 基于微分對(duì)策技術(shù)的信任計(jì)算方法 98
7.4.4 信任值計(jì)算實(shí)例 100
7.5 任務(wù)執(zhí)行行為安全性開(kāi)銷(xiāo) 101
7.5.1 安全開(kāi)銷(xiāo)模型 101
7.5.2 任務(wù)安全性分析 102
7.6 任務(wù)執(zhí)行行為安全性調(diào)度算法 103
7.6.1 任務(wù)優(yōu)先級(jí)計(jì)算 104
7.6.2 安全性驅(qū)動(dòng)的任務(wù)調(diào)度算法 104
7.6.3 時(shí)間復(fù)雜度分析 105
7.7 算法性能評(píng)價(jià) 106
7.7.1 隨機(jī)應(yīng)用程序?qū)嶒?yàn)結(jié)果 106
7.7.2 實(shí)際應(yīng)用程序 111
7.8 小結(jié) 112
第8章 任務(wù)計(jì)算量服從隨機(jī)分布調(diào)度理論 113
8.1 任務(wù)計(jì)算量隨機(jī)性 113
8.2 隨機(jī)性與任務(wù)調(diào)度 114
8.3 隨機(jī)任務(wù)調(diào)度 115
8.4 隨機(jī)調(diào)度問(wèn)題調(diào)度長(zhǎng)度期望值下限 117
8.5 并行應(yīng)用程序DAG近似路徑長(zhǎng)度 119
8.5.1 并行應(yīng)用程序隨機(jī)任務(wù)DAG模型 119
8.5.2 串-并結(jié)構(gòu)隨機(jī)任務(wù)路徑長(zhǎng)度計(jì)算 120
8.6 隨機(jī)動(dòng)態(tài)級(jí)調(diào)度算法 122
8.6.1 計(jì)算DAG模型中隨機(jī)任務(wù)b-level 122
8.6.2 隨機(jī)動(dòng)態(tài)級(jí)調(diào)度算法 124
8.7 隨機(jī)調(diào)度算法性能 126
8.7.1 性能評(píng)價(jià)指標(biāo) 127
8.7.2 隨機(jī)并行應(yīng)用程序DAG任務(wù)圖 127
8.7.3 隨機(jī)DAG任務(wù)調(diào)度實(shí)驗(yàn)結(jié)果 128
8.7.4 特殊隨機(jī)DAG應(yīng)用程序?qū)嶒?yàn) 132
8.8 小結(jié) 133
第9章 能耗感知隨機(jī)任務(wù)調(diào)度策略 135
9.1 異構(gòu)計(jì)算系統(tǒng)能耗 135
9.2 系統(tǒng)模型 136
9.2.1 異構(gòu)計(jì)算系統(tǒng) 136
9.2.2 任務(wù)模型 136
9.2.3 能耗計(jì)算模型 137
9.3 時(shí)限能耗約束任務(wù)調(diào)度問(wèn)題 138
9.3.1 單處理器任務(wù)執(zhí)行時(shí)間 138
9.3.2 異構(gòu)計(jì)算系統(tǒng)BoT應(yīng)用程序調(diào)度長(zhǎng)度 139
9.3.3 時(shí)限和能耗約束的隨機(jī)調(diào)度數(shù)學(xué)模型 140
9.4 時(shí)限能耗約束任務(wù)調(diào)度算法 141
9.4.1 任務(wù)執(zhí)行權(quán)值近似計(jì)算 141
9.4.2 時(shí)限能耗約束隨機(jī)任務(wù)調(diào)度算法 142
9.4.3 算法時(shí)間復(fù)雜度 145
9.5 性能評(píng)價(jià) 145
9.5.1 實(shí)驗(yàn)環(huán)境設(shè)置 145
9.5.2 隨機(jī)任務(wù)性能評(píng)價(jià) 146
9.5.3 實(shí)際應(yīng)用程序性能評(píng)價(jià) 150
9.6 小結(jié) 150
參考文獻(xiàn) 151
編后記 160