FR3131022A1

FR3131022A1 - Procede de determination d une grandeur physique et systeme de determination associe.

Info

Publication number: FR3131022A1
Application number: FR2114111A
Authority: FR
Inventors: Lionel GAYRAUD; Aurélien THIRIET; Rémi Barrere
Original assignee: Thales SA
Current assignee: Thales SA
Priority date: 2021-12-21
Filing date: 2021-12-21
Publication date: 2023-06-23
Also published as: WO2023118261A1

Abstract

Procédé de détermination d’une grandeur physique et système de détermination associé La présente invention concerne un procédé de détermination d’une grandeur physique vérifiant un système d’équations respectant une contrainte, le procédé étant mis en œuvre par un système comprenant une pluralité de cœurs, le procédé déterminant la grandeur physique par résolution du système d’équations différentielles en plusieurs itérations comportant : - une transformation d’une liste courante en une liste compactée comprenant : - l’initialisation de la liste compactée, - pour chaque cœur, la détermination pour chaque point de la liste courante présentant un des indices spécifiques au cœur si une condition est vérifiée, et pour chaque point déterminé, modification d’une valeur de la liste compactée, - la lecture des valeurs de la liste compactée différentes de la valeur d’initialisation, - des calculs sur les points déterminés, et - l’actualisation de la liste, et ce jusqu’à vider la liste courante. Figure pour l'abrégé : figure 3

Description

Procédé de détermination d’une grandeur physique et système de détermination associé

La présente invention concerne un procédé de détermination d’une grandeur physique. Elle se rapporte également à un système de détermination d’une grandeur physique correspondante.

Les équations différentielles d’Hamilton-Jacobi régissent de nombreux phénomènes physiques et se retrouvent donc impliquées dans de multiples applications telles que le traitement d’images, par exemple les images médicales, les géosciences ou la planification de trajectoires.

En effet, les équations différentielles d’Hamilton-Jacobi ont des équations associées à une transformation du hamiltonien dans l'espace des phases, et qui permettent de simplifier la résolution des équations du mouvement. Tout domaine impliquant des équations de mouvement est donc concerné par des phénomènes physiques régis par des équations différentielles d’Hamilton-Jacobi.

Une équation d’Hamilton-Jacobi prend la forme :

Où :

Où H est un opérateur Hamiltonien,
est une solution de l’équation qui est la grandeur physique cherchée lorsque l’on souhaite résoudre l’équation d’Hamilton-Jacobi,
est généralement dénommée un nœud, c’est-à-dire une valeur possible pour la variable de . Par ailleurs, , étant un domaine inclus dans ,
désigne le gradient de u par rapport à x.

Les méthodes les plus répandues pour résoudre une telle équation sont des méthodes causales.

Une méthode causale implique l’emploi d’un liste prioritaire au sein de laquelle chaque nœud est classé par valeur croissante de . Ainsi, une méthode causale repose sur un ordre précis de résolution avec une pluralité d’itérations. Selon cet ordre, à chaque itération, le nœud de plus faible valeur de est choisi et considéré ensuite comme « accepté ». Lorsqu’un nœud est accepté, la valeur n’est plus jamais réévaluée dans les itérations subséquentes de la méthode causale.

Du fait de cette évaluation unique de la valeur de chaque nœud, une méthode causale est également qualifiée de méthode à passe unique (plus souvent désignée sous la dénomination anglaise correspondante de « single pass »).

Cela permet de diminuer fortement la complexité algorithmique au prix d’une hypothèse de causalité.

Toutefois, dans certains cas, cette hypothèse n’est pas valable, ce qui fait qu’une méthode causale n’est pas universelle.

En outre, une méthode causale présente une forte dépendance entre les données, ce qui ne permet pas une implémentation physique efficace des calculs, notamment sur une architecture parallèle de type GP-GPU (l’abréviation « GP-GPU » renvoyant à la dénomination anglaise de « general purpose computing on graphical process units » qui signifie calcul générique sur processeur graphique).

Il est également connu des méthodes de résolution itérative n’impliquant pas de faire l’hypothèse de causalité au prix d’un plus grand nombre de calculs. Les méthodes de résolution itérative n’impliquent l’emploi d'aucun mécanisme d’ordonnancement particulier. De fait, ce ne sont pas des méthodes de type passe unique comme les méthodes causales, mais plutôt des méthodes de type passe multiple dans lesquelles un nœud n’est jamais définitivement considéré comme résolu, et est donc susceptible d’être réévalué à tout moment.

Ces méthodes de résolution itérative sont donc moins efficaces que les méthodes de résolution causale sur des architectures non parallèles (tel qu’un microprocesseur classique) dans la mesure où le nombre de calculs rend leur exécution lente.

Il existe donc un besoin pour un procédé de détermination d’une grandeur physique impliquant une résolution d’un système d’équations différentielles d’Hamilton-Jacobi permettant une implémentation efficace dans un calculateur parallèle.

A cet effet, la description décrit un procédé de détermination d’une grandeur physique, la grandeur physique vérifiant un système d’équations différentielles d’Hamilton-Jacobi pour respecter une contrainte variant spatialement dans un environnement prédéfini, le procédé étant mis en œuvre par un système de détermination de la grandeur physique, le système de détermination comprenant une pluralité de cœurs, le procédé comportant :

- une phase de réception de données d’entrées, les données d’entrées comprenant des mesures de la contrainte en plusieurs points de l’environnement prédéfini,

- une phase de détermination de la grandeur physique par utilisation d’une technique de résolution du système d’équations différentielles, pour obtenir la grandeur physique respectant la contrainte, la technique de résolution comportant plusieurs itérations, chaque itération comportant les étapes suivantes:

- la transformation d’une liste courante en une liste compactée courante, la liste courante comportant des points de l’environnement prédéfini auxquels sont attribués un nombre, chaque point étant repéré par un indice, des indices spécifiques étant attribués à chaque cœur de la pluralité de cœurs, l’ensemble des indices de la liste courante étant attribué à l’un des cœurs, la transformation comprenant :

- l’initialisation de la liste compactée à une valeur d’initialisation,

- pour chaque cœur de la pluralité de cœurs :

- la détermination pour chaque point de la liste courante présentant un indice compris parmi des indices spécifiques au cœur considéré si une condition binaire est vérifiée, pour obtenir un élément déterminé lorsque la condition binaire est vérifiée, et

- pour chaque point de la liste courante déterminé, la modification d’une valeur de la liste compactée n’ayant pas été modifiée et présentant l’indice le plus petit de l’ensemble des indices spécifiques au cœur considéré,

- la lecture des valeurs de la liste compactée courante différentes de la valeur d’initialisation pour obtenir les points vérifiant la condition binaire,

- la mise en œuvre de calculs uniquement sur les points déterminés, et

- l’actualisation de la liste en fonction des calculs mis en œuvre,

les itérations étant mises en œuvre jusqu’à ce que la liste courante soit vide.

Selon des modes de réalisation particuliers, le procédé de détermination présente une ou plusieurs des caractéristiques suivantes, prise(s) isolément ou selon toutes les combinaisons techniquement possibles :

- le nombre d’indices spécifiques est le même pour chaque cœur.

