@@ -100,7 +117,7 @@ メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、階層上の構造となっている。 - この2つのレベルはプログラミング言語レベルでの変換として実現される。 -- 本研究では Perl スクリプトによって実装されている。 +- 本研究では Perl スクリプトによってノーマルレベルからメタレベルへの変換が実装されている。 ## Meta Gear - Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。 @@ -115,518 +132,651 @@ - Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする。 ## Context -- Context は Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。 -- - +- Context は全ての Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。 +```c +enum Code { + C_popSingleLinkedStack, + C_pushSingleLinkedStack, + C_stackTest3, + C_assert3, + ... +}; +``` +```c +context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub; +context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub; +context->code[C_stackTest3] = stackTest3_stub; +context->code[C_assert3] = assert3_stub; +``` - - - +## Context +- Data Gear も Code Gear と同様に Context が全ての Data Gear のリストを持っている。 +- Data Gear のリストも enum で管理されている。 +- これは引数格納用の Data Gear の番号である。 +```c +enum DataType { + D_Code, + D_SingleLinkedStack, + D_Stack, + D_TaskManager, + D_Worker, + ... + }; +``` ## stub Code Gear -- Data Gear にアクセスするには Context から番号を指定して行う -- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある -- Gears OS では Code Gear に接続する Data Gear をメタレベルである Context から取り出す処理を行う stub Code Gear を用意している - -

- -## Interface -- Gears OS を実装するに連れて、stub Code Gear の記述が煩雑になることがわかった -- そこで、Gears OS のモジュール化する仕組みとして **Interface** を導入した -- Interface はある Data Gear とそれに対する操作(API) を行う Code Gear の集合を表現する Data Gear -- stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能 -- Interface を導入することで、 Stack や Queue などのデータ構造を仕様と実装に分けて記述することが出来る -- Interface は Java のインターフェース、 Haskell の型クラスに対応する - -## Interface の定義 -- Interface の定義には以下の内容を定義する - - 操作(API)の引数群の型 - - 操作(API)自体のCode Gear の型 - -``` c -typedef struct Queue{ - // Data Gear parameter - union Data* queue; - union Data* data; - __code next(...); - __code whenEmpty(...); - - // Code Gear - __code clear(Impl* queue, __code next(...)); - __code put(Impl* queue, union Data* data, __code next(...)); - __code take(Impl* queue, __code next(union Data*, ...)); - __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); -} Queue; -``` +- ノーマルレベルの Gears OS では継続先に渡す Data Gear は引数の集合に見える。 +- しかし、メタレベルで見ると、Data Gear は Context が管理しており、 +アクセスするには Context を介さなくてはならない。 +```c +__code cg1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stackPush(stack, node); +} -## Interface の定義 -- **__code next(...)** は継続を表している -- ... は可変長引数に相当する -- 可変長引数部分には呼び出し元の Interface の Data Gear が入る -- 継続の引数で Output Data Gear を返すことが出来る - -``` c -typedef struct Queue{ - // Data Gear parameter - union Data* queue; - union Data* data; - __code next(...); - __code whenEmpty(...); - - // Code Gear - __code clear(Impl* queue, __code next(...)); - __code put(Impl* queue, union Data* data, __code next(...)); - __code take(Impl* queue, __code next(union Data*, ...)); - __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); -} Queue; -``` - -## Interface のインスタンスの生成 -- Interface は API に Code Gear を番号を入れることにより、複数の実装ヲ行うことが出来る -- 代入する Code Gear を入れ替えることで別の実装を表現する -- Interface を表す Data Gear の生成は以下の関数で行われる - -``` c -Queue* createSingleLinkedQueue(struct Context* context) { - struct Queue* queue = new Queue(); // Allocate Queue interface - struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement - queue->queue = (union Data*)singleLinkedQueue; - singleLinkedQueue->top = new Element(); - singleLinkedQueue->last = singleLinkedQueue->top; - queue->clear = C_clearSingleLinkedQueue; - queue->put = C_putSingleLinkedQueue; - queue->take = C_takeSingleLinkedQueue; - queue->isEmpty = C_isEmptySingleLinkedQueue; - return queue; +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } ``` -## Interface の使い方 -- Interface を利用した Code Gear への継続は `goto interface->method` で行われる -- **interface** は Interface を表す Data Gear、 **method** は実装した Code Gear に対応する +## stub Code Gear +- このノーマルレベルとメタレベルのズレを合わせるための Meta Code Gear である +Stub Code Gear が Code Gear の間に挿入される。 +- stub Code Gear は Context から継続先の Code Gear が必要とする Data Gear を取り出す作業を行う。 +```c +__code stackPush_stub(struct Contet* context) { + Stack* stack = &context->data[D_Stack]->Stack; + Node* node = &context->data[D_Node]->Node; + goto stackPush(context, stack, node); +} -``` c -__code code1() { - Queue* queue = createSingleLinkedQueue(context); - Node* node = new Node(); - node->color = Red; - goto queue->put(node, code2); +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } ``` -## メタレベルでの Interface の呼び出しの詳細 -- Interface を利用した Code Gear の継続はスクリプトによってメタレベルの記述に変換される - - 変換後は Context を参照するコードが生成される -- Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す -- Context には Interface の引数を渡すための Data Gear が予め用意されている -- goto meta では Interface の Code Gear の番号を Code Gear へのポインタに変換して継続を行う - -``` c -__code code1(struct Context *context) { - Queue* queue = createSingleLinkedQueue(context); - Node* node = &ALLOCATE(context, Node)->Node; - node->color = Red; - Gearef(context, Queue)->queue = (union Data*) queue; - Gearef(context, Queue)->data = (union Data*) node; - Gearef(context, Queue)->next = C_code2; - goto meta(context, queue->put); -} -``` +## stub Code Gear +- メタレベルで見た Code Gear の引き渡し +

