再上一篇:9. 2  模拟退火框架
上一篇:9. 3  进化程序设计
主页
下一篇:10.2  均场退火
再下一篇:10.3  遗传算法
文章列表

第 10 章  多处理器调度

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

多处理器调度的一般问题可表述为在一个多处理器系统中调度一组部分有序的计算任务以使一组性能指标最优化。问题的难度在很大程度上取决于表示计算任务间先后次序关系的任务图的拓扑结构、多处理器系统的拓扑结构、并行处理器的个数、任务处理时间的均匀程度以及所选性能指标。一般来讲,多处理器调度问题(MSP)即使在简化了的假定前提下也很难解[57],因此启发式算法被提出以求取MSP 的最优解或次优解。

已有多种不同的 解法被提出[66][96]。卡沙拉( )和那瑞塔( )[95][96]提

MSP Kashara Narita

出了一个启发式算法(关键路径/最直接节点优先)和一个最优化/近似算法(深度优先/隐式启发搜索)。陈( )等[39]发展了一个利用从费南德( )和布赛尔( )边

Chen Fernandez Bussell界推导出的启发知识的MSP 状态空间算法(A* 算法)。海尔斯车姆(Hellstrom)和卡耐尔( )[76]将 映射到一个神经元网络模型——非对称均场网络。张( )等[178]开Kanal MSP Zhang

发了一个用霍普费尔德网络的均场退火求解MSP 的方法。

在这一章中,介绍求解MSP 的均场退火方法和遗传算法。这里所讨论的只是基于确定性模型的MSP,即计算任务的运行时间及其之间的关系是已知的。任务之间的先后关系由一个非循环有向图表示,且任务的运行时间可为非均匀的。同时,假定多处理器系统是均衡的、无优先权的,即每个处理器都是一样的,且一个处理器在完成当前任务前不会执行下一个任务。

10.1  模型与定义

一组偏序的计算任务可由一个非循环有向图表示,TG= (V,E),其中V为一个节点的非空有限集,E 为连接节点的有向连线的有限集。节点的集合V= {T1,T2,…,Tm}表示要执行的一组计算任务, 而有向连线的集合 E=

{eij}(eij表示从节点Ti到Tj 的有向连线)则表示任

务中的偏序或先后关系 。如果Ti Tj,任务Ti必

须在Tj 开始执行之前完成。一个具有8个任务的简

单任务图TG如图10.1所示。

一个具有p 个多处理机系统的任务图最优化调

度问题是要在保证前后关系的条件下将计算任务分

配到各个处理机上,以使所有任务能在最短时间内

完成。最后一个任务完成的时刻被称为调度的完成

图 10.1  任务图TG

时间(FT)。图10.2描绘了一个以甘特图给出的两

处理器的任务图TG示例。这一调度的完成时间为

#第97页-

11个单位时间。临界路径长度对于调度的完成时间来说是一个重要下限。一个任务图的临界路径长度tcp定义为完成任务图中所有任务所需的

最短时间。

下列定义和术语将用于任务图TG= (V,E):

・ 如果eij∈E, 则Ti是Tj 的父节点,且Tj 是Ti 图 10.2  用甘特图表示的一个的子节点。 两处理器 的调度

・ 如果存在从Ti到Tj 的序列有向连线,则Ti是 TG

Tj 的前辈节点,且Tj 是Ti的后辈节点。

・PRED(Ti)是Ti的前辈节点集;

・SUCC(Ti)是Ti的后辈节点集;

・et(Ti)是Ti的运行时间;

・ 任务Ti的高度定义为

height(Ti) = 0 如果Ti没有前辈节点

1+ maxTj∈PRED(Ti)height(Tj) 其它

该高度公式以其特殊的方式给出了任务之间的先后关系。实际上,如果任务Ti是任务Tj的前辈节点(亦即Ti必须在Tj 之前执行),则一定会有height(Ti)< height(Tj)。不过,如果两个任务之间没有路径,则它们之间没有先后关系,因而这两个任务的执行顺序是任意的。