基于任务相互关系图的任务调度 负载定义 。处理器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 。 ⚫ 需要图嵌入技巧来区分上面两种情况