セキュリティ・キャンプ 2026 全国大会・応募課題晒し (L2, CPU)

姉妹編：セキュリティ・キャンプ 2026 参加記

セキュキャンに通っていたので，主にこれから応募する人々に参考してもらうために応募課題の回答を公開しておく．自分が参加したのは開発 L2（プロセッサゼミ）のうちの CPU 班であり（NPU 班も存在する），応募課題はそれに際して CPU に関連する部分にのみ回答していることに注意されたい．ポエムは姉妹編の方で書くため，とりあえずこの記事では回答のみを記載することにする．

ちなみに他の受講生 2 人の応募課題晒しも既に存在している：

• https://zenn.dev/ryoga_exe/articles/seccamp2026-assignment
• https://qiita.com/Latte72R/items/3df98286c837db769b1f

Disclaimer: 今読んでみると拙い回答だが，今の自分が満足するために書き直してしまっては意味がないのでそのまま公開することにする．

---

「プロセッサゼミ」の応募課題は全3問(Q1-Q3)からなります。 Q1は共通問題であり、当ゼミに応募する方は全員回答してください。 Q2とQ3は選択問題です。このゼミは途中からCPU自作班とNPUプログラミング班に分かれます。選考に通過した場合、回答した選択問題に対応する班に配属されます。両方とも回答した場合の配属は講師側で決定させてもらいます。

Q1 (共通)

Q1.1

プロセッサゼミをなぜ志望するか教えてください。あわせて、本ゼミで取り組みたいことがあれば記述してください。ゼミではまず基本的な課題に取り組んだ後、受講者の皆さんそれぞれの興味に応じた発展課題に取り組む時間を設ける予定です。 また、何か他にアピールしたいこと（今まで作ってきたものなど）があれば、それも自由に書いてください。

志望理由

コンピュータサイエンスの各分野のうち、私が興味を持っているのはプログラミング言語の理論である。 理論的には関数型言語やプログラムの形式検証・静的解析、実践的にはコンパイラや言語処理系の実装についても興味を持ってきた。 実際のところ、これまで私が個人的に勉強してきたのもこれらの分野であり、ハードウェアやアーキテクチャといった低レイヤの分野については、大学の授業で初めて勉強している。

しかし、コンピュータサイエンスという理学・工学のいずれにも偏重しない分野を専攻する者として、こうした理論的な分野に留まるのはもったいないことだと思われる。 アーキテクチャや ISA について深い理解があるからこそ良いプログラムが書けるし、最適化技法についてよく理解しているからこそアーキテクチャの設計を真に理解することができるというものだ。 アーキテクチャやオペレーティングシステムについて知る毎に、キャッシュ効率の良いプログラムだとか、GC や参照カウンタというようなユーザ視点の断片的な知識が有機的に繋がるのを感じる。

私は「ハードウェアと手を取り合うソフトウェア」というスローガンを大切にしている。 ソフトウェアは究極的にハードウェアに依存しているわけで、ソフトウェアを提供するにはその地盤たるハードウェアの理解が不可欠であり、その上でハードウェアの長所を生かし、短所を隠蔽するような理論を創りたいと考える。 例えば Rust がその一例で、線形論理という高級な論理を用いることでコンピュータのメモリモデルをよく抽象化し、高速かつ安全なプログラムを簡単に書けるようにした。 これからの時代、ハードウェア側で様々な革新的な技術が起こることが期待される。 新しい ISA が出てくれば新しいコンパイラが必要だし、例えば PiM のような技術が現実的になれば、あるいはマルチコアによる性能向上の時代の今でこそ、これに対応したパラダイムを持つプログラミング言語を設計し、ソフトウェア側でも最適化が必要になる。 このゼミで学ぶような fundamental な知見を基盤にして、ハードウェアと手を取り合うソフトウェアを、理論の側から作り、高速、かつ安全、かつ楽しいコンピューティングを提供するような人間になりたいというのが、私がこのゼミを志望する理由である。

具体的にゼミでやりたいこと

