Data aware algorithms
Loris Marchal ENS Lyon
Course Summary |
About the lecturer |
Location and schedule |
For decades, algorithms have been designed with the objective of minimizing the amount of computation, which is the main focus of complexity theory. However, the evolution of computing resources show that the computing speed of our computers is increasing at a much faster pace than the communication speed of buses or networks, that are in charge of moving the data from a stable storage to a place where the computation takes place (such as memory or cache). Hence, the cost of moving data is becoming the prevailing factor for performance in many cases.
In this lectures, we will present several computation models and algorithmic strategies that have been proposed to optimize data movement instead of (or in addition to) computational complexity. In particular, we we briefly present the founding models of pebbles games introduced in the 70s and 80s, then we will present lower bounds on data movements and optimized algorithms for linear algebra operations. Next, we will show the basis of two other models focusing on data movement: cache oblivious algorithms and memory-aware task graph scheduling.
About the lecturer:Loris Marchal is a CNRS senior researcher working in the computer science laboratory of the École Normale Supérieure de Lyon, in France, where he is leading the Inria ROMA team. He received his PhD and habilitation degree from ENS Lyon. His main research interest lies in the optimization of high performance computing application through mapping and scheduling algorithms. He is particularly interested in the design of scheduling algorithms for situations where memory is limited and/or data movements must be carefully considered.
Materials: Slides and extra materials Homework
Location and schedule:
|
|
||||||||