JPH0797310B2 - ソ−ト処理装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、文字列や数値データを対象としたソート処理
装置に係り、特に比較転送ユニットの１次元アレイ構造
からなるソート処理装置の改良に関する。

〔従来の技術〕

ソート処理は、与えられたデータの集まりを所定の規則
に基づいて並び替える処理をいう。電子計算機における
ソート処理とは、数値あるいは文字列として与えられた
データが、計算機内部では“0"あるいは“1"の二値符号
で表記されている事から、二値符号の持つ数値的意味に
もとづいて、昇順（小さいものから大きいものへの順）
あるい降順（大きいものから小さいものへの順）にデー
タを並びかえることである。

一般に、ソート対象とするデータをレコードと称し、レ
コードはデータ相互の比較を行って大小関係を判定する
キー部と比較を行わない部分とに分けることができる。
このレコードを、文字列や正整数（符号なし整数）に限
定した場合には、二進符号を表されたレコードのキー部
を上位桁ほど優位性を持たせて比較することによって、
ソート処理を行うレコード相互の大小関係を決定でき
る。

従来、このようなソート処理を高速に実行する専用のソ
ート処理装置として、本出願人は、データ相互の比較に
よる大小関係の判定とデータの転送を並列に行う構成の
ものを提案した（特開昭60-81640号公報参照）。第４図
はかかるソート処理装置の構成図である。本装置は、比
較の対象となるデータを保持するための第１のメモリ10
1および第２のメモリ102、比較器103、該比較器103によ
って得られた判定結果を保持するためのフラグレジスタ
104および転送回路105からなる比較転送ユニット100を
複数個、一次元接続した構成となっている。各ユニット
装置100では、第１、第２のメモリ100、102及び比較器1
03、転送回路105をｉビット幅で構成され、第１、第２
のメモリの容量をｉ×ｊビットすることにより、ｉ×ｋ
（ｋ≦ｊ）ビットの長さを持つレコードを、Ｎレコード
（Ｎ≦２×ユニット数）までソート出来る。このソート
処理に要する時間は、以下に説明する動作原理にしたが
って、レコードの入出力時間（２×kNステップ）に等し
い。

第５図は、第４図のソート処理装置の動作原理図であ
り、１例として０から９までの一桁の数値データのう
ち、3,6,5,2,4,1の６個のレコードを降順にソートする
場合の動作を示している。即ち、この例は、一桁の数値
をｉビットとして、１レコード＝ｉビット,k＝1,N＝６
である。

ソート処理を行うにあたって、全てのユニット100の第
１のメモリ101および第２のメモリ102の内容を初期設定
する。降順ソートの場合には、初期値としてデータの最
小値である０を設定する。ソート処理は、順次レコード
を入力する入力操作と、順次レコードを出力する出力操
作とからなる。各ユニット100では、一回の入力操作で
データ（ｉビット）の右方向への転送と２個のデータ間
での比較とを同期して行う。この場合、転送されるデー
タは第１および第２のメモリ101,102に保持された２個
のデータのうち小さい方である。この時、データの転送
と同期して１個のレコードを該ソート処理装置に入力
し、最左端のユニットの第１のメモリ101あるいは第２
のメモリ102のいずれのうち転送によって空になった方
のメモリに保持する（T1〜T7）。

ソート対象とする６個のレコードの入力が完了した時点
で、出力操作によって順次データを隣接する左側のユニ
ットに転送する。この時、転送するデータはユニット内
の２個のデータのうち大きい方であり、最左端のユニッ
トからソート済みのレコード列が降順に出力される。最
右端のユニットには初期値と同じ０を入力する（T7〜T1
2）。

本ソート処理装置を用いて降順にソートする場合には、
初期設定として、全ユニット100の第１および第１のメ
モリ101及び第２のメモリ102に、データの最大値９を設
定しておき、入力操作時には、各ユニットで比較した２
個のデータのうち、大きい方を右方向に転送し、出力操
作時には、各ユニットで比較した２個のデータのうち小
さい方を左方向に転送する。

次に、第４図のソート処理装置において、１レコードの
長さが一度に比較転送できるｉビットを越える場合（１
＜ｋ≦ｊ）の動作例を第６図に示す。第６図は、アルフ
ァベット１文字をｉビットで表現するとして、それぞれ
２文字の長さ（ｋ＝２）からなる４個のレコード（Ｎ＝
４）ab,de,ca,bdを２個のユニット（ユニット0,ユニッ
ト１）を使用して降順にソートする場合を示している。
第６図において、m1とm2は、それぞれ各ユニットの２個
のメモリ101,102、ｆはフラグレジスタ104である。個々
のレコードを１ビット単位のｋ個のデータに分割して大
小比較し、それまでの比較が等しくて、初めて大小関係
が決まった時にその値を比較結果としてフラグレジスタ
に設定する。第６図では、メモリm1の値とメモリm2の値
を比較して、メモリm2の値が小さい時に、比較結果は１
としてフラグレジスタｆに設定される。

