Multigrid Algorithms on the Hypercube Multiprocessor,

Abstract

This paper examines several ways of implementing multigrid algorithms on the hypercube multiprocessor. We consider both the standard multigrid algorithms and a concurrent version proposed by Gannon and Van Rosendale. We present several mappings of the mesh points onto the nodes of the cube. The main property of these mappings, which are based on binary reflected Gray codes, is that the distance between neighboring grid points remains constant from one grid level to another. This results in a communication effective implementation of multigrid algorithms on the hypercube multiprocessor. The hierarchy of grids in multigrid algorithms presents a speical challenge in minimizing the communicaton overhead in a parallel implementation. For even though it is possible to map the grid points of the finest grid onto many architectures such that neighboring grid points are mapped into neighboring processors, it is generally much more difficult to preserve this proximity property for the coarser grids required in the multigrid algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1985
Accession Number
ADA152200

Entities

People

  • T. F. Chan
  • Y. Saad

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Computations
  • Computer Programming
  • Computer Science
  • Convergence
  • Data Transmission
  • Differential Equations
  • Equations
  • Errors
  • Grids
  • Integral Equations
  • Interpolation
  • Iterations
  • Partial Differential Equations
  • Three Dimensional
  • Two Dimensional

Readers

  • Computer Networking
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Image Processing and Computer Vision.