JPH01189723A - マージ・ソータ - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明はデータベース処理に代表される非数値処理分
野における基本演算の１つであるソート処理を高速に効
率良く実行し得るようにしたマージ・ソータに関する。

（従来の技術） データを特定の順序に並び換えるソート処理は非数値処
理分野における基本演算の１つであり、古くから数多く
のソフトウェアのアルゴリズム（単純選択法、単純交換
法、ヒープソート法、分割ソート法、クイックソート法
、マージソート法等）か提案されて、目的に応じた使い
分けが行われてきた。

１９７０年代に入ると、ホスト計算機のソート処理ルー
チンを付加プロセッサのファームウェアｎ個のレコード
をｎ個のセルを用いてソートするパイトニック・ソータ
や並列計数ソータ、ｌｏｇ　ｎ個のセルを用いてｎ個数
のレコードをソートするパイプライン方式のソータ等が
ある。これらを現状の技術を用いて実現するという観点
からみると、ハードウェアの小型化が可能という利点か
ら、ｌｏｇ　ｎ個のセルを用いてｎ個のレコードをソー
トするパイプライン方式のソータが実用的であるとされ
ている。

パイプライン方式のソータで実用化されたちの１つに２
ウエイ・マージ・ソータかある。このソータは、２つの
ソートされたレコード列（以下、ストリングと呼ぶ）を
突き合せて１つのソートされたストリングを生成するマ
ージ操作を、１次元に多数個配置したセルにより連続的
に行うものである。第５図に３段の２ウエイ・マージ・
ソータを用いて昇順に並んだ５個のレコード（１，２゜
・・・の順に入力されるとする）を降順に並び換える時
のこのソータの動作原理を示し、第６図にそのパイプラ
イン動作動作の様子を示す。ソータの各一’−：１５＜
　Ｕ　Ｍに、偶数番目の入力ストリングがＬＭに交互に
格納される。ソータは、入力レコード列（以下、ストリ
ームと呼ぶ）を長さ１のストリングが−”並んたものと
見なして、これを入力順に２個ずつマージし、各段でス
トリング長（ストリングのレコード数）を倍々にしてい
く。即ち、第５図に示されているように、セル２１に入
力されるストリング長は１であるから、セル２１は、長
さ１のストリング１，２，３，４．５を入力順にＵＭと
ＬＭに交互に格納しつつＵＭとＬＭのレコードのマージ
操作を行い、長さが２のストリング［２，ｊ］ｃ４．、
　３］　［５，−］を生成し、セル２２に出力する動作
を行う。セル２　は、セル２１より送られてくる長さ２
のストリングを入力順にＵＭとＬＭに交互に格納しつつ
ＵＭと’ＬＭのレコードのマージ操作を行い、長さ４の
ストリング［４，３゜２．１１　　［５，−、−＋−１
を生成し、セル２３に出力する動作を行う。このように
セル２ｉ　　（ｉ−１，２，・）はセル２１−１より送
られてくる長さ２　ｊ−１のストリングを入力順にメモ
リー１のＵＭとＬＭに交互に格納しつつＵＭとＬＭのレ
コードのマージ操作を行い、長さ２１のストリングを生
成し、セル２　ｉ＋１に出力する。この時、各段は偶数
番口のストリングの先頭データが入力される毎′贋に処
理を開始し、第６図に示すようなパイプライン動作を行
う。第６図より本ソータの処理時間Ｔ（１）を求めると
、 Ｔ　（１）　＝　ｔ　ｉ　＋　ｄ　Ｌ　＋ｄ　２　＋　
ｔ　Ｏ・・・（１）となる。ここで、ｔｌとｔｏはそれ
ぞれ５個のレコードからなるストリームを入力する時間
と出力する時間ｄ１はストリームのレコード数が２の累
ノ 乗値からずれたために生じた遅れ時間を、ｄ２はストリ
ームがセルを通過するための遅れ時間を示す。ストリー
ムのレコード数をＣ１セル数をＮ。

１ステツプの処理時間をＴとすると（１）式は次のよう
に表わされる。

Ｔ（１）＝ＣＴ＋　（２ａ−Ｃ）Ｔ＋　（Ｎ−１）Ｔ＋
ＣＴ　　　　　　　　　　　・・・（２）ただし、ａ　
＝＜１０ｇ２Ｃ＞　（＜　＞□は小数点以下を切り上げ
た整数値）　、ｔｉ　＝ｔＯ＝Ｃ’ｒ、　　　ｄｉ＝（
２ａ−Ｃ）Ｔ、ｄ２＝（Ｎ−１）Ｔである。

