a fast algorithm for scheduling instructions with deadline constraints on risc processors
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 lij = -1 which denotes that instruction vj cannot be started before vi. 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 + e1log n) to O(min{ne; n2.376}) where e1 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.
deadline constraints feasible schedule inter-instructional latency instruction scheduling