Multigrid Algorithms on the Hypercube Multiprocessor

Tony F. Chan; Youcef Saad

doi:10.1109/TC.1986.1676698

Multigrid Algorithms on the Hypercube Multiprocessor

Tony F. Chan, Youcef Saad

Research output: Contribution to journal › Article › peer-review

87 Scopus citations

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.

Original language	English (US)
Pages (from-to)	969-977
Number of pages	9
Journal	IEEE Transactions on Computers
Volume	C-35
Issue number	11
DOIs	https://doi.org/10.1109/TC.1986.1676698
State	Published - Nov 1986
Externally published	Yes

Keywords

Gray codes
hvnercube multiprocessor
multigrid algorithms
parallel computing
partial differential equations

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/TC.1986.1676698

Cite this

@article{b4820c5301c547e2b271c2614eb78b75,

title = "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.",

keywords = "Gray codes, hvnercube multiprocessor, multigrid algorithms, parallel computing, partial differential equations",

author = "Chan, {Tony F.} and Youcef Saad",

year = "1986",

month = nov,

doi = "10.1109/TC.1986.1676698",

language = "English (US)",

volume = "C-35",

pages = "969--977",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - Multigrid Algorithms on the Hypercube Multiprocessor

AU - Chan, Tony F.

AU - Saad, Youcef

PY - 1986/11

Y1 - 1986/11

N2 - 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.

AB - 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.

KW - Gray codes

KW - hvnercube multiprocessor

KW - multigrid algorithms

KW - parallel computing

KW - partial differential equations

UR - http://www.scopus.com/inward/record.url?scp=0022812268&partnerID=8YFLogxK

U2 - 10.1109/TC.1986.1676698

DO - 10.1109/TC.1986.1676698

M3 - Article

AN - SCOPUS:0022812268

SN - 0018-9340

VL - C-35

SP - 969

EP - 977

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 11

ER -

Multigrid Algorithms on the Hypercube Multiprocessor

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this