Content

•  
   List of Figures
•  
   List of Tables
•  
   Abstract
•  
   1 Introduction
•  
   1.1 Motivation to Real-Time Multitasking
•  
   1.2 Contribution of This Thesis
•  
   1.3 Chapter Outline
•  
   2 Background and Related Work
•  
  2.1 Reconfigurable Hardware Devices
•  
   2.1.1 Fine-Grain RHDs (FPGAs)
•  
   2.1.2 Coarse-Grain RHDs
•  
   2.1.3 Configuration Memory and Reconfiguration
•  
   2.1.4 Architecture of RHD Based Computer Platforms
•  
   2.2 Hardware Tasks
•  
  2.3 Multi-Tasking on Reconfigurable Hardware
•  
   2.3.1 Resource Sharing Models
•  
   2.3.2 Task Scheduling and Placement Methods for RHDs
•  
   2.3.3 Dynamic Reconfigurable Systems
•  
  2.4 Real-Time Scheduling
•  
   2.4.1 A Background on RT Systems
•  
   2.4.2 RT Scheduling Problems and Algorithms for Uniprocessor Systems
•  
   2.4.3 RT Scheduling Problems and Algorithms for Multiprocessor Systems
•  
   2.4.4 Real-Time Scheduling on RHDs and Similar Architectures
•  
   2.5 Chapter Conclusion
•  
  3 Problem Modeling and Metrics
•  
   3.1 Task and Resource Models
•  
   3.2 Feasible Schedule
•  
   3.3 Utilization Metrics
•  
   3.4 Chapter Conclusion
•  
   4 Three Scheduling Algorithms
•  
  4.1 Global Scheduling
•  
   4.1.1 Earliest Deadline First on RHDs
•  
   4.1.2 Relation to Multiprocessor EDF
•  
   4.1.3 Schedulability Analysis for EDF-FkF
•  
   4.1.4 Conclusion on global EDF
•  
  4.2 Partitioned Scheduling
•  
   4.2.1 Partitioned Scheduling on RHDs
•  
   4.2.2 Relation to 2-Dimensional Packing Problems
•  
   4.2.3 Optimal Partitioning by ILP
•  
   4.2.4 Next-Fit-Decreasing-Area Partitioning
•  
   4.2.5 Conclusion on Partitioned EDF
•  
  4.3 Server-Based Scheduling
•  
   4.3.1 The Merge-Server Distribute Load (MSDL) Algorithm
•  
   4.3.2 Exact Evaluation of Computation Time Reduction
•  
   4.3.3 Properties of MSDL
•  
   4.3.4 Conclusion on Server-Based Scheduling
•  
   4.4 Chapter Conclusion
•  
  5 Comparison of Algorithm Scheduling Performance
•  
   5.1 Analytical Comparison and Scheduling Anomalies
•  
  5.2 Simulation Results
•  
   5.2.1 Creation of Benchmarks
•  
   5.2.2 Performance on Standard Benchmark BMstd
•  
   5.2.3 Impact of Area and Time-utilization
•  
   5.2.4 Performance of Combined Algorithms
•  
   5.2.5 Impact of Number of Tasks
•  
   5.3 Conclusion on Algorithm Performance
•  
  6 Execution Model and Overhead Analysis
•  
  6.1 Global EDF Overhead Model
•  
   6.1.1 Reconfiguration Modes and Task Placement
•  
   6.1.2 Runtime System Requirements
•  
   6.1.3 Reconfiguration Overheads
•  
  6.2 Partitioned EDF Overhead Model
•  
   6.2.1 Reconfiguration Modes and Task Placement
•  
   6.2.2 Runtime System Requirements
•  
   6.2.3 Reconfiguration Overheads
•  
   6.3 Server Based MSDL Overhead Model
•  
   6.3.1 Reconfiguration Modes and Task Placement
•  
   6.3.2 Runtime System Requirements
•  
   6.3.3 Reconfiguration Overheads
•  
  6.4 Performance Evaluation Including Overhead
•  
   6.4.1 Global EDF Overhead Evaluation
•  
   6.4.2 Partitioned EDF Overhead Evaluation
•  
   6.4.3 Server Based MSDL Overhead Evaluation
•  
   6.5 Conclusion on Execution Models and Overhead
•  
  7 Model Extensions
•  
   7.1 Periodic Tasks with Variants
•  
   7.1.1 Variant-Rich Tasks
•  
   7.1.2 Partitioned Scheduling of Variant-Rich Tasks
•  
   7.1.3 Optimal Partitioning by ILP
•  
   7.1.4 Performance Evaluation for Variant-Rich Tasks
•  
   7.1.5 Approaches for Global- and Server Scheduling of Variant-Rich Tasks
•  
   7.2 Periodic Tasks with Memory Access
•  
   7.2.1 The Buffer Assignment Problem
•  
   7.2.2 Task Schedule Aware Buffer Assignment
•  
   7.2.3 Buffer Assignment Based on Integer Programming
•  
   7.2.4 Simulation Results
•  
   7.2.5 Concluding Discussion on Memory Demanding RT Applications
•  
   7.3 Chapter Conclusion
•  
  8 Prototype: FPGA Based Real-Time Kernel
•  
  8.1 System Architecture
•  
   8.1.1 An All-Hardware Runtime System
•  
   8.1.2 Scheduler Data Structures
•  
   8.1.3 The Scheduler Cycle
•  
   8.2 Synthesis Tool Flow
•  
   8.3 Synthesis Results
•  
   8.4 Chapter Conclusion
•  
  9 Conclusion and Outlook
•  
   9.1 Summary
•  
   9.2 Drawn Conclusions
•  
   9.3 Outlook and Future Work
•  
   Author's Publications
•  
   Bibliography