JP6583111B2 - 演算装置 - Google Patents

Description

本発明は、加算比較選択演算を繰り返し実行する演算装置に関する。

近年、自動車の事故防止や自動運転化のために、車載カメラによる測距や認識処理のニーズが高まっている。車載向けの画像処理装置は組み込みシステムのため、限られた性能およびリソースで要求時間内での処理を実現する必要がある。例えば、ステレオカメラは原理的に模様の少ない物体の測距が難しい。そのため、グローバル法という視差画像全体の滑らかさを考慮する手法を導入することにより、弱パタンである路面などもロバストに検出することができる手法が近年開発されている。このような方法の主なものとして、Viterbi（以下、ビタビと呼ぶ）アルゴリズムと呼ばれる動的計画法の一種により、全体のコストが最小になる視差の組み合わせを決定するものがある。

ビタビアルゴリズムの計算量としては、その遷移状態、つまりノードの数が増えると、指数関数的に処理量が増える。そして、ステレオカメラの場合、遷移状態数が視差の数（通常、数十〜数百以上の数）だけあるため、計算量が大きくなる。このような課題に対して、アルゴリズムに着目し、既に計算した隣の遷移状態の結果を再利用することにより、従来ではノード数の２乗に比例していた計算量を、ノード数の２倍程度の計算量に抑えることを実現する手法が考えられている（例えば、特許文献１参照）。このような手法によれば、処理時間の短縮が可能になるが、ステレオカメラの数百万画素にわたって上記処理を車載のような組み込み環境で実現するためには、更なる高速化が必要となる。

特開２０１５−１１４２６９号公報 特開２０１４−０４５４８０号公報

ビタビ演算の高速化の課題に対し、ビタビ演算の基本処理要素である加算・比較・選択（以下、ＡＣＳと呼ぶ）回路を直列に接続した専用回路が提案されている（例えば、特許文献２参照）。この手法によれば、単一のＡＣＳ回路を再帰的に用いる場合に比べ、クロックの受け渡しでの処理時間のオーバーヘッドを減らせる分だけ高速化が期待できる。しかし、この場合、通過するＡＣＳ回路の段数は少なくなっておらず、スループットの向上には限界がある。

本発明は上記事情に鑑みてなされたものであり、その目的は、演算の精度を良好に維持しつつ、演算の高速化を実現することができる演算装置を提供することにある。

請求項１に記載の演算装置（１２）は、複数の入力データのそれぞれに対し、前段の演算結果を用いる演算処理を所定の順序に従い実行する。その演算処理は、複数の入力データのうちいずれか１つの入力データと、前段の演算結果に所定の定数を加算したデータとを比較し、それら各データのうち予め定めた条件を満たす値を選択して演算結果として出力する加算比較選択演算である。上記演算装置は、複数の入力データに対する一連の演算処理を上記順序に沿って複数に分割し、それぞれを並列に実行する分割部（２１、２２、３１〜３４）と、上記順序が隣り合う２つの分割部のうち順序が後の分割部の各段から出力される演算結果のそれぞれに対し順序が前の分割部の最終段から出力される演算結果を一括比較して予め定めた条件を満たす値を選択して出力する統合処理を実行する統合部（２３、３５、４１）と、を備える。

このような構成によれば、一連の演算処理を複数に分割して並列に実行するので、一連の演算処理を逐次的に処理する場合に比べ、演算処理に要する時間が短縮される。また、統合部を設けたことにより、順序が後の分割部から出力される演算結果についても、順序が前の分割部における演算結果を考慮したものとなり、演算が不正確になることはない。したがって、本手段によれば、演算の精度を良好に維持しつつ、演算の高速化を実現することができる。