第６図（Ａ）は入力操作時の動作であり、ユニット０で
は、フラグレジスタｆ＝０であればメモリm1の内容を、
ｆ＝１であればメモリm2の内容を、右方向に隣接するユ
ニット１に向けて出力する。一方、第６図（Ｂ）は出力
操作時の動作であり、ユニット１では、フラグレジスタ
ｆ＝１であればメモリm1の内容を、ｆ＝０であればメモ
リm2の内容を左方向に隣接するユニット０に向けて出力
し、同様に、ユニット０では外部に出力する。なお、こ
のような１レコードの長さがｉビットを越える場合の動
作は、先の特開昭60-81640号公報に詳述されている。

第６図に示したように、メモリ容量がｉ×ｊの比較転送
ユニットを２個で構成されたソート処理装置では、ｊ＝
２の場合、１文字をｉビットして、長さ２文字（ｋ＝
２）の４個（Ｎ＝４）のレコードを、16ステップ（＝２
×ｋ×Ｎ）でソートできる。なお、上記の手順の中で，
比較器による比較動作はレコードの転送と同期して行
え、比較結果をフラグレジスタに移動する操作は、レコ
ードの転送と比較動作に比べて十分短い時間で処理する
ことが出来る為、ステップ数の算出では無視できるとし
てある。第６図で、カッコで示した部分がこれを意味し
ている。

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

上記従来技術のソート処理装置によれば、レコード数に
等しい入出力操作回数と出力操作回数でソート処理が行
える。また、１レコードの長さが一度に比較転送できる
ｉビットを越える場合には、個々のレコードをｉビット
単位のｋ個のデータに分割し、ｋ回の入力／出力操作に
よって、１レコードの処理を行うことができる。従っ
て、ｉ×ｋ（ｋ≦ｊ）ビットまでの長さのレコードをレ
コード数に比例する時間でソートできる。

一方、ソート可能なレコード長は、比較転送ユニット内
のメモリ容量によって決定されることから、ソート対象
とするレコードを長くするためには、比較転送ユニット
内のメモリ容量を予め大きく設けておかなればならな
い。比較転送ユニット内のメモリ容量を大きくした場合
には、レコード長が短いソート処理時のメモリ使用効率
が低下することから、レコード長に関係なく比較転送ユ
ニットのメモリを有効に活用することは困難であった。

本発明の目的は、比較転送ユニット内のメモリ容量に制
限されることなく、レコード長の長いレコードを高速に
ソートできるソート処理装置を実現することにある。

〔課題を解決するための手段及び作用〕

本発明は、比較転送ユニットの１次元アレイ構造からな
るソート処理装置に於て、ソート対象とするレコードの
長さに応じて、該レコードを複数の比較転送ユニットに
分割した格納し、該レコードを分割して格納した各比較
転送ユニットをあたかも一つの比較転送ユニットと見做
して、その比較・転送処理を連動させて行うことを特徴
とする。

本発明に基づくソート処理装置では、複数の比較転送ユ
ニットを連動して動作させることから、比較転送ユニッ
ト単体では扱うことが出来ない程長いレコードであって
も、該レコードを複数の比較転送ユニットに分割して格
納することによってソートすることが出来る。更に、複
数の比較転送ユニットを比較器の幅が広がる方向に連動
させることによって、一度に比較・転送するデータの幅
を拡張することも可能であり、ソート処理装置のスルー
プットの向上、及び、ソート処理装置の使用環境に合わ
せて一度に入力／出力するデータの処理幅を適合させる
ことが出来る。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明のソート処理装置の一実施例の構成図
で、（１）はソート処理装置全体の構成図、（２）は一
つのユニット群の構成図である。図中、11は第４図で示
した一つの比較転送ユニット100と同一構成であり、本
実施例では、４個の比較転送ユニットで一つのユニット
群を構成している。各ユニット群内の４個のユニット
は、U0からU3の識別名を有する。更に、G0からG3の識別
名を有する４個のユニット群でソート処理装置全体10を
構成する。従って、本実施例のソート処理装置は、G0-U
0からG3-U3までの16個の比較転送ユニット11で構成され
る。ユニット群内の12は、双方向データ転送を行うバス
の転送経路を切替えるための転送切替回路である。ソー
ト対象となるレコードの入出力は、データ入出力端子PA
とPBを介して行い、PA及びPBは、それぞれ一つの比較転
送ユニット11のデータ処理幅と等しいｉビット幅のＬと
Ｈからなる。

