JPH04365129A - ソート処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明はソート処理装置に関し
、特に２ウェイマージソートのアルゴリズムにしたがっ
て２組の入力データをマージソートするパイプライン構
成のソート処理装置に関する。

【０００２】

【従来の技術】一般に、２ウェイマージソートのアルゴ
リズムにしたがってソート処理を行うソート処理装置は
、そのソート処理の高速化を実現するために、図６のよ
うな構成のハードウェア演算回路を利用している。すな
わち、図６の装置は、ソートセル１−１、１−２、…１
−ｎを直列接続して構成されるものであり、ソートセル
１−１、１−２、…１−ｎの各々は、２組の入力データ
をマージソートして整列化されたデータ列を出力する。

【０００３】これらソートセル１−１、１−２、…１−
ｎの各々は、入力されたデータを一時的に保持するバッ
ファメモリと、このバッファメモリに保持されたデータ
をソートするソート制御部とから構成されている。すな
わち、第１段目のソートセル１−１はソート制御部１１
−１およびバッファメモリ１２−１から構成され、第２
段目のソートセル１−２はソート制御部１１−２および
バッファメモリ１２−２から構成され、そして、第ｎ段
目のソートセル１−ｎはソート制御部１１−ｎおよびバ
ッファメモリ１２−ｎから構成されている。各ソート制
御部はコントロール回路をもっていて、メモリアドレス
を対応するバッファメモリに直接入力してアクセスする
。

【０００４】ここで、２ウェイマージソートのアルゴリ
ズムの性格上、バッファメモリの容量は、１段目のソー
トセル１−１でソート対象データ長（例えばレコード長
）の２倍、２段目のソートセル１−２で４倍、そして、
ｎ段目のソートセル１−ｎで２ｎ　倍必要となる。

【０００５】これは、２ウェイマージソートにおいては
、１段目のソートセル１−１は入力データ列の先頭から
順に２個づつバッファメモリ１２−１にデータを格納し
てそれら２個のデータ間のソートを行い、２段目のソー
トセル１−２は１段目のソートセル１−１でソートされ
たデータ列を２組づつバッファメモリ１２−２に格納し
てそれら２組のデータ列（４個のデータ）間のソートを
行い、さらに、３段目のソートセルは、２段目のソート
セル１−２でソートされたデータ列を２組づつバッファ
メモリに格納してそれら２組のデータ列（８個のデータ
）間のソートを行うからである。

【０００６】このように、２ウェイマージソートを行う
図６のようなパイプライン構成のソート処理装置におい
ては、最終段のソートセルのバッファメモリは大きな記
憶容量が必要であるが、初段のソートセルのバッファメ
モリは少量の記憶容量で十分である。

【０００７】ところが、実際には、バッファメモリとし
て使用される半導体メモリチップの種類も限られている
ので、各バッファメモリの記憶容量に適したメモリを全
ての段のソートセルについて用意することは困難である
。このため、従来では、比較的記憶容量の大きいメモリ
チップが各段のソートセル毎に設けられていた。この場
合、終段側のソートセルについては特に問題はないが、
初段側のソートセルについては、そのメモリチップの記
憶容量の大半が使用されず無駄になる。

【０００８】また、ソート制御部１１−１〜１１−ｎは
それぞれ別個のメモリバスを介してバッファメモリ１２
−１〜１２−ｎをそれぞれアクセスする構成であるため
、これらソート制御部１１−１〜１１−ｎを１チップＬ
ＳＩ化する場合には、それぞれのメモリバスを独立にチ
ップから導出するために多くの入出力ピンが必要となり
、１チップ化の実現は困難であった。

【０００９】

【発明が解決しようとする課題】従来では、バッファメ
モリの使用効率が悪く、また必要となる入出力ピンの数
が増加されることから１チップＬＳＩ化することが困難
であった。

【００１０】この発明はこのような点に鑑みてなされた
もので、メモリの使用効率の向上、および１チップＬＳ
Ｉ化に適した構成のソート処理装置を提供することを目
的とする。

【００１１】

