A fast algorithm for scheduling instructions with deadline constraints on RISC machines

We present a fast algorithm for scheduling UET (Unit Execution Time) instructions with deadline constraints in a basic block on RISC machines with multiple processors. Unlike Palem and Simon´s algorithm, our algorithm allows latency of 1_ij=-1 which denotes that instruction v_j cannot be started before v_i. 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: 1) Arbitrary precedence constraints, latencies in {0, 1} and one processor. In this special case, our algorithm improves the existing fastest algorithm from O(ne+e´log n) to O(min{ne, n^2.376}), where e´ is the number of edges in the transitively closed precedence graph. 2) Arbitrary precedence constraints, latencies in {-1, 0} and two processors. In the special case where all latencies are 0, our algorithm degenerates to Garey and Johnson´s two processor algorithm. 3) Special precedence constraints in the form of monotone interval graph, arbitrary latencies in {-1, 0, 1, ···, d} and multiple processors. 4) Special precedence constraints in the form of in-forest, equal latencies and multiple processors. In the above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. 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 and the special case of out-forest, equal latencies and multiple processors