Seite - 181 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 76 It supports low overhead DMA transfers between internal memory, external memory, memory-mappedperipherals, linkports,hostprocessors,andotherDSPs,providinghighperformance for I/Oalgorithms. Flexible instructionsetsandhigh-level language-friendlyDSPsupport theeaseof implementation ofdigital signalprocessingwith lowcommunicationsoverheadinscalablemultiprocessingsystems. Withsoftware that isprogrammable formaximumflexibilityandsupportedbyeasy-to-use, low-cost development tools,DSPsenabledesigners tobuild innovative featureswithhighefficiency. TheDSPcombinesverywidememorywidthswith execution sixfloating-point and2464-bit fixed-pointoperations fordigital signalprocessing. Itmaintainsasystem-on-chipscalablecomputing design, including24Mbitofon-chipDRAM,six4Kwordcaches, integratedI/Operipherals, ahost processor interface, DMAcontrollers, LVDS link ports, and shared bus connectivity forGlueless Multiprocessingwithoutspecialbridgesandchipsets. It typicallyusestwomethodstocommunicatebetweenprocessornodes. Thefirstoneisdedicated point-to-pointcommunicationthroughlinkports.Othermethodusesasinglesharedglobalmemory tocommunicate throughaparallelbus. For full performanceof sucha combinedarchitecture, sophisticated resourcemanagement is necessary. Specifically,multiple instructionsmustbedispatchedtoprocessingunits simultaneously, andfunctionalparallelismmustbecalculatedbeforeruntime. In thispaper,wedescribeanapproach for scheduling imageprocessingworkflowsusing the networksofaDSP-cluster (Figure1). Figure1.Digital signalprocessor (DSP)cluster. 2.Model 2.1. BasicDefinitions Weaddressanoffline (deterministic)non-preemptive, clairvoyantworkflowschedulingproblem onaparallel clusterofDSPs. DSP-clustersconsistofm integratedmodules (IM) IM1, IM2, . . . , IMm. Letkibethesizeof IMi (numberofDSP-processors). Letnworkflowjobs J1, J2, . . . , Jnbescheduledonthecluster. A workflow is a composition of tasks subject to precedence constraints. Workflows are modeled as a Directed Acyclic Graph (DAG) Gj = ( Vj,Ej ) , where Vj is the set of tasks, and Ej= { (i,k) ∣∣ i,k∈Vj, i = k},withnocycles. Eacharc (i,k) isassociatedwithacommunicationtimedi,k representingthecommunicationdelay, if iandkareexecutedondifferentprocessors. Task imustbecompleted,anddatamustbe transmitted duringdi,kprior towhenexecutionof taskk is initiated. If iandkareexecutedonthesameprocessor, nodata transmissionbetweenthemisneeded;hence, communicationdelay isnotconsidered. Eachworkflow task i is a sequential application (thread) anddescribed by the tuple ( r′i,p ′ i ) , withreleasedate r′i, andexecutiontime p ′ i. 181