JPH1185468A - ソートバッファ - Google Patents

Abstract

(57)【要約】 【課題】 ハードウェア構成のソート処理において、ソ
ート中のバスの使用を可能とし、さらにソートデータ個
数の設定を不要とし、さらに回路規模の低減を可能にす
る。 【解決手段】 バッファ群２、バッファデータラッチ回
路７、コンペア回路９、ラッチデータセレクト回路８を
用い、バッファ制御回路１、カウンタＡ３、カウンタＢ
４の制御により、ソート処理をバッファ内で行い、バッ
ファ内のデータをソートする。そして、ソートが完了し
た後に、バッファデータ制御回路６およびバッファ１０
を介してバッファ群２内のデータを出力し、その信号を
監視し、バッファ内のデータを連続して読み出す。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データバッファを
もつ情報処理装置において、データの降順／昇順の並べ
替えを高速に行うソートバッファに関する。

【０００２】

【従来の技術】従来のソートバッファには、例えば特開
平２−７１３２７号公報（ソート処理装置）に記載のも
のがある。これは、ソフトウェアで行われてきたソート
処理をハードウェアで行い、ソフトウェアの処理の軽減
を図ったものである。図１２は、公報に記載のソートバ
ッファの構成例を示す。

【０００３】図１２において、主記憶装置２１は、命令
語およびオペランドを格納する。バッファ記憶制御装置
２２は、要求元の指示に従って主記憶装置２１から命令
語およびオペランドを読み出して要求元へ送出したり、
主記憶装置２１の所定の場所へ演算結果を格納する。演
算制御装置２３は、命令制御装置２４の指示に従って所
定の演算を行う。命令制御装置２４は、主記憶装置２１
から命令語を読み出して解読し、演算制御装置２３また
はソート処理装置２５に演算の実行を指示する。ソート
処理装置２５は、命令制御装置２４からの指示によりソ
ートを行う。

【０００４】このような構成において、ソート処理は以
下のように行われる。バッファ記憶制御装置２２に主記
憶装置２１から読み出した命令語を命令制御装置２４で
解読し、ソート命令であればソート処理装置２５に通知
する。ここで、ソートすべきデータの格納場所とソート
済みデータの格納場所は、いずれも主記憶装置２１内の
メモリ上にとる。ソート処理の実行は命令制御装置２４
の制御に基づいて行い、メモリ上に連続して配置されて
いるソートすべきデータを順次読み出す。また、命令制
御装置２４は、ソートすべきデータの個数と昇順または
降順の指示をソート処理装置２５に通知し、ソート処理
を実行する。

【０００５】

【発明が解決しようとする課題】図１２に示す従来のハ
ードウェア構成のソート処理では、メモリよりデータを
読み出し、ソートを行い、ソートが終了したデータより
順次メモリに書き込む処理を行っていた。このような処
理により、頻繁にメモリにデータが書き込まれるために
バスが頻繁に使用され、システム全体の性能を落とす要
因になっていた。

【０００６】さらに、バスの状態を監視せずに、ソート
が終了したデータを順次出力しているので、データ保護
のためにデータソート中はバスの使用ができなかった
り、または接続されるバスが専用バスになっていた。

【０００７】また、従来のハードウェア構成のソート処
理は、ソートするデータの個数を予め与えてやる必要が
あった。

【０００８】本発明は、このような従来の問題点を解決
するものであり、ハードウェア構成のソート処理におい
て、ソート中のバスの使用を可能とし、さらにソートデ
ータ個数の設定を不要とし、さらに回路規模の低減を可
能にするソートバッファを提供することを目的とする。

【０００９】

【課題を解決するための手段】本発明のソートバッファ
は、データを格納するバッファ群と、バッファ群のライ
ト／リード時のデータ数をカウントし、バッファ群のデ
ータソート時にソート制御に用いるカウント値を出力す
るカウンタＡと、バッファ群のデータソート時にソート
制御に用いるカウント値を出力するカウンタＢと、バッ
ファ群のデータソート時にバッファ群へのデータライト
数を記憶するカウンタＡラッチ回路と、バッファ群のデ
ータをセレクトし、リードデータまたはデータソートの
ためのコンペアデータを出力するバッファデータ制御回
路と、バッファデータ制御回路を介してバッファ群から
出力されたデータのうち、カウンタＢのカウント値に対
応するｊ番目のバッファのデータとｊ＋１番目のバッフ
ァのデータをラッチするバッファデータラッチ回路と、
バッファデータラッチ回路にラッチれたデータを比較
し、外部から指定されたソート方向に応じたデータ入れ
替えの有無を判定し、カウンタＢをカウントアップさせ
るコンペア回路と、コンペア回路の判定によりデータの
入れ替えが生じたときに、ｊ番目およびｊ＋１番目のバ
ッファのデータの順番を入れ替えて出力するラッチデー
タセレクト回路と、コンペア回路の判定によりデータの
入れ替えが生じたときに、ラッチデータセレクト回路か
ら順次出力されたｊ＋１番目およびｊ番目のバッファの
データをｊ番目およびｊ＋１番目のバッファに書き込む
データ入れ替えを制御し、さらに逐次カウントアップす
るカウンタＢとカウンタＡのカウント値が一致するまで
以上の制御を繰り返し、カウント値が一致したときにカ
ウンタＡをカウントダウンしカウンタＢをリセットして
以上の制御を繰り返し、カウンタＡのカウント値が
‘０’になったときにソートを完了し、カウンタＡのカ
ウント値をカウンタＡラッチ回路に記憶された値までカ
ウントアップしながら、各カウント値に対応するバッフ
ァ群のデータをバッファデータ制御回路を介して読み出
す制御を行うバッファ制御回路と、バッファ制御回路の
制御により、バッファデータ制御回路から出力されたリ
ードデータの出力制御を行うバッファとを備える。

【００１０】このように、本発明のソートバッファで
は、ソート処理をバッファ内で行い、バッファ内のデー
タをソートする。そして、ソートが完了した後にバッフ
ァ内のデータを出力し、その信号を監視し、バッファ内
のデータを連続して読み出す（メモリに書き込む）こと
を可能にする。これにより、従来頻繁に行っていたメモ
リへの書き込みを一括して行うことができる。

