JPH08315566A - Ｆｉｆｏ待ち行列システム - Google Patents

Ｆｉｆｏ待ち行列システム

Info

Publication number
JPH08315566A
JPH08315566A JP8084894A JP8489496A JPH08315566A JP H08315566 A JPH08315566 A JP H08315566A JP 8084894 A JP8084894 A JP 8084894A JP 8489496 A JP8489496 A JP 8489496A JP H08315566 A JPH08315566 A JP H08315566A
Authority
JP
Japan
Prior art keywords
queue
data
state machine
fifo
fifo queue
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP8084894A
Other languages
English (en)
Inventor
S Krech Alan Jr
アラン・エス・クレッチ、ジュニア
D Scott Noel
ノエル・ディー・スコット
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
HP Inc
Original Assignee
Hewlett Packard Co
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hewlett Packard Co filed Critical Hewlett Packard Co
Publication of JPH08315566A publication Critical patent/JPH08315566A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F5/06—Methods or arrangements for data conversion without changing the order or content of the data handled for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 【課題】ＦＩＦＯ待ち行列を含む待ち行列システムの処
理能力を向上させる。 【解決手段】第１の装置が、データ・ブロック単位また
はデータ・ブロックを構成するデータ項目単位いずれか
の増分値でＦＩＦＯ待ち行列にデータを書き込む。ＦＩ
ＦＯの空き空間があるか否かＦＩＦＯ待ち行列状態がデ
ータ・ブロック書き込みに先がけて検証される。各書き
込み動作に先行して行われるＦＩＦＯ待ち行列状態を調
べるポーリングは必要とされない。第２の装置がデータ
・ブロック単位またはデータ項目単位いずれかの増分値
でＦＩＦＯ待ち行列からデータを読み取る。第２の装置
が第１の装置に追いつくことなくＦＩＦＯ待ち行列から
読み取ることができように第１の装置はＦＩＦＯへの書
き込みを開始した後第２の装置へ読み取り開始可能信号
を送る。これによって、読み取りデータがあるか否かを
判断するためのＦＩＦＯ待ち行列状態のポーリングの必
要性が排除される。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、待ち行列システム
に関するもので、特に、論理機構とポーリングの必要性
を最小にすることによる先入れ先出し(ＦＩＦＯ)待ち行
列の処理性能改善に関するものである。
【０００２】
【従来の技術】実装回路空間および状態ポーリングの必
要性を最小にとどめる効率的で高性能な待ち行列システ
ムを実現することは、３次元画像装置において使用され
る高性能低コストのグラフィックス・アクセラレータ回
路の分野における課題である。限られた回路空間環境に
おいて最大処理性能および効率を実現するように製品を
設計しなければならないため、他の電子装置と同様に、
グラフィックス・アクセラレータ回路においても、より
小さくより効率的な待ち行列システムを実現することが
必要とされる。
【０００３】伝統的ＦＩＦＯ待ち行列システムは、ＦＩ
ＦＯ待ち行列に書き込みを行う一般的に装置"Ａ"と呼ば
れる少くとも１つの電子装置（またはコンポーネントま
たはプロセス）、および、同じＦＩＦＯ待ち行列から読
み取りを行う一般的に装置"Ｂ"と呼ばれる別の少なくと
も１つの電子装置（またはコンポーネントまたはプロセ
ス）を備える。装置ＡにとってＦＩＦＯ待ち行列へ書込
みを行うことのできる空間があるか否かを知ることは有
益であり、装置ＢにとってＦＩＦＯ待ち行列から読み取
ることのできるデータがあるか否かを知ることは有益で
ある。伝統的ＦＩＦＯ待ち行列システムは、各書込み動
作に先行して空間が使用可能であるか否かを判断するよ
うにＦＩＦＯ待ち行列コンローラに要求することによっ
て、上記のような空間およびデータの使用可能性の問題
を解決している。ＦＩＦＯ待ち行列コントローラが、"f
ull(十分な空間なし)"という標識で応答する場合、装置
Ａは待機し、ＦＩＦＯ待ち行列へ書込みを行う空間がで
きるまでＦＩＦＯ待ち行列コントローラへのポーリング
を繰り返す。その間、装置Ａは、現行の処理がＦＩＦＯ
待ち行列への書込みを終わるまで、別の処理を実行する
ことはできない。
【０００４】同様に、装置Ｂは、各読取り動作に先行し
てデータが読み取ることのできる状態にあるか否か判断
するため、ＦＩＦＯ待ち行列コンローラをポーリングす
る必要がある。ＦＩＦＯ待ち行列コントローラが、"emp
ty(データなし)"という標識で応答するならば、装置Ｂ
は待機し、ＦＩＦＯ待ち行列から読み取るデータができ
るまでＦＩＦＯ待ち行列コントローラへのポーリングを
繰り返す。その間、装置Ｂは、ＦＩＦＯ待ち行列から新
しいデータを読み取るまで、別の処理を実行することが
できない。
【０００５】
【発明が解決しようとする課題】しかしながら、回路空
間に制約があり、処理時間を浪費する状態ポーリングを
許容できない高性能電子装置において実施されるＦＩＦ
Ｏ待ち行列の使用にとって、上述のような伝統的ＦＩＦ
Ｏ待ち行列システムを実施するために必要とされる一見
単純な論理機構でも規模は過大であり、各書込み／読取
り動作に先行する状態ポーリングの反復はコストがかか
りすぎる。
【０００６】このような理由のため、伝統的ＦＩＦＯ待
ち行列システムは、３次元画像装置において使用される
グラフィックス・アクセラレータ回路のような高性能電
子装置の実装回路空間および処理性能に対する要求を満
たすことができない。かくして、効率的で高性能なＦＩ
ＦＯ待ち行列システムが必要とされる。
【０００７】
【課題を解決するための手段】待ち行列システムに関す
る本発明の性能向上によって、上述された問題は解決さ
れ、当分野において技術的進歩が達成される。本発明の
性能向上待ち行列システムは、第１の状態マシン""Ａお
よび第２の状態マシン"Ｂ"を含む複数の電子装置を有す
るグラフィックス・アクセラレータ回路によって実現さ
れる。上記状態マシン"Ａ"および"Ｂ"のはともに、ＦＩ
ＦＯ待ち行列コントローラによって制御されるＦＩＦＯ
待ち行列に電気的に接続し、相互に非同期的に動作す
る。状態マシンＡは、部分的にデータを処理してＦＩＦ
Ｏ待ち行列へ結果を出力する。状態マシンＢは、ＦＩＦ
Ｏ待ち行列からデータを読み取り、そのデータを処理し
て、他の下流ハードウェアにその結果を出力する。
【０００８】待ち行列システムの第１の改善は、ＦＩＦ
Ｏ待ち行列に対する書込み／読み取りに先立って必要と
されるＦＩＦＯ待ち行状態ポーリングの回数を減少する
ことによって実現される。ＦＩＦＯ待ち行列コントロー
ラは、待ち行列状態要求に対して単に"full"標識を返す
のではなく、ＦＩＦＯ待ち行列の利用可能空間の数量に
関する情報を回答する。ＦＩＦＯ待ち行列の利用可能空
間において記憶できるデータの量を状態マシンＡは判断
することができるので、状態マシンＡは、ＦＩＦＯ待ち
行列状態について一度ポーリングを行えば、その後は、
各書き込み動作に先行するポーリング割込みを反復して
行わずとも、複数の計算によって、使用可能ＦＩＦＯ待
ち行列空間に書き込まれる複数の出力を生成することが
できる。ＦＩＦＯ待ち行列へ書き込むべき出力を生成す
ることに先行して、使用可能ＦＩＦＯ待ち行列空間が存
在することがわかるので、上記の結果は効率的な待ち行
列システムである。本明細書において、複数の出力を
「データ・ブロック（data chunk；データ・チャンク：
データかたまり）」と呼び、複数の出力のそれぞれ１つ
を「データ項目」と呼ぶこととする。データ・ブロック
は、ＦＩＦＯ待ち行列における使用可能データ・ブロッ
ク空間へ、データ項目単位の増分値で書き込むことがで
きるであろうし、あるいは、書き込み動作効率を更に向
上させるため、１回の書き込み動作で１つのデータ・ブ
ロック全体をＦＩＦＯ待ち行列に書き込むこともできる
であろう。本発明の好ましい実施形態では、データ・ブ
ロック範囲内のデータがデータ項目増分値で書き込まれ
る。
【０００９】同様に、ＦＩＦＯ待ち行列コントローラ
は、読み取り動作に先行して待ち行列状態要求に対し
て"empty"標識を返すのではなく、ＦＩＦＯ待ち行列に
おけるデータの存在に関する情報を返す。データの存在
が、ＦＩＦＯ待ち行列において少くとも１つのデータ・
ブロックが読み取り可能な状態にあることを標示するこ
ともできるし、あるいは、ＦＩＦＯ待ち行列において少
くとも１つのデータ・ブロック中の少なくとも１つのデ
ータ項目が読み取り可能な状態にあることを標示しても
よい。状態マシンＢは、データ・ブロックが使用可能か
否かＦＩＦＯ待ち行列状態についてポーリングを１回だ
け行なえばよく、その後は、データ項目単位増分で全デ
ータ・ブロックのデータを読み取るか、あるいは、読み
取り動作効率の向上のためデータ・ブロック単位増分で
データを読み取ることもできる。各読取り動作に先行す
るポーリング割込みの反復は発生しない。
【００１０】代替的形態として、状態マシンＡが同じＦ
ＩＦＯ待ち行列にデータを書き込むことができる速度と
同じ速度または遅い速度で状態マシンＢがデータを読む
ことが既知であるという前提に立てば、ＦＩＦＯ待ち行
列からのデータ読み取りに先立ち、状態マシンＢはＦＩ
ＦＯ待ち行列状態に関して１回ポーリングを行うだけで
よく、その後はいかなる理由でもＦＩＦＯ待ち行列状態
のポーリングを要求する必要はない。この代替形態で
は、状態マシンＡの状態に永久に追いつくことなしに状
態マシンＢがＦＩＦＯ待ち行列からの読み取りを継続す
ることができるように、状態マシンＡはＦＩＦＯ待ち行
列に対する先頭開始(head start)書き込みデータを確保
する。
【００１１】待ち行列システムの第２の改善は、上記第
１の改善を含む上に、更に、状態マシンＡが信号線を経
由して状態マシンＢに信号を送る時まで状態マシンＢの
開始を遅延するように制御する機能を付加する。状態マ
シンＡは、上記第１の待ち行列システム改善形態におけ
る場合と同様に、ＦＩＦＯ待ち行列にデータを書き込
む。一旦所定量のデータがＦＩＦＯ待ち行列に書き込ま
れると、状態マシンＡは、状態マシンＢに対してＦＩＦ
Ｏ待ち行列からの読み取りを開始するように信号を送
る。状態マシンＡがＦＩＦＯ待ち行列に書き込むことが
できる速度と同じまたはそれより遅い速度で状態マシン
ＢがＦＩＦＯ待ち行列からデータを読み取るので、状態
マシンＢは、読み取るデータを常に持ち、状態マシンＡ
に決して追いつくことはない。このような構成によっ
て、より小規模な回路の実施が可能となるとともに、読
み取りに先行するポーリングが必要とされなくなる。
【００１２】
【発明の実施の形態】グラフィックス・アクセラレータ・アーキテクチャ 図１は、３次元画像装置に使用されるグラフィックス・
アクセラレータ・ハードウェアのアーキテクチャ１００
を示す。図１に示されるアーキテクチャは、図解のため
の例に過ぎず、本発明をいかなる特別のハードウェア・
アーキテクチャまたは実施形態に制限するものではな
い。伝統的グラフィックス・アクセラレータは、ソフト
ウェアおよび一般的マイクロコード化されたプロセッサ
として実施される浮動小数点指向アーキテクチャではあ
るが、アーキテクチャ１００と伝統的グラフィックス・
アクセラレータのアーキテクチャの間の基本的相違は、
アーキテクチャ１００がハードワイヤード制御機構、動
的論理浮動小数点メガ・セルおよび高度にカスタマイズ
された固定データ経路を含むという点にある。特に、ア
ーキテクチャ１００は、幾何学マトリックス変換、多角
形分解、オブジェクト明照／陰影、遠近法調整、切り取
り、および、ランダムな方向に向いている多角形ならび
にベクトルに関する平面／傾斜方程式計算を実行するよ
うに設計されている。このアーキテクチャ１００におい
て処理される典型的な多角形は、３辺または４辺多角形
である。
【００１３】アーキテクチャ１００は、最も共通に処理
される特性を持つ最も共通のプリミティブだけを迅速に
かつ効率的に処理し下流のハードウェアによる後続処理
を容易にすることによって、一層大規模な全般的３次元
処理方式を支援するように設計されている。アーキテク
チャ１００の形態は、回路空間を最小にし過剰処理時間
を少なくすることが求められる環境において実施される
ので、使用可能回路空間の使用度を最大にし、高性能規
格を維持する努力を払うことによって、処理効率全体を
向上し、より小規模回路の設計を実施する必要がある。
【００１４】アーキテクチャ１００は、制御装置１３５
によって制御される第１のマイクロプロセッサ１１０お
よび制御装置１４５によって制御される第２のマイクロ
プロセッサ１２５を有する複式プロセッサ・ベクトル処
理設計である。以下の記述において、上記第１のマイク
ロプロセッサを状態マシンＡ、上記第２のマイクロプロ
セッサを状態マシンＢとそれぞれ呼称する。動作的に
は、状態マシンＡは、伝統的ＦＩＦＯ待ち行列１０２を
経由して入力される頂点プリミティブを前処理する。二
重ランダム・アクセス・メモリ(ＲＡＭ)バッファ１０５
および１０７が、マイクロプロセッサ１１０がプリミテ
ィブを取り出すステージング領域を提供する。マイクロ
プロセッサ１１０は、ＦＩＦＯ／ＲＡＭメモリ１１２お
よび１１５を経由してマイクロプロセッサ１２５へ結果
を渡す前に、入力プリミティブに対して、幾何学変換、
部分的傾斜計算、その他の予備計算などを含む初期的浮
動小数点演算を実行する。マイクロプロセッサ１１０
は、メモリ、マスター・マルチプレクサ、レジスタ、そ
の他の浮動小数点コンポーネント等を含む複数のプロセ
ッサ・エレメント１１１を含む。制御装置１３５は、ア
ドレス復号、変換、分解および位置援助のような処理命
令をプロセッサ・エレメント１１１に対して与える。
【００１５】ＦＩＦＯ／ＲＡＭメモリ装置１１２および
１１５が、メモリ・コントローラ１１３および１１６に
よってそれぞれ制御される。メモリ・コントローラ１１
３および１１６は、複合型ＦＩＦＯ／ＲＡＭメモリ方式
および本発明の処理向上待ち行列システムの２つを実現
する。処理されるプリミティブのタイプおよび実行され
る計算に依存して、メモリ１１２および１１５は、ＦＩ
ＦＯ待ち行列としてあるいはＲＡＭメモリとして適時使
用される。ＦＩＦＯ待ち行列として使用される時、メモ
リ１１２または１１５は、本発明の改良待ち行列システ
ムを使用して状態マシンＡから状態マシンＢへのデータ
引き渡しを実施する。
【００１６】メモリ装置１１２および１１５からの出力
は、切り取りＲＡＭステージング装置１１８から出力さ
れるら明照位置、輝度、カラーおよび方向と統合され
る。統合されたデータは、マイクロプロセッサ１２５に
よる処理のため入力ラッチ待ち行列１２１に送られる。
マイクロプロセッサ１２５は、メモリ、マスター・マル
チプレクサ、レジスタ、その他の浮動小数点コンポーネ
ント等を含む複数のプロセッサ・エレメント１２４を含
む。制御装置１４５は、アドレス復号、変換、分解およ
び位置援助のような処理命令をプロセッサ・エレメント
１２４に対して与える。マイクロプロセッサ１２５によ
る処理が完了したものは伝統的ＦＩＦＯ待ち行列１２７
へ出力され、本発明の開示の範囲外の下流ハードウエア
による後続の処理に備えられる。
【００１７】伝統的ＦＩＦＯ待ち行列システム 伝統的ＦＩＦＯ待ち行列システムと本発明の改良待ち行
列システム実施形態の間の相違を考察する場合共通の処
理シナリオを使用する。この処理シナリオは、４個の頂
点各々について使用可能とされる８つの光度を持つ３次
元四辺形プリミティブを状態マシンＡおよびＢが完全に
処理するために必要とされるＦＩＦＯ待ち行列コントロ
ーラ・ポーリングおよび読取り／書込みメモリ・アクセ
スの数量に焦点をあてる。処理を完了するために必要と
される特定の計算は、本例の目的範囲を越えている。し
かし、３次元プリミティブにおける基本ｘ、ｙ、ｚ座標
に関する計算は、例示の目的としての処理が発生する相
対的位置として識別される。四辺形の例は、例示の目的
だけのものであって、本発明に対する制限を意図するも
のではない。
【００１８】図２は、ベクトル処理システムのための伝
統的ＦＩＦＯ待ち行列システム２００を示す。ＦＩＦＯ
待ち行列１１２は、制御装置１３５によって制御される
マイクロプロセッサ１１０を含む第１の状態マシン"
Ａ"、および制御装置１４５によって制御されるマイク
ロプロセッサ１２５を含む第２の状態マシン"Ｂ"にサー
ビスを提供する。状態マシンＡおよびＢは、必要に応じ
てハンドシェーキング(握手)制御２１０によって相互の
間の活動を連絡し調整する。入力待ち行列１０２が、処
理のため状態マシンＡにプリミティブ・データを与え
る。出力待ち行列１２７は、状態マシンＢによって処理
されたプリミティブを、必要な場合下流のハードウェア
へ送付するため待ち行列に入れる。
【００１９】状態マシンＡは、状態制御線２２０および
データ経路２３０によってＦＩＦＯ待ち行列１１２に接
続される。状態制御線２２０は、状態マシンＡがＦＩＦ
Ｏ待ち行列状態をポーリングする時そのような情報を状
態マシンＡに通知するために使用される。ＦＩＦＯ待ち
行列状態は、ＦＩＦＯ待ち行列１１２が"full(いっぱ
い)"である時点を標示する。データ経路２３０は、処理
されたデータをＦＩＦＯ待ち行列１１２に出力するため
状態マシンＡによって使用される。
【００２０】状態マシンＢは、状態制御線２４０および
データ経路２５０によってＦＩＦＯ待ち行列１１２に接
続される。状態制御線２４０は、状態マシンＢがＦＩＦ
Ｏ待ち行列１１２の状態を調べるためＦＩＦＯ待ち行列
コントローラ１１３をポーリングする時そのような情報
を状態マシンＢに通知するためＦＩＦＯ待ち行列コント
ローラ１１３によって使用される。ＦＩＦＯ待ち行列１
１２に使用可能データがない場合、ＦＩＦＯ待ち行列コ
ントローラ１１３は、ＦＩＦＯ待ち行列"empty(空)"状
態を戻す。データ経路２５０は、状態マシンＢが処理を
遂行できる状態にある時ＦＩＦＯ待ち行列１１２からデ
ータを読み取るため状態マシンＢによって使用される。
【００２１】図３は、図２の待ち行列システム２００に
基づく状態マシンＡとＦＩＦＯ待ち行列１１２の間の伝
統的動作の相互交信プロセスを示す。伝統的待ち行列シ
ステム２００を使用する四辺形プリミティブを完全に処
理するため状態マシンＡによって必要とされるＦＩＦＯ
待ち行列１１２状態のポーリングおよび書込みアクセス
の回数は、４＊(８＊４)=１２８回の動作である。すな
わち、８つの光度を持つ４つの頂点の各々について４回
の計算が存在する。
【００２２】待ち行列システム２００を含むシステムの
動作は、図３のステップ３０２におけるシステム初期化
に続いて、状態マシンＡを始動する（ステップ３０
３）。状態マシンＡは、初期化され動作可能状態になる
と、処理すべきプリミティブがあるか否かを判断する
（ステップ３０４）。処理すべきプリミティブがない場
合、状態マシンＡは、ステップ３０４を繰り返して待機
する。プリミティブが使用可能になり次第、プリミティ
ブが入力待ち行列１０２から読み取られ（ステップ３０
６）、状態マシンＡは、プリミティブの処理を開始す
る。
【００２３】処理の最初のステップとして、状態マシン
Ａは、ＦＩＦＯ待ち行列１１２の空間が使用可能である
か否かを判断するためＦＩＦＯ待ち行列コントローラ１
１３をポーリングする（ステップ３０７）。空間が使用
可能でない場合、ＦＩＦＯ待ち行列１１２の空間が使用
可能となるまで、状態マシンＡは、このプリミティブに
関しこれ以上の処理を行わず、ステップ３０７で待機す
る。ＦＩＦＯ待ち行列１１２の空間が使用可能である
時、状態マシンＡは、ステップ３１０でｘ座標計算を実
行し、ステップ３１２でＦＩＦＯ待ち行列１１２に結果
を書き込む。
【００２４】次に、状態マシンＡは、ＦＩＦＯ待ち行列
１１２の空間が使用可能であるか否かを判断するためＦ
ＩＦＯ待ち行列コントローラ１１３をポーリングする
（ステップ３１５）。ＦＩＦＯ待ち行列１１２の空間が
使用可能となるまで、状態マシンＡは、このプリミティ
ブに関しこれ以上の処理を行わず、ステップ３１５で待
機する。ＦＩＦＯ待ち行列１１２の空間が使用可能であ
る時、状態マシンＡは、ステップ３２０でｙ座標計算を
実行し、ステップ３２０でＦＩＦＯ待ち行列１１２に結
果を書き込む。ｚ座標計算に関するポーリング、計算お
よび書込みが継続し（ステップ３２４、３２７および３
２９）、ｘ，ｙ、ｚ座標の平方の和に関するポーリン
グ、計算および書込みが実行される（ステップ３３３、
３３５および３３７）。
【００２５】本実施例の四辺形プリミティブ・シナリオ
は、４つの頂点の各々について使用可能にされる８段階
の光度を持つので、ステップ３４０の判断は、３０７な
いし３３７の処理ステップを通して８つの光度に関する
処理サイクルを制御し、ステップ３４１の判断は、３０
７ないし３４０の処理ステップを通して４つの頂点関す
る処理サイクルを制御する。各頂点についてすべての光
度が処理されると、処理はステップ３４０および３４４
を通過し、状態マシンＡが次のプリミティブの処理を開
始することができる（ステップ３４８）。
【００２６】図４は、状態マシンＢがＦＩＦＯ待ち行列
１１２からデータを読む場合の伝統的な動作のプロセス
を示す。伝統的待ち行列システム２００に関するステッ
プ３０２のシステム初期化に続いて、状態マシンＢが図
４のステップ３６３において始動される。ステップ３０
２におけるシステム初期化に続く状態マシンＡの始動と
同時に状態マシンＢが始動されるので、状態マシンＡが
最終的にＦＩＦＯ待ち行列１１２にデータを書き込むま
で、状態マシンＢはステップ３６５でＦＩＦＯ待ち行列
コントローラ１１３に対するポーリングを繰り返さなけ
ればならない。状態マシンＢがＦＩＦＯ待ち行列コント
ローラ１１３から"not empty(空でない)"状態標識を受
け取ると（ステップ３６５）、状態マシンＢは、ＦＩＦ
Ｏ待ち行列１１２からｘ座標データを読み取る（ステッ
プ３６５）。ＦＩＦＯ待ち行列１１２からｙ座標、Ｚ座
標およびｘ、ｙ、ｚ座標平方総和データを読み取るま
で、状態マシンＢはＦＩＦＯ待ち行列１１２に対するポ
ーリングおよび読み取りを継続する（ステップ３６９な
いし３８２）。
【００２７】すべてのデータが状態マシンＢによって読
み取られると、プリミティブに関する最終計算が実行さ
れる（ステップ３８４）。その結果が出力待ち行列１２
７へ出力される（ステップ３８５）。４つの頂点の各々
について８つ光度の計算サイクルがあるので、ステップ
３８７の判断は、ステップ３６５ないし３８５までの処
理を４つの頂点各々について８回繰り返す。すべての頂
点がステップ３８７で処理されたなら、状態マシンＢは
必要に応じて他のデータの処理を継続する（ステップ３
９０）。
【００２８】ＦＩＦＯ待ち行列システムの改良 図５は、アーキテクチャ１００のようなベクトル処理シ
ステムに関する改善されたＦＩＦＯ待ち行列システム４
００を示す。ＦＩＦＯ待ち行列１１２は、制御装置１３
５によって制御されるマイクロプロセッサ１１０を含む
第１の状態マシンＡおよび制御装置１４５によって制御
されるマイクロプロセッサ１２５を含む第２の状態マシ
ンＢにサービスを提供する。状態マシンＡおよびＢはハ
ンドシェーキング制御４１０によって必要に応じて相互
にプロトコールを通信するが、相互の読み書きは非同期
的に行われる。入力待ち行列１０２は、状態マシンＡに
処理すべきデータを提供する。出力待ち行列１２７は、
状態マシンＢで処理されたプリミティブを下流ハードウ
ェアへの送信に備えて待ち行列に入れる。
【００２９】状態マシンＡは、状態制御線４２０および
データ経路４３０によってＦＩＦＯ待ち行列１１２に接
続される。状態マシンＡが状態情報を求めてＦＩＦＯ待
ち行列コントローラ１１３に対してポーリングを行う場
合、ＦＩＦＯ待ち行列コントローラ１１３は状態制御線
４２０を用いてＦＩＦＯ待ち行列１１２の状態を状態マ
シンＡに通知する。ＦＩＦＯ待ち行列システム４００の
改善の鍵は、ＦＩＦＯ待ち行列コントローラー１１３が
ＦＩＦＯ待ち行列１１２の利用可能空間量に関する情報
を回答するため状態制御線４２０を使用する点にある。
ＦＩＦＯ待ち行列１１２の利用可能空間は、空きのバイ
トかワードの数か、または、既知のサイズのＦＩＦＯ待
ち行列１１２に所在するデータの量から引き出されるで
あろう。状態マシンＡがＦＩＦＯ待ち行列１１２の使用
可能空間に記憶することができるデータ量を判断できる
ので、状態マシンＡはＦＩＦＯ待ち行列１１２の状態を
一度ポーリングすれば、その後は、各書込み動作に先立
ちポーリング割り込みを繰り返さずに、ＦＩＦＯ待ち行
列空き空間に書かれる複数データ項目を生成する複数の
計算を実行することができる。ＦＩＦＯ待ち行列１１２
へ書き込むべきデータの生成に先行して、ＦＩＦＯ待ち
行列１１２の空間が存在することが判明するので、上記
構成は一層効率的な待ち行列システムを生み出す。ＦＩ
ＦＯ待ち行列１１２におけるデータ・ブロック書き込み
可能空き空間にデータ項目単位の増分値で１つのデータ
・ブロックが書き込まれるか、あるいは、書き込み動作
の効率化を図るため１つのデータ・ブロック全体が一度
にＦＩＦＯ待ち行列１１２に書き込まれる。本発明の好
ましい実施形態は、データ項目単位の増分値でデータ・
ブロックを書き込む。
【００３０】データ経路４３０はＦＩＦＯ待ち行列１１
２への書き込みのため、状態マシンＡによって使用され
る。４つの頂点の各々について８つの光度を持つ３次元
四辺形プリミティブという本実施形態の処理シナリオに
おいては、データ・ブロックは、各頂点毎に４片のデー
タからなる８つの光源計算の結果を含む。すなわち、各
データ・ブロック中のデータ項目のすべてをＦＩＦＯ待
ち行列１１２に書き込むため、４回だけのＦＩＦＯ待ち
行列１１２状態要求ポーリングが必要とされる。状態マ
シンＢは、状態制御線４４０およびデータ経路４５０に
よってＦＩＦＯ待ち行列１１２に接続される。状態マシ
ンＢが状態情報を求めてＦＩＦＯ待ち行列コントローラ
１１３に対してポーリングを行う時、ＦＩＦＯ待ち行列
１１２は状態制御線４４０を使用してＦＩＦＯ待ち行列
１１２の状態を状態マシンＢに通知する。本実施形態の
改善では、ＦＩＦＯ待ち行列１１２のデータの存在に関
する情報を通知するため、状態制御線４４０がＦＩＦＯ
待ち行列コントローラ１１３によって使用される。状態
マシンＢは、１つのデータ・ブロックが読み取り可能状
態にあるか否かを判断するため１度だけＦＩＦＯ待ち行
列１１２の状態についてポーリングを行う必要があり、
その後は、データ項目単位の増分値で１つのデータ・ブ
ロック全体を読み取るか、読みとり動作の効率化を図る
ため１つのデータ・ブロック全体を一度に読み取る。各
読取り動作に先行するポーリング割込みの繰り返しは起
きない。代替的形態としては、ＦＩＦＯ待ち行列１１２
からのデータ読み取りに先行して、状態マシンＢがＦＩ
ＦＯ待ち行列１１２の状態に関するポーリングを一度行
い、状態マシンＢの読み取り速度が、態機械Ａが同じＦ
ＩＦＯ待ち行列にデータを書き込む速度と同じまたは遅
いということが既知であることを前提とすれば、その後
はいかなる理由にせよＦＩＦＯ待ち行列状態を決して要
求しない。この場合、状態マシンＢが状態マシンＡに永
久に追いつくことなくＦＩＦＯ待ち行列１１２からの読
み取りを継続できるように、状態マシンＡはＦＩＦＯ待
ち行列１１２への先頭開始書き込みデータを取得する。
いずれの場合でも、状態マシンＢが処理を遂行できる準
備ができている時、ＦＩＦＯ待ち行列１１２からデータ
を読み取るため、データ経路４５０は状態マシンＢによ
って使用される。
【００３１】図５に示されるＦＩＦＯ待ち行列システム
４００に基づいて、図６は、状態マシンＡとＦＩＦＯ待
ち行列１１２の間の動作上の交信プロセスを示す。待ち
行列システム４００を使用して四辺形プリミティブを処
理する状態マシンＡによって要求されるＦＩＦＯ待ち行
列１１２要求ポーリングおよび書込みアクセスの回数
は、４＊１＝４回の動作である。すなわち、処理される
４つの頂点の各々に関するすべての処理結果を出力する
ために４つのデータ・ブロック空間が必要とされる。
【００３２】図６に示されるように、待ち行列システム
４００を含むシステムに関して、状態マシンＡはシステ
ム初期化（ステップ５０２）に続いて始動される（ステ
ップ５０３）。動作可能状態になると、状態マシンＡ
は、処理するプリミティブがあるか否か判断する（ステ
ップ５０５）。もし処理するプリミティブがなければ、
状態マシンＡは待機する。待機中、状態マシンは他のタ
スクを継続することができる。プリミティブが使用可能
になると、入力待ち行列１０２からプリミティブが読み
取られる（ステップ５０６）。プリミティブが読み取ら
れると、状態マシンＡはプリミティブの処理を開始す
る。
【００３３】最初のステップとして、状態マシンＡは、
データ・ブロックのために適切なサイズのＦＩＦＯ待ち
行列１１２使用可能空間があるか否かを判断するためＦ
ＩＦＯ待ち行列コントローラ１１３に対しポーリングを
行う（ステップ５０７）。必要とされるデータ・ブロッ
クのサイズは、処理するために使用可能な計算の数およ
び計算によって生成される出力の数によって決定され
る。必要サイズのデータ・ブロック空間が使用可能状態
になければ、ＦＩＦＯ待ち行列１１２の空間が使用可能
になるまで、状態マシンＡは、このプリミティブに関す
る処理をこれ以上進めない（ステップ５０７）。ＦＩＦ
Ｏ待ち行列１１２の空間が使用可能になり次第、状態マ
シンＡはｘ座標計算を実行し（ステップ５１０）、ＦＩ
ＦＯ待ち行列１１２に結果を書く（ステップ５１２）。
続いて、ｙ座標、ｚ座標およびｘ、ｙ、ｚ座標平方和を
計算し（ステップ５１８、５２７および５３５）、それ
ぞれ書き込む（ステップ５２０、５２９および５３
７）。４つの頂点の各々について使用可能とされる８つ
の光度を持つ本実施形態の四辺形プリミティブにおいて
は、ステップ５４０の判断に従って、ステップ５０７な
いし５３７を通して８つの光度についての処理サイクル
が制御され、ステップ５４４の判断に従って、ステップ
５０７ないし５４０を通して４つの頂点についての処理
サイクルが制御される。各頂点についてのすべての光度
が処理されると、状態マシンＡは、次のプリミティブの
処理を開始する（ステップ５４８）。状態マシンＡは、
書き込み効率向上のため、データ・ブロック全体を一度
に書き込むことがもできるが、本発明にとって好ましく
は、データ項目単位の増分値でデータ・ブロックを書き
込む。
【００３４】図７は、状態マシンＢがＦＩＦＯ待ち行列
１１２からデータを読み取る動作プロセスを示す。待ち
行列システム４００に関して、システム初期化（ステッ
プ５０２）に続いて状態マシンＢが始動される（ステッ
プ５６２）。ステップ５０２におけるシステム初期化に
続く状態マシンＡと同時に、状態マシンＢは始動される
ので、状態マシンＡが最終的にＦＩＦＯ待ち行列１１２
にデータを書き終わるまで、状態マシンＢはＦＩＦＯ待
ち行列コントローラ１１３に対するポーリングを繰り返
し、待機しなければならない（ステップ５６５）。状態
マシンＢは、状態マシンＡと非同期的に動作する。デー
タがＦＩＦＯ待ち行列１１２で使用可能であると判断す
ると（ステップ５６５）、状態マシンＢは、ＦＩＦＯ待
ち行列１１２からデータを読み取る（ステップ５６
７）。データは、効率向上のためデータ・ブロック全体
として読み取ることもでき、あるいは、データ項目増分
値にわけてデータ・ブロックを読み取ることもできる。
ＦＩＦＯ待ち行列１１２の状態は、ＦＩＦＯ待ち行列１
１２の空き空間の量として、ＦＩＦＯ待ち行列１１２に
現在所在するデータの量として、あるいは、現在いかな
るデータも存在しないか否かの情報として、いずれかを
選択して標示される。
【００３５】すべてのデータが状態マシンＢにとって使
用可能となると、最終的処理が実行される（ステップ５
８４）。結果が出力待ち行列１２７へ出力される（ステ
ップ５８５）。四辺形プリミティブに関して４つの頂点
の各々に８つの光度があるので、ステップ５８７の判断
に従って、ステップ５６５ないし５８５の処理は４つの
頂点の各々につて４回繰り返される。すべての４つの頂
点の処理が完了すると（ステップ５８７）、状態マシン
Ｂは必要に応じて次の処理を続ける（ステップ５９
０）。
【００３６】本発明の好ましいＦＩＦＯ待ち行列システ
ム 図８は、アーキテクチャ１００のようなベクトル処理シ
ステムに使用される好ましいＦＩＦＯ待ち行列システム
６００を示す。ＦＩＦＯ待ち行列１１２は、制御装置１
３５によって制御されるマイクロプロセッサ１１０を含
む第１の状態マシンＡおよび制御装置１４５によって制
御されるマイクロプロセッサ１２５を含む第２の状態マ
シンＢにサービスを提供する。状態マシンＡおよびＢは
ハンドシェーキング制御６１０によって必要に応じて相
互にプロトコールを通信する。入力待ち行列１０２は、
状態マシンＡに処理すべきデータを提供する。出力待ち
行列１２７は、状態マシンＢで処理されたプリミティブ
を下流ハードウェアへの送信に備えて待ち行列に入れ
る。
【００３７】状態マシンＡは、状態制御線６２０および
データ経路６３０によってＦＩＦＯ待ち行列１１２に接
続される。状態制御線６２０は、ＦＩＦＯ待ち行列１１
２の使用可能空間量に関する情報を回答するために、Ｆ
ＩＦＯ待ち行列コントローラ１１３によって使用され
る。状態マシンＡは、図５および図６について上述した
ような書込み動作を実行する。データ経路６３０は、Ｆ
ＩＦＯ待ち行列１１２にデータを書き込むため状態マシ
ンＡによって使用される。
【００３８】状態マシンＢは、データ経路６５０によっ
てのみＦＩＦＯ待ち行列１１２に接続される。常に状態
マシンＡが状態マシンＢより前に進んでいるように、状
態マシンＢは状態マシンＡの後から開始するように制御
されるので、ＦＩＦＯ待ち行列１１２と状態マシンＢの
間で状態制御線は使用されない。状態マシンＢに感知さ
れる１ビット「Ｂ開始」制御線６０５を介して状態マシ
ンＡが状態マシンＢに信号を送ると、状態マシンＢが開
始する。ＦＩＦＯ待ち行列１１２の状態ポーリングが除
去されるため、処理効率が向上し、状態ＢおよびＦＩＦ
Ｏ待ち行列コントローラ１１３の回路実装が単純化され
る。データ経路６５０は、状態マシンＢが処理を実行す
る準備ができている時、ＦＩＦＯ待ち行列１１２からデ
ータを読み取るため状態マシンＢによって使用される。
データは、読み取り動作の効率化を図るため１つのデー
タ・ブロック全体として読み取られるか、あるいは、本
発明の好ましい実施形態において行われるようにデータ
項目単位の増分値で読み取られる。
【００３９】図８に示される好ましいＦＩＦＯ待ち行列
システム６００に基づいて、図９は、状態マシンＡとＦ
ＩＦＯ待ち行列１１２の間の動作上の交信プロセスを示
す。状態マシンＡがＦＩＦＯ待ち行列１１２に書き込む
ために必要なＦＩＦＯ待ち行列１１２のポーリングの回
数は、図５に基づいた図６の記述の場合と同一である。
【００４０】好ましいＦＩＦＯ待ち行列システム６００
を含むシステムに関して、システム初期化（ステップ７
０２）に続いて、状態マシンＡが始動される（ステップ
７０３）。初期化され使用可能状態になると、状態マシ
ンＡは、処理すべきプリミティブが使用可能か否かを判
断する（ステップ７０５）。処理するプミティブが使用
可能でなければ、状態マシンＡは待機する（ステップ７
０５）。待機中状態マシンＡは他のタスクを実行するこ
ともできる。プリミティブが使用可能になり次第、プリ
ミティブが入力待ち行列１０２から読み取られる（ステ
ップ７０６）。一旦プリミティブが読み取られると、状
態マシンＡはプリミティブの処理を開始する。
【００４１】最初のステップとして、状態マシンＡはＦ
ＩＦＯ待ち行列コントローラ１１３に対するポーリング
を行ってＦＩＦＯ待ち行列１１２の空き空間がデータ・
ブロックに適切な大きさか否かを判断する（ステップ７
０７）。必要なデータ・ブロックの大きさは、処理する
ために使用可能な計算の数および各計算が生成する対応
する出力の数によって決定される。データ・ブロックの
ためのＦＩＦＯ待ち行列１１２空間が使用可能でなけれ
ば、使用可能になるまで、状態マシンＡはこのプリミテ
ィブの処理を進めない。ＦＩＦＯ待ち行列１１２空間が
使用可能になると、状態マシンＡは、すべての光度につ
いてｘ、ｙ、ｚ座標計算を実行し（ステップ７１０）、
ｘ、ｙ、ｚ座標の平方和を計算する（ステップ７１
１）。計算結果がＦＩＦＯへ書き込まれる（ステップ７
１０、７１１）。データは、書き込み動作の効率化を図
るため１つのデータ・ブロック全体として書き込まれる
か、あるいは、本発明の好ましい実施形態において行わ
れるようにデータ項目単位の増分値で書き込まれる。ス
テップ７１２に続いて、状態マシンＡは、「Ｂ開始」ビ
ットをオンにして、状態マシンＡが十分な先頭開始情報
を持ち、少くとも１つのデータ・ブロックの少くとも１
つのデータ項目が状態マシンＢによる読み取りに備えて
準備ができていることを状態マシンＢに通知する。状態
マシンＢは、データ・ブロック全体がＦＩＦＯ待ち行列
１１２に書き込まれるまでか、あるいは、所望の状態マ
シンＡ先頭開始に基づいて第１のデータ・ブロック内の
第１のデータ項目が書き込まれるまで、読み取りを待た
なければならない。状態マシンＡがデータ処理を終了す
るかまたはＦＩＦＯ待ち行列１１２が空になるまで、
「Ｂ開始」ビットはオンのままにされる。
【００４２】本実施形態の四辺形プリミティブが４つの
頂点の各々について使用可能とされる８つの光度を持つ
ので、ステップ７４０の判断に従って、ステップ７１０
ないし７１１を通して８つの光度についての処理サイク
ルが制御され、ステップ７４４の判断に従って、ステッ
プ７０７ないし７４０を通して４つの頂点についての処
理サイクルが制御される。各頂点についてすべての光度
が処理されると、処理はステップ７４０および７４４を
通過し、状態マシンＡが後続プリミティブの処理を開始
する（ステップ７４８）。
【００４３】図１０は、ＦＩＦＯ待ち行列１１２から読
み取りを行う状態マシンＢに関する好ましい動作プロセ
スを示す。本発明の好ましい待ち行列システム６００に
関して、システム初期化（ステップ７６２）に続いて、
状態マシンＢが始動される（ステップ７６２）。ステッ
プ７０２におけるシステム初期化に続く状態マシンＡの
始動と同じ時点で状態マシンＢが始動されるが、状態マ
シンＢは、データ・ブロックが使用可能か否かを決定す
るためのＦＩＦＯ待ち行列コントローラ１１３に対する
ポーリングを行わない。状態マシンＡが状態マシンＢに
関する先頭開始情報を持ち、少くとも１つのデータ・ブ
ロックの少くとも１つのデータ項目がＦＩＦＯ待ち行列
１１２で使用可能であることを標識する「Ｂ開始」ビッ
トがオンにされるまで、状態マシンＢは他のタスクを実
行する。状態マシンＢは、ＦＩＦＯ待ち行列コントロー
ラ１１３からのＦＩＦＯ待ち行列１１２状態通知を必要
としない。状態マシンＢが「Ｂ開始」ビットのオンを検
出すると（ステップ７６４）、ｘ、ｙ、ｚ座標および平
方和データがＦＩＦＯ待ち行列１１２から読み取られる
（ステップ７６７）。すべてのデータが状態マシンＢに
とって使用可能となると、最終的計算が実行され（ステ
ップ７８４）、結果が待ち行列１２７へ出力される（ス
テップ７８５）。本実施形態の四辺形プリミティブが４
つの頂点の各々について使用可能とされる８つの光度を
持つので、ステップ７８７の判断に従って、ステップ７
６７ないし７８５を通して４つの頂点についての処理サ
イクルが制御される。すべての頂点が処理されると（ス
テップ７８７）、状態マシンＢは必要に応じて処理を継
続する（ステップ７９０）。
【００４４】以上本発明の特定の実施形態を記述した
が、当業者が本発明の原理を逸脱することなく本発明の
代替的実施形態を設計することができることは明らかで
ある。
【００４５】本発明には、例として次のような実施様態
が含まれる。 （１）電子装置において、ＦＩＦＯ待ち行列コントロー
ラによって制御されるＦＩＦＯ待ち行列、上記ＦＩＦＯ
待ち行列へ書き込みを行う第１の装置、および上記ＦＩ
ＦＯ待ち行列から読み取りを行う第２の装置を備える待
ち行列システムであって、上記ＦＩＦＯ待ち行列コント
ローラを介してＦＩＦＯ待ち行列状態を生成する状態生
成機構と、上記ＦＩＦＯ待ち行列の空間が複数のデータ
項目からなるデータ・ブロックの１つを記憶するために
十分なサイズであるか否かを判断するデータ・ブロック
・サイズ識別機構と、上記データ・ブロックを書き込む
ことのできる空間が上記ＦＩＦＯ待ち行列において使用
可能な状態にある場合上記ＦＩＦＯ待ち行列にデータを
書き込む上記待ち行列コントローラのデータ書き込み制
御部分と、上記データ書き込み制御部分と非同期的に上
記ＦＩＦＯ待ち行列から上記データを読み取る上記待ち
行列コントローラのデータ読み取り制御部分と、を含む
待ち行列システム。 （２）使用可能空間量、既知のサイズのＦＩＦＯ待ち行
列中の非使用可能空間量、および上記ＦＩＦＯにデータ
が現在所在するか否かの情報からなるグループから選択
される形態で、上記ＦＩＦＯ待ち行列状態が上記ＦＩＦ
Ｏ待ち行列の使用可能空間に関する情報を含む、上記
（１）に記載の待ち行列システム。 （３）上記データ書き込み制御部分が、データ・ブロッ
ク単位またはデータ項目単位いずれかの増分値で上記デ
ータを書き込む、上記（１）に記載の待ち行列システ
ム。 （４）上記データ読み取り制御部分が、データ・ブロッ
ク単位またはデータ項目単位いずれかの増分値で上記デ
ータを読み取る、上記（１）に記載の待ち行列システ
ム。
【００４６】（５）電子装置において、ＦＩＦＯ待ち行
列コントローラによって制御されるＦＩＦＯ待ち行列、
上記ＦＩＦＯ待ち行列へ書き込みを行う第１の装置、お
よび上記ＦＩＦＯ待ち行列から読み取りを行う第２の装
置を備える待ち行列システムであって、上記ＦＩＦＯ待
ち行列コントローラを介してＦＩＦＯ待ち行列状態を生
成する状態生成機構と、上記ＦＩＦＯ待ち行列の空間が
複数のデータ項目からなるデータ・ブロックの１つを記
憶するために十分なサイズであるか否かを判断するデー
タ・ブロック・サイズ識別機構と、上記データ・ブロッ
クを書き込むことのできる空間が上記ＦＩＦＯ待ち行列
において使用可能な状態にある場合上記ＦＩＦＯ待ち行
列にデータを書き込む上記待ち行列コントローラのデー
タ書き込み制御部分と、上記データが上記ＦＩＦＯ待ち
行列において使用可能であることを上記第２の装置へ標
示するための信号と、上記信号に応答して上記ＦＩＦＯ
待ち行列から上記データを読み取る上記待ち行列コント
ローラのデータ読み取り制御部分と、を含む待ち行列シ
ステム。 （６）使用可能空間量、既知のサイズのＦＩＦＯ待ち行
列中の非使用可能空間量、および上記ＦＩＦＯにデータ
が現在所在するか否かの情報からなるグループから選択
される形態で、上記ＦＩＦＯ待ち行列状態が上記ＦＩＦ
Ｏ待ち行列の使用可能空間に関する情報を含む、上記
（５）に記載の待ち行列システム。 （７）上記データ書き込み制御部分が、データ・ブロッ
ク単位またはデータ項目単位いずれかの増分値で上記デ
ータを書き込み、上記データ読み取り制御部分が、デー
タ・ブロック単位またはデータ項目単位いずれかの増分
値で上記データを読み取る、上記（５）に記載の待ち行
列システム。
【００４７】（８）電子装置において、ＦＩＦＯ待ち行
列コントローラによって制御されるＦＩＦＯ待ち行列、
上記ＦＩＦＯ待ち行列へ書き込みを行う第１の装置、お
よび上記ＦＩＦＯ待ち行列から読み取りを行う第２の装
置を備える待ち行列システムを使用する方法であって、
上記ＦＩＦＯ待ち行列コントローラを介して、上記ＦＩ
ＦＯ待ち行列の使用可能空間量に関する情報を含むＦＩ
ＦＯ待ち行列状態を生成するステップと、上記ＦＩＦＯ
待ち行列の空間が複数のデータ項目からなるデータ・ブ
ロックの１つを記憶するために十分なサイズであるか否
かを判断するステップと、上記データ・ブロックを書き
込むことのできる空間が上記ＦＩＦＯ待ち行列において
使用可能な状態にある場合、上記ＦＩＦＯ待ち行列にデ
ータを書き込むステップと、上記データ書き込みステッ
プと非同期的に、上記ＦＩＦＯ待ち行列から上記データ
を読み取るステップと、を含む待ち行列システム使用方
法。
【００４８】（９）電子装置において、ＦＩＦＯ待ち行
列コントローラによって制御されるＦＩＦＯ待ち行列、
上記ＦＩＦＯ待ち行列へ書き込みを行う第１の装置、お
よび上記ＦＩＦＯ待ち行列から読み取りを行う第２の装
置を備える待ち行列システムを使用する方法であって、
上記ＦＩＦＯ待ち行列コントローラを介して、上記ＦＩ
ＦＯ待ち行列の使用可能空間量に関する情報を含むＦＩ
ＦＯ待ち行列状態を生成するステップと、上記ＦＩＦＯ
待ち行列の空間が複数のデータ項目からなるデータ・ブ
ロックの１つを記憶するために十分なサイズであるか否
かを判断するステップと、上記データ・ブロックを書き
込むことのできる空間が上記ＦＩＦＯ待ち行列において
使用可能な状態にある場合、上記ＦＩＦＯ待ち行列にデ
ータを書き込むステップと、上記データが上記ＦＩＦＯ
待ち行列において使用可能であることを標示する信号を
上記第２の装置へ送るステップと、上記信号に応答して
上記ＦＩＦＯ待ち行列から上記データを読み取るステッ
プと、を含む待ち行列システム使用方法。
【００４９】
【発明の効果】待ち行列システムの処理能力の改善の結
果、書込み動作に関するＦＩＦＯ待ち行列状態スポーリ
ングの回数が減少し、データ書き込みに先行してＦＩＦ
Ｏ待ち行列データ・ブロック空間が使用可能か否かを判
断することによって、また、書き込み動作が先頭開始を
持つまで読取り動作の開始を遅延させることによって、
読み取り動作に関するポーリングが不要となる。
【図面の簡単な説明】
【図１】高速ＦＩＦＯ待ち行列を含むグラフィックス・
アクセラレータを示すブロック図である。
【図２】伝統的ＦＩＦＯ待ち行列システムを示すブロッ
ク図である。
【図３】伝統的ＦＩＦＯ待ち行列システムの状態マシン
Ａのプロセスを示す流れ図である。
【図４】伝統的ＦＩＦＯ待ち行列システムの状態マシン
Ｂのプロセスを示す流れ図である。
【図５】改良型ＦＩＦＯ待ち行列システムを示すブロッ
ク図である。
【図６】改良型ＦＩＦＯ待ち行列システムの状態マシン
Ａのプロセスを示す流れ図である。
【図７】改良型ＦＩＦＯ待ち行列システムの状態マシン
Ｂのプロセスを示す流れ図である。
【図８】本発明の好ましい実施形態のＦＩＦＯ待ち行列
システムを示すブロック図である。
【図９】本発明の好ましい実施形態のＦＩＦＯ待ち行列
システムの状態マシンＡのプロセスを示す流れ図であ
る。
【図１０】本発明の好ましい実施形態のＦＩＦＯ待ち行
列システムの状態マシンＢのプロセスを示す流れ図であ
る。
【符号の説明】 １００ アーキテクチャ １０２ 入力待ち行列 １１０、１３５ 状態マシンＡ １１２ ＦＩＦＯ待ち行列 １１３ ＦＩＦＯ待ち行列コントローラ １２５、１４５ 状態マシンＢ １２７ 出力待ち行列 ２００、４００、６００ ＦＩＦＯ待ち行列システム ２１０、４１０、６１０ ハンドシェーキング制御 ２２０、２４０、４２０、４４０、６２０
状態制御線 ２３０、４３０、６３０ データ入力用データ経路 ２５０、４５０、６５０ データ出力用データ経路 ６０５ 「Ｂ開始」ビット信号線

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】）電子装置において、ＦＩＦＯ待ち行列コ
    ントローラによって制御されるＦＩＦＯ待ち行列、上記
    ＦＩＦＯ待ち行列へ書き込みを行う第１の装置、および
    上記ＦＩＦＯ待ち行列から読み取りを行う第２の装置を
    備える待ち行列システムであって、 上記ＦＩＦＯ待ち行列コントローラを介してＦＩＦＯ待
    ち行列状態を生成する状態生成機構と、 上記ＦＩＦＯ待ち行列の空間が複数のデータ項目からな
    るデータ・ブロックの１つを記憶するために十分なサイ
    ズであるか否かを判断するデータ・ブロック・サイズ識
    別機構と、 上記データ・ブロックを書き込むことのできる空間が上
    記ＦＩＦＯ待ち行列において使用可能な状態にある場合
    上記ＦＩＦＯ待ち行列にデータを書き込む上記待ち行列
    コントローラのデータ書き込み制御部分と、 上記データ書き込み制御部分と非同期的に上記ＦＩＦＯ
    待ち行列から上記データを読み取る上記待ち行列コント
    ローラのデータ読み取り制御部分と、 を含む待ち行列システム。
