A Multistage Linear Array Assignment Problem

Abstract

Implementation of certain algorithms on parallel computing architectures can involve partitioning contiguous elements into a fixed number of groups, each of which is to be handled by a single processor. It is desired to find an assignment of elements to processors that minimizes the sum of the maximum workloads experienced at each stage. This problem can be viewed as a multi-objective network optimization problem. Polynomially-bounded algorithms are developed for the case of two-stages, whereas the associated decision problem (for an arbitrary number of stages) is shown to be NP-complete. Heuristic procedures are therefore proposed and analyzed for the general problem. Computational experience with one of the exact problems, incorporating certain pruning rules, is presented for a variety of test problems. Empirical results also demonstrate that one of the heuristic procedures is especially effective in practice.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1988
Accession Number
ADA203532

Entities

People

  • D. M. Nicol
  • D. R. Shier
  • D. S. Richards
  • R. K. Kincaid

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Computing System Architectures
  • Fluid Flow
  • Heuristic Methods
  • Image Processing
  • Linear Arrays
  • Network Protocols
  • Numbers
  • Operations Research
  • Optimization
  • Parallel Computing
  • Parallel Processing
  • Polynomials
  • Workload

Fields of Study

  • Engineering

Readers

  • Operations Research