Visão geral

Há alguns meses comecei a trabalhar em um protótipo de banco de dados relacional em Metal. A Apple havia acabado de lançar o M1 Max e o M1 Ultra alguns meses antes com até 128 GB de memória unificada (no Mac Studio).

Vi isso como uma oportunidade de fazer algo com processamento muito pesado que exigia muita memória da GPU: processar grandes tabelas relacionais em uma GPU.

Não fui o primeiro a pensar em escrever um banco de dados relacional em uma GPU. Bancos de dados como o BlazingSQL , um banco de dados relacional de GPU criado em Rapids.AI . Rapids.AI é uma biblioteca Python da NVIDIA que espelha a funcionalidade de muitas bibliotecas Python populares, como Pandas, mas executa as funções equivalentes na GPU. A NVIDIA vem investindo fortemente no data center e ajudando a desenvolver mais ferramentas que rodam em suas placas, principalmente para aprendizado de máquina e processamento de grandes volumes de dados.

Ao assistir às conferências da Apple recentemente, senti que há muito potencial de desempenho que não está realmente sendo usado. Pelo que tenho visto, os desenvolvedores estão aproveitando os novos recursos gráficos dos novos chips. No lado da computação, faltam as demos e o software de código aberto construído com o Metal. A Apple fez um projeto de amostra de uma simulação de partícula, presumo mostrar o equivalente à amostra CUDA. Eles mostram como você pode usar computação em CUDA e renderizar em OpenGL na GPU sem ter que voltar para a CPU no meio. O outro lugar em que a Apple tem usado fortemente a GPU é para tarefas de IA. Sempre que o Neural Engine não for compatível com uma operação em um modelo, o CoreML recorrerá automaticamente à GPU para obter mais desempenho. Embora isso seja muito útil e fascinante,

Escolhi um banco de dados relacional porque realmente amo bancos de dados e pensei em vários designs para eles, alguns dos quais construí protótipos ao longo dos anos. Bancos de dados relacionais também são interessantes, pois usam strings e valores nulos. Tanto o exemplo de IA quanto o simulador de partículas, embora muito impressionantes, usam apenas floats e integers.

A implementação que construí pode ser encontrada aqui: MetalDB Github

ideias de design

Não lembro se foi logo no começo ou no meio do processo, porém me inspirei na documentação do BigQuery Query Plans que falava sobre um gráfico de estágios de query que compõem um plano de execução de query.

Uma das principais limitações de design do Metal é que toda a memória precisa ser dimensionada estaticamente em tempo de compilação. Isso apresentou desafios porque eu não conseguia copiar uma string, pois não sabia quantas strings havia em uma linha do banco de dados ou quanto tempo cada string teria no tempo de compilação.

Achei que usar um algoritmo de soma de prefixo para copiar todos os dados de volta da GPU para a CPU de maneira eficiente seria mais simples se cada thread processasse uma linha. Também precisei usar o maior bloco sincronizável disponível, que no Metal é um ThreadGroup.

Parcialmente como uma otimização e parcialmente como um desafio pessoal, eu queria maximizar a quantidade de trabalho feito na GPU. Por esses motivos, optei por começar lendo arquivos CSV na CPU e fazendo a análise CSV na GPU.

Durante a implementação, eu também queria poder testar o banco de dados na CPU para que os testes de unidade pudessem ser executados em um depurador. Por esse motivo, configurei o pipeline de construção para ter todos os meus kernels do Metal escritos como cabeçalhos. Como resultado, pude incluí-los nos arquivos do kernel do Metal, mas também incluí-los nos testes em C++. Esse design também me permitiria definir constantes e tipos em cabeçalhos de Metal e garantir que eles fossem sempre os mesmos no código C++ que os chamaria.

Antecedentes sobre Threadgroups e conceitos de Metal

Como pano de fundo para mais ideias e explicações, a execução do Metal é organizada em grades. Uma grade é um grupo 1D, 2D ou 3D de ThreadGroups. Um ThreadGroup é um grupo sincronizável dentro dessa grade. As threads dentro de um ThreadGroup são quebradas e executadas em outros grupos, chamados warps.

