JPS59189442A - ソ−テイング処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 発明の技術分野 本発明は所定の順序関係に従ってデータを並べ換えるソ
ーティング処理方式に関する。

技術の背景 計算機システムにおいては、データの集合をある順序関
係に従って並べ換えるソーティング処理が頻繁に行なわ
れている。特に情報検索では、所望のデータの検索全容
易ならしめることからソーティングが基本的な処理とな
っている。例えば、ファイルを検索する場合、ファイル
名の頭文字をアルファベットの順序関係に従ってソーテ
ィングする処理が行なわれ、情報検索を容易にしている
。

従来から、この様なソーティングを効率良く行なうため
に、ソフトウェアによるソーティングのアルゴリズムが
各種提案されている。ソーティングのステップ数はソー
ティングするデータ数ｉｎとすると、簡単な方法でｎ２
のオーダであシ、ヒープソートと称するアルゴリズムに
代表される効率の良い方法でｎＡ！０ｇ２ｎのオーダで
ある。

しかしながら、計算機システムで扱うデータ量が膨大と
な９、ｎが大きい値となると、高性能な大形計算機でも
多くの実行時間を要することになる。例えば、データ数
ｎが１万個とすると、１データ当りの平均ソーティング
ステップ数ｆｍとすればヒープソートでは約１３万×ｍ
のステップ数であり、仮に１ステツプの実行時間を１μ
ｓとしても、約１３０ｍｓＸｍの実行時間を要する。

従来技術と問題点 従来ソーティングを高速に行なうために、複数の計算機
を用いて並列処理する方法が提案されているが、この方
法では、全ての計算機がソーティングデータを格納して
いる記憶装置に同時にアクセスする必要があるなど記憶
装置の構成に制限が加わる。

一方、半導体技術の発展は著しく、シリコンの集積回路
（ＬＳＩ）の集積度は２倍／年で増大している。そこで
、ソーティングの高速化の方法として、従来のソフトウ
ェアによる高速なソーティングアルゴリズム１ＬｓＩで
置き換えるという方法がおる。

しかし、これらのアルゴリズムは多数のソーティングモ
ジュール間で通信を必要とするためモジュール間の配線
が複雑となり、また、各モジュールが必らずしも同一構
成とはならないため多品種のＬＳＩ　ｋ必要とするなど
、ＬＳＩと整合しないという問題があった。

発明の目的 本発明は２個のレジスタと１個の比較回路からなる同一
構成のソーティングモジュールｋｎ数個亘列接続して並
列に動作させ、各ソーティングモジュールはソーティン
グデータを隣接するソーティングモジュールへ伝達する
処理と、２個のデータを所定の順序関係となるようにレ
ジスタへ再配置する処理とを両隣接ソーティングデ−タ
にっいて交互に繰返すことｆ：特徴とし、その目的は同
一構成の繰返し構造からなる高速ソーティング処理方式
を提供することにある。以下図面を用いて本発明の詳細
な説明する。

発明の実施例 第１図は本発明の実施例であシ、ソーティングモジュー
ルのブロック図全示している。１は２個のデータをソー
ティングするソーティングモジュールであや、レジスタ
回路（ＲＡ、ＲＢ）　　２　、３、選択回路（８Ａ、Ｓ
Ｂ）　４　、５、比較回路６、制御回路７とから構成さ
れる。レジスタ回路２．３はそれぞれ選択回路４，５で
選択したデータを保持するレジスタである。また、レジ
スタ回路２，３は同一のクロック信号で動作するとする
。選択回路４は双方向データ線（８ＤＡ）８及び入力デ
ータ線（ＤＡ）９から入力されるデータとレジスタ回路
２，３で保持しているデータとを制御線球の状態に基づ
いて選択し、レジスタ回路２に出力する。選択回路５は
双方向データ線（ＳＤＢ）１０及び入力データ線（ＤＢ
）１１かも入力されるデータとレジスタ回路２，３で保
持しているデータと全制御線１３の状態に基づいて選択
し、レジスタ回路３に出力する。比較回路６はレジスタ
回路２．３で保持している２個のデータの間で比較を行
ない、比較信号１４ヲ出力する。ここで比較回路６は正
整数の大小関係を比較し、レジスタ回路２および３の出
力データにおいてＲＡ〉ＲＢであれば、たとえば論理的
に「０」の比較信号（８Ｗ）　１４’ｋＳＲＡ＜ＲＢで
あれば論理的に「１」の比較信号（ＳＷ）１４’ｌｒ出
力する。制御回路７は制御入力線（ＬＯＡＤ　、　Ｒ／
Ｌ　、　５ＯＲＴの３本からなる）１５と比較信号（Ｓ
Ｗ）１４ｔ−人力し、選択回路４．５を制御する制御線
シ、１３ヲ出力する。

第２図は第１図におけるソーティングモジュールの動作
金示している。５Ｗ＝ＯはＲＡ≧ＲＢ、５Ｗ−１はＲＡ
　＜　ＲＢにおけるそれぞれの比較信号の論理値を示す
。制御入力線ＬＯＡＤが「１」のとき、選択回路（ＳＡ
、ＳＢ）　４　、５はそれぞれ入力データ線９．１１か
らのデータを選択し、レジスタ回路（ＲＡ。

