Avalanches dans les écosystèmes computationnels

Singularités plurielles

Avalanches
dans
les écosystèmes computationnels

Juan Luis Jimenez Laredo, Frédéric Guinand, Damien Olivier, Yoann Pigné et Charlie

Rochebrune, janvier 2015

Singularité ? Quand j'ai vu l'appel à communication de Rochebrune j'ai eu envie de participer, alors je me suis interrogé sur ce que je pouvais apporter au débat. Je vous propose de suivre la démarche entreprise, un peu pour meubler !! mais aussi pour montrer les racines d'un travail en cours avec mes collègues : Juan, Yoann, Frédéric. Je vais essayer de vous emmener sur des pistes souvent enneigées, ou plutôt ensablées pas encore complètement explorées à notre niveau. Nous ne maîtrisons pas par exemple l'état de l'art et ce séjour à Rochebrune va j'en suis sur être l'occasion de compléter nos connaissances. De quoi va t-il donc être question : d'avalanche de processus, de taches dans des réseaux de machines/processeurs/calculateurs et l'idée que ces avalanches sont intéressantes pour gérer leurs répartitions. Derrière cela se cache des singularités et plus encore peut-être la volonté d'entretenir ces singularités.

Au menu ce soir

Singularité quesako ?
Utilisation de la singularité
Puisqu'il faut une conclusion

Singularité quesako ?

Singularité ?

Changement brusque dans l’évolution, la structure, la forme d’un système physique, vivant, artificiel ou d’une trajectoire.

Singularité d'une fonction $f$.

C'est un point $p_0$ pour lequel le "comportement" de l'équation $f(x)$ n'est pas semblable à celui des points $p$ voisin de $p_0$.

Source

Singularités mathématiques

Générique versus singulier

Source

Générique

Étant donné une collection d’objets $x$ formant un espace $X$ (mesuré, topologique, ou algébrique...), on dit qu’une propriété $\cal{P}$ de ces objets est générique si elle est vraie « presque partout », c’est-à-dire pour « presque tout » objet $x$.

Singulier

Les $x$ qui ne vérifient pas $\cal{P}$ sont singuliers (eu égard à $\cal{P}$). « Singularité » a donc valeur d’ « exception », de « dégénérescence ». C’est par exemple le lieu où certaines fonctions ne sont pas « bien définies », où certaines quantités deviennent infinies, etc...

La singularité m'a amené à m'interroger sur l'aspect général et donc sur la généricité par opposition. Dans beaucoup de présentation il a été évoqué l'importance de la singularité, sans prendre le contre pied total, il me semble important d'insister aussi sur la généricité outil de l'analogie.
D. Hofstadter est en lutte avec les formes de l'IA actuelle qui lui semble privilégier la puissance de calcul plutôt que chercher à comprendre les faits de pensée. Les succès actuels ne sont que le résultat des machines toujours plus puissantes. Je vais sans doute trahir son propos, mais après tout c'est le résultat de mon appropriation.

l'analogie détermine le flot de la pensée dans son entier et à tout instant. Toute pensée est analogie. Non seulement l'analogie est le moteur de la cognition, elle en est aussi l'essence, dans les deux sens de ce mot. Nous faisons tous des analogies plusieurs fois par seconde. Chaque perception repose sur une analogie. Chaque choix de mot implique une analogie, ou peut-être plusieurs. Et chaque concept s'étend sans cesse par analogie. Prenez le concept de "maman". Quand vous étiez enfant "maman" signifiait évidemment votre propre mère. Quelque chose de singulier, de particulier. Au fur et à mesure le concept se généralise, de singulier il devient générique. Vous avez ensuite remarqué que d'autres femmes s'occupent d'autres enfants et vous avez établi une analogie entre vous-même et un autre enfant, entre une autre femme et votre Maman. Maman n'est plus singulier avec son M majuscule pour devenir maman avec son m minuscule. La généralisation se poursuit pour inclure les mamans d'animaux, on atteint le concept de mère, sur lequel vont venir s'agréger d'autres concepts comme "la Révolution américaine est la mère de la Révolution française" ou "l'oisiveté est la mère de la philosophie".

Singularités en informatique

Singularité technologique

Point hypothétique dans notre futur, à partir duquel nous atteindrons un niveau de croissance technologique d’un ordre supérieure.

