I parallella adaptiva applikationer ändras applikationens beräkningsstruktur över tiden, vilket leder till obalans i belastningen trots att de initiala lastfördelningarna var balanserade. För att återställa balansen och hålla kommunikationsvolymen låg i vidare iterationer av applikationerna krävs dynamisk belastningsbalansering (omfördelning) av den ändrade beräkningsstrukturen. Omfördelning skiljer sig från statisk belastningsbalansering (partitionering) på grund av det ytterligare kravet på att minimera migrationskostnaden för att flytta data från en befintlig partition till en ny partition. I detta dokument presenterar vi en ny omdelningshybridmodell för dynamisk lastbalansering som står för både kommunikationsvolym i applikationen och migrationskostnader för att flytta data, för att minimera den totala kostnaden. Med hjälp av en hypergrafbaserad modell kan vi exakt modellera kommunikationskostnaderna i stället för att approximera dem med grafbaserade modeller. Vi visar att den nya modellen kan realiseras med hjälp av hypergraph-partitionering med fasta hörn och beskriver vårt parallella multilevel-implementation inom Zoltan-verktyget för lastbalansering. Såvitt vi vet är detta den första implementeringen för dynamisk lastbalansering baserad på hypergrafpartitionering. För att visa effektiviteten i vårt tillvägagångssätt utförde vi experiment på ett Linuxkluster med 1024 processorer. Resultaten visar att vår nya modell, när det gäller att minska den totala kostnaden, på ett gynnsamt sätt jämför med de grafbaserade dynamiska lastbalanseringsstrategierna, och att flernivåstrategier avsevärt förbättrar fördelningens kvalitet.
al REF undersökte hur man dynamiskt återställer balansen i parallella vetenskapliga datortillämpningar där ansökningarnas beräkningsstruktur förändras över tiden.
A Repartitioning Hypergraph Model for Dynamic Load Balancing
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}