Ir al contenido
EN
2015—2022 Archivado

Cómputo de reductos: del algoritmo al FPGA

Trabajo doctoral sobre un problema combinatorio NP-duro, atacado a la vez en diseño de algoritmos y en hardware.

Diagrama de bloques del módulo Generador de Candidatos: las entradas super-reduct y contributes alimentando un selector, tres bloques E1A, E2A y A cuyas salidas llegan a tres multiplexores, registros que guardan el candidato actual, el candidato anterior y J, y un comparador contra todo ceros que levanta la señal done.
Figura 4.5 de la tesis, capítulo de arquitectura hardware: el módulo que genera el siguiente candidato. El orden de búsqueda está cableado, no interpretado — que es justo la razón por la que el cómputo se mueve a un FPGA.
Gráfico de líneas del tiempo de ejecución en segundos frente a la densidad media de 1's, de 0,22 a 0,78, con una barra de desviación estándar en cada punto. Las tres curvas suben hasta un máximo y caen casi a cero en 0,70. fast-BR alcanza el máximo más alto, unos 200 s cerca de 0,26; fast-CT-EXT unos 145 s cerca de 0,34; GCreduct el más bajo, unos 105 s cerca de 0,34. GCreduct corre por debajo de los otros dos hasta cerca de 0,36, a partir de donde fast-BR pasa a ser el más rápido de los tres, y GCreduct se mantiene por debajo de fast-CT-EXT en todo el rango.
Figura 5.1 de la tesis, capítulo 5, página 61: tiempo de ejecución promedio sobre 500 matrices básicas generadas al azar de 2000 filas y 30 columnas, agrupadas en 15 bins de densidad de unas 33 matrices cada uno; las barras son la desviación estándar dentro de cada bin. Implementaciones en Java — las de los propios autores para fast-CT-EXT y fast-BR — cronometradas en un Intel Core i7-5820K a 3,30 GHz con 32 GB de RAM bajo GNU/Linux. El resultado es la regla con que cierra el capítulo: GCreduct es el más rápido por debajo de una densidad de 0,36, fast-BR entre 0,36 y 0,66, y por encima de ahí la elección deja de importar. La leyenda escribe CGreduct, que es una errata de la propia figura de la tesis; se reproduce tal como se defendió, no repintada aquí.

El problema. Computar todos los reductos de un sistema de decisión — los subconjuntos mínimos de atributos que preservan su capacidad de discernimiento — es NP-duro. El enfoque ingenuo enumera el conjunto potencia, y de ese costo no se sale escribiendo mejor código.

Dos frentes a la vez. Del lado algorítmico, GCreduct poda el espacio de búsqueda mediante eliminación de brechas y contribución de atributos; MinReduct computa todos los reductos más cortos sin enumerar el resto. Del lado del hardware, una plataforma FPGA co-diseñada acelera el cómputo de testores irreducibles.

Por qué sigue importando aquí. Es el mismo instinto que produjo todo lo demás en esta página: cuando un cómputo es caro, la respuesta rara vez es una máquina más grande. Es un algoritmo mejor, el lugar correcto donde correrlo, y la disposición a diseñar ambos.