Brevet FR3115901A1 — publié le 20220506

Système sur puce de sommation en arbre binaire de valeurs flottantes intermédiaires, une valeur flottante intermédiaire résultant d'un nombre respectif de valeurs flottantes sommées, comprenant : - un automate (1) à pile configuré pour réaliser des opérations de décalage, de réduction, de vidage et d'acceptation; et - un désambigüiseur (10) configuré pour mettre en œuvre un critère de désambiguïsation permettant de réaliser l'opération de décalage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai, et permettant, lorsque l'automate (1) traite l'information (eof) représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner, de réaliser l'opération de vidage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai. Figure pour l’abrégé : Fig. 1 Système sur puce de sommation en arbre binaire de valeurs flottantes L’invention porte sur un système sur puce de sommation en arbre binaire de valeurs flottantes. L'invention se situe dans le domaine de la réalisation de composants matériels pour l’accélération du calcul. Toute opération en virgule flottante dans un ordinateur comporte un risque d’erreur ou de perte de précision, si les opérateurs arithmétiques standards (IEE754) sont utilisés. Il en est ainsi d'une somme naïve ou itérative, effectuée par accumulation et itération sur un ensemble de nombres ou valeurs. L'écriture d'un nombre ou valeur en virgule flottante est une écriture sous la forme d'un signe, d'une matisse et d'une base avec un exposant. Par exemple, -1,3254=-13254 ×10 -4 (le signe est négatif, la matisse est 13254, la base est 10, mais souvent la base est 2 en informatique, et l'exposant est -4). Des algorithmes diminuant (ou supprimant) l’erreur existent, mais requièrent plus d’opérations ou tout du moins des opérations plus lentes. Le tri des données avant la somme (partitionner les données positives et négatives, puis sommer du plus petit au plus grand en valeur absolue chaque partition, et enfin additionner les deux valeurs positive et négative intermédiaires) permet de limiter l’erreur, au prix d’avoir à effectuer cette partition et ce tri. Un compromis proposé par l'état de l'art peut être une somme en arbre binaire, qui donne une erreur réduite quelle que soit la distribution des valeurs dans l’ensemble, comme cela est illustré dans le document Doc1: "Accuracy and Stability of Numerical Algorithms (2 ed)", SIAM, de Higham, Nicholas (2002). Mais l’état de l’art considère que cette somme en arbre binaire suppose la connaissance a priori du nombre de valeurs à additionner, comme dans le document Doc1, ainsi que dans le document Doc2: "Sums : A summation algorithm balancing accuracy with throughput.", de Barnaby Dalton, Amy Wang, Bob Blainey; SIMDizing Pairwise WPMVP '14: Proceedings of the 2014 Workshop on Programming models for SIMD/Vector processingFebruary 2014 Pages 65–70 https://doi.org/10.1145/2568058.2568070; et dans le document Doc3: "Implementation of a low round-off summation method" de Caprani, Ole; BIT Numerical Mathematics, Sept 1971. Les documents Doc1 et Doc2 décrivent un algorithme itératif de somme en arbre avec un automate et une pile. Cet algorithme nécessite une connaissance a priori du nombre d’éléments dans l’ensemble, ce qui constitue un problème lorsque cette taille n’est pas connue au début de la somme. Il est connu des techniques du domaine des langages algébriques, utilisées principalement pour le problème de l’appartenance d’une phrase à un langage, et la construction d’une structure abstraite sur une phrase, par exemple dans le document Doc4: "Parsing Techniques, A Practical Guide", de Dick Grune et Ceriel J.H. Jacobs, 2nd Edition, 2007, Springer, et dans le document Doc5: "Compilateurs: Principes, Techniques et Outils", de A. Aho, M. Lam, R. Sethi et J. Ullman, 2nd édition, 2007, Pearson. De telles approches ne sont pas utilisées habituellement pour le calcul, cependant elles constituent des éléments théoriques pour l’analyse de calculs. Un but de l'invention est de pallier les problèmes précédemment cités, et notamment de permettre de fusionner plusieurs sommes effectuées de manière indépendante sur une ou plusieurs unités de calcul distinctes en une seule. Les sous-totaux ainsi que la somme résultant de leurs fusions sont réalisés en arbre binaire avec un minimum d’opérations et de mémoire, d’un ensemble de flux de valeurs numériques prétraités et transmis en plusieurs lots sans connaissance de leur nombre dans chaque lot, du nombre d’éléments par lot qu’ils représentent et la taille de l’ensemble des valeurs traitées avant fusion du dernier flux. Aussi, il est proposé, selon un aspect de l'invention, un système sur puce de sommation en arbre binaire de valeurs flottantes intermédiaires, une valeur flottante intermédiaire résultant d'un nombre respectif de valeurs flottantes sommées, comprenant : - un automate à pile configuré pour réaliser des opérations de décalage, de réduction, de vidage et d'acceptation; - une entrée recevant en file, des valeurs flottantes intermédiaires et une information représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner par l'automate, chaque valeur flottante intermédiaire étant associée à un nombre respectif de valeurs flottantes sommées, ledit nombre respectif de valeurs flottantes sommées étant une puissance de 2 possédant un seul bit à 1 dans sa représentation binaire ou la valeur 2 0 =1 ; - un premier registre comprenant le nombre courant de valeurs flottantes total sommées; - un deuxième registre comprenant le nombre courant de valeurs flottantes sommées total, mis à jour par un vidage lorsque l'information représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate est reçue; - une mémoire de programmation de l'automate comprenant une table de transition de l'automate; - une mémoire comprenant une pile d'états de l'automate, de taille inférieure ou égale à une taille maximale; - une mémoire comprenant un tableau de sous-piles ou de files de résultats, de taille ladite taille maximale moins 1, des opérations effectuées par l'automate; - un troisième registre comprenant un index représentatif de la sous-pile ou de la file comprenant le résultat de la dernière opération effectuée par l'automate; - un additionneur en virgule flottante configuré pour additionner deux valeurs en virgule flottante et délivrer en sortie leur somme en virgule flottante; - un désambigüiseur configuré pour mettre en œuvre un critère de désambiguïsation permettant de réaliser l'opération de décalage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai, et permettant, lorsque l'automate traite l'information représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner, de réaliser l'opération de vidage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai; - un quatrième registre de sortie contenant le nombre final de valeurs flottantes total sommées, mis à jour par l’opération d’acceptation avec la valeur du premier registre; -une mémoire de transfert configurée pour permettre à un dispositif externe de retirer la valeur flottante calculée la plus ancienne, et décaler ainsi toutes les valeurs flottantes calculées selon le principe FIFO, et configurée pour mettre à disposition les valeurs flottantes calculées par l'automate lorsque l'information représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate est reçue. Un tel système permet de fusionner plusieurs sommes effectuées de manière indépendante sur une ou plusieurs unités de calcul distinctes en une seule. Les sous-totaux ainsi que la somme résultant de leurs fusions sont réalisées en arbre binaire avec un minimum d’opérations et de mémoire, d’un ensemble de flux de valeurs numériques prétraités et transmis en plusieurs lots sans connaissance de leur nombre dans chaque lot, du nombre d’éléments par lot qu’ils représentent et la taille de l’ensemble des valeurs traitées avant fusion du dernier flux. Selon un mode de réalisation, le système comprend un cinquième registre configuré pour être utilisé pour le calcul d'un résultat final à partir de la sommation des valeurs flottantes calculées mises à disposition dans la mémoire de transfert. Ainsi le dispositif peut être utilisé pour finaliser le calcul distribué sans avoir besoin de recourir à un autre dispositif afin d‘assurer la dernière étape dudit calcul. Les valeurs calculées par l'automate 1 peuvent se retrouver en entrée d'une autre instance du système de l'invention. Le système proposé permet de distribuer ce calcul sur plusieurs systèmes communicants entre eux : - Le dispositif peut effectuer un calcul sur des valeurs flottantes dites unitaires (valeur intermédiaire contenant une seule valeur 2 puissance 0); - Fusionner des calculs intermédiaires provenant des dispositifs concurrents en ne transmettant qu’un nombre réduit de valeurs flottantes (une valeur intermédiaire transmise porte l’information de 2 puissance N valeurs flottantes unitaires); - Réaliser en option le calcul final total. La sommation de valeurs flottantes par arbre binaire peut donc être distribuée sur différents dispositifs suivant diverses topologies. Dans un mode de réalisation, le système comprend un sixième registre comprenant le résultat final et configuré pour mettre à disposition ledit résultat final à un dispositif externe. Ainsi le dispositif peut mettre à disposition le résultat final. Dans un mode de réalisation, l'automate est configuré pour terminer sa somme lorsqu'il doit traiter l'information représentative de la fin de la réception de valeurs flottantes intermédiaires. Ainsi le système sait quand arrêter la sommation sans avoir a priori la connaissance du nombre de flottants à sommer. Selon un mode de réalisation, le critère de désambiguïsation est vrai si la profondeur totale ou nombre d'éléments du tableau de sous-piles ou files est supérieure au poids de Hamming du nombre de valeurs flottantes intermédiaires total reçues en entrée et déjà traitées par l'automate. En variante, le critère de désambiguïsation est vrai si la profondeur totale de la pile d’état moins un est supérieure au poids de Hamming du nombre de valeurs flottantes intermédiaires total reçues en entrée et déjà traitées par l'automate. L'utilisation d'un tel critère de désambiguïsation permet de rendre déterministe cette somme et d’obtenir l’évaluation de la somme en arbre binaire telle que recherchée. Dans un mode de réalisation, la table de transition est de type LR(1): une table d’un automate effectuant une reconnaissance de la suite de valeurs flottantes, lue de gauche à droite et avec un élément de pré-vision ("lookahead" en langue anglaise). Une telle table de transition dispose dans l’état de l’art d’outils et d’algorithmes pour sa génération, et, dans cette réalisation, est très petite. L'invention sera mieux comprise à l'étude de quelques modes de réalisation décrits à titre d'exemples nullement limitatifs et illustrés par le dessin annexé sur lequel: illustre schématiquement un système sur puce de sommation, selon un aspect de l'invention; illustre schématiquement une table de transition de l'automate du système de la , selon un aspect de l'invention; illustre schématiquement le fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention; et illustre schématiquement une étape de fonctionnement de l'automate du système des figures 1 et 2, selon un aspect de l'invention. Sur l'ensemble des figures, les éléments ayant des références identiques sont similaires. Sur la est illustré, selon un aspect de l'invention un système sur puce de sommation en arbre binaire de valeurs flottantes intermédiaires, une valeur flottante intermédiaire résultant d'un nombre respectif de valeurs flottantes sommées, comprenant : - un automate 1 à pile configuré pour réaliser des opérations de décalage, de réduction, de vidage et d'acceptation; - une entrée 2 recevant en file, des valeurs flottants intermédiaires et une information eof représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate 1, chaque valeur flottante intermédiaire étant associée à un nombre respectif de valeurs flottantes sommées, ledit nombre respectif de valeurs flottantes sommées étant une puissance de 2 possédant un seul bit à 1 dans sa représentation binaire ou la valeur 2 0 =1; - un premier registre 3 comprenant le nombre courant de valeurs flottantes total sommées; - un deuxième registre 4 comprenant le nombre courant de valeurs flottantes sommées total, mis à jour par un vidage lorsque l'information eof représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate 1 est reçue; - une mémoire 5 de programmation de l'automate 1 comprenant une table de transition 5a de l'automate 1; - une mémoire 6 comprenant une pile d'états 6a de l'automate 1, de taille inférieure ou égale à une taille maximale Tmax; - une mémoire 7 comprenant un tableau de sous-piles ou de files de résultats 7a, de taille ladite taille maximale Tmax moins 1, des opérations effectuées par l'automate 1; - un troisième registre 8 comprenant un index représentatif de la sous-pile ou de la file comprenant le résultat de la dernière opération effectuée par l'automate 1; - un additionneur 9 en virgule flottante configuré pour additionner deux valeurs en virgule flottante et délivrer en sortie leur somme en virgule flottante; - un désambigüiseur 10 configuré pour mettre en œuvre un critère de désambiguïsation permettant de réaliser l'opération de décalage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai, et permettant, lorsque l'automate 1 traite l'information eof représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner, de réaliser l'opération de vidage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai; - un quatrième registre 11 de sortie contenant le nombre final de valeurs flottantes total sommées, mis à jour par l’opération d’acceptation avec la valeur du premier registre; et - une mémoire 12 de transfert configurée pour permettre à un dispositif externe de retirer la valeur flottante calculée la plus ancienne, et décaler ainsi toutes les valeurs flottantes calculées selon le principe FIFO, et configurée pour mettre à disposition les valeurs flottantes calculées par l'automate 1 lorsque l'information eof représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate 1 est reçue. La présente invention repose sur le principe suivant concernant une somme en arbre et un flux de valeurs numériques sous forme de valeurs flottantes étendue à la fusion de résultats intermédiaires issus de sommes de sous-ensembles disjoints dudit flux, effectuées par des unités de calcul distinctes connectées par un réseau de communication. Les calculs intermédiaires peuvent être produits comme décrit dans le document FR 2001575, comme décrit dans la présente demande, ou de toute autre manière tant que les résultats desdits calculs peuvent être transmis à l’unité de fusion dans un format équivalent à celui décrit dans la suite de la description. Le principe de l’invention se résume comme suit. Une table de transition pour un automate à pile non-déterministe et un critère de levée de l’ambiguïté permettent de construire une somme en arbre binaire au fur et à mesure que les valeurs (issues de calculs intermédiaires ou non) sont reçues, et ceci sans connaître la taille de l’ensemble à traiter avant de recevoir le dernier élément, de manière déterministe et avec une mémoire utilisée comprenant : Le tableau de sous piles ou files pouvant contenir au maximum 2 x log 2 (nMax) arrondi à l'entier supérieur, nMax étant le nombre maximum de valeurs flottantes du flux pouvant être traitées par le système, en unité de mémoire pour représenter un nombre en virgule flottante, i.e. typiquement 32 bits pour un nombre flottant en simple précision et 64 bits pour un nombre flottant en double précision. La pile d'états de taille maximale égale à log2 (nMax) arrondi à l'entier supérieur + 1, nMax étant le nombre maximum de valeurs flottantes du flux pouvant être traitées par le système, d’entiers sur deux bits minimum. La définition d’un arbre d’additions binaires est la suivante: un nœud de l’arbre représente soit une addition et possède alors deux fils, soit une valeur numérique et n'a aucun fils. Il s’agit de la définition d’un arbre binaire strict ou localement complet. Une somme en arbre correspond à un arbre binaire d’additions de profondeur minimale. Si le nombre de valeurs dans la somme est une puissance de 2, alors cet arbre est un arbre binaire parfait. Si le nombre de valeurs n’est pas une puissance de 2, nous considérons l’arbre de profondeur minimale pour lequel la propriété suivante est respectée : chaque fils gauche est un arbre binaire parfait. L’arbre possède n-1 nœuds avec 2 fils, et donc correspond à n-1 additions pour obtenir le résultat final. La fusion est en mesure de construire un arbre binaire de profondeur minimale respectant la propriété que chaque fils gauche d’un nœud est un arbre binaire parfait si et seulement si les résultats intermédiaires reçus sont issus de la somme d’un nombre puissance de 2 de valeurs flottantes du flux. Les sommes par paire effectuées par le système de l'invention respectent cette contrainte. L'entrée 2 reçoit les valeurs une à une ou en bloc, et il est possible de retirer la valeur la plus ancienne reçue (et décaler ainsi toutes les valeurs reçues), suivant un principe de première arrivée, première sortie (FIFO pour "First In First Out" en langue anglaise). Une donnée eof en entrée peut indiquer que la transmission est terminée et plus aucune valeur ne sera ajoutée à l’entrée. Ceci peut être réalisé par un signal qui, s’il est activé, signifie que la transmission de valeurs se poursuit. S’il est désactivé, alors la transmission est terminée et plus aucune valeur ne sera ajoutée à l’entrée. Sur l'entrée 2 les valeurs intermédiaires arrivent une à une, et il est possible de retirer la valeur la plus ancienne reçue (et décaler ainsi toutes les valeurs reçues), suivant un principe de première arrivée, première sortie (FIFO) : - A chaque valeur flottante intermédiaire reçue, est associé le nombre de valeurs flottantes sommées; - Le nombre de valeurs flottantes représentées dans une valeur flottante intermédiaire est une puissance de 2 et possède un seul bit à 1 dans sa représentation binaire ; - Ce format d’entrée ne fixe aucune hypothèse sur le(s) format(s) d’échange utilisé(s) entre les différentes unités distribuées concourant à la sommation en arbre binaire. Le premier registre 3 comprend le nombre courant de valeurs flottantes total sommées. Le deuxième registre 4 comptabilise le nombre courant de valeurs flottantes total sommées, mis à jour par un vidage lorsque l'information eof représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate 1 est reçue. La mémoire 5 de programmation de l’automate, permet un accès en deux dimensions, et est suffisamment grande pour 3 lignes et 2 colonnes, numérotées à partir de 1, avec des éléments suffisants pour contenir 6 valeurs différentes par croisement ligne/colonne. Cette mémoire comprend la table de transition 5a de l'automate 1 ( ). La mémoire 6 comprend la pile d'états 6a, de taille maximale Tmax prédéterminée (Tmax=log 2 nMax arrondi à l'entier supérieur + 1, nMax étant le nombre maximum de valeurs flottantes du flux pouvant être traitées par le système), pouvant contenir trois valeurs différentes par élément de la pile, permettant la lecture du dernier élément, son retrait, et l’ajout d’un nouvel élément. La mémoire 7 comprend un tableau de sous-piles ou de files de résultats 7a, de taille ladite taille maximale Tmax moins 1, des opérations effectuées par l'automate 1. Le tableau de sous piles ou de files de résultats, de nombre de sous-piles ou files prédéterminée est : - indexé à partir de 1; - de nombre de sous-piles ou files de taille maximale log 2 nMax arrondi à l'entier supérieur, nMax étant le nombre maximum de valeurs flottantes du flux pouvant être traitées par le système; - chaque sous-pile ou file peut contenir 0, 1 ou 2 éléments; - chaque élément des sous-piles ou files peut contenir un nombre flottant; - de taille maximale 2 x log 2 (nMax) arrondi à l'entier supérieur nMax étant le nombre maximum de valeurs flottantes du flux pouvant être traitées par le système; - les opérations de retrait des deux derniers éléments, et d’ajout d’un élément, sont supportées; - de manière optionnelle, l’accès à la taille de la sous-pile ou file, pour des vérifications et tests; et - de manière optionnelle lorsque le critère de désambiguïsation est calculé à partir de la profondeur de la pile d'état, l’accès à la taille de la pile constituée par l’ensemble des sous piles ou files (somme des tailles des différentes sous piles ou files) est supporté. Le troisième registre 8 comprend un index représentatif de la sous-pile ou de la file comprenant le résultat de la dernière opération effectuée par l'automate 1, i.e. l’index de la sous-pile ou de la file sur laquelle a été empilée ou respectivement insérée la dernière valeur flottante intermédiaire. L'additionneur 9 en virgule flottante est configuré pour additionner deux nombres ou valeurs en virgule flottante et délivrer en sortie leur somme en virgule flottante, et est conforme à la norme IEE754, prenant deux valeurs en virgule flottante et retournant le résultat de l’addition de ces deux valeurs. Le désambigüiseur 10 configuré pour mettre en œuvre un critère de désambiguïsation permettant de réaliser l'opération de décalage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai, et permettant, lorsque l'automate 1 traite l'information eof représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner, de réaliser l'opération de vidage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai. Le quatrième registre 11 de sortie contient le nombre final de valeurs flottantes total sommées, mis à jour par l’opération d’acceptation avec la valeur du premier registre. Le cinquième registre 14 contient la somme finale des valeurs flottantes sommées. Il est possible, pour un dispositif extérieur, d'accéder à la mémoire de transfert 12 et d'y retirer la valeur flottante calculée par l'automate 1 la plus ancienne produite par le système (et décaler ainsi toutes les valeurs reçues), mises à disposition suivant un principe de premier arrivé, premier sorti (FIFO), les nombres flottants calculés par l'automate 1 sont insérés lorsque l'information eof représentative de la fin de la réception de nombres flottants intermédiaires à additionner par l'automate 1 est reçue. L'automate 1 à pile est capable de quatre opérations: décalage ("shift" en langue anglaise), réduction ("reduce" en langue anglaise), acceptation ("accept" en langue anglaise) et vidage ("dump" en langue anglaise). La table correspondante de l'automate 1 est illustrée sur la . L’automate peut donc effectuer ces quatre opérations différentes : - Décalage : l’automate 1 retire un couple (valeur, nombre) de 2, affecte à 8 le rang du seul bit à 1 de la représentation binaire de nombre, ajoute nombre à 3 et 4, insère valeur sur le sommet de la sous-pile ou file 8 du tableau 7a. L’automate 1 lit la valeur d’état sur la pile 6a, y ajoute 1 (avec un maximum de 3 pour le résultat) et insère cette valeur d’état Etat=min((Etat+1),3) sur le sommet de la pile 6a. - Réduction : l’automate retire deux états de la pile 6a, lit la valeur au sommet de la pile 6a après le retrait, y ajoute 1 (avec un maximum de 3 pour le résultat) et place cette valeur Etat=min((Etat+1),3) sur le sommet de la pile 6a. L’automate retire deux valeurs de la sous-pile ou file 8 (index) du tableau 7a, place ces deux valeurs sur les entrées de l’additionneur 9, active cet additionneur pour faire l’addition, ajoute 1 à l'index 8, et place le résultat de l’addition flottant sur la sous-pile ou file 8 du tableau 7a. - Vidage : - l’automate retire un état de la pile 6a, extrait le bit à 1 de plus faible poids du deuxième registre 4 et le place dans un registre temporaire nommé lsb, soustrait lsb au deuxième registre 4 et place le résultat dans le deuxième registre 4, affecte à un registre temporaire nommé lsbRange le rang du seul bit à 1 de la représentation binaire de lsb, retire une valeur de la sous-pile ou file (lsbRange) du tableau 7a et insère la valeur retirée dans la zone de transfert 12. - de manière optionnelle, l’automate peut placer sur les entrées de l’additionneur 9 la valeur retirée de la sous-pile ou file (lsbRange) du tableau 7a ainsi que la valeur d'un cinquième registre 14 optionnel utilisé pour le calcul du résultat final, activer cet additionneur 9 pour faire l’addition, et placer le résultat de l’addition flottante dans le cinquième registre 14. - Acceptation : - l’automate 1 retire un état de la pile 6a, affecte à un registre temporaire nommé lsbRange le rang du seul bit à 1 de la représentation binaire du deuxième registre 4, retire une valeur de la sous-pile ou file (lsbRange) du tableau 7a, insère la valeur retirée dans la zone de transfert 12. - de manière optionnelle, l’automate 1 peut placer sur les entrées de l’additionneur 9 la valeur retirée de la sous pile ou file (lsbRangelsbRange) du tableau 7a ainsi que la valeur du cinquième registre 14, activer cet additionneur 9 pour faire l’addition, et placer le résultat de l’addition flottante dans le cinquième registre 14. - L’automate 1 place la valeur contenue dans le premier registre 3 dans le quatrième registre 11 de sortie. - De manière optionnelle, l’automate 1 peut placer la valeur du cinquième registre 14 dans le sixième registre 15 de sortie. - L'automate 1 réinitialise en leur affectant la valeur 0 les premier et deuxième registres 3 et 4. - De manière optionnelle, l’automate 1 réinitialise en lui affectant la valeur flottante 0 le cinquième registre 14. Comme illustré sur la , la table de transition (ou transition) 5a possède l’organisation d’une table d’un automate classiquement nommé "décalage/réduction" ou "Shift+R/Reduce" en langue anglaise (par exemple dans "Compilateurs : Principes, Techniques et Outils, A. Aho, M. Lam, R. Sethi et J. Ullman, 2nd édition, 2007, Pearson", .37 page 231), avec pour colonnes une action sur valeur flottante intermédiaire F, une action sur fin de l’entrée eof, et pas de colonne Aller_à. Lorsque l'état de l'automate est 1, l'action sur une valeur flottante F est un Décalage. Lorsque la l'état de l'automate est 2, l'action sur une valeur flottante F est un Décalage et l'action sur fin de l’entrée eof est une Acceptation. Enfin, lorsque l'état de de l'automate est 3, l'action sur une valeur flottante F est un Décalage ou une Réduction, et l'action sur fin de l’entrée eof est un Vidage ou une Réduction. L’automate 1 respecte la structure donnée de "Compilateurs : Principes, Techniques et Outils, A. Aho, M. Lam, R. Sethi et J. Ullman, 2nd édition, 2007, Pearson" .36, page 230 de [5]… sous une forme optimisée compte tenu du petit nombre d’opérations à effectuer, explicitée en [Annexe 1]. Le test de désambiguïsation 10 est calculé de la manière suivante : Soit i le nombre de valeurs flottantes total traitées par l’automate 1 (c’est à dire que le dernier F absorbé (F est un jeton ou "token" en langue anglaise en entrée de l'automate à table) porte la i ème valeur flottante comptabilisée dans le premier registre 3) Soit p le nombre de bits à 1 dans la représentation binaire de i (c’est à dire le poids de Hamming de i) Soit d la profondeur ou taille totale du tableau de sous-piles (ou files) 7a calculée comme la somme des profondeurs ou tailles de chacune des sous-piles ou files (à noter que d est égal à la profondeur de la pile d’états 6a moins 1) Le test de désambiguïsation 10 est vrai si d est supérieure à p, sinon le test de désambiguïsation 10 est faux En variante, En utilisant la pile d’états 6a, le test de désambiguïsation 10 est vrai si la profondeur de la pile d’états 6a moins 1 est supérieure à p, sinon le test de désambiguïsation 10 est faux. L'objet de la présente invention, ne calcule pas nécessairement le résultat final de la somme en arbre binaire d’un nombre quelconque et non connu à priori de valeurs flottantes mais produit un ensemble de résultats intermédiaires pouvant : soit être transmis à une autre unité de fusion; soit être traités par un procédé en vue de produire le résultat final de la somme, ce traitement pouvant être intégré en option à l'invention. Les résultats intermédiaires peuvent être transmis à travers un flux (Stream) vers une autre unité en charge de leur fusion avec d’autres flux. Un tel flux peut être construit à partir du quatrième registre 11 et de la zone de transfert 12 comme suit : Transmission du nombre de valeurs flottantes traitées contenu dans le quatrième registre 11; Transmission dans l’ordre d’extraction des valeurs intermédiaires flottantes présentes dans la zone de transfert 12; Le nombre de valeurs flottantes à transmettre est égal au nombre de bits à 1 de la représentation binaire (poids de Hamming) du quatrième registre 11. La création de ce type de flux peut se résumer comme suit : - Transmettre sur le flux la valeur entière présente dans le quatrième registre 11; - Soit n le poids de Hamming du quatrième registre 11; - Répéter n fois : - Extraire une valeur intermédiaire flottante de la zone de transfert 12; - Transmettre sur le flux la valeur flottante ainsi extraite. De manière similaire la réception du flux décrit dans cette invention nécessite d’ajouter le traitement suivant : Extraire du flux la valeur entière représentant le nombre de valeurs flottantes comprises dans les valeurs intermédiaires à suivre et l’affecter à n; Tant que n est différent de 0: Soit i le nombre obtenu en ne conservant que le bit à 1 de poids faible de n (i = Isb(n)); Soit v la valeur intermédiaire flottante extraite du flux; Insérer sur l’entrée 2 de l’unité de calcul du couple (i,v) représentant une valeur intermédiaire à traiter par l'invention; Soustraire à n i et placer le résultat dans n (n = n - i). D’autres formats d’émission utilisant un flux (Stream) de communication peuvent être mis en place. Chacun d’eux nécessite d’adapter les traitements en entrée et en sortie de l'invention. Citons deux d’entre eux qui autorisent le traitement indépendant au fil de l’eau de chaque valeur intermédiaire : - Celle qui consiste à transmettre systématiquement avec chaque valeur intermédiaire le nombre de valeurs flottantes qu’elle porte; - Une version plus compacte de la précédente qui consiste à associer à chaque valeur intermédiaire, le rang du seul bit à 1 de la représentation binaire du nombre de valeurs flottantes qu’elle porte. Lorsque cette unité de calcul est en charge de produire un résultat final, il est nécessaire d’y adjoindre un traitement afin de sommer les valeurs intermédiaires issues de l'invention. Le traitement itératif suivant : - Soit r valeur flottante initialisée à 0; - Soit n le poids de Hamming du quatrième registre 11; - Répéter n fois - Extraire une valeur intermédiaire flottante f de la zone de transfert 12 - Ajouter à r la valeur flottante f extraite (r = r + f) Ce traitement itératif peut être intégré à l'invention en activant les étapes optionnelles décrites dans les actions de vidage et d'acceptation. Compte-tenu du nombre limité de valeurs flottantes restant à sommer, dont log 2 (5) + 1 est un majorant, l’erreur induite par cette dernière étape de calcul peut être minimisée par l’utilisation de procédés de l’état de l’art (ex : le tri préalable des valeurs) dont la complexité algorithmique ne s’applique qu’au nombre réduit des valeurs restant à traiter. La présente invention construit, au fur et à mesure de l’arrivée, dans un système distribué comprenant un nombre quelconque d’unités de calcul, des valeurs flottantes, de manière itérative, sans connaître à l’avance leur nombre. L’expression de tous les arbres de sommation binaires sur un ensemble de valeurs est la grammaire algébrique suivante : N → N N | F dans laquelle N est un nœud somme de ses deux fils ou une feuille F (contenant une valeur flottante) La compilation de cette grammaire par un générateur de parseurs GLR (par exemple Bison ou SmaCC) nous donne la table de transition d’un automate à pile non déterministe qui génère tous les arbres binaires de somme possibles depuis une entrée de valeurs flottantes traitées de gauche à droite avec un look-ahead de 1 élément, le calcul se terminant à la réception du dernier élément. Le critère de désambiguïsation assure que nous construisons uniquement l’arbre dont chaque fils gauche est un arbre binaire équilibré parfait, et ceci de manière déterministe. La littérature sur les parseurs rappelle que la table de transition de l’automate à pile non déterministe est une compilation de la stratégie top-down exprimée par la grammaire algébrique de la somme en arbre (cf "Parsing Techniques, A Practical Guide", Dick Grune et Ceriel J.H. Jacobs, 2nd Edition, 2007, Springer.", page vii), et donc, que la table de transition de l’automate est équivalente à cette dite grammaire. Les figures 3 à 13 détaillent le fonctionnement étape par étape le fonctionnement du système appliqué à la somme des sommes des ensembles et , avec et transmises au dispositif comme suit (valeur, nombre de valeurs sommées) : , comme illustré sur la . La figure 4 illustre l'absorption de avec une opération de Décalage, car on est à l'état 1 au sommet de la pile d'état 6a pour une valeur flottante F de la table de transition de l'automate 1 de la , qui implique le Décalage. La figure 5 illustre qui est placé dans la sous-pile ou file du tableau de sous-piles ou files 7a, l'index L 8 mis à 1, le troisième registre C 3 mis à 1, le deuxième registre D 4 mis à 1, et l'absorption de . La figure 6 illustre placé dans le tableau de sous-piles ou files 7a, l'index L 8 mis à 3, et 4 est ajouté au premier registre 3 C et au deuxième registre D 4, et l’état 3 empilé sur la pile d'états 6a (le haut de la pile est représenté en bas). Comme on est à l'état 3 en sommet de la pile d'états 6a, selon la table de transition de l'automate 1 de la figure 2, le choix est entre les opérations D (Décalage) et R (Réduction), et comme le test de désambigüisation 10 est faux, le choix est le (Décalage), et il y a absorption de . La figure 7 illustre placé dans le tableau de sous-piles ou files 7a en accord avec l'index L 8 mis à 1, et 1 ajouté au premier registre C 3 et au deuxième registre D 4. L’état 3 est empilé sur la pile d'états 6a. Comme on est à l'état 3 en sommet de la pile d'états 6a, selon la table de transition de l'automate 1 de la figure 2, le Choix est entre les opérations de D (Décalage) et R (Réduction), et comme le test de désambigüisation 10 est vrai, l’opération choisie est la R (Réduction) et donc somme de la sous-pile ou file d'index L 8 du tableau 7a contenant et . La figure 8 illustre somme de et par l'additionneur 9, dont le résultat est . L'index L du troisième registre 8 est incrémenté de 1 à 2, et est empilé sur la sous-pile ou file d'index L 8 du tableau de sous-piles ou files 7a. Deux valeurs sont dépilées de la pile d'états 6a, laissant 1 et 2 sur la pile d'états 6a, et la valeur au sommet de la pile d'état 6a + 1 (avec un maximum de 3) soit ici 2 + 1 = 3 est empilée sur la pile d'états 6a. La figure 9 illustre le choix entre les opérations D (Décalage) et R (Réduction), le test de désambigüisation 10 retourne faux, donc l'opération D (Décalage) est choisie et il y a absorption de . La figure 10 illustre la valeur 2 placée dans l'index L du troisième registre 8 et est placé sur la sous-pile ou file d'index L du tableau 7a. 3 est empilé sur la pile d'états 6a. La prochaine opération est D (Décalage) ou R (Réduction), et la réduction R est choisie. La figure 11 illustre la somme effectuée dans la sous-pile ou file d'index L du troisième registre 8 du tableau 7a, en l'espèce . L'index L du troisième registre 8 est incrémenté de 1 et est empilé, respectivement inséré, dans la sous-pile ou fils d'index L du troisième registre 8 du tableau 7a. Deux états sont dépilés de la pile d'états 6a et l'état 3 est empilé sur la pile d'états 6a. La prochaine opération est D (Décalage) ou R (Réduction), et la réduction R est choisie. La figure 12 illustre la somme effectuée dans la sous-pile ou file d'index L du troisième registre 8 du tableau 7a, en l'espèce . L'index L du troisième registre 8 est incrémenté de 1 et est empilé, respectivement inséré, dans la sous-pile ou file d'index L du troisième registre 8 du tableau 7a. Deux états sont dépilés de la pile d'états 6a et l'état 2 est empilé sur la pile d'états 6a. La prochaine opération est A (Acceptation) La figure 13 illustre l'acceptation A: est dépilé, respectivement inséré, de la sous-pile ou file d'index L du troisième registre 8 du tableau 7a et placé dans la zone de transfert 12. Le contenu du premier registre 3 est copié dans le quatrième registre 11 de sortie. Les premier et deuxième registres 3 et 4 sont remis à 0 et un état est dépilé de la pile d'états 6a. [Annexe1] Système sur puce de sommation en arbre binaire de valeurs flottantes intermédiaires, une valeur flottante intermédiaire résultant d'un nombre respectif de valeurs flottantes sommées, comprenant : - un automate (1) à pile configuré pour réaliser des opérations de décalage, de réduction, de vidage et d'acceptation; - une entrée (2) recevant en file, des valeurs flottantes intermédiaires (F) et une information (eof) représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner par l'automate (1), les valeurs flottantes intermédiaires étant associées à un nombre respectif de valeurs flottantes sommées, ledit nombre respectif de valeurs flottantes sommées étant une puissance de 2 possédant un seul bit à 1 dans sa représentation binaire ou la valeur 2 0 =1; - un premier registre (3) comprenant le nombre courant de valeurs flottantes total sommés; - un deuxième registre (4) comprenant le nombre courant de valeurs flottantes sommées total, mis à jour par un vidage lorsque l'information (eof) représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate (1) est reçue; - une mémoire (5) de programmation de l'automate (1) comprenant une table de transition (5a) de l'automate (1); - une mémoire (6) comprenant une pile d'états (6a) de l'automate (1), de taille inférieure ou égale à une taille maximale (Tmax); - une mémoire (7) comprenant un tableau (7a) de sous-piles ou de files de résultats, de taille ladite taille maximale (Tmax) moins 1, des opérations effectuées par l'automate (1); - un troisième registre (8) comprenant un index représentatif de la sous-pile ou de la file comprenant le résultat de la dernière opération effectuée par l'automate (1); - un additionneur (9) en virgule flottante configuré pour additionner deux valeurs en virgule flottante et délivrer en sortie leur somme en virgule flottante; - un désambigüiseur (10) configuré pour mettre en œuvre un critère de désambiguïsation permettant de réaliser l'opération de décalage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai, et permettant, lorsque l'automate (1) traite l'information (eof) représentative de la fin de la réception des valeurs flottantes intermédiaires à additionner, de réaliser l'opération de vidage lorsqu'il est faux et de réaliser l'opération de réduction lorsqu'il est vrai; - un quatrième registre (11) de sortie contenant le nombre final de valeurs flottantes total sommées, mis à jour par l’opération d’acceptation avec la valeur du premier registre; - une mémoire (12) de transfert configurée pour permettre à un dispositif externe de retirer la valeur flottante calculée la plus ancienne, et décaler ainsi toutes les valeurs flottantes calculées selon le principe FIFO, et configurée pour mettre à disposition les valeurs flottantes calculées par l'automate (1) lorsque l'information (eof) représentative de la fin de la réception de valeurs flottantes intermédiaires à additionner par l'automate (1) est reçue. Système selon la revendication 1, comprenant un cinquième registre (14) configuré pour être utilisé pour le calcul d’un résultat final à partir de la sommation des valeurs flottantes calculées mises à disposition dans la mémoire de transfert 12. Système selon la revendication 2, comprenant un sixième registre (15) comprenant le résultat final et configuré pour mettre à disposition ledit résultat final à un dispositif externe. Système selon l'une des revendications 2 ou 3, dans lequel l'automate (1) est configuré pour terminer sa somme lorsqu'il doit traiter l'information (eof) représentative de la fin de la réception de valeurs flottantes intermédiaires. Système selon l'une des revendications 1 à 4, dans lequel le critère de désambiguïsation est vrai si la profondeur totale ou nombre d'éléments (d) du tableau de sous-piles ou files (7a) est supérieure au poids de Hamming (p) du nombre (i) de valeurs flottantes intermédiaires total reçues en entrée (2) et déjà traitées par l'automate (1). Système selon l'une des revendications 1 à 4, dans lequel le critère de désambiguïsation est vrai si la profondeur totale (d) de la pile d’état (6a) moins 1 est supérieure au poids de Hamming (p) du nombre (i) de valeurs flottantes intermédiaires total reçues en entrée (2) et déjà traitées par l'automate (1). Système selon l'une des revendications précédentes, dans lequel la table de transition (5a) est de type LR(1).