Que peut apporter le multithread au développement de jeux ?

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

Envoyé par Matthieu Brucher

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]

Envoyé par 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.

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

[Matthieu Brucher]

Un processeur n'est pas plus data-parallel qu'un autre, c'est l'algorithme qui sera data-parallel ou task-parallel ou rien du tout. Et la majorité des algorithmes, c'est task-parallel ou rien du tout.

Envoyé par LeGreg

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

Ce n'est pas pour le grand public tout de suite, c'est pour certaines applications (comme le raytracing que tu connais bien )

[screetch]

est ce vraiment une question de data parallelisme ? ce n'est pas plutot une question de localité (c'est a dire, faire deux choses simultanément sans qu'elles interfèrent ?) il me emble que le data-aprallelisme est uniquement sur un algorithme ou une partie de code, alors qu'un logiciel a une architecture bien plus large que cela.

Le GPU n'effectue pour ainsi dire qu'une tache, les cartes dediees sont donc adaptées a un pipeline graphique a plusieurs etapes et du data parallelisme, cependant il n'est pas necessaire de diviser un logiciel ni en "taches" ni en "data" parallelisme, tu peux faire un peu d'IA et un peu de physique ant qu'elles n'entrent pas en conflit. Et ces taches ne sont pas "data paralleles", elles sont independantes. On peut augmenter l'independance en utilisant des copies privées sur lesquelles chaque "worker" peut travailler sans voir son resultat detruit par un autre trhead, et ainsi de suite.

[Matthieu Brucher]

Envoyé par screetch

est ce vraiment une question de data parallelisme ? ce n'est pas plutot une question de localité (c'est a dire, faire deux choses simultanément sans qu'elles interfèrent ?) il me emble que le data-aprallelisme est uniquement sur un algorithme ou une partie de code, alors qu'un logiciel a une architecture bien plus large que cela.

