Veille et meilleures pratiques

Exploiter la puissance de calcul de l'infonuagique pour faire face à l'explosion combinatoire

Bond, S., Nantel, J.-P. Exploiter la puissance de calcul de l'infonuagique pour faire face à l'explosion combinatoire. Montréal, CRIM, 2012. 11 p.
[Texte complet]

Un exemple d’utilisation de serveurs Amazon EC2 (spot instances) et de centaines de serveurs privés pour du calcul distribué massif et extensible (scalable).
 

Mise en contexte

Le but du document est de présenter une architecture de calcul distribué que nous avons utilisée pour profiter des infrastructures serveurs disponibles dans l’infonuagique (« Cloud IaaS ») et de celles à notre disposition à l’interne. La grille de calcul construite a la particularité d’être extensible et d’exploiter des serveurs (agents de calculs) indépendamment du fournisseur infonuagique. Ces principes peuvent être réutilisés dans le cadre de différents besoins applicatifs.

Nous avons utilisé l’architecture pour diminuer drastiquement les temps de production de résultats avec Le Solutionneur [9], un logiciel de fabrication d’horaires destiné aux écoles secondaires québécoises. Avec 300 cœurs de processeurs chez Amazon (AWS EC2 [2]) et 300 cœurs disponibles à l’interne, le système a permis de multiplier la puissance de calcul par un facteur 30 pour chacun des utilisateurs.

La première partie du document présentera notre problématique avec ses besoins en puissance de calcul, pour ensuite présenter l’architecture de la grille de calcul.
 

1. Description du problème à résourdre

1.1 La complexité de la confection d'un horaire d'école

L’optimisation combinatoire a comme principal but de trouver des solutions intéressantes, voire optimales, à des problèmes ayant un nombre fini de solutions. La difficulté de tels problèmes provient du fait qu’il est souvent impossible en pratique d’énumérer les solutions en raison de leur nombre excessivement élevé. Un exemple notoire d’un tel problème est celui du voyageur de commerce [12]. En effet, le nombre de solutions possibles (10e99) dépasse largement le nombre d’a tomes de l’univers (10e80) pour un problème avec seulement 70 villes.

Le problème à résoudre dans le cas présent est la construction d’horaires maîtres pour les écoles secondaires québécoises. Dans ce dernier, on cherche à assigner un groupe pour chacune des matières au choix de cours de l’élève tout en assignant à chaque groupe un temps de rencontre, un enseignant et un local. Le nombre d’élèves par groupe est limité, mais peut être augmenté en payant une pénalité (un dépassement). C’est donc un problème d’optimisation dans lequel on cherche à maximiser le nombre d’élèves ayant un horaire tout en minimisant les pénalités. Malheureusement, ce problème est presque toujours non réalisable. En effet, le nombre élevé de contraintes et leur nature (conventions collectives, lois, préférences individuelles, règles administratives, etc.) crée souvent des problèmes impossible à résoudre. On cherche donc, en plus des objectifs précédents, à maximiser le nombre de contraintes satisfaites. Plus précisément, on aura des contraintes dites faibles que l’on peut satisfaire ou non (un enseignant est assigné toujours au même local) et d’autres dites fortes que l’on ne peut violer (un élève ne peut assister à plus d’un cours en même temps). Une solution optimale respectera les contraintes fortes tout en respectant un maximum de contraintes faibles. Ce problème, à l’instar du problème du voyageur de commerce, possède un très grand nombre de solutions et à ce jour, pour une instance de taille réelle, aucun algorithme connu ne permet de résoudre ce problème de manière exacte [a].
 

1.2 Méthode de résolution

Étant donné la situation, on peut tout de même trouver des solutions de très bonne qualité. Nous n’avons simplement pas de preuve qu’il s’agisse de la meilleure. Pour trouver de telles solutions, on a recours à des approches approximatives comme les métaheuristiques [10]. Plus précisément, on utilise la recherche à grand voisinage (Large Neighborhood Search) pour diriger la recherche locale. Cette recherche locale est faite selon les circonstances par programmation par contraintes, par descente, par programmation linéaire en nombres entiers ou encore par recuit simulé.

