Andrew Lumsdaine
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Andrew Lumsdaine has a total of 58 co-authors. Here are the top co-authors by number of shared publications:
- Robert Stevenson
University of Notre Dame, Department of Electrical Engineering, Notre Dame, Indiana
3 shared publications - Torsten Hoefler
Open Systems Laboratory , Indiana University , 501 N. Morton Street, Bloomington, IN, 47404, USA
3 shared publications - Jesun Sahariar Firoz
Pacific Northwest National Laboratory
2 shared publications Marcin Zalewski
2 shared publications- Timo Schneider
ETH Zurich, Zurich, Switzerland
2 shared publications - Timo Schneider
Open Systems Laboratory , Indiana University , 501 N. Morton Street, Bloomington, IN, 47404, USA
2 shared publications
Latest Publications
- Open Access
- 13 December 2022
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 27, 1-31
Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis
Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.
- 13 December 2022
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 27, 1-31
Open AccessDirection-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis
Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.
- 26 May 2022
- Published by Taylor & Francis
- p. 507-524
Introduction to GraphBLAS
508Graphs are powerful tools for modeling complex problems because of their simplicity and generality [Staudt et al. 2016, Bergamini & Meyerhenke 2016]. For this reason, the field of graph algorithms has become one of the pillars of theoretical computer science, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Graph algorithms have been adapted and implemented by the military, commercial industry, and researchers in academia, and have become essential in controlling the power grid, telephone systems, and, of course, computer networks. Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to applications in bioinformatics [Georganas et al. 2014], computer networks, and social media [Ediger et al. 2010, Ediger et al. 2011, Riedy et al. 2012, Riedy & Bader 2013]. Parallel graph algorithms are notoriously difficult to implement and optimize [Ediger et al. 2012, Ediger & Bader 2013, McLaughlin & Bader 2014a, McLaughlin & Bader 2014b, McLaughlin et al. 2014, Staudt & Meyerhenke 2016]. The irregular data access patterns and inherently high communication-to-computation ratios found in graph algorithms mean that even the best algorithms will have parallel efficiencies that decrease as the number of processors is increased [Buluç & Gilbert 2012, Azad et al. 2015]. Recent work on communication-avoiding algorithms, and their applications to graph computations [Ballard et al. 2013, Solomonik et al. 2013], might defer but not completely eliminate the parallel scalability bottleneck. Consequently, novel hardware architectures will also be required 509[Song et al. 2010, Song et al. 2013]. A common graph processing interface provides a useful tool for optimizing both software and hardware to provide high performance graph applications.
- 26 May 2022
- Published by Taylor & Francis
- p. 507-524
Introduction to GraphBLAS
508Graphs are powerful tools for modeling complex problems because of their simplicity and generality [Staudt et al. 2016, Bergamini & Meyerhenke 2016]. For this reason, the field of graph algorithms has become one of the pillars of theoretical computer science, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Graph algorithms have been adapted and implemented by the military, commercial industry, and researchers in academia, and have become essential in controlling the power grid, telephone systems, and, of course, computer networks. Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to applications in bioinformatics [Georganas et al. 2014], computer networks, and social media [Ediger et al. 2010, Ediger et al. 2011, Riedy et al. 2012, Riedy & Bader 2013]. Parallel graph algorithms are notoriously difficult to implement and optimize [Ediger et al. 2012, Ediger & Bader 2013, McLaughlin & Bader 2014a, McLaughlin & Bader 2014b, McLaughlin et al. 2014, Staudt & Meyerhenke 2016]. The irregular data access patterns and inherently high communication-to-computation ratios found in graph algorithms mean that even the best algorithms will have parallel efficiencies that decrease as the number of processors is increased [Buluç & Gilbert 2012, Azad et al. 2015]. Recent work on communication-avoiding algorithms, and their applications to graph computations [Ballard et al. 2013, Solomonik et al. 2013], might defer but not completely eliminate the parallel scalability bottleneck. Consequently, novel hardware architectures will also be required 509[Song et al. 2010, Song et al. 2013]. A common graph processing interface provides a useful tool for optimizing both software and hardware to provide high performance graph applications.
- Open Access
- 1 May 2022
- Published by Office of Scientific and Technical Information (OSTI)
Scalable Second Order Optimization for Machine Learning
Many machine learning (ML) training tasks are essentially optimization processes that would at first glance appear eminently parallelizable and scalable. However, effective acceleration of these tasks with scalable parallel hardware has proven to be elusive. While standard methods for machine learning, e.g., stochastic gradient descent (SGD) for DNNs, tend to be resource efficient, they appear to be fundamentally sequential in nature.
- 1 May 2022
- Published by Office of Scientific and Technical Information (OSTI)
Open AccessScalable Second Order Optimization for Machine Learning
Many machine learning (ML) training tasks are essentially optimization processes that would at first glance appear eminently parallelizable and scalable. However, effective acceleration of these tasks with scalable parallel hardware has proven to be elusive. While standard methods for machine learning, e.g., stochastic gradient descent (SGD) for DNNs, tend to be resource efficient, they appear to be fundamentally sequential in nature.
- 1 September 2021
- Published by Office of Scientific and Technical Information (OSTI)
NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20
The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. With the new addition of ranges and concepts in C++20, the language has the mechanisms to cleanly support generic graph algorithms as operations on a range of ranges. This report presents NWGraph, a generic C++ graph library for expressing graph algorithms in a modern, composable, and extensible, aka generic, fashion.
- 1 September 2021
- Published by Office of Scientific and Technical Information (OSTI)
NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20
The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. With the new addition of ranges and concepts in C++20, the language has the mechanisms to cleanly support generic graph algorithms as operations on a range of ranges. This report presents NWGraph, a generic C++ graph library for expressing graph algorithms in a modern, composable, and extensible, aka generic, fashion.
- 1 December 2016
- Published by Elsevier in Journal of Computational and Applied Mathematics
- Vol. 308, 98-116
Matrix-free Krylov iteration for implicit convolution of numerically low-rank data
- 1 December 2016
- Published by Elsevier in Journal of Computational and Applied Mathematics
- Vol. 308, 98-116
Matrix-free Krylov iteration for implicit convolution of numerically low-rank data
- Open Access
- 18 December 2015
- Published by Springer Nature
- p. 553-564
Importance of Runtime Considerations in Performance Engineering of Large-Scale Distributed Graph Algorithms
- 18 December 2015
- Published by Springer Nature
- p. 553-564
Open AccessImportance of Runtime Considerations in Performance Engineering of Large-Scale Distributed Graph Algorithms
- 1 December 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 674-681
Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems
With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.
- 1 December 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 674-681
Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems
With the advent of the exascale era, new runtimes and algorithm design techniques need to be explored. In this paper, we investigate performance of three different single-source shortest path algorithms in two relatively recent asynchronous many-task runtime systems AM++ and HPX-5. We identify the underlying set of differential features for these runtimes, and we compare and contrast the performance of Δ-stepping algorithm, Distributed Control based algorithm, K-level Asynchronous algorithm in AM++ and in HPX-5, for which we also include chaotic implementation. We observe that specific runtime characteristics or lack thereoff and different graph inputs can impact the feasibility of an algorithmic approach.
- Open Access
What Makes Code Hard to Understand?
What factors impact the comprehensibility of code? Previous research suggests that expectation-congruent programs should take less time to understand and be less prone to errors. We present an experiment in which participants with programming experience predict the exact output of ten small Python programs. We use subtle differences between program versions to demonstrate that seemingly insignificant notational changes can have profound effects on correctness and response times. Our results show that experience increases performance in most cases, but may hurt performance significantly when underlying assumptions about related code statements are violated.
Open AccessWhat Makes Code Hard to Understand?
What factors impact the comprehensibility of code? Previous research suggests that expectation-congruent programs should take less time to understand and be less prone to errors. We present an experiment in which participants with programming experience predict the exact output of ten small Python programs. We use subtle differences between program versions to demonstrate that seemingly insignificant notational changes can have profound effects on correctness and response times. Our results show that experience increases performance in most cases, but may hurt performance significantly when underlying assumptions about related code statements are violated.
- Open Access
- 26 February 2013
- Published by SPIE-Intl Soc Optical Eng
- p. 866701-866701-2
Introduction to the JEI Focal Track Presentations
- 26 February 2013
- Published by SPIE-Intl Soc Optical Eng
- p. 866701-866701-2
Open AccessIntroduction to the JEI Focal Track Presentations
- Open Access
- 1 January 2013
- Published by SPIE-Intl Soc Optical Eng in Journal of Electronic Imaging
- Vol. 22 (1) , 010901
Special Section Guest Editorial: Mobile Computational Photography
For many photographers today, mobile photography is photography. According to statistics available on the photo-sharing site CrossRef[[XSLOpenURL/]], over the last year the most popular camera used to take photos on the site has been an Apple iPhone. In fact, during the summer of 2012, the iPhone 4 and the iPhone 4S occupied the number one and number two spots. The success of mobile photography perhaps goes hand in glove with the rise of social networking sites. Mobile photography has enabled any individual with a cell phone (the ubiquitous mobile camera) to quickly and easily share visual images of their lives. Mobile cameras are cheap, small, lightweight, and connected—pictures can be taken anytime and anywhere—and shared immediately.
- 1 January 2013
- Published by SPIE-Intl Soc Optical Eng in Journal of Electronic Imaging
- Vol. 22 (1) , 010901
Open AccessSpecial Section Guest Editorial: Mobile Computational Photography
For many photographers today, mobile photography is photography. According to statistics available on the photo-sharing site CrossRef[[XSLOpenURL/]], over the last year the most popular camera used to take photos on the site has been an Apple iPhone. In fact, during the summer of 2012, the iPhone 4 and the iPhone 4S occupied the number one and number two spots. The success of mobile photography perhaps goes hand in glove with the rise of social networking sites. Mobile photography has enabled any individual with a cell phone (the ubiquitous mobile camera) to quickly and easily share visual images of their lives. Mobile cameras are cheap, small, lightweight, and connected—pictures can be taken anytime and anywhere—and shared immediately.