【００１１】また、本発明のソートバッファでは、ソー
ト中はバッファ内でソートしてバスにアクセスしないの
で、ソート中のバスの使用を可能にすることができる。
そして、バッファのデータ読み出しが可能となったとき
に、バスの監視手段（例えばアービタなど）がバスの空
き状態を確認し、バッファからのデータ読み出しを可能
にする。すなわち、バスの占有時間を短くすることがで
きる。

【００１２】また、本発明のソートバッファでは、バッ
ファに書き込むデータ数をカウントし、ソートスタート
信号をアクティブにしてソートスタートさせることによ
り、ソートデータ個数を設定しなくてもよい。さらに、
カウント値をソートスタート時にラッチし、カウンタに
ライトデータ数カウント、ソート制御、データリード数
カウント、バッファ制御の複数の役割をもたせることに
より、回路削減が可能となる。

【００１３】また、従来技術として示した公報のソート
処理装置では、同じ深さの２組のバッファをソートすべ
きデータの読出し用バッファおよび退避用バッファとし
て交互に使用してソートを行っていた。それに対して、
本発明のソートバッファでは、１組のバッファを使用し
てソートを行う構成であり、バッファ数およびバッファ
を制御するカウンタ数を半減させることができる。

【００１４】

【発明の実施の形態】本発明の実施例について以下に説
明する。

【００１５】図１は、実施例の全体構成を示すブロック
図である。

【００１６】図１において、バッファ制御回路１は、バ
ッファ群２の制御、カウンタＡ３の制御、ソート制御、
リード可能信号（ＲＥＡＤ ＰＯＳ）作成、およびバッ
ファ群２の状態を示す信号（ＢＵＦ ＦＵＬＬ／ＥＭＰ
ＴＹ）を生成する。バッファ群２は、ソートデータを格
納する。カウンタＡ３は、バッファ群２のライトデータ
数のカウント、バッファリードデータ数のカウント、バ
ッファデータソート時にソートの制御、およびバッファ
群２の制御に用いるカウント値を出力する。カウンタＢ
４は、バッファ群２のデータソート時にバッファ群２の
制御に用いるカウント値を出力する。カウンタＡラッチ
回路５は、バッファ群２のデータソート時にバッファ群
２へのデータライト数を記憶する。バッファデータ制御
回路６は、バッファ制御回路１の制御によりバッファ群
２のデータをセレクトし、リードデータおよびコンペア
データを出力する。バッファデータラッチ回路７は、コ
ンペアデータをラッチする。ラッチデータセレクト回路
８は、コンペア結果によるデータ入れ替え時にバッファ
にライトするデータを出力する。コンペア回路９は、デ
ータを比較し、その結果をバッファ制御回路１に通知
し、カウンタＢ４を制御する。バッファ１０は、リード
データの出力制御を行う。

【００１７】ここで、図１中の各信号について説明す
る。

【００１８】「ＤＡＴＡ ＢＵＳ」は、バッファ制御回
路１にライトデータを入力し、バッファ１０からリード
データを出力するデータバスである。

【００１９】「ＤＡＴＡ ＷＲＩＴＥ０」は、バッファ
制御回路１に入力されるデータライト信号である。通常
は‘１’であり、データライト時に‘０’から‘１’の
立ち上がりでＤＡＴＡ ＢＵＳの値をバッファ群２に書
き込む。ただし、ＢＵＦ ＦＵＬＬ１＝‘１’のとき、
ＳＯＲＴ ＥＮ１＝‘１’のとき、ＲＥＡＤ ＰＯＳ１
＝‘１’のときは無効である。

【００２０】「ＤＡＴＡ ＲＥＡＤ０」は、バッファ制
御回路１に入力されるデータリード信号である。通常は
‘１’であり、データリード時に‘０’にすることによ
り、ＤＡＴＡ ＢＵＳにバッファ群２の値を出力する。
データは、ＤＡＴＡ ＲＥＡＤ０の立ち上がり後１クロ
ック分確定している（ホールド確保）。ただし、ＲＥＡ
Ｄ ＰＯＳ１＝‘１’のときは無効である。

【００２１】「ＣＮＴＡＤ」は、カウンタＡ３のカウン
ト値であり、バッファ制御回路１およびカウンタＡラッ
チ回路５に入力される。

【００２２】「ＣＮＴＢＤ」は、カウンタＢ４のカウン
ト値であり、バッファ制御回路１に入力される。

【００２３】「Ｗ ＤＡＴＡ」は、バッファ制御回路１
からバッファ群２に出力されるライトデータ信号であ
る。ＳＯＲＴ ＥＮ１＝‘０’のときにＤＡＴＡ ＢＵ
Ｓの値を出力し、ＳＯＲＴ ＥＮ１＝‘１’のときにラ
ッチデータセレクト回路８から出力されたＳ ＬＡＴ
ＤＡＴＡを出力する。

【００２４】「Ｗ ＢＵＦ」は、バッファ制御回路１か
らバッファ群２の各レジスタ個々に出力されるライト信
号である。ＳＯＲＴ ＥＮ１＝‘０’のときに、ＤＡＴ
ＡＷＲＩＴＥ０をＣＮＴＡＤの示すレジスタに対して出
力し、ＳＯＲＴ ＥＮ１＝‘１’のときに、コンペア回
路９から出力されるＥＸ ＷＲＩＴＥ０をＣＮＴＢＤの
示すレジスタに対して出力する。

【００２５】「ＢＵＦ ＤＩＲ１」は、バッファ制御回
路１からバッファ１０に出力されるイネーブル信号であ
る。‘１’でバッファ１０をイネーブルする。ＲＥＡＤ
ＰＯＳ１＝‘１’のときに、ＤＡＴＡ ＲＥＡＤ０＝
‘０’になったら‘１’を出力し、ＤＡＴＡ ＲＥＡＤ
０＝‘１’になった１クロック後に‘０’を出力する。

【００２６】「ＤＡＴＡ ＳＥＬ」は、バッファ制御回
路１からバッファデータ制御回路６に出力され、バッフ
ァデータ制御回路６がバッファ群２の各レジスタの出力
をセレクトする信号である。ＳＯＲＴ ＥＮ１＝‘０’
のときにＣＮＴＡＤを出力し、ＳＯＲＴ ＥＮ１＝
‘１’のときにＣＮＴＢＤを出力する。