比較転送ユニット11は、第４図に示したように、第１、
第２のメモリ101、102及び比較器103、入出力回路105を
ｉビット幅で構成し、第１、第２のメモリ101,102の容
量をそれぞれｉ×ｊビットとする。この時、ソート対象
とする各レコードをｉビット幅のデータにｋ分割して、
１レコード当りｋ（ｋ≦ｊ）回の比較と転送処理を繰返
すことによって、第４図に示した比較転送ユニットの固
定的な一次元配列によって、１レコードが最大ｉ×ｊビ
ットの長さを持つ複数のレコードをレコードの入出力時
間でソート出来る（第６図）。本発明では、この比較転
送ユニット11を複数個、連結及び／又は結合して連動さ
せることで、ソートできるレコード長の上限の拡大、お
よび／又は、ソート処理速度すなわちソートに要するス
テップ数の結減を実現するものである。

第１図の実施例は、上記の機能を有する比較転送ユニッ
ト11を比較器の幅を拡張する方向に最大２ユニット連動
でき、また、メモリの深さを拡張する方向に最大４ユニ
ット連動できる構成を示したものである。以下では、比
較転送ユニットの比較器の幅を拡張する方向に複数ユニ
ットを連動せしめることを結合と称し、比較転送ユニッ
トのメモリの容量を拡張する方向に複数ユニットを連動
することを連結と称する。

第２図は第１図に示した本ソート処理装置におけるデー
タ転送経路を示したものである。

第２図（１）は、比較転送ユニットの連結を行った場合
のデータ転送経路である。この時、形成されるデータ経
路は、図中の太実線で示すように、16個の比較転送ユニ
ット11を１次元アレイ上に縦続接続した次の１種類であ
る。

PA:L→G0:U0→G0:U1……G3:U3→PB:L 連結の場合、１回の比較・転送処理は従来と同じくｉビ
ット単位である。ただし、連結対象の複数の比較転送ユ
ニットごとに（実施例では最大４ユニット）、各々をあ
たかも一つのユニットのごとく連動して動作せしめるこ
とにより、単一の比較転送ユニットでは扱うことができ
ない長いレコードであっても、連動して動作する複数の
縦続接続の各ユニットに分割して格納でき（即ち、比較
転送ユニットのメモリ容量が拡張）、ソート対象のレコ
ード長を拡大できる。

第２図（２）は、２個の比較転送ユニットを結合した場
合のデータ転送経路である。この場合のデータ転送経路
は、図中の太実線で示すローバスト側で太破線で示すハ
イバイト側の次の２種類である。なお、ローバイト側、
ハイバイト側のそれぞれのデータ処理幅はｉビットであ
る。

PA:L→G0:U0→G0:U3……G3:U3→PB:L ローバイト側 PA:H→G0:U1→G0:U2……G3:U2→PB:L ハイバイト側 実施例の２結合の場合、ローバイト側とハイバイト側の
各々、２個の比較転送ユニットが並列に動作するため
（即ち、比較転送ユニットの比較器の幅が拡張）、１回
の比較・転送処理は２×ｉビット単位であり、ソート処
理速度を1/2に短縮できる。

第３図は、第１図に示した16個の比較転送ユニット11を
結合及び連結する場合に実現される動作モードを示した
図である。図中の（ ）はユニットの連結状態を示し、
［ ］はユニットの結合状態を示している。また（ ）
及び［ ］内のHLは、レコードを比較転送ユニットに分
割して入力する際のハイバイト側とローバイト側を示し
ている。ユニットの連結と結合は、比較転送ユニットの
接続を変更する、すなわち、ユニット間の接続を転送切
替回路を介して、可変構造としておき、ソートするレコ
ードの長さや要求されるソート処理性能に応じて接続関
係を変更してデータ転送路を形成することで容易に実現
できる。モード１は、第４図の従来技術に対応し、レコ
ードを単純に各々の比較転送ユニットに格納することか
ら、最大ｉ×ｊビット（ｊ＝ｋ）の長さを持つレコード
を16レコードソートできる。モード２は、２個の比較転
送ユニットを１組として連結した場合であり、ソート可
能な最大レコード長はモード１の２倍に拡張される。以
下、モード５までは、順次連結する比較転送ユニットの
数を２倍づつ拡張した場合であり、モード５ではモード
１に比較してソート可能な最大レコード長を16倍とでき
る。

