JP4825154B2 - データ処理装置 - Google Patents

Description

本発明は、データ処理装置、特にＳＩＭＤ型マイクロプロセッサに関する。

画像処理においては、所定範囲の全画素データの最大値又は最小値を特徴量として画像処理の計算式を設定・変更するというような処理が必要となることがある。多データを一度に演算するという特徴が画像処理に向いているとされるＳＩＭＤ型マイクロプロセッサにおいて、各プロセッサエレメント（以下、ＰＥという。）に格納される画素データのうちから、最大値又は最小値を選出することを実現する技術が、従来幾つか開示されている。

特許文献１や特許文献２で開示されている技術は、基本的に逐次処理に関するものである。その技術は、全てのＰＥから対象画素データを読み出し、逐次大小比較を行った結果大きい方を残す、又は小さい方を残すことにより、全対象画素データの最大値又は最小値を求めるというものである。この技術には、検出までに要する時間が、対象画素の数が大きくなるに従い大きくなるという特徴があり、ＰＥ数の多いプロセッサには適切な技術ではないといえる。

特許文献３で開示される技術も基本的に逐次処理に関する。特許文献１や特許文献２で開示されている技術とは異なり、各ＰＥの持つデータを順次、全ＰＥに供給し、比較結果を収集することで最大値あるいは最小値を求めるという技術であるが、特許文献１や特許文献２で開示されている技術と同様の長所・短所を持つといえる。

特許文献４では、ＰＥ間にツリー状に演算器を設け、各ツリーにパイプラインを切ることによって演算器の負荷を少なく保持したまま、最大値を検出したり総和を演算したりすることを高速に行う回路構成について開示している。この構成では、ＰＥ数が増加すると演算器の数が増加し、回路規模の増大につながること、及びツリーの最後には全ＰＥ長の半分の距離を跨いだ演算が必要になることから、動作速度の面で懸念がある。特許文献５でも基本的に同様の技術を開示する。

特許文献６と特許文献７で開示される技術は、上位ビットから順に１ビットずつ比較を行い、フラグを用いることで最大値又は最小値の候補から外れたものを除外していくというものである。このような技術では、対象データのビット幅の数だけ処理を繰り返すと最大値又は最小値を得ることができるが、対象データ数が多いと１回の処理にかかる時間が増大するという問題が生じる。

特許文献８は、比較対象データをまずデコードしておき、そのデコード結果の論理和を求めることで最大値、最小値検出を行う回路構成を開示する。この回路構成では、比較対象データのビット幅が広い場合、対象データ数が多い場合についての問題点が解決されていない。
特開２００１−２６５５９２号公報 特開平０８−０３０５７７号公報 特許第２９６９１１５号 特公平８−１４８１６号公報 特開２００２−２０７７０６号公報 特開平０５−１００８２４号公報 特開平０６−１３９０４８号公報 特開平１１−８５４６７号公報

本発明は、前述の従来技術の問題点を考慮して、少ない回路規模を保ったまま最大値又は最小値を短いサイクルで選出することのできるデータ処理装置、特にマイクロプロセッサを構築することを目的とする。つまり、マイクロプロセッサにおいて、２進データの数が多い場合にも短いサイクルで最大値又は最小値を求めることができること、２進データのビット幅が広い場合でも回路規模を増やすことなく最大値又は最小値を求めることができること、及び、特にＳＩＭＤ型などの並列プロセッサが処理しているデータの中から最大値又は最小値を回路規模を増やさずに求めることができることを目的とする。

本発明は、上記の目的を達成するために為されたものである。本発明に係る請求項１に記載のデータ処理装置は、複数の２進データの中から最大値又は最小値を求めるデータ処理装置であって、
２進データと同数以上の条件フラグと、
各２進データをデコードするための２進データと同数以上のデコーダと、
２進データと同数以上の比較器と、
各デコーダからのデコード結果がＷｉｒｅｄ−ＯＲされて出力される１ビット毎のバスを有し、
各条件フラグと各デコーダと各比較器は、対象の２進データに対して関連付けされており、
上記デコーダによるデコード結果は、関連する条件フラグの値が真であれば１ビット毎にＷｉｒｅｄ−ＯＲされてバスに出力され、関連する条件フラグが偽であればバスに出力されず、
各比較器は、関連するデコーダのデコード結果の値とＷｉｒｅｄ−ＯＲされたバスの値とを比較し、Ｗｉｒｅｄ−ＯＲされたバス値よりもデコード結果の方が小さい場合には、関連する条件フラグの値をリセットすることを特徴とする。

本発明に係る請求項２に記載のデータ処理装置は、
更に、関連する条件フラグ、デコーダ、及び比較器に対して、ビットシフト回路が関連付けされて設置され、
各ビットシフト回路は各２進データを入力して所定幅だけビットシフトして関連するデコーダに出力し、
複数の２進データのビット幅の中の特定部分のビット幅のデータに関して最大値又は最小値を算出することを特徴とする請求項１に記載のデータ処理装置である。

