¿Cuál es el algoritmo de recocido simulado utilizado para la colocación en FPGA, descripción completa y en palabras simples?
¿Cuál es el algoritmo de recocido simulado utilizado para la colocación en FPGA, descripción completa y en palabras simples?
La optimización del diseño en un FPGA se complica por las muchas restricciones físicas que están integradas en el chip básico. Un método que se ha encontrado que funciona bien sin tener que lidiar explícitamente con esas restricciones se llama "recocido simulado" (por analogía con la metalurgia).
En un nivel alto, el algoritmo comienza colocando los elementos lógicos al azar en el chip, sin prestar atención a su conectividad con los otros elementos. Luego, itera a través de todos los elementos uno a la vez y evalúa las conexiones a ese elemento, verificando en qué dirección y hasta qué punto van esas conexiones. Si hay un fuerte sesgo en una dirección particular, la posición del elemento se intercambia con una que está en esa dirección general, pero con un desplazamiento aleatorio agregado. Una vez que todos los elementos han sido evaluados de esta manera, el proceso se repite. En cada iteración, la distribución de probabilidad del desplazamiento aleatorio se "reduce" gradualmente; esta es la analogía con el recocido en maturgia; el desplazamiento aleatorio representa la "temperatura" descendente del proceso de migración.
Después de muchas iteraciones, los elementos lógicos generalmente se habrán movido de tal manera que sus conexiones serán más cortas, con elementos que forman parte de la misma subfunción agrupados.
Este método generalmente encuentra buenas soluciones, pero a veces se puede "atascar" en una configuración de los elementos que no es óptima. Por esta razón, todo se hace a menudo varias veces, comenzando con una distribución aleatoria diferente cada vez. El mejor resultado de las varias ejecuciones es el que se mantiene.
Un buen artículo sobre esto apareció en la edición de septiembre de 1989 de Dr. Dobbs
Utilicé ese artículo para implementar una rutina de optimización para el diseño de instrumentación y pude hacer que funcione bien. Tiene que trabajar mucho de forma interactiva con los resultados: si el enfriamiento simulado es demasiado rápido, tenderá a perder los resultados óptimos globales.