CPU実験:マルチコアで並列実行するまで(コンパイラ係目線)

 CPU実験が終わって半年ですが、忘れる前にやったことを書き残しておこうと思います。

f:id:eguchishi:20170904025735p:plain

並列化ーー

CPU実験

全体

 4人程のチームで、自作CPU、コンパイラアセンブラ、シュミレータ等を作り、最終的には高級言語(mincamlというOcamlのサブセット)で書かれたプログラム(レイトレーシング)を実行速度を競います。CPU実験の詳細は検索すると結構出てくるかと思います。

f:id:eguchishi:20170909133436p:plain

レイトレプログラムの出力結果
自班の最終成果

 『レイトレプログラムをマルチコアで並列実行する』ということをやりました。結論から言うとこれがかなり上手いこといって、歴代最速記録を大幅に(1/2位?)更新することができました。

具体的には記録は以下の通りです。詳しくは*1

  • 4.666948 s(7コア、逐次実行と比べ演算順序が変わり得る)
  • 5.193502 s(6コア、演算順序が変わらない)

 *実験の条件も年々良くなっているので、単純に過去との比較はできませんが、過去最高記録というのは良いものです笑

 またコンパイラ係が気になるのは動的命令数(プログラム実行時に何個の命令が処理されたか)です。これは、

  • 動的命令数:3.3億命令(7コア)

*↑各コアの間で、動的命令数の最大値(マルチコアなので)

でした。恐らく8億台あたりが過去最短だったと聞いているのですが、今回はそれを大幅に上回る効率を出すことができました。逐次実行させた場合は16億命令くらいなので、並列処理の恩恵を多分に受けたことが分かります。

並列実行までの話

ちょっと長くなってしまったので目次です。

 

自分の担当:コンパイラ係について

 コンパイラ係の仕事は、コア係が書くCPUが受理する機械語へのコンパイラを実装することです。フルスクラッチしなければならない訳ではなく、実はmincamlコンパイラ*2が公開されているので、 これを改造して自分達のCPUに対応することになります(フルスクラッチする人もいますが)。このおかげで、”何をしたら良いか全く分からない”ということがなくなり、より高度な実装に挑戦しやすくなるので、昔のCPU実験よりは結構良い環境になっているようです。

並列実行する為に必要なこと

 悲しい事実ですが、コアをたくさん並べるだけでは並列に実行してくれません。

  1. コアの並列処理の仕組みを決めて、実装する。
  2. 並列処理に関する命令セットを定義する。
  3. コンパイラが、入力プログラムの並列実行できる部分を認識できるようにする。
  4.  その部分を、2で決めた命令を使って並列処理コードに変換する

 実際の作業順は3->1->2->4という感じでした。1はコア係の仕事。2もコア係が考えた大枠をもとに、コアとコンパイラの事情を擦り合わせて決めました。

 ということで、コンパイラがやるべきことは3,4です。3がエグい感じでした。

並列化したかった処理について

  コア係が1st完動の後で、「レイトレプログラムで大量に呼び出されている関数が並列化できるかも」と突然言い出したのがことの発端だった訳ですが、これがどのような関数だったかを少し説明します。

iter_trace_diffuse_rays

この部分にある、iter_trace_diffuse_raysという関数です。見ると分かりますが、末尾再起によってforループと等価な関数であることが分かります。レイトレプログラムでは、このループが60回回りますが、それぞれのループ間に依存関係はなく並列実行できるのです。

 厳密には依存関係がないというのは嘘で、各ループがdiffuse_raysという変数に対して、『diffuse_raysを参照する』、『"独立に計算された値”を足してdiffuse_raysを更新する』ということをしています。しかし、この2つの処理を不可分な1つの処理として実行することができれば、並列実行した際に『演算順序は変わるけど、最終的なdiffuse_raysの値は変わらない(丸め誤差覗く)』ということになる訳です。

並列判定の辛さ

 iter_trace_diffuse_raysに目をつけたコア係は凄かったです。しかし、このレベルの並列性を認識できる解析をコンパイラで一般的に行うとなると、これは結構険しい道のりです。