私の所属する学科では来季に「CPU 実験」と呼ばれる実験が開講される。 この実験では OCaml のサブセットによるレイトレーシングプログラムと FPGA ボードが与えられ、自分たちで ISA やアーキテクチャを策定し、コンパイラ、FPU を含んだコア、シミュレータを書き実行速度を競う。 先述の通り私の興味はハードウェアよりもソフトウェアにあるため、ここではコンパイラ係を選択するつもりでいるのが、これにハードウェアのことを深く理解した上で臨みたいというのが本ゼミを志望するもうひとつの理由である。 この実験の面白いところは、目標が汎用 CPU ではなくて特定のプログラムをとにかく高速に動かすというところにあり、したがって自分たちで考案した ISA が RISC-V よりも好成績を残すということが往々にしてある。 これこそまさに、先述した「ハードウェアと協調するソフトウェア」の究極的な姿であり、ハードウェアと緊密に連携をとるようなコンパイラを書き、そのための ISA を設計できるようにもなりたいと思う。 具体的には、汎用型としては失敗したものの、VLIW 型の ISA をここで用いるのが面白いのではないかと考えている。

この実験に望む前に、こうしてプロセッサに対して一度深く向き合うために、（後述するものの）今回は RISC-V に準拠したオーソドックスなプロセッサを作成することを第一の目標とし、最終的な目標を目指して高速な CPU についての理解を深めながらできる範囲で高速化を目指したいと思う。 具体的にはパイプライン化や分岐予測などある程度の高速化を実装し、その後で VLIW について考えてみたいと思う。

過去の取り組み

• ブログ：https://atree4728.github.io/
  • 実績なども書いてあります
  • Haskell についての記事：https://atree4728.github.io/posts/introduction_to_equational_reasoning
• アルバイトでの Web 開発
  • TypeScript で社内チャットボットのフルスタック開発に参加
  • LLM と文字起こしアプリによる同時通訳アプリを owner として開発
• GitHub: https://github.com/atree4728
  • 簡単な TypeScript の型検査器：https://github.com/atree4728/ts-type-checker
  • レイトレーシング：https://github.com/atree4728/RayTracing.fs

コメント

CPU のゼミなのに関数型言語の話ばかりしている．「ハードウェアと手を取り合うソフトウェア」というのは当時の自分がハマっていたスローガンなのだが，言っていることは正しいと思う．大したことを言っているわけではないが，大学でコンピュータサイエンスを勉強したから書けた文章だなとは思う．一般にこういう選考は課題の出来よりも熱意が重要視される傾向にあるという体感があり，したがって割と頑張って書いた．

Q1.2

ターミナルでcoding agentに「このディレクトリ以下の構造を把握して」とプロンプトを入力してから結果がターミナルに表示されるまでにコンピュータの内側で起こっていることを、プロセッサの視点に立って説明してください。

[1] を参考にした。 簡単のためにキーボードとマシンはシリアル通信によって接続されているものとする。 まず、ユーザがキーボードを押下し物理的な短絡が生じると、キーボードからマシンに信号が送信され、マシンの割り込み要求端子がアサートされる。 割り込みコントローラはこれを受けて、割り込みの優先関係や、現在割り込み処理が行われているかどうかをチェックし、割り込みを受け容れると判断した場合はプロセッサのポートに信号を送信する。 プロセッサは命令境界において割り込み信号の有無を確認し、適切なセットアップをしたのちに割り込みを処理する割り込みハンドラに制御を移す。 ここでいう適切なセットアップというのはアーキテクチャに依存するが、おおよそ割り込みハンドラを適切に呼び出すための処理であり、例えば割り込みの原因を特別なレジスタに保存し、現在の実行コンテキストをスタックに保存したりする。 割り込みに対応するハンドラのエントリポイントは割り込みベクタというテーブルに保存されているが、これを呼び出す方法もアーキテクチャに依存し、システムコールのように共通のエントリから特殊なレジスタを読み取ることでハンドラを起動するタイプのものもあれば、始めからコントローラが適切な割り込みハンドラを呼び出すものもある。 キーボードによる IO に対応する割り込みハンドラは、デバイスに保存されたキーコードを Memory mapped IO 方式によって読み取り、主記憶に書き込む。 一連の処理が終わると、割り込みハンドラは mret 命令を実行し、コンテキストがユーザランドに復帰し、それまでの処理を継続し始める。

このようにして得た入力はメモリに保存され、ディスプレイに表示される。 ここでもプリミティブなシステムを仮定することにする。 この場合、ユーザがシステムコールを発行し、CPU はカーネルモードに移行する。 CPU はユーザ空間のメモリ領域に存在する文字列をカーネル空間のメモリ領域にコピーし、Memory Mapped IO を用いてディスプレイデバイスのデータレジスタにこれを転送する。 デバイスはデータを受け取った後に次の入力の準備が出来たかをマシンに通知し、さらにCPUが転送というのを繰り返す。

