静态负载分配

静态负载分配《分布式系统》(九20112负载分配分布式系统的资源管理模块，主要实现合理和透明地在处理器之间重新分配系统负载，以达到系统的综合性能最优。（最小的总体系统执行时间最大的总体系统输出）大致分为静态负载分配和动态负载分配2大类情况。静态负载分配：进程运行前进行处理器分配，运行中不作调整，直到运行结束；（确定性分配）动态负载分配：进程运行中动态进行处理器分配，且可以不断调整；（负载均衡）第2页,共56页，2024年2月25日，星期天《分布式系统》(九20113负载分配分类进程和处理器在负载分配时是M:N（多对多）的关系。有多种负载分配算法分类：负载分配局部全局静态动态分散式控制集中式控制协作非协作最优次优近似启发式单个处理器上多个进程对时间片的分配。先完成全局进程对处理器的分配，再在处理器内进行局部分配。进程执行以前的编译阶段完成进程对处理器的分配。进程在系统中执行时才作分配。得到一个最优的结果。得到一个次优的结果。搜索一个解空间的子集，寻找到一个较好的解。使用某些特殊参数，近似地对真实系统建模。决策工作被分配给不同的处理器。决策工作由一个处理器完成。不同处理器间有协同操作。各处理器独立做出决策。第3页,共56页，2024年2月25日，星期天《分布式系统》(九20114负载分配分类其它的负载分配算法分类：单个和多个应用程序抢占式的和非抢占式的自适应的和非自适应的第4页,共56页，2024年2月25日，星期天《分布式系统》(九20115静态负载分配根据先验知识在执行前调度一个任务（进程）集合，使它们总体上在各个目标PE上有最小的执行时间（代价）。静态负载分配问题也称为任务调度问题，它涉及到3方面的要素：处理器互连、任务划分和任务分配。负载分配有时即使加入执行开销和通信开销等假设仍然是一个NP完全问题，很难求得一个明确的最优解，我们总是用各种方法试图求得一个次优的解，或者加入一些特殊的约束以求得最优解。第5页,共56页，2024年2月25日，星期天《分布式系统》(九20116任务（进程）的图模型表示－任务优先图任务优先图G是一个有向无环图（DAG）xy任务优先顺序x：任务在处理器上的执行代价y：在不同处理器上启动后续任务所需的时间（处理器间通信代价）第6页,共56页，2024年2月25日，星期天《分布式系统》(九20117任务的图模型表示－任务相互关系图2个处理器的情况x,yz,z’任务通信x,y：任务在不同的处理器上的执行代价z,z’：在不同处理器上和在相同处理器上的任务间通信代价（通常z’可忽略）第7页,共56页，2024年2月25日，星期天《分布式系统》(九20118处理器互连a)Illiac网格方案（16个PE的系统）

2维节点度数：4

网络直径：n-1（n元）（常规2维网格的一半）第8页,共56页，2024年2月25日，星期天《分布式系统》(九20119处理器互连b)圆环方案（16个PE的系统）

2维节点度数：4

网络直径：2n/2第9页,共56页，2024年2月25日，星期天《分布式系统》(九201110处理器互连c)超立方体方案（16个PE的系统）节点度数：n

网络直径：nn维，每维2个节点

n维立方体是2个n-1维立方体互连而成。第10页,共56页，2024年2月25日，星期天《分布式系统》(九201111处理器互连d)WK网络方案（16个PE的系统）1层WK网络2层WK网络节点度数：4

网络直径：

n-1n层的WK网络由4个(n-1)层的WK子网络组成，每个子网络是一个虚拟节点。第11页,共56页，2024年2月25日，星期天《分布式系统》(九201112任务划分将一个大的任务（应用程序）分解成一些小的子任务类，每个子任务类作为分配给同一个PE执行。也称任务聚类。根据子任务类中基本任务单元（粒度）的大小，任务划分算法可分成：细粒度、中粒度、和粗粒度。粒度太大，会降低并行度；粒度太小，子任务进程的切换和它们间的通信代价会增加。任务划分的主要目标是尽可能地增加并行度和降低通信代价（寻找一个适中的粒度）。第12页,共56页，2024年2月25日，星期天《分布式系统》(九201113任务划分大体上有三种方法的任务划分：水平或垂直划分：根据任务优先图的关键路径（最长路径）垂直进行或任务分层水平进行；通信延迟最小划分：将通信频繁的基本任务节点归成一类，让其在同一个PE上执行，以最大限度地降低通信代价。此方法需要顾及并行任务串行化所带来的损失。任务复制：通过在PE上复制任务来降低通信代价，同时保留任务的并行性。此方法会增加PE的储存空间开销和PE间同步的开销。通常任务划分的子任务类数目等于PE的个数，以简化后续的任务分配。第13页,共56页，2024年2月25日，星期天《分布式系统》(九201114任务划分－线性和非线性任务划分后，如果至少有一个子任务类中包含两个独立的任务，则划分是非线性的；否则划分是线性的（所有独立的任务被划分在不同的任务类中）。如：T1T2T3d1d2a)线性划分T1T2T3d1d2b)非线性划分第14页,共56页，2024年2月25日，星期天《分布式系统》(九201115任务划分－衡量划分任务优先图可以认为是许多分叉和合并操作的集合：a)分叉c1xv1l1b)合并c2v2l2cnvnln…c1v1l1c2v2l2cnvnln…x分叉x（或合并x）的粒度是：g(x)=min{ck}/max{lk} 0

kn0

kn任务优先图G的粒度是：g(G)=min{g(x)}

xG第15页,共56页，2024年2月25日，星期天《分布式系统》(九201116任务划分－衡量划分如果g(x)>1（g(G)>1），合并或分叉（或图G）就是粗粒度的，否则操作或图就是细粒度的。如下图的非线性划分是粗粒度的（g(x)=2）。432T1T2T311第16页,共56页，2024年2月25日，星期天《分布式系统》(九201117任务划分－衡量划分可以证明，如果任务优先图G是粗粒度的，则其任何非线性的子任务类都可以转换（再划分）成具有更少或相等执行时间的线性分类。即：粗粒度的任务优先图其线性划分性能优于任何非线性划分。然而，如果任务优先图G是细粒度的，可能存在，也可能不存在一个非线性划分优于线性划分。第17页,共56页，2024年2月25日，星期天《分布式系统》(九201118任务划分－衡量划分例：432T1T2T311a)线性划分432T1T2T311b)非线性划分b)是粗粒度的，其非线性划分b)的执行时间是9，线性划分a)的执行时间是7；若将通信代价1变为4，则b)是细粒度的，其非线性划分b)的执行时间是9，线性划分a)的执行时间是10。4444第18页,共56页，2024年2月25日，星期天《分布式系统》(九201119任务分配将任务划分后的子任务类分配给PE的过程。在n个子任务类和n个PE间作映射分配，共有Cnn=n!种分配方法，根据PE的存储容量、处理能力和PE间的通信距离各映射分配方法会产生较大差异的效果。为了减少任务分配的复杂性，可以作一些假设：PE的存储容量无限每个PE有相同的处理能力忽略通信距离所造成的网络拥塞等。第19页,共56页，2024年2月25日，星期天《分布式系统》(九201120任务调度（静态负载分配）方法基于任务优先图的任务调度算法（算法1）任务优先图是一棵树（算法2）只有两个处理器基于任务相互关系图的任务调度任务调度评测使用其它模型和技术的任务调度Stone网络流量技术实现最优任务调度算法实时定期任务调度速率单调优先调度期限驱动调度第20页,共56页，2024年2月25日，星期天《分布式系统》(九201121基于任务优先图的任务调度对任务优先图，可以用G=(V，A)来描述，其中V是节点的集合，表示任务集；A是弧线的集合，表示任务间的优先关系。如：u、v是V中的节点（任务），(u,v)是A中的弧线链接。对于每个节点（任务）和链接都定义了代价函数w，其中w(u)(0,)表示任务u在处理器上执行的时间代价（所有处理器是相同的），w(u,v)=(l,l’)是链接的代价，其中l’是在同一处理器内的通信时间代价，l是处理器间的通信时间代价（u和v分配在不同处理器）。w(u)w(u,v)uv第21页,共56页，2024年2月25日，星期天《分布式系统》(九201122基于任务优先图的任务调度几点约束：处理器的处理能力是相同的。不考虑处理器互连，即忽略网络拥塞，也即处理器间的通信代价对所有处理器是一样的。相对l，l’是非常小的，可以忽略，因此w(u,v)=l。w(u)w(u,v)uv第22页,共56页，2024年2月25日，星期天《分布式系统》(九201123基于任务优先图的任务调度甘特图（GanttChart）任务分配表示：横坐标是处理器，纵坐标是时间，方块是任务的开始、持续和结束时间。T1T2T3T4T5时间0第23页,共56页，2024年2月25日，星期天《分布式系统》(九201124基于任务优先图的任务调度任务优先图的甘特图（GanttChart）任务分配表示例：T1T3时间1221T11424T2T3T4T51122T2T5T412a)任务优先图b)2个处理器的甘特图第24页,共56页，2024年2月25日，星期天《分布式系统》(九201125基于任务优先图的任务调度 在不同处理器上分配任务时，通信的开销对任务调度有较大影响，如：T1T2T3ddT1da)任务优先图b)调度结果1T2T3T1T2T3c)调度结果2T1T1T2T3d)调度结果3第25页,共56页，2024年2月25日，星期天《分布式系统》(九201126基于任务优先图的任务调度只有当通信代价较小时，将任务分配到不同的处理器是比较合适的（图c）；任务调度总是尽量将任务分配到不同的处理器以增加并行度，同时尽量降低通信的开销，然而二者有时是无法满足的矛盾，需要某种程度的折中；有时采用任务复制的方法实现可以得到一个很好的效果（图d）。第26页,共56页，2024年2月25日，星期天《分布式系统》(九201127基于任务优先图的两个最优调度算法为了实现最优，两个算法各自有约束条件：（算法1）任务优先图是一棵树。（算法2）只有两个处理器。 而且两个算法都假设通信代价可以忽略和优先图中每个任务节点的执行时间是一样的。两个算法都是最高级优先方法，即根据任务节点的等级来选择分配节点。第27页,共56页，2024年2月25日，星期天《分布式系统》(九201128最优调度算法1具体算法：任务节点的等级等于它到根节点的距离加1，等级越高，优先级就越高；相同等级的节点中，所有先导节点都已执行的节点先被选中；若有多个节点符合条件2，则随机选择。T1T2T3T4T5T6T7T8T9T10T11T12T13第28页,共56页，2024年2月25日，星期天《分布式系统》(九201129最优调度算法1在3个处理器上实现的例：T1T2T3T4T5T6T7T8T9T10T11T12T13T1T4T6T8T11T13T2T5T9T12T3T7T10时间0a)任务优先图b)算法实现的甘特图第29页,共56页，2024年2月25日，星期天《分布式系统》(九201130最优调度算法1使用一个就绪队列实现算法：就绪队列按优先级排列那些可以被选择分配给处理器的任务节点。T1T2T3T4T5T6T7T8T9T10T11T12T13就绪队列状态：(T1,T2,T3,T4,T5,T7,T9,T10,T12)

(T4,T5,T7,T9,T10,T12)

(T6,T9,T10,T12)

(T8,T12)

(T11)

(T13)等级54321第30页,共56页，2024年2月25日，星期天《分布式系统》(九201131最优调度算法2具体算法：将k个终止节点依次标记为1~k（标记越大，优先级越高）；寻找所有后续节点均被标记的节点；根据这些节点的后续节点排列的字典升序依次标记这些节点；重复2、3直到所有节点标记完毕；根据优先级的高低顺序依次将任务分配给2个处理器。11T9910T107T116T6T78T84T45T521T1T23T3第31页,共56页，2024年2月25日，星期天《分布式系统》(九201132最优调度算法2例的标记结果：T1,T2,T3,T4,T5,T6,T11,T8,T7,

T10,T9

11T9910T107T116T6T78T84T45T521T1T23T3T9T7T11T5T3T1T10T8T6T4T2a)任务优先图b)算法实现的甘特图(2个处理器)时间0第32页,共56页，2024年2月25日，星期天《分布式系统》(九201133最优调度算法2本算法有问题的！思考为什么需要是2个处理器的限制？还需要加入什么限制，算法才没有问题？提示比如：任务优先图中，去掉T10，算法会出现错误。第33页,共56页，2024年2月25日，星期天《分布式系统》(九201134基于任务相互关系图的任务调度假设任务关系图由无向图Gt=(Vt，Et)表示，其中Vt是任务节点集合，Et是边集合。处理器关系图由无向图Gp=(Vp，Ep)表示，其中Vp是处理器集合，Ep是边集合（处理器间的通信通道）。一般来说，如果任务划分已经完成，则|Vt|

|Vp|，我们进行映射分配M：Vt

Vp及执行时间估计： 设w(u)和w(u,v)分别是节点u和连接(u,v)的代价。 处理器p

Vp的计算负载：Comp(p)=w(u)|M(u)=p uVt

通信负载：Commp(p)=w(u,v)|M(u)=pM(v) (u,v)Et第34页,共56页，2024年2月25日，星期天《分布式系统》(九201135基于任务相互关系图的任务调度一个应用程序总的计算和通信负载：Comp=

Comp(p)=

w(u)|M(u)=p pVp pVpuVtComm=1/2

Comm(p)=1/2

w(u,v)|M(u)=pM(v) pVp pVp(u,v)Et总的程序执行时间估计：T＝max{Comp(p)+Comm(p)},pVp

是依据每个PE的执行速度设定的调节比例；是依据每个通信信道的通信速度和通信进程间的距离设定的调节比例。第35页,共56页，2024年2月25日，星期天《分布式系统》(九201136基于任务相互关系图的任务调度理想情况下，任务关系图中相邻的节点应被分配在相邻的处理器上，以减少处理器间长距离的通信。因此，评估映射质量的一个指标是任务关系图Gt的边映射到处理器图Gp的边的数目，这个数目称为映射的势，映射的势

Gt的边数，映射的势越大则越理想。第36页,共56页，2024年2月25日，星期天《分布式系统》(九201137基于任务相互关系图的任务调度下例中，映射的势是8（共13条边）映射的势并不能完全反映出映射的质量，这主要表现在势以外的边所对应的处理器的距离。（图中虚线的距离）134562789123456798第37页,共56页，2024年2月25日，星期天《分布式系统》(九201138基于任务相互关系图的任务调度P203使用嵌入技巧来衡量利用任务相互关系图分配任务到处理器关系图时的理想程度。其目标：发现一个嵌入，有最小膨胀、最大扩大和最小拥塞。即上图中，虚线的数目最少，且最短；任务节点到处理器节点的数目最多；经过一个处理器边（通信链路）的任务边数最小。*书中错误：（P203,第8行）嵌入的负载，是Gt分配给Gp中任意……第38页,共56页，2024年2月25日，星期天《分布式系统》(九201139网络流量技术实现最优任务调度Stone网络流量算法：一个在双处理器且处理器有不同处理能力的系统中对任务相互关系图的最优调度算法。图的分割、带权分割：tsd分割为图中边的子集：1)删除这些边后使图不连通；2)这些边的任何子集都不满足上一点。带权图的分割为带权分割。分割后的2部分中各包含s和t的分割，称为s-t分割或s-t带权分割。第39页,共56页，2024年2月25日，星期天《分布式系统》(九201140网络流量技术实现最优任务调度网络的分割、带权分割：边的流量不能超过边的容量，网络的流量不能超过分割的容量；除起始节点和终止节点，节点的流入流量等于节点的流出流量；起始节点只有流出，终止节点只有流入。ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第40页,共56页，2024年2月25日，星期天《分布式系统》(九201141网络流量技术实现最优任务调度Ford-Fulkerson最大流-最小割理论：最小的带权分割就是最大的网络流量。（根据容量图）ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第41页,共56页，2024年2月25日，星期天《分布式系统》(九201142网络流量技术实现最优任务调度确定了最大的网络流量就确定了最小的带权分割。确定网络最大流量的算法：使网络流量最大化的进程方法。从任意一种流开始，寻找可能存在的增加路径（augmentingpath），在该路径上：对于前向链接，它有富余的容量；对于后向链接，它有反向的流量。消除这些增加路径：对于前向链接，增大实际的流量；对于后向链接，减少反向的流量。直到网络中没有增加路径为止。此时，网络的流量最大，它的一个分割（其各链接边的容量等于实际流量）就是最小带权分割。第42页,共56页，2024年2月25日，星期天《分布式系统》(九201143网络流量技术实现最优任务调度利用网络最大流量就是图的最小带权分割技术，实现对2个处理器的最优任务分配。任务相互关系图T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893在2个处理器上的执行代价，-表示不能在该处理器上执行。在不同处理器上的通信代价。第43页,共56页，2024年2月25日，星期天《分布式系统》(九201144网络流量技术实现最优任务调度分别将2个处理器作为s和t加入任务关系图中，增加s和t到各任务的边（共2n条），边的权值为任务在该处理器上的执行代价，形成任务分配图。T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893T2T1T44892tT3s3445-773任务相互关系图任务分配图第44页,共56页，2024年2月25日，星期天《分布式系统》(九201145网络流量技术实现最优任务调度利用网络最大流量算法在网络流量图中寻找最大网络流量（以s为起点、t为终点，初始实际流量设为0）。T2T1T44,08,09,02,0tT3s3,04,04,05,0-,07,07,03,0第45页,共56页，2024年2月25日，星期天《分布式系统》(九201146网络流量技术实现最优任务调度得到的最大网络流量，就是最小网络分割，也即任务的最优分配。最小分割的权重（各分割边的权之和）即任务分配后的最小代价（执行代价和通信代价）之和。T2T1T44,08,39,02,2tT3s3,34,44,45,4-,67,27,73,0如图的最小代价是16，分配方案是T1、T2、T3、T4均在一个处理器s上执行。最小分割第46页,共56页，2024年2月25日，星期天《分布式系统》(九201147网络流量技术实现最优任务调度前述是一个利用网络最大流算法得到最小分割的方法，适合在计算机环境下编程实现。人工计算相当麻烦！！！一个可行的人工计算方法：（“笨”的、穷尽的方法）T1T2T44892tT3s4345-773(34)(38)(33)(16)可能的分割(分配)：T1*T1T2*T1T3T1T4T1T2T3T1T2T4*T1T3T4T1T2T3T4*比较各种分割的权重。第47页,共56页，2024年2月25日，星期天《分布式系统》(九201148实时定期任务调度实时定期任务（Ti）定期（间隔周期ti）出现，每次运行时间为ci，在下一次出现前（期限，即n*ti），前一次任务必须运行结束（实时）。处理器的整体利用率：

n

ci/ti

i=0第48页,共56页，2024年2月25日，星期天《分布式系统》(九201149实时定期任务调度实时定期任务调度2个算法（单处理器，多个独立实时定期任务）速率单调优先调度有高速率（间隔周期小）要求的任务有高优先权；优先权是固定分配的。期限驱动调度离结束期限最近的任务有高优先权；优先权是动态分配的。2个算法都是基于优先权和抢占式的。第49页,共56页，2024年2月25日，星期天《分布式系统》(九201150实时定期任务调度一个实时定期任务集合是可调度的，说明任务集中所有任务的期限要求都可以满足。在不同的实时定期任务调度算法下，一个实时定期任务集可能可调度，可能不可调度。可以证明：对期限驱动算法，一个任务集可调度的充分条件是：

n

处理器的整体利用率

ci/ti1

i=0对速率单调算法，一个任务集可调度的充分条件是：

n

处理器的整体利用率

ci/tin(21/n-1)

i=0

n为任务个数：如n=1时，限度为1；n=2时，限度为0.828，n=3时，限度为0.779。第50页,共56页，2024年2月25日，星期天《分布式系统》(九201151实时定期任务调度如：2个实时定期任务开始于同一时间

T1：c1=3,t1=5 T2：c2=3,t2=8

整体利用率是0.975，如下图：T1T200c1c2510858调度点t1t2

对速率单调算法，系统是不可调度的；对期限驱动算法，系统是可调度的。225第51页,共56页，2024年2月25日，星期天《分布式系统》(九201152实时定期任务调度但前述条件是充分条件，而非必要条件，如

T1：c1=3,t1=5 T2：c2=2,t2=7

整体利用率是0.887，高于0.828，但对速率单调算法，系统仍是可调度的。如下图：T1T200c1c2510757t1t2第52页,共56页，2024年2月25日，星期天《分布式系统》(九201153实时定期任务调度所有任务的期限点组成系统的调度点（但在最长的第一个期限内）。在不同的调度点，任务集可能可以调度，可能不可以调度。只要有一个调度点，任务集可以调度，则整个任务集就是可以调度的。（例）3个任务的任务集：

T1：c1=40,t1=100 T2：c2=50,t2=150