Multiprogrammation – quelques liens

Au menu sur cette page :

Vous trouverez ici quelques liens portant sur la multiprogrammation, qui intervient dans la plupart de mes cours, bien qu'il s'agisse, au fond, d'un sujet à part entière. Si vous découvrez d'autres liens dignes d'intérêt, faites-m'en part. De même, signalez-moi des liens brisés ou périmés si vous en rencontrez, ce qui me permettra d'offrir un meilleur service à vous comme à vos collègues.

Pour des texte portant plus spécifiquement...

Généralités

Les sites Wiki décrivant...

Comment se porte la monoprogrammation? Données colligées par Jeff Preshing en 2012 : http://preshing.com/20120208/a-look-back-at-single-threaded-cpu-performance/

Discussion de différentes perspectives architecturales : http://www.possibility.com/wiki/index.php?title=ArchitectureDiscussion

Catalogue de concepts associés au parallélisme et aux systèmes concurrents, répertoriés par Kai Sellgren : https://github.com/kaisellgren/Concurrency-concepts

Les difficultés associées au développement pour des architecturess fortement hétérogènes, typiques des systèmes destinés au High Performance Computing et aux systèmes massivement parallèles, par Michael Wolfe en 2012 : http://www.hpcwire.com/hpcwire/2012-03-19/the_heterogeneous_programming_jungle.html

Une réflexion de Rob Pike sur la question des canaux en multiprogrammation :

Cours en ligne sur la programmation de systèmes concurrents :

Concurrence et réseaux de Pétri :

Quelques articles plus massifs :

Un bref sur la multiprogrammation chez Microsoft (tiré du Code Project, alors lire avec un oeil critique) :

Des réflexions sur le design de systèmes répartis par Ken Arnold, un penseur parfois provoquant :

Est-ce qu'un modèle réparti subsume un modèle centralisé « équivalent »? Une discussion : http://www.markdomowicz.com/index.php?option=com_content&view=article&id=64:distributed-is-not-a-superset-of-client-server-version-control&catid=40:programming&Itemid=60

Principes de multiprogrammation : http://queue.acm.org/detail.cfm?id=1454462

À propos des variables globales : http://software.intel.com/en-us/articles/global-variable-reconsidered/

Sur les difficultés associées à l'écriture du code multiprogrammé :

En 2012, Bartosz Milewski explique qu'à son avis, la multiprogrammation a sonné le glas de la programmation impérative, et que la programmation fonctionnelle est maintenant le chemin à emprunter : http://fpcomplete.com/the-downfall-of-imperative-programming/

Le débit et la latence, texte de 2016 par Pedro Ramalhete : http://concurrencyfreaks.blogspot.ca/2016/08/throughput-vs-latency-and-lock-free-vs.html

Conjecture CALM

La conjecture CALM, ou Consistency as Logicial Monotonicity, suppose que les systèmes répartis deviendront éventuellement cohérents si leur comportement peut être exprimé par un raisonnement de logique monotone.

Dans le monde du jeu vidéo

Modèles de programmation

Quelques modèles de multiprogrammation suivent. La plupart ne sont pas mutuellement exclusifs.

Modèle événementiel

Modèle par acteurs

Les acteurs constituent un modèle de programmation sans partage de données, fait d'entités actives qui transigent par messages asynchrones.

Modèle par tapon

Non, ce n'est pas un nom scientifique.

Modèle par CSP (Communicating Sequential Processes, ou processus séquentiels communiquant entre eux)

Modèle par flux

Modèle sous Android et sous iOS

Autres modèles

L'approche par révisions concurrentes, mise en valeur par Microsoft Research, où chaque tâche obtient une copie (conceptuelle) de tous les états partagés, et où les changement d'états ne sont intégrés que lorsque les tâches se rejoignent, moment où les conflits d'écriture sont résolus de manière déterministe.

Communication

Algorithmes

Quelques algorithmes et quelques familles d'algorithmes parallèles bien connus.

Approche Map/ Reduce

À propos de Map/ Reduce :

L'approche Map/ Reduce a donné naissance à ce que certains ont nommé l'architecture λ :

Traitement parallèle de chaînes de caractères

À propos du traitement de chaînes de caractères :

Allocation dynamique de mémoire

L'allocation dynamique de mémoire sur un ordinateur à plusieurs coeurs ou à plusieurs processeurs :

Comment fonctionne tcmalloc (Thread-Cache Memory Allocator), un texte de James Golick en 2013 :

Accumulation parallèle

