基于任务优先图的任务调度 案例2：优先级定义 案例2假定只有两个处理器。优先图中不同节点的等 级不相同。下面的算法生成一个优先图： 假定有k个终止节点（无后续节点），从1到k依次标记这些 节点。 ● 令S是没有被分配（未被标记）的节点的集合，并且其中每 个节点的后续节点都已被标记，从中选一个标记成。方法如 下： 01 令exu)是u的所有直接后续节点的标记的升序排列。 若对S中所有u'(u'u),lexu<lexu)(字典序)，那么u可以 赋予i
基于任务优先图的任务调度 案例2：优先级定义 ⚫ 案例2假定只有两个处理器。优先图中不同节点的等 级不相同。下面的算法生成一个优先图： ⚫ 假定有k个终止节点（无后续节点），从1到k依次标记这些 节点。 ⚫ 令S是没有被分配（未被标记）的节点的集合，并且其中每 个节点的后续节点都已被标记，从中选一个标记成i。方法如 下： ⚫ 令lex(u)是u的所有直接后续节点的标记的升序排列。 若对S中所有u’(u’≠u), lex(u)<lex(u’) （字典序），那么u可以 赋予i
案例2： 优先图举例 。图9-9表示一个优先图，每个节点都用上面的方法进 行了标记。节点的标记可以当做它的优先级 任务按照优先级升序排序为： T10 TI T1,T2,T3,T4,T5,T6,T11,T8,T7,T10,T9 ● 注意终止任务T1,T2,T3的顺序是随机选 T 择的，例中它们的优先级分别是1,2,3 T4的直接后续节点是T1和T2, 因此lex(T4)=(1,2)。 显然Iex(T4)<lex(T5) 所以T4的标记是4，T5的标记是5
案例2： 优先图举例 ⚫ 图9-9 表示一个优先图，每个节点都用上面的方法进 行了标记。节点的标记可以当做它的优先级 ⚫ 任务按照优先级升序排序为： T1,T2,T3,T4,T5,T6,T11,T8,T7,T10,T9 ⚫ 注意终止任务T1,T2,T3的顺序是随机选 择的，例中它们的优先级分别是1,2,3 T4的直接后续节点是T1和T2， 因此lex(T4)=(1, 2)。 显然lex(T4)< Iex(T5) 所以T4的标记是4 ，T5的标记是5 。
案例2： 任务分配举例 。图9-6b是甘特图表示的最优调度。 0 T10 10 T9 T10 T7 T8 间 T11 T6 T5 T4 T3 T2 TI
案例2： 任务分配举例 ⚫ 图9-6b 是甘特图表示的最优调度。
基于任务相互关系图的任务调度 任务图定义 第二个任务调度模型是利用任务相互关系图和 进程的集合来表示应用程序 ●任务相互关系图由无向图GV,E)表示 V:是进程的集合 E:是边的集合， 其中每条边表示两个通信进程间的相互作用关系，用相 关两个进程的通信代价标记（不是优先关系）
基于任务相互关系图的任务调度 任务图定义 ⚫ 第二个任务调度模型是利用任务相互关系图和 进程的集合来表示应用程序。 ⚫ 任务相互关系图由无向图Gt (Vt , Et )表示 Vt：是进程的集合 Et：是边的集合， 其中每条边表示两个通信进程间的相互作用关系，用相 关两个进程的通信代价标记（不是优先关系）
基于任务相互关系图的任务调度 处理器图定义 与任务优先图模型不同的是处理器间通信在任务相互 关系图调度模型中有重要作用。 特别地，处理器图由G(V,E)表示 顶点集V,中每个元素是一个处理器 边集E。中每个元素是一个通信信道 一般来说，VsV,因此可以假设任务划分已经完 成。然后，进行分配M:V→V,以及执行时间的估计。 注意，w(U)和w(u,V)分别表示节点u和链接(u,V)的代 价
基于任务相互关系图的任务调度 处理器图定义 ⚫ 与任务优先图模型不同的是处理器间通信在任务相互 关系图调度模型中有重要作用。 ⚫ 特别地，处理器图由Gp (Vp , Ep )表示 顶点集Vp中每个元素是一个处理器 边集Ep中每个元素是一个通信信道 ⚫ 一般来说，|Vt |≤|Vp |，因此可以假设任务划分已经完 成。然后，进行分配M:Vt→Vp以及执行时间的估计。 注意，w(u)和w(u, v)分别表示节点u和链接(u, v)的代 价
基于任务相互关系图的任务调度 负载定义 。处理器p的计算负载，p∈V。: M(U)表示将u任务 Comp(p)=∑w(0川M(W=p 分配到节点M(U)上 。通信负载： u∈V Commp(p)=∑w(u,v)川M(u)=p≠M() (u,v)EE ·在一个应用程序中总的计算和通信量是： Comp=∑Comp(p)=∑∑w(u川M(u)=p PEVpVEVI Comm=2∑Comp)-3∑.∑wu,lM=p≠M) pEVp(u,v)EE
基于任务相互关系图的任务调度 负载定义 ⚫ 处理器p的计算负载，p∈Vp : ⚫ 通信负载： ⚫ 在一个应用程序中总的计算和通信量是： = = u Vt Comp( p) w(u)| M(u) p ( ) ( , )| ( ) ( ) ( , ) Commp p w u v M u p M v Et u v = = = = = = = = p p t p p t p V p V u v E p V p V v V Comm Comm p w u v M u p M v Comp Comp p w u M u p ( , ) ( , )| ( ) ( ) 2 1 ( ) 2 1 ( ) ( )| ( ) M(u)表示将u任务 分配到节点M(u)上
基于任务相互关系图的任务调度 负载定义 程序总的执行时间大概是： T=max{aComp(p)+BComm(p),peVp 其中，α依据每个PE的执行速度，B依据每个通信信 道的通信速度和通信进程间的距离。 。注意： 如果两个进程u和V在G,邻接，它们在G,的映像（M的 映像结果)可能邻接也可能不邻接。理想的情况下， 所有通信进程被分配在邻接的处理器上，以此减少处 理器间通信
基于任务相互关系图的任务调度 负载定义 ⚫ 程序总的执行时间大概是： ⚫ 其中，α依据每个PE的执行速度，β依据每个通信信 道的通信速度和通信进程间的距离。 ⚫ 注意： 如果两个进程u和v在Gt邻接，它们在Gp的映像（M 的 映像结果）可能邻接也可能不邻接。理想的情况下， 所有通信进程被分配在邻接的处理器上，以此减少处 理器间通信。 T = Comp p + Comm p pVp max{ ( ) ( )}
基于任务相互关系图的任务调度 映射的势 。注意： 通常两个进程不应该映射在一个处理器上。 。任务分类时这两个进程应当分类进同一个进程。 评估映射质量的一个指标是 映射的势，即 任务图G中的边映射到处理器图G的边的数目。也是 G中映射到G,中邻接处理器的通信进程对的数目。 ● 映射的势不能超过G中的链接数。 如果一个映射的势最大，它就是一个理想映射
基于任务相互关系图的任务调度 映射的势 ⚫ 注意： 通常两个进程不应该映射在一个处理器上。 ⚫ 任务分类时这两个进程应当分类进同一个进程。 ⚫ 评估映射质量的一个指标是 映射的势，即 任务图Gt中的边映射到处理器图Gp的边的数目。也是 Gt中映射到Gp中邻接处理器的通信进程对的数目。 ⚫ 映射的势不能超过Gt中的链接数。 ⚫ 如果一个映射的势最大，它就是一个理想映射
基于任务相互关系图的任务调度 映射的势举例 下图中，左边是一个任务相互关系图，右边是 一个具有9个处理器的处理器图。 右图显示了任务与处理器的映射关系，该映射 的势是8(13条边) 13-5条虚边=8 a) b) 把任务相互关系图a)映射到处理器图6)
基于任务相互关系图的任务调度 映射的势举例 ⚫ 下图中，左边是一个任务相互关系图，右边是 一个具有9个处理器的处理器图。 ⚫ 右图显示了任务与处理器的映射关系，该映射 的势是8（13条边）。 13-5条虚边=8
基于任务相互关系图的任务调度 映射的势 ●有时映射的势可能不能准确地反映映射的质量。 比如，它不能区分下面两种情况： a)两个通信进程被映射到两个处理器上，这两个 处理器在处理器图中的距离是k(k>2), o b)两个通信进程被映射到两个处理器上，这两个 处理器在处理器图中的距离是2。 需要图嵌入技巧来区分上面两种情况
基于任务相互关系图的任务调度 映射的势 ⚫ 有时映射的势可能不能准确地反映映射的质量。 比如，它不能区分下面两种情况： ⚫ a）两个通信进程被映射到两个处理器上，这两个 处理器在处理器图中的距离是k(k>2)， ⚫ b）两个通信进程被映射到两个处理器上，这两个 处理器在处理器图中的距离是2 。 ⚫ 需要图嵌入技巧来区分上面两种情况