Brevet FR3098945A1 — publié le 20210122

Description Titre de l'invention : Site pour GPU Domaine technique [0001] La présente invention concerne le domaine des bases de données et plus particu- lièrement de procédé de stockage et d'accès aux données sur une machine disposant d'un processeur graphique performant. Technique antérieure [0002] Nous nous intéressons dans ce document à l'architecture des SIG (Système d'Information Géographique) modernes composés d'importantes bases de données vectorielles. Nous verrons que les solutions décrites dépassent cc cadre et sont applicables à toute base de données indépendamment du type des données manipulées. [0003] Les SIG modernes sont composés d'une base de données contenant un grand nombre, typiquement en millions, d'objets élémentaires. Ces objets élémentaires sont typiquement : d'une part, des primitives vectorielles de base telles que points, vecteurs et polygones, de nature géométrique et décrivant la localisation de la primitive, et d'autre part, des attributs sémantiques de natures diverses, par exemple type de route ou autre. Les données peuvent donc être vues comme une collection de vecteurs à N dimensions où N représente le nombre d'attributs de chaque primitive. [0004] Lorsque l'on utilise le système, on navigue dans une vue géographique ou scène. Cette scène est typiquement une zone géographique éventuellement associée à des critères de sélection des éléments à afficher en fonction de critères propres à l'application courante. L'affichage nécessite donc une requête dans la base de données pour récupérer les primitives à afficher en fonction de la vue désirée, éventuellement une étape d'habillage de ces primitives consistant à fixer certains paramètres qui peuvent dépendre de l'application comme la couleur d'affichage, puis le traçage de ces primitives. Ces étapes font intervenir un module d'accès aux données qui s'exécute typiquement sur le processeur de l'ordinateur utilisé. Ce module accède aux données qui sont stockées sur un moyen de stockage accessible tel qu'un disque dur, un disque en mémoire flash ou SSD (Solid State Drive en anglais). Pour accélérer les traitements, il est connu de charger l'intégralité des données en mémoire vive ou RAM (Random Access Memory en anglais) du processeur principal ou CPU (Central Processing Unit en anglais) de l'ordinateur. Même ainsi, la quantité de données typiquement en Gigaoctets, la résolution des écrans, typiquement plusieurs milliers de points dans chaque dimension, conduisent à un traitement de plusieurs minutes sur les processeurs les plus puissants du moment. Ces données nécessaires à l'affichage d'une vue, une fois acquises, sont transférées à un processeur graphique ou GPU (Graphical Processing 2 Unit en anglais) sous la forme d'un flux de primitives pour être tracées à l'écran. Exposé de l'invention [0005] L'invention vise à résoudre les problèmes précédents par l'utilisation de procédés de stockage et d'accès aux données entièrement gérés dans l'unité de traitement graphique de l'ordinateur. Les données y sont stockées au sein d'un arbre kd adapté à l'architecture de l'unité de traitement dans la mémoire vive de l'unité de traitement graphique. Les algorithmes d'agencement des données et d'accès à ces données sont adaptés à une exécution parallèle par cette unité de traitement graphique. De cette façon, on utilise avantageusement la puissance de calcul de l'unité graphique pour accélérer la gestion de la base de données. [0006] La présente invention concerne un procédé de stockage d'une collection de points d'un espace multidimensionnel en mémoire d'un dispositif de traitement de l'information, caractérisé en ce qu'il comporte : [0007] - une étape préliminaire de création d'un vecteur de rang par dimension et d'un vecteur d'index, lesdits points de la collection étant stockés dans un tableau, ledit vecteur d'index contenant l'index dans le tableau de chaque point, chaque vecteur de rang contenant l'index du point correspondant dans un tableau où les points seraient triés selon la dimension correspondante ; [0008] - une étape de construction d'un arbre kd représentant ladite collection de points, les points étant répartis à chaque noeud en valeurs inférieures et supérieures à la médiane des valeurs selon une des dimensions, la répartition étant faite sur les vecteurs de rang et le vecteur d'index, les points affectés à chaque fil n'étant pas triés entre eux, le tableau stockant la collection de points n'étant pas modifié. [0009] Selon un mode de réalisation, l'étape de construction de l'arbre kd comporte : [0010] - une étape de répartition des valeurs d'un vecteur de rang en valeurs inférieures et en valeurs supérieures à la médiane ; [0011] - une étape de répercussion de ladite répartition sur les autres vecteurs de rang et sur le vecteur d'index ; [0012] - une étape de renumérotation des valeurs réparties au sein de chaque serai-vecteur au sein d'un autre vecteur de rang correspondant à la dimension selon laquelle doit être effectuée l'étape suivante de répartition. [0013] Selon un mode de réalisation, l'étape de répartition comporte : [0014] - une étape (4.1) de calcul d'un second vecteur de drapeaux binaires de la même longueur que le vecteur à répartir dont chaque valeur est le résultat de la comparaison de la valeur correspondante du tableau avec la valeur de l'index de la médiane ; [0015] - une étape (4.2) de calcul d'un second vecteur de drapeaux binaires de la même longueur que le vecteur à répartir dont chaque valeur est l'inverse de la valeur con-es- 3 pondante du premier vecteur de drapeaux ; [0016] - une étape (4.3) de calcul des sommes préfixes de ces deux vecteurs de drapeaux ; [0017] - une étape (4.4) d'ajout de la valeur de l'index de la médiane à toutes les valeurs de la somme préfixe du second vecteur de drapeaux ; [0018] - une étape (4.5) de réordonnancement des index inférieurs à la médiane à l'index correspondant à la valeur de la première somme préfixe ; [0019] - une étape (4.6) de réordonnancement des index supérieurs à la médiane à l'index correspondant à la valeur de la seconde somme préfixe. [0020] Selon un mode de réalisation, l'étape de renumérotation comporte, le vecteur à re- numéroter (6.2) étant de longueur N/2 et contenant des valeurs comprises entre 0 et N1 : [0021] - une étape de construction d'un vecteur de drapeaux (6.3) de longueur N contenant pour chaque indice une valeur booléenne 1 si l'indice est présent dans le tableau et 0 sinon ; [0022] - une étape de construction de la somme préfixe (6.4) dudit vecteur de drapeaux ; [0023] - une étape où chaque valeur du tableau initial (6.2) est remplacée par la valeur du tableau des sommes préfixes (6.4) dont l'indice correspond à ladite valeur du tableau initial. [0024] Selon un mode de réalisation, ledit dispositif de traitement de l'information comportant une pluralité de processeurs scalaires disposant d'une mémoire locale, l'étape de construction de l'arbre kd est interrompue dès que la collection de points associée à une feuille de l'arbre a une taille mémoire inférieure à la taille de cette mémoire locale. [0025] Selon un mode de réalisation, chaque noeud de l'arbre mémorise deux points re- présentant un hypercube englobant la collection de points associée à ce noeud. [0026] La présente invention concerne également un procédé de recherche, au sein d'une collection de points d'un espace multidimensionnel, des points appartenant à un hypercube dudit espace, la collection de points étant mémorisée sous la forme d'un arbre kd, caractérisé en ce qu'il comporte : [0027] - une étape (7.1) d'initialisation d'un vecteur de longueur égale au nombre de feuilles dans l'arbre kd à zéro, la première valeur étant mise à un, ce vecteur représentant pour une profondeur donnée de l'arbre aux indices des noeuds devant être recherchés ; [0028] - une étape (7.2) de test pour chaque noeud dont l'indice est à 1 pour la profondeur courante en commençant par la racine, on met à 1 les indices des fils du noeud testé, l'intersection de l'hypercube englobant les points associés à ce noeud possédant une intersection non nulle avec l'hypercube recherché ; [0029] - une étape (7.3) où l'on teste s'il reste des noeuds à rechercher ; si oui, on reboucle à l'étape de test pour la profondeur suivante ; 100301 - une étape (7.4) où l'on teste les points associés aux feuilles sélectionnées pour obtenir le résultat. [0031] La présente invention concerne, de plus, un système de gestion de base de données comportant une unité de traitement graphique et des moyens de stockage d'une collection de points d'un espace multidimensionnel en mémoire d'un dispositif de traitement de l'information, caractérisé en cc qu'il comporte : [0032] - des moyens pour créer un vecteur de rang par dimension et un vecteur d'index, lesdits points de la collection étant stockés dans un tableau, ledit vecteur d'index contenant l'index dans le tableau de chaque point, chaque vecteur de rang contenant l'index du point correspondant dans un tableau où les points seraient triés selon la dimension correspondante ; [0033] - des moyens pour construire un arbre kd représentant ladite collection de points, les points étant répartis à chaque noeud en valeurs inférieures et supérieures à la médiane des valeurs selon une des dimensions, la répartition étant faite sur les vecteurs de rang et le vecteur d'index, les points affectés à chaque fil n'étant pas triés entre eux, le tableau stockant la collection de points n'étant pas modifié. [0034] La présente invention concerne aussi un système de gestion de base de données comportant une unité de traitement graphique et des moyens de recherche, au sein d'une collection de points d'un espace multidimensionnel, des points appartenant à un hypercubc dudit espace, la collection de points étant mémorisée sous la forme d'un arbre kd, caractérisé en ce qu'il comporte : [0035] - des moyens pour initialiser un vecteur de longueur égale au nombre de feuilles dans l'arbre kd à zéro, la première valeur étant mise à un, ce vecteur représentant pour une profondeur donnée de l'arbre aux indices des noeuds devant être recherchés ; [0036] - des moyens pour tester pour chaque noeud dont l'indice est à 1 pour la profondeur courante en commençant par la racine, on met à 1 les indices des fils du noeud testé, l'intersection de l'hypercube englobant les points associés à ce noeud possédant une intersection non nulle avec l'hypercube recherché ; [0037] - des moyens pour tester s'il reste des noeuds à rechercher et si oui pour reboucler l'étape de test pour la profondeur suivante ; [0038] - des moyens pour tester les points associés aux feuilles sélectionnées pour obtenir le résultat. Brève description des dessins [0039] Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, appa- raîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels : [0040] [fig.l] illustre un exemple d'architecture d'une unité de traitement graphique ; [0041] [fig.2] illustre un arbre kd ; [0042] [fig.3] illustre les structures de données utilisées dans un exemple de réalisation de l' invention ; [0043] [fig.4] illustre l'algorithme parallèle de répartition d'un vecteur de rang selon un exemple de réalisation de l'invention ; [0044] [fig.5] illustre un exemple de répartition d'un vecteur de rang ; [0045] [fig.6] illustre un exemple de renumérotation des semi-vecteurs ; et [0046] [fig.7] illustre l'algorithme de sélection au sein de la structure selon un exemple de réalisation de l'invention. [0047] EXPOSE DETAILLE DE MODES DE REALISATION [0048] Les unités de traitement graphiques actuelles sont des multiprocesseurs massivement parallèles. Ces unités de traitement cumulent plusieurs modèles de parallélisme. Un exemple d'une telle architecture est illustré Fig. 1. L'unité de traitement graphique 1.1 contient une mémoire globale 1.2 accessible à l'ensemble des processeurs. Elle est constituée d'une pluralité de multiprocesseurs 1.3, 1.4, 1.5 et 1.6 chacun de ces multi processeurs contenant lui-même une pluralité de processeurs scalaires 1.7, 1.8 et 1.9. Ces processeurs scalaires fonctionnent selon un mode SPMD (Single Program Multiple Data en anglais), c'est-à-dire qu'ils exécutent le même programme sous le contrôle d'une unité de gestion des instructions 1.10 sur des données propres à chaque processeur. Il existe plusieurs espaces de mémoires au sein de l'unité de traitement graphique. On a déjà cité la mémoire globale 1.2. L'accès à cette mémoire globale est exclusif et il est donc nécessaire de le limiter Il existe également deux caches permettant d'accélérer l'accès à certaines données. Un premier cache 1.12 est dédié au stockage de constantes. Un second cache 1.13 est dédié au stockage des textures. Ces caches sont prévus pour optimiser une utilisation en rendu d'une scène 3D pour des applications telles que les jeux. Ils peuvent être utilisés à d'autres fins dans les autres applications. Chaque multiprocesseur dispose également d'une mémoire locale 1.11 partagée entre les processeurs scalaires du multiprocesseur. L'accès à cette mémoire locale est beaucoup plus rapide que l'accès à la mémoire globale et surtout indépendant de l'activité des autres multiprocesseurs. Chaque processeur scalaire dispose également d'un espace de registres propres non représentés. [0049] Le modèle de programmation de ces unités tire parti de leur nature massivement parallèle. Ce modèle est un modèle SIMT (Single Instruction Multiple Thread en anglais). Dans ce modèle, il s'agit d'exécuter en parallèle un même programme sur les différents multiprocesseurs, chaque multiprocesseur pouvant exécuter en parallèle des groupes de processus légers (connus sous le nom de Warps of Threads en anglais), chaque groupe (warp) étant exécuté sur un processeur scalaire. Dans l'exemple de réalisation, on utilise une carte graphique du constructeur NVidia qui peut exécuter ainsi 6 128 groupes de 1024 processus légers (thrcad). [0050] Des langages de programmation dédiés à la programmation de telles architectures existent. On peut citcr CUDA (Comput° Unified Device Architecture en anglais) du constructeur NVidia ou encore OpenCL (Open Computing Language en anglais) proposé à l'origine par Apple et actuellement maintenu par le groupe Khronos. C'est ce dernier qui est utilisé dans l'exemple de réalisation. [0051] L'invention repose sur l'idée de gérer la hase de données entièrement sur une telle unité de traitement graphique. Une telle hase de données est typiquement gérée sous la forme d'un arbre de données. Cet agencement des données permet des requêtes rapides en particulier sur les attributs géométriques. Lorsque l'on cherche à implémenter un tel agencement sur une architecture d'unité de traitement graphique, on doit résoudre plusieurs problèmes. Il faut trouver une méthode rapide de construction de l'arbre dans la mémoire globale de l'unité. Il faut aussi adapter l'agencement pour que les requêtes puissent se faire de manière rapide. Les algorithmes classiques de gestion des arbres sont fortement récursifs. Une des particularités des unités de traitement graphique est qu'elles ne disposent pas de pile et sont donc impropres à l'exécution de programmes récursifs. De plus, quand bien même elles seraient dotées d'une telle pile, ces algorithmes récursifs ne présentent pas de parallélisme directement exploitable. [0052] On a choisi un agencement des données sous la forme d'un arbre kd (kd-troc en anglais). On rappelle qu'il s'agit de stocker une collection de points constitués par des vecteurs de dimension N dans la mémoire globale de l'unité de traitement graphique. Dans un arbre kd (un exemple est illustré Fig. 2), chaque noeud possède exactement deux fils sauf les feuilles. Les données vont être stockées dans un tel arbre selon le procédé que l'on va décrire maintenant. Une première étape avantageuse permet d'obtenir l'équilibrage de l'arbre. Cette première étape initiale consiste à calculer le nombre de niveaux de l'arbre et la dimension des feuilles en fonction de la taille de la mémoire locale disponible. On en déduit la taille totale de l'arbre, ce qui permet de réaliser le compactage des données et leur allocation statique. En effet, les unités de traitement graphique ne permettent généralement pas l'allocation dynamique de mémoire. L'arbre final est fortement équilibré, car le remplissage des feuilles et la répartition des niveaux sont maximaux, ce qui permet d'augmenter le degré de parallélisme et donc la performance finale. En effet, il est important pour une bonne exploitation du parallélisme que les données soient réparties de manière homogène dans l'arbre. A chaque noeud correspond une collection de points que l'on doit répartir entre le fil gauche et le fil droit. A la racine correspond l'intégralité de la collection. La répartition se fait ensuite selon une dimension de l'espace des attributs, et ceci séquentiellement pour chaque dimension jusqu'à obtenir le remplissage souhaité pour les feuilles. Cette dimension dépend de la profondeur. Par exemple, la répartition à la 7 racine 2.1 peut se faire selon la première dimension, typiquement la dimension géographique des X. La répartition des noeuds de profondeur 1, c'est-à-dire les noeuds 2.2 et 2.3, peut se faire selon la dimension géographique des Y. La répartition des noeuds de profondeur 2, c'est-à-dire les noeuds 2.4 à 2.7, peut se faire selon la dimension géographique des Z. La répartition des noeuds de profondeur 3, c'est-à-dire les noeuds 2.8 à 2.15, peut se faire selon la première dimension sémantique, par exemple le type de route, et ainsi de suite. La répartition se fait selon la valeur médiane de la collection à répartir dans la dimension sélectionnée. Les points de la collection à répartir dont la valeur dans la dimension donnée est inférieure à la valeur médiane sont affectés au fil gauche. Ceux dont la valeur est supérieure à la médiane sont affectés au fil droit. Avantageusement, on mémorise au niveau du père deux points définissant la fenêtre englobante des points de la collection à répartir. Par fenêtre englobante s'entend un ensemble de homes, typiquement deux, pour chaque dimension des données stockées de façon à constituer un hypercuhe englobant les données. Dans le cas d'attributs géographiques ou géométriques, ces homes correspondent à des limites spatiales. Le point minimum contient dans chaque dimension la valeur minimum de l'attribut pour l'ensemble des points. Le point maximum contient dans chaque dimension la valeur maximum de l'attribut pour l'ensemble des points. Cela permet d'accélérer les recherches. [0053] Pour exploiter au mieux le parallélisme, il est avantageux de pouvoir saturer la mémoire locale des processeurs pour effectuer les traitements. Il est donc contre-productif de pousser la division de l'arbre jusqu'aux feuilles ultimes ne contenant qu'un point de la collection de données. Au contraire, il est avantageux de stopper la division de l'arbre lorsqu'un noeud se trouve gérer une collection de points dont la taille en mémoire équivaut à la taille de la mémoire locale des processeurs. De cette façon, cette collection peut être intégralement chargée en mémoire locale pour les différents traitements parallèles devant être faits. [0054] Alternativement, on définit la taille de la collection ultime comme étant le nombre de processus légers gérés par un processeur. Cette alternative conduit à effectuer des traitements où chaque processus léger gère un point de la collection à la fois. [0055] L'exemple de réalisation de l'invention propose un algorithme de création de l'arbre kd qui ne nécessite pas un tri de toutes les données lors de chaque étape et qui de plus est parallélisable. Le procédé proposé consiste à effectuer une étape préliminaire de tri par dimension avant tout calcul. Pour ce faire, on mémorise dans un vecteur de rang de la même longueur que la collection de points, pour chaque point, le rang qu'aurait ce point dans le vecteur trié. Un tel vecteur de rang est créé pour chaque dimension de la collection de points. La collection de points elle-même n'est pas réordonnancée lors de cette étape préliminaire ni lors de toutes les étapes de la construction et de la mise à 8 jour de l'arbre, ce qui permet avantageusement d'éviter le coût de manipulation des données propres. Ceci est illustré par la Fig. 3. Cette figure illustre une collection 3.1 de points rangés dans un tableau, chaque point ayant 4 attributs rangés dans le sens horizontal 3.2, la collection comprenant ici 8 points rangés dans le sens vertical 3.3. Pour chaque dimension, on crée un vecteur 3.4, 3.5, 3.6 et 3.7 dans lequel sont rangés les index qu'auraient les points correspondants si la collection était triée selon la dimension correspondante. Typiquement, le vecteur 3.4 contient le rang des points de la collection si elle était triée selon la première dimension, le vecteur 3.5 contient le rang des points de la collection si elle était triée selon la seconde dimension, le vecteur 3.6 contient le rang des points de la collection si elle était triée selon la troisième dimension et le vecteur 3.7 contient le rang des points de la collection si elle était triée selon la quatrième dimension. Un vecteur supplémentaire d'index 3.8 est également constitué. Ce vecteur d'index est initialisé avec les index croissants de 1 à N des points de la collection. En effet, lors des réordonnancements des vecteurs de rang relatifs à la construction de l'arbre kd, on réordonnance avantageusement ce vecteur d'index pour éviter de réordonnancer le tableau 3.1 qui contient la collection de points. [0056] L'algorithme de tri utilisé pour cette étape préliminaire doit avantageusement être choisi pour son efficacité sur une architecture massivement parallèle telle que celle des unités de traitement graphique. On peut utiliser une méthode apparentée au tri rapide (quicksort en anglais), qui permet de calculer le kième plus petit élément d'un vecteur. Cette méthode est due à Mr Hoare et de complexité o(n.log(n)). Une autre méthode plus efficace appelée médiane des médianes peut également être utilisée, elle est d'une complexité en o(n). Un tri bitonique parallèle peut avantageusement être aussi réalisé. [0057] On doit ensuite réaliser une étape de construction de l'arbre kd représentant la collection de points. Cette construction nécessite de parcourir l'arbre à partir de la racine pour répartir la collection sur les deux fils de chaque noeud. Nous avons vu que la répartition se fait en fonction d'une des dimensions, c'est-à-dire d'un des attributs des points à répartir. La dimension choisie dépend de la profondeur dans l'arbre du noeud à traiter. Traditionnellement, cette répartition implique un tri des points à répartir en fonction de la dimension courante lors de l'opération de chaque noeud et donc un tri de l'ensemble des points pour chaque profondeur de l'arbre. Avantageusement, la solution proposée ici consiste à utiliser les vecteurs de rang créés lors de l'étape préliminaire pour répartir les points en fonction de leur position par rapport à la médiane dans la dimension choisie. Les points dont la valeur de l'attribut dans la dimension courante est inférieure à la valeur de la médiane sont affectés au fil gauche tandis que les points dont la valeur de l'attribut dans la dimension courante est supérieure à la valeur de la médiane sont affectés au fil droit. Les points affectés à chaque fil ne sont pas triés selon la dimension courante entre eux, le tableau stockant la collection de 9 points n'étant pas modifiée. [0058] La répartition se fait en trois étapes pour chaque noeud. Lors d'une première étape, on répartit les index du vecteur de rang de la dimension considérée en fonction de la médiane. Dans une seconde étape on répercute cette répartition sur l'ensemble des vecteurs de rang ainsi que sur le vecteur d'index. Lors d'une troisième étape, on renumérote les index des points dans la dimension suivante pour chaque demi-vecteur pour préparer la découpe selon la médiane de ces demi-vecteurs lors de l'étape suivante. [0059] L'algorithme parallèle permettant la répartition d'un vecteur de rang en fonction de la médiane est illustré par la Fig. 4. Un exemple sur un vecteur de rang de longueur 16 est illustré Fig. 5. Au départ, on part d'un vecteur de rang où est rangé pour chaque point l'index qu'il aurait si le tableau était trié selon la dimension considérée. Si le vecteur a une longueur N, on en déduit que le rang de la médiane est N/2. Lc but de l'opération est donc de déplacer les valeurs du tableau inférieures à la médiane N/2 dans la première partie du vecteur et les valeurs du tableau supérieures à la médiane N/ 2 dans la seconde partie du tableau. Dans une solution itérative, on testerait chaque valeur par rapport à la médiane et on la rangerait dans la partie qui convient. Pour exploiter le parallélisme, on définit la notion de vecteur de drapeaux. Un vecteur de drapeaux est un vecteur binaire. Chaque élément a une valeur binaire zéro ou un, qui stocke le résultat d'un test sur la valeur correspondante du vecteur à répartir. Le vecteur de départ est référencé 5.1. On calcule un premier vecteur de drapeaux 5.2 lors de l'étape 4.1. Ce vecteur représente le résultat de la comparaison de chaque rang avec le rang de la médiane, 8 dans l'exemple. Le vecteur de drapeaux 5.2 contient un 1 si le rang correspondant est inférieur à la médiane et un 0 sinon. Lors de l'étape 4.2 on créé également le vecteur 5.4 qui contient les valeurs inverses. Lors d'une étape 4.3 on crée les vecteurs des sommes préfixes de ces deux vecteurs de drapeaux. Le vecteur 5.3 est la somme préfixe du vecteur 5.2, le vecteur 5.5 est la somme préfixe du vecteur 5.4. Lors de l'étape 4.4 on ajoute la médiane, ici 8, au second vecteur préfixe 5.5 pour obtenir le vecteur 5.6. Lors d'une étape 4.5 on réordonne les index inférieurs à la médiane. Pour ce faire, on déplace tous les index dont la valeur dans le premier vecteur de drapeaux 5.2 est à un dans le vecteur final au rang dans ce vecteur final donné par le premier vecteur préfixe 5.4. Lors d'une étape 4.6 on réordonne les index supérieurs à la médiane. Pour ce faire on déplace tous les index dont la valeur dans le second vecteur de drapeaux 5.4 est à un dans le vecteur final au rang dans ce vecteur final donné par le second vecteur préfixe 5.6. On obtient un vecteur 5.7 où tous les index inférieurs à la médiane sont dans la première moitié du vecteur et les index supérieurs à la médiane sont dans la partie supérieure du vecteur. On a bien obtenu la découpe selon la médiane du vecteur de rang 5.1 du départ. [0060] Lorsque l'on a effectué cette découpe, il est nécessaire de répercuter le réordon- nancement sur les autres vecteurs de rang 3.4 à 3.7 ainsi que sur le vecteur d'index 3.8 pour maintenir la cohérence des données. On applique alors les étapes de réordonnancement 4.5 et 4.6 à ces vecteurs en gardant les mêmes vecteurs de drapeaux et les mêmes vecteurs préfixes que pour le vecteur de rang découpé. [0061] Lorsque l'on a terminé les découpes pour une profondeur donnée de l'arbre kd et donc pour une dimension donnée, il faut commencer les découpes suivant la dimension suivante pour la profondeur suivante des données. Pour cc faire, il est nécessaire de reproduire les opérations de découpe précédemment décrites mais sur des vecteurs ayant une longueur inférieure de moitié à la longueur des vecteurs précédents. Ceci est illustré à la Fig. 6. [0062] Le vecteur 6.1 représente sur sa première ligne un vecteur de rang selon une première dimension X. Ce vecteur reprend les valeurs de la Fig. 5. Sur la deuxième ligne est représenté le vecteur de rang selon une seconde dimension Y. Cc second vecteur de rang contient lui aussi des index compris entre 0 et N-1. Lorsqu'intervient la découpe du premier vecteur selon X et la répercussion sur le second vecteur selon Y tel que décrit ci-dessus, on aboutit au vecteur 6.2 dont la première ligne correspond au résultat pour le vecteur selon X, c'est-à-dire au vecteur 5.7. La seconde ligne correspond au vecteur selon Y ayant subi le même réordonnancement. On va donc devoir refaire une découpe et une répartition du vecteur selon Y pour chacun des demi-vecteurs de longueur N/2, le demi-vecteur contenant les valeurs 11 à 0 et le demi-vecteur contenant les valeurs 14 à 10. On constate que l'algorithme décrit ci-dessus assume que les valeurs à répartir sont comprises entre la valeur 0 et la longueur du vecteur -1. Ce n'est pas le cas ici, car nous avons des vecteurs de longueur N/2 à répartir qui contiennent des valeurs entre 0 et N-1. [0063] Il faut donc renuméroter les index sans en changer l'ordre pour obtenir des vecteurs de taille N/2 contenant des valeurs consécutives entre 0 et N/2-1. Les opérations à suivre doivent être effectuées pour chaque vecteur de longueur N/2. On commence par une étape de calcul d'un vecteur de drapeaux de longueur N. C'est le vecteur 6.3 qui pour chaque index i du vecteur de drapeaux contient un 1 si l'index est présent dans le vecteur de longueur N/2. Par exemple, la première valeur du tableau de chapeaux 6.3 est à 1, car l'index 0 est présent dans le premier demi-vecteur selon Y du vecteur 6.2. La troisième valeur est 0, car l'index 2 n'est pas présent dans le premier demi-vecteur selon Y du vecteur 6.2. On calcule alors la somme préfixe 6.4 de ce vecteur de drapeaux. On obtient alors le tableau renuméroté 6.5 en prenant pour chaque index la valeur du tableau des sommes préfixes 6.4 ayant pour index la valeur contenue dans le tableau initial. Par exemple pour l'index 0, la valeur du tableau de départ d'index 0 est 11 ; on affecte donc au résultat d'index O la valeur 6 correspondant à l'index 11 dans le 11 tableau préfixe 6.4. De même, pour l'index 1, la valeur du tableau de départ d'index 1 est 9 ; on affecte donc au résultat d'index 1 la valeur 5 correspondant à l'index 9 dans le tableau préfixe 6.4. Il faut faire de même pour la seconde moitié du vecteur 6.5. Il faut calculer un nouveau vecteur de drapeaux et en faire la somme préfixe pour obtenir le résultat illustré par le vecteur 6.5. On constate que le vecteur résultat 6.5 reprend les index du vecteur 6.2 selon Y dans le même ordre, niais avec des valeurs consécutives entre 0 et 7. Une fois les demi-vecteurs renumérotés, on peut passer à l'étape suivante de découpe de chacun des demi-vecteurs et ainsi de suite. [0064] Une construction classique d'arbre kd impliquerait de continuer la découpe jusqu'au niveau des feuilles, c'est-à-dire que les feuilles ne contiendraient qu'un seul élément de la collection de points. Pour exploiter au mieux le parallélisme de l'unité de traitement graphique, il est au contraire plus avantageux d'arrêter la découpe plus tôt. Dans l'exemple de réalisation, la découpe est arrêtée dès que le noeud est associé à une collection de points dont la taille en mémoire est inférieure à la taille de la mémoire locale des processeurs scalaires. Les feuilles de l'arbre contiennent donc une collection de points qui peut tenir intégralement dans cette mémoire locale pour le calcul. Alternativement, on peut aussi choisir une taille égale au nombre de processus légers qui peuvent être exécutés simultanément par le processeur scalaire. Ce nombre tient également typiquement dans la mémoire locale et est typiquement inférieur au nombre de points obtenu par la première alternative. De cette façon, les traitements peuvent être implémentés de telle sorte qu'un processus léger s'occupe des calculs concernant un seul point de la collection. [0065] Les opérations de recherche dans la collection consistent à sélectionner les points dont les attributs répondent à un critère. Typiquement, la recherche s'apparente à déterminer les points présents dans un hypercube de dimension N, N étant le nombre d'attributs. Cet hypercube est défini par deux points de dimension N. Cette recherche se fait par un parcours de l'arbre à partir de la racine. Ce parcours s'effectue profondeur par profondeur jusqu'aux feuilles. A chaque profondeur, on élimine les noeuds qui n'ont pas d'intersection dans la dimension associée à la profondeur avec l'hypercube recherché. Nous avons vu qu'avantageusement on mémorise au niveau du père deux points définissant la fenêtre englobante des points de la collection à répartir. Ces points sont utilisés ici pour déterminer si cette collection a une intersection avec l'hypercube. On continue la recherche en testant dans la profondeur suivante les fils des noeuds n'ayant pas été éliminés Cette recherche s'effectue jusqu'aux feuilles. On obtient alors la liste des feuilles ayant une intersection avec l'hypercube recherché. Il suffit alors de tester les points de ces feuilles pour obtenir ce résultat. Cette recherche est d'autant plus efficace que les points de la feuille sont transférables dans la mémoire locale des processeurs scalaires. 12 [0066] Cette recherche peut se faire selon le procédé suivant : [0067] Dans une première étape 7.1, on initialise un vecteur de longueur égale au nombre de feuilles dans l'arbre kd à 0, on met seulement la valeur d'index 0 à 1. Ce vecteur re- présente les noeuds à rechercher lors de l'opération courante et donc pour une profondeur donnée. Cette initialisation consiste à initier la recherche avec la racine. [0068] Dans une seconde étape 7.2, on teste les noeuds à 1 pour la profondeur courante en commençant par la racine. S'ils ont une intersection avec l'hypercubc, on met à 1 les index des fils du noeud sauf si c'est une feuille. Si le père est d'index n dans le tableau initial, les fils ont les index 2.n et 2.n+1 dans le tableau résultant. [0069] Dans une troisième étape 7.3, on calcule dans un vecteur auxiliaire la somme préfixe du vecteur pour obtenir dans son dernier élément le nombre de noeuds restant à rechercher. Si cc nombre est nul, on s'arrête, sinon on reboucle à la seconde étape pour la profondeur suivante. [0070] Dans une quatrième étape 7.4, on teste les points des feuilles sélectionnées pour obtenir le résultat. [0071] Dans une utilisation de ces procédés pour l'implémentation d'un système d'information géographique, les résultats de la recherche sont typiquement des primitives graphiques devant être affichées à l'écran. On utilise alors typiquement l'unité de traitement graphique pour l'affichage des résultats sous la forme d'une fenêtre contenant la représentation graphique d'une zone géographique. [0072] Toutefois, les unités de traitement graphiques permettent aujourd'hui de transférer des informations de la mémoire globale du GPU vers la mémoire du processeur central de l'ordinateur. Il est donc tout à fait envisageable d'utiliser les procédés décrits dans tout type de bases de données et d'exploiter les résultats de la recherche sur le processeur central. Les procédés ne sont donc pas limités à un usage dans les systèmes d'information géographique, mais sont utilisables pour l'implémentation de bases de données généralistes. [0073] Tous ces algorithmes sont parallélisables avec efficacité sur une unité de traitement graphique et permettent d'obtenir un niveau de performance plus élevé que sur un processeur classique. L'exemple de réalisation montre un gain d'un facteur 10 à 20 par rapport à une implémentation classique sur un processeur central. 13 [Revendication 1] [Revendication 2] REVENDICATIONSProcédé de recherche, au sein d'une collection de points d'un espace multidimensionnel, des points appartenant à un hypercube dudit espace, la collection de points étant mémorisée sous la forme d'un arbre kd, caractérisé en ce qu'il comporte : - une étape (7.1) d' initial isation d'un vecteur de longueur égale au nombre de feuilles dans l'arbre kd à zéro, la première valeur étant mise à un, cc vecteur représentant pour une profondeur donnée de l'arbre aux indices des noeuds devant être recherchés ; - une étape (7.2) de test pour chaque noeud dont l'indice est à 1 pour la profondeur courante en commençant par la racine, on met à 1 les indices des fils du noeud testé, l'intersection de l'hypercube englobant les points associés à ce noeud possédant une intersection non nulle avec l'hypercube recherché ; - une étape (7.3) où l'on teste s'il reste des noeuds à rechercher, si oui on reboucle à l'étape de test pour la profondeur suivante ; - une étape (7.4) où l'on teste les points associés aux feuilles sélectionnées pour obtenir le résultat. Système de gestion de base de données comportant une unité de traitement graphique et des moyens de recherche, au sein d'une collection de points d'un espace multidimensionnel, des points appartenant à un hypercube dudit espace, la collection de points étant mémorisée sous la forme d'un arbre kd, caractérisé en ce qu'il comporte - des moyens pour initialiser un vecteur de longueur égale au nombre de feuilles dans l'arbre kd à zéro, la première valeur étant mise à un, ce vecteur représentant pour une profondeur donnée de l'arbre aux indices des noeuds devant être recherchés ; - des moyens pour tester pour chaque noeud dont l'indice est à 1 pour la profondeur courante en commençant par la racine, on met à 1 les indices des fils du noeud testé, l'intersection de l'hypercube englobant les points associés à ce noeud possédant une intersection non nulle avec l'hypercube recherché ; - des moyens pour tester s'il reste des noeuds à rechercher et si oui pour reboucler à l'étape de test pour la profondeur suivante ; - des moyens pour tester les points associés aux feuilles sélectionnées pour obtenir le résultat.