Modèles parallèles actuels pour le calcul

30

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?

Nicholas Mancuso
la source

Réponses:

19

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.

Suresh Venkat
la source
L'atelier DIMACs est génial! Merci.
Nicholas Mancuso
3
Il y avait eu un atelier plus tôt en 2009 umiacs.umd.edu/conferences/tmc2009 qui m'a semblé être encore plus affûté que le récent DIMAC. Leslie Valiant y a présenté le modèle Multi-BSP (discuté plus en détail lors de l'atelier de cette année), et Phil Gibbons d'Intel a présenté une théorie provocatrice : endormi au passage à plusieurs cœurs qui mérite d'être examiné. Pour moi, l'atelier DIMAC était beaucoup trop axé sur MapReduce, que Google n'utilise plus pour construire son index Web.
András Salamon
c'est vrai. J'avais oublié la précédente.
Suresh Venkat
22

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.

Du boeuf
la source
Je ne comprends pas comment mapreduce forme un arbre. Pourriez-vous expliquer?
Riko Jacob
@Riko Jacob, disons que vous mappez '+' à (1 2 3 4), conceptuellement, cela crée une arborescence d'application avec '+' à chaque nœud et chaque nombre sous forme de feuilles. réduire (ou replier si vous êtes de haskel) réduira chaque nœud avec les données de ses enfants.
Boeuf
K2,2
Si vous ne tenez pas compte de la création du graphique lui-même (par exemple en mappant a, b aux paires clé / valeur), vous obtenez deux arbres faisant la réduction, avec un peu de bonne volonté :) Peut-être que c'est plus un graphique connecté en k ou en treillis comme tu dis. Vous avez raison, c'est un peu plus général qu'un simple arbre. J'essayais de faire une distinction avec les structures de flux de données DAG plus générales.
Boeuf
8

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.

Massimo Cafaro
la source
4

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.

Riko Jacob
la source
4

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.

labotsirc
la source
3

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.

Riko Jacob
la source
Il n'y a pas de modèle de coût particulier associé à la programmation fonctionnelle, donc cela ne répond pas à la question. Voir cstheory.stackexchange.com/questions/376/…
Charles Stewart
2
Le mécanisme d'évaluation de ces langages basés sur le lambda-calcul est la réduction, qui n'a pas vraiment de correspondance directe avec le matériel réel. C'est pourquoi Haskell doit encore introduire des constructions parallèles explicites comme «par». référence: csg.csail.mit.edu/projects/languages/ph.shtml
Beef
3

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.

tumptump

Chad Brewbaker
la source
-3

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

vzn
la source
encore. Je demande des modèles ou des calculs parallèles. Pas d'outils. MapReduce est l'un de ces modèles. Mais Hadoop et NoSQL ne le sont pas. Hadoop est une réification Java de MapReduce. NoSQL est un modèle de stockage de clés détendu d'après ce que je peux dire.
Nicholas Mancuso
MapReduce a commencé comme un outil et est passé à un modèle grâce à une utilisation / adoption généralisée. même avec les autres. Hadoop n'est pas identique à MapReduce, mais peut-être similaire. oui, je suppose que j'ai été renversé par la réponse de Suresh qui incluait MapReduce. même étant donné qu'ils inspirent / pollinisent / conduisent une théorie solide plus tard comme MapReduce l'a fait ... mon mauvais = (
vzn
2
le fait est que vous ne répondez pas à la question. la politique ici est que les suggestions tangentiellement liées à la question ne sont pas des réponses acceptables. si vous n'aimez pas cette politique, vous pouvez choisir de ne pas participer. si vous aviez des idées réelles sur la façon de modéliser un système parallèle dans le monde réel, ce serait plus sur le sujet (bien que ce ne soit toujours pas une réponse à la question posée)
Sasho Nikolov
-3

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.

vzn
la source
-6

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

vzn
la source
@vnz, cela semble être au mieux un méli-mélo aléatoire de concepts quantiques. Googler "quantum parallèle" et lister les résultats ici ne sert à rien pour moi et pour les autres qui lisent ceci. Je pense qu'il serait préférable que la communauté réponde réellement aux réponses avec lesquelles vous vous sentez à l'aise et bien informé, plutôt que de simplement vous précipiter pour les points de réputation. Il n'est pas constructif et peut-être malhonnête de considérer le calcul quantique comme une recherche parallèle. Le calcul quantique a, pour reprendre votre description, des "analogies / connexions fortes" avec recherche probabiliste, non parallèle.
Nicholas Mancuso
Je ne sais pas ce que le dogme est enseigné dans les salles de classe, mais si quelqu'un là-bas a en fait une RÉFÉRENCE plutôt que de simples ASSERTIONS BASES qui indiquent pourquoi il n'y a aucune validité à une correspondance non découverte à ce jour de QM accomplissant un calcul classique parallèle .... Je vais LIRE IL. Le calcul QM renvoie des réponses précises ala / eg shor factororing sinon ce n'est pas un système de calcul réel ..... il y a aussi d'autres moyens que ceux que j'esquisse pour démontrer que le calcul QM doit être équivalent au calcul classique parallèle dans un certain sens ... peut-être car ce n'est pas dans un manuel, ça doit être faux hein !!
vzn
Il y a tout un cours gratuit sur l'informatique quantique ici: coursera.org cela peut clarifier les choses pour vous.
Nicholas Mancuso
ps comme pour "méli-mélo" ... essayez en fait de LIRE LES REFS .. ou peut-être juste de les effleurer dans votre cas wink =)
vzn
1
(6.) Votre référence. [5] décrit les façons dont l'algorithme de Grover peut être étendu, encore une fois sans aborder le parallélisme que vous recherchez dans le calcul quantique. En résumé: votre interprétation selon laquelle il existe des liens entre le calcul quantique et parallèle semble dériver de l'interprétation de nombreux mondes de QM. Bien qu'il ne soit pas obscur, il n'est pas non plus controversé et ne nous permet certainement pas de décrire de manière productive le calcul quantique comme un "calcul en parallèle", sauf dans la mesure où nous ne voyons pas ces calculs ... ce qui n'est pas un argument solide pour leur présence.
Niel de Beaudrap