Ejecutando una ecuación larga en un ciclo de reloj [cerrado]

0

Estoy utilizando la placa DE2-115 para hacer un recorrido en una estructura de datos forestales en una frecuencia de 50 MHz. Se han almacenado varios árboles en la ROM del chip, ahora debo configurar la dirección que puede apuntar a un determinado nodo en un determinado árbol durante la operación de decisión.

La asignación de direcciones se convertirá en una larga ecuación como: (Utilizando Verilog)

    vip_rom_addr_out_1 = (2251*( {total_tree_cnt[5:0], 1'b0} )) +
        + 75 + (now_i_1 - 15)*68 + leaf_cnt;

Encontré que esta ecuación parece que no se puede calcular en un ciclo de reloj (50 MHz), porque el resultado muestra que "vip_rom_addr_out_1" no es correcto en el tablero.

¿Debo convertir la ecuación en múltiples tuberías? ¿Existen métodos eficaces para acceder a una gran cantidad de árboles en FPGA que puedan permitir el acceso a la memoria en un ciclo de reloj?

Gracias por tus sugerencias.

Detalle de la estructura de datos

Cada árbol es un árbol binario completo con 16 hojas. Cada dirección correspondiente a 1 palabra (cada palabra es de 8 bits).

Algunos datos se almacenan en cada división de cada árbol, estos datos se enumeran a continuación: (Divisiones significa los nodos que tienen dos hijos, un total de 15 divisiones en cada árbol)

1. Two data numbers "a0" and "a1", each number is 2 byte.
2. One data number "b" of 8 bits.

Hay 68 pares de números (m, n) almacenados en cada hoja, m y n son los 8 bits:

Leaf 0:
(m0_0, n0_0) 
(m1_0, n1_0)
(m2_0, n2_0)
...... 
(m67_0, n67_0)
------------
Leaf 1:
(m0_1, n0_1) 
(m1_1, n1_1)
(m2_1, n2_1)
...... 
(m67_1, n67_1)
------------
Leaf 2:
...

Detalle de memoria

100 árboles binarios como se mencionó anteriormente se han almacenado en la ROM en chip de 2 puertos.

[For Tree 1]
address 0: [a0 for split 0, lower 8 bits]
address 1: [a0 for split 0, higher 8 bits]
address 2: [a0 for split 1, lower 8 bits]
address 3: [a0 for split 1, higher 8 bits]
...
address 28: [a0 for split 14, lower 8 bits]
address 29: [a0 for split 14, higher 8 bits]
--------------------------------------------
address 32: [a1 for split 0, lower 8 bits]
address 33: [a1 for split 0, higher 8 bits]
address 34: [a1 for split 1, lower 8 bits]
address 35: [a1 for split 1, higher 8 bits]
...
address 58: [a1 for split 14, lower 8 bits]
address 59: [a1 for split 14, higher 8 bits]
--------------------------------------------
address 60: [b for split 0]
address 61: [b for split 1]
address 62: [b for split 2]
...
address 74: [b for split 14]
-----------------------------------
address 75: m0 for leaf 0
address 76: m1 for leaf 0
address 77: m2 for leaf 0
......
address 142: m67 for leaf 0
-----------------------------------
address 143: m0 for leaf 1
address 144: m1 for leaf 1
address 145: m2 for leaf 1
......
address 210: m67 for leaf 1
-----------------------------------
...... 
-----------------------------------
address 1163: n0 for leaf 0
address 1164: n1 for leaf 0
address 1165: n2 for leaf 0
......
address 1230: n67 for leaf 0
-----------------------------------
address 1231: n0 for leaf 1
address 1232: n1 for leaf 1
address 1233: n2 for leaf 1
......
address 1298: n67 for leaf 1
-----------------------------------
......
-----------------------------------
......
address 2250: n67 for leaf 15
----------------------------------     


[For Tree 2]
address 2251: [a0 for split 0, lower 8 bits]
address 2252: [a0 for split 0, higher 8 bits]
......

Quiero leer el contenido de "m" en cierta hoja, y uso la ecuación para acceder a la memoria: (todo el índice está basado en 0)

address_index = 2251*(Tree_Index) + 75 + (node_index - 15)*68 + (m_index);

Por lo tanto, uso 3 registros de 3 contadores:

total_tree_cnt is the index of Tree.
now_i_1 is the index of nodes, (now_i_1 - 15) is the index of leaf(0~15).
leaf_cnt is the index of m(0~67).

Utilizo dos estados para leer los datos de la memoria, configuro "vip_rom_addr_out_1" en el estado_1 como se mencionó anteriormente, después de que se hayan activado 2 relojes de flanco ascendente, el FSM salta al estado_2 y se deben leer los datos, pero he comprobado el contenido de vip_rom_addr_out_1 y obtuvo la dirección incorrecta (0x24d), y los datos leídos de la ROM parecen provenir de la dirección 0.

No hay errores durante la compilación. Por eso creo que la velocidad de la multiplicación importa. Cualquier sugerencia será apreciada.

    
pregunta C. Peter

2 respuestas

1

Dos pensamientos:

  • Asegurarse de que puedes usar poderes de 2 (y una sugerencia para hacerlo);
  • Ayudando a la herramienta de síntesis.

A. Haciendo poderes de dos.

Desafortunadamente, un simple cambio en las potencias de dos te hace cambiar de 2228 a 4096 y de 68 a 128. Eso requeriría casi cuatro veces el rango de memoria ...

Podrías dividir 2228 en 2048 + 180 dando como resultado 2048 + 256, y dividir 68 en 64 + 4 (ya potencias de dos). Necesitará reorganizar sus datos y probar qué ecuación usar en base a leaf_data, por ejemplo:

if(leaf_data[...]<30) then 
     vip_rom_addr_out_1 = (2048*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;
else 
     vip_rom_addr_out_1 = base_adr+(256*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;
endif    

Las ecuaciones anteriores necesitan ser reelaboradas, el análisis necesita algo de trabajo. El código resultante será más complejo de entender, pero más rápido de ejecutar.

También tengo en cuenta que el número de entradas para leaf_cnt ya es una potencia de 2; podría reemplazar su 2228 * ... con (16 * 2 ^ n) * leaf_cnt y sumar con total_tree_cnt en su lugar.

Para reorganizar sus datos, escriba un pequeño programa de utilidad en el idioma que prefiera y valide su fórmula en ese programa (verificando los resultados conocidos para los valores de entrada dados).

B. Ayuda a la herramienta de síntesis.

Es realmente más eficiente escribir sus expresiones en términos de los bloques informáticos que espera en lugar de introducir una expresión compleja en la herramienta de síntesis.

Por ejemplo, no debes escribir:

if(leaf_data[...]<30) then 
     vip_rom_addr_out_1 = (2048*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;
else 
     vip_rom_addr_out_1 = base_adr+(256*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;
endif  

pero

vip_rom_addr_out_1a = (2048*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;
vip_rom_addr_out_1b = base_adr+(256*( {total_tree_cnt[5:0], 1'b0} )) +
    + 75 + (now_i_1 - 15)*68 + leaf_cnt;

if(leaf_data[...]<30) then 
     vip_rom_addr_out_1 = vip_rom_addr_out_1a;
else 
     vip_rom_addr_out_1 = vip_rom_addr_out_1b;
endif

Esta segunda alternativa indicará la herramienta de síntesis que espera que cree dos módulos de cómputo y un multiplexor que probablemente sea más eficiente que un gran bloque de lógica.

Factorizar su expresión también ayudará a reutilizar recursos, etc.:

leaf_offset=75 + (now_i_1 - 15)*68 + leaf_cnt;
vip_rom_addr_out_1a = (2048*( {total_tree_cnt[5:0], 1'b0} )) +
    + leaf_offset;
vip_rom_addr_out_1b = base_adr+(256*( {total_tree_cnt[5:0], 1'b0} )) +
    + leaf_offset;

Tenga en cuenta que no hay una estructura predefinida para una suma de tres términos, solo para dos. Por lo tanto, asegurarse de que solo suma dos términos a la vez ayuda a que la herramienta reconozca el sumador y establezca la prioridad. Si suma 4 términos, sumarlos dos por dos y luego el resultado de estos dos resultados intermedios.

Si algunos de los valores corresponden a una configuración que no cambia durante un tiempo, debería poder limitar su influencia negativa en la frecuencia (encerrándolos en un registro, indicando a su herramienta que suponga que la señal es estable para el análisis de tiempo, ...).

Estoy de acuerdo en que las herramientas optimizan, pero no tanto como pensarías para la síntesis de hardware. Después de la síntesis, asegúrese de que la herramienta haya creado los sumadores, multiplicadores, multiplexores, etc. esperados. De lo contrario, verifique la documentación de pragmas que puede agregar a su código fuente.

C. El mismo tipo de trabajo es necesario para la tubería. En lugar de definir lo anterior como resultados intermedios no sincronizados, tendrá que cronometrarlos (es posible que también se deban canalizar otras señales).

D. Sepa cuánto está por debajo de alcanzar los 50MHz y dónde pierde el tiempo de cálculo. Recuerdo que aceleré los circuitos por un factor de dos y reduje su tamaño en dos con técnicas como la anterior. La aceleración puede ser bastante alta si puedes introducir multiplicaciones con factores de dos (al final solo tienes unas pocas sumas y un multiplexor). Intente calcular la ganancia que puede lograr y determine si necesita canalización o no.

    
respondido por el le_top
0

¿Qué tan importante es que uses esas direcciones específicas y pongas todo eso en una RAM? Considere la posibilidad de dividir las cosas de manera diferente para que pueda reemplazar todas las constantes en esa ecuación con potencias de dos. Esto eliminará la necesidad de multiplicadores de hardware y podrá ejecutar la computación en un solo ciclo de reloj. Además, la partición del árbol en múltiples RAMs de bloques podría simplificar el cálculo de la dirección al eliminar algunas de las compensaciones que se agregan o restan.

    
respondido por el alex.forencich

Lea otras preguntas en las etiquetas