A Genetic Algorithm Approach to Static Task Scheduling in a Reconfigurable Hardware Environment

This paper presents a basic framework for applying static task scheduling techniques to arbitrarily-structured task systems whose targeted execution environment is comprised of finite amounts of reconfigurable hardware. Such reconfigurable hardware is characterized by the fact that its structure and logical functionality can be altered any time after the hardware devices are constructed. Such an environment is assumed to allow for the use of multiple sequential processing elements, task-specific logic and a communication network within the reconfigurable hardware. This research focuses upon the application of scheduling theory to a static/deterministic environment where all the task execution times and communication times can be estimated with a great degree of certainty, and the system configuration is determined prior to the execution of the application. The goal of this strategy is to create schedules that have minimal overall execution time under the constraint that the implementation of such schedules does not require more resources of any type than is present within the reconfigurable hardware. This scheduling technique conforms in many ways to those applied to the heterogeneous parallel and distributed processing domains but with the addition that the scheduling routines also determines the configuration of the reconfigurable hardware as well as creating an ordered list of tasks and communications for each sequential processing element that is employed. This hardware configuration information includes the type of processors employed, the type of communication that is supported by each data link (buffered or non-buffered), and the interconnection topology needed to support these data links. This paper highlights how a genetic algorithm can be utilized to create schedules for such an environment.