並列シャッフルの考察

C++

C++14後のParallelism TSで提案されている並列アルゴリズムについての考察。

N3850 Working Draft, Technical Specification for C++ Extensions for Parallelism

この提案にはshuffle()の並列版は予定されていないのですが、そのアルゴリズムを入れることは可能なのかと。Boost.Computeを見てみたら、random_shuffle()の実装が、以下のようになっていました。

template<class Iterator>
inline void random_shuffle(Iterator first,
                           Iterator last,
                           command_queue &queue = system::default_queue())
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;

    size_t count = detail::iterator_range_size(first, last);
    if(count == 0){
        return;
    }

    // generate shuffled indices on the host
    std::vector<cl_uint> random_indices(count);
    boost::iota(random_indices, 0);
    std::random_shuffle(random_indices.begin(), random_indices.end());

    // copy random indices to the device
    const context &context = queue.get_context();
    vector<cl_uint> indices(count, context);
    ::boost::compute::copy(random_indices.begin(),
                           random_indices.end(),
                           indices.begin(),
                           queue);

    // make a copy of the values on the device
    vector<value_type> tmp(count, context);
    ::boost::compute::copy(first,
                           last,
                           tmp.begin(),
                           queue);

    // write values to their new locations
    ::boost::compute::scatter(tmp.begin(),
                              tmp.end(),
                              indices.begin(),
                              first,
                              queue);
}

https://github.com/kylelutz/compute/blob/master/include/boost/compute/algorithm/random_shuffle.hpp

以下のような作りになっていました。

  • CPU(メインスレッド)でランダムに並んだインデックスを作っておく
  • デバイス(GPU)で、事前に計算しておいたランダムなインデックスに、並列に並び替えを行う。

なので、乱数生成器は並列に特化したものじゃなくてもよさそうなので、従来のmt19937とかをそのまま並列シャッフルに使えそうです。

では先日のVexCLの並列乱数アルゴリズムは何に使うかというと、おそらくランダムな行列を作るのに使うのでしょう。

参照