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

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

2、tedsuitofcomputingmachineswitlldiversecapabilitiesconnectbydiversehighspeedlinksutilizedtoexecuteparallelprogramsHowever，theperformanceoftheparallelprogramexecutioningddishighlydependentontheschedulingoftheparallelprogra

3、mtasksontothesemachinesIngridenvironment，thecommunicationdelayisakeyindegradingtheperformanceoftheparallelprogramexecutionButlist—basedschedulingalgorithmsfailtoconsiderthecommunicationcostandachildnodecall’tstartuntilit

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

5、mprovestheperformanceoflistbasedalgorithm誠(chéng)ththeduplicationIfthereisaperiodofidletimeontheprocessor，STDHattemptstoinsertallsuitableimmediateparentnodesofthecurrentselectednode，notonlythecriticalparent，SOastoreduceitswaiti

6、ngtimeontheprocessor，whichishelpfultoadvancingtheearlieststartingtimeofthiscandidatetaskOntheonehandtheearlieststartingtimeofsometaskscouldminimizetheoveralltimeofthescheduling，andontheotherhand，theutilizationoftheproces

7、sorscouldberaisedTheexperimentalresultsshowthatSTDHoutperformsHEFTandHNDPintermsoffinishtimeBesideswhiletheratiooftotalcommunicationcostandtotalcomputationcostofthetaskgraphbecomeslarger，STDHbecomesbetterthanthetwoothers

8、Takingintoaccountthesystemheterogeneity，thesametasktakedifferentruntimeondifferentprocessors，thepriorityofonetaskmaydynamicallychangeintheschedulingprocessduetothattheprocessortoassignthetasknodeisnotdeterminedSoscheduli

9、ngsequencedeterminestaticallyinthelistingphaseiSnotreasonablebecauseofthesequencecannotchangeintheschedulingprocess，theprioritycomputedinlistingphasemaybedifferentfromtherealpriorityInordertodealwiththisproblemthepriorit

10、ywasdetermineddynamicallyintheschedulingprocess，inthisway，thenodeswhichhadthegreatestinfluencetotheschedulinglengthofthetaskgraphwouldbeselectedtoschedulefirstInaddition，iftherewereidietimeslotsintheprocessorsthepredeces