ＲＢ）　２　、３は前記選択されたデータを保持する。

制御入力線５ＯＲＴとＲ／Ｌは制御入力線ＬＯＡＤが「
Ｏ」のとき有効な信号線となる。制御人力＃５ＯＲＴが
「０」のとき、双方向データ線（８ＤＡ、５ＤＢ）　８
　、１０をを介して、レジスタ回路（ＲＡ、ＲＢ）　２
　、３のデー、りをシフトすることを指定する。ここで
、制御入力線Ｒ／Ｉ、が「１」でおれば、双方向データ
線８，１０はそれぞれ入力データｆｓ、出力データ線と
して動作し、双方向データ線レジスタ回路（ＲＡ、ＲＢ
）２　、３、双方向データ線（ＳＤＲ）１０という順番
に直列接続される。そして、双方向データ線（ＳＤＡ）
　８のデータがレジスタ回路（ＲＡ）　２へ、レジスタ
回路（８人）２のデータがレジスタ回路（ＲＢ）　３へ
、レジスタ回路（ＲＢ）　３のデータが双方向データ線
（ＳＤＲ）１０へとシフトする。この処理を右シフト処
理と呼ぶ。

また、制御入力線Ｒ／Ｉ、が「０」であれば、双方向デ
ータ線８，１０はそれぞれ出力データ線、入力データ線
として動作し、前記処理とは逆に双方向データ線（８Ｄ
Ｂ）１０、レジスタ回路（ＲＢ、ＲＡ）　３　、２、双
方向データ線（ＳＤＡ）　８という順番に直列接続され
る。そして双方向データ線（ＳＤＲ）１０のデータがレ
ジスタ回路（ＲＢ）　３へ、レジスタ回路（ＲＢ）　３
のデータがレジスタ回路（ＲＡ）　２へ、レジスタ回路
（ＲＡ）　２のデータが双方向データ線（ＳＤＡ）　８
へとシフトする。この処理を左シフト処理と呼ぶ。制御
入力線８０ＲＴがｒｌＪのとき、比較回路６の比較結果
に基づいてレジスタ回路（ＲＡ、ＲＢ）　２　、３のデ
ータを並べ換える。ここでは、小さい値のデータがレジ
スタ回路（ＲＡ）　２に保持されると仮定する。

したがって比較の結果、レジスタ回路（ＲＡ）　２のデ
ータの値がレジスタ回路（ＲＢ）　３のデ・−夕の値よ
り大きいかあるいは等しいとき、データの並べ換えが行
なわれ、レジスタ回路（ＲＢ）　３のデータがレジスタ
回路（ＲＡ）　２に、レジスタ回路（ＲＡ）２のデータ
がレジスタ回路（ＲＢ）　３に交換されて保持される。

また、比較の結果、レジスタ回路（８人）２のデータの
値がレジスタ回路（ＲＢ）　３のデータの値より小さい
とき、データの並べ換えは行なわれず、両レジスタ回路
は元のデータを保持する。以上述べた様なデータを比較
し、並べ換える処理を交換処理と呼ぶこととする。

第３図は本発明の実施例であシ、第２図の動作を行う第
１図の構成のソーティングモジュール（以下モジュール
と略記する。）　（Ｓｉ、　　ｉ＝１〜ｌ）全１佃直列
接続して構成したソーティング処理装置である。モジュ
ール（Ｓｉ）　１の双方向データ線８は隣接のモジュー
ル（Ｓｉ−ｔ）”の双方向データ線１０と接続し、モジ
ュール（Ｓｉ）１の双方向データ線ｌＯは反対側の隣接
モジュール（Ｓｉ＋１）１の双方向データ線８と接続す
る。３本の制御入力線は全てのモジュールの制御回路７
（図は省略）と接続し、全てのモジュールを共通して制
御する。両端のモジュール（Ｓｉ）　１と（８７）　１
の双方向データ線８゜１０からはソーティング処理され
たデータが出力される。１６はモジュール１に対応して
設けたデータ処理モジュール（ＰＥｉ）１６であシ、演
算、記憶等通常の計算機の処理を行なう。モジュール（
Ｓｉ）　１とデータ処理モジュール（ＰＥｉ）１６とは
入力データ線９．１１とで接続される。したがって、デ
ータ処理モジュール（ＰＥｔ）ｘ６でのデータ処理後、
ソーティングの必要なデータは入力データ線９．ｉｉ’
ｌ介して対応するモジュール（Ｓｉ）１に入力しレジス
タ回路２，３（図示省略）に保持される。１７　、１８
は制御入力線Ｐ／Ｌで制御するレジスタ回路（Ｒ１，Ｒ
２）であ）、それぞれモジュール（８１）１の双方向デ
ータ線８．モジュール（８７）　１の双方向データ線１
ｏに接続される。レジスタ回路（Ｒ１）１７はデータの
左シフト処理でモジュール（Ｓｌ）１の双方向データ線
８よシ出力されるデータを保持し、データの右シフト処
理では、レジスタ回路（Ｒ１）１７のデータをモジュー
ル（Ｓｌ）　１に双方向データ線８を介して入力する。

