Discussion :

[C-E.B]

Bonjour,

Voyant l'avancée technologique dans ce domaine, pensez-vous qu'il soit possible d'exploiter tous les threads disponibles d'un processeur pour un moteur 3D ?

Vous n'êtes pas s'en savoir qu'Intel va lancer courant de l'année 2009 des nouveaux processeurs comportant 2 et 4 core avec chacun des core pouvant exploiter 2 threads.
D'autre part les jeux n'exploite pas encore ces ressources des processeurs, et cela est bien dommage.

Imaginez un processeur dont chaque thread aurait une(des) tâche(s) particulière(s), ce qui permettrait de monter en puissance au niveau des jeux, augmenter de par ce fait la qualité et la réalité.

Est-ce donc possible ?

[Laurent Gomila]

Oui c'est possible. C'est même très utilisé dans les moteurs de jeu pro, car les consoles exploitent le parallèlisme avec plusieurs cores beaucoup plus fortement que les processeurs de PC.

Mais attention la parallèlisation est loin d'être triviale, surtout dans un moteur graphique. Tu as plutôt intérêt à savoir très exactement ce que tu fais.

[C-E.B]

Merci pour ta réponse

[screetch]

ca ne se fera pas comme ca, un jeu qui marche avec des threads pour des taches ne s'etend pas facilement avec les cores. par exemple, comment va fonctionner le jeu si tu as 4 coeurs au lieu de 2 ? aller deux fois plus vite ? ahum

mettons que tu prevoies large, tu fais un thread pour la physique, un pour le rendu, un pour le gameplay, un pour l'ia, un pour les particules, un pour le son. te voila avec 6 threads. Que faire lorsque du coup tu as un octo-core ?

le futur semble aller vers plus et plus de core dont la fréquence stagne voire est reduit (je te parle la depuis un bi-quad-core, soit deux processeurs de 4 cores, chacun cadencés a 1.86GHz seulement). On est loin des 3,4GHz des pentiums 4 hein
alors si tu ne sais pas metrte a l'echelle sur 2 ou 8 cores, le jeu va etre moisi.

Le principe est de developper le jeu a l'aide de taches divisibles, et de partager ces taches sur les processeurs. par exemple, l'IA et le rendu; tu peux, d'un coté, faire l'IA sur le thread 1 et le calcul de visibilité des objets sur le thread 2. Que faire avec un troisieme proc ? bah...

l'idée c'est de traiter l'IA par batchs divisibles; mettons que tu aies 40 npc sur la map, tu fais une fonction qui prend une liste e npc a mettre a jour, et tu les mets a jour. Et pour le calcul de visibilité, tu prends une liste d'objets en argument et tu verifies s'ils sont visibles ou pas.
Maintenant, tu as deux coeurs; bah tu divise les listes en 2 et tu appelles la fonction deux fois, chacune sur un coeur et chacune sur une moitié de liste. Et lorsque c'est fini, tu divises ta liste d'objets en 2 et tu appelles le calcul de visibilité deux fois, sur deux moitiés de listes.

Et si tu passes a 8 coeurs ? et bien tu divises ta liste en 8 au lieu de 2 et chaque coeur va faire un tout petit bout de l'IA (genre 5 npc chacun) et lorsque c'est fini, tu divises ta liste d'objets en 8 et chaque coeur va verifier la visibilité d'1/8 des objets.

Cela marche tant que les taches sont independantes, ce qui DOIT etre le cas pour un code bien fait. Et voila, ainsi, peu importe le nombre de cores. Et si tu tombes sur une machine a un nombre incroyable de cores, tu peux rajouter des particules ou autres.

[zesinger]