-## Interface での stub Code Gear -- meta Code Gear では引数に指定された Code Gear の番号から stub Code Gear への関数ポインタを取り出し、継続を行う -- メタ計算で格納された引数は stub Code Gear で Code Gear に渡される -- Interface を実装した Code Gear は Interface の定義から stub Code Gear の自動生成が可能 -- 必要ならばメタ計算を meta Code Gear か stub Code Gear に埋め込むことができる - -``` c -// implement put code gear -__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, - union Data* data, enum Code next) { - ... +## goto meta +- Gears OS では Code Gear もリストで管理しており、継続する際には一度 \_\_code meta へと継続する。 +- ここでノーマルレベルの Code Gear には変換が行われているが、これはコンパイル時に変換される。 +- この変換によりノーマルレベルでは隠れていた Context が見えるようになっている。 +- context に引き渡しているコードもここで生成される。 +```c +__code cg1(struct Context* context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + &context->data[D_Stack]->Stack = (union Data*) stack; + &context->data[D_Node]->Node = node; + goto meta(C_stackPush); } -// generated by script -__code putSingleLinkedQueue_stub(struct Context* context) { - SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue); - Data* data = Gearef(context, Queue)->data; - enum Code next = Gearef(context, Queue)->next; - goto putSingleLinkedQueue(context, queue, data, next); -} __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); } ``` -## 並列処理の構成 -- 今回は並列処理機構である - - Task - - 1つの Context 上で goto で遷移しながら実行される Code Gear の列 - - TaskManager - - 依存関係を解決したTask を Worker SynchronizedQueue に送信する - - Worker - - SynchronizedQueue から Task を一つずつ取得し、実行する - - Worker 毎に POSIX Therad などを生成し、それぞれのスレッドで Code Gear を実行する - - SynchronizedQueue - - Gears OS で記述されたマルチスレッド環境でもデータの同期処理が行われる Queue -- これらを Interface として実装した +## Interface +- Interface は Gears OS のモジュール化の仕組みである。 +- Interface はある Data Gear と、それに対する操作(API)を行う +Code Gear とその操作に用いる Data Gear の集合を表現する。 +- Java の Interface に対応し、定義することで複数の実装を持つことができる。 + +## Interface の定義 +- Stack の Interface の例である。 +- typedef struct Interface 名で記述する。 +- Impl は実際に実装した際のデータ構造の型になる。 + +```c +typedef struct Stack { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -## Task -- Gears OS では Context が並列実行の Task に相当する -- Context は Task用の情報として以下の情報を付け加えた - - 実行する Code Gear - - Input/Output Data Gear の格納場所 - - 待っている Input Data Gear の数 - - この Task を実行する Worker + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + +} +``` -## TaskManger -- Worker をCPU、 GPU の数分生成する -- 依存関係を解決した Task を各 Worker の Queue に送信する +## Interface の定義 +- Data Gear は操作する Data Gear と +操作に必要な全ての Data Gear Gear が記述されている。 +- \_\_code で記述されているものが操作の Code Gear である。 -

