Y a-t-il quelque chose qui DOIT être fait sur un processeur multicœur?

45

En considérant à quel point notre programme doit être convivial pour les multi-threads, mon équipe se demanda si quelque chose ne pouvait absolument pas être fait sur un processeur monocœur. J'ai posé comme principe que le traitement graphique nécessite un traitement extrêmement parallèle, mais ils affirment que des opérations telles que DOOM ont été effectuées sur des processeurs monocœurs sans GPU.

Y at - il quelque chose qui doit être fait sur un processeur multi-core?

Supposons qu'il y ait un temps infini pour le développement et l'exécution.

Ben Leggiero
la source
8
Alors que les réponses ci-dessous semblent être en grande partie "non", il existe historiquement des systèmes qui n'auraient littéralement pas pu fonctionner sans un co-processeur gérant certaines tâches. Je connais un exemple frappant: la Nintendo DS, qui comprend un processeur ARM9 à 67 MHz et un processeur ARM7 à 33 MHz (également utilisés pour la rétro-compatibilité lors de la lecture de jeux GBA). Pour les jeux DS, l’ARM7 gère la lecture de l’audio et la communication Wi-Fi, car l’ARM9 ne peut traiter ni afficher quoi que ce soit d’important à l’écran tout en continuant d’alimenter l’audio directement sur la puce sonore. Donc, comme @jmite déclare “sous quelles contraintes”, le manque de vitesse peut nécessiter plusieurs processeurs.
Slipp D. Thompson
10
Dans mon travail, nous utilisons Xeons multicœurs et les extensions Linux temps réel Xenomai pour effectuer le traitement audio à faible latence. Nous avons un pipeline de traitement audio en trois étapes et chaque étape dispose de son propre noyau dédié, qui utilise environ 70% des cycles. Les tâches qui ne sont pas en temps réel utilisent le quatrième noyau et tous les cycles restants des trois premiers. Cela ne serait possible sur un processeur simple cœur que si ce dernier était 3 fois plus rapide qu'un cœur sur un processeur actuel à 4 cœurs; étant donné que le processeur actuel fonctionne à 2 GHz, cela pourrait être difficile à atteindre.
Jeremy Friesner
19
Un logiciel sur un processeur monocœur peut émuler un processeur multicœur. La différence est presque entièrement la vitesse.
user253751
24
Une chose à faire sur un système multicœur est de tester les logiciels multithread. Parce que certains défauts ne se produiront (presque) jamais sur un système monocœur. Je ne suis pas sûr que cela
puisse être
13
@nikie Un système monocœur peut également émuler l'ordonnancement de la mémoire et les caches obsolètes - mais j'imagine que cela serait extrêmement inefficace (comme un ralentissement de 10 ×)
Nayuki

Réponses:

47

Si vous ne vous souciez pas du temps d'exécution, vous pouvez faire tout ce que vous pouvez faire sur une machine multicœur, sur une machine monocœur. Une machine multi-core n’est qu’un moyen d’accélérer certains types de calculs.

