• 分散プログラムには信頼性とスケーラビリティが必要である
• しかし、両方を兼ね備えたプログラムを作成することは容易ではない
• そこで、当研究室では信頼性とスケーラビリティの両方をもったプログラムの記述をサポートする、分散フレームワークAliceを開発を行なっている
• Aliceはデータとタスクを細かく分割したDataSegment、CodeSegmentでプログラム記述する
• DataSegment、CodeSegmentで記述することにより高い並列処理を行うことができる
• Aliceの並列性能を確認するためbitonic Sortを実装したが、実行速度に問題があったため、 本論文では実行速度の改善を試みた

• 本研究室で開発を行なっている分散管理フレームワーク
• Data SegmentとCodeSegmentによりプログラムを記述する
• 並列フレームワーク Ceriumに似たタスク管理機構と先行研究であるFederated Lindaに似たData Segmentの通信構造をもつ
• メニーコアのマシンが主流である背景からSEDA Architectureが採用している

Data Segmentは数値や文字列を構造体的に保持する。
Aliceではデータベース的に扱うが、通常とは異なりKey毎にQueueを持つ
以下のAPIでデータの送受信を行う

• put
• update
• peek
• take

• AliceではCode Segmentと呼ばれる単位でタスクを生成する
• Code Segmentは依存するData Segmentが全て揃うとActiveになる
• Input/Output Data SegmentがCode Segment間の依存関係を自動的に記述する

Aliceは先行研究であるFederated Lindaよりも処理速度が遅い。
作成した例題によりOverHeadの原因が見つかっている

• Message Packによる型変換
• SEDA Architecture
• Output Data Segmentの作成時のコピー

シリアライズライブラリの一種。
シリアライズされたデータにオブジェクトの型情報を併せて埋め込むため、
IDL(インターフェース定義ファイル)を用意する必要がない。
異なる言語間でオブジェクトを交換可能
MessagePack for Java のVersion 0.6からValue型が追加されており、
オブジェクトを動的型付け可能

• MessagePackを使用することで他のノードとData Segmentの送受信が高速に行うことができる
• AliceはData SegmentをQueueに追加する際にValue型に変換
• アノテーションをつけることにより既存のData Segmentと互換性を保ったまま拡張することができる

分散プログラムにおいて、常にVersionが同じとは限らない。
旧Versionとの互換性のため、Value型に変換している。
しかし、追加するタイミングで変換を行うと、外部と通信を行わない
DataSegmentに対しても型変換を行う

マルチコアを活かすためにAliceではSEDA Architectureを採用している。
SEDAとはマルチコアスレッドを用いて大量の接続を管理し、
データを処理毎に分けられたステージと呼ばれるスレッドで処理を行う。

• putやtakeなどの要求に沿ったCommandを作成するステージ
• Commandを処理するステージ
• DataSegmentをCodeSegmentにセットするステージ

SEDAは多段のパイプラインによって構成されるためレスポンスが遅れる。
スループット重視の実装であるため、レスポンスが要求される
Sortのようなプログラムに向いていない。
非力なマシーンでは、スレッドを切り替えが頻繁に起こり、
レスポンスを下げる要因になる。

SEDA Architectureを実装するにあたり、LinkedBlockingQueueを使用している。

• LinkedBlockingQueueは片方向の連結リストを使用したQueue
• enqueue/dequeueの操作時は排他制御は別々のlockで管理
• enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)

• MessagePack
MessagePackによるValue型に変換が必要なケースは、
他のノードに対してData Segmentを送信する場合である。
DataSegmentを追加するタイミングでValue型に変換せず、
メッセージを送信する前に変換を行えばよい。
• SEDA Architecture
Sortのようなにレスポンスが必要なプログラムのために、SEDAのステージ上ではなく、 直接DataSegmentを取得するAPIを用意する

• Output Data Segment作成時におけるコピー
Ceriumでも同様なコピーの問題があり、Input Data SegmentとOutput Data Segmentを Swapすることで解決している。Aliceでも同様の方法で解決する。
Data SegmentはCode Segment内ではReceiverという変数が保持している。
このReceiverをOutput Data Segmentにすることで無駄なコピーを減らす。

実験環境

今回行った改善による効果を調べるために3つの実験を行った。

• SEDAの有無

Data Segmentを取得するCode Segmentが10000回実行されるまでの時間を測定

• flipとputの比較

既存のAPIのputと新しく追加したAPIであるflipをつかい10000回、Data Segmentを追加されるまでの時間を測定

• Bitonic Sortによる比較

今回行った改善(ただし、MessagePackによる改善を除く) Bitonic Sortで100万の要素をSortされるまでの時間を測定する。分割数は10個で行った

実験結果は100回行った平均である

SEDA	あり	なし
実行時間(ms)	27.72	7.53

API	flip	put
実行時間(ms)	61.12	65.24

	改善前	改善後
実行時間(ms)	199.38	184.64

Bitonic Sortの例題では約10％程度改善された

• 今回行った改善により、以前のAliceよりも約10％程度速度が改善した
• しかし、Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度
• 分散環境下ではFederated Linda以上の速度が求められる
• また、Aliceが抱える問題は速度だけではない
• 信頼性の問題や永続性の問題についても改善をしなければならない