Probabilistic loop scheduling for applications with uncertain execution time

Sissades Tongsima

doi:10.1109/12.822565

2000-01-01

PRE

Sissades Tongsima

Edwin H.‐M. Sha

Chantana Chantrapornchai

Surma, DR

DOI：10.1109/12.822565

原文链接

原文求助

摘要

En 中文

One of the difficulties in high-level synthesis and compiler optimization is obtaining a good schedule without knowing the exact computation time of the tasks involved. The uncertain computation times of these tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship between these tasks can be represented as a data-flow graph where each node models the task associated with a probabilistic computation time. A set of edges represents the dependencies between tasks. In this research, we study scheduling and optimization algorithms taking into account the probabilistic execution times. Two novel algorithms, called probabilistic retiming and probabilistic rotation scheduling, are developed for solving the underlying nonresource and resource constrained scheduling problems, respectively. Experimental results show that probabilistic retiming consistently produces a graph with a smaller longest path computation time for a given confidence level, as compared with the traditional retiming algorithm that assumes a fixed worst-case and average-case computation times. Furthermore, when considering the resource constraints and probabilistic environments, probabilistic rotation scheduling gives a schedule whose length is guaranteed to satisfy a given probability requirement. This schedule is better than schedules produced by other algorithms that consider worst-case and average-case scenarios.

Keyword:

scheduling

loop pipelining

probabilistic approach

retiming

rotation scheduling