- à chaque cœur est attribué un reste respectif de la division euclidienne par le nombre de cœurs, l’ensemble des indices spécifiques au cœur considéré comprenant l’ensemble des indices dont le reste de la division euclidienne de l’indice par le nombre de cœurs est égal au reste respectif.

- chaque nombre attribué est un nombre binaire et la condition binaire est que le nombre binaire attribué est égal à une valeur prédéfinie.

- la valeur d’initialisation est une valeur négative.

- l’opération d’initialisation est également mise en œuvre par chaque cœur uniquement pour les indices spécifiques au cœur considéré.

- la mise en œuvre itérative de calculs est réalisée jusqu’à ce que la liste courante soit vide.

- les calculs comportent une opération de test de convergence de la valeur du point.

- pour chaque point, il est défini un stencil négatif, les calculs comportent également une opération d’élimination du point ayant fait l’objet de l’opération de test de la liste courante, et une opération d’ajout de points uniquement si le test de convergence n’est pas satisfait, les points ajoutés étant de préférence les points du stencil négatif.

- les contraintes sont des mesures d’au moins un capteur

La description décrit aussi un système de détermination d’une grandeur physique, la grandeur physique vérifiant un système d’équations différentielles d’Hamilton-Jacobi pour respecter une contrainte variant spatialement dans un environnement prédéfini, le système de détermination comprenant une pluralité de cœurs, le système de détermination étant propre à mettre en œuvre un procédé de détermination d’une grandeur physique, le procédé comportant :

- l’initialisation de la liste compactée à une valeur d’initialisation,

- pour chaque cœur de la pluralité de cœurs :

- la mise en œuvre de calculs uniquement sur les points déterminés, et

- l’actualisation de la liste en fonction des calculs mis en œuvre,

Des caractéristiques et avantages de l’invention apparaîtront à la lecture de la description qui va suivre, donnée uniquement à titre d’exemple non limitatif, et faite en référence aux dessins annexés, sur lesquels :

- la est une représentation schématique d’un exemple de système de détermination,

- la est une illustration schématique des notions de stencil direct et de stencil indirect,

- la est une vue schématique d’un exemple de mise en œuvre d’une partie d’un exemple de technique de compactage,

- la est une vue schématique d’un exemple de mise en œuvre d’une autre partie d’un exemple de technique de compactage,

- la est une vue schématique d’un exemple de mise en œuvre d’une autre partie d’un exemple de technique de compactage, et

- la est une vue schématique d’un exemple de mise en œuvre d’une autre partie d’un exemple de technique de compactage.

La est une représentation schématique d’un système de détermination 10 d’une grandeur physique.

Le système de détermination 10 est propre à déterminer une grandeur physique.

Plus précisément, le système de détermination 10 est propre à partir d’au moins une donnée d’entrée 12 à obtenir au moins une donnée de sortie 16, l’au moins une donnée de sortie 16 correspondant à la grandeur physique à déterminer.

Une grandeur physique correspond, dans ce contexte, à l’évolution spatiale d’une mesure physique (c’est-à-dire une mesure obtenue par un capteur) dans un environnement prédéfini.

Dans le suite, la grandeur physique est notée U et l’environnement prédéfini est noté . Il peut être remarqué que l’environnement prédéfini est souvent dénommé domaine. L’expression « domaine » sera donc utilisée. Le domaine est un ensemble de points x.

Avec de telles notations, une mesure physique s’écrit donc U(x) qui est la valeur de la grandeur physique U évaluée au point x.

Par ailleurs, la grandeur U vérifie en tout point du domaine un système d’équations différentielles dit d’Hamilton-Jacobi ainsi que des conditions initiales (typiquement U(x)=0) sur les points d’un ensemble D.

A titre d’illustration, la grandeur physique est liée au mouvement, c’est par exemple, une position ou une vitesse.

Selon l’exemple décrit, la grandeur U est en chaque point x de la longueur de la trajectoire (ou géodésique) la plus courte permettant d’atteindre le point x depuis un ensemble D de points appelé ensemble de départ.

Dans ce cas, la grandeur physique est la position d’un ensemble de points, la position pouvant être évaluée par une ou plusieurs coordonnées.

Selon l’exemple décrit, les données d’entrée 12 comprennent :

un domaine contenant un ensemble de points x,
l’opérateur Hamiltonien H en tout point x du domaine , c’est-à-dire l’équation H(x,∇u(x))=0 à vérifier au point x, et
pour tout point x d’un ensemble de départ D, la valeur U(x) en ce point.

A titre de remarque, il est intéressant de noter que la manière dont sont fournis ces données est indifférente. Typiquement, il est également possible de fournir un opérateur Hamilton paramétrique (une équation, qui sera la même en tout point x du domaine à quelques valeurs de paramètres près) ainsi que des tables permettant d’associer à chaque point du domaine les valeurs idoines de ces paramètres (il peut par exemple s’agir d’une carte de coût). Ceci permettra de « paramétrer » l’opérateur d’Hamilton de façon différente d’un point à l’autre du domaine.

Plusieurs exemples d’utilisation du système de détermination 10 à des fins de planification de trajectoire sont maintenant décrits. Pour chacun de ces exemples, le système de détermination 10 produit une grandeur U(x) associée à chaque point x du domaine qui permettra à un autre système, non détaillé ici, de rechercher des trajectoires optimisées partant d’un des points de l’ensemble de départ D (le plus favorable) et arrivant en tout x point du domaine .

Selon un premier exemple, il s’agit de minimiser les risques d’enlisement d’un véhicule terrestre. Dans un tel exemple, les points du domaine sont caractérisés par deux coordonnées et sont donc des 2-uplets de la forme (x,y), la trajectoire à déterminer étant la trajectoire du véhicule dans le plan. L’opérateur d’Hamilton associé à tout point x traduit la plus ou moins grande adhérence du sol en ce point x. Les conditions initiales sont typiquement U(x) = 0 pour tout point x correspondant à une position de départ envisageable du véhicule terrestre.

Selon un deuxième exemple, il s’agit d’obtenir la trajectoire d’un hélicoptère dans un espace aérien sans percuter un élément de l’espace aérien. Dans un tel exemple, les points sont caractérisés par trois coordonnées et sont donc des 3-uplets de la forme (x,y,z), la trajectoire à déterminer étant la trajectoire de l’hélicoptère dans l’espace. L’opérateur d’Hamilton associé à tout point x traduit le risque de collision avec le sol en ce point. Les conditions initiales sont typiquement U(x) = 0 pour tout point x correspondant à une position de départ envisageable de l’hélicoptère.

Selon un troisième exemple, il s’agit d’obtenir une trajectoire évoluant sur du plat pour un véhicule terrestre. Dans un tel exemple, les points sont caractérisés par trois coordonnées et sont donc des 3-uplets de la forme (x,y,θ), où θ est une information de cap (en radians ou degrés). L’opérateur d’Hamilton associé à tout point x traduit le caractère plus ou moins plat du sol à la position (x,y) lorsqu’on la traverse via le cap θ . En variante ou en complément, il est également possible d’introduire dans l’opérateur d’Hamilton une contrainte de rayon de virage minimum à respecter en ce point. Les conditions initiales sont typiquement U(x) = 0 pour tout point x correspondant à une position de départ envisageable du véhicule terrestre.