【課題を解決するための手段および作用】この発明は、
２組の入力データをマージソートするソートセルをｎ個
直列に接続する事により２ｎ　個のデータを一度にソー
ト処理するように構成され、各ソートセルが、入力され
たデータを一時的に保持するバッファメモリ、このバッ
ファメモリに保持されたデータのソートを実行するソー
ト実行部、および前記ソート実行部と前記バッファメモ
リ間を接続するメモリバスを有するソート処理装置にお
いて、前記ソート実行部の各々のメモリバスを共通接続
して外部メモリに導出する手段と、前記各ソート実行部
によるメモリバスの使用タイミングを制御する手段とを
具備し、前記複数のソート実行部が共通のメモリバスを
介して前記外部メモリをアクセスするように構成されて
いることを特徴とする。

【００１２】このソート処理装置においては、複数のソ
ート実行部のメモリバスが共通接続され、その共通のメ
モリバスの使用タイミングが複数のソート実行部間で制
御されるので、同一の外部メモリをバッファメモリとし
て使用することができ、メモリの使用効率を向上できる
。また、各ソートセルからのメモリバスが一本化される
ことにより、メモリバス用の入出力ピンが減少し、複数
のソート実行部を１チップ上に集積形成することが容易
となる。

【００１３】

【実施例】以下、図面を参照してこの発明の実施例を説
明する。

【００１４】図１にはこの発明の一実施例に係わるソー
ト処理装置が示されている。このソート処理装置は、パ
イプライン方式でソート処理を実行するものであり、直
列接続されたソートセル２１−１〜２１−ｎによって構
成されている。ソートセル２１−１〜２１−ｎは、ソー
ト制御部２２−１〜２２−ｎをそれぞれ備えている。こ
れらソート制御部２２−１〜２２−ｎは、２ウェイマー
ジソートアルゴリズムに従ったソート処理、およびソー
トセル全体の制御を行う。

【００１５】ソート制御部２２−１〜２２−ｎは、共通
のメモリバス２３を介してメモリ２４に接続されている
。メモリ２４は、入力データを格納するためのバッファ
メモリとしてソート制御部２２−１〜２２−ｎによって
共通に使用される。

【００１６】第１段目のソート制御部２２−１は、デー
タが入力されると、メモリバス２３を通してメモリ２４
にそのデータを一時保持し、データがそろいソートでき
る状態になると（２個のデータが格納された状態）、メ
モリバス２３を通してメモリ２４からデータを読み出し
ソートを行い、第２段目のソート制御部２２−２にデー
タを出力する。

【００１７】第２段目のソート制御部２２−２も同様の
動作を行い、それぞれ２個のデータから構成される２組
のデータ列をソート制御部２２−１から受取り、それを
ソートして第３段目のソート制御部２２−３に出力する
。これをセル毎に繰り返して、全体をソートする。

【００１８】メモリ２４は、メモリバス２３を通して１
段目、２段目、…ｎ段目のソート制御部２２−１〜２２
−ｎからのデータを受け、一時的に保持し、ソート制御
部が必要なときにメモリバス２３を通してそれぞれのソ
ート制御部にデータを返す。この場合、メモリ２４の記
憶領域はソート制御部２２−１〜２２−ｎによって分割
されて使用される。次に、図２を参照して、ソート制御
部２２−１〜２２−ｎの具体的な構成の一例を説明する
。

【００１９】図２に示されているように、各ソート制御
部は、レジスタＲ０，Ｒ１，Ｒ２、比較器Ｃ１、セレク
タＳ１、およびコントロール回路３０から構成されてい
る。レジスタＲ０は、入力データをメモリ２４に書き込
むためのバッファとして使用される。レジスタＲ１には
、メモリ２４から読み出された２組のデータの内の一方
が保持される。また、レジスタＲ２には、メモリ２４か
ら読み出された２組のデータの内の他方が保持される。

【００２０】比較器Ｃ１は、レジスタＲ１のデータとレ
ジスタＲ２のデータの値の大小を比較し、その比較結果
をコントロール回路３０に通知する。セレクタＳ１は、
コントロール回路３０の指示に応じて、レジスタＲ１と
レジスタＲ２のデータを選択的に出力する。コントロー
ル回路３０は、ソート制御部全体の動作を制御するもの
であり、メモリ２４に対するデータのリード／ライトの
ためにメモリアドレスおよびリード／ライト信号をメモ
リバス２３を介してメモリ２４に供給すると共に、比較
器Ｃ１の比較結果にしたがってセレクタＳ１を制御する
。

【００２１】セレクタＳ１の制御においては、例えば、
入力データを昇順にソートする場合には、レジスタＲ１
とレジスタＲ２の中で、値の小さいデータが保持されて
いる方のレジスタから先にデータが読み出される。また
、入力データを降順にソートする場合には、レジスタＲ
１とレジスタＲ２の中で、値の大きいデータが保持され
ている方のレジスタから先にデータが読み出される。

