2022 Advent Of Code: Cathode-Ray Tube

ふと自分が面白いと思った問題を記録しておこうと思い立った。特に視覚化できるものがいい。もし余力があれば毎日の問題をノートにまとめようと思う。とにかく、Advent Of Code Day10 の問題がかなり面白かったので、ひとまず記録しておく。

Part1

問題の第1パートは比較的シンプルで、2つの命令（noop と addx）しか実行できないCPUを実装するというものだ。このCPUにはXレジスタが1つあり、特定のサイクルにおけるレジスタの値を計算する。命令の説明に従って入力をもとに計算すれば、すぐに答えが出るはずだ。問題の説明文にはハードウェアに関する知識がいくつか含まれていて、問題を解くこと自体には影響しないものの、個人的にとても面白いと思ったので、後で詳しく掘り下げてみたい。

class CPU {
  x: number;
  cycles: number;

  constructor() {
    this.x = 1;
    this.cycles = 0;
  }

  tick() {
    this.cycles += 1;
  }

  noop() {
    this.tick();
  }

  addx(arg) {
    this.tick();
    this.tick();
    this.x += parseInt(arg);
  }
}

Part2

第2パートはずっと面白い。このレジスタは実はスプライト（Sprite）の位置を表しており、サイクル数は現在画面のどこを描画しているかを示している。問題文にはリンクが1つ貼られていた – Racing the Beam。コードに画面描画のロジックを追加すれば完了だ。

# を描画するかどうかの判定ロジックはビット演算（bitwise）でも実装できる。例えば 0x111000 >> register でシフトさせてスプライトの位置を表し、現在のサイクルとAND演算を行えば、現在の画面の文字が得られる。僕の場合はちょっと手抜きをして、単純に1つずつ比較することにした：

class CPU {
  // ...

  draw() {
    const column = this.cycles % 40;
    if (column === 0 && this.cycles !== 0) {
      this.screen += "\n";
    }

    if (this.x - 1 === column || this.x === column || this.x + 1 === column) {
      this.screen += "#";
      return "#";
    } else {
      this.screen += ".";
      return ".";
    }
  }
}

ここで簡単なビジュアライゼーションを作成してみた。テキストボックスに命令を入力して Execute を押すと、命令に従って描画が行われる。（注意：addx と noop のみ対応）

書き終えた後、命令から画面の画像を描画するのは簡単だが、その逆ははるかに難しいことに気づいた。つまり、ある画像が与えられたときに、それに対応する命令を生成することだ。これを実現するためには、サイクル数を計算しながら次のピクセルが生成される位置を動かさなければならず、しかも早すぎても遅すぎてもいけない。Reddit 上の議論を見てみたら、同じことを考えている人がいて、ASCII画像を渡すと対応する命令を生成するコードをPythonで書いていた。

Atari 2600

問題で触れられている Atari 2600 のように、初期のゲーム機には専用のビデオフレームバッファ（video frame buffer）がなく、CPUのメモリも極めて小さかった（わずか 128KB）ため、画面全体を描画するには全く足りず、メモリ（RAM）を極力再利用する必要があった。

このように描画計算を必要とするプログラムでは、通常フレームバッファを使用してCPUの負荷を分散させる。CPUは対応する位置のピクセルをフレームバッファに流し込むだけでよく、GPUが残りの処理（適切なタイミングでの描画や、対応する出力フォーマットへのエンコード・デコードなど）を担当する。しかし、フレームバッファの助けがない状況では画像を実行時にリアルタイムで演算しなければならず、エンジニアは限られたメモリの中でデータをあちこちやりくりするしかなかった。

問題は、CPUが命令を実行するのにも時間（サイクル）がかかることだ。メモリの移動が遅すぎても早すぎてもフレーム落ちにつながるため、正確なタイミングでメモリを移動させなければならない。これはまるでCRT（ブラウン管）の電子ビームと競争しているようなものであり、そこから Racing the Beam という名が付けられた。

数々の制約を理解した上で、改めてAtari版のパックマン（Pac-Man）を見てみると、涙が出るほど少ないメモリと信じられないほど遅いCPUでゲームを作り上げたのはまさに奇跡だと感じる。僕があの時代のエンジニアでなくて本当によかった。さもなければ失業していただろう。

