Quel est le contraire de & 8282; embarrassamment parallèle & # 8221 ;?

Question

Selon Wikipedia, un "parallèle embarrassant" Le problème est un problème pour lequel peu ou pas d’efforts sont nécessaires pour séparer le problème en plusieurs tâches parallèles. Le lancer de rayons est souvent cité en exemple car chaque rayon peut, en principe, être traité en parallèle.

Évidemment, certains problèmes sont beaucoup plus difficiles à mettre en parallèle. Certains peuvent même être impossible. Je me demande quels termes sont utilisés et quels sont les exemples standard pour ces cas difficiles.

Puis-je proposer "De manière embarrassante séquentielle" comme un nom possible?

Answer 1

intrinsèquement séquentiel .

Exemple: le nombre de femmes ne réduira pas la durée de la grossesse.

Answer 2

Il existe plus d’un opposé à un "parallèle embarrassant". problème.

Parfaitement séquentiel

L’un des opposés est un problème non parallélisable , c’est-à-dire un problème pour lequel aucun accélération peut être obtenue en utilisant plusieurs processeurs. Plusieurs suggestions ont déjà été publiées, mais je proposerais encore un autre nom: un problème parfaitement séquentiel .

Exemples: problèmes liés aux E / S , " calculer f ^1000000 (x ₀ ) " type de problème, calcul de certaines fonctions de hachage cryptographique .

Communication intensive

Un autre problème est un problème parallélisable qui nécessite beaucoup de communication parallèle (problème axé sur la communication ). Une implémentation d'un tel problème ne peut évoluer correctement que sur un super-ordinateur avec une interconnexion à bande passante élevée et à faible temps de latence. Contrastez ceci avec des problèmes parallèles embarrassants, dont les implémentations fonctionnent efficacement même sur des systèmes avec une très mauvaise interconnexion (par exemple, fermes ).

Exemple notable de problème lié à la communication: résolution de A x = b où A est une grande matrice dense. En fait, une implémentation du problème est utilisée pour compiler le classement TOP500 . C’est un bon point de repère car il souligne à la fois la puissance de calcul de chaque processeur et la qualité de l’interconnexion (en raison de l’intensité de la communication).

Plus concrètement, tout modèle mathématique qui résout un système d’équations différentielles partielles sur une grille régulière en utilisant un pas de temps discret (pensez: prévisions météorologiques, in silico , est parallélisable par décomposition de domaine . Cela signifie que chaque CPU prend en charge une partie de la grille et qu'à la fin de chaque pas de temps, les CPU échangent leurs résultats sur les limites de région avec des "voisins". CPU. Ces échanges rendent cette classe de problèmes gourmands en communication.

Answer 3

J'ai du mal à ne pas poster ceci ... parce que je sais que cela n'ajoute rien à la discussion ... mais pour tous les fans de Southpark

"Super serial!"

Answer 4

"Série obstinément"?

Answer 5

L'opposé de ce parallèle si embarrassant est la loi d'Amdahl , qui stipule que certaines tâches ne peuvent pas être remplies. parallèle, et que le temps minimum requis par une tâche parfaitement parallèle est dicté par la partie purement séquentielle de cette tâche.

Answer 6

"Exemples standard" des processus séquentiels:

• faire un bébé: «Les programmes d’échec ont échoué parce qu’ils reposent sur la théorie selon laquelle, avec neuf femmes enceintes, on peut avoir un bébé par mois.» - attribué à Werner von Braun
• calculant les nombres pi, e, sqrt (2) et autres nombres irrationnels en millions de chiffres: la plupart des algorithmes séquentiels
• navigation: pour aller du point A au point Z, vous devez d’abord passer par certains points intermédiaires B, C, D, etc.
• Méthode de Newton: vous avez besoin de chaque approximation pour calculer la suivante, meilleure approximation
• authentification défi-réponse
• renforcement des clés
• chaîne de hachage
• hashcash

Answer 7

P-complet (mais ce n'est pas encore connu).

Answer 8

J'utilise "humiliatingly séquentielle"

Paul

Answer 9

"séquentiel gladdengly"

Answer 10

Tout est lié aux dépendances de données. Les problèmes parallèles embarrassants sont ceux pour lesquels la solution est composée de nombreuses parties indépendantes. Les problèmes avec le contraire de cette nature seraient ceux qui ont des dépendances massives de données, où il n'y a presque rien qui puisse être fait en parallèle. Dépendant de manière dégénérative ?

Answer 11

Le terme que j'ai entendu le plus souvent est "étroitement couplé", en ce sens que chaque processus doit interagir et communiquer souvent afin de partager des données intermédiaires. Fondamentalement, chaque processus dépend des autres pour effectuer leur calcul.

Par exemple, le traitement de la matrice implique souvent le partage de valeurs de limite aux bords de chaque partition du tableau.

Cela contraste avec les problèmes parallèles (ou couplés de manière lâche) si embarrassants, où chaque partie du problème est complètement autonome et où aucun (ou très peu) IPC n’est nécessaire. Pensez au parallélisme maître / travailleur.

Answer 12

Vraiment séquentiel.

Answer 13

J'ai toujours préféré "tristement séquentiel" à la partition du tri rapide.

Answer 14

Si jamais on peut se demander ce que serait un problème naturel, séquentiellement incorrigible, essayez

.

parfaitement séquentiel

pour contrer " parallèlement embarrassant ".

Answer 15

"Complètement en série?"

Cela ne devrait pas vous surprendre que les scientifiques pensent plus à ce qui peut être fait qu'à ce qui ne peut pas être fait. Surtout dans ce cas, où l'alternative à la parallélisation consiste à tout faire comme on le ferait normalement.

Answer 16

Complètement non-parallélisable? Pessimalement parallélisable?

Answer 17

L'opposé est "série déconcertante".

Answer 18

en tenant compte du fait que le parallélisme est l’acte de faire plusieurs tâches en même temps, l’étape t. le contraire pourrait être des problèmes chronologiques

Answer 19

Un exemple de problème intrinsèquement séquentiel. C’est courant dans les logiciels de CAO et certains types d’analyses techniques.

Traversée d’arbre avec dépendances de données entre les nœuds.

Imaginez parcourir un graphique et additionner les poids des nœuds.

Vous ne pouvez simplement pas le paralléliser.

Le logiciel de CAO représente les pièces sous forme d’arbre, et pour rendre un objet, vous devez traverser l’arbre. Pour cette raison, les stations de travail CAO utilisent moins de cœurs et plus rapidement, plutôt que plusieurs cœurs.

Merci d'avoir lu.

Answer 20

Vous pouvez bien sûr, mais je pense que les deux noms ne sont pas un problème. Du point de vue de la programmation fonctionnelle, on pourrait dire que la partie «agaçante séquentielle» est la plus petite partie plus ou moins indépendante d’un algorithme.

Bien que le «parallélisme embarrassant», sinon la prise en parallèle, soit une mauvaise pratique de codage.

Je ne vois donc pas l'intérêt de donner à ces choses un nom si les bonnes pratiques de codage consistent toujours à scinder votre solution en pièces indépendantes, même si à ce moment-là vous ne tirez pas parti du parallélisme.