OpenMP による C++ コードの並列化

Abstract

　並列化の方針には，1) １タスクあたりの実行時間を削減する方針 (ストロング・スケーリング [1]) と，2) １タスクの実行時間はそのままだが，多数のタスクでも１タスクの時と同じ実行時間で処理する方針 (ウィーク・スケーリング [1]) の 2 種類がある．OpenMP は「OpenMP が使用できない環境では無視されるディレクティブ [2]」を用いて，for 文単位で並列化を行うため，ストロング・スケーリングに向いているが，実際には，並列化をタスク単位に調整すれば，ウェーク・スケーリングに利用できる．
　並列化を行う場合に，まず思い浮かべるのは，スレッドを生成しての並列化である．C++11 からは std::thread が標準化されているため，Windows か Linux かを意識せずに並列化できる．しかしながら，単純にタスクをスレッド数で割って処理させると，実行時間の不均一性から，処理の後半でプロセッサに空きができるなど問題がある．プロセッサを遊ばせないためには，タスクを一度スレッドプールに集約し，スレッドプールから，各 CPU に処理を振る必要がある．このような煩雑な処理の実装は，非常に骨の折れる作業である．このような状況に際しても，OpenMP は，ディレクティブ 1 行で並列化され，schedule(guided) オプション１つでスレッドプーロを生成する．
　実際に並列化が必要とされる状況について，例えば，多量のデータを扱う場合，CSV 等からタスクの一覧を読み込み，タスクごとに処理することは多い．これは，アムダールの法則 [3] を考えた場合，処理の単位が大きく並列化不能な箇所が少ないため，並列度を上げて実行時間を削減し易い．また，実装に際しても，大きな単位でのみ並列化の面倒を見ればよいため，実装の負担が少ない．
　本投稿では，OpenMP の簡単な実装例／実行例を示した後，多数のグラフプロットを必要とする GIF 動画の生成について，OpenMP を用いた並列化を行う．

A single header file template container class of pseudo 2 dimensions row-major and column-major matrix

C++ における行列コンテナ sstd::mat_c<T>/sstd::mat_r<T> の提案

Abstract

　C++ において，画像処理や線形代数演算を行う場合，動的確保された固定長 2 次元配列クラスが用いられる．一般に，画像では，行方向にデータが格納されているため，row-major (行優先) の配列が用いられる．また，数値行列では，固有値計算における固有ベクトルなど，必要な計算結果が列方向に現れるため，column-major (列優先) の配列が用いられる．例えば，画像処理ライブラリである OpenCV の cv::Mat クラスは row-major として，線形代数演算ライブラリである Eigen の Matrix クラスは column-major として※1，それぞれ設計されている．また，可変長 2 次元配列を動的確保する場合，std::vector<std::vector<T>> が用いられる．これは，要素の追加や削除が発生する場合に有効である．
　このように，C++ において 2 次元配列を利用する場合は，用途に応じて型を使い分けることが望ましい．しかし，実態として，OpenCV や Eigen を用いない場合は，殆ど std::vector<std::vector<T>> が用いられている．これは，現状の STL が標準的な行列コンテナとして std::matrix<T> を提供しておらず，また，代替クラスの設計にはコストが掛かることに起因する．基本的に，std::vector<std::vector<T>> は row-major であるため，column-major のデータを扱うには不向きである．加えて，各行ベクトルは独立してメモリ確保されるため※2，メモリアドレスは不連続となる．これらは，キャッシュミスを誘発する．更に，例え固定長であっても，std::vector<T> は，現在確保しているメモリ長と挿入されている要素数を保持するため，余分にメモリを消費する．これらの問題を解消するため，本投稿では，標準的な行列コンテナとして，sstd::mat_r<T> (row-major: r) と sstd::mat_c<T> (column-major: c) を提案する．

※1. Eigen は，行列サイズが小さい場合，静的確保を用いる ^[1]．
※2. 行ベクトルのコンストラクタは，それぞれの行ごとに別に呼び出される．