Explosion de l’intelligence artificielle, des machines intelligentes conçoivent des machines plus intelligentes. I.J. Good (1960).

Avènement d’entités dépassant l’intelligence humaine. Ray Kurzweill (2005).

Extrait de A.I Intelligence Artificielle (CR : Warner Bros)

Il en faut bien un qui en parle. Rendons à Jack ce qui est à Jack. Jack Good (inférence bayésienne) est le premier à ma connaissance à en parler. Il a conseillé Kubrick pour 2001 Odyssée de l'espace et la première version comportait un prologue fait d'interview de scientifique.
Je m'inscrit dans la vision de l'état actuel de l'IA fait par Emmanuel Sander, Alain Cardon, Hofstadter qui constatent que la tendance rationnelle de l'IA et l'abandon de la vision anthropomorphique à conduit à laisser de coté comment on pense en terme de mécanisme même si on maîtrise de mieux en mieux la physiologie avec par exemple l'imagerie.
Pour demain c'est pas sur. Le coté prévision autour de la singularité technologique, transhumanisme me fait penser au propos tenu sur l'IA lors du congrès de Dartmouth en 1956 organisé par John McCarthy, Marvin Minksky, Nathaniel Rochester et Claude Shannon excusez du peu. Qui avait vu la naissance de terme mais aussi quelques prédictions fausses sur les échecs, les démonstrations mathématiques, la traduction .....
Je vous propose de quitter le sujet qui me semble plus approprié pour nos discussions de fin de soirée.

Singularités en informatique

Données pathologiques

Entrées provoquant un comportement atypique d'un algorithme, comme une violation de sa complexité en moyenne, ou même son exactitude.

Tables de hachage : jeux de clés qui entrent en collision sur les valeurs de hachage.

Quicksort normalement $O(n \log n)$ mais $O(n^2)$ dans certains cas.

Min/MAX ou alpha/beta sur la profondeur.

Sorting quicksort anim (Wikipedia)

La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite. Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié.
MIN/MAX thèse de Nau.

Singularités en informatique

Ecosystème computationnel

Écosystème : Ensemble structuré comprenant un substrat et la biocénose qui y vit. Cet ensemble est caractérisé par des échanges de matière et d’énergie dus aux interactions entre les organismes vivants et le substrat.

Simulation distribuée : Ensemble structuré comprenant un environnement d’exécution en éventuelle évolution, et des composants logiciels qui s’y exécutent. Cet ensemble est caractérisé par des échanges d’informations dus aux interactions entre les composants du système.

Singularités en informatique

Recherche de généricité
d'auto-organisation pour la distribution

Singularités en informatique

Données pathologiques

Utilisation de la singularité

Singularité naturelle

Métamorphose du fourmilion

Larve de fourmilion

Taille 10 mm, vie larvaire 2 ans environ

Singularité naturelle

Métamorphose du fourmilion

Cocon d'un fourmilion, durée de la phase 3 semaines

Imago

Fourmilion adulte

Singularité naturelle

Fonctionnement du piège du fourmilion

Source - National Geographic

