第一章 概论 1
1.1 调度问题研究的背景和意义 1
1.1.1 分布计算的新途径 1
1.1.2 调度问题在分布计算中所处的地位 4
1.2 调度问题的定义和分类 4
1.2.1 调度问题的定义 4
1.2.2 调度问题的分类 5
1.3 调度问题的研究进展 7
1.3.1 调度问题的研究动态 7
1.3.2 调度技术的研究进展 8
1.4 调度问题的主要难点及解决途径 10
1.5 本书的组织 11
第二章 调度的基本问题及相关技术 14
2.1 调度问题 14
2.1.1 调度模型 14
2.1.3 分布模型 15
2.1.2 DAG的产生 15
2.1.4 调度 16
2.1.5 计算时间和通信时间 17
2.2 通信模型 18
2.2.1 考虑通信的完成时间 18
2.2.2 从Gantt图得到完成时间 19
2.3 调度问题的复杂性 20
2.3.1 不考虑通信时间的调度问题的复杂性 21
2.3.2 考虑通信时间的调度问题的复杂性 23
2.4 启发式调度及其相关问题 24
2.4.1 并行性与通信时间 25
2.4.2 并行粒度和数据的局部性 26
2.4.3 非确定性 27
2.4.4 基于优先级的调度 28
2.4.5 启发式方法中的任务聚族 29
2.4.6 任务复制 30
2.5 具有AND／OR优先约束关系的调度问题 31
2.6 小结 32
第三章 任务分配问题 33
3.1 任务分配模型 34
3.2 影响系统性能的因素 36
3.3 基于图论的分配算法 37
3.3.1 两个处理机上的优化分配 37
3.3.2 多处理机之间的优化分配 38
3.4 0-1规划策略 41
3.5 “合一-阈值”启发式分配算法 43
3.6 改进的启发式算法 47
3.7 基于遗传算法和模拟退火算法的任务分配策略 53
3.7.1 遗传算法(Genetic Algorithm) 53
3.7.2 模拟退火算法(Simulated Annealing) 54
3.7.3 基于遗传算法和模拟退火算法的任务分配算法 55
3.8 小结 59
第四章 启发式表调度算法 60
4.1 表调度的基本方法 60
4.2 BNP的表调度算法 63
4.2.1 ISH算法 64
4.2.2 MCP算法 65
4.2.3 ETF算法 67
4.3 APN的表调度算法 68
4.3.1 信息的路由问题 68
4.3.2 MH算法 69
4.3.3 DLS算法 70
4.4 冒泡迁移算法 73
4.4.1 将启发式信息作为选择参数 73
4.4.2 调度策略 75
4.4.3 算法描述 77
4.4.4 复杂性分析 79
4.5 小结 81
第五章 负载平衡与智能调度 82
5.1 负载平衡问题 82
5.1.1 概述 82
5.1.2 负载平衡算法分类 83
5.1.3 负载平衡策略 84
5.2.1 发送者主动算法 86
5.2 负载平衡算法及其策略 86
5.2.2 接收者主动算法 87
5.2.3 双向主动算法 88
5.2.4 梯度模型 88
5.2.5 接收者主动的渗透算法 89
5.2.6 预约策略 90
5.2.7 投标策略 90
5.2.8 广播策略 90
5.3 智能型任务调度算法 90
5.3.1 任务调度中的知识及其表示 91
5.3.2 任务调度程序的结构 92
5.3.3 任务调度算法的实现 94
5.4 小结 95
第六章 启发式混合调度算法 96
6.1 负载平衡模型 96
6.2 分布模型 97
6.3.1 实现分布计算的Agent 99
6.3 分布并行的实现模型 99
6.3.2 并行应用框架 102
6.3.3 任务模型 105
6.4 调度策略与算法 108
6.4.1 调度策略 108
6.4.2 族分配算法 109
6.4.3 族内分配算法 111
6.4.4 动态分配算法 111
6.5 示例与分析 112
6.6 小结 117
第七章 具有AND／OR优先约束关系的调度问题 118
7.1 AND／OR调度问题的定义 118
7.1.1 定义和术语 118
7.1.2 等价问题及形式化 122
7.2 其他调度问题之间的关系 124
7.2.1 限时修改(Deadline Modification) 124
7.2.2 优先约束修改(Precedence Constraint Modification) 125
7.3 AND／OR调度问题的时间复杂性 126
7.4.1 AND／0R图的传递闭包的定义 130
7.4 AND／OR图的传递闭包 130
7.4.2 算法描述 131
7.4.3 加速算法的实现 135
7.5 小结 137
第八章 AND／OR优先约束调度问题的近似算法 138
8.1 图搜索距离定理 139
8.2 减少完成时间的调度方法 146
8.2.1 IN-TREE结构 146
8.2.2 具有IN-TREE结构的可跳过任务系统的调度 148
8.2.3 应用实例 150
8.3 小结 154
第九章 可跳过的AND／OR任务系统的启发式方法 155
9.1 抽象集覆盖启发式方法 155
9.1.1 CLJ启发式方法 156
9.1.2 删除式启发式方法DCLJ 157
9.1.3 冗余删除法RDM 157
9.1.4 基于独立数删除方法INBDM 158
9.1.5 利用集覆盖算法进行AND／OR任务系统调度的抽象过程 159
9.2 单处理机上的启发式方法 160
9.2.1 DCLJ算法的进一步描述 160
9.2.2 RDM算法的进一步描述 165
9.2.3 其他算法和改进算法 166
9.3 多处理机系统启发式方法 170
9.4 模拟参数 174
9.4.5 AND／OR任务图生成算法 175
9.4.4 OR任务的百分比P 175
9.4.3 任务处理时间分布区间[a，b] 175
9.4.2 网格比X／Y 175
9.4.1 边概率Q 175
9.5 模拟结果 177
9.6 小结 184
第十章 结论与展望 185
10.1 总结 185
10.2 展望 187
参考文献 189