【００２２】また、コントロール回路３０によるメモリ
アドレスおよびリード／ライト信号の発生タイミングは
、メモリ２４のリード／ライトがソート制御部２２−１
〜２２−ｎで順番に実行されるように、外部からのタイ
ミング制御信号によって制御される。次に、図３を参照
して、ソート制御部２２−１〜２２−ｎを１チップＬＳ
Ｉ化した場合の構成について説明する。

【００２３】ここでは、簡単のために、５個のソート制
御部２２−１〜２２−５を単一の半導体チップ１００上
に集積形成した例が示されている。ソート制御部２２−
１〜２２−５は、外部から供給されるタイミング制御信
号にしたがって共通のメモリバス２３を順番に使用し、
ソート制御部２２−１はメモリ２４の第１記憶領域（Ｍ
１）に対してデータ入出力を行い、同様に、ソート制御
部２２−２はメモリ２４の第２記憶領域（Ｍ２）に対し
て、ソート制御部２２−３はメモリ２４の第３記憶領域
（Ｍ３）に対して、ソート制御部２２−４はメモリ２４
の第４記憶領域（Ｍ４）に対して、ソート制御部２２−
５はメモリ２４の第５記憶領域（Ｍ５）に対してそれぞ
れデータ入出力を行う。ソート制御部２２−１〜２２−
５に割り当てられるメモリバス２３の使用タイミングは
、図４の通りである。

【００２４】図４において、タイムスロットＴ１はソー
ト制御部２２−１によるメモリバス２３の使用タイミン
グを示し、同様に、タイムスロットＴ２はソート制御部
２２−２のメモリバス使用タイミング、タイムスロット
Ｔ３はソート制御部２２−３のメモリバス使用タイミン
グ、タイムスロットＴ４はソート制御部２２−４のメモ
リバス使用タイミング、タイムスロットＴ５はソート制
御部２２−５のメモリバス使用タイミングを示している
。

【００２５】各タイムスロットは、メモリ２４に対する
１回のデータ書き込み期間と２回のデータ読み出し期間
とに分割されている。データ書き込み期間は、レジスタ
Ｒ０からメモリ２４へのデータ書き込みに用いられ、ま
た、２回のデータ読み出し期間は、メモリ２４からレジ
スタＲ１へのデータ読み出し、およびメモリ２４からレ
ジスタＲ２へのデータ読み出しに用いられる。次に、図
５を参照して、ソート処理動作を説明する。ここでは、
“１”，“３”，“５”，“７”，“４”，“２”，“
６”，“８”……の順に並んだ入力データを、昇順にソ
ートする場合を考える。

【００２６】ソート制御部２１−１は、入力データを先
頭から順に記憶領域Ｍ１に書き込み、入力データを２個
のデータ単位で小さい順に並べ変えて出力する。ここで
、データ“１”，“５”，“４”，“６”はレジスタＲ
１側に順次読み出され、データ“３”，“７”，“２”
，“８”はレジスタＲ２側に順次読み出される。 そして、レジスタＲ１とＲ２のデータが比較され、小さ
いほうのデータが先に出力される。この結果、ソート制
御部２１−１からは、データ“１”，“３”がソートさ
れた第１組、データ“５”，“７”がソートされた第２
組、データ“２”，“４”がソートされた第３組、デー
タ“６”，“８”がソートされた第４組目のデータとし
て出力される。

【００２７】ソート制御部２１−２は、ソート制御部２
１−１からの出力データを順次記憶領域Ｍ２に書き込み
、４個のデータ単位で小さい順に並べ変えて出力する。 ここで、第１組目のデータと第３組目のデータはレジス
タＲ１側に順次読み出され、第２組目のデータと第４組
目のデータはレジスタＲ２側に順次読み出される。 この場合、データの比較は、まず、第１組のデータの先
頭データ“１”と第２組のデータの先頭データ“５”と
の間で行われ、小さいほうのデータ“１”が出力される
。そして、そのレジスタＲ１にデータ“３”が読み出さ
れて、今度は、データ“５”とデータ“３”との比較が
行われ、小さいほうのデータ“１”が出力される。この
様にして、値の大きい方のデータをレジスタに残して行
き、順次２個のデータ間での比較が行われる。この結果
、ソート制御部２１−２からは、データ“１”，“３”
，“５”，“７”がソートされた第１組目のデータとし
て出力され、データ“２”，“４”，“６”，“８”が
ソートされた第２組目のデータとして出力される。