Bien que les métaheuristiques ne soient pas en mesure de nous fournir de garantie au sujet de la qualité d’une solution trouvée, elles ont quand même quelques avantages de taille. Premièrement, ces méthodes produisent de très bons résultats en pratique. Ensuite, mentionnons que le problème de construction de l’horaire d’une école secondaire a une forte composante multicritère. Les critères sont contradictoires et leur importance relative varie beaucoup d’une école à l’autre. Par exemple, la qualité de l’horaire des enseignants (un seul local, répartition de la charge d’enseignement) augmente souvent au détriment de la qualité de l’horaire des élèves (chaque élève a un horaire sans modifier son choix de cours). Puisque les métaheuristiques utilisées sont des approches ayant une certaine composante aléatoire, on n’obtient pratiquement jamais deux fois la même solution pour un même problème. Étant donné que l’on optimise plusieurs aspects dans une solution, la qualité des solutions selon un critère donné, comme la répartition de la charge de travail d’un enseignant, variera beaucoup. On se retrouve donc avec plusieurs solutions ayant des contraintes non satisfaites différentes et il revient à l’utilisateur de choisir lesquelles sont les moins importantes.
 
1.2.1 Augmentation de la puissance de calcul
La construction d’un horaire pour une polyvalente de taille moyenne demande un effort de calcul important pouvant nécessiter de 20 à 60 minutes par solution. L’application est conçue pour ne prendre qu’un seul fil d’exécution pour le calcul.

Les utilisateurs peuvent faire beaucoup de tests au début du processus en ajoutant ou retirant des contraintes de manière à obtenir les solutions les mieux adaptées à leurs besoins. Après les tests, une pratique courante est de choisir une solution finale parmi une cinquantaine. 

On peut donc estimer grossièrement l’effort de calcul à une centaine d’heures pour chaque école. Plus les utilisateurs ont accès à une grande puissance de calcul, plus la fabrication d’horaires est rapide et meilleures sont les solutions.
 

2. Architecture de la grille de calcul

La période de confection des horaires d’écoles secondaires se déroule essentiellement au mois d’a oût, soit pendant la période de vacances des étudiants. Les commissions scolaires ont donc un parc informatique largement sous-utilisé pendant cette période. De plus, pour les pointes d’utilisation, on peut aussi avoir recours à des ressources infonuagiques comme les instances ponctuelles (spot instances) [6] d’Amazon EC2. L’élaboration d’une architecture de grille d’agents de calcul hétérogènes était la solution pour exploiter pleinement autant de puissance de calcul inutilisée.

On retrouve essentiellement trois types d’éléments dans l’architecture de la grille :
  • Client : poste de travail d’un utilisateur.
  • Agent : machine exécutant des calculs pour le compte d’un client.
  • Serveur : machine utilisée pour la communication entre les agents et les clients.
La figure 1 présente l’architecture initialement déployée (les deux nœuds représentant Internet ne sont dupliqués que pour simplifier le schéma). On y voit donc le serveur au centre avec sa base de données auquel se connectent l’ensemble des clients et agents.

Figure 1 Architecture initiale
 

2.1 Architecture du client

Le logiciel Le Solutionneur est une application de bureau déployée sous forme de client intelligent (Smart Client [15]) à l’aide de Java Network Launching Protocol [7]. Le déploiement en client intelligent permet le contrôle des versions et mises à jour, tout en ayant accès aux ressources locales.

L’utilisateur peut éditer les contraintes et les données à l’aide de l’interface graphique fournie. Il choisit aussi les paramètres de résolution et il peut ensuite lancer la recherche de solutions et attendre que ces dernières apparaissent dans une liste. Ainsi, on définit un travail comme un problème à résoudre (données et contraintes) avec les paramètres de résolution. Avant l’u tilisation de la grille de calcul, cette recherche ne se faisait que sur la machine de l’u tilisateur, alors que le client envoie maintenant son travail au serveur.
 

2.2 Architecture de l'agent de calcul

On définit une tâche comme la recherche d'une seule solution à un travail envoyé par un client. Ainsi, l'unique but de l'agent est d'exécuter des tâches. L'agent de calcul est dérivé du client et est donc lui aussi un client intelligent. Par contre, il est conçu comme un service ayant pour effet de s'exécuter en arrière-plan au démarrage du système d'exploitation. La librairie SIGAR [5] est utilisée pour détecter les caractéristiques de la machine (processeur et mémoire vive). L'agent envoie donc ses caractéristiques et s'enregistre auprès du serveur. Tant que l'agent aura des ressources (cœur libre et suffisamment de mémoire vive), il demandera au serveur de lui envoyer une tâche et il fera de même lorsqu'une de ses tâches se complète.

