Descripción general

Hace unos meses comencé a trabajar en un prototipo de base de datos relacional en Metal. Apple acababa de lanzar M1 Max y M1 Ultra unos meses antes con hasta 128 GB de memoria unificada (en Mac Studio).

Vi esto como una oportunidad para hacer algo con un procesamiento muy pesado que requería mucha memoria GPU: procesar tablas relacionales grandes en una GPU.

No fui el primero en pensar en escribir una base de datos relacional en una GPU. Bases de datos como BlazingSQL , una base de datos relacional de GPU basada en Rapids.AI . Rapids.AI es una biblioteca de Python de NVIDIA que refleja la funcionalidad de muchas bibliotecas populares de Python, como Pandas, pero ejecuta las funciones equivalentes en la GPU. NVIDIA ha estado invirtiendo mucho en el centro de datos y ha ayudado a desarrollar más herramientas que se ejecutan en sus tarjetas, especialmente para el aprendizaje automático y el procesamiento de grandes datos.

Al ver las conferencias de Apple últimamente, he sentido que hay mucho rendimiento potencial que realmente no se está utilizando. Por lo que he visto, los desarrolladores están aprovechando las nuevas capacidades gráficas de los nuevos chips. En el lado de la computación, faltaban las demostraciones y el software de código abierto construido con Metal. Apple hizo un proyecto de muestra de una simulación de partículas, presumo para mostrar el equivalente de la muestra CUDA. Muestran cómo puede usar la computación en CUDA y la representación en OpenGL en la GPU sin tener que volver a la CPU en el medio. El otro lugar en el que Apple ha estado usando mucho la GPU es para tareas de IA. Siempre que Neural Engine no admita una operación en un modelo, CoreML recurrirá automáticamente a la GPU para obtener más rendimiento. Si bien esto es muy útil y fascinante,

Elegí una base de datos relacional porque me encantan las bases de datos y he pensado en una serie de diseños para ellas, algunos de los cuales he creado prototipos a lo largo de los años. Las bases de datos relacionales también son interesantes ya que utilizan cadenas y valores nulos. Tanto el ejemplo de IA como el simulador de partículas, aunque son muy impresionantes, solo usan números flotantes y enteros.

La implementación que construí se puede encontrar aquí: MetalDB Github

Ideas de diseño

No recuerdo si fue justo al principio o en algún punto a la mitad del proceso, sin embargo, me inspiré en la documentación de BigQuery Query Plans que hablaba sobre un gráfico de etapas de consulta que conforman un plan de ejecución de consulta.

Una de las principales limitaciones de diseño con Metal es que toda la memoria debe tener un tamaño estático en el momento de la compilación. Esto presentaba desafíos porque no podía copiar una cadena porque no sabía cuántas cadenas había en una fila de la base de datos, o cuánto duraría cada cadena en el momento de la compilación.

Pensé que usar un algoritmo de suma de prefijos para copiar todos los datos de la GPU a la CPU de manera eficiente sería más simple si cada hilo procesara una fila. También necesitaba usar el bloque sincronizable más grande disponible, que en Metal es un ThreadGroup.

En parte como una optimización y en parte como un desafío personal, quería maximizar la cantidad de trabajo realizado en la GPU. Por esos motivos, opté por comenzar con la lectura de archivos CSV en la CPU y hacer el análisis de CSV en la GPU.

Durante la implementación, también quería poder probar la base de datos en la CPU para que las pruebas unitarias pudieran realizarse paso a paso en un depurador. Por esta razón, configuro la canalización de compilación para que todos mis kernels de Metal estén escritos como encabezados. Como resultado, pude incluirlos en los archivos del kernel de Metal, pero también incluirlos en las pruebas en C++. Este diseño también me permitiría definir constantes y tipos en los encabezados de Metal y garantizar que siempre fueran los mismos en el código C++ que lo llamaría.

Antecedentes sobre Threadgroups y conceptos de metal

Como base para ideas y explicaciones adicionales, la ejecución de Metal está organizada en cuadrículas. Una cuadrícula es un grupo 1D, 2D o 3D de ThreadGroups. Un ThreadGroup es un grupo sincronizable dentro de esa cuadrícula. Los subprocesos dentro de un ThreadGroup se dividen y ejecutan en grupos adicionales, llamados deformaciones.

Un subproceso es el bloque más básico en la programación de GPU y se traduce aproximadamente en el modelo de un subproceso en un núcleo de CPU. Es una ejecución única, lineal y en orden de instrucciones. El subproceso tiene registros a los que puede acceder directamente, así como leer y escribir en la memoria compartida. Es un modelo de memoria diferente al de la CPU, pero eso está más allá del alcance de este artículo.

Un warp (llamado SIMD en la documentación de Metal) suele ser un grupo de 16 o 32 hilos. La misma instrucción debe ejecutarse al mismo tiempo en todos los subprocesos en un warp, aunque potencialmente en diferentes datos (SIMD, instrucción única, datos múltiples). Si algunos de los subprocesos toman una ruta diferente en el código, todos los subprocesos dentro de esa deformación deben esperar a que todas las ramas se ejecuten en serie. Esto lleva a diseñar el código GPU con la menor cantidad de ramas posible, de modo que mantenga ocupados todos los subprocesos dentro de una deformación tanto como sea posible.

Otros sistemas como CUDA y OpenCL tienen conceptos similares, solo que con nombres diferentes.

Implementación

Enlace a la implementación:https://github.com/mattpaletta/metaldb

En mi opinión, creo que tiene más sentido hablar de la implementación en el orden del flujo de datos a través del sistema. Sin embargo, esto es casi el inverso perfecto de cómo lo implementé.

Binario

El resultado final que se produce es muy sencillo. Es un binario llamado metaldby solo tiene una función principal en él. Hice la aplicación muy liviana para que yo, al igual que otros, pudiéramos reutilizar las bibliotecas internas fácilmente como parte de otras bibliotecas y aplicaciones en el futuro.

Motor

El motor es donde se coordina la mayor parte de la lógica del sistema. El Motor interactúa con el QueryPlanner, que está implementado en la biblioteca QueryPlanner, así como con el Scheduler, que se encarga de ejecutar y coordinar la ejecución del plan de consulta generado.

Analizador de consultas

Query Parser es el componente responsable de convertir una consulta similar a SQL en un AST que el resto del sistema puede analizar más fácilmente .

Esta primera versión de la base de datos no implementa un analizador de consultas. En cambio, he codificado el AST para varias consultas que quiero probar. Escribir un analizador y producir un AST, aunque suena muy interesante, es algo que hice en otro proyecto y no fue el enfoque de este proyecto.

Tampoco tenía la intención de que este proyecto fuera una base de datos lista para producción. Por lo tanto, no necesita un analizador de consultas en este momento, pero todos los stubs están ahí para que los implemente en un momento posterior si así lo decido.

Además de que el sistema acepte cadenas de consulta, planeo implementar eventualmente una API de Dataframe, similar a Pandas, pero en C++. Desde mi punto de vista, este tipo de API sería más fácil de usar para otras bibliotecas. Esto también ahorra el paso de que la otra biblioteca tenga que producir una cadena de consulta solo para que el analizador la vuelva a analizar inmediatamente. Esta API de marco de datos también se deja como trabajo futuro.

Como conjunto de datos de prueba, primero utilicé el conjunto de datos Iris disponible públicamente . Elegí este conjunto de datos porque es relativamente pequeño, en formato CSV y en su mayoría números, sin valores nulos.

Después de que puse en funcionamiento ese conjunto de datos, quise probar un conjunto de datos mucho más grande con varios archivos. Para ello utilicé el New York Taxi Dataset . Este conjunto de datos más grande demostró algunos desafíos interesantes que no esperaba, más sobre esto más adelante.

Planificador de consultas

Después de que Query Parser haya generado el AST, el siguiente componente es Query Planner. Este es el responsable de convertir el AST en un plan de ejecución optimizado.

El primer paso para hacer un plan de ejecución optimizado es hacer un plan. Inspirándome en la referencia de BigQuery , me gustó la idea de dividir un plan de ejecución en un gráfico de "Etapas". En BigQuery, cada etapa se compone de uno o más pasos. Cada paso puede ser una lectura o una escritura, un agregado o una unión, etc. No quería bajar a la granularidad de los pasos, pero tengo un concepto similar, lo llamo "parcial".

Para pasar de un AST a un gráfico de etapas, primero enumero los archivos en el disco para la(s) tabla(s). Luego voy a las hojas del AST y para cada una de ellas produzco una nueva etapa que leerá ese archivo.

Mientras vuelvo a subir por el árbol, decido si crearé un nuevo parcial como parte de la etapa existente o crearé una nueva etapa. El punto clave es cuando tengo que pasar de la GPU a la CPU o viceversa para un paso, creo una nueva etapa. Esto significa que se puede procesar la mayor cantidad de datos en la GPU mientras se minimizan los tiempos de transferencia entre la CPU y la GPU. Esto es especialmente relevante para dispositivos que no tienen memoria unificada.

Cada etapa tiene una lista singular de parciales para ejecutar. Más tarde, estos se traducirán como instrucciones para la GPU dentro de esa etapa, ya que exploraremos más en la sección sobre el programador.

Cada vez que creo una nueva etapa, inserto una "instrucción aleatoria", que le dice a la GPU que copie la información a la CPU.

En el futuro, también escribiría un optimizador que pudiera reescribir consultas para minimizar la cantidad de datos leídos de cada archivo y copiados nuevamente a la CPU después de leerlos.

programador

El programador es responsable de la ejecución paralela de la consulta. Tuve la tentación de escribir mi propia biblioteca de subprocesos múltiples para hacer esto. Terminé escribiendo mi implementación sobre TaskFlow , una biblioteca de gráficos de tareas C++ de código abierto.

En un nivel alto, la creación del gráfico de tareas sigue el gráfico de etapas. Cada etapa es una tarea en el gráfico y depende de sus hijos.

Dentro de una etapa, cada parcial, la lista de pasos a realizar en la CPU o la GPU, se expanden en orden. A medida que se registra cada parcial, tiene varias tareas dentro del gráfico de tareas a las que puede conectarse.

La tarea principal a la que se puede enganchar es la tarea de codificación de la tarea anterior. El parcial debe crear una nueva tarea que dependa de la tarea de codificación parcial principal. Utiliza el codificador pasado para codificarse a sí mismo en una representación serializada que se puede enviar a la GPU. Para la mayoría de las tareas, esto es todo lo que se necesita y la implementación del parcial está en la GPU en Metal.

La otra tarea que está disponible es la tarea de trabajo. Esto existe en caso de que un parcial quiera anular algo sobre cómo se ejecuta el trabajo para ese parcial en lugar del comportamiento predeterminado.

La mayoría de las tareas leen los búferes de una o más etapas secundarias y escriben en su búfer de salida. La instrucción de lectura es única porque tiene que leer desde el disco, no desde los búfer secundarios.

La instrucción de lectura establece una cadena de tareas que leen el archivo CSV (el único tipo de archivo implementado actualmente) que se le ha asignado y lo lee en un búfer. Mientras lee en un búfer, realiza un seguimiento del desplazamiento de la fila actual y los almacena como parte del RawTableobjeto, que se describe a continuación.

Una vez que se ha leído el archivo, la GPU puede comenzar a procesar las filas. El diseño de la base de datos requiere un hilo por fila. El metal tiene un límite de cuántos subprocesos se pueden asignar por ThreadGroup. Por lo tanto, primero dividimos las filas en varios búferes que se enviarán a la GPU de forma independiente.

TaskFlow permite subtareas dinámicas dentro de una tarea. Cuando obtengo el RawTable, consulto la cantidad de subprocesos que Metal me permite programar y divido las filas originales en partes de ese tamaño.

Luego, cada fragmento se envía a la GPU en paralelo.

Una vez que se han procesado todos los fragmentos, ejecuto una tarea de combinación que copia todos los OutputRowobjetos de la GPU y los combina en un solo gigante OutputRowpara que la siguiente etapa pueda leerlos juntos.

En el futuro, me gustaría optimizar la división de múltiples lotes. Tan pronto como el lote se haya dividido, se puede enviar a la GPU. Tan pronto como ese fragmento regrese, se puede copiar en el búfer final mientras las otras tareas se procesan de forma asíncrona.

Además, me gustaría liberar el original RawTableuna vez que todas las filas se hayan dividido en partes, cada una de las cuales almacena una copia. Además, debería poder liberar el búfer de salida del fragmento tan pronto como se haya copiado en el búfer final, reduciendo la cantidad total de memoria requerida.

Instrucción ParseRow

El ParseRowInstructioncomienza con una premisa simple. Dada una lista de índices para el inicio de cada fila e información sobre el número de filas y los tipos de columnas, analice los valores para una fila en particular, convierta a sus tipos correctos.

El tipo de columna más simple es una cadena. Para la fila N , podemos saltar al principio de esa fila buscando su índice, que la CPU almacenó cuando leímos el archivo del disco. Entonces podemos obtener un puntero a ese índice. Este es el comienzo de la fila. El final de cualquier columna es la posición antes de la siguiente coma (que marca la siguiente columna) cuando avanzamos un carácter a la vez, o uno antes del comienzo de la siguiente fila (si es la última columna de la fila), o uno antes del final del búfer (si es la última columna de la última fila).

La instrucción lee primero cada columna como una cadena. Analiza una columna exactamente como se describe y la lee como una cadena, carácter por carácter. Ahora, para leer la siguiente columna, comenzamos al principio de la fila. Cuando llegamos a la primera coma, la marcamos como el principio y continuamos hasta la coma que sigue. El proceso se repite para las columnas posteriores.

Si tenemos un número entero, pasamos los punteros al principio y al final de la cadena a una stoifunción personalizada. Esto es similar al de la biblioteca estándar de C, que convierte la cadena en una representación entera. Escribí mi propia versión de stoftambién.

Como puede imaginar, leer cada columna desde el principio de la fila cada vez es muy lento y hay mucho trabajo duplicado. Podemos hacerlo mejor, mucho mejor.

La primera constatación al optimizar la búsqueda del comienzo de la columna es que, a menudo, hay un número bajo de columnas. Elegí 16 como un número arbitrario de columnas para almacenar en caché.

Con este primer nivel de caché, si estoy leyendo una columna dentro de las primeras 16 columnas, intento leer el puntero previamente almacenado en caché para esa columna. Si no es nulo, ya tengo el valor. Las filas son inmutables, por lo que el puntero debe ser válido y el proceso ha finalizado.

Si el puntero es nulo, puedo iterar sobre mi caché hacia atrás desde el índice de la columna 16 hasta que encuentre una columna previamente almacenada en caché o llegue a la primera entrada.

Desde donde me detenga, puedo iterar a través de la fila de manera ingenua, un carácter a la vez. Cada vez que encuentro una coma, almaceno el puntero al comienzo de esa columna en mi caché para que las consultas posteriores puedan ir directamente allí.

Esto significa que el acceso aleatorio a las primeras 16 columnas debería ser básicamente gratuito, ya que se convierte en una búsqueda de puntero directo. Esto excluye el primer acceso, que es O(n) .

¿Qué pasa con las filas con más de 16 columnas? Ya sé dónde está la columna 15 (a partir de 0), así que puedo saltar directamente a la columna 15 y luego interactuar de manera ingenua después de eso. Si no sé dónde está la columna 15, puedo calcularla rápidamente y almacenarla en caché.

Esto bastante bien, excepto que hay una optimización más que se puede hacer. La otra realización es que dentro de ParseRowInstruction mientras construye la fila de salida, accede a las columnas en orden. Además del caché aleatorio de tamaño fijo para las primeras 16 columnas, podemos mantener un puntero adicional que almacena el comienzo de la última columna a la que se accede y el índice de esa columna. Esto permite una búsqueda directa de punteros para accesos secuenciales para cualquier número de columnas, sin tener que almacenar un número infinito de punteros, como en el primer nivel de almacenamiento en caché. Por supuesto, estas dos capas de almacenamiento en caché funcionan juntas. A medida que actualizamos los primeros 16 valores, también actualizamos el last_accessedpuntero.

Cuando se ejecuta en la GPU, cada subproceso es responsable de una sola fila. Entonces, cada subproceso tiene su propio caché de múltiples capas como se describe. El caché también realiza un seguimiento de qué fila estamos almacenando en caché. Si es diferente al solicitado, reiniciamos el caché, por lo que sabemos que el caché siempre es relevante. Es posible expandir esto para cubrir casos de uso de lectura de múltiples filas o compartir el caché entre subprocesos, pero esto estaba más allá del alcance de la implementación inicial.

Instrucción de proyección

El ProjectionInstructiones muy simple en comparación. Se le da una lista de índices de columna para buscar. Crea un nuevo objeto TempRow y copia esas columnas del último TempRow, actualizando los metadatos en el nuevo objeto TempRow.

Instrucción de filtro

La implementación básica de FilterInstructionestá diseñada para evaluar alguna fila contra alguna expresión que devuelve trueo false.

Esto se implementó como una máquina virtual basada en pila. La asignación de la pila se fija en tiempo de compilación y, por lo tanto, siempre asigna su tamaño máximo.

La pila fue algo interesante de implementar. Opté por diseñar el código de bytes para que la máquina virtual incluyera los tipos, así como las instrucciones para convertir un tipo en otro. La implementación de la pila permite datos heterogéneos, pero la persona que llama es responsable de proporcionar los tipos.

En una pila normal, puede crear cuadros para un objeto, y el cuadro almacenará de qué tipo es la cosa, así como un puntero a la cosa. En este caso, el compilador (aún no implementado) es responsable de escribir el código de bytes para incluir todo el casting necesario. Esto permite que el tiempo de ejecución inserte un número entero en la pila, que son xbytes, y luego, cuando va a leer un número entero, puede xextraer bytes de la pila y obtener el mismo número entero. No se requieren cajas ni casting dinámico. Esto hace que el compilador tenga la responsabilidad de obtener todos los tipos correctos, pero eso se deja para futuras implementaciones.

Instrucción de salida

se utiliza para combinar todos los OutputInstructiondatos de los subprocesos individuales dentro de ThreadGroup y eliminar todos los datos duplicados que necesita cada subproceso individual, pero que en realidad solo necesita copiarse una vez en la CPU y colocarse de manera eficiente en un gran búfer .

El primer paso es que cada fila (cada subproceso) calcula su propio tamaño. Luego ejecutamos una suma de prefijos de los tamaños. Esto nos da un índice donde sabemos que podemos comenzar a escribir nuestros datos.

La suma de prefijos es un algoritmo que se usa a menudo en el cálculo de GPU donde, dada una matriz de números enteros, devuelve una nueva matriz donde, para cada índice i, contiene la suma de todos los elementos menores que i . Si la suma incluye el elemento i para la posición i , se denomina suma inclusiva; de lo contrario, se denomina suma exclusiva. Usé una suma exclusiva para mi implementación.

Antes de que podamos comenzar a escribir datos, los subprocesos deben coordinarse para escribir el encabezado del archivo OutputRow. Para ello, la primera fila, encargada de escribir la cabecera, añade también el tamaño de la cabecera a su propio tamaño. Después de hacer la suma de prefijos, también ejecutamos una reducción en los tamaños de fila para que el primer subproceso pueda escribir el número total de bytes en el encabezado.

Una vez que se completa, cada fila puede saltar a su desplazamiento desde la salida de la suma de prefijos y copiar sus bytes en el búfer comenzando en ese punto en paralelo, y tenemos la garantía de que no habrá colisiones.

fila temporal

La TempRowes la estructura de datos que se transmite mientras los datos se procesan en Metal. Idealmente, asignaríamos un tamaño variable TempRowen el montón, para minimizar el uso de memoria, pero porque Metal no admite asignaciones de memoria dinámica. Cada TempRowes un búfer de un tamaño fijo. Lo he elegido para que sea de 1024 bytes o 1 kilobyte. La primera sección del TempRowes un encabezado, seguida de los datos.

El primer valor en el encabezado es su longitud. Esto es importante porque los datos comienzan inmediatamente después del encabezado, y el encabezado tiene un tamaño variable según la cantidad de columnas y sus tipos.

El siguiente byte es el número de columnas. Dado que esto es solo 1 byte, el número máximo de columnas es 256. Creo que esto es suficiente para la mayoría de los casos de uso.

Los siguientes N bytes son los tipos de columna. Las columnas pueden ser una de: , Integero sus equivalentes anulables. Un valor booleano se expresa simplemente como un número entero.FloatString

Un entero y un flotante siempre tienen un tamaño constante, por lo que no tenemos que almacenar su tamaño en el encabezado, a menos que sea una columna anulable. Por el contrario, una cadena puede tener cualquier número de caracteres. Por lo tanto, almacenamos el tamaño de todas las columnas de longitud variable (cadenas y columnas opcionales) en los bytes siguientes. Nuevamente, dado que el tamaño de una columna es de solo 1 byte, la longitud máxima de una cadena es de 256 caracteres.

Después del encabezado, todos los datos de las columnas se agregan uno tras otro.

Para simplificar la construcción de TempRow, hay una clase de ayuda TempRowBuilderdonde la persona que llama puede escribir todos los tipos y tamaños de columna, etc. en matrices separadas. TempRowLuego, se puede construir de forma trivial a partir del constructor copiando los valores .

Los datos de las columnas se pueden agregar en orden. Existen métodos de ayuda para ayudar a copiar cadenas, enteros y flotantes, y escribirlos byte por byte.

Cuando el siguiente método va a leer el TempRow, hay métodos auxiliares que leen el encabezado para determinar los índices de inicio y finalización en el búfer para esa columna y convertir los bytes de nuevo en el tipo apropiado. La persona que llama es responsable de consultar el ColumnTypede la columna que le interesa, antes de leerlo como ese tipo.

Debido a que TempRowlee todos los datos directamente desde un búfer de tamaño fijo, podría adaptarse de manera trivial a una constexprclase para otras aplicaciones.

fila de salida

El OutputRowes creado por OutputRowInstruction(descrito anteriormente) y tiene el propósito de mover varias filas que comparten el mismo esquema. Sería un desperdicio copiar todos los TempRowobjetos individuales directamente porque cada fila tiene el mismo esquema, por lo que hay muchos metadatos duplicados. En su lugar, copiamos todos los datos en una estructura singular de modo que podamos copiarlos en TempRowobjetos separados si es necesario más adelante, o dividirlos en dos o más OutputRowobjetos si es necesario.

Similar a TempRow, OutputRowtiene una definición de encabezado, aunque es ligeramente diferente de TempRow. El primer valor, como se explicó anteriormente, es el tamaño del encabezado, pero este valor es más grande, con 2 bytes asignados en lugar de 1. El siguiente valor es la cantidad de bytes en el OutputRow, y este es un entero sin signo de 32 bits. Después de esto está el número de columnas, y esto es solo un byte. Seguido de los tipos de columna, similar al TempRow.

Después del encabezado, se agregan todos los datos. Dado OutputRowque siempre se construye a partir de uno o más TempRowo de otro OutputRow, podemos calcular el tamaño de los datos de cada fila en paralelo utilizando el algoritmo de suma de prefijos y escribir en el búfer de datos en paralelo.

Cuando se ejecuta en Metal, OutputRowse asigna estáticamente para tener un tamaño fijo de 1.000.000 de bytes. En la CPU, podemos ser más eficientes y usar a std::vectorpara asignar solo la cantidad de espacio que necesitamos.

Para facilitar mejor que cada subproceso lea y escriba OutputRowen paralelo, en lugar de que los tamaños de las columnas de tamaño variable se escriban en el encabezado como lo están en el TempRow, se anteponen a los datos de esa columna por fila. Entonces, por ejemplo, una fila con 2 números enteros seguidos de una cadena de 3 caracteres “abc”, tendría el formato: <integer><integer>3abc. El lector de OutputRow(actualmente solo implementado en la CPU) sabe que la columna es una cadena y, por lo tanto, puede saltar al principio de la cadena para leer su contenido. Los tamaños de cada fila no se escriben en elOutputRow. En su lugar, el lector itera a través del búfer y registra el inicio de cada fila y los tamaños de cada columna de tamaño variable para cada fila. Esto se hizo para ahorrar espacio, pero podría optimizarse para escribirse en el encabezado o por fila, de modo que la lectura OutputRowsea más eficiente y, por lo tanto, más rápida. Los detalles de lectura, división y combinación OutputRowde objetos en la CPU se discutieron brevemente anteriormente en la sección sobre Scheduler.

Trabajo futuro

Trabajé en este proyecto como un experimento para ver si era posible. Hay muchas cosas que me hubiera gustado implementar, si iba a dejarlo listo para la producción, o incluso dedicar más tiempo al prototipo del que tengo.

ese error

El primer problema que me encantaría resolver es (lo que creo que es un error en Xcode 13), donde a varios subprocesos se les asigna el subproceso 0 dentro de un ThreadGroup. Avísame si tienes alguna idea. Esto hace que varios subprocesos intenten escribir el encabezado. Esto da como resultado que el encabezado se aplaste parcialmente con datos, según el orden de los subprocesos. Traté de buscar en Google al respecto, pero no pude encontrar ninguna fuente que fuera particularmente útil. Creo que tenía que ver con la cantidad de memoria que intentaba asignar a cada subproceso. Desafortunadamente, la documentación oficial de Apple no dice nada sobre eso que pude encontrar.

Motor de consultas + analizador

La próxima gran tarea es implementar un analizador y un motor de consulta para que la base de datos pueda aceptar consultas similares a SQL y convertirlas en planes de consulta y ejecutarlos. Esta tarea también implica implementar una API de DataFrame, o escribir en múltiples formatos en el disco, para ser consumidos por otras bibliotecas y programas.

Unirse + Agrupar por

Ampliando la especificación SQL, sería divertido poder calcular una unión y una cláusula Group By. Pensé que la forma ingenua de implementar una combinación es calcular cada fila sin procesar en la GPU en paralelo y luego hacer una combinación hash en la CPU, una vez por fragmento. Sin embargo, puede ser más eficiente encontrar una forma de enviar un fragmento de 2 tablas diferentes que desea unir al mismo tiempo y hacer que la GPU devuelva las filas unidas.

Para el Agrupar por, puede hacerlo en la CPU o quizás haciendo una agregación parcial en la GPU. O podría hacer alguna combinación en la que realice el procesamiento sin procesar inicial en la GPU y luego ejecute un kernel diferente donde, dado un conjunto de filas, calcule el grupo para cada fila dentro del conjunto. Esto le permitiría acumular rápidamente filas en la CPU donde podría asignar más datos para mantener las filas, mientras aprovecha la naturaleza paralela de la GPU para calcular grupos en paralelo.

Sistema distribuido

Si este sistema se va a utilizar en la producción, es probable que deba poder aprovechar varias máquinas. Podría imaginar una red heterogénea de dispositivos conectados de Apple (y no Apple) trabajando juntos. Imagine un iPhone como el controlador de host que envía comandos a las otras máquinas, y un grupo de iPads que procesan los datos que tienen localmente y envían las filas procesadas al controlador central. Alternativamente, tal vez tenga una implementación en la nube que ejecute el mismo código en la CPU en una instancia de AWS lambda, o en varias GPU con un servidor Mac Pro en las instalaciones. Todos estos sistemas podrían funcionar juntos para brindarle un acceso de respuesta muy rápido a conjuntos de datos muy grandes con dispositivos que (creo) tienen todavía disponible una gran cantidad de potencia de procesamiento sin explotar.

Reducir la huella de memoria

Como otra optimización, especialmente porque quiero que esto se ejecute en cualquier dispositivo que ejecute Metal, sería bueno mantener la huella de memoria lo más pequeña posible para que podamos maximizar los recursos en el dispositivo para la aplicación del usuario final que se está ejecutando. . Idealmente, deberíamos poder leer una parte de un archivo del disco a la memoria, convertirlo en un búfer para enviarlo a la GPU y luego liberar esa parte de la memoria. Traté de diseñar el sistema de esa manera usando shared_ptr, de modo que tuviera un sistema de asignación de memoria de conteo de referencias para los búferes. Sin embargo, descubrí en la práctica que, dado que la biblioteca de tareas que estaba usando no sabía si necesitaba volver a ejecutar el gráfico de tareas con múltiples entradas, la biblioteca no liberó la lambda capturando la referencia al búfer a medida que avanzaba. Esto significa que elshared_ptrtodavía se hace referencia a lo que capturó la lambda y, por lo tanto, no libera su memoria hasta que se destruye el gráfico de tareas, lo que solo sucede cuando el gráfico completo termina de ejecutarse.

Conclusión

En general, me divertí mucho trabajando y pensando en este proyecto. Fue muy diferente de muchos de los otros proyectos que he hecho. Espero que hayas disfrutado leyendo este artículo. Mi implementación completa está vinculada en la parte superior de este artículo. Si tiene algún comentario o idea de cosas que le gustaron o que haría de otra manera, no dude en ponerse en contacto conmigo. ¡Gracias!