Mercurial > hg > Papers > 2015 > kkb-sigos

changeset 10:92f7c78d8d6c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
edit
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Wed, 06 May 2015 19:55:44 +0900
parents 12a7b1cb59fe
children 37c481e6d758
files paper/jlisting.sty paper/sigos.bib paper/sigos.pdf paper/sigos.tex paper/source/allocate-ideal.c paper/source/allocate.h
diffstat 6 files changed, 324 insertions(+), 32 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/jlisting.sty	Wed May 06 19:55:44 2015 +0900
@@ -0,0 +1,216 @@
+\NeedsTeXFormat{LaTeX2e}
+\def\filedate{2006/02/20}
+\def\fileversion{0.2}
+\ProvidesPackage{jlisting}[\filedate\space\fileversion\space(Thor)]
+%
+\newcount\lst@nextchar
+\let\lst@@ProcessSpace\lst@ProcessSpace
+\def\lst@ProcessSpace#1{%
+   \lst@check@chartype{#1}%
+      \lst@@ProcessSpace
+      \lst@whitespacetrue}
+\let\lst@@ProcessLetter\lst@ProcessLetter
+\def\lst@ProcessLetter#1#2{%
+   \lst@check@chartype{#2}%
+      {\lst@@ProcessLetter{#1}}%
+      \relax}
+\let\lst@@ProcessDigit\lst@ProcessDigit
+\def\lst@ProcessDigit#1#2{%
+   \lst@check@chartype{#2}%
+      {\lst@@ProcessDigit{#1}}%
+      \relax}
+\let\lst@@ProcessOther\lst@ProcessOther
+\def\lst@ProcessOther#1#2{%
+   \lst@check@chartype{#2}%
+      {\lst@@ProcessOther{#1}}%
+      \relax}
+\let\lst@@ProcessTabulator\lst@ProcessTabulator
+\def\lst@ProcessTabulator#1{%
+   \lst@check@chartype{#1}%
+      \lst@@ProcessTabulator
+      \relax}
+\def\lst@check@chartype#1#2#3{%
+   \edef\@tempa{\lst@nextchar=`\string#1\relax}%
+   \afterassignment\remove@to@nnil
+   \@tempa\@nnil
+   #2%
+   \ifnum\lst@nextchar<\@cclvi
+      #3%
+   \else
+      \lst@ifletter \else \lst@OutputOther \fi
+      \lst@whitespacefalse
+      \expandafter\lst@AppendJchar
+   \fi
+   #1}
+\def\lst@AppendJchar#1#2{%
+   \lst@check@chartype{#2}%
+      {\advance\lst@length\@ne\lst@Append{#1}}%
+      \relax}
+\def\lst@check@chartype@BOL#1{%
+   \edef\@tempa{\lst@nextchar=`\string#1\relax}%
+   \afterassignment\remove@to@nnil
+   \@tempa\@nnil
+   \ifnum\lst@nextchar<\@cclvi\else
+      \lst@whitespacefalse
+      \expandafter\lst@AppendJchar
+   \fi
+   #1}
+\def\lst@InputListing#1{%
+   \begingroup
+      \lsthk@PreSet \gdef\lst@intname{#1}%
+      \expandafter\lstset\expandafter{\lst@set}%
+      \lsthk@DisplayStyle
+      \catcode\active=\active
+      \lst@Init\relax \let\lst@gobble\z@
+      \lst@SkipToFirst
+      \lst@ifprint \def\lst@next{\lst@get@filecontents{#1}}%
+      \else        \let\lst@next\@empty
+      \fi
+      \lst@next
+      \lst@DeInit
+   \endgroup}
+\newread\lst@inputfile
+\def\lst@get@filecontents#1{%
+   \let\lst@filecontents\@empty
+   \openin\lst@inputfile=#1\relax
+   \let\@lst@get@filecontents@prevline\relax
+   \lst@get@filecontents@loop
+   \closein\lst@inputfile
+   \lst@filecontents\empty}
+\def\lst@get@filecontents@loop{%
+   \read\lst@inputfile to\@lst@get@filecontents@currline
+   \ifx\@lst@get@filecontents@prevline\relax\else
+      \expandafter\expandafter\expandafter\def
+      \expandafter\expandafter\expandafter\lst@filecontents
+      \expandafter\expandafter\expandafter{%
+         \expandafter\lst@filecontents\@lst@get@filecontents@prevline}%
+   \fi
+   \let\@lst@get@filecontents@prevline\@lst@get@filecontents@currline
+   \ifeof\lst@inputfile\else
+      \expandafter\lst@get@filecontents@loop
+   \fi}
+%%% [$B$3$N=hM}$b!$AjEv6/0z$G$9!%(B]
+\def\lst@BOLGobble{%
+   \ifnum\lst@gobble>\z@
+      \@tempcnta\lst@gobble\relax
+      \expandafter\lst@BOLGobble@
+   \else
+      \expandafter\lst@check@chartype@BOL
+   \fi}
+\def\lst@BOLGobble@#1{%
+   \let\lst@next#1%
+   \ifx \lst@next\relax\else
+   \ifx \lst@next\lst@MProcessListing\else
+   \ifx \lst@next\lst@ProcessFormFeed\else
+   \ifx \lst@next\lstenv@backslash
+      \let\lst@next\lstenv@BOLGobble@@
+   \else
+      \let\lst@next\lst@BOLGobble@@
+      \ifx #1\lst@ProcessTabulator
+         \advance\@tempcnta-\lst@tabsize\relax
+         \ifnum\@tempcnta<\z@
+            \lst@length-\@tempcnta \lst@PreGotoTabStop
+         \fi
+      \else
+         \edef\@tempa{\lst@nextchar=`\string#1\relax}%
+         \@tempa
+         \ifnum\lst@nextchar<\@cclvi\else
+            \advance\@tempcnta\m@ne
+         \fi
+         \advance\@tempcnta\m@ne
+      \fi
+   \fi \fi \fi \fi
+   \lst@next}
+\def\lst@BOLGobble@@{%
+   \ifnum\@tempcnta>\z@
+      \expandafter\lst@BOLGobble@
+   \else
+      \expandafter\lst@check@chartype@BOL
+   \fi
+}
+%
+%    \begin{$B=$@5;v9`(B}{1.3}
+% $B$A$g$C$H$7$?=$@5(B
+\gdef\lst@breakProcessOther#1{\lst@ProcessOther#1}
+% $B%=!<%9%3!<%IL\<!$K$*$1$kJ8;z$HHV9f$N6u$-(B
+\let \l@lstlisting = \l@figure
+% $B%-%c%W%7%g%s$H%=!<%9%3!<%IL\<!$KBP$9$kF|K\8lBP1~(B
+\def\lstlistingname{$B%=!<%9%3!<%I(B}
+\def\lstlistlistingname{$B%=!<%9%3!<%IL\<!(B}
+%    \end{$B=$@5;v9`(B}
+\endinput
+% 
+%#!platex
+\documentclass[papersize]{jsarticle}
+% Macros
+\IfFileExists{dvipdfmx.def}{%
+  \usepackage[dvipdfmx]{color,graphicx}%
+}{%
+  \usepackage[dvipdfm]{color,graphicx}%
+}
+\usepackage{listings}[2004/09/07]
+\usepackage{jlisting}[2006/02/20]
+\usepackage{url} 
+\usepackage{verbatim}
+
+\makeatletter
+% Original Macros
+\def\email#1{\gdef\@email{\texttt{#1}}}
+\def\homepage#1{\gdef\@homepage{\texttt{#1}}}
+\def\mac#1{\textsf{#1}}
+\def\URL#1{\texttt{#1}}
+\def\src#1{\texttt{#1}}
+
+% Dvipdfmx.def 
+\def\dvipdfmxDefi{http://tex.dante.jp/ok/dvipdfmx/}
+\def\dvipdfmxDefii{http://ftp.ktug.or.kr/KTUG/dvipdfmx/contrib/latex/}
+
+\IfFileExists{dvipdfmx.def}{%
+   \let \IfDvipdfmxDef = \empty \relax}{%
+   \typeout{^^Jget dvipdfmx.def at \dvipdfmxDefi^^J
+            or \dvipdfmxDefii^^J}%
+   \def\IfDvipdfmxDef{Get \src{dvipdfmx.def} at \URL \dvipdfmxDefii \\ 
+      or \URL \dvipdfmxDefi.}%
+}
+
+% Author Info
+\author   {Th\'or Watanabe\thanks \@email \space \thanks \@homepage}
+\title    {\mac{jlisting.sty}\\
+          ---Japanese Localized Patch File of \mac{listings}---}
+\email    {thor@tex.dante.jp}
+\homepage {http://tex.dante.jp/typo/}
+\date     {2006/02/20}
+
+\makeatother
+
+\begin{document}
+\maketitle
+%\IfDvipdfmxDef
+
+\section{$B$A$g$C$H$7$?@bL@(B}% Short Description
+ 
+$B1|B<@2I';a$N7G<(HD$N!VHFMQE*$JIbF0BN!W$H$$$&0lO"$N=q$-9~$_$+$i(B
+$BE>:\$7$^$7$?!#(B
+
+\begin{quote}
+ \url{http://http://cise.edu.mie-u.ac.jp/~okumura/texfaq/qa/21172.html}\\
+ \url{http://http://cise.edu.mie-u.ac.jp/~okumura/texfaq/qa/21184.html}\\
+ \url{http://http://cise.edu.mie-u.ac.jp/~okumura/texfaq/qa/21189.html}\\
+ \url{http://http://cise.edu.mie-u.ac.jp/~okumura/texfaq/qa/21197.html}
+\end{quote}
+
+ Copyright $B$O5H1JE/H~;a$K$"$k$N$@$H;W$$$^$9!%(B
+ 
+\section{$B99?7MzNr(B}% ChageLogs
+
+\begin{description}
+ \item[ver.~0.1 (2004/03/24)]
+   $B$H$j$"$($:8x3+!%(B
+ \item[ver.~0.2 (2006/02/20)] 
+   \verb|\lst@breakProcessOther| $BL?Na$NDj5A$NDI2C!%(B
+\end{description}
+
+\section{$B%=!<%9%3!<%I(B}
+\par\narrowbaselines
+\verbatiminput{jlisting.sty}
+\end{document}
--- a/paper/sigos.bib	Wed May 06 02:52:05 2015 +0900
+++ b/paper/sigos.bib	Wed May 06 19:55:44 2015 +0900
@@ -23,6 +23,15 @@
 }
 
 @article{
+    segment,
+    author = "河野 真治 and 杉本 優",
+    title = "Code Segment と Data Segment によるプログラミング手法",
+    journal = "第54回プログラミング・シンポジウム",
+    month = "Jan",
+    year = 2013
+}
+
+@article{
     cbc,
     author = "河野 真治 and 島袋 仁",
     title = "C with Continuation と、そのPlayStationへの応用",
@@ -39,6 +48,7 @@
     month = "May",
     year = 2014
 }
+                  
 @article{
     monad,
     author = "Eugenio Moggi",
@@ -47,6 +57,15 @@
     year = 1989
 }
                   
+@article{
+    model-check,
+    author = "下地 篤樹 and 河野 真治",
+    title = "線形時相論理によるContinuation based Cプログラムの検証",
+    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "April",
+    year = 2007
+}
+
 @manual{opencl,
 author = "{Aaftab Munshi, Khronos OpenCL Working Group}",
 title ="{The OpenCL Specification Version 1.0}",
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Wed May 06 02:52:05 2015 +0900
+++ b/paper/sigos.tex	Wed May 06 19:55:44 2015 +0900
@@ -1,14 +1,14 @@
 \documentclass[techrep]{ipsjpapers}
 \usepackage[dvipdfm]{graphicx}
 \usepackage{url}
-\usepackage{listings}
+\usepackage{listings,jlisting}
 \usepackage{enumitem}
 
 \lstset{
   language=C,
   tabsize=2,
   frame=single,
-  basicstyle={\footnotesize},%
+  basicstyle={\ttfamily\footnotesize},%
   identifierstyle={\footnotesize},%
   commentstyle={\footnotesize\itshape},%
   keywordstyle={\footnotesize\bfseries},%
@@ -26,7 +26,6 @@
   lineskip=-0.5ex%
 }
 
-\renewcommand{\lstlistingname}{Code}
 \input{dummy.tex} %% Font 
 
 % ユーザが定義したマクロなど．
@@ -71,21 +70,23 @@
 % 和文概要
 \begin{abstract}
   本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
-  並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。
-  今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と  Meta Data Gear を付属させる。
-  Code Gear が実行されるとそれに属する Meta Code Gear が実行され、Meta Computation が行われる。
+  Code Gear, Data Gear は処理とデータの単位である。
+  並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現する。
+  今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と  Meta Data Gear を対応させる。
+  Code Gear が実行されるとそれに対応する Meta Code Gear が実行され、Meta Computation が行われる。
   Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
-  本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
+  本論文では基本的な機能を設計し、CbC(Continuation based C) で実装する。
 \end{abstract}
 
 % 英文概要
 \begin{eabstract}
-  We are developing parallel framework using Code Gear, Data Gear.
-  We obtain meta function for parallel execution, based on Monad in Functional Language.
-  Meta Code Gear and Meta Data Gear attached to Code Gear and Data Gear with designed Gears OS.
-  Meta Code Gear is executed after Code Gear, this is Meta Computation.
+  We are developing parallel framework using a Code/Data Gear.
+  Code/Data Gear are unit of processing and data.
+  We obtains meta function for parallel execution, based on a Monad in Functional Language.
+  Meta Code/Data Gear attached to Code/Data Gear with designed a Gears OS.
+  Meta Code Gear is executed after a Code Gear, which perform a Meta Computation.
   Meta Computation performs Network Management, Memory Management and more.
-  We implement basic functions using CbC and evaluate it.
+  We designs basic functions and evaluate it using CbC.
 \end{eabstract}
 
 % 表題などの出力
@@ -95,41 +96,52 @@
 
 % Introduce
 \section{Cerium と Alice}
-本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なっている。
+本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なっていた。
+
+Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
 
 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
 依存関係はプログラマ自身が意識して記述する必要がある。
 Task の種類が増えると記述が煩雑になり、プログラマの負担が大きくなる。
-依存関係の記述がデータの依存関係と無関係という問題もある。
-また、Task の取り扱うデータには型情報がなく、Task とデータも分離されていない。
-Cerium は C++ で実装されている。
+Task の依存関係がデータの依存関係を正しく保証しない場合があるという問題がある。
+また、Task の取り扱うデータには型情報がない。
+汎用ポインタをキャストして利用するしかなく、型の検査が行われていない。
+Cerium は C++ で実装されているが、オブジェクトと並列処理が直接対応していないのでオブジェクト指向で記述する利点が少ない。
 Cell\cite{cell}, Many Core CPU, GPU といった様々なプロセッサをサポートしている。
-高速で動作するが、非常に複雑な実装となっており機能の追加やデバッグが難しい現状である。
+しかし、それぞれの環境でプログラムを高速に動作させるためにはそれぞれに合わせた実行機構を必要としている。
 
 Alice は本研究室で開発を行なっている分散管理フレームワークである。
-Alice では処理の単位である Code Segment, データの単位である Data Segment を用いてプログラムを記述する。
+Alice では処理の単位である Code Segment, データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
 Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。
-Alice は Java で実装されている。
-ガベージコレクション(GC)が実行されると性能が低下するといった問題がある。
+Alice は Java で実装されており、実行速度が遅いという問題がある。
 また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。
 
-Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
+\section{Gears OS}
+Cerium と Alice から得られた知見から並列実行には Code の単位だけでなく、Data の単位も必要であることがわかった。
+Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
+Code Gear は Input Data Gear から Output Data Gear を生成する。
+Input と Output の関係から Code Gear 同士の依存関係を解決し、並列実行するフレームワークの開発を行う。
+Code Gear はそれに接続された Data Gear のみを扱う。
+Code/Data Gear 同士の関係は Meta Code/Data Gear によって表現される。
+この Meta Code/Data Gear を用いることで機能やデータ自体を拡張することができる。
 
-\section{Gears OS}
-Cerium と Alice から並列実行には Code の並列実行だけでなく、Data の単位が重要であることが明らかとなった。
-本研究では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割し、Code と Data の関係から Code Gear 同士の依存関係を解決して並列実行するフレームワーク Gears OS の開発を行なっている。
-Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能となるように設計する。
 Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。
 Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。
+
 Gears OS は本研究室で開発している CbC(Continuation based C)\cite{cbc} で実装する。
-CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる
+CbC はプログラムを Code Segment, Data Segment という単位で記述する。
+CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。
+CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる。
 
 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
-Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。
+関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
+Gears OS では、Meta Code/Data Gear を Monad として定義し、Meta Computation を実現する。
 
-Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。
-Model Chaecking によって、並列実行時のデッドロックの検出などを行う。
-これにより、プログラムの信頼性を保証する。
+Gears OS では並列実行をサポートするだけでなく、信頼性も確保する。
+そのために Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能\cite{model-check}を提供する。
+並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。
+これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
+Model Checking も Meta Code/Data Gear を用いて実現する。
 
 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
@@ -261,7 +273,12 @@
 Context には Allocation 用の Data Gear が格納されている。
 この Data Gear に確保するサイズと確保後に接続する Code Gear の名前を書き込み、Allocation を行う Code Gear に接続することで必要な領域を確保する。
 
-\lstinputlisting[caption=Allocator]{source/allocate.h}
+\lstinputlisting[label=allocate, caption=Allocator]{source/allocate.h}
+
+ソースコード\ref{allocate}では Code Gear である code1 でポインタを扱っており、Code Gear でポインタを扱わないという設計思想に合っていない。
+そこで、ソースコード\ref{allocate-ideal}をソースコード\ref{allocate}として解釈するようにコンパイラを改良する。
+
+\lstinputlisting[label=allocate-ideal, caption=SyntaxSugar]{source/allocate-ideal.c}
 
 % List
 \section{List}
@@ -275,6 +292,10 @@
   \label{fig:list}
 \end{figure}
 
+\section{Synchronized Queue}
+Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。
+Synchronized Queue があれば並行制御を行うことが可能となり、Gears OS は Cerium と同等の機能を持つことになる。
+
 \section{比較}
 Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。
 
@@ -285,6 +306,9 @@
 これは Alice の Data Segment と同等のものである。
 Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。
 
+Alice は Data Segment を MessagePack を利用して通信することで分散実行を実現する。
+Gears OS 上での分散実行も Alice に沿って設計・実装する。
+
 \paragraph*{OpenCL/CUDA}
 Code Gear は OpenCL/CUDA の kernel に相当する。
 OpenCL/CUDA には Data Gear に相当する仕組みはない。
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/source/allocate-ideal.c	Wed May 06 19:55:44 2015 +0900
@@ -0,0 +1,24 @@
+// Code Gear
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate); // goes through meta
+}
+
+// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Meta Code Gear
+__code allocate(struct Context* context) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap += context->data[Allocate]->allocate.size;
+    goto (context->code[context->data[Allocate]->allocate.next])(context);
+}
+
+// Code Gear
+__code code2(Allocate allocate, Count count) {
+    // processing
+}
--- a/paper/source/allocate.h	Wed May 06 02:52:05 2015 +0900
+++ b/paper/source/allocate.h	Wed May 06 19:55:44 2015 +0900
@@ -1,15 +1,24 @@
+// Code Gear
 __code code1(struct Context* context) {
     context->data[Allocate]->allocate.size = sizeof(struct Node);
     context->data[Allocate]->allocate.next = Code2;
-    goto Allocate(context);
+    goto meta(context, Allocate);
 }
 
+// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Meta Code Gear
 __code allocate(struct Context* context) {
     context->data[++context->dataNum] = context->heap;
     context->heap += context->data[Allocate]->allocate.size;
     goto (context->code[context->data[Allocate]->allocate.next])(context);
 }
 
+// Code Gear
 __code code2(struct Context* context) {
     // processing content
 }