A travers ces exemples, il apparaît bien que chaque point est caractérisé par un n-uplet quelconque, où n est la dimension du domaine , la dimension du domaine dépendant de la grandeur U à déterminer ainsi que de l’opérateur d’Hamilton à appliquer à chaque point.

Pour transformer au moins une donnée d’entrée 12 en au moins une donnée de sortie 16, le système de détermination 10 est propre à mettre en œuvre un procédé de détermination d’une grandeur physique, procédé qui sera décrit ultérieurement.

Le système de détermination 10 est un calculateur comportant plusieurs cœurs 18.

Un cœur 18 est un ensemble de circuits capables d’exécuter des programmes de façon autonome.

L’implémentation physique de chaque cœur 18 est indifférente pour ce qui suit, un cœur pouvant être une unité de traitement graphique (GP-GPU), un microcontrôleur et un processeur de signal numérique (DSP), un circuit logique programmable (comme un circuit intégré spécifique à une application (ASIC), un réseau de portes programmablesin situ(FPGA), un dispositif logique programmable (PLD) et des réseaux logiques programmables (PLA)), une machine à états, une porte logique et des composants matériels discrets.

Dans la , seuls deux cœurs 18 sont présentés, sachant que le nombre de cœurs 18 peut être aussi élevé que désiré.

Le fonctionnement du système de détermination 10 est maintenant décrit en référence à un exemple de mise en œuvre du procédé de détermination illustré par les figures 2 à 7.

Avant de détailler l’ensemble du procédé, deux techniques, une technique de résolution itérative et une technique de compactage impliquées dans le procédé de détermination vont d’abord être décrites.

Pour mettre au point le procédé de détermination, le demandeur a choisi une technique de résolution itérative.

Comme expliqué précédemment, la technique de résolution ne peut pas être une méthode causale du fait de la forte dépendance entre les données. En effet, une telle dépendance empêche une parallélisation et donc une implémentation physique efficace des calculs sur une architecture parallèle.

Il convient de choisir une technique de résolution qui est une technique de résolution itérative n’impliquant pas de faire l’hypothèse de causalité.

Parmi les différentes techniques, le demandeur a trouvé comme particulièrement pertinente la technique connue d’un article de F. Bornemann et al. intitulé «Finite-element discretization o f static hamilton-jacobi equatio ns based on local variational principe» daté de 2006 une technique de résolution adaptative par itérations de Gauss-Seidel. Une telle technique est appelée AGSI, l’abréviation AGSI renvoyant à la dénomination anglaise correspondante de «Adaptative Gauss Seidel Iterative».

La technique AGSI utilise les notions de stencils qui sont représentés schématiquement sur la .

Le stencil direct est l’ensemble des points impliqués dans le calcul de la valeur u(x) et est représenté par des rectangles sur la figure 2. Le stencil direct est noté dans ce qui suit.

Le stencil indirect d’un point désigne, quant à lui, l’ensemble des points de contenant dans leur stencil direct : . Le stencil indirect est noté .

La technique AGSI utilise également une formule d’Hopf-Lax, qui est une équation permettant de calculer la distance de connaissant celle des voisins de x, au sens du stencil direct. Cette formule est notée . La formule d’Hof-Lax exprime l’opérateur d’Hamilton à vérifier au point sous la forme d’une équation impliquant x et l’ensemble de ses voisins au sens du stencil indirect.

La technique AGSI revient ainsi à approximer l’opérateur d’Hamilton H(x,∇u(x)) en considérant qu’un point x n’interagit qu’avec ses proches voisins, les points de . Le vecteur gradient ∇u(x) ne dépend alors plus que des points de , et l’opérateur H(x,∇u(x)) devient une simple équation liant la valeur U en x aux valeurs de U sur les points de .

En outre, il est également défini un critère de convergence arbitraire désignant la tolérance liée à la bonne convergence d’un nœud x ainsi qu’une liste non ordonnée de nœuds actifs . A chaque itération, seuls les nœuds de la liste L sont évalués.

La technique AGSI peut se résumer selon l’ensemble des actions ci-après :

Initialisation :

, ajouter à

puis

Tant que n’est pas vide :

Retirer de

Si et si :

, ajouter à

Cette série d’instructions peut être résumée de la façon suivante : à chaque itération, tous les nœuds de la liste L sont réévalués, c’est-à-dire ceux dont au moins un voisin (au sens du stencil indirect) a été amélioré à l’itération précédente (valeur absolue de l’amélioration supérieure au seuil de convergence ). La réévaluation de chacun de ces nœuds provoquera la réévaluation de tous leurs voisins (au sens du stencil direct). Cette procédure se répète jusqu’à ce que plus aucun nœud ne change de valeurs. Les nœuds initiaux sont l’ensemble des nœuds de D.

Il est aussi connu une autre technique de la demande US 2011/0046927 A1, la technique étant itérative et correspondant au schéma de résolution :

Tant que n’est pas vide :

Pour tout de :

Si :
Si :
- :
  - Si n’appartient pas à :

Si

Ajouter y à
Retirer x de L

Pour la suite, une telle technique est appelée technique FIM, l’abréviation FIM renvoyant à la dénomination de «Fast Iterative Marching» qui signifie littéralement marche itérative rapide.

Les deux techniques précitées, à savoir la technique FIM et la technique AGSI, sont très proches, ce qui n’est guère surprenant puisque ces techniques résolvent le même problème et relèvent toutes les deux d’une technique itérative de résolution.

Néanmoins, malgré leurs similitudes, ces deux techniques ne sont pas strictement équivalentes.

En effet, entre les deux techniques, il y a une inversion de l’utilisation du test de convergence par rapport au seuil .

De fait, pour la technique FIM, la convergence est testée pour chaque point de la liste L. En outre, l’activation potentielle des voisins correspond au fait que le nœud antérieur respecte le critère de convergence. Au contraire, dans la technique AGSI, l’activation potentielle des voisins n’a lieu que si le nœud antérieur est modifié, ce qui implique que le nœud antérieur ne respecte pas le critère de convergence.

De plus, le rôle des listes est différent entre les deux techniques.

Pour le cas de la technique FIM, puisqu’un nœud reste dans la liste sauf s’il a convergé, la liste correspond à l’ensemble des nœuds qui doivent encore converger. Par contraste, dans la technique AGSI, un nœud est systématiquement retiré de la liste, quel que soit le résultat du test de convergence. Il n’y sera réintroduit que si un nœud dont il dépend (même stencil) réalise une amélioration. Aussi, la liste dans le cas de la technique AGSI peut être comprise comme jouant un mécanisme de requête/acquittement. L’insertion d’un nœud dans la liste peut être perçu comme une requête de mise à jour, qui est acquittée de façon systématique.

Du fait de ce constat, la technique AGSI a été sélectionnée par le demandeur comme une bonne technique de résolution itérative candidate pour une parallélisation, c’est-à-dire un traitement au moins en partie parallèle dans plusieurs cœurs 18.

La technique AGSI technique peut être décrite comme la mise en œuvre de deux phases :

