research-article

A Family of Provably Correct Algorithms for Exact Triangle Counting

Authors:

Tze Meng LowAuthors Info & Claims

Correctness'17: Proceedings of the First International Workshop on Software Correctness for HPC Applications

Pages 14 - 20

https://doi.org/10.1145/3145344.3145484

Published: 12 November 2017 Publication History

Abstract

In recent years, there has been renewed interest in casting graph algorithms in the language of linear algebra. By replacing the computations with appropriate operations over different semi-rings, different graph algorithms can be cast as a sequence of linear algebra operations. In this paper, we show that this recent trend allows us to leverage the Formal Linear Algebra Methods Environment (FLAME) methodology to formally specify, derive and implement a family of graph algorithms for counting the number of triangles (3-cliques) in a graph. In addition, we introduce a new back-end for the FLAME Application Programming Interface (API) that computes over sparse matrices stored in the compressed sparse row (CSR) format so that the correctness of the derived algorithm can be translated to the implementation.

References

[1]

2017. Graph Challenge. http://graphchallenge.mit.edu/. (2017).

[2]

Paolo Bientinesi, John A. Gunnels, Margaret E. Myers, Enrique S. Quintana-Ortí, Tyler Rhodes, Robert A. van de Geijn, and Field G. Van Zee. 2013. Deriving dense linear algebra libraries. Formal Aspects of Computing 25, 6 (01 Nov 2013), 933--945.

[3]

Paolo Bientinesi, John A. Gunnels, Margaret E. Myers, Enrique S. Quintana-Ortí, and Robert A. van de Geijn. 2005. The Science of Deriving Dense Linear Algebra Algorithms. ACM Trans. Math. Soft. 31, 1 (March 2005), 1--26. http://doi.acm.org/10.1145/1055531.1055532

Digital Library

[4]

Paolo Bientinesi, Enrique S. Quintana-Ortí, and Robert A. van de Geijn. 2005. Representing Linear Algebra Algorithms in Code: The FLAME Application Programming Interfaces. ACM Trans. Math. Soft. 31, 1 (March 2005), 27--59. http://doi.acm.org/10.1145/1055531.1055533

Digital Library

[5]

Aydin Buluç, Jeremy T Fineman, Matteo Frigo, John R Gilbert, and Charles E Leiserson. 2009. Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. ACM, 233--244.

Digital Library

[6]

Paul Burkhardt. 2016. Graphing trillions of triangles. Information Visualization (2016), 1473871616666393.

[7]

Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report 16 (2008).

[8]

E. W. Dijkstra. 1976. A discipline of programming. Prentice Hall.

[9]

Diego Fabregat-Traver and Paolo Bientinesi. 2013. A Domain-Specific Compiler for Linear Algebra Operations. Springer Berlin Heidelberg, Berlin, Heidelberg, 346--361.

[10]

John A. Gunnels, Fred G. Gustavson, Greg M. Henry, and Robert A. van de Geijn. 2001. FLAME: Formal Linear Algebra Methods Environment. ACM Trans. Math. Soft. 27, 4 (December 2001), 422--455. http://doi.acm.org/10.1145/504210.504213

Digital Library

[11]

C. A. R. Hoare. 1969. An axiomatic basis for computer programming. Commun. ACM (October 1969), 576--580.

Digital Library

[12]

Francisco D. Igual, Ernie Chan, Enrique S. Quintana-Ortí, Gregorio Quintana-Ortí, Robert A. Van De Geijn, and Field G. Van Zee. 2012. The FLAME Approach: From Dense Linear Algebra Algorithms to High-performance Multi-accelerator Implementations. J. Parallel Distrib. Comput. 72, 9 (September 2012), 1134--1143.

Digital Library

[13]

J. Kepner, P. Aaltonen, D. Bader, A. Bulu, F. Franchetti, J. Gilbert, D. Hutchison, M. Kumar, A. Lumsdaine, H. Meyerhenke, S. McMillan, C. Yang, J. D. Owens, M. Zalewski, T. Mattson, and J. Moreira. 2016. Mathematical foundations of the GraphBLAS. In 2016 IEEE High Performance Extreme Computing Conference (HPEC). 1--9.

[14]

Daniel J Lehmann. 1977. Algebraic structures for transitive closure. Theoretical Computer Science 4, 1 (1977), 59--76.