レジスタ・回Ｍ（Ｒ２）１．８はデータの右シフト処理
テモジュール（ＳＡ）　１の双方向データ線１０よシ出
カされるデータを保持し、左シフト処理では、レジスタ
回路（Ｒ２）１８のデータをモジュール（Ｓｌ）１に双
方向データ線１０ヲ介して入力する。通常、ソーティン
グ処理の初期状態においては、レジスタ回路（Ｒ１゜Ｒ
２）　１７　、１８のどちらが一方にはソーティング処
理に影響を与えない最／Ｆ値あるいは最大値がセットさ
れる。この場合、レジスタ回路は保持データがソーティ
ング処理過程において変化しないので、必らずしもフリ
ップフロップで構成した回路テある必要はない。

また、全てのモジュールは同一のクロックによシ同期し
て動作する構成とする。したがって、データ処理モジュ
ールからのデータの取シ込み、データの右シフト、左シ
フト、交換の谷処理は全てのモジュールが同時に行なわ
れる。

第４図は第３図のソーティング処理装置において、モジ
ュールが４個のときの動作例を示している。第４図にお
いて、レジスタ回路（Ｒ１）１７は初期状態として正整
数の最小値ゼロがセットされると仮定する。フェーズＴ
ｉにおける１ｏではデータの右シフトあるいは左シフト
処理を行ない、ｔｌではデータの交換処理を行なう。ま
た、第４図は谷フェーズのｊＧ＋ｈにおける制御入力線
ＬＯＡＤ、　５ＯＲＴ　。

Ｒ／Ｌの状態を示している。まず、ＬＯＡＤを「１」と
して、モジュールに対応するデータ処理モジュールより
ソーティングするデータを同時に取カ込む。

フェーズＴ１のｔｏでは谷モジュールのデータを隣接モ
ジュールに右シフトする。ｔｌでは各モジュール同時に
左側のレジスタ内のデータが小さい値と々るようにデー
タの交換処理を行なう。フェーズＴＱのＴｏでは各モジ
ュールのデータを反対側の隣接モジュールに左シフトす
る。ｔｌでは前記と同様にデータの交換処理を行なう。

以下同様に右シフト／交換、左シフト／交換管＜９返し
行ない、フェーズＴ８でソーティング処理が終了する。

その後、モジュールＳ１の双方向データ線８よシデータ
金読出せば非減少順にソーティングされたデータが得ら
れる。またモジュールＳ４の双方向データ線１０よシデ
ータを読出せば非増大順にソーティングされたデータが
得られる。

また、第１図の比較回路６によるデータの比較の結果、
第１図のレジスタ回路２に大きい値のデータを保持する
ように構成すれば、モジュールＳｌの双方向データ線８
からは非増大順にソーティングされたデータが得られる
。

第３図におけるソーティング処理装置の動作を第５図ａ
＋ｂ　ｋ用いて、一般的に説明する。モジュール５１（
ｔ＝ｉ、ｚ、・・・、））のレジスタ回路２．３全それ
ぞれＰＡ　１　＊　ＲＢ　ｉと表わし、ＲＡｉ、ＲＢｉ
の内容全それぞれ５（ＲＡｉ）、　５（ＲＢｉ）とする
。ｔｎｉ、７エーズＴｋのｔｌにおいて５（ＰＡｉ）＝
αｌ　、　５（ＲＪ）＝βｉとすると、αｌとβｉの大
小関係は明らかにα１くβｉである。フェーズＴｋ＋１
で右シフト処理、フェーズＴｌ（−＋−ｓ＋で左シフト
処理を行なうとし、そのときのモジュールＳｉのレジス
タＲＡｉ、ＲＪの内容を第５図ａに示す。フェーズＴｌ
（＋ｓ　の右シフト処理で隣接βｉ７ｔ　　となるので
、７エーズＴｌ（＋ｚの左シフト／交換においてもβｉ
−１はモジュールＳｉにとどまる。

βｉ−１＜”ｉであれば、７エーズＴｌ（＋１　＋７）
　ｔ１テ５（ＲＢｉ）＝β１−ｔとなるので、フェーズ
Ｔｋ＋　ｓの左シフト処理でβｉ−１は元のモジュール
５ｉ−１にもどる。

このことは、モジュール内の大きい値のデータは右シフ
ト処理によりそのデータの順位に応じたモジュールまで
右シフトし、隣接モジュールに確実にシフトするのにＴ
ｋ　”　１１　Ｔｋ　＋　ｚの２フエーズを必要とする
ことを示している。

また１、フェーズＴｌ（＋ｘで左シフト処理、フェーズ
Ｔｋ＋２で右シフト処理を行なうとしたときのモジュー
ル８１のレジスタＲＡｉ、ＲＢｉの内容を第５図すに示
す。７エーズＴｌ（＋ｔの左シフト処理で隣接モジュー
ルＳｉ＋ｘよ多α１＋１が入力され、仮すにβｉ〉αｉ
＋１であればフェーズＴｋ＋１Ｏｔｌ　ｆ　５（ＲＡｌ
）−αｉ＋１となるので、　フェーズＴｋ＋ｇの右シフ
ト処理後においてもαｉ＋ｘはモジュールＳｉにとどま
る。βｉ〈αｉ＋１であれば、フェーズＴｌ（＋ｉのｔ
ｌで５（ＲＪ）＝α［＋１となるので、７エーズＴｋ＋
＋の右シフト処理でαｉ＋１は元のモジュールＳｉ＋１
にモトる。このことは、モジール内の小さい値のデータ
は左シフト処理にょシ、そのデータの順位に応じたモジ
ュールまで左シフトし、隣接モジュールに確実にシフト
するのにＴｌ（＋ｔ　、　Ｔｌ（＋ｚの２７エーズを必
要とすることを示している。