une phase de réception des données d’entrées suivantes:
- Un domaine contenant un ensemble de points x associés chacun à un indice unique i
- Pour tout point x du domaine , les ensembles et appelés stencils directs et indirects, ainsi que la formule d’Hopf-Lax en ce point
- Pour tout point x d’un ensemble D, la valeur U(x) en ce point
- Une valeur de seuil
une phase de détermination de la grandeur physiques U(x) en tout point de \D par utilisation d’itérations AGSI successives, chaque itération comprenant la mise en œuvre de calculs uniquement sur des points contenus dans une liste L et l’actualisation de la liste en fonction des calculs mis en œuvre, les itérations étant mises en œuvre jusqu’à ce que la liste courante soit vide.

En l’espèce, les calculs comportent une opération de réévaluation de la valeur de U pour tout point de la liste L, une opération d’élimination de ce point de la liste L, et une opération d’ajout à la liste L des points appartenant au stencil direct des points pour lesquels la réévaluation a conduit à une amélioration d’amplitude supérieure à en valeur absolue.

Pour des raisons pratiques liées à la parallélisation massive du procédé, la liste L est implémentée sous la forme d’une table contenant une cellule par point x du domaine . Dans une réalisation, la liste L est une liste d’entiers (aussi dénommés sous l’appellation anglaise correspondante d’« integer ») prenant les valeurs 0 ou 1 à la position correspondant à l’indice i du point x.

L’utilisation d’une liste contenant autant de cellules que de points x dans le domaine permet à N processus indépendants d’ajouter un nœud x à la liste L en évitant qu’un nœud n’apparaisse plusieurs fois. Ainsi, N processus indépendants peuvent simultanément écrire 1 dans la cellule du nœud d’indice i correspondant à un point x. Le point x ne sera introduit qu’une fois et une seule dans la liste L. Par ailleurs, le fait que les processus écrivent cette valeur simultanément n’est pas gênant car ils y inscrivent tous la valeur 1 (il n’y a pas de conflit en écriture).

Afin d’améliorer l’efficacité du procédé de résolution la liste L est compactée à chaque itération de la phase de détermination de la grandeur physique U(x). La phase de détermination de la grandeur physique U(x) repose sur deux listes notées L et cL. La liste cL est implémentée sous la forme d’une table contenant une cellule par point x du domaine , chaque cellule prenant pour valeur soit l’indice i d’un point du domaine , soit une valeur indiquant que la cellule est vide. Dans une réalisation, les cellules vides contiennent la valeur -1. Un exemple de listes L et cL est présenté sur les deux tableaux suivants.

L
0	0	1	1	0	0	0	1	1	0

cL
2	3	7	8	-1	-1	-1	-1	-1	-1

La technique de compactage permettant de déterminer cL à partir de L choisie par le demandeur est illustrée par les schémas des figures 3 à 7.

La liste L comporte un ensemble de 20 éléments (représentés chacun sous la forme d’une case).

Pour la suite, les éléments sont ordonnés de la gauche vers la droite avec un indice qui est positionné en bas à gauche dans la liste L sur les figures 3 à 6.

Le premier indice est 0, le deuxième indice est 1 et ainsi de suite jusqu’au dernier indice de 19.

En l’espèce, chaque élément de la liste L est soit un « 0 » soit un « 1 ». Plus précisément, les éléments de la liste L dont les indices sont 1, 3, 7, 8, 12, 14, 17 et 19 sont un « 1 ». Les éléments de la liste L ayant un autre indice sont un « 0 ».

Similairement, sur les figures 3 à 6, la liste compactée cL comprend aussi un ensemble de 20 éléments (également représentés sous la forme d’une case).

Le même système d’indice est utilisé pour la liste compactée cL, les indices n’étant pas repris sur les figures dans un souci de lisibilité des figures.

Initialement, chaque élément de la liste compactée cL est un « -1 ».

Les figures 3 à 6 illustrent comment les éléments de la liste compactée cL sont remplis en fonction de liste L, chaque à 6 correspondant à des éléments respectifs.

Il convient également de noter que l’opération de remplissage de la liste compactée cL est ici spécifique en ce sens que l’opération de remplissage est une opération de remplacement de la valeur « -1 » lorsqu’au moins une condition est remplie dans la liste L.

La montre comment les éléments d’indice 0, 4, 8, 12 et 16 sont traités, c’est-à-dire tous les éléments dont l’indice est proportionnel à 4 soit égal à 0 modulo 4 ; la montre comment les éléments d’indice 1, 5, 9, 13 et 17 sont traités, c’est-à-dire tous les éléments dont l’indice est égal à 1 modulo 4 ; la montre comment les éléments d’indice 2, 6, 10, 14 et 18 sont traités, c’est-à-dire tous les éléments dont l’indice est égal à 2 modulo 4 et la montre comment les éléments d’indice 3, 7, 11, 15 et 19 sont traités, c’est-à-dire tous les éléments dont l’indice est égal à 3 modulo 4.

Du fait de ce partage, l’opération de traitement des éléments de la liste compactée cL visée par la correspond à un processus dénommé premier processus P0, l’opération de traitement des éléments de la liste compactée cL visée par la correspond à un processus dénommé deuxième processus P1, l’opération de traitement des éléments de la liste compactée cL visée par la correspond à un processus dénommé troisième processus P2 et l’opération de traitement des éléments de la liste compactée cL visée par la correspond à un processus dénommé quatrième processus P3.

Chacun de ces processus va être décrit de manière plus détaillée.

Comme expliqué précédemment, le premier processus P0 est illustré sur la . Le premier processus P0 vise à effectuer l’opération de traitement des éléments dont l’indice est égal à 0 modulo 4.

Pour cela, dans l’exemple décrit, le premier processus P0 commence par lire la valeur du premier élément de la liste L concerné par ce processus (indice 0) et lit la valeur « 0 ». Le premier processus P0 ne fait alors aucune opération sur la liste compactée cL.

Ensuite, le premier processus P0 lit la valeur du deuxième élément de la liste L concerné par ce processus (indice 4) et lit la valeur « 0 ». Le premier processus P0 ne fait alors aucune opération sur la liste compactée cL

Puis, le premier processus P0 lit la valeur du troisième élément de la liste L concerné par le processus (indice 8) et lit la valeur « 1 ». Le premier processus P0 modifie alors la valeur de l’élément de la liste compactée cL ayant le premier indice accessible de la liste compactée cL car c’est la première fois qu’une valeur « 1 » est lue par le premier processus P0. Le premier indice de la liste compactée cL accessible au premier processus P0 est, en l’occurrence, le premier indice de la liste compactée cL (l’indice 0). Le premier processus P0 change alors la valeur initiale « -1 » de l’élément d’indice 0 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 8 ».

Ensuite, le premier processus P0 lit la valeur du quatrième élément de la liste L concerné par le processus (indice 12) et lit la valeur « 1 ». Le premier processus P0 modifie alors la valeur de l’élément de la liste compactée cL ayant le deuxième indice accessible de la liste compactée cL car c’est la deuxième fois qu’une valeur « 1 » est lue par le premier processus P0. Le deuxième indice de la liste compactée cL accessible au premier processus P0 est, en l’occurrence, le cinquième indice de la liste compactée cL (l’indice 4). Le premier processus P0 change alors la valeur initiale « -1 » de l’élément d’indice 4 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 12 ».

Enfin, le premier processus P0 lit la valeur du cinquième élément de la liste L concerné par le processus (indice 16) et lit la valeur « 0 ». Le premier processus P0 ne fait alors aucune opération sur la liste compactée cL

