Computer systems usually have a whole hierarchy of memory levels, with each level having its own performance characteristics. Typical memory levels are: CPU registers, memory cache, main memory (RAM), and secondary memory storage such as magnetic disks. Traditionally, the design of algorithms do not take this memory hierarchy into account, but assumes a model with a single level of main memory.
In an increasing number of problems, the amount of data to be processed is far too massive to fit into internal memory. Examples include VLSI verification, computer graphics, geographic information systems (GIS), and geological and
meteorological databases, where the amount of data may be measured in terabytes.
In such applications, the communication between the fast internal memory and the slow external memory is often the performance bottleneck, and the analysis of algorithms under the assumption of a single level of memory may be meaningless.
Instead, a more realistic measure of the efficiency of an algorithm is the number of I/O-operations performed between internal memory and disk. Algorithms designed to minimize this number are termed external memory algorithms.
In this course, we will study the design and analysis of efficient external memory algorithms and data structures. Different paradigms for efficiently solving problems in external memory will be covered, and a number of specific algorithms from areas like computational geometry and GIS will be covered.
Lecturers:
Gerth Stølting Brodal and Rolf Fagerberg
Literature
Selected papers and surveys
Prerequisites
dADS and dAlg
Course Language
Danish or English
Credits
2 points/10 ECTS credits