(57)【特許請求の範囲】
【請求項１】
クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを備え、
クロスポイントバッファの２ワード目以降の各クロスポイントバッファにシフト機能を実装し、
前記クロスバ入力バッファの要素が入力されるクロスポイントバッファの１ワード目のエントリに格納されている要素数が、前記１ワード目の要素が入力されるクロスポイントバッファの２ワード目のエントリに格納されている要素数より多い場合、シフト機能を利用しないことを選択する選択手段を含み、
前記シフト機能は、
クロスポイントバッファの２ワード目から、予め定められた優先順位に基づいて、発行すべき要素を選択し、
当該要素が発行されると、当該発行により空となったエントリに対して高優先順位側へ前記２ワード目の各要素をシフトし、１ワード目の最優先エントリを、前記シフトにより空となった前記２ワード目のエントリに入れ、
前記優先順位は、前記クロスバ入力バッファに到着した順に決定され、同時到着の要素については、入力バッファの若番順に決定される
ことを特徴とするクロスバスイッチ。
【請求項２】
クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを含むクロスバスイッチを備え、
前記クロスバスイッチの前記クロスポイントバッファの２ワード目以降の各クロスポイントバッファにシフト機能を実装し、
前記クロスバスイッチが、
前記クロスバ入力バッファの要素が入力されるクロスポイントバッファの１ワード目のエントリに格納されている要素数が、前記１ワード目の要素が入力されるクロスポイントバッファの２ワード目のエントリに格納されている要素数より多い場合、シフト機能を利用しないことを選択する選択手段を含み、
前記シフト機能は、
クロスポイントバッファの２ワード目から、予め定められた優先順位に基づいて、発行すべき要素を選択し、
当該要素が発行されると、当該発行により空となったエントリに対して高優先順位側へ前記２ワード目の各要素をシフトし、１ワード目の最優先エントリを、前記シフトにより空となった前記２ワード目のエントリに入れ、
前記優先順位は、前記クロスバ入力バッファにに到着した順に決定され、同時到着の要素については、入力バッファの若番順に決定される
ことを特徴とするベクトル処理装置。
【請求項３】
クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを備えるクロスバスイッチによるクロスバ制御方法であって、
クロスポイントバッファの２ワード目以降の各クロスポイントバッファにシフト機能を実装し、
前記クロスバ入力バッファの要素が入力されるクロスポイントバッファの１ワード目のエントリに格納されている要素数が、前記１ワード目の要素が入力されるクロスポイントバッファの２ワード目のエントリに格納されている要素数より多い場合、シフト機能を利用しないことを選択する選択ステップを、選択手段が実行し、
前記シフト機能は、
クロスポイントバッファの２ワード目から、予め定められた優先順位に基づいて、発行すべき要素を選択し、
当該要素が発行されると、当該発行により空となったエントリに対して高優先順位側へ前記２ワード目の各要素をシフトし、１ワード目の最優先エントリを、前記シフトにより空となった前記２ワード目のエントリに入れ、
前記優先順位は、前記クロスバ入力バッファにに到着した順に決定され、同時到着の要素については、入力バッファの若番順に決定される
ことを特徴とするクロスバ制御方法。
【請求項４】
クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを含むクロスバスイッチを備え、クロスポイントバッファの２ワード目以降の各クロスポイントバッファにシフト機能を実装するベクトル処理装置によるクロスバ制御方法であって、
前記クロスバ入力バッファの要素が入力されるクロスポイントバッファの１ワード目のエントリに格納されている要素数が、前記１ワード目の要素が入力されるクロスポイントバッファの２ワード目のエントリに格納されている要素数より多い場合、シフト機能を利用しないことを選択する選択ステップを、前記クロスバスイッチの選択手段が実行し、
前記シフト機能は、
クロスポイントバッファの２ワード目から、予め定められた優先順位に基づいて、発行すべき要素を選択し、
当該要素が発行されると、当該発行により空となったエントリに対して高優先順位側へ前記２ワード目の各要素をシフトし、１ワード目の最優先エントリを、前記シフトにより空となった前記２ワード目のエントリに入れ、
前記優先順位は、前記クロスバ入力バッファにに到着した順に決定され、同時到着の要素については、入力バッファの若番順に決定される
ことを特徴とするクロスバ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クロスバスイッチに関し、特に、クロスポイントバッファの利用効率向上に関する。
【背景技術】
【０００２】
ベクトル型コンピュータでは、クロスバを通過する通過順序を保証しつつ、クロスバで要素を調停しなければならないときがある。また、性能も必要とされるため、ハードウェア量をかけて、クロスポイントバッファを使う技術も存在する。
【０００３】
背景技術によるベクトル処理装置の例を、図９〜図１４を用いて説明する。図９、図１１、図１３は、クロスバの構成を示し、図１０、図１２、図１４はそれぞれに対応する動作例を示している。
【０００４】
図９は一般的なクロスバスイッチの構成を示している。ここでは、クロスバスイッチの一例として、入力バッファが１６バッファあり（Ｉ００〜Ｉ１５）、出力バッファが１６バッファある（Ｏ００〜Ｏ１５  先頭文字はアルファベットの”オー”）、１６ｘ１６のクロスバを想定している。
【０００５】
図１０が、図９に対応する動作例である。今、最初にＳ００〜Ｓ１５の要素、次にＬ０〜Ｌ１の要素、さらに次にＭ０の要素、さらに次にＮ０の要素が入力バッファから流れるものとする。
【０００６】
各要素が１サイクルをかけてクロスバを抜け、順次出力バッファに出力されている。Ｓ００で見ると時間０サイクルに入力バッファから発行され、時間１サイクルに出力バッファから出力されている。
【０００７】
ここで、クロスバを通過する要素は、入力バッファへ到着順を、出力バッファにおいても守らなければならないアーキテクチャを想定している。これは後述する本発明に置いても同様とする。すなわち、図１０の例においては、Ｌ０、Ｌ１は、Ｓ００〜Ｓ１５を追い越して、出力バッファＯ０１に出力されてはならず、同様にＭ０がＬ０、Ｌ１を追い越して、出力バッファＯ０１に出力されてはならないアーキテクチャを想定している。
【０００８】
本例では、全要素が出力バッファＯ０１に集中しているため、クロスバの調停部は、各要素を調停して、順次要素を出力しなければならない。つまり、調停の結果Ｓ００からＳ１５が順次発行されているが、１６番目の要素であるＳ１５は、１５Ｔ待たされてから発行されている。
【０００９】
本例では、すべての出力先がＯ０１であるため、すべての順序を保証しているように見えるが、たとえば、Ｓ００〜Ｓ０７がＯ０１、Ｓ０８〜Ｓ１５がＯ０９、Ｌ０がＯ０１、Ｌ１がＯ０９を出力バッファとする場合、Ｏ０１を出力先とするＳ０７より、Ｏ０９を行き先とするＬ１が出力バッファ全体のタイミングをみたときに、先に発行されるケースは問題とならないアーキテクチャを想定している。すなわち、各出力バッファで見た場合、その出力バッファ内で見た要素の順序が入力バッファでの到着順序を保証していればよいものとする。
【００１０】
具体的には、ベクトル型コンピュータがこれに当てはまり、複数要素を発行するベクトルロード命令／ストア命令を後続の複数要素を発行するベクトルロード・ストア命令が追い越してはならないため、このアーキテクチャに該当する。
【００１１】
なお、より厳しい制約として、同時に入力バッファに到着した要素は、入力バッファＩ００側を先行到着要素として扱うものとする。本例でいうと、Ｏ０１バッファにＳ００、Ｓ０１、…Ｓ１５の順で出力されるのは良いが、同時に入力バッファに到着したとはいえ、Ｓ１５、Ｓ１４…Ｓ００の順で出力されるのは、認められないのものとする。
【００１２】
優先順位をまとめると、入力バッファに先に到着したものに優先権があり、同時到着の中では、入力バッファ若番（Ｉ００側）に優先権があるものとする。
【００１３】
これらの制約を守るためには、後続のＬ０、Ｌ１の要素は、先行のＳ００〜Ｓ１５までの要素が全て掃けるまで、調停に参加できない。よって、順序を保証するためにＬ０、Ｌ１の入力バッファへの参加開始（＝調停参加）は、１６サイクルになっており、同様にＭ０はＬ０、Ｌ１が調停の結果すべて掃けるまで調停に参加できないため、入力バッファへの参加開始（＝調停参加）は、１８サイクルになっている。
【００１４】
図９、図１０の例では、要素の到着順を守らなければならないアーキテクチャにおいて、単純なクロスバ構成を用いた場合の問題点を示している。すなわち、順序を保証するために、Ｌ０、Ｌ１がＳ００〜Ｓ１５を待ち、Ｍ０がＬ０、Ｌ１を待っており、その結果、出力バッファをＯ０１以外のＯ００にするＮ０までも調停に参加できず、待っている状態になっている。結果として、クロスバの利用効率は低いものになってしまっている。
【００１５】
図１１、図１２に、単純なクロスバ構成での問題点を回避する性能向上施策であるクロスポイントバッファを備えるクロスバスイッチの例を示す。入力バッファと出力バッファの交差するポイントにバッファを設ける方式であり、図１１ではＸ００〜Ｘ１５と示されている。このＸ００〜Ｘ１５は、各出力バッファあたり１セットもたれるものである。
【００１６】
図１２にクロスポイントバッファでの動作例を示す。図１０と違い、クロスポイントバッファを保持しているため、入力バッファに並んだ要素Ｓ００〜Ｓ１５の要素が１サイクル後にすべてクロスポイントバッファに保持されている。クロスポイントバッファに保持されたＳ００〜Ｓ１５までの要素は、出力バッファに対して１６ｔｏ１のセレクタを通り、一つずつ発行される。
【００１７】
図１０のとの違いは、後続のＬ０、Ｌ１の調停開始時間が、早まっている点である。すまわち、クロスポイントバッファなしでは、Ｌ０、Ｌ１の調停開始がサイクル１６だったのに対し、クロスポイントバッファありでは、サイクル１になっている。すなわち、Ｌ０、Ｌ１の行き先バッファが、Ｏ０１以外であれば、Ｌ０、Ｌ１はクロスポイントバッファに対して即発行できるため、性能上効果のある方式である。
【００１８】
ただし、本例では、後続のＬ０、Ｌ１の行き先バッファもＳ００〜Ｓ１５と同じＯ０１であるため、その後、クロスポイントバッファが空くまで待たされてしまうので全体としての性能向上はまり見られていない。
【００１９】
クロスポイントバッファの性能をさらに向上させる施策として、クロスポイントバッファのワード数を増やす方式がある。図１３、図１４にクロスポイントバッファのワード数を２ワードにしたクロスバスイッチの例を示す。
【００２０】
図１３では、クロスバッファバッファ１  Ｘ００〜Ｘ１５に加え、その下にクロスポイントバッファ２  Ｙ００〜Ｙ１５を備えている。
【００２１】
図１４にワード数を２にしたクロスポイントバッファでの動作例を示す。図１２と違いクロスポイントバッファを深さ方向に２ワードもっているため、先ほど、入力バッファで待たされていたＬ０、Ｌ１の発行が早くなっている。図１２ではＬ０、Ｌ１の発行が１６サイクルまで待たされているのに対し、図１４では、待ちなしの１サイクルでの発行となっている。
【００２２】
このようにクロスポイントバッファの深さ方向にワード数を持つことは、性能の上で一定の効果をもたらす。
【００２３】
ここで、関連技術として、クロスバの利用効率をあげる技術が特許文献１に開示されている。特許文献１に開示の技術は、入力バッファ、および、クロスポイントバッファからの出力要素の選択アルゴリズムを改良して、クロスバの利用効率をあげるものである。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特許第４００２２１０号公報
【発明の概要】
【発明が解決しようとする課題】
【００２５】
図１３、図１４に示す例では、後続のＭ０の行き先バッファもＬ０、Ｌ１と同じＯ０１であるため、その後、クロスポイントバッファが空くまで待たされてしまうので全体としての性能向上はまり見られていない。さらに深さ方向を増やし、クロスポイントバッファを３ワードにすれば、さらに後続の行き先バッファの違うＮ０は待たされることはなくなるので、性能を向上させることはできるが、この場合、多くのハードウェア量を費やすことになり、また、ワード数の増加に伴い、レイテンシが悪化するという問題もある。
【００２６】
ここまでの例から、背景技術では以下の問題があったといえる。
【００２７】
クロスポイントバッファの性能を向上させる施策として、バッファの深さ方向にワード数を持たせる方法がある。しかしながら、クロスバを通過させる要素に対して、通過順序を保証しなければならないアーキテクチャにおいては、単純に、深さ方向にワード数を持っても、特定のパターンや、ランダムアクセスにおいて性能が得られないケースが存在する。また、単純にワード数を増やした場合の解決方法には、ハードウェア量の増大と、レイテンシの悪化という問題ももっている。
【００２８】
また、特許文献１に開示技術は、出力要素順序を保証する必要のないクロスバにおいて利用できる手段であるため、出力要素順を保証する必要のある構成においては利用できないという問題がある。
【００２９】
（発明の目的）
本発明の目的は、上述の課題を解決し、深さ方向に２ワード以上を持つクロスポイントバッファ方式において、クロスバの利用効率を向上させるクロスバスイッチ、ベクトル処理装置、及びクロスバ制御方法を提供することである。
【課題を解決するための手段】
【００３０】
本発明の第１のクロスバスイッチは、クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを備え、クロスポイントバッファの２ワード目にシフト機能を実装し、クロスポイントバッファの１ワード目の要素数がクロスポイントバッファの２ワード目の要素数より多い場合、シフト機能を利用しないことを選択する選択手段を含む。
【００３１】
本発明の第１のベクトル処理装置は、クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを含むクロスバスイッチを備え、クロスバスイッチのクロスポイントバッファの２ワード目にシフト機能を実装し、クロスバスイッチが、クロスポイントバッファの１ワード目の要素数がクロスポイントバッファの２ワード目の要素数より多い場合、シフト機能を利用しないことを選択する選択手段を含む。
【００３２】
本発明の第１のクロスバ制御方法は、クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを備えるクロスバスイッチによるクロスバ制御方法であって、クロスポイントバッファの２ワード目にシフト機能を実装し、クロスポイントバッファの１ワード目の要素数がクロスポイントバッファの２ワード目の要素数より多い場合、シフト機能を利用しないことを選択する選択ステップを、選択手段が実行する。
【００３３】
本発明の第２のクロスバ制御方法は、クロスバ入力バッファとクロスバ出力バッファの間に深さ方向に２ワード以上のクロスポイントバッファを含むクロスバスイッチを備えるベクトル処理装置によるクロスバ制御方法であって、クロスポイントバッファの１ワード目の要素数がクロスポイントバッファの２ワード目の要素数より多い場合、クロスバスイッチのクロスポイントバッファの２ワード目に実装されたシフト機能を利用しないことを選択する選択ステップを、クロスバスイッチの選択手段が実行する。
【発明の効果】
【００３４】
本発明によれば、深さ方向に２ワード以上を持つクロスポイントバッファ方式において、クロスバの利用効率を向上させることができる。
【図面の簡単な説明】
【００３５】
【図１】本発明の第１の実施の形態によるシフト機能を示す図である。
【図２】本発明の第１の実施の形態によるシフト機能を実装したときの効果を示す図である。
【図３】本発明の第１の実施の形態によるクロスバスイッチの構成を示す図である。
【図４】本発明の第１の実施の形態によるシフト機能を使用しなかったときの効果を示す図である。
【図５】本発明の第１の実施の形態によるクロスバスイッチの動作を示すフローチャートである。
【図６】本発明の第１の実施の形態によるクロスバスイッチの動作を示すフローチャートである。
【図７】本発明の第１の実施の形態によるクロスバスイッチの動作を示すフローチャートである。
【図８】本発明の第１の実施の形態によるクロスバスイッチの動作を示すフローチャートである。
【図９】背景技術によるベクトル処理装置の例を示す図である。
【図１０】背景技術によるベクトル処理装置の例を示す図である。
【図１１】背景技術によるベクトル処理装置の例を示す図である。
【図１２】背景技術によるベクトル処理装置の例を示す図である。
【図１３】背景技術によるベクトル処理装置の例を示す図である。
【図１４】背景技術によるベクトル処理装置の例を示す図である。
【図１５】背景技術によるクロスバスイッチの構成を示す図である。
【発明を実施するための形態】
【００３６】
本発明の上記及び他の目的、特徴及び利点を明確にすべく、添付した図面を参照しながら、本発明の実施形態を以下に詳述する。なお、上述の本願発明の目的のほか、他の技術的課題、その技術的課題を解決する手段及びその作用効果についても、以下の実施形態による開示によって明らかとなるものである。
【００３７】
なお、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００３８】
（第１の実施の形態）
本発明の第１の実施の形態について図面を参照して詳細に説明する。
【００３９】
本実施の形態によるクロスバスイッチ１００は、深さ方向に２ワードを持つクロスポイントバッファを備える（図１参照）。
【００４０】
図１５は、図１４で示されている２ワードのクロスポイントバッファの１出力バッファに対応する部分である。クロスポイントバッファ１ワード目のＸ００〜Ｘ１５（３−１）が、クロスポイントバッファ２ワード目のＹ００〜Ｙ１５（３−３）にそれぞれ対応している。
【００４１】
前述の通り、要素の順序を保証しなければならないことを想定しているため、図１５に示す構成では、クロスポイントバッファ２ワード目のＹ００〜Ｙ１５（３−３）から要素がすべて発行されてからでないと、クロスポイントバッファ１ワード目のＸ００〜Ｘ１５（３−１）からのクロスポイントバッファ２ワード目のＹ００〜Ｙ１５（３−３）への移動はできない。図１４では、この例を示した。
【００４２】
こうした動作をするため、１出力バッファあたりのクロスポイントバッファを１６ｘ２ワードの３２要素のバッファを持っているにもかかわらず、性能がでないケースが存在する。
【００４３】
例えば、Ｙ１４、Ｙ１５で２要素、Ｘ００で１要素と全部で３要素しか埋まっていなかったとしても、１ワード目の要素は、バッファ２ワード目が空いていないので待たされるしかない。また、さらに後続の要素が同出力バッファをめがけていたとしても、Ｘ００〜Ｘ１５に入れず、結果として性能低下をもたらしていた。これは、クロスバッファを有効活用できないことに起因している。
【００４４】
そこで、この問題を解決するために、本発明では、図１に示すように、クロスポイントバッファの２ワード目にシフト機能を実装する。
【００４５】
２ワード目のシフト機能は、次のように動作する。
【００４６】
第１に、２ワード目から、発行すべき要素を選択させる。選択優先順位をＹ００＞Ｙ０１…＞Ｙ１５とする。
【００４７】
第２に、２ワード目から、要素が発行されると、空エントリに対して、左シフトする（Ｙ００側が高優先順位のため。）
【００４８】
第３に、１ワード目ワード数  ＜  ２ワード目ワード数の場合、１ワード目の最優先エントリを２ワード目のＹ１５に入れる。
【００４９】
第４に、１ワード目ワード数＞＝２ワード目ワード数の場合、２ワード目のエントリがすべて発行された後に、Ｘ００−＞Ｙ００、Ｘ０１−＞Ｙ０１、…Ｘ１５−＞Ｙ１５にそれぞれ入れる（１ワード目と２ワード目のエントリ数に応じて、性能のでる適切な選択を実施。）。
【００５０】
第５に、１ワード目の全エントリが空くときに後続の入力を受付。
【００５１】
図２に、シフト機能を実装したときの効果を示す。
【００５２】
最初の要素Ｓ００〜Ｓ１５はクロスポイントバッファ１（Ｘ００〜Ｘ１５）を通過し、クロスポイントバッファ２（Ｙ００〜Ｙ１５）に到達する。ここで、本発明では、シフト機能があるため、先行の要素が発行される毎に、Ｙ００側にシフトされていく。後続のＬ０、Ｌ１もＳ００〜Ｓ１５のあとにクロスポイントバッファ１（Ｘ００〜Ｘ０１）に挿入される。
【００５３】
改良前の図１４では、クロスポイントバッファ２（Ｙ００〜Ｙ１５）の要素が掃けるまでＬ０、Ｌ１はクロスポイントバッファ１（Ｘ００〜Ｘ０１）でホールドされるしかなかったが、改良後はシフト機能によりクロスポイントバッファ２（Ｙ００〜Ｙ１５）のうちのＹ１５が空いているため、Ｌ０要素をＹ１５に挿入できる。同様に１サイクル後にはＬ１をＹ１５に挿入できるため、後続のＭ０は入力バッファで１サイクル待たされるのみで通過している。
【００５４】
効果の差分としてわかりやすいのは、Ｍ０のさらに後ろのＮ０要素である。シフト機能を持たない図１４では、Ｎ０要素は先行のＭ０がクロスポイントバッファ１に入るまで発行されることはないため、結果として、出力バッファでみたときに通過するのは、２１サイクルとなっている。これに対し、先行要素Ｍ０が早々にクロスポイントバッファ１に挿入される図２では、出力バッファでＮ０が通過するのは、７サイクルとなっている。
【００５５】
以上のように、クロスポイントバッファ２にシフト機能を追加することの性能的な効果は大きい。
【００５６】
しかしながら、本シフト機能を利用しないほうが性能のでるケースが存在する。一般的にいって、シフト機能が有効に働くのは、クロスポイントバッファ２（Ｙ００〜Ｙ１５）にある要素数とクロスポイントバッファ１（Ｘ００〜Ｘ１５）の要素数を比較して、クロスポイントバッファ２の要素数の方が多いときにシフト機能は有効に働く。反対にクロスポイントバッファ１の要素数の方が多いときには、シフト機能を利用しない方式の方が性能がよい。
【００５７】
クロスポイントバッファ１の要素数の方が多いときにシフト機能を使って、反対に性能を落としてしまうケースを図３に示す。図３の例では、クロスポイントバッファ１からクロスポイントバッファ２への移動に１６サイクル要しており、性能が悪化している。
【００５８】
同命令列に対してシフト機能を使わなかったときのケースを図４に示す。クロスポイントバッファ１からクロスポイントバッファ２への移動を１サイクルの待ち合わせと１サイクルの移動の計２サイクルで済ませている。
【００５９】
以上から、本シフト機能が有効に働くのは、（クロスポイントバッファ１の要素数）＜（クロスポイントバッファ２の要素数）のときとなる。このため、本発明では、（クロスポイントバッファ１の要素数）＜（クロスポイントバッファ２の要素数）を判定する選択回路も追加する。前述の第３、第４の動作がこの選択回路の部分になるが、以降の実施例で詳しく説明する。
【００６０】
（第１の実施の形態の動作の説明）
次に、本実施の形態によるクロスバスイッチ１００の動作について、図面を参照して詳細に説明する。
【実施例１】
【００６１】
次に、具体的な実施例を用いて本実施の形態の動作を説明する。
【００６２】
（構成の説明）
図１に、１出力バッファに対するクロスポイントバッファと、シフト機能を示す。この回路は１出力バッファあたりに存在するため、論理的に１６ｘ１６のクロスバの場合には、この回路が１６個存在することになる。
【００６３】
符号４１のＸ００〜Ｘ１５は、クロスポイントバッファの１ワード目である。要素順序の保証のために、新規の挿入は、Ｘ００〜Ｘ１５がすべて空くタイミングからとなる。
【００６４】
符号４２は、３ウェイのセレクタである。ひとつは、後述のＹ００〜Ｙ１５自身のホールド、ひとつが、Ｘ００…Ｘ１５とＹ００…Ｙ１５がそれぞれに対応したパスで、これら、ふたつは従来のクロスポイントバッファにも存在するウェイである。最後の３ウェイ目がシフト機能を実現するパスであり、Ｙ００はＹ０１、Ｙ０１はＹ０２からのパスがつながれている。ただし、Ｙ１５は、Ｘ００〜Ｘ１５のうちの最優先のものが選ばれた結果がシフトパスとしてつながっている。
【００６５】
符号４３のＹ００〜Ｙ１５はクロスポイントバッファの２ワード目である。要素順序の保証のために、クロスポイントバッファ２から要素が発行される毎にクロスポイントバッファ２の中でシフトが実行される。
【００６６】
符号４４は１６ウェイのセレクタである。先頭要素から発行していく必要があるため、Ｙ００〜Ｙ１５までの要素の有無をチェックし、最優先の要素を選択（Ｌｅａｄｉｎｇ０回路）したのちに、クロスポイントバッファ２のうちの最初の要素を発行する。
【００６７】
符号４５は２ウェイのセレクタである。出力バッファＯＵＴ（出力レジスタ４６）からは、さらに先の回路の混雑具合によって、発行できるケースとできないケースが存在する。この２ウェイセレクタは、発行できなかったときのホールドを実現する。
【００６８】
符号４７は、シフト機能を利用したときに、クロスポイントバッファ１からクロスポイントバッファ２へ要素を挿入するときに使われる１６ウェイのセレクタである。最優先の要素を選択（Ｌｅａｄｉｎｇ０回路）したのちに、クロスポイントバッファ１のうちの最初の要素を発行できる機能をもつ、また、その発行は常に実施するわけではなくクロスポイントバッファ１、クロスポイントバッファ２の要素数の関係によって、発行するか否かを判断する機能も持つ。
【００６９】
以上が本発明の構成要素である。
【００７０】
（動作の説明）
図１に示した構成要素の動作を図５、図６、図７、図８のフローチャートを用いて説明する。
【００７１】
図５は、出力レジスタ４６を中心に、２ウェイセレクタ４５の動作を示している。
【００７２】
図６は、クロスポイントバッファ２（クロスポイントバッファ４４）を中心に、３ウェイセレクタ４２、１６ウェイセレクタ４４、１６ウェイセレクタ４７の動作を示している。
【００７３】
図７は、クロスポイントバッファ１（クロスポイントバッファ４１）を中心に、３ウェイのセレクタ４２、１６ウェイのセレクタ４７の動作を示している。
【００７４】
図８は、入力バッファ（図９、図１１、図１３のＩ００〜Ｉ１５）の動作を示している。
【００７５】
図５は、出力バッファ４６を中心に示したフローチャートである。最初に電源Ｏｎ、リセットがあり（ステップＳＯ−１）、要素がない状態に移行する（ステップＳＯ−２）。
【００７６】
上位のレジスタにあたるクロスポイントバッファ２に要素があるか否かを判別し（ステップＳＯ−３）、なければ、要素なしのまま、あれば要素ありの状態になる（ステップＳＯ−４）。
【００７７】
出力バッファＯＵＴから、さらに先のステージへの発行可否を判断し（ステップＳＯ−５）、不可能であれば何もしないが、可能であれば要素を発行する（ステップＳＯ−６）。以降システムが停止するまで繰り返される（ステップＳＯ−７）
【００７８】
図６は、クロスポイントバッファ２を中心に示したフローチャートである。最初に電源Ｏｎ、リセットがあり（ステップＳＹ−１）、要素がない状態に移行する（ステップＳＹ−２）。
【００７９】
上位のレジスタにあたるクロスポイントバッファ１に要素があるか否かを判別し（ステップＳＹ−３）、なければ、要素なしのまま、あれば要素ありの状態になる（ステップＳＹ−４）。
【００８０】
次のタイミングで出力バッファが空くか否かの判断を行い（ステップＳＹ−５）、空かなければそのまま、空くのであれば次のステップにすすむ。
【００８１】
２ワード目から要素が発行可能な場合には、２ワード目中の要素数が２個以上が否かを判定する（ステップＳＹ−６）。１要素のみの場合には、当該要素を発行し（ステップＳＹ−７）、ステップＳＹ−３に戻り、システムが停止するまで繰り返される（ステップＳＹ−８）。
【００８２】
２要素以上ある場合には、クロスポイントバッファ１とクロスポイントバッファ２の要素数を比較する（ステップＳＹ−９）。クロスポイントバッファ１＞＝クロスポイントバッファ２の場合には、クロスポイントバッファ２から１要素を発行し、他の要素をシフトするのみで、ステップＳＹ−４に進む（ステップＳＹ−１０）。クロスポイントバッファ１＜クロスポイントバッファ２の場合には、クロスポイントバッファ２から１要素を発行し、他の要素をシフトし、さらに、クロスポイントバッファ１の最優先要素をクロスポイントバッファ２の最老番Ｙ１５に挿入する（ステップＳＹ−１１）。
【００８３】
図７は、クロスポイントバッファ１を中心に示したフローチャートである。最初に電源Ｏｎ、リセットがあり（ステップＳＸ−１）、要素がない状態に移行する（ステップＳＸ−２）。
【００８４】
上位のレジスタにあたる入力バッファに要素があるか否かを判別し（ステップＳＸ−３）、なければ、要素なしのまま、あれば要素ありの状態になる（ステップＳＸ−４）。
【００８５】
次のタイミングでクロスポイントバッファ２がすべて空くか否かの判断を行い（ステップＳＸ−５）、空くのであれば、１ワード目の全要素を２ワード目に挿入する（ステップＳＸ−６）。反対に空かないのであれば、ステップＳＸ−８に進み、クロスポイントバッファ２から要素の発行があるか否かを確認する（ステップＳＸ−８）。
【００８６】
１要素も発行がない場合には、ステップＳＸ−４に戻る。発行ある場合には、クロスポイントバッファ１の要素数とクロスポイントバッファ２の要素数の比較を行なう。
【００８７】
（バッファ１の数）＞＝（バッファ２の数）の場合には、何もせずにステップＳＸ−４に戻る。（バッファ１の数）＜（バッファ２の数）の場合には、クロスポイントバッファ１の最優先の要素をクロスポイントバッファ２の最優先ではないＹ１５に挿入する（ステップＳＸ−１０）。
【００８８】
ステップＳＸ−１０で最優先の要素をＹ１５に挿入した結果、クロスポイントバッファ１の全エントリが空になるか否かをチェックする（ステップＳＸ−１１）。空になる場合には、要素なしから状態ステップＳＸ−３に進み、まだ要素があるならば、要素のある状態ステップＳＸ−４に進む。
【００８９】
図８は入力バッファ（図９、図１１、図１３のＩ００〜Ｉ１５）のを中心に示したフローチャートである。
【００９０】
最初に電源Ｏｎ、リセットがあり（ステップＳＩ−１）、要素がない状態に移行する（ステップＳＩ−２）。
【００９１】
入力バッファよりさらに上位の回路（バッファｏｒレジスタ）に入力バッファに登録すべき要素があるか否かを判別し（ステップＳＩ−３）、なければ、要素なしのまま、あれば要素ありの状態になる（ステップＳＩ−４）。
【００９２】
次に入力バッファの要素が行くべき先のクロスポイントバッファ１が次のタイミングで全て空になるか否かを確認する（ステップＳＩ−５）。空にならなければ何もせずにＳＩ−４に戻り、空になるのであれば、入力バッファから要素を発行する。発行した後には、新規要素があるか否かのステップに戻る。
【００９３】
以上が、各バッファで見た動作のタイミングである。
【００９４】
（第１の実施の形態による効果）
本実施の形態によれば、クロスポイントバッファにシフト機能を実装することにより、クロスバの利用効率を向上させることができる。
【００９５】
本実施の形態では、ランダム性能（調停する出力バッファがランダム）については、シフト機能なし実効性能が５７．１％であるのに対し、シフト機能あり実効性能は６５．１％となり、性能が改善する。また、ベクトル型コンピュータを考慮した場合、特定の命令パターンにおいても１８〜４５％の性能向上が見られる。
【００９６】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態に限定されるものでなく、その技術的思想の範囲内において様々に変形して実施することができる。
【００９７】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００９８】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。
【００９９】
また、本発明の方法およびコンピュータプログラムには複数の手順を順番に記載してあるが、その記載の順番は複数の手順を実行する順番を限定するものではない。このため、本発明の方法およびコンピュータプログラムを実施する時には、その複数の手順の順番は内容的に支障しない範囲で変更することができる。
【０１００】
また、本発明の方法およびコンピュータプログラムの複数の手順は個々に相違するタイミングで実行されることに限定されない。このため、ある手順の実行中に他の手順が発生すること、ある手順の実行タイミングと他の手順の実行タイミングとの一部ないし全部が重複していること、等でもよい。
【産業上の利用可能性】
【０１０１】
本発明によれば、クロスバのような多入力対多出力の通信網を持ち、かつ、通信網を通るパケット（命令列、もしくは、データ列）間で到着順序の保証を必要とするようなコンピュータシステム、もしくは、ネットワークスイッチにおける利用の可能性が考えられる。
【符号の説明】
【０１０２】
１００：クロスバスイッチ
４１：クロスポイントバッファ
４２：セレクタ
４３：クロスポイントバッファ
４４：セレクタ
４５：セレクタ
４６：出力レジスタ
４７：セレクタ
【図１】
0005403380.tif 000002
【図２】
0005403380.tif 000003
【図３】
0005403380.tif 000004
【図４】
0005403380.tif 000005
【図５】
0005403380.tif 000006
【図６】
0005403380.tif 000007
【図７】
0005403380.tif 000008
【図８】
0005403380.tif 000009
【図９】
0005403380.tif 000010
【図１０】
0005403380.tif 000011
【図１１】
0005403380.tif 000012
【図１２】
0005403380.tif 000013
【図１３】
0005403380.tif 000014
【図１４】
0005403380.tif 000015
【図１５】
0005403380.tif 000016