JPH04219859A - 並列プロセッサに直列命令ストリームデータを分散するハードウェアディストリビュータ - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、直列命令ストリームデ
ータを並列プロセッサに分散する方法及び装置に関する
ものであり、とりわけ、並列アレイをなすプロセッサ間
で直列ストリームをなす指令／データパケットを分散し
、プロセッサのデータ処理出力を組み換えて、簡単に元
のストリームと同じ配列の直列ストリームになるように
処理できるようにする方法及び装置に関するものである
。

【０００２】

【従来の技術】複数の処理装置を並列に用いることによ
って、処理速度が向上するのは周知のところである。例
えば、複雑なモデルを扱うためにかなりの演算処理を必
要とする対話式３次元グラフィックスのような用途の場
合、処理効率を改善するため、数年間にわたって並列処
理装置が用いられてきた。こうした処理効率の改善には
、１つ以上の並列処理装置に対して最適な入力順次デー
タの割当てを行なうメカニズムが必要になった。また、
元のデータ配列を維持しなければならない場合には、並
列処理装置のそれぞれから出力を読み取って、処理を施
されたデータの再配列を行なって、元のデータストリー
ムと同じ配列になるようにするメカニズムが必要になっ
た。しかしながら、こうした先行技術によるメカニズム
がうまくゆく場合は限定された。

【０００３】例えば、順次入力データを複数の並列処理
装置に割り当てる先行技術による技法の１つでは、並列
処理装置の１つをマスターとして割り当て、他の処理装
置はスレーブとして働くようにした。マスターは、普通
、適応ロード平衡アルゴリズムに従って、スレーブに対
して指令を送り出し、入力を受ける次の処理装置として
、バッファリングを施された仕事量が最も少ないスレー
ブを選択する。全てのスレーブが完全に入力バッファス
ペース外にある場合には、マスターが、活動処理装置に
なる。スレーブが、入力バッファスペースを利用できる
ようになり、最小数の指令が実行されるまで、マスター
は、活動処理装置であり続ける。マスターの指令ブロッ
クの最小サイズと、スレーブに与えられる指令ブロック
のサイズに調整を加えて、処理効率を高めることができ
る。さらに、割り当てられた処理装置における処理がす
んだ後、処理されたデータに確実に再順序づけが行なえ
るようにするため、マスターは、特定の指令が割り当て
られたスレーブ処理装置を識別する値をＲＡＭ　　ＦＩ
ＦＯに書き込むことができる。ＲＡＭ　　ＦＩＦＯへの
書込み順によって、マスターは、マスターの入力バッフ
ァにおいて指令を受信した元の順序と同じ再現順序を維
持することが可能になる。

【０００４】しかし、こうした技法には、処理装置の全
てが同じとは限らないし、同じプログラミングを施すわ
けにもいかないので、システムのコストが　　複雑性が
増すという欠点がある。さらに、１つ以上のスレーブ処
理装置が複雑なデータ処理指令にかかりっきりになって
いる場合、並列処理の利点が、すぐに失われる可能性が
ある。

【０００５】順次入力データを複数の並列処理装置に割
り当てる先行技術によるもう１つの技法については、例
えば、１９８７年７月の「Ｐｒｏｃｅｅｄｉｎｇｓ　ｏ
ｆ　ＳＩＧＧＲＡＰＨ」第２１巻第４号におけるトーボ
ルグ（Ｔｏｒｂｏｒｇ）による「Ａ　Ｐａｒｅｌｌｅｌ
　Ｐｒｏｃｅｓｓｏｒ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｆ
ｏｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ａｒｉｔｈｍｅｔｉ
ｃ　Ｏｐｅｒａｔｉｏｎｓ（グラフィックス及び算術演
算用並列処理アーキテクチャ）」に記載がある。その論
文で、トーボルグ（Ｔｏｒｂｏｒｇ）は、各プロセッサ
が単一のプロセッサシステムであるかのように同じプロ
グラミングが施された、並列に動作する任意の数の同じ
プロセッサから成るグラフィックスプロセッサアーキテ
クチャについて説明している。すなわち、トーボルグ（
Ｔｏｒｂｏｒｇ）の開示によれば、８つまでの演算プロ
セッサにおける並列処理を利用して、フロントエンド幾
何学的及び算術演算を行なうことによって、対話式３次
元グラフィックスシステムの処理時間を短縮することが
できる。また、トーボルグ（Ｔｏｒｂｏｒｇ）の述べる
ところによれば、プロセッサ間においてグラフィックス
指令を十分に分散させることによって、プロセッサを効
率よく利用しなければならないし、多重並列プロセッサ
は、同じ演算を行なって、単一プロセッサと見掛け上、
同じ結果を出さなければならない。

【０００６】トーボルグ（Ｔｏｒｂｏｒｇ）によれば、
そのシステムの実施において、多くのグラフィックス指
令は、順序が自由であり、従って、その処理及び再現の
順序は、表示に影響を及ぼすことなく変更することが可
能である。ただし、トーボルグ（Ｔｏｒｂｏｒｇ）は、
順序が自由ではないグラフィック指令の場合、順次指令
の処理を行なう前に、全てのプロセッサの同期がとれる
まで、他の指令の処理を行なっているプロセッサを遅延
させることを提案している。トーボルグ（Ｔｏｒｂｏｒ
ｇ）の指摘によれば、プロセッサの出力に対するバッフ
ァリングのため、この同期が処理効率に及ぼす影響は最
小限にとどまるということである。

【０００７】トーボルグ（Ｔｏｒｂｏｒｇ）は、さらに
、データが利用可能であれば、また、適合する演算プロ
セッサのデータに対する準備が整えば、必ず、並列演算
プロセッサにパイプライン処理データを転送するように
提案している。グラフィックス指令は、入力される指令
が、全ての演算プロセッサに送信すべき大域指令である
か、指令調停機構によって決まる指令を受ける準備が最
も整った演算プロセッサに送信すべき指令であるか、グ
ラフィックス指令内において指定された特定の演算プロ
セッサに送信すべき指令であるかに従って、演算プロセ
ッサに分散される。指令調停を利用して、並列処理が可
能な場合、どの演算プロセッサが指令を受けるべきかが
決定される。調停機構、指令を受ける準備が最も整って
いるプロセッサに優先権を与えることによって処理効率
を高めるため、プロセッサ間において指令を適当に分散
させようとする。このため、トーボルグ（Ｔｏｒｂｏｒ
ｇ）の開示によれば、各プロセッサは、表示リストマネ
ージャからの指令にバッファリングを施すのに用いられ
る指令入力バッファを備えることができる。バッファは
十分に深いので、いくつかの指令を同時に収容すること
ができ、入力バッファにおけるデータ量に従って、さま
ざまな優先レベルで指令を要求することが可能である。 従って、分散の優先権は、入力バッファの状況が示すと
ころに従って、処理時間が最短の指令を実行するプロセ
ッサに対して与えられる。

