JPH01177122A - ソート処理装置 - Google Patents
ソート処理装置Info
- Publication number
- JPH01177122A JPH01177122A JP161488A JP161488A JPH01177122A JP H01177122 A JPH01177122 A JP H01177122A JP 161488 A JP161488 A JP 161488A JP 161488 A JP161488 A JP 161488A JP H01177122 A JPH01177122 A JP H01177122A
- Authority
- JP
- Japan
- Prior art keywords
- data
- input
- sorting
- address
- bank
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Executing Machine-Instructions (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はソート処理装置に関し、特にメモリ上に配置さ
れる大量のデータを、高速にマージソートすることが可
能なソート処理装置に関する。
れる大量のデータを、高速にマージソートすることが可
能なソート処理装置に関する。
従来、ソート処理装置としては、例えば、特開昭６１−
４２０３１号公報に開示されている装置が知られている
。この装置は、ｋ（ｋ：１より大きな整数）個のデータ
のうち最大もしくは最小のデータを抽出するソート手段
と、予め昇順もしくは降順に並べ替えられたに個のデー
タ列を格納するデータ格納手段を有し、前記に個のデー
タ列の各々の先頭データを前記ソート手段に入力し、該
ソート手段からデータを出力する操作と、前記入力操作
とを交互に実行するマージ操作を繰り返すことによって
、前記データ格納手段に格納された複数のデータ列をマ
ージするソート処理装置において、上記データ格納手段
上に配置したに個のデータ列からソート手段に入力する
データのアドレスを、各データ列の残りデータ数を計数
するカウンタの値をシフトして生成するものであった。
４２０３１号公報に開示されている装置が知られている
。この装置は、ｋ（ｋ：１より大きな整数）個のデータ
のうち最大もしくは最小のデータを抽出するソート手段
と、予め昇順もしくは降順に並べ替えられたに個のデー
タ列を格納するデータ格納手段を有し、前記に個のデー
タ列の各々の先頭データを前記ソート手段に入力し、該
ソート手段からデータを出力する操作と、前記入力操作
とを交互に実行するマージ操作を繰り返すことによって
、前記データ格納手段に格納された複数のデータ列をマ
ージするソート処理装置において、上記データ格納手段
上に配置したに個のデータ列からソート手段に入力する
データのアドレスを、各データ列の残りデータ数を計数
するカウンタの値をシフトして生成するものであった。
上記従来技術は、メモリ上に格納するデータの格納効率
について配慮がなされておらず、データ列の先頭アドレ
スやデータ列の長さは少なくとも２のべき乗でしか可変
できないので、メモリ上に大量の空き領域ができ、ソー
ト件数が減ってしまうという問題があった。
について配慮がなされておらず、データ列の先頭アドレ
スやデータ列の長さは少なくとも２のべき乗でしか可変
できないので、メモリ上に大量の空き領域ができ、ソー
ト件数が減ってしまうという問題があった。
本発明は上記事情に鑑みてなされたもので、その目的と
するところは、従来のソート処理装置における上述の如
き問題を解消し、メモリの空き領域を小さくし、大量の
データのソートを可能とするソート処理装置を提供する
ことにある。
するところは、従来のソート処理装置における上述の如
き問題を解消し、メモリの空き領域を小さくし、大量の
データのソートを可能とするソート処理装置を提供する
ことにある。
〔課題を解決するための手段〕
本発明の上記目的は、ｋ（ｋ：１より大きな整数）個の
データのうち最大もしくは最小のデータを抽出するソー
ト手段と、予め昇順もしくは降順に並べ替えられたに個
のデータ列を格納するデータ格納手段を有し、前記に個
のデータ列の各々の先頭データを前記ソート手段に入力
し、該ソート手段からデータを出力する操作と、前記入
力操作とを交互に実行するマージ操作を繰り返すことに
より、前記データ格納手段に格納された複数のデータ列
をマージするソート処理装置において、前記に個のデー
タ列中の最大もしくは最小のデータのアドレスを保持す
るアドレステーブルを設けるとともに、前記データ格納
手段から前記ソート手段への入力データに、前記に個の
データ列のどのデータであるかを示す識別子を付加し、
前記ソート手段が出力するデータの前記識別子の値によ
って、前記アドレステーブルを索引して前記ソート手段
に入力するデータのアドレスを得る手段を設けたことを
特徴とするソート処理装置によって達成される。
データのうち最大もしくは最小のデータを抽出するソー
ト手段と、予め昇順もしくは降順に並べ替えられたに個
のデータ列を格納するデータ格納手段を有し、前記に個
のデータ列の各々の先頭データを前記ソート手段に入力
し、該ソート手段からデータを出力する操作と、前記入
力操作とを交互に実行するマージ操作を繰り返すことに
より、前記データ格納手段に格納された複数のデータ列
をマージするソート処理装置において、前記に個のデー
タ列中の最大もしくは最小のデータのアドレスを保持す
るアドレステーブルを設けるとともに、前記データ格納
手段から前記ソート手段への入力データに、前記に個の
データ列のどのデータであるかを示す識別子を付加し、
前記ソート手段が出力するデータの前記識別子の値によ
って、前記アドレステーブルを索引して前記ソート手段
に入力するデータのアドレスを得る手段を設けたことを
特徴とするソート処理装置によって達成される。
本発明に係わるソート処理装置においては、前記ソート
手段から出力されたデータには前記識別子が付加されて
おり、該識別子は前記に個のデータ列をそれぞれ識別可
能な値１例えば、１，２．・・・・ｋをとっており、前
記アドレステーブルに保持するに個のアドレスは、前記
識別子の値にそれぞれ対応したデータ列の最大もしくは
最小のデータのアドレスである。
手段から出力されたデータには前記識別子が付加されて
おり、該識別子は前記に個のデータ列をそれぞれ識別可
能な値１例えば、１，２．・・・・ｋをとっており、前
記アドレステーブルに保持するに個のアドレスは、前記
識別子の値にそれぞれ対応したデータ列の最大もしくは
最小のデータのアドレスである。
前記ソート手段には、各データ列から一つずつに個のデ
ータが格納されており、その中から最大もしくは最小の
データを出力する。このとき、本発明に係わるソート処
理装置においては、出力されたデータが格納されていた
データ列から次のデータを読出すために、該データに付
加されている識別子の値に対応する前記アトレイテーブ
ル中のアドレスの示すデータを読出し、該アドレスを１
デ一タ分だけ進めるとともに、読出したデータを前記ソ
ート手段に格納する一連の動作をデータ列中のデータが
すべてなくなるまで繰り返す。
ータが格納されており、その中から最大もしくは最小の
データを出力する。このとき、本発明に係わるソート処
理装置においては、出力されたデータが格納されていた
データ列から次のデータを読出すために、該データに付
加されている識別子の値に対応する前記アトレイテーブ
ル中のアドレスの示すデータを読出し、該アドレスを１
デ一タ分だけ進めるとともに、読出したデータを前記ソ
ート手段に格納する一連の動作をデータ列中のデータが
すべてなくなるまで繰り返す。
これにより、ソートが行われ、また、前記アドレステー
ブルに設定するアドレスをメモリの空き領域が最小とな
るように選ぶことができる。
ブルに設定するアドレスをメモリの空き領域が最小とな
るように選ぶことができる。
以下、本発明の実施例を図面に基づいて詳細に説明する
。
。
第１図は、本発明の一実施例を示すソート処理装置の構
成図である。図において、１はワークメモリ、２はソー
ト回路、３はアドレステーブル、４は入力レジスタ、５
は出力レジスタ、６は入力バンクレジスタ、７は出力バ
ンクレジスタ、８は出力線、９は加算器を示している。
成図である。図において、１はワークメモリ、２はソー
ト回路、３はアドレステーブル、４は入力レジスタ、５
は出力レジスタ、６は入力バンクレジスタ、７は出力バ
ンクレジスタ、８は出力線、９は加算器を示している。
ワークメモリ１には、ｋ個の予め昇順に並べ替えられた
データ列（バンク）が格納されており、本ワークメモリ
１のデータ出力は入力レジスタ４に転送され、入力バン
クレジスタ６の内容と合わせてソート回路２に格納され
る。
データ列（バンク）が格納されており、本ワークメモリ
１のデータ出力は入力レジスタ４に転送され、入力バン
クレジスタ６の内容と合わせてソート回路２に格納され
る。
ソート回路２から取出されたデータは、出力レジスタ５
１こ転送され、データ部分は出力線８を介して出力され
る。出力バンクレジスタ７は、入力バンクレジスタ６の
入力およびアドレステーブル３のアドレスに接続されて
おり、アドレステーブル３の出力は、ワークメモリ１の
アドレスおよび加算器９に接続されている。加算器９の
出力は、アドレステーブル３の入力に接続されている。
１こ転送され、データ部分は出力線８を介して出力され
る。出力バンクレジスタ７は、入力バンクレジスタ６の
入力およびアドレステーブル３のアドレスに接続されて
おり、アドレステーブル３の出力は、ワークメモリ１の
アドレスおよび加算器９に接続されている。加算器９の
出力は、アドレステーブル３の入力に接続されている。
以下、上述の如く構成された本実施例の動作を説明する
。
。
まず、ワークメモリ１内のに個のバンクがら一つずつ最
小のデータとそれぞれのバンクを識別するバンク番号を
、入力レジスタ４とその一部である入力バンクレジスタ
６を介してソート回路２に入力する。ソート回路２は入
力されたデータのうち、最小のものを出力する回路であ
り、入力されたに個のデータのうちの最小のデータが出
力レジスタ５に格納される。このとき、出力レジスタ５
の一部である出力バンクレジスタ７には、ｋ個のデータ
のうち、最小のデータを保持していたバンクの番号が格
納されている。
小のデータとそれぞれのバンクを識別するバンク番号を
、入力レジスタ４とその一部である入力バンクレジスタ
６を介してソート回路２に入力する。ソート回路２は入
力されたデータのうち、最小のものを出力する回路であ
り、入力されたに個のデータのうちの最小のデータが出
力レジスタ５に格納される。このとき、出力レジスタ５
の一部である出力バンクレジスタ７には、ｋ個のデータ
のうち、最小のデータを保持していたバンクの番号が格
納されている。
次に、上述の最小のデータを保持していたバンクから、
次に小さいデータを取出すため、出力バンクレジスタ７
の値でアドレス付けられるアトレイテーブル３を読出す
。アドレステーブル３は、各々のバンクから次に読出す
べきアドレスを保持しており、出力バンクレジスタ７の
値で読出しを行った後、加算器９により前記アドレスが
ワークメモリ１の当該バンクの更に次のデータアドレス
を示すように更新され、格納される。
次に小さいデータを取出すため、出力バンクレジスタ７
の値でアドレス付けられるアトレイテーブル３を読出す
。アドレステーブル３は、各々のバンクから次に読出す
べきアドレスを保持しており、出力バンクレジスタ７の
値で読出しを行った後、加算器９により前記アドレスが
ワークメモリ１の当該バンクの更に次のデータアドレス
を示すように更新され、格納される。
前記アドレスでワークメモリ１を読出し、出力バンクレ
ジスタ７の内容を入力バンクレジスタ６へ転送し、ソー
ト回路２へ入力することにより、ソート回路２には空で
ないバンクの各々の最小データを常に格納しておくこと
が可能となり、マージンートができる。このとき、各バ
ンクのあるデータのアドレスに加算器９によりある値、
例えば「データ長」を加えると、該バンクの次のデータ
のアドレスとなるように、各々のデータを配置しておく
。
ジスタ７の内容を入力バンクレジスタ６へ転送し、ソー
ト回路２へ入力することにより、ソート回路２には空で
ないバンクの各々の最小データを常に格納しておくこと
が可能となり、マージンートができる。このとき、各バ
ンクのあるデータのアドレスに加算器９によりある値、
例えば「データ長」を加えると、該バンクの次のデータ
のアドレスとなるように、各々のデータを配置しておく
。
本実施例によれば、ソート回路２にはバンクの番号だけ
を付加すれば良く、ソート回路２内でのデータ長が長く
ならず、性能向上効果がある。
を付加すれば良く、ソート回路２内でのデータ長が長く
ならず、性能向上効果がある。
なお、本発明は、上記実施例に限られるべきものではな
く、例えば、昇順と降順のどちらでもソート可能である
ソータや、バンク識別子をワークメモリ中に格納するソ
ータ、出力データをワークメモリ内に格納し多段のマー
ジを行うソータ等を構成することも容易である。
く、例えば、昇順と降順のどちらでもソート可能である
ソータや、バンク識別子をワークメモリ中に格納するソ
ータ、出力データをワークメモリ内に格納し多段のマー
ジを行うソータ等を構成することも容易である。
以上述べた如く、本発明によれば、ｋ（ｋ：１より大き
な整数）個のデータのうち最大もしくは最小のデータを
抽出するソート手段と、予め昇順もしくは降順に並べ替
えられたに個のデータ列を格納するデータ格納手段を有
し、前記に個のデータ列の各々の先頭データを前記ソー
ト手段に入力し、該ソート手段からデータを出力する操
作と、前記入力操作とを交互に実行するマージ操作を繰
り返すことにより、前記データ格納手段に格納された複
数のデータ列をマージするソート処理装置において、前
記に個のデータ列中の最大もしくは最小のデータのアド
レスを保持するアドレステーブルを設けるとともに、前
記データ格納手段から前記ソート手段への入力データに
、前記に個のデータ列のどのデータであるかを示す識別
子を付加し、前記ソート手段が出力するデータの前記識
別子の値により、前記アドレステーブルを索引して前記
ソート手段に入力するデータのアドレスを得る手段を設
けたので、メモリの空き領域を小さくし、大量のデータ
のソートを可能とするソート処理装置を実現できるとい
う顕著な効果−を奏するものである。
な整数）個のデータのうち最大もしくは最小のデータを
抽出するソート手段と、予め昇順もしくは降順に並べ替
えられたに個のデータ列を格納するデータ格納手段を有
し、前記に個のデータ列の各々の先頭データを前記ソー
ト手段に入力し、該ソート手段からデータを出力する操
作と、前記入力操作とを交互に実行するマージ操作を繰
り返すことにより、前記データ格納手段に格納された複
数のデータ列をマージするソート処理装置において、前
記に個のデータ列中の最大もしくは最小のデータのアド
レスを保持するアドレステーブルを設けるとともに、前
記データ格納手段から前記ソート手段への入力データに
、前記に個のデータ列のどのデータであるかを示す識別
子を付加し、前記ソート手段が出力するデータの前記識
別子の値により、前記アドレステーブルを索引して前記
ソート手段に入力するデータのアドレスを得る手段を設
けたので、メモリの空き領域を小さくし、大量のデータ
のソートを可能とするソート処理装置を実現できるとい
う顕著な効果−を奏するものである。
第１図は本発明の一実施例を示すソート処理装置の構成
図である。 １：ワークメモリ、２：ソート回路、３ニアドレステー
ブル、４：入力レジスタ、５：出力レジスタ、６：入力
バンクレジスタ、７：出力バンクレジスタ、８：出力線
、９：加算器。
図である。 １：ワークメモリ、２：ソート回路、３ニアドレステー
ブル、４：入力レジスタ、５：出力レジスタ、６：入力
バンクレジスタ、７：出力バンクレジスタ、８：出力線
、９：加算器。
Claims (1)
- １、ｋ（ｋ：１より大きな整数）個のデータのうち最大
もしくは最小のデータを抽出するソート手段と、予め昇
順もしくは降順に並べ替えられたｋ個のデータ列を格納
するデータ格納手段を有し、前記に個のデータ列の各々
の先頭データを前記ソート手段に入力し、該ソート手段
からデータを出力する操作と、前記入力操作とを交互に
実行するマージ操作を繰り返すことにより、前記データ
格納手段に格納された複数のデータ列をマージするソー
ト処理装置において、前記ｋ個のデータ列中の最大もし
くは最小のデータのアドレスを保持するアドレステーブ
ルを設けるとともに、前記データ格納手段から前記ソー
ト手段への入力データに、前記に個のデータ列のどのデ
ータであるかを示す識別子を付加し、前記ソート手段が
出力するデータの前記識別子の値により、前記アドレス
テーブルを索引して前記ソート手段に入力するデータの
アドレスを得る手段を設けたことを特徴とするソート処
理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP161488A JPH01177122A (ja) | 1988-01-07 | 1988-01-07 | ソート処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP161488A JPH01177122A (ja) | 1988-01-07 | 1988-01-07 | ソート処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH01177122A true JPH01177122A (ja) | 1989-07-13 |
Family
ID=11506392
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP161488A Pending JPH01177122A (ja) | 1988-01-07 | 1988-01-07 | ソート処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH01177122A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH056261A (ja) * | 1991-04-04 | 1993-01-14 | Mitsubishi Electric Corp | データのためのソーテイング装置およびソーテイング方法 |
| JP2007022661A (ja) * | 2006-11-06 | 2007-02-01 | Dainippon Printing Co Ltd | 易開封性カートン |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6142031A (ja) * | 1984-08-03 | 1986-02-28 | Nippon Telegr & Teleph Corp <Ntt> | ソ−ト処理装置 |
| JPS6172333A (ja) * | 1984-09-15 | 1986-04-14 | Casio Comput Co Ltd | 複数ファイルのマージ方法 |
-
1988
- 1988-01-07 JP JP161488A patent/JPH01177122A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6142031A (ja) * | 1984-08-03 | 1986-02-28 | Nippon Telegr & Teleph Corp <Ntt> | ソ−ト処理装置 |
| JPS6172333A (ja) * | 1984-09-15 | 1986-04-14 | Casio Comput Co Ltd | 複数ファイルのマージ方法 |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH056261A (ja) * | 1991-04-04 | 1993-01-14 | Mitsubishi Electric Corp | データのためのソーテイング装置およびソーテイング方法 |
| JP2007022661A (ja) * | 2006-11-06 | 2007-02-01 | Dainippon Printing Co Ltd | 易開封性カートン |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0731669B2 (ja) | ベクトル・プロセツサ | |
| EP0961966B1 (en) | N-way processing of bit strings in a dataflow architecture | |
| KR920003176B1 (ko) | 정렬처리장치의 제어데이타 생성장치 | |
| JPS6142031A (ja) | ソ−ト処理装置 | |
| JPH01177122A (ja) | ソート処理装置 | |
| JP2003224581A (ja) | 最長一致検索回路および方法およびプログラムおよび記録媒体 | |
| EP0029834A1 (en) | General purpose data buffer | |
| JPS6226723B2 (ja) | ||
| JPS58146935A (ja) | ソ−ト処理装置 | |
| JPS6143338A (ja) | 連想技術を使用して稀薄なデータベースをサーチする方法 | |
| Bhattacharjee et al. | A VLSI architecture for cellular automata based parallel data compression | |
| JPS60134938A (ja) | レジスタフアイル読出し方式 | |
| JPS5542308A (en) | Semiconductor memory unit | |
| JP3264114B2 (ja) | ソート装置 | |
| Parhami | The mixed serial/parallel approach to VLSI search processors | |
| JPS63231526A (ja) | ソ−ト処理装置 | |
| JP2674747B2 (ja) | シグナル・プロセツサ | |
| JP3265993B2 (ja) | ソート処理装置 | |
| Herrmannsfeldt | A Highly Parallel Finite State Automaton Processor for Biological Pattern Matching. | |
| JPH03216729A (ja) | 電子計算機 | |
| Lun et al. | A pipeline design for the realization of the prime factor algorithm using the extended diagonal structure | |
| Lun et al. | 1232 zyxwvutsrqponmlkjihgfedcbaZY | |
| JPS6325725A (ja) | アドレス表分類方式 | |
| JPH0437455B2 (ja) | ||
| JPH05143326A (ja) | バンク処理装置 |