En heterogen datormiljö är en serie heterogena processorer som är sammankopplade med höghastighetsnät, vilket ger löfte om snabb bearbetning av beräkningsintensiva tillämpningar med olika datorbehov. Schemaläggning av en applikation modellerad av Directed Acyklic Graph (DAG) är en nyckelfråga när man siktar på hög prestanda i denna typ av miljö. Problemet tas i allmänhet upp i termer av uppgift schemaläggning, där uppgifter är de schemaläggs enheter i ett program. Problemen med schemaläggningen har visat sig vara NP-kompletterade i allmänhet samt flera begränsade fall. I denna studie presenterar vi en enkel schemaläggningsalgoritm baserad på lista schemaläggning, nämligen, låg komplexitet Prestanda Effektiv Task Scheduling (PETS) algoritm för heterogena datorsystem med komplexitet O (e) (p+ log v), som ger effektiva resultat för applikationer som representeras av DAGs. Analysen och experimenten baserade på både slumpmässigt genererade grafer och grafer av några verkliga applikationer visar att PETS algoritmen väsentligt överträffar de befintliga schemaläggningsalgoritmer som heterogeneous Earliest Finish Time (HEFT), Critical-Path-On a Processor (CPOP) och Levelized Min Time (LMT), i termer av schema längd ratio, speed up, effektivitet, körtid och frekvens av bästa resultat. Nyckelord: DAG, uppgiftsgraf, schemaläggning av uppgifter, heterogena datorsystem, schemalängd, hastighetsförbättring, effektivitet En växande betoning på samtidig bearbetning av jobb har lett till en ökad acceptans av heterogena datormiljöer och tillgängligheten av ett nätverk av processorer gör ett kostnadseffektivt utnyttjande av underliggande parallellism för tillämpningar som vädermodellering, bildbehandling, realtid och distribuerade databassystem. En välkänd strategi bakom ett effektivt genomförande av en enorm applikation på en heterogen datormiljö är att dela upp den i flera oberoende uppgifter och schemalägga sådana uppgifter över en uppsättning tillgängliga processorer. En uppgiftsdelningsalgoritm tar hand om att effektivt dela upp en applikation i uppgifter av lämplig kornstorlek och en abstrakt modell av en sådan partitionerad applikation kan representeras av en riktad Acyklisk Graph (DAG). Varje uppgift hos en DAG motsvarar en sekvens av operationer och en riktad kant representerar företrädesbegränsningarna mellan uppgifterna. Varje uppgift kan utföras på en processor och den riktade kanten visar överföring av relevanta data från en processor till en annan. Schemaläggning av uppgifter kan utföras vid kompileringstid eller vid körtid. När egenskaperna hos en ansökan, som omfattar utförandetider för uppgifter på olika processorer, datastorleken på kommunikationen mellan uppgifter och beroenden uppgift, är kända a priori, representeras den med en statisk modell. Syftet med uppgiften schemaläggning är att kartlägga uppgifterna på processorer och beställa deras utförande så att kraven uppgift företräde är uppfyllda och en minsta övergripande slutförande tid erhålls. Problemet med schemaläggning av uppgifter med erforderligt företrädesförhållande, i det mest allmänna fallet, har visat sig vara NP-fullständigt [1, 2] för vilket optimala lösningar kan hittas först efter en uttömmande sökning. Effektiv programplanering är avgörande för att uppnå hög prestanda i heterogena datorsystem. På grund av dess avgörande betydelse för prestationen har problemet med schemaläggningen i allmänhet studerats ingående och olika heuristiker har föreslagits i litteraturen [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [14] [15] [16] [17]. Dessa heuristik klassificeras i en mängd olika kategorier såsom lista schemaläggning algoritmer, kluster algoritmer, guidade slumpmässiga sökmetoder och uppgift dubblering baserade algoritmer. I listan schemaläggningsalgoritmer [4] [5] [6], en beställd lista över uppgifter konstrueras genom att tilldela prioritet till varje uppgift och uppgifterna väljs för utförande baserat på deras prioritet. Lista schemaläggning algoritmer är i allmänhet att föredra eftersom de genererar god kvalitet scheman med mindre komplexitet. Lista schemaläggning algoritmer såsom Mapping Heuristic (MH) [4], Levelized Min
På samma sätt, Performance Effective Task Scheduling (PETS) algoritm REF består av tre steg, Nivåsortering, Uppgiftsprioritering, och Processor val.
Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments
{'venue': None, 'journal': 'Journal of Computer Science', 'mag_field_of_study': ['Computer Science']}