基于復制與動態(tài)優(yōu)先級網(wǎng)格任務調度算法研究.pdf

1、大連理工大學碩士學位論文基于復制與動態(tài)優(yōu)先級網(wǎng)格任務調度算法研究姓名：劉偉偉申請學位級別：碩士專業(yè)：計算機應用技術指導教師：孟憲福20091216基于復制與動態(tài)優(yōu)先級網(wǎng)格任務調度算法研究DuplicationandDynamic—PriorityBasedSchedulingAlgorithminGridComputingSystemsAbstractWiththeflouringofgridinrecentyearsadistribu

2、tedsuitofcomputingmachineswitlldiversecapabilitiesconnectbydiversehighspeedlinksutilizedtoexecuteparallelprogramsHowever，theperformanceoftheparallelprogramexecutioningddishighlydependentontheschedulingoftheparallelprogra

3、mtasksontothesemachinesIngridenvironment，thecommunicationdelayisakeyindegradingtheperformanceoftheparallelprogramexecutionButlist—basedschedulingalgorithmsfailtoconsiderthecommunicationcostandachildnodecall’tstartuntilit

4、simmediateparentscompleteandsendthemessagethechildtaskneed1eavingmanyidietimeslotsinaprocessorInordertodealwiththisproblem，agenericschedulingstrategy，STDH(SelectedTaskDuplicationforHeterogeneoussystem)，ispresented，whichi

5、mprovestheperformanceoflistbasedalgorithm誠ththeduplicationIfthereisaperiodofidletimeontheprocessor，STDHattemptstoinsertallsuitableimmediateparentnodesofthecurrentselectednode，notonlythecriticalparent，SOastoreduceitswaiti

6、ngtimeontheprocessor，whichishelpfultoadvancingtheearlieststartingtimeofthiscandidatetaskOntheonehandtheearlieststartingtimeofsometaskscouldminimizetheoveralltimeofthescheduling，andontheotherhand，theutilizationoftheproces

7、sorscouldberaisedTheexperimentalresultsshowthatSTDHoutperformsHEFTandHNDPintermsoffinishtimeBesideswhiletheratiooftotalcommunicationcostandtotalcomputationcostofthetaskgraphbecomeslarger，STDHbecomesbetterthanthetwoothers

8、Takingintoaccountthesystemheterogeneity，thesametasktakedifferentruntimeondifferentprocessors，thepriorityofonetaskmaydynamicallychangeintheschedulingprocessduetothattheprocessortoassignthetasknodeisnotdeterminedSoscheduli

9、ngsequencedeterminestaticallyinthelistingphaseiSnotreasonablebecauseofthesequencecannotchangeintheschedulingprocess，theprioritycomputedinlistingphasemaybedifferentfromtherealpriorityInordertodealwiththisproblemthepriorit

10、ywasdetermineddynamicallyintheschedulingprocess，inthisway，thenodeswhichhadthegreatestinfluencetotheschedulinglengthofthetaskgraphwouldbeselectedtoschedulefirstInaddition，iftherewereidietimeslotsintheprocessorsthepredeces