JP8084894A 1995-05-16 1996-04-08 Ｆｉｆｏ待ち行列システム Pending JPH08315566A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US442,543 1982-11-18
US08/442,543 US5664114A (en) 1995-05-16 1995-05-16 Asynchronous FIFO queuing system operating with minimal queue status

Publications (1)

Publication Number Publication Date
JPH08315566A true JPH08315566A (ja) 1996-11-29

Family

ID=23757206

Family Applications (1)

Application Number Title Priority Date Filing Date
JP8084894A Pending JPH08315566A (ja) 1995-05-16 1996-04-08 Ｆｉｆｏ待ち行列システム

Country Status (2)

Country Link
US (1) US5664114A (ja)
JP (1) JPH08315566A (ja)

Families Citing this family (71)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH096614A (ja) * 1995-06-21 1997-01-10 Sanyo Electric Co Ltd データ処理装置
US5822752A (en) * 1996-07-15 1998-10-13 International Business Machines Corporation Method and apparatus for fast parallel determination of queue entries
US6807581B1 (en) 2000-09-29 2004-10-19 Alacritech, Inc. Intelligent network storage interface system
US6434620B1 (en) 1998-08-27 2002-08-13 Alacritech, Inc. TCP/IP offload network interface device
US7076568B2 (en) * 1997-10-14 2006-07-11 Alacritech, Inc. Data communication apparatus for computer intelligent network interface card which transfers data between a network and a storage device according designated uniform datagram protocol socket
US6427171B1 (en) 1997-10-14 2002-07-30 Alacritech, Inc. Protocol processing stack for use with intelligent network interface device
US7042898B2 (en) 1997-10-14 2006-05-09 Alacritech, Inc. Reducing delays associated with inserting a checksum into a network message
US7185266B2 (en) 2003-02-12 2007-02-27 Alacritech, Inc. Network interface device for error detection using partial CRCS of variable length message portions
US8621101B1 (en) 2000-09-29 2013-12-31 Alacritech, Inc. Intelligent network storage interface device
US8782199B2 (en) 1997-10-14 2014-07-15 A-Tech Llc Parsing a packet header
US7089326B2 (en) * 1997-10-14 2006-08-08 Alacritech, Inc. Fast-path processing for receiving data on TCP connection offload devices
US6389479B1 (en) 1997-10-14 2002-05-14 Alacritech, Inc. Intelligent network interface device and system for accelerated communication
US6697868B2 (en) 2000-02-28 2004-02-24 Alacritech, Inc. Protocol processing stack for use with intelligent network interface device
US6658480B2 (en) 1997-10-14 2003-12-02 Alacritech, Inc. Intelligent network interface system and method for accelerated protocol processing
US6427173B1 (en) 1997-10-14 2002-07-30 Alacritech, Inc. Intelligent network interfaced device and system for accelerated communication
US6591302B2 (en) 1997-10-14 2003-07-08 Alacritech, Inc. Fast-path apparatus for receiving data corresponding to a TCP connection
US7133940B2 (en) 1997-10-14 2006-11-07 Alacritech, Inc. Network interface device employing a DMA command queue
US7237036B2 (en) 1997-10-14 2007-06-26 Alacritech, Inc. Fast-path apparatus for receiving data corresponding a TCP connection
US6226680B1 (en) 1997-10-14 2001-05-01 Alacritech, Inc. Intelligent network interface system method for protocol processing
US6470415B1 (en) 1999-10-13 2002-10-22 Alacritech, Inc. Queue system involving SRAM head, SRAM tail and DRAM body
US6757746B2 (en) 1997-10-14 2004-06-29 Alacritech, Inc. Obtaining a destination address so that a network interface device can write network data without headers directly into host memory
US8539112B2 (en) 1997-10-14 2013-09-17 Alacritech, Inc. TCP/IP offload device
US7167927B2 (en) 1997-10-14 2007-01-23 Alacritech, Inc. TCP/IP offload device with fast-path TCP ACK generating and transmitting mechanism
US6687758B2 (en) 2001-03-07 2004-02-03 Alacritech, Inc. Port aggregation for network connections that are offloaded to network interface devices
US7174393B2 (en) 2000-12-26 2007-02-06 Alacritech, Inc. TCP/IP offload network interface device
US7284070B2 (en) * 1997-10-14 2007-10-16 Alacritech, Inc. TCP offload network interface device
US6310891B1 (en) 1997-12-18 2001-10-30 Alcatel Usa Sourcing, L.P. Method of scheduling time division multiplex (TDM) cells in a synchronous optical network (SONET) frame
US6169749B1 (en) 1997-12-18 2001-01-02 Alcatel Usa Sourcing L.P. Method of sequencing time division multiplex (TDM) cells in a synchronous optical network (sonet) frame
US6078588A (en) * 1997-12-18 2000-06-20 Alcatel Usa Sourcing, L.P. Queuing apparatus and method for avoiding address collision of data in a plurality of frames
US6353864B1 (en) * 1998-04-20 2002-03-05 Fujitsu Limited System LSI having communication function
US6129757A (en) 1998-05-18 2000-10-10 Scimed Life Systems Implantable members for receiving therapeutically useful compositions
US7616200B1 (en) 1998-06-12 2009-11-10 3Dlabs Inc. Ltd. System for reducing aliasing on a display device
US6476816B1 (en) 1998-07-17 2002-11-05 3Dlabs Inc. Ltd. Multi-processor graphics accelerator
US6459453B1 (en) 1998-07-17 2002-10-01 3Dlabs Inc. Ltd. System for displaying a television signal on a computer monitor
WO2000004436A1 (en) 1998-07-17 2000-01-27 Intergraph Corporation Graphics processing with transcendental function generator
US7518616B1 (en) 1998-07-17 2009-04-14 3Dlabs, Inc. Ltd. Graphics processor with texture memory allocation system
US6188410B1 (en) 1998-07-17 2001-02-13 3Dlabs Inc. Ltd. System for processing vertices from a graphics request stream
WO2000004527A1 (en) * 1998-07-17 2000-01-27 Intergraph Corporation Apparatus and method of directing graphical data to a display device
WO2000004484A2 (en) 1998-07-17 2000-01-27 Intergraph Corporation Wide instruction word graphics processor
WO2000004443A1 (en) 1998-07-17 2000-01-27 Intergraph Corporation Byte reordering apparatus and method
WO2000004494A1 (en) 1998-07-17 2000-01-27 Intergraph Corporation Graphics processing system with multiple strip breakers
US7664883B2 (en) 1998-08-28 2010-02-16 Alacritech, Inc. Network interface device that fast-path processes solicited session layer read commands
US6674440B1 (en) 1999-04-05 2004-01-06 3Dlabs, Inc., Inc. Ltd. Graphics processor for stereoscopically displaying a graphical image
US6507877B1 (en) 1999-09-03 2003-01-14 Whamtech, Inc. Asynchronous concurrent dual-stream FIFO
US8019901B2 (en) 2000-09-29 2011-09-13 Alacritech, Inc. Intelligent network storage interface system
US6720074B2 (en) * 2000-10-26 2004-04-13 Inframat Corporation Insulator coated magnetic nanoparticulate composites with reduced core loss and method of manufacture thereof
US7510571B2 (en) * 2001-06-11 2009-03-31 Boston Scientific, Scimed, Inc. Pleated composite ePTFE/textile hybrid covering
US20030121835A1 (en) * 2001-12-31 2003-07-03 Peter Quartararo Apparatus for and method of sieving biocompatible adsorbent beaded polymers
US7543087B2 (en) 2002-04-22 2009-06-02 Alacritech, Inc. Freeing transmit memory on a network interface device prior to receiving an acknowledgement that transmit data has been received by a remote device
US7496689B2 (en) 2002-04-22 2009-02-24 Alacritech, Inc. TCP/IP offload device
US7191241B2 (en) * 2002-09-27 2007-03-13 Alacritech, Inc. Fast-path apparatus for receiving data corresponding to a TCP connection
US7337241B2 (en) 2002-09-27 2008-02-26 Alacritech, Inc. Fast-path apparatus for receiving data corresponding to a TCP connection
US7653588B2 (en) * 2003-04-24 2010-01-26 Chicago Board Options Exchange, Incorporated Method and system for providing order routing to a virtual crowd in a hybrid trading system
US20050050285A1 (en) * 2003-08-26 2005-03-03 Haas William Robert Memory control system and method for installing new memory
US6996070B2 (en) * 2003-12-05 2006-02-07 Alacritech, Inc. TCP/IP offload device with reduced sequential processing
US8248939B1 (en) 2004-10-08 2012-08-21 Alacritech, Inc. Transferring control of TCP connections between hierarchy of processing mechanisms
US7496700B1 (en) * 2005-01-12 2009-02-24 Pmc-Sierra, Inc. Serial tunneling protocol (STP) flow control in SAS expanders without SATA link state machine
US7738500B1 (en) 2005-12-14 2010-06-15 Alacritech, Inc. TCP timestamp synchronization for network connections that are offloaded to network interface devices
DE102006041306A1 (de) * 2006-09-01 2008-03-20 Micronas Gmbh Speicherverwaltungs-Schaltungsanordnung und Speicherverwaltungsverfahren
US8539513B1 (en) 2008-04-01 2013-09-17 Alacritech, Inc. Accelerating data transfer in a virtual computer system with tightly coupled TCP connections
US8341286B1 (en) 2008-07-31 2012-12-25 Alacritech, Inc. TCP offload send optimization
US9306793B1 (en) 2008-10-22 2016-04-05 Alacritech, Inc. TCP offload device that batches session layer headers to reduce interrupts as well as CPU copies
US10254967B2 (en) 2016-01-13 2019-04-09 Sandisk Technologies Llc Data path control for non-volatile memory
US20180088904A1 (en) * 2016-09-26 2018-03-29 Knuedge, Inc. Dedicated fifos in a multiprocessor system
US10528255B2 (en) 2016-11-11 2020-01-07 Sandisk Technologies Llc Interface for non-volatile memory
US10528286B2 (en) 2016-11-11 2020-01-07 Sandisk Technologies Llc Interface for non-volatile memory
US10528267B2 (en) 2016-11-11 2020-01-07 Sandisk Technologies Llc Command queue for storage operations
US10114589B2 (en) 2016-11-16 2018-10-30 Sandisk Technologies Llc Command control for multi-core non-volatile memory
US10382380B1 (en) * 2016-11-17 2019-08-13 Amazon Technologies, Inc. Workload management service for first-in first-out queues for network-accessible queuing and messaging services
CN108415859B (zh) * 2018-04-28 2023-10-27 珠海一微半导体股份有限公司 一种激光陀螺仪数据的硬件加速电路
CN120316027B (zh) * 2025-06-17 2025-09-09 此芯科技集团有限公司 一种乱序投机执行发射队列及电子设备

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5097442A (en) * 1985-06-20 1992-03-17 Texas Instruments Incorporated Programmable depth first-in, first-out memory
US5021994A (en) * 1988-01-11 1991-06-04 Texas Instruments Incorporated Look-ahead flag generator
JPH04242852A (ja) * 1990-02-13 1992-08-31 Internatl Business Mach Corp <Ibm> 多重処理のための先入れ先出しバッファ待ち行列の管理機構および方法
US5455913A (en) * 1990-05-14 1995-10-03 At&T Global Information Solutions Company System and method for transferring data between independent busses
US5296936A (en) * 1991-07-22 1994-03-22 International Business Machines Corporation Communication apparatus and method for transferring image data from a source to one or more receivers
US5172228A (en) * 1991-11-19 1992-12-15 Utah State University Foundation Image compression method and apparatus employing distortion adaptive tree search vector quantization
US5299315A (en) * 1992-09-17 1994-03-29 International Business Machines Corp. Personal computer with programmable threshold FIFO registers for data transfer
US5455907A (en) * 1993-09-10 1995-10-03 Compaq Computer Corp. Buffering digitizer data in a first-in first-out memory
US5442747A (en) * 1993-09-27 1995-08-15 Auravision Corporation Flexible multiport multiformat burst buffer
US5469223A (en) * 1993-10-13 1995-11-21 Auravision Corporation Shared line buffer architecture for a video processing circuit
US5448558A (en) * 1994-04-05 1995-09-05 International Business Machines Corporation Method and apparatus for managing packet FIFOS

