Panoramica

Qualche mese fa ho iniziato a lavorare su un prototipo di un database relazionale in Metal. Apple aveva appena rilasciato M1 Max e M1 Ultra pochi mesi prima con fino a 128 GB di memoria unificata (nel Mac Studio).

L'ho vista come un'opportunità per fare qualcosa con un'elaborazione molto pesante che richiedeva molta memoria GPU: elaborare grandi tabelle relazionali su una GPU.

Non sono stato il primo a pensare di scrivere un database relazionale su una GPU. Database come BlazingSQL , un database relazionale GPU basato su Rapids.AI . Rapids.AI è una libreria Python di NVIDIA che rispecchia la funzionalità di molte librerie Python popolari, come Pandas, ma esegue le funzioni equivalenti sulla GPU. NVIDIA ha investito molto nel data center e ha contribuito a sviluppare più strumenti che funzionano sulle loro carte, in particolare per l'apprendimento automatico e l'elaborazione di dati di grandi dimensioni.

Guardando le conferenze Apple di recente, ho sentito che ci sono molte prestazioni potenziali che non vengono realmente utilizzate. Da quello che ho visto, gli sviluppatori stanno sfruttando le nuove capacità grafiche dei nuovi chip. Dal punto di vista informatico, sono mancate le demo e il software open source realizzato con Metal. Apple ha realizzato un progetto di esempio di una simulazione di particelle, presumo per mostrare l'equivalente del campione CUDA. Mostrano come è possibile utilizzare il calcolo in CUDA e il rendering in OpenGL sulla GPU senza dover tornare alla CPU nel mezzo. L'altro posto in cui Apple ha utilizzato pesantemente la GPU è per le attività di intelligenza artificiale. Ogni volta che il Neural Engine non supporta un'operazione in un modello, CoreML eseguirà automaticamente il fallback sulla GPU per ottenere maggiori prestazioni. Mentre questo è molto utile e affascinante,

Ho scelto un database relazionale perché mi capita di amare davvero i database e ho pensato a una serie di progetti per loro, alcuni dei quali ho costruito prototipi nel corso degli anni. Anche i database relazionali sono interessanti poiché utilizzano stringhe e valori nulli. Sia l'esempio AI che il simulatore di particelle, sebbene molto impressionanti, usano solo float e numeri interi.

L'implementazione che ho creato può essere trovata qui: MetalDB Github

Idee di design

Non ricordo se fosse proprio all'inizio o da qualche parte nel mezzo del processo, tuttavia sono stato ispirato dalla documentazione di BigQuery Query Plans che parlava di un grafico delle fasi della query che compongono un piano di esecuzione della query.

Una delle principali limitazioni di progettazione con Metal è che tutta la memoria deve essere dimensionata staticamente in fase di compilazione. Ciò presentava delle sfide perché non potevo copiare una stringa poiché non sapevo quante stringhe c'erano in una riga del database o quanto sarebbe lunga ogni stringa al momento della compilazione.

Ho pensato che utilizzare un algoritmo di somma dei prefissi per copiare tutti i dati dalla GPU alla CPU in modo efficiente sarebbe stato più semplice se ogni thread elaborasse una riga. Avevo anche bisogno di utilizzare il più grande blocco sincronizzabile disponibile, che in Metal è un ThreadGroup.

In parte come ottimizzazione e in parte come sfida personale, volevo massimizzare la quantità di lavoro svolto sulla GPU. Per questi motivi, ho deciso di iniziare con la lettura dei file CSV sulla CPU e l'analisi CSV sulla GPU.

Durante l'implementazione, volevo anche essere in grado di testare il database sulla CPU in modo che i test unitari potessero essere eseguiti in un debugger. Per questo motivo, ho impostato la pipeline di compilazione in modo che tutti i miei kernel Metal siano scritti come intestazioni. Di conseguenza ho potuto includerli nei file del kernel Metal, ma anche includerli nei test in C++. Questo design mi permetterebbe anche di definire costanti e tipi nelle intestazioni Metal e garantire che fossero sempre gli stessi nel codice C++ che lo chiamerebbe.

