2022 Advent Of Code: カソード線管

突然、自分が面白いと思ったテーマを記録しておくべきだと思いつきました。特に視覚化できるものについてです。もし余力があれば、毎日のテーマをノートにまとめたいと思います。とにかく、私は Advent Of Code Day10 のテーマがかなり面白いと思ったので、まずは記録しておきます。

Part1

問題の第一部は比較的単調で、2つの命令（noopとaddx）のみを実行するCPUを実装する必要があります。このCPUにはXレジスタがあり、特定のサイクルでのレジスタの値を計算します。指示に従って、入力に基づいて計算すれば、すぐに答えが出るはずです。問題の説明には、ハードウェアに関するいくつかの知識が含まれていますが、解決には影響しないものの、私はそれが非常に興味深いと思っていますので、後で詳しく話しましょう。

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

第二部はずっと面白くなります。このレジスタは実際にはスプライトの位置を表していて、サイクル数は現在の画面の描画進捗を示します。問題の記述には、Racing the Beamというリンクが示されています。プログラムに画面描画のロジックを追加すれば、すぐに完成します。

#を描画するかどうかのロジックはbitwise演算を使って実装できます。例えば、0x111000 >> registerでスプライトの位置をオフセットし、現在のサイクルとANDを取ることで、現在の画面の文字を得ることができます。ここでは少し手を抜いて、直接一つずつ比較しました：

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のディスカッションを見たところ、同じ考えを持っている人がいた、彼はPythonを使ってASCII画像を入力すると対応する指令を生成するプログラムを書いていました。

Atari 2600

問題に挙がっているAtari2600のように、初期のゲーム機には追加のビデオフレームバッファがなく、CPUのメモリも非常に少なく（128KBしかありません）、画面全体を描画するには全く不十分でした。そのため、メモリ（RAM）をできる限り再利用する必要がありました。

このように描画計算が必要なプログラムでは、通常はフレームバッファを使用してCPUの負担を軽減します。CPUは対応する位置のピクセルをフレームバッファに投げ込み、GPUが残りの処理を行います。例えば、正しいタイミングで描画したり、出力フォーマットにエンコード・デコードしたりします。しかし、フレームバッファがない場合、画像をリアルタイムで計算する必要があり、エンジニアは限られたメモリの中でデータを移動させるだけです。

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

この多くの制約を理解した後、Atariでのスプライト（Pac-Man）を振り返ると、メモリが非常に少なく、CPUが非常に遅い状況でゲームを作り上げたことは本当に奇跡だと思いました。幸いなことに、私はその時代のエンジニアではないので、失業することはなかったでしょう。

ウィキペディアを見てみると、Atari 2600はMOS 6507を使用して開発され、ウィキの説明によれば、MOS TechnologyがAtariゲーム機の開発のために特別に改良したもので、6502の半額で済むとのことです。

2年前に任天堂のストーリーを見た後、好奇心からMOS 6502を購入しましたが、6502には内蔵ROMがなく、私の理解では6502はParallel ROMを使用しなければデータを読み取れません。しかし、現在ではほとんどSerial EEPROMしか購入できないため、6502を試す計画はずっとお蔵入りになっていましたが、この話を見た後、ちょっとやる気が出ました。（ただし、Parallel EEPROMをどこで買うかはまだ分かりません）

Clock Circuit

CPUを正常に動作させるためには、通常、オシレーターを通じて固定周波数を生成する必要があります。しかし、なぜオシレーターが必要なのでしょうか。このことを、Turing Completeをプレイした後に初めて理解しました。

CPU内部には多くの回路があり、その中には非常にシンプルなもの（加算器や論理ゲートなど）もあれば、現在の入力によって完全に出力が決まるものもあります。関数で表すと、$f(x) = y$となります。デジタルロジックでは、こうした回路をCombinatorialと呼びます。

もう一つのタイプの回路は、メモリを持つもので、レジスタのように、内部の原理はフリップフロップ回路で構成されています。このタイプの回路はメモリを持ち、出力が入力だけでなく、現在の状態によっても決まります。デジタルロジックでは、こうした回路を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つの主要なステージに分けられ、特定の条件下では、まだwrite backを行う前に次の命令のfetchを始めることができます。
2. Out of order execution：一連の命令がCPUによって回路の状態に従って順不同で実行されることがあります（命令の順序に従わない）。
3. Branch Predictor：特定の命令が進むであろう分岐を巧みに予測します。

実行周期

タイミングが必要なアプリケーションにとって、実行周期は非常に重要です。なぜなら、タイミングが正しくないと、全く異なる結果を引き起こす可能性が高いからです。この件については、以前書いた2つの記事でさらに詳細を見ることができます。

• ArduinoとESP32で空気品質監視アプリを作る（2）- データ通信編 UART
• Raspberry Pi pico PIO 初探

一般的に、精密なタイミング制御が必要なアプリケーション（または通信プロトコル）では、専用のハードウェアが用意されますが、時にはハードウェアの制約（例えばUARTの制限）や、使用したいプロトコルがハードウェアでサポートされていない場合があります。その場合、CPUを通じて実装すると、bit bangingの問題に直面し、CPUの負担が過大になり、性能に影響を与えることになります。