Algorithms for Modern Hardware: Flash Memory
Prof. Dr. Ulrich Meyer; Universität Frankfurt
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.
- 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]