JPH0690233A

JPH0690233A - アクセス調停方式

Info

Publication number: JPH0690233A
Application number: JP23863192A
Authority: JP
Inventors: Kanichi Endo; 乾一遠藤; Naoaki Yamanaka; 直明山中
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1992-09-07
Filing date: 1992-09-07
Publication date: 1994-03-29

Abstract

(57)【要約】【目的】複数のリソースを共有するシステムにおい
て、アクセスの要求発生源とリソースとのアクセスのス
ループットを向上させる。【構成】ある範囲までのアクセス要求を競合調停手段
にまとめて転送し、その範囲内で組合せ可能なアクセス
をすべて成立させる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、情報処理装置、通信用
交換機、特にＡＴＭ交換機、その他バスにより共通に接
続された複数のリソースを有するシステムに利用する。
ここでリソースとは、メモリ装置、出力装置、表示装
置、入力装置、印字装置、機能ユニット、その他システ
ムを運用するためのハードウエアを伴う設備を言う。

【０００２】本発明は、一つのシステムに配置された複
数の共有リソースに対して、そのシステム内から発生す
る複数のアクセス要求の調停に関する。

【０００３】

【従来の技術】図５に示すモデルにより従来技術による
アクセス要求の調停を説明すると、これはリングアービ
タの制御手法によるものである。このモデルには８個の
アクセス要求発生源Ｒ(1) 〜Ｒ(8) と、このアクセス要
求を受け付ける８個のリソースＳ(1) 〜Ｓ(8) がある。
これらはそれぞれマトリクススイッチ手段の入力端子群
と出力端子群に接続されている。このマトリクススイッ
チ手段は図示するようなマトリクス構成のハードウエア
を備えていてもよく、またアクセス要求を伝達できる図
示するマトリクス機能を有する論理回路により構成され
る仮想的なものでもよい。アクセス要求発生源の数とリ
ソースの数は必ずしも等しくなくともよい。

【０００４】アクセス要求発生源Ｒ(1) 〜Ｒ(8) は次々
にアクセス要求を発生する。アクセス要求は発生源側の
都合にしたがって発生するから、一つのリソースに対し
て同時に複数のアクセス要求が競合することがある。マ
トリクススイッチ手段によりその競合を調停して、一つ
のアクセス要求発生源を要求先の一つのリソースにその
アクセス要求を伝達する。このときリングアービタＲＡ
(1) 〜ＲＡ(8) が、それぞれ図５に矢印で示すようにア
クセス要求を掃引して、該当するアクセス要求に行き当
たるとその交点Ｃ(n,m) を介してそのアクセス要求を一
つだけリソース側に伝達しリソースはそのアクセス要求
を受け付ける。

【０００５】一つのアクセス要求が受け付けられると、
当該アクセス要求を送出していた要求源に対して要求が
受け付けられた旨の情報が送出される。また一つのアク
セス要求を受け付けることにより、そのリングアービタ
に送出されていた別のアクセス要求は待たされ、その別
のアクセス要求は次のタイミングで、あるいはその次の
タイミングで検出されることになる。アクセス要求が受
け付けられてからは、このマトリクススイッチ手段を介
して、あるいは別のバス信号線を介して必要なデータが
転送されるなど処理が実行される。

【０００６】図６はこのリングアービタの動作を説明す
る概念図である。各要求発生源Ｒ(1) 〜Ｒ(8) からそれ
ぞれ一つづつその要求先のリソースの番号がアクセス要
求として表示されている。調停制御はリソースＳ(1) 〜
Ｓ(8) 毎に実行される。いま図６でｍ番目のリソースＳ
(m) について調停制御が実行されている。各要求発生源
Ｒ(1) 〜Ｒ(8) からのアクセス要求を検索してその中に
当該リソースＳ(m) に対してアクセス要求を発している
ものがあるかを検索する。いまこの例では２番目の要求
発生源Ｒ(2) がｍ番目のリソースにアクセス要求を出し
ている。調停制御ではこれを発見するとこの要求発生源
Ｒ(2) を当該リソースＳ(m) に接続することになる。一
つが接続されると他の要求発生源Ｒ(1) 、Ｒ(3) 〜Ｒ
(8) については非接続となる。