A l’issue du premier processus P0, les valeurs des éléments des autres indices accessibles de la liste compactée cL, en l’occurrence les indices 8, 12 et 16, ne sont pas modifiées et restent donc à la valeur initiale de « -1 ».

Comme expliqué précédemment, le deuxième processus P1 est illustré sur la . Le deuxième processus P1 vise à effectuer l’opération de remplissage sur les éléments dont l’indice est égal à 1 modulo 4.

Pour cela, dans l’exemple décrit, le deuxième processus P1 lit la valeur du premier élément de la liste L concerné par le processus (indice 1) et lit la valeur « 1 ». Le deuxième processus P1 modifie alors la valeur de l’élément de la liste compactée cL ayant le premier indice accessible de la liste compactée cL car c’est la première fois qu’une valeur « 1 » est lue par le deuxième processus P1. Le premier indice de la liste compactée cL accessible au deuxième processus P1 est, en l’occurrence, le deuxième indice de la liste compactée cL (l’indice 1). Le deuxième processus P1 change alors la valeur initiale « -1 » de l’élément d’indice 1 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 12 ».

Puis, le deuxième processus P1 lit la valeur du deuxième élément concerné par le processus (indice 5) et lit la valeur « 0 ». Le deuxième processus P1 ne fait alors aucune opération sur la liste compactée cL.

Ensuite, le deuxième processus P1 lit la valeur du troisième élément de la liste L concerné par le processus (indice 9) et lit la valeur « 0 ». Le deuxième processus P1 ne fait alors aucune opération sur la liste compactée cL

Puis, le deuxième processus P1 lit la valeur du quatrième élément de la liste L concerné par le processus (indice 13) et lit la valeur « 0 ». Le deuxième processus P1 ne fait alors aucune opération sur la liste compactée cL.

Enfin, le deuxième processus P1 lit la valeur du cinquième élément de la liste L concerné par le processus (indice 17) et lit la valeur « 1 ». Le deuxième processus P1 modifie alors la valeur de l’élément de la liste compactée cL ayant le deuxième indice accessible de la liste compactée cL car c’est la deuxième fois qu’une valeur « 1 » est lue par le deuxième processus P1. Le deuxième indice de la liste compactée cL accessible au deuxième processus P1 est, en l’occurrence, le sixième indice de la liste compactée cL (l’indice 5). Le deuxième processus P1 change alors la valeur initiale « -1 » de l’élément d’indice 5 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 17 ».

A l’issue du deuxième processus P1, les valeurs des éléments des autres indices accessibles de la liste compactée cL, en l’occurrence les indices 9, 13 et 17, ne sont pas modifiées et restent donc à la valeur initiale de « -1 ».

Comme expliqué précédemment, le troisième processus P2 est illustré sur la . Le troisième processus P2 vise à effectuer l’opération de remplissage sur les éléments dont l’indice est égal à 2 modulo 4.

Le troisième processus P2 lit la valeur du premier élément de la liste L concerné par le processus (indice 2) et lit la valeur « 0 ». Le troisième processus P2 ne fait alors aucune opération sur la liste compactée cL.

Le troisième processus P2 lit la valeur du second élément de la liste L concerné par le processus (indice 6) et lit la valeur « 1 ». Le troisième processus P2 modifie alors la valeur de l’élément de la liste compactée cL ayant le premier indice accessible de la liste compactée cL car c’est la première fois qu’une valeur « 1 » est lue par le troisième processus P2. Le premier indice de la liste compactée cL accessible au troisième processus P2 est, en l’occurrence, le troisième indice de la liste compactée cL (l’indice 2). Le troisième processus P2 change alors la valeur initiale « -1 » de l’élément d’indice 2 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 6 ».

Le troisième processus P2 lit la valeur du troisième élément de la liste L concerné par le processus (indice 10) et lit la valeur « 0 ». Le troisième processus P2 ne fait alors aucune opération sur la liste compactée cL.

Le troisième processus P2 lit la valeur du quatrième élément de la liste L concerné par le processus (indice 14) et lit la valeur « 1 ». Le troisième processus P2 modifie alors la valeur de l’élément de la liste compactée cL ayant le deuxième indice accessible de la liste compactée cL car c’est la deuxième fois qu’une valeur « 1 » est lue par le troisième processus P2. Le deuxième indice de la liste compactée cL accessible au troisième processus P2 est, en l’occurrence, le huitième indice de la liste compactée cL (l’indice 7). Le troisième processus P2 change alors la valeur initiale « -1 » de l’élément d’indice 7 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 14 ».

Le troisième processus P2 lit la valeur du cinquième élément de la liste L concerné par le processus (indice 18) et lit la valeur « 0 ». Le troisième processus P2 ne fait alors aucune opération sur la liste compactée cL.

A l’issue du troisième processus P2, les valeurs des éléments des autres indices accessibles de la liste compactée cL, en l’occurrence les indices 10, 14 et 18, ne sont pas modifiées et restent donc à la valeur initiale de « -1 ».

Comme expliqué précédemment, le quatrième processus P3 est illustré sur la . Le quatrième processus P3 vise à effectuer l’opération de remplissage sur les éléments dont l’indice est égal à 3 modulo 4.

Pour cela, dans l’exemple décrit, le quatrième processus P3 lit la valeur du premier élément de la liste L concerné par le processus (indice 3) et lit la valeur « 1 ». Le quatrième processus P3 modifie alors la valeur de l’élément de la liste compactée cL ayant le premier indice accessible de la liste compactée cL car c’est la première fois qu’une valeur « 1 » est lue par le quatrième processus P3. Le premier indice de la liste compactée cL accessible au quatrième processus P3 est, en l’occurrence, le quatrième indice de la liste compactée cL (l’indice 3). Le quatrième processus P3 change alors la valeur initiale « -1 » de l’élément d’indice 3 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 3 ».

Puis, le quatrième processus P3 lit la valeur du second élément de la liste L concerné par le processus (indice 7) et lit la valeur « 1 ». Le quatrième processus P3 modifie alors la valeur de l’élément de la liste compactée cL ayant le deuxième indice accessible de la liste compactée cL car c’est la deuxième fois qu’une valeur « 1 » est lue par le quatrième processus P3. Le deuxième indice de la liste compactée cL accessible au quatrième processus P3 est, en l’occurrence, le huitième indice de la liste compactée cL (l’indice 7). Le quatrième processus P3 change alors la valeur initiale « -1 » de l’élément d’indice 7 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément de la liste L lu, à savoir la valeur « 7 ».

Le quatrième processus P3 lit la valeur du troisième élément de la liste L concerné par le processus (indice 11) et lit la valeur « 0 ». Le quatrième processus P3 ne fait alors aucune opération sur la liste compactée cL.

Le quatrième processus P3 lit la valeur du quatrième élément de la liste L concerné par le processus (indice 15) et lit la valeur « 0 ». Le quatrième processus P3 ne fait alors aucune opération sur la liste compactée cL.

Le quatrième processus P3 lit la valeur du cinquième élément de la liste L concerné par le processus (indice 19) et lit la valeur « 1 ». Le quatrième processus P3 modifie alors la valeur de l’élément de la liste compactée cL ayant le troisième indice accessible de la liste compactée cL car c’est la troisième fois qu’une valeur « 1 » est lue par le quatrième processus P3. Le troisième indice de la liste compactée cL accessible au quatrième processus P3 est, en l’occurrence, le douzième indice de la liste compactée cL (l’indice 11). Le quatrième processus P3 change alors la valeur initiale « -1 » de l’élément d’indice 19 de la liste compactée cL en la remplaçant par la valeur de l’indice de l’élément L lu, à savoir la valeur « 19 ».

