JP6333371B2 - キャッシュ線中でビット配列を実装するための方法 - Google Patents

Description

本発明は、コンピューティング・システムに関し、より詳細には、キャッシュ線中でビット配列を実装するための方法に関する。

多くのマルチスレッド化されたコンピュータ・システムは、種々の規模の会社にとって、より重要な技術の１つになる。これらは、コンピューティング・ハードウェア・プラットフォームの計算効率およびフレキシビリティを高める。マルチスレッド化されたコンピュータ・システム上でのマルチスレッド化された操作は、ビット配列の個々のビットに対して論理演算を実施する、ビット単位の原子的メモリ操作（ＡＭＯ: Atomic MemoryOperations）を含むことがある。このようなＡＭＯは、ストアのような操作であるｓｔｏｒｅＡＮＤ、ｓｔｏｒｅＯＲ、ｓｔｏｒｅＸＯＲ、および、ロードのような操作であるｆｅｔｃｈＡＮＤ、ｆｅｔｃｈＯＲ、ｆｅｔｃｈＸＯＲを含む。

本発明の実施形態の目的は、改善された方法、コンピュータ・システム、およびコンピュータ・プログラム製品を提供することである。この目的は、独立請求項の主題によって解決される。従属請求項に、有利な実施形態が記載される。

本明細書において使用されるような原子的メモリ操作（ＡＭＯ）は、共有データに対するリード−モディファイ−ライト（read-modify-write）操作を指す。ＡＭＯは、あるスレッドのリード−モディファイ−ライト操作が別のスレッドによる干渉なしで実施されるという意味で、原子的である。言い換えれば、スレッドまたはプロセッサが共有データにアクセスする（例えば同時にアクセスする）場合、各リードまたはライトまたはＡＭＯアクセスは、別のアクセスからの干渉なしで、原子的に実施される。

一態様では、本発明は、メモリ・ストレージとコントローラとを備えるメモリ・システムのキャッシュ線中でビット配列を実装するための方法に関する。

方法は、キャッシュ線中でビット配列を構成するステップを含み、ビット配列はビットの配列を含み、構成するステップはさらに、ビット配列中の各ビットの値を定義するステップを含む。方法はまた、コントローラによってビット配列に対する操作の要求を受け取るステップを含み、要求は、メモリ・ストレージ中におけるキャッシュ線の場所と、要求を指定する情報とを示す。方法はまた、コントローラ（２０６）によって、この情報を使用して、ビット配列に対する１つまたは複数のアクションを操作について識別するステップを含み、１つまたは複数のアクションは、コントローラ中でエンコードされる。方法はまた、要求を受け取るのに応答して、１つまたは複数のエンコードされたアクションを実行することによって要求を実施するステップを含む。

ビット配列は、個々のビットを記憶するデータ構造である。すなわち、各配列要素は、単一のビットに対応する。ビット配列の各要素は、２つの値０と１のうちの一方を記憶する。ビット配列の各要素は、固有のインデックスによって識別される。通常、Ｅ個の要素を含むビット配列には、インデックス値０〜（Ｅ−１）が使用される。

ビット配列を実装することは、ビット配列の個々のビットならびに一群のビットに対してビット単位の論理演算を実施するために、キャッシュ線の少なくとも一部にアクセスするのを可能にすることができる。例えば、ビット配列の各ビットは、メモリ・システムを備えるコンピュータ・システムのリソースのインスタンスを表すことができる。このビット配列に対する操作は、例えば、ユーザ（例えばスレッド）が、対応する１つまたは複数のビットの値を１にセットすることによって原子的にこの１つまたは複数のリソース・インスタンスの「所有者」になるのを可能にすることができる。

例えば、ビット配列の各ビットは、複数のスレッドによって共有されるロックのセット中のロックを表すことができる。このビット配列に対する操作は、例えば、スレッドが、高性能に、かつ低プログラミング労力で、複数のロックを原子的に獲得するのを可能にすることができる。

例えば、ビット配列の各ビットの１または０の値は、優先キュー中の特定の要素の有無を表すことができる。このような優先キューは、Ｅ個までの固有の要素を有し、各要素は、ビット配列の各インデックスに対応するように、０〜Ｅ−１の番号が付いた固有の優先順位を有する。

これらの特徴は、同時スレッドの場合には特に、従来の方法と比較して、ビット配列に対するより高いレートの操作を可能にできるので有利であろう。これは、ビット配列に対する操作が、他のデータ構造に対する従来の操作よりも速い単純な操作となり得るという事実によるものであろう。

これらの特徴は、ビット配列を、複数のスレッドによって同時データ構造として使用するのを可能にすることができる。例えば、要求された操作は、ＡＭＯとすることができる。受け取られた要求は、ビット配列に対する操作を求める、複数のスレッドからコントローラによって受け取られた複数の同時要求のうちの１つとすることができる。受け取られた同時要求は、順次実施されるものとすることができる。コントローラは、このような複数の同時スレッドを実施および管理するように適合されたものとすることができる。コントローラは、メモリ・アクセス要求を受け入れる受信機と、返答を返す送信機とを備えることができ、それぞれは、複数の同時スレッドのメモリ・アクセスに応じるために、先入れ先出しバッファ（ＦＩＦＯ）を備えることができる。

これらの特徴は、例えば、この要求など、ビット配列にアクセスする要求を複数のスレッドが同時に発行するマルチスレッド化されたアプリケーションで、複数のユーザまたはスレッドがビット配列を利用するための単一のインタフェースを提供することができる。

別の利点は、メモリ・システムが、従来の原子的メモリ操作を超えた新しい原子的メモリ操作を実装してビット配列を使用できることであろう。例えば、ＡＭＯは、プロセッサ・ストアまたはロード命令の変形とすることができる。

要求される操作は、キャッシュ線のアドレスのみを必要とすればよく、ビット配列の要素のアドレスを必要としない。

一実施形態によれば、要求は、「最初の０−ビットをフェッチしてセットする」要求を含む。要求を実施するステップは、ビット配列の各ビットをインデックス０から順次読み取るアクションと、値０を有する最初のビットが見つかった場合に、見つかった最初のビットのインデックスを返して、見つかった最初のビットの値を１にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。

０−ビットという用語は、値０を有するビットを指す。１−ビットという用語は、値１を有するビットを指す。

Ｅ個の要素を含むビット配列の場合、「最初の０−ビットをフェッチしてセットする」要求は、０〜Ｅ−１のうちのインデックス値を返す。ビット配列中に０−ビットが存在しない場合は、事前定義済みの失敗値は、有効なインデックスに対応しないものとすることができる。例えば、失敗値は、Ｅ、すなわちビット配列のビット数であってよい。

他のビット単位ＡＭＯによってキャッシュ線にアクセスすることもできる。例えば、ｓｔｏｒｅＡＮＤ（）のようなビット単位ＡＭＯが、１２８バイト・キャッシュ線内の８バイト・ワードをアドレス指定して修正する。例えば、スレッドが、「最初の０−ビットをフェッチしてセットする」要求を発行して、値０を有する最初のビットのインデックスに対応するリソースを得る。スレッドは、リソースを使用した後、キャッシュ線中の適切なワードに対してｓｔｏｒｅＡＮＤ（）操作を発行して、このビットを値０にセットし、したがってリソースを再び利用可能にする。このように、ビット配列を、メモリ・ページ、ｉｎｏｄｅ、ディスク・セクタなどの割振りに使用することができる。

一実施形態によれば、要求は、「最後の０−ビットをフェッチしてセットする」要求を含み、ビット配列はＥ個の要素を含む。要求を実施するステップは、ビット配列の各ビットをインデックスＥ−１から順次読み取るアクションと、ビット配列の、値０を有する最後のビットが見つかった場合に、最後のビットのインデックスを返して、この最後のビットの値を１にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。

一実施形態によれば、要求は、「１−ビットをカウントする」要求を含む。要求を実施するステップは、ビット配列の各ビットを読み取るアクションと、値１を有するビットの数をカウントするアクションと、カウントの結果を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、このような要求は、ポピュレーション・カウント要求としても知られる。

一実施形態によれば、要求は、「孤立した０−ビットをフェッチしてセットする」要求を含む。要求を実施するステップは、ビット配列を読み取って、０値を有するビットの、０個以上の連続的なシーケンスを決定するアクションと、見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、１つまたは複数の連続的なシーケンスをそれらのビット数に基づいてランク付けし、１つまたは複数の連続的なシーケンスのうちで最小数のビットを有する連続的なシーケンスのビットを選択し、選択されたビットのインデックスを返し、選択されたビットの値を１にセットするアクションと、のうちの１つまたは複数を実施するステップを含む。

これは、他の同時操作によって使用されるかもしれない可能な最長の０の連続を保存することができるので、有利であろう。これは、ビット配列が、メモリ・ページやディスク・ブロックなど、何らかのリソースの連続的なインスタンスを表すときに、有利であろう。この場合、０の連続を保存することで、何らかの将来のリソース獲得のために連続的な利用可能なリソースが保存される。このような将来の獲得では、「Ｎ個の連続的な０−ビットをフェッチしてセットする」要求をビット配列に対して使用することができる。

一実施形態によれば、要求は、「最初の１−ビットをフェッチする」要求を含む。要求を実施するステップは、ビット配列の各ビットをインデックス０から順次読み取るアクションと、値１を有する最初のビットが見つかった場合に、見つかった最初のビットのインデックスを返し、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、「最初の１−ビットをフェッチする」要求を使用して、ビット配列に基づく優先キュー中で優先順位の最も高い要素を識別することができる。

一実施形態によれば、要求は、「最初の１−ビットをフェッチしてクリアする」要求を含む。要求を実施するステップは、ビット配列の各ビットをインデックス０から順次読み取るアクションと、値１を有する最初のビットが見つかった場合に、見つかった最初のビットのインデックスを返して、見つかった最初のビットの値を０にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、「最初の１−ビットをフェッチしてクリアする」要求を使用して、ビット配列に基づく優先キュー中で優先順位の最も高い要素を識別して除去することができる。

一実施形態によれば、要求は、「最後の１−ビットをフェッチしてクリアする」要求を含み、ビット配列はＥ個の要素を含む。要求を実施するステップは、ビット配列の各ビットをインデックスＥ−１から順次読み取るアクションと、ビット配列の、値１を有する最後のビットが見つかった場合に、最後のビットのインデックスを返して、最後のビットの値を０にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、「最後の１−ビットをフェッチしてクリアする」要求を使用して、ビット配列に基づく優先キュー中で優先順位の最も低い要素を識別して除去することができる。

一実施形態によれば、要求は、「Ｎ番目の１−ビットをフェッチする」要求を含み、要求は、Ｎの値を提供する。要求を実施するステップは、ビット配列の各ビットをインデックス０から順次読み取るアクションと、値１を有するビットのＮ番目の発生が見つかった場合に、見つかったＮ番目の１−ビットのインデックスを返し、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、要求がＮに対して値１を提供する場合は、要求は、「最初の１−ビットをフェッチする」要求と等価である。例えば、４つのスレッドがあるシナリオでは、「Ｎ番目の１−ビットをフェッチする」要求により、各スレッドが、優先キュー中の４つの上位要素の１つを識別することができる。

一実施形態によれば、要求は、「Ｎ番目の１−ビットをフェッチしてクリアする」要求を含み、要求は、Ｎの値を提供する。要求を実施するステップは、ビット配列の各ビットをインデックス０から順次読み取るアクションと、値１を有するビットのＮ番目の発生が見つかった場合に、見つかったＮ番目の１−ビットのインデックスを返して、見つかったビットの値を０にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。例えば、性能の異なる２つのスレッドが優先キュー中の要素を処理する場合、速いスレッドおよび遅いスレッドが、Ｎに対して値１および２をそれぞれ提供すれば、アプリケーション性能目標が最もよく満たされるであろう。

一実施形態によれば、要求は、「孤立した１−ビットをフェッチしてクリアする」要求を含む。要求を実施するステップは、ビット配列を読み取って、１の値を有するビットの、０個以上の連続的なシーケンス決定するアクションと、見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、１つまたは複数の連続的なシーケンスをそれらのビット数に基づいてランク付けし、最小数のビットを有する連続的なシーケンスのビットを選択し、選択されたビットのインデックスを返し、選択されたビットの値を０にセットするアクションと、のうちの１つまたは複数を実施するステップを含む。

一実施形態によれば、要求は、「Ｎ個の連続的な０−ビットをフェッチしてセットする」要求を含む。要求を実施するステップは、ビット配列を読み取って、０の値を有するＮ個のビットの、０個以上の連続的なシーケンスを決定するアクションと、見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、１つまたは複数の連続的なシーケンスのうちで事前定義済みの条件を満たすシーケンスを選択し、選択されたシーケンスの最初のビットのインデックスを返し、選択されたＮ個のビットを値１にセットするアクションと、のうちの１つまたは複数を実施するステップを含む。

これは、例えば、スレッドがＮ個のリソースのシーケンスの所有権を原子的に獲得するのを可能にすることができる。ビット配列中にＮ個の連続的な０−ビットが存在しない場合は、事前定義済みの失敗値が返されてよい。このようなリソース・シーケンスは、メモリ・ページ、ｉｎｏｄｅ、ディスク・セクタなどの割振りの際に使用することができる。

一実施形態によれば、事前定義済みの条件は、シーケンスがビット配列の最初のＮ個の連続的なビットを含むこと、を含む。一実施形態によれば、ビット配列を循環バッファとして扱うことができ、したがって、Ｎ個のビットの連続的なシーケンスは、ビット配列の始めの連続的なシーケンスと、ビット配列の終わりの連続的なシーケンスとからなるものとすることができる。

一実施形態によれば、要求は、「Ｎ個の指定された０−ビットをフェッチしてセットする」要求を含む。要求を実施するステップは、ビット配列を読み取って、指定されたインデックスにある指定されたビットを突き止めるアクションと、指定されたビットの少なくとも１つのビットが値１を有する場合に、事前定義済みの失敗値を返すアクションと、指定されたビットの各々が値０を有する場合に、指定された各ビットを値１にセットして、事前定義済みの成功値を返すアクションと、のうちの１つまたは複数を実施するステップを含む。これは、スレッドが複数のロックを原子的に得るのを可能にすることができる。

「Ｎ個の指定された０−ビットをフェッチしてセットする」要求では、要求の中の１つまたは複数の値が、要求される０−ビットのインデックスを効率的に指定することができる。例えば、２５６個までの要素を含むビット配列の場合、要求は８バイト値を提供することができ、８バイトの各々はビット・インデックスを指定する。８ビット未満を指定するには、バイトのいくつかは同じインデックスを指定する。言い換えれば、Ｓ個の０−ビットを指定するには、８バイトは、Ｓ個の固有のインデックスを指定する。例えば、１０２４個までの要素を有するビット配列の場合、要求は６４ビット値を提供することができ、最下位の６０ビットは、それぞれ１０ビットの６つのフィールドとして扱われ、６つのフィールドの各々はビット・インデックスを指定する。

本発明の「指定されたＮ個の０−ビットをフェッチしてセットする」要求は、各プロセスまたはスレッドがロックの共有セットからの複数のロックを保持しなければならない場合の、細分性ロッキング(granular locking)の問題に対処する。この場合、セット中のロックの数は、ビット配列中のビットの数Ｅまでであり、セット中の各ロックには、０〜Ｅ−１の番号が付いているものとすることができる。本発明がなければ、細分性ロッキングは、微妙なロック依存性を生み出す可能性がある。この微妙さは、プログラマが知らずにデッドロックを導入することになる機会を増大させる可能性がある。したがって、本発明がなければ、ロックは、比較的入念な（オーバヘッド）ソフトウェア・サポートと、アプリケーション・プログラミングが厳格な約定を完全に厳守することとによってのみ、構成可能である（例えば、原子的にアイテムＸをテーブルＡから削除してＸをテーブルＢに挿入するために、複数の同時ロックを管理する）。

それぞれロックされるべき、セットのオブジェクトの数がＥよりも多い場合は、各オブジェクトを０とＥ−１との間の数にハッシュして、より粗いロック細分性の性能コストでビット配列の使用を可能にすることができる。

例えば、ビット配列は、メモリ・システムの２つ以上のキャッシュ線中で実装されてよく、２つ以上のキャッシュ線は、隣接するキャッシュ線である。ビット配列に対する操作の要求は、２つ以上の隣接するキャッシュ線と、メモリ・システム中における２つ以上のキャッシュ線のうちの第１のキャッシュ線の場所とを示すことができる。

別の態様では、本発明は、前述の実施形態のうちのいずれか１つの方法の方法ステップを実施するためのコンピュータ実行可能命令を含むコンピュータ・プログラム製品に関する。

別の態様では、本発明は、キャッシュ線中でビット配列を実装するためのシステムに関し、このシステムは、メモリ・ストレージおよびコントローラを備える。このシステムは、キャッシュ線中でビット配列を構成するように構成され、ビット配列はビットの配列を含み、構成することはさらに、ビット配列中の各ビットの値を定義することを含む。このシステムはまた、コントローラによってビット配列に対する操作の要求を受け取るように構成され、要求は、メモリ・ストレージ中におけるキャッシュ線の場所と、要求を指定する情報とを示す。このシステムはまた、この情報を使用して、ビット配列に対する１つまたは複数のアクションを操作について識別するように構成され、１つまたは複数のアクションは、コントローラ中でエンコードされる。このシステムはまた、要求を受け取るのに応答して、１つまたは複数のエンコードされたアクションを実行することによって要求を実施するように構成される。

メモリ・システムは、キャッシュ階層中のレベルであってよく、したがって、コントローラが要求を実施すると、その結果、キャッシュ階層中のより低いレベルへのメモリ・システム・アクセスとなり、それによりメタデータおよび要素がメモリ・キャッシュ中で確立されるものとすることができる。メモリ・システムは２つ以上の部分に分離していてよく、ある部分におけるコントローラが、その部分におけるメモリを使用して動的配列データ構造を操作することができる。キャッシュ・レベルは２つ以上のユニットとして複製されてよく、コントローラは、キャッシュ・ユニット内の、基礎をなすキャッシュまたはメモリ・レベルの任意の部分にアクセスすることができる。

本明細書において使用されるように、「コンピュータ可読ストレージ媒体」は、コンピューティング・デバイスのプロセッサによって実行可能な命令を記憶できる任意の有形ストレージ媒体を包含する。コンピュータ可読ストレージ媒体は、コンピュータ可読の非一時的なストレージ媒体と呼ばれる場合がある。コンピュータ可読ストレージ媒体はまた、有形のコンピュータ可読媒体と呼ばれる場合もある。いくつかの実施形態では、コンピュータ可読ストレージ媒体はまた、コンピューティング・デバイスのプロセッサによってアクセス可能なデータを記憶することが可能であってよい。コンピュータ可読ストレージ媒体の例は、以下のものに限定されないが、フロッピー（Ｒ）・ディスク、磁気ハード・ディスク・ドライブ、固体ハード・ディスク、フラッシュ・メモリ、ＵＳＢサム・ドライブ、ランダム・アクセス・メモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、光ディスク、光磁気ディスク、および、プロセッサのレジスタ・ファイルを含む。光ディスクの例は、コンパクト・ディスク（ＣＤ）およびディジタル多用途ディスク（ＤＶＤ）、例えば、ＣＤ−ＲＯＭ、ＣＤ−ＲＷ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＷ、またはＤＶＤ−Ｒディスクを含む。コンピュータ可読ストレージ媒体という用語はまた、ネットワークまたは通信リンクを介してコンピュータによってアクセス可能な様々なタイプの記録媒体を指す。例えば、モデム、インターネット、またはローカル・エリア・ネットワークを介して、データを取り出すことができる。コンピュータ可読媒体に組み入れられたコンピュータ実行可能コードは、以下のものに限定されないが、ワイヤレス、ワイヤ線、光ファイバ・ケーブル、ＲＦなど、またはこれらの任意の適切な組合せを含めた、任意の適切な媒体を使用して送信することができる。

コンピュータ可読信号媒体は、例えばベースバンド中でまたは搬送波の一部として、コンピュータ実行可能コードが組み入れられた、伝搬データ信号を含むことができる。このような伝搬信号は、以下のものに限定されないが、電磁、光学、またはこれらの任意の適切な組合せを含めた、様々な形のいずれかをとることができる。コンピュータ可読信号媒体は、コンピュータ可読ストレージ媒体でない任意のコンピュータ可読媒体であって、命令実行システム、装置、またはデバイスによって使用されるプログラムまたはそれらに関連して使用されるプログラムを通信、伝搬、または搬送できる任意のコンピュータ可読媒体とすることができる。

「コンピュータ・メモリ」または「メモリ」は、コンピュータ可読ストレージ媒体の例である。コンピュータ・メモリは、プロセッサから直接にアクセス可能な任意のメモリである。「コンピュータ・ストレージ」または「ストレージ」は、コンピュータ可読ストレージ媒体のさらに他の例である。コンピュータ・ストレージは、任意の不揮発性コンピュータ可読ストレージ媒体である。いくつかの実施形態では、コンピュータ・ストレージはコンピュータ・メモリでもある場合があり、またはその逆の場合もある。

本明細書において、「プロセッサ」は、プログラムまたは機械実行可能命令またはコンピュータ実行可能コードを実行できる、電子コンポーネントを包含する。「プロセッサ」を備えるコンピューティング・デバイスに言及する場合、これは、複数のプロセッサまたは処理コアを備える可能性があると解釈されるべきである。プロセッサは、例えば、マルチコア・プロセッサとすることができる。プロセッサはまた、単一のコンピュータ・システム内にあるかまたは複数のコンピュータ・システム間で分散された、プロセッサの集合を指す場合がある。コンピューティング・デバイスという用語もまた、１つまたは複数のプロセッサをそれぞれが備える複数のコンピューティング・デバイスの集合またはネットワークを指す可能性があると解釈されるべきである。コンピュータ実行可能コードは、同じコンピューティング・デバイス内にある場合のある、さらには複数のコンピューティング・デバイスにわたって分散されている場合のある、複数のプロセッサによって実行されることがある。

コンピュータ実行可能コードは、本発明の一態様をプロセッサに実施させる機械実行可能命令またはプログラムを含むことができる。本発明の態様に関する動作を行うためのコンピュータ実行可能コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語や類似のプログラミング言語などの従来の手続き型プログラミング言語を含めた、１つまたは複数のプログラミング言語の任意の組合せで書かれて、機械実行可能命令にコンパイルされてよい。いくつかの事例では、コンピュータ実行可能コードは、高水準言語の形であるかまたは事前コンパイルされた形であるものとすることができ、機械実行可能命令をオンザフライで生成するインタープリタと共に使用されてよい。

コンピュータ実行可能コードは、完全にユーザのコンピュータ上で実行されるか、スタンドアロン・ソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行されるか、部分的にユーザのコンピュータ上で実行され部分的にリモート・コンピュータ上で実行されるか、または完全にリモート・コンピュータもしくはサーバ上で実行される場合がある。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含めた任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、または、接続は、外部コンピュータに対して（例えば、インターネット・サービス・プロバイダを使用してインターネットを介して）行われてもよい。

本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品の、フローチャート、説明、またはブロック図、あるいはそれらの全てに関して、本発明の態様を述べる。適切なときは、フローチャート、説明、またはブロック図、あるいはそれらの全ての、各ブロック、またはブロックの一部を、コンピュータ実行可能コードの形のコンピュータ・プログラム命令によって実装できることは理解されるであろう。さらに、相互排他的でないときは、異なるフローチャート、説明、またはブロック図、あるいはそれらの全ての中のブロックを組み合わせてもよいことも理解されたい。これらのコンピュータ・プログラム命令は、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実装するための手段をもたらすように、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに提供されて、マシンを生み出すことができる。

これらのコンピュータ・プログラム命令はまた、コンピュータ可読媒体に記憶された命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実装する命令を含む製造品を生み出すように、コンピュータ可読媒体に記憶され、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスに、特定の方式で機能するよう指示することができる。

コンピュータ・プログラム命令はまた、コンピュータまたは他のプログラム可能装置上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実装するためのプロセスを提供するように、コンピュータ実装プロセスを生み出すべく、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実施させることができる。

当業者には理解されるであろうが、本発明の態様は、装置、方法、またはコンピュータ・プログラム製品として具現化することができる。したがって、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、または、ソフトウェアとハードウェアの態様を組み合わせた実施形態の形をとることができ、これらは全て、本明細書では「回路」、「モジュール」、または「システム」と一般に呼ばれる場合がある。さらに、本発明の態様は、コンピュータ実行可能コードを組み入れた１つまたは複数のコンピュータ可読媒体において具現化されるコンピュータ・プログラム製品の形をとることもできる。

前述の実施形態の１つまたは複数は、組み合わせられた実施形態が相互排他的でない限り、組み合わせることができることを理解されたい。

以下、図面を参照しながら、本発明の好ましい実施形態について、単なる例としてより詳細に述べる。

メモリ中のキャッシュ線中でビット配列を実装するための方法を実行するように動作可能なシステム・アーキテクチャを示す図である。 メモリ・システムの例示的なブロック図である。 ビット配列に対する操作のシーケンスを示す図である。 メモリ中のキャッシュ線中でビット配列を実装するための方法のフローチャートである。

以下では、図中で同様の番号が付された要素は、同様の要素を示すか、または等価な機能を実施する要素を示すかのいずれかである。機能が等価である場合、前に論じられた要素が必ずしも後の図でも論じられるとは限らない。

図１に、コンピューティング・システム１００中のコンピュータ・システム（またはサーバ）１１２が、汎用コンピューティング・デバイスの形で示されている。コンピュータ・システム１１２のコンポーネントは、以下のものに限定されないが、１つまたは複数のプロセッサまたは処理ユニット１１６と、メモリ・システム１２８と、メモリ・システム１２８を含めた様々なシステム・コンポーネントをプロセッサ１１６に結合するバス１１８とを含むことができる。

コンピュータ・システム１１２は通常、様々なコンピュータ・システム可読媒体を備える。このような媒体は、コンピュータ・システム１１２によってアクセス可能な任意の利用可能な媒体とすることができ、揮発性と不揮発性の媒体、取外し可能と非取外し可能の媒体の両方を含む。

メモリ・システム１２８は、ランダム・アクセス・メモリ（ＲＡＭ）またはキャッシュ・メモリあるいはその両方など、揮発性メモリの形のコンピュータ・システム可読媒体を含むことができる。メモリ・システムは、１つまたは複数のアクティブ・バッファ付きメモリ・デバイスを含むことができる。アクティブ・バッファ付きデバイスは、複数のメモリ要素（例えばチップ）を備えることができる。アクティブ・バッファ付きメモリ・デバイスは、３次元（「３Ｄ」）メモリ・デバイスを形成するメモリの層を含むことができ、この場合、チップの個々の列が、処理ユニット１１６と通信するヴォールト（ｖａｕｌｔ）を形成する。アクティブ・バッファ付きメモリ・デバイスは、複数の処理要素によって同時にアクセスできる区分を含むことができ、これらの区分は、ヴォールトを含めた（ただしこれに限定されない）、任意の適切なメモリ・セグメントとすることができる。

処理ユニット１１６は、アプリケーションを実装するために、動的配列データ構造および関連するメタデータを利用して、メモリ・システムに要求を発行することができる。

コンピュータ・システム１１２はまた、キーボード、ポインティング・デバイス、ディスプレイ１２４など、１つもしくは複数の外部デバイス１１４；ユーザがコンピュータ・システム１１２と対話できるようにする１つもしくは複数のデバイス；または、コンピュータ・システム１１２が１つもしくは複数の他のコンピューティング・デバイスと通信できるようにする任意のデバイス（例えば、ネットワーク・カード、モデムなど）、あるはそれらの全てと、通信することができる。このような通信は、Ｉ／Ｏインタフェース１２２を介して行うことができる。さらに、コンピュータ・システム１１２は、ローカル・エリア・ネットワーク（ＬＡＮ）、一般ワイド・エリア・ネットワーク（ＷＡＮ）、または公衆ネットワーク（例えばインターネット）、あるいはそれらの全てなど、１つまたは複数のネットワークと、ネットワーク・アダプタ１２０を介して通信することができる。図示のように、ネットワーク・アダプタ１２０は、バス１１８を介して、コンピュータ・システム／サーバ１１２の他のコンポーネントと通信する。

図２に、メモリ・システム１２８の例示的なブロック図を詳細に示す。メモリ・システム１２８は、コントローラ２０６およびメモリ・ストレージ２０８を備える。メモリ・ストレージ２０８は、例えば、キャッシュまたはランダム・アクセス・メモリ（ＲＡＭ）など、任意の適切な物理メモリとすることができる。

コントローラ２０６は、バス１１８と通信するように構成された、要求２１０の受信機２１４、および返答２１２の送信機２１６を備え、受信機２１４および送信機２１６はそれぞれ、先入れ先出しバッファを備える。コントローラ２０６は、要求２１０に応答して、ストレージ２０８へのリード・アクセスおよびライト・アクセスを実施し、返答２１２を返すことができる。

メモリ・ストレージ２０８は、１つまたは複数のキャッシュ線２１１を備える。キャッシュ線２１１へは、ビット配列としてアクセスすることができ、ビット配列はビット値０または１を含むことができる。ビット配列がキャッシュ線２１１中で実装されてよく、これは例えば、ビット単位の操作を使用してキャッシュ線の少なくとも一部にアクセスするために、キャッシュ線のこの少なくとも一部を構成することによって、行われる。

述べたメモリ・システムの構造は、例えば、要求２１０など、キャッシュ線にアクセスする要求を複数のスレッドが同時に発行するマルチスレッド化されたアプリケーションで、複数のユーザまたはスレッドがビット配列を利用するための単一のインタフェースを提供することができる。

ビット配列２２１に対する操作の要求２１０は、コントローラ２０６によって、この操作要求に対応するアクションを実行することで実施される。これらのアクションは、コントローラ中でエンコードされる。

要求元またはユーザからの要求２１０は、コントローラ２０６の受信機２１４によってバス１１８から受け取られる。要求元は、アプリケーションを実行しているスレッド、例えば、ＡＭＯを実行しているスレッドとすることができる。要求２１０は、メモリ中におけるキャッシュ線の場所を示す。

要求２１０は、ビット配列の全ての要素を０にセットするかまたは全ての要素を１にセットする操作要求など、ビット配列３１８に対する操作を求める任意の適切な要求とすることができる。これは、ビット配列の初期化を可能にすることができる。要求は、１にセットされたビットの数、最初の１−ビット、中間の１−ビット、または最初の遷移ビット（すなわち、先行０が１に変化するかまたはその逆のとき）を返す操作要求を含むことができる。要求はさらに、最初のブリップ（ｂｌｉｐ）全体を返してクリアする操作要求を含むことができる。例えば、配列００００１１０１の場合、位置４および長さ２が返され、結果的な配列は０００００００１となる。中間の１−ビットは、配列中で前後に同数の１−ビットがあるビットを指す。

通信２１８で、コントローラ２０６によって、ビット配列３１８のビットまたはビット・グループにアクセスすることができ、このアクセスは要求２１０の中の操作に基づく。要求２１０が「最初の０−ビットをフェッチする」要求である例では、通信２１８で読み取られた、値０を有する最初のビットの値が、コントローラ２０６によって返答２１２中でユーザに送信される。

図３に、ビット配列（例えば２１１）に対する操作のシーケンスを説明する図を示す。ビット配列３１８．１は、固定数のビットを含む。記述を簡単にするために、ビット配列３１８．１はキャッシュ線の最初の２４ビットを含むものとして示す。ビット位置は、行３３３に示すように、左から右にラベル付けされている。

操作は、同時要求として、要求されてメモリ・システムのコントローラ（例えば２０６）によって受け取られてよく、以下のように順次、処理されてよい（例えば１つずつ）。操作の順序は任意とすることができる。

シーケンスの操作３０１は、ビット配列３１８．１中で値０を有する最初のビットのインデックスを返してからこのビットを値１にセットするための、fetchAndSetFirst0Bit(cacheLineAddress)に対応する。このために、コントローラ２０６は、値０を有する最初のビット（すなわちインデックス００）が見つかるまで、ビット配列を、インデックス００を有するビットから順次読み取ることができる。次いで、コントローラは、インデックス００を返すことができる。次に、コントローラは、ビット００の値を１にセットし、この結果、ビット配列３１８．２となる。

シーケンスの操作３０３もまた、ビット配列３１８．２中で値０を有する最初のビットのインデックスを返してからこのビットを値１にセットするための、fetchAndSetFirst0Bit(cacheLineAddress)に対応する。このために、コントローラ２０６は、値０を有する最初のビット（すなわちインデックス０３）が見つかるまで、ビット配列を、インデックス００を有するビットから順次読み取ることができる。次いで、コントローラは、インデックス０３を返すことができる。次に、コントローラは、ビット００の値を１にセットし、この結果、ビット配列３１８．３となる。

シーケンスの操作３０５は、ビット配列３１８．３中の連続的な２つの０−ビットの最初のセットの最初のビットのインデックスを返してから、この２つのビットを値１にセットするための、fetchAndSetFirstNcontiguous0Bits(cacheLineAddress,2)に対応する。このために、コントローラ２０６は、値０をそれぞれが有する最初の連続的な２つのビット（すなわちインデックス０６、０７）が見つかるまで、ビット配列３１８．３を、インデックス００を有するビットから順次読み取ることができる。次いで、コントローラは、インデックス０６を返すことができ、２つのビット０６および０７の値を１にセットし、この結果、ビット配列３１８．４となる。

シーケンスの操作３０７は、ビット配列３１８．４中の連続的な４つの０−ビットの最初のセットの最初のビットのインデックスを返してから、この４つのビットを値１にセットするための、fetchAndSetFirstNcontiguous0Bits(cacheLineAddress,4)に対応する。このために、コントローラ２０６は、値０をそれぞれが有する最初の連続的な４つのビット（すなわちインデックス１１〜１４）が見つかるまで、ビット配列３１８．４を、インデックス００を有するビットから順次読み取ることができる。次いで、コントローラは、インデックス１１を返すことができ、４つのビット１１〜１４の値を１にセットし、この結果、ビット配列３１８．５となる。

シーケンスの操作３０９は、fetchAndSetNgiven0Bits(cacheLineAddress,3,x04090F)に対応する。第２の引数３は、３つのビットを０から１に変更できることを示す。第３の引数０ｘ０４０９１１は、３つの所望のビットのインデックスが０ｘ０４、０ｘ０９、０ｘ１１＝＝１７であることを示す。次いで、コントローラは、ビット配列３１８．５からこれらの３つのビットの各々の値を読み取り、各ビットが値０を有するかどうか判定することができる。コントローラは、１を返して成功を示すことができ、３つのビットの各々の値を１にセットすることができ、この結果、ビット配列３１８．６となる。

シーケンスの操作３１１は、fetchAndSetNgiven0Bits(cacheLineAddress,2,x0108)に対応する。第２の引数２は、２つのビットを０から１に変更できることを示す。第３の引数０ｘ０１０８は、２つの所望のビットのインデックス０ｘ０１、０ｘ０８を示す。次いで、コントローラは、ビット配列３１８．６からこれらの２つのビットの各々の値を読み取り、各ビットが値０を有するかどうか判定することができる。この場合、２つのビットのうちの一方が値１を有する。コントローラは、ビット配列３１８．６の内容を変更せずに、事前定義済みの失敗値０を返して要求失敗を示すことができる。

図４は、図１に示すメモリ・システムなどのメモリ・システムを操作して、キャッシュ線中で、例えばメモリ・システム中の単一のキャッシュ線中で、ビット配列を実装するための、例示的な方法およびシステムのフローチャートである。

ステップ４０１で、キャッシュ線の少なくとも一部にビット配列としてアクセスできるように、キャッシュ線がメモリ中で構成される。例えば、１０２４個の要素を含むビット配列として、キャッシュ線にアクセスすることができる。

ステップ４０３で、ユーザまたは要求元からの、ビット配列に対する操作の要求が、コントローラによって受け取られる。要求２１０は、操作に関するキャッシュ線のアドレス場所を提供する。要求を発行した要求元は、プロセッサ上で実行されているスレッドや、バッファ付きメモリ・スタックに含まれる処理要素や、ネットワーク・インタフェース・ロジックを経由してネットワークを介して通信するスレッドなど、任意の適切なユーザとすることができる。

ステップ４０５で、コントローラは、この情報を使用して、ビット配列に対する１つまたは複数のアクションを、操作について識別する。１つまたは複数のアクションは、コントローラ中でエンコードされる。複数のアクションがコントローラ中でエンコードされてよい。１つまたは複数のアクションを識別するステップは、複数のアクションから１つまたは複数のアクションを選択するステップを含むことができる。

ステップ４０７で、コントローラは、１つまたは複数のアクションを実行して要求を実施する。例えば、要求は、ビット配列中で値０を有する最初のビットのインデックスを返してからこのビットを値１にセットするための、「最初の０−ビットをフェッチしてセットする」要求を含むことができる。

図示のように、ステップ４０７に続いて、コントローラは、次の要求２１０に応じるために待機し、ブロック４０３に戻る。

最初の構成ステップ４０１は、最初の構成中に１回実施すればよく、ステップ４０３〜４０７は、操作を求める各要求がコントローラ２０６によって応じられるときに繰り返すことができる。

１００ コンピューティング・システム
１１２ サーバ
１１４ 外部デバイス
１１６ プロセッサ
１２０ ネットワーク・アダプタ
１２２ Ｉ／Ｏインタフェース
１２４ ディスプレイ
１２８ メモリ・システム
２０６ コントローラ
２０８ メモリ・ストレージ
２１０ 要求
２１１ キャッシュ線
２１２ 返答
２１３ メタデータ・フィールド
２１４ 受信機
２１５ 要素フィールド
２１６ 送信機
２１８ 通信
２２０ 通信
３０１ 操作
３０３ 操作
３０５ 操作
３０７ 操作
３０９ 操作
３１１ 操作
３３３ 行
４０１ ステップ
４０３ ステップ
４０５ ステップ
４０７ ステップ

Claims (15)

1. メモリ・ストレージとコントローラとを備えるメモリ・システムのキャッシュ線中でビット配列を実装するための方法であって、
   − 前記キャッシュ線中で前記ビット配列を構成するステップであって、前記ビット配列がビットの配列を含み、前記構成するステップがさらに、前記ビット配列中の各ビットの値を定義するステップを含む、前記構成するステップと、
   − 前記コントローラによって前記ビット配列に対する操作の要求を受け取るステップであって、前記要求が、前記メモリ・ストレージ中における前記キャッシュ線の場所と、前記要求を指定する情報とを示す、前記受け取るステップと、
   − 前記コントローラによって前記情報を使用して前記ビット配列に対する１つまたは複数のアクションを前記操作について識別するステップであって、前記１つまたは複数のアクションが前記コントローラ中でエンコードされる、前記識別するステップと、
   − 前記要求を受け取るのに応答して、前記１つまたは複数のエンコードされたアクションを実行することによって前記要求を実施するステップと、を含む方法。
2. 前記要求が「最初の０−ビットをフェッチしてセットする」要求を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列の各ビットをインデックス０から順次読み取るアクションと、
   − 値０を有する最初のビットが見つかった場合に、前記見つかった最初のビットのインデックスを返して、前記見つかった最初のビットの前記値を１にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１に記載の方法。
3. 前記要求が「最後の０−ビットをフェッチしてセットする」要求を含み、前記ビット配列がＥ個の要素を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列の各ビットをインデックスＥ−１から順次読み取るアクションと、
   − 前記ビット配列の、値０を有する最後のビットが見つかった場合に、前記最後のビットのインデックスを返して、前記最後のビットの前記値を１にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
4. 前記要求が「孤立した０−ビットをフェッチしてセットする」要求を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列を読み取って、０値を有するビットの、０個以上の連続的なシーケンスを決定するアクションと、
   − 見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、
   ・ 前記１つまたは複数の連続的なシーケンスをそれらのビット数に基づいてランク付けし、
   ・ 前記１つまたは複数の連続的なシーケンスのうちで最小数のビットを有する連続的なシーケンスのビットを選択し、
   ・ 前記選択されたビットのインデックスを返し、
   ・ 前記選択されたビットの前記値を１にセットするアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
5. 前記要求が「最初の１−ビットをフェッチしてクリアする」要求を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列の各ビットをインデックス０から順次読み取るアクションと、
   − 値１を有する最初のビットが見つかった場合に、前記見つかった最初のビットのインデックスを返して、前記見つかった最初のビットの値を０にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
6. 前記要求が「最後の１−ビットをフェッチしてクリアする」要求を含み、前記ビット配列がＥ個の要素を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列の各ビットをインデックスＥ−１から順次読み取るアクションと、
   − 前記ビット配列の、値１を有する最後のビットが見つかった場合に、前記最後のビットのインデックスを返して、前記最後のビットの値を０にセットし、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
7. 前記要求が「孤立した１−ビットをフェッチしてクリアする」要求を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列を読み取って、１の値を有するビットの、０個以上の連続的なシーケンス決定するアクションと、
   − 見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、
   ・ 前記１つまたは複数の連続的なシーケンスをそれらのビット数に基づいてランク付けし、
   ・ 最小数のビットを有する連続的なシーケンスのビットを選択し、
   ・ 前記選択されたビットのインデックスを返し、
   ・ 前記選択されたビットの値を０にセットするアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
8. 前記要求が「Ｎ個の連続的な０−ビットをフェッチしてセットする」要求を含み、前記要求を実施する前記ステップが、
   − 前記ビット配列を読み取って、０の値を有するＮ個のビットの、０個以上の連続的なシーケンスを決定するアクションと、
   − 見つかったシーケンスが０個の場合に、事前定義済みの失敗値を返し、そうでない場合に、
   ・ 前記１つまたは複数の組合せのうちで事前定義済みの条件を満たすシーケンスを選択し、
   ・ 前記選択されたＮ個のビットのシーケンスの最初のビットのインデックスを返し、
   ・ 前記選択されたＮ個のビットの値を１にセットするアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
9. 前記シーケンスが前記ビット配列の最初のＮ個の連続的なビットを含むことを、前記事前定義済みの条件が含む、請求項８に記載の方法。
10. 前記要求が「Ｎ個の指定された０−ビットをフェッチしてセットする」要求を含み、前記要求を実施する前記ステップが、
    − 前記ビット配列を読み取って、指定されたインデックスにある前記指定されたビットを突き止めるアクションと、
    − 前記指定されたビットの少なくとも１つのビットが値１を有する場合に、事前定義済みの失敗値を返すアクションと、
    − 前記指定されたビットの各々が値０を有する場合に、指定された各ビットを値１にセットして、事前定義済みの成功値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
11. 前記要求が「１−ビットをカウントする」要求を含み、前記要求を実施する前記ステップが、
    − 前記ビット配列の各ビットを読み取るアクションと、
    − 値１を有するビットの数をカウントするアクションと、
    − 前記カウントの結果を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
12. 前記要求が「最初の１−ビットをフェッチする」要求を含み、前記要求を実施する前記ステップが、
    − 前記ビット配列の各ビットをインデックス０から順次読み取るアクションと、
    − 値１を有する最初のビットが見つかった場合に、前記見つかった最初のビットのインデックスを返し、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
13. 前記要求が「Ｎ番目の１−ビットをフェッチする」要求を含み、前記要求がＮの値を提供し、前記要求を実施する前記ステップが、
    − 前記ビット配列の各ビットをインデックス０から順次読み取るアクションと、
    − 値１を有するビットのＮ番目の発生が見つかった場合に、前記見つかったＮ番目の１−ビットのインデックスを返し、そうでない場合に、事前定義済みの失敗値を返すアクションと、のうちの１つまたは複数を実施するステップを含む、請求項１または２に記載の方法。
14. 請求項１ないし１３のいずれか一項に記載の方法の方法ステップをコンピュータに実行させるプログラム。
15. キャッシュ線中でビット配列を実装するためのシステムであって、メモリ・ストレージおよびコントローラを備え、
    − 前記キャッシュ線中で前記ビット配列を構成することであって、前記ビット配列がビットの配列を含み、前記構成することがさらに、前記ビット配列中の各ビットの値を定義することを含む、前記構成することと、
    − 前記コントローラによって前記ビット配列に対する操作の要求を受け取ることであって、前記要求が、前記メモリ・ストレージ中における前記キャッシュ線の場所と、前記要求を指定する情報とを示す、前記受け取ることと、
    − 前記情報を使用して前記ビット配列に対する１つまたは複数のアクションを前記操作について識別することであって、前記１つまたは複数のアクションが前記コントローラ中でエンコードされる、前記識別することと、
    − 前記要求を受け取るのに応答して、前記１つまたは複数のエンコードされたアクションを実行することによって前記要求を実施することと、を行うように構成されたシステム。
    

Images