JPH061432B2 - デ−タ整列装置 - Google Patents

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 本発明はデータ集合をデータ値の小さい順もしくは大き
い順に並べ換えるデータ整列装置に関する。

〔従来の技術〕

一般にデータ整列装置は、２つの整列済みデータ部分集
合を併合し、該整列済みデータ部分集合に含まれるデー
タ数を１，２，４，……と倍々に大きくしていく比較ユ
ニットを複数個、縦続に接続した構成となっている。従
来のデータ整列装置は、比較ユニットの構成により二種
類に大別することができる。以下、Ａ方式およびＢ方式
と呼ぶことにする。

初め第６図乃至第８図によりＡ方式のデータ整列装置に
ついて説明する。

第６図はＡ方式の装置構成例を示す図であり、１０はデ
ータ整列装置、２０は装置１のデータ入力端子、３０は
装置１のデータ出力端子、４０−１〜４０−Ｕは比較ユ
ニットである。各比較ユニットは、入力端子６０１から
入力される整列済みデータ部分集合の一方を格納するメ
モリ６０３、該メモリ６０３と同じ大きさを持ち、入力
端子６０１からの整列済みデータ部分集合の他方を格納
するメモリ６０４、メモリ６０３，６０４へのデータの
読み書きを行う読出し／書込み回路６０５、メモリ６０
３のデータの１バイトを格納するレジスタ６０６、メモ
リ６０４のデータの１バイトを格納するレジスタ６０
７、レジスタ６０６と６０７に格納されているデータの
値を比較する比較器６０８、比較結果によりレジスタ６
０６，６０７のいずれか一方に格納されているデータを
出力端子６０２に転送する経路を確立するマルチプレク
サ６０９からなる。こゝで、メモリ６０３と６０４の大
きさは、比較ユニット４０−１では１個のデータ、４０
−２では２個のデータ、４０−３では４個のデータ、４
０−Ｕでは２^U-1個のデータを格納できる大きさを有し
ている。

第６図の比較ユニット４０−３におけるデータ部分集合
対の併合処理例のタイムチャートを第７図に示す。第７
図は、各々１バイトのデータが４個から成るデータ部分
集合対２組の併合処理を示したものである。第７図にお
いて、７００はデータ対の比較処理、７０１はメモリ６
０３から１バイト読み出してレジスタ６０６に格納する
処理、７０２はメモリ６０４から１バイト読み出してレ
ジスタ６０７に格納する処理、７０３はレジスタ６０６
と６０７に格納されているデータの値を比較して、比較
結果に従い、一方のレジスタ内のデータをマルチプレク
サ６０９で選択して出力端子６０２から比較ユニット４
０−４に転送すると同時に、比較ユニット４０−２から
入力端子６０１を経由して、データの１バイトをメモリ
６０３あるいは６０４に書き込む処理を示している。７
０４は１バイトの大きさを持つデータである。７０５−
１と７０６−１は入力端子６０１から順次入力される１
番目の整列済みデータ部分集合対であり、７０７−１は
該データ部分集合対に対する併合後の整列済み出力デー
タ部分集合である。同様に、７０５−２と７０６−２は
２組目の整列済み入力データ部分集合対、７０７−２は
該データ部分集合対に対する併合後の整列済み出力デー
タ部分集合である。

第７図の例について、比較ユニット４０−３における処
理の様子を示すと第８図の通りである。第８図におい
て、「∧」、「∨」は各々レジスタ６０６，６０７のデ
ータの方が小さいことを示し、「×」は比較しないこと
を示している。８００はメモリ６０３，６０４中のデー
タ部分集合の区切りを示し、８００−１はデータ部分集
合７０５−１と７０５−２の区切り、８００−２はデー
タ部分集合７０６−１と７０６−２の区切りを示す。時
刻は第７図の時刻及び処理７０１，７０２，７０３に対
応している。

