contar cero líder en camino de datos de un solo ciclo

Question

Como todos ustedes sabrán que la instrucción de MIPS soportes conjunto clz (recuento cero inicial) de la siguiente manera:

  

clz $ t0, $ t1 recuento de los ceros iniciales t0 = # de ceros a la izquierda en t1

Estoy escribiendo una única ruta de datos de ciclo en Verilog y estaba preguntando lo que la ALU necesita ayuda con el fin de que haga esto ... alguna idea ??

Answer 1

He aquí un posible enfoque (estoy ignorando el caso de una entrada de 0, que es probablemente el mejor tratado como un caso especial):

• El número de ceros a la izquierda en un número de 32 bits es o bien:
  • el número de ceros a la izquierda en los bits de la parte superior 16, si cualquiera de los bits de la parte superior 16 no son cero; o
  • 16, más el número de ceros a la izquierda en los 16 bits inferiores, si los bits de la parte superior 16 son todos cero
• Que da el bit superior del número 5 bits (ignorando el caso especial de una entrada de 0 ...).
• Ahora tiene que encontrar el número de ceros en un número de 16 bits, por lo que se aplica el mismo principio de nuevo.
• etc.

En Verilog, podría ser algo como esto:

result[4] = (value[31:16] == 16'b0);
val16     = result[4] ? value[15:0] : value[31:16];
result[3] = (val16[15:8] == 8'b0);
val8      = result[3] ? val16[7:0] : val16[15:8];
result[2] = (val8[7:4] == 4'b0);
val4      = result[2] ? val8[3:0] : val8[7:4];
result[1] = (val4[3:2] == 2'b0);
result[0] = result[1] ? ~val4[1] : ~val4[3];

Answer 2

La implementación más simple que puedo pensar (no muy optimizado) está comprobando la palabra contra 32 (en el caso de 32 bits), máscaras más largo en primer lugar, decidir que se ajusta primero y devolver su número.

Algo así como (pseudocódigo):

if word == 0: return 32
elsif (word & 1) == 0: return 31
elsif (word & 3) == 0: return 30

etc.

Answer 3

construir una unidad clz16 que mira a 16 bits, y tiene un resultado de 4 bits (0..15) y la salida 'allzero'. Ponga dos de ellos juntos para hacer clz32, se necesita un multiplexor para seleccionar los 4 bits más bajos y un poco de lógica para los bits superiores 2 de salida.

El clz16 está hecho de dos clz8 de la misma manera. El clz8 está hecho de dos clz4. El clz4 está a sólo tres funciones booleanas de <= 4 entradas, por lo que no importa mucho cómo lo hace, sintetizador hervirá se reduce a unos pocos puertas.

Este enfoque jerárquico es más grande que la solución de Mateo Slattery con los multiplexores en cascada, pero probablemente no por mucho (que no necesita las amplias puertas para cambiar los multiplexores), y creo que permite un apoyo inferior. retrasar. Ambos enfoques escala bien a los tamaños más grandes (por ejemplo 64, 128 bits) con prop demora. a log2 (n).