したがって、以上述べた処理ヲ＜シ返し行なうことによ
シ、データが所定の順序関係にソーティングされる。つ
ぎに、このソーティングの処理時間を求める。処理時間
が最大となるのは、モジュール５ｔ（Ｓｚ）のＲＡＩ（
ＲＢＡＩ）のデータがモジュール８７（Ｓｔ）のＲＢ７
　（ＲＡｔ　）に伝達される場合である。

すなわち、ソーティングデータの集合で最大値（最小値
）のデータがモジュール５１（８４）のＲＡ、（ＲＢｌ
）に存在するときが、最大の処理時間となる。第４図の
動作例で述べたように７工−ズＴｇｋ＋ｘで右シフト、
交換、フェーズＴｇｋで左シフト、交換の処理を行なう
と仮定する。最大値のデータがモジュール８１のＲＡ、
に存在する場合、フェーズＴ１．Ｔ２では最大値のデー
タの移動はなくフェーズＴ８から瞬接モジュールへシフ
トラ始め、２（Ｊ−１）フェーズでモジュールＩＪに伝
達する。したがって、この場合、モジュールＳ１からモ
ジュールＳｌ！に伝達するのに２１フエーズかかる。最
小値のデータがモジュール８７のＲＢＪに存在する場合
、フェーズＴｌで最小値のデータがレジスタ回路１８に
移動するため、１個のモジュールを移動する必要がある
ので同様に２１フエーズかかる。　したがって、ソーテ
ィングデータｉｎ個とすると、ソーティングの処理時間
はｎフェーズとなる。

以上、第３図のソーティング処理装置がどのように動作
するかを第４図、第５図ａ＋ｂ　ｋ用いて説明した。第
４図においては、ソーティング処理を７工−ズＴｇｋ＋
ｔで右シフト／交換、フェーズＴ２１（で左シフト／交
換としたが、これを逆にしてフェーズＴ＋に＋１で左シ
フト／交換、７工−ズＴｇ、で右シフト／交換としても
同様の動作をするのは勿論である。この場合も、ソーテ
ィングの処理時間は２Ｊ（ｎ）フェーズである。

また、各フェーズの１０でシフト処理、ｔｌで交換処理
としたが、これを逆にして、ｔｏで交換処理、１１でシ
フト処理としても同様の動作をするのは勿論である。こ
の場合のソーティング処理時間は、最大値のデータがモ
ジュールｓ１のＲＡｌにあるときについては、７エーズ
Ｔ１で最大値のデータの移動が行なわれ、最後の交換処
理でソーティングが終了するので、２（Ｊ−１）＋−フ
ェーズである。　最小値のデータがモジュールｓｌのＲ
ＢＪにあるときは、最小値のデータがレジスタ回路１８
に移動することがないので、（１−ｔ）個のモジュール
を移動すればよく、ソーティング処理時間は２（Ｊ−１
）十−フエ−ズである。

第１図のソーティングモジュールを用いた第３図のソー
ティング処理装置では、ソーティングの４！ｒ７エーズ
の処理（シフトと交換）に２クロツク必猥とする。第６
図は本発明の他の実施例であり、ソーティングの谷フェ
ーズの処理全１クロツクで処理するソーティングモジュ
ールのブロック図である。１は２つのデータをソーティ
ングするソーティングモジュールでアシ、レジスタＤｏ
　路（ＲＡ、ＲＢ）２．３、比較回路（ＣＯＭＰ）　６
、双方向データ線８゜１０、入力データ線９，１１、制
御入力線１５、選択回路（ＳＡＩ、　ＳＢＩ、　ＳＡ２
．５Ｂ２）　１９．２Ｑ、２１，２２、制御回路２３、
とから構成される。レジスタ回路２，３はそれぞれ選択
回路１９　、２０で選択したデータを保持するレジスタ
であり、同一のクロック信号で動作する。選択回路１９
は双方向データ線８，１０及び入力データ線（ＤＡ）　
　９から入力されるデータとレジスタ回路２，３で保持
しているデータとを制御線２４の状態に基づいて選択し
、レジスタ回路２に出力する。選択回路２０は双方向デ
ータ線８，１０及び入力データ線（１）Ｂ）　１１から
入力されるデータとレジスタ回路２，３で保持して因る
データとを制御線ｎの状態に基づいて選択し、レジスタ
回路（ＲＢ　）３に出力する。選択回路２１は双方向デ
ータ線（ＳＤＡ）８のデータとレジスタ回路（ＲＢ）３
のデータとを制御線筋の状態に基づいて選択し、比較回
路６に出力する。選択回路２２は双方向データ線（ＳＤ
Ｒ）１０のデータとレジスタ回路（ＲＡ）２のデータと
全制御線２６の状態に基づいて選択し、比較回路６に出
力する。比較回路６は正整数の大小関係全比較し、（選
択回路ＳＡ２の出力データ）≧（選択回路ＳＢ２の出力
データ）であれば論理的に「０」の比較信号（ＳＷ）１
４を、（選択回路ＳＡ２の出力データ）〈（選択回路Ｓ
Ｂ２の出力データ〕であれば論理的に「１」の比較信号
（ＳＷ）１４ｆｆｉ出力する。制御回路２３は２本の制
御入力線（ＬＯＡＤ　、　Ｒ／Ｌ）　１５と比較信号（
５Ｗ）１４を入力し、選択回路１９　、２０　、２１　
、２２を制御する制御線２４　、２５　、２６　、２７
を出力する。