Um thread é o bloco mais básico na programação de GPU e se traduz aproximadamente no modelo de um thread em um núcleo de CPU. É uma execução de instruções única, linear e em ordem. A thread possui registradores que podem ser acessados ​​diretamente, bem como lidos e gravados na memória compartilhada. É um modelo de memória diferente do da CPU, mas isso está além do escopo deste artigo.

Um warp (chamado SIMD na documentação do Metal) geralmente é um grupo de 16 ou 32 threads. A mesma instrução deve ser executada ao mesmo tempo em todas as threads de um warp, embora potencialmente em dados diferentes (SIMD, Single Instruction, Multiple Data). Se alguns dos encadeamentos tomarem um caminho diferente no código, todos os encadeamentos dentro desse warp devem esperar que todos os ramos sejam executados em série. Isso leva a projetar o código da GPU com o menor número de ramificações possível, de modo que você mantenha todos os threads dentro de um warp ocupados o máximo possível.

Outros sistemas como CUDA e OpenCL possuem conceitos semelhantes, apenas com nomes diferentes.

Implementação

Link para implementação:https://github.com/mattpaletta/metaldb

Na minha opinião, acho que faz mais sentido falar sobre a implementação na ordem do fluxo de dados pelo sistema. No entanto, isso é quase o inverso perfeito de como eu o implementei.

Binário

O resultado final produzido é muito simples. É um binário chamado metaldbe tem apenas uma função principal nele. Tornei o aplicativo muito leve para que eu, assim como outros, pudesse reutilizar as bibliotecas internas facilmente como parte de outras bibliotecas e aplicativos no futuro.

Motor

O Motor é onde a maior parte da lógica do sistema é coordenada. O Engine interage com o QueryPlanner, que é implementado na biblioteca QueryPlanner, e também com o Scheduler, que é responsável por executar e coordenar a execução do plano de consulta gerado.

Analisador de consultas

O Query Parser é o componente responsável por transformar uma consulta do tipo SQL em um AST que pode ser analisado mais facilmente pelo restante do sistema.

Esta primeira versão do banco de dados não implementa um Query Parser. Em vez disso, codifiquei o AST para várias consultas que desejo testar. Escrever um analisador e produzir um AST, embora pareça muito interessante, é algo que fiz em outro projeto e não foi o foco deste projeto.

Eu também não pretendia que este projeto fosse um banco de dados pronto para produção. Portanto, ele não precisa de um analisador de consulta neste momento, mas todos os stubs estão lá para eu implementá-lo posteriormente, se assim o desejar.

Além do sistema aceitar strings de consulta, pretendo eventualmente implementar uma API de Dataframe, semelhante ao Pandas, mas em C++. Do meu ponto de vista, esse tipo de API seria mais simples para outras bibliotecas trabalharem. Isso também economiza a etapa da outra biblioteca ter que produzir uma string de consulta apenas para que ela seja imediatamente reanalisada pelo parser. Essa API do Dataframe também é deixada como trabalho futuro.

Como conjunto de dados de teste, usei primeiro o conjunto de dados Iris disponível publicamente . Escolhi este conjunto de dados porque é relativamente pequeno, em formato CSV, e principalmente números, sem valores nulos.

Depois de fazer esse conjunto de dados funcionar, quis experimentar um conjunto de dados muito maior com vários arquivos. Para isso, usei o New York Taxi Dataset . Este conjunto de dados maior provou alguns desafios interessantes que eu não esperava, mais sobre isso mais tarde.

Planejador de consultas

Após o Query Parser ter gerado o AST, o próximo componente é o Query Planner. Este é responsável por transformar o AST em um plano de execução otimizado.

O primeiro passo para fazer um plano de execução otimizado é fazer um plano. Inspirado na referência do BigQuery , gostei da ideia de quebrar um plano de execução em um gráfico de “Estágios”. No BigQuery, cada estágio é composto por uma ou mais etapas. Cada etapa pode ser uma leitura ou gravação, uma agregação ou uma junção, etc. Não queria descer à granularidade das etapas, mas tenho um conceito semelhante, que chamo de “parcial”.

Para ir de um AST para um gráfico de estágios, primeiro listo os arquivos no disco para a(s) tabela(s). A seguir vou para as folhas do AST e para cada uma delas, produzo uma nova etapa que irá ler aquele arquivo.

