Rectilinear Partitioning of Irregular Data Parallel Computations

Research output: Contribution to journalArticlepeer-review


This paper describes new mapping algorithms for domain-oriented data-parallel computations, where the workload is distributed irregularly throughout the domain, but exhibits localized or rectilinear 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. We provide an improved algorithm for finding the optimal partition in one dimension, propose new algorithms for partitioning in two dimensions, and show that optimal partitioning in three dimensions is NP-complete. We discuss our application of these algorithms to real problems.

Original languageEnglish (US)
Pages (from-to)119-134
Number of pages16
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - 1994
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Rectilinear Partitioning of Irregular Data Parallel Computations'. Together they form a unique fingerprint.

Cite this