(57)【要約】      （修正有）【課題】木構造が深い場合や木の数が多い場合にも、回路規模の増加を抑えると共に、演算速度の低下を抑えた演算処理装置を提供する。【解決手段】演算処理装置は、決定木の各ノードを複数のメモリＴＭ０〜ＴＭ３に分散して保持する演算処理装置であって、各メモリには、決定木における深さに応じたノードを配置可能なアドレッシング方式をもつ。演算処理装置は、各メモリＴＭ０〜ＴＭ３を有する複数のプロセッシングエレメントと、複数のプロセッシングエレメントの間で共有された複数のデータメモリと、複数のプロセッシングエレメントと複数のデータメモリとを接続するクロスバーとを備える。プロセッシングエレメントは、他のプロセッシングエレメントのメモリアドレスを出力してもよい。【選択図】図４
2020017179.tif 000002
【特許請求の範囲】
【請求項１】
決定木の各ノードを複数のメモリ（ＴＭｉ）に分散して保持する演算処理装置（１）であって、
前記各メモリ（ＴＭｉ）には、前記決定木における深さに応じた前記ノードを配置可能なアドレッシング方式をもつ演算処理装置（１）。
【請求項２】
前記各メモリ（ＴＭｉ）は、前記決定木の所定の深さまでのノードを保持し、
前記決定木の分岐の処理に基づいて、必要となる前記分岐先にある深いノードを前記各メモリ（ＴＭｉ）に保持する請求項１に記載の演算処理装置（１）。
【請求項３】
前記各メモリ（ＴＭｉ）を有する複数のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）と、
複数のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）の間で共有された複数のデータメモリ（ＤＭ０〜ＤＭｎ）と、
複数の前記プロセッシングエレメント（ＰＥ０〜ＰＥｎ）と前記複数のデータメモリ（ＤＭ０〜ＤＭｎ）を接続するクロスバー（ＣＢ０）と、
を備え、
前記プロセッシングエレメント（ＰＥ０〜ＰＥｎ）は、他のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）のメモリアドレスを出力する、請求項１又は２に記載の演算処理装置（１）。
【請求項４】
前記データメモリ（ＤＭ０〜ＤＭｎ）は、プロセッシングエレメント（ＰＥ０〜ＰＥｎ）の実行サイクル数以上の複数の処理単位のデータにより構成される請求項３に記載の演算処理装置（１）。
【請求項５】
前記決定木の特定の深さまでのノードを共通のメモリ（ＴＭｅｉ）に配置可能なアドレッシング方式をもつ請求項１又は２に記載の演算処理装置（３）。
【請求項６】
前記各メモリ（ＴＭｅｉ，ＴＭｉ）を有する複数のプロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ，ＰＥ０〜ＰＥｎ）と、
複数の前記プロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ，ＰＥ０〜ＰＥｎ）の間で共有された複数のデータメモリ（ＤＭ０〜ＤＭｎ）と、
を備え、
前記プロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ，ＰＥ０〜ＰＥｎ）は、
前記データメモリとデータバスを介して直接接続された第１のプロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ）と、
前記第１のプロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ）とクロスバー（ＣＢ２）を介してツリーメモリのアドレスバスで接続された第２のプロセッシングエレメント（ＰＥ０）と、
前記第２のプロセッシングエレメントから一方向の接続を有する第３のプロセッシングエレメント（ＰＥ１〜ＰＥｎ）との３種類により構成され、
前記第２のプロセッシングエレメント（ＰＥ０）および前記第３のプロセッシングエレメント（ＰＥ１〜ＰＥｎ）と前記データメモリ（ＤＭ０〜ＤＭｎ）とはクロスバー（ＣＢ０）を介してデータメモリのアドレスバスで接続されると共に、クロスバー（ＣＢ１）を介してデータバスで接続され、
前記第１のプロセッシングエレメント（ＰＥｅ０〜ＰＥｅＮ）のツリーメモリ（ＴＭｅｉ）は、特定の深さまでのノードを保持する、請求項５に記載の演算処理装置（３）。
【請求項７】
前記データメモリ（ＤＭｉ）は複数のバンクにより構成され、
前記バンクのアドレスバスは、前記第１のプロセッシングエレメント（ＰＥｅｉ）と直接接続されると共に、前記第２のプロセッシングエレメント（ＰＥ０）及び前記第３のプロセッシングエレメント（ＰＥ１〜ＰＥｎ）とクロスバー（ＣＢ０）を介して接続され、
前記バンクのデータバスは、前記第１のプロセッシングエレメント（ＰＥｅｉ）と直接接続されると共に、前記第２のプロセッシングエレメント（ＰＥ０）及び前記第３のプロセッシングエレメント（ＰＥ１〜ＰＥｎ）とクロスバー（ＣＢ１）を介して接続される、請求項６に記載の演算処理装置（３）。
【請求項８】
前記プロセッシングエレメント（ＰＥ０−０〜ＰＥ１−ｎ）とそれらを接続するバスを前記決定木ごとに有し、
前記プロセッシングエレメント（ＰＥ０−０〜ＰＥ１−ｎ）ごとに、プロセッシングエレメント（ＰＥ０−０〜ＰＥ１−ｎ）間で共有されたデータメモリ（ＤＭ０〜ＤＭｎ）へ個別にアクセス可能な構成を有し、
前記共有されたデータメモリ（ＤＭ０〜ＤＭｎ）はプロセッシングエレメント（ＰＥ０−０〜ＰＥ１−ｎ）の並列度以上の複数のバンクにより構成された、請求項４又は請求項７に記載の演算処理装置（４）。
【請求項９】
請求項１乃至８のいずれかに記載の演算処理装置を備えた画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置および画像処理装置に関する。
【背景技術】
【０００２】
従来から、回路規模の増加を抑えつつ、決定木の演算を行う演算処理装置が知られている。特許文献１に記載された演算処理装置は、カスケードバスによってコマンドを各プロセッシングエレメントに対して、１サイクルの遅延をもって伝搬させる。このためツリー用メモリへのアクセスと画像メモリへのアクセスが各プロセッシングエレメントで同時に発生することがないため、回路面積増加を抑えつつ全体の処理時間削減が可能である。
【０００３】
また、非特許文献１は、データメモリとプロセッシングエレメントが個別のデータメモリとツリーメモリを持つため、データメモリとプロセッシングエレメントは他のデータメモリとプロセッシングエレメントとの読出し調停を行う必要がない。毎サイクルデータを供給することが可能となり、演算器効率の高い動作となる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１６−２００９０６号公報
【非特許文献】
【０００５】
【非特許文献１】M. Owaida他「Scalable Inference of Decision Tree Ensembles: Flexible Design for CPU-FPGA Platforms」In FPL'17
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１に記載された装置では、ツリーメモリがランダムフォレスト全体のデータを保持しているため、木構造が深い場合や、木の数が多い場合には、ツリーメモリサイズが大きくなり、実装することが困難であった。また、各プロセッシングエレメントがツリーのノードの順番にメモリアクセスを実行するため、各プロセッシングエレメントは各メモリへのアクセスコマンドを実行後、各プロセッシングエレメント共通の命令を実行するまで待たされることなるという問題もあった。
【０００７】
非特許文献１に記載された装置は、各データメモリとプロセッシングエレメントに対して一対のデータメモリとツリーメモリを備えるため、メモリ使用量の観点でのコストが大きい。非特許文献１の装置も、特許文献１と同じく、木構造が深い場合や、木の数が多い場合には、ツリーメモリサイズが大きくなり、実装することが困難であった。
【０００８】
そこで、本発明は、木構造が深い場合や木の数が多い場合にも、回路規模の増加を抑えると共に、演算速度の低下を抑えた演算処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は上記課題を解決するために以下の技術的手段を採用する。特許請求の範囲及びこの項に記載した括弧内の符号は、ひとつの態様として後述する実施の形態に記載の具体的手段との対応関係を示す一例であって、本発明の技術的範囲を限定するものではない。
【００１０】
本発明の演算処理装置（１）は、決定木の各ノードを複数のメモリ（ＴＭｉ）に分散して保持する演算処理装置（１）であって、前記各メモリ（ＴＭｉ）には、前記決定木における深さに応じた前記ノードを配置可能なアドレッシング方式をもつ。
【００１１】
本発明の演算処理装置（１）は、前記各メモリ（ＴＭｉ）を有する複数のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）と、複数のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）の間で共有された複数のデータメモリ（ＤＭ０〜ＤＭｎ）と、複数の前記プロセッシングエレメント（ＰＥ０〜ＰＥｎ）と前記複数のデータメモリ（ＤＭ０〜ＤＭｎ）を接続するクロスバー（ＣＢ０，ＣＢ１）とを備え、前記プロセッシングエレメント（ＰＥ０〜ＰＥｎ）は、他のプロセッシングエレメント（ＰＥ０〜ＰＥｎ）のメモリアドレスを出力してもよい。
【発明の効果】
【００１２】
本発明によれば、決定木が深くなってもメモリリソースを効率的に使用し、かつ処理速度を高く保つことができる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の演算処理装置の構成を示す図である。
【図２】クロスバーの構成を示す図である。
【図３】（ａ）プロセッシングエレメントＰＥの詳細な構成を示す図である。（ｂ）ツリーメモリのデータフォーマットを示す図である。
【図４】（ａ）ツリーの分割例を示す図である。（ｂ）ツリーデータのメモリ上の配置を示す図である。
【図５】データメモリの詳しい構成を示す図である。
【図６】第１の実施の形態の演算処理装置のタイミングチャートである。
【図７】データメモリＤＭ０〜ＤＭ３に記憶された各処理単位のデータｂ０〜ｂＦの例である。
【図８】第２の実施の形態の演算処理装置におけるツリーデータの分割例を示す図である。
【図９】（ａ）時刻ｔ＝１におけるツリーデータのメモリ上の配置を示す図である。（ｂ）時刻ｔ＝２におけるツリーデータのメモリ上の配置を示す図である。
【図１０】（ａ）時刻ｔ＝３におけるツリーデータのメモリ上の配置を示す図である。（ｂ）時刻ｔ＝４におけるツリーデータのメモリ上の配置を示す図である。
【図１１】時刻ｔ＝５におけるツリーデータのメモリ上の配置を示す図である。
【図１２】（ａ）第２の実施の形態の変形例に係る演算処理装置におけるツリーデータの分割例を示す図である。（ｂ）ツリーデータのメモリ上の配置を示す図である。
【図１３】（ａ）ツリーデータの分割例を示す図である。（ｂ）ツリーデータのメモリ上の配置を示す図である。
【図１４】第３の実施の形態の演算処理装置の構成を示す図である。
【図１５】（ａ）プロセッシングエレメントＰＥｅｉの構成を示す図である。（ｂ）プロセッシングエレメントＰＥ０の構成を示す図である。
【図１６】データメモリの構成を示す図である。
【図１７】第３の実施の形態の演算処理装置のタイミングチャートである。
【図１８】タイミングチャートの前提となるデータ配置を示す図である。
【図１９】第４の実施の形態の演算処理装置の構成を示す図である。
【図２０】データメモリの構成を示す図である。
【図２１】第４の実施の形態の演算処理装置のタイミングチャートである。
【図２２】ランダムフォレストによって画像内の人物を認識する例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態の演算処理装置について図面を参照しながら説明する。実施の形態では、決定木の一つである２分木探索処理の演算を行う演算処理装置を例として説明する。２分木は、データ構造の一種である木構造において、親ノードが有する子ノードの数が２つ以下のもので、親のないノードを根（root node：node 0）とし、順に、node 1, node 2, …として配置される。２分木は、例えば、画像認識等の機械学習において使用するランダムフォレストと呼ばれる手法で使用される。
【００１５】
図２２は、ランダムフォレストによって画像内の人物を認識する例を示す図である。画像内からパッチ（patch）と呼ばれる単位で画像を取ってくる。このパッチが判定領域である。パッチを各ツリーに入れて各ツリーでの処理を実行する。具体的には、パッチ内にある画素ｐ０，ｐ１，ｐ２，・・・の画素値を比較して、ツリーの上位のノードから下位のノードへと辿っていく。例えば、tree 0では、node 0でpatch 0の画素ｐ０と画素ｐ１を比較し、画素ｐ０の方が大きい場合には、node 1へ遷移し、node 1で画素ｐ２と画素ｐ３を比較するといった具合に、一番下位のノードまで辿っていく。
【００１６】
patch 0についての演算は、tree 0だけでなく、tree 1や図示しない他のツリーでも行なう。そして、各ツリーの結果を加算し、閾値と比較することによって、パッチ内に人物が含まれるかどうかを判定する。なお、画像から複数のパッチを切り出した場合には、各パッチについての演算は独立して実行することができる。以下に説明する実施の形態にかかる演算処理装置は、このような画像処理装置において演算処理を行う装置として用いられる。
【００１７】
（第１の実施の形態）
図１は、第１の実施の形態の演算処理装置１の構成を示す図である。演算処理装置１は、全体の制御を行うコントローラＣＮＴと、複数のプロセッシングエレメントＰＥ０〜ＰＥｎと、複数のデータメモリＤＭ０〜ＤＭｎとを備えている。プロセッシングエレメントＰＥ０〜ＰＥｎの構成は同じであるので、プロセッシングエレメントＰＥ０〜ＰＥｎを特定しないときは、プロセッシングエレメントＰＥｉという。同様に、データメモリＤＭ０〜ＤＭｎを特定しないときは、データメモリＤＭｉという。
【００１８】
データメモリＤＭ０〜ＤＭｎには、画像のパッチデータ等が格納されている。プロセッシングエレメントＰＥｉは、隣接するプロセッシングエレメントＰＥｉへと一方向への接続を持っている。そして、最終のＰＥｎの出力が各ツリーの結果となる。複数のプロセッシングエレメントＰＥ０〜ＰＥｎと複数のデータメモリＤＭ０〜ＤＭｎは、クロスバーＣＢ０を介して接続されている。それぞれのプロセッシングエレメントＰＥｉは、ツリーのノードのデータを保持するツリーメモリＴＭｉを有している。ツリーメモリＴＭｉは、ツリー全体を保持するのではなく、ツリーの一部のノードのデータを保持し、複数のプロセッシングエレメントＰＥ０〜ＰＥｎによってツリー全体の構造を保持する。つまり、複数のプロセッシングエレメントＰＥ０〜ＰＥｎのそれぞれが有するツリーメモリＴＭ０〜ＴＭｎが、分散メモリを構成している。
【００１９】
図２は、クロスバーＣＢ０，ＣＢ１の構成を示す図である。クロスバーは、複数の入力ａ〜ｄのそれぞれを、複数の出力Ａ〜Ｄに接続するように回路を形成し、その通信路上に、入力ａ〜ｄのうちのどの入力を出力Ａ〜Ｄから出力するか選択できるようにスイッチを設けた回路である。本実施の形態のクロスバーＣＢ０，ＣＢ１は、こうした回路において、出力Ａ〜Ｄからは、入力ａ〜ｄのいずれか一つが出力されるように、スイッチが制御される。すなわち、ある時刻でみると、入力ａ〜ｄと出力Ａ〜Ｄとを１対１に接続するように、スイッチ制御が行われる。なお、図２では、入出力が４つの場合を例示しているが、入出力の数が４つに限定されないことは言うまでもない。
【００２０】
データメモリＤＭ０とプロセッシングエレメントＰＥ０が接続しているときにデータメモリＤＭ０とプロセッシングエレメントＰＥ１が接続することはない（クロスバーＣＢ０内でｎ本の接続のみ有効である）。図１において複数のプロセッシングエレメントＰＥ０〜ＰＥｎと複数のデータメモリＤＭ０〜ＤＭｎが接続されているのは、切り替えることによって、各プロセッシングエレメントＰＥ０〜ＰＥｎが各データメモリＤＭ０〜ＤＭｎのいずれにも接続され得ることを示している。
【００２１】
図３（ａ）は、プロセッシングエレメントＰＥｉの詳細な構成を示す図である。プロセッシングエレメントＰＥｉは、プロセッシングエレメントＰＥｉを制御するコントローラＰＥＣＮＴｉと、データメモリＤＭｉから取得した画素値を比較する評価部ＥＶと、ツリーのノードのデータを保持するツリーメモリＴＭｉを有している。上述したとおり、複数のプロセッシングエレメントＰＥ０〜ＰＥｎのそれぞれが有するツリーメモリＴＭ０〜ＴＭｎが、分散メモリを構成し、ツリーメモリＴＭ０〜ＴＭｎによって、ツリーのノード全体のデータを記憶している。
【００２２】
図４（ａ）は、ツリーの分割例を示す図である。図４（ａ）では、ツリーのデータをツリーメモリＴＭ０〜ＴＭ３に分散して保持している。ツリーメモリＴＭ０は、各ツリーtree 0〜tree Mのルートノードnode 0を保持している。ツリーメモリＴＭ１は、各ツリーtree 0〜tree Mの上から２番目のノードnode 1，node 2を保持している。同様に、各ツリーメモリＴＭｉは、ツリーにおいて、同じ深さのノードのデータを保持している。
【００２３】
図３（ｂ）は、ツリーメモリのデータフォーマットを示す図である。ツリーメモリのデータフォーマットは、データメモリのアドレスDM addr 0, DM addr 1を有する。これは、ノードにおいて比較を行うべき２つの画素のアドレスである。そして、Next TM addr Offsetは、次のノードのオフセットアドレスである。２分木の場合、Next TM addr Offsetが分かれば、真の場合はNext TM addr Offset、偽の場合は、Next TM addr Offset +(TM Data Formatのサイズ分）を読み出すというように実装することが可能である。例えば、tree0のnode0はtree0のnode1のアドレスのみを持っている。node0の実行結果に応じて、tree0のnode1もしくはtree0のnode2を選択する。以下同様にtree0のnode2はtree0のnode5とnode6のどちらかを選択し、と実行する。
【００２４】
図４（ｂ）は、ツリーデータのメモリ上の配置を示す図である。図４（ａ）で説明したように、ツリーメモリＴＭ０〜ＴＭ３には、深さに応じてツリーのノードのデータを記憶している。tree 0のnode 0において、２つの画素値を比較し、その結果に応じて、tree 0のnode 2を読み出している。これは、図３（ｂ）で示したNext TM addr Offsetに基づくアドレッシングを行った結果である。続いて、ツリーメモリＴＭ２のtree 0のnode 6を読み出し、さらにtree 0のnode 13を読み出している。このようにツリーメモリに図３（ｂ）に示すデータフォーマットで保持されたデータに基づいて、他のプロセシングエレメントＰＥｉのツリーメモリを適切にアドレッシングすることができる。
【００２５】
以上では、主要な信号のみを示したが、例えばタイミング制御やクロスバー制御は、コントローラＣＮＴが行ってもよいし、プロセッシングエレメントＰＥｉのコントローラＰＥＣＮＴｉが行ってもよい。また、プロセッシングエレメントＰＥｉ内の機能分割も一例に過ぎない。
【００２６】
図５は、データメモリＤＭｉの詳しい構成を示す図である。データメモリＤＭｉには、複数の処理単位のデータｂ０〜ｂｍを有している。処理単位のデータとは、図２２に示す例でいうと、パッチ（patch）と呼ばれる画像の単位である。処理単位のデータの数は、プロセッシングエレメントＰＥｉの動作のサイクルの数と同じかそれ以上であることが望ましい。例えば、プロセッシングエレメントＰＥｉでの動作が、ツリーメモリのリード（Ｒｅａｄ）、データメモリのリード（Ｒｅａｄ）、評価、次のツリーメモリのアドレッシングの４サイクルであったとすると、処理単位のデータの数を４つとする。
【００２７】
図６は、本実施の形態の演算処理装置１のタイミングチャートである。図７は、データメモリＤＭ０〜ＤＭ３に記憶された各処理単位のデータｂ０〜ｂＦの例である。図６に示すタイミングチャートは、図７に示すようにデータメモリＤＭ０〜ＤＭ３に各処理単位のデータｂ０〜ｂＦが記憶されていることを前提にしている。「ｒｔｍ」はツリーメモリのリード、「ｒｄｍ」はデータメモリのリード、「ｅｖａ」は読み出したデータの評価、「ｎｘｔ」は次のツリーメモリのアドレッシングを示す。タイミングチャートは、図７に記載したデータメモリＤＭｉの処理単位のデータｂ０〜ｂｍへのアクセスのタイミングを示している。処理単位のデータｂ１〜ｂ４、処理単位のデータｂ４〜ｂ７、処理単位のデータｂ８〜ｂＢ、処理単位のデータｂＣ〜ｂＦは同じデータメモリに含まれており、例えば、処理単位のデータｂ１と処理単位のデータｂ２に対して同じタイミングにアクセスすることはできない。なお、実際にデータメモリＤＭｉをリードするのは「ｒｄｍ」のタイミングであって、その他の「ｒｔｍ」「ｅｖａ」「ｎｘｔ」は、データメモリＤＭｉからデータを読み出し、処理を行うプロセッシングエレメントＰＥｉの動作の実行タイミングを示している。
【００２８】
本実施の形態では、データメモリＤＭｉは、プロセッシングエレメントＰＥｉのサイクル数と同じ４つの処理単位のデータを記憶しているので、各タイミングで別のデータメモリへアクセスすることで、同時アクセスを可能としている。結果として、各プロセッシングエレメントＰＥｉは常に稼働した状態で演算が可能となる。
以上、第１の実施の形態の演算処理装置１について説明した。
【００２９】
本実施の形態の演算処理装置１は、各ツリーメモリに分散してデータを格納し、ツリーの上から実行するという処理順序を満たすことが可能である。なお、本実施の形態では、ツリーメモリを分割して記載しているが、物理的に分割されているメモリであることを指定しているわけではなく、上記のようなアクセスが可能であれば、実装形態は問わない。
【００３０】
本実施の形態の演算処理装置１は、複数のプロセッシングエレメントＰＥ０〜ＰＥｎがデータメモリＤＭ０〜ＤＭｎを共有しているので、少ないリソースによって高い演算速度を実現することができる。
【００３１】
（第２の実施の形態）
図８は、第２の実施の形態の演算処理装置におけるツリーデータの分割例を示す図、図９（ａ）〜図１１は、メモリ上にツリーデータを読み出していく様子を示す図である。図９（ａ）は時刻ｔ＝１、図９（ｂ）は時刻ｔ＝２、図１０（ａ）は時刻ｔ＝３、図１０（ｂ）は時刻ｔ＝４、図１１は時刻ｔ＝５に、メモリ上に読み出されたツリーデータを示す。第２の実施の形態の演算処理装置は、大きいツリーを扱う場合に、複数のサブツリーに分割して処理を行う。図８では、例えば、大きいツリーを、複数のサブツリーに分割し、サブツリーごとにツリーメモリにデータを読み出して処理を行う。
【００３２】
図８について説明する。図８において、各ノードに付した番号は、説明の便宜上、サブツリーにおいてノードを区別するために付したものである。ハッチングを付したノードは処理を実行したノードを示し、各ノードの右側に記載している「ｔ＝０」「ｔ＝１」等の記載は、当該ノードの処理を実行した時刻を示している。例を挙げると、時刻ｔ＝０にデータ処理単位０について、サブツリーs0-0のノード０の処理を行い、時刻ｔ＝１にサブツリーs0-0のノード１の処理を行うと共に、データ処理単位０についてサブツリーs0-0のノード０の処理を行う。続いて、時刻ｔ＝２にデータ処理単位０について、サブツリーs1-0のノード２の処理を行うと共に、データ処理単位１についてサブツリーs0-0のノード１の処理、及びデータ処理単位２についてサブツリーs0-0のノード０を行う。このように、複数のデータ処理単位を同時進行で処理することができる。
【００３３】
図９（ａ）は、時刻ｔ＝１に、メモリ上に読み出したデータの例を示す。データ処理単位０のツリーメモリＴＭ０の処理が完了し、ツリーメモリＴＭ１にNext TM addr(0-0 1)を発行する。同時に、ＴＭ２とＴＭ３のロードを発行する。この段階でＴＭ２とＴＭ３のロードを発行するのは、ＴＭ２とＴＭ３の読出しには、一定の時間（１サイクルを実行する時間）がかかるためであり、データが準備されるのは、次の時刻（ここではｔ＝２）である。
【００３４】
図９（ｂ）は、時刻ｔ＝２に、メモリ上に読み出したデータの例を示す図である。なお、本実施の形態では、ＴＭ０とＴＭ１については、各データ処理単位に共通のサブツリーs0-0を用いる例を示している。図９（ｂ）に示す状態では、データ処理単位１のＴＭ０の処理が完了し、ＴＭ１にNext TM addr(0-0 1)を発行する。同時に、データ処理単位１についてＴＭ２とＴＭ３のロードを発行する。また、データ処理単位０については、ＴＭ１の処理完了までに、ＴＭ２とＴＭ３の読み込みが完了しており、ＴＭ２にNext addr (1-0 1)を発行する。
【００３５】
図１０（ａ）は、時刻ｔ＝３に、メモリ上に読み出したデータの例を示す図である。図１０（ａ）に示す状態では、データ処理単位２のＴＭ０の処理が完了し、ＴＭ１にNext TM addr(0-0 2)を発行する。同時に、データ処理単位２についてＴＭ２とＴＭ３のロードを発行する。
【００３６】
また、データ処理単位１については、ＴＭ１処理完了までに前の時刻で行ったＴＭデータ読込が完了し、ＴＭ２にNext addr (1-0 1)を発行する。また、データ処理単位０についてはＴＭ２の処理が完了し、ＴＭ３にNext addr (1-0 5)を発行する。同時に、ＴＭ４とＴＭ５のロードを発行する。
【００３７】
図１０（ｂ）は、時刻ｔ＝４に、メモリ上に読み出したデータの例を示す図、図１１は、時刻ｔ＝５に、メモリ上に読み出したデータの例を示す図である。図１０（ｂ）及び図１１に示す状態でも、これまでに説明した処理を繰り返し行う。ＴＭのサイズは、今回の条件では、最大で８ノードを格納できれば、複数のデータ処理単位についてパイプライン処理を行うことができる。
【００３８】
図１２（ａ）は第２の実施の形態の変型例に係る演算処理装置におけるツリーデータの分割例を示す図、及び図１２（ｂ）は図１２（ａ）に示すツリーデータをメモリ上に読み出した例を示す図である。第２の実施の形態の演算処理装置において、ツリーメモリＴＭ０〜ＴＭ２を再利用する態様を示す。つまり、ツリーメモリＴＭ４〜ＴＭ６に代えて、ツリーメモリＴＭ０〜ＴＭ２を用いる。図８に示す例では、例えば、サブツリーsubtree 0-0のnode0から処理を開始し、まず、node1へ分岐したとする。その後、node1の結果、node4に分岐が決定したとすると、この時点で、tree 0で実行される可能性があるサブツリーは subtree 0-1とsubtree 0-2のどちらかとなる。したがって、すでに不要となっているＴＭ０へサブツリーsubtree 0-1、subtree 0-2の深さｄ４のデータの読み込みを開始する。その後、深さｄ３にて、最終的な分岐方向が決定するまでに、深さｄ４〜ｄ６までのデータの読み込みが完了すれば、効率的に演算を進めることが可能である。ここでは、深さｄ１の分岐が決定すると同時にデータの読み出しを行う例で示したが、ツリーメモリのサイズやサブツリーデータのロード時間等から、サブツリーの処理ノードがなくなる前に適切に設定すればよい。このように、ツリーデータの分割とツリーメモリの再利用とを組合せることでメモリ使用量と処理時間のトレードオフを図ることが可能である。
【００３９】
（第３の実施の形態）
図１３（ａ）及び図１３（ｂ）を参照して、第３の実施の形態の演算処理装置３におけるツリーメモリへのデータの格納の仕方を示す図である。図１３（ａ）は、ツリーデータの分割例を示す図であり、図１３（ｂ）はツリーデータのメモリ上の配置を示す図である。図１３（ａ）に示すように、深さｄ０と深さｄ１のノードを共通の分散メモリＴＭｅに持つことで、ツリーが浅い場合にＴＭ０とＴＭｎのメモリサイズが極端に変わることを防ぎ、ツリーメモリの物理レイアウト時に、レイアウトの自由度を高めることができる。
【００４０】
図１３（ｂ）に示すように、深さｄ０、ｄ１に属するノードnode0，node1，node2をツリーメモリＴＭｅに格納し、深さｄ２に属するノードnode3〜node6をツリーメモリＴＭ０に格納し、深さｄ３に属するノードnode7〜node14をツリーメモリＴＭ１に格納する。
【００４１】
図１４は、第３の実施の形態の演算処理装置３の構成を示す図である。第３の実施の形態の演算処理装置３は、全体の制御を行うコントローラＣＮＴと、複数のプロセッシングエレメントＰＥｅ０〜ＰＥｅＮ、ＰＥ０〜ＰＥｎと、複数のデータメモリＤＭ０〜ＤＭｎとを備えている。複数のプロセッシングエレメントＰＥｅ０〜ＰＥｅＮ，ＰＥ０〜ＰＥｎには、データメモリＤＭ０〜ＤＭｎと直接接続するプロセッシングエレメントＰＥｅ０〜ＰＥｅＮと、プロセッシングエレメントＰＥｅ０と接続するプロセッシングエレメントＰＥ０と、データメモリＤＭ０〜ＤＭｎとクロスバーＣＢ１を介して接続するプロセッシングエレメントＰＥ１〜ＰＥｎの３種類がある。
【００４２】
プロセッシングエレメントＰＥｅ０〜ＰＥｅＮのツリーメモリは、深さｄ０，ｄ１のノードを保持する。プロセッシングエレメントＰＥ０のツリーメモリは深さｄ２のノードを保持する。プロセッシングエレメントＰＥ１以下のツリーメモリは、深さｄ３以降のノードを保持する。
【００４３】
プロセッシングエレメントＰＥ０〜ＰＥｎとデータメモリＤＭ０〜ＤＭｎは、クロスバーＣＢ０及びクロスバーＣＢ１を介して接続されている。また、プロセッシングエレメントＰＮｅＮとプロセッシングエレメントＰＥ０とはクロスバーＣＢ２を介してアドレスバスによって接続されている。プロセッシングエレメントＰＥｉは、隣接するプロセッシングエレメントＰＥｉへと一方向への接続を持っている。
【００４４】
図１５（ａ）は、プロセッシングエレメントＰＥｅ０〜ＰＥｅＮ（総称して「ＰＥｅｉ」という）の構成を示す図である。プロセッシングエレメントＰＥｅｉは、プロセッシングエレメントＰＥｅｉを制御するコントローラＰＥｅＣＮＴｉと、データメモリＤＭｉから取得した画素値を比較する評価部ＥＶと、ツリーのノードを保持するツリーメモリＴＭｅｉを有している。図１５（ｂ）は、プロセッシングエレメントＰＥ０の構成を示す図である。プロセッシングエレメントＰＥ０の基本的な構成は、プロセッシングエレメントＰＥｅｉと同じであるが、プロセッシングエレメントＰＥ０は、プロセッシングエレメントＰＥｅｉから、TM addrを受け取り、複数の深さの評価を実行する。プロセッシングエレメントＰＥ１〜ＰＥｎの構成は、第１の実施の形態で説明した構成と同じである。
【００４５】
図１６は、データメモリＤＭｉの構成を示す図である。データメモリＤＭｉは、クロスバーＣＢ０，ＣＢ１に接続する経路とプロセッシングエレメントＰＥｅｉと接続する経路を有する。ここで、処理単位のデータ数を各プロセッシングエレメントＰＥｅｉ，ＰＥｉの実行サイクル以上とすることで、クロスバーＣＢ０のアドレスとプロセッシングエレメントＰＥｅｉ，ＰＥｉのアドレスが同じ処理単位のデータにアクセスすることを防ぐことが可能である。したがって、各処理単位のデータメモリｂ０〜ｂｍは調停を行わず読み出しが可能となり実行効率を上げることが可能となる。
【００４６】
図１７は、第３の実施の形態の演算処理装置３のタイミングチャートである。図１７に示すタイミングチャートは、図１８に示すデータ配置を前提としている。本実施の形態では、プロセッシングエレメントＰＥｉの番号と当該プロセッシングエレメントＰＥｉが実行するツリーの深さが一致しないので、タイミングチャートには、実行中のツリーの深さも示している。例えば、「b0d0」は、ｂ０のデータを深さｄ１で実行していることを意味している。
【００４７】
プロセッシングエレメントＰＥｅｉは深さｄ０，ｄ１のノードを実行する。このため４サイクル動作とすると、例えば、ＰＥｅ０は、４サイクル実行後、処理単位のデータb0d0のNext TM addrを次の深さのTM addr入力として与え、処理単位のデータb0d1を実行する。したがって、８サイクル後に処理単位のデータb0d1でのNext TM addrが得られる。深さｄ２以降はこれまでの例と同様に各プロセッシングエレメントＰＥｉの深さ1つ分を実行する。
【００４８】
ここで、プロセッシングエレメントＰＥｅｉのnxt実行とプロセッシングエレメントＰＥｎのｒｔｍ実行を適切な遅延時間を挟んで実行することで、メモリアクセスを処理単位のデータごとに分けることができる。例えばプロセッシングエレメントＰＥｅｉのｎｔｘ実行とプロセッシングエレメントＰＥｎのｒｔｍ実行を１サイクルずらすことで、処理単位のデータb1d1、d5d0、bCd2、b8d3、b4d4、b0d5と重複した処理単位のデータへのアクセスを避けることが可能となる。各処理単位のデータへの排他制御をおこなうことなく、単純なセレクト信号のみで実装が可能である。
【００４９】
第３の実施の形態の演算処理装置３は、ツリーの深さが浅い部分でデータメモリを共有することにより、ツリーメモリの物理レイアウト時に、レイアウトの自由度を高めることができる。
【００５０】
（第４の実施の形態）
図１９は、第４の実施の形態の演算処理装置４の構成を示す図である。これまでに説明した実施の形態では、各ツリーメモリには複数のツリーのデータを保持したが、第４の実施の形態では、ツリーごとにプロセッシングエレメントを有する。このため、演算処理装置４は、プロセッシングエレメント及びクロスバーは、並列度に応じて複数有している。図１９では並列度が「２」の例を示しているので、各深さのノードを処理するプロセッシングエレメントは２つずつあり、これをプロセッシングエレメントＰＥ０−０〜ＰＥ０−ｎ，ＰＥ１−０〜ＰＥ１−ｎで表している。なお、図１９においてバス上に記載した「ｐ」は並列であることを示している。各プロセッシングエレメントＰＥ０−１〜ＰＥ１−ｎが、データメモリＤＭ０〜ＤＭｎに個別にアクセス可能である。
【００５１】
図２０は、データメモリＤＭｉの構成を示す図である。データメモリＤＭｉは、並列度以上の複数のバンクｂ０〜ｂｍを有している。データメモリＤＭｉは内部にクロスバーＤＭＣＢ０，ＤＭＣＢ１を有し、すべてのバンクへ並列度分のバンク選択が可能な構成となっている。データメモリＤＭｉとプロセッシングエレメントＰＥ０−０〜ＰＥ１−ｎの間は例えば、クロスバーＣＢ０−０、ＣＢ０−１を用いて従来のプロセッシングエレメントＰＥ０−０〜ＰＥ０−ｎ（またはＰＥ１−０〜ＰＥ１−ｎ）方向（ｎ方向）の選択を行った後、並列度方向（ｐ方向）への選択を行うといった２段階の経路選択を行うといったことで任意のプロセッシングエレメントＰＥ０−０〜ＰＥ１−ｎからアクセスが可能である。
【００５２】
図２１は、第４の実施の形態の演算処理装置４のタイミングチャートである。例えば、偶数ツリーと奇数ツリーに分けた場合に、これまで同様にプロセッシングエレメントＰＥでの動作が４サイクル必要だったとする。この場合、図２１に示すように１サイクル遅延をいれることで同じ処理単位のデータへのアクセスがなくなり、調停や遅延が発生することなくデータを読み出すことが可能となる。
【産業上の利用可能性】
【００５３】
本発明は、例えば、決定木の演算を行う演算処理装置等として有用である。
【符号の説明】
【００５４】
１，３，４  演算処理装置
ＰＥ  プロセッシングエレメント
ＤＭ  データメモリ
ＴＭ  ツリーメモリ
ＣＢ  クロスバー
【図１】
2020017179.tif 000003
【図２】
2020017179.tif 000004
【図３】
2020017179.tif 000005
【図４】
2020017179.tif 000006
【図５】
2020017179.tif 000007
【図６】
2020017179.tif 000008
【図７】
2020017179.tif 000009
【図８】
2020017179.tif 000010
【図９】
2020017179.tif 000011
【図１０】
2020017179.tif 000012
【図１１】
2020017179.tif 000013
【図１２】
2020017179.tif 000014
【図１３】
2020017179.tif 000015
【図１４】
2020017179.tif 000016
【図１５】
2020017179.tif 000017
【図１６】
2020017179.tif 000018
【図１７】
2020017179.tif 000019
【図１８】
2020017179.tif 000020
【図１９】
2020017179.tif 000021
【図２０】
2020017179.tif 000022
【図２１】
2020017179.tif 000023
【図２２】
2020017179.tif 000024