自作CPUでDoomを動かし、バイラルになる

Doom # Doom Doomはid Softwareによって1993年にリリースされたビデオゲームです。それはゲームの世界に革命をもたらし、現代のFPSを定義しました。その人気から「Doomは何でも動く」という言葉が生まれました。この点を証明するために、Doomはマイクロコントローラーからトースター、さらにはバクテリアに至るまで、ほぼあらゆるものに移植されてきました。2週間前、私たちはゼロから構築したCPU上でDoomを（這うように）実行することに成功し、その後数百万回の再生回数を記録したビデオを投稿しました。正直、まだ信じられません。では、私たちは実際に何をしたのでしょうか？論理ゲートレベルでカスタムCPUを設計し、ペリフェラルに接続し、Doomのソースコードを私たちのマシンで実行できるように適応させ、リアルタイムで実行するためにFPGAにデプロイしました。Doomを実行する前は、PongやMandelbrot集合のような、私たちが書いた簡単なプログラムしか実行したことがありませんでした。今ではフル公開ゲームを実行できますが、そこに至るまでの道のりはかなり険しいものでした。 要件 この記事ではパイプライン設計から始め、より複雑なプログラムを目指しました。Pongは素晴らしかったですが、70年代のものでした。私たちは90年代に飛び込みたかったのです。しかし、私たちの前にはメモリと速度という2つの大きな問題がありました。より大きなプログラムにはより大きなメモリが必要ですが、私たちの設計ではFPGAのBRAMしか利用できず、それは1メガバイト未満でした。Doomの基本的なシェアウェア（doom1.wad）は14メガバイトです。これはプログラムを実行するために必要なメモリを含んでおらず、単に保存するためだけのものです。2つ目の障壁は速度です。Doomは現代のPCにとっては楽勝ですが、私たちのCPUにとっては非常に遅いです。私たちは単純に、もっと速くする必要がありました。 そこで、Liamと私はそれぞれ個別に問題に取り組むことにしました。Liamは現在、アウトオブオーダー実行の基盤を築いており、これにより並列処理とパイプライン実行のトリックが大幅に向上します。私はメモリ統合に取り組みました。 extraメモリチップを接続するだけのように聞こえるかもしれませんが、現実ははるかに複雑です。 メモリ統合 元のCPU設計では、メモリは非常にクリーンでした。FPGA BRAMは1サイクルのレイテンシを持ち、インターフェースするのが非常に簡単です。この一貫性により、パイプライン化されたプロセッサはメモリのためにストールする必要がありませんでした。なぜなら、一貫した遅延が直接パイプラインに組み込まれていたからです。さらに、BRAMは粒度が高く、メモリを単語ごとに読み書きできます。 一方、DDR3メモリは遅く、レイテンシが変動し、バス幅が広いです。これにより、メモリ操作はより複雑で予測不可能になります。また、はるかに遅くなります。すべてのメモリ操作がDDR3メモリに送信されると、CPUは非常に遅くなります。ここでキャッシュが登場します。プログラムは常にすべてのメモリを使用するわけではないため、キャッシュはアクティブなメモリ領域をBRAMに保存して、アクセス速度を向上させます。うまく最適化されたキャッシュは、DDR3による追加のレイテンシをほぼ排除できます。 設計 このバージョンのCPUは、比較的標準的な5ステージパイプラインを使用しています：命令フェッチ、デコード、レジスタ読み取り、実行、ライトバック。さらに、この設計はメモリ操作を抽象化して統一インターフェースにすることで、コアパイプラインステージを簡素化しています。 コアパイプライン 命令フェッチステージは、プログラムポインタを追跡し、命令キャッシュ（ICache）を介してメモリから正しい命令を取得します。以前の設計とは異なり、内部でリダイレクションとストールを処理します。DDRメモリが追加されたことで、リダイレクションははるかに複雑になりました。以前はメモリのレイテンシは1サイクルだったので、命令をサイクルごとにフェッチし、リダイレクション要求が来たサイクルでメモリ要求アドレスを切り替えることができました。 しかし、新しい設計では、フェッチステージがリダイレクション要求を受け取った場合、メモリはすでにインフライトの要求を持っている可能性があります。次にメモリからの応答が無効であることを追跡し、正しいアドレスを要求する必要があります。この問題を解決した後、フェッチステージは問題なく動作します。 デコードステージは単純です。32ビットの命令を受け取り、それを構成要素に分解してパイプラインを通過する命令バンドルに保存します。このステージにもいくつかのユニークな問題がありましたが、それについては後続のセクションで説明します。 読み取りステージは大幅に変更されました。以前のレジスタファイルの問題の1つは、組み合わせ読み取りを使用していたため、CPUが遅くなったことでした。このバージョンでは読み取りをパイプライン化し、1サイクルのレイテンシを追加しますが、クリティカルパスの遅延を短縮します。もう1つの変更点は、Read-After-Write（RAW）ハザードの処理です。RAWハザードとは、保留中の書き込みが完了する前にレジスタを読み取ってしまい、不正確なデータを得てしまうことです。以前の読み取りステージは、それを通過した最後のいくつかのレジスタ書き込みを内部で追跡していました。これは論理的には効率的でしたが、脆弱で、常に機能するわけではありませんでした。より厳密なテストにより、特別なケースでハザードを検出できないことが示されました。新しいバージョンは、周囲のコアによって計算され、ステージにフィードされるRegister Usage Map（RUM）に依存しています。RUMは、レジスタが使用中かどうかを追跡する32ビットマップです。これは、マジックナンバーを必要とせずに、可変パイプライン長に自然にスケーリングします。RUMを使用して、読み取りステージはハザードフラグを立てて前のステージをストールする必要があるか、または命令を通過させるかを決定します。 実行ステージは、各命令に対して何を行うかを決定します。命令の部分をさまざまなコンポーネントにルーティングし、算術演算のためにALUを呼び出し、分岐を解決し、メモリと通信します。ジャンプを解決するときは、パイプラインを逆方向にフラッシュ信号を送信して、不正なステージを消去します。メモリ命令を見ると、メモリが応答するまでストールする特定のメモリ待機ステージに入ります。 ライトバックステージは、値をレジスタファイルに書き戻すだけです。 メモリ処理 コアパイプラインは正直かなり標準的で、メモリが面白いところです。理想的なパイプライン化されたCPUでは、命令フェッチステージは新しい単語をフェッチし、実行ステージはサイクルごとに新しいデータをフェッチします。対照的に、FPGA上のDDR3は30〜60サイクルごとに2つの単語を返すことができます。これは、私たちの望むスループットよりも大幅に遅いため、キャッシュが必要です。実際、2つのキャッシュが必要です。フェッチステージと実行ステージは、1サイクルで2つの異なるアドレスを要求する可能性があるため、両方をサービスするには、命令キャッシュ（ICache）とデータキャッシュ（DCache）が必要であり、これらは独立して動作します。 キャッシュ ICacheとDCacheは比較的シンプルで、互いに非常に似ています。実際、ICacheはDCacheと全く同じ基盤コードを使用していますが、書き込みロジックは削除されています。どちらのキャッシュも、シンプルでシングルウェイのダイレクトマップキャッシュです。現在のイテレーションでは、それぞれが4単語ごとの2048キャッシュラインを使用しています。 メモリ要求を受信すると、キャッシュは単語アドレス（下位2ビットを削除して）を分離し、キャッシュインデックスを計算します。キャッシュインデックスは、単語アドレスの下位10ビットです。次に、そのキャッシュラインをBRAMからプルします。キャッシュラインは、データ、タグ、ステータスの3つのコンポーネントで構成されています。データは、キャッシュが追跡しているメモリの実際の4つの単語です。タグは、単語アドレスの上位ビットであり、キャッシュエイリアシングを防ぎます。エイリアシングとは、複数のアドレスが同じキャッシュインデックスを指し、それらを混同しないようにする必要があることです。2つのステータスビットは、有効（valid）とダーティ（dirty）信号を表します。有効は、ラインデータが実際にはデータであり、初期化ランダムではないことを意味し、ダーティ信号は、CPUがメモリからフェッチされて以来、ラインを変更したかどうかを知らせます。プルされたキャッシュラインが有効で、タグが一致する場合、キャッシュはメモリ要求を一切行うことなく、単純な読み取りまたは読み取り・変更・書き込み操作を実行します。 しかし、タグが一致しない場合、キャッシュはDDR3メモリを参照する必要があります。有効なキャッシュラインには、クリーンとダーティの2つの状態があります。ラインがクリーンな場合、新しいキャッシュラインをメモリから読み取り、現在のデータを破棄できます。ラインがダーティな場合、キャッシュはまず変更されたラインを書き戻し、次に新しいデータを要求する必要があります。DDR3のレイテンシは30〜100サイクルである可能性があるのに対し、キャッシュヒットはわずか2サイクルであるため、これは非常に遅いです。 キャッシュアドレスデコーダー ダイレクトマップド ・1