(57)【要約】本発明は、格納対象となるデータの第１値を参照する第１の方法と、抽出対象となるデータの第１アドレスを参照する第２の方法に関する。当該データは、作成者と使用者との間で共有されている。第１の方法は、（ｐ−ＶＡｐｒｏｄ）に等しい前記第１値を計算するステップと（ただし、ｐは前記作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは前記作成者の仮想アドレス空間にある）、前記第１値を前記データのアドレスとしてＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）に格納するステップとを有する。任意的に、第１方法は、データをロケーションｐに格納するステップを有する。第２方法は、（ｐ−ＶＡｐｒｏｄ）に等しい第２値をＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）から抽出するステップと（ただし、ｐは前記作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは前記作成者の仮想アドレス空間にある）、前記使用者の仮想アドレス空間にある前記第１アドレスを（ＶＡｃｏｎｓ＋前記第２値）として計算するステップと（ただし、ＶＡｃｏｎｓは、前記使用者の仮想アドレス空間のＳＧＬの使用者アドレスである）を有する。任意的に、第２方法は、前記第１アドレスにより指示されるデータを抽出するステップを有する。これにより、上記方法が共に利用されるとき、使用者が作成者と異なる仮想アドレス空間を有したとしても、作成者は使用者とデータを通信することが可能となる。
2006521617.tif 000002
【特許請求の範囲】
【請求項１】
作成者と利用者の間に共有される格納対象となるデータの第１値を参照する方法であって、
（ｐ−ＶＡｐｒｏｄ）に等しい前記第１値を計算するステップと（ただし、ｐは前記作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは前記作成者の仮想アドレス空間にある）、
前記第１値を前記データのアドレスとしてＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）に格納するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
データをロケーションｐに格納するステップを有することを特徴とする方法。
【請求項３】
作成者と利用者の間に共有される抽出対象となるデータの第１アドレスを参照する方法であって、
（ｐ−ＶＡｐｒｏｄ）に等しい第２値をＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）から抽出するステップと（ただし、ｐは前記作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは前記作成者の仮想アドレス空間にある）、
前記使用者の仮想アドレス空間にある前記第１アドレスを（ＶＡｃｏｎｓ＋前記第２値）として計算するステップと（ただし、ＶＡｃｏｎｓは、前記使用者の仮想アドレス空間のＳＧＬの使用者アドレスである）、
を有することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、さらに、
前記第１アドレスにより指示されるデータを抽出するステップを有することを特徴とする方法。
【請求項５】
請求項１または２記載の方法を実行することを特徴とするコンピュータシステム。
【請求項６】
請求項３または４記載の方法を実行することを特徴とするコンピュータシステム。
【請求項７】
コンピュータ上で実行されると、請求項１または２記載の方法を実行するためのコンピュータ可読媒体に格納されているプログラムコードを有することを特徴とするコンピュータプログラム。
【請求項８】
コンピュータ上で実行されると、請求項３または４記載の方法を実行するためのコンピュータ可読媒体に格納されているプログラムコードを有することを特徴とするコンピュータプログラム。
【請求項９】
マイクロプロセッサシステムへのデータ格納のための請求項１または２記載の方法の利用。
【請求項１０】
マイクロプロセッサシステムへのデータ格納のための請求項３または４記載の方法の利用。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、データが作成者及び利用者間に共有される格納対象となるデータの第１値を参照する第１の方法に関する。
【０００２】
本発明はさらに、データが作成者及び利用者間に共有される抽出または読出し対象となるデータの第１アドレスを参照する第２の方法に関する。
【０００３】
本発明はまた、各方法を実行するコンピュータシステムに関する。
【０００４】
本発明はさらに、各方法を実行するコンピュータプログラムプロダクツに関する。
【０００５】
さらに、本発明は、メモリが付属されているプロセッサとの間のデータ格納及び抽出のための第１及び第２方法の利用に関する。
【０００６】
本発明は、適用されるＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）の分野に関するものである。大部分のコンピュータシステムでは、データバッファのメモリは、隣接するというよりは分散されている。すなわち、バッファの異なる「フラグメント（ｆｒａｇｍｅｎｔ）」は、異なるメモリ位置に物理的に配置されるかもしれない。例えば、ホストコンピュータのメインメモリから２次的な記憶装置へのデータの「分散された」バッファを転送するときには、より連続的に２次的記憶装置に転送できるように、バッファの異なるフラグメントを「収集」する必要がある。ＳＧＬは、通常上記目的のため利用される。ＳＧＬの各要素は、バッファフラグメントの各々に指定され、リストは必要とされる転送のためにフラグメントを効果的に「収集」する。その後、ダイレクト・アクセス・メモリ（ＤＡＭ）コントローラなどのメモリコントローラが、ＳＧＬの連続する各要素に指定されるように転送を実行する。
【０００７】
米国特許第６，４３４，６３５号は、ＳＧＬを用いたデータ転送の入出力アダプタ及び方法を開示している。ＳＧＬは、第１メモリから第２メモリに一定の長さのデータバッファを転送するのに用いられる。他の長さのパッドが、ある長さのデータの連続する部分の各部分が、新たに生成及び更新されたＳＧＬにより転送された後に挿入される。ＳＧＬの各要素は、データセグメントのスタートと長さを指定する。当該転送は、入出力アダプタの一例としてのＤＭＡコントローラにより実行可能である。
【０００８】
典型的には、データの作成者と利用者がメインメモリを共有する。しかしながら、作成者の仮想アドレス空間は、利用者の仮想アドレス空間と異なっている。作成者が共有メモリからのデータを利用者と通信することを所望するときに問題が生じる。作成者のＳＧＬは、作成者の仮想アドレス空間におけるデータのアドレスへの参照を含む。これに伴い、利用者のＳＧＬは、自分の仮想アドレス空間における同一のデータのアドレスへの参照を含む。利用者は作成者と異なる仮想アドレス空間を有するため、作成者が当該データを利用者にどのようにして通信することができるという問題が生じる。同様の問題は、物理的メモリがプロセッサの異なるアドレスマップにある物理的メモリにも当てはまる。
【０００９】
上記問題は、特に図３、４及び５に図示され、主張されるような本方法により解決される。
【００１０】
本発明の一効果は、使用中のメモリまたは未使用のメモリを追跡することに通常は関連するすべてのポインタ・アリスメトリック（ｐｏｉｎｔｅｒ−ａｒｉｔｈｍｅｔｒｉｃ）が、ＳＧＬにより隠されているということである。
【００１１】
本発明のさらなる効果は、それが記憶装置や他のアドレス空間だけでなくメインメモリにも適用可能であるということである。
【００１２】
本発明のさらなる効果は、ＳＧＬのＦＩＦＯ動作がＳＧＬを、アプリケーションやファイルシステムなどのシステムのレイヤ間だけでなく、下位レイヤにおける自然な非同期インタフェースとするということである。すなわち、当該効果は単一プロセッサシステムだけでなく、複数プロセッサ共有メモリシステムにも適用される。
【００１３】
本コンピュータシステム及びコンピュータプログラムプロダクツはそれぞれ、同様の効果を提供し、上記方法に関して共に及び個別に上述されたような同一の理由に対して、同一の問題を解決する。
【００１４】
本発明は、好適な実施例に関して、図面を参照することにより、以下において十分に説明される。
【００１５】
図面を通じて、同一の参照番号は、同様または対応する特徴、機能、リストなどを示す。
【００１６】
図１は、２つのＳＧＬに対する作成者及び利用者の動作方法を示す。
【００１７】
ＳＧＬ（Ｓｃａｔｔｅｒ  Ｇａｔｈｅｒ  Ｌｉｓｔ）は、メモリメモリロケーションの論理シーケンスを記述する抽象的データタイプ（ＡＤＴ）であるかもしれない。しかしながら、ＳＧＬはより抽象性の低いデータタイプを有するかもしれないということは当業者には知られている。メインメモリロケーションの当該論理シーケンスは、連続性を有する必要はなく、すなわち、それらはメモリ上に分散されていてもよい。ロケーションは、典型的には論理エンドに追加することが可能であり、ロケーションはＳＧＬの論理スタートのみから取得及び削除することができる。ＡＰＩ、すなわち、アプリケーション・プログラマ・インタフェースは、作成者が高々１人、利用者が高々１人しかいない限り、ＳＧＬ１２が追加的な同期方法なしに作成者１０と利用者１１との間のＦＩＦＯ機構として利用されることを可能にする。単独の作成者と利用者は、自動的に同期化される。複数の作成者間の同期は、臨界領域、ミューテック、セマフォなどの追加的な方法を必要とする。複数の利用者に対しても、上記ケースがあてはまる。ポインタ１３、１４及び１５は、循環バッファデータに対するメモリ１６がＳＧＬにより維持及び参照される方法を一般的に示すのに図示される。典型的に、これらのポインタは、データが（作成者から）書き込みまたは格納されるアドレスを追跡し、これに応じて、他のポインタによりデータが（利用者から）読出しまたは抽出されるアドレスを追跡する。従来技術から、一般にポインタは、（データの）作成者と利用者との間のＦＩＦＯ機構を維持するのに利用することができるということが知られている。
【００１８】
典型的な利用例として、循環バッファのデータを保持するメモリが連続し、エンプティＳＧＬが単一のユニットを含む、すなわち、メモリの連続部分のアドレスと長さを含む単一のタプル、あるいは空の部分は分割されている場合には２つのユニットを含むと仮定するとき、ＳＧＬを用いてフルパートとエンプティパートが容易に記述される循環バッファ１６があげられる。この例では、フルＳＧＬは最も古いデータを記述するユニットから始めて、そのようなユニットを２つ有する。バッファのラップアラウンド（ｗｒａｐ−ａｒｏｕｎｄ）は、エンプティＳＧＬまたはフルＳＧＬにあるか、あるいはそのどちらにもないかもしれない。ＳＧＬの先頭には、本例ではトリガー機能１７とコールバック機能１８により、作成者と利用者との間の同期のための機構が任意的に適用される。ここで説明される同期は、上述のものとは異なる。ここでは、それはポーリング（ｐｏｌｌｉｎｇ）を回避するのに適用されている。
【００１９】
トリガー及びコールバック機能は、典型的には、作成者と利用者の実行状況の分離を維持するため、リリース、シグナルまたは同様の動作を実行するにすぎない。循環バッファのメモリは連続である必要はなく、この場合、ＳＧＬは単により多くのユニットを含むであろう。
【００２０】
当該機能名（トリガー、コールバック）は、作成者と利用者が異なるレイヤにいるときに典型的なものである。そうでない場合、直接的にこれはセマフォ、キューなどに対する処理とすることができる。ＳＧＬにより記述されるすべてのデータは、同一のアドレス空間に属す必要があり、このため一部のＳＧＬでは、これはすべての仮想メモリまたは物理的メモリとすることが可能であるが、これらの組み合わせは許可されない。これに対する理由は、ＳＧＬ  ＡＰＩが論理的に連続するユニットとメモリにおいて連続するユニットを合成するということである。
【００２１】
このフラグメントの合成は、「デ・フラグメンテーション（ｄｅ−ｆｒａｇｍｅｎｔａｔｉｏｎ）」として知られている。このようなデ・フラグメンテーションは任意的なものであり、必須のものではない。もちろん、それはリソース（ＣＰＵ、メモリなど）の利用に関して効果的である。
【００２２】
ＳＧＬは、例えば、論理ブロックアドレスやセクタ数に関して、小さいＩＤＥ  ＨＤＤ上に配置されているデータを記述するのに利用することができる。当該ＳＧＬは、マルチプロセッサシステムに属する１以上のプロセッサにより適用されてもよい。これにより、付属の対応するメモリを有するプロセッサは、本発明によりデータの読出し及び書き込みを実行することができる。
【００２３】
従って、本発明の一効果は、それがメインメモリと他のアドレス空間に適用可能であり、マルチプロセッサシステムに適用可能であるということである。
【００２４】
プロセッサがデータを生成し、利用者が同一のデータを利用するとき、ＳＧＬの整合性を確実にするため、一定のルールが守られる必要がある。
【００２５】
利用者は、フルＳＧＬからデータを有するメモリを取得し、それを使用し、当該メモリをエンプティＳＧＬに追加する。
【００２６】
このため、本発明の一効果は、ＳＧＬのＦＩＦＯ動作がＳＧＬをアプリケーションやファイルシステムなどのシステムのレイヤ間、及び／または下位レイヤ上の自然な非同期インタフェースをするということである。作成者と利用者は共に、ＳＧＬの長さまたはサイズを取得するようにしてもよい。返された長さは、ＳＧＬにより記述されるデータの合計サイズを示す。
【００２７】
ＳＧＬが共有メモリにあり、ＳＧＬのみがこの同じ共有メモリのロケーションを記述している場合、ＳＧＬはマップにおいてこの共有メモリを有するすべての（仮想）メモリ空間から利用することができる。このとき、共有メモリのこの部分は、上述されたような「同一のアドレス空間」であるとみなされるが、それは他のいくつかのアドレス空間から可視的なものとすることができる。これらの場合におけるＡＰＩは、特定のＡＰＩを呼び出すプロセスのアドレス空間の仮想アドレスを常に使用する。共有メモリのスタートアドレスは異なるメモリスペースに対しては異なるものとすることが可能であるため、本発明によるＳＧＬ構成は、図３に示されるように、自らの仮想アドレスに関してオフセットを内部的に維持する。
【００２８】
従って、本発明のさらなる効果は、ＳＧＬがＡＰＩ仕様の一部として利用可能であるということである。
【００２９】
図２は、ＳＧＬの機能内容を示す。ＳＧＬ３１は、矢印方向３２により示されるような論理データシーケンスを記述するのに使用される。データはすべてメモリ上に分散されていてもよい。ＳＧＬにより記述されているデータは、異なるサイズのデータ領域に配置されてもよく、すなわち、Ｍｅｍ１、Ｍｅｍ２などは異なるサイズを有するかもしれない。矢印方向３４は、メモリ３３のメモリアドレス順序を示す。
【００３０】
図に示されるようなＳＧＬインスタンス化は、一定数のスキャッタ・ギャザ（ＳＧ）・ユニット（すなわち、Ａ、Ｂ、Ｃ、Ｄ及びＥ）を有し、Ｍｅｍ３、Ｍｅｍ２、Ｍｅｍ４及びＭｅｍ１の論理データシーケンスを記述する。図におけるＳＧＬインスタンス化は、完全に記載されたものではなく、追加的な１つの連続データ領域が、ＳＧユニットＥに添付可能である。ここで、論理データ（Ａ、Ｂ、Ｃ、Ｄ）の順序は、メモリアドレス順序と同一のものである必要はないということに留意されたい。
【００３１】
さらに、図示されたユニット（Ａ〜Ｅ）はＳＧＬに内部的なものであるということに留意されたい。
【００３２】
図３は、共有メモリにおけるＳＧＬの一例を示す。共有メモリは、２本の破線の間に示される。参照番号２０は、作成者の仮想アドレス空間を示し、参照番号２１は利用者の仮想アドレス空間を示す。
【００３３】
ここで、作成者と利用者が共に双方のＳＧＬ上であるが、ＳＧＬの異なるエンド上で処理を行っており、作成者がメモリやデータの取得、「エンプティ」ＳＧＬ上のメモリの削除、「フル」ＳＧＬ上の添付処理などの処理を実行する。利用者については、それは逆となる。
【００３４】
上述のように、共有メモリのスタートアドレスは異なるメモリスペースに対しては異なるものとすることができるため、本発明による方法はそれぞれ、この図に示されるように、自らの仮想アドレスに関してオフセットを内部的に維持する。本方法はそれぞれ、図４及び５により説明されるであろう。
【００３５】
利用者が作成者と異なる仮想アドレス空間を有することから、作成者が利用者とデータを通信する方法が問題となっていた。実際、両者のＳＧＬは共有メモリにあるため、両者のアドレス空間は双方のＳＧＬを含んでいる。ここで、作成者はフルＳＧＬに添付を行い、利用者は同一のフルＳＧＬからメモリ／データの取得及び（データの）削除などの処理を実行する。この同一のフルＳＧＬの仮想アドレスは２つのアドレス空間において異なるものとなりうるという問題がある。この問題は、作成者が自分の仮想アドレス空間、すなわち、ＶＡｐｒｏｄ２６におけるＳＧＬのアドレスを知っており、これにより、利用者は自分の仮想アドレス空間、すなわち、ＶＡｃｏｎｓ２８におけるＳＧＬのアドレスを知っていることから解決される。
【００３６】
言い換えると、作成者と共に利用者は、エンプティＳＧＬとフルＳＧＬの両方の仮想アドレスを知っており、すなわち、作成者と利用者は共にもちろん異なるエンドから双方のＳＧＬに対し動作する。通信対象となるデータのアドレスは、作成者のアドレス空間ではｐとなる。このアドレスｐをＳＧＬに格納する代わりに、フルＳＧＬのアドレスに関するｐのオフセットは、フルＳＧＬに格納される（オフセット＝ｐ−ＶＡｐｒｏｄ）。
【００３７】
この同一のＳＧＬからアドレスを抽出するため利用者により呼び出されるＡＰＩは、利用者の仮想アドレス空間のデータ（ｑ）のアドレス２７を構成するのに利用される（ｑ＝ＶＡｃｏｎｓ＋オフセット）。理解されるように、このオフセットはＶＡｃｏｎｓとＶＡｐｒｏｄの仮想アドレス空間の間をリンクさせるのに利用される。
【００３８】
図４は、格納対象となるデータの第１値を参照する方法を示す。この図は、格納されるＳＧＬのアドレスに関するｐのオフセットに関して図３に与えられる説明に対応し、すなわち、ＳＧＬにおいて、オフセット＝ｐ−ＶＡｐｒｏｄとなる。
【００３９】
本方法は以下の２つのステップを有する。
【００４０】
ステップ１００において、第１値が計算される。それはｐ−ＶＡｐｒｏｄに等しい。ｐは作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは作成者の仮想アドレス空間にある。
【００４１】
ステップ２００において、第１値は、当該ＳＧＬのデータのアドレスとして格納される。
【００４２】
さらにこのステップにおいて、当該データの長さを格納することが可能である。
【００４３】
本方法はさらに、ステップ３００を有するようにしてもよい。
【００４４】
ここでは、データが格納される。データはロケーションＰに格納される。典型的には、まずデータが格納され、その後、ＳＧＬにメモリが添付される。そうでない場合、レース（ｒａｃｅ）条件が存在し、すなわち、利用者はデータが作成者により格納される前に、アドレスを取得する。
【００４５】
図５は、抽出対象となるデータの第１アドレスを参照する方法を示す。この図は、ＳＧＬに格納されているＳＧＬのアドレスに関するｐのオフセットに関して図３に与えられる説明に対応している（オフセット＝ｐ−ＶＡｐｒｏｄ）。この図はさらに、オフセットが再利用される方法及び場所に関するものであり、すなわち、この計算されたオフセットは、ＳＧＬにより自分の仮想アドレス空間のデータのアドレス（ｑ）を構成するのに利用される。すなわち、ｑ＝ＶＡｃｏｎｓ＋オフセットとなる。
【００４６】
抽出対象となるデータの第１アドレスを参照する方法は、以下の２つのステップを有する。
【００４７】
ステップ４００において、ＳＧＬから第２値が抽出される。この第２値は、ＳＧＬに対する追加データ処理中に以前に計算されたものである。それは、ｐ−ＶＡｐｒｏｄに等しい。このｐは作成者の仮想アドレス空間にあり、ＶＡｐｒｏｄは作成者の仮想アドレス空間にある。
【００４８】
このステップは、前の図のステップ１００に対応している。
【００４９】
ステップ５００において、第１アドレスｑが計算される。それは、（ＶＡｃｏｎｓ−第２値）に等しい。ＶＡｃｏｎｓは、利用者の仮想アドレス空間のＳＧＬの利用者アドレスであり、第１アドレスは、利用者の仮想アドレス空間にある。
【００５０】
その後、メモリ／データ取得機能または処理は、計算されたアドレス、すなわち、第１アドレスｑを返す。
【００５１】
本方法はさらに、以下のステップ６００を有するようにしてもよい。
【００５２】
ここでは、データが抽出または読み出される。データは第１アドレスにより指示される。
【００５３】
コンピュータ可読媒体は、磁気テープ、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、コンパクトディスク（記録可能ＣＤ、書き換え可能ＣＤ）、ミニディスク、ハードディスク（ＩＤＥ、ＡＴＡなど）、フロッピー（登録商標）ディスク、スマートカード、ＰＣＭＣＩＡカードなどであってもよい。
【００５４】
説明された第１の方法は、マルチプロセッサシステムにおけるデータ格納に利用されてもよい。
【００５５】
説明された第２の方法は、マルチプロセッサシステムのプロセッサにより実行されるデータ抽出に利用されてもよい。
【００５６】
請求項において、カッコ内の参照記号は、請求項を限定するものとして構成されてはいない。「有する」という用語は、請求項に列挙した以外の要素またはステップの存在を排除するものでない。要素に前置される「ある」という用語は、そのような要素が複数存在することを排除するものではない。
【００５７】
本発明は、複数の相異なる要素を有するハードウェア及び適切にプログラムされたコンピュータにより実現することが可能である。複数の手段を列挙した装置クレームでは、これらの手段の一部は単一のハードウェアアイテムにより実現することが可能である。ある手段が互いに異なる従属クレームに記載されているという事実は、これらの手段の組み合わせが効果的に利用できないことを示すものではない。
【図面の簡単な説明】
【００５８】
【図１】図１は、２つのＳＧＬ上で作成者と利用者が動作する方法を示す。
【図２】図２は、ＳＧＬの機能内容を示す。
【図３】図３は、共有メモリにおけるＳＧＬの一例を示す。
【図４】図４は、格納対象となるデータの第１値を参照する方法を示す。
【図５】図５は、抽出対象となるデータの第１アドレスを参照する方法を示す。
【図１】
2006521617.tif 000003
【図２】
2006521617.tif 000004
【図３】
2006521617.tif 000005
【図４】
2006521617.tif 000006
【図５】
2006521617.tif 000007
【国際調査報告】
2006521617.tif 000008
2006521617.tif 000009