Chaque tâche s’exécute dans un processus isolé ayant ses propres librairies. Il s’agit en fait d'une nouvelle machine virtuelle Java dans laquelle s’exécutent les algorithmes sans interface utilisateur. Cette manière de faire permet à l'agent d'exécuter en parallèle des versions différentes de l'application et le rend moins vulnérable aux erreurs dans l'exécution de la tâche. Le processus envoie au serveur le résultat de la simulation à la fin du processus et se ferme pour permettre à une autre tâche d’être exécutée.
 

2.3 Architecture du serveur

Étant donné qu’un grand nombre de machines de la grille sont derrière des pare-feux très restrictifs, l’utilisation d’une architecture centrée sur un serveur Web s’est imposée. Le serveur est donc le point central du réseau et il est supporté par une base de données MySQL pour conserver les informations concernant les travaux, les tâches et les agents. On a donc un moyen de savoir à tout moment, le nombre de tâches exécutées par chaque agent et le nombre de tâches associées à un travail. Le serveur expose des services Web pour répondre aux requêtes des clients et agents. Une architecture simple a été initialement déployée, puis a été améliorée pour répondre à la demande.
 
2.3.1 Ordonnancement des travaux
C'est donc du côté du serveur que s'effectue l'ordonnancement des tâches et la distribution du calcul. Le but de l'ordonnancement est de répartir de manière équitable les travaux à exécuter à l'ensemble des agents. Un modèle simple consiste à diviser le nombre de ressources disponibles d'après le nombre de travaux à effectuer. Cette méthode s'inspire du « round-robin scheduling » [11], à la différence que l'on divise la ressource elle-même plutôt que son temps d'utilisation. On ajuste le nombre de tâches selon l'ajout ou le retrait d'agents ou de travaux. Cette manière de procéder a cependant quelques défauts.

En effet, lorsque le nombre d'agents est élevé et que le nombre de travaux est faible, l'ajout d'un travail engendre des fluctuations importantes dans le nombre de tâches à exécuter (par exemple 600 agents; 1 travail : 600 tâches; 2 travaux 300 tâches). On doit donc indiquer à un grand nombre d'agents de cesser la résolution d'une tâche et leur en assigner une autre. On peut corriger le problème simplement en définissant un nombre maximal absolu de tâches associées à un seul travail de manière à limiter les fluctuations.

Un autre inconvénient est qu'il est impossible de prioriser certains travaux plus urgents. On peut pallier ce manque en introduisant un système de poids pour les travaux et en répartissant les tâches en fonction du nombre pondéré de travaux plutôt qu'en fonction du nombre de travaux.
 
2.3.2 Distribution, réception et stockage des fichiers
Comme il a été mentionné dans les sections précédentes, c'est le serveur qui est responsable de recevoir les fichiers du problème du client et de lui renvoyer les résultats. C'est aussi lui qui doit envoyer le fichier de problème à un agent et récupérer ses résultats. Le serveur est donc très sollicité par ces tâches et il faut minimiser la taille des fichiers au maximum. Le fichier de données du problème est donc épuré (retrait des champs inutiles à la résolution comme le nom des élèves) et le fichier de résultat ne contient que l'essentiel, quitte à recalculer certaines métriques. Ces fichiers sont ensuite compressés avant d'être envoyés. Bien que les données soient rendues anonymes avant d'être transmises par le client, il faut tout de même prendre soin de les protéger lors des échanges avec le serveur. La manière la plus simple pour mettre en place une connexion sécuritaire est d'utiliser TLS [13]. On obtient ainsi une connexion sécuritaire robuste transparente, puisque le support du protocole est intégré dans Java.
 
2.3.3 Console de gestion
Une console de gestion développée avec le cadre applicatif (Framework) vaadin [14] permet de consulter l'état de la grille de calcul. Vaadin utilise Google Web Toolkit (GWT) [4] pour faire le rendu des pages et comporte une architecture complète côté serveur, ce qui fait en sorte que la logique s'exécute surtout du côté du serveur, contrairement à GWT seulement. L'utilisation de ce cadre applicatif a permis de construire l'application rapidement avec une technologie similaire à celle utilisée pour le client (Swing [8]), tout en se dotant d'une application Web dynamique grâce à l'utilisation de requêtes Ajax.

