JPS62271014A - ソ−テイング装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ３、発明の詳細な説明 〔概　要〕 ソーティングを高速に実行する装置。Ｎ個の被処理デー
タのレジスタ、隣接データの大小により２レジスタ間の
データ相互交換を制御する比較器、及びそれらで部分的
にソートされた２組のデータを交互に配置するように並
べ変えるデータ転送手段を設け、比較、交換動作を複数
の部分で並行に実行し、その結果を並べ変える動作を反
復することによりソーティングが実行される。この構成
により、処理実行の並行度を高めることによる、高速ソ
ーティングができる。

〔産業上の利用分野〕

本発明は、データのソーティングを実行する装置に関す
る。

複数のデータを、そのデータ値の大きさによって、増加
又は減少順に整列する処理は、ソート処理あるいはソー
ティング等と呼ばれ、データ処理の各種の面で必要にな
る。

〔従来の技術〕

第４図はソーティング装置の一構成例を示すブロック図
である。

図の３０ａ　、３０ｂ、３１ａ、３１ｂ、３２ａ、３２
ｂ等は、それぞれ１段、２段、４段等の先入先出型の行
列を構成するレジスタの対であり、３０ｃ、３１ｃ、３
２ｃ等は、入力側に接続するレジスタの各先頭のデータ
を比較して、例えば値の大きくない側の１データを次段
のレジスタの一方へ出力するように構成したソーティン
グ回路である。

入力回路３３は被処理データを順次受は入れて、レジス
タ３０ａ　、３０ｂに交互に分配する。

ソーティング回路３０ｃは、レジスタ３０ａ　、３０ｂ
のデータを比較し、例えば小さい方又は同一の場合はそ
の一方を、例えばレジスタ３１ａに出力し、次いで残っ
たデータをレジスタ３１ａに出力することにより、レジ
スタ３１ａ上に図の下から値の小さい順にデータがセッ
トされるようにする。

次にソーティング回路３０ｃは、後続してレジスタ３０
ａ　、３０ｂにセットされるデータを、前と同様に比較
して、レジスタ３１ｂへ出力し、このようにしてソーテ
ィング回路３０ｃは入力データを２個づつ小さい順にな
らべてレジスタ３１ａ　、３１ｂへ交互に出力する。

ソーティング回路３１ｃは、レジスタ３１ａ　、３１ｂ
にセットされたデータの各先頭のデータについて、ソー
ティング回路３０ｃの場合と同様に比較してレジスタ３
２ａ又は３２ｂへ出力する処理により、レジスタ３１ａ
　、３１ｂにある４データを小さい順に先ずレジスタ３
２ａに出力し、次にレジスタ３１ａ　、３１ｂにセント
されるデータを小さい順にレジスタ３２ｂに出力する。

このようにして各ソーティング回路３０ｃ　、３１ｃ、
３２ｃ等は入力側のレジスタの対に大きさの順に整列さ
れた２デ一タ列から、２倍の長さの整列されたデータ列
を構成し、このような構成のレジスタ対とソーティング
回路を直列に接続することによって所要の個数のデータ
のソーティングを行う装置を構成することができる。

〔発明が解決しようとする問題点〕

前記の従来のソーティング装置の構成によれば、各ソー
トされた部分データ列から、２倍長のソートされたデー
タ列を生成する場合に、最大の場合には部分データ列の
全データについて逐次比較しなければならないので、直
列に処理時間が累積され、ソーティング処理の高速化が
難しいという問題がある。

〔問題点を解決するための手段〕

第１図は、本発明の構成を示すブロック図である。

図はソーティング装置の構成を示し、１−０．１−５．
１−２、〜ＬＨ−＋　は被処理データを保持するレジス
タ、２−１．２−ｚ、〜２−Ｎ−１　は比較器、３は所
定のレジスタ間のデータ転送回路、４は制御バスである
。

〔作　用〕

Ｎ個のレジスタ１−０．１−１．１−２．〜１−Ｎ−１
には、ソーティング対象のＮ個のデータが適当な手段で
入力されている。こ＼でＮは２の冨乗とする。

