Non-conventional vector units for big data workloads

Abstract

RESUMEN: La velocidad de generación de datos, así como su variedad se han visto incrementados en los últimos años, trayendo consigo una era conocida como la era de Big Data. Existe una constante presión sobre los desarrolladores de software y hardware para crear centros de datos que puedan cubrir los requerimientos de tiempo y potencia computacional, debido a esto nuevas ideas son necesarias para explotar las capacidades del hardware existente. Los microprocesadores modernos a menudo incluyen una arquitectura tipo SIMD, refiriéndose en este trabajo a las maquinas vectoriales tal como la AVX de X86-64. Las unidades vectoriales fueron originalmente diseñadas para computo científico; aunque su funcionamiento se ha expandido para soportar trabajos relacionados con Big Data (procesamiento y análisis de datos) de forma más eficiente. Primero fue realizado un análisis general de aplicaciones las cuales presentan un desempeño sub-optimo cuando se aplica vectorización sobre ellas, y un grupo es seleccionado de entre estas aplicaciones como base para futuras pruebas. A partir de este grupo, el estado del arte de hardware especifico que busca resolver estos problemas es estudiado para encontrar oportunidades de mejora y características no presentes y necesarias para las unidades vectoriales. Este trabajo presenta nuestra extensión de Register File Vectorial indexado (iVRF) así como un grupo de extensiones de comportamiento para arquitecturas vectoriales las cuales capturan más DLP (Paralelismo a nivel de datos) sobre aplicaciones que usan index matching como la generación de histogramas y la resolución de matrices dispersas, las cuales son altamente usadas en Big Data. Se usó como base de pruebas el ISA de X86-64 específicamente la maquina AVX256, nuevas estructuras (hardware) son presentadas para implementar las extensiones propuestas. Se realizaron pruebas de funcionalidad sobre de nuestra propuesta usando un simulador full-system CPU modular. Los resultados de nuestras pruebas presentan un speedup promedio de 14.3x para algoritmos de ordenamiento basados en histogramas y un speedup promedio de 12x para algoritmos que trabajan sobre matrices dispersas. ABSTRACT: Data generation rate and variety have increased over the past years, bringing with it the Big Data era. There is a pressure on software and hardware developers to create data centers able to cope the increasing requirements about computational time and power, therefore new approaches are needed to exploit the capabilities of the actual hardware. Modern microprocessors often include a SIMD engine, referring on this work to vector architecture as x86-64 AVX. These vector units are traditionally designed for scientific applications; however, in this thesis we study how vector processor have been extended for supporting Big Data workloads (data analysis and processing) efficiently. First a general analysis of Big Data applications presenting issues when applying vectorization on them is performed, and a set of example is selected as base for further tests. From this, a state-of-the-art about hardware approaches is studied to find opportunities and important characteristics needed by vector architectures. This work presents our indexed Vector Register File (iVRF) extension as well as a set of behavior extensions for vector architectures which expose more DLP (Data Level Parallelism) on applications using index matching like histogram generation and sparse matrix solvers which are highly used on Big Data nowadays. we used as test base x86-64 ISA specifically AVX256 engine, new structures (hardware) to handle and support these extensions are presented. Behavior extensions and structures are implemented and evaluated using a modular full-system CPU simulator. Results shows that our implementation presents an average speedup of 14.3X for sort algorithms working with histograms and an average of 12x for sparse matrix solver algorithms.