Optimal processor assignment for a class of pipelined computations

Publisher Website
Google Scholar
Abstract
The availability of large-scale multitasked parallel architectures introduces the followingprocessor assignment problem. We are given a long sequence of data sets, each of whichis to undergo processing by a collection of tasks whose intertask data dependencies forma series-parallel partial order. Each individual task is potentially parallelizable, with aknown experimentally determined execution signature. Recognizing that data sets can bepipelined through the task structure, the problem is to find a "good" assignment ofprocessors to tasks. Two objectives interest us: minimal response time per data set,given a throughput requirement, and maximal throughput, given a response timerequirement. Our approach is to decompose a series-parallel task system into its essential"serial" and "parallel" components; our problem admits the independent solution andrecomposition 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(np/sup 2/) algorithm that finds the optimal assignment (over a broad class ofassignments) for the response time optimization problem; we find the assignmentoptimizing the constrained throughput in O(np/sup 2/ log p) time. These techniques areapplied to a task system in computer vision.

This publication has 26 references indexed in Scilit: