Modelización y Asignación de Tareas para Aplicaciones Paralelas con Flujo Continuo de Datos de Entrada

Abstract

Las aplicaciones paralelas que procesan flujos continuos de datos de entrada, denominadas como aplicaciones pipeline, son de gran interés para la comunidad científica. Los principales criterios de rendimiento en el proceso de su optimización son dos: (a) minimizar la latencia, de forma que se obtenga el resultado para un dato de entrada en el menor tiempo posible y (b) conseguir un ratio de datos procesados por unidad de tiempo predeterminado, valor denominado como productividad.<br/>La necesidad de procesar una flujo continuo de datos, añade un factor de iteratividad en la ejecución de las tareas, lo cual supone un incremento en la complejidad de su optimización respecto a las aplicaciones que solo procesan un dato de entrada.<br/>El objetivo de este trabajo de tesis contribuye en aportar una solución en la optimización de las aplicaciones pipeline. El proceso de optimización está basado en la obtención de una productividad específica en la ejecución de la aplicación. Para realizarllo, se aborda el problema mediante dos estrategias: (a) cuando la aplicacione no tienen la capacidad de alcanzar la productividad requerida, se crea una nueva estructura para el grafo de tareas que lo permita y, (b) en la situación de que le requerimiento de productividad sí sea alcanzable, se definen estrategias de mapping que asignan las tareas a los procesadores asegurando la capacidad de obtener el rendimiento marcado como objetivo. La arquitectura de ejecución escogida en esta tesis está basada en la arquitectura de memoria distribuida, por ser ésta la más utilizada en la actualidad en el cómputo de altas prestaciones.<br/>Con respecto a la definición del grafo de tareas, esta tesis desarrolla dos técnicas basadas en la paralelización/replicación de taeras y que minimizan la sobrecarga de las comunicaciones. Ambas técnicas localizan las tareas que actúan como cuello de botella en la obtención del requisito de productividad. Con el conocimiento de su funcionalidad y del tipo de flujo de datos a tratar aplican: (a) paralelismo de datos para disminuir el tiempo de cómputo individual de cada uno de los datos de entrada o (b) replicación de tareas para aumentar la capacidad de procesar, de forma concurrente, más datos del flujo de entrada. <br/>En el proceso de mapping, en el que las tareas de la aplicación serán asignadas a los nodos de procesamiento de la arquitectura de ejecución, esta tesis propone dos heurísticas de mapping basadas en el concepto de etapa síncrona y con diferente complejidad. Estas heurísticas reciben el nombre de MPASS (Mapping of Pipeline Applications based on Synchronous Stages) y MPART (Mapping of Pipeline Applications based on Reduced Tree). Ambas heurísticas, poseen los mismos objetivos para la asignación: (a) obtener una productividad prefijada, minimizando el número de nodos de procesamiento o (b) minimizar la latencia, bajo un requisito de productividad a alcanzar y, de nuevo, minimizando el número de nodos de procesamiento.<br/>La experimentación se ha realizado utilizando un conjunto de aplicaciones sintéticas que modelan el comportamiento de las aplicaciones pipeline y tres aplicaciones reales de diferentes ámbitos científicos: el compresor de vídeo MPEG2, IVUS (IntraVascular UltraSound), encargada de procesar imágenes medicas para definir la estructura arterial y BASIZ (Bright And Satured Images Zones), que detecta en una secuencia de imágenes, aquellas regiones que captan la atención del ojo humano. Los resultados obtenidos demuestran como las técnicas propuestas son capaces de alcanzar el redimiento marcado como objetivo, proponiendo la estructura más adecuada para el grafo de tareas y mediante el mapping apropiado para las aplicaicones pipeline.

Parallel applications that process an input data stream, called pipeline applications, are currently focussing the interest of scientific comunity. The main issues to deal with in the optimization process of these applications are the following two: (a) to minimize latency, allowing the execution of one data of the input stream in the smallest possible time and, (b) to achieve a specific ratio of data processed per time unit, named as throughput.<br/>The necessity of processing an input data stream, adds a characteristic of iterativity in the execution of tasks that increases the complexity of the optimization of these applications compared with this for parallel applications that only process a single input data.<br/>The aim of this thesis is to contribute with a solution in the optimization of the pipeline applications. The optimization process is based on the obtention of a specific throguhput for the application during the execution. To do this, we confront the problem with two kind of strategies: (a) when the pipeline application is not able to achieve the throughput requirement, we develop the definition of a new task graph structure that allows it and, (b) in the situation where the required throuhgput is achievable, we define task mapping strategies that assign tasks to processors ensuring the capacity of obtaining the performance objective. The execution architecture selected in this thesis is based on the distributed memory arquitecture, as can be the clusters of workstations, which in the present time are broadly used on high performance computing.<br/>Related to the task graph definition issue, this thesis propose two new techniques based on task parallelization/replication and reduce the communications overhead. Both techniques find the bottleneck tasks that don't allow to reach the throughput requirement. With the knowledge of their functionality and the kind of input data stream they apply: (a) data parallelism to minimize the individual computation time of a single input data or, (b) task replication in order to increase the ability of the pipeline application to process concurrently a higher number of input data.<br/>In the mapping process, where the tasks of the applications are assigned to the processors on the execution architecture, this thesis proposes two new mapping heuristics based in the synchronous stage concept, with different complexity. These heuristics are named as MPASS (Mapping of Pipeline Applications based on Synchronous Stages) and MPART (Mapping of Pipeline Applications based on Reduced Tree). Both mapping heuristics have the same objectives: (a) to obtain the throughput used as the requirement by minimizing the number of processors and, (b) to minimize the latency, under a throughput requirement to be achieved by minimizing the number of processors to be used too.<br/>The experimentation process is carried out using a set of synthetic applications that model the behaviour of the pipeline applications, and with three real applications of different scientific fields: the video mpeg-2 compressor, IVUS (IntraVascular-UltraSound) that process medical images in order to determine the arterial structure and BASIZ (Bright and Satured Images Zones) that detects on a image sequence, the zones that capture the main interest of the human eye. The results show that the proposed techniques are able to reach the target performance, proposing the best suitable task graph structure and the appropriate task mapping for these pipeline applications.