Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40556
Title: An efficient algorithm for scheduling instructions with deadline constraints on ILP processors
Authors: Wu, H. 
Jaffar, J. 
Issue Date: 2001
Source: Wu, H.,Jaffar, J. (2001). An efficient algorithm for scheduling instructions with deadline constraints on ILP processors. Proceedings - Real-Time Systems Symposium : 235-242. ScholarBank@NUS Repository.
Abstract: We propose an efficient algorithm for scheduling UET (Unit Execution Time) instructions with deadline constraints on ILP (Instruction Level Parallelism) processors with multiple functional units of different types. 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: I) Arbitrary precedence constraints, latencies in {-1, 0} and two functional units. 2) In-forest, equal latencies and multiple functional units. 3) Monotone interval graph and multiple functional units. For all above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. In each of the above special cases, no polynomial time algorithm existed before. 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.
Source Title: Proceedings - Real-Time Systems Symposium
URI: http://scholarbank.nus.edu.sg/handle/10635/40556
Appears in Collections:Staff Publications

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

Page view(s)

42
checked on Dec 16, 2017

Google ScholarTM

Check


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