Optimal Processor Assignment for Pipeline Computations
Abstract
The availability of large scale multitasked parallel architectures introduces the following processor assignment problem for pipelined computations. Given a set of tasks and their precedence constraints, along with their experimentally determined individual response times for different processor sizes, find an assignment of processors to tasks. Two objectives interest us: minimal response given a throughput requirement, and maximal throughput given a response time requirement. These assignment problems differ considerably from the classical mapping problem in which several tasks share a processor; instead, we assume that a large number of processors are to be assigned to a relatively small number of tasks. In this paper we develop efficient assignment algorithms for different classes of task structures. For a p processor system and a series-parallel precedence graph with n constituent tasks, we provide an O(np squared) algorithm that finds the optimal assignment for a response time optimization problem; we find the assignment optimizing the constrained throughput in o(np squared logp) time. Special cases of linear, independent, and three graphs are also considered. In addition, we also examine more efficient algorithms when certain restrictions are placed on the problem parameters. Our techniques are applied to a task system in computer vision.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1991
- Accession Number
- ADA242793
Entities
People
- Alok N. Choudhury
- Bhagirath Narahari
- David M. Nicol
- Rahul Simha