JPH024926B2

JPH024926B2 -

Info

Publication number: JPH024926B2
Application number: JP18836883A
Authority: JP
Inventors: Nobuo Tsuda; Tetsuji Sato
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1983-10-11
Filing date: 1983-10-11
Publication date: 1990-01-31
Also published as: JPS6081640A

Description

【発明の詳細な説明】本発明はソート処理装置に関し、特にソート処
理を並列に実行する装置に関する。

ソート処理とは、数値データや文字データから
なる配列要素を一定の順序に従つて並べ替える処
理である。電子計算機でソート処理を行うには、
配列要素を記述している２値符号の数値的意味か
ら配列要素間の大小関係を判定して、配列要素を
昇順（小さいものから大きいものへの順）もしく
は降順（大きいものから小さいものへの順）に並
べ替えを行う。この際、配列要素が数値データの
場合には数値の大きさに順じて並べ替えられる
が、文字データの場合には、文字を記述している
ASCII（Abbreviation for American Standard
Code for Information Interchange）コードや
JISコードがアルフアベツト順やあいうえお順に
対応して昇順の大小関係を有しているため、辞書
の記載順序と同様な並べ替えを行うことができ
る。

電子計算機を用いた従来のソート処理では、ハ
ードウエアが逐次処理用に構成されているため、
配列要素数が大量の場合には処理に要する時間が
極めて長くなる問題があつた。第１図は、従来技
術による逐次的なソート処理の原理図である。本
図は、置換法と呼ばれるソート処理手順の一例を
示している。本手順では、電子計算機のメモリ上
に配列要素の格納領域を定義しておき、そこに初
期状態においてあらかじめ配列要素を書き込んで
おく。第１図では、D₀からD₅が６個の配列要素
の格納領域であり、初期状態において６個の配列
要素４，６，１，３，５，２が書き込まれてい
る。T₀からT_l-1はソート処理のサイクルを表わ
し、サイクルごとに配列要素が並べ替えられてゆ
く様子を図示している。本図の手順では、T₀か
らT_l-1の各サイクルにおいて以下に述べる操作を
行う。

配列要素の格納領域Ａから配列要素ａを読み
出す。

配列要素の格納領域Ｂから配列要素ｂを読み
出す。

配列要素ａおよびｂの大小関係を判定する。
ここで、配列要素ａの方が大かもしくは配列要
素ｂと等しい場合には次のサイクルへ移行し、
配列要素ｂの方が大の場合には次の操作へ進
む。

配列要素ａを配列要素の格納領域Ｂへ書き込
む。

配列要素ｂを配列要素の格納領域Ａへ書き込
む。

以上のからの操作において、からが比
較操作であり、およびが置換操作である。第
１図に示した手順では、サイクルT₀ではD₀およ
びD₁を上記操作におけるＡおよびＢとし、以下
同様にサイクルT₁ではD₁およびD₂をＡおよびＢ
として逐次的に処理を進める。図中、丸で囲んだ
配列要素は比較操作の対象であることを示してい
る。また、矢印を付記した２個の配列要素は置換
操作が行われたことを示している。処理がD₄お
よびD₅に対するサイクルまで進んだならば、D₀
およびD₁に対するサイクルへもどつて、再び同
様の処理を繰り返す。D₀およびD₁に対するサイ
クルからD₄およびD₅に対するサイクルを繰り返
し行う過程で、置換操作が一度も行われなければ
D₄およびD₅に対するサイクルT_l-1をもつて本ソ
ート処理は完了し、D₀からD₅の配列要素の格納
領域には配列要素６，５，４，３，２，１が降順
に並べ替えられて配列されている。

以上説明した第１図の手順では、処理が完了す
るまで無条件に処理を進めるため、一般に配列要
素数がｍ個の場合に全処理に要するサイクル数ｌ
は、ｌ＝ｍ×（ｍ−１）となり、配列要素数が増大すると処理時間はほぼ
２乗に比例して増大する難点があつた。一方、こ
うした難点を緩和するために、置換操作が完了し
たと推定されるサイクルを省略する手順も知られ
ているが、一般に逐次的なソート処理を行うかぎ
り、完了までに要するサイクル数ｌは、ｌ＝ｍ×log₂m 以下にはできず、やはり配列要素数が大量の場
合には、極めて長い処理時間を必要としていた。

そこで、逐次的なソート処理における難点を解
決する従来技術として、専用のソート処理装置を
用いて前記の第１図で説明した手順におけるD₀
およびD₁に対するサイクルからD₄およびD₅に対
するサイクルの比較操作と置換操作とをそれぞれ
並列に実行する方法が既知である。本方法では、
配列要素１個のビツト数がｉビツトである場合、
２個の配列要素に対してこれらを保持するｉビツ
トのレジスタ２個とｉビツトの比較器１個を割り
当てる。従つて、一般に2n個のレジスタｎ個の
比較器からなるソート処理装置では、ｍ≦2n の関係にあるｍ個の配列要素のソート処理を実行
できる。本ソート処理装置は、電子計算機の付属
装置として使用するため、具体的にソート処理を
行うに当つては、電子計算機のメモリ等に予めソ
ート処理の対象である複数個の配列要素を保持し
ておき、データ転送路を介して配列要素を本ソー
ト処理装置へ順次入力し、次いでソート処理がな
された配列要素を順次出力して同じくデータ転送
路を介して元のメモリ等に整列して保持する。ソ
ート処理の手順における置換操作と比較操作は、
前記のレジスタにｍ個の配列要素を順次入力し、
次いで出力する操作と同期して実施することが原
理的に可能なため、ソート処理完了までに必要な
サイクル数ｌは、ｌ＝2m となる。

このように、従来のソート処理装置では、配列
要素１個当りのビツト数がデータ転送路のベツト
幅と同じかもしくは小さい場合に、逐次的なソー
ト処理に比べて極めて高速にソート処理を行うこ
とができる。しかし、配列要素１個当りのビツト
数が、ソート処理装置を構成しているレジスタお
よび比較器のビツト幅ｉを超える場合には、ソー
ト処理を行えない問題があつた。また、この問題
を解決するため、レジスタおよび比較器のビツト
幅ｉを大きくした場合には、ソート処理装置の回
路量が膨大になるにもかかわらず、ソート処理の
速度はデータ転送路のビツト幅と転送サイクルで
決まるため、装置としての価格性能比が低下する
問題があつた。現用の電子計算機のデータ転送路
は、８ビツトから32ビツト程度であるため、従来
のソート処理装置の適用範囲も配列要素１個当り
のビツト数が８ビツトから32ビツト程度の数値デ
ータのソート処理を主としていた。しかし、今
日、電子計算機による情報処理の需要が数値デー
タのみならず文章等の文字データへ拡大するにつ
れて、配列要素１個が数百ビツトであつても効率
良くソート処理を行える拡張性のあるソート処理
装置が望まれていた。

本発明は、かかる従来技術の問題を除去するた
め、それぞれ独立して読み出し動作および書き込
み動作が可能な２個のメモリと、比較器と２個の
フラグレジスタを少くとも具備したユニツトの複
数個でソート処理装置を構成したことにより、前
記ソート処理のサイクル１回における比較操作の
回数および置換操作と等価な転送操作の回数を配
列要素のビツト数に応じて任意に設定可能にし、
かつこれら比較操作および転送操作を並列実行可
能にしたことを特徴とし、その目的はデータベー
スの検索など配列要素のビツト数が極めて大きい
場合のソート処理に適するソート処理装置を提供
することにある。

以下、本発明を実施例を参照して詳細に説明す
る。