本発明に係る請求項３に記載のデータ処理装置は、
各デコーダが、
デコード結果として、ＬＳＢビットから、入力データをデコードして“１”となったビットまでを、“１”として出力し、それ以外のビットを“０”として出力する、
又は、その負論理を出力するように構成されていることを特徴とする請求項１に記載のデータ処理装置である。

本発明に係る請求項４に記載のデータ処理装置は、
請求項１乃至３のうちのいずれか一に記載のデータ処理装置であって、
比較器が、複数の２進データを演算処理するための算術演算装置（ＡＬＵ）で構成されていることを特徴とする。

本発明を利用することにより、データ処理装置において、対象となる２進データの数が多い場合にも、短いサイクルでそれら多数の２進データの最大値又は最小値を求めることが可能になる。

以下、図面を参照して本発明に係る好適な実施形態を説明する。

［第１の実施形態］

図１０は、本発明に係るマイクロプロセッサ２の概略の構成図である。図１０に示されるマイクロプロセッサ２は、プロセッサエレメント（４−（１）、４−（２）、・・・４−（ｎ））を複数（図ではｎ個）備えており、各プロセッサエレメント４は図示しないレジスタ及び演算部を備える。各プロセッサエレメント４は適宜接続されており、図示しないグローバルプロセッサなどにより動作を制御される。このような並列プロセッサは通常「ＳＩＭＤ型マイクロプロセッサ」と称されるものである。

図１は、本発明の第１の実施形態に係るマイクロプロセッサ２の一部拡大図である。特に、３つのプロセッサエレメントの夫々の一部分を示している。ここでは、比較対象となる２進データが４ビットであり、比較対象となる２進データは対象データ１〜対象データ３までの３つである場合について、図示している。対象データ１〜対象データ３は、例えば夫々レジスタ（図示せず。）に記憶されており、それらがデコーダ（デコーダ１、デコーダ２、デコーダ３）に入力する。

デコーダ（デコーダ１、デコーダ２、デコーダ３）には、上記２進データと、夫々の条件フラグの値とが入力される。各デコーダの構成は、図２に示しているようなものである。各デコーダは２進データをデコードした結果を、３ステートバッファを介して、図１下部に示すバスに出力する。図２に示されるように、３ステートバッファの出力イネーブル信号には条件フラグが接続される。つまり、条件フラグが真の状態であるプロセッサエレメントでは、３ステートバッファを介してデコード結果がバスに出力される。

なお、３ステートバッファに代わりに、ダイナミックバス構成若しくはオープンドレイン構成を採用しても同様の作用を行うことができることは明白である。

比較器（比較器１、比較器２、比較器３）には、各デコーダからの出力とバス上のデータとが入力され、比較器での比較結果が条件フラグのリセット端子に接続されている。

図３は、本発明の第１の実施形態に係るマイクロプロセッサに含まれる比較器の構成図（図３（ｂ））、及び、機能内容（図３（ａ））を示す。図３（ａ）は、図３（ｂ）の比較器を構成する２種類の比較素子、即ちＣＭＰ１とＣＭＰ２の動作内容を示す記述である。

図１、図２及び図３に示す構成を備えるマイクロプロセッサは、以下の工程のようにして、３つの対象データの中から最大値を求める。なお、対象データ１、対象データ２、及び、対象データ３は、例として、（１０１０ｂ）、（０１１１ｂ）、（１００１ｂ）であるとする。

（工程１）；全ての条件フラグを“1”にセットする。

（工程２−１）；デコーダの出力及びバス上のデータは、以下の表１のようになる。

（工程２−２）；比較結果は以下の表２のようになる。

（工程２−３）；結果として条件フラグ２と条件フラグ３はリセットされ、デコーダの出力およびバス上のデータは以下の表３のようになり、最大値が求まる。

ここで、バス上のデータ“( 0000010000000000b )”をエンコードして“1010b”が得られる。

以上、３つのデータにおける最大値を求めることについて説明をしたが、これより多数のデータにおける最大値を求める場合も同様にすればよい。また、２進データの反転をデコーダに入力し、バス上のデータのビット順をスワップ（交換）してエンコードすることで、最小値を求めることが可能である。

［第２の実施形態］
図４は、本発明の第２の実施形態に係るマイクロプロセッサ２の一部拡大図である。特に、３つのプロセッサエレメントの夫々の一部分を示している。本発明の第２の実施形態に係るマイクロプロセッサは、本発明の第１の実施形態に係るマイクロプロセッサと略同様のものであるので、両者の差異を中心に説明する。

ここでは、比較対象となる２進データが１６ビットであり、比較対象となる２進データは対象データ１〜対象データ３までの３つである場合について図示している。対象データ１〜対象データ３は、例えば夫々レジスタ（図示せず。）に記憶されており、それらがバレルシフタに入力され、バレルシフタで任意のビット数だけシフトされその結果の４ビットがデコーダ（デコータ１、デコーダ２、デコーダ３）に入力される。

例えば、１６ビットデータが右シフトされ、シフト結果の下位４ビットがデコーダに入力される。かかる構成によれば、以下のようにして３つの１６ビットデータの中から最大値が求められ得る。なお、対象データ１、対象データ２、及び、対象データ３は、例として、（３２ＦＦｈ）、（３７５０ｈ）、（２８９Ｃｈ）であるとする。

（工程１）；全ての条件フラグを“1”にセットする。

（工程２-１）；バレルシフタで右１２ビットシフトした結果の下位４ビットをデコーダに出力する。デコーダの出力およびバス上のデータは以下の表４のようになる。

（工程２−２）；各比較器における比較結果は以下の表５のようになる。

結果として条件フラグ３はリセットされ、デコーダの出力およびバス上のデータは以下の表６のようになり、ビット１５〜１２における最大値が求まる。

ここで、バス上のデータ“( 0000000000001000b )”をエンコードして“0011b (3h)”が得られる。

（工程３-１）；バレルシフタで右８ビットシフトした結果の下位４ビットをデコーダに出力する。デコーダの出力およびバス上のデータは以下の表７のようになる。

（工程３−２）；各比較器における比較結果は以下の表８のようになる。

結果として条件フラグ１と条件フラグ３はリセットされ、デコーダの出力およびバス上のデータは以下の表９のようになり、ビット１１〜８における最大値が求まる。

ここで、バス上のデータ“( 0000000010000000b )”をエンコードして“0111b (7h)”が得られる。

上記例では、ここで最大値が求まったことになる。この時点で未だ求まらなければ、前述と同様に、バレルシフタで右４ビットシフトした結果の下位４ビットをデコーダに出力することで、ビット７〜４における最大値を求めて、全体の最大値を求める。その時点でも未だ求まらなければ、更にバレルシフタで右０ビットシフトした（即ち、シフトしない）結果の下位４ビットをデコーダに出力することで、ビット３〜０における最大値を求めて、全体の最大値を求める。つまり、最後までリセットされない条件フラグを含むプロセッサエレメントにおける対象データが、最大値である。

以上、３つのデータにおける最大値を求めることについて説明をしたが、これより多数のデータにおける最大値を求める場合も同様にすればよい。

［第３の実施形態］
図５は、本発明の第３の実施形態に係るマイクロプロセッサにおけるデコーダの回路構成図である。

図１に示す第１の実施形態に係るマイクロプロセッサ、および図４に示す第２の実施形態に係るマイクロプロセッサにおいて、デコーダを、図２に示すものから図５に示すものに入れ替えると、比較器の構成を通常の比較器又は減算器にすることが可能である。

対象データ１（１０１０ｂ）、対象データ２（０１１１ｂ）、対象データ３（１００１ｂ）の場合で説明すると、デコーダの出力およびバス上のデータは以下の表１０のようになる。

このように、バス上のデータは最大数を持つデコーダ１と全く同一となることがわかる。従って、比較器として、図６で示すような単純なコンパレータ、若しくは、（図示しない）減算器を用いることが可能となる。

［第４の実施形態］
図７は、本発明の第４の実施形態に係るマイクロプロセッサ２の一部拡大図である。特に、３つのプロセッサエレメントの夫々の一部分を示している。本発明の第４の実施形態に係るマイクロプロセッサは、本発明の第３の実施形態に係るマイクロプロセッサと略同様のものであるので、両者の差異を中心に説明する。

図７に示す第４の第４の実施形態に係るマイクロプロセッサでは、図１に示す第１の実施形態に係るマイクロプロセッサ、および図４に示す第２の実施形態に係るマイクロプロセッサにおいて、デコーダを、図２に示すものから図５に示すものに入れ替え、更に、比較器（比較器１、比較器２、比較器３）を、ＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ Ｌｏｇｉｃａｌ Ｕｎｉｔ；数値演算ユニット）（ＡＬＵ１、ＡＬＵ２、ＡＬＵ３）に入れ替える。更に、（図示していないが、）ＡＬＵ（ＡＬＵ１、ＡＬＵ２、ＡＬＵ３）には、デコーダの出力とバスのデータのみならず、（図示しない）アキュムレータのデータと（図示しない）レジスタからの２進データとが入力されるように構成されている。

かかる構成は、通常の並列マイクロプロセッサに対して、デコーダ、条件フラグ、及びデコード結果のＷｉｒｅｄ−ＯＲ結果を出力するバスを追加設定すれば、実現される。このような追加設定によって、多数のデータにおける最大値又は最小値を求めることができるようになる。

