Nous avons montré dans les premiers chapitres de cette thèse que le Cloud Computing est une offre protéiforme qui répond à un besoin grandissant du monde économique en ressources informatiques, qu'elles soient logicielles ou matérielles. Durant nos trois années de thèse, nous nous sommes appliqués à bâtir des projets logiciels sur l'environnement matériel fournit par une plateforme PaaS spécifique, celle d'Azure. A la lumière de ces projets, nous nous proposons maintenant de donner notre vision d'Azure en tant que plateforme de calcul, puis de rappeler nos conclusions présentées dans les chapitres \ref{chap:KMeans}, \ref{chap:practicalDALVQ} et \ref{chap:cloudDALVQ} quant à la parallélisation d'algorithmes de clustering.\\

%Cette conclusion présente notre point de vue à la fois sur le cloud comme plateforme de calcul intensif mais aussi sur la parallélisation des algorithmes de clustering sur lesquels nous nous sommes penchés. Dans une première partie, nous proposons quelques observations à propos d'Azure. Issues directement de notre expérience sur cette plateforme pendant nos trois années de thèse, ces conclusions ne portent ni sur les offres IaaS, ni sur les offres SaaS, ni sur les offres des petits fournisseurs de Cloud Computing. Par ailleurs, ces conclusions ne concernent Azure qu'en tant que plateforme de calcul intensif, rôle qui ne représente qu'une partie de sa cible commerciale. Enfin, elles ne sont le reflet que du comportement d'Azure sur la période qui s'étend de 2009 à 2011. Dans une seconde partie, nous revenons sur les conclusions tirées des modèles de clustering présentés dans les chapitres \ref{chap:KMeans}, \ref{chap:practicalDALVQ} et \ref{chap:cloudDALVQ}. \\

\section{De l'utilisation du PaaS comme plateforme de calcul intensif}

\subsection{Constat technique}

Le premier constat que nous pouvons porter sur Azure est celui d'une plateforme qui tient ses promesses en termes de garantie de performance, au moins jusque 200 machines. En effet, les résultats que nous obtenons sont comparables aux valeurs nominales présentées par Microsoft sur le site AzureScope, site aujourd'hui supprimé. Ainsi, nous avons bien retrouvé des cadences de CPU que nous nous attendions à obtenir par rapport à la taille des VM que nous avions louées, et les performances du BlobStorage que nous avons observées concordent également avec celles qui étaient déclarées par Microsoft. Enfin, la contrainte sur la bande passante agrégée est bien d'environ 850 Méga-octets, comme déclaré par Microsoft.\\

Cependant, ces performances sont loin d'égaler celles que nous pourrions obtenir avec un nombre équivalent de CPU ou de GPU sur un cluster de machines en local. Toutes choses égales par ailleurs, le cloud semble peu efficace dans le sens où il ne tire pas un profit optimal des ressources matérielles sous-jacentes: la virtualisation\footnote{Que ce soit via la machine virtuelle .NET ou la virtualisation de l'OS hébergée sur le cloud}, les communications moins efficaces que dans un réseau local, et le manque actuel de contrôle dans la fabrique d'Azure sur la topologie des machines qui nous sont allouées apportent des limites physiques sur la quantité de calcul que nous pouvons effectuer sur cette plateforme, à nombre de machines fixé. Ce constat est particulièrement vérifié quand le nombre de processeurs impliqués est faible: lorsque nous souhaitons implémenter un algorithme sur 16 unités de calcul, il est bien plus simple et performant d'utiliser une seule machine pourvue de 16 coeurs, dont le coût est très accessible. Lorsque nous augmentons le nombre de processeurs que nous souhaitons utiliser, les solutions disponibles se raréfient, et le cloud devient alors d'autant plus compétitif. Nous pouvons donc raisonnablement prendre le pari que les cas d'applications du Cloud Computing comme plateforme de calcul intensif impliqueront des projets nécessitant au moins plusieurs dizaines d'unités de calcul.\\

Un autre aspect intéressant des limitations actuelles d'Azure réside dans le manque d'environnement logiciel adaptés, qu'ils aient trait à l'exécution générale ou à la communication. Le PaaS est réputé plus simple d'utilisation que le IaaS en raison des primitives supplémentaires qu'il propose. En effet, les ``briques élémentaires'' du PaaS sont de plus haut niveau que celles proposées dans les solutions IaaS. Cependant les solutions IaaS proposent aujourd'hui des implémentations éprouvées d'environnement logiciel comme MapReduce ou MPI. Ces environnements, qui simplifient encore bien plus la tâche de développement que les primitives de plus haut niveau fournies par le PaaS, sont encore en cours de développement pour les solutions PaaS. Ainsi, plusieurs projets d'implémentation de MapReduce pour Azure ont été proposés, notamment celui de Microsoft Research ---appelé projet Daytona--- dont la première version a été mise à disposition du public en juillet 2011. Ce projet, qui est à l'heure où nous écrivons ces lignes la version la plus aboutie des implémentations de MapReduce sur Azure, est encore à l'état de prototype et n'a pas été intégré à l'offre commerciale d'Azure. Paradoxalement, c'est donc les solutions IaaS qui semblent fournir à l'heure actuelle les solutions les plus simples pour effectuer des calculs intensifs. \\

%Un autre aspect intéressant des limitations actuelles d'Azure réside dans le manque de framework d'exécution en général, de communication en particulier. Le PaaS est réputé plus simple d'utilisation que le IaaS en raison des primitives supplémentaires qu'il propose. En effet,  En réalité, même si par défaut les primitives du PaaS sont effectivement de plus haut niveau que celles proposées dans les solutions IaaS, ces dernières proposent aujourd'hui ---à la différence d'Azure--- de s'appuyer sur des frameworks plus "haut-niveau" comme MapReduce ou MPI, ce que ne proposent pas encore les solutions PaaS comme Azure.\\

Nous identifions cependant quatre cas d'utilisation (qui ne s'excluent pas mutuellement) dans lesquels le Cloud Computing est déjà compétitif techniquement pour réaliser des calculs intensifs. Le premier de ces quatre cas a trait à un besoin en calcul volatile: puisqu'Azure est à la fois élastisque et agnostique à la charge en calcul, le nombre de machines disponibles peut être sous quelques minutes redimensionné pour s'adapter à un pic de demande, ou réciproquement une baisse temporaire de celle-ci. Un second cas d'utilisation d'Azure est incarné par les tâches de calcul requérant plusieurs centaines de machines; dans ce cas, moins de solutions sont facilement accessibles, et Azure devient donc par contraste plus compétitif. Une troisième catégorie de tâches sont celles ne requérant pas des communications importantes ou des latences faibles entre les machines, deux des points faibles d'Azure par rapport à un cluster local de machine. Enfin, et c'est à nos yeux une catégorie très importante de tâches, de nombreux calculs intensifs sont réalisés dans un contexte de production, c'est à dire dans un cadre où la robustesse est primordiale. Azure fournit un environnement de calcul dans lequel le remplacement d'une machine morte est réalisé automatiquement dans un délai très bref, et dans lequel la perte d'une telle machine affecte peu le temps total d'exécution d'une tâche de calcul.\\

Les quatres contextes qui viennent d'être évoqués sont parfois tous réunis. C'est le cas par exemple pour le coeur technologique de Lokad, la société dans laquelle j'ai réalisé cette thèse. En effet, ce coeur technologique fournit une API qui permet d'exécuter des prévisions sur un ensemble de séries temporelles. Dans ce contexte, les garanties de robustesse et d'élasticité du cloud sont primordiales. Par ailleurs, une partie importante des calculs présentant un cas de parallélisme sur les données (dit de "data-level parallelism"), ces tâches de prévision demandent peu de communication entre les différentes unités de calcul. Enfin, les volumes de données, ainsi que la complexité algorithmique de ce coeur technologique requièrent d'allouer chaque jour plusieurs fois entre 100 et 200 machines, mais ce coeur technologique n'est pas utilisé une majorité du temps, et utilise donc dans ces circonstances une seule VM (c'est à dire le minimum). Pour Lokad, Azure est donc une excellente solution technologique à ses besoins de performance, de robustesse et d'élasticité.\\

\subsection{Constat économique}

Au-delà des divers éléments techniques qui viennent d'être présentés, nous sommes convaincus que l'adoption du cloud en général et du PaaS en particulier se joueront probablement plus sur des considérations économiques et stratégiques que techniques. A ce titre, trois éléments doivent être pris en compte: le coût de développement de l'application d'une part (c'est à dire le coût du software), et le coût du hardware d'autre part (achat amorti ou location, consommation énergétique, administration, entrepôt, etc.).\\

En ce qui concerne le développement d'applications très intensives en calcul, Azure n'est pas encore compétitif en raison du manque actuel d'environnement logiciel disponible. Nous avons déjà constaté que ce manque fait d'Azure une plateforme sur laquelle le développement de ces applications est rendu long et délicat. Ce coût de développement peut aujourd'hui se révéler trop important, puisque le coût horaire d'un ingénieur compétent peut représenter l'équivalent du coût horaire d'un millier de machines sur des plateformes comme Azure ou Amazon. Microsoft a cependant annoncé qu'une implémentation commerciale de MapReduce pour Azure est en cours de développement. Alors qu'une première version d'une adaptation de Dryad sur Azure a été développée et lancée, Microsoft a abandonné le projet pour se concentrer sur une implémentation officielle de MapReduce sur Azure, plus simple à manipuler et donc plus accessible pour ses clients que Dryad. \\

L'estimation du coût moyen d'usage du matériel physique ne fait quant à elle pas l'objet d'un consensus. En effet, certaines incertitudes demeurent sur les tarifs à long terme que proposeront Amazon ou Azure. En effet, ces tarifs ont été maintes fois diminués au cours des dernières années (ainsi certains des prix d'Amazon ont fait l'objet de 19 réductions successives sous différentes formes depuis 6 ans), et devraient probablement encore l'être à l'avenir.\\

Au delà de ces incertitudes à la fois sur les coûts de développement et sur les coûts d'utilisation, Azure peut-il se révéler une solution économiquement compétitive pour réaliser du calcul intensif ? En d'autres termes sera-t-il plus rentable d'utiliser une plateforme cloud comme Azure par rapport à un cluster local de machines, des GPU ou du matériel reprogrammable comme des Field-Programmable Gate Array (FPGA) ? En ce qui concerne les FPGA, leur marché est en sensible croissance, mais l'utilisation de ce type de solutions entraine souvent des coûts de développement qui rendent leur utilisation si ce n'est situationnelle, du moins peu adaptée dans de nombreux cas. Puisque de récentes offres de cloud (comme celles d'Amazon) proposent maintenant des GPU, la vraie question de la compétitivité économique du cloud est donc celle de la performance relative du cloud vis-à-vis d'un cluster local de machines, contenant des CPU et/ou des GPU. Sur ce dernier point, l'analogie entre Cloud Computing et Assurance peut apporter des éléments de réponse. De la même manière que les mécanismes d'assurance fournissent une mutualisation des risques pour lisser en espérance les coûts liés à des accidents, les mécanismes de cloud fournissent une mutualisation des ressources pour lisser dans le temps les besoins en consommation de multiples clients, et ainsi transformer l'I.T. en un bien de production courant comme l'électricité. De nombreuses organisations n'ont pas la taille critique au delà de laquelle les besoins internes sont suffisants pour que la mutualisation s'opère sans recourir à une organisation extérieure. Gageons alors qu'au moins pour ces organisations, les solutions cloud sont ou pourront être pertinentes.\\

\section{Implémentation d'algorithmes de clustering réparti}

\subsection{Cloud Batch K-Means}

Le problème de la parallélisation du Batch K-Means est un problème bien maitrisé dans le cas d'architectures Symmetric Multi-Processors (SMP) ou Distributed Memory Multi-processors (DMM), à tel point qu'il fait parfois figure de cas d'école pour le développement d'algorithmes de machine-learning parallèle. En effet, son schéma de parallélisation est évident et son efficacité est excellente à condition que les coûts de communication soient faibles. Sur des architectures SMP ou sur des architectures DMM pourvues de MPI, ces coûts sont effectivement très faibles. À l'inverse, les coûts de communication sur Azure rendent cette parallélisation moins efficace. Même si nous avons obtenu des accélérations de convergence qui avaient été atteintes précédemment dans peu de travaux académiques\footnote{avec certaines exécutions $58$ fois plus rapides que leur pendant séquentiel exécuté sur une machine avec la même puissance mais une RAM infinie}, nous avons aussi montré que l'utilisation des ressources était peu efficace.\\

Plus précisément, le synchronisme de l'algorithme du Batch K-Means réparti met en lumière deux phénomènes bien connus en calcul réparti, mais qui semblaient peu illustrés du côté de la communauté machine-learning. Le premier de ces phénomènes est l'aspect crucial que peuvent revêtir des ralentissements non-anticipés sur certaines machines, un phénomène dit de ``stragglers''. L'aspect synchrone de l'algorithme du Batch K-Means réparti implique en effet que le comportement général de l'algorithme est déduit non pas du comportement moyen des machines mais du comportement de la ``pire'' de celles-ci.\\

Le second phénomène est celui de l'importance des débits dans les communications. Puisque le synchronisme ne permet pas dans le cas du Batch K-Means de recouvrir les temps de communication et de calcul, les coûts de communication doivent être ajoutés à ceux des coûts de calcul. En l'absence d'un environnement logiciel efficace pour prendre en charge ces communications, nous avons utilisé le stockage d'Azure pour servir de moyen de communication entre les machines. Dans ce contexte, les coûts de communication ne peuvent plus être négligés. Nous pouvons montrer qu'un mécanisme d'aggrégation des résultats des $M$ différentes unités de calcul en $p$ étapes conduit à un coût de communication en $O(p\sqrt[1/p]{M})$. Cependant, les latences internes à Azure et les fréquences de ping des queues empêchent de concevoir des mécanismes efficaces d'aggrégation en $p=log(M)$ étapes comme c'est le cas dans MPI. Nous avons analysé le modèle correspondant au mécanisme d'aggrégation en deux étapes que nous avons retenu pour notre implémentation. Ce modèle de coût permet notamment d'anticiper l'ordre de grandeur du nombre optimal de machines à utiliser pour minimiser le temps d'exécution de notre Batch K-Means réparti sur Azure.

\subsection{Cloud DAVQ}

Les ralentissements non-anticipés (les ``stragglers'') et les coûts de communication qui viennent d'être rappelés nous ont donc incités à orienter nos travaux vers des algorithmes asynchrones de clustering. Pour le Batch K-Means, c'est le caractère ``Batch'' de l'algorithme qui entraine le synchronisme: l'étape de recalcul des prototypes nécessite que les communications soient réalisées exactement une fois par itération. Le passage vers un algorithme ``en-ligne'' ---l'algorithme de Vector Quantization (VQ)--- permet donc de supprimer ce point de synchronisation évidente.\\

La parallélisation de l'algorithme de VQ sur le cloud présente deux difficultés majeures : la non-convexité de la fonction de perte et la latence des écritures d'un objet (dans notre cas situé dans le BlobStorage). À notre connaissance, de nombreux travaux ont été proposés pour répondre à la problématique de descente de gradient parallèle en présence d'une de ces difficultés mais aucun ne proposait de réponse lorsque les deux difficultés sont réunies.\\

Lorsque les latences des écritures sont faibles par rapport au coût de calcul du gradient, il est possible de ne posséder qu'une seule version du paramètre à optimiser (dans notre cas les prototypes qui résument les données). Ainsi, certains travaux comme \cite{Zealous} ou \cite{Delalleau_Bengio_2007} proposent des schémas de parallélisation dans lesquels différents threads executés sur une seule machine multi-coeurs accèdent en écriture chacun leur tour au paramètre pour le modifier (on parle alors d'entrelacement des écritures). Comme souligné dans les conclusions de \cite{Delalleau_Bengio_2007} ou dans \cite{BBL}, ce mécanisme d'entrelacement n'est possible que sur une architecture matérielle avec mémoire partagée et pour un nombre faible de coeurs.\\

Sur le cloud, les temps d'écriture dans le BlobStorage sont trop importants par rapport au temps de calcul du gradient pour utiliser de telles techniques. Chaque unité de calcul, ici des machines virtuelles potentiellement distantes, possède donc sa propre version du paramètre (i.e. des prototypes) qu'elle modifie localement au fur et à mesure qu'elle examine des points issus du jeu de données sur lequel elle travaille. La difficulté de la parallélisation réside alors dans le choix d'une stratégie d'utilisation de ces différentes versions pour obtenir une version ``meilleure''.\\

La présentation dans les chapitres \ref{chap:practicalDALVQ} et \ref{chap:cloudDALVQ} de notre travail de parallélisation de l'algorithme de VQ, désigné dans la suite par Distributed Asynchronous Vector Quantization (DAVQ), reprend à rebours la chronologie de notre travail. En effet, inspirés par les résultats présentés dans \cite{TSI1}, \cite{PatraDALVQ} ou \cite{DekelShamir}, nous avons tout d'abord implémenté sur Azure une version répartie asynchrone de l'algorithme de VQ dans laquelle les différentes versions des prototypes sont moyennées de manière asynchrone. À notre surprise les premiers résultats ne fournissaient pas d'amélioration par rapport à l'algorithme séquentiel. Nous avons pendant longtemps cherché à comprendre ce résultat que nous mettions initialement sur le compte de spécificités d'Azure ou de réglages inhérents aux algorithmes stochastiques, notamment le réglage de la décroissance du pas $\{\varepsilon_t\}_{t=1}^{\infty}$.\\