Réaliser une accumulation parallèle sur des fonctions qui peuvent ne pas être pures, une proposition de Craig Gidney en 2013 : http://twistedoakstudios.com/blog/Post8355_brute-force-parallelization

Multiples coeurs

Les dernières années des processeurs monocoeurs et le virage vers ce que nous connaissons maintenant, un texte de Jeff Preshing en 2012 : http://preshing.com/20120208/a-look-back-at-single-threaded-cpu-performance

Textes informatifs et semi-rigoureux sur les microprocesseurs contemporains :

Le site Wiki décrivant les processeurs à plusieurs coeurs est : http://en.wikipedia.org/wiki/Multi-core

Diverses considérations architecturales :

Des articles sur le défi derrière la programmation des processeurs à plusieurs coeurs :

Le développement et l'optimisation du code pour un processeur à plusieurs coeurs :

Idem mais pour des programmes pris en charge : http://msdn.microsoft.com/msdnmag/issues/07/10/Futures/default.aspx?loc=fr

Accéder à des masses importantes de données sur un ordinateur à plusieurs processeurs : http://msdn.microsoft.com/msdnmag/issues/01/08/Concur/

Sur les tangentes (plusieurs coeurs généralistes; plusieurs coeurs spécialisés) : http://www.eetimes.com/showArticle.jhtml;?articleID=206105179

Sur le futur de la programmation de processeurs munis de multiples coeurs : http://www.eetimes.com/news/latest/showArticle.jhtml?articleID=206504466

Sur le futur de la programmation à l'aide d'accélérateurs, par Kamil Rocki et Martin Burtscher en 2014 : http://www.hpcwire.com/2014/01/09/future-accelerator-programming/

Les coeurs ne sont pas nécessairement tous égaux : http://gcn.com/articles/2008/12/22/multicore-does-not-mean-equal-core.aspx

À propos du système d'exploitation Barrelfish, projet expérimental de Microsoft d'un système d'exploitation optimisé pour les machines à plusieurs coeurs : http://h-deb.clg.qc.ca/Liens/Systemes-exploitation.html#barrelfish

Avec Windows 7 :

La position d'AMD sur l'approche par hyperthreading : http://blogs.amd.com/work/2010/01/21/it%E2%80%99s-all-about-the-cores/

Faire véritablement le saut au multiples coeurs exigera une réécriture du système d'exploitation Windows, apparemment : http://www.networkworld.com/news/2010/031910-multicore-requires-os-rework-windows.html

Préparer le code pour la parallélisation sur plusieurs coeurs : http://www.drdobbs.com/go-parallel/article/showArticle.jhtml;jsessionid=MUIULNTFUDRZZQE1GHPSKH4ATMY32JVN?articleID=227500610

Il semble que les systèmes d'exploitation actuels (fin 2010) soient plus ou moins appropriés pour des ordinateurs munis de plus de 48 coeurs :

Un programme de tri en parallèle du Code Project, article de 2008 : http://www.codeproject.com/KB/threads/tricky_multicore.aspx

De combien d'échelonnabilité avons-nous besoin? La vision d'Herb Sutter :

Évaluer les interactions asymétriques sur des processeurs à multiples coeurs symétriques, article de 2008 : http://synergy.cs.vt.edu/pubs/papers/scogland-sc2008-symmer.pdf

Synchronisation et multiples coeurs : http://msdn.microsoft.com/en-us/library/ms686355%28VS.85%29.aspx

De l'avis de Vasudevan Thiygarajan, en 2012, la multiprogrammation avec plusieurs threads n'est pas la meilleure approche pour tirer profit au maximum des architectures munies de plusieurs coeurs : http://www.ibm.com/developerworks/java/library/j-nothreads/index.html?ca=drs-

Régler les problèmes de Python face aux ordinateurs à multiples coeurs, une proposition d'Eric Snow en 2015 : https://lwn.net/Articles/650521/

GPU et « programmation multiappareils »

La multiprogrammation utilisant les unités de traitement graphiques, communément nommées GPU (Graphical Processing Unit), est en vogue. Voir aussi Advanced Massive Parallelism (AMP).

Article général de 2010 sur la montée des architectures orientées débit (Throughput-Oriented Architectures) : http://highscalability.com/blog/2010/12/3/gpu-vs-cpu-smackdown-the-rise-of-throughput-oriented-archite.html

Quelques bases de vocabulaire, tirées de Wiki :

À propos d'OpenCL, le Open Computing Language :

