ALAndrew Lumsdaine

Andrew Lumsdaine

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

    by Xu T. Liu, Andrew Lumsdaine, Mahantesh Halappanavar, Kevin Barker, Assefaw H. Gebremedhin

    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.


  • Introduction to GraphBLAS

    by Jeremy Kepner, Peter Aaltonen, David Bader, Aydin Buluc, Franz Franchetti, John Gilbert, Shana Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, et al.

    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

    Scalable Second Order Optimization for Machine Learning

    by Andrew Lumsdaine

    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.

  • NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

    by Andrew Lumsdaine, Jesun S. Firoz, Joseph B. Manzano Franco, Andres Marquez, Joshua D. Suetterlein, Marcin J. Zalewski, Xu Liu

    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.


  • Open Access

    Importance of Runtime Considerations in Performance Engineering of Large-Scale Distributed Graph Algorithms

    by Jesun Sahariar Firoz, Thejaka Amila Kanewala, Marcin Zalewski, Martina Barnas, Andrew Lumsdaine


  • Comparison of Single Source Shortest Path Algorithms on Two Recent Asynchronous Many-task Runtime Systems

    by Jesun Sahariar Firoz, Martina Barnas, Marcin Zalewski, Andrew Lumsdaine

    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?

    by Michael Hansen, Robert L. Goldstone, Andrew Lumsdaine

    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

    Introduction to the JEI Focal Track Presentations

    by Todor Georgiev, Andrew Lumsdaine

  • Open Access

    Special Section Guest Editorial: Mobile Computational Photography

    by Todor Georgiev, Andrew Lumsdaine, Sergio Goma

    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.