【０００８】順序づけは、トーボルグ（Ｔｏｒｂｏｒｇ
）のシステムの場合、各プロセッサ毎に小規模なタグＦ
ＩＦＯを維持して、全ての演算プロセッサによって処理
される全ての順次指令と、タグＦＩＦＯを含む特定のプ
ロセッサによって処理される全ての指令の順序づけを記
録しておくことによって維持されるのが普通である。ト
ーボルグ（Ｔｏｒｂｏｒｇ）によれば、タグＦＩＦＯの
２ビット入力を利用して、指令が、タグＦＩＦＯを含む
特定の演算プロセッサによって処理されているかどうか
、及び、指令が順次指令かどうかが示される。タグＦＩ
ＦＯの出力を利用して、順序に従う全ての指令の順次処
理が確実に行なわれるようにし、処理したデータをイメ
ージ記憶装置に転送して、後続の表示を行なう順序に制
御を加える。 すなわち、タグＦＩＦＯの出力を利用して、並列グラフ
ィックス処理装置をイメージ記憶装置に継続するバスに
関する調停が制御される。例えば、タグＦＩＦＯの２つ
の制御ビットが、指令が順次的でないことを表わしてい
る場合、完全な指令ブロックが利用可能になるとすぐに
、出力コントローラがバスの要求を行なう。この場合、
指令がイメージ記憶装置に転送される順序は、全てのプ
ロセッサのプロセッサロード及び指令分散によって決ま
る。単一のグラフィックス入力指令に関連した各指令グ
ループが、バスを介してイメージ記憶装置に転送される
毎に、タグＦＩＦＯ出力の刻時が行なわれる。

【０００９】タグＦＩＦＯが順次指令であることを示す
と、出力コントローラは、他の全ての演算プロセッサの
出力コントローラが、同期を目的として、元の指令スト
リームの同じポイントに達するまで、待機する。すなわ
ち、出力コントローラは、全ての演算プロセッサが、特
定の順次指令に対応するタグＦＩＦＯの項目に達して、
演算プロセッサの同期がとれるまで待機し、それから、
順次指令が出力されて、処理を受けるようにする。トー
ボルグ（Ｔｏｒｂｏｒｇ）のシステムにおける全てのプ
ロセッサが、全ての順次指令に関してそのタグＦＩＦＯ
に項目を入力するので（その指令がそのプロセッサで処
理されない場合でも）、全てのプロセッサのタグＦＩＦ
Ｏは、順次指令を表わすが、１つだけ、その指令がその
プロセッサによって処理されたことを表わすことになる
。順次指令の処理を行なったプロセッサは、次に、バス
を要求し、グラフィックス入力指令に関連した指令のグ
ループをイメージ記憶装置に送る。この指令の転送が完
了すると、全ての演算プロセッサのタグＦＩＦＯ出力が
刻時される。上述のように、トーボルグ（Ｔｏｒｂｏｒ
ｇ）の指摘によれば、このシステムの場合、プロセッサ
コアは、出力コントローラが、順次性を維持するために
、全てのプロセッサの同期をとっている間中、プロセッ
サの出力ＦＩＦＯに指令を転送し続けることができるの
で、処理効率が維持される。　　従って、トーボルグ（
Ｔｏｒｂｏｒｇ）のシステムには、複数の並列プロセッ
サに順次指令を割り当て、出力バス調停に関してタグＦ
ＩＦＯに記憶された値を利用して、処理された出力を元
の配列に組み換えるメカニズムが設けられている。ただ
し、タグ値は、各プロセッサ毎に別個に維持しなければ
ならないし、順次性は、順次命令の受信時に、全プロセ
ッサの出力を同期させて維持しなければならない。結果
として、特に、いくつかの大域（順次）命令を順次受信
する場合、処理効率は極めて低くなる可能性がある。さ
らに、指令ストリームを再配列して、並列処理能力を最
大限に利用できるようにするのは不可能である。従って
、入力バッファのサイズに比較して実行時間が長くなる
可能性のあるＢスプラインパッチのような複雑な入力グ
ラフィックスプリミティブを受信する場合、処理の効率
がさらに低下する可能性がある。

【００１０】

【発明が解決しようとする課題】従って、直列命令スト
リームをなすデータ指令を同じ並列処理装置に分散して
、処理を実施させ、それによって、処理データの組み換
えを行ない、各順次指令毎に、処理効率を損うことにな
る。全プロセッサの同期をとらなくても、順次性を維持
できるようにすることが可能な指令分散装置が、長年に
わたって必要と考えられてきた。さらに、複雑な指令を
分割して、複数の並列プロセッサに分散し、出力データ
ストリームの順次性を破壊することなく、処理が行なえ
るようにすることが可能な指令分散装置が、長年にわた
って必要と考えられてきた。本発明は、こうした目的に
合わせて設計されたものである。

【００１１】

【課題を解決するための手段】上述の長年にわたって感
じられてきた要求が、高速バス調停ハードウェアを利用
して、真の「先着順サービス」に基づき、直列命令スト
リームをなすデータを複数の並列処理装置に分散するハ
ードウェア分散装置に関連した本発明によって満たされ
た。先行技術におけるように、指令にパージングを施し
ロード平衡演算を行なうのに、複合プロセッサを必要と
はしない。さらに、本発明によって、処理後、全指令ス
トリームを適正な順序に組み換えることが可能になり、
また、かなりの処理を必要とする単一の指令を全てのプ
ロセッサで並列に実行し、その結果の各部分が異なるプ
ロセッサから得られ、再順序づけ時にその順序が破壊さ
れないようにすることも可能になる。さらに、同期が不
要のため、全てのプロセッサの準備が整うまで待つ代り
に、第１のプロセッサがそれ以上の仕事に対して準備が
整っていれば、大域指令を送ることができる。本発明の
システムは、従って、処理効率の大幅な改善を可能にす
る。

【００１２】本発明によれば、直列ストリームをなすデ
ータ処理指令及び関連するデータを１つ以上の並列処理
装置に分散して、処理が加えられるようにするための装
置が得られる。処理されたデータは、その後、組み換え
て、直列処理データストリームにすることもできる。本
発明によるデータ分散装置は、直列命令ストリームをな
すデータ処理指令及び関連データを提供する手段、及び
、処理装置のどれかが入力を受けて、処理することが可
能か否かを表わす手段を備えている。また、直列命令ス
トリームをなすデータ処理指令及び関連データの各指令
毎に、提供手段によって提供されるそれぞれの指令毎に
処理を行なう処理装置として、データ処理装置の選択を
行なう手段が設けられているが、この場合、選択処理装
置は、入力データを受けて、処理を行なうことができる
ものとして、表示手段によって示される処理装置である
。さらに、提供手段からの各指令が、それぞれ、処理に
合わせて割り当てられる、処理装置を表わした処理装置
識別値を記録する手段が設けられている。記録手段に記
憶されているそれぞれの処理装置識別値によって指定さ
れる順序で各データ処理装置の出力を順次読み取ること
によって、データ処理装置からの処理データを組み合わ
せて、直列処理データストリームにする手段を設けるこ
とも可能である。

