Averiguar si un valor se encuentra entre una matriz utilizando un FPGA

0

He estado haciendo un montón de ingeniería de software, y me siento intrigado por la implementación del hardware de las cosas en la medida en que me gustaría trasladar uno de mis algoritmos recientes a un FPGA. Tratar de aprender FPGAs, que parece más fácil de lo que solía, pero todavía me deja en la oscuridad para los patrones / soluciones habituales. Así que aquí está mi problema:

Digamos que puse muchos (~ 100) "núcleos" en un FPGA que calcula las posibles coincidencias. Cada coincidencia posible es un valor de 64 bits, y supongamos que la computación dice que las posibles coincidencias son caras (~ 35k ciclos de reloj).

Ahora, una vez que se han calculado las coincidencias, quiero ver si alguna coincide con una lista precomputada de aproximadamente 15k posibles valores de 64 bits. La probabilidad de que se encuentre una posible coincidencia es muy pequeña (~ 1e-8).

¿Cuál sería / debería ser un diseño para calcular si se encuentran posibles coincidencias en mi lista original? Puedo asumir que mi lista original es fija (y presumiblemente clasificada).

En software, he estado utilizando una búsqueda binaria, pero me pregunto sobre el acceso a la RAM en ese caso. Si tuviera 100 núcleos, cada uno de ellos con una coincidencia posible cada 35k ciclos de reloj, significa que (suponiendo que tuviera algún tipo de búfer disponible) podría tener un componente de búsqueda binario siempre que se necesitaran menos de 350 ciclos de reloj para ver si algo coincide (y suponiendo 14 comparaciones para una búsqueda binaria entre elementos de 15k, parece casi factible).

Entonces, ¿alguna idea? ¿Es la búsqueda binaria el camino a seguir (y debería modificarse? ¿Usar un montón para ayudar con el almacenamiento en caché de las líneas de memoria RAM o la búsqueda k-ary? ¿Mirar los mapas de hash o los filtros de floración para un descarte más rápido?) ¿Existe alguna forma "estándar"? para hacer este tipo de cosas?

    
pregunta Wam

1 respuesta

2

Bueno, para almacenar valores de 15K de 64 bits, necesita un número razonable (es decir, aproximadamente 64) BlockRams a los que puede acceder en paralelo. Normalmente tienen puertos duales, por lo que potencialmente puede realizar 128 comparaciones en paralelo. Cada BlockRam (16k bits) almacena 256 valores de 64 bits y puede exponer 2 valores por ciclo, por lo que incluso una búsqueda lineal solo tomará 128 ciclos.

Puede dedicar dos entradas en cada BlockRam a cada valor número 128 de la lista y realizar una comparación de agrupamiento; Si su coincidencia es entre los contenedores 17 y 18, entonces dirija la ubicación 17 dentro de cada BlockRam, entonces una operación adicional probará ese contenedor completo. (Vaya, ya que perdiste una ubicación de 128 para la búsqueda de bin, haz que cada valor 127) ...

Considere su dirección de muestra en el rango de 0 a 16000 como N * 127 + M donde:
N varía de 0 a 127 (128 contenedores)
M oscila entre 0 y 126 (127 valores dentro de cada bandeja).

La primera comparación (comparación de bin) accede a 128 valores, almacenados en la ubicación 127 (y 255 en el segundo puerto) dentro de cada BlockRam. Estos valores son entradas de lista N * 127 + 0 para todas las N en 0 a 127.
Para algunos N, el valor (N) < = coincidir < valor (N + 1) - por lo tanto, bin N es el bin para buscar más. Tenga en cuenta que esto requiere una comparación relacional

Ahora abordamos la ubicación N en cada BlockRam y realizamos una comparación de igualdad.
Cada BlockRam contiene (en su Nª dirección) un valor (N + M) para M de 0 a 126.
NB: esto significa que la última BlockRam no está en uso y solo realizamos 127 comparaciones de igualdad. Si una de estas M coincide, calcule N * 127 + M, de lo contrario, señale una falla.

Toma un poco más de 2 ciclos gracias a la indirección y la memoria síncrona de BlockRam, pero probablemente lo suficientemente rápido para su propósito. Dudo que una GPU pueda coincidir con 3 ciclos ...

Supongo que es lo suficientemente barato como para ordenar previamente e intercalar la lista, probablemente en el software del host, antes de cargarla en BlockRams.

Por lo tanto, los datos se intercalan de manera que la Nth BlockRam contiene

Address    Data   
0          List(0*127 + N)   
1          List(1*127 + N)   
2          List(2*127 + N)   
...   
126        List(126*127 + N)   
127        List(N*127 + 0) (the bin comparison value)
    
respondido por el Brian Drummond

Lea otras preguntas en las etiquetas