第２図は、本発明の一実施例であるソート処理
装置の構成図である。本ソート処理装置は、複数
個のユニツトをユニツト間データ転送路により直
列接続した構成を有し、電子計算機の付属装置と
して使用する。図中、U₀からU_o-1を付記した１
はユニツト、２はユニツト間データ転送路、３お
よび４はそれぞれ配列要素の保持手段である第１
のメモリおよび第２のメモリ、５は２個の配列要
素の大小関係の判定手段である比較器、６および
７はそれぞれ比較器により発生する判定結果の保
持手段である第１のフラグレジスタおよび第２の
フラグレジスタである。また、ユニツトU₀から
U_o-1を直列接続しているユニツト間データ転送
路２の両端に付記したBLおよびBRは、それぞれ
入出力端子である。ユニツト１の各々における第
１のメモリ３および第２のメモリ４は、それぞれ
読み書きビツト幅がｉビツト（ｉ≧１整数）で容
量がｉ×ｊビツト（ｊ＞１整数）のランダムアク
セスメモリ（RAM）である。これら第１のメモ
リ３および第２のメモリ４は、それぞれMA₀か
らMA_j-1およびMB₀からMB_j-1で示す各ｉビツト
の格納領域と、DECで示すデコーダと、Ｉ／Ｏ
で示す入出力回路とから構成され、１回の読み出
し動作および書き込み動作においてデコーダ
DECで指定する格納領域に対して配列要素のｉ
ビツト分をそれぞれ独立に読み書きするととも
に、入出力回路Ｉ／Ｏを介してこれらのメモリを
含むユニツトに接続している２方向のビツト幅ｉ
ビツトのユニツト間データ転送路の一方をそれぞ
れ独立に選択して配列要素のｉビツト分を送出す
ること、あるいは受入することが可能である。ま
た、入出力回路Ｉ／Ｏでは、読み出した配列要素
のｉビツト分をユニツト間データ転送路へ送出せ
ずに比較器５へ入力することと、受入した配列要
素のｉビツト分を格納領域へ書き込むとともに比
較器５へ入力することが可能である。比較器５は
演算ビツト幅がｉビツトであり、２個の配列要素
のｉビツト分について大小関係を判定する機能を
有している。比較器による判定結果は１ビツトの
フラグ情報として第１のフラグレジスタ６に保持
することができる。また、このフラグ情報は第１
のフラグレジスタ６から第２のフラグレジスタ７
へ保持し替えることができ、この第２のフラグレ
ジスタのフラグ情報によつて第１および第２のメ
モリの入出力回路Ｉ／Ｏの動作を制御できる。

以上説明した本発明のソート処理装置の構成に
おいて、ｉおよびｊは先に述べた範囲で任意の値
をとることが可能であるが、本実施例ではｉが
８、ｊが１６の場合を説明する。なお、第２図で
はユニツトを構成する回路のブロツク構成と配列
要素ならびにフラグ情報の伝搬路を示し、制御系
の詳細は別図にて説明する。

第３図ａおよびｂは、第２図に示した本発明の
ソート処理装置の動作原理図である。本図では、
３個のユニツトU₀からU₂を用いて、４桁の数字
からなる配列要素６個を降順にソート処理する場
合を例として、ソート処理の各サイクルにおける
配列要素の動きと判定結果の状態を示している。
配列要素は、各桁を８ビツトのASCIIコードで記
述した文字データであり、配列要素１個当りのビ
ツト数は８×４ビツトである。従つて、本数では
個々のユニツトを説明に必要な第１のメモリ３お
よび第２のメモリ４と第１のフラグレジスタ６お
よび第２のフラグレジスタ７のみをシンボル化し
て示し、残りを省略している。また、第１のメモ
リ３および第２のメモリ４においても上記の配列
要素の保持に必要なそれぞれ４個の格納領域
MA₀からMA₃およびMB₀からMB₃のみを示し、
残りを省略している。T₀からT₁₁はソート処理の
サイクルを表わしている。本ソート処理装置で
は、配列要素数がｍ個の場合、ソート処理完了ま
でに必要なサイクル数ｌは、ｌ＝2m で与えられる。また必要な最小ユニツト数ｎは、ｎ≧ｍ／２で与えられる整数である。従つて、第３図ａおよ
びｂでは配列要素数ｍが６個の場合を示している
ため、ソート処理のサイクル数ｌは12回となり
T₀からT₁₁でソート処理を完了できる。また、ユ
ニツト数ｎは３個あれば十分であり、U₀からU₂
のみを示している。