こうしてユーザがインストラクションを入力し終えてEnterキーを入力すると、プロセスは入力をサーバーに送信する。 サーバー側では巨大な資源によってニューラルネットワークによる計算が行われる。 特定の目的に特化して設計されたアーキテクチャは DSA; Domain Specific Architecture と呼ばれ、AI ワークロードの需要が高まる現代においては様々なものが開発されている。 ここでは、DNN に特化したアーキテクチャがどのような計算を行っているか、具体例として、Google による TPU について書くことにする。

TPU は CPU のように命令をフェッチして動作するユニットではなく、コプロセッサのようにホストから命令を受信して動作する。 この命令は CISC になっており、ホストのメモリとのIO、重みのセットアップ、行列積などの線形演算、非線型関数の演算などが備わっている。 TPU はメモリを受け取るとバッファにデータを置き、重み FIFO と呼ばれるメモリから重みをセットする。 次に行列積（及びそれに類する）計算を行う。 このような計算は逐次的に行うとなるとなにがしかの記憶領域を必要としてしまうが、TPU はシストリックアレイというアーキテクチャによってこれを解決する。 これは演算器、より正確には積和ユニットを長方形状に配置し、異なるタイミングで供給されるデータを計算し他のユニットに供給していくことで、結果の一時的保存なしにこのような計算を行う方法である。

このようにして得られた出力はまたクライアントに送信され、先程と同じようにディスプレイされる。

コメント

これは open-ended というか，書こうと思えばいくらでも書けるタイプの課題だし，話題が多岐に渡る傾向にあるので大変で，（ちょっと飽きたしこのくらいで勘弁してくれや）といったところで区切りをつけた記憶がある．といっても基本的にはヘネパタと Tanenbaum の内容をまとめただけなのだが．前半はプロセッサというよりシステムプログラミング的な部分もあり，この類の回答が想定されていたのかはよくわからない．

Q2 (選択・CPU自作)

Q2は難しい問題が多いので、すべてを完璧に回答できる必要はありません。調べても分からないことがあれば「どこまで調べて、何が分からなかったか」を書いてください。 Q2.2、Q2.3、Q2.4は、CPUが命令を処理する仕組みと構造の観点から回答してください。

Q2.1

CPU自作班では受講者がそれぞれ好きなISAのCPUを実装し、高速化や機能の追加に取り組んでもらう予定です。あなたが実装したいCPUの種類、使用するプログラミング言語、ハードウェア記述言語を教えてください。講師が予習するためにも、詳しく教えてください。

• 実装したい CPU の種類：RISC-V(RV32I)
• 使用するプログラミング言語：Haskell
• ハードウェア記述言語：Clash
  • https://clash-lang.org/
  • Haskell のサブセットをフロントエンドとした高位合成ツールで、Verilog HDL, SystemVerilog, VHDL のいずれかを出力する
  • Clash による既存の RISC-V コア実装
    • https://github.com/christiaanb/contranomy （パイプライン化されていないシンプルなもの、一応の目標としてこのレベルのものを想定している）
    • https://github.com/standardsemiconductor/lion （パイプライン化されていて、さらに形式検証の付いた advanced なもの）

注：Clash での実装を希望している理由は単にそれが面白くて便利そうだというだけなので、もしなにか困難があれば Chisel か SystemVerilog を使うことも想定しています。

コメント

RV32I とかパイプライン化しないだとかで自信のなさが垣間見える．Clash を「高位合成ツール」だと思っているのは明確に間違いで，Clash は RTL 記述のための EDSL である．このときは Verylで作るCPU の存在を知らなかったので，なにを見ながら実装するというようなイメージも湧いていなかった．今新しいコアを書くとしたら Veryl を使うと思うが，当時は Veryl も知らなかった（他の受講生 2 人は既に Veryl である程度動くコアを書いていた！）．

Q2.2

同じプログラムを実行した場合であっても、昔の高性能なCPUと比較して、最新の高性能なCPUの方が実行時間が基本的に短くなっています。何が差異を生み出しているのでしょうか？比較する年代、技術や手法を明示したうえで、CPUで命令が実行される手順に注目して説明してください。

簡単のためにシングルスレッドのプロセッサの性能向上について書く。 プログラムの実行時間は、一般に (1) プログラム中の命令数、(2) CPI; サイクル数/命令、(3) 実行時間/サイクル の積で書ける。 それぞれの変化について考えることにする。

まず、(1) の変化はそれほど大きな影響を与えていない。 x86_64 や ARM64 というような旧来の ISA は今でもスタンダードなアーキテクチャとして採用され大量生産されているし、RISC-V のような新興の ISA をもってしても、命令数はたかだか 0.75 倍程度にしかならない [2]。

(3) はプロセッサの周波数に対応する。 それまでは Moore の法則にしたがってプロセッサの集積密度が高まるのにつれ、チップ全体の消費エネルギーは一定のまま、プロセッサの周波数は線形に向上していったものの、2000 年代初頭にこの傾向はストップし、それ以降横這いになっている。 これは High/Low を区別できる限界まで電圧を下げきってしまったため、それ以上周波数を上げようとすると電力密度が増大してしまうという壁にぶつかったためである。 したがって、特に 21 世紀のプロセッサを考えるにあたってこれは支配的ではない。

本題は (2) CPI の向上、つまり特に命令レベル並列性の向上にある。

CPUが命令を実行する手順は、一般に (IF) 命令フェッチ (ID) 命令デコード (EX) 実行 (MEM) メモリ (WB) ライトバックの 5 段階に分けられる。

IF ステージでは、プログラムカウンタによってメモリから次の命令を読み出し、PC を +4 する処理が行われる。 この段階、及び MEM ステージにおける高速化としては、まずはキャッシュメモリが第一である。 記憶領域においては規模と速度が物理的なトレードオフとして存在する。 実際のところ主記憶へのアクセスは通常の演算と比して 10^2 オーダーのサイクルを要するため、レジスタと主記憶の中間的な性質を持ち、プログラムの局所性を生かす記憶装置としてキャッシュメモリが提案された。 これは、1968 年に発表された IBM 360/85 が商用コンピュータとしての初の搭載例である[3]。 また、そのキャッシュメモリはその規模に合わせて L1, L2, L3 というふうな階層化・大規模化が進んだ。 また、この段階における高速化として分岐予測もその一例である。 分岐命令は CPU のパイプライン化を滞らせるため、なんらかの手段を用いて、フェッチした命令が分岐命令かを検知し、その分岐先を予測することでこれを回避することができる。 これには様々な手法が用いられており、最近の N 回の履歴の偏りから単純に分岐方向を予測するもの、その応用である gshare 予測器、単純なパーセプトロンを用いるものなどが提案されてきた。 現在のところ最も精度が高いと言われている TAGE 予測器は 2006 年に登場し、現代のコンピュータにもよく搭載されている[4]。

ID ステージでは、取得した命令をデコードし、どのコンポーネントで処理するかを決定し、しばしばレジスタフェッチをする。 この段階における高速化としては、スーパースカラが挙げられる。 スーパースカラとは、1 つのコアにおいて 1 サイクルで複数の命令をデコードし、並列に実行する方式である。 分岐予測や後述する OoO によってパイプラインをいくら埋めたとしても CPI が 1 を下回ることはないが、こうした空間的な並列性を利用することで 1 コアでも CPI を理想的には 1 未満にすることができる。 また、レジスタフェッチ時におけるテクニックとしては、命令間の依存関係を解消するためのレジスタリネーミングによってストールを回避することができる。 これは依存関係を生じさせているレジスタに対して適切に新たなレジスタを割当てることで依存関係を解消する手法であり、IBM 360/91 に Tomasulo のアルゴリズムが搭載されたのが商用の例として初であった[5]。 このアルゴリズムはハードウェア的にも複雑なものだったが、現代では物理レジスタリネーミングという手法で ID ステージにリネーム処理を閉じさせる、よりシンプルな実装が主流になっている[6]。

EX ステージでは、ALU や FPU というふうなユニットを用いて実際に演算を行う。 この段階においては、先に言及したスーパースカラによる並列実行や、パイプライン状のバブルを埋めるために命令の順序を無視する Out-of-Order; OoO が処理を高速化する。 OoO は先述したレジスタリネーミングに依存しており、実際に IBM 360/91 が商用初の例である。 しかし、単に命令の順序を無視してしまえばプログラムが壊れるのは明らかであり、これを回避するためには後述するリオーダーバッファが利用される。

MEM ステージではメモリの読み出し・書き出しが実行されるが、ここの高速化は先述したキャッシュメモリが対応する。

