【手続補正書】
【提出日】平成25年8月15日(2013.8.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するための方法であって、当該方法を実行するシステムが、複数のプロセッサと、前記複数のプロセッサと通信可能に結合された共有ランダム・アクセス・メモリとを備えており、前記共有ランダム・アクセス・メモリがその中に複数のキュー可用性フラグの対を格納し、前記複数のキュー可用性フラグの対のうちの各キュー可用性フラグの対は、複数のワークキュー内の個々の関連付けられたワークキューに関連付けられており、各キュー可用性フラグは、個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグを含み、個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグそれぞれは、個々のキュー可用性フラグの対に関連付けられた個々の関連付けられたワークキューの新しいタスクを受け入れるための可用性を示し、
前記方法は、
前記複数のキュー可用性フラグの対内の少なくとも１つのフラグに基づくローカル・プロセッサ上で、新しいタスクを受け入れるために選択されたプロセッサに関連付けられた選択されたワークキューの可用性を判断するステップであって、前記ローカル・プロセッサ及び前記選択されたプロセッサはマルチプロセッサ・アーキテクチャ内にあり、かつ、前記共有ランダム・アクセス・メモリにアクセスする、前記判断するステップと、
前記可用性を判断することに応答して、前記新しいタスクを、前記選択されたワークキューに割り当てるステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであることを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないと判断することに応答して、前記選択されたプロセッサに関連付けられた前記ワークキューのサイズに基づいて、選択されたリモート・キュー可用性フラグを更新するステップであって、前記選択されたリモート・キュー可用性フラグは前記選択されたワークキューに関連付けられたキュー可用性フラグの対のうちのリモート・キュー可用性フラグである、前記更新するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであると判断することに応答して且つ前記新しいタスクを割り当てることに応答して、前記複数のキュー可用性フラグの対内の任意のフラグを変更しないことを判断するステップであって、当該任意のフラグを変更しないことを判断することが前記選択されたワークキューのサイズと独立している、前記判断するステップと
を含む、前記方法。
【請求項２】
前記マルチプロセッサ・アーキテクチャ内の個々の複数のプロセッサに関連付けられた複数のワークキューについての複合キュー・サイズを繰り返し求めるステップであって、前記複数のワークキューは全てが１つのタイプのものである、前記繰り返し求めるステップ
をさらに含み、
前記選択されたリモート・キュー可用性フラグを更新するステップは、
前記複合キュー・サイズに基づいて、上限比較値を導き出すステップと、
前記選択されたプロセッサに関する前記リモート・キュー可用性フラグを前記上限比較サイズと比較するステップと、
前記リモート・キュー可用性フラグが前記上限比較値より大きいことを示す前記比較することに応答して、新しいタスクを受け入れるのに前記選択されたプロセッサと関連した前記ワークキューが利用不能であることを示すように、前記リモート・キュー可用性フラグを設定するステップと
をさらに含む、請求項１に記載の方法。
【請求項３】
前記個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグは、前記共有ランダム・アクセス・メモリ内の個々の別のキャッシュ・ラインに格納される、請求項１又は２に記載の方法。
【請求項４】
前記可用性を判断するステップは、
前記選択されたプロセッサが前記ローカル・プロセッサであることを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないと判断することに応答して、前記選択されたプロセッサに関する前記リモート・キュー可用性フラグを検査するステップと、
前記選択されたプロセッサは前記ローカル・プロセッサであると判断することに応答して、前記選択されたプロセッサに関する前記ローカル・キュー可用性フラグを検査するステップと
を含む、請求項１に記載の方法。
【請求項５】
前記ローカル・プロセッサによって、前記ローカル・プロセッサに関連付けられた前記ワークキューから実行すべきタスクを受け入れるステップと、
前記タスクを受け入れることに応答して、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記リモート・キュー可用性フラグを更新するステップと、
前記タスクを受け入れること及び前記選択されたワークキューのサイズと独立していることに応答して、前記ローカル・キュー可用性フラグを更新しないステップと
をさらに含む、請求項４に記載の方法。
【請求項６】
各々の繰り返し実行時に、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記ローカル・キュー可用性フラグを繰り返し更新するステップを含み、前記繰り返し更新するステップは、前記タスクの受け入れとは関係のない時点で行なわれる、請求項４に記載の方法。
【請求項７】
前記繰り返し更新することとは関係のない時点で、前記マルチプロセッサ・アーキテクチャ内のそれぞれの複数のプロセッサに関連付けられた複数のワークキューについての複合キュー・サイズを繰り返し求めるステップであって、前記複数のワークキューは全てが１つのタイプのものである、前記繰り返し求めるステップをさらに含み、
前記ローカル・キュー可用性フラグを繰り返し更新するステップは、
前記複合キュー・サイズに基づいて上限比較値を導き出すステップと、
前記選択されたプロセッサに関するワークキューのサイズを前記上部比較値と比較するステップと、
前記ローカル・キュー可用性フラグが前記上限比較値より大きいことを示す前記比較することに応答して、新しいタスクを受け入れるのに前記ローカル・プロセッサに関連付けられた前記ワークキューが利用不能であることを示すように、前記ローカル・キュー可用性フラグを設定するステップと
をさらに含む、請求項６に記載の方法。
【請求項８】
前記繰り返し更新するステップは、ランダムな時間間隔で実行される、請求項５に記載の方法。
【請求項９】
新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのシステムであって、
複数のプロセッサと、
前記複数のプロセッサと通信可能に結合された共有ランダム・アクセス・メモリであって、前記共有ランダム・アクセス・メモリがその中に複数のキュー可用性フラグの対を格納し、前記複数のキュー可用性フラグの対のうちの各キュー可用性フラグの対は、複数のワークキュー内の個々の関連付けられたワークキューに関連付けられており、各キュー可用性フラグは、個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグを含み、個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグそれぞれは、個々のキュー可用性フラグの対に関連付けられた個々の関連付けられたワークキューの新しいタスクを受け入れるための可用性を示す、前記共有ランダム・アクセス・メモリと、
タスク分散プロセッサであって、
前記複数のキュー可用性フラグの対内の少なくとも１つのフラグに基づくローカル・プロセッサ上で、新しいタスクを受け入れるために選択されたプロセッサに関連付けられた選択されたワークキューの可用性を判断するステップであって、前記ローカル・プロセッサ及び前記選択されたプロセッサはマルチプロセッサ・アーキテクチャ内にあり、かつ、前記共有ランダム・アクセス・メモリにアクセスする、前記判断するステップと、
前記可用性を判断することに応答して、前記新しいタスクを、前記選択されたワークキューに割り当てるステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであることを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないと判断することに応答して、前記選択されたプロセッサに関連付けられた前記ワークキューのサイズに基づいて、選択されたリモート・キュー可用性フラグを更新するステップであって、前記選択されたリモート・キュー可用性フラグは前記選択されたワークキューに関連付けられたキュー可用性フラグの対のうちのリモート・キュー可用性フラグである、前記更新するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであると判断することに応答して且つ前記新しいタスクを割り当てることに応答して、前記複数のキュー可用性フラグの対内の任意のフラグを変更しないことを判断するステップであって、当該任意のフラグを変更しないことを判断することが前記選択されたワークキューのサイズと独立している、前記判断するステップ
を実行するように適合された前記タスク分散プロセッサと
を備えている、前記システム。
【請求項１０】
前記マルチプロセッサ・アーキテクチャ内の個々の複数のプロセッサに関連付けられた複数のワークキューについての複合キュー・サイズを繰り返し求めるように適合された複合キュー・サイズ・プロセッサであって、前記複数のワークキューは全て１つのタイプのものである、前記複合キュー・サイズ・プロセッサをさらに備えており、
前記タスク分散プロセッサは、
前記複合キュー・サイズに基づいて、上限比較値を導き出すステップと、
前記選択されたプロセッサに関する前記リモート・キュー可用性フラグを前記上限比較サイズと比較するステップと、
前記リモート・キュー可用性フラグが前記上限比較値より大きいことを示す前記比較することに応答して、新しいタスクを受け入れるのに前記選択されたプロセッサと関連した前記ワークキューが利用不能であることを示すように、前記リモート・キュー可用性フラグを設定するステップと
を実行することによって、前記少なくとも１つのキュー可用性フラグを調整するように適合される、請求項９に記載のシステム。
【請求項１１】
前記個々のローカル・キュー可用性フラグ及び個々のリモート・キュー可用性フラグは、前記共有ランダム・アクセス・メモリ内の個々の別のキャッシュ・ラインに格納される、請求項９又は１０に記載のシステム。
【請求項１２】
前記タスク分散プロセッサは、
前記選択されたプロセッサが前記ローカル・プロセッサであることを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないと判断することに応答して、前記選択されたプロセッサに関する前記リモート・キュー可用性フラグを検査するステップと、
前記選択されたプロセッサは前記ローカル・プロセッサであると判断することに応答して、前記選択されたプロセッサに関する前記ローカル・キュー可用性フラグを検査するステップと
を実行することによって前記可用性を判断するように適合される、請求項９に記載のシステム。
【請求項１３】
タスク受け入れプロセッサであって、
前記ローカル・プロセッサによって、前記ローカル・プロセッサに関連付けられた前記ワークキューから実行すべきタスクを受け入れるステップと、
前記タスクを受け入れることに応答して、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記リモート・キュー可用性フラグを更新するステップと、
前記タスクを受け入れること及び前記選択されたワークキューのサイズと独立していることに応答して、前記ローカル・キュー可用性フラグを更新しないステップと
を実行するように適合され前記タスク受け入れプロセッサをさらに備えている、請求項１２に記載のシステム。
【請求項１４】
ローカル・フラグ保持プロセッサであって、
各々の繰り返し実行時に、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記ローカル・キュー可用性フラグを繰り返し更新するステップを実行するように適合された前記ローカル・フラグ保持プロセッサをさらに備えており、
前記ローカル・フラグ保持プロセッサは、前記タスク受け入れプロセッサにより、前記タスクの受け入れとは関係のない時点で前記繰り返し更新するステップを実行する、請求項１２に記載のシステム。
【請求項１５】
前記マルチプロセッサ・アーキテクチャ内の全てのプロセッサに関連付けられた全てのワークキューについての複合キュー・サイズを、第１の時間間隔で繰り返し求めるように適合された複合キュー・サイズ・プロセッサであって、前記複数のワークキューは全て１つのタイプのものである、前記複合キュー・サイズ・プロセッサをさらに備えており、
前記タスク分散プロセッサは、前記第１の間隔とは無関係の第２の間隔で、
前記複合キュー・サイズに基づいて上限比較値を導き出すステップと、
前記選択されたプロセッサに関するワークキューのサイズを前記上部比較値と比較するステップと、
前記ローカル・キュー可用性フラグが前記上限比較値より大きいことを示す前記比較することに応答して、新しいタスクを受け入れるのに前記ローカル・プロセッサに関連付けられた前記ワークキューが利用不能であることを示すように、前記ローカル・キュー可用性フラグを設定するステップと
を実行することによって、前記ローカル・キュー可用性フラグを繰り返し更新するようにさらに適合される、請求項１２に記載のシステム。
【請求項１６】
前記第１の時間間隔及び前記第２の時間間隔の少なくとも一方は、ランダムな時間間隔を含む、請求項１５に記載のシステム。
【請求項１７】
新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのコンピュータ・プログラムであって、コンピュータに、請求項１〜８のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。