次に本ソート処理装置を動作させるには、初期
状態において、全てのユニツトの第１のメモリ３
および第２のメモリ４には配列要素の最小値であ
る“0000”を書き込んでおく。この際、格納領域
MA₀からMA₃およびMB₀からMB₃には、それぞ
れ最下位桁から最上位桁に対応して配列要素を分
割した小要素すなわち前述の配列要素のｉビツト
（８ビツト）分である“０”が書き込まれる。ま
た、全てのユニツトの第１のフラグレジスタ６お
よび第２のフラグレジスタ７には、判定結果であ
る１ビツトのフラグ情報のうち“０”を書き込ん
でおく。また、ソート処理の対象である配列要素
は、本ソート処理装置が付属している電子計算機
のメモリ等に定義した格納領域D₀からD₅に保持
しておく。なお、本図ではユニツト外に配列要素
を列記したことをもつて、かかる状態を表わして
いる。ソート処理を行うT₀からT₁₁のサイクルの
うちT₀からT₅は入力モードで、T₆からT₁₁は出
力モードで動作させる。すなわち、本ソート処理
装置では必要なソート処理のサイクル2m回のう
ち、前半のｍ回は入力モードで、後半のｍ回は出
力モードで動作させる。入力モードならびに出力
モードの各サイクルでは、本図のソート処理の例
では、転送操作と比較操作をそれぞれ４回、全て
のユニツトで同期して並列に実施する。t_S0から
t_S3およびt_C0からt_C3は、それぞれ４回の転送操作
および比較操作を実施するタイミングを示してい
る。本ソート処理装置では、各回の転送操作と比
較操作のタイミング、t_S0とt_C0，t_S1とt_C1，t_S2と
t_C2，t_S3とt_C3のそれぞれは時間的に重畳して設定
することが可能であり、転送操作と比較操作を並
列に実施できる。

入力モードで動作させるT₀からT₅の各サイク
ルでは、第２図に示した入出力端子BLから、各
サイクル当り１個の配列要素を入力する。この
際、配列要素を桁ごとに分割した小要素を単位と
して、最下位の桁から順に転送操作のタイミング
t_S0，t_S1，t_S2，t_S3に同期して入力する。入力モー
ドにおける転送操作と比較操作では、各ユニツト
は次に述べる動作を行う。

（転送操作）第２のフラグレジスタ７にフラグ情報として保
持している判定結果を参照し、判定結果が“０”
である場合には、t_S0，t_S1，t_S2，t_S3のタイミング
に対応して第１のメモリ３の格納領域MA₀，
MA₁，MA₂，MA₃のうち１個を選択し、判定結
果が“１”である場合には、同様に第２のメモリ
４の格納領域MB₀＋MB₁，MB₂，MB₃のうち１
個を選択して、保持している配列要素の小要素を
読み出して２方向の系のユニツト間データ転送路
２のうち右側の系へ送出するとともに左側の系か
ら配列要素の小要素を受入して書き込み保持す
る。

（比較操作） t_C0，t_C1，t_C2，t_C3のタイミングに対応して、第
１のメモリ３の格納領域MA₀，MA₁，MA₂，
MA₃と第２のメモリ４の格納領域MB₀，MB₁，
MB₂，MB₃のうちそれぞれ１個を選択し、保持
している配列要素の小要素を読み出して比較器５
により大小関係を判定する。この際、２個の格納
領域のうち一方は、前記転送操作において選択さ
れているため、受入した配列要素の小要素を保持
するとともに比較器５へ読み出して入力する。他
方は、ユニツト間データ転送路２とは切離して比
較器５へのみ読み出して入力する。比較器５で
は、第１のメモリ３側が大の場合には判定結果
“１”を発生し、第２のメモリ４側が大の場合に
は判定結果“０”を発生する。この判定結果は比
較操作が終了する時点で第１のフラグレジスタへ
フラグ情報として書き込み保持する。第１のメモ
リ３側と第２のメモリ４側が等しい場合には判定
結果を発生せず、第１のフラグレジスタ６への書
き込みを行わない。

入力モードの各サイクルでは、以上説明した転
送操作と比較操作をそれぞれ４回実施した時点で
第１のフラグレジスタ６には第１のメモリ３と第
２のメモリ４に保持している２個の配列要素全体
についての判定結果がフラグ情報として保持され
ている。そこで、この時点をもつてサイクルを終
了し、第１のフラグレジスタ６に保持しているフ
ラグ情報を第２のフラグレジスタ７へ保持し替え
る操作を行うとともに、第１のフラグレジスタ６
に“０”を書き込んで初期化する。

以上説明した入力モードのサイクルT₀からT₅
を実施することにより、６個の配列要素は並列に
比較操作と置換操作と等価な転送操作を受けつつ
ユニツトU₀からU₂の第１のメモリ３と第２のメ
モリ４に保持される。なお、入力モードでは、転
送操作に同期して入出力端子BRから配列要素の
最小値の小要素である“０”が順次出力される。

出力モードで動作させるT₆からT₁₁の各サイク
ルでは、入出力端子BRから、各サイクル当り１
個の配列要素の最小値“0000”を入力する。この
際、この最小値を桁ごとに分割した小要素の
“０”を転送操作のタイミングt_S0，t_S1，t_S2，t_S3に
同期して入力する。出力モードにおける転送操作
と比較操作では、各ユニツトは次に述べる動作を
行う。

