{"id":270,"date":"2017-04-25T19:12:29","date_gmt":"2017-04-25T19:12:29","guid":{"rendered":"http:\/\/learningcenter.paratools.com\/?p=270"},"modified":"2022-04-14T14:04:47","modified_gmt":"2022-04-14T14:04:47","slug":"lensemble-de-mandelbrot","status":"publish","type":"post","link":"https:\/\/learningcenter.paratools.com\/?p=270","title":{"rendered":"L&rsquo;ensemble de Mandelbrot"},"content":{"rendered":"<p>Dans cet article nous allons explorer l&rsquo;ensemble de Mandelbrot. Le but ici est de se familiariser avec le d\u00e9veloppement C tout en mettant en place une version initiale d&rsquo;un calcul relativement intensif. L&rsquo;exemple retenu ici est le dessin de l&rsquo;ensemble de Mandelbrot en reposant sur la petite<a href=\"http:\/\/learningcenter.paratools.com\/?p=255\"> biblioth\u00e8que de dessin PPM que nous avons pr\u00e9c\u00e9dement introduite<\/a>. Ensuite, une fois le probl\u00e8me initial d\u00e9finit et une premi\u00e8re impl\u00e9mentation r\u00e9alis\u00e9e, nous profilerons le programme pour identifier de potentielles optimisations. Enfin nous r\u00e9aliserons une \u00e9tude de scalabilit\u00e9 sur architecture KNL pour illustrer les m\u00e9triques de performance HPC de base.<\/p>\n<p><!--more--><\/p>\n<h1>L&rsquo;ensemble de Mandelbrot<\/h1>\n<p style=\"text-align: center;\"><iframe loading=\"lazy\" src=\"https:\/\/www.youtube.com\/embed\/ay8OMOsf6AQ\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>Benoit Mandelbrot, de nationalit\u00e9 Fran\u00e7aise pr\u00e9sente la notion de rugosit\u00e9 dans la vid\u00e9o ci-dessus. Nous allons ici nous int\u00e9r\u00e9sser \u00e0\u00a0<a href=\"https:\/\/fr.wikipedia.org\/wiki\/Ensemble_de_Mandelbrot\">la fractale qui porte son nom<\/a>. Cet objet de curiosit\u00e9 est d&rsquo;une infinie complexit\u00e9 bien que commes nous allons voir naissant d&rsquo;une simple formule r\u00e9p\u00e9t\u00e9e infiniment. O\u00f9 comme le dit Mr. Mandelbrot \u00e0 la fin de la vid\u00e9o ci-dessus: <strong>\u00ab\u00a0Des merveilles insondables naissent de r\u00e8gles simples.. r\u00e9p\u00e9t\u00e9e ind\u00e9finiment\u00a0\u00bb<\/strong>.<\/p>\n<p>Ici nous allons tout d&rsquo;abord d\u00e9finir la m\u00e9thode pour g\u00e9n\u00e9rer cet ensemble qui est d\u00e9fini dans le plan complexe. On note Z un nombre complexe et ^2 le carr\u00e9 de ce nombre. Enfin on d\u00e9finit |Z| comme le module d&rsquo;un nombre complexe.<\/p>\n<p>L&rsquo;ensemble de Mandelbrot est d\u00e9fini de mani\u00e8re r\u00e9cursive pour tout point du plan complexe c comme suit:<\/p>\n<p>Z(0) = 0<br \/>\nZ(n+1) = Z(n)^2 + c<\/p>\n<p>L&rsquo;ensemble de Mandelbrot M est tel que cette suite est born\u00e9e. Attachons nous maintenant \u00e0 d\u00e9finir en termes informatiques cette abstraction math\u00e9matique.<\/p>\n<h2>Les Complexes en C<\/h2>\n<p>On l&rsquo;oublie parfois mais le C propose en standard des fonction et un support des nombres complexes. Pour le v\u00e9rifier vous pouvez consulter le manuel associ\u00e9:<\/p>\n<pre class=\"brush: bash; title: ; notranslate\" title=\"\">\r\nman complex\r\n<\/pre>\n<h2>Mandelbrot en C<\/h2>\n<p>Nous allons donc utiliser ces nombres directement, \u00e9vitant ainsi de r\u00e9inventer des complexes et de nous tromper dans les calculs de modules et de produits. Repr\u00e9sentons nous maintenant l&rsquo;ensemble de Mandelbrot:<\/p>\n<p><a href=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/440px-Mandelset_hires.png\"><img loading=\"lazy\" class=\"aligncenter size-full wp-image-282\" src=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/440px-Mandelset_hires.png\" alt=\"\" width=\"440\" height=\"323\" srcset=\"https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/440px-Mandelset_hires.png 440w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/440px-Mandelset_hires-300x220.png 300w\" sizes=\"(max-width: 440px) 100vw, 440px\" \/><\/a><br \/>\nSOURCE ARTICLE WIKIPEDIA (domaine public)<\/p>\n<p>On voit ici qu&rsquo;il est pr\u00e9sent dans le plan complexe entre -2 et 1 sur l&rsquo;axe des r\u00e9els et entre -1 et 1 sur l&rsquo;axe des immaginaires. Dans une approche informatiques nous allons bien s\u00fbr devoir discr\u00e9tiser cet espace pour y op\u00e9rer les calculs, la m\u00e9moire de nos machines \u00e9tant limit\u00e9e. La premi\u00e8re t\u00e2che est donc d&rsquo;associer l&rsquo;espace de d\u00e9finition de M \u00e0 un tableau 2D de nombre complexes C, index\u00e9s de 0 \u00e0 N.<\/p>\n<p>Pour ce faire, il faut r\u00e9aliser des fonction donnant pour un point du tableau ses coordonn\u00e9es complexes telles qu&rsquo;elle couvrent de mani\u00e8re uniforme l&rsquo;espace cible. Cela revient \u00e0 diviser uniform\u00e9ment, largeur et hauteur par le nombre de cases dans chaque dimension pour d\u00e9finir un pas <i>q<\/i> correspondant \u00e0 la \u00ab\u00a0largeur\u00a0\u00bb d&rsquo;une case.<\/p>\n<p>On peut donc d\u00e9finir notre plan complexe comme suit:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &amp;lt;complex.h&amp;gt;\r\n\r\n#define SIZEX 5000\r\n#define SIZEY 5000\r\n\r\ndouble cx( int x )\r\n{\r\n\t\/* -2 ---&gt; 1 *\/\r\n\tstatic const double qx = 3.0 \/ (double)SIZEX;\r\n\treturn -2.0 +  x * qx;\r\n}\r\n\r\ndouble cy( int y )\r\n{\r\n\t\/* -1 ---&gt; 1 *\/\r\n\tstatic const double qy = 2.0 \/ (double)SIZEY;\r\n\treturn -1.0 + y * qy;\r\n}\r\n<\/pre>\n<p>En utilisant ces deux fonctions il est alors possible de faire correspondre chaque case du tableau \u00e0 un point du plan complexe. Nous allons maintenant \u00e9crire le calcul des points dans l&rsquo;ensemble de Mandelbrot. Pour rappel ils sont d\u00e9finis par la fonctions r\u00e9cursive ci dessus sachant de plus que le module de la suite doit \u00eatre inf\u00e9rieur \u00e0 2.0 pour ne pas diverger, donnant un point d&rsquo;arr\u00eat plus pratique \u00e0 la r\u00e9cursivit\u00e9. De plus, l&rsquo;ensemble est g\u00e9n\u00e9ralement color\u00e9 en fonction du nombre d&rsquo;it\u00e9ration avant d&rsquo;atteindre cette limite de module. Enfin, afin de ne pas itt\u00e9rer infiniment sur certains points, une limite d&rsquo;itt\u00e9rations est fix\u00e9es, limitant le nombre d&rsquo;invocation indif\u00e9ramment du module. On obtient donc pour un point du plan complexe aux coordonn\u00e9es (x,y) du tableau le calcul suivant:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#define TRSH 2.0\r\n#define ITER 150ull\r\n\r\nunsigned long int iter = 0;\r\n\r\ndouble complex c =  cx(x) + cy(y) * I;\r\ndouble complex z = 0;\r\n\r\nwhile(iter &lt; ITER)\r\n{\r\n    double mod = cabs(z);\r\n\r\n    if( TRSH &lt; mod )\r\n    {\r\n        break;\r\n    }\r\n\r\n    z = z*z + c;\r\n\r\n    iter++;\r\n}\r\n\r\ncolor[x][y] = iter;\r\n<\/pre>\n<p>En appliquant maintenant cette formule \u00e0 l&rsquo;ensemble des points du plan complexe \u00e9chantillon\u00e9s par SIZEX et SIZEY, nous pouvons maintenant dessiner l&rsquo;ensemble de Mandelbrot.<\/p>\n<p><a href=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2.jpg\"><img loading=\"lazy\" class=\"aligncenter size-medium wp-image-305\" src=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" srcset=\"https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2-300x300.jpg 300w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2-150x150.jpg 150w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2-768x768.jpg 768w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2-940x940.jpg 940w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-2.jpg 1500w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<h1>Le Code Initial<\/h1>\n<p>Ce premier dessin repose sur le code suivant en utilisant la <a href=\"http:\/\/learningcenter.paratools.com\/?p=255\"> biblioth\u00e8que de dessin PPM que nous avons pr\u00e9c\u00e9dement impl\u00e9ment\u00e9e<\/a>.<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;stdio.h&gt;\r\n#include &lt;complex.h&gt;\r\n#include &lt;math.h&gt;\r\n#include &quot;ppm.h&quot;\r\n\r\n\r\n#define TRSH 2.0\r\n#define ITER 1024ull\r\n\r\n#define SIZEX 1500\r\n#define SIZEY 1500\r\n\r\ndouble cx( int x )\r\n{\r\n\t\/* -2 ---&gt; 1 *\/\r\n\tstatic const double qx = 3.0 \/ (double)SIZEX;\r\n\treturn -2.0 +  x * qx;\r\n}\r\n\r\ndouble cy( int y )\r\n{\r\n\t\/* -1 ---&gt; 1 *\/\r\n\tstatic const double qy = 2.0 \/ (double)SIZEY;\r\n\treturn -1.0 + y * qy;\r\n}\r\n\r\nint main(int argc, char *argv[])\r\n{\r\n\tstruct ppm_image im;\r\n\tppm_image_init( &amp;amp;im , SIZEX , SIZEY );\r\n\r\n\tint i,j;\r\n\tdouble colref = 255.0\/log(ITER);\r\n\r\n\tfor (i = 0; i &lt; SIZEX; ++i) {\r\n\t\tfor (j = 0; j &lt; SIZEY; ++j) {\r\n\r\n\t\t\tunsigned long int iter = 0;\r\n\r\n\t\t\tdouble complex c =  cx(i) + cy(j) * I;\r\n\t\t\tdouble complex z = 0;\r\n\r\n\t\t\twhile(iter &lt; ITER)\r\n\t\t\t{\r\n\t\t\t\tdouble mod = cabs(z);\r\n\r\n\t\t\t\tif( TRSH &amp;lt; mod )\r\n\t\t\t\t{\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tz = z*z + c;\r\n\r\n\t\t\t\titer++;\r\n\t\t\t}\r\n\r\n\t\t\tint grey = colref*log(iter);\r\n\t\t\tppm_image_setpixel(&amp;amp;im, i,j, grey, grey , grey );\r\n\t\t}\r\n\t}\r\n\r\n\tppm_image_dump( &amp;amp;im, &quot;m.ppm&quot;);\r\n\tppm_image_release( &amp;amp;im );\r\n\r\n\r\n\treturn 0;\r\n}\r\n<\/pre>\n<p>Dans ce code finalement tr\u00e8s simple, on cr\u00e9e une image PPM aux dimensions SIZEX et SIZEY. Ensuite on parcours le plan complexe et on calcule \u00ab\u00a0c\u00a0\u00bb les coordonn\u00e9es du point d&rsquo;origine. Puis, on applique la r\u00e9cursivit\u00e9 tant que le module est inf\u00e9rieur \u00e0 2.0 et que le nombre limite d&rsquo;it\u00e9ration n&rsquo;est pas d\u00e9pass\u00e9. Enfin, pour chaque point du plan retenu, on d\u00e9finit une couleur en niveau de gris dans l&rsquo;image PPM. Notez que pour des raisons de lisibilit\u00e9 la valeur source subit un LOG<\/p>\n<h1>Un peu de couleur<\/h1>\n<p>Cette visualisation est un peu terne, elle ne tire pas avantage des trois canaux de notre image PPM couleur, le rendu \u00e9tant fait en niveaux de gris. Nous alons maintenant parcourir le cube RGB (<a href=\"https:\/\/commons.wikimedia.org\/wiki\/File:RGB_color_solid_cube.png\">voir sur Wikimedia<\/a>) pour apporter plus de dynamique \u00e0 notre rendu. Le principe est relativement simple, il consiste \u00e0 plaquer la dynamique de niveau de gris (normalis\u00e9e entre 0 et 1 sur un nombre flotant) sur un parcours dans le cube RGB. On propose le code suivant (il est possible de tester avec une \u00e9chelle lin\u00e9aire):<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nstruct col\r\n{\r\n\tint r;\r\n\tint g;\r\n\tint b;\r\n};\r\n\r\nstruct col getcol( int val , int max )\r\n{\r\n\tdouble q = (double)val\/(double)max;\r\n\r\n\tstruct col c = { 0, 0, 0 };\r\n\r\n\tif( q &lt; 0.25 )\r\n\t{\r\n\t\t\tc.r = ( q * 4.0 ) * 255.0;\r\n\t\t\tc.b = 255;\r\n\t\t}\r\n\telse if( q &lt; 0.5 )\r\n\t{\r\n\t\t\tc.b = 255;\r\n\t\t\tc.g = 255;\r\n\t\t\tc.r = (q-0.25)*4.0*255.0;\r\n\r\n\t\t}\r\n\telse if( q &lt; 0.75 )\r\n\t{\r\n\t\t\tc.b = 255;\r\n\t\t\tc.r = 255;\r\n\t\t\tc.g = 255.0 - (q-0.5)*4.0*255.0;\r\n\t\t}\r\n\telse\r\n\t{\r\n\t\t\tc.b = 255-(q-0.75)*4.0*255.0;\r\n\t\t\tc.g = 0;\r\n\t\t\tc.r = 255;\r\n\t\t}\r\n\r\n\treturn c;\r\n}\r\n<\/pre>\n<p>Et on remplace le calcul de couleur:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\ndouble colref = log(ITER);\r\n\/\/...\r\nstruct col cc = getcol( log(iter), colref );\r\nppm_image_setpixel(&amp;im, i,j, cc.r, cc.g , cc.b );\r\n<\/pre>\n<p>Ce qui donne le r\u00e9sultat suivant un peu plus color\u00e9:<\/p>\n<p><a href=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc.jpg\"><img loading=\"lazy\" src=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" class=\"aligncenter size-medium wp-image-312\" srcset=\"https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc-300x300.jpg 300w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc-150x150.jpg 150w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc-768x768.jpg 768w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mc-940x940.jpg 940w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355.jpg\"><img loading=\"lazy\" src=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" class=\"aligncenter size-medium wp-image-317\" srcset=\"https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355-300x300.jpg 300w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355-150x150.jpg 150w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355-768x768.jpg 768w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355-940x940.jpg 940w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/m-0-355.jpg 2000w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc.jpg\"><img loading=\"lazy\" src=\"http:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc-300x300.jpg\" alt=\"\" width=\"300\" height=\"300\" class=\"aligncenter size-medium wp-image-320\" srcset=\"https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc-300x300.jpg 300w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc-150x150.jpg 150w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc-768x768.jpg 768w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc-940x940.jpg 940w, https:\/\/learningcenter.paratools.com\/wp-content\/uploads\/2017\/04\/mcc.jpg 2000w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<h1>Performances S\u00e9quentielles<\/h1>\n<p>TODO<\/p>\n<h1>Parall\u00e9lisation OpenMP<\/h1>\n<p>TODO<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dans cet article nous allons explorer l&rsquo;ensemble de Mandelbrot. Le but ici est de se familiariser avec le d\u00e9veloppement C tout en mettant en place une version initiale d&rsquo;un calcul relativement intensif. L&rsquo;exemple retenu ici est le dessin de l&rsquo;ensemble de Mandelbrot en reposant sur la petite biblioth\u00e8que de dessin PPM que nous avons pr\u00e9c\u00e9dement [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[36,40,4],"tags":[41,42,39,7],"_links":{"self":[{"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/posts\/270"}],"collection":[{"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=270"}],"version-history":[{"count":44,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/posts\/270\/revisions"}],"predecessor-version":[{"id":321,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=\/wp\/v2\/posts\/270\/revisions\/321"}],"wp:attachment":[{"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=270"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=270"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learningcenter.paratools.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=270"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}