prime's diary

そすうの日々を垂れ流しちゃうやつだよ

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

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

adventar.org

Brainf*ckとは

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

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

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

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

Brainf*ck CPUを作る

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

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

github.com

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

github.com

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もあります。

コアの実装

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

BFCPUの大まかな構成

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はこちら

primenumber.hatenadiary.jp

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

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

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

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

導入

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

例え話による議論では、もとの複雑で想像が難しいシチュエーション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:多項式の定数項が出るだけ

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

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

adventar.org

背景

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

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

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

記憶装置と光速の壁

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

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

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

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

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

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

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

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

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

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

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

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

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

adventar.org

架空伝統ゲーム「机戦」とは

創作上の異世界ファイクレオネで遊ばれている（という設定の）伝統ゲームです。 日本机戦連盟では、それを実際に遊べるようにする様々な活動が行われています。

sites.google.com

今回から、机戦のAIを作っていきます。

今日の成果

  1. リポジトリを作りました。
    • もう半分くらいできたといっても過言ではありません（過言）。 github.com
    • リポジトリ名は東島通商語（という架空の言語）でのこのゲームの名前 cetkaik と AI から取りました（お気に入り）。
  2. ランダムプレイヤーを実装しました。 github.com 状態遷移が複雑で、ランダム要素もあるため、既存の実装GitHub - cetkaik/cetkaik_full_state_transitionを活用しています。
  3. 単純に役を作れるなら作る、駒をとれるなら取る、という戦略を実装したAI (greedy)を実装しました。 github.com
  4. cetkaik_full_state_transitionのバグを発見しました
    • 踏越え後の可能な行動をリストアップすると、非合法な行動が入ってしまうバグがあることを発見しました。近いうちに id:hsjoihs が直してくれるそうです。

今後の展望

踏越えルール等により、手の可能性が多く、何手も先まで探索することは非現実的です。 モンテカルロ法を利用したり、評価関数を実装したりすることにより、現実的な計算量で戦略的に行動するAIを作っていきたいです。

ととりにゃあ あつめて早し 最上川 それにつけても 金の欲しさよ - あるいは、ととりにゃあの語感の良さについて 【ととりにゃあ Advent Calendar 2021 Day 19】

ネタ

こんばんは、そすうぽよです。 この記事はととりにゃあ Advent Calendar 2021の19日目の記事です。

adventar.org

概要

まずは、こちらのツイートをご覧ください*1。 https://twitter.com/totori_kpr/status/1472143266753953795

2021年12月18日現在、ととりにゃあさんの名前は「毎日進捗」となっています。 しばしば「毎日進捗ととりにゃあ」とフルネーム（？）で呼ばれることもあるようです。

ツイート本文は「毎日懇親」となっています。 以下のように、Twitter上ではしばしば「<ここに四字の熟語が入る>ととりにゃあ」として親しまれています。（このパターンに収まらないツイートもありますが）

https://twitter.com/totori_kpr/status/1469494096859660288

https://twitter.com/totori_kpr/status/1464120109190975491

これらのツイートを読むと、妙に語呂が良いことに気付きます。

「ととりにゃあ」は五音なので、五・七・五のリズムの中に取り入れやすくなっています。 これまで取り上げたツイートは、そのほとんどが四字の熟語が七音や、四音+四音になっており、七・五のリズムが語呂の良さを与えているように思われます。

主題

これを拡張して、ととりにゃあを便利な五音として乱用していこうというのがこの記事の目的です。 既存研究としては、

dic.nicovideo.jp

もともとは漫画・アニメ「日常」らしいですが、現代ではしばしばツイッター等で観測することができます。元の句は松尾芭蕉の「五月雨をあつめて早し最上川」。

狂歌 - Wikipedia

江戸中期に流行ったらしい。どんな優雅な上の句も破壊できるパワー下の句。

  • 「メイクアメリカ グレートアゲイン」

トランプ元米大統領のスローガンが実は下の句になる。どんな優雅な上の句もトランプの顔がちらつくようになってしまう。

ということでこの記事のタイトル「ととりにゃあ あつめて早し 最上川 それにつけても 金の欲しさよ」は「ととりにゃあ」と「それにつけても金の欲しさよ」を「五月雨をあつめて早し最上川」と悪魔合体させて作った句です。

実践

ではドンドン行きましょう。

  • 素晴らしい 毎日進捗 ととりにゃあ

毎日進捗、してますか？

  • 使います 伝家の宝刀 ととりにゃあ