1.minrtにはfor構文がない

 mincaml関数型言語であり、再帰呼び出しを使うので、forやwhileといったループ構文は存在しません。なので、中間表現にfor構文を導入し、”可能であれば関数を適切にfor構文に変換する”機能が必要です。また、この過程で『再代入可能な変数(Ocaml のrefにあたるもの)』を扱う必要が出てくるのですが、レジスタ割り当てでこれに正面から取り組んだ結果、泥沼にはまりました。

2.深い関数のネスト

 iter_diffuse_raysは、ネストの深い関数呼び出しを行います。下は、レイトレプログラムの関数依存グラフです(コア係作)。f:id:eguchishi:20170903235025g:plain

  赤で囲った部分が並列化目標のiter_trace_diffuse_raysです。内部でたくさんの関数が呼び出されることが分かります。なので、並列化判定は真面目に関数間の解析をする必要がありそうです。

3.様々な関数で繰り返し参照される、メモリ領域(array型の要素)

  これが難しさの本質ですが、レイトレプログラムでは、array型を含む入れ子構造(配列の組の配列、、といった型)に対し、各関数がreadしたりwriteしたりをしています。なので、この配列アクセスがループを越えた依存関係を作っていないことを保証することが、並列化判定の仕事になります。また、同じ領域を、色々な関数で、違う変数名で、アクセスすることがあるという辛いポイントもあります

 

 という感じで、結構大変そうな雰囲気が出ています。以降は、このレイトレプログラムの並列性をコンパイラで認識し、マルチコアで実行までを書いていきます。

  

並列性の判定をしよう!

 紆余曲折で1stが完動したのが12月中旬で、冬休みに入ってから並列化の為の実装に取り掛かり始めました。

 まずは上で紹介した困難を乗り越え、iter_trace_diffuse_raysの並列性が判定できるレベルの並列性評価を目指していきます。

(前準備)中間表現にfor構文を導入

 中間表現(knormal.t)にfor構文を用意してやり、前処理として適切に末尾再帰関数をfor文に変換します。ざっくりと下のような変換をします。

f:id:eguchishi:20170904025638p:plain

 

  上の絵からも分かりますが、末尾再帰の引数をfor文で表す関係上、『再代入可能な変数』(Ocamlでいうref型)を表現する必要が出てきます。

 このref型をまともに扱おうとしてハマりました。mincamlは『変数は定義から値が変わらない』という性質を元に実装されているので、レジスタ割り当ての際に、ref型に対して1つのレジスタを割り当てようすると、例外的な扱いをする必要が出てきます。無理やり、regAlloc.mlをゴリゴリ拡張したのですが、「バグが出続ける、コードはゴチャゴチャになっていく、ついでに試験期間とも被る」という感じで、闇に飲まれかけました、、

 例えば、ref型変数はを1要素array型として扱ってしまえば楽だったのですが、ループごとに無駄にメモリアクセスが起きるのが嫌な感じで意地を張ってしまいました。今考えてみると、全体の性能に与える影響を考えると、早すぎる最適化をしてしまった感じで、取り敢えず1要素array型で済まして先に進んだ方が良かった気がします。

 

->この結果、レイトレプログラムの12個の関数がforループに変換されました

データフローグラフ、アクセスしているデータを表すtreeの作成

 並列化判定は下の流れで行います。判定の対象は各forループです。

  1. メモリアクセスに関するフローグラフの作成。(関数呼び出しも追う)
  2. フローグラフから、1つのループを越えたデータ読み書き依存がないか検証

 フローグラフの各ノードには、『a[1]をread』,『b<2>[3]をwrite』などという情報が入ります。また、コンパイル時には何番めにアクセスするか分からないこともありますが、それも『c[unknown]をread』という感じで表現します。

*簡単の為、a<2>で組(tuple)の2番目要素、のように表現しますm()m。なので上のb<2>[3]は、『組の2番目要素にある配列の3番目』という意味です。

データ構造を表すtreeの作成

 同じ領域を異なる変数名、異なる関数アクセスすることに対応する為には、アクセスしているデータの構造をコンパイラ側である程度把握する必要があります。ということで、フローグラフを作るのと同時に、データ構造を表すtreeを成長させていきます。

 まず、並列化を判定するforループに到達するまでに、宣言された配列を集めます。

 

f:id:eguchishi:20170904225437p:plain

