Advanced Models of Computation
Coordinator
- N.N. Previously Uli Meyer (now at Frankfurt University).
|
Researchers
Recent Alumni
Research Area
Basic algorithmic research usually assumes some variant of the
von Neumann model of computation with a single processor
and uniform memory. Driven by technological developments
and new applications, the von Neumann model increasingly
deviates from reality. Therefore much work in Department 1 is devoted
to meeting these challenges by developing algorithms
for more advanced models of computing. Some important questions:
- Parallelism and Distribution: How to exploit the
power of many processors? How to schedule work?
How to coordinate multiple competing or cooperating agents?
- Networks: How to communicate efficiently
using the many types of networks that are the backbone of the
``information society'': Internet, mobile networks, ...?
- Memory Hierarchies: Registers, hardware caches, hard disks and
tapes/optical disks form a hierarchy from fast,
small, and expensive memory to
slow, large, and cheap memory. How to orchestrate computations to
optimize the processing of massive data sets in this context?
Sample Publications
- D. Ajwani, U. Meyer, and V. Osipov.
Improved external memory BFS implementations.
In 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 3-13, 2007.
- K. Chang and R. Kannan.
The Space Complexity of Pass Efficient Algorithms for Clustering.
In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06
ACM-SIAM, pp. 1157-1166, 2006.
- U. Meyer and N. Zeh.
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths.
In Proc. 14th Ann. European Symposium on Algorithms (ESA),
LNCS, Springer, pp. 540-551, 2006.
Projects
