(57)【要約】【課題】本発明は、ランスペースとして知られ、コンピューティングシステム制御、データ処理、およびデータ通信の分野に関し、より詳細には、特に、複数の処理要素において実行可能な、分解可能な多くの構成要素のタスクのための資源効率の良い計算を提供する相乗的な方法およびシステムに関する。【解決手段】この方法およびシステム（１０１）は、コードおよびデータ局所性を表す距離空間を用いて、コードおよびデータの割り当ておよび移動を導き、コード領域をマークするための解析を実行して、ランタイムを向上するための機会を提供し、さらに、ローカルメモリにアクセスするコードの圧縮セクションの分散起動に適した、低電力、ローカル、安全メモリ管理システムを提供する。ランスペースは、階層的な割り当て、最適化、モニタリングおよび制御を支援し、さらに、その回復可能な、エネルギ効率の良い大規模計算を支援する機構を提供する。【選択図】図１
2013524386.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システム資源を、１つ以上のアプリケーションプログラムのタスクに割り当てる方法であって、
ａ）少なくとも１つのタスクを達成するように設定されたコードレット群を取得することと、
ｂ）前記群内の前記コードレット間の依存関係を決定することと、
ｃ）前記コードレット間の前記依存関係、およびデータ処理システム資源の可用性に少なくとも部分的に基づいて、前記群内の所定のコードレットを、前記所定のコードレットの実行のためのデータ処理システム資源セットに動的にマッピングすることと、を含む、方法。
【請求項２】
前記マッピングは、配置、位置決め、再位置決め、移転および移動から成る群から選択された機能を含む、請求項１に記載の方法。
【請求項３】
前記マッピングは、前記所定のコードレットの実行のための起動時間の決定、および前記所定のコードレットの実行のための位置の決定から成る群から選択された機能を含む、請求項１に記載の方法。
【請求項４】
前記マッピングは、１）アプリケーションプログラムの性能メトリクスの向上、２）前記データ処理システム資源の利用性の向上、および３）所定の資源消費目標セットに従いながら、アプリケーションプログラムの性能メトリクスの最大化から成る群から選択された少なくとも１つの基準に基づくマッピングの実行を含む、請求項１に記載の方法。
【請求項５】
前記マッピングは、プログラムの全実行時間、特定セクション内のプログラムの実行時間、特定命令の実行前の最大遅延、用いられる処理ユニットの数量、用いられるメモリの数量、レジスタファイルの使用、キャッシュメモリの使用、レベル１キャッシュメモリの使用、レベル２キャッシュメモリの使用、レベル３キャッシュメモリの使用、レベルＮ（Ｎは正数）キャッシュメモリの使用、スタティックＲＡＭメモリの使用、ダイナミックＲＡＭメモリの使用、グローバルメモリの使用、仮想メモリの使用、前記プログラムの実行以外に使用可能なプロセッサの数量、前記プログラムの実行以外に使用可能なメモリの数量、エネルギ消費、ピークエネルギ消費、コンピューティングシステムの寿命コスト、更新に必要なレジスタ量、メモリ消去が必要な量、セキュリティ実施効率、およびセキュリティ実施コストから成る群から選択された測定値に関するアプリケーションプログラムの性能を最適化するように実行される、請求項１に記載の方法。
【請求項６】
前記マッピングは、プログラムの全実行時間、特定セクション内のプログラムの実行時間、特定命令の実行前の最大遅延、用いられる処理ユニットの数量、用いられるメモリの数量、レジスタファイルの使用、キャッシュメモリの使用、レベル１キャッシュメモリの使用、レベル２キャッシュメモリの使用、レベル３キャッシュメモリの使用、レベルＮ（Ｎは正数）キャッシュメモリの使用、スタティックＲＡＭメモリの使用、ダイナミックＲＡＭメモリの使用、グローバルメモリの使用、仮想メモリの使用、前記プログラムの実行以外に使用可能なプロセッサの数量、前記プログラムの実行以外に使用可能なメモリの数量、エネルギ消費、ピークエネルギ消費、コンピューティングシステムの寿命コスト、更新に必要なレジスタ量、メモリ消去が必要な量、セキュリティ実施効率、およびセキュリティ実施コストから成る前記群から選択された資源制約内で動作するように実行される、請求項１に記載の方法。
【請求項７】
前記マッピングは、時間により変化する目的の混合を追求するように実行され、前記混合は、事前指定された変化および動的に生じる変化から成る群から選択された要因に起因して、時間とともに変化する、請求項１に記載の方法。
【請求項８】
前記取得、前記決定または前記動的マッピングの１つ以上の実行を援助するためにコンパイル時の指示セットを適用することをさらに含む、請求項１に記載の方法。
【請求項９】
前記コンパイル時の指示は、所望の浮動小数点ユニット、所望の浮動小数点精度、アクセス頻度、アクセスの局所性、停止アクセス、読み出し専用データ型、最初は読み出し専用であるデータ型、最終的に読み出し専用であるデータ型、および条件的に読み出し専用であるデータ型から成る前記群から選択される、請求項８に記載の方法。
【請求項１０】
コンピュータプログラム実行に関するユーザまたはシステムが定義した目的を追求するための方法であって、
ａ）前記コンピュータプログラムを、コードレット、協働コードレットセット、協働抽象モジュールセット、またはそれ自体の他の成員の少なくともいくつかに共有されるデータの１つ以上を備えている抽象モジュールセットに分解することと、
ｂ）メモリスペース内、または実行時間での前記抽象モジュールの成員の最大の近接性を追求するための近接関係を定義することと、
ｃ）ランタイムシステムによって、ｉ）調整された方法により、抽象モジュール内において、最初にデータを配置するか、コードレットの実行を開始すること、または、ｉｉ）前記ユーザまたはシステムが定義した目的の追求において有益である場合に、調整された方法により抽象モジュールの成員を移動させることの少なくともいずれかを実行し、
ａ）前記配置または前記移動を、前記近接関係に少なくとも部分的に基づいて実行することと、を含む、方法。
【請求項１１】
前記分解は、前記抽象モジュール間の依存関係を最小化するように、前記コンピュータプログラムを分解することを含む、請求項１０に記載の方法。
【請求項１２】
前記抽象モジュール間の依存関係セットを決定することをさらに含む、請求項１０に記載の方法。
【請求項１３】
ユーザまたはシステムが定義した、コンピュータプログラムに関する目的を追求するための方法であって、
ｂ）前記コンピュータプログラムを、コードレット、協働コードレットセット、協働抽象モジュールセット、またはそれ自体の他の成員の少なくともいくつかに共有されるデータの１つ以上を備えている抽象モジュールセットに分解することと、
ｃ）前記抽象モジュールに関するプログラムランタイム情報、当該プログラムに関連する性能および資源活用を取得することと、
ｄ）前記プログラムランタイム情報を利用して、前記コンピュータプログラムの少なくとも一部の継続中またはその後の起動における、前記抽象モジュールのその後の配置または実行スケジュールを導くことと、を含む、方法。
【請求項１４】
前記分解は、前記抽象モジュール間の依存関係を最小化するように、前記コンピュータプログラムを分解することを含む、請求項１３に記載の方法。
【請求項１５】
前記抽象モジュール間の依存関係セットを決定することをさらに含む、請求項１３に記載の方法。
【請求項１６】
前記抽象モジュールの要素の改善した局所性の基準に少なくとも部分的に基づいて、実行中またはすぐ実行されるコードレットを含む前記抽象モジュールの前記要素を移動することをさらに含む、請求項１３に記載の方法。
【請求項１７】
資源の広範囲の割り当ての改善、エネルギ節約のための処理資源の低減、処理資源に関する電力の低減、および所定の処理タスクにより適した処理資源の利用から成る群から選択された基準に基づいて、前記抽象モジュールの要素を移動することをさらに含む、請求項１３に記載の方法。
【請求項１８】
データ処理資源をデータ処理タスクに割り当てるための方法であって、
ａ）コンパイル時において、コードレット移動およびデータマイグレーションから成る群から選択された動作のための１つ以上の機会を特定するために、可能性のあるコードおよびデータ割り当てを解析することと、
ｂ）ランタイムにおいて、実際のコードおよびデータ割り当てにより示される機会を実行するために、コードレットまたはデータを移動すること、を含む方法。
【請求項１９】
前記移動は、コードレットを十分に活用されていないプロセッサに移動することを含む、請求項１８に記載の方法。
【請求項２０】
１つ以上のコードレットの移動を予期して、少なくとも一部のデータを、あるロケールから別のロケールにコピーすることをさらに含む、請求項１８に記載の方法。
【請求項２１】
前述の方法によるコードレット処理において考慮される制限または特権を示す、前記コードレットに関するセキュリティマークの提供をさらに含む、請求項１８に記載の方法。
【請求項２２】
ソフトウェアアプリケーションの少なくともセグメントの実行を区分分けするための方法であって、
ａ）ランタイムシステムにクエリして、前記アプリケーションセグメントに使用可能な処理コア量を検出することと、
ｂ）前記セグメントを分割可能な処理ユニットの最大量を決定することと、
ｃ）ａ）およびｂ）で決定した前記量に基づいて、前記セグメントを、最適数の処理ユニットに分割することと、を含む、方法。
【請求項２３】
資源効率の良いプログラム実行を改善するための、コンピュータプログラムをコンパイルおよび起動する方法であって、
ａ）プログラムコンパイル時において、前記プログラムのコードレットに関する最適効率実行環境を決定することと、
ｂ）プログラムランタイムにおいて、前記決定に少なくても部分的に基づいて、それらの最適効率実行環境に従いコードレットを配置およびスケジューリングすることと、を含む、方法。
【請求項２４】
ａ）データパーコレーションマネージャ、コードレットスケジューラ、コードレット移動マネージャ、負荷分散手段、電源レギュレータ、または性能マネージャの１つ以上を含む、複数のシステム管理エージェントセットと、
ｂ）複数のコアにおけるプログラム実行を最適化するために相乗的な方法により、前記システム管理エージェントセットを相互作動させる手段と、を備えている、前記複数のコアから成るデータ処理システム。
【請求項２５】
ａ）データ処理システム内の処理資源セットの間で、処理資源のうちのコードレットセットの最適な配置に関連するメトリクスに関する情報を交換する手段と、
ｂ）前記コードレットセットのうちの１つ以上のコードレットを前記処理資源のいずれに位置決めするかを決定する手段と、
ｃ）前記決定に従い、前記１つ以上のコードレットを１つ以上の処理資源にマッピングする手段と、を備えている、前記データ処理システムにおいて前記コードレットセットを最適に位置決めするためのシステム。
【請求項２６】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項１に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項２７】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項１０に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項２８】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項１３に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項２９】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項１８に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項３０】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項２２に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項３１】
コンピュータシステム内に複数のノードを備えており、前記ノードの少なくとも１つにおいて実行されるように設計されており、実行されると、請求項２３に記載の方法に従う動作の実現をもたらすコンピュータプログラムコードをそこに保存するストレージ媒体を備えている、コンピュータプログラム製品。
【請求項３２】
その少なくとも一部が実行されると、請求項１の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体。
【請求項３３】
その少なくとも一部が実行されると、請求項１０の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体を備えている、コンピュータプログラム製品。
【請求項３４】
その少なくとも一部が実行されると、請求項１３の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体。
【請求項３５】
その少なくとも一部が実行されると、請求項１８の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体。
【請求項３６】
その少なくとも一部が実行されると、請求項２２の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体。
【請求項３７】
その少なくとも一部が実行されると、請求項２３の方法に従う動作の実現をもたらす、そこに保存された実行可能プログラムコードを有する、コンピュータ使用可能ストレージ媒体またはネットワークアクセス可能ストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本願は、［１］米国仮特許出願第６１／３２３３６２号（２０１０年４月１３日出願）、［２］米国仮特許出願第６１／３７７０６７号（２０１０年８月２５日出願）、および［３］米国仮特許出願第６１／３８６４７２号（２０１０年９月２５日出願）の利益を主張するものであり、それらの全体は参照により本明細書に組み込まれる。
【０００２】
本発明は、ランスペースと称される、コンピューティングシステム制御、データ処理、およびデータ通信の分野一般に関するものであり、より詳細には、複数の処理要素に分散される、大きい、多くの構成要素のタスクの実行を含む資源効率の良い計算を提供する方法およびシステムに関するものである。
【背景技術】
【０００３】
最新の高性能コンピュータアーキテクチャは、さまざまな程度の非ローカルメモリ、ネットワークの構成要素、およびストレージインフラストラクチャと共に、何万から何百万もの処理要素、大容量の分散型メモリを統合する。これらのシステムは、実行アプリケーションにより消費する資源の静的および動的両方の最適化に関する大きな課題を提起する。従来、コンピュータアーキテクチャは、アプリケーションに、単一かつ単純なアドレス空間を、コードの順次実行およびデータへのアクセスのための直観的に妥当な意味とともに提示するように努めてきた。結果生じたパラダイムは長年首尾よく目的を果たしてきた。しかしながら、これは計算およびデータの両方が分散され、実際上全てのハードウェアの速度向上をクロック速度の改善ではなく並列処理により達成する場合には、最適な資源割り当てに障害となる。本発明は、半導体製造業者が回路規模の縮小に関する物理的なまたは費用効率の限界に近づき、並列処理が性能を向上するための最も有望な手段として残される段階を予期する。既に、最大性能が重要となるアプリケーションでは、インタラプトおよびプリエンプションを通じた従来のＯＳでの資源割り当てにより、性能が低下する。それ故、効率的な分散コンピューティングの達成における主要課題は、物理的システムの最適利用を実現するシステムソフトウェアを提供し、それと同時にアプリケーションコードの作者に、有用な計算の抽象モデルを提供することである。
【発明の概要】
【課題を解決するための手段】
【０００４】
本発明は、資源効率が最高となるプログラム実行の追求を目的とした、コンピュータプログラムをコンパイルおよび起動するためのシステムおよび方法を提供する。これらのシステムおよび方法は、コンパイル時に、コードレットと称される所定のプログラムのセグメントにおける最適効率実行環境を決定することと、ランタイムにおいて、コードレットを、実行におけるそれらの最適効率実行環境に、適宜に配置およびスケジューリングすることとを含む。
【０００５】
本発明の実施形態は、データ処理システム資源をアプリケーションプログラムタスクに効率的に割り当てるための方法を組み込んでいる。そのような方法は、特定のデータ処理タスクを遂行するコードレット群を取得することと、これらのコードレット間の依存関係を決定することと、コードレット間の依存関係、データ処理システムの種々の資源の可用性、およびそれらの相対的な使用コストに基づき、所定のデータ処理システムにおける識別された資源を用いて、実行のためのコードレットを動的に配置およびスケジューリングすることとを含む。
【０００６】
本発明の実施形態に従うさらなる方法は、コンピュータプログラムを実行するためのユーザまたはシステムが定義した目的を追求するために、所定のコンピュータプログラムを抽象モジュールセットに分解することに基づいており、抽象モジュールは、コードレット、協働するコードレットのセット、協働する抽象モジュールのセットおよび所定の抽象モジュールの成員の間で共有されるデータを備える。さらに、種々の実施形態では、これらの方法は、抽象モジュール、プログラムに関連する性能および資源活用に関するプログラムランタイム情報を取得するステップと、プログラムランタイム情報を利用して、コンピュータプログラムまたはその部分の継続中またはその後の起動における、抽象モジュールのその後の配置または実行スケジュールを導くステップとを含む。このような方法のさらなる実施形態は、ランタイムシステムにより少なくとも一部が実現される以下のステップを含む。すなわち、メモリスペースおよび実行時間における、抽象モジュールの成員の近接性についての目標を定義するステップと、最初にデータを配置して、抽象モジュールのコードレットの実行をスケジューリングし、所定のユーザまたはシステムが定義した目的の追求に有益な場合には、抽象モジュール成員を移動させるステップとを含む。そして、この配置および移動は、その定義した目標に基づいて、抽象モジュールの成員間の実際の近接性を最大にするように調整された方法により実行される。
【０００７】
本発明のさらなる態様は以下のステップを含有する、ソフトウェアプログラムの実行を最適に並列化するための方法を含む。すなわち、ａ）ランタイムシステムをクエリして、プログラムの実行に使用可能な処理コアの数量を検出するステップと、ｂ）プログラムを分割可能な、処理ユニットの最大量を決定するステップと、ｃ）ステップａ）およびステップｂ）で決定した量に基づいて、プログラムを、コードレットなどの、最適数およびサイズの処理ユニットに分割するステップと、ｄ）ステップｃ）による分割に従い、プログラムの並列実行を管理するステップとを含む。
【０００８】
本発明の実施形態に従うシステムは、所与のデータ処理ハードウェアにおけるコードレットのセットの実行を最適に配置およびスケジューリングする。このようなシステムは、以下のためのデジタルハードウェアおよびソフトウェアベースの手段を備える。処理資源の中でのコードレットセットの最適な配置に関連するメトリクスに関する情報を処理資源セット間で交換すること、前述のセットの中で、処理資源のうちのどれに、実行するコードレットを配置するかを決定すること、および前述の決定に従い、処理資源を用いてコードレットの実行を配置およびスケジューリングすること。ここで前述の手段の少なくとも一部は、システムランタイム中でも動的に動作する。本発明のさらなる態様は、複数のコアから成るデータ処理システムを含む。このシステムは、ａ）データパーコレーションマネージャ、コードレットスケジューラ、コードレット移動マネージャ、負荷分散手段、電源レギュレータ、および性能マネージャのうちの１つ以上を含むシステム管理エージェントのセットと、ｂ）前述のエージェントセットが、時間変化する、システム全体の目的を追求するための相乗的な方法による処理を行うための手段であって、種々の実施形態においては、動的ランタイムシステム挙動を提供する手段を備えている。
【０００９】
本発明はまた、本発明の方法の種々の組み合わせを実現するためのアプリケーションおよびシステムソフトウェアプログラム、ならびに、このようなプログラムを起動するハードウェアシステム、および関連するハードウェアおよびソフトウェア製品を含む。
【図面の簡単な説明】
【００１０】
【図１】例示のランスペースアーキテクチャを示す図である。
【図２】複数のスコープを有する例示のランスペースの割り当てを示す図である。
【図３】例示のランスペースランタイムシステムを示す図である。
【図４】例示のランタイム性能モニタリングおよび割り当ての事例を示す図である。
【図５】ランスペースシステム内のコードに関するランタイム挙動を例示する図である。
【図６】例示の相互作用の階層を示す図である。
【図７】例示の自己最適化オペレーティングシステムを示す図である。
【図８】明示的および暗示的なアプリケーション指示を例示する図である。
【図９】例示のマイクロメモリ管理ユニットを示す図である。
【図１０】例示のアプリケーション使用事例を描写する図である。
【図１１】経時的な例示のランスペースにおけるグループ分けを描写する図である。
【図１２】コードレットセットを用いたコンピューティングシステムを示す図である。
【図１３】コードレットセット表現システムを示す図である。
【図１４】例示のコードレットセットの変換を示す図である。
【図１５】メタレベルのコードレットセット分配を示す図である。
【図１６】コードレットセット実行および移動を示す図である。
【図１７】両端待ち行列同時アクセス機構、書き込み／キューへの追加を示す図である。
【図１８】キューからの取り出し同時アクセス機構、読み出し／キューからの取り出しを示す図である。
【図１９】アトミック追加配列（Ａ）を介した同時アクセス、書き込みを示す図である。
【図２０】アトミック追加配列（Ｂ）を介した同時アクセス、書き込みを示す図である。
【図２１】アトミック追加配列（Ｃ）を介した同時アクセス、読み出しを示す図である。
【図２２】リンクリスト、特に、アトミック追加配列（Ａ）を示す図である。
【図２３】リンクリスト、特に、アトミック追加配列（Ｂ）を示す図である。
【図２４】リンクリスト、特に、アトミック追加配列（Ｃ）を示す図である。
【図２５】リンクリスト、特に、アトミック追加配列（Ｄ）を示す図である。
【図２６】リンクリスト、特に、アトミック追加配列（Ｅ）を示す図である。
【図２７】順番に共有配列を介する同時アクセスを示す図である。
【図２８】連結ネットワークの分配されたインクリメントを示す図である。
【図２９】アトミック追加配列（Ａ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す図である。
【図３０】アトミック追加配列（Ｂ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す図である。
【図３１】アトミック追加配列（Ｃ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す図である。
【図３２】アトミック追加配列（Ｄ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す図である。
【図３３】アトミック追加配列（Ｅ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す図である。
【図３４】コードレットセット計算システムのシナリオを示す図である。
【図３５】チップレベルにおける例示の一般的アーキテクチャを示す図である。
【図３６】回路基板／システムレベルにおける一般的アーキテクチャを示す図である。
【図３７】コードレットおよびコードレットセットの指示を示す図である。
【図３８】二重バッファ計算（Ａ）を示す図である。
【図３９】二重バッファ計算（Ｂ）を示す図である。
【図４０】二重バッファ計算（Ｃ）を示す図である。
【図４１】二重バッファ計算（Ｄ）を示す図である。
【図４２】二重バッファ計算（Ｅ）を示す図である。
【図４３】二重バッファ計算（Ｆ）を示す図である。
【図４４】二重バッファ計算（Ｇ）を示す図である。
【図４５】ＳＲＡＭおよびＤＲＡＭにおける行列乗算を示す図である。
【図４６】行列乗算二重バッファ／ＤＲＡＭを示す。
【図４７】ＬＩＮＰＡＣＫ  ＤＴＲＳＭ（線形代数関数）計算の例を示す図である。
【図４８】ＤＴＲＳＭに関するコードレットセットのランタイム初期化を示す図である。
【図４９】クイックソートの例を示す図である。
【図５０】アプリケーションコードレットセットが組み入れられたスケーラブルシステム関数を示す図である。
【図５１】レガシーコードの複数タスクへの変換を示す図である。
【図５２】複数タスクコードを利用して起動するブラックボックスコードを示す図である。
【図５３】複数タスクコードを利用して起動する改善したブラックボックスコードを示す図である。
【発明を実施するための形態】
【００１１】
用いられる用語の解説
アプリケーション：ユーザが実行を所望する単数または複数の関連特定タスクを具現化する命令セット。
アプリケーションプログラミングインターフェース（ＡＰＩ）：システムの内部コンポーネントにアクセスできないか、システムの基礎的な機能性を通じて利用可能なものよりも単純またはより一貫したインターフェースを所望し得るか、または、相互運用の特別規格に従うインターフェースを所望し得るアプリケーション開発者により書かれたプログラムによる操作が、システムの機能にアクセスできるようにさせる、プログラマがアクセスできる手順セット。
コードレット：それらの入力が得られた後に、通常、完了するまで連続的に実行可能な命令群。
コードレットセット：依存関係解析または実行に関して、１単位として処理され得るコードレット群。
計算ドメイン：局所性または機能によりグループ分けされる処理要素のセット。これらのドメインは階層的に他の計算ドメインを含み得る。階層ドメインの例は、システム、ノード、ソケット、コアおよび／またはハードウェアスレッドを含み得る。
並行システム：並行プロセス、およびこれらのプロセスにより操作されるオブジェクトのセット。
コア：計算デバイス内の処理ユニット。これは、ＣＰＵ（中央処理装置）、ＧＰＵ（グラフィック処理装置）、ＦＰＧＡ（フィールドゲートプログラマブルアレイ）、またはこれらのサブセットを含む（ただし、これらに限定されない）。
依存関係：一方が開始する前に他方が終了することを示す、２つのコードレットセット間の有向のアーク。
フラクタル調整構造：各レベルにおいて同等の方策を用いて、システム内の複数の尺度において安全かつ確実な資源の有効利用を提供する機構。
ＧＡＣＴ、一般化した動作主：一人のユーザ、ユーザ群、もしくはユーザ群およびソフトウェアエージェント、またはある目的を達成するためにユーザの役割を実行する計算上のエンティティ。
ＧＣＳ、一般化したコンピューティングシステム：データへのアクセスおよびコンピューティングサービスを提供する、プログラマブルプロセッサ、メモリ、Ｉ／Ｏデバイスを備えている１つ以上のコンピュータ。
ＣＳＩＧ、コードレット信号：コードレットの依存関係を充足するか、または状況および完了情報の通信を可能にする、複数のコードレット間、またはモニタリングシステムと少なくとも１つのコードレットとの間の通信。
階層実行モデル：粒度の基準レベルにおいてコードレットを含むいくつかのレベルにアプリケーションが分けられたマルチレベル実行モデル。
線形化：即座に起こり得るように見える、並行処理システムにおける１つ以上の動作。線形化は、典型的には、（群として）成功した、または（押し戻され、）無視された命令により達成されるか、特殊命令を通じた「アトミック」動作、または重大なセクション周囲のロックを提供するシステムにより達成される。
ロックフリー同期化：（少なくとも）システム全体の前進を確実にするための、共有資源の非ブロック同期化。
ローカルエリアネットワーク（ＬＡＮ）：通常では単一組織内における、比較的短距離でのコンピュータおよび他のネットワークデバイスを接続する。
ノード：１つ以上の計算プロセッサ、および任意でメモリ、ネットワーキングインターフェース、並びに周辺機器から成るデバイス。
オーバープロビジョニング：資源配分の自由度をより大きくするために、最低限よりも多い処理要素およびローカルメモリを提供すること。例えば、より速いクロック速度において高度な連続タスクを起動する少数の処理要素を、より遅いクロック速度において、より分散したコードおよびデータを起動するより多くの処理要素に置換する。
複数タスク：計算資源セットに関して単位として処理され得る関連タスク群。典型的には、複数タスク同士は同等の資源需要を有し、資源ブロックの割り当てを求め得る。複数タスク同士はまた、相補的な資源要件を有し得、分散リクエストに基づいて負荷バランシングを実行し得る。
近接性：メモリスペース、計算スペース、または時間または依存完成が近似した状態における局所性。
待ち行列：キューへの追加用の要素を受け入れ、キューからの取り出しにおいてその要素を除去および返却し得るデータ構造。要素は、待ち行列の先端、後端または中間を含む（ただし、これらに限定されない）任意の位置においてキューへの追加またはキューからの取り出しをされ得る。
ランタイムシステム（ＲＴＳ）：コンピュータプログラムの実行を支援するように設計されたソフトウェアの集合。
スケーラビリティ：追加のプロセッサ、メモリおよび接続装置を用いることにより、より大量の処理への需要を効率的に満たすことができるコンピュータシステム、アーキテクチャ、ネットワーク、またはプロセスの能力。
自己認識制御システム：それ自体の性能および制約のモデルを用い、高レベルの目標をモデル属性に関して宣言的に表現可能なシステム。
信号：コードレットセットを有効にするイベント。信号は、実行中にコードレットにより送信され得る。
タスク：ソフトウェアプログラム内における作業の単位。
スレッド：特定の処理要素に制限される長期ランタイム処理オブジェクト。
待機時間無し同期化：システム全体の前進およびスレッドごとの前進の両方を保証する共有資源の非ブロック同期化。
広域ネットワーク（ＷＡＮ）：広い地理的領域でも可能になるコンピュータおよび他のネットワークデバイスを接続する。
【００１２】
本発明は、コードレットセットの表現、操作および実行のための方法およびシステムを提供する。コードレットは、通常は、それらの依存関係が充足された後に、完了するまで連続的に実行可能な、典型的にはノンプリエンプティブ命令群である。コードレットセットは、依存関係解析または実行に関して単位として処理され得るコードレット群である。コードレットセットは、従来のプログラミングおよび実行モデルから顕著な様式で異なる。アプリケーションは、最小限のシステム調整しか必要とせず実行され得るコードの独立したセグメントに分解される。本発明の実施形態に従い、資源の集中制御および割り当てではなく、（コードレットセットを通じて実施される）システムコードは、コードレットセットの最初のコードレットを有効にすることにより、起動するコードレットセットに関するプラットフォームを単に初期化する。これらのコードレットは以前の依存関係を有さず、それ故、コードレットセットが有効化されると直ぐに有効になる。コードレットセットアプリケーションは、それらの実行中、テキストコードスペースとして全体を保持される必要は無い。実際に、あまり用いられないいくつかのコードレットセット要素の変換は、それらが特定の起動、または実行中に提供される特定データのために要求されない場合には、無期限にでも延期することができる。
【００１３】
コードレットセットアプローチの実施形態は以下の特徴を含む。
計算タスクの、モジュール間の依存関係を最小限にする抽象モジュールへの分解。
最初のコードレットの有効化、およびコンピューティング資源の最初のおよび継続した割り当てを導く抽象的依存マップの生成。
ペトリネットと少なくとも同等の表現力を有する計算表現の使用。
ローカルメモリ、特定データおよび中間結果などの資源の局所性、および通信遅延の最小化を目的とした協働コードレットの局所性を活用するための実行中または実行直後のコードレットセットの移動。
より広範囲への資源の配分を可能にし、エネルギ節約または予備容量のために、いくつかの処理資源の低減を可能にするコードレットセットの移動。例えば、異種システムにおける所与の処理タスクのための適した資源の使用。
複数タスク、すなわち計算資源セットに関して単位として処理され得、その群のための必要資源および追加のタスクを得るように動作する代表的プロキシタスクにより管理され得る関連タスクの使用。
アクセス順序が潜在的に重要である場合に、共有データまたは他の処理入力もしくは資源に作用するコードレットのための同時アクセスの効率的な媒体となるアトミック追加配列の使用。
主にローカルアクセスの効率を向上しつつ、並列データ蓄積の実質的に無制限の増大を支援するリンクリストアトミック追加配列の使用。
厳密にローカルなストレージの利益を維持しつつ、多数の継続中動作を支援するマルチターン／マルチジェネレーションアトミック追加配列の使用。
メモリアクセスへの直列による増大を提供し、単一の広範囲における隣の機能の障害を回避する連結ネットワーク。
【００１４】
本発明の重要概念および態様を、図面を参照して以下に記述する。以下の記述では、ステップおよびその順序を説明目的のために提供するが、多くの他の順序、サブセット、およびスーパーセットが、本発明の公開後に実施者に明らかになることに留意されたい。簡潔にする目的のため、本発明の正当な範囲内に収まるステップの全ての組み合わせの列挙はしない。
【００１５】
要旨
ランスペースは、多くの処理要素の高度な並列アーキテクチャを有効利用するように構成され、そこでは、データおよびコード両方が一貫性のあるマルチレベル組織において分散される。ランスペースシステムおよび方法は、コードおよびデータに距離測度が適用される距離空間モデルを維持することにより、処理資源の最適利用を実現する。タスク割り当ての細かいレベルは、入力条件の充足後に完了するまでノンプリエンプティブで実行され得る命令群であるコードレットのレベルである。
【００１６】
本発明の実施形態では、ランスペース方法およびシステムは、以下のうちの１つ以上を実行することにより、コンピューティング資源を計算タスクに割り当てる。タスクのセットを達成するコードレットセットを取得すること、コードレットにより要求されるデータの仕様セットを取得すること、コードレットおよびそれらがアクセスするデータの局所性を表す距離空間を構築すること、距離空間に関して、コードレットにおいて静的に定義された初期配置を取得すること、コードレットまたはデータの初期配置のために距離空間表現を使用すること、コードレットおよびデータに関する、動的に利用可能なランタイム資源要求を取得すること、およびコードレットまたはデータを動的に配置または移動するために、距離空間表現を使用すること。
【００１７】
さらに、実施形態では、ランスペースは割り当ての機会を用意し、ランタイムにおいてこれらの機会を有効利用する。これは、コンパイル時に動作のための潜在的コードおよびデータ割り当てを解析し、かつコードレットおよびデータを結合または移動するための機会を示す参照を解析し、次に、実際のコードおよびデータ割り当てにより示される機会を用いて、これらのコードレット、結合コードレット、またはデータのランタイムでの移動を実行する。
【００１８】
また、コードレットの非常に細かい実行を支援するために、ランスペースの実施形態は、以下の１つ以上を実行することにより、安全かつ効率的な局部的なメモリアクセスを提供する。アプリケーションコードをコードレットへ分解すること、論理および物理アドレスを含むローカルテーブルを提供すること、関連コードレットの別々の群の物理アドレスを別々のアドレス空間にマッピングし、別々のアドレス空間はそれぞれ、それらの関連コードレットの別々の群にアクセス可能となるようにすること、および、所与の別個のコードレットの群の、その別個のアドレス空間外のスペースへのいかなるアクセスもエラーとして扱うこと、の１つ以上を実行する。
【００１９】
本発明は、コードレットセットの表現、操作および実行のための方法およびシステムをさらに提供する。コードレットセットは、依存関係解析または実行に関して単位として処理され得るコードレットの群である。コードレットセットは、分散アプリケーションを開発および実行するための機構、ならびにアプリケーションの構成能力を提供するための機構を提供する。コードレットセットは、階層的に構成され、再利用され得るものを含み得る。コードレットは、それらが依存関係を充足するとすぐプリエンプション無しで完了するまで動作し得るが、さらに、プリエンプティブシステムにおいても起動し得る。すなわち、ノンプリエンプティブマルチコアアーキテクチャをシミュレートして起動するか、プリエンプティブ計算のいくつかの他の属性がコードレットセットにより表される分散アプリケーションに所望されるために起動する。さらに、コア親和性およびプロセスの優先順位などのプリエンプションを最小化するための暗示が、プリエンプティブＯＳに与えられ得る。このようにして、コードレットのランスペースは、現用のコンピュータシステムにおいて他のレガシーアプリケーションと共存できる。
【００２０】
本発明の実施形態に従い、資源の集中制御および割り当てではなく、（コードレットセットを通じて実施される）システムコードは、コードレットセットの最初のルーティンを有効にすることにより、起動するコードレットセットに関するプラットフォームを単に初期化する。本発明に従い、アプリケーションプログラムは、最小限のシステム調整で実行され得るコードの独立セグメントに分解される。
【００２１】
システム利用および管理の要旨
より詳細を以下に記述するような本発明の実施形態では、ランスペース実行モデルが、システム利用およびモニタリングに関する全てのレベルを利用できる。実行モデルは、非常に細かいレベルにおいて、一連のコードレットおよびそのそれぞれの依存関係を提供する。コードレットの非常に細かい性質により、ランタイムシステムは、資源を効率的に割り当て可能になり、その上、性能および消費電力を動的にモニタリングして、アプリケーションの性能および電力需要に合うスケジュール変更を行うことまたはそれを有効にすることができる。
【００２２】
ランスペースシステムは、利用可能資源を所与のアプリケーションに割り当て、ディスク、周辺機器、他のノードのメモリなどの外部資源にアクセスするためのＡＰＩを提供する。アプリケーションのドメイン（すなわち、アプリケーションにより使用可能なノード）は、ハイパーバイザによって定義される。コードレットの非常に細かい性質により、ランタイムシステムは、資源を効率的に割り当て可能になり、その上、性能および消費電力を動的にモニタリングして、アプリケーションおよびシステムの性能および電力の目標に合うスケジュール変更が可能になる。
【００２３】
図１に示すような、本発明の実施形態に従うシステム１０１は、例示のランスペースアーキテクチャにおいて、１０１でのシステム利用および管理に用いる５つの構成要素を備えている。すなわち、（１）ファイルシステムを長期で共有するための、アプリケーションを起動する従来のオペレーティングシステム（ＯＳ）、（２）大雑把なレベルにおいてシステムの資源割り当てを制御するハイパーバイザ、（３）外部資源を管理するマイクロＯＳ、（４）タスクを同期化し、エネルギ消費および性能を管理するランタイムシステム、および（５）マイクロＯＳの移植性を提供し、新規の周辺機器へのアクセスを可能にするハードウェア抽象層を備えている。このような実施形態に従い、スレッド仮想マシン（ＴＶＭ）が従来のＯＳに取って代わり、ハードウェアへのダイレクトアクセスおよびコードレット間の非常に細かい同期化を提供する。ＴＶＭは、本明細書では分離した構成要素としては考慮されず、むしろ、ランタイムシステムおよびマイクロＯＳによって実現される。
【００２４】
図１に、構成要素間全体の相互動作を示す。
【００２５】
ハイパーバイザ
ハイパーバイザは、所与のアプリケーションのための広範囲の資源を、ユーザのパラメータおよび任意でアプリケーションにおいて特定されたパラメータに基づいて割り当てる。このパラメータには、使用すべきノード数が含まれ、特定の実施形態では、ノードの連結性も含まれる。ハイパーバイザは、アプリケーションドメインを設定し、各ノードにおいて起動するマイクロＯＳを定義する。次に、ハイパーバイザは、アプリケーション固有のパラメータ（コマンドライン引数、環境変数など）をロードし、ランタイムシステムにアプリケーションの起動を命令する。ランタイムシステムは、主プログラム開始ポインタにおいて開始して、コアにおいて１つ以上のコードレットを起動することにより、ユーザアプリケーションを開始する。ユーザアプリケーションは、ランタイムにおいてより多くのコードレットが生じるように要求できる。さらに、ユーザアプリケーションは、タスク同期化のためにランタイムシステムと直接に相互動作する。全ての外部Ｉ／Ｏは、直列コンジットを通じた通路（ディスクＩ／Ｏ、イーサネット（登録商標）、ノード間通信など）のためのリクエストおよび応答を順番に並べるマイクロＯＳによって媒介される。さらに、マイクロＯＳは、ランタイムシステムと、他のランタイムシステム構成要素に繋がるノードとの通信を促進する。ハードウェア抽象層は、マイクロＯＳと他のプラットフォームとの移植性、および新規の周辺機器の検出を促進する共通ＡＰＩを備えている。
【００２６】
次の段落では、システム利用および保守に関与する、種々の構成要素の全体構造および機能性の概略を記述する。
【００２７】
スレッド仮想マシン（ＴＶＭ）
ＴＶＭは、作業を、コードレットと呼ばれる小さなノンプリエンプティブブロックに分割し、それらをランタイムにおいて効率的にスケジューリングするフレームワークを備える。ＴＶＭは、ＯＳを、ハードウェアに直接にインターフェース接続可能なシステムソフトウェアの薄層に置き換え、概してアプリケーションプログラマを、アーキテクチャの複雑性から解放する。従来のＯＳとは異なり、ＴＶＭでは、性能の達成に重要な資源を表に出すことができる。
【００２８】
ＴＶＭの実施形態を図２に示す。ＴＶＭは、任意の制御フロー、データ依存関係、または同期化条件を、ランタイムにおいてコードレット機構に分解可能な統合されたデータ非巡回グラフ（ＤＡＧ）に抽象化する。このＤＡＧの上部において、ＴＶＭはまた、概念範囲を用いてプログラムの局所性を表す追加ＤＡＧに重ね合わせる。本発明の実施形態では、コードレットは、親レベル（例えば、２０１）において形成された任意の変数または状態にアクセスし得るが、兄弟レベル（例えば、２０２と２０３または２０４と２０５）は、それぞれ、他のメモリスペースにアクセスできない。この範囲を利用して、コンパイラおよびランタイムは、所与のグラフに関する、適切な作業セットおよび利用可能な並行処理を決定できる。これにより、ランタイムは、コードレットの実行およびモデルを最適化する出力を用いて、システム状態または範囲変数のパーコレーションの両方に資源をスケジュールし、相性および負荷バランシング特性を設定できる。
【００２９】
従来のＯＳのフレームワークとは異なり、ＴＶＭは、フラクタルの意味構造を維持し、タスクを最適に実行するためにスケジューリングおよびパーコレート制御をランタイムにおいて与える。このフラクタル性によって、使用可能プログラミングモデルは、十分な情報をランタイムシステムに提供できる。それ故、予測し得ないかつ単純なキャッシング機構を備えたモノリシックスレッドとは異なり、粒度およびランタイムオーバーヘッドは、より優れた電力効率をもたらすたように、静的および動的両方の性質において可能な限り高度に管理される。
【００３０】
ランタイムシステム
ランタイムシステムは、ソフトウェアではユーザライブラリとして、およびハードウェアではランタイムシステムコアにより実現され、多くの実行コアによって使用できるようにされる。実施形態では、このランタイムシステムコアは、実行コアと異なるものでもよく、より効率的なランタイム動作を促進するための特殊ハードウェアを有し得る。実施形態では、実行コアはランタイムシステムタスクを実行し得、ランタイムシステムタスク実行に専用のコアであってもよいし、そうでなくてもよい。
【００３１】
本発明の実施形態に従う動的ランタイムシステムの設定および実行は、データ処理資源をデータ処理タスクに最適に割り当てる方法を含む。このような方法は、コンパイル時において、可能性のあるコードおよびデータの割り当て、配置および移動を解析し、ランタイムにおいて、実際のコードおよびデータ割り当てにより示される機会を用いて、コードレットまたはデータを配置または移動することを含む。これに加えて特定の実施形態では、あるロケールから１つ以上のコードレットの移動が予期される別のロケールに少なくとも一部のデータをコピーし、コードレットを、さもなければ十分に活用されていないプロセッサに移動することを含む。
【００３２】
本発明の実施形態は、システム内にコードレットセットを最適に配置するための、ハードウェアおよびソフトウェアから成るデータ処理システムを含む。このようなシステムの要素は、以下の処理を実行するためのデジタルハードウェアまたはソフトウェアベースの手段を備える。（ｉ）処理資源のうちのコードレットセットの最適な配置に関連するメトリクスに関する、システム内の処理資源セット間で情報を交換すること、（ｉｉ）前述のコードレットセットのうちの１つ以上のコードレットをどの処理資源に配置するかを決定すること、および（ｉｉｉ）前述の決定に従い、１つ以上のコードレットを１つ以上の処理資源にマッピングすること。種々の実施形態では、マッピングは、準最適なデータ局所性によりトリガされるデータおよび／またはコードレットの移動を含み得る。特定のシナリオでは、移動コストに従い大量のコードレットおよびデータを移動する。実施形態では、移動コストドライバは、移動するデータまたはコード量、移動距離、同期化のオーバーヘッド、メモリ帯域幅利用性および可用性の１つ以上を含む。
【００３３】
ランタイムシステムは、コードレットに関する最適効率環境を特定する、コンパイル時の注釈または最新または以前の実行からの注釈を利用することができる。本発明の実施形態の関連方法は、資源効率が最高となるプログラム実行の追求を目的とした、コンピュータプログラムのコンパイルおよび起動を含む。このような方法は、プログラムコンパイル時において、コードレットと称されるプログラムの部分における最適効率実行環境を決定し、それに応じて、プログラムランタイムにおいて、それらの最適効率実行環境において実行するコードレットを配置することを含む。さらに、特定の実施形態では、最適環境の決定は、以下のようなプログラムソースコードにおける指示に基づいて行われる。（ｉ）コンパイラ指示文、（ｉｉ）関数の呼び出し（呼び出される関数のタイプが、その関数における最適な実行環境に関する情報を提供する）（ｉｉｉ）正常進行、作業セット、浮動小数点利用などの特定の特性を有するループ本体（最適な実行環境は、類似のデータ処理プラットフォームにおける類似のループのシステム的な起動により予め決定されている）。所与のコードレットの実行における最適効率実行環境は、以下のような基準によって定義され得る。消費電力、処理ハードウェア資源の利用、完了時間、所与の消費電力予算における最短完了時間。
【００３４】
内部ハードウェア／ソフトウェアランタイムスタック
例えば、図３に示すシステム３００の本発明の実施形態では、ランタイムシステムコア３０１は、イベントプールストレージ３０２と共に設置される。実施形態では、ランタイムシステムのタスクは、専用ランタイムシステムコアにおいて、または代替的に、実行コアにより動作し得る。イベントプール３０２は、アプリケーションおよびシステム目標（性能または出力ターゲットなど）、並びにデータ有用性イベントを起動するための非常に細かいコードレットを含む。イベントプール３０２は、リストなどの実際の共有データ構造、または資源活用が変化した際に（例えば、待ち行列が空き領域を有している場合に処理要素が作業に利用可能であるか、相互排除ロックが利用可能であるときに）、呼び出されるコールバックのシステムなどの分布構造でもよい。ランタイムシステムコア３０１は、イベントプール３０２内のイベントに応答する。本発明の実施形態に従うと、ランタイムシステムコア３０１上で起動する５つのマネージャがある。すなわち、（１）データパーコレーションマネージャ、（２）コードレットスケジューラ、（３）コードレットセット移動マネージャ、（４）負荷分散手段、および（５）ランタイムパフォーマンスモニタ／レギュレータがある。特定の実施形態では、これらのマネージャは、近接して動作し、ランタイム状態を共有することにより相乗的に動作する。例示的な一実施形態のランタイムシステムコア３０１において起動するマネージャの入力、出力および相互作用４０１を図４に示す。適切であるとみなされると、データパーコレーションマネージャは、データ依存関係（すなわち、利用可能な場合にはプリフェッチ入力データ）、およびコード依存関係（すなわち、プリフェッチ命令キャッシュ）をパーコレートする。全ての入力依存の要求が満たされると、コードレットスケジューラは、作業待ち行列にコードレットを配置し、特定のシナリオでは、待ち行列での実行できるコードレットの優先度を並べ替える。実行コアは、連続して作業待ち行列からタスクを取得し、それらを起動して完了する。コードレットを起動する過程において、実行コアはコードレットまたはスレッドを作成し、それらをイベントプールに配置し得る。ランタイムパフォーマンスモニタ／レギュレータは、実行コアの消費電力および性能をモニタする。そして、消費電力の低減（例えば、コアの周波数および／または電圧の低減、コアの停止、または作業待ち行列からチップ上の他の計算ドメインへの一部または全ての仕事の移動およびコアの停止）、または性能の向上（例えば、周波数および／または電圧の増大、コアの起動、他の計算ドメインからのより多くの仕事の採用、または種々の計算ドメインの起動およびそれらのアプリケーションへの加入）のための調節を行うことができる。負荷分散手段は、作業待ち行列およびイベントプールを解析し、作業を局所的に（すなわち、この計算ドメイン内において）行うべきか、別の場所に移動するべきかを決定する。コードレット移動マネージャは、ノードおよび遠隔ノードにおける他のランタイムシステムコアと連携し、コードレットセットのための最適なあて先を見出し、それらを適切に移動する。コードレット移動は、データ局所性が乏しくてもトリガされ得る。コードレットセットの多くのコードレットが別のノードに存在するデータを要求する場合には、データではなくコードを再配置することが好ましい。
【００３５】
これらのマネージャはまた、相乗的な方法により共に通信することにより、例えば、所定の消費電力予算に対する完了時間の最短化などの相互利益となる目的を達成する。例えば、性能マネージャが電力低下の抑制を所望し、負荷分散手段がより多くの作業の局所への移動を所望する場合には、２つのマネージャを、１つのＲＴＳコア手段上に一緒に配置することは、これらのマネージャが、それらの双方の目的のための最善の方策において同時に互いに通信し、迅速に決定的な決断をすることができることを意味する。それ故、これらのサブシステムは、性能の内部モデルを構築し、一般的な動作主（ＧＡＣＴ）の目的に基づいた設定点を達成する制御アーキテクチャを提供する。本システムの目的は、ＧＡＣＴの制約により制限されるエネルギ比率を考慮した方法において、最小の消費電力で最高の性能を提供することにある。本発明の実施形態では、これらの機能はランタイムシステムコアが、負荷および電力インジケータを送信し、目標ターゲットを受信することにより、マスターランタイムシステムコアと非同期的に通信することに依存する。マスターランタイムシステムコアの仕事は、チップ上の所定のアプリケーションの全体的性能／電力プロファイルをモニタし、各計算ドメインの性能（個々のコアの周波数、電圧、およびオン／オフ状態を含み得る）を適切に調整することである。
【００３６】
アプリケーションに割り当てられた各ノードのマスターランタイムシステムコアは、いわゆるアプリケーションのためのヘッドノードのマスターランタイムシステムコアと非同期的に通信し、完了までの時間、消費電力、および最大資源制約（例えば、メモリスペース、ノード、ネットワークリンクなど）などの性能メトリクスおよび目標ターゲットを通信する。ランタイムシステムハードウェアの階層およびフラクタル調整構造は、実行モデルの階層的性質を反映する。全体として、アプリケーションを起動するノードのマスターランタイムシステムコアは、共同で、ハイパーバイザセクションにおいて後述するようなハイパーバイザタスクを実行する。ランタイムシステムは互いに通信し、システムが全体として自己認識するように、フィードバック（例えば、ローカルランタイムコアが、作業負荷が低いことを決定し、それをマスターランタイムコアに通知し、より多くの作業を受ける）を提供する。
【００３７】
自己認識オペレーティングシステムの実施形態では、モニタリングドメインのフラクタル階層ネットワークが、データ処理システムの調整を実行する。例えば、基本クラスタでは、ドメインは、クラスタ、ノード、ソケット、コア、ハードウェアスレッドでもよい。各リーフドメインにおける（スケジューラでもよい）処理は、ハードウェアおよびアプリケーションの健康状態（例えば、消費電力、負荷、プログラムの進捗度など）をモニタする。階層内のより高レベルのモニタが、それらの子ドメインから情報を収集し（さらに、それらのドメインに情報を選択的に追加するか、全てのモニタリングを子ドメインが実行することを要求し得る）、その情報をそれらの親ドメインまで伝える。ハードウェアの構成要素が機能しない場合には、それはチェーンに通知される。階層の任意のレベルにおいて、機能不全のハードウェアにおいて起動するコードレットの再開を選択するか、チェーンに伝達し得る。レベルにおいてコードレットの再開が選択されると、それはタスクの実行をその子ドメインに委任する。有効にされたコードレットもまた、この方法で移動され得る。レベルにおいて、その待ち行列の満杯、または電力消費の過多が検出された場合には、それは前述と同じ方法で有効なコードレットを移動できる。最終的に、レベルにおいて、作業が少なすぎることが検出された場合には、その親ドメインから作業をリクエストし、適切なドナーが検出されるまで、このリクエストをチェーンに送信し得る。
【００３８】
ランタイムシステムユーザＡＰＩ
コードレットは追加コードレットを作成できる。この作成は、ランタイムライブラリコールを呼び出し、その追加コードレットのデータ依存、引数、およびプログラムカウンタを定義することにより行われる。同期化は、データ依存または制御依存を通じて実現され得る。例えば、境界の実装は、変数との、その境界を共有している動作主の数との等価性に応じて決まるコードレットを発生させることにより行われる（図５参照）。共有コードレット各々は、境界変数に１をアトミックに追加する。相互排除も同様の方法により実施され得る。すなわち、重大なセクションを有するコードレットは、データ依存として取得した相互排除ロックを利用し、完了したら、このロックを解放する。ただし、重大なセクションが短い場合に、特定のシナリオ（デッドロックが無く、ロックが空間的にローカルメモリ内にある場合）では、ロックに対して少し待機することが、コアにとってより生産的となり得る。最終的に、（ローカルメモリコントローラにより管理される）メモリ内のアトミック操作により、待ち行列項目の比較および交換、インクリメント／デクリメントのためのアトミック追加などの、多くの種類の暗示的な非ブロック同期化が可能になる。
【００３９】
マイクロＯＳ
マイクロＯＳは、ノード外資源、およびノード境界におけるセキュリティを提供する。本発明の実施形態では、マイクロＯＳは２つの構成要素を有する。すなわち、（１）実行コアにおいて起動する特別コードレット、および（２）ユーザコードレットがシステムコール（シスコール）を通じて呼び出すライブラリ関数を有する。特別コードレットは、イベントベースの割り込み駆動実行、またはシリアルデバイスの非同期ポーリング、およびデータの待ち行列への配置に用いられる。典型的デバイスは、イーサネット（登録商標）、そのノードと他のノードとを接続するスイッチのポート、および（場合によっては、ディスクＩ／Ｏからの非同期の応答）入力が要求されない他のソースを含む。コードレットはさらに、ＴＣＰ／ＩＰなどの信頼性のある通信プロトコルにおける再送動作などのタイミングイベント用に確保されてもよい。これらのコードレットは送り手および受け手を解析し、ノードを所有するアプリケーションが属する特定ソースが、確実に、ノード上のソース、またはアプリケーションに専用の資源（例えば、ディスク上のスクラッチスペース）にアクセスできるようにする。共有資源（例えば、グローバルファイルシステム）へのアクセスの認証は、ユーザ、複数タスク、役割、または性能アクセスレベルなどの手段を通じて行われる。
【００４０】
ライブラリ関数により、ユーザアプリケーションは、介入または追加のスケジューリングが無しで、ハードウェアに直接アクセスできる。これらの機能の一部は、ハードウェア（例えば、ＬＡＮ、ノード間、またはディスク書き込み）において直接実現され得る。他の機能は、別のノードからのディスクアクセスのリクエストなどの、非同期入力ポーリングスレッドからバッファを通じたデータを直接に送信および受信するための下位レベルのサポートを用いる。ライブラリコールは、ユーザに、そのアプリケーションに割り当てられたデータへのアクセスを与える。ユーザまたはシステムライブラリは、応答への待機をブロック（例えば、直ぐに戻ってくることが分かっている）するか、またはその結果に依存するデータを用いて起動するコードレットをスケジューリングするかを特定することができる。
【００４１】
ライブラリ関数は、ランタイムシステムと堅く連結することにより、エネルギ効率が良く、待ち時間を隠すように設計される。例えば、システムファイル読み出しを呼び出すコードレットは、ファイルシステムリクエストを発行し、ファイルシステム応答上でデータ依存性を有する応答を処理するコードレットを生成し、終了する。これにより、実行コアは、データ送信中（その代わりに、Ｉ／Ｏが待ち状態に静止中）に、他のコードレットにおいて動作可能になる。十分な並行処理がない場合には、ランタイムシステムは、コアを停止するか、コアの周波数を低減することにより、待ち時間が長い読み出し操作に直面した場合に計算を遅くすることができる。
【００４２】
本発明の実施形態では、２つのモードでセキュリティを提供する。すなわち、１つのアプリケーションがノード全体を所有する場合の高性能計算（ＨＰＣ）モードと、複数のアプリケーションが１つのノードに共存し得る非ＨＰＣモードとがある。ＨＰＣモードでは、通常、ノード境界においてセキュリティが実行されることで十分である（すなわち、オンチップアクセスは、カーネル／ユーザメモリスペースおよび読み出し専用メモリ以外では確認されない）。さらに、ユーザアプリケーションが、それらのアプリケーションにおけるノードの論理マッピング（すなわち、ノード０〜Ｎ−ｌ（Ｎはアプリケーションにおけるノード数））を認識ことで十分である。マイクロＯＳは、論理ノードＩＤに対するノードＩＤの物理的マッピングを認識し、必要に応じてアドレスを再書き込みする。また、マイクロＯＳがノード境界外部からの入力を取得した場合には、そのデータがそのノードに関するものであることを検証する。それ故、オンチップセキュリティは、ユーザコードからのカーネルコードの保護、および書き込みからのユーザの読み出し専用メモリの保護を含む。非ＨＰＣモードでは、マイクロＯＳは、ノードの外部の周辺機器との通信を許可するが、通常、他のノードとは通信させない。入力も同じ方法で認証される。ハイパーバイザセクションに記述するように、ハイパーバイザにより設定されるさらなるセキュリティがハードウェアにより実行される。セキュリティは、大雑把なアプリケーションレベルにおいて実行されてもよいし、非常に細かいコードレットレベルにおいて実行されてもよい。コードレットレベルでは、データ依存関係およびデータブロックのサイズがランタイムにおいて知られているので、セキュリティは、（Ｍマシンに用いられるなどの）保護ポインタを利用してハードウェアによって、またはデータオブジェクト周囲の（プロポリスまたはスタックガードにおいて用いられる）無効ページまたはカナリアを利用したソフトウェアにより保証され得る。
【００４３】
ハイパーバイザ
ハイパーバイザは、ユーザアプリケーションへの資源の割り当てを管理する。本発明の実施形態では、これは全てのノード、およびホストシステムの一部にも物理的に存在する。各チップにおける１つ以上のコードレットセットがハイパーバイザ機能に対して利用可能である。これらは、ランタイムシステムコアおよび実行コアに存在し、通常、システムの残りの部分と同一の非常に細かい実行モデルに従う。ホストソフトウェアにおけるハイパーバイザの実施形態は、システム内の全てのアプリケーションに割り当てされる全ての資源の状態を維持する。アプリケーションが起動すると、一般化した動作主（ＧＡＣＴ）は、ノード数、並びに電力および性能ターゲットなどの実行環境変数セットを特定できる。ハイパーバイザは、アプリケーションスペース内のノードが隣接し、好ましくはＧＡＣＴのアプリケーション要求に合致するように、システム内にアプリケーションを配置し、資源を割り当てる。ノードセットが割り当てられると、ホストハイパーバイザは、ノードを割り当てるためにノード各々におけるハイパーバイザインスタンスと通信し、アプリケーションコードイメージおよび（存在する場合には電力および性能ターゲットを含む）ユーザ環境を伝え、アプリケーションを開始する信号をランタイムシステムに送信する。ハイパーバイザは、アプリケーションに割り当てられた資源についてマイクロＯＳおよびランタイムシステムに通知する。次に、ノードにおけるハイパーバイザインスタンスは、アプリケーション性能をモニタし、アプリケーションに割り当てられた他のノードにおける他のハイパーバイザインスタンスおよびランタイムシステムコアの両方と連携し、電力および性能目標を実現する。この目標は、電力、性能、セキュリティ、および回復機能の関係性を管理することにより達成され、これにより、エネルギ比例ランタイム電力予算を維持する（全体システム、ハイパーバイザ、およびランタイムシステム相互作用の階層６０１を示す図６参照）。マイクロＯＳスレッドおよびライブラリは、アプリケーションに割り当てられた全てのノードにおけるアプリケーションデータおよび環境に関するセキュリティを提供する。
【００４４】
複数のアプリケーションが１つのノードに共存し得る非ＨＰＣモードでは、ハイパーバイザはコアセットから計算ドメインを作成する。アプリケーションごとにＲＡＭが区分され、ユーザアプリケーションは、各他のアプリケーションのＤＲＡＭまたはオンチップＳＲＡＭに書き込みできない。これは、電力効率のための基本のメモリ管理ユニット（ＭＭＵ）、またはレガシーマシンにおける汎用仮想メモリマネージャ（ＶＭＭ）を用いて達成され得る。ハイパーバイザは、アプリケーション起動フェーズ中に、アドレスプレフィックスおよび各セグメントのサイズを決定する。そして、アプリケーションアドレスは、ＭＭＵによって、アプリケーション実行中に再書き込みされ得る。通常、アプリケーションのメモリスペースにマッピングされるアドレスは、この方法によりアクセスされ得る。
【００４５】
ハードウェア抽象層
ハードウェア抽象層（ＨＡＬ）により、マイクロＯＳおよびユーザアプリケーションは、ハードウェアデバイスの可用性をクエリし、一律の方法でハードウェアと相互動作できる。デバイスは、実行コア、ディスク、ネットワークインターフェース、他のノードなどでもよい。システムの大部分は、ファイル記述子を利用することにより、ユーザアプリケーションによりアクセスされ得る。開く、読み出す、書き込む、および閉じるなどのマイクロＯＳのライブラリ関数の呼出しは、アプリケーションに基本ハードウェア抽象層を提供する。ドライバは、一連のメモリ読み出しおよび書き込みでＨＡＬと相互動作する。ＨＡＬの実装により、これらの要求が、ハードウェアプラットフォームに適切なバストランザクションに変換される。これにより、ユーザは、種々の基礎プラットフォームにドライバコードを再利用できる。
【００４６】
アプリケーションはさらに、アプリケーションに利用可能なノード数、チップ内の実行コア数、およびメモリ有用性に関してハードウェアまたはランタイムシステムをクエリし得、これは問題を分割する方法の決定を支援する。例えば、一千個のコアが存在する場合には、アプリケーションは、百万の反復ループを、一千の反復コードレットに分割できる。それに対して、コアが４つしかない場合には、ハードウェアから得られる並行処理がもはや無く、より少数のコードレットのオーバーヘッドがより低いため、その作業を、より粒度の粗いブロックに分割できる。種々の実施形態では、ブロックの最適サイズは、例えば、（１）並行して行うことのできる作業単位の最大数を、アプリケーションに利用可能な処理要素の数量で除して丸めた整数の商、（２）最小ブロックサイズと最大ブロックサイズとの最大差異が最小となるようなブロック間の可変サイズ、または（３）与えられた消費電力予算内に収まる、与えられた時間予算において、アプリケーションのセグメントを完了可能な最大サイズであり得る。
【００４７】
自己最適化オペレーティングシステム
オペレーティングシステムサービスは、マイクロＯＳおよびランタイムシステムにより実行され、ハイパーバイザを通じて管理される。これらの構成要素は、共に、図７に示す実施形態の例示の自己認識オペレーティングシステム７０１を構成する。ランタイムシステムの自己最適化の性質は、（１）実行システムの自己認識特徴、（２）ＯＳの自己認識特徴、（３）（１）と（２）との相互作用によって実現される。図７に示すように、ＯＳ、ハイパーバイザ、ランタイムシステム、および実行ユニットは、それらの隣接レベルにおいて互いに通信し、観測−決定−制御ループにおけるフィードバックを与える。
【００４８】
このセクションでは、自己最適化システムモデル７０１の実施形態を記述する。
（１）実行システムに組み込まれた自己最適化ループ。実行モデルの実施形態では、２種類のコードレット、すなわち、非同期タスクおよびデータフローコードレットが特徴付けられる。どちらの種類でも、対応するコードレット活動の呼び出しはイベント駆動型である。少なくとも非同期タスクの場合には、コードレットの起動はさらに、タスクが割り当てされ得る特定の物理ドメインにおける計算負荷、エネルギ消費、エラー率、または他の条件に応じて決定され得る。自己最適化は、性能認識モニタリング認識および適応などにも適用され得る。
（２）オペレーティングシステムに組み込まれた自己最適化ループ。自己最適化ＯＳはそれ自体を観察し、その動作に反映し、適応する。それは目的指向型であり、理想的には、システムのクライアントにとっては目的を特定することだけで十分であり、その目的をどのように達成するかを見出すのはシステムの仕事である。このような自己最適化機能を支援するために、ＯＳオブザーバエージェント（すなわち、ランタイムシステムコアおよびハイパーバイザ）は、実施形態では、性能モニタ機能およびエネルギ効率モニタ機能を備えている。性能モニタ機能は、プログラム実行およびシステム資源活用の全ての局面を観察するようにプログラムされ得、エネルギ効率モニタ機能は、ＯＳの要求により、種々の時間間隔または特定のロケーション／ドメインでシステム電力条件を観察できる。
【００４９】
実施形態では、ＯＳ決定エージェント（ランタイムシステムコアにおいて起動するコード）は、適切なモデルビルダおよび学習能力を備えている。このため、これは適時に自己補正のために有効動作し、目標を達成するように適応できる。一部の実施形態では、ＯＳ自己最適化ループは、その目標を達成するための制御理論方法を呼び出すことができる。（１）と（２）との相互作用を図７に示す。ＯＳ内の制御ループと各実行システム内の制御ループとが接続する。ＯＳ制御ループは、実行システムに、それらの起動状況、資源活用、エネルギ効率、およびエラー状態に関して問い合わせることができる。これにより、システムレベルでの包括的制御および調節の実行に関して、これらの情報に基づき決定することができる。同時に、個々の実行システムは、それ自体の制御に関する問題を解決するための援助をＯＳに要求し、この援助によりＯＳレベルにおいてより最適に問題を解決できる。
【００５０】
ランスペースシステムおよび方法を効率的に使用するために、アプリケーション開発者は、コンパイル時においてシステムが認識し、改善された初期静的割り当て、ランタイム（動的）における割り当ての向上、またはその両方をもたらす指示を与えることができる。図８に、Ｃ言語における明示的な言語要素（８０１）を示す。この言語により、アプリケーションプログラマは、システムに、コードが極めて低電力で遅く実行ユニットに移動し得ることを示し得る「資源ストール」を警告する。指示８０２に暗示的な指示を示す。この指示では、特別ＡＰＩ呼び出しは忠実度が低い浮動小数点演算を用いる。このような演算は、ごく少数の仮数ビットを用いた浮動小数点演算ユニットにおいて安価に実行され得る。これにより、優れた特殊性を可能にし、それ故、システムの計算ドメインにおいて要求される性能により良く一致する。これらは、ランタイムが動的決定に用いることができるユーザ指定の指示のいくつかの例である。さらに、アプリケーションはプロファイルされ、指示を含む注釈を付けられ得る。これにより、ランタイムは、注釈が提供する暗示に基づいて、その後の起動においてより優れた動的決定を実現できる。
【００５１】
例示のマイクロメモリ管理ユニットを図９に示す。参照番号９０１は、局所コード実行および４個の局部物理メモリブロックを備えた処理ユニットである。参照番号９０２および９０３は、同一の制御タスクである所有者Ｘが所有する２つのメモリブロックであり、そのタスクに関連するコードレットによりアクセス可能である。９０２は論理アドレス００および物理アドレス００を有し、９０３は物理アドレス１０および論理アドレスＬ０１を有する。参照番号９０４は、Ｌ０１の域を越えたメモリアクセスが、Ｘが所有するコードレットにどのように表示されるかを示す。つまり、Ｌ０２の域を越えた任意のローカル論理アドレスは、Ｘが所有するコードレットにエラーとして表示される。参照番号９０５は、物理的な位置０１に存在するメモリセグメントを示し、これは、Ｙが所有するコードレットにＬ００として論理的に表示される。他の全ての局部物理メモリはＹコードレットによりアクセスできない。参照番号９０６は、物理位置１１に存在するメモリセグメントを示し、これは、Ｚが所有するコードレットにＬ００として論理的に表示される。全ての他の局部物理メモリは、Ｚコードレットによりアクセスできない。
【００５２】
図１０に、ランスペースシステムが関与する単純な使用事例を示す。そこでは、汎用エージェント１００１が、（典型的には、ソースコードをコンパイルすることにより）タスクを指定し、アプリケーション１００３を起動し、結果１００４を得る。同時に、別のＧＡＣＴ１００５が、モニタリングおよびシステム保守１００６を実行する。典型的環境では、ランスペースシステムは、ローカルエリアネットワーク（ＬＡＮ）および／または広域ネットワーク（ＷＡＮ）１００７を通じて利用可能とされ、従来のフロントエンドサーバ１００８との相互動作により処理され、フロントエンドサーバはハイエンドコンピュータ（ＨＥＣ）１００９と通信する。
【００５３】
図１１に、ランスペースにおいて観察されるコードおよびデータ局所性の例をコードレットおよびデータの経時の割り当てと共に示す。ランスペースのさらなる特性は、周辺機器の資源需要または割り当て、プロセッサ操作限界および制約、タスク緊急性または延期能力などを含み得る。ランスペースシステムは、距離空間モデルを利用して、最初に、コードおよびデータを適切なローカル処理要素に割り当てる。そして、現在の目的を参照して、システム性能の最適化に有益とみなされるように、コードおよびデータを動的に移動できる。システムは、動的割り当てのためのポリシ駆動型最適化手法と、コンパイル時における包括的な最適化法との両方を用いることができる。さらに、システムは、過去の性能データから学習し、特定のコードレット、サブルーチン、タスク、およびアプリケーションの将来の割り当てを改善することができる。
【００５４】
横断的な相互動作
実行モデル：ランタイムシステムおよびマイクロＯＳは、コードレットを管理、移動および生成する。それらは、ランタイム目標に従い起動するコードレットのバージョンを選択する。前述のように、ランタイムシステムコアは、コードレット間のデータ依存関係を管理し、データおよびコードレットを共に移動し、ランタイム制約に基づいて正確なコードレットバージョンを生成する。
【００５５】
信頼性は、セキュリティと回復力との組み合わせである。実施形態に従う本発明のセキュリティの態様は、コードレットに関するセキュリティマークの提供を含む。このマークは、当該のコードレットおよびそれらの関連データの割り当てにおいて考慮されるべき制限または特権を示す。データ境界外、または規定の特権外のメモリへのアクセスは、ランタイムシステムにより処理されることとなるセキュリティ例外を発生する。ＨＰＣモードでは、ノードはアプリケーションに完全に所有される。セキュリティは、コアレベルでは、ユーザ／カーネルスペースメモリおよび命令セットにより提供される。セキュリティは、アプリケーションレベルでは、アプリケーションが起動するノードセットを規定するホストシステムと、割り当てられたノード上で起動するマイクロＯＳにその情報を中継するハイパーバイザとの両方により提供される。セキュリティは、システムレベルでは、相互排他的な方法により、ノードをアプリケーションにスケジューリングおよび割り当てる、ホストシステムにおけるジョブマネージャにより提供される。非ＨＰＣモードでは、システムは、相互排他的なチップドメインおよびメモリセグメントにさらに再分割される。メモリおよび資源は、アプリケーションが同一チップにおける互いのデータにアクセスできないようにマッピングされる。
【００５６】
回復力の維持は、システムの健康状態をフラクタルにモニタリングし、失敗したコードレットを再実行することにより実現される。計算ドメインにおけるローカルランタイムコアが実行コアの健康状態をモニタする。ノードレベルランタイムコアは、そのランタイムコアをモニタし、これは、ホストシステムによりモニタされる。構成要素の動作が失敗すると、コアにおいて起動するコードレットが（これらがプログラムにおいて状態の変化をもたらさなかった場合には）再開されるか、（プログラム状態が非決定的である場合には）チェックポイントからアプリケーションが再開される。
【００５７】
効率性に関する目標は、所定のアプリケーションおよびシステム目標セットを前提として、性能の最大化および消費電力の最小化を追求することにある。これは、コードの依存関係および作業の可用性に基づく、実行コアレベルにおける周波数および電圧スケーリングを通じて達成される。また、コードレットおよびデータは、（例えば、相互動作するコードレットをより緊密に維持することにより）それらが互いに最も効率的に通信し、（例えば、未使用のクラスタの電力ドメインを停止し、消費電力の無駄を無くすことができるように、コードレットを一緒に移動して）電力消費量が最小になる位置に移動される。
【００５８】
自己最適化：自己最適化の維持は、（健康状態および性能両方の）フラクタルモニタリングネットワーク、およびランタイムシステムの再スケジューリングを通じて行われる。これにより、信頼性および効率を維持しつつ、アプリケーションおよびシステムの目的を達成できる。
【００５９】
実施形態の説明
本発明の実施形態の動作例およびアプリケーションシナリオを、さらに図面を参照して以下に記述する。
【００６０】
図１２に、コードレットセットを用いたコンピューティングシステムを示す。重要な典型的ステップは以下を含む。ＧＣＳ上にコードレットセット表現システムを提供する（１２０１）、ＧＡＣＴからコードレットセット表現を取得する（１２０２）、コードレットセットを、実行可能または解釈可能命令および依存表現へ変換する（１２０３）、ＧＣＳ上のコードレットセットのメタレベル分配および割り当てに関する指示を利用する（１２０４）、コードレットセットの実行可能インスタンスの動的かつ具体的な分配およびマ移動を実行する（１２０５）、コードレットセットを実行する（１２０６）、および少なくとも一部の依存関係に基づいて、新規のコードレットセットを有効化する（１２０７）。
【００６１】
図１３に、以下のステップを含むコードレットセット表現システムを示す。コードレットセットを指定するための仕様システムを提供する（１３０１）、ＧＡＣＴがコードレットセットを構成および変更し、コードレットセットの初期解析を得る機構を提供する（１３０２）、ＧＡＣＴが実際のまたはシミュレートされた資源においてコードレットセットを実行する機構を提供する（１３０３）、ＧＡＣＴが起動しているコードレットセットをモニタするか、コードレットセットの履歴を確認する機構を提供する（１３０４）、ＧＡＣＴがコードレットセットを動的に操作する機構を提供する（１３０５）、およびＧＡＣＴがコードレットセット性能および資源活用をプロファイルする機構を提供する（１３０６）。
【００６２】
図１４に、以下のステップを含むコードレットセットを変換する例を示す。表現からコードレットセット記述子を抽出する（１４０１）、実行可能命令を変換する（１４０２）、資源不変の最適化を適用する（１４０３）、ランタイム割り当て、分配および移動を案内するための指示を構成、グループ分け、および分配する（１４０４）、資源に特有の最適化を適用する（１４０５）、および実行可能テキストを生成し、最初のコードレットを有効にする（１４０６）。
【００６３】
図１５に、以下のステップを含むメタレベルコードレットセット分配の例を示す。指示を利用して、最初に、コードレットセットを計算およびデータ資源に割り当てる（１５０１）、具体的レベルのコードレットセット実行および資源活用をモニタリングする（１５０２）、変更したコードレットセット分配のための機会を収集する（１５０３）、改善した（コンパイル時）最初のコードレットセット分配に関する指示を構成する（１５０４）、およびコードレットセットの（ランタイムにおける）動的移動を支援する資源情報および裁決を提供する（１５０５）。
【００６４】
図１６に、以下のステップを含むコードレットセット実行および移動を示す。コードレットセット分配命令を利用して、コードレットセットのテキストを交換資源またはシミュレートされたコンピューティング資源に分配する（１６０１）、コードレットセットの実行テキストと分配指示との間のマッピングを提供する（１６０２）、資源および結果を完了時にシステムに戻すようにコードレットセットを構成する（１６０３）、資源活用および有効化されたコードレット待ち行列負荷をモニタリングする（１６０４）、コードレット信号を利用して、状況情報を取得または通信するか、コードレットシステムをモニタする、資源を特定かつコミットするか、より高レベルモニタまでリクエストを転送するためにモニタリングする（１６０６）、および有効化された待ち行列からコードレットセットを除去し、データと共にそれらを適切な位置に移動する（１６０７）。
【００６５】
図１７に、書き込み１７０２およびキューへの追加１７０３を含む両端待ち行列同時アクセス機構を示す。待ち行列の他の状態は、空１７０１およびハウスキーピング１７０４である。
【００６６】
図１８に、一貫性チェック１８０１、空待ち行列１８０２、非空待ち行列１８０３、並びに読み出しおよびキューからの取り出し１８０４を、この時に実行するキューからの取り出し同時アクセス機構を示す。このようなシステムの１つの長所は、システムを利用する処理がハウスクリーニングタスクを処理する統合された特徴を有し、待ち行列が非常に強固であることに留意されたい。
【００６７】
図１９に、アトミック追加配列（Ａ）を介した同時アクセス、書き込みを示す。示される状態は、初期状態１９０１と、アトミックに更新された書き込みポインタ１９０２とから成る。
【００６８】
図２０に、アトミック追加配列（Ｂ）を介した同時アクセス、書き込みを示す。示される状態は、書き込みデータ２００１と、フラグが更新された、読取機に読み出されるデータ２００２とから成る。
【００６９】
図２１に、アトミック追加配列（Ｃ）を介した同時アクセス、読み出しを示す。示される状態では、読み出せる状態にあり、読み出しポインタが更新されたデータ２１０１と、開始された読み出し２１０２と、読み出し完了およびフラグ更新２１０３から成る。
【００７０】
図２２は、リンクリスト、特に、アトミック追加配列（Ａ）を示す。
【００７１】
図２３は、リンクリスト、特に、アトミック追加配列（Ｂ）を示す。
【００７２】
図２４は、リンクリスト、特に、アトミック追加配列（Ｃ）を示す。
【００７３】
図２５は、リンクリスト、特に、アトミック追加配列（Ｄ）を示す。
【００７４】
図２６は、リンクリスト、特に、アトミック追加配列（Ｅ）を示す。
【００７５】
図２７は、順番に共有配列を通る同時アクセスを示す。
【００７６】
図２８は、ネットワークに分配されたインクリメントの連結を示す。
【００７７】
図２９は、アトミック追加配列（Ａ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す。
【００７８】
図３０は、アトミック追加配列（Ｂ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す。
【００７９】
図３１は、アトミック追加配列（Ｃ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す。
【００８０】
図３２は、アトミック追加配列（Ｄ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す。
【００８１】
図３３は、アトミック追加配列（Ｅ）を通じた同時アクセスを実行する単一タスクおよび複数タスクを示す。
【００８２】
図３４は、コードレットセット計算システムシナリオを説明し、システムに関する種々のユーザの役割を示す。
【００８３】
図３５は、マイクロチップレベルにおける例示の一般的アーキテクチャを示す。メモリレベルが、非特定的であり、非ローカルメモリと異なり（高速アクセスを有する）ローカルメモリの階層を伝達するように意図されることに留意されたい。例えば、Ｌ１は、レジスタファイル、ＳＲＡＭなどとして実現され得る。
【００８４】
図３６は、回路基板／システムレベルにおける一般的アーキテクチャを示し、性能およびグローバル化の範囲を再度示す。
【００８５】
図３７はコードレットおよびコードレットセットの指定を示す。コードレットセットを特定する多くの同様の方法がある。仕様は、典型的には、特別なメタ言語、ネイティブ言語構造体、さらには、非実行の注釈を、または統合開発環境を通じた抽出により示し、伝えられ得る。コードレットセットは構成可能であり、他のコードレットまたはコードレットセットを起動するように定義され得る。ＧＡＣＴは、基本コードレットからコードレットセットを構成することにより機能性を構築し、次に、このセットを、アプリケーション全体を包含する大きなセットに一体化する。関数ｓｅｔＤｅｐｅｎｄｅｎｃｙにより、コードレットセットの２つの要素間、または異なるコードレットセットの２つの要素間の依存関係を表現することができる。一実施形態では、関数ｉｍｐｌｅｍｅｎｔＳｅｔが、依存グラフを構築し、それらをポインタに変換するためにランタイムに呼び出される。また、ある実施形態では、このような依存情報をＧＡＣＴが提供しない場合でも、コンパイラを変更してコードから依存情報を生成する。
【００８６】
図３８は二重バッファ計算（Ａ）を示す。全てのコードレットセットは、システムを開始し、終了時の依存関係を除去および起動するための初期起動および削除手順を有することに留意されたい。一部の実施形態では、初期起動および削除タスクは、コンパイル時間において静的に、またはランタイム時に動的に別々に最適化され得る。ランタイムシステムは、位置と遷移とのグラフであるペトリネットとして表された場合に同型となる。この位置はデータフローモデルを拡張し、データ依存関係、制御フロー依存関係、および資源依存関係を表すことができる。一実施形態では、システムは、最初に、より優先順位の高いタスクを実行し、次に、より優先度の低いタスクを実行する。これにより、システムに関する資源への同時アクセスを維持するタスクなどの、特定のシステムに重要なコードレットのスケジューリングが可能になる。実行コアの全てがＣｏｍｐ１、その後Ｃｏｍｐ２において動作した場合には、コピー１およびコピー２が終了するまで、突然に、コアの大部分についてはいかなる作業も存在しない。それ故、起動している待ち行列が決して空にならないように、より多くのコードレットを生成するコードレットの優先度を高くする。以下の説明では、コピーコードレットが利用可能になると優先度が高くなるため、システムは一旦起動すると、実行する少なくとも一部の計算コードレットを連続的に実行する。
【００８７】
さらに、二重バッファ計算の例では、例示の１０２４に制限された指数は、初期起動の完了時に１０２４のＣｏｍｐ１コードレットを有効にすることを示す。同様に、例示の８コピーコードレットに制限された指数は、コピーコードレットセットにおいて起動される。システムがそれらの中で解決されるＤＲＡＭ帯域幅を要求する多くのプロセッサを有し得るため、８の計数が用いられることに留意されたい。それ故、コードレットシステムは、（状況切り替え）オーバーヘッドがより低くはなるが、より少数の実行コアを用いて同一の持続的な帯域幅を実現できる。それ故、アプリケーションプログラム処理スループットの向上を実現できる。別の実施形態では、システムは、常にその内部に８トークンを有するコピー１に入り、そこから戻る場所を動的に供給し得る。同様に、コピー２に関しても同一の最適化が実行され得る。最終的に、別の実施形態では、これら２つの場所は同一場所に結合し得、コピー関数は、ＤＲＡＭ帯域幅トークンの同一プールを用いることができる。このような場合には、その計算がコピーよりも長いときには、システムは、コピー１およびコピー２を同時に実行しないことを保証できる。これは、例えば、メモリ帯域幅、実行ユニット、電力、ネットワーク、ロックなどの資源制約に関するペトリネットの表現力の一例であり、コードレットセットがその表現力を活用することにより、極めて並列、高度にスケーラブルなアプリケーションの生成が可能になることを示している。２７０２では、ｄｅｌｔａＴが、ＳｉｇｎａｌＳｅｔ（ｂｕｆｆｅｒ＿ｓｅｔ［ｌ］）の前にＳｉｇｎａｌＳｅｔ（ｂｕｆｆｅｒ＿ｓｅｔ［０］）が実行されるという事実を暗示していることに留意されたい。
【００８８】
図３９は二重バッファ計算（Ｂ）を示す。３９０１において、Ｉｎｉｔ  Ｓｅｔ１に合図が伝えられ、一方３９０２では、Ｉｎｉｔ  ｓｅｔ２に合図が伝えられる。そして、例示の数の１０２４のコードレットの計算を開始する。
【００８９】
図４０は二重バッファ計算（Ｃ）を示す。４００１では、タスクＣｏｍｐ２が待ち行列に存在するが、システムが、優先度の差異を無視した先着順モードにおいて動作しているため、実行コアはＣｏｍｐ１において動作し続ける。４００２では、Ｃｏｍｐ１が終了し、最優先タスクの「削除」が配置される。Ｃｏｍｐ２はこの時点で継続し得る。他の実施形態では、先入れ先出し以外の、たとえばスタック様の意味を与えることができる後入れ先出しなどの方法で作業を処理し得る。この実施形態は、再帰的アプリケーションにおける作業共有に有用である。
【００９０】
図４１は二重バッファ計算（Ｄ）を示す。４１０１では、Ｃｏｍｐ２は動作し続けることができるが、コピー（８）の最優先タスクに少なくとも１つの実行ユニットを用いる。４１０２では、Ｃｏｍｐ２がなおも動作し続けるが、コピー機能にさらに多くの実行ユニットが割り当てられる。システムはコピー後に資源を削除する。
【００９１】
図４２は二重バッファ計算（Ｅ）を示す。４２０１では、システムは実行終了フラグがバッファ１内に存在するか否かを確認する。４２０２では、Ｃｏｍｐ１コードレットが初期化される。
【００９２】
図４３は二重バッファ計算（Ｆ）を示す。４３０１では、Ｃｏｍｐ１コードレットは、待ち行列において既存のＣｏｍｐ２コードレットの後ろに配置される。４３０２では、Ｃｏｍｐ２が終了し、Ｃｏｍｐ１が動作し続ける。
【００９３】
図４４は二重バッファ計算（Ｇ）を示す。最終的に、４４０１では、コピーセット２の最優先コードレットが初期化され、一方、Ｃｏｍｐ１は動作し続ける。コードレットがそれらの実行中を含むいかなる時でも信号を受信できることに留意されたい。これにより、計算資源をより良く活用するためにコードおよびデータの移動を可能にできる。要約すると、顕著な態様のいくつかは以下を含み得る。（ａ）優先度、（ｂ）待ち行列スペースによる並行処理の均一化、および（ｃ）例えば、初期信号、イベントフローおよび／またはプログラマがスケジュールに影響を与え得ることを可能にさせる等を含み得る、データフローの域を超えた拡張を含み得る。
【００９４】
図４５はＳＲＡＭおよびＤＲＡＭにおける行列乗算を示す。４５０１では、システムは、ＤＲＡＭからＳＲＡＭに行列ＡおよびＢ両方のブロックをコピーし、ＳＲＡＭ内で行列Ｃを計算している。４５０２では、Ｃの各ブロックを、ＤＲＡＭ内の適切な場所に再コピーする。
【００９５】
図４６は行列乗算二重バッファ／ＤＲＡＭを示す。この場合では、コードレットを用いて、ＤＲＡＭアクセスを二重バッファし、アクセスの待ち時間を短縮する。これを、角括弧に示すコード４６０２の一部に示す。
【００９６】
図４７は、ＬＩＮＰＡＣＫ  ＤＴＲＳＭ（二重三角形の正確な倍数の解）の計算の例を示す。４７０１は最初の依存関係を示す。第１の行列が乗算されると直ぐに、システムは次のデータセットに移動することができる。
【００９７】
図４８はＤＴＲＳＭのためのコードレットセットのランタイム初期化を示す。Ｉｎｉｔ（）が、生成されるコードレット数を表すパラメータと共に呼び出されることに留意されたい。４８０２は、ＤＴＲＳＭのコードレットセット実施において実行され得るいくつかの最適化を示す。
【００９８】
図４９はクイックソートの例を示す。４９０１では、制御フローパスはデータに依存する。依存関係が初期に決定または充足される場合には、これはコードレットの出力または中間状態に基づいて条件的に設定され得る。４９０２は、クイックソートグラフに関するペトリネット表現を示す。この表現が与えられると、スワップコードレットに関する入力データが存在しなくなるまで、（データが存在しないか、不正データの全てが片側に存在しているため）スレッドは上半分において動作する。実行ユニットがもはや最優先コードレットを有さない場合には、例えば、境界において待機している優先度の低いコードレットを処理する。この時点で、「移動」コードレットが起動し、その軸を正しい位置に移動する。
【００９９】
図５０は、アプリケーションコードレットセットが組み入れられたスケーラブルシステム関数を示す。システム機能性がコードレットセットアプリケーションと流動的に一体化され得るため、システム設計者は、システムサービス対システムオーバーヘッドの均衡に関して優れた柔軟性を得ることができる。一部の使用およびアプリケーションでは、システムソフトウェアはほぼ無くてもよく、他の場合では、所与の時点で、広範囲のモニタリングおよびデバッギングにより、アプリケーションタスクよりも多くのシステムタスクを起動し得る。
【０１００】
図５１は、複数タスクへの既存のプログラムコードの変換を示し、複数タスク入出力表を用いて、コードレットセットを通じてコードの並列評価を作成する方法を示す。優先度の構成は、１つ以上の後続の並行タスクを有効にするために必要な順次タスクが最優先となるように行われる。入力変数と出力変数とのセットの特定の要素間のマッピングにより、受け入れ関数が、第１のインスタンスが利用可能になると直ぐに処理を開始することができる。コードレットセット内の分離可能なインスタンス数の計数により、システムソフトウェアは、コードレット実行の分配が可能になり、ＣＰＵの利用性の向上、およびデータ局所性の活用が可能になる。
【０１０１】
図５２は、複数タスクコードを用いた「ブラックボックス」コード起動の例を示し、ライブラリコードがコードレットセットに変換されているシナリオ５２０１を説明するが、ブラックボックスユーザコード５２０２はなおも本質的に順次的である。代替の実施形態では、以前の起動からの性能評価、同じ起動の以前のサイクル、またはその両方に基づいて、統計的に、その後の処理に全てのブラックボックス値が必要であると見込まれる場合には、優先度は控えめであり得る。
【０１０２】
図５３に改良された複数タスクコードを利用して起動したブラックボックスコードを示す。この場合では、ブラックボックスコードの一部が、並列実行に使用可能になるようにユーザによりマーキングされる。元のブラックボックスタスク５３０２に先立つ複数タスクは、関数Ｆ２、５３０３に対応する。ブラックボックスタスクの最初のセクション５３０４は、リファクタ関数ＢＢ１ａに対応し、利用可能になるときに５３０２からの結果を利用して、その時点で起動するように変換される。ブラックボックス機能の次のセクションは本質的に順次的であり、その後の動作前に完了すべきブラックボックスのままである。ある実施形態では、その後の関数の推測的実行が行われ得、５３０６の実行中でさえも並行処理を実行可能な方法を提供することに留意されたい。参照番号５３０８は、リファクタされたブラックボックス関数の第３の部分であり、関数ＢＢ１ｃに対応し、ＭＰ２  ５３１１に対応するライブラリコール５３１０との並列実行が可能である。
【０１０３】
さらなる解説
本発明の種々の実施形態は、１つ以上の性能測定値または１つ以上の資源制約に関するアプリケーションプログラムの性能の最適化に対処する。例示となる性能測定値または制約は、これらに限定されないが、プログラムの全実行時間、特定セクション内のプログラムの実行時間、特定命令の実行前の最大遅延、用いられる処理ユニットの数量、用いられるメモリの数量、レジスタファイルの使用、キャッシュメモリの使用、レベル１キャッシュメモリの使用、レベル２キャッシュメモリの使用、レベル３キャッシュメモリの使用、レベルＮ（Ｎは正数）キャッシュメモリの使用、スタティックＲＡＭメモリの使用、ダイナミックＲＡＭメモリの使用、グローバルメモリの使用、仮想メモリの使用、プログラムの実行以外に使用可能なプロセッサ数量、プログラムの実行以外に使用可能なメモリ数量、エネルギ消費、ピークエネルギ消費、コンピューティングシステムの寿命コスト、更新に必要なレジスタ量、メモリ消去が必要な量、セキュリティ実施効率、およびセキュリティ実施コストに関連し得る。
【０１０４】
結論
この詳細な説明は、前述の実例となるシステムの動作シナリオおよびアプリケーションの例に関する本発明の実施形態の仕様を提供する。特定のアプリケーション、アーキテクチャ、および論理の実施例が、本発明の概念の可能な実現形態の例、ならびに関連発明の利用シナリオを説明する目的のために、ここにおよび参照される特許出願において提供される。当然ながら、前に説明したような本発明の原理を全体または一部において実現または利用する複数の代替法がある。例えば、本明細書に区別して記述または示される要素または処理ステップは、種々の実施形態では、互いに結合されてもよいし、新たな要素またはステップを追加してもよい。記述する要素はまた、本発明の精神および範囲から逸脱すること無く、さらに再分割されてもよい。また、本発明の態様は、種々の実施形態では、アプリケーションおよびシステムソフトウェア、汎用および専用マイクロプロセッサ、カスタムハードウェア論理、並びにこれらの種々の組み合わせを用いて実現されてもよい。概して、当業者は種々のバージョンを開発し得、本明細書に個々に明示的に記載しないが、本発明の原理に依存し、それ故、その精神および範囲内に収まる、記述する実施形態の種々の変更が可能である。それ故、明細書および図面は限定的意味ではなく、例示目的のみとして考慮され、以下の請求項に示す本発明の真の範囲に収まることが意図される。
【図１】
2013524386.tif 000003
【図２】
2013524386.tif 000004
【図３】
2013524386.tif 000005
【図４】
2013524386.tif 000006
【図５】
2013524386.tif 000007
【図６】
2013524386.tif 000008
【図７】
2013524386.tif 000009
【図８】
2013524386.tif 000010
【図９】
2013524386.tif 000011
【図１０】
2013524386.tif 000012
【図１１】
2013524386.tif 000013
【図１２】
2013524386.tif 000014
【図１３】
2013524386.tif 000015
【図１４】
2013524386.tif 000016
【図１５】
2013524386.tif 000017
【図１６】
2013524386.tif 000018
【図１７】
2013524386.tif 000019
【図１８】
2013524386.tif 000020
【図１９】
2013524386.tif 000021
【図２０】
2013524386.tif 000022
【図２１】
2013524386.tif 000023
【図２２】
2013524386.tif 000024
【図２３】
2013524386.tif 000025
【図２４】
2013524386.tif 000026
【図２５】
2013524386.tif 000027
【図２６】
2013524386.tif 000028
【図２７】
2013524386.tif 000029
【図２８】
2013524386.tif 000030
【図２９】
2013524386.tif 000031
【図３０】
2013524386.tif 000032
【図３１】
2013524386.tif 000033
【図３２】
2013524386.tif 000034
【図３３】
2013524386.tif 000035
【図３４】
2013524386.tif 000036
【図３５】
2013524386.tif 000037
【図３６】
2013524386.tif 000038
【図３７】
2013524386.tif 000039
【図３８】
2013524386.tif 000040
【図３９】
2013524386.tif 000041
【図４０】
2013524386.tif 000042
【図４１】
2013524386.tif 000043
【図４２】
2013524386.tif 000044
【図４３】
2013524386.tif 000045
【図４４】
2013524386.tif 000046
【図４５】
2013524386.tif 000047
【図４６】
2013524386.tif 000048
【図４７】
2013524386.tif 000049
【図４８】
2013524386.tif 000050
【図４９】
2013524386.tif 000051
【図５０】
2013524386.tif 000052
【図５１】
2013524386.tif 000053
【図５２】
2013524386.tif 000054
【図５３】
2013524386.tif 000055
【国際調査報告】
2013524386.tif 000056