該当ループの解析(フローグラフ作成)時に、上で集めた変数をrootとするようなtreeを成長させていきます。

f:id:eguchishi:20170905003848p:plain

 上のような感じで、array型or組要素へのアクセスがある度にtreeを更新していきます。これで同じ領域を示す変数達も同時に集められます。

 これを元に、フローグラフを下のように作成していきます。

 

f:id:eguchishi:20170905001451p:plain

 このようにすることで、『同じ領域は同じ変数で表されたフローグラフ』が作成

されるので、幸せになります。

いくつかの制約

 厳密には、 上のようにしてフローグラフを作成したとき、『同じ領域は同じ変数で表される(かつ違う領域は違う変数で表される)』にはいくつか条件があります。

1.並列化判定前に、rootとして集めたarray型を含む変数が表す領域は全て独立していて交わらない。

 『配列a,bに対して、a[3][1]とb[1][3]が同じところを表している』とかがないということです。これはちゃんと解析すべきですが、レイトレプログラムの場合はOKなので後回しにして結局実装しなかったです。言語仕様上エイリアスしているポインタを使いまわした場合、動作は不定ということにすることで回避(回避していない)。

 

2. 異なる場所で定義された変数は異なる名前がついている

ー>α変換後に並列性判定を行えば良いです。

3.for文が回る間に、データ構造が変化しない。

 変化すると、『コードの場所によってa[1][3]が示す領域が異なる』とか、『途中で1が成立しなくなる』とかの可能性があるので色々と嫌な感じがします。なので変化しないことを保証します。これは、代入構文などデータ構造を変えうる操作それぞれに対し、型を確かめることで簡単に保証できます。

4.ループの中で入出力(IO)をしない。

 入出力の順番はバラバラになってはいけないですね。これはコード解析中に入出力命令に遭遇しなければ良いので判定できます。

フローグラフから並列性の判定

 さて、フローグラフが作れたらいよいよ並列性の判定です。ループを越えたWAR(write after read)依存がないかチェックします。

 例えば、下のような3つのフローグラフがあったとした時、どの場合ならループ越え依存が存在するでしょうか。

 *フローグラフはforループの一周分の処理の流れを表していることに注意してください。

f:id:eguchishi:20170906010330p:plain

 

 この中では、X,Zがループを越えた依存関係を作っていますね。Xは,readした時のA[1]の値は、1周前のループでのA[1]のwriteに依存しています。Yは、readする時のA[1]の値が、同じループの処理が事前にwriteした値となるので、WAR依存はループ内で閉じています。Zは、条件分岐によってループ内でWAR依存が閉じる場合もあるが、閉じない場合もある、ということでループ越え依存があると判定できます。大雑把ですが、こんな感じで同一領域にwriteとreadの両方がある場合は、readは同一ループ内でwriteされた値を読んでいるかを判定します。

 また、コンパイル時にアクセス領域が分からない場合もありますが、その場合は保守的に判断します。以下グラフのような場合は、どちらもループ越え依存があるとするわけです。

f:id:eguchishi:20170907202538p:plain

並列性判定!(1回目)

 さて、結構長い道のりを経てここまで実装してきました。あとは並列性を判定して万歳万歳となりたいところです。しかし、現実はそう甘くはありませんでした。実際に上の方法で、iter_trace_diffuse_raysを検証すると、ループ越えのWAR依存があると判定されてしまうのです。

 説明するのが結構面倒なので、当時のやり取りを載せておきます。

f:id:eguchishi:20170907235133p:plain

 

という訳なのです。当時、ここまでの全てが水の泡ではという絶望的な気持ちになって班のスラックに投げたのですが、

f:id:eguchishi:20170908000103p:plain

という訳なのですね。(はしょり)

 改めてコードを見て見ると、レイトレプログラムにはこういうトリッキーな依存関係がいたるところに存在することが分かってきました。

トリッキーなループ内で閉じたWAR依存

 一見コンパイラで解析するのは絶望的というような感じに見えたのですが、ここまできたら後には引けません。頑張ります。

 実際、落ち着いて考えてみると、一般的な解析ができそうなことが分かってきました。まず上の状態を噛み砕いて図にすると以下のようになります。

