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

La computacion reconfigurable es una tecnologia prometedora que permite ejecutar con gran eficiencia aplicaciones con una alta carga computacional y/o un comportamiento dinamico dificil 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 aciclicos. Toda tarea HW necesita un proceso de reconfiguracion previo a su ejecucion 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 planificacion que reduzca en gran medida estas penalizaciones, solapandolas 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 gestion 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 tecnicas de reutilizacion, prebusqueda y reemplazo de tareas, este planificador consigue reducir las penalizaciones por reconfiguracion del 42% del tiempo total de ejecucion de las tareas a aproximadamente el 9%. Ademas, esta gestion se produce en unos pocos ciclos de reloj, por lo que las penalizaciones que produce en su gestion son insignificantes. Por otro lado, se ha comparado esta implementacion con una version 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 ejecucion 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.