Optimal Processor Assignment for a Class of Pipelined Computations

Alok N. Choudhary, Rahul Simha

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

The availability of large-scale multitasked parallel architectures introduces the following processor assignment problem. We are given a long sequence of data sets, each of which is to undergo processing by a collection of tasks whose intertask data dependencies form a series-parallel partial order. Each individual task is potentially parallelizable, with a known experimentally determined execution signature. Recognizing that data sets can be pipelined through the task structure, the problem is to find a “good” assignment of processors to tasks. Two objectives interest us: minimal response time per data set, given a throughput requirement, and maximal throughput, given a response time requirement Our approach is to decompose a series-parallel task system into its essential “serial” and “parallel” components; our problem admits the independent solution and recomposition of each such component. We provide algorithms for the series analysis, and use an algorithm due to Krishnamurti and Ma for the parallel analysis. For a p processor system and a series-parallel precedence graph with n constituent tasks, we give a O(np2) algorithm that finds the optimal assignment (over a broad class of assignments) for the response time optimization problem; we find the assignment optimizing the constrained throughput in O(np2 log p) time. Our techniques are applied to a task system in computer vision.

Original languageEnglish (US)
Pages (from-to)439-445
Number of pages7
JournalIEEE Transactions on Parallel and Distributed Systems
Volume5
Issue number4
DOIs
StatePublished - Apr 1994

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Optimal Processor Assignment for a Class of Pipelined Computations'. Together they form a unique fingerprint.

Cite this