WB ステージでは、これまでの結果を適切なレジスタに書き込む。 まず第一に、このステージに到達する前にフロントエンド側に直接値を送出するフォワーディングという手法によってパイプライン化が促進される。 次に、OoO を搭載したプロセッサにおいては WB ステージはリオーダーバッファ ROB への結果の格納と、その中身の in-order な commit という二段の構成になっている。 これによって投機的実行の順序の保証や、その取消が実現されている。

コメント

前半で定量的に原因を切り分けて議論しているのはよいと思うが，後半はフワッとしたタームの羅列になってしまっている．また，途中で書いたり消したりを繰り返しながら書いていたのもあって，単純に文章があまりうまくない．教科書を読んでその内容をフンワリ理解した感じになっているが，自分でもよくわかっていないなあと思っていた気がする．

Q2.3

分岐予測、投機的実行、Out-of-Order実行の中から1つ選んで、どのような技術かを簡単に説明してください。また、その動作を観測するプログラムを書いて、プログラムと実行環境、結果と考察を教えてください。観測できなかった場合は、なぜ観測できなかったか、どうすれば観測できそうかを考察してください。

分岐予測について書く。

CPU は効率化のためにひとつの命令の処理を複数のステージに分割し、これをパイプライン化して実行の並列度を高めている。 しかし、この戦略は分岐命令を弱点とする。 これは、レジスタを介したジャンプや条件付けによるジャンプをするためには、適切な命令をフェッチするために実際にその命令の直前まで実行が進まねばならないためである。 このようなハザードはパイプラインのステージ数が進む程にバブルを増やす一方で、分岐命令はプログラムのうち一定の割合を占める普遍的な命令である。 さらに、以降の命令をフェッチできない以上 Out-of-Order によってバブルを埋めることも困難である。

この問題を解決するためには、分岐に辿り着いた時点でその方向を決め打ちしておき、投機的にそのまま実行を進める分岐予測という手法が用いられる。 この方法には、 (1) ステージの早い段階で分岐命令を検知し、投機的実行を開始する (2) 分岐命令に対し、その分岐先アドレスを予測する ことが必要である。

(1) については、それまでに実行した分岐命令のアドレスをメモリ領域に保存しておくことで、命令フェッチステージでこれを行うことができる。 (2) については、分岐命令のアドレスを key、ジャンプ先アドレスを value とした Branch Target Buffer と呼ばれるテーブルを保存しておくという戦略が考えられる。 より洗練された戦略としては、ジャンプ先アドレスを複数保存し、それとは別に最近 N 回の分岐の taken/untaken の履歴を key、その次の分岐履歴を value としたパターン分岐テーブルを保存しておき、これに基づいた分岐方向の予測からジャンプ先アドレスを決定するというものがある。 この方法は、例えば分岐先が周期的に変化するようなループに対して分岐予測をヒットさせられる。

実際に分岐予測を検証するために、次のアセンブリを考える（[7] を参考にした。https://github.com/takenobu-hs/cpu-assembly-examples/blob/master/arm/linux/E00.perf_expt/branch_miss_many.S を macOS 向けに書き直したものである）。

/**
  *         for (i = 0; i < 10000000; i++) {
  *             x = xorshift();                // generate a random number
  *             if ((x & 1) == 0) goto L_br;   // branch-prediction test
  *             nop;
  *         L_br:
  *
  *         }
  *
  */
 
        .global _main
        .p2align 2
 
_main:
        /* Register usage:
         *   x0  : xorshift state / printf 1st arg
         *   x1  : xorshift temp
         *   x2  : branch condition (x0 & 1)
         *   x10 : address of `random`
         *   x11 : loop counter (i)
         *   x12 : loop max
         */
 
        /* save fp,lr registers */
        stp     x29, x30, [sp, -16]!    /* sp -= 16; *sp = x29; *(sp+8) = x30 */
 
 
        /* loop conditions */
        mov     x11, 0                  /* x11 = 0 */
        ldr     x12, =10000000          /* x12 = 10000000 */
 
        adrp    x10, random@PAGE
        add     x10, x10, random@PAGEOFF
        ldr     x0, [x10]               /* x0 = 88172645463325252 */
 
L_loop:
        /* generate a random number with the xorshift algorithm */
        lsl     x1, x0, 13              /* x0 = x0 ^ (x0 << 13) */
        eor     x0, x0, x1
 
        lsr     x1, x0, 7               /* x0 = x0 ^ (x0 >> 7) */
        eor     x0, x0, x1
 
        lsl     x1, x0, 17              /* x0 = x0 ^ (x0 << 17) */
        eor     x0, x0, x1
 
 
        /* branch-prediction test */
        and     x2, x0, 1               /* x2 = x0 & 1 */
        cmp     x2, 0
        beq     L_br                    /* if (x2 == 0) { goto L_br; } else { nop; } */
        nop