Background sui Threadgroup e sui concetti di Metal

Come sfondo per ulteriori idee e spiegazioni, l'esecuzione di Metal è organizzata in griglie. Una griglia è un gruppo 1D, 2D o 3D di ThreadGroup. Un ThreadGroup è un gruppo sincronizzabile all'interno di quella griglia. I thread all'interno di un ThreadGroup vengono interrotti ed eseguiti in ulteriori gruppi, chiamati warp.

Un thread è il blocco più basilare nella programmazione GPU e si traduce approssimativamente nel modello di un thread su un core della CPU. È un'esecuzione singola, lineare e ordinata di istruzioni. Il thread ha registri a cui può accedere direttamente, nonché leggere e scrivere nella memoria condivisa. È un modello di memoria diverso rispetto alla CPU, ma questo va oltre lo scopo di questo articolo.

Un warp (chiamato SIMD nella documentazione di Metal) è spesso un gruppo di 16 o 32 thread. La stessa istruzione deve essere eseguita contemporaneamente su tutti i thread in un warp, anche se potenzialmente su dati differenti (SIMD, Single Instruction, Multiple Data). Se alcuni dei thread prendono un percorso diverso nel codice, tutti i thread all'interno di quel warp devono attendere che tutti i rami vengano eseguiti in serie. Ciò porta a progettare il codice GPU con il minor numero possibile di rami, in modo tale da mantenere occupati il ​​​​più possibile tutti i thread all'interno di un warp.

Altri sistemi come CUDA e OpenCL hanno concetti simili, solo con nomi diversi.

Implementazione

Link all'implementazione:https://github.com/mattpaletta/metaldb

A mio parere, penso che abbia più senso parlare dell'implementazione nell'ordine del flusso di dati attraverso il sistema. Tuttavia, questo è quasi l'inverso perfetto di come ho fatto per implementarlo.

Binario

Il risultato finale che viene prodotto è molto semplice. È un binario chiamato metaldbe contiene solo una funzione principale. Ho reso l'applicazione molto leggera in modo che io, così come altri, potessi riutilizzare facilmente le librerie interne come parte di altre librerie e applicazioni in futuro.

Motore

Il motore è dove la maggior parte della logica del sistema è coordinata. Il motore interagisce con QueryPlanner, implementato nella libreria QueryPlanner, nonché con Scheduler, che è responsabile dell'esecuzione e del coordinamento dell'esecuzione del piano di query generato.

Analizzatore di query

Il Query Parser è il componente responsabile della trasformazione di una query simile a SQL in un AST che può essere analizzato più facilmente dal resto del sistema.

Questa prima versione del database non implementa un Query Parser. Invece, ho codificato l'AST per varie query che voglio testare. Scrivere un parser e produrre un AST, sebbene sembri molto interessante, è qualcosa che ho fatto in un altro progetto e non era il focus di questo progetto.

Inoltre, non intendevo che questo progetto fosse un database pronto per la produzione. Pertanto non ha bisogno di un parser di query in questo momento, ma tutti gli stub sono lì per me per implementarlo in un secondo momento se lo desidero.

Oltre al sistema che accetta stringhe di query, ho intenzione di implementare eventualmente un'API Dataframe, simile a Pandas, ma in C++. Dal mio punto di vista, questo tipo di API sarebbe più semplice per altre librerie con cui lavorare. Ciò evita anche il passaggio dell'altra libreria che deve produrre una stringa di query solo per essere immediatamente analizzata dal parser. Anche questa API Dataframe viene lasciata come lavoro futuro.

Come set di dati di prova ho utilizzato per la prima volta il set di dati Iris disponibile al pubblico . Ho scelto questo set di dati perché è relativamente piccolo, in formato CSV e principalmente numeri, senza valori nulli.