（転送操作）第２のフラグレジスタ７にフラグ情報として保
持している判定結果を参照し、入力モードとは逆
に、判定結果が“１”である場合には、t_S0，t_S1，
t_S2，t_S3のタイミングに対応して第１のメモリ３
の格納領域MA₀，MA₁，MA₂，MA₃のうち１個
を選択し、判定結果が“０”である場合には、同
様に第２のメモリ４の格納領域MB₀，MB₁，
MB₂，MB₃のうち１個を選択して、保持してい
る配列要素の小要素を読み出して２方向の系のユ
ニツト間データ転送路２のうち左側の系へ送出す
るとともに右側の系から配列要素の小要素を受入
して書き込み保持する。

（比較操作）入力モードの場合と同じ動作を行う。出力モー
ドの各サイクルでは、入力モードと同様に、以上
説明した転送操作と比較操作をそれぞれ４回実施
した時点をもつてサイクルを終了し、第１のフラ
グレジスタ６にフラグ情報として保持している判
定結果を第２のフラグレジスタ７へ保持し替える
操作を行うとともに第１のフラグレジスタ６に
“０”を書き込んで初期化する。

以上説明した出力モードのサイクルT₆からT₁₁
を実施することにより、６個の配列要素は並列に
比較操作と置換操作と等価な転送操作を受けつ
つ、入出力端子BRから最大値の配列要素から降
順にソート処理がなされて出力される。この際、
各サイクル当り１個の配列要素が、桁ごとに分割
した小要素すなわち配列要素のｉビツト（８ビツ
ト）分を単位として、最下位の桁から順に転送操
作のタイミングt_S0，t_S1，t_S2，t_S3に同期して出力
される。出力された配列要素は、電子計算機のメ
モリ等に定義した格納領域D₀からD₅に順次書き
込むことにより、ソート処理が完了した状態で保
持される。

以上のソート処理の動作原理を説明した第３図
ａおよびｂでは矢印を付記した配列要素の小要素
は転送操作の結果矢印の先が示す格納領域へ移動
したことを示している。また第１のフラグレジス
タ６の内容は比較操作における判定結果を書き込
んだ状態を示している。

第４図は、第２図に示した本発明のソート処理
装置のユニツト１個の構成図である。本図では、
第３図ａおよびｂで説明したソート処理を行うに
必要な制御系の詳細を示す。図中、２はユニツト
間データ転送路、３は第１のメモリ、４は第２の
メモリ、５は比較器、６は第１のフラグレジス
タ、７は第２のフラグレジスタである。また、図
中の論理シンボル８はAND回路、９はOR回路、
１０はインバータである。第１のメモリ３および
第２のメモリ４のそれぞれは、格納領域MA₀か
らMA_j-1および格納領域MB₀からMB_j-1で示す格
納領域と、DECで示すデコーダと、Ｉ／Ｏで示
す入出力回路で構成されている。デコーダDEC
は、アドレス信号ADにより格納領域MA₀から
MA_j-1および格納領域MB₀からMB_j-1のうち各１
個を選択する。本実施例ではｊが１６であるた
め、アドレス信号ADはAD₀からAD₃の４ビツト
からなつている。入出力回路Ｉ／Ｏは、前記のデ
コーダDECで選択される格納領域に対する読み
出し動作および書き込み動作を制御するＲ／Ｗで
示す読み書き制御回路と、左右２系のユニツト間
データ転送路２とユニツト内データ転送路BAお
よびBBとを接続するSWで示すスイツチ回路と、
これら読み書き制御回路Ｒ／Ｗおよびスイツチ回
路SWを制御する論理回路とで構成されている。
入出力回路Ｉ／Ｏを制御する信号は、IMが入力
モード信号、OMが出力モード信号、MRが読み
出し信号、MWが書き込み信号、FL₂が第２のフ
ラグレジスタ７に保持しているフラグ情報、
WE_aおよびWE_bが書き込み制御信号、RSがリセ
ツト信号である。これらのうち入力モード信号
IMおよび出力モード信号OMは、入力モードお
よび出力モードのソート処理のサイクルにおいて
それぞれ“１”とする。読み出し信号MRおよび
書き込み信号MWは、ソート処理のサイクルの前
半および後半においてそれぞれ“１”とする。リ
セツト信号RSは、ソート処理の開始前に“１”
に設定してアドレス信号ADを歩進することによ
り、格納領域MA₀からMA_j-1および格納領域
MB₀からMB_j-1に小要素の“０”を書き込んで
初期化する際に用いる。書き込み制御信号WE_a
およびWE_bは、“１”の場合には読み書き制御回
路Ｒ／Ｗが書き込み動作を行い、“０”の場合に
は読み出し動作を行う。

