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.
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 :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.
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).
Paradigme conventionnel et séquentiel
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 ).
Paradigme des flux parallèles (SIMD/MIMD)
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.
Recherche
Notes sur le modèle de programmation
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 :
Modèles de calcul pour le traitement de flux
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.
Architecture de processeur générique
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.
Problèmes liés au matériel en boucle
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.
Exemples
Bibliothèques et langages de programmation de flux
La plupart des langages de programmation pour processeurs de flux sont basés sur Java, C ou C++ et ajoutent des extensions fournissant des instructions spécifiques permettant aux développeurs d'applications d'étiqueter les noyaux et/ou les flux. Ceci s'applique également à la plupart des langages de shaders , qui peuvent être considérés, dans une certaine mesure, comme des langages de programmation de flux.
Voici quelques exemples non commerciaux de langages de programmation de flux :
- Ateji PX Free Edition permet une expression simple de la programmation de flux, du modèle d'acteurs et de l'algorithme MapReduce sur JVM.
- AutoPipe, développé par le laboratoire de supercalcul basé sur les flux de l'université Washington de Saint-Louis , est un environnement de développement d'applications pour le traitement de flux permettant la création d'applications pour systèmes hétérogènes (CPU, GPGPU , FPGA). Les applications peuvent être développées en C, C++ et Java pour le CPU, et en Verilog ou VHDL pour les FPGA. CUDA est actuellement utilisé pour les GPGPU Nvidia. AutoPipe gère également la coordination des connexions TCP entre plusieurs machines.
- Modèle de programmation ACOTES : langage de l’Université polytechnique de Catalogne basé sur OpenMP
- BeepBeep, une bibliothèque de traitement de flux d'événements simple et légère basée sur Java, développée par le Laboratoire d'informatique formelle de l' Université du Québec à Chicoutimi.
- Langue Brook de Stanford
- CAL Actor Language : un langage de programmation de haut niveau pour écrire des acteurs (flux de données), qui sont des opérateurs à état qui transforment les flux d'entrée d'objets de données (jetons) en flux de sortie.
- Cal2Many est un framework de génération de code développé par l'université de Halmstad, en Suède. Il prend du code CAL en entrée et génère différents langages cibles spécifiques, notamment le C séquentiel, Chisel, le C parallèle ciblant l'architecture Epiphany, Java et Astruct ciblant l'architecture Ambric, etc.
- Langue DUP de l'Université technique de Munich et de l'Université de Denver
- HSTREAM : une extension de langage basée sur des directives pour le calcul de flux hétérogènes
- RaftLib - bibliothèque de modèles de traitement de flux C++ open source, initialement développée par le Stream Based Supercomputing Lab de l'Université Washington à Saint-Louis.
- Rimmel.js est une bibliothèque JavaScript qui permet le développement d'interfaces utilisateur basées sur les flux en traitant tous les nœuds et attributs HTML comme des sources et des récepteurs réactifs.
- SPar est un langage C++ dédié au domaine, développé par le Groupe de modélisation d'applications (GMAP) de l' Université pontificale catholique de Rio Grande do Sul, pour exprimer le parallélisme de flux.
- Bibliothèque Sh de l' Université de Waterloo
- Shallows, un projet open source
- Le langage de coordination S-Net de l' Université du Hertfordshire assure la séparation entre la coordination et la programmation algorithmique.
- StreamIt du MIT
- Siddhi de WSO2
- WaveScript, un logiciel de traitement de flux fonctionnel également développé au MIT.
- La programmation réactive fonctionnelle pourrait être considérée comme du traitement de flux au sens large.
Les implémentations commerciales sont soit généralistes, soit liées à un matériel spécifique par un fournisseur. Exemples de langages généralistes :
- Jacket d' AccelerEyes est une commercialisation d'un moteur GPU pour MATLAB.
- Extension Java Ateji PX permettant une expression simple de la programmation de flux, du modèle Actor et de l'algorithme MapReduce.
- Embiot, un agent d'analyse de flux embarqué léger de Telchemy
- Floodgate est un processeur de flux fourni avec le moteur de jeu Gamebryo pour PlayStation 3, Xbox 360, Wii et PC.
- OpenHMPP , une vision « directive » de la programmation multicœur
- PeakStream, une spin-off du projet Brook (acquis par Google en juin 2007)
- IBM Spade - Moteur déclaratif d'applications de traitement de flux (B. Gedik et al. SPADE : le moteur de traitement de flux déclaratif du système S. ACM SIGMOD 2008.)
- RapidMind , une commercialisation de Sh (acquis par Intel en août 2009)
- TStreams, Laboratoire de recherche Hewlett-Packard de Cambridge
Les langues spécifiques au fournisseur incluent :
- Brook+ (implémentation matérielle optimisée de Brook pour AMD ) d' AMD / ATI
- CUDA (Compute Unified Device Architecture) de Nvidia
- Intel Ct - C pour le calcul à haut débit
- StreamC de Stream Processors, Inc. , une commercialisation des travaux Imagine menés à Stanford
Traitement événementiel
- Apama - un moteur de traitement d'événements complexes et de flux de données combiné, développé par Software AG
- Wallaroo
- Processeur de flux WSO2 par WSO2
- Apache NiFi
Traitement par lots de fichiers (émule certains aspects du traitement de flux réel, mais avec des performances généralement bien inférieures )Apache Kafka
Traitement continu du flux de l'opérateurApache Flink
Services de traitement de flux :
- Amazon Web Services - Kinesis
- Google Cloud - Flux de données
- Microsoft Azure - Analyse de flux
- Datastreams - Plateforme d'analyse de flux de données
- IBM Streams
- IBM Stream Analytics
- Eventador SQLStreamBuilder