More Web Proxy on the site http://driver.im/

Article

A hypergraph-partitioning approach for coarse-grain decomposition

Authors:

Umit Catalyurek,

Cevdet AykanatAuthors Info & Claims

SC '01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing

Page 28

https://doi.org/10.1145/582034.582062

Published: 10 November 2001 Publication History

Abstract

We propose a new two-phase method for the coarse-grain decomposition of irregular computational domains. This work focuses on the 2D partitioning of sparse matrices for parallel matrix-vector multiplication. However, the proposed model can also be used to decompose computational domains of other parallel reduction problems. This work also introduces the use of multi-constraint hypergraph partitioning, for solving the decomposition problem. The proposed method explicitly models the minimization of communication volume while enforcing the upper bound of p + q --- 2 on the maximum number of messages handled by a single processor, for a parallel system with P = p × q processors. Experimental results on a wide range of realistic sparse matrices confirm the validity of the proposed methods, by achieving up to 25 percent better partitions than the standard graph model, in terms of total communication volume, and 59 percent better partitions in terms of number of messages, on the overall average.

References

[1]

A. Afework, M. D. Beynon, F. Bustamante, A. Demarzo, R. Ferreira, R. Miller, M. Silberman, J. Saltz, A. Sussman, and H. Tsang. Digital dynamic telepathology --- the Virtual Microscope. In Proceedings of the 1998 AMIA Annual Fall Symposium. American Medical Informatics Association, Nov. 1998.

[2]

T. Bultan and C. Aykanat. A new mapping heuristic based on mean field annealing. Journal of Parallel and Distributed Computing, 16:292-305, 1992.

[3]

W. Camp, S. J. Plimpton, B. Hendrickson, and R. W. Leland. Massively parallel methods for engineering and science problems. Communication of ACM, 37(4):31-41, April 1994.

Digital Library

[4]

W. J. Carolan, J. E. Hill, J. L. Kennington, S. Niemi, and S. J. Wichmann. An empirical evaluation of the korbx algorithms for military airlift applications. Operations Research, 38(2):240-248, 1990.

Digital Library

[5]

U. V. Çatalyürek. Hypergraph Models for Sparse Matrix Partitioning and Reordering. PhD thesis, Bilkent University, Computer Engineering and Information Science, Nov 1999.

[6]

U. V. Çatalyürek and C. Aykanat. Decomposing irregularly sparse matrices for parallel matrix-vector multiplications. Lecture Notes in Computer Science, 1117:75-86, 1996.

Digital Library

[7]

U. V. Çatalyürek and C. Aykanat. Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693, 1999.

Digital Library

[8]

U. V. Çatalyürek and C. Aykanat. PaToH: A Multilevel Hypergraph Partitioning Tool, Version 3.0. Bilkent University, Department of Computer Engineering, Ankara, 06533 Turkey, 1999.

[9]

U. V. Çatalyürek and C. Aykanat. A fine-grain hypergraph model for 2D decomposition of sparse matrices. In Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, April 2001.

Digital Library

[10]

I. O. Center. Linear programming problems. ftp://col.biz.uiowa.edu:pub/testprob/lp/gondzio.

[11]

C. F. Cerco and T. Cole. User's guide to the CE-QUAL-ICM three-dimensional eutrophication model, release version 1.0. Technical Report EL-95-15, US Army Corps of Engineers Water Experiment Station, Vicksburg, MS, 1995.

[12]

C. Chang, A. Acharya, A. Sussman, and J. Saltz. T2: A customizable parallel database for multi-dimensional data. ACM SIGMOD Record, 27(1):58-66, Mar. 1998.

Digital Library

[13]

C. Chang, T. Kurc, A. Sussman, U. V. Çatalyürek, and J. Saltz. A hypergraph-based workload partitioning strategy for parallel data aggregation. In Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Mar. 2001.

[14]

T. Davis. University of florida sparse matrix collection: http://www.cise.ufl.edu/davis/sparse/. NA Digest, 92/96/97(42/28/23), 1994/1996/1997.

[15]

I. S. Duff, R. Grimes, and J. Lewis. Sparse matrix test problems. ACM Transactions on Mathematical Software, 15(1):1-14, march 1989.

Digital Library

[16]

B. Hendrickson. Graph partitioning and parallel solvers: has the emperor no clothes? Lecture Notes in Computer Science, 1457:218-225, 1998.

