Traitement de flux

En informatique , le traitement de flux (également appelé traitement de flux d'événements , traitement de flux de données ou traitement de flux distribué ) est un paradigme de programmation qui considère les flux , ou séquences d'événements dans le temps, comme les objets d'entrée et de sortie centraux du calcul . Le traitement de flux englobe la programmation par flux de données , la programmation réactive et le traitement distribué des données . Les systèmes de traitement de flux utilisent des algorithmes de flux pour tracer le traitement parallèle des flux de données. La pile logicielle de ces systèmes comprend des composants tels que des modèles de programmation et des langages de requête , pour exprimer le calcul ; des systèmes de gestion de flux , pour la distribution et l'ordonnancement ; et des composants matériels pour l'accélération, notamment des unités de calcul en virgule flottante , des unités de traitement graphique et des FPGA .

Le paradigme du traitement de flux simplifie les logiciels et le matériel parallèles en limitant les calculs parallèles possibles. Étant donné une séquence de données (un flux ), une série d'opérations ( fonctions noyau ) est appliquée à chaque élément du flux. Les fonctions noyau sont généralement pipelinées et une réutilisation optimale de la mémoire locale sur puce est recherchée afin de minimiser la perte de bande passante liée aux interactions avec la mémoire externe. Le traitement de flux uniforme , où une seule fonction noyau est appliquée à tous les éléments du flux, est typique. Puisque les abstractions de noyau et de flux exposent les dépendances de données, les outils de compilation peuvent automatiser et optimiser entièrement les tâches de gestion sur puce. Le matériel de traitement de flux peut utiliser le scoreboarding , par exemple, pour initier un accès direct à la mémoire (DMA) lorsque des dépendances sont connues. L'élimination de la gestion manuelle du DMA réduit la complexité logicielle et, par conséquent, la mise en cache matérielle des E/S, ce qui réduit la surface de données utilisée par les unités de calcul spécialisées telles que les unités arithmétiques et logiques .

Dans les années 1980, le traitement de flux a été exploré dans le cadre de la programmation par flux de données . Le langage SISAL (Streams and Iteration in a Single Assignment Language) en est un exemple.

Le traitement de flux est par essence un compromis, reposant sur un modèle centré sur les données. Ce modèle est parfaitement adapté aux applications DSP ou GPU traditionnelles ( traitement d'images, de vidéos et de signaux numériques , par exemple ), mais moins performant pour les traitements à usage général nécessitant un accès aux données plus aléatoire (bases de données, par exemple). En sacrifiant une certaine flexibilité, le modèle permet une exécution plus simple, plus rapide et plus efficace. Selon le contexte, la conception du processeur peut privilégier l'efficacité maximale ou, au contraire, la flexibilité.

Le traitement de flux est particulièrement adapté aux applications qui présentent trois caractéristiques :

• L'intensité de calcul , c'est-à-dire le nombre d'opérations arithmétiques par entrée/sortie ou référence mémoire globale, dépasse largement 50:1 dans de nombreuses applications de traitement du signal actuelles et augmente avec la complexité algorithmique.
• Le parallélisme des données existe dans un noyau si la même fonction est appliquée à tous les enregistrements d'un flux d'entrée et si un certain nombre d'enregistrements peuvent être traités simultanément sans attendre les résultats des enregistrements précédents.
• La localité des données est un type spécifique de localité temporelle, fréquent dans les applications de traitement du signal et des médias, où les données sont produites une seule fois, lues une ou deux fois plus tard dans l'application, puis plus jamais. Les flux intermédiaires échangés entre les noyaux, ainsi que les données intermédiaires au sein des fonctions des noyaux, peuvent exploiter directement cette localité grâce au modèle de programmation du traitement de flux.

Exemples d'enregistrements dans les flux :

• En infographie, chaque enregistrement peut correspondre aux informations relatives au sommet, à la normale et à la couleur d'un triangle ;
• En traitement d'images, chaque enregistrement peut correspondre à un seul pixel d'une image ;
• Dans un encodeur vidéo, chaque enregistrement peut comporter 256 pixels formant un macrobloc de données ; ou
• En traitement du signal sans fil, chaque enregistrement peut être une séquence d'échantillons reçus d'une antenne.

Pour chaque enregistrement, nous pouvons uniquement lire l'entrée, effectuer des opérations dessus et écrire dans la sortie. Il est permis d'avoir plusieurs entrées et plusieurs sorties, mais jamais une zone mémoire à la fois lisible et inscriptible.

À titre d'illustration, les extraits de code suivants démontrent la détection de motifs dans les flux d'événements. Le premier est un exemple de traitement d'un flux de données à l'aide d'une requête SQL continue (une requête qui s'exécute indéfiniment, traitant les données entrantes en fonction des horodatages et de la durée de la fenêtre). Cet extrait de code illustre une jointure entre deux flux de données : l'un pour les ordres boursiers et l'autre pour les transactions boursières qui en résultent. La requête génère un flux contenant tous les ordres correspondant à une transaction dans la seconde suivant leur passation. Le flux de sortie est trié par horodatage, en l'occurrence, l'horodatage du flux des ordres.

SELECT DataStream Orders.TimeStamp , Orders.orderId , Orders.ticker , Orders.amount , Trade.amount FROM Orders JOIN Trades OVER ( RANGE INTERVAL ' 1 ' SECOND FOLLOWING ) ON Orders.orderId = Trades.orderId ;​​​​​​​​​​​​

Un autre extrait de code détecte les mariages parmi un flux d'« événements » externes, tels que le son des cloches d'une église, l'apparition d'un homme en smoking ou en jaquette, une femme en robe blanche fluide et du riz qui vole dans les airs. Un événement « complexe » ou « composite » est ce que l'on déduit de ces événements simples : un mariage est en train de se produire.

QUAND Person.Gender EST ÉGAL À « homme » ET Person.Clothes EST ÉGAL À « smoking » SUIVI DE Personne.Vêtements ÉGALE « robe » ET (Church_Block OU Rice_Flying) EN MOINS DE 2 heures ACTION Mariage 

Les premiers ordinateurs fonctionnaient selon un paradigme d'exécution séquentielle. Les processeurs traditionnels sont basés sur le principe SISD (Séquentiel , Séquentiel, Différence), ce qui signifie qu'ils n'effectuent conceptuellement qu'une seule opération à la fois. Avec l'évolution des besoins informatiques mondiaux, la quantité de données à gérer a explosé. Il est devenu évident que le modèle de programmation séquentielle ne pouvait plus répondre à la demande croissante de puissance de calcul. De nombreux efforts ont été déployés pour trouver des solutions alternatives permettant d'effectuer des calculs massifs, mais la seule solution retenue a été d'exploiter un certain niveau d'exécution parallèle. Ces efforts ont abouti au SIMD ( Système d'Instruction Programmation Modulée), un paradigme de programmation permettant d'appliquer une seule instruction à plusieurs instances de données (différentes). Le SIMD était généralement utilisé dans un environnement SWAR (Système d'Instruction Programmation ). En utilisant des structures plus complexes, il était également possible d'obtenir un parallélisme MIMD ( Méthode d'Instruction Programmation Modulée ).

Bien que ces deux paradigmes fussent efficaces, leurs implémentations concrètes souffraient de limitations, allant des problèmes d'alignement mémoire aux problèmes de synchronisation, en passant par un parallélisme limité. Seuls quelques processeurs SIMD ont subsisté en tant que composants autonomes ; la plupart ont été intégrés aux processeurs centraux standard.

Prenons l'exemple d'un programme simple qui additionne deux tableaux contenant 100 vecteurs à 4 composantes (soit 400 nombres au total).

for ( int i = 0 ; i < 400 ; i ++ ) { result [ i ] = source0 [ i ] + source1 [ i ]; }

C’est le paradigme séquentiel le plus répandu. Il existe des variantes (boucles internes, structures, etc.), mais elles se résument en fin de compte à cette construction.

// pour chaque vecteur for ( int elem = 0 ; elem < 100 ; elem ++ ) { vectorSum ( result [ elem ], source0 [ elem ], source1 [ elem ]); }

Cette description est en réalité très simplifiée. Elle suppose que l'instruction vector_sumfonctionne. Bien que ce soit le cas pour les instructions intrinsèques , de nombreuses informations ne sont pas prises en compte, comme le nombre de composantes du vecteur et leur format de données. Ce choix est fait par souci de clarté.

On constate toutefois que cette méthode réduit le nombre d'instructions décodées de `numElements * componentsPerElement` à `numElements` . Le nombre d'instructions de saut est également réduit, car la boucle est exécutée moins de fois. Ces gains résultent de l'exécution parallèle des quatre opérations mathématiques.

En revanche, le registre SIMD compacté contient une quantité limitée de données, ce qui empêche d'obtenir davantage de parallélisme. L'accélération est donc quelque peu limitée par l'hypothèse que nous avons faite d'effectuer quatre opérations parallèles (à noter que ce cas de figure est commun à AltiVec et SSE ).

// Ceci est un langage fictif à des fins de démonstration. éléments = tableau streamElement ([ nombre , nombre ])[ 100 ] noyau = instance streamKernel ( "@arg0[@iter]" ) résultat = noyau . invoke ( éléments )

Dans ce paradigme, l'ensemble des données est défini, plutôt que chaque bloc composant séparément. La description des données est supposée figurer dans les deux premières lignes. Ensuite, le résultat est déduit des sources et du noyau. Par souci de simplicité, il existe une correspondance biunivoque entre les données d'entrée et de sortie, mais ce n'est pas obligatoire. Les noyaux utilisés peuvent également être beaucoup plus complexes.

Ce paradigme permet de « dérouler » une boucle en interne. Le débit peut ainsi évoluer en fonction de la complexité de la puce, en exploitant facilement des centaines d'unités arithmétiques et logiques (UAL). L'élimination des modèles de données complexes rend disponible une grande partie de cette puissance supplémentaire.

Bien que le traitement de flux soit une branche du traitement SIMD/MIMD, il ne faut pas les confondre. Si les implémentations SIMD peuvent souvent fonctionner en mode « flux », leurs performances ne sont pas comparables : le modèle envisage un mode d’utilisation très différent, qui permet d’atteindre des performances nettement supérieures.

Il a été constaté que, sur des processeurs génériques tels que les CPU standard, on n'obtient qu'une accélération de 1,5x. En revanche, les processeurs de flux ad hoc atteignent facilement des performances supérieures à 10x, principalement grâce à un accès mémoire plus efficace et à un niveau de traitement parallèle plus élevé.

Bien que le modèle offre différents degrés de flexibilité, les processeurs de flux imposent généralement certaines limitations à la taille du noyau ou du flux. Par exemple, le matériel grand public est souvent incapable d'effectuer des calculs de haute précision, ne prend pas en charge les chaînes d'indirection complexes ou présente des limites inférieures quant au nombre d'instructions exécutables.

Les projets de traitement de flux de l'Université de Stanford comprenaient le Stanford Real-Time Programmable Shading Project, lancé en 1999 Un prototype nommé Imagine a été développé en 2002 Le projet Merrimac s'est poursuivi jusqu'en 2004 environ AT&T a également mené des recherches sur les processeurs optimisés pour le traitement de flux, les unités de traitement graphique évoluant rapidement en termes de vitesse et de fonctionnalités ^[1] . Depuis ces débuts, des dizaines de langages de traitement de flux ont été développés, ainsi que du matériel spécialisé.

Le défi le plus immédiat en matière de traitement parallèle ne réside pas tant dans le type d'architecture matérielle utilisé, mais plutôt dans la facilité de programmation du système en question dans un environnement réel, tout en garantissant des performances acceptables. Des machines comme Imagine utilisent un modèle monothread simple, avec gestion automatisée des dépendances, allocation mémoire et planification DMA . Ce modèle est le fruit des recherches menées au MIT et à Stanford pour trouver une répartition optimale des tâches entre programmeur, outils et matériel. Les programmeurs sont plus performants que les outils pour adapter les algorithmes au matériel parallèle, et les outils sont plus performants que les programmeurs pour optimiser l'allocation mémoire, etc. Les architectures MIMD, telles que Cell , sont particulièrement problématiques, car le programmeur doit gérer le partitionnement des applications sur plusieurs cœurs, ainsi que la synchronisation des processus et l'équilibrage de charge.

Un inconvénient de la programmation SIMD résidait dans la gestion des tableaux de structures (AoS) et des structures de tableaux (SoA) . Les programmeurs créent souvent des représentations d'entités en mémoire, par exemple la position d'une particule dans l'espace 3D, la couleur et la taille d'une sphère, comme illustré ci-dessous :

// Une particule dans un espace tridimensionnel. struct Particle { double x ; double y ; double z ;// 8 bits par canal, disons que nous ne nous intéressons qu'à la couleur RGB, octet non signé [ 3 ] ; taille flottante ; // ... et de nombreux autres attributs peuvent suivre... };

Lorsque plusieurs de ces structures sont présentes en mémoire, elles sont placées bout à bout, créant ainsi une topologie de type « tableau dans un tableau de structures » (AoS). Cela signifie que si un algorithme est appliqué à l'emplacement de chaque particule, il doit ignorer les emplacements mémoire contenant les autres attributs. Si ces attributs ne sont pas nécessaires, cela entraîne une utilisation inutile du cache du processeur. De plus, une instruction SIMD s'attend généralement à ce que les données sur lesquelles elle opère soient contiguës en mémoire ; les éléments peuvent également devoir être alignés . En déplaçant l'emplacement mémoire des données hors de la structure, les données peuvent être mieux organisées pour un accès efficace dans un flux et pour le traitement des instructions SIMD. Une structure de tableaux (SoA), comme illustrée ci-dessous, permet cela.

struct Particule { double * x ; double * y ; double * z ;octet non signé * couleurRouge ; octet non signé * couleurBleu ; octet non signé * couleurVert ;float * taille ; };

Au lieu de stocker les données dans la structure, elle ne contient que des pointeurs (adresses mémoire) vers ces données. L'inconvénient est que si plusieurs attributs d'un objet doivent être manipulés, ils peuvent désormais être éloignés en mémoire, ce qui entraîne un défaut de cache. L'alignement et le remplissage éventuel augmentent la consommation de mémoire. Globalement, la gestion de la mémoire peut se complexifier si des structures sont ajoutées ou supprimées, par exemple.

Pour les processeurs de flux, l'utilisation de structures est recommandée. Du point de vue applicatif, tous les attributs peuvent être définis avec une certaine flexibilité. Prenons l'exemple des GPU : un ensemble d'attributs (au moins 16) est disponible. Pour chaque attribut, l'application peut spécifier le nombre et le format des composants (mais seuls les types de données primitifs sont pris en charge pour le moment). Les différents attributs sont ensuite associés à un bloc mémoire, définissant éventuellement un pas entre les éléments consécutifs d'un même attribut, ce qui permet l'entrelacement des données. Lorsque le GPU lance le traitement du flux, il rassemble tous les attributs dans un ensemble de paramètres unique (généralement une structure ou une variable globale), effectue les opérations et répartit les résultats dans une zone mémoire pour un traitement (ou une récupération) ultérieur(e).

Les frameworks de traitement de flux modernes offrent une interface de type FIFO pour structurer les données sous forme de flux littéral. Cette abstraction permet de spécifier implicitement les dépendances de données tout en permettant à l'environnement d'exécution et au matériel d'exploiter pleinement ces informations pour un calcul efficace. RaftLib est l'une des méthodes de traitement de flux les plus simples et les plus efficaces à ce jour pour C++. Elle permet de lier des noyaux de calcul indépendants sous forme de graphe de flux de données à l'aide des opérateurs de flux C++. Par exemple :

import < raft > ; import < raftio > ;import std ;utiliser String = std :: string ;using RaftKernel = raft :: kernel ; using RaftKernelStatus = raft :: kstatus ; using RaftMap = raft :: map ; using RaftPrint = raft :: print ;class HelloWorld : public RaftKernel { public : HelloWorld () { output . addPort < String > ( "0" ); }virtual RaftKernelStatus run () { output [ "0" ]. push ( "Hello World " ); return raft :: stop ; } };int main ( int argc , char * argv []) { // instancier le noyau d'impression RaftPrint < String > p ;// instancier le noyau hello world HelloWorld hello ;// créer un objet carte RaftMap m ;// ajouter des noyaux à la carte, hello et p sont exécutés simultanément m += hello >> p ;// exécuter la carte m.exe ();retourner 0 ; }

Outre la spécification des applications de flux dans des langages de haut niveau, les modèles de calcul (MoC) ont également été largement utilisés comme modèles de flux de données et modèles basés sur les processus.

Historiquement, les processeurs ont intégré différents niveaux d'optimisation de l'accès à la mémoire en raison de leurs performances toujours croissantes, comparées à la croissance relativement lente de la bande passante de la mémoire externe. À mesure que cet écart s'est creusé, une part importante de la surface de la puce a été consacrée à la réduction de la latence mémoire. Le coût d'accès aux informations et aux codes d'opération pour les quelques unités arithmétiques et logiques (UAL) étant élevé, la surface de la puce dédiée aux calculs proprement dits est très faible (on peut l'estimer à moins de 10 %).

Une architecture similaire existe sur les processeurs de flux, mais grâce au nouveau modèle de programmation, le nombre de transistors dédiés à la gestion est en réalité très faible.

Du point de vue du système dans son ensemble, les processeurs de flux fonctionnent généralement dans un environnement contrôlé. Les GPU sont intégrés sur une carte d'extension (cela semble également s'appliquer à Imagine). Les CPU continuent de gérer les ressources système, d'exécuter les applications, etc.

Le processeur de flux est généralement équipé d'un bus mémoire propriétaire rapide et performant (les commutateurs crossbar sont aujourd'hui courants, mais des bus multiples ont été utilisés par le passé). Le nombre exact de lignes mémoire dépend du segment de marché. À l'heure actuelle, on trouve encore des interconnexions 64 bits (entrée de gamme). La plupart des modèles de milieu de gamme utilisent une matrice de commutation crossbar rapide de 128 bits (4 ou 2 segments), tandis que les modèles haut de gamme déploient d'importantes quantités de mémoire (jusqu'à 512 Mo) avec un crossbar légèrement moins rapide de 256 bits. En revanche, les processeurs standard, de l'Intel Pentium à certains Athlon 64, ne disposent que d'un seul bus de données 64 bits.

Les schémas d'accès à la mémoire sont beaucoup plus prévisibles. Bien que les tableaux existent, leur dimension est fixée lors de l'appel au noyau. Ce qui se rapproche le plus d'une indirection par pointeurs multiples est une chaîne d'indirection , qui garantit toutefois de lire ou d'écrire dans une zone mémoire spécifique (au sein d'un flux).

Du fait de la nature SIMD des unités d'exécution (clusters d'UAL) du processeur de flux, les opérations de lecture/écriture sont effectuées par lots. Par conséquent, la mémoire est optimisée pour une bande passante élevée plutôt que pour une faible latence (contrairement à la Rambus et à la DDR SDRAM , par exemple). Ceci permet également une négociation efficace du bus mémoire.

La majeure partie (90 %) du travail d'un processeur de flux est effectuée sur la puce, ne nécessitant que 1 % des données globales en mémoire. C'est là que la connaissance des variables temporaires et des dépendances du noyau s'avère cruciale.

En interne, un processeur de flux intègre des circuits de communication et de gestion sophistiqués, mais son élément le plus intéressant est le fichier de registres de flux (SRF). Il s'agit conceptuellement d'un cache de grande capacité où les données de flux sont stockées en vue de leur transfert par lots vers la mémoire externe. Fonctionnant comme un cache géré par logiciel pour les différentes unités arithmétiques et logiques (UAL) , le SRF est partagé entre tous les clusters d'UAL. L'innovation majeure de la puce Imagine de Stanford réside dans la capacité du compilateur à automatiser et allouer la mémoire de manière optimale, en toute transparence pour le programmeur. Les dépendances entre les fonctions du noyau et les données sont connues grâce au modèle de programmation, ce qui permet au compilateur d'effectuer une analyse de flux et d'optimiser l'utilisation des SRF. Généralement, la gestion du cache et de l'accès direct à la mémoire (DMA) peut représenter la majeure partie du temps de développement d'un projet ; une tâche que le processeur de flux (ou du moins Imagine) automatise entièrement. Des tests réalisés à Stanford ont démontré que le compilateur était aussi performant, voire plus performant, en matière d'allocation mémoire qu'un paramétrage manuel complexe et laborieux.

Il existe des preuves : un grand nombre de clusters est possible car la communication inter-clusters est considérée comme rare. En revanche, chaque cluster peut exploiter efficacement un nombre bien moindre d'unités arithmétiques et logiques (UAL) car la communication intra-cluster est fréquente et doit donc être extrêmement efficace.

Pour que ces ALU soient toujours alimentées en données, chaque ALU est équipée de fichiers de registres locaux (LRF), qui sont essentiellement ses registres utilisables.

Ce modèle d'accès aux données à trois niveaux permet d'éloigner facilement les données temporaires des mémoires lentes, ce qui rend l'implémentation sur silicium très efficace et économe en énergie.

Bien qu'un gain de vitesse d'un ordre de grandeur soit raisonnablement envisageable (même avec les GPU grand public en traitement de flux), toutes les applications n'en bénéficient pas. La latence de communication constitue le principal obstacle. Malgré les améliorations apportées par PCI Express grâce à la communication bidirectionnelle simultanée, la mise en service d'un GPU (et éventuellement d'un processeur de flux générique) peut s'avérer longue. De ce fait, leur utilisation pour de petits ensembles de données est généralement contre-productive. Par ailleurs, la modification du noyau étant une opération coûteuse, l'architecture de flux engendre également des pénalités pour les petits flux, un phénomène connu sous le nom d' effet de flux court .

Le pipeline est une pratique très répandue et largement utilisée sur les processeurs de flux, les GPU pouvant atteindre plus de 200 étages. Le coût de la modification des paramètres dépend de ces derniers, mais il est désormais considéré comme toujours élevé. Pour pallier ces problèmes à différents niveaux du pipeline, de nombreuses techniques ont été mises en œuvre, telles que les « sur-shaders » et les « atlas de textures ». Ces techniques sont orientées vers le jeu vidéo en raison de la nature des GPU, mais leurs concepts sont également intéressants pour le traitement de flux en général.