Instruction Scheduling with Timing Constraints on a Single RISC Processor with 0/1 Latencies

In this paper, We propose a faster algorithm for the following instruction scheduling problem: Given a set of UET (Unit Execution Time) instructions with precedence constraints in the form of a DAG(Directed Acyclic Graph), latency constraints where latencies between any two instructions are restricted to be either 0 or 1, timing constraints in the form of individual integer release times and deadlines and a single RISC processor, find a feasible schedule which satisfies all constraints. The time complexity of our algorithm is O(n log n) + minfO(ne);O(n )g, where n is the number of instructions and e is the number of edges in the precedence graph. Our algorithm is faster than the existing algorithm which runs in O(n ff(n)) time, where ff(n) is the inverse of Ackermann function. In addition, our algorithm can be used to solve the maximum lateness minimization problem in O(n n + minfne;n g) time