Go to Qiita Advent Calendar 2024 Top
LoginSignup
13
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@MitsutakaTakeda

HPXの紹介

Last updated at Posted at 2015-12-04

前振

この記事はC++ Advent Calendar 2015の4日目の記事です。

前日はRiyaaaa_aさんでした。

本当はコチラのScala記事の移植版をC++でやりたかったのですが、まあ、C++まだfutureがmonadicじゃないし、(DB.futureLocalTx)の1行に集約されているトランザクショナルな処理をC++で0から実装するの面倒だしという言い訳で、まずはfutureをmonadicにするためのライブラリHPXを紹介してお茶を濁したいと思います。

HPX(High Performance ParallelX)とは

HPXとは"A general purpose C++ runtime system for parallel and distributed applications of any scale"とプロジェクト・ページにあるように、green threads、高レベルConncurency/Parallel API(std::futureの拡張)、remote procedure callを提供する並列・並行・分散アプリケーションの実行環境&ライブラリです。HPXは99.9% C++11と数十行のアセンブリで実装されており、Windows, Linux, Mac OS X, BlueGene/Q, Intel(R) Xeon/Phiと幅広い環境をサポートしています。また、開発は知る人ぞ知るHartmut Kaiserがリードしており、将来が非常に楽しみです。

http://stellar-group.org/libraries/hpx/
https://github.com/STEllAR-GROUP/hpx

注目するべきHPXの特徴として、C++標準への準拠の高さがあります。上記の通り実装はC++11に準拠している上、HPXのIFはC++標準に可能な限り併せてあります。また、Standard Template Libraryの並列版アルゴリズムを提供しています。C++17はBjarne Stroustrupの意向もあり、高レベルなConcurrency/Parallelモデルを導入しようとしています。HPXで得られた知見は標準に提案されており、HPXのIFはC++17で導入されるものに近くなる蓋然性が高いです。C++17の機能を少し早く体験してみたい方には絶好のライブラリとなっています。

この記事ではHPXの導入方法とConcurrent/Parallel部分について紹介したいと思います。

How to install HPX

HPXをビルドするには、BoostとPortable Hardware Localityが最低でも必要です。tcmallocがないと性能がでないと警告がでるので、Google Perftoolsも入れます。またHPXはビルド・システムにcmakeを使用しているのでcmakeもインストールしましょう。

Build Prerequisites@HPX Manual

Ubuntuでは以下のコマンドでインストール。C++使いの方はBoostはインストール済みだと思うのでBoostのインストール方法は割愛します。

prerequisite.sh
sudo apt-get install hwloc
sudo apt-get install libgoogle-perftools-dev
wget https://cmake.org/files/v3.4/cmake-3.4.0-Linux-x86_64.tar.gz -O - | tar -xz
# cmake-3.4.0-Linux-x86_64/binのコマンドへパスを通す。

HPXをgithubからクローンしてビルド&インストールします。

build_hpx.sh
git clone https://github.com/STEllAR-GROUP/hpx.git
mkdir hpx_build && pushd hpx_build
cmake -DBOOST_ROOT=/your_boost_directory -DCMAKE_INSTALL_PREFIX=/where_to_install_hpx ../hpx
cmake --build ./ --target install

your_boost_directoryはシステム上にあるBoostのルート(include/libディレクトリの親ディレクトリ)、を指定します。where_to_install_hpxはHPXをインストールしたいディレクトリです。このディレクトリの下にHPXのincludeやlibディレクトリが配置されます。

How to build with HPX

HPXを使用したアプリケーションはcmakeを利用してビルドします。

アプリケーションのCMakeLists.txtにて、find_packageでHPXパッケージを検索後、HPXが提供しているcmakeコマンドを利用してビルド・ターゲットの定義を行います。

CMakeLists.txt
find_package(HPX)

add_hpx_executable(my_application
  SOURCES my_app.cpp
  COMPONENT_DEPENDENCIES iostreams
  )

上記のようにCMakeLists.txtを定義したあと、以下のコマンドでビルド用のプロジェクト(Linuxではmakeファイル・ベースのプロジェクト)を生成し、アプリケーションをビルドします。

build_hpx_application.sh
mkdir build_my_app && pushd build_my_app
cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DHPX_DIR=/where_HPX_is_installed -DCMAKE_BUILD_TYPE=Release /path_to_source_directory
cmake --build ./

ここでwhere_HPX_is_installedはHPXがインストールされているディレクトリで、前述の方法でHPXをインストールした場合は、CMAKE_INSTALL_PREFIXに指定したディレクトリとなります。path_to_source_directoryはCMakeLists.txtを含んだアプリケーションのプロジェクト・ルート・ディレクトリです。

[[http://stellar-group.github.io/hpx/docs/html/hpx/manual/build_system/using_hpx/using_hpx_cmake.html][Using HPX with CMake based projects]]

HPXを利用したプログラム その1(std::future extension)

ここからはHPXを利用したアプリケーションのコードを見ていきます。

次のコードはquick_sortでvectorをsortしてsortに掛った時間を表示するプログラムです。HPX実行環境上で実行されていますが、同期的なコードです。main関数ではboost::program_optionsへvectorのサイズを指定するコマンド・ライン・パラメータ"size-of-vector"を追加した後、hpx::initを呼びHPXの実行環境を初期化しています。

quick_sort.cpp
#include <hpx/hpx_init.hpp>
#include <hpx/components/iostreams/standard_streams.hpp>
#include <algorithm>

template <typename RandomAccessIterator>
void
quick_sort(RandomAccessIterator first, RandomAccessIterator limit)
{
    const auto size = std::distance(first, limit);
    if(size < 2){
        return;
    }

    const auto pivot = first + size/2;
    std::nth_element(first, pivot, limit);
    quick_sort(first, pivot);
    quick_sort(pivot + 1, limit);
}

int main(int argc, char *argv[]) {
    boost::program_options::options_description
       desc_commandline("Usage: " HPX_APPLICATION_STRING " [options]");

    desc_commandline.add_options()
        ( "size-of-vector",
          boost::program_options::value<boost::uint64_t>()->default_value(10),
          "size of the vector for the quick_sort function");

    return hpx::init(desc_commandline, argc, argv);
}

int hpx_main(boost::program_options::variables_map& vm){
    boost::uint64_t n = vm["size-of-vector"].as<boost::uint64_t>();

    {
        std::vector<int> nums(n);
        std::iota(nums.begin(), nums.end(), 0);
        std::random_shuffle(nums.begin(), nums.end());

        hpx::util::high_resolution_timer t;

        quick_sort(nums.begin(), nums.end());

        char const* fmt = "sort %1% elements with quick_sort \n elapsed time: %2% [s]\n";
        std::cout << (boost::format(fmt) % n % t.elapsed());
    }

    return hpx::finalize(); // Handles HPX shutdown
}

HPX実行環境はコマンド・ライン引数をパース後、hpx_mainを呼びます。hpx_mainの中でアプリケーションは
コマンド・ライン引数にアクセスやHPX APIを使用することができます。hpx::finalizeを呼び出した時点で、
スケジュールされているタスクが完了後アプリケーションは終了します。

以下、10,000,000要素のvectorに対してコードを10回実行した結果です。環境は、
CPU Intel(R) Core(TM) i5-4430 CPU @ 3.00GHz(4 Threads)、メモリ32GB、Ubuntu 14.04 64bitです。

in sec
1.13741
1.14225
1.13889
1.13946
1.14262
1.13301
1.13663
1.13245
1.12904
1.13021

次に、HPXが提供しているstd::futureの拡張であるhpx::futureでquick_sortの中を部分を非同期に実行してみます。

quick_sort_concurrent.cpp
#include <hpx/hpx_init.hpp>
#include <hpx/components/iostreams/standard_streams.hpp>
#include <hpx/async.hpp>
#include <hpx/lcos/wait_all.hpp>
#include <hpx/lcos/when_all.hpp>

template <typename RandomAccessIterator>
void
quick_sort(RandomAccessIterator first, RandomAccessIterator limit)
{
    const auto size = std::distance(first, limit);
    if(size < 1000){
        std::sort(first,limit);
        return;
    }

    const auto pivot = first + size/2;
    hpx::future<void> nth = hpx::async([pivot, first, limit]{
            std::nth_element(first, pivot, limit);
        });

    hpx::future<hpx::util::tuple<hpx::future<void>, hpx::future<void> > > low_and_high
        = nth.then([=](hpx::future<void>) {
                return hpx::when_all(
                    hpx::async([=]{
                            quick_sort(first, pivot);
                        }),
                    hpx::async([=]{
                            quick_sort(pivot + 1, limit);
                        }));
        });
    hpx::wait_all(low_and_high);
}

int main(int argc, char *argv[]) {
    boost::program_options::options_description
       desc_commandline("Usage: " HPX_APPLICATION_STRING " [options]");

    desc_commandline.add_options()
        ( "size-of-vector",
          boost::program_options::value<boost::uint64_t>()->default_value(10),
          "size of the vector for the quick_sort function");

    return hpx::init(desc_commandline, argc, argv);
}

int hpx_main(boost::program_options::variables_map& vm){
    boost::uint64_t n = vm["size-of-vector"].as<boost::uint64_t>();

    {
        std::vector<int> nums(n);
        std::iota(nums.begin(), nums.end(), 0);
        std::random_shuffle(nums.begin(), nums.end());

        hpx::util::high_resolution_timer t;

        quick_sort(nums.begin(), nums.end());

        char const* fmt = "sort %1% elements with quick_sort \n elapsed time: %2% [s]\n";
        std::cout << (boost::format(fmt) % n % t.elapsed());
    }

    return hpx::finalize(); // Handles HPX shutdown
}

まず同期版と違いquick_sortの基底部の判定条件を(size < 1000)にしています。これは、非同期版ではquick_sortの呼び出しの度にthreadが作成されるため、size < 2 ではthreadが過剰に作られstackを食い潰すためです。これを避けるためsize < 1000で非同期にsortをするようにしています。

次に実際に非同期化しているsort部分ですが、まずhpx::asyncでstd::nth_elementを非同期に実行しています。hpx::asyncの戻り値の型はhpx::futureです。その後、hpx::asyncの戻り値に対してthenメンバ関数で継続を渡しています。継続は、継続をとりつける対象のfuture(thenを呼び出す対象のfuture)を引数に取るCallableです。継続の中では、継続の引数に渡されたfutureに対してgetを呼び出してもブロックされないことが保証されます。このケースではhpx::futureなので 戻り値は使用しないためgetをする必要はありません。継続にfutureの中身ではなくfutureそのものが渡されるのは、継続でエラー処理を行うためです。継続の前の処理が失敗している場合はfutureのgetを呼び出すと例外が投げられます。

今回のコードでは、std::nth_elementが終了した時点で継続が実行されます。この時点で、区間[first,pivot)中の要素は全てpivotが指す要素以下、かつ、(pivot,limit)はpivot以上の要素の区間です。2つの区間は重なりあっていないのでasyncで2つの区間を非同期にsortします。

hpx::when_allは複数のfutureを取り、全futureが準備完了になった時点で準備完了になる新しいfuture(tupleのfuture)を生成します。quick_sort関数自体は同期関数なので、最後にhpx::wait_allで全ての処理が完了するのを待ちます。

このコードを複数スレッドで実行して結果を見てみます。HPXアプリケーションは、コマンド・ラインでHPX実行環境の設定を行うことができます。今回はhpx:threadsで使用するOSスレッドの数を変更しながら性能の違いを比較します。以下の通りOSスレッドの数までは性能が向上することが分ります。

thread数1つの時点ですでに元の同期版より速いのはsize < 1000でstd::sortに投げるようにしたからです。

| thread 1 | thread 2 | thread 3 | thread 4 | thread 5 | thread 6 |
|----------+----------+----------+----------+----------+----------|
| 1.02486 | 0.56766 | 0.42141 | 0.36274 | 0.65654 | 0.89876 |
| 1.04226 | 0.57922 | 0.43653 | 0.36113 | 0.60928 | 0.95430 |
| 1.03334 | 0.57115 | 0.41869 | 0.36951 | 0.60109 | 1.0321 |
| 1.04057 | 0.56761 | 0.44103 | 0.37260 | 0.61818 | 1.035 |
| 1.03897 | 0.58690 | 0.44036 | 0.37122 | 0.64002 | 1.0650 |
| 1.03961 | 0.57346 | 0.44094 | 0.36466 | 0.70506 | 1.0914 |
| 1.04396 | 0.58433 | 0.41883 | 0.3725 | 0.58261 | 0.9674 |
| 1.04145 | 0.56963 | 0.43441 | 0.36596 | 0.73187 | 0.93868 |
| 1.03376 | 0.60703 | 0.43523 | 0.36844 | 0.60366 | 1.0285 |
| 1.036 | 0.57827 | 0.42404 | 0.37641 | 0.77232 | 1.0330 |

HPXを利用したプログラム その2(parallel algorithm)

"HPXとは"の部分で記載した通りHPXはparallel版のSTL algorithmを提供しています。

通常のSTL algorithmとの違いは、第1引数にexecution policyを取ることです。execution poilcyはその名前の通りalgorithmがどのように実行されるか(並列に関数呼出しを行えるか、GPU/Thread/SIMDを使用するか等)を決定するポリシーです。

次のプログラムではparallel版のSTL sortを使用しています。

parallel_sort.cpp
#include <hpx/hpx_init.hpp>
#include <hpx/components/iostreams/standard_streams.hpp>
#include <hpx/include/parallel_sort.hpp>
#include <hpx/parallel/execution_policy.hpp>
#include <hpx/lcos/wait_all.hpp>

#include <cassert>

int main(int argc, char *argv[]) {
    boost::program_options::options_description
        desc_commandline("Usage: " HPX_APPLICATION_STRING " [options]");

    desc_commandline.add_options()
        ( "size-of-vector",
          boost::program_options::value<boost::uint64_t>()->default_value(10),
          "size of the vector for the quick_sort function");

    return hpx::init(desc_commandline, argc, argv);
}

int hpx_main(boost::program_options::variables_map& vm){
    boost::uint64_t n = vm["size-of-vector"].as<boost::uint64_t>();

    {
        std::vector<int> nums(n);
        std::iota(nums.begin(), nums.end(), 0);
        std::random_shuffle(nums.begin(), nums.end());

        hpx::util::high_resolution_timer t;

        hpx::wait_all(
            hpx::parallel::sort(
                hpx::parallel::parallel_task_execution_policy{},
                nums.begin(),
                nums.end()
                ));

        char const* fmt = "sort %1% elements with parallel::sort \n elapsed time: %2% [s]\n";
        std::cout << (boost::format(fmt) % n % t.elapsed());
        assert(std::is_sorted(nums.cbegin(), nums.cend()));
    }

    return hpx::finalize(); // Handles HPX shutdown
}

hpx::parallel::sortと名前は標準のsortと同じですが、第1引数にexecution policyであるhpx::parallel_task_execution_policyを指定しています。このPolicyはHPXが提供している並列実行のためのpolicyでalgorithmに並列化を許可しています。並列下を許可しないhpx::sequential_task_execution_policyというポリシーも提供されています。

自作したsort関数と同様に10,000,000要素のベクタをソートした時の結果は以下の通りです。前セクションで手書きした非同期版のquick_sortよりも性能が良いです。

| thread 1 | thread 2 | thread 3 | thread 4 | thread 5 | thread 6 |
|----------+----------+----------+----------+----------+----------|
| 0.80008 | 0.4268 | 0.31206 | 0.25602 | 0.38823 | 0.25974 |
| 0.81694 | 0.42054 | 0.29581 | 0.25796 | 0.24671 | 0.40423 |
| 0.81695 | 0.41996 | 0.29672 | 0.25102 | 0.25073 | 0.41123 |
| 0.81430 | 0.40735 | 0.30884 | 0.24249 | 0.25108 | 0.46951 |
| 0.81337 | 0.42505 | 0.28987 | 0.23891 | 0.24913 | 0.40175 |
| 0.80691 | 0.4172 | 0.30108 | 0.24293 | 0.26371 | 0.38921 |
| 0.80969 | 0.42186 | 0.30851 | 0.25037 | 0.24568 | 0.27229 |
| 0.80518 | 0.42214 | 0.29308 | 0.23448 | 0.26886 | 0.45639 |
| 0.79770 | 0.42739 | 0.29972 | 0.23506 | 0.2510 | 0.29977 |
| 0.80921 | 0.42644 | 0.30017 | 0.23990 | 0.29222 | 0.50994 |

HPXがParallel algorithmに採用しているexecutoin policy(executor)は、並列の実行機構を汎用的に扱うためのIFでHPXは提供していませんが、先日Riyaaaa_aさんが書かれたC++ AMPのようにGPU上で実行するためのexecution policyも提供されるかと思います。同じコードで環境に合せて最適な並行実行機構で動くプログラムも書けるようになるかもしれず夢は広がるばかりです。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4406.pdf
http://stellar-group.org/2015/06/hpx-and-cpp-parallel-algorithms/

最後に

HPXのConcurrent/Parallel部分を少しだけ紹介しました。std::futureの拡張やparallel algorithmなどC++17に入るかと思うと今からワクワクがとまりません。

また今回の記事では触れませんでしたが、HPXは分散コンピューティングの実行環境&分散プログラムを書くためのライブラリでもあります。複数マシンでHPXを実行させてどこまでスケール・アウトするか、またどれだけ分散プログラムが楽になるか試してみるのも面白いかと思います。

もしHPXに興味を持たれたかたは以下のカンファレンスの動画や資料がお勧めです。

  • Plain Threas are the GOTO of todays computing - Hartmut Kaiser - Keynote@Meeting C++ 2014

  • STELLAR GROUP(HPXを開発している組織)の技術ブログ

  • C++17: I See a Monad in Your Future(std::futureの拡張の話。C++ concurrencyの裏にいるHaskellerです)

今回のサンプル・コードはココです。

あと、EmacsのAdvent CalendarでEmacs for C++を書きました。Emacs & C++使いの方はぜひ読んでください。Emacs Advent CalendarとC++ Advent Calendarの担当日を近くに設定しすぎたことだけが悔まれます。。。現在、12/04 10:32PM、締め切りまで1時間ちょっと。

明日はFlast_ROさんです。よろしくお願いします!

13
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
13
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?