L_br:
 
        /* increment the loop-variable and loop-back */
        add     x11, x11, 1             /* x11++ */
        cmp     x11, x12
        blt     L_loop                  /* if (x11 < x12) { goto L_loop; } */
 
 
        /* print the last loop-variable */
        sub     sp, sp, 16              /* sp -= 16 */
        str     x11, [sp]               /* 2nd argument (variadic) on stack */
        adrp    x0, fmt@PAGE            /* 1st argument for printf */
        add     x0, x0, fmt@PAGEOFF
        bl      _printf                 /* printf("loop-variable = %lld\n", x11) */
        add     sp, sp, 16              /* sp += 16 */
 
 
        /* restore fp,lr registers and return from main */
        ldp     x29, x30, [sp], 16     /* x29 = *sp; x30 = *(sp+8); sp += 16 */
        ret
 
 
        /* read-only data */
        .section __TEXT,__const
random:
        .quad   88172645463325252       /* xorshift(xor64)'s initial value */
 
fmt:
        .asciz "loop-variable = %lld\n"

冒頭部のコメントにあるように、このアセンブリは 10^7 回のループ内で xorshift による擬似乱数を計算し、最後に乱数による分岐を行う。

Linux の perf コマンドに相当する https://github.com/tmcgilchrist/mperf を用いて、このコードを監視すると次のようになる：

$ sudo mperf-stat -e cycles -e instructions -e branches -e branch-misses -- ./branch_miss_many
loop-variable = 10000000
 
 Performance counter stats (2 threads):
 
             155605376  cycles
             137256503  instructions              #   0.88 IPC
              20834548  branches
               4983340  branch-misses
 
        0.077984 seconds wall time
        0.068211 seconds user
        0.006002 seconds sys

分岐命令はおよそ 2 * 10^7 発行されており、これは半分がループの継続条件に伴う分岐、もう半分がお目当ての (x2 & 1) == 0 に基づく分岐である。

前者のループに関しては 10^7 回のうちほぼすべてが taken であるため分岐予測がほぼ成功することが期待される。 一方で擬似乱数に基づいて 1/2 の確率で taken/untaken が切り替わる後者の分岐については、おおよそ半分程度の分岐が分岐予測に失敗することが期待される。 これは実際に、branch-misses が約 5 * 10^6 回であるという観察に対応している。

条件部を変更することで、この観察をよりもっともらしいものにすることができる。 条件部を x2 == x2, x2 & 3 = 0 に変更したそれぞれ branch_miss_few, branch_miss_quarter の実行結果は次のようになり、分岐予測の失敗率がおおよそ 0, 1/4 になることがわかる。

$ sudo mperf-stat -e cycles -e instructions -e branches -e branch-misses -- ./branch_miss_few
Password:
loop-variable = 10000000
 
 Performance counter stats (2 threads):
 
              71864594  cycles
             132407526  instructions              #   1.84 IPC
              20994899  branches
                 23588  branch-misses
 
        0.039428 seconds wall time
        0.032008 seconds user
        0.003189 seconds sys
 
$ sudo mperf-stat -e cycles -e instructions -e branches -e branch-misses -- ./branch_miss_quarter
loop-variable = 10000000
 
 Performance counter stats (2 threads):
 
             117081150  cycles
             141567133  instructions              #   1.21 IPC
              20998778  branches
               2584241  branch-misses
 
        0.456965 seconds wall time
        0.049751 seconds user
        0.004520 seconds sys

コメント

今思えば，投機的実行を選べば結果として他 2 つ（分岐予測，OoO）についても書かざるをえないという意味でヘンな三択である．ちょうどピッタリの説明が教科書にあったためにそれを流用する形になったが，こういう計測基盤を自分で構築できる人間は強いと思う．CPU を開発する上でも（どんなものだってそうなのだが）評価基盤を適切に設計し，定量的な評価フローを通しながら改善を施していくというのは重要なテクニックだった．

Q2.4

任意のISAの中から定義を1つ選んで、そのように定義されている理由や経緯を教えてください。その定義を変えればCPUを高速化できそうかを考察してください。ISAはあなたしか知らない自作のISAでも構いませんが、その場合は仕様書にアクセスする方法を教えてください。

