Introduction, état de l’art, incertitudes
Dans le cadre du projet Clariprint, nous travaillons sur des d’algorithmes complexes de recherche de solutions associant différentes techniques de calcul. L’algorithme général est de type « branch and bound » piloté par heuristique dynamique associé à des optimisations locales. L’ensemble est codé dans le langage CLAIRE issue de recherches sur la création de langage dédié a ce type d’algorithmes. Précédemment, nous avons travaillé sur la parallélisation en intégrant au langage un élément syntaxique (cf. ffor). Cependant, l’efficacité de la recherche dans un arbre dépend fortement des informations acquises lors de l’exploration, hors ce partage d’information est plus délicat dans une architecture distribuée. Nous avons étudié les possibilité d’amélioration des performances de calculs au travers d’un système de partage de connaissance inter-processus.
Partage d’objectif
Le premier élément d’apprentissage lors de l’exploration combinatoire est l’objectif de coût qui a été choisi comme borne à optimiser. Nous nous plaçons ici dans le cas ou il est possible de calculer lors de l’exploration soit un coût intermédiaire soit un intervalle. Ce coût peut être ainsi comparé au coût de la meilleur solution obtenue. Dès que le coût intermédiaire dépasse la cible, l’exploration est arrêtée pour la branche (« cut »).
Nous avons d’abord tenté de caractériser les domaines d’application, les données impliquées ainsi que l’efficacité intrinsèque du « cut » dans un cas classique.
Ensuite nous avons évalué les solutions techniques disponibles dans le partage d’information inter-processus, dans notre cadre d’application.
Nous avons enfin proposé une solution intégrée au langage CLAIRE.
Partage de résultats intermédiaires
Problématique
Les algorithmes de parcours d’arbre font généralement appel à des sous algorithmes de pilotage ou d’évaluation. Suivant les problèmes à résoudre, le temps d’exécution de ces algorithmes peut être non négligeable, alors qu’ils peuvent être appelés un grand nombre de fois lors de l’exploration.
Dans le cadre de Clariprint, nous avons mené des évaluations théoriques et pratiques de l’impact sur le temps de réponse d’un certain nombre de résolution de sous-problèmes.
Nous avons étudié quelles étaient les caractéristiques permettant d’envisager un processus d’apprentissage et déterminé ainsi les algorithmes éligibles. Notamment les structures d’entrée et de sortie et les temps d’exécution unitaires.
Recherches
Nous avons commencé par tester les outils et techniques proposés par la communauté. Nous avons été confronté à un problème de performance. Ces systèmes sont conçus pour des applications réseaux ou de base de donnée, ou les temps de réponses sont importants (plusieurs dizaines de ms).
Cette constatation nous a poussé à rechercher une solution spécifique. Nous avons ainsi poursuivi plusieurs pistes et élaboré des prototypes nous permettant de mieux cerner les éléments clés de la réussite.
Le premier élément a optimiser a été la structure des données partagées. Les prototypes ont mis en évidence l’aspect primordial en terme de temps d’un système de codage – décodage (codec) efficace. Nous avons ainsi testé des systèmes utilisant des structures standards (XML, JSON) comme des solutions spécifiques comme la sérialisation binaire. Cette dernière méthode s’est avérée considérablement plus performante, que ce soit en terme de temps de codec comme en mémoire utilisée.
Nous avons ensuite travaillé sur les différentes stratégies de communication des données. Nous avons pris parti de nous appuyer sur les solutions simples existantes et sélectionné une méthode largement utilisée : fichier partagé.
Suite à ces tests nous avons élaboré un nouveau prototype de CLAIRE nous permettant de créer des prototypes de Clariprint exploitant ces nouveaux outils.
Ce prototype a été confronté à des données industrielles, ce qui nous a permis de tester plusieurs scenarii d’implémentation, et d’analyser directement les gains apportés.
L’augmentation de performance est cependant très liée à la configuration du calcul. Nous avons ainsi mesuré des gains négligeables sur des configurations simples, ainsi que des gains substantiels (temps de réponse divisé par 2) sur des problèmes plus complexes. Hors ces derniers sont les plus gourmands en temps de réponse. Les problèmes plus complexes dont les arbres de recherches sont beaucoup plus larges ont plus de chance de retrouver des configurations identiques de sous-problèmes comme de profiter du partage de borne de recherche.
Cette amélioration a été testée chez notre principal client pendant 3 mois avant d’être mise en service.
Conclusion
Les gains espérés ont été en grande partie obtenus. Le système proposé a permis de valider le concept. Nous avons cependant plusieurs incertitudes concernant notamment le fonctionnement en réseau, les temps de latence et surtout une gestion entièrement automatique par CLAIRE. Ce dernier disposant d’un analyseur syntaxique il serait possible d’automatiquement détecter les fonctions candidates à un apprentissage.