第７図は第６図のソーティングモジュールの動作を示し
ておシ、選択回路（ＳＡＩ、ＳＢＩ、ＳＡ２，５Ｒ２）
１９　、２０　、２１　、２２が制御人力線１５と比較
信号１４とからどのデータ全選択するかを示した図であ
る。制御入力線ＬＯＡＤが「１」のとき、選択回路（Ｓ
ＡＩ、５ＢＩ）１９　、２０はそれぞれ入力データ線９
，１１からのデータを選択し、レジスタ回路（ＲＡ、Ｒ
Ｂ）２　、３は前記選択されたデータを保持する。双方
向データ線８゜１０は制御入力線Ｒ／Ｉ、が「Ｏｊのと
きそれぞれ出力データ線、入力データ線として動作する
。選択回路（ＳＡ２　、５Ｂ２）　２１　、２０は制御
入力線Ｒ／Ｉ、が「０」のときそれぞれレジスタ回路（
ＲＢ）　３　、双方向データ線（ＳＤＲ）　１０のデー
タを選択し、「１」のときそれぞれ双方向データ線（Ｓ
ＤＡ）８．レジスタ回路（ＲＡ）　２のデータを選択し
て、比較回路６に出力する。制御入力線ＬＯＡＤが「０
」のとき、第１図で説明したシフト処理と交換処理が１
クロツクで実行される。

すなわち、制御入力線ｎ／Ｌが「１」のとき選択回路（
ＳＡＩ、５ＢＩ）１９　、２０は比較信号１４に基づい
てレジスタ回路（ＲＡ）　２のデータあるいは双方向デ
ータ線（８ＤＡ）　８のデータのどちらかを選択する。

ここでは、小さい値のデータがレジスタ回路（ＲＡ）　
２に保持されると仮定すると、比較信号（ＳＷ）１４が
「１」（ＲＡ）ＳＤＡ）であれば、選択回路（ＳＡＩ　
、　ＳＢＩ　）　１９゜２０はそれぞれ双方向データ線
（ＳＤＡ）　、レジスタ回路（ＲＡ）のデータを選択し
、比較信号（ＳＷ）１４がｒＯＪ　（ＲＡり５ＤＡ）で
あれば、選択回路（ＳＡＩ）（ＳＢＩ）１９　、２０は
それぞれ前記と逆のデータを選択する。

これにより右シフト処理と交換処理が同時に実行される
。また、制御入力線Ｒ／Ｌが「Ｏ」のとき選択回路（Ｓ
Ａ１，５Ｂ１）１９，２０は比較信号１４に基づいてレ
ジスタ回路（ＲＢ）３Ｌ７）−データおるいは双方向デ
ータ線（ＳＤＲ）１０のデータのどちらかを選択する。

比較信号１４が「ＯＪ　（ＲＢ≧ＳＤＲ）であれば、選
択回路（ＳＡＩ、５ＢＩ）　１９．２０はそれぞれ双方
向データ線（ＳＤＢ）。

レジスタ回路（ＲＢ）のデータを選択し、比較信号１４
がｒｌＪ　（ＲＢ＜５ＤＲ）であれば、それぞれ前記と
逆のデータを選択する。これによシ左シフト処理と交換
処理が同時に実行される。このように、第６図のソーテ
ィングモジュールは右シフト処理と交換処理あるいは左
シフト処理と交換処理を１クロツクで実行する。したが
って、第３図のソーテインク処理装置に第６図のソーテ
ィングモジュールを用いれば、第４図の動作例のとと（
２７個のデータ全その大小関係に基づいてソーティング
することができる。このときのソーティング処理時間は
、各７′ニーズの処理順序がシフト処理、交換処理の順
であるので、２１フエーズ（２／クロツクと等しい）で
おる。ソーティング結果の読出しは制御入力線Ｒ／Ｌ　
’ｉ常に「０」とすればソーティングモジュール８１の
双方向データ線８よシ非減少順にソーティングされたデ
ータが得られ、制御入力線Ｒ／Ｌを常に「１」とすれば
ソーティングモジュールＳノの双方向データ線１０より
非増大順にソーティングされたデータが得られる。

