2022 Advent Of Code: カソード線管

突然、自分が面白いと思ったトピックを記録することに思い至りました。特に視覚化できるものに興味があります。余力があれば、毎日のトピックをメモに書いてみます。とにかく、私はAdvent Of Code Day10の問題がかなり面白いと思ったので、一旦記録しておきます。

Part1

問題の第1部分は比較的単調で、2つの命令しか実行できないCPU（noopとaddx）を実装する必要があります。この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

第2部分はさらに面白いです。このレジスタは実際にはスプライトの位置であり、サイクル数は現在の画面のどこまで描画されているかを示します。問題の説明には、Racing the Beamというリンクがあります。コードに画面描画のロジックを追加すれば完了です。

# を描画するかどうかのロジックもビット演算で行うことができます。たとえば、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 ".";
    }
  }
}

ここで、シミュレーションを行うための簡単な視覚化が行われます。テキストボックスに命令を入力し、実行ボタンを押すと、指示に従って描画されます。（注意：addxとnoopのみサポートされています）

Advent Of Code Day 10 Simulation

書いてみた後、指令を画像に変換するのは簡単ですが、逆に画像を指令に変換するのは難しいことに気づきました。つまり、画像が与えられた場合に対応する指令を生成する必要があります。このことを達成するためには、サイクル数を計算しながら次のピクセルの生成位置を移動させる必要がありますが、早すぎるか遅すぎるといけません。Redditのディスカッションを見てみると、同じ考えを持つ人がいました。彼はPythonを使用してASCII画像を入力すると対応する指令が生成されるプログラムを書きました。

Atari 2600

問題で言及されているAtari2600のような早期のゲーム機は、使用する追加のビデオフレームバッファがなく、CPUのメモリが小さすぎる（わずか128KB）ため、画面全体を描画するのに十分ではありません。したがって、メモリ（RAM）を最大限に再利用する必要があります。

このような描画計算を必要とするプログラムでは、通常、CPUの負荷を軽減するためにフレームバッファが使用されます。CPUは対応する位置のピクセルをフレームバッファに送り込むだけで、GPUが残りの処理を行います。正しいタイミングで描画するか、エンコードやデコードして対応する出力形式に変換します。しかし、フレームバッファの補助がない場合、画像はリアルタイムに計算する必要があり、エンジニアは限られたメモリ内でデータを移動するしかありません。

問題は、CPUが命令を実行するためにも時間（サイクル）が必要であることです。メモリの移動が早すぎるか遅すぎる場合、フレームのドロップが発生する可能性があるため、正しいタイミングでメモリを移動する必要があります。これはまるでCRTの電子ビームと競争しているようなものであり、それがRacing the Beamという名前の由来です。

これらの制約を理解した後、Atari上での小さなスプライト（パックマン）を見返してみると、メモリが非常に少なく、CPUが非常に遅い状況でもゲームを作成できたことは奇跡だと思います。幸いなことに、私はその時代のエンジニアではないので、失業することはないでしょう。

ウィキペディアを見ると、Atari 2600はMOS 6507を使用して開発され、MOS TechnologyがAtariゲーム機向けに特別に改良したもので、6502の半額で提供されました。

2年前、任天堂のストーリーを見た後、MOS 6502を購入しましたが、6502にはROMが内蔵されていません。そして、私の理解では、6502はパラレルROMを使用してデータを読み取る必要があるのですが、現在はほとんどシリアルEEPROMしか入手できないため、6502のプロジェクトを試すことができませんでした。このストーリーを読んだ後、少しやる気が出ました。（ただし、どこでパラレルEEPROMを購入できるかはまだわかりません）

クロック回路

CPUが正常に動作するためには、通常、振動子を使用して固定の周波数を生成する必要があります。しかし、なぜそのような振動子が必要なのでしょうか？私はTuring Completeをプレイした後に、このことを本当に理解したと言えるでしょう。

CPUには多くの回路があります。加算器や論理ゲートなど、いくつかの回路は非常に単純で、出力は現在の入力に完全に依存します。関数的な観点からは、 $f(x) = y$ と表されます。このような回路はデジタルロジックではCombinatorialと呼ばれます。

また、フリップフロップ回路を使用してメモリを持つ回路もあります。これらの回路は状態を持ち、出力は入力だけでなく、現在の状態にも依存します。デジタルロジックでは、これらの回路をSequentialと呼びます。メモリを持つことは当たり前のことのように思えますが、それはチューリング完全性を達成するための必要条件の1つです。

なぜ振動子が必要なのかについては、上記で説明した状態の変化が同じタイミングで発生することを確保するためであり、そのためには統一されたクロック信号ソースが必要です。例えば、次の命令を実行したいとします。レジスタr1とレジスタr2の値を加算し、その結果をレジスタr1に保存します。

add r1, r2

実際の回路では、r1の値とr2の値は同時に取り出され、加算回路に送られ、結果がr1に書き込まれます。順番に実行するのではありません。

r1の値を取得
r2の値を取得
加算回路に入力
結果を取得し、r1に書き込む

加算回路が正しい入力を取得するためには、統一されたクロックトリガ信号を使用する必要があります。しかし、ここでも少し強調したいことがあります。低消費電力や組み込み用途以外では、現代のCPU（IntelやAMDを含む）のアーキテクチャは非常に複雑であり、CPUの性能を最大限に引き出すためにさまざまなトリックが使用されています。前述のように単純ではありません。例えば：

命令パイプライン：CPUの命令実行はFetch、Decode、Execution、Write Backの4つのステージに分けられ、一部の条件下ではWrite Back前に次の命令のFetchを開始することができます。
順序実行：一連の命令をCPUが回路の状態に基づいてランダムに実行することができます（命令の順序に従わない）。
分岐予測（Branch Predictor）：分岐がどちらに進むかを推測するためのテクニック。

クロック周期

タイミングが必要なアプリケーションでは、実行周期が非常に重要です。なぜなら、タイミングが正しくない場合、完全に異なる結果になる可能性があるからです。詳細は、私の以前の2つの記事で確認できます。

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