Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/27657
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
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/27657
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

OPEN

NoneView/Download

Page view(s)

175
checked on Dec 11, 2017

Download(s)

78
checked on Dec 11, 2017

Google ScholarTM

Check


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