HPC, « Big Data » : de la théorie à la pratique (2/2)

1. Les architectures parallèles

1.1 GPU

Les GPU (Graphical Processing Unit) se sont depuis quelques années transformés en GPGPU (General Purpose GPU). Ils peuvent maintenant être utilisés à des fins plus scientifiques que de jouer à GTA V en full HD.

L'architecture d'un GPU est très différente de celle d'un CPU classique, comme le montre la figure 1:

 

 

Cette architecture est particulièrement adaptée pour des problèmes de type du SIMD. Chaque unité de calcul (ALU) exécute la même instruction sur des données différentes. Ce que le programme décrit est le noyau de calcul, ou kernel, exécuté par chacune des ces ALU.

Plusieurs outils et langages existent pour programmer ces GPGPU. NVIDIA a développé le framework CUDA [1], spécifiques à ces GPU. Le groupe khronos, responsable d'OpenGL, a crée le standard OpenCL [2], qui décrit un modèle générique pour la programmation de systèmes hétérogènes (composés par exemple de plusieurs CPU et de plusieurs GPU), adopté par ex. par ATI pour ses GPU, et Intel & AMD pour leurs CPU.

Le principal problème de ce genre de périphériques est leur bus d'accès, généralement le PCI Express. Dans ses dernières versions (3.0), en 16x, ce bus peut transférer jusqu'à 15Go/s [3].

Or les données d'entrée nécessaires au calcul sont souvent localisées... en RAM. Il faut donc les transférer sur la carte graphique, calculer puis... rapatrier le résultat. De ces trois opérations, seule la deuxième, le calcul, est utile. Les autres ajoutent un surcoût. Ainsi, s'il s'avère (après benchmarks, bien sûr) que le CPU est capable de traiter le problème à une vitesse supérieure à la vitesse du bus PCI Express, alors le calcul sur GPU ne permet pas de gagner en performance. Une fois de plus, la loi d'Amdhal nous frappe de plein fouet.

Si au contraire le problème est de type SIMD, qu'il est très gourmand en calcul, et moins en mémoire, il y a de bonnes chances que l'accélération sur le GPU soit importante.

1.2 NUMA

Une architecture NUMA (Non Uniform Memory Access) est un système comportant plusieurs processeurs, chacun possédant son propre bus mémoire. Les différents processeurs sont reliés entre eux par des bus de type Intel QPI (QuickPath Interconnect), ou AMD HyperTransport. De part cette architecture, pour un CPU donné, les temps d'accès diffèrent suivant la zone mémoire accédée. La figure 2 décrit ce type d'architecture pour quatre processeurs :

 

 

Lorsque par exemple le CPU 4 veut accéder à des données situées dans le bloc 1, il passe donc par ce réseau d'interconnexion. Le débit de ce bus est assez important pour qu'il ne devienne pas vite un goulot d'étranglement. La bande passante de ce bus est parfois exprimé en GT/s, soit en Giga Transferts par seconde. Cela défini le nombre de transferts effectués sur le bus par seconde. Sachant que celui-ci est bi-directionnel, qu'il est d'une largeur de 20 bits (dont 16 bits de données utiles), cela donne une bande passante théorique de (T*16/8)*2 = T*4 (avec T le nombre de transferts par secondes). Ainsi, le processeur Intel Xeon E5-2680 (ci-dessus) possède un QPI offrant une bande passante utile de 8*4=32Go/s.

Ces architectures présentent plusieurs intérêts :

-chaque processeur possédant son propre bus mémoire, il est possible, si les données traitées sont bien réparties, d'utiliser pleinement chaque bus, et ainsi de faire passer à l'échelle des algorithmes « memory-bound »

-cela permet d'augmenter au passage la quantité maximum de RAM possible au sein d'un système. Des systèmes se basant sur cette architecture proposés par SGI peuvent supporter jusqu'à 64To de RAM (comme l'UV 2000 [4]).