【００１３】本発明による分散装置は、グラフィックス
指令及びグラフィックスプリミティブからなる指令／デ
ータパケットを複数のグラフィックス処理装置に分散し
、対話式３次元グラフィックス用途に関する処理効率の
改善を可能にするために用いるのが望ましい。ただし、
当該技術の熟練者には明らかなように、本発明による分
散技法は、並列処理技法が用いられる他の多くの処理環
境に適用することが可能である。

【００１４】望ましい実施例の場合、各プロセッサは、
「グリーディ（ｇｒｅｅｄｙ）」アルゴリズムを組み込
んでおり、これによって、入力は、真の「先着順サービ
ス（ｆｉｒｓｔｃｏｍｅ，　ｆｉｒｓｔ　ｓｅｒｖｉｃ
ｅｄ）」に基づいて要求されることになる。こうしたア
ルゴリズムは、各処理装置毎に入力ＦＩＦＯを設け、関
連処理装置によって処理される指令／データパケットを
待ち合わせて、処理装置が、その入力ＦＩＦＯから指令
／データパケットを読み取ろうとするが、入力ＦＩＦＯ
が、ほぼ空の場合、プロセッサ「準備完了」信号を発生
させることによって実現する。 一方、処理装置が、その処理がほぼ完了し、その入力Ｆ
ＩＦＯがほぼ空であることを表示すると、本発明に従っ
てプロセッサ「準備完了」信号が発生するようにするこ
ともできる。

【００１５】本発明のもう１つの望ましい実施例によれ
ば、選択手段が、ソースＦＩＦＯにおける次の指令／デ
ータパケットのタイプ、次の指令を処理することになる
プロセッサの数を決め、また、表示手段が、ある処理装
置が入力データを設けて、処理を施すことができること
を示しているか否かを判定し、次に、少なくとも、表示
手段が、データを受けて、処理を施すことが可能である
と表示した処理装置の入力ラインを使用可能にする。さ
らに、表示手段が、２つ以上の処理装置が、入力として
データを受けることができると表示した場合には、選択
手段は、調停によって処理装置の１つを選択することが
できる。選択手段は、また、各指令／データパケットが
割り当てられる処理装置のための記録手段に処理装置識
別値を書き込む機能を備えるのが望ましい。

【００１６】本発明の望ましい実施例による記録手段は
、処理装置識別値が順次記憶される一次シーケンスＦＩ
ＦＯと、処理装置識別値が、２つ以上の処理装置によっ
て処理される指令の場合に順次記憶される代替シーケン
スＦＩＦＯから構成されるのが望ましい。動作時、選択
手段は、２つ以上の処理装置によって処理されることに
なる指令の場合、２つ以上の処理装置によって処理され
る指令の処理を実施する各処理装置に、代替シーケンス
ＦＩＦＯに処理装置識別値を書き込まなければならない
旨の指示を行なう代替フラグを一次シーケンスに対して
書き込むのが望ましい。次に、２つ以上の処理装置によ
って処理されることになる指令の処理が全て完了すると
、この時点で、一次シーケンスＦＩＦＯに処理単位識別
値を書き込まなければならない旨の指示を行なうスイッ
チフラグが、代替シーケンスＦＩＦＯに書き込まれる。 この記憶技法の結果として、組合せ手段は、一次シーケ
ンスＦＩＦＯから代替フラグを読み取るまで、処理装置
識別値を順次読み取り、読み取った処理装置識別値に対
応する処理装置の出力から処理データの読取りを行ない
、代替フラグを読み取った時点で、スイッチフラグを読
み取るまで、代替シーケンスＦＩＦＯから処理装置識別
値を順次読み取り、読み取った処理装置識別値に対応す
る処理装置の出力から処理データを読み取ることによっ
て、元のデータシーケンスを簡単に回復することができ
る。この結果、並列プロセッサを繰返し同期させなくて
も、元の指令順序づけの保持が可能になり、単一の命令
を複数の並列プロセッサによって、並列に処理すること
が可能になる。

【００１７】本発明は、また、直列ストリームをなすデ
ータ処理指令及び関連データを１つ以上の並列データ処
理装置に分散して、処理が施されるようにする方法によ
っても構成される。本発明によるこの方法は、一般に：
直列ストリームをなすデータ処理指令及び関連データを
提供するステップと；一つ以上の処理装置のどれかが、
入力データを受けて、処理を行なうことができるか否か
を表示するステップと；直列ストリームをなすデータ処
理指令及び関連データにおける各指令毎に、それぞれの
指令を処理する処理装置として、入力データを受けて、
処理を行なうことが可能な処理装置を選択するステップ
と；各指令をそれぞれ処理する処理装置を表わす処理装
置識別値を記録するステップから構成される。

【００１８】本発明による方法には、引続き、それぞれ
の記録された処理装置識別値で指定の各処理装置の出力
を順次読み取ることによって、処理データを組み換えて
、直列処理データストリームにするステップを含むこと
も可能である。

【００１９】本発明による方法は、とりわけ、記録ステ
ップが、処理装置識別値を一次シーケンスＦＩＦＯに順
次記憶するステップと、入力指令が、２つ以上の処理装
置によって処理を施されるものである場合には、処理装
置識別値を代替シーケンスＦＩＦＯに順次記憶するステ
ップから成る点を特徴とする。本発明の望ましい方法に
よる記録ステップには、２つ以上の処理装置によって処
理を施されることになる指令の場合には、２つ以上の処
理装置によって処理される指令の処理を行なう各処理装
置毎に、代替シーケンスＦＩＦＯに処理装置識別値を書
き込まなければならない旨の指示を行なう代替フラグを
一次シーケンスに対して書き込むステップと、２つ以上
の処理装置によって処理されることになる指令の処理が
全て完了すると、この時点で、一次シーケンスＦＩＦＯ
に処理単位識別値を書き込まなければならない旨の指示
を行なうスイッチフラグを代替シーケンスＦＩＦＯに書
き込むステップも含まれている。この処理シーケンス記
録技法の結果として、元のデータシーケンスは、一次シ
ーケンスＦＩＦＯから代替フラグを読み取るまで、処理
装置識別値を一次シーケンスＦＩＦＯから順次読み取り
、読み取った処理装置識別値に対応する処理装置の出力
から処理データの読取りを行ない、代替フラグを読み取
ると、スイッチフラグを読み取るまで、代替シーケンス
ＦＩＦＯから処理装置識別値を順次読み取り、読み取っ
た処理装置識別値に対応する処理装置の出力から処理デ
ータを読み取ることによって再編成することができる。

【００２０】従って、本発明は、順次指令に関して並列
プロセッサの繰返し同期を必要とせずに、パイプライン
処理を施したグラフィックス指令／データパケットとい
った順次データストリームを複数の並列プロセッサに対
して分散できるように構成することが望ましい。さらに
、本発明は、全ての入力指令／データパケットを配列す
るシーケンスを維持しなければならないという基本的仮
定に基づいて機能するので、処理機能の融通性を高め、
処理速度を増すことが可能になる。

【００２１】

