Mercurial > hg > Papers > 2016 > ikkun-midterm
changeset 2:b62cf63d9812 default tip
rewrite rb_tree and GPGPU
| author | ikkun |
|---|---|
| date | Sat, 22 Oct 2016 19:12:11 +0900 |
| parents | 1b5ee04a7b4f |
| children | |
| files | midterm.pdf midterm.tex pic/gearsosgpgpu.bb pic/gearsosgpgpu.pdf pic/gearsosgpgpu.xbb pic/rb_tree.bb pic/rb_tree.pdf pic/rb_tree.xbb |
| diffstat | 8 files changed, 23 insertions(+), 9 deletions(-) [+] |
line wrap: on
line diff
--- a/midterm.tex Sat Oct 22 00:28:39 2016 +0900 +++ b/midterm.tex Sat Oct 22 19:12:11 2016 +0900 @@ -81,17 +81,31 @@ \end{itemize} \section{Red Black Tree} - Red Black Tree(赤黒木)は平衡二分木の一種で、主に連想配列の実装に使われる。Red Black Tree の Stack Pop,Stack Push している部分に Stub を仲介させることによって、Stack pop と Stack psuh を Data Gear に分けることで CbC による記述に直した。 +図\ref{fig:rb_tree}はRed Black Treeにおけるinsertとバランシングのアルゴリズムを表したものです。 +putした時、rootがあればNew Node をpushして空いているNodeにReplaceする。rootがなければinsertする。 +Red Black Treeのバランシングはバランスに必要な分Popで戻り、バランスさせる点まで来たらRoutateR RoutateLする。 +Routateは自分の今のNodeとParentとGrandPararentの３種類でroutateする。 \begin{figure}[ht] \centering \includegraphics[width=70mm]{pic/rb_tree.pdf} \caption{CbCでのRed Black Tree} - \label{fig:rb_Tree} + \label{fig:rb_tree} \end{figure} \section{GPGPU} GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。 GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。 Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に変数が書き変わる事がない。 +図\ref{fig:gpgpu}では以下の流れで処理が行われる。 +\begin{itemize} + \item Data Gear をPersistent Data Tree に挿入。 + \item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。 + \item 生成したTaskをTaskQueueに挿入。 + \item Workerの起動。 + \item WorkerがTskQueueからTaskを取得。 + \item 取得した Task を元に必要なData Gear を Persistent Data Tree から取得。 + \item 並列処理される Code Gear を実行。 +\end{itemize} + \begin{figure}[ht] \centering \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf}
--- a/pic/gearsosgpgpu.bb Sat Oct 22 00:28:39 2016 +0900 +++ b/pic/gearsosgpgpu.bb Sat Oct 22 19:12:11 2016 +0900 @@ -1,5 +1,5 @@ %%Title: gearsosgpgpu.pdf %%Creator: extractbb 20150315 -%%BoundingBox: 0 0 1156 979 -%%CreationDate: Fri Oct 21 19:35:18 2016 +%%BoundingBox: 0 0 1322 1377 +%%CreationDate: Sat Oct 22 02:15:02 2016
--- a/pic/gearsosgpgpu.xbb Sat Oct 22 00:28:39 2016 +0900 +++ b/pic/gearsosgpgpu.xbb Sat Oct 22 19:12:11 2016 +0900 @@ -1,8 +1,8 @@ %%Title: gearsosgpgpu.pdf %%Creator: extractbb 20150315 -%%BoundingBox: 0 0 1156 979 -%%HiResBoundingBox: 0.000000 0.000000 1156.000000 979.000000 +%%BoundingBox: 0 0 1156 1375 +%%HiResBoundingBox: 0.000000 0.000000 1156.000000 1375.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Fri Oct 21 19:35:06 2016 +%%CreationDate: Sat Oct 22 02:17:02 2016