A l’issue du quatrième processus P3, les valeurs des éléments des autres indices accessibles de la liste compactée cL, en l’occurrence les indices 15 et 19, ne sont pas modifiées et restent donc à la valeur initiale de « -1 ».

La illustre les résultats des quatre compactages effectués par chacun des processus P0, P1, P2 et P3.

Plus précisément, sur cette , la première liste modifiée par le premier processus P0 est représentée à la première ligne ; la deuxième liste modifiée par le deuxième processus P1 est représentée à la deuxième ligne en dessous de la première ligne ; la troisième liste modifiée par le troisième processus P2 est représentée à la troisième ligne en dessous de la deuxième ligne et la quatrième liste modifiée par le quatrième processus P3 est représentée à la quatrième ligne en dessous de la troisième ligne.

Dans cette représentation, les éléments concernés par les processus sont représentés en grisé.

La liste compactée cL finale correspond à la valeur grisée. Il est ainsi obtenu une liste dans laquelle des éléments d’indice 0 à 7 ont la valeur d’un indice de la liste L ainsi que l’élément d’indice 11 alors que les éléments ayant un indice compris entre 8 et 10 et un indice supérieur ou égal à 12 ont une valeur restée à la valeur initiale.

La technique de compactage illustrée à travers les figures 3 à 7 permet de paralléliser la tâche de compactage de la liste L.

En effet, les processus P0 à P3 peuvent être conçus comme le passage d’un « peigne » sur la liste L comme schématiquement représenté sur les figures 3 à 6. Autrement formulé, les processus P0 à P3 sont indépendants les uns des autres et peuvent être réalisés simultanément par un cœur 18 différent, ici quatre cœurs 18.

Autrement formulé, dans le cas proposé, chaque cœur 18 traite tous les indices ayant le même reste de la division euclidienne par le nombre 4 (en désignant par abus de langage le fait de traiter l’élément ayant l’indice par le fait de traiter l’indice).

En l’occurrence, au premier cœur 18 est attribué le reste 0, au deuxième cœur 18 est attribué le reste 1, au troisième cœur 18 est attribué le reste 2 et au quatrième cœur 18 est attribué le reste 3. Ainsi, mathématiquement, cela signifie que le premier cœur 18 traite tous les indices proportionnels à 4, le deuxième cœur 18 traite les indices égaux à 1 modulo 4, le troisième cœur 18 traite les indices égaux à 2 modulo 4 et le quatrième cœur 18 traite les indices égaux à 3 modulo 4.

En considérant un nombre quelconque de cœurs 18, cela signifie qu’à chaque cœur 18 est attribué un reste respectif de la division euclidienne par le nombre de cœurs et que chaque cœur traite l’ensemble des indices dont le reste de la division euclidienne de l’indice par le nombre de cœurs est égal au reste respectif.

Le principe d’attribution d’indices spécifiques à chaque cœur 18 qui vient d’être décrit peut être généralisé.

En effet, la seule contrainte est que l’ensemble des indices de la liste courante soit attribué à l’un au moins des cœurs 18.

Il est à noter qu’un principe d’attribution confiant le même nœud à plusieurs cœurs 18 entraînerait des évaluations redondantes dans la technique AGSI sans que cela ne fausse les calculs. Un tel principe d’attribution, a priori moins favorable, pourrait toutefois être choisi s’il permettait une exécution plus rapide par chaque cœur 18.

La technique de compactage peut également être réalisée avec une opération d’initialisation différente. Il convient seulement que la valeur inscrite soit reconnue de façon non équivoque comme non valide lors de la technique AGSI. Autrement formulé, cette valeur ne correspond à aucune valeur possible d’indice d’élément.

Par exemple, une autre valeur que la valeur « -1 » peut être utilisée comme valeur d’initialisation au début du processus pour la liste compactée cL.

En variante, il est possible de prendre toute valeur négative en valeur d’initialisation pour la liste compactée cL.

Selon une autre variante, si le nombre d’éléments au sein du domaine est N, alors il est possible de prendre toute valeur comme valeur d’initialisation.

En tenant compte de tous les modes de réalisation précités, la technique de compactage peut être décrite comme suit.

La technique de compactage comporte une opération d’initialisation de la liste compactée à une valeur d’initialisation.

La technique de compactage comporte également, pour chaque cœur 18, une opération de détermination et une opération de modification éventuelle. Pour chaque cœur 18, l’opération de détermination est mise en œuvre pour plusieurs indices spécifiques au cœur 18 considéré. Pour chaque indice appartenant à ces indices spécifiques, l’opération de détermination consiste à vérifier si l’élément ayant l’indice considéré vérifie une condition binaire.

L’opération de détermination permet ainsi de déterminer l’ensemble des éléments dont l’indice appartient aux indices spécifiques et qui vérifie la condition binaire.

L’opération de modification éventuelle est uniquement mise en œuvre pour les éléments déterminés à l’opération de détermination.

Autrement formulé, l’opération de modification est une modification d’une valeur de la liste compactée uniquement s’il est déterminé que la condition binaire est vérifiée.

La valeur modifiée est celle correspondant à l’indice le plus petit de l’ensemble des indices spécifiques au cœur et n’ayant pas subi de modifications.

D’un point de vue mathématique, on peut écrire le pseudocode qui suit :

initialisation: pour chaque élément

compactage: Pour chaque processus

Na = 0
Tant que
- si

Le procédé de compactage de liste choisi par le demandeur présente la particularité de laisser des trous au sein de la liste compactée. On voit sur la trois valeurs non valides (-1) encadrées. A titre de comparaison, la méthode proposée par (A massively parallel Eikonal solver on unstructured meshes, D. Ganellari, G. Haase, 2018) produit une liste sans trou. La présence de trou dans la liste compactée cL se traduit par une occupation a priori moins optimale des processeurs 18 (certains étant affectés à des tâches vides). Toutefois, la méthode de compactage du demandeur présente un temps d’exécution plus réduite que celle évoquée par D. Ganellari et al. Il s’en suit que la performance de l’ensemble est avantageuse.

Il s’en suit également qu’une information supplémentaire, notée Na, doit être collectée pendant ou après la phase de compactage de liste. Na désigne le plus grand indice de cL contenant une valeur d’indice valide.

Sur l’exemple rapporté en , Na = 10, dit autrement, tout indice de cL de valeur supérieure à 10 contient -1.

Le procédé de détermination correspond à l’utilisation de la technique de compactage dans la technique AGSI.

La technique AGSI peut être décrite comme la mise en œuvre de deux phases :

une phase de réception des données d’entrées suivantes:
- Un domaine contenant un ensemble de points x associés chacun à un indice unique i
- Pour tout point x du domaine , les ensembles et appelés stencils directs et indirects, ainsi que la formule d’Hopf-Lax en ce point
- Pour tout point x d’un ensemble D, la valeur U(x) en ce point
- Une valeur de seuil
une phase de détermination de la grandeur physique U(x) en tout point de \D par utilisation d’itérations AGSI successives, chaque itération comprenant la mise en œuvre de calculs uniquement sur des points contenus dans une liste L et l’actualisation de la liste en fonction des calculs mis en œuvre, les itérations étant mises en œuvre jusqu’à ce que la liste courante soit vide.

