PetaRabbit

Coucou les zestueux,

Pour la petite histoire, ça a commencé ici.

Petarabbit c’est le projet d’un simulateur numérique d’ensembles de Julia (et bien plus), en particulier du Lapin de Douady. (D’où le nom : peta + rabbit, merci @dri1).

Le projet

Il s’agirait de l’action conjointe de deux programmes.

• Un premier qui serait un visualiseur d’images de très grandes tailles (très, très grandes tailles, au-delà du milliards de pixels). Ce programme devrait permettre de se balader dans l’image de façon fluide.
• Le deuxième serait le simulateur. Il a pour rôle de produire l’image de très grande taille.

Sur le simulateur

Le simulateur fonctionne selon 3 axes :

• Le premier axe gère l’aspect mathématique descriptif : structures algébriques, définition de la dynamique discrète et du critère de convergence.
• Le second axe joue le rôle de pilote : il lance les tests de convergence sur les points. C’est ici que se joue le multithreading.
• Le troisième axe a pour but d’inscrire les informations en une image. Il donne au deuxième axe les points à calculer et gère l’information pour inscrire le résultat dans un .png.

L’état actuel

Le code est là.

Actuellement les fichiers sont répartis de la façon suivante :

• Premier axe = Algebre.cpp, Julia.cpp, Cycle.cpp, Mandelbrot.cpp
• Deuxième axe = Dynamicien.cpp
• Troisième axe = main.cpp avec Moteur.cpp (et Parametre.h et SFML et lodepng.cpp)

Cette base permet de fournir des images de grande taille (voir billet plus haut) mais ne propose ni de très grande taille (du fait d’optimisations à faire et de matériel à avoir — que je n’ai pas) ni de logiciel pour explorer les grandes images.

Sur ce qu’il faut faire

Le visionneur d’images grandes tailles.

C’est une partie indépendante qui doit répondre à deux objectifs :

• fluide ;
• permet de sélectionner n’importe quel .png en entrée.

Je ne doute pas qu’un zestueux talentueux en informatique pourra le faire sans trop d’encombres.

Le simulateur.

Actuellement il faudrait commencer le travail de parallélisation sur GPU.

Quelques précisions pour finir

Jusque là, je me suis lancé en C++ après avoir comparé différents langages à ma portée. J’ai l’impression que ça tourne plutôt bien et que le rapport simplicité d’écriture / efficacité est bon. Mais si vous avez de meilleures options, je serai heureux de les entendre.

Aussi, je compte réellement sur vous pour travailler sur ce projet. Je n’ai pas de grande compétence en informatique. Ma contribution est surtout sur la compréhension mathématique du sujet, qui n’est pas sans difficulté.

À long terme

Je pense que ce projet peut être fini assez rapidement si on le limite au calcul d’un lapin avec des dimensions très très grandes.

Mais ça serait dommage de se limiter au lapin de Douady. Il y a plein d’ensembles de Julia passionnant à examiner, et l’intérêt du premier axe serait de pouvoir passer facilement d’un exemple à l’autre.

Actuellement on peut déjà faire quasiment tous les ensembles de Julia possible (je ne parle pas uniquement de Julia de polynômes, mais aussi de fractions rationnelles). On peut aussi faire l’ensemble de Mandelbrot.

Mieux : on pourrait avec un premier axe propre permettre de simuler des dynamiques discrètes sur des espaces plus exotiques que $\mathbf C\cup\{\infty\}$ comme par exemple $\mathbf CP^2$ ou $\mathbf CP^3$ qui sont des sujets de recherche très actuels.

Mot de la fin

Pour finir, j’aimerai vous signaler que c’est une opportunité pour ZdS de mener à bout un tel projet. En effet, toutes les images de Wikipédia concernant des ensembles de Julia pourraient être refaites et dans une qualité bien supérieure.

Rien qu’à titre d’exemple, comparez le lapin de Wikipédia et celui dans ma balise en début de topic …

Si on fait ces images, on pourrait donner de la visibilité à ZdS à travers tous les articles mentionnant les ensembles de Julia mais aussi les fractales. Ce sont des pages très visitées (pour des pages de maths).

Bisous ! Et bonne année 2018

Juste une remarque rapide en passant avant que je me penche plus en détail dessus : le format PNG est un cauchemar à gérer en parallèle et pour en accéder qu’une portion définie. Il y aurait intérêt à stocker le résultat du calcul dans un format plus efficace pour les IO parallèles et la lecture partielle, genre du HDF5.

Ça peut bien sûr être un autre format.

Qu’est-ce qu’il y a comme solutions ?

Le HDF5 est facile à manipuler ? À convertir si besoin ?

J’adore ce genre de projets

Est-ce que le découpage en deux parties a une autre raison d’être que "ça semble logique alors pourquoi pas" ? Est-ce que ça ne serait pas envisageable de générer à la volée la fenêtre d’image demandée dans le visualiseur ? Pas forcément quelque chose d’aussi naïf que ça en a l’air, mais coupler un peu plus les deux permet d’éviter de générer des bouts de l’image inutiles (parce qu’ils sont super loin par exemple), et ça me semble plus efficace pour faire des super zooms que tout générer avec une résolution énorme.

Bien sûr, il y a d’autres choses que ça ne permet pas de faire, d’où ma question de départ. Peut-être aussi que le but c’est juste de générer des très gros fichiers images, auquel cas je suis à côté de la plaque

Peut-être aussi que le but c’est juste de générer des très gros fichiers images

Petarabbit !!!

Le but est de générer de grosses images

Mon code actuel permet déjà de faire ce que tu dis : calculer à la volée selon la zone visée

Coucou tout le monde !

Le code actuel est là, il faut compiler avec SFML pour la gestion de la fenêtre et lodpng pour la création de la photo

C’est encore un peu le bordel dans le main … il faudra aussi penser à changer le chemin du fichier pour la sauvegarde de la photo

Bonsoir,

Chouette projet ! J’ai essayé de compiler ton programme sans succès avec la commande g++ -o output *.cpp -std=c++11. C’est la première fois que je compile un programme en C++, aussi je ne sais pas si je m’y suis bien pris. Pourrais-tu indiquer les instructions pour compiler s’il te plaît ?

Merci !

Le message d’erreur:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

$ g++ -o output *.cpp -std=c++11

In file included from Algebre.cpp:9:0:
Algebre.h:173:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene(Homogene)> fonctionRationnelle;
       ^~~~~~~~
Algebre.cpp: Dans le constructeur « FractionRationnelle::FractionRationnelle() »:
Algebre.cpp:405:2: error: « fonctionRationnelle » n'a pas été déclaré dans cette portée
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
Algebre.cpp:405:2: note: alternatives suggérées: « FractionRationnelle »
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
  FractionRationnelle
Algebre.cpp: Dans le constructeur « FractionRationnelle::FractionRationnelle(Polynome) »:
Algebre.cpp:413:2: error: « fonctionRationnelle » n'a pas été déclaré dans cette portée
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
Algebre.cpp:413:2: note: alternatives suggérées: « FractionRationnelle »
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
  FractionRationnelle
Algebre.cpp: Dans le constructeur « FractionRationnelle::FractionRationnelle(Polynome, Polynome) »:
Algebre.cpp:421:2: error: « fonctionRationnelle » n'a pas été déclaré dans cette portée
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
Algebre.cpp:421:2: note: alternatives suggérées: « FractionRationnelle »
  fonctionRationnelle = [nume, deno](Homogene point){return evaluationAuPoint(nume, deno, point);};
  ^~~~~~~~~~~~~~~~~~~
  FractionRationnelle
In file included from Cycle.h:7:0,
                 from Cycle.cpp:1:
Algebre.h:173:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene(Homogene)> fonctionRationnelle;
       ^~~~~~~~
In file included from Cycle.cpp:1:0:
Cycle.h:20:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene(Homogene)> fonctionIteree;
       ^~~~~~~~
Cycle.h:22:21: error: expected « ) » before « < » token
  Cycle(std::function<Homogene (Homogene)> fonctionAIterer):fonctionIteree(fonctionAIterer){};
                     ^
Cycle.cpp: Dans la fonction membre « bool Cycle::donneUnCycle(Homogene) »:
Cycle.cpp:16:8: error: « fonctionIteree » n'a pas été déclaré dans cette portée
   z0 = fonctionIteree(z0);
        ^~~~~~~~~~~~~~
In file included from Julia.h:12:0,
                 from Julia.cpp:1:
Algebre.h:173:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene(Homogene)> fonctionRationnelle;
       ^~~~~~~~
