Les cas pathologiques pour la complexité exponentielle, on les rencontres dans du « vrai » code ?
Ce ne sont pas des cas pathologiques, c'est bien le problème. La boucle en elle-même est peut-être « simplement » 2D ou 3D. Mais tout un tas d'applications scientifiques qui simulent des phénomènes naturels (différents aspects météo, dynamique moléculaire, etc., dont je ne maîtrise absolument pas la théorie derrière) utilisent des dizaines de variables, tableaux, etc., pour représenter divers paramètres et aspects du modèle. La complexité ne vient pas uniquement du nid de boucle, mais aussi de l'explosion du nombre de variables dans les systèmes d'(in)équations linéaires qui en résultent. Beaucoup de ces applications utilisent des tableaux à une, deux, ou trois dimensions, ce qui fait exploser le nombre d'états (car le problème des dépendances inter-itérations est qu'il faut maintenir un vecteur d'itération par tableau, plus ou moins, pour tracer les dépendances qui doivent être résolues, et celles qui peuvent être potentiellement « dynamiques » et malgré tout « calculables » par le compilateur pour déterminer si la forme de l'espace d'itération ET du réseau de dépendances constituent toujours un polyèdre convexe).
Enfin, pour paraphraser Feautrier lors d'une keynote sur le sujet, « le modèle polyédrique n'est que polyédrique ». Beaucoup de codes de la vie réelle font appel à des tableaux d'indirection (algèbre linéaire creux, méthodes par éléments finis, et en général pas mal d'algorithmes fonctionnant à partir de représentations par graphes). Le résultat est que dans le cas général le modèle polyédrique ne peut rien car il est impossible de savoir si on a bien un polyèdre convexe pour les dépendances de données1.
Cependant j'ai vu des gens montrer au cas par cas comment dépasser le problème de la convexité, au moins partiellement. Du coup peut-être que dans vingt ans on aura une théorie et des outils pour aller au-delà des limites actuelles du modèle. :)
EDIT: j'oubliais aussi un cas important : si on commence à avoir l'analyse polyédrique activable (genre Polly dans LLVM, qui est dans la branche principale je crois), il faut accepter que l'analyse va sans doute s'appliquer à TOUTES les boucles du programme. Ça risque de sérieusement rallonger le temps de compilation (du coup il faudra passer par des méthodes de ségrégation de certaines fonctions pour qu'elles soient isolées dans des fichiers spécifiques avec des options de compilation spécifiques). C'est déjà plus ou moins le cas dans pas mal de codes scientifiques optimisés, mais ça rajoute des contraintes sur le programmeur.
En pratique je connais des gens capables de faire tout un tas de trucs très cool malgré tout. Par exemple, si tu sais que malgré une indirection de type a[b[i]] par construction les valeurs de b sont monotones (croissantes ou décroissantes) tu peux quand même utiliser l'analyse polyédrique pour permettre la parallélisation. Mais du coup ça demande d'avoir un utilisateur qui le dit au compilateur. ↩
[^] # Re: Solution à base de types variants en ADA
Posté par lasher . En réponse à la dépêche Sortie de GHC 8.0.2 et une petite histoire de typage statique. Évalué à 3. Dernière modification le 02 février 2017 à 17:59.
Ce ne sont pas des cas pathologiques, c'est bien le problème. La boucle en elle-même est peut-être « simplement » 2D ou 3D. Mais tout un tas d'applications scientifiques qui simulent des phénomènes naturels (différents aspects météo, dynamique moléculaire, etc., dont je ne maîtrise absolument pas la théorie derrière) utilisent des dizaines de variables, tableaux, etc., pour représenter divers paramètres et aspects du modèle. La complexité ne vient pas uniquement du nid de boucle, mais aussi de l'explosion du nombre de variables dans les systèmes d'(in)équations linéaires qui en résultent. Beaucoup de ces applications utilisent des tableaux à une, deux, ou trois dimensions, ce qui fait exploser le nombre d'états (car le problème des dépendances inter-itérations est qu'il faut maintenir un vecteur d'itération par tableau, plus ou moins, pour tracer les dépendances qui doivent être résolues, et celles qui peuvent être potentiellement « dynamiques » et malgré tout « calculables » par le compilateur pour déterminer si la forme de l'espace d'itération ET du réseau de dépendances constituent toujours un polyèdre convexe).
Enfin, pour paraphraser Feautrier lors d'une keynote sur le sujet, « le modèle polyédrique n'est que polyédrique ». Beaucoup de codes de la vie réelle font appel à des tableaux d'indirection (algèbre linéaire creux, méthodes par éléments finis, et en général pas mal d'algorithmes fonctionnant à partir de représentations par graphes). Le résultat est que dans le cas général le modèle polyédrique ne peut rien car il est impossible de savoir si on a bien un polyèdre convexe pour les dépendances de données1 .
Cependant j'ai vu des gens montrer au cas par cas comment dépasser le problème de la convexité, au moins partiellement. Du coup peut-être que dans vingt ans on aura une théorie et des outils pour aller au-delà des limites actuelles du modèle. :)
EDIT: j'oubliais aussi un cas important : si on commence à avoir l'analyse polyédrique activable (genre Polly dans LLVM, qui est dans la branche principale je crois), il faut accepter que l'analyse va sans doute s'appliquer à TOUTES les boucles du programme. Ça risque de sérieusement rallonger le temps de compilation (du coup il faudra passer par des méthodes de ségrégation de certaines fonctions pour qu'elles soient isolées dans des fichiers spécifiques avec des options de compilation spécifiques). C'est déjà plus ou moins le cas dans pas mal de codes scientifiques optimisés, mais ça rajoute des contraintes sur le programmeur.
En pratique je connais des gens capables de faire tout un tas de trucs très cool malgré tout. Par exemple, si tu sais que malgré une indirection de type
a[b[i]]par construction les valeurs debsont monotones (croissantes ou décroissantes) tu peux quand même utiliser l'analyse polyédrique pour permettre la parallélisation. Mais du coup ça demande d'avoir un utilisateur qui le dit au compilateur. ↩