Mercurial > hg > Papers > 2013 > nobuyasu-jssst

annotate Paper/jssst.tex @ 13:f7ace466a7f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
wrote description for non destructive tree
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 18 Jul 2013 01:17:35 +0900
parents fcfd5857d435
children 906c76445554
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 % Sample file for the use of compsoft style file.
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \documentclass[T]{compsoft}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 % Preamble
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 % 巻数，号数，開始ページ，終了ページを指定する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 %\volNoPp{16}{5}{78}{83}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 % \suisen{ワークショップ名}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 % 特集の場合，特集のタイトルを与える．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 % \tokushu{特集のタイトル}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 % 大会の回数は計算される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \taikai{2013}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 % ここに，使用するパッケージを列挙する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 \usepackage[dvipdfmx]{graphicx}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
23 \usepackage{listings,jlisting}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
24 \usepackage{url}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 % 再定義は原則として避けること．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 \begin{document}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 % 論文のタイトル
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
32 \title{Data Segment の分散データベースへの応用}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 % 著者
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 % 和文論文の場合，姓と名の間には半角スペースを入れ，
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 % 複数の著者の間は全角スペースで区切る
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 \author{大城 信康 \and 河野 真治 \and 杉本 優
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 % ここにタイトル英訳 (英文の場合は和訳) を書く．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 \ejtitle{}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 % ここに著者英文表記 (英文の場合は和文表記) および
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 % 所属 (和文および英文) を書く．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 % 複数著者の所属はまとめてよい．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 \shozoku{Nobuyasu OSHIRO, Shinij KONO,Yu SUGIMOTO }{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 {Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 % 出典情報は \shutten とすれば出力される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 %\shutten
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 % 受付年月日，記事カテゴリなどは自動的に生成される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 %\uketsuke{1999}{8}{3}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 % その他，脚注に入れるものがあれば，\note に記述する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 %\note{脚注に入れる内容}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 }
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 % 和文アブストラクト
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 \Jabstract{%
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
64
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
65 Data Segment のJava上の実装としてAliceを作成してきた。
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 非破壊的木構造データベースjungleの分散実装を行う際にノード間での通信が必要になる。
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 Aliceを用いてデータベースノード間の通信を行う利点と欠点について考察する。
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 }
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 % 英文アブストラクト（大会論文には必要なし)
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 % \Eabstract{}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 \maketitle
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 \section{はじめに}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
77 当研究室では並列・分散プログラムに向いたプログラミングを目指し, データを Data Segment, タスクを Code Segment という単位で扱うプログラミングスタイルの
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
78 提案を行なっている.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
79 Data Segment, Code Segment によるプログラミングを提供する実装として, Java による分散ネットワークフレームワーク
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
80 Alice を開発している.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
81 Alice はノード間のトポロジー生成を提供しており, Data Segment としてデータの送受信をノード間で行うことができる.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
82
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
83 また, 当研究室では非破壊的木構造を用いたデータベースである Jungle の開発も行なっている.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
84 Jungle はデータを非破壊で保持することでスケーラビリティのあるデータベースを目指している.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
85 Jungle はデータの編集を TreeOperationLog という単位で行う.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
86 Alice を使いこの TreeOperationLog を各ノード間で送受信することでデータの分散を行うことができる.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
87
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
88 本研究では, Alice と Jungle を用いて分散データベースの実装を行う.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
89 さらに, 例題のアプリケーションとして掲示板を作成し, 評価を行う.
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
91 \section{分散ネットワークフレームワーク Alice}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
92 Alice は当研究室で開発している分散管理フレームワークである.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
93 Data Segment とCode Segment による並列・分散プログラミングを提供する.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
94
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
95 まず, Data Segment と Code Segment についての説明を行う.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
96
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
97 \subsection{Data Segment}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
98 Data Segment は計算に必要なデータになる.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
99 Alice は Data Segment を文字列の Key で管理する.
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
100 Key 毎にリストが用意され, put された順番で Data Segment は取り出され計算が行われる.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
101 Data Segment は Data Segment Manager(以下DSM) により管理される.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
102 DSM はノード毎にキーを持つ.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
103 他のノードの DSM にアクセスする場合は Remote DSM 経由で行う.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
104 Alice による分散プログラミングはこの Remote DSM の機能を使用する.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
105
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
106 Data Segment Manager は API を提供しており, この API を通じて Data Segment のやりとりが行われる
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
107 具体的には以下の API が用意されている.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
108 \begin{itemize}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
109 \item \verb+void put(String key, Value val)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
110 \item \verb+void update(String key, Value val)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
111 \item \verb+void peek(Receiver receiver, String key)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
112 \item \verb+void take(Receiver receiver, String key)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
113 \end{itemize}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
114
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
115 \subsubsection{put}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
116 put は Data Segment をリストへと追加する API である.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
117
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
118 \subsubsection{update}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
119 update はリストに入っている Data Segment を更新する API である.
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
120
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
122 \subsubsection{peek}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
123 peek はリストに入っている Data Segment を取り出す API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
124 peek により取り出された Data Segement はリストより削除されない.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
125
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
126 \subsubsection{take}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
127 take はリストに入っている Data Segment を取り出す API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
128 取り出した Data Segment はリストより削除される.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
129
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
130
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
131 \subsection{Code Segment}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
132 Code Segment は Data Segment を受け取り計算を行うコードのことを示す.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
133 並列プログラミングにおけるタスクにあたる.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
134 Code Segment は Data Segment は対になっている.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
135 Code Segment は計算に使う Data Segment のキーを登録して, そのキー
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
136 にあたる Data Segment が用意され次第処理が実行される.
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
137 Code Segment が処理を開始するのに必要な Data Segment を Input Data Segment という.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
138
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
139 Code Segment では Data Segment の生成を行い, put や update により新たにリストに登録することができる.
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
140 Code Segment 内で作成し登録される Data Segment は Output Data Segment と呼ばれる.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
141
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
142 Code Segment は Input Data Segment と Output Data Segment の API を提供する.
4
f3a5eb2c9081 added graffle directory
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 3
diff changeset
143
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
144
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
145 \subsection{MessagePack}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
146 Alice における Data Segment のデータ表現には MessagePack を利用している.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
147 MessagePack はバイナリをベースにしたシリアライズライブラリーである.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
148 また, MessagePack のバイナリにシリアライズできる型のみで構成された Value オブジェクト
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
149 が用意されている.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
150 Java の基本的な型はシリアライズすることができる.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
151
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
152 Value オブジェクトは自己記述なデータ形式になっている.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
153 独自のクラスでも @Message アノテーションを付けることで Value 型
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
154 へと変換することができる.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
155 その時は MessagePack がシリアライズできる型のみをフィールドに入れなければならない.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
156
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
157
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
158 \section{非破壊的木構造を用いたデータベース Jungle}
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
159 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
160 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
161 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
162
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
163 ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle の特徴について述べる.
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
164
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
165 \subsection{破壊的木構造}
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
166 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
167 図\ref{fig:destractive}は破壊的木構造の編集を表している.
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
168
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
169 \begin{figure}[htpb]
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
170 \begin{center}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
171 \includegraphics[scale=0.50]{figures/destructive_tree.pdf}
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
172 \caption{破壊的木構造の編集}
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
173 \label{fig:destractive}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
174 \end{center}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
175 \end{figure}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
176
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
177 破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
178 データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
179 いる場合は木の走査が終わるまで書き換えをまたなければならない.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
180 これではスケールしないと考えられる.
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
181
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
182 \subsection{非破壊的木構造木構造}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
183 非破壊的木構造は破壊的木構造とは違い一度作成したデータを破壊することはない.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
184 非破壊的木構造においてデータの編集を行う場合は, root から編集のあったノードまでコピー
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
185 を行い新しく作成したノードへとつなげることで行う.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
186 編集が行われない部分は参照をもたせる.
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
187 図\ref{fig:nondestractive}は非破壊的木構造の編集を表している.
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
188
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
189 \begin{figure}[htpb]
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
190 \begin{center}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
191 \includegraphics[scale=0.50]{figures/non_destructive_tree.pdf}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
192 \caption{非破壊的木構造の編集}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
193 \label{fig:nondestractive}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
194 \end{center}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
195 \end{figure}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
196
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
197 非破壊的木構造により, 木構造を編集しながら走査することが可能となる.
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
198
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
199
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
200 \subsection{Jungleの特徴}
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
201
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
202
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
203
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
204
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 \section{その３}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 \section{その４}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 \section{まとめ}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 \nocite{fix200609}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 \bibliographystyle{junsrt}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 \bibliography{reference}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 \end{document}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
216
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
217
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
218
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
219
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
220
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
221
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
222
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
223
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
224
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
225
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
226
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
227
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
228