Multiplicateur non signé multicycle par décalage-addition

Prérequis : logique séquentielle, affectations non bloquantes^{iAffectation non bloquante Affectation <= du RTL séquentiel : le membre droit est évalué puis la mise à jour planifiée, permettant aux registres du même front de calculer à partir de l'ancien état. En savoir plus}, compteurs, décalages et additionneurs.

Réutiliser un additionneur sur plusieurs cycles

La multiplication non signée^{iNon signé Interprétation d'un motif de bits comme entier non négatif. Sur n bits, la plage va de 0 à 2^n−1 et peut différer de l'interprétation signée du même motif. En savoir plus} W bits est la somme des produits partiels sélectionnés par chaque bit de B.

Tout additionner simultanément exige beaucoup de logique. Ici, un seul additionneur est utilisé W fois : un compromis entre aire et débit. Une boucle RTL ne crée pas spontanément plusieurs cycles ; il faut des registres^{iRegistre Circuit stockant plusieurs bits d'état. Les registres synchrones du cours capturent leur entrée définie sur un front d'horloge. En savoir plus} d'état intermédiaire et une condition de fin.

P, l'accumulateur, et M, le multiplicande décalé, ont 2W bits ; Q, le multiplicateur décalé à droite, en a W. Initialisez P=0,M=zero-extend(A),Q=B. À chaque cycle de travail, ajoutez M à P si Q[0]=1, décalez M à gauche et Q à droite d'un bit.

Après W opérations, Q=0 et P est le produit complet. 2W bits suffisent car $(2^W-1)^2<2^{2W}$ et les sommes partielles non signées ne dépassent pas le produit final.

Pour A=13,B=11,W=4, les bits bas de Q sont 1,1,0,1. P suit 0→13→39→39→143 ; M utilisé vaut 13,26,52,104. Même à la troisième opération où Q[0]=0, décalages et compteur doivent avancer.

Chaque colonne montre l'état après capture de requête ou opération. La première initialise ; les quatre suivantes calculent. À la troisième opération, l'ancien bit bas de Q est nul : seul P reste constant, M et Q avancent.

Définir acceptation et achèvement

Une requête est acceptée au front montant^{iFront montant Instant où l'horloge passe de 0 à 1, distinct du niveau désignant tout l'intervalle CLK=1. En savoir plus} avec start=1 pendant idle. À t0, seules les entrées sont stockées. Les W opérations ont lieu de t1 à tW ; product et done deviennent valides après tW. La latence est W périodes, avec W+1 fronts si l'on inclut celui de départ.

start est ignoré lorsque busy=1, y compris au front d'achèvement où l'ancien busy vaut encore 1. La prochaine acceptation est donc au plus tôt tW+1 : intervalle minimal W+1 périodes. Maintenir start à 1 relance au prochain front idle ; l'appelant fournit généralement une impulsion adaptée à l'acceptation.

module mul_iter #(parameter int W = 8) (
  input  logic clk, rst, start,
  input  logic [W-1:0] a, b,
  output logic busy, done,
  output logic [2*W-1:0] product
);
  localparam int CW = (W <= 1) ? 1 : $clog2(W);
  localparam logic [CW-1:0] LAST = CW'(W-1);
  logic [CW-1:0] step;
  logic [2*W-1:0] acc, m, next_acc;
  logic [W-1:0] q;

  assign next_acc = acc + (q[0] ? m : {2*W{1'b0}});

  always_ff @(posedge clk) begin
    if (rst) begin
      busy <= 1'b0;
      done <= 1'b0;
      product <= '0;
      acc <= '0;
      m <= '0;
      q <= '0;
      step <= '0;
    end else begin
      done <= 1'b0;
      if (!busy) begin
        if (start) begin
          busy <= 1'b1;
          acc <= '0;
          m <= {{W{1'b0}}, a};
          q <= b;
          step <= '0;
        end
      end else begin
        acc <= next_acc;
        m <= m << 1;
        q <= q >> 1;
        if (step == LAST) begin
          product <= next_acc;
          busy <= 1'b0;
          done <= 1'b1;
        end else begin
          step <= step + 1'b1;
        end
      end
    end
  end
endmodule

Le contrat est W≥1 ; CW reste au moins 1 pour éviter un compteur de largeur nulle à W=1. Le reset synchrone actif haut prime sur une opération en cours. Après capture, changer a,b externes n'affecte pas m,q stockés. product ne change qu'au reset ou à l'achèvement. done est une impulsion d'une période, pas un valid maintenu jusqu'à consommation.

L'affectation finale est product<=next_acc, pas product<=acc. Les membres droits non bloquants lisent l'ancien état : acc seul omettrait le dernier produit partiel. Pour la même raison, écrire le décalage de q plus haut ne change pas le Q[0] actuel utilisé par next_acc.

Invariant de calcul et choix d'implémentation

Après k opérations :

Décomposer Q en partie paire et bit bas montre la conservation à l'étape suivante. À k=W, Q=0, donc P=AB. Cet invariant^{iInvariant Condition devant rester vraie dans toute exécution autorisée. Par exemple, l'occupation d'un FIFO de profondeur 4 reste toujours entre 0 et 4. En savoir plus} explique l'ordre accumulation/décalage plus clairement qu'un petit chronogramme seul.

Le chemin critique d'une opération comprend un additionneur 2W bits et la sélection d'entrée. Supprimer le symbole de multiplication ne garantit ni gain d'aire ni vitesse : comparez blocs DSP FPGA, synthèse et débit^{iDébit Nombre d'opérations acceptées ou terminées par unité de temps. Un pipeline peut l'augmenter sans réduire la latence d'une opération individuelle. En savoir plus} requis. Le module ne réalise ni fin anticipée, ni signé, ni backpressure de résultat ; le consommateur ne doit pas manquer done.

Testez 0,1,maximum et B avec seulement son bit haut à 1, ainsi que start et changements d'entrée pendant busy et annulation par reset. Le B à un seul bit haut révèle particulièrement l'oubli de la dernière accumulation.