prime&#39;s diary

BTBの実装はBTB.scalaにあります。

BTBは小さなメモリに探索結果を保存することで実現します。

分岐元アドレスの下位ビットをキャッシュメモリのアドレスとして用います。もし下位ビットが同じで上位ビットが異なるアドレスについてキャッシュに書き込むと、以前の内容は消えてしまいますが、そのときは再度探索を行うことにします。

下位ビットを元に直接保存場所が決定する方式のキャッシュを、ダイレクトマップ方式といいます。実装は簡単ですが、セットアソシアティブ方式等に比べるとキャッシュミスが増加してしまいます。

実験の結果、ダイレクトマップ方式でも十分な性能向上が得られたため、ダイレクトマップ方式のままでいくことにしました。

キャッシュメモリにはvalidフラグ、分岐元アドレスの上位ビット(キャッシュメモリのアドレスとして使わなかった部分)、分岐先アドレスを保存します。

validフラグは、キャッシュメモリから読んできた内容が有効かを判定するのに必要です。キャッシュメモリを最初validが0のデータで埋めておき、キャッシュに書き込むときにはvalidが1のデータを書き込むことで、内容の有効性を判定できます。

分岐先アドレスの上位ビットは、キャッシュメモリから読んできた内容が欲しいアドレスの内容かどうかを判定するのに必要です。

命令フェッチのレイテンシーの隠蔽

命令フェッチには現状2サイクル必要です。分岐命令を処理した次のサイクルでは、分岐後の命令がまだフェッチできていないため、このままでは1サイクルストールする必要があります。

そこで、BTBに分岐先アドレスだけでなく、ジャンプ後の次の命令も一緒に保存することにします。

BTBヒット時には、命令メモリから命令がやってくるのを待たずに、BTBに保存した命令を使うことで、命令フェッチのレイテンシーを隠蔽し、パイプラインを止めることなく分岐が可能になりました。

ベンチマーク

ベンチマークに用いているHanoi4.bfでの結果をまとめてみました。Hanoi4.bfは455bytesであるため、512エントリあれば衝突は絶対に発生しなくなります。

BTBエントリ数	命令実行サイクル数	ジャンプ先探索サイクル数
なし	14803	21352
2	14803	12224
4	14803	12172
8	14803	11491
16	14803	7776
32	14803	1957
64	14803	1643
128	14803	1643
256	14803	1643
512	14803	1643

エントリ数がそれなりにあれば、ジャンプ先探索にかかるサイクル数が、BTBがない状態と比べて1/10未満になっています！全体でも半分以下のサイクル数になっており、すばらしい性能向上です。

また、64エントリ以上はサイクル数がかわっていないことから、衝突が起きていないことが分かります。

ちなみに、BTBの追加でUltra96-V2 | Avnet Boardsでの最大動作周波数は220MHz程度と、若干下がってしまいました。それでもサイクル数の削減の効果の方が圧倒的に大きいため、実時間ベースでも約半減になっています。動作周波数を上げるボトルネックになっているクリティカルパスは、命令アドレス生成・命令フェッチまわりのようです。これはちょっとすぐには解決が難しそうです。

今後の展望

ここまでの改良で、（BTBエントリが衝突しない限り）1サイクルあたり1命令実行に限りなく近づけることができました。個人的にここまでは実装したいな、と思っていたのでよかったです。

ここからさらに性能を向上させるには、2通りのアプローチがあります。

1サイクルの間に1命令より多くの命令を処理する
- op fusionとfusion済み命令キャッシュの実装
- スーパースカラ実行の実装
動作周波数を上げる
- パイプラインステージの分割

構造の複雑化で、最大動作周波数が下がってきているので、パイプラインステージの分割はぜひともやりたいところです。命令デコードと実行をステージ分割することで、op fusionにつなげられるとよりうれしいですが、果たして…

スーパースカラ実行は、Brainf*ckの命令レベルの並列性のなさが原因で、圧倒的に難易度が上がりそうで、実装できるかちょっと自信がないです。