元ネタ:

元ネタ:

ドラムには、ととりにゃあさえないんだな…

  • ととりにゃあ 墾田永年 私財法

  • ウマ娘 プリティダービー ととりにゃあ

  • あたしンち グラグラゲーム ととりにゃあ

  • 俺でなきゃ 見逃しちゃうね ととりにゃあ

  • ととりにゃあ 人には人の 乳酸菌

  • 大型で 非常に強い ととりにゃあ

まとめ

ととりにゃあの語呂、良すぎ

*1:飯テロの意図はありませんよ、本当です

マナ回路設計と魔術アーキテクチャ 【存在しない技術 Advent Calendar 2021】

ネタ

この記事は存在しない技術 Advent Calendar 2021 - Adventarの14日目の記事です。

この記事はあなたのお住まいの世界には存在しない技術をもとに記述されているため、あなたのお住いの世界ではご利用いただけません。

マナ回路前史

近代以前は、魔術を発動できるのは人間、それも多くのマナ*1を備えている人間に限定されていた。 これは、まず魔術を発動するには、一定以上のマナの密度が必要であるが、マナを蓄えられるのは人間に限られていたためである。

しかし、近代になり、マナを遮断する材料(断魔体)が発見されると、それを用いて任意の場所にマナを集めることが可能になった。 さらに、マナを集めた空間を圧縮することにより、マナの密度を魔術を発動するのに十分なだけ高められるようになると、魔術を発動できる機械である魔術機が登場した。

最初期の魔術期は発光、浮遊・移動、加熱・冷却といった単純なものに限られており、またその魔力も弱いものであった。 大きな魔力を扱うにはとても巨大な魔術機および、それに足るだけのマナが必要となるため、動力としての利用は蒸気機関の隆盛により小規模なものに限られるようになった。

一方で、微弱な魔力でよければ、小さな機構と少量のマナで魔術を発動することができ、小さな機構であれば微弱な魔力でも制御が可能である。 そこで、微弱な魔力で制御できる魔術機を複数並べ、これを連鎖的に、繰り返し発動できる魔術機が作られた。 マナを供給する限り半永久的に動き続けることから、マナ回路と呼ばれている。

マナ回路基本素子

マナ回路は、魔術を発動するのに必要なマナを圧縮する"圧縮機構"と、発動する魔術を決定する"発動機構"から構成される。 圧縮機構は、筒状の空間に集めたマナを板状の断魔体で押すことで圧縮する機構がよく用いられる。

圧縮機構

念力はマナ回路で最もよく使われる魔術で、これによりほかの圧縮機構を制御する。

左の圧縮機構により念力を発動して、別の圧縮機構を押す

念力により単純に魔術を発動するだけでなく、圧縮機構を無効化したりすることでより複雑な制御を行える。

圧縮機構に穴をあけて無効化する

マナ回路例: リングオシレータ

8組16個の機構を組み合わせたリングオシレータ

圧縮機構を連鎖させることによって、状態を一定間隔で変化させ続けるマナ回路。 圧縮機構を制御する断魔体の位置を往復させることで、ぐるぐると魔術の発動を連鎖させることができる。

ポイントは左上橙波線で示した部分で、ここだけ他と断魔体の動かす向きを変えることで、状態がループして継続的に魔術を発動し続けることが可能となる。

現代の魔術アーキテクチャ

魔術機は、その大きさを小さくすることで必要な魔力、消費されるマナを低減することができるため、世界中の魔術師が魔術機の小型化、集積化に取り組んだ。 その結果、現代では米粒ほどの大きさに、億単位の魔術機が集積できるようになった。 それに伴い高度で複雑な魔術を大量のマナ回路素子を組み合わせて実現することが可能になった。 さらに、マナ制御技術の向上等により、強力な魔術を発動する魔術機（フォース魔術機）が実用化されるなど、ますます魔術の応用範囲は拡大している。

*1:魔力を司る粒子。目で直接見ることはできないが、空間中を飛び回っている。

『フカシギの数え方』の数え上げを、全探索のままGPGPUで高速化した 【KMCアドベントカレンダー 2021 4日目】

ネタ

この記事はKMCアドベントカレンダー2021の4日目の記事です。

adventar.org

概要

元ネタ：『フカシギの数え方』


www.youtube.com

問題としてはN×Nマスのグリッド（頂点としては (N+1) \times (N+1) 頂点）を左上から右下まで移動する経路であって、同じところを二度通らないものの数を数える、というものになっています。

