Resumen

La partición hardware/software (HW/SW) consiste en determinar qué componentes de un sistema se implementan en hardware y cuáles en software. Es uno de los pasos más importantes en el diseño de sistemas embebidos. El problema de la partición HW/SW es un problema de optimización binario con restricciones NP-hard. En este artículo, proponemos un algoritmo memético basado en la búsqueda tabu para resolver el problema de particionamiento HW/SW. En primer lugar, convertimos el problema binario restringido HW/SW en un problema binario no restringido utilizando una función de penalización adaptativa que no tiene parámetros. A continuación, se propone un algoritmo memético para resolver este problema sin restricciones. El algoritmo utiliza una búsqueda tabú como procedimiento de búsqueda local. Esta búsqueda tabú tiene una característica especial con respecto a la generación de soluciones, y utiliza un mecanismo de retroalimentación para actualizar la tenencia tabú. Además, el algoritmo integra un procedimiento de reconexión de caminos para la explotación de las soluciones recién encontradas. Se presentan resultados computacionales utilizando una serie de instancias de prueba extraídas de la literatura. El algoritmo demuestra su robustez cuando sus resultados se comparan con los de otros dos algoritmos. También se demuestra la eficacia de la función de penalización adaptativa sin parámetros propuesta.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Mathematical logic
• Palabras claves:búsqueda tabu, algoritmo, algoritmo memético, función de penalización adaptativa libre, problema de partición sw, función de penalización adaptativa, problema de optimización binario, hw binario restringido, procedimiento de búsqueda local, procedimiento de reconexión de caminos
• Keywords:tabu search, algorithm, memetic algorithm, free adaptive penalty function, sw partitioning problem, adaptive penalty function, binary optimization problem, constrained binary hw, local search procedure, path relinking procedure