Also Published As

Publication number Publication date
US5664114A (en) 1997-09-02

Similar Documents

Publication Publication Date Title
JPH08315566A (ja) Ｆｉｆｏ待ち行列システム
US5821949A (en) Three-dimensional graphics accelerator with direct data channels for improved performance
EP2936492B1 (en) Multi-mode memory access techniques for performing graphics processing unit-based memory transfer operations
US5874969A (en) Three-dimensional graphics accelerator which implements multiple logical buses using common data lines for improved bus communication
US6628277B1 (en) Decompression of three-dimensional graphics data using mesh buffer references to reduce redundancy of processing
US7071935B1 (en) Graphics system with just-in-time decompression of compressed graphics data
EP0817010B1 (en) Floating point processor for a three-dimensional graphics accelerator
US6476808B1 (en) Token-based buffer system and method for a geometry pipeline in three-dimensional graphics
EP0817117B1 (en) Command processor for a three-dimensional graphics accelerator which includes geometry decompression capabilities and method for processing geometry data in said graphics accelerator
US6459429B1 (en) Segmenting compressed graphics data for parallel decompression and rendering
US8098255B2 (en) Graphics processing system with enhanced memory controller
US5956042A (en) Graphics accelerator with improved lighting processor
US6559854B2 (en) Image creation device
US20030169262A1 (en) System and method for handling display device requests for display data from a frame buffer
US7522171B1 (en) On-the-fly reordering of 32-bit per component texture images in a multi-cycle data transfer
US20030169626A1 (en) System and method for controlling a number of outstanding data transactions within an integrated circuit
US6864892B2 (en) Graphics data synchronization with multiple data paths in a graphics accelerator
EP1255227A1 (en) Vertices index processor
US5914724A (en) Lighting unit for a three-dimensional graphics accelerator with improved handling of incoming color values
US8243086B1 (en) Variable length data compression using a geometry shading unit
US8254701B1 (en) Data compression using a geometry shading unit
US8295621B1 (en) Data decompression using a geometry shading unit
US6308237B1 (en) Method and system for improved data transmission in accelerated graphics port systems
US6515670B1 (en) Graphics system and method for minimizing the idle time of a host processor in the graphics system
US6885375B2 (en) Stalling pipelines in large designs

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20051101

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20051108

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20060202

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20060221

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20060704