(57)【特許請求の範囲】
【請求項１】
入力データを受け付けて複数の子ノードのうち一つの子ノードを入力データに従って選択するルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置であって、
前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定手段と、
それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断手段と、
同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算手段と、
前記ビットワイズ論理和演算の結果に対して全ての階層についてビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記設定手段は、ｎ個のリーフノードの識別情報をｎビットの二進数の表記により設定し、
子ノードとして有するリーフノードの識別情報に対するビットワイズ論理和演算により求めた二進数の表記を前記判断ノードの識別情報として設定することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
それぞれの判断ノードの処理を、プログラム実行主体であるスレッドが一つのシングルスレッド環境、または、複数のスレッドが同時に処理を行うマルチスレッド環境で実行するために、各スレッドがアクセスできる記憶領域に前記入力データを保持する記憶手段を更に備える
ことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記判断手段は、それぞれの判断ノードにおける判断処理を前記マルチスレッド環境で実行することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記判断手段は、一つの判断ノードに対して一つのスレッドを割り当てることを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記判断手段は、同一階層に含まれる複数の判断ノードに対して一つのスレッドを割り当てることを特徴とする請求項４に記載の情報処理装置。
【請求項７】
前記判断手段は、同一階層に含まれる複数の判断ノードおよびルートノードに対して一つのスレッドを割り当てることを特徴とする請求項４に記載の情報処理装置。
【請求項８】
一のスレッドの処理と他のスレッドの処理とを同期させるために各スレッドの実行タイミングを制御する同期手段を更に備えることを特徴とする請求項３乃至７のいずれか１項に記載の情報処理装置。
【請求項９】
前記決定木による前記入力データの処理は、前記マルチスレッド環境を提供するＧＰＧＰＵ（General-purpose computing on graphics processing units)上の、Open CL（Open Computing Language）における一つのワークグループ上で実行されることを特徴とする請求項３に記載の情報処理装置。
【請求項１０】
コンピュータを、請求項１乃至９のいずれか１項に記載の情報処理装置の各手段として機能させるためのプログラム。
【請求項１１】
入力データを受け付けて複数の子ノードのうち一つの子ノードを入力データに従って選択するルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置のおける情報処理方法であって、
前記情報処理装置の設定手段が、前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定工程と、
前記情報処理装置の判断手段が、それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断工程と、
前記情報処理装置の演算手段が、同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算工程と、
前記情報処理装置の決定手段が、前記ビットワイズ論理和演算の結果に対して全ての階層についてビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定工程と、
を有することを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
決定木はデシジョンツリー（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）とも呼ばれ、決定理論の分野における意思決定のほか、機械学習や最近では物体認識にもよく使われる手法である。決定木の実行は単純である。ルートノードと呼ばれる唯一のノードから始め、入力に対する判断を行い、その結果に従って複数ある子ノードのうちの一つを選択する。これを再帰的に繰り返すことにより、最終的に子ノードを持たないノードにたどり着く。
【０００３】
子ノードを持たないノードをリーフノードと呼び、決定木の結果（ここではクラスと呼ぶ）と結びついている。子ノードを持つノードをここでは判断ノードと呼ぶことにする。判断ノードでは入力データを基に複数ある子ノードのうち、どれを選択するかを判断する。このように決定木とは複数あるクラス候補のうちの一つを、入力データを基に選択する手法である。全ての判断ノードが２つの子ノードを持ち、全ての子ノードは唯一つの親ノードを持つとすると、ｎ回の判断で最大２ｎクラスへの分類ができるため、従来から決定木は効率的な分類器として用いられてきた。
【０００４】
一方で計算機の実行環境はＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を用いるようになってきている。ＧＰＵをグラフィクス描画以外の計算に使うものをＧＰＧＰＵ（Ｇｅｎｅｒａｌ  Ｐｕｒｐｏｓｅ  ｃｏｍｐｕｔｉｎｇ  ｏｎ  ＧＰＵ）と呼ぶ。ＧＰＧＰＵにおいては通常数十から１０００を超える計算コアを同時に動かす（並列処理）ことにより速度向上を図っている。
【０００５】
しかし多くの計算アルゴリズムには、計算の実行に依存関係があり、並列処理を行うことが難しい。決定木の実行に関しても同様である。その結果、計算に参加しない計算コア（アイドルコアと呼ぶ）が増え、処理の高速化が図れないという問題が生じる。例えば、特許文献１には決定木の処理を高速に行なう構成が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−１８４８５８号公報
【非特許文献】
【０００７】
【非特許文献１】ＮＶＩＤＩＡ  ＣＵＤＡＴＭ  ＮＶＩＤＩＡ  ＣＵＤＡ  Ｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｇｕｉｄｅ  Ｖｅｒｓｉｏｎ３．２  １１／９／２０１０
【非特許文献２】Ｗｈｉｔｅｐａｐｅｒ  ＮＶＩＤＩＡ’ｓ  Ｎｅｘｔ  Ｇｅｎｅｒａｔｉｏｎ  ＣＵＤＡＴＭ  Ｃｏｍｐｕｔｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ：  ＦｅｒｍｉＴＭ
【非特許文献３】Ｔｈｅ  ＯｐｅｎＣＬ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ  Ｖｅｒｓｉｏｎ：１．１  Ｄｏｃｕｍｅｎｔ  Ｒｅｖｉｓｉｏｎ：３６
【非特許文献４】Ｐｒｏｇｒａｍｍｉｎｇ  Ｇｕｉｄｅ  ＡＭＤ  Ａｃｃｅｌｅｒａｔｅｄ  Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｉｎｇ  ＯｐｅｎＣＬＴＭ  Ｄｅｃｅｍｂｅｒ  ２０１０
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら特許文献１の手法はデータのメモリ配置を工夫したものであり、決定木の実行に際しては、一つのスレッドが判断ノードを渡り歩きながら、判断を繰り返すことで結果を得ている。多くの計算コア（スレッド）がある状況では、いかに多くの計算コアを同時に計算に参加させ、アイドルコアを減らすことができるかが重要である。決定木の実行に関する従来の技術では、アイドルコアを減らすことができず、並列化による実行の高速化が図れない、という課題がある。
【課題を解決するための手段】
【０００９】
本発明は、アイドルコアを減らし、処理の高速化を図ることが可能な情報処理技術を提供する。
【００１０】
本発明の一つの側面にかかる情報処理装置は、入力データを受け付けて複数の子ノードのうち一つの子ノードを入力データに従って選択するルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび子ノードを有さないリーフノードのうち少なくとも一方と、が階層的に接続された決定木により前記入力データを処理する情報処理装置であって、
前記ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する設定手段と、
それぞれの判断ノードによって、入力データに対する判断処理を行い、当該判断処理によって選択された子ノードの前記識別情報をそれぞれの判断ノードの選択結果として出力する判断手段と、
同一階層に含まれる前記判断ノードの選択結果として求められた前記子ノードの識別情報に対してビットワイズ論理和演算を行う演算手段と、
前記ビットワイズ論理和演算の結果に対して全ての階層についてビットワイズ論理積演算を行い、当該ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索し、当該検索されたリーフノードに関連付けられたクラスを前記入力データに対する決定木の実行結果として決定する決定手段と、
を備えることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、アイドルコアを減らし、処理の高速化を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】決定木を用いた第１実施形態に係る情報処理方法を説明する図。
【図２】（ａ）決定木を用いた第１実施形態に係る情報処理方法の流れを説明する図、（ｂ）情報処理装置の機能構成を示す図。
【図３】図２のステップＳ４の集計結果を例示する図。
【図４】実施形態に係る情報処理方法で適用可能な決定木を例示する図。
【図５】実施形態の情報処理方法におけるスレッドの割り当てを例示する図。
【発明を実施するための形態】
【００１３】
（第１実施形態）
図１を参照して決定木を用いた本発明の第１実施形態にかかる情報処理方法および情報処理装置決定木の実行方法を説明する。子ノードの選択はルートノード１１から行われる。ルートノード１１は入力データを受け付け、その入力データに対する判別結果として子ノード１２１、１２２のどちらを選択すべきかを判断する。複数の子ノードのうち一つを選択するノードを判断ノードと呼ぶ。図１において、判断ノードは線幅の細い円で示されている。判断ノードが何を基に判断するかは決定木によって異なるが、例えば、入力データに複数の値（変数）があり、それらの値と予め定めた値との比較を行って決定する。その比較の結果により、変数から求められた値により適合する子ノードを選択する。
【００１４】
図１では判断ノードから出る太い矢印が選択結果を示している。ルートノード１１では、子ノード１２１、１２２のうち、子ノード１２１が選択されている。同様に判断ノード１２１では子ノード１２３、１２４のうち、子ノード１２４が選択されている。そして判断ノード１２４では子ノード１３０が選択されている。判断ノード１３０では子ノード１４１が選択されているが、ノード１４１は子ノードを有さないリーフノードである。リーフノードでは選択は行われず、関連付けられたクラスがそのまま結果となる。図１では「９」というクラスが決定木の実行結果となる。
【００１５】
図２（ａ）は決定木を用いた第１実施形態にかかる情報処理方法の流れを説明する図であり、図２（ｂ）は情報処理装置２０の機能構成を示す図である。情報処理装置２０は、決定木により入力データを処理する。決定木はルートノードと、複数の子ノードのうち一つの子ノードを入力データに従って選択する判断ノードおよび下位の階層に子ノードを有さないリーフノードのうち少なくともいずれか一方と、が階層的に接続されたものである。
【００１６】
設定部２１は、ルートノード、判断ノード、およびリーフノードのそれぞれを識別するために、識別情報を二進数の表記により設定する。判断部２２は、それぞれの判断ノードによって、入力データに対する判断処理を行い、判断処理によって選択された子ノードの識別情報をそれぞれの判断ノードの選択結果として出力する。演算部２３は、同一階層に含まれる判断ノードの選択結果として求められた子ノードの識別情報に対してビットワイズ論理和演算を行う。
【００１７】
決定部２４は、ビットワイズ論理和演算の結果に対してビットワイズ論理積演算を行い、ビットワイズ論理積演算により求められた二進数の表記を識別情報として有するリーフノードを検索する。そして、決定部２４は、検索されたリーフノードに関連付けられたクラスを入力データに対する決定木の実行結果として決定する。記憶部２５は、それぞれの判断ノードの処理を、プログラム実行主体のスレッドが一つのシングルスレッド環境、または、複数のスレッドが同時、並列に処理を行うマルチスレッド環境で実行するために入力データを保持する。
【００１８】
制御部２６は、決定木による入力データの処理を、マルチスレッド環境を提供するＧＰＧＰＵ（General-purpose computing on graphics processing units)上の一つのワークグループ（Open CL）上で実行する。制御部２６は、マルチスレッド環境における一のスレッドの処理と他のスレッドの処理とを同期させるために各スレッドの実行タイミングを制御する。
【００１９】
情報処理装置２０の制御部２６（図２（ｂ））が図２（ａ）の処理の全体的な処理を制御する。ノードＩＤ付与ステップＳ１では、決定木の各ノードに内部処理用に、決定木を構成する各ノードを識別するために、ノードの識別情報（ノードＩＤ）を設定する。設定部２１はノードＩＤはまずリーフノードから付与する。設定部２１は重複のないよう整数値を適当に割り付ける。図１の場合、リーフノードのクラスがｎ（ｎは整数）＝０〜１５の１６個の整数値であるので、リーフノードに関連付けられるクラスの値をn＝０〜１５としている。クラスの関連付けは特にこの値に拘るものではない。設定部２１は、最終的にｎ個のリーフノードの識別情報をｎビットの二進数の表記により設定する。図１においてノードＩＤは関連付けられたクラスに基づく１６桁の二進数として各ノードの近傍に表記されている。
【００２０】
リーフノードのノードＩＤの付与が終了後、設定部２１は判断ノードのノードＩＤを付与する。判断ノードのノードＩＤには全ての子ノードのリーフノードのノードＩＤをビットワイズＯＲ（ビットワイズ論理和演算）したものを付与する。例えば、判断ノード１２７の場合、子ノードはふたつあり、それぞれ二進数の表記で示すと“10000000 00000000”と“01000000 00000000”である。これらのＯＲ（論理和演算）をとると“11000000 00000000”となる。これがノードＩＤとなる。同様に全ての判断ノードにノードＩＤを付与する。このようにリーフノードのノードＩＤが決定すれば、全ての判断ノードのノードＩＤは自動的に決定できる。ルートノードのノードＩＤは、ルートノードに接続しているノード（判断ノード、リーフノード）のノードＩＤを論理和演算することにより求めることができる。
【００２１】
次に入力データ準備ステップＳ２を行う。本発明はＩｎｔｅｌ社やＡＭＤ社のマルチコアＣＰＵ、ＮＶＩＤＩＡ社やＡＭＤ社のＧＰＧＰＵ等を搭載したコンピュータ（情報処理装置２０）上で実行可能であるが、特にそれらに拘るものではない。本発明はプログラムの実行主体であるスレッドが一つであるシングルスレッド環境でも実行可能である。また、本発明は、複数のスレッドが同時、並列に処理を行うマルチスレッド環境でも実行可能であり、処理の同時、並列化により処理の高速化を図ることが可能である。
【００２２】
各々のスレッドは続く判断ステップＳ３での判断を行うにあたり、その拠り所となる入力データが必要である。入力データ準備ステップＳ２ではこの判断に必要な入力データを各スレッドがアクセスできる記憶領域にセットする。判断ノードごとに判断内容が異なるため、各判断ノードで必要な入力データも異なる。
【００２３】
Ｉｎｔｅｌ社やＡＭＤ社のマルチコアＣＰＵに代表されるようなＳＭＰ（Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇ）アーキテクチャにおいては、判断のための入力データ保管場所として共有メモリを用いる。そのため、典型的にはスレッド専用のデータ保管場所にスレッドごとに異なる入力データをセットする必要はない。そのため、このステップは省略できる。一方、ＮＶＩＤＩＡ社やＡＭＤ社のＧＰＧＰＵの場合、各スレッドが排他的にアクセスできるレジスタに値をセットする高速化テクニックが用いられる。
【００２４】
続いて、判断ステップＳ３では、各判断ノードにおいて、記憶領域にセットされた入力データに対し予め定められた判断処理を行い、複数ある子ノードのうち、いずれか一つを選択し、結果として返すものである。判断処理とは、例えば、入力データに含まれるある変数の値と予め定められた値とを比較し、一致するか否かでどの子ノードを選択するかというものである。より具体的な例としては、入力データ内の変数「天気」が、予め定められた値「晴れ」であるか否かにより、二つある子ノードのうちのいずれかを選ぶようなものが挙げられる。
【００２５】
このように判断処理は単に変数の値を用いて比較することもあるが、さらに複雑な計算を必要とする判断もある。例えば、入力データに輝度画像と、この画像上の２点の座標が与えられ、各座標を中心とする３×３の範囲の画素値の平均値を比較し、前者の方が大きいか否かによって選択する子ノードを決定するようなものである。いずれの場合においても、子ノードを一つ選択するが、選択した子ノードのノードＩＤを判断ステップＳ３の選択結果とする。
【００２６】
判断ステップＳ３の処理は並列実行が可能である。マルチスレッド環境において、一つのスレッドが一つまたは複数の判断ノードの処理を担当する。判断ステップＳ３では各判断ノードの判断結果を多くのスレッドが分散して保持している。次のＯＲステップＳ４とＡＮＤステップＳ５とによって、各スレッドが保持している結果を集計して、決定木の実行結果を算出する。
【００２７】
ＯＲステップＳ４において、演算部２３は同一階層の判断ノードの結果を集計する。「階層」とはルートノード１１から判断ノードに至るまでに通過するブランチの数である。ブランチとは決定木内で親ノードと子ノードを繋ぐ矢印で示される。図１ではルートノード１１は第０階層、判断ノード１２１，１２２は第１階層、判断ノード１２３，１２４，１２５，１２６は第２階層、その他の判断ノードは第３階層である。ＯＲステップＳ４では同一階層の判断ノードの選択結果（ビット表示の子ノードの識別情報）に対してビットワイズＯＲ演算（ビットワイズ論理和演算）を行う。図１の場合における、ＯＲステップＳ４の集計結果を図３に示す。集計結果は階層ごと二進数表記でまとめられる。
【００２８】
最後にＡＮＤステップＳ５において、決定部２４はＯＲステップＳ４で同一階層ごとに集計された結果を全ての階層についてビットワイズＡＮＤ（ビットワイズ論理積演算）する。図１の場合、図３に示した集計結果を全てビットワイズＡＮＤ（ビットワイズ論理積）演算をすればよい。その結果、二進表記で“00000010 00000000”を得る。このノードＩＤを持つリーフノードに関連付けられたクラスが決定木の実行結果である。図１の場合、リーフノード１４１がこれに該当し、結果のクラスは「９」となる。
【００２９】
図１の場合、従来技法のシングルスレッド処理では４回の判断処理が必要となり、決定木の実行には４ＴＤ＋Ｔαの時間がかかる。ここでＴＤは１回の判断にかかる時間で、Ｔαは分岐等その他の処理にかかる時間である。
【００３０】
一方、本発明の実施形態にかかる判断ステップＳ３において各判断ノードにおける判断処理を異なるスレッドで同時に行った場合、ＴＤ＋ＴＴ＋Ｔβの時間がかかる。ＴＴは集計のためのスレッド間データ転送にかかる時間で、Ｔβはその他の処理にかかる時間である。判断処理が十分複雑でＴＤ≫ＴＴ，Ｔα，Ｔβの場合には、本実施形態は従来技法に比べ、約４倍高速に決定木の実行処理を行うことが可能である。
【００３１】
図１の場合では１５本のスレッドを使うが、従来技法ではアイドルコアとして使われなかった余剰の演算リソースである。このように本発明の実施形態ではアイドルコアを積極的に使用することにより、従来技法に比べ高速に判断木の実行を行うことが可能になる。
【００３２】
（第２実施形態）
先に説明した第１実施形態の決定木は平衡二分木であったが、本発明の趣旨はこの例に限定されず、例えば図４のような決定木の構造でもよい。ルートノード４１の子ノードには判断ノード４２１とリーフノード４３１があり、判断ノード４２１の子ノードには、判断ノード４２３、判断ノード４２２、およびリーフノード４３２を有る。また、判断ノード４２３はリーフノード４３５、４３４を有し、判断ノード４２２はリーフノード４３３、４３４を有する。
【００３３】
判断ノード４２１の子ノードは４２２，４２３，４３２と３つのノードがあるが、このように子ノードの数はいくつでもよい。判断ノード４２２，４２３の子ノードは共通のノード４３４であるが、このように親ノードの数はいくつでもよい。このように、一つのルートノードを持つループ経路のない決定木であれば、決定木の構造は問わない。図４の場合、ＴＤ≫ＴＴ，Ｔα，Ｔβとすると、従来技法では入力データによりＴＤ〜３ＴＤ程度の時間がかかる。本実施形態ではＴＤであり、従来技法に比べて最大で３倍程度の高速化を図ることが可能になる。
【００３４】
（第３実施形態）
ＴＤ≫ＴＴ，Ｔα，Ｔβの場合は、一つのスレッドで一つの判断ノードに関する判断ステップＳ３を同時に実行することにより、高速に判断木の実行を行うことができる。従来技法ではアイドルコアとして使われなかったｎ本のスレッドを演算リソースとして積極的に使用することにより、従来技法に比べ高速に判断木の実行を行うことが可能になる。２ｎの判断ノードがある平衡二分決定木を実行する場合、従来技法に比べ約ｎ倍の高速化が図れる。
【００３５】
第１実施形態の処理の流れでは判断ステップＳ３の並列実行処理のあと、ＯＲステップＳ４およびＡＮＤステップＳ５によって、各判断ノードの選択結果を集計している。この集計処理にはスレッド間の通信を伴うため、並列実行処理に比べて十分に決定木の実行の高速化が図れないこともある。判断ステップＳ３における各判断ノードでの判断が時間のかかる処理であれば、スレッド間通信による律速よりも並列処理による高速化が効果的である。逆に各判断ノードでの判断が単純であまり時間がかからない処理であれば、並列化による高速化よりもスレッド間通信による律速の影響が大きくなる。
【００３６】
ＴＤとＴＴに関して、ＴＤ≫ＴＴであれば処理ステップＳ３を最大限に並列化することによる高速化が有効である。そうではない場合には多少並列化を犠牲にしてもＴＴを小さくすることが有効である。
【００３７】
これには判断ステップＳ３において、複数の判断ノードにおける判断処理を一つのスレッドで行う。これにより、処理並列度を下げる代わりにスレッド間通信での律速の影響を減らすことができる。
【００３８】
いくつの判断ノードでの判断処理を一つのスレッドで行うかはトレードオフであり、実行環境に大きく依存するため、多くの場合試行を繰り返して実験的に求めることになるが、詳細は本発明の範囲外であるため省略する。
【００３９】
スレッド間通信を効果的に減らすにはＯＲステップＳ４で行う同一階層内の判断ノードでの処理を一つのスレッドで行うか、ＡＮＤステップＳ５で行う階層間の結果を集計する処理を一つのスレッドで行うのがよい。しかしながら、ＡＮＤステップＳ５におけるスレッド間通信は高々判断ステップの階層数のノードしか関与しておらず、効果は限定的となる上に、並列度を実験的に変更する際の柔軟度が低い。そこで、同一階層内の判断ノードの処理を、一つのスレッドで行う。図１において、どのスレッドがどの判断ノードの処理を行うかを図５に例示する。図５の例１では、一つのスレッドには１〜２個の判断ノードの判断処理が割り当てられている。例２では、一つのスレッドには３〜４個の判断ノードの判断処理が割り当てられている。例２ではスレッド番号１のスレッドには階層を跨って判断ノードの判断処理が割り当てられているが、同一階層内処理をした上で、さらに異なる階層の判断処理を行うように担当が割り当てられている。例１の場合にスレッド間通信にかかる時間が先の実施形態の半分であるとすると、決定木の実行にかかる時間は約２ＴＤ＋ＴＴ／２である。ＴＴ＝２．５ＴＤとすると、実施形態では従来技法に比べ１４％程度の高速化であったのが、約２３％の高速化が達成できる。
【００４０】
図５の例では使用スレッド数は８本であり、使用スレッド数が１５本の場合に比べてアイドルコアの利用率は減るが、従来技法に比べるとアイドルコアを積極的に活用した高速化が可能になる。
【００４１】
（第４実施形態）
図１において、下位の階層に子ノードを有さないリーフノードの数は１６個、図４においてリーフノードの数は５個である。本実施形態においてノードＩＤは１リーフノードあたり１ビット要する。そのためノードＩＤのサイズとして、図１の場合は１６ビット、図４の場合は５ビットが最低でも必要となる。
【００４２】
またＯＲステップＳ４およびＡＮＤステップＳ５ではビット演算を用いる。そこでノードＩＤを情報処理装置２０が一度に読み書きできる単位のサイズを持つ整数値とすることで、情報処理装置２０は効率よく処理を行うことができる。現在、よく使われているＩｎｔｅｌやＡＭＤのマルチコアＣＰＵや、ＮＶＩＤＩＡやＡＭＤのＧＰＧＰＵでは、８、１６、３２ビットといったサイズのデータを一度に読み書きできる。
【００４３】
そこで図１の決定木では１６ビット長、図４の決定木では８ビット長の整数とする。なお情報処理装置２０によっては、複数のサイズのデータを一度に読み書きできるが、その中でも最も効率のよいサイズが存在する場合がある。そのサイズが３２ビットであるとすると、図１、図４のどちらの場合も３２ビット長の整数とすることで、データの読み書きを効率的に行うことが可能になる。
【００４４】
（第５実施形態）
ＮＶＩＤＩＡのＧＰＧＰＵ（General-purpose computing on graphics processing units)開発環境であるＣＵＤＡや、ＡＭＤがＧＰＧＰＵ開発言語として採用しているＯｐｅｎＣＬ（Open Computing Language）ではＧＰＵの構造を反映したスレッドの階層構造を持つ。詳細は各々のドキュメント（非特許文献１〜４）に記載があるのでここでは省略するが、実行主体であるスレッドをＣＵＤＡではスレッド、ＯｐｅｎＣＬではワークアイテムと呼ぶ。さらにこれらをいくつかまとめたものをブロック（ＣＵＤＡ）、ワークグループ（ＯｐｅｎＣＬ）と呼ぶ。以下ではＯｐｅｎＣＬの用語を用いる。ＣＵＤＡの場合は適宜読み替えることで、同様の説明となる。ワークグループとはワークアイテムをまとめたもので、ワークグループ内のワークアイテムは論理的に同時並列処理が行われる。また同一ワークグループ内のワークアイテムは、ローカルメモリ（ＣＵＤＡでは共有メモリ）を介して高速なワークアイテム間通信ができる。
【００４５】
異なるワークグループが同時に実行されることは保障されておらず、そのためワークグループを跨いだワークアイテム間通信は原則として行えない。
【００４６】
そこで一つの決定木の実行を一つのワークグループ上で行うことで、ワークアイテム間通信を行いつつ、並列処理により実行結果を算出することができる。
【００４７】
（第６実施形態）
具体的なＧＰＵ（Graphics Processing Unit）との対応も考慮するとさらに細かい規則がある。基本的には同一ワークグループ内のワークアイテム（スレッド）は同一プログラムの同一位置の命令を実行することで、プログラムを高速に実行できる。そこで処理を早く終わった判断ノードに対するワークアイテムが次の処理を先行して実行しないように、各ステップ間で全ての全ワークアイテム（スレッド）の待ち合わせ同期を行う。制御部２６（図２（ｂ））は、一のワークアイテム（スレッド）の処理と他のワークアイテム（スレッド）の処理とを同期させるために各スレッドの実行タイミングを制御する。こうすることにより各ステップの実行タイミングを合わせることができ、少なくとも各ステップの先頭では全ワークアイテムが同一プログラムの同一位置の命令を実行することが可能となる。
【００４８】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005863426.tif 000002
【図２】
0005863426.tif 000003
【図３】
0005863426.tif 000004
【図４】
0005863426.tif 000005
【図５】
0005863426.tif 000006