Aperçu

Il y a quelques mois j'ai commencé à travailler sur un prototype de base de données relationnelle en Metal. Apple venait de sortir les M1 Max et M1 Ultra quelques mois auparavant avec jusqu'à 128 Go de mémoire unifiée (dans le Mac Studio).

J'ai vu cela comme une opportunité de faire quelque chose avec un traitement très lourd qui nécessitait beaucoup de mémoire GPU : traiter de grandes tables relationnelles sur un GPU.

Je n'étais pas le premier à penser à écrire une base de données relationnelle sur un GPU. Des bases de données comme BlazingSQL , une base de données relationnelle GPU construite sur Rapids.AI . Rapids.AI est une bibliothèque Python de NVIDIA qui reflète les fonctionnalités de nombreuses bibliothèques Python populaires, telles que Pandas, mais exécute les fonctions équivalentes sur le GPU. NVIDIA a investi massivement dans le centre de données et a aidé à développer davantage d'outils fonctionnant sur leurs cartes, en particulier pour l'apprentissage automatique et le traitement de données volumineuses.

En regardant les conférences Apple ces derniers temps, j'ai senti qu'il y avait beaucoup de performances potentielles qui n'étaient pas vraiment utilisées. D'après ce que j'ai vu, les développeurs profitent des nouvelles capacités graphiques des nouvelles puces. Du côté informatique, les démos et les logiciels open source construits avec Metal ont fait défaut. Apple a fait un exemple de projet d'une simulation de particules, je présume pour montrer l'équivalent de l'échantillon CUDA. Ils montrent comment vous pouvez utiliser le calcul dans CUDA et le rendu dans OpenGL sur le GPU sans avoir à revenir au CPU entre les deux. L'autre endroit où Apple utilise beaucoup le GPU est pour les tâches d'IA. Chaque fois que le Neural Engine ne prend pas en charge une opération dans un modèle, CoreML se rabattra automatiquement sur le GPU pour plus de performances. Bien que cela soit très utile et fascinant,

J'ai choisi une base de données relationnelle car j'adore vraiment les bases de données et j'ai pensé à un certain nombre de conceptions pour celles-ci, dont certaines pour lesquelles j'ai construit des prototypes au fil des ans. Les bases de données relationnelles sont également intéressantes car elles utilisent des chaînes et des valeurs nulles. L'exemple d'IA et le simulateur de particules, bien que très impressionnants, n'utilisent que des flottants et des entiers.

L'implémentation que j'ai construite peut être trouvée ici : MetalDB Github

Idées de conception

Je ne me souviens pas si c'était juste au début ou quelque part au milieu du processus, mais j'ai été inspiré par la documentation de BigQuery Query Plans qui parlait d'un graphique des étapes de requête qui composent un plan d'exécution de requête.

L'une des principales limitations de conception avec Metal est que toute la mémoire doit être dimensionnée statiquement au moment de la compilation. Cela présentait des défis car je ne pouvais pas copier une chaîne car je ne savais pas combien de chaînes il y avait dans une ligne de base de données, ou combien de temps chaque chaîne serait au moment de la compilation.

J'ai pensé qu'il serait plus simple d'utiliser un algorithme de somme de préfixes pour copier toutes les données du GPU vers le CPU de manière efficace si chaque thread traitait une ligne. J'avais également besoin d'utiliser le plus grand bloc synchronisable disponible, qui dans Metal est un ThreadGroup.

En partie par optimisation et en partie par défi personnel, je voulais maximiser la quantité de travail effectué sur le GPU. Pour ces raisons, j'ai choisi de commencer par lire les fichiers CSV sur le CPU et d'effectuer l'analyse CSV sur le GPU.

Lors de l'implémentation, je voulais également pouvoir tester la base de données sur le processeur afin que les tests unitaires puissent être effectués dans un débogueur. Pour cette raison, j'ai configuré le pipeline de construction pour que tous mes noyaux Metal soient écrits en tant qu'en-têtes. Par conséquent, je pourrais les inclure dans les fichiers du noyau Metal, mais aussi les inclure dans les tests en C++. Cette conception me permettrait également de définir des constantes et des types dans les en-têtes Metal et de garantir qu'ils étaient toujours les mêmes dans le code C++ qui l'appellerait.

