-title: CodeSegmentとDataSegmentによるプログラミング手法

--author: 河野 真治, 杉本 優

--並列分散フレームワーク

本研究室では分散プログラミングと並列プログラミングのツールを開発してきた。

    分散プログラミング用のFederated Lidna
    並列プログラミング用のCerium

これらの経験から並列分散を統一的に扱えるプログラミングフレームワークを考えたい。

--並列分散フレームワークには何が求められるのか

    並列実行単位の記述
    プロトコルの記述
    実用的な実装
    実験環境の用意
    多言語対応
    検証や証明への対応

--Federated Linda 

データの塊である Tuple を使って通信するフレームワーク

   in Tuple を取り出す
   out Tuple 書きだす

--Federated Linda の Pros and Cons

--Cerium 

Task 単位で並列実行するツール

--Cerium の Pros and Cons

--Data segment と Code Segment

--Java Implmentation : Alice

--CS/DS API

--Alice Architecture

--Sample Application

--Experiment

--Ring





に置いて、タスクをCode Segment、データをData Segmentという単位に分割して記述する方法を提唱している。</p>
<p>しかし、前述したプログラムをプログラマーが一から記述していくことは大変である。</p>
<p>そこで、本研究室の卒業生である赤嶺一樹氏が分散ネットフレームワークAliceのプロトタイプを作成した。</p>
<p>本研究では実際にAliceを利用して、水族館の例題を作成した。また、Federated Lindaとの性能比較を行った。そして、Aliceの問題点の洗い出し、APIの見直しを行った。</p>
	  
--発表内容
<ul>
<li>Aliceの紹介
<li>プログラムの記述方法
<li>水族館の例題と性能評価
<li>まとめと課題
</ul>

--Alice
<ul>
<p>Alice は本研究室で開発を行なっている分散タスク管理フレームワークである。</p>
<p>Cell用のOpen CL に似たTask管理用フレームワークCeriumと
	   Lindaを相互接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見を生かされている。</p>
<ul>

--Cerium
<ul>
<p>Ceriumは当研究室で開発を行なっている並列プログラミングフレームワークである。</p>
<p>CeriumではTaskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。</p>
<p>Taskには依存関係がありデータの依存関係がそのままTaskの依存関係になることが多い。</p>
<p>繰り返し使われるデータの管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。</p>
</ul>

--Data Segment API
<ul>
<p>Data Segmentは数値や文字などのデータを構造体的に保持するが、分散プログラムにおいてData Segmentの相互参照が問題になってくる。</p>
<p>AliceではData SegmentにユニークなKeyを持たせ、Key Value Storeとして扱っている。Key毎のキューがあり、Key毎に順に実行される。<br>
<div align="center">
<img src="images/dataSegment_key.png">
</div>
          
</ul>


--Data Segment API
<ul>
<p>Data Segmentを管理するのが、Data Segment Manager
	   各ノード毎に、Local DS ManagerとRemote DS Managerが存在する。</p>
<p>Local DS Managerはノード固有のKey Value Storeであり、Remote DS Managerは他のノードのLocal DS Managerのproxyである。
	 AliceのTopology Managerが自動的に構成する。</p>	 
<div align="center">
<img src="images/lrds.png" width=500>
</div>
</ul>


--Data Segment API
<ul>
	  以下が用意されているData Segment APIである。
<li>void put(String key, Value val)</li>
<li>void update(String key, Value val)</li>
<li>void peek(Receiver receiver, String key)</li>
<li>void take(Receiver receiver, String key)</li>
<p>これらを用いてデータの送受信を行う。</p>
</ul>

--Data Segment API - put
<ul>
<li>データを追加する</li>
</ul>
<div align="center">
<img src="images/put.png" width=70%>
</div>
<ul>
<p>putを行うとデータがenqueueされる。</p>
<p>putするたびにKeyが持つindexがincrementされる。</p>
</ul>
      
