3.2.5处理机分配算法举例 基于图论的确定性分配算法 。假定：每个进程都知道 1)所需的处理机 2)所要求的内存 3)知道系统中任意一对进程间的平均通信量 若系统中处理机的数目k比进程数少，那系统 中的一些处理机就必须被分配多个进程 ·基于图论的确定性算法 保证在系统网络通信量最小的条件下对处理机 进行分配
3.2.5 处理机分配算法举例 基于图论的确定性分配算法 ⚫ 假定：每个进程都知道 1）所需的处理机 2）所要求的内存 3）知道系统中任意一对进程间的平均通信量 若系统中处理机的数目k比进程数少，那系统 中的一些处理机就必须被分配多个进程 ⚫ 基于图论的确定性算法 保证在系统网络通信量最小的条件下对处理机 进行分配
基于图论的确定性分配算法 系统的带权图表示 0 系统的带权图表示： 系统可以被表示图GV,E), V中的每个节点表示一个进程 E中的每条边表示两个进程需要通信， 边上面的数字表示两个进程之间的通信量。 从数学角度看，处理机分配问题已经被简化为： 在一定的约束条件下（例如，每一个子图总的处理机 和内存需求量不超过某一个阀值)将图分割成k个不 相连的子图。 算法的目标就是在满足所有限制条件下，找到一个分 割方法，使得分割后各子图之间的通信量之和最小
基于图论的确定性分配算法 系统的带权图表示 ⚫ 系统的带权图表示： 系统可以被表示图G(V,E)， V中的每个节点表示一个进程 E中的每条边表示两个进程需要通信， 边上面的数字表示两个进程之间的通信量。 ⚫ 从数学角度看，处理机分配问题已经被简化为： 在一定的约束条件下（例如，每一个子图总的处理机 和内存需求量不超过某一个阀值）将图分割成k个不 相连的子图。 算法的目标就是在满足所有限制条件下，找到一个分 割方法，使得分割后各子图之间的通信量之和最小
基于图论的确定性分配算法 分割举例 下图表示了一个图的两种不同的分割方法，并得到了 两个不同的通信量。 CPU1!CPU2 CPU3 CPU1! CPU2 CPU3 A 3;B 2 3 3 B 2 C 6 6 5 4 E 4 5 2 (a 给3个处理机分配9个进程的方法
基于图论的确定性分配算法 分割举例 ⚫ 下图表示了一个图的两种不同的分割方法，并得到了 两个不同的通信量。 CPU1 CPU2 CPU3 CPU1 CPU2 CPU3
基于图论的确定性分配算法 分割举例 a中，系统图被分割为： A,E,G在处理机1上 B,F,H在处理机2上 C,D,I在处理机3上 CPU1！ CPU2！ CPU3 A 3 B 2 3 整个网络通信量 =被虚线分割开的边上 6 的权值之和 5 4 5 =30。 H 2 和 248+5+2=17 3+2+4+4=13 (a)
基于图论的确定性分配算法 分割举例 a中，系统图被分割为： A,E,G在处理机1上 B,F,H在处理机2上 C,D,I在处理机3上 整个网络通信量 =被虚线分割开的边上 的权值之和 =30。 3+2+4+4=13 2+8+5+2=17