.. _l-td3a: ========================================================== 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 :ref:`projet informatique `. Programme de l'année 2023 : :ref:`l-feuille-de-route-2023-3A`. .. contents:: :local: ------------ Eléments techniques =================== .. _l-anatomie-ordi: 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* * `Memory Latency over the years `_ * `What every computer scientist should know about floating point `_ * `What every programmer should know about memory `_ * `Introduction to High Performance Scientific Computing `_ * `Zoologie des réseaux de neurones `_ * `Teaching a machine how to play Mario `_ * `Introduction au système de recommandation par facteurs latents `_ * `The Unreasonable Effectiveness of Data `_ * :ref:`Après l'architecture Von Neumann ` * `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* * `Infrastructure for Usable Machine Learning: The Stanford DAWN Project `_ 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 :epkg:`branching`. * `Measures branching in C++ from python `_ *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 :epkg:`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? `_ * `How to optimize C and C++ code in 2018 `_ * `C++ Concurrency in Action (second edition, published 2019 by Manning Publications) `_ * `Embarrassingly parallel for loops `_ * `ZeRO: Memory Optimizations Toward Training Trillion Parameter Models `_ * `SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems `_ *Vidéos* * `C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 1 of 2 `_ *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* * `Introducing PyTorch Profiler - the new and improved performance tool `_ * `DeepSpeed `_ 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 +++ * `Convolution `_ * `Introduction to CUDA C `_ * Notion de block, threads * Echange d'information entre CPU et GPU * `index de thread `_ * `syncthread `_ * `shared array `_ *Lectures sur le GPU* * `Comment apprendre aux ordinateurs à comprendre des images `_ * `Scaling-up Machine Learning Chapitre 16 et 17 `_ * `Quelques exemples graphiques de kernel 3x3 de convolution `_ * `Introduction aux réseaux convolutifs `_, `Canny edge detector `_ * `Understanding Convolution in Deep Learning `_ * `Introduction au GPGPU `_ * `Quelques éléments de consommation électrique sur les GPU et CPU `_ * `Inter-Block GPU Communication via Fast Barrier Synchronization `_ * `CUDA C Programming Guide `_ * `Demystifying GPU Microarchitecture through Microbenchmarking `_ * `Mixed-Precision Training of Deep Neural Networks `_ * `Computing Higher Order Derivatives of Matrix and Tensor Expressions `_ * `Enclaves as accelerators: learning lessons from GPU computing for designing efficient runtimes for enclaves `_ * `WarpDrive: Extremely Fast End-to-End Deep Multi-Agent Reinforcement Learning on a GPU `_ * `A friendly introduction to machine learning compilers and optimizers `_ * `CUDA C/C++ Streams and Concurrency `_ *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 * `SizeBench: a new tool for analyzing Windows binary size `_ *Python* * `GPU and pycuda or pyopencl on Windows `_ * `Pycuda `_ ou `pyopencl `_ pour ceux qui n'ont pas de carte `NVidia `_ * `theano `_ (n'est plus maintenu) * Tous les modules de deep learning. *Bas niveau* * `Low-Level Programming University `_ *Sécurité et bas niveau* * `'Kernel memory leaking' Intel processor design flaw forces Linux, Windows redesign `_ * `KASLR is Dead: Long Live KASLR `_ * `Meltdown and Spectre `_ : Bugs in modern computers leak passwords and sensitive data. * `Meltdown `_ * `Spectre Attacks: Exploiting Speculative Execution∗ `_ *Optimisation* * `No Bits Left Behind `_ : l'article quelques stratégies bas-niveau pour optimiser les programmes *Modules* * `scikit-cuda `_ * `pycuda `_ * `numbapro `_ (voir `A Monte Carlo Option Pricer `_) TPU, IPU, FGPA, ... +++++++++++++++++++ * `Tensor Processor Unit (TPU) `_ * `How different is a TPU from GPU? `_ * `Using the Graphcore IPU for traditional HPC applications `_ * `A List of Chip/IP for Deep Learning `_ * `FPGA vs GPU for Machine Learning Applications: Which one is better? `_ 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* * `Fonctions LAPACK `_ * `Introducing TensorNetwork, an Open Source Library for Efficient Tensor Calculations `_, `Tensor in a Nutshell `_ (`github `_) * `Anatomy of High-Performance Many-Threaded Matrix Multiplication `_ * `Computing the vector norm `_ * `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* * :epkg:`Cython` * `BLAS `_ * `LAPACK `_ * `OpenBLAS `_ * `cython-blis `_ Optimisations logicielles +++++++++++++++++++++++++ * `Compiling ONNX Neural Network Models Using MLIR `_ * `Compiling Classical ML Pipelines into Tensor Computations for One-size-fits-all Prediction Serving `_, `Taming Model Serving Complexity, Performance and Cost: A Compilation to Tensor Computations Approach `_ Calcul matriciel ++++++++++++++++ * `How to optimize GEMM on CPU `_ * `HIGH PERFORMANCE CODE GENERATION IN MLIR: AN EARLY CASE STUDY WITH GEMM `_ * `Fireiron: A Data-Movement-Aware Scheduling Language for GPUs `_ * `Linalg Dialect Rationale: The Case For Compiler-Friendly Custom Operations `_ Autres que CPU, GPU +++++++++++++++++++ *Lectures* * `Plasticine: A Reconfigurable Architecture For Parallel Patterns `_ * `Introduction to CGRA `_ (`Coarse-Grained Reconfigurable Architecture `_) * `Tensor Processor Unit (TPU) `_ * `Application-specific integrated circuit (ASIC) `_ * `Field-programmable gate array (FGPA) `_ * `Ethereum: a Secure Decentralised Generalized Transaction Ledger EIP-150 Revision `_ ------------ 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 ?) * `Ethereum `_ * `Trustless Machine Learning Contracts; Evaluating and Exchanging Machine Learning Models on the Ethereum Blockchain `_ *Lectures* * The art of multiprocessor programming, *Nit Shavit* * `CS176: Multiprocessor Synchronization `_ * `Bitcoin and Cryptocurrency Technologies `_ * `Delivery versus payment `_ * `Ethereum official website `_ * `Hello World in Ethereum `_ * `Introduction to Smart Contracts `_ * `Monnaie, finance et économie réelle `_ .. _l-algo3A-distri: Algorithmes Distribués ++++++++++++++++++++++ (à venir) *Lectures* * `Optimization Methods for Large-Scale Machine Learning `_ * `Diagonal Rescaling For Neural Networks `_ * `Communication Complexity of Distributed Convex Learning and Optimization `_ * `Fast Distributed Gradient Methods `_ * `A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA `_ * `Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis `_ * `Measuring the Effects of Data Parallelismon Neural Network Training `_ * `Scaling Distributed Training with Adaptive Summation `_ * `ZeRO: Memory Optimizations Toward Training Trillion Parameter Models `_ *Vidéo* * `CS231n Winter 2016 Lecture 4 Backpropagation, Neural Networks 1 `_ * :ref:`Algorithmes classiques implémentés ` * `Fast Interesection of Sorted Lists Using SSE Instructions `_ * `Hogwild for Machine Learning on Multicore `_ 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. :epkg:`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* * `ast `_ * `ply `_ (`Lex Yacc `_) * `llvmlite `_ * :epkg:`numba` * `cffi `_ * `jax `_ : module pour calculer automatique la dérivée d'une fonction écrité avec :epkg:`numpy` * `tensornetwork `_ * `clang `_ ------------ Eléments logiciels ================== Structures de données +++++++++++++++++++++ * :ref:`codelistetuplerst` * `liste chaînées `_, `stack `_, `queue `_, `dictionnaire `_, `hashtable `_ * graphe `BFS `_, `DFS `_, `Red Black Tree `_ * `merge sort `_, `quicksort `_, `heapsort `_, `max heap `_ * String matching, Rabin-Karp, automates finis * Notions de coût algorithme, `NP Complet `_ *Lectures* * `Introduction to Algorithms, 3rd Edition `_, Cormen, Leiserson, Rivest, Stein. * `Cracking the Coding Interview `_ * :ref:`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* * `TIL: clock skew exists (distributed system) `_ * `Le dîner des philosophes `_, `The Part-Time Parliament `_ * `Is Parallel Programming Hard, And, If So, What Can You Do About It? `_ * `Time, Clocks, and the Ordering of Events in a Distributed System `_ * `Paxos Made Simple `_ * `Linearizability: A Correctness Condition for Concurrent Objects `_ * :ref:`Calcul distribué en Python (CPU) ` Plus proches voisins en grandes dimensions ++++++++++++++++++++++++++++++++++++++++++ * `Efficient Distributed Locality Sensitive Hashing `_ * `Scalable Locality-Sensitive Hashing for Similarity Search in High-Dimensional, Large-Scale Multimedia Datasets `_ * `Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing `_ .. _l-algo-distribues-3a: Distribution des calculs, stratégies de stockage, SQL NoSQL +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .. toctree:: :maxdepth: 2 td_3a_s5_synthese notebooks/hash_distribution *Lectures* * `What Every Data Scientist Needs to Know about SQL `_ * `Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services `_ * `Distributed Algorithms in NoSQL Databases `_ * `No SQL Data Modeling Techniques `_ * `Distributed Systems and Parallel Computing `_ * `Faster: A Concurrent Key-Value Store with In-Place Updates `_ *Logiciels* * `MongoDB `_ * `rethinkdb `_ (python : `rethinkdb `_) * `FASTER `_ *Distribution des calculs en Python* * :epkg:`dask` * :epkg:`mars` * :epkg:`h2o` * :epkg:`joblib` Compression des données +++++++++++++++++++++++ Lorsque les données sont volumineuses. Une solution consiste à les compresser. *Lectures* * `Compressed sparse row (CSR, CRS or Yale format) `_ * `Moving away from HDF5 `_ *Modules* * `ASDF `_ * `blosc `_ * `h5py `_ * `Zarr `_ Workflow de données +++++++++++++++++++ *Lectures* * `Composable Multi-Threading for Python Libraries `_ *Modules* * `Luigi `_ (Python) * `Threading Building Blocks `_ (C++, Python) * `Oozie `_ (Hadoop, Spark) * `Azkaban `_ (Hadoop, Spark) .. _l-deep-learning-3A: Deep Learning +++++++++++++ * deep learning : notebooks (Matthieu Bizien): * `Réseaux de neurones et Deep Learning `_. * `Transfer Learning `_ (Olivier Grisel) * `Search images with deep learning `_ * deep learning : présentations * `Introduction au Deep Learning `_ * :ref:`l-nolabel` * `Deep Learning 2017 `_ (avec Olivier Grisel) *Vidéos* * `PyTorch in 5 Minutes `_ * `PyTorch Demystified, Why Did I Switch `_ *Cours* * :ref:`Cours de deep learning appliqués au NLP ` * `Companion Jupyter notebooks for the book "Deep Learning with Python" `_ (avec :epkg:`keras`, :epkg:`auto-keras`) 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 `_, ...) * `pytorch `_ * `caffe `_ * `mxnet `_ * `paddlepaddle `_ * `chainer `_ * `gluon `_ Quelques modules spécialisé dans le calcul GPU: * `cupy `_ * `rapids `_ (NVidia), en embryon de :epkg:`scikit-learn` pour GPU * `tensorly `_ 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é... * `Zephyr `_: real-time operating system (`RTOS `_) * `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 ++++++++++++++++++++++++++++ Voir :ref:`l-td2A-massive-data`. ------------ Map Reduce ========== Map Reduce en pratique ++++++++++++++++++++++ * Itérateurs, lien avec le SQL (voir `Séries temporelles et map reduce `_) * Distribution à base de hash (voir :ref:`hashdistributionrst`) * `Mapper, Reducer, Combiner, Partitionner `_ * 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 :ref:`random walk with restarts ` * Problème des skewed datasets --> clés très mal distribués (voir :ref:`hashdistributionrst`) * 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 `_ (évalusation presseuse, :epkg:`dask`, :epkg:`Spark`, :epkg:`mars`) *Lectures* * `Computer Systems for Big Data `_ (cours à Columbia) * `Map-Reduce Patterns, Algorithms, and Use Cases `_ * `MapReduce: Simplified Data Processing on Large Clusters `_ * `Speeding up Hadoop Builds using Distributed Unit tests `_ *Vidéos* * `Calculer sur des données massives `_ * `Le hachage `_ .. _l-spark-3a: 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 * `From scikit-learn to Spark ML `_ * `Deep Dive into Catalyst `_, `Catalyst — Tree Manipulation Framework `_ * `What is Tungsten for Apache Spark? `_, `Project Tungsten: Bringing Apache Spark Closer to Bare Metal `_ * `Spark SQL: Another 16x times faster after Tungsten `_ * `Databricks `_ *FAQ* * `Avoid GroupByKey `_ * `What is the difference between cache and persist? `_ *Modules* * `spark-sklearn `_ : implémentation d'un grid search distribué pour `scikit-learn `_. * `turicreate `_ : mélange de deep learning et de *spark* .. _l-td3a-start: Getting started, installation, setup ==================================== SPARK +++++ Voir `Spark approximatif `_. .. _l-td3a-biblio: ------------ Bibliographie ============= **Cours** * `Distributed Systems Fundamentals `_ * `Advanced Distributed Systems `_ **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 * `Convergence Properties of the KMeans Algorithm `_ **Liens** * `HackerRank `_ * `15+ Great Books for Hadoop `_ * `A Roundup of Recent Text Analytics and Vis Work `_ * `Don't use Hadoop - your data isn't that big `_ * `Remote Notebook with Azure `_ * `Mahout 1.0 Features by Engine `_ * `Tutorial: Spark-GPU Cluster Dev in a Notebook `_ * `How CPU load averages work (and using them to triage webserver performance!) `_ *(2016/06)* **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 * `rapids `_ : :epkg:`numpy`, :epkg:`pandas` version GPU * `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. Feuilles de routes des années passées ===================================== .. toctree:: :maxdepth: 1 questions/route_3A_2017 questions/cython_python questions/route_3A_2019 questions/route_3A_2020 questions/route_3A_2021 questions/route_3A_2023