# HG changeset patch # User atton # Date 1484890785 -32400 # Node ID 415fa6d79d00158756e963be488ce93302f2c6aa # Parent db2909ab202dd5189af1a409f5dd7207ba8e40db Add GearsOS description diff -r db2909ab202d -r 415fa6d79d00 paper/cbc.tex --- a/paper/cbc.tex Fri Jan 20 12:40:43 2017 +0900 +++ b/paper/cbc.tex Fri Jan 20 14:39:45 2017 +0900 @@ -98,9 +98,9 @@ % }}} +% {{{ Continuation based C におけるメタ計算の例: GearsOS \section{Continuation based C におけるメタ計算の例: GearsOS} CbC におけるメタ計算は軽量継続を行なう際に Meta CodeSegment を挟むことで実現できる。 - CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142108_1}が存在する。 GearsOS とはマルチコアCPUやGPU環境での動作を対象としたOSであり、現在OSの設計と並列処理部分の実装が行なわれている。 現在存在するメタ計算としてメモリの確保と割り当て、並列に書き込むことが可能な Synchronized Queue、データの保存に用いる非破壊赤黒木がある。 @@ -111,5 +111,58 @@ 通常 GPU でデータの処理を行なう場合はデータの転送、転送終了を同期で確認、 kernel 実行、kernel の終了を同期で確認する、という手順が必要である。 CPU/GPU での処理をメタ計算で行なうことにより、ノーマルレベルでは CodeGear が実行されるデバイスや DataGear の位置を意識する必要が無いというメリットがある。 +GearsOS においては軽量継続の呼び出し部分もメタ計算として実現されている。 +ある CodeGear から次の CodeGear へと継続する際には、次に実行される CodeGear の名前を指定する。 +その名前を Meta CodeGear が解釈し、対応する CodeGear へと処理を引き渡す。 +これは従来の OS の Dynamic Loading Libary や Command の呼び出しに相当する。 +CodeGear と名前の対応は Meta DataGear に格納されており、従来の OS の Process や Thread に相当する。 + +具体的には Meta DataGear には以下のようなものが格納される。 + +\begin{itemize} + \item DataGear の型情報 + \item DataGear を格納するメモリの情報 + \item CodeGear の名前と CodeGear の関数ポインタ との対応表 + \item CodeGear が参照する DataGear へのポインタ +\end{itemize} + +実際の GearsOS におけるメモリ管理を含むメタ計算用の Meta DataGear の定義例をリスト\ref{src:context}に示す。 +Meta DataGear は Context という名前の構造体で定義されている。 + +\lstinputlisting[label=src:context, caption=GearsOS における Meta DataGearの定義例] {src/context.h} + +\begin{itemize} + \item DataGear の型情報 + + DataGear は構造体を用いて定義する(リスト\ref{src:context} 27-46行)。 + Tree や Node、 Allocate 構造体が DataGear に相当する。 + メタ計算は任意の DataGear 扱うために全ての DataGear を扱える必要がある。 + 全ての DataGear の共用体を定義することで、 DataGear を一律に扱うことができる(リスト\ref{src:context} 26-47行)。 + メモリを確保する場合はこの型情報からサイズを決定する。 + + \item DataGear を格納するメモリの情報 + + メモリ領域の管理は、事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 + そのために Context は割り当て済みの領域 heap と、割り当てた DataGear の数 dataNum を持つ。 + + \item CodeGear の名前と CodeGear の関数ポインタ との対応表 + + CodeGear の名前と CodeGear の関数ポインタの対応は enum と関数ポインタによって実現されている。 + CodeGear の名前は enum (リスト\ref{src:context} 5-9行) で定義され、コンパイル後には整数へと変換される。 + プログラム全体で利用する CodeGear は code フィールドに格納されており、enum を用いてアクセスする。 + この対応表を動的に変更することにより、実行時に比較ルーチンなどを変更することが可能になる。 + + + \item CodeGear が参照する DataGear へのポインタ + + Meta CodeGear は Context を引数に取る CodeGear として定義されている。 + そのため、Meta CodeGear が DataGear の値を使う為には Context から DataGear を取り出す必要がある。 + 取り出す必要がある DataGear は enum を用いて定義し(リスト\ref{src:context} 11-14行)、 CodeGear を実行する際に data フィールドから取り出す。 + なお、この Context から DataGear を取り出す Meta CodeSegment を stub と呼ぶ。 +\end{itemize} + +% }}} + + \section{メタ計算ライブラリ akasha を用いた赤黒木の実装の検証} diff -r db2909ab202d -r 415fa6d79d00 paper/fig/gears-meta.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/gears-meta.graffle Fri Jan 20 14:39:45 2017 +0900 @@ -0,0 +1,974 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle6 + 169.5.0.253125 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {1118.4000244140625, 782.79998779296875}} + Class + SolidGraphic + ID + 2 + Style + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2014-02-10 06:36:22 +0000 + Creator + utah + DisplayScale + 1 in = 1 in + GraphDocumentVersion + 12 + GraphicsList + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 34 + Points + + {414, 72} + {468, 72} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + 0 + Legacy + + LineType + 1 + Pattern + 1 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 29 + Info + 2 + + ID + 33 + Points + + {189, 72} + {243, 72} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + 0 + Legacy + + LineType + 1 + Pattern + 1 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 32 + Points + + {585, 99} + {585, 135} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 31 + OrthogonalBarAutomatic + + OrthogonalBarPoint + {0, 0} + OrthogonalBarPosition + -1 + Points + + {414, 162} + {468, 162} + {468, 72} + {531, 72} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 2 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 30 + Points + + {360, 99} + {360, 135} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 29 + OrthogonalBarAutomatic + + OrthogonalBarPoint + {0, 0} + OrthogonalBarPosition + -1 + Points + + {189, 162} + {243, 162} + {243, 72} + {306, 72} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 2 + TailArrow + 0 + + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 27 + Points + + {135, 99} + {135, 135} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + + + Bounds + {{60.5, 198}, {83, 30}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 26 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs32 \cf0 meta level} + + Wrap + NO + + + Bounds + {{51.0625, 3}, {96, 30}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 25 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs32 \cf0 normal level} + + Wrap + NO + + + Bounds + {{531, 135}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 24 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 meta3} + VerticalPad + 0.0 + + + + Bounds + {{306, 135}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 23 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 meta2} + VerticalPad + 0.0 + + + + Bounds + {{81, 135}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 22 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 meta1} + VerticalPad + 0.0 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + ID + 21 + Points + + {684, 117} + {54, 117} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + 0 + Legacy + + LineType + 1 + Pattern + 2 + TailArrow + 0 + + + + + Bounds + {{531, 45}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 19 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 code3} + VerticalPad + 0.0 + + + + Bounds + {{306, 45}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 5 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 code2} + VerticalPad + 0.0 + + + + Bounds + {{81, 45}, {108, 54}} + Class + ShapedGraphic + FontInfo + + Font + Helvetica + Size + 9 + + HFlip + YES + ID + 4 + Magnets + + {1, 0.5} + {1, -0.5} + {-1, 0.5} + {-1, -0.5} + {0.5, 1} + {-0.5, 1} + {0.5, -1} + {-0.5, -1} + + Style + + fill + + Color + + b + 0.99999099999999996 + g + 0.99997400000000003 + r + 1 + + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs28 \cf0 code1} + VerticalPad + 0.0 + + + + GridInfo + + SnapsToGrid + YES + + GuidesLocked + NO + GuidesVisible + YES + HPages + 2 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + Layer 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoLineLength + 0.20000000298023224 + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2016-02-09 02:10:43 +0000 + Modifier + utah + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595.20001220703125, 841.79998779296875} + + NSPrintReverseOrientation + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + Canvas 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + Expanded_Canvases + + Frame + {{252, -73}, {1263, 938}} + ShowInfo + + ShowRuler + + Sidebar + + SidebarWidth + 200 + TopSlabHeight + 250 + VisibleRegion + {{0, 0}, {749, 780}} + Zoom + 1 + ZoomValues + + + Canvas 1 + 1 + 1 + + + + + diff -r db2909ab202d -r 415fa6d79d00 paper/fig/gears-meta.pdf Binary file paper/fig/gears-meta.pdf has changed diff -r db2909ab202d -r 415fa6d79d00 paper/reference.bib --- a/paper/reference.bib Fri Jan 20 12:40:43 2017 +0900 +++ b/paper/reference.bib Fri Jan 20 14:39:45 2017 +0900 @@ -92,12 +92,12 @@ } @techreport{weko_142109_1, - author = "小久保,翔平 and 伊波,立樹 and 河野,真治", - title = "Monadに基づくメタ計算を基本とするGears OSの設計", - year = "2015", - institution = "琉球大学大学院理工学研究科情報工学専攻, 琉球大学工学部情報工学科, 琉球大学工学部情報工学科", - number = "16", - month = "may" + author = "小久保,翔平 and 伊波,立樹 and 河野,真治", + title = "Monadに基づくメタ計算を基本とするGears OSの設計", + year = "2015", + institution = "琉球大学大学院理工学研究科情報工学専攻, 琉球大学工学部情報工学科, 琉球大学工学部情報工学科", + number = "16", + month = "may" } % TODO : 会長さんの修論 diff -r db2909ab202d -r 415fa6d79d00 paper/src/context.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/context.h Fri Jan 20 14:39:45 2017 +0900 @@ -0,0 +1,47 @@ +/* Context definition */ + +#define ALLOCATE_SIZE 1024 + +enum Code { + Code1, + Code2, + Allocator, +}; + +enum UniqueData { + Allocate, + Tree, +}; + +struct Context { + int codeNum; + __code (**code) (struct Context *); + void* heap_start; + void* heap; + long dataSize; + int dataNum; + union Data **data; +}; + +union Data { + struct Tree { + union Data* root; + union Data* current; + union Data* prev; + int result; + } tree; + struct Node { + int key; + int value; + enum Color { + Red, + Black, + } color; + union Data* left; + union Data* right; + } node; + struct Allocate { + long size; + enum Code next; + } allocate; +};