【実施例】本書に開示し、請求した内容の発明者は、直
列命令ストリームをなすデータを並列プロセッサに分散
するハードウェア分散装置、及び、前記分散装置によっ
て、データ処理の効率が高められるようにする方法を開
発することによって、当該技術において長年にわたって
いだかれてきた要求を満たした。本発明によれば、高速
バス調停ハードウェアを用いて、真の「先着順サービス
」または「グリーディ」アルゴリズムを利用する処理装
置に直列データストリームを分配することによって、指
令にパージングを施し、ロード平衡アルゴリズムを実現
するのに、複合プロセッサが必要でなくなるようにする
。本発明は、また、かなりの処理を必要とする単一の指
令が、複数のプロセッサによって並列に実行され、結果
の各部分が異なるプロセッサから得られる場合でも、処
理後に、全体指令ストリームを適正な順序に組み換える
ことを可能にする。

【００２２】本発明の現在のところ望ましい実施例によ
るこうした、及び、その他の有効な特徴を備えた装置に
ついては、図１〜図５に関連して述べることにする。ま
ず、図１に関連して、本発明の一般的な説明を行なうこ
とにする。本発明の本書における説明は、ホスト処理シ
ステム及びホストシステムのグラフィックスサブシステ
ムに関して行なわれ、直列データストリームは、パイプ
ライン処理を施されたグラフィックス指令及びプリミテ
ィブから構成されるが、当該技術の通常の技能者には明
らかなように、本発明の原理は、他のさまざまな処理環
境にも適用することが可能である。さらに、当該技術の
熟練者には明らかなように、本書で示される説明は、単
に解説を目的としたものであって、本発明の範囲を限定
しようとする意図は全くない。本発明の範囲に関する疑
問は、付属のクレームを参照することによって、解決す
ることができる。

【００２３】図１には、本発明に従って、並列処理シス
テムとインターフェイスされたホスト処理システムが示
されている。すなわち、ホストプロセッサ１０は、例え
ば、グラフィックス指令及びプリミティブを含む複数の
指令／データパケットから成る直列データストリームを
発生して、これらの指令／データパケットをホストシス
テムＩ／Ｏバス１２を介してホストインターフェイス１
４に出力し、その後で、指令／データパケットを入力プ
ロセッサ１６に送る。可能性のあるホストインターフェ
イス装置については、本発明の譲受人に譲渡され、従っ
て、本書にも参考までに組み込まれている、１９９０年
３月１２日に提出された米国出願第４９２，５１６号及
び１９９０年３月１５日に提出された米国出願４９４，
００８号に説明されている。入力プロセッサ１６は、例
えば、入力される直列データストリームにパージングを
施し、指令／データパケットに適合するタグをセットし
て、指令／データパケットを適正に分散できるようにす
るゲートアレイとすることが可能である。入力プロセッ
サ１６は、グラフィックスプリミティブに関するいくつ
かの再現状態変数を記録しておくことも可能である。次
に、処理される指令／データパケットが、ソースＦＩＦ
Ｏ１８に対する待ち行列を形成する。詳細に後述するよ
うに、指令／データパケットが、ソース待ち行列から読
み取られ、Ｘバス、さらに、Ｓ／Ｐ指令分散装置２０に
送られて、適合するプロセッサに分散され、処理を受け
ることになる。

【００２４】Ｘバスは、ソースＦＩＦＯ１８をＳ／Ｐ指
令分散装置２０に、さらに、設計者の所望の数とするこ
とができる処理装置２４のそれぞれと連係した待ち行列
入力ＦＩＦＯ２２に接続する。Ｓ／Ｐ指令分散装置２０
は、本発明に従って、ソースＦＩＦＯ１８から入力ＦＩ
ＦＯ２２の１つまたは全てに対しデータをいつ転送する
かについての制御を行なう。各入力ＦＩＦＯ２２は、そ
の連係するプロセッサ２４が、それ以外の入力データに
対する準備が整うまで処理しなければならない指令及び
データを保持する。 各プロセッサ２４によって処理されるデータは、次に、
その連係する出力ＦＩＦＯ２６に出力され、本発明に基
づくデータの再順序づけが可能になるまで記憶される。

【００２５】本発明によるシステムにおける各プロセッ
サ２４は、Ｓ／Ｐ指令分散装置には分る固有の識別番号
を備えている。従って、処理能力を生じさせる指令／デ
ータパケットが、処理装置２４の１つに送られると、そ
の処理装置の識別番号が、本発明に従って一次シーケン
スＦＩＦＯ２８に書き込まれ、入力指令／データパケッ
トの順序づけを維持することが可能になる。上述のよう
に、本発明は、全ての順序づけを維持しなければならな
いという仮定に基づいて機能するものであり、従って、
出力を生じさせる各命令毎に、識別番号を一次シーケン
スＦＩＦＯ２８に書き込むことが重要である。一次シー
ケンスＦＩＦＯ２８の出力は、従って、各指令／データ
パケットが、それぞれどこに送られて、処理を受けたか
を識別する、処理装置識別番号のリストである。従って
、処理装置２４による操作が施された後、一次シーケン
スＦＩＦＯ２８の出力を利用して、直列ストリームをな
す指令を再構成することが可能である。

【００２６】本発明には、一次シーケンスＦＩＦＯ２８
と同様の代替シーケンスＦＩＦＯ３０も含まれている。 述べたばかりのように、プロセッサ２４に指令／データ
パケットがロードされる順序は、一次シーケンスＦＩＦ
Ｏ２８から利用可能であるが；全てのプロセッサ２４が
、同じ指令の異なる部分に対して働くように求められる
場合のように、この順序を乱さなければならない場合も
ある。こうした状況を取り扱う代替シーケンスＦＩＦＯ
３０が、本発明に従って設けられた。すなわち、こうし
た指令を受信すると、Ｓ／Ｐ指令分散装置２０は、一次
シーケンスＦＩＦＯ２８に特殊なフラグ（今後は「代替
」フラグと呼ぶ）をセットし、下流のハードウェアに対
し、順序づけした配列を中断しなければならない旨の警
告を行なう。これによって、下流のハードウェアは、代
替シーケンスＦＩＦＯ３０から新しい配列の読取りを開
始する。さらに詳細に後述するように、代替シーケンス
ＦＩＦＯ３０には、受信した指令に関する全体結果の異
なる部分の配列が含まれることになり、最後のプロセッ
サ２４が、受信した指令の最後の部分を仕上げると、代
替シーケンスＦＩＦＯ３０に指令またはフラグ（今後は
「スイッチ」フラグと呼ぶことにする）を挿入し、下流
のハードウェアに対して一次シーケンスＦＩＦＯ２８の
順序づけに戻るように警告する。指令の処理は、データ
に対する共用アクセスのためのＳバスを介して共用メモ
リ３２と通信し、処理することによって、プロセッサ間
で分担するのが普通である。

【００２７】最後に、さらに詳細に後述するように、連
結装置３４が、一次シーケンスＦＩＦＯ２８及び代替シ
ーケンスＦＩＦＯ３０に記憶された処理装置識別値を利
用して、出力ＦＩＦＯ２６に記憶された処理データを直
列データストリームに組み換え、それ以上の処理に備え
る。

【００２８】本発明によるシステムは、少なくとも４つ
の異なるタイプの入力指令を取り扱うように設計されて
いる。グラフィックスシステムに関して、これらの指令
は、例えば、ワールドと装置の両方の座標の多角形、ポ
リライン、及び、メッシュを含むプリミティブ指令；ハ
ードウェア構成によるプリミティブ指令；大域指令；及
び、ハードウェア構成による大域指令と呼ばれるものと
する。

【００２９】これらの指令は、全ての処理装置２４によ
って処理される大域指令と、必要に応じて、単一のプロ
セッサによって処理するか、または、いくつかのプロセ
ッサによる処理に備えて分割することが可能な指令のい
ずれであるかに基づき、Ｓ／Ｐ指令分散装置２０によっ
て特定の処理装置２４に割り当てられて、処理される。 こうした分割可能な指令は、一般に、Ｂスプライン指令
のような複合プリミティブであるが、長時間の処理を必
要とする（及び分割することができる）指令は、どれで
も、本発明に従って分割し、処理することが可能である
。

【００３０】大域指令の場合、常に、全プロセッサ２４
によって実行しなければならないので、こうした指令は
、従来、順序づけの目的にとって最も困難を生じた。こ
れらの指令の順次（時間ではなく）実行順序は、維持し
なければならない。一方、ハードウェア構成による指令
命令は、プロセッサ２４外部のハードウェア構成を変更
する指令である。この外部ハードウェアには、フレーム
バッファ制御レジスタ、ブロック移動装置、走査変換器
レジスタ等を含むことができる。例えば、ハードウェア
構成による大域指令の場合、指令のハードウェア構成部
分は、１回実行しさえすればすんでしまうので、特に注
意しなければならない。従って、こうした指令の場合、
ハードウェア構成部分は、単一プロセッサ２４で１回し
か実行されないことをフラグで示すのが望ましい。

【００３１】もちろん、当該技術の熟練者であれば、本
発明に従って他の指令を利用することもできる。ただし
、通常、該指令は、単一プロセッサで処理する指令及び
全てのプロセッサで処理する指令のカテゴリーに入るの
が望ましい。さらに、当該技術の熟練者には明らかなよ
うに、本発明のハードウェアは、簡単に修正を加えて、
他の同様の指令に適応させることができる。

【００３２】次に、図１の回路の一般的動作について説
明する。まず、入力プロセッサ１６が、直列入力ストリ
ームにおける各指令／データパケットを読み取り、それ
が、プロセッサの１つで実行できる操作か、全てのプロ
セッサに送らなければならないか判定を行なう。全ての
グラフィックスプロセッサに送らなければならない操作
は、指令／データパケットの最初のワードにおけるビッ
トの１つをセットして、大域のフラグ表示を行なう。入
力プロセッサ１６は、また、チェックして、詳細に後述
するように、パケットが、代替シーケンスＦＩＦＯ３０
の利用を必要とする分割可能な指令タイプであるか否か
を確かめる。もしそうなら、もう１つのビットが、指令
／データパケットの第１のワードにおいてセットされる
。入力プロセッサ１６は、また、指令／データパケット
の最後のワードにおけるビットをセットし、Ｓ／Ｐ指令
分散装置２０は、指令／データパケットの終端を検出で
きるようにすることが可能である。指令／データパケッ
トは、次に、ソースＦＩＦＯ１８に記憶される。

【００３３】プロセッサ２４の１つが、さらに仕事をす
る必要がある場合、そのプロセッサは、その入力ＦＩＦ
Ｏ２２を読み取ろうとする。その入力ＦＩＦＯ２２が空
の場合には、プロセッサ２４はさらに多くのデータを要
求する。 ２つ以上のプロセッサがさらに多くのデータを要求する
場合、Ｓ／Ｐ指令分散装置２０が、要求する処理装置２
４間で調停を行ない、ソースＦＩＦＯ１８から勝ちとっ
たプロセッサの入力ＦＩＦＯ２２に次の指令／データパ
ケットを自動的に転送する。指令／データパケットが大
域としてフラグ表示された場合、第１のプロセッサ２４
がさらにデータを要求すると、パケットは入力ＦＩＦＯ
２２の全てに書き込まれる。

【００３４】勝利を得た処理装置２４に対する指令／デ
ータパケットの転送時、Ｓ／Ｐ指令分散装置２０は、一
次シーケンスＦＩＦＯ２８にワードも書き込む。このワ
ードは、指令／データパケットを送りつけた処理装置の
番号を表わすか、あるいは、下流のハードウェアが代替
シーケンスＦＩＦＯ３０の出力の利用を開始すべきであ
ることを表わす。ただし、注目すべきは、大域指令のタ
イプによっては、処理装置２４からの出力をパイプライ
ンで送る必要のないものもある。従って、これらの指令
は、Ｓ／Ｐ指令分散装置２０が、識別番号を一次シーケ
ンスＦＩＦＯ２８に書き込むことを必要としない。少な
くとも１つのプロセッサ２４によって出力を発生させる
指令だけしか、一次シーケンスＦＩＦＯ２８に記録する
必要はない。

【００３５】一方、上述のＢスプラインパッチ指令のよ
うな分割可能な複合指令を受信する場合、各処理装置２
４が利用可能になるので、こうした指令は、本発明に従
って分割し、複数の処理装置２４によって処理できるよ
うにする。代替シーケンスＦＩＦＯ３０は、従って、処
理装置によって指令の異なる部分に処理を施す際に対応
させる処理装置識別番号を記録することになる。

【００３６】本発明によれば、Ｓ／Ｐ指令分散装置２０
は、また、処理装置２４にそれ以上の仕事に対する「早
期要求」をさせる機能も備えている。ソフトウェアの制
御下で、各プロセッサは、Ｓ／Ｐ指令分散装置に対して
、処理装置２４が、すぐにその入力ＦＩＦＯ２２からそ
れ以上の仕事を読み取ろうとする旨の警告を行なうビッ
トをセットすることができる。プロセッサ２４の入力Ｆ
ＩＦＯが空の場合、Ｓ／Ｐ指令分散装置２０は、ソース
ＦＩＦＯ１８からそれ以上の仕事に対する「早期要求」
を行なうプロセッサ２４に次の指令／データパケットを
転送することを知っている。本発明のこの態様について
は、図３に関連してさらに詳細に後述する。

