自作CPUでDoomを動かし、バイラルになる
Running Doom on Our Custom CPU and Going Viral (armaangomes.com)
要約
この記事は、開発者がゼロから設計・構築したカスタムCPU上で、古典的なFPSゲーム「Doom」を動作させることに成功したプロジェクトについて詳述しています。メモリ容量と処理速度の課題を克服するために、DDR3メモリとキャッシュシステムを統合したCPUパイプラインの設計と実装について解説しています。
全文翻訳
カスタムCPUでDOOMを動作させ、バイラルヒットを記録
[画像: 作者が設計したカスタムCPUの様子]
DOOMは1993年にid Softwareからリリースされたビデオゲームです。これはゲームにおける革命であり、世界中に広まり、現代のFPS(ファーストパーソン・シューティング)の定義を確立しました。「何にでもDOOMは動く」という言葉が生まれるほど、その人気は、マイクロコントローラーからトースター、さらにはバクテリアに至るまで、ほぼあらゆるものにDOOMが移植されるきっかけとなりました。
2週間前、私たちはゼロから構築したCPUでDOOMを(クロールさせるように)動作させることに成功しました(そして、数百万回再生された動画を投稿しました)。正直なところ、今でも信じられません。では、私たちは一体何をしたのでしょうか? 論理ゲートレベルでカスタムCPUを設計し、ペリフェラルに接続し、DOOMのソースコードを私たちのマシンで実行できるように適応させ、リアルタイムで動作させるためにFPGAにデプロイしました。DOOMを実行する前は、Pongやマンデルブロ集合のような、私たちが書いた簡単なプログラムしか実行していませんでした。今や、市販のフルゲームを実行できるようになりましたが、そこに至るまでの道のりは、かなり険しいものでした。
要件
この投稿にあるパイプライン設計から始め、私たちはより複雑なプログラムを目指しました。Pongは素晴らしかったですが、それは70年代のゲームでした。私たちは90年代に飛び込みたかったのです。しかし、私たちの前にはメモリと速度という2つの大きな問題がありました。より大きなプログラムにはより大きなメモリが必要ですが、私たちの設計ではFPGAのBRAMしか利用できず、それは1メガバイト未満でした。DOOMの基本的なシェアウェア(doom1.wad)は14メガバイトです。これには、プログラムを実行するために必要なメモリだけでなく、保存するためのメモリも含まれていません。2つ目の障壁は速度です。現代のPCにとってはDOOMは朝飯前ですが、私たちのCPUにとっては非常に遅いです。私たちは単純に、もっと速くする必要がありました。
そこで、Liamと私はそれぞれ個別の問題に取り組むことにしました。Liamは現在、より大きな並列処理とパイプラインの履行トリックを可能にするアウト・オブ・オーダー処理の基盤を築いています。私はメモリ統合を担当しました。単純に聞こえるかもしれませんが、「追加のメモリチップを接続するだけ」というわけにはいきません。現実ははるかに複雑です。
メモリ統合
元のCPU設計では、メモリは非常にシンプルでした。FPGA BRAMは1サイクルのレイテンシを持ち、インターフェース接続は非常に簡単です。この一貫性により、パイプライン化されたプロセッサーはメモリのためにストールする必要がありませんでした。なぜなら、一貫した遅延はパイプラインに直接組み込まれていたからです。さらに、BRAMは粒度が細かく、メモリを単語単位で読み書きできます。
一方、DDR3メモリは遅く、レイテンシが変動し、バス幅が広いです。これにより、メモリ操作はより複雑で予測不可能になります。また、はるかに遅いです。もしすべてのメモリ操作がDDR3メモリに送られたら、CPUは非常に遅くなります。ここでキャッシュが登場します。プログラムは常にすべてのメモリを使用するわけではないので、キャッシュはアクティブなメモリ領域をBRAMに保存して、アクセス速度を向上させます。うまく最適化されたキャッシュは、DDR3によるレイテンシの追加をほぼ完全に排除できます。
設計
このバージョンのCPUは、比較的標準的な5ステージパイプラインを使用しています:命令フェッチ、デコード、レジスタ読み込み、実行、ライトバック。さらに、この設計ではメモリ操作を統一されたインターフェースに抽象化し、コアパイプラインステージを簡素化しています。
コアパイプライン
命令のFetchステージはプログラムポインタを追跡し、命令キャッシュ(ICache)を介してメモリから正しい命令を取得します。以前の設計とは異なり、リダイレクションとストールを内部的に処理します。DDRメモリの追加により、リダイレクションははるかに複雑になります。以前はメモリのレイテンシは1サイクルだったので、命令を毎サイクルフェッチし、リダイレクション要求が入ったサイクルでメモリ要求アドレスを切り替えることができました。
しかし、新しい設計では、フェッチステージがリダイレクション要求を受け取った場合、メモリはすでにインフライトの要求を持っている可能性があります。次にメモリからの応答が無効であることを追跡し、正しいアドレスを要求する必要があります。この問題を解決した後、フェッチステージは完璧に動作します。
Decodeステージはシンプルです。32ビットの命令を受け取り、それを構成要素に分解し、パイプラインを通過する命令バンドルに保存します。このステージにもいくつかのユニークな問題がありましたが、それは後で説明します。
Readステージは大幅に修正されました。以前のレジスタファイルの問題の1つは、コンビネーショナルリードを使用していたため、CPUが遅くなっていたことです。このバージョンではリードをパイプライン化し、レイテンシが1サイクル追加されますが、クリティカルパスの遅延を短縮します。もう1つの変更は、Read-After-Write(RAW)ハザードの処理です。RAWハザードとは、保留中の書き込みが完了する前にレジスタを読み取ってしまい、不正なデータを得てしまうことです。以前のリードステージは、それを通過した最後のレジスタ書き込みを内部的に追跡していました。これは論理的には効率的でしたが、脆弱で、常に機能するわけではありませんでした。より厳密なテストにより、特殊なケースでハザードを検出できないことが判明しました。新しいバージョンは、周囲のコアによって計算され、ステージに供給されるRegister Usage Map(RUM)に依存しています。RUMは、レジスタが使用中かどうかを追跡する32ビットマップです。これは、マジックナンバーを必要とせずに、可変パイプライン長に自然にスケーリングします。RUMを使用して、Readステージはハザードフラグを立てて前のステージをストールする必要があるか、または命令を通過させるかを決定します。
Executeステージは、各命令に対して何を行うかを決定します。命令の一部をさまざまなコンポーネントにルーティングし、算術演算のためにALUを呼び出し、分岐を解決し、メモリと通信します。ジャンプを解決する際には、パイプライン全体にフラッシュ信号を送信して、不正なステージを消去します。メモリ命令を検出すると、メモリが応答するまでストールする特定のメモリ待機ステージに入ります。
Writebackステージは、値をレジスタファイルに書き戻すだけです。
メモリ処理
コアパイプラインは正直言ってかなり標準的ですが、メモリ部分が面白くなります。理想的なパイプライン化された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メモリを参照する必要があります。有効なキャッシュラインには、クリーン(clean)とダーティ(dirty)の2つの状態があります。ラインがクリーンな場合、新しいキャッシュラインをメモリから読み取り、現在のデータを破棄できます。ラインがダーティな場合、キャッシュはまず変更されたラインをライトバックしてから、新しいデータを要求する必要があります。DDR3のレイテンシは30〜100サイクルになる可能性があるのに対し、キャッシュヒットはわずか2サイクルであるため、これは非常に遅いです。
率直に言って、これは非効率的な設計です。より優れたキャッシュは、ストレージ密度と空間的再利用性を向上させるために、より長いキャッシュラインを使用するでしょう。しかし、4単語のライン幅は、元のFPGAボード上の128ビット幅のMIGインターフェースとの接続を簡素化するために選択されました。後に別のボードに切り替えたため、現在は単なる残された非効率性となっています。
アービトレーション
ここで、もう1つの問題に気づいたかもしれません。2つのメモリ要求が同時にインフライト状態になるのをサポートするために2つのキャッシュを使用しましたが、これは問題を先送りしただけです。ICacheとDCacheの両方が同時にメモリ要求を行う場合はどうなるでしょうか? 以前の6.191では、キャッシュごとにメモリチップを用意することで解決されていましたが、私たちのボードには1つのチップしかなく、これは不可能です。ここでメモリアービターが登場します。これは両方のキャッシュのメモリインターフェースとして機能し、通常は要求を実際のDDR3メモリに渡すだけですが、要求が既にある要求と同時に行われた場合、メモリが要求を受け取ったかのように見せかけ、実際にはキューに入れ、メモリが空くまで待ってから送信します。もちろん、これにより、一方のキャッシュが他方のメモリアクセスを飢えさせるデッドロックの可能性が生じます。これは、DCacheをICacheよりも優先することで解決されます。なぜなら、DCacheはパイプラインの下流にあり、最終的にはクリアされてメモリ要求を完了するためです。
低レベル
上記すべてにより、CPUはシミュレートされたメモリで完璧に動作しますが、実際のハードウェアでは動作しません。まず、DDR3メモリインターフェースは非常に複雑で、非常にタイトなタイミングと制御が必要です。ここでXilinxのMemory Interface Generator(MIG)が登場します。これは、非常に複雑なインターフェースを、単に複雑なインターフェースにします。2つ目の問題は、MIGが独自のクロックドメインで実行されるため、CPUをMIGに直接接続すると、解読不能なタイミング問題が発生してクラッシュすることです。3つ目は、元のFPGAボード(128ビットバス搭載)でMIGを動作させることができなかったため、友人のRyan Tangのボードを借りました。このボードには、64ビットバスを持つより小さなDDR3チップが搭載されています。
これらの問題は、Clock Domain Crossings(CDC)、FIFO、およびプロトコルラッパーのシリーズによって解決されました。詳細に立ち入るのは痛すぎるため、GitHubで確認できます。しかし、最も重要なのは、すべてが機能したことです。
[動画: DOOMが動作している様子]
新しいメモリを使えば、Bee Movieを再生できます。
インターフェースとI/O
DOOMをポートする前に、さらにいくつかのハードウェア要素が必要です。CPUは動作しますが、外部と通信する方法がありません。ペリフェラルが必要です:ディスプレイ出力、ハードウェアタイマー、デバッグ出力、キーボード入力。これらのペリフェラルにはメモリマップドIO(MMIO)を使用することにしました。VGAコントローラーは既に構築されていましたが、12ビットカラーに拡張し、HDMIポートに接続しました。ハードウェアタイマーもシンプルでした。マイクロ秒単位で時間を追跡し、メモリの単語に保存するだけです。デバッグ出力は少しトリッキーでした。シンプルなバージョンは、UART送信機を書き込み可能なメモリ値に接続するだけです。しかし、CPUが連続して多くの文字を印刷すると、一部がドロップされ、ゴミのような出力につながりました。そのため、オーバーフローを防ぐためにFIFOバッファを使用しました。キーボード入力はさらに悪かったです。当初の計画は、Ryanが貸してくれたUrbana FPGAボードのUSBホストチップとインターフェースすることでした。しかし、SPIドライバーを書き込んだ後、SPIバスを何も通らないのを見て混乱しました。ボード上のUSBポートは電力を供給しないため、キーボードに電力を供給できなかったようです。代わりに、UARTレシーバーを配線し、ラップトップからのキーストロークをFPGAに転送しました。完璧ではありませんが、機能します。これで、DOOMを実行するために必要なすべてが揃いました。
DOOMのポートとデバッグ
新しいチップにDOOMをポートするのは困難です。プログラムのロード方法、正しいペリフェラルへのアクセス方法、入出力の取得方法、そしてプラットフォームの特異性に対処するための通常のジャンク修正を見つける必要があります。カスタムCPUにDOOMをポートするのはさらに困難です。なぜなら、それが壊れたときに、コードが間違っているのか、CPUが間違っているのかわからないからです。良い点としては、Ozklがdoomgenericを作成し、ポートプロセスを簡素化してくれたことです。この簡略化にもかかわらず、私たちは多くの課題に直面しました。私の友人Liamがポートプロセスの主導権を握り、おそらく彼のブログで洞察を共有するでしょう。多くの課題の中でも、ファイルシステムの問題、レンダリングの課題、そして奇妙なことにprintfに関する問題が多すぎて、彼は独自のバージョンを書くことになりました。最も奇妙な問題は、printfが時々機能し、他の場合は機能しなかったことでした。
[画像: 最初に何かがレンダリングされた様子]
これらのバグの多くはCPUのエラーを露呈しました。例えば、システムが数百の命令とジャンプにまたがる無限ループに陥ることが頻繁にありました。他の times は、ランダムな理由で、意味のない場所にジャンプしているように見えました。しかし、DOOMプログラム全体を一度にデバッグすることは不可能だったので、私たちはそれを部分に分解し、徐々に複雑なプログラムをテストしました。時にはキャッシュアービターとMIG CDCが問題に直面し、ライトバック要求をドロップすることがありました。時には即値が誤って計算され、他の時にはDCacheが命令データを上書きしました。これらの問題の一部は、私たちの最初のシングルサイクルプロセッサに由来しており、これまで遭遇したことがなかっただけでした。しかし、最終的には、シミュレーションで全てを機能させることができました。
[画像: シミュレーションで実行されているDOOM]
しかし、ハードウェアではどうしても動作しませんでした。私たちが書いたどのプログラムも動作しましたが、DOOMは単純に動作しませんでした。ランダムな場所で停止し、ランダムなアドレスにジャンプし、半単語の命令を読み取り始めるように見えました。これは私をしばらくの間困惑させました。全く意味が分かりませんでした。MIGシミュレーションに問題があるはずです。なぜなら、それは容易にシミュレートできなかった唯一の部分だったからです。しかし、私が書いたすべてのメモリテストは、シミュレーションとハードウェアの両方で完璧に動作しました。何時間も悩んだ後、DDR3メモリをプログラムをロードする前にランダムな値で初期化するようにシミュレーションを変更することにしました。これはDOOMを壊しましたが、他のプログラムは壊しませんでした。DOOMは初期化されていないメモリがゼロになっていると仮定していたようですが、実際にはそうではありませんでした。いくつかのリンカとアセンブラの修正の後、DOOMはついにハードウェアにロードされました。
その後は比較的順調に進み、DOOMを毎秒0.7フレームという丸い数字で実行できるようになりました。実際には1フレームあたりの秒数であるべきです。これが、私がこのブログを終える予定だった場所です。私たちは目標を達成しました。しかし、0.7 FPSでは満足できませんでした。例えば、線形代数を勉強しようと座りましたが、代わりにCPUの最適化を始めました。私は中毒なのかもしれません。
30 FPSへの道
1 FPSのDOOMはかなり見劣りします。確かに印象的ですが、プレイ可能ではありません。私たちはスライドショーを見るだけでなく、DOOMをプレイしたかったのです。最も簡単な速度アップは、クロック速度を上げるだけです。100MHzから125MHzに引き上げたところ、FPSは約20%向上しました。メモリレイテンシはCPUコア速度から切り離されているため、これは正確に25%ではありません。次の最適化は、CPUのフェッチステージで行われました。元のフェッチ設計は非常に非効率的で、速度よりも正確性に重点を置いていました。そのため、命令ごとにICacheに2回要求を出すことが頻繁にありました。これを修正したことで、約2.5 FPSになり、300%以上高速化しました。
しかし、この時点では、パフォーマンスの向上は少し困難になりました。私は命令を追加することに着手しました。乗算演算子を実装しましたが、除算や剰余は実装しないことにしました。なぜなら、それらはパイプラインの複雑さを増大させるからです。そのため、CPUはRV32I-ZMMUL CPUになりました。これにより、さらに1 FPSが追加され、3.5 FPSになりました。目標の15 FPSを考慮すると、これはかなり残念でしたが、それでも正しい方向への一歩でした。
その後、CPU時間を使用している関数を詳しく調べたところ、画面バッファからVGAコントローラーのBRAMにデータをコピーするのがコストがかかることに気づきました。これはメモリ帯域幅を圧迫し、キャッシュをフラッシュしました。そこで、コードを変更してVGA BRAMに直接書き込むようにしました。同時に、キャッシュの読み取りヒットをパイプライン化して、レイテンシを2サイクルから1サイクルに短縮できることに気づきました。これらの組み合わせにより、約6.7 FPSになりました。
ここから、パイプラインを大幅に変更せずに速度を改善する簡単な方法はあまりないように見えました。現在、アウト・オブ・オーダー処理パイプラインに取り組んでおり、現在のパイプラインのほとんどを上書きすることになるため、このパイプラインにあまり時間を投資したくありませんでした。しかし、まだ1つだけレバーを引くことができました:コンパイラ最適化です。現在実行しているDOOMのバージョンは、O0でコンパイルされていました。これは、コンパイラがコードを全く最適化しないことを意味します。これは簡単な変更のはずです。0を2に変えるだけで、すべてが機能するはずです。しかし、試すたびにクラッシュし、その理由を理解できませんでした。当初はCPUのエラーだと思っていました。なぜコンパイラ最適化が私たちのコードを壊すのか? しかし、何時間もデバッグした後、問題の特定に成功しました。ハードウェアタイマーのMMIOポインタをvolatileとしてマークしていませんでした。コンパイラは、タイマーに書き込んでいないことを見て、コードから最適化していました。最適化について学ぶ際に、このブログ記事が役立ちました。この問題を修正した後、ゲームは完璧に動作しました。
[動画: DOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOM!!!!!!!]
では、どこまで到達したのでしょうか? コンパイラ最適化の後、DOOMは15〜20 FPSでスムーズに動作し、非常にプレイしやすく、かなり楽しいものになりました。当時の人気がなぜあったのかが分かります。アウト・オブ・オーダー処理やその他の最適化により、最終的に30 FPSに到達することを目指しています。
最後に
DOOMのポートは、少しトラウマ的ではありましたが、楽しい経験でした。メモリとキャッシュについて多くのことを学びましたが、これほど大規模なシステムをデバッグする方法を学んだことが最大のメリットだったと思います。少し面白い話ですが、実行中の9秒間の動画を投稿したところ、現在200万回再生されており、これは驚異的です。今後の計画としては、アウト・オブ・オーダー処理の実装と、より良いメモリアクセスパターンに取り組んでいます。これにより、さらに高速に動作するはずです。おそらくその後、基本的なGPUを書き上げた後、Quake 2をポートできるかもしれません。うまくいけば、より大きなFPGAでも実行できるようになるでしょう(伏線)。
読んでくれてありがとう。質問があれば遠慮なく連絡してください! あ、私たちのdoomポート、CPU、そして200万回再生された動画へのリンクはこちらです。
AIの使用
いつものように、このブログ記事のいかなる部分もAIによって書かれたものではありません。私のブログで機械の考えを共有するのは、むしろ無意味でしょう。コードに関しては、AIは主にデバッグ、テストの作成、ヘルパースクリプトに使用されました。LLMは、数分で数百の潜在的な障害点を手続き的に生成できるため、テストの作成に非常に優れています。これは、DOOMで見つかった「 haystack の中の針」のようなバグを追跡するのに役立ちました。Python UARTパーサーのようなヘルパースクリプトを作成するのにも非常に役立ちました。自分で書くこともできますが、AIを使った方が速いです。実際のChiselに関しては、ほとんどすべて手書きでした。いくつかのケースでは、以前のコード(BlueSpec、Verilog、または他のChiselモジュールで書かれたものの一部)からのリファクタリングにAIの助けを借りました。なぜなら、怠惰だったからです。また、すべてがAIによって行われると、このようなものを作る喜びが失われます。