Contexte des groupes de threads et des concepts de métal

Comme arrière-plan pour d'autres idées et explications, l'exécution du métal est organisée en grilles. Une grille est un groupe 1D, 2D ou 3D de ThreadGroups. Un ThreadGroup est un groupe synchronisable au sein de cette grille. Les threads au sein d'un ThreadGroup sont divisés et exécutés dans d'autres groupes, appelés warps.

Un thread est le bloc le plus basique de la programmation GPU et se traduit approximativement par le modèle d'un thread sur un cœur de processeur. Il s'agit d'une exécution d'instructions unique, linéaire et dans l'ordre. Le thread a des registres auxquels il peut accéder directement ainsi que lire et écrire dans la mémoire partagée. Il s'agit d'un modèle de mémoire différent de celui du processeur, mais cela dépasse le cadre de cet article.

Un warp (appelé SIMD dans la documentation Metal) est souvent un groupe de 16 ou 32 threads. La même instruction doit être exécutée en même temps sur tous les threads d'un warp, bien que potentiellement sur des données différentes (SIMD, Single Instruction, Multiple Data). Si certains threads empruntent un chemin différent dans le code, tous les threads de ce warp doivent attendre que toutes les branches s'exécutent en série. Cela conduit à concevoir du code GPU avec le moins de branches possible, de sorte que tous les threads d'une chaîne soient occupés autant que possible.

D'autres systèmes comme CUDA et OpenCL ont des concepts similaires, mais avec des noms différents.

Mise en œuvre

Lien vers la mise en œuvre :https://github.com/mattpaletta/metaldb

À mon avis, je pense qu'il est plus logique de parler de la mise en œuvre dans l'ordre du flux de données à travers le système. Cependant, c'est presque l'inverse parfait de la façon dont j'ai procédé pour l'implémenter.

Binaire

Le résultat final qui est produit est très simple. C'est un binaire appelé metaldbet il contient juste une fonction principale. J'ai rendu l'application très légère afin que moi-même, ainsi que d'autres, puissions réutiliser facilement les bibliothèques internes dans le cadre d'autres bibliothèques et applications à l'avenir.

Moteur

Le moteur est l'endroit où la majeure partie de la logique du système est coordonnée. Le moteur interagit avec le QueryPlanner, qui est implémenté dans la bibliothèque QueryPlanner, ainsi que le Scheduler, qui est responsable de l'exécution et de la coordination de l'exécution du plan de requête généré.

Analyseur de requête

L'analyseur de requêtes est le composant chargé de transformer une requête de type SQL en un AST qui peut être plus facilement analysé par le reste du système.

Cette première version de la base de données n'implémente pas d'analyseur de requêtes. Au lieu de cela, j'ai codé en dur l'AST pour diverses requêtes que je souhaite tester. Écrire un analyseur et produire un AST, bien que cela semble très intéressant, est quelque chose que j'ai fait dans un autre projet et qui n'était pas l'objectif de ce projet.

Je n'avais pas non plus l'intention de faire de ce projet une base de données prête pour la production. Par conséquent, il n'a pas besoin d'un analyseur de requêtes pour le moment, mais tous les stubs sont là pour que je puisse les implémenter ultérieurement si je le souhaite.

En plus du système acceptant les chaînes de requête, je prévois d'implémenter éventuellement une API Dataframe, similaire à Pandas, mais en C++. De mon point de vue, ce type d'API serait plus simple à utiliser pour d'autres bibliothèques. Cela évite également à l'autre bibliothèque d'avoir à produire une chaîne de requête uniquement pour qu'elle soit ensuite immédiatement analysée par l'analyseur. Cette API Dataframe est également laissée en tant que travail futur.

En tant qu'ensemble de données de test, j'ai d'abord utilisé l'ensemble de données Iris accessible au public . J'ai choisi cet ensemble de données car il est relativement petit, au format CSV, et principalement des nombres, sans valeurs nulles.

