Automatic Runtime Performance Optimization Methodology Applied to Dataflow-based Hyperspectral Imaging Cancer Detection Algorithms

Lazcano López, Raquel (2020). Automatic Runtime Performance Optimization Methodology Applied to Dataflow-based Hyperspectral Imaging Cancer Detection Algorithms. Thesis (Doctoral), E.T.S.I. y Sistemas de Telecomunicación (UPM). https://doi.org/10.20868/UPM.thesis.65813.

Description

Title: Automatic Runtime Performance Optimization Methodology Applied to Dataflow-based Hyperspectral Imaging Cancer Detection Algorithms
Author/s:
  • Lazcano López, Raquel
Contributor/s:
  • Juárez Martínez, Eduardo
  • Sanz Álvaro, César
Item Type: Thesis (Doctoral)
Date: 2020
Subjects:
Faculty: E.T.S.I. y Sistemas de Telecomunicación (UPM)
Department: Ingeniería Telemática y Electrónica
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only until 7 July 2021 - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (10MB)

Abstract

Hoy en día, el aumento de la complejidad de los algoritmos, junto con la ingente cantidad de datos que tienen que procesar y los requisitos de tiempo de ejecución, que cada vez son más estrictos, hace necesaria la utilización de plataformas multinúcleo y, por tanto, el uso de técnicas de paralelización. Todo esto ha contribuido en gran medida a que cada vez sea más difícil desarrollar aplicaciones que cumplan estos requisitos y que, además, usen de forma eficiente los recursos disponibles en la plataforma destino, lo que implica, a su vez, un incremento en el tiempo de desarrollo. En los últimos años se han propuesto varias metodologías de trabajo como solución a esta problemática, siendo algunas de las más utilizadas el diseño conocido como Y-chart, el modelado basado en flujo de datos –del inglés, dataflow– y las técnicas de paralelización automática. El diseño Y-chart tiene como objetivo aislar la aplicación de la arquitectura, modelando cada una de ellas por separado y combinándolas después, usando para ello un conjunto de directrices establecidas por los desarrolladores. Por otro lado, el modelado basado en flujo de datos consiste en especificar aplicaciones a través de Modelos de Computación –del inglés, Models of Computation (MoCs)–, cuyas características son especialmente útiles para exponer el paralelismo estructural de la aplicación. Finalmente, las técnicas de paralelización automáticas se basan en simplificar el proceso de paralelización de las aplicaciones, de tal forma que la dedicación de los desarrolladores a esta tarea pueda minimizarse. La combinación de Y-chart y modelado basado en flujo de datos dio como resultado una metodología donde, utilizando losmencionadosMoCs, cada aplicación se modela como un conjunto de tareas –o actores– que intercambian paquetes de información –o, del inglés, tokens–, de tal forma que elmapeado y la planificación de la ejecución de dichas tareas aproveche todos los recursos disponibles en la plataforma destino. Aún así, este proceso conlleva todavía un alto grado de implicación por parte de los desarrolladores, ya que dicha planificación necesita ser refinada iterativamente hasta que se alcanza una situación en la que todos los recursos se utilizan de forma eficiente. Esto se debe, entre otros motivos, a que estas tareas son consideradas las unidades funcionales de esta metodología, y por tanto se comportan como cajas negras; esto significa que su contenido depende exclusivamente de los desarrolladores y que, por tanto, su carga computacional puede no estar correctamente balanceada. Para abordar dicha situación, esta tesis propone diseñar una metodología mejorada que, aunando las tres metodologías descritas anteriormente, optimice aún más el rendimiento de las aplicaciones. Esta metodología tiene como objetivo, por tanto, simplificar el proceso de paralelización y distribución de las aplicaciones sobre arquitecturas multinúcleo, pudiendo utilizarse con un amplio abanico de aplicaciones. Para ello, se propone combinar una metodología de diseño Y-chart basada en flujo de datos con las posibilidades de optimización que ofrece el modelo poliédrico, que se basa en la aplicación de transformaciones agresivas para maximizar el rendimiento de las aplicaciones de forma automática. Además, otro requisito que ha ganado importancia en los últimos años es que las aplicaciones puedan reaccionar ante cambios de contorno que se produzcan en tiempo de ejecución. Por tanto, sería recomendable que la nueva metodología pudiera garantizar el cumplimiento de este requisito. Considerando todo lo anterior, se han seleccionado dos herramientas del estado del arte para que actúen de pilares de la metodología propuesta en esta tesis: por un lado, Parallel Real-time Embedded Executives Scheduling Method (PREESM) –y su planificador dinámico, Synchronous Parameterized and InterfacedDataflowEmbedded Runtime (SPiDER)–, que es un entorno de desarrollo basado en Y-chart y flujo de datos; por el otro, Automatic Speculative Polyhedral Loop Optimizer (Apollo), que es una herramienta de paralelización automática basada en el modelo poliédrico. Estas herramientas se han elegido porque cumplen el requisito de detectar cambios en tiempo de ejecución y actuar en consecuencia: PREESM a través de SPiDER; y Apollo porque es una de las pocas herramientas existentes en la actualidad que extiende la aplicación delmodelo poliédrico al tiempo de ejecución. La combinación de estas dos herramientas abre la puerta, a su vez, a un amplio rango de oportunidades, puesto que las características intrínsecas a la naturaleza de los MoCs basados en flujo de datos pueden incluirse dentro de Apollo de tal forma que: (i) el comportamiento de esta herramienta se adapte al flujo de datos, y (ii) se exploren las nuevas oportunidades de optimización que surgen como consecuencia de considerar estas características, y que por tanto estaban fuera del alcance de Apollo hasta ahora. Por tanto, Apollo se ha extendido para tener en cuenta dichas características, y gracias a ellas su gestor dinámico ahora incluye un sistema de versionado –en inglés, multiversioning– capaz de evaluar varias transformaciones para optimizar el código y elegir la que mejores resultados arroje en función del contexto de la aplicación, que viene definido por características como la cantidad de datos a procesar o la plataforma destino. Una vez extendida la herramienta poliédrica para contemplar las características de flujo de datos y aprovecharse de ellas, el siguiente paso es embeber esta herramienta dentro del entorno de desarrollo dataflow con el objetivo de combinar las múltiples posibilidades de optimización de aplicaciones que estas herramientas ofrecen. Por consiguiente, Apollo se ha embebido dentro tanto de PREESM como de SPiDER, estudiando las diferentes opciones existentes para combinar sus ventajas de tal forma que se obtenga el máximo beneficio de ellas. De esta forma, aparecen nuevas optimizaciones aplicables dentro de cada actor, haciendo posible la explotación simultánea del paralelismo inter-actor –o paralelismo de datos– y de las optimizaciones intra-actor. Como se ha mencionado antes, una de las principales ventajas de unametodología como la descrita en este documento es que pueda usarse en un amplio espectro de aplicaciones. En este sentido, se ha construido una batería heterogénea de aplicaciones de referencia –del inglés, benchmark suite– para validar dicha metodología. Estas aplicaciones han sido extraídas de algunas de las colecciones de aplicaciones más usadas en ambos mundos –poliédrico y dataflow–. Por un lado, del dominio poliédrico se han elegido PolyBench y ApolloBench: la primera colección se ha elegido porque es la más usada por todos los desarrolladores del dominio poliédrico, mientras que la segunda se ha escogido porque es la usada por los desarrolladores de Apollo para validar la versión original de la herramienta, y contiene algunas características específicas que no se contemplan en PolyBench. Por otro lado, en el dominio dataflow no existe una colección uniforme de aplicaciones de referencia, sino que las aplicaciones varían en función del MoC utilizado; por tanto, para validar esta metodología se han elegido tres de las aplicaciones más usadas por los desarrolladores de PREESM y SPiDER para validar nuevas funcionalidades en la herramienta. Con respecto a la evaluación de la metodología propuesta con las aplicaciones de referencia extraídas del dominio poliédrico, los resultados obtenidos muestran que, tal y como se esperaba, la versión extendida de Apollo mejora considerablemente los resultados proporcionados por la versión original para aplicaciones que simulan un comportamiento dataflow; en concreto, cabe mencionar que estos resultados destacan especialmente cuando la cantidad de datos a procesar es pequeña. Además, comparando los resultados obtenidos con los proporcionados por Clang, se observa que el rendimiento también se incrementa, en este caso en mayor proporción cuando la cantidad de datos a procesar es alta, llegando a obtener aceleraciones de 59£ y 161£ para PolyBench y ApolloBench, respectivamente. De la evaluación de estas aplicaciones también se han extraído conclusiones muy interesantes con respecto a la transformación elegida por el sistema multiversioning en cada caso: se ha podido comprobar que, como se esperaba, la transformación evaluada tiene un impacto directo en el tiempo de ejecución, ya que los resultados obtenidos con esta transformación pueden ser beneficiosos o no dependiendo de la aplicación, la cantidad de datos a procesar o la plataforma destino, mostrando así los beneficios que aporta un sistema multiversioning. No obstante, se debe resaltar que dichos beneficios llevan asociada una penalización inicial en el tiempo de ejecución, ya que este sistema depende de una fase de entrenamiento; a pesar de ello, la naturaleza iterativa de las aplicaciones basadas en flujo de datos hace posible hace posible la neutralización de esta penalización al cabo del tiempo. Además, la evaluación de la metodología con las aplicaciones extraídas del dominio dataflow tiene como objetivo principal estudiar las ventajas e inconvenientes asociados a otorgar la capacidad de paralelización a una herramienta u otra. Los resultados obtenidos muestran que las tres aplicaciones seleccionadas permiten una buena representación del problema: una de ellas presenta un mejor rendimiento cuando es PREESM quien gestiona la paralelización –9£ con PREESM, 4£ con Apollo y 6£ con la combinación de ambas, comparando siempre con Clang–; otra presenta aceleración sólo cuando es Apollo quien paraleliza –en torno a 5£–; por último, la tercera presenta tiempos de ejecución mucho más rápidos cuando ambas herramientas se reparten las tareas –14£ con PREESM, 75£ con Apollo y casi 100£ con la combinación–. Esta última aplicación se ha utilizado también para validar las modificaciones añadidas en SPiDER, demostrando que la metodología propuesta es capaz de detectar cambios en tiempo de ejecución y reconfigurar el comportamiento del sistema multiversioning de acuerdo con estos cambios, obteniendo aceleraciones similares a las alcanzadas de forma estática –cercanas a 100£. Por último, se va a utilizar la metodología propuesta en este documento para implementar la aplicación elegida como caso de uso real para esta tesis; el objetivo de este estudio es caracterizar su aplicabilidad a través de una aplicación utilizada en la actualidad. Este caso de uso se ha extraído de un algoritmo complejo usado para detectar tumores cerebrales en tiempo real mientras la intervención quirúrgica se está llevando a cabo. En concreto, la parte del algoritmo seleccionada como caso de uso es la etapa de clasificación supervisada del algoritmo híbrido específicamente diseñado para esta tarea, ya que es la etapa que necesita más recursos de computación y, por tanto, la que más puede beneficiarse de técnicas de optimización automática. Los resultados obtenidos muestran que, efectivamente, las aceleraciones más altas aparecen cuando se combina el potencial de optimización de ambas herramientas, alcanzando aceleraciones de 4£ con respecto a Clang. Además, los resultados obtenidos con esta metodología demuestran ser competitivos con estudios del estado del arte, en los que se ha acelerado este caso de uso utilizando para ello plataformas de altas prestaciones –del inglés, High Performance Computing (HPC)– y explotando la paralelización de estas plataformas de forma manual, con el consecuente incremento del tiempo de desarrollo que ello conlleva. En conclusión, se ha probado que la metodología propuesta en esta tesis conjuga las posibilidades de paralelización que ofrecen los procedimientos dataflow con el potencial de optimización ofrecido por las técnicas de paralelización automática, ya sea explotando las ventajas de cada mundo por separado cuando uno de ellos no es capaz de incrementar el rendimiento, o aunando el potencial de dichos dominios cuando el problema en cuestión es susceptible de ser optimizado por ambos. ----------ABSTRACT---------- Nowadays, the increase in the complexity of algorithms, the growth of the volumes of information to process and the tightening of the performance requirements have contributed to the need for multicore architectures and parallel processing. These challenges have led to widening the gap between application development productivity and platformusage complexity. In the last few years, many methodologies have been proposed to close this productivity gap, like Y-chart strategy, dataflowbased design or automatic parallelization techniques. Y-chart strategy isolates the application from the architecture, modeling each one separately and merging them afterwards under a list of user-defined constraints; dataflow-based design proposes modeling applications using dataflow Models of Computation (MoCs), which are specifically well-suited for exposing their structural parallelism; automatic parallelization techniques parallelize applications with very small effort from developers side. The combination of the first two resulted in a methodology where dataflow-based applications are modeled as a set of tasks –or actors– exchanging pieces of information –or tokens–; these tasks can be automatically deployed onto multicore platforms, mapping and scheduling them so they can make use of all the available resources of the target architecture. Nonetheless, this process is yet arduous from developers side: since the computational load of actors may considerably vary, conceiving an efficient mapping and scheduling of them results in an iterative process. These actors are the functional units of these models, and thus they are considered as black boxes –primitives of the system–, so up until now there is an open issue to solve if their computational load is not well balanced. To tackle this situation, this PhD aims at devising a methodology to further optimize applications throughput by combining these three methodologies, using it with a wide range of applications and simplifying the process of parallelizing and deploying them onto multicore architectures. To do so, the methodology proposed in this document aims at combining a Y-chart dataflow-based design with the optimization potential offered by the polyhedral model, which is a mathematical framework applying aggressive transformations to maximize applications performance. As nowadays there is a trend to consider reactiveness to changes at runtime as a requirement formany applications, it is desirable for the enhanced methodology to ensure this requirement is fulfilled. Hence, two frameworks are selected as cornerstones of this methodology: Parallel Real-time Embedded Executives Scheduling Method (PREESM) –and its dynamic counterpart, Synchronous Parameterized and Interfaced Dataflow Embedded Runtime (SPiDER)– from the Y-chart dataflow-based domain, and Automatic Speculative Polyhedral Loop Optimizer (Apollo) from the polyhedral one. These frameworks are chosen because they guarantee this runtime reactiveness: PREESM thanks to SPiDER, and Apollo because it is one of the few tools in the state of the art successfully extending the polyhedral model to runtime. The combination of dataflow and polyhedral domains creates, in turn, a broad spectrum of new opportunities: the characteristics intrinsic to dataflow MoCs can be embedded within Apollo to (i)make it dataflow-based compliant, and (ii) explore new optimization possibilities these characteristics enable, which were out of reach until now. As a result, Apollo is extended to include these two features, providing its runtime manager with a multiversioning systemto evaluate several optimizing transformations and choose the best one depending on the application context, which in turn is defined by features as volume of data to process or target architecture. Similarly, after modifying and extending the automatic optimization framework to include these new functionalities, it needs to be immersed into the dataflow design environment so as to join their parallelization capabilities. Hence, Apollo has been embedded within both PREESM and SPiDER, assessing how to balance the parallelization potential of both frameworks to make the most of them. By doing so, new optimizations are enabled inside actors to exploit intra-actor optimization opportunities together with inter-actor parallelism –i.e., data parallelism. Since it is desirable for the methodology to be used with a broad range of applications, a heterogeneous benchmark suite is devised to validate the mentioned methodology with applications coming from different domains. To do so, this suite is built by combining some of the most traditionally used benchmark suites in both the polyhedral domain and in the dataflow one. From the polyhedral domain, PolyBench and ApolloBench are chosen, the former because it is the most widely used benchmark suite in the community, and the latter because it was the one used by Apollo developers to originally validate the tool, and it contains several features not represented within PolyBench. From the dataflow domain, due to the lack of uniformity in dataflow benchmark suites, the benchmarks chosen are three of the applications most widely used by PREESM and SPiDER developers when testing new functionalities. The results obtained from the evaluation of the proposed methodology with the polyhedral benchmarks show that, as expected, the extended version of Apollo outperforms by far the original one for applications simulating a dataflow-based behavior, providing particularly good results for small problem sizes. When compared to Clang, the results demonstrate that the throughput is also improved, especially for the largest problem sizes, where maximum speedups of 59£ and 161£ are achieved for PolyBench and ApolloBench, respectively. This study shows also interesting results regarding the transformation selected for each case, proving that the transformation has a direct impact on the execution time: depending on the benchmark, problem size or target architecture, the same transformation may provide very good or very bad results, hence illustrating the benefits of a multiversioning system. This study proves that using such a system comes at the cost of adding a non-negligible initial overhead, but that it can be canceled out thanks to the iterative nature of dataflow applications. Additionally, the main objective of the evaluation of the methodology with the dataflow benchmarks is to assess the advantages and disadvantages of assigning the parallelization capabilities to one framework or the other. The three applications selected prove to be a good representation of this problematic: one of them obtains better results when PREESM parallelizes –9£ with PREESM, 4£ with Apollo and 6£ with the combination, always compared to Clang–; another only obtains speedups when Apollo is in charge –around 5£–; finally, the last one is much faster when the optimizations come from both frameworks –14£ with PREESM, 75£ with Apollo and almost 100£ with the combination–. The latter is also used to functionally validate the changes added within SPiDER, proving the proposed methodology to successfully detect runtime changes and reconfigure the behavior of the multiversioning system accordingly, with similar speedups than those obtained statically –close to 100£. These two studies ensure the correctness of the proposed methodology, using to that end benchmark suites widely applied in the related domains; nonetheless, so as to guarantee that the proposed methodology fulfills the objectives for which it is envisioned and characterize its applicability, a real-life application is implemented using this methodology, considering it as a real use-case. This application has been extracted from a complex algorithm used to locate human brain tumor boundaries in intraoperative real-time during surgical procedures: specifically, the part of the algorithm selected to conform this use-case is the supervised classification stage of the hybrid classification algorithm specifically designed for this task, as it is the most time-consuming part of the algorithm. The results obtained showthat, as expected, the largest speedups are reached when combining the optimization potential of both tools, with speedups close to 4£ when compared to the sequential version. These results prove also to be competitive with those extracted from the state of the art, showing similar execution times using fewer Processing Elements (PEs) and applying automatic parallelization techniques instead of manually exploiting the parallelization, which in turn involves a non-negligible increase in the production times. In conclusion, the methodology proposed in this PhD has been proven to be successful in merging the parallelization potential of dataflow-based specifications with the optimization capabilities of automatic parallelization approaches, which is achieved by either exploiting separately the advantages of each domain when one fails to increase the throughput, or profiting from both potentials in those situations compliant with both worlds.

Funding Projects

TypeCodeAcronymLeaderTitle
Universidad Politécnica de MadridRR01/2015UnspecifiedUnspecifiedContrato Predoctoral del Programa Propio
FP7618080HELICoiDUNIVERSIDAD DE LAS PALMAS DE GRAN CANARIAHypErspectraL Imaging Cancer Detection
Horizon 2020732105CERBEROIBM ISRAEL - SCIENCE AND TECHNOLOGY LTDCross-layer modEl-based fRamework for multi-oBjective dEsign of Reconfigurable systems in unceRtain hybRid envirOnments
Government of SpainTEC2017-86722-C4-4-RPLATINOUnspecifiedPlataforma HW/SW distribuida para el procesamiento inteligente de información sensorial heterogénea en aplicaciones de supervisión de grandes espacios naturales

More information

Item ID: 65813
DC Identifier: http://oa.upm.es/65813/
OAI Identifier: oai:oa.upm.es:65813
DOI: 10.20868/UPM.thesis.65813
Deposited by: Archivo Digital UPM 2
Deposited on: 22 Dec 2020 08:59
Last Modified: 07 Jan 2021 07:30
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM