Please use this identifier to cite or link to this item: https://doi.org/10.1109/RTCSA.2006.39|
Title: Instruction scheduling with release times and deadlines on ILP processors
Authors: Wu, H.
Jaffar, J. 
Xue, J.
Issue Date: 2006
Citation: Wu, H.,Jaffar, J.,Xue, J. (2006). Instruction scheduling with release times and deadlines on ILP processors. Proceedings - 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2006 : 51-60. ScholarBank@NUS Repository. https://doi.org/10.1109/RTCSA.2006.39|
Abstract: ILP (Instruction Level Parallelism) processors are being increasingly used in embedded systems. In embedded systems, instructions may be subject to timing constraints. An optimising compiler for ILP processors needs to find a feasible schedule for a set of time-constrained instructions. In this paper, we present a fast algorithm for scheduling instructions with precedence-latency constraints, individual integer release times and deadlines on an ILP processor with multiple functional units. The time complexity of our algorithm is O(n 2 log d) + min{O(de), O(ne)} + min{O(ne), O(n 2.376)}, 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 find a feasible schedule whenever one exists in the following special cases: 1) one functional unit, arbitrary precedence constraints, latencies in {0, 1}, integer release times and deadlines; 2) two identical functional units, arbitrary precedence constraints, latencies of 0, integer release times and deadlines; 3) multiple identical functional units or multiple functional units of different types, monotone interval-ordered graph, integer release times and deadlines; 4) multiple identical functional units, in-forest, equal latencies, integer release times and deadlines. In case 1), our algorithm improves the existing fastest algorithm from O(n 2 log n) + mm{O(ne),O(n 2.376)} to min{O(ne), O(n 2.376)}. In case 2), our algorithm improves the existing faste st algorithm from O(ne + n 2 log n) to min{O(ne), O(n 2.376)}. In case 3), no polynomial time algorithm for multiple functional units of different types was known before. © 2006 IEEE.
Source Title: Proceedings - 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2006
URI: http://scholarbank.nus.edu.sg/handle/10635/40858
ISBN: 0769526764
DOI: 10.1109/RTCSA.2006.39|
Appears in Collections:Staff Publications

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

Google ScholarTM

Check

Altmetric


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