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
310
「自作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
820
F*でプログラムの正しさを証明する
anqou
1
1k
ぼくのかんがえたさいきょうのマリオAI
anqou
1
500
10ステップで作るお手軽インタプリタ開発
anqou
3
960
seccamp2018でセルフホストCコンパイラをつくった
anqou
8
5.2k
Other Decks in Programming
See All in Programming
LangChainの現在とv0.3にむけて
os1ma
4
920
はじめてみよう量子プログラミング
itokoichi01
0
210
事業フェーズの変化に対応する 開発生産性向上のゼロイチ
masaygggg
0
200
connect-go で面倒くささと戦う / 2024-08-27 #newmo_layerx_go
izumin5210
2
650
Rechartsで楽にゴリゴリにカスタマイズする!
10tera
1
170
Regular Expressions, REXML, Automata Learning
makenowjust
0
220
いまから追い上げる、Jetpack Compose トレーニング
nyafunta9858
0
590
Method Swizzlingを行うライブラリにおけるマルチモジュール設計
yoshikma
0
120
unique パッケージから学ぶ interning と weak reference @ Asakusa.go#3
karamaru
2
810
GraphQL あるいは React における自律的なデータ取得について
quramy
11
3k
今インフラ技術をイチから学び直すなら
yuhta28
1
140
長期運用プロダクトの開発速度を維持し続けるためのリファクタリング実践例
wataruss
8
2.7k
Featured
See All Featured
Fashionably flexible responsive web design (full day workshop)
malarkey
401
65k
Atom: Resistance is Futile
akmur
261
25k
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.4k
Music & Morning Musume
bryan
46
6k
Optimising Largest Contentful Paint
csswizardry
31
2.8k
A Modern Web Designer's Workflow
chriscoyier
691
190k
Debugging Ruby Performance
tmm1
72
12k
Testing 201, or: Great Expectations
jmmastey
36
7k
Scaling GitHub
holman
458
140k
Robots, Beer and Maslow
schacon
PRO
157
8.2k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
Intergalactic Javascript Robots from Outer Space
tanoku
268
26k
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