(57)【要約】  分散型コンピューティングシステムは、実行モデルの実装、ローカリティ管理スキーム、スケジューリングスキーム、型システム、および／または異種システムの管理を組み込んでもよい。【選択図】図２
2013546106.tif 000002
【特許請求の範囲】
【請求項１】
分散型コンピューティングシステムであって、
ハードウェア、ソフトウェア、または両方を使用して、１つ以上の動作の実行を促進するように構成される、１つ以上のリソースと、
少なくとも、前記リソースのサブセットによって動作されるように構成される、２つ以上の処理デバイスと、
を備え、前記１つ以上のリソースは、１つ以上のコードレットの制御下、動作を実行するように構成される、システム。
【請求項２】
前記リソースのうちの少なくとも１つは、少なくとも１つの処理デバイス上における１つ以上のコードレットの実行をスケジューリングするように構成される、スケジューラを備える、請求項１に記載のシステム。
【請求項３】
少なくとも１つのスケジューラは、特定のロケールと関連付けられた１つ以上のリソースと関連付けられる、請求項２に記載のシステム。
【請求項４】
少なくとも１つのスケジューラは、ロケールの階層内のロケールと関連付けられていない、請求項３に記載のシステム。
【請求項５】
前記システム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、前記階層のより高いレベルにおける親スケジューラからワークを要求するように構成される、請求項３に記載のシステム。
【請求項６】
前記システム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、前記階層内の異なる位置における他のスケジューラからワークを要求するように構成される、請求項３に記載のシステム。
【請求項７】
前記システム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、同一の前記階層の所与のレベルにおける１つ以上の兄弟スケジューラと相互作用し、ワークを要求する、ワークを提供する、または両方を行うように構成される、請求項３に記載のシステム。
【請求項８】
提供は、順番を譲る、またはそれらが後に再開され得るように、その状態をメモリに書き込み、その実行を終了させることのいずれかによって、前記１つ以上のコードレットが、それ自体の実行を保留するように行われる、請求項１から７の何れか１項に記載のシステム。
【請求項９】
前記１つ以上のコードレットのうちの少なくとも１つは、さらなるコードレットを参照する、請求項１から８の何れか１項に記載のシステム。
【請求項１０】
前記１つ以上のコードレットのうちの少なくとも１つは、異種型の処理デバイス上で起動可能である、請求項１から９の何れか１項に記載のシステム。
【請求項１１】
前記１つ以上のコードレットのうちの少なくとも１つは、前記１つ以上のコードレットのうちの少なくとも１つを前記異種型の処理デバイス上で起動可能にするために、複数の形態の起動フォークおよび複数の形態のキャンセルフォークの少なくとも一方を含む、請求項１０に記載のシステム。
【請求項１２】
前記システム内のオブジェクトをカテゴリ化するように構成される、階層型システムをさらに備える、請求項１から１１の何れか１項に記載のシステム。
【請求項１３】
１つ以上のノードレットが、提供され、前記ノードレットのうちの少なくとも１つは、複数のリソースへのアクセスを提供するように構成される、請求項１から１２の何れか１項に記載のシステム。
【請求項１４】
前記システムは、１つ以上のプログラムレットの使用をサポートするように構成される、請求項１から１３の何れか１項に記載のシステム。
【請求項１５】
１つ以上の処理デバイスに、
ハードウェア、ソフトウェア、または両方を使用して、１つ以上の動作の実行を促進するように構成される、１つ以上のリソースを動作させる段階と、
前記１つ以上のリソースを、１つ以上のコードレットの制御下、動作を実行するように構成する段階と、
を実行させるためのプログラムであって、
前記ハードウェアは、２つ以上の処理デバイスを含み、前記ハードウェア、ソフトウェア、または両方は、分散型コンピューティングシステムの一部であるプログラム。
【請求項１６】
さらに、前記リソースのうちの少なくとも１つを、スケジューラとして動作し、少なくとも１つの処理デバイス上での１つ以上のコードレットの実行をスケジューリングするように構成する段階を実行させる、請求項１５に記載のプログラム。
【請求項１７】
少なくとも１つのスケジューラは、特定のロケールと関連付けられた１つ以上のリソースと関連付けられる、請求項１６に記載のプログラム。
【請求項１８】
少なくとも１つのスケジューラは、ロケールの階層内のロケールと関連付けられていない、請求項１７に記載のプログラム。
【請求項１９】
前記分散型コンピューティングシステム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、前記階層のより高いレベルにおける親スケジューラからワークを要求するように構成される、請求項１７に記載のプログラム。
【請求項２０】
前記分散型コンピューティングシステム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、前記階層内の異なる位置における他のスケジューラからワークを要求するように構成される、請求項１７に記載のプログラム。
【請求項２１】
前記分散型コンピューティングシステム内のロケールは、階層に編成され、前記階層の所与のレベルにおいてロケールと関連付けられたスケジューラは、同一の前記階層の所与のレベルにおける１つ以上の兄弟スケジューラと相互作用し、ワークを要求する、ワークを提供する、または両方を行うように構成される、請求項１７に記載のプログラム。
【請求項２２】
前記１つ以上のコードレットが、順番を譲る、またはそれらが後に再開され得るように、その状態をメモリに書き込み、その実行を終了させることのいずれかによって、それ自体の実行を保留することを可能にする段階を実行させる、請求項１５から２１の何れか１項に記載のプログラム。
【請求項２３】
前記１つ以上のコードレットのうちの少なくとも１つは、さらなるコードレットを参照する、請求項１５から２２の何れか１項に記載のプログラム。
【請求項２４】
さらに、前記システム内のオブジェクトをカテゴリ化するように構成される、階層型システムをサポートする段階を実行させる、請求項１５から２３の何れか１項に記載のプログラム。
【請求項２５】
さらに、複数のリソースへのアクセスを提供するように構成される、１つ以上のノードレットの使用をサポートする段階を実行させる、請求項１５から２４の何れか１項に記載のプログラム。
【請求項２６】
さらに、１つ以上のプログラムレットの使用をサポートする段階を実行させる、請求項１５から２５の何れか１項に記載のプログラム。
【請求項２７】
分散型コンピューティングの方法であって、
ハードウェア、ソフトウェア、または両方を使用して、１つ以上の動作の実行を促進するように構成される、１つ以上のリソースを動作させることと、
前記１つ以上のリソースを、１つ以上のコードレットの制御下、動作を実行するように構成することと、
を備え、
前記ハードウェアは、２つ以上の処理デバイスを含み、前記ハードウェア、ソフトウェア、または両方は、分散型コンピューティングシステムの一部である、方法。
【請求項２８】
前記リソースのうちの少なくとも１つは、スケジューラを備え、前記方法はさらに、前記スケジューラによって、少なくとも１つの処理デバイス上での１つ以上のコードレットの実行をスケジューリングすることを備える、請求項２７に記載の方法。
【請求項２９】
少なくとも１つのスケジューラは、特定のロケールと関連付けられた１つ以上のリソースと関連付けられる、請求項２８に記載の方法。
【請求項３０】
少なくとも１つのスケジューラは、ロケールの階層内のロケールと関連付けられていない、請求項２９に記載の方法。
【請求項３１】
前記システム内のロケールは、階層に編成され、前記方法はさらに、前記階層の所与のレベルにおけるロケールと関連付けられたスケジューラによって、前記階層のより高いレベルにおける親スケジューラからワークを要求することを備える、請求項２９に記載の方法。
【請求項３２】
前記システム内のロケールは、階層に編成され、前記方法はさらに、前記階層の所与のレベルにおけるロケールと関連付けられたスケジューラによって、前記階層内の異なる位置における他のスケジューラからワークを要求することを備える、請求項２９に記載の方法。
【請求項３３】
前記システム内のロケールは、階層に編成され、前記方法はさらに、前記階層の所与のレベルにおけるロケールと関連付けられたスケジューラによって、同一の前記階層の所与のレベルにおける１つ以上の兄弟スケジューラと相互作用し、ワークを要求する、ワークを提供する、または両方を行うことを備える、請求項２９に記載の方法。
【請求項３４】
前記１つ以上のコードレットが、順番を譲る、またはそれらが後に再開され得るように、その状態をメモリに書き込み、その実行を終了させることのいずれかによって、それ自体の実行を保留することを可能にすることをさらに備える、請求項２７から３３の何れか１項に記載の方法。
【請求項３５】
前記１つ以上のコードレットのうちの少なくとも１つは、さらなるコードレットを参照する、請求項２７から３４の何れか１項に記載の方法。
【請求項３６】
前記１つ以上のコードレットのうちの少なくとも１つは、異種型の処理デバイス上で起動可能にされる、請求項２７から３５の何れか１項に記載の方法。
【請求項３７】
前記１つ以上のコードレットのうちの少なくとも１つは、前記１つ以上のコードレットのうちの少なくとも１つを前記異種型の処理デバイス上で起動可能にするために、複数の形態の起動フォークおよび複数の形態のキャンセルフォークの少なくとも一方を含む、請求項３６に記載の方法。
【請求項３８】
前記システム内のオブジェクトをカテゴリ化するように構成される、階層型システムを実装することをさらに備える、請求項２７から３７の何れか１項に記載の方法。
【請求項３９】
１つ以上のノードレットを提供することをさらに備え、前記ノードレットのうちの少なくとも１つは、複数のリソースへのアクセスを提供するように構成される、請求項２７から３８の何れか１項に記載の方法。
【請求項４０】
１つ以上のプログラムレットの使用をサポートすることをさらに備える、請求項２７から３９の何れか１項に記載の方法。
【請求項４１】
コンピューティングシステムであって、
少なくとも１つの処理デバイスと、
前記少なくとも１つの処理デバイスに連結される、少なくとも１つのメモリユニットと、
を備え、前記少なくとも１つのメモリユニットは、複数のインヘリタンス、複数のインターフェース、および統合型をサポートするように構成される、階層型システムを実装するために、前記少なくとも１つの処理デバイスによって実行可能である命令を含有し、前記階層型システムはさらに、異種アーキテクチャ、プラットフォーム、バイナリインターフェース、またはこれらの何れかの組み合わせを有する、システム間のデータの転送をサポートする。
【請求項４２】
少なくとも１つの処理デバイスに、複数のインヘリタンス、複数のインターフェース、および統合型をサポートするように構成される、階層型システムを実装させるためのプログラムであって、に、前記階層型システムはさらに、異種アーキテクチャ、プラットフォーム、バイナリインターフェース、またはこれらの何れかの組み合わせを有する、システム間のデータの転送をサポートする、プログラム。
【請求項４３】
階層型システムを実装する方法であって、
階層構造に従って編成される型の多様性を提供することと、
前記型が、複数のインヘリタンス、複数のインターフェース、および統合型をサポートすることを可能にすることと、
を備え、前記階層型システムは、異種アーキテクチャ、プラットフォーム、バイナリインターフェース、またはこれらの何れかの組み合わせを有するシステム間のデータの転送をサポートする、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の参照
本願は、参照することによって、全体として本明細書に組み込まれる、２０１０年１２月１６日出願の米国仮特許出願第６１／４２４，０５２号の優先権を請求する、特許出願である。
【０００２】
本発明の種々の実施形態は、分散型コンピューティングを実装するためのコンピューティング環境の種々の態様に関し得る。
【背景技術】
【０００３】
現代のハイエンドコンピュータ（ＨＥＣ）アーキテクチャは、数千から数百万の処理要素、様々な程度の非ローカルメモリを伴う大量の分散型メモリ、ネットワーキング、およびストレージインフラストラクチャを具現化し得る。これらのシステムは、アプリケーションを実行することによって利用されるリソースの静的および動的両方の最適化のための大きな機会を提示する。従来、コンピュータアーキテクチャは、アプリケーションに、単一の均一アドレス空間とともに、コードの順次実行およびデータへのアクセスのための合理的意味論を提示するよう努力してきた。結果として生じるパラダイムは、長年、良好に機能していたが、計算およびデータ両方が分散される時、かつ事実上、全ハードウェアの加速が、クロックレートの増加ではなく、並行処理を介して達成される時、最適リソース配分の障害となっている。
【０００４】
効率的分散型コンピューティングにおける大きな課題は、下層ハードウェアを最適に利用する一方、アプリケーションコードの作成者に、計算の使用可能な抽象モデルを提供する、システムソフトウェアを提供可能にすることである。これは、概して、制御、監視、信頼性、およびセキュリティが、各レベルにおいてコヒーレントであるように、システム要素のスペクトルに沿って、一貫した選択が行われることを要求し得る。開発者が、新しい環境において、アプリケーションの非常に大量のサブセットを生産的に処理することができるように、コンピュータ仕様システム、調整システム、およびクリアかつ合理的意味論を伴う言語もまた、必要であろう。加えて、アプリケーションコードの効率的分散型実行をサポートする、コンパイラまたはインタープリタも要求され、開発者に、アプリケーションコードの実行に関する選択肢および洞察を提供するための関連開発ツールを必要とし得る。
【０００５】
ＨＥＣ開発を推進するアプリケーションとして、一般に、グラフ検索、最小経路検索、および最大フロー分析等のグラフ分析アプリケーション；非線形および混合整数プログラミング、ならびに確率的最適化を含む、汎用最適化アプリケーション；イメージ分析、データマイニング、および有限要素シミュレーションを含む、科学的コンピューティングアプリケーションを含んでもよい。より大きな消費者指向問題もまた、ＨＥＣの標的であって、情報検索および索引付け、テキスト分析、ならびに情報抽出を含んでもよい。
【発明の概要】
【０００６】
本発明の種々の実施形態は、分散型コンピューティングシステムを実装するためのハードウェア、ソフトウェア、および／またはファームウェア、ならびに方法に関し得る。そのような実施形態は、実行モデルの実装、ローカリティ管理スキーム、スケジューリングスキーム、型システム、および／または異種システムの管理を組み込んでもよい。
【図面の簡単な説明】
【０００７】
次に、本発明の種々の実施形態が、付随の図面と併せて、さらに詳細に説明される。
【０００８】
【図１】本発明の種々の実施形態による、分散型コンピューティングシステムの概念的ブロック図を示す。
【図２】本発明の種々の実施形態に組み込まれ得る、またはそれを利用し得る、システムの概念的ブロック図を示す。
【図３】本発明の種々の実施形態による、通信のためのキーパッシングの使用を図示する。
【図４】本発明の実施形態の概念的階層表現を示す。
【図５】本発明の種々の実施形態による、コンテキスト階層を示す。
【図６】本発明の種々の実施形態による、ノードレットの実施例を示す。
【図７】本発明の種々の実施形態による、ストレージマッピングの実施例を示す。
【図８】本発明の種々の実施形態による、例示的型階層を示す。
【図９】本発明の種々の実施形態による、階層ワークスティーリングスケジューラの動作を示す。
【図１０】本発明の種々の実施形態における、コードレット挙動に関するように、データレットの挙動を示す。
【発明を実施するための形態】
【０００９】
分散型コンピューティングシステムでは、単一プログラムが、複数の処理デバイス上で実行されてもよい。図１は、そのようなシステムが、どのように実装され得るかの実施例を示す。ユーザデバイス１１は、プログラムが実行されるように準備するために使用されてもよい（ユーザが、プログラムを書き込むことを可能にすることを含む）。ユーザデバイスは、本プログラムの態様を実行するために使用され得る、種々の処理デバイス１２ａ、１２ｂ、...、１２ｎと通信してもよい。処理デバイスは、相互間において、および／またはユーザデバイス１１と相互接続１３されてもよい。ユーザデバイスおよび／または処理デバイスのうちの種々のデバイスは、図２に示される実施例等のコンピューティングシステムを備えてもよい。ユーザデバイス１１はまた、分散型コンピューティングシステムの一部としての役割を果たし得る、処理デバイスを組み込んでもよいことに留意されたい。また、１つ以上の処理デバイス１２ａ、１２ｂ、...、１２ｎは、マルチコア中央処理ユニット（ＣＰＵ）等、単一プロセッサパッケージ内に含有されてもよいことに留意されたい。
【００１０】
図２は、本発明の実施形態の種々の形態および／または一部を実装するために使用され得る、例示的システムを示す。そのようなコンピューティングシステムは、１つ以上のシステムメモリ２１に連結され得る、１つ以上のプロセッサ２２を含んでもよい。そのようなシステムメモリ２１は、例えば、ＲＡＭ、ＲＯＭ、または他のそのような機械可読媒体を含んでもよく、システムメモリ２１は、例えば、ベーシックＩ／Ｏシステム（ＢＩＯＳ）、オペレーティングシステム、プロセッサ２２による実行のための命令等を組み込むために使用されてもよい。システムはまた、付加的ＲＡＭ、ＲＯＭ、ハードディスクドライブ、または他のプロセッサ可読媒体等、さらなるメモリ２３を含んでもよい。プロセッサ２２はまた、少なくとも１つの入力／出力（Ｉ／Ｏ）インターフェース２４に連結されてもよい。Ｉ／Ｏインターフェース２４は、１つ以上のユーザインターフェース、ならびに種々の型のストレージ媒体のためのリーダ、および／またはそこから、例えば、ソフトウェアコードが、得られてもよい、１つ以上の通信ネットワーク（例えば、通信インターフェースおよび／またはモデム）への接続を含んでもよい。そのようなコンピューティングシステムは、例えば、その上で、翻訳ソフトウェアを起動し、および／またはエミュレーションシステムを制御する、それを格納する、またはそれとインターフェースをとる、プラットフォームとして使用されてもよい。さらに、ＦＰＧＡ等の他のデバイス／媒体もまた、システムに取り付けられ、それと相互作用してもよい。
【００１１】
前述のように、分散型コンピューティングシステムを実装時、検討される必要があり得る、多数の問題が存在する。例えば、１つは、タスクをどのように分散させるか、処理デバイス（例えば、図１の１２ａ、１２ｂ、...、１２ｎおよび／またはユーザデバイス１１）間のデータの相互作用／交換をどのように配列するか、効率的実行をどのように促進するか、そのようなシステムのためのプログラムの準備をどのように促進するか等を検討する必要があり得る。
【００１２】
分散型コンピューティング環境の種々の態様に対応するために、そのような環境のためのランタイムアーキテクチャは、プログラムコンポーネントのためのきめの細かいスケジューリングサービスを提供してもよく、そのために、プログラムは、従来の実行システムおよびＣ等の関連付けられたプログラミング言語において型変換されたプログラムと異なるように分解されてもよい。したがって、典型的には、主として、スレッドあたり１つのコールスタックを使用する、リエントラント関数を呼び出す複数の独立スレッドから成る「ネイティブ」Ｃ／Ｐスレッド実行モデル（ほとんどの他の命令型言語によって共有されるモデル）と、本発明の種々の実施形態において使用され得る実行モデルとの間で区別が行われてもよい。
【００１３】
本発明の実施形態は、ランタイムのスケジューリングアルゴリズムに関して、個々に、実行の基本単位を構成し得る、「コードレット」に基づく実行モデルを使用してもよい。コードレットは、以下を含んでもよい。
・プログラムの状態を進行させるために、通常状況下、行われるべきタスクの記述。これは、コードレットの「起動フォーク」である。
・プログラム状態を安全に取り消すために、例外的状況下、行われるべきタスクの随意の記述。これは、コードレットの「キャンセルフォーク」である。
・該当する場合、コードレットによって予期されるコンテキストフレームの型の記述。コードレットへのコンテキストフレーム入力は、オブジェクト指向言語におけるメソッドにパスされる、ｉｍｐｌｉｃｉｔ  ｔｈｉｓ／ｓｅｌｆパラメータに類似する。「コンテキスト」とは、その状況または状態（例えば、変数、キャッシュ値等）を記録するために、コードレット（または、一般に、任意のプロシージャ）によって使用され得る、情報を指す。
・該当する場合、コードレットによって予期される入力データの型の記述。
【００１４】
コードレットは、各フォーク、起動およびキャンセル、ならびにコンテキストおよび入力型の記述のための関数への参照を含有する記述子オブジェクトとして、ランタイム環境内に表現されてもよい。
【００１５】
実行を始動すると、コードレットは、そのコンテキストおよび入力への参照、ならびにシステムハードウェアに対してその関係を管理可能にする役割を果たし得る、環境バッファへの参照を受信してもよい。加えて、コードレットは、付加的「チェーンコードレット」（以下参照）およびコードレットによって開始されたアクティビティが完了すると、起動されるべき関連付けられた「チェーンコンテキスト」への参照を受信してもよい。
【００１６】
コードレットを起動するために、「コードレットインスタンス」は、スケジューラ（スケジューラは、以下にさらに論じられるであろう）によって、コードレット、コンテキスト、および入力への参照をレジスタすることによって作動可能となり得る。コードレット参照はまた、様々な作動可能の段階において、部分的コードレットインスタンスを作成するために使用され得る。例えば、ネットワークからの入力を待機するコードレットは、ネットワークインターフェース上のそのコンテキストにレジスタされてもよく、その入力は、データがネットワークから到着すると、コードレットインスタンスを完成するように、後に記入することができる。
【００１７】
スケジューラが、実行のためのコードレットを選択すると、そのコードレットは、「アクティブ」となり、概して、プリエンプションまたはブロッキングを伴わずに、完了するように起動し得る。これは、コードレットが、その実行の持続時間の間、排他的にその処理スレッドを利用し得ることを意味する。コードレットが、従来、ブロッキング（例えば、ファイルからの読み取り）をもたらすであろう条件に遭遇する場合、任意の不揮発性データをそのコンテキストにスピルし、チェーンコンテキストおよびコードレットを適切なソフトウェアインターフェースにレジスタし、その実行を終了し、制御をランタイムシステムに委譲し得る。ｒｅｇｉｓｔｅｒｅｄ−ｆｏｒイベントが生じると、レジスタされたチェーンコードレットは、次いで、コンテキストからの状態をアンパックし、以前のコードレットが中断した実行を再開し得る。本機構は、オペレーティングシステムを関与させ得る、鈍重なタスクまたはスレッド切替機構を要求せずに、レイテンシの長い動作が完了する間、コードレットによって使用中のハードウェアリソースが、放棄され、他のワークのために再使用されることを可能にする。本機構はまた、例えば、いくつかのコードレットインスタンスをスケジューラにレジスタすることによって、より多くのコードレットを生成するために使用されることができる。
【００１８】
ある場合には、タスクを完了するために、２つ以上のコードレットを使用することが必要であり得る。例えば、ファイルからテキストの一節を読み取ることは、任意の数のブロッキング動作を伴い、それぞれ、コードレットに、そのコンテキストにスピルし、再開のためにレジスタし、終了し、最終的に、再開することを要求し得る。単一目標に向かってワークを行うコードレットのグループは、「コードレットコンプレックス」と称され得る。典型的には、コンプレックス内の全コードレットは、個々に連続して、またはともに並行してかにかかわらず、同一コンテキストオブジェクトを使用してもよい。コードレットはまた、包括的「スーパーコンプレックス」の代わりに、タスクのより小さい部分を行う、「サブコンプレックス」を形成し得る。例えば、コードレットコンプレックスは、ファイルからテキストの一節を読み取るために使用されてもよく、スーパーコンプレックスは、ファイル全体を解析し、そのデータをメモリ内に記憶する間、そのコンプレックスを使用してもよく、スーパー−スーパーコンプレックスは、解析コンプレックスを使用して、アプリケーションコアに投じられる前に、その構成データを作動可能にしてもよい等となる。コンプレックスは、したがって、プログラム構造に及ぼす影響の観点から、高レベルプログラミング言語におけるサブルーチンに類似すると考えられ得る。しかしながら、必ずしも、ほとんどの言語におけるサブルーチンと同一の後入れ先出し（ＬＩＦＯ）順序要件を被るわけではない。
【００１９】
前述のように、コードレットが実行を始動すると、ともに「チェーンペア」と称され得る、チェーンコードレットおよびコンテキストへの参照が与えられてもよい。これはいくつかのタスクの完了への依存性を示すための単純機構を提供し、典型的には、任意の従来のサブルーチンコールに暗黙的にパスされる、リターンアドレスに関連すると見なされ得る。前述の一節の読取実施例を再考すると、チェーンペアを一節の読取コンプレックスを開始するコードレットにパスすることは、その入力として、新しく読み取られたテキストとともに、一節全体が読み取られた後、チェーンコードレットの作動可能状態をもたらし得る。
【００２０】
アクティブコードレット内では、実行モデルは、従来のスタックベースのモデルに類似してもよく、下層プラットフォームがそれをサポートすると仮定すると、コードレットは、関数コールを正常に行い得る。コードレットはまた、ランタイムソフトウェアに明示的に「順番を譲る」ことによって、それ自体の実行を一時的に保留してもよく、これによって、直接、保留されたコードレット内から読み出されるかのように、１つ以上の他のコードレットを同一プログラムスタック上で起動可能にし、その後、スケジューラは、何事もなかったかのように、保留されたコードレットの実行を再開し得る。
【００２１】
本発明による、ランタイム環境の実施形態は、従来の関数コールおよび／またはコードレット内での使用のために、スタックベースの例外ハンドリングをサポートしてもよく、加えて、可能であれば、高速かつ単純エラー回復を可能にし得る、双方向例外再開意味論をサポートしてもよい。しかしながら、コードレットは、直接、プログラムスタック上で相互に関連し得ないため、スタックベース機構を使用してコードレット間で例外を伝送することは、不可能であって、純粋なＬＩＦＯの順序を有していない可能性が高いであろう。このため、各コードレットは、チェーニングの間、使用することができる、随意のキャンセルフォークを有してもよい。
【００２２】
チェーンコードレットは、それを正常に起動する（起動フォークを介して）、またはそれをキャンセルする（キャンセルフォークを介して）ことによって、対処され得る。キャンセルフォークは、例外をチェーンコードレットに伝送するために使用されてもよく、同様に、スタックベースの例外スローは、例外を発呼側関数に伝送してもよい。チェーンペアは、コードレットのキャンセルフォークにパスされ、エラー回復後、再開のためのサポートを提供してもよく、同様に、チェーンペアは、起動フォークにパスされ、完了をサポートすることができる。本発明の種々の実施形態による、コードレットは、現在普及している関数およびスタックベースの実行モデルに密接に関連してもよく、その拡張機能として作用してもよい。関数とコードレットとの間の主要な差異は、以下である。
・順序制約（ＬＩＦＯまたは別様に）が、相互に対して、コードレットに課されないが、コードレット自体の挙動によって施行されるそれらの制約を除く。
・リターンアドレスおよび発呼側のスタック／例外フレームポインタの代わりに、コードレットは、チェーンペアを受け取る。
・チェーンペアは、コードレットがアクティブになった後、随時（コードレットの実行または保留の間を含む）、トリガされてもよい一方、関数のリターンは、関数自体の実行と重複し得ない。
コードレットに課される要件は、関数に課されるものより弱いため、コードレットは、従来の方式のＬＩＦＯ順序化関数を実装するために使用されてもよい。
【００２３】
当然ながら、従来のスタックベースの機構は、主に、その極端に低いオーバーヘッドのため、依然として、有用であり得る。スタック上のデータ配分は、加減動作のみを要求してもよく、関数コールは、典型的には、レジスタ記憶またはスタックプッシュ動作のみを伴ってもよい。このことから、コードレット生成コンパイラが、チェーニングされたコードレットコールをコードレット内ＬＩＦＯ関数コールに変換することは、非コードレット生成コンパイラのインライン化関数コールに非常に類似し得るということになる。コンパイラが、可能であれば、その出力のコードレットおよび関数ベースの形態の両方を生成する場合、また、より低いオーバーヘッドの同期（ＬＩＦＯ）関数ベースのコールとより高いオーバーヘッドの非同期コードレットベースのコールとの間の静的または動的選択も可能にし得る。
【００２４】
本発明の実施形態は、コードレットに対するサポートの提供に加え、静的データフロープログラミングのためのより優れたビルトインサポートを提供する、コードレットの拡張機能である、「データレット」に対するサポートを提供してもよい。コードレットは、単一コンテキスト、入力、およびチェーンペアを受け取ってもよく、これらのデータが作動可能になるとすぐに、実行されてもよい。データレットは、単一コンテキストおよびチェーンペアを受け取るだけではなく、また、非同期的に、かつ任意の順序で準備され、割り当てられ得る、任意の数の入力を受け取ってもよい。データレットは、コードレット同様に、メモリ内に、ランタイムコンポーネントがデータレットを直接参照することを可能にし得る、関連付けられた記述子を有してもよく、本記述子は、コードレット記述子の全コンポーネント（起動／キャンセルフォークへの参照を含む）、ならびに全入力およびその型の記述とアプリケーション提供起動およびキャンセルフォーク関数への参照を含んでもよい。データレット挙動は、コードレット挙動を拡張させ得るため、データレットのコードレットアスペクトは、別個の内部起動およびキャンセルフォーク関数を使用して、データレットのための入力を受け取り、準備し、データレット特有の起動／キャンセルフォーク関数を立ち上げてもよい。データレットの内部起動／キャンセルフォークは、以下、その「制御フォーク」（例えば、その制御起動フォークまたは制御キャンセルフォーク）と称され、アプリケーション特有フォークは、「アプリケーションフォーク」と称される。図１０（ａ）および１０（ｂ）は、コードレットのフォーク（図１０（ａ））とデータレットのフォーク（図１０（ｂ））との間の差異を図示する。
【００２５】
入力をデータレットに割り当てる時、入力のための識別子（例えば、整数）、入力のための値、および入力がもはや必要ではなくなる時に実行されるべきチェーンペアが、データレットの制御起動フォークへの入力として、ともにパスされてもよい。制御起動フォークは、開始に応じて、データレットのアプリケーション起動フォークによる後の使用のための入力を準備する、および／または実行のためのアプリケーション起動またはキャンセルフォークをスケジューリングするために必要な任意のアクションをとってもよい（図１０（ｃ））。データレットのキャンセルは、特定のコンテキストのために収集された入力の破棄をもたらしてもよく、データレットのアプリケーションキャンセルフォークは、その結果、コールされてもよい（図１０（ｄ））。アプリケーションフォークを開始するために使用される方法にかかわらず、入力がデータレットによって「消耗」されると、すなわち、アプリケーションフォークが、そのチェーンペアを実行させると、入力とともにパスされた任意のチェーンペアが、ディスパッチされてもよい。本発明の実施形態は、ランタイム内部チェーンペアを制御フォークからアプリケーションフォークにパスし、次いで、チェーンコードレットを使用して、データレット入力をクリーンアップすることによって、本プロセスをもたらしてもよい。
【００２６】
いくつかの種々のデータレット挙動は、特に有用であって、論理ＡＮＤ、ＯＲ、およびＸＯＲ演算子に対応してもよい。ＡＮＤベースのデータレットは、全指定された入力が受信され、使用のために準備された後、そのアプリケーション起動フォークを起動し、制御起動フォークに対するコンテキストパラメータを使用して、具体的入力値のキューにマップしてもよく、全入力値が特定のコンテキストに対して収集されると、値は、キューから除かれ、データレットのアプリケーション起動フォークが、開始されてもよい。ＯＲベースのデータレットは、入力の一部または全部が収集される場合、そのアプリケーション起動フォークを起動してもよい。異なる実施形態は、他の挙動の中でもとりわけ、任意の１つの入力が収集されるとすぐに、アプリケーション起動フォークを起動するように選択してもよく（ＸＯＲベースのデータレットと効果的に同じ挙動）、いくつかの最小数の入力が収集されるまで、待機してもよく、またはある短い遅延の間、待機し、入力を蓄積させてもよい。ＸＯＲベースのデータレットは、単一入力が受信されるとすぐに、そのアプリケーション起動フォークを起動し、その単一入力をアプリケーション起動フォークにパスするのみであってもよい。本発明の実施形態は、他のデータレット挙動（例えば、時限ＮＯＴまたはＮＯＲベースのデータレット）を実装または提供してもよい。加えて、いくつかの実施形態は、動的に指定された入力リストおよび型を提供してもよい。
【００２７】
本発明の種々の実施形態による、システムは、図４に示されるように、大まかに階層線に沿って分割されてもよい。コンピューティング「ユニバース」は、システム４１、４２、および４３等の１つ以上のランタイムシステムを含んでもよい。所与のランタイムシステムは、ホスト４１１等の１つ以上のホストを含んでもよい。ホストは、ノード４１１１等の１つ以上の処理ノードを含んでもよい。処理ノード４１１１は、１つ以上のソフトウェアまたはハードウェアスレッド４１１１１を起動するために使用されてもよい。
【００２８】
コードレット実行は、ランタイムシステムによって管理され得る、ハードウェアまたはソフトウェアスレッド上で生じてもよい。これらのスレッドは、それらの間で容易に共有され得る、情報の程度に基づいて、ともにグループ化されてもよい。例えば、キャッシュを共有する２つのスレッドは、ともにグループ化される場合があり、またはホスト上の全コアは、ともにグループ化され得る。これらのグループ化は、分散型プラットフォーム上で実行するソフトウェアの通信特性を記述するために使用され得る、ツリー状の構造または「ロケールツリー」にネスト化されてもよい。
【００２９】
ツリー内の各ロケールは、それぞれ、ロケール内のメモリ空間および処理時間の配分を管理し得る、関連付けられたストレージおよび処理リソースを有してもよい。リーフ（すなわち、最下レベルかつ子がない）ロケールのアロケータおよびスケジューラは、その記述されるハードウェアまたはソフトウェア構造内の空間／時間配分を管理し得る一方、より高いレベルのロケールのアロケータおよびスケジューラは、それ自体の配分および／またはその子孫の配分を管理し、潜在的に、子孫のハードウェアおよびソフトウェアリソースの集約を可能にし得る。
【００３０】
ロケールは、コンピューティングシステムの境界領域を表し得るため、本発明の実施形態によって提供されるロケールとのソフトウェアインターフェースは、通常、特殊ソフトウェアサポートまたは明示的ハンドリングを要求する、境界を越える、それらの領域間のデータの転送および制御を提供し得る。ロケールは、アドレス空間内データ転送（例えば、ポインタ共有およびバルクコピー）、ノード内アドレス空間間転送（例えば、メモリマッピングを共有して、またはローカルソケットインターフェースを使用して）、および／またはノード間転送（例えば、ネットワーク／バス相互接続にわたっての明示的パケット／メッセージベースの通信）を含む、異種データ転送方法の抽象化を可能にし得る。
【００３１】
データ転送に加え、１つのロケール内で実行するコードレットは、ロケールツリー内のその実行範囲を拡大、縮小、または全体的に移動させ得る。これは、プログラムコンポーネントの実行が、明示的または暗黙的に、それに応じて作用が必要となるデータにフォワードされることを可能にし、システムをデータ可用性および配置に動的に反応可能にさせ得る。
【００３２】
ロケールを管理するための技法はさらに、システム内の不均一性に関連する問題の管理を支援し得る。将来的コンピューティングシステムは、相当なハードウェア不均一性を呈することが予期されるため、それに良好に対処するための分散型ランタイムシステムを設計することが望ましくあり得る。通信、スケジューリング、およびメモリ配分のために使用される抽象化を統一することによって、本発明の実施形態は、単純明快な実行の分散を可能にし得る。
【００３３】
前述のロケールツリーは、利用可能である場合、異種ハードウェアコンポーネントを記述するために拡張されてもよい。例えば、付随メモリを伴うＧＰＵは、具体的にそれを参照する、それ自体のスケジューラおよびアロケータとともに、それ自体のロケールが与えられてもよい。コードレットは、ランタイムに対する高レベル多型オブジェクトとして表され得るため、起動またはキャンセルフォークの複数の形態が、コードレットオブジェクトとともに記憶されてもよく、例えば、１つは、ＣＰＵアーキテクチャ用、１つは、ＧＰＵアーキテクチャ用であって、ランタイムは、次いで、自動的に、必要に応じて、その形態から選択してもよい。自動的および明示的両方のスケジューリングが、可能となり得るため、プログラムは、コードレットを明示的に特定し、例えば、ＧＰＵにスケジューリングする、またはそれおよび適切なワークが利用可能になるのに伴って、ランタイムをＧＰＵにスケジューリングさせるかのいずれかであってもよい。本発明のランタイムシステムの実施形態はまた、典型的には、互換性がない、アーキテクチャの統合を可能にしてもよい。例えば、データは、以下に論じられる、Ｔｒａｎｓｆｅｒａｂｌｅインターフェース型（以下により詳細に論じられる）を使用して、リトルエンディアンとビッグエンディアンアーキテクチャとの間、または異なるポインタ形式を伴うアーキテクチャ間を容易に移行され、アーキテクチャの個別のロケール間でデータをポートしてもよい。（一方、Ｔｒａｎｓｆｅｒａｂｌｅの非使用は、オブジェクトをそのアドレス空間に暗黙的に固定可能にし得るが、圧縮ガーベジコレクションを伴うシステムは、依然として、アドレス空間内のオブジェクトを再配置させ得る。）
【００３４】
データ転送の基礎としてのロケールの使用はまた、ネットワーク化された計算ノード間の境界が、多くの場合、アプリケーションによって軽視されることを可能にして得る。プログラムコンポーネントが、起動するために十分なローカルデータおよび利用可能なメモリ空間を有する限り、そのコンポーネントの実行が生じる場所、またはハードウェアのどの精密な部品上であるかが問題になることは稀であり得る。ランタイムが、通信および実行配置を管理可能となることによって、アプリケーションコンポーネントは、必要に応じて、透過的に移行され、例えば、通信オーバーヘッドを削減し、またはローカル処理またはメモリ負荷を平衡化し得る。
【００３５】
ロケール階層は、コードレットスケジューラおよび／または他のソフトウェアリソースによって使用され、ローカリティの概算を導出し、したがって、コードレット実行および／またはコンテキストの配置の判定を支援してもよい。一実施形態では、デフォルト挙動は、協働コードレットが、メモリ内の単一コンテキストブロックを共有することを要求するものであってもよく、これらのコードレットは、理想的には、本コンテキストブロック近傍のいずれかの場所で実行していてもよい。別の実施形態では、より高度な並行コードレットコンプレックスに対して、より大きなシステムリソースの集合にわたって、その実行を分散させることが望ましくあり得る。
【００３６】
このため、コンプレックスは、ロケールツリーの上部にオーバーレイされるツリー状構造内に配列され得る、コンテキストのいくつかの層を利用してもよい。図５は、コンテキスト層の実施例を示す。コンテキスト層ツリーのリーフは、コードレットが、最も容易かつ直接、確認する、コンテキストに対応し得る、最も局在したコンテキストブロックを表し得る。あまり局在していないコンテキストブロックは、リーフコンテキストから親ポインタを通して、参照することができる（但し、ランタイムシステムの実施形態と互換性があるコードを生成する、プログラミング言語は、これらのポインタを通したより高いレベル層への参照を曖昧にし得る）。その結果、多層コンテキスト（図５の実施例では、本発明は、これに限定されないが、３層コンテキスト）は、単一ＣＰＵコア内の異なるハードウェアスレッド上で起動するコードレット間で共有されるコンテキスト層、単一ＮＵＭＡノードまたはホスト上で起動するコードレット間で共有される別の層、およびコンプレックス内の全コードレット間で共有されるさらなる層を提供するために使用することができる。通常単一層プロシージャコンテキストは、直接、コードレット間で共有されてもよいが、いくつかの状況または実施形態では、そこに記憶されたデータを同期させるために、明示的リソース管理コールを使用して、より上層のコンテキストを明示的にフラッシュするために必要であってもよい。典型的実施形態では、より上層のコンテキストは、より下層コンテキストが、未使用となると、自動的にフラッシュされてもよく、そのストレージは、リクレ−ムされる。代替実施形態では、コンテキスト情報の更新は、現在の情報が必要とされるまで、延期されてもよい。
【００３７】
本発明を具現化する、ランタイム内で実行する各コードレットは、開始されると、「環境バッファ」が提供されてもよい。環境バッファは、コードレットが、現在、実行中である、ロケール、コードレットコンプレックスの実行ルートに対する最新のホップおよび発信元を指定し得る、原点および送信側ロケール、ならびにルートに対する次のおよび最終ホップを指定し得る、受信側および宛先ロケールへの参照を含有してもよい。環境バッファは、その実行経路をリダイレクトするために、それを使用するコードレットによって修正されてもよい（例えば、返信をもたらすために、それを反転させることによって）。コードレットの現在の環境バッファは、実行を始動すると、コードレットにパスされることに加え、スレッドローカルメモリ領域内に記憶される、またはスレッドローカルポインタによって参照されてもよい。現在の環境バッファ（特に、現在かつ受信側ロケール）は、ランタイムによって使用され、配分およびスケジューリング要求が、完了されるべき、ロケールを選択してもよい。したがって、コードレットが、その環境バッファの受信側ポインタを別のスレッドのロケールを参照するように設定する場合、配分された任意のメモリは、デフォルトによって、そのスレッドロケールのアロケータから配分されてもよく、スケジューリングされた任意の他のコードレットは、デフォルトによって、そのスレッドにスケジューリングされてもよい。しかしながら、コードレットはまた、その環境バッファを迂回し、明示的に、そのような動作のための標的ロケールを指定してもよい。
【００３８】
本議論では、「リソース」を参照し、かつ参照されてきた。本願の目的のために、リソースは、プロセスまたはインターフェースを伴う、制御またはデータ依存性が存在し得るものである。すなわち、リソースが、ハードウェアを伴う場合、リソースは、本願の目的のために、そうでないことが指定されない限り（例えば、「ハードウェアリソース」、「デバイス」等として明示的に説明される）、ハードウェア自体ではなく、ハードウェアに対するソフトウェアインターフェース（例えば、ハードウェア処理デバイスに対するソフトウェアインターフェース）である。リソースは、必ずしも、そのように限定されないが、とりわけ、ＣＰＵスレッド／コアに対するインターフェース等の処理リソース；ディスク上のオンまたはオフチップＲＡＭおよびファイルに対するインターフェース等のストレージリソース；ネットワークソケット等の通信リソース；共有データ構造；および実行可能コードを含んでもよい。リソース相互作用は、ｇｅｔおよびｐｕｔ動作の使用を通して生じてもよい。ｐｕｔ動作は、データをリソースにプッシュするために使用され、終了すると、その呼び出しプロセスの代わりに、いくつかのユーザ指定チェーンコードレットの実行を生じさせてもよい一方、ｇｅｔは、リソースからデータを抽出するために使用されてもよく、終了すると、ユーザ指定チェーンコードレットの実行を生じさせてもよい。ｇｅｔおよびｐｕｔ動作に与えられるチェーンコードレットは、「完了コードレット」と称される、または当該動作の完了後のみ、実行するため、関連付けられたチェーンコンテキストとともに、「完了ペア」と称される。
【００３９】
相互作用リソース間のツリー状「対話」を促進するために、本発明の実施形態は、「キー」を使用して、リソースとのデータ／制御交換をマークしてもよい。キーは、リソースとの一連の相互作用の状態のための記述子として、またはそのような記述子のためのセレクタ（すなわち、記述子への直接または間接ポインタ）として作用する。各ｐｕｔおよびｇｅｔ動作は、リソースの挙動に従って、キー値を受け取り、および／または生成することができる：
・ｐｕｔ／ｇｅｔのためのヌルキーをパスすることは、新しい対話を開始するために使用されてもよい。そのような動作は、任意の具体的な以前のｐｕｔ／ｇｅｔ動作を参照するとみなされないが、リソースの内部状態を暗黙的に参照することができる。
・ｐｕｔ／ｇｅｔからヌルキーを生成することは、いずれの後の動作も、現在の対話が、交換を終了させるために試行されるべきではない、またはその必要がないことを示してもよい。しかしながら、リソースに応じて、以前のｐｕｔ動作にパスされたキーを再び参照することが可能であってもよい。
・ｐｕｔ／ｇｅｔのための非ヌルキーをパスすることは、既存の対話を参照してもよく、キーを生成した以前のものと動作を関連付けてもよい。キーを複数回使用することは、リソースによって可能となる場合、第１のものから分岐する複数の対話を開始してもよい。しかしながら、本挙動は、いくつかの状況に対してのみ適切であり得る。
・ｐｕｔ／ｇｅｔから非ヌルキーを生成することは、後の動作が、現在のものを参照し得ることを示してもよい。
・それを生成しなかったリソースにキーをパスすることは、エラーをもたらし得、キーは、ランタイム環境内の特定の領域に局在し得る場合がある。
【００４０】
図３は、キーパッシングによってサポートされ得る、３種類の対話を図示する。図３において、「（ａ）」によって指定される対話は、単一動作対話であってもよい。本対話では、ヌルキーは、動作入力として示され、ヌルキーは、動作によって生成される。対話（ｂ）は、順次対話と考えられてもよい。本対話では、ヌルキーは、それに応答してキー１が生成され得る、第１の動作入力として使用されてもよい。キー１は、次いで、第２の動作への入力として使用されてもよく、キー２は、第２の動作によって生成されてもよい。キー２は、次いで、ヌルキーを生成し得る、第３の動作への入力であってもよい。最後に、対話（ｃ）では、ヌルキーは、キー１を生成し得る、第１の動作への入力として使用されてもよい。キー１はまた、ヌルキーを生成し得る、さらなる動作への入力として使用されてもよい（第１の動作と連続して、または並行のいずれかにおいて）。
【００４１】
本発明の実施形態は、コードレットコンプレックスコンテキストによって使用されるコンテキストの設定および分解を抽象化し、また、従来のＬＩＦＯ要求−応答挙動の並列化形態が必要とされる時、コンプレックスを支援し得る、高レベル構成概念をサポートしてもよい。ネイティブ関数コールの使用は、ＡＰＩコールまたは少量の計算等、共通場所または軽量アクションに対しては、完全に容認可能であり得るが、プログラム内のより大きな関数は、「高レベルプロシージャ」を利用することによって、リソースの観点から実装されてもよい。
【００４２】
プロシージャは、任意の他のリソース同様に処理されてもよく、パラメータをプロシージャにｐｕｔする、および／または関連付けられたリターン値をプロシージャからｇｅｔすることができる。本発明の実施形態による、プロシージャは、リソースとみなされ得るため、各プロシージャは、関連付けられた実行可能コードを伴うメモリ内の小リソース記述子として、ランタイムのビュー内に存在する。
【００４３】
アクティブに実行中のプロシージャ毎に、前述のように、その状況または状態（例えば、変数およびキャッシュ値）を記録するために、プロシージャによって使用される、任意の情報を記憶する、関連付けられたコンテキストを有する。ｐｕｔが、プロシージャ上で呼び出されると、新しいプロシージャコンテキストが、プロシージャ起動の開始に備えて、作成されてもよく、そのある部分は、パラメータ入力によって初期化され、ある部分は、リターン値のために留保され、残りは、実行の間、プロシージャ自体の使用のために留保される。コンテキストが作成されると、プロシージャのための任意のエントリコードレットが、起動するようにスケジューリングされてもよく、コードレットは、加えて、発呼側に、ｐｕｔが完了したことを通知するようにスケジューリングされてもよい。発呼側が、プロシージャの出力値を要求すると（または、出力値が不在の場合は、発呼側が、プロシージャの完了の通知を要求すると）、オリジナルｐｕｔから返され得るキーを使用して、ｇｅｔをプロシージャリソースに発行してもよい。プロシージャが、実行を完了し、出力値を生成すると、該当する場合、値は、前述のｇｅｔ動作から、完了コードレットを介して、発呼側にパスされてもよい。イベントの順序は、プロシージャリソースと相互作用する時、最小限に順次的であることに留意されたい。すなわち、プロシージャコンテキストは、初期ｐｕｔ動作後、随時、初期化されてもよく、ｐｕｔ完了コードレットは、エントリコードレットが開始された後、随時、実行されてもよく、ｇｅｔ動作は、完了コードレットが開始後、随時、開始されてもよく、ｇｅｔ完了コードレットは、プロシージャが完了後、随時、開始されてもよい。
【００４４】
そのようなランタイムおよび実行モデルに対する拡張機能が、高レベル同時ルーチンとして作用するプロシージャのためのサポートを提供してもよい。具体的にキー指示されたｐｕｔ動作を使用することによって、連続値を実行プロシージャにプッシュすることができ、複数のｇｅｔ動作を使用することによって、値をプルすることができる。これは、チェックポイントを行うことができる、またはそのコンテキストをバージョン化することができる、プロシージャに対して、あるいはプロシージャの実行の特定の分岐が、異なる入力値によって再開することができる場合、特に有用であり得る。また、プロシージャとその発呼側との間に要求−応答相互作用パラダイムを確立するために有用であり得る。
【００４５】
本発明の実施形態では、ストレージリソースは、特定のメモリ領域のためのマネージャとして作用してもよい。オブジェクトが、ストレージリソースにｐｕｔされると、オブジェクトのための空間が、配分されてもよく、オブジェクトは、複製されてもよく、オブジェクトのためのキーが、生成されてもよい。ストレージ空間の要求される量が、利用不可能である場合、ｐｕｔは、要求を直ぐに満たすことが不可能であり得、完全に失敗する、または二次ストレージ装置にフォールバックする場合さえある。
【００４６】
ストレージリソース内に記憶されたデータが、それをリソース内に配置したｐｕｔから生成された対話キーを使用して、アクセス可能であってもよいが、また、アドレス可能メモリに「マップ」され、アプリケーションが、データがアクセスされ得る、ローカルポインタを得ることを可能にしてもよい。図７は、ストレージリソース、アプリケーションのローカルアドレス空間、およびマッピング要求を満たすために使用されるストレージ−リソース−プライベートアドレス空間の間の関係の概念的略図を示す。直接、所望のリソースにマップする、アドレスを得ることが不可能である場合、記憶されたオブジェクトのローカルコピーが、代わりに、作成されてもよい。本発明のいくつかの実施形態は、マッピングに行われた変更（コピーされたオブジェクトを含む）を自動的に同期させてもよい。他の実施形態は、変更を同期させるために、ストレージリソースと明示的相互作用を要求してもよい。もはや必要されなくなると、マッピングは、アドレス範囲またはそれと関連付けられたメモリを解放するために破壊されてもよい。マッピングは、加えて、マッピングのためのアクセス許可および／またはキャッシング規範等の選択肢を含み得る、ユーザが、データがどのように使用され、所望のマッピングがどのように行われるべきかを指定することを可能にしてもよい。マップされたデータが、複数のアプリケーションコンポーネント間で共有され得るかどうかに関して、推測的に任意の保証を行うことは不可能であり得ることに留意されたい。すなわち、ストレージリソースが、マップされた範囲のローカルコピーを維持しなければならないことを把握している場合でも、そのローカルコピーは、ローカルに行われる場合、依然として、共有され得る。
【００４７】
ストレージリソースは、非ローカルデータをハンドリングするために、便宜的抽象化をもたらし得るが、ユーザコードは、必要ならば、依然として、マッピングローカリティを記録する必要があってもよい。例えば、１つのスレッド上で起動している間、ローカルである、マッピングは、別のスレッド上で起動している間、ローカルでなくてもよい。これは、マッピングのユーザが、異なるスレッドへの再スケジュール間において、マップ解除する、または任意の再スケジュールが、同一スレッド上で生じることを確実にすることのいずれかを必要とし得ることを意味する。
【００４８】
直接、実行中のコードレットにアクセス可能なアドレス空間を管理し、かつそれにアクセスするために、コードレットに、そのデータをマップおよびマップ解除することを要求しない、ストレージリソースは、具体的には、「アロケータ」と称されてもよい。前述のように、ロケール毎に、それに付随する任意のメモリおよびその従属メモリを管理し、それとともに、コードレットのコンテキスト、入力、および他の付随的データが、記憶される、関連付けられたアロケータを有する。スレッドのスタック、ヒープ、静的データ、および／またはコードもまた、ストレージリソースとともに保持されてもよい。各コードレットの環境バッファは、配分要求のための適切なアロケータを選択するために使用され得るが、いくつかの実施形態は、他の要因を考慮してもよく、またはある場合には、潜在的に、環境バッファ全体を軽視してもよい。
【００４９】
処理リソースは、本発明の実施形態のさらなるコンポーネントを構成してもよい。処理リソースは、概して、ｇｅｔ完了コードレットのスケジューリングを可能にしてもよい。例えば、ヌルキーからｇｅｔすると、リソースは、次に適合するとみなす時は常時、コードレットをスケジューリングしてもよい。より精密な制御が、必要とされる場合、処理リソースは、ｐｕｔによってプッシュされたジョブ記述を受け取ってもよく、そのｐｕｔから生じるキーは、１回以上、ｇｅｔによって使用され、より精密なパラメータによってジョブをスケジューリングしてもよい。本発明のいくつかの実施形態では、ある処理リソースは、ハードウェアスレッド毎に作成されてもよく、１つ以上の代表リソースが、その上の層内に作成されてもよい。
【００５０】
最も一般的型の処理リソースは、コードレットスケジューラ（または、単に「スケジューラ」）であるが、処理リソースはまた、ソフトウェアインターフェースをグラフィック処理ユニット（ＧＰＵ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、または他のプロセッサおよびコプロセッサハードウェアに提供してもよい。スレッドレベルスケジューラは、実際には、スケジューリングされたコードレットインスタンスを起動し得るが、より高いレベル（例えば、プロセッサホストレベル）スケジューラは、コードレットインスタンスおよびスケジューラが、利用可能となるのに伴って、コードレットインスタンスをバッファし、それらをスレッドレベルスケジューラにフォワードするために使用されてもよい。
【００５１】
リーフロケールのスケジューラ（または、「リーフスケジューラ」）は、スケジューリングされたコードレットのデック（両端キュー）を管理してもよい。それ自体内からロケールにスケジューリングされたコードレットは、典型的には、他のコードレットより優先され、かつより高速のスケジューリング／ディスパッチ経路が与えられてもよい。これは、要件ではないが、速度最適化を支援し得る。非リーフスケジューラは、典型的には、より高速またはより低速経路も伴わずに、より単純なワークデックを管理してもよい。
【００５２】
通常動作下、各リーフスケジューラは、ランタイムコアによって繰り返し介入されてもよく、それぞれのスケジューリングデックの先頭におけるコードレットインスタンスをポップオフおよび実行させ得る。リーフスケジューラが、空のデックを有する場合、その親ロケールに対するスケジューラは、コンサルトされ、いくつかのワークをリーフスケジューラに与えるよう依頼される。親のスケジューリングデックに何らかが存在する場合、そのデックの先頭は、ポップオフされ、実行のために、リーフスケジューラにパスされてもよい（図９（ａ））。そうではない場合、親は、リーフスケジューラの兄弟スケジューラのうちの１つから、ワークのスティールを試みてもよく、成功する場合、兄弟スケジューラの最後尾からそのワークを除去してもよい（図９（ｂ））。兄弟スケジューラが、行うべき任意のワークを有していない場合、親は、その親にコンサルトしてもよく、プロセスは、本様式を継続してもよい。いずれのワークも、リーフスケジューラに対して見つけられ得ない場合、それおよびその関連付けられたスレッドは、より多くのワークが到着するまで、アイドル（例えば、低電力）状態に置かれてもよい。
【００５３】
コードレットは、意図された挙動に応じて、スケジューラのデックの両側にスケジューリングされてもよい。スケジューリングは、典型的には、次にスケジューリングされたものが、最後に実行されるものとなり、ほぼ先入先出（ＦＩＦＯ）の順序を維持するように、デックの最後にダイレクトされてもよい。しかしながら、スケジューリングはまた、次にスケジューリングされたものが、次に実行されるものとなり、ほぼＬＩＦＯの順序を維持するように、デックの先頭にダイレクトされてもよい。後者の形態は、例えば、深い再帰呼び出しが用いられる場合、分岐スケジューリング要求によって、全利用可能なメモリを占有することを回避するために有用であり得る。本発明の異なる実施形態におけるスケジューラは、内部的には、デックベースではなくてもよく、実行するためのコードレットを選択する時、要求順序以外の要因を考慮してもよいことに留意されたい。加えて、いくつかの実施形態のスケジューラは、ヒントと同程度にＦＩＦＯおよびＬＩＦＯ順序化スケジューリング間のアプリケーションベースの区別を扱ってもよく、またはそれを完全に軽視してもよい。（例えば、スケジューラは、プログラム要求ＦＩＦＯまたはＬＩＦＯ順序を大部分または全体的に無視する、動的スケジューリング決定が、ＦＩＦＯ／ＬＩＦＯ順序を綿密に履行するものより優れた性能をもたらすように、プログラムの挙動に関する予測を動的に行うことが可能であってもよい。）
【００５４】
本発明の実施形態はさらに、通信および／または同期リソースを含んでもよい。通信リソースは、プログラムの異なる部分間において、データを渡すために使用されてもよく、コードレット、ノードレット等のように、ランタイム抽象化に関与し得る、低レベルストリームまたはメッセージベースの通信インターフェースにわたって、より高いレベルの抽象化を可能にし得る。同期リソースは、セマフォ、バリア等のコードレットベースの実装へのアクセスを提供してもよい。
【００５５】
本発明の実施形態による、有用概念の１つは、ノードレットであり得る。ノードレットは、共有サービスを介して、アクセスされ、例えば、いくつかの種類のネットワークソケットにわたって、利用可能となり得る、リソースおよび／またはコードレットの集合である。これは、例えば、共有される必要があり得る、メモリおよびリソースアドレスの管理を促進し、アプリケーションが、ホストとアドレス空間との間のアドレスマッピングを動的に管理する必要性を回避することを可能にし得る。対照的に、ノードレットは、それらをノードレットにレジスタすることによって、具体的パブリックリソースおよびコードレットへのより広範なアクセスを可能にさせ得る。ノードレットは、（ａ）サーブされたリソースを初期化し、任意の必要とされるバックグラウンドコードレットコンプレックスを開始し、（ｂ）エクスポートされたリソースのレジストレーションを管理し、（ｃ）サーブされたリソースへのアクセスを制御し、（ｄ）ノードレットの使用と関連付けられた補助状態を管理し、（ｅ）アクセスパターンの最適化を制御し、および／または（ｆ）ノードレットがシャットダウンされると、サーブされたリソースの初期化を解除してもよい。ノードレットは、ランタイム環境内で明示的に作成および開始されてもよく、または自動的に開始されてもよい（例えば、構成ファイル内の動的ライブラリにネーム付けすることによって）。ノードレットはまた、明示的にアクセスされると、ネットワークサービスに伴って即時、またはオンデマンドで、開始されてもよい。リソースが、ノードレットにレジスタされると、ｐｕｔ／ｇｅｔ要求は、遠隔で発行され、それらとローカルに相互作用してもよい。同様に、コードレットが、ノードレットにレジスタされると、遠隔要求によって、ローカルに開始されてもよい。バイトシリアライゼーションは、ある場合には、データ転送のために、必要とされてもよい。
【００５６】
多くのリソースは、ｇｅｔおよびｐｕｔプリミティブに勝る特徴を提供し得るため、ノードレットはまた、適切な型および機能性を伴うプロキシリソースが、ローカル要求を遠隔要求に変換するためにセットアップされ得るように、いくつかの遠隔型イントロスペクション機能を提供してもよい。例えば、ストレージリソースは、ネットワークにわたって提供されることができない、マッピング／マッピング解除関数を提供してもよい。これらの関数は、例えば、遠隔リソース内の実際のストレージを管理するために、転送されたｇｅｔおよびｐｕｔを使用して、その中に挿入された、またはそこから読み出された、オブジェクトのローカルキャッシュを維持し得る、プロキシリソースによって、ローカルにエミュレートされてもよい。
【００５７】
ノードレットの実装は、内部リソースおよびコードレットのための外部接続を多重化してもよい。ノードレットは、例えば、整数によって識別され得る、一式のリソース／コードレットの周囲に「ラッパ」を提供するとみなされてもよく、それらのリソース／コードレットと特定の方法において相互作用するために、それをダイレクトし得る、間接ｐｕｔ／ｇｅｔ要求メッセージを受け取ってもよい。ノードレットは、プロキシとして作用するが、その遠隔相手側と同様に見え、遠隔ノードレットにフォワードされるサロゲートとのローカル相互作用を可能にする、サロゲートをローカルに確立することによって、遠隔リソースおよびコードレットへの透過的アクセスを提供してもよい。ノードレットが、ｇｅｔ要求メッセージを遠隔要求側から受信すると、要求をローカルリソースにフォワードしてもよく、ｇｅｔ動作が完了すると、ｇｅｔの結果が、要求側に返されることができる。ノードレットが、ｐｕｔ要求メッセージを受信すると、パラメータをメッセージからプルし、即、適用可能であるサロゲートリソースにｐｕｔしてもよく、再び、ｐｕｔ完了を要求側にフォワードしてもよい。ノードレットが、コードレットを実行するための要求を受信すると、コンテキストおよび入力パラメータを要求メッセージから抽出し、要求されたコードレットをローカルに起動してもよい。すなわち、コードレットが、そのチェーンペアを起動すると、その入力は、要求側にフォワードバックされることができる。実施形態は、要求側のコードレットが、さらなるチェーンコードレットをノードレットのローカル側にトリガバックされ得るように、さらなるチェーンペアのための識別をフォワード可能にしてもよい。本プロセスは、潜在的に、ノードレットの両側のコードレットが、双方向的にデータを交換し続ける場合、無限に繰り返され得る。
【００５８】
ノードレットを開始すると、ローカルコードレットおよびリソースは、遠隔要求側が、それらと相互作用し得るように、それにレジスタされてもよい。ノードレットはまた、遠隔リソース／コードレットとローカルサロゲートとの間の関連付けを確立し、それらとの相互作用を提供してもよい。いくつかの実施形態は、遠隔リソース／コードレットのレジストレーションまたは検出およびそれとの関連付けのためのローカルリソース／コードレットの自動検出およびレジストレーションを提供してもよく、実施形態は、アプリケーションに、リソース／コードレットにレジスタし、それと関連付けることを可能にする、またはそれを要求してもよい。
【００５９】
図６は、本発明の種々の実施形態による、３つのリソースマッピングを伴うノードレットを示す。ノードレットは、ＩＤ１、２、および３のための仮想化されたリソースを提供してもよく、それぞれ、そのｐｕｔおよびｇｅｔ動作を他のリソースに接続させてもよい。
【００６０】
プログラムレットもまた、本発明のいくつかの実施形態において使用されてもよい。プログラムレットは、そのコンポーネントが、抽象形態において、ランタイムソフトウェアに提示され、解釈される、またはネイティブコードに動的にコンパイルされ、本発明の分散型ランタイム環境の実施形態において起動され得る、プログラムとみなされてもよい。プログラムレットは、関与するリソースの場所の推測的知識を伴わずに、接続されたランタイムにわたって、ワークロードの自動分散を可能にしてもよい。すなわち、プログラムレットの抽象プログラム形態は、ランタイムシステムが、プログラムを構造的に操作し、そのデータおよび計算を知的に配列および分散することを可能にし得る。プログラムレットは、ランタイムにおいて、以下の能力を可能にし得る：（ａ）データの大きなチャンクを分割し、それらをランタイムシステム内の他のロケールにプッシュする、（ｂ）固有並列が、再編成および利用され得るように、長い計算を分割する、（ｃ）データおよびコードローカリティを管理する（例えば、データの大きなチャンクを分割し、それらを複数のノードにわたって拡散させる；非集計データを合体または統合する；長い計算をノードにわたって、タイミングをとり、スケジューリングする；データを複製、キャッシュ、および共有する；および／またはデータへの変更を伝搬することを含んでもよい）、（ｄ）リソース使用およびオーバーヘッドを追跡し、制限し、および／または優先順位をつける、（ｅ）ガーベッジコレクション、（ｆ）解釈、動的コード生成、および関連付けられた状態の管理、および／またはアプリケーションの高レベル表現。
【００６１】
分散型または多重スレッド化プログラムを作成時、遭遇し得る問題は、特に、配置、移行、および寿命の観点における、データの管理である。本ランタイムシステムの実施形態は、高レベルオブジェクト指向型システムを使用して、これらの懸念に対処することに役立ち、かつランタイムシステム、プログラマ、およびユーザによる、ランタイム動作を支援するための他の拡張機能を提供し得る。
【００６２】
型は、それらの型が属するメモリ内のオブジェクトの具体的レイアウトを識別および記述するために使用され得る。型が、オブジェクトに属する場合、そのオブジェクトは、その型のインスタンスと言え得る。本発明の実施形態は、メモリ内のオブジェクトのレイアウトおよびそれらのオブジェクトとの潜在的相互作用を規定し得る、「基本型」と、基本型が有していなければならない型要件を記述する、「統合型」とを含む、異なる種々の型を確立し得る。基本型はさらに、オブジェクトのレイアウトおよび全許容される相互作用を完全に記述し得る、「具象型」と、レイアウトおよび許容される相互作用を部分的に記述し得る（したがって、具象型の一部としてではない限り、インスタンス化することができない）、「抽象型」と、許容される相互作用のみ指定し、さらなる相互作用オーバーヘッドを要求するが、インスタンスオブジェクト内の付加的ストレージオーバーヘッドを要求しなくてもよい、「インターフェース型」とに分類され得る。実施形態は、型に関する付加的変形例をサポートしてもよい（例えば、型の具象連結、結合、およびアレイ、より広い空間であるが、より少ない時間オーバーヘッドを伴う、フォームインターフェース型等）。
【００６３】
本発明の実施形態では、より基本的区別は、「低レベル」と「高レベル」型との間で行われ得る。低レベル型は、固定サイズ整数および実数等のプリミティブ型、アーキテクチャポインタ、ならびにアレイ、記録、および結合型におけるこれらの組み合わせを含んでもよい。対照的に、高レベル型は、メモリ内にある定義の明確であって、解読可能、かつ有限である形式を伴う、オブジェクトを記述する。高レベル型は、オブジェクト指向上位／下位クラス関係の従来の概念を拡張し得る、上位型関係によって、直接、ある数の他の高レベル型に関連し得る。型Ｔが、上位型の型Ｓ（または、同等に、Ｓは、下位型のＴである）である場合、型Ｔと関連付けられた全ストレージおよび相互作用もまた、Ｓと関連付けられる。すなわち、実際は、これは、型Ｓのインスタンス毎に、Ｓによって、Ｔから継承されるストレージを参照する時に使用され得る、型Ｔのインスタンスを含有することを意味し得る。上位型／下位型関係に密接に関連するのは、割当可能関係である。型Ｔが、型Ｓに割当可能である場合、型Ｔのオブジェクトを参照するポインタ値は、型Ｓをポイントする変数に割り当てられてもよく、または換言すると、Ｓは、Ｔの上位型またはそれと同一型である。ステートメント「Ｓは、Ｔの下位型である」は、以下、象徴的に、
【００６４】
【数１】
2013546106.tif 000003
【００６５】
と表され、ステートメント「Ｓは、Ｔに割当可能である」は、
【００６６】
【数２】
2013546106.tif 000004
【００６７】
と表され得る。否定形態
【００６８】
【数３】
2013546106.tif 000005
【００６９】
および
【００７０】
【数４】
2013546106.tif 000006
【００７１】
もまた、Ｓが、それぞれ、Ｔの下位型ではない、またはそれに割当可能ではないことを示すために使用され得る。下位型関係は、推移的であることに留意されたい。したがって、型Ｒ、Ｓ、およびＴに対して、
【００７２】
【数５】
2013546106.tif 000007
【００７３】
および
【００７４】
【数６】
2013546106.tif 000008
【００７５】
である場合、
【００７６】
【数７】
2013546106.tif 000009
【００７７】
となる。
【００７８】
ランタイムシステム内の高レベルオブジェクト毎に、関連付けられた高レベル型を有してもよく、本発明のランタイムシステムの実施形態における型毎に、ランタイム時に、任意のオブジェクトの型を検査するために使用することができる、メモリ内の関連付けられた型記述子オブジェクトを有してもよい。イントロスペクションは、プログラマに、後の検査のために、型の要素にネーム付けし、それをエクスポートする能力を提供する。加えて、第１のクラス型オブジェクトは、コンパイル時言語環境が、ランタイム時、任意に拡張され得る、かつプログラムコンポーネントの移行を簡略化し得るように動的に作成されてもよい。（例えば、ホストＡが、型Ｔを使用して、ホストＢにワークをオフロードする必要がある場合、ホストＢは、型Ｔのそれ自体のコピーを動的に取得し、再コンパイルまたは再開される必要なく、そのワークを行ってもよい。Ｂは、潜在的に、必要時、Ａにフォワードバックされ得るが、その他の点では、ＴのホストＡのバージョンと同じに見え得る、プロキシ型をさらに作成してもよい。）
【００７９】
イントロスペクションの別の層が、基本型−ａｓ−ｏｂｊｅｃｔ層の上部に追加されてもよい。すなわち、各型オブジェクトは、オブジェクトの状態が、言語固有名を使用することによって、ランタイム時、アクセスされ得るように、型要素の記述を含んでもよい。これは、多くのスレッド化または分散型アプリケーションが、従来の二値イメージベースのデバッガが、ハンドリングすることができるものより高いレベルにおいて、デバッグすることを可能にし、アドレス空間とアプリケーションとの間のオブジェクトの機能性の分散を簡略化するのに役立ち得る。
【００８０】
型システムの実施形態は、多様性、仮想インヘリタンス、および／またはインターフェース型をサポートし、Ｃ＋＋、Ｃ＃、およびＪａｖａ（登録商標）等のプログラミング言語を使用して、既存のシステムとの完全相互運用性を可能にしてもよい。本発明のランタイムシステムの実施形態はまた、型統合をサポートしてもよく、複数の型が、型結合、交差、否定、および／または減算演算子を使用して、式中で組み合わせられてもよい。本発明の実施形態は、無限数のコンポーネント型を含んでもよいが、それらは、他の型に対して整合され、例えば、遠隔接続の両側が、通信を伴わずに、接続の他方側に向けたパラメータおよびリターン値を型チェックすることを可能にし得る、コンパクト表現を提供し得るため、必ずしも、統合型のインスタンスを作成可能にする能力を含むことが要求されなくてもよい。
【００８１】
２つの特殊な高レベル型は、種々の実施形態によるランタイムシステム内に存在し得る、すなわち、ＡｎｙおよびＶｏｉｄである。Ａｎｙは、ランタイムによって、インターフェース型として確立され、包括型ワイルドカードとして使用され、汎用セットとして、統合型式に関与し得るように、全他の高レベル型の上位型として作用してもよい。Ｖｏｉｄは、全他の型の下位型として作用し、排他的ワイルドカードとして使用され、ヌル（空の）セットとして、統合型式に関与してもよい。Ｖｏｉｄのインスタンスは、必然的に、全他の可能な型のインスタンスを含有するであろうため、型Ｖｏｉｄに対する唯一の有効ポインタは、ＮＵＬＬであり得る。（これは、任意の型へのポインタに割当可能として、ＮＵＬＬポインタ値を確立することに留意されたい。また、ランタイムソフトウェアの特定の実施形態は、特定のハードウェア／ソフトウェアロケールに対して、ＮＵＬＬポインタをサポートしてもよいことに留意されたい。例えば、小ローカルメモリ内で起動するハードウェアプロセッサコアは、そのＮＵＬＬに対して、アドレス０を使用してもよいが、そのコア外からは、その同一アドレスは、［例えば］６５，５３６のある倍数としてマップされてもよい。これは、ＮＵＬＬが、代替として、いずれのオブジェクトも全く参照しない、またはコードレットが含有するロケールと関連付けられたメモリ全体を参照することを可能にし得る。）型システム内のＡｎｙ、Ｖｏｉｄ、および他の型間の関係は、図８（ａ）に示される。
【００８２】
いくつかの実施形態では、型システムは、データパーティション化、コピー、シリアライゼーション、および／またはデシリアライゼーションルーチンの実装を許可、容易化、または向上させ得る。固定幅整数または実数等のプリミティブデータ型は、容易にコピーおよび移行され得るが（バイト順にかかわらず）、より高いレベル型は、それらと関連付けられた任意の量のコンテキストを有してもよく、それらのいずれも、オブジェクトが、異種アドレス空間間で移動される時、トランスポート、再構築、または破棄される必要がなくてもよい。インターフェース型ＣｏｐｙａｂｌｅおよびＴｒａｎｓｆｅｒａｂｌｅは、これらの目的のために使用されてもよく、Ｃｏｐｙａｂｌｅは、同一アドレス空間内のオブジェクトを複製するために有用であり得、Ｔｒａｎｓｆｅｒａｂｌｅは、オブジェクトをバイトストリームに縮小する（シリアル化）、またはオブジェクトを生成されたストリームから再構成する（デシリアル化）ために有用であり得る。
【００８３】
加えて、大きなアレイ、セット、またはマップ等のいくつかのオブジェクトを、相互に独立して使用され得る、断片にパーティション化することが望ましくあり得る。そのような構造は、Ｐａｒｔｉｔｉｏｎａｂｌｅを実装し、インデックスとパーティションとの間に関数マッピングが与えられる場合、そのコンポーネントが、異なるリソースに割り当てられる、または異なるホストにプッシュされ得るように、分割されてもよい。Ｐａｒｔｉｔｉｏｎａｂｌｅオブジェクトはまた、全てのインデックスが同一パーティションにマップされ得るように、それらに一定のインデックス−パーティションマッピングを与えることによって、パーティション化されずに残されてもよい。
【００８４】
種々の実施形態による、型システムは、統合型の形態において、集合論的結合、交差、減算、および／または否定動作（例えば、リソースに対する入力および出力制約を指定するため）の使用を可能にし得るが、その実装は、完全に記述されなくてもよいため、直接、それ自体、そのような型をインスタンス化可能でなくてもよい。統合型は、ランタイム時の型間の関係を判定するために使用され得る、メモリ内のデータ構造とともに記述されてもよい。統合型は、静的または動的に作成されてもよく、可能である時、縮小およびキャッシュされてもよく、これは、基本型等価チェックのための直接ポインタ比較を可能にし、未使用データ構造の蓄積を回避するのに役立ち得る。
【００８５】
集合論的式に基づく型の判定をさらに検討すると、前述のように、
【００８６】
【数８】
2013546106.tif 000010
【００８７】
は、型によって受け取られたオブジェクトのセットを組み合わせる、またはフィルタリングするために使用されてもよい。例えば、型Ｔおよび統合型ＵおよびＶに対して、集合論におけるように、
【００８８】
【数９】
2013546106.tif 000011
【００８９】
となる。同様に、
【００９０】
【数１０】
2013546106.tif 000012
【００９１】
となる。ある型はまた、別の型から減算されてもよい。すなわち、
【００９２】
【数１１】
2013546106.tif 000013
【００９３】
となる。最後に、Ａｎｙからの減算に相当する、型否定は、
【００９４】
【数１２】
2013546106.tif 000014
【００９５】
となるような型をもたらす。再び、集合論におけるように、
【００９６】
【数１３】
2013546106.tif 000015
【００９７】
、
【００９８】
【数１４】
2013546106.tif 000016
【００９９】
、
【０１００】
【数１５】
2013546106.tif 000017
【０１０１】
、
【０１０２】
【数１６】
2013546106.tif 000018
【０１０３】
、
【０１０４】
【数１７】
2013546106.tif 000019
【０１０５】
、
【０１０６】
【数１８】
2013546106.tif 000020
【０１０７】
、
【０１０８】
【数１９】
2013546106.tif 000021
【０１０９】
、および
【０１１０】
【数２０】
2013546106.tif 000022
【０１１１】
となる。ド・モルガンの法則の応用（
【０１１２】
【数２１】
2013546106.tif 000023
【０１１３】
および
【０１１４】
【数２２】
2013546106.tif 000024
【０１１５】
）を含む、ブール代数変換は、これらのルールを使用して、統合型で行われ、例えば、型を内部表現のための特定の形態に縮小してもよい。
【０１１６】
ユーザ構築型は、複数の同じ上位型を含んでもよい。（例えば、図８（ｃ）に示されるように、型Ｑ、Ｒ、Ｓ、およびＴを前提とすると、Ｔの任意のインスタンスは、ＲおよびＳのそのインスタンス内に各１つずつ、型Ｑの２つのインスタンスを含まなければならない。）本発明の異なる実施形態は、異なる方法において、そのような型内で型変換を行ってもよい。例えば、ランタイムは、ＲまたはＳの個別のインスタンス内に含有されるインスタンスを選択することによる、ＲまたはＳからＱへの型変換を除いて、ＱのＲのインスタンスを選択することによって、型ＴからＱに全型変換を実装してもよい。しかしながら、実装仕様にかかわらず、型のデータの実際の構造に関して把握しているプログラムは、依然として、直接、全上位型インスタンスにアクセスしてもよい。
【０１１７】
前述の型システムは、いくつかの実施形態では、Ｃ＋＋プログラミング言語において見られる「ｖ−ｔａｂｌｅ」アプローチの拡張機能を使用して、実装されてもよい。本アプローチでは、任意の高レベルオブジェクトのメモリイメージは、オブジェクトが有する任意の上位型を含む、オブジェクトの型を記述する、テーブルへのポインタから始まる。加えて、ｖ−ｔａｂｌｅは、仮想メソッドおよびコードレット実装、ならびに他の型関連データ（例えば、その値が、その型に特有であるが、その下位型にはそうではない、型の全インスタンス間で共有される変数）へのポインタを含んでもよい。各高レベル型は、それと関連付けられたそのような型データテーブルの１つを有してもよく、その型の全インスタンスは、そのメモリイメージ内でそれを参照してもよい。さらに、このような型テーブルは、本発明のいくつかの実施形態では、統合型式ならびに具象型情報を表すために使用されてもよい。
【０１１８】
型階層内のポインタ型間で変換時、型変換の種々の形態が、正しいポインタが使用されることを確実にするために使用されてもよい。もたらされる最も単純な型変換は、下位型へのポインタから、上位型へのポインタへの型変換である、「アップキャスト」である。実施例として、図８（ｃ）からの型を使用すると、型Ｒへのポインタから型Ｑへのポインタへの型変換は、アーキテクチャポインタの幅だけ、Ｒインスタンスのアドレスをオフセットすることによって、または、プログラミング言語内において、適切な上位型インスタンスのアドレスをとることによって（例えば、Ｃにおける＆ｐｔｒ−＞ｓｕｐｅｒ）、行われてもよい。同じことは、型階層内の任意の数のレベルを上方型変換するために行われてもよい。すなわち、ＴからＱの型変換は、ＴからＲ、次いで、ＲからＱ、または代替として、ＴからＳ、次いで、ＳからＱへの型変換によってもたらされてもよい。上位型から下位型への型変換（例えば、ＱからＲ、あるいはＲまたはＳからＴ）、または「ダウンキャスト」は、アップキャストを反転する（概して、加算する代わりに、オフセットを減算する）ことによって行われてもよい。下位型の上位型または上位型の下位型への型変換（「クロスキャスト」；例えば、ＲからＳ、これは、Ｔのインスタンス内で行われる）は、連続的に、２つの方法を組み合わせることによって行われてもよい（例えば、ＲからＱ、そこからＳ）。そのような型変換は、その結果を予測可能なコンパイラによって静的に、または本発明を具現化するソフトウェアによって動的にのいずれかにおいて、適用されてもよい。動的型変換は、各型の型データテーブル内に記憶されたデータを利用して、正しいオフセットを判定し、ポインタに適用してもよい。ランタイムの実施形態は、
【０１１９】
【数２３】
2013546106.tif 000025
【０１２０】
であるときに、型Ｓのオブジェクトを型Ｔに型変換しようとした場合、エラーを生成してもよい（例えば、関数リターン値、ネイティブ例外ハンドリング機構、またはコードレットのキャンセルフォークを介して）。
【０１２１】
本発明のランタイムシステムの実施形態における高レベルオブジェクトは、動的に追加、除去、または修正され得、かつオブジェクトとともに移行し得る、それに付随する任意のデータを有してもよい。コンテキストセンシティブおよびコンテキスト非センシティブデータは、オブジェクトに関するサイドバンドコメントとして作用し得る、タグを作成することによって、動的にオブジェクトに付随されてもよい。タグは、特定のオブジェクトが配置されるべき場所、コードレットが起動することが予期され得る時間、あるいはコードレットに対して好ましいまたは有益であり得る、環境への修正等、ランタイムにヒントを提供するために使用されてもよい。それらはまた、オブジェクトの配置または使用履歴の記録等、オブジェクトを使用するアプリケーションコンポーネント間に、第三者通信チャネルをもたらすために使用されてもよい。
【０１２２】
本発明のランタイムシステムの実施形態の種々の態様は、とりわけ、多くのスレッドおよび／またはノードにわたって、プログラム状態を追跡するために、監視および制御能力とともに実装されてもよい。ランタイムシステムのコンポーネントは、情報が、可能性として、ほぼリアルタイムにおいて、抽出、ログ、集約、表示され得るように、高レベルステータスインターフェースを具備してもよい。スケジューラはまた、例えば、複数のノードにわたって、単一スレッド、スレッドグループ、またはランタイムシステム全体の保留および検査を可能にし得る、集積制御インターフェースを具備してもよい。監視フロントエンドもまた、ランタイムシステムと相互作用するために提供されてもよい。
【０１２３】
ランタイムシステムの実施形態におけるコンポーネントは、ランタイムへのパブリックインターフェース定義のレジストレーションによって、モニタに可視となってもよい。これは、たとえそうであったとしても、ランタイムシステムに、コンポーネントによって提供されるステータス出力、ならびにそれらの出力内のデータの形式およびデータが集約または収集され得る方法を把握させる役割を果たし得る。ステータスインターフェースは、モニタシステムがそれと相互作用し得る方法を判定するために、前述の型システムに依存し得る。例えば、更新頻度、集約のスタイル、収集のスタイル、フォーマッティング、ラベリング、および／または場所情報等のパラメータが、型インターフェースを通して、提供されてもよい。カウンタ、タイマ、および／または列挙ビットセット等のビルトイン型の好適なセットが、ステータスインターフェースの迅速かつ容易な追加を可能にするために提供されてもよいが、ユーザ構築ステータス型も同様に、追加されてもよい。
【０１２４】
ランタイムシステムの実施形態におけるオブジェクトは、モニタが、その実行を動的に制御することを可能にし得る、制御オブジェクトをレジスタ可能にしてもよい。例えば、スケジューラは、スケジューリングが、ジョブ間で停止または開始することを可能にし、かつ具体的ジョブをスケジューリングから免除させることを可能にし得る、制御オブジェクトをレジスタしてもよい。試験インターフェースもまた、コンポーネントが、具体的タスクを行うことを可能にし得るように実装され、その結果が検査されてもよい。
【０１２５】
制御入力は、特殊モニタスレッドにおいて、アプリケーション特有コードの実行を生じさせ得る（例えば、コールバック関数を介して）、ローカルモニタインターフェースを使用して、促進されてもよい。これは、コールバックと、それらが影響を及ぼすオブジェクトとの間の同期を伴ってもよいが、ほとんどの制御コールバックは、単に、フラグを設定する、または最終的に、制御されたオブジェクトによって見られ得る、情報を上書きしてもよい。
【０１２６】
監視フロントエンドは、ランタイムシステム内からサーブされるソケットを介して、ランタイムシステムバックエンドに接続してもよい。バックエンドは、レジスタされた型、個々および集約ステータス情報、および／または制御情報への直接アクセスを可能にし、かつ潜在的に、遠隔ノードへの接続、リソースの作成／破壊／それとの相互作用、および／または作動可能ジョブのキル等、基本ランタイムタスクを可能にし得る。いくつかの実施形態では、バックエンドは、デバッガをランタイムシステム上で開始可能にし得る、「フック」を提供してもよく、したがって、フロントエンドがこれを行う必要性を排除または縮小させ、潜在的に、フロントエンドアクセスが制限され得る、複数の遠隔ノードに、初期化を分散し得る。
【０１２７】
本発明の種々の実施形態は、適切なインターフェースでラップされ、システムリソース上のコードコンポーネントとして使用される、システムの所与の実装とのリンカ／ローダレベルバイナリ互換性を有する、外部関数を可能にし得る。ランタイムシステム自体は、ＡＰＩとして使用するためのコードとリンクされ得る、静的または動的ライブラリとして具現化されてもよく、あるいはライブラリにリンクされた実行可能ファイルとして具現化されてもよい。本後者の形態は、ランタイムシステムをオペレーティングシステムによってアプリケーションコンポーネントに適用可能にし、かつランタイムシステムをノードレットおよび／またはプログラムレットと併用するための受動的サービスとして開始可能にし得る。
【０１２８】
本発明の種々の実施形態は、以下のようにメモリ配分規範を組み込んでもよい。参照によってランタイムインターフェース関数にパスされた値は、ランタイムインターフェースではなく、発呼側によって管理されてもよい。それらは、少なくとも、コールされたインターフェース関数が返すまで、存在したままであってもよく、ランタイムシステムが、そのような値を留保しなければならない場合、それらは、ランタイムシステムによってコピーされ、内部に留保／管理されてもよい。Ｎｏｎ−Ｃｏｐｙａｂｌｅオブジェクトは、可能である場合、コピーされるのではなく、性能に影響を及ぼさずに、間接的に参照される必要があってもよい。参照によってランタイムインターフェースからコードレットにパスされた入力値は、インターフェースにパスされた値と同様に扱われてもよい。そのような値のためのメモリが、明示的に管理されなければならない場合、チェーンペアは、その入力とともに、コードレットにパスされてもよい。すなわち、チェーンコードレットが起動されると、参照値に対する責任は、入力内で元々パスしたエンティティに返されたとみなされ得る（関数コールからのリターンに関して）。値が、その時点後に必要とされる場合、入力を受信するコードレットは、入力を（例えば、そのコンテキストに）コピーしなければならない。参照によってランタイムシステムから返された値は、３つカテゴリのうちの１つに分類され得る：（１）そのメモリが、もはやアクティブ使用中ではない時に解放される必要がない、静的またはスレッド−ローカルデータ、（２）含有オブジェクトがこれらのカテゴリの１つに分類され、かつそのデータのストレージが、コンテナの残留寿命に対して配分されたままである限り、含有オブジェクトと関連付けられるデータ、または（３）明示的に管理されるメモリおよび状態（例えば、ｃｒｅａｔｅおよびｄｅｓｔｒｏｙインターフェース関数を介して）。
【０１２９】
本発明が、特に、本明細書に図示および前述されたものに制限されるわけではないことは、当業者によって理解されるであろう。むしろ、本発明の範囲は、本明細書に前述される種々の特徴の組み合わせおよび部分的組み合わせ、ならびに前述の説明を熟読することによって、当業者に想起され、先行技術にはない、修正および変形例の両方を含む。
【図１】
2013546106.tif 000026
【図２】
2013546106.tif 000027
【図３】
2013546106.tif 000028
【図４】
2013546106.tif 000029
【図５】
2013546106.tif 000030
【図６】
2013546106.tif 000031
【図７】
2013546106.tif 000032
【図８】
2013546106.tif 000033
【図９】
2013546106.tif 000034
【図１０】
2013546106.tif 000035
【国際調査報告】
2013546106.tif 000036
2013546106.tif 000037
2013546106.tif 000038