DFG

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
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
15
Gabriel Moruz and Andrei Negoescu
Onlinemin: A fast strongly competitive randomized paging algorithm
Submitted, 2011. Available online at http://www.ae.cs.uni-frankfurt.de/pdf/simple_paging.pdf.
14
Ulrich Meyer, Andrei Negoescu, and Volker Weichert
New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest Path Approaches
In Proc. 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS), 2011, to appear.
13
Andreas Beckmann and Ulrich Meyer
Deterministic Graph-Clustering in External-Memory with Applications to Breadth-First Search
Manuscript, 2010. Electronically available under http://www.ae.cs.uni-frankfurt.de/pdf/detcluster.pdf
12
Fabian Gieseke, Gabriel Moruz, and J. Vahrenhold
Resilient k-d trees: K-means in space revisited
In Proc. 10th IEEE International Conference on Data Mining (ICDM), pages 815--820, 2010.
11
Andreas Beckmann, Ulrich Meyer, Peter Sanders, and Johannes Singler
Energy-Efficient Sorting using Solid State Disks
In Proc. 1st International Green Computing Conference (IGCC), pages 191-202, 2010. Full version invited for a special issue of Sustainable Computing: Informatics and Systems.
10
Annamaria Kovacs, Ulrich Meyer, Gabriel Moruz, and Andrei Negoescu
Online Paging for Flash Memory Devices
In Proc. 20th International Symposium on Algorithms and Computation (ISAAC), pages 352--361, 2009
9
Gerth S. Brodal, Allan G. Jørgensen, Gabriel Moruz, and Thomas Mølhave.
Counting in the Presence of Memory Faults
In Proc. 20th International Symposium on Algorithms and Computation (ISAAC), pages 842-851, 2009.
8
Deepak Ajwani, Andreas Beckmann, Riko Jacob, Ulrich Meyer, and Gabriel Moruz
On Computational Models for Flash Memory Devices.
In Proc. 8th International Symposium on Experimental Algorithms (SEA), pages 16-27, 2009.
7
Andreas Beckmann, Roman Dementiev, and Johannes Singler
Building A Parallel Pipelined External Memory Algorithm Library
In In Proc. 23rd International Parallel & Distributed Processing Symposium (IPDPS), pages 1-10, 2009.
6
Deepak Ajwani, Roman Dementiev, Ulrich Meyer, and Vitaly Osipov.
Breadth first search on massive graphs.
In Shortest Path Computations: Ninth DIMACS Challenge, 2009.
5
Deepak Ajwani and Ulrich Meyer
Design and Engineering of External Memory Traversal Algorithms for General Graphs
In Algorithmics of Large and Complex Networks, pages 1-33, 2009.
4
Ulrich Meyer and Vitaly Osipov
Design and Implementation of a Practical I/O-efficient Shortest Paths Algorithm
In Proc. 11th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 85-96, 2009
3
Deepak Ajwani, Itay Malinger, Ulrich Meyer, and Sivan Toledo
Characterizing the Performance of Flash Memory Storage Devices and Its Impact on Algorithm Design
In Proc. 7th International Workshop on Experimental Algorithms (WEA), pages 208-219, 2008.
2
Ulrich Meyer
On Dynamic Breadth-First Search in External-Memory
In Proc. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 551--560, 2008.
1
Ulrich Meyer
On Trade-Offs in External-Memory Diameter Approximation
In Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT), pages 426-436, 2008.
Theses
2
Kai-Marian Pukall
Modelling and Analysis of Flash Memory Translation Layers
Bachelor Thesis, Goethe University Frankfurt am Main, 2010.
1
Christian Neumann
Semi-External Stable-Marriage
Bachelor Thesis, Goethe University Frankfurt am Main, 2009.