RISC-V について書く。

RISC-V は x86_64 や ARM64 といった既存の ISA の反省を踏まえて設計されたとアピールされている[8]。 例えば、既存の ISA が技術進歩に伴って際限無く命令を追加してしまったために、obsolete な命令で仕様が肥大化してしまったことを踏まえ、RISC-V は機能毎に仕様をモジュールに分離し、それぞれは凍結するという選択を取っている。 例えば浮動小数点演算はコア仕様に含まれておらず、浮動小数点用のレジスタを他の部分から独立にさせることによってレジスタを指定するためのビット幅をミニマルに抑えられている。

また、RISC-V は命令ビット列のエンコーディングについても工夫されている[8]。 opcode と funct の分離は一見非自明だが、これによって命令を全て読まずとも実行ステージを進行させることができ、これは高速化に寄与する。 ほかにも、ある部分がひとつの命令では読み込みレジスタ、他の命令では書き込みレジスタの番号として参照されることがないように設計されており、これはハードウェアの単純化に寄与する。

RISC-V の美しい設計にケチをつけるのは難しいが、例えば 32 個しかないレジスタを 64 個に増やせばより高速に実行できる ISA になるではないかと考えることができる。 レジスタの数が増えればコンパイラはレジスタ割当て問題を解きやすく、スピルアウトを減らすこともでき、共通部分式削除というような最適化を小さなレジスタ圧の下行うこともできる。 レジスタリネーミングがあるといえども、実際 armv8 や x86 に比して RISC-V はより多くのレジスタを持っている。

これに対して、[9] の Figure 5.1 には RISC-V におけるレジスタの使用率がグラフになって示されており、レジスタの添字が大きくなるにつれてその使用率が指数的に小さくなっていることが確認できる。 これによると、レジスタを増やしたからといってたくさんのレジスタが使われるとは限らず、逆にエンコーディング中のレジスタを指定する部分が増大することによるデメリットの方が大きいということが予想される。

簡単のために $n$ 個のレジスタ $r_1,...,r_n$ を持つ ISA I1 があって、使用率が比を $0<t<1$ として小さくなっていくものとする。 もしこれに追加で $n$ 個のレジスタが使える ISA I2 があったとすると、$r_i$ の使用率は $c{t}^i$ と書けることが期待できる。 ここで $c$ は I2 の全レジスタの使用率の総和が 1 となるための正規化定数であり、$c=(1-t)/(t(1-t^{2n}))$ である。 一回のレジスタ参照に対し、I1 においてスピルアウトが必要だが、I2 なら必要ないというような場合は $r_{n+1},...,r_{2n}$ が参照される場合で、この確率は

$$c(t^{n+1}+...+t^{2n})=c\cdot t^{n+1}(1-t^n)/(1-t)=t^n/(1+t^n)$$

である。 例えばグラフから読みとった概算として t = 0.6 であったものとすると、n = 1, 2, 4, 8, 16, 32 のそれぞれについてこれを計算すると、0.375, 0.265, 0.115, 0.0165, 0.000282, 0.0000000896 となる。 この指数的減少が観察できるのは RISC-V でいうところの a 系列及び s 系列というようなレジスタ群なので、だいたい RV32I は n = 10 に対応し、この場合の値は 0.00601 に対応する。 この確率と、レジスタアクセスに対するストアのサイクル比の積が 1 に近付くとだいたいバランスがよいレジスタ数だろうと考えることができる。 スピルアウトに要するサイクル数はキャッシュ能率に依存するし、最大限好意的にメインメモリにスピルアウトされるとしても、レジスタアクセスに比べて 100 倍のオーダーだから n = 10 という値はこのモデルでは最適とは言えない。 しかし、単純なモデルで少々都合の良い計算かもしれないが、少なくともレジスタを増やせば増やすほどよいというものではないということが考察できた。

コメント

これなんかは全員 RISC-V の話を書くのではないかと思う．と思っていたら Latte さんは x86_64 で書いていた．『RISC-V 原典』に x86 の命令数の変遷のグラフがあり，現在の x86 は数千個の命令が存在しているが多くは obsolete になっているみたいな話が載っていて，苦笑してしまった．後半の解析については正確な結果とは到底言えないのだが，こういうオーダーレベルの概算みたいなもので定性的な解釈をするというふうな考え方は物理・化学のうまい考察っぽい感じがして割と気に入っている（他の回答に新規性っぽいものがないため）．この回答もグオオと言いながら書き殴ってしまった感じがあり，読みにくい……

