(57)【要約】  一態様において、本発明はシステムであり、（ａ）単一のチップ上の複数の並列プロセッサと、（ｂ）チップ上に置かれていて、かつプロセッサの各々によってアクセス可能なコンピュータメモリとを備えていて、プロセッサの各々は、de minimis命令セットを処理するように動作可能であり、プロセッサの各々は、プロセッサの中の少なくとも３つの特定のレジスタの各々専用のローカルキャッシュを備えている。別の態様において、本発明はシステムであり、（ａ）単一のチップ上の複数の並列プロセッサと、（ｂ）チップ上に置かれていて、かつプロセッサの各々によってアクセス可能なコンピュータメモリとを備えていて、プロセッサの各々は、スレッドレベルの並列処理のために最適化された命令セットを処理するように動作可能である。
2009525545.tif 000002
【特許請求の範囲】
【請求項１】
単一のチップ上の複数の並列プロセッサと、
前記チップ上に置かれていて、かつ前記プロセッサの各々によってアクセス可能なコンピュータメモリとを備えたシステムにおいて、
前記プロセッサの各々は、de minimis命令セットを処理するように動作可能であり、
前記プロセッサの各々は、前記プロセッサの中の少なくとも３つの特定のレジスタの各々専用のローカルキャッシュを備えていることを特徴とするシステム。
【請求項２】
前記ローカルキャッシュの各々のサイズは、前記チップ上のランダムアクセスメモリの１行に等しいことを特徴とする請求項１に記載のシステム。
【請求項３】
関連するキャッシュを有する少なくとも３つの特定のレジスタは、命令レジスタ、ソースレジスタ、および宛先レジスタを含むことを特徴とする請求項１に記載のシステム。
【請求項４】
前記de minimis命令セットは、７つの命令から成ることを特徴とする請求項１に記載のシステム。
【請求項５】
前記プロセッサの各々は、単一のスレッドを処理するように動作可能であることを特徴とする請求項１に記載のシステム。
【請求項６】
アキュムレータは、インクリメント命令を除く、あらゆる命令のためのオペランドであることを特徴とする請求項１に記載のシステム。
【請求項７】
各命令のための宛先は、常にオペランドレジスタであることを特徴とする請求項１に記載のシステム。
【請求項８】
３つのレジスタは自動インクリメントであり、かつ３つのレジスタは自動デクリメントであることを特徴とする請求項１に記載のシステム。
【請求項９】
各命令は、完了するために１クロックサイクルのみを必要とすることを特徴とする請求項１に記載のシステム。
【請求項１０】
前記命令セットは、分岐命令およびジャンプ命令を備えていないことを特徴とする請求項１に記載のシステム。
【請求項１１】
各命令は、長さが最高でも８ビットであることを特徴とする請求項１に記載のシステム。
【請求項１２】
単一のマスタプロセッサが、前記並列プロセッサの各々を管理する役割を担っていることを特徴とする請求項１に記載のシステム。
【請求項１３】
単一のチップ上の複数の並列プロセッサと、
前記チップ上に置かれていて、かつ前記プロセッサの各々によってアクセス可能なコンピュータメモリとを備えたシステムにおいて、
前記プロセッサの各々は、スレッドレベルの並列処理のために最適化された命令セットを処理するように動作可能であることを特徴とするシステム。
【請求項１４】
前記プロセッサの各々は、de minimis命令セットを処理するように動作可能であることを特徴とする請求項１３に記載のシステム。
【請求項１５】
前記プロセッサの各々は、前記プロセッサの中の少なくとも３つの特定のレジスタの各々専用のローカルキャッシュを備えていることを特徴とする請求項１３に記載のシステム。
【請求項１６】
前記ローカルキャッシュの各々のサイズは、前記チップ上のランダムアクセスメモリの１行に等しいことを特徴とする請求項１５に記載のシステム。
【請求項１７】
少なくとも３つの特定のレジスタは、命令レジスタ、ソースレジスタ、および宛先レジスタを含むことを特徴とする請求項１５に記載のシステム。
【請求項１８】
前記de minimis命令セットは、７つの命令から成ることを特徴とする請求項１４に記載のシステム。
【請求項１９】
前記プロセッサの各々は、単一のスレッドを処理するように動作可能であることを特徴とする請求項１３に記載のシステム。
【請求項２０】
単一のマスタプロセッサが、前記並列プロセッサの各々を管理する役割を担っていることを特徴とする請求項１３に記載のシステム。
【請求項２１】
単一のチップ上の複数の並列プロセッサ、マスタプロセッサ、およびコンピュータメモリを利用するスレッドレベルの並列処理の方法において、前記複数のプロセッサの各々は、de minimis命令セットを処理し、かつ単一のスレッドを処理するように動作可能であり、
（ａ）ローカルキャッシュを、前記複数のプロセッサの各々の中の３つの特定のレジスタの各々に割り当てるステップと、
（ｂ）単一のスレッドを処理するために複数のプロセッサのうちの１つを割り当てるステップと、
（ｃ）前記プロセッサによって割り当てられた各スレッドを処理するステップと、
（ｄ）前記プロセッサによって処理された各スレッドからの結果を処理するステップと、
（ｅ）スレッドが処理された後に前記複数のプロセッサのうちの１つの割り当てを解除するステップとを有していることを特徴とする方法。
【請求項２２】
de minimis命令セットは、７つの命令から成ることを特徴とする請求項２１に記載の方法。
【請求項２３】
de minimis命令セットの中の各命令は、長さが最高でも８ビットであることを特徴とする請求項２１に記載の方法。
【請求項２４】
de minimis命令セットの中の各命令は、１クロックサイクルの中で処理されることを特徴とする請求項２１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００６年２月３日に出願された米国仮特許出願第６０／７６４,９５５号に対する優先権を主張する。この仮出願の全内容は、ここでの引用により本願明細書に組み込まれるものとする。
【背景技術】
【０００２】
コンピュータの速度は、２つの一般的な方法を用いて増加させることができる。命令実行速度を上げる、または並列により多くの命令を実行する。命令実行速度が、シリコン中の電子移動度の限界に近づくとき、並列法（parallelism）は、コンピュータの速度を上げるための最善の代替案になる。
【０００３】
並列法の以前の試みは、以下を含んでいる。
１．次の命令のフェッチング（fetching）を、現在の命令の実行とオーバーラップさせること。
２．命令のパイプライン化（pipelining）。命令パイプラインは、各命令をできるだけ多くの部分に分解し、次にシーケンシャル命令を並列実行ユニットの中にマッピングすることを試みる。理論上最高の改良は、多段階命令の非効率性、並列実行ユニットを満たされた状態に保つための十分なシーケンシャル命令を提供するための多くのソフトウェアプログラムの無能力、および、分岐、ループ、またはケース構文が実行ユニットの補充を必要とする状態に遭遇したとき、払われるかなりの時間ペナルティ（penalty）のために、めったに達成されない。
３．単一命令多重データ（Single instruction multiple data）すなわちSIMD。この種の技術は、インテルペンティアム（登録商標）３および他のプロセッサの中で実現されているように、インテルＳＳＥ命令セットの中で見つかる。この技術においては、単一の命令が複数のデータセット上で実行される。この技術は、特別なアプリケーション、例えばビデオグラフィックスレンダリングの用途にだけ役立つ。
４．ハイパーキューブ。この技術は、プロセッサおよびローカルメモリの大きな二次元アレイ（array）、時には三次元アレイを用いる。プロセッサのこれらのアレイをサポートするのに必要な通信および相互接続は、本質的に、それらを非常に専門化されたアプリケーションに限定する。
【０００４】
パイプラインは、１つの命令の実行の一部分、例えばフェッチ、デコード、実行、ストアなどを連続して実行する複数のシーケンシャルな段階から成る命令実行ユニットである。いくつかのパイプラインが並列に配置され得るので、全てのパイプラインが命令を実行している状態になるまで、プログラム命令が次々と各パイプラインに供給される。それから、満たされた命令は、最初のパイプラインで繰り返される。Ｎ個のパイプラインが命令および実行で満たされるとき、性能に対する効果は、単一の実行ユニットに対して実行速度をＮ倍増加させるのと理論的に同じである。
【０００５】
成功するパイプライン化は、以下に依存する。
１．命令の実行は、いくつかの連続した状態として定義されることが可能でなければならない。
２．各命令は、同じ数の状態を持っていなければならない。
３．命令当たりの状態の数は、並列実行ユニットの最大数を決定する。
【０００６】
パイプライン化は、並列のパイプラインの数に基づいて性能の上昇を成し遂げることができ、かつ、並列のパイプラインの数は、一命令の中の状態の数によって決定されるので、パイプラインは、複雑な複数の状態を持つ命令を助長する。
【０００７】
重度にパイプライン化されたコンピュータは、並列パイプライン実行ユニットから予想される理論的な性能の改善に近い性能を、めったに成し遂げることはない。このパイプラインペナルティ（penalty）のいくつかの理由は、以下を含んでいる。
１．ソフトウェアプログラムは、シーケンシャルな命令だけから構成されているわけではない。様々な研究は、実行フローの変化が８〜１０命令毎に起こることを示している。プログラムのフローを変化させる分岐は、パイプラインを転覆させる。パイプラインの転覆を最小限にする試みは、複雑かつそれらの緩和において不完全でありがちである。
２．全ての命令に同じ数の状態を持つことを強いることは、しばしば最小公分母（すなわち、最も遅くて最も複雑な）命令の要求を満たす実行パイプラインに導く。パイプラインのため、全命令は、それらが必要とするか否かを考えないで、同じ数の状態にされる。例えば、論理演算（例えばANDまたはOR）は、ADDより１桁速く実行されるが、両者は、しばしば、実行のために同量の時間を割り当てられる。
３．パイプラインは、複数の状態を有する複雑な命令を助長する。２状態を必要とする可能性がある命令は、通常２０状態を満たすように拡張される。なぜなら、それがパイプラインの深さであるからである。（インテルペンティアム（登録商標）４は、２０状態のパイプラインを用いている。）
４．各パイプラインの状態のために必要な時間は、特定の状態に対する設計マージンまたは許容誤差に加えて、論理回路および関連するトランジスタによる伝播遅延が原因であるにちがいない。
５．パイプラインレジスタおよび他のリソースのアクセスのための調停は、調停論理のトランジスタの伝播遅延により、しばしば性能を低下させる。
６．状態を追加すると、速度が上がるよりはむしろ、実際には実行が遅くなるということ以前に、一命令が分割され得る状態の数に対する上限が存在する。いくつかの研究は、ディジタルイクイップメントコーポレーションのアルファプロセッサの最近の世代のパイプラインアーキテクチャがその地点を越え、かつ実際に以前のより短いパイプラインのバージョンのプロセッサより実行が遅いことを示している。
【０００８】
パイプラインを別々に分割すること
ＣＰＵ設計の再考に対する１つの考え方は、複数（Ｎ個）の単純化されたプロセッサに分割された、パイプライン化された実行ユニットについて考えることである。（レジスタおよびいくつかの他のロジックは、このような設計においては複製されることが必要かもしれない。）Ｎ個の単純化されたプロセッサの各々は、上述したパイプラインアーキテクチャに勝る以下の利点がある。
１．パイプラインによる遅れがない。分岐予測が必要ない。
２．全ての命令に最も遅い命令と同じ実行時間を割り当てられるのではなく、命令に必要なだけの時間をとることができる。
３．命令は、必要な実行状態を減らすことによって単純化され、これによりパイプラインペナルティを減らすことができる。
４．パイプラインから除去される各状態によって伝播遅延を削減することができ、
かつこの状態のために必要な設計マージンを除くことができる。
５．レジスタの調停を除くことができる。
【０００９】
さらに、Ｎ個の単純化されたプロセッサを備えるシステムには、パイプライン化されたＣＰＵに勝る以下の利点がある。
１．最大パイプライン並列性の制限がない。
２．パイプライン型プロセッサとは異なり、複数の独立型プロセッサは、使用しないときに、電力消費を減らすために、選択的に電源を切ることができる。
【００１０】
並列法への現在のアプローチに関する他の課題
並列法の多くの実施態様は、アムダールの法則の制限に屈する。並列法による加速は、課題の直列不可能（non-serializable）部分に起因するオーバーヘッドによって制限される。本質的には、並列法の量が増加するにつれて、それをサポートするために必要な通信が、並列法に起因する増進を圧倒する。
【００１１】
レッドライン（Redline）にあるストップライト（Stoplight）
現在のプロセッサの他の非効率性は、即時の計算要求に応ずるためにコンピューティングパワーを拡大縮小する能力がないことである。大部分のコンピュータは、何かが起こるのを待ちつつ、それらの時間の大部分を費やしている。それらは、入出力、次の命令、メモリアクセス、または時にはヒューマンインタフェースを待っている。この待機は、コンピューティングパワーの非効率的な浪費である。さらに、待機に費やされるコンピュータの時間は、しばしば電力消費および熱の発生を増加させる結果となる。
【００１２】
待機の原則に対する例外は、エンジンコントローラ、シグナルプロセッサ、およびファイアウォールルータのようなアプリケーションである。これらのアプリケーションは、課題のセットおよび解決策のセットの予め定められた性質のために、並列法を加速するための優れた候補である。Ｎ個の独立した乗算の積を必要とする課題は、Ｎ個の乗算器を用いれば、より速く解くことができる。
【００１３】
汎用コンピュータの認められた性能は、実際にはそのピークの性能である。最近、汎用コンピュータが忙しくなり始めたのは、高速なスクリーンリフレッシュを伴うビデオゲームを走らせること、大きなソースファイルをコンパイルすること、またはデータベースを検索することによる。最適な世界において、ビデオレンダリングは、特別な目的、シェーディング、変換、およびレンダリングハードウェアを考慮に入れている。このような特定用途のハードウェアに対するプログラミングについて考える１つの方法は、「スレッド」の使用である。
【００１４】
スレッドは、独立したプログラムであり、自己完結型であり、まれにしかデータを他のスレッドに伝達しない。スレッドの一般的な使用法は、ゆっくりとしたリアルタイムの動作からデータを収集して、整理された結果を提供することである。スレッドは、ディスプレイ上の変化を描画するために用いられることもある。スレッドは、他のスレッドとの更なる相互作用を要求する前に、数千または数百万の状態を通って遷移することができる。独立したスレッドは、並列法を通して性能が増強される機会を示している。
【００１５】
多くのソフトウェアコンパイラは、ソフトウェア設計プロセスを考慮に入れるために、スレッドの生成および管理をサポートする。同じ考慮は、好ましい実施形態におけるスレッドに最適化されたマイクロプロセッサ（ＴＯＭＩ）の中で実現されるスレッドレベル並列法の技術を介して、複数のＣＰＵの並列処理をサポートする。
【００１６】
スレッドレベル並列法
スレッディングは、単一のＣＰＵ上のソフトウェアプログラムを考慮するために、よく理解された技術である。スレッドレベル並列法は、ＴＯＭＩプロセッサの使用を通してプログラムの加速を成し遂げることができる。
【００１７】
他の並列法に勝るＴＯＭＩプロセッサの１つの重要な利点は、ＴＯＭＩプロセッサが、現在のソフトウェアプログラミング技法に対して最小限の変更しか必要としないことである。新規なアルゴリズムが開発される必要はない。多くの既存のプログラムは、再コンパイルされる必要があるかもしれないが、実質的に書き直される必要はない。
【００１８】
効果的なＴＯＭＩコンピュータアーキテクチャは、多数の単純化されたプロセッサに関して構築されるべきである。異なるアーキテクチャが、異なるタイプのコンピューティング課題のために用いられ得る。
【００１９】
基本的なコンピュータの動作
汎用コンピュータにとって、頻度を下げる順として最も一般的な動作は、ロードおよびストア、シーケンシング、および数学（Math）およびロジックである。
【００２０】
ロードおよびストア
ロードおよびストアのパラメータは、ソースおよび宛先である。ロードおよびストアの力は、ソースおよび宛先の範囲である（例えば、４ギガバイトは、２５６バイトより強力な範囲である）。現在のソースおよび宛先と関連する局所性（locality）は、多くのデータセットにとって重要である。プラス１、マイナス１は最も役に立つ。現在のソースおよび宛先からのオフセットが増加するほど、次第に役立たなくなる。
【００２１】
ロードおよびストアは、メモリ階層によっても影響され得る。記憶装置からのロードは、ＣＰＵが実行することができる最も遅い動作である。
【００２２】
シーケンシング
分岐およびループは、基本的なシーケンシング命令である。テストに基づいてシーケンスが変わる命令は、コンピュータが決定を行うやり方である。
【００２３】
数学およびロジック
数学およびロジック動作は、３つの動作の中で使用が最も少ない。ロジック動作は、ＣＰＵが実行することができる最も速い動作であり、単一のロジックゲートの遅延と同じ程度に小さい遅延しか必要としない。数学動作は、より複雑である。なぜなら、上位ビットが下位ビットの演算の結果に依存するからである。３２ビットADDは、桁上げ先回り制御を用いても、少なくとも３２ゲートの遅延を必要とする。シフトおよび加算手法を用いるMULTIPLYは、３２個のADDに相当するものを必要とする。
【００２４】
命令サイズのトレードオフ
完全な命令セットは、演算コードから成り、それは、無限の可能なソース、宛先、演算、および次の命令を選択するのに十分大きい。残念なことに、完全な命令セットの演算コードは無限に幅が広く、従って命令のバンド幅はゼロである。
【００２５】
高い命令バンド幅のためのコンピュータ設計は、最少の演算コードビットで最も多くの共通ソース、宛先、演算、および次の命令を能率的に定めることができる演算コードを有する命令セットの作成を必要とする。
【００２６】
幅の広い演算コードは、高い命令バスバンド幅の要求につながり、結果として生じるアーキテクチャは、フォンノイマンボトルネックによって急速に制限され、コンピュータの性能は、メモリから命令をフェッチする速度によって制限される。
【００２７】
メモリバスが６４ビット幅である場合、各メモリサイクルの中で、単一の６４ビット命令、２つの３２ビット命令、４つの１６ビット命令、または８つの８ビット命令をフェッチすることができる。３２ビット命令は、１６ビット命令の２倍役立つべきである。なぜなら、それは半分の命令バンド幅をカットしているからである。
【００２８】
命令セット設計の主な目的は、命令の冗長性を減らすことである。一般に、最適化された効率的な命令セットは、命令およびデータの局所性を利用する。最も簡単な命令の最適化は、ずっと以前になされた。大部分のコンピュータプログラムにとって、最も見込みのある次の命令は、メモリの中のシーケンシャルな次の命令である。従って、次の命令フィールドを有するあらゆる命令の代わりに、大部分の命令は、次の命令が現在の命令＋１であると仮定する。ソースのための０ビットおよび宛先のための０ビットを有するアーキテクチャを構築することは可能である。
【００２９】
スタックアーキテクチャ
スタックアーキテクチャコンピュータは、ゼロオペランドアーキテクチャとも呼ばれる。スタックアーキテクチャは、プッシュダウンスタックの内容に基づいて、全ての動作を実行する。２オペランド動作は、スタックに両方のオペランドが存在することを必要とする。動作を実行するとき、両方のオペランドがスタックからPOPされ、動作が実行され、かつ結果がスタックにPUSHされて戻される。スタックアーキテクチャコンピュータは、非常に短い演算コードを有することができる。なぜなら、ソースおよび宛先は、スタックにあると暗示されているからである。
【００３０】
大部分のプログラムは、必要なときにスタックで必ずしも利用可能ではないグローバルレジスタの内容を必要とする。この発生を最小限にする試みは、スタックの先頭にあるオペランド以外のオペランドにアクセスすることを可能にするスタックインデクシングを含む。スタックインデクシングは、追加の演算コードビットがより大きい命令という結果をもたらすか、またはスタックインデックス値をスタック自体に配置するための追加の動作を必要とする。時には１つ以上の追加のスタックが定義される。より良好であるが最適ではない解決策は、コンビネーション  スタック/レジスタ  アーキテクチャである。
【００３１】
スタックアーキテクチャ動作は、明らかな最適化に逆らう方法で、しばしば冗長でもある。例えば、各POPおよびPUSH動作は、スタックがメモリの中で操作されるときに時間を浪費するメモリ動作を引き起こす可能性を有している。さらに、スタック動作は、次の動作のために直ちに必要となるかもしれないオペランドを消費する可能性があり、これにより、さらに別のメモリ動作の可能性によってオペランドの重複を必要とする。例えば、一次元アレイの全要素に１５を乗算する動作である。
【００３２】
１つのスタックアーキテクチャにおいて、これは以下によって実行される。
１．アレイの開始アドレスをPUSHする
２．アドレスをDUPLICATEする（それで、我々は、アレイに結果をストアするためのアドレスを持つ。）
３．アドレスをDUPLICATEする（それで、我々は、アレイから読み出すためのアドレスを持つ。）
４．PUSH INDIRECT（スタックの先頭によって示されているアレイ位置の内容をPUSHする）
５．PUSH 15
６．MULTIPLY（１５かける我々が第３行の中で読み出したアレイの内容）
７．SWAP（次の命令のためにスタックの先頭のアレイアドレスを得る。）
８．POP INDIRECT（乗算結果をPOPして、それをアレイに戻してストアする。）
９．INCREMENT（次のアレイ項目に対するポイント。）
１０．アレイが完了するまで、ステップ２へ行く。
第９行のループカウンタは、追加のパラメータを必要とする。いくつかのアーキテクチャにおいて、このパラメータは、他のスタックに格納される。
【００３３】
仮定的なレジスタ/アキュムレータ  アーキテクチャにおいて、この例は以下によって実現される。
１．アレイの開始アドレスをSTORE POINTERする
２．READ POINTER（アキュムレータに示されているアドレスの内容を読む。）
３．MULTIPLY 15
４．STORE POINTER（示されたアドレスの中へ結果をストアする。）
５．INCREMENT POINTER
６．アレイが完了するまで、第２行へ行く。
【００３４】
上記の例で、スタックアーキテクチャのための９ステップ対レジスタアーキテクチャのための５ステップを比較せよ。さらにまた、スタック動作は、スタック動作に起因して、余分のメモリアクセスのために少なくとも３回のあり得る機会を有している。仮定的なレジスタ/アキュムレータ  アーキテクチャのループ制御は、レジスタの中で容易に処理され得る。
【００３５】
スタックは、式（expression）を評価するために役立ち、ほとんどのコンパイラでこのように用いられる。スタックは、入れ子にされた動作、例えばファンクションコールのためにも役立つ。ほとんどのＣコンパイラは、ファンクションコールをスタックによって実行する。しかし、汎用記憶装置を補わないと、スタックアーキテクチャは、多くの追加データの転送および操作を必要とする。最適化のために、スタックPUSHおよびPOP動作は、また、数学およびロジック動作と区別しなければならない。しかし、上記の例から分かるように、スタックは、繰り返しデータをロードかつストアするとき、特に非効率的である。なぜならアレイアドレスがPUSH INDIRECTおよびPOP INDIRECTによって消費されるからである。
【発明の開示】
【課題を解決するための手段】
【００３６】
一態様において、本発明はシステムであり、（ａ）単一のチップ上の複数の並列プロセッサと、（ｂ）チップ上に配置されていて、プロセッサの各々によってアクセス可能なコンピュータメモリとを備えていて、プロセッサの各々は、de minimis命令セットを処理するように動作可能であり、プロセッサの各々は、プロセッサ内の少なくとも３つの特定のレジスタの各々専用のローカルキャッシュを備えている。
【００３７】
様々な実施形態において、（１）ローカルキャッシュの各々のサイズは、チップ上のランダムアクセスメモリの１行に等しい。（２）関連するキャッシュを有する少なくとも３つの特定のレジスタは、命令レジスタ、ソースレジスタ、および宛先レジスタを含む。（３）de minimis命令セットは、７つの命令から成る。（４）プロセッサの各々は、単一のスレッドを処理するように動作可能である。（５）アキュムレータは、インクリメント命令を除く、あらゆる命令のためのオペランドである。（６）各命令のための宛先は、常にオペランドレジスタである。（７）３つのレジスタは自動インクリメントであり、３つのレジスタは自動デクリメントである。（８）各命令は、完了するのに１クロックサイクルしか必要としない。（９）命令セットは、BRANCH命令およびJUMP命令を備えていない。（１０）各命令は、長さが、長くても８ビットである。（１１）単一のマスタプロセッサは、並列プロセッサの各々を管理する役割を果たす。
【００３８】
別の態様において、本発明はシステムであり、（ａ）単一のチップ上の複数の並列プロセッサと、（ｂ）チップ上に配置されていて、プロセッサの各々によってアクセス可能なコンピュータメモリとを備えていて、プロセッサの各々は、スレッドレベルの並列処理のために最適化された命令セットを処理するように動作可能である。
【００３９】
様々な実施形態において、（１）プロセッサの各々は、de minimis命令セットを処理するように動作可能である。（２）プロセッサの各々は、プロセッサ内の少なくとも３つの特定のレジスタの各々専用のローカルキャッシュを備えている。（３）ローカルキャッシュの各々のサイズは、チップ上のランダムアクセスメモリの１行に等しい。（４）少なくとも３つの特定のレジスタは、命令レジスタ、ソースレジスタ、および宛先レジスタを含む。（５）de minimis命令セットは、７つの命令から成る。（６）プロセッサの各々は、単一のスレッドを処理するように動作可能である。（７）単一のマスタプロセッサは、並列プロセッサの各々を管理する役割を果たす。
【００４０】
別の態様において、本発明は、単一チップ上の複数の並列プロセッサ、マスタプロセッサ、およびコンピュータメモリを用いるスレッドレベルの並列処理方法であり、複数のプロセッサの各々は、de minimis命令セットを処理して、単一のスレッドを処理するように動作可能であり、（ａ）ローカルキャッシュを複数のプロセッサの各々の中の３つの特定のレジスタの各々に割り当てるステップと、（ｂ）単一のスレッドを処理するために、複数のプロセッサのうちの１つを割り当てるステップと、（ｃ）プロセッサによって各々の割り当てられたスレッドを処理するステップと、（ｄ）プロセッサによって処理された各スレッドからの結果を処理するステップと、（ｅ）スレッドが処理された後に、複数のプロセッサのうちの１つの割り当てを解除するステップとを有している。
【００４１】
様々な実施形態において、（１）de minimis命令セットは、７つの命令から成る。(２)de minimis命令セットの中の命令は、長さが、長くても８ビットである。（３）de minimis命令セットの中の各命令は、１クロックサイクル内に処理される。
【発明を実施するための最良の形態】
【００４２】
本発明の少なくとも１つの実施形態のＴＯＭＩアーキテクチャは、好ましくは、汎用コンピュータとして動作可能な最小限のロジックを用いる。最も一般的な動作には優先権が与えられる。大部分の動作は、可視的、規則的、かつコンパイラ最適化のために利用可能である。
【００４３】
一実施形態において、図１に示すように、ＴＯＭＩアーキテクチャは、アキュムレータ、レジスタ、およびスタックアーキテクチャ上での変形である。この実施形態において、
１．アキュムレータアーキテクチャと同様に、アキュムレータは、インクリメント命令を除いて、常にオペランドのうちの１つである。
２．レジスタアーキテクチャと同様に、宛先は、常にオペランドレジスタのうちの１つである。
３．アキュムレータおよびプログラムカウンタは、レジスタ空間の中にもあり、従って操作され得る。
４．３つの特別なレジスタは、自動インクリメントおよび自動デクリメントであり、入出力のスタックおよびストリームを作成するのに役立つ。
５．全ての動作は、１クロックサイクル（および２状態：クロックハイ、クロックロー）を必要とする。
６．全ての命令は、長さが８ビットであり、命令デコードを単純化して速度を上げている。
７．BRANCHまたはJUMP命令がない。
８．図２に示すように、８ビット命令から３ビットのオペレータを選択することを可能にする７つの命令しかない。
【００４４】
好ましい実施形態のいくつかの利点は、以下を含む。
１．全ての動作は、パイプラインによって必要とされるものと同等のものによって抑えられるのではなく、ロジックによって許容される最大速度で動く。論理演算は最も高速である。数学演算は次に高速である。メモリアクセスを必要とする動作は最も遅い。
２．アーキテクチャは、パッケージピン、加算器桁上げ時間、および有用性のみによって制限される任意のデータ幅に比例する。
３．アーキテクチャは、汎用コンピュータの全ての動作を実行するのに必要な最小限の可能な機能に近い。
４．アーキテクチャは、非常に透明で、非常に規則的であり、大部分の動作は、最適化コンパイラで利用可能である。
【００４５】
アーキテクチャは、単一のモノリシックチップ上で、多数回、複製されるために十分簡単に設計されている。一実施形態は、メモリとモノリシックのＣＰＵの複数のコピーを埋め込んでいる。３２ビットＣＰＵは、大部分のゲートはレジスタを定めている１，５００ゲート足らずで実現され得る。好ましい実施形態におけるほとんど１，０００個のＴＯＭＩ  ＣＰＵは、単一のインテルペンティアム（登録商標）４と同数のトランジスタを用いて実現され得る。
【００４６】
命令セット
命令セットのうちの７つの命令が、それらのビットマッピングと共に図２に示されている。各命令は、好ましくは単一の８ビットワードから成る。
【００４７】
アドレッシングモード
図３は、様々なアドレッシングモードの有効アドレスを示している。
【００４８】
アドレッシングモードは、以下の通りである。
即値
レジスタ
レジスタ  間接
レジスタ  間接  自動インクリメント
レジスタ  間接  自動デクリメント
【００４９】
特別なケース
レジスタ０およびレジスタ１の両方は、プログラムカウンタ（ＰＣ）を指す。オペランドとしてレジスタ０（ＰＣ）を持つ演算は、全て、アキュムレータキャリービット（Ｃ）が１に等しいという条件付きである。Ｃ＝１であれば、ＰＣの旧値はアキュムレータ（ＡＣＣ）にスワップされる。オペランドとしてレジスタ１（ＰＣ）を持つ演算は、全て、無条件である。
【００５０】
分岐がない
分岐およびジャンプ動作は、通常、ＣＰＵ設計者の課題である。なぜなら、それらが貴重な演算コード空間の多くのビットを必要とするからである。分岐機能は、LOADACC, xxを用いて所望の分岐アドレスをＡＣＣにロードして、次に、STOREACC, PC命令を用いて分岐を遂行することによって引き起こされ得る。分岐は、レジスタ０に保存したときのＣの状態次第で、なされる。
【００５１】
スキップ
スキップは、INC, PCを実行することによって引き起こされ得る。実行は２サイクルを必要とし、１つはカレントＰＣインクリメントサイクルを完了させるためであり、１つはINCのためである。スキップは、レジスタ０をインクリメントしたときのＣの状態次第で、なされる。
【００５２】
相対分岐
相対分岐は、所望のオフセットをＡＣＣにロードして、次にADD, PC命令を実行することによって引き起こされ得る。相対分岐は、レジスタ０に加算したときのＣの状態次第で、なされる。
【００５３】
前方への分岐
前方への分岐は、後方への分岐より役に立つ。なぜなら、ループのために必要な後方への分岐の位置は、初めてループの先頭を通るプログラムステップのときＰＣを保存することによって、容易に捕獲されるからである。
【００５４】
相対分岐より効率的な前方への分岐は、分岐エンドポイントの最下位ビットをＡＣＣにロードして、次にＰＣにストアすることによって、引き起こされ得る。ＰＣは、レジスタ０またはレジスタ１の使用に応じて、条件付または無条件の両方でアクセスされ得るので、前方への分岐もまた、宛先オペランドとしてのＰＣレジスタの選択（レジスタ０またはレジスタ１）に応じて、条件付または無条件となり得る。
【００５５】
例えば、
LOADI, #1C
STOREACC, PC
【００５６】
もしＡＣＣの最上位ビットがゼロであれば、最下位６ビットのみがＰＣレジスタに転送される。もし現在のＰＣレジスタの最下位６ビットがロードされるべきＡＣＣ値より小さいのであれば、レジスタの最上位ビットは不変のままである。もし現在のＰＣレジスタの最下位６ビットがロードされるべきＡＣＣ値より大きいのであれば、現在のＰＣレジスタはインクリメントされ、第７ビットでスタートする。
【００５７】
これは、効果的に分岐を３１命令前方まで可能にする。前方への分岐のこの方法は、可能な場合はいつでも用いられるべきである。なぜなら、それは、相対分岐のための３命令に対して２命令しか必要としないだけでなく、最も遅い動作のうちの１つである加算器を通る経路を必要としないからである。図２Ａは、動作中の前方への分岐を示している。
【００５８】
ループ
ループの先頭は、LOADACC, PCを用いてセーブすることができる。結果として生じるループ構文の先頭に対するポインタは、レジスタにストアされるか、またはオートインデクシングレジスタのうちの１つにプッシュされる。ループの末尾で、ポインタはLOADACC, EAによって検索され、STOREACC, PCを用いてＰＣにリストアされ、これにより後方へのループが引き起こされる。ループは、レジスタ０への保存によるＣの状態次第で、なされ、これにより条件付き後方へのループが引き起こされる。
【００５９】
自己変更（modifying）コード
STOREACC, PCを用いて自己変更コードを書くことが可能である。命令は、引き起こされ、またはＡＣＣにフェッチされ、そして、次の命令として実行されるＰＣに格納される。この技術は、ＣＡＳＥ構文を作成するために用いられ得る。
【００６０】
JUMPTABLEのＮ個のアドレスとベースアドレスとから成るメモリ内のジャンプテーブルアレイを仮定する。便宜のために、JUMPTABLEは、ローメモリ２０の中にあるので、そのアドレスは、LOADIまたは１以上の右シフトADD, ACCが続くLOADIによって生成され得る。
【００６１】
ジャンプテーブルへのインデックスが、ＡＣＣの中にあり、かつジャンプテーブルのベースアドレスが、JUMPTABLEと名付けられた汎用レジスタの中にあると仮定する。
ADD, JUMPTABLE  インデックスをジャンプテーブルのベースアドレスに加算する。
LOADACC, (JUMPTABLE)  インデックスされたアドレスをロードする
STOREACC, PC  ジャンプを実行する。
【００６２】
００００からスタートする低位メモリがシステムコールに割り当てられる場合、
各システムコールは、以下の通りに実行される。ここでSPECIAL_FUNCTIONは即値オペランド０−６３の名前である。
LOADI, SPECIAL_FUNCTION  システムコール番号をロードする
LOADACC, (ACC)  システムコールのアドレスをロードする
STOREACC, PC  関数へジャンプする
【００６３】
右シフト
基本的なアーキテクチャは、右シフト演算を想定していない。もしこのような演算が必要であれば、好ましい実施形態の解決策は、汎用レジスタのうちの１つを「右シフトレジスタ」に指定することである。STOREACC, RIGHTSHIFTは、「右シフトレジスタ」への単一の位置を右シフトしたＡＣＣをストアする。ここで、その値は、LOADACC, RIGHTSHIFTによって読むことができる。
【００６４】
アーキテクチャのスケーラビリティ
ＴＯＭＩアーキテクチャは、好ましくは８ビット命令を特徴とするが、データ幅は、制限される必要はない。図４は、いかにして４〜３２ビットの任意の幅のデータ経路が容易に作成されるかを示している。より広い幅のデータ処理を行うことは、所望の幅に対して、レジスタセット、内部データ経路、およびＡＬＵの幅を増加させることを必要とするだけである。データ経路の上限は、加算器のキャリー伝播遅延およびトランジスタの予算によって制限されるのみである。
【００６５】
好適なＴＯＭＩアーキテクチャは、説明を簡単にするため、フォンノイマンメモリ構成として実現されるが、（別々のデータおよび命令バスを有する）ハーバードアーキテクチャによって実現することも可能である。
【００６６】
共通の数学演算
２の補数の数学は、いくつかの方法でなされ得る。汎用レジスタは、全て“１s”として予め設定され、ALLONESと名付けられる。オペランドは、OPERANDと名付けられたレジスタの中にあると仮定する。
LOADACC, ALLONES
XOR, OPERAND
INC, OPERAND  “２s”の補数がOPERANDの中に残る。
【００６７】
共通のコンパイラ構造
大部分のコンピュータプログラムは、コンパイラによって生成される。従って、実用的なコンピュータアーキテクチャは、共通のコンパイラ構造に適合しているべきである。
【００６８】
Ｃコンパイラは、通常、ファンクションコールにパラメータを渡すためのスタックを維持する。Ｓ、Ｘ、またはＹレジスタをスタックポインタとして用いることができる。ファンクションコールは、例えば、STOREACC, (X)+を用いて、スタックとして動作するオートインデクシングレジスタのうちの１つにパラメータをプッシュする。関数を入力すると、パラメータは、使用のために汎用レジスタにPOPされる。
【００６９】
スタック相対アドレッシング
汎用レジスタに都合よく適合させることができるときより、ファンクションコールを通過したより多くの要素があるときがある。以下の例のために、スタックプッシュ動作がスタックをデクリメントすると仮定する。もしＳがスタックレジスタとして用いられているのであれば、スタックの先頭に対してＮ番目の項目を読むために、
LOADI, N
STOREACC, X
LOADACC, S
ADD, X
LOADACC, (X)
【００７０】
アレイへのインデクシング
アレイ関数にエントリすると、アレイのベースアドレスは、ARRAYと名付けられた汎用レジスタに置かれる。アレイの中のＮ番目の要素を読むために、
LOADI, N
STOREACC, X
LOADACC, ARRAY
ADD, X
LOADACC, (X)
【００７１】
Ｎワード要素アレイへのインデクシング
時々、アレイは、Ｎワード幅の要素に割り当てられる。アレイのベースアドレスは、ARRAYと名付けられた汎用レジスタに置かれる。５ワード幅アレイの中のＮ番目の要素の最初のワードにアクセスするために、
LOADI, N
STOREACC, X  テンポラリレジスタにストアする
ADD, ACC  ２をかける
ADD, ACC  再び２をかける＝４
ADD, X  プラス１＝５
LOADACC, ARRAY
ADD, X  アレイのベースアドレスをプラスする
LOADACC, (X)
【００７２】
ローカルＴＯＭＩキャッシング
キャッシュは、メインメモリと比べて、大きさにおいてより小型で、アクセスにおいてより高速なメモリである。減少されたアクセスタイムおよびプログラムおよびデータアクセスの局所性は、キャッシュ動作を可能にし、多くの動作のために好適なＴＯＭＩプロセッサの性能を増加させる。他の観点から見て、キャッシュは、ＴＯＭＩプロセッサのメインメモリからの独立性を増加させることによって、並列処理性能を増加させる。キャッシュのメインメモリに対する相対的な性能およびキャッシュに、またはキャッシュから、他のメインメモリに、ロードまたはストアを要求する前に、ＴＯＭＩプロセッサが実行可能なサイクル数は、ＴＯＭＩプロセッサ並列法による性能の上昇の量を決定する。
【００７３】
ＴＯＭＩローカルキャッシュは、ＴＯＭＩプロセッサ並列法によって性能の上昇を強化する。図５に示すように、各ＴＯＭＩプロセッサは、好ましくは３つの関連するローカルキャッシュを備えている。
命令−PCと関連する
ソース−Ｘレジスタと関連する
宛先−Ｙレジスタと関連する
【００７４】
これらのキャッシュの最適な大きさは、アプリケーションに依存する。典型的な実施形態は、各キャッシュに対して１０２４バイトを必要とする。換言すれば、１０２４の命令と、ソースおよび宛先の２５６の３２ビットワードである。少なくとも２つの要因が、キャッシュの最適サイズを決定する。第１は、他のキャッシュのロードまたはストア動作が要求される前に、ＴＯＭＩプロセッサが繰り返すことができる状態の数である。第２は、メインメモリの動作の間に可能なＴＯＭＩプロセッサ実行サイクルの数と関連するメインメモリからのキャッシュのロードまたはストア動作のコストである。
【００７５】
ＴＯＭＩプロセッサのＲＡＭの中への埋め込み
一実施形態において、広いバスは、大きな埋め込まれたメモリをキャッシュに接続するので、キャッシュに対するロードまたはストア動作は、速く起こることができる。ＲＡＭに埋め込まれたＴＯＭＩプロセッサで、全てのキャッシュのロードまたはストアは、ＲＡＭの列に対する単一のメモリサイクルから成る。一実施形態において、埋め込まれたメモリは、６３個のＴＯＭＩプロセッサの要求に応答しているので、１つのＴＯＭＩプロセッサに対するキャッシュのロードまたはストアの応答時間は、他のＴＯＭＩプロセッサのキャッシュのロードまたはストアが完了する間、延長可能である。
【００７６】
図６に示すように、キャッシュは、関連するメモリアドレッシングレジスタＸ，Ｙ，ＰＣの変化に基づいて、ストアおよびロードされる。例えば、ＰＣレジスタの全幅は、２４ビットであり得る。ＰＣキャッシュが１０２４バイトである場合、ＰＣの下位１０ビットは、ＰＣキャッシュの中でのアクセスを定義する。上位１４ビットの中に変化があるようにＰＣが書き込まれるとき、キャッシュロードサイクルが要求される。そのＰＣキャッシュと関連するＴＯＭＩ  ＣＰＵは、キャッシュロードサイクルが完了するまで実行を停止し、示された命令は、ＰＣキャッシュからフェッチされ得る。
【００７７】
キャッシュダブルバッファリング
２次キャッシュは、キャッシュロード要求を予想してロードされ得る。２つのキャッシュは同一であり、ＰＣの上位１４ビットの内容に基づいて交互に選択されかつ選択から外される。上記の例では、ＰＣの上位１４ビットが、２次キャッシュの中に予め格納されたデータのそれと合うように変化するとき、２次キャッシュは、１次キャッシュとして選択されるようになる。旧１次キャッシュは、その時は２次キャッシュになる。大部分のコンピュータプログラムが線形にメモリの中で増加するので、本発明の一実施形態は、常にキャッシュの内容、現在のＰＣプラス１の上位１４ビットによって示されるメインメモリの内容をフェッチする２次キャッシュを有する。
【００７８】
２次キャッシュの追加は、現在のキャッシュの境界線の外に移動するときに、ＴＯＭＩプロセッサが、メモリデータがメインメモリからフェッチされるのを待たなければならない時間を減らす。２次キャッシュの追加は、ＴＯＭＩプロセッサの複雑さをほとんど２倍にする。最適システムのために、複雑さが２倍になるのであれば、対応するＴＯＭＩプロセッサの性能も２倍になることで相殺されなければならない。さもないと、２次キャッシュのない２つのより簡単なＴＯＭＩプロセッサが、同じトランジスタ数で実現され得る。
【００７９】
高速乗算、浮動小数点演算、追加の機能
整数乗算および全ての浮動小数点演算は、特別な目的のハードウェアを用いてさえ、実行するために、多くのサイクルを必要とする。従って、それらは、基本的なＴＯＭＩプロセッサに含めるよりはむしろ、他のプロセッサを考慮に入れるべきである。デジタル信号処理（ＤＳＰ）動作は、全乗算が多くのサイクルを必要とする場合であっても、しばしば、サイクル毎に結果を生じる高度にパイプライン化された乗算器を用いる。何度も同じアルゴリズムを繰り返す信号処理アプリケーションのために、このような乗算器アーキテクチャが最適であり、ＴＯＭＩプロセッサに対する周辺プロセッサとして組み込まれ得るが、もしそれがＴＯＭＩプロセッサの中に直接組み込まれるのであれば、それは、たぶん複雑さを増加させ、かつ全体の性能を減少させる。図７は、広いシステムＲＡＭバスを利用するために構成された追加の処理機能の一例を示している。
【００８０】
ＴＯＭＩ割り込みストラテジー
割り込みは、プロセッサの通常のシーケンシャル動作に対する外部イベントであり、それは、プロセッサに、その動作シーケンスを直ちに変えることを強いる。
【００８１】
割り込みの例は、外部装置による動作の完了またはいくつかのハードウェアによるエラー状態である。従来のプロセッサは、通常のシーケンシャル動作を素早く停止し、現在の動作の状態をセーブし、割り込みを引き起こしたどんなイベントでも処理するために、いくつかの特別な動作の実行を開始し、特別な動作が完了されたときに以前の状態を回復し、シーケンシャル動作を続けるために、どんな事でもする。割り込み処理品質の主要な基準は、応答時間である。
【００８２】
割り込みは、従来のプロセッサに対していくつかの課題を提起する。それらは、実行時間を不確定にする。それらは、状態をストアしてそれからリストアするプロセッササイクルを浪費する。それらは、プロセッサ設計を難しくし、あらゆるプロセッサ動作を遅くする遅延をもたらす可能性がある。
【００８３】
即時の割り込み応答は、エラー処理および現実世界の活動に直接結びついているプロセッサを除いて、大部分のプロセッサに対しては不必要である。
【００８４】
マルチプロセッサＴＯＭＩシステムの一実施形態において、１つのプロセッサのみが、主な割り込み機能を備えている。他の全てのプロセッサは、それらがいくつかの割り当てられた仕事を完了して、それら自身で停止するまで、中断されずに動く。または、それらがコーディネートプロセッサによって停止させられるまで動く。
【００８５】
入出力（Ｉ/Ｏ）
ＴＯＭＩプロセッサ環境の一実施形態において、単一のプロセッサが、外部の世界に対する全てのインターフェースについて責任を負っている。
【００８６】
ダイレクトメモリアクセス（ＤＭＡ）制御
一実施形態において、ＴＯＭＩプロセッサシステムにおける外部の世界に対する即時の応答は、ＤＭＡコントローラを介して起こる。ＤＭＡコントローラは、外部装置によって要求されるときに、外部装置からシステムＲＡＭに書き込みを行うための内部データバスにデータを転送する。同じコントローラが、また、要求されると、システムＲＡＭから外部装置にデータを転送する。ＤＭＡ要求は、内部バスアクセスに対する最高優先度を有する。
【００８７】
ＴＯＭＩプロセッサのアレイの編成
本発明の好ましい実施形態のＴＯＭＩプロセッサは、かなりの数、複製され、かつモノリシックチップ上の追加の処理機能、非常に幅の広い内部バス、およびシステムメモリと結合されるように設計されている。このようなシステムのための例示的なメモリマップが図８に示されている。
【００８８】
各プロセッサのためのメモリマップは、そのプロセッサ用のローカルレジスタに対して、最初の３２の位置（１６進法の１Ｆ）を費やす（図３参照）。メモリマップの残りは、それらのキャッシュレジスタを通して全てのプロセッサによってアドレス指定可能である（図６参照）。システムＲＡＭのアドレス指定能力は、ローカルキャッシュと関連している３つのレジスタＰＣ，Ｘ，およびＹの幅のみによって制限される。レジスタが２４ビット幅である場合、全アドレス指定能力は４メガバイトであるが、上限はない。
【００８９】
一実施形態において、６４個のＴＯＭＩプロセッサは、メモリと共にモノリシックに実現される。単一のマスタプロセッサが、その他の６３個を管理する役割を果たす。スレーブプロセッサのうちの１つがアイドル状態で、クロックが動いていないとき、それは、ほとんど電力を消費しないし、ほとんど熱を発生しない。初期化時には、マスタプロセッサのみが使用可能である。マスタは、スレッドが開始すべき時間まで、フェッチングおよび実行の命令を開始する。各スレッドは、プレコンパイルされて、メモリにロードされる。スレッドを開始するために、マスタは、このスレッドをＴＯＭＩ  ＣＰＵのうちの１つに割り当てる。
【００９０】
プロセッサ稼働率
好ましく仕事をするためのＴＯＭＩプロセッサの稼働率のコーディネート（Coordination）は、図９に示すプロセッサ稼働率テーブルによって処理される。コーディネート（マスタ）プロセッサは、好ましくは以下の機能を実行することができる。
１．スレッドの実行アドレス、ソースメモリ、および宛先メモリを含むが、これらに限られない、そのスタック上にスレーブプロセッサのためにコールしているパラメータをプッシュする。
２．スレーブプロセッサを起動する。
３．ポーリングまたは割り込みに応答することによって、スレーブプロセッサスレッド完了イベントに応答する。
【００９１】
プロセッサ要求
コーディネートプロセッサは、稼働率テーブルからプロセッサを要求することができる。available_flagが「０」にセットされた最低位のプロセッサの数が戻される。すると、コーディネートプロセッサは、利用可能なプロセッサに関するavailable_flagを「１」にセットし、これによりスレーブプロセッサを起動する。プロセッサが利用可能でない場合、要求はエラーを返す。代替案として、プロセッサは、実行されるべき要求された仕事に関する優先順位レベルに基づいて、コーディネートプロセッサによって割り当てられ得る。優先順位方式に基づいてリソースを割り当てる技術は、従来技術において周知である。図１０は、プロセッサ割り当ての３つの好適な構成要素を示している。コーディネートプロセッサを起動する動作、スレーブプロセッサの動作、および割り込み応答によるコーディネートプロセッサの結果処理。
【００９２】
段階的にスレーブプロセッサを起動すること
１．コーディネートプロセッサは、それ自身のスタック上へ走るためにスレッドに対するパラメータをプッシュする。パラメータは、以下のものを含む。スレッドの先頭アドレス、スレッドに対するソースメモリ、スレッドに対する宛先メモリ、および最後のパラメータカウント。
２．コーディネートプロセッサは、利用可能なプロセッサを要求する。
３．プロセッサ割り当てロジックは、その関連するavailable_flagをセットし、かつその関連するdone_flagをクリアする、数値的に最低のスレーブプロセッサの番号、またはエラーを返す。
４．エラーが返されると、コーディネートプロセッサは、スレーブプロセッサが利用可能になるまで要求を再試行するか、またはエラーを処理するためのいくつかの特別な動作を実行する。
５．利用可能なプロセッサ番号が返されたら、コーディネートプロセッサは、示されたプロセッサに対するavailable_flagをクリアする。この動作は、選択されたスレーブプロセッサのスタックに、スタックパラメータのparameter_count数をプッシュする。done_flagは、ゼロにクリアされる。
６．スレーブプロセッサは、先頭スタック項目を検索し、それをスレーブプロセッサのプログラムカウンタに転送する。
７．スレーブプロセッサは、次に、命令キャッシュの中に、プログラムカウンタによって示されるメモリカラムをフェッチする。
８．スレーブプロセッサは、命令キャッシュの始めから命令を実行し始める。最初の命令は、たぶん、スタックからコールしているパラメータを検索することである。
９．スレーブプロセッサは、命令キャッシュからのスレッドを実行する。スレッドが完了すると、その関連するdone_flagの状態をチェックする。done_flagがセットされている場合には、done_flagがクリアされるまで待つ。これは、コーディネートプロセッサがいかなる以前の結果も処理したことを示している。
１０．スレーブプロセッサに関する割り込みベクトルが−１にセットされている場合には、done_flagをセットしても割り込みは発生しない。従って、コーディネートプロセッサは、done_flagがセットされるようにポーリングを行う。
【００９３】
コーディネートプロセッサが、done_flagがセットされたことを検出すると、スレーブプロセッサの結果を処理し、かつ、おそらく、新しい仕事をするためにスレーブプロセッサを再割り当てする。スレーブプロセッサの結果が処理されると、関連するコーディネートプロセッサは、関連するdone_flagをクリアする。
【００９４】
スレーブプロセッサに関する割り込みベクトルが−１に等しくない場合、関連するdone_flagをセットすると、コーディネートプロセッサに割り込みが発生し、かつ割り込みベクトルアドレスで割り込みハンドラを実行し始める。
【００９５】
関連するavailable_flagもまたセットされた場合、コーディネートプロセッサは、スレーブプロセッサのスタックにプッシュされたリターンパラメータを読み取ることもできる。
【００９６】
割り込みハンドラは、スレーブプロセッサの結果を処理し、かつ、おそらく、新しい仕事をするためにスレーブプロセッサを再割り当てする。スレーブプロセッサの結果が処理されると、コーディネートプロセッサ上で動作している割り込みハンドラは、関連するdone_flagをクリアする。
【００９７】
１１．done_flagがクリアされると、スレーブプロセッサは、その関連するdone_flagをセットして、新しいstart_timeをセーブする。スレーブプロセッサは、仕事をし続けてもよいし、利用可能な状態に戻ってもよい。利用可能な状態に戻るために、スレーブプロセッサは、そのスタック上へリターンパラメータをプッシュし、続けてスタックカウントおよびそのavailable_flagをセットする。
【００９８】
メモリのロック
ＴＯＭＩプロセッサは、それらのキャッシュを通してシステムメモリを読み書きする。完全にキャッシュに入れられたカラムは、一度に読み書きされる。いかなるプロセッサも、システムメモリの任意の部分を読むことができる。個々のプロセッサは、その排他的な書き込みのために、メモリのカラムをロックすることができる。このロックメカニズムは、プロセッサ間でのメモリ書き込みコンフリクトを回避する。
【００９９】
提案されたアプリケーション
並列法は、個々のプロセッサに対して仕事の独立した部分に入ると考えられるアプリケーションを効果的に加速する。うまく考えられた１つのアプリケーションは、ロボットの視覚のための画像操作である。画像操作アルゴリズムは、相関、等化、エッジ識別、および他の動作を含む。多くは、行列操作によって実行される。図１１に示すように、このアルゴリズムは、非常にしばしば、うまく考えられる。
【０１００】
図１１に例示されたイメージマップは、全イメージマップの矩形のサブセットに対する画像データを操作するために割り当てられたプロセッサを含む、２４個のプロセッサを示している。
【０１０１】
図１２は、一実施形態において、ＴＯＭＩシステムＲＡＭが、どのように割り当てられ得るかを示している。システムＲＡＭの１つのブロックは、画像キャプチャの画素を保持し、他のブロックは、処理された結果を保持する。
【０１０２】
動作中に、コーディネートプロセッサは、一定時間毎に外部ソースから内部システムＲＡＭに画像ピクセルを転送するために、ＤＭＡチャンネルを割り当てる。画像キャプチャの一般的な速度は、１秒当たり６０画像である。
【０１０３】
コーディネートプロセッサは、次に、Ｘレジスタによって用いられるべき画像マップのアドレス、Ｙレジスタによって用いられるべき処理された画像のアドレス、２のパラメータカウント、および画像処理アルゴリズムのアドレスをプッシュすることによって、スレーブプロセッサ１をイネーブルにする。コーディネートプロセッサは、その後、同様に、プロセッサ２から２５をイネーブルにする。プロセッサは、画像処理アルゴリズムが完了するまで、それぞれ並列に実行を続ける。
【０１０４】
アルゴリズムが完了すると、各プロセッサは、プロセッサ稼働率テーブル内のその関連するdone_flagをセットする。結果は、コーディネートプロセッサによって処理される。それは、完了のためにポーリングすることであるか、または“done”イベント上での割り込みに応答することである。
【０１０５】
図１３は、６４個のプロセッサのモノリシックアレイのための例示的な平面図である。
【０１０６】
本発明が、添付の図面を参照して例示のみのために記載されてきたこと、および、その改良および修正が、その範囲または精神から逸脱することなく、本発明に対してなされ得ることは言うまでもない。
【図面の簡単な説明】
【０１０７】
【図１】一実施形態における例示的なＴＯＭＩアーキテクチャを示している。
【図２】例示的な命令セットを示している。
【図２Ａ】動作中の前方分岐を示している。
【図３】様々なアドレッシングモードの有効アドレスを示している。
【図４】４〜３２ビットから如何にしてデータ経路が容易に作成されるかを示している。
【図５】例示的なローカルキャッシュを示している。
【図６】例示的なキャッシュ管理状態を示している。
【図７】幅の広いシステムＲＡＭバスを活用するために構成された追加の処理機能の一実施形態を示している。
【図８】例示的なメモリマップを示している。
【図９】例示的なプロセッサ稼働率テーブルを示している。
【図１０】プロセッサ割り当ての３つの構成要素を示している。
【図１１】例示的なファクタリングを示している。
【図１２】例示的なシステムＲＡＭを示している。
【図１３】６４個のプロセッサのモノリシックアレイのための例示的な平面図を示している。
【図１】
2009525545.tif 000003
【図２】
2009525545.tif 000004
【図２Ａ】
2009525545.tif 000005
【図３】
2009525545.tif 000006
【図４】
2009525545.tif 000007
【図５】
2009525545.tif 000008
【図６】
2009525545.tif 000009
【図７】
2009525545.tif 000010
【図８】
2009525545.tif 000011
【図９】
2009525545.tif 000012
【図１０】
2009525545.tif 000013
【図１１】
2009525545.tif 000014
【図１２】
2009525545.tif 000015
【図１３】
2009525545.tif 000016
【国際調査報告】
2009525545.tif 000017