Algoritmos heurísticos para el ruteo de dispositivos programables

Abstract

En este documento, se presenta una nueva manera eficiente de obtener un ruteo detallado, para cualquier tipo de FPGA con estructura de islas. A partir de instancias de ruteo global, que proporciona el programa de empaquetamiento versatil, colocación y ruteo, se creó un nuevo algoritmo heurístico llamado búsqueda indexada, que parte de un modelo matemático de satisfacibilidad booleana y que se resuelve mediante una coloración condicional de gráficas, que también se propone aquí. A su vez, se potencializa la heurística de búsqueda indexada, por medio de un árbol R, el cual indexa los datos de tal manera, que la heurística puede conocer rápidamente el número de conflictos, en los que aumenta o disminuye la función objetivo, si se realiza un movimiento. Con cada uno de estos aspectos, se busca un ruteo de calidad perfecta y que además disminuya considerablemente el tiempo necesario para obtener un ruteo detallado. Finalmente, se compara el ruteo detallado de seis instancias obtenidos por el VPR y por la búsqueda indexada.