マルチスレッドを意識しないマルチスレッド・ライブラリ「Intel Concurent Collections」がおもしろい

　たくさんのstepがわらわら動くサンプルを書いてみました。おなじみソートです。tagとして2つのintの組：lo,hiをstepに与え"配列のlo以上hi未満の範囲をソート"します。stepでの処理は:

• loとhiの差（＝範囲内にある要素の数）がそんなに大きくなければ単純選択法でソートする
• さもなくば、範囲[lo,hi)を前半部[lo,mid)と後半部[mid,hi)に分割し、それぞれの範囲をソートする。

　としましょう。このstepは新たな2つのstepに着火しますから、着火されたstepが倍々ゲームで増殖します。

list07

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <utility>
#include <cnc/cnc.h>

using namespace std;

struct my_context; // forward decl.

struct my_step {
  int execute(const pair<int,int>& range, my_context& ctx) const;
};

struct my_context : public CnC::context<my_context> {
  CnC::step_collection<my_step>      steps;
  CnC::tag_collection<pair<int,int>> tags;
  int                                limit; // これを下回ったら選択ソート
  vector<int>                        data;

  my_context() : steps(*this), tags(*this) {
    tags.prescribes(steps, *this); // tags は steps に 指示する
  }

  // 単純選択ソートで data[first..last-1] をソートする
  void selection_sort(int first, int last) {
    for ( ; first < last; ++first ) {
      iter_swap(data.begin()+first, min_element(data.begin()+first, data.begin()+last));
    }
  }
};

// rangeが示す範囲のデータをソートする
int my_step::execute(const pair<int,int>& range, my_context& ctx) const {
  int lo = range.first;
  int hi = range.second;

  if ( (hi - lo) < ctx.limit ) {
    // 小さな範囲に対しては選択ソートを行う
    ctx.selection_sort(lo,hi);
  } else {
    // 範囲内のデータを前半/後半に分け、
    int mid = (lo + hi) / 2;
    nth_element(ctx.data.begin()+lo, ctx.data.begin()+mid, ctx.data.begin()+hi);
    // それぞれに対しソートする
    ctx.tags.put(make_pair(lo, mid)); // 前半部に着火
    ctx.tags.put(make_pair(mid, hi)); // 後半部に着火
  }
  return CnC::CNC_Success;
}

int main() {
  const int N = 1000; // データ数
  my_context ctx;
  ctx.limit = 20;

  // N個のデータを用意する
  ctx.data.assign(N, 0);
  iota(ctx.data.begin(), ctx.data.end(), 0);
  random_shuffle(ctx.data.begin(), ctx.data.end());

  ctx.tags.put(make_pair(0,N)); // ソート開始!
  ctx.wait(); // 終わるのを待って

  // 結果を確認する
  if ( is_sorted(ctx.data.begin(), ctx.data.end()) ) {
    cout << "OK!" << endl;
  }
}

　最後にもう一つ、ちょいとややこしい行列演算。J行K列の行列AとK行L列の行列Bとの積:J行L列の行列Cを求めます。

　C[x][y] は Aのx行 と Bのy列 の内積で求まりますから、

　"Aのr行 と Bのc列 の内積を求める" step と"求めた結果を C[r][c]にセットする" step とをつなぎ、それを JxL回着火して積を求めます。