Ces premiers résultats négatifs nous ont amenés à une analyse plus fine des schémas de parallélisation, analyse présentée dans le chapitre \ref{chap:practicalDALVQ}. En particulier, nous avons montré que dans notre problème le moyennage de différentes versions des prototypes ne mène pas à une meilleure version. Ce résultat vient très probablement de l'absence de convexité de notre fonction de perte, puisque des résultats théoriques d'accélération sont fournis dans des cadres très proches lorsque l'hypothèse de convexité est ajoutée (nous renvoyons par exemple à \cite{DekelShamir}). Les modélisations \eqref{eq:correctAveraging} et \eqref{eq:delayedAveraging} présentent des schémas alternatifs de parallélisation dont la simulation a présenté une accélération de la convergence par rapport à la version séquentielle de l'algorithme de VQ.\\

%Les modélisations \eqref{eq:correctAveraging} et \eqref{eq:delayedAveraging} du chapitre \ref{chap:practicalDALVQ} présentent de nouveaux schémas de parallélisation dont la simulation a présenté une accélération de la convergence par rapport à la version séquentielle de l'algorithme de VQ. Ces schémas se révèlent également adaptés pour fournir une réponse à un deuxième enjeu de notre problème, celui du ratio entre le temps nécessaire pour calculer le ``gradient'' de notre fonction de perte et le temps d'updater les prototypes. Dans le cas d'une implémentation sur une architecture avec mémoire partagée, les communications sont si rapides que le calcul du gradient en un point est comparativement suffisamment lent pour simplifier la logique d'update. Dans ce contexte, il est en effet possible d'entrelacer les updates exécutées par chaque processeur de telle manière qu'ils puissent updater les prototypes à chaque point examiné sans se gêner mutuellement. Dans notre cas, les ratios actuels des cadence des CPU par rapport aux bande-passantes disponibles font que ce mécanisme d'entrelacement n'est pas possible. Les modélisations développées prennent en compte ce fait puisque les communications ne sont pas effectuées à chaque point exécuté mais au moins tous les $\tau$ points.\\
%
%Nous soulignons que c'est la réunion de ces deux problèmes (non-convexité de la fonction de perte et latence des updates) qui nous a amenés à proposer de nouveaux schémas de parallélisation. En raison des performances d'Azure, notre implémentation cloud ne permet pas le mécanisme d'entrelacement dans lequel il n'existe qu'une version des prototypes commune à toutes les unités de calcul (cas traité par exemple dans \cite{Zealous} ou \cite{Delalleau_Bengio_2007}). Dans notre contexte, chaque unité de calcul possède sa propre version des prototypes et se pose alors la question du choix de la règle qui permet d'utiliser ces différentes versions pour bâtir une version des prototypes meilleure (au sens de notre critère de perte). C'est ici que la non-convexité de notre critère joue, puisque la règle naïve de moyennage de ces différentes versions utilisée par exemple dans \cite{SlowLearners} ou \cite{PatraDALVQ} ne permet plus dans notre cas d'obtenir de speedup.\\

Le chapitre \ref{chap:cloudDALVQ} présente l'implémentation cloud des travaux précédents. En particulier, nous décrivons en détail l'ordonnancement de notre algorithme en différents services et les mécanismes classiques de recouvrement de calcul et de communication utilisés au sein de chaque unité de calcul. Nous montrons que la version cloud de notre DAVQ permet d'obtenir des gains conséquents en terme d'accélération de la convergence : l'utilisation de machines supplémentaires permet jusqu'à un certain point d'accélérer cette vitesse de convergence vers un niveau de quantization équivalent.\\

La dernière section du chapitre \ref{chap:cloudDALVQ} présente un exemple dans lequel notre implémentation cloud du DAVQ converge plus rapidement que notre implémentation cloud du Batch K-Means vers des niveaux de quantization comparables. Nous retrouvons ainsi comme dans le cas séquentiel certaines des conclusions qui avaient été tirées de comparaisons réalisées entre Batch K-Means et Online K-Means (c'est à dire VQ) dans lesquelles l'algorithme en-ligne permettait d'obtenir plus rapidement un même niveau de quantization. Ces bonnes performances statistiques de notre version stochastique doivent être mises en regard avec le coût important de développement de l'algorithme, ainsi que l'instabilité et la difficulté de paramétrage inhérente à de nombreux algorithmes stochastiques.\\