(57)【要約】      （修正有）【課題】面積制約が厳しく、ソート対象のデータ数が少ないシステムにおいて、ソート回数が多大な場合に、従来のバブルソートより処理速度が高速なソート処理を可能とする。【解決手段】記憶手段１０１からソート対象データ内のｍ個（ｍ＞２）の比較交換対象データを読み出し、並列に実行される２値の比較交換演算器を含む比較交換演算器１１１、１１２とパイプライン用のレジスタ１１２からなる比較交換手段１０３を用いて最大値データを決定する処理をソート対象データすべてに行いｍ−１個のデータの順位を決定し残りのソート対象データに対しても同様な処理を繰り返すことによりソート処理を行う。【選択図】図１
2010218178.tif 000002
【特許請求の範囲】
【請求項１】
入力された複数のデータを昇順または降順に並べ替えるソート処理方法であって、前記入力された複数のデータを初めのソート対象データとする第１のステップと、前記ソート対象データからｍ個（ｍは３以上の整数）のデータを初めの比較交換対象データとして比較交換し昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める第２のステップと、前記比較交換対象データの内の決められた前記決定データを除くｍ−１個のデータと前記ソート対象データの内の比較交換対象データとなったことがないデータの１つを合わせて新たな比較対象データとして比較交換し新たな決定データを決める処理を前記比較交換対象データとなる最後のｍ個のデータまで繰り返す第３のステップと、前記第３のステップで残ったｍ−１個のデータの順位を決めて前記ソート対象データの内の前記残ったｍ−１個のデータを除くデータを新たなソート対象データとする第４のステップと、を備え、前記第２のステップと前記第３のステップと前記第４のステップを前記入力された複数のデータの全ての順位が確定するまで繰り返すことを特徴とするソート処理方法。
【請求項２】
入力された複数のデータを昇順または降順に並べ替えるソート処理装置であって、前記入力された複数のデータを格納する記憶手段と、前記記憶手段のソート対象データの範囲の内のデータを比較交換対象データとして格納する第１のレジスタ群と、前記第１のレジスタ群に格納した各々のデータの比較交換演算を複数のステージでパイプライン処理し昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める比較交換手段と、前記比較交換手段の各ステージでの比較交換演算の対象となるデータを各ステージに対応して格納する第２のレジスタ群と、前記記憶手段と前記第１のレジスタ群と前記比較交換手段と第２のレジスタ群を制御する制御部と、を備え、前記記憶手段からソート対象データの範囲の内のｍ個（ｍは３以上の整数）のデータを読み出し第１のレジスタ群に格納する第１の処理をした後、前記第１のレジスタ群から比較交換対象データを読み出して前記比較交換手段において前記比較交換対象データの内で昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める処理と、前記比較交換手段で決められた前記決定データを前記記憶手段に書き戻す処理と、前記比較交換対象データの内の決められた前記決定データを除くｍ−１個のデータと前記記憶手段に格納されている前記ソート対象データの範囲の内の比較交換対象データとなったことがないデータの１つを読み出し合わせて第１のレジスタ群に新たな比較対象データとして格納する処理と、を前記比較交換対象データとなる最後のｍ個のデータまで繰り返す第２の処理を行い、残ったｍ−１個のデータの順位を決める第３の処理を行い、前記ソート対象データの内の前記残ったｍ−１個のデータを除くデータを新たなソート対象データの範囲とする第４の処理を行い、前記入力された複数のデータの全ての順位が確定するまで前記第１の処理と前記第２の処理と前記第３の処理と前記第４の処理を繰り返すことを特徴とするソート処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、従来のバブルソートに比べて処理速度を大幅に向上できるソート処理装置およびソート処理方法に関するものである。            
【背景技術】
【０００２】
バブルソートは，データの比較と交換を繰り返すことにより、最大または最小の数を1 つずつ確定していくソーティング方法である。バブルソートは、最悪計算時間がデータ数ｎに対して(ｎ＋・・・＋２＋１)回の比較交換が必要でデータ数２乗に比例するため，ソーティング方法としては遅い部類に分類されるが、アルゴリズムが単純であり、複雑な演算器を使用しないため、面積制約が厳しく、ソート対象のデータ数が少ないシステムに適している。
【０００３】
バブルソートは２重のループで構成される。内側のループでは、順位が未確定のデータを順に２個ずつ選択、比較交換し、最小値を選び出す。内側のループは、最小値が1つ選択されるまで繰り返される。外側のループでは、順位が未確定のデータの範囲を更新し、内側のループに戻る。外側のループは全てのデータの順位が確定するまで繰り返される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−２２９７７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、面積制約が厳しく、ソート対象のデータ数が少ないシステムにおいてもソート回数が多大な場合には従来のバブルソートの方法では処理速度が遅いなどの課題があった。
本発明は、このような従来の課題を解決するため、バブルソートの方法を拡張かつ改善し、専用演算器を追加し、また、パイプライン化により従来のバブルソート装置より高速なソート装置及びソート方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係るソート処理方法は、入力された複数のデータを初めのソート対象データとする第１のステップと、ソート対象データからｍ個（ｍは３以上の整数）のデータを初めの比較交換対象データとして比較交換し昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める第２のステップと、比較交換対象データの内の決められた決定データを除くｍ−１個のデータとソート対象データの内の比較交換対象データとなったことがないデータの１つを合わせて新たな比較対象データとして比較交換し新たな決定データを決める処理を比較交換対象データとなる最後のｍ個のデータまで繰り返す第３のステップと、第３のステップで残ったｍ−１個のデータの順位を決めてソート対象データの内の残ったｍ−１個のデータを除くデータを新たなソート対象データとする第４のステップと、を備え、第２のステップと第３のステップと第４のステップを入力された複数のデータの全ての順位が確定するまで繰り返すようにしたものである。
本発明に係るソート処理装置は、入力された複数のデータを格納する記憶手段と、記憶手段のソート対象データの範囲の内のデータを比較交換対象データとして格納する第１のレジスタ群と、第１のレジスタ群に格納した各々のデータの比較交換演算を複数のステージでパイプライン処理し昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める比較交換手段と、比較交換手段の各ステージでの比較交換演算の対象となるデータを各ステージに対応して格納する第２のレジスタ群と、記憶手段と第１のレジスタ群と比較交換手段と第２のレジスタ群を制御する制御部と、を備え、記憶手段からソート対象データの範囲の内のｍ個（ｍは３以上の整数）のデータを読み出し第１のレジスタ群に格納する第１の処理をした後、第１のレジスタ群から比較交換対象データを読み出して比較交換手段において比較交換対象データの内で昇順のソートの場合は最大値のデータを降順のソートの場合は最小値のデータを決定データとして決める処理と、比較交換手段で決められた決定データを記憶手段に書き戻す処理と、比較交換対象データの内の決められた決定データを除くｍ−１個のデータと記憶手段に格納されているソート対象データの範囲の内の比較交換対象データとなったことがないデータの１つを読み出し合わせて第１のレジスタ群に新たな比較対象データとして格納する処理と、を比較交換対象データとなる最後のｍ個のデータまで繰り返す第２の処理を行い、残ったｍ−１個のデータの順位を決める第３の処理を行い、ソート対象データの内の残ったｍ−１個のデータを除くデータを新たなソート対象データの範囲とする第４の処理を行い、入力された複数のデータの全ての順位が確定するまで第１の処理と第２の処理と第３の処理と第４の処理を繰り返すようにしたものである。
【発明の効果】
【０００７】
本願発明のソート処理方法（以下、拡張バブルソート方法という）は、最悪計算時間のオーダーは、バブルソートと同じく、データ数の２乗に比例するが、専用演算器との組み合わせにより、ループ回数を削減し、実行時間を短縮できる。
例えば、一度に比較するデータ数を4とすると、最悪時の比較交換回数はおよそ(ｎ＋・・・＋２＋１)／３となる。さらに、メモリアクセス回数の削減により実行サイクル数がより削減される。
【０００８】
本願発明のソート処理装置は、ハードウェア量を従来のバブルソートより少しの増加に抑えることができ、従来のバブルソートを用いる演算器と同様に、面積制約の大きいシステムに適用できるだけではなく、より高速にソート処理することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態１によるソート処理装置の構成図
【図２】本発明の実施の形態１によるソート処理装置の処理方法を示すフローチャート
【図３】本発明の実施の形態１によるｍ＝４の場合の実施例であるソート処理装置の構成図
【図４】図３のプロセッサを構成するブロックの表記とその種類と名称および内容または動作を示す図
【図５】本発明の実施例の比較交換手段の構成及び動作の説明図
【図６】本発明の実施例におけるソート処理装置の処理方法を示すフローチャート
【図７】本発明の実施例におけるソート処理装置の評価実験の測定結果
【発明を実施するための形態】
【００１０】
本発明の実施の一形態を説明する。
【００１１】
図1は本発明の実施の形態１によるソート処理装置を示す構成図である。
【００１２】
図１において、ソート処理装置は、入力された複数のデータを格納するデータメモリ１０１（記憶手段）と、データメモリ１０１のソート対象データの範囲の内のデータをｍ個（ｍは３以上の整数）読み出し比較交換対象データとして格納する専用レジスタ１０２（第１のレジスタ群）と、専用レジスタ１０２に格納した各々のデータの比較交換演算により昇順のソートの場合は最大値のデータを決め降順のソートの場合は最小値を決める比較交換手段１０３と、制御部１０４を備えている。また、比較交換手段１０３は、複数のステージの比較交換演算を行うため、専用レジスタ１０２から読み出したデータを比較演算する比較交換演算器１１１と、比較交換演算器１１１の出力で次のステージの比較演算の対象となるデータを格納するレジスタ１１２（第２のレジスタ群）、次のステージでレジスタ１１２から読み出したデータを比較演算する比較交換演算器１１２を備えている。制御部１０４は、データメモリ１０１と専用レジスタ１０２の入出力、比較交換手段の出力の専用レジスタ１０２及びデータメモリ１０１への出力を制御する。
なお、比較交換手段１０３が３以上のステージを持つ場合はステージ間にさらにレジスタを付け加えればよい。例えば、ｍ＞４のときは、比較交換手段１０３が、ｌｏｇ(2)ｍ (２を底とする対数をとり小数点以下切り上げ)個の比較交換演算器と、ｌｏｇ(2)ｍ−１個のレジスタで構成され、比較交換演算器間にレジスタが挟まれる構成になる。ｍが大きい場合、複数の比較交換演算を1サイクルで実現するために、全ての比較交換演算器の間にレジスタを挟むのではなく、他の演算器の遅延やシステムの遅延制約次第で、数個の比較交換演算器の間に1つのレジスタを挟むことにより、パイプライン段数の増加を抑えるという構成をとることもできる。
【００１３】
次に、ソート処理装置の動作を説明する。
【００１４】
図２は、本発明の実施の形態１によるソート処理装置の処理方法を昇順のソートについて示すフローチャートである。まず、データメモリ１０１のソート対象データの範囲を初期設定する（ステップＳ１）。次に、ソート対象のデータが存在するかを判断し（ステップＳ２）、無ければ全ての順位づけが終わったとして終了し、あれば次のステップＳ３に進む。ステップＳ３では、データメモリ１０１からソート対象データの範囲の内の所定のｍ個（ｍは３以上の整数）のデータを比較交換対象データとして読み出す。次に、比較交換対象データを専用レジスタ１０２に書き込み（ステップＳ４）、比較交換手段１０３で比較交換対象データの最大値のデータを決め（ステップＳ５）、決められた最大値のデータをデータメモリ１０１に書き戻す（ステップＳ６）。次に、ソート対象の全てのデータが比較交換済みかを判断する（ステップＳ７）。済んでいない場合は、比較交換対象データの内の決められた最大値のデータを除くｍ−１個のデータとデータメモリ１０１に格納されているソート対象データの範囲の内で比較交換対象データとなったことがないデータの１つを読み出し合わせて新たな比較対象データとし（ステップＳ８）、ステップＳ４に戻る。ステップＳ４〜Ｓ８の繰り返しを内側ループと呼ぶ。ソート対象データの範囲の比較交換対象データとなる最後のｍ個のデータまで内側ループの処理が終わりソート対象の全てのデータが比較交換済みとなったとき、残ったｍ−１個のデータの順位を決めデータメモリ１０１に書き戻す（ステップＳ９）、ここでこれまでの内側ループの処理とステップＳ９で交換が行われたかどうかについて例えば交換発生フラグで保持して置き一度も交換が発生しないかどうかを見ることによって、処理の途中でソートが完了したかを判断する（ステップＳ１０）。一度も交換が発生しなかった時は、ソートが完了したとして終了する。一度でも交換が発生したときは、ソート対象データのうちで内側ループの最後で残ったｍ−１個のデータ以外のデータを新たなソート対象データの範囲とし（ステップ１１）、ステップＳ２に戻り新たな比較交換を実行していく。このループを外側ループと呼ぶ。
【００１５】
なお、ここでソートを小さい値から行う場合（昇順）としたが、大きいほうから行う場合（降順）は、上述したート処理装置の処理方法の説明で「最大値」を「最小値」と読み替えればよい。
【実施例】
【００１６】
図３は、本発明の実施の形態１のｍ＝４の場合の実施例で、プロセッサに組み込まれたソート処理装置を示す。プロセッサを構成するブロックの図３中の表記とその種類と名称及び内容または動作について、図４に示す。
【００１７】
図３のプロセッサは、遅延時間の削減のため、4段のパイプラインを持ち、３つのパイプラインレジスタ３２０、３１２、３２２で分けられている。パイプラインステージは命令フェッチを行うパイプラインレジスタ３２０の前までのIFステージ、 命令のデコードを行うパイプラインレジスタ３１２の前までのIDステージ、 演算を実行するパイプラインレジスタ３２２の前までのEXEステージ、パイプラインレジスタ３２２の後のデータメモリの読み書きやレジスタへの書き込みを行うWBステージの4個で構成される。比較交換演算器３１１は図１の比較交換演算器１１１に対応し、IDステージに含まれる。比較交換演算器３１３は図１の比較交換演算器１１３に対応し、EXEステージに含まれる。比較交換演算器３１１、比較交換演算器３１３及びパイプラインレジスタ３１２は、比較交換演算により昇順のソートの場合は最大値のデータを決める比較交換手段１０３を構成する。データメモリ３０１は図１のデータメモリ１０１に対応し、入力された複数のデータを格納し、また処理途中のデータの入出力および最終の全ての順位づけが終わったデータの格納が行われる。専用レジスタ３０２は図１の専用レジスタ１０２に対応し、４個の比較交換対象データを格納するＳＰＲ０，ＳＰＲ１，ＳＰＲ２，ＳＰＲ３に加えて、IDステージ及びEXEステージの比較交換演算器３１１または比較交換演算器３１３で一度でも交換が発生したかどうかを示す交換発生フラグを格納する交換フラグレジスタＸＦからなる。
【００１８】
図５は、比較交換手段１０３の詳細な説明図である。４個の比較交換対象データが専用レジスタ１０２のＳＰＲ０〜３から比較交換演算器３１１に読み込まれる。比較交換演算器３１１は、入力された２値を比較し大きい方の値と小さい方の値に分けて出力する２個の比較交換演算器CMPX0，CMPX1からなる。比較交換演算器３１３も同様に、入力された２値を比較し大きい方の値と小さい方の値に分けて出力する２個の比較交換演算器CMPX2，CMPX3からなるが、比較交換演算器CMPX2では比較交換演算器３１１で出力されパイプラインレジスタ３１２に格納された２個の大きい方の値を入力し比較交換し、比較交換演算器CMPX3では比較交換演算器３１１で出力されパイプラインレジスタ４１２に格納された２個の小さい方の値を入力し比較交換する。従って、４個の比較交換対象データの内、最大値を持つデータと最小値を持つデータが決定され、それぞれ専用レジスタ１０２のＳＰＲ３とＳＰＲ２に格納される。一方、比較交換演算器CMPX0，CMPX1でそれぞれ交換が起こった場合に１を出力するようにして交換フラグレジスタＸＦの値とＯＲ演算器５０１で論理和をとりパイプラインレジスタ４１２に出力し、その値と比較交換演算器CMPX2，CMPX3でそれぞれ交換が起こった場合に１を出力するようにしてＯＲ演算器５０１で論理和をとり交換フラグレジスタＸＦに出力することにより、比較交換手段１０３の比較交換演算器CMPX0，CMPX1，CMPX2，CMPX3どれか1つでもデータの交換が成立したときに交換フラグレジスタＸＦ1が１にセットされるようにすることができる。
【００１９】
次に、本実施例におけるソート処理装置の動作を説明する。
図６は、本実施例におけるソート処理装置の処理方法を昇順のソートについて示すフローチャートである。まず、交換フラグレジスタＸＦの値を０クリアしてまたデータメモリ３０１におけるソート対象データの先頭アドレスｘと末尾アドレスｙを設定しソート対象データの範囲を初期設定する（ステップＳ６１）。次に、ｘの値とｙの値を比較することによりソート対象のデータが存在するかを判断し（ステップＳ６２）、ｘ＞ｙの時はデータが存在するとして次のステップに移り、それ以外は終了する。データがあるときは未ソートのデータの先頭アドレスを表すｔにｘを代入し（ステップＳ６３）、データメモリ３０１のアドレスのｔからｔ＋２番地の３値のデータを選択しデータメモリ３０１から読み出し（ステップＳ６４）、選択した３値のデータを専用レジスタ１０２のＳＰＲ０〜２に読み込む（ステップＳ６５）。次に、データメモリ３０１のアドレスのｔ＋３番地のデータの値をＳＰＲ３に読み込み（ステップＳ６６）、ＳＰＲ０〜３のデータの値の４値を比較交換手段１０３により比較交換し最大値を持つデータと最小値を持つデータと交換フラグレジスタＸＦの値を決定し（ステップＳ６７）、最大値が格納されたＳＰＲ３のデータの値をアドレスのｔ番地に書き込み（ステップＳ６８）、ソート対象データの範囲のすべてのデータを比較交換済みかどうかをｔ+３の値とｙを比較することにより判断し（ステップＳ６９）、ｔ＋３＞ｙの時は比較交換済みでないとしてｔ＋１を新たにｔの値としてステップＳ６６に戻り（ステップＳ７０）、ｔ＋３＝ｙとなった時は比較交換済みとして次のステップＳ７１に進む。ソート対象データの範囲のすべてのデータを比較交換済みとなり、ソート対象データの範囲の内の値の小さい方から３個が確定し、３個のうち最小値はＳＰＲ２に格納されているため、ステップＳ７１では、順位が未確定なＳＰＲ０とＳＰＲ１のデータの値を２値比較交換器CMPX0，CMPX1，CMPX2，CMPX3のいずれかを使用して比較交換し小さい方をＳＰＲ１に格納し大きい方をＳＰＲ０に格納しまた交換フラグレジスタＸＦの値を決定する。次に、ＳＰＲ０，ＳＰＲ１，ＳＰＲ２のデータをデータメモリ３０１のアドレスのそれぞれｔ＋１，ｔ＋２，ｔ＋３番地に保存し（ステップＳ７２）、交換フラグレジスタＸＦの値が０かどうかでソート対象データの範囲のすべてのデータに対して一度も交換が発生しないかどうかを判断し（ステップＳ７３）、交換フラグレジスタＸＦの値が０の時は処理の途中でソートが完了したとして終了し、交換フラグレジスタＸＦの値が１の時は順位が確定したデータを除くためｙ−３の値を新たにｙとしてまた交換フラグレジスタＸＦの値を０クリアして（（ステップＳ７４）、次にステップＳ６２に戻る。
なお、ここでソートを小さい値から行う場合（昇順）とし説明したが、大きいほうから行う場合（降順）は、上述した図5のソート処理装置で最大値を持つデータと最小値を持つデータが決定された後、それぞれ専用レジスタ１０２のＳＰＲ２とＳＰＲ３に格納されるとし、ソート処理装置の処理方法の説明で「最大値」を「最小値」と、「最大値」を「最小値」をそれぞれと読み替え、ステップＳ７１で「小さい方」を「大きい方」と、「大きい方」を「小さい方」とそれぞれ読み替えればよい。
【００２０】
（評価実験）
本実施例のプロセッサで、従来のバブルソート方法と本発明の拡張バブルソート方法を比較した。ソート対象のデータ数ｎは８，１６，３２の３種類で、ハードウェア記述言語（ＨＤＬ）のシミュレーションにより、それぞれの方法による動作終了までのサイクル数を測定した。測定結果を図７に示す。拡張バブルソート方法により、従来のバブルソート方法の１／４程度の実行サイクル数でソートが完了した。
【００２１】
また、ＴＳＭＣ０．１８ミクロンのデザインルールで遅延優先の条件でＨＤＬより回路を合成した結果、回路規模として拡張バブルソート用に追加した比較交換器、専用レジスタ及び追加のパイプラインレジスタの面積比率は全体の１３％程度となった。
【００２２】
従って、従来のバブルソート方法に比べて顕著な処理速度の向上が得られかつハードウェア量の増加は１３％程度に抑えることができることがわかった。
【符号の説明】
【００２３】
１０１  データメモリ
１０２  専用レジスタ
１０３  比較交換手段
１０４  制御部
１１１  比較交換演算器
１１２  レジスタ
１１３  比較交換演算器
【図１】
2010218178.tif 000003
【図２】
2010218178.tif 000004
【図３】
2010218178.tif 000005
【図４】
2010218178.tif 000006
【図５】
2010218178.tif 000007
【図６】
2010218178.tif 000008
【図７】
2010218178.tif 000009
【手続補正書】
【提出日】平成21年4月15日(2009.4.15)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図７
【補正方法】変更
【補正の内容】
【図７】
2010218178.tif 000010