Dopo aver fatto funzionare quel set di dati, volevo provare un set di dati molto più grande con più file. Per questo ho utilizzato il set di dati dei taxi di New York . Questo set di dati più ampio ha dimostrato alcune sfide interessanti che non mi aspettavo, ne parleremo più avanti.

Pianificatore di query

Dopo che Query Parser ha generato l'AST, il componente successivo è Query Planner. Questo è responsabile della trasformazione dell'AST in un piano di esecuzione ottimizzato.

Il primo passo per creare un piano di esecuzione ottimizzato è creare un piano. Ispirato dal riferimento BigQuery , mi è piaciuta l'idea di suddividere un piano di esecuzione in un grafico di "Fasi". In BigQuery, ogni fase è composta da uno o più passaggi. Ogni passaggio potrebbe essere una lettura o una scrittura, un aggregato o un join, ecc. Non volevo scendere alla granularità dei passaggi, ma ho un concetto simile, che chiamo "parziale".

Per passare da un AST a un grafico di stadi, elenco prima i file su disco per le tabelle. Successivamente vado alle foglie dell'AST e per ognuna di esse produco un nuovo stage che leggerà quel file.

Mentre risalgo l'albero, decido se creerò un nuovo partial come parte dello stage esistente o creerò un nuovo stage. Il punto chiave è quando devo passare dalla GPU alla CPU o viceversa per un passaggio, creo una nuova fase. Ciò significa che è possibile elaborare quanti più dati sulla GPU riducendo al minimo i tempi di trasferimento tra CPU e GPU. Ciò è particolarmente rilevante per i dispositivi che non dispongono di memoria unificata.

Ogni stage ha una singola lista di parziali da eseguire. Questi verranno successivamente tradotti come istruzioni per la GPU all'interno di quella fase, poiché esploreremo di più nella sezione sullo scheduler.

Ogni volta che creo un nuovo stage, inserisco una "Shuffle Instruction", che dice alla GPU di copiare le informazioni nella CPU.

In futuro, scriverei anche un ottimizzatore in grado di riscrivere le query per ridurre al minimo la quantità di dati letti da ciascun file e copiati nuovamente nella CPU dopo essere stati letti.

Programmatore

Lo scheduler è responsabile dell'esecuzione parallela della query. Sono stato tentato di scrivere la mia libreria multithread per farlo. Ho finito per scrivere la mia implementazione su TaskFlow , una libreria di grafici di attività C++ open source.

Ad alto livello, la creazione del grafico delle attività segue il grafico delle fasi. Ogni fase è un'attività nel grafico e dipende dai suoi figli.

All'interno di una fase, ogni parziale, l'elenco dei passaggi da eseguire sulla CPU o sulla GPU, viene espanso in ordine. Poiché ogni parziale viene registrato, ha diverse attività all'interno del grafico delle attività a cui può agganciarsi.

L'attività principale a cui è possibile agganciarsi è l'attività di codifica dell'attività precedente. Il partial dovrebbe creare una nuova attività che dipende dall'attività di codifica parziale padre. Utilizza l'Encoder passato per codificarsi in una rappresentazione serializzata che può essere inviata alla GPU. Per la maggior parte delle attività, questo è tutto ciò che è necessario e l'implementazione del partial è sulla GPU in Metal.

L'altra attività disponibile è l'attività di lavoro. Questo esiste nel caso in cui un partial voglia sovrascrivere qualcosa su come il lavoro viene eseguito per quel partial invece del comportamento predefinito.

La maggior parte delle attività legge i buffer da una o più fasi figlio e scrive nel relativo buffer di output. L'istruzione di lettura è unica perché deve leggere dal disco, non dai buffer figli.

L'istruzione di lettura imposta una catena di attività che leggono il file CSV (l'unico tipo di file attualmente implementato) che gli è stato assegnato e lo leggono in un buffer. Durante la lettura in un buffer, tiene traccia dell'offset della riga corrente e li memorizza come parte RawTabledell'oggetto, descritto di seguito.

