Accession Number : ADA242793
Title : Optimal Processor Assignment for Pipeline Computations
Descriptive Note : Final rept.
Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
Personal Author(s) : Nicol, David M ; Simha, Rahul ; Choudhury, Alok N ; Narahari, Bhagirath
Report Date : Oct 1991
Pagination or Media Count : 39
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.
Descriptors : *COMPUTER ARCHITECTURE , *PIPELINES , *PARALLEL PROCESSING , COMPUTATIONS , SIZES(DIMENSIONS) , PARAMETERS , REACTION TIME , GRAPHS , STRUCTURES , EFFICIENCY , PROCESSING EQUIPMENT , AVAILABILITY , RESPONSE , THROUGHPUT , MAPPING , OPTIMIZATION , COMPUTER VISION , ALGORITHMS , REQUIREMENTS
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE