前回の複利計算。お気づきとは存じますが実はちっとも並列処理やってません。
n-1番step が完了(n-1番itemを出力)するまで n番step は出番がなくて居眠りしてますからね。
もちっとマシな、並列処理をちゃんとやるサンプルをこさえました。毎度おなじみ"ソート"です。
戦術はこんなかんじ:
- "範囲[lo,hi) をソートする"
- 範囲がそこそこ小さいときはフツーに選択ソートを行う
- さもなくば、範囲を 前半部[lo,mid) と 後半部[mid,hi) とに分け、
- "範囲[lo,mid) をソートする"
- "範囲[mid,hi) をソートする"
ひとつのstepが新たな2つのstepに着火します。
この場合step数が
わらわら増えますけど、そいつらの管理/制御は CnC任せ、
動かせるスレッド数に合わせて善きに計らってくれます。
/*
* Intel Concurrent Collections (CnC)
* ソート
*/
#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 に 指示する
}
void selection_sort(int first, int last) {
while ( first < last ) {
iter_swap(data.begin()+first, min_element(data.begin()+first, data.begin()+last));
++first;
}
}
};
// rangeが示す範囲のデータをソートする
int my_step::execute(const pair<int,int>& range, my_context& ctx) const {
int lo = range.first;
int hi = range.second;
#ifdef _DEBUG
static int steps = 0;
cout << ++steps << '[' << lo << ',' << hi << ")\n";
#endif
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;
}
}