Q2.5

今までに作ったり、書いたことがあるCPU(シミュレータや周辺部品でも可)について、そのテスト手法を教えてください。テストは何を対象にして何を検証したのか、今後テスト手法を改善するならどうするかを書いてください。まだCPUを作ったことがない場合は、CPUをハードウェア記述言語で書くにあたって、どのように設計してテストするかの計画を立てて教えてください。

CPU を作ったことがないので、設計やテストの計画を記述する。

まず、目標を定める。 ここでは RV32I に準拠したシングルコア・パイプラインなしの CPU を実装し、FPGA 上で動かすことを第一の目標とする。 その後 UART を実装するなどして外部と通信することでなにかしらのプログラムを動かしたいが、このあたりの方法についてはメンターの方に適切な方法を教えていただこうと思う。 プログラムが動いてベンチマークがとれるようになってから、パイプライン化や分岐予測といった最適化に挑戦していければと思う。

CPU の設計については、Clash の特長を生かして宣言的・純粋に記述していく。 組合せ回路のコンポーネントについては単純な純粋関数として定義し、順序回路は Mealy machine として状態遷移を純粋に記述する。 ここまでのロジックは stateless に書くことができるため、容易にテストを書くことができる。 Clash は mealy という関数をライブラリとして提供しており、実際にクロックに同期するレジスタと統合するパートは書かずに済む。 また、Clash のウリであるところの Haskell の言語機能も積極的に使用することができる。 例えば型情報としてレジスタのビット幅を持つことであらぬエラーを静的に弾くことができる。

テスト手法としては Haskell の機能を使うことができる。 QuickCheckやtastyというようなライブラリが整っており、コンポーネント毎のユニットテスト及びプロパティベーステストを行うことによってボトムアップに実装の正しさを検証していく。 また、順序回路のように stateful な回路の検証についても、Clash の提供する simulate 関数によって Haskell の範疇でテストを書くことができる：https://hackage-content.haskell.org/package/clash-prelude-1.10.0/docs/Clash-Prelude.html

また、https://github.com/riscv-software-src/riscv-tests や https://github.com/riscv/riscv-arch-test を用いることができるだろう。 第一の目標については riscv-tests の rv32ui を通すことが到達点になるだろう。

コメント

当たり前のことしか書けなそうで，当たり前のことを膨らませたという感じ．今思えばベンチマークとか継続的な評価の話も書けそうである．EDSL による HDL の実現のよいところはテストが書きやすいところだというのは事実で，cabal test 一発で並列化されたシミュレーションテストが走り riscv-tests が通るという開発体験は良かった（Veryl は C++ への transpile を介す必要があり，ちょっと遅いようだった）．

参考文献

[1] A. S. Tanenbaum and H. Bos, モダンオペレーティングシステム 第5版 上, 水野忠則 ほか訳. 東京: 日経BP, 2025.
[2] D. Patterson and A. Waterman, RISC-V原典 オープンアーキテクチャのススメ, 成田光彰 訳. 東京: 日経BP, 2018.
[3] “IBM System/360 Model 85,” Wikipedia. https://en.wikipedia.org/wiki/IBM_System/360_Model_85 (accessed May 17, 2026).
[4] 塩谷亮太, “先進計算機構成論 付録：分岐予測の詳細.” https://github.com/shioyadan/advanced-computer-organization/blob/master/aco-shioya-appendix-bpred.pdf (accessed May 17, 2026).
[5] J. L. Hennessy and D. A. Patterson, コンピュータアーキテクチャ 定量的アプローチ 第6版, 中條拓伯, 天野英晴, 鈴木貢 訳. 東京: エスアイビー・アクセス, 2019.
[6] 塩谷亮太, “高性能 CPU の研究・開発動向（2022/11/07）.” https://github.com/shioyadan/advanced-computer-organization/blob/master/aco-shioya-appendix-processor.pdf (accessed May 17, 2026).
[7] T. Tani, プログラマーのためのCPU入門 ― CPUは如何にしてソフトウェアを高速に実行するか. 東京: ラムダノート, 2023.
[8] 塩谷亮太, “先進計算機構成論 02.” https://github.com/shioyadan/advanced-computer-organization/blob/master/aco-shioya-02.pdf (accessed May 17, 2026).
[9] A. Waterman, “Design of the RISC-V Instruction Set Architecture,” EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2016-1, Jan. 2016.