Après avoir fait fonctionner cet ensemble de données, je voulais essayer un ensemble de données beaucoup plus volumineux avec plusieurs fichiers. Pour cela, j'ai utilisé le New York Taxi Dataset . Cet ensemble de données plus volumineux s'est avéré des défis intéressants auxquels je ne m'attendais pas, plus à ce sujet plus tard.

Planificateur de requêtes

Une fois que l'analyseur de requêtes a généré l'AST, le composant suivant est le planificateur de requêtes. Celui-ci est chargé de transformer l'AST en un plan d'exécution optimisé.

La première étape de l'élaboration d'un plan d'exécution optimisé consiste à élaborer un plan. Inspiré par la référence BigQuery , j'aimais l'idée de décomposer un plan d'exécution en un graphe d'"Etapes". Dans BigQuery, chaque étape est composée d'une ou de plusieurs étapes. Chaque étape peut être une lecture ou une écriture, un agrégat ou une jointure, etc. Je n'ai pas vraiment voulu descendre dans la granularité des étapes, mais j'ai un concept similaire, que j'appelle un « partiel ».

Pour passer d'un AST à un graphe d'étapes, je liste d'abord les fichiers sur disque pour la ou les table(s). Ensuite, je vais aux feuilles de l'AST et pour chacune d'elles, je produis une nouvelle étape qui lira ce fichier.

En remontant l'arbre, je décide si je vais créer un nouveau partiel dans le cadre de l'étape existante ou créer une nouvelle étape. Le point clé est que lorsque je dois passer du GPU au CPU ou inversement pour une étape, je crée une nouvelle étape. Cela signifie qu'autant de données peuvent être traitées sur le GPU tout en minimisant les temps de transfert entre le CPU et le GPU. Ceci est particulièrement pertinent pour les appareils qui n'ont pas de mémoire unifiée.

Chaque étape a une liste unique de partiels à exécuter. Celles-ci seront ensuite traduites sous forme d'instructions pour le GPU au cours de cette étape, car nous en explorerons plus dans la section sur le planificateur.

Chaque fois que je crée une nouvelle étape, j'insère une "Instruction Shuffle", qui indique au GPU de recopier les informations vers le CPU.

À l'avenir, j'écrirais également un optimiseur qui pourrait réécrire les requêtes pour minimiser la quantité de données lues à partir de chaque fichier et copiées sur le processeur après avoir été lues.

Planificateur

Le planificateur est responsable de l'exécution parallèle de la requête. J'ai été tenté d'écrire ma propre bibliothèque multithread pour ce faire. J'ai fini par écrire mon implémentation au-dessus de TaskFlow , une bibliothèque de graphes de tâches C++ open source.

A haut niveau, la création du graphe des tâches suit le graphe des étapes. Chaque étape est une tâche dans le graphe et dépend de ses enfants.

Au sein d'une étape, chaque partiel, la liste des étapes à effectuer sur le CPU ou le GPU, sont développées dans l'ordre. Au fur et à mesure que chaque partiel est enregistré, il a plusieurs tâches dans le graphe de tâches auquel il peut s'accrocher.

La tâche principale qui peut être accrochée est la tâche d'encodage de la tâche précédente. Le partiel doit créer une nouvelle tâche qui dépend de la tâche d'encodage du partiel parent. Il utilise l'encodeur transmis pour s'encoder dans une représentation sérialisée qui peut être envoyée au GPU. Pour la plupart des tâches, c'est tout ce qui est nécessaire et l'implémentation du partiel se fait sur le GPU en Métal.

L'autre tâche disponible est la tâche de travail. Cela existe dans le cas où un partiel veut remplacer quelque chose sur la façon dont le travail est exécuté pour ce partiel au lieu du comportement par défaut.

La plupart des tâches lisent les tampons d'une ou plusieurs étapes enfants et écrivent dans leur tampon de sortie. L'instruction de lecture est unique car elle doit lire à partir du disque, et non à partir des tampons enfants.