【０００７】いまｍ番目のリソースＳ(m) に対してアク
セス要求を出している要求発生源Ｒ(1) 〜Ｒ(8) が一つ
であればただちにその要求を受け付けるが、それが複数
であればその間の競合について調停を実行して一つを選
択してその要求を受け付ける。この調停の論理はさまざ
まに設定することができる。ここではかりに要求発生源
Ｒ(1) 、Ｒ(2) 、・・・、Ｒ(n) のように循環して実行
されるものとする。この論理は、各要求発生源について
平等に行う、要求発生源に優先順位を付ける、その他任
意の論理を設定することができる。

【０００８】

【発明が解決しようとする課題】このようなアクセス要
求の調停制御では、競合する場合の調停を行うためのリ
ングアービタＲＡ(1) 〜ＲＡ(8) はそれぞれ、１回のタ
イムスロットで各要求発生源から出されているアクセス
要求を一つだけ受け付けることができる。各要求発生源
にかりに複数のアクセス要求が既に発生していて、これ
が図６左端に示すように待ち行列を作って待っていたと
しても、その先頭の斜線で示すアクセス要求だけが競合
調停の対象になるのであって、待ち行列二番目以降のア
クセス要求は少なくとも次のタイムスロットを待たなけ
ればならない。

【０００９】かりに、一つの要求発生源ではその待ち行
列の先頭のアクセス要求が二番目のリソースＳ(2) であ
り、待ち行列二番目のアクセス要求がリソースＳ(3) で
あったとすると、このタイムスロットでリソースＳ(2)
が他の要求発生源との間で競合状態であり受け付けられ
ず、リソースＳ(3) には他の要求発生源からのアクセス
要求がなかったとすると、リソースＳ(3) に対するアク
セス要求は受け付けられてもよかったはずである。つま
り、マトリクススイッチ手段のこの要求発生源とリソー
スＳ(3) との交点はこのタイムスロットで使用されなか
ったことになる。これは、マトリクススイッチ手段にま
だ余裕があるにもかかわらず調停制御の都合で使用され
ず、実質的にアクセス要求のスループットが抑制されて
いることを意味する。

【００１０】本発明はこれを改良するもので、アクセス
要求のスループットを向上するアクセス調停方式を提供
することを目的とする。

【００１１】

【課題を解決するための手段】本発明は、アクセス要求
を発生するＮ個（Ｎは２以上の整数）の要求発生源と、
このアクセス要求源に共有されたＭ個（Ｍは２以上の整
数）のリソースと、前記Ｎ個の要求発生源が入力端子に
接続され、前記Ｍ個のリソースが出力端子に接続された
Ｎ×Ｍの容量を有するマトリクススイッチ手段と、この
マトリクススイッチ手段の交点の接断を制御する制御回
路とを備えた装置に実施される。この制御回路は、前記
Ｎ個の要求発生源から発生するアクセス要求について、
タイムスロット毎に１回の調停制御を行い、その調停制
御の結果にしたがってそのタイムスロット毎に前記マト
リクススイッチ手段の多数（厳密には１以上）の交点の
接断を同時に制御する構成である。

【００１２】前記アクセス要求源は、それぞれ広い意味
でリソースであり、装置構成によっては前記Ｍ個のリソ
ースの一つであることもできる。前記マトリクススイッ
チ手段は、ハードウエアで構成されたスイッチがマトリ
クスの交点に配列されたマトリクススイッチでもよく、
また、実質的にアクセス要求を前記交点で接続または遮
断する回路をプログラム制御回路により実現する仮想的
なマトリクススイッチでもよい。

【００１３】ここで本発明の特徴とするところは、各要
求発生源に対応して発生するアクセス要求の要求先のリ
ソース番号をそれぞれ待ち行列として保持するレジスタ
を備えたところにある。そして、前記制御回路は、前記
リソース対応に前記待ちレジスタのそれぞれ設定された
深さまで当該リソースの番号があるかを検索する手段
と、この検索する手段により当該リソースの番号がある
ことが識別された要求発生源についてそのリソース番号
毎に調停制御を行うことを特徴とする。