Les formes de la partie haute et de la partie basse ne sont pas anodines, en effet voici comment le piège fonctionne : un petit insecte imprudent va s’aventurer sur le haut du cône mais sa pente n’est pas le fruit du hasard son angle est l’angle maximum d’avalanche (environ 30◦ ), la pente est donc très instable et notre malheureux va être embarqué par une avalanche de granulat et il va amplifier le phénomène en se débattant. Si par hasard, notre imprudent n’est pas entraîné par une avalanche le fourmilion force le destin en projetant des grains au dessus de sa proie. [Swanson, 2006]. [Duran, 2003] s’est interrogé sur la forme du piège et a constaté que si le piège était uniquement constitué de la partie haute, il fonctionnerait beaucoup moins bien puisqu’une fois l’avalanche produite, l’angle que fait la surface avec l’horizontale a diminué et constitue l’angle de repos du système, la pente est alors beaucoup plus stable [Rajchenbach, 2002]. En effet, la surface sur laquelle les grains issus de l’avalanche s’accumulent provoque une onde remontante qui va accumuler du sable vers le haut et du coup éloigner l’angle de la pente de l’angle d’avalanche. Le piège dans cette configuration ne peut fonctionner qu’un nombre limité de fois, mais notre ami le fourmilion, résultat d’une longue évolution, utilise un piège beaucoup plus sophistiqué que cela et ceci grâce à la partie basse. En effet, la configuration que nous venons de décrire correspond `a un cratère fermé mais si l’on y ajoute la partie cylindrique de sable mouillée le cratère devient «ouvert». Si l’on considère que le fourmilion maintient ce cylindre toujours libre en rejetant les exosquelettes de ses victimes et les grains de sable surnuméraires `a l’extérieur du piège, l’onde remontante ne se produit plus. La pente du piège est alors maintenue dans son état critique correspondant `a l’angle maximum d’avalanche.

Singularité naturelle

Le piège du fourmilion

Structure du piège

Champ de piège

Piège

Singularité naturelle

Il a tout compris, moi pas encore !

Physique des avalanches et des milieux granulaires ;
Entretien d'un état critique, angle critique $\frac{\Pi}{6}$ ;
Système ouvert ;
$\Rightarrow $ système critique auto-organisé .

État critique

État critique auto-organisé

Un état critique est défini dans le cadre de la théorie des transitions de phases comme un point de séparation entre plusieurs phases, pour lequel la longueur de corrélation du système est divergente. Cette longueur de corrélation est la distance au-delà de laquelle deux éléments pris au hasard dans le système ne sont plus «en phase» ou bien encore corrélés. Pour avoir une transition de phases il faut un paramètre de contrôle. Ce type de transition de phase est du second ordre (non linéaire). La notion de criticalité auto-organisée a été introduite par P. Bak, Tang et Wiesenfeld dans [Bak et al., 1987]. L’idée principale est que certains systèmes peuvent évoluer sans paramètre de contrôle, vers un état critique. Le système évolue alors naturellement vers un tel état, l’état critique auto-organisé étant un attracteur de la dynamique. On doit donc faire la différence entre un point critique et un point critique auto- organisé. Ainsi un point critique traditionnel est une transition entre deux états stables du système alors qu’un point critique auto-organisé se trouve entre deux états instables du système. Tout état instable tend `a atteindre l’état critique auto-organisé. Ainsi donc, la larve du fourmilion a compris depuis longtemps cette notion de criticalité auto-organisée et l’utilise. Le piège est dans un état critique auto-organisé, une perturbation par l’intermédiaire d’une proie se produit, l’avalanche se déclenche et le piège se retrouve à nouveau dans un état critique auto-organisé prêt à nouveau à fonctionner !

Modèle

Automate cellulaire

Les cellules représentent l'empilement des grains ;
Le tas est défini par une suite de nombres qui représentent la hauteur de chaque empilement ;
L’empilement $i$ dépend de la hauteur de ses voisins ;
Le modèle est unidimensionnel ;
Peu réaliste concernant la taille des avalanches .

Modèle

Automate cellulaire

Introduction d'aléatoire

Règle 1 mécanisme de chute. Si une cellule vide $c_{j−1}$ se trouve au dessous d'une cellule occupée $c_j$ , la pile des cellules occupées $c_j$ , $c_{j+1}$ , $c_{j+2}$ . . . se déplace vers le bas, respectivement en $c_{j−1}$ , $c_{j}$ , $c_{j+1}$...
Règle 2 : éboulement. Une pile est un empilement de cellules pleines de hauteur $h \geq 1$ dont le voisinage droit est vide Si $h = 1$ alors la cellule pleine se décale à droite, sinon on détermine de façon aléatoire le nombre $n$ de cellules pleines qui se décalent à droite. La règle 1 est prioritaire sur la règle 2.
$\Rightarrow$ Avalanches de taille variable.

Modèle

Modèle abélien du tas de sable - Bak–Tang–Wiesenfeld (1987)

Quadrillage de $n\times n$ cases ;
Dans chaque case, nous pouvons empiler au plus trois grains ;
S’il y a quatre grains dans une case donnée, un éboulement se produit : la case se vide de ses quatre grains qui sont envoyés dans les quatre cases voisines, un par case .

Propriétés

On atteint une configuration stable lorsque chaque case contient au maximum trois grains.
L'ordre des éboulements n'a pas d'importance.
Loi de puissance

Utilisation de la singularité

Environnement de calcul $=$ tas de sable ?

Dans le contexte de l'équilibrage de charge, même comportement ?

Environnement de calcul

Modèle

