Resumen

La enumeración de matrices de Costas bidimensionales es un problema con complejidad temporal factorial y ha sido resuelto para tamaños de hasta 29 utilizando clústeres de computadoras. Recientemente se han propuesto matrices de Costas de mayor dimensionalidad y sus propiedades están comenzando a ser comprendidas. Este artículo presenta, hasta donde sabemos, las primeras implementaciones propuestas para enumerar estas matrices multidimensionales en GPUs y FPGAs, así como la primera discusión de técnicas para podar el espacio de búsqueda y reducir el tiempo de ejecución de la enumeración. Tanto las implementaciones en GPU como en FPGA se basan en las simetrías de las matrices de Costas para reducir el espacio de búsqueda y realizar exploraciones concurrentes sobre las soluciones candidatas restantes. El paralelismo de grano fino utilizado para evaluar y avanzar en la exploración, junto con la concurrencia adicional proporcionada por los múltiples núcleos instanciados, permitió que la implementación en FPGA (XC5VLX330-2) lograra mejoras de velocidad de hasta 30 veces sobre la GPU (Ge

• Materias:Control de potencia Núcleo de memoria Sensor de visión Acelerador de hardware Programación de arquitecturas
• Subjects:Power control Memory core Vision sensor Hardware accelerator Architecture programming
• Palabras claves:Enumeración; Bidimensional; Matrices de Costas; Mayor dimensionalidad; GPUs; FPGAs
• Keywords:Enumeration; Two-dimensional; Costas arrays; Higher dimensionality; GPUs; FPGAs