Algoritmos metaheurísticos en el problema del particionado hardware/software de sistemas embebidos

El particionado hardware/software es una tarea fundamental en el co-diseño de sistemas embebidos. En ella se decide, teniendo en cuenta las métricas de diseño, qué componentes se ejecutarán en un procesador de propósito general (software) y cuáles en un hardware específico. En los últimos años se han propuesto diversas soluciones al problema del particionado dirigidas por algoritmos metaheurísticos. Sin embargo, debido a la diversidad de modelos y métricas utilizadas, la elección del algoritmo más apropiado sigue siendo un problema abierto. En este trabajo se presenta una comparación de seis algoritmos metaheurísticos: Búsqueda aleatoria (Random search), Búsqueda tabú (Tabu search), Recocido simulado (Simulated annealing), Escalador de colinas estocástico (Stochastic hill climbing), Algoritmo genético (Genetic algorithm) y Estrategia evolutiva (Evolution strategy). El modelo utilizado en la comparación está dirigido a minimizar el área ocupada y el tiempo de ejecución, las restricciones del modelo son consideradas como penalizaciones para incluir en el espacio de búsqueda otras soluciones. Los resultados muestran que los algoritmos Escalador de colinas estocástico y Estrategia evolutiva son los que mejores resultados obtienen en general, seguidos por el Algoritmo genético.

Hardware/software partitioning is a key task for embedded system co-design. The main goal of this task is to decide which components of an application will be executed in a general purpose processor (software) and which ones on a specific hardware. In last years, several approaches have been proposed for solving the HSP problem, directed by metaheuristics algorithms. However, due to diversity of models and metrics used, the choice of the best suited algorithm is an open problem yet. This article presents a comparison of six metaheuristics algorithms: Random Search, Tabu Search, Simulated Annealing, Hill Climbing, Genetic Algorithm and Evolution Strategy. The model presented is aimed to minimize the hardware area and execution time, restrictions are considered as penalizations in order to include in the search space other solutions. Results show that Hill climbing and Evolution strategy are the algorithms that obtains best results in general, followed by the Genetic Algorithm.