title: Gears OS
author: Tatsuki IHA
profile:
lang: Japanese
code-engine: coderay

## 研究目的
- 当研究室では  処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う.
- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。
- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。
- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行を検証をメタ計算として記述することで、 並列処理の信頼性を保証する。

## 今週
- synchornized Queue の修正
- Time interface

## synchornized Queue
- ダミーElement を作る
- dequeue で行う cas はtopの変更

<div style="text-align: center;">
    <img src="./pictures/inqueue.svg" alt="message" width="500">
</div>

- inqueue で行う cas は末尾のnextを変更とlastの変更

<div style="text-align: center;">
    <img src="./pictures/dequeue.svg" alt="message" width="500">
</div>

## synchornized Queue
- inqueue では2回CAS が必要なため CAS の間で構造が壊れる可能性がある
- なので, inqueue では末尾の要素の next のみを確実にCASする
- last のCAS は inqueue と dequeue 両方で行う

``` c
__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
    Element* element = new Element();
    element->data = data;
    element->next = NULL;
    Element* last = queue->last;
    Element* nextElement = last->next;
    if (last != queue->last) {
        goto meta(context, C_putSynchronizedQueue);
    }
    if (nextElement == NULL) {
        if (__sync_bool_compare_and_swap(&last->next, nextElement, element)) {
            __sync_bool_compare_and_swap(&queue->last, last, element);
            goto next(...);
        }
    } else {
        // nextElement が Null 出ない場合, last を nextElement に cas する
        __sync_bool_compare_and_swap(&queue->last, last, nextElement);
    }
    goto meta(context, C_putSynchronizedQueue);
}
```

```c
__code takeSynchronizedQueue(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) {
    struct Element* top = queue->top;
    struct Element* last = queue->last;
    struct Element* nextElement = top->next;
    if (top != queue->top) {
        goto meta(context, C_takeSynchronizedQueue);
    }
    if (top == last) {
        if (nextElement != NULL) {
            // nextElement が Null 出ない場合, last を nextElement に cas する
          __sync_bool_compare_and_swap(&queue->last, last, nextElement);
        }
    } else {
        if (__sync_bool_compare_and_swap(&queue->top, top, nextElement)) {
            data = nextElement->data;
            goto next(data, ...);
        }
    }
    goto meta(context, C_takeSynchronizedQueue);
}
```

## Time interface
- 前に実行時間を図るために使っていた CodeGear をinterface化しました

``` c
typedef struct Time<Impl>{
        union Data* time;
        __code start(Impl* time, __code next(...));
        __code end(Impl* time, __code next(...));
        __code next(...);
} Queue;

```

``` c
__code startTime(struct TimeImpl* time, __code next(...)) {
    struct timeval tv;
    gettimeofday(&tv, NULL);

    time->time = tv.tv_sec + (double)tv.tv_usec*1e-6;

    goto next(...);
}

__code endTime(struct TimeImpl* time, __code next(...)) {
    struct timeval tv;
    gettimeofday(&tv, NULL);

    printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time);

    goto next(...);
}
```

## Time interface
- 試しに twice を測定しました
- 測った範囲はTask の生成から, TaskManager の shutdown(pthread_join) まで
- 環境 firefly
- 要素数: 10^9
- タスク数: 1000
- 1タスク辺りの処理量: 10^6

<table  border="1" align='center' width='50%'>
  <tbody>
    <tr>
      <td style="text-align: center;">Number of Processors</td>
      <td style="text-align: center;">Time(ms)</td>
    </tr>
    <tr>
      <td style="text-align: center;">1 CPU</td>
      <td style="text-align: right;">9322</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">4734</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">2674</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">1408</td>
    </tr>
    <tr>
      <td style="text-align: center;">12 CPUs</td>
      <td style="text-align: right;">902</td>
    </tr>
  </tbody>
</table>

## 来週の予定
- bitonic sort を並列化
- CAS の部分をmetaに切り分け