(57)【要約】      （修正有）【課題】プロセッシングエレメントを３次元の空間に配置することなく、高速３次元データ処理を提供する。【解決手段】並列演算装置１０において、２次元平面上に配置された２つ以上のプロセッシングエレメント１１をトーラス状に接続する。この２次元平面上に配置されたプロセッシングエレメント１１に３次元データを写像して保持させる。プロセッシングユニット１１が配置された２次元平面上で、各プロセッシングユニット１１での受信データの保持判定を含むデータ転送を行わせる。【選択図】図１
2017207798.tif 000002
【特許請求の範囲】
【請求項１】
２次元平面上に配置されトーラス状に接続された２つ以上のプロセッシングユニットと、前記プロセッシングエレメントと外部装置との間の通信を制御するブロックと、全体を制御するブロックとを有する並列演算装置におけるデータ処理方法であって、
前記２次元平面上に配置されたプロセッシングエレメントに３次元データを写像して保持するステップと、
前記プロセッシングユニットが配置された２次元平面上で各プロセッシングユニットでの受信データの保持判定を含むデータ転送を行うステップと
を備えることを特徴とする並列演算装置におけるデータ処理方法。
【請求項２】
請求項１に記載された並列演算装置におけるデータ処理方法において、
前記データ転送を行うステップは、
隣接する一方向のプロセッシングエレメントにデータ転送を行い、らせん状にデータ転送を繰り返す
ことを特徴とする並列演算装置におけるデータ処理方法。
【請求項３】
請求項２に記載された並列演算装置におけるデータ処理方法において、
前記データ転送を行うステップにおいて、
各プロセッシングエレメントは、
隣接したプロセッシングエレメントからデータを受信した場合、データの送信元の座標と自身の座標とを比較してそのデータを保持するか否かを判定し、
保持すると判定した場合には、そのデータを保持するとともに、次のプロセッシングエレメントに転送し、
保持しないと判定した場合には、そのデータを保持せずに、次のプロセッシングエレメントに転送する
ことを特徴とする並列演算装置におけるデータ処理方法。
【請求項４】
２次元平面上に配置されトーラス状に接続された２つ以上のプロセッシングユニットと、前記プロセッシングエレメントと外部装置との間の通信を制御するブロックと、全体を制御するブロックとを有する並列演算装置であって、
前記２次元平面上に配置されたプロセッシングエレメントに３次元データを写像させる手段と、
前記プロセッシングユニットが配置された２次元平面上で各プロセッシングユニットでの受信データの保持判定を含むデータ転送を行わせる手段と
を備えることを特徴とする並列演算装置。
【請求項５】
請求項４に記載された並列演算装置において、
前記プロセッシングエレメントは、
データの送受信を行うブロックと、４本の同じ条件の通信経路と、受信したデータの保持判定を行うブロックと、データの転送方向を制御するブロックと、データを保持するブロックと、演算を行うブロックと
を備えることを特徴とする並列演算装置。
【請求項６】
請求項５に記載された並列演算装置において、
前記受信したデータの保持判定を行うブロックは、
隣接したプロセッシングエレメントからデータを受信した場合、データの送信元の座標と自身の座標とを比較してそのデータを保持するか否かを判定し、
保持すると判定した場合には、そのデータを保持させるとともに、次のプロセッシングエレメントに転送させ、
保持しないと判定した場合には、そのデータを保持させずに、次のプロセッシングエレメントに転送させる
ことを特徴とする並列演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッシングエレメント(ＰＥ：Processing Element(演算処理回路))を備えた並列演算装置におけるデータ処理方法および並列演算装置に関する。
【背景技術】
【０００２】
近年、低レイテンシ・高スループットを実現するデータ処理システムに対する要望がますます高まっており、高速にデータ処理を行うためのアーキテクチャの一つとして、プロセッシングエレメントを多数並べたアレイ型プロセッサが使われることがある。このアレイ型プロセッサでは、各プロセッシングエレメントが並列演算処理を行うことによって、高速にデータ処理が行われる。
【０００３】
一般に普及しているアレイ型プロセッサにはＧＰＵ（Graphics Processing Unit）があり、主に画像処理などに利用される。ＧＰＵを汎用的なデータ処理に用いる（ＧＰＧＰＵ：General Purpose GPU）ことも検討されているが、アプリケーションごとに最適な設計を行うことはできない。
【０００４】
また、Ｎ次元（Ｎは自然数）のデータの並列演算処理を想定すると、周辺プロセッシングエレメントと通信するためには多くの配線資源と転送時間が必要となる。この問題を解決するために、高速バスとクロスバースイッチを用いた構成やシストリックアレイ構成が提案されているが、プロセッシングエレメント間の通信やメモリアクセスにおける競合により処理速度が制限される問題がある。
【０００５】
そこで、独自の機構や制御命令を備えたアレイ型プロセッサをＦＰＧＡ（Field Programmable Gate Array）などを用いて実現することで特定のアプリケーションに対して最適化することが注目されている。このような独自構成のアレイ型プロセッサの一つとして例えば非特許文献１に示されるような構成がある。
【０００６】
この非特許文献１に示された構成では、独自のプロセッシングエレメントを備えており、プロセッシングエレメント間のデータ転送を工夫してメモリアクセスの競合を防ぐことで配線資源と転送時間を削減している。具体的には、すべてのプロセッシングエレメントでデータ転送を同時かつ同じ方向に行い、常にデータが一定の方向に流れるようにすることで、配線混雑および配線遅延を回避し、データの衝突による待ち時間の発生をなくしている。この非特許文献１に示された構成は、移動物体のトラッキングを行うアプリケーションなどに応用されている。
【０００７】
このように、専用のプロセッシングエレメントを設計することで、各アプリケーションに特化したアーキテクチャを構成することができ、高速にデータ処理を行うことができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】内苑  孝俊、他５名、「同期シフトデータ転送による２次元アレイ型トラッキングハードウェア」、電子情報通信学会技術研究報告．RECONF，リコンフィギャラブルシステム 111(399), 19-24, 2012-01-18
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１に示された構成において、Ｎ次元のデータとして３次元データの処理を想定した場合、プロセッシングエレメントを３次元の方向に配置する必要がある。しかしながら、３次元の空間に物理的にプロセッシングエレメントを配置することは難しい。
【００１０】
本発明は、このような課題を解決するためになされたもので、その目的とするところは、プロセッシングエレメントを３次元の空間に配置することなく、３次元データの処理を高速に行うことが可能な並列演算装置におけるデータ処理方法および並列演算装置を提供することにある。
【課題を解決するための手段】
【００１１】
このような目的を達成するために本発明は、２次元平面上に配置されトーラス状に接続された２つ以上のプロセッシングユニット（１１）と、プロセッシングエレメント（１１）と外部装置（１２）との間の通信を制御するブロック（１２）と、全体を制御するブロック（１４）とを有する並列演算装置（１０）におけるデータ処理方法であって、２次元平面上に配置されたプロセッシングエレメント（１１）に３次元データを写像して保持するステップと、プロセッシングユニットが配置された２次元平面上で各プロセッシングユニットでの受信データの保持判定を含むデータ転送を行うステップとを備えることを特徴とする。
【００１２】
本発明では、２次元平面上に配置されたプロセッシングエレメント（１１）に３次元データが写像して保持され、プロセッシングユニット（１１）が配置された２次元平面上で各プロセッシングユニット（１１）での受信データの保持判定を含むデータ転送が行われる。これにより、プロセッシングエレメント（１１）を３次元の空間に配置することなく、３次元データの処理を高速に行うことが可能となる。
【００１３】
なお、上記説明では、一例として、発明の構成要素に対応する図面上の構成要素を、括弧を付した参照符号によって示している。
【発明の効果】
【００１４】
本発明によれば、２次元平面上に配置されたプロセッシングエレメントに３次元データを写像して保持し、プロセッシングユニットが配置された２次元平面上で各プロセッシングユニットでの受信データの保持判定を含むデータ転送を行うようにしたので、プロセッシングエレメントを３次元の空間に配置することなく、３次元データの処理を高速に行うことが可能となる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施の形態に係る並列演算装置を含むシステムの構成を示す図である。
【図２】図２は、このシステムにおける並列演算装置で用いられるプロセッシングエレメントの構成を示すブロック図である。
【図３】図３は、３次元データを２次元平面上に配置されたプロセッシングエレメントに写像（伸張）して保持させた例を示す図である。
【図４】図４は、図３のデータ配置により実現される３次元ネットワークを説明する図である。
【図５】図５は、図３のデータ配置においてデータ処理を行う際のデータ転送の一例を説明する図である。
【図６】図６は、フレーム間で移動する物体のフローを抽出する画像処理の例を説明する図である。
【図７】図７は、図６で示した画像処理を図１に示したシシテムにおける並列演算装置で行ったときのデータ配置を説明する図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。図１は本発明の実施の形態に係る並列演算装置１０を含むシステム１００の構成を示す図である。
【００１７】
このシステム１００において、並列演算装置１０は、２つ以上のプロセッシングエレメント（ＰＥ）１１と、プロセッシングエレメント１１と外部記憶装置１５との間でデータや制御信号をやり取りするための転送制御部１２と、通信路１３と、システム１００全体を管理するための全体制御部１４とを備えている。
【００１８】
なお、この並列演算装置１０は、再生可能デバイスとして、集積回路やＦＰＧＡなどの上に実装されている。また、外部記憶装置１５としては、ＳＤＲＡＭ（Synchronous Dynamic Ramdam Access Memory）などを用いる。
【００１９】
また、図１では、２つ以上のプロセッシングエレメントとして、縦・横に４個ずつ合計１６個のプロセッシングエレメント１１しか示していないが、実際にはさらに多くのプロセッシングエレメント１１が配置されている。これらのプロセッシングエレメント１１は、横方向（左右方向）をＸ方向、縦方向（上下方向）をＹ方向とする２次元平面上に配置され、Ｘ方向およびＹ方向にトーラス状に接続された構成とされている。
【００２０】
プロセッシングエレメント１１は、図２に示すように、データ転送部２０と、上下左右の４本の同じ条件の通信経路２１と、受信したデータを保持するか否かを判定するデータ保持判定部２２と、プロセッシングエレメント１１内外のデータ転送を制御する転送制御部２３と、データを保持するデータ保持部２４と、実行するアプリケーションに応じて最適化された演算部２５とから構成されている。
【００２１】
データ保持判定部２２では、受信したデータの送信元のプロセッシングエレメント１１の座標と自身の座標とを比較することで保持判定を行い、その結果を転送制御部２３に伝えることで受信したデータをデータ保持部２４に取り込むかどうかを決める。このデータ保持判定部２２での保持判定については後述する。
【００２２】
図３に３×３×３の３次元データ（ｘ，ｙ，ｚ，Ｄ）を２次元平面上（Ｘ，Ｙ）に配置されたプロセッシングエレメント１１に写像（伸張）して保持させた例を示す。図３中、その色を濃淡の度合いで示す各色のセル（枡目）がプロセッシングエレメント１１に対応し、各色のセル中にａ，ａ’ａ”というようにして示したデータが、それぞれｚ＝０、ｚ＝１、ｚ＝２の座標のデータを表している。
【００２３】
この配置例では、Ｘ方向に（ｘ，ｙ＝α，ｚ）のデータを割当て、Ｙ方向に（ｘ＝β，ｙ，ｚ＝γ）のデータを割当てている（α，β，γは定数）。このようにＸ方向にｚ方向のデータを順番に割り当てることで３次元データを２次元平面上に配置されたプロセッシングエレメント１１に写像（伸張）する。
【００２４】
この２次元平面上に配置されたプロセッシングエレメント１１（１１−ａ〜１１−ｉ”）への３次元データの写像は、全体制御部１４と転送制御部１２とが連携して行う。また、写像される３次元データは、外部記憶装置１５に記憶されている。
【００２５】
このような配置により実現される３次元ネットワークを図４に示す。図４中、その色を濃淡の度合いで示す各色のノード（丸）が図３中の各色のセルに対応する。このネットワークでは、ｙ方向とｚ方向については隣接するノードが接続され、ｘ方向については最下層のノードと最上層のノードとが接続される。
【００２６】
図５に図３のデータ配置においてデータ処理を行う際のデータ転送の一例を示す。この図は図３に示した中央のセルのデータｅ’、すなわちプロセッシングエレメント１１−ｅ’のデータｅ’を３次元的に隣接するプロセッシングエレメント１１−ａ〜１１−ｉ”に転送する例を示している。
【００２７】
この例では、プロセッシングエレメント１１をＸ方向に９個、Ｙ方向に９個、合計８１個配置し、その中央部の３×９のプロセッシングエレメント１１を図３に示した３×９個のセルに対応するプロセッシングエレメント１１−ａ〜１１−ｉ”としており、転送元（送信元）のプロセッシングエレメント１１−ｅ’を中心として、らせん状に隣接するプロセッシングエレメント１１にデータを転送する。このデータの転送は全体制御部１４と転送制御部１２とが連携して行う。
【００２８】
これは従来技術の２次元平面上のデータ転送と同等である。本実施の形態での転送では、本来データを送る必要がないプロセッシングエレメント１１を通過する可能性があるため、各プロセッシングエレメント１１に受信したデータの保持判定を行う手段としてデータ保持判定部２２を追加している。
【００２９】
各プロセッシングエレメント１１のデータ保持判定部２２は、隣接したプロセッシングエレメント１１からデータを受信した場合、データの転送元（送信元）の座標（ｘ，ｙ）と自身の座標（Ｘ，Ｙ）とを比較して、そのデータを保持するか否かを判定する。
【００３０】
より詳細に述べると、データ保持判定部２２は、Ｘｔｈ-≦Ｘ−ｘ≦Ｘｔｈ+かつＹｔｈ-≦Ｙ−ｙ≦Ｙｔｈ+であった場合に、受信したデータを保持すると判定（該当するデータであると判定）し、そのデータをデータ保持部２４に保持させるとともに、次のプロセッシングエレメント１１に転送させる。Ｘｔｈ-≦Ｘ−ｘ≦Ｘｔｈ+かつＹｔｈ-≦Ｙ−ｙ≦Ｙｔｈ+でなかった場合には、受信したデータを保持しないと判定（該当するデータではないと判定）し、そのデータはデータ保持部２４に保持させずに、次のプロセッシングエレメント１１に転送させる。データ保持部２４に保持させたデータは、そのプロセッシングエレメント１１での計算に使用する。ここで、Ｘｔｈ-，Ｘｔｈ+およびＹｔｈ-，Ｙｔｈ+は、予め設定した定数とする。
【００３１】
図６に本発明のデータ処理を画像処理に応用した例を示す。この例は、異なる時刻ｔ，ｔ-1，ｔ-2において取得した３枚のフレーム（１フレームは７×７ピクセル）からフレーム間で移動する物体のフローを抽出する画像処理の例を表している。具体的には、各ノード（ピクセル）間で特徴量の類似度を計算し、フレーム間で一番類似しているノードに物体が移動したと考える。
【００３２】
図７は図６で示した画像処理を図１に示したシステム１００における並列演算装置１０で行ったときのデータ配置を示しており、各セルはプロセッシングエレメント１１を表し、中央部の２１×７個のセル中、その色を濃淡の度合いで示した色付きのセルは、移動物体があるプロセッシングエレメント１１を表している。
【００３３】
これに図５を用いて説明したデータ転送方法を用いた場合、必要なセルにデータを転送するためには４４１サイクル必要になり、本来データを送る必要がないプロセッシングエレメント１１（斜線を引いたセル）を２９４回通過する。しかし、実装上必要となるプロセッシングエレメント数に関しては接続構成をトーラス状にすることで１４７個とすることができる。
【００３４】
〔実施の形態の拡張〕
以上、実施の形態を参照して本発明を説明したが、本発明は上記の実施の形態に限定されるものではない。本発明の構成や詳細には、本発明の技術思想の範囲内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００３５】
１０…並列演算装置（再生可能デバイス）、１１…プロセッシングエレメント（ＰＥ）、１２…転送制御部、１３…通信路、１４…全体制御部、１５…外部記憶装置、２０…データ転送部、２１…通信経路、２２…データ保持判定部、２３…転送制御部、２４…データ保持部、２５…演算部、１００…システム。
【図１】
2017207798.tif 000003
【図２】
2017207798.tif 000004
【図３】
2017207798.tif 000005
【図４】
2017207798.tif 000006
【図５】
2017207798.tif 000007
【図６】
2017207798.tif 000008
【図７】
2017207798.tif 000009