Dr. Goulu

Pourquoi … Comment … Combien ?

Optimisation de la Joconde

Mona Lisa en "TSP art". Cliquez dessus pour l'admirer dans mon applet Processing

Cette image me donne enfin l’occasion de consacrer un article marrant au célèbre mais barbant « problème du voyageur de commerce« . Si vous cliquez sur Mona Lisa, vous verrez qu’elle est produite par une seule ligne brisée zig-zaguant entre 100’000 points sans jamais s’entrecouper. De plus la ligne n’a ni début ni fin, elle forme un cycle. Autrement dit, on peut dessiner la Joconde comme un cercle déformé, sans lever le crayon… Je viens de publier une petite applet en processing qui montre ça.

Le dessin a initialement été produit par Robert Bosch, un prof de maths allemand qui étudie l’ « Opt Art », l’utilisation de techniques d’optimisation dans l’art. La méthode est assez simple:

  1. on prend une image en « niveaux de gris »
  2. on dispose un grand nombre N de points sur l’image, resserrés dans les zones sombres, plus espacés dans les zones claires. Craig S. Kaplan a eu l’idée d’utiliser l’algorithme « Voronoï Stippler » [2] qui fait ça de manière remarquable.
  3. Ensuite, il suffit de résoudre le problème du voyageur de commerce à N villes pour obtenir le circuit le plus court entre les N points, donc sans intersection.

Quand vous lisez « il suffit de.. »  , il faut vous méfier. C’est souvent sous cette formule lapidaire qu’on cache l’os. En réalité, le problème du voyageur de commerce (« Travelling Salesman Problem » en anglais, TSP dans la suite) est un problème « NP-complet », un de ceux qui nécessite un nombre « non polynomial » d’opérations pour sa résolution, « non polynomial » étant un euphémisme. En l’occurence, il faut en principe mesurer la longueur des N! (N factorielle…) cycles hamiltoniens possibles passant par les N points pour déterminer lequel est le plus court. Au delà de N=20, on oublie.

Mais le TSP a un intérêt certain pour beaucoup d’applications pratiques dans lesquelles N est bien plus grand, ce qui justifie la recherche d’algorithmes efficaces mêmes s’ils ne fournissent pas la solution absolument optimale. Le site TSP de Georgia Tech est une mine d’exemples et d’infos sur les progrès de la résolution du TSP. On y trouve également Concorde, un solveur de TSP open source très performant basé sur la programmation linéaire. Il détient le record du plus gros TSP résolu, pour N=85’500 calculé en  135 années de CPU, mais résout des problèmes raisonnables en un temps qui l’est aussi. J’ai eu l’occasion de m’en servir pour optimiser le parcours d’une perceuse de circuits imprimés où N valait autour de 1000: quelques minutes de calcul permettent d’économiser des secondes de travail par circuit. Il existe d’ailleurs un Concorde en ligne pour résoudre vos (pas trop gros) problèmes de TSP.

Pour revenir à la Joconde, elle fait l’objet d’un petit concours car il n’est pas sur que le chemin affiché dans l’image soit le plus court possible entre les 100’000 points définis par R. Bosch. Ce chemin, calculé par Yuichi Nagata avec Concorde a une longueur de 5’757’191 unités, alors qu’on a pu déterminer que le chemin ne peut pas être plus court que 5’757’044 unités. Il est donc possible qu’il existe un chemin encore plus court de 0.0026% ! Tout ce qu’il vous faut pour le trouver, c’est le fichier mona-lisa100K.tsp, et touiller un peu le code de Concorde ou de son concurrent TSPLib. Ah, et un superordinateur peut être utile aussi.  Si vous trouvez le chemin le plus court, vous gagnerez la somme mirobolante de $100 !

Références:

  1. Robert Bosch, « Opt Art« , Math Horizons, February 2006, pages 6–9.
  2. Adrian Secord, « Weighted Voronoi Stippling« , 2002, Proceedings of 2nd NPAR, Annecy, p 37-43

13 juin 2010 Publié par Dr. Goulu | Art, Graphisme, Informatique, Maths, graphes | , , | 2 commentaires

Echelle interactive de l’Univers

Bad Astronomy indique une très jolie réalisation graphique en Flash permettant de zoomer dans les ordres de grandeur de l’Univers, sur le modèle des impérissables « puissances de dix« , mais en interactif :

cliquez sur l'image pour la version interactive

Il y a décidément encore un trou de plusieurs ordres de grandeur entre le « diamètre » du neutrino et la longueur de Planck…

30 janvier 2010 Publié par Dr. Goulu | Graphisme, Informatique, Science | | 4 commentaires

reMap

Le Big Bang Numérique s’accompagne de travaux intensifs sur la visualisation d’énorme quantités de données, un domaine qui combine maths (graphes, algorithmique …) et art. Le site VisualComplexity.com répertorie des centaines de visualisation extrêmement variées réalisées pour des applications aussi diverses que la biologie, la scientométrie, la politique, internet et les réseaux sociaux etc.

