DOC

Optimal

By Rodney Lawson,2014-07-24 00:52
10 views 0
OptimalOptima

    Optimal

2O卷第4期重庆邮电大学学报(自然科学版)Vo1.2ONo.4

    ;20088

    JournalofChongqingUniversityofPostsandTelecommunications(NaturalScienceEdition

    )Aug.2008

    ;Optimalalgorithmsforschedulinglarge

    ;ll??l

    ;scaleapplicationonheterogeneoussystems ;WANGQingxian

    ;(SchoolofComputerScienceandEngineering,UniversityofElectronicScienceandTechn

    ologyofChina,Chengdu610054,P.R.China)

    ;Abstract:ThispaperstudiesoptimalalgorithmsforschedulinglargescaleapplicationonheterogeneoussystemsusingDivis

    ;ibleLoadTheoU.A.1orerealisticandgeneralmodel,i.e.,bothprocessorsandcommunicati

    onlinksmayhavedifferent

    ;speedsandarbitraUstartupcosts,andcommunicationisinnonblocking.1ode,isintroduced.Undersuchenvironment,

    ;thefollowingresultsareobtained:Mathematicmodelandclosedformexpressionsbothfortheprocessingtimeandthe

    ;fractionofloadforeachprocessorarederived;?

    theinfluenceofstartupcostsontheoptimalprocessingtimeisanalyzed; ;?

    foragivenheterogeneoussystemsandalargescalecomputingproblem,optimalalgorithmsareproposed.

    ;Keywords:heterogeneouscomputing;divisibleloadtheory;nonblockingmodeofcommunication;startupcosts;schedu

    ;lingalgorithm.

    ;CLCnumber:TP301.6Documentcode:AArticalID:1673-825X(2008)04-0440-07

    ;1Introduction

    ;Interestinsolvinglargescalecomputationintensive

    ;problemsinanetworkbaseddistributedcomputingen

    ;vironmenthasreceivedmuchmoreattentionrecently. ;Thisincludestheuseofclustersofworkstations,net

    ;worksofworkstationsoragridcomputingenvironment. ;Amajorproblemofsuchapplicationsistofindanopti

    ;malalgorithmforschedulingworkloadsothatthepro

    ;cessingtimeisminimized[1].

    ;Amaincharacterofsuchplatformisheterogeneity. ;However,theproblemofoptimalschedulingoftasks ;onheterogeneoussystem,inthemostgeneralcase,has

