L’ensemble de Mandelbrot avec du calcul parallèle en CUDA

Après deux mois d’attente, le cours d’Udacity sur la calcul parallèle en CUDA a enfin commencé. Comme pour leurs autres cours, c’est très soigné et on a envie de continuer à la fin de la séquence, mais il faut patienter une semaine de plus. Petit défaut quand même, leur valeur ajoutée Nvidia n’est pas particulièrement forte, la première semaine se termine avec une interview, certes intéressante, mais cela reste un discours de chercheur. On ne voit pas Nvidia de l’intérieur, des cartes graphiques en morceaux, des lignes d’assemblage, des outils de test qui font rêver. Il leur reste encore plusieurs semaines de cours pour faire rêver, je vais leur laisser le bénéfice du doute.

L’autre défaut, qui me mène à cet article, c’est le manque de pratique : un pauvre petit problème par semaine, pas de quoi s’occuper bien longtemps. Et pourtant, ce ne sont pas les petits problèmes amusants qui manquent.
Pour essayer un peu d’essayer par moi même ce que cela pouvait donner, je me suis plongé dans un problème tout bête qui me dérangeait depuis un moment : comment faire lemendel10s jolis dessins de fractales de l’ensemble de Mandelbrot, cette formulaire quasi légendaire qui a le droit à ses chansons sur Youtube.

Le principe est simple : on prend un nombre complexe c, on part de U0 = 0, et on applique la formule Un+1 = Un² + c. Dès que |Un| > 2, on s’arrête (on peut montrer qu’alors la suite diverge en l’infini). On se fixe un nombre maximal d’itération avant d’abandonner. Le nombre d’itération avant d’arriver à une norme supérieure à 2 donne la couleur.

De mystérieux problèmes de vitesse d’exécution

Ce qui est agréable, c’est que  ce problème est trivialement parallélisable, on forme un nombre c = x + i.y avec chaque pixel de l’écran et on calcule les éléments de la suite, indépendamment des autres pixels. Ce qui est moins sympathique, c’est que je n’ai pas vu comment faire beaucoup mieux … pour obtenir une bonne qualité de dégradé, il faut un nombre d’itérations de l’ordre de 200-500. Et s’il existe une manière astucieuse d’arriver à calculer le terme d’indice 500 sans avoir à calculer tous les précédents, elle n’est pas évidente. On se retrouve donc avec la frustration de ne pas pouvoir faire mieux, même si on multiplie le nombre de cœurs …

mendel8Et si le calcul se fait en 3 ms pour une image triviale (écran où tous les pixels convergent en 1 itération), on atteints 300 ms dans le pire des cas. Ou approximativement 150ms sur une image dont la moitié est triviale et l’autre moitié affreuse. Ca ressemble quand même pas mal à de la proportionalité pour quelque chose qui devrait etre constant. Pourtant, le calcul se fait bien en parallèle : sans utiliser CUDA, les images mettent plusieurs centaines de millisecondes dans les meilleurs cas et plusieurs secondes dans le pire cas, .
Quand on regarde au niveau de la taille de l’image, ce n’est pas non plus aussi simple qu’on le voudrait. 5ms pour une image 100*100, 8 ms pour une image 1000*100 ou 200*200 et 13 ms pour une image de 1000*1000. Ce n’est pas aussi constant qu’on le voudrait, mais quand même, ça y ressemble.
Ce qui est alors intéressant, c’est qu’en prenant une image 200*200, on passe de 0.7 ms pour un image triviale à 17 ms dans le pire cas. Soit à peu près un facteur 20. Dans le cas d’une image 1000*1000, on passe de 3ms à 300ms soit un facteur 100.
D’où vient cet écart ? Est-ce une limite du nombre de threads, est-ce un problème d’accès mémoire (je n’ai pas du tout travaillé l’optimisation) ? Il reste encore des mystères à percer sur le fonctionnement de CUDA …

Le code est accessible sur Pastebin

Exploration de l’ensemble de Mandelbrot

mendel2.pngAprès tout ces histoires de temps de calcul, il faut quand même de jolies images. Et rien qu’avec cette pauvre formule z² + c, il y a un bon paquet de choses à explorer. Tellement que même après des dizaines de tentatives, je tombe encore sur des motifs que je n’avais jamais vu auparavant …mendel5

Alors que l’on crois reconnaitre un motif, on découvre en zoomant qu’en fait il y a d’importantes différences.

Ici par exemple, on croit en voyant le “point bleu” au centre que l’on a retrouvé le motif initial …mendel6

On s’approche, on s’approche, et en effet, ça y ressemble beaucoup !

Mais quand on finit de zoomer, en découvre des spirales dont les nœuds ont 8 branches.
Mais dans d’autres cas, on retombe en effet sur le motif initial.mendel7mendel3Il y a en suite les endroits incroyablement simples. La couleur est presque unie. Les motifs sont quasi-circulaires … tout parait parfaitement ordonné.

mendel4

Une grande famille pleine de variantes