第１実施形態に係る距離検出装置の構成を模式的に示す図 処理部の具体的な構成を模式的に示す図 距離演算処理の内容を模式的に示すフローチャート コスト補正処理回路の構成を模式的に示す図 分割部におけるＡＣＳ回路の構成を模式的に示す図 統合部におけるＡＣＳ回路の構成を模式的に示す図 第２実施形態に係るコスト補正処理回路の第１構成例を模式的に示す図 第２実施形態に係るコスト補正処理回路の第２構成例を模式的に示す図

以下、本発明の複数の実施形態について図面を参照して説明する。なお、各実施形態において実質的に同一の構成には同一の符号を付して説明を省略する。
（第１実施形態）
以下、本発明の第１実施形態について図１〜図６を参照して説明する。
図１に示す距離検出装置１は、複数の撮像画像の視差を検出することによって撮像画像中の各点までの距離を検出する装置である。距離検出装置１では、動的計画法であるビタビアルゴリズムを複数の方向に適用することで複数の撮像画像を構成する画素間の対応関係、つまり視差を高精度に求めることができるように配慮されている。

距離検出装置１は、乗用車などの車両に搭載されており、２つの撮像部２、３、処理部４および車両制御部５を備えている。なお、撮像部２、３は、２つに限らずともよく、例えば３つ以上設けられていてもよい。撮像部２、３は、それぞれ車両の進行方向が撮像範囲内となる周知のカメラとして構成されている。撮像部２、３は、ステレオカメラを構成しており、周期的に同時に撮像を行うように設定されている。

処理部４は、撮像部２、３により撮像された撮像画像を取得し、後述する各種処理を実行する。車両制御部５は、処理部４による処理結果を用いて車両を制御する処理を実行する。例えば、車両制御部５は、撮像部２、３による撮像範囲内の各点における距離の情報を処理部４から取得し、その距離の情報に基づいて物標位置および相対速度を認識する。そして、車両制御部５は、物標が走行に支障をきたすおそれがある場合、走行軌道を変更するなどの車両制御を実行する。

処理部４の機能は、例えば、図２に示すような構成により実現することができる。すなわち、この場合、処理部４は、バス６を介して通信可能に接続されたＣＰＵ７、ＤＭＡコントローラ８、メインメモリ９および専用アクセラレータ１０により構成される。専用アクセラレータ１０は、プログラム制御部１１、コスト補正処理回路１２、その他演算回路１３、ロードストア制御回路１４、ローカルメモリ１５およびデータレジスタ１６を備えている。

上記構成の基本的な動作および機能は、次の通りである。すなわち、ホストＣＰＵ７は、専用アクセラレータ１０に対し、対象とする処理依頼を通知する。また、メインメモリ９から処理対象のデータがＤＭＡコントローラ８を介して専用アクセラレータ１０のローカルメモリ１５に順次転送される。

プログラム制御部１１は、ＣＰＵ７からの処理依頼に基づいて対象の処理プログラムを読み出し、各回路に対して対象処理や対象レジスタなどを指定する制御信号を送信する。ロードストア制御回路１４は、上記制御信号に基づいてローカルメモリ１５から複数データを単位とした配列をデータレジスタにロードまたはストアする。

コスト補正処理回路１２およびその他演算回路１３は、上記制御信号に基づいて対象レジスタのデータを読み出して処理を行い、レジスタに書き戻す。プログラム制御部１１は、処理プログラムが完了すると、ＣＰＵ７およびＤＭＡコントローラ８に完了通知を転送する。また、ローカルメモリ１５から完了した処理データがＤＭＡコントローラ８を介してメインメモリ９に転送される。その後、ホストＣＰＵ７は、次の処理を判断し、次の処理依頼を専用アクセラレータ１０に転送する。処理部４は、以上のような動作を繰り返すことにより、各種の処理を実行する。

本実施形態の距離検出装置１において、処理部４は、特開２０１５−１１４２６９号公報（以下、文献１とも呼ぶ）に開示された距離演算処理と同様の処理を行う。すなわち、図３に示すように、まず、ステップＳ１では、撮像部２、３により撮像された撮像画像が取得される。続くステップＳ２では、撮像画像のレンズによる画像の歪や姿勢のずれを補正するなどの処理が行われ、撮像された画像が平行化される。

ステップＳ３では、対応点探索処理が実施される。対応点探索処理は、例えば撮像部２による撮像画像である基準画像を構成する各画素と、例えば撮像部３による撮像画像である比較画像を構成する各画素との対応関係、つまり同じものが写っている場所を関連付ける処理である。対応点探索処理の具体的な内容は、文献１に開示されているため、ここでの説明は省略する。続いて、ステップＳ４では、各画素における対応点の視差に応じて各画素に写っている物標までの距離が算出される。そして、ステップＳ５では、これらの画素と距離との対応データが車両制御部５に対して出力される。

ただし、本実施形態では、対応点探索処理に対し、以下に説明するような工夫を加えることで、演算の更なる高速化を実現している。すなわち、文献１の対応点探索処理では、１つ前までの最小コスト結果を再利用することで総当たり計算を二項比較の反復に直し、処理負荷の削減が図られている。そして、本願の発明者は、このような文献１では「s(u,v)=u-v」としているが、「s(u,v)=λ│u-v│」であれば線形性が保たれることを見出した。ただし、λは所定の定数である。この場合、前の結果にλを加算して次のノードの値と比較し、小さいほうの値を次の結果とする、といったことが繰り返される。つまり、この場合、ＡＣＳ演算が基本の繰り返し単位となる。

ここで、ＡＣＳ演算を行うＡＣＳ回路を直列に接続する従来技術を用いると、１つ前の結果を用いる演算および選択が直列に反復処理される、つまり逐次的に処理されるため、多段接続による回路遅延などに起因する速度低下の影響が大きい。そこで、このような逐次処理を分割して並列に実行することが考えられる。しかし、演算結果がその後の演算に依存するような逐次処理を、単純に分割して並列化すると、計算が不正確になり、精度が低下するといった懸念がある。

これらの点を考慮し、本実施形態では、遷移コストの線形性を導入することを前提として、逐次処理を行う回路を複数のブロックに分割して並列動作させ、それら並列動作させた各ブロックにおける結果を一括比較して統合するようにした。具体的には、本実施形態のコスト補正処理回路１２は、図４に示すような構成を有している。なお、コスト補正処理回路１２は、複数の入力データのそれぞれに対し、前段の演算結果を用いる演算処理を所定の順序に従い実行する演算装置に相当する。

コスト補正処理回路１２は、逐次処理を行う回路を前半の分割部２１と後半の分割部２２とに分割して並列処理し、最後に統合部２３により各段の結果を統合する。なお、以下では、コスト補正処理回路１２に入力される入力データ配列の各データのことを入力データ［１］，入力データ［２］，…，入力データ［Ｎ］と呼び、コスト補正処理回路１２から出力される出力データ配列の各データのことを出力データ［１］，出力データ［２］，…，出力データ［Ｎ］と呼ぶこととする。また、本実施形態では、これらのデータ数Ｎは、偶数となっている。

前半の分割部２１は、入力データ［２］〜［Ｎ／２］をそれぞれ入力データとするＡＣＳ回路２４［２］〜２４［Ｎ／２］を備えている。また、後半の分割部２２は、入力データ［Ｎ／２＋２］〜［Ｎ］をそれぞれ入力データとするＡＣＳ回路２４［Ｎ／２＋２］〜２４［Ｎ］を備えている。なお、以下では、ＡＣＳ回路２４［２］〜ＡＣＳ回路２４［Ｎ］のことをＡＣＳ回路２４と総称することがある。

ＡＣＳ回路２４は、図５に示すような構成となっている。すなわち、ＡＣＳ回路２４は、加算器２５および比較選択器２６を備えている。加算器２５は、前段から出力される演算結果に定数λを加算する。なお、本実施形態では、定数λは正の値となっており、加算器２５は純粋に加算を行うものである。また、定数λの値は、レジスタ設定などにより適宜変更することが可能となっている。比較選択器２６は、加算器２５の出力データと本段の入力データとを比較し、それら各データのうち予め定めた条件を満たす値を選択して本段の演算結果として出力する。具体的には、比較選択器２６は、各データのうちいずれか小さいほうの値を選択して本段の演算結果として出力する。

例えば、ＡＣＳ回路２４［２］は、入力データ［１］に定数λを加算して入力データ［２］と比較し、小さいほうの値を本段の演算結果として出力するとともに、次段のＡＣＳ回路２４［３］に対し前段の演算結果として出力する。そして、次段のＡＣＳ回路２４［３］は、ＡＣＳ回路２４［２］から出力された前段の演算結果に定数λを加算して入力データ［３］と比較し、いずれか小さいほうの値を本段の演算結果として出力するとともに、次段のＡＣＳ回路２４［４］に対し前段の演算結果として出力する。

また、ＡＣＳ回路２４［Ｎ／２＋２］は、入力データ［Ｎ／２＋１］に定数λを加算して入力データ［Ｎ／２＋２］と比較し、小さいほうの値を本段の演算結果として統合部２３に出力するとともに、次段のＡＣＳ回路２４［Ｎ／２＋３］に対し前段の演算結果として出力する。そして、次段のＡＣＳ回路２４［Ｎ／２＋３］は、ＡＣＳ回路２４［Ｎ／２＋２］から出力された前段の演算結果に定数λを加算して入力データ［Ｎ／２＋３］と比較し、いずれか小さいほうの値を本段の演算結果として統合部２３に出力するとともに、次段のＡＣＳ回路２４［Ｎ／２＋４］に対し前段の演算結果として出力する。

このような構成において、入力データ［１］がそのまま出力データ［１］となり、前半の分割部２１が備えるＡＣＳ回路２４［２］〜２４［Ｎ／２］から出力される演算結果が、それぞれ出力データ［２］〜［Ｎ／２］となる。ただし、ＡＣＳ回路２４［Ｎ／２］から出力される演算結果は、統合部２３にも与えられる。

統合部２３は、分割部２２の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［Ｎ／２＋１］〜２７［Ｎ］を備えている。なお、以下では、ＡＣＳ回路２７［Ｎ／２＋１］〜ＡＣＳ回路２７［Ｎ］のことをＡＣＳ回路２７と総称することがある。

ＡＣＳ回路２７は、図６に示すような構成となっている。すなわち、ＡＣＳ回路２７は、加算器２８および比較選択器２９を備えている。加算器２８は、前半の最終段の結果、つまりＡＣＳ回路２４［Ｎ／２］から出力される演算結果にαを加算する。αは、後半における順番を表す数に定数λを乗じた値である。

例えば、ＡＣＳ回路２７［Ｎ／２＋１］の場合、後半における順番が「１」であるため「α＝１×λ」となり、ＡＣＳ回路２７［Ｎ／２＋２］の場合、後半における順番が「２」であるため「α＝２×λ」となり、ＡＣＳ回路２７［Ｎ］の場合、後半における順番が「Ｎ／２」であるため「α＝（Ｎ／２）×λ」となる。したがって、ＡＣＳ回路２７［Ｘ］とすると、αは下記（１）で表される。
α＝（Ｘ−Ｎ／２）×λ …（１）

比較選択器２９は、加算器２８の出力データと分割部２２の各段から出力される演算結果とを比較し、いずれか小さいほうの値を後半の各段の最終結果として出力する。例えば、ＡＣＳ回路２７［Ｎ／２＋１］は、前半の最終段の演算結果にα（＝１×λ）を加算して入力データ［Ｎ／２＋１］と比較し、小さいほうの値を本段の最終結果、つまり出力データ［Ｎ／２＋１］として出力する。また、ＡＣＳ回路２７［Ｎ／２＋２］は、前半の最終段の演算結果にα（＝２×λ）を加算してＡＣＳ回路２４［Ｎ／２＋２］から出力される演算結果と比較し、小さいほうの値を本段の最終結果、つまり出力データ［Ｎ／２＋２］として出力する。

このようなＡＣＳ回路２７を有する統合部２３は、分割部２１の最終段の演算結果と比例関係にあるデータ（＝加算器２８の出力データ）と、分割部２２の各段から出力される演算結果とを比較し、いずれか小さいほうの値を一連のＡＣＳ演算処理における後半の各段の最終結果として出力するようになっている。つまり、統合部２３は、後半の分割部２２の各段から出力される演算結果のそれぞれに対し前半の分割部２１の最終段から出力される演算結果を一括比較して統合するようになっている。

以上説明した本実施形態によれば、次のような効果が得られる。
本実施形態のコスト補正処理回路１２は、入力データ配列の各入力データ［１］〜［Ｎ］のそれぞれに対し、前段の演算結果を用いるＡＣＳ演算を入力データ配列の順序に従い実行する。そして、コスト補正処理回路１２は、複数の入力データ［１］〜［Ｎ］に対する一連のＡＣＳ演算処理を上記順序に沿って前半と後半に分割し、それぞれを並列に実行する分割部２１、２２と、後半の分割部２２の各段から出力される演算結果のそれぞれに対し前半の分割部２１の最終段から出力される演算結果を一括比較して統合する統合部２３と、を備えている。

このような構成によれば、一連のＡＣＳ演算処理を２つに分割して並列に実行するので、一連のＡＣＳ演算処理を逐次的に処理する場合に比べ、回路遅延の短縮などを期待することができ、その結果、演算処理に要する時間が約半分程度に短縮される。しかも一連のＡＣＳ演算処理を単純に並列化しただけでなく、統合部２３を設けているため、後半の分割部２２から出力される演算結果についても、前半の分割部２１での演算結果を考慮したものとなり、演算が不正確になるおそれはない。したがって、本実施形態によれば、演算の精度を良好に維持しつつ、演算の高速化を実現することができる。このような演算の高速化、つまり処理時間の削減による効果は、車載のような組み込み環境において、一層有益なものとなる。

（第２実施形態）
第１実施形態では、コスト補正処理回路１２は、複数の入力データ［１］〜［Ｎ］に対する一連のＡＣＳ演算処理を前半と後半の２つに分割していたが、この分割数は３つ以上でもよい。本実施形態では、一連のＡＣＳ演算処理を４つに分割した２つの構成例について図７および図８を参照して説明する。

＜第１構成例＞
図７に示すように、第１構成例では、一連のＡＣＳ演算処理を入力データ配列の順序に沿って４つの分割部３１〜３４に分割して並列処理し、最後に統合部３５により各段の結果を統合する。分割部３１は、入力データ［２］〜［Ｎ／４］をそれぞれ入力データとするＡＣＳ回路２４［２］〜２４［Ｎ／４］を備えている。分割部３２は、入力データ［Ｎ／４＋２］〜［Ｎ／２］をそれぞれ入力データとするＡＣＳ回路２４［Ｎ／４＋２］〜２４［Ｎ／２］を備えている。

分割部３３は、入力データ［Ｎ／２＋２］〜［３Ｎ／４］をそれぞれ入力データとするＡＣＳ回路２４［Ｎ／２＋２］〜２４［３Ｎ／４］を備えている。分割部３４は、入力データ［３Ｎ／４＋２］〜［Ｎ］をそれぞれ入力データとするＡＣＳ回路２４［３Ｎ／４＋２］〜２４［Ｎ］を備えている。

このような構成において、入力データ［１］がそのまま出力データ［１］となり、分割部３１が備えるＡＣＳ回路２４［２］〜２４［Ｎ／４］から出力される演算結果が、それぞれ出力データ［２］〜［Ｎ／４］となる。ただし、ＡＣＳ回路２４［Ｎ／４］から出力される演算結果は、統合部３５にも与えられる。

統合部３５は、第１統合ブロック３５ａ、第２統合ブロック３５ｂおよび第３統合ブロック３５ｃを備えている。第１統合ブロック３５ａは、分割部３２の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［Ｎ／４＋１］〜２７［Ｎ／２］を備えている。ＡＣＳ回路２７［Ｎ／４＋１］〜２７［Ｎ／２］の加算器２８は、分割部３１の最終段の結果、つまりＡＣＳ回路２４［Ｎ／４］から出力される演算結果にαを加算するようになっている。したがって、第１統合ブロック３５ａは、分割部３１の最終段の演算結果と比例関係にあるデータと、分割部３２の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［Ｎ／４＋１］〜［Ｎ／２］として出力する。

第２統合ブロック３５ｂは、分割部３３の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［Ｎ／２＋１］〜２７［３Ｎ／４］を備えている。ＡＣＳ回路２７［Ｎ／２＋１］〜２７［３Ｎ／４］の加算器２８は、第１統合ブロック３５ａの最終段の結果、つまりＡＣＳ回路２７［Ｎ／２］から出力される演算結果にαを加算するようになっている。したがって、第２統合ブロック３５ｂは、分割部３２の最終段から出力されて第１統合ブロック３５ａを介して統合が行われた後の演算結果である出力データ［Ｎ／２］と比例関係にあるデータと、分割部３３の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［Ｎ／２＋１］〜［３Ｎ／４］として出力する。

第３統合ブロック３５ｃは、分割部３４の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［３Ｎ／４＋１］〜２７［Ｎ］を備えている。ＡＣＳ回路２７［３Ｎ／４＋１］〜２７［Ｎ］の加算器２８は、第２統合ブロック３５ｂの最終段の結果、つまりＡＣＳ回路２７［３Ｎ／４］から出力される演算結果にαを加算するようになっている。したがって、第３統合ブロック３５ｃは、分割部３３の最終段から出力されて第２統合ブロック３５ｂを介して統合が行われた後の演算結果である出力データ［３Ｎ／４］と比例関係にあるデータと、分割部３４の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［３Ｎ／４＋１］〜［Ｎ］として出力する。

このように、第１構成例の統合部３５は、順序が１番目、２番目の分割部３１、３２を組にして統合処理を行い、順序が３番目以降の分割部３３、３４の各段から出力される演算結果のそれぞれに対し、それらより順序が１つ前の分割部から出力されて統合処理が行われた後の演算結果を一括比較して統合し、最終結果として出力するようになっている。なお、この場合、統合部３５では、「（１）第１統合ブロック３５ａによる統合→（２）第２統合ブロック３５ｂによる統合→（３）第３統合ブロック３５ｃによる統合」という順に、３段階で統合処理が行われることになる。

＜第２構成例＞
図８に示すように、第２構成例では、第１構成例と同様に、一連のＡＣＳ演算処理を入力データ配列の順序に沿って４つの分割部３１〜３４に分割して並列処理し、最後に統合部４１により各段の結果を統合する。統合部４１は、第１統合ブロック４１ａ、第２統合ブロック４１ｂおよび第３統合ブロック４１ｃを備えている。

第１統合ブロック４１ａは、第１構成例の第１統合ブロック３５ａと同様の構成となっている。したがって、第１統合ブロック４１ａは、分割部３１の最終段の演算結果と比例関係にあるデータと、分割部３２の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［Ｎ／４＋１］〜［Ｎ／２］として出力する。

第２統合ブロック４１ｂは、分割部３４の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［３Ｎ／４＋１］〜２７［Ｎ］を備えている。ＡＣＳ回路２７［３Ｎ／４＋１］〜２７［Ｎ］の加算器２８は、分割部３３の最終段の結果、つまりＡＣＳ回路２４［３Ｎ／４］から出力される演算結果にαを加算するようになっている。したがって、第２統合ブロック４１ｂは、分割部３３の最終段の演算結果と比例関係にあるデータと、分割部３４の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力する。

第３統合ブロック４１ｃは、分割部３３の各段の出力をそれぞれ入力データとするＡＣＳ回路２７［Ｎ／２＋１］〜２７［３Ｎ／４］と、第２統合ブロック４１ｂの各段の出力をそれぞれ入力データとするＡＣＳ回路４２［３Ｎ／４＋１］〜４２［Ｎ］と、を備えている。なお、ＡＣＳ回路４２［３Ｎ／４＋１］〜４２［Ｎ］は、ＡＣＳ回路２７と同様の構成である。また、以下では、ＡＣＳ回路４２［３Ｎ／４＋１］〜４２［Ｎ］のことをＡＣＳ回路４２と総称することがある。

ＡＣＳ回路２７［Ｎ／２＋１］〜２７［３Ｎ／４］およびＡＣＳ回路４２［３Ｎ／４＋１］〜４２［Ｎ］の加算器２８は、第１統合ブロック４１ａの最終段の結果、つまりＡＣＳ回路２７［Ｎ／２］から出力される演算結果にαを加算するようになっている。したがって、第３統合ブロック４１ｃは、分割部３２の最終段から出力されて第１統合ブロック４１ａを介して統合が行われた後の演算結果である出力データ［Ｎ／２］と比例関係にあるデータと、分割部３３の各段から出力される演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［Ｎ／２＋１］〜［３Ｎ／４］として出力する。また、第３統合ブロック４１ｃは、出力データ［Ｎ／２］と比例関係にあるデータと、分割部３４の各段から出力されて第２統合ブロック４１ｂを介して統合が行われた後の演算結果とを比較し、いずれか小さいほうの値を選択して出力データ［３Ｎ／４＋１］〜［Ｎ］として出力する。

このように、第２構成例の統合部４１は、順序が隣り合う２つの分割部３１、３２を組にして統合処理を行うとともに、順序が隣り合う２つの分割部３３、３４を組にして統合処理を行う。そして、統合部４１は、統合処理が行われた２つの組に対してさらに統合処理を行い、最終結果として出力するようになっている。なお、この場合、統合部４１では、「（１）第１統合ブロック４１ａによる統合および第２統合ブロック４１ｂによる統合→（２）第３統合ブロック４１ｃによる統合」という順に、２段階で統合処理が行われることになる。

以上説明した本実施形態によっても、第１実施形態と同様に、演算の精度を良好に維持しつつ、演算の高速化を実現することができる。なお、第１構成例および第２構成例は、それぞれにメリットがある。すなわち、第１構成例の統合部３５は、第２構成例の統合部４１に比べ、ＡＣＳ回路の数を少なくできるため、その回路規模を小さくすることができる。また、第２構成例の統合部４１は、第１構成例の統合部３５に比べ、ＡＣＳ回路を通過する段数を小さく抑えることができるため、演算処理に要する時間を更に短縮することができる。したがって、一連のＡＣＳ演算処理の分割数を４以上にする場合、このような点を考慮したうえで、回路規模や処理時間などの仕様を満たすように、最適な構成を用いればよい。