;beenproventobeNPhardandanoptimalsolutioncan

    ;befoundonlyafteranexhaustivesearch[1].Inshaqa ;contrastwithgeneraltaskscheduling,undersomecon

    ;ditions,optimalalgorithmsandclosedformformulas

    ;existforschedulingdivisibleload.

    ;2Themodelandrelatedwork

    ;InthisSection,themathematicmodel,alltheter

    ;Receiveddate:2008-0401

    ;Foundationitem:ThisresearchwassupportedbytheNational ;NaturalScienceFoundationofChinaunderGrant(10467007) ;Foundationof”863”(2006AAO1Z414)

    ;minology,definitions,andnotationsthatareused ;throughoutthepaper.Somerelatedworksarealso ;presented.

    ;2.1Problemstated

    ;Inthispaper,wewillstudythefollowingproblem: ;givenalarge?-scaleapplicationandacomputingplat?- ;formofnetworkconnectedprocessors,ourobjectiveis ;tofindataskschedulingalgorithmtodividethework

    ;loadoftheapplicationintoseveralsubtasksandthen

    taskstoexecuteoneachprocessor ;schedulethesesub

    ;inparallel,suchthatthemankspan,i.e.,thecom

    ;pletiontimeoftheapplication,isminimum. ;Letlbetheworkload,andn,thenumberofa

    ;vailableprocessors,assumeo/denotesthefractionof ;theloadwillbeassignedtoprocessorP,Tibethe ;completedtimeofP,andTbethemakespan,then ;theaboveproblemcanbeformattedas

    ;T=min{max

    ;…l2..{Ti)(1)

    ;suchthat

    ;?d=vt_jl’d>0,1?i?n(2)

    ;2.2Themodel

    ;Theprobleminthispaperismodelasdivisibleload. ;Thetargetplatformisaheterogeneoussystem.Thehet

    ;

    ;4

    WANGQing—xian.Optimalalgorithmsforscheduli”glal”gescaleapplicationonheterogeneoussystems?441?

    ;erogeneousnetworksweconsideredareofdifferent ;computingspeedsandcommunicationspeeds. ;2.3Relatedwork

    ;Duetoitssimpleyetrealisticandanalyticaltracta

    ;bility,thedivisibleloadtheoryhasbeenwidelystudied

    ;inthelastseveralyears.Alistofpapersinthisareais ;availableat[2].Compilationofalltheresearchcon

    ;tributionsinDLTuntil1996canbefoundinamono

    ;graphs[3]writtenbyBharadwaj,GhoseandRober

    ;tazzi,andarecentreportsummarizesallthepublished ;contributionstilldateinthisdomain[1,4].Aunified ;theoreticalperspectivethatsynthesizespreviouslypub

    ;lishedresults,severalnovelresults,andopenques

    ;tionsarepresentedin[5].Therefore,weshallnow ;presentaverybriefsurveyonsomeofsignificantcon

    ;tributionsinthisarearelevanttotheproblemaddressed ;inthispaper.

    ;Inalltheresearchsofarinthisdomain.aprinciple ;thatisusedtoderiveoptimalsolutionisasfollows:in ;ordertoobtainanoptimalprocessingtime,

    ;itisneces

    ;saryandsufficientthatalltheprocessorsparticipating ;inthecomputationmuststopcomputingatthesame ;timeinstantly.Althoughtheoptimalityprinciplere

    ;mainsvalidforevenanarbitrarynetworktopology, ;the

    ;optimaltimeperformancedependscruciallyonthese

    ;lectionofapropersubsetoftheavailableprocessors. ;Thus,usingalargersetofnodesmayyieldaninferior ;performancecomparedtoanoptimalsubsetofnodesa

    ;mongwhichtheloadisdistributedaccordingtothe0p

    ;timalityprinciple[3,5].

    ;ThereisawideacceptanceinDLTresearchona

    ;doptingalinearcostmodeloftheprocessorspeedand ;communicationlinkspeedparameters[1,3,4,6].In ;thismodel,thecommunicationtimedelayisassumed ;tobeproportionaltotheamountofloadthatistrans

    ;ferredoverthechannel,andthecomputationtimeis ;proportionaltotheamountofloadassignedtothepro

    ;cessor.

    ;Inthecaseofos=0andgg,whichrepresent

    ;ahomogeneousbusorientedplatformwithoutstartup ;overheadbothforcomputationandcommunication, ;[3]presentsananalyticproofforabusnetworkthat ;foraminimaltimesolutionallprocessorsmuststop ;computingatthesametime.Withthisprinciple,opti

    ;malsolution,togetherwithclosedformexpressionsfor

    ;themakespanTCanbederived.BecauseTdoesnot ;dependonthedistributesequencing,sotheresultinis

;optima1.

    ;Inthecaseofof=s=0anddifferentg,whichre

    ;presentaheterogeneoussingle--leveltreenetworkwith-- ;outstart--upoverheadbothforcomputationandcommu.. ;nicationcosts,theclosedformcanbeobtainedbothfor

    ;andthemakespanT.ButTstronglydependsonthe ;distributionsequencing,andtheprimaryoptimalprin

    ;ciplethatallprocessorsfinishprocessatthesametime ;isnolongervalid[5,7].Beaumontetc.provedthat ;theoptimalorderinthiscaseshouldbefollowedby ;nondecreaseofg[5].

    ;Formostplatforms,thezerostartuptimebecomes

    ;quiteunrealistic[5,7].Inthecaseofs=s,o=o, ;andgg,theinfluenceofoverheadsontheoptimal ;processingtime,andtheeffectofchangingtheload ;distributionsequenceonthetimeperformanceareana

    ;lyzedin[7-9].Anecessaryandsufficientcondition ;fortheexistenceoftheoptimalprocessingtimeisalso ;given,thattheoptimalsequencingshouldbefollowed ;bynondecreaseofto.Beaumontetc.[5]alsoproved ;thatforthecaseofs=0,differentoandg=g,opti

    ;malsequencingshouldbefollowedbynondecreaseof

    ;g×.

    ;Inthecaseofarbitrarilyo,arbitrarilyg., ;arbitrarily

    ;s,andarbitrarily?,schedulingdivisibleworkloadon

    ;starandtreenetworktopologies,bothlinearandaffined ;costmodelsforcommunicationandcomputationare ;studiedin[5].Theresultshowsthatforenoughwork

    ;load,theoptimalsequenceshouldbefollowedbynon

    ;decreaseofg.

    ;Allstudiesaboveareconsideredonlythe”blocking

    ;modeofcommunication”,i.e.,theprocessorscan

    ;startcomputingprocessonlyafteralltheloadfractions ;havebeenreceivedcompletely.Forsomeapplications, ;“blockingmodeofcommunication”isn’tsuitable.In

    ;veryrecently,communicationin”non—blockingmode

    ;ofcommunication”,i.e.oncereceivedafractions0f

    ;itsshare,processorPcanstartcomputingprocess, ;withoutwaitingforalltheloadfractionshavebeenre

    ;

    ;?

    ;442?重庆邮电大学学报(自然科学版)20

    ;ceivedcompletely,hasbeenstudied[6].nonbloc

;kingmodewasfirstintroducedinhomogeneoustree

    ;networkandlinearnetwork,andin[6]someresults ;includesclosedformexpressionfortheprocessingtime ;andoptimalsequenceofschedulinginheterogeneous ;systemwerederived.In[6],areconsideredwithno ;startupoverheads.

    ;Ithasbeenwidelyacceptedthatstartupcostsplays

    ;somesignificantinfluenceonscheduling[5,7-9].In ;thispaper,weaddstartupcosts,bothforcomputation ;andc0mmunication.Themodelsweconsideredaredif- ;ferentfromtheearlyblockingmode1.Comparedwith ;somefewnonblockingmodel,whichonlyfocuseson ;eitherhomogeneoussystemorwithoutstartupcosts,

    ;ourresultsaremoregeneral,theresultsinprevious ;studiesareonlyspecialcase.

    ;3Optimalprinciples

    ;Ithasbeenprovedthatifthereisnostartupcost

     ;bothofcommunicationandcomputing,optimalalgo

    ;rithmsforDLTsatisfiedthefollowingproperties:?All

    ;processorsareinvolvedincomputing;?Allprocessor

    ;completeitstaskatthesametimeinstance:?The

    ;schedulingsequencedoesnotaffectthemakespan; ;Thereisnotimeintervalforthemasterprocessorbe

    ;tweenanytwocommunication;and?Processorstart

    ;computingatonceuponitsworkloadbeingreceived. ;Theaboveresultsareobvious,andtheycanbe ;Dr0vedviareductiontoabsurdity.Basedonthesere

    ;suhs,alinearprogrammingcanbeobtained.Because ;thatisareallinearprogramming,itcanbesolvedin ;polynomialtime.

    ;Itisnecessarytonotethat,withnonzerostartupo

    ;verheads.thereisnoneedtoinvolveallprocessorsin ;computationintheblockingmodeofcommunication ;[10,11].Inthenonblockingmodeofcommunica.

    ;tion,itisalsoeasytoprovethefollowingtheory. ;Theorem1Innon.blockingmodeofcommunica

    ;tion,optimalschedulingforDLTsatisfiedthefollowing ;conditions:

    ;1)Thereisnotimeintervalforthemasterprocessor