This research was supported in part by the Air Force Office of Scientific Research under Grant F49620-86-K-006


This work studies the use of intelligence-guided control of reconfigurable parallel processing systems. A reconfigurable architecture is one that can be partitioned into several independent virtual parallel machines operating in either SIMD or MIMD mode. Reconfigurable systems, while allowing great flexibility, present many scheduling and control problems. Scheduling tasks on such a system is an exponential time problem. Therefore, in an effort to achieve reduced, task execution time without incurring unacceptable scheduling costs, an expert system is used to apply heuristics to approximate an optimal schedule. When the execution time of a task is not known a priori, conventional scheduling methods which produce optimal or near-optimal Schedules cannot be used effectively. A dynamic controller, however, is not locked into a static schedule and pan reconfigure the machine and process subtasks based on the current state of the parallel processing system. The scheduling system attempts to achieve decreased execution time by balancing the overall processing scenario of the task with the needs of the individual routines that make up the task. Repartitioning is done when either the processor’s resources need to be split among the subtasks or the processor’s resources have become fragmented and need to be merged into larger partitions. The scheduler keeps track of what subtasks are potentially executable and chooses the best candidate by considering the relative importance of quickly finishing the subtask and the matching of partition data contents and subtask data needs.

Date of this Version