[15]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data. (June 2014).

[16]

Tze Meng Low. 2013. A calculus of loop invariants for dense linear algebra optimization. Ph.D. Dissertation. Department of Computer Sciences, The University of Texas.

[17]

Tze Meng Low, Robert A. van de Geijn, and Field G. Van Zee. 2005. Extracting SMP parallelism for dense linear algebra algorithms from high-level specifications. In Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP '05). ACM, New York, NY, USA, 153--163.

[18]

R. Duncan Luce and Albert D. Perry. 1949. A method of matrix analysis of group structure. Psychometrika 14, 2 (01 Jun 1949), 95--116.

[19]

OpenMP Architecture Review Board. 2015. OpenMP Application Program Interface. (November 2015). http://www.openmp.org/

[20]

Jack Poulson, Bryan Marker, Robert A. van de Geijn, Jeff R. Hammond, and Nichols A. Romero. 2013. Elemental: A New Framework for Distributed Memory Dense Matrix Computations. ACM Trans. Math. Softw. 39, 2, Article 13 (February 2013), 24 pages.

Digital Library

[21]

Richard Veras, Tze Meng Low, and Franz Franchetti. 2016. A scale-free structure for power-law graphs. In High Performance Extreme Computing Conference (HPEC), 2016 IEEE. IEEE, 1--7.

Cited By

van de Geijn RMyers M(2022)Applying Dijkstra’s Vision to Numerical SoftwareEdsger Wybe Dijkstra10.1145/3544585.3544597(215-230)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544597
Azad AAznaveh MBeamer SBlanco MChen JD'Alessandro LDathathri RDavis TDeweese KFiroz JGabb HGill GHegyi BKolodziej SLow TLumsdaine AManlaibaatar TMattson TMcMillan SPeri RPingali KSridhar USzarnyas GZhang YZhang Y(2020)Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite2020 IEEE International Symposium on Workload Characterization (IISWC)10.1109/IISWC50251.2020.00029(216-227)Online publication date: Oct-2020
https://doi.org/10.1109/IISWC50251.2020.00029
Blanco MMcMillan SLow T(2020)Towards an Objective Metric for the Performance of Exact Triangle Count2020 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC43674.2020.9286188(1-7)Online publication date: 22-Sep-2020
https://doi.org/10.1109/HPEC43674.2020.9286188

Index Terms

A Family of Provably Correct Algorithms for Exact Triangle Counting

Recommendations

The science of deriving dense linear algebra algorithms

In this article we present a systematic approach to the derivation of families of high-performance algorithms for a large set of frequently encountered dense linear algebra operations. As part of the derivation a constructive proof of the correctness of ...
Exact algorithms for dominating induced matching based on graph partition

A dominating induced matching, also called an efficient edge domination, of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F E of edges in the graph such that no two edges in F share a common endpoint and each edge in E F ...
Efficient algorithms for Roman domination on some classes of graphs

A Roman dominating function of a graph G=(V,E) is a function f:V->{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=@?"x"@?"Vf(x), and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Correctness'17: Proceedings of the First International Workshop on Software Correctness for HPC Applications

November 2017

55 pages

ISBN:9781450351270

DOI:10.1145/3145344

Copyright © 2017 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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 November 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SC '17

Sponsor:

SIGHPC

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

November 12 - 17, 2017

CO, Denver, USA

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
231
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

van de Geijn RMyers M(2022)Applying Dijkstra’s Vision to Numerical SoftwareEdsger Wybe Dijkstra10.1145/3544585.3544597(215-230)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544597
Azad AAznaveh MBeamer SBlanco MChen JD'Alessandro LDathathri RDavis TDeweese KFiroz JGabb HGill GHegyi BKolodziej SLow TLumsdaine AManlaibaatar TMattson TMcMillan SPeri RPingali KSridhar USzarnyas GZhang YZhang Y(2020)Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite2020 IEEE International Symposium on Workload Characterization (IISWC)10.1109/IISWC50251.2020.00029(216-227)Online publication date: Oct-2020
https://doi.org/10.1109/IISWC50251.2020.00029
Blanco MMcMillan SLow T(2020)Towards an Objective Metric for the Performance of Exact Triangle Count2020 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC43674.2020.9286188(1-7)Online publication date: 22-Sep-2020
https://doi.org/10.1109/HPEC43674.2020.9286188

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