*1:アウトオブオーダー実行をしていて分岐先アドレスの計算を待つ必要がある、ということはありますが、その計算が終わりさえすれば分岐先は判明します

*2:もちろん、実行するプログラムによるが、典型的には

2023-12-30

Brainf*ckを直接実行できるCPUを作った (その3) パイプライン化とデータキャッシュ【いろいろなコンピューター Advent Calendar 2023 12日目】

この記事はいろいろなコンピューター Advent Calendar 2023の12日目の記事です（大遅刻）。

この記事は10日目の記事の続きです。ぜひ先にそちらをご覧ください。

10日目の記事で実装したいとしていた

命令書き込みモードを作る
[ によるジャンプと ] によるジャンプで状態を分けているが、進む向きが違うだけなので共通化する

はすぐにできたので、この記事ではついにCPUのパイプライン化を実現します。

Brainf*ck CPUにおけるデータハザード

Brainf*ck CPUをパイプライン化するうえでもっとも困難なことは、データハザードです。

1命令でメモリからのデータの読み込み→計算→メモリへのデータの書き込みを行うため、メモリアクセスを含めてパイプライン化する必要があります。連続で+や-を行った場合、当然読み書きするアドレスは同じです。そこをなにも考えずにパイプライン化すると、直前の命令で得られた結果をメモリに書き込む前に、次の命令が必要とするデータの読み込みが発生*1してしまい、内容が壊れてしまいます。これをデータハザードといいます。

レジスタマシン（今日一般的なCPUのアーキテクチャ）では、EXステージの結果をレジスタに書き込むと同時に、（必要なら）次の命令の入力に直接渡す、フォワーディングと呼ばれる方法が使われています。

Brainf*ck CPUでも、直前に使ったアドレスと同じアドレスにアクセスするのなら、そのデータをフォワーディングすることでデータハザードを回避できます。

しかし、アクセスするアドレスが変わるとデータを読み直す必要があり、このときはメモリからデータがやってくるまで待つ（ストールする）ことになります。これでは頻繁にストールしてしまい、あまり性能が出なくなってしまいます。

データキャッシュの実装

そこで、メモリの内容を一部だけCPU内に保持することにします。つまりデータキャッシュを実装すればよいことになります。

一般的なCPUに対するデータキャッシュでは、アクセス先を予測することは困難であるため、効率の良いキャッシュの実装はかなり難易度が高いです。幸いにも、Brainf*ckではデータアクセス先は1命令あたり高々1byteずつしか動かないため、データポインタの周囲数bytesを保持しておくだけでよいです。

今回は、データメモリに1サイクル後にアクセスできる想定で、データポインタの指す先とその前後1byteずつ、合計3bytesを保持するキャッシュを実装しました。

挙動としては、データポインタをインクリメントするときは、(データポインタ+2)番地のメモリを読みに行き、デクリメントするときは(データポインタ-2)番地のメモリを読みに行きます。

こうすることで、データポインタを移動させていったときに、データが欲しいときには常にキャッシュに載っているようにすることができます。

また、毎サイクルデータポインタの指す場所にキャッシュの内容を書き込みます。

データキャッシュの実装はDCache.scalaにあります。

パイプライン化

これで無事データハザードが解決できると、あとは比較的スムーズにパイプライン化することができました（デコード/実行が1ステージになっているなど、3ステージしかないのも楽な理由）。

分岐予測等は実装していないので、分岐（ジャンプ）が発生したときには、素直に命令フェッチからやり直します。

できたものがこちらになります。

今後の展望

直近で実装したいのは次の二つの機能です。

分岐先キャッシュの実装

パイプライン化の結果、実行時間の多くを[ ]命令の対応する] [を探すことに費やすようになりました。

ジャンプ先アドレス（とジャンプ先からの数命令）をキャッシュすることで、即座にジャンプできるようになると、大幅な高速化が期待できます。

パイプラインステージの追加

FPGAのBlock RAMは読みだしたデータを一旦レジスタに受けることで、アクセスまでのサイクル数増加と引き換えに、最大動作周波数の向上を狙うことができます。現状ではレジスタで受けていないため、動作周波数をあまり上げることができません。

今の設計では、私の持っている Ultra96-V2 | Avnet Boards では170MHz程度が上限のようでした。

メモリからの読み込みをレジスタで受け、追加のパイプラインステージを追加することで、最大動作周波数を向上させ、トータルの性能向上を狙っていきたいです。場合によっては、命令デコードと命令実行をステージ分割することで、さらなる最大動作周波数の向上が可能かもしれません。

(追記) その4はこちら

*1:図における命令Bのloadが命令Aのwritebackに先行してしまう

2023-12-11

Brainf*ckを直接実行できるCPUを作った (その2) マルチサイクルCPU化【いろいろなコンピューター Advent Calendar 2023 10日目】

この記事はいろいろなコンピューター Advent Calendar 2023の10日目の記事です。（遅刻です　すみません…）

前日の記事

の続きとなっております。よければそちらからお読みください。

シングルサイクル・マルチサイクル・パイプラインCPU

CPUのマイクロアーキテクチャの設計には大きく分けて3種類あります。

シングルサイクルCPU

1命令を1サイクルかけて実行します。設計難易度的にはもっとも単純です。

シングルサイクルCPUでは命令のフェッチ、命令のデコード、レジスタの読出し、演算処理、レジスタやメモリへの書き込みといったすべての処理を1サイクルに詰めこみます。そのため、クリティカルパス(一連の処理の流れのうち、最も時間のかかる経路)が長くなり、動作周波数を上げづらいという問題があります。

リソースや性能の観点から実用にされることはほとんどありません。

マルチサイクルCPU

1命令を複数サイクルかけて実行します。何サイクルかけるかは設計により異なります。上の画像の例では、1命令の処理をIF(Instruction Fetch), ID(Instruction Decode), Ex(Execute), WB(Writeback)の4ステージを4サイクルかけて処理しています。

一見、シングルサイクルよりサイクル数が増える分だけ遅そうですが、回路のクリティカルパスを短くできるため、動作周波数を上げて補うことができます。

また、1命令をNサイクルで処理するとき、異なるステップで共通して使うモジュールを一つにまとめることで、リソースの有効活用が可能です。

パイプラインCPU

1命令を複数サイクルかけて実行しますが、各ステージを完全に分離することで、各ステージが命令1を処理し終わった次のサイクルで、命令2の処理を行い、その次のサイクルでは命令3の処理を行い…とすることで、1サイクルあたり(最大で)1命令を処理できます。

マルチサイクルCPUと同様、クリティカルパスを短くできるため、シングルサイクルCPUよりも動作周波数を上げることができ、トータルでシングルサイクルCPUより単位時間当たりに処理できる命令数が向上します。

パイプライン処理では、命令同士にデータの依存関係がある場合に、後続の命令がデータを必要としていてもまだレジスタに書き戻されていない、といったことも発生します。そのため、レジスタを経由せずにパイプラインのステージ間でデータをフォワーディングする、などといった対策が必要です。

さらに、分岐命令が実行されて実行パスが変わった時、すでにフェッチした命令を一旦捨てて分岐先の命令を読み直す、といった処理も必要です。このため、シングルサイクルCPUやマルチサイクルCPUよりずっと設計難易度が高まります。

今日は扱いませんが、現代の高性能なCPUは単にパイプライン化されているだけでなく、1サイクルで複数の命令を実行することで、さらに高い性能を実現しています。

Brainf*ck CPUをマルチサイクルCPU化する

昨日作ったBrainf*ck CPUはシングルサイクルCPUでした。今日はこれをマルチサイクル化してみます。ついでに、メモリをFPGAのBlock RAMで実装できるようにしていきます。

できたものがこちらになります。

Chiselで生成したSystemVerilogファイルを、Vitisに読み込ませてsynthesisして、命令メモリ、データメモリがBlock RAMに推論されることを確認しています。

主な変更点は次の通りです。

命令実行時の状態を3つに分割

Fetch, Execution, Writebackの3ステージを作りました。これまでは実行中は([ ]によるジャンプ先探索状態を除くと)Executionだけでした。

メモリアクセスのレイテンシーを考慮

Block RAMはアドレスを入力してからデータが出てくるまでに1サイクル以上かかります。これまでは即座にデータが返ってくることが前提の実装だったので、そこを修正しました。シングルサイクルCPUでは、そもそもこういうことはできないので、マルチサイクル化が必須でした。

今後の展望

直近で改善したいこととしては、

命令書き込みモードを作る
[ によるジャンプと ] によるジャンプで状態を分けているが、進む向きが違うだけなので共通化する
FetchとWritebackは簡単に同時実行可能なので、同時に実行する（計算上、ジャンプ先探索以外のスループットが1.5倍になる）

その先は、完全なパイプライン化やFPGA上での動作の実現、ジャンプ先キャッシュの実装を目指していきたいです。

(追記) その3はこちら

2023-12-09

Brainf*ckを直接実行できるCPUを作った (その1)【いろいろなコンピューター Advent Calendar 2023 9日目】【Scala Advent Calendar 2023 9日目】

この記事はいろいろなコンピューター Advent Calendar 2023の9日目の記事です。

Brainf*ckとは

Brainf*ck(この記事では一部伏字にして表記しています)は難解プログラミング言語のひとつです。

コンパイラがなるべく単純になるように設計されており、わずか8種の命令+ - > < [ ] . ,のみが存在する手続き型プログラミング言語です*1。

詳しい言語仕様等はEsolang wikiの記事 brainfuck - Esolang 等を参考にしてください。

仕様は単純ですが、チューリング完全なので、理論上はどんな計算でもすることができます。

Brainf*ck CPUを作る

今回は、Brainf*ckのコンパイラでもインタプリタでもなく、ソースコードを直接実行できるCPUを作りました。

できたものがこちらになります。

この記事の時点での実装はこちら:

ChiselというScalaのDSLで実装しました。ChiselはSystemVerilogやVHDLと同じRTL(Register Transfer Level)の回路設計言語ですが*2、Scalaによるリッチで現代的な書き味が特徴です。もっとも、私はまだScalaそのものにもChiselにもRTLにもあまり慣れていないため、その恩恵をあまり活用できていないですが…*3

この記事の時点では最適化等のない、単純な実装になっています。今後の記事で徐々に高速化や高機能化を進めていきます。

BFCPUの動作

命令メモリにソースコードが格納されており、コアがソースコードを直接解釈・実行します。

外部にin/outのストリームI/Oが生えており、ここから標準入出力を行うことができます。 reset/ready/start/finishedというコントロール用のI/Oも生えており、ここから実行をキックしたり終了したかの状態を得たりできます（現時点ではリセットは信号としては存在するが、データメモリを初期化しないため、正しく動作しない）。主にデバッグ用にステータスを出力するI/Oもあります。

コアの実装

ここからは内部の実装を解説していきます。

Core.scala bfcpu/src/main/scala/bfcpu/Core.scala at 862664008b6adf9b455a4b2eaed0e14198037698 · primenumber/bfcpu · GitHubがコア部分の実装です。

state という実行状態を管理するレジスタがあり、実行中、実行待機、対応する[を走査中、実行完了などの状態に応じて挙動の変わるステートマシンとなっています。 sExecuting が実行中に対応する状態です。

実行部分は、パイプライン化等はされていない、1命令1サイクル実行となっています。読んできた命令の内容に応じて、命令ポインタ、データポインタ、データの内容等を更新していきます。

現時点では、[ や ] によるジャンプでは、対応する ] [ まで1文字ずつ移動していく実装になっています。このため、実行にかかるサイクル数は実行する命令数よりもかなり多くなります。

命令・データ用にそれぞれメモリが用意されていますが、今はシングルサイクル実装なので、アドレスを入力すると、次のクロックで即座にアクセスできることが前提の実装になっています。このため、現時点ではFPGAのBlock RAM等を使うことができません。また、命令メモリを実行直前に書き換える方法を用意していないため、合成時に用意したソースコードをメモリに埋め込んで実行しています。

今後の改良ポイント

今後、数記事にわたって改良を施していく予定です（記事執筆時点では完全に未着手）。現時点でやりたいことをリストアップしてみました。

マルチサイクルCPUにして、メモリにFPGAのBlock RAMを使えるようにし、FPGAで使えるようにする
命令メモリを実行直前に外から書き換えられるようにする
パイプライン化で動作周波数を上げる
[ ]のジャンプ先をキャッシュして実行サイクル数を削減する
スーパースカラ実行で1サイクルに複数命令処理する
op fusionによる最適化: 例えば[-]はデータを0クリアするイディオムで、これを1サイクルで実行できると大幅な高速化が可能。

後半は難易度が高いですが、がんばってチャレンジしていきます！

(追記) その2はこちら

*1:Lazy Kという3種(SKI)または1種(iota)のコンビネータ―だけで計算できる関数型難解プログラミング言語がありますが、コンパイラの実装はBrainf*ckよりずっと難しいです

*2:つまりHLS(高位合成)ではない

*3:IOのFlippedとかConnection Operatorとかは確かに便利

2023-12-09

例え話の罠: 例え話と準同型

導入

何らかの議論をするときに、アナロジー、例え話をして説得力を持たせるテクニックは広く使われている。故事成語のもととなった寓話などがその代表である。

例え話による議論では、もとの複雑で想像が難しいシチュエーションAを、理解しやすいシチュエーションBに"投影"し、シチュエーションBの中での議論を行い、そこで出た結論を元のシチュエーションAに引き戻して当てはめる、ということが行われる。

例え話は一見非常に説得力のある議論ができるが、そこには落とし穴がある。騙されない、あるいは騙してしまわないよう、気を付けなければならない。

本記事では、例え話の問題点について見ていく。

準同型

突然話題が変わるが、数学には準同型という概念がある。ざっくり説明すると、数学的構造(群とか環とか線形空間とか)XとYがあって、Xの要素xをYの要素f(x)に写す関数(写像ということも多い) $f : X \rightarrow Y$ が準同型であるとは、fが数学的構造を保ったままXの要素をYの要素に写すことをいう。

群であれば、群Xの二項演算★と群Yの二項演算＊について $f(x_1★x_2) = f(x_1) ＊ f(x_2)$ が成り立つことが条件になる*1。

準同型の具体例

具体的な例をいくつか挙げてみよう。すでに準同型に慣れ親しんでいる人は、このセクションを読み飛ばしてもよい。（ちなみにここでの具体的な例の「例」はinstanceで、例え話の「例」のanalogyではない。）

実数係数の多項式全体の集合 $\mathbb{R}[x$ ]と、その上での加算、乗算を考えると、環という代数構造をなすことが知られている。たとえば多項式 $p_1, p_2$ がそれぞれ

$p_1 = x^3 + x^2 + x + 1 \\ p_2 = x - 1$

だったとき、その和と積は

$p_1 + p_2 = x^3 + x^2 + 2x \\ p_1 p_2 = x^4 - 1$

のようになる。ここで、多項式の不定元に、具体的な実数を多項式に代入することを考える。 0では面白くない*2ので、ここでは3を代入してみる。

$p_1|_{x=3} = 3^3 + 3^2 + 3^1 + 1 = 40 \\ p_2|_{x=3} = 3 - 1 = 2$

関数fを"多項式 $p(x)$ に対して、不定元に3を代入した結果 $p(3)$ を返す"と定義すると、fは $\mathbb{R}[x$ ]から $\mathbb{R}$ への関数になっている。実数全体の集合も（通常の）加算と乗算について環をなし、またこのfは可算と乗算の構造を保存する、つまり準同型であることが知られている。さきほどの $p_1,p_2$ で確認すると、

$f(p_1)+f(p_2) = 40 + 2 = 42 \\ f(p_1 + p_2) = f(x^3 + x^2 + 2x) = 3^3 + 3^2 + 2 \times 3 = 42 \\ f(p_1)f(p_2) = 40 \times 2 = 80 \\ f(p_1 p_2) = f(x^4 - 1) = 3^4 - 1 = 80$

となっており、ちゃんと加算と乗算について保存されている。

準同型の利便性と危険性

準同型は数学における非常に強力な道具で、Xの素性はよくわからないがYの素性はよくわかっていて、準同型 $f: X \rightarrow Y$ があったとすると、fとYについて調べることで、Xの素性の理解につなげることができる。

しかし、準同型を用いた議論をするときに忘れてはいけない重要なことがいくつかある。その一つが、考えている準同型が何に関する準同型なのか、ということである。環の準同型であれば、環の演算については保存するが、それ以外のことについては何も言っていないため、なんでも準同型で写した先で議論できるわけではないのである。

具体例で考える

先の多項式を例に挙げると、多項式には合成という演算がある。多項式を多項式関数だと思って関数合成をすると、その合成関数はまた多項式関数となる。

$p_1 = x^3 + x^2 + x + 1 \\ p_2 = x - 1$

とすれば、その合成は

$p_1 \circ p_2 = (x-1)^3 + (x-1)^2 + (x-1) + 1 = x^3 - 2x^2 + 2x$

実数も定数関数だと思えば、それについて合成を考えることができる。

$40 \circ 2 = 40$

ここで先のfが合成について保存するかどうかを見てみよう。

$f(p_1) \circ f(p_2) = 40 \circ 2 = 40 \\ f(p_1 \circ p_2) = f(x^3 - 2x^2 + 2x) = 3^3 -2 \times 3^2 + 2 \times 3 = 15$

このように、fは合成に対しては準同型ではない。従って、もし多項式の合成を含む議論をするのであれば、fを用いた実数上での議論に帰着することは(基本的には)できない。

翻って、例え話でも同じようなことが言えて、きれいな例え話があったとしても、その例え話がいま議論したいシチュエーションを正しくマッピングして、その構造を保存しているかをよく吟味しなければならない。

…ここまでで「なるほどたしかにそうだ」、と騙されてはいけない。

ここまでの文章自体が、「例え話」を「準同型」で例えて、その性質を議論するアナロジーになっている。しかし、例え話と準同型の対応が、その性質を語れるようなものになっていることを言っていない。

そもそもの話、ほとんどすべてのアナロジーは、対応関係の正確な定義もなければ、その対応の正当性を示すこともないため、数学の準同型とのアナロジー以前の問題で、全く議論にならない。議論として正しくないがぱっと見の説得力はあるため、自分に都合の良い対応と議論を持ってくることによって、あらかじめ用意した結論を出すための道具だと思った方がよいだろう。

今日の標語：

例え話はすべて詐欺です。

*1:群の構造を保つことを言うには、単位元と逆元を取る操作に関しても構造を保つことを言う必要があるが、それらは積の保存から導ける

*2:多項式の定数項が出るだけ

2023-12-02

CPU自体が準光速で動くことで計算時間を短縮するコンピューター【いろいろなコンピューター Advent Calendar 2023 1日目】

この記事はいろいろなコンピューター Advent Calendar 2023(さっき作った)の1日目の記事です。

背景

さて、昨今のCPUはどんどん高速化し、クロック周波数も5GHzを超えることは珍しくなくなりました。一方で、ここまで高速化すると問題になるのが光速です。

5GHzというのは50億分の1秒に1サイクルということなので、この間に光は真空中でも60mmしか進むことができません。媒質中では屈折率に反比例して遅くなるので、例えば屈折率1.5の光ファイバーがあったとすると、40mmほどしか進めません。

一方で、単位体積あたりに詰め込める計算ユニットやメモリセルは有限なので、大きな並列度を持った計算機を作ったり、大容量の記憶装置を持ったりするには、それに応じた体積が必要です。しかし、光に限らずあらゆるものは真空中の光速を超えることはできないので、大きくなればなるほど光速の制約がきつくなります。

記憶装置と光速の壁

簡単のため、CPUは大きさを持たず、空間中のある1点にあるとします。このCPUからアクセス要求をだしてからnサイクル以内にデータが帰ってくるには、アクセス要求とデータ返送が真空中の光速で到達するとして、メモリセルはCPUから $n*60/2=30n$ mm以内*1になければいけません。したがって、半径 $30n$ mmの球に入るメモリセルであることが必要条件となり、半径 $30n$ mmの球の体積は $\frac{4}{3} \pi (n * 30) ^ 3 \approx 113097.33n ^ 3$ mm³となります。

今、1mm³あたり1GiBのメモリを積めると仮定します（stacked DRAMの密度はたぶんこのくらいのオーダーになるはず、このあとの話的には定数倍が変わるだけなので、1MiBでも1TiBでもよいです）。すると、nサイクル以内にアクセスできる容量は約 $110n ^ 3$ TiBとなります。

全世界のデータ量が約100ZiBだとすると、これをすべておさめたメモリにアクセスするには半径約30m必要で、およそ1000サイクルかかることになります。今は全世界分で1000サイクルなので大したことはないですが、今後も人類の扱うデータ量が増大していくと、（メモリの3次元的な密度上昇が追いつかなければ）必要な体積とアクセス時間も増大していきます。

すべてを収めるメモリの大きさはどんどん大きくなり、やがて地球サイズを超え、太陽系を飲み込み、はるか星間空間、銀河系まで埋め尽くしていくことになります(もっとも、現在の物質密度で太陽系いっぱいにメモリを配置すると、ブラックホールが発生してしまいますが、ここはなんとかするとして)。こうなるとメモリアクセスのレイテンシーがあまりに大きくなり、1データにアクセスするのに年単位あるいはそれ以上の時間がかかってしまいます。これではなにか1回計算しいてる間に、寿命が尽きて死んでしまうことが多発し、人類は滅亡してしまいます。

コンピュートフローアーキテクチャ

この解決策として、本記事ではデータがやってくるのを待つのではなく、CPU自体を計算機利用者とともに光速に近い速度で動かすことで、大幅なアクセス時間削減を実現する計算機アーキテクチャを提案します。

まず、計算機利用者と利用するCPUを、光速に近い速度で移動できる宇宙船に搭載します。CPUはメモリセルに向かってアクセス要求を出す代わりに、自分でメモリセルのある場所まで航行します。

すると、計算機利用者とCPUからみると、メモリセルに到達するまでの主観時間は、相対論的効果によりメモリセルから見た時間より短くなります（追記: CPUから見ると、ローレンツ収縮によりメモリセルまでの主観距離が縮み、メモリセル側から見るとCPUの時間の進みが遅くなって見えます）。光速に近ければ近いほどどんどん主観時間は際限なく短くすることができ、これにより計算が高速化され、計算機利用者の寿命が尽きてしまうことを防ぐことができました。めでたしめでたし。

このアーキテクチャをコンピュートフローアーキテクチャと命名することにします*2。このアーキテクチャの計算機の構築にあたって、私の許諾等は不要です。作れるならな！

*1:通信が往復するので/2している

*2:データが流れるように移動しながら計算していく、データフローアーキテクチャのアナロジー

2022-12-04

架空伝統ゲーム「机戦」のAIを作るその1 【ボードゲーム・パズルプログラミング Advent Calendar 2022】

この記事は「ボードゲーム・パズルプログラミング Advent Calendar 2022」3日目の記事です（遅刻すみません）。