Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/27657
DC Field | Value | |
---|---|---|
dc.title | Scheduling time-constrained instructions by consistency techniques | |
dc.contributor.author | WU HUI | |
dc.date.accessioned | 2011-10-12T18:00:46Z | |
dc.date.available | 2011-10-12T18:00:46Z | |
dc.date.issued | 2003-12-24 | |
dc.identifier.citation | WU HUI (2003-12-24). Scheduling time-constrained instructions by consistency techniques. ScholarBank@NUS Repository. | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/27657 | |
dc.description.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. | |
dc.language.iso | en | |
dc.subject | Instruction scheduling, ILP processor, timing constraint, embedded system, k-successor-tree consistency, feasible schedule | |
dc.type | Thesis | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.contributor.supervisor | JAFFAR, JOXAN | |
dc.description.degree | Ph.D | |
dc.description.degreeconferred | DOCTOR OF PHILOSOPHY | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Ph.D Theses (Open) |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
Wu-Hui-PhD-Thesis.pdf | 1.33 MB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.