Approche alternative, reposant sur la virtualisation des langages, par plusieurs auteurs dont Martin Odersky : http://infoscience.epfl.ch/record/148814/files/paper.pdf

Du GPGPU avec Java : http://www.javacodegeeks.com/2011/09/gpgpu-java-programming.html

Du code hybride CPU/GPU avec Haskell, un texte de Ryan Newton en 2012 : http://parfunk.blogspot.ca/2012/05/how-to-write-hybrid-cpugpu-programs.html?m=1

La technologie CUDA, pour Compute Unified Device Architecture :

Optimiser les accès dans des programmes destinés à des GPU, textes d'Eric Holk en 2012 :

Compiler un programme Rust pour l'exécuter sur un GPU, par Eric Holk en 2012 : http://blog.theincredibleholk.org/blog/2012/12/05/compiling-rust-for-gpus/

Résoudre un labyrinthe à l'aide du GPU, texte de Christopher Wellons en 2014 : http://nullprogram.com/blog/2014/06/22/

L'outil Mapgraph, pour le traitement massivement parallèle de graphes : http://mapgraph.io/

Le GPLGPU, un moteur graphique sous licence GPL v3 : http://gplgpu.com/?p=88

Techniques pour partager de la mémoire entre CPU et GPU, à l'aide de Swift, en 2014 : http://memkite.com/blog/2014/12/30/example-of-sharing-memory-between-gpu-and-cpu-with-swift-and-metal-for-ios8/

Programmer pour un GPU de NVIDIA, par Yosef Kreinin en 2015 : http://yosefk.com/blog/simd-simt-smt-parallelism-in-nvidia-gpus.html

Cas vécu d'optimisation de code dans lequel les mises en attente lors de transferts de données entre le CPU et GPU étaient au coeur du problème, relaté par Raja Bala en 2015 : https://software.intel.com/en-us/articles/removing-cpu-gpu-sync-stalls-in-galactic-civilizations-3

Ce qu'il faut savoir à propos de la fréquence du GPU, selon Ben Widawsky en 2015 : https://bwidawsk.net/blog/index.php/2015/05/a-bit-on-intel-gpu-frequency/

L'« initiative Boltzmann » proposée par AMD pour faciliter le recours programmatique à des GPU : http://www.amd.com/en-us/press-releases/Pages/boltzmann-initiative-2015nov16.aspx

Combiner programmation sur le GPU et variables atomiques, par Elmar Westphal en 2015 : https://devblogs.nvidia.com/parallelforall/voting-and-shuffling-optimize-atomic-operations/

Les GPU et Intel, une présentation de 2015 par Jason Ross, Ken Lueh et Subramaniam Maiyuran : https://software.intel.com/sites/default/files/managed/89/92/Intel-Graphics-Architecture-ISA-and-microarchitecture.pdf

Advanced Massive Parallelism (AMP)

L'approche AMP, pour Advanced Massive Parallelism, est survolée sur ../Sujets/Parallelisme/AMP.html

Langages

Quelques considérations d'ordre général :

Ce qui suit liste quelques particularités de multiprogrammation de divers langages. Pour en savoir plus sur ces langages et sur bien d'autres, vous pouvez examiner ceci.

Ada et la concurrence :

C et la concurrence :

Parallélisme et concurrence avec C++ (la plupart en lien avec C++ 11) :

Parallélisme et multiprogrammation en Clojure :

Parallélisme avec C# :

La concurrence en D :

Erlang et la concurrence :

Concurrence avec F# (voir aussi les liens pour C# plus haut, étant donné que les deux partagent les mêmes outils) :

Parallélisme avec Haskell (voir aussi les collections concurrentes) :

Avec Go :

Avec Java :

Officiellement, il n'y a pas de threads en JavaScript, mais...

Avec Objective-C :

Avec Perl :

Réflexions sur la multiprogrammation avec Python :

Parallélisme avec R :

Multiprogrammation avec Ruby :

Concurrence avec Rust :

Parallélisme avec Scala :

Parallélisme avec Swift :

Multiprogrammation avec VB.NET :

Outils et API

Pour plus d'informations sur des API particulières en soutien aux threads, voir ../Sujets/Parallelisme/Bref-unites-execution.html#thread

La populaire API qu'est OpenMP est sommairement décrite ici : ../Sujets/Parallelisme/OpenMP.html

Un survol de la bibliothèque Threading Building Blocks, ou TBB, est offert ici : ../Sujets/Parallelisme/TBB.html

