プログラムの高速化・並列化サービスの事例

＊ここに掲載するのは、エジンバラ大学のLawrence Mitchell博士によるHECToRレポート「A parallel Random Forest implementation for R, Lawrence Mitchell, 11 January 2011」を要約したものです。

概要

このプロジェクトではランダムフォレスト分類器(Breiman, 2001)の並列版の実装を行います。これはSPRINTフレームワークを用いたマイクロアレイ結果解析に利用され、HECToRスーパーコンピュータや他の並列マシンでの利用を想定するものです。

Rパッケージ (R Development Core Team, 2010)は、統計解析と可視化のオープンソフトウェアパッケージです。その実装の多くはR言語で記述されています。
The Simple Parallel R Interface：SPRINT (Hill et al., 2008)は、エジンバラ大学のDivision of Pathway MedicineおよびEPCCによるプロジェクトとして、Rを用いたマイクロアレイ解析に対する並列ワークフローを提供することを目的としています。その狙いは、できるだけ既存のコードに近い機能を提供することで、エンドユーザである生物統計学研究者が自身のワークフローを大きく変えることなく、HPC環境を利用可能にすることです。

ツリー分類

あるデータが与えられた場合に、データ測定値を結論にマッピングする予測モデルを構築することを考えます。例えば、観測された気象データを基にして、年間の日数を季節に分類することを考えます。一つのやり方は決定木学習(Kotsiantis, 2007)です。ここではデータを、予測を生成する決定木の構築に用います。このツリーはトレーニングデータセット（ここではデータ分類が既知のもの）を用いて構築され、その後未知のデータの分類の予測生成に用いられます。

·トレーニングデータ

マイクロアレイのデータは、コントロールと"感染"グループ両方から成る多くの個体に対する膨大な（数千から数十万）遺伝子の発現レベルの観測値から構成されます。ツリー分類の構築のためにここでは、観測された遺伝子発現レベルのみを用いて未知の個体のグループがどの分類かを予測するモデルを構築します。このモデルを用いて、ある個体が病気にかかりやすいかどうかを予測します。

·ランダムフォレスト

ランダムフォレストアルゴリズムは集団ツリー分類を行い、データセットのブートストラップ標本から分類木のフォレストを構築するものです。未知のデータの分類とは、フォレスト内の全ツリー上のデータの最頻クラスの特定を意味します。この文書で述べるランダムフォレスト法とその並列版は、入力データが変数数×ケース数の行列と同程度の高次元データに適用されます。ランダムフォレスト法はカテゴリーあるいは連続変数のどちらも分類可能です。マイクロアレイデータは連続値です。それは遺伝子発現レベルが実数として測定されるためですが、このプロジェクトではどちらも実行可能なように実装されました。

この分類手法はデータの分類を生成するだけでなく、どの遺伝子が重要かの推定や、分類誤差のバイアスの無い推定、およびフォレストサイズの増加に対して過剰適合しないことから、マイクロアレイデータでは一般的なものです。

·分類木の作成

決定木の構築は概念的には直截的です。ツリーはノードで構成され、ノードはデータセットを幾つかの属性値に基づき分割します。ルートノード（ここでは全データセットが存在する）から初めて、終了基準が満たされるまで繰り返し子ノードへ分割します。この条件とは特定のノードのケース数が閾値以下になった場合か、全ケースが同じクラスになった場合です。このような終端ノードを葉ノードを呼びます。一旦決定木を構築すれば、未知のケースに対しては、ルートノードから下位ノードへそれを渡していけば分類が得られます。その推定クラスはそれが終端に達した場所の葉ノードです。

ノードにおける分割基準は、一般にはジニ係数の最小化です(Breiman, 1984)。これは分割が、子ノードでのクラスの混合を如何にうまく減少させるかを示す尺度です：良い分割は悪い分割よりも少ないクラス混合で分割します。これ以外には、情報エントロピーを最初化する分割法があります(Quinlan, 1986; Kotsiantis, 2007)。

·分割のための変数の選択

ほとんどの決定木は決定論的なものです。これは、特にデータセットについては常に同じツリーを生成します。ランダムフォレストアルゴリズムのツリーはこの特性を持ちません。これはノード上で分割に用いる変数の選び方によるものです。これは、各ノードで全ての変数の中で最も良い分割を選ぶのではなく、ランダムに選んだ変数のサブセットを用います。よって一つのデータを分類する場合に、同じデータセットにより生成された2種の決定木により異なる分類となる場合があります。

·データ並列決定木

決定木生成の並列実装に関して多くの論文が存在ます(Joshi et al., 1998a,b; Shafer et al., 1996)。これらは全て社会科学で遭遇するデータタイプに関して設計されています。これは膨大なケース（数十万から数百万）を対象としますが、１ケースには極めて少ない変数（数重から数百）しかありません。その並列化には、ケースを均等に並列プロセスに分割する手法がとられています。