【００２７】「Ｃ ＬＡＴＣＨ０」は、バッファ制御回
路１からバッファデータラッチ回路７およびコンペア回
路９に出力されるスタート信号である。

【００２８】「ＲＥＡＤ ＰＯＳ１」は、バッファ制御
回路１から出力されるリード可能信号である。‘１’の
ときにバッファ群２のデータリードが可能になり、
‘０’のときはデータリード不可である。

【００２９】「ＢＵＦ ＦＵＬＬ１」は、バッファ制御
回路１から出力され、バッファ群２に空きがないことを
示す信号である。本実施形態では、４バイトライト時に
‘１’となる。

【００３０】「ＢＵＦ ＥＭＰＴＹ１」は、バッファ制
御回路１から出力され、バッファ群２に有効データがな
いことを示す信号である。有効データがないときに
‘１’となる。

【００３１】「ＣＮＴＡ ＵＰ０」は、バッファ制御回
路１からカウンタＡ３に出力される制御信号である。カ
ウントアップするときは‘０’、カウントダウンすると
きは‘１’を出力する。ＳＯＲＴ ＥＮ１＝‘０’のと
きは‘０’に固定であり、ＳＯＲＴ ＥＮ１＝‘１’の
ときはＣＮＴＡ ＥＮ０の反転を出力する。

【００３２】「ＣＮＴＡ ＥＮ０」は、バッファ制御回
路１からカウンタＡ３およびカウンタＢ４に出力される
制御信号である。カウンタＡ３は、この信号がイネーブ
ル‘０’のときのクロックの立ち上がりで、ＣＮＴＡ
ＵＰ０＝‘０’のときにカウントアップし、ＣＮＴＡ
ＵＰ０＝‘１’のときにカウントダウンする。カウンタ
Ｂ４は、この信号がイネーブル‘０’のときのクロック
の立ち上がりでリセットされる。

【００３３】「ＣＮＴ ＲＳＴ０」は、バッファ制御回
路１からカウンタＡ３およびカウンタＢ４に出力される
リセット信号である。この信号が‘０’のときのクロッ
クの立ち上がりでリセットされる。

【００３４】「ＣＮＴＡ ＬＡＴ０」は、バッファ制御
回路１からカウンタＡラッチ回路５に出力されるカウン
タＡ３の値をラッチする信号である。この信号が‘０’
のときのクロックの立ち上がりで、カウンタＡラッチ回
路５はＣＮＴＡＤをラッチする。

【００３５】「ＣＮＴＡ ＬＡＴＤ」は、カウンタＡラ
ッチ回路５にラッチされている値をバッファ制御回路１
に出力する信号である。カウンタＡラッチ回路５は、バ
ッファ群２のデータリード時にエンプティ検出のために
カウンタＡ３の値ＣＮＴＡＤをラッチしている。

【００３６】「ＢＵＦ ＤＡＴＡ」は、バッファ群２か
らバッファデータ制御回路６に出力される各レジスタの
データである。

【００３７】「Ｃ ＬＡＴ ＤＡＴＡ」は、バッファ群
２から出力されたデータをＤＡＴＡＳＥＬに応じてセレ
クトした信号であり、バッファデータ制御回路６からバ
ッファデータラッチ回路７およびバッファ１０に出力さ
れる。バッファデータラッチ回路７には、ＢＵＦｘのデ
ータとＢＵＦｘ＋１のデータが出力される。

【００３８】「ＬＡＴ１ ＤＡＴＡ」および「ＬＡＴ２
ＤＡＴＡ」は、バッファデータラッチ回路７内のレジ
スタのデータであり、Ｃ ＬＡＴＣＨ０によってラッチ
データセレクト回路８およびコンペア回路９に出力され
る。

【００３９】「ＬＡＴＣＨ ＳＥＬ０」は、コンペア回
路９からラッチデータセレクト回路８に出力されるセレ
クト信号である。バッファデータの入れ替え時に、ラッ
チデータセレクト回路８の出力を制御する。

【００４０】「Ｓ ＬＡＴ ＤＡＴＡ」は、ラッチデー
タセレクト回路８に入力されたＬＡＴ１ ＤＡＴＡおよ
びＬＡＴ２ ＤＡＴＡのうち、ＬＡＴＣＨ ＳＥＬ０に
よってセレクトされたデータであり、バッファ制御回路
１に出力される。バッファデータの入れ替え時に使用さ
れる。

【００４１】「ＥＸ ＷＲＩＴＥ０」は、バッファデー
タ入れ替え時に、コンペア回路９からバッファ制御回路
１に２回出力されるライト信号である。

【００４２】「ＣＯＭＰ ＲＤＹ０」は、コンペア回路
９でデータコンペアが終了したことを‘０’で知らせる
信号であり、バッファ制御回路１に出力される。

【００４３】「ＣＮＴＢ ＥＮ０」は、コンペア回路９
から出力されるカウンタＢ４のイネーブル信号である。
‘０’のときのクロックの立ち上がりでカウンタＢ４は
カウントアップする。

【００４４】「ＳＯＲＴ ＳＴＡＲＴ１」は、バッファ
制御回路１に対してソートスタートを指示する信号であ
る。‘０’から‘１’への立ち上がりでソートスタート
となる。ただし、バッファにデータが２バイト以上ライ
トされているときに有効となる。

【００４５】「ＳＯＲＴ ＵＰ０」は、バッファ制御回
路１に対してソート方向を設定する信号である。‘０’
のときに昇順、‘１’のときに降順を設定する。

【００４６】以下は、図１に示されない内部信号であ
る。

【００４７】「ＥＸ ＦＬＡＧ１」は、バッファ制御回
路１の内部信号である。データの入れ替えが発生したと
き（ＥＸ ＷＲＩＴＥ０＝‘０’のとき）に、‘１’に
セットされる。

【００４８】「ＳＯＲＴ ＥＮ１」は、バッファ制御回
路１の内部信号である。ソート中に‘１’にセットさ
れ、ソート終了後に‘０’にリセットされる（後述する
図５のステートマシンにおけるソートステート５０１の
ときに‘１’になる）。

【００４９】「ＣＯＭＰＡＲＥ ＥＮ１」は、コンペア
回路９の内部信号である。コンペア中に‘１’にセット
される。

【００５０】「ＥＸＣＨＡＮＧＥ１」は、コンペア回路
９の内部信号である。コンペアにおいてデータの入れ替
えが必要なときに‘１’にセットされる。ＣＯＭＰ Ｒ
ＤＹＯ＝‘０’のときのクロックの立ち上がりでリセッ
トされる。

【００５１】本実施例では、図５に示すように、大まか
に４つのステートに分けることによって、制御を簡略し
ている。アイドルステート５０１からライトステート５
０２へは、データライトすることによって遷移する。ラ
イトステート５０２からソートステート５０３へは、ソ
ートスタートがアクティブ（ＳＯＲＴ ＳＴＡＲＴ１＝
‘１’）、かつデータライト数が２以上（ＣＮＴＡ Ｌ
ＡＴＤ≠‘０’）で遷移する。ライトステート５０２か
らリードステート５０４へは、ソートスタートがアクテ
ィブ（ＳＯＲＴ ＳＴＡＲＴ１＝‘１’）、かつデータ
ライト数が１バイトの時（ＣＮＴＡ ＬＡＴＤ＝
‘０’）に遷移する。ソートステート５０３からリード
ステート５０４へは、ソート終了（ＲＥＡＤ ＰＯＳ１
＝‘１’）により遷移する。リードステート５０４から
アイドルステート５０１へは、ＢＵＦＥＭＰＴＹ１＝
‘１’により遷移する。

【００５２】以下、本実施例の動作について、図２〜４
のフローチャートおよび図６〜１１のタイミングチャー
トを参照して説明する。なお、タイミングチャート内の
数字は、表１のマトリックス表に対応し、各タイミング
での各レジスタの値を示している。また、表中の‘Ｘ’
は、初期値または無効値である。

【００５３】本実施例では、バッファ数は４バイト（４
バイトのデータライトでＢＵＦ ＦＵＬＬ）、ライトデ
ータは、‘３’，‘２’，‘４’，‘１’の順で書き込
み、ソート方向は昇順（ＳＯＲＴ ＵＰ０＝‘０’）で
行うものとする。ここで、ＢＵＦ０とは、バッファ群２
を構成するレジスタのうち、カウンタ（Ａ／Ｂ共通）の
値‘０’に対応するレジスタである。一般化すると、Ｂ
ＵＦｘとは、カウント値ｘに対応する。本回路はすべ
て、クロックの立ち上がりに同期している。

【００５４】まず、ソートデータの書き込み動作につい
て説明する。対応するフローチャートは図２の２０１〜
２０７、タイミングチャートは図６である。

【００５５】バッファ制御回路１に１バイト目のデータ
‘３’が入力されると、カウンタＡ３の値ＣＮＴＡＤが
‘０’のため、バッファ群２のＢＵＦ０にＤＡＴＡ Ｗ
ＲＩＴＥ０の立ち上がりでデータ書き込み（２０１）を
行う。このとき、バッファ制御回路１からバッファ群２
に出力されるＷ ＤＡＴＡには、データバスの値が出力
されている。同時に、バッファ制御回路１は、カウンタ
Ａ３をカウントアップさせるためのＣＮＴＡ ＥＮ０を
１クロック生成し出力する。このときカウンタＡ３はカ
ウントアップなので、バッファ制御回路１はカウンタＡ
３に対してＣＮＴＡ ＵＰ０として‘０’を出力する。
カウンタＡ３は、ＣＮＴＡ ＥＮ０＝０時のクロックの
立ち上がりでカウントアップ（２０２）する。カウンタ
Ａ３のカウントアップによって、バッファ制御回路１か
ら出力されるＢＵＦ ＥＭＰＴＹ１は‘０’にリセット
（２０３）される。

【００５６】バッファ制御回路２に２バイト目のデータ
‘２’が入力されると、１バイト目と同様にバッファに
書き込み（２０１）、カウンタＡ３をカウントアップ
（２０２）する。３バイト目のデータ‘４’、４バイト
目のデータ‘１’の書き込み（２０１）についても同様
である。ただし、４バイト目の書き込み時に、カウンタ
Ａ３の値が‘３’から‘０’に変化（２０４）すると、
バッファ制御回路１は、‘１’にセットしたＢＵＦ Ｆ
ＵＬＬ１を生成（２０６）する。ＢＵＦ ＦＵＬＬ１が
セットされると、バッファ制御回路１はＤＡＴＡ ＷＲ
ＩＴＥ０を無効（２０７）にする。これにより、バッフ
ァ群２へのデータ書き込みを不可にし、データ上書きに
よるバッファ内のデータが破壊されるのを防ぐ。また、
ＢＵＦ ＥＭＰＴＹ時はデータがないので、ＳＯＲＴ
ＳＴＡＲＴ１をアクティブにしてもソートスタートとは
ならない。それは、図５のステートマシンで、ＢＵＦ
ＥＭＰＴＹ時はアイドルステート５０１にあるため、ス
テートが遷移しない。

【００５７】次に、ソートスタートの動作について説明
する。対応するフローチャートは図２の２０８〜２１
３、タイミングチャートは図７である。

【００５８】ソート方向を設定（２０８）し、ＳＯＲＴ
ＳＴＡＲＴ１を‘０’から‘１’にすることにより
（２０９）、バッファ制御回路１内でＳＯＲＴ ＥＮ１
を‘１’にセットする。このセットにより、ＤＡＴＡ
ＲＥＡＤ０およびＤＡＴＡ ＷＲＩＴＥ０は無効（２１
０）となる。そして、バッファ制御回路１は、まずカウ
ンタＡ３をカウントダウンするために、ＣＮＴＡ ＥＮ
０を１クロック生成する。これは、データ書き込み後に
カウンタＡ３をカウントアップしているので、カウンタ
数がバッファ群に書き込みされているデータより１つ多
くなっているためである。また、カウントダウンなので
ＣＮＴＡ ＵＰ０は‘１’を出力する。この制御は単純
に、ＳＯＲＴ ＥＮ１＝‘１’時は、ＣＮＴＡ ＥＮ０
の反転を出力する（ソート時はカウンタＡは、カウント
ダウンのみ使用）。そして、ＣＮＴＡ ＥＮ０＝‘０’
時のクロックの立ち上がりで、カウンタＡ３はカウント
ダウン（２１１）する。

