异构多核系统中面向细粒度任务集的调度算法研究

《异构多核系统中面向细粒度任务集的调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、异构多核系统中面向细粒度任务集的调度算法研究摘要随着异构多核处理器的快速发展，异构多核系统中的任务调度成为研究热点。目前，适用于普通任务集调度的算法在调度细粒度任务集时，存在处理器负载失衡，处理器空闲时间多，并行性差和冗余任务等诸多缺陷，严重影响了多核系统的性能。本文针对这些问题展开研究。结合聚簇、列表和复制算法各自的优势，本文提出了一种高效的适合细粒度任务集的调度算法HCDUL，HCDUL分为聚簇、优先级计算和就绪任务列表建立、任务调度、复制上层节点四个阶段。通过聚簇降低了通信开销，调度过程中动态更新就绪列表，并实时对其排序，关键任务有最高的优先级；每次取列表头节点，并调度到完成时间最

2、小的处理器核上；利用当前节点之前的空闲时间段复制上层节点，进一步减小通信开销，提前子任务的开始时间，从而缩短整个任务集的完成时间。针对复制算法存在冗余任务问题，本文提出了一种优化算法HDO。首先，查找并删除冗余任务，然后计算冗余任务后继节点的开始时间，最后调整后继节点。通过消除冗余任务，提前了后续节点开始时间，节省了处理器资源，并进一步缩短了调度长度。本文使用随机生成图进行了大量实验，在调度细粒度任务集时，与HEFT和HCNF算法比较，HCDUL算法的调度长度率SLR更小，加速比Speedup更大。同样，使用大量的随机生成图对HDO算法验证，HCNF和HCDUL算法的调度结果经HDO算法

3、优化之后，总执行时间比率SETR更小，并且在一定程度上，调度长度率SLR减小，加速比Speedup增加。关键词：异构多核系统：细粒度任务集；冗余任务；优化算法；随机生成图Ⅱ￡AbstractAsthedevelopmentofheterogeneousmulti·coreprocessor，thetaskschedullng0nheterogeneousmulit．coresystemhasbecomeahotspot·WhenSC：hedulingfinegranularitvtasksets，TheschedulingalgorithmsadjustingtOnormaltaskse

4、t’shaVemnvdefectssuchasunbalancedload，toomuchidletime，lowparallelismandredundanttaskscot．Alloftheproblemsinfecttheperformanceofmultl·coresystem·Theresearchofthispaperistosolvetheseproblems·Firstly，thispaperproposedanewalgorithmcalledHCDULtoSChedulefinegranularitvtasksets．HCDULhasfourphases：cluste

5、rphase，prioritycalculatlon蛐dreadvnodeslistbuildingphase，taskschedulingphaseanduppeflevernodesduplicationphase．Throughclusterphase，theexpensesofcommunicatlonbecomeIower．Inthcprocessofscheduling，HCDULupdatereadynodeslistdynamicallyandresortthelistinrealtime．Whensortingthelist，theCPnodeshavethehlghe

6、stpriority．Throughduplicatingtheupperlevelnodes，theexpensesofcommunlcatlonbecome10wcrfurther．Andthusmakethechildnodes’earlieststarttimesmaller·Andthuscometoabridgetheendtimeofthewholetaskset·Inordertosolvetheproblemofredundanttasks，weproposeanotheralgorithmcalledHDOinthispaper．Firstly，HDOlooksfor

7、redundanttasksanddeletethem·Secondly，HDOcalculatetheearlieststarttimeofredundanttasks’childnodes，andfinaIIy，HDOrevisethenodes．Througheliminatingredundanttasks，thelastmgnodes’earlieststarttimesareahead．Eliminatingredund