L'instruction de lecture met en place une chaîne de tâches qui lisent le fichier CSV (le seul type de fichier actuellement implémenté) qui lui a été attribué et le lit dans un tampon. Pendant qu'il lit dans un tampon, il garde une trace du décalage de la ligne actuelle et les stocke dans le cadre de l' RawTableobjet, décrit ci-dessous.

Une fois le fichier lu, le GPU est libre de commencer à traiter les lignes. La conception de la base de données nécessite un thread par ligne. Il se trouve que Metal a une limite quant au nombre de threads pouvant être attribués par ThreadGroup. Par conséquent, nous avons d'abord divisé les lignes en plusieurs tampons qui seront chacun envoyés au GPU indépendamment.

TaskFlow permet des sous-tâches dynamiques au sein d'une tâche. Lorsque j'obtiens le RawTable, j'interroge le nombre de threads que Metal me permet de programmer et de diviser les lignes d'origine en morceaux de cette taille.

Chaque morceau est ensuite envoyé au GPU en parallèle.

Une fois que tous les morceaux ont été traités, j'exécute une tâche de fusion qui copie tous les OutputRowobjets du GPU et les fusionne en un seul géant OutputRowafin que l'étape suivante puisse les lire ensemble.

À l'avenir, j'aimerais optimiser le fractionnement de plusieurs lots. Dès que le lot a été divisé, il peut être envoyé au GPU. Dès que ce bloc revient, il peut être copié dans le tampon final pendant que les autres tâches sont traitées de manière asynchrone.

De plus, je voudrais libérer l'original RawTableune fois que toutes les lignes ont été divisées en morceaux, chacun stockant une copie. De plus, je devrais pouvoir libérer le tampon de sortie du morceau dès qu'il a été copié dans le tampon final, réduisant ainsi la quantité totale de mémoire requise.

Instruction ParseRow

Le ParseRowInstructioncommence par une prémisse simple. Étant donné une liste d'index pour le début de chaque ligne et des informations sur le nombre de lignes et les types de colonnes, analysez les valeurs d'une ligne particulière, converties en leurs types corrects.

Le type de colonne le plus simple est une chaîne. Pour la ligne N , nous pouvons sauter au début de cette ligne en recherchant son index, que le CPU a stocké lorsque nous avons lu le fichier à partir du disque. Nous pouvons alors obtenir un pointeur vers cet index. C'est le début de la rangée. La fin de toute colonne est la position avant la virgule suivante (marquant la colonne suivante) lorsque nous avançons d'un caractère à la fois, ou un avant le début de la ligne suivante (si c'est la dernière colonne de la ligne), ou un avant la fin du tampon (si c'est la dernière colonne de la dernière ligne).

L'instruction lit d'abord chaque colonne comme une chaîne. Il analyse une colonne exactement comme décrit et la lit comme une chaîne, caractère par caractère. Maintenant, pour lire la colonne suivante, nous commençons au début de la ligne. Lorsque nous arrivons à la première virgule, nous la marquons comme le début et allons jusqu'à la virgule après cela. Le processus se répète pour les colonnes suivantes.

Si nous avons un entier, nous passons les pointeurs au début et à la fin de la chaîne à une stoifonction personnalisée. Ceci est similaire à celui de la bibliothèque standard C, qui convertit la chaîne en une représentation entière. J'ai également écrit ma propre version de stof.

Comme vous pouvez l'imaginer, la lecture de chaque colonne depuis le début de la ligne à chaque fois est très lente et il y a beaucoup de travail en double. On peut faire mieux, beaucoup mieux.

La première réalisation dans l'optimisation de la recherche du début de la colonne est qu'il y a souvent un faible nombre de colonnes. J'ai choisi 16 comme nombre arbitraire de colonnes à mettre en cache.

Avec ce premier niveau de cache, si je lis une colonne dans les 16 premières colonnes, j'essaie de lire le pointeur précédemment mis en cache pour cette colonne. Si ce n'est pas nul, j'ai déjà la valeur. Les lignes sont immuables, le pointeur doit donc être valide et le processus est terminé !

