Abstract —Effektiv programplanering är avgörande för att uppnå hög prestanda i heterogena datormiljöer. Problemen med programplanering har visat sig vara NP-kompletterade både i allmänna fall och i flera begränsade fall. På grund av dess centrala betydelse har detta problem studerats i stor utsträckning och olika algoritmer har föreslagits i litteraturen som främst är för system med homogena processorer. Även om det finns några algoritmer i litteraturen för heterogena processorer, kräver de vanligtvis betydligt höga schemaläggningskostnader och de kanske inte levererar bra kvalitetsscheman med lägre kostnader. I detta dokument presenterar vi två nya schemaläggningsalgoritmer för ett begränsat antal heterogena processorer med målet att samtidigt uppfylla hög prestanda och snabb schemaläggningstid, som kallas den heterogena Earliest-Finish-Time-algoritmen (HEFT) och den kritiska-path-on-a-Processor-algoritmen (CPOP). HEFT-algoritmen väljer uppgiften med det högsta uppåtgående rankvärdet vid varje steg och tilldelar den valda uppgiften till processorn, vilket minimerar dess tidigaste sluttid med en insättningsbaserad metod. Å andra sidan använder CPOP-algoritmen summan av värden uppåt och nedåt för att prioritera uppgifter. En annan skillnad är i processorn urvalsfasen, som schemalägger de kritiska uppgifterna på processorn som minimerar den totala genomförandetiden för de kritiska uppgifterna. För att ge en robust och objektiv jämförelse med det relaterade arbetet, var en parametrisk grafgenerator utformad för att generera viktade riktade acykliska grafer med olika egenskaper. Jämförelsestudien, baserad både på slumpmässigt genererade grafer och graferna i vissa verkliga applikationer, visar att våra schemaläggningsalgoritmer avsevärt överträffar tidigare tillvägagångssätt både när det gäller kvalitet och kostnad för scheman, som huvudsakligen presenteras med schemalängd, upphastighet, frekvens av bästa resultat, och genomsnittliga schemaläggningstidsmått.
Den heterogena Earliest Finish Time (HEFT) algoritm REF upprätthåller en lista över uppgifter sorterade i fallande ordning efter deras uppåtgående rang.
Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}