ScAlBox

ScAlBox aims at basic algorithmic tools that can be used in a wide spectrum of applications and scale orders of magnitude better than the state of the art with respect to input size or number ofprocessors.

In the last decades, we have witnessed the transition into the information age with profound effects on science, technology, and our daily life. This transition is driven by a growing spectrum of computer applications that process larger and larger data sets using increasingly complex algorithms. However, the scalability challenge has emerged as a major road block to this progress: An explosion of the amount of data to be processed (big data) coincides with a stagnating performance of a single processor
core. This widening performance gap can only be closed using many parallel processors. However, parallel algorithms have long been neglected by algorithm theory while heuristic software development optimizes for existing machines and inputs but fails to give predictable scalability for future, larger data sets and more processors.

We want to overcome this roadblock by developing scalable solutions for the basic toolbox of algorithms and data structures that are needed in many applications (e.g., sorting, searching, queues, basic graph algorithms, collective communication, and load balancing). Our goal is to provide algorithms and software libraries that scale to millions of processors and give hard performance guarantees for arbitrary inputs. This is challenging due to large gaps between theory and practice and because such algorithms have to integrate scalable fault tolerance and dynamic load balancing to an unprecedented extent.