Una volta che il file è stato letto, la GPU è libera di iniziare a elaborare le righe. Il design del database richiede un thread per riga. Metal sembra avere un limite al numero di thread che possono essere assegnati per ThreadGroup. Pertanto, prima dividiamo le righe in più buffer che verranno inviati ciascuno alla GPU in modo indipendente.

TaskFlow consente attività secondarie dinamiche all'interno di un'attività. Quando ricevo RawTable, interrogo il numero di thread che Metal mi consente di pianificare e suddividere le righe originali in blocchi di quella dimensione.

Ogni blocco viene quindi inviato alla GPU in parallelo.

Dopo che tutti i blocchi sono stati elaborati, eseguo un'attività di unione che copia tutti gli OutputRowoggetti dalla GPU e li unisce in un unico gigante in OutputRowmodo che la fase successiva possa leggerli insieme.

In futuro, vorrei ottimizzare la suddivisione di più lotti. Non appena il batch è stato suddiviso, può essere inviato alla GPU. Non appena quel blocco ritorna, può essere copiato nel buffer finale mentre le altre attività vengono elaborate in modo asincrono.

Inoltre, vorrei liberare l'originale RawTableuna volta che tutte le righe sono state suddivise in blocchi, ognuno dei quali memorizza una copia. Inoltre, dovrei essere in grado di liberare il buffer di output dal blocco non appena è stato copiato nel buffer finale, riducendo la quantità totale di memoria richiesta.

Istruzione ParseRow

Il ParseRowInstructioninizia con una semplice premessa. Dato un elenco di indici per l'inizio di ogni riga e informazioni sul numero di righe e sui tipi di colonne, analizzare i valori per una particolare riga, eseguire il cast sui tipi corretti.

