(57)【特許請求の範囲】
【請求項１】
並列処理の方法であって、
プログラム構造によって管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第１のスレッドを提供するステップであって、前記第１のスレッドが、ソフトウェアが割り当てる作業を処理している第１の状態と、ディスパッチされず処理する作業を待っている第２の状態の２つの状態を有するものであるステップと、
プログラム構造によって前記第１のスレッドとは別に管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第２のスレッドを提供するステップと、
前記第２のスレッドを使用して前記第１のスレッドが処理する作業を準備するステップと、
キューをロックし、前記第２のスレッドによって準備された作業を、前記第１のスレッドが処理するためにキューに入れ、アンロックするステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、デッドロックを開放して前記第１のスレッドをディスパッチし、前記第１のスレッドを使用してキュー内の作業を処理するステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理している場合、前記第１のスレッドを使用して、前記他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップとを含み、前記他の作業を処理するために前記第１のスレッドを再使用し、前記第１のスレッドを使用して所望量の作業の処理を完了した後、前記第１のスレッドを破棄する、方法。
【請求項２】
前記第２のスレッドが追加の作業をキューに入れ続け、前記第１のスレッドが作業の処理を完了し次第キュー内の追加作業を順次処理する請求項１に記載の方法。
【請求項３】
前記第２のスレッドが前記第１のスレッドのキューに入れられた作業を未完了とマークする請求項１に記載の方法。
【請求項４】
前記第２のスレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理していた場合、前記第１のスレッドがキュー内の作業の処理を完了したとき、前記第１のスレッドを使用して完了作業を完了とマークし、前記第１のスレッド内の作業が完了とマークされるまで、前記第２のスレッドからの後続の作業が待たされる請求項１に記載の方法。
【請求項５】
前記第１のスレッドを使用して所望量の作業の処理を完了した後、前記第１のスレッドを破棄する請求項４に記載の方法。
【請求項６】
並列処理の方法であって、
プログラム構造によって管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第１のスレッドを提供するステップであって、前記第１のスレッドが、ソフトウェアが割り当てる作業を処理している第１の状態と、ディスパッチされず処理する作業を待っている第２の状態の２つの状態を有するものであるステップと、
プログラム構造によって前記第１のスレッドとは別に管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第２のスレッドを提供するステップと、
前記第２のスレッドを使用して、前記第１のスレッドが処理する作業を準備するステップと、
キューをロックし、前記第２のスレッドによって準備された作業を前記第１のスレッドが処理するためにキューに入れ、前記第１のスレッドのキューに入れられた作業が未完了とマークされるステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、デッドロックを開放して前記第２の状態とされている前記第１のスレッドをディスパッチし、それを使用してキュー内の作業を処理するステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理している場合、前記第１のスレッドを使用して、前記他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップと、
前記第２のスレッドを使用してキューに追加作業を入れるステップと、
前記第１のスレッドを使用して作業の処理を完了し次第、前記第１のスレッドを使用してキュー内の追加作業を順次処理するステップとを含み、前記他の作業を処理するために前記第１のスレッドを再使用し、前記第１のスレッドを使用して所望量の作業の処理を完了した後、前記第１のスレッドを破棄する、方法。
【請求項７】
前記第２スレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理している場合、前記第１のスレッドがキュー内の作業の処理を完了したとき、前記第１のスレッドを使用して完了作業を完了としてマークし、前記第２のスレッドからの後続の作業は、前記第１のスレッド内の作業が完了とマークされるまで待たされる請求項６に記載の方法。
【請求項８】
ｉ）プログラム構造によって管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第１のスレッドであって、ソフトウェアが割り当てる作業を処理している第１の状態と、ディスパッチされず処理すべき作業を待っている第２の状態の２つの状態を有するものである第１のスレッドと、ｉｉ）プログラム構造によって前記第１のスレッドとは別に管理される独立した制御の流れを表し、データ・オブジェクトとしてカプセル化された第２のスレッドとを使用して、並列処理のための方法を実行するための、マシン実行可能なプログラムが記録された記録媒体であって、前記プログラムが、
前記第２のスレッドを使用して、前記第１のスレッドが処理する作業を準備するステップと、
キューをロックして前記第２のスレッドによって準備された作業を、前記第１のスレッドが処理するためにキューに入れるステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、デッドロックを開放し前記第２の状態とされている前記第１のスレッドをディスパッチし、前記第１のスレッドを使用してキュー内の作業を処理するステップと、
前記第２のスレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理している場合、前記第１のスレッドを使用して、前記他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップとを前記マシンに実行させ、前記他の作業を処理するために前記第１のスレッドを再使用し、前記第１のスレッドを使用して所望量の作業の処理を完了した後、前記第１のスレッドを破棄する、記録媒体。
【請求項９】
前記第２のスレッドが追加作業をキューに入れ続け、前記第１のスレッドが作業の処理を完了し次第、キュー内の追加作業を順次処理する請求項８に記載の記録媒体。
【請求項１０】
前記第２のスレッドが、前記第１のスレッドのキューに入れられた作業を未完了とマークする請求項８に記載の記録媒体。
【請求項１１】
前記第２のスレッドによって準備された作業がキューに入れられたときに、前記第１のスレッドが該準備された作業以外の他の作業を処理している場合、前記第１のスレッドがキュー内の作業の処理を完了したとき、前記第１のスレッドを使用して完了作業を完了とマークし、前記第１のスレッド内の前の作業が完了としてマークされるまで、前記第２のスレッドからの後続の作業が待たされる請求項８に記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータ処理に関し、詳細には並列のコンピュータ・プログラミングまたは処理に関する。
【０００２】
【従来の技術】
関連出願
本出願は、共に本出願の発明者により本願と同日に出願された「Parallel Software Processing System」という名称の米国特許出願第09/597,523号（整理番号FIS990317US）および「High Performance Nonblocking Parallel Storage Manager For Parallel Software」という名称の米国特許出願第09/597,525号（整理番号FIS990318US）に記載され特許請求される主題に関連する。
【０００３】
分離した非並列処理を使用する従来技術のコンピューティングでは、プログラムはデータおよび他のサービスをしばしば共用する。図１に示すその一例では、別々のプロセス・メモリ１９ａおよび１９ｂは異なるメモリ記憶装置に物理的に分離されているか、または同一のメモリ記憶装置内で論理的に分離されており、プロセス全体から見ることのできるデータ項目用のグローバル変数メモリ２０ａおよび２０ｂと、データ構造用のヒープ・メモリ２１ａおよび２１ｂと、関数引き数およびローカル・データ項目用のスタック・メモリ２３ａおよび２３ｂと、必要に応じてヒープ・メモリ・スペースまたはスタック・メモリ・スペースとして利用できるフリー・メモリ・スペース２２ａおよび２２ｂとを含む。フリー・メモリ・スペースの一部分は、それぞれ別々のプロセス・メモリ１９ａおよび１９ｂ内で動作するプログラムＡ（２４ａ）およびプログラムＢ（２４ｂ）がともに使用できる共通メモリ２２ｃとして指定することができる。各プログラムＡおよびプログラムＢは、プロセス・メモリ内で、共通区域２２ｃ内で指定されたものだけにアクセスすることができ、プログラム間の他のメモリにはアクセスすることができない。図１のシステムを利用するプログラマは、共通メモリ内のデータ構造へのアクセスが制限されている場合、システムからの支援を比較的わずかしか受けられない。
【０００４】
並列処理は、単一のプログラムが、異なるスレッド、すなわちプログラムによって管理される独立した制御の流れを同時に実行できるという点で改良を提供する。複数のスレッドが並列に実行でき、それらのスレッドは疎結合方式あるいは密結合方式で情報を共用することができる。図２に示す並列処理構成の例では、共通グローバル・メモリ１２０および共通ヒープ・スペース１２１を有する単一のプロセス・メモリ１１９が、複数のスタック・スペース１２３ａおよび１２３ｂを含み、単一のプログラム１２４が１つのプログラム・スレッドにつき１つのスタックを用いて複数のスレッドを操作する。図のプロセス・メモリ構造は示すようにスレッド１〜Ｎをいくつでも操作することができ、それに対応するスタック１〜Ｎをいくつでも含むことができる。
【０００５】
スレッド間の調整されたデータ・アクセスでは、通常、セマフォーやロックなどオペレーティング・システムの支援（ペナルティを伴う）が必要である。しかし典型的な並列処理アプリケーションでは、記憶管理やメモリへのアクセスの調整などのシステム・サービスを使用することによって生じる直列化（serialization）により、しばしば、並列アルゴリズムで達成可能な性能上の利益が大幅に減じてしまう。直列化は、複数のスレッドが、データ・オブジェクトまたは他のシステム資源にアクセスするかあるいはそれを要求する際に発生する。このような競合が発生した場合、１つのスレッドのみがアクセス権を有し、他のすべてのスレッドは第１のスレッドがシステム資源の使用を終えるまでアクセスを拒否される。例えば、図２の構造は、異なるスレッドが同時に同一のデータ構造へのアクセスを試みるとき、プログラムによって操作されている情報を含むヒープ・スペースで衝突が生じる可能性があるので、エラーを起こしやすい。衝突が発生すると、１つまたは複数のスレッドはデータ構造が別のプログラム・スレッドによってアクセスされている間待機しなければならない。
【０００６】
現在の慣行では、並列ソフトウェアでのメモリ管理も、複雑さと非効率性が主な欠点となっている領域である。メモリを割り振りあるいは解放するために呼び出しが行われる際に、並列実行の利益が無になり、あるいは順次実行の方が高速になるほどに低下することがある。これは、２つ以上の制御の流れすなわちスレッドが、メモリ領域を獲得しようとあるいは解放しようと試みる際の衝突を防止するために用いなければならない、現在の直列化技術によるものである。これにより並列プログラムの性能が大幅に低下し、プログラム設計および実装における不自然な動作が余儀なくされる。これらの歪みは保守容易性および拡張性を損ない、エラーの原因になる。さらに悪いことにこれらの問題に関するコストのために、開発者は他の点では実現可能な並列の解決策を検討することすら思いとどまりかねない。
【０００７】
上記のような並列プログラミングでは、各スレッドに実行すべき作業の特定の単位が一般には並列に割り当てられ、その仕事が終了するとスレッドは存在しなくなる。スレッドを作成し、終了させ、管理するためにはコストがかかる。このコストにはマシン・サイクルの成分とプログラミングの複雑さの成分がある。プログラミングの複雑さの成分は、ソフトウェアを実装し設計する際のエラーの原因になる。スレッドを使用する際の有力なパラダイムは、スレッドとデータを別に扱うというものである。制御フロー（スレッド）がありデータがある。その結果生じる二分化（dichotomy）は、想定される解決策の種類を制限する傾向のある環境と複雑さを生み、その結果実装中にエラーが生じやすくなる。
【０００８】
【発明が解決しようとする課題】
したがって、従来技術の課題および欠陥を念頭に置くと、本発明の一目的はエラーが生じにくい並列処理構造を提供することである。
【０００９】
本発明の他の目的は、データ構造など共通システム・サービスにアクセスする際に直列化による制限を受けにくい並列処理構造を提供することである。
【００１０】
本発明の他の目的は、メモリを割り振りまたは解放する際に直列化による制限を受けにくい並列処理構造を提供することである。
【００１１】
本発明の他の目的は、異なるスレッド間の相互作用が少ない並列処理構造を提供することである。
【００１２】
本発明の他の目的は、スレッドを作成し管理し終了する際のコストおよびエラーを低減する並列処理構造を提供することである。
【００１３】
本発明のその他の目的および利点は、一部は自明であり一部は本明細書から明らかになるであろう。
【００１４】
【課題を解決するための手段】
当分野の技術者には明らかである上記および他の目的および利点は、本発明によって達成される。本発明は、第１の態様では、プレーンを備える第１の階層レベルを有する、並列コンピューティング用のコンピュータ・メモリ構造を対象とする。プレーンは、プログラム構造によって管理される独立した制御の流れを表すスレッドと、データ構造用のヒープ部分と、関数引き数のためのスタック部分と、ローカル変数と、プログラム構造のいずれの部分からもアクセスできるグローバル・データとを含む。メモリ構造はさらに、スペースを備える第２の階層レベルを有する。このスペースは２つ以上のプレーンを含み、スペース中の各プレーンはプログラム構造を含んでいる。スペースはさらに、各プレーンの間にプログラム構造からアクセス可能な共通データを含む。
【００１５】
メモリ構造はさらに、２つ以上のスペースを備えた第３の階層レベルを有することが好ましい。このスペースは、同一のまたは異なるプログラム構造と、各スペースの間にプログラム構造からアクセスできる共通データを含んでいる。プログラム構造はプログラムのライブラリを備え、さらに各スペース用の関数テーブルを含み、この関数テーブルは各スペース中のライブラリとサービスを交換するように適合されている。
【００１６】
関連する態様では、本発明は、媒体中で実施されるコンピュータ可読コードを有するコンピュータ使用可能媒体を備える、並列コンピューティング用のコンピュータ・プログラム製品を提供する。コンピュータ・コードは、コンピュータ・メモリ構造を定義し、上記の第１の階層レベルおよび第２の階層レベルを含み、好ましくは第３の階層レベルも含む。
【００１７】
本発明の関連する別の態様は、並列処理方法を提供する。この方法では、まず上記の第１の階層レベルおよび第２の階層レベルを有するコンピュータ・メモリ構造が提供される。この方法は次いで、スペース内の第１プレーン中のプログラム構造によって管理される第１スレッドを使用すること、第１プレーン中のデータおよび各プレーン間の共通データにアクセスすること、スペース内の第２プレーン中のプログラム構造によって管理される第２スレッドを使用すること、ならびに第２プレーン中のデータおよび各プレーン間の共通データにアクセスすることを含む。第１スレッドと第２スレッドは、プログラム構造によって明示的に要求されるとき以外は互いの相互作用を回避する。
【００１８】
このプログラム構造はプログラムのライブラリを備え、さらにスペース用の関数テーブルを提供し、この関数テーブルはスペース中のライブラリとサービスを交換するように適合されている。この方法は、第１スレッドおよび第２スレッドを使用して関数テーブルに関数呼び出しを行い、各プレーン間の共通データおよびスペース内の共通データにアクセスすることを含む。２つ以上のスペースを備えた第３の階層レベルがさらに提供され、そのスペースが同一のまたは異なるプログラム構造と、各スペースの間のプログラム構造からアクセス可能な共通データを含むことが好ましい。次いでこの方法は、第１スレッドおよび第２スレッドにより各スペースの間の共通データにアクセスすることを含む。
【００１９】
関連する別の態様は、上記の第１、第２の階層レベルおよび好ましくは第３の階層レベルを有するコンピュータ・メモリ構造を使用して、上記の並列処理の方法ステップを実行するためのマシン実行可能な命令のプログラムを有形に実施する、マシン可読のプログラム記憶装置を提供する。
【００２０】
別の態様では、本発明は並列処理コンピューティング・システムにおいてメモリを割り振る方法を提供する。この方法では、まず並列処理および第１スレッド、第２スレッドに使用可能なシステム・メモリが提供される。各スレッドは、プログラム構造によって管理される独立した制御の流れを表し、異なるプログラム・タスクを実行する。この方法は、第１スレッドを使用してシステム・メモリからメモリを要求すること、第１スレッドに要求を超える第１のメモリ・プールを割り振り、そのメモリ・プールを第２スレッドと関連付けること、第２スレッドを使用してシステム・メモリからメモリを要求すること、第２スレッドに要求を超える第２のメモリ・プールを割り振り、そのメモリ・プールを第１スレッドと関連付けること、第１スレッドを使用して第２スレッドからさらにメモリを要求すること、ならびにシステム・メモリに要求を行わずに、第２スレッドからの第２メモリ・プールの一部分を第１スレッドに割り振ることを含む。
【００２１】
第１メモリ・プールおよび第２メモリ・プールがそれぞれ、システム・メモリが第１スレッドおよび第２スレッドのためにマークしたメモリ部分を含むことが好ましい。この方法は次いで、第１スレッドのためにマークされた第１メモリ・プールの部分を第２スレッドによって解放し、第２スレッドのためにマークされた第２メモリ・プールの部分を第１スレッドに割り振ることを含む。第１スレッドのためにマークされた第２メモリ・プールの部分は、そのようなメモリの所定最小限量が第２スレッドによって解放されるまでは第１スレッドに割り振ることができず、第１スレッドのためにマークされた第２メモリ・プールの部分は、第１スレッドが第２スレッドからさらにメモリを要求するまで第１スレッドに割り振ることができない。第１メモリ・プールおよび第２メモリ・プールがそれぞれ、システム・メモリによって第１スレッドおよび第２スレッドのためにマークされたメモリ部分を含むことが好ましい。この方法は次いで、第１スレッドのために所定時間マークされる第２メモリ・プールの部分を第２スレッドによって解放し、所定時間の経過後に第１スレッドがメモリを要求しない場合は、第１スレッドのためにマークされた第２メモリ・プールの部分を第２スレッドのために再利用する（reclaim）ことを含む。
【００２２】
関連する態様では、本発明は、並列処理コンピューティング・システムにおいてメモリを割り振る上記の方法ステップを実行するためのマシン実行可能な命令プログラムを有形に実施する、マシン可読のプログラム記憶装置を提供する。
【００２３】
関連する別の態様は、並列処理コンピューティング・システムで使用するためのメモリ構造を提供する。このメモリ構造は、並列処理で使用可能なシステム・メモリと、プログラム構造によって管理される制御の流れを表す第１スレッドの使用のために指定され第１スレッドが使用できる第１のメモリ・プールと、第２スレッドの使用のために指定され第２スレッドが使用できる第２のメモリ・プールとを備える。第２スレッドは、第１スレッドとは無関係にプログラム構造によって管理される制御の流れを表し、第１メモリ・プールおよび第２メモリ・プールはそれぞれ、もう一方のスレッドのためにマークされたメモリ・プールの部分を有する。第１メモリ・プールおよび第２メモリ・プールがそれぞれ、システム・メモリによって第１スレッドおよび第２スレッドのためにマークされたメモリ部分を含むことが好ましい。
【００２４】
関連する別の態様は、媒体中で実施されるコンピュータ可読コードを有するコンピュータ使用可能媒体を備える、並列コンピューティング用のコンピュータ・プログラム製品を提供し、そのコンピュータ・コードは上記のコンピュータ・メモリ構造を定義する。
【００２５】
本発明の別の態様は、並列処理の方法を提供する。この方法では、まずプログラム構造によって管理される独立した制御の流れを表す第１スレッドが提供され、この第１スレッドは、プログラム構造のために作業を処理する第１の状態と、ディスパッチされず処理すべき作業を待っている第２の状態の２つの状態を有する。また第１スレッドとは別にプログラム構造によって管理される独立した制御の流れを表す第２スレッドが提供される。この方法は、第２スレッドを使用して、第１スレッドが処理すべき作業を準備すること、および第２スレッドが準備した作業を、第１スレッドによる処理のためにキューに入れることを含む。この方法は、第２スレッドが準備した作業がキューに入れられたとき、第１スレッドが処理すべき作業を待っている場合に、第１スレッドをディスパッチし、それを使用してキュー内の作業を処理することを含む。この方法は、第２スレッドが準備した作業がキューに入れられたときに第１スレッドが他の作業を処理中である場合に、第１スレッドを使用して他の作業の処理を完了し、キュー内の作業にアクセスし、キュー内のその作業を処理することを含む。
【００２６】
第２スレッドは追加の作業をキューに入れ続けることができ、第１スレッドは前の作業の処理を完了し次第、キュー内の追加の作業を順次処理する。第２スレッドが、第１スレッドのキューに入れられた作業を未完了とマークすることが好ましい。この方法は、第２スレッドが準備した作業がキューに入れられたとき、第１スレッドが他の作業を処理中である場合に、第１スレッドがキュー内の作業の処理を完了したとき、第１スレッドを使用して完了した作業を完了とマークすることを含む。第２スレッドからの後続の作業は、第１スレッドにおける前の作業が完了とマークされるまで待たされる。第１スレッドを再使用して他の作業を処理してもよく、プログラム構造は、第１スレッドが所望量の作業を完了した後にそれを破棄することができる。
【００２７】
関連する態様は、ｉ）プログラム構造によって管理される独立した制御の流れを表す第１のスレッドであって、プログラム構造のために作業を処理する第１の状態と、ディスパッチされず処理すべき作業を待っている第２の状態との２つの状態を有する第１スレッドと、ｉｉ）第１スレッドとは別にプログラム構造によって管理される独立した制御の流れを表す第２スレッドとを使用して、並列処理の上記の方法ステップを実行するためのマシン実行可能な命令プログラムを有形に実施する、マシン可読のプログラム記憶装置を提供する。
【００２８】
【発明の実施の形態】
並列ソフトウェア処理システム
並列処理中にシステム・サービスにアクセスする際の直列化による制限の問題を克服するために、本発明は、プログラマの権限からこれらの問題を暗示的に取り除き並列アプリケーションの大幅な改善をもたらすプログラミング手法を、高級言語の構文で定式化する。本発明は、プログラマをより高性能の解決策に自然に導くのに必要な構造を提供する。詳細には本発明は、様々な態様において、各並列スレッドのデータ・スペースを自然に分離する座標系システムと、スレッドとデータ・スペースを関連付ける方法と、この分離を記述し管理するための高級言語を提供する。以下でさらに述べる構造を組み込んだ本発明のシステムは、その他の点では従来型の、コンピュータ・プログラム記憶装置または半導体チップ、ＲＯＭなどのメモリ記憶装置、あるいはディスケットやコンピュータ・ハード・ドライブなどの磁気媒体に記憶することができる。
【００２９】
本発明によって作り出される構造では、各スレッドが、それ自体のデータ・スペースすなわち単一のスレッドと関連付けられたメモリ区域を有し、このスペースは、共通であると明示的に宣言された部分を除き他のすべてのデータ・スペースから分離されている。本発明を使用すると、データ・スペースの最小限の明確な相互作用で並列アルゴリズムを設計し実装することが自然に可能になり、それによって、プログラマが並列性の管理に関する専門家でなくとも低コストで高性能の並列性が提供される。
【００３０】
本発明の並列構造は、各スレッドごとに１つずつ異なるスタックを提供し、スタックごとに異なる別々のグローバル・メモリ、ヒープ・スペースおよびフリー・ゾーンを有するという外観および機能を提供する。図３に、本明細書中で「プレーン」と呼ぶ、本発明の並列メモリ構造の第１の階層レベルと、２つ以上のプレーンの「スペース」へのグループ化を示す。メモリは別々のプレーン２２５ａおよび２２５ｂに再分割される。プレーン２２５ａおよび２２５ｂは異なるプレーン・メモリ領域２１９ａおよび２１９ｂを有する。プログラム構造２２４からの１つのスレッドは各プレーンのスタック上で稼動し、複数のスレッド１〜Ｎは複数のスタック１〜Ｎ上でそれぞれ稼動することができる。スレッドは並列コンピューティング・システムで同時に実行されるが、任意の所与の瞬間にプレーン・メモリにアクセスするスレッドはせいぜい１つである。プレーン・メモリ２１９ａおよび２１９ｂは、それぞれグローバル・メモリ２２０ａおよび２２０ｂと、ヒープ・スペース２２１ａおよび２２１ｂと、フリー・スペース２２２ａおよび２２２ｂを含み、これらはそれぞれプレーン２２５ａ、２２５ｂごとに編成され提供される。このとき各プレーンは、スレッド、グローバル・メモリ、ヒープ・メモリ、およびスタック・メモリによって定義されるコンテキストからなる。任意の特定時間にあるコンテキストを使用するのは１つのスレッドだけである。明示的に定義された共通（プレーン）領域２２２ｃもあり、これは他の点では分離しているプレーン・メモリ２１９ａおよび２１９ｂによって共用される。したがってプログラマから見ると、プレーン・メモリ構造は、図１に示すように別々のプログラムを実行しているという外観および機能を有するが、実際には、共通（プレーン）メモリ２２２ｃ内のデータ構造がすべて使用可能であり、ヒープ２２１ａおよび２２１ｂ内の選択されたデータ構造が異なるプレーンにわたってスタック２２３ａおよび２２３ｂ内の各スレッドにとって使用可能なので、このプレーン・メモリ構造は並列スレッドとして動作する。
【００３１】
すべてが単一のプログラム構造の異なるスレッドを並列に実行している、メモリ構造中の複数のプレーンのグループを本明細書中では「スペース」と呼ぶ。プログラムの集まりが、こうしたスペース内で一貫した単一のプログラム構造を作る。スペース２３０は、本発明の並列処理システムの第２の階層レベルを表す。図４には複数のスペース２３０、２３０'、２３０"が示されており、各スペースは１つまたは複数のプレーン・メモリ構造を含んでいる。各スペースは互いに他のプログラムとは無関係に稼動する、異なるプログラム２２４、２２４'、２２４"を含む。フリー・メモリは、共通（プレーン）メモリの場合と類似の形で、異なるスペース間の共通（スペース）として指定することができる。異なるスペース２３０、２３０'、２３０"間で指定された共通（スペース）メモリを２２２ｄで表す。これらの複数のスペースは、本発明の第３の階層レベルを表す。
【００３２】
明示的には共通にされないグローバル・メモリ・オブジェクトまたはヒープ・メモリ・オブジェクトは、特定の言語エレメントによって表される。このようなオブジェクトは、すべてのプレーンで同一の言語エレメントによって表されるが、各プレーン内では分離したメモリによってバックアップ（back）される。したがって言語エレメントはスレッドごとに自動的にインスタンス化される。これによりプログラマは、そのようなメモリ・オブジェクトを管理し分離するという厄介な仕事から解放される。本発明のメモリ構成はまた、プレーンとスペースの間で情報を共用するための規律ある手段も提供し、プログラマは規律を提供するという重荷から解放される。
【００３３】
図５に示すように、指定スペース中の各プレーンは、コンテキスト（スレッド、ヒープ、スタック、グローバル・データ）および同一のプログラム構造からなり、このプログラム構造は同一の実行可能プログラム・コードを使用する。この同一のプログラム構造が、スペース内の各プレーンに使用される。異なるスペース間では、プログラム構造は同じでも異なってもよい。本明細書では、「コンテキスト」は、各グローバル変数に各スレッドが容易にアクセスできるようにグローバル変数の分離を行う、索引付け構造を指す。本発明のメモリ構造を使用するプログラマは、所望の特定のコンテキストを作成し、そのコンテキストを使用して、共通（プレーン）メモリまたは共通（スペース）メモリの外部にあるその特定のコンテキスト内で動作するプログラムを呼び出す。
【００３４】
具体的には、コンテキスト索引付け構造は、各グローバル変数の整数識別を、メモリ・アドレスなど一意の識別にリンクする。例えば図６に示すように、プレーン1内にはグローバル変数Ｇ1、Ｇ2、Ｇ3があり、プレーン2内には別のグローバル変数Ｇ1、Ｇ2がある。Ｇ4（プレーン1、コンテキスト1）、Ｇ3'（プレーン2、コンテキスト2）、およびＧ5（プレーン1、コンテキスト1）、Ｇ4'（プレーン2、コンテキスト2）で示したグローバル・データ変数は、スペース内部の共通（プレーン）内にあるように指定される。第１プレーンのコンテキスト1および第２プレーンのコンテキスト2はそれぞれ、索引付け方式を使用して、グローバル変数のそれ自体の整数ＩＤをグローバル変数の一意のＩＤに変換することができる。図に示すように共通（プレーン）内のＧ4とＧ3'、Ｇ5とＧ4'は同じオブジェクトである。
【００３５】
図７は、各スペースが共通（スペース）メモリによってリンクされ、それぞれ複数のプレーンおよび共通プログラムを有する、複数のスペースを示す。スペース1はプレーン1およびプレーン2を有し、各プレーンがプログラム1を使用する。スペース2はそれとは異なるプレーン1およびプレーン2を有し、各プレーンが異なるプログラム2を使用する。共通（スペース）メモリは、スペース1およびスペース2それぞれに使用可能である。図８は、図６に類似の形で、各スペースのコンテキストが、異なる索引ＩＤを使用して、共通（スペース）グローバル・データ・オブジェクトＧ6にどのようにアクセスするかを示している。例えば言語エレメントは、コンテキストが共通（プレーン）または共通（スペース）中のグローバル変数にアクセスできるように、定義または構文を提供することができる。共通（スペース）メモリは、本発明のメモリ構造の異なるスペース中の異なるプログラムが共用できる情報を含むことができる。したがってデータは、特定のプレーンだけからアクセス可能なデフォルト・グローバル・データ・メモリ、スペース内の異なるプレーンにわたってコンテキストからアクセス可能な共通（プレーン）メモリ、あるいは異なるスペースにわたってコンテキストからアクセス可能な共通（スペース）メモリに記憶することができる。図に示すように共通（スペース）内のＧ6、Ｇ5'、Ｇ8"、Ｇ7'''は同じオブジェクトである。
【００３６】
ＩＥＥＥ標準１４８１−１９９９に従って作成された交換可能な関数テーブルを、本発明のメモリ構造中でスペースごとに１つずつ作成することが好ましい。関数テーブルを下記の表１および表２に示すが、この関数テーブル中で、特定スペース内で使用される選択された関数名（ＦＣＮ名）に対する関数ポインタ（ＦＣＮポインタ）が確立される。
【表１】
0004398116.tif 000002
【表２】
0004398116.tif 000003
【００３７】
アプリケーション・プログラムは各スペースにプログラムをロードすることができる。アプリケーション・プログラムおよびロードされたプログラムはそれぞれ関数テーブル交換を実行する。関数テーブル交換は、アプリケーションと特定スペースにロードされたプログラムの間でのサービスの交換を表す。すべての関数呼び出しは、要求されたデータを共通（プレーン）メモリまたは共通（スペース）メモリ内で見つけるためのコンテキスト引き数を有する。コンテキストは索引付け構造がどこに位置するのかを伝える。アプリケーション・プログラムまたはロードされたプログラムによる関数呼び出しは、デフォルト位置と見なされるプレーン内のデータ、または共通（プレーン）もしくは共通（スペース）メモリ位置にあるデータを見つけ出すためのコンテキスト識別を含む。
【００３８】
ＤＣＬ（遅延カルキュレータ言語）は、多くのＡＳＩＣ（特定用途向け集積回路）ベンダーがその技術を記述するために使用している言語である。このＤＣＬのライブラリは、アプリケーションによって動的にロードされる実行可能モジュールである。アプリケーション・ベンダーもＡＳＩＣベンダーも明確なある標準に従っている。ＤＣＬおよびこのインタフェース定義はどちらも、本発明による並列処理システムを確立するのに使用することができる。ＤＣＬシステム（実行時環境、コンパイラ、およびコンパイルされたそのモジュールからなる）は、せいぜい１つのスレッドしか各コンテキストで実行されないコンテキスト・システムを実装する。コンテキストはアプリケーションまたはライブラリの要求に応じて作成される。新しいコンテキストに対する要求に応答して、ＤＣＬ実行時環境は各状態変数の別個のコピーを生成する。状態変数としては、ＡＳＳＩＧＮステートメント、テーブル、モジュール構造によって生成される変数が含まれる。各状態は状態変数の配列によって表され、その中で各コンテキストがそれ自体の状態変数を有する。システムは新しい各コンテキストごとに、状態変数が既知の値にプリセットされるように、そのコンテキストに対する初期化ステートメントを実行する。
【００３９】
ＤＣＬの基本動作は、現在のコンテキスト変数（標準構造）がすべてのステートメントに渡されることを必要とする。コンテキスト変数は、制御フロー、データ・スペース、実行が行われるプレーンの完全な記述を提供する。実行時サポート機能は、アプリケーション要求およびＤＣＬプログラムの並列実行をサポートするのに必要とされる適切なメモリ・オブジェクトをトランスペアレントに選択する。ＤＣＬを使用すると、ＡＳＳＩＧＮステートメントを使ってグローバル変数を生成することができる。これによりコンパイル時にグローバル変数をステートメントのタイプ（ＡＳＳＩＧＮ）によって識別することができ、グローバル変数に対する更新を単一の関数を通じて集中させることができる。
【００４０】
本発明では、各配列エレメントがあるコンテキストと関連付けられるＡＳＳＩＧＮ変数の結果の配列など、ＡＳＳＩＧＮの結果をコンテキストによって分離する。これにより直列化を起こさずにＡＳＳＩＧＮ変数値を並列に読み取り、書き込むことが可能になる。ＤＣＬのＴＡＢＬＥＤＥＦステートメントは情報のテーブルを読み込み、検索する。本発明はこのテーブルを上記のコンテキスト・システムによって分離し、これにより直列化することなくこのテーブルを真の並列方式で読み込み、検索し更新することが可能になる。
【００４１】
ＤＣＬにより、アプリケーションがサブルールと呼ばれる追加モジュールを既存のシステムに付加することが可能になるが、本発明ではまたあるスペースに付加されたサブルールを別のスペースに付加されたサブルールから分離する。これにより、ロードされる多様なライブラリの独立したビューをアプリケーションが維持することが可能になる。本発明はまた、ライブラリ開発者の要求に応じて同じ状態変数が複数のコンテキストに存在できるようにする構成と、その時点で直列化を強制するための構成も提供する。コンテキストは通常、ライブラリ開発者から明示的に要求される場合以外は、状態変数の独立性を想定している。これにより並列アルゴリズムの開発が非常に容易になり、共通性の必要なポイントだけを調べればよくなる。
【００４２】
動作に際して、本発明はあるコンテキストに対するスレッドに関連するすべてのアクティビティを自然に分離することにより利益を達成する。異なるスレッドは異なるコンテキストで動作し、したがって明示的に要求されるとき以外は互いに相互作用しない。これによって並列処理に特有の直列化による制限が取り除かれ、したがって本発明は思考プロセスならびに実際の実装を単純化する。
【００４３】
高性能非ブロッキング並列記憶マネジャ
本発明はさらに、スレッド・コンテキストを用いて、並列環境で使用するためのブロッキングのない効率的な記憶管理を提供する。記憶マネジャは使用可能メモリの別々のプールをコンテキストごとに維持し、当該のコンテキストにはそれらのプールのみからのメモリを割り振る。多数のスレッド（上記のようにコンテキストごとに１つのスレッド）がメモリを獲得または解放するために記憶マネジャに同時にアクセスすることができるが、そのほとんどの時間実行はブロックされない。従来技術の慣行では、複数のスレッドが同時にメモリ・エリアの割り振りまたは解放を要求するたびに実行がブロックされるのに対して、本発明では複数のコンテキストが同時にそのメモリ・プールを使い果たし、メモリを割り振るシステム・サービスの呼び出しを行わなければならないときにのみ実行がブロックされる。本発明が、システムからいくつかの大きなメモリ・エリアを獲得し、スレッドの必要に応じてそのメモリ・エリアを分割することが好ましい。スレッドのブロッキングは、そのスレッドのためにいくつかの大きなエリアを得ようと試みている間に別のスレッドもそれ自体の大きなエリアをシステムから得ようとする場合にしか起こらないので、本発明の性能は概して従来方法の性能をはるかに上回る。システムに別の大きな部分を割り振らせるための１つのスレッドの呼び出しによってブロックされる場合も、このシステムではその関連するメモリ・プールの中にメモリ・エリアがある限り、他のスレッドからのメモリ要求を依然処理することができる。通常の状況において並列アプリケーションは実行の部分的ブロッキングしか受けず、それもめったに起こらない可能性が高い。
【００４４】
メモリ・エリアの解放に関する問題には２つの側面がある。コンテキストがそれが割り振ったメモリ・エリアだけを解放する場合、解放動作は、そのエリアを必要とするスレッドあるいは他のどのスレッドもブロックせずに進行する。あるコンテキストによって割り振られたメモリ・エリアを別のコンテキストが解放する際に生じる直列化を最小限に抑えるために、「据え置き解放（deferred free）」のリストが作成される。コンテキストがそれが割り振っていないメモリ・エリアを解放するとき、本発明ではそのエリアを「据え置きリスト」に入れる。各コンテキストは据え置きリストのセットを有し、据え置きリストの各セットは他のあらゆるコンテキストに対する据え置きリストを有する。次いでメモリ・エリアは、そのエリアを解放しているコンテキストとそのエリアが一時的に解放される先の他のコンテキストとを識別する据え置きリストに入れられ、実行はブロッキングを起こさずに続行する。これらのリストは、アプリケーション・プログラムが設定できる基準（metric）を超えるまで増大する。基準を超えると他の各コンテキストに対する据え置きリストは、現在それを持つ他の受け取りコンテキストに非ブロッキング方式で転送される。各メモリ・エリアの中にはマークがあり、そのマークはどのコンテキストがそのエリアの割り振りをしたのかを示す。転送が完了すると、転送側のコンテキストはブロッキングを起こさずに受け取り側のコンテキストの既知のスポットにフラグをセットする。
【００４５】
コンテキストが、システムにスペースを要求する前にメモリ・エリアを割り振らなければならないとき、そのコンテキストは他のコンテキストからいずれかの据え置き解放を受け取ったかどうかチェックする。受け取っている場合、コンテキストはそのメモリ・エリアを再利用し、システム・サービスを呼び出す代わりにメモリ・エリアからの要求を満たそうと試みる。これによりブロッキングがさらに取り除かれる。
【００４６】
コンテキストを受け取ることによる据え置きブロックの再利用は非ブロッキング方式で行われ、ブロッキングを回避するために非同期にすることができる。制御データ構造のレイアウトおよび動作の順序は、処理中に追加されたいくつかの再利用が欠落する可能性があるものの、非同期環境で再利用が成功することを可能にする。欠落したこれらの再利用は失われずに次の再利用期間に回復される。
【００４７】
図９に示すように、並列処理で動作する第１スレッドのコンテキスト1は、システム・ヒープ・メモリ３００からの最初の要求によりフリー・メモリ３１０の一部分またはプールを獲得し、その特定のコンテキストのヒープとして機能するメモリ・ブロック３１０ａ、３１０ｂ、３１０ｃ、３１０ｄを備える。複数のコンテキスト１〜Ｎのうち任意数のコンテキストはそれ自体の分離したメモリ・プールを獲得することができ、スレッドＮのコンテキストNはメモリ・ブロック３２０ａ、３２０ｂ、３２０ｃ、３２０ｄとともにそれ自体のメモリ・プール３２０を獲得する。プール３１０、３２０内の各ブロックは、メモリを割り振る前に所定のコンテキスト識別子で事前にマークされる。各メモリ・プール３１０、３２０は、システム・ヒープ３００に対して最初に行われる要求で必要とされるよりも多くのメモリ・ブロックを有する。図１０は未使用メモリ・ブロックの再利用をより詳細に示している。
【００４８】
第１の状況では、不必要なメモリ・ブロックを特定のコンテキストが解放し、そのメモリ・ブロックがその同一コンテキストに割り振られたと事前識別されている場合、メモリ・ブロックはその特定のコンテキストが使用できる状態にあるものと単純に識別される。第２の状況では、不必要なメモリ・ブロックを特定のコンテキストが解放し、そのメモリ・ブロックが別の異なるコンテキストから割り振られたと事前識別されている場合、そのメモリ・ブロックは、他の異なるコンテキストに対応する、再利用リスト中の特定コンテキストの同一のメモリ・プールに集められる。図１０は、コンテキスト1のメモリ・プール３１０が不必要なメモリ・ブロック３１０ｅ〜ｈを解放する状況を示している。これらのメモリ・ブロック３１０ｅ〜ｈは以前にコンテキスト2の識別によってマークされたので、ブロック３１０ｅ〜ｈは、コンテキスト2に対応するコンテキスト1再利用リスト３１２ａに残る。再利用リスト３１２ａのブロックのサイズまたは内容がアプリケーション指定の基準を超えると、コンテキスト1はスイッチ３１４を３１４ｂから３１４ａにセットし、コンテキストが再利用リスト３１２ａ中のメモリを再利用できることを示す。コンテキスト1はスイッチ３１３を３１３ｂにセットする。したがってコンテキスト2に属するものとしてマークされた後続のフリー・メモリ・ブロックは、コンテキスト2がリスト３１２ａ中のメモリを再利用するまで再利用リスト３１２ｂに入れられる。コンテキスト2はヒープ・メモリ３２０を使い果たすと、システム・メモリから入手可能なメモリを探す代わりに、再利用リストが使用可能になっているかを調べ、使用可能なメモリ・ブロック３１０ｅ〜ｈを突き止め、次いでそれらを解放しそれ自体のヒープ・メモリ・プール３２０に組み込む。コンテキスト2は次いでスイッチ３１４を３１４ｂにセットし、コンテキスト2が再利用リストを処理し終わり、現在は別の再利用リストを処理できる状態であることを示す。同様にコンテキスト1がそれ自体のメモリ・プールで使用可能なメモリよりも多くのメモリを要求する際は、コンテキスト2など他のコンテキストによって生成された再利用リストからメモリを探し、使用可能メモリ３２０ｅ〜ｈを突き止め、それらを解放しメモリ・プール３１０に組み込むが、このすべての動作の際にメイン・システム・メモリからメモリを探す必要がない。再利用リスト３１２ｂがアプリケーション指定の基準を超えると同様の動作が行われ、コンテキスト1はスイッチ３１４を３１４ｂから３１４ｃにセットしてコンテキスト2がリスト３１２ｂのメモリを再利用できることを示し、コンテキスト1はスイッチ３１３を３１３ａにセットして、コンテキスト2が３１２ｂのメモリを再利用するまで、コンテキスト2に属するものとしてマークされた後続のフリー・メモリ・ブロックがリスト３１２ａ中に置かれるようにする。コンテキスト2が再利用リスト３１２ｂ中のメモリを再利用するとき、コンテキスト2はスイッチ３１４を３１４ｂにセットして、それがリストの処理をし終わり現在は別の再利用リストを処理できることを示す。本発明は、コンテキストの組ごとに任意数の再利用リストを可能にする。
【００４９】
別のコンテキストにマークされた、１つのコンテキストからの使用可能なメモリ・ブロックは、もう一方のコンテキストが追加のメモリ・ブロックを探すまで、実際にはもう一方のコンテキストによって解放されず再利用されないことが好ましい。もう一方のコンテキストが所定の期間後にメモリ・ブロックを再利用しない場合、その１つのコンテキストはそのメモリ・ブロックを使用するために再利用することができ、同時にもう一方のコンテキストの識別をそのブロック上になお保持している。これらはすべて、どちらかのコンテキストがメイン・システム・メモリからメモリを探す前に行うことができる。
【００５０】
本発明のこの態様の試験では、並列処理のメモリ・アクセスが従来技術による方法に比べて最大で２０．７倍まで高速になることが示された。
【００５１】
再利用可能な抽象データ・オブジェクトとしてコンピューティング制御の別個のフローを使用する
コンテキストとデータを別に扱う従来技術と異なり、本発明は並列環境でコンテキストを使用するための新しいパラダイムを実装する。基本的にこの発明ではコンテキストを作成してそれをキャプチャし、それをプログラマの視点からは抽象的であるデータ・オブジェクトにバインドする。このため、スレッド（すなわち制御の流れ）をソフトウェアによりデータ・オブジェクトとして扱うことが可能になる。これにはいくつかの利点がある。１つの利点はスレッドが一度作成され、必要に応じて再使用されることである。これにより、一般的な手法で見られるスレッドの作成および破棄のコストが回避される。別の利点は、スレッドがデータ・オブジェクトであり、したがって制御とデータの間における一般的な二分化を除去し、プログラマに問題に対する解決策を構想するための精神的余裕をより多く与えることである。別の利点は、スレッドがデータ・オブジェクトであるので、従来は不可能だった操作をソフトウェア開発者が利用できることである。この操作には、スレッドを他のデータ・オブジェクトに追加すること（後の実行時に使用するため）、スレッド（制御フロー）をパラメータとして渡すことなどが含まれるがそれだけに制限されるものではない。
【００５２】
本発明のこの態様は、その上で待機するスレッドを有する抽象データ・オブジェクトを実装する。従来のデータ・オブジェクトに可能であるように、このデータ・オブジェクトは順に渡され、プログラムのデータ構造に組み込むことができる。要求があると、ソフトウェアは特定の作業をデータ・オブジェクトに割り当て、待機しているスレッドがウェイク・アップしてその作業を行う。作業を実行した後、スレッドはさらなる作業を求めて再び待機する。作業は所望の任意時に、アプリケーションのいずれのセクションからも割り当てることができる。スレッドはアプリケーション・プログラムが破棄を決定するまでは破棄されない。
【００５３】
この手法は、スレッドの使用により並列動作を行うことを必要とするソフトウェアの作成を大幅に単純化する。スレッドを抽象化することにより、プログラマの権限から煩瑣な詳細事項が取り除かれる。待機スレッドをデータ・オブジェクトとしてカプセル化することにより、制御フローとデータ間の二分化がブリッジされるので、プログラマはより多くの自由度と広範囲の解決策を得られる。
【００５４】
図１１は、作業が割り当てられる抽象データ・オブジェクトとして実装されるスレッドの概略流れ図である。第１のスレッドはデータ・オブジェクト（「ボトル」）として指定され、通常これはディスパッチされず、プログラム構造がそれに指定された作業を行うために使用可能ではない。この作業とは、使用される関数、パラメータの収集、結果をどこに置くかという命令など、通常並列処理でスレッドによって実行されるどんな作業単位でもよい。「ボトル」は単一のコンテキストと関連付けられ、他のコンテキストによってのみ起動されそれ自体の作業を実行することができる。本発明では、各ボトルはそれ自体のコンテキストによって起動できないことが好ましい。ボトルには、プログラム構造のために作業を処理する第１の状態と、ディスパッチされず、実行時間を消費しない延期状態で処理する作業を待機している第２の状態の２つの状態しかない。ボトルは、要求された作業が１つまたは複数の他のコンテキストによって入れられる、関連付けられたキュー（Ｑ）を有する。動作において、ボトルは作業要求があるかキューを調べ、キュー内に待機中の作業がある場合ボトルはキューをロックし、作業単位を取り出し、キューをアンロックして要求作業を実行する。要求作業をその作業単位で終了すると、ボトルはその結果を完了とマークし、作業キューを再度チェックする。ボトルは待機作業を順次処理し、作業がキュー内で実行を待っている限り基本的に永久ループで動作する。キューが空の場合、ボトルはデッドロックでディスパッチされない状態に入り、他のいずれのコンテキストが作業をキューに入れ、次いでそのボトルがディスパッチされて作業キューを再度チェックさせられるのを待機する。
【００５５】
第１スレッドすなわち「ボトル」スレッドとは別にプログラム構造によって管理される独立した制御の流れを表す第２のスレッドを、図１１に「ランチャ」として示す。ランチャは、「ボトル」が処理する作業を準備するために使用される。ランチャは、作業キューをロックし、作業単位を作業キューに入れ、キューをアンロックすることにより、第１の「ボトル」が処理するために作業をキューに入れる。「ボトル」が中断されている場合、ランチャはその「ボトル」をディスパッチさせる。ランチャはボトル・キューに追加作業を引き続き追加することができる。作業をボトル・キューに入れるとき、ランチャはその作業を未完了としてマークする。他のコンテキスト（ボトル・コンテキスト以外の）はいずれも、互いのコンテキストが結果の構造へのアクセス権を有すると想定して、特定の結果が完了しているかをチェックすることができる。
【００５６】
したがって、第１スレッドは単一のタスクを完了した後、破棄されずにプログラム構造の要求に応じて再使用される。プログラム構造は、第１スレッドが所望量の作業を完了した後にのみそれを破棄する。
【００５７】
本明細書に記載する並列ソフトウェア・システムは、マシン、好ましくは従来型のコンピュータにおいて、従来のコンピュータ可読コードを使用したコンピュータ使用可能な媒体上、半導体チップや読取り専用メモリなど他の点では従来型のプログラム記憶装置、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの光学読取媒体、あるいはディスケットやコンピュータ・ハード・ドライブなどの磁気媒体上で作成し記憶することができる。
【００５８】
したがって本発明は、従来技術で使用される構造に比べてエラーの生じにくい並列処理構造を提供する。本発明の並列処理構造は、データ構造など共通システム・サービスにアクセスする際に直列化による制限を受けにくい。またメモリの割り振りおよび解放の際にも直列化による制限を受けにくい。さらに異なるスレッド間の相互作用が少ない。本発明は、スレッドを作成し、管理し、終了する際のコストおよびエラーを低減する並列処理構造を提供する。さらに各スレッドは、ソフトウェアによりデータ・オブジェクトとして扱うことが可能である。
【００５９】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６０】
（１）並列処理の方法であって、
プログラム構造によって管理される独立した制御の流れを表す第１のスレッドを提供するステップであって、前記第１スレッドが、プログラム構造のための作業を処理している第１の状態と、ディスパッチされず処理する作業を待っている第２の状態の２つの状態を有するステップと、
プログラム構造によって前記第１スレッドとは別に管理される独立した制御の流れを表す第２のスレッドを提供するステップと、
第２スレッドを使用して第１スレッドが処理する作業を準備するステップと、第２スレッドによって準備された作業を、第１スレッドが処理するためにキューに入れるステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが処理すべき作業を待っている場合、第１スレッドをディスパッチし、第１スレッドを使用してキュー内の作業を処理するステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが他の作業を処理している場合、第１スレッドを使用して、他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップとを含む方法。
（２）第２スレッドが追加の作業をキューに入れ続け、第１スレッドが前の作業の処理を完了し次第キュー内の追加作業を順次処理する上記（１）に記載の方法。
（３）第２スレッドが第１スレッドのキューに入れられた作業を未完了とマークする上記（１）に記載の方法。
（４）第２スレッドによって準備された作業がキューに入れられたときに第１スレッドが他の作業を処理していた場合、第１スレッドがキュー内の作業の処理を完了したとき、第１スレッドを使用して完了作業を完了とマークし、第１スレッド内の前の作業が完了とマークされるまで、第２スレッドからの後続の作業が待たされる上記（１）に記載の方法。
（５）他の作業を処理するために第１スレッドが再使用される上記（１）に記載の方法。
（６）第１スレッドが所望量の作業を完了した後、プログラム構造がそれを破棄する上記（４）に記載の方法。
（７）並列処理の方法であって、
プログラム構造によって管理される独立した制御の流れを表す第１のスレッドを提供するステップであって、前記第１スレッドが、プログラム構造のための作業を処理している第１の状態と、ディスパッチされず処理する作業を待っている第２の状態の２つの状態を有するステップと、
プログラム構造によって第１スレッドとは別に管理される独立した制御の流れを表す第２のスレッドを提供するステップと、
第２スレッドを使用して、第１スレッドが処理する作業を準備するステップと、
第２スレッドによって準備された作業を第１スレッドが処理するためにキューに入れ、第１スレッドのキューに入れられた作業が未完了とマークされるステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが処理すべき作業を待っている場合、第１スレッドをディスパッチし、それを使用してキュー内の作業を処理するステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが他の作業を処理している場合、第１スレッドを使用して、他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップと、
第２スレッドを使用してキューに追加作業を入れるステップと、
第１スレッドが前の作業の処理を完了し次第、それを使用してキュー内の追加作業を順次処理するステップとを含む方法。
（８）第２スレッドによって準備された作業がキューに入れられたときに第１スレッドが他の作業を処理している場合、第１スレッドがキュー内の作業の処理を完了したとき、第１スレッドを使用して完了作業を完了としてマークし、第２スレッドからの後続の作業は、第１スレッド内の前の作業が完了とマークされるまで待たされる上記（７）に記載の方法。
（９）他の作業を処理するために第１スレッドが再使用される上記（７）に記載の方法。
（１０）第１スレッドが所望量の作業を完了した後、プログラム構造がそれを破棄する上記（８）に記載の方法。
（１１）マシン可読のプログラム記憶装置であって、ｉ）プログラム構造によって管理される独立した制御の流れを表す第１スレッドであって、プログラム構造のための作業を処理している第１の状態と、ディスパッチされず処理すべき作業を待っている第２の状態の２つの状態を有する第１スレッドと、ｉｉ）プログラム構造によって第１スレッドとは別に管理される独立した制御の流れを表す第２スレッドとを使用して、並列処理のための方法ステップを実行するための、マシン実行可能な命令のプログラムを有形に実施し前記方法ステップが、
第２スレッドを使用して、第１スレッドが処理する作業を準備するステップと、
第２スレッドによって準備された作業を、第１スレッドが処理するためにキューに入れるステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが処理する作業を待っている場合、第１スレッドをディスパッチし、それを使用してキュー内の作業を処理するステップと、
第２スレッドによって準備された作業がキューに入れられたときに、第１スレッドが他の作業を処理している場合、第１スレッドを使用して、他の作業の処理を完了し、キュー内の作業にアクセスし、次いでキュー内の作業を処理するステップとを含むプログラム記憶装置。
（１２）前記方法ステップ中、第２スレッドが追加作業をキューに入れ続け、第１スレッドが前の作業の処理を完了し次第、キュー内の追加作業を順次処理する上記（１１）に記載のプログラム記憶装置。
（１３）前記方法ステップ中、第２スレッドが、第１スレッドのキューに入れられた作業を未完了とマークする上記（１１）に記載のプログラム記憶装置。
（１４）前記方法ステップ中、第２スレッドによって準備された作業がキューに入れられたときに第１スレッドが他の作業を処理している場合、第１スレッドがキュー内の作業の処理を完了したとき、第１スレッドを使用して完了作業を完了とマークし、第１スレッド内の前の作業が完了としてマークされるまで、第２スレッドからの後続の作業が待たされる上記（１１）に記載のプログラム記憶装置。
（１５）前記方法ステップ中、他の作業を処理するために第１スレッドが再使用される上記（１１）に記載のプログラム記憶装置。
（１６）前記方法ステップ中、第１スレッドが所望量の作業を完了した後、プログラム構造がそれを破棄する上記（１４）に記載のプログラム記憶装置。
【図面の簡単な説明】
【図１】従来技術による、別々のプログラム用のメモリ構造の概略図である。
【図２】従来技術による、並列プログラム用のメモリ構造の概略図である。
【図３】プレーンと呼ばれる本発明の並列メモリ構造の第１の階層レベルと、２つ以上のプレーンのスペースへのグループ化を示す概略図である。
【図４】図３に示した複数スペースを示す、本発明の並列メモリ構造の第２の階層レベルの概略図である。
【図５】プレーン内のデフォルト・グローバル・データおよび共通（プレーン）メモリ内のデータへのアクセスを示す、図３に示したスペースのコンテキストまたは索引付け構造を表す概略図である。
【図６】各グローバル変数の整数識別を一意の識別にリンクする、コンテキスト索引付け構造の概略図である。
【図７】共通（スペース）メモリによってリンクされ、それぞれが複数のプレーンおよび共通プログラムを有する、複数のスペースの概略図である。
【図８】共通（スペース）グローバル・データ・オブジェクトをリンクするコンテキスト索引付け構造の概略図である。
【図９】システム・メモリによって複数のスレッド・コンテキストに割り振られた別々のメモリ・プールの概略図である。
【図１０】他のスレッドのためにマークされた不使用のメモリ・ブロックの再利用を示す、図９の別々のメモリ・プールの概略図である。
【図１１】作業がそれに割り当てられる抽象データ・オブジェクトとして実装されるスレッドの概略流れ図である。
【符号の説明】
２２５ａ  プレーン
２２５ｂ  プレーン
２３０  スペース
２３０'  スペース
２３０"  スペース
３１０ｅ  メモリ・ブロック
３１０ｆ  メモリ・ブロック
３１０ｇ  メモリ・ブロック
３１０ｈ  メモリ・ブロック
３１３  スイッチ
３１３ａ  スイッチ
３１３ｂ  スイッチ
３１４  スイッチ
３１４ａ  スイッチ
３１４ｂ  スイッチ
３１４ｃ  スイッチ
【図１】
0004398116.tif 000004
【図２】
0004398116.tif 000005
【図３】
0004398116.tif 000006
【図４】
0004398116.tif 000007
【図５】
0004398116.tif 000008
【図６】
0004398116.tif 000009
【図７】
0004398116.tif 000010
【図８】
0004398116.tif 000011
【図９】
0004398116.tif 000012
【図１０】
0004398116.tif 000013
【図１１】
0004398116.tif 000014