【手続補正書】
【提出日】平成25年6月24日(2013.6.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
マルチスレッド処理フレームワーク上で実行されるマルチスレッドアプリケーションのパフォーマンスを解析する方法であって、
前記マルチスレッドアプリケーションのパラレル領域のパラレルオーバヘッドが閾値を超えているか判断するステップと、
前記マルチスレッドアプリケーションのパラレル領域のパラレルオーバヘッドが閾値を超えているという判断に応答して、前記パラレル領域のパラレルオーバヘッドの１以上の原因を決定するステップと、
を有する方法。
【請求項２】
前記パラレルオーバヘッドは、アクティブパラレルオーバヘッドと非アクティブパラレルオーバヘッドとを有し、
前記マルチスレッドアプリケーションのパラレル領域のパラレルオーバヘッドが閾値を超えているか判断するステップは、前記マルチスレッドアプリケーションのパラレル領域の前記アクティブパラレルオーバヘッド及び／又は前記非アクティブパラレルオーバヘッドが前記閾値を超えているか判断することを含む、請求項１記載の方法。
【請求項３】
前記パラレル領域のパラレルオーバヘッドの１以上の原因を決定するステップは、設定されたモニタリング期間に基づき前記パラレル領域を実行することを含む、請求項２記載の方法。
【請求項４】
前記パラレル領域の実行は、１以上のワーカスレッドを利用し、
当該方法はさらに、
各スレッドが前記パラレル領域の１以上のタスクの１つを実行することに応答して、前記１以上のワーカスレッドのそれぞれをユーザコード実行状態に割り当てるステップと、
各スレッドがローカルキューにおいてタスクを検索することに応答して、前記１以上のワーカスレッドのそれぞれをローカルキュールックアップ状態に割り当てるステップであって、前記タスクは前記パラレル領域の１以上のタスクの一部である、前記ローカルキュールックアップ状態に割り当てるステップと、
各スレッドが他のキュー又はグローバルキューにおいて他のタスクを検索することに応答して、前記１以上のワーカスレッドのそれぞれをグローバルタスク検索状態に割り当てるステップであって、前記他のタスクは前記パラレル領域の１以上のタスクの一部である、前記グローバルタスク検索状態に割り当てるステップと、
各スレッドがアイドル状態にあることに応答して、前記１以上のワーカスレッドのそれぞれを待機状態に割り当てるステップと、
を有する、請求項３記載の方法。
【請求項５】
前記１以上のワーカスレッドのそれぞれについて、前記ローカルキュー、前記他のキュー及び前記グローバルキューにおける前記タスクの実行の頻度が他の閾値を超えているか判断するステップと、
前記タスクの実行の頻度が前記他の閾値を超えたという判断に応答して、前記パラレル領域のパラレルオーバヘッドの１以上の原因の１つとして、各ワーカスレッドが前記ローカルキューから前記タスクを取得するのにそれのライフタイムの多すぎる時間を費やしていることを報告するステップと、
をさらに有する、請求項４記載の方法。
【請求項６】
前記ローカルキューにおける前記タスクの実行と前記他のキュー及び前記グローバルキューにおける前記タスクの実行とのレシオが他の閾値を超えているか判断するステップと、
前記ローカルキューにおける前記タスクの実行と前記他のキュー及び前記グローバルキューにおける前記タスクの実行とのレシオが他の閾値を超えているという判断に応答して、前記パラレル領域のパラレルオーバヘッドの１以上の原因の１つとして、各ワーカスレッドが前記他のローカルキューにおける前記他のタスクを検索するか、又は前記グローバルキューにおける前記他のタスクを検索するのに多すぎる時間を費やしていることを報告するステップと、
をさらに有する、請求項４又は５記載の方法。
【請求項７】
前記１以上のワーカスレッドのそれぞれについて、前記グローバルタスク検索状態から前記グローバルタスク検索状態及び前記待機状態への状態遷移の頻度が他の閾値を超えているか判断するステップと、
前記１以上のワーカスレッドのそれぞれについて、前記グローバルタスク検索状態から前記グローバルタスク検索状態及び前記待機状態への状態遷移の頻度が他の閾値を超えているという判断と、前記マルチスレッドアプリケーションのパラレル領域の前記非アクティブパラレルオーバヘッドが前記閾値を超えているという判断とに応答して、前記パラレル領域のパラレルオーバヘッドの１以上の原因の１つとして、前記１以上のワーカスレッドの少なくとも１つが自らのタスクを終了したが、前記１以上のワーカスレッドの残りを支援することができないことを報告するステップと、
をさらに有する、請求項４又は５記載の方法。
【請求項８】
前記マルチスレッド処理フレームワークは、Ｏｐｅｎ  Ｍｕｌｔｉ−Ｐｒｏｃｅｓｓｉｎｇ（ＯｐｅｎＭＰ）、Ｉｎｔｅｌ（登録商標）  Ｔｈｒｅａｄｉｎｇ  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋｓ（ＴＢＢ）、Ｉｎｔｅｌ（登録商標）  Ｃｉｌｋ＋＋、Ｉｎｔｅｌ（登録商標）  Ｃ＋＋  ｆｏｒ  Ｔｈｒｏｕｇｈｐｕｔ  Ｃｏｍｐｕｔｉｎｇ（Ｃｔ）、及びＭｉｃｒｏｓｏｆｔ（登録商標）  Ｐａｒａｌｌｅｌ  Ｐａｔｔｅｒｎｓ  Ｌｉｂｒａｒｙ（ＰＰＬ）の１つに少なくとも部分的に準拠する、請求項１記載の方法。
【請求項９】
１以上のプロセッサと、
前記１以上のプロセッサに接続され、前記１以上のプロセッサ上での実行に応答して、装置にマルチスレッドシステムを実行させる１以上のマシーン可読命令を有する１以上のマシーン可読媒体と、
パラレルスレッド処理ライブラリを用いてマルチスレッドアプリケーションを実行するため、前記１以上のプロセッサにより実行されるよう構成されるオペレーティングシステムと、
前記マルチスレッドアプリケーションはサブ最適パラレルアルゴリズムを有すると判断し、スレッドライフサイクル状態マシーンを用いて前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題を決定するため、前記１以上のプロセッサにより実行されるよう構成されるマルチスレッドアプリケーションパフォーマンス解析手段と、
を有する装置。
【請求項１０】
前記マルチスレッドアプリケーションが前記サブ最適パラレルアルゴリズムを有することの判断は、前記サブ最適アルゴリズムのパラレルオーバヘッドが前記マルチスレッドアプリケーションのパフォーマンスゲインと同等又はそれ以上であると判断することを含む、請求項９記載の装置。
【請求項１１】
前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題は、サブ最適な粒度、不十分なパラレルスラックネス及び過剰なタスクのスチールの１以上を有する、請求項９又は１０記載の装置。
【請求項１２】
前記スレッドライフサイクル状態マシーンは、
第１の複数のスレッドを有する実行状態であって、前記第１の複数のスレッドのそれぞれは、前記サブ最適パラレルアルゴリズムの複数のジョブの１つを実行する状態にある、前記実行状態と、
第２の複数のスレッドを有するローカルキュールックアップ状態であって、前記第２の複数のスレッドのそれぞれは、ローカルキューにおいて前記サブ最適パラレルアルゴリズムの複数のジョブの一部であるジョブを検索する状態にある、前記ローカルキュールックアップ状態と、
第３の複数のスレッドを有するグローバルジョブ検索状態であって、前記第３の複数のスレッドのそれぞれは、他のキュー又はグローバルキューにおいて前記サブ最適パラレルアルゴリズムの複数のジョブの一部である他のジョブを検索する状態にある、前記グローバルジョブ検索状態と、
第４の複数のスレッドを有する待機状態であって、前記第４の複数のスレッドのそれぞれは、アイドル状態にある、前記待機状態と、
を有する、請求項９記載の装置。
【請求項１３】
前記スレッドライフサイクル状態マシーンを用いた前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の決定は、
決定された期間に前記サブ最適パラレルアルゴリズムを実行し、
前記ローカルキュールックアップ状態への前記実行状態の遷移の回数と、前記グローバルジョブ検索状態に前記ローカルキュールックアップ状態が遷移し、前記グローバルジョブ検索状態を繰り返した回数との和を決定し、
前記和と前記決定された期間の長さとのレシオが第１閾値を超えていると判断し、
前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムの粒度が詳細すぎると特定する、請求項９記載の装置。
【請求項１４】
前記スレッドライフサイクル状態マシーンを用いた前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の決定は、
前記グローバルジョブ検索状態に前記ローカルキュールックアップ状態が遷移し、前記グローバルジョブ検索状態を繰り返す回数と、前記ローカルキュールックアップ状態への前記実行状態の遷移の回数とのレシオが第２閾値を超えていると判断し、
前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムのリニアスポーニングを特定する、請求項１２記載の装置。
【請求項１５】
前記スレッドライフサイクル状態マシーンを用いた前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の決定は、
前記グローバルジョブ検索状態及び前記待機状態への前記グローバルジョブ検索状態の遷移の回数が第３閾値を超えているか判断し、
前記グローバルジョブ検索状態及び前記待機状態への前記グローバルジョブ検索状態の遷移の回数が第３閾値を超えているという判断に応答して、前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムの過剰な待機を特定し、
前記グローバルジョブ検索状態及び前記待機状態への前記グローバルジョブ検索状態の遷移の回数が第３閾値を超えているという判断と、前記サブ最適パラレルアルゴリズムの非アクティブパラレルオーバヘッドが第４閾値を超えているという判断とに応答して、前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムの不十分なジョブ生成を特定する、請求項１２乃至１４何れか一項記載の装置。
【請求項１６】
前記パラレルスレッド処理ライブラリは、Ｏｐｅｎ  Ｍｕｌｔｉ−Ｐｒｏｃｅｓｓｉｎｇ（ＯｐｅｎＭＰ）、Ｉｎｔｅｌ（登録商標）  Ｔｈｒｅａｄｉｎｇ  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋｓ（ＴＢＢ）、Ｉｎｔｅｌ（登録商標）  Ｃｉｌｋ＋＋、Ｉｎｔｅｌ（登録商標）  Ｃ＋＋  ｆｏｒ  Ｔｈｒｏｕｇｈｐｕｔ  Ｃｏｍｐｕｔｉｎｇ（Ｃｔ）、及びＭｉｃｒｏｓｏｆｔ（登録商標）  Ｐａｒａｌｌｅｌ  Ｐａｔｔｅｒｎｓ  Ｌｉｂｒａｒｙ（ＰＰＬ）の１つに少なくとも部分的に準拠する、請求項９記載の方法。
【請求項１７】
前記マルチスレッドアプリケーションパフォーマンス解析手段は、前記パラレルスレッド処理ライブラリの一部である、請求項９記載の装置。
【請求項１８】
実行されるとプロセッサに、
各スレッドの現在状態に基づき、複数のスレッドのそれぞれを複数の状態の１つに割り当てさせ、
各スレッドの前記複数の状態間の遷移の回数に少なくとも部分的に基づき、マルチスレッドアプリケーションのパラレル領域による１以上の問題を決定させる、
命令を格納したマシーン可読記憶媒体。
【請求項１９】
前記複数の状態は、
各スレッドが前記マルチスレッドアプリケーションのパラレル領域の一部を実行する前記現在状態にあることに応答して、各スレッドが割り当てられる実行状態と、
各スレッドがローカルキューにおいて前記マルチスレッドアプリケーションのパラレル領域の複数のジョブの一部であるジョブを検索する前記現在状態にあることに応答して、各スレッドが割り当てられるローカルキュールックアップ状態と、
各スレッドが他のキュー又はグローバルキューにおいて前記マルチスレッドアプリケーションの前記複数のジョブの一部である他のジョブを検索する前記現在状態にあることに応答して、各スレッドが割り当てられるグローバルジョブ検索状態と、
各スレッドが非アクティブの前記現在状態にあることに応答して、各スレッドが割り当てられる待機状態と、
を有する、請求項１８記載のマシーン可読記憶媒体。
【請求項２０】
前記各スレッドの前記複数の状態間の遷移の回数に少なくとも部分的に基づく、マルチスレッドアプリケーションのパラレル領域による１以上の問題の決定は、
決定された期間に前記マルチスレッドアプリケーションのパラレル領域を実行させ、
前記ローカルキュールックアップ状態への前記実行状態の遷移の回数と、前記グローバルジョブ検索状態へ前記ローカルキュールックアップ状態が遷移し、前記グローバルジョブ検索状態を繰り返す回数との和を決定させ、
前記和と前記決定された期間の長さとのレシオが第１閾値を超えていると判断させ、
前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムの粒度が詳細すぎると特定させる、
ことを有する、請求項１９記載のマシーン可読記憶媒体。
【請求項２１】
前記各スレッドの前記複数の状態間の遷移の回数に少なくとも部分的に基づく、マルチスレッドアプリケーションのパラレル領域による１以上の問題の決定は、
前記グローバルジョブ検索状態に前記ローカルキュールックアップ状態が遷移し、前記グローバルジョブ検索状態を繰り返す回数と、前記ローカルキュールックアップ状態への前記実行状態の遷移の回数とのレシオが第２閾値を超えていると判断させ、
前記サブ最適パラレルアルゴリズムの１以上のパフォーマンス問題の１つとして、前記サブ最適パラレルアルゴリズムのリニアスポーニングを特定させる、
ことを有する、請求項１９記載のマシーン可読記憶媒体。
【請求項２２】
前記各スレッドの前記複数の状態間の遷移の回数に少なくとも部分的に基づく、マルチスレッドアプリケーションのパラレル領域による１以上の問題の決定は、
前記グローバルジョブ検索状態及び前記待機状態への前記グローバルジョブ検索状態の遷移の回数が第３閾値を超えているか判断させ、
前記グローバルジョブ検索状態及び前記待機状態への前記グローバルジョブ検索状態の遷移の回数が第３閾値を超えているという判断に応答して、前記マルチスレッドアプリケーションのパラレル領域の１以上のパフォーマンス問題の１つとして、前記マルチスレッドアプリケーションのパラレル領域の過剰な待機を特定させる、
ことを有する、請求項１９記載のマシーン可読記憶媒体。
【請求項２３】
前記各スレッドの前記複数の状態間の遷移の回数に少なくとも部分的に基づく、マルチスレッドアプリケーションのパラレル領域による１以上の問題の決定は、
前記１以上のワーカスレッドのそれぞれについて前記グローバルタスク検索状態及び前記待機状態への前記グローバルタスク検索状態の遷移の回数が他の閾値を超えているか判断させ、
前記グローバルタスク検索状態及び前記待機状態への前記グローバルタスク検索状態の遷移の回数が前記第３閾値を超えているという判断に応答して、前記マルチスレッドアプリケーションのパラレル領域の１以上のパフォーマンス問題の１つとして、前記マルチスレッドアプリケーションのパラレル領域の過剰な待機を特定させ、
前記グローバルタスク検索状態及び前記待機状態への前記グローバルタスク検索状態の遷移の回数が前記第３閾値を超えていないという判断と、前記マルチスレッドアプリケーションのパラレル領域の非アクティブパラレルオーバヘッドが第５閾値を超えているという判断とに応答して、前記マルチスレッドアプリケーションのパラレル領域の１以上のパフォーマンス問題の１つとして、前記マルチスレッドアプリケーションのパラレル領域の不十分なジョブ生成を特定させる、
ことを有する、請求項１９乃至２２何れか一項記載のマシーン可読記憶媒体。