Article

Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors

Authors:

David A. Bader,

Kamesh MadduriAuthors Info & Claims

HiPC'05: Proceedings of the 12th international conference on High Performance Computing

Pages 465 - 476

https://doi.org/10.1007/11602569_48

Published: 18 December 2005 Publication History

Abstract

Graph theoretic problems are representative of fundamental computations in traditional and emerging scientific disciplines like scientific computing and computational biology, as well as applications in national security. We present our design and implementation of a graph theory application that supports the kernels from the Scalable Synthetic Compact Applications (SSCA) benchmark suite, developed under the DARPA High Productivity Computing Systems (HPCS) program. This synthetic benchmark consists of four kernels that require irregular access to a large, directed, weighted multi-graph. We have developed a parallel implementation of this benchmark in C using the POSIX thread library for commodity symmetric multiprocessors (SMPs). In this paper, we primarily discuss the data layout choices and algorithmic design issues for each kernel, and also present execution time and benchmark validation results.

References

[1]

DARPA Information Processing Technology Office: High productivity computing systems project (2004) http://www.darpa.mil/ipto/programs/hpcs/.

[2]

Kepner, J., Koester, D.P., et al.: HPCS Scalable Synthetic Compact Application (SSCA) Benchmarks (2004) http://www.highproductivity.org/SSCABmks.htm.

[3]

Kepner, J., Koester, D.P., et al.: HPCS SSCA#2 Graph Analysis Benchmark Specifications v1.0. (2005)

[4]

Dongarra, J., Bunch, J., Moler, C., Stewart, G.: LINPACK Users' Guide. SIAM, Philadelphia, PA. (1979)

[5]

Bader, D., Sreshta, S., Weisse-Bernstein, N.: Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs). In Sahni, S., Prasanna, V., Shukla, U., eds.: Proc. 9th Int'l Conf. on High Performance Computing (HiPC 2002). Volume 2552 of Lecture Notes in Computer Science., Bangalore, India, Springer-Verlag (2002) 63-75

Digital Library

[6]

Bader, D.A., Cong, G.: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs). In: Proc. Int'l Parallel and Distributed Processing Symp. (IPDPS 2004), Santa Fe, NM (2004)

[7]

Bader, D.A., Cong, G.: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. In: Proc. Int'l Parallel and Distributed Processing Symp. (IPDPS 2004), Santa Fe, NM (2004)

[8]

