Title :
A parallel implementation of MRSB
Author :
Barnard, Stephen T.
Author_Institution :
Cray Res. Inc., Sunnyvale, CA, USA
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;
Conference_Titel :
System Sciences, 1996., Proceedings of the Twenty-Ninth Hawaii International Conference on ,
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-7324-9
DOI :
10.1109/HICSS.1996.495510
