Codiseño y Programación de Aplicaciones Paralelas Embebidas en Sistemas de Computación Heterogénea Reconfigurable: Un Enfoque Basado en Esqueletos Algorítmicos

Abstract

La presente tesis doctoral se enfoca en los Sistemas de Computación Heterogénea Reconfigurables (RHCS, Reconfigurable Heterogeneous Computing Systems). Estos sistemas se basan en dispositivos de computación de arreglos de compuertas programables por campo (FPGA, Field-Programmable Gate Arrays). En particular, el interés de este trabajo se centra en las técnicas de diseño y programación que facilitan el desarrollo de aplicaciones paralelas embebidas que explotan estos sistemas con alto rendimiento. Los sistemas de computación heterogénea reconfigurables (RHCS) se han utilizado para explotar paralelismo mediante el procesamiento acoplado y coordinado entre los FPGA y diferentes dispositivos de computación microprogramables como CPUs y GPUs. Sin embargo, estos sistemas tienen una alta complejidad de programación debido a los detalles asociados al paralelismo y al diseño digital de los FPGA. Esto hace que el proceso de implementar, al mismo nivel de abstracción, tareas y componentes en hardware y software de una aplicación embebida en los RHCS sea difícil de lograr. Es por esto, que el objetivo del presente trabajo doctoral es demostrar que mediante la integración de la técnica de codiseño de sistemas, el paradigma de algoritmo en hardware y el enfoque de esqueletos algorítmicos de Cole [Cole, 1989b] es posible proveer una herramienta con alto nivel de abstracción que facilita el codiseño y programación de aplicaciones paralelas embebidas en estos sistemas. Como solución se presenta una Interfaz de Programación de Aplicaciones Paralelas (Parallel Applications Programming Interface, PAPI), denominada SkeletonCoRe (Reconfigurable Skeletons Core for Parallel Programming). Esta PAPI provee al programador una librería o núcleo de esqueletos algorítmicos reconfigurables que expresan con alto nivel de abstracción paralelismo implícito, estructurado y reconfigurable, encapsulando y ocultando los detalles de bajo nivel del paralelismo, así como el diseño y reconfiguración de los FPGA. Con esto se logra explotar de forma transparente y con alto rendimiento aplicaciones de procesamiento paralelo embebidas que aprovechen la arquitectura de Hardware y Software de los RHCS. Como pruebas de concepto se instancian dos esqueletos algorítmicos reconfigurables llamados PipeSkeleton y TaskSkeleton de SkeletonCoRe, que implementan los patrones de computación paralela "pipeline” y "master/slave”, respectivamente. Estos esqueletos reconfigurables se proporcionan como plantillas de alto nivel en código OpenCL/C++ que heredan las propiedades de las funciones de orden superior, por lo cual toman parámetros de configuración para explotar paralelismo implícito. Estos permiten al programador escribir aplicaciones con alto rendimiento independientemente de la arquitectura del sistema heterogéneo disponible. Se ha definido la arquitectura jerárquica del PAPI con sus capas funcionales y las interacciones entre éstas. Luego, se ha especificado la estructura e interacción de los patrones de cómputo paralelo implementados como esqueletos y se han diseñado como funciones de orden superior. Como demostración de SkeletonCoRe, se ha realizado un conjunto de pruebas usando ambos, PipeSkeleton y TaskSkeleton, con diferentes configuraciones sobre un sistema heterogéneo del tipo CPU, GPU y FPGA. Para la prueba de PipeSkeleton y TaskSkeleton se implementó una aplicación de procesamiento de imagen con 3 tareas coordinadas entre hardware y software. Para cada configuración se tomaron medidas del costo en tiempo de ejecución, entrada/salida y comunicación utilizados por el CPU, GPU y el FPGA. Los resultados demostraron que las configuraciones con núcleos implementados en FPGA y GPU, y las tareas de entrada/salida de datos implementadas por software en CPU se ejecutan más rápido y consumen menos recursos. Como conclusión, la PAPI SkeletonCoRe es una herramienta que proporciona al programador esqueletos reconfiguables con el suficiente nivel de abstracción para programar aplicaciones paralelas y mover fácilmente las funcionalidades entre las tareas de software y hardware durante la etapa de exploración de los espacios de diseño. This PhD thesis focuses on Reconfigurable Heterogeneous Computing Systems (RHCS). These systems are based on Field-Programmable Gate Array (FPGA) computing devices. In particular, the focus of this work is on design and programming techniques that facilitate the development of parallel embedded applications that exploit these systems with high performance. Reconfigurable heterogeneous computing systems (RHCS) have been used to exploit parallelism through coupled and coordinated processing between FPGAs and different microprogrammable computing devices. However, these systems have a high programming complexity due to the details associated with parallelism and the digital design of FPGAs. This makes the process of implementing, at the same level of abstraction, hardware and software tasks and components of an embedded application in RHCSs difficult to achieve. Therefore, the aim of this doctoral work is to demonstrate that by integrating the systems co-design technique, the hardware algorithm paradigm and Cole’s algorithmic skeleton approach [Cole, 1989b], it is possible to provide a tool with a high level of abstraction that facilitates the coding and programming of parallel applications embedded in these systems. The solution is presented as an Applications Programming Interface (PAPI), called SkeletonCoRe (Reconfigurable Skeletons Core for Parallel Programming). This PAPI provides the programmer with a library or reconfigurable algorithmic skeletons core. It expresses at a high level of abstraction implicit, structured and reconfigurable parallelism by encapsulating and hiding the low-level details of parallelism, as well as the design and reconfiguration of FPGAs. This enables the transparent and high performance exploitation of embedded parallel processing applications that take advantage of the RHCS hardware and software architecture. As a proof of concept, two reconfigurable algorithmic skeletons called PipeSkeleton and TaskSkeleton are instantiated, which are part of the SkeletonCoRe PAPI and implement the "pipeline” and "master/slave” parallel computing patterns, respectively. These reconfigurable skeletons are provided as high-level templates in OpenCL/C++ code, which take configuration parameters to exploit implicit parallelism. They allow the programmer to write applications with high performance regardless of the available heterogeneous system architecture. The PAPI hierarchical architecture with its functional layers and the interactions between them has been defined. Then, the structure and interaction of the parallel computing patterns that are implemented as skeletons have been specified and designged by using higher order functions. As a demonstration of the SkeletonCoRe PAPI, a set of tests have been performed using both, PipeSkeleton and TaskSkeleton, with different configurations on a heterogeneous CPU, GPU and FPGA system. For the PipeSkeleton and TaskSkeleton test, an image processing application was implemented with tasks coordinated between hardware and software. For each configuration, cost measurements were taken on execution time, input/output and communication used on the FPGA. The results showed that configurations with FPGA- and GPU-implemented cores and software-implemented input/output tasks on CPU run faster and consume fewer resources. As a conclusion, the SkeletonCoRe PAPI is a tool that provides the programmer with sufficient level of abstraction for applications parallel programming and easily move functionalities between software and hardware tasks during the exploration stage of application design spaces.