Actions for HARP : A Dynamic Inertial Spectral Partitioner

Email RIS file
Bookmark
Report an Issue

HARP : A Dynamic Inertial Spectral Partitioner

Author
Simon, Horst D.
Published
Jun. 25, 1997.
Physical Description
1 electronic document
Additional Creators
Sohn, Andrew and Biswas, Rupak
Online Version

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Unclassified, Unlimited, Publicly available.
Free-to-read Unrestricted online access
Summary
Partitioning unstructured graphs is central to the parallel solution of computational science and engineering problems. Spectral partitioners, such recursive spectral bisection (RSB), have proven effecfive in generating high-quality partitions of realistically-sized meshes. The major problem which hindered their wide-spread use was their long execution times. This paper presents a new inertial spectral partitioner, called HARP. The main objective of the proposed approach is to quickly partition the meshes at runtime in a manner that works efficiently for real applications in the context of distributed-memory machines. The underlying principle of HARP is to find the eigenvectors of the unpartitioned vertices and then project them onto the eigerivectors of the original mesh. Results for various meshes ranging in size from 1000 to 100,000 vertices indicate that HARP can indeed partition meshes rapidly at runtime. Experimental results show that our largest mesh can be partitioned sequentially in only a few seconds on an SP2 which is several times faster than other spectral partitioners while maintaining the solution quality of the proven RSB method. A parallel WI version of HARP has also been implemented on IBM SP2 and Cray T3E. Parallel HARP, running on 64 processors SP2 and T3E, can partition a mesh containing more than 100,000 vertices into 64 subgrids in about half a second. These results indicate that graph partitioning can now be truly embedded in dynamically-changing real-world applications.
Other Subject(s)
Collection
NASA Technical Reports Server (NTRS) Collection.
Note
Document ID: 19970022762.
Accession ID: 97N23212.
RIACS-TR-97-01.
NASA-CR-204489.
NAS 1.26:204489.
Parallel Algorithms and Architectures; 22-25 Jun. 1997; Newport, RI; United States.
Terms of Use and Reproduction
No Copyright.
View MARC record | catkey: 15647901