Hybrid Method to Predict Execution Time of Parallel Applications.
Bernard Miegemolle, Thierry Monteil · Conference on Scientific Computing · 2008
Many researches are carried out in the domain of the execution time prediction for sequential or parallel applications. This data can be used by job scheduling algorithms present on grid or cluster infrastructures to improve their behavior. In real-time context, the prediction of execution time is a crucial data, which the respect of deadline constraints may depend on. Both domains introduce their own prediction models. In parallel job scheduling, historic-based models can be used to estimate the execution time of a job using an experience base of past executions of similar jobs. In real-time domain, the Worst Case Execution Time (WCET) of applications is notably computed from the profile of the applications. In this paper, an hybrid method for predicting execution time of parallel applications is presented. This method relies on both profile-based and historicbased predictions. Programs profiles are analyzed in order to decompose them into a set of basic blocks. The execution time of each block is determined using past executions of the programs. Then, a prediction of the overall execution time can be performed by applying historic-based predictions model to estimate the execution count of basic blocks.