(57)【特許請求の範囲】
【請求項１】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、
前記データ転送要求候補データをＮ×Ｎビットで表し、このＮ×Ｎビットのデータ転送要求候補データを、１からＮまでの全ての順列組み合わせパターンを表す、それぞれがＮ×Ｎビットで構成される、Ｎの階乗個の順列組み合わせデータと、夫々並列に論理積をとる第１ステップと、
前記論理積が成立する候補数が最大となる順列組み合わせパターンを探し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定する第２ステップと、
を備え、
前記第２ステップでは、論理積が成立する候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するとともに、前記候補数が最大となる順列組み合わせパターンを探す際の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とするデータ転送組み合わせ決定方法。
【請求項２】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、
前記データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行、列毎に計数する第１ステップと、
前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行または列を１つ選択して記憶する第２ステップと、
選択した行または列の中の候補について、その候補が存在する列または行の候補の数のうち最小値を検索して、該最小値を示す列または行を１つ選択して記憶する第３ステップと、
前記第２ステップおよび第３ステップで決定した行上の候補および列上の候補を全て削除する第４ステップと、
を備え、前記第１〜第４ステップを候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定することを特徴とするデータ転送組み合わせ決定方法。
【請求項３】
前記第２または第３ステップにおいて、行または列を選択するときに、最小値を示す行、または列が複数あった場合に、行から列へ、あるいは列から行への順にラウンドロビン方式を適用して最小値を示す行または列を一意に決定することを特徴とする請求項２に記載のデータ転送組み合わせ決定方法。
【請求項４】
前記第２または第３ステップでは、前記候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする請求項３に記載のデータ転送組み合わせ決定方法。
【請求項５】
前記第２または第３ステップで、行または列を選択するときに、最小値を示す行または列が複数あった場合に、行番号または列番号の小さい方を優先して選択することにより、最小値を示す行または列を一意に決定することを特徴とする請求項２に記載のデータ転送組み合わせ決定方法。
【請求項６】
前記第１ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくすることを特徴とする請求項２〜５のいずれか一つに記載のデータ転送組み合わせ決定方法。
【請求項７】
前記第１ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行、または列が強制的に選択されるようにすることを特徴とする請求項２〜５のいずれか一つに記載のデータ転送組み合わせ決定方法。
【請求項８】
前記Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す前記転送要求候補データが処理順序に関する複数の優先クラスに対応して複数組備えられ、複数組の格子から候補を選択するときの条件が全ての格子の同一行および全ての格子の同一列について選択可能な候補を１つとする複数の優先クラスを扱うデータ転送に適用されるデータ転送組み合わせ決定方法であって、
前記第１〜第４ステップの繰り返し処理を、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に実行し、
前記第４ステップにおいては、前記第２ステップおよび第３ステップで決定された当該優先クラスに対応する格子の行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記決定された行上の候補および列上の候補とを削除することを特徴とする請求項２〜７のいずれか一つに記載のデータ転送組み合わせ決定方法。
【請求項９】
前記第２および第３ステップにおいて、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定することを特徴とする請求項８に記載のデータ転送組み合わせ決定方法。
【請求項１０】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、
前記データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数する第１ステップと、
前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行を１つ選択して記憶する第２ステップと、
選択した行の中の候補について、その候補が存在する列における候補の数を列毎に計数する第３ステップと、
前記第３ステップで計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す列を１つ選択して記憶する第４ステップと、
前記第２ステップおよび第４ステップで決定した行上の候補および列上の候補を全て削除する第５ステップと、
を備え、前記第１〜第５ステップを候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定することを特徴とするデータ転送組み合わせ決定方法。
【請求項１１】
前記第２および第４ステップで、行および列を夫々選択するときに、候補数が最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行および列を一意に決定することを特徴とする請求項１０に記載のデータ転送組み合わせ決定方法。
【請求項１２】
前記第２および第４ステップでは、前記候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする請求項１１に記載のデータ転送組み合わせ決定方法。
【請求項１３】
前記第２および第４ステップで、行および列を夫々選択するときに、最小値を示す行および列が複数あった場合に、行番号および列番号の小さい方を優先して選択することにより、最小値を示す行および列を一意に決定することを特徴とする請求項１０に記載のデータ転送組み合わせ決定方法。
【請求項１４】
前記第１ステップまたは第３ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくすることを特徴とする請求項１０〜１３のいずれか一つに記載のデータ転送組み合わせ決定方法。
【請求項１５】
前記第１ステップまたは第３ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行または列が強制的に選択されるようにすることを特徴とする請求項１０〜１３のいずれか一つに記載のデータ転送組み合わせ決定方法。
【請求項１６】
前記Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す前記転送要求候補データが処理順序に関する複数の優先クラスに対応して複数組備えられ、複数組の格子から候補を選択するときの条件が全ての格子の同一行および全ての格子の同一列について選択可能な候補を１つとする複数の優先クラスを扱うデータ転送に適用されるデータ転送組み合わせ決定方法であって、
前記第１〜第５ステップの繰り返し処理を、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に実行し、
前記第５ステップにおいては、前記第２ステップおよび第４ステップで決定された当該優先クラスに対応する格子の行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記決定された行上の候補および列上の候補とを削除することを特徴とする請求項１０〜１５に記載のデータ転送組み合わせ決定方法。
【請求項１７】
前記第２および第４ステップにおいて、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定することを特徴とする請求項１６に記載のデータ転送組み合わせ決定方法。
【請求項１８】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、
Ｎ×Ｎビットの前記データ転送要求候補データと、１からＮまでの全ての順列組み合わせパターンを表す、それぞれがＮ×Ｎビットで構成される、Ｎの階乗個の順列組み合わせデータと、夫々並列に論理積をとる論理積回路と、
前記複数の順列組み合わせパターン毎に、前記論理積が成立する候補数を演算する個数演算部と、
前記個数演算部の複数の出力を比較することにより、候補数が最大となる順列組み合わせパターンを検索し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定する検索決定回路と、
を備え、
前記検索決定回路は、
候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するとともに、
比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することにより、候補数が最大となる順列組み合わせパターンを択一選択する比較器を備えることを特徴とする組み合わせ決定回路。
【請求項１９】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、
Ｎ×Ｎビットの前記データ転送要求候補データから、前回の組み合わせ決定結果で指定される行及び列と同一行および同一列の候補を削除する選択行列候補削除部と、
前記選択行列候補削除部の出力データ中の候補数を、Ｎ行×Ｎ列の格子点にある候補の数として、行毎に計数する行候補数計算部と、
前記行候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する行用最小値比較器と、
前記行用最小値比較器の選択行に基づいて、前記選択行列候補削除部の出力データから、前記選択行に候補の存在しない列の候補を削除する選択行非選択列候補削除部と、
前記選択行非選択列候補削除部の出力データに基づき、各列における候補の数を列毎に計数する列候補数計算部と、
前記列候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する列用最小値比較器と、
前記行用最小値比較器および列用最小値比較器の各選択結果を記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力する選択結果保存レジスタと、
を備え、
前記選択結果保存レジスタに、前記行用最小値比較器および列用最小値比較器の各選択結果が夫々最大でＮ組入力されたときの選択結果保存レジスタの記憶データを最終的なデータ転送の組み合わせ結果として出力をすることを特徴とする組み合わせ決定回路。
【請求項２０】
前記行用最小値比較器は、最小値を示す行が複数あった場合に、ラウンドロビンを用いて最小値を示す行を一意に決定するラウンドロビン回路を備え、
前記列用最小値比較器は、最小値を示す列が複数あった場合に、ラウンドロビンを用いて最小値を示す列を一意に決定するラウンドロビン回路を備えることを特徴とする請求項１９に記載の組み合わせ決定回路。
【請求項２１】
前記行用最小値比較器および列用最小値比較器は、各比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする請求項２０に記載の組み合わせ決定回路。
【請求項２２】
前記行用最小値比較器は、最小値を示す行が複数あった場合に、小さい行番号を優先して選択することにより、最小値を示す行を一意に決定し、
前記列用最小値比較器は、最小値を示す列が複数あった場合に、小さい列番号を優先して選択することにより、最小値を示す列を一意に決定することを特徴とする請求項１９に記載の組み合わせ決定回路。
【請求項２３】
前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行を最小値を置き換えて前記行用最小値比較器に入力する指定行優先選択部と、
前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列を最小値を置き換えて前記列行用最小値比較器に入力する指定列優先選択部と、
をさらに備えることを特徴とする請求項１９〜２２のいずれか一つに記載の組み合わせ決定回路。
【請求項２４】
前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行の計数結果をそのまま前記行用最小値比較器に入力するとともに、前記指定行以外の行の計数結果を０に置き換える手段と、
前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列の計数結果をそのまま前記列用最小値比較器に入力するとともに、前記指定列行以外の列の計数結果を０に置き換える手段と、
を備えることを特徴とする請求項１９〜２２のいずれか一つに記載の組み合わせ決定回路。
【請求項２５】
Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データが、処理順序に関する複数の優先クラスに対応して複数組備えられ、全ての組の転送要求候補データの同一行および同一列から選択可能な候補を各１つとする複数の優先クラスを扱うデータ転送に適用され、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、
複数の優先クラス分の前記データ転送要求候補データから、前回の組み合わせ決定結果で指定される優先クラスおよび該優先クラスより下位の全ての優先クラスにおける前回の組み合わせ決定結果が指定する入力回線および出力回線と同一入力回線および同一出力回線の候補を削除して出力する選択行列候補削除部と、
前記選択行列候補削除部の出力から少なくとも１つの優先クラスについてのデータ転送要求候補データを選択し、該選択したデータ転送要求候補データを選択した優先クラスを示すクラスデータと共に出力する動作を、上位優先クラスから下位優先クラスへの順に、各優先クラスのデータ転送の組み合わせを決定する毎に繰り返し実行するクラス選択部と、
前記クラス選択部から出力される１つの優先クラスのデータ転送要求候補データ中の候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数する行候補数計算部と、
前記行候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する行用最小値比較器と、
前記行用最小値比較器の選択行に基づいて、前記クラス選択部から出力される１つの優先クラスのデータ転送要求候補データから、前記選択行に候補の存在しない列の候補を削除する選択行非選択列候補削除部と、
前記選択行非選択列候補削除部の出力データに基づき、各列における候補の数を列毎に計数する列候補数計算部と、
前記列候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する列用最小値比較器と、
前記行用最小値比較器および列用最小値比較器の各選択結果を前記クラス選択部からの前記クラス選択データと共に記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力する選択結果保存レジスタと、
を備え、前記選択結果保存レジスタにおける最終的な記憶データを前記データ転送の組み合わせ結果として出力をすることを特徴とする組み合わせ決定回路。
【請求項２６】
前記行用最小値比較器および列用最小値比較器において、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、最小値を示す行及び列を夫々選択することを特徴とする請求項２５に記載の組み合わせ決定回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、Ｎ×Ｎのデータ交換を実行する入力バッファ型あるいは入出力バッファ型の通信交換装置に適用されるデータ転送組み合わせ決定方法および組み合わせ決定回路に関し、特にデータ交換の調停に一般的に用いられているラウンドロビン方式よりもデータ転送能力の高いデータ転送をなし得る斬新なアルゴリズムを用いたデータ転送組み合わせ決定方法および組み合わせ決定回路に関するものである。
【０００２】
【従来の技術】
Ｎ×Ｎのデータ交換を実現する通信装置が、入力バッファ型あるいは入出力バッファ型と呼ばれるスイッチングアーキテクチャを持つ場合、そのデータ交換のための組み合わせ決定アルゴリズムには、Ｎ本の入力回線とＮ本の出力回線を１対１に対応させた組み合わせを探す機能が求められる。つまり一回のデータ転送時に、交換装置全体で見て最大Ｎ個、各回線当たりでは１個のデータまでしか転送できない。したがって、各入力回線において転送待ちをしているデータがそれぞれどの出力回線宛なのかを確認し、その都度の転送待ちデータの組み合わせにおいてできるだけ多くのデータ転送を実行していかないと、交換装置全体としての転送能力を高レベルに維持することはできない。
【０００３】
この種のデータ交換の調停には、ラウンドロビン方式（以下ＲＲ方式という）が用いられることが多い。ラウンドロビン方式は、基本的に平等な扱いをされるべき要求元に対し、回線や共用帯域やバスなどの共用資源を公平にアクセスする権利を与えるべく調停するものである。
【０００４】
ＲＲ方式をＮ×Ｎのデータ交換に適用する場合、従来においては、ＲＲ方式を出力回線側および入力回線側でそれぞれ実施するようなアルゴリズムが一般的であった(例えば、１９９８年電子情報通信学会通信ソサイエティ大会  Ｂ−６−２０、入力バッファ型ＡＴＭスイッチにおけるスケジューリングアルゴリズムに関する一検討)。
【０００５】
この従来技術には、シーケンシャルラウンドロビン（ＳＲＲ）方式を用いた調停アルゴリズムが開示されている。ＳＲＲ方式では、各入力回線に優先度を与え、最優先の入力回線において入力回線毎に保持しているポインタ値を用いて要求のある出力回線のうちの１つの出力回線をＲＲ方式によって選択し、ポインタ値を更新する。次の優先順位の入力回線では未決定の出力回線の中からポインタ値を用いて同様にして１つの出力回線を選択する。この手順を全入力回線について繰り返す。次回は、最優先の入力回線をＲＲ方式によってシフトさせて、同様の手順を行う。
【０００６】
この従来技術によるＲＲ方式を図１４に示す４×４の交換装置を用いて説明する。図１４（ａ）に示すようなデータ転送待ちの組み合わせがあるとする。すなわち、入力回線＃１は出力回線＃１，＃２，＃３への要求があり、入力回線＃２は出力回線＃１，＃３への要求があり、入力回線＃３は出力回線＃１，＃４への要求があり、入力回線＃４は出力回線＃３，＃４への要求がある。この状態を格子点のモデルに置き換えると図１４（ｂ）のようになる。
【０００７】
図１４（ａ）において、入力回線を決定するためのＲＲの前回の決定結果ＲＲａ＝３とし、各入力回線において出力回線を決定するためのＲＲの前回決定結果（ポインタ値）ＲＲｂは、＃１が「４」、＃２が「１」、＃３が「２」、＃４が「２」であったとする。
【０００８】
まず入力回線を決定する前回のＲＲ値ＲＲａ＝３であるので、入力回線＃４が最優先回線となる。入力回線＃４には、転送待ちデータ(候補)が存在するので、入力回線＃４が選択される。入力回線＃４が選択されたので、入力回線を決定するＲＲ値ＲＲａに「４」がロードされ、ＲＲａ＝４として保存される（図１４（ｃ））。
【０００９】
次に入力回線＃４において出力回線を決定する。ここで、入力回線＃４のポインタ値ＲＲｂが２であることから出力回線＃３から見ていくと、出力回線＃３宛にデータが存在するので、入力回線＃４と出力回線＃３の組み合わせ（点線）がまず決定される。出力回線＃３が選択されたので、入力回線＃４のポインタ値ＲＲｂに「３」がロードされ、ＲＲｂ＝３として保存される（図１４（ｄ））。
【００１０】
つぎに、図１４（ｅ）に示すように、入力回線＃４と出力回線＃３に関係する転送待ちデータの候補はもはや選択することはできないので全て削除する。ここでは、入力回線＃４−出力回線＃４、入力回線＃１−出力回線＃３、入力回線＃２−出力回線＃３の組み合わせが削除される。
【００１１】
つぎに、図１４（ｆ）に示すように、同様にして、入力回線＃１と出力回線＃１の組み合わせが決定される。そして、図１４（ｇ）に示すように、選択不可能となった転送待ちデータの候補を削除する。ここでは、入力回線＃２−出力回線＃１、入力回線＃３−出力回線＃１、入力回線＃１−出力回線＃２の組み合わせが削除される。
【００１２】
最後に、図１４（ｈ）に示すように、入力回線＃３と出力回線＃４の組み合わせが決定される。未選択の候補がなくなって組み合わせ決定手順は完了する。結局３本の候補が選択され、次回のデータ転送においては３つのデータを転送することが可能である。
【００１３】
【発明が解決しようとする課題】
上記従来のＲＲ方式を用いたアルゴリズムでは、４×４の交換において、３つの組み合わせしか求められなかったが、図１４（ｂ）に示したデータ転送待ちの組み合わせにおいては、実は、図１５（ａ）（ｂ）に示すように、４つの入出力回線の全てを選択する組み合わせが２つ存在する。図１５においては、黒丸が最終的に選択される入出力回線の組み合わせを示している。
【００１４】
このように上記従来のＲＲ方式では、図１５に示したどちらの組み合わせも見つけることができず、４つのデータ転送ができたはずが、３つしかデータ転送の機会を与えなかったことになる。
【００１５】
勿論、従来のＲＲ方式においても、前回のＲＲの決定結果によっては、図１５に示した組み合わせに至る場合もある。しかし、あくまでも前回のＲＲの決定結果に左右されるということが問題である。このような転送待ちデータの組み合わせにおいては、あらゆるＲＲの前回決定結果の組み合わせについて試行すると、３つが決定する確率は５１．２％、４つが決定する確率が４８．８％となる。これは計算機を利用して全てのＲＲの前回決定結果の組み合わせについて試行することによって得ることができる。具体的な結果は、３つとなるのが５２４／１０２４、４つとなるのが５００／１０２４である。ＲＲ値、ポインタ値は１〜４までの数値が有効で、入力回線決定のために１つ、出力回線決定のために４つ存在するので合計５つ、４5＝１０２４が全てのＲＲ値の組み合わせパターンである。
【００１６】
因みに、図１４（ｈ）に示したＲＲ値の結果をそのまま利用して、図１４と同じ転送待ちデータの組み合わせのときに、もう一度同じＲＲ手順を実施すると、図１６（ａ）に示すように、図１５(ｂ)の４つのデータ転送が可能な組み合わせに到達する。さらにそのまま同じパターンで手順を実施すると、図１６（ｂ）に示すような３つのデータ転送が可能な組み合わせとなる。つまり、連続して同じ組み合わせパターンが続いた場合、４つのデータ転送の組み合わせが見つかったすぐ次に、３つのデータ転送の組み合わせが適用されることになる。これでは交換装置としての転送能力を高レベルに維持することはできない。
【００１７】
図１７では、図１６（ａ）の結果に至る手順の詳細を示している。この図１７の手順において、各入力回線についての出力回線を選択する段階で、削除されるデータ転送の候補の数に注目すると、
入力回線＃４−出力回線＃４（図１７（ａ）→図１７（ｃ））：２本
入力回線＃１−出力回線＃２（図１７（ｄ）→図１７（ｅ））：２本
入力回線＃２−出力回線＃３（図１７（ｆ）→図１７（ｇ））：１本
となっている。
【００１８】
これに対し、図１４の手順では、
入力回線＃４−出力回線＃３（図１４（ｄ）→図１４（ｅ））：３本
入力回線＃１−出力回線＃１（図１４（ｆ）→図１４（ｇ））：３本
である。
【００１９】
このように、２組の入出力回線の組み合わせを決めた段階までに、決定した候補の他に、図１７では４本、図１４では６本が削除されている。そして図１４の場合は、図１４（ｇ）で３本の候補を削除した段階で、何も候補の残っていない回線が存在している。結局、削除される数が多いと言うことは、入出力回線の決定が進むにつれて残りの候補がかなり少なくなることを意味している。つまり、残りの候補が少なくなることによって、より多くの入出力回線の組み合わせが得られる確率を下げているのである。
【００２０】
ＲＲ方式においては、このような転送待ちデータの候補の削除数が入出力回線の組み合わせを決定するための要因、あるいは要因の一つとなっておらず、前回の決定結果が全てであるので、４つの組み合わせが選択可能な転送待ちデータの状態であっても、４つのデータ転送が可能な組み合わせに至るかどうかは、完全に確率の問題、すなわち運次第である。
【００２１】
このように、ＲＲ方式は、この種のデータ交換に要求される、「Ｎ行×Ｎ列のＮ2個の格子点があり、そのうちの任意の格子点を選択できる状態であるときに、Ｎ行×Ｎ列の各行および各列には最大１つの候補のみ選択可能という条件の下で、最大数の格子点を選択する」という命題を解くには不向きな方式であり、入力バッファ型、あるいは入出力バッファ型のアーキテクチャを持つ通信交換装置における組み合わせ決定アルゴリズムにＲＲ方式を採用することは、交換装置のデータ転送能力を高レベルに維持することができないことを意味するのである。
【００２２】
この発明は上記に鑑みてなされたもので、データ交換能力を高レベルに維持することができる斬新なアルゴリズムを有するデータ転送組み合わせ決定方法および組み合わせ決定回路を得ることを目的とする。
【００２３】
【課題を解決するための手段】
上記目的を達成するため、この発明にかかるデータ転送組み合わせ決定方法は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、前記データ転送要求候補データをＮ×Ｎビットで表し、このＮ×Ｎビットのデータ転送要求候補データを、１からＮまでの全ての順列組み合わせパターンを表す、それぞれがＮ×Ｎビットで構成される、Ｎの階乗個の順列組み合わせデータと、夫々並列に論理積をとる第１ステップと、前記論理積が成立する候補数が最大となる順列組み合わせパターンを探し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定する第２ステップと、を備え、前記第２ステップでは、論理積が成立する候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するとともに、前記候補数が最大となる順列組み合わせパターンを探す際の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする。
【００２４】
この発明によれば、Ｎ×Ｎビットのデータ転送要求候補データを、１からＮまでの全ての順列組み合わせパターンを表すＮ×ＮビットのＮ！個の順列組み合わせデータと夫々論理積をとり、論理積が成立する候補数が最大となる順列組み合わせパターンを探し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定し、候補数が最大となる順列組み合わせパターンを探す際の候補数の比較処理において、論理積が成立する候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択し、候補数が最大となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしている。
【００２９】
つぎの発明にかかるデータ転送組み合わせ決定方法は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、前記データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行、列毎に計数する第１ステップと、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行または列を１つ選択して記憶する第２ステップと、選択した行または列の中の候補について、その候補が存在する列または行の候補の数のうち最小値を検索して、該最小値を示す列または行を１つ選択して記憶する第３ステップと、前記第２ステップおよび第３ステップで決定した行上の候補および列上の候補を全て削除する第４ステップとを備え、前記第１〜第４ステップを候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定することを特徴とする。
【００３０】
この発明によれば、データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行、列毎に計数し、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行または列を１つ選択して記憶し、選択した行または列の中の候補について、その候補が存在する列または行の候補の数のうち最小値を検索して、該最小値を示す列または行を１つ選択して記憶し、上記決定した行上の候補および列上の候補を全て削除し、これらの処理を候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定するようにしている。
【００３１】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２または第３ステップにおいて、行または列を選択するときに、最小値を示す行、または列が複数あった場合に、行から列へ、あるいは列から行への順にラウンドロビン方式を適用して最小値を示す行または列を一意に決定することを特徴とする。
【００３２】
この発明によれば、行または列を選択するときに、最小値を示す行、または列が複数あった場合に、行から列へ、あるいは列から行への順にラウンドロビン方式を適用して最小値を示す行または列を一意に決定するようにしている。
【００３３】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２または第３ステップでは、前記候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする。
【００３４】
この発明によれば、候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしている。
【００３５】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２または第３ステップで、行または列を選択するときに、最小値を示す行または列が複数あった場合に、行番号または列番号の小さい方を優先して選択することにより、最小値を示す行または列を一意に決定することを特徴とする。
【００３６】
この発明によれば、行または列を選択するときに、最小値を示す行または列が複数あった場合に、行番号または列番号の小さい方を優先して選択することにより、最小値を示す行または列を一意に決定するようにしている。
【００３７】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第１ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくすることを特徴とする。
【００３８】
この発明によれば、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくするようにしている。
【００３９】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第１ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行、または列が強制的に選択されるようにすることを特徴とする。
【００４０】
この発明によれば、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行、または列が強制的に選択されるようにしている。
【００４１】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す前記転送要求候補データが処理順序に関する複数の優先クラスに対応して複数組備えられ、複数組の格子から候補を選択するときの条件が全ての格子の同一行および全ての格子の同一列について選択可能な候補を１つとする複数の優先クラスを扱うデータ転送に適用されるデータ転送組み合わせ決定方法であって、前記第１〜第４ステップの繰り返し処理を、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に実行し、前記第４ステップにおいては、前記第２ステップおよび第３ステップで決定された当該優先クラスに対応する格子の行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記決定された行上の候補および列上の候補とを削除することを特徴とする。
【００４２】
この発明によれば、処理順序に関する複数の優先クラスが設定されている場合において、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に、上記データ転送組み合わせ処理を実行し、さらに選択決定された行上および列上の候補を全て削除する際に、当該優先クラスに対応する格子における選択決定された行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記選択決定された行上の候補および列上の候補を削除するようにしている。
【００４３】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２および第３ステップにおいて、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定することを特徴とする。
【００４４】
この発明によれば、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定するようにしている。
【００４５】
つぎの発明にかかるデータ転送組み合わせ決定方法は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定するデータ転送組み合わせ決定方法において、前記データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数する第１ステップと、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行を１つ選択して記憶する第２ステップと、選択した行の中の候補について、その候補が存在する列における候補の数を列毎に計数する第３ステップと、前記第３ステップで計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す列を１つ選択して記憶する第４ステップと、前記第２ステップおよび第４ステップで決定した行上の候補および列上の候補を全て削除する第５ステップとを備え、前記第１〜第５ステップを候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定することを特徴とする。
【００４６】
この発明によれば、データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数し、該計数された結果が１以上である計数値のうち最小値を検索して、該最小値を示す行を１つ選択して記憶し、選択された行の中の候補について、その候補が存在する列における候補の数を列毎に計数し、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す列を１つ選択して記憶し、前記決定した行上の候補および列上の候補を全て削除し、前記一連の処理を候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定するようにしている。
【００４７】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２および第４ステップで、行および列を夫々選択するときに、候補数が最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行および列を一意に決定することを特徴とする。
【００４８】
この発明によれば、前記行および列を夫々選択するときに、候補数が最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行および列を一意に決定するようにしている。
【００４９】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２および第４ステップでは、前記候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする。
【００５０】
この発明によれば、候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしている。
【００５１】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２および第４ステップで、行および列を夫々選択するときに、最小値を示す行および列が複数あった場合に、行番号および列番号の小さい方を優先して選択することにより、最小値を示す行および列を一意に決定することを特徴としている。
【００５２】
この発明によれば、行および列を夫々選択するときに、最小値を示す行および列が複数あった場合に、行番号および列番号の小さい方を優先して選択することにより、最小値を示す行および列を一意に決定するようにしている。
【００５３】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第１ステップまたは第３ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくすることを特徴とする。
【００５４】
この発明によれば、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくするようにしている。
【００５５】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第１ステップまたは第３ステップにおいて、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行または列が強制的に選択されるようにすることを特徴とする。
【００５６】
この発明によれば、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行または列が強制的に選択されるようにしている。
【００５７】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す前記転送要求候補データが処理順序に関する複数の優先クラスに対応して複数組備えられ、複数組の格子から候補を選択するときの条件が全ての格子の同一行および全ての格子の同一列について選択可能な候補を１つとする複数の優先クラスを扱うデータ転送に適用されるデータ転送組み合わせ決定方法であって、前記第１〜第５ステップの繰り返し処理を、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に実行し、前記第５ステップにおいては、前記第２ステップおよび第４ステップで決定された当該優先クラスに対応する格子の行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記決定された行上の候補および列上の候補とを削除することを特徴とする。
【００５８】
この発明によれば、処理順序に関する複数の優先クラスが設定されている場合において、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に、上記データ転送組み合わせ処理を実行し、さらに選択決定された行上および列上の候補を全て削除する際に、当該優先クラスに対応する格子における選択決定された行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記選択決定された行上の候補および列上の候補を削除するようにしている。
【００５９】
つぎの発明にかかるデータ転送組み合わせ決定方法は、上記の発明において、前記第２および第４ステップにおいて、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定することを特徴とする。
【００６０】
この発明によれば、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定するようにしている。
【００６１】
つぎの発明にかかる組み合わせ決定回路は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、Ｎ×Ｎビットの前記データ転送要求候補データと、１からＮまでの全ての順列組み合わせパターンを表す、それぞれがＮ×Ｎビットで構成される、Ｎの階乗個の順列組み合わせデータと、夫々並列に論理積をとる論理積回路と、前記複数の順列組み合わせパターン毎に、前記論理積が成立する候補数を演算する個数演算部と、前記個数演算部の複数の出力を比較することにより、候補数が最大となる順列組み合わせパターンを検索し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定する検索決定回路と、を備え、前記検索決定回路は、候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するとともに、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することにより、候補数が最大となる順列組み合わせパターンを択一選択する比較器を備えることを特徴とする。
【００６２】
この発明によれば、論理積回路によってＮ×Ｎビットの前記データ転送要求候補データと１からＮまでの全ての順列組み合わせパターンを表すＮ×Ｎビットの順列組み合わせデータとの論理積を夫々求め、個数演算部によって複数の順列組み合わせパターン毎に前記論理積が成立する候補数を演算し、検索決定回路によって個数演算部の複数の出力を比較することにより、候補数が最大となる順列組み合わせパターンを検索し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定し、前記検索決定回路はラウンドロビン回路を備え、候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択、検索決定回路は比較器を備え、この比較器は、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することにより、候補数が最大となる順列組み合わせパターンを択一選択するようにしている。
【００６７】
つぎの発明にかかる組み合わせ決定回路は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データを用いて、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、Ｎ×Ｎビットの前記データ転送要求候補データから、前回の組み合わせ決定結果で指定される行及び列と同一行および同一列の候補を削除する選択行列候補削除部と、前記選択行列候補削除部の出力データ中の候補数を、Ｎ行×Ｎ列の格子点にある候補の数として、行毎に計数する行候補数計算部と、前記行候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する行用最小値比較器と、前記行用最小値比較器の選択行に基づいて、前記選択行列候補削除部の出力データから、前記選択行に候補の存在しない列の候補を削除する選択行非選択列候補削除部と、前記選択行非選択列候補削除部の出力データに基づき、各列における候補の数を列毎に計数する列候補数計算部と、前記列候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する列用最小値比較器と、前記行用最小値比較器および列用最小値比較器の各選択結果を記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力する選択結果保存レジスタとを備え、前記選択結果保存レジスタに、前記行用最小値比較器および列用最小値比較器の各選択結果が夫々最大でＮ組入力されたときの選択結果保存レジスタの記憶データを最終的なデータ転送の組み合わせ結果として出力をすることを特徴とする。
【００６８】
この発明によれば、行候補数計算部は、データ転送要求候補データにおける候補数をＮ行×Ｎ列の格子の格子点にある候補の数として行毎に計数し、行用最小値比較器は、前記計数された結果が１以上である計数値のうち最小値を検索して、該最小値を示す行を１つ選択する。選択行非選択列候補削除部は、前記行用最小値比較器の選択行に基づいて、前記選択行列候補削除部の出力データから、前記選択行に候補の存在しない列の候補を削除し、列候補数計算部は、前記選択行非選択列候補削除部の出力データに基づき各列における候補の数を列毎に計数し、列用最小値比較器は、前記列候補数計算部の計数結果のうちで１以上である最小値を検索して該最小値を示す行を１つ選択する。選択結果保存レジスタは、前記行用最小値比較器および列用最小値比較器の各選択結果を記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力する。選択行列候補削除部は、入力されるＮ×Ｎビットの前記データ転送要求候補データから、前回の組み合わせ決定結果で指定される行及び列と同一行および同一列の候補を削除する。そして、選択結果保存レジスタに、前記行用最小値比較器および列用最小値比較器の各選択結果が夫々最大でＮ組入力されたときの選択結果保存レジスタの記憶データを最終的なデータ転送の組み合わせ結果として出力する。
【００６９】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行用最小値比較器は、最小値を示す行が複数あった場合に、ラウンドロビンを用いて最小値を示す行を一意に決定するラウンドロビン回路を備え、前記列用最小値比較器は、最小値を示す列が複数あった場合に、ラウンドロビンを用いて最小値を示す列を一意に決定するラウンドロビン回路を備えることを特徴とする。
【００７０】
この発明によれば、行用最小値比較器および列用最小値比較器は、ラウンドロビン回路を夫々備え、最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行を一意に決定するようにしている。
【００７１】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行用最小値比較器および列用最小値比較器は、各比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することを特徴とする。
【００７２】
この発明によれば、前記行用最小値比較器および列用最小値比較器は、各比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしている。
【００７３】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行用最小値比較器は、最小値を示す行が複数あった場合に、小さい行番号を優先して選択することにより、最小値を示す行を一意に決定し、前記列用最小値比較器は、最小値を示す列が複数あった場合に、小さい列番号を優先して選択することにより、最小値を示す列を一意に決定することを特徴とする。
【００７４】
この発明によれば、前記行用最小値比較器および列用最小値比較器は、最小値を示す行および列が複数あった場合に、小さい行番号を優先して選択することにより、最小値を示す行および列を一意に決定するようにしている。
【００７５】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行を最小値を置き換えて前記行用最小値比較器に入力する指定行優先選択部と、前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列を最小値を置き換えて前記列行用最小値比較器に入力する指定列優先選択部とをさらに備えることを特徴とする。
【００７６】
この発明によれば、指定行優先選択部は、前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行を最小値を置き換えて前記行用最小値比較器に入力するとともに、指定列優先選択部は、前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列を最小値を置き換えて前記列行用最小値比較器に入力するようにしている。
【００７７】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行の計数結果をそのまま前記行用最小値比較器に入力するとともに、前記指定行以外の行の計数結果を０に置き換える手段と、前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列の計数結果をそのまま前記列用最小値比較器に入力するとともに、前記指定列行以外の列の計数結果を０に置き換える手段とを備えることを特徴とする。
【００７８】
この発明によれば、行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行の計数結果をそのまま前記行用最小値比較器に入力するとともに、前記指定行以外の行の計数結果を０に置き換えるようにするとともに、列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列の計数結果をそのまま前記列用最小値比較器に入力するとともに、前記指定列行以外の列の計数結果を０に置き換えるようにしている。
【００７９】
つぎの発明にかかる組み合わせ決定回路は、Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データが、処理順序に関する複数の優先クラスに対応して複数組備えられ、全ての組の転送要求候補データの同一行および同一列から選択可能な候補を各１つとする複数の優先クラスを扱うデータ転送に適用され、Ｎ個の入力回線からＮ個の出力回線へデータ転送するときのデータ転送の組み合わせを決定する組み合わせ決定回路において、複数の優先クラス分の前記データ転送要求候補データから、前回の組み合わせ決定結果で指定される優先クラスおよび該優先クラスより下位の全ての優先クラスにおける前回の組み合わせ決定結果が指定する入力回線および出力回線と同一入力回線および同一出力回線の候補を削除して出力する選択行列候補削除部と、前記選択行列候補削除部の出力から少なくとも１つの優先クラスについてのデータ転送要求候補データを選択し、該選択したデータ転送要求候補データを選択した優先クラスを示すクラスデータと共に出力する動作を、上位優先クラスから下位優先クラスへの順に、各優先クラスのデータ転送の組み合わせを決定する毎に繰り返し実行するクラス選択部と、前記クラス選択部から出力される１つの優先クラスのデータ転送要求候補データ中の候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数する行候補数計算部と、前記行候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する行用最小値比較器と、前記行用最小値比較器の選択行に基づいて、前記クラス選択部から出力される１つの優先クラスのデータ転送要求候補データから、前記選択行に候補の存在しない列の候補を削除する選択行非選択列候補削除部と、前記選択行非選択列候補削除部の出力データに基づき、各列における候補の数を列毎に計数する列候補数計算部と、前記列候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する列用最小値比較器と、前記行用最小値比較器および列用最小値比較器の各選択結果を前記クラス選択部からの前記クラス選択データと共に記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力する選択結果保存レジスタとを備え、前記選択結果保存レジスタにおける最終的な記憶データを前記データ転送の組み合わせ結果として出力をすることを特徴とする。
【００８０】
この発明によれば、複数の優先クラスを扱うデータ転送に適用される組み合わせ決定回路において、選択行列候補削除部は、複数の優先クラス分のデータ転送要求候補データから、前回の組み合わせ決定結果で指定される優先クラスおよび該優先クラスより下位の全ての優先クラスにおける前回の組み合わせ決定結果が指定する入力回線および出力回線と同一入力回線および同一出力回線の候補を削除し、クラス選択部は、選択行列候補削除部の出力から少なくとも１つの優先クラスについてのデータ転送要求候補データを選択し、該選択したデータ転送要求候補データを選択した優先クラスを示すクラスデータと共に出力する動作を、上位優先クラスから下位優先クラスへの順に繰り返し実行する。行候補数計算部は、クラス選択部から出力される１つの優先クラスのデータ転送要求候補データ中の候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数し、行用最小値比較器は、行候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する。選択行非選択列候補削除部は、行用最小値比較器の選択行に基づいて、前記クラス選択部から出力される１つの優先クラスのデータ転送要求候補データから、前記選択行に候補の存在しない列の候補を削除し、列候補数計算部は、選択行非選択列候補削除部の出力データに基づき、各列における候補の数を列毎に計数し、列用最小値比較器は、前記列候補数計算部の計数結果のうちで１以上である最小値を検索して、該最小値を示す行を１つ選択する。選択結果保存レジスタは、前記行用最小値比較器および列用最小値比較器の各選択結果を前記クラス選択部からの前記クラス選択データと共に記憶し、その出力を選択行列候補削除部に前回の組み合わせ決定結果として入力し、前記選択結果保存レジスタにおける最終的な記憶データを前記データ転送の組み合わせ結果として出力をするようにしている。
【００８１】
つぎの発明にかかる組み合わせ決定回路は、上記の発明において、前記行用最小値比較器および列用最小値比較器において、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、最小値を示す行及び列を夫々選択することを特徴とする。
【００８２】
この発明によれば、行用最小値比較器および列用最小値比較器は、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、最小値を示す行及び列を夫々選択するようにしている。
【００８３】
【発明の実施の形態】
以下に添付図面を参照して、この発明にかかるデータ転送組み合わせ決定方法および組み合わせ決定回路の好適な実施の形態を詳細に説明する。
【００８４】
実施の形態１．
図１は、この発明の実施の形態１の組み合わせ決定アルゴリズムを概念的に示すものである。図１（ａ）に示すように、Ｎ×Ｎのデータ交換装置を、Ｎ×Ｎの格子点モデルに置き換える。例えば、Ｎ行をＮチャネルの入力回線に対応させ、Ｎ列をＮチャネルの出力回線に対応させる。
【００８５】
図１（ｂ）は、４行４列の格子点モデルを示しており、この場合は、１行１列、１行２列、１行３列、２行１列、２行３列、３行１列、３行４列、４行３列、４行４列の格子点に、各入出力回線の転送待ちデータの候補が存在している。
【００８６】
この実施の形態１においては、このような格子点モデルを用い、データ交換に要求される上述した「Ｎ行×Ｎ列のＮ2個の格子点があり、そのうちの任意の格子点を選択できる状態であるときに、Ｎ行×Ｎ列の各行および各列には最大１つの候補のみ選択可能という条件の下で、最大数の格子点を選択する」という命題を解くために、１からＮまでの数字を並べるための順列組み合わせ(組み合わせ数＝Ｎの階乗個（Ｎ！）)のパターンを全て用意しておき、これら全ての順列組み合わせパターンを格子点上に並んだ候補と論理積をとり、出力が１となるすなわち論理積が成立した候補の数が最大となる順列組み合わせのパターンを探し、そのうちの１つを選択するようにしている。
【００８７】
図１（ｃ）は、１から４までの数字を並べるための、４行４列の順列組み合わせパターンを示しており、この場合の組み合わせパターン数は４の階乗（４！）＝２４となる。
【００８８】
図１（ｄ）は、図１（ｂ）に示した格子点上に並んだ候補パターンと、図１（ｃ）に示した全ての順列組み合わせパターンとの論理積をとることを示している。
【００８９】
図１（ｅ）に示すように、上記論理積が成立した候補の数が最大となる順列組み合わせのパターンを探し、そのうちの１つを選択する。図１の場合は、２組が最大数「４」となり、これらのうち１組を選択する。
【００９０】
この実施の形態１の方式においては、論理積を取る順列組み合わせのパターン数がＮの階乗で増加する。そのため、ソフトウェアならともかく高速性のためにハードウェアで実現する必要がある場合、Ｎ＝６程度までが現実的な値となると予想される。基本的にはＮが増えれば回路規模が爆発的に大きくなっていくだけで基本方式としては変わらない。
【００９１】
図２に４×４の場合の組み合わせ決定回路のハードウェア構成例を示す。この図２に示す組み合わせ決定回路は、完全に組み合わせ回路だけで構成することができ、入力データとしての全入出力回線の転送待ちデータの有無を示す情報が出そろってから一定時間後に選択・決定された入出力回線の組み合わせが出力されるというものである。
【００９２】
図２に示す組み合わせ決定回路１０は、（１６×順列組み合わせのパターン数）個の論理積回路１１および個数算出部１２を有する論理積成立数演算部（ＰＴＮＡＮＤ）１３と、比較およびＲＲ動作を行う比較ＲＲ部（ＣＮＴＣＭＰ）１４と、２４個から１個を選択するセレクタ（ＰＴＮＳＬＣＴ）１５とを備えている。また、ＲＲ用の外部回路として、５ビットのレジスタ１６を備えている。
【００９３】
入出力インタフェースは以下の通りである。
入力信号線（１６ビット）
dataw[4:1][4:1]；Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データである。上位の[4:1]が入力回線、下位の[4:1]が出力回線を表し、[4:1][4:1]で４×４の行列を表している。各１６ビットにおいて、１：データあり、０：データなしである。
出力信号線（１６ビット、組み合わせの選択結果）
datar[4:1][4:1]；上位の[4:1]が入力回線、下位の[4:1]が出力回線を表し、[4:1][4:1]で４×４の行列を表している。各１６ビットにおいて、１：選択、０：非選択である。
【００９４】
例えば、図１（ｂ）に示した入出力パターンを、列単位に表現した場合（縦に見た場合）、
dataw[4:1][4:1]＝1110．1000．1101．0011b
となる。添え字の“b”は２進数表記であることを意味するものとする。
【００９５】
また、図１（ｂ）に示した入出力パターンを、行単位に表現した場合（横に見た場合）、
dataw[4:1][4:1]＝1110．1010．1001．0011b
となる。
【００９６】
論理積成立数演算部（ＰＴＮＡＮＤ）１３においては、上記した１６ビットの入力信号線dataw[4:1][4:1]と、１６ビットの順列組み合わせのパターンptn[n][4:1][4:1]とが、１６個の論理積回路１１に夫々入力される。１６個の論理積回路１１は、順列組み合わせのパターン数分（この場合２４個）だけ用意されている。
【００９７】
順列組み合わせパターンptn[n][4:1][4:1]は、１６ビットで図１（ｃ）に示した１つの４×４の順列組み合わせパターンを表す。ptn[n][4:1][4:1]は、以下に示す２４個の固定値である順列組み合わせのパターンを有しており、これら２４個の順列組み合わせのパターンが論理積回路１１に同時に入力される。
【００９８】
これは例えば、
0003863421.tif 000002
のようになっていて、１から４までの数字を並べるときの順列組み合わせパターンを数値化したものである。このように、ptn[n][4:1][4:1]は、１からＮまでの全ての順列組み合わせパターンを表すＮの階乗個のパターン数をもつＮ×Ｎビットの順列組み合わせデータである。
【００９９】
１６ビットの論理積回路１１は、以下の論理積を信号線毎に実行し、その出力d_ptn[n][4:1][4:1]を個数算出部１２に入力する。
d_ptn[n][4:1][4:1]＝dataw[4:1][4:1]＆ptn[n][4:1][4:1]
論理積回路１１には、上記２４個の順列組み合わせのパターンptn[n][4:1][4:1]が同時に入力されるので、２４セットのd_ptn[n][4:1][4:1]が得られることになる。
【０１００】
個数算出部１２は、次式にしたがって、上記論理積が成立した、すなわち論理積出力が１となった行方向の候補の個数（または行方向の候補の個数）を演算する処理を、２４セットのd_ptn[n][4:1][4:1]について夫々実行する。
【０１０１】
0003863421.tif 000003
ここで“|”は論理和を示す記号とする。d_cnt[n][3:1]値は、０から４までの値を取り得るので、d_cntは３ビット幅となる。
【０１０２】
つぎに、比較ＲＲ部（ＣＮＴＣＭＰ）１４では、入力された２４セットのd_cnt値をトーナメント比較して、結果として最大となったd_cnt値の番号ｎを比較結果cmprとして出力する。
【０１０３】
ここで最大値を得るとき、いくつかのd_cnt値が最大値かつ同一の値となることがあるので、この場合、比較ＲＲ部１４においては、ＲＲ方式を適用して、１つのd_cnt値を一意に決定している。
【０１０４】
このときのＲＲにおいては、例えば、d_cnt値が一番大きい値を示すｎが複数ある時、前回決定したｎを記憶しておきそれをｎPとすると、d_cnt値が最大となるｎのうち、最高優先：ｎP＋１、次優先：ｎP＋２、…、Ｎ、１、２、…、最低優先：ｎPとし、この優先順位にしたがってｎを決定するようにしている。
【０１０５】
ここで、比較ＲＲ部１４では、入力された複数のd_cnt値をトーナメント比較して最大値を選択する処理と、選択結果が複数になったときに最終的に選択結果を一意に絞るためのＲＲ処理とを行わなければならない。そこで、この場合、比較ＲＲ部１４では、比較ビット長を拡張して、比較ビット中の上位ビットをd_cnt値とし、その下位ビットをＲＲ方式を実現するための比較値とし、これらを一括して同時に比較して結果を出すことによって、複数のクロックステップなどを踏まずに高速処理をなし得るようにしている。
【０１０６】
すなわちこの場合、比較対象は２４個なので、ＲＲ値は１〜２４までの値を示す必要がある。つまりＲＲのビット幅は５ビットが必要である。従って、実際の比較値である決定組み合わせ数（１〜４）を表すための上位３ビットと、ＲＲのための下位５ビットを合わせて８ビットの比較値となる。前回の決定結果がｓ(ｓ：１、２、…、２４)であった場合、次に最優先されるべきd_cntはｓ＋１番目である。ここでは最大値を検索するので、ｓ＋１番目のd_cntの下位５ビットが２４となり、ｓ＋２番目のd_cntの下位５ビットが２３ということになり、結局、下位の５ビットを、以下のようにすればよい。
【０１０７】
0003863421.tif 000004
【０１０８】
このようにすることで、決定組み合わせ数の最大値を求める比較と、一意に結果を求めるためのＲＲ手順が同時に実施され、結果的に平等性を維持しつつ常に一意に決定したものが出力されることになる。ただし、この場合はＲＲ値について前回の決定結果を利用するため、前回の決定結果をレジスタ１６にラッチし、それを内部にフィードバックする回路が必要となる。
【０１０９】
こうして最終的に得られた順列組み合わせパターンの番号cmprは、セレクタ（ＰＴＮＳＬＣＴ）１５に選択信号selとして入力される。セレクタ１５には、論理積回路１１の１６ビット出力d_ptn[n][4:1][4:1]の分岐出力が、信号ps_ptnとして入力されており、セレクタ１５は、選択信号selで示された番号に対応するps_ptnを選択して、出力信号datar[4:1][4:1]として出力する。このようにして、転送可能な入出力回線の組み合わせ結果が、datar[4:1][4:1]として出力される。
【０１１０】
このようにこの実施の形態１においては、入出力回線の転送待ちデータの候補をＮの階乗個ある順列組み合わせの全パターンと総当たりで比較確認することで、もっとも多くのデータ転送が可能となる組み合わせのうちの１つを選択する方式を採用するようにしているので、交換装置のデータ転送能力を最大に高めることが可能となる。
【０１１１】
なお、上記した実施の形態１においては、入出力チャネル数が同じであるＮ×Ｎの格子点モデルについて説明したが、入出力チャネル数の異なるＮ×Ｍの格子点モデルは、ｍａｘ（Ｎ，Ｍ）＝Ｋの場合のＫ×Ｋの格子点モデルの一部として考えることができるので、上述したＮ×Ｎの格子点モデルに包含されると考えることができ、上述した組み合わせ決定アルゴリズムをそのまま適用することができる。このことは、後述する実施の形態２〜４についても、同様に当てはまる。
【０１１２】
実施の形態２.
つぎに、図３〜図８を用いてこの発明の実施の形態２について説明する。先の実施の形態１では、Ｎの階乗個に相当する順列組み合わせの全てについて総当たりで確認する必要があるが、その順列組み合わせ数が、Ｎの値が少し増えると大きく増大するため、現状ではＮは６(６！＝７２０)程度までが現実的であり、一般の交換装置(回線数：８〜６４程度)に適用することは困難である。実際、交換装置の収容回線数は２のべき乗に相当することが多いので、現実的にはＮ＝４となることが多いだろう。
【０１１３】
そこで、この実施の形態２においては、１回の決定手順後毎に削除される転送待ちデータの候補数に注目し、常にそれが最小になるように入出力回線の組み合わせを決定していくという方式を採用する。この実施の形態２においては、つぎのようなアルゴリズムを採用している。
【０１１４】
ステップ(1)
Ｎ行×Ｎ列の格子点上にある候補の数を、行毎、列毎に計数し、
ステップ(2)
計数した結果が１以上である値のうち最小値を検索して、その値を示す行、または列を１つ選択し、
ステップ(3)
選択した行または列の中の候補について、その候補が存在する列、または行の候補の数のうち最小値を検索して、その値を示す列、または行を１つ選択し、
ステップ(4)
上記(2)および(3)の手順によって決定した行・列の組み合わせを記憶し、
ステップ(5)
決定した行・列上の候補を全て削除して、まだ決定していない行および列の候補数を再びそれぞれ計数し、(2)の処理から候補がなくなるまで繰り返し、
ステップ(6)
候補がなくなった時点で記憶されている行・列の組み合わせを最終的な入出力回線の組み合わせ結果とする。
【０１１５】
また、上記(2)(3)の手順において、最小値を検索するときに行および列全ての計数値を検索対象とするのでなく、行の計数値をまず最初に検索して行を決定し、次にその行の中にある候補に対応する列のうち、もっとも小さい計数値を示す列を決定するという手順を採用することで、効率よく、高速に、最小値を示す列または行を選択するようにしている。
【０１１６】
上記実施の形態２のアルゴリズムを図３を用いて説明する。図３において、入出力回線の転送待ちデータの組み合わせは、図１４あるいは図１７と同じとし、ＲＲの前回決定値は図１４と同じ状態とした。この場合、前記ステップ(1)が行われることで、入出力回線の転送待ちデータ候補数を行、列毎に計算される。この場合、入力回線＃１，＃２，＃３，＃４の転送待ちデータ候補数（各行の待ち候補数）は、３，２，２，２となる、出力回線＃１，＃２，＃３，＃４の転送待ちデータ候補数（各列の待ち候補数）は、３，１，３，２となる。
【０１１７】
また、図３（ａ）〜（ｅ）の各下部に示したＲＲａは、最小値が同じ入力回線が複数あったときに１つの入力回線を選択するためのＲＲ値であり、入力側の各ボックス内に記入された数値「４，１，２，２」（ＲＲｂ）は、最小値が同じ出力回線が複数あったときに１つの出力回線を選択するためのＲＲ値である。
【０１１８】
つぎに、ステップ(2)の手順を実行して、入力回線側（行）の待ち候補数のうち最小値を１つ選択する。この場合、図３（ｂ）に示すように、入力回線側の候補数を比較すると、候補数が２である入力回線＃２、＃３および＃４が最小値を持つ入力回線となる。この中から１つを選択するために、ＲＲ値ＲＲａ（＝３）を利用して、結局入力回線＃４がまず選択される。ＲＲａは、入力回線＃４を最も低い優先度とするように、ＲＲａ＝４となる。
【０１１９】
つぎに、ステップ(3)の手順を実行して、選択した行（入力回線＃４）が指定している複数の列（出力回線）についての待ち候補数を比較することにより、最小の待ち候補数を指定している列（出力回線）を１つ選択する。この場合、図３（ｃ）に示すように、入力回線＃４の２つの転送待ちデータの宛先は出力回線＃３と＃４であるので、それらの回線の候補数を同様に比較すると、出力回線＃３の候補数は３で、出力回線＃４の候補数は２であり、出力回線＃４の候補数が最小かつ唯一であるので、第１回目の決定手順によって入力回線＃４と出力回線＃４の組み合わせが決定する（図３（ｄ））。この場合、出力回線＃４が選択されたので、入力回線＃４のＲＲ値ＲＲｂは、出力回線＃４を最低優先度とするように、ＲＲｂ＝４とされる。
【０１２０】
つぎに、上記ステップ(4)(5)の手順を実行することにより、入力回線＃４と出力回線＃４につながる候補のうち決定したもの以外は全て削除する。この場合は、図３（ｄ）（ｅ）に示すように、入力回線＃４−出力回線＃３、入力回線＃３−出力回線＃４の候補が削除される。この削除により、図３（ｅ）に示すように、入力回線側の待ち候補数は、＃１が３、＃２が２、＃３が１、＃４が０となり、出力回線側の待ち候補数は、＃１が３、＃２が１、＃３が２、＃４が０となる。
【０１２１】
第２回目の決定手順では、まず、入力回線として、候補数の最も少ない入力回線＃３が選択される。入力回線＃３が指定する出力回線は出力回線＃１のみであるので、第２回目の決定手順では、入力回線＃３と出力回線＃１の組み合わせが選択される（図３（ｆ））。ＲＲａは、入力回線＃３を最も低い優先度とするように３とされ、また入力回線＃３のＲＲｂは出力回線＃１を最も低い優先度とするように１とされる。入力回線＃３と出力回線＃１につながる候補のうち決定したもの以外、この場合は、入力回線＃１−出力回線＃１、入力回線＃２−出力回線＃１の組み合わせが削除される。この削除により、図３（ｇ）に示すように、入力回線側の待ち候補数は、＃１が２、＃２が１、＃３が０、＃４が０となり、出力回線側の待ち候補数は、＃１が０、＃２が１、＃３が２、＃４が０となる。
【０１２２】
第３回目の決定手順では、まず、入力回線として、候補数の最も少ない入力回線＃２が選択される。入力回線＃２が指定する出力回線は、出力回線＃３のみであるので、第３回目の決定手順では、入力回線＃２と出力回線＃３の組み合わせが選択される（図３（ｈ））。ＲＲａは、入力回線＃２を最も低い優先度とするように２とされ、また入力回線＃２のＲＲｂは出力回線＃３を最も低い優先度とするように３とされる。入力回線＃２と出力回線＃３につながる候補のうち決定したもの以外、この場合は、入力回線＃１−出力回線＃３の組み合わせが削除される。この削除により、図３（ｉ）に示すように、入力回線側の待ち候補数は、＃１が１、＃２が０、＃３が０、＃４が０となり、出力回線側の待ち候補数は、＃１が０、＃２が１、＃３が０、＃４が０となる。
【０１２３】
第４回目の決定手順では、図３（ｊ）に示すように、入力回線＃１と出力回線＃２の組み合わせが選択される。ＲＲａは、入力回線＃１を最も低い優先度とするように１とされ、また入力回線＃１のＲＲｂは出力回線＃２を最も低い優先度とするように２とされる。
【０１２４】
ここで、各決定段階において削除される候補数を確認すると、
図３（ｄ）→図３（ｅ）：２本
図３（ｆ）→図３（ｇ）：２本
図３（ｈ）→図３（ｉ）：１本
であり、ＲＲ方式において４つの入出力回線が決定された図１７の場合と、削除される候補の本数が同じであることがわかる。このようにこの実施の形態２においては、削除される候補の数をできるだけ少なくすることによって、より多くの入出力回線の組み合わせが決定できるようにする。実際、実施の形態２の方法によれば、４×４の場合には、ＲＲ値の全ての組み合わせにおいて、必ず４つの入出力回線の組み合わせが決定する。つまり、図１５（ａ）（ｂ）のどちらかの選択結果に至ることができる。このような結果も計算機で全てのパターンについて試行して得ることができる。
【０１２５】
因みに、図３の結果は、図１５（ｂ）の結果に相当するが、図３（ｊ）のＲＲ値の状態から同じ転送待ちデータの状態について、上記した実施の形態２の方法を行うようにすれば、図４（ａ）〜（ｈ）に示すように、図１５（ａ）の結果を得ることができる。
【０１２６】
図４（ａ）〜（ｈ）を用いてその動作を簡単に説明する。最初に、入力回線側（行）の待ち候補数のうち最小値を１つ選択する。この場合、候補数が２である入力回線＃２、＃３および＃４が最小値を持つ入力回線となる。ＲＲ値ＲＲａ（＝１）であるので、入力回線＃２がまず選択される。（図４（ａ））。
【０１２７】
つぎに、選択した行（入力回線＃２）が指定している複数の列（出力回線）についての待ち候補数を比較することにより、最小の待ち候補数を指定している列（出力回線）を１つ選択する。この場合、図４（ｂ）に示すように、入力回線＃２の２つの転送待ちデータの宛先は出力回線＃１と＃３であるので、それらの回線の候補数を同様に比較すると、出力回線＃１の候補数は３で、出力回線＃３の候補数は３であり、同数である。入力回線＃２のＲＲ値ＲＲｂ（＝３）が参照され、出力回線＃１のほうが出力回線＃３より優先度が高いことが判る。したがって、第１回目の決定手順によって入力回線＃２と出力回線＃１の組み合わせが決定する（図４（ｂ））。この場合、入力回線＃２が選択されたので、ＲＲａは、入力回線＃２を最も低い優先度とするように、ＲＲａ＝２となる。また、出力回線＃１が選択されたので、入力回線＃２のＲＲ値ＲＲｂは、出力回線＃１を最低優先度とするように、ＲＲｂ＝１とされる。
【０１２８】
つぎに、入力回線＃２と出力回線＃１につながる候補のうち決定したもの以外は全て削除する。この場合は、図４（ｂ）（ｃ）に示すように、入力回線＃２−出力回線＃３、入力回線＃１−出力回線＃１、入力回線＃３−出力回線＃１の候補が削除される。この削除により、図４（ｃ）に示すように、入力回線側の待ち候補数は、＃１が２、＃２が０、＃３が１、＃４が２となり、出力回線側の待ち候補数は、＃１が０、＃２が１、＃３が２、＃４が２となる。
【０１２９】
第２回目の決定手順では、まず、入力回線として、候補数の最も少ない入力回線＃３が選択される。入力回線＃３が指定する出力回線は出力回線＃４のみであるので、第２回目の決定手順では、入力回線＃３と出力回線＃４の組み合わせが選択される（図４（ｄ））。ＲＲａは、入力回線＃３を最も低い優先度とするように３とされ、また入力回線＃３のＲＲｂは出力回線＃４を最も低い優先度とするように４とされる。入力回線＃３と出力回線＃４につながる候補のうち決定したもの以外、この場合は、入力回線＃４−出力回線＃４の組み合わせが削除される。この削除により、図４（ｅ）に示すように、入力回線側の待ち候補数は、＃１が２、＃２が０、＃３が０、＃４が１となり、出力回線側の待ち候補数は、＃１が０、＃２が１、＃３が２、＃４が０となる。
【０１３０】
第３回目の決定手順では、まず、入力回線として、候補数の最も少ない入力回線＃４が選択される。入力回線＃４が指定する出力回線は、出力回線＃３のみであるので、第３回目の決定手順では、入力回線＃４と出力回線＃３の組み合わせが選択される（図４（ｆ））。ＲＲａは、入力回線＃４を最も低い優先度とするように４とされ、また入力回線＃４のＲＲｂは出力回線＃３を最も低い優先度とするように３とされる。入力回線＃４と出力回線＃３につながる候補のうち決定したもの以外、この場合は、入力回線＃１−出力回線＃３の組み合わせが削除される。この削除により、図４（ｇ）に示すように、入力回線側の待ち候補数は、＃１が１、＃２が０、＃３が０、＃４が０となり、出力回線側の待ち候補数は、＃１が０、＃２が１、＃３が０、＃４が０となる。
【０１３１】
第４回目の決定手順では、図４（ｈ）に示すように、入力回線＃１と出力回線＃２の組み合わせが選択される。ＲＲａは、入力回線＃１を最も低い優先度とするように１とされ、また入力回線＃１のＲＲｂは出力回線＃２を最も低い優先度とするように２とされる。
【０１３２】
図５は、上述した実施の形態２のアルゴリズムを実現するための回路構成を示すものである。但し、上記図３あるいは図４の説明では、入力回線（或いは出力回線）を選択するときに、候補数の同じ入力回線（或いは出力回線）が存在しているときには、ＲＲ方式を用いて１つの入力回線（或いは出力回線）を選択するようにしているが、図５の回路においては、候補数の同じ入力回線（或いは出力回線）が存在しているときには、入力回線番号（あるいは出力回線番号）の小さい方を優先して選択するようにしている。
【０１３３】
図５に示す組み合わせ決定回路１０は、選択行列候補削除部２１と、行候補数計算部２２と、行用の最小値比較器２３と、デコーダ２４と、選択行非選択列候補削除部２５と、列候補数計算部２６と、列用の最小値比較器２７と、選択結果保存レジスタ２８とを備えている。
【０１３４】
図５において、入出力インタフェースは以下の通りである。
入力信号線（Ｎ×Ｎビット）
dataw[N:1][N:1]；Ｎ個の出力回線に対するＮ個の入力回線のデータ転送要求の候補を示す転送要求候補データである。上位の[N:1]が入力回線、下位の[N:1]が出力回線を表し、[N:1][N:1]でＮ×Ｎの行列を表している。各ビットにおいて、１：データあり、０：データなしである。
出力信号線（Ｎ×ｎビット、組み合わせの選択結果）
datar[N:1][n:1]；上位の[N:1]が入力回線、下位の[n:1]が出力回線を表し、[N:1][n:1]でＮ×ｎの行列を表している。
クロック
CLK；一回の決定に最大でＮクロック必要
【０１３５】
入力信号は、データの有無を示すdatawと、クロックCLKである。入力datawのデータ形態は、先の実施の形態１と同じである。出力datarのデータ形態は、先の実施の形態１のように、格子点にビットが立つのではなく、行毎に列番号が与えられる。この組み合わせ決定回路１０では、数値に関しては、全て１から数えており、０は無効であることを意味している。出力datarは、行毎に与えられる数値が１〜Ｎまでの値であれば、その行には選択された候補が存在し、その数値が列番号を示しており、行毎に与えられる数値が０であった場合にはその行は候補が選択されていないことを意味する。
【０１３６】
また、図５において、ｎは、数値１〜Ｎを表すのに必要なビット数である。数値の内容が基本的に０からＮ−１ではなく１からＮとしたことによって、結果を数値として示すのに必要なビット数を表すｎの値は図内右下に注釈で示したようになる。Ｎ≦２(n-1)としてあるが、実現にあたってはＮ＝２n-1となるのが一般的である。Ｎ＝４のとき、例えば、ｎ＝３である。
【０１３７】
選択行列候補削除部２１は、既に選択された行および列の候補を全て削除する処理を行うもので、選択結果保存レジスタ２８から出力されるdataSelの内容から選択済みの行および列を検索し、入力されるdataw中の対応する行および列の値を０に変更するという処理を行っている。例えば、図１（ｂ）の格子点モデルにおいて、dataSelが２行３列が選択されたことを示しているとすると、２行の全ての候補と、３列の全ての候補が０に変更される。
【０１３８】
この選択行列候補削除部２１での処理を、数式化すると以下のようになる。
dataDel＝dataw，ただし以下の変更を加える；
if dataSel[i]＞０ then dataDel[i]＝０      （行の０化）
if dataSel[i]＝ｊ then dataDel[k][j]＝０  （列の０化）
(ｉ，ｊ、ｋ＝１，２，…，Ｎ)
なお、dataSel[i]は、ｎビット（Ｎビットではなく）の数値を表しており、数値は０〜Ｎまでの値が有効であり、０のときまだ決定していないことを示している。
【０１３９】
選択行列候補削除部２１での処理は、数式ではループが必要な処理となるが、論理回路でこれを実現する場合は、デコーダ、セレクタ、および０化のための論理積などの組み合わせ回路となる。第１回目の決定手順では、dataSelの内容は当然全て０であるので、datawの内容がそのままdataDelへ出力されることになる。選択行列候補削除部２１の出力dataDelは、行候補数計算部２２および選択行非選択列候補削除部２５に入力されている。
【０１４０】
行候補数計算部２２は、各行について候補数を計算するブロックである。行候補数計算部２２での処理を数式化すると以下のようになる。
cLine[i]＝dataDel[i][1]＋dataDel[i][2]＋…＋dataDel[i][N]
(ｉ＝１，２，…，Ｎ)
【０１４１】
行候補数計算部２２で計算された各行についての候補数計算結果cLineは、そのまま最小値比較器２３へ入力される。
【０１４２】
最小値比較器２３は、入力されたＮ個のcLine[i]のうち、最小であるもののうちの１つを選択し、そのｉ値をselLへ出力するものである。このときcLine[i]＝０であるものに関しては比較の対象としない。全てのcLine[i]が０である場合には、selLは０を出力する。これを回路実現イメージを絡めて数式化すると以下のようになる。
0003863421.tif 000005
【０１４３】
cLineのうち０であるものを無効とするために、最初にcLine[i]が０の場合には、実際に比較を行うためのビット列であるcLineSの最上位ビットに１を立て、必ず最大値のうちの１つになるようにしておく。そして最下位ｎビットには行の順番を示す値（行番号）を挿入し、cLine[i]に同じ値が複数あっても最終的にこの最下位の値によって一意に決定することができるようにしている。こうすると、選択されたcLineS、つまりcLineRの最上位ビットを確認したときに１が立っていれば候補が全くなくて無効であることを意味するので、selLに０を出力すればよく、最上位ビットが０であれば行番号に相当するcLineRの最下位ｎビットをselLに出力する。
【０１４４】
比較を行うためのビット列であるcLineS[i]は２ｎ＋１ビット幅で、以下のビット配列となっている。
0003863421.tif 000006
【０１４５】
この場合、最小値比較器２３においては、最小値を示すcLine[i]が複数個あった場合には、行番号の小さい方を優先して選択するようにしている。最小値比較器２３のｎビット出力selLは、デコーダ２４に入力され、ここでＮビットにデコードされる。
【０１４６】
デコーダ２４の出力であるdecLは、selLが０の時は全てのビットが０となって、選択されたものがないことを示している。デコーダ２４での処理を数式化すると以下のようになる。
0003863421.tif 000007
【０１４７】
デコーダ２４の出力decLは２つに分岐され、１つは選択行非選択列候補削除部２５に入力され、もう１つは選択結果保存レジスタ２８に入力される。
【０１４８】
次に、選択行非選択列候補削除部２５について説明する。選択行非選択列候補削除部２５では、デコーダ２４の出力decLを用いて、選択された行についての候補の有無を確認し、選択された行に候補が存在する場合は、候補の存在しない列についての候補を全て削除する。すなわち、その後行われる最小値比較器２７での比較処理では、選択された行に候補が存在する場合、候補が存在する列から最小の候補数を持つ列を選択する処理を行わなければならないが、選択された行については候補が存在しない列でも、選択されていない他の行に候補が存在している可能性はある。このような選択されていない他の行に候補が存在している列については、最小値比較器２７での比較処理の対象から外さなくてはならないので、選択行非選択列候補削除部２５で、選択された行で、候補のない列の候補を０化するようにしている。最小値比較器２７での比較処理では、０は無視される。例えば、図１（ｂ）の格子点モデルにおいて、decLが２行を選択されたことを示しているとすると、２行に候補のない２列の候補および４列の候補が全て０化される。
【０１４９】
選択行非選択列候補削除部２５の動作を数式化すると以下のようになる。
dataCol＝dataDel，ただし以下の変更を加える；
if dataDel[decL][j]＝０ then dataCol[i][j]＝０
(ｉ、ｊ＝１，２，３，…，Ｎ)
【０１５０】
列候補数計算部２６は、選択行非選択列候補削除部２５の出力dataColを用いて各列について候補数を計算し、計算した各列の候補数値cClmを最小値比較器２７に入力する。列候補数計算部２６での処理を数式化すると以下のようになる。
cClm[j]＝dataCol[1][j]＋dataCol[2][j]＋…＋dataCol[N][j]
(ｊ＝１，２，…，Ｎ)
【０１５１】
最小値比較器２７は、値が０でないcClmのうち最小であるものを選択して、その列番号をselCへ出力する。この場合、最小値比較器２７は、最小値比較器２３と同じ回路構成を用いている。その処理内容を数式化すると、次のようになる。
0003863421.tif 000008
【０１５２】
この場合、最小値比較器２７においては、最小値比較器２３と同様、０でない最小値を示すcClmが複数あった場合には列番号の小さいものが優先的に選択されるようにしている。このselCは、選択結果保存レジスタ２８に入力される。
【０１５３】
選択結果保存レジスタ２８は、複数個（Ｎ個）のレジスタを備え、先に得られたデコーダ２４の出力decLによって選択されたレジスタに列情報として与えられるselCの値を保存する。選択結果保存レジスタ２８の出力は、dataSelとして、選択行列候補削除部２１に入力されるとともに、入出力回線の決定結果datarとして出力される。その動作を数式化したものを以下に示す。この場合、レジスタとして、イネーブル付きDタイプ-フリップフロップを用いている。
reg[N:1][n:1]；
reg.CLK＝CLK，reg[i][m]．D＝selC[m]，datar＝reg.Q，
reg[i][m].EN＝decL[i]
(ｉ＝１，２，３，…，Ｎ)，(ｍ＝１，２，…，ｎ)
なお、reg.CLKはレジスタのクロック、reg.Dはレジスタのデータ入力、reg.Qはレジスタの保存データ出力、reg.ENはレジスタの正論理のイネーブル入力を表す。
【０１５４】
このように、選択結果保存レジスタ２８より前段の各組み合わせ回路の内容が安定するのに十分な時間経過毎にクロックCLKを入力することで、選択された行毎に最適な列が決定され、選択行列候補削除部２１の出力であるdataDelに候補がなくなるか、あるいはＮ回クロックを入力した時点で組み合わせ決定手順を完了することができる。
【０１５５】
つぎに、図６は、先の図３あるいは図４に示した方式を実現するための回路構成を示すものである。すなわち、図６に示す組み合わせ決定回路１０では、入出力回線を選択するときに、候補数の同じ入出力回線が存在しているときには、ＲＲ方式を用いて１つの入出力回線を選択するようにしている。
【０１５６】
図６に示す組み合わせ決定回路１０において、選択行列候補削除部２１、行候補数計算部２２、デコーダ２４と、選択行非選択列候補削除部２５と、列候補数計算部２６および選択結果保存レジスタ２８に関しては、先の図５に示したものと同じ機能を有している。
【０１５７】
この図６の組み合わせ決定回路１０においては、ｎビットレジスタ３０、Ｎ×ｎビットレジスタ３１を追加するとともに、最小値比較ＲＲ回路３２および３３でＲＲが可能なように、図５の最小値比較器２３および２７にＲＲ機能を追加している。
【０１５８】
図３あるいは図４の説明からも判るように、行を選択するＲＲ値（ＲＲａ）は１つなのに対して列を選択するためのＲＲ値（ＲＲｂ）は行毎にあるのが望ましいので、列を選択するためのＲＲ値はＮ個設けている。そして、列を選択するときに使用するＲＲ値については、行の選択結果であるdecLを利用して、Ｎ×ｎビットレジスタ３１から、使用するＲＲ値のレジスタを選択している。
【０１５９】
まず、行選択のための最小値比較ＲＲ回路３２の動作と、ＲＲ値を保存するためのｎビットレジスタ３０の動作を数式化したものを以下に示す。
if cLine[i]＝０ then cLineS[i][2n+1]＝1
0003863421.tif 000009
【０１６０】
ｎビットレジスタ３０は、イネーブル付きDタイプ-フリップフロップを用いている。
reg[n:1]；
reg.CLK＝CLK，reg[m].D＝selL[m]，s＝reg.Q，reg.EN＝(selL＞０)
(ｍ＝１，２，…，ｎ)
【０１６１】
最小値比較ＲＲ回路３２については、比較器としての実現方式は図５の最小値比較器２３と同様であるが、唯一異なるのがｃLineSの下位ｎビットに適用する内容で、((Ｎ＋ｉ−ｓ−１)％Ｎ)＋１を適用する。ここで、“％”は左辺の数値を右辺の数値で割ったときの剰余を返す演算子である。上記数式では最初の括弧内が負数にならないようにするためにＮを加算しているが、回路上で有効範囲ｎビットの符号なし演算回路を生成すると、小さい数値から大きい数値を減算するときには自動的に桁借りが行われるのでＮの加算は必要ない。
【０１６２】
実際に((Ｎ＋ｉ−ｓ−１)％Ｎ)＋１にｉ＝１から適用すると、図７に示す値となる。ここで適用するＲＲ方式では、前回の決定結果に相当する対象が今回では最も優先順位が低くなり、次の対象がもっとも優先順位が高くなる。比較結果として最小値を探すので、最も優先順位の高い対象のＲＲ値が一番小さい値（＝１）で、前回の決定結果に相当する対象はもっとも大きい値（＝Ｎ）でなければならない。その間は順に巡回している必要がある。図７によれば、上記の式((Ｎ＋ｉ−ｓ−１)％Ｎ)＋１は、それを満たしていることがわかる。
【０１６３】
一方、比較結果については、図５の最小値比較器２３の場合は、cLineSの下位ｎビットをそのまま利用すれば良かったが、図６の最小値比較ＲＲ回路３２の場合は、上記したように変換した値を用いているので、元に戻す必要がある。
【０１６４】
それが((cLineR[ｎ:１]＋ｓ−１)％Ｎ)＋１の式である。この式を、上記と同様に、実際に計算してみると図８に示すような結果となる。((cLineR[ｎ:１]＋ｓ−１)％Ｎ)＋１の値はまさにｉと一致する。これによって、最小比較でＲＲ方式を実施し、その後選択された行の番号を間違いなく得られることが示された。
【０１６５】
ＲＲ値保存のためのｎビットレジスタ３０に関しては、基本的にはselLとsの間にレジスタを挿入するだけである。但し、reg.EN＝(selL＞０)の意味は、selLが０より大きいときには１を入力し、selLが０の時には０を入力することであり、これにより、最小値比較ＲＲ回路３２の出力結果が０、つまり比較結果が無効であったときにはレジスタを変化させないようにしている。
【０１６６】
次に、列の選択のための最小値比較ＲＲ回路３３およびＮ×ｎビットレジスタ３１について説明する。
【０１６７】
最小値比較ＲＲ回路３３の構成は、上述した行選択のための最小値比較ＲＲ回路３２と全く同じであり、その説明は省略する。外部で、ＲＲ値を保存するためのＮ×ｎビットレジスタ３１においては、デコーダ２４の出力decLによって対応するレジスタを選択するセレクタを設けている。Ｎ×ｎビットレジスタ３１には、イネーブル付きDタイプ-フリップフロップを用いている。その動作を数式化したものを以下に示す。
reg[N:1][n:1]；
reg.CLK＝CLK，reg[i][m].D＝selC[m]，reg[i][m].EN＝decL[i]，
if decL[i]＝１ then s[m]＝reg.Q[i][m]
(ｉ＝１，２，３，…，Ｎ)、(ｍ＝１，２，…，ｎ)
【０１６８】
つまり、レジスタ３１の出力ｓへの出力内容は、Ｎ組あるｎビットのレジスタのうちdecL中のビットが１のものに対応するレジスタとなる。またクロックCLKによって、その内容を書き換えるレジスタも、同様にdecLにおける対応するビットが１となっているレジスタとなる。こうして、対象となっている行に対応する列選択用のＲＲ値のみが最小値比較ＲＲ回路３３に入力され、また、その結果を次のクロックCLKで同一のレジスタに保存することができる。
【０１６９】
このようにこの実施の形態２によれば、各決定手順後に削除される転送待ちデータの候補数に注目し、常にそれが最小になるように入出力回線の組み合わせを決定しているので、通信交換装置におけるデータ転送能力を、従来のＲＲ方式よりも、向上させることができる。
【０１７０】
実施の形態３．
つぎに、図９を用いてこの発明の実施の形態３について説明する。この実施の形態３は、上記したアルゴリズムとは別のある要因が発生した時に、外部から特定行優先信号fctL[n:1](＝１以上：要因発生、０：要因なし)および特定列優先信号fctC[n:1](＝１以上：要因発生、０：要因なし)を、指定行優先選択部４０および指定列優先選択部４１に入力することで、特定行優先信号fctL[n:1]あるいは特定列優先信号fctC[n:1]で指定された行，列の計数値cLine，cClmを、最小値比較器２３，２７で最優先選択される最小値、すなわち１に一時的に置き換えるようにしている。このように、特定の行，列の計数値cLine，cClmを１に一時的に置き換えた後、最小値比較器２３，２７での通常の最小値選択処理を行うことで、特定の行，列が最初に選択される可能性を大きくすることができる。
【０１７１】
行候補数計算部２２での処理を数式化すると次のようになる。
cLine[i]＝dataDel[i][1]＋dataDel[i][2]＋…＋dataDel[i][N]
(ｉ＝１，２，…，Ｎ)
【０１７２】
指定行優先選択部４０での処理を数式化すると次のようになる。
if fctL＞０ then
if cLine[fctL]＞０ then cLine[fctL]＝１
【０１７３】
列候補数計算部２６での処理を数式化すると次のようになる。
cClm[j]＝dataCol[1][j]＋dataCol[2][j]＋…＋dataCol[N][j]
(ｊ＝１，２，…，Ｎ)
【０１７４】
指定列優先選択部４１での処理を数式化すると次のようになる。
if fctC＞０ then
if cClm[fctC]＝１ then cClm[fctC]＝１
【０１７５】
上式は、要因が発生して対象となった行、あるいは列に対して計数値が１となるようにする手順を追加するものである。ただし、対象となった行または列に候補がいない場合には、１への置き換え処理を実行しない。
【０１７６】
なお、図９の場合は、fctCについては、特に行毎に別の値を指定するための回路を図示していないが、fctC[N:1][n:1]として、行毎に別の値が与えられるようにし、デコーダから出力されるdecLの値を利用して行毎に別の値を選択するような構成をとるのが、一般的である。また行、列共にfctL、fctCが適用されることは必然ではなく、行または列のみをfctLまたはfctCによって選択させるようにしてもよい。また、図９の場合は、図５に示した組み合わせ決定回路１０に、指定行優先選択部４０および指定列優先選択部４１を追加するようにしたが、図６に示したＲＲ方式を用いる組み合わせ決定回路１０に、指定行優先選択部４０および指定列優先選択部４１を追加するようにしてもよい。
【０１７７】
同様に、fctL、fctCの適用例として、強制的に対象となる行、または列を選択するためには最小値比較器に適用するのがもっとも現実的な方法である。すなわち、以下に示す手法では、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行、または列が強制的に選択されるようにする。最小値比較器で行われる処理についての数式を以下に示す。
0003863421.tif 000010
なお、上記の数式は、外部要因によるデータを元に、外部要因の対象となる行または列以外の計数値を０化した後の処理について記述したものである。
【０１７８】
ここで、selXはselLおよびselCを代表しており、cXxxはcLineおよびcClmを代表しており、fctXはfctLおよびfctCを代表している。この数式は、０より大きい最小値を探す時に、fctXの示すcXxxが０以上、つまり候補がいた場合には、selXにfctXを代入し、変更のための条件を０より大きく１より小さいという絶対に起こりえない状況にして、selXを変化させないようにしている。
【０１７９】
なおＲＲ機能付きの比較器においても同様で、以下の数式となる。
0003863421.tif 000011
【０１８０】
ＲＲ値保存のためのレジスタについては全く変更はないため、特に示さない。また、前記同様、fctCについては、fctC[N:1][n:1]として、行毎に別の値が与えられるようにし、デコーダから出力されるdecLの値を利用して行毎に別の値を選択するような構成をとるのが、一般的である。また行、列共にfctL、fctCが適用されることは必然ではなく、行または列のみをfctLまたはfctCによって選択させるようにしてもよい。
【０１８１】
実施の形態４．
次に、図１０および図１１を用いてこの発明の実施の形態４について説明する。この実施の形態４は、処理順序についての複数の優先クラスがあったときの、つまりＮ×Ｎの格子モデルが複数枚あって、各格子モデル間に優先クラスが設定されているときの、組み合わせ決定アルゴリズムを示すものである。このように複数の格子モデル間に優先クラスが設定されているときは、入出力回線を選択するときの条件は、各格子モデルの同一の行と同一の列についてはそれら全てにおいて候補を１つしか選択できない、言い換えると全ての格子のｉ（ｉ＝１〜Ｎ）行および全ての格子のｊ（ｊ＝１〜Ｎ）列において選択可能な候補はただ１つであるという条件となる。
【０１８２】
この実施の形態４においては、つぎのようなアルゴリズムを採用している。
ステップ(1)
候補の有無を上位の優先クラスの格子から見ていき、候補があったうちの最上位の優先クラスの格子において、前述した実施の形態２の格子点選択手順を実施し、
ステップ(2)
決定した格子点の行および列について、決定した格子とそれよりも下位の全ての格子についても対応する行および列の候補を削除し、
ステップ(3)
上記ステップ(1)およびステップ(2)を候補がなくなるまで、最大Ｎ回繰り返す。
【０１８３】
図１０は、上記アルゴリズムを実現するための組み合わせ回路の構成を示すものである。図１０において、入出力インタフェースは以下の通りである。
入力信号線（Ｍ×Ｎ×Ｎビット）
dataw[M:1][N:1][N:1]；上位の[M:1]が優先クラス、中位の[N:1]が入力回線、下位の[N:1]が出力回線を表している。
出力信号線（Ｎ×（ｍ＋ｎ）ビット、組み合わせの選択結果）
datar[N:1][m+n:1]；上位の[N:1]が入力回線、下位の[m+n:1]が出力回線と優先クラスを表している。
【０１８４】
以下、図６に示した実施の形態２の回路構成から追加あるいは変更になった構成要素についてのみ説明する。
【０１８５】
選択行列候補削除部５０での処理を数式化すると次のようになる。
dataSelC＝dataw、ただし以下の変更を加える；
if dataSel[i]＞０ then dataSelC[h][i]＝０      （行の０化）
if dataSel[i][n:1]＝ｊ then dataSelC[h][k][j]＝０  （列の０化）
(ｈ＝１，２，…，Ｍ)、(ｉ，ｊ，ｋ＝１，２，…，Ｎ)
【０１８６】
ここでdataSel[i][n:1]は、dataSel[i]の下位ｎビットを意味する。上式によれば、削除対象となる候補は、dataSelの値に対応する行および列の全クラスの候補にわたっていることになる。
【０１８７】
クラス選択部５１は、決定手順の実行対象となるクラスを選択し、該選択したクラスにおける選択行列候補削除部５０の出力データをdataDelとして出力するとともに、選択したクラス番号classを出力する。その処理を数式化すると次のようになる。
class＝０、次に以下の手順を実施；
if dataSelC[h][i][j]＝１ then dataDel＝dataSelC[h]、class＝h
(ｈ＝１，２，…，Ｍ)，(ｉ，ｊ＝１，２，…，Ｎ)
【０１８８】
ここで、ｈは最優先クラスに対応する１から順にカウントし、各ｈの値についてｉおよびｊは全て確認する。条件が成立した時点で動作を終了する。常にクラスの上位から確認していき、候補が１つでも存在すれば、そのクラスの候補データを手順実施対象としてdataDelに出力するのと同時に、そのクラス番号をclassに出力する。実際の回路としては、dataSelCをクラス毎に全て論理和を取って、そのクラス毎の結果をプライオリティエンコーダ(優先選択回路)にかけて、論理和の結果が１であるもののうち最上位のクラスを選択し、それに対応する番号(プライオリティエンコーダの結果が０の時は０)を出力するという形態となる。
【０１８９】
選択結果保存レジスタ５２は、クラスに関するｍビットの情報も保存できるようにレジスタを追加している。すなわち、図６の選択結果保存レジスタ２８に対し、datar[i]のそれぞれの上位にクラス番号を保存するためのｍビットを追加した。
【０１９０】
つぎに、図１１に、上記図１０に示した組み合わせ決定回路の変形形態を示す。この図１１に示す組み合わせ決定回路においては、複数の優先クラスを扱う組み合わせ決定アルゴリズムにおいて、ある優先クラスの決定手順において候補数を比較するときに、候補数が同じであった場合にはそれよりも下位の優先クラスの候補数を１クラス下位まで、あるいはそれよりも更に下位まで順次比較することによって、下位の優先クラスの候補の状態も考慮に入れて組み合わせを決定するようにしている。但し、図１１に示す組み合わせ決定回路においては、下位のクラスまで考慮するのは、列決定のときのみとし、またそのとき考慮する下位のクラスを１つ下位のクラスの候補数までとし、それでも一意に決定できない場合はＲＲを利用するようにしている。
【０１９１】
以下、図１０に示した回路構成から追加あるいは変更になった構成要素についてのみ説明する。
【０１９２】
クラス選択部６０では、図１０のクラス選択部５１に対し、決定手順の実行対象となるクラスより１つ下位のクラスの候補データdataDel2も同時に出力する機能を追加している。最下位のクラスが手順実行対象となった場合には、１つ下位のクラスの候補データは全て０を出力する。その機能を数式化すると、つぎのようになる。
class＝０、次に以下の手順を実施；
0003863421.tif 000012
【０１９３】
ここで、ｈは１から順にカウントし、各ｈの値についてｉおよびｊは全て確認する。条件が成立した時点で動作を終了する。
【０１９４】
選択行非選択列候補削除部２５には、１つ下位のクラスの処理用にもう１つ回路を追加する。動作自体は、前述した選択行非選択列候補削除部２５と変わらない。
【０１９５】
列候補数計算部２６には、１つ下位のクラスの処理用にもう１つ回路を追加する。動作自体は、前述した列候補数計算部２６と変わらない。
【０１９６】
クラス選択部６０から出力されるdataDel2は、前述と同様にして、選択行非選択列候補削除部２５および列候補数計算部２６で処理され、対象クラスの候補数結果の下位ｎビットに追加されて、最小値比較ＲＲ回路６１に入力される。
【０１９７】
最小値比較ＲＲ回路６１については、１つ下のクラスも同時に比較できるよう、比較ビット幅をｎビット更に拡張する。すなわち、比較ビット幅は、１(対象クラスの候補数の有無)＋ｎ(対象クラスでの候補数)＋ｎ(１つ下位クラスでの候補数)＋ｎ(ＲＲ値)で、３ｎ＋１ビット幅となる。なお、候補数が０か否かを確認する対象とするのは対象クラスの候補数に関してであり、下位クラスの候補数は問わない。最小値比較ＲＲ回路６１での処理を数式化すると、次のようになる。
0003863421.tif 000013
【０１９８】
このように、図１１の組み合わせ決定回路においては、対象クラスの候補数を適用するビットとＲＲを適用するビットの間に、下位クラスの候補数を適用するビットを設けて比較することによって、対象クラスの候補数で比較して一意に決定できない場合は、１つ下位クラスの状況を見て、削除される候補が少ない方を選択することによって、このアルゴリズムの基本原理である一回の手順で削除される候補数をできるだけ少なく維持することを実現し、結果的により多くの候補が選択されるための確率を高くすることができる。つまり、実際に通信装置にこのアルゴリズムを適用した場合に、装置としてのデータ転送能力を高レベルに維持することができる。
【０１９９】
シミュレーション評価結果．
図１３に上記の方式を８×８の通信交換装置に適用した場合について計算機シミュレーションによる評価結果を示す。適用した手順は、ＲＲ方式については図１４に示したもの、本発明におけるアルゴリズムについては図３に示した方式である。どちらもHead of Lineブロッキングによるスループットの低下を解消するために、仮想出力キューを各入力ポートに８個ずつ装備している。また交換は256バイト固定長のセル単位で、簡単のため入力トラヒックも全て256バイト固定長とした。また各入出力ポートの速度は10Ｇｂ／ｓ(１０ギガビット毎秒)である。どの測定結果も乱数ページを変えて５回測定し、その平均を測定結果とし、その９５％信頼区間を併せて示した。入力トラヒックは全て指数分布を利用したもっとも一般的なマルコフ過程であり、帯域はポート速度の９９％平均(９．９Ｇｂ／ｓ)とした。そして各入力ポートから出力ポートへの帯域の振り分け方は、以下の２種類（均等、不均等）の場合について評価した。
【０２００】
均等
各入力ポートから各出力ポートへそれぞれ８分の１ずつ帯域を振り分ける。つまり、ある入力ポートから見ると全ての出力ポートへ８分の１ずつトラヒックが流れるようにし、ある出力ポートから見ると全ての入力ポートから８分の１ずつトラヒックが入力している。
【０２０１】
不均等
図１２に示したように、各入力ポートから各出力ポートへのトラヒック量は均一にはなっていない。図１２では、例えば入力ポート＃１から各出力ポートへの帯域の割り当ては、出力ポート番号＃１から順に、７：４：８：１：６：５：２：３の比になっている。これらの値の合計は３６であるので、出力ポート＃１には入力ポート＃１の全トラヒック量の３６分の７が流れることになる。なお図１２では、縦横共に合計が３６となっている。これはつまり、各出力ポートでも、合計では各入力ポートのトラヒック量と同じトラヒックが平均的に流れてきており、出力ポートでの帯域不足を原因とする定常的なバッファあふれは起きないことを意味している。
【０２０２】
また評価したデータは廃棄率および交換決定率の２つである。
廃棄率：入力したトラヒックのうち、どれだけの量のトラヒックが入力バッファで廃棄されたのかを、比率の常用対数を取ったもの。１％の廃棄率であれば、値は−２(＝log0.01)となる。
交換決定率：毎回の組み合わせ決定手順の結果、いくつの候補が決定したのかを記録し、その平均を求めたもの。８×８であり最大８の候補が決定されるので、各回にｋ個の候補が決定されてｋ個のデータが転送されたとすると、８分のｋを記録して平均したものである。もともと９９％トラヒックであるので、最大で約９９％となる。図１３に示すシミュレーション結果に対する考察を以下に示す。
【０２０３】
廃棄率について；
均等のトラヒックの場合には、本発明とＲＲ方式ではほとんど差は見られない。むしろＲＲ方式の方が廃棄率は低くなっている。ただし、取り立てて言うほどの差ではない。ＲＲ方式は、元々ポート毎の平等性を発揮するには最適な方式であるので、均等なトラヒックにおいては特にその能力を発揮することができるためである。しかし、不均等のトラヒックを入力した場合にはその結果は一変する。本発明では−４．２７の廃棄率で、均等の時よりも良くなっているが(実質的にはさほど大きな差ではない)、ＲＲ方式では極端にその特性を落とし、−１．４８となっている。これは３０パケットに１つ廃棄するという、かなり特性の悪い状態である。これは、逆に平等性を発揮するばかりに、不均等のトラヒックには柔軟に対応できないためである。本発明では、とにかく通信装置全体としての交換能力を高めるようにアルゴリズムが設計されているため、不均等なトラヒックが入力されても柔軟に対応し、均等の時よりもわずかながら良い特性を示すほどになっているのである。現実のネットワークにおいて均等にトラヒックが流れていることなどまれであることから、本発明が優位である。
【０２０４】
決定率について；
ＲＲ方式の不均等トラヒックの場合以外の廃棄率が−４．０程度であるということは、１００００パケットに１つ程度の廃棄ということになるが、図１３中の入力トラヒック平均の値に対して、上記ＲＲ方式の不均等トラヒック以外はまさに１００００分の１程度の差しかない(全体９９に対して０．０１程度)ことがわかる。ＲＲ方式の不均等トラヒックの場合だけははっきりしており、１００分の３の違いが出ている。１００００分の１に対して１００分の３ということは、３００倍の違いである。この特性の違いは、廃棄が一般に再送による更なるトラヒックを生み出すことから、９９％といった本シミュレーションのような過酷な環境に対しても耐え抜くための不可欠の要素となる。
【０２０５】
【発明の効果】
以上説明したように、この発明にかかるデータ転送組み合わせ決定方法によれば、Ｎ×Ｎビットのデータ転送要求候補データを、１からＮまでの全ての順列組み合わせパターンを表すＮ×ＮビットのＮ！個の順列組み合わせデータと夫々論理積をとり、論理積が成立する候補数が最大となる順列組み合わせパターンを探し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定するようにしているので、通信交換装置のデータ転送能力を最大に高めることが可能となる。また、論理積が成立する候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するようにしているので、入出力回線の組み合わせ選択を平等になし得る。また、候補数が最大となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしているので、これら２種類の比較手順を複数のクロックステップを踏まずに同時に実行することが可能となり、これにより回路の単純簡素化、回路の高速化等を実現することが可能となる。
【０２０８】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行、列毎に計数し、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す行または列を１つ選択して記憶し、選択した行または列の中の候補について、その候補が存在する列または行の候補の数のうち最小値を検索して、該最小値を示す列または行を１つ選択して記憶し、上記決定した行上の候補および列上の候補を全て削除し、これらの処理を候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定するようにしており、１回の決定手順後に削除される転送待ちデータの候補数に注目し、常にそれが最小になるように入出力回線の組み合わせを決定していくようにしているので、通信交換装置のデータ転送能力を高レベルに維持することを可能にする。
【０２０９】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、行または列を選択するときに、最小値を示す行または列が複数あった場合に、行から列へ、あるいは列から行への順にラウンドロビン方式を適用して最小値を示す行または列を一意に決定するようにしているので、入出力回線の組み合わせ選択を平等になし得る。
【０２１０】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしているので、これら２種類の比較手順を複数のクロックステップを踏まずに同時に実行することが可能となり、これにより回路の単純簡素化、回路の高速化等を実現することが可能となる。
【０２１１】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、行または列を選択するときに、最小値を示す行または列が複数あった場合に、行番号または列番号の小さい方を優先して選択することにより、最小値を示す行または列を一意に決定するようにしているので、最小値を示す行または列が複数あった場合でも簡便な方法で、最小値を示す行または列を択一選択することができる。
【０２１２】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくするようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を優先的に選択することができる。
【０２１３】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行または列が強制的に選択されるようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を強制的に選択することができる。
【０２１４】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に、上記データ転送組み合わせ処理を実行し、さらに選択決定された行上および列上の候補を全て削除する際に、当該優先クラスに対応する格子における選択決定された行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記選択決定された行上の候補および列上の候補を削除するようにしているので、処理順序に関する複数の優先クラスが設定されている場合においても、データ転送能力を高レベルに維持したデータ交換をなし得る。
【０２１５】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定するようにしているので、一回の手順で削除される候補数をできるだけ少なくすることができ、結果的により多くの候補が選択される確率を高くすることができる。
【０２１６】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、データ転送要求候補データにおける候補数を、Ｎ行×Ｎ列の格子の格子点にある候補の数として、行毎に計数し、該計数された結果が１以上である計数値のうち最小値を検索して、該最小値を示す行を１つ選択して記憶し、選択された行の中の候補について、その候補が存在する列における候補の数を列毎に計数し、前記計数した結果が１以上である計数値のうち最小値を検索して、該最小値を示す列を１つ選択して記憶し、前記決定した行上の候補および列上の候補を全て削除し、前記一連の処理を候補がなくなるまで繰り返し、候補がなくなった時点で記憶されている行、列の組み合わせを前記データ転送するときのデータ転送の組み合わせとして決定するようにしており、１回の決定手順後に削除される転送待ちデータの候補数が最小になるように入出力回線の組み合わせを決定するとともに、各決定手順においては最初に行の候補を選択しつぎに列の候補を選択しているので、効率よく、高速に、最小値を示す列または行が選択されるとともに、通信交換装置のデータ転送能力を高レベルに維持することを可能にする。
【０２１７】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、前記行および列を夫々選択するときに、候補数が最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行および列を一意に決定するようにしているので、入出力回線の組み合わせ選択を平等になし得る。
【０２１８】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、候補数が最小となる順列組み合わせパターンを探す際の候補数の比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしているので、これら２種類の比較手順を複数のクロックステップを踏まずに同時に実行することが可能となり、これにより回路の単純簡素化、回路の高速化等を実現することが可能となる。
【０２１９】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、行および列を夫々選択するときに、最小値を示す行および列が複数あった場合に、行番号および列番号の小さい方を優先して選択することにより、最小値を示す行および列を一意に決定するようにしているので、最小値を示す行または列が複数あった場合でも簡便な方法で、最小値を示す行または列を択一選択することができる。
【０２２０】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、外部要因が発生した時に、外部要因の対象となる行または列の計数値を最小値に置き換えることによって、特定の行または列が最初に選択される可能性を大きくするようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を優先的に選択することができる。
【０２２１】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、外部要因が発生した時に、外部要因の対象となる行または列以外の計数値を０に置き換えることによって、特定の行または列が強制的に選択されるようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を強制的に選択することができる。
【０２２２】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、上位の優先クラスに対応する格子から下位の優先クラスに対応する格子へ順に、上記データ転送組み合わせ処理を実行し、さらに選択決定された行上および列上の候補を全て削除する際に、当該優先クラスに対応する格子における選択決定された行上の候補および列上の候補と、当該優先クラスより下位の全ての優先クラスに対応する格子の前記選択決定された行上の候補および列上の候補を削除するようにしているので、処理順序に関する複数の優先クラスが設定されている場合においても、データ転送能力を高レベルに維持したデータ交換をなし得る。
【０２２３】
つぎの発明にかかるデータ転送組み合わせ決定方法によれば、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、下位の優先クラスの候補の状態にも基づいて組み合わせを決定するようにしているので、一回の手順で削除される候補数をできるだけ少なくすることができ、結果的により多くの候補が選択される確率を高くすることができる。
【０２２４】
つぎの発明にかかる組み合わせ決定回路によれば、Ｎ×Ｎビットのデータ転送要求候補データと１からＮまでの全ての順列組み合わせパターンを表すＮ×Ｎビットの順列組み合わせデータとの論理積を夫々求める論理積回路と、複数の順列組み合わせパターン毎に前記論理積が成立する候補数を演算する個数演算部と、個数演算部の複数の出力を比較することにより、候補数が最大となる順列組み合わせパターンを検索し、そのうちの１つを前記データ転送するときのデータ転送の組み合わせとして決定する検索決定回路とを備え、Ｎの階乗個ある全ての順列組み合わせパターンについて総当たりで確認しているので、通信交換装置のデータ転送能力を最大に高めることが可能となる。また、検索決定回路に、候補数が最大となる順列組み合わせパターンが複数あるとき、ラウンドロビンを用いて１つの順列組み合わせパターンを選択するラウンドロビン回路を備えるようにしているので、入出力回線の組み合わせ選択を平等になし得る。また、検索決定回路に、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較することにより、候補数が最大となる順列組み合わせパターンを択一選択する比較器を備えるようにしているので、２種類の比較手順を複数のクロックステップを踏まずに同時に実行することが可能となり、これにより回路の単純簡素化、回路の高速化等を実現することが可能となる。
【０２２７】
つぎの発明にかかる組み合わせ決定回路によれば、行候補数計算部、行用最小値比較器、選択行非選択列候補削除部、列候補数計算部、列用最小値比較器、選択結果保存レジスタおよび選択行列候補削除部を備え、１回の決定手順後に削除される転送待ちデータの候補数が最小になるように入出力回線の組み合わせを決定していくようにするとともに、各決定手順においては最初に行の候補を選択しつぎに列の候補を選択しているので、効率よく、高速に、最小値を示す列または行が選択されるとともに、通信交換装置のデータ転送能力を高レベルに維持することを可能にする。
【０２２８】
つぎの発明にかかる組み合わせ決定回路によれば、行用最小値比較器および列用最小値比較器はラウンドロビン回路を夫々備え、最小値を示す行および列が複数あった場合に、ラウンドロビンを用いて最小値を示す行を一意に決定するようにしているので、入出力回線の組み合わせ選択を平等になし得る。
【０２２９】
つぎの発明にかかる組み合わせ決定回路によれば、行用最小値比較器および列用最小値比較器は、各比較処理において、比較ビット中の上位ビットを前記候補数として用い、その下位ビットをラウンドロビンを行うための比較値として用い、これら比較ビットを一括して同時に比較するようにしているので、２種類の比較手順を複数のクロックステップを踏まずに同時に実行することが可能となり、これにより回路の単純簡素化、回路の高速化等を実現することが可能となる。
【０２３０】
つぎの発明にかかる組み合わせ決定回路によれば、行用最小値比較器および列用最小値比較器は、最小値を示す行および列が複数あった場合に、小さい行番号を優先して選択することにより、最小値を示す行および列を一意に決定するようにしているので、最小値を示す行または列が複数あった場合でも簡単な構成で、最小値を示す行または列を択一選択することができる。
【０２３１】
つぎの発明にかかる組み合わせ決定回路によれば、指定行優先選択部は、前記行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行を最小値を置き換えて前記行用最小値比較器に入力するとともに、指定列優先選択部は、前記列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列を最小値を置き換えて前記列行用最小値比較器に入力するようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を優先的に選択することができる。
【０２３２】
つぎの発明にかかる組み合わせ決定回路によれば、行候補数計算部の複数行分の計数結果のうち、外部入力信号の指定行に対応する行の計数結果をそのまま前記行用最小値比較器に入力するとともに、指定行以外の行の計数結果を０に置き換えるようにするとともに、列候補数計算部の複数列分の計数結果のうち、外部入力信号の指定列に対応する列の計数結果をそのまま前記列用最小値比較器に入力するとともに、指定列行以外の列の計数結果を０に置き換えるようにしているので、所望の入力回線番号あるいは出力回線番号を指定するのみで簡便に所定の入力回線あるいは出力回線を強制的に選択することができる。
【０２３３】
つぎの発明にかかる組み合わせ決定回路によれば、選択行列候補削除部、クラス選択部、行候補数計算部、行用最小値比較器、選択行非選択列候補削除部、列候補数計算部、列用最小値比較器、選択結果保存レジスタを備え、１回の決定手順後に削除される転送待ちデータの候補数が最小になるように入出力回線の組み合わせを決定しているので、処理順序に関する複数の優先クラスが設定されている場合において、効率よく、高速に、最小値を示す列または行が選択されるとともに、通信交換装置のデータ転送能力を高レベルに維持することを可能にする。
【０２３４】
つぎの発明にかかる組み合わせ決定回路によれば、行用最小値比較器および列用最小値比較器は、最小値を検索する際、候補数が同じであった場合には、当該優先クラスに対応する格子よりも１段階または複数段階だけ下位の優先クラスに対応する格子までを含めて、候補数を順次比較することによって、最小値を示す行及び列を夫々選択しているので、一回の手順で削除される候補数をできるだけ少なくすることができ、結果的により多くの候補が選択される確率を高くすることができる。
【図面の簡単な説明】
【図１】  この発明の実施の形態１の手順を説明するための図である。
【図２】  この発明の実施形態１にかかる組み合わせ決定回路を例示するブロック図である。
【図３】  この発明の実施形態２の組み合わせ決定アルゴリズムを説明するための工程図である。
【図４】  この発明の実施形態２の組み合わせ決定アルゴリズムを説明するための工程図である。
【図５】  この発明の実施形態２にかかる組み合わせ決定回路を例示するブロック図である。
【図６】  この発明の実施形態２にかかる他の組み合わせ決定回路を例示するブロック図である。
【図７】  図６に示した組み合わせ決定回路の比較器の下位ｎビットに適用するためのＲＲ値の変換式を説明するための図である。
【図８】  図６に示した組み合わせ決定回路の比較器の比較結果を変換前に戻すデータ番号復元式を説明するための図である。
【図９】  この発明の実施形態３にかかる組み合わせ決定回路を例示するブロック図である。
【図１０】  この発明の実施形態４にかかる組み合わせ決定回路を例示するブロック図である。
【図１１】  この発明の実施形態４にかかる他の組み合わせ決定回路を例示するブロック図である。
【図１２】  各入力ポートから各出力ポートへの不均等トラヒックの入力比率を示す図である。
【図１３】  本発明の手法を８×８の通信交換装置に適用した場合について計算機シミュレーションによる評価結果を示す図である。
【図１４】  従来のＳＲＲ方式による交換組み合わせ決定手順を説明するための工程図である。
【図１５】  図１４の転送待ちデータ組み合わせにおいて、最大数のデータ転送を実現する組み合わせ結果と入出力回線形態を示す図である。
【図１６】  最大数のデータ転送を実現する入出力回線形態を示す図である。
【図１７】  従来のＳＲＲ方式による交換組み合わせ決定手順を他のＲＲ値に基づき実行した場合の工程図である。
【符号の説明】
１０  組み合わせ決定回路、１１  論理積回路、１２  個数算出部、１３  論理積成立数演算部、１４  比較ＲＲ部、１５  セレクタ、１６  レジスタ、２１選択行列候補削除部、２２  行候補数計算部、２３  最小値比較器、２４  デコーダ、２５  選択行非選択列候補削除部、２６  列候補数計算部、２７  最小値比較器、２８  選択結果保存レジスタ、３０  ｎビットレジスタ、３１  Ｎ×ｎビットレジスタ、３２，３３  最小値比較ＲＲ回路、４０  指定行優先選択部、４１  指定列優先選択部、５０  選択行列候補削除部、５１  クラス選択部、５２  選択結果保存レジスタ、６０  クラス選択部、６１  最小値比較ＲＲ回路。
【図１】
0003863421.tif 000014
【図２】
0003863421.tif 000015
【図３】
0003863421.tif 000016
【図４】
0003863421.tif 000017
【図５】
0003863421.tif 000018
【図６】
0003863421.tif 000019
【図７】
0003863421.tif 000020
【図８】
0003863421.tif 000021
【図９】
0003863421.tif 000022
【図１０】
0003863421.tif 000023
【図１１】
0003863421.tif 000024
【図１２】
0003863421.tif 000025
【図１３】
0003863421.tif 000026
【図１４】
0003863421.tif 000027
【図１５】
0003863421.tif 000028
【図１６】
0003863421.tif 000029
【図１７】
0003863421.tif 000030