An efficient algorithm for scheduling instructions with deadline constraints on ILP processors

Abstract

We propose an efficient algorithm for scheduling UET (Unit Execution Time) instructions with deadline constraints on ILP (Instruction Level Parallelism) processors with multiple functional units of different types. The time complexity of our algorithm is O(ne + nd), where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to compute a feasible schedule whenever one exists in the following special cases: I) Arbitrary precedence constraints, latencies in {-1, 0} and two functional units. 2) In-forest, equal latencies and multiple functional units. 3) Monotone interval graph and multiple functional units. For all above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. In each of the above special cases, no polynomial time algorithm existed before. Moreover, by setting all deadlines to a sufficiently large integer, our algorithm will compute a schedule with minimum length in all the above special cases.