PetaRabbit

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

Je dis que non, justement. "Shared memory", c’est une stratégie de parallélisation (utilisé par OpenMP) dans lequel l’ensemble des threads utilise la même mémoire. C’est surtout utile quand on a besoin de beaucoup de communication entre les différents threads.

Ça n’a pas grand chose à voir avec la quantité de mémoire disponible sur la machine.

Ah ok. C’est juste que ton "il y a peu de .." était ambigu sur ce que le "il" représentait (l’algo ou OpenMP)

OpenMP permet effectivement l’approche shared-memory, mais je le vois surtout comme une des solutions les plus simples pour paralléliser un code existant. Le fait que la mémoire soit partagée n’est pas un problème en soi, en pratique cela signifie simplement que c’est du parallélisme de type "thread" (et non processus).

Tant que le programme est destiné à tourner sur la même machine (et exploiter surtout le CPU), c’est une des solutions les plus simples possibles AMHA.

Il y a déjà une parallélisation en place : j’utilise deux threads pour exploiter mon dual-core.

Et si j’ai 8 coeurs, le programme sait s’adapter ou non ? Si non, ce n’est pas très intéressant.

NB: Pour OpenMP, je viens de reprendre un ancien explorateur de fractales que j’avais fait (Mandelbrot et Julia) à titre d’exemple: il m’a pratiquement suffi d’ajouter une ligne et modifier les options de compilation pour le rendre parallèle.

1
2
3
4
5
6
7
8

    // parallelisation (ignore si pas de support OpenMP)
    #pragma omp parallel for collapse(2)
    // parcours des pixels de l'ecran
    for ( int y=0; y<screen->h; ++y )
        for ( int x=0; x<screen->w; ++x )
        {
            // boucle de traitement ici
        }

Bah pour huit coeur il y aurait quelques lignes à écrire en plus

Mais tu aurais pu le voir directement dans le code

Update

naegi a fait le boulot pour le multithreading avec openmp. Les perfs ne sont pas vraiment meilleures, mais maintenant ceux qui ont un quad-core peuvent directement en profiter. (Et le code a été un peu simplifié.)

Merci pour son boulot

Je viens de faire un tour sur le code. Au départ pour voir si je pouvais donner un coup de main, mais je vais me contenter de quelques critiques (et je suis loin d’avoir tout vu) :

• pourquoi ré-implémenter une classe Complexe, alors que C++ dispose d’une classe complex native (sans doute plus efficace).
• pas de const-correctness dans tes classes, pas de passage par référence, autant de choses qui peuvent grandement affecter la performance d’un programme C++.
• lorsqu’on utilise une struct, ce n’est généralement pas pour écrire des getters, vu que tout est public.
• le code du calcul d’une fractale semble trop complexe. je ne suis pas vraiment matheux, mais on trouve sur le net des sources d’inspiration franchement plus simple à appréhender (exemple).

le code du calcul d’une fractale semble trop complexe. je ne suis pas vraiment matheux, mais on trouve sur le net des sources d’inspiration franchement plus simple à appréhender

La partie maths est celle sur laquelle je suis le moins prêt à faire des concessions sans une critique précise.

L’algorithme est moins simple que ceux utilisés habituellement mais il est plus performant et valable dans bien plus de cas que le simple polynôme $z^2+c$ (pour lequel il est quand même plus efficace).

Pour le reste, je l’ai dit, je suis pas codeur expérimenté. Je vais voir cette classe complex native, que je ne connaissais pas. L’intégrer sera probablement facile.

La partie maths est celle sur laquelle je suis le moins prêt à faire des concessions sans une critique précise.

Je veux bien, encore faut-il que je comprennes ce que tu fais

Pourrais-tu expliquer ce raffinement algorithmique un peu plus en détail ? Il me semble que c’est là le point intéressant dans ton code, et j’aimerais bien en savoir plus.

J’ai un vieux papier qui traine ici, y a tous les détails.

Dans le principe, ça fonctionne comme ça :

Tout d’abord, faut savoir qu’un ensemble de Julia, c’est l’ensemble des points qui ne convergent pas vers un cycle attractif. Pour les polynômes, l’un de ces cycles est le point à l’infini (qui est fixe, et attractif, c’est donc bien un cycle attractif). La plupart des algorithmes se contentent de chercher le bassin du point à l’infini, ça donne ce qu’on appelle l’ensemble de Julia rempli.

Mon algorithme fonctionne en deux étapes :

• Pour une fraction rationnelle donnée, on cherche des cycles attractifs (ça se fait rapidement, de façon largement efficace par rapport au reste). Par exemple pour le lapin on en trouve 2 : celui à l’infini et puis un autre cycle.
• Pour chaque pixel à dessiner, on itère et on attend de voir quand est-ce qu’il va tomber proche d’un cycle attractif. On colore selon le temps qu’il a fallu.

Les gros avantages sont les suivants :