【００１４】この待ちレジスタの各段に対応して優先順
位を保持する優先順位レジスタを設け、前記検索する手
段により当該リソースの番号が複数あることが識別され
たときに、対応する優先順位レジスタに保持された優先
順位にしたがって調停制御を行うように構成することが
できる。

【００１５】

【作用】本発明の方式では、マトリクススイッチ手段を
制御する制御回路は、時間の経過にしたがってタイムス
ロット毎に、複数の要求発生源からのアクセス要求につ
いて競合する場合に調停制御を実行して、その調停制御
に結果に基づいて１つのタイムスロットに１回だけマト
リクススイッチ手段の交点を接続状態にしてアクセス要
求を受け付ける。つまり、１回のタイムスロット期間内
では、はじめに調停制御を実行し、その後に一つの交点
について１回だけ接続状態を作る。したがって、一つの
要求発生源は１回のタイムスロットに１回だけアクセス
要求ができる。一つのリソースも１回のタイムスロット
に１回だけアクセス要求を受け付けることができる。

【００１６】本発明の方式では、各要求発生源に対応し
て設けられたレジスタに、その要求発生源から発生する
アクセス要求の要求先のリソース番号をそれぞれ待ち行
列として保持する。そして、この待ち行列の先頭から順
にあらかじめ設定された深さまで、当該リソース番号に
対してアクセス要求があるかの検索を実行する。したが
って、従来例方式で各要求発生源毎に１つだけアクセス
要求を表示できたものに比べると、待ちレジスタに保持
された複数のアクセス要求について１回のタイムスロッ
ト内に検索を実行できるから、アクセス要求が受け付け
られる可能性が高くなりスループットが向上する。

【００１７】前記調停制御は、一つのマトリクススイッ
チ手段に接続されたｎ個のリソースＳ(1) 〜Ｓ(n) につ
いて、順次実行することもできるし、時間的に並行して
実行することもできる。

【００１８】

【実施例】本発明第一実施例の構成を図１および図２を
参照して説明する。図１は本発明第一実施例の構成図で
ある。図２は本発明第一実施例の要求発生源のブロック
図である。

【００１９】本発明は、アクセス要求を発生する８個の
要求発生源Ｒ(1) 〜Ｒ(8) と、このアクセスの要求発生
源Ｒ(1) 〜Ｒ(8) に共有された８個のリソースＳ(1) 〜
Ｓ(8) と、８個の要求発生源Ｒ(1) 〜Ｒ(8) が入力端子
１₁〜１₈に接続され、８個のリソースＳ(1) 〜Ｓ(8)
が出力端子２₁〜２₈に接続された８×８の容量を有す
るマトリクススイッチ３と、８個の要求発生源Ｒ(1) 〜
Ｒ(8) から発生するアクセス要求について、タイムスロ
ット毎に１回の調停制御を行い、その調停制御の結果に
したがってそのタイムスロット毎にマトリクススイッチ
３の１以上の交点の接断を制御するマトリクススイッチ
接断部１１を含む制御回路４とを備えたアクセス調停方
式である。

【００２０】ここで、本発明の特徴とするところは、要
求発生源Ｒ(1) 〜Ｒ(8) 毎に発生するアクセス要求の要
求先のリソース番号をそれぞれ待ち行列として保持する
待ちレジスタであるシフトレジスタ６を備え、制御回路
４は、リソースＳ(1) 〜Ｓ(8) 対応にシフトレジスタ６
のそれぞれ設定された深さまで当該リソースＳ(1) 〜Ｓ
(8) の番号があるかを検索する手段と、この検索する手
段により当該リソースＳ(1) 〜Ｓ(8) の番号があること
が識別された要求発生源Ｒ(1) 〜Ｒ(8) についてそのリ
ソース番号毎に調停制御を行う手段とを含む調停部１０
を備えたところにある。

