Mercurial > hg > Papers > 2015 > nozomi-sigos

annotate paper/sigos.tex @ 0:0127effb8fcd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Tue, 05 May 2015 15:36:41 +0900
parents
children e13be99f69b6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \documentclass[techrep]{ipsjpapers}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \usepackage[dvipdfm]{graphicx}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \usepackage{url}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 \usepackage{listings}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 \usepackage{mediabb}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \lstset{%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 language={C++},%使用言語
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 basicstyle={\small},%書体
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 commentstyle={\small\itshape},%コメントの書体
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 keywordstyle={\small\bfseries},%キーワードの書体
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 %identifierstyle={\small},%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 %ndkeywordstyle={\small},%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 stringstyle={\small},%文字列の書体
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 frame={trlb},%外枠
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 breaklines=true,%改行
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 columns=[l]{fullflexible},%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 xrightmargin=0zw,%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 xleftmargin=3zw,%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 %numbers=none,%行番号の表示
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 %numberstyle={\scriptsize},%行番号の書体
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 %numbersep=1zw,%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 %stepnumber=1,
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 lineskip=-0.5ex,%
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 captionpos=b,%キャプションの位置
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 }
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 \renewcommand{\lstlistingname}{Code}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 \input{dummy.tex} %% Font
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 % ユーザが定義したマクロなど．
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 \makeatletter
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 \begin{document}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 % 和文表題
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 \title{分散フレームワークAliceの圧縮機能}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 % 英文表題
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 \etitle{}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 % 所属ラベルの定義
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 \affilabel{1}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 \affilabel{2}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 \affilabel{3}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 % 和文著者名
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \author{
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 照屋 のぞみ\affiref{1}\and
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 杉本 優\affiref{2}\and
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 河野 真治\affiref{3}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 }
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 % 英文著者名
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 \eauthor{
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 Nozomi TERUYA\affiref{1}\and
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 Yu SUGIMOTO\affiref{2}\and
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 Shinji KONO\affiref{3}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 }
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 % 連絡先（投稿時に必要．製版用では無視される．）
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 \contact{照屋 のぞみ\\
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 〒903-0213 沖縄県西原町千原1番地\\
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 琉球大学工学部情報工学科\\
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 email: kokubo@cr.ie.u-ryukyu.ac.jp}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 % 和文概要
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 \begin{abstract}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する手法を提唱しており、そのプロトタイプとして並列分散フレームワークAliceを開発している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 　本研究ではAliceに実用的なアプリケーションを作成するために必要な動的なトポロジーを管理する機能とAliceの制御を行えるメタ計算を追加した。また、通信時におけるData Segmentの多態性を実現するため、Data SegmentをObject型、MessagePackを使ったByteArray型、圧縮されたByteArray型の３つの形式で表現できるメタ計算の設計と実装、性能評価を行った。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 \end{abstract}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 % 英文概要　仮
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 \begin{eabstract}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 Alice is a prototype framework for distributed programming, which uses Data Segment and Code Segment as programming units. We checked Alice has an ability to write dis- tributed program using aquarium example, distributed database Jungle and share screen system AliceVNC .
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 In this paper, we add functions which control dynamic topology and Alice computation. And we show Alice has an ability to write useful application.
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 Furthermore we improve Alice performance. So Alice works 12% faster and has same performance as Federated Linda.
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 \end{eabstract}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 % 表題などの出力
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 \maketitle
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 % 本文はここから始まる
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \section{研究背景と目的}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 当研究室ではデータをData Segment、タスクをCode Segmentという単位で分割して記述する並列分散フレームワークAliceの開発を行っている。Aliceでは分散環境の構築に必要な処理をMeta Computationとして提供することで、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 Alice が分散プログラムを記述する能力を有することは確認された。だが、実用的な分散プログラムを作成するためには、ノードの切断・再接続時に対応した処理を行いたい場合や圧縮されたデータ形式で通信を行いたい場合がある。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 本研究では、 Alice の Computation の 制御を行う Meta Computation を実装した。プログラムに Alice の制御を行うメタプログラムを記述することにより切断や再接続の状況に応じた処理を元のコードを変更することなく指定することができる。また、圧縮機能を持ったDataSegmentManagerを追加することによりData Segmentの多態性を実現した。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 そして、 TreeVNC と TreeVNC を Alice を用いて実装した AliceVNC の比較をコードの観点から評価を行った。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 \section{分散フレームワーク Alice の概要}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 \subsection{Data SegmentとCode Segment}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 AliceはデータをData Segment、（以下DS）タスクをとCode Segment（以下CS）という単位に分割してプログラミングを行う。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 DSはAliceが内部にもつデータベースによって管理されている。DSに対応する一意のkeyが設定されており、そのkeyを用いてデータベースを操作する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 CSは実行に必要なDSが揃うと実行されるという性質を持ち、入力されたDSに応じた結果が出力される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 CSを実行するために必要な入力DSはInputDS、CSが計算を行った後に出力されるDSはOutput DSと呼ばれる。データの依存関係にないCSは並列実行が可能であるため、並列度を上げるためにはCSの処理内容を細かく分割して依存するデータを少なくするのが望ましい。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 \subsection{ComputationとMeta Computation}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 AliceのComputationは、keyで指し示されるDSを待ち合わせてCSを実行させると定義できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 それに対して、AliceのMeta Computationは、AliceのComputationを支えているComputationのプログラミングと定義できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 例えば、トポロジーを指定するAPIはMeta Computationである。Aliceが動作するためにはトポロジーを決める必要がある。つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。トポロジーが決定するとそのトポロジーを構成する計算が行われる。トポロジーを指定するAPIはその構成の計算をプログラミングして変更するものである。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 他にも再接続の動作を決めるAPIや切断時の動作を決めるAPIはMeta Computationである。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 これらのMeta ComputationがAliceのComputationに影響することはない。プログラマーはCSを記述する際にトポロジーや切断、再接続という状況を予め想定した処理にする必要はない。プログラマーは目的の処理だけ記述する。そして、切断や再接続が起こった場合の処理を記述しMeta Computationで指定する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 このようにプログラムすることで、通常処理と例外処理を分離することができるため、シンプルなプログラムを記述できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 \subsection{Data Segment}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 複数のスレッドから１つのデータに変更を行うためには、データの不整合を防ぐためのlockが必要になる。複数の関係のない要素を１つのデータオブジェクトで表現した場合、全ての操作でlockが必要になる。このlockがスケラビリティーを低下させる。つまりデータのサイズも並列計算には重要である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 Aliceはデータを細かく分割して記述する。その細かく分割されたデータをDSと呼ぶ。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 実際には特定のオブジェクトにマッピングされ、マッピングされたクラスを通してアクセスされる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 \subsection{Data Segment Manager}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 DSは実際にはqueueに保存される。queueには対になるkeyが存在し、keyの数だけqueueが存在する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 このkeyを指定してDSの保存、取得を行う。queueの集合体はデータベースとして捉えられる。このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。Remote DSMは他のノードのLocal DSMのproxyであり、接続しているノードの数だけ存在する。（図\ref{fig:RemoteDSM}）Remote DSMに対して書き込むと対応するノードのLocal DSMに書き込まれる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 \begin{figure}[htbp]
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 \includegraphics[width=60mm]{images/remote_datasegment.pdf}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 \caption{Remote DSMは他のノードのLocal DSMのproxy }
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 \label{fig:RemoteDSM}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 \end{figure}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 \subsection{Data Segment API}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 以下のData Segment APIを用いてデータベースにアクセスする。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 putとupdateはDSを追加する際に、peekとtakeはDSを取得する際に使用する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 \item {\ttfamily void put(String key, Object val)}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 DSをqueueに追加するためのAPIである。第一引数に対応するqueueに対してDSを追加している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 \item {\ttfamily void update(String key, Object val)}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 updateもqueueに追加するためのAPIである。putとの違いは、先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 \item {\ttfamily void take(String key)}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 \item {\ttfamily void peek(String key)}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 \section{Code Segment}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 Alice上で実行されるタスクの単位がCSである。ユーザーはCSを組み合わせることでプログラミングを行う。CSをユーザーが記述する際に、内部で使用するDSの作成を記述する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
156
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 Input DS と Output DSはCSに用意されているAPIを用いて作成する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 Input DSは、LocalかRemoteか、またkeyを指定する必要がある。CSは、記述したInput DSが全て揃うとThread poolに送られ、実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 Output DSもLocalかRemoteか、またkeyを指定する必要がある。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 \section{Code Segmentの記述方法}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \ref{src:StartCodeSegment} ,\ref{src:CodeSegment})。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 継承することによりCode Segmentで使用するAPIを利用する事ができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 \begin{table}[html]
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 \end{table}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 Alice には、Start CS (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される CS がある。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 Start CSはどのDSにも依存しない。つまりInput DSを持たない。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 ソースコード \ref{src:StartCodeSegment}は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment}）を作成している。8行目でOutput DSMを通してLocal DSMに対してDSをputしている。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 Output DSMはCSの{\tt ods}というフィールドを用いてアクセスする。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 Output DSMは{\tt put}と{\tt update}を実行することができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 \item \verb+void put(String managerKey, String key, Object val)+
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 \item \verb+void update(String managerKey, String key, Object val)+
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でupdateが行われるとTestCodeSegmentは実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 ソースコード\ref{src:CodeSegment}は、0から10までインクリメントする例題である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 2行目で取得されたDSが格納される受け皿を作る。Input DSMがもつcreateメソッド使うことで作成できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 \item {\ttfamily Receiver create(CommandType type)}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
191
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
192 引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 Input DSM はCSの{\tt ids}というフィールドを用いてアクセスする。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
194
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
196
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 TestCodeSegmentのコンストラクタが呼ばれた際には、
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 \begin{enumerate}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 \item TestCodeSegmentが持つフィールド変数Receiver input1の定義が行われる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 \item 次にCSのコンストラクタが呼ばれ、CSが持つフィールド変数の定義と初期化が行われる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 \item {\tt ids.create(CommandType.TAKE)}が行われ、input1の初期化が行われる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 \item 最後にTestCodeSegmentのコンストラクタの5行目が実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 \end{enumerate}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 5行目はInput DSMがもつsetKeyメソッドによりLocal DSMからDSを取得している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 \item \verb+void setKey(String managerKey, String key)+
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 setKeyメソッドにより、どのDSMのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
210
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 runメソッドの内容としては10行目で取得されたDSをInteger型に変換してcountに代入している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 16行目で もう一度TestCodeSegmentのCSが作られる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 17行目でcountの値をインクリメントしてLocal DSMに値を追加する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 13行目が終了条件であり、countの値が10になれば終了する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
215
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 \section{Meta Data Segment}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 DSは、アプリケーションに管理されているデータのことである。アプリケーションを構成するCSによってその値は変更される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 それに対してMeta DSは、分散フレームワークAliceが管理しているデータである。Aliceを構成するCSによってのみ、その値は変更される。一部のMeta DSはアプリケーションに利用することができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
219
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 例えば、"start"というkeyでは、ノードがStart CSを実行可能かどうかの状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote DSの一覧が管理されている。ユーザーはこの一覧にある名前を指定することで、動的にDSの伝搬などを行うことができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 また、Input DSに付随しているものもある。Input DSはCS内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでDSを入手できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 このReceiverには、fromというフィールドがあり、このDSを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、DSをputしたノードに送り返すことを防ぐことができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
224
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 Meta DSはDS同様にDS APIを用いて取得できる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
226
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 \section{Meta Code Segment}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 \input{chapter2}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 % \input{chapter3}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 % \input{chapter4}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 % \input{chapter5}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 % \input{conclusion}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 \nocite{*}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 %\nocite{opencl}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 %\nocite{opencl:ref}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 %\nocite{opencl:applied}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 %\nocite{yutaka:os}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 %\bibliographystyle{ipsjunsrt}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 %\bibliography{sigos}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
245 %\bibliography{cerium,book}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
247
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
248 \end{document}