（その他の実施形態）
なお、本発明は上記し且つ図面に記載した各実施形態に限定されるものではなく、その要旨を逸脱しない範囲で任意に変形、組み合わせ、あるいは拡張することができる。
上記各実施形態では、ＡＣＳ演算は「加算→最小比較」であったが、「減算→最大比較」としてもよい。すなわち、上記各実施形態では定数λを正の値としていたが、これを負の値としてもよい。そうすると、加算器２５、２８は、実質的に減算を行うものとなる。この場合、比較選択器２６、２９は、２つの入力値のうち、いずれか大きいほうの値を選択して演算結果として出力すればよい。つまり、この場合、いずれか大きい値が「予め定めた条件を満たす値」となる。
上記各実施形態では、一連のＡＣＳ演算処理を分割する際、それぞれの分割部を等分するようにしていたが、必ずしも等分する必要はない。また、上記各実施形態では、入力データ配列のデータ数Ｎは偶数としていたが、データ数Ｎは奇数でもよい。

上記各実施形態では一連のＡＣＳ演算処理を、入力データ配列の順序に沿って複数に分割していたが、これに限らずともよく、所定の順序に沿って複数に分割すればよい。
統合部２３、３５、４１のＡＣＳ回路のうち、後段部分を省略することも可能である。例えば、統合部における所定のＡＣＳ回路での比較選択において加算器側のデータが最小値ではないとされて一旦棄却された場合、その後段のＡＣＳ回路での比較選択においても必ず加算器側のデータは棄却される。そこで、予め実験やシミュレーションなどで、統合部の後半のある所で非常に高い確率で加算器側のデータが棄却されることが判明していれば、それ以降はＡＣＳ回路を省略し、前段の演算結果を一括比較して統合する処理を行わないことも可能である。このようにすれば、回路規模を小さくできるという効果が得られる。なお、このようにした場合でも、大きく演算の精度が低下することはない。

１２…コスト補正処理回路、２１、２２、３１〜３４…分割部、２３、３５、４１…統合部。

Claims (4)

1. 複数の入力データのそれぞれに対し、前段の演算結果を用いる演算処理を所定の順序に従い実行する演算装置（１２）であって、
   前記演算処理は、前記複数の入力データのうちいずれか１つの入力データと、前段の演算結果に所定の定数を加算したデータとを比較し、それら各データのうち予め定めた条件を満たす値を選択して演算結果として出力する加算比較選択演算であり、
   前記複数の入力データに対する一連の前記演算処理を、前記順序に沿って複数に分割し、それぞれを並列に実行する分割部（２１、２２、３１〜３４）と、
   前記順序が隣り合う２つの分割部のうち前記順序が後の分割部の各段から出力される演算結果のそれぞれに対し前記順序が前の分割部の最終段から出力される演算結果を一括比較して予め定めた条件を満たす値を選択して出力する統合処理を実行する統合部（２３、３５、４１）と、
   を備える演算装置。
2. 前記分割部（２１、２２）は、前記複数の入力データに対する一連の前記演算処理を、前記順序の前半および後半の２つに分割し、それぞれを並列に実行するものであり、
   前記統合部（２３）は、後半の前記分割部の各段から出力される演算結果のそれぞれに対し、前半の前記分割部の最終段から出力される演算結果を一括比較して予め定めた条件を満たす値を選択して出力する請求項１に記載の演算装置。
3. 前記分割部（３１〜３４）は、前記複数の入力データに対する一連の前記演算処理を、前記順序に沿って３つ以上に分割し、それぞれを並列に実行するものであり、
   前記統合部（３５）は、前記順序が３番目以降の分割部の各段から出力される演算結果のそれぞれに対し、当該分割部より前記順序が１つ前の分割部から出力されて前記統合が行われた後の演算結果を一括比較して予め定めた条件を満たす値を選択して出力する請求項１に記載の演算装置。
4. 前記分割部（３１〜３４）は、前記複数の入力データに対する一連の前記演算処理を、前記順序に沿って３つ以上に分割し、それぞれを並列に実行するものであり、
   前記統合部（４１）は、前記順序が隣り合う２つの分割部を組に対して前記統合処理を実行し、前記統合処理が実行された組のうち順序が隣り合う２つの組に対してさらに前記統合処理を実行する請求項１に記載の演算装置。

Images