Rectilinear Partitioning of Irregular Data Parallel Computations

Abstract

This paper describes new mapping algorithms for domain-oriented data parallel computations, where the workload is distributed irregularly throughout the domain, but exhibits localized communication patterns. We consider the problem of partitioning the domain for parallel processing in such a way that the workload on the most heavily loaded processor is minimized, subject to the constraint that the partition be perfectly rectilinear. Rectilinear partitions are useful on architectures that have a fast local mesh network and a relatively slower global network; these partitions heuristically attempt to maximize the fraction of communication carried by the local network. This paper provides an improved algorithm for finding the optimal partition in one dimension, new algorithms for partitioning in two dimensions, and shows that optimal partitioning in three dimensions is NP-complete. We discuss our application of these algorithms to real problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1991
Accession Number
ADA240681

Entities

People

  • David M. Nicol

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computations
  • Computer Programming
  • Computing System Architectures
  • Differential Equations
  • Fluid Dynamics
  • Fluid Flow
  • Global Communications
  • Linear Arrays
  • Orientation (Direction)
  • Parallel Computing
  • Partial Differential Equations
  • Spatial Partitioning
  • Three Dimensional
  • Two Dimensional
  • Workload

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Fluid Dynamics.
  • Mathematical Modeling and Probability Theory.