Avec toutes ces visualisations, il devenait utile de disposer d’un visualisateur de visualisations… C’est ce qu’ont réalisé les infographistes de Bestiario (dont j’avais déjà parlé ici) avec une nouvelle réalisation épatante : reMap.

remapReMap permet de naviguer de façon interactive et animée dans VisualComplexity en mettant en évidence les relations entre les visualisations.

Heures de navigation instructive et multicolore droit devant!

source : infosthetics

27 juillet 2009 Publié par Dr. Goulu | Art, Graphisme, Informatique, Internet | , | 3 commentaires

Superordinateurs de table

Depuis de nombreuses années, les ordinateurs les plus puissants sont formés de très nombreux processeurs calculant en parallèle. Le record actuel est tenu par le “Roadrunner” d’IBM qui comprend 6’948 Opteron bicœurs et 12’960 processeurs PowerXCell 8i d’IBM, contenant chacun 8 unités de calcul en flux (« Stream Processing Unit », SPU).

Combien ?

« Roadrunner » peut effectuer 1 petaflops, soit un million de milliards d’opérations arithmétiques par seconde et vaut des millions d’euros. Vous pouvez aujourd’hui assez facilement disposer dans votre PC du millième de cette puissance pour quelques centaines d’euros seulement.

En effet, les processeurs graphiques « GPU » récents sont formés de centaines d’unités de calcul en flux assez semblables aux 8 SPU du Cell. Initialement dédiés à la génération d’images réalistes en 3D temps réel et limités au calcul en virgule fixe, les GPU sont devenus capables d’exécuter certains programmes en virgule flottante beaucoup plus rapidement que sur les processeurs classiques : c’est le calcul générique sur GPU  (GPGPU).

La série 5000 d’ATI (racheté par AMD) et les nouvelles GTX 200 de nVidia offrent désormais une puissance de l’ordre du teraflops, soit 200x plus que les plus puissants processeurs intel. D’ailleurs nVidia commercialise désormais ses derniers processeurs sur des cartes « Tesla » dédiées au calcul, et dépourvues de sortie video, un comble pour des processeurs graphiques !

ça ressemple à de la pub, mais ça n'en est pas (hélas)

Ainsi, la science peut bénéficier de processeurs puissants à des prix très bas grâce aux millions de consoles et de PC familiaux.

Simulation d’écoulement d’un fluide par la méthode « Lattice Bolzmann » exécutée simultanément sur le CPU et sur le GPU…

Comment ?

La loi d’Amdahl limite beaucoup le gain de performances obtenu en répartissant un programme existant sur plusieurs processeurs (MIMD). Dans un GPU, les centaines de processeurs travaillant en parallèle ne sont réellement efficaces que s’lorsqu’ils effectuent tous les mêmes opérations sur des données différentes (SIMD).

Pour exploiter la puissance des GPU il faut donc re-coder bon nombre d’algorithmes et de méthodes numériques en se basant sur une bonne connaissance de l’architecture des GPU, et en utilisant des langages de programmation spécifiques. nVidia a pris une longueur d’avance dès 2007 en proposant CUDA, une extension du langage C et son compilateur pour les GPU de marque nVidia exclusivement. ATI/AMD a suivi fin 2008 en lançant Stream, une variante du langage BrookGPU, lui même dérivé du C par l’Université de Stanford. Mais Stream ne fonctionne que sur les GPU d’AMD/ATI, évidemment.

Là dessus, des entreprises comme RapidMind ont développé des plate-formes de développement permettant de compiler le même programme C++ pour CPU classiques, GPU nVidia ou ATI/AMD et aussi pour les processeurs Cell de « Roadrunner » et des consoles PlayStation 3 de Sony.

Apple a annoncé une nouvelle étape avec OpenCL, une autre variante de C qui devrait être supportée par son prochain système d’exploitation OS X 10.6 « Snow Leopard » cette année. Microsoft suivra probablement avec quelque chose d’équivalent intégré au Direct X 11 qui accompagnera Windows Seven (si tout va bien…)

Resté bien silencieux sur le sujet des GPU, intel prépare sa revanche en 2010 avec son processeur Larrabee, qui contiendra quelques dizaines de coeurs de ses processeurs classiques x86, et donc sera en principe capable d’exécuter simultanément un grand nombre de programmes habituels, tout en offrant une puissance suffisante pour générer des images en 3D également.

Pour quoi ?

 » le PowerXcell 8i s’adresse avant tout aux scientifiques et au marché des consoles« . Cette merveilleuse phrase s’applique également aux GPU : le marché porteur est celui des jeux video, toujours plus gourmands en qualité d’image et d’animation de scènes 3D complexes, mais aussi en capacité de simulation de phénomènes physiques. On veut de plus en plus de réalisme des chutes, collisions, explosions.

