Processor allocation, message scheduling, and algorithm selection for parallel space-time adaptive processing

The minimization of execution time (which includes both computation and communication components) and/or the maximization of throughput are of great significance in embedded parallel environments. Given tight system constraints associated with applications in these environments, it is imperative to efficiently map the tasks and/or data of an application onto the processors so as to reduce the imposed inter-processor communication traffic. In addition to mapping the tasks and data to the processors in an efficient manner, it is also important to schedule the communication of messages during phases of data movement so as to minimize network contention in an attempt to attain the smallest possible communication time. In this instance, mapping and scheduling can be classified as optimization problems, where the performance of the parallel system is vastly impacted by the optimization of both mapping and scheduling.

This dissertation involves optimizing the mapping of data and the scheduling of messages for a class of signal processing techniques known as space-time adaptive processing (STAP). An objective function is proposed to measure the quality of data mapping to processing elements of a parallel system for a STAP algorithm. The objective function is a cost metric that provides a quantitative measurement of the message traffic generated during phases of data movement based on the mapping of data to processors on a parallel system. The results show significant differences in the quality of data mappings using the proposed objective function.

A genetic algorithm (GA) based approach for solving the message scheduling optimization problem is proposed, and numerical results fi"om different scenarios are provided. The GA-based optimization is performed off-line, and the results of this optimization are static schedules for each processing element in the parallel system. These static schedules are then implemented in the on-line parallel STAP application. The results of this research illustrate significant improvement in communication time performance is possible using the proposed GA-based approach to scheduling.