JPH0836877A - キュー装置 - Google Patents

Abstract

(57)【要約】 【目的】 本発明はキュー装置に関し、キューが満杯に
なった場合でもキューにデータを書き込む装置が、キュ
ーに“空き”が生じるまで待たされることなくキューへ
のデータ出力を行えるようにすることを目的とする。 【構成】 オーバーフロー制御部３０は、ＦＩＦＯバッ
ファ１０が満杯になったことを検出すると、その後にＦ
ＩＦＯバッファ１０に対して書き込み要求がなされたデ
ータを、退避バッファ２０の書き込みポインタ３３に設
定されているアドレスに書き込み・退避させる。そし
て、フラグ３２をセットする。そして、該フラグ３２が
セットされている状態の間、ＦＩＦＯバッファ１０に対
する書き込みデータは退避バッファ２０に退避させる。
そして、その後、ＦＩＦＯバッファ１０に“空き”が生
じると、退避バッファ２０に退避させていたデータをＦ
ＩＦＯバッファ１０に転送させ、退避バッファ２０内に
退避データが無くなるとフラグ３２をリセットする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データの生成側と該デ
ータを利用する側との間でのデータの授受に用いられる
キュー装置に関する。

【０００２】

【従来の技術】キューは、データを生成する側（データ
生成装置）と該データを入力して利用する側（データ処
理装置）との間での処理タイミングの差異を吸収するた
めに利用される。該データには、例えば、メッセージ、
パケット、ジョブ、トランザクションなどがある。キュ
ーは、一般にＦＩＦＯ（First In First Out) メモリ
（ＦＩＦＯバッファ）などで実現され、データ生成装置
は、生成したデータをキューに入れ、データ処理装置は
そのデータをキューから取り出して所定の処理を行う。

【０００３】キューは、複数のデータを格納可能な容量
を持っており、このため、データ処理装置は、キューか
ら１つづつデータを取り出しながら、自己の処理能力に
応じて逐次データ処理することができる。また、キュー
を複数のデータ生成装置で共有することにより、１つの
データ処理装置が該複数のデータ生成装置からのデータ
処理要求を受け付けることが可能となる。さらに、各デ
ータ生成装置は、キューに空きがあるときには、いつで
も生成したデータを直ちにキューに入れることによっ
て、すぐに次の処理に移れるので効率的な動作が可能に
なる。

【０００４】

【発明が解決しようとする課題】しかしながら、従来の
キュー装置は以下のような問題点をかかえていた。 キューのデータ容量には限界があるため、キューが
満杯となり空き容量が無くなった場合には、データをキ
ューに投入する側、すなわちデータ生成装置は、該キュ
ーに空き領域が生じるまでそのデータの投入を待たねば
ならない。このため、データ生成装置側にとっては、キ
ューに空きが生じるまで待機していなければならず、そ
の間の待ち時間が処理効率の低下をもたらす。 また、データ処理装置として、ある一連のデータ列
をパケットとして処理するような装置がキューの出力側
に接続されている場合、キューにパケットの全データが
投入されるまでの間、該データ処理装置はそのパケット
処理を終了することができない。すなわち、データ生成
装置がパケットの全データをキューに投入するまで、デ
ータ処理装置は処理を中断しなければならない。したが
って、この場合には、キューにパケットの全データが投
入されてからパケットの取り出しを開始しないとパケッ
ト処理装置に待ち時間が生じ処理効率が低下することに
なる。 また、パケット処理においては、キューにパケット
データを投入中にそのデータを取り除く必要が生じる場
合があるが、パケット処理装置側が既にそのデータをキ
ューから取り出してパケット処理を開始しているときに
は、その出力済のデータを取り戻すのは不可能であっ
た。すなわち、この場合、そのパケットデータは廃棄さ
れることになる。このような場合は、例えばデータ生成
装置が複数のプログラム（プロセス）を並列して実行す
るプロセッサから成り、各プロセスがそれぞれ個別にパ
ケットを生成して共有キューにその書き込みを行うシス
テムにおいて発生する。すなわち、あるプロセスがキュ
ーにパケットデータを書き込んでいる途中で、実行権が
他のプロセスに切り換えられ、この新たにスケジューリ
ングされたプロセスがキューに自己の生成したパケット
データを続けて書き込もうとした場合である。

【０００５】本発明は、キューが満杯になった場合で
も、データ生成装置側が該キューに空きが生じるまで待
たされることなく、キューへのデータ投入操作を行える
ようにすることを目的とする。

【０００６】

【課題を解決するための手段】図１は、請求項１乃至３
記載の発明の原理を説明する図である。請求項１記載の
発明は、ＦＩＦＯバッファ１と、該ＦＩＦＯバッファに
書き込まれるデータが退避される退避バッファ２と、該
退避バッファにデータが退避されているか否かを示すフ
ラグ３を備える。また、さらに第１の検出手段４とデー
タ退避手段５を備える。

【０００７】第１の検出手段４は、上記ＦＩＦＯバッフ
ァ１の残り容量が予め定められた第１の閾値より少なく
なったことを検出する。データ退避手段５は、該第１の
検出手段４により上記ＦＩＦＯバッファ１の残り容量が
上記第１の閾値よりも少なくなったことが検出される
と、その後のＦＩＦＯバッファ１に対する書き込みデー
タを前記退避バッファ２に退避させると共に前記フラグ
３をセットさせ、該フラグがセットされている状態の
間、上記ＦＩＦＯバッファ１に対する書き込みデータを
前記退避バッファの方に書き込む。

【０００８】請求項２記載の発明は、上述した請求項１
が有する各構成要素に加え、さらに以下の手段を有す
る。第２の検出手段６は、前記フラグ３がセットされて
いる状態のときに、前記ＦＩＦＯバッファ１の残り容量
が予め定められた第２の閾値よりも多くなったことを検
出する。

【０００９】データリストア手段７は、該第２の検出手
段６よりＦＩＦＯバッファ１の残り容量が上記第２の閾
値よりも多くなったことが検出された際、前記退避バッ
ファ２に退避されていたデータを上記ＦＩＦＯバッファ
１に転送し、前記退避バッファ２に退避されているデー
タが無くなったときに前記フラグ３をリセットする。

【００１０】請求項３記載の発明は、上記請求項１が有
する各構成要素に加え、下記の第３の検出手段８を備え
る。第３の検出手段８は、前記退避バッファ２の残り容
量が予め定められた第３の閾値よりも少なくなったこと
を検出し、該検出時に例えば、割り込み信号などの特定
の信号を発生する。

【００１１】図２は、請求項４乃至８記載の発明の原理
を説明する図である。請求項４記載の発明は、パケット
が格納されるＦＩＦＯバッファ１１と、該ＦＩＦＯバッ
ファ１１に格納されるパケットの個数を計数する計数手
段１２とを備える。

【００１２】請求項５記載の発明は、上記請求項４記載
の発明が有する各構成要素に加え、前記ＦＩＦＯバッフ
ァ１１に書き込まれるパケットのデータが退避される退
避バッファ１３と、該退避バッファ１３にパケットデー
タが退避されているか否かを示すフラグ１４と、前記Ｆ
ＩＦＯバッファ１１の残り容量が予め定められた第１の
閾値よりも少なくなったことを検出する第１の検出手段
１５と、該第１の検出手段１５により前記ＦＩＦＯバッ
ファ１１の残り容量が前記第１の閾値よりも少なくなっ
たことが検出されると、その後のＦＩＦＯバッファ１１
に対する書き込みデータを前記退避バッファ１３に退避
させると共に、前記フラグ１４をセットさせ、該フラグ
がセットされている状態の間、上記ＦＩＦＯバッファ１
１に対する書き込みパケットデータを前記退避バッファ
の方に書き込むパケットデータ退避手段１６と、を更に
備える。

【００１３】前記ＦＩＦＯバッファ１１に格納される各
パケットデータには、例えば、請求項８記載のように該
パケットデータが当該パケットの最後のデータであるか
否かを示す情報が設定されたビットが付加されるように
してもよい。

【００１４】請求項６記載の発明は、上記請求項５記載
の発明が有する各構成要素に加え、前記フラグ１４がセ
ットされている状態のときに、前記計数手段の計数値が
予め定められた第２の閾値よりも少なくなったことを検
出する第２の検出手段１７と、該第２の検出手段１７に
より前記ＦＩＦＯバッファ１１に格納されているパケッ
ト数が上記第２の閾値よりも少なくなったことが検出さ
れた際、前記退避バッファ１３に退避されていたデータ
を上記ＦＩＦＯバッファ１１に転送し、前記退避バッフ
ァ１３に退避されているデータが無くなったときに前記
フラグ１４をリセットするデータリストア手段１８と、
をさらに備える。

【００１５】請求項９記載の発明は、上記請求項４記載
の発明が有する各構成要素に加え、前記計数手段１２の
計数値を参照して、前記ＦＩＦＯバッファ１１内に完結
しているパケットデータが存在するか否かを検出するパ
ケット完結検出手段１９を、さらに備える。

【００１６】図３は、請求項９乃至１１記載の発明の原
理を説明する図である。請求項９記載の発明は、パケッ
トサイズを示す情報が設定されているデータを有するパ
ケットが格納されるＦＩＦＯバッファ２１と、前記ＦＩ
ＦＯバッファ２１内に格納されているパケットデータの
個数を計数する計数手段２２と、該計数手段２２の計数
値と、前記ＦＩＦＯバッファ２１の先頭に格納されてい
るパケットの上記パケットサイズ情報が設定されている
データとを入力して、前記ＦＩＦＯバッファ２１内に完
結しているパケットが存在するか否かを検出するパケッ
ト完結検出手段２３と、を備える。

【００１７】請求項１０記載の発明は、上記請求項９の
発明が有する各構成要素に加え、前記ＦＩＦＯバッファ
２１に書き込まれるパケットのデータが退避される退避
バッファ２３と、該退避バッファ２３にパケットデータ
が退避されているか否かを示すフラグ２４と、前記ＦＩ
ＦＯバッファ２１の残り容量が予め定められた第１の閾
値よりも少なくなったことを検出する第１の検出手段２
５と、該第１の検出手段２５により前記ＦＩＦＯバッフ
ァ２１の残り容量が前記第１の閾値よりも少なくなった
ことが検出されると、その後のＦＩＦＯバッファ２１に
対する書き込みデータを前記退避バッファ２３に退避さ
せると共に、前記フラグ２４をセットさせ、該フラグ２
４がセットされている状態の間、上記ＦＩＦＯバッファ
２１に対する書き込みデータを前記退避バッファの方に
書き込むパケットデータ退避手段２６と、をさらに備え
る。

【００１８】請求項１１記載の発明は、上記請求項１０
記載の発明が有する各構成要素に加え、前記フラグ２４
がセットされている状態のときに、前記計数手段２２の
計数値が予め定められた第２の閾値よりも少なくなった
ことを検出する第２の検出手段２７と、該第２の検出手
段２７によりＦＩＦＯバッファ２１の残り容量が上記第
２の閾値よりも少なくなったことが検出された際、前記
退避バッファ２３に退避されていたデータを上記ＦＩＦ
Ｏバッファ２１に転送し、前記退避バッファ２３に退避
されているデータが無くなったときに前記フラグ２４を
リセットするデータリストア手段２８と、をさらに備え
る。

