JPH0833812B2 - ソート処理装置 - Google Patents
ソート処理装置Info
- Publication number
- JPH0833812B2 JPH0833812B2 JP63224304A JP22430488A JPH0833812B2 JP H0833812 B2 JPH0833812 B2 JP H0833812B2 JP 63224304 A JP63224304 A JP 63224304A JP 22430488 A JP22430488 A JP 22430488A JP H0833812 B2 JPH0833812 B2 JP H0833812B2
- Authority
- JP
- Japan
- Prior art keywords
- data
- sorted
- sort
- register
- buffer
- 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.)
- Expired - Lifetime
Links
Landscapes
- Executing Machine-Instructions (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明はソート処理装置に関し、特にソート処理をパ
イプライン処理で高速に実行可能なソート処理装置に関
する。
イプライン処理で高速に実行可能なソート処理装置に関
する。
従来、ソート処理はソフトウェアで行なわれ、その処
理には多数の命令の実行が必要であった。ソート処理は
与えられたデータを一定の順序、即ち昇順あるいは降順
に並べ替える処理であり、例えば数字のみから成るデー
タや英文字から成るデータの場合等では、大小順やアル
ファベット順に並べる操作がある。
理には多数の命令の実行が必要であった。ソート処理は
与えられたデータを一定の順序、即ち昇順あるいは降順
に並べ替える処理であり、例えば数字のみから成るデー
タや英文字から成るデータの場合等では、大小順やアル
ファベット順に並べる操作がある。
計算機内ではアルファベットもASCIIコードやEBCDIC
コードのように、大小の順序関係が保たれた数字として
処理されるため、結局、数字の大小関係に帰着した昇順
および降順の並べ替え処理となる。
コードのように、大小の順序関係が保たれた数字として
処理されるため、結局、数字の大小関係に帰着した昇順
および降順の並べ替え処理となる。
ソフトウェアによりソート処理の手法の一つにバブル
ソートによるものがある。バブルソートは、与えられた
データ列に対して先頭のデータから順に次のデータと比
較し、必要に応じて入れ替えを行なう一連の操作を何回
か繰り返すことによってソートを行う。
ソートによるものがある。バブルソートは、与えられた
データ列に対して先頭のデータから順に次のデータと比
較し、必要に応じて入れ替えを行なう一連の操作を何回
か繰り返すことによってソートを行う。
表１は、ソートされるデータ列の一例であり、データ
D0〜データD3の４つのデータ列が示されている。一つの
データの形式は、前半部にソートを行なう比較値をもつ
キー部と後半部に実際のレコードの格納場所を示すポイ
ンタ部とからなっている。データ列はキー部のキー値に
従ってソートされ、ソート結果の順番にポインタ部で示
されたレコードを順番に取出すことによってソート済の
レコードを取出すことができる。
D0〜データD3の４つのデータ列が示されている。一つの
データの形式は、前半部にソートを行なう比較値をもつ
キー部と後半部に実際のレコードの格納場所を示すポイ
ンタ部とからなっている。データ列はキー部のキー値に
従ってソートされ、ソート結果の順番にポインタ部で示
されたレコードを順番に取出すことによってソート済の
レコードを取出すことができる。
一般に用いられるレコード長は数バイトから数百バイ
ト以上にもおよぶことがあり、このようにポインタ部で
格納場所を保持しておくことにより、実際のレコードそ
のものの移動を伴わずにソートを行うことができる。
ト以上にもおよぶことがあり、このようにポインタ部で
格納場所を保持しておくことにより、実際のレコードそ
のものの移動を伴わずにソートを行うことができる。
今、表１のデータ列をキー値に従ってバブルソートに
よって昇順にソートする場合を考える。キーK0〜キーK3
の値は順に4,2,3,1であり、これを昇順に1,2,3,4の順番
に並べ替える。その処理の様子を第６図に従って順に追
って説明する。
よって昇順にソートする場合を考える。キーK0〜キーK3
の値は順に4,2,3,1であり、これを昇順に1,2,3,4の順番
に並べ替える。その処理の様子を第６図に従って順に追
って説明する。
（１）まず、先頭と２番目のキー値、即ちキーK0とキー
K1の内容を読出して比較を行なう。昇順に並んでいる場
合はそのままとし、昇順に並んでいない場合は両者を入
れ替える。
K1の内容を読出して比較を行なう。昇順に並んでいる場
合はそのままとし、昇順に並んでいない場合は両者を入
れ替える。
（２）次に、（１）の並べ替え後のデータ列の２番目と
３番目のキー値、即ちキーK0とキーK2の内容を読出し、
（１）と同様の処理を行なう。
３番目のキー値、即ちキーK0とキーK2の内容を読出し、
（１）と同様の処理を行なう。
（３）同様にキーK0とキーK3に対して（１）と同様の処
理を行なう。以上最終データまでの比較、並べ替え動作
が終了し、最大のキー値を有するキーK0が列の最後尾に
移される。
理を行なう。以上最終データまでの比較、並べ替え動作
が終了し、最大のキー値を有するキーK0が列の最後尾に
移される。
（４）次に、先頭より残った３つのキー、即ちキーK1、
キーK2、キーK3に対して、再び同様の比較、並べ替えの
処理が行なわれる。まず、先頭と２番目のキーK1とキー
K2の処理が行なわれる。この場合、キーK1とキーK2はす
でに昇順に並んでいるので並べ替えは行なわれずそのま
まとなる。
キーK2、キーK3に対して、再び同様の比較、並べ替えの
処理が行なわれる。まず、先頭と２番目のキーK1とキー
K2の処理が行なわれる。この場合、キーK1とキーK2はす
でに昇順に並んでいるので並べ替えは行なわれずそのま
まとなる。
（５）次に、２番目と３番目のキーK2とキーK3について
処理する。以上により、２回目の比較、並べ替え動作が
終了し、２番目に大きいキー値を有するキーK2が比較動
作が行なわれた３キーの内の最後尾に移される。
処理する。以上により、２回目の比較、並べ替え動作が
終了し、２番目に大きいキー値を有するキーK2が比較動
作が行なわれた３キーの内の最後尾に移される。
（６）再び先頭より残った２つのキー、即ちキーK1、キ
ーK3に対して同様の比較、並べ替えの処理が行なわれ
る。
ーK3に対して同様の比較、並べ替えの処理が行なわれ
る。
以上、（１）〜（６）の一連の操作によってキー値に
従った昇順ソートが完了し、この順番にポインタによっ
て示されたレコードを取出すことにより、昇順ソート後
のレコード配列が得られる。
従った昇順ソートが完了し、この順番にポインタによっ
て示されたレコードを取出すことにより、昇順ソート後
のレコード配列が得られる。
上記（１）〜（６）の操作での比較動作の回数は、３
＋２＋１＝６回であり、一般に、ｎ個のデータ配列の比
較動作の回数の最大は、（ｎ−１）＋（ｎ−２）＋…＋
１＝ｎ（ｎ−１）/2回となる。さらに、従来のソフトウ
ェアの処理では、１回の比較動作を、 （１）キーアドレスの生成命令 （２）キーのロード命令 （３）キー同士の比較命令 （４）比較結果による処理ルーチンへの分岐命令 （５）データ交換のためのストア命令 （６）残データ数の更新命令 （７）繰り返しのための分岐命令 のように多数の命令により実行していた。
＋２＋１＝６回であり、一般に、ｎ個のデータ配列の比
較動作の回数の最大は、（ｎ−１）＋（ｎ−２）＋…＋
１＝ｎ（ｎ−１）/2回となる。さらに、従来のソフトウ
ェアの処理では、１回の比較動作を、 （１）キーアドレスの生成命令 （２）キーのロード命令 （３）キー同士の比較命令 （４）比較結果による処理ルーチンへの分岐命令 （５）データ交換のためのストア命令 （６）残データ数の更新命令 （７）繰り返しのための分岐命令 のように多数の命令により実行していた。
上述した従来のソフトウェアによるソート処理は、多
数の命令の実行を必要とし、かつその処理のほとんどが
前の命令の結果に依存して逐次的に実行されるため、処
理時間が非常に長くかかるという欠点がある。
数の命令の実行を必要とし、かつその処理のほとんどが
前の命令の結果に依存して逐次的に実行されるため、処
理時間が非常に長くかかるという欠点がある。
本発明の第１のソート処理装置は、 第１および第２のデータバッファと、 これら第１および第２のデータバッファのうち、いず
れか一方をソートすべきデータの読出し用バッファに、
他方をソートすべきデータの退避用バッファとして選択
する手段と、 最初にソートすべきデータの読出し用として選択され
たデータバッファに外部から与えられるソートすべきデ
ータを入力する手段と、 ソートすべきデータの読出し用バッファの出力を保持
する第１および第２のレジストと、 これら第１および第２のレジスタにソートすべきデー
タを順次格納する手段と、 前記第１および第２のレジスタにソートすべきデータ
が格納される度に、第１および第２のレジスタの予め定
められた部分の内容同士を比較し、比較結果を出力する
比較手段と、 この比較手段が第１のレジスタの値を退避すべき旨を
出力した場合は、第１のレジスタに保持されているデー
タを前記退避用バッファに退避し、第２のレジスタに保
持されているデータはそのまま保持し、新たなデータを
第１のレジスタに格納して次の比較動作を実行させ、一
方前記比較手段が第２のレジスタの値を退避すべき旨を
出力した場合は、同様に第２のレジスタに保持されてい
るデータを前記退避用バッファに退避し、第１のレジス
タに保持されているデータはそのまま保持し、新たなデ
ータを第２のレジスタに格納して次の動作を実行させる
手段と、 予め指定された全データの前記比較手段と前記退避手
段が終了すると、前記退避用バッファに退避されずに前
記第１および第２のレジスタのいずれか一方にそのまま
保持されているデータを予め指定された格納場所に出力
する手段と、 前記退避用バッファとして用いられたデータバッファ
をソートすべきデータの読出し用バッファとし、他方を
ソートすべきデータの退避用バッファとして再選択し、
この再選択された読出し用バッファから順次ソートすべ
きデータを読み出し、上記一連の比較動作と退避用バッ
ファへの退避動作および結果データの出力動作を繰り返
させる手段とを有している。
れか一方をソートすべきデータの読出し用バッファに、
他方をソートすべきデータの退避用バッファとして選択
する手段と、 最初にソートすべきデータの読出し用として選択され
たデータバッファに外部から与えられるソートすべきデ
ータを入力する手段と、 ソートすべきデータの読出し用バッファの出力を保持
する第１および第２のレジストと、 これら第１および第２のレジスタにソートすべきデー
タを順次格納する手段と、 前記第１および第２のレジスタにソートすべきデータ
が格納される度に、第１および第２のレジスタの予め定
められた部分の内容同士を比較し、比較結果を出力する
比較手段と、 この比較手段が第１のレジスタの値を退避すべき旨を
出力した場合は、第１のレジスタに保持されているデー
タを前記退避用バッファに退避し、第２のレジスタに保
持されているデータはそのまま保持し、新たなデータを
第１のレジスタに格納して次の比較動作を実行させ、一
方前記比較手段が第２のレジスタの値を退避すべき旨を
出力した場合は、同様に第２のレジスタに保持されてい
るデータを前記退避用バッファに退避し、第１のレジス
タに保持されているデータはそのまま保持し、新たなデ
ータを第２のレジスタに格納して次の動作を実行させる
手段と、 予め指定された全データの前記比較手段と前記退避手
段が終了すると、前記退避用バッファに退避されずに前
記第１および第２のレジスタのいずれか一方にそのまま
保持されているデータを予め指定された格納場所に出力
する手段と、 前記退避用バッファとして用いられたデータバッファ
をソートすべきデータの読出し用バッファとし、他方を
ソートすべきデータの退避用バッファとして再選択し、
この再選択された読出し用バッファから順次ソートすべ
きデータを読み出し、上記一連の比較動作と退避用バッ
ファへの退避動作および結果データの出力動作を繰り返
させる手段とを有している。
また、本発明の第２のソート処理装置は、 第１および第２のレジスタと、 これら第１および第２のレジスタにソートすべきデー
タが格納される度に、前記第１および第２のレジスタの
予め定められた部分の内容同士を比較し、比較結果を出
力する比較手段と、 この比較手段の比較結果に従って、前記第１および第
２のレジスタのいずれに新たなソートすべきデータを格
納すべきかを指定するレジスタ指定手段と、 このレジスタ指定手段の指定に従って、前記第１およ
び第２のレジスタの一方に新たなソートすべきデータを
格納する手段と、 前記レジスタ指定手段がソートすべき全データに対し
て前記第１および第２のレジスタを交互に指定したかを
検出する検出手段と、 この検出手段の検出出力があった場合は、前記ソート
すべき全データがすでにソート済みデータであることを
検出し、前記ソートすべき全データを予め定められた順
序に従って出力してソート処理を終了させる手段とを有
している。
タが格納される度に、前記第１および第２のレジスタの
予め定められた部分の内容同士を比較し、比較結果を出
力する比較手段と、 この比較手段の比較結果に従って、前記第１および第
２のレジスタのいずれに新たなソートすべきデータを格
納すべきかを指定するレジスタ指定手段と、 このレジスタ指定手段の指定に従って、前記第１およ
び第２のレジスタの一方に新たなソートすべきデータを
格納する手段と、 前記レジスタ指定手段がソートすべき全データに対し
て前記第１および第２のレジスタを交互に指定したかを
検出する検出手段と、 この検出手段の検出出力があった場合は、前記ソート
すべき全データがすでにソート済みデータであることを
検出し、前記ソートすべき全データを予め定められた順
序に従って出力してソート処理を終了させる手段とを有
している。
第１、第２のソート処理装置とも、ソート処理をハー
ドウェアによるパイプライン処理により行なうので、処
理時間が短かくなり、処理が高速化される。
ドウェアによるパイプライン処理により行なうので、処
理時間が短かくなり、処理が高速化される。
なお、第１のソート処理装置では、バブルソートを実
行している途中でソート処理が完了した場合も後続の無
駄な処理を実行してしまうという欠点がある。第２のソ
ート処理装置は、バブルソートの実行中にソート処理が
すでに終了したか否かを検出することにより、無駄なソ
ート処理の実行を削減し、ソート処理の一層の高速化を
図ったものである。
行している途中でソート処理が完了した場合も後続の無
駄な処理を実行してしまうという欠点がある。第２のソ
ート処理装置は、バブルソートの実行中にソート処理が
すでに終了したか否かを検出することにより、無駄なソ
ート処理の実行を削減し、ソート処理の一層の高速化を
図ったものである。
次に、本発明の実施例について図面を参照して説明す
る。
る。
第５図は本発明のソート処理装置を含む、システム構
成の一実施例を示すブロック図である。
成の一実施例を示すブロック図である。
主記憶装置１は命令語およびオペランドを格納する記
憶装置、バッファ記憶制御装置２は要求元の指示に従っ
て、主記憶装置１より命令語およびオペランドを読出し
て要求元へ送出したり、主記憶装置１の所定の場所へ演
算結果を格納する記憶制御装置、演算制御装置３は命令
制御装置４の指示に従って所定の演算を行なう演算制御
装置、命令制御装置４は主記憶装置１から命令語を読出
して解読し、演算制御装置３またはソート処理装置５に
演算の実行を指示する命令制御装置、ソート処理装置５
は本発明のソート処理装置である。
憶装置、バッファ記憶制御装置２は要求元の指示に従っ
て、主記憶装置１より命令語およびオペランドを読出し
て要求元へ送出したり、主記憶装置１の所定の場所へ演
算結果を格納する記憶制御装置、演算制御装置３は命令
制御装置４の指示に従って所定の演算を行なう演算制御
装置、命令制御装置４は主記憶装置１から命令語を読出
して解読し、演算制御装置３またはソート処理装置５に
演算の実行を指示する命令制御装置、ソート処理装置５
は本発明のソート処理装置である。
本実施例のシステム構成は、主記憶装置１、バッファ
記憶制御装置２、演算制御装置３、命令制御装置４から
成る公知のシステム構成に本発明のソート処理装置５が
付加される構成となっている。なお、ソート処理装置５
は演算制御装置３内に内蔵される構成であってもよい。
記憶制御装置２、演算制御装置３、命令制御装置４から
成る公知のシステム構成に本発明のソート処理装置５が
付加される構成となっている。なお、ソート処理装置５
は演算制御装置３内に内蔵される構成であってもよい。
バッファ記憶制御装置２によって主記憶装置１から読
出された命令語が命令制御装置４で解読され、ソート命
令である場合には、ソート処理装置５に通知される。
出された命令語が命令制御装置４で解読され、ソート命
令である場合には、ソート処理装置５に通知される。
ソート命令は、ソートすべきデータの格納場所とソー
ト済データの格納場所を示す情報を有しており、さらに
ソートすべきデータの個数および昇順にソートすべきか
降順にソートすべきかを指示するフィールドを有してい
る。ソートすべきデータの格納場所とソート済データの
格納場所はいずれも主記憶装置１内のメモリ上にとられ
る。本実施例のソートデータは表１のようにキー部とポ
インタ部よりなり、キー部４バイト、ポインタ部４バイ
トの８バイト固定長データで、メモリ上に連続に配置さ
れる。ソート処理の実行にあたっては、ソートすべきデ
ータの読出しおよびソート済データの格納のリクエスト
の制御は、命令制御装置４が司ってもよいし、ソート処
理装置５自身が司ってもよい。本実施例では命令制御装
置４が制御を司どり、メモリ上に連続に配置されている
ソートすべきデータを順次読出してソート処理装置５に
送出する。命令制御装置４はまた、ソートすべきデータ
の個数と、昇順にソートすべきか、降順にソートすべき
かの指示をソート処理装置５に通知する。
ト済データの格納場所を示す情報を有しており、さらに
ソートすべきデータの個数および昇順にソートすべきか
降順にソートすべきかを指示するフィールドを有してい
る。ソートすべきデータの格納場所とソート済データの
格納場所はいずれも主記憶装置１内のメモリ上にとられ
る。本実施例のソートデータは表１のようにキー部とポ
インタ部よりなり、キー部４バイト、ポインタ部４バイ
トの８バイト固定長データで、メモリ上に連続に配置さ
れる。ソート処理の実行にあたっては、ソートすべきデ
ータの読出しおよびソート済データの格納のリクエスト
の制御は、命令制御装置４が司ってもよいし、ソート処
理装置５自身が司ってもよい。本実施例では命令制御装
置４が制御を司どり、メモリ上に連続に配置されている
ソートすべきデータを順次読出してソート処理装置５に
送出する。命令制御装置４はまた、ソートすべきデータ
の個数と、昇順にソートすべきか、降順にソートすべき
かの指示をソート処理装置５に通知する。
第１図は本発明のソート処理装置５の第１の実施例の
ブロック構成図である。
ブロック構成図である。
SL10は命令制御装置４から送られてくるソートすべき
データの個数もしくはカウンタ50の出力を保持するレジ
スタ、カウンタ50はSL10の内容を−１する減算器、セレ
クタ30は命令制御装置４から送られてくるソートすべき
データの個数およびカウンタ50の出力の一方を選択して
出力する選択器、SDB20およびSDB21はソートすべきデー
タを保持するバッファ、WAR11およびWAR13はSDB20およ
びSDB21の書込みアドレスを保持するライトアドレスレ
ジスタ、RAR12およびRAR14はSDB20およびSDB21の読出し
アドレスを保持するリードアドレスレジスタ、カウンタ
51〜54はWAR11、RAR12、WAR13、RAR14の内容をそれぞれ
＋１する加算器、セレクタ31〜34はリセット値０とカウ
ンタ51〜54の出力をそれぞれ選択する選択器、SDR16お
よびSDR17はSDB20またはSDB21から読出されたソートす
べきデータを保持するレジスタ、セレクタ36および37は
SDB20またはSDB21から読出されたソートすべきデータを
選択する選択器、SDR18はSDR16またはSDR17から出力さ
れた結果データを受け取り、結果データを主記憶装置１
に格納するために、バッファ記憶制御装置２に結果デー
タを送出するインタフェースレジスタ、セレクタ38はSD
R16およびSDR17の出力データを選択する選択器、セレク
タ40は主記憶装置１から読出されてソート処理装置５に
送出されてくるソートすべきデータまたはSDR16およびS
DR17からの出力データのいずれかを選択する選択器、セ
レクタ41はSDR16およびSDR17からの出力データを選択す
る選択器、FGR15はSDB20およびSDB21のいずれか一方を
ソートすべきデータの読出し用バッファとして指定し、
他方をソートすべきデータの退避用バッファとして指定
するフラグレジスタ、セレクタ35は初期値０とFGR15の
内容が反転を受けた値とを選択する選択器、比較器23
は、SDR16およびSDR17に保持されるソートすべきデータ
の予め定められた部分、即ち本実施例ではソートすべき
データのキー部の内容同士を比較し、比較結果を出力す
る比較器、比較器22はSL10の内容と、RAR12またはRAR14
のいずれかの内容とを比較し、一致を検出して出力する
比較器、セレクタ39はRAR12およびRAR14の内容を選択す
る選択器、制御回路24はソート処理装置５全体の制御を
司る制御回路である。
データの個数もしくはカウンタ50の出力を保持するレジ
スタ、カウンタ50はSL10の内容を−１する減算器、セレ
クタ30は命令制御装置４から送られてくるソートすべき
データの個数およびカウンタ50の出力の一方を選択して
出力する選択器、SDB20およびSDB21はソートすべきデー
タを保持するバッファ、WAR11およびWAR13はSDB20およ
びSDB21の書込みアドレスを保持するライトアドレスレ
ジスタ、RAR12およびRAR14はSDB20およびSDB21の読出し
アドレスを保持するリードアドレスレジスタ、カウンタ
51〜54はWAR11、RAR12、WAR13、RAR14の内容をそれぞれ
＋１する加算器、セレクタ31〜34はリセット値０とカウ
ンタ51〜54の出力をそれぞれ選択する選択器、SDR16お
よびSDR17はSDB20またはSDB21から読出されたソートす
べきデータを保持するレジスタ、セレクタ36および37は
SDB20またはSDB21から読出されたソートすべきデータを
選択する選択器、SDR18はSDR16またはSDR17から出力さ
れた結果データを受け取り、結果データを主記憶装置１
に格納するために、バッファ記憶制御装置２に結果デー
タを送出するインタフェースレジスタ、セレクタ38はSD
R16およびSDR17の出力データを選択する選択器、セレク
タ40は主記憶装置１から読出されてソート処理装置５に
送出されてくるソートすべきデータまたはSDR16およびS
DR17からの出力データのいずれかを選択する選択器、セ
レクタ41はSDR16およびSDR17からの出力データを選択す
る選択器、FGR15はSDB20およびSDB21のいずれか一方を
ソートすべきデータの読出し用バッファとして指定し、
他方をソートすべきデータの退避用バッファとして指定
するフラグレジスタ、セレクタ35は初期値０とFGR15の
内容が反転を受けた値とを選択する選択器、比較器23
は、SDR16およびSDR17に保持されるソートすべきデータ
の予め定められた部分、即ち本実施例ではソートすべき
データのキー部の内容同士を比較し、比較結果を出力す
る比較器、比較器22はSL10の内容と、RAR12またはRAR14
のいずれかの内容とを比較し、一致を検出して出力する
比較器、セレクタ39はRAR12およびRAR14の内容を選択す
る選択器、制御回路24はソート処理装置５全体の制御を
司る制御回路である。
次に、本実施例のソート処理装置５によって、表１の
データ列がソートされる動作について説明する。
データ列がソートされる動作について説明する。
今、表１のデータ列、即ちデータD0〜データD3までの
４データがメモリ上に連続に配置されており、このデー
タ列を昇順にソートする場合を考える。表１のデータD0
〜データD3は、バッファ記憶制御装置２によって主記憶
装置１から順次読出され、ソート処理装置５へ送出され
る。また、ソート命令によって示されるソートすべきデ
ータの個数「４」が命令制御装置４によって解読されソ
ート処理装置５へ送出される。
４データがメモリ上に連続に配置されており、このデー
タ列を昇順にソートする場合を考える。表１のデータD0
〜データD3は、バッファ記憶制御装置２によって主記憶
装置１から順次読出され、ソート処理装置５へ送出され
る。また、ソート命令によって示されるソートすべきデ
ータの個数「４」が命令制御装置４によって解読されソ
ート処理装置５へ送出される。
第２図は表１のデータ列、データD0〜データD3がソー
ト処理装置５によってソートされる動作を示すタイミン
グ図である。
ト処理装置５によってソートされる動作を示すタイミン
グ図である。
サイクルT0ではSL10、WAR11、RAR12、WAR13、RAR14は
初期値０にリセットされた状態を保っている。また、命
令制御装置４からソートレングス、即ちソートすべきデ
ータの個数「４」がソート処理装置５に送られてきて、
サイクルT1でSL10にセットされる。FGR15には、同時に
初期値「０」がセットされる。FGR15が値「０」を保持
している場合は、SDB20をソートすべきデータの読出し
用バッファとし、SDB21のソートすべきデータの退避用
バッファとして使用することを指示する。一方、FGR15
が値「１」にセットされると、SDB20がソートすべきデ
ータの退避用バッファとし、SDB21がソートすべきデー
タの読出し用バッファとして使用することが指示され
る。
初期値０にリセットされた状態を保っている。また、命
令制御装置４からソートレングス、即ちソートすべきデ
ータの個数「４」がソート処理装置５に送られてきて、
サイクルT1でSL10にセットされる。FGR15には、同時に
初期値「０」がセットされる。FGR15が値「０」を保持
している場合は、SDB20をソートすべきデータの読出し
用バッファとし、SDB21のソートすべきデータの退避用
バッファとして使用することを指示する。一方、FGR15
が値「１」にセットされると、SDB20がソートすべきデ
ータの退避用バッファとし、SDB21がソートすべきデー
タの読出し用バッファとして使用することが指示され
る。
また、サイクルT1〜T4では、主記憶装置１から読出さ
れたソートすべきデータD0〜D3が順次ソート処理装置５
へ転送され、SDB20のライトアドレスレジスタWAR11が順
次カウントアップして、サイクルT2〜T5にかけて、SDB2
0に取り込まれる。ソートデータD0〜D3がSDB20に取り込
まれると、順次SDR16、SDR17にデータが読出されて、比
較器23でデータのキー部の比較が行なわれる。まず、サ
イクルT3でSDB20のワード０より読出されたソートデー
タD0がSDR16にセットされ、サイクルT4でSDB20のワード
１より読出されたソートデータD1がSDR17にセットされ
る。SDR16とSDR17にデータがそろうと比較器23でキー部
の比較が行なわれ、比較結果が制御回路24に通知され
る。比較器23はSDR16とSDR17の大小を検出する機能と一
致を検出する機能から構成されており、SDR16＜SDR17の
時論理「１」を、SDR16＞SDR17の時論理「０」を出力
し、SDR16＝SDR17が検出された時には上記信号とは別に
一致信号が制御回路24に通知される。
れたソートすべきデータD0〜D3が順次ソート処理装置５
へ転送され、SDB20のライトアドレスレジスタWAR11が順
次カウントアップして、サイクルT2〜T5にかけて、SDB2
0に取り込まれる。ソートデータD0〜D3がSDB20に取り込
まれると、順次SDR16、SDR17にデータが読出されて、比
較器23でデータのキー部の比較が行なわれる。まず、サ
イクルT3でSDB20のワード０より読出されたソートデー
タD0がSDR16にセットされ、サイクルT4でSDB20のワード
１より読出されたソートデータD1がSDR17にセットされ
る。SDR16とSDR17にデータがそろうと比較器23でキー部
の比較が行なわれ、比較結果が制御回路24に通知され
る。比較器23はSDR16とSDR17の大小を検出する機能と一
致を検出する機能から構成されており、SDR16＜SDR17の
時論理「１」を、SDR16＞SDR17の時論理「０」を出力
し、SDR16＝SDR17が検出された時には上記信号とは別に
一致信号が制御回路24に通知される。
サイクルT4でSDR16内のソートデータD0とSDR17内のソ
ートデータD1のキー部が比較され、比較器23は論理
「０」を出力し、制御回路24に通知する。
ートデータD1のキー部が比較され、比較器23は論理
「０」を出力し、制御回路24に通知する。
本実施例では、バブルソートによる昇順ソートを行な
っているので、より大きいキー値を有するソートデータ
は次のソートデータとの比較のために用いられ、小なる
キー値を有するソートデータは退避用バッファに退避さ
れる。この退避用バッファへの退避動作によって、バブ
ルソートにおけるソートデータの入れ替え処理が実行さ
れる。
っているので、より大きいキー値を有するソートデータ
は次のソートデータとの比較のために用いられ、小なる
キー値を有するソートデータは退避用バッファに退避さ
れる。この退避用バッファへの退避動作によって、バブ
ルソートにおけるソートデータの入れ替え処理が実行さ
れる。
比較器23からの論理「０」の出力結果を受けた制御回
路24の制御によってサイクルT5ではSDR17内のソートデ
ータD1がソートすべきデータの退避用バッファとして指
定されているSDB21のワード０に退避され、同時にSDB20
のワード２から次の比較動作のために読出されたソート
データD2がSDR17にセットされる。比較器23で比較動作
が再び行なわれ、小なるキー値を有するソートデータD2
がサイクルT6でSDB21のワード１に退避される。サイク
ルT6ではSDB20のワード３から読出された最後尾のソー
トデータD3がSDR17にセットされる。サイクルT6での比
較器23の比較動作により、小なるキー値を有するソート
データD3がサイクルT7でSDB21のワード２に退避され
る。
路24の制御によってサイクルT5ではSDR17内のソートデ
ータD1がソートすべきデータの退避用バッファとして指
定されているSDB21のワード０に退避され、同時にSDB20
のワード２から次の比較動作のために読出されたソート
データD2がSDR17にセットされる。比較器23で比較動作
が再び行なわれ、小なるキー値を有するソートデータD2
がサイクルT6でSDB21のワード１に退避される。サイク
ルT6ではSDB20のワード３から読出された最後尾のソー
トデータD3がSDR17にセットされる。サイクルT6での比
較器23の比較動作により、小なるキー値を有するソート
データD3がサイクルT7でSDB21のワード２に退避され
る。
SDB20、SDB21のライトアドレスレジスタWAR11、WAR13
およびリードアドレスレジスタRAR12、RAR14は、それぞ
れ書込みおよび読出し動作を実行する度毎に、次のアド
レスを示すように＋１カウントアップが行なわれる。し
たがって、サイクルT5でSDB20のワード３より最後尾の
ソートデータD3が読出され、サイクルT6でSDR17にセッ
トされると同時にRAR12はSDB20のワード４を示すように
カウントアップされる。セレクタ39は、ソートすべきデ
ータの読出し用バッファとして用いられている側のリー
ドアドレスレジスタの内容を選択して比較器22に出力し
ており、比較器22でSL10の内容と比較される。サイクル
T6ではRAR12の内容は「４」でありSL10の内容「４」と
一致する。比較器22は一致信号を出力し、制御回路24に
通知する。この一致信号は、ソートすべきデータの読出
し用バッファ内のソートデータの比較動作が全て終了し
たことを示す。この比較動作終了信号を受けた制御回路
24の制御によってサイクルT7では以下の動作が行なわれ
る。
およびリードアドレスレジスタRAR12、RAR14は、それぞ
れ書込みおよび読出し動作を実行する度毎に、次のアド
レスを示すように＋１カウントアップが行なわれる。し
たがって、サイクルT5でSDB20のワード３より最後尾の
ソートデータD3が読出され、サイクルT6でSDR17にセッ
トされると同時にRAR12はSDB20のワード４を示すように
カウントアップされる。セレクタ39は、ソートすべきデ
ータの読出し用バッファとして用いられている側のリー
ドアドレスレジスタの内容を選択して比較器22に出力し
ており、比較器22でSL10の内容と比較される。サイクル
T6ではRAR12の内容は「４」でありSL10の内容「４」と
一致する。比較器22は一致信号を出力し、制御回路24に
通知する。この一致信号は、ソートすべきデータの読出
し用バッファ内のソートデータの比較動作が全て終了し
たことを示す。この比較動作終了信号を受けた制御回路
24の制御によってサイクルT7では以下の動作が行なわれ
る。
まず、比較器23の比較動作の結果により、小なるキー
値を有するSDR17内のソートデータD3が退避用バッファS
DB21のワード３に退避され、SDR16内に残った最大のキ
ー値を有するソートデータD0がSDR18にセットされて、
メモリの所定の場所へ格納するためにバッファ記憶制御
装置２に送出される。
値を有するSDR17内のソートデータD3が退避用バッファS
DB21のワード３に退避され、SDR16内に残った最大のキ
ー値を有するソートデータD0がSDR18にセットされて、
メモリの所定の場所へ格納するためにバッファ記憶制御
装置２に送出される。
SL10は、減算器50で−１された値「３」に更新され
る。この値は、ソート処理装置５内に保持されているソ
ートすべきデータの残数を示している。
る。この値は、ソート処理装置５内に保持されているソ
ートすべきデータの残数を示している。
WAR11、RAR12、WAR13、RAR14の各アドレスレジスタの
値は初期値「０」にリセットされる。
値は初期値「０」にリセットされる。
また、FGR15は、自身の内容が反転された値、即ち値
「１」に更新される。これはサイクルT7以降、SDB20が
ソートすべきデータの退避用バッファに、SDB21がソー
トすべきデータの読出し用バッファとして使用されるこ
とを示しており、この指示に従って上述した一連の処理
動作が繰り返される。
「１」に更新される。これはサイクルT7以降、SDB20が
ソートすべきデータの退避用バッファに、SDB21がソー
トすべきデータの読出し用バッファとして使用されるこ
とを示しており、この指示に従って上述した一連の処理
動作が繰り返される。
即ち、サイクルT8〜T10まではSDB21のワード０〜ワー
ド２に保持されているソートデータがSDR16もしくはSDR
17に順次読出されて、比較器23で比較動作が行なわれて
小なるキー値を有するソートデータがFGR15の指示によ
りSDB20のワード０より順に退避させられる。
ド２に保持されているソートデータがSDR16もしくはSDR
17に順次読出されて、比較器23で比較動作が行なわれて
小なるキー値を有するソートデータがFGR15の指示によ
りSDB20のワード０より順に退避させられる。
サイクルT10ではRAR14の値とSL10の値の一致が検出さ
れて、比較動作の終了が制御回路24に通知される。そし
てサイクルT11で、SDR16に保持されている小なるキー値
を有するソートデータD3がSDB20のワード１に退避さ
れ、同時に残ソートデータの中で最大のキー値を有する
ソートデータD2がSDR17からSDR18にセットされてバッフ
ァ記憶制御装置２に送出される。また、サイクルT11で
はSL10の値が「３」→「２」に、FGR15の値が「１」→
「０」に更新され、WAR11、RAR12、WAR13、RAR14の各ア
ドレスレジスタの値が初期値「０」にリセットされて新
たな比較動作と退避動作が実行される。
れて、比較動作の終了が制御回路24に通知される。そし
てサイクルT11で、SDR16に保持されている小なるキー値
を有するソートデータD3がSDB20のワード１に退避さ
れ、同時に残ソートデータの中で最大のキー値を有する
ソートデータD2がSDR17からSDR18にセットされてバッフ
ァ記憶制御装置２に送出される。また、サイクルT11で
はSL10の値が「３」→「２」に、FGR15の値が「１」→
「０」に更新され、WAR11、RAR12、WAR13、RAR14の各ア
ドレスレジスタの値が初期値「０」にリセットされて新
たな比較動作と退避動作が実行される。
サイクルT13では、残った２つのソートデータD1とD3
の比較動作が実行され、サイクルT14で、小なるキー値
を有するソートデータD3がSDB21のワード０に退避さ
れ、大なるキー値を有するソートデータD1がSDR18にセ
ットされてバッファ記憶制御装置２に送出される。
の比較動作が実行され、サイクルT14で、小なるキー値
を有するソートデータD3がSDB21のワード０に退避さ
れ、大なるキー値を有するソートデータD1がSDR18にセ
ットされてバッファ記憶制御装置２に送出される。
サイクルT15でSDB21のワード０から読出された最後の
ソートデータD3がSDR16にセットされる。この時、SDB21
のリードアドレスレジスタRARは値「１」にカウントア
ップされており、セレクタ39で選択されて比較器22でSL
10の値「１」と比較され一致信号が制御回路24に通知さ
れる。SDR17には有効なデータがセットされていないこ
とにより、制御回路24はサイクルT16でSDR16に保持され
ている最後のソートデータD3をSDR18にセットしバッフ
ァ記憶制御装置２に送出する。また、サイクルT16ではS
L10の残ソートデータを示す値「０」となり、全ソート
処理動作が終了したことが比較器22を通して制御回路24
に通知され、一連のソート処理動作が終了する。
ソートデータD3がSDR16にセットされる。この時、SDB21
のリードアドレスレジスタRARは値「１」にカウントア
ップされており、セレクタ39で選択されて比較器22でSL
10の値「１」と比較され一致信号が制御回路24に通知さ
れる。SDR17には有効なデータがセットされていないこ
とにより、制御回路24はサイクルT16でSDR16に保持され
ている最後のソートデータD3をSDR18にセットしバッフ
ァ記憶制御装置２に送出する。また、サイクルT16ではS
L10の残ソートデータを示す値「０」となり、全ソート
処理動作が終了したことが比較器22を通して制御回路24
に通知され、一連のソート処理動作が終了する。
昇順ソートの結果はソートデータがストアされたメモ
リの所定の場所より、ストア順の逆にソートデータのポ
インタ部を取り出すことにより得られる。
リの所定の場所より、ストア順の逆にソートデータのポ
インタ部を取り出すことにより得られる。
降順ソートの場合も、昇順ソートの場合と同様に行な
うことができる。
うことができる。
次に、表２のデータ列を本ソート処理装置がキー値に
従ってバブルソートにより昇順にソートする場合の処理
手順について、第７図に従って簡単に説明する。
従ってバブルソートにより昇順にソートする場合の処理
手順について、第７図に従って簡単に説明する。
キーK0〜キーK3の値は順に4,1,2,3であり、これを昇順
に1,2,3,4の順番に並べ替える。
に1,2,3,4の順番に並べ替える。
（１）まず、先頭と２番目のキー値、即ちキーK0とキー
K1の内容を読出して比較を行なう。昇順に並んでいる場
合はそのままとし、昇順に並んでいない場合は両者を入
れ替える。
K1の内容を読出して比較を行なう。昇順に並んでいる場
合はそのままとし、昇順に並んでいない場合は両者を入
れ替える。
（２）次に、（１）の並べ替え後のデータ列の２番目と
３番目のキー値、即ちキーK0とキーK2の内容を読出し、
（１）と同様の処理を行なう。
３番目のキー値、即ちキーK0とキーK2の内容を読出し、
（１）と同様の処理を行なう。
（３）同様にキーK0とキーK3に対して（１）と同様の処
理を行なう。以上最終データまでの比較、並べ替え動作
が終了し、最大のキー値を有するキーK0が列の最後尾に
移される。
理を行なう。以上最終データまでの比較、並べ替え動作
が終了し、最大のキー値を有するキーK0が列の最後尾に
移される。
（４）次に、再び先頭より残った３つのキー、即ちキー
K1、キーK2、キーK3に対して、同様の比較、並べ替えの
処理が行なわれる。まず、先頭と２番目のキーK1とキー
K2の処理が行なわれる。この場合、キーK1とキーK2はす
でに昇順に並んでいるので並べ替えは行なわれずそのま
まとなる。
K1、キーK2、キーK3に対して、同様の比較、並べ替えの
処理が行なわれる。まず、先頭と２番目のキーK1とキー
K2の処理が行なわれる。この場合、キーK1とキーK2はす
でに昇順に並んでいるので並べ替えは行なわれずそのま
まとなる。
（５）次に、２番目と３番目のキーK2とキーK3について
処理する。以上により、２回目の比較、並べ替え動作が
終了し、２番目に大きいキー値を有するキーK3が比較動
作が行なわれた３キーの内の最後尾に移される。
処理する。以上により、２回目の比較、並べ替え動作が
終了し、２番目に大きいキー値を有するキーK3が比較動
作が行なわれた３キーの内の最後尾に移される。
（６）再び先頭より残った２つのキー、即ちキーK1、キ
ーK2に対して同様の比較、並べ替えの処理が行なわれ
る。
ーK2に対して同様の比較、並べ替えの処理が行なわれ
る。
以上、（１）〜（６）の一連の操作によってキー値に
従った昇順ソートが完了し、この順番にポインタによっ
て示されたレコードを取出すことにより、昇順ソート後
のレコード配列が得られる。
従った昇順ソートが完了し、この順番にポインタによっ
て示されたレコードを取出すことにより、昇順ソート後
のレコード配列が得られる。
上記（１）〜（６）の操作での比較動作の回数は、３
＋２＋１＝６回である。
＋２＋１＝６回である。
このように、上述した第１図のソート処理装置は、バ
ブルソートのアルゴリズムをそのままハードウェア化し
ているために、例えば表２のデータ列を昇順にソートす
る場合のように、実際は第７図の処理手順の（１）〜
（３）までの処理でソート処理が完了するような場合で
も、後続の（４）〜（６）の処理を自動的に実行してし
まう、つまり、バブルソートを実行している途中でソー
ト処理が完了した場合も後続の無駄な処理を実行してし
まい、高速化の妨げとなる欠点がある。
ブルソートのアルゴリズムをそのままハードウェア化し
ているために、例えば表２のデータ列を昇順にソートす
る場合のように、実際は第７図の処理手順の（１）〜
（３）までの処理でソート処理が完了するような場合で
も、後続の（４）〜（６）の処理を自動的に実行してし
まう、つまり、バブルソートを実行している途中でソー
ト処理が完了した場合も後続の無駄な処理を実行してし
まい、高速化の妨げとなる欠点がある。
次に、第１の実施例の欠点を解消する本発明の第２の
実施例について図面を参照して説明する。
実施例について図面を参照して説明する。
第５図は本発明のソート処理装置を含むシステム構成
の一実施例を示すブロック図である。
の一実施例を示すブロック図である。
主記憶装置１は命令語およびオペランドを格納する記
憶装置、バッファ記憶制御装置２は要求元の指示に従っ
て、主記憶装置１より命令語およびオペランドを読出し
て要求元へ送出したり、主記憶装置１の所定の場所へ演
算結果を格納する記憶制御装置、演算制御装置３は命令
制御装置４の指示に従って所定の演算を行なう演算制御
装置、命令制御装置４は主記憶装置１から命令語を読出
して解読し、演算制御装置３またはソート処理装置５に
演算の実行を指示する命令制御装置、ソート処理装置５
は本発明のソート処理装置である。
憶装置、バッファ記憶制御装置２は要求元の指示に従っ
て、主記憶装置１より命令語およびオペランドを読出し
て要求元へ送出したり、主記憶装置１の所定の場所へ演
算結果を格納する記憶制御装置、演算制御装置３は命令
制御装置４の指示に従って所定の演算を行なう演算制御
装置、命令制御装置４は主記憶装置１から命令語を読出
して解読し、演算制御装置３またはソート処理装置５に
演算の実行を指示する命令制御装置、ソート処理装置５
は本発明のソート処理装置である。
本実施例のシステム構成は、主記憶装置１、バッファ
記憶制御装置２、演算制御装置３、命令制御装置４から
なる公知のシステム構成に本発明のソート処理装置５が
付加される構成となっている。また、ソート処理装置５
は演算制御装置３内に内蔵される構成であってもよい。
記憶制御装置２、演算制御装置３、命令制御装置４から
なる公知のシステム構成に本発明のソート処理装置５が
付加される構成となっている。また、ソート処理装置５
は演算制御装置３内に内蔵される構成であってもよい。
バッファ記憶制御装置２によって主記憶装置１から読
出された命令語が命令制御装置４で解読され、ソート命
令である場合には、ソート処理装置５に通知される。
出された命令語が命令制御装置４で解読され、ソート命
令である場合には、ソート処理装置５に通知される。
ソート命令は、ソートすべきデータの格納場所とソー
ト済データの格納場所を示す情報を有しており、さらに
ソートすべきデータの個数および昇順にソートすべきか
降順にソートすべきかを指示するフィールドを有してい
る。ソートすべきデータの格納場所とソート済データの
格納場所はいずれも主記憶装置１内のメモリ上にとられ
る。本実施例におけるソートデータは表２のようにキー
部とポインタ部よりなり、キー部４バイト、ポインタ部
４バイトの８バイト固定長データでメモリ上に連続に配
置される。ソート処理の実行にあたっては、ソートすべ
きデータの読出しおよびソート済データの格納のリクエ
ストの制御は、命令制御装置４が司ってもよいし、ソー
ト処理装置５自身が司ってもよい。本実施例では命令制
御装置４が制御を司どり、メモリ上に連続に配置されて
いるソートすべきデータを順次読出してソート処理装置
５に送出する。命令制御装置４はまた、ソートすべきデ
ータの個数と、昇順にソートすべきか、降順にソートす
べきかの指示をソート処理装置５に通知する。
ト済データの格納場所を示す情報を有しており、さらに
ソートすべきデータの個数および昇順にソートすべきか
降順にソートすべきかを指示するフィールドを有してい
る。ソートすべきデータの格納場所とソート済データの
格納場所はいずれも主記憶装置１内のメモリ上にとられ
る。本実施例におけるソートデータは表２のようにキー
部とポインタ部よりなり、キー部４バイト、ポインタ部
４バイトの８バイト固定長データでメモリ上に連続に配
置される。ソート処理の実行にあたっては、ソートすべ
きデータの読出しおよびソート済データの格納のリクエ
ストの制御は、命令制御装置４が司ってもよいし、ソー
ト処理装置５自身が司ってもよい。本実施例では命令制
御装置４が制御を司どり、メモリ上に連続に配置されて
いるソートすべきデータを順次読出してソート処理装置
５に送出する。命令制御装置４はまた、ソートすべきデ
ータの個数と、昇順にソートすべきか、降順にソートす
べきかの指示をソート処理装置５に通知する。
第３図は本発明のソート処理装置５の第２の実施例の
ブロック構成図である。
ブロック構成図である。
SL10は命令制御装置４から送られてくるソートすべき
データの個数を保持し、ソート処理装置５内に保持され
ているソートすべきデータの個数を示すレジスタ、カウ
ンタ50はSL10の内容を−１する減算器、セレクタ30は命
令制御装置４から送られてくるソートすべきデータの個
数またはカウンタ50の出力および初期値「０」のいずれ
かを選択して出力する選択器、SDB20およびSDB21はソー
トすべきデータを保持するバッファ、WAR11およびWAR13
は、SDB20およびSDB21の書込みアドレスを保持するライ
トアドレスレジスタ、RAR12およびRAR14は、SDB20およ
びSDB21の読出しアドレスを保持するリードアドレスレ
ジスタ、カウンタ51〜54はWAR11、RAR12、WAR13、RAR14
の内容をそれぞれ＋１する加算器、カウンタ55,56はRAR
12、RAR14の内容をそれぞれ−１する減算器、セレクタ3
1,33はリセット値０とカウンタ51,53の出力をそれぞれ
選択する選択器、セレクタ32,33はリセット値０とカウ
ンタ52と55、54と56、およびWAR11、WAR13の内容をそれ
ぞれ選択する選択器、SDR16およびSDR17は、SDB20また
はSDB21から読出されたソートすべきデータを保持する
レジスタ、セレクタ36および37は、SDB20またはSDB21か
ら読出されたソートすべきデータを選択する選択器、SD
R18はSDR16もしくはSDR17から出力された結果データを
受け取り、結果データを主記憶装置１に格納するため
に、バッファ記憶制御装置２に結果データを送出するイ
ンタフェースレジスタ、セレクタ38はSDR16およびSDR17
の出力データを選択する選択器、セレクタ40は主記憶装
置１から読出されてソート処理装置５に送出されてくる
ソートすべきデータまたは、SDR16およびSDR17からの出
力データのいずれかを選択する選択器、セレクタ41はSD
R16およびSDR17からの出力データを選択する選択器、FG
R15は、SDB20およびSDB21のいずれか一方をソートすべ
きデータの読出し用バッファとして指定し、他方をソー
トすべきデータの退避用バッファとして指定するフラグ
レジスタ、セレクタ35は初期値０のFGR15の内容が反転
を受けた値とを選択する選択器、比較器23は、SDR16お
よびSDR17に保持されるソートすべきデータの予め定め
られた部分、即ち本実施例ではソートすべきデータのキ
ー部の内容同士を比較し、比較結果を出力する比較器、
比較器22はSL10の内容と、RAR12またはRAR14のいずれか
の内容とを比較し、一致を検出して出力する比較器、セ
レクタ39は、RAR12とRAR14の内容を選択する選択器、ケ
ート回路25は比較器23の内容を反転させる反転器、レジ
スタ19は初期値「０」または「１」または比較器23の出
力を保持するレジスタ、セレクタ42は初期値「０」また
は「１」と比較器23の出力を選択する選択器、比較器26
はゲート回路25の出力とレジスタ19の出力を比較し、一
致を検出する比較器、制御回路24はソート処理装置５全
体の制御を司る制御回路である。
データの個数を保持し、ソート処理装置５内に保持され
ているソートすべきデータの個数を示すレジスタ、カウ
ンタ50はSL10の内容を−１する減算器、セレクタ30は命
令制御装置４から送られてくるソートすべきデータの個
数またはカウンタ50の出力および初期値「０」のいずれ
かを選択して出力する選択器、SDB20およびSDB21はソー
トすべきデータを保持するバッファ、WAR11およびWAR13
は、SDB20およびSDB21の書込みアドレスを保持するライ
トアドレスレジスタ、RAR12およびRAR14は、SDB20およ
びSDB21の読出しアドレスを保持するリードアドレスレ
ジスタ、カウンタ51〜54はWAR11、RAR12、WAR13、RAR14
の内容をそれぞれ＋１する加算器、カウンタ55,56はRAR
12、RAR14の内容をそれぞれ−１する減算器、セレクタ3
1,33はリセット値０とカウンタ51,53の出力をそれぞれ
選択する選択器、セレクタ32,33はリセット値０とカウ
ンタ52と55、54と56、およびWAR11、WAR13の内容をそれ
ぞれ選択する選択器、SDR16およびSDR17は、SDB20また
はSDB21から読出されたソートすべきデータを保持する
レジスタ、セレクタ36および37は、SDB20またはSDB21か
ら読出されたソートすべきデータを選択する選択器、SD
R18はSDR16もしくはSDR17から出力された結果データを
受け取り、結果データを主記憶装置１に格納するため
に、バッファ記憶制御装置２に結果データを送出するイ
ンタフェースレジスタ、セレクタ38はSDR16およびSDR17
の出力データを選択する選択器、セレクタ40は主記憶装
置１から読出されてソート処理装置５に送出されてくる
ソートすべきデータまたは、SDR16およびSDR17からの出
力データのいずれかを選択する選択器、セレクタ41はSD
R16およびSDR17からの出力データを選択する選択器、FG
R15は、SDB20およびSDB21のいずれか一方をソートすべ
きデータの読出し用バッファとして指定し、他方をソー
トすべきデータの退避用バッファとして指定するフラグ
レジスタ、セレクタ35は初期値０のFGR15の内容が反転
を受けた値とを選択する選択器、比較器23は、SDR16お
よびSDR17に保持されるソートすべきデータの予め定め
られた部分、即ち本実施例ではソートすべきデータのキ
ー部の内容同士を比較し、比較結果を出力する比較器、
比較器22はSL10の内容と、RAR12またはRAR14のいずれか
の内容とを比較し、一致を検出して出力する比較器、セ
レクタ39は、RAR12とRAR14の内容を選択する選択器、ケ
ート回路25は比較器23の内容を反転させる反転器、レジ
スタ19は初期値「０」または「１」または比較器23の出
力を保持するレジスタ、セレクタ42は初期値「０」また
は「１」と比較器23の出力を選択する選択器、比較器26
はゲート回路25の出力とレジスタ19の出力を比較し、一
致を検出する比較器、制御回路24はソート処理装置５全
体の制御を司る制御回路である。
次に、本実施例のソート処理装置５によって、表２の
データ列がソートされる動作について説明する。
データ列がソートされる動作について説明する。
今、表２のデータ列、即ちデータD0〜データD3までの
４データがメモリ上に連続に配置されており、このデー
タ列を昇順にソートする場合を考える。表２のデータD0
〜データD3は、バッファ記憶制御装置２によって主記憶
装置１から順次読出され、ソート処理装置５へ送出され
る。また、ソート命令によって示されるソートすべきデ
ータの個数「４」が命令制御装置４によって解読され、
ソート処理装置５へ送出される。
４データがメモリ上に連続に配置されており、このデー
タ列を昇順にソートする場合を考える。表２のデータD0
〜データD3は、バッファ記憶制御装置２によって主記憶
装置１から順次読出され、ソート処理装置５へ送出され
る。また、ソート命令によって示されるソートすべきデ
ータの個数「４」が命令制御装置４によって解読され、
ソート処理装置５へ送出される。
第４図は表２のデータ列、データD0〜データD3がソー
ト処理装置５によってソートされる動作を示すタイミン
グ図である。
ト処理装置５によってソートされる動作を示すタイミン
グ図である。
サイクルT0では、SL10、WAR11、RAR12、WAR13、RAR14
は初期値０にリセットされた状態を保っている。また、
命令制御装置４からソートレングス、即ちソートすべき
データの個数「４」がソート処理装置５に送られてき
て、サイクルT1でSL10にセットされる。FGR15には、同
時に初期値「０」がセットされる。FGR15が値「０」を
保持している場合は、SDB20をソートすべきデータの読
出し用バッファとし、SDB21をソートすべきデータの退
避用バッファとして使用することを指示する。一方、FG
R15が値「１」にセットされると、SDB20がソートすべき
データの退避用バッファとし、SDB21がソートすべきデ
ータの読出し用バッファとして使用することが指示され
る。
は初期値０にリセットされた状態を保っている。また、
命令制御装置４からソートレングス、即ちソートすべき
データの個数「４」がソート処理装置５に送られてき
て、サイクルT1でSL10にセットされる。FGR15には、同
時に初期値「０」がセットされる。FGR15が値「０」を
保持している場合は、SDB20をソートすべきデータの読
出し用バッファとし、SDB21をソートすべきデータの退
避用バッファとして使用することを指示する。一方、FG
R15が値「１」にセットされると、SDB20がソートすべき
データの退避用バッファとし、SDB21がソートすべきデ
ータの読出し用バッファとして使用することが指示され
る。
また、サイクルT1〜T4では、メモリから読出されたソ
ートすべきデータD0〜D3が順次ソート処理装置５へ転送
され、SDB20のライトアドレスレジスタWAR11が順次カウ
ントアップして、サイクルT2〜T5にかけて、SDB20に取
り込まれる。ソートデータD0〜D3がSDB20に取り込まれ
ると、順次SDR16、SDR17にデータが読出されて、比較器
23でデータのキー部の比較が行なわれる。レジスタ19
は、昇順ソートを行なう時には初期値「０」に、降順ソ
ートを行なう時には初期値「１」にリセットされ、今の
場合は「０」にリセットされる。まず、サイクルT3でSD
B20のワード０より読出されたソートデータD0がSDR16に
セットされ、サイクルT4でSDB20のワード１より読出さ
れたソートデータD1がSDR17にセットされる。SDR16とSD
R17にデータがそろうと比較器23でキー部の比較が行な
われ、比較結果が制御回路24に通知される。比較器23は
SDR16とSDR17の大小を検出する機能と一致を検出する機
能から構成されており、SDR16＜SDR17の時論理「１」
を、SDR16＞SDR17の時論理「０」を出力し、SDR16＝SDR
17が検出された時には上記信号とは別に一致信号が制御
回路24に通知される。
ートすべきデータD0〜D3が順次ソート処理装置５へ転送
され、SDB20のライトアドレスレジスタWAR11が順次カウ
ントアップして、サイクルT2〜T5にかけて、SDB20に取
り込まれる。ソートデータD0〜D3がSDB20に取り込まれ
ると、順次SDR16、SDR17にデータが読出されて、比較器
23でデータのキー部の比較が行なわれる。レジスタ19
は、昇順ソートを行なう時には初期値「０」に、降順ソ
ートを行なう時には初期値「１」にリセットされ、今の
場合は「０」にリセットされる。まず、サイクルT3でSD
B20のワード０より読出されたソートデータD0がSDR16に
セットされ、サイクルT4でSDB20のワード１より読出さ
れたソートデータD1がSDR17にセットされる。SDR16とSD
R17にデータがそろうと比較器23でキー部の比較が行な
われ、比較結果が制御回路24に通知される。比較器23は
SDR16とSDR17の大小を検出する機能と一致を検出する機
能から構成されており、SDR16＜SDR17の時論理「１」
を、SDR16＞SDR17の時論理「０」を出力し、SDR16＝SDR
17が検出された時には上記信号とは別に一致信号が制御
回路24に通知される。
サイクルT4でSDR16内のソートデータD0とSDR17内のソ
ートデータD1のキー部が比較され、比較器23は論理
「０」を出力し、制御回路24に通知する。この時、比較
器26では比較器23の内容がゲート回路25で反転をうけた
値「１」とレジスタ19に保持されている値「０」が比較
され、不一致を示す論理「０」が同時に制御回路24に通
知される。このことはSDR16に保持されているソートデ
ータD0とSDR17に保持されているソートデータD1が昇順
に並んでおらずソートデータの入れ替え処理が必要であ
ることを示している。つまり、先頭のソートデータはSD
R16に格納され、２番目のソートデータはSDR17に格納さ
れて比較動作が実行される。この先頭のデータD0と２番
目のデータD1がすでに昇順にソートされているならば、
比較器23は２番目のデータがより大なるキー値を保持し
ていることにより論理「１」を出力し、ゲート回路25で
反転を受けた値「０」がレジスタ19の初期値「０」と比
較され一致が検出されるはずである。バブルソートによ
る昇順ソートではより大きいキー値を有するソートデー
タが次のソートデータとの比較のために用いられ、小な
るキー値を有するソートデータが次の新たなソートデー
タと入れ替えられる。したがって、全ソートデータがす
でに昇順ソートされている場合には、ソートデータは、
必ずSDR16→SDR17→SDR16のようにSDR16とSDR17に交互
に入力されるはずである。即ち比較器23の出力も「１」
→「０」→「１」と交互に繰り返されるはずである。つ
まり、レジスタ19の値は比較器23出力値により毎回更新
され、一つ前の比較結果を保持し、今回の比較結果と比
較され、ソートデータが昇順に配列されているか否かが
検出される。
ートデータD1のキー部が比較され、比較器23は論理
「０」を出力し、制御回路24に通知する。この時、比較
器26では比較器23の内容がゲート回路25で反転をうけた
値「１」とレジスタ19に保持されている値「０」が比較
され、不一致を示す論理「０」が同時に制御回路24に通
知される。このことはSDR16に保持されているソートデ
ータD0とSDR17に保持されているソートデータD1が昇順
に並んでおらずソートデータの入れ替え処理が必要であ
ることを示している。つまり、先頭のソートデータはSD
R16に格納され、２番目のソートデータはSDR17に格納さ
れて比較動作が実行される。この先頭のデータD0と２番
目のデータD1がすでに昇順にソートされているならば、
比較器23は２番目のデータがより大なるキー値を保持し
ていることにより論理「１」を出力し、ゲート回路25で
反転を受けた値「０」がレジスタ19の初期値「０」と比
較され一致が検出されるはずである。バブルソートによ
る昇順ソートではより大きいキー値を有するソートデー
タが次のソートデータとの比較のために用いられ、小な
るキー値を有するソートデータが次の新たなソートデー
タと入れ替えられる。したがって、全ソートデータがす
でに昇順ソートされている場合には、ソートデータは、
必ずSDR16→SDR17→SDR16のようにSDR16とSDR17に交互
に入力されるはずである。即ち比較器23の出力も「１」
→「０」→「１」と交互に繰り返されるはずである。つ
まり、レジスタ19の値は比較器23出力値により毎回更新
され、一つ前の比較結果を保持し、今回の比較結果と比
較され、ソートデータが昇順に配列されているか否かが
検出される。
また、新たな比較動作のために供給されたソートデー
タのキー値が、前回、次の比較動作のために残されたソ
ートデータのキー値と等しい場合には、前回のソートデ
ータを保持するレジスタおよびレジスタ19の内容は更新
されずにそのまま保持され、新たなソートデータを保持
する側のレジスタに異なるキー値を有する新たなソート
データが供給されるまで新たなソートデータを保持する
側のレジスタの内容が更新される。
タのキー値が、前回、次の比較動作のために残されたソ
ートデータのキー値と等しい場合には、前回のソートデ
ータを保持するレジスタおよびレジスタ19の内容は更新
されずにそのまま保持され、新たなソートデータを保持
する側のレジスタに異なるキー値を有する新たなソート
データが供給されるまで新たなソートデータを保持する
側のレジスタの内容が更新される。
なお、降順ソートを行なう場合はレジスタ19の初期値
が「１」にリセットされるだけの相異で後は同様であ
る。
が「１」にリセットされるだけの相異で後は同様であ
る。
再び、第３図および第４図にもどって本実施例の動作
の続きを説明する。
の続きを説明する。
本実施例ではより大なるキー値を有するソートデータ
は次のソートデータとの比較に用いられるためにそのま
まレジスタに保持され、小なるキー値を有するソートデ
ータは退避用バッファに退避される。この退避用バッフ
ァへの退避動作によって、バブルソートにおけるソート
の入れ替え処理が実行される。
は次のソートデータとの比較に用いられるためにそのま
まレジスタに保持され、小なるキー値を有するソートデ
ータは退避用バッファに退避される。この退避用バッフ
ァへの退避動作によって、バブルソートにおけるソート
の入れ替え処理が実行される。
比較器23からの論理「０」の出力結果を受けた制御回
路24の制御によってサイクルT5ではSDR17内のソートデ
ータD1がソートすべきデータの退避用バッファとして指
定されているSDB21のワード０に退避され、同時にSDB20
のワード２から次の比較動作のために読出されたソート
データD2がSDR17にセットされる。再び比較器23で比較
動作が行なわれ、小なるキー値を有するソートデータD2
がサイクルT6でSDB21のワード１に退避される。サイク
ルT6では、SDB20のワード３から読出された最後尾のソ
ートデータD3がSDR17にセットされる。サイクルT6での
比較器23の比較動作により、小なるキー値を有するソー
トデータD3がサイクルT7でSDB21のワード２に退避され
る。
路24の制御によってサイクルT5ではSDR17内のソートデ
ータD1がソートすべきデータの退避用バッファとして指
定されているSDB21のワード０に退避され、同時にSDB20
のワード２から次の比較動作のために読出されたソート
データD2がSDR17にセットされる。再び比較器23で比較
動作が行なわれ、小なるキー値を有するソートデータD2
がサイクルT6でSDB21のワード１に退避される。サイク
ルT6では、SDB20のワード３から読出された最後尾のソ
ートデータD3がSDR17にセットされる。サイクルT6での
比較器23の比較動作により、小なるキー値を有するソー
トデータD3がサイクルT7でSDB21のワード２に退避され
る。
SDB20、SDB21のライトアドレスレジスタWAR11、WAR13
およびリードアドレスレジスタRAR12、RAR14は、それぞ
れ書込みおよび読出し動作を実行する度毎に、次のアド
レスを示すように＋１カウントアップが行なわれる。し
たがって、サイクルT5でSDB20のワード３より最後尾の
ソートデータD3が読出され、サイクルT6でSDR17にセッ
トされると同時にRAR12はSDB20のワード４を示すように
カウントアップされる。セレクタ39は、ソートすべきデ
ータの読出し用バッファとして用いられている側のリー
ドアドレスレジスタの内容を選択して比較器22に出力し
ており、比較器22でSL10の内容と比較される。サイクル
T6ではRAR12の内容は「４」でありSL10の内容「４」と
一致する。比較器22は一致信号を出力し、制御回路24に
通知する。この一致信号は、ソートすべきデータの読出
し用バッファ内のソートデータの比較動作が全て終了し
たことを示す。また、一連のソートデータは、すでに昇
順にソートされたデータではなかったためにこの比較動
作終了信号を受けた制御回路24の制御によってサイクル
T7では以下の動作が行なわれる。
およびリードアドレスレジスタRAR12、RAR14は、それぞ
れ書込みおよび読出し動作を実行する度毎に、次のアド
レスを示すように＋１カウントアップが行なわれる。し
たがって、サイクルT5でSDB20のワード３より最後尾の
ソートデータD3が読出され、サイクルT6でSDR17にセッ
トされると同時にRAR12はSDB20のワード４を示すように
カウントアップされる。セレクタ39は、ソートすべきデ
ータの読出し用バッファとして用いられている側のリー
ドアドレスレジスタの内容を選択して比較器22に出力し
ており、比較器22でSL10の内容と比較される。サイクル
T6ではRAR12の内容は「４」でありSL10の内容「４」と
一致する。比較器22は一致信号を出力し、制御回路24に
通知する。この一致信号は、ソートすべきデータの読出
し用バッファ内のソートデータの比較動作が全て終了し
たことを示す。また、一連のソートデータは、すでに昇
順にソートされたデータではなかったためにこの比較動
作終了信号を受けた制御回路24の制御によってサイクル
T7では以下の動作が行なわれる。
まず、比較器23の比較動作の結果により、小なるキー
値を有するSDR17内のソートデータD3が退避用バッファS
DB21のワード３に退避され、SDR16内に残った最大のキ
ー値を有するソートデータD0がSDR18にセットされて、
メモリの所定の場所へ格納するためにバッファ記憶制御
装置２に送出される。
値を有するSDR17内のソートデータD3が退避用バッファS
DB21のワード３に退避され、SDR16内に残った最大のキ
ー値を有するソートデータD0がSDR18にセットされて、
メモリの所定の場所へ格納するためにバッファ記憶制御
装置２に送出される。
SL10は、減算器50で−１された値「３」に更新され
る。この値は、ソート処理装置５内に保持されているソ
ートすべきデータの残数を示している。
る。この値は、ソート処理装置５内に保持されているソ
ートすべきデータの残数を示している。
WAR11、RAR12、WAR13、RAR14の各アドレスレジスタの
値は初期値「０」にリセットされ、レジスタ19も初期値
「０」にリセットされる。また、FGR15は、自身の内容
が反転された値、即ち値「１」に更新される。これはサ
イクルT7以降、SDB20がソートすべきデータの退避用バ
ッファに、SDB21がソートすべきデータの読出し用バッ
ファとして使用されることを示している。ここまでは第
１図のソート処理装置と同様の動作であり、この指示に
従って上述した一連の処理動作が繰り返される。
値は初期値「０」にリセットされ、レジスタ19も初期値
「０」にリセットされる。また、FGR15は、自身の内容
が反転された値、即ち値「１」に更新される。これはサ
イクルT7以降、SDB20がソートすべきデータの退避用バ
ッファに、SDB21がソートすべきデータの読出し用バッ
ファとして使用されることを示している。ここまでは第
１図のソート処理装置と同様の動作であり、この指示に
従って上述した一連の処理動作が繰り返される。
即ち、サイクルT8〜T10までSDB21のワード０〜ワード
２に保持されているソートデータがSDR16またはSDR17に
順次読出されて比較器23で比較動作が行なわれて小なる
キー値を有するソートデータがFGR15の指示によりSDB20
のワード０より順に退避させられる。ところで今回の一
連の比較動作では比較器26はいずれもソートデータが昇
順にソートされている論理「１」を出力し、全ソートデ
ータがすでに昇順にソートされていることを検出し、制
御回路24に通知する。同時にサイクルT10ではRAR14の値
とSL10の値の一致が検出されて、比較動作の終了が制御
回路24に通知され、以降では、全ソートデータがすでに
昇順にソートされていることにより、ソート処理の終了
処理が実行される。
２に保持されているソートデータがSDR16またはSDR17に
順次読出されて比較器23で比較動作が行なわれて小なる
キー値を有するソートデータがFGR15の指示によりSDB20
のワード０より順に退避させられる。ところで今回の一
連の比較動作では比較器26はいずれもソートデータが昇
順にソートされている論理「１」を出力し、全ソートデ
ータがすでに昇順にソートされていることを検出し、制
御回路24に通知する。同時にサイクルT10ではRAR14の値
とSL10の値の一致が検出されて、比較動作の終了が制御
回路24に通知され、以降では、全ソートデータがすでに
昇順にソートされていることにより、ソート処理の終了
処理が実行される。
まず、サイクルT11でSDR17に保持されている小なるキ
ー値を有するソートデータD2がSDB20のワード１に退避
され、同時に残ソートデータの中で最大のキー値を有す
るソートデータD3がSDR16からSDR18にセットされてバッ
ファ記憶制御装置２に送出される。また、サイクルT11
ではSL10の値は残ソートデータの個数を示す値「０」に
リセットされ、またSDB20に退避されている昇順ソート
済のソートデータを掃き出すためにサイクルT10で保持
されているWAR11のポインタ値がサイクルT11でRAR12に
移される。そして、RAR12のポインタ値が−１ずつ減算
されて、SDB20のワード1,0よりソートデータD2およびD1
が読出され、サイクルT12,T13でSDR16にセットされ引き
続いてサイクルT13,T14でSDR18にセットされて、バッフ
ァ記憶制御装置２に送出されることで全ソート処理動作
が終了する。
ー値を有するソートデータD2がSDB20のワード１に退避
され、同時に残ソートデータの中で最大のキー値を有す
るソートデータD3がSDR16からSDR18にセットされてバッ
ファ記憶制御装置２に送出される。また、サイクルT11
ではSL10の値は残ソートデータの個数を示す値「０」に
リセットされ、またSDB20に退避されている昇順ソート
済のソートデータを掃き出すためにサイクルT10で保持
されているWAR11のポインタ値がサイクルT11でRAR12に
移される。そして、RAR12のポインタ値が−１ずつ減算
されて、SDB20のワード1,0よりソートデータD2およびD1
が読出され、サイクルT12,T13でSDR16にセットされ引き
続いてサイクルT13,T14でSDR18にセットされて、バッフ
ァ記憶制御装置２に送出されることで全ソート処理動作
が終了する。
昇順ソートの結果はソートデータがストアされたメモ
リの所定の場所より、ストア順の逆にソートデータのポ
インタ部を取り出すことにより得られる。
リの所定の場所より、ストア順の逆にソートデータのポ
インタ部を取り出すことにより得られる。
降順ソートの場合も、昇順ソートの場合と同様に行な
うことができる。
うことができる。
以上説明したように本発明は、従来多数のソフトウェ
ア命令により逐次的に実行していたソート処理をハード
ウェアによるパイプライン処理により行なうことによ
り、高速に実行できる効果があり、また、バブルソート
の実行中にソート処理がすでに終了したか否かを検出す
ることにより、無駄なソート処理の実行を削減し、ソー
ト処理の一層の高速化が可能となる効果がある。
ア命令により逐次的に実行していたソート処理をハード
ウェアによるパイプライン処理により行なうことによ
り、高速に実行できる効果があり、また、バブルソート
の実行中にソート処理がすでに終了したか否かを検出す
ることにより、無駄なソート処理の実行を削減し、ソー
ト処理の一層の高速化が可能となる効果がある。
第１図は本発明のソート処理装置の第１の実施例のブロ
ック図、第２図は第１図のソート処理装置によって実行
されるソート処理の動作を表わすタイミング図、第３図
は本発明のソート処理装置の第２の実施例のブロック
図、第４図は本実施例のソート処理装置によって実行さ
れるソート処理の動作を表わしたタイミング図、第５図
はソート処理装置を含むシステム全体の一実施例の構成
図、第６図、第７図はバブルソートによるソート処理の
動作を示す図である。 １……主記憶装置、２……バッファ記憶制御装置、３…
…演算制御装置、４……命令制御装置、５……ソート制
御装置、10……ソートレングスレジスタ（SL）、11,13
……ライトアドレスレジスタ（WAR）、12,14……リード
アドレスレジスタ（RAR）、15……フラグレジスタ（FG
R）、16,17,18……ソートデータレジスタ（SDR）、19…
…レジスタ、20,21……ソートデータバッファ（SDB）、
22,23,26……比較器、24……制御回路、25……ゲート回
路、30〜42……セレクタ、50,55,56……−１減算器、51
〜54……＋１加算器。
ック図、第２図は第１図のソート処理装置によって実行
されるソート処理の動作を表わすタイミング図、第３図
は本発明のソート処理装置の第２の実施例のブロック
図、第４図は本実施例のソート処理装置によって実行さ
れるソート処理の動作を表わしたタイミング図、第５図
はソート処理装置を含むシステム全体の一実施例の構成
図、第６図、第７図はバブルソートによるソート処理の
動作を示す図である。 １……主記憶装置、２……バッファ記憶制御装置、３…
…演算制御装置、４……命令制御装置、５……ソート制
御装置、10……ソートレングスレジスタ（SL）、11,13
……ライトアドレスレジスタ（WAR）、12,14……リード
アドレスレジスタ（RAR）、15……フラグレジスタ（FG
R）、16,17,18……ソートデータレジスタ（SDR）、19…
…レジスタ、20,21……ソートデータバッファ（SDB）、
22,23,26……比較器、24……制御回路、25……ゲート回
路、30〜42……セレクタ、50,55,56……−１減算器、51
〜54……＋１加算器。
Claims (2)
- 【請求項１】第１および第２のデータバッファと、 これら第１および第２のデータバッファのうち、いずれ
か一方をソートすべきデータの読出し用バッファに、他
方をソートすべきデータの退避用バッファとして選択す
る手段と、 最初にソートすべきデータの読出し用として選択された
データバッファに外部から与えられるソートすべきデー
タを入力する手段と、 ソートすべきデータの読出し用バッファの出力を保持す
る第１および第２のレジスタと、 これら第１および第２のレジスタにソートすべきデータ
を順次格納する手段と、 前記第１および第２のレジスタにソートすべきデータが
格納される度に、第１および第２のレジスタの予め定め
られた部分の内容同士を比較し、比較結果を出力する比
較手段と、 この比較手段が第１のレジスタの値を退避すべき旨を出
力した場合は、第１のレジスタに保持されているデータ
を前記退避用バッファに退避し、第２のレジスタに保持
されているデータはそのまま保持し、新たなデータを第
１のレジスタに格納して次の比較動作を実行させ、一方
前記比較手段が第２のレジスタの値を退避すべき旨を出
力した場合は、同様に第２のレジスタに保持されている
データを前記退避用バッファに退避し、第１のレジスタ
に保持されているデータはそのまま保持し、新たなデー
タを第２のレジスタに格納して次の動作を実行させる手
段と、 予め指定された全データの前記比較手段と前記退避手段
が終了すると、前記退避用バッファに退避されずに前記
第１および第２のレジスタのいずれか一方にそのまま保
持されているデータを予め指定された格納場所に出力す
る手段と、 前記退避用バッファとして用いられたデータバッファを
ソートすべきデータの読出し用バッファとし、他方をソ
ートすべきデータの退避用バッファとして再選択し、こ
の再選択された読出し用バッファから順次ソートすべき
データを読み出し、上記一連の比較動作と退避用バッフ
ァへの退避動作および結果データの出力動作を繰り返さ
せる手段とを含むことを特徴とするソート処理装置。 - 【請求項２】第１および第２のレジスタと、 これら第１および第２のレジスタにソートすべきデータ
が格納される度に、前記第１および第２のレジスタの予
め定められた部分の内容同士を比較し、比較結果を出力
する比較手段と、 この比較手段の比較結果に従って、前記第１および第２
のレジスタのいずれに新たなソートすべきデータを格納
すべきかを指定するレジスタ指定手段と、 このレジスタ指定手段の指定に従って、前記第１および
第２のレジスタの一方に新たなソートすべきデータを格
納する手段と、 前記レジスタ指定手段がソートすべき全データに対して
前記第１および第２のレジスタを交互に指定したかを検
出する検出手段と、 この検出手段の検出出力があった場合は、前記ソートす
べき全データがすでにソート済みデータであることを検
出し、前記ソートすべき全データを予め定められた順序
に従って出力してソート処理を終了させる手段とを含む
ことを特徴とするソート処理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63224304A JPH0833812B2 (ja) | 1988-09-06 | 1988-09-06 | ソート処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63224304A JPH0833812B2 (ja) | 1988-09-06 | 1988-09-06 | ソート処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0271327A JPH0271327A (ja) | 1990-03-09 |
| JPH0833812B2 true JPH0833812B2 (ja) | 1996-03-29 |
Family
ID=16811670
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63224304A Expired - Lifetime JPH0833812B2 (ja) | 1988-09-06 | 1988-09-06 | ソート処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0833812B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP6255840B2 (ja) | 2013-09-24 | 2018-01-10 | 横浜ゴム株式会社 | 空気入りタイヤ |
| JP6318515B2 (ja) | 2013-09-24 | 2018-05-09 | 横浜ゴム株式会社 | 空気入りタイヤおよびその製造方法 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6054043A (ja) * | 1983-09-01 | 1985-03-28 | Fujitsu Ltd | ソ−ト処理器 |
-
1988
- 1988-09-06 JP JP63224304A patent/JPH0833812B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0271327A (ja) | 1990-03-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4476525A (en) | Pipeline-controlled data processing system capable of performing a plurality of instructions simultaneously | |
| US4053871A (en) | Method and system for the iterative and simultaneous comparison of data with a group of reference data items | |
| US5742805A (en) | Method and apparatus for a single history register based branch predictor in a superscalar microprocessor | |
| JP3188467B2 (ja) | 最小値・最大値検索装置 | |
| JPH0814801B2 (ja) | プログラマブルアクセスメモリ | |
| KR0152979B1 (ko) | 가변길이 데이터 처리장치 | |
| US5081608A (en) | Apparatus for processing record-structured data by inserting replacement data of arbitrary length into selected data fields | |
| JPS6235949A (ja) | メモリ−装置 | |
| US4734877A (en) | Vector processing system | |
| US4028670A (en) | Fetch instruction for operand address calculation | |
| JPH0786875B2 (ja) | ベクトル処理装置 | |
| JPS6142031A (ja) | ソ−ト処理装置 | |
| JPH0271327A (ja) | ソート処理装置 | |
| JPH01273132A (ja) | マイクロプロセッサ | |
| JPS6327746B2 (ja) | ||
| JP2772125B2 (ja) | 辞書検索方式 | |
| JP2671325B2 (ja) | データ処理装置 | |
| JPS61278933A (ja) | デ−タのソ−ト方式 | |
| JP3693873B2 (ja) | マスクビット数演算装置、ベクトル処理装置、情報処理装置 | |
| JPH048815B2 (ja) | ||
| JPH0926872A (ja) | パイプラインマージソータ | |
| JPH07295812A (ja) | 条件分岐制御方法および装置 | |
| JPH052485A (ja) | パイプライン制御方式 | |
| JPH0520353A (ja) | ベクトルデータ処理装置 | |
| JPH0370826B2 (ja) |