【００３７】要するに、任意の数にすることが可能な並
列アレイをなす処理装置２４に指令及びデータを転送す
る場合、本発明によるＳ／Ｐ指令分散装置２０が利用さ
れる。ほとんどの指令は、１度に１つの処理装置に対し
てしか送られないようになっており、この場合、特定の
処理装置２４は、各処理装置２４の使用可能度によって
決定されるが、大域指令の処理は、順次性を損うことな
く実施することができる。Ｓ／Ｐ指令分散装置２０には
、また、指令のタイプ（すなわち、プリミティブ、大域
、あるいは、Ｂスプラインまたは他の分割可能な複合指
令）と、指令の終端にいつ達したかを判定するためのデ
コーダを含むのが望ましい。この知識に基づき、Ｓ／Ｐ
指令分散装置２０は、処理装置２４の１つと全てのいず
れに指令を送るべきかを判定し、さらに、いつ停止すべ
きかを知ることができる。また、Ｓ／Ｐ指令分散装置２
０が、１つの処理装置２４にだけしか指令を送らない場
合、処理装置２４の全てについて要求ラインを検知し、
新しい指令に対する準備の整った処理装置２４に指令を
送る。２つ以上の処理装置２４が利用可能な場合、Ｓ／
Ｐ指令分散装置２０は、調停に勝った処理装置２４（例
えば、要求している識別番号の最も小さい処理装置２４
）に指令を送ることによって、決着をつける。ただし、
指令が、処理装置２４に転送される前に、処理装置２４
の識別番号が、一次シーケンスＦＩＦＯ２８に書き込ま
れる。同様に、指令が、大域またはＢスプラインの場合
、指令が大域でないように、識別番号が書き込まれる。 従って、処理装置２４が出力を発生すべきか否かの判定
を行なうため、Ｓ／Ｐ指令分散装置２０は、その識別番
号が記憶されており、出力のための制御処理装置２４と
なるものを除く全ての処理装置２４について、送られる
大域ビットを取り除くことができる。もちろん、当該技
術の通常の技能者には明らかなように、他の案も可能で
ある。

【００３８】図２には、Ｓ／Ｐ指令分散装置２０が行な
う必要のある内容の流れ図が示されている。ステップ２
００でリセットされると、Ｓ／Ｐ指令分散装置２０が、
ステップ２０２で、ソースＦＩＦＯ１８を調べて、ソー
ス１８が処理すべき指令／データパケットを有している
かどうかを確認することによって、チェックを行ない、
なすべき仕事の有無を判断する。もしあれば、指令／デ
ータパケットの指令ビットをチェックして、指令が大域
指令か否かを確かめる（ステップ２０４）。指令が大域
指令でなければ、処理装置２４が指令を要求するまで、
Ｓ／Ｐ指令分散装置２０は待機する（ステップ２０６）
。要求を受信すると、Ｓ／Ｐ指令分散装置２０は、ステ
ップ２０８において、決着をつけ（必要な場合）、「準
備完了」の処理装置を選択する。Ｓ／Ｐ指令分散装置２
０は、次に、ステップ２１０においてチェックをし、一
次シーケンスＦＩＦＯ２８が、自由にデータ入力を受信
できるか否かを確かめて、受信できる場合には、Ｓ／Ｐ
指令分散装置２０が、勝利をおさめた処理装置２４の番
号を一次シーケンスＦＩＦＯ２８に書き込むことになる
。（一般に、一次シーケンスＦＩＦＯ２８は、常に、デ
ータを受信する準備が整っており、従って、ステップ２
１０は省略することができる。）処理装置識別番号が一
次シーケンスＦＩＦＯ２８に書き込まれると、Ｓ／Ｐ指
令分散装置２０が、ステップ２１２においてチェックを
行ない、指令ワードに「代替」フラグがセットされてい
るか否かを確める。上述のように、その指令の処理が複
数の処理装置によって並列を行なえる場合には、指令ワ
ードに「代替」フラグがセットされる。指令ワードに「
代替」フラグがセットされている場合、Ｓ／Ｐ指令分散
装置２０がステップ２１４において、一次シーケンスＦ
ＩＦＯ２８に「代替」フラグを書き込む。一方、「代替
」フラグが指令ワードにセットされていなければ、前述
のように、勝利をおさめた処理装置２４の処理装置識別
値だけが、一次シーケンスＦＩＦＯ２８に書き込まれる
。次に、ステップ２１８において、Ｓ／Ｐ指令分散装置
２０は、勝利をおさめた処理装置２４の入力ＦＩＦＯ２
２に対する入力ラインを使用可能にし、ソースＦＩＦＯ
１８の指令を選択された処理装置２４に転送できるよう
にする。

【００３９】一方、ステップ２０４において、ソース１
８からの指令が大域指令であると判定されると（Ｂスプ
ライン指令は、大域指令として扱うことができる点に留
意のこと）、Ｓ／Ｐ指令分散装置２０は、ステップ２２
０においてチェックし、「代替」フラグが指令ワードに
おいてセットされているか否かを確認する。「代替」フ
ラグが指令ワードにおいてセットされていなければ、ス
テップ２２２において、全ての入力ＦＩＦＯ２２に対す
る入力ラインが使用可能になり、ソースＦＩＦＯ１８か
らの指令が、全ての処理装置２４に対し同報通信可能に
なる。一方、「代替」フラグが、指令ワードにセットさ
れている場合、Ｓ／Ｐ指令分散装置２０は、ステップ２
２４において、まず、一次シーケンスＦＩＦＯ２８の準
備が整っているか否かのチェックを行ない、整っていれ
ば、ステップ２２６において、こうした指令を受信済み
であることを表わした「代替」フラグを一次シーケンス
ＦＩＦＯ２８に書き込む。

【００４０】次に、ステップ２２８において、ソースＦ
ＩＦＯ１８がデータ転送の準備が整っているか否か、ス
テップ２３０において、使用可能になった全てのプロセ
ッサがデータ入力の準備が整っているか否かのチェック
を行なって、データ転送を開始する。全ての要素の準備
が整っている場合、ステップ２３２において、データ転
送が開始し、ステップ２３４で判定される指令の最後の
ワードが転送されるまで、ソースＦＩＦＯ１８における
次のデータワードが使用可能になった処理装置の入力Ｆ
ＩＦＯ２２に書き込まれる。このプロセスが、ソースＦ
ＩＦＯ１８における各ワード毎に繰り返され、ソースＦ
ＩＦＯ１８が空になるか、あるいは、宛先入力ＦＩＦＯ
２２が満杯になると、データ転送を一時的に中断するこ
とが可能である。Ｓ／Ｐ指令分散装置２０は、こうした
条件を検知して、必要な措置を講じる。例えば、データ
転送が完了すると、Ｓ／Ｐ指令分散装置２０はループを
戻り、新しい指令についてチェックを行なう。

【００４１】図３には、各処理装置が、ステップ２０６
においてＳ／Ｐ指令分散装置によって検出されるように
（図２）、それ以上の入力データに対する準備が整った
ことを表示できるようにする回路が示されている。すな
わち、処理装置２４のソフトウェアは、処理がすぐに完
了するものと判定すると、それに応じて、任意データレ
ジスタ３６にＳＥＴビットをセットする。このビットが
セットされ、入力ＦＩＦＯ２２が空になると、この処理
装置がそれ以上のデータに対して準備が整ったことを表
わす「処理装置準備完了」信号がＳ／Ｐ指令分配装置２
０に送られる。処理装置２４が選択されると、次に、Ｓ
／Ｐ指令分散装置２０は、任意データレジスタをクリア
することができる。一方、処理装置は、読取り要求をそ
の入力ＦＩＦＯ２２に対して発生しさえすればよいよう
になっており、入力ＦＩＦＯ２２が空の時に、こうした
読取り要求を受信すると、やはり、「処理装置準備完了
」信号を発生して、処理装置がそれ以上のデータに対し
て準備が整ったことを表わすことができる。次に、上述
のように、Ｓ／Ｐ指令分散装置２０は、次の入力指令／
データパケットが、要求する処理装置２４に対して出力
すべきか否かの決定を行なうのに必要な調停を行なうこ
とができる。

