Mercurial > hg > Papers > 2008 > akira-ieice
changeset 7:5cfa596eece1
*** empty log message ***
author | akira |
---|---|
date | Wed, 05 Mar 2008 11:25:22 +0900 |
parents | 01d07212a708 |
children | 34da095373ab |
files | bibitem.tex cbc.tex cell.tex compare.tex fig/pipeline.bb fig/pipeline.pdf fig/span.bb fig/span.pdf fig/taskmanager.bb fig/taskmanager.pdf introduction.tex multicore.tex rendering.tex thesis.tex |
diffstat | 14 files changed, 100 insertions(+), 121 deletions(-) [+] |
line wrap: on
line diff
--- a/bibitem.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/bibitem.tex Wed Mar 05 11:25:22 2008 +0900 @@ -2,11 +2,10 @@ \bibitem{bib:CbC} 河野真治. ``継続を持つCの下位言語によるシステム記述''. 日本ソフトウェア科学会第17回大会, 2000. -\bibitem{bib:Mesa} -OSMesa. http://www.mesa3d.org/ -\bibitem{bib:Blender} -Blender. http://www.blender.org/ \bibitem{bib:cbc-develop} 河野真治. ``継続を基本とするプログラム単位を用いた組み込みシステム開発''. 組み込みソフトウェア工学シンポジウム, 2003 +\bibitem{bib:SPURS} +井上 敬介 ``「Cellプロセッサ向け実行環境(SPU Centric Execution Model)」''. +先進的計算基盤システムシンポジウム SACSIS, 2006 \end{thebibliography}
--- a/cbc.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/cbc.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,11 +1,12 @@ \section{CbCの概要} CbCはC言語からループ制御構造とサブルーチンコールを取り除き、継続を導入し た言語である\cite{bib:CbC}。code-segmentは引数付きgotoで接続することで継 -続を実現する。以下は階乗の計算の例題である。\\ -\small{ -\input{src/fact.c} -} -\normalsize +続を実現する。 +%以下は階乗の計算の例題である。\\ +%\small{ +%\input{src/fact.c} +%} +%\normalsize code-segmentはキーワードcodeを用いることで関数のように定義される。引数部 分はinterfaceと呼ぶ。code-segmentからの脱出は引数付きgotoである。よって
--- a/cell.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/cell.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,8 +1,8 @@ \section{Cell} Cell Broadband EngineはメインプロセッサであるPowerPC Processor Element(PPE)と6個のデータ処理プロセッサアーキテクチャSynergistic -Processor Element(SPE)からなる非対称マルチコアプロセッサでなり、EIBと呼ばれる高速リン -グバスで構成されている。(図\ref{fig:Cell}) +Processor Element(SPE)が使用できる非対称マルチコアプロセッサでなり、EIB +と呼ばれる高速リングバスで構成されている。(図\ref{fig:Cell}) \begin{figure}[htb] \begin{center} \includegraphics[scale=.5]{./fig/Cell.pdf} @@ -13,7 +13,7 @@ PPEは複数のSPEをコアプロセッサとして使用することができる汎用プロセッサで、 オペレーティングシステムの役割であるメインメモリや外部デバイスへの入出力 -制御を行う。\\ +制御を行う。 SPEはPPEのような複雑な制御よりも計算を単純に繰り返すマルチメディア系の処 理を得意とする演算系プロセッサコアである。(図\ref{fig:SPE}) @@ -26,7 +26,9 @@ \end{figure} SPEはSPUとMFCから構成され、独自規格の命令セットを持っている。各々のSPUは -256Kbのメモリを持ち、各SPUから直接参照できる唯一のメモリとして存在する。また128Kbのレジスタを128本持っていることが特徴となっている。 +256Kbのメモリを持ち、各SPUから直接参照できる唯一のメモリとして存在する。 +また128Kbのレジスタを128本持ち、SPEは各自が持っているLS以外は参照するこ +とができない。メインメモリなどのデータにアクセスする場合はDMAを用いる。 MFCはメインメモリや他のSPEなどとデータをやりとりするためのユニットで、 SPUはチャネルというインターフェースを介してMFCに対してデータ転送などを依 頼し、各々のSPUが持つLSにメインメモリ上のデータなどを転送する。
--- a/compare.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/compare.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,6 +1,2 @@ -\section{Cとの比較} -従来のCでCeriumを記述すると、並列に動作するように考慮しながら記述しなけ -ればならない。それに比べて、CbCは状態遷移記述になるので、自然に並列向け -なプログラミング記述が可能となる。構文もほとんどCなので実装者が理解 -しやすく、スケジューラも容易に書くことができるので、より並列的なテスト環 -境を作ることが可能となる。 +\section{SPURSとの比較} +我々が作成したタスクマネージャに似た研究としてSPURS\cite{bib:SPURS}が挙げられる。SPURSは我々が今回作成したCeriumのようなSPUに入力データを与えるプログラムに関してはほとんど同じ機能を持っている。しかし、タスクがSPURSの場合は関数に対し、Ceriumではcode-segmentになる。
--- a/fig/pipeline.bb Tue Mar 04 20:30:02 2008 +0900 +++ b/fig/pipeline.bb Wed Mar 05 11:25:22 2008 +0900 @@ -1,5 +1,5 @@ %%Title: ./pipeline.pdf %%Creator: ebb Version 0.5.2 %%BoundingBox: 0 0 473 410 -%%CreationDate: Tue Mar 4 20:06:57 2008 +%%CreationDate: Wed Mar 5 02:56:18 2008
--- a/fig/span.bb Tue Mar 04 20:30:02 2008 +0900 +++ b/fig/span.bb Wed Mar 05 11:25:22 2008 +0900 @@ -1,5 +1,5 @@ %%Title: ./span.pdf %%Creator: ebb Version 0.5.2 -%%BoundingBox: 0 0 552 278 -%%CreationDate: Tue Mar 4 18:07:56 2008 +%%BoundingBox: 0 0 405 229 +%%CreationDate: Tue Mar 4 23:49:30 2008
--- a/fig/taskmanager.bb Tue Mar 04 20:30:02 2008 +0900 +++ b/fig/taskmanager.bb Wed Mar 05 11:25:22 2008 +0900 @@ -1,5 +1,5 @@ %%Title: ./taskmanager.pdf %%Creator: ebb Version 0.5.2 -%%BoundingBox: 0 0 421 291 -%%CreationDate: Tue Mar 4 14:12:46 2008 +%%BoundingBox: 0 0 422 291 +%%CreationDate: Wed Mar 5 02:44:21 2008
--- a/introduction.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/introduction.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,4 +1,10 @@ \section{はじめに} -継続を基本とする言語CbCによるCell上の並列計算について考察する。CbCはCに継続を付 -加し、while文などのループの制御構造とサブルーチンコールを取り除いた言語 -である。Cell上で実行されるタスクの呼び出しを行うタスクマネージャを使用したときのCbCの利点をのべ、Cとの比較を行う。 +Cから継続を基本とする言語CbCによるCell上の並列計算への変換手法について考 +察する。 +Cell Broadband Engineは一つの制御系プロセッサPower Processor Elementと7 +つのデータ処理演算プロセッサSynergistic Processor Element(SPE)から構成さ +れている。SPEには256KbのLocal Store(LS)と呼ばれるSPEから唯一直接参照でき +るメモリ領域があり、メインメモリや他のSPEのLSとのデータはDMAを通して行 +われる。ここでは信頼性の高い並列計算を行うプログラムを提供するためにCbC +を用いる。 +例題として我々が独自に開発したソフトウェアレンダリングエンジンCeriumを用いる。
--- a/multicore.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/multicore.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,14 +1,30 @@ -\section{マルチコアシステムの要求仕様} -ここでは例題としてCell上のDMA転送について考える。 -DMAを用いたSPEプログラムは基本的に次のようになる。 -\begin{small} -\input{src/spe.c} -\end{small} -この例で示したように、Cell上でSPEを用いる場合、次のような要素がまず必要になる。 -\begin{itemize} -\item 実行プログラム -\item 入力データアドレス -\item 入力データサイズ -\item 出力データアドレス -\end{itemize} -その後でRead、Exec、Writeという構造でCellのプログラムは記述できる。またReadとWriteはDMAで行われるためパイプライン形式で実行が可能となっている。 +\section{マルチコアシステム} +一概にマルチコアアーキテクチャといっても様々なマルチコアアーキテクチャが +存在する。簡単に分別するとホモジニアスマルチコア(図\ref{fig:homo})とヘテロジニアスマルチコ +ア(図\ref{fig:hetero})がある。 +\begin{figure}[htb] +\begin{center} +\includegraphics[scale=.5]{./fig/homogeneous.pdf} +\end{center} +\caption{ホモジニアスマルチコア} +\label{fig:homo} +\end{figure} +\begin{figure}[htb] +\begin{center} +\includegraphics[scale=.5]{./fig/heterogeneous.pdf} +\end{center} +\caption{ヘテロジニアスマルチコア} +\label{fig:hetero} +\end{figure} +ホモジニアスマルチコアはすべてのコアが同じコアで構成され、プログラマ側は +CPUコアや命令セットの違いを意識する必要がないが、汎用的なコアですべての +処理をこなすため、処理効率が悪いという特徴がある。それに対してヘテロジニ +アスマルチコアは二種類の構造があり、単一命令セットで構成されたマルチコア +と異種命令セットで構成されたマルチコアが存在する。単一命令セットで構成さ +れたマルチコアはCPUコアをタスクにあわせて最適化することで、効率の高いCPU +を作ることができる。しかし、異種命令セットのヘテロジニアスマルチコアはそ +れだけではなく、命令セットアーキテクチャレベルからタスクを最適化する必要 +がある。 + +必然的にシングルコアでは限られていたアルゴリズムがマルチコアの種類や並列 +化を考慮しアルゴリズムを考え直さなければいけない。 \ No newline at end of file
--- a/rendering.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/rendering.tex Wed Mar 05 11:25:22 2008 +0900 @@ -1,31 +1,18 @@ \section{レンダリングエンジン} -PS3Linuxでは以前我々が扱っていたPS2Linuxと違いGDPに直接アクセスすること -ができない。しかし、フレームバッファは扱うことができる。そこでMesa -\cite{bib:Mesa}のフレー -ムバッファ用ドライバであるOSMesaを使ってゲーム開発を行っていた。しかし、 -OSMesaはメインメモリ依存でCellのようなマルチコアアーキテクチャを活かすよ -うな分割を行うことは容易ではない。 - -そこで我々はシーングラフ、レンダリングエンジン、タスクマネージャからなる -Ceriumを例題として用いた。 - -ゲームの中の一つの場面(Scene)を構成するオブジェクトやその振る舞い、ゲー -ムのルールの集合をSceneGraphとする。SceneGraphの各ノードがゲームの一部で -あるオブジェクトのファイルやゲームのルールとなり、ノードをたどり実行する -ことでゲームの中の一つの場面となる。(図\ref{fig:scenegraph}) +ここでは例題として用いるレンダリングエンジンCeriumについて説明する。 +Ceriumはシーングラフ、レンダリングエンジン、タスクマネージャから構成され +る。(図\ref{fig:Cerium}) \begin{figure}[htb] \begin{center} -\includegraphics[scale=.5]{fig/scenegraph.pdf} +\includegraphics[scale=.4]{./fig/cerium_detail.pdf} \end{center} -\caption{シーングラフ} -\label{fig:scenegraph} +\caption{Ceriumの要素} +\label{fig:Cerium} \end{figure} -SceneGraphはゲームプログラムとしての -条件を満たす物なので、一つのSceneGraphで小さなゲームと言える。SceneGraph -はBlender3Dモデリングツール\cite{bib:Blender}から出力されるポリゴン情報やテクスチャ情報などが記述されたxmlをパースし、 -ポリゴンを取得する。ポリゴンとは図\ref{fig:SPAN}の三角形の各頂点の値のこ -とである。そのポリゴン座標を次の動作を汲み取った上で、動作に伴う行列演算 -を行う。 + +SceneGraphはBlender3Dモデリングツールから出力されるポリゴン情報やテクス +チャ情報などが記述されたxmlをパースし、XYZの頂点座標を取得する。図\ref{fig:Cerium}のSceneGraphの入力はXYZの頂点座標となる。XYZの頂点座標をキー入力にあわせて、拡大や縮小、移動などを行うのがTransformとなる。XYZの頂点をポリゴンにまとめるのがGatherとなる。 +ポリゴンとは図\ref{fig:SPAN}の三角形の各頂点の値のことである。 \begin{figure}[htb] \begin{center} \includegraphics[scale=.4]{fig/span.pdf} @@ -33,16 +20,14 @@ \caption{データ構造} \label{fig:SPAN} \end{figure} -\\ -レンダリングエンジンはOSMesaの機能を簡素化し、よりシンプルに設計されたフ -レームワークである。OSMesaではいろいろな機能を付加し続けた結果、様々な計 -算の部分でコピーがたくさん行われていた。それはCPUに多大な負荷を与えると -ともに動作が遅くなる大きな要因となっていた。そこで我々が提案するレンダリ -ングエンジンはシーングラフからポリゴンの各頂点を受け取り、頂点からSPANを -生成し、SPANに対応するテクスチャを生成するシンプルな物を目指す。ここで -SPANとは図\ref{fig:SPAN}のポリゴンに対するある特定のY座標に関数データを -抜き出した構造体で、そのSPANに対応するテクスチャは右の図のあるラインに対 -応する。 + +レンダリングエンジンはSPANを生成する部分とSPANにRGBをマッピングし描画す +る部分とに分けることができる。SPANとは図\ref{fig:SPAN}のポリゴンに対するある特定のY座標に関するデータを抜き出した構造体である。 +SPANを生成する部分は図\ref{fig:Cerium}のcreate\_spanの部分に相当する。Create\_SPANではポリゴンからSPANを計算する部分(CreateSPAN)とテクスチャを読み込む部分(TextureImage)のみ行う。 + +SPANにRGBをマッピングし描画する部分は図\ref{fig:Cerium}のDRAWの部分に相当する。 +DRAWではCreate\_SPANで生成されたSPANを受け取り、ZBufferをみながら描画するデータをメモリに書き込んでいく。ZBufferとは画面サイズ分用意されたZのメモリ空間で、XY座標に対する描画されるZの値が代入されている。SPANのZ座標とZBufferのZを比較し、カメラからみてどちらが手前にあるかというのを判断するのがDRAWのZcompareである。 +実際にZBufferと比較して描画するSPANであるならば、XY座標に対してのテクスチャのRGB情報をメモリに書き込む。その役目が図\ref{fig:Cerium}のMapping RGBとなる。RGB情報をマッピングした後、実際に描画するのがWriteFBとなる。 タスクマネージャはタスクを管理するライブラリで、タスクと呼ばれる分割され た各プログラムを依存関係を考慮しながらメモリ上にマッピングし、SPU上では @@ -54,21 +39,7 @@ \caption{タスクマネージャ} \label{fig:taskmanager} \end{figure} -\\ -これらをCbCで実装すると次のようになる。 -\begin{small} -\input{./src/render.c} -\end{small} -上記のソースはシーケンシャルなアルゴリズムでの実装コードである。 -SCENEGRAPH2POLYGONではシーングラフの計算を行い、ポリゴンの情報から回転や -拡大、平行移動などの計算を行い、ポリゴンの情報を次のcode-segmentに渡す。 -POLYGON2SPANでも同様に、受け取ったPOLYGONからSPANを出力する。SPAN2DRAWで -も基本的に変わらないが、ここで終了条件をみることになる。 - -これらのcode-segmentはすべてSPUで実行される。しかし、これだけでは足りな -い。実際にはSPUにテクスチャ情報をロードするcode-segmentが存在する。SPUで -実行するときは前述した通り、入力データアドレス、入力データサイズ、出力デー -タアドレスが必要となる。これらはタスクマネージャに登録される。 +これはSPUのLSが256Kbしかないため必要になる。 タスクマネージャは次のような関数で実行することができる。 \begin{table}[htb] \begin{center} @@ -79,6 +50,7 @@ create\_task & タスクを作る \\ \hline spawn\_task & 実行タスクQueueに追加 \\ \hline set\_depend & 依存関係の考慮 \\ \hline +set\_cpu & タスクを行うCPUのセット \\ \hline run & 実行タスクQueueの実行 \\ \hline \end{tabular} \caption{タスクマネージャの関数} @@ -86,12 +58,5 @@ \end{center} \end{table} \\ -タスクマネージャは登録されたcode-segmentをみて、プログラムのロードを行い、 -入力データの読み込み、計算、出力データの書き出しを行う。またcreate\_taskのときに入力データのサイズやアドレスなどが登録される。タスクマネージャはPPUで実行するかSPUで実行するかを明示的に書くことができる。またSPUを使う場合はSPUコアを使うことができる。そうすると、図\ref{fig:pipeline}のようなことができる可能性もある。 -\begin{figure}[htb] -\begin{center} -\includegraphics[scale=.5]{./fig/pipeline.pdf} -\end{center} -\caption{タスクマネージャが行うパイプライン} -\label{fig:pipeline} -\end{figure} +タスクマネージャは登録されたタスクをみて、プログラムのロードを行い、 +入力データの読み込み、計算、出力データの書き出しを行う。またcreate\_taskのときに入力データのサイズやアドレスなどが登録される。またタスクマネージャはPPUで実行するかSPUで実行するかを明示的に書くことができる。またSPUを使う場合はSPUコアを使うことができる。
--- a/thesis.tex Tue Mar 04 20:30:02 2008 +0900 +++ b/thesis.tex Wed Mar 05 11:25:22 2008 +0900 @@ -15,13 +15,15 @@ \def\BibTeX{{\rmfamily B\kern-.05em{\scshape i\kern-.025em b}\kern-.08em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125em X}} -\jtitle{Cellアーキテクチャを利用したCbCの応用} +\jtitle{CからCellアーキテクチャを利用したCbCへの変換} \jsubtitle{} \etitle{ Conversion to CbC which used the Cell architecture from C } \esubtitle{} \authorlist{% - \authorentry[akira@cr.ie.u-ryukyu.ac.jp]{神里 晃 }{Akira KAMIZATO}{Okinawa}% - \authorentry[kono@ie.u-ryukyu.ac.jp]{河野 真治}{Shinji KONO}{Okinawa}% + \authorentry[akira@cr.ie.u-ryukyu.ac.jp]{神里 晃 }{Akira KAMIZATO}{Okinawa} + \authorentry[gongo@cr.ie.u-ryukyu.ac.jp]{宮國 渡 }{Wataru MIYAGUNI}{Okinawa} + \authorentry[chiaki@cr.ie.u-ryukyu.ac.jp]{杉山 千秋 }{Chiaki SUGIYAMA}{Tokyo} + \authorentry[kono@ie.u-ryukyu.ac.jp]{河野 真治}{Shinji KONO}{Tokyo}% } \affiliate[Okinawa]{琉球大学理工学研究科情報工学専攻\hskip1zw 〒903-0213 沖縄県西原町千原1番地} @@ -29,12 +31,12 @@ University Of Ryukyus\hskip1em Senbaru 1, Nishihara , Okinawa, 903-0213 Japan} -%\affiliate[Tokyo]{琉球大学工学部情報工学専攻\hskip1zw -% 〒903-0213 沖縄県西原町千原1番地} -% {Information Engineering, -% University Of Ryukyus\hskip1em -% Senbaru 1, Nishihara , Okinawa, -% 903-0213 Japan} +\affiliate[Tokyo]{琉球大学工学部情報工学専攻\hskip1zw + 〒903-0213 沖縄県西原町千原1番地} + {Information Engineering, + University Of Ryukyus\hskip1em + Senbaru 1, Nishihara , Okinawa, + 903-0213 Japan} %\MailAddress{$\dagger$hanako@denshi.ac.jp, % $\dagger\dagger$\{taro,jiro\}@jouhou.co.jp} @@ -42,26 +44,17 @@ \begin{document} \begin{jabstract} 我々は状態遷移記述に向いたCの下位言語であるContinuation based C(CbC)を提 -案している。今回Cellアーキテクチャ上でのCbCを利用したCellプログラムについて -考察する。CbCはサブルーチンコールは行われず、gotoで接続された状態になるので、依存関係が明白になる。Cよりも自然な形で並列計算にマッピングしやすいという特徴を備えている。 -%今回Cellアーキテクチャを利用し、C言語からCbCを利用したCellプ -%ログラムを生成する手法について考察する。本変換で、信頼性の高い並列計算を -%行うシーケンシャルなプログラムを提供することが可能となる. +案している。今回Cellアーキテクチャを利用し、C言語からCbCを利用したCellプログラムを生成する手法ついて考察する。本変換で、信頼性の高い並列計算を行うシーケンシャルなプログラムを提供することが可能となる。 \end{jabstract} \begin{jkeyword} Cell,マルチコア, \end{jkeyword} \begin{eabstract} -IEICE (the Institute of Electronics, Information -and Communication Engineers) provides -a p\LaTeXe\ class file, named \IEICEJcls\ (ver.\,\IEICEver), -for the Technical Report of IEICE. -This document describes how to use the class file, -and also makes some remarks about typesetting a document by using p\LaTeXe. -The design is based on ASCII Japanese p\LaTeXe. +We are proposing Continuation based C(CbC), which is a low level language of C. +In this paper, the technique which converted CbC which used the Cell Architecture from C is considered.In this conversion, it can provide sequential program which is reliable parallel calculate. \end{eabstract} \begin{ekeyword} -p\LaTeXe\ class file, typesetting +multicore , Cell \end{ekeyword} \maketitle @@ -70,7 +63,8 @@ \input{cell.tex} \input{multicore.tex} \input{rendering.tex} -\input{debug.tex} +\input{develop_process.tex} +\input{doublebuffer.tex} \input{compare.tex} \input{finally.tex} \input{bibitem.tex}