mendel9Et tout ça, c’est pour l’ensemble de Mandelbrot habituel. Mais si on commence à jouer avec la formule, on tombe sur des centaines d’autres fractales tout aussi surprenantes.

Même en écrivant n’importe quoi comme formule de récurrence, on tombe sur des motifs jolis de ce style.
Et comme à chaque fois, on zoom, on zoom et on retombe sur un motif qui n’a absolument rien à voir.

Quand je vois des formules aussi simples qui donnent d’aussi belles images, je me demande pourquoi on se limite au lycée à voir des suite arithmétiques ou géométriques. Les mathématiques seraient sans doute un peu plus appréciées par certains si on leur donnait l’occasion de découvrir le côté artistique qui se cache derrière des formules à priori abstraites et ennuyeuses.

Google Translate et nos amis Chinois

Toujours le même problème de langues sur internet. Les commentaires en russe sur Youtube … Un mot de que l’on ne comprend pas dans un texte en langue étrangère …

Aperçu de la fenêtre de traductionIl y a quelques mois, en cherchant un addon Firefox permettant d’avoir une traduction en passant le curseur sur un mot, je suis tombé sur un script Greasemonkey qui faisait ça très bien. Enfin, pas tant que ça. Google Translator Tooltip est basé sur Google Translate comme l’indique son nom. Ok, c’est pratique, ça fonctionne dans toutes les langues, j’ai maintenant le bonheur de comprendre les commentaires dans des langues incompréhensibles sur 9gag. Le problème, c’est qu’une unique traduction, c’est assez médiocre pour s’en servir comme d’un dictionnaire. Surtout quand Google Translate indique plusieurs alternatives sur le site.

Il n’en fallait pas plus pour me donner envie de bidouiller une amélioation et Google Translator Expanded est né. Après 2 mois, le script a passé hier la barre des 5000 téléchargements, (un score très bon pour userscript.org, surtout avec un ratio de près de 1 “fan” pour 100 téléchargements). Cela mérite bien un article !

Plus d’API gratuite pour Google Translate … ça donne envie d’aller voir comment marchent leurs requêtes AJAX !

Il fut un temps où Google fournissait généreusement une API pour Google Translate. Cette époque est révolue mais ce n’est pas pour autant qu’il n’est plus possible d’aller se servir à la source. Seulement, les scripts que j’ai pu trouver n’étaient pas vraiment élégants : ils demandent la page web complète et récupèrent le contenu de la balise où se trouve la phrase traduite. Déjà,c’est particulièrement laid, mais surtout cela ne permet de récupérer que la phrase complète. De nombreuses informations complémentaires sont disponibles, mais cette fois ci, plus possible de trouver facilement un moyen de les récupérer dans le code HTML. Mais bon, comme tout se charge dynamiquement, autant aller regarder les requêtes AJAX. Et c’est à que cela devient amusant : le résultat est un tableau assez indigeste qui contient un bon paquet d’informations intéressantes. Et ce n’est pas si simple de s’y retrouver.

[
	[
		["To a cat show are purebred cats presented by breeders and owners","Auf einer Katzenausstellung werden Rassekatzen von Z??ern und Haltern pr?ntiert","",""]
	],,"de",,
	[
		["To",[4],1,0,883,0,1,0],
		["a cat show",[5],1,0,883,1,4,0],
		["are",[6],1,0,556,4,5,0],
		["purebred cats",[7],1,0,524,5,7,0],
		["presented by",[8],1,0,515,7,9,0],
		["breeders and owners",[9],1,0,883,9,12,0]
	],
	[
		[
			"Auf",4,
			[
				["To",883,1,0],
				["At",76,1,0],
				["On",0,1,0],
				["In",0,1,0],
				["Onto",0,1,0]
			],[[0,3]],
			"Auf einer Katzenausstellung werden Rassekatzen von Z??ern und Haltern pr?ntiert"
		],
		[
			"einer Katzen Ausstellung",5,
			[["a cat show",883,1,0]],[[4,27]],""
		],
		["werden",6,[["are",556,1,0],["will",327,1,0],["be",0,1,0],["to be",0,1,0],["will be",0,1,0]],[[28,34]],""],
		["Rasse Katzen",7,[["purebred cats",524,1,0],["pedigreed cats",31,1,0],["breed cats",6,1,0],["race cats",0,1,0],["Rassekatzen",0,1,0]],[[35,46]],""],
		["pr?ntiert von",8,[["presented by",515,1,0],["brought to you by",0,1,0],["Powered by",0,1,0]],[[47,50],[72,83]],""],
		["Z??ern und Haltern",9,[["breeders and owners",883,1,0]],[[51,71]],""]
	],,,[["de"]],27
]

Un tableau de 10 cases, avec des cases vides et d’autres remplies de chiffres. En regardant sur plusieurs requêtes faites dans différentes langues, on arrive à trouver les informations intéressantes :

  • Dans la case 0, la traduction principale coupée en petits morceaux.
  • Dans la case 1, des informations sur la grammaire, si les informations sont disponibles pour le couple de langues considéré.
  • Dans la case 5, les traductions alternatives pour chacun des groupes de mots.