Enquanto subo na árvore, decido se vou criar uma nova parcial como parte do estágio existente ou criar um novo estágio. O ponto chave é quando tenho que ir da GPU para a CPU ou vice-versa para uma etapa, crio uma nova etapa. Isso significa que o máximo de dados pode ser processado na GPU, minimizando os tempos de transferência entre a CPU e a GPU. Isso é especialmente relevante para dispositivos que não possuem memória unificada.

Cada estágio tem uma lista singular de parciais para executar. Posteriormente, eles serão traduzidos como instruções para a GPU nesse estágio, conforme exploraremos mais na seção sobre o agendador.

Toda vez que crio um novo estágio, insiro uma “Instrução Shuffle”, que diz à GPU para copiar as informações de volta para a CPU.

No futuro, eu também escreveria um otimizador que pudesse reescrever as consultas para minimizar a quantidade de dados lidos de cada arquivo e copiados de volta para a CPU após a leitura.

Agendador

O escalonador é responsável pela execução paralela da consulta. Fiquei tentado a escrever minha própria biblioteca multithread para fazer isso. Acabei escrevendo minha implementação no TaskFlow , uma biblioteca de gráficos de tarefas C++ de código aberto.

Em alto nível, a criação do grafo de tarefas segue o grafo de etapas. Cada estágio é uma tarefa no gráfico e depende de seus filhos.

Dentro de um estágio, cada parcial, a lista de etapas a serem executadas na CPU ou na GPU é expandida em ordem. À medida que cada parcial está sendo registrada, ela possui várias tarefas dentro do gráfico de tarefas às quais pode se conectar.

A principal tarefa que pode ser conectada é a tarefa de codificação da tarefa anterior. A parcial deve criar uma nova tarefa dependente da tarefa de codificação parcial pai. Ele usa o Encoder passado para se codificar em uma representação serializada que pode ser enviada para a GPU. Para a maioria das tarefas, isso é tudo o que é necessário e a implementação da parcial está na GPU do Metal.

A outra tarefa disponível é a tarefa de trabalho. Isso existe no caso de um parcial querer substituir algo sobre como o trabalho é executado para esse parcial, em vez do comportamento padrão.

A maioria das tarefas lê os buffers de um ou mais estágios filhos e grava em seu buffer de saída. A instrução de leitura é única porque precisa ler do disco, não dos buffers filhos.

A instrução de leitura configura uma cadeia de tarefas que lêem o arquivo CSV (o único tipo de arquivo atualmente implementado) que foi atribuído e o lê em um buffer. Como ele está lendo em um buffer, ele rastreia o deslocamento da linha atual e os armazena como parte do RawTableobjeto, descrito abaixo.

Uma vez que o arquivo foi lido, a GPU está livre para começar a processar as linhas. O design do banco de dados exige um thread por linha. Acontece que o Metal tem um limite de quantos encadeamentos podem ser atribuídos por ThreadGroup. Portanto, primeiro dividimos as linhas em vários buffers que serão enviados para a GPU de forma independente.

TaskFlow permite subtarefas dinâmicas dentro de uma tarefa. Quando obtenho o RawTable, consulto o número de threads que o Metal me permite agendar e divido as linhas originais em blocos desse tamanho.

Cada pedaço é então enviado para a GPU em paralelo.

Depois que todos os pedaços foram processados, executo uma tarefa de mesclagem que copia todos os OutputRowobjetos da GPU e os mescla em um único gigante OutputRowpara que o próximo estágio possa lê-los juntos.

No futuro, gostaria de otimizar a divisão de vários lotes. Assim que o lote for dividido, ele pode ser enviado para a GPU. Assim que esse pedaço voltar, ele pode ser copiado para o buffer final enquanto as outras tarefas são processadas de forma assíncrona.

Além disso, gostaria de liberar o original RawTableassim que todas as linhas forem divididas em partes, cada uma armazenando uma cópia. Além disso, devo ser capaz de liberar o buffer de saída do bloco assim que ele for copiado para o buffer final, reduzindo a quantidade total de memória necessária.

Instrução ParseRow

