Resource constrained and speculative scheduling of an algorithm class with run-time dependent conditionals

Abstract

We present a significant extension of the quantified equation based algorithm class of piecewise regular algorithms. The main contributions of the following paper are: the class of piecewise regular algorithms are extended by allowing run-time dependent conditionals; a mixed integer linear program is given to derive optimal schedules of the novel class we call dynamic piecewise regular algorithms; and in order to achieve highest performance, we present a speculative scheduling approach. The results are applied to an illustrative example.