【００５９】カウンタＡ３がカウントダウン後に、バッ
ファ制御回路１は、カウンタＡ３の値をラッチするため
のＣＮＴＡ ＬＡＴ０を１クロック分、カウンタＡラッ
チ回路５に出力する。この信号でカウンタＡラッチ回路
５は、カウンタＡ３の値ＣＮＴＡＤをラッチ（２１２）
する。このとき、ＣＮＴＡＤが‘０’の時（２１３のフ
ローでＹｅｓ）、すなわちバッファ群２に書き込まれた
データが１バイトの時はソートする必要がないので、バ
ッファ制御回路１は、ＲＥＡＤ ＰＯＳ１を‘１’にセ
ット（図３、３１７）し、内部信号のＳＯＲＴ ＥＮ１
を‘０’にリセット（図３、３１８）し、バッファデー
タの読み出し可能およびソート完了を通知する。この制
御により、余計な処理をするのを防ぐ。詳しくは後述す
る。

【００６０】ソート方向設定は、ＳＯＲＴ ＵＰ０にて
行う（２０８）。この設定はＳＯＲＴ ＳＴＡＲＴ１を
アクティブにする前ならいつでもよい。それは、コンペ
ア回路９内は、ソートがスタートしたときに、その時の
ＳＯＲＴ ＵＰ０のレベルをラッチし、データのコンペ
アを行うためである。

【００６１】次に、ソート処理の動作について説明す
る。対応するフローチャートは図３の３０１〜３１５、
タイミングチャートは図８である。

【００６２】バッファ制御回路１は、Ｃ ＬＡＴＣＨ０
（コンペアスタート信号としても使用）を１クロック出
力し、ソート処理に入る。Ｃ ＬＡＴＣＨ０が出力され
ると、バッファデータラッチ回路７は、バッファデータ
制御回路６から出力されているデータをクロックの立ち
上がりでラッチする（３０１）。このとき、バッファ制
御回路１からバッファデータ制御回路６へ出力されるＤ
ＡＴＡ ＳＥＬは、ＳＯＲＴ ＥＮ１＝‘０’時にカウ
ンタＡ３のカウント値ＣＮＴＡＤを出力し、ＳＯＲＴ
ＥＮ１＝‘１’時にカウンタＢ４のカウント値ＣＮＴＢ
Ｄを出力する。同時に、コンペア回路９では、内部信号
ＣＯＭＰＡＲＥ ＥＮ１を‘１’にセットし、コンペア
イネーブルとする。

【００６３】コンペア回路９では、バッファデータラッ
チ回路７にラッチされたＬＡＴ１ＤＡＴＡ（＝‘３’）
とＬＡＴ２ ＤＡＴＡ（＝‘２’）を比較（３０４）す
る。本実施例では昇順ソートであり、ＬＡＴ１ ＤＡＴ
Ａの方が大きいため、次のクロックでデータ入れ替え信
号ＥＸＣＨＡＮＧＥ１を‘１’にセットする。ＥＸＣＨ
ＡＮＧＥ１＝‘１’になると、コンペア回路９は、デー
タの入れ替えが生じたと判断し、次のクロックでＥＸ
ＷＲＩＴＥ０を１クロック分‘０’出力する。これを受
けてバッファ制御回路１では、カウンタＢ４のカウント
値ＣＮＴＢＤに対応したバッファ群２に対し、ＥＸ Ｗ
ＲＩＴＥ０をＷ ＤＡＴＡに出力する（この場合、ＢＵ
Ｆ０に対しＥＸ ＷＲＩＴＥ０を出力する）。この信号
の立ち上がりでＷ ＢＵＦ値をＢＵＦ０に書き込む（３
０５）。Ｗ ＢＵＦには、ラッチデータセレクト回路８
からのＳ ＬＡＴ ＤＡＴＡが出力されている。すなわ
ち、ＳＯＲＴ ＥＮ１＝‘０’時はＤＡＴＡ ＢＵＳの
データが出力され、ＳＯＲＴ ＥＮ１＝‘１’時はＳ
ＬＡＴ ＤＡＴＡが出力される。Ｓ ＬＡＴ ＤＡＴＡ
には、ＬＡＴ ＳＥＬ０＝‘１’なので、ＬＡＴ２ Ｄ
ＡＴＡが出力されている。これは、ＢＵＦ１に書き込ま
れていたデータである。

【００６４】同時に、ＥＸ ＷＲＩＴＥ０＝‘０’の時
のクロックの立ち上がりで、Ｓ ＬＡＴ ＤＡＴＡにＬ
ＡＴ１ ＤＡＴＡを出力するためにＬＡＴ ＳＥＬ０は
‘０’となり、バッファ制御回路１の内部信号ＥＸ Ｆ
ＬＡＧ１は‘１’にセット（３０７）される。すなわ
ち、データの入れ替えが発生したとき‘１’となる。さ
らに、カウンタＢ４をカウントアップするためのＣＮＴ
Ｂ ＥＮ０を１クロック分イネーブルにする。これは、
ＬＡＴ１ ＤＡＴＡ値をバッファに書き込むためと、次
のコンペアのための準備である。このときＣＮＴＢ Ｅ
Ｎ０の出力される条件として、ＬＡＴ ＳＥＬ０＝
‘１’が条件である。これは、次のＥＸ ＷＲＩＴＥ０
＝‘０’の条件で、ＣＮＴＢ ＥＮ０を出力させないた
めである。