La technologie Ct, de Intel, se présente comme une API pour C++ et se concentre sur le parallélisme des données : http://software.intel.com/en-us/data-parallel/

Un survol de la technologie MPI, pour Message Passing Interface, un standard de facto du monde des calculs à haute performance (HPC, pour High Performance Computing) est offert sur ../Sujets/Parallelisme/MPI.html

Le projet PSTL, pour Parallel STL : http://www.extreme.indiana.edu/hpc++/docs/overview/class-lib/PSTL/ (ce projet est rendu quelque peu caduque du fait que la bibliothèque standard de C++ offre des algorithmes parallèles depuis C++ 17)

Le projet STAPL, pour Standard Template Adaptive Parallel Library, développé à l'Université du Texas (en partie par Bjarne Stroustrup) : https://parasol.tamu.edu/groups/rwergergroup/research/stapl/

Le Parallel Studio d'Intel : http://software.intel.com/en-us/articles/intel-parallel-studio-home/

Les collections concurrentes proposées par Intel :

L'extension Cilk Plus d'Intel, pour C et C++ :

Le projet GNU UPC (pour Unified Parallel C) : http://gcc.gnu.org/projects/gupc.html

Une nouvelle approche sous MacOS X, nommée le Grand Central Dispatch :

La bibliothèque Boost.InterProcess, pour communication entre processus : http://www.boost.org/doc/libs/1_39_0/doc/html/interprocess.html

Le compilateur Sieve est un moteur prenant en charge la parallélisation du code C++. Pour quelques articles sur le sujet, voir :

Performance des entrées/ sorties asynchrones de Java :

Bibliothèque s4, pour les calculs répartis sur des flux :

Les threads et Qt :

Parallélisme et technologies Microsoft :

Outils GNU :

Paralléliser des tâches avec xargs : http://www.spinellis.gr/blog/20090304/

L'appel système fork() : ../Sujets/Parallelisme/Bref-fork.html

Le compilateur par4all, voué à la parallélisation automatique de programmes Fortran et C :

SIMD (Single Instruction, Multiple Data)

Une instruction SIMD traite plusieurs données d'un seul coup. Lorsqu'un algorithme est écrit de manière à traiter une vaste quantité de données de manière semblable, le recours à des instructions SIMD peut réduire le temps de calcul de manière significative.

Faire des calculs avec des instructions SIMD ::

Structure d'une instruction SIMD, par Arvid Gerstmann en 2016 : https://arvid.io/2016/12/09/simd-instruction-format/

Risques

La multiprogrammation est un jouet pour grandes personnes, porteur d'un grand nombre de risques qui lui sont propres. Plusieurs font partie de la grande famille des des conditions de course et sont répertoriées sur : ../Sujets/Parallelisme/Bref-conditions-course.html

Pour un survol de quelques-uns des principaux risques associés à la multiprogrammation, voir ce texte de 2014 par Austin G. Walters : http://austingwalters.com/multithreading-common-pitfalls/

Joe Duffy, en 2010, explique les limites de readonly avec .NET : http://www.bluebytesoftware.com/blog/2010/07/01/WhenIsAReadonlyFieldNotReadonly.aspx

Certaines API ne passent pas bien le cap de la multiprogrammation.

Résoudre 11 problèmes dans du code multiprogrammé sous .NET, selon Joe Duffy en 2008 :

Synchronisation et partage des ressources

Pour les questions de synchronisation, voir ../Sujets/Parallelisme/Synchronisation.html

Algorithmes

Quelques algorithmes bien connus dans le monde de la synchronisation en situation de multiprogrammation (la plupart des liens qui suivent mènent sur des sites Wiki) :

Atomicité

J'ai regroupé des informations sur ce sujet dans ../Sujets/Parallelisme/Bref-atomiques-primitives.html

Pour le cas plus précis des opérations Compare and Swap (CAS), voir ../Sujets/Parallelisme/Bref-atomiques-primitives.html#xchg pour des détails.

Exceptions

Exceptions et le Concurrency Runtime de Microsoft :

Faux partage

Le faux partage, ou False Sharing, est un obstacle à l'échelonnabilité résultant du fait que, dans un ordinateur à plusieurs coeurs ou à plusieurs processeurs, il peut arriver que la Cache d'un coeur contienne des données qui peuvent être modifiées par un autre processeur ou par un autre coeur.

Les données sont lues en antémémoire par petits blocs qu'on nomme des Cache Lines; le faux partage résulte d'une modification à une Cache Line forçant sa mise à jour dans les antémémoires d'autres coeurs ou d'autres processeurs, ce qui entraîne un ralentissement inutile et très coûteux.

Noyau d'un système d'exploitation

Dans le monde du noyau de Linux :

Il semble que le noyau de Linux souffre (ou, du moins, ait souffert) d'une synchronisation sur la base d'un « gros verrou », si on se fie à cet article de Jeremy Andrews en 2008 : http://kerneltrap.org/Linux/Removing_the_Big_Kernel_Lock

Optimisation et règles

Outils

Quelques outils de synchronisation bien connus sont brièvement décrits dans les sections ci-dessous.

Futex

J'ai regroupé les textes sur ce sujet dans ../Sujets/Parallelisme/Synchronisation.html#avec_verrou

Futures

J'ai regroupé les textes sur ce sujet dans ../Sujets/Parallelisme/futures.html

Mémoire partagée

Le partage brut de mémoire est une approche traditionnellement utilisée pour les échanges à débit rapide entre processus et entre threads. Cela dit, un échange aussi direct comporte des risques.

Mémoire transactionnelle

J'ai regroupé les lies et les textes à ce sujet dans ../Sujets/Parallelisme/memoire_transactionnelle.html

Moniteurs

Terme général pour désigner un objet susceptible d'être manipulé en toute sécurité de manière concurrente par plusieurs threads.

Un Wiki : http://en.wikipedia.org/wiki/Monitor_%28synchronization%29

Sections critiques, sémaphores, mutex

J'ai regroupé les textes sur ce sujet dans ../Sujets/Parallelisme/Synchronisation.html#avec_verrou

Pratiques

En 2007, Herb Sutter nous rappelle qu'il ne faut pas appeler de code dont on ne connaît pas l'implémentation à l'intérieur d'une section critique : http://www.drdobbs.com/architecture-and-design/202802983?greturn=true&greturn=true

En 2009, Chris Forbes explique qu'à son avis, l'idéal est de s'assurer que tout thread puisse être suspendu au moment opportun : http://blogs.ijw.co.nz/chris/index.php/2009/04/theres-a-third-hard-thing-about-concurrency/

Une technique de partage de données entre threads à partir de transfert de responsabilité, proposée par Mark Lee en 2012 : http://www.altdevblogaday.com/2012/01/11/safer-data-sharing-between-threads/

Dans ce texte de 2012, Bruce Dawson nous rappelle que l'attente active (Busy Waiting) est rarement une bonne idée d'un point de vue performance, consommation d'énergie, équilibre systémique, etc. : http://randomascii.wordpress.com/2012/06/05/in-praise-of-idleness/

Structures de données

Voir aussi la synchronisation sans verrous.

Quelques structures de données pensées pour les programmes concurrents, un texte d'Arpan Sen en 2012 : http://www.ibm.com/developerworks/aix/library/au-multithreaded_structures1/index.html

Files asynchrones pour des tâches, par Richard Bone en 2012 : http://99designs.com/tech-blog/blog/2012/02/17/async-task-queues/

Collections immuables sous C# avec opérations en temps constant :

Temps

Un texte fondamental sur la question de la synchronisation et du temps, qu'on m'a fait lire quand j'étais étudiant :

Comprendre les horloges vectorielles (Vector Clocks) :

Le temps sous Microsoft Windows, de l'avis de Joseph M. Newcomer en 2011 : http://www.flounder.com/time.htm

Dossiers divers

Quelques considérations diverses sur la multiprogrammation et la synchronisation, pêle-mêle.

Déboguer et tester

La littérature sur les tests et le débogage des systèmes multiprogrammés est encore en période de maturation, mais un bref aperçu de la raison pour laquelle les tests unitaires ne suffisent pas en ce sens peut être trouvée sur : http://www.artima.com/lejava/articles/javaone_2008_andy_chou.html

Certains tests nous révèlent des optimisations qui, au fond, n'en sont pas vraiment : http://antirez.com/post/fsync-different-thread-useless.html

Provoquer des bogues de concurrence (texte de 2011) : http://blog.corensic.com/2011/08/22/accelerating-concurrency-bugs/

On trouve parfois des bogues de concurrence à des endroits surprenants ou inattendus, par exemple lors de la finalisation des objets, comme en atteste ce texte de 2012 : http://wingolog.org/archives/2012/02/16/unexpected-concurrency

Gestion de la mémoire

Pour plus d'articles sur ce sujet, voir Gestion-memoire--Liens.html


Valid XHTML 1.0 Transitional

CSS Valide !