# HG changeset patch # User e095732 # Date 1353286671 -32400 # Node ID a48e22ceed00186d311b48b1065f54726647d0be # Parent 88a77b2c92eaca713b4cfb893a8d01d132fffb93 test diff -r 88a77b2c92ea -r a48e22ceed00 Paper/sugi-prosym.tex --- a/Paper/sugi-prosym.tex Sun Nov 18 03:32:29 2012 +0900 +++ b/Paper/sugi-prosym.tex Mon Nov 19 09:57:51 2012 +0900 @@ -1,1 +1,1 @@ -\documentclass[private]{ipsjpapers} % 巻数,号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} % ユーザが定義したマクロなど. \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} %\def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Code Segment と Data Segment によるプログラミング手法]% {Code Segment と Data Segment によるプログラミング手法 } % 英文表題 \etitle{How to Programming with Code Segment and Data Segment} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{河野 真治\affiref{URYUKYU}\member{19841765}\and 杉本 優\affiref{URYUKYU}\nomember} % 英文著者名 \eauthor{Shinji Kono\affiref{URYUKYU}\and Yu Sugimoto\affiref{URYUKYU}} % 連絡先(投稿時に必要.製版用では無視される.) \contact{杉本 優\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: sugi@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} 本研究室では分散プログラミングにおいて、データをData Segment、タスクをCode Segmentという単位に分割して記述する方法を提唱している。 しかし、前述した方法をプログラマーが一から記述することは大変である。そこで、本研究室で分散ネットフレームワーク Alice を作成した。本論文では実際にAliceを用いてCode Segment と Data Segment によるプログラミング手法の例を示す。 \end{abstract} % 英文概要 \begin{eabstract} \end{eabstract} % 表題などの出力 \maketitle % }{ % 本文はここから始まる \section{歴史的経緯} 本研究室では、並列タスク管理フレームワークCeriumの管理を行なっているが、その設計と実装を行うにあたり、並列プログラミングと分散プログラミング は本質的には同じことを行なっていることが分かった。特にヘテロジーニアスマルチコアであり、ローカルストアをそれぞれのコアが持っているというCell の特異な環境は、分散プログラミング環境と告示している。それらを踏まえて、Ceriumのタスク管理手法を分散に応用できないかと考えた。 Ceriumに置いても、タスクとそれの入出力データの取り扱いは難しい課題である。データを操作するAPIを考えて、タスクを自然に記述し、効率良く実行する方法を考えてきた。そこで考えられた手法が、データをDataSegment、タスクをCodeSegmentという単位に分割して記述する方法である。 % }{ \section{分散ネットフレームワークAlice}\label{sec:ITEM} \subsection{Aliceとは} Aliceは本研究室の卒業生である赤嶺一樹氏が、本研究室で開発を行なっている並列タスク管理フレームワーク Cerium と先行研究である Federated Linda の開発を通して得られた知見を生かされている。 Federated Linda の設計はシングルスレッドで行われている。しかし、近年ではマルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になってくると考えられるそのような背景を踏まえてAliceはマルチスレッド向けに設計されている。 AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。 % }{ \subsection{Data Segment} AliceではData Semgnetをデータベースとして利用している。KeyValueStoreで実装されており、キーごとにリストを持っている。Data Segment APIを用いることで、リストにデータを追加、削除を適宜行うことができる。 \subsubsection{Data Segment Manager} 大量のData Segmentを管理するのがData Segment Managerである。Data Segment Managerは文字列のキーでData Segmentを整理する。各キーごとにキュー構造を持っている。それらをData Segment APIを用いて操作する。 データの読み出し("peek" または "take")時に、希望のデータがなかった場合、ブロッキングを行う機能を持つ。 しかし、ブロッキングといってもそこで同期するわけではない。 非同期でデータを通信する。 そのため、 "peek" と "take" は他の API とは違い、レスポンスが発生する。 \subsubsection{Data Segment API} 表番号)が用意されているData Segment APIである。これらを用いてデータの送受信を行う。 \begin{itemize} \item {\ttfamily void put(String key, Value val)} \item {\ttfamily void update(String key, Value val)} \item {\ttfamily void peek(Receiver receiver, String key, int id)} \item {\ttfamily void take(Receiver receiver, String key, int id)} \end{itemize} \subsubsection*{"put"} "put" はデータを追加するための API である。 "put" は受け取ったデータ val を Data Segment 内のキューに対してエンキューする。 この時、キーごとに重複しない連番の ID を受け取った順に振る。 %(図 \ref{fig:put}) \subsubsection*{"update"} "update" はデータを置き換えるための API である。 "update" はキューの先頭にあるデータをひとつだけ削除する。 その後は "put" と同じく、 受け取ったデータ val を Data Segment 内のキューに対してエンキューする。 この時、キーごとに重複しない連番の ID を受け取った順に振る。 %(図 \ref{fig:update}) \subsubsection*{"peek"} "peek" はデータを読み込むための API である。 "peek" は前回読み込んだデータの id を引数で指定する。省略した場合は、 0 が id として渡される。 id よりも値の大きい id のデータがキューに含まれていれば、そのデータを receiver に返す。 もし id 以下のデータしか無いならば、データの更新が前回の "peek" 発行時から更新が無いものと考え、リストに格納されて保留される。 %(図 \ref{fig:peek}) "take" や "update" によりデータの更新があれば、 "peek" が直ちに実行される。 \subsubsection*{"take"} "take" もデータを読み込むための API である。 基本的な id に関する部分は "peek" と同じである。 "peek" との決定的な違いは、読み込まれたデータは Data Segment 内のキューから取り除かれるということである。 %(図 \ref{fig:take}) \subsection{Code Segment} Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segment 内で使用するData Segment を記述し、依存関係を作る。依存関係により、実行される順番が一意に決まる。実際に使用するData Segment はCode Segmentの入出力に相当する。それぞれ、Input Data Segment、Output Data Segmentとする。 \subsubsection{Code Segmentの実行方法} Code Semgnetを実行するためにはStart Code SegmentというCode Segmentを実行させる必要がある。 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 \subsubsection{Code Segmentの記述方法} Code Segmentをユーザーが記述する際にはCodeSegmentを継承して記述する。そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。 \subsubsection*{InputDataSegmentManager} InputDataSegmentManagerはCode Segmentのidsというフィールドを用いてアクセスする。 \begin{itemize} \item {\ttfamily Receiver create(CommandType type)} \end{itemize} createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeはPEEKまたはTAKEである。 \begin{itemize} \item {\ttfamily void setKey(String managerKey, String key, int id)} \end{itemize} setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。 \subsubsection*{OutputDataSegmentManager} OutputDataSegmentManagerはCode Segmentのodsというフィールドを用いてアクセスする。 OutPutDataSegmentManagerは"put"または"update"を実行することができる。 \begin{itemize} \item {\ttfamily void put(String managerKey, String key, \\ Value val)} \item {\ttfamily void update(String managerKey, String key, Value val)} \end{itemize} \subsection{Topology Manager} TopologyManagerはAlice同士の接続トポロジーを管理する。TopologyManager関連の通信処理はCode Segmentで実装してある。 TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送り、トポロジーファイルに記述された通りにトポロジーを作成する。 \subsection{Topology Managerの設定ファイル} Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Languageという言語で記述される。 DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。 クライアント間の接続にはlabelを用いて名前が割り振られており、この接続名を用いてユーザーはData Segment Managerにアクセスすることができる。 前述したReceiver にsetKeyを行う際、odsでputまたはupdateする際の引数のmanagerKeyがこれにあたる。 \subsection{Topology Managerの使用方法} Topology Nodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定をする。 そしてmain関数内でTopologyNodeをnewを行えば良い。 TopologyNodeの第一引数は Alice デーモンの設定オブジェクト、第二引数はStart Code Segmentである。 ここで指定した、Start Code Segmentがトポロジーが完成した後実行される。 % }{ \section{ゲームの例題}\label{sec:Enum}\label{sec:item} \subsection{水族館} 今回作成した例題は水族館である。複数のクライアントのディスプレイを複数の魚が移動していくものである。魚は画面の端まで移動すると自分の画面上からは消え、別のクライアントの画面の端から魚が出てくる。また、魚のうち一匹はクライアントが直接操作することができる。トポロジーはTopologyManagerによりツリー状に構成してある。 \subsection{データの伝搬} \begin{enumerate} \item ユーザーが魚を操作するまたはCode Segmentにより魚の座標が更新される。 \item 画面に表示させるためのSetLocation (Code Segment)が実行され実際に魚のオブジェクトにセットされ画面に反映される。 \item Update(Code Segment)にFishPosition(魚の座標データ)が渡される。 \item Updateにlist(送信者リスト)が渡される。 \item Updateが実行され、listを元にデータが送信される。ただし、この時にFishPositionには送信元情報が付加されているので、送信元には送信されない。 \item 各clientで2 - 4が実行される。 \end{enumerate} \section{評価} \section{まとめと今後の課題} \end{document} \ No newline at end of file +\documentclass[private]{ipsjpapers} \usepackage{listings} % 巻数,号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} % ユーザが定義したマクロなど. \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} %\def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Code Segment と Data Segment によるプログラミング手法]% {Code Segment と Data Segment によるプログラミング手法 } % 英文表題 \etitle{How to Programming with Code Segment and Data Segment} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{河野 真治\affiref{URYUKYU}\member{19841765}\and 杉本 優\affiref{URYUKYU}\nomember} % 英文著者名 \eauthor{Shinji Kono\affiref{URYUKYU}\and Yu Sugimoto\affiref{URYUKYU}} % 連絡先(投稿時に必要.製版用では無視される.) \contact{杉本 優\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: sugi@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} 本研究室では分散プログラミングにおいて、データをData Segment、タスクをCode Segmentという単位に分割して記述する方法を提唱している。 しかし、前述した方法をプログラマーが一から記述することは大変である。そこで、本研究室で分散ネットフレームワーク Alice を作成した。本論文では実際にAliceを用いてCode Segment と Data Segment によるプログラミング手法の例を示す。 \end{abstract} % 英文概要 \begin{eabstract} \end{eabstract} % 表題などの出力 \maketitle % }{ % 本文はここから始まる \section{歴史的経緯} 本研究室では、並列タスク管理フレームワークCeriumの管理を行なっているが、その設計と実装を行うにあたり、並列プログラミングと分散プログラミング は本質的には同じことを行なっていることが分かった。特にヘテロジーニアスマルチコアであり、ローカルストアをそれぞれのコアが持っているというCell の特異な環境は、分散プログラミング環境と告示している。それらを踏まえて、Ceriumのタスク管理手法を分散に応用できないかと考えた。 Ceriumに置いても、タスクとそれの入出力データの取り扱いは難しい課題である。データを操作するAPIを考えて、タスクを自然に記述し、効率良く実行する方法を考えてきた。そこで考えられた手法が、データをDataSegment、タスクをCodeSegmentという単位に分割して記述する方法である。 % }{ \section{分散ネットフレームワークAlice}\label{sec:ITEM} \subsection{Aliceとは} Aliceは本研究室の卒業生である赤嶺一樹氏が、本研究室で開発を行なっている並列タスク管理フレームワーク Cerium と先行研究である Federated Linda の開発を通して得られた知見を生かされている。 Federated Linda の設計はシングルスレッドで行われている。しかし、近年ではマルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になってくると考えられるそのような背景を踏まえてAliceはマルチスレッド向けに設計されている。 AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。また、他のマシンとの接続トポロジーの構成の機能も有しているのでユーザーはトポロジー構成後の処理を記述するだけでよい。 % }{ \subsection{Data Segment} AliceではData Semgnetをデータベースとして利用している。KeyValueStoreで実装されており、キーごとにリストを持っている。Data Segment APIを用いることで、リストにデータを追加、削除を適宜行うことができる。 \subsubsection{Data Segment Manager} 大量のData Segmentを管理するのがData Segment Managerである。Data Segment Managerは文字列のキーでData Segmentを整理する。各キーごとにキュー構造を持っている。それらをData Segment APIを用いて操作する。 データの読み出し("peek" または "take")時に、希望のデータがなかった場合、ブロッキングを行う機能を持つ。 しかし、ブロッキングといってもそこで同期するわけではない。 非同期でデータを通信する。 そのため、 "peek" と "take" は他の API とは違い、レスポンスが発生する。 \subsubsection{Data Segment API} 表番号)が用意されているData Segment APIである。これらを用いてデータの送受信を行う。 \begin{itemize} \item {\ttfamily void put(String key, Value val)} \item {\ttfamily void update(String key, Value val)} \item {\ttfamily void peek(Receiver receiver, String key, int id)} \item {\ttfamily void take(Receiver receiver, String key, int id)} \end{itemize} \subsubsection*{"put"} "put" はデータを追加するための API である。 "put" は受け取ったデータ val を Data Segment 内のキューに対してエンキューする。 この時、キーごとに重複しない連番の ID を受け取った順に振る。 %(図 \ref{fig:put}) \subsubsection*{"update"} "update" はデータを置き換えるための API である。 "update" はキューの先頭にあるデータをひとつだけ削除する。 その後は "put" と同じく、 受け取ったデータ val を Data Segment 内のキューに対してエンキューする。 この時、キーごとに重複しない連番の ID を受け取った順に振る。 %(図 \ref{fig:update}) \subsubsection*{"peek"} "peek" はデータを読み込むための API である。 "peek" は前回読み込んだデータの id を引数で指定する。省略した場合は、 0 が id として渡される。 id よりも値の大きい id のデータがキューに含まれていれば、そのデータを receiver に返す。 もし id 以下のデータしか無いならば、データの更新が前回の "peek" 発行時から更新が無いものと考え、リストに格納されて保留される。 %(図 \ref{fig:peek}) "take" や "update" によりデータの更新があれば、 "peek" が直ちに実行される。 \subsubsection*{"take"} "take" もデータを読み込むための API である。 基本的な id に関する部分は "peek" と同じである。 "peek" との決定的な違いは、読み込まれたデータは Data Segment 内のキューから取り除かれるということである。 %(図 \ref{fig:take}) %after \lstset{ language={java}, basicstyle={\small}, identifierstyle={\small}, commentstyle={\small\itshape}, keywordstyle={\small\bfseries}, ndkeywordstyle={\small}, stringstyle={\small\ttfamily}, frame={tb}, breaklines=true, columns=[l]{fullflexible}, numbers=left, xrightmargin=0zw, xleftmargin=3zw, numberstyle={\scriptsize}, stepnumber=1, numbersep=1zw, lineskip=-0.5ex } \subsection{Code Segment} Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segment 内で使用するData Segment を記述し、依存関係を作る。依存関係により、実行される順番が一意に決まる。実際に使用するData Segment はCode Segmentの入出力に相当する。それぞれ、Input Data Segment、Output Data Segmentとする。 \subsubsection{Code Segmentの実行方法} Code Semgnetを実行するためにはStart Code SegmentというCode Segmentを実行させる必要がある。 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 \begin{table}[tb] \lstinputlisting[label=StartCodeSegment, caption=StartCodeSegment]{source/StartCodeSegment.java} \end{table} \subsubsection{Code Segmentの記述方法} Code Segmentをユーザーが記述する際にはCodeSegmentを継承して記述する。そのCodeSegmentはInputDataSegmentManagerとOutputDataSegmentManagerを利用することができる。 \subsubsection*{InputDataSegmentManager} InputDataSegmentManagerはCode Segmentのidsというフィールドを用いてアクセスする。 \begin{itemize} \item {\ttfamily Receiver create(CommandType type)} \end{itemize} createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeはPEEKまたはTAKEである。 \begin{itemize} \item {\ttfamily void setKey(String managerKey, String key, int id)} \end{itemize} setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。 \subsubsection*{OutputDataSegmentManager} OutputDataSegmentManagerはCode Segmentのodsというフィールドを用いてアクセスする。 OutPutDataSegmentManagerは"put"または"update"を実行することができる。 \begin{itemize} \item {\ttfamily void put(String managerKey, String key, \\ Value val)} \item {\ttfamily void update(String managerKey, String key, Value val)} \end{itemize} \subsection{Topology Manager} TopologyManagerはAlice同士の接続トポロジーを管理する。TopologyManager関連の通信処理はCode Segmentで実装してある。 TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送り、トポロジーファイルに記述された通りにトポロジーを作成する。 \subsection{Topology Managerの設定ファイル} Topology Managerはトポロジーファイルを読み込むが、トポロジーファイル自体はDOT Languageという言語で記述される。 DOT Languageとはプレーンテキストを用いて、データ構造としてのグラフを表現するための、データ記述言語の一種である。このDOT Languageのグラフを利用して、クライアント間の接続を表現する。DOT Languageファイルはdotコマンドを用いて、グラフの画像ファイルを出力することができるので、記述したトポロジーが正しいことを可視化して確認することができる。 クライアント間の接続にはlabelを用いて名前が割り振られており、この接続名を用いてユーザーはData Segment Managerにアクセスすることができる。 前述したReceiver にsetKeyを行う際、odsでputまたはupdateする際の引数のmanagerKeyがこれにあたる。 \subsection{Topology Managerの使用方法} Topology Nodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定をする。 そしてmain関数内でTopologyNodeをnewを行えば良い。 TopologyNodeの第一引数は Alice デーモンの設定オブジェクト、第二引数はStart Code Segmentである。 ここで指定した、Start Code Segmentがトポロジーが完成した後実行される。 % }{ \section{ゲームの例題}\label{sec:Enum}\label{sec:item} \subsection{水族館} 今回作成した例題は水族館である。複数のクライアントのディスプレイを複数の魚が移動していくものである。魚は画面の端まで移動すると自分の画面上からは消え、別のクライアントの画面の端から魚が出てくる。また、魚のうち一匹はクライアントが直接操作することができる。トポロジーはTopologyManagerによりツリー状に構成してある。 \subsection{データの伝搬} \begin{enumerate} \item ユーザーが魚を操作するまたはCode Segmentにより魚の座標が更新される。 \item 画面に表示させるためのSetLocation (Code Segment)が実行され実際に魚のオブジェクトにセットされ画面に反映される。 \item Update(Code Segment)にFishPosition(魚の座標データ)が渡される。 \item Updateにlist(送信者リスト)が渡される。 \item Updateが実行され、listを元にデータが送信される。ただし、この時にFishPositionには送信元情報が付加されているので、送信元には送信されない。 \item 各clientで2 - 4が実行される。 \end{enumerate} \section{評価} \section{まとめと今後の課題} \end{document} \ No newline at end of file