并行算法的设计与分析第19章.ppt

第19章并行算法（程序）性能优化任务调度,任务调度的概念,调度问题的一般模型构成调度问题的基本元素：资源集、消费者集及这些资源为这些消费者服务所依据的一定规则。调度问题就是在满足资源集和消费者集约束条件的基础上，设计一个有效的调度系统来管理消费者如何高效地使用这些资源，并使得一些系统性能指标达到最优或近似最优。,调度问题的一般模型,任务调度的概念,调度问题的一般模型调度性能和调度效率是评价一个调度系统优劣程度的两个方面。调度性能（SchedulingPerformance）通过性能测试指标的取值来反映，它直接体现了调度结果的好坏。调度效率（SchedulingEfficiency）主要指调度系统本身的复杂度。,任务调度的概念,并行计算中的任务调度并行分布计算中的任务调度问题：根据一定的调度规则和调度策略，把组成并行程序的一组任务或构成工作负载的一组作业，按照一定执行时序分配到并行分布系统的多个计算节点上，以期取得较好的系统执行性能。任务调度与作业调度任务层调度针对某个用户的单一并行应用程序的一组任务（子任务），面向的一般是单应用程序系统，它的调度实体是任务，调度目标一般就是求得任务最短的执行时间。作业层调度针对若干个用户的多个并行应用程序构成的一组作业，面向的一般是多应用程序系统，它的调度实体是传统批处理意义下的作业，调度目标有多个，如最短的平均作业响应时间、最大的资源利用率或最大的系统吞吐率等。,任务调度的概念,并行计算中的任务调度任务调度与任务划分在分布系统中一组任务相互间发生关系的方式有多种多样，其中有一种是通信关系，如果两个任务被分配到不同的处理器上，那么就产生以通信成本形式表示的通信开销（CommunicationOverhead），如果两个任务被分配到相同的处理器上，那么就不产生任何通信开销，这种特殊的任务调度我们称作任务划分（TaskPartitioning）。对于任务划分，我们通常用任务交互作用图（TaskInteractionGraph）来表示并行算法（程序）模型对于任务调度，通常用带权有向图（WeightedDirectGraph）来表示并行算法（程序）模型。,任务调度的概念,并行计算中任务调度的分类静态调度、动态调度和混合调度静态调度（StaticScheduling）在编译并行程序时，就决定每个任务的执行处理器及执行时序，它经常用于任务图比较确定的情况。动态调度（DynamicScheduling）在并行程序运行过程中，根据当前任务调度及系统执行情况，实时决定每个任务的执行处理器及起始执行时刻。混合调度（HybridScheduling）介于静态调度和动态调度之间的调度方法，它在编译时先静态调度部分任务，而剩余部分则采用动态调度方法在系统运行过程中来给它们分配处理器。,任务调度的概念,并行计算中任务调度的分类最优调度和启发式调度最优调度一般是指静态调度，如果一个调度算法能在多项式复杂度的时间内获得最佳调度结果，那么称之为有效的最优调度算法。启发式调度方法将任务调度分配到各处理器上，它虽然不能确保获得最优解，但可以获得最优调度的近似解。共享存储结构的任务调度和分布存储结构的任务调度共享存储结构的任务调度：不考虑通信延迟，任务调度的着重点在于如何最大限度地获得并行程序任务间的并行性。分布存储结构的任务调度：通信延迟的存在使得任务调度更为复杂，需尽可能利用各任务之间的并行性和尽量减少计算节点通信开销之间进行折衷。,任务调度的概念,并行计算中任务调度的分类集中式调度和分布式调度集中式调度：由一个叫作中心调度器的处理器来收集全局调度信息，其他处理器把它们的状态信息传送给中心调度器，并由中心调度器作出调度决定。优点在于实现比较简单，但在计算节点数较多的大规模并行分布系统中，各节点与调度服务器的通信成为瓶颈，调度开销比较大。分布式调度：由各处理器的调度程序根据局部范围内的一些调度信息来调度任务。优点在于具有良好的可扩放性（Scalability），但调度算法复杂。,任务调度的概念,并行计算中任务调度的分类抢占式调度和非抢占式调度抢占式调度：动态地将优先权更高的任务调度分配给处理器。自适应调度和非自适应调度自适应调度（AdaptiveScheduling）：根据调度程序在以前一段时间内的执行效果，以及当前系统状态信息（系统资源和任务负载情况）自动修正调度程序的执行机制，它们通过收集当前系统状态信息来动态修正调度策略。非自适应调度（Non-adaptiveScheduling）：一旦确定任务调度算法的调度策略，那么在并行程序执行过程中就固定地按照这些调度策略来进行任务调度，即使某些不确定因素（如动态产生的任务）使得调度效率比较低，那么也必须等到非执行状态时，再修正调度策略。,任务调度的概念,并行计算中任务调度的模型并行应用程序任务一个并行应用程序的性质可用(A,D,W)来刻画，其中A=ak|k=1,2,n为任务集；D=dij|i,j=1,2,n是一个nn的通信矩阵，dij(0)表示任务ai传送给任务aj的数据量；工作负载W=w(ai)，w(ai)表示任务ai的工作负载大小。在同构的并行分布系统中，由于每个节点的计算能力（包括运算速度、内存大小等）相同，所以也可以直接用w(ai)来表示任务ai的执行成本。而在异构的并行分布计算环境下，相同负载在不同的（计算能力不同）节点上的执行成本是不相同的。“”定义了任务间的偏序（PartialOrdering）关系,“aiaj”表示任务aj的执行依赖于任务ai的执行。,任务调度的概念,并行计算中任务调度的模型目标机器（TargetMachine）假定有m个处理器组成，该m个处理器可以是同构的，也可以是异构的，它们通过任意的互连网络进行连接。每个处理器某一时刻只能处理一个任务，每个任务可在任何一个处理器上运行。可用六元组TM=（P,Pij,Si,Ii,Bi,Rij）来刻画目标机器的特性：P=P1,P2,Pm为构成并行分布系统的一组处理器；Pij为mm的互连网络拓扑矩阵；Si(1im)为处理器Pi的执行速度；Ii(1im)表示在处理器Pi上启动一个消息传递所需的时间；Bi(1im)表示在处理器Pi上启动一个进程执行所需的时间；Rij(1im,1jm)为两个相邻处理器之间的消息传输率，即每单位时间传送的数据量。,任务调度的概念,并行计算中任务调度的模型执行时间与通信开销tij表示任务ai在处理器Pj上的执行时间表示处理器P上的任务a与处理器P上的任务a之间的通信开销，如果这两个处理器相邻，则其中R表示这两个处理器间的传输率，O表示P与P之间通信线路的竞争开销。如果P与P之间不相邻，假定每两个相邻处理器之间的消息传输率均为R，每个处理器的消息传递启动时间均为I，用H表示处理器P到处理器P的线路条数，则,任务调度的概念,并行计算中任务调度的模型调度及调度目标并行应用程序的一个调度其实就是其对应的任务图G到目标机器的一个映射f：VP1,P2,Pm0,，f(ai)=(p,t)表示任务ai被调度到编号为p的处理器上，起始执行时刻为t。一般地，我们可用Gantt图GC=(p(ai),t(ai)|aiV来直观地表示调度结果，其中函数p(ai)表示分配给任务ai的处理器号，t(ai)表示任务ai的起始执行时刻。一般入口节点任务的起始执行时刻以零计算，那么所有任务执行完的那个时刻称为调度长度SL（SchedulingLength），它反映了整个并行程序任务的执行时间，显然SL=t(ai)+w(ai)/Sj，其中j=p(ai)。任务调度的目标就是要获得最短的整个应用程序执行时间，即最短的调度长度。,静态任务调度的最优算法,在忽略通信延迟的情况下，对任务图再加以一些限制条件可以得到最优调度算法。限制一：任务图是树结构。代表算法：T.C.Hu线性的最优调度算法、M.Kaufman最优调度算法。限制二：区间有序条件。代表算法：C.Papadimitriou算法。限制三：对目标机器加以限制。代表算法：E.G.Coffman调度算法，时间复杂度为O(n2)。,静态任务调度的启发式算法,贪心算法基本思想是优先权高的任务先执行，又称为优先权队列调度（PriorityListScheduling）。任务一旦分配出去通常就不会再更改，称为无回溯（Non-backtracking）。贪心算法的关键在于优先权，可以分为静态优先权和动态优先权两大类。常用的几种贪心算法：最高层次优先HLF（HighestLevelFirst）最长路径优先LPF（LongestPathFirst）最早任务优先ETF（EarliestTaskFirst）最大处理时间优先LPTF（LargestProcessingTimeFirst）最大总代价优先LGCF（LargestGlobalCostFirst）,静态任务调度的启发式算法,随机算法算法的主要思想：采取某种随机扰动的机制来跳出局部最优解以便获得更优的解。模拟退火：一个调度方案s及其代价函数f(s)分别对应于固体的一个微观状态及其能量，再设置一个随算法过程递降的控制参数t来表示固体的温度。算法将施行“产生新方案s判断接受舍弃”的迭代过程。其中，新方案s的接受概率p可计算如下：刚开始的时候t值较大，当f(s)f(s)时，s将以较大的概率被接受；随着t值的减小，这个概率也将减小并趋向于零。这种机制使得算法既能跳出局部最优（LocalOptimal）的陷阱，又能稳定收敛到系统的最终稳态，是整个算法的关键所在。,静态任务调度的启发式算法,随机算法禁忌搜索：在每次迭代中都向近邻集合中的最优方案移动。为了避免循环移动和陷入局部最优，该算法通过建立禁忌列表（TabuList）用以记录先前移动步的信息，并从近邻集合中删除相应的元素。禁忌列表是一个有长度限制的先进先出队列。遗传算法：算法以字符串代表基因（Gene），字符串集合代表种群（Population），以适应性函数和代价函数表示物种的适应度（Fitness）。算法首先产生一组的字符串，即种群；然后在每一次迭代中，选择部分基因执行遗传操作，适应度越高的基因被选中的概率越大，这样做是为了让优秀的遗传特征能以较大的可能性被保留下来，而低劣者则被淘汰，从而提高种群的整体适应度，并最终产生次优解。,静态任务调度的启发式算法,聚簇策略聚簇策略实际上是上述贪心算法和随机算法的一个折衷，通过将一些任务合并成一个簇（Cluster），增加问题粒度，减小问题规模，从而达到这样一个效果：既具备贪心算法的高计算效率，又能保证解的质量不会跟随机算法的相差太多。分类：合并法（AgglomerativeAlgorithms）：开始时把每个任务看成是一个簇，然后执行合并操作，每次选择最合适的两个簇进行合并，直至簇的数目达到预定的要求。分割法（DivisiveAlgorithms）：开始的时候把所有任务作为一个簇，然后执行分割操作，每次选择合适的簇进行分割，直至簇的数目达到预定的要求。,动态负载平衡,基本概念负载平衡（LoadBalancing）策略是为了提高并行机的利用率，将提交的作业任务与并行机中计算节点进行有效的匹配，使各节点被指派的任务量与其处理能力相当。负载平衡又分为静态负载平衡SLB（StaticLoadBalancing）和动态负载平衡DLB（DynamicLoadBalancing）两类。静态负载平衡是在程序执行之前根据每个节点的计算能力指派（Assignment）作业。动态负载平衡是在程序执行过程中在并行计算机各个处理器间进行任务的重新分配。一个好的动态负载平衡系统需要解决以下三方面的问题：如何收集系统当前的负载信息（由负载信息管理进程LIM负责）；根据收集的负载信息如何决定是否进行迁移以及向何处迁移（由负载迁移管理进程LMM负责）；在做出迁移决定后如何进行任务的迁移（由负载迁移决策进程LMD负责）。,动态负载平衡,负载平衡的一个简单实例,动态负载平衡,负载信息收集负载信息管理进程负责收集并管理系统中各节点的负载信息，并向后续的负载迁移决策提供原始数据。按需收集（On-demandCollection）：每当系统需要进行下一次的动态负载平衡DLB策略时才开始由LIM进程收集各节点的负载信息。周期间隔收集（PeriodicalCollection）：每隔一定的时间周期，各个节点才向其他节点发送最新的负载状况。变化收集（On-state-changeCollection）：随着时间的变化，收集系统中各节点的负载状态改变信息。,动态负载平衡,负载迁移决策1动态负载平衡调度策略集中式动态负载平衡调度策略分布式动态负载平衡调度策略半分布式策略：半分布式的负载迁移决策策略LMD是以上两者折衷，目前在大规模的并行计算机系统中使用较多。,（分布）,（集中）,动态负载平衡,负载迁移决策分布式动态负载平衡调度规则,分布式动态负载平衡调度算法的规则构成,动态负载平衡,负载迁移决策分布式动态负载平衡调度方法算法分类：基于随机选择任务移动节点的随机调度算法根据负载变化差额而基于梯度模型的调度算法自适应的近邻契约算法算法都需解决三个问题：什么时候启动负载平衡调度？每次平衡调度的源节点和目标节点是哪些？选择哪些任务进行调度？按一次局部负载平衡调度的启动者来划分：接收者驱动、发送者驱动、混合驱动任务调度三大类。,动态负载平衡,负载迁移决策分布式动态负载平衡调度约束条件基本的调度约束条件：平衡约束（EquilibriumConstraint）条件，该条件主要用来局部平衡各处理器的工作负载，每个处理器根据系统的拓扑连接结构及平衡约束条件，把部分过重任务负载迁移到负荷较轻的相邻处理器上。一般的成本约束（CostConstraint）条件：不仅考虑处理器之间的负载平衡，而且还针对不同的具体并行分布系统，进一步根据某些成本指标进行任务调度。,动态负载平衡,负载迁移决策负载迁移策略接收者驱动策略：由空闲节点逐个向邻接节点请求任务，如果请求到任务，那么就中止请求，否则就继续询问下一个相邻节点。也有可能所有相邻节点都没有满足请求，那么请求节点就等待，过一段时间后再向相邻节点发出任务请求。优点：不需要相互交换负载信息；对于大规模并行计算问题，当每个节点均处于忙状态时，几乎不需要额外调度开销；负载平衡的许多工作由空闲节点来完成。缺点：在开始和结束阶段，任务数相对较少，许多任务请求会延迟忙节点的执行。算法实例：事件驱动（TDS）算法,动态负载平衡,负载迁移决策负载迁移策略发送者驱动策略：节点间的任务调度分配由创建任务的节点来执行，至于分配给哪个邻接节点，主要取决于邻接节点的负载状态，因此，该策略需要交换处理器的负载信息。优点：没有过重负载的忙节点不会被空闲邻接节点所打扰。缺点：负载过重的忙节点还要额外增加处理负载平衡调度的负担。算法实例：招标（Bidding）算法,动态负载平衡,负载迁移决策负载迁移策略混合驱动策略：结合接收者驱动和发送者驱动这两者优点，只有当负载状态发生变化时，才交换负载状态信息，因而减少网络竞争。具有空闲信息的负载消息也被看作任务请求，如果不能满足该请求，那么就记录下请求任务的节点号，以后产生新任务时，就把该任务发送到该空闲的邻接节点上，这样就避免了接收者驱动策略中的反复请求，从而减少通信开销。为了减少消息传递数量，可在向邻接节点传递任务消息和结果消息时，把自身当前的负载状态消息也附上。因此，每个节点都具有记录邻接节点负载状态信息及相互间任务传递情况的一组属性。,动态负载平衡,负载迁移执行迁移负载的类型负载选择：可供选择的负载有进程、线程、数据等，在数学上是一个子集求和问题（SubsetSumProblem）。负载迁移：数据迁移所需要处理的是数据的重新分配。线程迁移的时候只需要将该线程的状态以及其所需要的数据从一个节点传送到另一个节点。进程迁移，对该进程的状态以及数据进行节点间的传输。但是与线程迁移相比较，进程迁移需要关注更多的状态信息，同时还可能需要进行可执行代码的传输。,动态负载平衡,负载迁移执行进程迁移迁移初始化：启动负载迁移管理进程LMM，确定要迁移哪一个进程，迁移到哪个