Si le pointeur est nul, je peux parcourir mon cache en arrière à partir de l'index de la 16e colonne jusqu'à ce que je trouve une colonne précédemment mise en cache ou que j'arrive à la première entrée.

Où que je m'arrête, je peux parcourir la ligne de manière naïve, un caractère à la fois. Chaque fois que je trouve une virgule, je stocke le pointeur vers le début de cette colonne dans mon cache afin que les requêtes suivantes puissent y accéder directement.

Cela signifie que l'accès aléatoire aux 16 premières colonnes devrait être fondamentalement gratuit car il devient une recherche directe de pointeur. Cela exclut le premier accès, qui est O(n) .

Qu'en est-il des lignes de plus de 16 colonnes ? Je sais déjà où se trouve la 15ème colonne (à partir de 0), donc je peux sauter directement à la 15ème colonne et ensuite interagir de manière naïve après cela. Si je ne sais pas où se trouve la 15e colonne, je peux rapidement la calculer et la mettre en cache.

C'est plutôt bien, sauf qu'il y a une autre optimisation qui peut être faite. L'autre réalisation est que dans la ParseRowInstruction pendant qu'elle construit la ligne de sortie, elle accède aux colonnes dans l'ordre. En plus du cache aléatoire de taille fixe pour les 16 premières colonnes, nous pouvons conserver un pointeur supplémentaire qui stocke le début de la dernière colonne consultée et l'index de cette colonne. Cela permet une recherche directe de pointeur pour des accès séquentiels pour n'importe quel nombre de colonnes, sans avoir à stocker un nombre infini de pointeurs, comme dans le premier niveau de mise en cache. Bien sûr, ces deux couches de mise en cache fonctionnent ensemble. Lorsque nous mettons à jour les 16 premières valeurs, nous mettons également à jour le last_accessedpointeur.

Lors de l'exécution sur le GPU, chaque thread est responsable d'une seule ligne. Ainsi, chaque thread a son propre cache multicouche, comme décrit. Le cache garde également une trace de la ligne que nous mettons en cache. S'il est différent de celui demandé, nous réinitialisons le cache, nous savons donc que le cache est toujours pertinent. Il est possible d'étendre cela pour couvrir les cas d'utilisation de la lecture de plusieurs lignes ou du partage du cache entre les threads, mais cela sortait du cadre de l'implémentation initiale.

Instructions de projection

C'est ProjectionInstructiontrès simple par comparaison. On lui donne une liste d'index de colonne à récupérer. Il crée un nouvel objet TempRow et copie ces colonnes du dernier TempRow, mettant à jour les métadonnées dans le nouvel objet TempRow.

Instruction de filtrage

L'implémentation de base de FilterInstructionest conçue autour de l'évaluation d'une ligne par rapport à une expression qui renvoie soit trueou false.

Cela a été implémenté en tant que machine virtuelle basée sur la pile. L'allocation de la pile est fixée au moment de la compilation et alloue donc toujours sa taille maximale.

La pile était quelque peu intéressante à mettre en œuvre. J'ai choisi de concevoir le bytecode de la machine virtuelle pour inclure les types ainsi que des instructions pour convertir un type en un autre. L'implémentation de la pile permet des données hétérogènes, mais l'appelant est responsable de fournir les types.

Dans une pile normale, vous pouvez créer des boîtes pour un objet, et la boîte stockera le type de la chose ainsi qu'un pointeur vers la chose. Dans ce cas, le compilateur (pas encore implémenté) est chargé d'écrire le bytecode pour inclure tout le casting nécessaire. Cela permet au runtime de pousser un entier sur la pile, qui est des xoctets, et plus tard, lorsqu'il va lire un entier, il peut xextraire des octets de la pile et obtenir le même entier. Aucune boîte ou coulée dynamique requise. Cela impose au compilateur la responsabilité d'obtenir tous les types corrects, mais cela reste pour une implémentation future.

Instruction de sortie