【００４２】図４には、入力ＦＩＦＯ２２に記憶された
指令／データパケットの処理時に、各処理装置２４が従
うことになるプロセスの一部に関する流れ図が示されて
いる。一般に、各処理装置２４は、受信指令が大域指令
であろうと、プリミティブ指令であろうとかまわない。 そうではなく、各処理装置２４は、主として、受信した
指令に対する処理の全てを実施すべきか、あるいは、そ
の処理を他の処理装置と分担すべきかを問題にする。上
述のように、それが、Ｂスプラインのような命令を受信
する場合には、指令ワードに「代替」フラグがセットさ
れ、その命令が、複数の処理装置で処理できる命令であ
ることが表示されている。従って、処理装置はチェック
して、どんな処理を行うべきか確める必要がある。

【００４３】従って、入力ＦＩＦＯ２２から指令／デー
タパケットを読み取った後、各処理装置２４は、まず、
指令ワードをチェックして、「代替」フラグがセットさ
れているか否かを判定する（ステップ４０２）。「代替
」フラグがセットされていなければ、指令は、ステップ
４０４において、その処理装置だけで処理可能な通常の
指令である。一方、「代替」フラグが指令ワードにセッ
トされている場合、処理装置２４は、ステップ４０６に
おいてＳバスを獲得し、共用メモリ３２にアクセスして
、ステップ４０８において、次のブロックの仕事を構成
するのが何かを確める。Ｓバスは、１度に１つの処理装
置だけしかアクセスできないセマフォー式バスが望まし
い。従って、指令の処理が完了すると（ステップ４１０
）、ステップ４１２において、Ｓバスは解放され、プロ
セスが終了する。一方、共用メモリ３２にまだ処理をす
る指令が残っている場合、Ｓバスセマフォーによって、
処理装置が、ステップ４１４で代替シーケンスＦＩＦＯ
３０に処理装置識別番号を書き込み、それがそのデータ
に対するプロセスを実施中であることを表示する（例え
ば、Ｂスプライン機能に関した出力ディスプレイにおけ
るデータに対するいくつかのライン処理）。処理装置２
４は、次に、ステップ４１６で、共用メモリ３２におい
て、次のブロックの仕事について述べていることを表示
し、処理に備えて次のブロックのデータを読み取る。こ
れが、指令の処理時における最後のブロックの仕事であ
る場合、処理装置２４は、ステップ４１８において、順
序づけ制御が一次シーケンスＦＩＦＯ２８に戻らなけれ
ばならないと判定し、その結果、ステップ４２０におい
て、「スイッチ」フラグを代替シーケンスＦＩＦＯ３０
に書き込む。さもなければ、プロセッサ２４は、直接ス
テップ４２２に進み、Ｓバスセマフォーを解放して、ス
テップ４２４におけるデータ読取りのプロセスを実施し
、その結果は、出力ＦＩＦＯ２６に出力される。処理は
、次に、開始点にまで戻り、処理装置２４は、Ｓバスセ
マフォーを獲得し、処理する仕事が残っているか否かを
判定することができる。分担された命令処理が完了する
まで、プロセッサ間においてこの方法による処理が続行
される。次に、代替シーケンスＦＩＦＯ３０に記憶され
た値を一次シーケンスＦＩＦＯ２８に記憶された値に関
連して利用し、図５に関連して次に述べるように、デー
タ指令ワードのストリームに対する再順序づけを行なう
ことが可能になる。

【００４４】図５に示すように、連結装置３４は、一次
シーケンスＦＩＦＯ２８及び代替シーケンスＦＩＦＯ３
２の出力を利用して、出力ＦＩＦＯ２６からの出力に対
して再順序づけを施し、元の配列と同じ配列を備えた直
列データストリームにする。すなわち、ステップ５００
においてパワーアップされると、連結装置３４は、まず
、ステップ５０２において、一次シーケンスＦＩＦＯ２
８がデータ読取りの準備が整っているか否かのチェック
を行なう。一次シーケンスＦＩＦＯ２８が、記憶されて
いる処理装置識別データを読取る準備が整うと、次の処
理装置識別値が、ステップ５０４において読み取られる
。連結装置３４は、次に、読み取られる識別値として「
代替」フラグが記憶されているか否か（すなわち、次に
、代替シーケンスＦＩＦＯ３０の読取りを始めるべきか
否か）をチェックする。 「代替」フラグが記憶されていなければ、連結装置３４
は、ステップ５０８において、識別された処理装置の出
力ＦＩＦＯ２６が、その処理データを出力する準備が整
っているかチェックする。出力ＦＩＦＯ２６が、そのデ
ータを出力する準備が整っている場合、データの次のワ
ードが、ステップ５１０において、出力データシーケン
スにおける次のワードとして出力される。

【００４５】次に、連結装置３４は、ステップ５１２に
おいて、転送されたワードが最後のワードであったか否
かをチェックし、そうでなければ、特定の指令に関する
全てのデータが出力されるまで、同じ出力ＦＩＦＯ２６
が、引続き、処理されたデータを出力する。処理装置は
、次に、開始点に戻ると、一次シーケンスＦＩＦＯ２８
から次の処理装置識別番号を読み取り、処理が繰り返さ
れる。

【００４６】一方、「代替」フラグが処理装置識別値と
して一次シーケンスＦＩＦＯ２８に記憶される場合、処
理はステップ５０６からステップ５１４にスキップし、
代替シーケンスＦＩＦＯ３０をチェックして、その記憶
された値を出力する準備が整っているか否かを判定を行
なう。代替シーケンスＦＩＦＯ３０の読取り準備が整っ
ていれば、ステップ５１６において、次の処理装置識別
値が代替シーケンスＦＩＦＯから読み取られる。ステッ
プ５１８において、「スイッチ」フラグが、処理装置識
別値として記憶されていると判断されると、連結装置３
４は、一次シーケンスＦＩＦＯ２８から次の処理装置識
別値を読み取るべきであると判断する。一方、「スイッ
チ」フラグが代替シーケンスＦＩＦＯ３０が記憶されて
いなければ、ステップ５２０において、連結装置３４は
、識別された処理装置の出力ＦＩＦＯ２６がそのデータ
の出力準備が整っているか否かを判定する。識別された
処理装置２４に関する出力ＦＩＦＯ２６の出力準備が整
っていると、出力ＦＩＦＯ２６に記憶された次のワード
が、ステップ５２２において、データストリームの次の
ワードとして転送される。連結装置３４は、次に、ステ
ップ５２４において、このデータ転送が、その指令に関
する処理データの最後のワードについてのものか否かを
判定し、そうでなければ、同じ出力ＦＩＦＯ２６からデ
ータの次のワードを読み取る。処理データの最後のワー
ドが読み取られると、処理は、ステップ５１４に戻り、
ステップ５１８において、「スイッチ」フラグが見つか
ると、一次シーケンスＦＩＦＯ２８が読み取られる。こ
うして、処理データは、指令がＳ／Ｐ指令分散装置２０
によって分散された元の配列と同じ配列に再構成するこ
とが可能になる。

