任务分配与调度.pptx

<p>,2019/12/21,#,2024/11/20 周三,1,第四章 任务分配与调度,4.1,多机操作系统概述,1.,主要特征,并行性,多机操作系统的主要目标是增强程序执行的并行性，以获得更高的系统处理能力，提高系统的运算速度，满足各应用领域对计算机系统性能的需求,2024/11/20 周三,2,分布性,任务分布,问题分解后，分解成为多个子任务，分配到不同的处理机上运行,控制分布,处理机结点由自己的操作系统或管理程序管理和控制本结点的资源和进程,资源分布,系统所有资源分布在各结点上，便于各进程对资源的共享,2024/11/20 周三,3,通信与同步,存在结点内并发进程之间的同步和通信，各不同结点进程之间需要同步和通信,系统容错,当系统中某一个部件或结点发生故障，系统应能动态重新组合，降级使用,2024/11/20 周三,4,基本特点：,要求主处理机速度快，能使各从处理机尽可能处于“忙”状态,由于只有一台处理机进行管理，不存在访问各种文件和表格的冲突问题,不要求各管理程序模块编写为可重入结构,2.,多机操作系统分类,主从式,操作系统仅在指定的主处理机上运行。主处理机管理整个系统并为从处理机分配任务，从处理机通过软中断或访管访问主机。,2024/11/20 周三,5,软硬件结构简单，但灵活性差,一旦主处理机发生故障，系统瘫痪,处理较多短任务时，增大管理工作量，主机负担重，系统效率低。,适用于由功能相差很大的处理机组成的非对称系统及工作负载不是太重的情况,2024/11/20 周三,6,基本特点,：,每个处理机有各自的私有表格，而有些表格是系统公用的，增加了表格存取控制的复杂性,每个处理机可以根据自身的需要及所分配的任务进行管理,单独管理,每个处理机具有自己的操作系统或管理程序，按照自身需要，独立运行和管理。,2024/11/20 周三,7,管理程序的代码必须是可重入的，或者是为每个处理机装入专用的管理程序副本,某个处理机出了故障不一定会引起整个系统瘫痪，但恢复困难。,难以处理系统负载平衡,适合于松散耦合的多处理机系统,2024/11/20 周三,8,浮动管理,主处理机可以从一个处理机浮动到另一个处理机，任何处理机均可成为主处理机。,基本特点：,管理程序的代码必须写成可重入的,可以获得较好的系统负载平衡,2024/11/20 周三,9,在同一时间里可以有多个处理机处于管态，可能发生访问表格、数据冲突，用互斥访问解决。,OS,对处理机是透明的，并有较高的可靠性及灵活性，较难设计。,当某台处理机发生故障，易于降级使用。,适用于同构型多机系统。对于异构型多处理系统，,OS,设计将更困难。,2024/11/20 周三,10,4.2,任务分配,调度策略,1,、概述,调度,为了优化某个目标函数，在一组具有任意特性的处理机中对一组进程进行调度。调度主要作出两个决定：,决定把程序和数据分配到物理存储器的什么位置,决定每个进程在哪个处理机上运行,2024/11/20 周三,11,调度算法,是对一组给定进程进行调度的过程，目的是研究处理机的分配和进程调度技术，以达到使用最少数量的处理机在最短时间内完成并行程序。,调度算法效率：,当调度算法可以描述为一个多项式算法，效率较高,当调度算法可以描述为一个指数算法，效率较低,2024/11/20 周三,12,与调度相关的一些性能指标（参数）,最小完成时间,所需最少处理机数目,最小平均流,处理机最大利用率,处理机最小空闲时间,2024/11/20 周三,13,一般情况下，寻找最优的调度算法不一定是最好的调度算法或不存在最优调度算法。所以最优调度算法往往指为合理的调度算法,2024/11/20 周三,14,长期进程调度,选择和激活一个新进程使其进入处理环境,短期进程调度,选择一个进程送入所分配的处理机,两类调度：,确定性调度,在求解问题前必须给出表示问题特征所需要的所有信息，主要有每个任务的运行时间和各任务之间的关系,不确定性调度,系统运行过程中根据系统状态对任务进行分配,2024/11/20 周三,15,在确定性调度中，任务的执行时间很难直接给出。一般是最大任务的执行时间或估计值，由于任务执行时间不确切，造成系统调度效率较低。,在不确定性调度中，使各处理机尽可能处于,“,忙,”,状态。可以有效利用系统资源，但会增加系统额外开销。,2024/11/20 周三,16,两种调度方法：,抢先调度,一个任务完成之前允许被打断，以后可以接续恢复执行的调度,非抢先调度,当一台处理机分配给某个任务后，该处理机为该任务提供服务直至该任务完成,2024/11/20 周三,17,2,、确定性调度,进程调度过程往往采用,Gantt,图表示。,0,2,4,6,7,P1,P2,P3,T1,T2,T3,T4,T5,T2,T1,可以表示处理机的调度过程，反映各种运行参数,2024/11/20 周三,18,非抢先调度,给定一个任务图，结点表示子任务，有向线表示各子任务之间关系，结点右侧数字表示子任务的运行时间。,T1,T3,T6,T5,T7,T9,T2,T4,T8,0,3,7,9,13,17,P1,P2,两台处理机的尽早分配任务调度,2024/11/20 周三,19,0,3,7,11,15,P1,P2,两台处理机的最佳分配任务调度,T1,T3,T4,T7,T9,T2,T5,T8,T6,14,最小完成时间，由关键路径决定,所需最多处理机个数,图宽度,结点的最早调度时间,结点的最晚调度时间,2024/11/20 周三,20,从上图可以看出，处理机空闲时立即分配任务不一定获得最小完成时间。,最早调度策略,从开始结点计算结点的最早分配时间,最晚调度策略,从结束结点推算计算最晚调度时间,一个任务图的任务分配是一个网络规划问题,2024/11/20 周三,21,一个任务图，可由图,G=(T,Q,）,表示：,T=t,1,t,2,t,3,.t,n,T,为任务集,t,i,为结点权，表示子任务的运行时间。,Q=q,1,q,2,q,3,.q,m,Q,为通信集,q,j,（,t,i,t,k,),为,t,i,与,t,k,两个结点之间边的权，表示两个子任务之间的通信量。,确定性调度，结点权是个常数，不确定性调度结点权是不确定的数。,2024/11/20 周三,22,一个多机系统可由系统图,H,（,P,E),表示,P=p,1,p,2,.P,s,P,为处理机集,P,i,为结点权，表示处理机速度,E=e,1,e,2,e,r,E,通信链路集,e,j,为有向边权，表示两个处理机之间通信链路的带宽,调度过程可以归纳为任务图到系统图的映射,2024/11/20 周三,23,最小完成时间的非抢先调度,HU,调度算法：,设任务图为一棵根数，所有任务结点权为单位时间，可以解决：,给定处理机数目，决定执行任务图的最小完成时间,给定执行一个任务图的时间，决定所需最小处理机数目,2024/11/20 周三,24,方法：,对结点,T,i,用,a,i,=x,i,+1,进行标号，其中,x,i,是,T,i,到结束结点的最大路径长度,从结束结点加标号，,a,1,=1,，与结束结点相差一个单位时间的结点,a,2,=2,，依次类推,任务图最小完成时间,T,min,与,a,max,有关，即为：,T,min,a,max,a,max,为图的图的最大路径,2024/11/20 周三,25,调度过程：,对于,P,台处理机,首先调度,P,个最大标号结点，可能包括两层结点,把处理过的,P,个结点从图中删除，剩下没有前趋的结点为开始结点,重复以上过程,2024/11/20 周三,26,设一个任务图的执行时间为：,T=a,max,+c c,为正整数,所需最少处理机数目可由下式求出：,其中,(i),表示途中标号,a,i,的结点数，,r*,是给定表达式值为最大的常数,r,值,2024/11/20 周三,27,C=0,，,T=a,max,=7,r=1:,(7)/1=,4/1=4,r=2:,(,(7)+,(6)/1,=(4+4)/1=4,r=4,(,(7)+,(6)+,(5)+,(4)/4,=13/4=3.25,2024/11/20 周三,28,C=1,，,T=a,max,+1=8,r=1:4/2=2,r=2:8/3=2.66,r=3:10/4=2.5,r=4:13/5=2.6,r=5:16/6=2.66,r=6:18/7=2.57,r=7:19/8=2.357,r=2,和,r=5,时，产生,r*,值，表达式值最大,2024/11/20 周三,29,抢先调度,公度结点权,定义：,设如果存在一个正数,w,，使得每个结点的权是,w,的正倍数，称这组结点的权是相互成比例的或是可公度的。,公度（单位）结点权为,4,2024/11/20 周三,30,最小完成时间的抢先调度,假设对,n,个相互独立任务和,p,台处理机进行调度，,n,个任务的权分别是,w1,w2,.wn,，,最小完成时间是：,2024/11/20 周三,31,T1,T3,T2,T4,单位权结点的抢先调度,两台处理机：,T1,T2,T2,T3,P1,P2,P1,P2,任务数为偶数,任务数为奇数,1.5,2024/11/20 周三,32,对于三台处理机,T1,T2,T2,T3,T3,T4,P1,P2,P3,T1,T2,T2,T4,T3,T3,T5,P1,P2,P3,任务数为,4,任务数为,5,2024/11/20 周三,33,最小完成时间的抢先调度算法：,设任务图为一颗根树，结点权可公度,将单位权结点划分为若干个不相交的子集，子集内的结点相互独立，可以同时运行,任务图按层分割，结束结点为第一层，向上单位时间完成的结点为第二层，依此类推。,在不违背原图前趋的条件下，下层结点可以移至上层结点。,首先调度最高层，逐步向下，可获得最小完成时间,2024/11/20 周三,34,例：,2024/11/20 周三,35,公度结点权,2024/11/20 周三,36,T1,7+1/2,T2,7/3,T4,1,T6,3/2,T9,1/2,T2,14/3+1/2,T3,14/3,T5,1,T7,3/2,T3,7/3+1/2,T5,7,T7,T8,T8,3/2,1,2,3,4,5,6,7,8,9,10,11,12,13,0,P1,P2,P3,31/6,64/6,73/6,76/6,2024/11/20 周三,37,粒度组合与调度,做并行程序设计时要回答两个基本问题：,（,1,）如何将程序划分成并行模块、子任务以获得最短执行时间。,（,2,）计算中的并发粒度为多大会比较理想。,与问题以及机器有关，需要在并行性与调度开销之间做折衷。,2024/11/20 周三,38,细粒度程序的调度举例,Var a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,Begin,1,a:=1,2,b:=2,3,c:=3,4,d:=4,5,e:=5,6,f:=6,2024/11/20 周三,39,7,g:=a*b,8,h:=c*d,9,i:=d*e,10,j:=e*f,11,k:=d*f,12,l:=j*k,13,m:=4*l,14,n:=3*m,15,o:=n*i,16,p:=o*h,17,q=p*g,End,2024/11/20 周三,40,指令,1,，,2,，,3,，,4,，,5,，,6,是存储器访问（取数据）操作，每个结点用一个周期进行寻址，用六个周期从存储器取数。,指令,7-17,是,CPU,操作，每个需要两个周期完成。,程序图,：,每个结点相当于程序中的计算单元,粒度用执行结点中全部操作所需要的基本时间来度量（处理机和存储器）,程序图中的结点表示如下图,：,2024/11/20 周三,41,n,，,s,x,，,i,y,，,j,u,，,k,v,，,h,（,n,，,s,）,=,（结点名，粒度）,（,x,，,i,）,=,（输入变量，延迟）,（,u,，,k,）,=,（输出变量，延迟）,粒度是指程序段所含的计算量；,延迟主要指通信延迟，包括通道延迟和消息延迟。,2024/11/20 周三,42,程序初始尽可能细分，任务图如下：,1,1,2,1,3,1,4,1,5,1,6,1,7,2,8,2,9,2,10,2,11,2,12,2,13,2,14,2,15,2,16,2,17,2,a,6,b,6,c,6,d,6,d,6,e,6,e,6,d,6,f,6,f,6,g,4,h,4,i,4,j,4,k,4,l,3,4,0,3,0,m,3,n,4,o,3,p,3,q,3,2024/11/20 周三,43,2,台处理机的细粒度调度：,P1,P2,6,11,1,2,3,9,8,7,0,1,7,9,10,11,12,18,20,22,24,28,5,10,12,13,14,4,0,1,2,8,10,14,16,19,21,24,26,15,16,17,30,32,35,37,40,42,阴影部分为通信延迟,2024/11/20 周三,44,粒度的组合,如果加大粒度有可能消除消除一些不必要的通信时延或降低总的调度开销，则将多个细粒度结点组合成粗粒度结点。,前面细粒度的程序图经过粒度组合可以得到粗粒度的程序图如下所示：,2024/11/20 周三,45,1,1,2,1,3,1,4,1,5,1,6,1,7,2,8,2,9,2,10,2,11,2,12,2,13,2,14,2,15,2,16,2,17,2,a,6,b,6,c,6,d,6,d,6,e,6,e,6,d,6,f,6,g,4,h,4,i,4,j,4,k,4,l,3,4,0,3,0,m,3,n,4,o,3,p,3,q,3,A,B,C,D,E,2024/11/20 周三,46,例中的粗粒度程序图如下：,A,8,B,4,C,4,D,6,E,6,a,6,b,6,c,6,d,6,d,6,e,6,f,6,g,4,h,4,i,4,j,4,k,4,n,4,q,0,2024/11/20 周三,47,2,台处理机的粗粒度调度,P1,P2,阴影部分为通信延迟,I,表示处理机空闲,A,C,D,0,8,14,22,28,32,38,18,E,I,B,0,14,22,18,I,2024/11/20 周三,48,静态多处理机调度,结点复制：,为了消除空闲时间和进一步降低处理机间的通信延迟。以下面的程序图为例：,d,4,A,4,B,1,E,2,C,1,D,2,a,1,b,1,c,8,a,8,c,1,e,4,2024/11/20 周三,49,2,台处理机的不用结点复制技术的调度方案,:,d,4,A,4,B,1,E,2,C,1,D,2,a,1,b,1,c,8,a,8,c,1,e,4,P1,P2,A,B,I,P1,0,4,5,7,13,21,23,6,D,27,得到,d,P2,I,C,0,4,16,12,得到,e,E,13,14,20,阴影部分为通信延迟,I,表示处理机空闲,2024/11/20 周三,50,2,台处理机的采用结点复制技术的调度方案,:,d,4,A,4,B,1,E,2,C,1,D,2,a,1,b,1,c,1,a,1,c,1,e,4,P1,P2,A,4,C,1,a,1,A,B,C,P1,0,4,5,7,10,6,D,14,得到,d,8,P2,A,C,0,4,9,5,得到,e,E,6,7,13,阴影部分为通信延迟,I,表示处理机空闲,2024/11/20 周三,51,比较两种方案,：,采用结点复制的技术后，调度方案所用的时间几乎短了,50%,，其原因是由于消除了两台处理机之间的延迟,（,a,，,8,）,和,（,c,，,8,）,。,2024/11/20 周三,52,粒度确定和调度优化过程,：,第一步：,构造细粒度的程序图,第二步：,调度细粒度运算,第三步：,进行粒度组合得到粗粒度,第四步：,在组合图基础上产生并行调度方案,2024/11/20 周三,53,静态多处理机调度的程序分解,需要,8,次乘法（每次需要,101,个,CPU,周期），,7,次加法（每次需要,8,个,CPU,周期），以二叉树结构完成，如下。,2024/11/20 周三,54,A,ik,B,kj,k=1,2,粒度,=101,A,ik,B,kj,A,i1,B,1j,A,i2,B,2j,粒度,=8,G,ij,=A,i1,B,1j,+A,i2,B,2j,2024/11/20 周三,55,在,20MHz,下，,M68000,汇编代码如下（后面的数字是指令所用的周期数）：,MoveWAxx,D1,15,MoveWBxx,D2,15,MPTYD1,D2,71,MoveLD2,PAR,20,MoveLPAR1,D1,20,MoveLPAR2,D2,20,ADDLD1,D2,8,MoveLD2,PSUM,20,2024/11/20 周三,56,通信延迟,d,的计算,：,P1,存储器,DMA,DMA,P2,存储器,T1,T2,T3,T4,T5,串行链路,其中，,T3,是,32,位在,20Mbps,下的传输时间，折合成,M68000,的周期，,T6,是由于软件协议的延迟（假定用,5,条,Move,指令，共,100,个周期）。,2024/11/20 周三,57,细粒度的程序图如下：,A,B,C,D,E,F,G,H,d,d,d,d,d,d,d,d,J,K,L,M,d,d,d,d,N,O,P,d,d,SUM,2024/11/20 周三,58,细粒度的顺序调度方案如下：,P1,A,B,0,202,101,C,D,404,303,E,F,606,505,G,H,808,707,J,K,L,M,N,O,P,816,824,832,840,848,856,864,808,共需,864,个周期。,2024/11/20 周三,59,细粒度的并行调度方案如下（,8,处理器）：,P1,A,B,0,313,101,C,D,321,=101,E,F,531,523,G,H,751,743,J,K,L,M,N,O,P,P2,P3,P4,P5,P6,P7,P8,I,I,I,I,I,I,图中的阴影部分为通信延迟,I,表示处理机空闲,=8,d=212,=8,d=212,=8,d=212,2024/11/20 周三,60,使用,8,个处理机进行并行调度，共需,751,个周期。,和顺序调度相比，获得的加速比为,:,2024/11/20 周三,61,采用粒度组合减少通信开销：,A,B,C,D,E,F,G,H,d,d,d,d,d,d,d,d,J,K,L,M,d,d,d,d,N,O,P,d,d,SUM,V,W,X,Y,Z,2024/11/20 周三,62,通信延迟为：,各结点粒度为：,程序图中最大并行度已降为,4,，所以只需要用,4,台处理机执行此粗粒度程序即可。,上述调度方案只用了,2024/11/20 周三,63,最小平均流时间调度,设多机系统为异构型或各处理机速度不同。已知每个任务在每个处理机上的执行时间，对于一组相互独立的任务，可获得最小平均流时间。,对于,m,个处理机和,n,个任务，有,mn,的矩阵表示每个任务在不同处理机上的执行时间，,Tij,表示任务,Tj,在处理机,Pi,上的执行时间。,2024/11/20 周三,64,T1 T2 T3 T4 T5,2 3 1 4 6,Tij=1 4 1 5 5,3 2 3 2 3,T2,T3,T1,T4,T5,P1,P2,P3,1,2,3,4,5,0,最小平均流时间调度就是在矩阵中找出一个调度流时间最小的,n,元素组，该元素组中两个或两个以上元素不能在矩阵同一列上,2024/11/20 周三,65,3,、不确定性调度,不确定性调度的基本思路：,(1),进一步探索进程执行时间的规律，以获得任务的执行时间或相应的数据,(2),在运行过程中保证各处理机满负荷运行,2024/11/20 周三,66,排队调度,设有,P,个处理机和无界要求服务的任务队列，已知任务到达的时间间隔概率分布，处理机处理时间的概率分布，并且任务到达时间间隔和处理时间概率分布相互独立。利用排队模型可以求得任务响应的平均时间或给出任务平均响应时间，求所需的处理机数目。,（经过统计，任务到达服从爱尔郎,Erlang,分布）,2024/11/20 周三,67,排队系统三个主要组成部分：,输入过程,指顾客到达排队的情况,顾客总体（服务对象）,有限多、无限多,到达方式,单个、成批,到达时间间隔,确定、随机,到达联系,独立的、前后相关,到达稳定性,到达时间间隔分布,排队规则,即时制,立即服务，无柜台空即走不等待,等待制,排队,等待服务次序,先来先服务，先来后服务，随机服务，优先权服务等,2024/11/20 周三,68,服务机构,一个或多个服务台,串行或并行服务,单个服务或成批服务,服务时间确定或不确定,服务时间间隔平稳情况,三个影响最大的因素：顾客到达时间间隔分布,服务时间分布,服务台的个数,可以求出顾客等待平均时间或所需服务台个数,2024/11/20 周三,69,两个含义：,（,1,）在程序执行过程中对任务进行分解和分配,（,2,）将任务从一台处理机向另一台处理机调动,将任务从重载处理机向空载或轻载处理机上迁移,动态调度的依据，系统状态信息。需要通过交换信息了解系统状态,两种交换方式：,同步方式：按固定时间互通信息,（多长时间互通一次信息？）,异步方式：因某一事件触发互通信息,动态负载平衡,2024/11/20 周三,70,负载平衡策略,接收者负载平衡,在任务并行执行过程中，当某处理机空载时，按,“,征兵协议,”,向周围结点发出征载请求，邻近的重载处理机进行响应，相互建立联系。,发送者负载平衡,在任务并行执行过程中，重载处理机按,“,招标协议,”,向外广播寻求帮助。空载处理机收到请求，给予响应。,“,征兵协议”适用于负载比较平衡的系统,“招标协议”适用于负载不平衡的系统,2024/11/20 周三,71,几个基本参数：,负载,处理机运行的用户程序没有完成的工作量。包括计算时间和通信时间。往往与具体的求解问题有关，需要按一定的方法估算。,负载阈值,处理机负载的某一界限值。当某未完成任务的负载低于此值，就不适于再分解。,设任务,P,的计算时间为,Tp,，分解为两个子任务,P1,，,P2,。计算时间为,Tp/2,。若任务通信时间为,Tc,，当,Tp/22Tc,。,2024/11/20 周三,72,轻载,处理机负载小于负载阈值,重载,处理机负载大于等于负载阈值,空载,处理机空闲,负载平衡,处理机均重载或处理机为空载和轻载,2024/11/20 周三,73,所生成的树,例：并行求解迷宫问题,2024/11/20 周三,74,1,2,3,4,5,6,7,8,方位图,2024/11/20 周三,75,x,y,为当前位置,Top,为路径栈指针,Level,存在未搜索分支树深度,n,未搜索的分支数,负载阈值：,0.25,按“征兵协议”,当该路径所有祖先都不存在未搜索的分支，并且当前位置（,x,y),后仅存在一条搜索路径，该处理机的负载为,0.125,否则处理机负载为,:top-level+n/8,2024/11/20 周三,76,执行过程,：（两台处理机）,P1,在,(0,0),，,P2,空载并征载，,P1,轻载不予响应,P1,到,(1,1),，,P1,重载并响应,P2,，,P1,分,(1,2),支给,P2,P1,搜索,(0,0),(1,1),(2,1),(3,1)(4,1),P2,搜索,(1,2),(1,3),(2,3),(3,3),.,P1,搜索到,(4,1),，无路回溯到,(0,0),，结束任务。,P1,空载征载,P2,到,(1,3),，有分支，负载为,0.25,，将,(0,3),支分到,P1,依此类推,2024/11/20 周三,77,试验结果：,单机搜索：,67,步,双机搜索：,47,步,十二次平衡 加速比,S,67/47,1.43,四机搜索：,33,步,十三次负载平衡，加速比,S=67/33=2,2024/11/20 周三,78,并行求解迷宫问题附加说明：,迷宫问题的描述,矩阵,MAZEx,y MAZEx,y=0,，可通过,MAZEx,y=1,，不能通过,MAZEx,y=2,，边墙,可以转化为一棵树表示可以通过的路径，变成为并行搜索树,2024/11/20 周三,79,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,1,1,0,0,0,0,1,1,1,1,1,1,1,0,0,2,2,1,0,0,0,1,1,1,1,1,1,1,1,1,0,1,0,2,2,1,0,1,0,1,1,0,0,0,0,1,1,0,1,1,0,2,2,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,0,2,2,1,0,1,0,1,1,0,0,0,0,0,1,1,1,1,1,2,2,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,2,2,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,2,2,1,1,1,0,1,1,0,1,0,1,0,0,1,0,0,0,2,2,0,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,2,2,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,2,2,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,2,2,1,1,0,1,1,0,0,0,0,1,1,1,0,0,0,1,2,2,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1,1,2,2,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,2,2,1,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,2,2,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,迷宫问题描述,2024/11/20 周三,80,搜索方向及相关变量,搜索方向：,8,个方向,搜索方位的上界与下界,0=base=7,0=bound=7,序号,cert,该结点在兄弟姐妹结点中的序号,搜索路径栈,pathstack,搜索过程矩阵,markx,ymarkx,y=0,未搜索,markx,y=1,已搜索,负载阈值,当前路径指针,top,最早出现尚未搜索分支的祖先深度,level,和未分支数,n,负载估算函数,lde=top-level+n/8,当,level=top,，,n=2,得到负载阈值,0.25,2024/11/20 周三,81,握手过程,征兵或招标协议，广播征载或发标请求 广播,重载或空载给予响应 多个点对点通信,选择重载或空载结点,确认平衡结点 点对点通信,实验多机系统：超立方体结构,握手过程：在超立方体结构上建立逻辑环网,2024/11/20 周三,82,进程迁移,进程分割 一般按负载的,1/2,分割。但将根据所求解问题的情况进行划分,进程迁移 包括 代码、数据和现场,结果回收,2024/11/20 周三,83,软硬件结构简单，但灵活性差,一旦主处理机发生故障，系统瘫痪,处理较多短任务时，增大管理工作量，主机负担重，系统效率低。,适用于由功能相差很大的处理机组成的非对称系统及工作负载不是太重的情况,2024/11/20 周三,84,在确定性调度中，任务的执行时间很难直接给出。一般是最大任务的执行时间或估计值，由于任务执行时间不确切，造成系统调度效率较低。,在不确定性调度中，使各处理机尽可能处于,“,忙,”,状态。可以有效利用系统资源，但会增加系统额外开销。,2024/11/20 周三,85,一个多机系统可由系统图,H,（,P,E),表示,P=p,1,p,2,.P,s,P,为处理机集,P,i,为结点权，表示处理机速度,E=e,1,e,2,e,r,E,通信链路集,e,j,为有向边权，表示两个处理机之间通信链路的带宽,调度过程可以归纳为任务图到系统图的映射,2024/11/20 周三,86,抢先调度,公度结点权,定义：,设如果存在一个正数,w,，使得每个结点的权是,w,的正倍数，称这组结点的权是相互成比例的或是可公度的。,公度（单位）结点权为,4,2024/11/20 周三,87,7,g:=a*b,8,h:=c*d,9,i:=d*e,10,j:=e*f,11,k:=d*f,12,l:=j*k,13,m:=4*l,14,n:=3*m,15,o:=n*i,16,p:=o*h,17,q=p*g,End,2024/11/20 周三,88,细粒度的并行调度方案如下（,8,处理器）：,P1,A,B,0,313,101,C,D,321,=101,E,F,531,523,G,H,751,743,J,K,L,M,N,O,P,P2,P3,P4,P5,P6,P7,P8,I,I,I,I,I,I,图中的阴影部分为通信延迟,I,表示处理机空闲,=8,d=212,=8,d=212,=8,d=212,2024/11/20 周三,89,几个基本参数：,负载,处理机运行的用户程序没有完成的工作量。包括计算时间和通信时间。往往与具体的求解问题有关，需要按一定的方法估算。,负载阈值,处理机负载的某一界限值。当某未完成任务的负载低于此值，就不适于再分解。,设任务,P,的计算时间为,Tp,，分解为两个子任务,P1,，,P2,。计算时间为,Tp/2,。若任务通信时间为,Tc,，当,Tp/22Tc,。,2024/11/20 周三,90,搜索方向及相关变量,搜索方向：,8,个方向,搜索方位的上界与下界,0=base=7,0=bound=7,序号,cert,该结点在兄弟姐妹结点中的序号,搜索路径栈,pathstack,搜索过程矩阵,markx,ymarkx,y=0,未搜索,markx,y=1,已搜索,负载阈值,当前路径指针,top,最早出现尚未搜索分支的祖先深度,level,和未分支数,n,负载估算函数,lde=top-level+n/8,当,level=top,，,n=2,得到负载阈值,0.25,</p>