10.2 Special Session: Enabling Graph Analytics at Extreme Scales: Design Challenges, Advances, and Opportunities

Printer-friendly version PDF version

Date: Thursday, March 28, 2019
Time: 11:00 - 12:30
Location / Room: Room 2

Ananth Kalyanaraman, Washington State University, US, Contact Ananth Kalyanaraman

Partha Pande, Washington State University, US, Contact Partha Pande

A hot topic special session on enabling extreme scale graph analytics using innovations in algorithms and architectures is proposed. The special session will host three talks by speakers who work at the intersection of graph analytics and high performance computing. Through these talks, the session will cover the spectrum of unique challenges, latest advances, and exciting opportunities for research and development that exist in this emerging research area. The special session will serve as an avenue for discussion of recent advances that have started to show that graph analytics and computer architecture are capable of benefiting from one another and spawning new research directions. The goal is to build a new vibrant community at the intersection of graph analytics and HPC architecture, by fostering an environment conducive to active engagement and exchange of ideas between the two groups.

TimeLabelPresentation Title
Ananth Kalyanaraman, Washington State University, US
Ananth Kalyanaraman and Partha Pratim Pande, Washington State University, US
The notion of networks is inherent in the structure, function and behavior of the natural and engineered world that surround us. Consequently, graph models and methods have assumed a prominent role to play in this modern era of Big Data, and are taking a center stage in the discovery pipelines of various data-driven scientific domains. In this paper, we present a brief review of the state-of-the-art in parallel graph analytics, particularly focusing on iterative graph algorithms and their implementation on modern day manycore architectures. The class of iterative graph algorithms covers a broad class of graph operations of varying complexities, from simpler routines such as Breadth-First Search (BFS), to polynomially-solvable problems such as shortest path computations, to NP-Hard problems such as community detection and graph coloring. We cover a set of common algorithmic abstractions used in implementing such iterative graph algorithms, state the challenges around parallelization on contemporary parallel platforms (including commodity multicores and emerging manycore platforms), and describe a set of approaches that have led to efficient implementations. We conclude the paper identifying potential research directions, opportunities, and challenges that lay ahead in the path toward enabling graph analytics at exascale

Download Paper (PDF; Only available from the DATE venue WiFi)
John Feo, Pacific Northwest National Laboratory, US
Vito Giovanni Castellana, Maurizio Drocco, John Feo, Andrew Lumsdaine, Joseph Manzano, Andres Marquez, Marco Minutoli, Joshua Suetterlein, Antonino Tumeo and Marcin Zalewski, Pacific Northwest National Laboratory, US
Economic competitiveness and national security depend increasingly on the insightful analysis of large data sets. The diversity of real-world data sources and analytic workflows impose challenging hardware and software requirements for parallel graph platforms. The irregular nature of graph methods is not supported well by the deep memory hierarchies of conventional distributed systems, requiring new processor and runtime system designs to tolerate memory and synchronization latencies. Moreover, the efficiency of relational table operations and matrix computations are not attainable when data is stored in common graph data structures. In this paper, we present HAGGLE, a high-performance, scalable data analytic platform. The platform's hybrid data model supports a variety of distributed, thread-safe data structures, parallel programming constructs, and persistent and streaming data. An abstract runtime layer enables us to map the stack to conventional, distributed computer systems with accelerators. The runtime uses multithreading, active messages, and data aggregation to hide memory and synchronization latencies on large-scale systems.

Download Paper (PDF; Only available from the DATE venue WiFi)
Henning Meyerhenke, Humboldt-University Berlin, DE
Henning Meyerhenke and Alexander van der Grinten, Humboldt-University Berlin, DE
Network science methodology is increasingly applied to study various real-world phenomena. Consequently, large network data sets comprising millions or billions of edges are more and more common. In order to process and analyze such massive graphs, we need appropriate graph processing systems and fast algorithms. Yet, many analysis algorithms have been pioneered on small networks, where speed was not the highest concern. Developing an analysis toolkit for large-scale networks thus often requires faster variants, both from an algorithmic and from an implementation point of view. In this paper we focus on computational aspects of network centrality measures. Such measures indicate the importance of a vertex (or an edge) based on the position of the vertex (or the edge) in the network. We describe several common measures as well as algorithms for computing them. This description focuses on three aspects: (i) our recent contributions to the field, (ii) new results regarding Katz centrality, and (iii) future work from a lower-level implementation point of view.

Download Paper (PDF; Only available from the DATE venue WiFi)
12:30End of session
Lunch Break in Lunch Area

Coffee Breaks in the Exhibition Area

On all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area.

Lunch Breaks (Lunch Area)

On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the Lunch Area to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area.

Tuesday, March 26, 2019

Wednesday, March 27, 2019

Thursday, March 28, 2019