Modèles parallèles actuels pour le calcul

Les années 80 ont donné naissance aux modèles PRAM et BSP de calcul parallèle. Il semble que l'apogée des deux modèles remonte à la fin des années 80 et au début des années 90.

Ces domaines sont-ils toujours actifs en termes de recherche d'algorithmes parallèles? Existe-t-il des modèles plus récents et plus sophistiqués pour le calcul parallèle? Les modèles généraux sont-ils toujours en vogue, ou les chercheurs tentent-ils de se spécialiser avec le GPGPU ou le calcul basé sur le cloud à la mode?

Il existe un certain nombre de modèles flottant, mais certains des plus saillants sont:

1. Les modèles MUD et Mapreduce qui concernent principalement la capture du cadre MapReduce, mais plus généralement peuvent être considérés comme des modèles de calcul distribués en parallèle
2. Les différents modèles multicœurs qui ont été proposés (mais en aucun cas la norme pour l'instant)

Il y a eu un atelier le mois dernier au DIMACS sur ce sujet: parcourir les résumés vous donnera plus de conseils.

Je m'excuse au préalable pour le format de blog de ma réponse. Je ne pouvais pas m'empêcher de faire un petit aperçu du monde de l'informatique parallèle.

Vous pouvez classer les modèles de programmation parallèle en deux catégories: les modèles de flux de contrôle et de flux de données.

Les modèles de flux de contrôle tentent de faire fonctionner le parallélisme dans le contexte d'un programme de contrôle explicite, essentiellement tous les ordinateurs programmables d'aujourd'hui. Le problème fondamental abordé est qu'une telle «architecture Von Neumann» n'a pas été conçue pour une exécution parallèle, mais pour des calculs séquentiels efficaces. Le parallélisme dans un tel contexte est obtenu en dupliquant des parties des modules de base (mémoire, contrôle, arithmétique).

Dupliquer uniquement l'arithmétique vous donne des instructions SIMD, toutes les ALU partagent le même compteur de programmes (PC) et exécutent donc toujours la même opération en parallèle, bien que sur des données différentes.

Dupliquer ALU et le PC mais garder le séquenceur d'instructions à l'intérieur de l'unité de contrôle vous donne une exécution Out of Order (OoO) qui produit un certain parallélisme de pipeline. Dans cette catégorie, vous avez également le très long mot d'instruction (VLWI) et les techniques de prédiction de branche. Cependant, vous voyez rarement cette catégorie au niveau logiciel.

Aller un peu plus loin consiste à dupliquer l'ensemble du `` cœur '' mais en gardant la mémoire partagée, ce sont les processeurs multicœurs actuels qui vous donnent le parallélisme des tâches (ou des threads). Partager la mémoire dans ce contexte vous pose des problèmes de concurrence très, très difficiles et subtils . Les calculs parallèles sur le multicœur actuel tournent donc complètement autour des problèmes de synchronisation / concurrence, de l'équilibre soigneux des performances (pas de synchronisation) et de la sémantique souhaitée (sémantique d'exécution séquentielle totalement synchronisée). Des exemples de cela est la PRAM ou plus populaire de nos jours le Cilk ofshoots tels que fork / join ( IntelTBB , Java.Utils.Concurrency). Les modèles CSP et Actor sont des modèles de concurrence, mais comme mentionné ci-dessus, la concurrence et le parallélisme deviennent flous dans un environnement de mémoire partagée. Le parallélisme nb est pour les performances, la concurrence pour maintenir une sémantique correcte.

La duplication de mémoire vous donne également des ordinateurs en réseau qui sont programmés avec MPI et ses semblables ou tout simplement d'étranges architectures non Von Neumann telles que les processeurs de réseau sur puce (processeur cloud, Transputer, Tilera). Les modèles de mémoire tels que UMA ou NUMA tentent de maintenir l'illusion de la mémoire partagée et peuvent exister au niveau logiciel ou matériel. MPI maintient le parallélisme au niveau du programme et ne communique que via le passage de messages. Le passage de messages est également utilisé au niveau matériel pour la communication et la concurrence (Transputer).

La deuxième catégorie est constituée des modèles de flux de données . Celles-ci ont été conçues à l'aube de l'ère informatique comme un moyen d'écrire et d'exécuter des calculs parallèles, en évitant la conception de Von Neumann. Ceux-ci sont tombés en vogue (pour le calcul parallèle) dans les années 80 après une augmentation exponentielle des performances séquentielles. Cependant, de nombreux systèmes de programmation parallèle tels que Google MapReduce, Dryad de Microsoft ou Collections simultanées d'Intel sont en fait des modèles de calcul de flux de données. À un certain point, ils représentent les calculs sous forme de graphique et l'utilisent pour guider l'exécution.

En spécifiant des parties des modèles, vous obtenez différentes catégories et sémantiques pour le modèle de flux de données. À quoi restreignez-vous la forme du graphique: DAG (CnC, Dryade), arbre (mapreduce), digraphe? Existe-t-il une sémantique de synchronisation stricte ( Lustre, programmation réactive]? Désactivez-vous la récursivité pour pouvoir avoir un calendrier statique (StreaMIT) ou offrez-vous une puissance plus expressive en ayant un planificateur dynamique (Intel CnC)? Y a-t-il une limite sur le nombre de fronts entrants ou sortants? La sémantique de déclenchement permet-elle de déclencher le nœud lorsqu'un sous-ensemble des données entrantes est disponible? Sont des flux de données de bords (traitement de flux) ou des jetons de données uniques (affectation unique statique / dynamique). Pour les travaux connexes, vous pouvez commencer par regarder les travaux de recherche sur le flux de données de personnes comme Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.

Edit: Par souci d'exhaustivité. Je dois souligner qu'il existe également des modèles parallèles axés sur la réduction et sur les modèles. Pour les stratégies de réduction, vous avez généralement une réduction de graphique et une réduction de chaîne. Haskell utilise essentiellement la réduction de graphes, qui est une stratégie très efficace sur un système séquentiel à mémoire partagée. Les doublons de réduction de chaîne fonctionnent, mais ont une propriété de mémoire privée qui la rend mieux adaptée pour être implicitement parallélisée. Les modèles basés sur des modèles sont les langages logiques parallèles, tels que le prologue simultané. Le modèle Actor est également un modèle basé sur des modèles, mais avec des caractéristiques de mémoire privée.

PS. J'utilise le terme «modèle» au sens large, couvrant les machines abstraites à des fins formelles et de programmation.

Pour les architectures de transmission de messages, un modèle qui est assez similaire à BSP mais plus facile à gérer et à une analyse des performances proche de ce que vous obtenez vraiment sur une vraie machine est certainement CGM ou Coalse Grained Multicomputer. Il a été proposé par Frank Dehne, et vous trouverez de nombreux articles intéressants présentant des algorithmes développés dans ce contexte.

CGM s'adapte aux architectures à grain grossier en supposant p processeurs, chacun avec O (n / p) mémoire locale et la taille de l'entrée n beaucoup plus grande (ordres de grandeur séparés) que p, c'est-à-dire p≪n. Par conséquent, le modèle correspond bien mieux que d'autres aux architectures actuelles; il a été étudié de manière approfondie. Le modèle est basé sur les hypothèses suivantes: (i) les algorithmes exécutent ce qu'on appelle des super-étapes, qui consistent en une phase de calcul local et une phase de communication interprocesseur avec synchronisation de barrière intermédiaire, (ii) tous les p processeurs ont accès à O (n / p) mémoire locale, (iii) à chaque étape supérieure, un processeur peut envoyer et recevoir au plus O (n / p) éléments et (iv) le réseau de communication entre les processeurs peut être arbitraire. Dans ce modèle, un algorithme est évalué par rapport à sa durée de calcul et au nombre de cycles de communication. Bien que le modèle soit simple, il fournit néanmoins une prédiction raisonnable des performances réelles des algorithmes parallèles; en effet, les algorithmes parallèles pour les CGM ont généralement une analyse de complexité théorique très proche des temps réels déterminés expérimentalement lors de leur mise en œuvre et de leur analyse comparative.

La mémoire externe parallèle (PEM) est une combinaison naturelle d'une machine à mémoire partagée de style PRAM avec le modèle de mémoire externe. Il se concentre sur les implications des caches privées.

D'après ce que je sais, les modèles BSP et LogP sont utilisés aujourd'hui pour les algorithmes distribués. De plus, depuis l'informatique GPU, les PRAM redeviennent populaires, mais il faut inclure les hiérarchies de mémoire dans l'analyse. Vous pouvez vérifier le modèle UPMH (hiérarchie de mémoire parallèle uniforme) qui complète bien PRAM.

B. Alpern, L. Carter, E. Feig et T. Selker. Le modèle de hiérarchie de mémoire uniforme du calcul. Algorithmica, 12: 72–109, 1994. 10.1007 / BF01185206.

Bowen Alpern, Larry Carter et Jeanne Ferrante. Modélisation d'ordinateurs parallèles en tant que hiérarchies de mémoire. Dans In Proc. Modèles de programmation pour ordinateurs massivement parallèles, pages 116– 123. IEEE Computer Society Press, 1993.

Pour le calcul GPU également, il a été proposé un modèle de calcul théorique; le modèle K:

Gabriele Capannini, Fabrizio Silvestri et Ranieri Baraglia. K-model: Un nouveau modèle de calcul pour les processeurs de flux. Dans les actes de la 12e conférence internationale 2010 de l'IEEE sur le calcul et les communications à haute performance, HPCC '10, pages 239–246, Washington, DC, États-Unis, 2010. IEEE Computer Society.

Enfin, j'ai vu des automates cellulaires (CA) modélisés comme des ordinateurs parallèles, personnellement, je pense que c'est un sujet de recherche très intéressant. Qui sait à l'avenir les processeurs se feront de cette façon, comme de petits espaces de calcul. Je n'ai pas de référence solide pour cela, vous pouvez regarder sur le web.

Des programmes purement fonctionnels permettent l'exécution parallèle d'expressions indépendantes. Par conséquent, je les considérerais comme des modèles de calcul parallèles.

Je préfère l' approche Bader-Jaja (voir section 2.1). Vous modélisez la complexité comme un problème de transmission de messages. Pour chaque message envoyé, il existe à la fois une variable de latence pour initier la communication et une variable de bande passante.

$t$$u$$m$$p$$t$$u$$m$$p$

vous mentionnez spécifiquement le cloud computing. il y a eu en quelques années seulement une intense innovation dans ce domaine avec le cloud de calcul élastique d'Amazon, le moteur d'application google et divers outils et leurs "modèles" de traitement parallèle conceptuel.

les outils open source spéciaux incluent les bases de données Google Mapreduce , Apache Hadoop et NoSQL qui émergent comme de nouvelles normes solides et largement adaptées dans les "meilleures pratiques" et "modèles de conception" des algorithmes de parallélisation. memcacheD est également de plus en plus utilisé comme base de données distribuée en mémoire. un exemple de ceci est utilisé chez Facebook décrit dans un article récent [1].

[1] Nombreux magasins de valeurs clés de Berezecki et al

un autre angle à ce sujet. Certes, cela pourrait être considéré comme quelque peu obscur ou marginal par certains, mais il existe un certain travail sur la parallélisation, d'une manière générale, des algorithmes probabilistes, qui sont prétendument quelque peu naturellement adaptés au parallélisme.

voir par exemple les calculs probabilistes parallèles sur un groupe de postes de travail Radenski, Vann, Norris:

Les algorithmes probabilistes sont des méthodes approximatives à calcul intensif pour résoudre des problèmes insolubles. Les algorithmes probabilistes sont d'excellents candidats pour les calculs de cluster car ils nécessitent peu de communication et de synchronisation. Il est possible de spécifier une structure de contrôle parallèle commune comme algorithme générique pour les calculs de grappes probabilistes. Un tel algorithme parallèle générique peut être collé avec des algorithmes séquentiels spécifiques au domaine afin de dériver des solutions parallèles approximatives pour différents problèmes insolubles. Dans cet article, nous proposons un algorithme générique pour les calculs probabilistes sur un cluster de postes de travail. Nous utilisons cet algorithme générique pour dériver des algorithmes parallèles spécifiques pour deux problèmes d'optimisation discrets: le problème du sac à dos et le problème du vendeur ambulant.

au cas où ce ne serait pas clair, la "structure de contrôle parallèle commune en tant qu'algorithme générique", mentionnée avec le calcul probabiliste et la conversion globale, est le "modèle".

on pourrait faire valoir que le calcul probabiliste n'est pas strictement informatique classique ou Turing complet. alors notez qu'il y a un peu de travail à lier le classique avec le calcul probabiliste également spécifiquement dans un contexte parallèle, par exemple

Raisonnement sur les programmes parallèles probabilistes par Rao:

L'utilisation de la randomisation dans la conception et l'analyse d'algorithmes promet des algorithmes simples et efficaces pour des problèmes difficiles, dont certains peuvent ne pas avoir de solution déterministe. Ce gain de simplicité, d'efficacité et de solvabilité se traduit par un compromis entre la notion traditionnelle d'exactitude absolue des algorithmes et une notion plus quantitative: l'exactitude avec une probabilité comprise entre 0 et 1. L'ajout de la notion de parallélisme au déjà non intuitif L'idée de randomisation rend le raisonnement sur les programmes parallèles probabilistes d'autant plus tortueux et difficile. Dans cet article, nous abordons le problème de la spécification et de la dérivation des propriétés des programmes parallèles probabilistes qui sont soit déterministes soit avec la probabilité 1.

bien sûr, l'informatique QM est très similaire à l'informatique probabiliste (une belle référence qui souligne qu'il s'agit de One Complexity Theorist's View of Quantum Computing by Fortnow ) & il y a un indice que ces approches pourraient être étendues là-bas, par exemple dans le travail en simulation parallèle de QM.

cela sera considéré comme controversé par certains, et même les partisans de cet angle devront l'admettre dans les premiers stades de la recherche, mais en gros, l'informatique quantique semble avoir de nombreux liens avec le parallélisme et le calcul parallèle. les références sont actuellement éparpillées mais un thème émergent peut être vu par un chercheur déterminé.

peut-être que la meilleure connexion est avec l' algorithme de recherche Grovers qui s'est récemment révélé plus général dans le sens où il est utilisable pour accélérer la plupart des problèmes NP complets en général [5]. L'algorithme Grovers semble avoir une forte analogie / connexion avec les algorithmes de recherche de bases de données parallèles. les meilleurs algorithmes série classiques ne peuvent pas atteindre les mêmes performances, mais au moins une autorité a récemment soutenu que les approches QM pour la recherche ne surpassent pas réellement les algorithmes classiques parallélisés. [1]

des preuves supplémentaires sont des schémas qui examinent explicitement le parallélisme dans la recherche quantique, par exemple [2]. des simulateurs quantiques ont également été proposés qui sont basés sur un traitement parallèle / distribué [3] [4] et parce que le schéma s’adapte bien et conduit à des simulations efficaces et exploitables (30 qubits sont simulés dans la référence [3]), cette conversion n'est certainement pas une simple coïncidence et indique un pont plus profond entre l'informatique classique parallèle et l'informatique QM, mais probablement jusqu'à présent découvert.

[1] La recherche quantique est-elle pratique? par Viamontes et al

[2] Recherche quantique exacte par des schémas de discrimination unitaires parallèles par Wu / Dian

[3] Simulateur parallèle à usage général pour l'informatique quantique par Niwa, Matsumoto, Imai.

[4] calcul quantique distribué efficace par Beals et al 2012

[5] Résolution de problèmes complets de NP avec la recherche quantique par Furer 2008