Le OutputInstructionest utilisé pour combiner toutes les données des threads individuels au sein du ThreadGroup et supprimer toutes les données en double dont chaque thread individuel a besoin, mais qui n'ont vraiment besoin d'être copiées qu'une seule fois sur le CPU, et de les mettre efficacement dans un grand tampon .

La première étape est que chaque ligne (chaque thread) calcule sa propre taille. Ensuite, nous exécutons une somme préfixe des tailles. Cela nous donne un index où nous savons que nous pouvons commencer à écrire nos données.

La somme des préfixes est un algorithme souvent utilisé dans le calcul GPU où, étant donné un tableau d'entiers, renvoie un nouveau tableau où, pour chaque index i, contient la somme de tous les éléments inférieurs à i . Si la somme inclut l'élément i pour la position i , on l'appelle une somme inclusive, sinon on l'appelle une somme exclusive. J'ai utilisé une somme exclusive pour ma mise en œuvre.

Avant de pouvoir commencer à écrire des données, les threads doivent coordonner l'écriture de l'en-tête du fichier OutputRow. Pour ce faire, la première ligne, chargée d'écrire l'en-tête, ajoute également la taille de l'en-tête à sa propre taille. Après avoir fait la somme des préfixes, nous exécutons également une réduction sur les tailles de ligne afin que le premier thread puisse écrire le nombre total d'octets dans l'en-tête.

Une fois cette opération terminée, chaque ligne peut passer à son décalage à partir de la sortie de la somme des préfixes et copier ses octets dans le tampon à partir de ce point en parallèle, et nous sommes assurés qu'il n'y aura pas de collisions.

TempRow

C'est TempRowla structure de données qui est transmise pendant que les données sont traitées dans Metal. Idéalement, nous allouerions un redimensionnable TempRowsur le tas, pour minimiser l'empreinte mémoire, mais parce que Metal ne prend pas en charge les allocations de mémoire dynamiques. Every TempRowest un tampon de taille fixe. J'ai choisi qu'il soit de 1024 octets, soit 1 kilo-octet. La première section du TempRowest un en-tête, suivi des données.

La première valeur de l'en-tête est sa longueur. Ceci est important car les données commencent immédiatement après l'en-tête et l'en-tête a une taille variable en fonction du nombre de colonnes et de leurs types.

L'octet suivant est le nombre de colonnes. Comme il ne s'agit que de 1 octet, le nombre maximum de colonnes est donc de 256. Je pense que c'est suffisant pour la plupart des cas d'utilisation.

Les N octets suivants sont les types de colonne. Les colonnes peuvent être l'une des suivantes : Integer, Float, Stringou leurs équivalents nullables. Une valeur booléenne est simplement exprimée sous la forme d'un entier.

Un entier et un flottant ont toujours une taille constante, nous n'avons donc pas à stocker leur taille dans l'en-tête, sauf s'il s'agit d'une colonne nullable. En revanche, une chaîne peut avoir n'importe quel nombre de caractères. Par conséquent, nous stockons la taille de toutes les colonnes de longueur variable (chaînes et colonnes facultatives) dans les octets suivants. Encore une fois, étant donné que la taille d'une colonne n'est que de 1 octet, la longueur maximale d'une chaîne est de 256 caractères.

Après l'en-tête, toutes les données des colonnes sont ajoutées les unes après les autres.

Afin de TempRowsimplifier la construction de, il existe une classe d'assistance TempRowBuilderdans laquelle l'appelant peut écrire tous les types et tailles de colonnes, etc. dans des tableaux séparés. Le TempRowpeut ensuite être trivialement construit à partir du constructeur en copiant les valeurs.

Les données des colonnes peuvent ensuite être ajoutées dans l'ordre. Il existe des méthodes d'assistance pour aider à copier des chaînes, des entiers et des flottants, et à les écrire octet par octet.

Lorsque la méthode suivante va ensuite lire le TempRow, il existe des méthodes d'assistance qui lisent à partir de l'en-tête pour déterminer les index de début et de fin dans le tampon pour cette colonne, et retransmettent les octets dans le type approprié. L'appelant est chargé d'interroger la ColumnTypecolonne qui l'intéresse avant de la lire comme ce type.