Task を Input Data Gear としてTaskManager の spawn を呼び出す
Task が待っている Data Gear のカウンタである IDGCount をチェックする
IDGCount が0の場合 Data Gear が揃っているので Worker の Queue に Task を送信する

+```c +typedef struct Stack { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -## Worker -- 初期化時に Worker 用の Context を生成し、Code Gear を実行していく -- TaskManager から送信された Task を一つずつ取得して実行する + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + +} +``` -

Worker は Queue から Task(Context)を取得する
Worker の Context からTask の Context へ入れ替える
Task に設定されている Code Gear を実行
Task の Output Data Gear の書き出し
Task Context から Worker の Context へ入れ替える
Worker は再び Queue から Task を取得する

+## Interface の実装の記述 +- ソースコードは Interface の実装の初期化のコードである。 +- 操作の Code Gear には実装した Code Gear の番号が代入されるが、ここを入れ替えることで、複数の実装を持つことができる。 +```c +Stack* createSingleLinkedStack(struct Context* context) { + struct Stack* stack = new Stack(); + struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack(); + stack->stack = (union Data*)singleLinkedStack; + singleLinkedStack->top = NULL; + stack->push = C_pushSingleLinkedStack; + stack->pop = C_popSingleLinkedStack; + stack->isEmpty = C_isEmptySingleLinkedStack; + stack->clear = C_clearSingleLinkedStack; + return stack; +} +``` -## Synchronized Queue -- TaskManager と Worker 間の通信を行うための Queue -- マルチスレッドでのデータの同期処理を行える SynchronizedQueue として実装する -- Gears OS では同期機構として CAS(Check and Set、 Compare and Swap) を使用した実装を行った - - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較し、変化がなければ値を更新する - - メモリ番地の値が変わっているなら、もう一度 CAS を行う +## Interface の操作の呼び出し +- Interface の操作の呼び出しは、ノーマルレベルでは `goto interface->method` の形で記述される。 +- interface は Interface を表す Data Gear 、method は実装した Code Gear に対応する。 -

- -## 依存関係の解決 -- 依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する -- この Queue には Data Gear に依存関係がある Context が格納されている +```c +__code stackTest1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stack->push(node, stackTest2) +} +``` -

Task に設定されている Code Gear を実行する
Output Data Gear の書き出し処理を行う際にメタレベルの Queue を参照する
依存関係にある Task を取り出し、IDGCount をデクリメントする

