A parallel implementation of MRSB

Author

Barnard, Stephen T.

Author_Institution

Cray Res. Inc., Sunnyvale, CA, USA

Volume

1

fYear

1996

fDate

3-6 Jan 1996

Firstpage

594

Abstract

The design of a parallel implementation of multilevel recursive spectral bisection (PMRSB) is described. The code is fast enough to enable dynamic repartitioning of adaptive meshes and to partition meshes that are too large for workstations. Two innovations in the implementation are recursive asynchronous task teams and a parallel version of the multilevel accelerator. A performance improvement of a factor of 140 over the best available serial implementation is demonstrated (a high-end workstation compared to a 256-processor T3D, partitioning a large problem into 256 domains)

Keywords

graph colouring; parallel algorithms; parallel machines; resource allocation; software performance evaluation; workstations; MRSB; adaptive meshes; dynamic repartitioning; graph coloring; high-end workstation; mesh partitioning; multilevel accelerator; multilevel recursive spectral bisection; parallel implementation; performance; recursive asynchronous task teams; serial implementation; Application software; Computational modeling; Concurrent computing; Eigenvalues and eigenfunctions; Heuristic algorithms; Laplace equations; NP-hard problem; Partitioning algorithms; Topology; Workstations;

fLanguage

English

Publisher

ieee

Conference_Titel

System Sciences, 1996., Proceedings of the Twenty-Ninth Hawaii International Conference on ,

Conference_Location

Wailea, HI

Print_ISBN

0-8186-7324-9

Type

conf

DOI

10.1109/HICSS.1996.495510

Filename

495510