非サイクル有向グラフで接続された構成要素間の通信方法
【課題】 システムバスに沿ったノードの任意アセンブリが非サイクル有向グラフに変更されているシステムにおいて、各ノード間の通信を確立する。
【解決手段】 構成バスアクセスアービトレーション方式、優先バスアクセスアービトレーション方式、トークンパッシングバスアービトレーション方式及びプレエンプティブバス初期設定メカニズム等を実施する。
【解決手段】 構成バスアクセスアービトレーション方式、優先バスアクセスアービトレーション方式、トークンパッシングバスアービトレーション方式及びプレエンプティブバス初期設定メカニズム等を実施する。
【発明の詳細な説明】
【技術分野】
【0001】
関連出願
本出願は、本出願の譲受人にそれぞれ譲渡されており且つ本出願と同時に出願された名称「Method and Apparatus for Unique Address Assignment,Node Self−Identification and Topology Mapping for a Directed Acyclic Graph」による出願Serial No.07/994,402及び名称「Method and Apparatus for Transforming an Arbitrary Acyclic Topology Collection of Nodes into an Acyclic Directed Graph」による出願Serial No.07/994,117に関連している。
発明の分野
本発明はコンピュータシステムに関する。さらに特定すれば、本発明は、コンピュータシステムの複数の任意に組立てられた要素の間に通信方式を確立し且つそれを利用する方法及び装置に関する。
【背景技術】
【0002】
背 景
所定のコンピュータシステムの内部の構成要素は、それらの要素自体の間で信号を搬送する能力を必要とする。非常に単純なシステムでは、システムの各要素をシステムのその他の全ての部品に直接ワイヤリングさせることが可能である。しかし、現実には、コンピュータを拡張自在にし、且つ未知の数のシステム部品に対応するために、コンピュータ設計者はずっと以前に通信バスの概念を開発した。
【0003】
バスは、コンピュータシステム全体を通って走る1本又は複数本のワイヤなどの通信経路である。システムの各構成要素は、システム中のその他の構成要素の各々に理論上接続されるべきバスにプラグインされるだけで良い。構成要素間には単一の通信チャネルしか存在しえないので、各構成要素が他の構成要素と同時に通信できないことは言うまでもない。通信バスを利用する場合、1つの構成要素からの重要な情報部分をバスアクセスを待機しながらの係属状態に放置することのない効率良い方式で他の構成要素と通信するために各構成要素がバスを使用できるように、何らかの形態で共用構造を確定することが必要である。バス上の構成要素がバスを共用するための方法を一般にバスアービトレーション方式という。
【0004】
重要な情報の流れを最大にするようにバスアービトレーション方式を最適化するという重大な要求に加えて、柔軟性をできる限り残しつつシステム遅延を最小にするために、バス自体の物理的(及び論理的/電気的)構成を最適化でき、また、そのようにすべきである。
【0005】
バスに付随する他の構成要素と通信するためには、各構成要素はそのバスに関して実現された通信規約と一致する送受信回路などのハードウェアを具備しなければならない。そのような通信規格の1つは、この文書に付録Aとして添付されている表題「High Performance Serial Bus」のIEEE規格文書P1394の中に記載されている。P1394に記載されている規格は同じバックプレーン上のカード、他のバックプレーン上のカード及び外部周辺機器の間で低コストで相互接続を実行しようとするものである。
【0006】
従来の技術のバス又はネットワークは、どれをどこにプラグ接続すべきかを知ることを要求していた。たとえば、多くのコンピュータの背面には、特定の周辺機器に対応する指定ポートがある。コンピュータの中には、マウス及びキーボードなどの構成要素に対してADBと呼ばれるバスを使用し、他の周辺機器に対してはSCSIバスを使用するMacintoshのようにいくつかのバスを実現するものもある。これらの型のバスはディジーチェーン要素を一体に構成するが、その接続のトポロジーは限られている。他に知られているバス/ネットワークは、ネットワークのノードをリングとして、すなわち、動作するためには閉成されなければならないループに配列することを要求する。最後に、星状配列、すなわち、ハブ・スポーク配列は各ノードを中央マスタに直接リンクすることを必要としていた。従来の技術のシステムの各々には、望ましい程度の柔軟性が欠けている。
【発明の開示】
【発明が解決しようとする課題】
【0007】
コンピュータの要素を1つのバスに任意に取り付けることが可能であり、それに際して、任意トポロジーをシステムにより構成要素の所定の配列を要求することなく機能システムに変更できることが望ましいであろうし、従って、それが本発明の目的である。
発明の概要
本発明の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して公正バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して優先バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関してトークンパッシングバスアービトレーションの方法を提供することである。
本発明のさらに別の目的は、非サイクル有向グラフに変更されているノードのネットワークにおいて誤りが検出されたとき又は動作中にノードが増減されたときにネットワーク中のどのノードによってもプレエンプティブバス初期設定をトリガしうるメカニズムを提供することである。
【課題を解決するための手段】
【0008】
本発明のこれらの目的及びその他の目的は、システムバスに沿ったノードの任意アセンブリが非サイクル有向グラフに変更されているシステムで実現される。ノードの階層配列は1つのノードをルートと指定する一方で、他の全てのノードはそれらのノードがリンクしているノードとの間に親子関係を成立させている。各ノードは所定の肯定応答優先順位方式を成立させた複数の接続された子ポートを有しても良い。公正バスアクセスアービトレーションは、所定のポート優先順位に相応するシーケンスでバス許可を実行して、全ノードをバスでターンさせる。ルートノードは、等時性データ転送を要求するルートノードに対応するのに有用であるバスアクセスを獲得するために、常にその優先アクセス状態をアサートしても良い。あるいは、トークンパッシングアービトレーション方式を実現しても良く、その場合、バスアクセスに関わるトークンは先に説明した所定のポート優先順位方式に従ってノードを巡って渡されて行く。プレエンプティブバス初期設定は、必然的な誤りの検出時、あるいは既存のノードに対する接続の追加又は除去の時点でいずれかのノードによってトリガされれば良い。
【発明を実施するための最良の形態】
【0009】
発明の詳細な説明
任意のトポロジーを有するバスを利用する方法及び装置を説明する。以下の説明中、本発明を完全に理解させるために様々なコンピュータ素子などの数多くの特定の詳細な事項を述べる。しかしながら、そのような特定の詳細な事項がなくとも本発明を実施しうることは当業者には自明であろう。別の場合には、本発明を無用にわかりにくくしないために周知の制御構造やコード化技法を詳細には説明しなかった。
【0010】
この詳細な説明を通して、説明に比喩による明確性を与えるために数多くの描写用語を導入している。たとえば、所定のトポロジーの中におけるノード間の親子関係という表現がしばしば見られる。この目的は、最終的に導出されるグラフに至る「方向」の概念を表わすことである。以下に説明するように、任意のトポロジーが非サイクル有向グラフに変化されたならば、1つのノードは「ルート」ノードとして識別されることになる。ルートノードは親ノードをもたず、ルートノードに論理の上ですぐ隣接している全てのノードはそのルートの子ノードである。「ツリー」の比喩は「ブランチ(枝)」及び「リーフ(葉)」と呼ばれるノードを取り入れることによって完成する。
【0011】
ここで説明するバスアーキテクチャは単一のコンピュータに関わる素子に関連して説明されるのであるが、一般に、より広い範囲を有する。本発明は、バストポロジーを定義するに際して、装置のネットワークにおけるように一体にリンクされたノードの任意に組立てられたどのような集合体にも適用可能である。注意しなければならない1点は、ノードと物理的コンピュータ素子とを区別する必要があるということである。バスに常駐すべき各素子に関連して、少なくとも1つのノード物理層制御装置がある。状況によっては、所定の1つの素子を複数のノードと関連させると有利であろうが、通常の場合には、バスにある装置又は素子と、ノードとの間には1対1の対応がある。
【0012】
そこで図1を参照すると、ノード10のブロック線図が示されている。ノードを物理的にいかに実現するかは多少は任意である。本発明の好ましい実施例の実現形態では、ノードは付録Aとして添付したIEEE P1394 High Performance Serial Bus通信規約に準拠するように設計されている。ノード10はアービトレーション状態機械論理11を含む。このアービトレーション状態論理機械論理は、ここで説明すべき技法及びアルゴリズムを実行するためのあらゆる論理回路を取り入れている。この回路はプログラマブルロジックアレイ(PLA)から構成されていても良く、あるいはここで説明する機能を実行するように独自に設計されていても良い。ノード論理により実行されるべき機能を説明したならば、当業者はむやみに説明を加えなくとも本発明を実現することができるであろう。ノードは、その論理によって、バス初期設定、ツリー識別、自己識別及びバスアービトレーションの機能を含む最小限のアービトレーションプロトコルを実現するが、それら全ての機能については以下にさらに詳細に説明する。
【実施例】
【0013】
図1に示すノード10は送信側マルチプレクサ12及び13と、データ送信器、受信器及び再同期装置14とをさらに含む。図1に示すノードは局所ホスト15に結合している。局所ホスト15は、システム中の他の構成要素と通信することが必要であるディスクドライブ、CPU、キーボード又は他の何らかの構成要素などの、バスに付属させたい何らかの装置であれば良い。ノード10は通信リンクを介して他のノードと通信する。リンクは2つのポートの間の接続であって、直接的、実用的な用語でいえばケーブルセグメントであるが、通常は何らかの物理通信チャネルとして実現されれば良い。リンクは、最低でも、それが接続する2つのポートの間に半二重通信チャネルを構成することが可能であるべきであろう。ポートはノードとリンクとの間のインタフェースである。本発明に従えば、ポートはデータ及びアービトレーション信号を送受信する能力を有していなければならない。ポートは、それがリンクを介して別のポートに接続しているか否かを判定することもできなければならない。これを容易にする1つの方法は、接続しているポートによってリンクを介して、リンクの他端にあるポートにより検出可能であるバイアス電圧を印加させるというものである。すなわち、1つのポートに、他端でポートに接続していないリンク、裸リンクが付属している場合には、そのポートは接続ポートではないと判定するのである。図1では、図示されているノード10は接続リンク17,18及び19をそれぞれ有する3つの外部ポート21,22及び23を有する。
【0014】
本発明を実現するためのノードに関わる実現規則のいくつかは、1つのノードが1つ又は複数のポートを有していて良いということである。ノードはそのポートのいずれか1つでデータを送受信可能であるべきであろう。ノードは一度にイネーブルされているポートのうち唯一つのポートでデータを受信可能であり且つ残る全てのイネーブルされたポートではこのデータを送信可能であるべきであろう。ノードはそのポートの全てを介して信号メッセージを同時に且つ独立して送受信可能であるべきであろう。ノードのポートごとに別個の信号トランシーバ、エンコーダ及びデコーダが要求される。最低限の実現ノードは局所ホスト装置を必要としない。たとえば、そのようなノードはケーブル延長として機能しても良い。これ以降、装置及び局所ホストを無視し、バストポロジーを言うときには、常に、ノードや様々なポートを介するバス接続に関連させて説明する。
【0015】
グラフ変換
図2(a)及び図2(b)は、任意に組立てられたノードの集合体を示す。これ以降、ノードを単に円として示すが、ノードは、それぞれ、図1に関して説明した素子と等価の素子を含むものと思われる。ただし、各ノードはその図に示した3つより多い数又は少ない数の外部ポートを有していても良いということに注意する。それぞれのノードを結合する図示されている線は、リンクを示すための方法である。ポートは図示されていないが、暗黙のうちに、リンクとノードを接続するインタフェースである。
【0016】
ここで説明するバスアービトレーション技法は、任意のトポロジーを非サイクル有向グラフへと変更することを要求する。任意トポロジーグラフにおいては、ノードとリンクの集合体は1つのサイクルを形成しても良い。グラフ中の特定のノードから始まって、リンクを2度通ることをせずにリンクとノードを通過することによって同じノードに戻れる場合に、サイクルは成立する。図2(a)は、図示されているノードはいずれもループの中に接続していないことから、非サイクルグラフを示している。ところが、図2(b)は、境界規定ボックス25の中の領域が複数のサイクルを形成するノード40〜47の集合体を含んでいるために非サイクルグラフではない。説明すべきバスアービトレーション技法はサイクルが存在しないことを要求するので、ここではサイクルを変更するためのユーザ介入の方法についてもさらに説明する。
【0017】
グラフを非サイクルしないという必要条件に加えて、グラフは有向グラフでなければならない。有向グラフは、隣接ノードの間に階層構造が成立しているようなグラフである。当初は、ノード間に親子関係は成立していない。すなわち、たとえば、ノード31はノード34に対して「親ノード」であっても良く、あるいはノード34に対して「子ノード」であっても良い。従って、所定の任意トポロジーグラフを取り上げて、それを非サイクル有向グラフに変換することが必要である。ここで説明する方法は、ノードの数、あるいはノードが物理的にどのようにリンクしているかということとは無関係に且つリンクに沿った信号伝搬時間には関係なく、どのような所定の任意トポロジーに対してもこの変換を実行するように働く。
【0018】
ノード通信
まず、非サイクル任意トポロジーグラフを有向グラフに変換するプロセスを説明する。次に、サイクル変更が要求されるケースを説明する。図3(a)は、ノードとリンクが状態ラベルを有し且つ通信される信号はグラフを有向にするためのグラフ変換プロセスを表して指示されているような図2(a)の任意グラフを示す。この時点で、ノード間の信号通信を説明しておくと有益である。図3(b)は、リンク52によって結合された2つのノード50及び51(以下、それぞれノードAと、ノードB)を示す。説明した通り、リンクは図1に関連して先に説明したように各々のノードのトランシーバポートを結合する通信チャネルである。グラフ変換プロセスの間、ノードは隣接するノードとの間に親子関係を成立させることが必要になる。第1のノードのポートと第2のノードのポートとの間に少なくとも1つのリンクが接続していれば、それら2つのノードは隣接ノードであるという。図3(b)〜図3(d)では、変更されるべき関係はノードBがノードAの親であるということであり且つノードはその関係を成立させることが適切であると仮定する。
【0019】
方向を設定するのに先立って、ノードAがノードBをその親として成立させることが適切になったとき、ノードAはリンク52が結合しているポートから信号「You Are My Parent」(YAMP)を送信する。このメッセージは、ノードAがYAMP信号を発生していることをわかり且つノードBは受信したメッセージがYAMPであることを理解できるのであれば、どのような形態をとっていても良い。YAMP信号53がノードBにより受信されると、ノードBは「You Are My Child」(YAMC)をリンク52を介してノードAへ送信することによってノードAに応答する。ノードAのアービトレーション状態機械論理11はYAMP信号53の送信と、YAMC信号54の受信との間の時間遅延を追跡し続ける。測定される時間は、ノードAとノードBとの間の伝搬遅延の2倍を指定する。YAMC信号を受信すると、ノードAは「You Are My Child Acknowledged」(YAMCA)信号55をもって応答する。これは、ノード間の伝搬時間遅延がYAMCの送信と、YAMCAの受信との間の時間遅延と等しいことをも確定する能力をノードBに与える。半二重通信リンクの場合、YAMCAメッセージは通信チャネルを適正に方向付けする効果をも有する。
【0020】
全二重通信リンクの場合には、3つの論理メッセージYAMP、YAMC及びYAMCAを代わりに2回の信号送信のみによって中継することができる。図3(c)にはこの状況が示されており、ノードAは戻りYAMC信号57を受信するまでYAMP信号56を加え続ける。YAMCA信号は、論理上は、YAMP信号が到着しなくなったと検出されたときにノードBへ送信される。
説明したこの三重非同期メッセージ交換の使用により、メッセージ交換に関わる双方のノードがリンクを介する伝搬時間遅延を確定できるようなメカニズムが構成される。この遅延値は以下にさらに説明する競合事象を変更するとき、並びにバス性能を最適化するための正規のバスアービトレーションの間に使用される。このパラメータの動的抽出は必須である。その代わりに、最適のバス性能は得られなくとも最大伝搬時間遅延を演繹的に規定することができる。
【0021】
ノードA及びBがノードBはノードAの親であることを意味するメッセージを交換した後には、リンクは有向になったと言うことができる。ノードAはその論理によって、リンク52が結合しているポートを親ポート(親ノードに話し掛ける)とラベル付けし、また、ノードBはリンク52が結合しているポートを子ポート(子ノードに話し掛ける)とラベル付けする。以下に説明する方法は所定の時点でノード及びポートに割当てられるラベルによって説明されるため、ポートが得るラベルを維持することは大切である。図3(d)には速記図式表記が示されており、図中の方向矢印58はノードBがノードAの親として設定されており且つリンクは有向であることを指示している。
【0022】
方向確定
ここで図3(a)に戻ると共に、図6(a)〜図6(e)のプロセスを参照して、任意トポロジー全体を方向づけするプロセスを説明する。トポロジー変換プロセスの説明を助けるためには、若干多彩な定義を導入することが必要である。第1に、「リーフ」ノードは1つのポートしか接続していないノードとして定義される。パワーアップ後又は他のバス初期設定後に初期設定されると、直ちにノードはその状態をリーフノードとして認識する。「ブランチ」ノードは少なくとも2つの接続するポートを有するノードである。1つを除く全ての接続ポートを介して、ブランチノードはYAMP信号を受信しており且つそれに応答している。残るポートを介して、ブランチノードはYAMP信号を送信しており、それにより、ノードが親ノードであることを確定する。ノードは、1つの親を有しており(ノードは親ノードを1つしかもつことができない)且つ他の全てのポートは子ノードに接続していることを確定するまで、ブランチ状態には到達しない。ブランチ状態に達するのに先立って、ノードがブランチであると確定されるまでノードが方向の設定を不可能にするサイクルの一部である可能性は存在しているので、ノードは「サイクル」ノードと考えられる。
【0023】
グラフ変換手続きは、ステップ60で、バス初期設定(パワーアップ又は誘導)のときに始まり、この時点で任意トポロジーの中のリーフノードはステップ61で認識し、決定ボックス66でそれらのノードが接続するポートを唯一つしかもたないことを判定することによって、ステップ68でそれら自身をリーフノードとしてラベル付けする。図3(a)に示すグラフにおいては、ノード33,35,36及び37は、初期設定後、ステップ69で各々がYAMP信号を唯一の接続ポートを介して隣接するノードへ送信するリーフノードである。それらの信号を受信するノードは、次に、ステップ70でYAMC信号をリーフノードへ伝搬して戻すことにより、YAMCA通信が完了したときにはそれぞれの親子ペアの間の所定のリンクについて1つの方向が確定する。ステップ71では、各リーフノードは1つの接続ポートを親ポートとしてラベル付けし、親ノードにある各受信ポートは子ポートとしてラベル付けされる。
【0024】
当初はリーフノードでないグラフ上のノードは、初め、先に述べた理由によって「サイクルノード」と考えられ、サイクルノード手続き63に従って進行する。接続するポートのうち1つを除いて全てのポートを子ポートとしてラベル付けしているサイクルノードは、いずれも、後のステップ85で、残ったラベル付けされていないポートからYAMP信号を伝搬する。リンクについてその方向が設定されたとき、そこでサイクルノードはブランチノードとラベル付けされるようになる。すなわち、リーフノード37がそのノード34を親として確定した後は、ノード34は唯一つのラベルなしポートを有するので(ノード37に至るリンク接続を子ポートを介するものとしてラベル付けしている)、ノード34はYAMP信号をノード31へ同報通信し、その結果、ノード34はブランチノードになる。同様に、ノード31がノード33及び34はその子ノードであると識別したならば、ノード31はYAMP信号をノード30へ同報通信する。1つのノードが決定ボックス75でその全てのポートを介してYAMP信号を受信していたとき、そのノードはルートノードになる。図3(a)で、ノード30がノード31及び32からYAMP信号を受信した後、そのラベルはサイクルノードからルートノードであると変わる。図3(a)のグラフにおいては、必ずしもノード30がルートになる必要はないであろう。ツリー中のリンクのうちいくつかが長い伝搬遅延を生じさせるのであれば、ノード30は1つのポートでYAMP信号を受信しており、次に別のポートを介してYAMP信号を送信していたかもしれない。ノードのいずれもルート、さらにはリーフになって良く、リーフは適正に手続きをとる。図3(e)は、図3(a)に示す通信信号に応答して、その結果得られた有向グラフを示し、各ノードはラベル付けされており且つ方向は黒の矢印によって指示されている。
【0025】
ルート競合
状況によっては、ルート競合状態が起こりうる。これは、たとえば、任意トポロジーが図4に示す任意トポロジーに対し対称の配列を有するような場合に起こるであろう。図4に示す任意グラフでは、ノード160及び161はそれが結合している2つのリーフノードに対して親であることをそれぞれ確定している。次に、各ノードはYAMP信号をほぼ同時に他方へ伝搬している。ルート競合状態は決定ボックス86において関連する双方のノードにより認識される。各ノードはそれを親として指定する信号を受信しており、その一方で同じ信号を同じポートを介して送信している。競合しているノードの各々はステップ91でYAMC信号によって他方に応答し、それにより、各ノードはノード間の伝搬時間の2倍に等しい「決定時限」を確定できる。
【0026】
ルート競合状態は、各ノードの各々の任意状態機械論理装置11に組込まれているランダム決定メカニズムを利用することによって解決される。「決定時限」が経過するたびに、各ノードは、ステップ92で、再び他方へYAMP信号を送信すべきか否かを無作為に(50%の確率をもって)決定する。ほぼ確実に限られた数のサイクルの中で、一方のノードはその一方が往復することなく他方を親として指定することを決定する。親と指定されたほうはステップ95でルートになる。あるいは、ノードに所定の選択基準値を割当て、その大きいほう又は小さいほうの値が競合事象でどちらが優勢であるかを判定するようにしても良い。「決定時限」の動的確定は最適の性能を与えるものではあるが、本発明を実現する上で不可欠ではない。その代わりに、このアルゴリズムを使用するどのようなバスにおいても生じうる最悪の場合のリンク伝搬より長くありさえすれば、演繹的に定義された「決定時限」を使用しても良い。ルート競合を解決するために使用するのと同じ方法が、以下にさらに説明する他の競合事象を解決するためにも使用される。
【0027】
ルート割当て
先に説明した通り、グラフ変換プロセスの結果はグラフ中の唯一つのノードへのルート属性の割当てである。ルートノードは後述するバスアービトレーション方式における最終的な決定を有し、従って、特別の優先順位時間間隔を使用せずに最大の優先順位をもってバスをアクセスすることができる。多くの場合、所定のシステムを最適化するために、ノードが製造されるときに、もしくは動的に(ランタイム中に)所定のノードにルート特性を割当てることが可能であるのが望ましい。所定のバスは、等時性データ転送を要求するノードを含んでいるかもしれない。等時性データは、所定の時間に何らかの値をもつように伝送されなければならないデータである。たとえば、コンパクトディスクから発する音楽は、断片的に転送され、必ずしも順序通りではないデータファイルとは異なり、聴取すべき順序で、大きな遅れなく転送され且つ出力される必要がある。
【0028】
ルート指定に関してノードを3つのカテゴリに分類することができる。それらの指定は、製造中、装置への指定のハードワイヤリング、アービトレーション状態機械論理のプログラミング又は決定を実行するより高いレベルのソフトウェアの使用と、その後のその決定を維持したままの再ブートの開始によって適用されれば良い。ルートを指定されるのに関してノードが割当てられうる3つの指定は:ルートとなることを望まないノードと、ルートになりうる(なるべき)ノードと、ルートになるであろうノードである。ステップ81及び83では、それらの指定を試験する。第1のカテゴリに指定されるノードは、指示されたときに直ちにグラフ変換手続きを開始する。これは、通常、バス初期設定手続きの完了の直後である。第2のカテゴリのノードは、ステップ84でグラフ変換手続きを開始することを指示された後に、そのプロセスの開始を所定の長さの時間だけ遅延させる。この遅延によって、ノードはルートになる機会を増す。(YAMP信号はその遅延によりそのノードまでより伝搬しやすい。)遅延の追加にもかかわらず、「ルートになりうる」ノードがルートと指定されることで終わらない可能性は依然としてある。これは与えられたトポロジーと、メッセージ伝搬遅延とによって決まる。遅延の量は、設計中、相当に複雑なグラフを通るときの最悪の場合の妥当な伝搬遅延より多くなるように定義できる。
【0029】
ルート指定の可能性のうち第3のカテゴリに入るノードは、グラフを既に変換し終わり且つ全てのノードはそれ自体を識別した後にルートにならなければならないということを認識するのみであろう。アービトレーション状態機能論理がこの確定を実行しても良く、ホストシステムでランするソフトウェアであっても良い。これが起こると、ルートにならなければならないノードはバスに沿った他の全てのノードと、それが唯一のルートになろうとしていることを承諾し、以下でさらに説明する割込形バス初期設定信号を発信することによってグラフ変換プロセスを再開する。次に、ノードは、ステップ82で、ルートになるのを待ち、その全てのポートでYAMP信号を受信するまでグラフ変換に参加せず、それにより、そのノードは必然的にルートと指定されることになる。
ルートが確定されたならば、グラフは有向であるということができる。グラフ上の全ての隣接ノードの間に定義された関係が存在している。
【0030】
サイクル変更
先に説明したグラフを有向にする手続きは非サイクルグラフについてのみ働く。任意トポロジーの中にサイクルがあれば、ステップ80で始まる手続きによってサイクルを破断しなければならない。ステップ79で、所定の時間切れ周期が経過した後に、ノードが依然としてリーフ、ブランチ又はルートではなく、サイクルノードとラベル付けされているとき、サイクルの存在は検出される。「サイクル検出」タイミングはバス初期設定機能の終了の直後に始まる。時間切れ周期は最悪の場合のグラフ変換プロセスの持続時間(「ルートになりうる」ノード及び起こりうるルート競合事象に関しての遅延時間の追加)より長くなってはならない。
【0031】
あらゆるメッセージ交換は非同期事象であるので、「サイクル検出」時間切れ事象はグラフの全てのノードに対して同時に起こる必要はない。そのため、「サイクル検出」時間切れ事象にまだ到達していないノードがサイクル解決は進行中であることを指示するメッセージを受信することは可能である。そのようなノードはそのサイクル検出時間切れ間隔を終了し、適切なサイクル解決プロセスを開始する。
【0032】
本発明に従ったサイクル解決の方法は組立て後のノードの集合体のユーザが介入することを要求する。ノードが「サイクル検出」時間切れを受けると、システムのユーザは図6(e)のステップ100で、サイクルが存在しており且つノードが次に関連しない出力装置を介して通知されるであろう。そこで、ユーザは、どのようなサイクルでも存在することを排除するために、リンクを遮断することを命令される。次に、ユーザはグラフ変換手続きに制御を戻す。
ループの各々が破断されて、サイクルが全く残っていないのであれば、先の節で説明したようなグラフを変換する手続きを、グラフ全体が非サイクルであると共に有向になるまで進行させて良い。
【0033】
固有物理アドレスの割当て
元の任意トポロジーから非サイクル有向グラフを確定したならば、グラフの各ノードに固有の物理アドレスを割当てることが可能である。このプロセスは、全てのリーフノードがその単一の接続ポートを介してバス要求(BR)信号を送信することによりバスを要求することをもって始まる。その信号を受信した親ノードは、その子ポートの全てからBR信号を受信し終わるまで待機し、次にBR信号をその親に伝搬する。BR信号は、ルートがその子の全てからBR信号を受信し終わるまでグラフを通って伝搬する。ルートがその子ポートの全てを介してバス要求を受信したならば、ルートはバスを1つのポートを介して許可し且つその残る子ポートを介してバス拒否(BD)信号を伝搬するための決定を実行する。どのバス要求を許可すべきかを選択する方法は、先に、たとえば、ポートを左から右へと又はポート番号づけに基づいて選択する場合などについて説明したような演繹的決定であっても良い。バス許可(BG)信号はルートからそれが要求している子へ送信される。その要求中の子が、それ自体、その子のうち1つからバス要求を伝搬した親ノードである場合には、その子ノードはその子ポートの1つを除く全てのポートを介して先に説明したのと同じ所定の方式でバス拒否信号を送信する。最終的には1つのリーフノードがバス許可信号を受信し、そのノードはバス許可確認(BGA)信号によって応答し、BGA信号はルートノードへと伝搬されて戻る。BD信号とBGA信号の伝搬は半二重通信チャネルの場合に必要になるであろう通信リンクの方向を定める働きをする。そこで、拒否された全てのノードは最終的にBG信号を受信するノードによるアクティビティを待つ。
【0034】
最終的にバスに対するアクセスを許可されるノードはアドレス割当てパケットを送信する。ノードはこのパケットをバスを介して送信し、パケットは他の全てのノードにより受信されて、それらのノードは、それぞれ、受信するアドレスパケットの数をカウントする。送信されるアドレスパケットは何らかの任意の情報を有していても良い。ノードの固有物理アドレスは、ノードがアドレスパケットを送信する前にカウントしたアドレスパケットの数に基づいている。すなわち、前もってアドレス情報は割当てられていないにもかかわらず、2つのノードが同じ物理アドレスを獲得することはない。アドレスパケットの実際の組成は任意であって、システムにより効率良く利用可能な何らかのビットストリームであれば良い。物理アドレス割当てパケットを送信した後、ノードは「子ID完了」信号(CIC)信号を送信する。子ポートでこれを受信した親ノードは、次に、「子識別完了確認」(CICA)信号を送信し、ポートを識別済子ポートとしてラベル付けする。次のBR信号の伝搬に応答して、自身を識別したばかりであるノードの親は物理アドレスパケットを送信すべき次の子を選択する。1つの親ノードの子ノードの全てが自身を識別したならば、親ノードはバスを要求し、バスを許可したとき、その物理アドレス割当てパケットを伝搬する。この手続きは、所定の選択基準に従って、全てのノードがカウント動作によって固有物理アドレス割当てを確定するまで続く。図5は、左から右への事前定義済選択基準が実現されている図3(e)のグラフを示す。ノードは固有のアドレスを割当てられ、ノード33は第1のアドレスを受信し、前述のように、ルートノード30は第8の、そして最後のアドレスを受信する。
この手続きが完了すると、グラフ中の各ノードは固有物理アドレスを有することになり、そのアドレスは前もって確定されている必要はなく、システム管理又はその他の目的のために利用されれば良い。
【0035】
ノードの自己識別
ノード自己識別プロセスは本質的には先に説明した物理アドレス割当て手続きと同一のルーチンに従う。各ノードがその物理アドレス割当てパケットを送信するとき、そのパケットはノードに関連する局所ホストのID、それがどれほどの量の電力を必要とするか、さらに、たとえば、「ソフトパワーオン」属性を支援するか否か等々の別の情報を含んでいても良い。事実、ノード自己識別情報は、どの情報を送信するにしても、それは固有物理アドレスを獲得するためのカウントの基礎となることから、物理アドレス割当てパケットとして働くのである。
ノード自己識別パケットに関しては、ノードに関する特定の情報は告知しているノードの性質によって影響を受けるノードにより「聴取」されるだけで良い。先の場合と同様に、この手続きは全ノードがそのノード自己識別情報を送信し終わるまで進んで行く。
【0036】
トポロジーマッピング
トポロジーマッピングの方法は、物理アドレス割当て及びノード自己識別と同じラインに沿って流れる。すなわち、この手続きでは、各ノードがアドレス割当て又はノード自己識別のプロセスを経過しているとき、そのノードに、ノードが有している子ポートの数及びディスエーブルされたポートを有しているか否かなどの全てのポートに関する情報をさらに送信する。ディスエーブルされたポートに関しては、どこからディスエーブルされるかを識別できるように、ディスエーブルしようとしているポートの相互間に通信規約を実現することが望ましいであろう。従って、ポートがディスエーブルされたポートを識別するとき、ポートはそれ独自のIDを指示する識別子並びにディスエーブルされる元になったポートIDを与える。
【0037】
トポロジーマッピング手続きの間に受信する全てのポートに関わるあらゆるトポロジー情報を組立てることにより、ホスト又は何らかのソフトウェアレベルアプリケーションは解決したバストポロジーを論理的に再構成できるであろう。これは、リンクが予想外に故障した場合に、先にディスエーブルしたリンクがどのノードに対しても通信チャネルの損失を阻止するように働ける冗長性を実現することを含む数多くの目的のために有用である。
【0038】
公正バスアクセスアービトレーション
トポロジーマッピング、ノード自己識別又は物理アドレス割当てのルーチンが完了したならば、バスが起動し、ラン中であると考えることができる。本発明に従って実現される1つのアービトレーション方式は、正当なバスアクセスのアービトレーション方式である。バスに対するアクセスを望むとき、ノードはその親ポートを介して(それがルートでない限り)バス要求(BR)信号を送信する。親は、1つの子からBR信号を受信すると、他の全ての子ポートを介してバス拒否信号(BD)を送信する。そこで、親はBR信号をその親を通って、その信号がルートに到達するまで上方へと伝搬する。ルートはそれが受信する第1のBR信号に応答してバス許可信号(BG)を発行すると共に、その他の全ての子ポートを介してBD信号を送信し、BD信号は下方へと伝搬することにより、リンクの方向を定める。BG信号は要求している側のノードに到達するまでグラフを通って下方へと伝搬し、そのノードは、次に、バス確認(BA)信号を送信し、それに続くのはノードがバスへ送信することを必要とした情報のパケットである。パケットが完了したとき、全てのノードはアイドル状態に戻るか、又はアイドル状態に入る。
【0039】
ルートがバスに対するほぼ同時の要求を受信する場合、ノードのうち1つにバスアクセスを許可するために、ルートノードに関わる所定の選択基準を使用することができる。これは先に説明したのと同じ所定の優先順位選択基準であっても良い。
【0040】
公正バスアクセスアービトレーションの別の一面は、親ノードがその子に対して優先権をもつことである。すなわち、親ノードは、バスを要求するときに、BD信号をその子ポートの全てを介して送信し、次にBR信号をルートに向かって上方へと伝搬する。このメカニズムに伴って起こりうる1つの問題は、親がバスを介して送信すべき大量の情報を有している場合に、子ノードが適切なバスアクセスを獲得するのに障害を生じるかもしれないということである。従って、当該技術では広く使用され且つ良く知られているギャップシステムが導入されている。ノードはバスを利用した後に、再びバスを要求できるようになる前にギャップ周期1つ分待機しなければならない。これにより、バス上におけるノードのトポロジー配列にかかわらず、バスに沿ったどのノードにもバスを許可される均等な機会が与えられるのである。公正アービトレーションプロトコルを保証するためには、ギャップの長さはバスを通過するときの最悪の場合の信号伝搬遅延より大きくなければならない。ギャップ値をあらかじめ確定して、ノード論理にハードワイヤリングすることができるが、そのような方式は、結果として、最も極端なケースを除くあらゆる場合においてバスを最適に近い形で利用できる。トポロジーマッピング能力は、グラフ変換段階の間に実行される隣接ノード間の伝搬遅延の測定とあいまって、どの特定の実現形態に対してもバス性能を最適化する最適公正ギャップの計算を可能にする。
【0041】
優先バスアービトレーション
上述の公正バスアクセスアービトレーションに従って実現されるバスアービトレーション方式においては、ルートは常にバス優先権を有していることが望ましいであろう。これが実現されるとき、ルートノードはそれ自身にいつでもバスを許可して良い。これは、まず、BD信号をグラフ中の全てのノードを通して下方へと送信することによって実行される。ルートに関わる優先バスアクセスは、等時性データ転送を実行するためにルートノードが要求されるような場合に非常に有用である。
【0042】
トークンパッシングバスアービトレーション
先に説明した公正バスアクセスアービトレーション方式及び優先バスアクセスアービトレーション方式の代わりに、トークンパッシングバスアービトレーション方式を実現するに際して本発明を利用しても良い。比喩的にいえば、トークンパッシングバスアクセスは、バスがノード間を渡されているトークンを所有しているときにノードはバスを介して通信して良いという概念を表わす。各ノードがサイクル中の所定のポイントでバスを受けるように、トークンはノードからノードへとサイクル方式で渡されて行く。本発明においては、トークンパッシングは先に説明した物理アドレス割当てルーチンと同じ方式に従って実現される。実現される所定の選択メカニズムを使用して、トークンをノードからノードへと渡して行く順序を選択する。この順序は、固有アドレス割当ての順序を指示する図5に示すような順序に類似している。各ノードは、トークンを割当てられたとき、残るノードが聴取している間にバスに沿ってその情報パケットを伝搬する。次に、ノードは、先に説明したような所定の順序づけ方法に基づいてトークンを次の論理ノードに渡す。
【0043】
プレエンプティブバス初期設定
本発明に従って実現しうる重要な特徴は、プレエンプティブバス初期設定の概念である。各ノードに組込まれている状態機械論理は、いくつかの条件に対してノードからその全てのポートを介して伝搬されるべきバス初期設定(BI)信号をトリガすることができる。ノードがバス初期設定条件を信号で報知する必要があると確定したとき、ノードはBI信号をその全てのポートを介して、全ての隣接ノードがその信号を受信し、次に変更するように保証するのに十分な長さの時間だけ伝搬する。そこで、ノードはその後に先に説明した手続きの中でグラフ変換プロセスに至る開始手続きに入る。
【0044】
プレエンプティブバス初期設定をトリガすることを必要にするか又は望ましくするであろういくつかの状況がある。第1に、これは予期せぬ誤りに対するノード応答であっても良い。加えて、ホストレベルでは、異なるノードがルート属性、たとえば、等時性データ転送ノードを獲得すべきであることを確定しても良い。この割当てはバス初期設定ルーチンを通して維持されるので、所望のノードはルート指定を受信するまで変換手続きの間は待機することになる。プレエンプティブバス初期設定に至る別の条件はリンクの破断であろうが、その場合、付属するノードについて新たな非サイクル有向グラフを計算することが必要であろう。最後にプレエンプティブバス初期設定が起こるべき重要な状況は、周辺機器の「ホットアディション」と呼ばれるような、装置がネットワークに追加されるときである。新たな装置が接続されるポートは新たなノードの有無を検出し、システムのユーザに対しては透明であるが、たとえば、遮断と再給電の必要なく周辺機器の増減を可能にするバス初期設定をトリガする。追加されたノードの存在を含む新たな非サイクル有向グラフを計算する。いくつかのノードを取り除いたとき、バス初期設定をトリガする必要はなくなる、たとえば、リーフノードを取り除いたときには、ネットワークに害はないということはありうる。しかしながら、動作中のバスからブランチノードが指定される場合には、グラフを再構成する必要がありそうである。
【0045】
本発明を好ましい実施例によって説明したが、当業者により本発明の趣旨から逸脱せずに様々な変形や変更を実施しうることは理解されるであろう。従って、本発明は続く請求の範囲によって判断されるべきである。
【図面の簡単な説明】
【0046】
【図1】図1は、本発明に従って利用されるハードウェア層実現のブロック線図を示す。
【図2a】図2(a)は、ノードの任意の組立てられた集合体を示し、非サイクルのものを示す。
【図2b】図2(b)は、ノードの任意の組立てられた集合体を示し、サイクルを含むものを示す。
【図3a】図3(a)は、本発明に従ったグラフ変換プロセスを受ける図2(a)のノードの任意に組立てられた集合体である。
【図3b】図3(b)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3c】図3(c)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3d】図3(d)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3e】図3(e)は、図2(a)のノードの任意に組立てられたネットワークから得られる有向グラフを図式的に示す。
【図4】図4は、ルート競合を変更することを要求する対称グラフ配列を示す。
【図5】図5は、指示されうる固有アドレス割当て順序をもつ非サイクル有向グラフを示す。
【図6a】図6(a)は、本発明の好ましい実施例に従うプロセスの全体の流れを示す。
【図6b】図6(b)は、本発明の好ましい実施例に従うプロセスのリーフノード手続の流れを示す。
【図6c】図6(c)は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第1部分を示す。
【図6d】図6(d)は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第2部分を示す。
【図6e】図6(e)は、本発明の好ましい実施例に従うプロセスのルート競合処理の流れを示す。
【図6f】図6(f)は、本発明の好ましい実施例に従うプロセスのサイクル変更処理を示す。
【符号の説明】
【0047】
10 ノード
11 アービトレーション状態機械論理
14 データ送受信及び同期装置
【技術分野】
【0001】
関連出願
本出願は、本出願の譲受人にそれぞれ譲渡されており且つ本出願と同時に出願された名称「Method and Apparatus for Unique Address Assignment,Node Self−Identification and Topology Mapping for a Directed Acyclic Graph」による出願Serial No.07/994,402及び名称「Method and Apparatus for Transforming an Arbitrary Acyclic Topology Collection of Nodes into an Acyclic Directed Graph」による出願Serial No.07/994,117に関連している。
発明の分野
本発明はコンピュータシステムに関する。さらに特定すれば、本発明は、コンピュータシステムの複数の任意に組立てられた要素の間に通信方式を確立し且つそれを利用する方法及び装置に関する。
【背景技術】
【0002】
背 景
所定のコンピュータシステムの内部の構成要素は、それらの要素自体の間で信号を搬送する能力を必要とする。非常に単純なシステムでは、システムの各要素をシステムのその他の全ての部品に直接ワイヤリングさせることが可能である。しかし、現実には、コンピュータを拡張自在にし、且つ未知の数のシステム部品に対応するために、コンピュータ設計者はずっと以前に通信バスの概念を開発した。
【0003】
バスは、コンピュータシステム全体を通って走る1本又は複数本のワイヤなどの通信経路である。システムの各構成要素は、システム中のその他の構成要素の各々に理論上接続されるべきバスにプラグインされるだけで良い。構成要素間には単一の通信チャネルしか存在しえないので、各構成要素が他の構成要素と同時に通信できないことは言うまでもない。通信バスを利用する場合、1つの構成要素からの重要な情報部分をバスアクセスを待機しながらの係属状態に放置することのない効率良い方式で他の構成要素と通信するために各構成要素がバスを使用できるように、何らかの形態で共用構造を確定することが必要である。バス上の構成要素がバスを共用するための方法を一般にバスアービトレーション方式という。
【0004】
重要な情報の流れを最大にするようにバスアービトレーション方式を最適化するという重大な要求に加えて、柔軟性をできる限り残しつつシステム遅延を最小にするために、バス自体の物理的(及び論理的/電気的)構成を最適化でき、また、そのようにすべきである。
【0005】
バスに付随する他の構成要素と通信するためには、各構成要素はそのバスに関して実現された通信規約と一致する送受信回路などのハードウェアを具備しなければならない。そのような通信規格の1つは、この文書に付録Aとして添付されている表題「High Performance Serial Bus」のIEEE規格文書P1394の中に記載されている。P1394に記載されている規格は同じバックプレーン上のカード、他のバックプレーン上のカード及び外部周辺機器の間で低コストで相互接続を実行しようとするものである。
【0006】
従来の技術のバス又はネットワークは、どれをどこにプラグ接続すべきかを知ることを要求していた。たとえば、多くのコンピュータの背面には、特定の周辺機器に対応する指定ポートがある。コンピュータの中には、マウス及びキーボードなどの構成要素に対してADBと呼ばれるバスを使用し、他の周辺機器に対してはSCSIバスを使用するMacintoshのようにいくつかのバスを実現するものもある。これらの型のバスはディジーチェーン要素を一体に構成するが、その接続のトポロジーは限られている。他に知られているバス/ネットワークは、ネットワークのノードをリングとして、すなわち、動作するためには閉成されなければならないループに配列することを要求する。最後に、星状配列、すなわち、ハブ・スポーク配列は各ノードを中央マスタに直接リンクすることを必要としていた。従来の技術のシステムの各々には、望ましい程度の柔軟性が欠けている。
【発明の開示】
【発明が解決しようとする課題】
【0007】
コンピュータの要素を1つのバスに任意に取り付けることが可能であり、それに際して、任意トポロジーをシステムにより構成要素の所定の配列を要求することなく機能システムに変更できることが望ましいであろうし、従って、それが本発明の目的である。
発明の概要
本発明の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して公正バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関して優先バスアクセスアービトレーション方式を提供することである。
本発明の別の目的は、ノードの接続が非サイクル有向グラフに変更されているコンピュータシステムバス又はネットワークに関してトークンパッシングバスアービトレーションの方法を提供することである。
本発明のさらに別の目的は、非サイクル有向グラフに変更されているノードのネットワークにおいて誤りが検出されたとき又は動作中にノードが増減されたときにネットワーク中のどのノードによってもプレエンプティブバス初期設定をトリガしうるメカニズムを提供することである。
【課題を解決するための手段】
【0008】
本発明のこれらの目的及びその他の目的は、システムバスに沿ったノードの任意アセンブリが非サイクル有向グラフに変更されているシステムで実現される。ノードの階層配列は1つのノードをルートと指定する一方で、他の全てのノードはそれらのノードがリンクしているノードとの間に親子関係を成立させている。各ノードは所定の肯定応答優先順位方式を成立させた複数の接続された子ポートを有しても良い。公正バスアクセスアービトレーションは、所定のポート優先順位に相応するシーケンスでバス許可を実行して、全ノードをバスでターンさせる。ルートノードは、等時性データ転送を要求するルートノードに対応するのに有用であるバスアクセスを獲得するために、常にその優先アクセス状態をアサートしても良い。あるいは、トークンパッシングアービトレーション方式を実現しても良く、その場合、バスアクセスに関わるトークンは先に説明した所定のポート優先順位方式に従ってノードを巡って渡されて行く。プレエンプティブバス初期設定は、必然的な誤りの検出時、あるいは既存のノードに対する接続の追加又は除去の時点でいずれかのノードによってトリガされれば良い。
【発明を実施するための最良の形態】
【0009】
発明の詳細な説明
任意のトポロジーを有するバスを利用する方法及び装置を説明する。以下の説明中、本発明を完全に理解させるために様々なコンピュータ素子などの数多くの特定の詳細な事項を述べる。しかしながら、そのような特定の詳細な事項がなくとも本発明を実施しうることは当業者には自明であろう。別の場合には、本発明を無用にわかりにくくしないために周知の制御構造やコード化技法を詳細には説明しなかった。
【0010】
この詳細な説明を通して、説明に比喩による明確性を与えるために数多くの描写用語を導入している。たとえば、所定のトポロジーの中におけるノード間の親子関係という表現がしばしば見られる。この目的は、最終的に導出されるグラフに至る「方向」の概念を表わすことである。以下に説明するように、任意のトポロジーが非サイクル有向グラフに変化されたならば、1つのノードは「ルート」ノードとして識別されることになる。ルートノードは親ノードをもたず、ルートノードに論理の上ですぐ隣接している全てのノードはそのルートの子ノードである。「ツリー」の比喩は「ブランチ(枝)」及び「リーフ(葉)」と呼ばれるノードを取り入れることによって完成する。
【0011】
ここで説明するバスアーキテクチャは単一のコンピュータに関わる素子に関連して説明されるのであるが、一般に、より広い範囲を有する。本発明は、バストポロジーを定義するに際して、装置のネットワークにおけるように一体にリンクされたノードの任意に組立てられたどのような集合体にも適用可能である。注意しなければならない1点は、ノードと物理的コンピュータ素子とを区別する必要があるということである。バスに常駐すべき各素子に関連して、少なくとも1つのノード物理層制御装置がある。状況によっては、所定の1つの素子を複数のノードと関連させると有利であろうが、通常の場合には、バスにある装置又は素子と、ノードとの間には1対1の対応がある。
【0012】
そこで図1を参照すると、ノード10のブロック線図が示されている。ノードを物理的にいかに実現するかは多少は任意である。本発明の好ましい実施例の実現形態では、ノードは付録Aとして添付したIEEE P1394 High Performance Serial Bus通信規約に準拠するように設計されている。ノード10はアービトレーション状態機械論理11を含む。このアービトレーション状態論理機械論理は、ここで説明すべき技法及びアルゴリズムを実行するためのあらゆる論理回路を取り入れている。この回路はプログラマブルロジックアレイ(PLA)から構成されていても良く、あるいはここで説明する機能を実行するように独自に設計されていても良い。ノード論理により実行されるべき機能を説明したならば、当業者はむやみに説明を加えなくとも本発明を実現することができるであろう。ノードは、その論理によって、バス初期設定、ツリー識別、自己識別及びバスアービトレーションの機能を含む最小限のアービトレーションプロトコルを実現するが、それら全ての機能については以下にさらに詳細に説明する。
【実施例】
【0013】
図1に示すノード10は送信側マルチプレクサ12及び13と、データ送信器、受信器及び再同期装置14とをさらに含む。図1に示すノードは局所ホスト15に結合している。局所ホスト15は、システム中の他の構成要素と通信することが必要であるディスクドライブ、CPU、キーボード又は他の何らかの構成要素などの、バスに付属させたい何らかの装置であれば良い。ノード10は通信リンクを介して他のノードと通信する。リンクは2つのポートの間の接続であって、直接的、実用的な用語でいえばケーブルセグメントであるが、通常は何らかの物理通信チャネルとして実現されれば良い。リンクは、最低でも、それが接続する2つのポートの間に半二重通信チャネルを構成することが可能であるべきであろう。ポートはノードとリンクとの間のインタフェースである。本発明に従えば、ポートはデータ及びアービトレーション信号を送受信する能力を有していなければならない。ポートは、それがリンクを介して別のポートに接続しているか否かを判定することもできなければならない。これを容易にする1つの方法は、接続しているポートによってリンクを介して、リンクの他端にあるポートにより検出可能であるバイアス電圧を印加させるというものである。すなわち、1つのポートに、他端でポートに接続していないリンク、裸リンクが付属している場合には、そのポートは接続ポートではないと判定するのである。図1では、図示されているノード10は接続リンク17,18及び19をそれぞれ有する3つの外部ポート21,22及び23を有する。
【0014】
本発明を実現するためのノードに関わる実現規則のいくつかは、1つのノードが1つ又は複数のポートを有していて良いということである。ノードはそのポートのいずれか1つでデータを送受信可能であるべきであろう。ノードは一度にイネーブルされているポートのうち唯一つのポートでデータを受信可能であり且つ残る全てのイネーブルされたポートではこのデータを送信可能であるべきであろう。ノードはそのポートの全てを介して信号メッセージを同時に且つ独立して送受信可能であるべきであろう。ノードのポートごとに別個の信号トランシーバ、エンコーダ及びデコーダが要求される。最低限の実現ノードは局所ホスト装置を必要としない。たとえば、そのようなノードはケーブル延長として機能しても良い。これ以降、装置及び局所ホストを無視し、バストポロジーを言うときには、常に、ノードや様々なポートを介するバス接続に関連させて説明する。
【0015】
グラフ変換
図2(a)及び図2(b)は、任意に組立てられたノードの集合体を示す。これ以降、ノードを単に円として示すが、ノードは、それぞれ、図1に関して説明した素子と等価の素子を含むものと思われる。ただし、各ノードはその図に示した3つより多い数又は少ない数の外部ポートを有していても良いということに注意する。それぞれのノードを結合する図示されている線は、リンクを示すための方法である。ポートは図示されていないが、暗黙のうちに、リンクとノードを接続するインタフェースである。
【0016】
ここで説明するバスアービトレーション技法は、任意のトポロジーを非サイクル有向グラフへと変更することを要求する。任意トポロジーグラフにおいては、ノードとリンクの集合体は1つのサイクルを形成しても良い。グラフ中の特定のノードから始まって、リンクを2度通ることをせずにリンクとノードを通過することによって同じノードに戻れる場合に、サイクルは成立する。図2(a)は、図示されているノードはいずれもループの中に接続していないことから、非サイクルグラフを示している。ところが、図2(b)は、境界規定ボックス25の中の領域が複数のサイクルを形成するノード40〜47の集合体を含んでいるために非サイクルグラフではない。説明すべきバスアービトレーション技法はサイクルが存在しないことを要求するので、ここではサイクルを変更するためのユーザ介入の方法についてもさらに説明する。
【0017】
グラフを非サイクルしないという必要条件に加えて、グラフは有向グラフでなければならない。有向グラフは、隣接ノードの間に階層構造が成立しているようなグラフである。当初は、ノード間に親子関係は成立していない。すなわち、たとえば、ノード31はノード34に対して「親ノード」であっても良く、あるいはノード34に対して「子ノード」であっても良い。従って、所定の任意トポロジーグラフを取り上げて、それを非サイクル有向グラフに変換することが必要である。ここで説明する方法は、ノードの数、あるいはノードが物理的にどのようにリンクしているかということとは無関係に且つリンクに沿った信号伝搬時間には関係なく、どのような所定の任意トポロジーに対してもこの変換を実行するように働く。
【0018】
ノード通信
まず、非サイクル任意トポロジーグラフを有向グラフに変換するプロセスを説明する。次に、サイクル変更が要求されるケースを説明する。図3(a)は、ノードとリンクが状態ラベルを有し且つ通信される信号はグラフを有向にするためのグラフ変換プロセスを表して指示されているような図2(a)の任意グラフを示す。この時点で、ノード間の信号通信を説明しておくと有益である。図3(b)は、リンク52によって結合された2つのノード50及び51(以下、それぞれノードAと、ノードB)を示す。説明した通り、リンクは図1に関連して先に説明したように各々のノードのトランシーバポートを結合する通信チャネルである。グラフ変換プロセスの間、ノードは隣接するノードとの間に親子関係を成立させることが必要になる。第1のノードのポートと第2のノードのポートとの間に少なくとも1つのリンクが接続していれば、それら2つのノードは隣接ノードであるという。図3(b)〜図3(d)では、変更されるべき関係はノードBがノードAの親であるということであり且つノードはその関係を成立させることが適切であると仮定する。
【0019】
方向を設定するのに先立って、ノードAがノードBをその親として成立させることが適切になったとき、ノードAはリンク52が結合しているポートから信号「You Are My Parent」(YAMP)を送信する。このメッセージは、ノードAがYAMP信号を発生していることをわかり且つノードBは受信したメッセージがYAMPであることを理解できるのであれば、どのような形態をとっていても良い。YAMP信号53がノードBにより受信されると、ノードBは「You Are My Child」(YAMC)をリンク52を介してノードAへ送信することによってノードAに応答する。ノードAのアービトレーション状態機械論理11はYAMP信号53の送信と、YAMC信号54の受信との間の時間遅延を追跡し続ける。測定される時間は、ノードAとノードBとの間の伝搬遅延の2倍を指定する。YAMC信号を受信すると、ノードAは「You Are My Child Acknowledged」(YAMCA)信号55をもって応答する。これは、ノード間の伝搬時間遅延がYAMCの送信と、YAMCAの受信との間の時間遅延と等しいことをも確定する能力をノードBに与える。半二重通信リンクの場合、YAMCAメッセージは通信チャネルを適正に方向付けする効果をも有する。
【0020】
全二重通信リンクの場合には、3つの論理メッセージYAMP、YAMC及びYAMCAを代わりに2回の信号送信のみによって中継することができる。図3(c)にはこの状況が示されており、ノードAは戻りYAMC信号57を受信するまでYAMP信号56を加え続ける。YAMCA信号は、論理上は、YAMP信号が到着しなくなったと検出されたときにノードBへ送信される。
説明したこの三重非同期メッセージ交換の使用により、メッセージ交換に関わる双方のノードがリンクを介する伝搬時間遅延を確定できるようなメカニズムが構成される。この遅延値は以下にさらに説明する競合事象を変更するとき、並びにバス性能を最適化するための正規のバスアービトレーションの間に使用される。このパラメータの動的抽出は必須である。その代わりに、最適のバス性能は得られなくとも最大伝搬時間遅延を演繹的に規定することができる。
【0021】
ノードA及びBがノードBはノードAの親であることを意味するメッセージを交換した後には、リンクは有向になったと言うことができる。ノードAはその論理によって、リンク52が結合しているポートを親ポート(親ノードに話し掛ける)とラベル付けし、また、ノードBはリンク52が結合しているポートを子ポート(子ノードに話し掛ける)とラベル付けする。以下に説明する方法は所定の時点でノード及びポートに割当てられるラベルによって説明されるため、ポートが得るラベルを維持することは大切である。図3(d)には速記図式表記が示されており、図中の方向矢印58はノードBがノードAの親として設定されており且つリンクは有向であることを指示している。
【0022】
方向確定
ここで図3(a)に戻ると共に、図6(a)〜図6(e)のプロセスを参照して、任意トポロジー全体を方向づけするプロセスを説明する。トポロジー変換プロセスの説明を助けるためには、若干多彩な定義を導入することが必要である。第1に、「リーフ」ノードは1つのポートしか接続していないノードとして定義される。パワーアップ後又は他のバス初期設定後に初期設定されると、直ちにノードはその状態をリーフノードとして認識する。「ブランチ」ノードは少なくとも2つの接続するポートを有するノードである。1つを除く全ての接続ポートを介して、ブランチノードはYAMP信号を受信しており且つそれに応答している。残るポートを介して、ブランチノードはYAMP信号を送信しており、それにより、ノードが親ノードであることを確定する。ノードは、1つの親を有しており(ノードは親ノードを1つしかもつことができない)且つ他の全てのポートは子ノードに接続していることを確定するまで、ブランチ状態には到達しない。ブランチ状態に達するのに先立って、ノードがブランチであると確定されるまでノードが方向の設定を不可能にするサイクルの一部である可能性は存在しているので、ノードは「サイクル」ノードと考えられる。
【0023】
グラフ変換手続きは、ステップ60で、バス初期設定(パワーアップ又は誘導)のときに始まり、この時点で任意トポロジーの中のリーフノードはステップ61で認識し、決定ボックス66でそれらのノードが接続するポートを唯一つしかもたないことを判定することによって、ステップ68でそれら自身をリーフノードとしてラベル付けする。図3(a)に示すグラフにおいては、ノード33,35,36及び37は、初期設定後、ステップ69で各々がYAMP信号を唯一の接続ポートを介して隣接するノードへ送信するリーフノードである。それらの信号を受信するノードは、次に、ステップ70でYAMC信号をリーフノードへ伝搬して戻すことにより、YAMCA通信が完了したときにはそれぞれの親子ペアの間の所定のリンクについて1つの方向が確定する。ステップ71では、各リーフノードは1つの接続ポートを親ポートとしてラベル付けし、親ノードにある各受信ポートは子ポートとしてラベル付けされる。
【0024】
当初はリーフノードでないグラフ上のノードは、初め、先に述べた理由によって「サイクルノード」と考えられ、サイクルノード手続き63に従って進行する。接続するポートのうち1つを除いて全てのポートを子ポートとしてラベル付けしているサイクルノードは、いずれも、後のステップ85で、残ったラベル付けされていないポートからYAMP信号を伝搬する。リンクについてその方向が設定されたとき、そこでサイクルノードはブランチノードとラベル付けされるようになる。すなわち、リーフノード37がそのノード34を親として確定した後は、ノード34は唯一つのラベルなしポートを有するので(ノード37に至るリンク接続を子ポートを介するものとしてラベル付けしている)、ノード34はYAMP信号をノード31へ同報通信し、その結果、ノード34はブランチノードになる。同様に、ノード31がノード33及び34はその子ノードであると識別したならば、ノード31はYAMP信号をノード30へ同報通信する。1つのノードが決定ボックス75でその全てのポートを介してYAMP信号を受信していたとき、そのノードはルートノードになる。図3(a)で、ノード30がノード31及び32からYAMP信号を受信した後、そのラベルはサイクルノードからルートノードであると変わる。図3(a)のグラフにおいては、必ずしもノード30がルートになる必要はないであろう。ツリー中のリンクのうちいくつかが長い伝搬遅延を生じさせるのであれば、ノード30は1つのポートでYAMP信号を受信しており、次に別のポートを介してYAMP信号を送信していたかもしれない。ノードのいずれもルート、さらにはリーフになって良く、リーフは適正に手続きをとる。図3(e)は、図3(a)に示す通信信号に応答して、その結果得られた有向グラフを示し、各ノードはラベル付けされており且つ方向は黒の矢印によって指示されている。
【0025】
ルート競合
状況によっては、ルート競合状態が起こりうる。これは、たとえば、任意トポロジーが図4に示す任意トポロジーに対し対称の配列を有するような場合に起こるであろう。図4に示す任意グラフでは、ノード160及び161はそれが結合している2つのリーフノードに対して親であることをそれぞれ確定している。次に、各ノードはYAMP信号をほぼ同時に他方へ伝搬している。ルート競合状態は決定ボックス86において関連する双方のノードにより認識される。各ノードはそれを親として指定する信号を受信しており、その一方で同じ信号を同じポートを介して送信している。競合しているノードの各々はステップ91でYAMC信号によって他方に応答し、それにより、各ノードはノード間の伝搬時間の2倍に等しい「決定時限」を確定できる。
【0026】
ルート競合状態は、各ノードの各々の任意状態機械論理装置11に組込まれているランダム決定メカニズムを利用することによって解決される。「決定時限」が経過するたびに、各ノードは、ステップ92で、再び他方へYAMP信号を送信すべきか否かを無作為に(50%の確率をもって)決定する。ほぼ確実に限られた数のサイクルの中で、一方のノードはその一方が往復することなく他方を親として指定することを決定する。親と指定されたほうはステップ95でルートになる。あるいは、ノードに所定の選択基準値を割当て、その大きいほう又は小さいほうの値が競合事象でどちらが優勢であるかを判定するようにしても良い。「決定時限」の動的確定は最適の性能を与えるものではあるが、本発明を実現する上で不可欠ではない。その代わりに、このアルゴリズムを使用するどのようなバスにおいても生じうる最悪の場合のリンク伝搬より長くありさえすれば、演繹的に定義された「決定時限」を使用しても良い。ルート競合を解決するために使用するのと同じ方法が、以下にさらに説明する他の競合事象を解決するためにも使用される。
【0027】
ルート割当て
先に説明した通り、グラフ変換プロセスの結果はグラフ中の唯一つのノードへのルート属性の割当てである。ルートノードは後述するバスアービトレーション方式における最終的な決定を有し、従って、特別の優先順位時間間隔を使用せずに最大の優先順位をもってバスをアクセスすることができる。多くの場合、所定のシステムを最適化するために、ノードが製造されるときに、もしくは動的に(ランタイム中に)所定のノードにルート特性を割当てることが可能であるのが望ましい。所定のバスは、等時性データ転送を要求するノードを含んでいるかもしれない。等時性データは、所定の時間に何らかの値をもつように伝送されなければならないデータである。たとえば、コンパクトディスクから発する音楽は、断片的に転送され、必ずしも順序通りではないデータファイルとは異なり、聴取すべき順序で、大きな遅れなく転送され且つ出力される必要がある。
【0028】
ルート指定に関してノードを3つのカテゴリに分類することができる。それらの指定は、製造中、装置への指定のハードワイヤリング、アービトレーション状態機械論理のプログラミング又は決定を実行するより高いレベルのソフトウェアの使用と、その後のその決定を維持したままの再ブートの開始によって適用されれば良い。ルートを指定されるのに関してノードが割当てられうる3つの指定は:ルートとなることを望まないノードと、ルートになりうる(なるべき)ノードと、ルートになるであろうノードである。ステップ81及び83では、それらの指定を試験する。第1のカテゴリに指定されるノードは、指示されたときに直ちにグラフ変換手続きを開始する。これは、通常、バス初期設定手続きの完了の直後である。第2のカテゴリのノードは、ステップ84でグラフ変換手続きを開始することを指示された後に、そのプロセスの開始を所定の長さの時間だけ遅延させる。この遅延によって、ノードはルートになる機会を増す。(YAMP信号はその遅延によりそのノードまでより伝搬しやすい。)遅延の追加にもかかわらず、「ルートになりうる」ノードがルートと指定されることで終わらない可能性は依然としてある。これは与えられたトポロジーと、メッセージ伝搬遅延とによって決まる。遅延の量は、設計中、相当に複雑なグラフを通るときの最悪の場合の妥当な伝搬遅延より多くなるように定義できる。
【0029】
ルート指定の可能性のうち第3のカテゴリに入るノードは、グラフを既に変換し終わり且つ全てのノードはそれ自体を識別した後にルートにならなければならないということを認識するのみであろう。アービトレーション状態機能論理がこの確定を実行しても良く、ホストシステムでランするソフトウェアであっても良い。これが起こると、ルートにならなければならないノードはバスに沿った他の全てのノードと、それが唯一のルートになろうとしていることを承諾し、以下でさらに説明する割込形バス初期設定信号を発信することによってグラフ変換プロセスを再開する。次に、ノードは、ステップ82で、ルートになるのを待ち、その全てのポートでYAMP信号を受信するまでグラフ変換に参加せず、それにより、そのノードは必然的にルートと指定されることになる。
ルートが確定されたならば、グラフは有向であるということができる。グラフ上の全ての隣接ノードの間に定義された関係が存在している。
【0030】
サイクル変更
先に説明したグラフを有向にする手続きは非サイクルグラフについてのみ働く。任意トポロジーの中にサイクルがあれば、ステップ80で始まる手続きによってサイクルを破断しなければならない。ステップ79で、所定の時間切れ周期が経過した後に、ノードが依然としてリーフ、ブランチ又はルートではなく、サイクルノードとラベル付けされているとき、サイクルの存在は検出される。「サイクル検出」タイミングはバス初期設定機能の終了の直後に始まる。時間切れ周期は最悪の場合のグラフ変換プロセスの持続時間(「ルートになりうる」ノード及び起こりうるルート競合事象に関しての遅延時間の追加)より長くなってはならない。
【0031】
あらゆるメッセージ交換は非同期事象であるので、「サイクル検出」時間切れ事象はグラフの全てのノードに対して同時に起こる必要はない。そのため、「サイクル検出」時間切れ事象にまだ到達していないノードがサイクル解決は進行中であることを指示するメッセージを受信することは可能である。そのようなノードはそのサイクル検出時間切れ間隔を終了し、適切なサイクル解決プロセスを開始する。
【0032】
本発明に従ったサイクル解決の方法は組立て後のノードの集合体のユーザが介入することを要求する。ノードが「サイクル検出」時間切れを受けると、システムのユーザは図6(e)のステップ100で、サイクルが存在しており且つノードが次に関連しない出力装置を介して通知されるであろう。そこで、ユーザは、どのようなサイクルでも存在することを排除するために、リンクを遮断することを命令される。次に、ユーザはグラフ変換手続きに制御を戻す。
ループの各々が破断されて、サイクルが全く残っていないのであれば、先の節で説明したようなグラフを変換する手続きを、グラフ全体が非サイクルであると共に有向になるまで進行させて良い。
【0033】
固有物理アドレスの割当て
元の任意トポロジーから非サイクル有向グラフを確定したならば、グラフの各ノードに固有の物理アドレスを割当てることが可能である。このプロセスは、全てのリーフノードがその単一の接続ポートを介してバス要求(BR)信号を送信することによりバスを要求することをもって始まる。その信号を受信した親ノードは、その子ポートの全てからBR信号を受信し終わるまで待機し、次にBR信号をその親に伝搬する。BR信号は、ルートがその子の全てからBR信号を受信し終わるまでグラフを通って伝搬する。ルートがその子ポートの全てを介してバス要求を受信したならば、ルートはバスを1つのポートを介して許可し且つその残る子ポートを介してバス拒否(BD)信号を伝搬するための決定を実行する。どのバス要求を許可すべきかを選択する方法は、先に、たとえば、ポートを左から右へと又はポート番号づけに基づいて選択する場合などについて説明したような演繹的決定であっても良い。バス許可(BG)信号はルートからそれが要求している子へ送信される。その要求中の子が、それ自体、その子のうち1つからバス要求を伝搬した親ノードである場合には、その子ノードはその子ポートの1つを除く全てのポートを介して先に説明したのと同じ所定の方式でバス拒否信号を送信する。最終的には1つのリーフノードがバス許可信号を受信し、そのノードはバス許可確認(BGA)信号によって応答し、BGA信号はルートノードへと伝搬されて戻る。BD信号とBGA信号の伝搬は半二重通信チャネルの場合に必要になるであろう通信リンクの方向を定める働きをする。そこで、拒否された全てのノードは最終的にBG信号を受信するノードによるアクティビティを待つ。
【0034】
最終的にバスに対するアクセスを許可されるノードはアドレス割当てパケットを送信する。ノードはこのパケットをバスを介して送信し、パケットは他の全てのノードにより受信されて、それらのノードは、それぞれ、受信するアドレスパケットの数をカウントする。送信されるアドレスパケットは何らかの任意の情報を有していても良い。ノードの固有物理アドレスは、ノードがアドレスパケットを送信する前にカウントしたアドレスパケットの数に基づいている。すなわち、前もってアドレス情報は割当てられていないにもかかわらず、2つのノードが同じ物理アドレスを獲得することはない。アドレスパケットの実際の組成は任意であって、システムにより効率良く利用可能な何らかのビットストリームであれば良い。物理アドレス割当てパケットを送信した後、ノードは「子ID完了」信号(CIC)信号を送信する。子ポートでこれを受信した親ノードは、次に、「子識別完了確認」(CICA)信号を送信し、ポートを識別済子ポートとしてラベル付けする。次のBR信号の伝搬に応答して、自身を識別したばかりであるノードの親は物理アドレスパケットを送信すべき次の子を選択する。1つの親ノードの子ノードの全てが自身を識別したならば、親ノードはバスを要求し、バスを許可したとき、その物理アドレス割当てパケットを伝搬する。この手続きは、所定の選択基準に従って、全てのノードがカウント動作によって固有物理アドレス割当てを確定するまで続く。図5は、左から右への事前定義済選択基準が実現されている図3(e)のグラフを示す。ノードは固有のアドレスを割当てられ、ノード33は第1のアドレスを受信し、前述のように、ルートノード30は第8の、そして最後のアドレスを受信する。
この手続きが完了すると、グラフ中の各ノードは固有物理アドレスを有することになり、そのアドレスは前もって確定されている必要はなく、システム管理又はその他の目的のために利用されれば良い。
【0035】
ノードの自己識別
ノード自己識別プロセスは本質的には先に説明した物理アドレス割当て手続きと同一のルーチンに従う。各ノードがその物理アドレス割当てパケットを送信するとき、そのパケットはノードに関連する局所ホストのID、それがどれほどの量の電力を必要とするか、さらに、たとえば、「ソフトパワーオン」属性を支援するか否か等々の別の情報を含んでいても良い。事実、ノード自己識別情報は、どの情報を送信するにしても、それは固有物理アドレスを獲得するためのカウントの基礎となることから、物理アドレス割当てパケットとして働くのである。
ノード自己識別パケットに関しては、ノードに関する特定の情報は告知しているノードの性質によって影響を受けるノードにより「聴取」されるだけで良い。先の場合と同様に、この手続きは全ノードがそのノード自己識別情報を送信し終わるまで進んで行く。
【0036】
トポロジーマッピング
トポロジーマッピングの方法は、物理アドレス割当て及びノード自己識別と同じラインに沿って流れる。すなわち、この手続きでは、各ノードがアドレス割当て又はノード自己識別のプロセスを経過しているとき、そのノードに、ノードが有している子ポートの数及びディスエーブルされたポートを有しているか否かなどの全てのポートに関する情報をさらに送信する。ディスエーブルされたポートに関しては、どこからディスエーブルされるかを識別できるように、ディスエーブルしようとしているポートの相互間に通信規約を実現することが望ましいであろう。従って、ポートがディスエーブルされたポートを識別するとき、ポートはそれ独自のIDを指示する識別子並びにディスエーブルされる元になったポートIDを与える。
【0037】
トポロジーマッピング手続きの間に受信する全てのポートに関わるあらゆるトポロジー情報を組立てることにより、ホスト又は何らかのソフトウェアレベルアプリケーションは解決したバストポロジーを論理的に再構成できるであろう。これは、リンクが予想外に故障した場合に、先にディスエーブルしたリンクがどのノードに対しても通信チャネルの損失を阻止するように働ける冗長性を実現することを含む数多くの目的のために有用である。
【0038】
公正バスアクセスアービトレーション
トポロジーマッピング、ノード自己識別又は物理アドレス割当てのルーチンが完了したならば、バスが起動し、ラン中であると考えることができる。本発明に従って実現される1つのアービトレーション方式は、正当なバスアクセスのアービトレーション方式である。バスに対するアクセスを望むとき、ノードはその親ポートを介して(それがルートでない限り)バス要求(BR)信号を送信する。親は、1つの子からBR信号を受信すると、他の全ての子ポートを介してバス拒否信号(BD)を送信する。そこで、親はBR信号をその親を通って、その信号がルートに到達するまで上方へと伝搬する。ルートはそれが受信する第1のBR信号に応答してバス許可信号(BG)を発行すると共に、その他の全ての子ポートを介してBD信号を送信し、BD信号は下方へと伝搬することにより、リンクの方向を定める。BG信号は要求している側のノードに到達するまでグラフを通って下方へと伝搬し、そのノードは、次に、バス確認(BA)信号を送信し、それに続くのはノードがバスへ送信することを必要とした情報のパケットである。パケットが完了したとき、全てのノードはアイドル状態に戻るか、又はアイドル状態に入る。
【0039】
ルートがバスに対するほぼ同時の要求を受信する場合、ノードのうち1つにバスアクセスを許可するために、ルートノードに関わる所定の選択基準を使用することができる。これは先に説明したのと同じ所定の優先順位選択基準であっても良い。
【0040】
公正バスアクセスアービトレーションの別の一面は、親ノードがその子に対して優先権をもつことである。すなわち、親ノードは、バスを要求するときに、BD信号をその子ポートの全てを介して送信し、次にBR信号をルートに向かって上方へと伝搬する。このメカニズムに伴って起こりうる1つの問題は、親がバスを介して送信すべき大量の情報を有している場合に、子ノードが適切なバスアクセスを獲得するのに障害を生じるかもしれないということである。従って、当該技術では広く使用され且つ良く知られているギャップシステムが導入されている。ノードはバスを利用した後に、再びバスを要求できるようになる前にギャップ周期1つ分待機しなければならない。これにより、バス上におけるノードのトポロジー配列にかかわらず、バスに沿ったどのノードにもバスを許可される均等な機会が与えられるのである。公正アービトレーションプロトコルを保証するためには、ギャップの長さはバスを通過するときの最悪の場合の信号伝搬遅延より大きくなければならない。ギャップ値をあらかじめ確定して、ノード論理にハードワイヤリングすることができるが、そのような方式は、結果として、最も極端なケースを除くあらゆる場合においてバスを最適に近い形で利用できる。トポロジーマッピング能力は、グラフ変換段階の間に実行される隣接ノード間の伝搬遅延の測定とあいまって、どの特定の実現形態に対してもバス性能を最適化する最適公正ギャップの計算を可能にする。
【0041】
優先バスアービトレーション
上述の公正バスアクセスアービトレーションに従って実現されるバスアービトレーション方式においては、ルートは常にバス優先権を有していることが望ましいであろう。これが実現されるとき、ルートノードはそれ自身にいつでもバスを許可して良い。これは、まず、BD信号をグラフ中の全てのノードを通して下方へと送信することによって実行される。ルートに関わる優先バスアクセスは、等時性データ転送を実行するためにルートノードが要求されるような場合に非常に有用である。
【0042】
トークンパッシングバスアービトレーション
先に説明した公正バスアクセスアービトレーション方式及び優先バスアクセスアービトレーション方式の代わりに、トークンパッシングバスアービトレーション方式を実現するに際して本発明を利用しても良い。比喩的にいえば、トークンパッシングバスアクセスは、バスがノード間を渡されているトークンを所有しているときにノードはバスを介して通信して良いという概念を表わす。各ノードがサイクル中の所定のポイントでバスを受けるように、トークンはノードからノードへとサイクル方式で渡されて行く。本発明においては、トークンパッシングは先に説明した物理アドレス割当てルーチンと同じ方式に従って実現される。実現される所定の選択メカニズムを使用して、トークンをノードからノードへと渡して行く順序を選択する。この順序は、固有アドレス割当ての順序を指示する図5に示すような順序に類似している。各ノードは、トークンを割当てられたとき、残るノードが聴取している間にバスに沿ってその情報パケットを伝搬する。次に、ノードは、先に説明したような所定の順序づけ方法に基づいてトークンを次の論理ノードに渡す。
【0043】
プレエンプティブバス初期設定
本発明に従って実現しうる重要な特徴は、プレエンプティブバス初期設定の概念である。各ノードに組込まれている状態機械論理は、いくつかの条件に対してノードからその全てのポートを介して伝搬されるべきバス初期設定(BI)信号をトリガすることができる。ノードがバス初期設定条件を信号で報知する必要があると確定したとき、ノードはBI信号をその全てのポートを介して、全ての隣接ノードがその信号を受信し、次に変更するように保証するのに十分な長さの時間だけ伝搬する。そこで、ノードはその後に先に説明した手続きの中でグラフ変換プロセスに至る開始手続きに入る。
【0044】
プレエンプティブバス初期設定をトリガすることを必要にするか又は望ましくするであろういくつかの状況がある。第1に、これは予期せぬ誤りに対するノード応答であっても良い。加えて、ホストレベルでは、異なるノードがルート属性、たとえば、等時性データ転送ノードを獲得すべきであることを確定しても良い。この割当てはバス初期設定ルーチンを通して維持されるので、所望のノードはルート指定を受信するまで変換手続きの間は待機することになる。プレエンプティブバス初期設定に至る別の条件はリンクの破断であろうが、その場合、付属するノードについて新たな非サイクル有向グラフを計算することが必要であろう。最後にプレエンプティブバス初期設定が起こるべき重要な状況は、周辺機器の「ホットアディション」と呼ばれるような、装置がネットワークに追加されるときである。新たな装置が接続されるポートは新たなノードの有無を検出し、システムのユーザに対しては透明であるが、たとえば、遮断と再給電の必要なく周辺機器の増減を可能にするバス初期設定をトリガする。追加されたノードの存在を含む新たな非サイクル有向グラフを計算する。いくつかのノードを取り除いたとき、バス初期設定をトリガする必要はなくなる、たとえば、リーフノードを取り除いたときには、ネットワークに害はないということはありうる。しかしながら、動作中のバスからブランチノードが指定される場合には、グラフを再構成する必要がありそうである。
【0045】
本発明を好ましい実施例によって説明したが、当業者により本発明の趣旨から逸脱せずに様々な変形や変更を実施しうることは理解されるであろう。従って、本発明は続く請求の範囲によって判断されるべきである。
【図面の簡単な説明】
【0046】
【図1】図1は、本発明に従って利用されるハードウェア層実現のブロック線図を示す。
【図2a】図2(a)は、ノードの任意の組立てられた集合体を示し、非サイクルのものを示す。
【図2b】図2(b)は、ノードの任意の組立てられた集合体を示し、サイクルを含むものを示す。
【図3a】図3(a)は、本発明に従ったグラフ変換プロセスを受ける図2(a)のノードの任意に組立てられた集合体である。
【図3b】図3(b)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3c】図3(c)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3d】図3(d)は、本発明を実現するに際してのノード間の代替通信交換例を示す。
【図3e】図3(e)は、図2(a)のノードの任意に組立てられたネットワークから得られる有向グラフを図式的に示す。
【図4】図4は、ルート競合を変更することを要求する対称グラフ配列を示す。
【図5】図5は、指示されうる固有アドレス割当て順序をもつ非サイクル有向グラフを示す。
【図6a】図6(a)は、本発明の好ましい実施例に従うプロセスの全体の流れを示す。
【図6b】図6(b)は、本発明の好ましい実施例に従うプロセスのリーフノード手続の流れを示す。
【図6c】図6(c)は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第1部分を示す。
【図6d】図6(d)は、本発明の好ましい実施例に従うプロセスのサイクルノード手続の第2部分を示す。
【図6e】図6(e)は、本発明の好ましい実施例に従うプロセスのルート競合処理の流れを示す。
【図6f】図6(f)は、本発明の好ましい実施例に従うプロセスのサイクル変更処理を示す。
【符号の説明】
【0047】
10 ノード
11 アービトレーション状態機械論理
14 データ送受信及び同期装置
【特許請求の範囲】
【請求項1】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードに第1のノードから「You are My Parent(YAMP)信号」を伝搬し、
「YAMP信号」の伝搬後に第2のノードから「You are My Child(YAMC)信号」を第1のノードにて受信し、
「YAMC信号」の受信に応答して前記第1のノードと第2のノードとの親子関係を確立し、
「YAMP信号」の伝搬と「YAMC信号」の受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定する方法。
【請求項2】
前記受信に応答して、前記第1のノードから第2のノードに「You are My Child Acknowledged(YAMCA)信号」を伝搬し、第2のノードからの第1のノードへの「YAMC信号」の伝搬と第1のノードからの「YAMC信号」の第2のノードでの受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定することをさらに含む請求項1記載の方法。
【請求項3】
第2のノードからの「YAMP」信号が「YAMP」信号の伝搬と「YAMC」信号の受信の間で受信されなかったとき、親子関係が確立される請求項1記載の方法。
【請求項4】
さらに、
前記ラウンド・トリップ時間にしたがって決定時間期間を決定し、
決定時間期間に基づく時間期間後、タスク実行が決定されるまでタスクを実行するか否かランダムに決定することを繰り返す請求項1記載の方法。
【請求項5】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードからの「You are My Parent(YAMP)信号」を第1のノードにて受信し、
「YAMP信号」の受信に応答して第1のノードから「You are My Child(YAMC)信号」を第2のノードに伝搬し、
「YAMP信号」の受信に応答して前記第1のノードと第2のノードとの親子関係を確立し、
前記「YAMC信号」の伝搬後、前記第2のノードからの「You are My Child Acknowledged(YAMCA)信号」を第1のノードにて受信し、
「YAMC信号」の伝搬と「YAMCA信号」の受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定する方法。
【請求項6】
第1のノードで受信される「YAMP」信号が、第1のノードから伝搬された「YAMP」信号に応答しないものであるとき、親子関係が確立される請求項5記載の方法。
【請求項7】
さらに、
前記ラウンド・トリップ時間にしたがって決定時間期間を決定し、
決定時間期間に基づく時間期間後、タスク実行が決定されるまでタスクを実行するか否かランダムに決定することを繰り返す請求項5記載の方法。
【請求項8】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードに第1のノードから第1の「You are My Parent(YAMP)信号」を伝搬し、
「YAMP信号」の伝搬後に第2のノードから第2の「YAMP信号」を第1のノードにて受信し、
第2の「YAMP」信号に応答して期間を決定し、
その期間の間に第2のノードからの「YAMP信号」が第1のノードにて受信されない場合にその期間の満了後に第1のノードから第2のノードに第3の「YAMP信号」を伝搬し、
第3の「YAMC信号」の伝搬後、第2のノードからの第1の「You are My Child(YAMC)信号」を第1のノードにて受信し、
第1の「YAMC信号」に応答して前記第1のノードと第2のノードとの親子関係を確立する方法。
【請求項9】
さらに、
前記期間の満了後、第2のノードからの第4の「YAMP信号」を第1のノードにて受信し、
第4の「YAMP信号」に応答して第1のノードから第2のノードへ第2の「YAMC信号」を伝搬し、
第4の「YAMP信号」に応答して第1、第2のノード間の親子関係を確立することを含む請求項8記載の方法。
【請求項10】
前記期間は所定の長さである請求項8記載の方法。
【請求項11】
さらに、
第2の「YAMP信号」に応答して第1のノードから第2のノードに第3の「YAMC信号」を伝搬し、
前記期間の決定前であってかつ前記第2の「YAMP信号」の受信後、第2のノードからの第4の「YAMC信号」を第1のノードにて受信し、
第1の「YAMP信号」の伝搬と第4の「YAMC信号」の受信までの時間ギャップにしたがって前記期間を決定することを含む請求項8記載の方法。
【請求項12】
さらに、
前記期間の満了後、第1のノードから第2のノードへ「YAMP信号」を伝搬するか否かランダムに決定することを含み、
前記「YAMP信号」を第1のノードから第2のノードへ伝搬することを決定したことに応答して第3の「YAMP信号」の伝搬を行う請求項11記載の方法。
【請求項13】
さらに、
前記時間ギャップにしたがって決定時間期間を決定し、
決定時間期間に基づく期間後、「YAMP信号」を伝搬することを決定するまで前記「YAMP信号」を第2のノードに伝搬するか否かランダムに決定することを繰り返す請求項12記載の方法。
【請求項1】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードに第1のノードから「You are My Parent(YAMP)信号」を伝搬し、
「YAMP信号」の伝搬後に第2のノードから「You are My Child(YAMC)信号」を第1のノードにて受信し、
「YAMC信号」の受信に応答して前記第1のノードと第2のノードとの親子関係を確立し、
「YAMP信号」の伝搬と「YAMC信号」の受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定する方法。
【請求項2】
前記受信に応答して、前記第1のノードから第2のノードに「You are My Child Acknowledged(YAMCA)信号」を伝搬し、第2のノードからの第1のノードへの「YAMC信号」の伝搬と第1のノードからの「YAMC信号」の第2のノードでの受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定することをさらに含む請求項1記載の方法。
【請求項3】
第2のノードからの「YAMP」信号が「YAMP」信号の伝搬と「YAMC」信号の受信の間で受信されなかったとき、親子関係が確立される請求項1記載の方法。
【請求項4】
さらに、
前記ラウンド・トリップ時間にしたがって決定時間期間を決定し、
決定時間期間に基づく時間期間後、タスク実行が決定されるまでタスクを実行するか否かランダムに決定することを繰り返す請求項1記載の方法。
【請求項5】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードからの「You are My Parent(YAMP)信号」を第1のノードにて受信し、
「YAMP信号」の受信に応答して第1のノードから「You are My Child(YAMC)信号」を第2のノードに伝搬し、
「YAMP信号」の受信に応答して前記第1のノードと第2のノードとの親子関係を確立し、
前記「YAMC信号」の伝搬後、前記第2のノードからの「You are My Child Acknowledged(YAMCA)信号」を第1のノードにて受信し、
「YAMC信号」の伝搬と「YAMCA信号」の受信までのギャップ時間から第1、第2のノード間通信のラウンド・トリップ時間を決定する方法。
【請求項6】
第1のノードで受信される「YAMP」信号が、第1のノードから伝搬された「YAMP」信号に応答しないものであるとき、親子関係が確立される請求項5記載の方法。
【請求項7】
さらに、
前記ラウンド・トリップ時間にしたがって決定時間期間を決定し、
決定時間期間に基づく時間期間後、タスク実行が決定されるまでタスクを実行するか否かランダムに決定することを繰り返す請求項5記載の方法。
【請求項8】
第1のノードから少なくとも一つの隣接ノードに接続される少なくとも一つのポイント間リンクを介して、前記第1のノードが少なくとも一つの隣接ノードと通信を行う方法において、
前記少なくとも一つの隣接ノードの第2のノードに第1のノードから第1の「You are My Parent(YAMP)信号」を伝搬し、
「YAMP信号」の伝搬後に第2のノードから第2の「YAMP信号」を第1のノードにて受信し、
第2の「YAMP」信号に応答して期間を決定し、
その期間の間に第2のノードからの「YAMP信号」が第1のノードにて受信されない場合にその期間の満了後に第1のノードから第2のノードに第3の「YAMP信号」を伝搬し、
第3の「YAMC信号」の伝搬後、第2のノードからの第1の「You are My Child(YAMC)信号」を第1のノードにて受信し、
第1の「YAMC信号」に応答して前記第1のノードと第2のノードとの親子関係を確立する方法。
【請求項9】
さらに、
前記期間の満了後、第2のノードからの第4の「YAMP信号」を第1のノードにて受信し、
第4の「YAMP信号」に応答して第1のノードから第2のノードへ第2の「YAMC信号」を伝搬し、
第4の「YAMP信号」に応答して第1、第2のノード間の親子関係を確立することを含む請求項8記載の方法。
【請求項10】
前記期間は所定の長さである請求項8記載の方法。
【請求項11】
さらに、
第2の「YAMP信号」に応答して第1のノードから第2のノードに第3の「YAMC信号」を伝搬し、
前記期間の決定前であってかつ前記第2の「YAMP信号」の受信後、第2のノードからの第4の「YAMC信号」を第1のノードにて受信し、
第1の「YAMP信号」の伝搬と第4の「YAMC信号」の受信までの時間ギャップにしたがって前記期間を決定することを含む請求項8記載の方法。
【請求項12】
さらに、
前記期間の満了後、第1のノードから第2のノードへ「YAMP信号」を伝搬するか否かランダムに決定することを含み、
前記「YAMP信号」を第1のノードから第2のノードへ伝搬することを決定したことに応答して第3の「YAMP信号」の伝搬を行う請求項11記載の方法。
【請求項13】
さらに、
前記時間ギャップにしたがって決定時間期間を決定し、
決定時間期間に基づく期間後、「YAMP信号」を伝搬することを決定するまで前記「YAMP信号」を第2のノードに伝搬するか否かランダムに決定することを繰り返す請求項12記載の方法。
【図1】
【図2a】
【図2b】
【図3a】
【図3b】
【図3c】
【図3d】
【図3e】
【図4】
【図5】
【図6a】
【図6b】
【図6c】
【図6d】
【図6e】
【図6f】
【図2a】
【図2b】
【図3a】
【図3b】
【図3c】
【図3d】
【図3e】
【図4】
【図5】
【図6a】
【図6b】
【図6c】
【図6d】
【図6e】
【図6f】
【公開番号】特開2006−238452(P2006−238452A)
【公開日】平成18年9月7日(2006.9.7)
【国際特許分類】
【出願番号】特願2006−51942(P2006−51942)
【出願日】平成18年2月28日(2006.2.28)
【分割の表示】特願2003−158059(P2003−158059)の分割
【原出願日】平成5年12月16日(1993.12.16)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Macintosh
【出願人】(591049538)アプル・コンピュータ・インコーポレーテッド (7)
【Fターム(参考)】
【公開日】平成18年9月7日(2006.9.7)
【国際特許分類】
【出願日】平成18年2月28日(2006.2.28)
【分割の表示】特願2003−158059(P2003−158059)の分割
【原出願日】平成5年12月16日(1993.12.16)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Macintosh
【出願人】(591049538)アプル・コンピュータ・インコーポレーテッド (7)
【Fターム(参考)】
[ Back to top ]