【手続補正書】
【提出日】平成28年12月2日(2016.12.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
方法であって、
１つ以上の計算ノードによって実行され、前記計算ノードの各々は少なくとも１つのプロセッサコアとメモリとを含み、方法は、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始めることを備え、前記共用カウンタは、前記１つ以上の計算ノード上で実行される前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能なデータ構造として実施され、前記データ構造は更新確率値の表現を格納し、前記更新確率値は、前記共用カウンタをターゲットとするインクリメント演算の開始に応答して前記更新確率値の前記表現が更新される確率を示し、前記共用カウンタの予測値は、前記更新確率値の前記表現に少なくとも部分的に基づいて計算可能であり、方法はさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタをターゲットとしたインクリメント演算を開始することと、
前記開始に応答し、前記インクリメント演算を行なうかを判定することとを備え、前記判定することは、前記データ構造に格納された前記更新確率値の前記表現に少なくとも部分的に依存し、方法はさらに、
前記インクリメント演算が行なわれるという判定に応答して、前記データ構造に格納された前記更新確率値の前記表現を更新することを備え、前記更新された表現は、後続のインクリメント演算の開始に応答して前記データ構造に格納された前記更新確率値の前記更新された表現がさらに更新される確率を表わし、
前記インクリメント演算を行なうかについての前記判定、または前記更新確率値の前記表現の更新のうちの１つ以上は、構成可能な正確性パラメータの所定値に依存する、方法。
【請求項２】
前記複数のスレッドのうちの１つによって前記共用カウンタをターゲットとしたリード演算を行うことを備え、前記リード演算を行なうことは、
前記データ構造に格納された前記更新確率値の前記表現を読み取ることと、
前記データ構造に格納された前記更新確率値の前記表現から前記共用カウンタの前記予測値を計算することと、
前記共用カウンタの前記予測値を返すこととを含む、請求項１に記載の方法。
【請求項３】
前記データ構造は前記更新確率値の浮動小数点表現を格納する、請求項１または２に記載の方法。
【請求項４】
前記更新することは、前記更新確率値の前記浮動小数点表現と前記構成可能な正確性パラメータの前記所定値に依存する定数とを掛け合わせることを含む、請求項３に記載の方法。
【請求項５】
前記データ構造は、仮数部分と指数部分とを含む確率的カウンタ値の二進浮動小数点表現を格納する、請求項１または２に記載の方法。
【請求項６】
前記更新することは、前記構成可能な正確性パラメータの前記所定値に応じて前記仮数部分または前記指数部分のうちの１つ以上を更新することを含む、請求項５に記載の方法。
【請求項７】
前記更新は、後続のインクリメント演算の開始に応答して前記データ構造に格納された前記更新確率値の前記更新された表現がさらに更新される前記確率を減少させる、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記開始することに応答して、乱数を生成することを備え、
前記判定することは、前記生成された乱数にさらに依存する、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
前記マルチスレッドアプリケーションの前記複数のスレッドは、同時に実行されるトランザクションを表わし、前記開始することは、前記同時に実行されるトランザクションのうちの１つにおいてインクリメント演算を開始することを含む、請求項１〜８のいずれか１項に記載の方法。
【請求項１０】
前記データ構造は、正確なカウント値をさらに格納し、
前記データ構造に格納された前記更新確率値の前記表現の前記更新は、前記格納された正確なカウント値をインクリメントする試みが１回以上失敗したことに応答して行なわれる、または競合管理ポリシーの条件を満たしたことに応答して行なわれる、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
前記複数のスレッドのうちの１つにより、前記共用カウンタをターゲットとするリード演算を開始することと、
前記複数のスレッドのうちの前記１つが前記リード演算を開始したことに応答して、
前記データ構造に格納された前記更新確率値の前記表現を読み取ることと、
前記データ構造に格納された前記更新確率値の前記表現から前記共用カウンタの前記予測値を計算することと、
前記格納された正確なカウント値に前記予測値を加算することと、
前記加算することの結果を返すこととをさらに備える、請求項１０に記載の方法。
【請求項１２】
システムであって、
マルチスレッドを支持する１つ以上のプロセッサと、
プログラム命令を格納するメモリとを備え、前記１つ以上のプロセッサ上で前記プログラム命令が実行されると、前記１つ以上のプロセッサは、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始め、前記共用カウンタは、前記１つ以上の計算ノード上で実行される前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能なデータ構造として実施され、前記データ構造は更新確率値の表現を格納し、前記更新確率値は、前記共用カウンタをターゲットとするインクリメント演算の開始に応答して前記更新確率値の前記表現が更新される確率を示し、前記共用カウンタの予測値は、前記更新確率値の前記表現に少なくとも部分的に基づいて計算可能であり、前記１つ以上のプロセッサはさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタをターゲットとしたインクリメント演算を開始し、
前記開始に応答し、前記インクリメント演算を行なうかを判定し、前記判定することは、前記データ構造に格納された前記更新確率値の前記表現に少なくとも部分的に依存し、前記１つ以上のプロセッサはさらに、
前記インクリメント演算が行なわれるという判定に応答して、前記データ構造に格納された前記更新確率値の前記表現を更新し、前記更新された表現は、後続のインクリメント演算の開始に応答して前記データ構造に格納された前記更新確率値の前記更新された表現がさらに更新される確率を表わし、
前記インクリメント演算を行なうかについての前記判定、または前記更新確率値の前記表現の更新のうちの１つ以上は、構成可能な正確性パラメータの所定値に依存する、システム。
【請求項１３】
前記データ構造は前記更新確率値の浮動小数点表現を格納し、
前記更新することは、前記更新確率値の前記浮動小数点表現と前記構成可能な正確性パラメータの前記所定値に依存する定数とを掛け合わせることを含む、請求項１２に記載のシステム。
【請求項１４】
前記データ構造は、仮数部分と指数部分とを含む確率的カウンタ値の二進浮動小数点表現を格納し、
前記更新することは、前記構成可能な正確性パラメータの前記所定値に応じて前記仮数部分または前記指数部分のうちの１つ以上を更新することを含む、請求項１２に記載のシステム。
【請求項１５】
前記プログラム命令が前記１つ以上のプロセッサ上で実行されると、前記１つ以上のプロセッサはさらに、
前記開始することに応答して、乱数を生成し、
前記判定することは、前記生成された乱数にさらに依存する、請求項１２〜１４のいずれか１項に記載のシステム。
【請求項１６】
前記データ構造は、正確なカウント値をさらに格納し、
前記正確なカウント値および前記予測カウント値は前記共用カウンタの前記値を集合的に表わし、
前記データ構造に格納された前記更新確率値の前記表現の前記更新は、前記格納された正確なカウント値をインクリメントする試みが１回以上失敗したことに応答して行なわれる、または競合管理ポリシーの条件を満たしたことに応答して行なわれる、請求項１２〜１５のいずれか１項に記載のシステム。
【請求項１７】
コンピュータ読み取り可能プログラムであって、前記プログラムが１つ以上のコンピュータ上で実行されると、前記１つ以上のコンピュータは、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始め、前記共用カウンタは、前記１つ以上の計算ノード上で実行される前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能なデータ構造として実施され、前記データ構造は更新確率値の表現を格納し、前記更新確率値は、前記共用カウンタをターゲットとするインクリメント演算の開始に応答して前記更新確率値の前記表現が更新される確率を示し、前記共用カウンタの予測値は、前記更新確率値の前記表現に少なくとも部分的に基づいて計算可能であり、前記１つ以上のコンピュータはさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタをターゲットとしたインクリメント演算を開始し、
前記開始に応答し、前記インクリメント演算を行なうかを判定し、前記判定することは、前記データ構造に格納された前記更新確率値の前記表現に少なくとも部分的に依存し、前記１つ以上のコンピュータはさらに、
前記インクリメント演算が行なわれるという判定に応答して、前記データ構造に格納された前記更新確率値の前記表現を更新し、前記更新された表現は、後続のインクリメント演算の開始に応答して前記データ構造に格納された前記更新確率値の前記更新された表現がさらに更新される確率を表わし、前記インクリメント演算を行なうかについての前記判定、または前記更新確率値の前記表現の更新のうちの１つ以上は、構成可能な正確性パラメータの所定値に依存する、コンピュータ読み取り可能プログラム。