Wikipedia を見てみると、Atari 2600 は MOS 6507 を採用して開発されたらしい。Wikipediaの記述によると、MOS Technology がAtariゲーム機の開発のために特別に改良したもので、6502の半額だったという。

2年前に任天堂の歴史を読んだ後、好奇心から MOS 6502 を購入したのだが、6502には内蔵ROMがない。それに僕の理解では、6502はパラレルROM（Parallel ROM）を使わなければデータを読み取れないが、今ではほぼシリアルEEPROM（Serial EEPROM）しか手に入らない。そのため、6502を触って遊んでみる計画はずっと棚上げになっていた。今回のエピソードを読んでまた少しやる気が出てきた。（とはいえ、パラレルEEPROMをどこで買えばいいのかはいまだに分からないが）

Clock Circuit

CPUを正常に動作させるためには、通常、発振器（オシレーター）を使って一定の周波数を生成する必要がある。しかし、なぜこの発振器が必要なのだろうか？ Turing Complete というゲームをクリアして初めて、僕はこのことを真に理解できた。

CPUの中にはたくさんの回路が存在する。加算器や論理ゲートのように非常に単純な回路もあり、その出力は完全にその瞬間の入力によって決まる。関数で表すなら $f(x) = y$ だ。デジタル論理回路では、このような回路を組み合わせ回路（Combinational）と呼ぶ。

もう一つは記憶性を持つ回路で、レジスタなどがこれに当たる。その背後にある仕組みはフリップフロップ（flip-flops）回路によって構成されている。この種の回路は記憶性を持ち、出力は入力だけでなく、現在の状態によっても決定される。デジタル論理回路では、このような回路を順序回路（Sequential）と呼ぶ。記憶性を持つということは当たり前のように聞こえるかもしれないが、チューリング完全を達成するための必要条件の一つだ。

なぜ発振器が必要なのかという話に戻ると、主な理由は前述の状態変化がすべて同一のタイミングで発生することを保証するためであり、それを実現するには統一されたクロックソースが必要になる。例えば、レジスタ r1 とレジスタ r2 の値を加算してレジスタ r1 に保存する命令を実行したいとしよう。

add r1, r2

実際の回路では、r1 の値と r2 の値は同時に取り出されて加算回路に送られ、結果が得られた後に r1 に書き込まれる。以下のように順次実行されるわけではない：

• r1 の値を取り出す
• r2 の値を取り出す
• 加算回路に送る
• 結果を得て r1 に書き込む

加算回路が受け取る入力が正しいことを保証するために、統一されたクロックトリガー信号を通じて初めて、レジスタの変化が一貫していることを保証できるのだ。

ただし、ここで少し補足しておくと、低消費電力や組み込み向けのCPUを除き、現代のCPU（IntelやAMDを含む）のアーキテクチャは途方もなく複雑であり、CPUの性能を最大化するために多くの魔法のような工夫が施されていて、前述したほど単純ではない。例えば：

1. Instruction Pipeline：CPUによる命令の実行は Fetch、Decode、Execution、Write Back の4大ステージに分けることができ、特定の条件下ではライトバックが完了する前に次の命令のフェッチを開始できる。
2. Out of order execution：命令列をCPUが回路の状態に応じて順不同で（命令の順番通りではなく）実行する。
3. 分岐予測（Branch Predictor）：一連の命令がどの分岐に進むかを巧みに予測する。

実行サイクル

タイミングが要求されるアプリケーションにとって、実行サイクルは極めて重要だ。なぜなら、タイミングが不正確だと全く異なる結果をもたらす可能性が高いからだ。この点については、以前僕が書いた2つの記事でより詳細に触れている。

• 用 Arduino 與 ESP32 打造空氣品質監測應用（2）- 資料溝通篇 UART
• Raspberry Pi pico PIO 初探

一般に、こうした精密なタイミング制御が必要なアプリケーション（または通信プロトコル）は、専用のハードウェアで処理されることが多い。しかし、ハードウェアの制約（UARTのポート数に限りがあるなど）があったり、利用したいプロトコルがハードウェアでサポートされていなかったりする場合がある。そうした際にCPUを使ってソフトウェア的に実装しようとすると、bit banging の問題に直面し、CPUへの負荷が過大になってパフォーマンスに影響を与えてしまう。