Brevet FR2840705A1 — publié le 20031212

op est l'operateur algorithmique. - 1 À ' La presente invention concerne un procede d'equilibrage de charge au sein d'un ensemble (cluster) d'ordinateurs utilises en parallele pour des applications graphiques. Wile vise egalement un dispositif pour la mise en ceuvre de ce procede. - - II existe deja des techniques d'equilibrage de charge au sein d'un cluster d'ordinateurs paralleles utilises pour traiter des portions diune image en temps reel. A chaque ordinateur est associee une portion ou region d'une meme image. Chaque image comporte un ou plusieurs objets, chaque objet pouvant etre decompose en soul-objets. Une technique existante d'equilibrage est basee sur le deplacement de frontiere entre les differentes regions. Mais on observe un effet de redondance de calculs effectues par plusieurs ordinateurs affectes a des regions adjacentes d'une meme image du fait qu'un meme soul-objet est ainsi calcule plusieurs fois, ce qui occasionne un temps de calcul eleve qui peut s'averer dans certaines configurations prohibitif pour une utilisation graphique en temps reel. Le but de la presente invention est de resoudre cet inconvenient en proposant un procede d'equilibrage de charge qui permette de reduire la probabilite qu'un meme objet ou soul-objet soit traite par plusieurs machines. Cet objectif est atteint avec un procede pour equilibrer la charge d'un ensemble (cluster) d'ordinateurs utilises en parallele et affectes chacun au calcul diune zone ou region d'une image numerique, comprenant pour chaque image, un decoupage prealable de ['image en plusieurs regions a chacune desquelles un ordinateur est affecte, et un maillage du ou des objets presents dans ['image selon une pluralite de formes geometriques 3 o elementaires. - 2 Suivant ['invention, le procede d'equilibrage de charge comprend en outre, pour chaque image: - une decomposition audit objet en une pluralite de soul-objets obtenus chacun par regroupement de formes geometriques elementaires, - un calcul de l'empreinte de cheque soul- objet comprenant une determination du nombre d'intersections audit soul- objet avec les frontieres de regions, et - un ajustement des regroupements de formes geometriques elementaires de fa,con a minimiser le nombre d'intersections. Ainsi, avec le procede d'equilibrage de charge selon ['invention, on reduit significativement la probabilite de redondance puisque les soulobjets vent construits de fa,con a n'etre inclus que dans une seule region et ne vent done traites que par la machine affectee a cette region determinee. Les formes geometriques elementaires peuvent comprendre des polyedres. D'autres avantages et caracteristiques de ['invention apparaftront a l'examen de la description detaillee d'un mode de mise en aeuvre nullement limitatif, et des dessins annexes sur lesquels: - la figure 1 represente schematiquement une image traitee avec le procede d'equilibrage de charge selon ['invention; et - la figure 2 illustre schematiquement un cluster d'ordinateurs pour lequel le procede d'equilibrage de charge est mis en aeuvre. On va maintenant decrire, en reference aux figures precitees, un exemple de mise en cauvre du procede d'equilibrage selon ['invention, en meme temps que le dispositif permettant cette mise en oeuvre. On considere un cluster C d'ordinateurs M1,,Mi, Mn pilote par une unite de pilotage U a laquelle vent connectes des peripheriques et equipements informatiques au nombre desquels un ecran E. L'unite de pilotage U est adaptee pour exploiter un traitement graphique d'images numeriques en affectant a chacune des regions d'une meme image un 3 0 ordinateur du cluster C. L'unite U inclut notamment un dispositif D d'equilibrage de la charge de calcul assuree par chacun des ordinateurs du cluster. Ce dispositif D est concu pour mettre en couvre le procede d'equilibrage de charge selon ['invention. Pour chaque image numerique 1, un decoupage prealable est effectue de facon 3 fournir un ensemble de regions R1,..,Ri,..Rn, par exemple sous la forme de rectangles de taille reguliere. Chaque objet O present dans ['image I est decompose en un ensemble d'objets elementaires ou soulobjets SO1,...SO\,...,SON obtenus par agregation ou regroupement de formes geometriques elementaires Fi, par exemple des triangles elementaires. Le dispositif d'equilibrage de charge D calcule alors ltempreinte de chaque soul-objet sur liecran, definie ici comme un rectangle englobant la projection du soul-objet sur l'ecran, et determine le nombre diintersections de ce soul-objet avec les frontieres des regions de ['image. Les regroupements des formes geometriques elementaires vent ajustees de facon a minimiser le nombre d'intersections pour chacun des soul-objets. On obtient alors un ensemble optimise de soul-objets completement inclus dans une region unique et done traites chacun par un seul ordinateur. Bien sGr, I'invention n'est pas limitee aux exemples qui viennent d'etre decrits et de nombreux amenagements peuvent etre apportes a ces exemples sans sortir du cadre de ['invention. - 4 - REVENDICATIONS 1. Procede pour equilibrer la charge d'un ensemble (cluster) (C) d'ordinateurs (M 1,..,Mi,..Mn) utilises en parallele et affectes chacun au calcul d'une zone ou region (R1,..,Ri,..Rn) diune image numerique (I), comprenant pour chaque image: - un decoupage prealable de ['image (I) en plusieurs regions (R1,..,Ri,..,Rn) a chacune desquelles un ordinateur est affecte, - un maillage du ou des objets (O) presents dans ['image (I) selon une pluralite de formes geometriques elementaires (F), caracterise en ce qu'il comprend en outre, pour chaque image: - une decomposition audit objet (O) en une pluralite de soul-objets (SOi, SOj, SO k) obtenus chacun par reg roupement de formes geometriques elementaires (F), - un calcul de ltempreinte de chaque soul-objet comprenant une determination du nombre d'intersections audit soul-objet avec les frontieres de regions, et - un ajustement des regroupements de formes geometriques elementaires de facon a minimiser le nombre d'intersections. 2. Procede selon la revendication 1, caracterise en ce que les formes geometriques elementaires comprennent des polyedres. 3. Procede selon l'une des revendications 1 ou 2, caracterise en ce que les regions vent de forme rectangulaire. 4. Dispositif (D) pour equilibrer la charge d'un ensemble (C) (cluster) d'ordinateurs (M 1,..,Mi,..,Mn) utilises en parallele et affectes chacun au calcul d'une zone ou region (Ri) d'une image numerique (I), comprenant: - 5 - - des moyens pour realiser pour chaque image un decoupage prealable de ladite image en plusieurs regions 3 chacune desquelles un ordinateur est affecte, - des moyens pour realiser un maillage du ou des objets presents dans ['image selon une pluralite de formes geometriques elementaires, caracterise en ce qu'il comprend en outre: - des moyens pour realiser une decomposition audit objet en une pluralite de soul-objets obtenus chacun par regroupement de formes geometriques elementaires, - des moyens pour calculer l'empreinte de chaque soul-objet comprenant une determination du nombre d'intersections audit soul-objet avec les frontieres de regions, et - des moyens pour ajuster les regroupements de formes geometriques elementaires de facon a minimiser le nombre d'intersections. 5. Application du procede d'equilibrage de charge selon l'une des revendications 1 a 3, pour un cluster d'ordinateurs adapte au traitement