--Data Segment API - update
<ul><li>データを置き換える</li></ul>
<div align="center">
<img src="images/update.png" width=70%>
</div>
<ul>
	 putと異なる点は先頭データを削除し、データを追加する。
</ul>
      
--Data Segment API - peek
<ul><li>データを取得する</li></ul>
<div align="center">
<img src="images/peek.png" width=50%><br>
</div>
<ul>
	 peekはデータを取得しreceiverに渡す。
</ul>
      
--Data Segment API - peek
<div align="center">
<img src="images/peek1.png" width=60%><br>
</div>
<ul>
<p>要求したデータがない場合にはwaitListに登録する。</p>
	   データがput、updateされる際に要求したデータがあるかどうかを再びチェックする。
	 
</ul>

--Data Segment API - take
<ul><li>データを取得して取得されたデータはdequeueされる</li></ul>
<div align="center">
<img src="images/take.png" width=50%><br>
</div>
<ul>
<p>基本的な動作はpeekと同じである。</p>
<p>peekと異なる点は取得されたデータがdequeueされる。</p>
</ul>

--Data Segmentの実装
<ul>
	 Data Segmentのデータ表現はMessagePackを使用。
</ul>
<ul><p>JavaにおけるMessagePackのデータ表現</p>
<li>一般的なJavaのクラスオブジェクト</li>
<li>MessagePack for JavaのValueオブジェクト</li>
<li>byte[]で表現されたバイナリ</li>
</ul>
<ul>
<p>Data Segment APIでは</p>
	 MessagePack for javaのValueオブジェクトを使用</p>
         MessagePackのバイナリにシリアライズできる型のみで
         構成されているため自己記述式のデータ形式
</ul>

--Data Segmentの実装
<ul>
<p>Valueオブジェクトは通信に関わる際には、シリアライズ、デシリアライズを高速に行うことができる</p>
<img src="images/FishPoint.png" width=700><br>
	  ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを記述することが可能
</ul>

--CodeSegment
<ul>
<li>Code Segmentはタスクのこと</li>
<li>ユーザーが記述する際にCode Segment内で使用する<br>Data Segmentの作成を記述</li>
<li>Input Data SegmentとOutput Data Segmentを作るAPI</li>
<li>必要なInput Data Segmentが揃った時に実行される</li>
</ul>       

--Input Data SegmentとOutput Data Segment
<ul>
<li>localかremoteを指定</li>
<li>Data Segmentに関連付けされているKEYを指定</li>
</ul>

<ul>
--Data Segmentの例
<img src="images/SendWidth.png" width=600>
</ul>

--Input Data Segmentの例       
<ul>
<img src="images/ids.png" width=400><br>
	 Receiverの作成<br>
	 PEEK,TAKEのどちらかを選択
</ul>
<ul>
<img src="images/idsSetkey.png" width=600><br>
	 第1引数 マシン名<br>
	 第2引数 Data Segmentに関連付けられているKEY<br>
	 第3引数 index(指定しない場合は先頭データが取得される)<br>
</ul>

--Output Data Segmentの例
<ul>
<img src="images/ods.png" width=400><br>
	  putかupdateのどちらかを選択
</ul>
<ul>
      	  第1引数 マシン名<br>
	  第2引数 Data Segmentに関連付けるKEY<br>
	  第3引数 Data Segment<br>
</ul>

--Code Segmentの実行方法
<ul>
<img src="images/StartCS.png" width=600><br>
</ul>
<ul>
	  AliceにはCのmainに相当するStart Code SegmentというCode Segmentが存在する。<br>
	  Start Code SegmentはInput Data Segmentが存在しない。
</ul>

--Code Segmentの実行方法
<ul>
<img src="images/execute.png" width=600><br>
</ul>
<ul>
	 このStart Code Segmentをnewし、executeメソッドを呼ぶことでCode Segmentを実行することができる。
</ul>

--Code Segmentの記述方法
<ul>
<img src="images/TestCodeSegment.png" width=600><br>
</ul>
	ユーザがCode Segmentを記述する際にはCode Segmentを継承する。<br>
	runの中に実際にさせたい処理を記述する。
      
--Topology Manager
<ul>
	  Alice同士の接続トポロジーを管理する。<br>
	  トポロジーファイルを読み込み、参加を表明したクライアントに接続すべきクライアントのIPアドレスやポート番号、接続名を送る。
<div align="center">
<img src="images/topology.png" width=350>
</div>
</ul>

--Topology Manager
<ul>
	  Topology Manager関連の通信は全て、Code Segmentで実装されている。
</ul>

--トポロジーファイル
<ul>
<p>トポロジーファイルはDOT Languageと言う言語で記述される。</p>
	  DOT Languageはプレーンテキストを用いてデータ構造としてのグラフを表現するデータ記述言語の一つ。<br>
	  DOT Languageのグラフ構造を用いてTopology Node間の接続を表現する。<br>
</ul>
      
--トポロジーファイルの記述方法
<ul>
<img src="images/topologyfile.png">
<p>dotコマンドを用いて、グラフの画像ファイルを生成することができるのでトポロジーが正しいか確認することができる。</p>

</ul>

--トポロジーファイルの確認方法
<ul>
<p><strong>dot -T png ring.dot -o ring.png</strong></p>
<div align="center">	  
<img src="images/dot.png">
</div>
</ul>
      
--水族館の例題
<ul>
<p>複数の魚が複数のディスプレイ上を移動する。</p>
<p>魚のうち一匹はクライアントが操作することができる。</p>
<p>トポロジーはツリー状に構成してある。</p>
</ul>
<div align="center">
<img src="images/aquarium.png" width=800>
</div>

<div align="center">
<img src="images/commnuication.png" width=600>
</div>
      
--性能比較 - 実験概要
<ul>
	  AliceとFederated Linda で性能比較を行った。<br>
	  Ring型のトポロジーを構成、メッセージが100周する時間を計測。
	  1周あたりの平均時間を求めた。
<div align="center">
<img src="images/ringTest.png">
</div>
	  パケットのサイズは10byte,10Kbyte,100kbtyeで実験
</ul>

--実験環境
<ul>
	  ブレードサーバー上の仮想マシンによる仮想クラスタ環境を用いて実験した。<br>
<p><strong>ブレードサーバー詳細</strong></p>
<table style="font:Osaka;text-align:right;" border="2" >
<tr>
<td>マシン台数</td>
<td>8台</td>
</tr>
<tr>
<td>CPU</td>
<td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td>
</tr>
<tr>
<td>物理コア数</td>
<td>12</td>
</tr>
<tr>
<td>論理コア数</td>
<td>24</td>
</tr><tr>
<td>CPU キャッシュ</td>
<td>12MB</td>
</tr>
<tr>
<td>Memory</td>
<td>132GB</td>
</tr>
</table>
	  
</ul>
--実験環境
<ul>
<p><strong>仮想クラスタ詳細</strong></p>
<table style="font:Osaka;text-align:right;" border="2" >
<tr>
<td>マシン台数</td>
<td>48台</td>
</tr>
<tr>
<td>CPU</td>
<td>Intel(R) Xeon(R) X5650 @ 2.67GHz</td>
</tr>
<tr>
<td>物理コア数</td>
<td>2</td>
</tr>
<tr>
<td>論理コア数</td>
<td>4</td>
</tr><tr>
<td>CPU キャッシュ</td>
<td>12MB</td>
</tr>
<tr>
<td>Memory</td>
<td>8GB</td>
</tr>
</table> 
</ul>

--実験結果
<ul>
<strong>10byte</strong><br>
<img src="images/ring10B.png" width=650>
</ul>

--実験結果
<ul>
<strong>10kbyte</strong><br>
<img src="images/ring10KB.png" width=650>
</ul>
      