【００１９】次に、図４は請求項１２記載の発明を説明
する原理図である。請求項１２記載の発明は複数のプロ
セスによってパケットが書き込まれるＦＩＦＯバッファ
４１と、記憶手段４２と、プロセスＡが上記ＦＩＦＯバ
ッファ４１にパケットを書き込んでいる途中で別のプロ
セスＢに実行権が切り換えられた際、上記プロセスＡが
書き込んだ未完結のパケットデータを上記ＦＩＦＯバッ
ファ４１から取り出し上記記憶手段４２に退避させるデ
ータ退避手段４３と、再び前記プロセスＡに実行権が移
行した際、該プロセスＡの実行開始前に前記記憶手段４
２に退避させておいたパケットデータを前記ＦＩＦＯバ
ッファに転送させるデータリストア手段４４と、を備え
る。

【００２０】

【作用】請求項１の発明においては、第１の検出手段４
がＦＩＦＯバッファ１の残り容量が予め定められた第１
の閾値よりも少なくなったことを検出する。データ退避
手段５は、該検出後にＦＩＦＯバッファ１に対するデー
タの書き込み要求があると、該データを退避バッファ２
の方に書き込み、フラグ３をセットする。そして、該フ
ラグ３がセットされている状態の間、データ退避手段５
はＦＩＦＯバッファ１に対する書き込みデータを退避バ
ッファ２の方に書き込む。

【００２１】これにより、ＦＩＦＯバッファ１に対して
データを書き込むデータ生成装置は、ＦＩＦＯバッファ
１が満杯になっても、ＦＩＦＯバッファ１に空きが生ず
るまで待たされることなくデータの出力が可能になり、
処理効率が向上する。

【００２２】また、請求項２記載の発明においては、第
２の検出手段６がフラグ３がセットされている状態にお
いてＦＩＦＯバッファ１の残り容量が予め定められた所
定の閾値よりも多くなったことを検出する。データリス
トア手段７は、この検出を受けて、退避バッファ２に退
避されていたデータをＦＩＦＯバッファ１に転送する。
そして、退避バッファ２に退避データが無くなるとフラ
グ３をリセットする。

【００２３】これにより、退避バッファ２に退避されて
いたデータは正しい順序でＦＩＦＯバッファ１に書き込
まれる。そして、フラグ３がリセットされると、ＦＩＦ
Ｏ１に空きがある間再びＦＩＦＯバッファ１の方にデー
タが書き込まれる。

【００２４】請求項３記載の発明においては、第３の検
出手段８が退避バッファの残り容量が予め定められた第
３の閾値よりも少なくなった状態を検出し、その旨を示
す特定の信号を外部に出力する。

【００２５】これにより、例えば、プロセッサ等に割り
込みをかけ、退避バッファ２のサイズを拡張することが
可能になる。請求項４記載の発明においては、計数手段
１２によりＦＩＦＯバッファ１１に格納されるパケット
の個数が計数される、したがって、この計数手段１２の
計数値を参照することにより、ＦＩＦＯバッファ１１に
パケットが格納されているか否かを判断することが可能
になり、パケット処理装置２０は、ＦＩＦＯバッファ１
１内においてパケットが完結してからパケットのデータ
を連続して取り出すことが可能になり、パケット処理を
効率良く行うことができる。

【００２６】請求項５記載の発明においては、退避バッ
ファ１３、フラグ１４、第１の検出手段１５、及びパケ
ットデータ退避手段１６により、上述した請求項２記載
の発明と同様な動作が、ＦＩＦＯバッファ１１に対する
パケットデータの書き込みに対して行われる。したがっ
て、パケット生成装置１０はＦＩＦＯバッファ１１が満
杯になっても、ＦＩＦＯバッファ１１に空きが生ずるま
で待たされることなく、パケットデータの出力が可能と
なり、処理効率が向上する。

【００２７】請求項６記載の発明においては、第２の検
出手段１７がフラグ１４がセットされている状態のとき
に計数手段１２の計数値すなわちＦＩＦＯバッファ１１
内の格納パケット数が予め定められた第２の閾値よりも
少なくなったことを検出する。データリストア手段１８
は、この検出を受けて退避バッファ１３に退避されてい
たパケットデータをＦＩＦＯバッファ１１に転送する。
そして、退避バッファ１３に退避パケットデータが無く
なると、フラグ１４をリセットする。

【００２８】したがって、退避バッファ１３に退避され
ていたパケットが、その一部のデータが退避されていた
パケットも含め、正しい順序並びに正しい形式でＦＩＦ
Ｏバッファ１１にリストアされる。

【００２９】請求項７記載の発明においては、パケット
完結検出手段１９が計数手段１２の計数値を参照して、
ＦＩＦＯバッファ１１内に完結しているパケットデータ
が存在するか否か検出する。したがって、この検出を利
用して、未完結のパケットのデータがＦＩＦＯバッファ
１１から出力されてしまう事態を抑止できる。

【００３０】請求項８記載の発明においては、ＦＩＦＯ
バッファ１１からパケットデータと共に出力される特定
のビットの値を参照することにより、パケット処理装置
はＦＩＦＯバッファ１１から読み出したデータがパケッ
トの最後のデータであるか否かを容易に検出できる。

【００３１】請求項９記載の発明においては、計数手段
２２によりＦＩＦＯバッファ２１に格納されているパケ
ットデータの個数が計数される。パケット完結検出手段
２３は、該計数値とＦＩＦＯバッファ２１の先頭に格納
されているパケットのそのサイズ情報が設定されている
データを入力して、両者を比較することによりＦＩＦＯ
バッファ２１内に完結しているパケットが存在するか否
か検出する。

【００３２】したがって、このパケット完結手段２３の
検出情報を利用して、ＦＩＦＯバッファ２１内の未完結
のパケットデータがパケット処理装置４０に出力されて
しまう状態を回避させることができる。

【００３３】請求項１０記載の発明においては、前述し
た請求項５記載の発明と同様な動作が、退避バッファ２
３、第１の検出手段２５、及びパケットデータ退避手段
２６により行われる。

【００３４】したがって、パケット生成装置３０は、Ｆ
ＩＦＯバッファ２１に空きが生じていない間でも、生成
したパケットを出力できるので、処理効率が向上する。
請求項１１記載の発明においては、前述した請求項６記
載の発明と同様な動作が、第２の検出手段２７とデータ
リストア手段２８により行われる。

【００３５】したがって、退避バッファ２３に退避され
ていたパケットが、その一部のデータが退避されていた
パケットも含め、正しい順序並びに正しい形式でＦＩＦ
Ｏバッファ１１にリストアされる。

【００３６】請求項１２記載の発明においては、プロセ
スＡがＦＩＦＯバッファ４１にパケットを書き込んでい
る途中で別のプロセスＢに実行権が切り換えられた際、
データ退避手段４３が上記プロセスＡが書き込んだ未完
結のパケットデータを上記ＦＩＦＯバッファ４１から取
り出し記憶手段４２に退避させる。そして、再び前記プ
ロセスＡに実行権が移行した際、データリストア手段４
４が該プロセスＡの実行開始前に前記記憶手段に退避さ
せておいたパケットデータを前記ＦＩＦＯバッファ４１
に転送させリストアさせる。

【００３７】したがって、プロセスＡがＦＩＦＯバッフ
ァ４１にパケットのデータを書き込んでいる途中であっ
ても、新たに起動されたプロセスＢはＦＩＦＯバッファ
４１にパケットを書き込むことが可能になる。そして、
再びプロセスＢが再起動された際には、プロセスＢはＦ
ＩＦＯバッファ４１に残りのパケットデータを書き込む
ことにより、ＦＩＦＯバッファ４１に正しくパケットを
書き込むことが可能になる。

【００３８】

【実施例】図５は、本発明の一実施例のキュー装置の全
体構成を示すブロック図である。ＦＩＦＯバッファ１１
０は、ｎビット単位でのデータの一括入出力が可能なFi
rst-In, First-Out 方式のメモリであり、例えば１チッ
プで構成される。そして、ＦＩＦＯバッファ１１０の残
り容量が予め定められた第１の閾値以下になったことを
示すフルフラグ信号ｆｕｌｌ（以下、ｆｕｌｌ信号と記
述する）並びにＦＩＦＯバッファ１１０が現在、全くデ
ータを格納していない状態であることを示すエンプティ
・フラグ信号empty （以下、ｅｍｐｔｙ信号と記述す
る）の出力端子と、該ＦＩＦＯバッファ１１０へのデー
タ書き込み時にイネーブルとする書き込みイネーブル信
号Ｗ１並びに該ＦＩＦＯバッファ１１０からデータを読
み出すときにイネーブルとする読み出しイネーブル信号
Ｒ１の入力端子を備えている。

【００３９】また、さらにｎビットのデータ入力線Ｄ１
とｎビットのデータ出力線Ｑ１を備えている。また、Ｆ
ＩＦＯバッファ１１０は、バッファ内の残り容量が予め
定められた第２の閾値よりも大きくなった場合には、Al
most-Empty信号を出力する。

【００４０】該ＦＩＦＯバッファ１１０は、例えばＳＲ
ＡＭ（Static Random Access Memory)のアレイから構成
され、該アレイに対してデータの入・出力が行われる。
また、該ＳＲＡＭに対する次の入力データの書き込みア
ドレスを指す入力ポインタと該ＳＲＡＭから次に読み出
すデータのアドレスを指す出力ポインタを内蔵してい
る。これらのポインタは、例えばリングカウンタから成
る。またさらに、上記２つのポインタが指すアドレス値
の差を常に監視・比較しているコンパレータも内蔵して
おり、該コンパレータにより上記ｆｕｌｌ信号や上記ｅ
ｍｐｔｙ信号並びにAlmost-Empty信号を生成・出力す
る。

【００４１】尚、該ＦＩＦＯバッファ１１０をＳＲＡＭ
ではなく、シフトレジスタにより構成するようにしても
よい。退避バッファ１２０は、例えばＤＲＡＭ（Dynami
c Random Access Memory) 等から成り、例えば上記ＦＩ
ＦＯバッファ１１０よりも大きな記憶容量を有する。こ
の退避バッファ１２０も、ｎビット幅のデータ入力線Ｄ
２並びにデータ出力線Ｑ２を備え、さらに、上記ＦＩＦ
Ｏバッファ１１０が有する書き込みイネーブル信号Ｗ１
と同等の機能を有するライトイネーブル信号Ｗ２と、例
えば、データ読み出し用のアウトプット・イネーブル信
号ＯＥを有する。この退避バッファ１２０には、ＦＩＦ
Ｏバッファ１１０の残り容量が上記第１の閾値よりも少
なくなったとき、すなわち、ＦＩＦＯバッファ１１０か
らｆｕｌｌ信号が出力されたとき、オーバーフロー制御
部１３０の制御によってＦＩＦＯバッファ１１０に対し
て書き込み要求がなされたデータが退避・格納される。

【００４２】オーバーフロー制御部１３０は、ＦＩＦＯ
バッファ１１０に対するデータの投入要求をデータ書き
込み要求信号write のイネーブル入力により受け付け、
ＦＩＦＯバッファ１１０から入力される上記ｆｕｌｌ信
号の状態に応じて、上記投入要求データをＦＩＦＯバッ
ファ１１０または退避バッファ１２０のいずれかに格納
する。

【００４３】このオーバーフロー制御部１３０は、書き
込み先決定装置１３１、フラグ１３２、書き込みポイン
タ１３３、及び退避バッファフル検出装置１３４を備え
ている。

【００４４】書き込み先決定装置１３１は、上記データ
書き込み要求信号write がイネーブルになって加わる
と、ＦＩＦＯバッファ１１０から入力されるｆｕｌｌ信
号がアクティブとなっているか否か調べ、アクティブで
ない間は上記信号write と共に、外部装置から入力され
るデータＤ１を、書き込みイネーブル信号Ｗ１を制御し
てＦＩＦＯバッファ１１０に書き込む。

【００４５】ＦＩＦＯバッファ１１０に対するデータの
投入の方が、ＦＩＦＯバッファ１１０からのデータ取り
出しよりも高速に行われる場合には、ＦＩＦＯバッファ
１１０はやがて充満状態となり、ＦＩＦＯバッファ１１
０はｆｕｌｌ信号を“アクティブ”とする。書き込み先
決定装置１３１は、ｆｕｌｌ信号が“アクティブ”にな
った状態のときにデータ書き込み要求信号write がイネ
ーブルになって加わると、書き込みポインタ１３３に上
記信号write がイネーブルになった後に送られてきたＦ
ＩＦＯバッファ１１０に対する書き込みデータの退避バ
ッファ１２０上の格納先アドレスをセットする。

【００４６】書き込みポインタ１３３にセットされたア
ドレス値は、退避バッファ１２０にアドレス信号として
送られ入力される。そして、書き込み先決定装置１３１
が、ライトイネーブル信号Ｗ２をイネーブルにすること
により、ＦＩＦＯバッファ１１０に対する書き込み要求
データＤ１が退避データＤ２として書き込みポインタ１
３３にセットされたポインタ値の指す退避バッファ１２
０上のアドレスに書き込まれ、一時的に退避される。書
き込み先決定装置１３１は、このようにして退避バッフ
ァ１２０にデータを書き込んだ後、フラグ１３２をセッ
トする。

【００４７】書き込み先決定装置１３１は、一度、フラ
グ１３２がセットされると、外部装置からのＦＩＦＯバ
ッファ１１０に対する書き込みデータを、退避バッファ
１２０の方へ転送し書き込む。この間、ＦＩＦＯバッフ
ァ１１０から出力されるAlmost-Empty信号を監視し、該
信号が“アクティブ”になる、すなわち、ＦＩＦＯバッ
ファ１１０に上記第２の閾値以上の“空き”が生ずる
と、退避バッファ１２０に退避させていたデータを、不
図示のデータリスト装置を介してＦＩＦＯバッファ１１
０に転送・復帰させる。

【００４８】一方、Almost-Empty信号が“アクティブ”
になる前に、退避バッファ１２０の残り容量が予め定め
られた第３の閾値よりも少なくなる場合がある。退避バ
ッファフル検出装置１３４は、退避バッファ１２０がこ
のような状態になったことを、書き込みポインタ１３３
から入力されるポインタ値すなわち退避バッファ１２０
の次のデータの格納先アドレスにより検出する。そし
て、該検出時に、バッファフル検出信号buffer-full を
外部出力する。この信号は、例えばプロセッサなどのデ
ータ生成装置に対する割り込み信号として用いられる。

【００４９】次に、図６はＦＩＦＯバッファ１１０を、
コマンドなどを表現する１個以上のデータ列である“パ
ケット”を格納するキューとして使用する場合の一実施
例を示す模式図である。

【００５０】カウンタ１４０は、ＦＩＦＯバッファ１１
０に格納されているパケット数を計数し、その計数値va
lue を該ＦＩＦＯバッファ１１０からパケットを取り出
して処理するパケット処理装置へ出力する。

【００５１】このカウンタ１４０のインクリメント（＋
１）は、プロセッサなどのＦＩＦＯバッファ１１０にパ
ケットを投入するパケット生成装置によって行われ、デ
クリメント（−１）は該ＦＩＦＯバッファ１１０からパ
ケットを取り出すパケット処理装置により行われる。す
なわち、ＦＩＦＯバッファ１１０へのデータ入力側のパ
ケットの投入の終了においてカウンタ１４０をインクリ
メントし、データ出力側のパケットの取り出しの終了に
おいてカウンタ１４０をデクリメントすることによっ
て、ＦＩＦＯバッファ１１０に格納されているパケット
の数を検出することができる。

【００５２】このように、パケット数を計数するカウン
タ１４０を付加することにより、パケット処理装置はＦ
ＩＦＯバッファ１１０内においてパケットが完結してか
ら、該パケットのデータを連続して取り出して効率良く
処理することが可能になる。

【００５３】続いて、図７に示す実施例は上述した図６
に示す構成において、ＦＩＦＯバッファ１１０Ａに格納
するパケットの各データに該データがパケットの最後の
データであるか否かを示す１ビットの情報（end bit)を
付加するようにしたものである。このような構成とする
ことにより、ＦＩＦＯバッファ１１０Ａの出力側では、
上記end bit の出力端子を監視することにより、ＦＩＦ
Ｏバッファ１１０Ａからデータを取り出す過程でパケッ
トの終了を容易に検出することができる。図８は本発明
の実施例のキュー装置１０００を適用したプロセッサ要
素の全体的な回路構成を示すブロック図である。

【００５４】プロセッサ１００は、例えばＲＩＳＣ（Re
duced Instruction Set Computer)型またはＣＩＳＣ（C
omplex Instruction Set Computer) 型のマイクロプロ
セッサから成り、コマンドなどから成るパケットを生成
する。

【００５５】このプロセッサ１００には、バス２００を
介してメモリ３００が接続されている。このメモリ３０
０は、例えばＤＲＡＭ等から成り、その内部には退避バ
ッファ１０２０の領域が確保される。この退避バッファ
１０２０は、上記退避バッファ１２０と同等の機能を有
するもので、上記プロセッサ１００により生成されるパ
ケットの一時的な退避領域として利用される。

【００５６】本実施例のキュー装置１０００の上記退避
領域１０２０を除く部分は、バスインタフェース４００
を介してバス２００に接続されている。次に、上記退避
領域１０２０以外のキュー装置１０００の構成を説明す
る。

【００５７】２つのＦＩＦＯバッファ（ＦＩＦＯ１、Ｆ
ＩＦＯ２）から成るＦＩＦＯバッファ１０１０は、プロ
セッサ１００がバスインタフェース４００を介して書き
込むパケットを格納するキューとして機能するＦＩＦＯ
メモリである。プロセッサ１００は、ＦＩＦＯ１または
２のいずれにデータを書き込むかは、バスインタフェー
ス４００を介してオーバーフロー制御部１０３０に出力
する書き込み要求信号Ｗ１１またはＷ１２を制御するこ
とにより指示する。

【００５８】これらの各ＦＩＦＯバッファ１，２にそれ
ぞれ対応するカウンタＣ１，Ｃ２を有するカウンタ１０
４０が設けられている。カウンタＣ１，Ｃ２は、それぞ
れ、ＦＩＦＯ１，２に格納されているパケット数を計数
する。

【００５９】オーバーフロー制御部１０３０は、これら
ＦＩＦＯ１，２並びにカウンタＣ１，Ｃ２と上記バスイ
ンタフェース４００との間に介在して設けられている。
オーバーフロー制御部１０３０は、２つのフラグＦ１，
Ｆ２を有するフラグ１０３２、パケットデータラッチ回
路１０３６（以下、単にラッチ回路１０３６と表現す
る）、退避バッファ１０２０用の書き込みポインタ１０
３３，該退避バッファ１０２０のサイズに応じて決定さ
れる該書き込みポインタ１０３３の限界値（最終格納ア
ドレス）が設定されるlimit レジスタ１０３７、上記ポ
インタ１０３３とlimit レジスタ１０３７とを比較する
コンパレータ１０３８、さらには前記フラグＦ１，Ｆ２
及び前記カウンタＣ１，Ｃ２の値を基に、プロセッサ１
００に対してデータリストアを要求する割り込みをかけ
るインタラプト発生部１０３９を備えている。

【００６０】フラグＦ１は、対応するＦＩＦＯ１から入
力されるｆｕｌｌ１信号が“アクティブ”になったと
き、すなわちＦＩＦＯ１が充満状態になったときに“セ
ット”される。そして、退避バッファ１０２０に退避さ
れていた全てのデータがＦＩＦＯバッファ１に投入され
た時点で“クリア”（リセット）される。

【００６１】フラグＦ２は、ＦＩＦＯ２に対して、上記
フラグＦ１と同様の動作をする。書き込み先ポインタ１
０３３には、最初、退避バッファ１０２０の先頭アドレ
スか設定される。そして、ＦＩＦＯバッファ１０１０に
対する書き込みデータが格納される毎にインクリメント
される。この書き込み先ポインタ１０３３の値は、バス
インタフェース４００及びバス２００を介してメモリ３
００にアドレス信号（address)として供給される。

【００６２】コンパレータ１０３８は、上記書き込み先
ポインタ１０３３の値がlimit レジスタ１０３７の値を
越えた時に、割り込み信号（Interrupt １）をバスイン
タフェース４００及びバス２００を介してプロセッサ１
００に加える。この割り込みは、退避バッファ１０２０
に“空き”が無くなったことをプロセッサ１００に通知
するものである。

【００６３】ラッチ回路１０３６は、バスインタフェー
ス４００を介して入力されるプロセッサ１００がバス２
００上に出力したＦＩＦＯバッファ１０１０に対する書
き込みデータ（data) を一時的に保持する。また、プロ
セッサ１００は、パケットの最後のデータを書き込む時
には、バス２００上のエンド・ビット（end bit)の信号
線を有効（“１”）にする。このend bit の値もバスイ
ンタフェース４００を介してラッチ回路１０３６にラッ
チされる。

【００６４】オーバーフロー制御部１０３０内の不図示
のカウンタ制御部は、このラッチ回路１０３６にラッチ
されたend bit が“１”に設定されていることを検出す
ることにより、ラッチ回路１０３６にパケットの最後の
データがラッチされたことを検出する。そしてＦＩＦＯ
１またはＦＩＦＯ２にパケットの最後のデータを書き込
んだ後に、カウンタＣ１またはＣ２をインクリメント
（＋１）する。

【００６５】インタラプト発生部１０３９は、フラグＦ
１またはＦ２がセットされているときに、そのセットさ
れているフラグＦ１またはＦ２に対応するカウンタＣ１
またはＣ２の値が“０”または所定の閾値以下になると
割り込み信号（Interrupt ２）を発生し、バスインタフ
ェース４００及びバス２００を介してプロセッサ１００
に割り込みをかける。この割り込みは、ＦＩＦＯバッフ
ァ１０１０に対する書き込みデータが、退避バッファ１
０２０に退避されている状態のときに、ＦＩＦＯ１また
はＦＩＦＯ２に格納されているパケットが“皆無”にな
ったときに発生する。

【００６６】図９(a) ，(b) は、上記インタラプト発生
部１０３９の回路構成例を示す図である。同図(a) に示
すインタラプト発生部１０３９は、フラグＦ１がセット
されており、かつカウンタＣ１の値（ＦＩＦＯ１の格納
パケット数）value 1 が“０”のとき、またはフラグＦ
２がセットされており、かつカウンタＣ２の値（ＦＩＦ
Ｏ２の格納パケット数）value ２が“０”のとき、共通
の割り込み信号Interrupt２を発生する。

【００６７】コンパレータ１１０２は、カウンタＣ１の
値value １が“０”のとき“Ｈ”信号をアンドゲート１
１０４の一方の入力端子に出力する。アンドゲート１１
０４は他方の入力端子にフラグＦ１の値（“１”（セッ
ト状態）のときに“Ｈ”、“０”（クリア状態）のとき
に“Ｌ”）を入力する。そして、フラグＦ１がセットさ
れており、かつカウンタＣ１の値value １が“０”のと
きに“Ｈ”信号をオアゲート１１１０に出力する。ま
た、上記フラグＦ１とカウンタＣ１の出力に対する回路
と同様な回路が、コンパレータ１１０６とアンドゲート
１１０８によりフラグＦ２の出力とカウンタＣ２の出力
に対しても設けられている。アンドゲート１１０８は、
フラグＦ２がセットされており、かつカウンタＣ２の値
value ２が“０”のときに“Ｈ”信号をオアゲート１１
１０に出力する。

【００６８】オアゲート１１１０は、アンドゲート１１
０４またはアンドゲート１１０８のいずれか一方が
“Ｈ”となったときに、割り込み信号Interrupt ２をバ
スインタフェース４００に出力する。

【００６９】この場合、プロセッサ１００は、オーバー
フロー制御部１０３０並びにバスインタフェース４００
を介してカウンタＣ１，Ｃ２の値を読み出して、値が
“０”となっているカウンタＣｉ（ｉ＝１，２，）を検
出することにより、ＦＩＦＯ１またはＦＩＦＯ２のいず
れが格納パケット数が“０”になったか判断する。

【００７０】一方、図９(b) に示す回路は、上述した同
図(a) に示す回路からオアゲート１１１０を省略したも
のであり、上記アンドゲート１１０４と上記アンドゲー
ト１１０８の出力が、それぞれ独立の割り込み信号Inte
rrupt ２Ａ，２Ｂとなって、バスインタフェース４００
に出力される。この場合、プロセッサ１００は、ＦＩＦ
Ｏ１またはＦＩＦＯ２のいずれの方が格納パケット数が
“０”になったかを認識できる。

【００７１】アービタ１０５０は、カウンタＣ１，Ｃ２
の値value １，２を監視しており、該カウンタ値value
１または２の値が“０”より大きくなると、２つのＦＩ
ＦＯ１，２のうち適当な方を選択し、該選択したＦＩＦ
Ｏ１または２からそれに加えるイネーブル信号ｒ１また
はｒ２を“イネーブル”にしてパケットデータを順次読
み出す。これらの読み出されたパケットデータはマルチ
プレクサ１０６０に入力される。アービタ１０５０は、
該マルチプレクサ１０６０に入力選択信号selectを加
え、上記ＦＩＦＯ１またはＦＩＦＯ２から読み出された
パケットデータdataをパケット処理装置５００に入力さ
せる。

【００７２】マルチプレクサ１０６０は、ＦＩＦＯ１及
びＦＩＦＯ２からアービタ１０５０によって取り出され
たパケットデータが入力されるデータセレクタであり、
アービタ１０５０から加わる入力選択信号selectに応じ
て、ＦＩＦＯ１またはＦＩＦＯ２のいずれか一方から出
力されるパケットデータdataをパケット処理装置５００
に出力する。

【００７３】マルチプレクサ１０７０は、ＦＩＦＯ１及
びＦＩＦＯ２からそれぞれｅｍｐｔｙ信号１，２を入力
し、アービタ１０５０から上記マルチプレクサ１０６０
と同様に入力選択信号selectを入力する。そして、該選
択信号selectに応じて、上記２つのｅｍｐｔｙ信号１ま
たは２のいずれか一方をパケット処理装置５００に選択
出力する。

【００７４】パケット処理装置５００は、パケット処理
の開始に際して前記アービタ１０５０にパケットの読み
出し要求信号readを送り、アービタ１０５０にＦＩＦＯ
バッファ１０１０に格納されているパケットの取り出し
を依頼する。アービタ１０５０は、この信号readを受け
取るとカウンタＣ１，Ｃ２を参照し、マルチプレクサ１
０６０を介してＦＩＦＯ１またはＦＩＦＯ２に格納され
ているパケットデータをパケット処理装置５００に入力
させる。パケット処理装置５００は、マルチプレクサ１
０６０を介してパケットの最後のデータを受け取ると、
パケットの取り出し終了を示すdone信号をアービタ１０
５０に出力する。アービタ１０５０は、このdone信号を
受信すると、上記パケットが取り出されたＦＩＦＯｉ
（ｉ＝１，２）に対応するカウンタＣｉをデクリメント
（−１）する。パケット処理装置５００には前述したよ
うにマルチプレクサ１０７０を介してｅｍｐｔｙ信号が
入力されるので、該ｅｍｐｔｙ信号が非アクティブとな
っている間はＦＩＦＯバッファ１０１０にパケットが格
納されていることを知ることができる。

【００７５】図１０は、ＦＩＦＯバッファ１０１０（Ｆ
ＩＦＯ１，ＦＩＦＯ２）に格納されるパケットの形式を
示す図である。パケットの先頭（第１ワード）には、コ
マンドの種類を示す情報が設定される。これに続く第２
ワード目以降には、該コマンドに付随するパラメータが
必要な個数だけ設定される。

【００７６】また、図１１は、退避バッファ１０２０に
退避されるパケットの形式を示す図である。このパケッ
トには、パケットデータdataに加え、さらに投入すべき
ＦＩＦＯバッファを示すキュー番号（例えばＦＩＦＯ１
の場合には“１”、ＦＩＦＯ２の場合には“２”）と対
応するパケットデータが当該パケットの最後のデータで
あるか否かを示す情報であるend-bit が付加される。該
end-bit は、例えば“１”のときに有効である。プロセ
ッサ１００が退避バッファ１０２０に退避されているパ
ケットデータを該当するＦＩＦＯｉ（ｉ＝１，２）に戻
す場合には、これらの付加情報を参照する。

【００７７】次に、上記構成のプロセッサ要素の動作を
説明する。プロセッサ１００は、パケットを生成する
と、該パケットをバス２００のデータバス幅に合わせて
分割し、end bit データに該当値を設定して逐次バス２
００に出力する。そして、オーバーフロー制御部１０３
０に対し、ＦＩＦＯ１またはＦＩＦＯ２に対するパケッ
トデータdataの書き込み要求信号Ｗ１１またはＷ１２を
イネーブルにしてバス２００上のコマンドバスに出力す
る。

【００７８】バスインタフェース４００は、上記書き込
み要求信号Ｗｉ（ｉ＝１，２）のイネーブル出力を検出
すると、この信号Ｗｉをオーバーフロー制御部１０３０
に出力し、その内部のラッチ回路１０３６にバス２００
上に出力されているパケットデータdata並びにend bit
をラッチさせる。

【００７９】このようにして、ラッチ回路１０３６にラ
ッチされたパケットデータは、オーバーフロー制御部１
０３０によって書き込み要求がなされたＦＩＦＯｉに順
次書き込まれる。そして、プロセッサ１００がパケット
の最後のデータと共に“１”に設定したend bit データ
をバス２００上に出力すると、オーバーフロー制御部１
０３０は、該当するＦＩＦＯｉにそのパケットの最後の
データを書き込み、その後、対応するカウンタＣｉをイ
ンクリメント（＋１）する。

【００８０】以上のようにして、プロセッサ１００によ
ってＦＩＦＯバッファ１０１０（ＦＩＦＯ１またはＦＩ
ＦＯ２）に対してパケットが書き込まれ、各ＦＩＦＯ
１，２に書き込まれるパケット数がオーバーフロー制御
部１０３０によってカウンタＣ１，２により計数され
る。

【００８１】アービタ１０５０は、カウンタＣ１，Ｃ２
の値を常時、監視しており、該カウンタＣ１又はＣ２の
値が“０”より大きくなると、マルチプレクサ１０６０
を制御して２つのＦＩＦＯ１，２の内、適当な方をパケ
ットを取り出すキューとして選択する。また、該制御に
伴って、マルチプレクサ１０７０からパケット処理装置
５００に対して非アクティブのｅｍｐｔｙ信号が加わ
る。非アクティブのｅｍｐｔｙ信号は、ＦＩＦＯバッフ
ァ１０１０すなわちＦＩＦＯ１またはＦＩＦＯ２の少な
くともいずれか一方にパケットが格納されていることを
示している。

【００８２】パケット処理装置５００は、マルチプレク
サ１０７０から非アクティブのｅｍｐｔｙ信号が加わる
と、アービタ１０５０に対して出力される信号readをア
クティブにして、パケットの受信要求を行う。アービタ
１０５０は、この要求を受けて、ＦＩＦＯ１またはＦＩ
ＦＯ２のいずれか適切な方にリードイネーブル信号ｒ１
またはｒ２を“イネーブル”にして出力し、該イネーブ
ル出力を行ったＦＩＦＯｉ（ｉ＝１，２）からパケット
データを順次読み出す。アービタ１０５０は、例えば、
カウンタＣ１，２の値が共に“０”より大きな値であっ
た場合、カウンタ値すなわち格納パケット数が多いＦＩ
ＦＯｉの方を優先的に選択する。そして、マルチプレク
サ１０６０を制御して、該選択したＦＩＦＯｉから読み
出されたパケットデータをパケット処理装置５００に順
次入力させる。

【００８３】パケット処理装置５００は、該ＦＩＦＯｉ
から読み出されてくるパケットデータを順次取り込んで
パケット処理を開始する。そして、パケットの最後のデ
ータを取り込むと、アービタ１０５０に対してdone信号
を送信する。アービタ１０５０は、これを受けて上記Ｆ
ＩＦＯｉに対応するカウンタＣｉの値をデクリメント
（−１）する。すなわち、ＦＩＦＯｉの格納パケット数
は“１”減少したので、これに合わせてカウンタＣｉの
値を更新する。パケット処理装置５００は、例えば、各
種コマンドの全体長を記憶しており、その記憶情報によ
り各パケットの取り出し終了を検出する。

【００８４】プロセッサ１００がＦＩＦＯ１またはＦＩ
ＦＯ２にパケットを書き込む速度の方が、パケット処理
装置５００がＦＩＦＯ１またはＦＩＦＯ２からパケット
を取り出して処理する速度よりも速い場合には、ＦＩＦ
Ｏ１またはＦＩＦＯ２が充満状態になる場合があり得
る。

【００８５】このような場合、オーバーフロー制御部１
０３０は、プロセッサ１００から現在、充満状態にある
ＦＩＦＯｉに対するパケットデータの書き込み要求を受
け取ると、該書き込み要求のあったパケットデータを図
１１に示す形式で退避バッファ１０２０のポインタ１０
３３の指すアドレスに書き込む。そして、対応するフラ
グＦｉをセットする。このように、いったんフラグＦｉ
がセットされると、オーバーフロー制御部１０３０はそ
の後プロセッサ１００からＦＩＦＯｉに対して書き込み
要求がなされるパケットを、ポインタ１０３３を更新し
ながら退避バッファ１０２０の方に書き込む。

【００８６】このように退避バッファ１０２０にパケッ
トの書き込みが行われている間に、充満状態にあったＦ
ＩＦＯｉからパケット処理装置５００によってパケット
が順次、取り出されていく。そして、やがて、該ＦＩＦ
Ｏｉの格納パケット数は“０”となる。すなわち、該Ｆ
ＩＦＯｉに対応するカウンタＣｉの値は“０”になる。
これにより、オーバーフロー制御１０３０においてイン
タラプト発生部１０３９からプロセッサ１００に対して
割り込み信号Interrupt ２が加わる。

【００８７】プロセッサ１００は、この割り込みにより
当該割り込み処理ルーチンを実行し、退避バッファ１０
２０からＦＩＦＯｉに投入すべきパケットデータを読み
出し、該パケットデータを該ＦＩＦＯｉに書き込む。そ
して、この結果退避バッファ１０２０内にＦＩＦＯｉに
投入すべきパケットデータが残らなくなれば、対応する
フラグＦｉをクリア（リセット）する。このフラグＦｉ
のクリアにより、オーバーフロー制御１０３０は、再び
ＦＩＦＯｉが充満状態になるまで、プロセッサ１００か
ら書き込み要求がなされるパケットデータをＦＩＦＯｉ
に書き込む。

【００８８】一方、上記退避バッファ１０２０からＦＩ
ＦＯｉへのデータのリストアにおいて、まだ、退避バッ
ファ１０２０の中にＦＩＦＯｉへの投入パケットデータ
が残っている場合には、フラグＦｉはクリアしない。し
たがって、この場合には、オーバーフロー制御１０３０
は引き続いて、プロセッサ１００のＦＩＦＯｉに対する
投入データを、退避バッファ１０２０の方に書き込む。
すなわち、この場合には、退避バッファ１０２０の方に
ＦＩＦＯｉに先に投入すべきパケットデータが残ってい
るからである。

【００８９】ところで、あるパケットにおいてＦＩＦＯ
ｉにデータを投入している途中で、ＦＩＦＯｉが充満状
態となり、それ以降のデータが退避バッファ１０２０の
方に格納される場合もありえる。この場合においては、
カウンタＣｉはインクリメント（＋１）されないので、
ＦＩＦＯｉには該パケットは格納されていないものとみ
なされる。そして、退避バッファ１０２０に退避されて
いた残りの全てのデータがＦＩＦＯｉに転送された時点
でカウンタＣｉがインクリメント（＋１）される。した
がって、パケット処理装置５００は、常にＦＩＦＯｉ内
でパケットが完結した時点でＦＩＦＯｉからパケットを
効率良く取り出すことができる。

【００９０】一方、退避バッファ１０２０がオーバーフ
ローする状態もありえる。この場合には、コンパレータ
１０３８により割り込み信号Interrupt １がプロセッサ
１００に加えられる。プロセッサ１００は、この割り込
みが加わると、例えばメモリ３００上の退避バッファ１
０２０のサイズを拡張する処理などを行う。そして、こ
れに伴ってlimit レジスタ１０３７の値を更新する。

【００９１】上述した実施例では、退避バッファ１０２
０から該当するＦＩＦＯｉへのデータのリストアを、プ
ロセッサ１００のソフトウェア処理により実行してい
る。次に述べる実施例は、上記データリストア処理を完
全にハードウェアで実現するキュー装置を実装したプロ
セッサ要素の例である。

【００９２】この実施例では、図１２に模式的に示すよ
うに、退避バッファ１０２０に対して書き込みポインタ
ＷＰ（図８のポインタ１０３３に対応）の他に、退避バ
ッファ１０２０から読み出すべき先頭のパケットデータ
の格納アドレスを指す読み出しポインタＲＰを用意す
る。これにより、退避バッファ１０２０をリングバッフ
ァとして取り扱うことが可能になる。そして、ＦＩＦＯ
バッファ１０１０が空になったことを検出したら、退避
バッファ１０２０に退避されていたデータを上記読み出
しポインタＲＰで示されるアドレスから読み出し、ＦＩ
ＦＯバッファ１０１０に転送する。そして、このデータ
転送により、退避バッファ１０２０が“空”になったな
らば、退避バッファ１０２０に退避データがあることを
示すフラグ１０３２をリセット（クリア）する。これら
の一連の処理をハードウェアにより実現する。

【００９３】図１３は上記データリストア処理をハード
ウェアにより実現するキュー装置２０００を実装したプ
ロセッサ要素の全体構成を示すブロック図である。同図
において、前述した図８に示す実施例内のブロックと同
一のブロックには同一の符号を付与しており詳しい説明
は省略する。

【００９４】本実施例においては、ＦＩＦＯバッファ１
０１０は１個のみ備えられ、これに対応して該ＦＩＦＯ
バッファ１０１０内の格納パケット数を計数するカウン
タ１０４０が設けられている。

【００９５】本実施例のオーバーフロー制御部２０３０
は、前記図８に示す実施例と同様に、ラッチ回路１０３
６、退避バッファ１０２０にＦＩＦＯバッファ１０１０
に書き込まれるべきパケットデータが退避されているこ
とを示すフラグ１０３２を備えている。そして、これら
の回路以外に、上述した退避バッファ１０２０用に設け
られた書き込みポインタＷＰと読み出しポインタＲＰ、
ポインタ比較器２０３１、シーケンサ２０３２、２つの
マルチプレクサ２０３３，２０３４を備えている。

【００９６】ポインタ比較器２０３１は、上記２つのポ
インタＷＰ，ＲＰの値を入力・比較し、退避バッファ１
０２０が現在、“空”になっているか又は“充満状態”
にあるかを検出する。そして、退避バッファ１０２０が
“空”になっていればｅｍｐｔｙ３信号を、“充満状
態”になっていればｆｕｌｌ３信号をシーケンサ２０３
２に出力する。退避バッファ１０２０は、上述したよう
にリングバッファの構成となっているので、“空”の状
態のときには上記両ポインタの値は一致し、充満状態の
ときには上記両ポインタはリングバッファ上における隣
接するアドレスを指すことになる。

【００９７】シーケンサ２０３２は、オーバーフロー制
御部２０３０を全体を制御し、プロセッサ１００からの
ＦＩＦＯバッファ１０１０に対するパケットデータdata
とそれに付加されるend bit データの書き込み要求信号
Ｗをバスインタフェース４００を介して受信する。そし
て、ラッチ回路１０３６に該パケットデータdataとend
bit データをラッチさせる。

【００９８】マルチプレクサ２０３３は、シーケンサ２
０３２から加えられる入力選択信号select１に従って上
記ポインタＷＰまたはＲＰのいずれか一方をアドレス信
号としてバスインタフェース４００に出力する。このア
ドレス信号は、バス２００を介してメモリ２００に送ら
れる。すなわち、シーケンサ２０３２は、ＦＩＦＯバッ
ファ１０１０への投入データを退避バッファ１０２０に
退避させる場合には、書き込みポインタＷＰの値が選択
出力されるように、退避バッファ１０２０に退避されて
いるデータをＦＩＦＯバッファ１０１０にリストアさせ
る場合には読み出しポインタＲＰの値が選択出力される
ようにマルチプレクサ２０３３を制御する。

【００９９】マルチプレクサ２０３４は、シーケンサ２
０３２から加えられる入力選択信号select２に従って、
ラッチ回路１０３６にラッチされたプロセッサ１００の
書き込みデータまたは退避バッファ１０２０から読み出
されたリストア用のデータのいずれか一方を、ＦＩＦＯ
バッファ１０１０に選択出力する。すなわち、シーケン
サ２０３２は、プロセッサ１００から書き込み要求がな
されたパケットデータdataをＦＩＦＯバッファ１０１０
に直接書き込む場合にはラッチ回路１０３６にラッチさ
れているパケットデータdataが選択出力されるように、
退避バッファ１０２０から読み出されたリストア用のパ
ケットデータdataをＦＩＦＯバッファ１０１０に書き込
む場合にはバスインタフェース４００から入力される上
記リストア用のパケットデータdataが選択出力さるよう
にマルチプレクサ２０３４を制御する。また、シーケン
サ２０３２は、上記マルチプレクサ２０３４からの出力
パケットデータdataをＦＩＦＯバッファ１０１０に書き
込むときには、ライトイネーブル信号write ２をイネー
ブルにしてＦＩＦＯバッファ１０１０に加える。

【０１００】シーケンサ２０３２は、ラッチ回路１０３
６にパケットの最後のデータdataがラッチされると、該
データdataと共にもラッチ回路１０３６にラッチされた
end-bit の値によりラッチ回路１０３６にパケットの最
後のデータdataがラッチされたことを認識する。そし
て、該最後のデータdataをＦＩＦＯバッファ１０１０に
書き込んだ後にカウンタ１０４０をインクリメント（＋
１）する。

【０１０１】本実施例においては、ＦＩＦＯバッファ１
０１０は１個しか実装されていないので、退避バッファ
１０２０に格納されるパケットデータの形式は図１４に
示すように、前述した実施例とは異なり、end-bit のみ
が付加された形式となる。シーケンサ２０３２は退避バ
ッファ１０２０からＦＩＦＯバッファ１０１０へリスト
アするパケットデータdataを読み出した際、該end-bit
の情報によりパケットの最後のデータdataの読み出しを
検出する。そして、該最後のデータdataをＦＩＦＯバッ
ファ１０１０にリストアした後に、カウンタ１０４０を
インクリメント（＋１）する。また、パケット処理装置
５００は、ＦＩＦＯバッファ１０１０からパケットの最
後のデータを読み出す毎に、該カウンタ１０４０をデク
リメント（−１）する。

【０１０２】以上のような構成の実施例におけるキュー
装置２０００の動作を、図１５のフローチャートを参照
しながら説明する。オーバーフロー制御部２０３０のシ
ーケンサ２０３２は、下記の（Ａ）〜（Ｄ）の判断を行
う。 （Ａ）プロセッサ１００からキューすなわちＦＩＦＯバ
ッファ１０１０へのパケットデータdataの書き込み要求
があると、退避バッファ１０２０に“空き”があるか否
か調べる。これは、ポインタ比較器２０３１から入力さ
れるｆｕｌｌ３信号がアクティブになっているか否かに
よって判断する。非アクティブであれば、退避バッファ
１０２０には“空き”がある。 （Ｂ）オーバーフローフラグ１０３２にセットされてい
るflag情報を参照して該オーバーフローフラグ１０３２
がセットされているか否か判別することにより、現在、
オーバーフローデータが退避バッファ１０２０に退避さ
れているか調べる。そして、退避データがあれば次にＦ
ＩＦＯバッファ１０１０からのｆｕｌｌ２信号の状態を
調べ、現在、ＦＩＦＯバッファ１０１０に“空き”があ
るか調べる。 （Ｃ）上記判断（Ａ）において、現在、退避バッファ１
０２０に“空き”があると判断すると、次に、オーバー
フローフラグ１０３２がセットされているか又はＦＩＦ
Ｏバッファ１０１０が充満状態（フル状態）にあるか調
べる。上述したように、オーバーフローフラグ１０３２
がセットされていることは現在、退避バッファ１０２０
に退避データが存在することを意味する。 （Ｄ）上記判断（Ａ）において、現在、退避バッファ１
０２０に“空き”があると判断すると、オーバーフロー
フラグ１０３２がオフとなっており、かつＦＩＦＯバッ
ファ１０１０に“空き”があるか否か調べる。

【０１０３】シーケンサ２０３２は、上記（Ａ）〜
（Ｄ）の判断を行い、その判断結果に応じてプロセッサ
１００からキューに対する書き込み要求のあったパケッ
トデータをＦＩＦＯバッファ１０１０または退避バッフ
ァ１０２０のいずれかに書き込む。また、退避バッファ
１０２０に退避されていたパケットデータをＦＩＦＯバ
ッファ１０１０にリストアする。

【０１０４】すなわち、システムの動作開始時には、上
記（Ｄ）の判断においてオーバーフローフラグ１０３２
がリセットされており、かつＦＩＦＯバッファ１０１０
に“空き”があることが認識され、プロセッサ１００か
らのキューに対する書き込み要求データは、ＦＩＦＯバ
ッファ１０１０に順次書き込まれる（ステップＳ１
１）。そして、ＦＩＦＯバッファ１０１０に書き込んだ
パケットデータに付加されているend-bit が“オン”と
なっている場合、すなわち、ＦＩＦＯバッファ１０１０
にパケットの最後のデータを書き込んだ際にはカウンタ
１０４０をインクリメント（＋１）する（ステップＳ１
２）。これにより、カウンタ１０４０にはＦＩＦＯバッ
ファ１０１０に格納されているパケット数がセットされ
る。その後も、マイクロプロセッサ１００のキューへの
書き込みデータは、上記ステップＳ１１〜Ｓ１２の処理
によりＦＩＦＯバッファ１０１０に書き込まれていく。

【０１０５】そして、やがてＦＩＦＯバッファ１０１０
が充満状態になると、ＦＩＦＯバッファ１０１０から出
力されるｆｕｌｌ２信号が“アクティブ”になる。これ
により、シーケンサ２０３２は、上記判断（Ｃ）におい
て、ＦＩＦＯバッファ１０１０が充満状態（フル）にな
ったことを検出し、これ以降のマイクロプロセッサ１０
０からのキューに対する書き込みデータdataは退避バッ
ファ１０２０に書き込む。このとき、図１４に示すよう
に書き込みデータdataに対して“end-bit ”を付加する
（ステップＳ２１）。そして、該データdataの書き込み
後、書き込みポインタＷＰをインクリメント（＋１）し
（ステップＳ２２）。オーバーフローフラグ１０３２を
“オン”にセットする（ステップＳ２３）。シーケンサ
２０３２は、このように、オーバーフローフラグが“オ
ン”になると、マイクロプロセッサ１００からキューへ
のパケットデータdataの書き込み要求がある毎に、上記
ステップＳ２１〜Ｓ２３の処理を行い、退避バッファ１
０２０に該パケットデータdataを書き込む。

【０１０６】その後、パケット処理装置５００によりＦ
ＩＦＯバッファ１０１０からパケットの取り出しが行わ
れ、ＦＩＦＯバッファ１０１０に“空き”が生じると、
ＦＩＦＯバッファ１０１０から出力されるｆｕｌｌ２信
号は非アクティブとなる。これにより、シーケンサ２０
３２は、上記判断（Ｂ）においてＦＩＦＯバッファ１０
１０に“空き”が生じたことを検出する。また、オーバ
ーフローフラグ１０３２がセットされていることによ
り、退避バッファ１０２０にオーバーフローデータ（退
避データ）が格納されていることを知る。

【０１０７】これにより、シーケンサ２０３２は退避バ
ッファ１０２０の読み出しポインタＲＰの指すアドレス
からパケットデータdataを読み出し、該データdataをＦ
ＩＦＯバッファ１０１０に書き込む（ステップＳ３
１）。続いて、読み出しポインタＲＰをインクリメント
（＋１）する（ステップＳ３２）。そして、ＦＩＦＯバ
ッファ１０１０に書き込んだパケットデータdataに付加
されていたend-bit が“オン”にセットされていたなら
ば、カウンタ１０４０をインクリメント（＋１）する。
すなわち、ＦＩＦＯバッファ１０１０に１パケットをリ
ストアするごとにカウンタ１０４０をインクリメント
（＋１）する（ステップＳ３３）。この後、ポインタ比
較器２０３１から入力されるｅｍｐｔｙ３信号の状態を
調べ、退避バッファ１０２０が“空”になったか否か調
べ、退避バッファ１０２０に退避されていたデータdata
が皆無になったならば、オーバーフローフラグ１０３２
をクリア（リセット）する（ステップＳ３４）。

【０１０８】シーケンサ２０３２は、例えばマイクロプ
ロセッサ１００からキューへのパケットデータdataの書
き込み要求が無い間、上記ステップＳ３１〜Ｓ３４の処
理を随時行う。これにより、マイクロプロセッサ１００
がバス２００を使用していない間を利用して、退避バッ
ファ１０２０からＦＩＦＯバッファ１０１０へのデータ
のリストアを、マイクロプロセッサ１００の動作を妨げ
ることなく行うことができる。

【０１０９】次に、図１６は本発明のさらに別の実施例
であるキュー装置３０００を実装したプロセッサ要素の
全体構成を示すブロック図である。同図において、前述
した図８に示すプロセッサ要素内のブロックと同一のブ
ロックには同一の符号を付与してあり、これらについて
は詳しい説明は省略する。

【０１１０】本実施例のＦＩＦＯバッファ３０１０は、
２つのＦＩＦＯメモリ１，２（以下、単にＦＩＦＯ１，
２と記述する）から成っており、各ＦＩＦＯ１，２はリ
ングバッファ構成となっている。図１７にその詳しい構
成を示す。

【０１１１】ＦＩＦＯｉ（ｉ＝１，２，）は、ＦＩＦＯ
バッファ３１１０と、該バッファ３１１０への次のデー
タの書き込みアドレスを指す書き込みポインタｗｐｉ
と、次のデータの読み出しアドレスを指す読み出しポイ
ンタｒｐｉから成っている。そして、これらの２つのポ
インタｗｐｉ，ｒｐｉを操作することにより、エンドレ
スなバッファとして機能する。

【０１１２】ＦＩＦＯバッファ３１１０に書き込まれる
パケットの形式を図１８に示す。同図に示すように、パ
ケットの先頭（第１ワード目）にはパケットの全体長を
示すサイズ情報が設定されている。

【０１１３】各ＦＩＦＯ１，２にそれぞれ対応してパケ
ット完結検出部３０６０が設けられている。該パケット
完結検出部３０６０は、対応するＦＩＦＯ１，２に完結
したパケットが格納されているか否かを検出するもの
で、１個以上の完結されたパケットがＦＩＦＯ１，２に
格納されていれば外部出力のpacket complete １，２信
号を“アクティブ”にする。このpacket complete １，
２信号は、アービタ３０５０に入力されており、アービ
タ３０５０はこのpacket complete １，２信号により前
記マルチプレクサ１０６０並びにマルチプレクサ１０７
０を制御する。すなわち、このpacket complete １，２
信号は、アービタ３０５０に対して前記カウンタＣ１，
Ｃ２の代替として機能する。そして、アービタ３０５０
は、ＦＩＦＯ１，２からパケットデータdataを読み出す
毎に上記ポインタｒｐ１，２を更新する。また、上記書
き込みポインタｗｐ１，２の操作は、オーバーフロー制
御部３０３０内の不図示のシーケンサによって行われ
る。

【０１１４】次に、パケット完結検出部３０６０の内部
の回路構成を図１７を参照しながら説明する。パケット
デコーダ３０６１は、ＦＩＦＯ１，２内に格納されてい
るパケットの先頭ワードのデータをデコードして、該パ
ケットの全体サイズを示すパケット長（packet size)を
コンパレータ３０６３に出力する。

【０１１５】演算器３０６２は、ＦＩＦＯ１，２から上
記２つのポインタｒｐ，ｗｐの値を入力し、両ポインタ
値からＦＩＦＯ１，２に格納されているパケットデータ
の個数（ワード数）を示すデータ長（data length)を求
め、これを上記コンパレータ３０６３に出力する。

【０１１６】コンパレータ３０６３は、パケットデコー
ダ３０６１から入力されるパケット長と演算器３０６２
から入力されるデータ長とを比較する。そして、該デー
タ長がパケット長以上であれば、ＦＩＦＯ１，２内にお
いてパケットが完結していることを示すべくアービタ３
０５０に加えるpacket complete 信号１，２を“アクテ
ィブ”にする。

【０１１７】ポインタ比較器３０６４は、前述した図１
３に示すポインタ比較器２０３１と同様な動作を行うも
のでＦＩＦＯ１，２から上記２つのポインタｒｐ（ｒｐ
１，２），ｗｐ（ｗｐ１，２）を入力し、これら両ポイ
ンタ値を比較して、ＦＩＦＯ１，２が“充満状態（ful
l) ”にあることを示すｆｕｌｌフラグ１，２信号と、
該ＦＩＦＯ１，２が“空”になっていることを示すｅｍ
ｐｔｙフラグ１，２信号を生成し、これらをオーバーフ
ロー制御部３０３０に出力する。本実施例におけるオー
バーフロー制御部３０３０内におけるインタラプト発生
部３０３９の構成を図１９に示す。

【０１１８】同図に示すように、インタラプト発生部３
０３９は前述したインタラプト発生部１０３９からコン
パレータ１１０２，１１０６を削除した構成となってお
り、アンドゲート１１０４，１１０８には、それぞれ前
記パケット完結検出部３０６０から出力されるｅｍｐｔ
ｙフラグ１，２信号が入力される。そして、前記インタ
ラプト発生部１０３９と同様に、フラグＦｉ（ｉ＝１，
２）がセットされているときにＦＩＦＯｉが“空”にな
ったら、割り込み信号Interrupt ２を“アクティブ”に
してプロセッサ１００に割り込みをかける。

【０１１９】上述した実施例においては、パケット処理
装置５００は、ＦＩＦＯバッファ１０１０内でパケット
が完結した時点で、該パケットを取り出す。換言すれ
ば、ＦＩＦＯバッファ１０１０内でパケットが未完結な
場合、そのパケットデータdataのＦＩＦＯバッファ１０
１０からの出力を抑制できる。これにより、プロセッサ
１００のソフトウェア処理により、ＦＩＦＯバッファ１
０１０にいったん入力された未完結なパケットの一部の
データdataをＦＩＦＯバッファ１０１０から取り出し一
時的にメモリ３００上に設け不図示の退避領域に退避さ
せておき、その後、この退避領域に退避させていたパケ
ットデータdataを再びＦＩＦＯバッファ１０１０に復帰
させることによりこのパケットをその他のパケットと同
様にＦＩＦＯバッファ１０１０内で完結させることが可
能である。

【０１２０】このような機能は、プロセッサ１００がマ
ルチプログラム処理をサポートしている場合に有効であ
る。この場合、複数のプロセス（ここで、プロセスとは
１つのプログラムの走行単位とする）が、１つのＦＩＦ
Ｏバッファ（ＦＩＦＯ１またはＦＩＦＯ２）をキューと
して共有する際、あるプロセスが該ＦＩＦＯバッファに
パケットを書き込んでいる途中で、別のプロセスに実行
権がスイッチされこの別のプロセスがＦＩＦＯバッファ
にパケットを書き込む場合があり得る。このような場
合、上記機能を利用することにより、両プロセスがＦＩ
ＦＯバッファに正しくパケットを書き込むことが可能に
なる。

【０１２１】図２０及び図２１は、上記機能を実現する
プロセッサ１００並びにキュー装置１０００，２０００
もしくは３０００の動作を説明するフローチャートであ
る。図２０のフローチャートは、プロセッサ１００がプ
ロセスＡの実行中に該プロセスＡの実行を中断し、他の
プロセスＢの実行に移行する場合の動作を説明するフロ
ーチャートである。

【０１２２】この場合、プロセッサ１００はオーバーフ
ロー制御部１０３０（２０３０もしくは３０３０）を介
しＦＩＦＯバッファ１０１０の書き込みポインタの値を
読み出す（ステップＳ１０１）。

【０１２３】次に、該書き込みポインタの指すアドレス
のデータdataをオーバーフロー制御部１０３０（２０３
０もしくは３０３０）を介しＦＩＦＯバッファ１０１０
から読み出し（ステップＳ１０２）、該データがプロセ
スＡが書き込み途中のデータdataであるか否か判別する
（ステップＳ１０３）。そして、プロセスＡが書き込み
途中のデータdataであれば（Ｓ１０３，ＹＥＳ）、この
データdataをメモリ３００上の退避領域に退避する。そ
して、このデータの退避に伴ってＦＩＦＯバッファ１０
１０の書き込みポインタを修正する（ステップＳ１０
４）。

【０１２４】上記ステップＳ１０１〜Ｓ１０４の処理
を、プロセスＡが書き込み途中の全てのデータdataをＦ
ＩＦＯバッファ１０１０からメモリ３００の上記退避領
域に退避するまで繰り返し、ＦＩＦＯバッファ１０１０
内にプロセスＡが書き込み途中のパケットのデータdata
が無くなると（Ｓ１０３，ＮＯ）、処理を終了する。

【０１２５】以上の処理によって、プロセスＡがその実
行中にＦＩＦＯバッファ１０１０に書き込んでいた未完
結のパケットがメモリ３００の特定領域に退避される。
次に、図２１はプロセッサ１００がプロセスＢの実行を
終了して再びプロセスＡの実行を再開する前に行う動作
を説明するフローチャートである。

【０１２６】プロセッサ１００は、上記メモリ３００上
の上記退避領域を調べ、該退避領域にプロセスＡの退避
データdataが存在するか否か調べる（ステップＳ２０
１）。そして、該退避データdataが存在すれば（Ｓ２０
１，ＹＥＳ）、これをオーバーフロー制御部１０３０
（２０３０または３０３０）を介してＦＩＦＯバッファ
１０１０に転送する。そして、該転送したデータ長に応
じてＦＩＦＯバッファ１０１０の書き込みポインタを更
新する（Ｓ２０２）。

【０１２７】以上の処理により、ＦＩＦＯバッファ１０
１０にはプロセスＢが書き込んだパケットに続いて、プ
ロセスＡが中断させられる前に書き込んでいた未完結の
パケットのデータdataが格納される。そして、これによ
り、プロセスＡは実行再開後、残りのパケットデータda
taを該格納済のパケットデータdataに続いて書き込み、
ＦＩＦＯバッファ１０１０に完結したパケットを書き込
むことが可能になる。前記図２０のステップＳ１０３に
おけるプロセスＡが書き込み途中のデータがＦＩＦＯバ
ッファ１０１０内に存在するか否かの判別は、例えば、
以下のような方法により行う。

【０１２８】 前記図１４に示すように、ＦＩＦＯバ
ッファ１０１０に格納する各パケットデータにend bit
を付加する構成を採用する場合、ＦＩＦＯバッファ１０
１０に最後に書き込まれたパケットデータに付加されて
いるend bit の値を調べる。そして、該end bit に
“０”（パケットの末尾データではないことを示す情
報）が設定されていた場合には、プロセスＡが書き込み
途中のデータがＦＩＦＯバッファ１０１０内に在ると判
断する。そして、この場合には、図２２に示すようにen
d bit が“１”（パケットの末尾データであることを示
す情報）に設定されている前パケットの末尾データの直
前に格納されているパケットデータ（data) をメモリ３
００上に設けられた退避領域に退避させる。

【０１２９】 バスインタフェース４００にＦＩＦＯ
バッファ１０１０に書き込まれるパケットのデータ数を
計数するカウンタを設ける。このカウンタは、ＦＩＦＯ
バッファ１０１０内に対するパケットの書き込み動作が
開始される毎に計数を開始し、ＦＩＦＯバッファ１０１
０にパケットの最後のデータの書き込みを終了した時点
で“０”にリセットされ計数を終了する。したがって、
プロセスＡからプロセスＢへの切り換えが発生した場
合、上記カウンタの値を調べることにより、プロセスＡ
がパケットの書き込み途中であったか否かを判断でき
る。すなわち、上記カウンタの値が“０”であればパケ
ットの書き込みは終了している。これに対し、該カウン
タの値が“０”でない場合は、プロセスＡが書き込み途
中のデータが該カウンタ値に等しい個数だけ有ることが
分かる。したがって、ＦＩＦＯバッファ１０１０の末尾
（一番最後に書かれたデータ）から、そのカウンタ値に
等しい個数のデータをメモリ３００上の退避領域に退避
させる。

【０１３０】 前記図８または図１６に示すアービタ
１０５０または３０５０に対して、図２３に示すよう
に、入力信号pause と出力信号stopを付加する。入力信
号pause はアービタ１０５０または３０５０に対して
「停止」を指示する信号であり、出力信号stopはアービ
タ１０５０または３０５０がＦＩＦＯバッファ１０１０
からのデータ出力を停止させている状態（停止状態）を
示す信号である。

【０１３１】アービタ１０５０または３０５０は、paus
e 信号により「停止」が指示されると( 図２４(a) ）、
ＦＩＦＯバッファ１０１０からパケットＡの出力途中の
データが最後まで出力されるまで、すなわち、パケット
処理装置５００からアクティブのdone信号が出力される
までＦＩＦＯバッファ１０１０からデータを出力させる
（図２４(b) ，(c) ）。そして、パケットＡのデータが
最後まで出力されると、ＦＩＦＯバッファ１０１０から
のデータ出力を停止させ、上記「停止状態」を示すstop
信号をアクティブにする。したがって、stop信号がアク
ティブになっている状態においては、ＦＩＦＯバッファ
１０１０の先頭データは必ずパケットの先頭のデータと
なっている。

【０１３２】マイクロプロセッサ１００は、プロセスＡ
からプロセスＢへ実行プロセスを切り換える際、例え
ば、バスインタフェース４００を介してアービタ１０５
０または３０５０にアクティブのpause 信号を加える。
そして、stop信号がアクティブに変化するのをバスイン
タフェース１００を介して検出すると、ＦＩＦＯバッフ
ァ１０１０の先頭からデータを順次読み出して、ＦＩＦ
Ｏバッファ１０１０内の内容を解析することにより、不
完全なパケットすなわちプロセスＡが書き込み途中の未
完結なパケットのデータがＦＩＦＯバッファ１０１０内
にあるか否かを検出できる。

【０１３３】

【発明の効果】請求項１記載の発明によれば、ＦＩＦＯ
バッファに対してデータを書き込むデータ生成装置は、
ＦＩＦＯバッファが満杯になっても、ＦＩＦＯバッファ
に空きが生ずるまで待たされることなくデータの出力が
可能となり、処理効率が向上する。

【０１３４】また、この場合、ＦＩＦＯバッファにはア
クセス速度が高速の比較的小容量の記憶装置を、退避バ
ッファには該ＦＩＦＯバッファよりもアクセス速度が低
速で大容量の記憶装置を用いることにより、低コストで
高性能のキュー装置を実現できる。

【０１３５】請求項２記載の発明によれば、前記ＦＩＦ
Ｏバッファの残り容量に余裕が生じたことを検出でき、
前記退避バッファに退避されていたデータを、ハードウ
ェアまたはソフトウェア処理により正しい順序でＦＩＦ
Ｏバッファにリストアすることができる。そして、上記
フラグがリセットされた後、ＦＩＦＯバッファに空きが
ある間再びＦＩＦＯバッファの方にデータを書き込むこ
とができる。上記リストア処理をハードウェアで実現し
た場合には、プロセッサに対して割り込みが生じないた
め、プロセッサの処理を妨害せず、高いシステム性能が
得られる。一方、上記リストア処理をマイプロセッサに
よるソフトウェア処理により実現した場合には複雑なハ
ードウェアが不要となり、実装面積も小さくできる。

【０１３６】請求項３記載の発明によれば、例えば、プ
ロセッサ等に割り込みをかけ、前記退避バッファのサイ
ズを拡張するなどの処理が可能になる。請求項４記載の
発明においては、計数手段の計数値を参照することによ
り、パケット処理装置は、ＦＩＦＯバッファ内において
パケットが完結してからパケットのデータを連続して取
り出すことが可能になり、パケット処理を効率良く行う
ことができる。特に、複数のＦＩＦＯバッファからパケ
ットを取り出して処理するパケット処理装置において
は、データの揃ったＦＩＦＯバッファからデータを取り
出して処理を開始することができ、効率のよい処理が可
能となる。

【０１３７】また、格納パケット数が多いＦＩＦＯバッ
ファの方から優先的にパケットを取り出して処理するな
どの機能も実現できる。請求項５記載の発明において
は、パケット生成装置はＦＩＦＯバッファが満杯になっ
ても、ＦＩＦＯバッファに空きが生ずるまで待たされる
ことなく、パケットデータの出力が可能となり、処理効
率が向上する。

【０１３８】請求項６記載の発明においては、上記請求
項５記載の発明によって前記退避バッファに退避されて
いたパケットを、その一部のデータが退避されていたパ
ケットも含め、正しい順序並びに正しい形式で上記ＦＩ
ＦＯバッファにリストアできる。

【０１３９】請求項７記載の発明においては、計数手段
１２の計数値を参照して、未完結のパケットのデータが
ＦＩＦＯバッファから出力されてしまう事態を抑止でき
る。また、前記ＦＩＦＯバッファ内に完結しているパケ
ットが存在しているか否かを知ることができるので、パ
ケット処理装置は前記ＦＩＦＯバッファ内でパケットが
完結してから、該パケットの取り出しを開始することに
より、前記ＦＩＦＯバッファ内にパケットの全データが
揃うまで待つという無駄な待ち時間を解消でき、効率の
良いパケット処理ができる。

【０１４０】請求項８記載の発明においては、ＦＩＦＯ
バッファからパケットデータと共に出力される特定のビ
ットの値を参照することにより、パケット処理装置はＦ
ＩＦＯバッファから読み出したデータがパケットの最後
のデータであるか否かを容易に検出できる。これにより
上記請求項４記載の発明の計数手段のデクリメント信号
の生成が容易になる。

【０１４１】請求項９記載の発明においては、計数手段
によりＦＩＦＯバッファに格納されているパケットデー
タの個数が計数される。パケット完結検出手段は、該計
数値とＦＩＦＯバッファの先頭に格納されているパケッ
トのそのサイズ情報が設定されているデータを入力し
て、両者を比較することによりＦＩＦＯバッファ内に完
結しているパケットが存在するか否か検出する。

【０１４２】したがって、このパケット完結手段の検出
情報を利用して、ＦＩＦＯバッファ内の未完結のパケッ
トデータがパケット処理装置に出力されてしまう状態を
回避させることができる。

【０１４３】請求項１０記載の発明においては、パケッ
ト生成装置は、上記請求項９記載の発明のＦＩＦＯバッ
ファに空きが生じていない間でも、生成したパケットを
出力できるので、処理効率が向上する。

【０１４４】請求項１１記載の発明においては、上記請
求項１０記載の発明により退避バッファに退避されてい
たパケットを、その一部のデータが退避されていたパケ
ットも含め、正しい順序並びに正しい形式で空きの生じ
たＦＩＦＯバッファに随時リストアできる。また、これ
により、上記ＦＩＦＯバッファからパケットを取り出し
て処理を行うパケット処理装置は、上記退避バッファか
ら退避されていたパケットデータがＦＩＦＯバッファに
転送されるまでの間、待機している必要がなくなり、無
駄な待ち時間を削減できる。

【０１４５】請求項１２記載の発明によれば、プロセス
ＡがＦＩＦＯバッファにパケットのデータを書き込んで
いる途中であっても、新たに起動されたプロセスＢはＦ
ＩＦＯバッファにパケットを書き込むことが可能にな
る。そして、再びプロセスＢが再起動された際には、プ
ロセスＢはＦＩＦＯバッファに残りのパケットデータを
書き込むことにより、ＦＩＦＯバッファに正しくパケッ
トを書き込むことが可能になる。したがって、ＦＩＦＯ
バッファ内に既に格納済の未完結のパケットのデータの
退避及びその復帰が可能である。

【図面の簡単な説明】

【図１】本発明の原理を説明する図（その１）である。

【図２】本発明の原理を説明する図（その２）である。

【図３】本発明の原理を説明する図（その３）である。

【図４】本発明の原理を説明する図（その４）であく

【図５】本発明の一実施例のキュー装置の全体構成を示
すブロック図である。

【図６】ＦＩＦＯバッファを、パケットを格納するキュ
ーとして使用する場合の一実施例を示す模式図である。

【図７】上述した図６に示す構成のＦＩＦＯバッファに
格納するパケットの各データに該データがパケットの最
後のデータであるか否かを示す１ビットの情報（end bi
t)を付加するようにした実施例を示す図である。

