Everything You Always Wanted to Know about Multicore Graph Processing but Were Afraid to Ask

Graph processing systems are used in a wide variety of fields, ranging from biology to social networks, and a large number of such systems have been described in the recent literature. We perform a systematic comparison of various techniques proposed to speed up in-memory multicore graph processing. In addition, we take an end- to-end view of execution time, including not only algorithm execution time, but also pre-processing time and the time to load the graph input data from storage. More specifically, we study various data structures to represent the graph in memory, various approaches to pre-processing and various ways to structure the graph computation. We also investigate approaches to improve cache locality, synchronization, and NUMA-awareness. In doing so, we take our inspiration from a number of graph processing systems, and implement the techniques they propose in a single system. We then selectively enable different techniques, allowing us to assess their benefits in isolation and independent of unrelated implementation considerations. Our main observation is that the cost of pre-processing in many circumstances dominates the cost of algorithm execution, calling into question the benefits of proposed algorithmic optimizations that rely on extensive pre- processing. Equally surprising, using radix sort turns out to be the most efficient way of pre-processing the graph input data into adjacency lists, when the graph in- put data is already in memory or is loaded from fast storage. Furthermore, we adapt a technique developed for out-of-core graph processing, and show that it significantly improves cache locality. Finally, we demonstrate that NUMA-awareness and its attendant pre-processing costs are beneficial only on large machines and for certain algorithms.

Efficient large-scale graph processing: optimisations for storage, performance and evolving graphs

Jasmina Malicevic

Graph processing systems are used in a wide variety of fields, ranging from biology to social networks. Algorithms to mine graphs incur many random accesses, and the sparse nature of the graphs of interest, exacerbates this. As DRAM sustains high bandwidth in the presence of random accesses, traditionally, it was the chosen medium to store and process graphs from. Many in-memory systems were presented at top tier conferences, and every system compared to the previous in algorithm execution time. What is not clearly evaluated are the overheads of pre-processing the input in order to support particular optimisations. More critical, for a systems designer, it is very hard to reason about what are the fundamental techniques that lead to performance gains. We implement the proposed optimisations of state-of-the-art systems within one system to answer this question. We found that the pre-processing cost often dominates the cost of algorithm execution, calling into question the benefits of proposed algorithmic optimisations that rely on extensive pre-processing. The design of a system has to be carefully guided by the characteristics of the algorithms, graphs and hardware. Furthermore, in-memory systems are often limited by the amount of available memory on a single machine. When the graph cannot fit in the available DRAM, many systems scale up to secondary storage on one machine, or in the cloud. As storage is cheaper than memory, they trade off performance for more space, at a lower cost. Emerging non-volatile technologies such as 3D XPoint, offer a new opportunity for bridging this performance gap. Designing a system that fully utilises these storage devices is not straightforward. Traditional I/O optimisations, designed for SSDs, underutilise the device, and systems end up being CPU bound on fast storage. By removing the dedicated I/O layers, and combining pre-processing approaches for in-memory and out-of-core systems, we are able to switch graph representations to benefit a particular algorithm. This improves the end-to-end execution time up to 2x. However, in the presence of updates to the graph structure, the data structures used by static algorithms need to be re-created on every update, and the algorithm executed from scratch. The high latency of this process is not acceptable for critical applications such as fraud detection. We address this problem by developing two systems to compute on evolving graphs, using an update friendly graph representation. Each system targets a different group of applications: graph analytics and graph pattern mining (GPM). For graph analytics we trade sub-millisecond latencies for consistency. For GPM, we use re-computation and backtracking to handle millions of updates per second, outperforming state of the art by up to 5x.

EPFL2019

Consensus Inside

Tudor Alexandru David, Rachid Guerraoui, Maysam Yabandeh

Scaling to a large number of cores with non-uniform communication latency and unpredictable response time may call for viewing a modern many-core architecture as a distributed system. In this view, the cores replicate shared data and ensure consistency among replicas through a message-passing based agreement protocol. In this paper, we present the first in-depth study of message-passing agreement on many-cores. In particular, we focus on the possibility of such a protocol being non-blocking. We highlight a number of optimizations that are specific to the many-core environment and present 1Paxos, a new non-blocking agreement protocol that takes up the challenges of this environment.

2014

Real-Time Optimization of Solid Oxide Fuel Cell Systems

Tafarel de Avila Ferreira

Optimization of industrial processes aims at minimizing operating cost or maximizing economic profit while respecting plant constraints. In process industry, real-time optimization (RTO) is often considered to ensure optimal plant operation and constraint satisfaction. Solid-oxide fuel-cell (SOFC) devices oxidize fuels such as hydrogen and methane to produce electric energy through electrochemical reactions at very high efficiency. To reduce the emission of carbon dioxide and the high cost of non-renewable energies, fuel cells have become popular as an alternative energy source with a wide range of applications. The optimal operation of SOFC systems, while being subjected to changing operating conditions such as variations in the electrical power demand, remains a challenging problem in the field of control and optimization. In addition, these types of devices are characterized by slow dynamics and drifts such as degradation. This motivates the use of real-time optimization for optimizing and controlling the operation of SOFC systems. The most popular RTO technique in industry is the so-called two-step approach. This approach consists in estimating the model parameters based on measurements by solving a parameter estimation problem, and computing the next operating point by solving an optimization problem using the updated model. However, this technique is highly dependent on model accuracy and tends to fail in the presence of structural plant-model mismatch. As an alternative, modifier adaptation has been developed to enforce convergence to the plant optimum even in presence of structural plant-model mismatch. Since plant optimality is often characterized by active constraints, it is possible to use a simpler version of modifier adaptation, called constraint adaptation (CA). This approach corrects the constraints in the model-based optimization problem by means of bias terms computed from the differences between the measured and predicted values of the constraints. The active plant constraintsâi.e. the intersection of the constraints where the plant opti- mum liesâfor each mode of operation is typically known from experience. Therefore, as the optimum of SOFC systems typically lies on active plant constraints, we can apply constraint adaptation. One of the drawbacks of static RTO is the fact that it is necessary to wait until the plant reaches its steady state. Since this may be inappropriate for slow processes, we propose an RTO approach that can speed up the procedure by using transient measurements combined with a dynamic tendency model. In this work, we apply constraint adaptation combined with transient measurements and a dynamic model to experimental SOFC systems. The proposed approach is applied to two SOFC systems: (i) an SOFC system with 6 cells that consists of both hardware and software components; (ii) a commercial SOFC system named BlueGEN. The results obtained are very promising. For both systems, the proposed approach can reach the power demand much faster than the time it takes for the process to settle to steady state. The optimizer is quick at finding and tracking the correct set of active constraints, thus avoiding large constraint violations. In addition, we study the effect of the RTO period on the convergence rate. Finally, we show that CA acts simultaneously as a controller and an optimizer that is able to efficiently detect and track the correct set of active constraints.

EPFL2019

Real-Time Optimization of Solid Oxide Fuel Cell Systems

Tafarel de Avila Ferreira

EPFL2019

Efficient large-scale graph processing: optimisations for storage, performance and evolving graphs

Jasmina Malicevic

EPFL2019