東工大 情報工学科 情報実験第四 「組み込みシステム」& MieruEMBシステム
Verilog HDLに関する補足説明 シンプルな命令キャッシュの追加 (2011-10-23版)


ここでは,MieruEMB System V1.0 (2011-10-05版)のVerilog HDLを修正して,シンプルな命令キャッシュを 追加する方法を掲載します.

file name: define.v
   25  /* Instruction Processing Stage definition                                                            */
   26  /******************************************************************************************************/
   27  `define CPU_START 5'h00
   28  `define CPU_IF0   5'h01
   29  `define CPU_IF1   5'h02
   30  `define CPU_IF2   5'h03
   31  `define CPU_IF3   5'h04
   32  `define CPU_IF4   5'h05
   33  `define CPU_ID    5'h06
   34  `define CPU_RF    5'h07
   35  `define CPU_EX    5'h08
   36  `define CPU_MA0   5'h09
   37  `define CPU_MA1   5'h0a
   38  `define CPU_MA2   5'h0b
   39  `define CPU_MA3   5'h0c
   40  `define CPU_MA4   5'h0d
   41  `define CPU_WB    5'h0e
   42  `define CPU_WCNT  5'h0f
   43  `define CPU_HALT  5'h10
   44  `define CPU_ERROR 5'h11

プロセッサMIPSCOREの命令処理のステージ定義が記述されています. この版に含まれるプロセッサは,(パイプライン処理をおこなわない)マルチサイクル版です.

ロード命令の場合には,IF0, IF1, IF2, IF3, IF4, ID, RF, EX, MA0, MA1, MA2, MA3, MA4, WB というステートを経由して, 1つの命令を処理するので,ロード命令の処理には14サイクルを必要とします. データメモリにアクセスしない加算命令では, IF0, IF1, IF2, IF3, IF4, ID, RF, EX, WB というステートを経由して,9サイクルを必要とします. このように,標準のプロセッサとしては(拡張や改良の余地のある)とても遅いものを採用しています.

命令キャッシュを搭載することで,これにヒットする場合には,IF1, IF2, IF3, IF4 というステージをスキップできる ようになります. データメモリにアクセスしない加算命令では,命令キャッシュにヒットした場合には, IF0, ID, RF, EX, WB という5サイクルに短縮されます. 命令キャッシュにミスした場合には,9サイクルと命令キャッシュがない場合と同じです.

file name: MipsCore.v
  161  /* Instruction Cache Tag Array                                                                        */
  162  /******************************************************************************************************/
  163  module IC_TAG(CLK, IDX, DIN, WE, DOUT);
  164      parameter DEPTH = 1024;
  165      input              CLK, WE;
  166      input      [`ADDR] DIN;
  167      input        [9:0] IDX;  // index
  168      output reg [`ADDR] DOUT;
  169      
  170      reg [`ADDR] mem [DEPTH-1:0];
  171    
  172      always @(negedge CLK) DOUT <= mem[IDX];
  173      always @(posedge CLK) if(WE) mem[IDX] <= (DIN | 2'b11); // use lower two bits as valid bit.
  174  endmodule
  175  
  176  /* Instruction Cache Data Array                                                                       */
  177  /******************************************************************************************************/
  178  module IC_DAT(CLK, IDX, DIN, WE, DOUT);
  179      parameter DEPTH = 1024;
  180      input             CLK, WE;
  181      input      [31:0] DIN;
  182      input       [9:0] IDX;  // index
  183      output reg [31:0] DOUT;
  184      
  185      reg [31:0] mem [DEPTH-1:0];
  186      
  187      always @(negedge CLK) DOUT <= mem[IDX];
  188      always @(posedge CLK) if(WE) mem[IDX] <= DIN;
  189  endmodule
  190  

MipsCore.vに,命令キャッシュのタグとデータのためのモジュールの記述を追加します. エントリ数は parameter で指定している1024です. シンプルなダイレクトマップ方式のキャッシュです.

タグとして,プログラムカウンタの値をそのまま格納することにします.このため,166行目,168行目のデータ幅は [`ADDR] となります. 本当は,インデックスの部分は必要ないので, タグのビット数は削減できます.

タグの下位2ビットをvalidビットとして利用することにしているため,明示的にvalidビットはありません. そのため,有効な値を書き込む際に,173行目で,下位の2ビットを1に設定します.

  191  /******************************************************************************************************/
  192  /* MipsCore: 32bit-MIPS multicycle processor                                                          */
  193  /******************************************************************************************************/
  194  module MIPSCORE(CLK, RST_X, ADDR, DATA_IN, DATA_OUT, WE);
  195      input              CLK, RST_X;
  196      input  [7:0]       DATA_IN;
  197      output [7:0]       DATA_OUT;
  198      output [`ADDR]     ADDR;

  253      /**************************************************************************************************/
  254      /* Sub module declaration                                                                         */
  255      /**************************************************************************************************/
  256      wire [`ADDR] ic_tag;
  257      wire [31:0]  ic_dat;
  258      IC_TAG ict(.CLK(CLK), .IDX(pc[11:2]), .DIN(pc),      .WE(state==`CPU_EX), .DOUT(ic_tag)); 
  259      IC_DAT icd(.CLK(CLK), .IDX(pc[11:2]), .DIN(inst_ir), .WE(state==`CPU_EX), .DOUT(ic_dat));
  260      
  261      DIVUNIT du(.CLK(CLK), .RST_X(RST_X), .INIT(DIVMULINIT), .SIGNED(EXSIGNED),
  262                 .A(GPRREADDT0), .B(GPRREADDT1), .RSLT(DURSLT), .BUSY(DUBUSY));
  263  
  264      MULUNIT mu(.CLK(CLK), .RST_X(RST_X), .INIT(DIVMULINIT), .SIGNED(EXSIGNED),
  265                 .A(GPRREADDT0), .B(GPRREADDT1), .RSLT(MURSLT), .BUSY(MUBUSY));
  266  
  267      GPR gpr(.CLK(CLK), .REGNUM0(GPRNUM0), .REGNUM1(GPRNUM1), .DIN0(GPRWRITEDT0), .DIN1(GPRWRITEDT1),
  268              .WE0(GPRWE0), .WE1(GPRWE1), .DOUT0(GPRREADDT0), .DOUT1(GPRREADDT1));
  269  
  270      MIPSCP0 cp0(.CLK(CLK), .RST_X(RST_X), .REG_NUM(CPRNUM), .REG_IN(CPRWRITEDT), .REG_WE(CPRWE),
  271                  .REG_OUT(CPRREADDT), .EXC_SET(CPEXCSET), .EXC_CLR(CPEXCCLR), .EXC_ACK(CPEXCACK),
  272                  .EXC_CODE(CPEXCCODE), .EXC_EPC(CPEXCEPC), .EXC_BD(CPEXCBD),
  273                  .EXC_OCCUR(CPEXCOCCUR), .EXC_NPC(CPEXCNPC));

プロセッサであるモジュールMIPSCOREです.命令キャッシュを追加するために,このモジュールを修正します.

256行から259行を追加します. 256行目と257行目で,命令キャッシュの出力となるワイヤを定義しています. 先に示した命令キャッシュのタグとデータのモジュールを258行目,259行目で生成しています.

これらのキャッシュのインデックスには,ダイレクトマップ方式なので,pc[11:2]を利用しています. これらのキャッシュへの書き込みですが,state==`CPU_EX のサイクルにて,フェッチした命令の プログラムカウンタと命令を書き込む仕様としています.

file name: MipsCore.v
  275      /**************************************************************************************************/
  276      /* Mips::proceedstate()                                                                           */
  277      /**************************************************************************************************/
  278      wire icache_hit = ((pc|2'b11)==ic_tag);
  279      always @(posedge CLK or negedge RST_X) begin
  280          if(!RST_X)                                   state <= `CPU_START;
  281          else if(~CPUEXE || state==`CPU_HALT)         state <= state;        
  282          else if(exec_delay && delay_npc==`HALT_ADDR) state <= `CPU_HALT;
  283          else if(state==`CPU_IF0 && icache_hit)       state <= `CPU_ID;    // icache hit!
  284          else if(state==`CPU_EX &&  EXBUSY)           state <= state;
  285          else if(state==`CPU_EX && ~EXBUSY)           state <= (inst_attr & `LDST) ? `CPU_MA0 : `CPU_WB;
  286          else if(state==`CPU_WB)                      state <= `CPU_IF0;
  287          else                                         state <= state + 1;
  288      end
  289  
  290      /**************************************************************************************************/
  291      /* Mips:: instruction fetch stage and memory access address generation                            */
  292      /**************************************************************************************************/
  293      // inst_eaddr is incremented on MA0, MA1, and MA2 stage
  294      assign ADDR = (state == `CPU_IF0)                      ? (pc & ~'h3)        :
  295                    (state == `CPU_IF1)                      ? (pc & ~'h3) | 2'h1 :
  296                    (state == `CPU_IF2)                      ? (pc & ~'h3) | 2'h2 :
  297                    (state == `CPU_IF3)                      ? (pc & ~'h3) | 2'h3 :
  298                    (state >= `CPU_MA0 && state <= `CPU_MA3) ? inst_eaddr : 0;
  299                    
  300      always @( posedge CLK or negedge RST_X ) begin
  301          if(!RST_X) inst_pc <= 0;
  302          else if(CPUEXE) begin
  303              if     (state==`CPU_IF0)  begin
  304                  inst_pc <= pc;
  305                  inst_ir <= ic_dat; // use icache output data
  306              end
  307              if     (state==`CPU_IF1)  inst_ir[ 7: 0]  <= DATA_IN;
  308              else if(state==`CPU_IF2)  inst_ir[15: 8]  <= DATA_IN;
  309              else if(state==`CPU_IF3)  inst_ir[23:16]  <= DATA_IN;
  310              else if(state==`CPU_IF4)  inst_ir[31:24]  <= DATA_IN;
  311          end
  312      end

プロセッサの状態stateを変更する部分を修正します. 278行と283行を追加します.すなわち,命令キャッシュがヒットした場合には,IF0からIDステージへと遷移する ように変更しています.

また,命令フェッチステージの303行から306行を変更します. IF0ステージでは,プログラムカウンタをinst_pcに格納する処理のみをおこなっていましたが, 命令キャッシュの出力を inst_irに格納しています(305行).キャッシュにヒットする場合には,これが正しい 命令なので,IDステージ進めばただしい命令を利用できます. 一方,命令キャッシュにミスした場合には,IF1からIF4のステージでinst_irを上書きするので,やはり,正しい 命令をフェッチすることができます.

このように,40行程度の追加でシンプルな命令キャッシュが追加できました.

このプロセッサでqn24b(N-queensの解の数を求めるプログラム)を動かしてみました.
開発キットには130_qn24bのディレクトリにソースコードがあります. gcc version 4.3.6 (Buildroot 2011.08), 最適化オプションO2でコンパイルして, N=13を実行したところ,実行時間は 17.79秒でした.
命令キャッシュがない版では,29.70秒ですので,命令キャッシュの導入により,67%の高速化を達成しています.

ここで説明した命令キャッシュには,多少の問題があります. ハードウェアリセットをおこなわずに,SDカードを交換して,別のプログラムを動かそうとすると 正しく動作しません.その理由と解決方法を考えてみて下さい.


Copyright(c) 2011 Tokyo Tech Kise Laboratory. All rights reserved.