un dinosaure s'effondre... : illustration du chapitre de GPU Gems 3 consacré à la simulation physique. Cliquez sur l'image pour accéder au texte

Jusqu’ici les jeux intégraient la mécanique des corps rigides, mais désormais les cheveux et les habits de nos héros virtuels suivent leurs mouvements, car il est possible de simuler la déformation élastique et la rupture. La prochaine étape est de simuler l’écoulement de fluides en temps réel, on y est presque.

Or les méthodes nécessaires à ces applications ludiques sont très semblables à celles permettant de prévoir la météo, de simuler des galaxies ou de déterminer les propriétés de molécules chimiques, entre autres.

Parmi les 200 applications listées sur la Cuda Zone de NVidia, bon nombre sont des librairies numériques et d’algèbre linéaire pouvant être appliquées dans de nombreux domaines, comme par exemple le contrôle des miroirs actifs des télescopes ESO qui nécessite d’effectuer chaque milliseconde un produit scalaire d’une matrice 3000 x 6000 par le vecteur des 6000 mesures pour obtenir les 3000 commandes (video à ce sujet)

Les logiciels scientifiques usuels commencent à tirer parti de ces librairies de façon quasiment transparente:

  • pour Matlab, il existe déjà un plugin FFT et le l’environnement Jacket
  • LabView dispose d’un suport « multicore » intégrant Cuda, utilisé dans le projet mentionné plus haut
  • Mathematica 7 utilisera Cuda
  • Python, mon langage préféré du moment, peut aussi accéder à la puissance de Cuda grâce à PyCuda (faut que j’essaie ça asap!)

Et bien d’autres applications spécifiques comme:

Quel que soit votre utilisation de l’ordinateur, souvenez-vous de faire bien attention au GPU qui équipera votre prochaine machine : ce sera lui qui fera de votre machine un superordinateur de table.

Liens:

  1. Geeks3d.com le site de référence de mon gourou sur ce sujet, JegX
  2. La montée en puissance des GPUs
  3. Loi de Moore toujours
  4. Damien Triolet, « Nvidia CUDA : aperçu« , sur hardware.fr 2 Mars 2007

13 mars 2009 Publié par Dr. Goulu | 3D, Graphisme, Informatique, Physique, Science, Simulation | , , , , , , | Laisser un commentaire

Bestiario

Bestiario.org est une petite, jeune et très dynamique entreprise créant des « espaces digitaux pour la création collective de connaissance ». Autour du slogan « rendre le complexe compréhensible », ils combinent art et science pour créer des sites interactifs en Flash utilisant la théorie des graphes, la topologie, la simulation physique et la visualisation géométrique et géographique.

Voici quelques unes de leurs réalisations (cliquez sur les images pour lancer le site interactif correspondant) :

SPISI : visualisation de données en spirale

SPISI permet de rechercher des périodicités dans des données. En bougeant un curseur, on agit sur le nombre de données par tour de spirale. Les données à explorer sont :

  • le nombre de diviseurs des nombre entiers. En approchant le curseur de 24 (ou 12…), on voit apparaitre la « Croix de Plichta« 
  • les variations de la température de notre belle planète, mesurée sur 422766 ans grâce à une carotte de glace antarctique. avec le curseur sur 100’000, on voit apparaitre 3 cycles assez clairement.
  • l’index Dow Jones. Là on a beau chercher des cycles …

videosphère : toutes les vidéos du TED reliées

Videosphère permet de découvrir les fantastiques videos des conférences du TED, (si vous ne connaissez pas, voyez au moins celle là). On peut évidemment trouver les conférences sur des thèmes donnés, mais aussi naviguer vers des conférences sur des sujets similaires en explorant un graphe liaant les vidéos représentées sur une sphère. simple, efficace, et beau.

drinkMe : un zoom de 10^36 dans un graphe

Si vous n’êtes pas impressionné par DrinkMe (drôle de nom) , c’est que vous n’êtes pas informaticien. Cette démonstration au graphisme primitif permet de zoomer dans des données un peu comme le film « Les Puissances de Dix » à travers l’Univers. Pour passer de façon continue d’une visualisation macroscopique à un microscope avec un grossissement de 1’000’000’000’000’000’000’000’000’000’000’000’000 x , il faut une certaine maitrise de la programmation…

J’aurais souhaité décrire ici toutes les autres réalisations de Bestiario.org , mais ce serait trop long. Sachez qu’elles valent toutes la peine d’être vues ou expérimentées : ces gars là font du très beau travail. à suivre.

source: information aesthetics, un blog à suivre si vous vous intéressez à la représentation des données et la communication visuelle.

10 octobre 2008 Publié par Dr. Goulu | Art, Graphisme, Géométrie, Internet, Science, Simulation, Statistiques, Video, graphes | Laisser un commentaire

« Articles précédents