• L’ajouts de cycles attractifs dans la collection ne change pas particulièrement la complexité. Le gros de la complexité vient du nombre d’itérations qu’il faut produire pour calculer la convergence d’un point. Sauf qu’un cycle qui n’est pas détecté, c’est tout son bassin qui doit passer par toutes les itérations. Un ensemble de Julia fait de façon naïve va demander énormément de calculs pour les points qui convergent vers des cycles qui ne sont pas le point à l’infini. Donc il y a réduction drastique du nombre d’itérations produites. D’ailleurs, par un argument mathématique, on peut montrer que l’ensemble de Julia est (dans les cas qu’on étudie) de mesure nulle, il est donc très improbable d’avoir des points qui demandent beaucoup d’itérations : c’est pour ça que les images sont surtout en gris clair et que les points noirs sont rares.
• On peut calculer des ensembles de Julia pour autre chose que des polynômes. C’est ce qui est nécessaire pour calculer des fractales de Newton par exemple.
• On a une information sur le cycle vers lequel ça converge. Ça permet de proposer une coloration, et ça apporte une information dynamique importante. Dans le code par défaut c’est en noir et blanc, mais en passant en mode couleur, ça le fait (et gratuitement en plus).

Update

Sinon j’ai suivi ta recommendation et j’ai fait le remplacement de Complexe par complex<double>. Les perfs semblent pas particulièrement meilleures. Ceci dit c’est plus propre

Pour les questions de copie en ref, etc. je suis pas assez habitué, faudrait que quelqu’un m’indique plus précisément là où faut faire les changements.

Merci pour les explications, je vois mieux ce que tu veux dire.

Mon algorithme fonctionne en deux étapes :

• Pour une fraction rationnelle donnée, on cherche des cycles attractifs (ça se fait rapidement, de façon largement efficace par rapport au reste). Par exemple pour le lapin on en trouve 2 : celui à l’infini et puis un autre cycle.
• Pour chaque pixel à dessiner, on itère et on attend de voir quand est-ce qu’il va tomber proche d’un cycle attractif. On colore selon le temps qu’il a fallu.

Combien y a t’il de cycles en général ? Apparemment, dans les cas que Wikipedia surnomme "poussière de Cantor" il n’y a qu’un attracteur à l’infini.

Apparemment, dans les cas que Wikipedia surnomme "poussière de Cantor" il n’y a qu’un attracteur à l’infini.

Oui ça arrive qu’il n’y ait qu’un seul cycle, mais c’est relativement rare.

Combien y en-a-t-il en général ? Ça dépend entièrement de la fonction étudiée, il peut en avoir autant que tu veux (suffit pour ça de considérer la méthode de Newton d’un polynôme ayant autant de racines que de cycles désirées).

Pour les exemples que j’ai donnés dans mes fichiers, ça va de 1 (pour le collier, qui n’est d’ailleurs pas à l’infini) à 16 (pour le pentagone).

Ceci dit, ça me paraît raisonnable de penser le nombre de cycles comme négligeable devant le nombre d’itérations à effectuer au maximum.

Update

J’ai surtout fait du ménage ces derniers temps. Normalement le code est plus propre …

Faudrait que je prenne le temps, ou que quelqu’un le fasse, de se pencher sur HDF5 pour commencer à générer des images aussi grosses que voulues

Update

L’idée de faire une présentation par des tuiles a été implémentée, et tourne bien.

C’est dans la branche Tuiles du git, vous pouvez déjà l’utiliser.

Pour le futur

Cette solution est sympa mais sort un peu du but initial de Petarabbit.

Il faut toujours des gens motivés pour :

• Mettre en place de quoi visionner de grosses images.
• Mettre en place le format de fichier pour ces grosses images.

Voilà je suis le projet depuis peut mais il me semble qu’il manque le fichier des dépendances dans le projet(fichier optionnel mais utile pour la gestion d’un projet)
Si quelqu’un veut l’ajouter(je ne connait pas toutes les dépendances du projet, si on me donne un liste je veut bien le faire)
Voir ici pour un peu de doc par rapport à GitHub

Ah oui ça fait un moment que j’ai pas eu le temps de me replonger dans le code …

Tu veux savoir quoi ? De mémoire le post initial était à jour pour correspondre à l’état du code

Ces fichiers là sont pour les projets Ruby et JS, là c’est du C++. Lire le CMakeLists suffit pour voir ce qu’il faut, en l’occurrence la seule dépendance est OpenMP (qui de toute façon est en général installée lorsque tu installes la suite GCC).

oui, je me doutais bien que la liste des fichiers qui était donné par gh ne correspondais pas au projet, mais je sait pas pourquoi j’ai l’impression qu’il manque ce fichier listant les dépendances
J’ai fait cette remarque car je n’arrive pas à builder le projet avec cmake(erreur de dépendances ou de fichier non existant)

Il faut installer la SFML aussi. Mais en fait, le CMakeLists n’est pas à jour, j’ai fait une PR pour corriger ça.