Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/40556
DC FieldValue
dc.titleAn efficient algorithm for scheduling instructions with deadline constraints on ILP processors
dc.contributor.authorWu, H.
dc.contributor.authorJaffar, J.
dc.date.accessioned2013-07-04T08:07:04Z
dc.date.available2013-07-04T08:07:04Z
dc.date.issued2001
dc.identifier.citationWu, 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.
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40556
dc.description.abstractWe 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.
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleProceedings - Real-Time Systems Symposium
dc.description.page235-242
dc.description.codenPRSYE
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)

115
checked on Nov 24, 2022

Google ScholarTM

Check


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