上述の例の場合、Ｃ＝５、Ｎ＝３であるからａ＝３とな
り、Ｔ（１）は１５Ｔとなる。

−、、＝、、　（Ｌ　）式において、ｔｉ、ｔｏ、ｄ２
はバードウ”：：”ｌニアの仕様により定まる値である
が、ｄｌはストリーｊ−ムのレコード数により決まる値
であるため１、制御方式を工夫することにより除去する
ことが可−６＝ 能である。

、：そこで、従来より、」二記ｄ１を取り除く方式とし
て、疑似レコード追加方式マージ・ソータ（Ｔｏｄｄ、
Ｓ、：Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｈａｒｄｗａｒｅ
　ｆｏｒ　ａ　ＭｅｒｇｅＳｏｒｔ　Ｕｓｉｎｇ　Ｍｕ
ｌｔｉｐｌｅ　Ｐｒｏｃｅｓｓｏｒｓ、ｌＢＭ　Ｊ、Ｒ
ＥＳ。

ＤＥＶＥＬＯＰ、、Ｖｏｌ、２２．Ｎｏ、５．ＰＰ、５
０９−５１７（１９７８））やダイナミック・マージ方
式マージ・ソータ（林、他；パイプラインマージンート
アルゴリズムの改良によるソート時間の短縮　情報処理
学会第２９口金国大会ＰＰ−７６３−７６４（１９８４
））が提案されている。

疑似レコード追加方式マージ・ソータは、第７図に示す
ように、ストリームのレコード数が２の累乗値になるよ
うに、入力ストリームの先頭に疑似レコード（十）を追
加して仮想的な動作を考え、第８図に示すステップ４よ
り実際にソータを動作させることにより遅れ時間（ｄｌ
）を除去しようとするものである。しかし、ソータをス
テップ４より動作させるためには、ステップ１，２．３
の処理が終了したものとしてセル２１〜２３に制御パラ
メータの初期値をセットする必要があるので、−なる欠
点を有している。

′１ ）一方、ダイナミック・マージ方式マージ・ソー〉は第
９図に示すように、ストリング数が奇数となるセルで最
後のストリングが入力されてきた時に、その時のマージ
動作を中断して最後にストリングが先にマージされるよ
うにストリームのダイナミックな切換を行うことにより
、遅れ時間（ｄｌ）を除去するものである。この方式の
処理例を第１０図に示す。第１０図ではステップ５と６
でダイナミック・マージ動作が行なわれている。

即ち、ステップ５において、セル４１は［５コが最後の
ストリングで奇数番目であることを検出し、ストリング
［３］と［４］をマージしてストリング［４，，３］を
出力する動作を、［４］を出力した時点でストリング［
３］と［５］をマージする動作に切換える。また、セル
４２は、ステップ６において、ストリング［２，１］　
と［４］をマージしてストリング［４，２，１］を出力
する動作を、４を出力した時点でストリング［２，１］
　と［５，３］をマージする動作に切換える。この方各
セルは処理ストリングのダイナミックな変更と糧々の長
さのストリングを扱う必要があるので制ｉが複雑になる
欠点を有している。

（発明が解決しようとする問題点） 上述の如く、従来のパイプラ・ｆン方式マージ・ソート
は入力ストリングのレコード数が２の累乗でない場合、
遅れ時間（ｄｌ）が生ずる欠点を有していた。この原因
は、２ウエイ・マージ・ソータの場合、各セルが２つの
ストリングをマージして１つのストリングを出力する動
作を繰返すため、セルで扱うストリング数が偶数であれ
ば良いが奇数の場合にはマージする相手のストリングが
無くなる場合かあるためである。この対策として、スト
リームのレコード数が２の累乗になるように疑似レコー
ドを追加する方法やダイナミック・マージを行う方法が
提案されていた。しかし、これらの方法はアルゴリズム
としては正しいものの、実現性に欠ける欠点を有してい
た。

本発明の目的は、複雑な制御を用いることなく、上記入
力ストリングのレコード数の２の累乗（問題点を解決す
るための手段） ゛　本発明に係るマージ・ソータは、各段のセル選択す
る機能とを持たせ、これらの機能を組合わせることによ
り、各セルでマージ操作を行なうストリング数が常に偶
数になるようにしたものである。

