A partitionable parallel architecture allows the simultaneous execution of a number of tasks, where each task can be executed on a number of processors. This model introduces the problem of how many processors to allocate to each task. The processor allocation process must (1) determine the number of processors required to process each task and (2) allocate and schedule these tasks on the processors in the system. The objective is to minimize the time to complete all the tasks. In most cases at the current time, the number of processors assigned to each task is determined manually thereby leading to under-utilization of the processors. This project considers the design of efficient processor allocation algorithms for a large class of partitionable parallel architectures. The conventional scheduling problems, where each job runs on one processor, differ significantly from the processor allocation problem and thus their solutions cannot be expected to perform adequately for this processor allocation problem. The objectives of this project are to study the processor allocation problem, under different computation and architecture models, and design and evaluate algorithms for processor assignment and processor scheduling. These algorithms are tested, through both a simulation and their application to real problems. The performance gains made by the algorithms, and the overheads incurred by the operating system, are measured through experiments performed on different parallel architectures. The results from this research are expected to provide a definite step forward in understanding resource allocation and scheduling problems in partitionable architectures, and consequently lead to a better utilization of parallel architectures.
