关于任务调度相关研究文献综述

关于任务调度相关研究文献综述随着多核处理器的出现，多核处理器任务调度已成为当前高性能处理器研究的热点之一。任务调度是指系统为确定一系列任务的执行顺序所采取的调度策略。随着计算机技术的不断发展，学术界对任务调度问题的讨论也逐渐深入，旨在通过减少通信开销、改变任务执行顺序，以缩短整个任务的调度长度。近年来，由于多处理器的广泛应用，如何充分利用多处理器的计算性能成为了大家关注的焦点，针对多处理器的任务调度问题突显出来。在多处理器任务调度算法研究的早期，PDutot［24］等人在研究中指出，对于异构计算环境下的任务调度问题是NP难问题，难以在多项式时间内寻求最优解。正是该问题的重要性和复杂性，吸引了一大批专家学者对其进行研究，并提出了大量经典的算法。一、国外研究现状计算机任务调度的研究早在上世纪60年代就已开始。1967年，芝加哥大学的ManacherG.K在ACMfi刊上第一次提出了“任务”的概念，并利用列表法和甘特图进行了基本的多核多任务调度算法研究，提出了能够保证调度稳定性的算法。同时文章对软实时系统和硬实时系统也给出了定义和说明。但是由于文章发表年代较为久远，文中提出的是同构多核处理器的模型，并不适用于当今迅速发展的异构多核处理器之间的任务调度。随后，刘炯朗和Layland在已有工作基础上提出了周期任务模型的概念，该模型对任务进行了较好的抽象，对周期性任务做出了一些假设，忽略计算机体系结构的复杂性以及应用程序的具体实现，可以借助各种数学方法对任务的可调度性进行分析。文中提出了可在单处理器上运行的三种调度算法：单调速率算法RM(ratemonotonicalgorithm)、最早结束优先EDF(earliestdeadlinefirst)算法［1］以及两者的混合算法。在RM算法中，根据任务的需求速度赋予其一定的优先级，即所谓的固定优先级。在EDF算法中，任务最终期限值较小的赋予更高的优先级，即动态调整任务的优先级。而综合算法将任务分开对待，分别使用上述的算法。文章分析了在上述几种任务调度算法下，CPUfg够达到的最大利用率，并用数学方法给予了证明。为后来的研究奠定了基础。后续又提出了许多经典算法，包括时间片轮转(RoundRobin,RR)算法、先到先服务(FirstComeFirstServed,FCFS)K法、截止期单调调度(DeadlineMonotonicScheduling,DMS)算法等。在这些算法中，任务的优先级都是基于任务的某些特征参数，如截止期、空闲时间或关键性等计算而得。然而，如果优先级仅由某个特征参数来确定是不够的，因为截止期或者空闲时间短的任务不一定是最关键的。而且这些算法主要是针对单核处理器，并不适用于多核处理器的任务调度。对于异构计算环境下的任务调度问题是NP完全问题，难以在多项式时间内寻求最优解。正是该问题的重要性和复杂性，吸引了一大批专家学者对其进行研究，并提出了大量经典的算法。HalukTopcuoglu和SalimHariri等人通过对异构环境下的任务调度进行大量分析，在1999年提出了两种到目前为止公认的调度效率较高的算法：基于处理器关键路径算法[8](CriticalPathOnaProcessor,CPOPf口异构最早结束时间算法网(HeterogeneousEarliestFinishTime,HEFT),是异构多处理器任务调度十分经典的调度算法。后期许多任务调度的算法都是在这两种算法的基础上提出的。这些算法都使用有向无环图(DirectedAcyclicGraph,DAG来表示任务模型，节点上和节点间都根据时间开销赋予一个权值。在任务排序和任务分配两个阶段采用不同的方法来提高任务调度的效率。HEFT算法思想描述如下：在任务排序阶段，每个任务根据自身的运行时间和与后继任务的通信时间计算出一个向上排序值ranku(n),根据ranku(n)降序排列每个任务；在任务分配阶段则根据最早完成时间进行分配，这种机制降低了算法复杂度，但同时处理器的利用率有待提高。与其它基于最早完成时间的调度算法有所不同，HEFT算法采用了区间插入技术，在同一处理器两个相邻任务间可能插入其它任务间隙处，插入一个新的任务来提高多核处理器的并行性和利用率，从而提高调度效率。但是该算法存在一些明显的缺点：任务排序只考虑到与后继任务的通信开销，让一些向上排序值高的节点优先运行，但没有从整体的拓扑结构考虑任务的关键程度，某节点向上排序值高并不代表此节点在整体拓扑结构的关键路径上，也就是说，有些关键节点可能得不到较高的优先级；能够利用区间插入技术插入到某个空闲时段的任务可能并不多；没有考虑较大任务间的通信开销，如果两个较大任务被分配到不同的处理器，任务间的通信开销可能远远超过任务本身的运行开销。HEFTJT法的时间复杂度是O(n2*p),n表示任务个数，p表示处理器个数。考虑到HEFTK法存在白问题，HalukTopcuoglu等人又提出了一种CPOPJ法。该算法在任务排序阶段不仅考虑了向上排序值ranku(n),而且还考虑了向下排序值rankd(n),通过两者的综合加上自身运行开销，计算每个节点的优先级权值，并且得到一个关键路径，然后选择一个串行执行这些关键路径任务时间最短的处理器CPP任务分配阶段，把属于关键路径上的任务分配到CPP非关键路径上的任务分配到具有最早完成时间的处理器上，后者结合了区间插入技术。关键路径是任务图中距离最长的路径，关键路径长度决定了整个任务图的完成时问，所以CPOPJ法的目的是给关键路径上的任务更高的优先级，保证关键任务优先调度，以此来缩短整个任务完成时间。但CPOPJ法同样存在一些不足：只考虑了提高关键路径节点的优先级，有可能忽视了某些关键节点的父节点，但这些父节点又不在关键路径上，CPOP算法中该类非关键路径节点的优先级可能很低，非关键路径节点的延迟调度将会影响关键路径的完成时间，降低整个调度算法的效率；同时，这种分配机制导致执行关键路径的处理器负载偏重，而其它处理器利用率并不一定很高，从而降低了处理器的利用率，导致处理器负载不均。止匕外，在异构多处理器任务调度算法中，经典的启发式算法还有Max-min、Min-min、Sufferage等。TracyD.Braun等人对这些算法做了比较和实验，给出了各种算法的实际性能[12]oMax-min算法首先计算任务的预期完成时间(ExpectedEarliestCompletionTime,EECT)然后优先调度EECT1大的任务，优先对其进行资源分配。这种调度方法可以保证颗粒大的任务较好地被执行，能够在一定程度上实现负载均衡。但该方法没有考虑任务的执行频率，对于那些执行频繁的小任务，提高它的执行优先级可能会取得更好的整体性能。同Max-min算法相似，Min-min算法也是根据任务的EEC怵确定任务调度优先级。不过，Min-min算法将EECT最小的任务对应最高的优先级，即将颗粒小的任务优先分配到最佳处理器上，依次完成任务的划分。该算法实现简单、复杂度较低。但算法策略单一，在按EECTV」、到大顺序对任务划分时，容易引起处理器负载不平衡。Sufferage算法在Max-min和Min-min算法的基础之上进行改进。对于每个任务，计算其次早完成时间(放在次优处理器上执行的时间)与最早完成时间的差值，该差值命名为Sufferage值，反映出各个任务的调度代价。Sufferage算法按Sufferage值从大到小确定任务的优先级，以保证调度所带来的代价最小。但该算法只考虑任务单次执行的情况，没能考虑任务的执行频率，从而没有不能计算在一段时间内的总代价，不能取得很好地负载均衡。同时没有考虑任务最早完成时间，故系统总的执行时间难以最优。另外，SanjoyBaruah教授及其小组在任务调度与分析领域的研究比较活跃，相继发表了一系列有影响的文章[5][6][7]o同时，各研究者根据不同的应用需求，提出了多类调度算法。为了减少任务之间的通信开销，许多学者提出了基于任务复制(TaskDuplicationBased,TDB)及分组等多种调度算法。Kwok和Ahmed1出了关键路径快速复制(CriticalPathFastDuplication,CPFD笄法[20],Bansal等提出了有限复制的调度算法[21],Shin等人提出了最小复制算法㈤。这些算法都属于基于任务的调度算法，通过在多个处理器之间对任务进行复制，从而减少处理器之间的通信量。Abdelzaher和Shin在文献[23]中，根据实时任务的周期进行了分簇。他们的方法可以处理任务的异构性，扩展性强。传统的启发式算法无法适应所有的任务模型。在采用传统启发式算法之前往往需要对任务进行假设，这使得一种启发式算法只能应用于特定的任务模型。于是许多人工智能算法被运用到任务调度问题上来。人工智能方法通过模拟各种自然活动，通过演化迭代的方式来求取问题的解，越来越多地被引入到启发式算法当中。目前，对于人工智能方法的研究已经深入，许多方法形成自己的理论体系，为解决不同的复杂问题提供科学指导。这些方法有遗传算法(GeneticAlgorithm,GA卜模拟退火(SimulatedAnnealing,SA)算法、蚁群算法(AntColonyOptimization,ACO以及粒子群优化算法(ParticleSwarmOptimization,PSO痔。这些算法都是模拟自然环境下的各种行为，从而求解过程具有随机性，比传统算法减少了人工干预。这些特点对于寻找全局最优解方面具有独特优势，为求解复杂问题提供了新的思路和解决方案，也广泛应用在任务调度这一复杂问题当中。二、国内研究现状相对于国外的研究，国内在多核处理器任务调度方面的研究起步比较晚，一直处于跟踪研究阶段，但随着近年来国内专家对任务调度研究的重视，仍取得了不少成果。中国科学院软件研究所的戴国忠、王宏安等人发表了一系列研究成果[32],采用集中式的调度方案，考虑任务划分策略及软实时任务的服务质量，以统一方式完成对实时异构系统中硬实时和软实时任务的集成动态调度，提高了算法的调度成功率。止匕外，一些研究也对多处理器调度问题提出了新的算法和见解。针又tfork-join图结构刘振英等人提出了一个新的算法TSA_FU4](TaskScheduleAlgorithmFork-Join)。TSA_FJ算法的原则是让Fork-join任务图中的最后一个任务节点尽早开始执行。该算法着眼于解决任务调度中被忽略的一个问题，通信信道使用冲突。在大多数任务调度算法中都是允许通信重叠的，也就是可以并行执行通信，在安排任务的起始执行时间时，仅考虑该任务接受最长消息需要的时间，实际任务需要的消息并没有全部获取就开始执行。但是现实中的并行计算系统处理器在接受发送消息时是用行进新的，所以传统调度算法和实际计算环境并不相同。为了解决这个问题作者提出了TAS_FJ来解决实际通信信道占用问题，并且力图使得处理器的消耗量最小。邱卫东、陈燕等人以提高现有启发式算法的性能为出发点，提出了一个异构分布式系统的动态BLevel优先算法阳。该算法选择就绪任务中动态BLevel值最大的任务，考虑任务之间的依赖关系，将其划分到完成时间最早的处理器上。如果超过一个处理器具有相同的最早完成时间，则将任务分配到利用率最低的处理器上执行，以降低任务调度长度。清华大学的石威、郑纬民教授等对相关任务图的表调度算法进行了深入研究，分析了现有经典表调度算法中存在的不足。在此基础上，提出了一种均衡动态关键路径算法[27]0该算法综合考虑了关键路径节点和非关键路径节点的优先级，在调度过程中采用动态计算关键路径长度的方法，优先调度影响调度长度最大的任务，最终缩短了整个任务图的总调度长度。华中科技大学何琨、赵勇对分布式并行系统中有向无回路图的静态任务调度问题，以使调度长度最短为主要目标、减少资源数目为次要目标，提出了一种基于任务复制的分簇与调度算法——动态关键前驱算法DCP1]。DCPI法将任务复制、分簇与优先级列表方法结合起来，采用一种新的选择策略来定义待复制的重要祖先集。哈尔宾工程大学的李静梅、孙冬微、吴艳霞针对现有任务调度算法优先级选取过于单一所产生局部较优调度结果的问题，从全局较优出发，提出一种先分层后分支决定优先级的静态任务调度算法一HGCOTS算法[42]。该算法考虑了任务间较大的通信开销和冗余任务对异构CMP任务调度效率的影响，通过综合区间插入和任务复制技术最大限度地降低了任务间的通信开销，对冗余任务进行删除，明显提高了任务调度效率。湖南大学的徐雨明、李肯立通过结合传统启发式算法HEFT和遗传算法(GA),提出了一种多优先队列遗传算法(MPQGA)[43],克服了各自算法的缺点。在建立初始种群时，利用多个优先队列使得初始种群能够在解空间内均匀分布。通过精心设计交叉、编译、选择等操作，使算法跳出局部最优解。三、节能调度研究现状由于功耗对于嵌入式系统的重要性，嵌入式处理器发展的同时诞生了多种能耗优化技术。如ARM处理器所具有的不同工作模式、硬件性能监控器、动态电压调节、动态时钟控制等技术都跟节能相关。为了降低能耗，在嵌入式系统设计各个过程中，设计人员需要从在电路级、芯片级以及系统级对能耗进行优化。而能耗优化的层面越高，则节能效果越明显，因此许多学者开始对高层的任务调度问题进行研究。为解决嵌入式系统设计中的能耗问题，近年来兴起的动态功耗管理和动态电压缩放技术引起了业界的广泛关注。对于非实时应用来说，DPM技术能够有效实现节能，但由于DPM是将不使用的模块挂起以实现节能，而实时系统在运行过程中有许多不确定性，从而不能很好地发挥节能效果。因而，对于实时性有较高需求的应用多采用DVS技术，由于电压调节过程通常也会影响到处理器频率，所以也有人称之为动态电压/频率缩放(DynamicVoltage/FrequencyScaling,DVFS)技术，许多流行的低功耗处理器都支持该节能技术。如，IBM公司的PowerPC、Intel公司的Xscale以及Transmeta公司的Crusoe等。DVS技术通过实时改变处理器单元的电压和频率来降低系统功耗。然而系统频率降低导致任务执行时间变长，可能错过任务的截止期。因而，在电压缩放过程中，需要设计适当的调度算法，在不影响系统性能的情况下对能耗进行优化。DVS技术的本身是通过牺牲系统性能用来换取功耗的降低，本质上算作一种硬件节能技术，需要在软件层面上通过配置处理器的电压级别，使用在保证系统实时性的同时最大限度地实现功耗优化。通常情况下，处理器电压并不能联系变化，只具有几个离散的电压值。在具有离散电压级别的异构多处理器系统下对关联任务进行节能调度已被证明属于NP难问题，通常采用启发式算法进行求解［44］。现今，在异构多处理器系统上进行节能调度算法研究得到了国内外研究者的广泛关注。目前，针对多处理器系统的实时低功耗调度算法的研究越来越受到人们的重视。针对同构多处理器系统的节能问题，许多研究者对其展开了研究。在文献［45］中，作者提出了一种面向软实时任务的节能调度算法。该算法首先计算每个任务的松弛时间，然后采用全局DVS技术，在松弛时间内对片上多处理器的电压进行动态调节，从而在满足任务的截止期前提下降低内核计算速度，以实现系统节能的目的。文献［46］通过采用性能计数器获取多处理器的功耗参数，再根据这些参数来决定是执行还是挂起任务，使系统的功耗始终处于阈值范围内，也是一种实时任务节能调度方法。然而，这些算法都是针对软实时任务而设计，无法保证硬实时任务的完成时间，从而难以在硬实时系统上应用。文献［47］假定同构多处理器片上系统中各个核的运行电压相同，采用全局DVS技术和EDF算法对各个核的电压进行同时调节，给出了一种静态DVS启发式节能调度算法。但是该算法忽略了各处理器核之间的电压差异，从而难以取得最佳的节能效果。文献［48］对节能调度算法进行了总结分析，文中认为，对于多处理器系统，没有通用的节能算法可以针对各种情形，不同算法有其特定的适用范围和应用环境。在某些情况下能取得很好节能效果的算法，在其它情况下可能比不考虑节能的调度算法需要的能耗更大。对于异构多处理器系统来说，各个核之间的指令集不同，存在性能和结构上的差异性。异构多处理器系统的各个处理器核是异构的，所以需要先对任务进行划分，将任务分配到各个处理器核上，然后再对分配到各处理器核上的任务队列进行调度。在任务划分之后，任务的调度策略跟单处理器上存在一定的类似，可以借鉴对单处理器的一些研究成果进行多处理器进行任务调度，但任务之间的关联性使得多处理器上的任务调度难度大大增加。在异构多处理器系统环境下，利用DVS技术对具有依赖任务集进行节能调度是NP难问题，难以在多项式时间内求取最优解。文献［49］将电压缩放问题表述为一个整数规划问题，通过求解该问题实现处理器能耗最优。Leung等人在文献［50］中将节能调度中的任务划分、调度以及电压缩放问题抽象成一个混合的整数非线性规划问题(MixedIntegerNonlinearProgramming,MINLP)加以解决，首先给出一个目标函数，然后在各种限制条件下下求解目标函数的最小值，从而获得系统最低能耗。Luo等人提出了一种同时调度多速率周期任务及非周期任务的能量感知算法［51］0美国加州大学欧文分校的Gorjiara.B等人提出了一种快速启发式算法［52］;作者随后在文献［53］中结合随机算法及能量梯度技术来同时解决松弛时间片的分配及任务调度问题；其最新相关工作在文献［54］中给出，根据任务的能量梯度和执行时间计算优先级，然后在优先级指导下进行随机调度。Gruian等提出了一种基于优先级的列表调度算法［55］。YanhongLiu提出了一种基于关键路径分析的任务调度和压缩放策略［56］。英国南安普顿大学的Marcus.T等人持续在多处理器节能调度方面进行研究，其在文献［57］中将传统遗传算法和列表调度策略相结合，提出遗传列表调度算法来确定任务的执行顺序，结合作者在文献画中提出的动态电压缩放算法完成异构多处理顺环境下的节能调度。V.Kianzad等在文献［59］中提出了一种融合任务分配、调度和能量管理(CombinedAssignment,Scheduling,andPowERmanagementCASPER)的调度框架，CASPER调度框架采用遗传算法，将任务划分、调度和电压缩放三个步骤整合到一个单循环优化迭代当中。在文献［60］中，作者首先进行优先级初始分配，然后采用模拟退火算法对任务执行顺序进一步优化，最后基于任务时效性和能量的变化率，采用时间片分配算法对处理器进行动态电压缩放。文献［61］认为漏极功耗是异构多处理器系统中主要能耗来源，采用DVS技术和处理器休眠技术提出一系列针对软实时任务的启发式节能调度算法。但是算法没有考虑硬实时任务，具有一定局限性。参考文献:LiuC,LaylandJ.Schedulingalgorithmsformultiprogramminginahardreal-timeenvironment[J].JournaloftheACM,1973,20(1):46-61.SanjoyBaruah.Feasibilityanalysisofpreemptivereal-timesystemsuponheterogeneousmultiprocessorplatforms[C].In:Procofthe25thIEEEInternationalReal-TimeSystemsSymposium.Lisbon,Portugal:ComputerSocietyPress,2004,37-46.GiuseppeLipari,SanjoyKBaruah.EfficientschedulingofReal-TimeMulti-TaskApplicationsinDynamicsystems[C].In:Proceedingsofthe6thIEEERealTimeTechnologyandApplicationsSymposium,2000,166-175.HalukTopcuoglu,SalimHariri,Min-YouWu.Performance-EffectiveandLow-ComplexityTaskSchedulingforHeterogeneousComputing[J].IEEETransactionsonParallelandDistributedSystems,2002,13(3):260-274.SanjoyBaruah.Taskpartitioninguponheterogeneousmultiprocessorplatform[C].InProceedingsofthe10thIEEEReal-TimeandEmbeddedTechnologyandApplicationsSymposium,2004.SanjoyBaruah.Feasibilityanalysisofpreemptivereal-timesystemsuponheterogeneousmultiprocessorplatforms[C].InProceedingsofthe25thIEEEInternationalReal-TimeSystemsSymposium,Dec.2004:37-46.SanjoyBaruah,NathanFisher.ThePartitionedMultiprocessorSchedulingofDeadline-ConstrainedSporadicTaskSystems[J].IEEETransactionsonComputers,July2006,55(7):918-923.HalukTopcuoglu,SalimHariri,Min-YouWu.TaskSchedulingAlgorithmsforHeterogeneousProcessors[J].ProceedingsoftheHeterogeneousComputingWorkshop,HCW,1999:3-14P.TaoYang,APostolosGerasoulis.DSC:SchedulingParallelTasksonanUnboundedNumberofProeessors[J].IEEETransactionsonParallelandDistributedSystems,1994,5(9):951-967P.LuizF.Bittencourt,RizosSakellariou,EdmundoR.M.Madeira.DAGSchedulingUsingaLookaheadVariantoftheHeterogeneousEarliestFinishTimeAlgorithm[C].201018thEuromicroConfereneeonParallel,DistributedandNetworkbasedProeessing,2010:27-34.Y.KwokandI.Ahmad,BenchmarkingtheTaskGraphSchedulingAlgorithms[C],ProceedingsofInternationalParallelProcessingSymposium,Florida,U.S.A.April1998,pp.531-537.TracyD.Braunt,HowardJaySiegel,NoahBeck,LadislauL.Boloni,MuthucumaruMaheswarans.AComparisonStudyofElevenStaticHeuristicsforMappingaClassofIndependentTasksontoHeterogeneousDistributedComputingSystems[J].PurdueUniversitySchoolofElectricalandComputerEngineeringTechnicalReport.2000:TR-ECE00-4.ChiXing,XudongChai,QiWang,YangChen,LiTan.SimulationJobSchedulingonClusterswithHeterogeneousSchedulingSystems[J].AsiaSim2013.2013,pp403-408.JinghuiZhang,JunzhouLuo,FangDong.SchedulingParallelTaskGraphsonnon-dedicatedheterogeneousmulticlusterplatformwithMoldableTaskDuplication[C].ComputerSupportedCooperativeWorkinDesign(CSCWD),2013IEEE17thInternationalConferenceon.June2013,313-318.Humphrey,John,Spagnoli,Kyle.SchedulingOperationsforMassiveHeterogeneousClusters[J].NASATechBriefs,July2013:33-34.DavidKoufaty,DheerajReddy,ScottHahn,Biasschedulinginheterogeneousmulti-corearchitectures[C].EuroSys'10Proceedingsofthe5thEuropeanconferenceonComputersystemstableofcontents.2010:125-138.Starke,R.A,deOliveira,R.S.AHeterogeneousPreemptiveandNon-preemptiveSchedulingApproachforReal-TimeSystemsonMultiprocessors[C].CriticalEmbeddedSystems(CBSEC),2012SecondBrazilianConferenceon.20-25May2012:70-75.LiWang,JingLiu,JingtongHu,QingfengZhuge,DuoLiu,EdwinH.-M.Sha.EfficientTaskAssignmentonHeterogeneousMulticoreSystemsConsideringCommunicationOverhead[C].12thInternationalConference,ICA3PP2012,Fukuoka,Japan,September4-7,2012,Proceedings,PartI.LinaSawalha,RonaldD.Barnes.Phase-basedschedulingandthreadmigrationforheterogeneousmulticoreprocessors[C].PACT'12Proceedingsofthe21stinternationalconferenceonParallelarchitecturesandcompilationtechniques.2012:493-494.AhmadI,KwokYK.Onexploitingtaskduplicationinparallelprogramscheduling[J].IEEETrans.ParallelandDistributedSystems,1998,9(9):872-892.BansalS,KumarP,SinghK.Dealingwithheterogeneitythroughlimitedduplicationforschedulingprecedenceconstrainedtaskgraphs[J].ParallelandDistributedComputing,2005,65(6):479-491.ShinK,ChaM,JangM,etal.Taskschedulingalgorithmusingminimizedduplicationsinhomogeneoussystems[J].ParallelandDistributedComputing,2008,68(8):1146-1156.TarekF,Abdelzaher,KangGShin.Period-BasedpartitioningandassignmentforlargeReal-TimeApplications[J].IEEETransactionsonComputers,Jan.2000,49(1):81-87.DutotP.Complexityofmaster-slavetaskingonheterogeneoustrees[J].EuropeanJournalonOperationalResearch,2005,164(3):690-695.[25]郑凯.对数据在异构多核处理器模拟器中进行任务划分的研究[D].上海交通大学硕士学位论文.2008:1-12[26]吴佳骏多核多线程处理器上任务调度技术研究[D].中国科学院计算技术研究所博士学位论文.2006:4-17[27]石威,郑纬民.相关任务图的均衡动态关键路径调度算法[J].计算机学报.2001,24(9):l-8[28]钟求喜,谢涛，陈火旺.基于遗传算法的任务分配与调度[J].计算机研究与发展.2000,37(10):1198-1203[29]李庆华，韩建军,AbbasA.Essa同构计算环境中一种快速有效的静态任务调度算法[J].计算机研究与发展.2005,42(1):118-125[30]刘轶，张听，李鹤，钱德沛一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展.2009,46(6):1058-1064[31]何琨，赵勇，黄文奇.基于任务复制的分簇与调度算法[J].计算机学报.2008,31(5):734-739[32]王永炎，王强，王宏安，金宏，戴国忠.基于优先级表的实时调度算法及其实现[J].软件学报.2004,15(3):361-369[33]梁洪涛，袁由光，方明一种基于任务全局迁移的静态调度算法[J].计算机研究与发展.2006,43(5):797-804[34]刘振英，方滨兴，姜誉，张毅，赵宏.一个调度Fork-Join任务图的新算法[J].软件学报，2002,13(4):693-697[35]章军,冯秀山，韩冀中，韩承德.总线互连机群系统上的静态任务调度[J].计算机研究与发展.1999,36(7):805-812[36]邱卫东，陈燕，李洁萍，彭澄廉.一种实时异构嵌入式系统的任务调度算法[J].软件学报Vol.15,No.4,2004[37]李仁发，刘彦，徐成.多处理器片上系统任务调度研究进展评述[J].计算机研究与发展.2008,45(9):1620-1629.[38]江维,常政威，桑楠等.安全和能量关键的分布式协作任务调度[J].电子学报，2011,39(4):757-762.[39]肖鹏，胡志刚.截止时间约束下独立网格任务的协同调度模型[J].电子学报，2011,39(8):1852-1857.[40]刘卫宁，高龙.异构云中面向集群负载均衡的任务调度策略[J].计算机应用，2013,33(8).[41]童小念，舒万能，李子茂.异构多处理机系统的负载均衡与任务调度[J].光学精密工程.2007,15(12).[42]李静梅，孙冬微，吴艳霞.一种全局较优的静态任务调度算法[J].计算机应用研究.2014,31(4):1027-1030.YumingXu,KenliLi,JingtongHu,KeqinLi.Ageneticalgorithmfortaskschedulingonheterogeneouscomputingsystemsusingmultiplepriorityqueues[J].InformationSciences,2014,Volume270(20):255-287.ANDREIA,SCHMITZM,ELESP,etal.Overhead-consciousvoltageselectionfordynamicandleakageenergyreductionoftime-constrainedsystems[C].InProc.Design,AutomationandTestinEuropeConferenceandExposition,2005:518-523.BautistaD,SahuquilloJ,HassanH,etal.ASimplePower-AwareSchedulingforMulticoreSystemsWhenRunningReal-TimeApplieations[C].InProceedingsofthe22ndIEEE/ACMInt'1ParallelandDistributedProcessingSymp,2708:1SinghK,BhadauriaM,McKeeSA.RealTimePowerEstimationandThreadSchedulingviaPerformanceCounters[J].ACMSIGARCHComputerArchitectureNews,2009,37(2):46-55.HuangXin,LiKenLi,LiRenFa.AEnergyEfficientSchedulingBaseonDynamicVoltageandFrequencyScalingforMulti-CoreEmbeddedReal-TimeSystem[C].InProceedingsofICA3PP'09,20094537RotemE,MendelsonA,GinosarR,etal.MultipleClockandVoltageDomainsforChipMultiProcessors[C].InProceedingsofACMMICRO'0942009:459ZhangY,HuX,ChenDZ.TaskSchedulingandVoltageSelectionforEnergyMinimization[C].InProceedingsofthe39thDesignAutomationConference,June2002:183-188.LeungLF,TsuiCY,KiWH.MinimizingEnergyConsumptionofMultipleProcessors-CoreSystemswithSimultaneousTaskAllocation,SchedulingandVoltageAssignment[C].InProceedingsofAsiaandSouthPacificDesignAutomationConf.,Jan.2004:647-652.LuoJ,JhaNK.Power-ConsciousJointSchedulingofPeriodicTaskGraphsandAperiodicTasksinDistributedReal-timeEmbeddedSystems[C].InProceedingsofInt'lConf.CompuAdedDesign,Nov.2000:357-364.GorjiaraB,ChouP,BagherzadehN,etal.Fastandefficientvoltageschedulingbyevolutionaryslackdistribution[