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
If you have questions or technical problems, please Contact LSU-ETD Support.