(57)【特許請求の範囲】
【請求項１】
セルを格納するセルバッファメモリと、入力されたセルの格納要求と前記セルの行き先である出力ポートを示す行き先情報とを発生し、前記セルを出力する際に出力要求及び行き先情報を発生するセル管理手段とを具備し、前記セルバッファメモリは、前記格納要求に応じたバッファアドレスにより、前記セルを書き込み、前記出力要求に応じたバッファアドレスにより、前記セルを読み出して、前記セル管理手段に送り、前記セル管理手段は、前記セルを受け取ると、行き先に応じて前記セルを前記出力ポートに送るＡＴＭスイッチ回路において、
前記セルバッファメモリの空きアドレスを管理し、前記セル管理手段から前記格納要求を受け取ると、空きアドレスをバッファアドレスとして前記セルバッファメモリに出力する空きアドレス管理手段と、
前記バッファアドレスを格納するＬ（Ｌは任意の自然数、以下において同じ）個の格納領域を１つのページとし、前記ページを繋げて形成すると共に前記出力ポートにそれぞれ対応するチェーン構造を用い、前記セル管理手段からの格納要求と前記空きアドレス管理手段からのバッファアドレスとを受け取ると、前記受け取ったバッファアドレスを前記チェーン構造のページの格納領域に順に格納し、前記セル管理手段から出力要求及び行き先情報を受け取ると、前記行き先情報に対応するチェーン構造のページの格納領域からバッファアドレスを順に読み出して、前記セルバッファメモリ及び前記空きアドレス管理手段に送るバッファアドレス管理手段とを備えてなることを特徴とするＡＴＭスイッチ回路。
【請求項２】
前記バッファアドレス管理手段は、
前記バッファアドレスを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成すると共に、前記出力ポートにそれぞれ対応するチェーン構造を用いて、前記空きアドレス管理手段からのバッファアドレスを格納するバッファアドレス格納部と、
前記バッファアドレス格納部のチェーン構造の最後尾にあるページの中で、最新のバッファアドレスを指し示すライトポインタと、前記チェーン構造の先頭にあるページの中で、最初のバッファアドレスを指し示すリードポインタとを格納するポインタ格納部と、
前記セル管理手段から格納要求及び行き先情報を受け取ると、前記ポインタ格納部から前記行き先情報に対応するライトポインタを読み出し、前記ライトポインタが指し示す該当出力ポート上の格納領域の次の格納領域に、前記空きアドレス管理手段からのバッファアドレスを格納し、前記セル管理手段から出力要求と行き先情報とを受け取ると、前記ポインタ格納部からリードポインタを読み出し、前記リードポインタが指し示す格納領域のバッファアドレスを前記セルバッファメモリと前記空きアドレス管理手段とに送る制御部とを備えてなることを特徴とする請求項１記載のＡＴＭスイッチ回路。
【請求項３】
入力されたセルの格納要求と前記セルの行き先の出力ポートを示す行き先情報とを発生する多重手段と、
前記セルを出力する際に出力要求及び行き先情報を発生する分離手段と、
前記セルを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成する共に前記出力ポートにそれぞれ対応するチェーン構造を用いて、前記多重手段からのセルを格納し、前記セルを読み出して前記分離手段に送るセルバッファメモリと、
前記多重手段から格納要求と行き先情報とを受け取ると、前記セルバッファメモリを指示して、前記行き先情報に対応するチェーン構造に、前記多重手段からのセルを順に格納する制御を行い、前記分離手段から出力要求と行き先情報とを受け取ると、前記セルバッファメモリを指示して、前記行き先情報に対応するチェーン構造から順にセルを読み出して前記分離手段に送る制御を行うセルバッファメモリ制御手段とを備えてなることを特徴とするＡＴＭスイッチ回路。
【請求項４】
前記セルバッファメモリ制御手段は、
前記セルバッファメモリのチェーン構造の最後尾にあるページの中で、最新のセルを指し示す書き込み用のバッファアドレスと、前記チェーン構造の先頭にあるページの中で、最初のセルを指し示す読み出し用のバッファアドレスとを格納するアドレス格納部と、
前記多重手段から格納要求及び行き先情報を受け取ると、前記アドレス格納部から前記行き先情報に対応する書き込み用のバッファアドレスを読み出し、前記書き込み用のバッファアドレスにより前記セルバッファメモリを制御し、前記分離手段から出力要求と行き先情報とを受け取ると、前記アドレス格納部から読み出し用のバッファアドレスを読み出し、前記読み出し用のバッファアドレスにより前記セルバッファメモリを制御する制御部とを備えてなることを特徴とする請求項３記載のＡＴＭスイッチ回路。
【請求項５】
セルを格納するセルバッファメモリと、入力されたセルの格納要求と前記セルの行き先である出カポートを示す行き先情報とを発生し、前記セルを出力する際に出力要求及び行き先情報を発生するセル管理手段とを制御して、前記セルバッファメモリが、前記格納要求に応じたバッファアドレスにより、前記セルを書き込み、前記出力要求に応じたバッファアドレスにより、前記セルを読み出して、前記セル管理手段に送り、前記セル管理手段が、前記セルを受け取ると、行き先に応じて前記セルを前記出力ポートに送るようにするＡＴＭスイッチ回路の制御方法において、
前記セルバッファメモリの空きアドレスを管理し、前記セル管理手段から前記格納要求を受け取ると、前記空きアドレスをバッファアドレスとして前記セルバッファメモリに出力する第１のステップと、
前記バッファアドレスを格納するＬ個の格納領域を１つのページとし、前記ぺージを繋げて形成する共に前記出カポートにそれぞれ対応するチェーン構造を用い、前記セル管理手段からの格納要求と前記第１のステップによるバッファアドレスとを受け取ると、前記受け取ったバッファアドレスを前記チェーン構造のページの格納領域に順に格納する第２のステップと、
前記セル管理手段から出力要求及び行き先情報を受け取ると、前記行き先情報に対応するチェーン構造のページの格納領域からバッファアドレスを順に読み出して、前記セルバッファメモリに送る第３のステップとを含み、
前記第３のステップにより読み出されたバッファアドレスを前記第１のステップで管理することを特徴とするＡＴＭスイッチ回路の制御方法。
【請求項６】
入力されたセルの格納要求と前記セルの行き先の出カポートを示す行き先情報とを発生する第１のステップと、
前記セルを出力する際に出力要求及び行き先情報を発生する第２のステップと、前記セルを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成する共に前記出カポートにそれぞれ対応するチェーン構造を用いて、前記第１のステップが処理するセルを格納し、前記セルを読み出して前記第２のステップに送る第３のステップと、
前記第１のステップによる格納要求と行き先情報とを受け取ると、前記行き先情報に対応するチェーン構造に、前記第１のステップが処理するセルを順に格納する第４のステップとを含み、
前記第２のステップによる出力要求と行き先情報とを受け取ると、前記行き先情報に対応するチェーン構造から順にセルを読み出し、前記セルに対して前記第２のステップを行うことを特徴とするＡＴＭスイッチ回路の制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ＡＴＭスイッチ回路に係り、詳しくは、ＡＴＭによるセルを扱うＡＴＭスイッチ回路に関する。
【０００２】
【従来の技術】
従来、非同期転送モード（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ、以下、ＡＴＭと記す）による伝送装置や交換機は、特開平６−６２０４１号公報に示すように、入力されたセルを一時的に蓄積し、同報通信などの際に、蓄積したセルを読み出して出力する。上記伝送装置や交換機等は、図４４に示すＡＴＭスイッチ回路を備えてなる。上記ＡＴＭスイッチ回路は、図４４に示すように、入力ポート１０１１〜１０１Ｎを経て入力されたセルを、多重部１０１が多重化して、セルバッファメモリ１０２に送る。セルバッファメモリ１０２は、空きアドレス管理メモリ１０７から与えられる空きアドレスに従って、上記入力されたセルを格納する。
【０００３】
書き込み制御部１０４は、多重部１０１からのセルのヘッダ部により、セルを出力する出力ポート１０３１〜１０３Ｎを調べる。この後、書き込み制御部１０４は、空きアドレス管理メモリ１０７に対して、セルを格納するための、空きアドレスの出力を要求する。また、書き込み制御部１０４は、該当するアドレスメモリに対して、空きアドレス管理メモリ１０７からの空きアドレスを格納するように指示する。
アドレスメモリ１０６１〜１０６Ｎは、ＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ−Ｆｉｒｓｔ−Ｏｕｔ）メモリである。アドレスメモリ１０６１〜１０６Ｎは、出力ポート１０３１〜１０３Ｎに対応して設けられている。そして、アドレスメモリ１０６１〜１０６Ｎは、書き込み制御部１０４からの指示により、空きアドレス管理メモリ１０７からの空きアドレスを格納する。空きアドレス管理メモリ１０７は、セルバッファメモリ１０２の空きアドレスを蓄積して管理する。上記空きアドレスは、読み出し制御部１０５が読み出しの指示を出したときに、上記指示に該当するアドレスメモリから出力されるアドレスである。
【０００４】
これらのアドレスメモリ１０６１〜１０６Ｎと空きアドレス管理メモリ１０７とにより、出力ポート１０３１〜１０３Ｎに出力されるセルのアドレスが、出力ポート１０３１〜１０３Ｎに対応して蓄積・管理される。そして、セルバッファメモリ１０２は、セルの出力時に、アドレスメモリ１０６１〜１０６Ｎが読み出し制御部１０５の指示で出力するアドレスに従って、格納しているセルを読み出して、分離部１０３に送る。分離部１０３は、セルバッファメモリ１０２からのセルを分離して、出力ポート１０３１〜１０３Ｎに送る。
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来技術には、次のような課題がある。すなわち、上記従来技術は、図４４に示すように、出力ポート１０３１〜１０３Ｎに対応してアドレスメモリ１０６１〜１０６Ｎを備えてなる。この結果、上記出力ポートの数が増えると、上記アドレスメモリの数の増加を伴うという課題が発生する。また、上記従来技術によるＡＴＭスイッチ回路を備えるシステムの運用状況により、セルが頻繁に送られて、使用頻度の多くなる出力ポートと、使用頻度の少ない出力ポートとが発生する。この場合、出力ポート１０３１〜１０３Ｎに対応してアドレスメモリ１０６１〜１０６Ｎを備える構成であると、使用頻度の少ない出力ポートに対応するアドレスメモリの使用効率が低下するという課題も発生する。
【０００６】
この発明は、上述の事情に鑑みてなされたもので、出力ポートが増えることにより発生する、アドレスメモリの増加を防ぎ、かつ、アドレスメモリの使用効率の低下を防止することができるＡＴＭスイッチ回路を提供することを目的としている。
【０００９】
【課題を解決するための手段】
請求項１記載の発明は、セルを格納するセルバッファメモリと、入力されたセルの格納要求と前記セルの行き先である出力ポートを示す行き先情報とを発生し、前記セルを出力する際に出力要求及び行き先情報を発生するセル管理手段とを具備し、前記セルバッファメモリは、前記格納要求に応じたバッファアドレスにより、前記セルを書き込み、前記出力要求に応じたバッファアドレスにより、前記セルを読み出して、前記セル管理手段に送り、前記セル管理手段は、前記セルを受け取ると、行き先に応じて前記セルを前記出力ポートに送るＡＴＭスイッチ回路に係り、前記セルバッファメモリの空きアドレスを管理し、前記セル管理手段から前記格納要求を受け取ると、空きアドレスをバッファアドレスとして前記セルバッファメモリに出力する空きアドレス管理手段と、前記バッファアドレスを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成すると共に前記出力ポートにそれぞれ対応するチェーン構造を用い、前記セル管理手段からの格納要求と前記空きアドレス管理手段からのバッファアドレスとを受け取ると、前記受け取ったバッファアドレスを前記チェーン構造のページの格納領域に順に格納し、前記セル管理手段から出力要求及び行き先情報を受け取ると、前記行き先情報に対応するチェーン構造のページの格納領域からバッファアドレスを順に読み出して、前記セルバッファメモリ及び前記空きアドレス管理手段に送るバッファアドレス管理手段とを備えてなることを特徴としている。
【００１０】
また、請求項２記載の発明は、請求項１記載のＡＴＭスイッチ回路に係り、前記バッファアドレス管理手段は、前記バッファアドレスを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成すると共に、前記出力ポートにそれぞれ対応するチェーン構造を用いて、前記空きアドレス管理手段からのバッファアドレスを格納するバッファアドレス格納部と、前記バッファアドレス格納部のチェーン構造の最後尾にあるページの中で、最新のバッファアドレスを指し示すライトポインタと、前記チェーン構造の先頭にあるページの中で、最初のバッファアドレスを指し示すリードポインタとを格納するポインタ格納部と、前記セル管理手段から格納要求及び行き先情報を受け取ると、前記ポインタ格納部から前記行き先情報に対応するライトポインタを読み出し、前記ライトポインタが指し示す該当出力ポート上の格納領域の次の格納領域に、前記空きアドレス管理手段からのバッファアドレスを格納し、前記セル管理手段から出力要求と行き先情報とを受け取ると、前記ポインタ格納部からリードポインタを読み出し、前記リードポインタが指し示す格納領域のバッファアドレスを前記セルバッファメモリと前記空きアドレス管理手段とに送る制御部とを備えてなることを特徴としている。
【００１１】
また、請求項３記載の発明に係るＡＴＭスイッチ回路は、入力されたセルの格納要求と前記セルの行き先の出力ポートを示す行き先情報とを発生する多重手段と、前記セルを出力する際に出力要求及び行き先情報を発生する分離手段と、前記セルを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成する共に前記出力ポートにそれぞれ対応するチェーン構造を用いて、前記多重手段からのセルを格納し、前記セルを読み出して前記分離手段に送るセルバッファメモリと、前記多重手段から格納要求と行き先情報とを受け取ると、前記セルバッファメモリを指示して、前記行き先情報に対応するチェーン構造に、前記多重手段からのセルを順に格納する制御を行い、前記分離手段から出力要求と行き先情報とを受け取ると、前記セルバッファメモリを指示して、前記行き先情報に対応するチェーン構造から順にセルを読み出して前記分離手段に送る制御を行うセルバッファメモリ制御手段とを備えてなることを特徴としている。
【００１２】
また、請求項４記載の発明は、請求項３記載のＡＴＭスイッチ回路に係り、前記セルバッファメモリ制御手段は、前記セルバッファメモリのチェーン構造の最後尾にあるページの中で、最新のセルを指し示す書き込み用のバッファアドレスと、前記チェーン構造の先頭にあるページの中で、最初のセルを指し示す読み出し用のバッファアドレスとを格納するアドレス格納部と、前記多重手段から格納要求及び行き先情報を受け取ると、前記アドレス格納部から前記行き先情報に対応する書き込み用のバッファアドレスを読み出し、前記書き込み用のバッファアドレスにより前記セルバッファメモリを制御し、前記分離手段から出力要求と行き先情報とを受け取ると、前記アドレス格納部から読み出し用のバッファアドレスを読み出し、前記読み出し用のバッファアドレスにより前記セルバッファメモリを制御する制御部とを備えてなることを特徴としている。
【００１４】
また、請求項５記載の発明は、セルを格納するセルバッファメモリと、入力されたセルの格納要求と前記セルの行き先である出カポートを示す行き先情報とを発生し、前記セルを出力する際に出力要求及び行き先情報を発生するセル管理手段とを制御して、前記セルバッファメモリが、前記格納要求に応じたバッファアドレスにより、前記セルを書き込み、前記出力要求に応じたバッファアドレスにより、前記セルを読み出して、前記セル管理手段に送り、前記セル管理手段が、前記セルを受け取ると、行き先に応じて前記セルを前記出力ポートに送るようにするＡＴＭスイッチ回路の制御方法に係り、前記セルバッファメモリの空きアドレスを管理し、前記セル管理手段から前記格納要求を受け取ると、前記空きアドレスをバッファアドレスとして前記セルバッファメモリに出力する第１のステップと、前記バッファアドレスを格納するＬ個の格納領域を１つのページとし、前記ぺージを繋げて形成する共に前記出カポートにそれぞれ対応するチェーン構造を用い、前記セル管理手段からの格納要求と前記第１のステップによるバッファアドレスとを受け取ると、前記受け取ったバッファアドレスを前記チェーン構造のページの格納領域に順に格納する第２のステップと、前記セル管理手段から出力要求及び行き先情報を受け取ると、前記行き先情報に対応するチェーン構造のページの格納領域からバッファアドレスを順に読み出して、前記セルバッファメモリに送る第３のステップとを含み、前記第３のステップにより読み出されたバッファアドレスを前記第１のステップで管理することを特徴としている。
【００１５】
また、請求項６記載の発明は、入力されたセルの格納要求と前記セルの行き先の出カポートを示す行き先情報とを発生する第１のステップと、前記セルを出力する際に出力要求及び行き先情報を発生する第２のステップと、前記セルを格納するＬ個の格納領域を１つのページとし、前記ページを繋げて形成する共に前記出カポートにそれぞれ対応するチェーン構造を用いて、前記第１のステップが処理するセルを格納し、前記セルを読み出して前記第２のステップに送る第３のステップと、前記第１のステップによる格納要求と行き先情報とを受け取ると、前記行き先情報に対応するチェーン構造に、前記第１のステップが処理するセルを順に格納する第４のステップとを含み、前記第２のステップによる出力要求と行き先情報とを受け取ると、行き先情報に対応するチェーン構造から順にセルを読み出し、前記セルに対して前記第２のステップを行うことを特徴としている。
【００１６】
【発明の実施の形態】
以下、図面を参照して、この発明の実施の形態について説明する。
◇参考例
図１は、この発明の参考例であるＡＴＭスイッチ回路の構成を概略示すブロック図、図２は、同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図、図３は、同ＡＴＭスイッチ回路のチェーン構造を説明する説明図、図４は、同ＡＴＭスイッチ回路のポインタ格納メモリの構成を示す構成図、図５は、同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャート、図６は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図７は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図８は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図９は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図１０は、同ＡＴＭスイッチ回路の制御部による、セル出力の処理を示すフローチャート、図１１は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図１２は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図１３は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図１４は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【００１７】
このＡＴＭスイッチ回路は、図１に示すように、多重部１、セルバッファメモリ２、分離部３、書き込み制御部４、読み出し制御部５、ポインタ格納メモリ６、制御部７、アドレス格納メモリ８及び空きアドレス管理メモリ９を備えてなっている。
多重部１は、入力ポート１１、１２、…、１Ｎからセルをそれぞれ受け取ると、上記セルを多重化し、この多重化したセルをセルバッファメモリ２に送る。
セルバッファメモリ２は、多重部１からセルを受け取ると共に、空きアドレス管理メモリ９から、書き込み用のバッファアドレスを受け取ると、上記バッファアドレスが指定する格納領域に上記セルを格納する。また、セルバッファメモリ２は、アドレス格納メモリ８から、読み出し用のバッファアドレスを受け取ると、上記バッファアドレスが指定する格納領域に格納されているセルを読み出して、上記セルを分離部３に出力する。
【００１８】
分離部３は、セルバッファメモリ２からセルを受け取ると、上記セルを分離する。この後、分離部３は、分離したセルを、出力ポート３１、３２、…、３Ｎの中の、該当する出力ポートに送る。
書き込み制御部４は、多重部１からセルが出力されるとき、上記セルのヘッダ部の情報から、上記セルの出力ポートを調べる。書き込み制御部４は、上記セルの出力ポートを示すポート信号及び上記セルの格納要求を制御部７に送る。この後、書き込み制御部４は、制御部７から格納許可を受け取ると、空きアドレス管理メモリ９に対してアドレス出力要求を送る。読み出し制御部５は、出力ポート３１、３２、…、３Ｎに対してセルを出力するとき、出力ポート３ｋとバッファアドレスの出力指示とを制御部７に送る。
【００１９】
空きアドレス管理メモリ９は、セルバッファメモリ２の空き領域のバッファアドレスを管理している。空きアドレス管理メモリ９は、書き込み制御部４からアドレス出力要求を受け取ると、空き領域のアドレスであるバッファアドレスを、セルバッファメモリ２及びアドレス格納メモリ８に送る。アドレス格納メモリ８は、図２に示すように、次ポインタ格納部８Ａとバッファアドレス格納部８Ｂとを備えてなっている。バッファアドレス格納部８Ｂには、バッファアドレス「ＢＡ」が格納領域に格納される。上記バッファアドレスは、セルバッファメモリ２に格納されたセルの格納領域を示す。上記バッファアドレス「ＢＡ」は、セルバッファメモリ２からセルを読み出すときに用いられる。
【００２０】
次ポインタ格納部８Ａには、各バッファアドレスをチェーン構造にするための情報が格納される。例えば、出力ポート３１に送られるセルのバッファアドレスが「ＢＡ１１」であり、次のセルのバッファアドレスが「ＢＡ１２」であるとする。このとき、バッファアドレス「ＢＡ１１」と対をなし、かつ、次のバッファアドレス「ＢＡ１２」を指し示すための情報が次ポインタ「ＮＰ１１」である。次ポインタ「ＮＰ１１」は、バッファアドレス「ＢＡ１１」と共に次ポインタ格納部８Ａに格納される。
このように、出力ポート３１に送られるセルのバッファアドレス「ＢＡ１１」、「ＢＡ１２」、…、「ＢＡ１ｍ」は、次ポインタ「ＮＰ１１」、「ＮＰ１２」、…、「ＮＰ１（ｍ−１）」によって繋げられ、論理的なチェーン構造にされる。この結果、図３に示すように、出力ポート３１に対応するアドレスチェーンＡＣ１が形成される。同様にして、アドレスチェーンＡＣ２、…、ＡＣＮも、次ポインタ「ＮＰ２１」〜「ＮＰ２（ｎ−１）」、…、「ＮＰＮ１」〜「ＮＰＮ（ｐ−１）」により形成される。
【００２１】
バッファアドレス格納部８Ｂの中で、アドレスが格納されていない、未使用領域（図３では印「＊」で示し、以下において同じである）も、同じようにして、次ポインタ「ＮＰ１」〜「ＮＰｑ」によって順に繋げられて、論理的なチェーン構造にされる。これにより、フリーチェーンＦＣが形成される。
アドレス格納メモリ８は、バッファアドレス「ＢＡ」及び次ポインタ「ＮＰ」の読み出し及び書き込みを制御部７の制御で行う。すなわち、アドレス格納メモリ８は、格納領域を指定するポインタ信号ａ３と、読み出しを示すアクセス指示信号ａ４とを制御部７から受け取ると、図２に示すように、ポインタ信号ａ３によるポインタ８Ｃが指定する格納領域から、次ポインタ格納部８Ａの次ポインタ「ＮＰ」や、バッファアドレス格納部８Ｂのバッファアドレス「ＢＡ」を読み出して、制御部７に送る。
【００２２】
また、アドレス格納メモリ８は、ポインタ信号ａ３と、書き込みを示すアクセス指示信号ａ４とを制御部７から受け取ると、次ポインタ格納部８Ａやバッファアドレス格納部８Ｂの、ポインタ８Ｃが指定する格納領域に、バッファアドレス「ＢＡ」や次ポインタ「ＮＰ」を書き込む。
ポインタ格納メモリ６は、図４に示すように、チェーン有無格納部６Ａ、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃを備えてなっている。チェーン有無格納部６Ａには、図４に示すように、有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」、「ＥＦ」が格納される。有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」は、アドレスチェーンＡＣ１、ＡＣ２、…、ＡＣＮの有無を示し、有無データ「ＥＦ」は、フリーチェーンの有無を示す。ここでは、有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」、「ＥＦ」が値「１」であるときに、チェーン有りを示し、値「０（ゼロ）」のときに、チェーン無しを示す。
【００２３】
ライトポインタ格納部６Ｂには、図４に示すように、ライトポインタ「ＷＰ１」、「ＷＰ２」、…、「ＷＰＮ」、「ＷＰＦ」が格納される。
ライトポインタ「ＷＰ１」、「ＷＰ２」、…、「ＷＰＮ」は、アドレスチェーンＡＣ１、ＡＣ２、…、ＡＣＮの最後尾のバッファアドレスを指し示すポインタであり、ライトポインタ「ＷＰＦ」は、フリーチェーンＦＣの最後尾の未使用領域を示すポインタである。各ポインタは、アドレス格納メモリの格納領域を指し示すもの、又は特定するものが用いられる。
リードポインタ格納部６Ｃには、図４に示すように、リードポインタ「ＲＰ１」、「ＲＰ２」、…、「ＲＰＮ」、「ＲＰＦ」が格納される。リードポインタ「ＲＰ１」、「ＲＰ２」、…、「ＲＰＮ」は、アドレスチェーンＡＣ１、ＡＣ２、…、ＡＣＮの先頭のバッファアドレスを指し示すポインタであり、リードポインタ「ＲＰＦ」は、フリーチェーンＦＣの先頭の未使用領域を示すポインタである。
【００２４】
ポインタ格納メモリ６は、上記リードポインタ及び上記ライトポインタの読み出し及び書き込みを制御部７の制御で行う。すなわち、ポインタ格納メモリ６は、アドレスチェーンやフリーチェーンを示すポート信号ａ１と、読み出しを示すアクセス指示信号ａ２とを制御部７から受け取ると、チェーン有無格納部６Ａ、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃから、ポート信号ａ１に対応する有無データ、ライトポインタ、リードポインタを読み出して、制御部７に送る。
また、ポインタ格納メモリ６は、アドレスチェーンやフリーチェーンを示すポート信号ａ１と、書き込みを示すアクセス指示信号ａ２とを制御部７から受け取ると、チェーン有無格納部６Ａ、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃに、制御部７から受け取った書き込みデータを、有無データ、ライトポインタ、リードポインタとして格納する。
【００２５】
制御部７は、書き込み制御部４から格納要求を受け取ると、図５に示す処理をする。ここでは、多重部１から出力されるセルが出力ポート３ｋ（ｋ＝１〜Ｎ）に送られるものとする。制御部７は、上記格納要求を受け取ると、フリーチェーンＦＣを示すポート信号ａ１と、チェーン有無格納部６Ａからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。この後、ポインタ格納メモリ６から有無データ「ＥＦ」を受け取ると、制御部７は、有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ１）。有無データ「ＥＦ」が値「１」であると、制御部７は、フリーチェーンＦＣが有るとして、書き込み制御部４に対して、入力されたセルの格納を許可する（ステップＳ２）。
【００２６】
ステップＳ２が終了すると、制御部７は、出力ポート３ｋに対応するアドレスチェーンＡＣｋの有無データ「Ｅｋ」が値「０」か否かを判断する（ステップＳ３）。ステップＳ３の処理のために、制御部７は、出力ポート３ｋを示すポート信号ａ１と、チェーン有無格納部６Ａからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。この後、ポインタ格納メモリ６から有無データ「Ｅｋ」を受け取ると、制御部７は、上記判断をする。
有無データ「Ｅｋ」が値「１」であり、出力ポート３ｋに対応するアドレスチェーンＡＣｋが有ると、制御部７は、
ＮＰ（ＷＰｋ）←ＲＰＦ
の処理をする（ステップＳ４）。ステップＳ４の処理は、図６に示すように、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示す未使用領域を、アドレスチェーンＡＣｋの次ポインタ「ＮＰｋｒ」が指し示すようにする。次ポインタ「ＮＰｋｒ」は、ライトポインタ「ＷＰｋ」が指し示すバッファアドレス「ＢＡｋｒ」と対をなすものである。
【００２７】
ステップＳ４の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とを、ポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰＦ」を受け取ると、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、ライトポインタ格納部６Ｂからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からライトポインタ「ＷＰｋ」を受け取ると、制御部７は、ライトポインタ「ＷＰｋ」をポインタ信号ａ３とする。ライトポインタ「ＷＰｋ」は、バッファアドレス「ＢＡｋ」を指し示している。この後、制御部７は、ポインタ信号ａ３と、次ポインタ格納部８Ａに対する書き込みを示すアクセス指示信号ａ２をアドレス格納メモリ８に送る。また、制御部７は、書き込みデータとして、リードポインタ「ＲＰＦ」をアドレス格納メモリ８に送る。これにより、アドレス格納メモリ８の次ポインタ格納部８Ａには、リードポインタ「ＲＰＦ」がバッファアドレス「ＢＡｋ」の次ポインタ「ＮＰｋ」として格納される。この結果、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示す未使用領域を、アドレスチェーンＡＣｋの次ポインタ「ＮＰｋｒ」が指し示すようになる。
【００２８】
ステップＳ４が終了すると、制御部７は、
ＷＰｋ←ＲＰＦ
の処理をする（ステップＳ５）。ステップＳ５の処理は、図７に示すように、フリーチェーンのリードポインタ「ＲＰＦ」が指し示す未使用領域を、ライトポインタ「ＷＰｋ」が指し示すようにする。
ステップＳ５の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰＦ」を受け取ると、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、ライトポインタ格納部６Ｂに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。
また、制御部７は、書き込みデータとして、リードポインタ「ＲＰＦ」をポインタ格納メモリ６に送る。これにより、リードポインタ「ＲＰＦ」がライトポインタ「ＷＰｋ」として格納される。この結果、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示す未使用領域を、アドレスチェーンＡＣｋの次ポインタ「ＮＰｋｒ」が指し示すようになる。
【００２９】
また、先のステップＳ３の処理で、アドレスチェーンＡＣｋが無いとき、制御部７は、
ＲＰｋ←ＲＰＦ
ＷＰｋ←ＲＰＦ
Ｅ←１
の処理をする（ステップＳ６）。ステップＳ６の処理は、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示す未使用領域を、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」及びライトポインタ「ＷＰｋ」が指し示すようにする。これにより、制御部７は、出力ポート３ｋに対応するアドレスチェーンＡＣｋを新たに生成する。そして、制御部７は、ポインタ格納メモリ６の有無データ「Ｅｋ」を「１」にする。
【００３０】
ステップＳ６の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰＦ」を受け取ると、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、リードポインタ「ＲＰＦ」をポインタ格納メモリ６に送る。これにより、リードポインタ「ＲＰＦ」がリードポインタ「ＲＰｋ」及びライトポインタ「ＷＰｋ」として格納される。この結果、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示す未使用領域を、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」及びライトポインタ「ＷＰｋ」が指し示すようになる。
【００３１】
この後、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、チェーン有無格納部６Ａに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、値「１」をポインタ格納メモリ６に送る。これにより、値「１」が有無データ「Ｅｋ」として格納される。
ステップＳ５又はステップＳ６の処理が終了すると、制御部７は、フリーチェーンＦＣのライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とが同じであるか否かを判断する（ステップＳ７）。ステップＳ７の処理は、ステップＳ６までの処理が終了した後、フリーチェーンＦＣが無くなっているか否かを調べるものである。ステップＳ７の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、制御部７は、ポインタ格納メモリ６からフリーチェーンＦＣのライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とを受け取り、上記判断をする。
【００３２】
フリーチェーンＦＣのライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とが異なれば、制御部７は、
ＲＰＦ←ＮＰ（ＲＰＦ）
の処理をする（ステップＳ８）。ステップＳ８の処理は、図８に示すように、フリーチェーンＦＣの次ポインタＮＰ１が指し示す未使用領域を、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示すようにする。これにより、制御部７は、リードポインタ「ＲＰＦ」を、フリーチェーンＦＣの新たな先頭に移動する。ステップＳ８の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とを、ポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰＦ」を受け取ると、制御部７は、リードポインタ「ＲＰＦ」をポインタ信号ａ３とする。この後、制御部７は、ポインタ信号ａ３と、次ポインタ格納部８Ａからの読み出しを示すアクセス指示信号ａ４とをアドレス格納メモリ８の次ポインタ格納部８Ａに送る。これにより、アドレス格納メモリ８から次ポインタ「ＮＰｋ」を受け取ると、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、リードポインタ格納部６Ｃに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。
また、制御部７は、書き込みデータとして、次ポインタ「ＮＰｋ」をポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６では、次ポインタ「ＮＰｋ」がリードポインタ「ＲＰＦ」として格納される。この結果、フリーチェーンＦＣの次ポインタＮＰ１が指し示す未使用領域を、フリーチェーンＦＣのリードポインタ「ＲＰＦ」が指し示すようになる。
【００３３】
また、先のステップＳ７で、フリーチェーンＦＣのライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とが同じであると、制御部７は、フリーチェーンＦＣの有無データ「ＥＦ」を値「０」にする（ステップＳ９）。この処理により、フリーチェーンＦＣが無いことが示される。
ステップＳ９の処理のために、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、チェーン有無格納部６Ａに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、値「０」をポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６では、値「０」が有無データ「ＥＦ」として格納される。
【００３４】
ステップＳ８又はステップＳ９が終了すると、制御部７は、
ＢＡ（ＷＰ）←空きバッファアドレス
の処理をする（ステップＳ１０）。ステップＳ１０は次の処理である。すなわち、図９に示すように、アドレス格納メモリ８が空きアドレス管理メモリ９から空きバッファアドレスを受け取ると、制御部７は、上記空きバッファアドレスを、ライトポインタ「ＷＰｋ」が指し示す、バッファアドレス格納部８Ｂの格納領域にバッファアドレス「ＢＡｋ（ｒ＋１）」として格納するための制御をする。制御部７は、ステップＳ１０の後、図５の処理を終了する。
また、先のステップＳ１で、フリーチェーンＦＣが無ければ、制御部７は、入力されたセルの格納の不許可を書き込み制御部４に送り（ステップＳ１１）、図５の処理を終了する。
こうして、制御部７は、書き込み制御部４から格納要求を受け取ると、該当するアドレスチェーンＡＣｋの最後尾に、新たなバッファアドレスを格納するための処理をする。
【００３５】
ところで、制御部７は、読み出し制御部５から出力ポート３ｋと、バッファアドレスの出力指示とを受け取ると、図１０に示す処理を開始する。すなわち、制御部７は、出力ポート３ｋと出力指示とを受け取ると、バッファアドレスを出力する制御をする（ステップＳ２１）。ステップＳ２１の処理は、図１１に示すように、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示すバッファアドレスを、バッファアドレス格納部８Ｂから出力させるためのものである。
ステップＳ２１の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタＲＰｋを受け取ると、リードポインタ「ＲＰｋ」をポインタ信号ａ３とする。この後、制御部７は、このポインタ信号ａ３と、バッファアドレス格納部８Ｂからの読み出しを示すアクセス指示信号ａ４とを、アドレス格納メモリ８に送る。これにより、アドレス格納メモリ８は、バッファアドレス「ＢＡｋ１」をセルバッファメモリ２及び空きアドレス管理メモリ９に送る。
【００３６】
ステップＳ２１が終了すると、フリーチェーンＦＣの有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ２２）。フリーチェーンＦＣが有ると、制御部７は、
ＮＰ（ＷＰＦ）←ＲＰｋ
の処理をする（ステップＳ２３）。ステップＳ２３の処理は、図１２に示すように、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域、すなわちバッファアドレス「ＢＡｋ１」が既に出力された格納領域を、フリーチェーンＦＣの次ポインタ「ＮＰｑ＋１」が指し示すようにする。
これにより、制御部７は、アドレスチェーンＡＣｋの先頭を、フリーチェーンＦＣの最後尾に繋げる。
【００３７】
ステップＳ２３の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とを、ポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰｋ」を受け取ると、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、ライトポインタ格納部６Ｂからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からライトポインタ「ＷＰＦ」を受け取ると、制御部７は、ライトポインタ「ＷＰＦ」をポインタ信号ａ３とする。この後、制御部７は、ポインタ信号ａ３と、次ポインタ格納部８Ａに対する書き込みを示すアクセス指示信号ａ４とをアドレス格納メモリ８に送る。また、制御部７は、書き込みデータとして、リードポインタ「ＲＰｋ」をアドレス格納メモリ８に送る。これにより、アドレス格納メモリ８の次ポインタ格納部８Ａには、リードポインタ「ＲＰｋ」がフリーチェーンＦＣの次ポインタ「ＮＰｑ＋１」として格納される。この結果、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域を、フリーチェーンＦＣの次ポインタ「ＮＰｑ＋１」が指し示すようになる。
【００３８】
ステップＳ２３が終了すると、制御部７は、
ＷＰＦ←ＲＰｋ
の処理をする（ステップＳ２４）。ステップＳ２４の処理は、図１３に示すように、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域を、フリーチェーンＦＣのライトポインタ「ＷＰＦ」が指し示すようにする。これにより、制御部７は、フリーチェーンＦＣの最後尾にライトポインタ「ＷＰＦ」を移す。
ステップＳ２４の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰｋ」を受け取ると、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、ライトポインタ格納部６Ｂに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。
また、制御部７は、書き込みデータとしてリードポインタ「ＲＰｋ」をポインタ格納メモリ６に送る。これにより、リードポインタ「ＲＰｋ」がライトポインタ「ＷＰＦ」として格納される。この結果、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域を、フリーチェーンＦＣのライトポインタ「ＷＰＦ」が指し示すようになる。
【００３９】
また、先のステップＳ２２で、フリーチェーンＦＣが無いとき、制御部７は、
ＲＰＦ←ＲＰｋ
ＷＰＦ←ＲＰｋ
ＥＦ←１
の処理をする（ステップＳ２５）。ステップＳ２５の処理は、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域を、フリーチェーンＦＣのリードポインタ「ＲＰＦ」及びライトポインタ「ＷＰＦ」が指し示すようにする。これにより、制御部７は、フリーチェーンＦＣを新たに形成する。そして、制御部７は、ポインタ格納メモリ６の有無データ「ＥＦ」を「１」にする。
ステップＳ２５の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰｋ」を受け取ると、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、リードポインタ「ＲＰｋ」をポインタ格納メモリ６に送る。これにより、リードポインタ「ＲＰｋ」がライトポインタ「ＷＰＦ」及びリードポインタ「ＲＰＦ」として格納される。この結果、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示す未使用領域を、フリーチェーンＦＣのリードポインタ「ＲＰＦ」及びライトポインタ「ＷＰＦ」が指し示すようになる。
【００４０】
この後、制御部７は、フリーチェーンＦＣを示すポート信号ａ１と、チェーン有無格納部６Ａに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、値「１」をポインタ格納メモリ６に送る。これにより、値「１」が有無データ「ＥＦ」として格納される。
ステップＳ２４又はステップＳ２５の処理が終了すると、制御部７は、アドレスチェーンＡＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じであるか否かを判断する（ステップＳ２６）。ステップＳ２６の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、ライトポインタ格納部６Ｂ及びリードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。これにより、制御部７は、ポインタ格納メモリ６からアドレスチェーンＡＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とを受け取り、上記判断をする。
【００４１】
アドレスチェーンＡＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが異なれば、制御部７は、
ＲＰｋ←ＮＰ（ＲＰｋ）
の処理をする（ステップＳ２７）。ステップＳ２７の処理は、図１４に示すように、次ポインタ「ＮＰｋ１」が指し示すバッファアドレス「ＢＡｋ２」を、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示すようにする。これにより、制御部７は、リードポインタ「ＲＰｋ」をアドレスチェーンＡＣｋの先頭に移動する。
ステップＳ２７の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃからの読み出しを示すアクセス指示信号ａ２とを、ポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６からリードポインタ「ＲＰｋ」を受け取ると、制御部７は、リードポインタ「ＲＰｋ」をポインタ信号ａ３とする。この後、制御部７は、このポインタ信号ａ３と、次ポインタ格納部８Ａからの読み出しを示すアクセス指示信号ａ４とをアドレス格納メモリ８に送る。これにより、アドレス格納メモリ８から次ポインタ「ＮＰｋ」を受け取ると、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、リードポインタ格納部６Ｃに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、次ポインタ「ＮＰｋ」をポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６では、次ポインタ「ＮＰｋ」がリードポインタ「ＲＰｋ」として格納される。この結果、次ポインタ「ＮＰｋ１」が指し示すバッファアドレス「ＢＡｋ２」を、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が指し示すようになる。
【００４２】
また、先のステップＳ２６の処理で、アドレスチェーンＡＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じであると、制御部７は、アドレスチェーンＡＣｋの有無データ「Ｅｋ」を値「０」にする（ステップＳ２８）。この処理により、アドレスチェーンＡＣｋが無いことが示される。
ステップＳ２７の処理のために、制御部７は、アドレスチェーンＡＣｋを示すポート信号ａ１と、チェーン有無格納部６Ａに対する書き込みを示すアクセス指示信号ａ２とをポインタ格納メモリ６に送る。また、制御部７は、書き込みデータとして、値「０」をポインタ格納メモリ６に送る。これにより、ポインタ格納メモリ６では、有無データ「Ｅｋ」が値「０」になる。
こうして、制御部７は、図１０に示す処理を終了する。
【００４３】
次に、この実施の形態の動作について説明する。
入力ポート１１、１２、…、１Ｎに入力されたセルは、多重部１で多重化されて、セルバッファメモリ２に送られる。多重部１から上記セルが出力されると、書き込み制御部４は、上記セルの行き先を調べる。上記セルの行き先が出力ポート３ｋであると、書き込み制御部４は、出力ポート３ｋを示すポート信号と、上記セルの格納要求を制御部７に送る。
制御部７は、上記格納要求を受け取ると、ステップＳ１により、フリーチェーンＦＣの有無を調べる。フリーチェーンＦＣが無ければ、制御部７は、ステップＳ１１により、上記セルの格納を不許可にする。書き込み制御部４は、制御部７から上記セルの格納の不許可を受け取ると、上記セルを破棄する。
【００４４】
フリーチェーンＦＣがステップＳ１で有ると、制御部７は、ステップＳ２で、書き込み制御部４に対して、入力されたセルの格納を許可する。書き込み制御部４は、制御部７から上記格納許可を受け取ると、空きアドレス管理メモリ９に対して、アドレス出力要求を送る。上記要求に応じて、空きアドレス管理メモリ９から、空き領域のアドレスであるバッファアドレスを読み出して、セルバッファメモリ２及びアドレス格納メモリ８に送る。セルバッファメモリ２は、空きアドレス管理メモリ９からバッファアドレスを受け取ると、上記バッファアドレスが指定する格納領域に、多重部１からの上記セルを格納する。
【００４５】
アドレス格納メモリ８が上記バッファアドレスを受け取ると、制御部７は、ステップＳ３で、アドレスチェーンＡＣｋの有無を調べる。アドレスチェーンＡＣｋが有ると、制御部７は、ステップＳ４，Ｓ５で、フリーチェーンＦＣの先頭を、アドレスチェーンＡＣｋの最後尾に繋げて、アドレスチェーンＡＣｋにバッファアドレス格納用の未使用領域を確保する。この後、制御部７は、アドレスチェーンＡＣｋのリードポインタ「ＲＰｋ」が新たな最後尾を指し示すようにする。また、アドレスチェーンＡＣｋが無ければ、制御部７は、ステップＳ６により、新たにアドレスチェーンＡＣｋを生成し、バッファアドレス格納用の未使用領域を確保する。ステップＳ７で、フリーチェーンＦＣのライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とが異なると、制御部７は、フリーチェーンＦＣがまだ有ると判断し、ステップＳ８により、フリーチェーンＦＣの新たな先頭にリードポインタ「ＲＰＦ」を移す。また、ステップＳ７で、ライトポインタ「ＷＰＦ」とリードポインタ「ＲＰＦ」とが同じであると、制御部７は、フリーチェーンＦＣが無いとして、ステップＳ９により、フリーチェーンＦＣの有無データ「ＥＦ」を値「０」にする。
【００４６】
未使用領域の確保が終了し、制御部７は、ステップＳ１０により、上記未使用領域に、上記バッファアドレスを、「ＢＡｋ（ｒ＋１）」として格納する。こうして、入力されたセルのバッファアドレス「ＢＡｋ（ｒ＋１）」は、アドレスチェーンＡＣｋの最後尾に繋がれる。
ところで、セルが出力ポート３ｋに出力されるとき、読み出し制御部５は、出力ポート３ｋとバッファアドレスの出力指示とを制御部７に送る。これにより、制御部７は、ステップＳ２１により、アドレス格納メモリ８を制御する。アドレス格納メモリ８は、アドレスチェーンＡＣｋの先頭のバッファアドレス「ＢＡｋ１」を読み出して、バッファアドレス「ＢＡｋ１」をセルバッファメモリ２及び空きアドレス管理メモリ９に送る。
【００４７】
セルバッファメモリ２は、バッファアドレス「ＢＡｋ１」で指定された格納領域からセルを読み出して、出力ポート３ｋに送る。また、空きアドレス管理メモリ９は、バッファアドレス「ＢＡｋ１」を空きバッファアドレスとして管理する。
アドレス格納メモリ８がバッファアドレス「ＢＡｋ１」を出力すると、制御部７は、次の制御をする。すなわち、制御部７は、ステップＳ２２で、フリーチェーンＦＣの有無を調べる。フリーチェーンＦＣが有ると、制御部７は、ステップＳ２３により、アドレスチェーンＡＣｋの先頭を切り離し、フリーチェーンＦＣの最後尾に繋げる。これにより、バッファアドレス「ＢＡｋ１」を出力した後の未使用領域が、フリーチェーンＦＣの最後尾に繋げられる。この後、制御部７は、ステップＳ２４により、フリーチェーンＦＣのライトポインタ「ＷＰＦ」が新たな最後尾を指し示すようにする。また、フリーチェーンＦＣが無ければ、制御部７は、ステップＳ２５により、バッファアドレス「ＢＡｋ１」を出力した後の未使用領域を用いて、新たなフリーチェーンＦＣを生成する。
【００４８】
この後、ステップＳ２６でアドレスチェーンＡＣｋの有無を調べる。アドレスチェーンＡＣｋが有ると、制御部７は、ステップＳ２７により、アドレスチェーンＡＣｋの新たな先頭にリードポインタ「ＲＰｋ」を移して、処理を終了する。
また、アドレスチェーンＡＣｋが無ければ、制御部７は、ステップＳ２８により、アドレスチェーンＡＣｋの有無データ「Ｅｋ」を値「０」にして、処理を終了する。
【００４９】
こうして、バッファアドレスの出力で未使用領域となった格納領域がフリーチェーンＦＣの最後尾に繋げられる。
このように、この実施の形態によれば、アドレス格納メモリ８を出力ポート３１〜３Ｎに対して共用する。この結果、出力ポートの使用頻度に応じて、上記出力ポートに対応するアドレスチェーンの長さを調節するので、出力ポート３１〜３Ｎに応じて、アドレス格納メモリ８を有効に使用することを可能にする。
【００５０】
◇第１の実施の形態
次に、この発明の第１の実施の形態について説明する。
図１５は、この発明の第１の実施の形態であるＡＴＭスイッチ回路の構成を概略示すブロック図、図１６は、同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図、図１７は、同ＡＴＭスイッチ回路のページ格納メモリの構成を示す構成図、図１８は、同ＡＴＭスイッチ回路のチェーン構造を説明する説明図、図１９は、同ＡＴＭスイッチ回路のポインタ格納メモリの構成を示す構成図、図２０は、同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャート、図２１は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２２は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２３は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２４は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２５は、同ＡＴＭスイッチ回路の制御部による、セル出力の処理を示すフローチャート、図２６は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２７は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２８は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図２９は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【００５１】
このＡＴＭスイッチ回路は、図１５に示すように、多重部１、セルバッファメモリ２、分離部３、書き込み制御部４、読み出し制御部５、空きアドレス管理メモリ９、ポインタ格納メモリ１１、制御部１２、ページ格納メモリ１３及びアドレス格納メモリ１４を備えてなっている。なお、図１５において、図１と同じものについては、図１と同じ符号を付与して、その説明を省略する。
アドレス格納メモリ１４は、バッファアドレスを格納する。上記バッファアドレスは、セルをセルバッファメモリ２に格納するときに用いられる。アドレス格納メモリ１４は、図１６に示すように、バッファアドレス「ＢＡ」を格納領域に格納するものであり、「Ｌ」個の格納領域をまとめて、論理的なページとしている。すなわち、アドレス格納メモリ１４では、ページ番号「１」が、「０」〜「Ｌ−１」のオフセット値で示される格納領域を持つ。同じようにして、ページ番号「２」、…、「Ｍ」は、「０」〜「Ｌ−１」のオフセット値で示される格納領域をそれぞれ持つ。そして、各バッファアドレス「ＢＡ」は、上記ページ番号と上記オフセット値とにより特定される。
【００５２】
ページ格納メモリ１３は、アドレス格納メモリ１４のページをチェーン構造にするための情報を格納する。例えば、出力ポート３１に送るためのセルを格納した、ページ番号が「１」のページに、バッファアドレスがすべての格納領域に格納されているために、ページ番号が次に移ると、ページ格納メモリ１３には、次ページ番号が格納される。すなわち、図１７に示すように、ページ格納メモリ１３には、次ページ番号「ＰＧ」が、ページ番号に対応して格納される。同じようにして、ページ格納メモリ１３には、ページ番号「２」、…、「Ｍ」に対応する次ページ番号「ＰＧ」がそれぞれ格納される。
【００５３】
ページ格納メモリ１３のページ番号及び次ページ番号により、図１８に示すように、出力ポート３１、３２、…、３Ｎに対応してページチェーンＰＣ１、ＰＣ２、…、ＰＣＮが形成される。
また、アドレス格納メモリ１４の中で、バッファアドレスが格納されていない、未使用領域から成るフリーページも、同じようにして、次ページ番号「ＰＧ」によって順に繋げられて、論理的なチェーン構造にされる。これにより、フリーページチェーンＦＰＣが形成される。
【００５４】
ポインタ格納メモリ１１は、図１９に示すように、チェーン有無格納部１１Ａ、ライトポインタ格納部１１Ｂ及びリードポインタ格納部１１Ｃを備えてなっている。さらに、ライトポインタ格納部１１Ｂは、ページ番号格納部１１Ｄとオフセット値格納部１１Ｅとを備え、リードポインタ格納部１１Ｃは、ページ番号格納部１１Ｆとオフセット値格納部１１Ｇとを備えてなっている。
チェーン有無格納部１１Ａには、有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」、「ＥＦ」が格納される。有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」は、ページチェーンＰＣ１、ＰＣ２、…、ＰＣＮの有無を示し、有無データ「ＥＦ」は、フリーページチェーンＦＰＣの有無を示す。
【００５５】
ページ番号格納部１１Ｄには、ページチェーンＰＣ１のライトポインタである「ＷＰ１」のページ番号「ＷＰＰ１」が格納される。また、ページ番号「ＷＰＰ１」には、オフセット値「ＷＰＯ１」がオフセット値格納部１１Ｅに格納される。オフセット値「ＷＰＯ１」は、ページ番号「ＷＰＰ１」で指定されたページ内の格納領域を指定するものである。
同じようにして、ページ番号格納部１１Ｄには、ページチェーンＰＣ２、…、ＰＣＮのライトポインタ「ＷＰ２」、…、「ＷＰＮ」のページ番号「ＷＰＰ２」、…、「ＷＰＰＮ」が格納され、オフセット値格納部１１Ｅには、ページ番号「ＷＰＰ２」、…、「ＷＰＰＮ」のオフセット値「ＷＰＯ２」、…、「ＷＰＯＮ」が格納される。また、ページ番号格納部１１Ｄは、フリーページチェーンＦＰＣのライトポインタがページ番号「ＷＰＰＦ」として格納される。
【００５６】
ページ番号格納部１１Ｆには、ページチェーンＰＣ１、ＰＣ２、…、ＰＣＮのリードポインタ「ＲＰ１」、「ＲＰ２」、…、「ＲＰＮ」のページ番号「ＲＰＰ１」、「ＲＰＰ２」、…、「ＲＰＰＮ」が格納され、オフセット値格納部１１Ｇには、ページ番号「ＲＰＰ１」、「ＲＰＰ２」、…、「ＲＰＰＮ」のオフセット値「ＲＰＯ１」、「ＲＰＯ２」、…、「ＲＰＯＮ」が格納される。また、ページ番号格納部１１Ｆには、フリーページチェーンＦＰＣのリードポインタがページ番号「ＲＰＰＦ」として格納される。
制御部１２は、書き込み制御部４から格納要求を受け取ると、図２０に示す処理をする。ここでは、多重部１から出力されるセルが出力ポート３ｋに送られるものとする。制御部１２は、上記格納要求を受け取ると、出力ポート３ｋに対応するページチェーンＰＣｋを示すポート信号ｂ１と、チェーン有無格納部１１Ａ及びオフセット値格納部１１Ｅからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ポインタ格納メモリ１１から有無データ「Ｅｋ」及びオフセット値「ＷＰＯｋ」を受け取ると、制御部１２は、データ「Ｅｋ」が値「１」であり、オフセット値「ＷＰＯｋ」が値「Ｌ−１」か否かを判断する。（ステップＳ３１）。ステップＳ３１の処理は、ページチェーンＰＣｋが有る場合に、ライトポインタ「ＷＰｋ」が指し示すページには、空きの格納領域が有るか否かを調べるものである。
【００５７】
ステップＳ３１により、ページチェーンＰＣｋが有り、かつ、オフセット値「ＷＰＯｋ」が値「Ｌ−１」と異なると判断すると、フリーページチェーンＦＰＣの有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ３２）。このために、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、チェーン有無格納部１１Ａからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ポインタ格納メモリ１１から有無データ「ＥＦ」を受け取ると、制御部１２は上記判断をする。
ステップＳ３２により、フリーページチェーンＦＰＣが有ると判断すると、制御部１２は、入力されたセルの格納を許可する格納許可を、書き込み制御部４に送る（ステップＳ３３）。ステップＳ３３が終了すると、制御部１２は、ページチェーンＰＣｋの有無データ「Ｅｋ」が「０」か否かを判断する（ステップＳ３４）。このために、制御部１２は、出力ポート３ｋを示すポート信号ｂ１と、チェーン有無格納部１１Ａからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ポインタ格納メモリ１１からデータ「Ｅｋ」を受け取ると、制御部１２は上記判断をする。
【００５８】
ステップＳ３４により、ページチェーンＰＣｋが有ると判断すると、制御部１２は、
ＰＧ（ＷＰＰｋ）←ＲＰＰＦ
の処理をする（ステップＳ３５）。ステップＳ３５の処理は、図２１に示すように、フリーページチェーンＦＰＣのリードポインタ「ＲＰＰＦ」が指し示すページを、ページチェーンＰＣｋの最後尾のページの次ページ番号「ＰＧ」が指し示しようにする（ステップＳ３５）。上記最後尾のページは、ライトポインタＷＰｋが指し示すページである。
ステップＳ３５の処理のために、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、リードポインタ格納部１１Ｃからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、フリーページチェーンＦＰＣのページ番号「ＲＰＰＦ」をポインタ格納メモリ１１から受け取ると、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｄからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ライトポインタ「ＷＰｋ」のページ番号「ＷＰＰｋ」をポインタ格納メモリ１１から受け取ると、制御部１２は、ページ番号「ＷＰＰｋ」をページ信号ｂ５とする。この後、制御部１２は、ページ信号ｂ５と、書き込みを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。また、制御部１２は、書き込みデータとして、ページ番号「ＲＰＰＦ」をページ格納メモリ１３に送る。これにより、ページ格納メモリ１３のページ番号「ＷＰＰｋ」に対応する格納領域には、次ページ番号「ＰＧ」としてリードポインタ「ＲＰＰＦ」が格納される。この結果、フリーページチェーンＦＰＣのリードポインタ「ＲＰＰＦ」が指し示すページを、ライトポインタ「ＷＰｋ」が指し示すページの次ページ番号「ＰＧ」が指し示すようになる。
【００５９】
ステップＳ３５が終了すると、制御部１２は、
ＷＰＰｋ←ＲＰＰＦ
ＷＰＯｋ←０
の処理をする（ステップＳ３６）。ステップＳ３６の処理は、図２２に示すように、ページ番号「ＲＰＰＦ」が指し示すページを、ライトポインタ「ＷＰｋ」のページ番号「ＷＰＰｋ」が指し示すようにすると共に、ライトポインタ「ＷＰＰｋ」のオフセット値「ＷＰＯｋ」を値「０」にする。
ステップＳ３６の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ライトポインタ格納部１１Ｂに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。
また、制御部１２は、書き込みデータとして値「０」をポインタ格納メモリ１１に送る。これにより、値「０」がライトポインタ「ＷＰｋ」のオフセット値「ＷＰＯｋ」として格納される。
【００６０】
この後、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰＦ」を受け取ると、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｄに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして、リードポインタ「ＲＰＰＦ」をポインタ格納メモリ１１に送る。この結果、ライトポインタ「ＷＰｋ」のページ番号「ＷＰＰｋ」として、ページ番号「ＲＰＰＦ」が格納される。この結果、ページ番号「ＲＰＰＦ」が指し示すページを、ライトポインタ「ＷＰｋ」が指し示すようになる。
【００６１】
また、ステップＳ３４で、ページチェーンＰＣｋが無い場合、制御部１２は、
ＲＰＰｋ←ＲＰＰＦ、ＲＰＯｋ←０
ＷＰＰｋ←ＲＰＰＦ、ＷＰＯｋ←０
Ｅｋ←１
の処理をする（ステップＳ３７）。ステップＳ３７の処理は、フリーページチェーンＦＰＣのページ番号「ＲＰＰＦ」が指し示す未使用領域を、ページチェーンＰＣｋのリードポインタ「ＲＰｋ」及びライトポインタ「ＷＰｋ」が指し示すようにする。これにより、制御部１２は、出力ポート３ｋに対応するページチェーンＰＣｋを新たに形成する。そして、制御部１２は、ポインタ格納メモリ１１の有無データ「Ｅｋ」を「１」にする。
【００６２】
ステップＳ３７の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｅ，１１Ｇに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして「０」をポインタ格納メモリ１１に送る。これにより、値「０」がライトポインタ「ＷＰｋ」のオフセット値「ＷＰＯｋ」及びリードポインタ「ＲＰｋ」のオフセット値「ＲＰＯｋ」として格納される。
この後、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰＦ」を受け取ると、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｄ，１１Ｆに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。
また、制御部１２は、書き込みデータとして、ページ番号「ＲＰＰＦ」をポインタ格納メモリ１１に送る。この結果、ページ番号「ＲＰＰＦ」がライトポインタ「ＷＰｋ」のページ番号「ＷＰＰｋ」及びリードポインタ「ＲＰｋ」のページ番号「ＲＰＰｋ」として格納される。
【００６３】
この後、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、チェーン有無格納部１１Ａに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして値「１」をポインタ格納メモリ１１に送る。これにより、値「１」が有無データ「Ｅｋ」として格納される。
ステップＳ３６又はステップＳ３７が終了すると、制御部１２は、フリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」とページ番号「ＲＰＰＦ」とが同じであるか否かを判断する（ステップＳ３８）。ステップＳ３８の処理のために、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｄ，１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からフリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」、「ＲＰＰＦ」を受け取ると、制御部１２は上記判断をする。
【００６４】
ステップＳ３８で、フリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」とページ番号「ＲＰＰＦ」とが異なると、制御部１２は、
ＲＰＰＦ←ＰＧ（ＲＰＰＦ）
の処理をする（ステップＳ３９）。ステップＳ３９の処理は、図２３に示すように、フリーページチェーンＦＰＣの、先頭のページの次ページ番号「ＰＧ」が指し示すページを、フリーページチェーンＦＰＣのリードポインタでもあるページ番号「ＲＰＰＦ」が指し示すようにする。これにより、ステップＳ３８までの処理が終了した場合、フリーページチェーンＦＰＣの先頭のページが１つ後にずれたとき、制御部１２は、ページ番号「ＲＰＰＦ」をフリーページチェーンＦＰＣの新たな先頭ページに移動する。
【００６５】
ステップＳ３９の処理のために、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とを、ポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰＦ」を受け取ると、制御部１２は、ページ番号「ＲＰＰＦ」をページ信号ｂ５とする。この後、制御部１２は、ページ信号ｂ５と、読み出しを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。これにより、ページ格納メモリ１３から次ページ番号「ＰＧ」を受け取ると、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｆに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。
また、制御部１２は、書き込みデータとして、次ページ番号「ＰＧ」をポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１では、次ページ番号「ＰＧ」がページ番号「ＲＰＰＦ」として格納される。
【００６６】
また、先のステップＳ３８で、フリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」とページ番号「ＲＰＰＦ」とが同じであると、制御部１２は、フリーページチェーンＦＰＣの有無データ「ＥＦ」を値「０」にする（ステップＳ４０）。この処理により、フリーページチェーンＦＰＣが無いことが示される。
ステップＳ４０の処理のために、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、チェーン有無格納部１１Ａに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして、値「０」をポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１では、値「０」が有無データ「ＥＦ」として格納される。さらに、先のステップＳ３１で、ページチェーンＰＣｋが有り、オフセット値「ＷＰＯｋ」が値「Ｌ−１」と異なると、制御部１２は、オフセット値「ＷＰＯｋ」の値を「１」だけ増加させる（ステップＳ４１）。
ステップＳ４１の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｅからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からオフセット値「ＷＰＯｋ」を受け取ると、制御部１２は、値「ＷＰＯｋ」に値「１」を加える計算をする。この後、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｅに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。
また、制御部１２は、書き込みデータとして、値「ＷＰＯｋ＋１」をポインタ格納メモリ１１に送る。これにより、値「ＷＰＯｋ＋１」がオフセット値「ＷＰＯｋ」として格納される。
【００６７】
ステップＳ３９、ステップＳ４０又はステップＳ４１が終了すると、制御部１２は、
ＢＡ（ＷＰｋ）←空きバッファアドレス
の処理をする（ステップＳ４２）。ステップＳ４２は次の処理である。すなわち、図２４に示すように、アドレス格納メモリ１４が、空きアドレス管理メモリ９から空きバッファアドレスを受け取ると、制御部１２は、ライトポインタ「ＷＰｋ」が指し示す未使用領域に、上記空きバッファアドレスをバッファアドレス「ＢＡ」として格納するための制御をする。
【００６８】
また、先のステップＳ３２で、フリーページチェーンＦＰＣが無ければ、制御部１２は、入力されたセルの格納の不許可を書き込み制御部４に送り（ステップＳ４３）、図５の処理を終了する。
こうして、制御部１２は、書き込み制御部４から格納要求を受け取ると、該当するページチェーンＰＣｋの最後尾に、新たなバッファアドレスを格納するための処理をする。
【００６９】
ところで、制御部１２は、読み出し制御部５から出力ポート３ｋとバッファアドレスの出力指示とを受け取ると、図２５に示す処理を開始する。すなわち、制御部１２は、出力ポート３ｋと出力指示とを受け取ると、バッファアドレスを出力する（ステップＳ５１）。ステップＳ５１の処理は、図２６に示すように、ページチェーンＰＣｋが出力ポート３ｋに対応するので、ページチェーンＰＣｋのリードポインタ「ＲＰｋ」が指し示すバッファアドレス「ＢＡ」を、出力するためのものである。
ステップＳ５１の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆ及びオフセット値格納部１１Ｇからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１から、ページ番号「ＲＰＰｋ」とオフセット値「ＲＰＯｋ」から成るリードポインタ「ＲＰｋ」を受け取ると、制御部１２は、リードポインタ「ＲＰｋ」をポインタ信号ｂ３とする。この後、制御部１２は、このポインタ信号ｂ３と、読み出しを示すアクセス指示信号ｂ４とを、アドレス格納メモリ１４に送る。これにより、アドレス格納メモリ１４は、ページ番号「ＲＰＰｋ」とオフセット値「ＲＰＯｋ」とで特定されるバッファアドレス「ＢＡ」を、セルバッファメモリ２及び空きアドレス管理メモリ９に送る。
【００７０】
ステップＳ５１が終了すると、制御部１２は、ページチェーンＰＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが異なり、オフセット値「ＲＰＯｋ」が値「Ｌ−１」と異なるか否かを判断する（ステップＳ５２）。
ステップＳ５２の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｄ，１１Ｆ及びオフセット値格納部１１Ｅ，１１Ｇからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ページ番号「ＷＰＰｋ」とオフセット値「ＷＰＯｋ」とから成るライトポインタ「ＷＰｋ」と、ページ番号「ＲＰＰｋ」とオフセット値「ＲＰＯｋ」とから成るリードポインタ「ＲＰｋ」とをポインタ格納メモリ１１から受け取る。
【００７１】
ステップＳ５２により、ライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じ、又は、オフセット値「ＲＰＯｋ」が値「Ｌ−１」に等しい場合、制御部１２は、先のステップＳ３２と同じように、フリーページチェーンＦＰＣの有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ５３）。
ステップＳ５３により、フリーページチェーンＦＰＣが有ると判断すると、制御部１２は、
ＰＧ（ＷＰＰＦ）←ＲＰＰｋ
の処理をする（ステップＳ５４）。ステップＳ５４の処理は、図２７に示すように、ページ番号「ＲＰＰｋ」が指し示すページを、次ページ番号「ＰＧ」が指し示すようにする。次ページ番号「ＰＧ」は、フリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」が指し示すページの次ページである。
【００７２】
ステップＳ５４の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ポインタ格納メモリ１１からページ番号「ＲＰＰｋ」を受け取ると、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｄからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ポインタ格納メモリ１１からページ番号「ＷＰＰＦ」を受け取ると、制御部１２は、ページ番号「ＷＰＰＦ」をページ信号ｂ５とする。この後、制御部１２は、ページ信号ｂ５と、書き込みを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。また、制御部１２は、書き込みデータとして、ページ番号「ＲＰＰｋ」をページ格納メモリ１３に送る。この結果、ページ格納メモリ１３のページ番号「ＷＰＰＦ」に対応する格納領域には、次ページ番号「ＰＧ」として値「ＲＰＰｋ」が格納される。この結果、ページ番号「ＲＰＰｋ」が指し示すページを、次ページ番号「ＰＧ」が指し示すようになる。
【００７３】
ステップＳ５４の処理が終了すると、制御部１２は、
ＷＰＰＦ←ＲＰＰｋ
の処理をする（ステップＳ５５）。ステップＳ５５の処理は、図２８に示すように、ページ番号「ＲＰＰｋ」が指し示すページを、ページ番号「ＷＰＰＦ」が指し示すようにする。
ステップＳ５５の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰｋ」を受け取ると、制御部１２は、フリーチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｄに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして値「ＲＰＰｋ」をポインタ格納メモリ１１に送る。これにより、値「ＲＰＰｋ」がページ番号「ＷＰＰＦ」として格納される。この結果、ページ番号「ＲＰＰｋ」が指し示すページを、ページ番号「ＷＰＰＦ」が指し示すようになる。
【００７４】
また、ステップＳ５３で、フリーページチェーンＦＰＣが無い場合、制御部１２は、
ＲＰＰＦ←ＲＰＰｋ
ＷＰＰＦ←ＲＰＰｋ
ＥＦ←１
の処理をする（ステップＳ５６）。ステップＳ５６の処理は、ページチェーンＰＣｋのページ番号「ＲＰＰｋ」が指し示すページを、フリーページチェーンＦＰＣのページ番号「ＲＰＰＦ」及びページ番号「ＷＰＰＦ」が指し示すようにする。これにより、制御部１２は、フリーページチェーンＦＰＣを新たに形成する。そして、制御部１２は、ポインタ格納メモリ１１の有無データ「ＥＦ」を「１」にする。
【００７５】
ステップＳ５６の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰｋ」を受け取ると、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、ページ番号格納部１１Ｄ，１１Ｆに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして値「ＲＰＰｋ」をポインタ格納メモリ１１に送る。この結果、値「ＲＰＰｋ」がページ番号「ＷＰＰＦ」及びページ番号「ＲＰＰＦ」として格納される。この後、制御部１２は、フリーページチェーンＦＰＣを示すポート信号ｂ１と、チェーン有無格納部１１Ａに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして値「１」をポインタ格納メモリ１１に送る。これにより、値「１」が有無データ「ＥＦ」として格納される。この結果、フリーページチェーンＦＰＣが新たに形成される。
【００７６】
ステップＳ５５又はＳ５６の処理が終了すると、制御部１２は、ページチェーンＰＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じであるか否かを判断する（ステップＳ５７）。ステップＳ５７の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｄ、１１Ｆ及びオフセット値格納部１１Ｅ、１１Ｇからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。この後、ページ番号「ＷＰＰｋ」とオフセット値「ＷＰＯｋ」とから成るライトポインタ「ＷＰｋ」と、ページ番号「ＲＰＰｋ」とオフセット値「ＲＰＯｋ」とから成るリードポインタ「ＲＰｋ」とをポインタ格納メモリ１１から受け取ると、制御部１２は、上記判断をする。
ライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが異なると判断すると、制御部１２は、
ＲＰＰｋ←ＰＧ（ＲＰＰｋ）
ＲＰＯｋ←０
の処理をする（ステップＳ５８）。ステップＳ５８の処理は、図２９に示すように、ページチェーンＰＣｋの先頭ページの次ページ番号「ＰＧ」が示すページを、リードポインタ「ＲＰｋ」のページ番号「ＲＰＰｋ」が指し示すようにし、かつ、オフセット値「ＲＰＯｋ」を値「０」にする。
ステップＳ５８の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からページ番号「ＲＰＰｋ」を受け取ると、制御部１２は、ページ番号「ＲＰＰｋ」をページ信号ｂ５とする。この後、制御部１２は、ページ信号ｂ５と、読み出しを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。これにより、ページ格納メモリ１３から次ページ番号「ＰＧ」を受け取ると、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、ページ番号格納部１１Ｆに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして、ページ番号「ＰＧ」をポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１では、次ページ番号「ＰＧ」がページ番号「ＲＰＰｋ」として格納される。
【００７７】
この後、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｇに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして値「０」を送る。これにより、ポインタ格納メモリ１１では、値「０」がオフセット値「ＲＰＯ」として格納され、ステップＳ５８の処理が終了する。
また、ステップＳ５７で、ライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じと判断すると、制御部１２は、ページチェーンＰＣｋの有無データ「Ｅｋ」を値「０」にする（ステップＳ５９）。
さらに、ステップＳ５２で、ページチェーンＰＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが異なり、オフセット値「ＲＰＯｋ」が値「Ｌ−１」と異なると、制御部１２は、オフセット値「ＲＰＯｋ」の値「１」を加える（ステップＳ６０）。
【００７８】
ステップＳ６０の処理のために、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｇからの読み出しを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。これにより、ポインタ格納メモリ１１からオフセット値「ＲＰＯｋ」を受け取ると、制御部１２は、値「ＲＰＯｋ」に値「１」を加える。この後、制御部１２は、ページチェーンＰＣｋを示すポート信号ｂ１と、オフセット値格納部１１Ｇに対する書き込みを示すアクセス指示信号ｂ２とをポインタ格納メモリ１１に送る。また、制御部１２は、書き込みデータとして、値「ＲＰＯｋ＋１」をポインタ格納メモリ１１に送る。これにより、値「ＷＰＯｋ＋１」がオフセット値「ＲＰＯｋ」として格納され、ステップＳ６０の処理が終了する。
【００７９】
次に、この実施の形態の動作について説明する。
入力ポート１１、１２…、１Ｎに入力されたセルは、多重部１で多重化されて、セルバッファメモリ２に送られる。多重部１から上記セルが出力されると、書き込み制御部４は、上記セルの行き先を調べる。上記セルの行き先が出力ポート３ｋであると、書き込み制御部４は、出力ポート３ｋを示すポート信号と、上記セルの格納要求を制御部１２に送る。
制御部１２は、上記格納要求を受け取ると、ステップＳ３１，Ｓ４１により、出力ポート３ｋに対応するページチェーンＰＣｋが有り、そのライトポインタ「ＷＰｋ」のオフセット値「ＷＰＯｋ」が値「Ｌ−１」と異なると、現在のオフセット値「ＷＰＯｋ」に値「１」を加えて、ライトポインタ「ＷＰｋ」が指し示す格納領域を１つ移動して、ライトポインタ「ＷＰｋ」が未使用領域を指し示すようにする。そして、ステップＳ４２により、制御部１２は、ライトポインタ「ＷＰｋ」が指し示す未使用領域に、空きアドレス管理メモリ９から受け取った空きバッファアドレスを、バッファアドレス「ＢＡ」として格納する。
【００８０】
また、上記格納要求を受け取り、ステップＳ３１により、ページチェーンＰＣｋが無い、又は、そのライトポインタ「ＷＰｋ」のオフセット値「ＷＰＯｋ」が値「Ｌ−１」であると、制御部１２は、ライトポインタ「ＷＰｋ」が指し示すページには、未使用領域が無いと判断する。この後、制御部１２は、ステップＳ３２でフリーページチェーンＦＰＣが無ければ、ステップＳ４３により、書き込み制御部４に対して、多重部１からのセルを破棄するように制御する。
ステップＳ３２でフリーページチェーンＦＰＣが有ると、制御部１２は、ステップＳ３３により、書き込み制御部４に対して、入力されたセルの格納を許可する。この後、制御部１２は、ステップＳ３４で、ページチェーンＰＣｋが有ると、制御部１２は、ステップＳ３５，Ｓ３６により、フリーページチェーンＦＰＣの先頭のページをページチェーンＰＣｋの最後に繋げて、ページチェーンＰＣｋにバッファアドレス格納用の未使用領域を確保する。この後、制御部１２は、リードポインタ「ＲＰｋ」がページチェーンＰＣｋの最後のページを指し示すようにする。また、ステップＳ３４で、ページチェーンＰＣｋが無いと、制御部１２は、ステップＳ３７により、新たなページチェーンＰＣｋを生成し、バッファアドレス格納用の未使用領域を確保する。
【００８１】
未使用領域の確保が終了し、ステップＳ３８でフリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」とページ番号「ＲＰＰＦ」とが異なると、制御部１２は、フリーページチェーンＦＰＣがまだ有ると判断し、ステップＳ３９により、フリーページチェーンＦＰＣの新たな先頭のページに、ページ番号「ＲＰＰＦ」を移す。また、ステップＳ３８で、フリーページチェーンＦＰＣのページ番号「ＷＰＰＦ」とページ番号「ＲＰＰＦ」とが同じであると、制御部１２は、ステップＳ４０フリーページチェーンＦＰＣが無いと判断する。
この後、ステップＳ４２により、制御部１２は、ライトポインタ「ＷＰｋ」が指し示す未使用領域に、空きアドレス管理メモリ９から受け取った空きバッファアドレスを、バッファアドレス「ＢＡ」として格納する。
こうして、入力されたセルのバッファアドレス「ＢＡ」は、ページチェーンＰＣｋの最後のページに格納される。
【００８２】
ところで、セルが出力ポート３ｋに出力されるとき、読み出し制御部５は、出力ポート３ｋとバッファアドレスの出力指示とを制御部１２に送る。これにより、制御部１２は、ステップＳ５１により、アドレス格納メモリ１４を制御する。アドレス格納メモリ１４は、出力ポート３ｋに対応するページチェーンＰＣｋのリードポインタ「ＲＰｋ」が指し示すバッファアドレス「ＢＡ」を読み出して、バッファアドレス「ＢＡ」をセルバッファメモリ２及び空きアドレス管理メモリ９に送る。空きアドレス管理メモリ９は、バッファアドレス「ＢＡ」で指定された格納領域からセルを読み出して、出力ポート３ｋに送る。また、空きアドレス管理メモリ９は、バッファアドレス「ＢＡ」を空きバッファアドレスとして管理する。
【００８３】
アドレス格納メモリ１４がバッファアドレス「ＢＡ」を出力すると、制御部１２は、ステップＳ５２，Ｓ６０により、ページチェーンＰＣｋのライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが同じ、又は、リードポインタ「ＲＰｋ」のオフセット値「ＲＰＯｋ」が値「Ｌ−１」と異なると、現在のオフセット値「ＲＰＯｋ」に値「１」を加えて、リードポインタ「ＲＰｋ」が指し示す格納領域を１つ移動する。これにより、リードポインタ「ＲＰｋ」が次のバッファアドレスを指し示す。
ステップＳ５２により、ページチェーンＰＣｋのライトポインタ「ＷＰｋ」とリードアポインタ「ＲＰｋ」とが異なり、リードポインタ「ＲＰｋ」のオフセット値「ＲＰＯｋ」が値「Ｌ−１」であると、制御部１２は、リードポインタ「ＲＰｋ」が指し示すページには、バッファアドレス「ＢＡ」が無いと判断する。この後、ステップＳ５３でフリーページチェーンＦＰＣが有ると、制御部１２は、ステップＳ５４，Ｓ５５により、リードポインタ「ＲＰｋ」が指し示すページをフリーページチェーンＦＰＣの最後に繋げて、上記ページをフリーページチェーンＦＰＣに組み込む。また、ステップＳ５３で、フリーページチェーンＦＰＣが無いと、制御部１２は、ステップＳ５６により、新たなフリーページチェーンＦＰＣを生成する。
【００８４】
ライトポインタ「ＷＰｋ」が指し示すページの、フリーページチェーンＦＰＣへの組み込みが終了し、ステップＳ５７で、ライトポインタ「ＷＰｋ」とリードポインタ「ＲＰｋ」とが異なると、制御部１２は、ページチェーンＰＣｋが有ると判断し、ステップＳ５８の処理により、リードポインタ「ＲＰｋ」がページチェーンＰＣｋの先頭のページを指し示すようにする。また、ステップＳ５７で、ライトポインタ「ＷＡｋ」とリードポインタ「ＲＡｋ」とが同じであると、制御部１２は、ページチェーンＰＣｋが無いとして処理を終了する。
【００８５】
このように、この実施の形態の構成によれば、第１の実施の形態に比べて、アドレス格納メモリ８の次ポインタ格納部８Ａを不要にすることができる。例えば、アドレス格納メモリ８に６４ｋ個のバッファアドレスが格納することができる場合、次ポインタ格納部８Ａには、
１６ｂｉｔ×６４ｋ＝１０２４ｋｂｉｔ
の容量を必要とする。これに対して、１ページに２５６個のバッファアドレスを格納することができる場合、ページ格納メモリ１３には、
８ｂｉｔ×２５６＝２ｋｂｉｔ
の容量だけが必要である。この結果、ページ格納メモリ１３による容量増加に比べて、次ポインタ格納部８Ａによる容量減少の方が大きいので、メモリ容量を削減することができる。
【００８６】
◇第２の実施の形態
次に、この発明の第２の実施の形態について説明する。
図３０は、この発明の第２の実施の形態であるＡＴＭスイッチ回路の構成を概略示すブロック図、図３１は、同ＡＴＭスイッチ回路のセルバッファメモリの構成を示す構成図、図３２は、同ＡＴＭスイッチ回路のチェーン構造を説明する説明図、図３３は、同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図、図３４は、同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャート、図３５は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図３６は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図３７は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図３８は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図３９は、同ＡＴＭスイッチ回路の制御部の、セル出力の処理を示すフローチャート、図４０は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図４１は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図４２は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図、図４３は、同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【００８７】
このＡＴＭスイッチ回路は、図３０に示すように、多重部１、分離部３、書き込み制御部４、読み出し制御部５、ページ格納メモリ１３、セルバッファメモリ２１、制御部２２及びアドレス格納メモリ２３を備えてなっている。なお、図３０において、図１及び図１５と同じものについては、図１及び図１５と同じ符号を付与して、その説明を省略する。
セルバッファメモリ２１はセルを格納する。このとき、セルバッファメモリ２１は、図３１に示すように、上記セルを格納領域にそれぞれ格納するものであり、セル「ＣＥ」を格納するための、「Ｌ」個の格納領域をまとめて、論理的なページとしている。すなわち、セルバッファメモリ２１では、ページ番号「１」が、「０」〜「Ｌ−１」のオフセット値で示される格納領域を持つ。同じようにして、ページ番号「２」、…、「Ｍ」は、「０」〜「Ｌ−１」のオフセット値で示される格納領域をそれぞれ持つ。そして、各セル「ＣＥ」は、上記ページ番号と上記オフセット値とにより特定される。
【００８８】
セルバッファメモリ２１では、ページ格納メモリ１３の次ページ番号「ＰＧ」により、図３２に示すように、出力ポート３１、３２、…、３Ｎに対応してページチェーンＢＰＣ１、ＢＰＣ２、…、ＢＰＣＮが形成される。また、セルバッファメモリ２１の中で、セルが格納されていない、未使用領域からなるフリーページも、同じようにして、ページ格納メモリ１３の次ページ番号「ＰＧ」によって順に繋げられて、論理的なチェーン構造にされる。これにより、フリーページチェーンＢＦＰＣが形成される。
アドレス格納メモリ２３は、図３３に示すように、チェーン有無格納部２３Ａ、ライトアドレス格納部２３Ｂ及びリードアドレス格納部２３Ｃを備えてなっている。さらに、ライトアドレス格納部２３Ｂは、ページ番号格納部２３Ｄとオフセット値格納部２３Ｅとを備え、リードアドレス格納部２３Ｃは、ページ番号格納部２３Ｆとオフセット値格納部２３Ｇとを備えてなっている。
【００８９】
チェーン有無格納部２３Ａには、出力ポート３１、３２、…、３Ｎに対応して設けられるページチェーンＢＰＣ１、ＢＰＣ２、…、ＢＰＣＮの有無を示す有無データ「Ｅ１」、「Ｅ２」、…、「ＥＮ」が格納される。同じようにして、チェーン有無格納部２３Ａには、フリーページチェーンＢＦＰＣの有無を示す有無データ「ＥＦ」が格納される。
ページ番号格納部２３Ｄには、ページチェーンＢＰＣ１のライトアドレス「ＷＡ１」のページ番号「ＷＡＰ１」が格納される。ライトアドレス「ＷＡ１」のページ番号が「ＷＡＰ１」であるとき、ページ番号「ＷＡＰ１」のオフセット値「ＷＡＯ１」がオフセット値格納部２３Ｅに格納される。オフセット値「ＷＡＯ１」は、ページ番号「ＷＡＰ１」で指定されたページ内の格納領域を指定するものである。
【００９０】
同じようにして、ページ番号格納部２３Ｄには、ページチェーンＢＰＣ２、…、ＢＰＣＮのライトアドレス「ＷＡ２」、…、「ＷＡＮ」のページ番号「ＷＡＰ２」、…、「ＷＡＰＮ」が格納され、オフセット値格納部２３Ｅには、ページ番号「ＷＡＰ２」、…、「ＷＡＰＮ」のオフセット値「ＷＡＯ２」、…、「ＷＡＯＮ」が格納される。また、ページ番号格納部２３Ｄは、フリーページチェーンＢＦＰＣのライトアドレスがページ番号「ＷＡＰＦ」として格納される。
ページ番号格納部２３Ｆには、ページチェーンＢＰＣ１、ＢＰＣ２、…、ＢＰＣＮのリードアドレス「ＲＡ１」、「ＲＡ２」、…、「ＲＡＮ」のページ番号「ＲＡＰ１」、「ＲＡＰ２」…、「ＲＡＰＮ」が格納され、オフセット値格納部２３Ｇには、ページ番号「ＲＡＰ１」、「ＲＡＰ２」、…、「ＲＡＰＮ」のオフセット値「ＲＡＯ１」、「ＲＡＯ２」、…、「ＲＡＯＮ」が格納される。また、ページ番号格納部２３Ｆには、フリーページチェーンＢＦＰＣのリードアドレスとしてページ番号「ＲＡＰＦ」として格納される。
【００９１】
制御部２２は、書き込み制御部４から格納要求を受け取ると、図３４に示す処理をする。ここでは、多重部１から出力されるセルが出力ポート３ｋに送られるものとする。制御部２２は、上記格納要求を受け取ると、出力ポート３ｋに対応するページチェーンＢＰＣｋ示すポート信号ｃ３と、チェーン有無格納部２３Ａ及びオフセット値格納部２３Ｅからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、アドレス格納メモリ２３から有無データ「Ｅｋ」及びオフセット値「ＷＡＯｋ」を受け取ると、制御部２２は、データ「Ｅｋ」が値「１」であり、オフセット値「ＷＡＯｋ」が値「Ｌ−１」ではないか否かを判断する。（ステップＳ６１）。ステップＳ６１の処理は、ページチェーンＢＰＣｋが有る場合に、ライトアドレス「ＷＰｋ」が指し示すページには、空きの格納領域が有るか否かを調べるものである。
ステップＳ６１により、ページチェーンＢＰＣｋが無い、又は、オフセット値「ＷＡＯｋ」が値「Ｌ−１」と同じであると判断すると、フリーページチェーンＢＦＰＣの有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ６２）。ステップＳ６２により、フリーページチェーンＢＦＰＣが有ると判断すると、制御部２２は、ページチェーンＢＰＣｋの有無データ「Ｅｋ」が「０」か否かを判断する（ステップＳ６３）。
【００９２】
ステップＳ６３により、ページチェーンＢＰＣｋが有ると判断すると、制御部２２は、
ＰＧ（ＷＡＰｋ）←ＲＡＰＦ
の処理をする（ステップＳ６４）。ステップＳ６４の処理は、図３５に示すように、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示すページを、ページチェーンＢＰＣｋの最後のページの次ページ番号「ＰＧ」が指し示しようにする。上記最後のページは、ライトアドレスＷＡｋが指し示すページである。ステップＳ６４の処理のために、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰＦ」を受け取ると、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｄからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、アドレス格納メモリ２３から、ページチェーンＢＰＣｋのページ番号「ＷＡＰｋ」を受け取ると、制御部２２は、ページ番号「ＷＡＰｋ」をページ信号ｂ５とする。この後、制御部２２は、ページ信号ｂ５と、書き込みを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。
また、制御部２２は、書き込みデータとして、ページ番号「ＲＡＰＦ」をページ格納メモリ１３に送る。これにより、ページ格納メモリ１３のページ番号「ＷＡＰｋ」に対応する格納領域には、次ページ番号「ＰＧ」としてページ番号「ＲＡＰＦ」が格納される。この結果、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示すページを、ライトアドレス「ＷＡｋ」が指し示すページの次ページ番号「ＰＧ」が指し示すようになる。
【００９３】
ステップＳ６４が終了すると、制御部２２は、
ＷＡＰｋ←ＲＡＰＦ
ＷＡＯｋ←０
の処理をする（ステップＳ６５）。ステップＳ６５の処理は、図３６に示すように、ページ番号「ＲＡＰＦ」が指し示すページを、ページ番号「ＷＡＰｋ」が指し示すようにすると共に、ライトアドレス「ＷＡｋ」のオフセット値「ＷＡＯｋ」を値「０」にする。
ステップＳ６５の処理のために、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰＦ」を受け取ると、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｄに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとしてページ番号「ＲＡＰＦ」をアドレス格納メモリ２３に送る。これにより、ページ番号「ＲＡＰＦ」がページ番号「ＷＡＰｋ」として格納される。
【００９４】
この後、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｅに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「０」をアドレス格納メモリ２３に送る。
これにより、値「０」がリードアドレスＷＡｋのオフセット値「ＷＡＯｋ」として格納される。この結果、ページ番号「ＲＡＰＦ」が指し示すページを、ページ番号「ＷＡＰｋ」が指し示すようになる。
また、ステップＳ６３で、ページチェーンＢＰＣｋが無い場合、制御部２２は、
ＲＡＰｋ←ＲＡＰＦ、ＲＡＯｋ←０
ＷＡＰｋ←ＲＡＰＦ、ＷＡＯｋ←０
Ｅｋ←１
の処理をする（ステップＳ６６）。ステップＳ６６の処理は、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示す未使用領域を、ページチェーンＢＰＣｋのリードアドレス「ＲＡｋ」のページ番号「ＲＡＰｋ」及びライトアドレス「ＷＡｋ」のページ番号「ＷＡＰｋ」が指し示すようにする。これにより、制御部２２は、出力ポート３ｋに対応するページチェーンＢＰＣｋを新たに形成する。そして、制御部２２は、アドレス格納メモリ２３の有無データ「Ｅｋ」を「１」にする。
【００９５】
ステップＳ６６の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｅ，２３Ｇに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして「０」をアドレス格納メモリ２３に送る。これにより、値「０」がオフセット値「ＲＡＯｋ」、「ＷＡＯｋ」として格納される。
この後、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰＦ」を受け取ると、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｄ，２３Ｆに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして、ページ番号「ＲＡＰＦ」をアドレス格納メモリ２３に送る。この結果、リードアドレス「ＲＡＰＦ」が、リードアドレス「ＲＡｋ」のページ番号「ＲＡＰｋ」及びライトアドレス「ＷＡｋ」のページ番号「ＷＡＰｋ」として格納される。
【００９６】
この後、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、チェーン有無格納部２３Ａに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「１」をアドレス格納メモリ２３に送る。これにより、値「１」が有無データ「Ｅｋ」として格納される。この結果、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示す未使用領域を、ページチェーンＢＰＣｋのリードアドレス「ＲＡｋ」のページ番号「ＲＡＰｋ」及びライトアドレス「ＷＡｋ」のページ番号「ＷＡＰｋ」が指し示すようになる。
ステップＳ６５又はステップＳ６６が終了すると、制御部２２は、フリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」とページ番号「ＲＡＰＦ」とが同じであるか否かを判断する（ステップＳ６７）。ステップＳ６７の処理のために、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｄ、２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３からフリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」、「ＲＡＰＦ」を受け取ると、制御部２２は上記判断をする。
ステップＳ６７の処理が終了すると、制御部２２は、
ＲＡＰＦ←ＰＧ（ＲＡＰＦ）
の処理をする（ステップＳ６８）。ステップＳ６８の処理は、図３７に示すように、フリーページチェーンＢＦＰＣの次ページ番号「ＰＧ」が指し示すページを、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示すようにする。これにより、制御部２２は、ページ番号「ＲＡＰＦ」をフリーページチェーンＢＦＰＣの先頭ページに移動する。
【００９７】
ステップＳ６８の処理のために、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とを、アドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰＦ」を受け取ると、制御部２２は、ページ番号「ＲＡＰＦ」をページ信号ｂ５とする。この後、制御部２２は、ページ信号ｂ５と、読み出しを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。これにより、ページ格納メモリ１３から次ページ番号「ＰＧ」を受け取ると、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｆに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして、次ページ番号「ＰＧ」をアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３では、次ページ番号「ＰＧ」がページ番号「ＲＡＰＦ」として格納される。この結果、フリーページチェーンＢＦＰＣの次ページ番号「ＰＧ」が指し示すページを、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」が指し示すようになる。
【００９８】
また、先のステップＳ６７で、フリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」とページ番号「ＲＡＰＦ」とが同じであると、制御部２２は、フリーページチェーンＢＦＰＣの有無データ「ＥＦ」を値「０」にする（ステップＳ６９）。この処理により、フリーページチェーンＢＦＰＣが無いことが示される。さらに、先のステップＳ６１で、ページチェーンＢＰＣｋが有り、オフセット値「ＷＡＯｋ」が値「Ｌ−１」と異なると、制御部２２は、オフセット値「ＷＡＯｋ」値を「１」を加える（ステップＳ７０）。
ステップＳ７０の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｅからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からオフセット値「ＷＡＯｋ」を受け取ると、制御部２２は、オフセット値「ＷＡＯｋ」に値「１」を加える。この後、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｅに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして、値「ＷＡＯｋ＋１」をアドレス格納メモリ２３に送る。これにより、値「ＷＡＯｋ＋１」がオフセット値「ＷＡＯｋ」として格納される。
【００９９】
ステップＳ６８、ステップＳ６９又はステップＳ７０が終了すると、制御部２２は、
セル（ＷＡｋ）←入力セル
の処理をする（ステップＳ７１）。ステップＳ７１は次の処理である。すなわち、図３８に示すように、ライトアドレス「ＷＡｋ」が指し示す未使用領域に、セルを格納するための制御をする。
ステップＳ７１のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｄ及びオフセット値格納部２３Ｅからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＷＡＰｋ」とオフセット値「ＷＡＯｋ」とから成るライトアドレス「ＷＡｋ」を受け取る。制御部２２は、ライトアドレス「ＷＡｋ」をアドレス信号ｃ１とする。この後、制御部２２は、アドレス信号ｃ１と、書き込みを示すアクセス指示信号ｃ２とをセルバッファメモリ２１に送る。これにより、セルバッファメモリ２１では、ライトアドレス「ＷＡｋ」が指し示す未使用領域にセルが格納される。
【０１００】
また、先のステップＳ６２で、フリーページチェーンＢＰＦＣが無ければ、制御部２２は、セルバッファメモリ２１に対して、入力されたセルを破棄するための制御を行い（ステップＳ７２）、図３４の処理を終了する。
ところで、制御部２２は、読み出し制御部５から出力ポート３ｋとセルの出力指示とを受け取ると、図３９に示す処理を開始する。すなわち、制御部２２は、出力ポート３ｋと出力指示とを受け取ると、セルを出力する（ステップＳ８１）。ステップＳ８１の処理は、図４０に示すように、ページチェーンＢＰＣｋが出力ポート３ｋに対応するので、ページチェーンＢＰＣｋのリードアドレス「ＲＡｋ」が指し示すセル「ＣＥ」を、出力するためのものである。
【０１０１】
ステップＳ８１の処理のために、制御部２２は、ページチェーンＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆ及びオフセット値格納部２３Ｇからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３から、ページ番号「ＲＡＰｋ」とオフセット値「ＲＡＯｋ」から成るリードアドレス「ＲＡｋ」を受け取ると、制御部２２は、リードアドレス「ＲＡｋ」をアドレス信号ｃ１とする。この後、制御部２２は、このアドレス信号ｃ１と、書き込みを示すアクセス指示信号ｃ２とを、セルバッファメモリ２１に送る。これにより、セルバッファメモリ２１は、ページ番号「ＲＡＰｋ」とオフセット値「ＲＡＯｋ」とで特定される格納領域からセルを読み出して、分離部３に送る。
ステップＳ８１が終了すると、制御部２２は、ページチェーンＢＰＣｋのライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」と異なり、オフセット値「ＲＡＯｋ」が値「Ｌ−１」でないか否かを判断する（ステップＳ８２）。
【０１０２】
ステップＳ８２の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｄ，２３Ｆ及びオフセット値格納部２３Ｅ，２３Ｇからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、ページ番号「ＷＡＰｋ」とオフセット値「ＷＡＯｋ」とから成るライトアドレス「ＷＡｋ」と、ページ番号「ＲＡＰｋ」とオフセット値「ＲＡＯｋ」とから成るリードアドレス「ＲＡｋ」とをアドレス格納メモリ２３から受け取る。
ステップＳ８２により、ライトアドレス「ＷＡｋ」と、リードアドレス「ＲＡｋ」とが同じである、又は、オフセット値「ＲＡＯｋ」が値「Ｌ−ｌ」に等しい場合、制御部２２は、フリーページチェーンＢＦＰＣの有無データ「ＥＦ」が値「０」か否かを判断する（ステップＳ８３）。このために、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、チェーン有無格納部２３Ａからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、アドレス格納メモリ２３から有無データ「ＥＦ」を受け取ると、制御部２２が上記判断をする。
【０１０３】
ステップＳ８３により、フリーページチェーンＢＦＰＣが有ると判断すると、制御部２２は、
ＰＧ（ＷＡＰＦ）←ＲＡＰｋ
の処理をする（ステップＳ８４）。ステップＳ８４の処理は、図４１に示すように、ページ番号「ＲＡＰｋ」が指し示すページを、次ページ番号「ＰＧ」が指し示すようにする。次ページ番号「ＰＧ」は、フリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」が指し示すページである。
ステップＳ８４の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、アドレス格納メモリ２３からページ番号「ＲＡＰｋ」を受け取ると、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｄからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。この後、アドレス格納メモリ２３からページ番号「ＷＡＰＦ」を受け取ると、制御部２２は、ページ番号「ＷＡＰＦ」をページ信号ｂ５とする。この後、制御部２２は、ページ信号ｂ５と、書き込みを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。また、制御部２２は、書き込みデータとして、ページ番号「ＲＡＰｋ」をページ格納メモリ１３に送る。この結果、ページ格納メモリ１３のページ番号「ＷＡＰＦ」に対応する格納領域には、次ページ番号「ＰＧ」として値「ＲＡＰｋ」が格納される。この結果、ページ番号「ＲＡＰｋ」が指し示すページを、次ページ番号「ＰＧ」が指し示すようになる。
【０１０４】
ステップＳ８４の処理が終了すると、制御部２２は、
ＷＡＰＦ←ＲＡＰｋ
の処理をする（ステップＳ８５）。ステップＳ８５の処理は、図４２に示すように、ページ番号「ＲＡＰｋ」が指し示すページを、ページ番号「ＷＡＰＦ」が指し示すようにする。
ステップＳ８５の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰｋ」を受け取ると、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｄに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「ＲＡＰｋ」をアドレス格納メモリ２３に送る。これにより、値「ＲＡＰｋ」がページ番号「ＷＡＰＦ」として格納される。この結果、ページ番号「ＲＡＰｋ」が指し示すページを、ページ番号「ＷＡＰＦ」が指し示すようになる。
【０１０５】
また、ステップＳ８３で、フリーページチェーンＢＦＰＣが無い場合、制御部２２は、
ＲＡＰＦ←ＲＡＰｋ
ＷＡＰＦ←ＲＡＰｋ
ＥＦ←１
の処理をする（ステップＳ８６）。ステップＳ８６の処理は、ページチェーンＢＰＣｋのページ番号「ＲＡＰｋ」が指し示すページを、フリーページチェーンＢＦＰＣのページ番号「ＲＡＰＦ」及びページ番号「ＷＡＰＦ」が指し示すようにする。これにより、制御部２２は、フリーページチェーンＢＦＰＣを新たに形成する。そして、制御部２２は、アドレス格納メモリ２３の有無データ「ＥＦ」を「１」にする。
ステップＳ８６の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰｋ」を受け取ると、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、ページ番号格納部２３Ｄ，２３Ｆに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「ＲＡＰｋ」をアドレス格納メモリ２３に送る。この結果、値「ＲＡＰｋ」がページ番号「ＷＡＰＦ」及びページ番号「ＲＡＰＦ」として格納される。この後、制御部２２は、フリーページチェーンＢＦＰＣを示すポート信号ｃ３と、チェーン有無格納部２３Ａに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「１」をアドレス格納メモリ２３に送る。これにより、値「１」が有無データ「ＥＦ」として格納される。この結果、フリーページチェーンＢＦＰＣが新たに形成される。
【０１０６】
ステップＳ８５又はＳ８６の処理が終了すると、制御部２２は、ページチェーンＢＰＣｋのライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが同じであるか否かを判断する（ステップＳ８７）。ライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが異なると判断すると、制御部２２は、
ＲＡＰｋ←ＰＧ（ＲＡＰｋ）
ＲＡＯｋ←０
の処理をする（ステップＳ８８）。ステップＳ８８の処理は、図４３に示すように、ページチェーンＢＰＣｋの先頭ページの次ページ番号「ＰＧ」が示すページを、リードアドレス「ＲＡｋ」のページ番号「ＲＡＰｋ」が指し示すようにし、かつ、オフセット値「ＲＡＯｋ」を値「０」にする。
ステップＳ８８の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からページ番号「ＲＡＰｋ」を受け取ると、制御部２２は、ページ番号「ＲＡＰｋ」をページ信号ｂ５とする。この後、制御部２２は、ページ信号ｂ５と、読み出しを示すアクセス指示信号ｂ６とをページ格納メモリ１３に送る。これにより、ページ格納メモリ１３から次ページ番号「ＰＧ」を受け取ると、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、ページ番号格納部２３Ｆに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして、ページ番号「ＰＧ」をアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３では、次ページ番号「ＰＧ」がページ番号「ＲＡＰｋ」として格納される。
【０１０７】
この後、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｇに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして値「０」を送る。これにより、アドレス格納メモリ２３では、値「０」がオフセット値「ＲＡＯｋ」として格納され、ステップＳ８８の処理が終了する。
また、ステップＳ８７で、ライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが同じと判断すると、制御部２２は、ページチェーンＢＰＣｋの有無データ「Ｅｋ」を値「０」にする（ステップＳ８９）。
さらに、ステップＳ８２で、ページチェーンＢＰＣｋのライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが異なり、オフセット値「ＲＡＯｋ」が値「Ｌ−１」と異なると、制御部２２は、オフセット値「ＲＡＯｋ」の値「１」を加える（ステップＳ９０）。
ステップＳ９０の処理のために、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｇからの読み出しを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。これにより、アドレス格納メモリ２３からオフセット値「ＲＡＯｋ」を受け取ると、制御部２２は、値「ＲＡＯｋ」に値「１」を加える。この後、制御部２２は、ページチェーンＢＰＣｋを示すポート信号ｃ３と、オフセット値格納部２３Ｇに対する書き込みを示すアクセス指示信号ｃ４とをアドレス格納メモリ２３に送る。また、制御部２２は、書き込みデータとして、値「ＲＡＯｋ＋１」をアドレス格納メモリ２３に送る。これにより、値「ＲＡＯｋ＋１」がオフセット値「ＲＡＯｋ」として格納され、ステップＳ９０の処理が終了する。
【０１０８】
次に、この実施の形態の動作について説明する。
入力ポート１１、…、１Ｎに入力されたセルは、多重部１で多重化されて、セルバッファメモリ２１に送られる。多重部１から上記セルが出力されると、書き込み制御部４は、上記セルの行き先を調べる。上記セルの行き先が出力ポート３ｋであると、書き込み制御部４は、出力ポート３ｋを示すポート信号と、上記セルの格納要求を制御部２２に送る。
制御部２２は、上記格納要求を受け取ると、ステップＳ６１，Ｓ７０により、出力ポート３ｋに対応するページチェーンＢＰＣｋが有り、そのライトアドレス「ＷＡｋ」のオフセット値「ＷＡＯｋ」が値「Ｌ−１」と異なると、現在のオフセット値「ＷＡＯｋ」に値「１」を加えて、ライトアドレス「ＷＡｋ」が指し示す格納領域を１つ移動して、ライトアドレス「ＷＡｋ」が未使用領域を指し示すようにする。そして、ステップＳ７１により、制御部２２は、セルバッファメモリ２１を制御して、ライトアドレス「ＷＡｋ」が指し示す未使用領域に、多重部１からのセルを格納する。
【０１０９】
また、上記格納要求を受け取り、ステップＳ６１により、ページチェーンＢＰＣｋが無い、又は、そのライトアドレス「ＷＡｋ」のオフセット値「ＷＡＯｋ」が値「Ｌ−１」であると、制御部２２は、ライトアドレス「ＷＡｋ」が指し示すページには、未使用領域が無いと判断する。この後、制御部２２は、ステップＳ６２でフリーページチェーンＢＦＰＣが無ければ、新たなセルを格納するための未使用領域が無いと判断して、ステップＳ７２により、セルバッファメモリ２１に対して、多重部１からのセルを破棄するように制御する。
ステップＳ６２でフリーページチェーンＢＦＰＣが有り、ステップＳ６３でページチェーンＢＰＣｋが有ると、制御部２２は、ステップＳ６４，Ｓ６５により、フリーページチェーンＢＦＰＣの先頭のページをページチェーンＢＰＣｋの最後に繋げて、ページチェーンＢＰＣｋにセル格納用の未使用領域を確保する。この後、制御部２２は、リードアドレス「ＲＡｋ」がページチェーンＢＰＣｋの最後のページ中で、最初の未使用領域を指し示すようにする。また、ステップＳ６３で、ページチェーンＢＰＣｋが無いと、制御部２２は、ステップＳ６６により、新たなページチェーンＢＰＣｋを生成し、セル格納用の未使用領域を確保する。
【０１１０】
未使用領域の確保が終了し、ステップＳ６７でフリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」とページ番号「ＲＡＰＦ」とが異なると、制御部２２は、フリーページチェーンＢＦＰＣがまだ有ると判断し、ステップＳ６８により、フリーページチェーンＢＦＰＣの新たな先頭のページに、ページ番号「ＲＡＰＰＦ」を移す。また、ステップＳ６７で、フリーページチェーンＢＦＰＣのページ番号「ＷＡＰＦ」とページ番号「ＲＡＰＦ」とが同じであると、制御部２２は、ステップＳ６９フリーページチェーンＢＦＰＣが無いと判断する。
この後、ステップＳ７１により、制御部２２は、セルバッファメモリ２１を制御して、ライトアドレス「ＷＡｋ」が指し示す未使用領域に、多重部１からのセルを格納する。
ところで、セルが出力ポート３ｋに出力されるとき、読み出し制御部５は、出力ポート３ｋとセルの出力指示とを制御部２２に送る。これにより、制御部２２は、ステップＳ８１により、アドレス格納メモリ２３から、リードアドレス「ＲＡｋ」を受け取る。この後、制御部２２は、リードアドレス「ＲＡｋ」が指し示す格納領域のセルを分離部３に出力するように、セルバッファメモリ２１を制御する。これにより、セルバッファメモリ２１は、指定された格納領域からセルを読み出して、分離部３に送る。分離部３は、受け取ったセルを出力ポート３ｋに送る。
【０１１１】
セルバッファメモリ２１がセルを出力すると、制御部２２は、ステップＳ８２，Ｓ９０により、出力ポート３ｋに対応するページチェーンＢＰＣｋのライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが異なり、リードアドレス「ＲＡｋ」のオフセット値「ＲＡＯｋ」が値「Ｌ−１」と異なると、現在のオフセット値「ＲＡＯｋ」に値「１」を加えて、リードアドレス「ＲＡｋ」が指し示す格納領域を１つ移動する。これにより、リードアドレス「ＲＡｋ」が次のセルの格納領域を指し示す。
ステップＳ８２により、ページチェーンＢＰＣｋのライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが同じである、又は、リードアドレス「ＲＡｋ」のオフセット値「ＲＡＯｋ」が値「Ｌ−１」であると、制御部２２は、リードアドレス「ＲＡｋ」が指し示すページには、セルが無いと判断する。この後、ステップＳ８３でフリーページチェーンＢＦＰＣが有ると、制御部２２は、ステップＳ８４，Ｓ８５により、リードアドレス「ＲＡｋ」が指し示すページをフリーページチェーンＢＦＰＣの最後に繋げて、上記ページをフリーページチェーンＢＦＰＣに組み込む。また、ステップＳ８３で、フリーページチェーンＢＦＰＣが無いと、制御部２２は、ステップＳ８６により、新たなフリーページチェーンＢＦＰＣを生成する。
【０１１２】
ライトアドレス「ＷＡｋ」が指し示すページの、フリーページチェーンＢＦＰＣへの組み込みが終了し、ステップＳ８７で、ライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが異なると、制御部２２は、ページチェーンＢＰＣｋが有ると判断し、ステップＳ８８の処理により、リードアドレス「ＲＡｋ」がページチェーンＢＰＣｋの先頭のページを指し示すようにする。また、ステップＳ８７で、ライトアドレス「ＷＡｋ」とリードアドレス「ＲＡｋ」とが同じであると、制御部２２は、ページチェーンＢＰＣｋが無いとして処理を終了する。
このように、この実施の形態の構成によれば、第２の実施の形態に比べて、空きアドレス管理メモリ９とアドレス格納メモリ１４と不要にして、メモリ容量を減らすことができる。
【０１１３】
以上、この発明の第１、第２の実施の形態を図面により詳述してきたが、具体的な構成は、上記実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等があっても、この発明に含まれる。例えば、各メモリとして個別のものを用いたが、１つのメモリを機能に応じて、分けて用いてもよい。
【０１１４】
【発明の効果】
以上、説明したように、この発明の構成によれば、セルバッファメモリにセルを格納する際のバッファアドレスや、格納されるセルをチェーン構造により管理するので、バッファアドレス管理手段用のメモリを、すべての出力ポートで共有することができる。
この結果、出力ポートが増えることにより発生する、上記メモリの増加を防ぎ、かつ、上記メモリの使用効率の低下を防止することができる。
【図面の簡単な説明】
【図１】この発明の参考例であるＡＴＭスイッチ回路の構成を概略示すブロック図である。
【図２】同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図である。
【図３】同ＡＴＭスイッチ回路のチェーン構造を説明する説明図である。
【図４】同ＡＴＭスイッチ回路のポインタ格納メモリの構成を示す構成図である。
【図５】同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャートである。
【図６】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図７】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図８】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図９】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図１０】同ＡＴＭスイッチ回路の制御部による、セル出力の処理を示すフローチャートである。
【図１１】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図１２】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図１３】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図１４】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図１５】この発明の第１の実施の形態であるＡＴＭスイッチ回路の構成を概略示すブロック図である。
【図１６】同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図である。
【図１７】同ＡＴＭスイッチ回路のページ格納メモリの構成を示す構成図である。
【図１８】同ＡＴＭスイッチ回路のチェーン構造を説明する説明図である。
【図１９】同ＡＴＭスイッチ回路のポインタ格納メモリの構成を示す構成図である。
【図２０】同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャートである。
【図２１】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２２】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２３】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２４】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２５】同ＡＴＭスイッチ回路の制御部の、セル出力の処理を示すフローチャートである。
【図２６】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２７】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２８】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図２９】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図３０】この発明の第２の実施の形態であるＡＴＭスイッチ回路の構成を概略示すブロック図である。
【図３１】同ＡＴＭスイッチ回路のセルバッファメモリの構成を示す構成図である。
【図３２】同ＡＴＭスイッチ回路のチェーン構造を説明する説明図である。
【図３３】同ＡＴＭスイッチ回路のアドレス格納メモリの構成を示す構成図である。
【図３４】同ＡＴＭスイッチ回路の制御部による、セル格納の処理を示すフローチャートである。
【図３５】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図３６】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図３７】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図３８】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図３９】同ＡＴＭスイッチ回路の制御部の、セル出力の処理を示すフローチャートである。
【図４０】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図４１】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図４２】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図４３】同ＡＴＭスイッチ回路の制御部の処理によるポインタの移動を説明する説明図である。
【図４４】従来のＡＴＭスイッチ回路を示す構成図である。
【図１】
0003563257.tif 000002
【図２】
0003563257.tif 000003
【図３】
0003563257.tif 000004
【図４】
0003563257.tif 000005
【図５】
0003563257.tif 000006
【図６】
0003563257.tif 000007
【図７】
0003563257.tif 000008
【図８】
0003563257.tif 000009
【図９】
0003563257.tif 000010
【図１０】
0003563257.tif 000011
【図１１】
0003563257.tif 000012
【図１２】
0003563257.tif 000013
【図１３】
0003563257.tif 000014
【図１４】
0003563257.tif 000015
【図１５】
0003563257.tif 000016
【図１６】
0003563257.tif 000017
【図１７】
0003563257.tif 000018
【図１８】
0003563257.tif 000019
【図１９】
0003563257.tif 000020
【図２０】
0003563257.tif 000021
【図２１】
0003563257.tif 000022
【図２２】
0003563257.tif 000023
【図２３】
0003563257.tif 000024
【図２４】
0003563257.tif 000025
【図２５】
0003563257.tif 000026
【図２６】
0003563257.tif 000027
【図２７】
0003563257.tif 000028
【図２８】
0003563257.tif 000029
【図２９】
0003563257.tif 000030
【図３０】
0003563257.tif 000031
【図３１】
0003563257.tif 000032
【図３２】
0003563257.tif 000033
【図３３】
0003563257.tif 000034
【図３４】
0003563257.tif 000035
【図３５】
0003563257.tif 000036
【図３６】
0003563257.tif 000037
【図３７】
0003563257.tif 000038
【図３８】
0003563257.tif 000039
【図３９】
0003563257.tif 000040
【図４０】
0003563257.tif 000041
【図４１】
0003563257.tif 000042
【図４２】
0003563257.tif 000043
【図４３】
0003563257.tif 000044
【図４４】
0003563257.tif 000045