Il tipo di colonna più semplice è una stringa. Per la riga N , possiamo saltare all'inizio di quella riga cercando il suo indice, che la CPU ha memorizzato quando abbiamo letto il file dal disco. Possiamo quindi ottenere un puntatore a quell'indice. Questo è l'inizio della riga. La fine di ogni colonna è la posizione prima della virgola successiva (che segna la colonna successiva) quando andiamo avanti di un carattere alla volta, o uno prima dell'inizio della riga successiva (se è l'ultima colonna della riga), o uno prima della fine del buffer (se è l'ultima colonna dell'ultima riga).

L'istruzione legge prima ogni colonna come una stringa. Analizza una colonna esattamente come descritto e la legge come una stringa, carattere per carattere. Ora per leggere la colonna successiva, iniziamo dall'inizio della riga. Quando arriviamo alla prima virgola, la contrassegniamo come inizio e andiamo fino alla virgola successiva. Il processo si ripete per le colonne successive.

Se abbiamo un numero intero, passiamo i puntatori all'inizio e alla fine della stringa a una stoifunzione personalizzata. Questo è simile a quello della libreria standard C, che converte la stringa in una rappresentazione intera. Ho scritto anche la mia versione di stof.

Come puoi immaginare, leggere ogni colonna dall'inizio della riga ogni volta è molto lento e c'è molto lavoro duplicato. Possiamo fare di meglio, molto meglio.

La prima realizzazione nell'ottimizzazione della ricerca dell'inizio della colonna è che spesso c'è un basso numero di colonne. Ho scelto 16 come numero arbitrario di colonne da memorizzare nella cache.

Con questo primo livello di cache, se sto leggendo una colonna all'interno delle prime 16 colonne, provo a leggere il puntatore precedentemente memorizzato nella cache per quella colonna. Se non è nullo, ho già il valore. Le righe sono immutabili, quindi il puntatore deve essere valido e il processo è terminato!

Se il puntatore è nullo, posso scorrere la mia cache all'indietro dall'indice della sedicesima colonna finché non trovo una colonna precedentemente memorizzata nella cache o arrivo alla prima voce.

Da qualunque punto mi fermi, posso scorrere la riga in modo ingenuo, un carattere alla volta. Ogni volta che trovo una virgola, memorizzo il puntatore all'inizio di quella colonna nella mia cache in modo che le query successive possano saltare direttamente lì.

Ciò significa che l'accesso casuale alle prime 16 colonne dovrebbe essere sostanzialmente gratuito in quanto diventa una ricerca diretta del puntatore. Questo esclude il primo accesso, che è O(n) .

E le righe con più di 16 colonne? So già dov'è la quindicesima colonna (a partire da 0), quindi posso saltare direttamente alla quindicesima colonna e poi interagire in modo ingenuo. Se non so dove si trova la quindicesima colonna, posso calcolarla rapidamente e memorizzarla nella cache.

Questo è abbastanza buono, tranne che c'è un'altra ottimizzazione che può essere fatta. L'altra realizzazione è che all'interno di ParseRowInstruction mentre sta costruendo la riga di output, accede alle colonne in ordine. Oltre alla cache casuale a dimensione fissa per le prime 16 colonne, possiamo mantenere un puntatore aggiuntivo che memorizza l'inizio dell'ultima colonna a cui si è avuto accesso e l'indice di quella colonna. Ciò consente una ricerca diretta del puntatore per accessi sequenziali per qualsiasi numero di colonne, senza dover memorizzare un numero infinito di puntatori, come nel primo livello di memorizzazione nella cache. Naturalmente, questi due livelli di memorizzazione nella cache funzionano insieme. Man mano che aggiorniamo i primi 16 valori, aggiorniamo anche il last_accessedpuntatore.

Quando si esegue sulla GPU, ogni thread è responsabile di una singola riga. Quindi ogni thread ha la propria cache multistrato come descritto. La cache tiene anche traccia di quale riga stiamo memorizzando nella cache. Se è diverso da quello richiesto, resettiamo la cache, quindi sappiamo che la cache è sempre rilevante. È possibile espandere questo per coprire casi d'uso di lettura di più righe o condivisione della cache tra thread, ma questo esulava dall'ambito dell'implementazione iniziale.

Istruzioni di proiezione

Il ProjectionInstructionè molto semplice in confronto. Viene fornito un elenco di indici di colonna da recuperare. Crea un nuovo oggetto TempRow e copia quelle colonne dall'ultimo TempRow, aggiornando i metadati nel nuovo oggetto TempRow.

Istruzioni per il filtro

L'implementazione di base di FilterInstructionè progettata per valutare una riga rispetto a un'espressione che restituisce trueo false.

Questo è stato implementato come una macchina virtuale basata su stack. L'allocazione dello stack è fissata in fase di compilazione e quindi alloca sempre la sua dimensione massima.

Lo stack è stato in qualche modo interessante da implementare. Ho scelto di progettare il bytecode per la VM per includere i tipi e le istruzioni per trasmettere un tipo a un altro. L'implementazione dello stack consente dati eterogenei, ma il chiamante è responsabile della fornitura dei tipi.

In una pila normale, puoi creare scatole per un oggetto e la scatola memorizzerà il tipo dell'oggetto oltre a un puntatore all'oggetto. In questo caso, il compilatore (non ancora implementato) è responsabile della scrittura del bytecode per includere tutto il casting necessario. Ciò consente al runtime di inserire un numero intero nello stack, che è xbyte, e in seguito, quando va a leggere un numero intero, può xestrarre i byte dallo stack e ottenere lo stesso numero intero. Non sono richieste scatole o casting dinamico. Ciò impone al compilatore l'onere di ottenere tutti i tipi corretti, ma ciò viene lasciato per l'implementazione futura.

Istruzione di uscita

Viene utilizzato per combinare tutti i OutputInstructiondati dai singoli thread all'interno del ThreadGroup e rimuovere tutti i dati duplicati di cui ogni singolo thread ha bisogno, ma che devono essere copiati solo una volta nella CPU e inseriti in modo efficiente in un grande buffer .

Il primo passaggio è che ogni riga (ogni thread) calcola la propria dimensione. Quindi eseguiamo una somma di prefissi delle dimensioni. Questo ci dà un indice in cui sappiamo che possiamo iniziare a scrivere i nostri dati.

La somma del prefisso è un algoritmo spesso utilizzato nel calcolo della GPU in cui dato un array di numeri interi, restituisce un nuovo array dove per ogni indice i, contiene la somma di tutti gli elementi inferiori a i . Se la somma include l'elemento i per la posizione i , è chiamata somma inclusiva, altrimenti è chiamata somma esclusiva. Ho utilizzato una somma esclusiva per la mia implementazione.

Prima di poter iniziare a scrivere i dati, i thread devono coordinare la scrittura dell'intestazione del file OutputRow. Per fare ciò, la prima riga, responsabile della scrittura dell'intestazione, aggiunge anche la dimensione dell'intestazione alla propria dimensione. Dopo aver eseguito la somma dei prefissi, eseguiamo anche una riduzione delle dimensioni delle righe in modo che il primo thread sia in grado di scrivere il numero totale di byte nell'intestazione.

Una volta completato, ogni riga può saltare al suo offset dall'output della somma dei prefissi e copiare i suoi byte nel buffer a partire da quel punto in parallelo, e siamo certi che non ci saranno collisioni.

TempRow

È TempRowla struttura dei dati che viene passata mentre i dati vengono elaborati in Metal. Idealmente, dovremmo allocare un ridimensionabile TempRowsull'heap, per ridurre al minimo l'impronta di memoria, ma poiché Metal non supporta le allocazioni dinamiche della memoria. Ogni TempRowè un buffer di dimensioni fisse. L'ho scelto per essere 1024 byte o 1 kilobyte. La prima sezione di TempRowè un'intestazione, seguita dai dati.

Il primo valore nell'intestazione è la sua lunghezza. Questo è importante perché i dati iniziano immediatamente dopo l'intestazione e la dimensione dell'intestazione è variabile a seconda del numero di colonne e dei relativi tipi.

Il byte successivo è il numero di colonne. Poiché questo è solo 1 byte, il numero massimo di colonne è quindi 256. Ritengo che sia sufficiente per la maggior parte dei casi d'uso.

I prossimi N byte sono i tipi di colonna. Le colonne possono essere una di: Integer, o Floati Stringrelativi equivalenti nullable. Un valore booleano è semplicemente espresso come numero intero.

Un numero intero e un float hanno sempre una dimensione costante, quindi non è necessario memorizzare la loro dimensione nell'intestazione, a meno che non si tratti di una colonna nullable. Al contrario, una stringa può avere qualsiasi numero di caratteri. Pertanto memorizziamo la dimensione di tutte le colonne di lunghezza variabile (stringhe e colonne opzionali) nei byte successivi. Di nuovo, poiché la dimensione di una colonna è di solo 1 byte, la lunghezza massima di una stringa è di 256 caratteri.

Dopo l'intestazione, tutti i dati per le colonne vengono aggiunti uno dopo l'altro.

Per semplificare la costruzione di TempRow, esiste una classe helper in TempRowBuildercui il chiamante può scrivere tutti i tipi e le dimensioni delle colonne, ecc. In array separati. Il TempRowpuò quindi essere banalmente costruito dal builder copiando i valori.

I dati delle colonne possono quindi essere aggiunti in ordine. Esistono metodi di supporto per aiutare a copiare stringhe, numeri interi e float e scriverli byte per byte.

Quando il metodo successivo va quindi a leggere TempRow, esistono metodi di supporto che leggono dall'intestazione per determinare gli indici di inizio e fine nel buffer per quella colonna e ritrasformano i byte nel tipo appropriato. Il chiamante è responsabile ColumnTypedell'interrogazione della colonna a cui è interessato, prima di leggerla come quel tipo.

Poiché TempRowlegge tutti i dati direttamente da un buffer di dimensioni fisse, potrebbe essere banalmente adattato a una constexprclasse per altre applicazioni.

OutputRow

OutputRowviene creato da (descritto sopra) e ha lo OutputRowInstructionscopo di spostare più righe che condividono lo stesso schema. Sarebbe uno spreco copiare TempRowdirettamente tutti i singoli oggetti perché ogni riga ha lo stesso schema, quindi ci sono molti metadati duplicati. Invece, copiamo tutti i dati in una singola struttura in modo tale da poterli copiare in TempRowoggetti separati se necessario in seguito o dividerli in due o più OutputRowoggetti se necessario.

Simile a TempRow, OutputRowha una definizione di intestazione, sebbene sia leggermente diversa da TempRow. Il primo valore, come spiegato in precedenza, è la dimensione dell'intestazione, ma questo valore è maggiore, con 2 byte allocati invece di 1. Il valore successivo è il numero di byte in OutputRow, e questo è un numero intero senza segno a 32 bit. Dopo questo è il numero di colonne, e questo è solo un singolo byte. Seguito dai tipi di colonna, simili a TempRow.

Dopo l'intestazione, vengono aggiunti tutti i dati. Poiché the OutputRowè sempre costruito da uno o più TempRowo da another OutputRow, possiamo calcolare la dimensione dei dati di ogni riga in parallelo utilizzando l'algoritmo della somma dei prefissi e scrivere nel buffer dei dati in parallelo.

Quando si esegue in Metal, OutputRowviene allocato staticamente a una dimensione fissa di 1.000.000 di byte. Sulla CPU, possiamo essere più efficienti e utilizzare a std::vectorper allocare solo la quantità di spazio di cui abbiamo bisogno.

Per facilitare meglio la lettura e la scrittura di ogni thread OutputRowin parallelo, invece di scrivere le dimensioni delle colonne di dimensioni variabili nell'intestazione così come sono in TempRow, vengono invece anteposte ai dati per quella colonna per riga. Quindi, ad esempio, una riga con 2 numeri interi seguiti da una stringa di 3 caratteri “abc”, avrebbe il formato: <integer><integer>3abc. Il lettore di OutputRow(attualmente implementato solo sulla CPU) sa che la colonna è una stringa, e può quindi saltare all'inizio della stringa per leggerne il contenuto. Le dimensioni di ogni riga non sono scritte nel fileOutputRow. Invece, il lettore scorre il buffer e registra l'inizio di ogni riga e le dimensioni di ogni colonna di dimensione variabile per ogni riga. Questo è stato fatto per risparmiare spazio, ma potrebbe essere ottimizzato per essere scritto nell'intestazione o per riga, in modo tale che la lettura OutputRowsia più efficiente e quindi più veloce. I dettagli della lettura, divisione e unione OutputRowdi oggetti sulla CPU sono stati discussi brevemente in precedenza nella sezione relativa al file Scheduler.

Lavoro futuro

Ho lavorato a questo progetto come esperimento per vedere se fosse possibile. Ci sono molte cose che mi sarebbe piaciuto implementare, se avessi intenzione di renderlo pronto per la produzione, o anche solo dedicare più tempo al prototipo di quello che ho.

Quel bug

Il primo problema che mi piacerebbe risolvere è (quello che credo sia un bug in Xcode 13), in cui a più thread viene assegnato il thread 0 all'interno di un ThreadGroup. Fammi sapere se hai qualche idea. Ciò fa sì che più thread provino a scrivere l'intestazione. Ciò comporta che l'intestazione venga parzialmente schiacciata con i dati, a seconda dell'ordine dei thread. Ho provato a cercarlo su Google, ma non sono riuscito a trovare nessuna fonte particolarmente utile. Penso che avesse a che fare con la quantità di memoria che stavo cercando di allocare a ciascun thread. Sfortunatamente la documentazione ufficiale di Apple non dice nulla di ciò che ho potuto trovare.

Motore di query + parser

Il prossimo grande compito è implementare un parser e un motore di query in modo che il database possa accettare query simili a SQL e trasformarle in piani di query ed eseguirle. Questa attività comporta anche l'implementazione di un'API DataFrame o la scrittura in più formati su disco, da utilizzare da altre librerie e programmi.

Partecipa + Raggruppa per

Espandendo le specifiche SQL, sarebbe divertente poter calcolare un join e una clausola Group By. Ho pensato che il modo ingenuo per implementare un join fosse calcolare ogni riga non elaborata sulla GPU in parallelo, quindi eseguire un hash-join sulla CPU, una volta per blocco. Tuttavia, potrebbe essere più efficiente invece trovare un modo per inviare invece un blocco da 2 tabelle diverse a cui si desidera unire contemporaneamente e fare in modo che la GPU restituisca le righe unite.

Per Group By, potresti farlo sulla CPU o forse fare un'aggregazione parziale sulla GPU. Oppure potresti fare una combinazione in base alla quale esegui l'elaborazione grezza iniziale sulla GPU, quindi esegui un kernel diverso dove, dato un set di righe, calcola il gruppo per ogni riga all'interno del set. Ciò consentirebbe di raggruppare rapidamente le righe sulla CPU in cui è possibile allocare più dati per conservare le righe, sfruttando al contempo la natura parallela della GPU per calcolare i gruppi in parallelo.

Sistema distribuito

Se questo sistema verrà utilizzato in produzione, probabilmente dovrà essere in grado di sfruttare più macchine. Potrei immaginare una rete eterogenea di dispositivi connessi Apple (e non Apple) che lavorano insieme. Immagina un iPhone come controller host che invia comandi alle altre macchine e un gruppo di iPad che elaborano ciascuno i dati che hanno localmente e inviano le righe elaborate al controller centrale. In alternativa, forse hai una distribuzione cloud che esegue lo stesso codice sulla CPU in un'istanza lambda AWS o su più GPU con un server Mac Pro on premise. Tutti questi sistemi potrebbero lavorare insieme per darti un accesso reattivo molto rapido a set di dati molto grandi con dispositivi che (credo) abbiano ancora molta potenza di elaborazione non sfruttata ancora disponibile.

Ridurre l'impronta di memoria

Come ulteriore ottimizzazione, soprattutto perché voglio che funzioni su qualsiasi dispositivo che esegue Metal, sarebbe bello mantenere il footprint di memoria il più piccolo possibile in modo da poter massimizzare le risorse sul dispositivo per l'applicazione dell'utente finale in esecuzione . Idealmente, dovremmo essere in grado di leggere una parte di un file dal disco alla memoria, trasformarlo in un buffer per inviarlo alla GPU e quindi liberare quella parte di memoria. Ho provato a progettare il sistema in questo modo utilizzando shared_ptr, in modo tale da avere un sistema di allocazione della memoria per il conteggio dei riferimenti per i buffer. Tuttavia ho scoperto in pratica che poiché la libreria delle attività che stavo usando non sapeva se era necessario rieseguire il grafico delle attività con più input, la libreria non ha liberato il lambda catturando il riferimento al buffer mentre procedeva. Ciò significa che ilshared_ptrche è stato catturato dal lambda è ancora referenziato e quindi non libera la sua memoria fino a quando il grafico dell'attività non viene distrutto, cosa che accade solo quando l'intero grafico termina l'esecuzione.

Conclusione

Nel complesso mi sono divertito molto a lavorare e pensare a questo progetto. Era molto diverso da molti altri progetti che ho fatto. Spero ti sia piaciuto leggere questo articolo. La mia implementazione completa è collegata all'inizio di questo articolo. Se hai commenti o idee su cose che ti sono piaciute o che faresti diversamente, non esitare a contattarmi. Grazie!