Ｎ−１個の比較２Ｓ２−＋、２−ｚ、〜２−Ｎ−１　は
、各隣接する２レジスタのデータを比較するように接続
されているが、初めに１個置きの比較器２−、．２−：
ｌ、２−５、〜２−□３．２−Ｎ−１を有効化して比較
を実行し、例えばデータ値の小さい方が図の左側になる
ように、各２レジスタ間のデータ交換を制御する。

データ交換が完了すると、データ転送回路３を経由して
、全レジスタ間のデータ転送を同時に並列に行って、デ
ータを並べ変える。

データ並べ変えは、例えば左側半分のレジスタ１−０，
１−１、〜１−Ｎ７□１のデータと、右側のレジスタ１
−ｓ／ｚ〜１−Ｎ−１のデータとが、レジスタ１−０．
１−１．１−２、〜１−、４−＋上に交互に前と同じｊ
１刊序で交互に並ぶようにする。

その結果、例えば４個のレジスタ１−０〜１−１のうち
のレジスタ１−０，１−２とレジスタ１−、．１−３に
それぞれ大小順に並べられたデータが配置されるように
なる。

そこで、比較器２−、．２−２．２−３　、比較器２−
３．２−６．２−７のように、４レジスタごとに区切っ
た範囲の比較器を有効化して比較を実行し、前記と同様
に所要の２レジスタ間のデータ交換を制御する。この場
合、各４レジスタごとにおいて、１又は２回の比較によ
って、０〜３組のデータ交換が起こり、各４レジスタご
とにデータが小さい順に整列される。

次に前記と同様に、データ転送回路３によるデータの並
べ変えを行った後、８レジスタごとに区切って比較器に
よりデータ交換を制御して、８個ごとに整列したデータ
を得る。

このような２動作ステップからなるサイクルを繰り返す
ことにより、各サイクルごとに整列されるデータ列の長
さが２倍になり、最後にＮ個の全データにわたって小さ
い順に並べられたデータ列を得る。

以上の構成により、ソーティング処理の並行実行度が高
められるので、ソーティング装置の処理速度を大幅に改
善することができる。

〔実施例〕

第２図は、第１図のレジスタｌ−０，１−１〜ＬＨ−＋
及び比較器２−、〜２−□１の実施例を示すブロック図
である。

図は１組のレジスタ１　（第１図の左端のレジスタを０
番としてｉ番目のレジスタＲ，とする）及び比較器２（
Ｃ８とする）の構成を両側のレジスタ（Ｒｔ−、及びＲ
ｔ−＋）と比較器（Ｃ，−、及びＣｔ、ｕとの関連を含
めて示す。

比較器Ｃ３はＲ１，レジスタ及びＲ１−１レジスタのレ
ジスタ部１４に保持するデータを、それぞれデータ線１
０及び１１により比較部１２へ人力して比較し、Ｒ，デ
ータがＲ４−１データより小さい場合に、制御線１３を
オンにして、Ｒ、レジスタのゲート１５及びＲ１−１レ
ジスタのゲート１６を制御することにより、両レジスタ
のデータを相互に交換するように制御する。

又、すべての比較器２から制？Ｉ　′！ａ１３の出力信
号と同一の状態を示す信号が、信号線１９によって制御
バス４へ出力され、従って制御バス４がオン信号状態に
あることによって、何れかの比較器２でデータ交換制御
が実行されていることを表示する。

この制御バス４の信号はすべてのレジスタｌのゲート１
７を制御■シて、データ交換動作が終了するまで、デー
タ転送回路３によるデータ並べ変えの実行を抑止する。

ゲート１８はデータ交換又は並べ変えによるレジスタ部
設定を制御するクロック信号を制御する。

比較器２の比較部１２は、制御部２０によって制御され
、制？１１線２１がオンの場合のみ比較動作を有効化さ
れる。

各比較器２の制御部２０は図示のようにｌｏｇｚＮビッ
トのシフトレジスタ２２を有し、その１ビツトの出力を
制御線２１に接続する。接続するビットは、図の右から
ｊ＋１番目のビットとし、ｊの値はＣ８比較器の場合に
、 ｉ＝に、２Ｊ　（但し、ｋは奇数） をンｍ足するように選ぶ。

このようにして、全制御部２０のシフトレジスタ２２を
すべて０゛にリセットして動作を開始し、制ｔＢバス４
の信号がオフになるごとに信号線２３から１”信号を人
力して、シフトレジスタ２２をシフトさせる。その結果
、比較器２はｊ回目の動作サイクル以後制御線２１がオ
ン（信号“１゛）になり、比較動作が有効化される。