【００６５】カウンタＢ４は、ＣＮＴＢ ＥＮ０＝
‘０’時のクロックの立ち上がりで、カウントアップ
（３０７）する。同時に、ＥＸ ＷＲＩＴＥ０の２回目
のライト信号‘０’を１クロック出力する。１回目のＥ
Ｘ ＷＲＩＴＥ０の出力時と同様に、バッファ制御回路
１では、カウンタＢ４のカウント値ＣＮＴＢＤに対応す
るＢＵＦ１に対し、ＥＸ ＷＲＩＴＥ０をＷ ＢＵＦに
出力し、Ｗ ＢＵＦの立ち上がりでＷ ＤＡＴＡを書き
込む（３０８）する。このときのＷ ＤＡＴＡには、Ｌ
ＡＴ１ ＤＡＴＡが出力されている。この段階で、ＢＵ
Ｆ０とＢＵＦ１とのデータの入れ替えが完了したことに
なる。

【００６６】コンペア回路９では、２回目のＥＸ ＷＲ
ＩＴＥ０＝‘０’時のクロックの立ち上がりで（１回
目、２回目の判断は、ＬＡＴＣＨ ＳＥＬ０＝‘１’時
のＥＸＷＲＩＴＥ０＝‘０’が１回目、ＬＡＴＣＨ Ｓ
ＥＬ０＝‘０’時のＥＸ ＷＲＩＴＥ０＝‘０’が２回
目と判断している）、ＣＯＭＰＡＲＥ ＥＮ１を‘０’
にクリア（コンペア完了）し、バッファ制御回路１へＣ
ＯＭＰＡＲＥ ＲＤＹ０信号を出力する。ＣＯＭＰＡＲ
Ｅ ＲＤＹ０＝‘０’時のクロックの立ち上がりで、Ｅ
ＸＣＨＡＮＧＥ１を‘０’にクリアし、ＬＡＴＣＨ Ｓ
ＥＬ０を‘１’にセットする（コンペアの後処理）。

【００６７】ＣＯＭＰＡＲＥ ＲＤＹ０を受けて、バッ
ファ制御回路１では、カウンタＡ３のカウント値ＣＮＴ
ＡＤ（ｉ）とカウンタＢ４のカウント値ＣＮＴＢＤ
（ｊ）を比較（３１０）する。この時点で、ＣＮＴＡＤ
＝‘３’、ＣＮＴＢＤ＝‘１’であるので、次のソート
データコンペアスタートのためのＣ ＬＡＴＣＨ０を出
力する。なお、両カウント値が等しい場合の動作は後述
する。

【００６８】前回のコンペア処理と同様に、Ｃ ＬＡＴ
ＣＨ０＝‘０’時のクロックの立ち上がりで、バッファ
データラッチ回路７では、ＬＡＴ１ ＤＡＴＡにＢＵＦ
１の値‘３’をラッチし、ＬＡＴ２ ＤＡＴＡにＢＵＦ
２に値‘４’をラッチ（３０１）し、コンペア回路９で
は、ＣＯＭＰＡＲＥ ＥＮ１を‘１’にセットする。コ
ンペア処理も前回と同様に行う。今回のコンペアデータ
は、ＬＡＴ１ ＤＡＴＡ＝‘３’、ＬＡＴ２ ＤＡＴＡ
＝‘４’であるため、昇順ではデータ入れ替えの必要は
ない（３０４）。よって、ＥＸＣＨＡＮＧＥ１もセット
されない。ＥＸＣＨＡＮＧＥ１がセットされないと、Ｅ
Ｘ ＷＲＩＴＥ０も発生しないため、前回のＣＮＴ Ｅ
Ｎ０の発生条件では、今回ＣＮＴ ＥＮ０は発生しな
い。そこで、ＣＭＰＡＲＥ ＥＮ１＝‘１’後にＥＸＣ
ＨＡＮＧＥ１をクロックで２回サンプルし、２回とも
‘０’をサンプルした場合にデータ入れ替え必要なしと
判断し、ＣＮＴＢ ＥＮ０を１クロック出力する。カウ
ンタＢ４では、これを受けてクロックの立ち上がりで、
カウントアップ（３０９）する。同時にＣＯＭＰＡＲＥ
ＥＮ１を‘０’にクリアし、ＣＯＭＰＡＲＥ ＲＤＹ
０を出力する。データ入れ替えが必要がないときは、無
駄な処理を省き、コンペア処理を終わらせることで、ソ
ート処理の高速化を図る。

【００６９】ＣＯＭＰＡＲＥ ＲＤＹ０を受けて、バッ
ファ制御回路１では、前回と同様にＣＮＴＡＤ（＝
‘３’）とＣＮＴＢＤ（＝‘２’）を比較（３１０）
し、両者が等しくないため、Ｃ ＬＡＴＣＨ０を出力し
てコンペア処理に入る。今回のコンペアデータはＬＡＴ
１ ＤＡＴＡ＝‘４’、ＬＡＴ２ ＤＡＴＡ＝‘１’の
ため、１回目のコンペア処理と同様にデータを入れ替え
る処理を行う。そして、コンペア処理が終わったことを
知らせるＣＯＭＰＡＲＥ ＲＤＹ０を出力する。

【００７０】今回、ＣＯＭＰＡＲＥ ＲＤＹ０＝‘０’
時、ＣＮＴＡＤ（＝‘３’）、ＣＮＴＢＤ（＝‘３’）
を比較（３１０）した結果、両者が等しいためＣ ＬＡ
ＴＣＨ０を出力せず、カウンタＡ３をカウントダウンす
るためにＣＮＴＡ ＥＮ０＝‘０’、ＣＮＴＡ ＵＰ０
＝‘１’を１クロック出力する。このときＥＸ ＦＬＡ
Ｇ１を監視し、この信号が‘１’の時はＣＮＴＡ ＥＮ
０を出力してデータ入れ替えを行う。一方、‘０’の時
は、途中でソートが終了したときでありＣＮＴＲＳＴ０
を出力する（詳細は後述する）。ＣＮＴＡ ＥＮ＝
‘０’を受けてカウンタＡ３では、クロックの立ち上が
りでカウントダウン（３１３）し、カウンタＢ４はリセ
ット（３１４）される。

【００７１】同時に、ＥＸ ＦＬＡＧ１は、ＣＮＴＡ
ＥＮ０＝‘０’時のクロックの立ち上がりで‘０’にリ
セット（３１２）する。そして、ＥＸ ＦＬＡＧ１が
‘１’から‘０’とサンプルされたときにＣＮＴＡＤを
サンプル（３１５）し、ソートを終了する。一方、
‘０’をサンプルしなかったときは、再びＣ ＬＡＴＣ
Ｈ０を出力する。