O ParseRowInstructioncomeça com uma premissa simples. Dada uma lista de índices para o início de cada linha e informações sobre o número de linhas e os tipos de colunas, analise os valores de uma determinada linha, converta em seus tipos corretos.

O tipo de coluna mais simples é uma string. Para a linha N , podemos pular para o início dessa linha procurando seu índice, que a CPU armazenou quando lemos o arquivo do disco. Podemos então obter um ponteiro para esse índice. Este é o início da linha. O fim de qualquer coluna é a posição antes da próxima vírgula (marcando a próxima coluna) quando avançamos um caractere de cada vez, ou um antes do início da próxima linha (se for a última coluna da linha), ou um antes do final do buffer (se for a última coluna da última linha).

A instrução lê cada coluna como uma string primeiro. Ele analisa uma coluna exatamente como descrita e a lê como uma string, caractere por caractere. Agora, para ler a próxima coluna, começamos no início da linha. Quando chegamos à primeira vírgula, marcamos isso como o começo e vamos até a vírgula depois disso. O processo se repete para as colunas subsequentes.

Se tivermos um número inteiro, passamos os ponteiros para o início e o fim da string para uma stoifunção personalizada. Isso é semelhante ao da biblioteca padrão C, que converte a string em uma representação inteira. Eu escrevi minha própria versão stoftambém.

Como você pode imaginar, ler cada coluna desde o início da linha é muito lento e há muito trabalho duplicado. Podemos fazer melhor, muito melhor.

A primeira constatação ao otimizar a localização do início da coluna é que geralmente há um número baixo de colunas. Eu escolhi 16 como um número arbitrário de colunas para armazenar em cache.

Com esse primeiro nível de cache, se eu estiver lendo uma coluna nas primeiras 16 colunas, tento ler o ponteiro armazenado em cache anteriormente para essa coluna. Se não for nulo, já tenho o valor. As linhas são imutáveis, portanto, o ponteiro deve ser válido e o processo está concluído!

Se o ponteiro for nulo, posso iterar em meu cache para trás a partir do índice da 16ª coluna até encontrar uma coluna armazenada em cache anteriormente ou chegar à primeira entrada.

Onde quer que eu pare, posso percorrer a linha de maneira ingênua, um caractere por vez. Sempre que encontro uma vírgula, armazeno o ponteiro no início dessa coluna em meu cache para que as consultas subsequentes possam ir direto para lá.

Isso significa que o acesso aleatório às primeiras 16 colunas deve ser basicamente gratuito, pois se torna uma pesquisa de ponteiro direto. Isso exclui o primeiro acesso, que é O(n) .

E as linhas com mais de 16 colunas? Eu já sei onde fica a 15ª coluna (começando de 0), então posso pular direto para a 15ª coluna e depois interagir da maneira ingênua depois disso. Se eu não souber onde está a 15ª coluna, posso calculá-la rapidamente e armazená-la em cache.

Isso é muito bom, exceto que há mais uma otimização que pode ser feita. A outra constatação é que dentro do ParseRowInstruction enquanto ele está construindo a linha de saída, ele acessa as colunas em ordem. Além do cache aleatório de tamanho fixo para as primeiras 16 colunas, podemos manter um ponteiro adicional que armazena o início da última coluna acessada e o índice dessa coluna. Isso permite uma consulta de ponteiro direto para acessos sequenciais para qualquer número de colunas, sem ter que armazenar um número infinito de ponteiros, como no primeiro nível de cache. Claro, essas duas camadas de cache funcionam juntas. À medida que atualizamos os primeiros 16 valores, também atualizamos o last_accessedponteiro.

Ao executar na GPU, cada thread é responsável por uma única linha. Portanto, cada thread possui seu próprio cache multicamadas, conforme descrito. O cache também rastreia qual linha estamos armazenando em cache. Se for diferente do solicitado, redefinimos o cache, para sabermos que o cache é sempre relevante. É possível expandir isso para cobrir casos de uso de leitura de várias linhas ou compartilhamento de cache entre threads, mas isso estava além do escopo da implementação inicial.

Instrução de projeção

O ProjectionInstructioné muito simples em comparação. É fornecida uma lista de índices de coluna a serem buscados. Ele cria um novo objeto TempRow e copia essas colunas do último TempRow, atualizando os metadados no novo objeto TempRow.