ところで、Ａ方式のデータ整列装置では、第６図に示す
様に、メモリ６０３，６０４へのデータの読出し／書込
み回路が１つしかないため、読み・書きが逐次的にしか
できない。このため、第７図に示すように、１バイトの
処理についてメモリへの読み・書きで３処理が必要とな
る。また、メモリ６０３，６０４のいずれかのデータ部
分集合が全て出力し終えないと、次のデータ部分集合の
入力を行うことができない。第７図の例では、データ部
分集合７０５−１と７０６−１を各々メモリ６０３，６
０４に入力後、そのうちのデータ部分集合７０５−１が
出力し終える時点で、次のデータ部分集合７０５−２の
入力を開始している。このため、データの値によって
は、第７図に示すように、データ部分集合の入力に時間
の空きができる。これら２つの理由から、Ａ方式は処理
時間が遅いという欠点があった。

次に第９図乃至第１１図によりＢ方式のデータ整列装置
について説明する。

第９図はＢ方式の装置構成例を示す図であり、データ整
列装置１０が比較ユニット４０−１〜４０−Ｕを縦続接
続した構成をとることは第６図と同様である。各比較ユ
ニットは、入力端子９０１から入力される整列済みデー
タ部分集合を格納するメモリ９０３、１データ分の大き
さを持つメモリ９０４、メモリ９０３の読出し／書込み
回路９０５、１バイトの大きさを持つレジスタ９０６，
９０７，９１０，レジスタ９０６と９０７に格納されて
いるデータの値を比較する比較器９０８、レジスタ９０
６と９０７のいずれか一方のデータをデータ出力端子９
０２に転送する経路を選択するマルチプレクサ９０９か
らなる。メモリ９０３の大きさは、第６図の場合と同様
に、比較ユニット４０−１では１個のデータ、４０−２
では２個のデータ、４０−３では４個のデータ、４０−
Ｕでは２^U-1個のデータを格納できる大きさを有してい
る。

第１０図は第９図の比較ユニット４０−３におけるデー
タ部分集合対の併合処理例を示すタイムチャートであ
る。第１０図において、１０００はデータ対の比較処理
であり、１００１と１００２の２つの処理に分けられ
る。処理１００１は次の〜のいずれかの動作とレジ
スタ９０６，９０７のいずれか一方のデータを比較結果
よりマルチプレクサ９０９で選択してデータ出力端子９
０２へ出力する動作を同時に行う処理であって、から
の動作は次の通りである。

データ入力端子９０１からデータを入力し、メモリ
９０４経由でレジスタ９０７に格納する。

データ入力端子９０１からデータを入力し、レジス
タ９１０に格納する。

の動作に加え、メモリ９０３からデータの１バイ
トを読み出し、レジスタ９０６に格納する。

の動作に加え、レジスタ９０６のデータをレジス
タ９０７に格納する。

処理１００２は、レジスタ９１０のデータをメモリ９０
３に格納すると同時に、レジスタ９０６と９０７のデー
タの値を比較器９０８で比較し、比較結果を得る処理で
ある。１００３は１バイトの大きさを持つデータを示
す。１００４は一方の整列済み入力データ部分集合、１
００５は他方の整列済み入力データ部分集合、１００６
は併合後の出力データ部分集合で、１００４−１と１０
０５−１を併合した結果が１００６−１であり、１００
４−２と１００５−２を併合した結果が１００６−２で
ある。

第１０図の例について、比較ユニット４０−３における
処理の様子を詳細に示したのが第１１図である。第１１
図では、データの大きさが１バイトのため、使用しない
メモリ９０４は省いてある。１１００はメモリ９０３中
のデータ部分集合の区切りであって、１１００−１はデ
ータ部分集合１００４−１と１００５−１の区切り、１
１００−２はデータ部分集合１００４−１と１００４−
２の区切り、１１００−３はデータ部分集合１００５−
１と１００４−２，１１００−４はデータ部分集合１０
０４−２と１００５−２の区切りを示す。１１０１はメ
モリ９０３内で１つのデータ部分集合に含まれるデータ
をつなぐポインタを示す。時刻は、第１０図の時刻及び
処理１００１，１００２に対応している。

