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.

[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.

[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]

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.

[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 ?

[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

[copter74]

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

Salut les gars...

screetch, you are
Pourrais tu nous dire un peu plus...
Personnellement, je me pose beaucoup de question sur le sujet et je sens que tu as encore bcp a nous dire...
Le DX11 serat-il commercialisé nativement en multitraitement ou ce sera une version genre DX11b non optimisé genre 20% de perf en plus en multicore ?
Le DX11 fera normalement son apparition au début de l'année 2009 tout comme les cartes graphiques compatibles...

Avant c'etait assez simple de faire une estimation au niveau ressource cpu entre chaque genration de GPU....il fallait compter 700Mhz de vitesse supplémentaire a compter du R300.
Aujourd'hui on est en plein virage...les frequences stagne, les coeurs se parallélise et les editeurs sont attentiste marketingment parlant sur la part du gâteau a se faire...c'est a dire l'équipement matériel du parc informatique.

Le feu sera t-il passé au vert niveau marketing en 2011 ? (date d'arrivé des next gen...720, etc...).
Le DX11 pour multicore sera t-il optimisé (cad, gain doublé et proportionnel au nombre de core)
Tu estimes quoi niveau ressource CPU pour faire tourner des jeux Next Gen entre 2011 et 2012 sur un r9xx ?
En repere la 360 a ces début (... janvier 2006) avec son r500 optimisé etait exploité a peine a 20% et arrive aujourd'hui a mi-generation console a maturité et pourtant fait jeu egal avec un C2D d'entré de gamme et un r6xx...

Selon toi, un R9X0 d' ATI ou soyons fou un r1xxx par exemple, qui sortira d'ici 2 ou 3 ans, aura t-il une chance de pouvoir tourner sans etre cpu limited sur une config toute neuve en socket 775 qui est en fin de vie avec un E8500@4.4ghz ? Avec un Q6600@3.6ghz ?
Une alternative a base de coprocesseur sur le meme PCB a coté du GPU prevu par les constructeur si le marché du quad se porte mal, sachant que 99% des utilisateurs de pc qui @ pas leur cpu et que le chiffres des utilisateurs de quad en 2011 ne sera sans doute pas suffisant pour que les éditeurs développe en multi ??

Bref tout est en train de changer mais je me demande pour assemblé une machine qui doit durée 4/5 ans en 775 si ce n'est pas trop tard et trop tot pour du Nehalem...un bon E8500E0@4.2ghz ou un bon Q6600@3.6 ghz min ???

Désolé si je me suis trop étalé sur votre topic en mode HS: actived

[deadalnix]

Moi je me pose une grosse question. Faire tourner une appli sur 4 voir 8 cores, c'est tout a fait faisable.

Le problème étant que répartir les taches entre les threads demande des ressources. Or, cette réârtition ne scale pas du tout, sans quoi deux thread peuvent se retrouver avec la même tache.

Avec une augmentation du nombre de cores comme le propose intel avec le larabee, ne risque-t-on pas de se retrouver dans une situation ou on passe plus de temps a organiser ce que les cores vont faire que de le faire vraiment ?

Quel outils seront proposés au programmeur ? Il me parrait évident qu'une solution doit être apportée au niveau matériel et logiciel conjointement.

A ce propos, comment les GPU gerent ce genre de problèmes (matérielement et logicielement ?). Ceci est en effet masqué par l'API, et le driver, mais je suis sur qu'il y a des choses a apprendre.

[LeGreg]

A ce propos, comment les GPU gerent ce genre de problèmes (matérielement et logicielement ?). Ceci est en effet masqué par l'API, et le driver, mais je suis sur qu'il y a des choses a apprendre.

Le logiciel pilote (qui tourne sur le CPU) est ridiculeusement simple en principe (meme si les lignes de code et la maintenance ne sont pas simples..).

Les commandes envoyées par DirectX et OpenGL, sont traduites en commandes proches directement comprehensibles par le GPU.
SetRenderstate(alphablendfunc, add)
devient un HW_state_alphablendfunc, hw_add
pour caricaturer (mais en fait c'est ça..).
Les commandes HW_ sont décodées en général par une unité spécialisée qui l'envoie ensuite à l'unité concernée.

Le seul parallélisme que doit vraiment "gérer" le pilote à l'heure actuelle c'est le parallélisme CPU/GPU, via un command buffer (une longue FIFO cyclique), une update en ligne ou asynchrone des constant buffers, textures, vertex buffers etc.

Pour le parallélisme à l'intérieur du GPU c'est un artefact de la façon dont sont tracés les triangles.

Un triangle est rasterisé : une opération de setup définit les équations qui vont permettre d'interpoler les attributs une seule fois par triangle, puis ces équations sont envoyés avec les attributs "screen space" (position x0,y0 d'un point fixe du triangle et dx, dy à l'intérieur du triangle) à des unités séparées qui vont chacune à leur tour faire tourner un programme prédéfini appelé pixel shader.

Le gros gros avantage du GPU est que :
- le code du pixel shader est commun pour une array of pixel, donc les instructions ont des chances d'êtres les mêmes à un moment donné ce qui permet de scheduler les tâches en "gros". Si il y a branchement ou appel conditionel de code alors cet avantage est perdu.
- les pixel shaders n'ont jamais besoin de communiquer avec un état "global" synchronisé tout est passé en input local et ils ne communiquent pas entre eux (à certaines exceptions près pour définir des phases pour accéder aux textures de manière cohérentes mais c'est une optimisation). De même les pixels simultanés sont organisés de telle manière que leur output ne se superposent pas (trop) à l'écran ce qui évite d'avoir à synchroniser l'écriture. Ils peuvent aussi être organisés en tiles pour booster l'utilisation de bande passante mémoire.
- Une grosse économie de transistors est réalisé en implémentant des opérations incontournables sous forme de "fixed function" transistors, configurables mais pas programmables, ou moins programmables que le core d'exécution des shaders. Le setup, clipping, blending, texture filtering, compression, etc peuvent être géré en parallèle à l'exécution des cores, de manière rapide et à une fraction du coût (en transistor et en temps d'execution) qui serait nécessaire pour les implémenter de manière "programmable".

Le vertex shader a le même avantage que le pixel shader. C'est juste que les input et les outputs sont organisées différemment (lues depuis un vertex buffer et index buffer et écrites dans une FIFO interne pour le viewport transform/clipping/setup etc.). Là encore les vertex shaders ne partagent pas de donnée et leur place dans la FIFO interne est réservé avant même leur exécution (pas de superposition puisque le VS écrit toujours la même quantité de données).

Le coût typique du GPU n'est pas mesuré en cycles d'exécution mais en nombre de transistors/taille (pour yield)/dissipation de chaleur.

PS: c'est un vaste sujet mais oui un GPU a un gros avantage lié au type de charge (vertex shaders/pixel shaders). Pour Cuda c'est un autre problème.

LeGreg

[Bakura]

Un p'tit papier qui traite du sujet : http://www-graphics.stanford.edu/papers/gramps-tog/

[Alp]

ACCLib bat quelques pronostiques en affichant de telles performances. Il faudrait tester sur des machines à 32 ou plus coeurs pour confirmer mais déjà c'est pas mal.

Encore une fois, attention à ne pas tout mélanger dans la discussion. Soit on parle de parallélisation de JV, soit d'algos en général. Il ne faut en particulier surtout pas généraliser le cas particulier du JV au reste.

Il y a des tas de choses qui ne pourront JAMAIS être correctement parallélisées, à moins de se projeter dans une autre dimension pour les calculer, revenir dans la notre, et rendre le résultat au processeur, le tout plus vite que la lumière.

En JV, on à affaire à un ensemble d'algos qui n'est rien dans l'immensité de tous les algos que l'on peut élaborer/utiliser.

En particulier, on distingue même plusieurs modèles de parallélisation de moteurs. Toutefois, je n'ai rien vu qui fasse mieux que ACCLib pour le moment.

Bref, pas mal de posts servent juste à reprendre sur la forme, ça serait sympa de faire avancer sur le fond (si biensûr il y a matière à ).