Handling Inaccurate Runtime Estimates by Event-basedOptimization
Dalibor Klusáček, Hana Rudová · 2010
In this work we present an event-based optimization procedure designed to improve the performance of Conservative backfilling [1] under inaccurate runtime estimates. Conservative backfilling (CONS) is a modification of the well known EASY backfilling (EASY) algorithm [1]. While EASY makes reservation for the first job only, CONS makes reservation for every job—creating a “plan of execution”—to avoid “overtaking ” and large waiting times of jobs in the queue. However, EASY is more popular than CONS [2,3] because it usually outperforms CONS when the runtime estimates are not accurate [1,2]. Our solution is based on the use of CONS which we have extended with a fast optimization procedure. It is launched every time some job finishes earlier than expected. When the runtime estimates are inaccurate, this is a common situation, since the estimates are typically higher than the actual runtime. Upon each such event, a “gap ” appears in the reservation plan. Our optimization procedure tries to fill such gaps with suitable jobs, modifying the reservation plan. Jobs are selected randomly (Random Search (RS)) and are moved into a suitable gap—if such gap exists. Each move is evaluated, measuring the expected impact on the average slowdown and the average wait time. The optimization procedure finishes after the fixed number of iterations or the predefined time limit (50ms) is reached. The time limit is necessary to guarantee that the optimization will not significantly delay the job