Aussi, le procédé de détermination comporte une phase de réception et une phase de détermination.

Chaque itération comporte une étape de transformation, une étape de lecture, une étape de mise en œuvre et une étape d’actualisation.

L’étape de transformation transforme une liste courante L en une liste compactée courante cL.

La liste courante comporte des points de l’environnement prédéfini auxquels sont attribués un nombre.

Chaque point est repéré par un indice.

Des indices spécifiques sont attribués à chaque cœur 18 de la pluralité de cœurs 18, l’ensemble des indices de la liste courante étant attribué à l’un des cœurs 18.

La transformation comporte l’initialisation de la liste compactée à une valeur d’initialisation.

La transformation comporte également pour chaque cœur 18 de la pluralité de cœurs 18 la détermination pour chaque point de la liste courante présentant un indice compris parmi des indices spécifiques au cœur 18 considéré si une condition binaire est vérifiée, pour obtenir un élément déterminé lorsque la condition binaire est vérifiée.

La transformation comprend aussi, pour chaque point de la liste courante déterminé, la modification d’une valeur de la liste compactée n’ayant pas été modifiée et présentant l’indice le plus petit de l’ensemble des indices spécifiques au cœur 18 considéré.

La lecture est une lecture des valeurs de la liste compactée courante différentes de la valeur d’initialisation pour obtenir les points vérifiant la condition binaire.

La mise en œuvre est une étape de mise en œuvre de calculs uniquement sur les points déterminés.

Les calculs comportent une opération de test de convergence de la valeur du point, une opération d’élimination du point ayant fait l’objet de l’opération de test de la liste courante, et une opération d’ajout de points uniquement si le test de convergence n’est pas satisfait, les points ajoutés étant de préférence les points du stencil négatif.

L’étape d’actualisation est une étape d’actualisation de la liste en fonction des calculs mis en œuvre.

Les itérations sont mises en œuvre jusqu’à ce que la liste courante soit vide.

Ce qui vient d’être décrit pour le procédé de détermination peut être décrit de manière équivalente comme suit.

Le domaine peut-être découpé en sous-domaines, de telle façon que chaque élément x du domaine appartient à un sous-domaine et un seul. Les listes L et cL ne désignent alors plus les indices des éléments x, mais les indices des sous-domaines auxquels ils sont associés.

Le découpage de en N sous-domaines accroît l’efficacité de résolution par une architecture parallèle car il permet de regrouper astucieusement les nœuds de façon à optimiser les accès à la mémoire centrale. Par exemple, il peut être avantageusement envisagé une stratégie de définition de sous-domaines au sein desquels tous les nœuds partagent certaines valeurs de paramètres, ce qui permet de les charger une fois pour toute en mémoire locale et de les utiliser ensuite pour chacun des nœuds du sous-domaine. Une telle stratégie est a priori plus favorable puisqu’elle repose sur l’emploi de mémoire locale et minimise les accès à la mémoire centrale.

Par ailleurs, le découpage de en N sous-domaines permet également de découpler la taille de la liste à compacter à chaque itération du nombre total d’éléments x du domaine et donc de compacter des listes plus courtes. Par exemple, en groupant les nœuds par sous-domaines de taille 64, une liste 64 fois moins grande à chaque itération est compactée.

Le domaine contient points et est découpé en sous-domaines.

Les notations qui suivent sont utilisées dans la série d’instructions qui décrit le procédé :

est une fonction retournant l’indice du sous-domaine auquel appartient le nœud . Cette fonction peut être implémentée de diverses façons, comme par exemple une table calculée à l’avance.
) est la fonction d’Hopf-Lax utilisée
et sont deux tableaux de booléens de taille appelés « liste courante des sous-domaines actifs » et « liste suivante des sous-domaines actifs »
et sont deux tableaux de taille appelés « distances courantes des sous-domaines actifs » et « distances suivantes des sous-domaines actifs »
est un tableau d’entiers de taille appelé « liste compactée des sous-domaines actifs »
est le plus grand indice de cL contenant une valeur valide

Avec ces notations, le procédé s’écrit ainsi :

Boucle principale:

AMELIORATION = VRAI

Tant que AMELIORATION = VRAI :

AMELIORATION = FAUX

Lancer en parallèle pour

RECUP_NA(cL):

Cette fonction peut être réalisée en lançant en parallèle N processus réalisant chacun :

Si :

Cette fonction peut également être réalisée pendant la fonctionCOMPACTER. Le pseudo code de COMPACTER est alors modifié comme suit (en gras):

D’un point de vue mathématique, on peut écrire le pseudocode qui suit :

initialisation: pour chaque élément

compactage: Pour chaque processus

Na = 0
Tant que
- si

Na = max(Na, )

COMPACTER(L):

Compacter L suivant la méthode détaillée précédemment.

SOLVE(a, cL):

s = cL(a)

Si s est non valide (ici: si s = -1), quitter.

Pour tout nœud appartenant au sous-domaine s :

= U1(CURR, p)

= F(p, (p) )

Si < et si | – | < :

AMELIORATION = VRAI

Pour tout voisin de (p) :

= SOUS_DOMAINE( )

( ) = VRAI

(s) = FAUX

Un tel procédé permet de résoudre l’équation avec efficacité pour obtenir la grandeur respectant les contraintes tout en permettant une parallélisation dans l’implémentation informatique du procédé.

Le procédé de compactage bénéficie de l’avantage de sa simplicité et de sa rapidité d’exécution, qui compense la présence de trous, et donc d’une occupation parfois sous optimale de processeurs 18.

Ainsi, le procédé de détermination d’une grandeur physique bénéficie de l’avantage de la généralité de la technique AGSI et de sa simplicité de mise en œuvre et compense sa complexité algorithmique par l’emploi d’une technique de compactage permettant une mise en œuvre parallèle.

Le procédé peut être utilisé pour d’autres techniques itératives utilisant une liste évolutive comme la technique AGSI. Par exemple, il pourrait être envisagé d’utiliser une technique appelée « Hamilton Fast Marching Dubins ».

Le procédé vient d’être décrit pour la détermination de trajectoires mais pourrait également être utilisé pour le domaine des images.

Par exemple, le système de détermination 10 délimite l’artère (segmentation d’image) ou détermine le débit dans une artère (déduction d’une mesure physique sur la base d’images).

Dans chacun des cas qui viennent d’être décrits, il apparaît bien que le procédé présenté comporte deux phases : une phase de réception de données d’entrées et une phase de détermination de la grandeur physique par utilisation d’une technique de résolution du système d’équations différentielles, pour obtenir la grandeur physique respectant la contrainte.

Les données d’entrées comprennent des mesures de la contrainte en plusieurs points de l’environnement prédéfini.

La technique de résolution est une technique itérative avec des itérations d’une opération de transformation, d’initialisation, de détermination, de modification, de lecture, de mise en œuvre et d’actualisation. Les itérations sont mises en œuvre jusqu’à ce que la liste courante soit vide.

