Brevet FR2979026A1 — publié le 20130215

-1- « Procédé pour simuler une propagation dans un domaine prédéterminé, support et produit programme d'ordinateur associés » Domaine technique La présente invention concerne un procédé pour simuler une propagation, dans un domaine prédéterminé, d'une onde émise par au moins une source. Le domaine prédéterminé est défini par une géométrie, au moins une source et comprend plusieurs capteurs virtuels, agencés pour mesurer en plusieurs points de la géométrie du domaine une donnée caractéristique telle qu'une énergie acoustique, une intensité lumineuse, une énergie d'un rayonnement électromagnétique quelconque ou une concentration de particules. Elle concerne également un produit programme d'ordinateur agencé pour exécuter les étapes du procédé selon l'invention lorsqu'il est exécuté dans au moins un ordinateur. Elle concerne également un support pouvant être lu par au moins un ordinateur, qui comporte enregistré un produit programme d'ordinateur agencé pour exécuter les étapes du procédé selon l'invention lorsqu'il est exécuté dans au moins un ordinateur. Le domaine de l'invention est plus particulièrement mais de manière non limitative celui des simulations acoustiques, optiques ou particulaires. On peut également mettre en oeuvre l'invention pour simuler la propagation de particules se propageant en première approximation selon les lois de l'optique géométrique. Etat de la technique antérieure La mesure d'une donnée caractéristique au niveau d'un capteur virtuel du domaine prédéterminé prend en compte les contributions de toutes les portions d'onde du domaine prédéterminé, reçues par ledit capteur virtuel. On parlera dans la suite de traitement global pour désigner l'ensemble des étapes de chargement de données, calcul de propagation, mesure de données caractéristiques, collecte de résultats, et aboutissant à un résultat formé par la mesure de la donnée caractéristique associée à chacun des 2979026 -2- capteurs virtuels du domaine et prenant en compte les contributions de toutes les portions d'onde se propageant dans le domaine prédéterminé et reçues par ledit capteur virtuel associé. 5 On connaît des méthodes dites numériques de simulation de la propagation d'une onde sonore. De telles méthodes mettent par exemple en oeuvre une modélisation par la méthode des éléments finis ou par la méthode des éléments infinis. Les méthodes numériques présentent l'avantage de fournir un résultat 10 très précis et physiquement correct, mais elles requièrent énormément de capacité de calcul et de mémoire. Ces méthodes numériques ne permettent que difficilement de traiter des propagations à travers de vastes domaines, telles que des propagations d'onde en domaine extérieur. 15 On connaît également dans l'art antérieur des méthodes dites géométriques, de simulation de la propagation d'une onde, notamment une onde sonore. Ces méthodes supposent qu'au moins en première approximation la 20 propagation s'effectue en ligne droite, et permettent un traitement rapide relativement aux méthodes numériques. Afin d'améliorer la vitesse de traitement global, on peut mettre en oeuvre des méthodes de parallélisation, consistant à répartir les étapes à mettre en oeuvre, entre différentes unités d'exécution. 25 Une unité d'exécution peut désigner notamment un programme, ensemble d'un ou plusieurs processus ou un ensemble d'une ou plusieurs tâches (l'homme du métier utilisant de préférence le terme anglais « thread »). Un programme est défini par un ensemble d'instructions à exécuter, un 30 espace mémoire pour les données de travail, et le cas échéant d'autres ressources telles que des ports réseaux, etc. Un même programme peut se décomposer en plusieurs processus, chacun exécutant certaines instructions du programme seulement. Un processus comprend son propre espace mémoire. -3- Un même processus peut se décomposer en plusieurs « threads », qui vont s'exécuter simultanément en partageant les mêmes données en mémoire. Les méthodes de parallélisation connues travaillent sur une répartition des portions d'onde (rayons, faisceaux, etc) parmi plusieurs unités d'exécution. Chaque unité d'exécution traite un paquet de portions d'onde se propageant dans l'ensemble du domaine prédéterminé. Cette répartition des portions d'onde peut mettre en oeuvre différents types d'algorithmes. On peut citer par exemple les algorithmes de partage statique (on parle en anglais de « static partioning algorithms »), mettant en oeuvre une répartition entre plusieurs unités d'exécution, lors d'une étape initiale préalable à tout calcul de propagation. La vitesse de traitement global peut être augmentée en utilisant plutôt des algorithmes de partage dynamique (on parle en anglais de « dynamic partioning algorithms »). Selon ces algorithmes, un processus central répartit des données à traiter entre plusieurs unités d'exécution, en cours de traitement d'autres données par les unités d'exécution. On peut également augmenter la vitesse de traitement global en mettant en oeuvre des algorithmes de rerépartition du travail (on utilise plutôt le terme anglais « work-stealing algorithm »). L'idée est de répartir initialement toutes les données à traiter, puis une fois les calculs avancés, de reprendre des données à un processus pour les réaffecter à un autre. Un inconvénient de ces méthodes est que la vitesse de traitement global 25 reste limitée. Un objectif de la présente invention est de proposer un procédé pour simuler une propagation dans un domaine prédéterminé, d'au moins une portion d'onde émise par au moins une source, et qui ne présente pas au 30 moins l'un des inconvénients précité de l'art antérieur. En particulier, un objectif de la présente invention est de proposer un tel procédé qui permette d'obtenir une plus grande vitesse de traitement global. Un autre objectif de la présente invention est de proposer un tel procédé qui permette de traiter plus efficacement des propagations à travers de vastes 35 domaines, telles que des propagations d'onde en extérieur. 2979026 -4- Un objectif supplémentaire de la présente invention est de proposer un produit programme d'ordinateur agencé pour exécuter les étapes d'un tel procédé lorsqu'il est exécuté dans au moins un ordinateur. Un autre but de la présente invention est de proposer un support 5 pouvant être lu par au moins un ordinateur, qui comporte enregistré un produit programme d'ordinateur agencé pour exécuter les étapes du procédé selon l'invention lorsqu'il est exécuté dans au moins un ordinateur. Exposé de l'invention 10 Au moins l'un des objectifs précités est atteint avec un procédé pour simuler une propagation dans un domaine prédéterminé, le domaine prédéterminé étant défini par une géométrie, au moins une source et comprenant plusieurs capteurs virtuels, le procédé mettant en oeuvre : - un calcul de la propagation, dans le domaine, d'au moins 15 une portion d'onde émise par la source, et - pour chaque capteur virtuel, une mesure d'une donnée caractéristique des portions d'onde reçues par celui-ci. Le procédé selon l'invention comprend en outre : - une étape de décomposition du domaine en plusieurs sous 20 domaines comprenant chacun un sous ensemble d'au moins un capteur virtuel ; et - une étape d'allocation des sous domaines réalisant la répartition d'au moins deux d'entre eux entre plusieurs unités d'exécution distinctes. Un sous domaine selon l'invention correspond à une partie seulement du domaine incluant une géométrie, éventuellement une source, et choisi de façon à comprendre au moins un capteur virtuel. L'étape de décomposition en plusieurs sous domaine est de préférence une étape préalable aux calculs et mesures. On parle de portion d'onde, une onde émise par une source et se propageant dans le domaine pouvant être décomposée en plusieurs portions d'onde telles que des faisceaux. Un capteur virtuel peut être un volume. On prend en compte les contributions de chacune des portions d'onde qui le traversent. Le cas 2979026 -5- échéant, on néglige les contributions inférieures à un seuil prédéterminé. Un capteur virtuel peut être une surface. On parle de calcul de propagation dans le domaine, puisque l'ensemble des calculs de propagation dans les sous domaines correspondent à eux tous 5 à un calcul de propagation dans le domaine. Au moins deux sous domaines sont donc répartis entre plusieurs unités d'exécution distinctes. Avantageusement selon l'invention, l'unité d'exécution ne calcule une propagation que dans au moins un sous domaine correspondant et ne mesure 10 une donnée caractéristique que pour au moins un capteur virtuel correspondant. Les calculs et mesures, associés aux au moins deux sous domaines alloués à des unités d'exécution distinctes, peuvent être effectués en parallèle. 15 L'idée à la base de l'invention, est de mettre en oeuvre une parallélisation des calculs et mesures par un découpage en sous domaines formant le domaine. Selon l'art antérieur, la parallélisation des calculs utilisant uniquement une attribution des faisceaux à différentes unités d'exécution nécessite de 20 mettre en oeuvre une étape supplémentaire de croisement des informations. En effet, la mesure par une unité d'exécution, d'une donnée caractéristique au niveau d'un capteur virtuel, prend en compte uniquement les contributions des portions d'onde attribuées à ladite unité d'exécution. Il est donc nécessaire, pour chaque capteur virtuel, de collecter les contributions des 25 différents paquets de faisceaux pour obtenir la mesure finale de la donnée caractéristique associée au capteur virtuel. Cette étape supplémentaire de croisement des informations peut être mise en oeuvre par exemple par : - une collecte de résultats mettant en oeuvre une librairie par 30 exemple MPI (pour l'anglais « Message Passing Interface ») ou PVM (pour l'anglais « Parallel Virtual Machine »), lorsque les calculs sont mis en oeuvre dans plusieurs unités d'exécutions formées des processus ; - une collecte de résultats mettant en oeuvre une duplication ou un 35 partage d'une matrice de résultats, lorsque les calculs sont mis en 2979026 -6- oeuvre dans plusieurs unités d'exécutions formées des « threads » d'un même processus. Dans le second cas, on doit sécuriser les accès à la matrice de résultats commune en utilisant par exemple un mutex (de l'anglais « mutual exclusion »). 5 - un algorithme hybride de mémoire partagée et distribuée (en anglais « hybrid distributed/shared memory algorithm »). Il s'agit de l'algorithme utilisé lorsque les calculs sont mis en oeuvre dans plusieurs unités d'exécutions formées par des « threads » regroupés en plusieurs processus. 10 L'envoi d'informations par chaque unité d'exécution en vue d'additionner différentes contributions pour un même capteur virtuel est une opération séquentielle. A l'inverse, selon l'invention, chaque unité d'exécution mesure directement une donnée caractéristique associée à un capteur virtuel et 15 comprenant déjà l'ensemble des contributions des différents faisceaux se propageant dans le domaine. L'étape de croisement des informations n'est donc plus nécessaire pour obtenir une mesure finale correspondant à un capteur virtuel donné. L'ensemble des étapes mises en oeuvre dans le cadre du traitement 20 global peut donc être parallélisé. Or, on sait d'après la loi d'Amdahl que la vitesse globale d'un programme dépend directement du taux de parallélisation de ce programme. L'augmentation du taux de parallélisation du traitement global permet ainsi d'augmenter la vitesse de ce traitement par rapport à l'art antérieur (à 25 capacité de calcul du matériel égale, domaine égal, jeu de capteurs virtuels identiques, et découpage des ondes en portions d'onde identique). On peut ainsi traiter des propagations à travers de vastes domaines, telles que des propagations d'onde en extérieur, tout en obtenant un temps de traitement global restreint. 30 On peut ainsi obtenir en temps réel ou quasi réel le résultat du traitement global. On peut également envisager de partager une onde en de très nombreuses portions d'ondes, de façon à augmenter la précision du résultat, et ce sans que le temps de traitement global n'augmente autant que le temps de traitement global obtenu dans l'art antérieur. -7- On peut également envisager de mettre en oeuvre un nombre de capteurs virtuels plus élevé, de façon à augmenter le nombre de mesures disponibles, et ce sans que le temps de traitement global n'augmente autant que le temps de traitement global obtenu dans l'art antérieur. On peut également envisager de prendre en compte toutes les sources présentes dans un domaine, même des sources que l'on préfère négliger dans l'art antérieur en raison du temps de traitement global selon l'art antérieur qui deviendrait alors considérable. En outre, l'allocation à une unité d'exécution distincte, d'un sous 10 domaine plutôt que d'un domaine complet, permet de répartir entre les différentes unités d'exécution les étapes liées : - au chargement de données à traiter, et - aux calculs de propagation d'une portion d'onde. Il s'agit notamment des étapes de détection des intersections 15 d'une portion d'onde avec une surface du domaine. On peut ainsi optimiser l'utilisation des ressources en capacité de calcul et en mémoire des unités d'exécution utilisées. Cela permet d'améliorer la vitesse de traitement global. Le chargement des données à traiter, par des unités d'exécution, peut 20 être effectué en parallèle, une fois le domaine décomposé en plusieurs sous domaines. Le procédé selon l'invention est avantageusement utilisé pour obtenir des résultats les plus proches possibles de ceux qui pourraient être mesurés en réalité, à l'aide de capteurs réels, dans un espace identique au domaine 25 étudié. En outre, un découpage d'un domaine en plusieurs sous domaines peut être réutilisé pour d'autres simulations. Pour chaque sous domaine, on peut en outre mettre en oeuvre des algorithmes de parallélisation par partage de faisceaux tels que présentés en 30 introduction. On diminue ainsi le temps de traitement global. De préférence, chaque unité d'exécution met ensuite en oeuvre les étapes de : 2979026 -8- - calcul de la propagation, uniquement dans l'au moins un sous domaine correspondant, d'au moins une portion d'onde, et - pour chaque capteur virtuel contenu dans l'au moins un 5 sous domaine correspondant, mesure d'une donnée caractéristique des portions d'onde reçues par celui-ci. Ces étapes sont avantageusement mises en oeuvre en parallèle dans les différentes unités d'exécution. L'unité d'exécution associée à au moins un sous domaine considéré 10 correspond à l'unité d'exécution à laquelle l'au moins un sous domaine considéré a été alloué. L'unité d'exécution associée à au moins un sous domaine considéré met avantageusement en oeuvre les étapes suivantes : - calcul de la propagation d'une portion d'onde dans le sous domaine 15 considéré ; - si ledit calcul montre que la portion d'onde atteint un sous domaine voisin, communication à une unité d'exécution associée audit sous domaine voisin, de données relatives à la propagation en dehors du sous domaine considéré et dans le sous domaine voisin. 20 On peut ainsi gérer la propagation d'une portion d'onde à travers l'ensemble du domaine, tout en n'allouant à une unité d'exécution qu'une partie de ce domaine. De préférence, lesdites données relatives à une propagation d'une portion d'onde en dehors du sous domaine considéré et dans le sous domaine 25 voisin comprennent : - un vecteur directeur ; - des coordonnées ; - une donnée caractéristique ; relatifs à la portion d'onde se propageant en dehors du sous domaine 30 considéré et dans le sous domaine voisin, et mesurés à la sortie du sous domaine considéré. De préférence, deux sous domaines voisins sont contigus, des mesures à la sortie d'un sous domaine étant alors équivalentes à des mesures à l'entrée du sous domaine voisin correspondant. 2979026 -9- Des étapes de calcul de la propagation d'une portion d'onde dans le sous domaine considéré et de communication de données relatives à une propagation dans le sous domaine voisin, peuvent être mises en oeuvre simultanément, chacune pour une portion d'onde distincte. 5 Un calcul de la propagation d'une portion d'onde utilise les capacités de calcul de l'unité d'exécution. Une communication de données utilise les capacités de transmission d'information de l'unité d'exécution. Les deux étapes n'interfèrent pas entre elles, et la mise en oeuvre de 10 l'une n'influe pas sur les capacités de l'unité d'exécution qui peuvent être disponibles pour l'autre. On peut ainsi augmenter la vitesse de traitement global. On peut également mettre en oeuvre une étape de mesure d'une donnée caractéristique d'une portion d'onde reçue par un capteur virtuel, 15 simultanément à ladite communication de données. De préférence, l'étape d'allocation des sous domaines, réalisant la répartition d'au moins deux d'entre eux entre plusieurs unités d'exécution distinctes, comprend en outre le chargement d'une géométrie simplifiée des sous domaines voisins entourant le sous domaine considéré. 20 Une telle étape facilite l'identification par une unité d'exécution d'une unité d'exécution, à laquelle elle doit communiquer des données relatives à une propagation d'une portion d'onde en dehors du sous domaine considéré et dans le sous domaine voisin. On charge une géométrie simplifiée et non une géométrie détaillée des 25 sous domaines voisins entourant le sous domaine considéré afin de limiter les capacités de mémoire requises pour une unité d'exécution. L'unité d'exécution associée à un sous domaine considéré peut mettre en oeuvre les étapes suivantes : - réception de données fournies par une unité d'exécution associée à un 30 sous domaine voisin, et relatives à une propagation d'une portion d'onde dans le sous domaine considéré et en dehors dudit sous domaine voisin ; - calcul de la propagation de cette portion d'onde dans le sous domaine considéré. 2979026 -10- De préférence, les données fournies par une unité d'exécution associée à un sous domaine voisin, et relatives à une propagation d'une portion d'onde dans le sous domaine considéré et en dehors dudit sous domaine voisin, comprennent : 5 - un vecteur directeur ; - des coordonnées ; - une donnée caractéristique ; relatifs à la portion d'onde se propageant dans le sous domaine considéré et en dehors dudit sous domaine voisin, et mesurés à la sortie du sous domaine voisin. Avantageusement, des étapes de réception de données fournies par une unité d'exécution associée à un sous domaine voisin et de calcul de la propagation de la portion d'onde sont mises en oeuvre simultanément, chacune pour une portion d'onde distincte. On peut également mettre en oeuvre une étape de mesure d'une donnée caractéristique d'une portion d'onde reçue par un capteur virtuel, simultanément à ladite réception de données. Un calcul de la propagation d'une portion d'onde utilise les capacités de calcul de l'unité d'exécution. On peut ainsi augmenter la vitesse de traitement global, pour les raisons évoquées ci-avant à propos d'un calcul de la propagation d'une portion d'onde simultanément à une communication de données. Une unité d'exécution peut recevoir des sous domaines initialement alloué une autre unité d'exécution, de façon à homogénéifier des temps de 25 traitement entre les unités d'exécution. En particulier, les différentes unités d'exécution n'ont nécessairement ni les même capacités de calcul, ni le même nombre de portions d'onde à traiter. Or, le temps de traitement global est limité par le temps de traitement le plus long parmi l'ensemble des temps de traitement des différentes unités 30 d'exécution. On diminue donc le temps de traitement global en reportant des sous domaines d'une unité d'exécution à l'autre, de façon à obtenir des temps de traitements les plus proches possibles entre les différentes unités d'exécution. De préférence, l'unité d'exécution démarre avec un ou plusieurs sous 35 domaines. Lorsqu'elle n'a plus que quelques portions d'onde à traiter, elle -11- commence à charger un ou plusieurs autres sous domaines dans lesquels il reste beaucoup de portions d'onde à traiter. Dans une unité d'exécution, on peut effectuer simultanément des étapes de traitement de portion d'onde et de transmission de résultats déjà 5 obtenus vers une unité de collecte de résultats. Les résultats peuvent être effacés de la mémoire associée à l'unité d'exécution, une fois transmis. Cela libère de la mémoire pour le chargement de nouveaux sous domaines à traiter. Cela diminue également le temps de traitement global, car la transmission des résultats s'effectue au moins en 10 partie parallèlement aux calculs et mesures effectuées par l'unité d'exécution. Avantageusement, l'unité d'exécution associée à au moins un sous domaine considéré, tour à tour pour chaque portion d'onde, met en oeuvre les étapes suivantes : - calcul de la propagation de la portion d'onde dans le sous domaine 15 considéré ; - si ledit calcul montre que la portion d'onde atteint un sous domaine voisin, communication à une unité d'exécution associée audit sous domaine voisin, de données relatives à la propagation en dehors du sous domaine considéré et dans le sous domaine voisin. 20 En outre, l'unité d'exécution associée à au moins un sous domaine considéré peut, tour à tour pour chaque portion d'onde, mettre en oeuvre les étapes suivantes : - réception de données fournies par une unité d'exécution associée à un sous domaine voisin, et relatives à une propagation d'une portion 25 d'onde dans le sous domaine considéré et en dehors dudit sous domaine voisin ; - calcul de la propagation de cette portion d'onde dans le sous domaine considéré. On peut ainsi obtenir plus rapidement un nombre de portions d'onde 30 total à traiter correspondant à un sous domaine donné. Après un temps de calcul prédéterminé, chaque unité d'exécution peut alors avoir reçu des informations plus fiables quant au nombre total de portions d'onde qu'elle doit traiter. Une unité d'exécution peut ainsi recevoir des sous domaines initialement alloué à une autre unité d'exécution, en 35 prenant en compte ces informations. On limite ainsi le nombre d'échanges de 2979026 -12- sous domaines à traiter entre les unités d'exécutions. Ces échanges prenant du temps sans apporter de résultat supplémentaire, le fait de limiter leur nombre permet de diminuer le temps de traitement global associé au procédé selon l'invention. De préférence, le calcul de propagation d'une portion d'onde met en oeuvre au moins une méthode parmi : - une méthode de lancé de rayons ; - une méthode de lancé de faisceaux ; - une méthode de lancé hybride rayons et faisceaux ; - une méthode de lancé de particules. Une portion d'onde correspond alors respectivement à un rayon, un faisceau, un ensemble hybride rayon et faisceau (on peut parler alors de « poutre »), et un ensemble d'une ou plusieurs particules. La méthode du lancé de rayon divise la contribution de chaque source en un grand nombre de participations élémentaires associées chacune à une particule virtuelle. Chaque particule virtuelle se propage en ligne droite, et sa contribution diminue progressivement en raison de l'atténuation par le milieu traversé, ou lors d'une réflexion sur une surface du domaine. La contribution d'une source peut être par exemple son énergie électromagnétique, notamment optique, ou son énergie acoustique. La méthode du lancé de faisceau divise la contribution de chaque source en un grand nombre de participations élémentaires associées chacune à un faisceau. Les intersections entre un faisceau et une surface sont plus complexes à calculer que des intersections entre une ligne droite et une surface. Il se peut en effet que seule une portion d'un faisceau atteigne une surface, ce qui entraîne la séparation d'un faisceau en plusieurs sous-faisceaux. Chaque faisceau requiert donc plus de traitements qu'un rayon. La méthode du tracé de faisceau est cependant avantageuse car on obtient une même qualité de résultat pour un nombre moins élevé de faisceaux (comparé à un nombre de rayons dans la méthode du tracé de rayons). La méthode de lancé hybride rayons et faisceaux considère des faisceaux associés chacun à un rayon porteur. Seul le rayon porteur est pris en compte pour la détection des intersections avec des surfaces dans un domaine à considérer. Les faisceaux ne sont alors plus séparés en sous-faisceaux. On 2979026 -13- peut également prévoir une séparation en sous-faisceaux uniquement lorsqu'un sous-faisceau atteindrait une ouverture angulaire prédéterminée. La méthode de lancé de particules associe à chaque particule ou groupe de particules une donnée caractéristique telle qu'une énergie. 5 Chaque particule se propage en ligne droite, et sa contribution diminue progressivement en raison de l'atténuation par le milieu traversé, ou lors d'une réflexion sur une surface du domaine. On peut également envisager de mettre en oeuvre la méthode dite « image-source » pour le calcul de propagation d'une portion d'onde. Cette 10 méthode créée des sources virtuelles pour chaque réflexion sur une surface dans le domaine considéré. De préférence, la donnée caractéristique comprend au moins une donnée parmi : - une intensité lumineuse ; 15 - une énergie électromagnétique ; - une intensité acoustique ; - une concentration de particules. De façon générale, le procédé selon l'invention peut s'appliquer à la simulation de toute propagation en ligne droite en première approximation : 20 la lumière, le son, des radiations, tout autre type de particules. Le procédé selon l'invention peut être mis en oeuvre dans au moins un système parmi : - un ordinateur multi-noeuds ; - un ordinateur multi-processeurs ; 25 - un ordinateur mufti-coeurs. Un noeud peut se définir comme une machine permettant de traiter des données. On parle en anglais de « node ». Les données peuvent être traitées dans des noeuds, des processeurs ou des coeurs. Une même machine peut se décomposer en au moins un noeud, 30 composé lui-même d'au moins un processeur, composé lui-même d'au moins un coeur. On peut prévoir d'attribuer un sous domaine par noeud ou par processeur ou par coeur d'un ordinateur. 2979026 -14- L'invention concerne également un produit programme d'ordinateur, agencé pour exécuter les étapes du procédé selon l'invention lorsqu'il est exécuté dans au moins un ordinateur. L'invention concerne également un support pouvant être lu par au 5 moins un ordinateur et comportant enregistré un produit programme d'ordinateur agencé pour exécuter les étapes du procédé selon l'invention lorsqu'il est exécuté dans au moins un ordinateur. Un tel support peut consister en un CD (pour l'anglais « Compact Disc »), une clé USB (pour l'anglais « Universal Serial Bus »), un processeur, 10 etc. Description des figures et modes de réalisation D'autres avantages et particularités de l'invention apparaîtront à la lecture de la description détaillée de mises en oeuvre et de modes de 15 réalisation nullement limitatifs, et des dessins annexés suivants : - la figure 1 illustre un procédé selon l'art antérieur ; - la figure 2 illustre un mode de réalisation de procédé selon l'invention ; - la figure 3 illustre un aspect particulier d'un mode de réalisation de procédé selon l'invention ; 20 - la figure 4 illustre les différentes accélérations de la vitesse de traitement global, obtenues avec différents modes de réalisation de procédé selon l'invention, et avec un procédé selon l'art antérieur, mettant en oeuvre un système Ethernet ; - la figure 5 illustre les différentes accélérations de la vitesse de traitement 25 global, obtenues avec différents modes de réalisation de procédé selon l'invention, et avec un procédé selon l'art antérieur, mettant en oeuvre un système InfiniBand (système de communication à haut débit entre composants d'un ordinateur) ; et - la figure 6 illustre un domaine et les résultats d'une simulation mise en 30 oeuvre pour ce domaine en utilisant un procédé selon l'invention. La figure 1 illustre de façon schématique le principe retenu dans les procédés selon l'art antérieur, pour simuler une propagation dans un domaine 1 prédéterminé. -15- Pour des raisons de clarté, on a représenté un unique capteur virtuel 2, surdimensionné sur la figure 1 par rapport à la taille du domaine 1. Le domaine 1 comprend deux sources 3. Les sources 3 peuvent consister en : - des sources lumineuses ; - des sources acoustiques ; - des sources de rayonnement ; - des sources radios ; - etc. Dans toute la suite, on gardera l'exemple de sources 3 acoustiques. Cela ne doit pas être considéré comme limitatif. Chaque source 3 émet une onde que l'on peut découper en portions d'onde 7. Une portion d'onde 7 peut être simulée par : - un simple rayon auquel on attribue une énergie acoustique 15 correspondant à la portion d'onde 7 ; - un faisceau (en deux dimensions si le domaine 1 est en deux dimensions, en trois dimensions si le domaine 1 est en trois dimensions) auquel on attribue une énergie acoustique correspondant à la portion d'onde 7; 20 - une poutre c'est-à-dire un faisceau auquel on attribue une énergie acoustique correspondant à la portion d'onde 7, et un rayon porteur servant à calculer une trajectoire approximée de la portion d'onde 7 dans le domaine 1. Le procédé selon l'art antérieur met en oeuvre au final : un calcul de la propagation, dans le domaine 1, des portions 25 d'onde 7 émise par les sources 3, et pour le capteur virtuel 2, une mesure d'une énergie acoustique des portions d'onde 7 reçues par celui-ci. On parallélise lesdites étapes de calcul et mesure en attribuant à une unité d'exécution donnée (formée par exemple par un ou plusieurs 30 « thread ») un groupe de portions d'onde 7 donné. A la figure 1, on a représenté trois groupes correspondant respectivement aux portions d'onde 7 représentées en trait continu, en trait mixte et en pointillés. Chaque unité d'exécution permet donc d'obtenir seulement une partie 35 de l'énergie acoustique reçue par le capteur virtuel 2. 2979026 -16- Pour obtenir l'ensemble de l'énergie acoustique reçue par le capteur virtuel 2, il faut mettre en oeuvre une étape supplémentaire de croisement des informations obtenues dans les différentes unités d'exécution. Cette étape supplémentaire ne peut pas être parallélisée. 5 On va maintenant décrire en référence à la figure 2, le principe retenu dans le procédé selon l'invention pour simuler une propagation dans un domaine 1 prédéterminé. Le procédé selon l'invention comprend une étape de décomposition du domaine 1 en plusieurs sous domaines 101, 102, 103 et 104. 10 Les traits mixtes 4 dessinent les frontières entre des sous domaines voisins. Chaque sous domaine 101r 102, 103 respectivement 104 comprend : - au moins un capteur virtuel 2 ; - éventuellement une source 3 ; - une géométrie, définie notamment par les obstacles 5. Chaque sous domaine 101r 102, 103 respectivement 104 est traité par une unité d'exécution différente. Chaque unité d'exécution met en oeuvre les étapes de : - calcul de la propagation dans le sous domaine qui lui a été attribué, d'au moins une portion d'onde 7, et - pour chaque capteur virtuel 2 contenu dans le sous domaine qui lui a été attribué, mesure de l'énergie acoustique totale reçue par celui-ci. On obtient directement au sein d'une unité d'exécution donnée l'énergie 25 acoustique totale reçue par un capteur virtuel 2, prenant en compte les contributions de toutes les portions d'onde dans le domaine 1. Aucune étape de croisement des résultats obtenus dans les différentes unités d'exécution n'est nécessaire pour connaître l'énergie acoustique totale reçue par un capteur virtuel 2. 30 Le taux de parallélisation du procédé selon l'invention est donc amélioré, en comparaison avec l'art antérieur. La figure 3 illustre un aspect particulier d'un mode de réalisation de procédé selon l'invention. 2979026 -17- La figure 3 illustre plus particulièrement le procédé mis en oeuvre lorsqu'une portion d'onde se propage d'un sous domaine à un sous domaine voisin. L'unité d'exécution associée au sous domaine 102 met en oeuvre les 5 étapes suivantes pour chaque portion d'onde qui s'y propage : - calcul de la propagation de la portion d'onde dans le sous domaine considéré 102; - si à l'issue de ce calcul de propagation, il s'avère que la portion d'onde 73 (portions d'onde représentées en trait mixte épais à la figure 3) 10 atteint une frontière avec un sous domaine voisin, communication à l'unité d'exécution associée à ce sous domaine voisin 103, 104, respectivement 101r de données relatives à la propagation de cette portion d'onde 73 en dehors du sous domaine considéré 102 et vers le sous domaine voisin. 15 L'unité d'exécution communique à l'unité d'exécution associée au sous domaine voisin 103, 104, respectivement 101: - un vecteur directeur ; - des coordonnées ; - une énergie acoustique ; 20 mesurés au point 8, à la sortie du sous domaine 102 considéré ou à l'entrée du sous domaine voisin. En outre, l'unité d'exécution peut : - recevoir des données fournies par une unité d'exécution associée à un sous domaine voisin, et relatives à une propagation d'une portion d'onde 72 (portions d'onde représentées en trait pointillé à la figure 3) vers le sous domaine considéré 102 et en dehors dudit sous domaine voisin ; - calculer la propagation de cette portion d'onde dans le sous domaine considéré 102. Ce qui vient d'être décrit pour l'unité d'exécution associée au sous domaine 102 est valable pour toutes les autres unités d'exécution mises en oeuvre. En pratique, on peut prévoir de charger dans une unité d'exécution donnée un modèle modifié dans lequel tous les sous domaines excepté le sous domaine à traiter sont remplacés par une version simplifiée, par exemple une 2979026 -18- boîte englobante (on utilise en pratique le terme anglais « bounding box »). Cela permet à une unité d'exécution d'identifier un sous domaine voisin dans lequel se propage une portion d'onde, tout en limitant la mémoire requise. Dans les exemples qui viennent d'être développés, on suppose que 5 chaque unité d'exécution ne traite qu'un seul sous domaine. Ces exemples sont nullement limitatifs, et on peut prévoir que chaque unité d'exécution traite un ou plusieurs sous domaines. On peut dans ce cas mettre en oeuvre des échanges de sous domaine d'une unité d'exécution à l'autre, de façon à homogénéifier des temps 10 traitement entre les unités d'exécution. On va maintenant décrire une mise en oeuvre particulière de l'invention. Il s'agit de simuler la pollution acoustique dans le quartier de Shinjuku, à Tokyo, au Japon. Il s'agit d'une zone de 2,5 km par 1,5 km centrée sur le point de coordonnées {35°41'23" N ; 139°41'25"E}. 15 On utilise comme domaine 1 une modélisation en trois dimensions de ce quartier. La figure 6 représente une vue en perspective de cette modélisation, avec également la distribution 60 de niveaux de bruit obtenue à l'issu de la simulation par le procédé selon l'invention. 20 On simule la propagation de nombreuses sources acoustiques (véhicules automobiles, explosion dans le centre...). On utilise au total 10 millions de faisceaux pour chaque source acoustique 3. On a utilisé pour la mise en oeuvre du procédé selon l'invention un super- 25 ordinateur de la marque « NOVA » commercialisé par la société « Bull S.A. ». Ce super-ordinateur est formé de 32 noeuds. Chaque noeud est formé de quatre processeurs de type « Xeon E7310 Tigerton ». Chaque processeur est formé de quatre coeurs. Au total, 13,7 millions de microphones (capteurs virtuels) sont placés 30 selon un maillage régulier dans le domaine 1 volumique, ce qui correspond à un microphone tous les 4 mètres dans chaque direction de l'espace à trois dimensions. Le domaine est donc une boîte de taille {w, h, d}, avec une origine au point de coordonnées {0, 0, 0}. On découpe le domaine 1 en N sous 2979026 -19- domaines de dimensions égales, et tels que le sous domaine i est un volume de taille { N , h, d}, avec une origine au point de coordonnées { N , 0, 0}. Les calculs de propagation utilisent la méthode de lancé hybride rayons et faisceaux. 5 La figure 4 illustre un graphique d'accélération en fonction d'un nombre de « threads » utilisé. Les « threads » sont regroupés par groupes de 16 en processus. Les résultats obtenus par les différents processus sont collectés en mettant en oeuvre une librairie MPI et une communication Ethernet ou InfiniBand. t 10 L'accélération S est calculée par la formule suivante : S = ref , où t - tref est un temps de référence correspondant au temps de traitement global en l'absence de toute parallélisation des calculs ; et - t est le temps de traitement global obtenu en mettant en oeuvre le procédé selon l'invention. 15 Le temps de traitement global prend en compte : - le chargement des données à traiter, notamment le chargement des sous domaines par les unités d'exécution ; - les calculs de propagation et mesures de l'énergie acoustique totale reçue par chaque capteur virtuel ; 20 - la collecte des résultats obtenus dans chaque unité d'exécution. Pour chaque sous domaine, on a mis en oeuvre des méthodes de partage de faisceaux telles que déjà connues dans l'art antérieur, afin d'améliorer encore les performances de calcul. En particulier, pour chaque sous domaine, on met en oeuvre un algorithme de partage dynamique des 25 faisceaux, et un algorithme de partage d'une matrice de résultats utilisant un mutex. Cette sélection d'algorithmes est choisie pour son efficacité. La figure 4 correspond à l'utilisation d'un système Ethernet pour la collecte des résultats obtenus par les différents processus. Les courbes 41, 42, 43 et 44 correspondent à des accélérations S en 30 fonction du nombre d'unités d'exécution utilisé. En particulier : 2979026 -20- - la courbe 41 correspond aux résultats obtenus avec le procédé selon l'invention et lorsque le domaine 1 est décomposé en 8 sous domaines - la courbe 42 correspond aux résultats obtenus avec le procédé selon 5 l'invention et lorsque le domaine 1 est décomposé en 2 sous domaines - la courbe 43 correspond aux résultats obtenus avec le procédé selon l'invention et lorsque le domaine 1 est décomposé en 4 sous domaines 10 - la courbe 44 correspond aux résultats obtenus avec un procédé selon l'art antérieur mettant en oeuvre les mêmes algorithmes mais pour le sous domaine pris dans son entier (algorithme de partage dynamique des faisceaux, algorithme de partage d'une matrice de résultats utilisant un mutex). 15 On voit que les résultats obtenus avec le procédé selon l'invention sont bien meilleurs que les résultats pouvant être obtenus avec les procédés de l'art antérieur. On voit également qu'il est avantageux d'utiliser un grand nombre de sous domaines, par exemple 8. 20 On a pu montrer qu'il n'était cependant pas avantageux d'avoir plus de sous domaines que de noeuds dans le système informatique mettant en oeuvre le procédé selon l'invention. La figure 5 ne diffère de la figure 4 que par le système utilisé pour la collecte des résultats obtenus par les différents processus. 25 La figure 5 correspond à l'utilisation d'un système InfiniBand pour la collecte des résultats obtenus par les différents processus. On obtient des temps de traitement global plus rapides qu'en utilisant un système Ethernet, puisque le système InfiniBand permet une communication plus rapide vers la matrice de résultats. 30 On voit que les deux courbes les plus affectées par la différence de vitesse de communication sont les courbes 44 (cas où on ne découpe pas le domaine 1 en sous domaines) et 42 (cas où on découpe le sous domaine 1 en seulement 2 sous domaines). Elles correspondent en effet aux cas dans lesquels chaque unité d'exécution doit envoyer beaucoup de données vers la 35 matrice de résultat unique. 2979026 -21- Le procédé selon l'invention, offrant un temps de traitement global fortement diminué en comparaison des procédés de l'art antérieur permet de traiter : - de grands volumes (dans lesquels le nombre de capteurs virtuels 5 devient rapidement important lorsque le volume augmente) ; - de nombreuses sources dans un même domaine ; - de nombreux capteurs virtuels afin d'augmenter la précision des calculs ; - fournir des résultats en temps réel. 10 On peut par exemple l'utiliser dans le domaine : - des jeux vidéo, par exemple pour simuler en temps réel et de façon réaliste le bruit entendu par un personnage évoluant dans un domaine 1; - de la conception de bâtiments ; 15 - des dessins animés ; - etc. Ces modes de réalisation étant nullement limitatifs, on pourra notamment imaginer des variantes de l'invention ne comprenant qu'une 20 sélection de caractéristiques décrites par la suite isolées des autres caractéristiques décrites, si cette sélection de caractéristiques est suffisante pour conférer un avantage technique ou pour différencier l'invention par rapport à de l'état de la technique antérieur. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être 25 décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention. En particulier, on peut prendre en compte dans le calcul de propagation de portion d'onde la diffraction et/ou les matériaux du domaine (matériaux des surfaces sur lesquelles il y a réflexion des portions d'onde, matériaux dans lesquels il y a propagation des portions 30 d'onde, etc). REVENDICATIONS1. Procédé mis en oeuvre dans au moins un système parmi : un ordinateur multi-noeuds ; un ordinateur multi-processeurs ; un ordinateur mufti-coeurs, pour simuler une propagation dans un domaine (1) prédéterminé, le domaine (1) prédéterminé étant défini par une géométrie (5), au moins une source (3) et comprenant plusieurs capteurs virtuels (2), le procédé mettant en oeuvre : - un calcul de la propagation, dans le domaine (1), d'au moins une portion d'onde (7) émise par la source (3), et - pour chaque capteur virtuel (2), une mesure d'une donnée caractéristique des portions d'onde (7) reçues par celui-ci, le procédé étant caractérisé par : une étape de décomposition du domaine (1) en plusieurs sous domaines (101, 102, 103, 104) comprenant chacun un sous ensemble d'au moins un capteur virtuel (2); et une étape d'allocation des sous domaines (101, 102, 103, 104) réalisant la répartition d'au moins deux d'entre eux entre plusieurs unités d'exécution distinctes. 2. Procédé selon la revendication 1, caractérisé en ce chaque unité d'exécution met ensuite en oeuvre les étapes de : calcul de la propagation, uniquement dans l'au moins un sous domaine correspondant (101 ; 102; 103; 104), d'au moins une portion d'onde (7), et pour chaque capteur virtuel (2) contenu dans l'au moins un sous domaine correspondant (101 ; 102; 103; 104), mesure d'une donnée caractéristique des portions d'onde (7) reçues par celui-ci. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que l'unité d'exécution associée à au moins un sous domaine considéré (101 ; 102; 103; 35 104) met en oeuvre les étapes suivantes : 30calcul de la propagation d'une portion d'onde (7) dans le sous domaine considéré (101 ; 102 ; 103 ; 104); si ledit calcul montre que la portion d'onde (73) atteint un sous domaine voisin, communication à une unité d'exécution associée audit sous domaine voisin, de données relatives à la propagation en dehors du sous domaine considéré (101 ; 102; 103; 104) et dans le sous domaine voisin. 4. Procédé selon la revendication 3, caractérisé en ce que lesdites données 10 comprennent : un vecteur directeur ; des coordonnées ; une donnée caractéristique ; relatifs à la portion d'onde (73) se propageant en dehors du sous domaine 15 considéré (101; 102; 103; 104) et dans le sous domaine voisin, et mesurés à la sortie du sous domaine considéré (101 ; 102; 103; 104). 5. Procédé selon la revendication 3 ou 4, caractérisé en ce que des étapes de calcul de la propagation d'une portion d'onde (7) dans le sous 20 domaine considéré (101 ; 102; 103; 104) et de communication de données relatives à une propagation dans le sous domaine voisin, sont mises en oeuvre simultanément, chacune pour une portion d'onde distincte. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en 25 ce que l'étape d'allocation des sous domaines (101, 102, 103, 104) comprend en outre le chargement d'une géométrie simplifiée des sous domaines voisins entourant le sous domaine considéré (101 ; 102 ; 103 ; 104). 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en 30 ce que l'unité d'exécution associée à au moins un sous domaine considéré (101; 102; 103; 104) met en oeuvre les étapes suivantes : réception de données fournies par une unité d'exécution associée à un sous domaine voisin, et relatives à une propagation d'une portion d'onde (72) dans le sous domaine considéré (101 ; 102 ; 103; 104) et en 35 dehors dudit sous domaine voisin ;calcul de la propagation de cette portion d'onde (72) dans le sous domaine considéré. 8. Procédé selon la revendication 7, caractérisé en ce que des étapes de réception de données fournies par une unité d'exécution associée à un sous domaine voisin et de calcul de la propagation de la portion d'onde (72) sont mises en oeuvre simultanément, chacune pour une portion d'onde (72) distincte. 9. Procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce qu'une unité d'exécution reçoit des sous domaines (101 ; 102; 103; 104) initialement alloué une autre unité d'exécution, de façon à homogénéifier des temps de traitement entre les unités d'exécution. 10. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que l'unité d'exécution associée à au moins un sous domaine considéré (101 ; 102 ; 103; 104), tour à tour pour chaque portion d'onde, met en oeuvre les étapes suivantes : calcul de la propagation de la portion d'onde (7) dans le sous domaine considéré ; si ledit calcul montre que la portion d'onde (73) atteint un sous domaine voisin, communication à une unité d'exécution associée audit sous domaine voisin, de données relatives à la propagation en dehors du sous domaine considéré (101 ; 102; 103; 104) et dans le sous domaine voisin. 11. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que l'unité d'exécution associée à au moins un sous domaine considéré (101 ; 102; 103; 104), tour à tour pour chaque portion d'onde, met en oeuvre les étapes suivantes : réception de données fournies par une unité d'exécution associée à un sous domaine voisin, et relatives à une propagation d'une portion d'onde (72) dans le sous domaine considéré (101 ; 102 ; 103; 104) et en dehors dudit sous domaine voisin ;calcul de la propagation de cette portion d'onde (72) dans le sous domaine considéré. 12. Procédé selon l'une quelconque des revendications 1 à 11, caractérisé en ce que le calcul de propagation d'une portion d'onde (7) met en oeuvre au moins une méthode parmi : une méthode de lancé de rayons ; une méthode de lancé de faisceaux ; une méthode de lancé hybride rayons et faisceaux. une méthode de lancé de particules. 13. Produit programme d'ordinateur, caractérisé en ce qu'il est agencé pour exécuter les étapes du procédé selon l'une quelconque des revendications 1 à 12 lorsqu'il est exécuté dans au moins un ordinateur. 14. Support pouvant être lu par au moins un ordinateur, caractérisé en ce qu'il comporte enregistré un produit programme d'ordinateur agencé pour exécuter les étapes du procédé selon l'une quelconque des revendications 1 à 12 lorsqu'il est exécuté dans au moins un ordinateur.15