Entorno para multitarea hardware en dispositivos reconfigurables con gestión dinámica de particiones y complejidad constante

Resumen

Este trabajo de investigación presenta un algoritmo de complejidad constante, fácil de implementar, realista con respecto a la tecnología existente y rápido de ejecutar, para planificar la ejecución de tareas HW en una FPGA cuyo área se divide en pa rticiones de diferente tamaño. Se prueba que con algoritmos sencillos y fáciles de implementar como los presentados en este trabajo se puede igualar la eficiencia a la hora de gestionar el dispositivo respecto a algoritmos complejos como por ejemplo First Fit. El algoritmo presentado utiliza una estructura de datos muy sencilla para representar el área libre en la FPGA. Además es interesante la posibilidad que ofrece el algoritmo, tras estudiar estadísticamente el perfil de las tareas ejecutadas , de cambiar la disposición de las particiones (tamaño y ubicación) gracias a la Adaptación Dinámica. En los resultados experimentales presentados se observa que el algoritmo es poco sensible al orden de llegada de tareas y presenta un mejor rendimi ento en situaciones de sobrecarga del sistema. Además puede absorber sin perjuicio de su rendimiento picos de tareas de tamaño pequeño que puedan presentarse a lo largo de la ejecución. Otro de los puntos fuertes del algoritmo presentado es el hech o de que en el momento de llegada de cada nueva tarea se puede calcular con rapidez y exactitud el tiempo de espera para dicha tarea. En el caso de que tenga que ser rechazada, esta información se comunica de forma inmediata al resto del SO y no es n ecesario esperar a la expiración de su tiempo máximo como ocurre con el uso de algoritmos complejos, retrasando así la comunicación de rechazo de tarea, lo que limita las posibilidades para su re-planificación. Valores añadidos a este trabajo son e l hecho de que el algoritmo haya sido implementado sobre una Virtex-2 XCV2P30, como se detalla en el apéndice B de la memoria de la tesis y la elaboración de un modelo sencillo y útil, independiente de la heurística de planificación que se utilice, p ara modelar la carga de trabajo con respecto a la capacidad de la FPGA.