largeC’est rempli de chiffres qui indiquent la longueur de chaque segment et l’endroit où il se trouve. Il y a de nombreuses subtilités dans la manière avec laquelle le texte est découpé lorsque l’on traduit des phrases entières, avec plusieurs paragraphes. Certaines informations ne seront affichées que dans certaines langues, en particulier dans les langues qui n’utilisent pas l’alphabet latin. Mais avec un peu de patience, on arrive à comprendre la structure du tableau, et à en extraire les précieuses informations. Victoire !

Une planète peuplée de chinois

Oui, il y a plein de Chinois sur Terre, c’est bien connu. Mais malgré le grand nombre d’internautes en Chine, il est très rare de tomber sur des sites chinois lorsque l’on cherche des information. C’est donc avec surprise que j’ai découvert le grand nombre de scripts faits par des Chinois sur userscript.org. Les Chinois ne sont donc pas une légende, ils existent vraiment sur internet (en dehors des bot de farm présents sur tous les MMORPG) !

Quand j’ai commencé à voir dans la liste des “fans” les noms du genre 烧坏的内存条, wuji2004 et bien d’autres camarades, j’ai commencé à me dire que la proportion de Chinois était bien plus élevée que ce à quoi on aurait pu s’attendre. On notera tout de même qu’il n’ont pas toujours une imagination débordante dans leur choix de pseudo : zxjsdp, qdfk, k9hy … Mais bon, passons.

Là où j’ai vraiment été surpris, c’est quand j’ai lu ce commentaire :

it’s good idea to use translate.google.fr instead of translate.google.com or www.google.com in this script. it works very well even in china.

Je n’avais même pas fait attention, j’avais juste copié l’url d’où venaient les requêtes AJAX sans réfléchir. Impossible de prévoir que cette “fonctionnalité” allait faire le succès de ma version du script … A tel point que lorsque je cherche les sites où le script est cité, il s’agit exclusivement de blogs et forums chinois. Pas étonnant alors qu’ils soient si nombreux parmi les “fans”.

La dernière chose qui par contre me surprend, c’est que très souvent sur les forums en questions, des utilisateurs demandent si quelqu’un veut se charger de traduire le script. Il doit y avoir 2-3 moits d’écrit, “Save” et “Cancel”, “From” et “To”. Ce n’est pas comme s’il s’agissait d’un script qui sert justement à traduire, donc qui s’adresse à des gens qui ont un minimum de connaissances en anglais s’ils vont s’aventurer sur des sites qui ne sont pas en chinois. Alors pourquoi vouloir une traduction du script ? Est-ce juste la traduction de Google qui est mauvaise et qui change le sens des commentaires en question, ou bien un nationalisme forcené qui justifie la traduction de tout sans exception, pour ne pas être sali en lisant de l’anglais ? Un grand mystère culturel à élucider.

Pourquoi s’arrêter en si bon chemin ?

Avec toutes ces requêtes, ça donne envie d’en tirer des statistiques. De mesurer la vitesse de lecture, les mots qui reviennent, et plein d’autres joyeusetés. Mais tout ça, ce sera pour un prochain article.

Nouvelle année, nouveau blog

Et voila, depuis le temps que je me dis que je dois le faire, mon blog est enfin là ! Je rejoins la partie du monde à l’égo suffisamment grand pour penser que non seulement ils sont capables de raconter des choses qui valent le coup d’être lues (le même sentiment qui pousse des milliers de personnes à pondre des commentaires sur un gros site de news), mais qu’en plus ils méritent une petite vitrine rien que pour eux et non un vulgaire compte Twitter, perdu au milieu de millions d’autres comptes sur un énorme plateforme. Pire que cela, j’entre dans la communauté de ceux qui hébergent eux même leur blog, en ayant un nom de domaine à leur nom. Bon il y a quand même la frustration de ne pas avoir cnudde.com, mais après tout, cnud.de c’est encore mieux, c’est court, ça fait geek et avant même de cliquer sur le lien, il y a déjà un petit jeu de mot caché.

Je vais pouvoir faire profiter le monde de mes merveilleuses réflexions et ajouter encore un peu de désordre sur internet. Cela tournera principalement autour des divers projets informatiques pour montrer que je fais des choses intéressantes (vive le personnal branding) et aussi raconter des choses sur l’enseignement pour dire à quel point le système scolaire actuel pourrait être meilleur si on utilisait toutes les possibilités qu’offrent les ordinateurs.

La grande question qui m’a longuement occupé, c’est de choisir la langue. Pour avoir de la visibilité, rien de mieux que l’anglais. Le problème, c’est qu’il y a déjà plein de gens biens qui racontent des choses intéressantes en anglais sur les sujets dont je vais parler. C’est bien plus rare en français. Et comme j’ai ne petite pensée pour ceux qui ne vont pas naturellement s’aventurer sur la partie anglophone d’internet, j’écrirai en français dans l’espoir de leur faire découvrir des idées intéressantes que l’on trouve plus rarement en français.

Je vous souhaite plein de temps perdu et de découvertes en lisant ce blog !