モード６からモード９までは、２個の比較転送ユニット
を結合した上でユニットの連結を行う例である。モード
６は、単に２個のユニットを１組として結合した場合で
あり、データ転送処理の幅を２倍に拡張したことから、
ソート処理のスループットを２倍に拡張できる。この
時、ソート可能な最大レコード長は、１レコードが２分
割されて２個のユニットに並列に入力されるため、モー
ド１の場合の２倍である。モード７からモード９は、２
個のユニットを結合するモード６を基本として、更にユ
ニットの連結を行う場合であり、モード６と同じソート
処理スループット（モード１の２倍）で、最大レコード
長がモード６を基本として２倍づつ拡張することができ
る。

以上説明した実施例では、16個の比較転送ユニットから
なるソート処理装置に於て、データ転送幅を拡張する方
向に最大２ユニットを結合し、データを格納するメモリ
量を拡張する方向に最大16ユニットを連結する場合を示
したが、全体のユニット数が16個以外の場合であって
も、本実施例と同様にユニット間の接続構造を可変とす
ることによって、データの転送処理幅及びソートできる
レコードの最大長を拡張できる。更に、ユニットを結合
・連結する個数を本実施例以外の値とすることによっ
て、データ転送処理幅及び最大ソート可能なレコード長
を所望の値まで拡張できる。一方、本実施例では、結合
・連結の基本とする比較転送ユニットのデータ処理幅を
ｉビット＝１バイトとして示したが、これ以外の値であ
っても、本実施例と同様にユニットの結合・連結を行う
ことが出来る。

次に、一例として第３図のモード２（２連結）及びモー
ド６（２結合）の場合の具体的な動作例を示す。ただ
し、説明の簡単化のため、２個の比較転送ユニット（ユ
ニット0,ユニット１）で一つのユニット群を構成し、ユ
ニット群は２組（ユニット群G0,ユニット群G1）で構成
されるとする。

第７図は、比較転送ユニットを連結したレコード長を拡
大する場合の動作例であり、（Ａ）は入力操作時の動
作、（ｂ）は出力操作時の動作である。先の第６図の例
では、ｋ＝２すなわち英文字２文字からなるレコードを
ソートする場合を示したが、第７図は、それぞれ２個の
比較転送ユニットを連結し、２組のユニット群により、
英文字４文字（ｋ＝４）からなる４個（Ｎ＝４）のレコ
ード（abcd,defg,acdf,abef）をソートする場合を示
す。なお、１文字はｉビットとし、個々の比較転送ユニ
ットの各メモリの容量はｉ×２（ｊ＝２）とする。フラ
グレジスタへの比較結果の設定は第６図の例と同一であ
るが、ユニット群を形成する２個のユニット（ユニット
０とユニット１）を連動して動作させる。すなわち、ユ
ニット０のメモリm1にユニット１のメモリm1が連結さ
れ、同様にユニット０のメモリm2にユニット１のメモリ
m2を連結動作させるために、連動しているユニット群に
フラグレジスタＦを用意して（第７図ではユニット１の
フラグレジスタを利用するとしている）、Ｆの値によっ
てレコードの転送を制御する。入力操作時には、Ｆ＝０
であればメモリm1側の内容を、Ｆ＝１であればメモリm2
側の内容を右方向に隣接する比較転送ユニットに向けて
出力する。一方、出力操作時は、Ｆ＝１であればメモリ
m1側の内容を、Ｆ＝０であればメモリm2側の内容を左方
向に隣接する比較転送ユニットに向けて出力する。

第７図に示したように、複数の比較転送ユニットをメモ
リの容量が増える方向に連結することで、単一の比較転
送ユニットではソートできない長さのレコードをソート
することができる。この時のソートに必要なステップ数
は、一度に転送できるデータ幅が第６図の単一ユニット
でのソートと同一（ｉビット）であるから、レコード長
が長くなった分だけ増大し、第７図の例では32ステップ
（＝２×ｋ×Ｎ）を要している。

第８図は、複数の比較転送ユニットを結合動作させソー
ト処理速度、すなわち、ソートに要するステップ数を削
減する場合の動作を、第７図と同じ４個のレコードを用
いた降順ソートの例を示したものである。第７図の比較
転送ユニットの連結との違いは、連結がメモリの容量を
増やす方向に比較転送ユニットを縦続接続していたのに
対し、結合では一度に比較転送できるデータの幅を増や
す方向、即ち、単一ユニットではｉビットであったデー
タ転送の幅を、第８図に示すように、例えば２個のユニ
ットと結合して（２×ｉ）ビットに拡張したことであ
る。従って、４文字からなるレコードを２文字づつ２回
の転送操作で入力することができる。第８図で、（Ａ）
は入力操作の動作、（Ｂ）は出力操作時の動作である。

