FLASH INFORMATIQUE FI

Numéro spécial HPC


Simulation de chaînes de Markov pour la biophysique




Vittoria REZZONICO

Carlo MAFFI


Une classe d’algorithmes Monte Carlo pour la simulation des systèmes physiques est particulièrement adaptée à la parallélisation. L’algorithme gagne en efficacité de deux façons différentes : trivialement, par le fait de disposer de plusieurs processeurs qui travaillent en même temps, et, plus intéressant, par la possibilité d’échanger des messages entre les processus. L’article ci contre présente comment On montre comme cette dernière possibilité améliore la performance de l’algorithme. Notre étude est conduite sur des simulations des chemins auto-évitants (i.e. qui ne se croisent pas) avec interaction.

Étude des chemins auto-évitants pour la biophysique

La physique des grandes molécules biologiques, comme l’ADN ou les protéines, est déterminée a priori par des milliers d’interactions différentes parmi tous ses atomes composants. Une étude complète et détaillée est donc très difficile à poursuivre. Pourtant, on peut chercher à comprendre le comportement de ces complexes sur la base de modèles simples qui prennent en considération seulement quelques facteurs à la fois. Par exemple, une protéine en solution est une chaîne composée par beaucoup d’amino-acides, qui sont par eux-mêmes des molécules très complexes. On observe que pour des conditions spécifiques du solvant (la température par exemple) les protéines sont compactes, ce qui est le signe d’une attraction entre les monomères. En plus, le volume des monomères les empêche d’occuper le même point plusieurs fois. On peut construire un modèle qui garde ces deux aspects (attraction et volume exclus) : ceci peut être un chemin auto-évitant avec une énergie d’attraction entre ses monomères assez proches (voir fig. 1).

JPEG - 7.1 ko
fig. 1
Quelques chemins auto-évitants en 2 dimensions avec 0 ou 3 contacts (en bleu)


La physique associe à chaque configuration une probabilité de se présenter dépendante d’un paramètre, \beta, paramètre qui se révèle être l’inverse de la température. Cette probabilité est la loi de Boltzmann :

\rho_\beta = \frac{{e}^-\beta(-{n}_{contacts} )}{Z}, où \beta=1/T , Z donne la bonne normalisation de la probabilité et l’énergie E = -ncontacts (nombre de contacts) privilégie les chemins avec plus de contacts. Toutes les propriétés physiques sont calculées comme des valeurs moyennes sur l’ensemble des chemins pris avec la loi de probabilité montrée.
On souhaite donc estimer des valeurs moyennes de certaines grandeurs qui sont définies sur un ensemble très grand de configurations. Le nombre de chemins d’une longueur donnée peut être énorme. Il est donc impensable de faire le calcul sur tous les chemins. Des configurations sont donc engendrées au hasard et les moyennes cherchées sont calculées uniquement sur les données simulées. Une bonne façon d’engendrer une série des configurations distribuées selon une certaine loi de probabilité consiste à commencer par une configuration (chemin) initiale et la modifier pas par pas : cette méthode est dite Monte Carlo dynamique. On commence par un chemin droit. De ce chemin droit on va générer, par symétries ou rotations autour d’un point du chemin, un nouveau chemin (voir fig. 2).

JPEG - 5.7 ko
fig. 2
Création d’un nouveau chemin auto-évitant : on choisit un site au hasard, on bouge la partie en aval selon une symétrie du réseau, ici une rotation de 90 degrés. Au cas où la nouvelle configuration ne serait pas auto-évitante on la rejette et on revient à la précédente

