Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40999
Title: Fast algorithm for scheduling instructions with deadline constraints on RISC machines
Authors: Wu, Hui 
Jaffar, Joxan 
Yap, Roland 
Issue Date: 2000
Source: Wu, Hui,Jaffar, Joxan,Yap, Roland (2000). Fast algorithm for scheduling instructions with deadline constraints on RISC machines. Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT : 281-290. ScholarBank@NUS Repository.
Abstract: 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 algorithms 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, n2.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.
Source Title: Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
URI: http://scholarbank.nus.edu.sg/handle/10635/40999
ISSN: 1089795X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

52
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.