FR 3093208 A1 20200828 FR 1902028 A 20190227 Description Titre de l'invention : Procédé de validation d'un système flots de données [0001] La présente invention concerne un procédé et un dispositif de validation d'un système flots de données, et plus particulièrement la vérification de la cohérence du système. Etat de la technique antérieure [0002] La présente invention s'applique à des systèmes dans lesquels des applications concrètes utilisent des fonctions d'interface prédéfinies pour s'échanger des données entre elles. En particulier, l'invention s'applique à tous les systèmes (ou applications) flots de données de types synchrones comportant des composants (ou tâches) appelés acteurs, connectés entre eux par des canaux (ou connexions) de communication unidirectionnels. Ces systèmes sont souvent utilisés pour décrire le comportement des applications de traitement du signal, car ils fournissent une sémantique d'exécution adéquate pour analyser leurs performances. Les critères les plus courants pour l'analyse des performances sont directement liés à l'optimisation du dimensionnement de la mémoire tampon, du débit ou de la latence. Une première étape dans la résolution de ces problèmes d'optimisation consiste à vérifier quelques propriétés, telles que l'existence d'une limite supérieure pour les tailles de mémoire tampon et l'absence de blocages. Ces propriétés sont avantageusement décidables dans un système flots de données en vérifiant des propriétés de cohérence et d'absence d'inter-blocage décrits plus loin. 100031 Un système flots de données est en général modélisé par un graphe de flot de données. Le graphe de llots de données décrit une structure de flots de données dans laquelle les acteurs sont représentés par des noeuds (ou sommets) et les canaux de communication par des arcs. Chaque acteur du graphe de flots de données dispose d'un ensemble de ports. Chaque port représente un point d'extrémité du canal de communication. Les acteurs ont généralement un comportement cyclique, appelé activation ou tir (firing en anglais) consistant à lire des données d'entrée à partir de leurs ports d'entrée, à exécuter leurs tâches et à placer des données de sortie sur leurs ports de sortie. Un tir ne peut avoir lieu que lorsque facteur dispose de suffisamment d'informations sur ses ports d'entrée. La quantité de données envoyée sur les ports de sortie ou reçue depuis les ports d'entrée est spécifiée par un nombre de jetons. Les taux de production (respectivement, consommation) représentent le nombre de jetons qu'un acteur peut envoyer (respectivement, recevoir) lorsqu'il fait un tir. On notera que dans un flot de données de type synchrone, les taux de consommation et de production sont 2 constants. [0004] Un système flots de données peut être planifié de manière statique, car chaque acteur du graphe de flots de données produit et utilise la même quantité de données à chaque fois qu'il fait un tir. De plus, un programme périodique peut être construit pour un système flots de données synchrones, étant donné que tous les taux de consommation et de production sont fixes. Dans un ordonnancement périodique valide, chaque acteur s'active (i.e. tire) un certain nombre de fois avant que le graphe ne revienne à son état initial, avec le même nombre de jetons initialement sur les canaux. [0005] Généralement, un vecteur de répétition valide est construit lors de la planification d'un système flots de données SDF. Le vecteur de répétition est un vecteur dont les composants sont des nombres entiers positifs, et dont la dimension est égale au nombre d'acteurs appartenant au graphe de flux de données. Chaque composant du vecteur correspond à un acteur et spécifie le nombre de tirs déclenchés par l'acteur pendant le programme périodique. On peut trouver plus d'un vecteur de répétition pour un graphe donné. Le vecteur de répétition minimale a la norme minimale et correspond à un ordonnancement périodique minimal. On notera que le vecteur de répétition est utilisé pour vérifier la validité du système flots de données. [0006] En effet, pour trouver une planification périodique valide d'un système flots de données, le graphe de flots de données modélisant le système doit vérifier des propriétés de cohérence (consistcncy, en anglais) et d'absence d'inter-blocage (deadlock, en anglais). La propriété de cohérence concerne le fait que lors des périodes d'exécution, les jetons dans un graphe de flots de données ne s'accumulent pas sur les canaux unidirectionnels. Il est connu [2] que l'existence d'un vecteur de répétition non nul est une condition nécessaire à la cohérence d'un graphe de flots de données, c'est-à-dire qu'elle ait un ordonnancement périodique valide. Par ailleurs, la propriété d'absence d'inter-blocage (appelée également, vivacité) signifie que les acteurs ont suffisamment de jetons sur leurs entrées pour continuer à faire des tirs. On notera que les propriétés de cohérence et d'absence d'inter-blocage sont indépendantes. [0007] Les Figs. 1A-1C illustrent des exemples de graphes de flots de données à deux acteurs montrant les propriétés de cohérence et d'absence d'inter-blocage, selon l'état de l'art. [0008] L'exemple de la Fig. 1A illustre un graphe cohérent mais présentant un inter-blocage. En effet, ce graphe G1 est cohérent car aucun jeton ne s'accumule sur les canaux. L'acteur A produit un jeton, qui est consommé par l'acteur B, ensuite, l'acteur B tire et produit un jeton, lequel est consommé pat- l'acteur A, et ainsi de suite. Le vecteur de répétition correspondant au graphe G1 est X1=(1 1), ce qui signifie que chacun des acteurs A et B s'active (tire) une fois avant que le graphe G1 ne revienne à son état initial. Toutefois, ce graphe G1 n'est pas exempt d'inter-blocage car il n'y a pas de 3 jeton initial sur les canaux, cc qui signifie que ni l'acteur A ni l'acteur B ne peuvent commencer à tirer. [0009] L'exemple de la Fig. 1B illustre un graphe 02 non-cohérent mais présentant une absence d'inter-blocage. Le canal unidirectionnel allant de B vers A contient un jeton initial. L'acteur A consomme ce jeton initial et produit un autre jeton, qui est à son tour consommé par Facteur B. Ensuite, l'acteur B produit deux jetons par tir, de sorte que l'acteur A ait suffisamment de jetons sur ses entrées pour continuer à tirer. Toutefois, les jetons continueront à s'accumuler sur les ports d'entrées de l'acteur A car le rythme de consommation par ce dernier n'est pas aussi rapide que celui de production par l'acteur B. Dans cc cas, aucun vecteur de répétition ne peut être trouvé pour ce graphe 02, cc qui signifie qu'il n'est pas cohérent. [0010] En contraste, l'exemple de la Fig. 1C illustre un graphe 03 satisfaisant à la fois la propriété de cohérence et de vivacité (i.e. absence d'inter-blocage). En effet, l'acteur A consomme les deux jetons initiaux sur son port d'entrée et produit un jeton sur le port de sortie. Ensuite, l'acteur B consomme un jeton et produit deux jetons sur son port de sortie, ce qui signifie que le graphe 03 revient dans son état initial. Le vecteur de répétition correspondant au graphe 03 est alors X3=(1 1). L'existence d'un tel vecteur de répétition (non nul) signifie que le graphe G3 est cohérent. Par ailleurs, une façon de vérifier l'absence d'inter-blocage, comme proposé dans [12], consiste à déclencher chaque noeud le nombre de fois spécifié par le vecteur de répétition. Si le graphe de flots de données n'a pas d'inter-blocage pendant ce test, alors il est libre de tout inter-blocage. [0011] La propriété de cohérence est importante car si un vecteur de répétition ne peut pas être trouvé pour un graphe de flots de données donné, alors tout système flots de données correspondant à ce graphe se retrouvera soit dans une impasse, soit dans des tailles de mémoires tampons sans limite supérieure. [0012] Actuellement, le formalisme généralement utilisé dans l'état de l'art pour la véri- fication de la cohérence est basé sur l'extraction d'une matrice dite « matrice de topologie » du graphe de flux de données. Ce formalisme est décrit par Lee et Messerschmitt [1, 2] pour les graphes de flots de données synchrones. La matrice de topologie décrit la manière dont le graphe est connecté et les quantités d'informations que chaque acteur dans le graphe peut envoyer ou recevoir à chaque tir. La matrice de topologie est généralement désignée par la lettre gamma F. Chaque acteur du graphe de flots de données possède une colonne dans la matrice de topologie F et chaque canal (connexion) est affecté à une ligne. Ainsi, la (i, j)ènc entrée de la matrice de topologie F correspond au taux de production ou de consommation du noeud j sur le canal i. Par convention, les taux de production sont désignés par des nombres positifs tandis que les taux de consommation sont désignés par des nombres négatifs. 100131 Selon la définition ci-dessus, les matrices de topologie FI, L2 et L3 correspondant aux graphes Gl, 02 et 03 illustrés sur les Figs. 1A-1C sont : 1Math.11 F2 = » [0014] Un vecteur de répétition non nul, ici noté X, peut éventuellement être trouvé en résolvant l'équation matricielle suivante : [Math.21 r'x=o [0015] L'existence d'un vecteur de répétition X non nul est une condition nécessaire pour l'existence d'un ordonnancement périodique dans lequel les tailles de mémoire tampon restent limitées La résolution de l'équation matricielle pour les graphes 01, 02 et 03 donne les vecteurs indiqués ci-dessus : X1,(1 1), X2=(0 0) et X3=(1 1). [0016] Ainsi, pour pouvoir vérifier s'il existe un vecteur de répétition X non nul, il est au- paravant nécessaire de construire entièrement le graphe de flots de données. En d'autres termes, il faut que le système flot de données soit dans sa [mine finale avant de pouvoir vérifier si le système est cohérent ou non. [0017] Cette méthode est très couteuse en temps et en calcul et au cas où le système flot de données a été jugé non-cohérent, la méthode ne permet pas de détecter les éléments responsables de cette incohérence. De plus, si on ajoute une nouvelle tâche ou acteur à un système flot de données déjà cohérent, on est obligé à nouveau de reconsidérer tout le système flot de données ainsi modifié avant de décider si ce dernier reste cohérent. 10018] L'objet de la présente invention est, par conséquent, de proposer un procédé de va- lidation d'un système flots de données de type synchrones remédiant aux inconvénients précités, en particulier, en permettant une vérification rapide et simple de la cohérence au cas où des nouvelles tâches sont ajoutées ainsi qu'en permettant l'identification des éléments non-cohérents. Présentation de l'invention 100191 La présente invention concerne un procédé de validation d'un système flots de données représenté par un graphe de Bots de données comportant des acteurs présentant des taux de production et des taux de consommation déterminés, ledit procédé étant. caractérisé par une vérification incrémentielle dans laquelle la cohérence d'une connexion unidirectionnelle courante reliant une première partie courante du graphe de flots de données à une deuxième partie courante du graphe de flots de données est localement vérifiée à chaque incrément. 100201 Ce procédé permet au graphe de flots de données d'avoir une topologie flexible dans laquelle des acteurs (ou connexions) peuvent être supprimés, ajoutés ou modifiés.Avantageusement, le procédé comporte les étapes suivantes : -définir des acteurs d'origine et d'arrivée reliés par ladite connexion unidirectionnelle courante, les acteurs d'origine et d'arrivée appartenant auxditcs première et deuxième parties courantes du graphe de flots de données respectivement, les acteurs d'origine et d'arrivée étant définis par des composants d'origine x, et d'arrivée x, respectivement pouvant appartenir à un unique vecteur courant de répétition ou à deux vecteurs courants de répétition représentatif(s) desdites première et deuxième parties courantes du graphe de flots de données, -attribuer à ladite connexion unidirectionnelle courante un taux dc production r, relatif à l'acteur d'origine et un taux de consommation ri relatif à l'acteur d'arrivée, -vérifier un indicateur de cohérence locale de ladite connexion unidirectionnelle courante, ledit indicateur de cohérence locale examinant si le produit dudit taux de production ri fois ledit composant d'origine xi est égal au produit dudit taux de consommation ri fois ledit composant d'arrivée xi, -définir un vecteur courant dc répétition résultant représentatif desdites première et deuxième parties courantes du graphe de flots de données. [0021] Ainsi, la cohérence peut être vérifiée localement lors de la construction du graphe flots de données ou lors de l'ajout d'une nouvelle connexion sans reconsidérer tout le graphe de flots de données. En effet, la cohérence de la nouvelle connexion peut être évaluée en prenant en compte l'état du graphe précédent. [0022] Avantageusement, au cas où ladite connexion unidirectionnelle courante vérifie l'indicateur de cohérence locale, ledit procédé comporte les étapes suivantes : -si les acteurs d'origine et d'an-ivée sont associés à deux vecteurs courants de répétitions distincts, dits vecteurs de répétition d'oiigine et d'arrivée, alors on construit le vecteur courant de répétition résultant en concaténant lesdits vecteurs de répétions d'origine et d'arrivée, et -si les acteurs d'origine et d'an-ivée sont associés à un unique vecteur courant de répétition, alors le vecteur courant de répétition résultant est égal audit unique vecteur courant de répétition. [0023] Ainsi, à chaque fois qu'une nouvelle connexion est ajoutée, on peut directement savoir si cette nouvelle connexion est cohérente ou pas. [0024] Avantageusement, au cas où ladite connexion unidirectionnelle courante ne vérifie pas l'indicateur de cohérence locale ledit procédé comporte les étapes suivantes : -si les acteurs d'origine et d'an-ivée sont associés à deux vecteurs courants de répétitions distincts, dits vecteurs de répétition d'origine et d'arrivée, alors on calcule deux nombres naturels, dits coefficient de production c, et coefficient de consommation ci vérifiant une égalité entre d'une part le produit dudit coefficient de production c1 fois 6 ledit taux de production ri fois ledit composant d'origine xi et d'autre part, le produit dudit coefficient de consommation ci fois ledit taux de consommation ri fois ledit composant d'arrivée xi, et on construit le vecteur courant de répétition résultant en concaténant le vecteur de répétition d'origine après l'avoir multiplié par le coefficient de production ci avec le vecteur de répétition d'arrivée après l'avoir multiplié par le coefficient de consommation ci, et -si les acteurs d'origine et d'arrivée sont associés à un unique vecteur courant de répétition, alors la connexion unidirectionnelle courante est identifiée comme étant non cohérente. [0025] Ainsi, ce procédé permet d'identifier quel élément du système flots de données est incohérent. [0026] Avantageusement, les coefficients de production ci et de consommation ci sont donnés par les équations suivantes : [Math.3] où Avantageusement, le procédé comporte une opération (l'addition d'une nouvelle connexion unidirectionnelle entre des première et deuxième parties courantes du graphe de flots de données. Ainsi, le procédé peut être efficacement utilisé pour des systèmes flots de données modulaires. Avantageusement, le procédé comporte une opération de suppression d'une connexion unidirectionnelle du graphe de flots de données représenté par un unique vecteur de répétition, dit vecteur de répétition initial, selon les étapes suivantes : -si le graphe de flots de données se divise en des premier et deuxième sous-graphes de flots de données après la suppression de ladite connexion unidirectionnelle, alors on construit un premier vecteur de répétition en regroupant les composants dudit vecteur de répétition initial relatifs audit premier sous-graphe de flots de données, et on construit un deuxième vecteur de répétition en regroupant les composants du vecteur de répétition initial relatifs audit deuxième sous-graphe de flots de données, et -si le graphe reste connexe après la suppression de ladite connexion unidirectionnelle, alors on ne modifie pas ledit vecteur de répétition initial. Avantageusement, le procédé comporte une opération de modification d'une connexion unidirectionnelle, selon les étapes suivantes: -attribuer des nouveaux taux de production r'; et. de consommation r'i relatifs aux 7 acteurs d'origine et d'arrivée reliés par ladite connexion unidirectionnelle, -appliquer l'opération de suppression d'une connexion unidirectionnelle, et -appliquer l'opération d'addition d'une connexion unidirectionnelle. Avantageusement, le procédé comporte la vérification de la cohérence du graphe de flots de données lors de sa construction en attribuant à chaque acteur d'arrivée additionnel un vecteur additionnel de répétition dont son unique composant xi est égal à 1, ledit acteur d'arrivée additionnel étant relié par ladite connexion unidirectionnelle courante à un acteur d'origine appartenant audit graphe courant de flots de données en construction. La présente invention vise également un système de traitement de signal numérique conçu en utilisant le procédé de validation selon l'une quelconque des caractéristiques précédentes, ledit système de traitement étant modélisé par un système flots de données comportant des acteurs connectés entre eux par des connexions de communications unidirectionnelles, chaque acteur étant configure pour recevoir des données d'entrées et pour délivrer des données de sortie. Avantageusement, ledit système est un système parmi l'un quelconque des systèmes de traitement suivants : système d'imagerie médicale, système de vision par ordinateur, système de codage et compression vidéo, système de conversion d'une fréquence d'échantillonnage audio, système de conception d'outils pour les systèmes de communication sans fil, système d'amélioration de la parole multicanal, système embarqué. La présente invention vise aussi un dispositif de validation d'un système flots de données représenté par un graphe de flots de données comportant des acteurs présentant des taux de production et des taux de consommation déterminés, ledit système comportant : -un module d'acquisition configure pour acquérir des données concernant des première et deuxième parties courantes du graphe de flots de données, et -un module de supervision configure pour vérifier de manière incrémentielle la cohérence dudit système flots de données en vérifiant à chaque incrément la cohérence locale d'une connexion unidirectionnelle courante reliant la première partie courante du graphe de flots de données à la deuxième partie courante du graphe de flots de données. Brève description des figures [0027] D'autres particularités et avantages du dispositif et du procédé selon l'invention res- sortiront mieux à la lecture de la description faite ci-après, à titre indicatif mais non limitatif, en référence aux dessins annexés sur lesquels : [0028] [fig.1A] [0029] [fig.113] 8 100301 Ifig.1CI illustrent des exemples de graphes flots de données à deux acteurs montrant les propriétés de cohérence et d'absence d'inter-blocage, selon l'état de l'art ; [0031] [fig.2] illustre de manière schématique un dispositif et un procédé de validation d'un système flots de données, selon un mode de réalisation de l'invention ; [0032] [fig.3] est un graphe flots de données illustrant la vérification de cohérence d'une connexion, selon un mode de réalisation de la présente invention ; [0033] [fig.4] est un organigramme illustrant les étapes d'un procédé de validation d'un système flots de données, selon un mode de réalisation préféré de l'invention ; [0034] [fig.5] illustre de manière schématique la construction d'un graphe flots de données selon le procédé de la Fig. 4; [0035] [fig.6] illustre de manière schématique la connexion de deux graphes distincts, selon le procédé de la présente invention ; [0036] [fig.7] est un organigramme illustrant les étapes d'un procédé de validation comportant une opération de suppression, selon un mode de réalisation préféré de l'invention ; [0037] [fig.8] un organigramme illustrant les étapes d'un procédé de validation comportant une opération de modification, selon un mode de réalisation préféré de l'invention ; [0038] [fig.9A] et [0039] [fig.913] illustrent à titre d'exemple la vérification de cohérence dans un système de flots de données modélisant un dispositif d'amélioration de la parole multicanal, selon la présente invention. Description détaillée de l'invention [0040] Le principe de la présente invention est de vérifier la cohérence d'un système flots de données de manière incrémentielle et locale. La présente invention s'intéresse en particulier, aux systèmes flots de données dont les acteurs ont des taux de consommation et de production déterminés (i.e. définis ou quantifiables). Par exemple, le système peut être un système flots de données synchrones de type SDF (Synchronous dataflow) ou un système flots de données synchrones et cycliques. 9 [0041] La Fig. 2 illustre de manière schématique un dispositif et un procédé de validation d'un système flots de données, selon un mode de réalisation de l'invention. [0042] Le dispositif de validation 1 est mis en oeuvre par des moyens matériels comportant une machine de traitement de l'information tel un calculateur ou ordinateur 3 comportant un microprocesseur 5 et des mémoires 7. Le microprocesseur 5 est configure pour exécuter un ou plusieurs programmes d'ordinateur comprenant des instructions de code de programme, stockés dans les mémoires 7 de l'ordinateur et conçus pour mettre en oeuvre la validation d'un système de flots de données. [0043] Conformément à l'invention, le dispositif de validation 1 comporte un module d'acquisition 9 et un module de supervision 11. [0044] Le module d'acquisition 9 est configure pour acquérir des données concernant un graphe courant de flots de données et plus particulièrement, des données concernant des première et deuxième parties courantes du graphe de flots de données ainsi qu'une connexion courante entre ces deux parties. Par première ou deuxième partie courante d'un graphe de flots de données, on entend une partie du graphe comportant au moins un seul acteur. [0045] De manière générale, un graphe de flots de données comporte des acteurs indé- pendants s'échangeant entre eux des informations quantifiables, à travers des connexions (i.e. canaux) de communications unidirectionnelles. Les acteurs peuvent être des entités logicielles (par exemple, des applications) et/ou matérielles (par exemple, des capteurs, caméras, sondes, microprocesseurs, etc.). Les acteurs sont représentés par des noeuds (ou sommets) et les connexions de communication par des arcs. Chaque acteur est configuré pour attendre d'avoir reçu une quantité de données spécifiée sur ses ports d'entrée dans le but de consommer cette quantité de données, d'effectuer (ou pas) un traitement de ces données et de produire une quantité de données spécifiée sur ses ports de sortie à destination de nouveaux acteurs, et chacun répétant ce comportement indéfiniment. Le processus cyclique de consommation/ traitement/émission est communément appelé une activation ou un tir. [0046] Dans des flots de données synchrones, tous les acteurs ont des taux de consommation et de production déterminés (quantifiables), et ces taux sont connus lors de la construction du graphe de flots de données. Les noeuds du graphe de flots de données peuvent être 'nappés sur différentes unités de calcul, afin que les tâches puissent être exécutées dans un certain ordre. Cette procédure s'appelle la planification qui peut être effectuée de manière statique (au moment de la compilation) ou dynamique (au moment de l'exécution). [0047] Le module de supervision 11 est configuré pour vérifier de manière incrémentielle la cohérence du système flots de données en vérifiant à chaque incrément la cohérence locale de la connexion unidirectionnelle courante reliant la première partie courante du graphe de flots de données à la deuxième partie courante du graphe de flots de données. [0048] Par ailleurs, on notera que l'absence d'inter-blocage peut être vérifiée en déclenchant chaque noeud le nombre de fois spécifié par le vecteur de répétition. Si aucun d'inter-blocage n'a été décelé pendant ce test, le graphe de flots de données est alors libre de tout blocage. [0049] Dans la suite, on note X le vecteur de répétition et par xt le renie composant du vecteur de répétition X. On considère par convention que lorsqu'un acteur est créé, un vecteur de répétition lui est associé ne comportant qu'un seul composant dont la valeur est égale à un. [0050] Par ailleurs, la vérification locale et incrémentielle de la cohérence selon l'invention se base sur la proposition suivante et son corollaire ainsi que sur leurs implications. [0051] Proposition : Si un graphe G de flots de données est cohérent et a un vecteur de ré- pétition valide X. alors kX est également un vecteur de répétition valide pour tout nombre naturel k (i.e. k e Z). [0052] Corollaire : Considérons un graphe de flots de données cohérent avec n acteurs et un vecteur de répétition valide X = [xi x2... x]. Supposons qu'en raison d'une contrainte de conception supplémentaire, le Vine composant du vecteur X doit être modifié. On note x"i la nouvelle valeur du ième composant du vecteur X. Alors, afin de préserver la cohérence du graphe de flux de données, les valeurs de tous les autres composants xi du vecteur X (i.e. xi, j = 1... n, et j # n) doivent être multipliées par x'ti / xi. [0053] Ainsi, lorsqu'une nouvelle connexion unidirectionnelle est créée entre deux acteurs ai et ai ayant des taux de production et de consommation ri et ri respectivement et étant représentés par des composants xi et xi respectivement, la nouvelle connexion unidirectionnelle est considérée comme étant cohérente si l'on peut trouver deux nombres naturels ci et ci (i.e. ci e Z et ci e Z), dits coefficients de production ci et de consommation ci, satisfaisant une propriété de cohérence. Cette propriété est une égalité entre d'une part le produit du coefficient de production ci fois le taux de production ri fois le composant d'oiigine xi et d'autre part, le produit du coefficient de consommation ci fois le taux de consommation ri fois le composant d'arrivée xi selon l'équation suivante : [Math.4] Ct 2( = (3) [0054] En effet, la Fig. 3 est un graphe flots de données illustrant la vérification de cohérence d'une connexion, selon l'équation (3) ci-dessus. [0055] Plus particulièrement, l'exemple de la Fig. 3 illustre un graphe 04 résultant de la mo- dification du graphe cohérent 03 de la Fig. 1C en lui ajoutant un nouvel acteur C et 11 une nouvelle connexion entre l'acteur B et l'acteur C. On notera que cette modification peut être vue soit comme une modification du graphe initial 03 illustré dans la Fig. 1C, soit comme une étape parmi d'autres dans la construction itérative du graphe 04 de la Fig. 3. Dans les deux cas, la modification consiste à ajouter la nouvelle connexion entre l'acteur B et l'acteur C. Soient X,J et Xc les vecteurs de répétition du graphe initial G3 et de l'acteur C respectivement. Dans ce cas, le second composant x,, du vecteur de répétition Xc associé au graphe initial G3 est égal à 1 (i.e. XB =1) et par convention le seul composant xc du vecteur de répétition Xc de l'acteur C est égal à 1 (i.e. xc=1). Sur cette nouvelle connexion, l'acteur B produit un jeton, ce qui signifie ri, =1, et l'acteur C consomme deux jetons, ce qui signifie rc =2. On a vu précédemment que le vecteur de répétition Xc, correspondant au graphe initial G3 est XG=(1 1). Afin de calculer le nouveau vecteur de répétition X' G résultant de la connexion, il suffit de trouver deux nombres naturels c, et c, vérifiant l'équation (3) ci-dessus. En remplaçant les variables connues dans l'équation (3), on obtient c1=2c2. Par ailleurs, on peut déterminer un vecteur de répétition minimal, en choisissant c1=2 et c2=1. Ainsi, les valeurs correspondant aux acteurs B et C dans le nouveau vecteur de répétition X'c, seront respectivement es=c,x,, =2 et x*c=c,xc =1. Dans ce cas, la propriété de cohérence est préservée par la proposition énoncée ci-dessus. En outre, en conformité avec le corollaire ci-dessus, le composant du vecteur de répétition correspondant à l'acteur A doit également être changé. Ainsi, après la connexion des acteurs B et C, le nouveau vecteur de répétition X'r, du graphe de la Fig. 3 est X'c,=(2 2 1). [0056] On remarque qu'il n'est nullement nécessaire de calculer une nouvelle matrice de topologie F pour le graphe 04 de la Fig. 3. 11 suffisait seulement de trouver les coefficients cl et c, et ensuite d'appliquer le corolaire ci-dessus. Néanmoins, on remarque que le nouveau vecteur de répétition X'c, =(2 2 1) trouvé ci-dessus satisfait à l'équation (2) avec une matrice de topologie donnée par : Nath.51 [0057] Dans ce qui suit, on montre unc manière de choisir les coefficients é et c, de manière à satisfaire l'équation (3) pour le cas général dans lequel deux acteurs, dits acteur d'origine a, de composant x, ct acteur d'arrivée ai de composant x, sont connectés. En particulier, en choisissant ci = x, / ri et ci = x / fi et en les remplaçant dans l'équation (3), 011 obtient : 12 [Math.6] [0058] Cette équation est bien entendu toujours vraie. Toutefois, ce choix de paramètres ne garantit pas des valeurs entières pour les coefficients ci et ci. Alors, pour que ces coefficients soient entiers, on multiplie l'égalité (5) ci-dessus par le plus petit commun multiplicateur ppcm des taux de production ri et de consommation r; et on divise par le plus grand commun diviseur pged des composants xi et x; des acteurs d'origine et d'arrivée respectivement. Ceci donne les coefficients de production ci et de consommation ci, suivants : [Math.71 d r, [0059] Les coefficients ci et ci selon l'équation (6) satisfont la condition de cohérence de l'équation (3). [0060] Afin de déterminer le vecteur de répétition minimal, les composants initiaux du vecteur de répétition ne sont multipliés que par des coefficients définis par leur plus grand commun diviseur: [Math.8] [0061] Les coefficients ci et c; définis dans les équations (7) vérifient, bien entendu, l'égalité (3). Par exemple, lorsqu'une nouvelle connexion est établie entre les acteurs ai et a;, le composant xi du vecteur de répétition correspondant à l'acteur ai est multiplié par ci, et le composant x; correspondant à l'acteur a; est multiplié par le coefficient c; afin de conserver la propriété de cohérence du graphe. 100621 La Fig. 4 est un organigramme illustrant les étapes d'un procédé de validation d'un système flots de données, selon un mode de réalisation préféré de l'invention. 100631 Dans ce procédé, on vérifie la cohérence d'une connexion unidirectionnelle courante reliant une première partie courante du graphe de flots de données à une deuxième partie courante du graphe de flots de données. 100641 A l'étape El, on définit la connexion unidirectionnelle courante reliant des acteurs d'origine ai et d'arrivée ai. Les acteurs d'origine ai et d'arrivée a; appartiennent aux première et deuxième parties courantes du graphe de flots de données respectivement. On définit les composants d'origine x'i et d'arrivée x"; associés aux acteurs d'origine a et d'arrivée ai. On notera que de manière générale, les composants d'origine x'i et 13 d'arrivée x'', peuvent appartenir à un unique vecteur courant de répétition X' représentatif des première et deuxième parties courantes du graphe ou à deux vecteurs courants de répétition distincts X' et X" représentatifs des première et deuxième parties courantes du graphe respectivement. [0065] La définition de la connexion unidirectionnelle courante comporte l'attribution d'un taux de production r, relatif à l'acteur d'origine a, et d'un taux de consommation r, relatif à l'acteur d'arrivée a,. [0066] On peut par exemple considérer qu'un graphe de flots de données est en construction et qu'une nouvelle connexion courante est établie entre l'acteur d'origine a, et l'acteur d'arrivée a,. Ce cas est résumé dans l'Algorithme décrit dans le tableau 1 ci-dessous. Dans cet Algorithme, on considère deux vecteurs de répétition X' et correspondant respectivement aux première et deuxième parties courantes du graphe de flots de données. On note i l'indice du i,nie composant du vecteur X' et j l'indice du igue composant du vecteur On note r, le taux de production correspondant au composant x', du vecteur X' et r, le taux de consommation correspondant au composant du vecteur X". On note les opérations « ppcm » et « pgcd » par « lcm » et « gcd » respectivement. En outre, on note X le vecteur de répétition résultant correspondant au nouveau graphe. 14 [Tabicauxl] Algorithme 1: if roe, = rix", then 2: o flag true the new oonnection is c.onsistent 3: if X' and X" are twc} distinct ecton then connect two actors frem two different graphs 4: if c flag k true thon 5: X (-- [X' 6: STOP 1: eise 8: m E icordri: d & gcd(x'i; 10: d 4- (m/d);x7e-E) cj (cnifcf)(x',/ri) 12: d 4- gi..dtc,; ci) 13: oi cild 14: c, cr/d 15: x Ç- [cir Lir] lb: STOP 17: else crin neot twa actors of the sarne graph 18: if ri flag is trùe then 19: X 4-- X' 20: STOP 21: else 22: Mark this connection os tact consistent 23: OptiOnal: Send ei ror message 24: STOP 100671 A l'étape E2, afin d'éviter des opérations inutiles, on vérifie d'abord un indicateur de cohérence locale de la connexion unidirectionnelle courante (ligne 1 de l'Algorithme). Cet indicateur de cohérence locale examine si le produit du taux de production ri fois le composant d'origine xi est égal au produit du taux de consommation ri fois le composant d'arrivée xi (i.e., it,x; = ry.xi). Quel que soit l'issue de ce test, on considère aux étapes suivantes deux cas. Un premier cas où les deux acteurs proviennent de deux vecteurs de répétition différents, c'est-à-dire qu'il n'y avait pas de connexion entre les deux acteurs avant la nouvelle connexion, et un deuxième cas où les deux acteurs proviennent du même graphe, c'est-à-dire qu'ils ont le même vecteur de répétition. Selon l'issue de ces deux différents cas, on définit aux étapes E4-E6 ou E8-E9 un vecteur courant de répétition résultant représentatif des première et deuxième parties courantes du graphe de flots de données. [0068] En effet, si le test de l'étape E2 est positif, c'est-à-dire, au cas où la connexion unidi- rectionnelle courante vérifie l'indicateur de cohérence locale, on considère que le drapeau de cohérence (c flag) est vrai sur la ligne 2 de l'Algorithme et on va à l'étape E3. Sinon, on va à l'étape E7. [0069] Les étapes E3-E6 concernent le cas où la connexion unidirectionnelle courante vérifie l'indicateur de cohérence locale. Plus particulièrement, l'étape E3 est un test pour vérifier si les acteurs d'origine a, et d'arrivée a, sont associés à deux vecteurs courants de répétitions distincts, dits vecteurs de répétition d'origine X' et d'arrivée X" (i.e. le cas où il n'existait pas de connexion entre les acteurs d'origine a, et d'arrivée a', avant la connexion unidirectionnelle courante). Si oui, on va à l'étape E4 et sinon, on va à l'étape E6. [0070] L'étape E4 concerne le cas où les deux acteurs proviennent de deux vecteurs de ré- pétition différents et que la nouvelle connexion est cohérente. Dans ce cas, on construit le vecteur courant de répétition résultant X en concaténant les vecteurs de répétitions d'origine X' et d'arrivée X" et on s'arrête à l'étape ES où le graphe est considéré comme étant cohérent. Cela correspond aux lignes 3 à 6 de l'Algorithme ci-dessus. [0071] L'étape E6 concerne le cas où les acteurs d'origine ai et d'arrivée a, sont associés à un unique vecteur courant de répétition (i.e., ils viennent du même graphe). Alors, dans ce cas, le vecteur courant de répétition résultant X est égal à l'unique vecteur courant de répétition X'. Autrement dit, étant donné que les deux acteurs qu'on souhaite associer proviennent du même vecteur de répétition et que l'indicateur de cohérence est vrai, alors l'unique vecteur courant de répétition X' n'est pas modifié et on s'arrête à l'étape ES où le graphe est considéré comme étant cohérent. Cela correspond aux lignes 18-20 de l'Algorithme ci-dessus. [0072] En revanche, si l'issue de l'étape E2 est négatif, c'est-dire, si la connexion unidirec- tionnelle courante ne vérifie pas l'indicateur de cohérence locale, alors on examine les étapes E7-E9. [0073] L'étape E7 est un test similaire à celui de l'étape E3 dans lequel on vérifie si les acteurs d'origine ai et d'arrivée ai sont associés à deux vecteurs courants de répétitions distincts, dits vecteurs de répétition d'origine X' et d'arrivée X". Si oui, on va à l'étape E8 et sinon, on va à l'étape E10. [0074] A l'étape E8, on calcule les deux nombres naturels (i.e. les coefficients de production ci et de consommation ci) vérifiant l'équation (3) ci-dessus. Autrement dit, étant donné que la nouvelle connexion n'est pas cohérente, les coefficients ci et ci définis dans l'équation (7) sont calculés aux lignes 8 à 14 de l'Algorithme ci-dessus. [0075] A l'étape E9, on construit le vecteur courant de répétition résultant X (ligne 15 de l'Algorithme) en concaténant d'une part le vecteur de répétitions d'origine X' après l'avoir multiplié par le coefficient de production c1 avec d'autre part, le vecteur de répétitions d'arrivée X" après l'avoir multiplié par le coefficient de consommation c. Ensuite, on s'arrête à l'étape E5 où l'on considère que le graphe est cohérent. [0076] L'étape EIO concerne le cas où les acteurs d'origine a, et d'arrivée a, sont associés à un unique vecteur courant de répétition (i.e. les acteurs viennent du même graphe), 16 alors la connexion unidirectionnelle courante est identifiée comme étant non cohérente (i.e. le graphe résultant n'est pas cohérent). Cela correspond aux lignes 22-24 de l'Algorithme. [0077] La Fig. 5 illustre de manière schématique la construction d'un graphe selon le procédé de la Fig. 4. [0078] Plus particulièrement, la construction du graphe G5 de la figure 5 est une application de l'Algorithme représenté ci-dessus. Selon cet exemple, quatre acteurs A, B, C et D sont créés, chacun d'entre eux a un vecteur de répétition X= (1). Les connexions unidi- rectionnelles sont établies dans l'ordre suivant: (A -> B), (A -> C), (B D), et (C -> D). Après la connexion (A B), les calculs selon l'Algorithme donnent les valeurs suivantes : c = 3, c; = 2 et X = (3 2), car les deux acteurs proviennent de deux vecteurs de répétition différents. De manière similaire, c, = 1, c; = 3 et X = (3 23) lorsque la connexion (A -> C) est établie. La connexion (B D) souligne l'importance des lignes 12-14 dans l'Algorithme. En effet, avant la ligne 12, ci = ci = 2. Toutefois, en utilisant ces coefficients, on n'obtient pas un vecteur de répétition minimal lors de la mise à jour du vecteur de répétition X comme à la ligne 15, d'où l'intérêt de diviser les coefficients par d (lignes 13 et 14). Le cas exprimé sur les lignes 17 et 18 de l'Algorithme illustre la connexion (C D) où le vecteur de répétition ne change pas, il en est de même après la connexion (C -> D), X = (3 23 1). [0079] L'exemple de la Fig. 5 montre bien l'application de l'Algorithme sur un graphe 05 donné. À partir de cet exemple, on observe que les lignes 8-14 garantissent un ensemble de coefficients entiers nécessaires pour obtenir un vecteur de répétition minimal. En outre, la vérification de la cohérence locale selon le procédé de la présente invention montre très avantageusement comment le nombre d'opérations requises est réduit au minimum, ce qui est très avantageux en particulier, dans le cas d'applications modulaires. [0080] La Fig. 6 illustre de manière schématique la connexion de deux graphes distincts, selon le procédé de la présente invention. L'exemple de la Fig. 6 est une application de flots de données modulaire, dans laquelle le graphe 05 de flots de données représenté sur la Fig. 5 est ajouté au graphe 04 de flots de données représenté sur la Fig. 3 pour former un nouveau graphe 06. La propriété de cohérence ayant déjà été vérifiée pour les deux graphes 04 et 05, seule la nouvelle connexion entre l'acteur BI du premier graphe 04 et l'acteur B2 du second graphe 05 est à vérifier. En appliquant l'Algorithme ci-dessus avec les entrées X'= (2 2 1), X"= (3 23 1), i = 2, j = 2, ri = 1, et ri = 5, on obtient ci = 5 et ci = I. Le vecteur de répétition résultant donné par la sortie de l'Algorithme est X = (10 10 5 3 2 3 1). On remarque que le vecteur courant de répétition résultant X du graphe 06 est construit en concaténant le premier vecteur de répétition X' du graphe 04 après l'avoir multiplié 17 par le coefficient de production ci=5 avec le deuxième vecteur de répétition X" du graphe 05. On notera que les quatre derniers composants sont identiques à ceux du deuxième vecteur de répétition X" car le coefficient de consommation cF1. L'exemple de la Fig. 6 montre bien que lorsque deux graphes G4 et G5 cohérents sont connectés, le procédé selon la présente invention permet de vérifier la propriété de cohérence de manière locale de sorte qu'il n'est plus nécessaire de revérifier la cohérence du graphe résultant 06. En effet, le procédé selon la présente invention ne vérifie que les nouvelles connexions et déduit le vecteur de répétition résultant des deux vecteurs de répétition initiaux. C'est un avantage très important par rapport aux méthodes classiques de l'art antérieur, pour lesquelles une nouvelle matrice de topologie doit être calculée et une nouvelle équation matricielle doit être résolue. En outre, l'application modulaire décrite dans de la Fig. 6 peut également être vue comme la construction d'un premier sous-graphe 04 dans laquelle trois acteurs sont d'abord créés et connectés entre eux, puis la construction d'un deuxième sous-graphe 05 dans laquelle quatre autres acteurs sont créés et connectés entre eux, et enfin les deux sous-graphes 04 et 05 sont connectés entre eux pour former un graphe résultant 06. On notera que la cohérence est vérifiée lors de la construction de chaque sous-graphe 04, 05 en attribuant à chaque acteur d'arrivée ai additionnel un vecteur additionnel de répétition dont son unique composant xi est égal à 1. L'acteur d'arrivée ai additionnel est relié par une connexion unidirectionnelle courante à un acteur d'origine ai appartenant au sous-graphe de flots de données en construction. [0081] La Fig. 7 est un organigramme illustrant les étapes d'un procédé de validation comportant une opération de suppression, selon un mode de réalisation préféré de l'invention. [0082] Dans ce procédé, on vérifie la cohérence d'un graphe de flots de données lors de la suppression d'une connexion unidirectionnelle de ce graphe. [0083] A l'étape E21, on supprime une connexion donnée du graphe de flots de données. [0084] L'étape E22 est un test pour vérifier si le graphe de flots de données initial se divise en deux parties distinctes ou pas. Si le graphe de flots de données se divise en deux parties distinctes, alors on va à l'étape E23 et sinon, on va à l'étape E26. L'étape E23 concerne le cas où le graphe de flots de données se divise en des premier et deuxième sous-graphes de flots de données après la suppression de la connexion unidirectionnelle. Dans ce cas, on construit un premier vecteur de répétition X' en regroupant les composants du vecteur de répétition initial relatifs au premier sous-graphe de flots de données, et on construit un deuxième vecteur de répétition X" en regroupant les composants du vecteur de répétition initial relatifs au deuxième sous-graphe de flots de données. 18 Eventuellement, à l'étape E24, on construit des premier et deuxième vecteurs de répétition minimaux X* et X** en divisant le premier vecteur de répétition X' par le pgcd de ses composants et également, en divisant le deuxième vecteur de répétition X" par le pgcd de ses composants. A l'étape E25, on obtient deux graphes de flots de données distincts et cohérents. L'étape E26 concerne le cas où le graphe de flots de données reste connexe après la suppression de la connexion unidirectionnelle. Alors dans ce cas, on ne modifie pas le vecteur de répétition initial. A l'étape E27, on a toujours un seul graphe cohérent. [0085] La Fig. 8 est un organigramme illustrant les étapes d'un procédé de validation comportant une opération de modification, selon un mode de réalisation préféré de l' invention. [0086] Dans ce procédé on vérifie la cohérence d'un graphe de flots de données lors de la modification d'une connexion unidirectionnelle de cc graphe. [0087] A l'étape E31, on modifie une connexion donnée du graphe de flots de données en lui attribuant des nouveaux taux de production r'i et de consommation r'i relatifs aux acteurs d'origine ai et d'arrivée ai reliés par cette connexion unidirectionnelle. [0088] A l'étape E32, on applique l'opération de suppression d'une connexion unidirec- tionnelle selon les étapes du procédé de la Fig. 7. [0089] A l'étape E33, on applique l'opération d'addition d'une connexion unidirectionnelle décrite par les procédés de la Fig. 4 selon les nouveaux taux de production r'i et de consommation r'i. [0090] A l'étape E34, on obtient un graphe modifié et cohérent. Les exemples et modes de réalisations présentés ci-dessus soulignent les avantages de la vérification locale de la propriété de cohérence. Sur les exemples considérés, on voit que le calcul de la matrice de topologie n'est pas nécessaire et que le vecteur de répétition minimale peut être trouvé de manière très efficace et avec très peu de calcul. Un autre avantage réside dans le fait que les éléments incohérents peuvent être identifiés et qu'il n'est pas nécessaire de reconsidérer le graphe en son entier pour décider de sa cohérence. Par ailleurs, on notera que le procédé selon l'invention peut être appliqué de manière incrémentielle lors de la construction du graphe de flots de données. En variante, il peut également être appliqué après la construction d'un graphe, sur chacune de ses connexions. La présente invention s'applique à tous les systèmes à flot de données. En particulier, elle s'applique aux systèmes de traitement de signal numérique. En effet, le système de traitement peut être modélisé par un système flots de données comportant des acteurs connectés entre eux par des connexions de communications unidirectionnelles. Chaque 19 acteur est configure pour recevoir des données d'entrée et pour délivrer des données de sortie. A titre d'exemple, le système de traitement de signal numérique peut être un système d'imagerie médicale, un système de vision par ordinateur, un système de codage et compression, un système de conversion de la fréquence d'échantillonnage audio, un système de conception d'outils pour les systèmes de communication sans fil, un système embarqué, etc. Ainsi, le système de traitement de signal peut être modélisé par un graphe de flots de données en construction selon une approche incrémentale pouvant être appliquée lors de la construction du graphe. La construction d'un graphe incohérent peut être arrêtée dès qu'un élément incohérent a été identifié. En outre, la modélisation du système de traitement de signal peut être réalisée de manière modulaire. Supposons qu'on souhaite modéliser un système embarqué d'anticollision dans un véhicule et qu'on souhaite ajouter un module de radar à un module de vision par caméras. Supposons que chacun des modules de radar et de vision est décrit par un graphe cohérent. La cohérence de la combinaison des deux modules peut être déterminée selon la présente invention en vérifiant uniquement les modifications générées par la combinaison, telles que l'ajout des connexions entre les deux graphes, et peut ainsi réduire le nombre d'opérations requises pour le contrôle de la cohérence. La Fig. 9 illustre à titre d'exemple la vérification de cohérence dans un système de flots de données modélisant un dispositif d'amélioration de la parole multicanal, selon la présente invention. Le dispositif 21 d'amélioration de la parole multicanal (multichannel speech enhancement, en anglais) est connecté à un réseau de quatre microphones MI-M4. Les signaux bruyants provenant de ces quatre microphones Ml-M4 sont traités par un ensemble d'unités 23, 25, 27 et 29 de traitement de signal compris dans le dispositif 21 pour extraire le signal de la parole améliorée à la sortie 31. En effet, le dispositif 21 d'amélioration de la parole comporte une unité d'alignement temporel ou de synchronisation 23, une unité de transformation de Fourier à court terme 25 (TFCT), une unité d'amélioration du signal avec post-filtrage 27 et une unité d'addition ou de synthèse 29. En particulier, l'unité d'amélioration de la parole avec post-filtrage 27 comporte un premier module 33 de filtrage spatial MVDR (Minimum Variance Distortionless Response), un deuxième module 35 d'estimation de post-filtrage et un troisième module 37 de post-filtrage. Les signaux el-e4 provenant de l'unité 25 de transformation de Fourier sont injectés d'une part dans le premier module 33 de filtrage spatial (Beamformer, en anglais) et d'autre part, dans le deuxième module 35 d'estimation de post-filtrage. En outre, les signaux de sorties des premier 33 et deuxième 35 modules sont injectés dans le troisième module 37 de post-filtrage et le signal de sortie de ce dernier est injecté dans l'unité de synthèse 29. On notera que chacun des modules 33, 35 et 37 peut comporter un ensemble d'acteurs. Ainsi l'unité de post-filtrage 37 peut être modélisée par un graphe de flots de données où la propriété de cohérence est vérifiée sur tous les acteurs selon le procédé de la présente invention. En outre, une fois que la propriété de cohérence a été vérifiée sur tous les modules 33, 35, 37 de cette application, on peut en modifier certains. Supposons par exemple que l'application d'amélioration de la parole multicanal utilise un post-filtre de McCowan pour le module de post-filtrage 37. Ce filtre peut être remplacé par un post-filtre de Wiener afin d'obtenir une estimation plus précise de la densité spectrale du bruit. Dans ce cas, il n'est pas nécessaire de vérifier à nouveau la propriété de cohérence sur l'ensemble des modules. En effet, si le nouveau module de post-filtrage vérifie la propriété de cohérence, ceci n'impactc pas la propriété de cohérence des autres modules et on en conclut que toute l'application vérifie la propriété de cohérence selon le procédé de la présente invention. Références [OO91j I. Lee, E.A., Messerschmitt, D.G.: Synchronous data ow. Proceedings of the IEEE 75(9), 1235[1245 (1987). 2. Lee, E.A., Messerschmitt, D.G.: Static schcduling of synchronous data ow programs for digital signal processing; IEEE Transactions on computers 100(1), 24[35 (1987). 21 [Revendication I] [Revendication 2] [Revendication 3]