(57)【要約】【課題】　再形態特定可能処理装置を改善し、且つ再形態特定可能処理装置において使用する資源マネジャを改善する。【解決手段】　データソーティング装置が（１）定義した基準に従ってデータセットをソートする格納ソーターと、（２）格納ソーターから中間ソートデータ値を受取り且つ該中間ソートデータ値を少なくとも１個のキー値と比較するクエリーメカニズムを有している。該格納ソーターは、データセットをソーティングするための優先キューを有しており、該優先キューはＭ個の処理要素を有している。該クエリーメカニズムはＭ個の処理要素から中間ソートデータ値を受取る。該クエリーメカニズムは複数個の比較回路を有しており、その各々は、中間ソートデータ値のうちの一つが該少なくとも１個のキー値に等しいか否かを検知し、又は、一致しない場合には、該少なくとも１個のキー値よりも大きな（又は定義した基準に基づいてより小さな）最小値を抽出することが可能である。【選択図】　　　図１
2004133939.tif 000002
【特許請求の範囲】
【請求項１】
　データ処理システムに使用するデータソーティング装置において、
　定義した基準に従ってデータセットをソーティングすることが可能な格納ソーター、
　前記格納ソーターから複数個の中間ソートデータ値を受取ることが可能であり且つ前記中間ソートデータ値を少なくとも１個のキー値と比較するクエリーメカニズム、
を有していることを特徴とするデータソーティング装置。
【請求項２】
　請求項１において、前記格納ソーターが前記データセットをソーティングするための優先キューを有しており、前記優先キューはＭ個の処理要素を有していることを特徴とするデータソーティング装置。
【請求項３】
　請求項２において、前記クエリーメカニズムが前記優先キューにおける前記Ｍ個の処理要素のサブセットから前記複数個の中間ソートデータ値を受取ることを特徴とするデータソーティング装置。
【請求項４】
　請求項３において、前記クエリーメカニズムが複数個の比較回路を有しており、前記比較回路の各々は前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１個のキー値に等しいか否かを検知することが可能であることを特徴とするデータソーティング装置。
【請求項５】
　請求項４において、前記各比較回路が、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値よりも大きいか否かを検知することが可能であることを特徴とするデータソーティング装置。
【請求項６】
　請求項４において、前記各比較回路が、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値より小さいか否かを検知することが可能であることを特徴とするデータソーティング装置。
【請求項７】
　請求項４において、前記クエリーメカニズムが、更に、複数個の優先決定回路を有しており、前記優先決定回路の各々が定義した最適基準に従って結果的に得られるマッチを判別することが可能であることを特徴とするデータソーティング装置。
【請求項８】
　請求項７において、前記各比較回路の動作が前記格納ソーターから１つの値を除去することを特徴とするデータソーティング装置。
【請求項９】
　請求項８において、前記各比較回路が前記格納ソーターから１つの値を除去する場合には、前記格納ソーターが前記格納ソーターのステータスをアップデートすることを特徴とするデータソーティング装置。
【請求項１０】
　処理システムにおいて、
　レジスタファイルを有する固定データ経路、
　前記固定データ経路へ結合されておりデータソーティング装置を有する再形態特定可能論理ユニット、
を有しており、前記データソーティング装置が、
　　定義した基準に従ってデータセットをソーティングすることが可能な格納ソーター、
　　前記格納ソーターから複数個の中間ソートデータ値を受取り且つ前記中間ソートデータ値を少なくとも１つのキー値と比較することが可能なクエリーメカニズム、
を有していることを特徴とする処理システム。
【請求項１１】
　請求項１０において、前記格納ソーターが前記データセットをソーティングするための優先キューを有しており、前記優先キューがＭ個の処理要素を有していることを特徴とする処理システム。
【請求項１２】
　請求項１１において、前記クエリーメカニズムが前記優先キューにおける前記Ｍ個の処理要素のサブセットから前記複数個の中間ソートデータ値を受取ることを特徴とする処理システム。
【請求項１３】
　請求項１２において、前記クエリーメカニズムが複数個の比較回路を有しており、前記比較回路の各々は、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値と等しいか否かを検知することが可能であることを特徴とする処理システム。
【請求項１４】
　請求項１３において、前記各比較回路が、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値より大きいか否かを検知することが可能であることを特徴とする処理システム。
【請求項１５】
　請求項１３において、前記各比較回路が、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値より小さいか否かを検知することが可能であることを特徴とする処理システム。
【請求項１６】
　請求項１３において、前記クエリーメカニズムが、更に、複数個の優先判別回路を有しており、前記優先判別回路の各々が、定義した最適規準に従って結果的に発生するマッチを判別することが可能であることを特徴とする処理システム。
【請求項１７】
　請求項１６において、前記各比較回路の動作が前記格納ソーターから１つの値を除去することを特徴とする処理システム。
【請求項１８】
　請求項１７において、前記各比較回路が前記格納ソーターから１つの値を除去する場合に、前記格納ソーターが前記格納ソーターのステータスをアップデートすることを特徴とする処理システム。
【請求項１９】
　データ処理システムにおいて使用するためのデータをソーティングする方法において、
　定義した基準に従ってＭ個の処理要素を有する優先キューにおけるデータセットをソーティングし、
　前記Ｍ個の処理要素から複数個の中間ソートデータ値を抽出し、
　前記中間ソートデータ値を少なくとも１つのキー値と比較する、
上記各ステップを有していることを特徴とする方法。
【請求項２０】
　請求項１９において、更に、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値と等しいか否かを検知するステップを有していることを特徴とする方法。
【請求項２１】
　請求項２０において、更に、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値より大きいか否かを検知するステップを有していることを特徴とする方法。
【請求項２２】
　請求項２０において、更に、前記複数個の中間ソートデータ値のうちの１つが前記少なくとも１つのキー値より小さいか否かを検知するステップを有していることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、大略、処理システムに関するものであって、更に詳細には、データプロセッサにおいて使用するデータソーターに関するものである。
【背景技術】
【０００２】
　マイクロプロセッサチップ、ランダムアクセスメモリ（ＲＡＭ）チップ、応用特定集積回路（ＡＳＩＣ）チップ等の集積回路の速度、パワー及び複雑性は過去２０年の間劇的に増加した。より最近になって、これらの増加は所謂システム・オン・チップ（ＳｏＣ）装置の開発を招来している。ＳｏＣ装置は、例えば携帯電話又はテレビ受信器等の複雑なシステムのほぼ全てのコンポーネントをシリコンの単一部品上に集積化させることを可能とさせる。このレベルの集積化はシステムの寸法及び電力消費を著しく減少させ、又製造コストも減少させる。
【０００３】
　ＳｏＣ装置及びその他の大規模集積回路の最近の傾向は、リコンフィギャラブル（ｒｅｃｏｎｆｉｇｕｒａｂｌｅ）、即ち再形態特定可能処理装置の採用に向かうものである。再形態特定可能プロセッサは、典型的に、動的に再形態特定可能なユニット（ＲＵ）へ結合されている固定データ経路として実現される。然しながら、それが比較的新しいものであるために、再形態特定可能装置に対する広く採用されている基準のアーキテクチャは未だに存在しない。この分野における研究は極めて活発なものである。学究的研究の中で、注目に値する幾つかの業績としては、バークレイにおけるＧＡＲＰ、ノースウエスタン大学におけるＣｈｉｍａｅｒａ、カーネギーメロンにおけるＰｉｐｅｒｅｎｃｈ等がある。ＧＡＲＰはループ実現を高速化させるためにホストプロセッサへ取付けられており、そのコンパイラーによってＣコードから自動的に抽出され且つマッピングされるコプロセッサである。Ｃｈｉｍａｅｒａは最大で９個の入力オペランドのカスタム命令を実現する従来のプロセッサデータ経路における密接して結合された再形態特定可能機能ユニットである。Ｐｉｐｅｒｅｎｃｈは全体的なストリームを基礎としたメディアアプリケーションを実現する付加プロセッサであり、仮想パイプラインの概念を実現する。これらの提案の各々は異なる編成、プログラミングモデル及びプロセッサに対するインターフェースを有している。
【０００４】
　いずれの再形態特定可能処理装置の重要な性能パラメータは該プロセッサのハードウエア資源の管理である。ハードウエア資源の制限した組の管理はこのような資源の１組の要求されたコンフィギュレーション（ｃｏｎｆｉｇｕｒａｔｉｏｎ）即ち形態（リクエスター）に対する割当てが関与する。資源とリクエスターとの間のインターフェースとして作用されるべくデータ処理システムの一部として資源マネジャーが通常付加される。資源マネジャによって実施される基本的なタスクは以下のものである。
【０００５】
　（１）要求を遂行するために最も相応しい（即ち、最適な）使用可能な資源の組に対するサーチ。このことは、維持されねばならず且つ常に資源のステータスに関するアップデートした情報を包含するデータ構造（多分、ソートしたもの）が関与；
　（２）新たな要求割当及び終了による変化を反映させるためにこのようなデータ構造の修正；
　（３）リクエスターに対して資源を効果的に割当て且つセットアップする動作を実行。
【０００６】
　これらの動作は、しばしば、データ処理システムにおけるオーバーヘッドを表わす。何故ならば、資源マネジャーが割当てタスクを完了するまで、管理される資源は有用な作業を実施するために使用可能なものではないからである。従って、これらのステップを実施するのに費やされる時間はシステム資源の最も高い処理能力及び利用を与えるために最小とされるべきである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
　本発明は、以上の点に鑑みなされたものであって、上述した如き従来技術の欠点を解消し、改良した再形態特定可能処理装置を提供することを目的とする。特に、再形態特定可能処理装置において使用する改良した資源マネジャーを提供することを目的とする。
【課題を解決するための手段】
【０００８】
　本発明は、ソートしたデータ構造を効率的に管理し（キーフィールドｋに関し）且つ、ソートしたデータセット内に存在する場合には、所要のキーｋqと関連する情報を効率的に抽出し、又は最も近い（昇順又は降順のいずれか）キーｋfと関連するデータ値を抽出する問題に対処するものである。効率は応答時間及び必要とされるハードウエア資源によって考慮される。
【０００９】
　本発明はソートしたデータセットの管理及びクエリーの問題を解消するための効率的なハードウエア解決である。それは、基本的に、特定したキーフィールドｋに関して格納されているデータをソートするための必要性を考慮に入れるために修正した完全に連想型のメモリからなる。この構造は、最大でＮ個の値からなるセットを格納し、且つキーフィールドにおける特定した値ｎに関する情報をソート又は抽出することが可能である。
【００１０】
　従来技術の上述した欠点に対処するために、データ処理システムにおいて使用するデータソーティング装置を提供することが本発明の主要な目的である。本発明の有益的な実施例によれば、本データソーティング装置は、（１）定義した基準に従ってデータセットをソーティングすることが可能な格納ソーター、及び（２）該格納ソーターから複数個の中間ソートデータ値を受取り且つ該中間ソートデータ値を少なくとも１つのキー値と比較することが可能なクエリーメカニズムを有している。
【００１１】
　本発明の１実施例によれば、該格納ソーターは、データセットをソーティングするための優先キューを有しており、該優先キューはＮ個の処理要素を有している。
【００１２】
　本発明の別の実施例によれば、該クエリーメカニズムは該優先キューにおけるＭ個の処理要素のサブセットから該複数個の中間ソートデータ値を受取る。
【００１３】
　本発明の更に別の実施例によれば、該クエリーメカニズムは複数個の比較回路を有しており、該比較回路の各々は、該複数個の中間ソートデータ値のうちの１つが該少なくとも１つのキー値に等しいか否かを検知することが可能である。
【００１４】
　本発明の更に別の実施例によれば、各比較回路は、該複数個の中間ソートデータ値のうちの１つが該少なくとも１つのキー値より大きいか否かを検知することが可能である。
【００１５】
　本発明の別の実施例によれば、該クエリーメカニズムは、更に、複数個の優先判別回路を有しており、該優先判別回路の各々は、定義した最適基準に従って１つの結果的に得られるマッチのみを判別することが可能である。
【発明を実施するための最良の形態】
【００１６】
　以下に説明する図１乃至１０、及び本明細書において本発明の原理を説明するために使用する種々の実施例は単に例示的なものであって本発明の技術的範囲を制限するような態様で解釈されるべきものではない。当業者は、本発明の原理は任意の適宜に構成された処理システムにおいて実現することが可能であることを理解するものである。
【００１７】
　図１は例示的なデータプロセッサ１００を示しており、それは本発明の例示的実施例に基づく再形態特定可能ユニット１２５を有している。データプロセッサ１００は、又、再形態特定可能ユニットを包含する従来のシステムとアーキテクチャが類似している。データプロセッサ１００は、命令キャッシュ１０５、フェッチユニット１１０、分岐ユニット（ＢＲＵ）１１５、データ経路レジスタファイル１２０、ロード及びストアユニット１３０、データキャッシュ１３５、メモリ制御器１４０を包含する固定データ経路を有している。この固定データ経路は再形態特定可能ユニット１２５へ結合している。
【００１８】
　再形態特定可能ユニット１２５に対する究極的な目標は、与えられたアプリケーションがより効率的に且つより高い処理能力で実行することを可能とさせることである。本発明の例示的実施例によれば、再形態特定可能ユニット１２５は従来のＳＲＡＭを基礎としたプログラマブル即ちプログラム可能な論理技術に依存しており且つ計算要素、ルーチング即ち経路付けチャンネル、論理スイッチからなる規則的なグリッドとして実現することが可能である。これらの資源の各々はコンフィギュレーション即ち形態特定メモリ内に格納されている関連する組のコンフィギュレーション（形態特定）ビットにより制御される。任意の特定の時刻において、再形態特定可能ユニット１２５はコンフィギュレーション（形態特定）メモリ内にロードされている現在のコンフィギュレーション即ち形態に依存する機能を実現する。ＳＲＡＭプログラム可能技術のために、この機能性は、新たな且つ異なる組のコンフィギュレーションビットを単にローディングするだけで任意の時刻に変更させることが可能である。
【００１９】
　このアプローチは汎用プロセッサソリューションと比較して、柔軟性及び性能の上でより良好なトレードオフ即ち利益衡量をアーキテクチャに与える。例えば、本発明は、共通のドメイン（例えば、画像処理又はマルチメディアドメイン）からある範囲のアプリケーションの効率的な実現を可能とさせる。本発明は、アプリケーションを強制的に汎用組の計算資源とマッチさせるのではなく、アプリケーション条件とマッチすべく計算資源を効率的に適合させることを可能とする。この手法において、固定データ経路と再形態特定可能ユニット１２５との間のアプリケーションの区画化、同期、資源管理、再形態特定可能ユニット１２５の割当てがプログラムの効率にとって重要である。
【００２０】
　図２は本発明の１実施例に基づく再形態特定可能ユニット１２５を例示している。再形態特定可能ユニット１２５は従来の再形態特定可能ユニットとアーキテクチャが類似している。再形態特定可能ユニット１２５は、コンフィギュレーション（形態）マネジャ２１０、コンフィギュレーションメモリ２２０、再形態特定可能ローカルメモリバンク２２１、再形態特定可能アレイ２３０、コンフィギュレーションローダー２４０を有している。
【００２１】
　コンフィギュレーション（形態）マネジャ２１０は従来のＣＰＵとのインターフェースである。コンフィギュレーションマネジャ２１０はコンフィギュレーションの実行に対する要求を受付け且つ対応する結果をフィードバックする。コンフィギュレーションマネジャ２１０は再形態特定可能ユニット１２５の機能性をプログラムするためにコンフィギュレーション割当てを監視し且つ必要とされるコンフィギュレーションが現在ロードされておらず且つ使用可能でない場合にはデータプロセッサ１００をストールさせる。このような場合において、コンフィギュレーションローダー２４０がその要求を司るべく活性化される。結合メカニズムに依存して、再形態特定可能ユニット１２５は固定データ経路レジスタファイル１２０に対してのアクセスを有するか又は有するものでない場合がある。
【００２２】
　コンフィギュレーションローダー２４０はコンフィギュレーションのローディング及びキャッシングを司り、ダイレクトメモリアクセス（ＤＭＡ）制御器として作用する。例えばマルチコンテキスト（ｍｕｌｔｉ−ｃｏｎｔｅｘｔ）コンフィギュレーションメモリ等のエキストラな資源が使用可能である場合には、ロードプロセスは隠すことが可能である。再形態特定可能アレイ２３０は、ロードされたコンフィギュレーションにより支配された状態で、オペレーターが動的に構築され且つ除去されるデータ経路である。従来のシステムにおいては、再形態特定可能アレイ２３０は計算用セルからなる一様なグリッドであり、それはコンフィギュレーションの割当てを簡単化させる利点を有している。然しながら、特定の資源条件が既知である場合には、より規則性がないがより拘束性の高い編成を実現することが可能である。各セルは、特に入力と出力との相互接続において実施される機能性において、各制御点と関連する１組のビットを介して形態特定される。
【００２３】
　再形態特定可能ローカルメモリ２２１は、入力及び中間計算結果を格納するローカルレジスタファイルを実現するために再形態特定可能アレイ２３０から分離するか又はそれと合体させることが可能である。コンフィギュレーションメモリ２２０は、機能性及びデータ接続を定義するコンフィギュレーションビットを格納する。コンフィギュレーションメモリ２２０は、該アレイ内の各制御点に対して１つを超える組のコンフィギュレーションビットを格納する多数のコンフィギュレーションプレーンを有することが可能である。このことは異なるロードしたコンフィギュレーション即ち形態間において再形態特定可能ユニット１２５が高速のコンテキストスイッチを実施することを可能とする。又、最も最近に使用したコンフィギュレーション（形態）を格納するためにコンフィギュレーションキャッシュを使用することが可能であり、且つ再形態特定オーバーヘッドペナルティを減少させるコンフィギュレーションプリフェッチ技術を使用することが可能である。
【００２４】
　図３は本発明の１実施例に基づく再形態特定可能アレイ２３０を例示している。一般性を失うことなしに、再形態特定可能アレイ２３０は複数個のセルからなる規則的な構成として実現することが可能である。図３に示したように、再形態特定可能アレイ２３０は、ＣＢ０−ＣＢ１１を包含する形態特定可能ブロック（ＣＢ）、及びコンフィギュレーションメモリ２２０におけるＣＰ０−ＣＰ１１を包含する対応するコンフィギュレーションページ（ＣＰ）からなる規則的なグリッドを有している。マクロセル及びスライスの階層を再形態特定可能ユニット１２５に対して導入することが可能であり、セル、マクロセル、スライスレベルにおいての再形態の細分化を定義する。独立的に再形態特定することが可能な最小単位はコンフィギュレーションページ（ＣＰ）と呼ばれる。本明細書においては、各コンフィギュレーション即ち形態は、連続したコンフィギュレーションページにおいてのみ割当てられる。より一般的な割当ては、コンフィギュレーションマネジャ２１０及びコンフィギュレーションメモリ２２０がより複雑なものとなる犠牲において行うことが可能である。
【００２５】
　コンフィギュレーションマネジャ２１０は、例えば、ロードしたコンフィギュレーションの数及び再形態特定可能アレイ２３０内のこれらのコンフィギュレーションの位置を包含する再形態特定可能ユニット（ＲＵ）１２５のステータスを知得している。コンフィギュレーションマネジャ２１０は、基本的に、異なる実行要求を満足させる資源マネジャであり、再形態特定可能アレイ２３０において使用可能な制限された量から適切に資源を割当てる。このタスクを達成するために、コンフィギュレーションマネジャ２１０は、ＲＵステータスにおける変化を反映させるために、例えばコンフィギュレーション割当てマップ等の何等かのタイプのデータ構造を維持する場合がある。コンフィギュレーション割当てマップは各コンフィギュレーションに対しての初期的及び最終的コンフィギュレーションページのアドレスを包含する再形態特定可能ユニット１２５の現在アクティブなコンフィギュレーションを格納する。別のテーブルが連続する空のコンフィギュレーションページのインターバルを格納する。資源管理の観点からは、コンフィギュレーションマネジャ２１０は最近のマルチタスク用オペレーティングシステムカーネルと多くの類似性を共有している。
【００２６】
　ＣＰＵが再形態特定可能アレイ２３０において動作又はタスクの実行を要求すると、コンフィギュレーションマネジャ２１０は、その動作コンフィギュレーションが再形態特定可能アレイ２１０内に未だにロードされていない場合には、その実行に対して必要な資源が使用可能であるか否かを判別する。このような状態において、コンフィギュレーションマネジャ１２０は所要の動作コンフィギュレーションビットをロードするためにフリーの連続したコンフィギュレーションページからなる最小のセット（組）をサーチする。
【００２７】
　前述したように、割当て管理を簡単化するために連続するページを有することが望ましい。このことは、常駐していない動作が再形態特定可能アレイ２３０内に割り当てられ且つ形態特定されねばならない度にクエリーが発せられるべく、コンフィギュレーションマネジャ２１０へアクセス可能な順番付けしたデータ構造を使用することを暗示している。フリーなコンフィギュレーションページのセット即ち組は、要求された量よりも大きな最小の使用可能な値とすべきである（正確な値は最適な値を与える）。このことは、制限されている資源の最適な使用を保証し、且つ最大数の再形態特定可能動作に対しての再形態特定可能ユニット１２５が使用可能であることを保証する。
【００２８】
　本発明の有益的な実施例によれば、割当てアルゴリズムの簡明な実現は、再形態特定可能ユニット１２５からのサポートなしでデータプロセッサにおいてのみ実行されるインタラプトサービスルーチン（ＩＳＲ）として完全にソフトウエアで実施することが可能である。ＩＳＲは、必要とされるコンフィギュレーション即ち形態が存在していない場合に、再形態特定ユニット１２５により発生されるインタラプトを介してトリガさせることが可能である。この場合に、データ構造はメインメモリ内に格納され、且つコンフィギュレーションマネジャ２１０はより低い複雑性を有することとなる。
【００２９】
　ＩＳＲは、最も相応しい組の使用可能なページを見つけ出すためにデータ構造においてサーチを実施する。このソリューションは効率が悪く且つ実行及び応答時間の点で低い性能を有するものである。何故ならば、比較を行い且つデータ構造をアップデートするためにメインメモリへアクセスすることは時間がかかるからである。クエリーメカニズムと共に、コンフィギュレーションマネジャ２１０は、動作又はタスクが実行を終了する場合にデータ構造をアップデートし、前に割当てたコンフィギュレーションメモリページを開放する。このソリューションはアプリケーションコードを実行するためにプロセッサの低い利用係数を与えるものであるので非効率的であり、再形態特定可能ユニット１２５を正しく管理するためにコードのランにおいて高いオーバーヘッドを有している。
【００３０】
　その性能（応答時間及び利用係数）を改善するための可能なオプションは、効率的なソーティング及びクエリーを可能とさせるためにデータ構造を格納するための何等かの専用の回路を具備する混合型ハードウエア・ソフトウエアソリューションを採用することである。この場合に、完全に連想型のメモリを採用することが可能である。このソリューション即ち解決は、データがデータセット内にあることが既知である場合にはワンステップサーチを保証するが、データが存在しない場合には失敗し、従ってクエリーの成果として常に結果が得られねばならない場合には、キーに関しての推測を行いながらより多くのサーチステップが必要とされる。
【００３１】
　考慮中のデータセットは、空のコンフィギュレーションメモリ定義の連続したセット即ち組を表わす値により形成される（キーフィールドｋ、開始ページのアドレスを包含する別のフィールドＡk）。最適な管理は、必要以上のページを割り当てることの非効率性を回避するために、特定した値ｔのページ（クエリーキーｋq）に対して正確にサーチを行うことである。値ｐがデータセット内に存在しない場合には、このソリューションは最終的に値が見つかるまで値ｐ＋１等に対してテーブルに対して問い合わせを行うことを必要とする。このことは、発見された最も近い値Ｆ（キーｋf）がｐよりも著しく大きい場合には、特に時間がかかる場合がある。
【００３２】
　図４はソーター装置４００を例示しており、それは本発明の例示的実施例に基づくクエリーメカニズム４３０を包含している。ソーター装置４００は、挿入インターフェース４０５、抽出インターフェース４１０、格納ソーター４２０、クエリーブロック４３０を有している。格納ソーター４２０は、特定したキーフィールド（設計時間において一度決定され且つ固定される）に関してソートされるべきデータセットに対しての格納即ち記憶を提供し、且つクエリーブロック４３０は所要の情報を抽出する。外部世界に対するインターフェースは、実施すべき動作に基づいて定義される。挿入インターフェース４０５はキー値、残りの関連するデータ値（ＤＡＴＡ　ＩＮ）、挿入フラッグ信号に対するポートを有している。抽出（又はクエリー）インターフェース４１０は、サーチすべきキー、抽出された値（ＤＡＴＡ　ＯＵＴ）、抽出フラッグ信号に対するポートを与えている。
【００３３】
　動作用の利用は、挿入とそれに続くクエリー及び抽出の簡単なモデルに基づいている。クエリーは挿入数を超えることは不可能であり、従って常に以下の関係、
　　　Ｎextractions≦Ｎinsertions
が成立する。
【００３４】
　挿入インターフェース４０５と抽出インターフェース４１０とを接続する信号線は、前に行われた挿入数を超える場合に、抽出に対する要求をディスエーブルさせることによりこの動作用モデルを強制させる。
【００３５】
　本発明の有益的な実施例によれば、抽出動作は破壊的であり、クエリー動作から返されるデータセットが格納ソーター４２０から物理的に除去されることを意味する。別の実施例においては、本発明は、簡単明瞭であり且つハードウエア資源に関してより廉価である修正において破壊を回避すべく適合させることが可能である。
【００３６】
　格納ソーター４２０は特定したキー値に関してデータセットをソートされていることを維持する集積化したソーターを具備するメモリである。格納ソーター４２０はＮ個のセル（又は処理要素）からなる優先キューを実現するシストリック（ｓｙｓｔｏｌｉｃ）構造に基づいている。このようなシストリック構造はＣ．Ｌｅｉｅｓｒｓｏｎ著「シストリック優先キュー（Ｓｙｓｔｏｌｉｃ　Ｐｒｉｏｒｉｔｙ　Ｑｕｅｕｅｓ）」、テクニカルレポートＣＭＵ−ＣＳ−７９−１１５、カーネギーメロン大学、ピッツバーグ、ペンシルバニア、１９７９年４月の文献に記載されている。このタイプのシストリック構造は、与えれたデータシーケンスの最大（又は、設定時間選択に依存して最小）をある時刻において抽出することの問題を解くものである。
【００３７】
　本発明はその後の挿入及び抽出動作に対してソーティングメカニズムの一貫性を維持しながら、優先キュー内側から任意の値の抽出を可能とするためにこの構造を修正している。以下の説明において、降順で与えれたデータセットをソートするための構造について説明する。昇順でソートする構造に対しては類推的考慮が適用される。本発明の原理に基づくソーティング装置は、前述した挿入及び抽出メカニズムに依存している。Ｎ個のデータ値のシーケンスが与えられると、連続するサイクルにおいてある時間において一度づつ該挿入は逐次的である。
【００３８】
　図５は本発明の１実施例に基づく格納ソーター４２０における優先キューの基本的処理要素（ＰＥ）５００を例示している。処理要素５００は入力レジスタ５０５，５１０，５１５及びソーティング論理ブロック５２０を有している。処理要素５００は３入力ポート（Ｘ，Ｙ，Ｚ）、６出力ポート（Ｘ′，Ｙ′，Ｚ′，Ｘｉ，Ｙｉ，Ｚｉ）装置を有しており、それは３個の入力ポートをソートし且つこれら３個の入力ポートのうちでＸ′が最大値を得、Ｙ′が中間値を得、Ｚ′が最小値を得るようにそれらを出力ポートへ経路付けさせる。３個の残りの出力ポート（Ｘｉ，Ｙｉ，Ｚｉ）は処理要素５００の状態をクエリーブロック４３０へ転送する。入力レジスタ５０５，５１０，５１５は入力ポートをバッファする。これらのレジスタはソーティングのために使用すべきキーフィールド及び後に検索されることを必要とする関連する値を有している。
【００３９】
　図６は優先キュー６００を例示しており、それは、本発明の１実施例に基づく格納ソーター４２０内に処理要素（ＰＥ）５００からなるＮ個のセル（又はステージ）を有している。優先キュー６００はインターフェース（ＩＦ）論理ブロック４０５へ結合しており且つ例示的処理要素５００Ａ，５００Ｂ，５００Ｃ，５００Ｄ，５００Ｅ（説明を簡単化するためにＭ＝５と仮定する）を包含している。処理要素５００Ａ，５００Ｂ，５００Ｃ，５００Ｄ，５００Ｆ、は夫々、処理要素０（ＰＥ０）、処理要素１（ＰＥ１）、処理要素２（ＰＥ２）、処理要素３（ＰＥ３）、処理要素４（ＰＥ４）として順番に記号が付けられている。
【００４０】
　最も左側の処理要素５００（即ち、ＰＥ０）とインターフェースすることにより優先キュー６００に関して２つの基本的な動作を実施することが可能であり、即ち（１）ソートすべき新しい値を挿入するための挿入（ＩＮＳＥＲＴ）動作、及び（２）現在のデータセットの最大を抽出するための抽出（ＥＸＴＲＡＣＴ）動作である。本発明の例示的実施例においては、この後者の動作は実現されることはなく且つ抽出はクエリーブロック４３０を介して実施される。インターフェース論理ブロック４０５は、その構造が空である場合に更なる抽出をディスエーブルさせるため又はその構造が満杯であり且つオーバーフローしている場合に信号を発生するために、行われた挿入及び抽出を追従するためにカウンタを包含している。インターフェース論理ブロック４０５は、又、カウンタをアップデートし且つ優先キュー６００の状態を再調節し且つ一貫性のあるデータソートを維持するために、クエリーブロック４３０から内部の値が抽出された場合に注意を受取る。
【００４１】
　キーフィールドデータ範囲において２つの代表的な値を表わすことが必要であり、特に、正の無限（＋ＩＮＦ）及び負の無限（−ＩＮＦ）に対する表現が必要とされる。キーフィールドが２の補数系でＢ個のビットで表現され且つ最大の正の数（２B-1−１）を＋ＩＮＦとして解釈し且つ最小の負の数（−２B-1）を−ＩＮＦとして解釈するものと仮定する。従って、キー値は［−２B-1＋１，２B-1−２］の範囲を有しており、尚境界は包含されている。勿論、本発明の別の実施例においては、キーワード又は無限の値の有効性を主張するためにエキストラなビット線（キーとは別個）を付加すること等のその他の選択を採用することが可能である。リセット（ＲＥＳＥＴ）動作で内部値の全ては−ＩＮＦへ初期化される。更に、内部レジスタのいずれもクエリーブロック４３０からトリガされるリセット信号により実行期間中にリセットさせることが可能である。
【００４２】
　図７は本発明の１実施例に基づく内部レジスタ５０５，５１０，５１５の構造を例示している。Ｎ＋１個のセルの最後（ＰＥN）のＸ入力ポートは常に−ＩＮＦに等しく、従ってＺ′出力ポートは常に−ＩＮＦであり、且つＹ′が−ＩＮＦから異なる場合（又は最後のＰＥがＺ線上で−ＩＮＦと異なる入力を有する場合）には、オーバーフローが存在する（格納し且つソートすることが可能なものよりもより多くの値が挿入されている）。Ｎ個の挿入の与えられた最大の場合に、Ｍ＝Ｎ＋１個の処理要素５００を使用することによりオーバーフロー問題を回避することが可能である。
【００４３】
　各処理要素５００は１つ置きのクロックサイクル毎にアクティブである。実行は偶数位置における処理要素５００で開始し（即ち、偶数セル＝２ｉ、尚０≦２ｉ≦Ｍ、ｉ＝０，１，２．．．）、次いで奇数位置における処理要素５００に続く（即ち、奇数セル＝２ｉ＋１、尚０≦２ｉ＋１≦Ｍ、ｉ＝０，１，２．．．）。
【００４４】
　各セルに対する利用係数は５０％であり、２個のサイクル毎に１個の挿入又は抽出動作が潜在的に実施される。別の実施例においては、１つの可能な向上は、異なるレジスタセットに関して同一の比較論理を再使用するために偶数（２ｉ）及び奇数（２ｉ＋１）位置からのセルを合体させることとすることが可能であり、それにより１００％の利用に到達する。別の改善は両方のクロックエッジを使用することが関与する場合があり、その場合に、偶数セルは正のエッジで活性化され且つ奇数セルは負のエッジで活性化される。
【００４５】
　オリジナルの優先キュー６００は、現在の最大の挿入又は抽出のいずれかで全てのサイクルに関して使用されるものとされている。内部状態が修正された場合に、ＰＥ０のインターフェースにおける新たな挿入又は抽出なしで優先キュー６００の処理を維持することが重要である。
【００４６】
　図８は本発明の１実施例に基づくより詳細なクエリーブロック４３０の選択した部分を示している。クエリーブロック４３０はインターフェース論理８０５及び例示的な比較ブロック８１１，８１２，８１３を包含する複数個の比較ブロックを有している。ソーティングキーフィールドに関する比較論理ブロックを介して完全な連想性が得られる。例示的な比較ブロック８１１は比較ブロック、優先チェックブロック、トライステートラインドライバを有している。例示的な比較ブロック８１２及び８１３は同様の構造を有している。これらの比較ブロックは等しい（ＥＱ）比較及びより大きい（ＧＴ）機能に対する比較機能を実施する。比較ブロックの数は上述した格納ソーターブロック４２０からのＭ個のＰＥにおけるレジスタの数３×Ｍとマッチする。この数は、動作モード及び実行に関する拘束条件を注意深く分析することにより減少させることが可能である。
【００４７】
　優先チェックブロックは、複数のマッチの場合に、どの値が正しい出力結果であるかを決定する。一般的な規則として、小さな値の位置が、現在の例におけるように降順格納ソーター４２０を使用している場合に優先度を有している。従って、最も右側の比較ブロックが最も高い優先度を有している。各優先チェックブロックは右側のセルから全ての前の比較結果（又は複合信号）を受取り且つ何等かの決定機能を適用する。
【００４８】
　インターフェース論理ブロック８０５は同等比較から開始して実施すべき動作の信号を発生する。同等（ＥＱ）信号及びより大きい（ＧＴ）信号は複数個のセルからなるアレイ全体に沿って変化することなく伝播される。インターフェース論理ブロック８０５は同等クエリーのステータスに関する情報を受取り、且つ信号が活性化されない場合には（ソートしたデータセットにおいてマッチするキーが見つからないことを意味する）、インターフェース論理ブロック８０５は次のクロックサイクルから開始してより大きい比較が実施されるためのＧＴ信号をセットする。
【００４９】
　図９は本発明の１実施例に基づくより詳細な図８におけるクエリーブロック４３０においての比較ブロック及び優先チェックブロックの内部構造の選択した部分を示している。図９は最も右側のセルに対して（Ｍ個のＰＥを具備する昇順格納ソーター４２０における最も高い優先度を具備するＰＥM-1）、ソーター処理要素からの内部キー状態値（Ｘｉ，Ｙｉ，Ｚｉのいずれか）を包含する各レジスタへ取付けられている論理を示している。これは１つの可能な優先メカニズムの例に過ぎない。その他のセルに対する優先度はＡＮＤゲートを介して評価することが可能である。最悪の場合のクリチカルパス（即ち臨界的経路）はＭ個のＰＥを具備する格納ソーター４２０に対する最も左側の比較ブロックに関し３−Ｍ入力ＡＮＤゲートである。この高いファンインＡＮＤゲートは２入力ゲートの階層的ツリーとして実現することが可能であり、最悪の場合に、該クリチカルパスを拘束するためのｌｏｇ2（３Ｍ）レベルの論理を得る。
【００５０】
　比較が成功すると、リセット信号がレジスタへ送り戻され、対応するデータを格納ソーターブロック４２０において格納する。これはデータの抽出における破壊的メカニズムである。次いで、格納ソーターブロック４２０はエキストラの再評価サイクルを実施してソートした状態においての一貫性を維持する。信号が格納ソーターブロック４２０におけるインターフェース論理ブロック６２０へ送り戻されて挿入されたデータに関してその内部カウンタをアップデートし且つ優先キュー６００の再評価と共に進行する。
【００５１】
　格納ソーターブロック４２０における挿入（ＩＮＳＥＲＴ）及び抽出（ＥＸＴＲＡＣＴ）動作は、最も左側の処理要素５００（即ちＰＥ０）に対してのみ図５に示した例えば信号Ｙ及びＺ等の優先キュー６００のインターフェースにおいて提供されるデータ値を注意深く選択することにより実現することが可能である。新たな値ＫNの挿入動作はＹを＋ＩＮＦに設定し且つＺを新たな値ＫNに設定して実現することが可能である。抽出動作は、入力ポートＹ及び入力ポートＺの両方を−ＩＮＦ値に設定することにより実施することが可能である。抽出した値は、挿入された入力の組の中で優先キュー６００内に格納された最大値である。この挿入／抽出メカニズムは、レジスタが−ＩＮＦへ初期化されるという仮定の下で動作する。
【００５２】
　オリジナルの優先キュー６００は、常に、後者の２つの動作のうちの１つを一サイクル置きに印加することを必要とする。本発明は優先キュー６００に対して保持動作を与え、その場合に、新たな入力値が最も左側のＰＥインターフェースに提供されることはなく且つ値を抽出せねばならないものではない。このモードは入力Ｙが値＋ＩＮＦを有し且つ入力Ｚが−ＩＮＦを有するように設定することにより得ることが可能である。この動作なし（又は保持）モードは、優先キュー６００において何等変化がない場合には有用なものではなく、且つそれは前の状態の最小化に対応する。
【００５３】
　然しながら、それが重要である理由は、クエリーブロック４３０で確立される付加したインターフェースを介して、例えば内部値がクエリーブロック４３０のインターフェースを介して抽出される場合のように、内部状態レジスタに対する修正を行うことが可能だからである。クエリーブロック４３０からの抽出プロセスはリセット信号をその値を格納するレジスタへ送り戻し、それによりそれを−ＩＮＦへ設定する。優先キュー６００はデータセットのソーティングに関して非コヒレント状態に到達し、従ってクリーンで且つ正しい状態を回復するために最小化フェーズが必要とされる。この目標を達成するためには１つの再評価サイクルで充分である（全てのＰＥに対して一度活性化する）。
【００５４】
　クエリー動作はシステム抽出インターフェースを介して実施される。クエリーブロック４３０のインターフェース論理が同等（ＥＱ）から開始し第一比較が失敗した場合により大きい（ＧＴ）へ続く比較要求をシーケンス化するシーケンス化方法は、本発明により提供される１つの重要な革新である。資源管理問題を考慮すると、最適な選択はその要求を満足するのに充分な最小資源を許可するものである。
【００５５】
　１つの値が見つかり且つ抽出されると、格納ソーター４２０は、そのインターフェースに動作なしコマンドが存在する状態で格納されている値を再評価することが強制される。
【００５６】
　単一の挿入（ＩＮＳＥＲＴ）動作の後に、優先キュー６００は挿入されたデータセットの最大を１つのサイクルですぐさま提供することが可能である。その構造のシストリックな性質が与えられると、完全なソートを達成するためにある数の評価サイクルに対して新たなデータは処理要素５００Ａ−５００Ｅの間で流れねばならない。
【００５７】
　複数個の連続する挿入（オリジナルのモデルにおいては１つ置きのサイクル、又は両方クロックエッジで動作する場合にはすべてのサイクル）を実施することが可能であり、挿入した各値の評価フェーズのオーバーラップを可能とさせる。最後の挿入（ＩＮＳＥＲＴ）動作の後で且つクエリーブロック４３０のインターフェース論理ブロック８０５を介しての抽出（ＥＸＴＲＥＣＴ）動作を行う前に、優先キュー６００は安定な状態に到達せねばならず、その後の更なる評価サイクルは達成された順番を変更するものではないことを意味する。注意すべきことであるが、３Ｍ個のレジスタの中で、Ｍ段優先キュー６００の場合には、Ｍ−１個のレジスタのみがソートしたデータを保持し、その他はソートフェーズ期間中に値を一時的に格納し且つ伝播させるために有用である。該レジスタは偶数位置ＰＥにおけるＸ及びＹであり、最初のＰＥ（Ｘのみ）及び最後のＰＥ（Ｍが奇数である場合にはＹのみ）を排除している。このことは、クエリーブロック４３０における簡単化はＭ−１個の比較ブロック（３Ｍの代わり）のみに対する入力としてＭ−１個のレジスタのみを考慮することを意味する。このことは、又、優先チェックブロックの複雑性をクリチカルパスにおけるｌｏｇ2（Ｍ−１）レベルの論理へ簡単化させる。
【００５８】
　更に、注意すべきことであるが、ＰＥ４（処理要素５００Ｅ、然しながら、一般的にはＰＥ（Ｍ−１）、Ｍ個のＰＥ）における入力レジスタ５１５は、常に、−ＩＮＦを保持している。何故ならば、−ＩＮＦは常に入力ポートＸへ印加されるからである。更に注意すべきことであるが、ＰＥ０（処理要素５００Ａ）における入力レジスタ５０５は、常に、無限の値（＋ＩＮＦか又は−ＩＮＦのいずれか）を保持する。従って、これら２つのレジスタは必要なものではなく省略することが可能である。
【００５９】
　図１０Ａ−１０Ｓは挿入及び抽出の動作の簡単な例に対する本発明の原理に基づく優先キュー６００の動作を例示している。最大値の抽出は優先キュー６００の動作モードを例示する目的のためにのみ最も左側のＰＥにおいてのみ許容されるものと仮定する。本発明においては、抽出動作は任意の内部値を抽出することが可能なクエリーブロック４３０を介して実際にコマンドが与えられる。
【００６０】
　図１０Ａ−１０Ｓは動作シーケンス期間中における処理要素ＰＥ０−ＰＥ４に入力レジスタ５０５，５１０，５１５における実効ソート値を示している。
【００６１】
　図１０Ａ及び１０Ｓにおいて動作シーケンスは以下の通りであり、即ち、
　（１）６を挿入、
　（２）１０を挿入、
　（３）５を挿入、
　（４）４を挿入、
　（５）保持、
　（６）保持、
　（７）抽出、
　（８）保持（繰返し）。
【００６２】
　図１０Ａ及び１０Ｂは６挿入動作を例示している。図１０Ａは偶数要素がアクティブである場合の６挿入動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｂは、奇数要素がアクティブである場合の６挿入動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６３】
　図１０Ｃ及び１０Ｄは１０挿入動作を例示している。図１０Ｃは偶数要素がアクティブである場合の１０挿入動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｅは奇数要素がアクティブである場合の１０挿入動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６４】
　図１０Ｅ及び１０Ｆは５挿入動作を例示している。図１０Ｅは偶数要素がアクティブである場合の５挿入動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｆは奇数要素がアクティブである場合の５挿入動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６５】
　図１０Ｇ及び１０Ｈは４挿入動作を例示している。図１０Ｇは偶数要素がアクティブである場合の４挿入動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｈは奇数要素がアクティブである場合の４挿入動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６６】
　図１０Ｉ及び１０Ｊは最初の保持（ＨＯＬＤ）動作を例示している。図１０Ｉは偶数要素がアクティブである場合の最初の保持動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｊは奇数要素がアクティブである場合の最初の保持動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６７】
　図１０Ｋ及び１０Ｌは２番目の保持（ＨＯＬＤ）動作を例示している。図１０Ｋは偶数要素がアクティブである場合の第二保持動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｌは奇数要素がアクティブである場合の第二保持動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６８】
　図１０Ｍ及び１０Ｎは抽出（ＥＸＴＲＡＣＴ）動作を例示している。図１０Ｍは偶数要素がアクティブである場合の抽出動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｎは奇数要素がアクティブである場合の抽出動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００６９】
　図１０Ｏ及び１０Ｐは第三保持（ＨＯＬＤ）動作を例示している。図１０Ｏは偶数要素がアクティブである場合の第三保持動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｐは奇数要素がアクティブである場合の第三保持動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００７０】
　図１０Ｑ及び１０Ｒは第四保持（ＨＯＬＤ）動作を例示している。図１０Ｑは偶数要素がアクティブである場合の第四保持動作の最初の実行サイクル期間中における処理要素ＰＥ０，ＰＥ２，ＰＥ４の動作を示している。図１０Ｒは奇数要素がアクティブである場合の第四保持動作の第二実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００７１】
　最後に、図１０Ｓは偶数要素がアクティブである場合の第五保持動作の第一実行サイクル期間中における処理要素ＰＥ１及びＰＥ３の動作を示している。
【００７２】
　抽出（ＥＸＴＲＡＣＴ）動作を適用する前に必要とされるサイクル数における遅延に関して、優先キュー６００が既にＮ−１個の値（Ｎはオーバーフローなしでのキューの容量である）を包含している場合に新たな最小値を挿入する場合に最悪の場合が発生する。この場合に、該遅延は正確にＮ個のサイクルである（又は両方のクロックエッジで動作している場合にはＮ／２サイクル）。
【００７３】
　抽出動作を実行するために、キーが格納されているデータセット内に見つかった場合には該遅延は１個のクロックサイクルとすることが可能であり（これが１サイクルにおける比較論理に適合するものと仮定）、又はキーが見つからず且つ「より大きい」比較が適用される場合には複数個のサイクルとすることが可能である。注意すべきことであるが、この後者の場合には、比較を再計算することは必要ではない。結果が前のサイクルから既に使用可能であるので、該結果が図９に示されているマルチプレクサの出力へスイッチされ、それによりＥ　ＧＴ信号を設定する。
【００７４】
　クエリーからの最適以下の結果の危険性を発生することが許容される場合にはこの動作モードをより高速とさせることが可能である。抽出動作を行う前に挿入後の安定状態に到達するために最大でＮ個のサイクル待機することを回避することが可能である。この場合には偶数ＰＥにおける３個のレジスタの全てを考慮すべく比較論理を拡張せねばならず、比較ブロックの数においてクエリーブロック４３０の複雑性を僅かに増加させる。クエリー値が格納されているデータの中にある場合には（同等比較）、その結果は未だに最適なものである。最適以下の危険性はより大きいの問い合わせから発生する。何故ならば、最適な結果は未だに安定な最終の順序付けられた位置へ伝播している可能性があるからである。この場合には、選択された値はデータセットの中でその安定な位置に既に潜在する最適なものよりすぐ大きな値である。
【００７５】
　以上、本発明の具体的実施の態様について詳細に説明したが、本発明は、これら具体例にのみ制限されるべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００７６】
【図１】本発明の例示的実施例に基づく再形態特定可能ユニットを包含する例示的なデータプロセッサを示した概略図。
【図２】本発明の１実施例に基づく図１における再形態特定可能ユニットをより詳細に示した概略図。
【図３】本発明の１実施例に基づいて形態特定可能ブロック及び対応するコンフィギュレーションページからなる規則的なグリッドを有する再形態特定可能アレイを示した概略図。
【図４】本発明の１実施例に基づくクエリーメカニズムを有するソーター装置を示した概略図。
【図５】本発明の１実施例に基づくキューの基本的処理要素（ＰＥ）を示した概略図。
【図６】本発明の１実施例に基づく例示的処理要素からなるＭ個のステージを具備する全体的なキューを示した概略図。
【図７】本発明の１実施例に基づく内部レジスタの構造を示した概略図。
【図８】本発明の１実施例に基づく例示的クエリーブロックをより詳細に示した概略図。
【図９】本発明の１実施例に基づく図８におけるクエリーブロックにおける比較ブロックの内部構造をより詳細に示した概略図。
【図１０Ａ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｂ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｃ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｄ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｅ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｆ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｇ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｈ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｉ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｊ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｋ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｌ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｍ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｎ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｏ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｐ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｑ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｒ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【図１０Ｓ】本発明の原理に基づく優先キューの動作の１つの状態を示した概略図。
【符号の説明】
【００７７】
　１００　データプロセッサ
　１０５　命令キャッシュ
　１１０　フェッチユニット
　１１５　分岐ユニット（ＢＲＵ）
　１２０　データ経路レジスタファイル
　１２５　再形態特定可能ユニット
　１３０　ロード及びストアユニット
　１３５　データキャッシュ
　１４０　メモリ制御器
【図１】
2004133939.tif 000003
【図２】
2004133939.tif 000004
【図３】
2004133939.tif 000005
【図４】
2004133939.tif 000006
【図５】
2004133939.tif 000007
【図６】
2004133939.tif 000008
【図７】
2004133939.tif 000009
【図８】
2004133939.tif 000010
【図９】
2004133939.tif 000011
【図１０Ａ】
2004133939.tif 000012
【図１０Ｂ】
2004133939.tif 000013
【図１０Ｃ】
2004133939.tif 000014
【図１０Ｄ】
2004133939.tif 000015
【図１０Ｅ】
2004133939.tif 000016
【図１０Ｆ】
2004133939.tif 000017
【図１０Ｇ】
2004133939.tif 000018
【図１０Ｈ】
2004133939.tif 000019
【図１０Ｉ】
2004133939.tif 000020
【図１０Ｊ】
2004133939.tif 000021
【図１０Ｋ】
2004133939.tif 000022
【図１０Ｌ】
2004133939.tif 000023
【図１０Ｍ】
2004133939.tif 000024
【図１０Ｎ】
2004133939.tif 000025
【図１０Ｏ】
2004133939.tif 000026
【図１０Ｐ】
2004133939.tif 000027
【図１０Ｑ】
2004133939.tif 000028
【図１０Ｒ】
2004133939.tif 000029
【図１０Ｓ】
2004133939.tif 000030