Static scheduling in a reconfigurable hardware environment

This dissertation 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 a 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 determine the configuration of the reconfigurable hardware as well as create 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. In this research, three types of probabilistic scheduling techniques (random, simulated annealing and genetic algorithms) have been adapted to this domain through the development of a common objective function that reflects task ordering and configurable resource usage. The effectiveness of each of these three techniques has been evaluated in a statistical manner by comparing the projected performance of the valid schedules that have been created when a large set of arbitrarily-structured task systems were applied to all three scheduling strategies.