【００４７】当該技術の熟練者には明らかなように、本
発明の異なる特定の特徴に関して、他の技法を実施する
ことも可能である。例えば、一次シーケンスＦＩＦＯ２
８と代替シーケンスＦＩＦＯ３０のどちらの読取りを行
なうかを判定するため、連結装置３４は、一次シーケン
スＦＩＦＯ２８と代替ＦＩＦＯ３０のそれぞれに関する
状況ビットを絶えずチェックすることによって、読み取
るべきＦＩＦＯがどちらかを判定することが可能になる
。従って、状況ビットの状態は、「スイッチ」フラグま
たは「代替」指令またはフラグを利用する代りに、変更
することが可能である。さらに、出力が不要であったと
しても、大域指令を受信したことを表わす値が、一次シ
ーケンスＦＩＦＯ２８に記憶されている可能性があり、
従って、順序づけされた元の配列全体を再構成すること
ができる。 また、大域指令が、ハードウェアの更新に備えて、下流
のハードウェアに処理データを送らなければならない場
合、上述の技法に従って、ある処理装置識別値を任意に
選択し、適正なデータを下流に送ることができる。すな
わち、選択された処理装置は、出力を発生させる他の指
令の場合と同じやり方で、ハードウェア変更指令を下流
に送ることができる。

【００４８】さらに、本発明によれば、複数の処理装置
によって並列に処理できるＢスプライン指令のような指
令の場合、共用メモリ３２にフラグを利用して、次に処
理されるのがどのブロックになるかを表示することも可
能である。従って、処理装置が、Ｓバスを制御し、共用
メモリ３２にアクセスして、次に処理すべきデータブロ
ックがどれか判定する場合、フラグをチェックして、次
にどのデータブロックを処理すべきかを判定するだけで
よい。また、大域指令は、本発明により、Ｓ／Ｐ指令分
散装置２０によって、分散される場合、入力ＦＩＦＯの
１つが満杯でない限り、すぐに全ての入力ＦＩＦＯ２２
に転送することができる。こうした場合、Ｓ／Ｐ指令分
散装置２０は、入力ＦＩＦＯの全てが同期のために空に
なるまで、待機するのではなく、入力ＦＩＦＯ２２の全
てが大域指令を受けることが可能になるまで待機して、
大域指令を分散しさえすればよい。本発明に従って用い
られる全てのこうしたＦＩＦＯは、最高の性能を確保す
るのに妥当な数の大域指令にバッファリングを施すのに
十分な深さを備えているのが望ましい。さらに、各処理
装置の動作が独立しているため、追加処理装置を簡単に
追加することができるので、複雑なソフトウェアを並列
に扱うことができるようにすることによって、処理効率
をより極限にまで高めることが可能になる。

【００４９】

【発明の効果】以上のように、本発明によれば、高速バ
ス調停ハードウェアを利用して、真の「先着順サービス
」に基づき、直列命令ストリームをなすデータを複数の
並列処理装置に分散するハードウェア分散装置が提供さ
れる。本発明においては、先行技術におけるように、指
令にパージングを施しロード平衡演算を行なうのに、複
合プロセッサを必要とはしない。さらに、本発明によっ
て、処理後、全指令ストリームを適正な順序に組み換え
ることが可能になり、また、かなりの処理を必要とする
単一の指令を全てのプロセッサで並列に実行し、その結
果の各部分が異なるプロセッサから得られ、再順序づけ
時にその順序が破壊されないようにすることも可能にな
る。さらに、同期が不要のため、全てのプロセッサの準
備が整うまで待つ代りに、第１のプロセッサがそれ以上
の仕事に対して準備が整っていれば、大域指令を送るこ
とができる。本発明のシステムは、従って、処理効率の
大幅な改善を可能にする。

【００５０】本発明の典型的な実施例について詳述して
きたが、当該技術の熟練者にはすぐ分るように、本発明
の新規な教示及び利点からあまり逸脱することなく、典
型的な実施例に多くの修正を追加することが可能である
。例えば、本発明に基づいて解説の技法は、本書に記述
のグラフィックスシステムではなく、他の処理環境にお
ける大幅に異なるタイプの指令についても適用可能であ
る。本発明は、処理装置の全てが同期するのを無駄に待
たされることなく、並列処理装置に加えられるストリー
ムをなす指令の順序づけされた配列が維持されるのが望
ましい、他の処理システムに関連して用いることができ
る。従って、こうした修正は、全て、下記クレームに定
義の本発明の範囲に含まれるものとする。

【図面の簡単な説明】

【図１】本発明に基づき、直列指令ストリームデータを
並列プロセッサに分散させるためのハードウェア分散装
置のブロック図である。

【図２】本発明に基づき、直列／並列指令分散装置を動
作するためのアルゴリズムを示す流れ図である。

【図３】本発明に基づき、各プロセッサが入力データの
準備が完了したかどうかを表示するための手段のブロッ
ク図である。

【図４】処理が他のプロセッサと共有されるような複合
指令を処理する場合に各プロセッサで用いられるアルゴ
リズムを示す流れ図である。

【図５】本発明に基づき、処理済みデータを直列処理デ
ータストリームに再組み換えするための、図１に示す連
結装置の動作を示すアルゴリズムの流れ図である。

【符号の説明】

１０…ホストプロセッサ １２…ホストシステムＩ／Ｏバス １４…ホストインタフェース １６…入力プロセッサ １８…ソースＦＩＦＯ ２０…Ｓ／Ｐ指令分散装置 ２２…入力ＦＩＦＯ ２４…プロセッサ ２６…出力ＦＩＦＯ ２８…一次シーケンスＦＩＦＯ ３０…代替シーケンスＦＩＦＯ ３２…共有メモリ ３４…連結装置

Claims (1)

【特許請求の範囲】
1. 【請求項１】直列ストリームをなすデータ処理指令及び
   関連するデータを１つ以上の並列処理装置に分散して、
   処理が加えられるようにするための装置であって：前記
   直列命令ストリームをなすデータ処理指令及び関連デー
   タを提供する手段と；前記１つ以上の並列装置の内の１
   つが入力データを受けて、処理を行うことができるかど
   うかを表示するための手段と；前記直列命令ストリーム
   をなすデータ処理指令及び関連データ処理の各指令毎に
   、前記提供手段によって提供されるそれぞれの指令毎に
   処理を行なう処理装置として、データ処理装置の選択を
   行なうための手段であって、入力データを受けて、処理
   を行なうことができるものとして、前記表示手段によっ
   て示される手段と；さらに、前記提供手段からの各指令
   が、それぞれ、処理に合わせて割り当てられる、処理装
   置を表わした処理装置識別値を記録する手段と；から成
   ることを特徴とする装置。