- -- IDGCountの値が0になった実行可能な Task は TaskManager を通して Worker に送信される +## Interface の操作の呼び出し +- interface の操作の呼び出しは、メタレベルでは以下のように変換される。 +- stack->push には enum の番号が入っているため、\_\_code meta で +対応する番号の Code Gear へと継続する。 +```c +__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +``` -## 並列構文 -- 並列実行する際は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する -- この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述としては好ましくない -- Context の設定は煩雑な記述だが、並列実行されることを除けば通常の CbC の goto 文と同等 -- そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した +## Interface の操作の呼び出し +- ここで Gearef という記述があるが、これは Context を参照するためのマクロである。 +`Gearef(context, t) (&(context)->data[D_##t]->t)` +- 格納先は Interface の型が持つ Data Gear へ格納される。 +```c +__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +``` -## par goto 構文 -- par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される -- par goto 構文には引数として Input/Output Data Gear等を渡す -- スクリプトによって Code Gear の Input/Output の数を解析し、待っている Input Data Gear の数を設定する -- 並列実行される Task は **__exit** に継続することで終了する - - Gears OS の Task はOutput Data Gear を書き出す処理で終了するため **__exit** に直接継続せずに Data Gear を書き出す処理に継続する -- par goto 構文は通常のプログラミングの関数呼び出しのように扱える +## Interface における stub Code Gear +- Interface の情報から stub Code Gear は自動生成される。 +- 引数に必要な Data Gear は Interface の型が持つ Data Gear から取り出す。 +- GearImpl は interface の操作が対象にする Data Gear を取り出すマクロである。 +`GearImpl(context, intf, name) (Gearef(context, intf)->name->intf.name)` +```c +__code pushSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,union Data* data, enum Code next) { + ... +} -``` c -__code code1(Integer *integer1, Integer * integer2, Integer *output) { - par goto add(integer1, integer2, output, __exit); - goto code2(); +__code pushSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); + Data* data = Gearef(context, Stack)->data; + enum Code next = Gearef(context, Stack)->next; + goto pushSingleLinkedStack(context, stack, data, next); } ``` -## CUDA への対応 -- Gears OS は GPU での実行もサポートしている -- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる -- CUDA は GPU を Device、 CPU を Host として定義する -- CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する -- 今回、CUDA に合わせた並列処理機構である CUDAWorker、 CUDAExecutor をInterface を用いて実装し、 CPU、GPU 間のデータのマッピングのために CUDABuffer を用意した +## 目次 +- xv6 の書き換えの方針について +- システムコールの書き換えについての考察 +- 書き換えたシステムコールを追う + +## xv6 の CbC 書き換え +- xv6 は UNIX V6 を x86 向けに再実装した OS である。 +- プロセスや仮想メモリ、カーネルとユーザーの分離、割り込み、ファイルシステムなどの基本的な Unix の構造を持つ +- CbC は Code Gear 間の遷移が goto による継続で行われるため、状態遷移ベースでのプログラミングに適している。 +- CbC で xv6 を書き換えることにより、状態遷移モデルによるモデル検査が可能となることを期待する。 + +## xv6 の書き換えの方針 +- xv6 を CbC で書き換え、Gears OS の機能と置き換えることで Gears OS に OS の基本構造を持たせたい。 +- このためには xv6 をモジュール化することで、xv6 の機能を明らかにする必要がある。 +- xv6 の Interface を定義し、Gears OS の機能をこれに合わせることによって実現したい。 + +## システムコールの書き換え +- CbC は C と互換性のある言語であるため、元のソースコードから大きく崩すことなく必要な機能のみを CbC へと書き換えることが可能である。 +- ここでは実際にシステムコールを CbC で書き換えることによって、状態遷移ベースで書き換えるには何が必要か示すことにした。 +- 今回は read システムコールの CbC 書き換えを行なった。 -## CUDAWorker -- CUDA で実行する Task を受け取る Worker -- 初期化の際に CUDA ライブラリの初期化や CUDAExecutor の生成を行う +## syscall関数 +- syscall 関数はシステムコールを呼び出す関数である。 +```c +void syscall(void) +{ + int num; + int ret; + num = proc->tf->r0; + if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) { + proc->cbc_arg.cbc_console_arg.num = num; + goto (cbccodes[num])(cbc_ret); + } + if((num > 0) && (num <= NELEM(syscalls)) && syscalls[num]) { + ret = syscalls[num](); + if (num != SYS_exec) { + proc->tf->r0 = ret; + } + } else { + cprintf("%d %s: unknown sys call %d\n", proc->pid, proc->name, num); + proc->tf->r0 = -1; + } +} +``` + +## sys\_read 関数 +- 読み込むファイルの情報とアドレスを取り出し、fileread に渡している +```c +int sys_read(void) +{ + struct file *f; + int n; + char *p; + + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + return -1; + } + + return fileread(f, p, n); +} +``` + +## cbc\_read +```c +__code cbc_read(__code (*next)(int ret)){ + struct file *f; + int n; + char *p; -## CUDAExecutor -- CUDAExecutor は Executor Interface を実装した Data Gear -- 以下の Code Gear を実装している - - HostからDevice へのデータの送信(read) - - kernel の実行(exec) - - Device から Host へのデータの書き出し(write) + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + goto next(-1); + } + goto cbc_fileread(f, p, n, next); +} +``` + +## fileread +- file の状態を確認し、対応した関数へ移行する。 +```c +int fileread (struct file *f, char *addr, int n) +{ + int r; + + if (f->readable == 0) { + return -1; + } + + if (f->type == FD_PIPE) { + return piperead(f->pipe, addr, n); + } + + if (f->type == FD_INODE) { + ilock(f->ip); + + if ((r = readi(f->ip, addr, f->off, n)) > 0) { + f->off += r; + } + + iunlock(f->ip); + + return r; + } -``` c -typedef struct Executor{ - union Data* Executor; - struct Context* task; - __code next(...); - // method - __code read(Impl* executor, struct Context* task, __code next(...)); - __code exec(Impl* executor, struct Context* task, __code next(...)); - __code write(Impl* executor, struct Context* task, __code next(...)); + panic("fileread"); +} +``` + +## cbc\_fileread +```c +__code cbc_fileread1 (int r) +{ + struct file *f = proc->cbc_arg.cbc_console_arg.f; + __code (*next)(int ret) = cbc_ret; + if (r > 0) + f->off += r; + iunlock(f->ip); + goto next(r); +} + +__code cbc_fileread (struct file *f, char *addr, int n, __code (*next)(int ret)) +{ + if (f->readable == 0) { + goto next(-1); + } + + if (f->type == FD_PIPE) { + //goto cbc_piperead(f->pipe, addr, n, next); + goto next(-1); + } + + if (f->type == FD_INODE) { + ilock(f->ip); + proc->cbc_arg.cbc_console_arg.f = f; + goto cbc_readi(f->ip, addr, f->off, n, cbc_fileread1); + } + + goto cbc_panic("fileread"); } ``` -## CUDABuffer -- Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある -- CUDA Buffer ではそのマッピングを行う - - このマッピングは Task に設定されている stub Code Gear で行われる - -

