Generación del cubo de datos empleando paralelismo de GPUs y CPUs multinúcleo

In his M. Sc. Thesis, Mario Torres uses a combination of GPU and CPU processors in a computer, to calculate the full data cube.The data cube consists of all the cuboids (projections or summaries of a large multivariate dataset), in a way that facilitates Data Mining. His thesis (in Spanish) is here.

Effi cient data cube computing is a core problem in data warehousing and online analitical processing fields. This is a process that may involve very large amount of tuple group summarization over big data. For a given relation R with n dimensions and a measure attribute M, R(A1; A2; :::; An; M), the basic data cube generation problem involves the aggregation of R for the construction of 2**n tuple groups on every possible combination of the n dimensions (i.e., the power set of the n dimensions of R), each of these groups is called a cuboid. This problem has been researched extensively; however, most of algorithms have been proposed without considering the advantages of the modern CPU and GPU architectures.

This work presents the design and implementation of a set of parallel operations called primitives, which take advantage of the modern GPU and multicore CPU parallelism. Primitives help to generate data cubes by using routines such as sort, partition, and aggregate. The GPU software was implemented using CUDA, a parallel computing platform introduced by the graphics processor manufacturer NVIDIA. On the other hand, multicore CPU parallelism was implemented using POSIX threads.

Subsequently, we introduce tree parallel methods for e fficient generation of full and iceberg data cubes. Besides the previously mentioned parallel primitives, these methods use POSIX threads to exploit the multicore CPU parallelism in the simultaneous construction of several cuboids. I.e., all cuboids are distributed into groups and then cuboids in each group are constructed in parallel. Linear memory storage is used to keep tuples in main memory, avoiding additional costs related to building more complex data structures. Likewise, we use some well known strategies to accelerate the data cube computing process, but unlike previous work, our methods feature fi ne grained parallelism provided by parallel primitives.

En su tesis de maestría en el Centro de Investigación en Computación del Instituto Politécnico Nacional, Mario Torres usa la Unidad Gráfica de Proceso (GPU) más la Unidad Central de Procesamiento (CPU) para calcular el cubo de datos completo (con todos sus cuboides) que se utiliza en Minería de Datos. El documento completo está aquí.

La generaci ón de cubos de datos de manera efi ciente es un problema central en los almacenes de datos y el procesamiento anal ítico en l ínea. Es un proceso que puede implicar la ejecuci ón de gran número de operaciones aritm éticas, adem ás de consumir bastante tiempo cuando se realiza a partir de datos de gran volumen. Para una relaci ón R con n atributos o dimensiones m ás un atributo de medida M, R(A1;A2; :::;An;M), el problema b ásico del c álculo del cubo de datos implica la agregaci ón de R para construir 2**n grupos de tuplas respecto a toda posible combinaci ón de las n dimensiones (i.e., el conjunto potencia de las n dimensiones de R). A cada uno de estos grupos de tuplas se le llama cuboide. Dicho problema ha sido investigado y se han propuesto estrategias para resolverlo; sin embargo, hasta ahora la mayor ía de los algoritmos no consideran las ventajas del paralelismo y las recientes arquitecturas de CPUs y GPUs.

En este trabajo se presenta el diseño de un conjunto de operaciones paralelas llamadas primitivas que aprovechan el paralelismo proporcionado por los modelos recientes de GPUs y CPUs multin úcleo. Las primitivas facilitan la generaci ón de cubos de datos llevando a cabo rutinas de ordenamiento, partici ón y agregaci ón. La implementaci ón del software para GPU de este trabajo se realiz ó mediante la plataforma de c ómputo en paralelo conocida como CUDA del fabricante de procesadores gr áficos NVIDIA y para implementar el paralelismo en procesadores multin úcleo se utilizaron hilos POSIX.
Posteriormente, se introducen tres m étodos paralelos para generaci ón de cubos de datos completos y de tipo iceberg. Adem ás de las primitivas previamente diseñadas, estos m étodos utilizan hilos POSIX con el fin de explotar el paralelismo de CPUs multin úcleo en la construcci ón simult ánea de varios cuboides. Esto es, todos los cuboides se distribuyen en grupos y posteriormente los cuboides de cada grupo se generan en paralelo. Se utiliza almacenamiento en memoria lineal a trav és de arreglos de una dimensi ón para almacenar tuplas en memoria principal, evitando costos relacionados con la construcci ón de estructuras de datos m ás complejas. As ímismo, se utilizan algunas estrategias conocidas en la literatura a fin de agilizar la generaci ón del cubo de datos. Sin embargo, a diferencia de los trabajos previos, los m étodos presentados en esta tesis son de un paralelismo de grano fino que se obtiene a trav és del uso de las primitivas paralelas.