In file included from Julia.h:13:0,
                 from Julia.cpp:1:
Cycle.h:20:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene(Homogene)> fonctionIteree;
       ^~~~~~~~
Cycle.h:22:21: error: expected « ) » before « < » token
  Cycle(std::function<Homogene (Homogene)> fonctionAIterer):fonctionIteree(fonctionAIterer){};
                     ^
In file included from Julia.cpp:1:0:
Julia.h:20:7: error: « function » dans l'espace de noms « std » ne nomme pas un type de patron
  std::function<Homogene (Homogene)> fonctionIteree;
       ^~~~~~~~
Julia.h:35:21: error: expected « ) » before « < » token
  Julia(std::function<Homogene (Homogene)> fonction);
                     ^
Julia.cpp:9:13: error: expected constructor, destructor, or type conversion before « ( » token
 Julia::Julia(std::function<Homogene (Homogene)> fonction): fonctionIteree(fonction), moteurDesCycles(Cycle(fonction)){
             ^
Julia.cpp: Dans la fonction membre « bool Julia::nEstPasDejaUnCycle(Homogene, double) »:
Julia.cpp:92:12: error: « fonctionIteree » n'a pas été déclaré dans cette portée
    copie = fonctionIteree(copie);
            ^~~~~~~~~~~~~~
Julia.cpp: Dans la fonction membre « Complexe Julia::convergenceDe(Homogene, double) »:
Julia.cpp:120:7: error: « fonctionIteree » n'a pas été déclaré dans cette portée
   z = fonctionIteree(z);
       ^~~~~~~~~~~~~~
Julia.cpp:137:12: error: « fonctionIteree » n'a pas été déclaré dans cette portée
    copie = fonctionIteree(copie);
            ^~~~~~~~~~~~~~
Julia.cpp: Au niveau global:
Julia.cpp:153:7: error: « function » n'a pas été déclaré
       function<Complexe(Homogene)> convergenceDe,
       ^~~~~~~~
Julia.cpp:153:15: error: expected « , » or « ... » before « < » token
       function<Complexe(Homogene)> convergenceDe,
               ^
Julia.cpp: Dans la fonction « void calculeLigne(int, int, int, double, Complexe, int, bool, int) »:
Julia.cpp:168:34: error: « convergenceDe » n'a pas été déclaré dans cette portée
   Complexe resultatConvergence = convergenceDe(z);
                                  ^~~~~~~~~~~~~
Julia.cpp:177:6: error: « matrice » n'a pas été déclaré dans cette portée
    (*matrice)[k] = Vertex(Vector2f(j,y), Color(couleur,couleur,couleur));
      ^~~~~~~
Julia.cpp:177:6: note: alternatives suggérées: « mktime »
    (*matrice)[k] = Vertex(Vector2f(j,y), Color(couleur,couleur,couleur));
      ^~~~~~~
      mktime
Julia.cpp:182:8: error: « matrice » n'a pas été déclaré dans cette portée
      (*matrice)[k] = Vertex(Vector2f(j,y), Color(couleur,couleur,couleur));
        ^~~~~~~
Julia.cpp:182:8: note: alternatives suggérées: « mktime »
      (*matrice)[k] = Vertex(Vector2f(j,y), Color(couleur,couleur,couleur));
        ^~~~~~~
        mktime
Julia.cpp: Dans la fonction membre « sf::VertexArray Julia::creeLaMatrice(int, int, double, Complexe) »:
Julia.cpp:220:2: error: « function » n'a pas été déclaré dans cette portée
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
  ^~~~~~~~
Julia.cpp:220:2: note: alternatives suggérées: « union »
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
  ^~~~~~~~
  union
Julia.cpp:220:19: error: expected primary-expression before « ( » token
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
                   ^
Julia.cpp:220:28: error: expected primary-expression before « ) » token
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
                            ^
Julia.cpp:220:31: error: « convergenceDuPoint » n'a pas été déclaré dans cette portée
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
                               ^~~~~~~~~~~~~~~~~~
Julia.cpp:220:31: note: alternatives suggérées: « convergenceDe »
  function<Complexe(Homogene)> convergenceDuPoint = [this](Homogene p){return convergenceDe(p);};
                               ^~~~~~~~~~~~~~~~~~
                               convergenceDe

Pour ne rien cacher, je laisse xcode gérer le bordel de la compilation …

De vue, je dirais qu’il te manque au moins la mention de lodpng et de SFML pour la compilation. Mais il faudrait que quelqu’un de plus calé te réponde pour avoir une réponse satisfaisante.

Je ne sais pas ce que j’ai fait mais après avoir ajouté #include <functional> dans le main, puis compilé les fichiers main et lodepng avec g++ -c main.cpp lodepng.cpp -std=c++11, suivi de g++ main.o lodepng.o -o petarabbit -lsfml-graphics -lsfml-window -lsfml-system -lpthread, après appel du programme j’obtiens la fameuse image au format png. Par contre un core dumped a brutalement fermé la fenêtre qui affichait l’image…

J’ai réussi à trouver l’origine du bug, je fork, puis envoie la PR

EDIT: la voilà https://github.com/Holosmos/pentaRabbit/pull/1

Visiblement SFML est pas clean sur un problème de taille de fenêtre. On est en train d’en parler sur le sujet du fork de naegi

De toute façon, faudrait se passer de SFML pour cette partie du programme et faire un visualiseur séparé. (Comme proposé plus haut.)

@Thomas : ta suite de commandes ne fonctionne pas chez moi

Ok ça marche parfaitement

(J’ai update la présentation)

Update sur le code

J’ai bossé sur le code, il y a eu quelques évolutions :

Sur la structuration globale

Tout d’abord j’ai repensé la structure du premier et deuxième axe. Dorénavant :

• Le premier axe gère l’aspect mathématique descriptif : structures algébriques, définition de la dynamique discrète et du critère de convergence.
• Le second axe joue le rôle de pilote : il lance les tests de convergence sur les points. C’est ici que se joue le multithreading.

Actuellement les fichiers sont répartis de la façon suivante :

• Premier axe = Algebre.cpp, Julia.cpp, Cycle.cpp, Mandelbrot.cpp
• Deuxième axe = Dynamicien.cpp
• Troisième axe = main.cpp avec SFML et lodepng.cpp

Ce qu’il s’est passé sur le code depuis

• Dégagement du premier axe avec le second par la création d’une structure “Dynamicien” ayant pour vocation à être le lieu du déclenchement des calculs. C’est là qu’il faudra mettre en place le multhreading et potentiellement le découpage en unité d’images.
• Dynamicien ignore totalement le premier axe : il n’a besoin que d’une fonction donnant un résultat de convergence pour un point donné. Il sera donc très facile de rajouter des dynamiques à simuler.
• J’ai rendu relativement étanche la partie dédiée à la fenêtre SFML du reste. Une fois qu’on en aura marre, on pourra purement et simplement supprimer le code en question. Comme ça, ceux qui ont des bugs peuvent déjà le supprimer.

De façon plus anecdotique, j’ai rajouté le code pour faire l’ensemble de Mandelbrot, et j’ai déjà produit une image à 1Md et y a d’autres exemplaires sur mon site. Le souci que j’ai c’est une limite de mémoire : je sais pas comment avoir des tableaux plus grand. J’ai peur d’être contraint à la fraction de l’image :(.

Pour le threading, vous comptez utiliser quelle type d’approche ? Avez-vous considéré OpenMP (qui permet de threader un code existant à très faible coût en terme d’effort).

Pour la limite de mémoire, il suffit simplement de construire l’image par morceaux je pense (cela est d’ailleurs une stratégie possible de division du travail).

Je n’y connais rien en threading GPU. On m’a conseillé OpenCL parce qu’elle prend en charge le chipset Intel (c’est ce que j’ai). Mais si quelqu’un veut se lancer avec une autre solution, le git est là pour ça

OpenMP est pour du CPU… Je suis pas convaincu que ce soit une bonne stratégie pour le problème présent de toute façon puisqu’il y a peu de shared state entre les threads, ce qui casse l’intérêt du shared memory.

Après tout, est-ce qu’on a vraiment besoin d’un shared memory ?

Le frein actuellement c’est la puissance de calcul brut. Avec le code actuel, j’ai résolu le problème des quantités de mémoires astronomiques nécessaires.

Quand je parles de problèmes de mémoire dans mon post précédent, c’est un problème de code : les tableaux que j’utilise sont certainement indexés sur 32 bits. C’est cette limite que j’ai besoin de lever. C’est plutôt dans la direction d’un changement de format que la nécessité de plus de mémoire.