Étant donné que le TempRowlit toutes les données directement à partir d'un tampon de taille fixe, il pourrait être adapté de manière triviale à une constexprclasse pour d'autres applications.

OutputRow

Le OutputRowest créé par le OutputRowInstruction(décrit ci-dessus) et sert à déplacer plusieurs lignes qui partagent le même schéma. Il serait inutile de copier tous les TempRowobjets individuels directement car chaque ligne a le même schéma, il y a donc beaucoup de métadonnées en double. Au lieu de cela, nous copions toutes les données dans une structure singulière de sorte que nous puissions les copier dans des TempRowobjets séparés si nécessaire ultérieurement, ou les diviser en deux OutputRowobjets ou plus si nécessaire.

Semblable au TempRow, le OutputRowa une définition d'en-tête, bien qu'il soit légèrement différent du TempRow. La première valeur, comme expliqué précédemment, est la taille de l'en-tête, mais cette valeur est plus grande, avec 2 octets alloués au lieu de 1. La valeur suivante est le nombre d'octets dans le OutputRow, et il s'agit d'un entier non signé de 32 bits. Après c'est le nombre de colonnes, et ce n'est qu'un seul octet. Suivi par les types de colonnes, similaires au TempRow.

Après l'en-tête, toutes les données sont ajoutées. Étant donné que le OutputRowest toujours construit à partir d'un ou plusieurs TempRowou d'un autre OutputRow, nous pouvons calculer la taille des données de chaque ligne en parallèle à l'aide de l'algorithme de somme des préfixes et écrire dans le tampon de données en parallèle.

Lors de l'exécution dans Metal, le OutputRowest statiquement alloué pour avoir une taille fixe de 1 000 000 octets. Sur le CPU, nous pouvons être plus efficaces et utiliser a std::vectorpour allouer uniquement la quantité d'espace dont nous avons besoin.

Afin de faciliter la lecture et l'écriture de chaque thread OutputRowen parallèle, au lieu que les tailles des colonnes de taille variable soient écrites dans l'en-tête comme elles le sont dans le TempRow, elles sont plutôt ajoutées aux données de cette colonne par ligne. Ainsi par exemple, une ligne avec 2 entiers suivis d'une chaîne de 3 caractères « abc », aurait le format : <integer><integer>3abc. Le lecteur du OutputRow(actuellement uniquement implémenté sur le CPU) sait que la colonne est une chaîne, et peut donc sauter au début de la chaîne pour lire son contenu. Les tailles de chaque ligne ne sont pas écrites dans leOutputRow. Au lieu de cela, le lecteur parcourt le tampon et enregistre le début de chaque ligne et les tailles de chaque colonne de taille variable pour chaque ligne. Cela a été fait pour économiser de l'espace, mais pourrait être optimisé pour être écrit dans l'en-tête ou par ligne, de sorte que la lecture OutputRowsoit plus efficace et donc plus rapide. Les détails de la lecture, du fractionnement et de la fusion OutputRowd'objets sur le CPU ont été brièvement abordés précédemment dans la section sur le Scheduler.

Travail futur

J'ai travaillé sur ce projet comme une expérience pour voir si c'était possible. Il y a beaucoup de choses que j'aurais aimé mettre en œuvre, si je devais le rendre prêt pour la production, ou même simplement passer plus de temps sur le prototype que je n'en ai.

Ce bug

Le premier problème que j'aimerais résoudre est (ce que je pense être un bogue dans Xcode 13), où plusieurs threads se voient attribuer le thread 0 dans un ThreadGroup. Faites-moi savoir si vous avez des idées. Cela amène plusieurs threads à essayer d'écrire l'en-tête. Il en résulte que l'en-tête est partiellement écrasé avec des données, en fonction de l'ordre des threads. J'ai essayé de google à ce sujet, mais je n'ai trouvé aucune source particulièrement utile. Je pense que cela avait à voir avec la quantité de mémoire que j'essayais d'allouer à chaque thread. Malheureusement, la documentation officielle d'Apple ne dit rien à ce sujet que j'ai pu trouver.

