Técnicas de partición y ubicación para sistemas multi-FPGA basadas en algoritmos genéticos

Zusammenfassung

Los sistemas Multi-FPGA (MFPGA) se utilizan para multitud de aplicaciones debido fundamentalmente a sus posibilidades para realizar prototipos y para hacer correcciones sobre los diseños implementados con un bajo costo. Una de las tareas más difíciles en el diseño de sistemas MFPGA es la partición del sistema. Los principales problemas se encuentran en la dificultad de utilizar parte de la lógica debido a la limitación en el número de pines de entrada-salida (PE/S) disponibles. La mayoría de los trabajos realizados hasta el momento para abordar el problema de la partición, son adaptaciones de otros campos del diseño VLSI, y por lo tanto ignoran las características especiales de este tipo de circuitos. En este trabajo se presenta un nuevo método para resolver el problema de la partición en sistemas MFPGA. EL método utiliza la teoría de grafos para describir el circuito y a continuación se aplica un algoritmo genético clásico con una codificación que se adapta especialmente al problema. Una de las características más importantes es que respeta la estructura general del circuito. A la hora de evaluar el consumo de PE/S es necesario tener en cuenta que, en ciertas ocasiones, hay que comunicar partes del circuito que están en FPGAs no adyacentes por lo que el problema de la escasez de PE/S se agrava aún más. Para ello, se presenta una técnica de ubicación simultanea a la partición en la que las particiones con un mayor número de conexiones entre sí, tienen preferencia para ser ubicadas en FPGAs adyacentes y disminuir así el consumo de PE/S. Para realizar los experimentos se han utilizado los circuitos de prueba incluidos en Partitioning 93 benchmarks descritos en XNF (Xilinx Netlist Format). Los resultados obtenidos muestran como los algoritmos genéticos pueden llevar a cabo con éxito la tarea de la partición en este tipo de problemas. También se presenta un nuevo operador que permite al algoritmo genético evitar problemas de convergencia prematura.