compter un zéro dans datapath cycle unique

Question

Comme vous le savez peut que le jeu d'instructions MIPS prend en charge clz (compter zéro) comme suit:

  

clz t0 $, zéros $ count t1 t0 = Nombre de zéros non significatifs dans t1

Je suis en train d'écrire un seul cycle datapath en Verilog et me demandais ce que l'ALU doit prendre en charge pour que je fasse cela ... des idées ??

Answer 1

Voici une approche possible (j'ignore le cas d'une entrée de 0, ce qui est probablement mieux traitée comme un cas particulier):

• Le nombre de zéros principaux dans un nombre de 32 bits est soit:
  • le nombre de zéros de tête dans les 16 bits supérieurs, le cas échéant des 16 bits supérieurs sont non-zéro; ou
  • 16, plus le nombre de zéros de tête dans les 16 bits inférieurs, si les 16 bits supérieurs sont tous égaux à zéro
• Cela donne le bit haut du résultat 5 bits (en ignorant le cas particulier d'une entrée de 0 ...).
• Maintenant, vous devez trouver le nombre de zéros non significatifs dans un certain nombre de 16 bits, vous devez donc appliquer à nouveau le même principe.
• etc.

Dans Verilog, il pourrait ressembler à ceci:

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 simple mise en œuvre que je peux penser (pas très optimisé) vérifie le mot contre 32 (en cas de 32 bits), la plus longue des masques en premier lieu, de décider qui correspond à la première et en retournant son numéro.

Quelque chose comme (pseudo-code):

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

etc.

Answer 3

Construire une unité de clz16 qui porte sur 16 bits, et dispose d'un résultat de 4 bits (0..15) et de sortie « allzero ». Mettez deux de ces ensemble pour faire clz32, vous avez besoin d'un MUX pour sélectionner les 4 bits inférieurs et un peu de logique pour les 2 bits de sortie supérieur.

Le clz16 est composé de deux clz8 de la même manière. Le clz8 est composé de deux clz4. Le clz4 est à seulement trois fonctions booléennes <= 4 entrées, donc il n'a pas beaucoup d'importance comment vous le faites, synthé bouillir jusqu'à quelques portes.

Cette approche hiérarchique est plus grande que la solution de Matthew Slattery avec les muxes montés en cascade, mais probablement pas par beaucoup (il n'a pas besoin de larges portes pour changer les muxes), et je crois qu'il permet à un appui vertical inférieur. retard. Les deux approches échelle bien plus grandes tailles (64, 128 par exemple bits) avec accessoire de retard. à log2 (n).