Digital Library

[17]

B. Hendrickson and T. G. Kolda. Graph partitioning models for parallel computing. Parallel Computing, 26:1519-1534, 2000.

Digital Library

[18]

B. Hendrickson, R. Leland, and S. Plimpton. An efficient parallel algorithm for matrix-vector multiplication. Int. J. High Speed Computing, 7(1):73-88, 1995.

[19]

M. Kaddoura, C. W. Qu, and S. Ranka. Partitioning unstructured computational graphs for nonuniform and adaptive environments. IEEE Parallel and Distributed Technology, 3(3):63-69, 1995.

Digital Library

[20]

G. Karypis and V. Kumar. MeTiS A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0. University of Minnesota, Department of Comp. Sci. and Eng., Army HPC Research Center, Minneapolis, 1998.

[21]

G. Karypis and V. Kumar. Multilevel algorithms for multi-constraint graph partitioning. Technical Report 98-019, University of Minnesota, Department of Computer Science/Army HPC Research Center, Minneapolis, MN 55455, May 1998.

[22]

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, to appear.

Digital Library

[23]

V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings Publishing Company, Redwood City, CA, 1994.

Digital Library

[24]

T. Kurc, C. Chang, R. Ferreira, A. Sussman, and J. Saltz. Querying very large multi-dimensional datasets in ADR. In Proceedings of the 1999 ACM/IEEE SC99 Conference. ACM Press, Nov. 1999.

Digital Library

[25]

V. Lakamsani, L. N. Bhuyan, and D. S. Linthicum. Mapping molecular dynamics computations on to hypercubes. Parallel Computing, 21:993-1013, 1995.

Digital Library

[26]

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Willey-Teubner, Chichester, U.K., 199.

Digital Library

[27]

J. G. Lewis, D. G. Payne, and R. A. van de Geijn. Matrix-vector multiplication and conjugate gradient algorithms on distributed memory computers. In Proceedings of the Scalable High Performance Computing Conference, 1994.

[28]

J. G. Lewis and R. A. van de Geijn. Distributed memory matrix-vector multiplication and conjugate gradient algorithms. In Proceedings of Supercomputing '93, pages 15-19, Portland, OR, November 1993.

Digital Library

[29]

R. A. Luettich, J. J. Westerink, and N. W. Scheffner. ADCIRC: An advanced three-dimensional circulation model for shelves, coasts, and estuaries. Technical Report 1, Department of the Army, U.S. Army Corps of Engineers, Washington, D.C. 20314-1000, December 1991.

[30]

O. C. Martin and S. W. Otto. Partitioning of unstructured meshes for load balancing. Concurrency: Practice and Experience, 7(4):303-314, 1995.

[31]

The Moderate Resolution Imaging Spectrometer. http://ltpwww.gsfc.nasa.gov/MODIS/MODIS.html.

[32]

NASA Goddard Distributed Active Archive Center (DAAC). Advanced Very High Resolution Radiometer Global Area Coverage (AVHRR GAC) data. http://daac.gsfc.nasa.gov/CAMPAIGN_DOCS/LAND_BIO/origins.html.

[33]

A. T. Ogielski and W. Aielo. Sparse matrix computations on parallel processor arrays. SIAM Journal on Numerical Analysis, 1993.

Digital Library

[34]

C.-W. Qu and S. Ranka. Parallel incremental graph partitioning. IEEE Transactions on Parallel and Distributed Systems, 8(8):884-896, 1997.

Digital Library

[35]

K. Schloegel, G. Karypis, and V. Kumar. A new algorithm for multi-objective graph partitioning. Technical Report 99-003, University of Minnesota, Department of Computer Science/Army HPC Research Center, Minneapolis, MN 55455, Sep 1999.

[36]

T. Tanaka. Configurations of the solar wind flow and magnetic field around the planets with no magnetic field: calculation by a new MHD. Journal of Geophysical Research, 98(A10):17251-62, Oct 1993.

[37]

U.S. Geological Survey. Land satellite (LANDSAT) thematic mapper (TM). http://edcwww.cr.usgs.gov/nsdi/html/landsat_tm/landsat_tm.

Cited By

Gottesbüren LHeuer TMaas NSanders PSchlag S(2024)Scalable High-Quality Hypergraph PartitioningACM Transactions on Algorithms10.1145/362652720:1(1-54)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3626527
Dapena DLau DArce G(2023)Parallel Graph Signal Processing: Sampling and ReconstructionIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2023.32615049(190-206)Online publication date: 2023
https://doi.org/10.1109/TSIPN.2023.3261504
Çeliktuğ MKarsavuran MAcer SAykanat C(2022)Simultaneous Computational and Data Load Balancing in Distributed-Memory SettingSIAM Journal on Scientific Computing10.1137/22M148577244:6(C399-C424)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/22M1485772
Show More Cited By

Index Terms

A hypergraph-partitioning approach for coarse-grain decomposition
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Hypergraphs
  2. Mathematical analysis
    1. Differential equations
      1. Partial differential equations

Recommendations

Parallel hypergraph partitioning for scientific computing
IPDPS'06: Proceedings of the 20th international conference on Parallel and distributed processing

Graph partitioning is often used for load balancing in parallel computing, but it is known that hypergraph partitioning has several advantages. First, hypergraphs more accurately model communication volume, and second, they are more expressive and can ...
Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication

In this work, we show that the standard graph-partitioning-based decomposition of sparse matrices does not reflect the actual communication volume requirement for parallel matrix-vector multiplication. We propose two computational hypergraph models ...
Parallelizing Image Feature Extraction on Coarse-Grain Machines

In this paper, we present a fast parallel algorithm for feature extraction on coarse-grain MIMD machines. By maintaining algorithmic threads at each node, our algorithm enhances processor utilization and obtains large speed-ups. Our implementations show ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '01: Proceedings of the 2001 ACM/IEEE conference on Supercomputing

November 2001

756 pages

ISBN:158113293X

DOI:10.1145/582034

Conference Chair:
Charles Slocomb
Los Alamos National Laboratory

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '01

Sponsor:

SIGARCH
IEEE-CS

SC '01: International Conference for High Performance Computing, Networking, Storage and Analysis

November 10 - 16, 2001

Colorado, Denver

Acceptance Rates

SC '01 Paper Acceptance Rate 60 of 240 submissions, 25%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
509
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gottesbüren LHeuer TMaas NSanders PSchlag S(2024)Scalable High-Quality Hypergraph PartitioningACM Transactions on Algorithms10.1145/362652720:1(1-54)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3626527
Dapena DLau DArce G(2023)Parallel Graph Signal Processing: Sampling and ReconstructionIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2023.32615049(190-206)Online publication date: 2023
https://doi.org/10.1109/TSIPN.2023.3261504
Çeliktuğ MKarsavuran MAcer SAykanat C(2022)Simultaneous Computational and Data Load Balancing in Distributed-Memory SettingSIAM Journal on Scientific Computing10.1137/22M148577244:6(C399-C424)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/22M1485772
Dautov RDistefano S(2022)Stream Processing on Clustered Edge DevicesIEEE Transactions on Cloud Computing10.1109/TCC.2020.298340210:2(885-898)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TCC.2020.2983402
Han DNam YLee JPark KKim HKim MBoncz PManegold SAilamaki ADeshpande AKraska T(2019)DistMEProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319865(759-774)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319865
Demirci GAykanat C(2019)Scaling sparse matrix-matrix multiplication in the accumulo databaseDistributed and Parallel Databases10.1007/s10619-019-07257-yOnline publication date: 28-Jan-2019
https://doi.org/10.1007/s10619-019-07257-y
Selvitopi OAcer SAykanat C(2017)A Recursive Hypergraph Bipartitioning Framework for Reducing Bandwidth and Latency Costs SimultaneouslyIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.257702428:2(345-358)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2577024
Acer SSelvitopi OAykanat C(2017)Addressing Volume and Latency Overheads in 1D-parallel Sparse Matrix-Vector MultiplicationEuro-Par 2017: Parallel Processing10.1007/978-3-319-64203-1_45(625-637)Online publication date: 1-Aug-2017
https://doi.org/10.1007/978-3-319-64203-1_45
(2016)Reducing latency cost in 2D sparse matrix partitioning modelsParallel Computing10.1016/j.parco.2016.04.00457:C(1-24)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.parco.2016.04.004
Buluç AMeyerhenke HSafro ISanders PSchulz C(2016)Recent Advances in Graph PartitioningAlgorithm Engineering10.1007/978-3-319-49487-6_4(117-158)Online publication date: 11-Nov-2016
https://doi.org/10.1007/978-3-319-49487-6_4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents