github.com においた。

本記事の全体的な言い訳だが、2018/9月の末くらいからcomputer architectureの勉強始めたので、ところどころ言葉の使い方があやしい部分があるかもしれない(というかある)。そこは多めに見てくだせい👀

特徴

cache込みで5段pipeline実装(Fetch, Decode, Calculate, MemRead, RegiterWriteBack) (virtual memoryおよび、TLB(Translation Lookaside Buffer)は未実装¹。)
VHDLで実装
architectureはmips(次節のreferenceの1番目を種本としている) risc-vにしなかったのは、そもそもその存在を知らなかったから( ^ω^ )
add, sub, and, or, slt, addi, lw, sw, beq, j, (andi, ori, slti, bne) あたりのinstructionでうまくいく(乗算、除算は未実装)
GHDL + GtkWaveを用いて、testcaseがすべて通ることを確認。 (実機ではまだ動作確認できてないので、これから確かめます😅)

reference

Digital Design Computer Architecture 7章を下敷きにしてる。ただし、この本ではsingle cycle processorの実装までしかない(pipelineの解説はされてる)ので、pipeline化は自力実装。今回、7章の中にあるmipstest.asmを通すことを目標とした(tests/memfile_tb.vhdlに相当)が、このtestcaseではstallが起こらないので、stall_lw_add_tb.vhdlにて別個にstall実装がうまく行っているかどうかのtestbenchを別途書いている
コンピュータアーキテクチャ-電子情報通信レクチャーシリーズこちらはVHDLや、System Verilog実装はないが、かなり高度なことまで書かれていると思う
Computer Organization and Design MIPS Edition パタヘネ本主に、cacheについて参考にした。
Verilog HDL&VHDLテストベンチ記述の初歩 testbench書き方わからなかったので、この本見て参考にした

このブログはqiitaと違って、感想をかくための場所にしているので、どこらへんで困った😥 かと、よかったところ💪を書いていく。

Note) microarchitectureの基本から細かく説明しないので、もし本記事の前提知識を得たい方は、Digital Design Computer Architecture の5章辺りまでがわかりやすい。 mipsの仕様については、自分メモだが、https://qiita.com/knknkn1162/private/3f65ab4c5c30d3b9a5b3 においてる(著作権の関係でprivateです)

全体の構成図

https://twitter.com/knknkn26918/status/1069507872239702016 に汚いスケッチがある (j instruction はFetch Stageの1段で終わるようにしているので、メモが間違い) あるいは、datapath.vhdlを見る。

迷った所

Stateをどうするか？

最終的に、D FlipFlopのenable(または、syncronous reset)をON, OFFをcontrolするためのFSMを構成しさえすれば良いんだ、ということに着目して、正常系と異常系のStateに分離した。つまり、

-- pkg/state_pkg.vhdl
type flopen_statetype is (
    ResetS, LoadS, SuspendS, NormalS, ErrorS
);

みたいな感じにした。ResetS, LoadSはInitializationのときのモード。SuspendSはdata cacheおよび、instruction cacheのcache missが生じたときに突入するモード。controller/flopen_controller.vhdlにて、D-FlipFlopのenableおよび、syncronous reset(**_clr signalと定義されている)を管理、制御している。

以下、試行錯誤した部分：

Digital Design Computer Architecture 7章のmulti-cycle processorでは、FetchS, DecodeS, AddiCalcSなどのStateを定義してFSMを構成していく感じだったので、最初その方針でpipeline実装を行ったが、かなり苦しい実装となった。 pipeline化した場合、カエルの合唱の輪唱のように命令がn重に並列に走るので、上記の方針で行くと、stateの状態空間のn次元のものを管理する必要がある。これは、stallやforwardingの実装をする場合すごく大変だった。

(実は1度目その方針で、 https://github.com/knknkn1162/vhdl_sample/tree/pipeline-3/src/mips にてsandbox的に実装してみたが、controller部分(controller.vhdl)が本当にごちゃごちゃしてしまって残念な感じになってしまった。)

instructionごとにStageの段数が異なる場合の影響

Digital Design Computer Architectureとは異なり[^pipeline_n]、instructionごとにpipelineの段数を可変としている。例えば、ロード命令(lw)では、

Fetch -> Decode -> Calc(Addressの計算) -> Data-Cache Read -> Register WriteBack

の5段としている。一方、addiや、R-type instructionでは、

Fetch -> Decode -> Calc -> Register Writeback

の4段構成である。

こうすることの影響としては、何も考えずに組むとRegister WriteBackの部分のStageが衝突する。

例えば、

lw $s0, 8($0)
addi $t1, $s1, $0

の場合、なんの対策もしなかったら、

time(CLK)	1	2	3	4	5
lw	Fetch	Decode	Calc	Data-Cache Read	Register WriteBack
addi		Fetch	Decode	Calc	Register Writeback

で5 CLK目に衝突する。あかん。ただし、衝突するのはここのstageのみなので、逐次的にRegisterに値をWriteBackするようにcontrolすれば良い。結果的に、[component/regw_buffer.vhdl] のように逐次的にRegiterにデータを書き込むようにすることで解決した。(ただ、これはmips architectureに依存するかもしれない)

キャッシュの実装

最も基本的なキャッシュであるdirect mapped cacheを採用し、実装した。data cache, instruction cacheともに、 tag: 20bit, index: 7bit, cache lineを8line(2³)として²実装してる(pkg/cache_pkg.vhdlがCONST値の定義場所、data cacheでは、ここらへんに実体を定義してる。instruction cacheでも似たような感じの実装) memoryはmem.vhdlと名が付いているが、L2 cacheかもしれない。

注意) virtual memoryやTLB(Translation Lookaside Buffer)は時間の都合上、実装してない。

コンピュータアーキテクチャ-電子情報通信レクチャーシリーズや Computer Organization and Design MIPS Edition のCh5.3 The Basics of Caches を参考にした。そんなにムズくないやろ、と思っていたら、以下のことを考慮に入れる必要があり、結構実装に時間がかかってしまった：

1: instruction cacheはRead onlyなのに対して、data cacheはRead/Writeなので、2つのキャッシュの実装が少し異なるのを考慮する必要がある。これはまぁ難しい部分ではなかったが、ちょっと頭が混乱する部分だったので、実装に時間がかかった。

2: cache missが起こった場合、cache(instr_cache.vhdl or data_cache.vhdl) とmemory(mem.vhdl)³ のやり取りをどのように実装するか？

やり取りの制御は、controller/mem_cache_controller.vhdl に一任した。

プロトコルは、コンピュータアーキテクチャ-電子情報通信レクチャーシリーズの5.2.1を素直に採用した。つまり、

addressにアクセス(Read or Write)したらcache_missが発生
[古いキャッシュのデータをmemoryに移す(追い出し)]
memory内の必要な部分をreadする
新しいデータをキャッシュに書き込む(再コピー)

というフロー。それぞれの段階で1 CLK消費するので、cache missが発生したら、最大4 CLK遅延する。ただし、instruction cache(Read only のcacheなので)や、data cacheの特殊な場合⁴は2番目が不要になるので、3CLK分の遅延のみですむ。

3: instruction cacheとdata cacheが同時にcache missを起こしてしまった場合どうするか?( pipeline化しているなので、十分に起こりうる)

これは実装している最中に気づいた。結果的に、controller/mem_idcache_controller.vhdl で制御を行なっている。

なんでこれが問題なのかというと、instruction cacheとdata cacheが同時にcache missを起こしてしまった場合、上記のプロトコルの2番目、3番目が競合するから。

これを解消するため、instruction cache missとdata cache missを controller/mem_idcache_controller.vhdl にて1 CLKずらした。ずらして、更にこの部分自体をpipeline化すれば、5 CLKの遅延ですむ。

D-flipflopを用いて適切に信号を遅延させる

-- datapath.vhdl を少し改変
  reg_pc0 : flopr_en_clr generic map (N=>32)
  port map (
    clk => clk, rst => rst, en => decode_en, clr => decode_clr,
    a => pc0,
    y => pc1
  );

  -- (skip)

  brplus0 <= immext0(29 downto 0) & "00"
  ja0 <= pc0(31 downto 28) & instr(25 downto 0) & "00";
  br4 <= std_logic_vector(unsigned(brplus0) + unsigned(pc1) + 4);
  pc4 <= std_logic_vector(unsigned(pc0) + 4);

  pc_br_mux2 : mux4 generic map (N=>32)
  port map (
    d00 => pc4,
    d01 => br4,
    d10 => ja0,
    d11 => pc4, -- dummy
    s => decode_pc_br_ja_s,
    y => pcnext0
  );

pcはprogram counterです。ここで問題にしたいのは、上記のコードでpc0とpc1はなぜ使い分ける必要があるか？という所。簡単に言うと、beq, bneの分岐命令は(Fetch Stageでなく)Decode Stageにてbranch takenされるかどうか決定されるから。なので、br4 <= std_logic_vector(unsigned(brplus0) + unsigned(pc0) + 4);とすると、

beq $0, $0, 1
addi $s0, $0, 5
addi $s1, $0, 6
addi $s2, $0, 7

を実行すると、本来addi $s1, $0, 6に飛ぶはずが、4番目のaddi $s2, $0, 7に飛んでしまうことになりだめ。

同様の理由で、ja0 <= pc0(31 downto 28) & instr(25 downto 0) & "00";のところを`ja0 <= pc1(31 downto 28) &....とするとj instructionの部分で失敗する。ここは、バグ取りの際、原因を把握するのに結構時間のかかったところだった。(signal名の付け方がそもそもの問題なのかもしれないが..)

enable signal か syncronous reset(clear) signal か?

stall時は、calc_clr='1'とすることで、Calc Stageの入力を同期的にresetさっせる。 beqの条件がtrueになる場合も、decode_clr='1'とすることで、Decode Stageの入力を0にする。どちらの場合でもenable signalをOFFにすることで対応はできない。

f:id:knknkn11626:20181213162020j:plain — stall時の挙動

図の棒みたいな奴はD-flipflopのつもり。もし、Aの部分のsyncronous resetをONする代わりにenableをOFFにすると、CLKの立ち上がり後にCalc Stageにlw $s0, 60($0)が残ってしまう(Data Cache stageにもlw $s0, 60($0)があるにも関わらず)なので、意図しない結果が起こる(実装次第なので、必ずしも予期せぬことが起こるわけではないが、バグの温床となる)

一方で、cache missによるCPUの一時停止の際は、clrで該当のステージの入力を0にresetしてしまうと、本来持っているデータが意図せず消えてなくなるから、ここはenable signalをOFFにすることで対応する。

要するに意図して保存されている値を消したい場合は、syncronous resetを使い、消したくない場合は、enable signalを使い、各ステージの入り口を止めれば良い。

よかったところ

controllerを役割別に分離した結果、わかりやすい実装ができた

cached_pipelined_mips/controller at v1.0 · knknkn1162/cached_pipelined_mips · GitHub のように複数のcomponentに分離したことで見通しがよくなった。datapathは一つのファイル(datapath.vhdl)にまとめた。1ファイルに集約することで、ファイルが大きくなる問題はあるが、datapathの全体像を把握しやすいので、実装観点からはあんまり不満はなかった。

registerのwritebackのbufferを用意したことで、実装がかなり楽になった

Registerの書き込みを逐次的に行うためにcomponent/regw_buffer.vhdl を用意した。利点はいくつかある：

1: regw_buffer.vhdlではあるregister addressが与えられた時に、buffer内を検索して値を返すように実装している。これを行うことによって、どのステージ間でforwardingを実装する必要があるかどうかを意識することが不要になった。もし、forwardingを Digital Design Computer Architectureの通りに実装する場合、

Calc Stage->Decode Stageの方向にforwardingを実装
Data Cache R/W Stage -> Decode Stageの方向にforwardingを実装

の2箇所実装する必要がある。比べて、regw_buffer.vhdlを用意した場合は、このcomponentがregisterのwritebackを一元的に管理してくれるため、regw_buffer-> Decode Stageの1箇所ですむ( https://github.com/knknkn1162/cached_pipelined_mips/blob/v1.0/datapath.vhdl#L308-L309 ) 。

2: パイプラインの段数はlwやaddi, addで異なるように設計しているため、Resiger のwritebackの部分が2つのinstructionで競合してしまう可能性がある。 Registerの書き込みを逐次的に行うことによって、競合を回避することができた。(迷ったところの「instructionごとにStageの段数が異なる場合の影響」にも同じようなことを書いた) ただし、これはmips architectureに依存する実装かもしれない。

cacheをいい感じに実装できた

cache missが発生した時、数CLK遅延させることで、data cacheおよび、instruction cacheを更新するような実装ができた。箇条書きのStage名はcontroller/cache_controller.vhdl にちなんでいる:

[NormalS] cacheをRead/Writeした時、cache missが起こることを想定する。この時cache_miss_en signalがONに出力される(これはcontroller/cache_controller.vhdlで制御している) cache_miss_en='1'をトリガーとして、[controller/mem_cache_controller.vhdl]のsuspendがONになり、各pipeline ステージの入り口のD-flipflopのenableをOFFおよびsyncrounous resetをONにする

1-0. (CLKの立ち上がり)

1-1. [Cache2MemS] 古いデータをmemory(L2 cache)に保存するためにmem_we='1'とする(これはcontroller/mem_cache_controller.vhdlで制御している)

2-0. (CLKの立ち上がり)

2-1. [Mem2CacheS] memoryからcacheにデータを移動する

3-0. (CLKの立ち上がり)

3-1. [CacheWriteBackS] cacheに書き込むためにcacheのsignalのload_en='1'とする。(これはcontroller/mem_cache_controller.vhdlで制御している)

(CLKの立ち上がり)

4-2. [NormalS] cache hitする。[controller/mem_cache_controller.vhdl]のsuspendがOFFになり、各pipeline ステージのD-flipflopのenableをONにする。

(CLKの立ち上がり)

5-1. 次のinstructionが走る...

見たいな風になった。controllerとdatapathの責務が分離されている状態で実装できているのではないかと思う。(制御がややこしいわりにはごちゃごちゃした実装にならずにすんだ)

circleCIでtest回すの自動化した。

これは、小さなことだけどやってみるとやっぱり楽。GHDL compiler + make commandでtestbench通るかどうかを1pushごとに確認している。

感想

巷ではC compilerのフルスクラッチ実装が流行っている(自分は未経験なので、いつかやりたい)が、わかる人にしかわからない言語(VHDL)を用いてCPU実装するのは半分大変で半分楽しかった。大変というのはモチベーション維持の意味。楽しいというのは、なんかなんかよくわからないところからやるので、トンネルを自力で掘っている感があり、探検している感じがある。手を動かしながら、computer architectureを理解するという意味では、大変勉強になった。
testbench書く( https://github.com/knknkn1162/cached_pipelined_mips/tree/v1.0/tests )の結構骨折れる(というか、細かく書きすぎ??) デバッグはgtkwave使って波形みて根性で行なった。とはいいつつ、testbench書くのは答え合わせをする作業なので、そんなに苦ではなかった。ただ、効率はそんなによくない感じがあるので、どうしようか..
signal名の付け方はオレオレ流なので、これは偉い人の実装とかをコードリーディングするとかで身につけるしかないかな？ -> https://scrapbox.io/craftmemo/Verilog_%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%AB%E3%83%BC%E3%83%AB が良いかもしれない
Makefileがひどいが、CPU実装できたので直す気があんまりない
次は、Modern Processor Design: Fundamentals of Superscalar Processorsを読んでsuperscaler実装に取り組みたい。architectureは現在慣れているmipsにするかもしれないし、流行りのrisc-vに手を出すかもしれない。その辺は気分で決まりそうだが、risc-vの仕様書を眺めて見たかんじ、x86に比べて、え、そんなんでいいのっていうくらいにはかなりシンプルだし、mipsと結構似ているので、新しいことやるという意味では、risc-vでやってみるのが良いかもしれないですね。。

パタヘネ本の 5.7 virtual memoryが詳しそうです。↩
cacheの構成はパタハネ本のch.5.3のThe Intrinsity FastMATH Processorを参考にした。cache lineが16line(=2⁴)でなく、8lineで小さめなのは、cache missの頻度をわざと上げたかったから。↩
L2 cacheといったほうがよい？かもしれない↩
cache dataの有効ビットがONでない場合(valid_flag='0')や全く「汚れていない」(dirty_flag='0')場合↩