Brevet FR2790847A1 — publié le 20000915

PROCEDE DE SAISIE GRAPHIQUE D'APPLICATION DE TRAITEMENT DE SIGNAL DANS UNE FORME HIERARCHISEE. La présente invention se rapporte à un procédé de saisie graphique d'application de traitement de signal dans une forme hiérarchisée, et en particulier à un procédé de spécification de caractéristiques de circuits de traitement de signal qui fait appel à une entrée graphique. On connaît de la demande de brevet français N 95 04175 déposée par la Société Thomson-CSF le 7 avril 1995, publiée le 11 octobre 1996 sous le NO 2 732 787, et délivrée le 16 mai 1997, un procédé de saisie graphique, appelé " ARRAY-OL " dans lequel il est décrit une transformation qui met en oeuvre une " transformation élémentaire >" ou " TE " et que la spécification (par saisie graphique) conduit à itérer cette TE jusqu'au garnissage complet du ou des tableaux résultats produits par la transformation. Dans la pratique, cette TE comporte une suite de traitements et ce procédé est limité quant à la spécification de ces traitements. Autrement dit, ce procédé ne propose à l'utilisateur qu'un seul niveau de spécification celui de la transformation. Une deuxième limitation apparaît dans le cas o l'utilisateur veut spécifier une application complète de traitement de signal. En effet, l'information précisant dans quel ordre s'enchaînent les transformations dans I'application est donnée indirectement par le fait que si un même tableau est tableau résultat d'une transformation Ti ainsi que le tableau opérande d'une autre transformation Tk, Tk se trouve à la suite de Ti. Ce procédé impose donc de nommer et de caractériser les tableaux et leurs dimensions associées au fur et à mesure qu'ils apparaissent dans les transformations. Cette limitation est supprimée en décrivant dans sa globalité une application complète. La suite des transformations composant une application peut par exemple être figurée par un graphe orienté dont les sommets reçoivent le nom des transformations et les arcs celui des tableaux échangés entre transformations comme représenté en figure 1. Ce procédé constitue ce qu'on appelle le " modèle global ", le procédé décrit dans le brevet cité ayant été appelé le " modèle local ". On citera à ce sujet, l'article publié au GRETSI 18-21 septembre 1995 pp 1029-1033. La désignation et la caractérisation des tableaux sont faits dans le modèle global. On citera également comme art antérieur le High Performance Fortran Language Spécification (HPFLS) développé par le Center of Research on Parallel Computation, Rice University Houston, USA, Mai 1993. Ce langage comporte en particulier des primitives spécifiques donnant des directives de placement au compilateur. Il possède donc l'inconvénient d'utiliser deux formalismes distincts, l'un pour décrire le placement et l'autre le traitement (calculs). Pour généraliser le procédé ARRAY-OL, I'invention propose un procédé de saisie graphique d'application de traitement de signal à l'aide 1O d'un calculateur numérique, dans lequel on part de données structurées en tableaux visualisés sous forme de repères cartésiens en mettant en oeuvre au moins une transformation sur ces données, on dispose en bibliothèque d'un jeu de transformations élémentaires TE, on établit pour chaque transformation, en entrée, au moins un tableau d'application opérande, en sortie au moins un tableau d'application résultat, on établit en entrée de chaque transformation élémentaire un motif opérande et en sortie un motif résultat, et on met en correspondance, pour chaque axe de coordonnées cartésiennes, au moins deux éléments du motif opérande et du tableau d'application opérande d'une part, du motif résultat et du tableau d'application résultat d'autre part, on utilise les relations affines caractéristiques des accès dans les tableaux en traitement de signal pour établir par itération, à l'aide d'un logiciel inclus dans l'outil graphique, à partir d'au moins deux correspondances, I'ensemble des accès nécessaires à l'exécution complète de la transformation considérée, principalement caractérisé en ce que l'application est structurée, c'est à dire que l'on entre graduellement dans les détails d'une application en définissant dans les niveaux supérieurs les grandes étapes de l'application et les volumes de données prises en compte et que l'on donne dans les niveaux inférieurs le détail des calculs effectués dans ces étapes, et que, moyennant des conventions pour le compilateur produisant le code d'exécution, on donne des directives de placement c'est à dire de découpe de l'application, pour que les tableaux effectivement traités à l'exécution soient de taille compatible avec la capacité de la mémoire centrale (ou encore de la mémoire cache) de la machine utilisée et pour que, dans le cas d'une machine parallèle, tous les processeurs soient occupés. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante, présentée à titre d'exemple non limitatif en regard des figures annexées qui représentent: - la figure 1, le principe graphique du modèle global tiré de l'art antérieur; - la figure 2, le principe graphique du modèle local tiré de l'art antérieur permettant de définir les notions et le vocabulaire utilisés dans la description de l'invention; - la figure 3, un exemple de création d'une TE du type FFT à 8 points; la figure 4, un exemple d'application complète sans hiérarchie; - la figure 5, un exemple d'application complète avec hiérarchie et - la figure 6, un exemple d'utilisation d'ARRAY-OL hiérarchique 1 5 pour diriger le placement de la figure 4. Le procédé selon l'invention, appelé " ARRAY-OL Hierarchique ", propose principalement la saisie de la description de l'exécution d'une application sur une machine dans une forme hiérarchique permettant, moyennant des conventions pour le compilateur produisant le code d'exécution, de donner simplement des directives de placement, c'est-àdire comment découper l'application, par exemple: - pour que les tableaux effectivement traités à l'exécution soient de taille compatible avec la capacité de la mémoire centrale (ou encore de la mémoire cache) de la machine utilisée; - pour que, dans le cas d'une machine parallèle, tous les processeurs soient occupés. On utilise notamment pour cela les modèles local et global. Le procédé selon l'invention propose aussi de: - créer à partir des TE de base initialement disponibles en bibliothèque, des TE plus complexes sous forme de " petites " applications et enrichir ainsi cette bibliothèque de TE dites description d'algorithmes de traitement de signal. Afin de faciliter la compréhension de l'invention, la description portera sur des exemples d'utilisation présentés dans l'ordre suivant: exemple de création d'une TE Hiérarchique à partir de TE de base existantes; - exemple d'écriture d'une application complète; 1 5 - exemple de saisie de l'application précédente sur une machine. Le principe de l'invention est basé sur le fait que: - Ou bien une TE Hiérarchique peut être décrite en ARRAY-OL comme une application à part entière dont les tableaux d'entrée et les tableaux de sortie sont respectivement les motifs d'entrée et les motifs de sortie de cette TE; Ou bien une application décrite en ARRAY-OL peut être reprise globalement en tant que TE dont les motifs d'entrée et de sortie seront respectivement les tableaux d'entrée et de sortie de cette application. Une hiérarchie de spécification est ainsi établie, o, par convention: utilisée à un certain niveau, une TE Hiérarchique peut être décrite comme une application au niveau immédiatement inférieur; - écrite à un certain niveau, une application peut être reprise en tant que TE Hiérarchique au niveau immédiatement supérieur. De manière connue, comme représenté en figure 2, la TE opère sur des ensembles restreints d'éléments appelés " motifs ". Selon l'art antérieur, pour spécifier une transformation, on sélectionne une TE en bibliothèque et on donne la taille de ses motifs: on définit ensuite comment les éléments de chacun des motifs se placent sur les éléments des tableaux par des exemples d' " L'exemple décrit maintenant est la création d'une TE Hiérarchique " FFT à 8 points ". En se reportant à la figure 3, le haut de la figure montre dans le modèle local une transformation ayant en entrée un tableau monodimensionnel (suite temporelle de 28 échantillons), et en sortie un tableau bidimensionnel contenant une suite temporelle de 5 vecteurs, chacun ayant pour éléments 8 fréquences. La TE (FFT) a un motif d'entrée monodimensionnel constitué par 8 échantillons d'entrée successifs, et un motif de sortie contenant les 8 échantillons " fréquence " élaborés par la TE à chacune de ses itérations. Les liens numérotés 1 et 2 définissent l'ajustage et ceux numérotés 1 et 3 le pavage, conformément au procédé antérieur. Le milieu de la figure montre dans le modèle global comment la TE FFT peut être vue comme une application constituée de 3 transformations (P1, P2, P3) correspondant aux 3 passes nécessaires pour une FFT 8 points (le graphe FFT est représenté en bas à gauche de la figure). Les tableaux en entrée et en sortie de cette application (INP1 et OUTP3) sont de taille identique aux deux motifs vus par la TE FFT. Le bas de la figure montre les trois appels au modèle local pour donner les détails des transformations P1, P2 et P3. Ces transformations mettent en oeuvre toutes les trois une TE de base PAP (le classique papillon de la FFT). Pour simplifier, on a ignoré tout au long de cette description les racines de l'unité - appelées coefficients W - pris en compte dans une véritable FFT. Les exemples 1 et 2 définissent partout des ajustages; 1, 3 et 4 des pavages. On décrit maintenant un exemple d'écriture d'une application complète de traitement de signal, en se référant aux figures 4 et 5 qui illustrent respectivement un exemple d'application écrite sans, puis avec, utilisation de la hiérarchie. L'application est représentée dans le modèle global en haut de la figure 4. Elle est composée de 3 transformations PHASE (filtrage), BF (beamforming), INT (intégration) détaillées dans 3 appels au modèle local (bas de la figure 4). Les TE mises en oeuvre sont CXMUL, DP et SUM. La figure 5 montre une façon de réexprimer la même application, mais en ARRAY-OL Hiérarchique. En haut de la figure, I'application est vue de façon macroscopique dans le modèle global, comme composée d'une transformation unique APPLI qui s'exécute en itérant une TE Hiérarchique ALL. Cette première étape du procédé permet de définir pour chaque récurrence de l'application le volume de données consommées par les dimensions du motif d'entrée de la TE ALL et produites par les dimensions du motif de sortie de la TE ALL, et comment ces volumes se disposent dans les tableaux traités par l'application. La TE ALL est ensuite décrite dans le modèle global comme une application composée de 2 transformations (PHBF et INT). Dans le modèle local, on voit que la transformation INT utilise la TE de base SUM et est désormais complètement spécifiée sans autre niveau de hiérarchie. La transformation PHBF dans le modèle local fait elle appel à une TE Hiérarchique FBF nécessitant l'ouverture d'un nouveau et dernier niveau de hiérarchie. Cette TE apparaît alors dans le modèle global de ce niveau comme composée de 2 tâches (PHASE puis BF) que l'on voit mettant respectivement en oeuvre dans le modèle local les TE de base C XMUL et DP. La description ci-dessous reprend l'application décrite sur la figure 4 et montre comment, moyennant des conventions connues du compilateur, la hiérarchie peut être utilisée-pour spécifier un placement sur une machine parallèle. La machine qui est considérée ici, est un exemple d'architecture parallèle simplifiée composée de 16 noeuds. Chaque noeud est un monoprocesseur doté d'une mémoire principale de 1 Mmot, ce qui amène à disposer de 16 Mmots pour la capacité mémoire de toute la machine. L'unité de calcul (CPU) du noeud travaille par ailleurs sur une " mémoire de travail privée " (comparable à un cache) de capacité limitée à quelques Kmots (ex 32 Kmots). La figure 6 fait apparaître la réécriture avec 4 niveaux de hiérarchie de l'application de la figure 4. Par ordre de hiérarchie décroissante, on appellera ici ces niveaux: - niveau " Machine ", - niveau " Noeud ">, niveau " Repet. Noeud ">, - et enfin niveau " Calcul ". A un niveau correspond un modèle global et des modèles locaux. Cette limitation à 4 niveaux découle de la configuration parallèle et de l'application prises ici comme exemple. Pour des cas plus courants (par exemple des Noeuds eux-mêmes parallèles, c'est-à-dire multiprocesseurs, ou encore des tailles de tableaux de l'application imposant des décompositions plus fines) des niveaux supplémentaires peuvent être nécessaires, mais ceci ne remet pas en cause le principe de l'invention tel qu'expliqué ici. Au niveau Machine, au lieu de traiter complètement les tableaux Array TC, puis Array R1CF..., pour produire in fine tout le tableau Array R2BF comme représenté sur la figure 4, le niveau Machine permet de spécifier comment les traitements complets sont découpés en traitements plus petits appliqués à des tableaux de taille compatible de la capacité mémoire de toute la machine. La découpe (représentée sur la figure 6) est spécifiée par la taille des motifs de la TE 2XALL apparaissant dans le modèle local de ce niveau. Le motif d'entrée de cette TE prend tous les capteurs C (256), mais ne prend pour chaque capteur qu'une tranche de 16.384 échantillons sur la dimension T (ce motif contient donc au total 4 Mega-Echantillons). Avec un tel motif d'entrée, il est possible de passer 2 fois dans toutes (d'o le choix du nom 2XALL de la TE) les transformations composant l'application de la figure 4, mais sans les terminer puisque dans le tableau final R2BF on produit une tranche de résultats garnissant tous les indices des dimensions F et B, mais seulement 2 indices de la dimension R2. La machine ne doit ainsi stocker que 4 Megamots ce qui est compatible de sa capacité mémoire, le tableau complet Array TC pouvant être, soit stocké sur un disque externe à la machine (cas d'une exécution non temps réel), soit être consommé au fur et à mesure de sa production (c'est-à-dire sans jamais se retrouver 3o intégralement en mémoire) dans le cas d'une exécution temps réel, les échantillons de Array TC étant alors fournis par des codeurs du type analogique/numérique par exemple. Cependant, d'autres considérations que la capacité mémoire, par exemple la latence (délai entre acquisition des échantillons et sortie des résultats), peuvent guider la découpe faite au niveau Machine. - Au niveau Noeud, la TE 2XALL s'y détaille dans le modèle global en une application composée des transformations SEGa et SEGb (SEG pour " segment ", la séquence complète des traitements ayant été segmentée en deux étapes SEGa et SEGb), les résultats intermédiaires entre ces deux étapes étant regroupés dans Array 16R1BF. Pour la TE NODEa détaillant dans le modèle local la transformation SEGa, la convention pour le compilateur est d'itérer autant de fois cette TE qu'il y a de noeuds dans la machine (ici 16). Dans cette convention, un noeud se voit confier l'itération de même indice que l'indice de ce noeud (la même convention s'appliquerait o10 à la TE NODEb détaillant SEGb, cette TE n'étant pas représentée sur la figure 6 par souci de simplification). Chaque itération de la TE NODEa consomme et produit des motifs représentant les éléments opérandes et résultats vus par un noeud (on rappelle que le contenu d'un motif, c'està- dire quels sont les éléments de tableau qui le composent, est régi par I'ajustage et le pavage). Dans cet exemple, au noeud 0 est confiée l'itération 0 de la TE NODEa. Ce noeud reçoit donc du tableau Array 16KTC tous les capteurs C, mais dans une tranche sur la dimension 16KT allant de l'indice 0 à 1023. Au noeud 1, I'itération 1 et la tranche sur la dimension 16KT vont de l'indice 1024 à 2047... Au niveau Repet. Noeud, dans le modèle global de ce niveau la TE NODEa du niveau précédent devient dans cet exemple une application composée de la seule transformation REPETa. La TE PHBF détaillant cette transformation va définir, par comparaison de la taille de son motif de sortie avec celle du tableau Array BF, le nombre de ses itérations, c'est-à-dire combien de fois le noeud doit répéter (d'o le nom choisi pour ce niveau) le traitement composant la TE PH_BF pour que la transformation REPETa soit complètement accomplie. Pour le compilateur, la convention consiste à 1) définir le volume de données (choisi compatible avec la capacité de la mémoire de travail), et donc aussi de calcul, pris en compte par le CPU du processeur à chaque répétition; ce volume découlant de la taille des motifs vus par la TE PH_BF. 2) indiquer la nécessité de faire des transferts entre la mémoire principale et la mémoire de travail du processeur, exactement dimensionnés par la taille des motifs vus par la TE PH_BF. Dans l'exemple décrit, le transfert de 16 Kmots de la mémoire principale vers la mémoire de travail est défini par la taille du motif d'entrée. On transfère ainsi 1 Kmots de la mémoire de travail vers la mémoire principale. Au niveau Calcul, la TE PH_TBF du niveau Repet. Noeud devient dans ce niveau une application décrivant effectivement un traitement de signal (les niveaux précédents ne spécifiaient que des distributions). Cette application apparaît dans le modèle global de ce niveau comme composée des transformations PHASE et BF. Celles-ci mettent respectivement en oeuvre dans le modèle local les TE de base CXMUL et DP. Pour le compilateur, le travail est ici de convertir cette application de traitement de signal formulée en ARRAY-OL non hiérarchique (on se trouve au dernier niveau), en un code exécutable par le CPU du noeud. Ce code est valable pour chacun des noeuds, la machine fonctionnant en mode SIMD (Single Instruction Multiple Data). REVENDICATIONS 1. Procédé de saisie graphique d'application de traitement de signal à l'aide d'un calculateur numérique, dans lequel on part de données structurées en tableaux visualisés sous forme de repères cartésiens (X, Y, Z, T) en mettant en oeuvre au moins une transformation sur ces données (F), on dispose en bibliothèque d'un jeu de transformations élémentaires TE, on établit pour chaque transformation, en entrée, au moins un tableau d'application opérande, en sortie au moins un tableau d'application résultat, on établit en entrée de chaque transformation élémentaire un motif opérande et en sortie un motif résultat, on met en correspondance, pour chaque axe O de coordonnées cartésiennes, au moins deux éléments du motif opérande et du tableau d'application opérande d'une part, du motif résultat et du tableau d'application résultat d'autre part, on utilise les relations affines caractéristiques des accès dans les tableaux en traitement de signal pour établir par itération, à l'aide d'un logiciel inclus dans l'outil graphique, à partir d'au moins deux correspondances, I'ensemble des accès nécessaires à l'exécution complète de la transformation considérée, caractérisé en ce que l'application est structurée, c'est à dire que l'on entre graduellement dans les détails d'une application en définissant dans les niveaux supérieurs les grandes étapes de l'application et les volumes de données prises en compte 2o et que l'on donne dans les niveaux inférieurs le détail des calculs effectués dans ces étapes, et que, moyennant des conventions pour le compilateur produisant le code d'exécution, on donne des directives de placement, c'est à dire de découpe de l'application, pour que les tableaux effectivement traités à l'exécution soient de taille compatible avec la capacité de la mémoire centrale (ou encore de la mémoire cache) de la machine utilisée et pour que, dans le cas d'une machine parallèle, tous les processeurs soient occupes.