更に、図８は、本発明の第４の実施形態に係るマイクロプロセッサ２の別例の一部拡大図である。この別例では、デコーダの出力がバスに出力されるのではなく、一旦アキュムレータ１２に格納され、アキュムレータ１２の出力が条件フラグの値に拠ってバスに供給される。アキュムレータ１２は、多数のデータにおける最大値又は最小値を求めるとき以外は、ＡＬＵでの演算結果を格納する。即ち、通常のアキュムレータとして機能する。

この構成は、多数のデータにおける最大値又は最小値を求めるときに必要なバスと、その他の通常の演算で利用されるバスとを共通化するものである。この構成により、回路全体をコンパクトにできるといえる。

［第５の実施形態］
図９は、本発明の第５の実施形態に係るマイクロプロセッサ２の一部拡大図である。本発明の第５の実施形態に係るマイクロプロセッサは、図８に示す本発明の第４の実施形態に係るマイクロプロセッサの別例と略同様のものである。

図９に示す第５の実施形態に係るマイクロプロセッサでは、アキュムレータよりバスに出力された値が一度、外部レジスタ２０に格納され、そのレジスタ２０の値が別のバスを介してＡＬＵ（ＡＬＵ１、ＡＬＵ２、ＡＬＵ３）に入力される。

かかる構成によれば、Ｗｉｒｅｄ−ＯＲされた結果の値が一度、レジスタ２０に格納されるため、次のサイクルでＷｉｒｅｄ−ＯＲ結果の値と各アキュムレータの値との比較を行うことができる。このように構成することによって、プロセッサエレメントの数が増加してもマイクロプロセッサ全体において高速動作を行うことが可能となる。

本発明の第１の実施形態に係るマイクロプロセッサの一部拡大図である。 本発明の第１の実施形態に係るマイクロプロセッサで利用されるデコーダの概略の構成図である。 本発明の第１の実施形態に係るマイクロプロセッサに含まれる比較器の構成図（図３（ｂ））、及び、機能内容（図３（ａ））である。 本発明の第２の実施形態に係るマイクロプロセッサの一部拡大図である。 本発明の第３の実施形態に係るマイクロプロセッサにおけるデコーダの回路構成図である。 本発明の第３の実施形態に係るマイクロプロセッサで利用されるコンパレータの概略の構成図である。 本発明の第４の実施形態に係るマイクロプロセッサの一部拡大図である。 本発明の第４の実施形態に係るマイクロプロセッサの別例の一部拡大図である。 本発明の第５の実施形態に係るマイクロプロセッサの一部拡大図である。 本発明に係るマイクロプロセッサの概略の構成図である。

符号の説明

２・・・マイクロプロセッサ、４・・・プロセッサエレメント、１０・・・バレルシフタ、１２・・・アキュムレータ、２０・・・外部レジスタ。

Claims (4)

1. 複数の２進データの中から最大値又は最小値を求めるデータ処理装置であって、
   ２進データと同数以上の条件フラグと、
   各２進データをデコードするための２進データと同数以上のデコーダと、
   ２進データと同数以上の比較器と、
   各デコーダからのデコード結果がＷｉｒｅｄ−ＯＲされて出力される１ビット毎のバスを有し、
   各条件フラグと各デコーダと各比較器は、対象の２進データに対して関連付けされており、
   上記デコーダによるデコード結果は、関連する条件フラグの値が真であれば１ビット毎にＷｉｒｅｄ−ＯＲされてバスに出力され、関連する条件フラグが偽であればバスに出力されず、
   各比較器は、関連するデコーダのデコード結果の値とＷｉｒｅｄ−ＯＲされたバスの値とを比較し、Ｗｉｒｅｄ−ＯＲされたバス値よりもデコード結果の方が小さい場合には、関連する条件フラグの値をリセットすることを特徴とするデータ処理装置。
2. 更に、関連する条件フラグ、デコーダ、及び比較器に対して、ビットシフト回路が関連付けされて設置され、
   各ビットシフト回路は各２進データを入力して所定幅だけビットシフトして関連するデコーダに出力し、
   複数の２進データのビット幅の中の特定部分のビット幅のデータに関して最大値又は最小値を算出することを特徴とする請求項１に記載のデータ処理装置。
3. 各デコーダは、
   デコード結果として、ＬＳＢビットから、入力データをデコードして“１”となったビットまでを、“１”として出力し、それ以外のビットを“０”として出力する、
   又は、その負論理を出力するように構成されていることを特徴とする請求項１に記載のデータ処理装置。
4. 請求項１乃至３のうちのいずれか一に記載のデータ処理装置であって、
   比較器が、複数の２進データを演算処理するための算術演算装置（ＡＬＵ）で構成されていることを特徴とするデータ処理装置。

Images