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