3A - Projets informatiques#
Travail attendu#
Le projet a pour objectif l’implémentation d’un algorithme réparti, soit en utilisant le calcul sur GPU, soit via Map/Reduce, soit en implémentant vous-même la répartition des calculs sur plusieurs machines (virtuelles) via des primitives telles que MPI ou des Key-Value Pair Storages. Les technologies proposées sont donc :
n’importe quelle technologie sur CPU, une option proposée est un projet utilisant ;epkg:python, cython et openmp. Les projet td3a_cpp ou td3a_cpp_deep peuvent être utilisés comme point de départ.
Vous êtes libres de traiter l’algorithme de votre choix avec la technologie de votre choix avec la contrainte que l’algorithme implémenté soit distribué par votre implémentation et non par la librairie que vous utilisez. Nous vous en proposons certains dans les articles ci-dessous.
A souligner dans le rapport et le code
GPU : indiquer les parties parallélisées, les frontières entre CPU et GPU, une estimation du coût de l’algorithme CPU / GPU / nombre de verrous.
Calcul distribué : indiquer les parties parallélisées, les variables partagées, si cela est fait via un thread ou un processus, une estimation du coût de l’algorithme communication / CPU / nombre de verrous.
Suggestions d’articles#
Articles ou sujet que vous ne pouvez plus choisir
Map/Reduce Affinity Propagation Clustering Algorithm ou Parallel Hierarchical Affinity Propagation with MapReduce
Algorithme k-means clustering
2014-2015
Algos de PageRank (p106)
2015-2016
Multi-Block ADMM for Big Data Optimization in Modern Communication Networks, optimisation distribuée (ADMM)
A scalable system for primal-dual optimization, optimisation sous contrainte avec Map/Reduce et Spark
Scalable Models for Computing Hierarchies in Information Networks, Distributed Random Walks with Restart
Optimally Pruning Decision Tree Ensembles With Feature Cost, voir section 5
2016-2017
The Part-Time Parliament, ce papier introduit l’algorithme Paxos qui gère les problèmes de consensus entre machines. Une machine souhaite déléguer un travail à une autre mais elle a le choix. Comment s’assurer qu’une seule et une seule machine ne fait ce travail ? On pourra traiter n’importe qu’elle autre variance de l’algorithme plus récente.
Schönhage-Strassen Algorithm with MapReduce for Multiplying Terabit Integers
A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems
Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework
A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems
2017-2018
Large-Scale Matrix Factorization with Distributed Stochastic Gradient Descent
weighted minhash on gpu helps to find duplicate github repositories (article de blog)
2018-2019
Affinity Clustering: Hierarchical Clustering at Scale (voir également Spinner: Scalable Graph Partitioning in the Cloud, Fennel: Streaming Graph Partitioning for Massive Scale Graphs, METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering, Balanced Label Propagation for Partitioning Massive Graphs)
DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems
2019-2020
Anatomy of High-Performance Many-Threaded Matrix Multiplication
OpenMP parallelization of multiple precision Taylor series method
Programming Parallel Dense Matrix Factorizations with Look-Ahead and OpenMP
2020-2021
Nous vous recommandons d’adopter la démarche suivante:
implémentation et débugging sur un petit jeu de données synthétiques où les choses sont sensées bien se passer et la taille du jeu de données rend le debugging plus rapide,
application à un vrai jeu de données que vous aurez sélectionné sur un des sites suivants, DGML, Stanford Large Network Dataset Collection, UCI Machine Learning Repository ou autre (voir Source de données), cette approche est aussi valable que de générer des jeux de données articielles de tailles différentes.
Le site Kaggle (2) référence de nombreuses compétitions intéressantes. Toutefois, avant d’utiliser les données Kaggle, je vous encourage à lire les articles Date use for teaching after competition concludes et Using a Kaggle contest as a term project. Les règles peuvent varier d’un projet à l’autre, prenez soin de les lire avant de choisir un projet car on ne peut pas tout faire avec les données disponibles sur ce site.