Blandmaskin heterogena datormiljöer (HC) använder en distribuerad uppsättning av olika högpresterande maskiner, sammankopplade med höghastighetslänkar, för att utföra olika beräkningsintensiva applikationer som har olika beräkningskrav. HC-miljöer är väl lämpade för att möta de beräkningskrav som stora, olika grupper av uppgifter ställer. Problemet med optimal kartläggning (definierad som matchning och schemaläggning) dessa uppgifter på maskinerna i en distribuerad HC-miljö har i allmänhet visat sig vara NP-komplett, vilket kräver utveckling av heuristiska tekniker. Att välja den bästa heurismen att använda i en given miljö är dock fortfarande ett svårt problem, eftersom jämförelser ofta fördunklas av olika underliggande antaganden i den ursprungliga studien av varje heuristisk. Därför har en samling av 11 heuristiker från litteraturen valts ut, anpassats, implementerats och analyserats under en uppsättning gemensamma antaganden. Det antas att heuristikerna härleder en kartläggning statiskt (dvs. off-line). Det antas också att en metatask (dvs. en uppsättning oberoende, icke-kommunicerande uppgifter) kartläggs och att målet är att minimera den totala verkställighetstiden för metatask. De 11 heuristikerna som undersökts är opportunistisk lastbalansering, minimal körtid, minimal fullbordad tid, Min, Max min, Duplex, Genetisk Algoritm, Simulerad Annealing, Genetisk Simulerad Annealing, Tabu och A*. Denna studie ger en jämn grund för jämförelse och insikter om omständigheter där en teknik kommer att överträffa en annan. Utvärderingsförfarandet är specificerat, heuristiken definieras och sedan diskuteras jämförelseresultaten. Det visas att för de fall som studeras här, den relativt enkla Min min heuristic presterar bra i jämförelse med andra tekniker. Akademisk press
De enkla algoritmer som föreslås av Braun är Opportunistic Load Balancing (OLB), Minimum Execution Time (MET), Minimum Completing Time (MCT), Min-min, Max-min, Duplex, Genetic Algorithm (GA), Simulated Annealing (SA), Genetisk Simulering Annealing (GSA), Tabu och A * REF.
A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems
{'venue': 'J. Parallel Distributed Comput.', 'journal': 'J. Parallel Distributed Comput.', 'mag_field_of_study': ['Computer Science']}