La console de gestion présente deux perspectives, soit celle par agent et celle par client. Dans la perspective par agent, on voit l'ensemble des agents, leurs caractéristiques et les tâches exécutées par chacun. Dans la perspective par client, on peut voir les travaux lancés par chaque utilisateur du système et les tâches concernant ce travail qui sont actuellement exécutées avec leur résultat. On peut donc modifier l'importance relative d'un travail, retirer des travaux ou libérer des agents avec cette console. 
 

3. Montée en charge et améliorations

Le système a été mis en ligne pendant le mois d'août 2012, qui est le mois le plus occupé pour la confection des horaires. Certaines écoles et commissions scolaires ont mis à la disposition une partie de leur parc informatique pour produire la moitié de la puissance de la grille. Le reste des machines ont été des instances ponctuelles d'Amazon EC2. Il s'agit d'instances flottantes non utilisées qu'Amazon fournit à des tarifs avantageux (basé sur un système d'enchères). Lors de la requête d'un bloc d'instances ponctuelles, on peut spécifier un script à exécuter sur chaque machine au démarrage. Dans le cas présent il s'agissait d'un script d'installation de la base de l'application. Étant donné que l'agent gère ensuite lui-même le téléchargement d'autres librairies et l'exécution de tâches sans intervention humaine, le déploiement des instances ponctuelles se fait très facilement. Cette manière de procéder simple, mais astucieuse, permet aux gestionnaires du système de maintenir une puissance de calcul adéquate selon la demande avec un minimum d'intervention.

La figure 2 présente graphiquement l'architecture déployée pour répondre à la demande lors du projet pilote. La description de cette architecture est faite dans la suite du texte.

Fugure 2 Architecture déployée

Cependant, le déploiement simultané d'une très grande quantité d'agents a fait ressortir des problèmes importants qui ont forcé la modification de l'architecture. En effet, lors du démarrage d'un agent, ce dernier télécharge un environnement d'exécution Java ainsi que les librairies nécessaires qu'il conserve en cache pour éviter de les télécharger à nouveau. Le téléchargement de la distribution initiale à partir d'un serveur externe à Amazon peut prendre quelques minutes en plus de consommer des ressources et de la bande passante sur le serveur Web. Heureusement, on peut facilement pallier ce problème en utilisant Amazon S3 [3] pour héberger ces fichiers. On profite ainsi de la robustesse de l'infrastructure d'Amazon et du lien rapide à l'intérieur de leur propre réseau. Cette mesure de mitigation s'est avérée efficace pour pallier le problème de déploiement initial, mais le serveur du CRIM est tout de même fortement sollicité lors du démarrage d'un grand nombre de travaux.

Par ailleurs, l'ajout d'un mécanisme de répartition de charge s'est avéré nécessaire pour augmenter la robustesse du système. La première itération a donc consisté à faire une répartition statique de la charge. Ainsi, un deuxième serveur a été ajouté pour répondre uniquement aux agents, alors que le premier a été délesté de cette charge pour se consacrer aux clients. Les deux serveurs utilisent la même base de données et ont accès à un même serveur de fichier. Aucune adaptation n'a été nécessaire pour le stockage, puisque le serveur de fichier déjà utilisé est capable d'accommoder un nombre considérable de clients et d'agents avec une politique convenable sur la durée de vie des fichiers. En définitive, le système a été modifié pour permettre aux clients et agents de se connecter à l'un ou l'autre des serveurs en cas de défaillance de l'un d'eux. Cette mesure permet d'augmenter davantage la fiabilité du système et requière très peu d'adaptation.

Finalement, l'utilisation de la base de données a dû être revue pour l'ordonnancement des travaux, cette dernière étant à son tour surchargée. En effet, celle-ci doit être interrogée chaque fois qu'un agent est disponible pour connaître le portrait global des travaux en cours. La requête pour connaître quel travail toujours actif n'a pas suffisamment de tâches en traitement est relativement coûteuse, puisqu'elle fait appel à des fonctions d'agrégations. De plus, la performance décroît à mesure que l'on ajoute de nouveaux travaux et de nouvelles tâches. Ainsi, la solution la plus simple est de conserver l'information sur les travaux et tâches actifs en cache pour minimiser les accès à la base de données. En ne conservant que les informations sur ce qui est actif, on minimise la quantité de mémoire nécessaire pour la cache. Cette mesure de mitigation a permis au serveur de base de données de bien répondre lors du projet pilote.
 

Résultats, perspectives futures et conclusion