Le seul parallélisme qui fonctionnera bien sur les prochains processeurs, c'est le parallélisme des données. Et ça implique aussi une certaine localité, naturellement, sinon ce n'est pas du paralélisme de données.
En général, seule une partie du code a cette propriété. Le principe est de l'agrandir au maximum, mais comme c'est un sous-ensemble très restreint des algorithmes existants, c'est difficile à mettre en oeuvre.
L'avantage du parallélisme de données n'est pas vraiment de traiter plus vite les mêmes données avec un processeur plus rapide (justement parce qu'ona une partie non parallélisable, et donc on atteint rapidement les limites de la parallélisation), mais de traiter plus de donénes dan sle même temps. Par exemple, on fait sauter la limitation du nombre d'unités dans un jeu.

Envoyé par screetch

Le GPU n'effectue pour ainsi dire qu'une tache, les cartes dediees sont donc adaptées a un pipeline graphique a plusieurs etapes et du data parallelisme, cependant il n'est pas necessaire de diviser un logiciel ni en "taches" ni en "data" parallelisme, tu peux faire un peu d'IA et un peu de physique ant qu'elles n'entrent pas en conflit. Et ces taches ne sont pas "data paralleles", elles sont independantes. On peut augmenter l'independance en utilisant des copies privées sur lesquelles chaque "worker" peut travailler sans voir son resultat detruit par un autre trhead, et ainsi de suite.

Ce que tu décris, c'est le parallélisme de tâches. Certaines tâches sont data-parallel, mais ce n'est pas la panacée, et on sera limité par celles qui ne le sont pas.

[screetch]

Envoyé par Matthieu Brucher

Le seul parallélisme qui fonctionnera bien sur les prochains processeurs, c'est le parallélisme des données. Et ça implique aussi une certaine localité, naturellement, sinon ce n'est pas du paralélisme de données.
En général, seule une partie du code a cette propriété. Le principe est de l'agrandir au maximum, mais comme c'est un sous-ensemble très restreint des algorithmes existants, c'est difficile à mettre en oeuvre.
L'avantage du parallélisme de données n'est pas vraiment de traiter plus vite les mêmes données avec un processeur plus rapide (justement parce qu'ona une partie non parallélisable, et donc on atteint rapidement les limites de la parallélisation), mais de traiter plus de donénes dan sle même temps. Par exemple, on fait sauter la limitation du nombre d'unités dans un jeu.

Ce que tu décris, c'est le parallélisme de tâches. Certaines tâches sont data-parallel, mais ce n'est pas la panacée, et on sera limité par celles qui ne le sont pas.

Je ne suis pas d'accord, je trouve que tu regardes avec une trop grosse granularité (c'est a dire que tu ne divises pas tes taches en taches plus petites)

c'est dur de faire du parallelisme avec le C++ car il n'a pas été prévu pour au debut, mais tu divises quand meme ton logiciel en 4 et je pense que tu peux faire mieux. en articulier, tu parles de taches qui sont toutes continues (la physique, l'IA, etc)

Moi je te parle de taches ponctuelles, comme "lancer un missile", "avancer de deux pas", que tu englobes allegrement dans "IA" (ou dans "Gameplay").
En gros je pense que tu parles de theorie mais que tu es trop loin de la pratique. Les micro-taches ci-dessus ne sont pas data ou task ou quoi que ce soit, elles sont indépendantes, ou locales, ne necessittent pas d'etre ordonnancées. Toi tu parles plutot de la resolution generique de programmes, ce qui me parait tres eloigné de la réalité mais bon pour un article de wikipedia.

[LeGreg]

Envoyé par Matthieu Brucher

Un processeur n'est pas plus data-parallel qu'un autre, c'est l'algorithme qui sera data-parallel ou task-parallel ou rien du tout. Et la majorité des algorithmes, c'est task-parallel ou rien du tout.

Certes personne n'a dit que ce serait facile. C'est pour ça qu'il y a une forte valeur ajoutée à la fois dans le hardware et les outils, alors que l'importance du CPU (modèle single threaded ou faiblement threadé) décline.

Par ailleurs, je n'oppose pas Data parallelism et task parallelism. Je dis qu'on doit exploiter les deux (ce que les GPUs actuels font pour le domaine du graphisme mais feront demain dans beaucoup d'autres domaines). Le danger c'est le code "serial". Mais on y travaille.

Envoyé par Matthieu Brucher

Ce n'est pas pour le grand public tout de suite, c'est pour certaines applications (comme le raytracing que tu connais bien )

Larrabee n'est pas fait que pour le ray tracing. Le ray tracing est possible sur le GPGPU du futur mais n'est qu'une petite application parmi tant d'autres. L'IA, la physique, les calculs de visibilité, la detection des collisions, la compression/décompression de textures, tout ça va bénéficier aux jeux (on parle toujours de jeux, hein ?).

Je cite une étude d'Intel :
"D3D Runtime and Driver account for 25-40% of CPU cycles per frame" et c'est sans compter les cycles CPU "administratifs" que l'application doit dépenser de son coté pour garder le GPU busy. La tâche "affichage" est celle qui est coûte le plus sur un jeu moderne.
-> avec une nouvelle API, et un GPU qui est capable de générer ses propres tâches, tu réduis ce coût d'un ordre de magnitude. Et du coup l'importance du CPU faiblement threadé et du code serial décline.
Cela va arriver :
2009/2010 : Direct3D11 introduit le data parallelism dans son API (programmation multithread).
2012 (?) : Direct3D12, le GPU est suffisamment flexible pour être programmable en langage proche du C++ (ou une variante d'un langage fonctionnel pour les amateurs) et pouvoir générer ses propres tâches (rester occupé sans s'appuyer sur des cycles du processeur serial).

Je cite Tim Sweeney (Epic games et Unreal engine) en 2005 :
"2009 Next console generation. Unification of the
CPU, GPU. Massive multi-core, data parallelism, etc"

"By 2009, game developers will face…
- CPU’s with:
– 20+ cores
– 80+ hardware threads
– >1 TFLOP of computing power
- GPU’s with general computing capabilities.
- Game developers will be at the forefront."

Pour être safe, remplace 2009 par 2012 (En 2005 il était encore optimiste Tim Sweeney).

LeGreg

[Matthieu Brucher]

Envoyé par screetch

Je ne suis pas d'accord, je trouve que tu regardes avec une trop grosse granularité (c'est a dire que tu ne divises pas tes taches en taches plus petites)

J'ai dit que certaines tâches pouvaient être parallélisées, mais je suis désolé, toutes ne peuvent pas l'être. Donc quand tu fais du task-parallel dans un workflow ou un pipeline, tu seras ralenti par le plus lent.

Envoyé par screetch

c'est dur de faire du parallelisme avec le C++ car il n'a pas été prévu pour au debut, mais tu divises quand meme ton logiciel en 4 et je pense que tu peux faire mieux. en articulier, tu parles de taches qui sont toutes continues (la physique, l'IA, etc)

On ne peut pas toujours faire mieux. Il y a des applications qui sont purement monocore et où le gain parallèle sera infinitésimal. Un exemple simple, un filtrage AR d'ordre 1, qui peut être paraléllisé, mais le gain, c'est le calcul du filtre divisé par le calcul du filtre + l'accès mémoire. Bref, c'est quasiment négligeable.

Envoyé par screetch

Moi je te parle de taches ponctuelles, comme "lancer un missile", "avancer de deux pas", que tu englobes allegrement dans "IA" (ou dans "Gameplay").
En gros je pense que tu parles de theorie mais que tu es trop loin de la pratique. Les micro-taches ci-dessus ne sont pas data ou task ou quoi que ce soit, elles sont indépendantes, ou locales, ne necessittent pas d'etre ordonnancées. Toi tu parles plutot de la resolution generique de programmes, ce qui me parait tres eloigné de la réalité mais bon pour un article de wikipedia.

Je pense être bien plus proche de certaines pratiques que toi. J'ai dit aussi qu'on pouvait paralléliser certaines tâches, comme la gestion de plusieurs entités, mais il y a une limite. Tous les algorithmes ne sont pas parallélisables, il faudra bien que vous vous en rendiez compte.

Envoyé par LeGreg

Certes personne n'a dit que ce serait facile. C'est pour ça qu'il y a une forte valeur ajoutée à la fois dans le hardware et les outils, alors que l'importance du CPU (modèle single threaded ou faiblement threadé) décline.

Le problème, c'est qu'il ya plusieurs démonstrations mathématiques sur les problèmes algorithmiques expliquant clairement que tout n'était pas scalable, mais bon, si tu penses savoir mieux que les spécialistes du parallélisme (et je ne m'inclue pas dedans, j'apprends encore beaucoup).

Envoyé par LeGreg

Je cite une étude d'Intel :
"D3D Runtime and Driver account for 25-40% of CPU cycles per frame" et c'est sans compter les cycles CPU "administratifs" que l'application doit dépenser de son coté pour garder le GPU busy. La tâche "affichage" est celle qui est coûte le plus sur un jeu moderne.
-> avec une nouvelle API, et un GPU qui est capable de générer ses propres tâches, tu réduis ce coût d'un ordre de magnitude. Et du coup l'importance du CPU faiblement threadé et du code serial décline.
Cela va arriver :
2009/2010 : Direct3D11 introduit le data parallelism dans son API (programmation multithread).
2012 (?) : Direct3D12, le GPU est suffisamment flexible pour être programmable en langage proche du C++ (ou une variante d'un langage fonctionnel pour les amateurs) et pouvoir générer ses propres tâches (rester occupé sans s'appuyer sur des cycles du processeur serial).

Je cite Tim Sweeney (Epic games et Unreal engine) en 2005 :
"2009 Next console generation. Unification of the
CPU, GPU. Massive multi-core, data parallelism, etc"

"By 2009, game developers will face…
- CPU’s with:
– 20+ cores
– 80+ hardware threads
– >1 TFLOP of computing power
- GPU’s with general computing capabilities.
- Game developers will be at the forefront."

Pour être safe, remplace 2009 par 2012 (En 2005 il était encore optimiste Tim Sweeney).

LeGreg

On parle de la partie massivement parallèle, et là je n'ai jamais dit le contraire de ce que tu dis. Mais comme le marketing fait bien les choses, on a l'impression que le massivement parallèle est la solution à tout (ça me fait doucement rire, mais il y a quelques années, le principal problème des applications //, et c'est toujours encore le cas, c'est la congestion des flux de communication. Et ça n'a toujours pas encore été résolu).

Exemple avec la PS3. Avec Folding@Home, elle explose en terme de Tflops la contribution des PCs. C'est bien, mais si on regarde mieux les chiffres, dans les applications non massivement parallèlisables, elle reste très loin du PC. Quand dans une application, on a souvent des branchement et des prises de décision, elle s'écroule face à un processeur mono-thread actuel.

[C-E.B]

Donc pour bien faire, il faudrait différencier les tâches pouvant être parallélisées de celles qui ne le peuvent pas (ou plutôt que l'intérêt n'y est pas).

Si je suis ton raisonnement, une IA c'est de la pise de décision donc pas d'intérêt à être multi-threadé ? Ou devrait-elle avoir son propre thread ?

Je dois avouer que je m'y perd un peu...

En tout cas, c'est un débat très intéressant.

[screetch]

Un jeu n'est pas qu'un algorithme, c'est beaucoup. si certains sont divisibles en taches car "data parallels" tant mieux pour eux. si d'autres ne le sont pas, il reste la possibilité de faire tourner les bouts de codes independants en parallele, sans que ca soit le MEME bout de code. Tu est calé sur une boucle for, mais dans un jeu, y'en a pas qu'une de boucle for......

[Matthieu Brucher]

Envoyé par screetch

Un jeu n'est pas qu'un algorithme, c'est beaucoup. si certains sont divisibles en taches car "data parallels" tant mieux pour eux. si d'autres ne le sont pas, il reste la possibilité de faire tourner les bouts de codes independants en parallele, sans que ca soit le MEME bout de code. Tu est calé sur une boucle for, mais dans un jeu, y'en a pas qu'une de boucle for......

Est-ce que j'ai dit qu'il n'y avait qu'une boucle for ?

Je n'ai pas dit qu'un jeu n'était qu'un algorithme. Il y a plusieurs entités qui tournent ensemble et communiquent ensemble. Ce nombre sera quasiment fixe dans les années à venir. Ces tâches diverses peuvent elles-même être séparées en d'autres tâches (des bouts de code différents). Certaines pourront scaler, pas d'autres. Mais il y a une limite à ce parallélisme qui est inhérent à la phrase que tu as dite, à savoir "sans que ce soit le MEME bout de code". Ces différents bouts sont en nombre finis, donc il y a un nombre fini qui sera rapidement atteint de tâches différentes (et toutes ne peuvent pas être exécutées en même temps).
Par exemple dans un RTS, la sous-tâche de gestion de chaque entité sur le terrain pourra scaler dans une certaine limite. En revanche, la gestion du graphisme sera, avec l'architecture actuelle, bien plus difficile à scaler. Et même dans l'IA, il y a la gestion du path-finding qui aura elle aussi du mal à scaler car pour déplacer une unité, il faut tenir compte des autres unités, donc même là, il faudra faire attention.

[Djakisback]

Personnellement je me demande pourquoi c'est pas le compilo qui gère cela. En théorie rien qu'en parcourant le code il devrait être capable de dire quelles tâches et groupes de tâches peuvent être exécutés parallèlement ou non (ou du moins en déduire une bonne partie), est-ce qu'il existe déjà des approches de ce type ?