これらのアルゴリズムはマイクロアレイデータには適しません。何故ならケース上の並列数が小さいためです（数ケースが対象です）。ケースでなくて変数で並列化も可能ですが、ランダムフォレストによる生成で負荷バランスを保つには困難です。何故なら各ノードにおいて変数のサブセットで分割を行うため、並列プロセスの作業量に差が生じます。

この問題に対処するため、また、典型的なマイクロアレイデータセットは一つのRプロセスのメモリーに十分収まるため(Forster,2010)、データ並列を採らずにタスク並列手法を実装しました。

ランダムフォレストの生成

ランダムフォレストの生成においては、既存データセットのブートストラップ標本を多量に（普通は数千）生成し、これら各サンプルで分類木を生成します。ここで、既存のデータセットのデータはこれらツリーに送り込むことで分類され、最頻クラスが選ばれます。もしケースA で、100ツリーが感染していると評価され、900ツリーがコントロールと評価されれば、その分類はコントロールです。

ブートストラップ標本からの各ツリー生成は独立に行い、最後に結果を統合することが可能です。こうして、ブートストラップ標本を並列プロセスへ分散して結果を最後に統合するという、自然なタスク並列が可能です。

タスク並列の実装

タスク並列を実装しますが、SPRINTプロジェクトの目的の一つがシリアルコードに対する並列コードの置き換えであるため、既存のシリアル版Rコードを再利用して行います。この実装はシリアルコードの呼び出し方や結果を正確にまねたものです。

·作業の分散

並列化はrandomForest関数の引数であるツリー数ntreeに対して行います。ここで、これらツリーをプロセス間に渡って均等に分散させてこれらサブフォレストを並列に生成して、これらをマスタープロセスへ統合します。Rスクリプトの修正は不要です。

·結果の統合

各プロセスで生成されたサブフォレストは、実行の最後に一つのフォレストへ統合されてマスタープロセスへ返却されます。実装の一つが単純な線形アルゴリズムです。ここでは全てのデータをマスタープロセスへ集めて、その場で統合します。しかしながらこのアルゴリズムは32プロセッサ以上では、統合処理に大きなコストが掛かり、スケールしませんでした。データの転送はボトルネックではありませんが、問題は結果の統合処理です。

この統合はリダクション演算のため、MPI環境でこれを行うにはMPI_Reduce関数を用いるのが自然なやり方です。しかしながらこのコードでは、統合する対象が各レベルでサイスが異なり、MPI_Reduceの引数COUNTが不定です。我々が行った並列実装は、SPRINTの他の場所でも利用可能な一般的なものです。MPIと似た関数仕様ですが、Rオブジェクトは型でタグ付けられるため、COUNTやdatatype引数は不要です。

·他の方法

ランダムフォレストアルゴリズムの並列実装は多数存在します。例えば(Topic et al., 2005; Schwarz et al., 2010)はスタンドアローンプログラムです。また、foreachパッケージ(REvolution Computing, 2009)はランダムフォレストを並列に生成しますが、スクリプトに比べると利用には多くの作業が必要です。これらの実装では、結果の並列統合は行わずにシリアル実行します。

性能結果

HECToRのXT4とXT6上で性能を測定しました。XT4はクアッドコアノード、XT6は6コアダイによる24コアノードです。これらの性能差は大きくないことを観測しています。

それぞれ23292遺伝子を持つ62個体ケースのマイクロアレイデータを用いました。これは典型的なマイクロアレイデータのサイズです。さらに行あるいは列に対してノイズを含む複製を行い、さらに大きなデータセットも作成しました。

·結果統合アルゴリズムの性能

経過時間に関して、線形アルゴリズムが線形に増えるのに対し、ツリーリダクションの並列アルゴリズムは対数的にスケールします。これは256プロセスまで良好なスケール性を示します。

·メモリー競合

マルチコアノードでの実行では、通信が発生しない場合においても各プロセスが同じメモリーバスを共有することから大きな性能劣化を示しました。これは24コアノードのXT6で特有の問題です。複数のシリアルコードが一つのノード内で実行される場合に大きな性能劣化が観測されます。24コアノードは6つのダイから構成されており、1プロセスのみが1つのダイ上に割り当てられる場合は影響はありません。2プロセスが割り当てられると7%、4プロセスが割り当てられると13%の計算時間劣化が生じ、ノードが24プロセスで満たされると17%の劣化が生じます。メモリーアクセスパターンとシリアル実行されるランダムフォレストアルゴリズムのチューニングが必要なことが示唆されています。

·フォレスト生成の高速化

