annotate prepaper/finalPre.tex~ @ 7:677bd89014b1

add presen
author ikkun
date Wed, 15 Feb 2017 21:55:15 +0900 (2017-02-15)
parents 51a7b7a26995
children 5a6c8e4db581
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
2 \usepackage[dvipdfmx]{graphicx}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
3 \usepackage{picins}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
4 \usepackage{fancyhdr}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
5 %\pagestyle{fancy}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
6 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
7 \rhead{}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
8 \cfoot{}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
9
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
11 \setlength{\headheight}{0mm}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
12 \setlength{\headsep}{5mm}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
15 \setlength{\textwidth}{181mm}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
16 \setlength{\textheight}{261mm}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
17 \setlength{\footskip}{0mm}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
18 \pagestyle{empty}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
19
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
20 \input{dummy.tex}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
21 \begin{document}
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
22 \title{Code Gear Data Gear によるGPGPU処理実装}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
23 \author{135704C 氏名 {東恩納}{琢偉} 指導教員 : 河野 真治}
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
24 \date{}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
25 \twocolumn [
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
26 \maketitle
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
27 \begin{英語abst}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
28
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
29 \end{英語abst}]
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
30 \thispagestyle{fancy}
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
31
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
32 \section{Gears OS}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
33 Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
34 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
35 に細かく分割する。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
36 Gearで表現される計算はメタ計算により実行される。例えば、
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
37 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
38 接続する Gear を変更することでプログラムの振る舞いを変更することを可能
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
39 にする柔軟性、メタ計算による並行制御,モデル検査を用いた信頼性の確保を目的とする。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
40 本研究では現状のGears OS のマルチCPUサポートに加えてGPGPUサポートを行
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
41 う。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
42 GPGPUはCUDAまたはOpeCLで制御される。Gears OSからCide Gear Data Gearを
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
43 これらに正しく渡す必要がある。
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
44
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
45 Gears OS上のTaskはRed Black Tree上に格納される。rb\_treeはCbCで記述さ
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
46 れており、木をたどるためのStackを一つ持つ。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
47 アルゴリズム全体はCode Gearの有向グラフで表される。実際にこの有向グラ
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
48 フを作成した。これは一種のフローチャートになっている。木とStackに格納
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
49 されるのはData Gearである。この木を用いて GPGPUを実行するエンジンに
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
50 Taskを渡す。
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
51
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
52
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
53 \section{Code Gear と Data Gear}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
54 Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda} の kernel に相当する。
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
55
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
56 Code Gear は処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書き込む。また、接続された Data Gear 以外には参照を行わない。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
57 Input Data Gear と Output Data Gear の2つによって、Code Gear の Data に対す
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
58 る依存関係を解決し、 Code Gear の並列実行を可能とする。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
59 Code Gear はCbCを元に記述されており、処理の移行はfunction callではないので、呼び出し元に戻る概念はない。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
60 その代わりに、次に実行する Code Gear を軽量継続の goto で指定する。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
61 Data Gear は、int や文字列などの Primitive Data Type の組み合わせ(struct)\
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
62 である。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
63 Data Gearは様々な型を持つunionとして定義される。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
64 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
65 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
66 \lstinputlisting[label=code_Gear&Data_Gear, caption=code_Gear&Data_Gear]{sr
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
67 c/sample.c}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
68 \section{Context}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
69 ある Code Gear は次に実行する Code Gear を名前で指定する。これを継続と
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
70 いう。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
71 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
72 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
73 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
74 この Meta Data Gear を Context と呼ぶことにする。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
75 これは従来の OS の Process や Thread を表す構造体に対応する。
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
76
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
77 Context には以下のようなものが格納される。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
78 \begin{itemize}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
79 \item Code Gear の名前とポインタの対応表
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
80 \item Data Gear の Allocation 用の情報
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
81 \item Code Gear が参照する Data Gear へのポインタ
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
82 \item Data Gear に格納される Data Type の情報
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
83 \end{itemize}
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
84
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
85 \section{GPGPU}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
86 GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
87 GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
88 Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に変数が書き変わる事がない。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
89 図\ref{fig:gpgpu}では以下の流れで処理が行われる。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
90 \begin{itemize}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
91 \item Data Gear をPersistent Data Tree に挿入。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
92 \item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
93 \item 生成したTaskをTaskQueueに挿入。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
94 \item Workerの起動。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
95 \item WorkerがTskQueueからTaskを取得。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
96 \item 取得した Task を元に必要なData Gear を Persistent Data Tree から取得。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
97 \item 並列処理される Code Gear を実行。
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
98 \end{itemize}
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
99
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
100 \begin{figure}[ht]
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
101 \centering
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
102 \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
103 \caption{Gears OS による GPGPU}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
104 \label{fig:gpgpu}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
105 \end{figure}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
106 \section{今後の課題}
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
107
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
108 \begin{thebibliography}{10}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
109 \bibitem{cerium}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
110 宮國 渡,河野真治,神里 晃,杉山千秋:Cell 用の Fine-grain Task Manager
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
111 の実装,情報処理学会
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
112 システムソフトウェアとオペレーティング・システム研究会(OS) (2008).
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
113
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
114 \bibitem{alice}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
115 赤嶺一樹,河野真治:DataSegment API
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
116 を用いた分散フレームワークの設計,日本ソフトウェア科学会第28回大会論文集
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
117 (2011).
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
118
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
119 \bibitem{gears}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
120 伊波 立樹, 東恩納 琢偉,河野 真治:Code Gear、Data Gear に基づく OS のプロトタイプ、
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
121 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2016).
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
122
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
123 \bibitem{segment}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
124 河野真治,杉本 優:Code Segment と Data Segment
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
125 によるプログラミング手法,第54回プログラミング・シンポジウム (2013).
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
126
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
127 \bibitem{monad}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
128 Eugenio Moggi, Notion of Computation and Monads(1991)
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
129
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
130 \bibitem{cbc-llvm}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
131 徳森海斗,河野真治:Continuation based C の LLVM/clang 3.5
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
132 上の実装について,情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
133 (2014).
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
134
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
135 \bibitem{opencl}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
136 {Aaftab Munshi, Khronos OpenCL Working Group}: {\em {The OpenCL Specification Version 1.0}} (2007).
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
137
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
138 \bibitem{cuda}
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
139 : {CUDA}, {https://developer.nvidia.com/category/zone/cuda-zone/}.
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
140
7
677bd89014b1 add presen
ikkun
parents: 4
diff changeset
141 \end{thebibliography}
4
51a7b7a26995 add prepaper
ikkun
parents:
diff changeset
142 \end{document}