+## readi +- readi はファイルシステム上か特殊なデバイスを制御するかどうかで分岐する +- ここでは consoleread へ向かう処理を確認する。 +```c +int readi (struct inode *ip, char *dst, uint off, uint n) +{ + uint tot, m; + struct buf *bp; -## CUDA での呼び出し -- Gears OS では Task に設定している Code Gear の stub Code Gear で CUDA実行を切り替える -- CUDABuffer でのマッピング、実行する kernel の読み込みは stub Code Gear で行われる -- CUDA で実行する際は stub Code Gear に対応する Code Gear ではなく、 CUDAExecutor の Code Gear に継続する + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) { + return -1; + } -

+ return devsw[ip->major].read(ip, dst, n); + } +... +``` -## Gears OS の評価 -- 並列処理のタスクの例題として Twice と BitonicSort を実装し、以下の環境で測定を行った -- CPU 環境 - - Model : Dell PowerEdgeR630 - - Memory : 768GB - - CPU : 2 x 18-Core Intel Xeon 2.30GHz -- GPU 環境 - - GPU : GeForce GTX 1070 - - Cores : 1920 - - ClockSpeed : 1683MHz - - Memory Size : 8GB GDDR5 +## cbc\_readi +```c +__code cbc_readi (struct inode *ip, char *dst, uint off, uint n, __code (*next)(int ret)) +{ + uint tot, m; + struct buf *bp; + + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !cbc_devsw[ip->major].read) { + goto next(-1); + } + + goto cbc_devsw[ip->major].read(ip, dst, n, next); + } +... +``` -## Twice -- Twice は与えられた整数配列を2倍にする例題である -- 並列実行の依存関係がなく、並列度が高い課題である -- 要素数 2^27 -- CPU での実行時は要素数 2^27 を 2^6 個に分割して Task を生成する -- GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で kernel を実行 - -## Twice の結果 -- GPU は CPU との通信時間を含めた時間、 GPU(kernel only) は kernel のみの実行時間を示している -- 1 CPU と 32 CPU では約27.1倍の速度向上が見られた -- GPU は通信時間を含めると 8 CPU の約1.25倍、 kernel のみの実行では 32 CPU の約7.22倍になった -- 通信時間がオーバーヘッドになっている +## consoleread +- console への入力を読み込み、待っている間スリープする +```c +int consoleread (struct inode *ip, char *dst, int n) +{ + uint target; + int c; + iunlock(ip); + target = n; + acquire(&input.lock); - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Processor	Time(ms)
1 CPU	1181.215
2 CPUs	627.914
4 CPUs	324.059
8 CPUs	159.932
16 CPUs	85.518
32 CPUs	43.496
GPU	127.018
GPU(kernel only)	6.018

- -## BitonicSort -- 並列処理向けのソートアルゴリズム -- 決まった2点間の要素の入れ替えを並列に行うことでソーティングを進めていく -- 要素数 2^24 -- CPU での実行時は要素数 2^24 を 2^6 個に分割して Task を生成する -- GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で kernel を実行 + while (n > 0) { + while (input.r == input.w) { + if (proc->killed) { + release(&input.lock); + ilock(ip); + return -1; + } + sleep(&input.r, &input.lock); + } + c = input.buf[input.r++ % INPUT_BUF]; + if (c == C('D')) { // EOF + if (n < target) { + input.r--; + } + break; + } + *dst++ = c; + --n; + if (c == '\n') { + break; + } + } + release(&input.lock); + ilock(ip); + return target - n; +} +``` -## BitonicSort の結果 -- 1 CPU と 32 CPU で約22.12倍の速度向上 -- GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった -- 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった +## cbc\_consoleread - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Processor	Time(s)
1 CPU	41.416
2 CPUs	23.340
4 CPUs	11.952
8 CPUs	6.320
16 CPUs	3.336
32 CPUs	1.872
GPU	5.420
GPU(kernel only)	0.163

- - -## OpenMP との比較 -- OpenMP は C、 C++ のプログラムにアノテーションを付けることで並列化を行う -- データの待ち合わせ処理はバリア等のアノテーションで記述する -- Gears OS は並列処理を par goto 構文、データの待ち合わせを Code Gear と Input/Ouput Data Gear の関係で行う - -``` c -#pragma omp parallel for -for(int i = 0; i < length; i++) { - a[i] = a[i] * 2; +```c +__code cbc_consoleread (struct inode *ip, char *dst, int n, __code(*next)(int ret)) +{ + uint target; + + iunlock(ip); + + target = n; + acquire(&input.lock); + + if (n > 0) { + proc->cbc_arg.cbc_console_arg.n = n; + proc->cbc_arg.cbc_console_arg.target = target; + proc->cbc_arg.cbc_console_arg.dst = dst; + proc->cbc_arg.cbc_console_arg.ip = ip; + proc->cbc_arg.cbc_console_arg.next = next; + goto cbc_consoleread2(); + } + goto cbc_consoleread1(); } ``` -## Go 言語との比較 -- Go 言語は並列実行を **go funciton(argv)** の構文で行う。この実行を goroutine と呼ぶ -- goroutine 間のデータの待ち合わせはチャネルというデータ構造で行う -- チャネルでのデータの送受信は **<-** を使用して行うため、簡潔に書くことが出来る -- しかし、チャネルは複数の goroutine で共有されるため、データの送信元が推測しづらい -- Gears OS では goroutine は par goto 文とほぼ同等に扱える -- par goto 文では書き出す Data Gear を指定するため、書き出し元が推測しやすい - -``` go -c := make(chan []int) -for i :=0; i < *split; i++ { - // call goroutine - go twice(list, prefix, i, c); +## cbc\_consoleread +```c +__code cbc_consoleread2 () +{ + struct inode *ip = proc->cbc_arg.cbc_console_arg.ip; + __code(*next)(int ret) = proc->cbc_arg.cbc_console_arg.next; + if (input.r == input.w) { + if (proc->killed) { + release(&input.lock); + ilock(ip); + goto next(-1); + } + goto cbc_sleep(&input.r, &input.lock, cbc_consoleread2); + } + goto cbc_consoleread1(); } -func twice(list []int, prefix int, index int, c chan []int) { - for i := 0; i < prefix; i++ { - list[prefix*index+i] = list[prefix*index+i] * 2; +__code cbc_consoleread1 () +{ + int cont = 1; + int n = proc->cbc_arg.cbc_console_arg.n; + int target = proc->cbc_arg.cbc_console_arg.target; + char* dst = proc->cbc_arg.cbc_console_arg.dst; + struct inode *ip = proc->cbc_arg.cbc_console_arg.ip; + __code(*next)(int ret) = proc->cbc_arg.cbc_console_arg.next; + + int c = input.buf[input.r++ % INPUT_BUF]; + + if (c == C('D')) { // EOF + if (n < target) { + input.r--; + } + cont = 0; + } + + *dst++ = c; + --n; + if (c == '\n') { + cont = 0; + } + if (cont == 1) { + if (n > 0) { + proc->cbc_arg.cbc_console_arg.n = n; + proc->cbc_arg.cbc_console_arg.target = target; + proc->cbc_arg.cbc_console_arg.dst = dst; + proc->cbc_arg.cbc_console_arg.ip = ip; + proc->cbc_arg.cbc_console_arg.next = next; + goto cbc_sleep(&input.r, &input.lock, cbc_consoleread2); + } } - c <- list + release(&input.lock); + ilock(ip); + goto next(target - n); +} +``` +## sleep +- プロセスをスリープ状態にしてスケジューラーへ引き渡す。 +```c +void sleep(void *chan, struct spinlock *lk) +{ + if(proc == 0) { + panic("sleep"); + } + + if(lk == 0) { + panic("sleep without lk"); + } + + if(lk != &ptable.lock){ //DOC: sleeplock0 + acquire(&ptable.lock); //DOC: sleeplock1 + release(lk); + } + + proc->chan = chan; + proc->state = SLEEPING; + sched(); + + proc->chan = 0; + + if(lk != &ptable.lock){ //DOC: sleeplock2 + release(&ptable.lock); + acquire(lk); + } } ``` -## まとめ -- Gears OS の並列処理機構を Interface を用いて実装を行った -- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった -- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった -- 2つの例題である程度の台数効果が出ることを確認した +## cbc\_sleep +```c +__code cbc_sleep1() +{ + struct spinlock *lk = proc->lk; + proc->chan = 0; + + if(lk != &ptable.lock){ //DOC: sleeplock2 + release(&ptable.lock); + acquire(lk); + } + goto proc->cbc_next(); +} -## 今後の課題 -- Gears OS の並列処理の信頼性の保証、チューニングを行う -- Gears OS では証明とモデル検査をメタレベルで実現することで信頼性を保証する - - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある - - モデル検査は CbC で記述されたモデル検査器である akasha を使用して行う。モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う -- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった - - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う - -## 今後の課題 -- OpenMP、 Go 言語で Twice を実装し、 Gears OS の性能比較を行った -- その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 - - par goto 文を使用する度に Context を生成するため、ある程度の時間がかかってしまう - - モデル検査で par goto で実行する Code Gear のフローを解析し、処理が軽い場合は Context を生成せずに関数呼出しを行う等の最適化が必要 - -

+__code cbc_sleep(void *chan, struct spinlock *lk, __code(*next1)()) +{ + if(proc == 0) { + panic("sleep"); + } + + if(lk == 0) { + panic("sleep without lk"); + } + + if(lk != &ptable.lock){ //DOC: sleeplock0 + acquire(&ptable.lock); //DOC: sleeplock1 + release(lk); + } + proc->chan = chan; + proc->state = SLEEPING; + proc->lk = lk; + proc->cbc_next = next1; + + goto cbc_sched(cbc_sleep1); +} +``` -## データ並列 -- data並列はあるデータ構造がサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法 -- Gears OS ではdata 並列は par goto 構文に**iterate(分割数)**を追加することで可能になる -- データ並列の Task は CPU で実行する際は Task にインデックスを付与して分割数分コピーして実行する -- CUDA の場合は Kernel を実行する際にパラメーターとして分割数を渡す - -## Task 間の同期処理 -- Context 間での同期処理を行うために Semaphore を実装 -- Semaphore はContext 停止用の待ち Queue を持つ - -

+## sched +- レジスタの値を切り替えて、スケジューラーへと戻る +- 再開時は swtch の下から再開する。 +```c +void sched(void) +{ + int intena; + + if(!holding(&ptable.lock)) { + panic("sched ptable.lock"); + } + + if(cpu->ncli != 1) { + panic("sched locks"); + } + + if(proc->state == RUNNING) { + panic("sched running"); + } + + if(int_enabled ()) { + panic("sched interruptible"); + } + + intena = cpu->intena; + swtch(&proc->context, cpu->scheduler); + cpu->intena = intena; +} +``` -

OS の拡張性と信頼性の両立

メタ計算

メタ計算とは

Continuation based C (CbC)

Gears OS

Gears でのメタ計算

CbC の継続

Gears でのメタ計算

Meta Gear

Data Gear の表現

Context

Gears でのメタ計算

Gears でのメタ計算

stub Code Gear

Meta Gear

Interface

Context

Interface の定義

Context

Interface の定義

Context

Interface のインスタンスの生成

stub Code Gear

Interface の使い方

stub Code Gear

メタレベルでの Interface の呼び出しの詳細

stub Code Gear

Interface での stub Code Gear

goto meta

並列処理の構成

Interface

Task

TaskManger

Interface の定義

Worker

Synchronized Queue

Interface の定義

依存関係の解決

並列構文

par goto 構文

CUDA への対応

Interface の実装の記述

Interface の操作の呼び出し

CUDAWorker

Interface の操作の呼び出し

CUDAExecutor

Interface の操作の呼び出し

Interface における stub Code Gear

CUDABuffer

CUDA での呼び出し

xv6 の CbC 書き換え

Gears OS の評価

Twice

xv6 の書き換えの方針

システムコールの書き換え

Twice の結果

syscall関数

BitonicSort

sys_read 関数

BitonicSort の結果

cbc_read

OpenMP との比較

Go 言語との比較

fileread

まとめ

cbc_fileread

今後の課題

今後の課題

readi

データ並列

Task 間の同期処理

cbc_readi