Fixstars Corp. · TSE:3687
Fixstars — Technical Presentation (April 2021)
20 slides from Fixstars's technical presentation, Apr 27, 2021
Slide 1: Ising Register Allocation
ISING REGISTER ALLOCATION ～アニーラによるレジスタアロケーション～ ○熊谷 政仁†，高屋敷 光† †東北大学
Slide 2: What is register allocation
レジスタアロケーションとは • コンパイル中にソースコード内の変数をCPUのレジスタに割り当てる処理のこと void solve(int * data){ movl 4(%rdi,%rdx,4), %eax int n,i,w; cmpl %eax, %esi for( n=MAX; n>1; n-- ) jle .LBB0_4 { for( i=0; i<n-1; i++ ) n = %r1 movl %eax, (%rdi,%rdx,4) レジスタ%r1ト { i = %r2 movl %esi, 4(%rdi,%rdx,4) jmp .LBB0_4 レジスタ%r2 if ( data[i
Slide 3: Difficulty of register allocation
CPU 速い レジスタアロケーションの難しさ レジスタ キャッシュ メインメモリ • コードには多数の変数が存在 遅い ディスク • CPUが実際に持つレジスタの数は少ない void solve(int * data){ int n,i,w; for( n=MAX; n>1; n-- ) { for( i=0; i<n-1; i++ ) 退避させるか { if ( data[i]>data[i+1] ) らちょっと待っ { てね w=data[i]; data[i]=data[i+1]; えっ？このCPU data[i+1]=w; 変数100個 レジスタ10個 } しかないの？ } } くらい
Slide 4: Register allocation and graph coloring
レジスタアロケーションと彩色問題 • 古典的にレジスタアロケーションは彩色問題を応用して解くことが出来る 大雑把なコンパイルの流れ 1 各変数の生 ソース 存期間を分 色付けをもと 0 2 マシン コード 析して，変数 にレジスタへ コード をノードとす 割り当て る干渉グラフ を作成 3 ノード間にエッジが存在する時は変 数が同時に生存しているので，違う レジスタ（色）を与える必要がある ただし，グラフを色づけることが出来る最小色数を求めるのはNP-hard問題！ そこで最適化問題として量子アニーリング・イジングマシンで解くことを考える FIXSTARS AMPLIFYハッカソン 2021/
Slide 5: QUBO formulation
QUBO定式化 2 • 𝑁−1 𝐻 = σ𝑖=0 1 − σ𝑟=0 𝑞𝑖,𝑟 + σ𝑅−1 𝑅−1 𝑁−1 𝑟=0 σ𝑗∈𝐸[𝑖] 𝑞𝑖,𝑟 𝑞𝑗,𝑟 + σ𝑖=0 σ𝑟∉𝐴[𝑖] 𝑞𝑖,𝑟 • 変数の数：𝑁，レジスタの数：𝑅 • 変数𝑖をレジスタ𝒓に割り当てる時：𝑞𝑖,𝑟 = 1，割り当てない時：𝑞𝑖,𝑟 = 0 • 𝐸 𝑖 ： 変数 𝑖 と生存期間が重なる変数の集合 • 𝐴 𝑖 ： 変数 𝑖 が割り当て可能なレジスタの集合 • 制約条件 • 各変数をただ1つのレジスタに割り当て（ノードをただ1色で塗る）…
Slide 6: Partitioning large coloring problems
大規模な彩色問題の分割について • 状況に応じて問題サイズを分割する必要 前の分割時に得られた解を含めて次の解 • 変数が多くて量子ビット数を超える場合 を求める．割り当て可能なレジスタを絞る → 問題を分割して最適化 制約に解のみを与えることにより実現可能 1 2 1 2 1 2 3 3 3 0 0 0 4 4 4 5 5 5 7 6 7 6 7 6 FIXSTARS AMPLIFYハッカソン 特定の依存関係だけを取り出して，変数のレジスタ割り当てを決定 2021/4/27 6
Slide 7: Application architecture
アプリケーションの構成 • Clang/LLVMを利用して中間表現からレジスタ情報を抽出 • コードの分析や最適化はLLVMのエコシステムを利用 ソースコード Clang/LLVM Amplify (Python) バイナリ Clang/LLVM （C++) 中間表現 割り当ての決定 (X86等) • ベンチマーク （簡単なプログラム） ここは今後の課題 • モンテカルロ法，バブルソート • レジスタはX86_64を想定 • 問題は４変数ずつに分割して求解 FIXSTARS AMPLIFYハッカソン 2021/4/27 7
Slide 8: Evaluation (Monte Carlo method)
for( j=0,Ni=0; j<jmax; j++ ){ x=(double)rand()/max; y=(double)rand()/max; if ( x*x+y*y<=1.0 ) Ni++; 評価（モンテカルロ法） } pi=(double)Ni/(double)jmax*4; エッジは各変数(ノード)が重複する 生存期間を持つことを示す • 全ての制約を満たした割り当てに 成功 • 同色のノードは同じレジスタに割り 当てられている • エッジがない（生存期間が重ならな い）ため，制約を満たせている FIXSTARS AMPLIFYハッカソン 2021/4/27 8
Slide 9: Evaluation (bubble sort)
void solve(int * data){ int n,i,w; for( n=MAX; n>1; n-- ) { for( i=0; i<n-1; i++ ) 評価（バブルソート） { if ( data[i]>data[i+1] ) { w=data[i]; data[i]=data[i+1]; エッジが黒：制約が満たされる data[i+1]=w; } エッジが赤：制約が満たされない } } } • 概ね制約を満たした解を求めるこ とに成功 • 同じレジスタに割り当てられるが生 存期間の重なる変数が存在 • この場合スピルが発生する • 問題の分割方法に改善の余地あり FIXSTAR
Slide 10: Future outlook
今後の展望 • アルゴリズムに関して • スピルコストを考慮したレジスタの選択を行うコスト関数の追加 • 解品質を維持したまま問題を分割する手法の考案 • 実用性に関して • 量子アニーリング・イジングマシンを用いてレジスタアロケーションを行うLLVM Passの作成 • FPGAの高位合成時のリソース割り当てなど他の手法へ応用など • 一般的な大規模なリソース割当の問題に応用 • 評価に関して • ほかのレジスタアロケーション手法との実行時間・解品質の比較 • その他 • いつか論文にしたい(LLVMやコンパイラ最適化など，この辺のドメインに詳しい人がもし居たらご連絡ください) FIXSTA
Slide 11: Summary
まとめ • 新規性 • 量子コンピュータを用いたレジスタアロケーション手法の例はまだ無い • 彩色問題を色付け制約付きで定式化した例も無い • 進歩性 • 彩色問題によるレジスタアロケーションは品質は良いが柔軟性及び求解コストの側面から不利とされていた • 本手法は様々な制約を当てはめたうえで（たぶん）高速に解を求められる！ • 技術力 • 色付け制約付き彩色問題のQUBO定式化 • LLVMのバックエンドから中間表現を抽出しベンチマークを作成 • Amplifyを用いて手法のProof of conceptを作成 • 実用性 • 色付け制約により割り付けレジスタの指定，量子ビット数が不足する
Slide 12: Backup slides
以下，予備スライド FIXSTARS AMPLIFYハッカソン 2021/4/27 12
Slide 13: Summary
まとめ • 背景 • レジスタアロケーションについて • 彩色問題によるレジスタアロケーション • QUBOを用いた彩色問題の定式化 • 変数にレジスタが１つだけ割り当てられる制約 • 生存期間が被る変数に別のレジスタを割り当てる制約 • 各変数に割り当て可能なレジスタに応じて割り当てる制約 • 問題が大きい場合の分割について • 評価 • LLVMから得られた変数情報・レジスタ情報をもとにした色付け評価 • モンテカルロ法では正しく割り当てが出来ていた • バブルソートでは制約が破られる場合があった FIXSTARS AMPLIFYハッカソン 2021/4/27 13
Slide 14: Representing register allocation with qubits
量子ビットによるレジスタ割り当ての表現 4つの変数を4本のレジスタに割り当て 4×4個の量子ビットで表現 レジスタ 𝒓 1 0 1 2 3 変 0 𝑞0 0 𝑞0 1 𝑞0 2 𝑞0 3 数 0 2 𝑖 1 𝑞1 0 𝑞1 1 𝑞1 2 𝑞1 3 2 𝑞2 0 𝑞2 1 𝑞2 2 𝑞2 3 3 3 𝑞3 0 𝑞3 1 𝑞3 2 𝑞3 3 変数𝑖をレジスタ𝒓に割り当てる時， 𝑞 𝑖 𝑟 = 1 割り当てない時，𝑞 𝑖 𝑟 = 0 FIXSTARS AMPLIFYハッカソン 2021/4/27 14
Slide 15: Constraint: one register per variable
各変数をただ一つのレジスタに割り当てる制約 レジスタ 𝑅−1 1 0 1 2 3 𝑞2,𝑟 𝑟=0 変 0 = 𝑞2,0 + 𝑞2,1 数 + 𝑞2,2 + 𝑞2,3 = 1 0 2 1 レジスタ4本 のうち，1っに 2 1 0 0 0 3 しか割り当て られない 3 制約条件： σ𝑅−1 𝑟=0 𝑞𝑖,𝑟 = 1, 𝑖 ∈ {0, 1, ⋯ , 𝑁 − 1} 2 FIXSTARS AMPLIFYハッカソン QUBO： 𝐻 = σ𝑁−1 𝑅−1 𝑖=0 1 − σ𝑟=0 𝑞𝑖,𝑟 2021/4/27 15
Slide 16: Constraint: overlapping lifetimes use different registers
生存期間の重なる変数同士を別のレジスタに割り 当てる制約 同じレジスタでは，変数1 各変数が生存期間 番と2番の両方が1にな の重なる変数 レジスタ ることはない 1 𝐸 0 = 1, 3 0 1 2 3 𝑞2,0 𝑞𝑗,0 𝐸 1 = 0, 2, 3 𝑗∈𝐸[2] 𝐸2 = 1 変 0 = 𝑞2,0 𝑞1,0 = 0 𝐸 3 = 0, 1 数 0 2 1 1 0 0 0 変数1番とは 2 0 0 1 0 3 同じレジスタ にならない 3 制約条件： σ𝑗∈𝐸[𝑖] 𝑞𝑖,𝑟 𝑞𝑗,𝑟 = 0, 𝑟 ∈ {0, 1, ⋯ , 𝑅 − 1}…
Slide 17: Constraint: allowable registers per variable
各変数が割り当て可能なレジスタに関する制約 各変数が割り当て可 能なレジスタ番号 𝐴 2 に入ってない1番と レジスタ 𝐴 0 = 0, 1 2番は0になるようにす 1 𝐴 1 = 0, 2, 3 0 1 2 3 る 𝐴 2 = 0, 3 変 0 0 0 𝐴 3 = 1, 2, 3 𝑞𝑖,𝑟 数 𝑟∉𝐴[2] 0 2 1 0 = 𝑞2,1 + 𝑞2,2 = 0 レジスタ4本 あるけど，0 2 0 0 3 番と3番にし か割り当て 3 0 できない 制約条件： σ𝑟∉𝐴[𝑖] 𝑞𝑖,𝑟 = 0, 𝑖 ∈ {0, 1, ⋯ , 𝑁 − 1}…
Slide 18: Interference graph
干渉グラフについて 変数 0 1 2 3 1 • 変数0, 1, 3は変数が生存期間が重 複しているので，同じレジスタに割 生存期間 り当てることは出来ない 0 2 • 変数2と変数0,3は生存期間が重複 3 していないので，同じレジスタでも 問題ない FIXSTARS AMPLIFYハッカソン 2021/4/27 18
Slide 19: Evaluation (Monte Carlo)
評価（モンテカルロ） LLVMから抽出した，各変数が利用可能なレジスタ番号 0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 2: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 3: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 4: [15, 16, 17
Slide 20: Evaluation (Simpson)
LLVMから抽出した，各変数が利用可能なレジスタ番号 0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 1: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 評価（シンプソン） 2: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 3: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30], 4