JPH04505542A - Ａｔｍノードの共通記憶装置用制御ユニット - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 ＡＴＭノードの此゛看・億１？！ＩＩＶ卸ユニット本発明は請求項１の前段に基 づ＜ＡＴＭノードの共通記憶装置の制御に用いる制御ユニットに関する。本発明 はさらにこのノードの操作方法に関する。

用語ＡＴＭ　（非同期転送モード）は約１５５から６２２メガバイト／秒または これ以上の域における広帯域通信技術として公知である。この技術はパケットス イッチングとして考えられ、その全てのパケットはアドレスの付された均一の長 さを有している。以後、これらのパケットは他の文献と一致させて「セル」と呼 ぶことにする。

ＡＴＭノードは後で図１に概略的に示すように必要とする目的場所にセルを伝送 する働きをする。

ＡＴＭノードは種々の方法で構成できる。特許第ＢＥ９０４１００号に基づ（共 通記憶装置を用いるタイプのものは特に有利のようである。これはこの技術によ れば出力回路の一つまたは全ノードのブロックキングの問題が容易に克服できる 。

このタイプのＡＴＭノードの一つは、ＥＰ−Ａ−２９９４７３から詳しく知るこ とができる。このノードは主記憶装置を有しており、ここから全てのセルが主記 ・１装置中のアドレス管理のためのアドレスポインタストアおよび主記・ｌ装置 の空きエントリー（アイドルアドレスＦ　Ｉ　ＦＯ）の管理のための第３ストア に引出されている。アドレスポインラス１−アは主として一連のレジスタから成 る。これらのレジスタは引出し線と唯一連絡されている。レジスタは各々主記憶 装置中でストレージブロックのアドレスのための記憶装置として作用する。主記 憶装置中には、各関連する引出し線上に次のアドレスに伝送しなければならない セルか、あるいは記憶されるべき次に伝送されてくるセルのいずれかが記憶され る。どれだけのセルが記憶されているか、どのストレージブロックに記憶されて いるかという情報は各セルに関係し、かつ主記憶装置中のストレージブロックに 記憶されている。従って、直接アクセスはこの情報ではできない。

同圧願人によるＥＰ　、Δ、−３３６３７３には同様のＡＴ３４　、／−ドが開 示されている。その中でも特に重要視されるのはいわゆるマルチカースト装！、 すなわち、ただ一つの単一アドレスにそれぞれ伝送されるだけでなくかなり多く の自由に２択可能なアドレスにも伝送されるべきある種のセルである。

公知のＡＴＭノードの構造では、主記−１！装五の真の記′ｌ！機能がロジック と制御機能を総合し、セルがどこに記憶されるべきか、またはどこから読み出さ れるべきかを位置付けする。これでは理解するのが困難であり、融通性のないロ ジックの形態で現われるという本質的なハンディキャップがある。すなわち、こ の構造はＶＬＳＩ（超大曙模集積回路）または相当な改良努力を要するカスタム チップの使用を必要とする。

本発明の目的は、Ａ　Ｔ　Ｍノードの製作可能なより安価でより融通性のある装 置を提供し、そのＡＴＭノードはよりはっきりした構造であり、極めて簡単であ り。

従ってより安価でより信頼性のある操作機能性を有している。さらに、実際の構 造はあまり複雑でない集積回路にすることが可能である。

図１はＡ　Ｔ　Ｍノードの概略機構（最新技術による）を示す図である。

図２は共通記・ｌ装置を備えたＡＴＭノードのブロック図（！！に新技術による ）を示す区である。

図３は共通記′１１！装置の制御ユニットを示すブロック図である。

図４はバス／制御ロジックの詳細を示す制御ユニットのブロック図である。

図５は共通記憶装置の構成および内容の一例を示す表である。

図６はキューの形態にある共通記−！！！装置の内容を示す表である。

図７はリストの形態にあるＰ−ストアの内容を示す表である。

図８は共通記憶装置からセルを送り出すための順序図である。

図９は共通記・ｌ装置にセルを記憶させるための順序図である。

図１０は優先ロジックのブロック図である。

図１１はマルチカーストロシックのブロック図である。

図１はＡＴＭノード１０の極めて盪略的なブロック図を示す。このノードには複 数ｎ本の第１引入れ線１１および複数ｍ不の引出し縁１２がそれぞれ接続されて いる。ｎとｍは等しくてもよく１等しくなくてもよい。さらに２以上数１００ま での値とすることができる。引き出し綿１２となるセルには数個の異なる優先順 位ｐをもたせることができる。

どの引入れ線１１もバッファ１５に接続され、どの引出し綿１２もバッファ１６ の後段に接続されている。両線ｌＬ１２はこれらのバッファ１５．１６を介して スイッチングユニット１８に接続されている。このスイッチングユニット１８は 双頭矢印２０を介してスイッチング制御ユニット１９により制御される。

均−長さのアドレスの付されたパケットが引入れ綿１１からＡ　Ｔ　Ｍノードｌ Ｏに連続して入ってくる。これらのパケットは以後「セルＪ　（Ｚ）　（一つの セルは典型的にはユーザ情報の４８個の８ビツトバイトに続き５バイトまたは８ ビツトバイトのヘッダから成る）と呼ぶことにする。これらのセル２のヘッダか ら、スイッチング制御ユニットが第１に必要な制御情報（ヘッダ情報）を抽出す る。この制御情報から、送り出されるべき各セル２および伝送されるセルのため の新しいヘッダが引出し綿１２に引き出される。この動作は破線矢印２１によっ て示される。ユーザ情報を含まないセル２（いわゆる空きセル）が矢印２２によ って示されるようにバッファ１５から除去される。一方、引出し線１２に送り出 されるセル２がない場合、空きセルが矢印２３で示すようにこれに代って伝送さ れる。

セルはマルチカースト式またはＷ−Ａのブロードカースト（同報通信方式）とし て、また数本の所定のラインまたは全てのライン上に送り出される。

、Ａ　Ｔ　Ｍノード１０は、図によれば、入ってくるセル２の引出し線１２への 連続した伝送を変換するスイッチングの機能を実行する。もちろんこの点に関し 、関連する。ン・要条件は可能なときはいつでも考慮し、セル−ロスは決して生 じない。

図２にこの種の、Ａ　Ｔ　Ｍノード１０の一例のブロック図を示す。二の、Ａ　 Ｔ　Ｍノードは複数にのストレージブロックを傭人た共通記憶装置２７を有して いる。基本的に；よ、いずれの入ってくるセルＺも、引出し線１２の一本に再び 伝送されてくるｌ１ｉｉｌこ、この共通記憶装置２７に記！される。その付加バ ッファリング装置によって、共通記憶装置２７はセル−ロスを阻止し、連続した 方法でただ一つの単独セル２が同時に、すなわち連続して動作して書き込みまた は読み取りがそれぞれ可能となるように装備するのが好ましい。これを達成する ために、マルチプレクサ２９がバッファ１５と共通記・ツ装Ｍ２Ｔ間に挿入さね ている。このマルチプレクサがバッファ１５への入力からデータを周期的に取り 入れる。

ＡＴＭノード１０の入力側と同様にして、デマルチプレクサ３０が共通記憶装置 ２７と、引出し緋１２のためのバッファ１６との間に挿入されている。このデマ ルチプレクサは共通記憶装置２７のセルのＺ読み取りを各引出し線１２へ伝送す る。この動作はアドレス読取りユニット３３によるヘッダー情報の読み取りから 入力側において決定されたときに実行される。共通記憶装置２７はアドレス読取 りユニット３３からもっばら入ってくる必要な制御情報を受信する制御ユニット ３５によって制御される。最後に、シーケンサ３８がＡＴＭノード１０のユニッ トと共通記−１！装置２７を協同動作させる働きをする。このシーケンサは種々 のユニットの各機能段階をトリガし、かつそのユニットを互いに同期させる。

図３は図２に示した制御ユニット３５およびシーケンサ３８のブロック図を示す 。制御ユニット３５の最も重要なユニットは三つのアドレス可能な読取り／ＩＦ 込み記゛泄装置４１，４３．４５　（好ましくはラム−ランダム・アクセス・メ モリ）である。各読取り／書込み記憶装置はインデックスアドレス入力線Δ説」 −およびデータを記憶場所に記憶するための入力／出力線Ｄａｔａを有している 。

第１読取り／書込み記・ｌ装置４１は以後Ｈ−ストア（Ｈ＝ヘッド）と呼ぶ。こ の記憶装置はｍ＋１個の記憶場所を含んでいる。ここにｍは第２の複数の引き出 し線１２の数である）（次側ではｍ＝４）。Ｈ−ストアの記憶場所は引き出し線 １２の一本に各々連絡されており、ギリシャ文字のα、β、δ、μで示されてい る。加つるに、空き場所（後述するように）のリストと関連する０で示された（ ｍ＋１）番目の場所がある。

Ｈ−ストア４１の記憶場所Ｏ９α、β、δ、μの内容は各々ヘッダ素子（後述す るように）のアドレスである。

Ｈ−ストア４１はさらにシーケンサ３８と、入来セルに左右されるポイントコン トローラとによって制御される。これによって記憶場所のα、Ｂ、δ、Ｕの内容 は（後述するように）個々に書き込みまたは読み取りされる。記憶場所Ｏは特定 処理内容を受信する。

第２読取り／書込み記′１装置４３は以下Ｔ−ストア（Ｔ＝テイル）と呼ぶ。こ のＴ−ストアはＨ−ストアと同様にして構成されている。Ｔ−ストアの記憶場所 は同様にＯを含めてギリシャ文字のＢ、δ、μによって示される。その記゛！場 所の内容はそれぞれアドレスである。しかし、ポイントコントローラが周期的に 記憶場所を選択する。

第３読取り７畳込み記・１装置４５は、以後Ｐ−ストア（Ｐ＝ポインター）と呼 ぶ。この記・原装置は共通記憶装置２７のイメージを作る。この記′ｌ！！装置 は共通記憶装置２７のストレージブロックと同じ数にの記憶場所を含んでいる。

記憶場所およびストレージブロックは対をなし同じアドレスを有している。二つ の記′！場所間の差異は、Ｐ−ストアの記憶場所の容量が（短い）アドレスであ るのに対し、共通記憶装置２７のストレージブロックの容量が（長い）セルＺで あることである。

さらに、制御ユニット３５が制御情報入力４６、入力ロジック４８、バス／制御 ロジック５０、出力５２、コンパレータ５９、モニタロジック７１および優先ロ ジック７３を含んでいる。これらすべてのユニットは傾斜した矢印で示したよう に、シーケンサ３８によって連続的に作動またはトリガされる。

入力ロジック４８は制御情報入力４６（図２のアドレス読取りユニット３３から くる）を、優先ロジック７３、Ｈ−ストア４１およびＴ−ストア４３の各アドレ ス入力線Δｄｒだけでなくモニタロジック７１に接続させる。

図４はバス／制御ロジック５０をより詳細に示す。このロジック５０は多数の同 位バス６６．６７．６８．６９と、マルチプレクサ５１等の制御素子およびこれ ら両者間に配備されたトランシーバ５３．５５．５７から成る。ロジック５０は Ｈ−ストア４１およびＴ−ストア４３の入力、出力Ｄａｔａ線をＰ−ストア４５ の両人力ＫＭ（ＡｄｒおよびＤａｔａ）に、モニタロジック７１に、コンパレー タ５９、および出力５２にそれぞれ接続する。（バス６７から）出力５２へのバ スにはさらに二つの出力バッファ６１．６３が挿入されている。出力５２自体は 共通記ｔｉｌ装置２７への一方向バスであり、これがアドレス入力線に接続され ている。入力ロジック４８は、本質的にはＨ−ストア４１およびＴ−ストア４３ のための各アドレス信号と共動する二つの信号マルチプレクサ４７．４９から成 る。

マルチプレクサ４７．４９上にＯで示された入力は空き場所のリストを選択する ものである。

優先ロジック７３は、後はど詳述するが、制御ユニット３５のオプションである 。セルＺが例λば「アージェント」および１ノーマル」に転送するための異なる 優先順位に関係する場合に適合するだけである。しかし、まず最初に単一の優先 順位を有するセルのみが考慮される。

共通記憶装置２７および制御ユニット３５の動作方法は特定例における記憶装置 の状態に関係している次の図による実施例によって説明する。さらに図５は共通 記憶装置２７のストレージブロックのアドレスおよび現時点の内容を示している 。例のように、この記憶装置はグリッドのように構成されている。これによって 、カラムはアドレスＡ、Ｂ、Ｃ，Ｄ、Ｅ・・・に、またロウはアドレスａ、ｂ、 ｃ、ｄ、ｅにそれぞれ関連する。実際的な理由から、ブロックアドレスＡａから Ｅｅを有する２５個のストレージブロックの内容のみを示す。

共通記憶装置２７のストレージブロックの内容はこれまでに説明したように中間 的に記憶されたセルＺを形成するか、あるいは内容が空きである。他の場合、す なわち、セルＺが記憶されている場合、ブロックは２（セルを表わす）、連続番 号１，２．３・・・をはしめギリシャ文字α、β、δ、μが付される。ギリシャ 文字のα、Ｂ、δ、μは各セル２が伝送されるべき引出し線１２に対応している 。

この連続番号はセル２が共通記憶装置２７に薔き込まれ、引出し線１２によって 記・ツされた古い順を示している。このようにして、伝送されるのを待機してい るセルＺは各引出し線１２（ａ、　β、δ、ＬＬ）についてキューを形成してい る。キューの古い順は連続番号によってわかる。加つるに、多数の空き場所があ る。これは空き（すなわち、利用可能な）ストレージブロックの数を表わしてい る。

図６は問題の特定時刻における共通記゛ｍ装置２７中の空き場所Ｏおよび記憶さ れたセル２をキューとして示している。空き場所Ｏのキューは１２個の空き場所 ０１〜０１２から成り、０１は「最も古い］空き場所であり、キューのヘッドＨ を形成しており、０１２は「最も新しい」空き場所でありキューのテイル丁を形 成している。

空き場所のあるアドレスは空き場所の左側に示されている。より詳しく説明する と、空き場所Ｏのキューは共通記−１！装置２７のストレージブロックが空いて おり、その順位が使用可能状態にあることを示している。横線より下に位置する １３番目の空き場ＰＦＩＯ１３はこの状態にあるとは考えられない。

共通記・１装置２７から引出し線αへ伝送されるべきセルＺのキューは三つのセ ルＺα１〜Ｚα３から成る。引出し線δのキューは七つのセル２δ１〜Ｚδ７（ 横線より下の８番目のセルＺδ８は存在しているものとはまだ考えられていない ）を有し、引出し線μのキューは単一セルＺｕｌを有している。いずれのキュー においても最も小さい順位番号（最も古いセル）はヘッド８を表わし、最も大き い順位番号（ｉ＆も新しいセル）はテイルＴを表わす。

セル２が記憶されているか、または空きである共通記憶装置２７のストレージブ ロックに関連するアドレスＡａからＥｅはキュー内のセルの左側に示される。

ストレージブロックはセルＺを含んでいるか空きである。全てのキューは図５に 示す実施例の２５のストレージブロック、すなわち共通記・型装置２７のいずれ かのストレージブロックに対応している。伝送されるのを待っているセル（Ｚα １〜Ｚａ３．Ｚβ１〜２β２．Ｚδ１〜２δ７，２μｍ）かまたはストレージブ ロックが空きであるかである。この、点で、キューα、β、δ、μにおいて、最 も小さい順位番号の各セル（すなわち、セル２α１．　ＺＢｌ、Ｚδ１および２ μｍ）は既に伝送されるようになっていることに（これについては後述するので ）注意すべきである。すなわち、単一セルＺμｍのあるキューμが空きというこ とになる。従って、このキューが共通記憶装置２７に伝送されていないセルＺを 有しているものに対応する。

図７は図６の状態に対応するＰ−ストア４５内の関連するリストを示す。このリ ストの要素（右側列）はＰ−ストア４５の記′！場所に記・ｊ！されているアト １／スＡａからＥｅであり、Ｐ−ストアの記・！場所のアドレスＡａ−Ｅｅは左 側列に示されている。これらのアドレスは共通記憶装置２７のストレージブロッ ク内の関連するセルＺのアドレスと同じである（図６）。

従って、アドレスは一連の区別可能なアドレスの３倍が現われる。すなわち、第 １に共通記・！装置２７のストレージブロックのアドレスとして、第２にＰ−ス トア４５の記憶場所として、および第３に５Ｐ−ストア４５の記憶場所の容Ｉと してである。

Ｐ−ストア４５において、記憶場所の容量は基本的に関連するアドレスと決し７ て同じにならないことに注意しなければならない。このようにして、全ての記憶 場所の容量が各リスｈｏ、ａ、　β、δ、μの次の各関連要素が記憶されたアド レスを示すことになる。従って、Ｐ−ストア４５のリストは各シーケンスを独占 的に設定するポインターのリストになる。

Ｐ−ストア４５中のリストのどの要素がヘッドＨまたはティルＴになるかという 情報はＰ−ストア４５には含まれていない。むしろ、この情報はＨ−ストアまた はＴ−ストアのそれぞれに入っている。従って、三つのストア４１，４３．４５ は一緒にＰ−ストア４５中のリストに関する完全な情報を得るのに必要とされる 。

共通記憶装置２７のキューがそのアドレスによってＰ−ストア４５中のリストに よって関連付けられているので、三つのストア４１，４３．４５中の情報はキュ ー中のシーケンスに関する情報も備えている。従って、Ｐ−ストア４５の内容は 入来セルが中間的に記憶されているのは共通記憶装置２７のどのブロックであり 、どのような順序で、かつ、どの引出し線１２かを示しており、再び伝送される ことになる。

図５の実施例として既に示したように図８は共通記憶装置２７からのセルＺが伝 送されるときの工程を示している。さらに、これまでに説明した共通記１！ｉ装 置２７および各ストア４１，４３．４５も全て示している。区５の例における全 ての５番目の記・１場所が対応するＨ−ストア４１およびＴ−ストア４３に示さ れている。これらの記′ｌ場所のアドレスａ、β、δ、Ｕが対応する引出し線１ ２（α、β、δ、ＬＩ）に連絡されている。シーケンサ３８（図２および図３） が■（−ス１−アのこの瞬間で矢印８０で示したようにアドレスδにある記憶場 所を指定している。

読み出し工程の始めにおいては、記・邑場所δの実際の内容はアドレスＤａであ る。このアドレスはＨ−ストアから読み取れられ（矢印８１）、Ｐ−ス１−ア４ ５だけでなくＴ−ストア４３にも伝送される。Ｔ−ストア４３において、記憶場 所０　（Ｃｅ）の現内容がここでＤｃに書き換えられる。これは現テイル要素Ｃ ｅのアドレスがＤｃに置き換えられたことを意味する。空き場所のリストの新し いテ、イル要素がこれでアドレスＤｃになる。書き換えがなされる前に、最初の テイル要素ＣｅがＰ−ストア４５中の関連する記憶場所Ｃｅを選択するのに用い られる（矢印８２）、新しいアドレスＤＣがこの記憶場所の内容として記憶され る。最終的に、Ｐ−ストア４５の記憶場所Ｄｃが選択され（矢印８５）、この内 容（アドレスＡｅ）が現アドレスＤｃに代えてＨ−ストア４１の記憶場所δに書 き換えられる（矢印８３）。これと同時に、新しいアドレスＡｅが共通記憶装置 ２７のアドレスとしてここに伝送される。これによって共通記憶装置２７の関連 するブロックが選択され、その内容、すなわちセルＺδ２が引出し線１２のライ ンδに伝送される（矢印８４）。

以上の工程を経て、ラインδ上の２番目に古いセルであるＺδ２が所望通りに伝 送される。これによって、共通記憶装置２７のブロックＤｃが自由になる。ＤＣ が新しいテイルＴのアドレス、すなわち、Ｔ−ストア４３の空き場所のリスト中 の要素０１３（図５）として、マークされたことになる。さらに、ＡｅがＨ−ス トアのりストδの新しいヘッドＨとしてマークされたことになる。

ここで、シーケンサ３８がＨ−ストア４１の次の記憶場所に進行し、リストが存 在している間、同じ工程、しかしここでは引出し線１２のリストμおよびライン μにつき実行される。しかし、選択された例に基づいているが、リストμのヘッ ドとテイルが一致している場合でなく、新しくできた空きセルが引出し線μ（１ ２）に伝送される場合である。

図８に示したのと同様にして、図９は入来するセル２が共通記１！装置２７に記 憶されるときの工程を示す。この例において、このセルは後はど引出し線δに伝 送されるべきものである。この場合、アドレス読出しユニット３３が、リストδ の処理されるべき入力ロジックを（入力４６を介して）形成する。その後、入力 ロジック４８がＨ−ストア４１中の空き場所０のリストのヘッドが引き出される ように準備する。このヘッドはアドレスＡａを含んでおり、これが４回使用され る。最初の使用は、入来するセルＺδ８が記憶されるべき共通記’ＦＮ　装置２ ７中のブロックのアドレスを示すものである。これは上述したように、アドレス Ａａにおけるストレージブロックである。ここでセル２δ８がキューδの新しい テールを形成する（図６）。これによって、空き場所Ｏのキューの現ヘッド０１ が使用され、また、新しいヘッド０２（アドレスＢａを有するストレージブロッ ク）に取り換えられる。

第２の使用はＴ−ストア４３で行われる。記・１場所δにおいて、記憶されたア トＬ／スＥｄが読み出される。このアドレスはＰ−ストア４５中の関連する記憶 場所を表わし、ここにアドレスＡａが書き込まれる（矢印９２）。

第３の使用に関し、アドレスＡａがＴ−ストア４３の記憶場所δの新しい内容と して書き込みされ、これによって現内容Ｅｄがオーバーライドされる。

アドレスＡａの第４の使用は記憶場所Ａａの選択のためにＰ−ストア４５中で行 なわれ、Ｈ−ストア４１の記憶場所Ｏの新しい内容Ｂａとして記憶されるべく次 のアドレス（この場合Ｂａ）に読み込まれる（矢印９３）。

以上の工程を経て、所望通り新しいセル２６８が共通記憶装置２７に書き込まれ 、ここで占有されたブロックＡａがテイル要素２δ８としてキューδに付加され る。また、空き場所０のキューがそのヘッド要素Ａａによって短縮され、これに よってＢａが新しいヘッドになる。これらの工程もシーケンサ３８によって制御 される。

これまで説明した制御ユニット３５は構成するのが簡単である。共通記憶装置２ ７はセル２の中間記憶装置として独占的に作用するので、記憶装置の物理的な理 解と関係なくはっきりした基本的な機能を有している。例外なく、全てのストレ ージブロックはいずれのキューとしても任意に使用できる。空き場所のみのキュ ーは各々単一ストレージブロックを占有している。このようにして、共通記憶装 置２７は非常に有効的に使用される。

共通記憶装置２７と関係なく、Ｐ−ストア４５、Ｈ−ストア４１およびＴ−スト ア４３は共通記憶装置のストレージブロックの制御部としての働きをする。この 目的のために形成されたりストＯ，ａ、β、δ、μは再び共通記憶装置中でキュ ーのイメージになる。この目的のために単一の記憶場所がどのストア４１，４３ ．４５にも備えられているので新しいキューは容易に初期化される。さらに、Ｐ −ストア４５には、共通記憶装置２７に影響を及ぼすことなしに、例えばチェッ クの目的で、または試験のためにモニタロジック７１を介していつでもアクセス することができる。また、現時点のキューは妨害のある場合に、例えば別の経路 で伝送する目的で互いに単に接続が可能である。

制御ユニット３５はシーケンサ３８と協同動作する。このようにして、各動作工 程はセレクタのように非常に簡単で連続して制御されトリガまたは切り換えられ る。結局、制御ユニット３５は簡単な態様で迅速に動作し、これによって記憶機 能と制御機能が分離される。

概して、基本的にはセル２が共通記憶装置２７に記憶されている間、Ｐ−ストア ４５中の空き場所０のキューはその各テイル要素およびキューα、β、δ、ＬＬ によって短縮され、そのキューに関連するセルが新しいヘッド要素によって拡大 される。これとは逆に、セルの共通記憶装置への伝送は一つの要素と、セルと関 連するキューα、β、δ、μの対応する短縮によって空き場所Ｏのキューが拡大 される。

リストが単一要素のみを含み、従って、リストのヘッドＨおよびテイルＴが同じ アドレスを有している場合、リストはコンパレータ５９（図３）によって検知可 能で、関連するキューが空きであると考えらねる。この場合、空きセルが各関連 する引出し線１２に伝送される。一方、入来する空きセルがアドレス読取りユニ ット３３（図２）によって阻止され削除される。従って、Ｐ−ストア４５および 共通記憶装置２７は種々のリストまたはキューの必要条件に基づいて任意にかつ 、完全に融通性のある方法で区切られる。、最も極端な場合、Ｐ−ストア全体が 単一のリストによって占有されるか、またはそれぞれ共通記憶表！２７が単一の キューから構成できる。

空き場所Ｏにリストに関し、（図８を用いて説明したように）セルＺがそねぞれ 伝送されるときにＨ−ストアの記憶場所ａ、Ｂ、　δ、またはμに記憶された現 時点のアドレスは共通記憶装置２７における選択には用いないで、むしろ新しく 記゛！されたアドレスとなる。

リストをともかく作成するために、記・！場所に対応する数を初期化するために Ｐ−ストア４５に備えておくことが必要である。こねら各記憶場所はりストα。

β、δ、Ｈに対して始動要素を形成する。残りの記憶場所は空き場所のリスト用 に待機している。制御ユニット３５はその始動状態を作るために前述のモニタロ ジック７１　（図３）を用いる。かなり多くの他の形態もアウトラインの付けら れた好ましい形態の代わりにすることができる。

これまでに説明してきた構成は、全て単独の一様の優先順位を有するセル２と独 占的に動作する。従って、これら全てのセル２は同等に処理される。以後、この 原理は優先標識、例えば「ノーマル」、　「アージエント」及び［ベリーアージ ェント」を意味する標識Ｉ、ＩＩ、ＩＩＩをセルＺの現ヘッドに付加して拡大す る。概して、これは識別可能な優先順位の数ｐを予想することを意味する。

優先種ｍＩ、　ＩＩ、　ＩＩＩが付加されているために、どのセルＺもここでは 引出し線１２と開運しているだけでなく、各優先順位とも関連している。このよ うにして、共通記憶装置２７において、セル２のキューの競い合いが生じ、キュ ーが同じ引出し線１２に伝送され、これによって先入れ／先出しくＦＩＦＯ）の 原理が部分的に破られることになる。

これまでに説明したように、競合し合っているキューがＰ−ストア４５中の競合 リストで相手を見つける。この点において、Ｐ−ストア４５はどのようにも変更 してはいけない。しかし、Ｈ−ストア４１およびＴ−ストア４３をどの引出し線 にも単一の記憶場所と関連するだけでなく、許容できればできるだけの例えば三 つの優先順位Ｉ、　ＩＴ、　ＩＩＩをもたせるように拡大する必要がある。図５ 〜図９で説明したと同じ説明を用いて、これらの記憶場所には標識α工、αＵ、 αＩＩ１．　Ｂ工、β■・・・１μｍが与えられる。従って、前回［４＋１］　 リストのα、β、δ。

μ＋０の代わりに今回［（４Ｘ３）＋１］　リストが示される。

リストを共通記憶装置２７に入来するセルＺの記憶を変更する方法および手段は 前述したとまったく同じであるが、各優先標識Ｉ、ｎ、ＩＩＩの検討のみ異なる 。

一方、共通記・型装置２７から記憶されたセルＺを読み取る方法は、ある種の変 更を必要とし、実際に、全ての引出し線１２につき周期的な検討中、各々競合し 合うどのキューを一つのセルＺによって短縮する必要があるかチェックしなけれ ばならない。この点に関し、（−例として引出し線δを用いると）次の可能性が 考えられる。

全てのリストδ工、δ■、δｍが空きの場合、一つの空きセルが伝送される。

リストδ■、δ］、δｍのうちの一つのみが要素を含んでいる場合、関連する「 最も古い」セルＺδが共通記憶装置２７から読み取られて伝送される。

リストδ工、δ■、δｍのうち二つあるいは三つが要素を含んでいる場合、［最 も古い」セル２が、最も早い優先順位Ｉ、ＩＩ、ｍを有するリストと関連するキ ューから伝送される。

区３，４に示した優先ロジックは必要とされる可能性をモニタし、がっ、読み取 り工程の関連した制御を実行する。図１０はこのロジック７３のブロック図を示 す。このブロック図は各予想優先順位Ｉ、　ＩＩ、　ＩＩＩの記憶水準を含んで いる特別アドレス可能な読取り／書込み記憶装置７４からなる。アドレスの数は 引出し線１２の数に対応している。記憶水準の一つにおける任意のアドレスのた めのストア容量は、対応する引出し線１２のためのリストであるかどうが、また 対応する優先順位が空きであるかどうかを示す。

全ての要素のリストへの挿入またはそのリストからの除去（空き場所０のリスト は除外する）された後、このリフトのヘッドＨおよびテイルＴがコンパレータ５ ９（図３）で比較される。この結果がエキストラストア７４の記憶場所に、その アドレスにおいて、各引出し線と対応する優先順位を有する水準に書き込まれる 。コンパレータ５９からの各比較信号が入カフ６と一方向入力素子（バッファ） ７７を介して入ってくる。

引出し線１２に適した最も早い優先順位で非空きリストの選択がそのアドレス、 例えば６ｍをエキストラストア７４のすべての水準に付けることによって実行さ れ、これと並行して関連する順位が読み取られる。次に、優先エンコーダ７５が 対応する優先順位１．ｎ、ＩＩＩを決定し、引出し線の確認符号（ａ、β、δ、 μ）が正しい対応リストを決定する。

説明した優先ロジック７３は、優先順位Ｉ、　ＩＴ、　ＩＩＩが存在しない場合 を確実にする処理時間がもはやないように比較的少ない努力と研究ですむことで ある。従って、ＡＴＭノードは優先順位の有無にかかわらず迅速に動作可能であ る。

本発明に間する制御ユニット３５のさらなる拡張は、マルチカースト機構である 。この機構は数本の引出し線１２上に一つずつ同様のセルを正確に伝送すること である。もちろん、特定の引出し線を予め決定しておくことができる。この拡張 は例えばテレビジョン画像の伝送に対して重要であり、かつ、これまでに説明し た優先ロジック７３によって各々処理された高い優先順位を有している。

図１１はマルチカーストロシック９４のブロック図を示す。このロジックは付加 的なアドレス可能な読取り／書込みストア９５がら成り、以後デスティネーショ ンストアという。このデスティネーションストア９５はＰ−ストア４５と並列配 置されており、後者と同等のアドレス範囲を有している。

デスティネーションストア９５に関連し、引出し線１２の表が役に立つ。さらに 、この表の各要素に対し、デスティネーションストア９５は、ｒビットの長さを 有する関連するデスティネーションワードＤである内容を備えている。ワードＤ の各ビットは各マルチカーストセルＺがこの番号を有する各引出し線１２上に伝 送されるべきか否かを表示する。同時に、キューからの全てのマルチカーストセ ルＺは、Ｐ−ストア４５中のマルチカーストリストに関連している。

デスティネーションワードＤがアドレス読取りユニット３３（図２）によって、 マルチカーストセルのリスト番号とともに制御ユニット３５に通される。

マルチカーストセルが決して空きでないときに、最も古いマルチカーストセルの デスティネーションワードＤがセル周期の始めにおいてシフトレジスタ９６に書 き込まれる。このデスティネーションワードＤの各ビットは、各引出し線１２に 対しマルチカーストセルが優先ストア７４（図１０）がらの情報とともに伝送さ れるか否かという情報が、優先エンコーダ７５に供給されるようにして選択され る。このエンコーダにおいて情報が、最も高い優先順位Ｉ、　ＩＩ、　ＩＩＩで 処理される。

同じ情報が共通記憶装置２７に供給され、ここで、マルチカーストセルおよび引 出し線１２のためのノーマルヘッダＨとスペッシャルヘッダ間で選択可能である 。

マルチカースト装置は、全ての引出し線１２上に並行して各々伝送されるいわゆ るブロードカーストセルＲによってブロードカースト装置に拡張または補完され る。このため、この各ブロードカーストセルの記憶につき、各共通記憶装置２７ に一つの単一ブロックを備えることを要するだけである。

本発明に関する制御ユニット３５は次の特徴および利点を有している。

その動作は第１の複数ｎの引入れ線１１と無関係であり、かつ、第２の複数ｍの 引出し線１２を適当に調節するのが容易である。この点に関し、Ｈ−ストア４１ およびＴ−ストア４３の記憶場所の数が簡単に変更される。これはソフトウェア によって、シーケンサ３８あるいはストア４１．４３と関連するポインタコント ローラを介して簡単に実行できる。

Ｐ−ストア４５に収容されたリスト数だけでなくＨ−ストア４１およびＴ−スト ア４３にある記憶場所の数はごく僅がから約４０までの範囲とすることができ、 これによってこの数は必要とされ、かつ、技術的に有効な操作速度によってのみ 制限される。

制御ユニット３５は共通記憶装置２７のあらゆるサイズに容易に調節可能であり 、多分５０から数１００ブロツクの範囲が可能である。

さらに、重要なことは制御ユニット３５が説明は省略するが論理ユニットによっ て必要条件を満たすように構成され調節されることである。この点は自由に選択 できる初期設定のタイプに対して特に適用される。

Ｈ−ストア４１、Ｔ−ストア４３およびＰ−ストア４５は市販のタイプのアドレ ス可能な読取り／書込みスト乙好ましくはＲＡＭ　（ランダム・アクセス・メモ リ）である。しかし他のタイプのストアも例えば他の半導体ストアまたは他のス トアも考えられる。

Ｈ−ストア４１およびＴ−ストア４３は引出し線１２に関係するりストα、Ｂ、 δ、ＵのヘッドＨまたはティルＴのみを含むが、空き場所０のリストは含まない ように配備されている。従って、空き場所Ｏのリストは別々の付加的なストアに 配置でき実用的な理由で有利である。

三つのストア４１，４３，４５は−っの単独ストアとして構成でき、その記憶場 所を三つのドメインを形成してあたかも三つのストア４１，４３．４５があるか のように配置できる。

制御ユニット３５は主としてセル２の長さおよび共通記憶装置２７のためのアド レスとは無関係である。しかし、制御ユニットは非常に早く操作されなければな らないので、図８８よび図９で説明したすべての操作工程およびできる限り他の 操作も一つのセル２の伝送時間内に完了させる必要がある。さらに、この点と、 この時間的事実を考膚して、一つのセルを共通記憶装置２７に記憶することと、 この記憶装置から他のセルを伝送することを同時に実行する必要がある。規程、 ２〜３μｓが一つのセルの伝送時間に対するおおよその値として確認されている 。

既に確認してきた制御ユニット３５の利点以外に、制御ユニット３５がＡＴＭノ ード１０を機能させる特別な融通性をとりわけ再び説明しておく必要がある。

このように、「セルＺをそのデスティネーションに進行させる」という主たる機 能だけでなく、次の機能も備えている。すなわち、優先順位に基づいてセルを明 確な早さで進行させる機能、セルを数本の引出し線１２へ「並行」して進行させ る機能、妨害の場合にセルを転換させる機能、優先順位を変更させる機能、新し いリストを設けるかまたは既存のリストを除去する機能、および（または）いつ でも全ての、または特定の選択可能なリストをモニタし、チェックする能力をも たせる機能である。

Ｆｉ９．Ｉ Ｆｉｇ、　２ Ｚｅｎｔｒａｌｓｐｅｉｃｈｅｒ　２７Ｆｉｇ、　５ Ｚｅｎｔｒａｌｓｐｅｉｃｈｅｒ　２７Ｐ−８ｐｅｉｃｈｅｒ　４５ Ｆｉｇ、１０ Ｆｉｇ、１１ 要約書 ＡＴＭは広域通信（非対称転送モード）のための秘術として理解されるべきであ る。

ＡＴＭ−ノード（１０）の共通記憶装置（２７）の制御ユニット（３５）は主と して三つの読取り／書込みストア（４１，４３，４５）、入力ロジック（４８） 、バス／制御ロジック（５０）および任意のユニットをモニタし、初期設定する ためのモニタロジック（７１）を有している。シーケンサ（３８）が全てのユニ ットをトリガする。

第１読取り／書込みストア（４１）および第２読取り／書込みストア（４３）の 記憶場所の数は、それぞれ関連する共通記憶装置からの引出し線（１２）の数に 対応している。さらに、各々別の単一の付加的ストアがある。第３読取り／書込 みストア（４５）の記憶場所は共通記憶装置（２７）の記憶場所に対応している 。

三つの読取り／書込みストア（４１，４３，４５）は互いに共通記憶装置（２７ ）の占有状態に関する完全な情報を含んでいる。これらのストアは連結されたリ ストのようにして協同動作する。

国際調査報告 国際調査報告

Claims (1)

1. 【特許請求の範囲】 １．ＡＴＭノード（１０）の共通記憶装置（２７）を制御する制御ユニット（３ ５）であって、 前記ＡＴＭノード（１０）が第１の複数（ｎ）の引入れ線（１１）と第２の複数 （ｍ）の引出し線（１２）に接続されており、前記ＡＴＭノード（１０）が均一 長さと均一構造をなすアドレスの付されたセル（Ｚ）を連続して受信し、進行さ せる働きをし、セル（Ｚ）が引入れ線（１１）に入来し、引出し線１１２）から 伝送され、さらにセル（Ｚ）には関連する識別可能な優先順位Ｉ，ＩＩ，ＩＩＩ の番号（ｐ）が付されており、 共通記憶装置（２７）は引出し線（１２）の一つから伝送されるべき全てのセル （Ｚ）の中間記憶装置の働きをし、共通記憶装置（２７〕が第３の複数（ｋ）の ストレージブロックを有しており、ストレージブロックがアドレスによって各々 選択可能であり、かつ、セル（Ｚ）を受信する働きをし、 前記制御ユニット（３５）がシーケンサ（３８）をはじめとして、管理、制御手 段から成り、前記共通記憶装置（２７）のストレージブロックが管理されセルが 前記ストレージブロックに連続して読み込まれ、かつ、読み出されるのを制御す る手助けをするように構成されており、前記管理、制御手段が少なくともアドレ ス可能な読取り／書込みストア（４１，４３，４５）と、これに関した少なくと もモニタロジック（７１）と、入力ロジック（４８）と、バス／制御ロジック（ ５０）とコンパレータ（４９）とから成り； 前記読取り／書込みストア（４１，４３，４５）が第３の複数（ｋ）の一つに、 第２の複数（ｍ）に数（ｐ）を掛けたものの２倍を足し、記憶場所の二つの対応 する数字を足して構成されており；読取り／書込みストア（４１，４３，４５） のどの記憶場所もアドレスの各受信部によって構成されており； 数（ｐ）の掛けられた記憶場所の２倍の第２の複数（ｍ）が引出し線（１２）の 対に関連しており； 第３の複数（ｋ）の記憶場所が共通記憶場所（２７）のストレージブロックと関 連し； 二つの記憶場所が共通記憶装置（２７）の空きストレージブロックと関連してい ることを特徴とする。 ２．三つのアドレス可能な読取り／書込みストア（４１，４３，４５）が予想さ れ、第１読取り／書込みストア（４１）および第２読取り／書込みストア（４３ ）が同じように構成されており、両ストア（４１，４３）が第２の複数（ｍ）の 一つに数（ｐ）を掛けたものに記憶場所の一つの対応する数を足した数を有して おり、対の形で関連し、引出し線（１２；α，β，δ，μ）および優先順位（Ｉ ，ＩＩ，ＩＩＩ）さらに共通記憶装置（２７）の空きストレージブロックと関連 し、かつ、個々に制御可能であり；第３読取り／書込みストア（４５）が記憶場 所の第３の複数（ｋ）の対応する数の一つを有しており、これらの記憶場所が共 通記憶装置（２７）のストレージブロックとして正確にアドレスされることを特 徴とする請求項１に記載の制御ユニット（３５）。 ３．引出し線（１２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）に関連する第１読取 り／書込みストア（４１〕の記憶場所の内容がアドレスであり、これがリスト（ α，β，δ，μ）の始まりを形成し、引出し線（１２）および優先順位（Ｉ，Ｉ Ｉ，ＩＩＩ）にそれぞれ関連しており； 共通記憶装置（２７）の空きストレージブロックに関連する第１読取り／書込み ストア（４１）の記憶場所（０）の内容がアドレスであり、これが第３読取り／ 書込みストア（４５）中の利用可能な記憶場所のリストの始まりを形成しており ； 引出し線（１２）及び優先順位（Ｉ，ＩＩ，ＩＩＩ）に関連する第２読取り／書 込みストア（４３）の記憶場所の内容がアドレスされ、これが任意のリストの終 わりを形成し、引出し線（１２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）に関連し ており； 空きストレージブロックに関連する第２読取り／書込みストア（４３）の記憶場 所の内容がアドレスであり、これが第３読取り／書込みストア（４５）中の利用 可能な記憶場所の任意のリストを形成しており；第３読取り／書込みストア（４ ５）の占有された記憶場所の内容がアドレスであり、これが協同し、引出し線（ １２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）と関連して、いずれのアドレスにお いても第３読取り／書込みストア（４５）の記憶場所が、記憶された各リストの 次の各要素を表わすような方法で任意のリストを形成し； 第３読取り／書込みストア（４５）の利用可能な記憶場所の内容がアドレスであ り、これが協同し、いずれのアドレスにおいても第３読取り／書込みストア（４ ５）の記憶場所が、記憶されたリストの次の各要素を表わすような方法で、かつ 、全体として、全てのリストがその要素と協同して第３読取り／書込みストア（ ４５）の全ての記憶場所を占有するようにして、利用可能な記憶場所の任意のリ スト（０）を形成することを特徴とする請求項２に記載の制御ユニット（３５） 。 ４．第３読取り／書込みストア（４５）の記憶場所中の任意のアドレスに記憶さ れ、引出し線（１２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）に関連するリスト（ α，β，δ，μ）に関係するいずれの要素もセル（Ｚ）に関連し、これが共通記 憶装置（２７）の関連するストレージブロック中の同じアドレスに記憶され、か つ、各引出し線（１２）に伝送されるべく考慮されており；第３読取り／書込み ストア（４５）の利用可能な記憶場所のリスト（０）のいずれの要素も共通記憶 装置（２７）の空きストレージブロックに関連していることを特徴とする請求項 ３に記載の制御ユニット（３５）。 ５．引き出し線（１２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）に関連する第１読 取り／書込みストア（４１）および第２読取り／書込みストア（４３）の記憶場 所を決定するポインウコントローラが考慮された請求項１に記載の制御ユニット （３５）。 ６．読取り／書込みストア（４１，４３，４５）がＲＡＭ（ランダム・アクセス メモリ）である請求項１に記載の制御ユニット（３５）。 ７．バス／制御ロジック（５０）が、トランシーバ（５３，５５，５７）等の制 御ロジックおよびマルチプレクサ（５１）を介して他の任意のユニットに接続さ れた少なくとも一つのバス（６７，６８，６９）を有していることを特徴とする 請求項１に記載の制御ユニット（３５）。 ８．請求項１に記載の制御ユニット（３５）であって、前記制御ユニット（３５ ）を共通記憶装置（２７）に接続するアウトプット（５２）を備えており、前記 アウトプット（５２）の前段に少なくとも一つのアウトプットバッファ（６１， ６３）を有してし、ることを特徴とする。 ９．コンパレータ（５９）を介して第１読取り／書込みストア（４１）および第 ２読取り／書込みストア（４３）に接続し、さらにバス／制御ロジック（５０） に接続することが考慮された優先ロジック（７３）が設けられ；前記優先ロジッ ク（７３）が識別可能な優先順位の数（ｐ）としてのアクセス（エキストラ）ス トア（７４）の対応する数および優先エンコーダ（７５）を有していることを特 徴とする請求項１に記載の制御ユニット（３５）。 １０．第３読取り／書込みストア（４５）および優先ロジック（７３）に接続さ れるように考慮されたマルチカーストロジック（９４）が設けられており；前記 マルチカーストロジック（９４）がデスティネーションストア（９５）およびシ フトレジスタ（９６）を有していることを特徴とする請求項１に記載の制御ユニ ット（３５）。 １１．ＡＴＭ−ノード（１０）を動作させる方法であって、前記ＡＴＭ−ノード （１０）によって第１の複数（ｎ）の引入れ線（１１）から来る均一長さで均一 構成のアドレスーラベル付きセル（Ｚ）を連続して受信し、この受信されたセル （Ｚ）をタイムマルチプレキシンクで一定順序付けし、セル（Ｚ）のアドレスを 読み取り、さらに前記セル（Ｚ）を共通記憶装置（２７）のストレージブロック に記憶する工程と；前記ＡＴＭ−ノード（１０）によって前記共通記憶装置（２ ７）からセル（Ｚ）を連続して読み取り、アドレスと優先順位（Ｉ，ＩＩ，ＩＩ Ｉ）に基づいて、各セル（Ｚ）を第２の複数（ｍ）に属している関連する引出し 線（１２）に伝送する工程と； 引出し線（１２）および優先順位（Ｉ，ＩＩ，ＩＩＩ）に各々関連し、その要素 が各々同じ優先順位（Ｉ，ＩＩ，ＩＩＩ）のセル（Ｚ）が共通記憶装置（２７） に記憶され、かつ、各引出し線（１２）に伝送されるべく考慮されているキュー を形成する工程と； から成り， いずれのキューおよび全ての共通記憶装置（２７）の空きストレージブロックが 規定されたヘッド要素とテイル要素を備えたりスト（α，β，δ，μ，０）に各 々関連しており、これによって、リスト（α，β，δ，μ，０）の要素がアドレ スされ、かつ、全てのリスト（α，β，δ，μ，０）の全ての要素の総合したも のが一定であり、共通記憶装置（２７）のストレージブロックの数（ｋ）に等し く； 共通記憶装置（２７）へセル（Ｚ）を記憶させることにより、空きストレッジブ ロックに関連するリスト（Ｏ）の現ヘッド要素が各セル（Ｚ）が属するキューに 関連したリスト（α．β，δ．μ）の新しいテイル要素（α，β，δ，μ）とし て付加され； 共通記憶装置（２７）中のキューからセル（Ｚ）を読み取ることにより、この各 キューに関連するリスト（α，β，δ，μ）の現ヘッド要素がそれぞれ空きスト レージブロックに関連するリスト（Ｏ）の新しいテイル要素として付加されるこ とを特徴とする。 １２．リスト（α，β，δ，μ，０）のすべての要素がアドレスに関連しており 、これによって全てのアドレスが別々であり、かつ、基本的にどの要素もその要 素の有している同じアドレスを有していないことを特徴とする請求項１１に記載 の方法。 １３．リスト（α，β，δ，μ，０）の要素の総数に等しく、かつ、共通記憶装 置（２７）のストレージブロックのアドレスの総数に等しいことを特徴とする請 求項１２に記載の方法。 １４．引出し線（１２）に関連するリスト（α，β，δ，μ）が正確に周期的に 選択され； 同じ引き出し線（１２）に関連する全てのリスト（α，β，δ，μ）から最も早 い優先順位（Ｉ，ＩＩ，ＩＩＩ）にある非空きリストが選択され；各リストのヘ ッド要素が、その記憶されたセル（Ｚ）が次に読み取られるべき共通記憶装置（ ２７）のストレージブロックを表わしていることを特徴とする請求項１１に記載 の方法。