Le projet de calcul distribué pour Le Solutionneur s'est avéré un franc succès en permettant de déployer une grille de calcul de 600 cœurs de processeurs. Cette grille a permis de produire 30 000 solutions pour une vingtaine d'utilisateurs, soit environ 1 500 par utilisateur. Un tel nombre de solutions représente normalement deux mois de calcul ininterrompu, alors que la grille a permis de réduire ce temps à environ 2 jours. La capacité de calcul est donc en moyenne multipliée par trente, ce qui permet de réduire considérablement le temps nécessaire à la production d'un horaire maître et permet d'accroître le nombre de solutions finales obtenues de très bonne qualité. Les utilisateurs ont grandement apprécié la fonctionnalité qui permet de pallier aux imprévus (facteur humains) en rendant possible la génération d'un horaire en quelques jours.

La disponibilité d'autant de puissance de calcul ouvre d'abord la porte à l'expérimentation de nouvelles stratégies de résolution, comme des métaheuristiques opérant sur une population asynchrone et délocalisée. Aussi, l'accessibilité à toute cette puissance de calcul produit une grande quantité de données. On peut donc entrevoir des moyens d'extraire de l'information de ces données pour injecter de l'intelligence dans les méthodes de résolution. On peut donc combiner des solutions à un même problème ou détecter des phénomènes à plus grande échelle en apprenant de toutes les solutions, toujours dans le but de profiter plus efficacement de la puissance de calcul. Avec l'émergence de l'infonuagique, l'accès à autant de ressources matérielles se démocratise et devient réalisable à faible coût. Il est à prévoir que la demande pour des architectures de calcul distribué subira une augmentation considérable à moyen terme. Le projet de calcul distribué offre donc un énorme potentiel pour la recherche appliquée.

L'architecture proposée permet un déploiement à grande échelle pour les parties client et agent. Cependant, la partie serveur devra être adaptée s'il faut supporter davantage de clients et agents. Une solution serait d'utiliser des services extensibles (scalable) proposés par Amazon Web Services, Google Cloud ou Microsoft Azure. Ces plateformes infonuagiques proposent en effet des solutions adaptées à nos besoins.
 

Références

[a] Le problème de construction d’un horaire d’école secondaire québécoise est une variante du problème de construction d’horaire universitaire (University Timetabling). Or, ce dernier a été démontré comme étant NP-Dur (Cooper et Kingston, 1996) [1], c’est-à-dire qu’on ne dispose pas d’a lgorithme dont le temps de calcul n’explose pas lorsque la taille du problème augmente. La variante québécoise ajoute l’étape du placement des élèves dans les groupes, ce qui rend le problème encore plus complexe. On suppose donc que le problème est aussi NP-Dur sans en faire la démonstration formelle.

Actes de conférences, colloques, ateliers
[1] Cooper, Tim B, Kingston, Jeffrey H. «The complexity of timetable construction problems. » dans The Practice and Theory of Automated Timetabling, pp 283-295, Springer Lecture Notes in Computer Science 1153, (1996).

Références électroniques
[2] Amazon Elastic Compute Cloud (http://aws.amazon.com/fr/ec2/)
[3] Amazon Simple Storage Service (https://aws.amazon.com/fr/s3/)
[4] Google Web Toolkit (https://developers.google.com/web-toolkit/)
[5] Hyperic SIGAR API (http://www.hyperic.com/products/sigar)
[6] Instances ponctuelles Amazon EC2 (http://aws.amazon.com/fr/ec2/spot-instances/)
[7] Java Network Launching Protocol (http://jcp.org/aboutJava/communityprocess/final/jsr056/index.html)
[8] Java Swing (http://docs.oracle.com/javase/7/docs/technotes/guides/swing/index.html)
[9] Le Solutionneur (https://www.crim.ca/solutionneur/bin/view/Main/)
[10] Metaheuristics Network Project Summary (http://www.metaheuristics.net/index.php?main=1)
[11] Process Scheduling (http://oreilly.com/catalog/linuxkernel/chapter/ch10.html)
[12] The Traveling Salesman Problem (http://www.tsp.gatech.edu/)
[13] Transport Layer Security Protocol (http://www.ietf.org/rfc/rfc2246.txt)
[14] Vaadin (https://vaadin.com/home)
[15] What is a Smart Client anyway? (http://blogs.msdn.com/b/dphill/archive/2004/02/02/66300.aspx)