Pour des applications limités par le débit RAM<->CPU, il faut apporter quelques changements afin de pouvoir exploiter au mieux cette architecture. En effet, sous Linux, la politique d'allocation mémoire par défaut va allouer des espaces mémoires physiquement au plus proche du CPU [5], donc sur son propre bloc mémoire. L'idée est de spécifier au système que cet espace doit être entrelacé entre les différents blocs. Plusieurs façons de faire cela :

-utiliser la libnuma [6] et la fonction numa_alloc_interleave(), qui fait exactement cela. Cette fonction est implémentée avec deux appels systèmes : mmap (pour un mapping de mémoire privé) et mbind, qui permet de définir la politique sur l'espace fraichement alloué :

-définir la politique d'allocation par défaut avec set_mempolicy :

-définir la politique par défaut avec numactl (paquet numa-tools sous Debian) :

L'avantage de cette méthode est qu'il n'implique aucune modification du programme source.

Changer la politique d'allocation par défaut a le désavantage d'éliminer toute localité pour certains buffers, et ainsi surcharger le bus QPI inutilement (et impliquer potentiellement une perte de performance). Cela est malheureusement à voir au cas par cas suivant les performances de l'application. Par exemple, cette stratégie a été adopté dans le paquet de 10gen de MongoDB sous Debian¹.

Pour conclure, le prix de tels systèmes peut souvent aller jusqu'à plusieurs centaines de milliers d'euros pour une machine à huit CPU. Ce prix est à comparer avec l'achat de huit machines installées au sein d'un cluster, beaucoup moins élevé.

1.3 Clusters

Traditionnellement, un cluster de machine se programme à travers une bibliothèque de passage de message, le standard de référence étant MPI pour... Message Passing Interface. Ça ne s'invente pas. Chaque machine doit alors gérer ses communications avec l'ensemble des autres machines, enpaqueter des messages associés à des signaux, un vrai régal. Cette méthode a fait ses preuves pour de nombreux codes scientifiques, mais reste une approche assez bas niveau. Gérer à la main l'ordonnancement de tâches hétérogènes n'est pas forcément à la portée de tout le monde.

Dans cette partie, nous allons vous présenter deux projets qui abordent le problème à plus haut niveau. Libre à vous de descendre aussi bas qu'il vous plaira !

1.3.1 Celery