Moteur de requête + analyseur

La prochaine grande tâche consiste à implémenter un analyseur et un moteur de requête afin que la base de données puisse accepter des requêtes de type SQL, les transformer en plans de requête et les exécuter. Cette tâche implique également la mise en œuvre d'une API DataFrame, ou l'écriture dans plusieurs formats sur le disque, à utiliser par d'autres bibliothèques et programmes.

Rejoindre + Grouper par

En développant la spécification SQL, il serait amusant de pouvoir calculer une jointure et une clause Group By. Je pensais que la manière naïve d'implémenter une jointure était de calculer chaque ligne brute sur le GPU en parallèle, puis de faire une jointure par hachage sur le CPU, une fois par bloc. Cependant, il peut être plus efficace de trouver un moyen de soumettre à la place un bloc de 2 tables différentes que vous souhaitez joindre en même temps, et de faire en sorte que le GPU renvoie les lignes jointes.

Pour le Group By, vous pouvez soit le faire sur le CPU, soit faire une agrégation partielle sur le GPU. Ou vous pouvez faire une combinaison dans laquelle vous effectuez le traitement brut initial sur le GPU, puis vous avez un noyau différent que vous exécutez lorsqu'un ensemble de lignes est donné, calcule le groupe pour chaque ligne dans l'ensemble. Cela vous permettrait de compartimenter rapidement des lignes sur le CPU où vous pourriez allouer plus de données pour contenir les lignes, tout en profitant de la nature parallèle du GPU pour calculer des groupes en parallèle.

Système distribué

Si ce système doit être utilisé en production, il doit probablement pouvoir tirer parti de plusieurs machines. Je pourrais imaginer un réseau hétérogène d'appareils connectés Apple (et non Apple) travaillant ensemble. Imaginez un iPhone en tant que contrôleur hôte envoyant des commandes aux autres machines, et un groupe d'iPads qui traitent chacun les données dont ils disposent localement et renvoient les lignes traitées au contrôleur central. Alternativement, vous avez peut-être un déploiement cloud exécutant le même code sur le CPU dans une instance AWS lambda, ou sur plusieurs GPU avec un serveur Mac Pro sur site. Tous ces systèmes pourraient fonctionner ensemble pour vous donner un accès réactif très rapide à de très grands ensembles de données avec des appareils qui (je pense) ont encore beaucoup de puissance de traitement inexploitée.

Réduire l'empreinte mémoire

Comme autre optimisation, d'autant plus que je veux que cela fonctionne sur n'importe quel appareil qui exécute Metal, il serait bien de garder l'empreinte mémoire aussi petite que possible afin que nous puissions maximiser les ressources sur l'appareil pour l'application de l'utilisateur final qui s'exécute . Idéalement, nous devrions pouvoir lire un morceau de fichier du disque dans la mémoire, le transformer en tampon pour l'envoyer au GPU, puis libérer ce morceau de mémoire. J'ai essayé de concevoir le système de cette façon en utilisant shared_ptr, de sorte que j'aurais un système d'allocation de mémoire de comptage de références pour les tampons. Cependant, j'ai trouvé en pratique que puisque la bibliothèque de tâches que j'utilisais ne savait pas si elle devait réexécuter le graphique de tâches avec plusieurs entrées, la bibliothèque n'a pas libéré le lambda capturant la référence au tampon au fur et à mesure. Cela signifie que leshared_ptrqui a été capturé par le lambda est toujours référencé et ne libère donc sa mémoire qu'après la destruction du graphe de tâches, ce qui ne se produit que lorsque l'exécution du graphe entier est terminée.

Conclusion

Dans l'ensemble, j'ai eu beaucoup de plaisir à travailler et à réfléchir à ce projet. C'était très différent de beaucoup d'autres projets que j'ai réalisés. J'espère que vous avez apprécié la lecture de cet article. Ma mise en œuvre complète est liée en haut de cet article. Si vous avez des commentaires ou des idées de choses que vous avez aimées ou que vous feriez différemment, n'hésitez pas à me contacter. Merci!