【手続補正書】
【提出日】平成26年7月18日(2014.7.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するためのコンピュータによって実行される方法であって、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るステップと、
前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するステップであって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、ステップと、
それぞれのステートメント・ブロックの実行計画を自動的に決定するステップであって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含み、それぞれのステートメント・ブロックの実行計画を決定するステップが、ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む、ステップと、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するステップと
を含む方法。
【請求項２】
前記ステートメント・ブロックのうちの少なくとも１つの前記実行計画を決定するステップが、
前記ステートメント・ブロックを解析して、前記複数のｈｏｐ間の連係（interconnections）を決定するステップと、
前記連係を使用して、行列およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するステップと
を含む、請求項１に記載のコンピュータによって実行される方法。
【請求項３】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するステップをさらに含む、請求項２に記載のコンピュータによって実行される方法。
【請求項４】
前記ＬＯＰＤａｇが、スカラー演算の表現をさらに含む、請求項３に記載のコンピュータによって実行される方法。
【請求項５】
前記ｈｏｐを少なくとも１つのｌｏｐに変換するステップが、
前記ｈｏｐと同等の複数のｌｏｐのグループを決定するステップと、
コストベースの最適化を使用して、前記複数のｌｏｐのグループから、前記ｌｏｐのグループのうちの少なくとも１つの関連コストよりも低い関連コストを有する１つのｌｏｐのグループを選択するステップと
を含む、請求項１に記載のコンピュータによって実行される方法。
【請求項６】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＬＯＰＤａｇをＭａｐＲｅｄｕｃｅジョブの代表的なワークフローに変換するステップをさらに含み、前記ＬＯＰＤａｇを変換するステップが、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップを含む、請求項３に記載のコンピュータによって実行される方法。
【請求項７】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＨＯＰＤａｇを最適化するステップをさらに含み、前記ＨＯＰＤａｇの最適化が、代数的な書換えのうちの少なくとも１つおよび複数の中間行列の物理表現の選択を含む、請求項６に記載のコンピュータによって実行される方法。
【請求項８】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、コストベースの最適化を使用することによって、ＨＯＰＤａｇをＬＯＰＤａｇに変換している間に前記ＬＯＰＤａｇを最適化するステップをさらに含む、請求項７に記載のコンピュータによって実行される方法。
【請求項９】
前記実行計画を実施するステップが、制御プログラムおよびクラスタ上のＭａｐＲｅｄｕｃｅジョブの複数のワークフローによってスカラー演算の実行を管理するステップを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１０】
ＭａｐＲｅｄｕｃｅジョブの前記複数のワークフローの実行が、前記ワークフローが作成されたステートメント・ブロックのタイプを使用して、前記ワークフローを実行の際にスキップすべきか、または実行の際に繰り返すべきかを判定するステップを含む、請求項９に記載のコンピュータによって実行される方法。
【請求項１１】
複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップをさらに含み、そのような判定が、前記ｌｏｐの特性に基づいて複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックするステップを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１２】
前記ＭａｐＲｅｄｕｃｅジョブを作成するステップをさらに含み、前記ＭａｐＲｅｄｕｃｅジョブが、それぞれのフェーズがピギーバッキング方法に従って複数のｌｏｐを実行するようにパラメータ化された、少なくとも３つのフェーズに分割される汎用ＭａｐＲｅｄｕｃｅジョブからインスタンス化される、請求項１１に記載のコンピュータによって実行される方法。
【請求項１３】
前記ＭＬアルゴリズムを実施するためのデータ・ブロック表現のサイズを最適化するステップを含む前記実行計画を最適化するステップをさらに含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１４】
前記データ・ブロック表現のサイズを最適化する前記ステップが、それぞれのデータ・ブロックの局所疎性に依存する、請求項１３に記載のコンピュータによって実行される方法。
【請求項１５】
コンピュータ可読プログラムを記憶するためのコンピュータ使用可能記憶媒体を含むコンピュータ・プログラム製品であって、前記コンピュータ可読プログラムが、コンピュータ上で実行されるとき、前記コンピュータに、ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するための操作であって、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るステップと、
前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するステップであって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、ステップと、
それぞれのステートメント・ブロックの実行計画を自動的に決定するステップであって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含み、それぞれのステートメント・ブロックの実行計画を決定するステップが、ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む、ステップと、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するステップと、
複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップであって、そのような判定が、前記ｌｏｐの特性に基づいて複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックする、前記判定するステップと、
を含む前記操作を実行させる、コンピュータ・プログラム製品。
【請求項１６】
前記コンピュータ可読プログラムが、前記コンピュータに、前記ステートメント・ブロックのうちの少なくとも１つの前記実行計画を決定するための操作であって、
前記ステートメント・ブロックを解析して、前記複数のｈｏｐ間の連係を決定するステップと、
前記連係を使用して、行列およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するステップと
を含む前記操作を実行させる、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記コンピュータ可読プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するステップを含む前記操作を実行させる、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
前記ＬＯＰＤａｇが、スカラー演算の表現をさらに含む、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１９】
前記コンピュータ可読プログラムが、前記コンピュータに、前記ＨＯＰＤａｇを少なくとも１つのＬＯＰＤａｇに変換するための操作であって、前記ＨＯＰＤａｇで実施されるそれぞれのｈｏｐについて、前記ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む前記操作を実行させる、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
前記コンピュータ可読プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ｌｏｐをＭａｐＲｅｄｕｃｅジョブに変換するステップを含む前記操作を実行させ、前記ｌｏｐを変換するステップが、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップを含む、請求項１９に記載のコンピュータ・プログラム製品。
【請求項２１】
前記コンピュータ可読プログラムが、前記コンピュータに、前記複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するための操作であって、ｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックするステップを含む前記操作を実行させる、請求項２０に記載のコンピュータ・プログラム製品。
【請求項２２】
前記コンピュータ可読プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ＨＯＰＤａｇを最適化するステップを含む前記操作を実行させ、前記ＨＯＰＤａｇの最適化が、代数的な書換えのうちの少なくとも１つおよび複数の中間行列の物理表現の選択を含む、請求項１９に記載のコンピュータ・プログラム製品。
【請求項２３】
前記コンピュータ可読プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、ＨＯＰＤａｇをＬＯＰＤａｇに変換している間に前記ＬＯＰＤａｇを最適化するステップを含む前記操作を実行させ、そのような変換が、
前記ｈｏｐと同等の複数のｌｏｐのグループを決定するステップと、
コストベースの最適化を使用して、前記複数のｌｏｐのグループから、前記ｌｏｐのグループのうちの少なくとも１つの関連コストよりも低い関連コストを有する１つのｌｏｐのグループを選択するステップと
を含む、請求項１９に記載のコンピュータ・プログラム製品。
【請求項２４】
ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するためのシステムであって、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るための手段と、
前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するための手段であって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、手段と、
それぞれのステートメント・ブロックの実行計画を自動的に決定するための手段であって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含む、手段と、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するための手段と、
前記ＭＬアルゴリズムを実施するためのデータ・ブロック表現のサイズを最適化する手段を含む前記実行計画を最適化する手段と、
を含むシステム。
【請求項２５】
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、行列、ベクトル、およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するための手段を含み、
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するための手段を含み、
前記ＨＯＰＤａｇを少なくとも１つのＬＯＰＤａｇに変換するための手段が、前記ＨＯＰＤａｇで実施されるそれぞれのｈｏｐについて、前記ｈｏｐを少なくとも１つのｌｏｐに変換するための手段を含み、
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、前記ｌｏｐをＭａｐＲｅｄｕｃｅジョブの複数のワークフローに変換するための手段を含み、前記ｌｏｐを変換する手段が、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックする手段を含む、
請求項２４に記載のシステム。