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 の並列処理機構の実装を行う。また、並列処理の検証をメタ計算として記述することで、 並列処理の信頼性を保証する。

## 今週
- bitonicSort をGears上で動かす


## index Iterator
- Iterateなtaskにindexをもたせる
- taskの情報をcopyする際に新しく Integerのdata Gear を生成し, それを input Data Gear にする

``` c
struct Context* createOneDimIterateTask(struct Context* task, int x) {
    struct Context* task1 = NEW(struct Context);
    initContext(task1);
    task1->taskManager = task->taskManager;
    task1->next     = task->next;
    task1->iterate  = 1;
    task1->iterator = task->iterator;
    task1->idgCount = task->idgCount;
    task1->idg      = task->idg;
    task1->maxIdg   = task->maxIdg;
    for(int i = task1->idg; i < task1->maxIdg; i++) {
        task1->data[i] = task->data[i];
    }

    // create index data gear and register input data to iterate task
    struct Integer* dataX = &ALLOCATE_DATA_GEAR(task1, Integer)->Integer;
    dataX->value = x;
    task1->data[task1->maxIdg++] = (union Data*)dataX;

    task1->odg      = task->odg + 1;
    task1->maxOdg   = task->maxOdg + 1;
    for (int i = task1->odg; i < task1->maxOdg; i++) {
        task1->data[i] = task->data[i-1];
    }

    return task1;
}
```

## bitonicSort 
- Cerium で使っていた GPU 向けの例題を実装

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

- 並列実行されるtask は swap

``` c
__code bitonicSwap(struct SortArray* inputArray, struct Integer* block, struct Integer* first, struct Integer* i, struct LoopCounter* loopCounter, __code next(struct SortArray* output, ...)) {
    if (loopCounter->i < inputArray->prefix) {
        int index = loopCounter->i + i->value * inputArray->prefix;
        int position = index/block->value;
        int index1 = index+block->value*position;
        int index2 = (first->value == 1)? ((block->value<<1)*(position+1))-(index1%block->value)-1 : index1+block->value;
        struct Integer** array = inputArray->array;
        if (array[index2]->value < array[index1]->value) {
            struct Integer *tmp = array[index1];
            array[index1] = array[index2];
            array[index2] = tmp;
        }
        loopCounter->i++;
        goto meta(context, C_bitonicSwap);
    }
    loopCounter->i = 0;
    output->array = inputArray->array;
    goto meta(context, next);
}
```

## bitonicSort 実測
- 最初は1回の swap で 1 Task にしていた
- しかし, swap は処理的には軽い Task なので, Workerの一連の処理(Get task から Data Gear の書き出しまで)のほうが長くなってしまい, CPU を増やすと逆に遅くなった
- なので, ある程度の大きさの範囲のswap を 1Task にして実測した
    - 実行環境: firefly
    - core: 12
    - length: 2^20
    - Task数: 2^4

<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;">7986</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">3993</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">2142</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">1204</td>
    </tr>
    <tr>
      <td style="text-align: center;">12 CPUs</td>
      <td style="text-align: right;">1078</td>
    </tr>
  </tbody>
</table>