Data-Aware Algorithms

Loris Marchal, Warsaw, Fall 2023

In many today's computing systems, the cost, both in time and energy, of moving the data has become predominant compared to the cost of computing. Part of the solution for this problem can be found in algorithms: over the years, several computation models and algorithmic strategies have been proposed to optimize data movement instead of (or in addition to) the classical objective of computational complexity. The goal of this course is to present a variety of these solutions.

NB: this is a short version of a Master 2 course given at ENS-Lyon in Fall 2020.

Part 1: Introduction, pebble games models, I/O lower bounds for matrix product

The first part consists in a introduction to the course, presentation of the early models based on pebble games, study of I/O complexity for matrix multiplication, both in a sequential and a parallel context.

Available material:

Some articles where results are taken from:

Part 2: Cache-oblivious algorithms

We present here the basics of extern memory algorithms and cache-oblivious algorithms.

Available material:

Other courses/resources on cache-oblivious algorithms:

Some articles where results on cache-oblivious algorithms are taken from:

Part 3: Memory-aware DAG scheduling

We describe how to model scientific computations as DAGs of tasks, and how the way the DAG is scheduled (traversed) influences the amount of memory needed for the computation.

Available material:

Some articles where results on DAG scheduling are taken from:

Author: Loris Marchal

Created: 2023-10-17 Tue 17:28

Emacs (Org mode 8.2.10)