Novel vector architectures for data management

Author

Hayes, Timothy

Director

Valero Cortés, Mateo

Codirector

Palomar Pérez, Óscar

Date of defense

2015-07-08

Pages

179 p.



Department/Institute

Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors

Abstract

As the rate of annual data generation grows exponentially, there is a demand to manage, query and summarise vast amounts of information quickly. In the past, frequency scaling was relied upon to push application throughput. Today, Dennard scaling has ceased, and further performance must come from exploiting parallelism. Vector architectures offer a highly efficient and scalable way of exploiting data-level parallelism (DLP) through sophisticated single instruction-multiple data (SIMD) instruction sets. Traditionally, vector machines were used to accelerate scientific workloads rather than business-domain applications. In this thesis, we design innovative vector extensions for a modern superscalar microarchitecture that are optimised for data management workloads. Based on extensive analysis of these workloads, we propose new algorithms, novel instructions and microarchitectural optimisations. We first profile a leading commercial decision support system to better understand where the execution time is spent. We find that the hash join operator is responsible for a significant portion of the time. Based on our profiling, we develop lightweight integer-based pipelined vector extensions to capture the DLP in the operator. We then proceed to implement and evaluate these extensions using a custom simulation framework based on PTLsim and DRAMSim2. We motivate key design decisions based on the structure of the algorithm and compare these choices against alternatives experimentally. We discover that relaxing the base architecture's memory model is very beneficial when executing a vectorised implementation of the algorithm. This relaxed model serves as a powerful mechanism to execute indexed vector memory instructions out of order without requiring complex associative hardware. We find that our vectorised implementation shows good speedups. Furthermore, the vectorised version exhibits better scalability compared to the original scalar version run on a microarchitecture with larger superscalar and out-of-order structures. We then make a detailed study of SIMD sorting algorithms. Using our simulation framework, we evaluate the strengths, weaknesses and scalability of three diverse vectorised sorting algorithms- quicksort, bitonic mergesort and radix sort. We find that each of these algorithms has its unique set of bottlenecks. Based on these findings, we propose VSR sort- a novel vectorised non-comparative sorting algorithm that is based on radix sort but without its drawbacks. VSR sort, however, cannot be implemented directly with typical vector instructions due to the irregularity of its DLP. To facilitate the implementation of this algorithm, we define two new vector instructions and propose a complementary hardware structure for their execution. We find that VSR sort significantly outperforms each of the other vectorised algorithms. Next, we propose and evaluate five different ways of vectorising GROUP BY data aggregations. We find that although data aggregation algorithms are abundant in DLP, it is often too irregular to be expressed efficiently using typical vector instructions. By extending the hardware used for VSR sort, we propose a set of vector instructions and novel algorithms to better capture this irregular DLP. Furthermore, we discover that the best algorithm is highly dependent on the characteristics of the input. Finally, we evaluate the area, energy and power of these extensions using McPAT. Our results show that our proposed vector extensions come with a modest area overhead, even when using a large maximum vector length with lockstepped parallel lanes. Using sorting as a case study, we find that all of the vectorised algorithms consume much less energy than their scalar counterpart. In particular, our novel VSR sort requires an order of magnitude less energy than the scalar baseline. With respect to power, we discover that our vector extensions present a very reasonable increase in wattage.


El crecimiento exponencial de la ratio de creación de datos anual conlleva asociada una demanda para gestionar, consultar y resumir cantidades enormes de información rápidamente. En el pasado, se confiaba en el escalado de la frecuencia de los procesadores para incrementar el rendimiento. Hoy en día los incrementos de rendimiento deben conseguirse mediante la explotación de paralelismo. Las arquitecturas vectoriales ofrecen una manera muy eficiente y escalable de explotar el paralelismo a nivel de datos (DLP, por sus siglas en inglés) a través de sofisticados conjuntos de instrucciones "Single Instruction-Multiple Data" (SIMD). Tradicionalmente, las máquinas vectoriales se usaban para acelerar aplicaciones científicas y no de negocios. En esta tesis diseñamos extensiones vectoriales innovadoras para una microarquitectura superescalar moderna, optimizadas para tareas de gestión de datos. Basándonos en un extenso análisis de estas aplicaciones, también proponemos nuevos algoritmos, instrucciones novedosas y optimizaciones en la microarquitectura. Primero, caracterizamos un sistema comercial de soporte de decisiones. Encontramos que el operador "hash join" es responsable de una porción significativa del tiempo. Basándonos en nuestra caracterización, desarrollamos extensiones vectoriales ligeras para datos enteros, con el objetivo de capturar el paralelismo en este operandos. Entonces implementos y evaluamos estas extensiones usando un simulador especialmente adaptado por nosotros, basado en PTLsim y DRAMSim2. Descubrimos que relajar el modelo de memoria de la arquitectura base es altamente beneficioso, permitiendo ejecutar instrucciones vectoriales de memoria indexadas, fuera de orden, sin necesitar hardware asociativo complejo. Encontramos que nuestra implementación vectorial consigue buenos incrementos de rendimiento. Seguimos con la realización de un estudio detallado de algoritmos de ordenación SIMD. Usando nuestra infraestructura de simulación, evaluamos los puntos fuertes y débiles así como la escalabilidad de tres algoritmos vectorizados de ordenación diferentes quicksort, bitonic mergesort y radix sort. A partir de este análisis, proponemos "VSR sort" un nuevo algoritmo de ordenación vectorizado, basado en radix sort pero sin sus limitaciones. Sin embargo, VSR sort no puede ser implementado directamente con instrucciones vectoriales típicas, debido a la irregularidad de su DLP. Para facilitar la implementación de este algoritmo, definimos dos nuevas instrucciones vectoriales y proponemos una estructura hardware correspondiente. VSR sort consigue un rendimiento significativamente más alto que los otros algoritmos. A continuación, proponemos y evaluamos cinco maneras diferentes de vectorizar agregaciones de datos "GROUP BY". Encontramos que, aunque los algoritmos de agregación de datos tienen DLP abundante, frecuentemente este es demasiado irregular para ser expresado eficientemente usando instrucciones vectoriales típicas. Mediante la extensión del hardware usado para VSR sort, proponemos un conjunto de instrucciones vectoriales y algoritmos para capturar mejor este DLP irregular. Finalmente, evaluamos el área, energía y potencia de estas extensiones usando McPAT. Nuestros resultados muestran que las extensiones vectoriales propuestas conllevan un aumento modesto del área del procesador, incluso cuando se utiliza una longitud vectorial larga con varias líneas de ejecución vectorial paralelas. Escogiendo los algoritmos de ordenación como caso de estudio, encontramos que todos los algoritmos vectorizados consumen mucha menos energía que una implementación escalar. En particular, nuestro nuevo algoritmo VSR sort requiere un orden de magnitud menos de energía que el algoritmo escalar de referencia. Respecto a la potencia disipada, descubrimos que nuestras extensiones vectoriales presentan un incremento muy razonable

Keywords

Computer architecture; Microarchitecture; Data-level parallelism; Vector processors; Single instruction-multiple data; Database management systems; Decision support systems; Online analytical processing; Hash join; Sorting; Aggregation

Subjects

004 - Computer science and technology. Computing. Data processing

Knowledge Area

Àrees temàtiques de la UPC::Informàtica

Documents

TTH1de1.pdf

4.905Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)