Instrução de filtro

A implementação básica do FilterInstructioné projetada para avaliar alguma linha em relação a alguma expressão que retorna trueou false.

Isso foi implementado como uma máquina virtual baseada em pilha. A alocação da pilha é fixada em tempo de compilação e, portanto, sempre aloca seu tamanho máximo.

A pilha foi um tanto interessante de implementar. Optei por projetar o bytecode para a VM para incluir os tipos, bem como as instruções para converter um tipo para outro. A implementação da pilha permite dados heterogêneos, mas o chamador é responsável por fornecer os tipos.

Em uma pilha normal, você pode criar caixas para um objeto, e a caixa armazenará o tipo da coisa, bem como um ponteiro para a coisa. Neste caso, o compilador (ainda não implementado) é responsável por escrever o bytecode para incluir todo o casting necessário. Isso permite que o tempo de execução empurre um inteiro para a pilha, que é xbytes, e mais tarde, quando for ler um inteiro, ele pode xremover bytes da pilha e obter o mesmo inteiro. Não são necessárias caixas ou transmissão dinâmica. Isso coloca o ônus no compilador para obter todos os tipos corretos, mas isso é deixado para implementação futura.

Instrução de Saída

O OutputInstructioné usado para combinar todos os dados dos encadeamentos individuais dentro do ThreadGroup e remover todos os dados duplicados que cada encadeamento individual precisa, mas que só precisam ser copiados uma vez para a CPU e colocá-los com eficiência em um grande buffer .

O primeiro passo é cada linha (cada thread) calcular seu próprio tamanho. Em seguida, executamos uma soma de prefixos dos tamanhos. Isso nos dá um índice onde sabemos que podemos começar a escrever nossos dados.

A soma do prefixo é um algoritmo frequentemente usado na computação da GPU, onde, dado um array de inteiros, retorna um novo array onde para cada índice i, contém a soma de todos os itens menores que i . Se a soma incluir o item i para a posição i , ela é chamada de soma inclusiva, caso contrário, é chamada de soma exclusiva. Usei uma quantia exclusiva para minha implementação.

Antes de podermos começar a escrever dados, os threads devem coordenar a escrita do cabeçalho do arquivo OutputRow. Para fazer isso, a primeira linha, responsável por escrever o cabeçalho, também adiciona o tamanho do cabeçalho ao seu próprio tamanho. Depois de fazermos a soma do prefixo, também executamos uma redução nos tamanhos das linhas para que a primeira thread possa gravar o número total de bytes no cabeçalho.

Uma vez concluído, cada linha pode pular para seu deslocamento da saída da soma do prefixo e copiar seus bytes no buffer começando naquele ponto em paralelo, e temos a garantia de que não haverá colisões.

TempRow

A TempRowé a estrutura de dados que é transmitida enquanto os dados estão sendo processados ​​no Metal. Idealmente, alocaríamos um redimensionável TempRowno heap, para minimizar o consumo de memória, mas porque o Metal não oferece suporte a alocações dinâmicas de memória. Cada TempRowé um buffer de tamanho fixo. Eu escolhi 1024 bytes ou 1 kilobyte. A primeira seção do TempRowé um cabeçalho, seguido pelos dados.

O primeiro valor no cabeçalho é seu comprimento. Isso é importante porque os dados começam imediatamente após o cabeçalho, e o cabeçalho tem um tamanho variável dependendo do número de colunas e seus tipos.

O próximo byte é o número de colunas. Como este é apenas 1 byte, o número máximo de colunas é, portanto, 256. Acho que isso é suficiente para a maioria dos casos de uso.

Os próximos N bytes são os tipos de coluna. As colunas podem ser uma das seguintes: , Integerou seus equivalentes anuláveis. Um valor booleano é simplesmente expresso como um número inteiro.FloatString

Um número inteiro e um float são sempre de tamanho constante, portanto não precisamos armazenar seu tamanho no cabeçalho, a menos que seja uma coluna anulável. Por outro lado, uma string pode ter qualquer número de caracteres. Portanto, armazenamos o tamanho de todas as colunas de comprimento variável (strings e colunas opcionais) nos bytes subsequentes. Novamente, como o tamanho de uma coluna é de apenas 1 byte, o comprimento máximo de uma string é de 256 caracteres.

Após o cabeçalho, todos os dados das colunas são anexados um após o outro.

Para tornar a construção TempRowmais simples, existe uma classe auxiliar TempRowBuilderonde o chamador pode escrever todos os tipos e tamanhos de coluna, etc. em arrays separados. O TempRowpode então ser construído trivialmente a partir do construtor copiando os valores.

Os dados das colunas podem ser anexados em ordem. Existem métodos auxiliares para ajudar na cópia de strings, inteiros e flutuantes e na gravação deles byte por byte.

Quando o próximo método vai ler o TempRow, existem métodos auxiliares que leem do cabeçalho para determinar os índices inicial e final no buffer dessa coluna e convertem os bytes de volta no tipo apropriado. O chamador é responsável por consultar o ColumnTypeda coluna em que está interessado, antes de lê-lo como aquele tipo.

Como o TempRowlê todos os dados diretamente de um buffer de tamanho fixo, ele pode ser adaptado trivialmente a uma constexprclasse para outros aplicativos.

OutputRow

O OutputRowé criado pelo OutputRowInstruction(descrito acima) e serve para mover várias linhas que compartilham o mesmo esquema. Seria um desperdício copiar todos os TempRowobjetos individuais diretamente porque cada linha tem o mesmo esquema, então há muitos metadados duplicados. Em vez disso, copiamos todos os dados em uma estrutura singular de forma que possamos copiá-los em TempRowobjetos separados, se necessário posteriormente, ou dividi-los em dois ou mais OutputRowobjetos, se necessário.

Semelhante ao TempRow, o OutputRowtem uma definição de cabeçalho, embora seja um pouco diferente do TempRow. O primeiro valor, conforme explicado anteriormente, é o tamanho do cabeçalho, mas esse valor é maior, com 2 bytes alocados em vez de 1. O próximo valor é o número de bytes no OutputRow, e esse é um inteiro sem sinal de 32 bits. Depois disso é o número de colunas, e este é apenas um único byte. Seguido pelos tipos de coluna, semelhantes ao arquivo TempRow.

Após o cabeçalho, todos os dados são anexados. Como o OutputRowé sempre construído a partir de um ou mais TempRowou de outro OutputRow, podemos calcular o tamanho dos dados de cada linha em paralelo usando o algoritmo de soma de prefixos e gravar no buffer de dados em paralelo.

Ao executar no Metal, o OutputRowé alocado estaticamente para ter um tamanho fixo de 1.000.000 bytes. Na CPU, podemos ser mais eficientes e usar a std::vectorpara alocar apenas a quantidade de espaço que precisamos.

Para facilitar melhor cada thread lendo e escrevendo OutputRowem paralelo, em vez de os tamanhos das colunas de tamanho variável serem escritos no cabeçalho como estão no TempRow, eles são anexados aos dados dessa coluna por linha. Assim, por exemplo, uma linha com 2 inteiros seguidos por uma string de 3 caracteres “abc”, teria o formato: <integer><integer>3abc. O leitor do OutputRow(atualmente implementado apenas na CPU) sabe que a coluna é uma string e pode, portanto, pular para o início da string para ler seu conteúdo. Os tamanhos de cada linha não são gravados noOutputRow. Em vez disso, o leitor percorre o buffer e registra o início de cada linha e os tamanhos de cada coluna de tamanho variável para cada linha. Isso foi feito para economizar espaço, mas pode ser otimizado para ser escrito no cabeçalho ou por linha, de modo que a leitura OutputRowseja mais eficiente e, portanto, mais rápida. Os detalhes de leitura, divisão e mesclagem OutputRowde objetos na CPU foram brevemente discutidos anteriormente na seção sobre o Scheduler.

Trabalho futuro

Trabalhei neste projeto como um experimento para ver se era possível. Há muitas coisas que eu gostaria de implementar, se fosse deixá-lo pronto para produção ou apenas passar mais tempo no protótipo do que dediquei.

aquele bug

O primeiro problema que eu adoraria resolver é (o que acredito ser um bug no Xcode 13), onde vários threads estão sendo atribuídos ao thread 0 em um ThreadGroup. Avise-me se você tiver algumas idéias. Isso faz com que vários threads tentem gravar o cabeçalho. Isso faz com que o cabeçalho seja parcialmente compactado com dados, dependendo da ordem dos encadeamentos. Tentei pesquisar no Google sobre isso, mas não consegui encontrar nenhuma fonte que fosse particularmente útil. Acho que tinha a ver com a quantidade de memória que estava tentando alocar para cada thread. Infelizmente, a documentação oficial da Apple não diz nada sobre isso que eu possa encontrar.

Mecanismo de consulta + analisador

A próxima grande tarefa é implementar um analisador e um mecanismo de consulta para que o banco de dados possa aceitar consultas semelhantes a SQL e transformá-las em planos de consulta e executá-los. Essa tarefa também envolve a implementação de uma API DataFrame ou a gravação em vários formatos no disco, para ser consumida por outras bibliotecas e programas.

Juntar + Agrupar por

Expandindo a especificação SQL, seria divertido poder calcular uma junção e uma cláusula Group By. Achei que a maneira ingênua de implementar uma junção é calcular cada linha bruta na GPU em paralelo e, em seguida, fazer uma junção de hash na CPU, uma vez por bloco. No entanto, pode ser mais eficiente descobrir uma maneira de enviar um bloco de 2 tabelas diferentes que você deseja unir ao mesmo tempo e fazer com que a GPU retorne as linhas unidas.

Para o Group By, você pode fazer isso na CPU ou talvez fazer uma agregação parcial na GPU. Ou você pode fazer alguma combinação em que faz o processamento bruto inicial na GPU e, em seguida, executa um kernel diferente, onde, dado um conjunto de linhas, calcula o grupo para cada linha dentro do conjunto. Isso permitiria agrupar linhas rapidamente na CPU, onde você poderia alocar mais dados para manter as linhas, aproveitando a natureza paralela da GPU para calcular grupos em paralelo.

Sistema distribuído

Se esse sistema for usado na produção, provavelmente precisará tirar proveito de várias máquinas. Eu poderia imaginar uma rede heterogênea de dispositivos conectados da Apple (e não Apple) trabalhando juntos. Imagine um iPhone como o controlador host enviando comandos para as outras máquinas e um grupo de iPads que processam os dados que possuem localmente e enviam linhas processadas de volta ao controlador central. Como alternativa, talvez você tenha uma implantação na nuvem executando o mesmo código na CPU em uma instância lambda da AWS ou em várias GPUs com um servidor Mac Pro no local. Todos esses sistemas podem funcionar juntos para fornecer acesso responsivo muito rápido a conjuntos de dados muito grandes com dispositivos que (eu sinto) têm muito poder de processamento inexplorado ainda disponível.

Reduza a pegada de memória

Como outra otimização, especialmente porque quero que isso seja executado em qualquer dispositivo que execute o Metal, seria bom manter o consumo de memória o menor possível, para que possamos maximizar os recursos no dispositivo para o aplicativo do usuário final que está sendo executado . Idealmente, devemos ser capazes de ler um pedaço de um arquivo do disco para a memória, transformá-lo em um buffer para enviá-lo à GPU e liberar esse pedaço de memória. Tentei projetar o sistema dessa maneira usando shared_ptr, de modo que eu tivesse um sistema de alocação de memória de contagem de referência para buffers. No entanto, descobri na prática que, como a biblioteca de tarefas que eu estava usando não sabia se precisava executar novamente o gráfico de tarefas com várias entradas, a biblioteca não liberou o lambda capturando a referência ao buffer à medida que avançava. Isso significa que oshared_ptrque foi capturado pelo lambda ainda é referenciado e, portanto, não libera sua memória até que o grafo da tarefa seja destruído, o que só acontece quando todo o grafo termina de ser executado.

Conclusão

No geral, eu me diverti muito trabalhando e pensando sobre este projeto. Foi muito diferente de muitos dos outros projetos que fiz. Espero que tenha gostado de ler este artigo. Minha implementação completa está vinculada no início deste artigo. Se você tiver algum comentário ou ideia de coisas que gostou ou faria diferente, sinta-se à vontade para entrar em contato comigo. Obrigado!