Utnyttjandet av parallella datorer beror på hur jobben packas ihop: om jobben inte är tätt packade går resurserna förlorade på grund av fragmenteringen. Problemet är att målet med ett högt utnyttjande kan stå i konflikt med målen om rättvisa eller till och med framsteg för alla arbetstillfällen. Den gemensamma lösningen är att använda backfilling, som kombinerar en reservation för det första jobbet i intresse av framsteg med förpackning av senare jobb för att fylla i hål och öka utnyttjandet. Återfyllning anser dock de köade jobben en i taget, och därmed kan missa bättre förpackningsmöjligheter. Vi föreslår användning av dynamisk programmering för att hitta bästa möjliga förpackning med tanke på den aktuella sammansättningen av kön, vilket maximerar utnyttjandet på varje schemaläggning steg. Simuleringar av denna algoritm, kallad LOS (Lookahead Optimizing Scheduler), med hjälp av spårfiler från flera IBM SP parallella system, visar att LOS verkligen förbättrar utnyttjandet, och därmed minskar den genomsnittliga svarstiden och genomsnittlig avmattning av alla jobb. Dessutom är det faktiskt möjligt att begränsa siktdjupet till omkring 50 arbetstillfällen och ändå uppnå i stort sett samma resultat. Slutligen experimenterade vi med att välja bland alternativa arbetstillfällen som uppnår samma utnyttjande. Förvånande resultat tyder på att valet av uppsättningen i kön inte nödvändigtvis garanterar bästa prestanda. Istället, upprepade gånger välja uppsättningen med den maximala totala förväntade avmattning ökar prestanda jämfört med alla andra alternativ kontrolleras.
Shmueli m.fl. I REF föreslogs en backfillingsteknik där senare arbeten förpackas för att fylla i hål och öka utnyttjandet utan att försena de tidigare jobben.
Backfilling with Lookahead to Optimize the Packing of Parallel Jobs ∗
{'venue': 'ICPP', 'journal': None, 'mag_field_of_study': ['Computer Science']}