SPP 1307 - Algorithms for Modern Hardware: Flash Memory

This is part of the DFG Schwerpunkt Nr. 1307, Algorithm Engineering.

I would rather have today’s algorithms on yesterday’s computers than vice versa.” Philippe Toint

Modern computers significantly deviate from the uniform cost model traditionally used in algorithms research. This is particularly true for computing with large data on flash memory. Originally used in small portable devices, this block based solid-state storage technology is on its way to become a new standard level in the PC memory hierarchy, partially even replacing hard disks. Unfortunately, the read/write/erase performance of flash memory is highly dependent on access patterns, filling degree, and optimizations to prevent the devices from early wear-out. Therefore, even cache-efficient implementations of most classic algorithms may not exploit the benefits of flash.

After appropriately modeling flash memory we aim at the design, analysis, implementation, and experimental evaluation of graph algorithms tailored to these models. We will cover both fundamental questions and applied problems on massive graphs using flash memory. Additionally, we will explore connections to parallelism, energy-efficiency, and resilient computing. The best solutions will be added to libraries like STXXL. The potential benefits of this project are significantly improved methods to process large-scale graphs like the web or social network graphs.

People

Prof. Dr. Ulrich Meyer
Gabriel Moruz, PhD
Dipl.-Inform. Andreas Beckmann
Dipl.-Inf. Volker Weichert

Hardware/Software Projects

Our project EcoSort - Energy-efficient Sorting was awarded the title Selected Landmark 2011 by the initiative Germany - Land of Ideas.

We also keep on contributing to STXXL, the Standard Template Library for Extra Large Data Sets. Version 1.3.1. was released on March 10, 2011.

Publications

conference

Annamaria Kovacs, Angelina Vidali
A Characterization of n-Player Strongly Monotone Scheduling Mechanisms
IJCAI 2015: 568-574
|
Kristian Kersting, Ulrich Meyer
From Big Data to Big Artificial Intelligence? - Algorithmic Challenges and Opportunities of Big Data
KI 32(1): 3-8 (2018)
|
Annamaria Kovacs, Ulrich Meyer, Carmine Ventre
Mechanisms with Monitoring for Truthful RAM Allocation
WINE 2015: 398-412
|
Mahyar Behdju, Ulrich Meyer
DFG Priority Programme SPP 1736: Algorithms for Big Data
KI 32(1): 77-84 (2018)
|
Alexander Schickedanz, Deepak Ajwani, Ulrich Meyer, Pawel Gawrychowski
An Empirical Comparison of k-Shortest Simple Path Algorithms on Multicores
COMPLEX NETWORKS (1) 2018: 28-40
|
|
Ulrich Meyer, Manuel Penschuck, The Algorithmics Column by Gerhard J Woeginger
Large-scale Graph Generation and Big Data: An Overview on Recent Results
122nd issue of the EATCS Bulletin 2017
|
Michael Hamann, Ulrich Meyer, Manuel Penschuck, Dorothea Wagner
Average-Case Behavior of k-Shortest Path Algorithms
ALENEX 2017: 58-72
|
|
Gabriel Moruz, Andrei Negoescu, Christian Neumann and Volker Weichert
Engineering Efficient Paging Algorithms
Proc. of the 11th International Conference on Experimental Algorithms (SEA), LNCS 7276, pages 320-331, Springer, 2012
Ulrich Meyer, Andrei Negoescu and Volker Weichert
New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches
Proc. of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS), LNCS 6595, pages 217-228, Springer, 2011

journal

George Christodoulou, Annamária Kovács, Michael Schapira
Bayesian Combinatorial Auctions
J. ACM 63(2): 11:1-11:19 (2016)
|

thesis

Annamaria Kovacs
Fast Algorithms for Two Scheduling Problems
PhD thesis, Universität des Saarlandes, 2007