Mercurial > hg > Papers > 2016 > kkb-master
changeset 22:faaba0936fa9
revision
author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 18 Feb 2016 19:44:11 +0900 |
parents | 9e1747657acd |
children | f147f579d552 |
files | paper/abstract.tex paper/abstract_eng.tex paper/appendix.tex paper/cerium.tex paper/history.tex paper/intro.tex paper/master_paper.bib paper/master_paper.pdf paper/master_paper.tex |
diffstat | 9 files changed, 153 insertions(+), 86 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/abstract.tex Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/abstract.tex Thu Feb 18 19:44:11 2016 +0900 @@ -1,15 +1,25 @@ \begin{abstract} - % Gears + % Gears + 本研究では Code/Data Segment によって構成される Gears OS の設計を行った。 + Gears OS は Cerium の開発を通して得られた知見を元に開発する。 Cerium はオブジェクト指向言語である C++ を用いて開発した並列プログラミングフレームワークである。 - Task 間の依存関係を記述することで並列処理を行う。 - しかし、Task 間の依存関係だけではデータの正しさを保証することができない。 - また、Task とのデータの受け渡しに汎用ポインタを使うためそこでデータの型情報を失う。 - 型情報がないので誤った型変換を行うと未定義の動作となる。 - オブジェクト指向も並列処理と相性が悪い。 - 我々の研究室では Code Segment という単位でプログラミングを行う CbC(Continuation based C) を開発している。 - Code Segment は並列処理の単位として用いることができる。 - 本研究では Cerium を開発して得られた知見からデータの単位として Data Segment を定義し、Code/Data Segment を用いた並列プログラミングフレームワーク Gears OS の開発を行う。 - Code/Data Segment で記述することでプログラム全体の並列度を高めて効率的に並列処理することを可能にする。 - 本論文では Gears OS の基本的な機能を設計し、実装に CbC を用いる。 - また、Gears OS の実装自体が Code/Data Segment を用いたプログラミングの指針となるように実装する。 + Cell, マルチコア CPU, GPU を用いた並列実行をサポートしている。 + 並列処理の単位として Task を記述し、Task に他の Task との依存関係を設定することで並列実行を実現する。 + データは汎用ポインタで Task に渡されるため、データの依存関係を保証できない。 + Cerium を用いて並列処理を行うことでプロセッサの性能を十分に引き出すことができる + しかし、データの正しさや依存関係を保証できていないので信頼性が低い。 + また、Cerium を用いて並列処理を記述するのは慣れが必要で難しい。 + オブジェクト指向自体もオブジェクトの状態によって振る舞いが変わるため参照透過性が低く並列処理と相性が悪い。 + 今回設計した Gears OS は本研究室で開発している Continuation base C(CbC) を用いて実装する。 + CbC は Code Segment と Data Segment という単位でプログラムを記述する。 + Code Segment は並列処理の単位として利用でき、Data Segment はデータのそのもので型情報を持つ。 + Gears OS ではメタレベルの処理をサポートする。 + Gears OS の各スレッドは Context と呼ばれるメタレベルの Data Segment を持つ。 + Context には接続可能な Code/Data Segment のリスト、Data Segment の型情報、独立したメモリ空間、スレッドの情報等が格納されている。 + Code Segment の遷移には goto を用いる。 + ノーマルレベルの Code Segment からノーマルレベルの Code Segment に遷移するときメタレベルの Code Segment を間に挟む。 + CbC は Code/Data Segment, メタレベルの処理、並列処理を記述できる言語である。 + Gears OS 自体が Gears OS を用いて並列処理を記述する際の指針となるように実装する。 + 本論文では Gears OS のプロトタイプを実装する。 + また、並列処理に必要な機能である Red-Black Tree, Synchronized Queue も実装し、簡単な並列処理の例題を用いて評価する。 \end{abstract}
--- a/paper/abstract_eng.tex Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/abstract_eng.tex Thu Feb 18 19:44:11 2016 +0900 @@ -1,19 +1,19 @@ \begin{abstract_eng} In this thesis we have designed Gears OS based on Code/Data Segment. - It is a reimplementation of Cerium TaskManger. - Cerium is parallel programming framework developed by C++, which suports Cell broadband Engine, Shared Memory Multi CPU and GPU. - Prallel computing of Cerium describes by Tasks, which have Task-Dependency. - Data structures are passed to a Task as input/output parameters but the structures have no type constraints nore Data-Dependencies. - Cerium gives good peformancies, but without type correctness and Data-Dependency, its programming very difficult and unreliable. - Cerium is implement in C++, which is not suitable in parallel machine because objects in C++ has no refernsial transparelency. - Newly desined Gears OS is wrriten in Continuation base C(CbC). - CbC has Code Segments which are suitable as tasks, it also has Data Segments with Type-Signeture. - Gears OS has meta computatin supports. - For each Thread of Gears OS there is a meta data segment called context. - The Context contains a set of Code Segments and Data Segments in the threads, it also has a meta data Segment such as Data Segment Type-Signeture, Memory Allocation and Threads information. + It is a reimplementation of Cerium TaskManager. + Cerium is parallel programming framework developed by C++, which suports Cell Broadband Engine, Shared Memory Multi CPU and GPU. + Parallel computing of Cerium describes by Tasks, which have Task-Dependency. + Data structures are passed to a Task as input/output parameters but the structures have no type constraints nor Data-Dependencies. + Cerium gives good performances, but without type correctness and Data-Dependency, its programming very difficult and unreliable. + Cerium is implement in C++, which is not suitable in parallel machine because objects in C++ has no referential transparency. + Newly designed Gears OS is written in Continuation base C(CbC). + CbC has Code Segments which are suitable as Tasks, it also has Data Segments with Type-Signature. + Gears OS has Meta Computation supports. + For each thread of Gears OS there is a Meta Data Segment called Context. + The Context contains a set of Code Segments and Data Segments in the threads, it also has a Meta Data Segment such as Data Segment Type-Signature, Memory Allocation and Threads information. A Code Segment passes the control to another Code Segment using a goto statement. - A Meta Computaion can be inserted between the Code Segments. - Using CbC, Code Segments, Data Segments and Meta Computaion, parallel computaion can be described in reliable style. - Since Gears OS itself is wrritened CbC it can be a guide to Gears OS Parallel Programming. - We show a prottype implemntation of Gears OS and show some examples including Red-Black Tree, Syncronized Queue, Simple parallel cmputaion example. + A Meta Computation can be inserted between the Code Segments. + Using CbC, Code Segments, Data Segments and Meta Computation, parallel computation can be described in reliable style. + Since Gears OS itself is written CbC it can be a guide to Gears OS Parallel Programming. + We show a prototype implementation of Gears OS and show some examples including Red-Black Tree, Synchronized Queue, Simple parallel computation example. \end{abstract_eng}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/appendix.tex Thu Feb 18 19:44:11 2016 +0900 @@ -0,0 +1,1 @@ +\chapter*{付録}
--- a/paper/cerium.tex Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/cerium.tex Thu Feb 18 19:44:11 2016 +0900 @@ -1,10 +1,12 @@ \chapter{並列プログラミングフレームワーク Cerium} -% gears Os ha cerim kara -% many core to gpu de aruteido -% monndaitenga aru +Gears OS は Cerium を開発して得られた知見を元に設計を行う。 -Cerium は PlayStation 3(PS3) に搭載された Cell Broadband Engine(Cell) 向けの Fine-Grain TaskManager として当研究室で設計・開発されたフレームワークである。 -本章では Cerium の実装について説明する。 +Cerium は並列実行に Cell, マルチコア CPU, GPU を用いることができる並列プログラミングフレームワークである。 +高い並列度を保ったまま複雑な並列処理を記述可能で、プロセッサの性能を十分に引き出すことができる。 +しかし、いくつかの問題点が存在する。 +Gears OS はそれらの問題点を解決することを目的とする。 + +本章では Cerium の設計・実装について説明し、評価を行う。 \section{Cerium の概要} Cerium は、TaskManager, SceneGraph, Rendering Engine の3つの要素から構成される。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/history.tex Thu Feb 18 19:44:11 2016 +0900 @@ -0,0 +1,5 @@ +\chapter*{発表履歴} +\begin{itemize} +\item 小久保翔平, 河野真治. 並列プログラミングフレームワーク Cerium の OpenCL, CUDA への対応. 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS), May 2014. +\item 小久保翔平, 伊波立樹, 河野真治. Monad に基づくメタ計算を基本とする Gears OS の設計. 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS), May 2015. +\end{itemize}
--- a/paper/intro.tex Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/intro.tex Thu Feb 18 19:44:11 2016 +0900 @@ -1,4 +1,4 @@ -\chapter{並列環境下におけるプログラミング} +\chapter{並列環境下における\\プログラミング} CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。 そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。 マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。 @@ -8,15 +8,16 @@ 並列処理をする上でこれらのリソースを無視することができない。 しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。 +本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS の設計・実装を行う。 -Cerium は本研究室で開発している並列プログラミングフレームワークである。 +Cerium は本研究室で開発していた並列プログラミングフレームワークである。 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。 Cerium では依存関係を Task 間で設定するが、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない。 また、Task には汎用ポインタとしてデータの受け渡しを行うので型情報を失う。 Task 側で正しく明示的に型変換する必要があり、誤った型変換を行うとデータ構造自体を破壊する可能性がある。 型システムによって検査することも出来ず、型に基づく一連の不具合が常に付きまとう。 -今回、設計・実装を行なった Gears OS は Code Segment と Data Segment によって構成される。 +Gears OS は Code Segment と Data Segment によって構成される。 Code Segment は処理の単位、Data Segment はデータの単位となる。 Gears OS では Code/Data Segment を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。 また、Gears OS の実装自体が Code/Data Segment を用いたプログラミングの指針となるように実装する。
--- a/paper/master_paper.bib Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/master_paper.bib Thu Feb 18 19:44:11 2016 +0900 @@ -1,3 +1,57 @@ +@article{ + cbc1, + author = "河野 真治 and 島袋 仁", + title = "C with Continuation と、そのPlayStationへの応用", + journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", + month = "May", + year = 2000 +} + +@article{ + trans, + author = "河野 真治 and 揚 挺", + title = "C言語の Continuation based C への変換", + journal = "SWoPP 2001", + month = "July", + year = 2001 +} + +@article{ + refactoring, + author = "河野 真治", + title = "Continuation based C を使ったソースコードのリファクタリング手法", + journal = "日本ソフトウェア科学会第21回大会論文集", + month = "Sep", + year = 2004 +} + +@article{ + systemcall, + author = "宮國 渡 and 河野 真治", + title = "Continuation base C 言語による OS システムコールの意味記述", + journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", + month = "April", + year = 2007 +} + +@article{ + model-check, + author = "下地 篤樹 and 河野 真治", + title = "線形時相論理によるContinuation based Cプログラムの検証", + journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", + month = "April", + year = 2007 +} + +@article{ +kono:2008a, + author = "河野真治", + title = "検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用", + journal = "電子情報通信学会VLSI設計技術研究会", + month = "March", + year = 2008 +} + @article{ cerium, author = "宮國 渡 and 河野 真治 and 神里 晃 and 杉山 千秋", @@ -6,22 +60,7 @@ month = "April", year = 2008 } - -@article{ - alice, - author = "赤嶺 一樹 and 河野 真治", - title = "DataSegment API を用いた分散フレームワークの設計", - journal = "日本ソフトウェア科学会第28回大会論文集", - month = "Sep", - year = 2011 -} - -@misc{cell, - author = "{Sony Corporation}", - title = "{Cell broadband engine architecture}", - year = 2005 -} - + @article{ segment, author = "河野 真治 and 杉本 優", @@ -32,14 +71,14 @@ } @article{ - cbc, - author = "河野 真治 and 島袋 仁", - title = "C with Continuation と、そのPlayStationへの応用", - journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", - month = "May", - year = 2000 + prosym-cerium, + author = "渡真利 勇飛 and 小久保 翔平 and 河野 真治", + title = "Cerium Task Manager における GPU と MultiCore CPU の同時実行", + journal = "第55回プログラミング・シンポジウム", + month = "Jan", + year = 2014 } - + @article{ cbc-llvm, author = "徳森 海斗 and 河野 真治", @@ -50,35 +89,40 @@ } @article{ - monad, - author = "Eugenio Moggi", - title = "Computational lambda-calculus and monads", - journal = "Proceedings of the Fourth Annual Symposium on Logic in computer science", - year = 1989 + cerium2, + author = "小久保 翔平 and 河野 真治", + title = " 並列プログラミングフレームワーク Cerium の OpenCL, CUDA への対応", + journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", + month = "May", + year = 2014 +} + +@article{ +gears, +author = "小久保 翔平 and 伊波 立樹 and 河野 真治", +title = "Monad に基づくメタ計算を基本とする Gears OS の設計", +journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", +month = "May", +year = 2015 } @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}", -year = 2007 -} - -@misc{cuda, -title = "{CUDA}", -howpublished = "{https://developer.nvidia.com/category/zone/cuda-zone/}" +cbc-lola, +author = "Kaito TOKKMORI and Shinji KONO", +title = "Implementing Continuation based language in LLVM and Clang", +journal = "LOLA 2015", +month = "July", +year = 2015 } @misc{ - msg, - title = "MessagePack", - howpublished = "{http://msgpack.org/}" -} \ No newline at end of file +opencl, +title = "{OpenCL}", +howpublished = "{https://www.khronos.org/registry/cl/sdk/2.1/docs/man/xhtml}" +} + +@misc{ +cuda, +title = "{CUDA}", +howpublished = "{http://docs.nvidia.com/cuda/index.html}" +}
--- a/paper/master_paper.tex Thu Feb 18 17:12:23 2016 +0900 +++ b/paper/master_paper.tex Thu Feb 18 19:44:11 2016 +0900 @@ -101,7 +101,11 @@ \bibliographystyle{junsrt} \bibliography{master_paper} -%付録 +%発表履歴 +\addcontentsline{toc}{chapter}{発表履歴} +\input{history.tex} -\printindex +%付録 +\addcontentsline{toc}{chapter}{付録} +\input{appendix.tex} \end{document}