Planificación de grafos de tareas para sistemas multi-proceso dinámicamente reconfigurables

Abstract

La computación reconfigurable es una tecnología prometedora que permite ejecutar con gran eficiencia aplicaciones con una alta carga computacional y/o un comportamiento dinámico difícil o imposible de predecir, a la vez que reutilizar los mismos recursos HW para distintas tareas. En sistemas empotrados, las aplicaciones se representan frecuentemente como grafos de tareas dirigidos acíclicos. Toda tarea HW necesita un proceso de reconfiguración previo a su ejecución que puede producir penalizaciones significativas (del orden de ms) que, a su vez, pueden reducir en gran medida el rendimiento del sistema. Para intentar superar este problema, es imprescindible contar con una buena estrategia de planificación que reduzca en gran medida estas penalizaciones, solapándolas con ejecuciones de otras tareas. No obstante, esta labor puede derivar en una gran carga computacional si un procesador empotrado se encarga de ello, al involucrarse en el uso de estructuras de datos complejas y numerosas comunicaciones HW-SW.Como consecuencia, esta gestión puede producir penalizaciones adicionales. Por tanto, para superar este nuevo problema se ha desarrollado un planificador HW utilizando recursos reconfigurables (aproximadamente el 13% de una FPGA Virtex-II PRO xc2vp30). Mediante técnicas de reutilización, prebúsqueda y reemplazo de tareas, este planificador consigue reducir las penalizaciones por reconfiguración del 42% del tiempo total de ejecución de las tareas a aproximadamente el 9%. Además, esta gestión se produce en unos pocos ciclos de reloj, por lo que las penalizaciones que produce en su gestión son insignificantes. Por otro lado, se ha comparado esta implementación con una versión SW equivalente que no tiene coste HW pero, de acuerdo a nuestros experimentos, produce unas penalizaciones que oscilan entre el 1% y el 3% del tiempo total de ejecución de los grafos de tareas. [ABSTRACT] Reconfigurable computing is a promising technology that allows executing efficiently applications with a very high workload and/or dynamic and unpredictable behaviour. In addition, with this technology, HW resources can be reused for different tasks. In embedded systems,applications are frequently represented as direct acyclic task graphs. Every HW task needs to perform a reconfiguration process before starting its execution. This process can generate significant overheads (of the order of milliseconds) which, in turn, can greatly reduce the system’s performance. To try to overcome this problem, it’s essential to use a good scheduling strategy that greatly reduces these overheads, overlapping these reconfigurations with the execution of previous tasks. However, this management involves a hith workload since the processor must deal with complex complex data structures and HW-SW communications. As a result, it may produce additional time penalties. Hence, to overcome this new problem we have developed a HW scheduler using reconfigurable resources (approximately 13% of a Virtex-II PRO xc2vp30). Applying reuse, prefetch and replacement techniques; this scheduler can reduce reconfiguration overheads from 42% to 9% of the total execution time of task graphs. Moreover, this management is performed in just a few clock cycles, so it generates a negligible overnead. Moreover, we have compared this implementation with an equivalent SW version, which has no HW cost but, according to our experiments, generates overheads from 1% to 3% of the execution time of a task graph.