【００２１】次に、本発明第一実施例の動作を説明す
る。図２において、ＳＲ(1) 〜ＳＲ(D) は、シフトレジ
スタ６の構成要素を表す。アクセス要求発生部７では、
アクセス要求するリソースＳ(1) 〜Ｓ(8) の位置番号を
出力し、これをシフトレジスタ６に転送する。ここで、
この位置番号はＳＲ(1) 、…、ＳＲ(D) の順にシフトレ
ジスタ６に蓄えられる。

【００２２】制御回路４の調停部１０が行うリソースＳ
(m) に対する要求発生源Ｒ(n) のアクセス要求の検索順
序は、ＳＲ(1) 、…、ＳＲ(8) の順である。このＳＲ
(1) からＳＲ(d) までを検索範囲とし、ｄを検索個数す
なわち検索深さと呼ぶ。

【００２３】図２では、要求発生源Ｒ(n−1)の検索深さ
はｄ′、要求発生源Ｒ(n) の検索深さはｄ、要求発生源
Ｒ(n＋1)の検索深さはｄ″である。

【００２４】まず、要求発生源Ｒ(n−1)のＳＲ (1)（●
印）から検索を開始し、ＳＲ(d′)までこの順に検索す
る。要求発生源Ｒ(n−1)内のシフトレジスタ６にリソー
スＳ(m) へのアクセス要求がない場合は、次の要求発生
源Ｒ(n) にアクセス権を譲渡する。

【００２５】つづいて、要求発生源Ｒ(n) では、ＳＲ
(1) から検索を開始し、ＳＲ(d) までこの順に検索す
る。ここでは、ＳＲ(4) にリソースＳ(m) へのアクセス
要求が存在し、制御回路４の調停部１０にＳＲ(4) から
出力許可フラグＦが出力される。要求発生源Ｒ(n) では
ＳＲ(4) のデータを削除し、ＳＲ(5) 以降のデータをつ
める。

【００２６】ＳＲ(4) からの出力許可フラグＦを受け取
った制御回路４の調停部１０は、マトリクススイッチ接
断部１１を制御してＳＲ(4) に関するアクセスを実行す
る。

【００２７】つづいて、要求発生源Ｒ(n＋1)のＳＲ (1)
（○印）から検索を開始する。今回のアクセス許可は、
要求発生源Ｒ(n＋1)のＳＲ(3) に与えられる。

【００２８】次に、図３を参照して本発明第二実施例を
説明する。図３は本発明第二実施例の構成図である。本
発明第二実施例の特徴は、本発明第一実施例においてＳ
Ｒ(d) に蓄えられたリソースＳ(1) 〜Ｓ(8) の位置番号
に優先順位番号ＮＯを付与するところにある。

【００２９】シフトレジスタ６に並行して第二のシフト
レジスタ９を設け、アクセス要求発生部７からシフトレ
ジスタ６に転送されるアクセス要求に同期し、外部から
優先順位番号ＮＯを第二のシフトレジスタ９に転送す
る。

【００３０】ＮＣ(1) 〜ＮＣ(D) は第二のシフトレジス
タ９の構成要素であり、シフトレジスタ６の構成要素で
あるＳＲ(1) 〜ＳＲ(D) に一対一で対応している。すな
わち、ＮＣ(d) の値ｋ(k=1、…、d 、) は、この順でリ
ソースＳ(m) に対する要求発生源Ｒ(n) 内でのアクセス
要求の検索順序である。ＮＣ(d) ＝１、…、ｋに対応す
るＳＲ(d) を検索する範囲、ｋを検索個数、すなわち検
索深さと呼ぶ。要求発生源Ｒ(n−1)の検索深さはｋ′、
要求発生源Ｒ(n) の検索深さはｋ、要求発生源Ｒ(n＋1)
の検索深さはｋ″である。

【００３１】まず、要求発生源Ｒ(n−1)では、優先順位
番号ＮＯが「１」であるＮＣ(2) に対応するＳＲ(2) か
ら検索を開始し、優先順位番号ＮＯが「ｋ′」であるＮ
Ｃ(d′) に対応するＳＲ(d′) まで優先順位番号ＮＯの
小さい順に検索する。すなわち、要求発生源Ｒ(n−1)に
おいては、ＳＲ (2)（●印）、ＳＲ(1) 、ＳＲ(4) 、Ｓ
Ｒ(5) 、…、ＳＲ(d′) の順に検索する。要求発生源Ｒ
(n−1)内のシフトレジスタ６にリソースＳ(m) へのアク
セス要求がない場合は、次の要求発生源Ｒ(n)にアクセ
ス権を譲渡する。

【００３２】つづいて、要求発生源Ｒ(n) において、優
先順位番号ＮＯが「１」であるＳＲ(3) から検索を開始
し、ＮＣ(d) ＝ｋ以下であるＳＲ(d) までこの順に検索
する。優先順位ＮＯが「２」であるＳＲ(5) にリソース
Ｓ(m) に対するアクセス要求が存在し、ＳＲ(5) は制御
回路４に対して出力許可フラグＦを出力する。要求発生
源Ｒ(n) ではＳＲ(5) のデータを削除し、ＳＲ(6) 以降
のデータをつめる。さらに、優先順位番号ＮＯ「２」以
降のデータを持つＮＣ(d) からそれぞれ「１」を減じ、
優先順位番号ＮＯを繰り上げたうえでＮＣ(6) 以降のデ
ータをつめる。

【００３３】ＳＲ(5) からの出力許可フラグＦを受け取
った制御回路４の調停部１０は、マトリクススイッチ接
断部１１を制御してＳＲ(5) に関するアクセスを実行す
る。

【００３４】つづいて、要求発生源Ｒ(n＋1)において、
優先順位ＮＯが「１」であるＳＲ(5) から検索を開始
し、ＮＣ(d″) ＝ｋ″以下であるＳＲ(d″) までこの順
に検索する。優先順位ＮＯが「２」であるＳＲ(3) にリ
ソースＳ(m) に対するアクセス要求が存在し、ＳＲ(3)
は制御回路４に対して出力許可フラグＦ′を出力する。
要求発生源Ｒ(n＋1)ではＳＲ(3) のデータを削除し、Ｓ
Ｒ(4) 以降のデータをつめる。さらに、優先順位番号Ｎ
Ｏ「２」以降のデータを持つＮＣ(d″) からそれぞれ
「１」を減じ、優先順位番号ＮＯを繰り上げたうえでＮ
Ｃ(4) 以降のデータをつめる。

【００３５】ＳＲ(3) からの出力許可フラグＦ′を受け
取った制御回路４の調停部１０は、マトリクススイッチ
接断部１１を制御してＳＲ(3) に関するアクセスを実行
する。

【００３６】次に、図４を参照して本発明第三実施例を
説明する。図４は本発明第三実施例の要部構成図であ
る。本発明第三実施例の特徴は、本発明第一および第二
実施例における制御回路４に優先順位設定部ＰＲ(1) 〜
ＰＲ(8) を設けたところにある。この優先順位設定部Ｐ
Ｒ(1) 〜ＰＲ(8) は、要求発生源Ｒ(1) 〜Ｒ(8) にそれ
ぞれ設けられたシフトレジスタ６であるＳＲＴ(1) 〜Ｓ
ＲＴ(8) に蓄えられたアクセス要求量を監視し、その量
の多い要求発生源Ｒ(1) 〜Ｒ(8) から検索を開始する優
先順位を付加するものである。

【００３７】図４においては、要求発生源Ｒ(5) 、Ｒ
(8) 、Ｒ(2) 、Ｒ(6) 、Ｒ(3) 、Ｒ(7) 、Ｒ(1) 、Ｒ
(4) の順番で検索が行われる。それぞれの要求発生源Ｒ
(1) 〜Ｒ(8) での検索方法は本発明第一または第二実施
例と同様である。本発明第三実施例の利点は、アクセス
要求量の最も多い順に優先順位を設定するので、各要求
発生源Ｒ(1) 〜Ｒ(8) が保持しているアクセス要求量を
均等に保つことができるところにある。

【００３８】本発明第一ないし第三実施例において、要
求発生源Ｒ(1) 〜Ｒ(8) およびリソースＳ(1) 〜Ｓ(8)
の個数は８個で説明したが任意に構成することができ
る。また、要求発生源Ｒ(1) 〜Ｒ(8) およびリソースＳ
(1) 〜Ｓ(8) の個数は等しくなくてもよい。

【００３９】本発明第一および第二実施例では、要求発
生源Ｒ(n) のＳＲ(d) の一つに出力許可が与えられると
次の要求発生源Ｒ(n＋1)にアクセス権を譲渡したが、要
求発生源Ｒ(n) の出力許可が与えられたＳＲ(d) の次の
ＳＲ(d＋1)から再び検索を開始する構成とすることもで
きる。また、一度に複数のアクセスを許可する構成とす
ることもできる。

【００４０】本発明第三実施例では、優先順位の設定基
準をアクセス要求の蓄積量としたが外部から任意に付与
する構成とすることもできる。

【００４１】

【発明の効果】以上説明したように、本発明によればア
クセス要求検索の個数が複数なのでアクセス許可を与え
られる確率が大幅に向上される。したがって、アクセス
要求のスループットを向上することができる。

【図面の簡単な説明】

【図１】本発明第一実施例の構成図。

【図２】本発明第一実施例の要求発生源の構成図。

【図３】本発明第二実施例の構成図。

【図４】本発明第三実施例の要部構成図。

【図５】従来例の構成図。

【図６】リングアービタによる競合調停を示す図。

【符号の説明】

１₁〜１₈入力端子２₁〜２₈出力端子３マトリクススイッチ４制御回路６シフトレジスタ７アクセス要求発生部９第二のシフトレジスタ１０調停部１１マトリクススイッチ接断部ＮＯ優先順位番号ＰＲ(1) 〜ＰＲ(8) 優先順位設定部Ｒ(1) 〜Ｒ(8) 要求発生源ＲＡ(1) 〜ＲＡ(8) リングアービタＳ(1) 〜Ｓ(8) リソース

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁵ 識別記号庁内整理番号ＦＩ技術表示箇所Ｈ０４Ｌ 12/44 12/48 Ｈ０４Ｑ 3/52 Ａ 9076−5Ｋ 8732−5ＫＨ０４Ｌ 11/20 Ｚ

Claims

【特許請求の範囲】

【請求項１】アクセス要求を発生するＮ個（Ｎは２以
上の整数）の要求発生源と、このアクセス要求源に共有されたＭ個（Ｍは２以上の整
数）のリソースと、前記Ｎ個の要求発生源が入力端子に接続され、前記Ｍ個
のリソースが出力端子に接続されたＮ×Ｍの容量を有す
るマトリクススイッチ手段と、前記Ｎ個の要求発生源から発生するアクセス要求につい
て、タイムスロット毎に１回の調停制御を行い、その調
停制御の結果にしたがってそのタイムスロット毎に前記
マトリクススイッチ手段の１以上の交点の接断を制御す
る制御回路とを備えたアクセス調停方式において、前記要求発生源毎に発生するアクセス要求の要求先のリ
ソース番号をそれぞれ待ち行列として保持する待ちレジ
スタを備え、前記制御回路は、前記リソース対応に前記待ちレジスタ
のそれぞれ設定された深さまで当該リソースの番号があ
るかを検索する手段と、この検索する手段により当該リ
ソースの番号があることが識別された要求発生源につい
てそのリソース番号毎に調停制御を行う手段とを含むこ
とを特徴とするアクセス調停方式。
【請求項２】前記待ちレジスタの各段に対応して優先
順位を保持する優先順位レジスタが設けられ、前記制御回路には、前記検索する手段により当該リソー
スの番号が複数あることが識別されたときに、対応する
優先順位レジスタに保持された優先順位にしたがって調
停制御を行う手段を備えた請求項１記載のアクセス調停
方式。