第８図に示した２ユニットの結合の例の場合、２個のユ
ニットが並列動作の論理的に１個のユニットとして振る
舞い、第７図のユニットの連結では32ステップを要して
いたソート処理時間が1/2の16ステップで実現できるこ
とがわかる。

以上、具体例として、１回のデータ転送の幅ｉビット、
メモリm1,m2の容量ｉ×２（ｊ＝２）ビットの比較転送
ユニットを２個用い、連結動作させることで、ｉ×４ビ
ット長のレコードをソートできること、さらに、それら
を結合動作させることで、ソート処理時間を1/2に削減
できることを示した。これら連結および結合によるユニ
ットの連動は、複数のユニットを用いて論理的なユニッ
トを形成することが基本であり、論理ユニットを形成す
る際のユニット接続の方向がメモリを増やす方向である
か、あるいは、データ転送路を拡大する方向であるかの
違いである。したがって、転送切替回路により比較転送
ユニット間の接続が可変構造としておくことによって、
複数の比較転送ユニットからなる論理的なユニットをレ
コード長やソート処理速度に応じて形成することが可能
となる。特に、専用ハードウェア化されたソート処理装
置では、レコード長が短い場合でも長い場合でも、備え
られたハードウェアが有効に機能して十分に高い性能を
達成することが重要であり、例えばユニットの連結を用
いると、短いレコードはユニット単独でソートを行な
え、長いレコードは複数のユニットを連結してソートす
るので、単にレコード長に対するハードウェア的な制限
を緩和するだけでなく、ハードウェアを有効に利用する
と言う点でも極めて有効に機能する。即ち、短いレコー
ドは多数を、より長いレコードは少ない個数を一度にソ
ートできるソート処理装置を実現することができる。

〔発明の効果〕

以上説明したように、本発明のソート処理装置では、ソ
ート処理時のデータ転送幅及び最大レコード長等のソー
ト処理条件に基づいて、１次元アレイ上に配置した比較
転送ユニットの接続構造を変更できる構成としたことに
よって、使用環境、特にデータ転送処理幅や要求される
ソート処理性能に応じたソート処理装置を容易に実現す
ることが出来る。更に、本発明に基づくソート処理装置
をLSI化した場合には、比較転送ユニットの接続構成で
外部使用条件を吸収できることから、外部使用条件に依
存せずに繰返し単位となる比較転送ユニットを設計でき
ること、及びLSI化したソート処理装置の適用範囲が広
がる利点がある。

【図面の簡単な説明】

第１図は本発明の一実施例のソート処理装置の構成図、
第２図は第１図の実施例のデータ転送路の構成を示す
図、第３図は第１図の実施例の動作モードを示す図、第
４図は従来のソート処理装置の構成図、第５図は第４図
に示したソート処理装置の動作原理を示す図、第６図は
従来の具体的な動作例を示す図、第７図は本発明の連結
の具体的な動作例を示す図、第８図は本発明の結合の具
体的な動作例を示す図である。 10……ソート処理装置、11……比較転送ユニット、12…
…バス切替回路、13……ユニット群。

Claims (3)

【特許請求の範囲】
1. 【請求項１】２個のデータを格納する第１および第２の
   メモリと、該第１および第２のメモリに保持されたデー
   タ間の大小関係を判定する比較器と、該２個のデータの
   いずれか一方を転送するための転送回路とを少なくとも
   有する比較転送ユニットが複数個の１次元アレイからな
   るソート処理装置において、 前記複数個の比較転送ユニットを、２個あるいはそれ以
   上の比較転送ユニットを１組とする任意の組にグループ
   分けする手段を設け、 ソート対象レコードを、前記１組を構成する各比較転送
   ユニットに分割して与え、当該各比較転送ユニットを連
   動して動作せしめることを特徴とするソート処理装置。
2. 【請求項２】特許請求の範囲第１項記載のソート処理装
   置において、１組を構成する各比較転送ユニットを並列
   接続とし、当該各比較転送ユニットを並列に連動して動
   作せしめることを特徴とするソート処理装置。
3. 【請求項３】特許請求の範囲第１項記載のソート処理装
   置において、１組を構成する各比較転送ユニットを縦続
   接続とし、当該各比較転送ユニットの第１および第２の
   メモリ全体をそれぞれ第１および第２のメモリとして、
   該各比較転送ユニットを連動して動作せしめことを特徴
   とするソート処理装置。