Experience with Parametric Binary Dissection

Abstract

Parametric Binary Dissection (PBD) is a new algorithm that can be used for partitioning graphs embedded in 2- or 3-dimensional space. It partitions explicitly on the basis of nodes + Lamda x (edges cut), where Lamda is the ratio of time to communicate over an edge to the time to compute at a node. The new algorithm is faster than the original binary dissection algorithm and attempts to obtain better partitions than the older algorithm, which only takes nodes into account. We compare the performance of parametric dissection with plain binary dissection on 3 large unstructured 3-d meshes obtained from computational fluid dynamics and on 2 random graphs. We show that the new algorithm can usually yield partitions that are substantially superior, but that its performance is heavily dependent on the input data.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1993
Accession Number
ADA274649

Entities

People

  • Shahid H. Bokhari

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computational Fluid Dynamics
  • Computers
  • Dynamics
  • Electrical Engineering
  • Engineering
  • Fluid Dynamics
  • Mathematics
  • Parallel Computing
  • Parallel Processing
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Educational Psychology
  • Neural Network Machine Learning.

Technology Areas

  • Space