Eléments logiciels pour le traitement des données massives


Objectif

Ce cours, destiné aux étudiants déjà familiers avec les concepts de base d’un langage orienté objet ou fonctionnel, traite des aspects techniques informatiques que revêtent l’exploration et l’utilisation statistiques de données massives, des thèmes actuellement désignés par le terme "Big Data".
Le traitement de ces jeux de données très volumineux soulève de nombreux enjeux informatiques : lorsque les performances sont importantes, de nombreuses abstractions logicielles volent en éclat et une compréhension plus fine de nombreux phénomènes devient alors indispensable. Le cours présente certains de ces aspects : impact de la connaissance du hardware sur la performance, enjeux de la mémoire, qu’elle soit locale ou répartie sur de nombreuses machines, programmation répartie et concurrente, concepts de base d’algorithmie, afin de distinguer et d’estimer ce qui est lent de ce qui est rapide, ce qui est petit de ce qui est grand, ce qui nécessite d’être réparti de ce qui peut être réalisé sur une simple machine.

Plan

1 Hardware

– RAM DDR et SDR.
– Latence des CPUs. Loop unrolling.
– Architectures SMP et NUMA.
– Caches, Cache hit et Cache miss, Cohérence.
– Disques durs HDD et SSD.
– Quelques ordres de grandeurs.

2 Gestion de la mémoire

– Concepts de pile et tas. Call stack. Context switching. Trashing des caches.
– RAII.
– Smart pointers.
– Garbage-collection.

3 Programmation concurrente

– Mutual Exclusion.
– Verrous, Sections critiques, concepts de Starvation Freedom et Deadlock Freedom.
– Verrou de Peterson.
– Race conditions.
– Quelques structures de données thread-safe.
– Variables volatiles, réordonnancement des instructions, Memory Fence, et modèle mémoire C++/C#, Java.

4 Programmation répartie

– GPU.
– Grid-computing. Map-Reduce.
– Cloud Computing.
– Stacks Hadoop et Azure.
– Systèmes de stockage. TSV, SQL, No-SQL par les Key-value store.
– CAP theorem et strong consistency. Impact sur l’architecture et la responsabilité dans les Key-value stores.

5 Algorithmie

– Complexité espace/temps.
– Tris (Heapsort, Quicksort).
– Table de hachage et structures de données classiques.
– Binary Search Tree et Red Black Tree.
– Quelques algorithmes sur les chaînes de caractères.

6 Outils de développement

– Versionning de source.
– Intégration continue.
– Tests unitaires et TDD.
– Proling.
– Gestion des tickets.

7 Eléments d’architecture logicielle

– La POO revisitée.
– Langages fonctionnels.
– DDD et CQRS.

Le cours sera évalué par un projet informatique orienté mathématiques financières ou statistiques, au choix des étudiants. L’objectif du projet sera de donner une dimension concrète à des concepts déjà traités plus abstraitement dans des cours de  statistiques ou de finance, en utilisant une partie des outils introduits durant les cours.

Références

ECKEL B. : Thinking in C++, disponible gratuitement sur mindview.net
Meyers S. : Effective C++
Alexandrescù A. : Modern C++ Design: Generic Programming and Design Patterns Applied
Drepper U. : What every programmer should know about memory
Shavit N. et Herlihy M. : The Art of Multiprocessor Programming