Eléments logiciels pour le traitement des données massives#
Eléments logiciels pour le traitement des données massives (ENSAE)
Cours animé par : Matthieu Durut, Xavier Dupré.
Le cours est évalué avec un projet informatique. Programme de l’année 2023 : Feuille de route 2022-2023 (3A).
Eléments techniques#
Anatomie et histoire d’un ordinateur#
mémoire, cache, northbridge, southbridge
CPU, GPU, FGPA, ASICS
2004 - espace entre deux circuits intégrés de 32 ns, passage à 24 ns ? effet quantique, passage d’électron
optimisation des calculs, parallélisation, notion de cache et de latence
Lectures
What every computer scientist should know about floating point
Introduction au système de recommandation par facteurs latents
Learning Efficient Algorithms with Hierarchical Attentive Memory
GotoBLAS (écrit par Kazushige Gotō)
Judy Arrays, site, cette structure implémente un mapping int/int plus efficace que l’implémentation traditionnelle avec une table de hashage, la structure utilise les propriétés des caches dans les processeurs
Machine Learning
CPU#
Notebooks
Le notebook suivant montre comment écrire du code C++ tout en l’utilisant depuis Python pour mesurer une optimisation que proposent les processeurs CPU : le branching.
Code
ENH: Improves speed of one hot encoding, cette pull request (PR) modifie un code très court pour réduire le nombre d’allocations mémoire avec numpy
New K-means implementation for improved performances, cette pull request (PR) étudie une nouvelle implémentation de l’algorithme des k-means, il n’est pas évident de se plonger dans le code mais il faut lire les commentaires qui illustrent les différences de performances selon que la machine utilise ses caches L2, L3.
Lectures
Weld: A Multithreading Technique Towards Latencytolerant VLIW Processors
Stackless Python : implémentation de l’interpréteur de Python spécialisée dans le micro threading.
Why is it faster to process a sorted array than an unsorted array?
C++ Concurrency in Action (second edition, published 2019 by Manning Publications)
ZeRO: Memory Optimizations Toward Training Trillion Parameter Models
Vidéos
Librairies
OpenMP : c’est une librairie très utilisée pour paralléliser les calculs en C++ sur plusieurs threads
OpenMPI : c’est une librairie utilisée pour synchroniser des calculs parallélisés sur plusieurs processeurs (ou machines)
daal4py, réécriture d’algorithme de machine learning optimisée pour les processeurs Intel
Outils
Intel propose une version de l’interpréteur python avec les principaux modules compilée spécifiquement pour ces processeurs : Intel Python. L’accélération n’est pas exceptionnelle pour un processeur avec un ou deux coeurs, mais elle l’est particulièrement sur des machines dédiées aux calculs.
GPU#
Notion de block, threads
Echange d’information entre CPU et GPU
Lectures sur le GPU
Quelques éléments de consommation électrique sur les GPU et CPU
Inter-Block GPU Communication via Fast Barrier Synchronization
Demystifying GPU Microarchitecture through Microbenchmarking
Computing Higher Order Derivatives of Matrix and Tensor Expressions
WarpDrive: Extremely Fast End-to-End Deep Multi-Agent Reinforcement Learning on a GPU
A friendly introduction to machine learning compilers and optimizers
Lectures sur le C++
Thinking in C++, Bruce Eckel
Effective C++, Scott Meyers
What Every Programmer Should Know About Memory, Ulrich Drepper
The Art of Multiprocessor Programming, Maurice Herlihy, Nir Shavit
An Introduction to GPGPU Programming - CUDA Architecture, Rafia Inam
Python
theano (n’est plus maintenu)
Tous les modules de deep learning.
Bas niveau
Sécurité et bas niveau
“Kernel memory leaking” Intel processor design flaw forces Linux, Windows redesign
Meltdown and Spectre : Bugs in modern computers leak passwords and sensitive data.
Optimisation
No Bits Left Behind : l’article quelques stratégies bas-niveau pour optimiser les programmes
Modules
TPU, IPU, FGPA, …#
BLAS, LAPACK, calcul matriciel#
Notebook
Pas vraiment un notebook, un exemple d’utilisation d’une fonction LAPACK dans un code python / cython : Résoudre une régression linéaire avec BLAS (et le code associé direct_blas_lapack.pyx).
Lectures
Introducing TensorNetwork, an Open Source Library for Efficient Tensor Calculations, Tensor in a Nutshell (github)
Anatomy of High-Performance Many-Threaded Matrix Multiplication
Faster identification of optimal contraction sequences for tensor networks, cet article s’intéresse à l’implémentation optimale de réaliser une opération de type einsum, les découvertes de l’article sont implémentées dans le module opt-einsum.
Modules
Optimisations logicielles#
Calcul matriciel#
Autres que CPU, GPU#
Lectures
Eléments théoriques#
Crypographie, block chain#
commitment et signature (RSA)
Tiers de confiance et distributed consensus (PAXOS), RAFT
Block chain, Bitcoin, Attque (Incentive, long term consensus, la probabilité qu’on soit en désaccord décroît avec le temps, monnaie stable, sûre, anonyme ?)
Lectures
The art of multiprocessor programming, Nit Shavit
Algorithmes Distribués#
(à venir)
Lectures
Communication Complexity of Distributed Convex Learning and Optimization
Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
Measuring the Effects of Data Parallelismon Neural Network Training
ZeRO: Memory Optimizations Toward Training Trillion Parameter Models
Vidéo
Compilateur, compilation à la volée, JIT#
La compilation à la volée ou JIT pour Just in Time est utilisé pour optimiser une partie du code après que l’exécution du programme ait démarrée. numba permet de demander à un compilateur JIT de remplacer le code python par un code optimisé en C++ souvent beaucoup plus rapide si ce code est purement numérique.
Lectures
à venir
Modules
Eléments logiciels#
Structures de données#
1A.1 - Liste, tuple, ensemble, dictionnaire, liste chaînée, coût des opérations
graphe BFS, DFS, Red Black Tree
String matching, Rabin-Karp, automates finis
Notions de coût algorithme, NP Complet
Lectures
Introduction to Algorithms, 3rd Edition, Cormen, Leiserson, Rivest, Stein.
Ecrire du code rapide (article de blog)
The NumPy array: a structure for efficient numerical computation
Threads et synchronisation#
threads, application multi-threadées
variables globales, synchronisation
threads et processus
Lectures
Plus proches voisins en grandes dimensions#
Distribution des calculs, stratégies de stockage, SQL NoSQL#
Lectures
Logiciels
Distribution des calculs en Python
Compression des données#
Lorsque les données sont volumineuses. Une solution consiste à les compresser.
Lectures
Modules
Workflow de données#
Lectures
Modules
Luigi (Python)
Threading Building Blocks (C++, Python)
Oozie (Hadoop, Spark)
Azkaban (Hadoop, Spark)
Deep Learning#
- deep learningnotebooks (Matthieu Bizien):
- deep learningprésentations
Deep Learning 2017 (avec Olivier Grisel)
Framework de deep learning#
TensorFlow : GPU (Deep Learning Google)
Ray : (MPI, Berkeley), Meet Ray, the Real-Time Machine-Learning Replacement for Spark
CUDA : GPU for NVidia
OpenCL (Intel, NVidia Open CL, …)
Quelques modules spécialisé dans le calcul GPU:
rapids (NVidia), en embryon de scikit-learn pour GPU
Les ingénieurs cherchent sans arrêt à créer le bon outil, celui qui leur fait gagner du temps lors de la conception de programmes complexes. Voici quelques outils qui vont dans ce sens. Il faut toujours regarder la date de création de l’outil, s’il est toujours maintenu, s’il est utilisé…
Rust : langage de programmation dont la syntaxe est proche du C. C’est un langage plus sûr que C lorsque des threads sont utilisées car sa syntaxe interdit des constructions qui ne sont pas thread safe. Firefox est réécrit avec le langage RUST : Firefox 48 : le navigateur va embarquer ses premiers composants en Rust.
Données massives avec python#
Map Reduce#
Map Reduce en pratique#
Itérateurs, lien avec le SQL (voir Séries temporelles et map reduce)
Distribution à base de hash (voir 2A.algo - Hash et distribution)
Graphe d’exécution, synchronisation - Map Reduce Flow Chart
Exemple : moyennes par groupes
Pas d’ordre des observations, tri sur l’ensemble des données à éviter
Produit matriciel, représentation d’une matrice en trois colonnes, matrice sparse
Graphe : pas facile en map/reduce, exemple avec l’algorithme des random walk with restarts
Problème des skewed datasets –> clés très mal distribués (voir 2A.algo - Hash et distribution)
Descente du gradient : itératif
Stratégie de parallélisation, propriétés mathématiques optimisation d’une fonction convexe
Schéma des langages de map/reduce : lazy evaluation
Lectures
Computer Systems for Big Data (cours à Columbia)
Vidéos
avec Spark et Spark SQL#
Les notebooks ont été déplacés sur Introduction à Spark.
Lectures
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica
Deep Dive into Catalyst, Catalyst — Tree Manipulation Framework
What is Tungsten for Apache Spark?, Project Tungsten: Bringing Apache Spark Closer to Bare Metal
FAQ
Modules
spark-sklearn : implémentation d’un grid search distribué pour scikit-learn.
turicreate : mélange de deep learning et de spark
Getting started, installation, setup#
SPARK#
Voir Spark approximatif.
Bibliographie#
Cours
Articles
Large Scale Distributed Deep Networks, Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Andrew Y. Ng
Stochastic Gradient Descent Tricks, Léon Bottou
A Fast Distributed Stochastic Gradient Descent Algorithm for Matrix Factorization, Fanglin Li, Bin Wu, Liutong Xu, Chuan Shi, Jing Shi
Parallelized Stochastic Gradient Descent, Martin A. Zinkevich, Markus Weimer, Alex Smola, Lihong Li
Topic Similarity Networks: Visual Analytics for Large Document Sets, Arun S. Maiya, Robert M. Rolfe
Low-dimensional Embeddings for Interpretable Anchor-based Topic Inference, Moontae Lee, David Mimno
K-means on Azure, Matthieu Durut, Fabrice Rossi
Confidence intervals for AB-test, Cyrille Dubarry
Liens
Librairies / outils
amazon-dsstne : moteur de recommandation d’Amazon
Elastic Search : moteur de recherche
Giraph : Large-scale graph processing on Hadoop
Hadoop : système de fichier distribué + Map Reduce simple
Kafka : distributed streaming platform, conçu pour stocker et récupérer en temps réel des événements de sites web
Mesos : Apache Mesos abstracts CPU, memory, storage, and other compute resources away from machines (physical or virtual), Elixi
MLlib : distributed machine learning for Spark
Parquet : Apache Parquet is a columnar storage format available to any project in the Hadoop ecosystem.
Presto : Distributed SQL Query Engine for Big Data (Facebook)
Spark : Map Reduce, minimise les accès disques, (DPark clone Python de Spark, pas vraiment maintenu)
Spark SQL : SQL distribué, sur couche de Spark
Storm : Apache Storm is a free and open source distributed realtime computation system, conçu pour distribuer des pipelines de traitements de données
YARN : Ressource negociator
kubernetes : automatisation de déploiement d’applications dans des containers (type docker)
Librairies à suivre
multiverso : framework de parallélisation
lightLDA : Latent Dirichlet Application parallélisée
lightGBM : A fast, distributed, high performance gradient boosting (GBDT, GBRT, GBM or MART) framework based on decision tree algorithms.