Arora's Task Stealing Deque

作成日：2005.11.27

前置き
データ構造
操作
擬似コード
動作
問題点
参考文献
脚注

1. 前置き

マルチプロセッサ上で行う並列処理を行うプログラムが、仕事を均等に N 分割できるものは稀だ。プログラムの処理コストの最大値や平均値を見積もることができても、実際の処理時間や消費メモリはプログラムの実行内容によって大きく変わっていく。そのため各プロセッサに割り当てる負荷(ロード)が均一になるように負荷分散を行うことが重要になる。

負荷分散を行うためには、プログラムをある程度の粒度に分割し、プロセッサ間で担当をやり取りできるようにする。とりあえずプログラムを分割したものをタスクと呼ぶことにしよう。

タスクをやり取りする方法は、大雑把に言って三つある。

マネージャーがいて、どのプロセッサがどのタスクを行うか制御する。
暇なプロセッサが、タスクを多く抱えたプロセッサから盗む(steal)。
忙しいプロセッサが、暇なプロセッサにタスクを押しつける。

プロセッサ間の結合が密な SMP マシンの中では、 2. の タスクスチール(task stealing) が使われることが多い。

Nimar S. Arora の double-ended queue (deque) のアルゴリズム([1]) はこうしたタスクスチールアルゴリズムの一つで、基本的に SMP マシンの中でだけ動作する負荷分散用の同期データ構造だ。 [1] の論文名が示すように、もとはオペレーション・システムのプロセス・スレッドキューの実装のために考え出された。しかし筋がよかっため OS 以外のところでも使われているようだ。

Arora のアルゴリズムの特長・特徴としては

Deque のオーナースレッドと非オーナースレッド(他スレッドと呼ぶことにする)の区別があり、操作が非対称となる。スレッドをプロセッサにバインドして運用することを想定しているので、プロセッサ毎に deque がバインドされている様子をイメージして欲しい。
アトミック命令の使用量を限界(と思われるところ)まで減らしている。 Deque はタスクが2つ以上積んである場合には、プロセッサが自分の deque にタスクを積んだり・出したりする時に ほとんどアトミック命令が不要 になっている。他のプロセッサからタスクをスチールする際には Compare-And-Swap (CAS) 命令を 1 回使うだけ でよい。
Wait-free アルゴリズムである。スピンウェイトもブロックもされない。
オーナースレッドの操作は必ず定数時間内で成功する。
他スレッドの操作は状況に応じて成功と失敗(abort)がある。ただし失敗した場合でも定数時間内に処理が戻ってくる。

SMP 内で動作する task stealing アルゴリズムは、プロセッサとメモリの織り成すハードウェアとの戦いなので、ある程度ハードウェアを想定しないと説明し辛い。以降説明をするにあたっては、一般的な 32-bit RISC プロセッサでかつ sequential memory ordering (*1) を念頭において話を進める。あと擬似コードは C++ 風に記述している。

2. データ構造

Arora's deque は _deq[] は固定長配列となる。この _deq[] のうち、 [_bottom, _age._tag) 番目のインデックスにはデータが格納されている(図1)。

Deque のトップを表すのに Age という構造体を使う。 Age 構造体は、そのプロセッサで不可分に読み書きできるデータサイズでなくてはならない。 32 ビットプロセッサであれあば普通は 32 ビット = 4 バイトになる。 Age 内の top と tag のビットフィールドは、まず top に deque の最大値(SIZE) を格納できる最小限のビット割り当て、残りを tag に割り当てる。

初期状態では、すべての変数は 0 クリアされている。

// deque 本体
Data* _deq[SIZE];

// deque のトップを保持
struct Age {
  int top:16; // SIZE を格納できる最小のビット
  int tag:16; // top と足して 32 ビットとなるように
} _age; 

// deque のボトムを保持
int   _bottom;

図1: _deq と _bottom、_age の関係

3. 操作

Arora の deque は、 deque のオーナースレッドによるデータの挿入と取り出し、他スレッドによるデータの取り出し (スチール) の 3 種類の操作がある。オーナースレッドは常に deque の底からデータを出し入れし(pushBottom, popBottom)、他スレッドは deque のトップからデータをスチール(popTop)していく。

オーナースレッドからしか操作を受けない時は、スタック作法でデータがやり取りされる。

一方、他スレッドが deque からデータをスチールする場合、トップからデータを盗んでいくことになる。いったんデータを取ると「天井が下がった」状態になる。スチールが続くと deque 内のデータのある領域がずるずると下方に引っ張られていくことになる。これを防ぐため deque が空になると初期状態に戻すために _bottom と _age.top が 0 クリアされる。

図2: オペレーションの関係

4. 擬似コード

3つの操作の擬似コードを以下に示す。擬似コード中の Compare-And-Swap(_age, oldAge, newAge) は CAS アトミック命令をあらわしている。「_age 上のメモリの内容が oldAge と一致するなら、その内容を newAge で上書きせよ、不一致ならなにもするな」と言う処理を不可分に行う必要がある。実際にコードに落すにはプロセッサ固有のインラインアセンブラなどを使う必要がある。

