【手続補正書】
【提出日】平成28年12月1日(2016.12.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
方法であって、
複数の計算ノードによって実行され、前記計算ノードの各々は少なくとも１つのプロセッサコアとメモリとを含み、方法は、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始めることを備え、前記共用カウンタは、前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能なデータ構造として実施され、前記データ構造はカウント値部分とノード識別子部分とを含み、方法はさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタを標的としたインクリメント演算を開始することと、
前記インクリメント演算を実行する、または前記インクリメント演算の実行を遅らせるよう試みるかを判定することとを備え、前記判定することは、前記データ構造の前記ノード識別子部分に格納された値に少なくとも部分的に依存し、
前記データ構造の前記ノード識別子部分に格納された前記値は、前記複数の計算ノードのうちの特定の１つにおける１つ以上のスレッドが、前記共用カウンタをインクリメントするプライオリティを有するか、または前記共用カウンタをインクリメントするプライオリティを要求したかを示す、方法。
【請求項２】
前記データ構造の前記ノード識別子部分に格納された前記値は、最も新しく前記共用カウンタをインクリメントしたスレッドが実行された前記複数の計算ノードのうちの前記特定の１つを識別し、
前記識別された計算ノード上で実行されるスレッドのインクリメント演算は、前記複数の計算ノードのうちの他のノード上で実行されるスレッドのインクリメント演算よりも高い優先度を有し、
前記判定することは、前記データ構造の前記ノード識別子部分に格納された前記値が、前記所与のスレッドが実行されるノード以外の計算ノードを識別するかを判定することを含む、請求項１に記載の方法。
【請求項３】
前記データ構造の前記ノード識別子部分に格納された前記値は、前記共用カウンタをインクリメントするプライオリティを要求したスレッドが実行された前記複数の計算ノードのうちの前記特定の１つを識別し、
前記判定することは、前記データ構造の前記ノード識別子部分に格納された前記値が、前記所与のスレッドが実行されるノード以外の計算ノードを識別したかを判定することを含む、請求項１に記載の方法。
【請求項４】
インクリメント演算を行なうよう試みることは、前記データ構造の前記カウント値部分に格納された値をインクリメントし、単一のアトミック演算を使用して、前記データ構造の前記ノード識別子部分に、前記所与のスレッドが実行される前記計算ノードの識別子を格納するよう試みることを含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記判定することは、前記データ構造の前記ノード識別子部分の前記値が、前記複数の計算ノード上のスレッドのいずれも前記共用カウンタをインクリメントするプライオリティを有さない、または前記共用カウンタをインクリメントするプライオリティを要求しなかったことを判定することを含み、
前記データ構造の前記カウント値部分に格納された値をインクリメントし、前記所与のスレッドが実行される前記計算ノードの識別子を前記データ構造の前記ノード識別子部分に格納する前記試みは、前記データ構造の前記ノード識別子部分に値を書き込むことなく、前記データ構造の前記カウント値部分をインクリメントする試みが１回以上失敗したことに応答して行なわれる、請求項４に記載の方法。
【請求項６】
前記所与のスレッドが実行される前記計算ノード以外の前記複数の計算ノードのうちの特定の１つにおける１つ以上のスレッドが、前記共用カウンタをインクリメントするプライオリティを有する、または前記共用カウンタをインクリメントするプライオリティを要求したことを判定することに応答し、
前記インクリメント演算の実行を遅らせることと、
前記遅れに続いてインクリメント演算を行なうよう試みることとをさらに備える、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
前記所与のスレッドが実行される前記複数の計算ノードのうちの１つのスレッドが前記共用カウンタをインクリメントするプライオリティを有する、もしくは前記共用カウンタをインクリメントするプライオリティを要求したこと、または前記複数の計算ノードのいずれのスレッドも前記共用カウンタをインクリメントするプライオリティを有さない、もしくは前記共用カウンタをインクリメントするプライオリティを要求しなかったことを判定することに応答して、遅れなくインクリメント演算を行なうよう試みることをさらに備える、請求項１〜６のいずれか１項に記載の方法。
【請求項８】
前記データ構造の前記ノード識別子部分に格納された前記値が前記所与のスレッドが実行されるノード以外の計算ノードを識別することを判定することに応答して、前記所与のスレッドが、前記所与のスレッドが実行される前記計算ノードの識別子をアンチスタベーション変数に格納し、前記共用カウンタをインクリメントするプライオリティについての要求を示すことをさらに備える、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
前記格納に続き、前記所与のスレッドが実行される前記計算ノード上で実行されるスレッドが遅れなくインクリメント演算を行なうよう試みることをさらに備える、請求項８に記載の方法。
【請求項１０】
前記複数の計算ノード上のスレッドはいずれも前記共用カウンタをインクリメントするプライオリティを有さない、または前記共用カウンタをインクリメントするプライオリティを要求しなかったことを示すために、初期もしくはデフォルト値を前記データ構造の前記ノード識別子部分に格納することをさらに備え、
前記格納は、前記マルチスレッドアプリケーションの初期化時、周期的、または前記共用カウンタの競合の減少に応答して行なわれる、請求項１〜９のいずれか１項に記載の方法。
【請求項１１】
システムであって、
複数の計算ノードを備え、各計算ノードは、マルチスレッドを集合的に支持する１つ以上のプロセッサコアと、プログラム命令を格納するメモリとを備え、前記プログラム命令が１つ以上の計算ノード上で実行されると、前記１つ以上の計算ノードは、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始め、前記共用カウンタは、前記複数の計算ノード上で実行される前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能であるデータ構造として実施され、前記データ構造はカウント値部分とノード識別子部分とを含み、前記１つ以上の計算ノードはさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタを標的としたインクリメント演算を開始し、
前記インクリメント演算または前記インクリメント演算の遅延を行なうよう試みるかを判定し、前記判定することは、前記データ構造の前記ノード識別子部分に格納された値に少なくとも部分的に依存し、
前記データ構造の前記ノード識別子部分に格納された前記値は、前記複数の計算ノードのうちの特定の１つにおける１つ以上のスレッドが、前記共用カウンタをインクリメント
するプライオリティを有するか、または前記共用カウンタをインクリメントするプライオリティを要求したかを示す、システム。
【請求項１２】
前記データ構造の前記ノード識別子部分に格納された前記値は、最も新しく前記共用カウンタをインクリメントしたスレッドが実行された前記複数の計算ノードのうちの前記特定の１つを識別する、または前記共用カウンタをインクリメントするプライオリティを要求したスレッドが実行される前記複数の計算ノードのうちの前記特定の１つを識別し、
前記識別された計算ノード上で実行されるスレッドのインクリメント演算は、前記複数の計算ノードのうちの他のノード上で実行されるスレッドのインクリメント演算よりも高い優先度を有し、
前記判定することは、前記データ構造の前記ノード識別子部分に格納された前記値が、前記所与のスレッドが実行されるノード以外の計算ノードを識別するかを判定することを含む、請求項１１に記載のシステム。
【請求項１３】
前記プログラム命令が前記１つ以上の計算ノード上で実行されると、前記１つ以上の計算ノードはさらに、
前記所与のスレッドが実行される前記計算ノード以外の前記複数の計算ノードのうちの特定の１つにおける１つ以上のスレッドが、前記共用カウンタをインクリメントするプライオリティを有する、または前記共用カウンタをインクリメントするプライオリティを要求したことを判定することに応答し、
前記インクリメント演算の実行を遅らせ、
前記遅れに続いてインクリメント演算を行なうよう試みる、請求項１１または１２に記載のシステム。
【請求項１４】
前記プログラム命令が前記１つ以上の計算ノード上で実行されると、前記１つ以上の計算ノードはさらに、
前記所与のスレッドが実行される前記複数の計算ノードのうちの１つのスレッドが前記共用カウンタをインクリメントするプライオリティを有する、もしくは前記共用カウンタをインクリメントするプライオリティを要求したこと、または前記複数の計算ノードのいずれのスレッドも前記共用カウンタをインクリメントするプライオリティを有さない、もしくは前記共用カウンタをインクリメントするプライオリティを要求しなかったことを判定することに応答して、遅れなくインクリメント演算を行なうよう試みる、請求項１１〜１３のいずれか１項に記載のシステム。
【請求項１５】
前記プログラム命令が前記１つ以上の計算ノード上で実行されると、前記１つ以上の計算ノードはさらに、
前記データ構造の前記ノード識別子部分に格納された前記値が前記所与のスレッドが実行されるノード以外の計算ノードを識別することを判定することに応答して、前記所与のスレッドが、前記所与のスレッドが実行される前記計算ノードの識別子をアンチスタベーション変数に格納し、前記共用カウンタをインクリメントするプライオリティについての要求を示し、
前記格納に続き、前記所与のスレッドが実行される前記計算ノード上で実行されるスレッドが遅れなくインクリメント演算を行なうよう試みる、請求項１１〜１４のいずれか１項に記載のシステム。
【請求項１６】
コンピュータ読み取り可能プログラムであって、前記プログラムが１つ以上のコンピュータ上で実行されると、前記１つ以上のコンピュータは、
共用カウンタをインクリメントする１つ以上の演算を含むマルチスレッドアプリケーションの実行を始め、前記共用カウンタは、複数の計算ノード上で実行される前記マルチスレッドアプリケーションの複数のスレッドによってアクセス可能であるデータ構造として
実施され、前記データ構造はカウント値部分とノード識別子部分とを含み、前記１つ以上のコンピュータはさらに、
前記マルチスレッドアプリケーションの所与のスレッドにより、前記共用カウンタを標的としたインクリメント演算を開始し、
前記インクリメント演算または前記インクリメント演算の遅延を行なうよう試みるかを判定し、前記判定することは、前記データ構造の前記ノード識別子部分に格納された値に少なくとも部分的に依存し、
前記データ構造の前記ノード識別子部分に格納された前記値は、前記複数の計算ノードのうちの特定の１つにおける１つ以上のスレッドが、前記共用カウンタをインクリメントするプライオリティを有するか、または前記共用カウンタをインクリメントするプライオリティを要求したかを示す、コンピュータ読み取り可能プログラム。