【００７２】この後の処理は、今までに説明したことと
同様にコンペア処理、データ入れ替え処理を行う。対応
するフローチャートは図３の３１７〜３１９、タイミン
グチャートは図９である。

【００７３】ＥＸ ＦＬＡＧ１が‘１’から‘０’とサ
ンプルされ、そのときＣＮＴＡＤ＝‘０’をサンプル
（３１５）したときにソート終了となる。ＣＮＴＡＤ＝
‘０’サンプルしたクロックの立ち上がりで、ＲＥＡＤ
ＰＯＳ１を‘１’にセット（３１７）し、ソートが終
了してリード可能となったことを知らせる。次のクロッ
クで、ＳＯＲＴ ＥＮ１を‘０’にリセット（３１８）
する。実際にＤＡＴＡＲＥＡＤ０が有効となるのは、Ｒ
ＥＡＤ ＰＯＳ１＝‘１’かつＳＯＲＴ ＥＮ１＝
‘０’の時である（３１９）。

【００７４】次に、ソートデータの読み出し処理につい
て説明する。対応するフローチャートは図４、タイミン
グチャートは図１０である。

【００７５】ＤＡＴＡ ＲＥＡＤ０＝‘０’（４０１）
となると、バッファ制御回路１は、ＢＵＦ ＤＩＲ１を
イネーブルする。これによりバッファ１０がイネーブル
になると、ＤＡＴＡ ＢＵＳにＣ ＬＡＴ ＤＡＴＡが
出力される。

【００７６】Ｃ ＬＡＴ ＤＡＴＡへは、ＤＡＴＡ Ｓ
ＥＬによりセレクトされたバッファ群２の値が出力され
ている。このデータリードではＢＵＦ０の‘１’が出力
されている。また、ＤＡＴＡ ＳＥＬにはＣＮＴＡＤが
出力されている。そしてＤＡＴＡ ＲＥＡＤ＝‘１’と
なると、カウンタＡ３をカウントアップするため、ＣＮ
ＴＡ ＥＮ０を１クロック分‘０’出力する。ＣＮＴＡ
ＥＮ０＝‘０’の時のクロックの立ち上がりで、カウ
ンタＡ３がカウントアップ（４０４）し、ＢＵＦ ＤＩ
Ｒ１が‘０’にクリアされ、バッファ１０がディセーブ
ルとなる。なお、ＤＡＴＡ ＲＥＡＤ０の立ち上がりか
ら、１クロック分遅らせているのはホールド確保のため
である。ＢＵＦ ＤＩＲ１が‘０’にクリアされると、
ＢＵＦＦＵＬＬ１も‘０’にクリア（４０３）される。
２バイト目、３バイト目も同様に処理される。

【００７７】４バイト目のデータリード時、ＤＡＴＡ
ＲＥＡＤ０の立ち上がり段階で、ソートはじめにラッチ
したＣＮＴＡ ＬＡＴＤと、ＣＮＴＡＤとを比較（４０
２）する（ＤＡＴＡ ＲＥＡＤ０の立ち上がりで随時比
較している）。そして、両者が等しい場合にＣＮＴＡ
ＥＮ０は出力せず、カウンタＡ３およびカウンタＢ４を
リセットするためのＣＮＴ ＲＳＴ０を１クロック分出
力する。ＣＮＴ ＲＳＴ０＝‘０’時のクロックの立ち
上がりで、カウンタＡ３およびカウンタＢ４はリセット
（４０７）され、ＢＵＦ ＥＭＰＴＹ１を‘１’にセッ
ト（４０６）する。ＢＵＦ ＥＭＰＴＹ１が‘０’から
‘１’にサンプルされたクロックの立ち上がりで、ＲＥ
ＡＤ ＰＯＳ１を‘０’にクリア（４０６）する。この
信号が‘０’クリアされると、データリード不可（無
効）となる。また、ＲＥＡＤ ＰＯＳ１＝‘０’によ
り、ＤＡＴＡ ＷＲＩＴＥ０の信号も有効（４０８）と
なる。

【００７８】以上が本実施例におけるデータ書き込み、
ソート、データ読み出しの一連の説明である。

【００７９】また本実施例では、ソート時間をより高速
にするために、ソートが途中で終了した場合、ソート途
中でもソート処理を終了させ、ＲＥＡＤ ＰＯＳ１を
‘１’にセットし、データリード可能とするように工夫
されている。基本的な処理は前述の例と同じである。こ
こでは、前述の例と異なる点を中心に説明する。対応す
るフローチャートは図３、タイミングチャートは図１１
である。

【００８０】ソートデータとして、‘２’、‘１’、
‘４’、‘３’の順でライトされたとする。またソート
方向は昇順でソートするものとする。ソートスタートさ
れると、最初のコンペア処理を実行する。

【００８１】ＬＡＴ１ ＤＡＴＡに‘２’、ＬＡＴ２
ＤＡＴＡに‘１’をラッチ（２０１）する。コンペア結
果（３０４）によりバッファ内のデータは入れ替えられ
る（３０５〜３０８）。このとき、データの入れ替えが
行われたので、ＥＸ ＦＬＡＧ１が‘１’にセット（３
０６）される。次のコンペア処理で、‘２’と‘４’が
コンペア（３０４）され、データの入れ替えは行われな
い。次に‘４’と‘３’がコンペア（３０４）され、入
れ替え処理が実行される。ここで、ＣＮＴＡＤ＝ＣＮＴ
ＢＤ（３１０）となったので、カウンタＡ３がカウント
ダウン（３１３）され、カウンタＢ４はリセット（３１
４）される。ＥＸ ＦＬＡＧ１もリセット（３１２）さ
れる。ＣＮＴＡＤが‘０’（３１５）でないので、コン
ペアスタートとなる。

