關鍵詞:流水線,乘法器

硬件描述語言的一個突出優點就是指令執行的並行性。多條語句能夠在相同時鍾周期內並行處理多個信號數據。

但是當數據串行輸入時,指令執行的並行性並不能體現出其優勢。而且很多時候有些計算並不能在一個或兩個時鍾周期內執行完畢,如果每次輸入的串行數據都需要等待上一次計算執行完畢後才能開啟下一次的計算,那效率是相當低的。流水線就是解決多周期下串行數據計算效率低的問題。

流水線

流水線的基本思想是:把一個重複的過程分解為若幹個子過程,每個子過程由專門的功能部件來實現。將多個處理過程在時間上錯開,依次通過各功能段,這樣每個子過程就可以與其他子過程並行進行。

假如一個洗衣店內洗衣服的過程分為 4 個階段:取衣、洗衣、烘幹、裝櫃。每個階段都需要半小時來完成,則洗一次衣服需要 2 小時。

考慮最差情況,洗衣店內隻有一台洗衣機、一台烘幹機、一個衣櫃。如果每半小時送來一批要洗的衣服,每次等待上一批衣服洗完需要 2 小時,那麼洗完 4 批衣服需要的時間就是 8 小時。

圖示如下:

對這個洗衣店的裝備進行升級,一共引進 4 套洗衣服的裝備,工作人員也增加到 4 個,每個人負責一個洗衣階段。所以每批次的衣服,都能夠及時的被相同的人放入到不同的洗衣機內。由於時間上是錯開的,每批次的衣服都能被相同的人在不同的設備與時間段(半小時)內洗衣、烘幹和裝櫃。圖示如下。

可以看出,洗完 4 批衣服隻需要 3 個半小時,效率明顯提高。

其實,在 2 小時後第一套洗衣裝備已經完成洗衣過程而處於空閑狀態,如果此時還有第 5 批衣服的送入,那麼第一套設備又可以開始工作。依次類推,隻要衣服批次不停的輸入,4 台洗衣設備即可不間斷的完成對所有衣服的清洗過程。且除了第一批次洗衣時間需要 2 小時,後麵每半小時都會有一批次衣服清洗完成。

衣服批次越多,節省的時間就越明顯。假如有 N 批次衣服,需要的時間為 (4+N) 個半小時。

當然,升級後洗衣流程也有缺點。設備和工作人員的增加導致了投入的成本增加,洗衣店內剩餘空間也被縮小,工作狀態看起來比較繁忙。

和洗衣服過程類似,數據的處理路徑也可以看作是一條生產線,路徑上的每個數字處理單元都可以看作是一個階段,會產生延時。

流水線設計就是將路徑係統的分割成一個個數字處理單元(階段),並在各個處理單元之間插入寄存器來暫存中間階段的數據。被分割的單元能夠按階段並行的執行,相互間沒有影響。所以最後流水線設計能夠提高數據的吞吐率,即提高數據的處理速度。

流水線設計的缺點就是,各個處理階段都需要增加寄存器保存中間計算狀態,而且多條指令並行執行,勢必會導致功耗增加。

下麵,設計一個乘法器,並對是否采用流水線設計進行對比。


一般乘法器設計

前言

也許有人會問,直接用乘號 * 來完成 2 個數的相乘不是更快更簡單嗎?

如果你有這個疑問,說明你對硬件描述語言的認知還有所不足。就像之前所說,Verilog 描述的是硬件電路,直接用乘號完成相乘過程,編譯器在編譯的時候也會把這個乘法表達式映射成默認的乘法器,但其構造不得而知。

例如,在 FPGA 設計中,可以直接調用 IP 核來生成一個高性能的乘法器。在位寬較小的時候,一個周期內就可以輸出結果,位寬較大時也可以流水輸出。在能滿足要求的前提下,可以謹慎的用 * 或直接調用 IP 來完成乘法運算。

但乘法器 IP 也有很多的缺陷,例如位寬的限製,未知的時序等。尤其使用乘號,會為數字設計的不確定性埋下很大的隱瞞。

很多時候,常數的乘法都會用移位相加的形式實現,例如:

實例

A = A<<1 ;       //完成A * 2
A = (A<<1) + A ;   //對應A * 3
A = (A<<3) + (A<<2) + (A<<1) + A ; //對應A * 15

用一個移位寄存器和一個加法器就能完成乘以 3 的操作。但是乘以 15 時就需要 3 個移位寄存器和 3 個加法器(當然乘以 15 可以用移位相減的方式)。

有時候數字電路在一個周期內並不能夠完成多個變量同時相加的操作。所以數字設計中,最保險的加法操作是同一時刻隻對 2 個數據進行加法運算,最差設計是同一時刻對 4 個及以上的數據進行加法運算。

如果設計中有同時對 4 個數據進行加法運算的操作設計,那麼此部分設計就會有危險,可能導致時序不滿足。

此時,設計參數可配、時序可控的流水線式乘法器就顯得有必要了。

設計原理

和十進製乘法類似,計算 13 與 5 的相乘過程如下所示:

由此可知,被乘數按照乘數對應 bit 位進行移位累加,便可完成相乘的過程。

假設每個周期隻能完成一次累加,那麼一次乘法計算時間最少的時鍾數恰好是乘數的位寬。所以建議,將位寬窄的數當做乘數,此時計算周期短。

乘法器設計

考慮每次乘法運算隻能輸出一個結果(非流水線設計),設計代碼如下。

實例

module    mult_low
    #(parameter N=4,
      parameter M=4)
     (
      input                     clk,
      input                     rstn,
      input                     data_rdy ,  //數據輸入使能
      input [N-1:0]             mult1,      //被乘數
      input [M-1:0]             mult2,      //乘數

      output                    res_rdy ,   //數據輸出使能
      output [N+M-1:0]          res         //乘法結果
      );

    //calculate counter
    reg [31:0]           cnt ;
    //乘法周期計數器
    wire [31:0]          cnt_temp = (cnt == M)? 'b0 : cnt + 1'b1 ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            cnt    <= 'b0 ;
        end
        else if (data_rdy) begin    //數據使能時開始計數
            cnt    <= cnt_temp ;
        end
        else if (cnt != 0 ) begin  //防止輸入使能端持續時間過短
            cnt    <= cnt_temp ;
        end
        else begin
            cnt    <= 'b0 ;
        end
    end

    //multiply
    reg [M-1:0]          mult2_shift ;
    reg [M+N-1:0]        mult1_shift ;
    reg [M+N-1:0]        mult1_acc ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            mult2_shift    <= 'b0 ;
            mult1_shift    <= 'b0 ;
            mult1_acc      <= 'b0 ;
        end
        else if (data_rdy && cnt=='b0) begin  //初始化
            mult1_shift    <= {{(N){1'b0}}, mult1} << 1 ;  
            mult2_shift    <= mult2 >> 1 ;  
            mult1_acc      <= mult2[0] ? {{(N){1'b0}}, mult1} : 'b0 ;
        end
        else if (cnt != M) begin
            mult1_shift    <= mult1_shift << 1 ;  //被乘數乘2
            mult2_shift    <= mult2_shift >> 1 ;  //乘數右移,方便判斷
            //判斷乘數對應為是否為1,為1則累加
            mult1_acc      <= mult2_shift[0] ? mult1_acc + mult1_shift : mult1_acc ;
        end
        else begin
            mult2_shift    <= 'b0 ;
            mult1_shift    <= 'b0 ;
            mult1_acc      <= 'b0 ;
        end
    end

    //results
    reg [M+N-1:0]        res_r ;
    reg                  res_rdy_r ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            res_r          <= 'b0 ;
            res_rdy_r      <= 'b0 ;
        end  
        else if (cnt == M) begin
            res_r          <= mult1_acc ;  //乘法周期結束時輸出結果
            res_rdy_r      <= 1'b1 ;
        end
        else begin
            res_r          <= 'b0 ;
            res_rdy_r      <= 'b0 ;
        end
    end

    assign res_rdy       = res_rdy_r;
    assign res           = res_r;

endmodule

testbench

實例

`timescale 1ns/1ns

module test ;
    parameter    N = 8 ;
    parameter    M = 4 ;
    reg          clk, rstn;
 
   //clock
    always begin
        clk = 0 ; #5 ;
        clk = 1 ; #5 ;
    end

   //reset
    initial begin
        rstn      = 1'b0 ;
        #8 ;      rstn      = 1'b1 ;
    end

    //no pipeline
    reg                  data_rdy_low ;
    reg [N-1:0]          mult1_low ;
    reg [M-1:0]          mult2_low ;
    wire [M+N-1:0]       res_low ;
    wire                 res_rdy_low ;

    //使用任務周期激勵
    task mult_data_in ;  
        input [M+N-1:0]   mult1_task, mult2_task ;
        begin
            wait(!test.u_mult_low.res_rdy) ;  //not output state
            @(negedge clk ) ;
            data_rdy_low = 1'b1 ;
            mult1_low = mult1_task ;
            mult2_low = mult2_task ;
            @(negedge clk ) ;
            data_rdy_low = 1'b0 ;
            wait(test.u_mult_low.res_rdy) ; //test the output state
        end
    endtask

    //driver
    initial begin
        #55 ;
        mult_data_in(25, 5 ) ;
        mult_data_in(16, 10 ) ;
        mult_data_in(10, 4 ) ;
        mult_data_in(15, 7) ;
        mult_data_in(215, 9) ;
    end

    mult_low  #(.N(N), .M(M))
    u_mult_low
    (
      .clk              (clk),
      .rstn             (rstn),
      .data_rdy         (data_rdy_low),
      .mult1            (mult1_low),
      .mult2            (mult2_low),
      .res_rdy          (res_rdy_low),
      .res              (res_low));

   //simulation finish
   initial begin
      forever begin
         #100;
         if ($time >= 10000)  $finish ;
      end
   end

endmodule // test

仿真結果如下。

由圖可知,輸入的 2 個數據在延遲 4 個周期後,得到了正確的相乘結果。算上中間送入數據的延遲時間,計算 4 次乘法大約需要 20 個時鍾周期。

流水線乘法器設計

下麵對乘法執行過程的中間狀態進行保存,以便流水工作,設計代碼如下。

單次累加計算過程的代碼文件如下(mult_cell.v ):

實例

module    mult_cell
    #(parameter N=4,
      parameter M=4)
    (
      input                     clk,
      input                     rstn,
      input                     en,
      input [M+N-1:0]           mult1,      //被乘數
      input [M-1:0]             mult2,      //乘數
      input [M+N-1:0]           mult1_acci, //上次累加結果

      output reg [M+N-1:0]      mult1_o,     //被乘數移位後保存值
      output reg [M-1:0]        mult2_shift, //乘數移位後保存值
      output reg [N+M-1:0]      mult1_acco,  //當前累加結果
      output reg                rdy );

    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            rdy            <= 'b0 ;
            mult1_o        <= 'b0 ;
            mult1_acco     <= 'b0 ;
            mult2_shift    <= 'b0 ;
        end
        else if (en) begin
            rdy            <= 1'b1 ;
            mult2_shift    <= mult2 >> 1 ;
            mult1_o        <= mult1 << 1 ;
            if (mult2[0]) begin
                //乘數對應位為1則累加
                mult1_acco  <= mult1_acci + mult1 ;  
            end
            else begin
                mult1_acco  <= mult1_acci ; //乘數對應位為1則保持
            end
        end
        else begin
            rdy            <= 'b0 ;
            mult1_o        <= 'b0 ;
            mult1_acco     <= 'b0 ;
            mult2_shift    <= 'b0 ;
        end
    end

endmodule

頂層例化

多次模塊例化完成多次累加,代碼文件如下(mult_man.v ):

實例

module    mult_man
    #(parameter N=4,
      parameter M=4)
    (
      input                     clk,
      input                     rstn,
      input                     data_rdy ,
      input [N-1:0]             mult1,
      input [M-1:0]             mult2,

      output                    res_rdy ,
      output [N+M-1:0]          res );

    wire [N+M-1:0]       mult1_t [M-1:0] ;
    wire [M-1:0]         mult2_t [M-1:0] ;
    wire [N+M-1:0]       mult1_acc_t [M-1:0] ;
    wire [M-1:0]         rdy_t ;

    //第一次例化相當於初始化,不能用 generate 語句
    mult_cell      #(.N(N), .M(M))
    u_mult_step0
    (
      .clk              (clk),
      .rstn             (rstn),
      .en               (data_rdy),
      .mult1            ({{(M){1'b0}}, mult1}),
      .mult2            (mult2),
      .mult1_acci       ({(N+M){1'b0}}),
      //output
      .mult1_acco       (mult1_acc_t[0]),
      .mult2_shift      (mult2_t[0]),
      .mult1_o          (mult1_t[0]),
      .rdy              (rdy_t[0]) );

    //多次模塊例化,用 generate 語句
    genvar               i ;
    generate
        for(i=1; i<=M-1; i=i+1) begin: mult_stepx
            mult_cell      #(.N(N), .M(M))
            u_mult_step
            (
              .clk              (clk),
              .rstn             (rstn),
              .en               (rdy_t[i-1]),
              .mult1            (mult1_t[i-1]),
              .mult2            (mult2_t[i-1]),
              //上一次累加結果作為下一次累加輸入
              .mult1_acci       (mult1_acc_t[i-1]),
              //output
              .mult1_acco       (mult1_acc_t[i]),                                      
              .mult1_o          (mult1_t[i]),  //被乘數移位狀態傳遞
              .mult2_shift      (mult2_t[i]),  //乘數移位狀態傳遞
              .rdy              (rdy_t[i]) );
        end
    endgenerate

    assign res_rdy       = rdy_t[M-1];
    assign res           = mult1_acc_t[M-1];

endmodule

testbench

將下述仿真描述添加到非流水乘法器設計例子的 testbench 中,即可得到流水式乘法運算的仿真結果。

2 路數據為不間斷串行輸入,且帶有自校驗模塊,可自動判斷乘法運算結果的正確性。

實例

    reg          data_rdy ;
    reg [N-1:0]  mult1 ;
    reg [M-1:0]  mult2 ;
    wire                 res_rdy ;
    wire [N+M-1:0]       res ;

    //driver
    initial begin
        #55 ;
        @(negedge clk ) ;
        data_rdy  = 1'b1 ;
        mult1  = 25;      mult2      = 5;
        #10 ;      mult1  = 16;      mult2      = 10;
        #10 ;      mult1  = 10;      mult2      = 4;
        #10 ;      mult1  = 15;      mult2      = 7;
        mult2      = 7;   repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 1;   repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 15;  repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 3;   repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 11;  repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 4;   repeat(32)    #10   mult1   = mult1 + 1 ;
        mult2      = 9;   repeat(32)    #10   mult1   = mult1 + 1 ;
    end

    //對輸入數據進行移位,方便後續校驗
    reg  [N-1:0]   mult1_ref [M-1:0];
    reg  [M-1:0]   mult2_ref [M-1:0];
    always @(posedge clk) begin
        mult1_ref[0] <= mult1 ;
        mult2_ref[0] <= mult2 ;
    end

    genvar         i ;
    generate
        for(i=1; i<=M-1; i=i+1) begin
            always @(posedge clk) begin
            mult1_ref[i] <= mult1_ref[i-1];
            mult2_ref[i] <= mult2_ref[i-1];
            end
        end
    endgenerate
   
    //自校驗
    reg  error_flag ;
    always @(posedge clk) begin
        # 1 ;
        if (mult1_ref[M-1] * mult2_ref[M-1] != res && res_rdy) begin
            error_flag <= 1'b1 ;
        end
        else begin
            error_flag <= 1'b0 ;
        end
    end

    //module instantiation
    mult_man  #(.N(N), .M(M))
     u_mult
     (
      .clk              (clk),
      .rstn             (rstn),
      .data_rdy         (data_rdy),
      .mult1            (mult1),
      .mult2            (mult2),
      .res_rdy          (res_rdy),
      .res              (res));

仿真結果

前幾十個時鍾周期的仿真結果如下。

由圖可知,仿真結果判斷信號 error_flag 一直為 0,表示乘法設計正確。

數據在時鍾驅動下不斷串行輸入,乘法輸出結果延遲了 4 個時鍾周期後,也源源不斷的在每個時鍾下無延時輸出,完成了流水線式的工作。

相對於一般不采用流水線的乘法器,乘法計算效率有了很大的改善。

但是,流水線式乘法器使用的寄存器資源也大約是之前不采用流水線式的 4 倍。

所以,一個數字設計,是否采用流水線設計,需要從資源和效率兩方麵進行權衡。

源碼下載

Download