第１０図に示すように、Ｂ方式のデータ整列装置では、
データ部分集合の入出力に時間の空きが生じないため、
処理時間の高速化が達成できるが、制御が非常に複雑で
ある欠点を有している。すなわち、第１０図における処
理１００１の場合、処理の分けが多い。また、メモリ９
０３内には最大３つのデータ部分集合が格納され、デー
タ管理が繁雑である。第１０図の例では、時刻９のデー
タ入力時点では、メモリ９０３にデータ部分集合１００
４−１，１００４−２，１００４−３のデータが格納さ
れている。

〔発明の目的〕

本発明の目的は、制御が容易で、しかもデータ整列時間
の短縮を図ることができるデータ整列装置を提供するこ
とにある。

〔発明の特徴〕

本発明は、データ整列装置の各比較ユニットに各々２つ
のメモリを設け、比較ユニットに入力されるデータを２
つのメモリに同時に複写して格納し、これらメモリのデ
ータを用いて併合処理を行うことを特徴とするものであ
る。

〔発明の実施例〕

第１図は本発明によるデータ整列装置の構成例を示す図
である。第１図において、データ整列装置１０は複数の
比較ユニット４０−１〜４０−Ｕを縦続接続した構成を
とる。２０は装置１０の１バイト幅データ入力端子、３
０は同じく装置１０の１バイト幅データ出力端子であ
り、１０１は比較ユニットの１バイト幅データ入力端
子、１０２は同じく比較ユニットの１バイト幅データ出
力端子である。各比較ユニット４０−１〜４０−Ｕは、
入力端子６０１から入力される一方の整列済みデータ部
分集合を格納するメモリ１０３、他方の整列済みデータ
部分集合を格納するメモリ１０４、メモリ１０３，１０
４へのデータの読み書きを各々行う読出し／書込み回路
１０５−１，１０５−２、メモリ１０３のデータの１バ
イトを格納するレジスタ１０６、メモリ１０４のデータ
の１バイトを格納するレジスタ１０７、レジスタ１０６
と１０７に格納されているデータの値を比較する比較器
１０８、レジスタ１０６と１０７のいずれか一方のデー
タを出力端子１０２に転送する経路を選択するマルチプ
レクサ１０９、比較器１０８から比較結果信号を受け取
り、それに基いて当該比較ユニットの各部を制御する制
御回路１１０からなる。メモリ１０３と１０４の大きさ
は、比較ユニット４０−１では１個のデータ、４０−２
では２個のデータ、４０−３では４個のデータ、４０−
Ｕでは２^U-1個のデータを格納できる大きさを有してい
る。

第２図は、第１図における各比較ユニットでの処理状態
の遷移を示した図であって、２００から２０５は状態、
２０６は遷移の方向を示している。各状態２００〜２０
５は書込み処理と読出し処理とからなる。

今、併合する２つの整列済みデータ部分集合を、比較ユ
ニット４０−ｉ（ｉ＝１，２，…Ｕ）に入力される順に
各々Ｒ，Ｓとし、Ｓに続いて入力される整列済みデータ
部分集合をＴとする。２００の状態Ａは次の処理より成
る。

書込み処理：データ入力端子１０１よりＲのデータ
を１バイト入力し、メモリ１０３と１０４に複写して格
納する。

読出し処理：何もしない。

Ｒの全データを入力し終えるまで状態Ａを繰り返し、そ
の後、２０１の状態Ｂに遷移する。状態Ｂは次の処理か
ら成る。

書込み処理：データ入力端子１０１よりＳのデータ
を１バイト入力し、メモリ１０３あるいは１０４のどち
らか一方に格納する。

読出し処理：メモリ１０３からＲまたはＳのデータ
の１バイトを読み出してレジスタ１０６に、メモリ１０
４からＳまたはＲのデータの１バイトを読み出してレジ
スタ１０７に各々同時に格納し、レジスタ１０６と１０
７に格納されているデータの値を比較器１０８で比較し
て、比較結果を制御回路１１０に通知する。

Ｓの先頭の１バイト目についてのみ状態Ｂを処理する。
Ｓに残りのデータがある場合は状態Ｃに、ない場合は状
態Ｅに遷移する。２０３の状態Ｃは次の処理から成る。