【００２８】ソート制御部２１−３は、ソート制御部２
１−２からの出力データを順次記憶領域Ｍ３に書き込み
、８個のデータ単位で小さい順に並べ変えて出力する。 ここで、第１組目のデータはレジスタＲ１側に順次読み
出され、第２組目のデータはレジスタＲ２側に順次読み
出される。この場合、データの比較は、まず、第１組の
データの先頭データ“１”と第２組のデータの先頭デー
タ“２”との間で行われ、小さいほうのデータ“１”が
出力される。そして、そのレジスタＲ１にデータ“３”
が読み出されて、今度は、データ“２”とデータ“３”
との比較が行われ、小さいほうのデータ“２”が出力さ
れる。この様にして、値の大きい方のデータをレジスタ
に残して行き、順次２個のデータ間での比較が行われる
。この結果、ソート制御部２１−３からは、データ“１
”，“２”，“３”，“４”，“５”，“６”，“７”
，“８”がソートされた第１組目のデータとして出力さ
れる。

【００２９】ここで、ソート制御部２１−１〜２１−３
によるメモリアクセス動作は前述のタイムスロットＴ１
〜Ｔ３の期間にそれぞれ行われるものであるので、ソー
ト対象の入力データが順次ソート制御部２１−１に入力
され、ソートされた８個のデータが順番にソート制御部
２１−３から出力されていく過度状態においては、レジ
スタＲ０からメモリに対する１回の書き込み動作と、メ
モリからレジスタＲ１，Ｒ２への２回の読み出し動作と
によって、ソート制御部２１−１〜２１−３はパイプラ
イン的に動作することになる。

【００３０】以上のように、この実施例においては、複
数のソート制御部２１−１〜２２−ｎが１つのメモリバ
ス２３を共通に使用し、その共通のメモリバス２３の使
用タイミングが複数のソート制御部２１−１〜２２−ｎ
間で順番に制御されるので、同一の外部メモリ２４をバ
ッファメモリとして使用することができ、メモリの使用
効率を向上できる。

【００３１】また、メモリバスが一本化されることによ
り、メモリバス用の入出力ピンが減少し、入出力ピン数
の増大を招くこと無く、複数のソート制御部２１−１〜
２２−ｎを１チップ上に集積形成することができる。

【００３２】

【発明の効果】以上のように、この発明によれば、複数
のソート実行部のメモリバスを接続して同一メモリをバ
ッファメモリとして使用することにより、メモリの使用
効率の向上、および１チップＬＳＩ化に適したソート処
理装置を提供できる。

【図面の簡単な説明】

【図１】この発明の一実施例に係わるソート処理装置の
構成を示すブロック図。

【図２】同実施例のソート制御部の具体的な構成の一例
を示すブロック図。

【図３】同実施例の複数のソート制御部を１チップ上に
集積形成した場合の具体的な構成の一例を示すブロック
図。

【図４】同実施例の複数のソート制御部に割り当てられ
るメモリバスの使用タイミングを示す図。

【図５】同実施例の動作を模式的に示す図。

【図６】従来のソート処理装置の構成を示すブロック図
。

【符号の説明】

２１−１〜２１−ｎ…ソートセル、２２−１〜２２−ｎ
…ソート制御部、２３…メモリバス、２４…メモリ。

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　２組の入力データをマージソートする
   ソートセルをｎ個直列に接続する事により２ｎ　個のデ
   ータを一度にソート処理するように構成され、各ソート
   セルが、入力されたデータを一時的に保持するバッファ
   メモリ、このバッファメモリに保持されたデータのソー
   トを実行するソート実行部、および前記ソート実行部と
   前記バッファメモリ間を接続するメモリバスを有するソ
   ート処理装置において、前記ソート実行部の各々のメモ
   リバスを共通接続して外部メモリに導出する手段と、前
   記各ソート実行部によるメモリバスの使用タイミングを
   制御する手段とを具備し、前記複数のソート実行部が共
   通のメモリバスを介して前記外部メモリをアクセスする
   ように構成されていることを特徴とするソート処理装置
   。
2. 【請求項２】　　前記複数のソート実行部は１チップ上
   に集積形成されて成ることを特徴とする請求項１記載の
   ソート処理装置。