第６図のソーティングモジュールは、ソーティングの谷
フェーズの処理を１クロツクで処理し、各フェーズにお
ける処理順序がシフト処理、交換処理の順とした構成例
である。第８図は本発明の他の実施例であり、ソーティ
ングの各フェーズの処理を１クロツクで処理するが、各
フェーズにおける処理順序を交換処理、シフト処理の順
とじた構成例である。１は２個のデータをンーティン゛
グするソーティングモジュールであシ、レジスタ回路（
ＲＡ、ＲＢ）　２　、３、比較回路（ＣＯＭＰ）　６、
双方向データ線８，１０．入力データ線９，１１、制御
入力線１５、選択回路（ＳＡ３．ＳＢ３．ＳＡ４，５Ｂ
４）　２８，２９，３０゜３１、制御回路３２とから構
成される。レジスタ回路（ＲＡ、ＲＢ）　２　、３はそ
れぞれ選択回路（ＳＡ３，５Ｂ３）２８　、２９で選択
したデータを保持するレジスタであシ、同一のクロック
信号で動作する。選択回路（ＳＡ３）２８は双方向デー
タ線（ＳＤＡ）　８　、入力データ線（ＤＡ）　９及び
レジスタ回路（ＲＡ、ＲＢ）　２　、３のデータを制御
線間の状態に基づいて選択踵レジスタ回路（ＲＡ）２に
出力する。選択回路（ＳＢ３）２９は双方向データ線（
８ＤＢ）　１０　、　入カテ−タ線（ＤＢ）　１１及び
レジスタ回路（ＲＡ、ＩＲＢ）　２　、３のデータを制
御線あの状態に基づいて選択し、レジスタ回路（ＲＢ　
）３に出力する。比較回路６はレジスタ回路（ＲＡ）２
とレジスタ回路（ＲＢ）　３のデータを比較する。ここ
では、正整数の大小関係を比較し、（ＲＡの出力データ
）″＞　（ＲＢの出力データ）であれば比較信号（ＳＷ
）　１４として「０」を出力し、（ＲＡの出力データ）
（（ＲＢの出力データ）であれば「１」全出力すると仮
定する。選択回路（ＳＡ４　、　Ｓ、ＢＡ）　３０　、
３１は比較信号１４１７）　状態に基づいてレジスタ回
路（ＲＡ、ＲＢ）　２　、３のどちらかのデータを選択
する。制御回路３２は２本の制御入力線（ＬＯＡＤ、　
Ｒ／Ｌ）　１５を入力し、選択回路（ＳＡ３，５Ｂ３）
　２８．２９を制御する制御線３３　、３４を出力する
。

第９図は第８図のソーティングモジュールの動作を示し
ておｐ１選択回路（ＳＡ３．ＳＢ３．ＳＡ４．５Ｂ４）
２８　、２９　、３０　、３１がどのデータを選択する
かを示す図である。制御入力線ＬＯＡＤが「１」のとき
、選択回路（ＳＡ３，５Ｂ３）２８　、２９はそれぞれ
入力データ線９，１１からのデータを選択し、レジスタ
回路（ＲＡ、ＲＢ）２゜３は前記選択されたデータを保
持する。選択回路（ＳＡ４　、８Ｂ４）　３０　、３１
は比較回路６とともに交換処理の役割を果たす。すなわ
ちソーティング終了径小さい値のデータがレジスタ回路
（ＲＡ）　２に保持されると仮定すれば、比較信号１４
が「ｏ」のときそれぞれレジスタ回路（ＲＢ、ＲＡ）　
３　、．２のデータを選択し、「１」のときそれぞれレ
ジスタ回路（ＲＡ、ＲＢ）２゜３のデータを出力する。

制御入力線Ｒ／ＬがｒＯＪのとき、双方向データ線８は
選択回路（８Ａ４）３００出力データを出力し、双方向
データ線１０は入力データ線となる。このとき選択回路
（ＳＢ３）２９は双方向データ線１０のデータを選択し
、また比較信号１４が「０」であればレジスタ回路（Ｒ
Ｂ）−３のデータが双方向データ線８に出力するので、
選択回路（ＳＡ３　）詔はレジスタ回路（ＲＡ）　２の
データを選択する。

比較信号１４が「１」であれば、レジスタ回路（ＲＡ）
２のデータが双方向データ線８に出力するので、選択回
路（ＳＡ３）２８はレジスタ回路（ＲＢ）　３のデータ
全選択する。これにより交換処理と左シフト処理が同時
に実行される。制御入力線Ｒ／Ｅが「１」のとき、双方
向データ線８は入力データ線となシ、双方向データ線１
０は選択回路（ＳＢＡ）３１の出力データ全出力する。

このとき選択回路（ＳＡ３）２８は双方向データ線８の
データを選択し、また比較信号１４が「０」であればレ
ジスタ回路（Ｒ／１）　２のデータが双方向データ線１
０に出力するので、選択回路（ＳＢ３）２９はレジスタ
回路（ＲＢ）　３のデータを選択する。

比較信号１４が「１」であれば、レジスタ回路（ＲＢ）
３のデータが双方向データ線ｌＯに出力するので、選択
回路（ＳＢ３）２９はレジスタ回路（ＲＡ）　２のデー
タを選択する。これによシ交換処理と右シフト処理が同
時に実行される。このように第８図のソーティングモジ
ュールは交換処理と右シフト処理あるいは交換処理と左
シフト処理を１クロツクで実行する。したがって第３図
のソーティング処理装置に第８図のモジュールを用いれ
ば、２１個のデータをその大小関係に基づいてソーティ
ングすることができる。このときのソーティング処理時
間は各フェーズの処理順序が交換処理、シフト処理の順
であるので、前述したように２ノー１７エーズ（２Ｊ−
１クロツクと等しい）である。ただし、ソーティングの
最後の処理がシフト処理であるので、ソーティング結果
のデータが隣接モジュールに１個づつシフトすることに
なる。そのため、ソーティング結果を読出すのにデータ
を１目金分にシフトする必要があるので、ソーティング
結果の読出し時間まで含めた処理時間は第６図のソーテ
ィングモジュールの場合と同一となる。

以上本発明につめて実施例を用いて説明した。

第１図、第６図、第８図のソーティングモジュールでは
、隣接モジュール間のデータの伝達に双方向データ線を
用いたが、これｔ入力データ線、出力データ線の二つに
分割しても同様の動作をする。

また、第３図のソーティング処理装置においては、ソー
ティング処理結果全双方向データ線よシ読出す構成とし
たが、これをデータ処理モジュールに格納する構成とす
ることも可能である。

なお本発明における選択回路、制御回路は、たとえばマ
イクロコンピュータを内蔵した各種プロセッサに使用さ
れている通常の信号選択、制御用論理回路を適用する。

発明の詳細 な説明したように、本発明では第１．第２のデータをソ
ーティングするソーティングモジュールを一次元配列状
に直列接続し、各モジュールは第２のデータを隣接モジ
ュールヘシフトし、隣接モジュールからのデータと該モ
ジュールの第１のデータとの比較結果に基づいて交換す
る処理と、各モジュールは第１のデータを前記と反対側
の隣接モジュールヘシフトし、隣接モジュールからのデ
ータと該モジュールの第２のデータとの比較結果に基づ
いて交換する処理とを交互にくシ返し行なって複数のデ
ータ全ハードウェアでソーティングしているので次のよ
うな利点がある。

第１の利点は、ソーティングの処理時間がデータ数ｆｎ
とすると最大ｎフェーズ（あるいはｎクロック）である
ので、大量のデータを高速にソーティングすることがで
きる。

第２の利点は、第３図のようなソーティング処理装置を
構成すれば、データ処理モジュールの処理とソーティン
グモジュールの処理と全独立に行なうことができる。そ
のため両モジュール全バイグライン的に制御し、両モジ
ュールの処理全オーバラッグさせればさらに処理性能が
向上する。

第３の利点は、谷ソーティングモジュールが全て同一構
成であり、またモジュール間の通信が隣接モジュールだ
けであるので、データ数の拡張が答易である。さらに、
＜シ返し性の高い回路構成であるのでＬＳＩとの整合性
が良い。

【図面の簡単な説明】

ｉｆ図は本発明のソーティングモジュールの構成例、第
２図は第１図のソーティングモジールの動作例を示す図
、第３図は第１図のソーティングモジュールを用いたソ
ーティング処理装置の構成例、第４図はモジュールを４
個としたときの第３図のソーティング処理装置の動作例
を示す図、第５図ａ、ｌ）は第３図のソーティング処理
装置の一般的な動作例を示す図、第６図、第８図は１ク
ロツクで処理するソーティングモジュールの構成例、第
７図、第９図はそれぞれ第６図、第８図のソーティング
モジュールの動作例を示す図である。 １°・°ソーティングモジュール、２，３・・・レジス
タ回路、４，５・・・選択回路、７・・・制御回路、８
．１０・・・双方向データ線、　９，１１・・・入力デ
ータ線、１２．１３・・・制御線、１４・・・比較信号
線、１５・・・制御入方線、１６・・・データ処理モジ
ュール、１７．１８・・・レジスタ回路、１９　、２０
　、２１　、２２　・・・選択回路、２３　・・・制御
回路、ｕ、２５２６　、２７・・・制御線、２８　、２
９　、３０　、３１・・・選択回路、３２・・・制御回
路、３３　、３４・・・制御線。 特許出願人　日本電信電話公社 代理人弁理士　玉　　蟲　　久　五　部（外３名） −２２８− 第　５　図 を事件の表示 昭和５８年特許願第６４９７４号 ２、発明の名称 ソーティング処理方式 ３、補正をする者 事件との関係　　特許出願人 住　所　　東京都千代田区内幸町１丁目１番６号氏名　
（４２２）日本電信電話公社 代表者真藤　恒 ４、代理人 明細書第４頁第７行から第３０頁第６行迄の発明の詳細
な説明の欄について、 （１）第１４頁第１８行目の［第５　’３　ａ　、　ｂ
　Ｊ　ヲｌ第１表および第２表」と補正する。 （２）第１４頁第１８行目「・・・一般的に説明する。 」の次（二次の第１表および第２表を挿入する。 第　１　表 第　　２　　表 （３）第１５頁第６行目乃至第７行目の「第５図α」を
「第１表」と補正する。 （４）第１６頁第２行目乃至第３行目の「第５図ｂ」を
「第２表」と補正する。 （５）第１８頁第１行目の「第５図α、ＡＪを「第１表
、第２表」と補正する。 （６）第１９頁第５行目の「第６区」を「第５区」と補
正する。 （７）第２０頁第１９行目の「第７図」を「第６図」、
「第６図」を「第５図」とそれぞれ補正する。 （８）第２２頁第１７行目乃至第１８行目の「第６図」
を「第５凶」と補正する。 （９）第２６頁第１行目の「第６図」を「第５図」と補
正する。 （１０）第２６頁第１４行目の「第６図」を「第５図」
と補正する。 （１１）第１４頁第１８行目の１第８図」を「第７図」
と補正する。 （１２）第２５頁第９行目の「第９図」を「第８図」。 「第８図」を「第７図」とそれぞれ補正する。 （１６）第２７頁第６行目の「第８図」を「第７図」と
補正する。 （１４）第２７頁第１０行目の「第８図Ｊｔｒ第７図」
と補正する。 （１５）第２８頁第１行目の［第６図Ｊを「第５図」と
補正する。 （１６）第２８頁第４行目の「第６図」を「第５図」、
「第８図」を「第７図」とそれぞれ補正する。 明細書第６０頁第４行から第６１頁第６行迄の図面の簡
単な説明の欄について、 （１７）第６０頁第１０行目乃至第１２行目の「第５図
α、には第６図のソーティング処理装置の一般的な動作
例を示す図、」を削除する。 （１８）第３０頁第１２行目の「第６図、第８図」を「
第５図、第７図」と補正する。 （１９）第６０頁第１４行目の「第７図、第９図」を「
第６図、第８図」、「第６図、第８図」を「第５図、第
７図」とそれぞれ補正する。 （２０）図面について、第５図α、ｈを削除し、第６図
、第７図、第８図、第９図をそれぞれ繰上げ第５図、第
６図、第７図、第８図と添付する赤で示すとおり補正す
る。

Claims (2)

【特許請求の範囲】
1. （１）双方向データ線および入力データ線からの入力デ
   ータと第１および第２のレジスタ回路に保持するデータ
   とを選択する第１および第２の選択回路と、該第１およ
   び第２の選択回路によシ選択したデータ會それぞれ保持
   する第１および第２のレジスタ回路と、該第１および第
   ２のレジスタ回路、または該第１および第２のレジスタ
   回路のそれぞれと該第１および第２のレジスタ回路に隣
   接する他の第２および第１のレジスタ回路で保持してい
   る２個のデータを比較し、該２個のデータの大小関係に
   よシ定まる比較信号を出力する比較回路と、該比較回路
   からの該比較信号出力と、前記入力データ線の選択およ
   び前記双方向データ線に対し入力データ線、出力データ
   線を指定する制御入力線からの制御信号とを入力踵前些
   第１および第２の選択回路のデータ選択全制御する制御
   回路とからなる同一構成のソーティングモジュールを複
   数個直列接続してなシ、該各ソーティングモジュールは
   並列動作を行い、前記第１のレジスタのデータと第２の
   レジスタのデータとを前記比較回路によｐ比較し、該２
   個のデータを前記制御回路によシ隣接する一方のソーテ
   ィングモジュールの第１のレジスタと、当該ソーティン
   グモジュールの第２のレジスタに再配置する処理と、前
   記第１のレジスタのデータと第２のレジスタのデータと
   を前記比較回路によシ比較し、該２個のデータを前記制
   御回路によシ轟該ソーティングモジュールの第１のレジ
   スタと、隣接する他方のソーティングモジュールの第２
   のレジスタとに再配置する処理とを交互に繰返すことを
   特徴とするソーティング処理方式。
2. （２）双方向データ線および入力データ線からの入力デ
   ータと第１および第２のレジスタ回路に保持す基データ
   とを選択する第１および第２の選択回路と、該第１およ
   び第２の選択回路によシ選択したデータをそれぞれ保持
   する第１および第２のレジスタ回路と、該第１および第
   ２のレジスタ回路、または該第１および第２のレジスタ
   回路のそれぞれと該第１および第２のレジスタ回路に隣
   接する他の第２および第１のレジスタ回路で保持してい
   る２個のデータ全比較し、該２個のデータの大小関係に
   より定まる比較信号を出力する比較回路と、該比較回路
   からの該比較信号出力と、前記入力データ線の選択およ
   び前記双方向データ線に対し入力データ線、出力データ
   線を指定する制御入力線からの制御信号とを入力し、前
   記第１および第２の選択回路のデータ選択を制御する制
   御回路とからなる同一構成のソーティングモジュールを
   複数個直列接続してなシ、該谷ンーテイングモジュール
   は並列動作を行い、前記第２のレジスタのデータと、隣
   接する一方のソーティングモジュールの第１のレジスタ
   のデータと全前記比較回路により比較し、該２個のデー
   タを前記制御回路によ）当該ソーティングモジュールの
   第１のレジスタと第２のレジスタとに再配置する処理と
   、前記第１のレジスタのデータと隣接する他方のソーテ
   ィングモジュールの第２のレジスタのデータとを前記比
   較回路によシ比較し、該２個のデータ全前記制御回路に
   よシ当該ソーティングモジュールの第１のレジスタと第
   ２のレジスタとに再配置する処理とを交互に繰返すこと
   全特徴とするソーティング処理方式。