Une fois cette nouvelle configuration construite, il faut s’assurer qu’elle ne se croise pas. Si elle se croise, on la rejette et on revient à la configuration précédente. Si le nouveau chemin ne s’autocroise pas, on l’accepte avec une probabilité p=min(1,e-$\beta\Delta(-ncontacts)) qui garantit que les chemins générés seront distribués selon la loi de Boltzmann désirée.
Il faudra générer des configurations sur un éventail de températures, c’est-à-dire avec différentes probabilités pβ.
Peut-on obtenir des améliorations en profitant de la capacité d’échanger des messages entre processeurs ?
On remarque que les simulations à basse température demandent plus de temps que celles à haute température. Cela pour deux raisons : les chemins à basse température sont normalement assez repliés sur eux-mêmes, et les modifications comme celles décrites plus haut donnent beaucoup des chemins qui seront rejetés, parce que non auto-évitants. De plus, même les bonnes configurations seront acceptées avec une probabilité petite à cause de la basse température T qui donnera une faible probabilité d’acceptation (voir p où β =1/T) ; en d’autres mots, il nous arrive de rester bloqués dans une petite région de l’espace des configurations, un minimum local qu’il est difficile de quitter. Ce problème est aussi connu sous le nom de quasi-ergodicité. La possibilité de visiter tout l’espace (ergodicité) est toujours garantie en principe, mais en pratique ça peut demander des temps très longs (quasi-ergodicité). Ceci est dû au fait que l’on crée toujours les nouvelles configurations à partir de la présente. Une solution à ce problème s’appelle Parallel Tempering (ou Multiple Markov Chain) [1]. De temps en temps la nouvelle configuration ne sera pas créée par modification de la présente, mais prise de la chaîne à la température plus proche, et l’échange est symétrique. La configuration déjà auto-évitante sera acceptée avec le même test (probabilité p) qui garantit la bonne distribution, généralisée au fait que l’échange a lieu entre deux températures dans les deux sens. Cet échange augmente la mobilité des chaînes de Markov : à chaque fois qu’un échange est accepté, la nouvelle configuration est complètement décorrélée de la présente, parce qu’elle n’en est pas une dérivation. Ceci permet des grands sauts dans l’espace des configurations.
Les processeurs communiquent et on arrive à un gain qui vient de la coopération, pas seulement du nombre des processeurs employés.
Le but de l’introduction des échanges entre les chaînes est d’obtenir plus de données indépendantes en faisant le même nombre de pas Monte Carlo. Donc pour évaluer l’efficacité de la méthode on compare le nombre des données indépendantes obtenues dans les cas sans et avec échanges. La figure 3 représente le rapport entre le nombre de données obtenu en faisant un échange chaque 48, 32, 16, 8 pas et le cas sans échange. La croissance de courbes montre que le nombre d’échanges augmente le nombre de données indépendantes, ce qui est la caractéristique principale de l’algorithme.

JPEG - 7.9 ko
fig. 3
Nombre des données obtenues et nombre d’échanges

Un deuxième aspect est la probabilité qu’un échange soit accepté : celle-ci dépend de la différence entre les températures qui échangent leur configuration : plus elles sont proches, plus l’échange a des chances d’être accepté, avec un effet direct sur le nombre des données indépendantes. La figure 4 représente l’efficacité de l’algorithme en variant le nombre de températures dans le même intervalle [0,1]. Aussi, avec un nombre plus grand de températures plus proches les unes des autres on obtient plus de données.

JPEG - 7.5 ko
fig. 4
efficacité et nombre de températures

Exploiter un grand nombre de processeurs ?

On a vu que d’une part notre algorithme pour une température donnée est facilement parallélisable. De plus, on peut diviser notre intervalle de températures et assigner une température à chaque groupe de processeurs. Chaque processeur calculera ses chemins et les valeurs associées indépendamment et le temps d’initialisation (subdivision de l’intervalle des températures) sera moindre. En rajoutant les échanges entre processeurs, on augmente le nombre de chemins acceptables et on résout le problème de quasi-ergodicité.
Nous remarquons que le nombre de processeurs utilisés dépend du nombre de températures que l’on veut considérer - si nous nécessitons de beaucoup de températures, nous avons besoin d’une machine avec beaucoup de processeurs. Dans notre cas, on pourrait penser avoir 128 températures et 8 processeurs par température, ce qui nécessiterait de 1024 processeurs à mémoire distribuée vue la nature des communications. Ceci nous ouvre les portes du massivement parallèle.
Nous n’avons pas mentionné les possibilités de parallélisation à l’intérieur de chaque chaîne de Markov : par exemple, on pourrait paralléliser la partie du code où on contrôle si le chemin est auto-évitant. Cette parallélisation est moins évidente, mais des essais fructueux ont était faits dans cette direction - cette partie du code a été parallélisée avec les POSIX threads et on a un bon speedup jusqu’à 8 processeurs. Nous avons donc deux niveaux de parallélisation dans le problème : le niveau le plus haut concernant les températures et le niveau le plus bas lors de la vérification des chemins.
Les deux parallélisations ont été testées indépendamment, mais à terme on pourrait penser à les combiner et avoir du MPI entre les noeuds et des Pthreads à l’intérieur du même noeud.
Les machines disponibles à l’EPFL se prêtent très bien à ce type de programmation : Callisto consiste en 128 noeuds, chacun ayant 8 cores partageant la même mémoire, et le nouveau Blue Gene a 4096 noeuds quadri-core. Affaire à suivre !

[1] Voir par exemple : Orlandini E., Monte carlo study of polymer systems by multiple markov chain method, in Numerical methods for polymeric systems edited by G. Whittington, IMA volumes in Mathematics and its applications, vol. 102 (1998), où le cas des chemins auto-evitant est directement traite.



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.