Title page for ETD etd-03252009-172523


Type of Document Dissertation
Author Elbidweihy, Mostafa
Author's Email Address mkadry76@gmail.com
URN etd-03252009-172523
Title Task Scheduling and Placement for Reconfigurable Devices
Degree Doctor of Philosophy (Ph.D.)
Department Electrical & Computer Engineering
Advisory Committee
Advisor Name Title
Jerry Trahan Committee Chair
J. Ramanujam Committee Member
Ramachandran Vaidy Committee Member
Sukhamay Kundu Committee Member
Suresh Rai Committee Member
Yaniv Almog Dean's Representative
Keywords
  • task scheduling
  • placement
  • dynamic reconfiguration
  • partial reconfiguration
  • reconfigurable devices
  • RC devices
Date of Defense 2009-03-19
Availability unrestricted
Abstract
Partially reconfigurable devices allow the execution of different tasks at the same time, removing tasks when they finish and inserting new tasks when they arrive. This dissertation investigates scheduling and placing real-time tasks (tasks with deadline) on reconfigurable devices.

One basic scheduler is the First-Fit scheduler. By allowing the First-Fit scheduler to retry tasks while they can satisfy their deadlines, we found that its performance can be enhanced to be better than other schedulers. We also proposed a placement idea based on partitioning the reconfigurable area into regions of various widths, assigning a task to a region based on its width. This idea has a similar rejection rate to a First-Fit scheduler that retries placing tasks and performs better than the First-Fit that does not retry tasks. Also, this regions-based scheduling method has a better running time.

Managing how the space will be shared among tasks is a problems of interest. The main function of the free-space manager is to maintain information about the free space (areas not used by active tasks) after any placement or deletion of a task. Speed and efficiency of the free-space data structure are important as well as its effect on scheduler performance. We introduce the use of maximal horizontal strips and maximal vertical strips to represent free space. This resulted in a faster free space manager compared to what has been used in the area.

Most researchers in the area of scheduling on reconfigurable devices assumed a homogeneous FPGA with only CLBs in the reconfigurable area. Most reconfigurable devices offered in the market, however, are not homogeneous but heterogeneous with other components between CLBs. We studied the effect of heterogeneity on the performance of schedulers designed for a homogeneous structure. We found that current schedulers result in worse performance when applied to a heterogeneous structure, but by simple modifications, we can apply them to a heterogeneous structure and achieve good performance. Consequently, the approach of studying homogeneous FPGAs is a valid one, as the scheduling ideas discovered there do carry over to heterogeneous FPGAs.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Elbidweihy_Dissertation.pdf 3.86 Mb 00:17:50 00:09:10 00:08:01 00:04:00 00:00:20

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.