Algorithms for Modern Hardware: Flash Memory
Description
Prof. Dr. Ulrich Meyer; Universität Frankfurt
Project website
Modern computers significantly deviate from the uniform cost model traditionally used in algorithms research. In the first phase of the proposed project we want to deal with a very recent trend: flash memory. Originally used in small portable devices, this block based solid-state storage technology is predicted 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 modelling 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 (like sorting, spanning trees, graph traversal, lower bounds) and applied problems (e.g. finding cycles in networks arising from cryptography applications) on massive graphs using flash memory. Some of these problems are still open for the easier external-memory model, too, in particular for directed graphs, in dynamic or approximate setting. The best solutions will be added to libraries like STXXL. The potential benefits of this project are significantly improved methods to process large-scale directed graphs like the web or social network graphs. Basic graph algorithms for depth first search, breadth first search, shortest paths, spanning trees or network flows are well established compenents of every algorithms course and many applications. Theory has produced advanced algorithms for these problems that should theoretically be superior to the simple text book methods. The starting point of this project is to explore the possibility to transform such advanced approaches in to practicable algorithms and implementations. We are particularly interested in algorithms that can exploit parallelism and memory hierarchies.
Publications
- A. Beckmann, U. Meyer, P. Sanders and J. Singler. "Energy-efficient sorting using solid state disks", Sustainable Computing: Informatics and Systems, Vol. 1. 2011, pp. 151-163. [More]
- U. Meyer, A. Negoescu and V. Weichert. "New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest-Paths Approaches". Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings. 2011. pp. 217-228. [More]
- G. Moruz and A. Negoescu. "OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm". 2011. [More]
- K. -. Pukall. "Modelling and Analysis of Flash Memory Translation Layers". Bachelor Thesis, Goethe University Frankfurt am Main. 2010. [More]
- F. Gieseke, G. Moruz and J. Vahrenhold. "Resilient K-d Trees: K-Means in Space Revisited". Proc. 10th IEEE International Conference on Data Mining. 2010. pp. 815-820. [More]
- C. Neumann. "Semi-External Stable-Marriage". Bachelor Thesis, Goethe University Frankfurt am Main. 2009. [More]
- D. Ajwani, R. Dementiev and U. Meyer. "Breadth first search on massive graphs". Shortest Path Computations: Ninth DIMACS Challenge. 2009. pp. 291-307. [More]
- A. Beckmann, R. Dementiev and J. Singler. "Building A Parallel Pipelined External Memory Algorithm Library_1". 23rd IEEE International Symposium on Parallel and Distributed Processing. 2009. pp. 1-10. [More]
- A. Beckmann, R. Dementiev and J. Singler. "Building A Parallel Pipelined External Memory Algorithm Library". 23rd IEEE International Symposium on Parallel and Distributed Processing. 2009. pp. 1-10. [More]
- D. Ajwani and U. Meyer. "Design and Engineering of External Memory Traversal Algorithms for General Graphs". Algorithmics of Large and Complex Networks. 2009. pp. 1-33. [More]
- G. S. Brodal, A. G. Jorgensen, G. Moruz and T. Molhave. "Counting in the Presence of Memory Faults". Proc. 20th International Symposium on Algorithms and Computation. 2009. pp. 842-851. [More]
- D. Ajwani, A. Beckmann, R. Jacob, U. Meyer and G. Moruz. "On computational models for flash memory devices". 8th International Symposium on Experimental Algorithms. 2009. pp. 16-27. [More]
- A. Kovacs, U. Meyer, G. Moruz and A. Negoescu. "Online Paging for Flash Memory Devices". 20th International Symposium on Algorithms and Computation. 2009. pp. 842-851. [More]
- D. Ajwani, I. Malinger, U. Meyer and S. Toledo. "Characterizing the Performance of Flash Memory Storage Devices". 7th International Workshop on Experimental Algorithms. 2008. pp. 208-219. [More]
- U. Meyer. "On Trade-Offs in External-Memory Diameter Approximation". 11th Scandinavian Workshop on Algorithm Theory. 2008. pp. 426-436. [More]
- U. Meyer. "On Dynamic Breadth-First Search in External-Memory". 25th Annual Symposium on Theoretical Aspects of Computer Science. 2008. [More]