即ち、有効化される比較器は、第１サイクルではＣ＋　
：Ｃｉ：Ｃｓ：Ｃ７：Ｃ９：Ｃ＋　ｌ　：ｃｌ　ｓ：ｃ
ｌ　ｓ等のように１個置きの比較器であり、第２サイク
ルでは、Ｃ，、Ｃ２，Ｃ３：Ｃ，、ＣいＣ７；等のよう
に４個ごとに３個の比較器が有効化され、次はＣ，−Ｃ
，がすぺで有効化されてＣ＠が抜けた状態になるという
ように、順次前の２倍の範囲で連続する比較器が有効化
されるように制御することができる。

こ＼で、例えば第２サイクルとして、第１図の比較器２
−１，２−２．２−３のように、隣接する比較器が有効
化されても、この場合にもし隣接する比較器、例えば比
較器２−１と２−２が同時にデータ交換を要する状態を
検出すると、レジスタ１−０と１−１の間のデータ交換
と、レジスタ１−１と１−２の間のデータ交換が同時に
起こり、不確定な制御を生じることになる。しかし、並
べ変えによってレジスタ１−〇、１−１．１−２．１−
３にセットされている１個置きのデータ列が、それぞれ
大きさの順に整列されたデータ列であることから、その
ような状況が起こり得ないことは明らかである。

ある動作サイクルで、すべての比較器２のデータ交換制
御が終わることにより、制御バス４がオフになると、制
御バス４の信号でレジスタ１のゲート１７が開かれ、全
レジスタ間でデータ転送回路３を経由するデータの並べ
変えが行われる。

この並べ変えにより、Ｒ０〜ＲＮ／□−１のデータ列と
、ＲＮ／Ｚ　−’　ＲＮ−１のデータ列が１つ置きに交
互に配置されるようにする。

そのためにデータ転送回路３は、レジスタＲ５の出力を
レジスタＲイのゲート１７へ接続するものとして、 ｍ＝２ｉ　　ｍｏｄＮ−１（但しｉ＜Ｎ−１）ｍ＝ｉ　
　　　　　　（但し１＝Ｎ−１）とする。このようにす
ることにより、例えばＮ＝１６の場合について第３図に
示すような転送による、データの並べ変えが行われる。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、従来
より並列実行度を高めて高速化したソーティング装置を
実現することができるという著しい工業的効果がある。

【図面の簡単な説明】

第１図は本発明の構成を示すブロック図、第２図は本発
明の実施例を示すブロック図、第３図は、データ並べ変
えの説明図、 第４図は従来の一構成例ブロック図 である。 図において、 １．１−０〜Ｌ、４−＋　はレジスタ、２．２−、〜２
−Ｎ−１　は比較器、 ３はデータ転送回路、　４は制御バス、１２は比較部、
　　　　　　１４はレジスタ部、２０は制御部、　　　
　　２２はシフトレジスタ３０ａ　、３０ｂ〜３２ａ　
、３２ｂはレジスタ、３３は入力回路、 ３０ｃ〜３２ｃはソーティング回路 を示す。

Claims (1)

1. 【特許請求の範囲】 Ｎ個のデータを、該データの値の大きさの順に整列する
   に際し、 該データを保持し所定の順序に配列されたＮ個のレジス
   タ（１−＿０〜１−＿Ｎ＿−＿１）、該レジスタの各隣
   接する２レジスタに保持されるデータの値を比較し、 所定の比較結果により該２レジスタのデータを相互に交
   換するＮ−１個の比較器（２−＿１〜２−＿Ｎ＿−＿１
   ）、及び、半数の該レジスタと他の半数の該レジスタと
   のデータが同一の順序で交互に保持されるように並べ変
   えて該レジスタに設定するデータ転送手段（３）を設け
   、 前記該比較器の比較及びデータ交換動作を、所定のすべ
   ての比較器について並行に実行し、該実行を該データ交
   換が発生されなくなるまで反復する動作ステップと、 前記データ転送手段によるデータ並べ変えを実行する動
   作ステップとを、交互に実行するように構成されている
   ことを特徴とするソーティング装置。