Mercurial > hg > Papers > 2015 > parusu-midterm
changeset 10:780adbc2d5ec
Fix List section
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 29 Oct 2015 15:17:04 +0900 |
parents | cc60f8c3b875 |
children | b523dcaafce6 |
files | midterm.pdf midterm.tex |
diffstat | 2 files changed, 20 insertions(+), 20 deletions(-) [+] |
line wrap: on
line diff
--- a/midterm.tex Wed Oct 28 18:45:49 2015 +0900 +++ b/midterm.tex Thu Oct 29 15:17:04 2015 +0900 @@ -30,8 +30,6 @@ Cerium と Alice を開発して得られた知見から、並列実行をサポートするだけでなく、信頼性も確保したGears OS の設計・開発を行う。 -Cerium では Taskと呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。 -依存関係はプログラマ自身が意識して記述する必要があり、Taskの種類が増えると記述が複雑になり、 負担が大きくなる。 Alice では処理の単位である Code Segment、 データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。 Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。 @@ -48,13 +46,13 @@ 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。 Meta Computationは本論のComputationを支えるComputationのことである。 関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。 -Gears OS では、Meta Code/Data Gear を Monadとして定義し、Meta Computationを実現する。 +Gears OS では、Meta Code Gear, Meta Data Gear を Monadとして定義し、Meta Computationを実現する。 Gears OS は並列実行をサポートするだけでなく、 信頼性も確保する。 そのために Gears OSを用いて作成されたプログラムに対する Model Checkingを行う機能\cite{model-check}を提供する。 並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。 これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。 -Model Checking の実現には Meta Code/Data Gearを用いる。 +Model Checking の実現には Meta Code Gear, Meta Data Gearを用いる。 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。 @@ -105,6 +103,17 @@ Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当する。 なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。 +図\ref{fig:list} は 通常の List の表現と Code Gear, Data Gear を使った List の表現である。 +通常の List は要素と次へのポインタをもつ構造体で表現される。 +Code Gear, Data Gear を使った List の場合、 Meta レベル以外でポインタを扱わないため、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。 + +\begin{figure}[ht] + \centering + \includegraphics[width=70mm]{pic/List.pdf} + \caption{List の表現} + \label{fig:list} +\end{figure} + \section{Context} ある Code Gear から継続するときには、次に実行する Code Gear を名前で指定する。 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。 @@ -121,19 +130,9 @@ \item Data Gear に格納される Data Type の情報 \end{itemize} -\section{List} -通常 List は要素と次へのポインタを持つ構造体で表現される。 -Gears OS の場合、Meta レベル以外でポインタは扱わないので図\ref{fig:list}のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。 - -\begin{figure}[ht] - \centering - \includegraphics[width=70mm]{pic/List.pdf} - \caption{List の表現} - \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 は Gear OS 内の Task を配るために必要なデータ構造である。 +Gears OS では List を表現する Code Gear, Data Gear に CAS(Compare and Swap) を行う Meta Code Gear, Meta Data Gear を接続することで Synchronized Queue を実現する。 Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。 この図を GearBox と呼ぶことにする。 図\ref{fig:sync}は Synchronized Queue の GearBox である。 @@ -149,10 +148,11 @@ \section{今後の課題} -Gears OS の今後の目的はCeriumと同等の例題を動かすことである。 -現在、必要な機能として Context、 Allocator、 List、 Non-Destructive Red-Black Tree、 Synchronized Queue を CbC を用いて実装しており、足りない機能としてはWorkerがある。 -Workerの実装後、動かす例題としては Bitonic Sort、 Word Count を予定している。 -例題の実装後、測定・評価を行う。 +今回、Gears OS の基本的な設計と必要な機能の一部をCbCを用いて実装した。 +今後の課題として Worker を実装する予定である。 +これにより, Cerium と同等の課題を動かす事が可能となる。 +動かす例題としては Bitonic Sort, Word Count を予定している。 +例題を実装後、 Gears OS の測定・評価を行う。 \begin{thebibliography}{10} \bibitem{cerium}