書込み処理：データ入力端子１０１よりＳのデータ
を１バイト入力し、全Ｒが格納されていない方のメモリ
に格納する。同時にレジスタ１０６と１０７のいずれか
一方を制御回路１１０からの指示に従い、マルチプレク
サ１０９で選択し、該データをデータ出力端子１０２に
出力する。

読出し処理：状態Ｂの読出し処理と同様である。

Ｓの全データを入力し終えるまで状態Ｃを繰り返す。メ
モリ１０３とメモリ１０４に格納されているＲとＳのい
ずれか一方の最終データの最終バイトが次処理で出力さ
れるならば状態Ｅへ、そうでなければ状態Ｄへ遷移す
る。２０４の状態Ｄは次の処理から成る。

書込み処理：データ入力端子１０１よりＴのデータ
を１バイト入力し、メモリ１０３と１０４に複写して格
納する。同時に、レジスタ１０６と１０７のいずれか一
方を制御回路１１０からの指示に従い、マルチプレクサ
１０９で選択し、該データをデータ出力端子１０２に出
力する。

読出し処理：状態Ｂの読出し処理と同様である。

メモリ１０３とメモリ１０４に格納されているＲとＳの
いずれか一方の最終データの最終バイトが次の処理で出
力される状態まで状態Ｄを繰り返し、その後、状態Ｅに
遷移する。２０５の状態Ｅは次の処理から成る。

書込み処理：データ入力端子１０１よりＴのデータ
を１バイト入力し、メモリ１０３あるいはメモリ１０４
のうち、ＲまたはＳが全て出力されている側のメモリ
か、この処理で出力される側のメモリとは反対のメモリ
に格納する。同時にレジスタ１０６と１０７のいずれか
一方を制御回路１１０からの指示に従い、マルチプレク
サ１０９で選択し、該データをデータ出力端子１０２に
出力する。

読出し処理：メモリ１０２からＲまたはＳが残って
いれば、ＲまたはＳのデータの１バイト、残っていなけ
ればＴのデータの１バイトを読み出し、レジスタ１０６
に格納すると同時にメモリ１０４からメモリ１０３と同
様にデータの１バイトを読み出しレジスタ１０７に格納
する。（こゝで、比較は行わず、制御回路１１０は次処
理でＲまたはＳのデータの格納されているレジスタから
データを出力するように指示する）。

残っているＲまたはＳの最終データの最終バイトが次処
理で出力される状態、すなわち、Ｔのすべのデータを入
力し終えるまで状態Ｅを繰り返し、その後、状態Ｃに遷
移する。こゝで、Ｔは次の併合されるデータ部分集合対
のＲに等しい。

第２図の状態遷移処理は各比較ユニットで同時に行われ
る。なお、各比較ユニットの制御回路１１０に例えばマ
イクロプロセッサを用いることにより、上記処理は容易
に実現可能である。

第３図は本発明による処理例を示すタイムチャートであ
り、この例では、比較ユニット４０−１，４０−２，４
０−３により、１バイトの大きさのデータ８個の整列を
行っている。第３図において、３００は１バイトの処
理、３０１は書込み処理、３０２は読出し処理、３０３
は１バイトデータ、３０４は整列済みデータ部分集合、
３０５は第２図の状態を示している。また、処理３００
に要する時間を１時刻としている。

第３図の例について、第１図の比較ユニット４０−１，
４０−２，４０−３内でのデータの動きを詳細に示す
と、第４図のようになる。第４図において、４００はデ
ータの流れ、４０１は第２図で示した状態、４０２は比
較結果、４０３はデータ部分集合の区切りを示すもので
ある。比較結果は、「Ｖ」がレジスタ１０６に格納され
ているデータの値がレジスタ１０７に格納されているデ
ータの値よりも大きいことを、「∧」が小さい、「‖」
は等しい、「×」は比較しないことを意味している。

