Problemet med att schemalägga ett parallellt program representerat av en viktad riktad acyklisk graf (DAG) till en uppsättning homogena processorer för att minimera slutförandet av programmet har studerats ingående. Problemets NP-fullständighet har stimulerat forskare att föreslå en myriad av heuristiska algoritmer. Även om de flesta av dessa algoritmer rapporteras vara effektiva, är det inte klart hur de jämför mot varandra. En meningsfull utvärdering och jämförelse av dessa algoritmer är en komplicerad uppgift och den måste ta hänsyn till ett antal frågor. För det första är de flesta schemaläggningsalgoritmer baserade på olika antaganden, vilket gör prestandajämförelsen ganska meningslös. För det andra finns det ingen standarduppsättning referensvärden för att undersöka dessa algoritmer. För det tredje utvärderas de flesta algoritmer med hjälp av små problemstorlekar, och därför är deras skalbarhet okänd. I detta dokument ger vi först en taxonomi för att klassificera olika algoritmer i olika kategorier beroende på deras antaganden och funktioner. Vi föreslår sedan en uppsättning riktmärken som bygger på olika strukturer och inte är partiska mot en viss schemaläggningsteknik. Vi har implementerat 15 schemaläggningsalgoritmer och jämfört dem på en gemensam plattform genom att använda de föreslagna riktmärkena, samt genom olika viktiga problemparametrar. Vi tolkar resultaten baserat på designfilosofier och principer bakom dessa algoritmer och drar slutsatser om varför vissa algoritmer presterar bättre än andra. Vi Artikel ID jpdc.1999.1578 föreslår också en prestandaåtgärd som kallas schemaläggning skalbarhet (SS) som fångar den kollektiva effektiviteten av en schemaläggningsalgoritm när det gäller dess lösningskvalitet, antalet processorer som används, och körtiden. 1999 Akademisk press
I sin allmänna form är detta problem NP-komplett och därför har ett antal heuristik föreslagits; se REF för en omfattande jämförelse av dessa heuristik.
Benchmarking and Comparison of the Task Graph Scheduling Algorithms 1
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}