L’opération de transformation est une opération de transformation d’une liste courante en une liste compactée courante, la liste courante comportant des points de l’environnement prédéfini auxquels sont attribués un nombre, chaque point étant repéré par un indice, des indices spécifiques étant attribués à chaque cœur 18, l’ensemble des indices de la liste courante étant attribué à l’un des cœurs 18.

La transformation comprend l’opération d’initialisation qui correspond à l’initialisation de la liste compactée à une valeur d’initialisation.

Par ailleurs, les opérations de détermination et de modification d’une valeur de la liste compactée sont mises en œuvre pour chaque cœur 18 durant la transformation.

En particulier, la détermination cherche à savoir si pour chaque point de la liste courante présentant un indice compris parmi des indices spécifiques au cœur 18 considéré, la condition binaire précitée est vérifiée.

Ensuite, la valeur de la liste compactée n’ayant pas été modifiée et ayant l’indice le plus petit est modifiée pour chaque point de la liste courante déterminé.

Lors de l’opération de lecture, les valeurs de la liste compactée courante différentes de la valeur d’initialisation sont lues pour obtenir les points vérifiant la condition binaire.

Ensuite, il est mis en œuvre les calculs uniquement sur les points déterminés et la liste est actualisée en fonction des calculs mis en œuvre.

Un tel procédé permet donc bien de gagner en rapidité sans perte en précision.

Claims

Procédé de détermination d’une grandeur physique, la grandeur physique vérifiant un système d’équations différentielles d’Hamilton-Jacobi pour respecter une contrainte variant spatialement dans un environnement prédéfini, le procédé étant mis en œuvre par un système de détermination (10) de la grandeur physique, le système de détermination (10) comprenant une pluralité de cœurs (18), le procédé comportant :
- une phase de réception de données d’entrées, les données d’entrées comprenant des mesures de la contrainte en plusieurs points de l’environnement prédéfini,
- une phase de détermination de la grandeur physique par utilisation d’une technique de résolution du système d’équations différentielles, pour obtenir la grandeur physique respectant la contrainte, la technique de résolution comportant plusieurs itérations, chaque itération comportant les étapes suivantes:
- la transformation d’une liste courante en une liste compactée courante, la liste courante comportant des points de l’environnement prédéfini auxquels sont attribués un nombre, chaque point étant repéré par un indice, des indices spécifiques étant attribués à chaque cœur (18) de la pluralité de cœurs (18), l’ensemble des indices de la liste courante étant attribué à l’un des cœurs (18), la transformation comprenant :
- l’initialisation de la liste compactée à une valeur d’initialisation,
- pour chaque cœur (18) de la pluralité de cœurs (18) :
- la détermination pour chaque point de la liste courante présentant un indice compris parmi des indices spécifiques au cœur (18) considéré si une condition binaire est vérifiée, pour obtenir un élément déterminé lorsque la condition binaire est vérifiée, et
- pour chaque point de la liste courante déterminé, la modification d’une valeur de la liste compactée n’ayant pas été modifiée et présentant l’indice le plus petit de l’ensemble des indices spécifiques au cœur (18) considéré,
- la lecture des valeurs de la liste compactée courante différentes de la valeur d’initialisation pour obtenir les points vérifiant la condition binaire,
- la mise en œuvre de calculs uniquement sur les points déterminés, et
- l’actualisation de la liste en fonction des calculs mis en œuvre,
les itérations étant mises en œuvre jusqu’à ce que la liste courante soit vide.
Procédé selon la revendication 1, dans lequel le nombre d’indices spécifiques est le même pour chaque cœur (18).
Procédé selon la revendication 1 ou 2, dans lequel, à chaque cœur (18) est attribué un reste respectif de la division euclidienne par le nombre de cœurs (18), l’ensemble des indices spécifiques au cœur (18) considéré comprenant l’ensemble des indices dont le reste de la division euclidienne de l’indice par le nombre de cœurs (18) est égal au reste respectif.
Procédé selon l’une quelconque des revendications 1 à 3, dans lequel chaque nombre attribué est un nombre binaire et la condition binaire est que le nombre binaire attribué est égal à une valeur prédéfinie.
Procédé selon l’une quelconque des revendications 1 à 4, dans lequel la valeur d’initialisation est une valeur négative.
Procédé selon l’une quelconque des revendications 1 à 5, dans lequel l’opération d’initialisation est également mise en œuvre par chaque cœur (18) uniquement pour les indices spécifiques au cœur (18) considéré.
Procédé selon l’une quelconque des revendications 1 à 6, dans lequel la mise en œuvre itérative de calculs est réalisée jusqu’à ce que la liste courante soit vide.
Procédé selon l’une quelconque des revendications 1 à 7, dans lequel, les calculs comportent une opération de test de convergence de la valeur du point.
Procédé selon la revendication 8, dans lequel, pour chaque point, il est défini un stencil négatif, les calculs comportent également :
- une opération d’élimination du point ayant fait l’objet de l’opération de test de la liste courante, et
- une opération d’ajout de points uniquement si le test de convergence n’est pas satisfait, les points ajoutés étant de préférence les points du stencil négatif.
Procédé selon l’une quelconque des revendications 1 à 9, dans lequel les contraintes sont des mesures d’au moins un capteur.
Système de détermination (10) d’une grandeur physique, la grandeur physique vérifiant un système d’équations différentielles d’Hamilton-Jacobi pour respecter une contrainte variant spatialement dans un environnement prédéfini, le système de détermination (10) comprenant une pluralité de cœurs (18), le système de détermination (18) étant propre à mettre en œuvre un procédé de détermination d’une grandeur physique, le procédé comportant :
- une phase de réception de données d’entrées, les données d’entrées comprenant des mesures de la contrainte en plusieurs points de l’environnement prédéfini,
- une phase de détermination de la grandeur physique par utilisation d’une technique de résolution du système d’équations différentielles, pour obtenir la grandeur physique respectant la contrainte, la technique de résolution comportant plusieurs itérations, chaque itération comportant les étapes suivantes:
- la transformation d’une liste courante en une liste compactée courante, la liste courante comportant des points de l’environnement prédéfini auxquels sont attribués un nombre, chaque point étant repéré par un indice, des indices spécifiques étant attribués à chaque cœur (18) de la pluralité de cœurs (18), l’ensemble des indices de la liste courante étant attribué à l’un des cœurs (18), la transformation comprenant :
- l’initialisation de la liste compactée à une valeur d’initialisation,
- pour chaque cœur (18) de la pluralité de cœurs (18) :
- la détermination pour chaque point de la liste courante présentant un indice compris parmi des indices spécifiques au cœur (18) considéré si une condition binaire est vérifiée, pour obtenir un élément déterminé lorsque la condition binaire est vérifiée, et
- pour chaque point de la liste courante déterminé, la modification d’une valeur de la liste compactée n’ayant pas été modifiée et présentant l’indice le plus petit de l’ensemble des indices spécifiques au cœur (18) considéré,
- la lecture des valeurs de la liste compactée courante différentes de la valeur d’initialisation pour obtenir les points vérifiant la condition binaire,
- la mise en œuvre de calculs uniquement sur les points déterminés, et
- l’actualisation de la liste en fonction des calculs mis en œuvre, et
les itérations étant mises en œuvre jusqu’à ce que la liste courante soit vide.