以上説明した回路と信号により、入力モードで
はフラグ情報FL₂が“０”の場合には第１のメモ
リ３が転送操作の対象となり、読み出し信号MR
が“１”となる期間に格納領域MA₀からMA_j-1
のうちアドレス信号ADで選択される１個から配
列要素の小要素が読み書き制御回路Ｒ／Ｗを介し
てユニツト内データ転送路BAへ読み出され、ス
イツチ回路SWを介して右側のユニツト間データ
転送路２へ送出される。次いで書き込み信号MW
が“１”となる期間では、左側のユニツト間デー
タ転送路２からスイツチ回路SWを介してユニツ
ト内データ転送路BAへ配列要素の小要素が受入
され、読み書き制御回路Ｒ／Ｗを介して前記と同
じ格納領域へ書き込まれる。一方、比較操作は書
き込み信号MWが“１”である期間に行われ、ユ
ニツト内データ転送路BAからは前記の転送操作
で受入した配列要素の小要素が比較器５へ入力
し、ユニツト内データ転送路BBからは格納領域
MB₀からMB_j-1のうち転送操作と同一のアドレ
ス信号ADで選択された１個から読み出された配
列要素の小要素が比較器５へ入力する。入力モー
ドでフラグ情報FL₂が“１”の場合には、逆に第
２のメモリ４が転送操作の対象となる。出力モー
ドでは、入力モードとは逆にフラグ情報FL₂が
“０”の場合には第２のメモリ４が転送操作の対
象となり、“１”の場合には第１のメモリ３が転
送操作の対象となる。配列要素の小要素は左側の
ユニツト間データ転送路２へ送出され、右側のユ
ニツト間データ転送路から受入される。

第５図は、第２図および第４図に示した本発明
のソート処理装置のユニツト１内における比較器
５と第１のフラグレジスタ６および第２のフラグ
レジスタ７の回路図である。図中の論理シンボル
は、８がAND回路、９がOR回路、１０がインバ
ータ、１１が排他的OR回路である。なお、８の
出力に１０が接続した１２はNAND回路である。
図中の信号は、BA₀からBA_i-1およびBB₀から
BB_i-1がそれぞれユニツト内データ転送路BAお
よびBBにより付与される配列要素の小要素すな
わち配列要素のｉビツト分、F₀が判定結果であ
るフラグ情報、SEがセツトイネーブル信号、FS₁
が第１のフラグレジスタのセツト信号、FR₁が第
１のフラグレジスタ６のリセツト信号、FL₁が第
１のフラグレジスタに保持しているフラグ情報、
FS₂は第２のフラグレジスタのセツト信号、RS
は第１のメモリ３および第２のメモリ４と共通な
第２のフラグレジスタ７のリセツト信号、FL₂が
第２のフラグレジスタ７に保持しているフラグ情
報である。比較器５では、配列要素BA₀から
BA_i-1と配列要素BB₀からBB_i-1の大小関係を下
位の桁から比較し、配列要素BA₀からBA_i-1の方
が大である場合にはフラグ情報F₀が“１”とな
り、逆に小である場合にはフラグ情報F₀が“０”
となる。また、配列要素BA₀からBA_i-1と配列要
素BB₀からBB_i-1とが等しい場合にはセツトイネ
ーブル信号SEが“０”となる。第１のフラグレ
ジスタ６では、リセツト信号FR₁が“１”の場合
にフラグ情報FL₁が“０”となるようにリセツト
される。また、セツトイネーブル信号SEが“１”
でかつセツト信号FS₁が“１”である場合に比較
器５からのフラグ情報F₀がそのままフラグ情報
FL₁としてセツトされる。第２のフラグレジスタ
７では、リセツト信号RSが“１”である場合に
フラグ情報FL₂が“０”となるようにリセツトさ
れ、セツト信号FS₂が“１”である場合に第１の
フラグレジスタ６のフラグ情報FL₁がそのまま第
２のフラグレジスタ７のフラグ情報FL₂としてセ
ツトされる。