『フカシギの数え方』でお姉さんが数え上げていた問題を、実際に全探索で解いてみて、組合せ爆発の凄さを体感しつつ、GPGPUで頑張って高速化してみます。

CPUで全探索

これを全探索で解くためには、これまでに通った場所を覚えておいて、そこを通らないようにしつつ、右下の頂点までたどり着けるものを探せばよいです。 これはバックトラックによって簡単に数え上げることができます。

RustでCPU向けに実装したものがこちらになります

github.com

バックトラック部分の本体は

fn solve_impl(n: isize, visit: &mut BitVec, row: isize, col: isize) -> usize {
    if row == n && col == n {
        return 1;
    }
    let mut ans = 0;
    let d = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    for (dr, dc) in d {
        let new_row = row + dr;
        let new_col = col + dc;
        if min(new_row, new_col) < 0 || max(new_row, new_col) > n {
            continue;
        }
        let new_pos = new_row * (n + 1) + new_col;
        if visit.get(new_pos as usize).unwrap() {
            continue;
        }
        visit.set(new_pos as usize, true);
        ans += solve_impl(n, visit, new_row, new_col);
        visit.set(new_pos as usize, false);
    }
    ans
}

こんな感じで容易に書くことができます。 今いる場所から4方向に対して、枠外になっていないか、既に通っていないかを確認して、大丈夫なら移動する、ということを再帰的に繰り返しています。

並列化のため、最初の2Nステップほどを並列に実行するようになっています（async-stdとfutures-rsを利用しています）。

実行するとこんな感じです（oneesan(N)でN×Nマスでの数え上げを行います）

$  cargo run --release
    Finished release [optimized] target(s) in 0.54s
     Running `target/release/kazoeage-oneesan`
oneesan(1) = 2, elapsed: 0.001s
oneesan(2) = 12, elapsed: 0.001s
oneesan(3) = 184, elapsed: 0.001s
oneesan(4) = 8512, elapsed: 0.002s
oneesan(5) = 1262816, elapsed: 0.019s
oneesan(6) = 575780564, elapsed: 6.891s
oneesan(7) = 789360053252, elapsed: 12195.893s

実行時間はCPUの性能等に依存します。 この調子で行くと、oneesan(8)の計算には1年半ほどかかる計算になります。

GPUで全探索

今回はoneesan(7)の計算をGPGPUで高速化してみます。 まず、GPUは並列化しないとその性能を発揮できないため、最初の一定ステップをCPUで全列挙し、そこからゴールまでの経路をそれぞれGPUで数え上げることにします。 しかし、GPUは再帰関数の処理が苦手なため、並列化しただけではとても効率が悪いです。 手元で試したところ、oneesan(6)の計算に40秒ほどかかってしまいました。

効率が悪くなる主な原因は、GPUの内部構造にあります。GPUは内部的には複数スレッドを一定数(32や64程度)束ねて、すべてのスレッドで同一の命令を実行する仕組みになっています(SIMT)。 このままだとスレッド間で計算内容が異なる場合に対応できないので、一方のスレッドの計算を行っている間は、別の命令を実行したいスレッドを待機させます。 その結果、バックトラックでの分岐が発生するたびに、一度に実行できるスレッドが絞られていき、束ねたスレッドのうち、最終的には同時に走るのは1スレッドのみになってしまいます。

今回は、再帰関数を明示的に用意した配列で実装したスタックを用いたループに展開することで、分岐して別行動になったスレッド同士が再び同時に実行できるチャンスを増やすことで、効率化を行いました。 その実装がこちらになります。

github.com

細かい点としては、ローカルメモリ消費量を抑えるために、再帰1段分のスタック用配列サイズを2bitに抑える工夫を入れてあります。

これらの工夫の結果、手元のGPUではoneesan(6)を1.8秒、oneesan(7)を1728秒で求めることができるようになりました。 oneesan(7)の計算は実に7倍高速になりました！ このペースだとoneesan(8)も83日程度で求められる計算になります。ぎりぎり希望が持てる時間になりました（？） CPUとGPUの性能比を考えるとそう悪くない結果だと思います。

『フカシギの数え方』ではスーパーコンピュータは1秒間に2000億通り数えられる想定でしたが、このプログラムでは手元のGPU(GeForce RTX 3080)1枚で毎秒約4.5億通り数えられます。 現代のGPUを500枚程度用意すれば、おねえさんのスーパーコンピュータより速く数え上げることができるかもしれません。