Si vous pouvez résoudre un problème dans le temps sur une machine multicœur à cœurs, vous pouvez le résoudre temps (ou moins, regardez la loi d'Amdahl ) sur une machine monocœur. La machine monocœur peut émuler une machine multicœur en utilisant le découpage / partage de temps .n T nTnTn

DW
la source
3
Je ne suis pas tout à fait sûr que ce soit tout à fait correct. Je ne pense pas qu'il soit possible de générer des bugs sur la cohérence de la mémoire sur un seul cœur (oui, on pourrait émuler un système multicache sur un unicore, mais un tel indirection est une sorte de tricherie.). (Peut-être une solution équivalente à la mise en œuvre de swaps réguliers par des opérations de déplacement dans un VLIW, exploitant une garantie || ism?) l'entropie serait plus petite par unité de temps (ce qui est simplement une question de performance comme les autres différences).
Paul A. Clayton
6
@ PaulA.Clayton Les problèmes de cohérence de la mémoire sont généralement indésirables et les logiciels bien écrits ne doivent pas les exposer. Toutefois, si vous le souhaitiez vraiment , vous pouvez les imiter sur un seul processeur. (Bien que cela puisse être lent)
utilisateur253751
4
Parfois, le temps sur un seul cœur sera plus de fois plus long que sur une machine à coeurs, par exemple pour une recherche avec redémarrage aléatoire ou si les pièces entrent dans le cache sur plusieurs coeurs mais pas sur un seul coeurs. nnn
András Salamon
11
"La machine monocœur peut émuler une machine multicœur en utilisant le découpage / le partage du temps." Et en effet l'ont fait depuis l'aube du système d'exploitation "moderne".
Courses de légèreté avec Monica
1
@ PaulA.Clayton Je pense que vous pourriez avoir des problèmes de cohérence de la mémoire (comme un incrément non atomique) si vous aviez deux processus différents modifiant à la fois la même mémoire partagée. Vous avez juste besoin d'un multi-tâches préemptif. Bien entendu, c’est généralement la raison pour laquelle les systèmes d’exploitation modernes ne disposent pas de processus partageant la même mémoire en écriture, à moins qu’ils ne le leur demandent explicitement.
Patrick M
58

La question est: sous quelles contraintes?

Il y a certainement des problèmes où, si nous posons la question "pouvons-nous résoudre ce problème avec le matériel X dans le temps imparti", la réponse sera non.

Mais ce n’est pas une réponse "à l’avenir": des choses qui dans le passé ne pouvaient pas être faites assez rapidement dans un seul noyau peuvent probablement être maintenant, et nous ne pouvons pas prédire ce que le matériel futur sera capable de faire.

En termes de calculabilité, nous savons qu'une machine Turing à bande unique est capable de calculer les mêmes fonctions qu'un ordinateur monocœur ou multicœur, de sorte que, mis à part le temps d'exécution, aucun ordinateur multicœur ne peut résoudre ce problème. single-core ne peut pas.

En termes de graphisme, littéralement, tout ce qui est sur le GPU pourrait être fait sur le CPU ... si vous êtes prêt à attendre assez longtemps.

jmite
la source
3
@ JanDvorak, je dirais en fait que cela n'est pas du tout fait par le GPU;)
TomTom
15
Si le temps n’est pas une contrainte, vous pouvez effectuer tous les calculs à la main, au stylo et au papier.
mathreadler
2
@mathreadler Oui, parce que le cerveau est Turing Complete. Quelque chose qui s'est transformé en un long débat sur Physics Stackexchange.
JBentley
4
En fait, @JanDvorak, la génération VGA est assez simple et peut se faire dans le logiciel sur un micro - contrôleur 16 MHz humble, comme ce projet montre: pyroelectro.com/tutorials/arduino_basic_vga
Axello
3
@mathreadler C'est en fait une question plus compliquée qu'il n'y parait. Une réponse courte pourrait être "oui" car une machine spécialisée peut construire un ordinateur sans avoir besoin d'outils complets pour le faire. Une réponse plus longue pourrait être "non", car la possibilité de construire une machine de turing peut impliquer que l'on dispose d'une machine de turing plus grande qui se trouve dans un état "d'initialisation" dans lequel elle construit le reste de la machine à états. La réponse complète est encore plus compliquée, car nous n’avons jamais construit d’appareil Turing Complete. Nous avons développé des idées abstraites pour des machines qui sont ...
Cort Ammon
17

Comme d'autres réponses l'ont souligné, un seul processeur peut toujours émuler plusieurs processeurs en découpant l'heure et en jouant le rôle de chaque processeur virtuel. Cette émulation calculera certainement les bonnes réponses.

Dans le monde réel, le temps d'exécution peut être important. Cela pourrait signifier la différence entre un taux de trame médiocre et une expérience visuelle stellaire. Ou la différence entre le profit et la perte dans le commerce.

Une situation pathologique où un multi- processeur est beaucoup plus rapide qu'un mono-processeur est celle où le traitement est un pipeline de données, la commutation de contexte est coûteuse et le code machine pour chaque étape de pipeline s'insère à peine dans le cache d'un processeur.

Permettez-moi d'illustrer avec quelques chiffres. Supposons que vous disposiez d'un pipeline de données (rendu 3D, etc.) comportant 4 étapes de traitement, chaque étape contenant 256 Kio de code de programme et 4 CPU avec 256 Kio de cache L2. Si vous essayez d'exécuter ce traitement sur une seule CPU, la commutation entre les 4 tâches sera coûteuse et impliquera de nombreuses erreurs de cache. D'un autre côté, si vous l'exécutez sur un système à 4 cœurs, le calcul pourrait être très lisse, les erreurs de cache sont minimes et les commutateurs de contexte inexistants. (Remarque: ceci est lié à la notion d'épingler certaines applications à certains cœurs - par exemple, ne faire que les opérations du noyau du système d'exploitation dans un seul cœur, la gestion TCP / IP, etc.)

Nayuki
la source
7

Il est beaucoup plus difficile de développer des courses de données vraiment néfastes avec un seul processeur. Je veux dire, bien sûr, vous pouvez arracher des mots entre deux mots si vous interrompez un seul processeur, mais pouvez-vous créer des scénarios exotiques où il n’existe pas un seul entrelacement de fils qui fasse ce que vous voulez?

OK, faire des bugs insidieux ne compte pas comme une utilisation valide des avancées multi-codes. En fin de compte, il n’ya pas grand chose que plusieurs cœurs puissent faire, ce qui ne peut pas être donné par un seul cœur. La raison est simple. Si vous essayez d'éviter ces courses de données pervers, vous devez avoir des points de synchronisation dans votre code. Si vous modélisez votre code comme un réseau de calculs dans lequel certaines entrées doivent être complètes et synchronisées avant de pouvoir calculer et générer des sorties, il est facile de voir qu'un seul processeur peut simplement se frayer un chemin le long du réseau, en calculant le prochain bloc de travail disponible. .

En fait, si vous pouvez démontrer que votre algorithme peut être résolu par une machine de Turing (qui correspond à pratiquement tous les algorithmes qui nous intéressent), il peut être prouvé que l’algorithme peut être exécuté non seulement par un processeur central, mais machine d'état avec un très long morceau de ruban adhésif pour la mémoire!

Le détecteur de course CHESS exploite en fait cela pour trouver des cas de course. Il exécute tout ce qui est lu individuellement et explore systématiquement tous les intercalages possibles entre les threads, en essayant de trouver les cas où un test échoue à cause d'une affaire de race. CHESS dépend du fait que vous pouvez exécuter n’importe quelle application multithread sur un seul cœur.

Les cas dans lesquels vous avez besoin de multicœurs apparaissent lorsque vous commencez à étirer les limites du matériel. La plus évidente est lorsque vous avez des contraintes de temps. Certains problèmes de contraintes de temps en temps réel sont impossibles à résoudre avec un seul cœur, car ils ne peuvent tout simplement pas conduire assez rapidement l’horloge d’un seul cœur. Il y a une raison pour laquelle les processeurs ont grimpé jusqu'à 4 GHz puis se sont installés un peu, préférant plus de cœurs à des vitesses inférieures.

Une version plus exotique de cette contrainte de synchronisation se trouve dans les systèmes en temps réel. Dans certains systèmes en temps réel difficiles, le service des interruptions est si exigeant que vous devez choisir un processeur multicœur qui vous permet de répartir les interruptions sur les différents cœurs ou de rencontrer des contraintes de temps.

Une autre limite se pose avec les bus de données. Prenons le Blue Gene / P comme exemple. JUGENE, un superordinateur particulier Blue Gene / P, dispose de 144 téraoctets de mémoire. Ils ne fabriquent tout simplement pas d'ordinateurs à processeur unique pouvant accéder à toute cette mémoire.

Cort Ammon
la source
1
Re, ils ne fabriquent tout simplement pas d'ordinateurs à processeur unique pouvant accéder à [autant] de mémoire. "Ne pas" n'est pas la même chose que "ne peut pas". Vous pouvez concevoir et créer un processeur unique doté de 144 téraoctets ou plus de mémoire principale. La seule raison pour laquelle les gens ne le font pas, c'est à cause des rendements décroissants: la valeur pratique et incrémentielle de l'ajout de mémoire supplémentaire à une conception à processeur unique atteint un pic à un moment donné, puis diminue lorsque la taille de la mémoire augmente, alors que le coût incrémentiel reste constant .
Salomon Slow
@jameslarge Ce serait la raison pour laquelle cette phrase figurait dans la partie de ma réponse traitant de matériel pratique, et pourquoi elle n'apparaissait pas dans les deux premiers tiers de la réponse traitant des capacités théoriques.
Cort Ammon
"Don't" vs "Can't" est illustré par deux systèmes dans mon sous-sol. Si je pouvais physiquement ajouter autant de mémoire dans leurs configurations matérielles, leurs processeurs "pourraient" accéder à chaque octet. Mais je ne peux pas, alors ils "ne peuvent pas". Les capacités des processeurs vont au-delà de la pratique.
user2338816
Je pensais quelque chose comme cette réponse. Il semble que les conditions de course seraient impossibles (ou se produiraient 100% du temps) dans un environnement monocœur. En ce qui concerne une application pratique, je pense qu'un développeur de logiciel pourrait concevoir une forme unique de protection contre la copie en codant un test de condition de concurrence étrange qui transmettrait toujours le matériel cible spécifique, mais échouerait sur un matériel émulé exécuté par un seul cœur. . Dans ce cas, l’émulation par un système multicœur passerait probablement quelquefois, mais de manière non fiable.
Dan Henderson
6

Si vous devez observer un processus s'exécutant sur un seul élément de traitement sans perturber son comportement en temps réel (ou le moins possible), comme pour l'analyse comparative ou la journalisation des activités, vous aurez probablement besoin d'une ressource de traitement distincte.

Yves Daoust
la source
Bel exemple concis de quelque chose qui nécessiterait une émulation précise sinon plusieurs processeurs
Ben Leggiero
Hey est ce votre compte? Voulez-vous le fusionner?
Mal
4

Les autres réponses adhèrent à la vision limitée du parallélisme en tant que "concurrence simultanée". Cela donne quelques réponses: dans un modèle clair de calcul à la Turing, les cœurs multiples n'offrent pas d'avantage; le seul avantage que vous pouvez obtenir est l'efficacité.

Il est la seule chose plusieurs unités de traitement (PUS) peuvent faire qu'un seul ne peut pas, cependant: exécuter des opérations en parallèle , qui est en même temps .

Cela est très utile si vous exécutez plusieurs programmes en même temps. Certes, il est rare que vous ayez absolument besoin de plus que de l’exécution simultanée, et la plupart des utilisations se résument à une efficacité accrue. Mais il y a cette différence.

Supposons que vous deviez traiter les données du capteur de données provenant de plusieurs sources en temps réel. Quoi que cela signifie précisément dans votre application, une unité centrale ne peut gérer qu'un nombre limité de flux d'entrée simultanément sans violer sa limite de temps de réponse. Vous avez donc besoin de plusieurs PU lorsque vous avez trop de capteurs pour votre génération de PU actuelle.

Dans le domaine plus classique, un exemple peut-être convaincant est celui des algorithmes de portefeuille . Supposons que vous ayez un problème pour lequel vous avez plusieurs (disons ) algorithmes à coûts orthogonaux; les bons cas de l'un sont des cas mauvais pour les autres. Vous ne pouvez pas dire rapidement quel est le meilleur pour une entrée donnée, cependant.k

Vous pouvez exécuter tous les algorithmes en parallèle et abandonner une fois l’opération terminée. Si vous avez au moins unités, vous obtenez le temps d'exécution minimal parmi tous les algorithmes du portefeuille. Avec un seul PU, vous obtiendrez fois cela, en supposant un ordonnanceur juste, plus tous les frais généraux.k kkkk

Raphaël
la source
0

à partir d'un CS pov, "multicœur" n'est pas tellement différent en théorie de "calcul distribué". le concept de base est "des éléments informatiques indépendants (qui calculent en parallèle". Donc, reformuler légèrement la question ("multicœur" n'est pas vraiment un concept théorique en CS) ouvre d'autres possibilités. Comme indiqué dans d'autres réponses, la programmation séquentielle est Cela revient à la définition du système théorique d’informatique, à savoir une machine de Turing. L’analyse théorique de la performance de CS est finalement en termes de TM où la distinction entre parallèle et séquentiel ne s’applique pas vraiment ( Il existe toutefois une analogie approximative avec les multitape TM .

mais si l'on considère cette question de manière moins abstraite, l'informatique distribuée est en effet supérieure, voire même presque nécessaire pour certains problèmes impliquant la tolérance aux pannes . dans ce domaine, il existe un concept qui s'applique lorsque / où les éléments informatiques indépendants sont considérés comme présentant un certain degré de non - fiabilité (ce n'est pas vraiment une hypothèse universellement applicable dans tous les contextes). Il existe plusieurs cas où la tolérance aux pannes est améliorée avec des éléments informatiques indépendants, voire même requise .

  • Considérez que chaque processeur a une "[x]%" probabilité d'échec indépendante pendant le calcul. il est possible de concevoir un système dans lequel, par le biais de la communication, la tolérance globale aux pannes du système est supérieure à celle des composants individuels. cela a été appliqué il y a plusieurs décennies, par exemple dans les systèmes de navette spatiale. plus récemment, il existe des protocoles de base conçus pour l'utiliser, par exemple Paxos, qui résolvent le problème dit du consensus . Google, par exemple, utilise beaucoup d'algorithmes exclusifs pour construire son ou ses supercalculateurs à partir d'éléments non fiables individuellement, associés à des algorithmes tolérants aux pannes.

  • Bitcoin implique des transactions distribuées pour calculer le grand livre et ce n'est pas simplement en raison de problèmes de charge de traitement. l'algorithme est soigneusement conçu pour contrecarrer les nœuds corrompus. En bref, il "résout" / implémente le problème des généraux byzantins, qui ne consiste pas simplement à maximiser les performances parallèles, mais implique des entités indépendantes qui se "contrôlent" et "rejettent par algorithme / cryptographie / sécurité" les calculs non valides, autrement dit une sorte de "triche" ou " la corruption".

  • une analyse classique du parallélisme conclut qu’il existe environ 7 types de problèmes «fondamentaux» qui se décomposent en défaillances d’exécution parallèles particulières. voir Le paysage de la recherche en informatique parallèle: une vue de Berkeley

  • Il existe un élément d’une question théorique ouverte dans la plupart des autres réponses. la question de savoir s'il existe des problèmes qui sont "intrinsèquement plus rapides" en parallèle que séquentiels est également appelée à peu près le problème P =? NC où NC est considéré comme la classe des algorithmes "efficacement parallélisables" et P est appelé "algorithmes [efficaces] séquentiels" "

vzn
la source
1
J'aime cette réponse! J'ai beaucoup appris de vos exemples: D
Ben Leggiero Le
+1 pour la tolérance aux pannes dans les environnements critiques avec rayonnement, -1 pour l'absence de plafonds et la redondance.
Cees Timmerman