f:id:eguchishi:20170908002934p:plain

 フローグラフの形だけをみると、A[1]をreadした時その値が同じループでwriteされたかわ分からないので、ループ越え依存があると判断するしかありません。しかし、変数の環境を追って見ると『A[1]をreadするのは同一ループでA[1]をwriteした時のみ』ということが分かります。

判定法

 以下のようにフローグラフの作成過程を改良することで、判定できるようにしました。

 まず、フローグラフを作成する段階で、writeされた全ての領域に対し、『writeされない最長の経路を通ってきた場合の、変数の環境』の情報を保持するようにします。

f:id:eguchishi:20170908012300p:plain

 このような情報を保持することで、以下のようにより精密に条件分岐が解析できるようになります。

 

f:id:eguchishi:20170908015402p:plain

 このようにより精密なフローグラフを作成し適切に解析することで、このトリッキーな読み書き依存が閉じている(readは必ずループ内のwriteに依存)が分かるようになりました。

 (それにしても、ここら辺が一番精神的に追い込まれました、、)

並列性判定!(2回目)

 ここまできて遂に、並列性をを判定することができましたーー

( ↓ 出てきた出てきた )

f:id:eguchishi:20170909004552p:plain

 出力の詳細は、ー>result.txt(GitHub)

 

、、達成感安堵感がもの凄かったです笑

並列判定の後、、、

 並列化判定ができたので、残りは並列化された機械語の出力です。実は、これまでと比べると難しい部分はなく、中間表現から出力までの流れを粛々と書き換えていく感じでした。並列化命令がコンパイラに優しいものになっており、並列処理モードへの移行は関数呼び出し、並列処理本体はforループの機械語出力、と同じ要領で実装できました。

 アーキテクチャの詳しい内容は、以下にあります。

 *因みにこの命令セットでは、コアの数に依存しないようなマルチコアのコンパイラコードが吐けるようになっています。

マルチコア完動まで

 まず、僕がズルズルと並列化判定で苦戦していたため、コンパイラで並列性を認識できたのが2月の初めでした。最終発表が2/21で、残りやるべきことが以下のように盛りだくさんだったのですが、班全体で怒涛の勢いで進捗が生まれました。

 

  1. 1stコンパイラ並列化
  2. 1stアセンブラ並列化
  3. 1stシミュレータ並列化
  4. 2ndコンパイラ作成
  5. 2ndシミュレータ作成
  6. 2ndコア、レイトレプログラムでデバッグ
  7. 2ndコンパイラ並列化
  8. 2ndアセンブラ並列化
  9. 2ndシミュレータ並列化
  10. 2ndコア並列化

 

 シュミレータが完成すると、まずコンパイラのバグがどんどん出てきます。なのでどんどん潰します。その後、2ndについても同じステップを踏み、シュミレータで完動するようになります。この段階で(コンパイラコードの正しさが保証されてから)、コア上でレイトレプログラムを動かしデバッグできるようになります。

 ここで中規模プログラムを実行した段階では出てこなかったコアのバグが出てきて、コア係が非常に苦戦していました。(自分が先に2ndコンパイラを作成していなかったせいで大きな負担をかけてしまったと思います。)一週間ほど、コア係の健闘をただ祈る期間があり、遂に、、

 

f:id:eguchishi:20170909022647p:plain

 

となり、マルチコア完動しました(お疲れ様ですm()m)。

 全てが報われる瞬間でした笑 

 感想

 結構大変でしたが、予想以上に面白いCPU実験になりました。最初は『レイトレプログラムをマルチコアで動かす』というのは夢のような話だったのですが、だんだん現実味が出てきて、最後は思っていた以上の結果を見ることができました。キレキレのコア係をはじめ、チームにも恵まれたなぁと思います。

 参考リンク

コンパイラコード -> https://github.com/cpuex2016D/min-caml.git

・D班全体のリポジトリ -> cpuex2016D · GitHub

・コア係の記事 ->    CPU実験2016年度D班コア係 - sueki743's blog

mincamlのソース ->  速攻MinCamlコンパイラ概説

・過去の記事など ->

CPU実験でコンパイラの改造でハマったところ - Handwriting

CPU実験 - てきとーな日記

東大理情名物のCPU実験で毎週徹夜したお話(技術編) | eureka tech blog