Please use this identifier to cite or link to this item:
Title: Scheduling time-constrained instructions by consistency techniques
Authors: WU HUI
Keywords: Instruction scheduling, ILP processor, timing constraint, embedded system, k-successor-tree consistency, feasible schedule
Issue Date: 24-Dec-2003
Citation: WU HUI (2003-12-24). Scheduling time-constrained instructions by consistency techniques. ScholarBank@NUS Repository.
Abstract: Scheduling Time-Constrained Instructions by Consistency Techniques Wu Hui ILP (Instruction Level Parallelism) processors are being increasingly used in real-time embedded systems. In real-timeembedded systems, critical tasks are subject to timing constraints such as release times and deadlines. As a result, instructions may also be subject to timing constraints. Inthe presence of timing constraints, the objective of a compiler is to find a feasible schedule which satisfies all timingconstraints. Nevertheless, the problem of finding a feasible schedule whenever one exists is NP-complete even if the ILPprocessor has only one functional unit and the latency can be arbitrarily large. In this thesis, we study the problem of scheduling time-constrained instructions in a basic block on an ILP processor. We propose a novel consistency notion, i.e. k-successor-tree-consistency, for scheduling instructions with timing constraints. Based on this consistency notion and other novel techniques such as forward scheduling and backward scheduling, we propose several provably good algorithms for finding a feasible schedule for the instruction scheduling problems with different timing constraints. Our algorithms solve several open problems and improve a number of existingalgorithms.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Wu-Hui-PhD-Thesis.pdf1.33 MBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


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