(57)【要約】【課題】演算速度とリソース使用量を減らして効率の良いベクトルプロセッサの配列ソート方法を提供する。【解決手段】複数の要素を含むベクトルデータ形式の配列をロードする段階と、配列を半分に分割して第１グループを形成し、第１グループのｉ番目（ｉは自然数）の要素同士をソートする段階と、第ｎ（ｎは自然数）グループをそれぞれ半分に分割して第（ｎ＋１）グループを形成し、第（ｎ＋１）グループのうちの隣り合うグループのｊ番目（ｊは自然数）の要素同士をソートする段階と、第（ｎ＋１）グループが１つの要素のみを含む前まで、分割及び要素同士のソートを反復する段階と、第（ｎ＋１）グループが１つの要素のみを含むと、第（ｎ＋１）グループのうちの隣り合うグループの要素同士をソートする段階と、を有し、第１グループのｉ番目の要素同士をソートする段階は、ＳＩＭＤ処理方式で処理する段階を含む。【選択図】  図２
2018200692.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素（ｅｌｅｍｅｎｔ）を含むベクトルデータ形式の配列（ｓｅｑｕｅｎｃｅ）をロード（ｌｏａｄ）する段階と、
前記配列を半分に分割して第１グループを形成し、前記第１グループのｉ番目（ｉは自然数）の要素同士をソートする段階と、
第ｎ（ｎは自然数）グループをそれぞれ半分に分割して第（ｎ＋１）グループを形成し、前記第（ｎ＋１）グループのうちの隣り合うグループのｊ番目（ｊは自然数）の要素同士をソートする段階と、
前記第（ｎ＋１）グループが１つの要素のみを含む前まで、前記分割及び要素同士のソートを反復する段階と、
前記第（ｎ＋１）グループが１つの要素のみを含むと、前記第（ｎ＋１）グループのうちの隣り合うグループの要素同士をソートする段階と、を有し、
前記第１グループのｉ番目の要素同士をソートする段階は、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）処理方式で処理する段階を含む、ことを特徴とするベクトルプロセッサの配列ソート方法。
【請求項２】
前記配列は、Ｎ＝２ｎ個の要素を含むことを特徴とする請求項１に記載のベクトルプロセッサの配列ソート方法。
【請求項３】
前記分割及び要素同士のソートを反復する段階は、前記分割が前記第（ｎ＋１）グループを２２ｍ個に形成する分割である場合、前記要素同士のソートを最大２ｍ回行う段階を含むことを特徴とする請求項２に記載のベクトルプロセッサの配列ソート方法。
【請求項４】
前記要素同士のソートを２ｍ回行う段階は、全体グループのうちの隣り合うグループの要素同士のソートを行う第１ソートを行う段階と、
前記第１ソートの後に、前記全体グループのうち、１番目のグループと最後のグループを除いて残りのグループにおける隣り合うグループの要素同士のソートを行う第２ソートを行う段階と、
前記第１及び第２ソートを行う段階を、ｍ回繰り返すことを特徴とする請求項３に記載のベクトルプロセッサの配列ソート方法。
【請求項５】
前記配列をロードする段階は、互いに同じ大きさの第１及び第２配列をロードする段階を含み、
前記第１配列を第１グループと第２グループに分割する段階と、
前記第２配列を第３グループと第４グループに分割する段階と、
前記第１グループと第３グループとを連結した第３配列、及び前記第２グループと前記第４グループとを連結した第４配列を定義する段階と、
前記第３及び第４配列をそれぞれソートする段階と、
前記第３配列を第５グループと第６グループに分割する段階と、
前記第４配列を第７グループと第８グループに分割する段階と、
前記第６グループと第７グループとを連結した第５配列を定義する段階と、
前記第５配列をソートして前記第５グループ、前記第５配列、及び前記第８グループの順にソートを完成する段階と、をさらに有し、
前記第３配列をソートする段階は、前記分割及び要素同士のソートを反復する段階を含むことを特徴とする請求項１に記載のベクトルプロセッサの配列ソート方法。
【請求項６】
前記ベクトルプロセッサは、それぞれ別途のファンクションユニットを含む複数のスロットを含み、
前記第３及び第４配列をソートする段階は、前記第３及び第４配列を互いに異なるスロットのファンクションユニットを用いてソートする段階を含むことを特徴とする請求項５に記載のベクトルプロセッサの配列ソート方法。
【請求項７】
前記ベクトルプロセッサは、ＶＬＩＷ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ）インストラクションを行い、
前記ＶＬＩＷインストラクションは、第１及び第２インストラクションを含み、前記第１及び第２インストラクションは、それぞれ前記第３及び第４配列をソートするインストラクションであり、
前記第３及び第４配列をソートする段階は、前記第１及び第２インストラクションが、前記互いに異なるスロットのファンクションユニットに伝達され、前記互いに異なるスロットのファンクションユニットがそれぞれ前記第３及び第４配列をソートする段階を含むことを特徴とする請求項６に記載のベクトルプロセッサの配列ソート方法。
【請求項８】
前記第４及び第５配列をソートする段階は、それぞれ、前記（第４又は第５）配列を半分に分割してグループを形成し、前記グループのｋ番目（ｋは自然数）の要素同士をソートする段階と、
前記グループをそれぞれ半分に分割して新しいグループを形成し、前記新しいグループのうちの隣り合うグループのｌ番目（ｌは自然数）の要素同士をソートする段階と、
前記新しいグループが１つの要素のみ含む前まで、前記分割及び要素同士のソートを反復する段階と、
前記新しいグループが１つの要素のみを含むと、前記新しいグループのうちの隣り合うグループの要素同士をソートする段階を含むことを特徴とする請求項５に記載のベクトルプロセッサの配列ソート方法。
【請求項９】
前記配列を半分に分割して第１グループを形成し、前記第１グループのｉ番目の要素同士をソートする段階は、パーミュテーション（ｐｅｒｍｕｔａｔｉｏｎ）演算を用いて、前記配列と順序が変更されたコピー配列を生成する段階と、
前記配列と前記コピー配列に対してＭｉｎ演算及びＭａｘ演算を行う段階と、を含むことを特徴とする請求項１に記載のベクトルプロセッサの配列ソート方法。
【請求項１０】
前記Ｍｉｎ演算及びＭａｘ演算は同時に行われることを特徴とする請求項９に記載のベクトルプロセッサの配列ソート方法。
【請求項１１】
Ｎ個（Ｎは２ｎ、ｎは自然数）の要素を含むベクトルデータ形式の配列をロードする（ａ）段階と、
前記配列を、それぞれ互いに同じＮ／（２ｎ）個の要素を有するグループにグループ化し、それぞれのグループのうちの隣り合うグループ同士でｉ番目（ｉはＮ／（２ｎ）よりも小さい自然数）の要素をソートする（ｂ）段階と、を有し、
前記（ｂ）段階は、パーミュテーション演算を用いて、前記配列と順序が変わったコピー配列を生成する（ｃ）段階と、
前記配列と前記コピー配列に対してＭｉｎ演算及びＭａｘ演算を行う（ｄ）段階とを含み、
前記それぞれのグループのうちの隣り合うグループ同士でｉ番目の要素をソートする段階は、ＳＩＭＤ処理方式で処理する段階を含むことを特徴とするベクトルプロセッサの配列ソート方法。
【請求項１２】
前記（ｃ）段階の前記コピー配列は、前記配列における、前記グループのうち互いに要素をソートする隣接グループ同士の位置が互いに変更された配列であることを特徴とする請求項１１に記載のベクトルプロセッサの配列ソート方法。
【請求項１３】
前記（ｄ）段階で、前記配列における互いにＭｉｎ演算及びＭａｘ演算を行わない部分は、前記コピー配列及び前記配列で互いに同一の要素を有することを特徴とする請求項１２に記載のベクトルプロセッサの配列ソート方法。
【請求項１４】
前記（ｂ）段階は、ｎ＝１、２、…、ｌｏｇ２Ｎのときのそれぞれに対して繰り返し行われることを特徴とする請求項１１に記載のベクトルプロセッサの配列ソート方法。
【請求項１５】
前記（ｂ）段階は、ｎ＝１のときに対しては１回、
ｎ＝２、…、ｌｏｇ２Ｎのときに対してはそれぞれ２（ｎ−１）回反復して隣接グループ同士で要素をソートする段階を含むことを特徴とする請求項１４に記載のベクトルプロセッサの配列ソート方法。
【請求項１６】
２（ｎ−１）回反復して隣接グループ同士で要素をソートする段階は、全体グループのうち、隣り合うグループの要素同士のソートを行う第１ソート段階と、
前記全体グループのうち、１番目のグループと最後のグループを除いて残りのグループにおける隣り合うグループの要素同士のソートを行う第２ソート段階と、
前記第１ソート段階及び第２ソート段階を最大（ｎ−１）回繰り返す段階と、を含むことを特徴とする請求項１５に記載のベクトルプロセッサの配列ソート方法。
【請求項１７】
前記配列は、互いに同じ大きさの前半部と後半部を含み、
前記（ｄ）段階は、コントロールシグナルベクトルによってｍｉｎ値とｍａｘ値を選択するＭｉｎ演算及びＭａｘ演算を使用し、
前記コントロールシグナルベクトルは、前記前半部及び後半部に互いに異なる値を有することを特徴とする請求項１１に記載のベクトルプロセッサの配列ソート方法。
【請求項１８】
前記Ｍｉｎ演算及びＭａｘ演算は、減算器と、
前記減算器の出力、前記コントロールシグナルベクトル、及び前記配列及び前記コピー配列の要素を入力として、前記配列及び前記コピー配列の要素のうちのいずれかを出力するマルチプレクサとを含むＭｉｎ／Ｍａｘ回路によって演算されることを特徴とする請求項１７に記載のベクトルプロセッサの配列ソート方法。
【請求項１９】
それぞれ別個の演算ユニットを含む複数のスロットと、前記複数のスロットが互いに共有するレジスタとを含むベクトルプロセッサの配列ソート方法において、
Ｎ個（Ｎは２ｎ、ｎは自然数）の要素を含むベクトルデータ形式の配列をロードする（ａ）段階と、
前記配列を、それぞれ互いに同じＮ／（２ｎ）個の要素を有するグループにグループ化し、それぞれのグループのうちの隣り合うグループ同士でｉ番目（ｉは自然数）の要素をソートする（ｂ）段階と、を有し、
前記（ｂ）段階は、前記複数のスロットによって並列処理され、
前記ソートは、ＳＩＭＤ処理方式で処理されることを特徴とするベクトルプロセッサの配列ソート方法。
【請求項２０】
前記（ｂ）段階は、ｎ＝１、２、…、ｌｏｇ２Ｎのときのそれぞれに対して繰り返し行われることを特徴とする請求項１９に記載のベクトルプロセッサの配列ソート方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルプロセッサの配列ソート方法に関し、特に、演算速度とリソース使用量を減らして効率を向上したベクトルプロセッサの配列ソート方法に関する。
【背景技術】
【０００２】
降順や昇順などの配列（ｓｅｑｕｅｎｃｅ）のソートは、多くのシステムで使用される基本的な関数である。
クイックソートのように「Ｏ（ｎｌｏｇ（ｎ））」の演算複雑度を持つ速いソートは、個別的な要素を操作する方式なので、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）やＳＩＭＴ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｔｈｒｅａｄ）を用いるベクトルプロセッサに適用するには困難がある。
【０００３】
このため、ほとんどのベクトルプロセッサやマルチコアではマージソート（ｍｅｒｇｅ  ｓｏｒｔｉｎｇ）を多く使用するが、マージソートは、既にソートされたデータに対して速い特性を持っているので、併合以前にグループ化された要素の速いソートが必要である。
一般に、バイナリツリー構造のマージソートを使用する場合、その複雑度はデータ集合サイズ（Ｎ）の「Ｏ（Ｎｌｏｇ２Ｎ）」に比例する。
【０００４】
図１は、従来の一般なマージソートを説明するための図である。
図１では要素の個数Ｎ＝８の配列を昇順にソートする方法を例示的に示している。
図１を参照すると、マージソートは配列をまず分割（ｄｉｖｉｄｅ）する。
既存のスカラプロセッサでは、分割することも別に作業が必要であるが、ベクトルプロセッサでは、それぞれの要素がベクトル構造で連結されているので、分割作業を別に必要としないこともある。
よって、Ｎ個の要素からなる配列のローディングのみで分割作業は完了でき得る。
【０００５】
次いで、分割された要素のうち、隣り合う要素同士がソートをする。
これをマージ（ｍｅｒｇｅ）段階といい、細分化してマージ段階中の統治（Ｃｏｎｑｕｅｒ）段階と命名することができる。
つまり、「８」と「３」の場合は、「３」が「８」よりも小さいので、順序が変わって「３８」にソートできる。「２」と「９」の場合は、「２」が「９」よりも小さいので、そのまま「２９」にソートされる。
このとき、それぞれの要素をバッファに取り込んで呼び出さなければならないので、Ｎ回の呼び出しレベルが達成される。
すなわち、最大Ｎ、Ｏ（Ｎ）の複雑度を持ち得る。
【０００６】
続いて、ソートされた部分配列同士を結合（ｃｏｍｂｉｎｅ）する。
このような結合段階は、マージ段階中の一部であり得る。
このとき、隣り合うサブ配列である「３８」と「２９」はソートされた「２３８９」に結合され、「１７」と「４５」は「１４５７」と結合され得る。
このとき、「３８」と「２９」との結合は、「３」と「２」、「９」を比較し、「８」と「９」を比較する３回の比較が必要なので、３回の呼び出しレベルが必要である。
また、「１７」と「４５」の結合は、「１」と「４」、「５」を比較し、「７」と「４」、「５」を比較しなければならないので、４回の呼び出しレベルが必要である。
つまり、２つの配列同士の比較は、最悪の場合には４の呼び出しレベルが必要なので、全体的に最大８の呼び出しレベルが必要である。
すなわち、複雑度はＯ（Ｎ）になり得る。
【０００７】
最後に、「２３８９」と「１４５７」とを結合する場合、「２」は「１」、「４」、「５」、「７」と比較し、「３」は「４」、「５」、「７」と比較し、「８」は「４」、「５」、「７」と比較するが、「９」はあえて比較する必要がない。
但し、配列の配置が異なる場合、最大Ｎ回の比較が必要であり、この場合にも、複雑度はＯ（Ｎ）になり得る。
よって、それぞれの段階で最大Ｎ回の呼び出しレベルが必要であり、各段階の複雑度はＯ（Ｎ）であると見られる。
【０００８】
Ｎ個の配列が２個ずつに分けられて一つの要素に分解されることはｌｏｇ２（Ｎ）回行われ、逆に、それぞれの要素が全体のソートされた配列に結合されることもｌｏｇ２（Ｎ）回行われ得る。
よって、最悪の場合、全体的にＮ×ｌｏｇ２（Ｎ）回の呼び出しレベルが必要である。
これは、全体的なマージソートの複雑度がＯ（Ｎ×ｌｏｇ２（Ｎ））の複雑度を持つことを意味し、これは効率の悪い演算であり、より効率の良い演算が課題となっている。
したがって、このような高い複雑度のソート方式よりもさらに低い複雑度のソート方式を使用できれば、演算速度及びメモリなどのリソース使用量を減らして効率の良い演算が可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は上記従来の配列ソート方法における問題点に鑑みてなされたものであって、本発明の課題は、演算速度とリソース使用量を減らして効率の良いベクトルプロセッサの配列ソート方法を提供することにある。
【課題を解決するための手段】
【００１０】
上記課題を達成するためになされた本発明によるベクトルプロセッサの配列ソート方法は、複数の要素（ｅｌｅｍｅｎｔ）を含むベクトルデータ形式の配列（ｓｅｑｕｅｎｃｅ）をロード（ｌｏａｄ）する段階と、前記配列を半分に分割して第１グループを形成し、前記第１グループのｉ番目（ｉは自然数）の要素同士をソートする段階と、第ｎ（ｎは自然数）グループをそれぞれ半分に分割して第（ｎ＋１）グループを形成し、前記第（ｎ＋１）グループのうちの隣り合うグループのｊ番目（ｊは自然数）の要素同士をソートする段階と、前記第（ｎ＋１）グループが１つの要素のみを含む前まで、前記分割及び要素同士のソートを反復する段階と、前記第（ｎ＋１）グループが１つの要素のみを含むと、前記第（ｎ＋１）グループのうちの隣り合うグループの要素同士をソートする段階と、を有し、前記第１グループのｉ番目の要素同士をソートする段階は、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）処理方式で処理する段階を含む、ことを特徴とする。
【００１１】
また、上記課題を達成するためになされた本発明によるベクトルプロセッサの配列ソート方法は、Ｎ個（Ｎは２ｎ、ｎは自然数）の要素を含むベクトルデータ形式の配列をロードする（ａ）段階と、前記配列を、それぞれ互いに同じＮ／（２ｎ）個の要素を有するグループにグループ化し、それぞれのグループのうちの隣り合うグループ同士でｉ番目（ｉはＮ／（２ｎ）よりも小さい自然数）の要素をソートする（ｂ）段階と、を有し，前記（ｂ）段階は、パーミュテーション演算を用いて、前記配列と順序が変わったコピー配列を生成する（ｃ）段階と、
前記配列と前記コピー配列に対してＭｉｎ演算及びＭａｘ演算を行う（ｄ）段階とを含み、
前記それぞれのグループのうちの隣り合うグループ同士でｉ番目の要素をソートする段階は、ＳＩＭＤ処理方式で処理する段階を含むことを特徴とする。
【００１２】
また、上記課題を達成するためになされた本発明によるベクトルプロセッサの配列ソート方法は、それぞれ別個の演算ユニットを含む複数のスロットと、前記複数のスロットが互いに共有するレジスタとを含むベクトルプロセッサの配列ソート方法において、Ｎ個（Ｎは２ｎ、ｎは自然数）の要素を含むベクトルデータ形式の配列をロードする（ａ）段階と、前記配列を、それぞれ互いに同じＮ／（２ｎ）個の要素を有するグループにグループ化し、それぞれのグループのうちの隣り合うグループ同士でｉ番目（ｉは自然数）の要素をソートする（ｂ）段階と、を有し、前記（ｂ）段階は、前記複数のスロットによって並列処理され、前記ソートは、ＳＩＭＤ処理方式で処理されることを特徴とする。
【発明の効果】
【００１３】
本発明に係るベクトルプロセッサの配列ソート方法によれば、既存のマージソートの複雑度に比べて一層低い複雑度を持つことができるという効果がある。
【図面の簡単な説明】
【００１４】
【図１】従来のマージソートの一例を説明するための図である。
【図２】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するためのフローチャートである。
【図３ａ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【図３ｂ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【図３ｃ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【図３ｄ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【図４】本発明の実施形態に係るベクトルプロセッサの配列ソート方法が実行されるベクトルプロセッサの構造を説明するためのブロック図である。
【図５】図４のベクトルプロセッサの構造を説明するためのブロック図である。
【図６】本発明の実施形態に係るベクトルプロセッサのデータ移動アーキテクチャの概念を説明するための図である。
【図７】本発明の実施形態に係るベクトルプロセッサの配列ソート方法に使用されるパーミュテーション回路を説明するための図である。
【図８】本発明の実施形態に係るベクトルプロセッサの配列ソート方法に使用されるＭｉｎ／Ｍａｘ回路を説明するための図である。
【図９】本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【図１０】本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンドセットを説明するための表である。
【図１１ａ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンド使用を説明するための例示図である。
【図１１ｂ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンド使用を説明するための例示図である。
【図１１ｃ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンド使用を説明するための例示図である。
【図１１ｄ】本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンド使用を説明するための例示図である。
【発明を実施するための形態】
【００１５】
次に、本発明に係るベクトルプロセッサの配列ソート方法を実施するための形態の具体例を図面を参照しながら説明する。
【００１６】
以下、図２及び図３ａ〜図３ｄを参照して、本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明する。
図２は本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するためのフローチャートであり、図３ａ〜図３ｄは本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
図３ａ〜図３ｄでは、１６個の要素を有する配列をソートすることを例示的に示す。但し、これに限定されない。
【００１７】
図２を参照すると、まず、ベクトルデータを入力する（ステップＳ１００）。
ベクトルデータはソートされていない配列データであり得る。
ソートされていない配列データは、合計Ｎ個の要素を有する。
このとき、Ｎ＝２ｎ、ここで、ｎは自然数であり得る。但し、これに限定されない。
Ｎが２ｎではない場合には、ダミー要素が加わって２ｎの形式に合わせられ得る。
それぞれのＮ個の要素は、互いに異なるＳＩＭＤレーンで演算できる。
よって、配列のＳＩＭＤレーン数はＮ個以上であり得る。
【００１８】
具体的には、図３ａを参照すると、例示的に、０〜Ｆの合計１６個の要素を有する配列を入力することができる。
これは一つの例示に過ぎず、本発明における要素の個数は限定されない。
このとき、入力は、新たにデータを入力するか、予め格納されたメモリからデータをロードすることを含む。
図３ａでは、例示的に［１、６、１４、３、１２、１０、１５、５、７、２、８、１１、１６、４、１３、９］の配列をソートすることを示す。
【００１９】
再び図２を参照すると、配列を二つのグループに分離する（ステップＳ２００）。
具体的には、図３ａを参照すると、第１段階（Ｓｔａｇｅ１）で、配列は第（１−１）  グループＧ（１−１）と第（１−２）グループＧ（１−２）に分離する。
第（１−１）グループＧ（１−１）及び第（１−２）グループＧ（１−２）は、配列が半分に分けられて形成される。
よって、第（１−１）グループＧ（１−１）及び第（１−２）グループＧ（１−２）はそれぞれＮ／２、すなわち８つの要素を有する。
分けられた第（１−１）グループＧ（１−１）及び第（１−２）グループＧ（１−２）は、それぞれ“０”〜“７”の番号を持つ要素を有する。
追って、それぞれの同じ番号の要素同士で比較ソートを行う。
【００２０】
再び図２を参照すると、グループの各要素を比較する（ステップＳ３００）。
具体的に、図３ａを参照すると、第（１−１）グループＧ（１−１）と第（１−２）グループＧ（１−２）とを互いに比較する。
第（１−１）グループＧ（１−１）と第（１−２）グループＧ（１−２）との比較はそれぞれの要素の比較であり得る。
すなわち、第（１−１）グループＧ（１−１）の“０”〜“７”の番号を持つ要素と、第（１−２）グループＧ（１−２）の“０”〜“７”の番号を持つ要素とを互いに同じ番号同士で比較してソートすることを意味する。
【００２１】
つまり、例えば、第（１−１）グループＧ（１−１）の“０”番要素である「１」と、第（１−２）グループＧ（１−２）の“０”番要素である「７」とを比較する。
このとき、「１」が「７」よりも小さいので、お互いの位置はそのまま維持される。
一方、第（１−１）グループＧ（１−１）の“１”番要素である「６」と、第（１−２）グループＧ（１−２）の“１”番要素である「２」とを比較すると、「６」が「２」よりも大きいので、お互いの位置を入れ替える。つまり、
「２」は第（１−１）グループＧ（１−１）に属し、「６」は第（１−２）グループＧ（１−２）に属することになる。
このような方式によって、第１段階（Ｓｔａｇｅ１）で２つのグループを通じた要素ソートの結果、配列は［１、「２」、「８」、３、１２、「４」、「１３」、５、７、「６」、「１４」、１１、１６、「１０」、「１５」、９］にソートされる。
【００２２】
再び図２を参照すると、各グループの要素の個数が１個よりも大きいかを判断する（ステップＳ４００）。
これは追って１つの要素が残っているときまでグループを分割し続けるための判断段階である。
もし要素が１つだけ残っている場合、それ以上グループを分割することができないので、グループの分割を終了する。
図３ａを参照すると、各グループの要素が８個なので、１つよりも大きい。
よって、グループの分割が終了しない。
【００２３】
再び図２を参照すると、各グループを二つのサブグループに分割する（ステップＳ５００）。
具体的には、図３ｂを参照すると、第（１−１）グループＧ（１−１）は第（２−１）グループＧ（２−１）と第（２−２）グループＧ（２−２）に分割し、第（１−２）グループＧ（１−２）は第（２−３）グループＧ（２−３）と第（２−４）グループＧ（２−４）に分割する。
第（２−１）グループＧ（２−１）、第（２−２）グループＧ（２−２）、第（２−３）グループＧ（２−３）、及び第（２−４）グループＧ（２−４）は、それぞれ、第（１−１）グループＧ（１−１）及び第（１−２）グループＧ（１−２）の要素の個数の半分である４つの要素を有する。
第２段階（Ｓｔａｇｅ２）では、４つのグループの要素ソートを行う。
４つのグループは、それぞれ“０”から“３”までの番号を持つ４つの要素を有する。
【００２４】
再び図２を参照すると、１番目のグループからすぐ隣り合うグループの要素同士の比較を行う（ステップＳ６００）。
具体的には、図３ｂを参照すると、第（２−１）グループＧ（２−１）と第（２−２）グループＧ（２−２）とを互いに比較し、第（２−３）グループＧ（２−３）と第（２−４）グループＧ（２−４）を互いに比較する。
すなわち、第（２−１）グループＧ（２−１）と第（２−２）グループＧ（２−２）の同じ番号を持つ要素同士を互いに比較し、第（２−３）グループＧ（２−３）と第（２−４）グループＧ（２−４）の同じ番号を持つ要素同士を互いに比較する。
このような方式によって、配列は［１、２、８、３、１２、４、１３、５、７、６、１４、「９」、１６、１０、１５、１１］にソートされる。
【００２５】
再び図２を参照すると、２番目のグループから隣り合うグループ同士の比較を行う（ステップＳ７００）。
具体的には、図３ｂを参照すると、１番目のグループ及び最後のグループを除いて第（２−２）グループＧ（２−２）と第（２−３）グループＧ（２−３）の要素同士を互いに比較する。
これにより、配列は［１、２、８、３、「７」、４、１３、５、「１２」、６、１４、９、１６、１０、１５、１１］にソートされる。
【００２６】
再び図２を参照すると、比較の結果が以前と同一であるか否かを判断する（ステップＳ８００）。
もし比較結果が以前と同一である場合には、現在の段階、すなわち第２段階（Ｓｔａｇｅ２）が終了し、新しい段階、すなわち図３ｃの第３段階（Ｓｔａｇｅ３）に進行する。
第３段階（Ｓｔａｇｅ３）は、現在のグループが再び分割される段階を意味する。
具体的に、図３ｂを参照すると、配列は「７」と「１２」の部分がソートされて以前と同一ではないので、まだ第３段階（Ｓｔａｇｅ３）に進行せず、第２段階（Ｓｔａｇｅ２）にとどまる。
【００２７】
再び図２を参照すると、最大ソート回数に到達したか否かを判断する（ステップＳ９００）。
最大ソート回数とは、各段階ごとに、予め定められたソート回数分だけソートを行い、次の段階に進むように定義された値である。
最大ソート回数は、何番目の段階であるかによって定められ得る。
すなわち、第１段階（Ｓｔａｇｅ１）では１回の最大ソート回数を有し、第２段階（Ｓｔａｇｅ２）では２回の最大ソート回数を有する。
また、第３段階では４回の最大ソート回数を有し、第４段階（Ｓｔａｇｅ４）では６回の最大ソート回数を有することができる。
【００２８】
これを一般化すると、第１段階では１回の最大ソート回数を有し、第１段階を除く第ｋ段階では２×（ｋ−１）回の最大ソート回数を有することができる。
配列の要素の個数がＮ＝２ｎなので、第ｋ段階では、各グループは２（ｎｋ）個の要素を有し、２ｋ個のグループが形成され得る。
すなわち、図２のステップＳ８００及びステップＳ９００の段階を考察すると、最大ソート回数の範囲内でソートが予め終了することができる。
すなわち、これを複雑度に結び付けて考えてみると、最後の第ｎ段階では、複雑度がＯ（２×（ｌｏｇ２（Ｎ）−１））になる。
全体複雑度については後で再び説明する。
【００２９】
具体的には、図３ｂを参照すると、第２段階（Ｓｔａｇｅ２）は、最大ソート回数である２に達したので、さらにソートせずに、第３段階（Ｓｔａｇｅ３）に進む。
再び図２を参照すると、ステップＳ９００で最大ソート回数に到達したので、ステップを戻って、要素の個数が１つより大きいかを判断し（ステップＳ４００）、各グループを二つのサブグループに分割する（ステップＳ５００）。
【００３０】
具体的には、図３ｃを参照すると、第（２−１）グループＧ（２−１）は第（３−１）グループＧ（３−１）と第（３−２）グループＧ（３−２）に分割し、第（２−２）グループＧ（２−２）は第（３−３）グループＧ（３−３）と第（３−４）グループＧ（３−４）に分割する。
第（２−３）グループＧ（２−３）は第（３−５）グループＧ（３−５）と第（３−６）グループＧ（３−６）に分割し、第（２−４）グループＧ（２−４）は第（３−７）グループＧ（３−７）と第（３−８）グループＧ（３−８）に分割する。
第（３−１）グループＧ（３−１）、第（３−２）グループＧ（３−２）、第（３−３）グループＧ（３−３）、第（３−４）グループＧ（３−４）、第（３−５）グループＧ（３−５）、第（３−６）グループＧ（３−６）、第（３−７）グループＧ（３−７）、及び第（３−８）グループＧ（３−８）は、それぞれ、第（２−１）グループＧ（２−１）、第（２−２）グループＧ（２−２）、第（２−３）グループＧ（２−３）及び第（２−４）グループＧ（２−４）の要素の個数の半分である２つの要素を有する。
第３段階（Ｓｔａｇｅ３）では、８つのグループの要素ソートを行う。
８つのグループは、それぞれ“０”から“１”までの番号を持つ２つの要素を有する。
【００３１】
再び図２を参照すると、１番目のグループからすぐ隣り合うグループの要素同士の比較を行う（ステップＳ６００）。
具体的には、図３ｃを参照すると、第（３−１）グループＧ（３−１）と第（３−２）グループＧ（３−２）とを互いに比較し、第（３−３）グループＧ（３−３）と第（３−４）グループＧ（３−４）とを互いに比較する。
また、第（３−５）グループＧ（３−５）と第（３−６）グループＧ（３−６）とを互いに比較し、第（３−７）グループＧ（３−７）と第（３−８）グループＧ（３−８）とを互いに比較する。
すなわち、第（３−１）グループＧ（３−１）と第（３−２）グループＧ（３−２）の同じ番号を持つ要素同士を互いに比較し、第（３−３）グループＧ（３−３）と第（３−４）グループＧ（３−４）の同じ番号を持つ要素同士を互いに比較する。
また、第（３−５）グループＧ（３−５）と第（３−６）グループＧ（３−６）の同じ番号を持つ要素同士を互いに比較し、第（３−７）グループＧ（３−７）と第（３−８）グループＧ（３−８）の同じ番号を持つ要素同士を互いに比較する。
このような方式によって、配列は［１、２、８、３、「７」、４、１３、５、「１２」、６、１４、９、「１５」、１０、「１６」、１１］にソートされる。
【００３２】
再び図２を参照すると、２番目のグループから隣り合うグループ同士の比較を行う（ステップＳ７００）。
具体的には、図３ｃを参照すると、１番目のグループ及び最後のグループを除いて第（３−２）グループＧ（３−２）と第（３−３）グループＧ（３−３）の要素同士を互い比較し、第（３−４）グループＧ（３−４）と第（３−５）グループＧ（３−５）の要素同士を互いに比較し、第（３−６）グループＧ（３−６）と第（３−７）グループＧ（３−７）の要素同士を互いに比較する。
これにより、配列は［１、２、「７」、３、「８」、４、「１２」、５、「１３」、６、１４、９、「１５」、１０、「１６」、１１］にソートされる。
【００３３】
再度図２及び図３ｃを参照すると、比較結果が以前と同一ではなく（ステップＳ８００）、最大ソート回数（第３段階では４回の最大ソート回数）に達してもいない（ソート２回）ので（ステップＳ９００）、ステップを戻り、再び１番目のグループから隣り合うグループの要素比較を行う（ステップＳ６００）。
これにより、配列は［１、２、７、３、８、４、１２、５、１３、６、１４、９、１５、１０、１６、１１］にソートされる。
上述した説明では、比較結果が以前と同一であるか否かを判断する段階（ステップＳ８００）がステップＳ６００とステップＳ７００の２つの段階をすべて経た後に行われるようにしたが、これに限定されない。
ステップＳ８００段階は、ステップＳ６００段階とステップＳ７００段階との間で行われてもよく、ステップＳ７００段階の直後に行われてもよく、ステップＳ６００段階とステップＳ７００段階が行われた直後ごとに行われてもよい。
ソートされた配列が以前結果と同一なので、第３段階（Ｓｔａｇｅ３）は終了し、第４段階に進行する。
このとき、最大ソート回数には到達していないが、これを判断する必要はない。
【００３４】
再び図２を参照すると、再びステップを戻って、要素の個数が１つより大きいかを判断し（ステップＳ４００）、各グループを二つのサブグループに分割する（ステップＳ５００）。
具体的に、図３ｄを参照すると、それぞれのグループはそれぞれ１つの要素に分割される。
つまり、要素１個が自らがグループを成す。よって、合計１６個のグループがあり、グループはそれぞれ１つの要素を有する。
【００３５】
再び図２を参照すると、１番目のグループからすぐ隣り合うグループの要素同士の比較を行う（ステップＳ６００）。
具体的に、図３ｄを参照すると、例えば、「１」と「２」とを比較し、「７」と「３」とを比較する。
このように、順次隣り合う要素同士を互いに比較してソートする。
このような方式によって、配列は［１、２、「３」、「７」、「４」、「８」、「５」、「１２」、「６」、「１３」、「９」、「１４」、「１０」、「１５」、「１１」、「１６」］にソートされる。
【００３６】
再び図２を参照すると、２番目のグループから隣り合うグループ同士の比較を行う（ステップＳ７００）。
具体的に、図３ｄを参照すると、１番目の要素及び最後の要素を除いて、隣接する要素を互いに比較する。
例えば、「２」と「３」とを比較し、「７」と「４」とを比較する。
このような方式によって、配列は［１、２、３、「４」、「７」、「５」、「８」、「６」、「１２」、「９」、「１３」、「１０」、「１４」、「１１」、「１５」、１６］にソートされる。
【００３７】
図２及び図３ｄを参照すると、比較結果が以前と同一ではなく（ステップＳ８００）、最大ソート回数（第４段階では６回の最大ソート回数）に到達してもいないので（ステップＳ９００）、再びステップを戻って、１番目のグループから隣り合うグループの要素の比較を行う（ステップＳ６００）。
これにより、配列は［１、２、３、４、「５」、「７」、「６」、「８」、「９」、「１２」、「１０」、「１３」、「１１」、「１４」、１５、１６］にソートされる。
【００３８】
再び図２を参照すると、２番目のグループから隣り合うグループ同士の比較を行う（ステップＳ７００）。
具体的に、図３ｄを参照すると、１番目の要素と最後の要素を除いて、隣接する要素を互いに比較する。
たとえば、「２」と「３」とを比較し、「４」と「５」とを比較する。
このような方式によって、配列は［１、２、３、４、５、「６」、「７」、「８」、「９」、「１０」、「１２」、「１１」、「１３」、１４、１５、１６］にソートされる。
【００３９】
図２及び図３ｄを参照すると、比較結果が以前と同一ではなく（ステップＳ８００）、最大ソート回数に達してもいないので（ステップＳ９００）、再びステップを戻って、１番目のグループから隣り合うグループの要素比較を行う（ステップＳ６００）。
これにより、配列は［１、２、３、４、５、６、７、８、９、１０、「１１」、「１２」、１３、１４、１５、１６］にソートされる。
【００４０】
再び図２を参照すると、２番目のグループから隣り合うグループ同士の比較を行う（ステップＳ７００）。
具体的には、図３ｄを参照すると、１番目の要素と最後の要素を除いて、隣接する要素を互いに比較する。
たとえば、「２」と「３」とを比較し、「４」と「５」とを比較する。
このような方式により、配列は［１、２、３、４、５、６、７、８、９、１０、１１、１２、１３、１４、１５、１６］にソートされる。
【００４１】
再び図２を参照すると、比較結果が以前と同一であり（ステップＳ８００）、要素の個数が１よりも大きくないので（ステップＳ４００）、ソートを終了する。
【００４２】
図３ａ〜図３ｄ及び図２を参照すると、配列全体の大きさはＮ＝２ｎので、第１段階（Ｓｔａｇｅ１）を除いた第ｋ段階でのソート回数は最大２×（ｋ−１）回であり、最後の第ｎ段階での最大ソート回数はｎ＝ｌｏｇ２（Ｎ）によって２×（ｌｏｇ２（Ｎ）−１）になる。
したがって、第１段階（Ｓｔａｇｅ１）を除いた全体ソート回数は、数列の和によって、２＋４＋６＋…＋２×（ｌｏｇ２（Ｎ）−１）＝［２＋２×｛ｌｏｇ２（Ｎ）−１｝］×｛ｌｏｇ２（Ｎ）−１｝／２で表すことができ、第１段階（Ｓｔａｇｅ１）の１番を加えると、１＋２＋４＋６＋…＋２×（ｌｏｇ２（Ｎ）−１）＝１＋［２＋２×｛ｌｏｇ２（Ｎ）−１｝］×｛ｌｏｇ２（Ｎ）−１｝／２≒｛ｌｏｇ２（Ｎ）｝２であって、近似が可能である。
したがって、本発明の実施形態に係るベクトルプロセッサの配列ソート方法は、既存のマージソートのＯ（Ｎ×ｌｏｇ２（Ｎ））の複雑度に比べて一層低いＯ（｛ｌｏｇ２（Ｎ）｝２）の複雑度を持つことができる。
【００４３】
図３ａ〜図３ｄ及び図２では、トップダウン（ｔｏｐ  ｄｏｗｎ）方式で漸次分解するソートを説明したが、これとは逆に、ボトムアップ（ｂｏｔｔｏｍ  ｕｐ）方式でもソートを行うことができる。
ボトムアップ方式の場合にも、従来のマージソートのＯ（Ｎ＊ｌｏｇ２（Ｎ））の複雑度に比べて一層低いＯ（｛ｌｏｇ２（Ｎ）｝２）の複雑度を持つことができるので、ソートの効率を高めることができる。
【００４４】
以下、図４〜図６を参照して、本発明の実施形態に係るベクトルプロセッサの配列ソート方法が実行されるベクトルプロセッサを説明する。
図４は本発明の実施形態に係るベクトルプロセッサの配列ソート方法が実行されるベクトルプロセッサの構造を説明するためのブロック図であり、図５は図４のベクトルプロセッサの構造を説明するためのブロック図であり、図６は本発明の実施形態に係るベクトルプロセッサのデータ移動アーキテクチャの概念を説明するための図である。
【００４５】
図４を参照すると、ベクトルプロセッサは、プロセッサ２００、コントローラ３００、及びメモリバス１００を含む。
プロセッサ２００は、算術演算を行うプロセッサである。
本発明の実施形態において、プロセッサ２００は、予測（ｐｒｅｄｉｃｔｉｏｎ）演算、ベクトルパーミュート（ｖｅｃｔｏｒ  ｐｅｒｍｕｔｅ）演算、ベクトルビット操作（ｖｅｃｔｏｒ  ｂｉｔ  ｍａｎｉｐｕｌａｔｉｏｎ）演算、バタフライ（ｂｕｔｔｅｒｆｌｙ）演算、ソート（ｓｏｒｔｉｎｇ）演算などのベクトル特化コマンドを含むベクトル演算処理に特化したベクトルプロセッサで実現できる。
【００４６】
本発明の実施形態において、プロセッサ２００は、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）及び多重スロットＶＬＩＷ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ）構造を採用することができる。
プロセッサ２００は、レジスタ（２１２、２１４）を含み、レジスタ（２１２、２１４）を用いて算術演算を行う。
本発明の実施形態において、レジスタ（２１２、２１４）は、ＳＲ（Ｓｃａｌａｒ  Ｒｅｇｉｓｔｅｒ）２１２及びＶＲ（Ｖｅｃｔｏｒ  Ｒｅｇｉｓｔｅｒ）２１４のうちの少なくとも一つを含むことができる。
ここで、ＳＲ２１２はプロセッサ２００のスカラ演算に使用されるレジスタであり、ＶＲ２１４はプロセッサ２００のベクトル演算に使用されるレジスタである。
【００４７】
図５を参照すると、プロセッサ２００は、フェッチユニット２２０及びデコーダ２３０を含む。
デコーダ２３０は、フェッチユニット２２０から提供されたインストラクションをデコードする。
本発明の実施形態において、インストラクションは、ＶＬＩＷに応じて３つのスロット（ｓｌｏｔ）（２４０ａ、２４０ｂ、２４０ｃ）によって処理される。
例えば、フェッチユニット２２０からフェッチされたインストラクションが９６ビットである場合、デコーダ２３０は、フェッチされたインストラクションをそれぞれ３２ビットからなる３つのインストラクションにデコードし、３つのインストラクションは、それぞれのスロット（２４０ａ、２４０ｂ、２４０ｃ）によって処理される。
本実施形態では、説明のための一例として、フェッチされたインストラクションが３つのインストラクションにデコードされて３つのスロットによって処理するものを示したが、本発明の範囲はこれに限定されるものではなく、インストラクションは、２つ以上の任意の個数のスロットによって処理できるように実現してもよい。
【００４８】
本実施形態において、３つのスロット（２４０ａ、２４０ｂ、２４０ｃ）はすべて同時に実行可能であり、このような並列処理を効率よく行うために、スカラ機能ユニット（Ｓｃａｌａｒ  Ｆｕｎｃｔｉｏｎａｌ  Ｕｎｉｔ：ＳＦＵ）（２４２ａ、２４２ｂ、２４２ｃ）、ベクトル機能ユニット（Ｖｅｃｔｏｒ  Ｆｕｎｃｔｉｏｎａｌ  Ｕｎｉｔ：ＶＦＵ）（２４４ａ、２４４ｂ、２４４ｃ）、移動ユニット（ＭｏＶｅ  ｕｎｉｔ：ＭＶ）（２４６ａ、２４６ｂ、２４６ｃ）が３つのスロット（２４０ａ、２４０ｂ、２４０ｃ）に効率よく配置される。
具体的に、第１スロット２４０ａはＳＦＵ２４２ａ、ＶＦＵ２４４ａ、及びＭＶ２４６ａを含み、第２スロット２４０ｂはＳＦＵ２４２ｂ、ＶＦＵ２４４ｂ、及びＭＶ２４６ｂを含み、また、第３スロット２４０ｃはＳＦＵ２４２ｃ、ＶＦＵ２４４ｃ、及びＭＶ２４６ｃを含む。
そして、プロセッサ２００は、各スロット（２４０ａ、２４０ｂ、２４０ｃ）に含まれているＭＶ（２４６ａ、２４６ｂ、２４６ｃ）を用いてお互いのデータを共有することができる。
【００４９】
一方、ＳＦＵ（２４２ａ、２４２ｂ、２４２ｃ）によって処理された結果は、図４で説明したＳＲ２１２に格納し、ＶＦＵ（２４４ａ、２４４ｂ、２４４ｃ）によって処理された結果は、図４で説明したＶＲ２１４に格納する。
もちろん、ＳＲ２１２及びＶＲ２１４に格納された結果は必要に応じてプロセッサ２００によって使用できる。
しかし、図５に示した構成は、以下で本発明の様々な実施形態についての説明の便宜のための一例に過ぎなく、本発明の範囲がこれに限定されないのは当該技術分野における通常の技術者にとって自明である。
【００５０】
図６は、本発明の実施形態に係るベクトルプロセッサのデータ移動アーキテクチャの概念を説明するための図である。
図６を参照すると、本発明の実施形態に係るベクトルプロセッサのデータ移動アーキテクチャは、メモリ階層１０５、レジスタファイル１１０、データ配置レイヤー１３０、複数のＡＬＵ１６０、及びこれらの要素を全体的に制御する制御部１７０を含む。
ここで、メモリ階層１０５は、メモリインターフェース（ｍｅｍｏｒｙ  ｉｎｔｅｒｆａｃｅ）を提供する。
先立って図４に関連して説明したメモリ装置、メモリバス１００などがメモリ階層１０５に対応する。
【００５１】
レジスタファイル１１０は、図５に関連して先立って説明した、ＳＲ２１２及びＶＲ２１４を含むレジスタ（２１２、２１４）に対応する。
データ配置レイヤー１３０は、プロセッサ２００が処理するさまざまなサイズのデータ（例えば、マトリックス）に対する演算を効率よく行うためのデータパターンを生成する。
上記アーキテクチャは、複数のＡＬＵ１６０が共有することが可能なレジスタ（２１２、２１４）を用いて精巧なフロー制御及び複雑な算術演算の実行を可能にしながらも、データ配置レイヤー１３０を用いて、レジスタ（２１２、２１４）に格納されたデータをパターン化することにより、入力データの再使用性を向上させることができる。
【００５２】
図４〜図６のベクトルプロセッサを用いれば、本発明の実施形態に係る配列ソート方法はより効率よく演算できる。
つまり、図３ａ〜図３ｄに示した配列ソート方法は、それぞれのグループごとに、データ依存度なしでソートを同時に行うので、これをＶＬＩＷの並列処理で行うことができる。
すなわち、例えば、図３ｂに示した第（２−１）グループＧ（２−１）と第（２−２）グループＧ（２−２）のソート、及び第（２−３）グループＧ（２−３）と第（２−４）グループＧ（２−４）のソートは、互いにデータ依存度が全くないので、同時に互いに異なるスロットでこれを処理することができる。
これにより、一層速い速度と一層高い効率で配列のソートを完了することができる。
【００５３】
さらに、データ依存度のある順次演算でも、レジスタがそれぞれのスロットごとに共有されるので、メモリの呼び出しを必要とすることなく、互いに異なるスロットの機能ユニットが作業を互いに渡しながら完了することができる。
つまり、段階ごとに最適の演算を行うことができるスロットから作業を引き渡されて行うことができる。
これにより、全体的なソート演算の効率を大幅に高めることができる。
【００５４】
以下、図３ａ〜図３ｄ、図７及び図８を参照して、本発明の実施形態に係るベクトルプロセッサの配列ソート方法の演算について説明する。
図７は、本発明の実施形態に係るベクトルプロセッサの配列ソート方法に使用されるパーミュテーション回路を説明するための図であり、図８は、本発明の実施形態に係るベクトルプロセッサの配列ソート方法に使用されるＭｉｎ／Ｍａｘ回路を説明するための図である。
【００５５】
図７を参照すると、パーミュテーション回路は、ベクトルレジスタ２０、マルチプレクサ選択信号１０、及び第１〜第８マルチプレクサ（Ｍ１〜Ｍ８）を含む。
ベクトルレジスタ２０は、パーミュテーション回路に入力されるインプットデータ（Ｉ１〜Ｉ８）を提供し、追ってパーミュテーション回路から出力されるアウトプットデータ（Ｏ１〜Ｏ８）を格納する。
ベクトルレジスタ２０は、図４〜図６のＶＲ２１４又はレジスタファイル１１０に該当し得る。
ベクトルレジスタ２０は、マルチプレクサ選択信号１０も提供する。
これにより、第１〜第８マルチプレクサ（Ｍ１〜Ｍ８）は、インプットデータ（Ｉ１〜Ｉ８）を、マルチプレクサ選択信号１０によって配置を変えてアウトプットデータ（Ｏ１〜Ｏ８）として出力する。
【００５６】
本実施形態において、インプットデータ（Ｉ１〜Ｉ８）とアウトプットデータ（Ｏ１〜Ｏ８）が８つの要素を有するベクトルデータの形式を持ち、第１〜第８マルチプレクサ（Ｍ１〜Ｍ８）が８つのマルチプレクサを含むが、これは一つの例示に過ぎず、これらに限定されない。
つまり、ベクトルデータの個数やマルチプレクサの個数は必要に応じていくらでも変更できる。
インプットデータ（Ｉ１〜Ｉ８）とアウトプットデータ（Ｏ１〜Ｏ８）は、ベクトルデータであって、それぞれの要素が別個のＳＩＭＤレーンによって処理される。
これにより、ベクトルプロセッサは、スカラプロセスとは異なり、速い演算速度を示すことができる。
第１〜第８マルチプレクサ（Ｍ１〜Ｍ８）は、インプットデータ（Ｉ１〜Ｉ８）の８つの要素すべてを入力として受け、これをアウトプットデータ（Ｏ１〜Ｏ８）として出力する。
【００５７】
図８は、本発明の実施形態に係るベクトルプロセッサの配列ソート方法に使用されるＭｉｎ／Ｍａｘ回路を説明するための図である。
図８を参照すると、Ｍｉｎ／Ｍａｘ回路は、ベクトルレジスタ２０、ベクトルコントロールレジスタ３０、及びＭｉｎ／Ｍａｘ演算器４０を含む。
ベクトルレジスタ２０は、Ｍｉｎ／Ｍａｘ回路に入力されるＤ１とＤ２を提供し、追ってＭｉｎ／Ｍａｘ回路から出力されるＤ０を格納する。
ベクトルレジスタ２０は、図４〜図６のＶＲ２１４又はレジスタファイル１１０に該当する。
【００５８】
ベクトルコントロールレジスタ３０は、図８では別個に示したが、ベクトルレジスタ２０と統合されて構成されてもよい。
ベクトルコントロールレジスタ３０は、Ｍｉｎ／Ｍａｘ演算器のコントロール信号であるコントロールベクトルＶｃを格納し、これをＭｉｎ／Ｍａｘ演算器４０に提供する。
Ｍｉｎ／Ｍａｘ演算器４０は複数であり得る。
ＳＩＭＤ処理方式に応じて、Ｄ１、Ｄ２、及びＤ０がＮ個の要素を有するベクトルデータである場合、Ｍｉｎ／Ｍａｘ演算器４０もＮ個であり得る。
図では全部で１６個のＭｉｎ／Ｍａｘ演算器４０が示したが、これは一つの例示に過ぎず、これに限定されるものではない。
【００５９】
Ｍｉｎ／Ｍａｘ演算器４０は、Ｄ１とＤ２の要素それぞれを比較して最大値又は最小値を出力する。
このとき、最大値を出力するか、最小値を出力するかは、コントロールベクトルＶｃによって定められ得る。
Ｍｉｎ／Ｍａｘ演算器４０は、減算器４１とマルチプレクサ４３を含み得る。
減算器４１は、Ｄ１とＤ２の要素の入力を受けて両者間の差を出力する。
マルチプレクサ４３は、上記両者間の差の符号に応じて、Ｄ１とＤ２の要素のうち、どの値が最大値であるか、どの値が最小値であるかを判断する。
これはＤ１とＤ２の要素の差の符号情報を持っているＬＳＢ（ｌｅａｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ）によって容易に判断することができる。
このとき、コントロールベクトルＶｃがコントロール信号ｃｔｒｌとしてマルチプレクサ４３に入力され、これに応じて、Ｄ１及びＤ２のいずれかの値が最大値もしくは最小値として出力される。
【００６０】
本発明の実施形態に係るベクトルプロセッサの配列ソート方法は、パーミュテーション回路とＭｉｎ／Ｍａｘ回路を用いて要素同士のソートを行うことができる。
具体的には、図３ａ、図７及び図８を参照すると、提供される配列［１、６、１４、３、１２、１０、１５、５、７、２、８、１１、１６、４、１３、９］に対して、パーミュテーション回路はコピー配列［７、２、８、１１、１６、４、１３、９、１、６、１４、３、１２、１０、１５、５］を出力する。
つまり、インプットデータ（Ｉ１〜Ｉ８）は上記配列であり、アウトプットデータ（Ｏ１〜Ｏ８）は上記コピー配列であり得る。
このとき、マルチプレクサ選択信号１０は、［０、１、２、３、４、５、６、７、８、９、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ］の配列に対して、［８、９、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、０、１、２、３、４、５、６、７］で表され、これは２つのグループ、すなわち、第（１−１）グループＧ（１−１）と第（１−２）グループＧ（１−２）が位置を入れ替えたことを意味する。
【００６１】
また、ベクトルレジスタ２０は、このようなコピー配列を格納してＭｉｎ／Ｍａｘ回路に提供する。
Ｍｉｎ／Ｍａｘ回路は、配列［１、６、１４、３、１２、１０、１５、５、７、２、８、１１、１６、４、１３、９］をＤ１とし、コピー配列［７、２、８、１１、１６、４、１３、９、１、６、１４、３、１２、１０、１５、５］をＤ２とする。
これにより、Ｍｉｎ／Ｍａｘ演算器４０は第（１−１）グループＧ（１−１）と第（１−２）グループＧ（１−２）の同じ番号の要素同士の比較を行うことができる。
【００６２】
このとき、コントロールベクトルＶｃは、要素が「０」である場合にはｍｉｎ値、要素が「１」である場合にはｍａｘ値を意味するとすれば、［０、０、０、０、０、０、０、０、１、１、１、１、１、１、１、１］であり得る。もちろん、これは昇順の場合であり、降順の場合には、コントロールベクトルＶｃは［１、１、１、１、１、１、１、１、０、０、０、０、０、０、０、０］になる。
したがって、Ｄ０の前半部はｍｉｎ値が出力され、後半部はｍａｘ値が出力される。
すなわち、このようなパーミュテーション演算とＭｉｎ／Ｍａｘ演算を介して、グループソートの段階を単に２つの段階で簡単に行うことができる。
このようなＭｉｎ／Ｍａｘ回路とパーミュテーション回路は、単にマルチプレクサと減算器などの共用の演算装置を用いてＳＩＭＤ演算を行うので、ソートのための専用ハードウェアがなくても公共のベクトルプロセッサを介していくらでも実現できる。
さらに、上述した複雑度の面でも優れるので、非常に効率よくソートを行うことができる。
【００６３】
以下、図９を参照して、本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明する。
上述した説明と重複する部分は簡略にするか或いは省略する。
図９は、本発明の実施形態に係るベクトルプロセッサの配列ソート方法を説明するための図である。
【００６４】
図９を参照して、ＳＩＭＤレーンより多くのデータをソートする場合の配列ソート方法を説明する。
ＳＩＭＤレーンの個数が１６個であるとき、３２個の要素を有する配列をソートすることを想定する。
まず、３２個の要素なので、２つのベクトルデータに分けて入力する。
すなわち、それぞれ１６個の要素を有する第１配列Ｓ１と第２配列Ｓ２に入力或いはロードする。
第１配列Ｓ１と第２配列Ｓ２は、それぞれ、図３ａ〜図３ｄで説明した本発明の実施形態に係る配列ソート方法でそれぞれソートする。
このとき、本発明の実施形態に係るベクトルプロセッサは、互いに異なるスロットでＶＬＩＷモードにて第１配列Ｓ１及び第２配列Ｓ２を並列的にソートする。但し、これに限定されるものではない。
【００６５】
続いて、第１配列Ｓ１は、それぞれ８つの要素を有する第１グループＧ１及び第２グループＧ２と定義する。
第２配列Ｓ２は、それぞれ８つの要素を有する第３グループＧ３及び第４グループＧ４と定義する。
次いで、第１グループＧ１と第３グループＧ３とを連結する第３配列Ｓ３、及び第２グループＧ２と第４グループＧ４とを連結する第４配列Ｓ４を形成する。
続いて、第３配列Ｓ３と第４配列Ｓ４を、本発明の実施形態に係る配列ソート方法によってそれぞれソートする。
このとき、本発明の実施形態に係るベクトルプロセッサは、互いに異なるスロットでＶＬＩＷモードにて第３配列Ｓ３及び第４配列Ｓ４を並列的にソートする。但し、これに限定されるものではない。
【００６６】
ソートされた後の第３配列Ｓ３は、それぞれ８つの要素を有する第５グループＧ５と第６グループＧ６を含む。
また、ソートされた後の第４配列Ｓ４は、それぞれ８つの要素を有する第７グループＧ７と第８グループＧ８を含む。
次いで、第６グループＧ６と第７グループＧ７とを連結する第５配列Ｓ５を形成する。
続いて、第５配列Ｓ５を本発明の実施形態による配列ソート方法でソートする。
これにより、第５グループＧ５、第５配列Ｓ５、及び第８グループＧ８の順に、合計３２個の要素を有するデータがソートされる。
【００６７】
図１０は本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンドセットを説明するための表である。
一般なベクトルプロセッサは、ｍｉｎ値又はｍａｘ値の処理のための関数を支援するが、すべてのＳＩＭＤレーンに同じ演算が実行できる。
すなわち、全体レーンに対してｍｉｎ値及びｍａｘ値のうちのいずれか一つのみを見つける形式である。
この場合、同一演算をもう一度さらに行うことでｍｉｎ値とｍａｘ値をすべて見つけることができるので、追加のオーバーヘッドが発生する。
本発明では、ＳＩＭＤレーンの予測演算（ｐｒｅｄｉｃａｔｉｏｎ−ベクトルプロセッサのＳＩＭＤレーンのうち、特定のレーンのみ該当演算を行うこと）のために存在するベクトルコントロールレジスタを活用してｍｉｎ値とｍａｘ値を同時に処理することができる。
【００６８】
図１０を参照すると、図７及び図８で実現されたパーミュテーション又はＭｉｎ／Ｍａｘコマンドが実現されることが分かる。
以下、図１１ａ〜図１１ｄを参照して、図１０のコマンドと図７及び図８の回路を用いて配列をソートすることを説明する。
図１１ａ〜図１１ｄは、本発明の実施形態に係るベクトルプロセッサの配列ソート方法の実現のためのコマンド使用を説明するための例示図である。
図１１ａ〜図１１ｄは、図３ａ〜図３ｄのソートにコマンドに対する付加的な表示をした図である。
【００６９】
図１１ａを参照すると、まず、「ｌｄ」コマンドを用いてｖ３のベクトルをロードする。
このとき、ｖ３は図７のマルチプレクサ選択信号１０である。
すなわち、２つのグループの位置を互いに入れ替えるパーミュテーション演算のための第１〜第８マルチプレクサ（Ｍ１〜Ｍ８）の選択信号である。
続いて、「ｖｐｍｔ」コマンドを介してｖ１のコピー配列を形成する。
次いで、「ｌｄ」コマンドを介してｖｃをロードする。
ｖｃは図８のＭｉｎ／Ｍａｘ演算器４０のコントロールベクトルＶｃである。
すなわち、Ｍｉｎ／Ｍａｘ演算の出力結果、配列の前半部はｍｉｎ値（０）であり、後半部はｍａｘ値（１）であることを意味するベクトルである。
【００７０】
続いて、「ｖｍｉｎｍａｘ」コマンドを介して、ｖ１に、第１段階（Ｓｔａｇｅ１）のグループソートをした値を格納する。
次いで、４つのグループのために、ｖ３を再びロードし（「ｌｄ」コマンド）、これをパーミュテーションした結果をｖ２へ出力する（「ｖｐｍｔ」コマンド）。
続いて、ｖｃをロードし、２つのグループずつｍｉｎ値とｍａｘ値が表示されなければならないので、ｖｃは［０、０、０、０、１、１、１、１、０、０、０、０、１、１、１、１］のようにロードされる。
次に、ｖ０に再びＭｉｎ／Ｍａｘ演算値を格納する（「ｖｍｉｎｍａｘ」コマンド）。
このとき、それぞれのｌｄ、ｖｐｍｔ、ｖｍｉｎｍａｘなどのコマンドは、互いに異なるスロットによって動作することができる。それぞれのスロットは、レジスタを共有するので、メモリにオーバーヘッドを増加させずに並列処理が可能である。
【００７１】
図１１ｂを参照すると、これも同様の方式で、ｌｄ、ｖｐｍｔ、ｌｄ、ｖｍｉｎｍａｘのコマンドを実行する。
もしグループのうち１番目のグループと最後のグループが除かれてソートされる場合には、図７のマルチプレクサ選択信号１０のためのｖ３が［０、１、２、３、８、９、Ａ、Ｂ、４、５、６、７、Ｃ、Ｄ、Ｅ、Ｆ］のようにロードされる。
これは１番目のグループと最後のグループの要素を変えなくて、Ｍｉｎ／Ｍａｘ演算において１番目のグループ及び最後のグループの要素が変更されないようにするためである。
【００７２】
図１１ｃ及び図１１ｄにおいても、これらと同様にコマンドを用いて演算できる。
【００７３】
尚、本発明は、上述の実施形態に限られるものではない。本発明の技術的範囲から逸脱しない範囲内で多様に変更実施することが可能である。
【符号の説明】
【００７４】
１０    マルチプレクサ選択信号
２０    ベクトルレジスタ
３０    ベクトルコントロールレジスタ
４０    Ｍｉｎ／Ｍａｘ演算器
４１    減算器
４３    マルチプレクサ
１００    メモリバス
１０５    メモリ階層
１１０    レジスタファイル
１３０    データ配置レイヤー
１６０（１６０ａ〜ｄ）    ＡＬＵ
１７０    制御部
２００    プロセッサ
２１２    （ＳＲ）レジスタ
２１４    （ＶＲ）レジスタ
２２０    フェッチユニット
２３０    デコーダ
２４０ａ、２４０ｂ、２４０ｃ    （第１〜第３）スロット
２４２ａ、２４２ｂ、２４２ｃ    スカラ機能ユニット（ＳＦＵ）
２４４ａ、２４４ｂ、２４４ｃ    ベクトル機能ユニット（ＶＦＵ）
２４６ａ、２４６ｂ、２４６ｃ    移動ユニット（ＭＶ）
３００    コントローラ
【図１】
2018200692.tif 000003
【図２】
2018200692.tif 000004
【図３ａ】
2018200692.tif 000005
【図３ｂ】
2018200692.tif 000006
【図３ｃ】
2018200692.tif 000007
【図３ｄ】
2018200692.tif 000008
【図４】
2018200692.tif 000009
【図５】
2018200692.tif 000010
【図６】
2018200692.tif 000011
【図７】
2018200692.tif 000012
【図８】
2018200692.tif 000013
【図９】
2018200692.tif 000014
【図１０】
2018200692.tif 000015
【図１１ａ】
2018200692.tif 000016
【図１１ｂ】
2018200692.tif 000017
【図１１ｃ】
2018200692.tif 000018
【図１１ｄ】
2018200692.tif 000019