并行分布计算中的调度问题研究

《并行分布计算中的调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学博士学位论文并行分布计算中的调度问题研究姓名：孙广中申请学位级别：博士专业：计算机软件与理论指导教师：陈国良;顾钧20050301中国科学技术大学博士学位论文(4)类似于sETI@home的大规模P2P计算系统中的调度策略研究：提出了相应的理论模型来描述其中的任务调度问题。在此基础上，评估现有的几种不同的调度策略，设计了新的根据具体的网络环境和计算资源进行选择的调度策略，通过理论分析和实验分析说明该策略较之现有策略有更好的性能，并将该调度策略应用于实际系统中。本文的主要贡献和创新有：(1)提出了具有中断时间代价的～致

2、并行机调度问题，给出了近似比为常数的近似算法，证明了问题求解难度和近似难度；(2)研究了多台机器条件下具有不可用时段的调度问题，分析了经典在线算法的性能并证明了问题的近似难度；(3)针对线性网络和环状网络，研究了分布式计算环境下的任务调度模型，证明了问题的难解性，给出了近似性能良好的调度算法；(4)研究了对等计算环境下任务调度问题，给出了相应的调度模型，针对已有策略的不足设计了新的策略。关键词：调度问题，并行计算，分布式计算，近似算法，F界中国科学技术大学博上学位论文AbstractSchedulingproblemsareonek

3、indofbasicproblemsincombinationoptimization．Theyarec。ncernedwiththeoptimala110cationofscarceresourcestoactivitiesovertime．Moregenerally，schedulingproblemsinv01vejobsthatf【

4、ustbescheduledonmachinessubjecttocertainconstraintstooptimizesomeobjectivefunction．Fordifferenceo

5、fmachineenvironrnent，sideconstraintsandcharacteristics，optimalityobjects，schedulingproblemscontainthousandsofdifferentschedulingmodels．Manyresearchersindifferentfields，suchasappliedmathernatics，computerscience，managescience：haveachieVedlotsofimportantresultsonschedulin

6、gproblemsinboththeoryandapplication．Inparallelanddistributedcomputing，thereareamassofschedulingproblems．SolVingtheseschedulingproblemshasastrongimpactontheparallelanddistributedcomputingsystems．Toimprovetheperformanceoftheparallelanddistributedsystemseffectively，resear

7、chonthealgorithmsofthoseschedulingproblemsarevaluableintheoryandpractice．Inthispaper，someschedulingproblemsinparallelanddistributedcomputingarestudiedasf0110ws．(1)Apreemptiveschedulingproblemispresented，inwhichanadditionaltimecostisneededifajobisinterruptedonce．Thispap

8、ersh。wsthatproblemisaNP—hardproblem，presentsanoff—lineapproximationalgorithmwithtimecomplexityofO(nlogn+m)andaperformancerationomorethan1．40825．Theon一1inepropertyisalsostudiedandanon一1inealgorithmwithlinearitytimecomplexitYandacompetitiveratioof2isproposed．(2)Weconside

9、rstheon—lineschedulingonidenticalmachineswithmachlneavailabilityconstraintsandanalyzeoftheperformanceoftheLSalgorithm