Helman, D.R., JáJá, J.: Designing practical efficient algorithms for symmetric multiprocessors. In: Algorithm Engineering and Experimentation (ALENEX'99). Volume 1619 of Lecture Notes in Computer Science., Baltimore, MD, Springer-Verlag (1999) 37-56

Digital Library

[9]

Helman, D.R., JáJá, J.: Prefix computations on symmetric multiprocessors. Journal of Parallel and Distributed Computing 61 (2001) 265-278

Digital Library

[10]

Bader, D.A., Madduri, K.: Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors. Technical report, Georgia Instutite of Technology (2005)

[11]

Park, J., Penner, M., Prasanna, V.: Optimizing graph algorithms for improved cache performance. In: Proc. Int'l Parallel and Distributed Processing Symp. (IPDPS 2002), Fort Lauderdale, FL (2002)

Digital Library

[12]

Kernighan, B., Lin, S.: An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 49 (1970) 291-307

[13]

Sangiovanni-Vincentelli, A., Chert, L., Chua, L.: A new tearing approach: Node tearing nodal analysis. In: Proc. IEEE Int'l Symp. on Circ. and Syst., Phoenix, AZ (1975) 143-147

[14]

Sangiovanni-Vincentelli, A., Chert, L., Chua, L.: An efficient heuristic cluster algorithm for tearing large-scale networks. IEEE Trans. Circuits and Systems (1977) 709-717

[15]

Bomze, I., Budinich, M., Pardalos, P., Pelillo, M.: The maximum clique problem. In Du, D.Z., Pardalos, P.M., eds.: Handbook of Combinatorial Optimization. Volume 4. Kluwer Academic Publishers, Boston, MA (1999)

[16]

Johnson, D., Trick, M., eds.: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. Volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society (1996)

Digital Library

[17]

Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proc. Supercomputing '95, San Diego, CA (1995)

Digital Library

[18]

Karypis, G., Kumar, V.: MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Department of Computer Science, University of Minnesota. Version 4.0 edn. (1998)

[19]

Koester, D.P.: Parallel Block-Diagonal-Bordered Sparse Linear Solvers for Power Systems Applications. PhD thesis, Syracuse University, Syracuse, NY (1995)

Digital Library

Cited By

Suchert FCastrillon J(2022)STAMP-Rust: Language and Performance Comparison to C on Transactional BenchmarksBenchmarking, Measuring, and Optimizing10.1007/978-3-031-31180-2_10(160-175)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-31180-2_10
Besta MVonarburg-Shmaria ZSchaffner YSchwarz LKwasniewski GGianinazzi LBeranek JJanda KHolenstein TLeisinger STatkowski POzdemir EBalla ACopik MLindenberger PKonieczny MMutlu OHoefler T(2021)GraphMineSuiteProceedings of the VLDB Endowment10.14778/3476249.347625214:11(1922-1935)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.14778/3476249.3476252
Dhulipala LShi JTseng TBlelloch GShun J(2020)The Graph Based Benchmark Suite (GBBS)Proceedings of the 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3398682.3399168(1-8)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3398682.3399168
Show More Cited By

Recommendations

A Benchmark Parallel Sort for Shared Memory Multiprocessors

The first parallel sort algorithm for shared memory MIMD (multiple-instruction-multiple-data-stream) multiprocessors that has a theoretical and measured speedup near linear is exhibited. It is based on a novel asynchronous parallel merge that evenly ...
Scalable real-time parallel garbage collection for symmetric multiprocessors
Subsetting the SPEC CPU2006 benchmark suite

On August 24, 2006, the Standard Performance Evaluation Corporation (SPEC) announced CPU2006 -- the next generation of industry-standardized CPU-intensive benchmark suite. The SPEC CPU benchmark suite has become the most frequently used suite for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

HiPC'05: Proceedings of the 12th international conference on High Performance Computing

December 2005

548 pages

ISBN:3540309365

Editors:
David A. Bader
College of Computing, Georgia Institute of Technology, Atlanta, GA
,
Manish Parashar
Department of Electrical and Computer Engineering, Rutgers, the State University of New Jersey, 94 Brett Road, Piscataway, NJ
,
Varadarajan Sridhar
Satyam Computer Services Ltd., Indian Institute of Science Campus, Entrepreneurship Centre, SID Block, Bangalore, NJ, India
,
Viktor K. Prasanna
Department of Electrical Engineering, University of Southern California, SID Block, Los Angeles, CA, India

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 December 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Suchert FCastrillon J(2022)STAMP-Rust: Language and Performance Comparison to C on Transactional BenchmarksBenchmarking, Measuring, and Optimizing10.1007/978-3-031-31180-2_10(160-175)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-31180-2_10
Besta MVonarburg-Shmaria ZSchaffner YSchwarz LKwasniewski GGianinazzi LBeranek JJanda KHolenstein TLeisinger STatkowski POzdemir EBalla ACopik MLindenberger PKonieczny MMutlu OHoefler T(2021)GraphMineSuiteProceedings of the VLDB Endowment10.14778/3476249.347625214:11(1922-1935)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.14778/3476249.3476252
Dhulipala LShi JTseng TBlelloch GShun J(2020)The Graph Based Benchmark Suite (GBBS)Proceedings of the 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3398682.3399168(1-8)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3398682.3399168
Anand VMehrotra PMargo DSeltzer M(2020)Smooth KroneckerProceedings of the 3rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3398682.3399161(1-10)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3398682.3399161
Hou JWang SWu GMa BZhang L(2020)Parallel SCC Detection Based on Reusing Warps and Coloring Partitions on GPUsAlgorithms and Architectures for Parallel Processing10.1007/978-3-030-60245-1_3(31-46)Online publication date: 2-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-60245-1_3
Wang XTumeo ALeidel JLi JChen Y(2019)MACProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337867(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337867
Saad MPalmieri RRavindran B(2019)LernaACM Transactions on Storage10.1145/331036815:1(1-24)Online publication date: 22-Mar-2019
https://dl.acm.org/doi/10.1145/3310368
Wang QSu PChabbi MLiu XHollingsworth JKeidar I(2019)Lightweight hardware transactional memory profilingProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295728(186-200)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295728
Hou JWang SWu GFu GJia SWang YLi BZhang L(2019)Parallel Strongly Connected Components Detection with Multi-partition on GPUsComputational Science – ICCS 201910.1007/978-3-030-22747-0_2(16-30)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-22747-0_2
Chatarasi PSarkar V(2018)A Preliminary Study of Compiler Transformations for Graph Applications on the Emu SystemProceedings of the Workshop on Memory Centric High Performance Computing10.1145/3286475.3286481(37-44)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1145/3286475.3286481
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents