Nuevos mecanismos hardware-software para explotar paralelismo en sistemas multinúcleo masivos

Abstract

Uno de los componentes principales de cualquier máquina de propósito general es el procesador, éste se puede encontrar en sistemas tan diversos como servidores o sistemas de cómputo de alto rendimiento (HPC) hasta plataformas portátiles como tablets, inclusive en smartcards. Su principal tarea es ejecutar programas tan rápido como sea posible considerando limitaciones como el costo del propio sistema y su consumo energético. Los procesadoresmulticorese pueden encontrar en todos los segmentos del mercado, desde procesadores embebidos hasta procesadores para HPC, pero pocas aplicaciones pueden hacer uso eficiente de estos recursos computacionales. Los actualesframeworkstiene como objetivo soportar paralelismo a nivel de thread en aplicaciones o permitir sincronizar el cómputo por medio de pasaje explícito de mensajes, pero el overhead que se agrega al utilizar estas técnicas impide su uso para instancias pequeñas de problemas. En esta tesis se presenta Micro-threads (Mth), una propuesta co-diseñada de hardware-software enfocada a compartir la administración de threads y a permitir que las aplicaciones puedan acceder a recursos paralelos con un overhead reducido. Se busca, entonces, ejecutar eficiente fragmentos de código pequeños o instancias de problemas que, de otra manera, resultaría impracticable debido al overhead. El mecanismo propuesto se basa en delegar el control de los recursos a las aplicaciones y a mejorar la forma en que se almacena y carga un contexto de ejecución, junto con un eficiente sistema de sincronización de threads. Los experimentos realizados sobrela propuesta se enfocan sobre dos aspectos, por unlado, un conjunto de algoritmos paradigmáticos bien definidos que cubren un amplio espectro de formas de sincronización y patrones de cómputo: filtro de conversión a HSL (trivialmente paralelizable), FFT Radix2 (algoritmo recursivo), descomposición LU (barrera de sincronización en cada ciclo) y algoritmo de camino mínimo de Dantzig(basado en grafos y operaciones sobre matrices). Los resultados muestran un notable speedup para todos los casos, incluso para instancias de tamaño reducido, que no superan los cientos de bytes. Además, el estudio muestra que la inicialización y sincronización no impacta de forma significativa sobre Mth a diferencia de otras tecnologías estudiadas. Por otro lado, se analizó el comportamiento de Mth sobre una aplicación de interés real y amplio uso. Los motores de base de datos (DBMS) constituyen no solo una parte fundamental de cualquier negocio, sino que también son utilizados diariamente en sistemas embebidos en aplicaciones móviles. Se propuso implementar modificaciones a un DBMS embebido utilizando Mth de manera que pudiera soportar la resolución de planificaciones paralelas de consultas. La propuesta incluye dar soporte al paralelismo utilizando Mth y un esquema para coordinar los recursos resolviendo planificaciones en múltiples máquinas virtuales. La combinación de ambos enfoques produjo un uso eficiente de los recursos computacionales, incluso para consultas de muy bajo volumen de datos, permitiendo la ejecución en paralelo de consultas que no pueden ser resueltas de esta forma por los DBMS actuales. Los resultados muestran una notable ganancia en términos de reducción del tiempo de ejecución y consumo de energía utilizando Mth aplicado a una DBMS embebida (SQLite). En términos generales, los resultados obtenidos alientan la utilización del esquema propuesto enMth, que aparece como una solución gradual al uso de múltiples cores en aplicaciones que actualmente no pueden aprovechar el incremento en la cantidad de recursos paralelos disponibles.

One of the main components of any general-purpose machine is the microprocessor, which can be found at the heart of every computer: from standard servers and high performance computing nodes to portable mobile platforms. Its main task is to correctly execute programs as fast as it can, having the production cost and consumption as design limitations. Multi-core processors are ubiquitous in all market segments from embedded to high performance computing, but only few applications can efficiently utilize them. Existing parallel frameworks aim to support thread-level parallelism in applications, but the imposed overhead prevents their usage for small problem instances. This work presents Micro-threads(Mth) a hardware-software co-designed proposal focused on a shared thread management model enabling the use of parallel resources in applications that have small chunks of parallel code or small problem inputs by a combination of software and hardware: delegation of the resource control to the application, an improved mechanism to store and fill processor's context, and an efficient synchronization system. In thiswork,we firstly deminstrate the factibilityof usingour proposal using a setof algorithms: HSL filter(trivially parallel), FFT Radix2(recursive algorithm), LU decomposition(barrier every cycle) and Dantzig algorithm(graph based,matrixmanipulation). Remarkable speedups and efficiency areobtained in all the cases, even when dealing with instance size of the order of hundreds of bytes. Moreover, initialization and synchronization do not impact in its behavior showing remarkable speed-up in the wide range of analyzed cases. To complete the evaluation of Mth, we modified an embedded relational database engine (DBMS) to support parallel operation. Database servers constitute not only the backbone of almost every enterprise, but also are used daily as embedded DBMS by millions of users in mobile applications, to store, manage and retrieve data without the need of special administration or configuration. We propose the use of Mth processor architecture (hardware side) with a parallel resources coordination schema (software side) in an embedded DBMS modified to support parallel query solving. The combination of both approaches produces an efficient use of multicore processors even when the workload is small, enabling the parallel execution of queries that are out of reach of the parallel support in current DBMS.We show that parallel query execution of very small queries can be treatedwith remarkable gains in terms of execution time and energy consumption using Mthwhich is applied to a broadly used embedded relational DBMS (i.e. SQLite). The results encourage the use of Mth and could smooth the use of multiple cores for applications that currently can not take advantage of the proliferation of the available parallel resources in each chip.