第 14 回 CSP 研究会 ( 東洋大学 ) CSP ベースの並列処理記述言語の動向 福永力 首都大学東京 数理情報科学専攻 29/11/2014 1
内容 米国学部情報教育カリキュラム改定案 (2013) 最近のCSPベース並列処理記述言語の動向 ProcessJ(Univ. Nevada Las Vegas) Occam- π(inmos- Univ. Kent UK) Guppy(Univ. Kent) Sire(Univ. Bristol UK) まとめ 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 2
参考にしたドキュメント J.B.Pedersen and M.L.Smith, ProcessJ: A possible Future of Process- Oriented Design, Proceedings of CPA2013 (CommunicaUon Process Architecture), pp.133-156, 2013 J.W.Hanlon, Scalable abstracuons for general purpose parallel computauon, Thesis for Ph.D, 2014, University of Bristol, UK 福永力 π- calculus と occam+π 第 11 回 CSP 研究会 東洋大学白山キャンパス May,25, 2013 Fred R.M.Barnes, Guppy, Slides presented at CPA2011(Limerick) and CPA2013(Edinburgh) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 3
学部情報処理教育カリキュラムの提案 2013 by IEEE and ACM ( 松井様ご紹介 ) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 4
情報教育入門コースへの提言 並列処理プログラミング言語教育の導入 ( その page.44) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 5
ProcessJ (Pedersen Smith: CPA13) 新たな並列処理言語と開発環境の提言現代の MulU- core system での並列処理はどのようなモデルを基礎とすればよいか? Java の threads 利用の並列処理は共有メモリ方式をとる. この方式は並列処理という複雑な概念の上にさらに nondeterminisuc, race condiuons, 相互排除技術 (Mutex, threads- and- lock) の導入などの問題を持ち込むことになる. Lock 機構を導入することなく安全にプログラムできてかつその正当性が論証できる同期的メッセージ交換型な並列処理モデル CSP に基礎を置く process oriented な言語こそ MulU- core system での並列処理プログラムには理想的なものであろう. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 6
Occam- π 言語がシンプルで表記がオリジナルな CSP に近い しかし Occam は 1980s の言語で伸びしろが少ない. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 7
JCSP CSP base の JCSP(Java- CSP) だと共有メモリはいらない. しかし channel 入出力 PAR や ALT などのコンストラクタはメソッドで実装 channel 交信で送受される 2 つの変数はリファレンスを共有する 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 8
Process Oriented Language: ProcessJ 研究 教育さらに昨今の言語開発の動向を踏まえて新たな Process Oriented な並列処理言語 ProcessJ の提案 Java 風だが JCSP より表記はシンプル par とか alt のコンストラクタも言語のプリミティブとして組み込む. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 9
Proposed Project for ProcessJ 技術的な側面 CSP ベースの現代的な並列処理言語 残念ながら言語のより深い内容については前スライド以外不明 ( 言及なし ) コンパイラの開発 通常のコンパイル 実行形式の生成 FDR2 検証用スクリプト生成 ソース ProcessJ C++ 変換 JavaScript へ変換 (via C++ LLVM JavaScript 1) ) (in- browser プログラミング用 ) IDE( 統合開発環境 )/GUI グラフィックプログラム環境 runume システム online repository cloud storage( プロセス再利用や共有 ) target は x86 を ( おそらく ) 仮定. しかし他のアーキテクチャにも C++ や JavaScript から変換可能としている 教育的側面 Web を通じて Lecture notes exercises slides handouts の配布 本や Video 教材の作成 1) 既存の C++ LLVM(low level virtual machine) JavaScript 変換プログラムの利用 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 10
新しいコンピュータ言語のインフラ機構 著者たちの言い分 ; 現代の新言語の利用には以下のようなインフラを完備しないとならない ( のだそうだ ) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 11
Occam- π の発展 (1990 年代以降 ~2005 年まで ) occam- π は occam+π と書くことも MOBILE and non- MOBILE barriers 並列プロセスの終了同期 MOBILE process types チャンネルを通したプロセスの送受信 MOBILE channel types チャンネルを通したチャンネルの送受信 MOBILE data types 動的データ移動 (reference data type) run- Ume sized MOBILE arrays Mobile data 動的配列サイズ run- Ume sized PAR replicators PAR 動的繰返し数設定 FORKed dynamic process creauon 動的プロセス生成 動的生成 (Forked 生成 ) プロセス間での共有メモリアクセス process priority support 32 段階プロセス優先度の割当て self- recursion for PROCs プロセスの再帰 (by Inmos 1988) data structure の組込み (by Inmos 1988) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 12
Occam- π から Guppy(Barnes at CPA2011 & 2013) へ Occam- π の進展は止め 新言語にて遺産を引き継ぐ (Occam- π は所詮 Occam にネジ止め (bolt on) されたものだった ) CSP ベースの Occam- like な言語機能 ( コンストラクタ ) をもつ Zero aliasing semanucs の堅持 (chan 交換後の 2 変数は独立に存在 ) Indent ベースのブロック構造を維持 Python や Go もこの形で成功している (New) 標準 (default) 計算形態として SEQ( 逐次型 ) を設定 (New) 型の充実 ( カスタム化にも対応 構造体の導入 ) コンパイルコードの高速実行 run Ume 時の型検査や garbage collecuon は省略 CCSP ライブラリの利用 アーキテクチャ指定なしの言語 コンパイラは LLVM(low- level- virtual machine) 止まり 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 13
channel とプロトコル chanend 宣言 /channel 入出力 chan?(int) e chan!(int) d par d! 100 e? a mobile channel 独自 Protocol 指定 独自プロトコルの設定 ( より複雑な通信にも対応 ) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 14
Mobile channel (channel を通した channel の転送 ) Bind により chanend 対を明示 高階度 (Higher order mobility)channel 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 15
コンストラクタ ( プリミティブ ) if, seq, (pri)par, (pri)alt, while, case は occam 仕様 Occam- π で実現させた Barrier も組み込む 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 16
実際のプログラム Dinning Philosopher より 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 17
Guppy の現状 : Occam- π からどこに行く? MOBILE and non- MOBILE barriers 並列プロセスの終了同期 MOBILE process types チャンネルを通したプロセスの送受信 MOBILE channel types チャンネルを通したチャンネルの送受信 MOBILE data types 動的データ移動 run- Ume sized MOBILE arrays Mobile data 動的配列サイズ run- Ume sized PAR replicators PAR 動的繰返し数設定 FORKed dynamic process creauon 動的プロセス生成 動的生成 (Forked 生成 ) プロセス間での共有メモリアクセス process priority support 32 段階プロセス優先度の割当て self- recursion for PROCs プロセスの再帰 (by Inmos 1988) data structure の組込み (by Inmos 1988) 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 18
Sire(Hanlon, Ph.D thesis, U.Bristol 2014) Sire とは XMOS の基本構造である XS1 のもとで 並列処理プログラム記述言語としての Sire コンパイラ 1. 字句解析 構文解析 2. 意味解析 3. プログラム成分 ( プロセス サーバ chanend) のリソース割当 4. 実行バイナリデータの生成 (Master と Slave の 2 種 ) Sire( サイァ ) とは bear とか create と同義 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 19
Sire プログラミング言語計算モデル Sire プログラムはプロセスの集まり (collecuon) からなる. 各プロセスはコマンドの並び (sequence) を実行していく. 相異なる 2 つのプロセス間で channel を通した一対一データ通信をすることができる.Channel 端を chanend と呼ぶ. プロセス間の通信を通して同期をとることができる ( メッセージ送出プロセスは相手がそれを受け取るまで実行を中断する ). server と呼ばれる特殊プロセスが導入できる. どのプロセスもこの server を一定のプロトコールの元で呼び出すことが可能. 通常 Sire プログラムは複数 (N) のプロセッサからなるシステム上で実行される. 1 つのプロセッサは複数のプロセスを同時実行できる 1). Sire プログラムは Master プロセッサから始まり複数のプロセスが時間とともに複数のプロセッサ (1..N- 1) に移行し そこで実行される. やがて Master プロセッサのメインプロセスを終了させることによりその処理が終了する. 1) ターゲットシステムとして XMOS XS1 を仮定している. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 20
Sire PrimiUve commands 代入文 (assignment) x := 2014 Input chan0? variab Output chan1! 1000 Connect connect chan0 to chan1 skip stop 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 21
Sire Structured command alt { les? v: out! v right? v: out! v } ガード付きもあり ; alt { enabl & les? v : out! v enabr & right? v : out! v } if e then C else D これは if { e: C ~e: D } とも書ける while e do C 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 22
Sire Process ComposiUon SequenUal( 逐次コマンド処理 )[ ; ] { a:=1 ; b:=10 ; c := a+b ; chan0! c } Parallel( 並列コマンド処理 ) [ & ] {a := 1 & b := 2 & ch0? s } interface interface(ch0):{a := 1; ch0! a } & interface(ch1):{b := 2; ch1! b } & interface(ch0,ch1):{ch0? s ; ch1? t ; c := s + t } 省略 (abbreviauon) を使って p is interface(chanend c): {connect c to q.c; c! 11} q is interface(chanend c): {var v: connect c to p.c; c? v } 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 23
Sire Server(Sire のユニークな機構 ) (Scope を同一にする ) どのプロセスからも呼ばれる特殊形態のプロセスを server と呼ぶ. 複数のクライエントプロセスから server を呼び出す (call) とは subrouune 呼び出しあるいは Remote(Local) Procedure Call を行っていることと同じ意味合いを持っている. 共有メモリ ( プロセッサの固有メモリ以上のメモリが必要な場合 ) や共有資源のアクセスを server に一元管理させるのに有効である. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 24
Sire Server(alt の利用 ) 複数プロセス間でデータを共有する server count() is interface(call inc(), dec()): { iniual c := 0 alt { accept inc(): c := c+1 accept dec(): c :=c - 1 }} ガードを立てる server count100() is interface(call inc(), dec()): { iniual c := 0 alt { c < 100 & accept inc(): c := c+1 c > 0 & accept dec(): c :=c- 1 }} 複数プロセス間で配列を共有する server Store() is interface(call read(val i, var v), write(val i, val v) ): { var[n] a : alt {accept read(val i, var v) : v := a[i] accept write(val i, val v): a[i] := v }} として s is Store(): (Store を s に名前付け ) s.write(10,23); s.write(11,30); s.read(10,u); s.read(11,v); w := u+v ;s.write(12,w) ; 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 25
実行モデル I (XMOS XS1 での動作を仮定 ) Sire プログラムの稼働するシステムは 0..N- 1 の付番されたプロセッサとそれらをつなぐネットワーク そして各プロセッサはそ れぞれメモリ chanend の集合 それに複数のプロセスを動かす機構 (threads;logical core) と 2 つの異なるプロセスにある chanends が channel 通信できるメカニズム (connect) がそなわっていることが必要. Sire プログラムのコンパイラは実行形式として Master( ユーザプログラムと run Ume kernel) Slave(run Ume kernel のみ ) の 2 種類のバイナリコードを生成する Master はプロセッサ 0 に Slave はプロセッサ 1..N- 1 に反復的に ロードされる. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 26
実行モデル II ( 実行開始と終了 ) 各プロセッサは kernel service process を開始する. 続いて Master にある Service process がユーザプログラムのメイン プロセスを新たなプロセスとして実行させることによりシステム が開始される. ユーザプログラムが開始されるとその成分である各プロセスが 開始される. しかしそれらは開始直前にあらかじめ割り当てられたプロセッサ ( のメモリ ) に移動され そのプロセッサでプロセス が実行されていく. すべてのアクティブプロセスが終了し流れがプロセッサ 0 にもどり メインプロセスが終了することによりシステム全体は停止する. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 27
コンパイル時のリソース割当 コンパイル時にプロセスやサーバなどのプログラム成分を抽出してターゲットシステムの枠組みの中でそれぞれの実行プロセッサを割り当てる. 現在プロセスの動的生成などはできない ( ように設定されている ) ので割当はなかば機械的に行われる. chanendの割当とそのリモートプロセッサでの相手側 chanendとの対応もコンパイル時に自動的に行われる. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 28
プログラムコードの動的分配 プログラムコンポーネント ( サーバー プロセスなど ) は run Ume 時に ( コンパイル時に割り当てられた ) 実行を担当するプロセッサに移行 (move) される. 実行が終了するとそのプロセッサのメモリからはずされる. 実行時の資源 ( メモリ ) の有効 ( 再 ) 利用 ( プロセッサは現在実行中のプロセスのみメモリにロード ) コンパイル時間の短縮 ; システムのプロセッサの数によらない実行形式の作成 (master と slave にすべて集約 ) バイナリデータ量の縮小 ; プロセッサ数によらない 素早いブーティング ;master のロードと slave の反復的なロード 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 29
Run Ume kernel プログラムは run Ume kernel も組み込まれてコンパイルされる. Run Ume kernel はユーザプログラムの実行にあたり自プロセッサに送られるプロセスを受け取って実行させたり そのプロセスの該当 chanend とそれを通じて更新する他のリモートプロセッサ上のプロセスの chanend をつなげたりする. Run Ume kernel には 2 種類あり以下の役割を担い そのため各プロセッサの Logical core(thread) を 1 つ専有 ( 占有 ) する ; Service kernel: リモートプロセッサとの交信 Program kernel: Service kernel を通じて得たプロセスの実行 コンパイラ出力の実行バイナリ形式の 1 つ Master は run Ume kernel+ ユーザプログラム Slave は run Ume kernel のみの実行形式が組み込まれる. Master は Xcore の processor 0 に 他の processor 1..N- 1 には Slave( どれも同じもの ) がロードされる. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 30
Master Slave メモリレイアウト 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 31
まとめ 学部教育初期段階より並列処理パラダイムの教育を実施したらどうか?(ACM&IEEE の提言 ; 2013) ProcessJ 言語そのものの詳細は不明だが CSP をその基盤に置こうとしている 言語の普及のための統合開発環境はどうあるべきかを議論 アーキテクチャに依存しない言語 コンパイラを模索 Guppy Barnes(occam- π 開発者の一人 ) のみでデザイン 開発が進められている. CSP に対して Occam- π よりはやや保守的 ( いまのところ ) アーキテクチャに依存しない言語 コンパイラを模索 Sire XMOS XS1 アーキテクチャを念頭に また純粋な CSP の枠組みでの言語を設計 しかし server 機能の導入で共有資源の一元管理など CSP を一歩踏み出してはいる XC を凌ぐものになるか 自動プロセッサ配分や Kernel などの でき が重要 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 32
Backup slides 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 33
Inmos Occam の問題点 1970 年代のプログラミング言語の概念で設計されている. インデントによる構造化プログラミング 構造が視覚的に捉えにくい データ有効範囲 ( スコープ ) の設定が煩雑 プロセスの再帰的呼び出しが出来ない. 配列のポインタ処理ができない. 複合型データ構造 (record あるいは structure) がない. 言語の要素 ( 配列 変数 チャンネル プロセスなど ) の動的取り扱いができない ( 実行時にサイズの変更 必要ない変数やチャンネルの抹消 プロセスの生成 ). チャンネル通信が一対一 多対一のみで一対多はできない. 並列プロセス数も動的取り扱いができない などなど. 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 34
Run Ume kernel 構造 29/11/2014 第 14 回 CSP 研究会 ( 東洋大学 ) 35