void pushBottom(Data* p) {
  int localBot;

  localBot = _bottom;
  _deq[localBot] = p;
  localBot++;
  _bottom = localBot;
}

Data* popBottom() {
  Age oldAge, newAge;
  int localBot;

  localBot = _bottom;
  if (localBot == 0)
    return NULL;
  localBot--;
  _bottom = localBot; // (1) _bottom を書く

  p = _deq[localBot]; // (2) データを読む
  oldAge = _age;      // (3) _age を読む
  if (localBot > oldAge.top)
     return p;

  _bottom = 0;
  newAge.top = 0;
  newAge.tag = oldAge.tag + 1;
  if (localBot == oldAge.top) {
    Compare-And-Swap(_age, oldAge, newAge);
    if (書き換え成功)
      return p;
  }
  _age = newAge;
  return NULL;  
}

Data* popTop() {
  Age oldAge, newAge;
  Data* p;
  int localBot; 

  oldAge = _age;     // (4)
  localBot = _bottom;
  if (localBot <= oldAge.top)
    return NULL;
  p = _deq[oldAge.top];
  newAge = oldAge;
  newAge.top++;
  Compare-And-Swap(_age, oldAge, newAge);
  if (書き換え成功)
    return p;

  return ABORT;
}

5. 動作

何故、これが動作するかというと、

まずオーナースレッドが Deque にデータが一つしかない状態で popBottom() を実行するとリセットが掛かる。そのため他スレッドが popTop() の (4) を通過した後にサスペンドしてその間にリセットが掛かると、リセット前後で _bottom と _age.top が一致する危険性がある。
これを防いでいるのが _age.tag でリセットが行われる度にカウントアップしてゆくのでリセット世代をあらわすことができる。リセット世代が古い popTop() 操作を ABORT できる。
複数の他スレッドが同時に popTop() を呼び出しても処理は逐次化される。 (4) の箇所で _age を読み込んで、 CAS 命令で内容を比較しながら新しい値を書き込むので、同じ _age の値に対して popTop() が成功するのは1スレッドだけだ。
Deque の中にデータが2つ以上残っている場合は、オーナースレッドはアトミック命令なしでデータを取ることができる。これはオーナースレッドがデータを取り出す操作に入った後は、他スレッドオーナーは最後の1個のデータを盗むことはできないためである。
オーナースレッドのデータを取り出す操作がロックオンされるのは、 popBottom の「(1) _bottom を書く」の部分。オーナースレッドはデータを取り出す前に _bottom をデクリメントして書き込んでしまうため、他スレッドが _bottom - _age.top を計算すると deque 上に残ったデータより一つ少なく見える。
このガードされた部分がオーナースレッドの取り分になる。

やはり一番重要なのは _age.tag の扱いで、 _age.top と一緒にロード・ストアできる点が肝になっている。

6. 残る問題点

Arora の task stealing deque は原理的にはいいのだが、いざ実装しようとすると色々検討すべき課題がある。

リセットが起きないと最大数まで使用できない

Deque は固定長配列をベースにしているので最大 SIZE 個のデータを格納できるはずだが、図2 のようにスチールが起きるたびに天井が降りてくるので、もしリセットが起きなければ使用可能な範囲がどんどん減っていくことになる。

解決方法はいくつかある。

Deque をリング・バッファによって実装する。 _deq[SIZE-1] の次が _deq[0] に繋がっているようにみせかける。
SIZE を大きめにとって仮想記憶を使って実メモリを切り貼りする。つまり _deq[] を malloc でとるのではなく、 mmap/munmap を使って仮想記憶の窓として取っておき、 _deq[_bottom] よりも高いアドレスのページと _deq[_age.top] よりも低いアドレスのページからは動的に実メモリを剥ぎ取っておくことにする。

Age.tag のオーバーフロー

Deque の使い方によっては、リセットが何度もかかり _age.tag がオーバーフローする可能性がある。実際にオーバーフローしてしまうと、長い間サスペンドしていた popTop() がオーバーフローして一周してきた _age と一致して誤ったデータのポップが起きる危険性がある。

この問題に対するうまい解決はない。

アーキテクチャ依存だが 32 ビットプロセッサでも 64 ビットロード・ストア命令や 64 ビット CAS 命令を備えたものがあるので、そういアーキテクチャでは Age 構造体を 64 ビットにするのは有効である。

使いどころを考えて使おう。

参考文献

[1]: Nimar S. Arora, Robert D. Blumofe, C. Greg Plaxton. Thread Scheduling for Multiprogrammed Multiprocessors. ACM SPAA (Symposium on Parallel Algorithms and Architectures) '98

脚注

*1: 2002.10.30 の日記や 2004.10.12 の日記を読んでね。

コメントを書き込む