Super intéressante ta réponse! Merci (et du coup merci à C-E.B d'avoir posé sa question )

[screetch]

c'est gentil. Du coup ca m'a mis de bonne humeur et je continue

La seule chose qui n'est pas parallelisable c'est l'envoi de commandes vers opengl ou directx (bien que directx 11 sera multithreadé), et il serait dommage que pendant qu'on envoie des commandes opengl/directx il ne se passe rien. Voila donc, pour un quad-core, comment je verrais les choses :
- tu alloues 3 cores (en regle generale, n-1) core aux taches
- tu reserves un core au rendu

ensuite :
- tu effectues tes taches aussi vite que possible avec tes 3 cores
- la derniere tache consiste a copier ce que tu vas rendre, faire une copie de ton quad tree par exemple, pour pouvoir d'un coté le modifier et de l'autre lire la version
- sur le premier core, tu lances le rendu de ce quad tree en envoyant les commandes
- sur les 3 autres cores, tu commences la prochaine frame

cela implique de separer la logique du jeu de la logique du rendu; par exemple, tu vas devoir stocker la position et l'animation actuelle du personnage de maniere a pouvoir la lire avec le rendu mais a modifier pour la frame suivante.

Si jamais ton coeur adoré a fini le rendu, et bien tu peux lui dire d'aider a effectuer des taches pour le compte des autres cores (les "voler") pour leur rendre service, et des qu'ils ont fini hop tu te lances sur le rendu de la frame qui vient de se finir.

Si les autres cores vont trop vite pour le rendu, cela signifie que ton rendu va "lagger", dans ce cas tu risques d'accumuler des frames de retard. Pour cela, bien evidemment, tu ne stockes pas une liste des frames a rendre, tu n'en stocke qu'une, et si le premier thread a du retard il va sauter directement a la frame la plus recente.

Enfin, pour que tout ce beau monde fonctionne, tu as besoin d'un scheduler, qui va diviser les taches a effectuer et qui va egalement les ordonnancer sur plusieurs cores.

mettons que tu divises ton IA sur 4 cores, et que tu aies 40 personnages; la logique veut que chaque core recoive 10 personnages. mais que se passe t'il si ts 10 premieres IA qui vont sur le coeur 1 jouent aux echecs, pendant que les 30 autres jouent a la bataille et ne monopolisent pas beaucoup de neurones ? ben le core 1 va ramer a mort sur ces 10 et les autres cores vont se tourner les pouces. dans ce cas, le plus simple est en fait de diviser les taches en k*n ou n est le nombre de cores et k un nombre de taches par core, que j'ai mis arbitrairement a 16 ou 32 et qui donnent de bons resultats.

Dans ce cas, si le core 1 rame sur une tache, les cores 2 3 et 4 peuvent:
- diviser une de ses taches dans sa queue et lui en voler la moitié
- lui voler une tache complete
et aider a la progression du core 1. Si tu n'as qu'une tache sur le core 1 et qu'il est deja dessus, tu ne peux pas l'aider.

Enfin, comme je me sens utile et de tres bonne humeu, je vous recommande la bibliotheque intel "thread building blocks" et la doc qui va avec.

J'ai commencé un moteur de jeu dont l'ambition est que la boucle principale envoie une tache dans la liste, cette tache a sa completion declenchera d'autres taches, etc etc, et que l'integralité du jeu soit donc des taches.

J'ai donc pour cela commencé a faire une petite lib ressemblant a intel TBB, et je suis en train de travailler sur les taches pour pouvoir les enchainer et ainsi faire l'integralité d'un update de frame sur les taches, utilsiant au maximum les CPU j'ai aussi lancé mon langage de script qui permettra (un jour) d'effectuer les calculs en parallele, decorrelles de la logique. Car comme montré plus haut, le principal probleme du multithread est que les gens pensent a un fil continu et ne savent pas comment paralleliser. par exemple, lorsqu'on shoote avec une arme a feu, on a :
- le son
- le systeme de particule (effet graphique)
- la balle et le calcul de ce qu'elle touche

mais dans du code en C++ on se voit mal effectuer ces trois choses en parallele car on ne peut pas lancer un thread expres pour faire le bruit d'une balle, et un autre pour faire l'effet graphique. Si ces choses arrivent sur un evenement, c'est tres dur de paralleliser cela.
Donc mon plan est de creer un langage qui permet de dire "effectue ces 3 choses la", va creer 3 taches et va les mettre dans le scheduler. Tout cela sans que le programmeur aient a tripatouiller



WARNING: l'enorme probleme est que si tout est multithread, alors chaque unité peut mourir pendant qu'un autre core lui demande combien elle a de PV, ou autres problemes de synchro. il est important de proteger correctement ces variables.

une idée pour cela est dans le moteur de valve je crois, qui consiste a avoir plein de copie d'objets et ce qu'isl appellent un "pipeline" qui permet de reconstruire un objet a partir des modifications appirtées par chaque thread.

le multithread restecependant quelque chose de tres dur a maitriser et donne d'innombrables bugs tres difficiles a reproduire, etant donné que le scheduler a la main sur tout et qu'on a peu de controle sur lui.

[raptor70]

D'autre part les jeux n'exploite pas encore ces ressources des processeurs, et cela est bien dommage.

La raison principale est simple ... si on base un jeu sur du multi-threading, on reduit considérablement la target des clients car beaucoup ont toujours des processeurs simple core... en grande partie une réponse commercial....

Mais cela changera.. faut laisser le temps ...

[screetch]

vu que les consoles actuelles xbox 360 et ps3 sont multi cores, les projets multi core pour PC arrivent. Le futur est en marche, vous ne le savez seulement pas

[LeGreg]

Petit ajout à ce qui a été dit (je n'en rajoute pas sur la physique, l'IA et la version Multithread de Direct3D 11) :

Le multithreading n'est pas *uniquement* lié à la gestion des multicore. Bien entendu le développement des CPUs multicore est important mais on a fait du multithreading (multitasking) depuis bien longtemps sur des CPUs simple core.

Malgré tous les problèmes usuellement reliés à la programmation multithread, c'est l'un des moyens les plus productif de gérer des problèmes d'UI, de réponses serveur, de l'interactivité, du chargement de données asynchrones sans avoir à faire de l'ordonnancement de tâches explicites dans le code (ou à se limiter arbitrairement à des tâches très simples).

Exemple :
1 - un navigateur fait une requête web, pendant ce temps là l'utilisateur continue à appuyer sur des boutons, déplace la fenêtre, etc. L'une des solutions est d'interrompre fréquement l'exécution de l'une des tâches pour vérifier que l'autre tâche ne fait rien, explicitement depuis le code du programme (multitâche collaboratif et explicite). L'autre solution est de créer deux threads indépendants et de reposer sur le scheduling implicite qui est géré en dehors de l'application par l'OS (multitâche préemptif et implicite). De plus en bonus, si on double le nombre de core disponibles, ces deux tâches peuvent s'exécuter deux fois plus vite car exécutée vraiment en parallèle. (la troisième, la plus mauvaise, solution c'est d'interrompre totalement A jusqu'à ce que B ait fini ce qui peut casser l'illusion d'interactivité et de temps réel).
2 - Jusqu'à récemment la plupart des jeux étaient programmés en multitâche explicite (division en tâches élémentaires qui devaient se terminer avant la fin de la frame courante), voire interrompait fréquemment le jeu pour charger les textures et autres données (interruption longue pour sauvegarde ou pour changement de niveau). C'est un modèle qui va rester vrai pour plusieurs jeux (même avec l'exploitation du multi-core), mais de plus en plus de jeux utilisent le modèle implicite et préemptif là où ils peuvent (il y a d'autres modèles comme les co-routines ou la parallélisation automatique mais laissons ça de côté pour l'instant).

Sinon pour l'exploitation du multithreading dans votre moteur de rendu, n'oubliez pas que Direct3D n'est que partiellement multithread-safe :
Direct3D et Multithreading. L'avis est également vrai pour Direct3D10 (même si les options par défaut ne sont pas les mêmes et même si la couche DXGI cache en partie les problèmes de Present() asynchrones).

LeGreg

[Matthieu Brucher]

Oui c'est possible. C'est même très utilisé dans les moteurs de jeu pro, car les consoles exploitent le parallèlisme avec plusieurs cores beaucoup plus fortement que les processeurs de PC.

Mais attention la parallèlisation est loin d'être triviale, surtout dans un moteur graphique. Tu as plutôt intérêt à savoir très exactement ce que tu fais.

Ce n'est pas aussi simple que ça. En général, on a un parallélisme en O(K) avec K le nombre de tâches, comme graphisme, physique, IA, et non en O(N) avec N le nombre de coeurs. Donc le Larrabee, c'est trop gros.

[Matthieu Brucher]

le futur semble aller vers plus et plus de core dont la fréquence stagne voire est reduit (je te parle la depuis un bi-quad-core, soit deux processeurs de 4 cores, chacun cadencés a 1.86GHz seulement). On est loin des 3,4GHz des pentiums 4 hein
alors si tu ne sais pas metrte a l'echelle sur 2 ou 8 cores, le jeu va etre moisi.

Il ne faut pas parler en terme de fréquence, c'est pas le bon facteur. Il faut voir le nombre d'instructions par coeur et par seconde, c'est ça qui augmente dans un coeur, pas la fréquence qui n'est pas pertinente.

vu que les consoles actuelles xbox 360 et ps3 sont multi cores, les projets multi core pour PC arrivent. Le futur est en marche, vous ne le savez seulement pas

Parallélisme en O(K) et non O(N), le suel vrai parallélisme qui a un intérêt à long terme sur PC.

[LeGreg]

Ce n'est pas aussi simple que ça. En général, on a un parallélisme en O(K) avec K le nombre de tâches, comme graphisme, physique, IA, et non en O(N) avec N le nombre de coeurs. Donc le Larrabee, c'est trop gros.

C'est parce que tu n'es pas data-parallel. Les GPUs (famille dont Larrabee fera partie s'il sort..) sont conçus pour le data parallelisme avant tout.

LeGreg

[Matthieu Brucher]

C'est parce que tu n'es pas data-parallel. Les GPUs (famille dont Larrabee fera partie s'il sort..) sont conçus pour le data parallelisme avant tout.

Malheureusement
On peut essayer d'en faire, mais ce n'est pas toujours possible, comme l'a dit screetch.

Dire qu'une architecture est faite pour le data-parallelism, c'est inverser le problème. Un problème est data-parallel ou task-parallel. Une architecture parallèle sera toujours plus efficace sur du data-parallel lors de son évolution qu'un task-parallel.

[LeGreg]

Ben le graphisme sur ordinateur est quelque chose qui n'existe pas ?
C'est bien une application qui est facilement transposable en data parallel qui a profité d'un processeur dédié depuis plus d'une décennie.

PhysX sur le GPU n'existe pas non plus ?

[Matthieu Brucher]

Ben le graphisme sur ordinateur est quelque chose qui n'existe pas ?
C'est bien une application qui est facilement transposable en data parallel qui a profité d'un processeur dédié depuis plus d'une décennie.

Soit un algorithme est data-parallel, soit il ne l'est pas. Rien à voir avec le support sur lequel il sera lancé.

PhysX sur le GPU n'existe pas non plus ?

Idem, tout dépend de l'algorithme utilisé, pas du support.

C'est quoi pour toi un processeur task-parallel dans ce cas ?

[LeGreg]

Ce qui est important n'est pas l'algorithme utilisé mais le pixel que tu sors et à quelle vitesse tu le sors.

Les gens qui se sont concentré sur l'algorithme (Videologic avec Powervr, Microsoft avec Talisman) se sont cassé les dents, parce qu'il a au final toujours été plus facile (historiquement) d'adapter le problème à l'outil qui peut le traiter le plus rapidement (un millions de marteaux à la recherche de clous).

Bien entendu, *l'algorithme* est important, mais pas cet algorithme-là en particulier à l'exclusion des autres.

Pour le processeur task parallel, c'est difficile, mais le task parallelism et data parallelism ont souvent été orthogonaux. Donc on n'oppose pas l'un à l'autre.
Le GPU est toujours fortement pipeliné par exemple. Bien entendu comme depuis peu (shaders unifiés) ce sont les mêmes parties qui traitent les pixels et les sommets, les tâches qui étaient auparavant vraiment parallèles deviennent concurrentes. Mais au fond c'est tant mieux parce que ça garantit une meilleure utilisation.

[screetch]

Parallélisme en O(K) et non O(N), le suel vrai parallélisme qui a un intérêt à long terme sur PC.

ben c'est exactement tout ce que je dis dans mes deux posts.....

[Matthieu Brucher]

Il y a de bonnes références : Sutter, Eckel, Intel, ...
Tu as un problème à résoudre, et tu as un algorithme task-parallel uniquement (pas le problème, je me suis trompé dans mon premier post, j'ai rattrapé sur le second), ben c'est comme ça. Ce n'est pas parce que tu vas le mettre sur un processeur avec plus de cores que ce que tu as de tâche que ça va transformer la solution task-parallel en data-parallel. L'utopie, c'ets bien, mais la réalité c'est tout de même mieux.

[C-E.B]

Cela sera donc une tâche ardu mais pas impossible...

Il faudra se pencher plus sur la question... Merci donc pour vos réponse.

[LeGreg]

Il y a de bonnes références : Sutter, Eckel, Intel, ...
Tu as un problème à résoudre, et tu as un algorithme task-parallel uniquement (pas le problème, je me suis trompé dans mon premier post, j'ai rattrapé sur le second), ben c'est comme ça. Ce n'est pas parce que tu vas le mettre sur un processeur avec plus de cores que ce que tu as de tâche que ça va transformer la solution task-parallel en data-parallel. L'utopie, c'ets bien, mais la réalité c'est tout de même mieux.

Intel, c'est une mauvaise pioche, ils ont récemment annoncé leur pari à N très grand * cores à unité vectorielle très large.