Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/40999
DC FieldValue
dc.titleFast algorithm for scheduling instructions with deadline constraints on RISC machines
dc.contributor.authorWu, Hui
dc.contributor.authorJaffar, Joxan
dc.contributor.authorYap, Roland
dc.date.accessioned2013-07-04T08:17:16Z
dc.date.available2013-07-04T08:17:16Z
dc.date.issued2000
dc.identifier.citationWu, 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.
dc.identifier.issn1089795X
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40999
dc.description.abstractWe 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.
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
dc.description.page281-290
dc.description.coden216
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

Page view(s)

74
checked on Oct 28, 2019

Google ScholarTM

Check


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