Automate cellulaire ;
Une cellule $\rightarrow$ une ressource de calcul (RC) ;
Hypothèse : chaque RC peut gérer $k$ tâches à la fois ;
Règle d'équilibrage : si $\mbox{charge}_{RC} > k$ alors transférer $m \leq k$ taches aux voisins.

Environnement de calcul

Modèle - Simulation

Volcan

Une tâche initiale génère une ou d'autres tâches quand elle est terminée ;
Paramètres : durée d'exécution des tâches, nombre de tâches générées par intervalles ;

Pluie

Des tâches arrivent périodiquement dans le système ;
La RC est choisie aléatoirement ;
Paramètres : taux d'arrivée, durée d'exécution des tâches.

Grains de sable $\Leftrightarrow $ Tâches

Environnement de calcul

Résultats

Système "sous-chargé" $\rightarrow$ presque pas d'avalanches ;
Si $N_{\mbox{tâches}}(t) \geq N_{\mbox{RC}} \times k$ alors
le système est surchargé $\rightarrow$ avalanches en permanence ;
Quel est le comportement au milieu ?

Sans échelle

Loi de puissance

Sensibilité aux paramètres

Robuste aux changements des paramètres ? Partiellement >>:)

Stratégie d'équilibrage (voisinage, aléatoire) $\rightarrow$ ok !
Voisinage (Von Neuman/Moore) $\rightarrow$ ok !
Topologie (grille, tore, anneau) $\rightarrow$ ok !
Application (volcan, pluie) $\rightarrow$ ok !
Paramètre de charge (temps d'éxécution, nombre de tâches, taux d'arrivée) $\rightarrow$ non !

Charge critique $\approx$ 80% du nombre maximal de tâches.

Puisqu'il faut conclure

Perspectives

Utilité

Contexte : centre de calcul haute performance, réseau de capteurs autonomes, ....
Utilisation : efficacité, autonomie et économie d'énergie ;
Hypothèses : les RC ont une gestion d'énergie et peuvent se mettre en veille.

Question
Comment calibrer le centre de calcul, le réseau de capteur de façon décentralisée et économe ?

Perspectives

Éléments de réponse

Chaque tâche est estampillée par le nombre de saut durant sa migration ;
Chaque RC rencontrée enregistre l'estampille et effectue une analyse de la distribution de ces dernières ;

L'analyse est approximée par une formule du type : $$ \begin{eqnarray*} y &=& \frac{a}{x^{\alpha}} \\ \end{eqnarray*} $$ dont on cherche à déterminer $\alpha$.

Perspectives

Éléments de réponse

$\frac{a}{x^{\alpha}}$ : $\alpha$ décroit $\rightarrow$ surcharge éventuelle.

Perspectives

Réponse à une surcharge éventuelle

Si la RC est en périphérie du système, elle réveille des voisins.

Perspectives

Comment économiser des ressources

Une RC est en périphérie du système inactive depuis "longtemps" se met en veille.

Merci de votre attention

Bibliographie

[Bak-1996] P. Bak. Quand la nature s’organise ; avalanches, tremblements de terre et autres cataclysmes. Flamarion, 1999.
Trad. de "How Nature Works : The Science of Self-Organized Criticality". New York : Copernicus (1996).

[BTW-1987] P. Bak, C. Tang and K. Wiesenfeld. Self-organized criticality : an explanation of 1/ƒ noise. Physical Review Letters 59 (1987) 381-384.

[DUR-2003] J. Duran, Sables émouvants - La physique du sable au quotidien -. Belin - Pour la science, (2003).

[RAJ-2002] J. Rajchenbach. Development of grain avalanches. Phys. Rev. Lett., (2002), 89(7) :074301.

[HOF-2013]D. Hofstadter et E. Sander. L'analogie: cœur de la pensée. Odile Jacob, (2013)

[NAU-1982]D. Nau. An investigation of the causes of pathology in games. Artificial Intelligence, (1982), Volume 19. 257-278

[AND-2009]Y. André. Leçons de Mathématiques contemporaines à l IRCAM. (2009).

[LAR-2014]J.L. Laredo, P. Bouvry, F. Guinand, B. Dorronsoro, C. Fernandes. The sandpile scheduler The sandpile scheduler - How self-organized criticality may lead to dynamic load-balancing}. Cluster Computing, (2014), Volume 17(2), 191-204

Singularités plurielles