第６図は、第２図、第４図、第５図に示した本
発明のソート処理装置を第３図ａおよびｂに示し
たソート処理の例に従つて動作させる際のタイム
チヤートである。本図は第３図ａに示したサイク
ルT₀にならつて１サイクル分を示している。図
中、AD₀はアドレス信号の最下位１ビツト分、
MRは読み出し信号、MWは書き込み信号、FR₁
は第１のフラグレジスタ６のリセツト信号、FS₁
およびFS₂はそれぞれ第１のフラグレジスタ６お
よび第２のフラグレジスタ７のセツト信号であ
る。これらの信号は「Ｈ」が“１”、「Ｌ」が
“０”に対応している。

以上説明したタイムチヤートにおける各信号は
入力モードと出力モードとで共通である。なお、
本図では配列要素が４桁の数字の場合の１サイク
ル分のタイムチヤートを示したが、第２図の本発
明のソート処理装置では各ユニツトの第１のメモ
リ３および第２のメモリ４の容量を８×16ビツト
としたため、配列要素が最大16桁の場合までソー
ト処理可能である。この際、転送操作と比較操作
それぞれ16回をもつて１サイクルを構成する。一
般には、第２図の本発明のソート処理装置におい
て、第１のメモリ３および第２のメモリ４のそれ
ぞれの読み書きビツト幅をｉビツト（ｉ≧１整
数）で容量をｉ×ｊビツト（ｊ≧１整数）とし、
比較器５のビツト幅ならびにユニツト間データ転
送路２の１系当りのビツト幅を少くともｉビツト
とし、転送操作と比較操作とをそれぞれｋ回（ｊ
≧ｋ≧１整数）実施し、それぞれｋ回の転送操作
と比較操作とが終了した時点でユニツトの各々に
おいて第１のフラグレジスタ６に保持している判
定結果を第２のフラグレジスタ７へ保持し替える
操作を実施することをもつてソート処理のサイク
ル１回とし、少くとも2m回（2n≧ｍ＞１，ｎは
ユニツト数）のサイクルを実施することをもつて
ｉ×ｋビツトの配列要素ｍ個のソート処理を行う
ことができる。

以上説明した本発明の実施例では、第３図ａお
よびｂをもつて降順のソート処理の動作例を示し
たが、動作条件を変更することによつて昇順のソ
ート処理を行うことも可能である。昇順のソート
処理の場合には、初期状態において各ユニツトの
第１のメモリ３および第２のメモリ４に配列要素
の最大値を書き込んでおき、入力モードでは大き
な値の配列要素を右の方のユニツトへ転送し、出
力モードでは小さな値の配列要素を左の方のユニ
ツトへ転送する。

また、本実施例では入出力端子BRから配列要
素を入力し、同じ入出力端子BRからソート処理
がなされた配列要素を出力する場合を示したが、
従来技術のソート処理装置で既知である降順のソ
ート処理と昇順のソート処理を相補的に実施する
方法や、入力モードのみでソート処理を行う等の
方法についても本発明のソート処理装置において
実施することができる。さらに、第２図に示した
本発明のソート処理装置をＲ台（Ｒ＞１整数）並
列接続し、Ｒ×ｉ×ｋビツトの配列要素のソート
処理を実施するソート処理装置、もしくは配列要
素のビツト数に応じて直列接続するユニツト数と
並列接続するユニツト数を可変にしたソート処理
装置も容易に構成することができる。

なお、本実施例で示した回路構成のうち、第１
のメモリおよび第２のメモリ内のデコーダDEC、
格納領域、読み書き制御回路Ｒ／Ｗ、スイツチ回
路SWについては、市販のスタテインクRAM等
に使用されている既知の回路構成が適用できる。
また、比較器、第１および第２のフラグレジスタ
については、本実施例で示した構成の他に、算術
論理演算ユニツトALUや汎用レジスタ等を利用
することもできる。

