SHAD: The Scalable High-Performance Algorithms and Data-Structures Library
- 1 May 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 442-451
Abstract
The unprecedented amount of data that needs to be processed in emerging data analytics applications poses novel challenges to industry and academia. Scalability and high performance become more than a desirable feature because, due to the scale and the nature of the problems, they draw the line between what is achievable and what is unfeasible. In this paper, we propose SHAD, the Scalable High-performance Algorithms and Data-structures library. SHAD adopts a modular design that confines low level details and promotes reuse. SHAD's core is built on an Abstract Runtime Interface which enhances portability and identifies the minimal set of features of the underlying system required by the framework. The core library includes common data-structures such as: Array, Vector, Map and Set. These are designed to accommodate significant amount of data which can be accessed in massively parallel environments, and used as building blocks for SHAD extensions, i.e. higher level software libraries. We have validated and evaluated our design with a performance and scalability study of the core components of the library. We have validated the design flexibility by proposing a Graph Library as an example of SHAD extension, which implements two different graph data-structures; we evaluate their performance with a set of graph applications. Experimental results show that the approach is promising in terms of both performance and scalability. On a distributed system with 320 cores, SHAD Arrays are able to sustain a throughput of 65 billion operations per second, while SHAD Maps sustain 1 billion of operations per second. Algorithms implemented using the Graph Library exhibit performance and scalability comparable to a custom solution, but with smaller development effort.Keywords
This publication has 15 references indexed in Scilit:
- High-Performance Data Analytics Beyond the Relational and Graph Data Models with GEMS2017
- DASH: A C++ PGAS Library for Distributed Data Structures and Parallel Algorithms2016
- GraQL: A Query Language for High-Performance Attributed Graph Databases2016
- In-Memory Graph Databases for Web-Scale DataComputer, 2015
- A reconfigurable fabric for accelerating large-scale datacenter services2014
- Scaling Irregular Applications through Data Aggregation and Software Multithreading2014
- Scaling Semantic Graph Databases in Size and PerformanceIEEE Micro, 2014
- STINGER: High performance data structure for streaming graphs2012
- STAPL2010
- Criticality and Parallelism in Combinatorial OptimizationScience, 1996