I detta dokument föreslår vi en statisk schemaläggningsalgoritm för tilldelning av uppgiftsgrafer till fullt anslutna multiprocessorer. Vi diskuterar sex nyligen rapporterade schemaläggningsalgoritmer och visar att de har en nackdel eller en annan som kan leda till dålig prestanda. Den föreslagna algoritmen, som kallas Dynamic Critical-Path (DCP) schemaläggningsalgoritm, skiljer sig från de tidigare föreslagna algoritmerna på ett antal sätt. Först bestämmer den den kritiska sökvägen för aktivitetsgrafen och väljer nästa nod som ska schemaläggas på ett dynamiskt sätt. För det andra omorganiserar det schemat på varje processor dynamiskt i den meningen att positionerna för noderna i de partiella scheman inte är fasta förrän alla noder har beaktats. För det tredje väljer det en lämplig processor för en nod genom att se framåt de potentiella starttiderna för de återstående noderna på den processorn, och schemalägger relativt mindre viktiga noder till processorer som redan används. En global och en parvis jämförelse görs för alla sju algoritmer under olika schemaläggningsförhållanden. DCP-algoritmen överträffar de tidigare algoritmerna med stor marginal. Trots att DCP-algoritmen har ett antal nya funktioner har den tillåtliga tids komplexiteten, är ekonomisk i fråga om antalet processorer som används och är lämplig för ett brett spektrum av grafstrukturer.
Den dynamiska kritiska vägen (DCP) heuristiska REF beräknar den kritiska vägen (CP) för den partiella schemat och väljer den färdiga vertex med minst rörlighet för schemaläggning först.
Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors
{'venue': 'IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS', 'journal': None, 'mag_field_of_study': ['Computer Science']}