ソート・モードは、前段から連続的に入力される２つの
人力ストリングをメモリに格納しつつ、後の上記入力ス
トリングの先頭のレコードか入力−１〇　　　− される毎に、前記両ストリングを構成するレコードの大
小関係を比較しその比較結果から決定される順序に並び
変えつつ前記両ストリングをマージして新たな１つのス
トリングとして次段に出力するモードである。

パス・モードは、前記入力ストリングを前記メモリを介
さずにそのまま次段に転送するモードである。

各セルは、当該セルで処理するストリング数が１　（作
　用） １　本発明によれば、入力ストリング数が奇数の場合に
は、最初のストリングを直ちに次段に転送するので、通
常のマージ操作を行なう場合に比べて処理ステップ数を
削減する作用を呈する。また、各セルでは、マージ操作
を行なうストリング数が常に偶数となるため無駄のない
処理が行われ、入カレコード数の２の累乗値からのすれ
に起因する遅れ時間（ｄｌ）を除去することができる。

（実施例） 本発明の一実施例に係るマージ・ソータの動作原理図を
第１図に、そのパイプライン処理動作の様子を第２図に
示す。

このマージ・ソータは、３つの処理ユニット５．５．５
３を縦続接続して構成され、各処理ユニット５ｉ（ｉ＝
１〜３）は、メモリ１１とセル６１とで構成されたもの
となっている。各セル６１は、ソート・モードとパス・
モードとを持ち、自身が処理するストリング数が奇数の
時に最初のストリングだけをパス・モードで処理し残り
へ １−・倉遅れ時間（ｄｌ）が生じない。以下、第１図と
第２図を用いてその理由を説明する。

ユ、１セル６１は長さ１のストリングを５個、即ち、奇
数個のストリングを処理しなければならないので、まず
パス・モードで最初のストリング［１］をメモリを介さ
ずにそのままセル６２に転送し、以後ソート・モードで
ストリング［２］をＵＭに、［３］をＬＭに格納しつつ
これら２つのストリングのマージ操作を行い、長さ２の
ストリング［３゜２］を、同様にして［５，４］をセル
６゜に出力する。次に、セル６２は長さ２のストリング
を３個処理しなければならないので、セル１と同様に最
初のストリング［１，−］をパス・モードでセル６３に
転送し、以後ソート・モードでストリング［３，２コを
ＵＭに、［５，４］をＬＭに格納しつつこれら２つのス
トリングのマージ操作を行い、長さ４のストリング［５
，４，３，２］をセル６　に出力する。セル６３は長さ
４のストリングを２個処理すればよいので、２番目のス
トリングの最初のレコードが入力されると直ちにマージ
、”めデータ若しくは入力レコード３を格納する入カシ レジスタ１１とメモリ１１のＵＭ部とＬＭ部から読み出
されたデータを格納するＵレジスタ１２及びＬレジスタ
１３と、Ｕレジスタ１２とＬレジスタ１３の内容を比較
する比較器１４と、この比較器１４の比較結果によりＵ
レジスタ１２又はＬレジスタ１３のデータを選択するセ
レクタ１５と、選択されたデータを最終結果として、又
は次段のセルに出力するため一時保持する出力レジスタ
１６と、メモリ１１のリードアドレス及びライトアドレ
スを生成するアドレス制御回路１７と、外部から制御情
報を保持する制御情報保持レジスタ１８と、制御情報保
持レジスタ１８の値により動作モードの切換信号を生成
する動作モード制御回路１９と、モードの切換を行う切
換器２０と、ソート・モード動作のシーフェンス発生器
２１およびパス・モード動作シーフェンス発生器２２と
より構成される。

セル６１は３サイクルで第４図に示すようなソート・モ
ード動作またはパス・モード動作の１処′即ち、ソート
・モードでは、最初のストリングをＵＭ部に格納して次
のストリングをＬＭ部に格納しはじめると、第４図に示
すように、サイクル１で入力データの入力レジスタ１１
へのセットとメモリ１１のＵＭ部のデータのＵレジスタ
１２への読み出し動作を、サイクル２でメモリ１１のＬ
Ｍ部のデータのしレジスタ１３への読み出し動作を、サ
イクル３で両者の比較を行って所定のデータを出力レジ
スタにセットする動作と入力レジスタ１１の内容をメモ
リ１１に格納する動作とを行う。

一方、パス・モードでは、入力データをサイクル１で入
力レジスタ１１に受は取り、サイクル２でそれをＵレジ
スタ１２に転送し、サイクル３でそれを出力レジスタ１
６に転送する動作を行う。

これらの動作モードは、動作モード制御回路１９で、制
御情報として与えられるストリームのレコード数と当該
セルで処理できるストリング長（ストリングのレコード
数）から当該セルが実際に処理するストリング数を求め
ることにより次の、路１９は、求めたストリング数の値
が奇数の時は、゛１人力されてくる最初のストリングだ
けをノくス・モ１：ｉｔ “′ニドで、残りのストリングをソート・モードで処、
門し、偶数の時はパス・モードだけで処理するよ゛うに
切換器２０を制御する。

このように、当該セルで処理すべきストリング数が奇数
の時は最初のストリングをメモリに格納しないで直接次
段のセルに転送するパス・モード機能を導入することに
より、遅れ時間（ｄｌ）を除去してソート処理時間を短
縮することができる。

なお、上記実施例では２ウエイ・マージ・ソータについ
て述べたが、本発明は２ウエイ・マージ・ソータに限定
されるものではなくマルチウェイ・マージ・ソータにも
適用可能である。

［発明の効果］ 本発明によれば、マージ・ソータの各セルは、ソート・
モード動作とパス・モード動作を行う２処理し残りをソ
ート・モードで処理するという極めで簡単な制御によっ
て、各セルでの操作を行う・ストリング数をいつも偶数
にすることができるので、」二記入カストリングのレコ
ード数の２の累乗値からのずれに起因する遅れ時間（ｄ
ｌ）を簡単１゜ な制御回路で除去することかできる。

【図面の簡単な説明】

１　第１図は本発明の一実施例に係るマージ・ソ−タの
動作原理図、第２図は同マージ・ソータのパイプライン
処理動作の様子を示す図、第３図は同マージ・ソータを
構成するセルの更に詳細な構成図、第４図は同マージ・
ソータの各セルにおけるソート・モード動作とパス・モ
ード動作の説明図、第５図は従来方式のマージ・ソータ
の動作原理図、第６図は同マージ・ソータのパイプライ
ン処理動作の様子を示す図、第７図は擬似レコード追加
方式マージ・ソータの動作原理図、第８図は同マージ・
ソータのパイプライン処理動作の様子を示す図、第９図
はダイナミック・マージ方式のマージ・ソータの動作原
理図、第１０図は同マー＝　１７− ジ・ソータのパイプライン処理動作の様子を示す図であ
る。 １〜１　・・・メモリ、２〜２．３〜３　。 ４〜４．６〜６　・・・セル、５１〜５３・・・処理ユ
ニット、２１１・・・入力レジスタ、１２・・・Ｕレジ
ースタ＼　１３・・・Ｌレジスタ、１４・・・比較器、
１５・・・・、゛ □′女レしタ、１６・・・出力レジスタ、１７・・・ア
ドレス制御回路、１８・・・制御情報保持レジスタ、１
９・・・“・動作モード制御回路、２０・・・切換器、
２１・・ソー３］ｉ： ＝ １０図

Claims (1)

1. 【特許請求の範囲】 複数のストリングからなるレコード列を格納するメモリ
   と、連続的に入力される前記複数のストリングを所定の
   順序で前期メモリに格納するとともに、所定の規定に従
   ってマージして出力するセルとからなる処理ユニットを
   複数段接続して構成され、これら処理ユニットによるパ
   イプライン処理によって入力レコード列をソーティング
   するマージ・ソータにおいて、 前記各セルは、前段から連続的に入力される２つの入力
   ストリングを前記メモリに格納しつつ、後の上記入力ス
   トリングの先頭のレコードが入力される毎に、前記両ス
   トリングを構成するレコードの大小関係を比較しその比
   較結果から決定される順序に並び変えながら前記両スト
   リングをマージして新たな１つのストリングとして次段
   に出力するソート・モードと、前記入力ストリングを前
   記メモリを介さずにそのまま次段に転送するパス・モー
   ドとを有し、当該セルで処理するストリング数が奇数の
   時は、最初のストリングが入力されたら直ちに該ストリ
   ングだけを前期パス・モードで処理し、その他のストリ
   ングについては前期ソート・モードで処理するものであ
   ることを特徴とするマージ・ソータ。