第３図はデータの大きさが１バイトの例であるが、本発
明はデータの大きさが任意の場合について容易に拡張で
きる。データの大きさをＬバイトとする時、比較ユニッ
ト４０−ｉ（ｉ＝１，２，３，…Ｕ）の処理開始時刻を
（２^i-1−１）Ｌ＋ｉ時刻とし、２データの比較は次の
ようにすればよい。すなわち、大きさＬバイトの２デー
タがＫバイトまで同じ値を持っている時、Ｋバイトまで
の出力はレジスタ１０６，１０７の任意の一方とし、次
比較バイトは各データの次バイトとする。Ｋ＋１バイト
目で２データの大小が判定すると、Ｋ＋１バイトからＬ
バイトまでは、データ全体の値の大小により出力する。
次に比較するデータは、その前で最終まで出力したデー
タの次のデータと、途中までしか出力しなかったデータ
であり、各々データの先頭バイトから比較を開始する。

第５図は、大きさ４バイトの２個のデータの比較ユニッ
ト４０−１での整列処理例を示すタイムチャートであっ
て、５０１は書込み処理、５０２は読出し処理、５０３
は４バイトのデータ、５０４は整列済みデータ部分集
合、５０５は第２図の状態を示している。

一般にＮ個のデータの整列は「log₂Ｎ」台の比較ユニッ
トを用いることにより、ＬＮ＋Ｌ・２「log₂Ｎ」「log₂
Ｎ」−Ｌ時刻で処理できる。

〔発明の効果〕

以上説明したように本発明では、１つの比較ユニットに
同一構成のメモリを２つ備えることにより、１つのメモ
リには最大２つのデータ部分集合しか存在せず、かつ、
メモリ内のデータは入力順に順番に並べることができる
ため、メモリ管理が容易になり、また、状態遷移の技分
れが最大２つしかないので、制御も容易になる利点があ
る。さらに、２メモリへのデータの複写及び２メモリか
らの同時データ読出しにより、１バイトの比較処理をメ
モリへの書込み、読出しの２処理で行え、かつ、データ
間の処理の中断がないため、整列時間が短かいという利
点がある。

【図面の簡単な説明】

第１図は本発明によるデータ整列装置の一実施例の構成
図、第２図は第１図における比較ユニットの処理状態の
遷移を示す図、第３図は本発明による処理例を示すタイ
ミング図、第４図は第３図の処理例の詳細な動作を示す
図、第５図は本発明による別の処理例を示すタイミング
図、第６図は従来のデータ整列装置の第１の構成例を示
す図、第７図は第６図の処理例を示すタイミング図、第
８図は第７図の処理例の詳細な動作を示す図、第９図は
従来のデータ整列装置の第２の構成例を示す図、第１０
図は第９図の処理例を示すタイミング図、第１１図は第
１０図の処理例の詳細な動作を示す図である。 １０…データ整列装置、４０−１〜４０−Ｕ…比較ユニ
ット、１０１…データ入力端子、１０２…データ出力端
子、１０３，１０４…メモリ、１０５−１，１０５−２
…読出し／書込み回路、１０６，１０７…レジスタ、１
０８…比較器、１０９…マルチプレクサ、１１０…制御
回路。

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数の比較ユニットを縦続接続し、各比較
   ユニットで並列的に、前段から入力される整列済みデー
   タ部分集合を２組ずつ整列して併合し、該併合結果の整
   列済みデータ部分集合を後段に出力して、データ集合を
   データ値の小さい順もしくは大きい順に並べ換えるデー
   タ整列装置において、各比較ユニットは、前段から入力
   される整列済みデータ部分集合を格納する１対のメモリ
   と、各メモリから読み出されたデータを格納する１対の
   レジスタと、前記レジスタのデータ値を比較する比較器
   と、前記レジスタのいずれか一方のデータを後段に出力
   するマルチプレクサと、前記比較器の比較結果にもとづ
   いて前記マルチプレクサを制御するとゝもに、前記メモ
   リの読み書きを制御し、前段から入力されるデータを２
   つのメモリへ複写して格納し、一方のメモリ内のデータ
   の併合中、データ部分集合がなくなると他方のメモリ内
   の複写データを破棄する制御回路とを具備してなるデー
   タ整列装置。