Reducing Processor Communication Overhead in Multiprocessor Scheduling
Abstract
The parallelism within an algorithm at any stage of execution can be defined as the number of independent operations that can be perfonned in parallel. These independent operations can be simultaneously scheduled on multiple processors. The scheduling algorithm used for this purpose influences the time taken to complete the entire set of operations. The efficiency and overhead of such a schedule depends on many issues such as task decomposition, allocation of tasks to processors, and processor communication overhead. In general, a given problem can be decomposed into smaller tasks/processes/operations, with interdependencies among them (i.e., the precedence relation among the tasks). Using known algorithms, the maximum possible parallelism can be extracted from these interdependencies. Subsequently, the tasks can be allocated to a set of available processors. The objective of the proposed thesis was to improve such parallel executions (in terms of multiprocessor performance) by reducing the communication overhead among processors. Research has been mainly conducted on detenninistic scheduling algorithms for multiprocessors. These algorithms can schedule a set of tasks, given in the fonn of a directed acyclic graph (DAG), on a given number of processors. Communication overhead between processors can be an important distinguishing factor among possible schedules of a given task system. The purpose of the thesis was to reduce the communication overhead between processors, which could result in faster execution times for algorithms. A simulation program was developed to study the effects of reducing processor communication overhead in multiprocessor scheduling. The program implements the proposed algorithm (algorithm D) which generates a schedule for a task system based on each task's predecessors. The test suite consisted of task systems obtained from various sources, but mostly from a task system generator program, which was designed and implemented as part of this work. It was found that algorithm D reduces the interprocessor communication overhead in most of the cases.
Collections
- OSU Theses [15752]