実験のマイクロアレイデータのサイズは固定です。この場合に期待されるのは強スケール性です。これは、入力データサイズを固定した場合にプロセス数を増やすことで高速化することを意味します。メモリー競合を除けば、ツリーの数を減らすとフォレスト生成時間は線形に減少します。よって、ツリー生成をプロセス間で均等にバランスさせれば、フォレスト生成ステップに良好な強スケール性を持たせることが可能です。全体の良好なスケール性を得るには、データのブロードキャストに関する通信と計算、および結果統合のオーバーヘッドを低く抑えることが必要です。マスタープロセスからのデータのブロードキャストはMPI_Bcastで可能です。ここでは、ベンダーが供給する最適化されたMPI_Bcastと、先述の統合アルゴリズムを用いました。

結果として、64プロセスまで良好なスケール性を示し、シリアル版に比べ40倍高速化しました。シリアル版が390秒だった時間が並列版では9秒に削減されました。

·フォレストサイズに対する弱スケール性

フォレストサイズを増やした場合にプロセス数を増加させて以前と同等の時間で計算させることを考えます。もしこの並列実装が良好な弱スケール性を持つならば、ツリー数を倍にした場合にプロセス数を倍にすれば同等の時間で結果を得ることが出来るはずです。測定結果では、メモリーアクセス性能による劣化が示されました。

·データセットサイズに対する弱スケール性

データセットで増減可能なものは、ケースと変数の2つの異なる次元を持ちます。ケースはマイクロアレイ実験では高価なものです（別の被験者を追加する）。変数はより低コストな追加の遺伝子の発現レベル測定です。

変数を増やした場合は、実行時間は線形に増加します。システムがスワップする限界の、1.5M遺伝子と62ケースまで測定しました。
変数数を固定してケース数を増やした場合、実行時間は線形以上に増加します。この場合はケース数を倍にすると、同じ時間で計算を終えるには倍以上のプロセスを用いる必要があります。

謝辞

このプロジェクトは、NAG Ltd.が運営するHECToRの分散計算科学および工学(CSE)サービスの基に実行されました。英国の国立スーパーコンピューティング・サービスである、HECToR：英国リサーチ・カウンシル・ハイエンド計算サービスは、リサーチ・カウンシルを代行するEPSRCが管理しています。そのミッションは英国学術界の科学および工学の研究支援です。HECToRスーパーコンピューターは、UoE HPCx Ltd.およびNAG Ltd.のCSEサポートサービスにより管理運営されています。

文献

[1]	L. Breiman. Classification and regression trees. Wadsworth, Belmont, California, 1984.
[2]	L. Breiman. Random forests. Machine Learning, 45:5-32, 2001.
[3]	T. Forster. Personal communication, 2010.
[4]	J. Hill, M. Hambley, T. Forster, M. Mewissen, T. Sloan, F. Scharinger, A. Trew, and P. Ghazal. SPRINT: A new parallel framework for R. BMC Bioinformatics, 9(1):558, 2008.
[5]	M. V. Joshi, G. Karypis, and V. Kumar. ScalParC: A new scalable and efficient parallel classification algorithm for mining large datasets. In Proceedings of the International Parallel Processing Symposium, pages 573-579, 1998a.
[6]	M. V. Joshi, G. Karypis, and V. Kumar. ScalParC: A new scalable and efficient parallel classification algorithm for mining large datasets. Technical report, University of Minnesota, 1998b. URL http://glaros.dtc.umn. edu/gkhome/fetch/papers/scalparc.pdf.
[7]	S. B. Kotsiantis. Supervised machine learning: a review of classification techniques. Informatica, 31:249-268, 2007.
[8]	J. R. Quinlan. Induction of decision trees. Machine Learning, 1(1):81-106, 1986
[9]	R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2010. URL http://www.R-project.org. ISBN 3-900051-07-0.
[10]	REvolution Computing. foreach: Foreach looping construct for R, 2009. URL http://CRAN.R-project.org/package=foreach. R package version 1.3.0.
[11]	D. Schwarz, S. Szymczak, A. Ziegler, and I. Konig. Picking single-nucleotide polymorphisms in forests. BMC Proceedings, 1(Suppl 1):S59, 2007.
[12]	D. F. Schwarz, I. R. Konig, and A. Ziegler. On safari to Random Jungle: a fast implementation of Random Forests for high-dimensional data. Bioinformatics, 26(14):1752-1758, 2010.
[13]	J. C. Shafer, R. Agrawal, and M. Mehta. SPRINT: A scalable parallel classifier for data mining. In T. M. Vijayaraman, A. P. Buchmann, C. Mohan, andN.L.Sarda, editors, VLDB’96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India, pages 544-555, 1996.
[14]	G. Topić, T. Šmuc, Z. Šojat, and K. Skala. Reimplementation of the random forest algorithm. In M. Vajteršic, R. Trobec, and P. Zinterhof, editors, Parallel Numerics '05, pages 119-125, 2005.
[15]	A. Ziegler, A. L. DeStefano, and I. R. Konig. Data mining, neural nets, trees - problems 2 and 3 of genetic analysis workshop 15. Genetic Epidemiology, 31(Supplement 1):S51-S60, 2007.