The workshop is intended to promote an open discussion of a large-scale graph processing on modern HPC systems. The main task of the workshop is to bring attention of the  HPC community to this topic and discuss further steps on advancing  parallel graph processing. The workshop is a complementary to the GraphHPC conference.

The workshop will be held on September, 26^th from 14:10 till 15:50.

Agenda

Parallel decomposition of distributed graph
N. Starostin, A. Filimonov, Nizhniy Novgorod State University

We consider canonical graph k-decomposition problem. A parallel algorithm exploiting multilevel paradigm is suggested. The algorithm is designed to perform in distributed memory architectures due to novel in-site heuristics. The implementation is compared with state-of-the-art ParMetis algorithm.

Technology of solving large-scale graph problems for heterogeneous platforms
I. Afanasyev, V. Voevodin, A. Daryin, J. Dongarra, D. Nikitenko, A. Teplov, Lomonosov Moscow State University / Yandex Technology GmbH

The talk introduces technology for solving various large-scale graph problems on hybrid architectures. The following problems have been selected to illustrate the proposed approach: minimum spanning tree search and shortest paths computation. A precise mathematical description accompanied with information structure of required algorithms is provided. An efficient parallel implementation for several graph algorithms is proposed based on this analysis. Hybrid calculation allows using all the available resources - both multi-core CPUs and GPUs. Current implementation uses out-of-core memory algorithms to handle graphs with a size larger than the amount of memory available. Experimental results confirm high performance and good scalability of the proposed solutions. Moreover, the approach can be applied to other graph processing problems, which recently rapidly increase in demand.

Practical experience of using asynchronous programming models based on active messages for large-scale graph processing
A. Frolov, DISLab

In the talk an overview of the three asynchronous programming models (Charm++, ActivePebbles, Grappa), based on the active messages concept, will be presented. The models will be compared on the set of the basic graph algorithms such as PageRank, breadth-first search (BFS), single source shortest paths (SSSP), and connected componets (CC).

Investigation and simulation of parallel methods for computing random graph characteristics
D. Migov, D.Weins, S. Nesterov, Institute of Computational mathematics and mathematical geophysics of SB RAS

We present parallel methods for calculation of the two indices of network reliability. It is assumed that network channels are subject to random failures and network nodes are perfectly reliable. Random graphs are usually used for dealing with such networks. As a reliability index of a network we consider two random graph characteristics. One of them is the probabilistic connectivity. The other index is the probability that a set of terminals are linked by operational paths with the number of included edges that is less or equal to a given integer. The problems of calculation of these characteristics are NP-hard. The analysis of the numerical experiments has allowed us to tune some important algorithms parameters and to significantly improve the algorithms scalability. We have also obtained and investigated multiagent models for execution of the proposed parallel methods.

Interconnect networks and Big Data technologies
A. Semenov, A. Agarkov, A. Frolov, DISLab

We present the survey of the state-of-the-art Big Data technologies and evaluate the interconnect characteristics impact on the performance of the Apache Spark operations and applications.

Topics of interest

Topics of interest include, but are not limited to:

• Parallel graph algorithms
• Graph applications
• Parallel programming models and runtime systems for graph processing
• Performance evaluation of graph algorithms on high performance computing systems
• Graph applications and exascale
• Graph applications and Big Data
• Graph visualization

Submission and Important Dates

Please see the conference submission terms and important dates.

Program Committee

• Voevodin V. V., Corresponding member of the Russian Academy of Sciences, MSU RCC (co-chair)
• Simonov A. S., PhD, JSC NICEVT (co-chair)
• Frolov A. S., DISLab (JSC NICEVT)
• Semenov A. S., PhD, DISLab (JSC NICEVT)
• Pozdneev A.V., PhD, IBM
• Daryin A. N., PhD, Yandex
• Korzh A. A., PhD, Micron
• Chernoskutov M. A., IMM Ural Dep. of RAS

Contacts

Alexander Frolov, DISLab (JSC NICEVT), e-mail: alexndr.frolov at gmail com
Alexander Semenov, DISLab (JSC NICEVT), e-mail: alxdr.semenov at gmail com