【００８２】まず、‘１’と‘２’がコンペア（３０
４）され、データの入れ替えは行われない。次に
‘２’、‘３’がコンペア（３０４）され、これもデー
タの入れ替えは行われない。ここで通常なら、バッファ
制御回路１は、ＣＯＭＰＡＲＥ ＲＤＹ０を受けたと
き、ＣＮＴＡＤ＝ＣＮＴＢＤ（３１０）なので、カウン
タＡ３をカウントダウンするためにＣＮＴＡ ＥＮ０を
出力する。しかし、ＥＸ ＦＬＡＧ１が‘０’（３１
１）（データの入れ替えが行われていない）なので、ソ
ートが終了したと判断し、カウンタＡ３およびカウンタ
Ｂ４をリセットする信号ＣＮＴ ＲＳＴ０を出力する。
この信号を受けカウンタＡ３およびカウンタＢ４では、
クロックの立ち上がりでリセット（３１６）する。そし
て、つぎのクロックでリード可能にするＲＥＡＤ ＰＯ
Ｓ１をセット（３１７）し、その次のクロックでＳＯＲ
Ｔ ＥＮ１をリセット（３１８）する。

【００８３】このように、本処理によってソートが途中
で完了した時点で、リード可能とし、無駄な処理を削る
ことで、より一層ソートを高速にする。

【００８４】本実施例では、説明の簡略化のために、バ
ッファ群２のレジスタの数を４バイトで説明したが、レ
ジスタの数を増やすことによって、ソートデータ数を増
やすことができる。またデータ数は、ＢＵＦ ＦＵＬＬ
までライトしなくてもソート可能である。

【００８５】

【発明の効果】以上説明したように、本発明では、１組
のバッファでソートを行うことにより、バッファを制御
するカウンタとともに回路数を削減できる。さらに、そ
のバッファ内でソートを行い、ソートが終了しデータリ
ードが可能となったことを知らせることによって、バッ
ファ内のデータを連続で読み出すことができる。しかも
バスの状態により、バスが空いている時を利用してデー
タを読み出すことができ、従来技術の欠点を克服するこ
とができる。

【００８６】また、ライトデータ数をカウントし、ソー
トスタートさせる信号をイネーブルにし、ソートをスタ
ートさせる方式をとったことにより、ソートデータ数を
設定しなくてもよい。さらに、カウント値をソートスタ
ート時にラッチし、カウンタを、ライトデータ数カウン
ト、ソート制御、リード数カウントと複数の役割をさせ
ることによって、回路削減に役立っている。

【図面の簡単な説明】

【図１】実施例の全体構成を示すブロック図である。

【図２】実施例の動作を説明するフローチャート（１／
３）である。

【図３】実施例の動作を説明するフローチャート（２／
３）である。

【図４】実施例の動作を説明するフローチャート（３／
３）である。

【図５】実施例の動作概要を説明するステートマシンで
ある。

【図６】バッファデータライトの動作を説明するタイミ
ングチャートである。

【図７】ソートスタートの動作を説明するタイミングチ
ャートである。

【図８】ソート動作を説明するタイミングチャートであ
る。

【図９】ソートエンドの動作を説明するタイミングチャ
ートである。

【図１０】バッファデータリードの動作を説明するタイ
ミングチャートである。

【図１１】ソート動作を説明するタイミングチャートで
ある。

【図１２】公報に記載のソートバッファの構成例を示す
ブロック図である。

【符号の説明】

１ バッファ制御回路 ２ バッファ群 ３ カウンタＡ ４ カウンタＢ ５ カウンタＡラッチ回路 ６ バッファデータ制御回路 ７ バッファデータラッチ回路 ８ ラッチデータセレクト回路 ９ コンペア回路 １０ バッファ

Claims (2)

【特許請求の範囲】
1. 【請求項１】 データを格納するバッファ群と、 前記バッファ群のライト／リード時のデータ数をカウン
   トし、前記バッファ群のデータソート時にソート制御に
   用いるカウント値を出力するカウンタＡと、 前記バッファ群のデータソート時にソート制御に用いる
   カウント値を出力するカウンタＢと、 前記バッファ群のデータソート時に前記バッファ群への
   データライト数を記憶するカウンタＡラッチ回路と、 前記バッファ群のデータをセレクトし、リードデータま
   たはデータソートのためのコンペアデータを出力するバ
   ッファデータ制御回路と、 前記バッファデータ制御回路を介して前記バッファ群か
   ら出力されたデータのうち、前記カウンタＢのカウント
   値に対応するｊ番目のバッファのデータとｊ＋１番目の
   バッファのデータをラッチするバッファデータラッチ回
   路と、 前記バッファデータラッチ回路にラッチれたデータを比
   較し、外部から指定されたソート方向に応じたデータ入
   れ替えの有無を判定し、前記カウンタＢをカウントアッ
   プさせるコンペア回路と、 前記コンペア回路の判定によりデータの入れ替えが生じ
   たときに、ｊ番目およびｊ＋１番目のバッファのデータ
   の順番を入れ替えて出力するラッチデータセレクト回路
   と、 前記コンペア回路の判定によりデータの入れ替えが生じ
   たときに、前記ラッチデータセレクト回路から順次出力
   されたｊ＋１番目およびｊ番目のバッファのデータをｊ
   番目およびｊ＋１番目のバッファに書き込むデータ入れ
   替えを制御し、さらに逐次カウントアップする前記カウ
   ンタＢと前記カウンタＡのカウント値が一致するまで以
   上の制御を繰り返し、カウント値が一致したときに前記
   カウンタＡをカウントダウンし前記カウンタＢをリセッ
   トして以上の制御を繰り返し、前記カウンタＡのカウン
   ト値が‘０’になったときにソートを完了し、前記カウ
   ンタＡのカウント値を前記カウンタＡラッチ回路に記憶
   された値までカウントアップしながら、各カウント値に
   対応する前記バッファ群のデータを前記バッファデータ
   制御回路を介して読み出す制御を行うバッファ制御回路
   と、 前記バッファ制御回路の制御により、前記バッファデー
   タ制御回路から出力されたリードデータの出力制御を行
   うバッファとを備えたことを特徴とするソートバッフ
   ァ。
2. 【請求項２】 バッファ制御回路は、カウンタＡのカウ
   ント値が‘０’になる前にソート完了とし、データリー
   ドを可能にする構成であることを特徴とする請求項１に
   記載のソートバッファ。