Celery (http://www.celeryproject.org/) est un projet sous licence BSD permettant d'implémenter une file d'attente distribuée.

Le principe est décrit figure 3 et reste assez simple : d'un côté, des clients vont produire des tâches à réaliser, et les mettre dans une file d'attente. De l'autre côté, des serveurs « écoutent » sur cette file d'attente et vont tour à tour exécuter ces tâches. Dans Celery, la fonction de la file d'attente est en « FIFO » (First In First Out).

 

 

Celery distingue deux composants essentiels pour gérer ces tâches : le « broker » et le « backend ». Le broker est responsable de la gestion de la file d'attente, de recevoir les tâches des  »producteurs » (Celery utilise le terme de producer) et de les rediriger vers les collecteurs. Le rôle du backend est de stocker (potentiellement de manière permanente) les résultats des tâches exécutées, afin de les retourner aux producers à la demande. Le fonctionnement général est décrit figure 4.

 

 

Un des intérêts principaux de Celery est qu'il permet d'utiliser indifféremment différentes technologies pour la gestion de la file d'attente (appelée « broker ») et le stockage des résultats (appelée « backend »).

Nous allons étudier un court exemple afin d'illustrer nos propos (disponible ici : https://github.com/aguinet/misc-examples/tree/master/celery).
Premièrement, installer Redis, RabbitMQ et Celery avec la méthode de votre choix. La procédure à suivre sous Debian est la suivante :

-Installer Python 3, un serveur Redis (backend) et un serveur RabbitMQ (broker). Attention, par défaut certains de ces serveurs écoutent sur toutes les interfaces réseaux et ne possèdent aucune authentification, donc vérifier que vous êtes en environnement « sûr » avant de lancer ces commandes.

-Si nécessaire, configurer RabbitMQ et Redis pour écouter seulement sur localhost (recommandé pour cette phase de test) :

-Installer Celery, un client AMQP et Redis avec pip :

Ensuite, après avoir récupérer le code à l'URL ci-dessus, le lancement du « consumer » se fait grâce à la commande celery, de cette façon :

Ici, nous indiquons à celery de lancer un « worker » en utilisation l'objet Python celery.Celery « app » se trouvant dans le module « tasks ».

Ce module est composé du code suivant :

La première étape consiste à configurer Celery en lui indiquant le backend et broker utilisé. Ensuite, l'objet app créé va permettre de rajouter de nouvelles tâches. Le worker celery sait donc quelles tâches il peut exécuter, et comment.

Le producer tient lui aussi en quelques lignes de Python :

Le décorateur « app.task » a crée un objet qui permet de créer et de soumettre simplement des tâches. La fonction « delay » va envoyer la tâche au broker et renvoi un objet temporaire de résultat. Sur cette objet, la méthode « get » va attendre que le résultat soit disponible et le récupérer du broker.

Des schémas plus avancés peuvent être aussi décrit avec Celery :

Ici, nous lançons deux tâches « task_mul » de manière asynchrone, et indiquons à travers la méthode « chord » que, une fois que ces deux résultats sont finis, ils doivent être passés à la fonction « task_sum ». Le tout en une ligne (un peu longue) de Python.

Ceci n'est qu'une introduction à Celery. Pour aller plus loin, je vous invite à lire sa documentation (http://docs.celeryproject.org/en/latest/index.html) qui est très fournie. Il est aussi facile d'obtenir de l'aide sur le channel IRC #celery sur irc.freenode.net.

1.3.2 Hadoop

Hadoop est un framework open-source qui a pris naissance en 2004 au sein du projet open-source Apache Nutch, un moteur de recherche open-source. Nutch est ainsi le nom original d’Hadoop, et ce dernier a été adopté lorsque la partie traitement des données de Nutch a été externalisée.

Hadoop se base sur l’algorithme map-reduce. Le principe est de diviser les tâches en deux groupes : le mapping et le reduce . Les tâches d’un groupe peuvent être exécutées en parallèle. Le mapping est la première étape du processus : son but est de transformer les données en entrée en couple (clé, valeur). La réduction est une fonction qui va prendre en argument, pour une clé donnée, la liste des différentes valeurs, et va les « réduire » en une seule valeur. En sortie de l'algorithme, une liste de couples (clé, valeur) est crée. Ce principe est expliqué figure 5 :

 

 

Pour exemple, l'histogramme calculée précédemment peut être décrit selon ce modèle :

-la fonction de mapping correspond au calcul de l'index d'un nombre flottant dans l'histogramme. La valeur associée est 1.

-la fonction de réduce va tout simplement ajouter les différentes valeurs passées pour un index.

De plus, Hadoop se base sur son propre système de fichiers, le HDFS, adapté à la répartition des données sur un cluster de machines. Les données sont réparties par blocs, et ces blocs répartis sur les différents nœuds du cluster. Un système de réplication permet de dupliquer chacun des blocs sur différents nœuds. Ainsi, si une machine appartenant à ce système de fichier n’est plus fonctionnel, alors le système de fichier peut être reconstruit tout en étant disponible et sans aucune perte de données. Le taux de réplication c’est-à-dire le nombre de fois que chaque bloc est réparti - est configurable, afin d’être capable de supporter la perte de un ou plusieurs nœuds. Il y a ainsi un compromis stabilité/capacité de stockage à définir. De plus, lorsque les tâches définies ci-dessus sont exécutées, alors un principe de localité est mis en place : chaque nœud travaille au possible sur les données qui sont stockées sur ses disques, afin de minimiser les transferts réseaux.

Hadoop est ainsi un très bon candidat pour les applications ayant à la fois besoin d'accéder à des données importantes et d'effectuer des calculs assez coûteux.

2. Les performances du « commodity hardware »

Il est important de connaître les performances des composants des machines actuels afin de pouvoir dimensionner correctement son infrastructure et essayer de prédire quels seront les éléments limitants.

Pour les accès aux données, nous distinguerons deux critères dont nous avons vu l'importance précédemment : les vitesses de lecture et écriture séquentielles, et le nombre d'opération d'écriture et/ou de lectures possibles par seconde (appelées IOPS).

2.1 Disques durs

Pour mesurer les performances bruts des disques durs rotatifs actuels, il existe plusieurs solutions.

En ce qui concerne le débit séquentiel de lecture séquentiel, la commande dd sous Linux permet de se faire une idée assez rapidement. En tant que root, lancer :

Il faut ici faire attention à deux choses. Premièrement, d'après le manuel de dd, celui-ci divise par 1000 et non par 1024 pour le calcul du débit en Mo/s. Ainsi, en divisant par 1024, le débit est donc de 78.9 Mo/s. Deuxièmement, si vous relancer une deuxième fois cette commande, vous allez tomber sur quelque chose comme :

Votre disque dur n'est pas devenu soudain plus rapide qu'un SSD (voir section suivante), ceci est juste l'effet du cache disque Linux. En effet, les données viennent ici d'être lues depuis la RAM, et non depuis le disque, car accédées récemment. Plus d'informations sur ce cache ici : .

Afin de ne pas fausser les résultats, nous devons donc dire au noyau de vider ce cache avant toute mesure. En tant que root, faire :

Cela a pour effet de vider les caches disques. Plus d'informations sur drop_caches peuvent être trouvées dans la documentation du noyau Linux ici : https://www.kernel.org/doc/Documentation/sysctl/vm.txt.

Nous venons donc à l'écriture séquentielle. Pour cela, afin d'éviter au départ l'overhead potentiel du système de fichier, nous allons utiliser un disque vierge (ou éventuellement une partition vierge s'il vous reste un peu d'espace), et utiliser de la même façon dd :

Le débit obtenu reste dans l'ordre de grandeur de celui de la lecture séquentielle. On pourrait se demander quel est l'overhead dû au système de fichiers de cas là.

Par exemple, dans le cas de l'ext4, nous obtenons un overhead d'environ 0.02 % en lecture et en écriture. Au final, cela peut être considéré comme négligeable, ce qui nous intéresse ici étant plus les ordres de grandeur.

Afin de mesurer les performances en accès aléatoire, nous utilisons ce programme : https://github.com/aguinet/misc-examples/tree/master/tools/mem_rand_bench. Il permet de lire de manière aléatoire par bloc de taille définie un fichier ou un périphérique, et rapporte le nombre d'opérations effectuées en moyenne par seconde.

En n'oubliant pas à chaque fois de vider les caches, nous obtenons, en lecture aléatoire de blocs de 4Ko, environ 200 IOPS, et 180 IOPS en écriture. Comme nous allons le voir par la suite, ces performances sont très basses par rapport à ce qui peut se faire avec des SSD ou en RAM, et cela est une des limites des disques durs magnétiques actuels.

Le lecteur est invité à faire ces tests sur sa propre machine afin de se rendre compte par lui-même !

2.2 SSD

Les disques SSD changent un peu la donne, et permettent d'augmenter premièrement les débits en lecture et écritures séquentielles, mais aussi et surtout en terme d'IOPS.

En effet, sur un SSD, les débits généralement atteints avoisinent les 500Mo/s en lecture et écriture séquentielle. En ce qui concerne l'écriture, les performances peuvent avoir tendance à varier avec le temps, dû aux mémoires flashs utilisées.

Outre le débit amélioré, le gros avantage des SSD est l'amélioration du nombre d'opérations par secondes possibles. En effet, tandis que les disques durs classiques plafonnent à 200/250 IOPS, les SSD changent d'ordre de grandeur et arrivent plutôt vers 75 000 écritures aléatoires par seconde, et 35 000 léctures aléatoires par seconde [8]. Cela dépend beaucoup des constructeurs et quelques benchmarks vous permettront de vous rendre compte des performances réelles des SSD existants.

2.3 RAM

Les accès en RAM eux disposent de propriétés assez intéressantes. Le débit d'accès a augmenté considérablement ces dernières années. Un CPU Xeon de l'architecture Ivy Bridge, disposant de quatre canaux d'accès, peut atteindre un débit allant jusqu'à 10Go/s en lecture/écriture.

Cela peut être vérifié avec un programme très simple comme disponible ici (sous Linux) : http://www.cs.virginia.edu/stream/ref.html.

Sur un CPU Intel Ivy Bridge (à double canaux mémoires), nous obtenons, pour un seul CPU, les débits suivants :

2.3.1 Les canaux multiples

Aujourd'hui, les contrôleurs mémoires (souvent intégrées aux CPU) possèdent plusieurs canaux, qui permettent de multiplier en théorie la bande passante vers la RAM. Pour que cela soit possible, il faut que la machine soit occupée d'un nombre de barrettes de RAM multiple du nombre de canaux, et que celles-ci soient identiques.

L'emplacement de ces barrettes est aussi important. En effet, chaque canal est représenté par une « bank » (généralement avec une couleur différente), et il faut donc au mieux mettre un nombre égal de barrettes par « bank ».

2.3.2 Caches CPU

Les caches des CPU remplissent un rôle important : ils tentent de masquer le coût important des accès aléatoires en RAM.

En effet, comme vu précédemment, les caches sont organisés en plusieurs niveaux. Plus le cache est proche, plus les accès sont « rapides », mais plus le cache est petit. Typiquement, sur les processeurs actuels, les caches de niveau 1 ont une taille de 32Ko pour les données, et 32Ko pour les instructions CPU. Les caches de niveau 2 avoisinent les 256Ko, et les caches de niveau 3 sont souvent partagés entre les cœurs et peuvent atteindre jusqu'à 32Mo. Les caches fonctionnent par ligne de 64 octets, c'est-à-dire qu'à chaque renouvelement/écriture en RAM d'un octet en cache, c'est en fait 64 octets qui sont acheminés/réécris en RAM.

Nous allons lancer un test simple consistant à écrire de manière aléatoire dans un buffer de taille donné et de voir le débit moyen d'écriture, afin de voir l'effet de ces différents niveaux de caches. Le programme peut être téléchargé et compilé (sous Linux) ici :https://github.com/aguinet/misc-examples/tree/master/caches.

Les résultats sur un CPU Intel Xeon E5-1245v2 (32Ko de cache L1 et 256Ko de cache L2 par CPU, 8Mo de cache L3), en utilisant un seul cœur, sont affichés figure 6.

 

 

La première barre bleue correspond à 32Ko (taille du cache L1), la deuxième à 256Ko (taille du cache L2). On voit ainsi, comme pour le cas précédent de l'histogramme, que les performances chutent dramatiquement lorsque la taille du buffer dépasse 32Ko. En effet, les écritures aléatoires vont ainsi se faire en cache L2. Les données présentes en cache L1 sont souvent invalidées et ainsi des transferts mémoires inutiles se produisent. Le même phénomène se produit pour le cache de niveau 3 ensuite. Ce phénomène a été de plus très bien décrit par Ulrich Drepper dans son article « What Every Programmer Should Know About Memory » [7] (lecture conseillée;-)).

Exemple de l'histogramme

La figure 7 montre en vert les performances du calcul de l'histogramme vu précédemment en fonction de sa taille totale en mémoire.

 

 

La courbe rouge est la réplique de la courbe présentée figure 7 (débit des accès aléatoires en écriture en RAM). Ce qui est intéressant est que l'on vient bien que les performances de notre application deviennent de plus en plus limitées par les accès aléatoires au cache L2 (puis L3) du CPU.

La parallélisation de cet algorithme peut nous apporter des performances supplémentaires, car les caches L1 et L2 sont propres à chaque CPU (voir première partie). Cependant, l'hyperthreading peut ainsi devenir ici un vrai soucis, car deux threads partageraient les mêmes caches et passeraient ainsi leur temps à les invalider.

 

 

Ce phénomène se voit très bien figure 8, où le débit de traitement (toujours en Mo/s) est tracé en fonction du nombre de threads, pour un histogramme de 32Ko et de 1024Ko.

Ainsi, dans ce cas là, l'hyperthreading n'apporte pas de gain conséquent, et peut surtout amener à des performances réduites.

Certaines classes d'algorithmes se comportent très bien vis à vis du cache, et d'autre non. Généralement, le principe de localité est primordial : tant que l'ensemble des thread accède à des données proches en mémoire tout va bien, sinon (comme dans notre exemple), le risque que chaque thread passe son temps à invalider le cache du voisin augmente.

3. Les bases de données « NoSQL »

Les bases de données dites « NoSQL » sont un type de base de données divergeant des bases relationnelles classiques. Les données ne sont pas forcément stockées sous forme de table, et le côté relationnel est généralement mis de côté. De plus, le langage SQL n'est pas le langage natif de ces bases.

Plusieurs types de bases peuvent être distinguées. Une des premières grandes catégories de bases stockent leurs données sous forme de document (sans nécessairement de schémas prédéfinis). Une autre famille se concentre sur un format d'association clé → valeur.

3.1 Stockage de documents

Ce type de base n'est pas tout jeune. Les annuaires de type LDAP, qui ont vu le jour dans les années 90, en sont un parfait exemple. Les données sont stockées sous forme hiérarchique, et l'unité de stockage est un document contenant un ensemble d'attributs. Chaque niveau de hiérarchie peut définir un schéma différent. Ces bases sont généralement optimisées pour des lectures rapides, car beaucoup plus fréquentes que les écritures. Le contrôle d'accès est assez évolué et permet de définir les permissions de lecture et écriture au niveau de la hiérarchie et des attributs.

Comme bases de données plus récentes, MongoDB est parfois cité comme référence dans le domaine. Les documents sont stockés sous format BSON (Binary JSON), une version binaire sérialisée du JSON. Aucun schéma n'est défini, et les documents sont organisés dans des collections elles-mêmes réparties dans des bases de données différentes. MongoDB stocke le plus possibles les données en RAM en utilisant le principe de fichiers « mappés » en mémoire. Des API dans plusieurs langages sont disponibles, et restent assez simples à utiliser.
Voici un exemple de document MongoDB, qui pourrait être représenté des logs de connexion à un serveur :

De plus, un de ses gros avantages est qu'il scale sur plusieurs serveurs, en utilisant le concept de « sharding » [9]. Techniquement, les documents au sein d'une collection sont réparties entre plusieurs serveurs, utilisant ainsi les ressources en RAM de chaque machine.

D'autres serveurs sont basés sur le même principe, tels que CouchDB.

3.2 Stockage « clé / valeur »

Le stockage clé/valeur est aussi très répandu. Le principe est globalement d'avoir un tableau associatif d'une très grande taille, pouvant être réparti potentiellement entre plusieurs serveurs.

Le serveur Redis est un bon exemple. Il stocke les données en RAM avec un système de sauvegarde sur disque par intervalle régulier. Cela peut poser problème car les données présentes sur disque auront toujours un temps de retard par rapport à la réalité présente en mémoire. Cela peut être acceptable dans certaines conditions, mais il faut en être conscient.
Le client en ligne de commande est assez simple et permet de se rendre compte du fonctionnement de ce type de logiciel :

Le code python associé reste lui aussi assez simple :

D'autres serveurs de ce type existent, tels que Hypertable ou Cassendra.

4. Écrire une application « scalable »

Répétons-le, la règle d'or est de ne pas partir sur des optimisations prématurées. Faire des prototypes des traitements à effectuer et en déterminer les performances et les différents goulots d'étranglements est donc primordial. Avoir en tête les ordres de grandeurs évoqués précédemment et les problèmes classiques rencontrés est un plus indéniable pour interpréter les résultats des benchmarks...

Il est aussi important de voir les performances de chaque composants de la machine de test face aux processus testés. Par exemple, pour grep, quelle bande passante peut vraiment traiter notre CPU ? Comme vu en première partie, le disque dur devient vite limitant. Nous pouvons donc créer un ramfs afin de pouvoir tester assez sereinement les performances de notre CPU (en gardant en tête l'ordre de grandeur de 10Go/s du débit de la RAM utilisé sur notre système de test) :

ce qui nous donne un débit d'environ 192Mo/s (loin des 10Go/s d'accès en RAM). Ainsi, le dimensionnement d'une machine pour ce type d'application posera ce genre de questions :

-quelles seront les performances d'un CPU plus puissant ? Quel sera son coût ?

-si les performances de traitement d'un tel CPU sont par exemple de 500Mo/s, quelles implications cela aura sur le stockage ? (utilisation de SSD, de RAID0, des deux ?) Et la même question :quel sera son coût ?

-est-il plus avantageux de partir sur une infrastructure cluster ? Quel est son coût matériel ? Quelle sera son coup en terme d'ingénierie et de développement ?

Plusieurs choses sont à considérer ici. Premièrement, c'est (malheureusement ?) souvent le coût financier qui tranche dans ces situations. Pour information, voici un ordre de grandeur du coup du stockage à l'heure actuelle, suivant le support utilisé :

 

Technologie	Prix moyen au Go	Exemple
Disque dur 7200 trs/min SAS	~0.12€	WD RE SAS 1 To SATS 6Gb/s (~130€)
Disque dur SSD MLC	~2.31€ (environ x20)	Intel SSD DC S3700 400Go
RAM DDR PC1600 ECC	~20€ (environ x166)	Kingston ValueRAM 8 Go DDR3 ECC

De plus, on reste souvent confronté à trois types d'applications :

-celles qui demanderont peu de données face aux calculs complexes qui sont effectués, et qui sont donc généralement « CPU-bound ». Par exemple, un bruteforce d'un hash MD5 (ou autre) demande beaucoup de calcul pour une donnée en entrée assez faible (dans l'ordre de 16 octets).

-celles qui demanderont beaucoup de données mais peu de calcul, et qui sont ainsi communément appelés «IO-bound ». Par exemple, le calcul de l'histogramme précédent est limité par les accès en mémoire.

-celles qui sont entre les deux, et qui sont aussi les plus compliquées à appréhender.

La frontière entre ces différents mondes n'est bien sûr pas claire pour un algorithme donné, et ne dépend pas forcément de sa complexité. Pour s'en sortir, bien que l'expérience ici ait aussi son rôle, obtenir des chiffres sur les performances de son application dès le début d'un projet reste une démarche importante.

N'oubliez pas non plus (pour faciliter le problème) que le code que vous aller écrire doit rester assez évolutif, car les mesures faites aujourd'hui ne seront peut être plus valides demain... et qu'écrire un code spécialiser à outrance pour une architecture, c'est s'exposer à le réécrire pour la prochaine génération de CPU / GPU /...

5. Applications à la sécurité informatique

MISC restant un journal traitant de la sécurité informatique, il parait opportun d'appliquer tout ce qui a été évoqué précédemment à ce domaine.

On peut trouver sur Internet plusieurs exemples de projets open-source « haute-performance » lié à la sécurité informatique.

Nous pouvons commencer par le projet truecrack [10], dont le but est d'utiliser la puissance des GPU actuels afin de bruteforcer des conteneurs truecrypt. Le site annonce un gain de performance d'environ 10.

Dans un autre registre, l'actualité récente a vu fleurir beaucoup de logiciels permettant de « scanner Internet » en moins d'une heure. Nous pouvons citer Zmap [11] ou encore masscan [12]. Ils se basent sur le fait que, au niveau d'une machine, le goulot d'étranglement d'un scanner doit être le nombre de paquets par seconde (noté PPS par la suite) que peut générer la ou les cartes réseaux associées. Plusieurs astuces permettent d'arriver à cela, généralement un bypass de plusieurs couches du noyau afin d'écrire au plus proche du driver de la carte réseau, couplé parfois à l'utilisation de drivers spécifiques. Avec ces astuces, Masscan affiche un nombre de paquets émis avoisinant les deux millions par seconde (sur une carte ethernet 10gb).
Cependant, ces exemples sont intéressants car ils se heurtent à un autre goulot d'étranglement (classiquement..) : la capacité qu'ont le ou les routeurs les reliant à Internet à router ces millions de paquets. À titre de comparaison, un routeur de cœur de réseau Cisco peut router dans le meilleur des cas jusqu'à 50 millions PPS [13]. Hors l'utilisateur d'un de ces logiciels n'est généralement pas seul sur son réseau d'opérateur... Envoyer une telle quantité de paquets peut de plus provoquer le remplissage des tampons des différents routeurs, et impliquer que beaucoup de paquets soient simplement éliminés. L'effet inverse de celui recherché est donc atteint. Rappelez-vous ce cher Donald Knuth.
Ainsi, effectuer ce genre de scans sur un clusters de machines déployées dans des réseaux différents paraît nécessaire pour atteindre les performances annoncées. Une technologie par « passage de messages » type Celery peut être intéressante dans ce cas là.

Ces scanners introduisent aussi un autre problème intéressant : la génération de nombres aléatoires uniques, nécessaire afin de ne pas scanner linéairement tout Internet. Le problème est évoqué en détail ici [14]. Bien que ce ne soit pas le cas, il est intéressant de vérifier que ce générateur est capable de générer autant de nombres aléatoires par seconde que de paquets à envoyer. Si nécessaire, des optimisations vectoriels et/ou une parallélisation du processus peuvent apporter une solution.

Un autre exemple intéressant d'un autre genre est l'utilisation de l'API streaming d'Hadoop. Imaginons que vous ayez stockés tous vos logs réseaux sur un système HDFS (bien qu'intéressante, la configuration d'un tel cluster ne sera pas discuté ici ; de très bonnes documentations peuvent être trouvées ici [15]), et que vous ayez envie rapidement de lancer (au hasard) la commande grep sur ces données afin de chercher (toujours au hasard) les connexions SSH échouées, alors une commande de ce genre peut donner le résultat :

Pas forcément très « sexy », mais facilement scriptable.

6. Conclusion

Le domaine du High Performance Computing est vaste, et comprendre les différentes technologies qui ont été développées dans ce domaine au fil des années est une lourde tâche. La création d'applications performantes est un challenge quotidien pour les personnes travaillant dans le domaine. Tout ici n'a pas été évoqué, mais nous avons essayé de donner un aperçu général du domaine (avec des exemples concrets). Les différents pointeurs de l'article peuvent amener les plus curieux à creuser d'avantage les technologies décrites.

N'hésitez pas à nous envoyez toutes remarques, questions et/ou erreurs de notre part aux mails ci-dessous.

Nous laisserons le mot de la fin à Frederick Brooks :

« Nine women can't make a baby in one month »

Références

[1] https://developer.nvidia.com/category/zone/cuda-zone

[2] http://www.khronos.org/opencl/

[3] http://www.tested.com/tech/457440-theoretical-vs-actual-bandwidth-[pci-express-and-thunderbolt/

[4] http://www.sgi.com/products/servers/uv/models.html

[5] http://man7.org/linux/man-pages/man2/set_mempolicy.2.html (description de MPOL_DEFAULT)

[6] http://linux.die.net/man/3/numa

[7] http://www.akkadia.org/drepper/cpumemory.pdf

[8] http://www.tomshardware.com/reviews/ssd-dc-s3700-enterprise-storage,3352-5.html

[9] http://docs.mongodb.org/manual/core/sharding/

[10] http://code.google.com/p/truecrack/

[11] https://zmap.io/

[12] https://github.com/robertdavidgraham/masscan

[13] http://www.cisco.com/web/partners/downloads/765/tools/quickreference/routerperformance.pdf

[14] http://blog.quarkslab.com/unique-random-number-set-computation.html

[15] http://hadoop.apache.org/docs/stable/cluster_setup.html

Note

(1) numactl est utilisé dans le script d'initialisation du service