--実験結果
<ul>
<strong>100kbyte</strong>
<img src="images/ring100KB.png" width=650><br>
	  データ量が増えると差が縮まっている。これはここの通信の手間の影響が大きことを示している。
</ul>
      
--評価と考察
<ul>
	  今回の実装はJavaによりCode SegmentとData Segmentに必要なAPIを洗い出すものだった。この実装でも問題をいくつか発見した。<br>
<p><strong>API</strong></p>
<li>Class継承したりData Segmentの作成にFactory objectを使うのはJavaを使う際の技術的な問題</li>
<li>JavaのObject指向な記述が全体を煩雑にしている部分がある</li>
<li>updateはData Segmentの競合的な更新に使われるべきだと思われる</li>
</ul>
      
--評価と考察
<p><strong>SEDA</strong></p>
<ul>
<li>Federated Lindaに比べ遅い原因の一つはSEDA architectureのせいと思われる</li>
<li>SEDAはスループット重視の実装であり、多段パイプラインのせいでレスポンスが遅れてしまう</li>
	    
</ul>
      
--評価と考察
<ul>
<li>スレッドプールを使わないほうが、Ringの結果は良い</li>
<img src="images/notp.png" width=650><br>
</ul>

--評価と考察
<p><strong>MessagePack</strong></p>
<ul>
<li>今回の実装では単純なMessageの転送時にもMessagePackのdecode/encodeをしているが、overheadになってしまうため、decode/encode抜きに直接操作できるほうが望ましい</li>
<li>Data Segmentの一部の修正をするたびにData Segmentが再構成されているがこれは望ましくない</li>
<li>AliceもCeriumのようにInput Data SegmentとOutput Data SegmentをswapするAPIがあるとよいと思われる</li>
</ul>


--評価と考察
<p><strong>Key</strong></p>
<ul>
<li>分散実装においてはData Segmentの相互参照はKey経由が打倒であるが、並列実装では全てのData SegmentをKey Value Storeに格納するのは、性能的な問題を引き起こす</li>
<li>分散記述と並列記述を分ければ解決するが、2つの記述がかけ離れるのは好ましくない</li>
<li>本来Key Value storeは持続性を持たせる必要がある</li>
</ul>

--評価と考察
<p><strong>Java</strong></p>
<ul>
<li>Data SegmentはCode Segmentがactiveの時のみメモリ上にあり、その最大値はActive Taskの量を見積もればよいのでAliceにGarbage Collectionの機能は必要ない</li>
<li>key Value Store 上のデータは決してGarbage Collectionの対象にはならないが、それがGarbage Collectionに負荷をかける結果となるためAliceとJavaの相性は悪い</li>
</ul>

--評価と考察
<p><strong>拡張性</strong></p>
<ul>
<li>分散アプリケーションのプロトコルは常に変更されるため、Aliceもそれに対応する必要がある</li>
<li>Keyとトポロジーマネージャーをプロトコル毎に別に用意すれば複数のプロトコルを同時に走らせることが可能</li>
<li>Data SegmentとCode Segmentの結びつきは弱いため、Data Segmentに余計な値がある場合、値が足りない場合に適切な値を設定することで古いCode Segmentを変更するとこなしにプロトコルを拡張できる</li>
</ul>

--まとめと課題
<ul>
<p>今回Code SegmentとData Segmentによる並列分散フレームワークのJavaによる実装を示した。実装でしかえられない知見を得ることができた。</p>
<p>今回Javaによる実装を行ったがJavaがAliceの実装に不向きであるということもわかった。</p>
<p>
<li>Code Segment/Data Segmentを見たコンパイラ的アプローチ</li>
<li>実行時最適化</li>
<li>CbCによる実装</li>
	  などが有効、効果的だと思われる。</p>
<p>今回はノード内の並列実行やGPGPUによる並列実行などは考慮していない。将来的にそれを含め実装をしていきたい。</p>
</ul>