Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
「自作CPUでサイゼリヤ問題」を支える技術
Search
Ushitora Anqou
June 16, 2019
Programming
2
330
「自作CPUでサイゼリヤ問題」を支える技術
https://github.com/ushitora-anqou/SIMPLE-arch-tools
Ushitora Anqou
June 16, 2019
Tweet
Share
More Decks by Ushitora Anqou
See All by Ushitora Anqou
Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption
anqou
1
890
F*でプログラムの正しさを証明する
anqou
1
1.1k
ぼくのかんがえたさいきょうのマリオAI
anqou
1
560
10ステップで作るお手軽インタプリタ開発
anqou
3
1k
seccamp2018でセルフホストCコンパイラをつくった
anqou
8
5.4k
Other Decks in Programming
See All in Programming
Dissecting and Reconstructing Ruby Syntactic Structures
ydah
2
1.2k
エンジニアが挑む、限界までの越境
nealle
1
280
Being an ethical software engineer
xgouchet
PRO
0
220
Make Parsers Compatible Using Automata Learning
makenowjust
2
5.6k
Vibe Coding の話をしよう
schroneko
12
3k
Deoptimization: How YJIT Speeds Up Ruby by Slowing Down / RubyKaigi 2025
k0kubun
0
1.3k
State of Namespace
tagomoris
4
2k
iOSアプリで測る!名古屋駅までの 方向と距離
ryunakayama
0
110
スモールスタートで始めるためのLambda×モノリス(Lambdalith)
akihisaikeda
2
300
The Nature of Complexity in John Ousterhout’s Philosophy of Software Design
philipschwarz
PRO
0
130
AIコーディングワークフローの試行 〜AIエージェント×ワークフローでの自動化を目指して〜
rkaga
3
3.8k
RubyKaigi Dev Meeting 2025
tenderlove
1
390
Featured
See All Featured
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.3k
Embracing the Ebb and Flow
colly
85
4.7k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Testing 201, or: Great Expectations
jmmastey
42
7.5k
Designing for Performance
lara
608
69k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
12k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.2k
Designing for humans not robots
tammielis
253
25k
How to Think Like a Performance Engineer
csswizardry
23
1.5k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
2.9k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
13
790
Into the Great Unknown - MozCon
thekraken
38
1.7k
Transcript
「自作 CPU でサイゼリヤ問 題」を支える技術 艮 鮟鱇 @ushitora anqou 1
もう読んだ? 「サイゼリヤで 1000 円あれば最大何 kcal 摂れるのか」を自作 CPU 上で解いてみた |カオスの坩堝 https://anqou.net/poc/2019/05/27/
post-2920/ 2
計算機科学実験及演習 3(ハードウェア) FPGA 上にプロセッサをつくる • やばそう • わからん!w 3
計算機科学実験及演習 3(ハードウェア) FPGA 上にプロセッサをつくる • やばそう • わからん!w 実際わからん 3
人に聞く @PiBVT と@fplwd には大変お世話になりま した 4
5
4 月 30 日 6
4 月 30 日 6
ハードウェア実験 終了!w 7
ハードウェア実験 終了!w 7
ソートコンテスト • 1024 個の符号付き 16bit 整数を昇順 ソート • データセット:ランダム・昇順ソート済 み・降順ソート済み
• 実行サイクル数と動作クロック周波数 から実行時間を計算 最終デモでは応用プログラムの実行が必須 8
「伝説」 9
方針 • 「伝説」は超えられない • c.f. ハードウェアロジック 0.04611ms • マルチコアはやりたくない •
でも 1ms は切りたい 10
1bit 幅基数ソート • 下位ビットから舐める • 上位ビットからでもいいらしいね。 • 0 と 1
のバケツを作って順に並べる • 以上繰り返し • 時間計算量は O(n × k) アルゴリズムが単純で実装が楽そう 11
ソート実装のためアセンブラを開発 でも普通のアセンブリは読みにくい…… • ADD R0, R1⏎ ST R0, 5(R1) ⇐⇒
R0 += R1⏎ [R1 + 5] = R0 • CMP R0, R1⏎ BLT loop ⇐⇒ if R0 < R1 then goto loop • 大抵の場合レジスタは変数一つに対応 12
ソート実装のためアセンブラを開発 でも普通のアセンブリは読みにくい…… • ADD R0, R1⏎ ST R0, 5(R1) ⇐⇒
R0 += R1⏎ [R1 + 5] = R0 • CMP R0, R1⏎ BLT loop ⇐⇒ if R0 < R1 then goto loop • 大抵の場合レジスタは変数一つに対応 もっと直感的に書けるようにする 12
examples/sort/radix sort1bit.s 13
結果 14
結果 14
1位! 15
1位! (暫定) 15
結果(再掲) 259,065 サイクルかかる 16
サイクル数を減らす 「伝説」以降の流行 りに乗っかる 17
1bit 幅基数+挿入ソート • 上位 m < k ビットを下位から 1bit 幅
基数ソート • その後全体を挿入ソート • 計算量は O(n × m + n2) • ただし後半の n2 は実際には n の気分 挿入ソートが「ほとんどソート済みの数 列」に対して早いことを利用 18
examples/sort/radix1bit insert sort.s 19
早いの? 20
早いの? • 微妙 • 実験すると m = 8 が一番早い •
理論値 11 万サイクルちょっと • 実機だともう少し悪くなる(未確認) どうする? 20
2bit 幅基数ソート 2bit の窓で値を見る (00/01/10/11) • 「どのバケツに属するか」を数サイク ルで判定可能 • ループ処理サイクル数を
1bit のときと ほぼ同じに 実装が煩雑なのでアセンブラを改造 21
examples/sort/radix sort2bit.s 22
2bit 幅基数ソート 時間計算量は O(n × k/2) • 単純計算で 1bit 幅基数ソートと比較し
て 2 倍早い • ループ内処理を 1bit と同じ程度に抑え る必要 • 実際は? 23
24
10 万サイクルの壁 • 挿入ソートと 2bit 幅基数ソートで実機 は 10 万サイクルちょい(未確認) 25
10 万サイクルの壁 • 挿入ソートと 2bit 幅基数ソートで実機 は 10 万サイクルちょい(未確認) 基数ソートの幅を増やす
25
最大幅は? FPGA 上の最大メモリサイズは 33792W • 愚直な kbit 幅基数ソートは (n ×
2k+1)W 必要 • n = 1024, k = 4 にて n × 2k+1 = 32768 • ギリギリ載るけど…… 26
最大幅は? FPGA 上の最大メモリサイズは 33792W • 愚直な kbit 幅基数ソートは (n ×
2k+1)W 必要 • n = 1024, k = 4 にて n × 2k+1 = 32768 • ギリギリ載るけど…… 4bit 幅基数ソートしたい 26
工夫する • バケツのほとんどの空間は使わない • 4bit だけの処理なら半分の空間でいい 27
工夫する • バケツのほとんどの空間は使わない • 4bit だけの処理なら半分の空間でいい =⇒ 4bit 処理するごとに値を詰め直す •
詰め直す処理は O(n) で比較的軽量 27
工夫する • バケツのほとんどの空間は使わない • 4bit だけの処理なら半分の空間でいい =⇒ 4bit 処理するごとに値を詰め直す •
詰め直す処理は O(n) で比較的軽量 ところで度数ソートって知ってる? 27
examples/sort/radix sort4bit.s 28
29
これを挿入ソートと組み合わせたい 実装が煩雑なのが嫌 • 「どこでどのレジスタが使われている か」なんて気にしたくない • アルゴリズム本体に注力したい 引数付きマクロをいじる 30
examples/sort/radix4bit insert sort.s 31
これで実験は終わり…… 32
これで実験は終わり…… ShinyaKato さんの DP 解法がこの日の朝 4 時頃に公開 32
とりあえず C で書く 後々ハンドアセンブルしやすいように 33
とりあえず C で書く 後々ハンドアセンブルしやすいように というのも 33
とりあえず C で書く 34
とりあえず C で書く • DP 配列を 2 本だけ持って交互に更新 • 7
品のみ持つようにする • 正答は 3 品程度 34
書けた 35
書けた ハンドアセンブルが難航 35
36
一級フラグ建築士の鮟鱇氏 36
ところで 世界の真相に気づく鮟鱇氏 37
フラグ回収 38
フラグ回収 38
インクリメンタルに開発 39
割り切り設計 とりあえずサイゼリヤが動けばいい • C の参考実装で必要な演算のみ実装 • if の else 節が無い
• 変数の宣言時初期化がない • 整数リテラルは-128〜127 のみ許容 • すべての変数はメモリ上に割り付け • 変数を使うときはレジスタに LD して操 作して ST する 40
コンパイラできた 意外と早くできた。 41
コンパイラできた 42
プロセッサバグった シミュレーションがまともにできず地獄 43
不満を並べる鮟鱇氏 44
@fplwd に手伝ってもらって完動 45
食べに行った ※ オヌヌメしません 46
47
記事は 1 万 PV/日を超えました • すべての閲覧者に感謝を。 • Twitter とはてブのコメントはおおよ そ全部読んだつもり。
• 「息を吐くようにコンパイラ作ってんの すげえなぁ。 」が一番うれしかった。 • 503 で落ちてて正直すまんかった。 • 7 月から改善予定なので許して。 48
SIMPLE-arch-tools • 鮟鱇が開発した SIMPLE 用 toolchain • エミュレータ・アセンブラ・マクロア センブラ・コンパイラ・デバッガ •
C 言語による単純な実装で改造容易 • 詳細な usage.md・豊富な examples/ • github.com/ushitora-anqou/SIMPLE-arch-tools ★スター★をください 49
怪文書 この演習は「ハードウェア実験」であって、アセンブラやエ ミュレータの開発はその目的に含まないはずである。にもか かわらず実際には、高性能なソートプログラムを作成するた めにはこれらの利用がほとんど必須であり、これらの開発に 貴重な時間的リソースが割かれる。これは実験の本旨に照ら して由々しき問題であり、到底看過されるべきでない。次年 度以降のハードウェア実験では、例えば拙作の SIMPLE-arch-tools のような過去の履修者が作成したツール
チェインか、ないし講師陣が作成したツールチェイン等が、 柔軟性のためそのソースコードを添付された形で、学生に対 し頒布ないし提示されることを切に期待する。 50
まとめ 51
まとめ 鮟鱇がハードウェア実験をすると、 ほとんどソフトウェア実験になる。 51
ご清聴 ありがとうござ いました 52