以上実施例をもつて説明したように、本発明の
ソート処理装置では、それぞれ独立して読み出し
動作および書き込み動作が可能な第１のメモリお
よび第２のメモリと、比較器と、比較器による判
定結果を保持する第１のフラグレジスタおよび第
２のフラグレジスタとを少くとも具備したユニツ
トの複数個をもつて構成したことにより、転送操
作と比較操作とを並列に行うことができ、かつ比
較器の演算ビツト幅よりビツト数が大きい配列要
素のソート処理を効率良く行うことができるた
め、従来のソート処理装置よりも処理速度、処理
限界、装置の価格・性能比の面で利点がある。従
つて、本ソート処理装置は、データベースの検索
など、配列要素のビツト数が大きくかつ配列要素
数も膨大な処理に適用すると、類似した配列要素
を順次とり出す等のデータ操作が高速に行える効
果がある。

【図面の簡単な説明】

第１図は従来の電子計算機を利用した逐次処理
によるソート処理の原理図、第２図は本発明の一
実施例であるソート処理装置の構成図、第３図ａ
およびｂは第２図のソート処理装置の動作原理
図、第４図は第２図のソート処理装置のユニツト
の構成図、第５図は第２図および第４図のユニツ
ト内の比較器と第１および第２のフラグレジスタ
の回路図、第６図は第２図のソート処理装置の動
作説明用タイムチヤートである。１…ユニツト、２…ユニツト間データ転送路、
３…第１のメモリ、４…第２のメモリ、５…比較
器、６…第１のフラグレジスタ、７…第２のフラ
グレジスタ、８…AND回路、９…OR回路、１０
…インバータ、１１…排他的OR回路、BL，BR
…入出力端子、MA₀〜MA_j-1，MB₀〜MB_j-1…
格納領域、DECーデコーダ、Ｉ／Ｏ…入出力回
路、AD…アドレス信号、Ｒ／Ｗ…読み書き制御
回路、BA，BB…ユニツト内データ転送路、SW
…スイツチ回路、IM…入力モード信号、OM…
出力モード信号、MR…読み出し信号、MW…書
き込み信号、FL₁，FL₂…フラグ情報、WE_a，
WE_b…書き込み制御信号、RS…リセツト信号、
BA₀〜BA_i-1，BB₀〜BB_i-1…配列要素のｉビツ
ト分、F₀…判定結果を示すフラグ情報、SE…セ
ツトイネーブル信号、FS₁…第１のフラグレジス
タのセツト信号、FS₂…第２のフラグレジスタの
セツト信号、FR₁…第１のフラグレジスタ６のリ
セツト信号、AD₀…アドレス信号ADの最下位１
ビツト分。

Claims

【特許請求の範囲】

１それぞれ配列要素の保持手段であり、かつそ
れぞれ独立して配列要素のｉビツト分（ｉ≧１整
数）の読み出し動作および書き込み動作が可能な
ｉ×ｊビツト（ｊ＞１整数）の容量を有する第１
のメモリおよび第２のメモリと、演算ビツト幅が
少くともｉビツトである比較器と、第１のフラグ
レジスタおよび第２のフラグレジスタとを少くと
も具備したユニツトの複数個をユニツト間データ
転送路により直列接続した構成を有し、該ユニツ
トの各々において該第２のフラグレジスタに保持
しているフラグ情報により該第１のメモリおよび
第２のメモリの一方を選択して配列要素のｉビツ
ト分を読み出すとともに該ユニツトに接続してい
る２方向のユニツト間データ転送路の一方へ送出
し、次いで他方のユニツト間データ転送路から配
列要素のｉビツト分を受入するとともに該第２の
フラグレジスタに保持しているフラグ情報により
選択した該第１のメモリおよび第２のメモリの一
方へ書き込む転送操作と、該ユニツトの各々にお
いて該転送操作で選択した該第１のメモリおよび
第２のメモリの一方とは異なる他方から配列要素
のｉビツト分を読み出すとともに該転送操作で受
入した配列要素のｉビツト分との大小関係を該比
較器により判定して判定結果が得られた場合には
該第１のフラグレジスタにフラグ情報として保持
する比較操作とをそれぞれｋ回（ｊ≧ｋ≧１）実
施し、ｋ回目の該転送操作と該比較操作とが少く
とも終了した時点で該ユニツトの各々において該
第１のフラグレジスタに保持しているフラグ情報
を該第２のフラグレジスタへ保持し替える操作と
を実施することをもつてソート処理のサイクル１
回とし、該ソート処理のサイクルを繰り返し実施
することをもつてｉ×ｋビツトの配列要素からな
るデータのソート処理を行うように構成されたソ
ート処理装置。