6任务分配与负载平衡VIP专享

第6 章 任务分配与负载平衡 主要内容：任务分配算法及负载平衡策略 学时：45′*8 重点：任务分配算法 难点：任务分配算法 6-1 任务分配 当处理机的个数大于3 时，任务分配问题是NP 完全的，所以，人们一直在寻找近似的最佳解。 任务的分配是以任务的划分为基础的，我们要将任务划分成若干个独立的、具有最少通信量的模块，然后将这些模块分配到不同的处理机上。这里我们只考虑任务的分配，而不考虑任务的划分。 任务分配追求的目标是IPC(Interprocessor Commu nication)的极小化和负载平衡，这两者显然是一对矛盾。努力调配各模块，使 IMC(Intermodu le Commu nication)和 IPC 最小，这称为最小IPC 策略；另一方面是尽可能使负载平衡，这称为负载平衡策略。走两者综合的道路是必须的。下面的讨论将基于模块数多于处理机个数进行。 一、 基于图论的分配策略 1设V={ m1, m2,…, mn } 为n个模块构成的集合，G=(V, E) E={( mi, mj) | mi与mj之间存在的IMC开销} 1 表示mi分配给处理机Pjxi j= 0 表示mi 未分配给处理机Pj。 qi j 表示mi在处理机Pj上的开销； Ci j 表示mi 与mj之间的IMC开销。 则总开销可以记为 ∑ ∑∑ ∑<<+=kikhijj hi ki ji ki kxxCxqXC}{)( 对图G 执行最小分割算法——切开的边的权的总和最小，可得 IPC 最小的划分。 如 果 要 将mi 在Pk 上的开销考 虑 进去，则需将此图改成“完全图”：设系统中有两个处理机P1、P2，如果P1处理mi的开销为r，则在顶点P2与mi之间联一条权为r的边。显然，被切掉的边的权的和越小，总的开销就越小。因为被“切掉”的就是按照此分配将产生的开销。 8 6 4 7 5 7 6 58347m1P1 m3m4m2P2 2 mk在P1运行的代价为r1，mk在P2运行的代价为r2，当将mk分配在P1上运行时，权为r1的边被切掉；当将mk分配在P2上运行时，权为r2的边被切掉。 此算法当处理机个数超过 3 时，就非常复杂了。不实用，而且它没有考虑负载平衡问题。而且在运行此算法之前，需要知道许多信息。但是该算法表现出的对问题的求解思路确实非常典型的计算机问题求解思路。 二、 0~1 程序策略 1 表示mi分配给处理机Pjxi j= 0 表示mi 未分配给处理机Pj。 qi j 表示mi在处理机Pi上的开销； Ci j 表示mi 与mj之间的IMC开销； di j 表示Pi 与Pj之间的距离。 r1P2mkr2 P1 目标函数（求极小）如下式所示，其中 w 为系数，用来调节处理开销，...