【図８】本発明の実施例のキュー装置を適用したプロセ
ッサ要素の全体的な回路構成を示すブロック図てある。

【図９】(a) ，(b) は、上記図８に示すインタラプト発
生部１０３９の回路構成例を示す図である。

【図１０】上記図８に示すＦＩＦＯバッファ（ＦＩＦＯ
１，ＦＩＦＯ２）に格納されるパケットの形式を示す図
である。

【図１１】上記図８に示す退避バッファ１０２０に退避
されるパケットの形式を示す図である。

【図１２】退避バッファからＦＩＦＯバッファへのデー
タリストア処理を完全にハードウェアで実現するキュー
装置を実装したプロセッサ要素で用いられる退避バッフ
ァの構成例を示す図である。

【図１３】上記データリストア処理をハードウェアによ
り実現するキュー装置を実装したプロセッサ要素の全体
構成を示すブロック図である。

【図１４】上記図１３に示すキュー装置内の退避バッフ
ァ１０２０に格納されるパケットデータの形式を示す図
である。

【図１５】上記図１３に示すキュー装置の動作を説明す
るフローチャートである。

【図１６】本発明のさらに別の実施例であるキュー装置
を実装したプロセッサ要素の全体構成を示すブロック図
である。

【図１７】上記図１６に示すＦＩＦＯバッファの構成を
説明する図である。

【図１８】上記図１７に示すＦＩＦＯバッファに書き込
まれるパケットの形式を示す図である。

【図１９】上記図１６に示すオーバーフロー制御部内に
おけるインタラプト発生部の構成を示す図である。

【図２０】プロセッサがプロセスＡの実行中に該プロセ
スＡの実行を中断し、同一のＦＩＦＯバッファをキュー
として共有する他のプロセスＢの実行に移行する場合の
動作を説明するフローチャートである。

【図２１】プロセッサが前記プロセスＢの実行を終了し
て再び前記プロセスＡの実行を再開する前に行う動作を
説明するフローチャートである。

【図２２】上記図２０で述べたＦＩＦＯバッファに格納
する各パケットデータにend bitを付加する動作を採用
する例を示す図である。

【図２３】前記図８または図１６に示すアービタに対し
て、入力信号pause と出力信号stopを付加する構成を説
明する図である。

【図２４】(a) ，(b) は、上記図２３に示す構成のアー
ビタの動作を説明する図である。

【符号の説明】

１，１１，２１，４１ ＦＩＦＯバッファ ２，１３，２３ 退避バッファ ３，１４，２４ フラグ ４，１５，２５ 第１の検出手段 ５，４３ データ退避手段 ６，１７，２７ 第２の検出手段 ７，１８，２８，４４ データリストア手段 ８ 第３の検出手段 １２ 計数手段 １６，２６ パケットデータ退避手段 １９，２３ パケット完結検出手段 ４２ 記憶手段

フロントページの続き (72)発明者 清水 俊幸 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 石畑 宏明 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内

Claims (12)

【特許請求の範囲】
1. 【請求項１】 ＦＩＦＯバッファと、 該ＦＩＦＯバッファに書き込まれるデータが退避される
   退避バッファと、 該退避バッファにデータが退避されているか否かを示す
   フラグと、 上記ＦＩＦＯバッファの残り容量が予め定められた第１
   の閾値より少なくなったことを検出する第１の検出手段
   と、 該第１の検出手段により上記ＦＩＦＯバッファの残り容
   量が上記第１の閾値よりも少なくなったことが検出され
   ると、その後の上記ＦＩＦＯバッファに対する書き込み
   データを前記退避バッファに退避させると共に前記フラ
   グをセットさせ、該フラグがセットされている状態の
   間、上記ＦＩＦＯバッファに対する書き込みデータを前
   記退避バッファの方に書き込むデータ退避手段と、 を備えたことを特徴とするキュー装置。
2. 【請求項２】 前記フラグがセットされている状態のと
   きに、前記ＦＩＦＯバッファの残り容量が予め定められ
   た第２の閾値よりも多くなったことを検出する第２の検
   出手段と、 該第２の検出手段によりＦＩＦＯバッファの残り容量が
   上記第２の閾値よりも多くなったことが検出された際、
   前記退避バッファに退避されていたデータを上記ＦＩＦ
   Ｏバッファに転送し、前記退避バッファに退避されてい
   るデータが無くなったときに前記フラグをリセットする
   データリストア手段と、 をさらに備えたことを特徴とする請求項１記載のキュー
   装置。
3. 【請求項３】 前記退避バッファの残り容量が予め定め
   られた第３の閾値よりも少なくなったことを検出し、該
   検出時に特定の信号を発生する第３の検出手段を、 さらに備えたことを特徴とする請求項１記載のキュー装
   置。
4. 【請求項４】 パケットが格納されるＦＩＦＯバッファ
   と、 該ＦＩＦＯバッファに格納されるパケットの個数を計数
   する計数手段と、 を備えたことを特徴とするキュー装置。
5. 【請求項５】 前記ＦＩＦＯバッファに書き込まれるパ
   ケットのデータが退避される退避バッファと、 該退避バッファにパケットデータが退避されているか否
   かを示すフラグと、 前記ＦＩＦＯバッファの残り容量が予め定められた第１
   の閾値よりも少なくなったことを検出する第１の検出手
   段と、 該第１の検出手段により前記ＦＩＦＯバッファの残り容
   量が前記第１の閾値よりも少なくなったことが検出され
   ると、その後のＦＩＦＯバッファに対する書き込みデー
   タを前記退避バッファに退避させると共に前記フラグを
   セットさせ、該フラグがセットされている状態の間、上
   記ＦＩＦＯバッファに対する書き込みデータを前記退避
   バッファの方に書き込むパケットデータ退避手段と、 をさらに備えたことを特徴とする請求項４記載のキュー
   装置。
6. 【請求項６】 前記フラグがセットされている状態のと
   きに、前記計数手段の計数値が予め定められた第２の閾
   値よりも少なくなったことを検出する第２の検出手段
   と、 該第２の検出手段により前記ＦＩＦＯバッファに格納さ
   れているパケット数が上記第２の閾値よりも少なくなっ
   たことが検出された際、前記退避バッファに退避されて
   いたデータを上記ＦＩＦＯバッファに転送し、前記退避
   バッファに退避されているデータが無くなったときに前
   記フラグをリセットするデータリストア手段と、 をさらに備えたことを特徴とする請求項５記載のキュー
   装置。
7. 【請求項７】 前記計数手段の計数値を参照して、前記
   ＦＩＦＯバッファ内に完結しているパケットデータが存
   在するか否かを検出するパケット完結検出手段を、 さらに備えたことを特徴とする請求項４記載のキュー装
   置。
8. 【請求項８】 前記ＦＩＦＯバッファに格納される各パ
   ケットデータには、該パケットデータが当該パケットの
   最後のデータであるか否かを示す情報が設定されたビッ
   トが付加されること、 を特徴とする請求項４記載のキュー装置。
9. 【請求項９】 パケットサイズを示す情報が設定されて
   いるデータを有するパケットが格納されるＦＩＦＯバッ
   ファと、 前記ＦＩＦＯバッファ内に格納されているパケットデー
   タの個数を計数する計数手段と、 該計数手段の計数値と、前記ＦＩＦＯバッファの先頭に
   格納されているパケットの上記パケットサイズ情報が設
   定されているデータとを入力して、前記ＦＩＦＯバッフ
   ァ内に完結しているパケットが存在するか否かを検出す
   るパケット完結検出手段と、 を備えたことを特徴とするキュー装置。
10. 【請求項１０】 前記ＦＩＦＯバッファに書き込まれる
    パケットのデータが退避される退避バッファと、 該退避バッファにパケットデータが退避されているか否
    かを示すフラグと、 前記ＦＩＦＯバッファの残り容量が予め定められた第１
    の閾値よりも少なくなったことを検出する第１の検出手
    段と、 該第１の検出手段により前記ＦＩＦＯバッファの残り容
    量が前記第１の閾値よりも少なくなったことが検出され
    ると、その後の上記ＦＩＦＯバッファに対する書き込み
    データを前記退避バッファに退避させると共に前記フラ
    グをセットさせ、該フラグがセットされている状態の
    間、上記ＦＩＦＯバッファに対する書き込みデータを前
    記退避バッファの方に書き込むパケットデータ退避手段
    と、 をさらに備えたことを特徴とする請求項９記載のキュー
    装置。
11. 【請求項１１】 前記フラグがセットされている状態の
    ときに、前記計数手段の計数値が予め定められた第２の
    閾値よりも少なくなったことを検出する第２の検出手段
    と、 該第２の検出手段によりＦＩＦＯバッファの残り容量が
    上記第２の閾値よりも少なくなったことが検出された
    際、前記退避バッファに退避されていたデータを上記Ｆ
    ＩＦＯバッファに転送し、前記退避バッファに退避され
    ているデータが無くなったときに前記フラグをリセット
    するデータリストア手段と、 をさらに備えたことを特徴とする請求項１０記載のキュ
    ー装置。
12. 【請求項１２】 複数のプロセスによってパケットが書
    き込まれるＦＩＦＯバッファと、 記憶手段と、 プロセスＡが上記ＦＩＦＯバッファにパケットを書き込
    んでいる途中で別のプロセスＢに実行権が切り換えられ
    た際、上記プロセスＡが書き込んだ未完結のパケットデ
    ータを上記ＦＩＦＯバッファから取り出し上記記憶手段
    に退避させるデータ退避手段と、 再び前記プロセスＡに実行権が移行した際、該プロセス
    Ａの実行開始前に前記記憶手段に退避させておいたパケ
    ットデータを前記ＦＩＦＯバッファに転送させるデータ
    リストア手段と、 を備えたことを特徴とするキュー装置。