(57)【特許請求の範囲】
【請求項１】
ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するためのコンピュータによって実行される方法であって、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るステップと、
前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するステップであって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、ステップと、
それぞれのステートメント・ブロックの実行計画を自動的に決定するステップであって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含み、それぞれのステートメント・ブロックの実行計画を決定するステップが、ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む、ステップと、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するステップと
を含む方法。
【請求項２】
前記ステートメント・ブロックのうちの少なくとも１つの前記実行計画を決定するステップが、
前記ステートメント・ブロックを解析して、前記複数のｈｏｐ間の連係（interconnections）を決定するステップと、
前記連係を使用して、行列およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するステップと
を含む、請求項１に記載のコンピュータによって実行される方法。
【請求項３】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するステップをさらに含む、請求項２に記載のコンピュータによって実行される方法。
【請求項４】
前記ＬＯＰＤａｇが、スカラー演算の表現をさらに含む、請求項３に記載のコンピュータによって実行される方法。
【請求項５】
前記ｈｏｐを少なくとも１つのｌｏｐに変換するステップが、
前記ｈｏｐと同等の複数のｌｏｐのグループを決定するステップと、
コストベースの最適化を使用して、前記複数のｌｏｐのグループから、前記ｌｏｐのグループのうちの少なくとも１つの関連コストよりも低い関連コストを有する１つのｌｏｐのグループを選択するステップと
を含む、請求項１に記載のコンピュータによって実行される方法。
【請求項６】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＬＯＰＤａｇをＭａｐＲｅｄｕｃｅジョブの代表的なワークフローに変換するステップをさらに含み、前記ＬＯＰＤａｇを変換するステップが、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップを含む、請求項３に記載のコンピュータによって実行される方法。
【請求項７】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、前記ＨＯＰＤａｇを最適化するステップをさらに含み、前記ＨＯＰＤａｇの最適化が、代数的な書換えのうちの少なくとも１つおよび複数の中間行列の物理表現の選択を含む、請求項６に記載のコンピュータによって実行される方法。
【請求項８】
それぞれのステートメント・ブロックの前記実行計画を決定するステップが、コストベースの最適化を使用することによって、ＨＯＰＤａｇをＬＯＰＤａｇに変換している間に前記ＬＯＰＤａｇを最適化するステップをさらに含む、請求項７に記載のコンピュータによって実行される方法。
【請求項９】
前記実行計画を実施するステップが、制御プログラムおよびクラスタ上のＭａｐＲｅｄｕｃｅジョブの複数のワークフローによってスカラー演算の実行を管理するステップを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１０】
ＭａｐＲｅｄｕｃｅジョブの前記複数のワークフローの実行が、前記ワークフローが作成されたステートメント・ブロックのタイプを使用して、前記ワークフローを実行の際にスキップすべきか、または実行の際に繰り返すべきかを判定するステップを含む、請求項９に記載のコンピュータによって実行される方法。
【請求項１１】
複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを
判定するステップをさらに含み、そのような判定が、前記ｌｏｐの特性に基づいて複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックするステップを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１２】
前記ＭａｐＲｅｄｕｃｅジョブを作成するステップをさらに含み、前記ＭａｐＲｅｄｕｃｅジョブが、それぞれのフェーズがピギーバッキング方法に従って複数のｌｏｐを実行するようにパラメータ化された、少なくとも３つのフェーズに分割される汎用ＭａｐＲｅｄｕｃｅジョブからインスタンス化される、請求項１１に記載のコンピュータによって実行される方法。
【請求項１３】
前記ＭＬアルゴリズムを実施するためのデータ・ブロック表現のサイズを最適化するステップを含む前記実行計画を最適化するステップをさらに含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１４】
前記データ・ブロック表現のサイズを最適化する前記ステップが、それぞれのデータ・ブロックの局所疎性に依存する、請求項１３に記載のコンピュータによって実行される方法。
【請求項１５】
コンピュータ・プログラムであって、コンピュータに、ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するための操作として、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るステップと、
前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するステップであって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、ステップと、
それぞれのステートメント・ブロックの実行計画を自動的に決定するステップであって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含み、それぞれのステートメント・ブロックの実行計画を決定するステップが、ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む、ステップと、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するステップと、
複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップであって、そのような判定が、前記ｌｏｐの特性に基づいて複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックする、前記判定するステップと、
を実行させる、コンピュータ・プログラム。
【請求項１６】
前記コンピュータ・プログラムが、前記コンピュータに、前記ステートメント・ブロックのうちの少なくとも１つの前記実行計画を決定するための操作であって、
前記ステートメント・ブロックを解析して、前記複数のｈｏｐ間の連係を決定するステップと、
前記連係を使用して、行列およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するステップと
を含む前記操作を実行させる、請求項１５に記載のコンピュータ・プログラム。
【請求項１７】
前記コンピュータ・プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するステップを含む前記操作を実行させる、請求項１６に記載のコンピュータ・プログラム。
【請求項１８】
前記ＬＯＰＤａｇが、スカラー演算の表現をさらに含む、請求項１７に記載のコンピュータ・プログラム。
【請求項１９】
前記コンピュータ・プログラムが、前記コンピュータに、前記ＨＯＰＤａｇを少なくとも１つのＬＯＰＤａｇに変換するための操作であって、前記ＨＯＰＤａｇで実施されるそれぞれのｈｏｐについて、前記ｈｏｐを少なくとも１つのｌｏｐに変換するステップを含む前記操作を実行させる、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
前記コンピュータ・プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ｌｏｐをＭａｐＲｅｄｕｃｅジョブに変換するステップを含む前記操作を実行させ、前記ｌｏｐを変換するステップが、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するステップを含む、請求項１９に記載のコンピュータ・プログラム。
【請求項２１】
前記コンピュータ・プログラムが、前記コンピュータに、前記複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブによって表すことができるかどうかを判定するための操作であって、ｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックするステップを含む前記操作を実行させる、請求項２０に記載のコンピュータ・プログラム。
【請求項２２】
前記コンピュータ・プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、前記ＨＯＰＤａｇを最適化するステップを含む前記操作を実行させ、前記ＨＯＰＤａｇの最適化が、代数的な書換えのうちの少なくとも１つおよび複数の中間行列の物理表現の選択を含む、請求項１９に記載のコンピュータ・プログラム。
【請求項２３】
前記コンピュータ・プログラムが、前記コンピュータに、それぞれのステートメント・ブロックの前記実行計画を決定するための操作であって、ＨＯＰＤａｇをＬＯＰＤａｇに変換している間に前記ＬＯＰＤａｇを最適化するステップを含む前記操作を実行させ、そのような変換が、
前記ｈｏｐと同等の複数のｌｏｐのグループを決定するステップと、
コストベースの最適化を使用して、前記複数のｌｏｐのグループから、前記ｌｏｐのグループのうちの少なくとも１つの関連コストよりも低い関連コストを有する１つのｌｏｐのグループを選択するステップと
を含む、請求項１９に記載のコンピュータ・プログラム。
【請求項２４】
ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するためのシステムであって、
前記ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るための手段と、  前記ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するための手段であって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、手段と、
それぞれのステートメント・ブロックの実行計画を自動的に決定するための手段であって、前記実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含む、手段と、
前記複数のステートメント・ブロックの前記シーケンスで前記実行計画を実施するための手段と、
前記ＭＬアルゴリズムを実施するためのデータ・ブロック表現のサイズを最適化する手段を含む前記実行計画を最適化する手段と、
を含むシステム。
【請求項２５】
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、行列、ベクトル、およびスカラーのうちの少なくとも１つにおける前記複数のｈｏｐの無閉路有向グラフ（ＨＯＰＤａｇ）を作成するための手段を含み、
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、前記ＨＯＰＤａｇを複数のｌｏｐを含む少なくとも１つの下位物理実行計画（ＬＯＰＤａｇ）に変換するための手段を含み、
前記ＨＯＰＤａｇを少なくとも１つのＬＯＰＤａｇに変換するための手段が、前記ＨＯＰＤａｇで実施されるそれぞれのｈｏｐについて、前記ｈｏｐを少なくとも１つのｌｏｐに変換するための手段を含み、
それぞれのステートメント・ブロックの前記実行計画を決定するための手段が、前記ｌｏｐをＭａｐＲｅｄｕｃｅジョブの複数のワークフローに変換するための手段を含み、前記ｌｏｐを変換する手段が、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにピギーバックする手段を含む、請求項２４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示の実施形態は、一般に、データ処理システムの分野に関する。例えば、本開示の実施形態は、ＭａｐＲｅｄｕｃｅ環境（例えば、Ａｐａｃｈｅ（Ｒ）  Ｈａｄｏｏｐ！）で機械学習アルゴリズムを処理するためのシステムおよび方法に関する。
【背景技術】
【０００２】
情報を抽出し、解析するために、データセット上で機械学習（ＭＬ）アルゴリズムを使用することがますます多くなっている。トピック・モデリング、レコメンダ・システム、およびインターネット検索クエリなどのアプリケーション用のデータセットの規模が大きくなるにつれて、大規模なデータセット上でＭＬアルゴリズムをスケーラブルに実施する必要がある。ＭＬアルゴリズムの本実施には特殊ハードウェアの手動調整を必要とし、マシンのクラスタ上で個々の学習アルゴリズムを並列化する方法を手動で実施しなければならない。
【０００３】
並列処理は、実行の速度を上げ、処理されるデータの量を増やすために使用される。しかし、分散ネットワークまたは複数のプロセッサを使用することは、１つのジョブに対して、より大きな複数の考えられる実行ストラテジが存在することを意味する。１つの問題は、特に複数のＭＬアルゴリズムを実施するために、複数のなかから１つの優れた実行ストラテジを選択することがプログラマの肩にかかっているということである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
コンピュータにより実行される、ＭａｐＲｅｄｕｃｅ環境で機械学習アルゴリズムを処理するための方法、プログラム及びシステムを提供する。
【課題を解決するための手段】
【０００５】
ＭａｐＲｅｄｕｃｅ環境で機械学習（ＭＬ）アルゴリズムを処理するためのシステムおよび方法が記載される。一実施形態では、方法は、ＭａｐＲｅｄｕｃｅ環境で実行されるＭＬアルゴリズムを受け取るステップを含む。方法は、ＭＬアルゴリズムをシーケンス内の複数のステートメント・ブロックに構文解析するステップであって、それぞれのステートメント・ブロックが複数の基本演算（ｈｏｐ）を含む、ステップをさらに含む。方法は、それぞれのステートメント・ブロックの実行計画を自動的に決定するステップであって、実行計画のうちの少なくとも１つが１以上の下位演算（ｌｏｐ）を含む、ステップも含む。方法は、複数のステートメント・ブロックのシーケンスで実行計画を実施するステップをさらに含む。
【０００６】
この例示の実施形態は、本発明を限定または定義するためではなく、本発明の理解を助ける例を与えるために述べられるものである。例示の実施形態は、「発明を実施するための形態」において説明され、そこで本開示のさらなる説明が与えられる。本開示の様々な実施形態によって与えられる利点は、本明細書を調べることによってさらに理解され得る。
【０００７】
本発明のこれらおよび他の特徴、態様、および利点は、以下の「発明を実施するための形態」を添付の図面を参照しながら読めば、より良く理解される。
【図面の簡単な説明】
【０００８】
【図１】ＭａｐＲｅｄｕｃｅ環境で機械学習アルゴリズムを実施するための例示的なシステムを示す図である。
【図２】ＭａｐＲｅｄｕｃｅ環境で機械学習アルゴリズムを実施する際に図１のシステムによって実行される例示的な方法を示す図である。
【図３】図２に示される方法を実行する図１に示されるシステムによる単純なステートメントＡ＝Ｂ＊（Ｃ／Ｄ）の例示的な処理を示す図である。
【図４】図２に示される方法の場合に構文解析された表現を生成するための例示的な方法を示す図である。
【図５】図２に示される方法を実行する図１に示されるシステムによって作成された基本演算の例示的な無閉路有向グラフ（directed acyclic graph）である。
【図６】Ｃ／Ｄを表すｂｉｎａｒｙ  ｈｏｐの対応するｌｏｐの例を示す図である。
【図７】図２に示される方法を実行する図１に示されるシステムによる、ＭａｐＲｅｄｕｃｅジョブへのｌｏｐのパッケージングの例を示す図である。
【図８】複製ベースの行列積アルゴリズムを示す図である。
【図９】クロス積ベースの行列積アルゴリズムを示す図である。
【図１０】図１に示されるシステムおよび図２に示される方法を実施するための例示的なコンピュータ・アーキテクチャを示す図である。
【発明を実施するための形態】
【０００９】
本開示の実施形態は、一般に、データ処理システムの分野に関する。例えば、本開示の実施形態は、ＭａｐＲｅｄｕｃｅ環境で機械学習アルゴリズムを処理するためのシステムおよび方法に関する。本明細書全体を通して、説明の目的で、本開示の完全な理解を与えるために多数の特定の詳細が記載される。しかし、本開示はこれらの特定の詳細の一部がなくても実施され得ることが当業者には明らかとなろう。他の例では、本開示の基礎をなす原理を不明瞭にするのを避けるために、よく知られている構造およびデバイスはブロック図の形で示される。
【００１０】
ＭａｐＲｅｄｕｃｅは、マシンの大規模なクラスタのための汎用並列プログラミング・パラダイムである。膨大なデータセット上で機械学習（ＭＬ）アルゴリズムを実行する必要性の増大と相まって、本開示は、ＭａｐＲｅｄｕｃｅでＭＬアルゴリズムを実施するための新規の方法およびシステムについて記載する。本開示は、機械学習アルゴリズムが高級言語で表され、ＭａｐＲｅｄｕｃｅ環境で実行されるシステムおよび方法について記載する。高級言語は、教師あり機械学習アルゴリズムおよび教師なし機械学習アルゴリズムの幅広いクラスに対してキー構築ブロックを構成するいくつかの構文を公開している。高級言語で表されるアルゴリズムは、マシンのクラスタ上で実行するＭａｐＲｅｄｕｃｅジョブのセットにコンパイルされ、最適化される。本開示は、ＭａｐＲｅｄｕｃｅフレームワーク（例えば、Ａｐａｃｈｅ（Ｒ）  Ｈａｄｏｏｐ！）でこれらのアルゴリズムを効率的に実行するためのいくつかの最適化ストラテジについても記載する。
【００１１】
以下の説明で記載されているように、ＭＬアルゴリズムを記述するための宣言型の高級言語は、下位実施の詳細およびＭａｐＲｅｄｕｃｅにおけるアルゴリズム実施の性能調整からユーザを解放する。加えて、システムおよび方法は、非常に大規模なデータセットまで拡大する性能を提供する。この性能は、手動で調整した個々のアルゴリズムの実施に匹敵する。
【００１２】
ＭａｐＲｅｄｕｃｅ
操作上、ＭａｐＲｅｄｕｃｅは、３つのフェーズ、すなわち、入力データが分離されて異なるキーと値のペア（key-value pair）になる「Ｍａｐ」フェーズ、異なるマッパからの同じキーがまとめられる「Ｓｈｕｆｆｌｅ」フェーズ、および個々のキーに関連付けられたすべての値が一緒に解析される「Ｒｅｄｕｃｅ」フェーズからなる。通常、ＭａｐフェーズおよびＲｅｄｕｃｅフェーズは公開されるが、Ｓｈｕｆｆｌｅフェーズはプラットフォームの内部で行われる。しかし、Ｓｈｕｆｆｌｅフェーズのコストは本開示に記載される最適化の重要な側面である。
【００１３】
システムＭＬ
図１は、ＭａｐＲｅｄｕｃｅ環境でＭＬアルゴリズムを実施するための（本開示において「システムＭＬ」と呼ばれる）システム１０１の例示的な実施形態を示す。一般に、システムＭＬ１０１は、宣言型機械学習言語（ＤＭＬ：Declarative Machine learning Language）スクリプト１０３を受け入れる言語コンポーネント１０２、言語コンポーネント１０２に結合された上位演算子（ＨＯＰ）コンポーネント１０４、ＨＯＰコンポーネント１０４に結合された下位演算子（ＬＯＰ）コンポーネント１０５、およびＬＯＰコンポーネント１０５に結合されたランタイム・コンポーネント１０６を含む。一実施形態では、ランタイム・コンポーネント１０６は分散ネットワークまたはクラスタ１０７、１０８ａ〜ｎと接続して、スクリプトを実行する。
【００１４】
宣言型機械学習言語
宣言型機械学習言語（ＤＭＬ）は宣言型言語であり、そのシンタックスはプログラミング言語Ｒのシンタックスに酷似している。システムが生成するさらなる最適化を実現するため、ＤＭＬはＲで利用可能なあらゆる柔軟性を提供しない。しかし、柔軟性を失うことは主としてプログラムの利便性を失うことにつながり、ＤＭＬでＭＬアルゴリズムのクラスを表すことにはあまり影響を及ぼさない。ＤＭＬ構文は、ガウス非負値行列因子分解（ＧＮＭＦ：Gaussian Non-Negative Matrix Factorization）アルゴリズム（以下のアルゴリズム１）である例示的なスクリプト１（以下）を使用して説明される。
アルゴリズム１：ＧＮＭＦ
1: V = read(“in/V”);
2: W = read(“in/W”);
3: H = read(“in/H”);
4: max iteration = 20;
5: i = 0;
6: while i < max iteration do
7: H = H * (WT V/WTWH);
8: W = W * (V HT/WHHT);
9: i = i + 1;
10: end while
11: write(W,“out/W”);
12: write(H,“out/H”);
スクリプト１：ＧＮＭＦ
1: V=readMM("in/V", rows=1e8,cols=1e5, nnzs=1e10);
2: W=readMM("in/W", rows=1e8,cols=10);
3: H=readMM("in/H", rows=10,cols=1e5);
4: max iteration=20;
5: i=0;
6: while(i<max iteration) {
7:H=H*(t(W)%*%V)/(t(W)%*%W%*%H);
8:W=W*(V%*%t(H))/(W%*%H%*%t(H));
9: i=i+1;}
10: writeMM(W, "out/W");
11: writeMM(H, "out/H");
【００１５】
ＤＭＬは、３つの主なデータ・タイプ、すなわち、行列、ベクトル、およびスカラーをサポートする。サポートされるスカラー・データ・タイプは、整数型（integer）、浮動小数点型（double）、文字列型（string）および論理型（logical）である。行列またはベクトル内のセルは、整数値、浮動小数点値または文字列値からなり得る。ＤＭＬプログラムはステートメントのシーケンスからなり、デフォルトの計算意味論（computation semantics）は個々のステートメントの順次評価（sequentialevaluation）である。現在、以下の構文がＤＭＬでサポートされている。
・  入力／出力：ＲｅａｄＭＭ（行列積（Matrix Multiplication））ステートメントおよびＷｒｉｔｅＭＭステートメントはそれぞれ、ファイルからベクトルおよび行列を読み取り、ファイルにベクトルおよび行列を書き込むために提供される。任意選択で、Ｒｅａｄステートメントでは、ユーザは、次元数および疎性（非ゼロ・エントリの数すなわちｎｎｚ）などの、行列またはベクトルの追加の特性を与えることができる。
・  制御構造：ＤＭＬでサポートされる制御構造は、ｗｈｉｌｅステートメント、ｆｏｒステートメントおよびｉｆステートメントを含む。スクリプト１におけるステップ６〜９は、例示的なｗｈｉｌｅステートメントを示す。
・  代入：代入ステートメント（assignment statement）は、式およびその式が変数に代入された結果（例えば、スクリプト１におけるステップ７〜９）からなる。代入はスカラー、ベクトルまたは行列に対して行うことができる。
【００１６】
ＤＭＬは、以下の主なタイプの演算子をサポートする。
・  算術：算術演算子は、乗算、除算、加算、および減算を含む。当然、算術演算子はベクトルおよび行列にまで及び、意味論は演算子がそれに対応するセルに適用されることを表す。
・  関係／ブール：関係／ブール演算子は、未満（less than）、より大きい（greater than）、および等しい（equal to）を含む。
・  内部関数：内部関数は、集約関数（例えば、ｓｕｍ、ｒｏｗＳｕｍ）、ｓｉｎおよびｌｏｇなどの数学関数、および線形代数関数（例えば、ｔｒａｎｓｐｏｓｅ  ｔ、ｄｉａｇ）を含む。
また、ＤＭＬにより、ユーザはシンタックス「関数（ａｒｇｌｉｓｔ）本体」を使用して独自の関数を定義することができる。ａｒｇｌｉｓｔは、入力および出力の仮引数のセットを含む。本体は有効なＤＭＬステートメントのグループである。
【００１７】
ＤＭＬをＲプログラミング言語と比較すると、ＤＭＬはオブジェクト指向機能などの高度なプログラミング機能、高度なデータ・タイプ（例えば、リストおよび配列）、および高度な関数のサポート（例えば、呼び出し元関数内およびさらにはコールスタック内の変数にアクセスする）をサポートしていない。加えて、ＤＭＬは、Ｒがサポートしている広範なグラフ手順（extensive graphical procedures）をサポートしていない。
【００１８】
システムＭＬのための例示的な方法
図２は、ＭａｐＲｅｄｕｃｅ環境でＭＬアルゴリズムを実施する際にシステムＭＬ１０１によって実行される方法２００の例示的な実施形態を示す。加えて、図３は、例示的な方法２００を説明する際に例示の目的で使用される、単純なステートメントＡ＝Ｂ＊（Ｃ／Ｄ）の例示的な処理３００を示す。２０１で開始すると、システムＭＬ１０１の言語コンポーネント１０２は、実施されるＭＬアルゴリズム用のＤＭＬスクリプト１０３を受け取る。２０２に進むと、言語コンポーネント１０２は、アルゴリズムをステートメント・ブロックと呼ばれるより小さい単位の構文解析された表現に分ける。
【００１９】
図４は、構文解析された表現を生成するための方法４００の例示的な実施形態を示す。４０１で開始すると、データ・タイプはＤＭＬスクリプト内のそれぞれの変数に代入される。例えば、スクリプト１から、ＲｅａｄＭＭステートメント（ステップ１〜３）を使用してＶ、ＷおよびＨを行列として入力(type)する一方、Ａｓｓｉｇｎｍｅｎｔステートメント（ステップ４〜５）を使用してｍａｘ  ｉｔｅｒａｔｉｏｎ（最大反復回数）およびｉをスカラー変数として特定する。
【００２０】
４０２に進むと、プログラムはステートメント・ブロックに分割される。スクリプト１による例を続けると、Ｃｏｎｓｅｃｕｔｉｖｅ  Ａｓｓｉｇｎｍｅｎｔステートメント、ＲｅａｄＭＭステートメントおよびＷｒｉｔｅＭＭステートメントは、これらのステートメントに関与する演算をまとめて最適化することができるので、単一のステートメント・ブロックに結合される。制御構造（例えば、ｗｈｉｌｅループおよび関数）は、ステートメント・ブロックが越えることができない自然境界をもたらす。スクリプト１は３つのステートメント・ブロック（以下）に分かれる。
ステートメント・ブロック１
1: V=readMM("in/V", rows=1e8,cols=1e5, nnzs=1e10);
2: W=readMM("in/W", rows=1e8,cols=10);
3: H=readMM("in/H", rows=10,cols=1e5);
4: max iteration=20;
5: i=0;
ステートメント・ブロック２
6: while (i<max iteration) do
7: H=H*(t(W)%*%V)/(t(W)%*%W%*%H);
8: W=W*(V%*%t(H))/(W%*%H%*%t(H));
9: i=i+1;
ステートメント・ブロック３
10: writeMM(W, "out/W");
11: writeMM(H, "out/H");
【００２１】
一実施形態では、異なるタイプのステートメント・ブロックが存在する。異なるタイプのステートメント・ブロックとしては、（１）単純なステートメント・ブロック（例えば、上記のステートメント・ブロック１などの、実行中に１回実行される基本スクリプトを含む）、（２）繰り返すステートメント・ブロック（スクリプトが２回以上実行され得るステートメント・ブロック、例えば、上記のステートメント・ブロック２などの、ｆｏｒ、ｗｈｉｌｅ、ｄｏ−ｗｈｉｌｅなどを含むコード内のループ）、および（３）スキップ・ステートメント・ブロック（スクリプトが実行されないことがあるステートメント・ブロック、例えば、ｉｆなどの条件付きステートメント）を挙げることができる。ステートメント・ブロックに対して関連するｌｏｐを実行するとき、ステートメント・ブロックのタイプを使用して、どのように下位演算を実行するか、また、下位演算を実行するかどうかを決定することができる（例えば、実行するためのｉｆ条件を満たさないスキップ・ステートメント・ブロックのｌｏｐをスキップする）。
【００２２】
４０３に進むと、システムＭＬ１０１は、ステートメント・ブロック間でどの変数を渡す必要があるかを判定する。例えば、ステップ７で使用される変数Ｗは、（ループの1回目の反復に対する）ステップ２および２回目の反復以降に対するステップ８の出力を指す。ステートメント・ブロック間でどの変数を渡す必要があるかを判定する際、スクリプトにおける変数のそれぞれの使用は、異なる評価パス間でのその変数に関する直前の（１つまたは複数の）書込みと結び付けられる。
【００２３】
図２に戻って参照し、２０３に進むと、ＨＯＰコンポーネント１０４は、複数のステートメント・ブロックの上位実行計画を決定する。ＨＯＰコンポーネント１０４は、ステートメント・ブロックの構文解析された表現を入力として受け取り、行列、ベクトル、およびスカラーにおける基本演算（ｈｏｐ）の無閉路有向グラフ（ＨＯＰＤａｇ）を生成する。以下はシステムＭＬ１０１で利用可能なｈｏｐ（およびその意味論）である。
・  Ｂｉｎａｒｙ（例えば、ｂ（／））：ｂｉｎａｒｙ  ｈｏｐは２つの入力（それぞれの入力は行列、ベクトル、またはスカラーである）を取り、以下の演算、すなわち、＊、＋、−、／、ｍｉｎ、ｍａｘなどのうちの１つを実行する。
・  Ｕｎａｒｙ（例えば、ｕ（＋））：ｕｎａｒｙ  ｈｏｐは入力として２つのオペランド、すなわち、（１）行列、ベクトルまたはスカラー、および（２）スカラー定数を取る。次いで、ｕｎａｒｙ  ｈｏｐは以下の演算、すなわち、＊、＋、−、／のうちの１つを実行する。
・  ＡｇｇＵｎａｒｙ（例えば、ａ（＋））：ＡｇｇＵｎａｒｙ  ｈｏｐは行列またはベクトル内のセルのセットを集約する。例えば、ｃｏｌＳｕｍは行列内のすべての列の合計を計算し、その合計のベクトルを返す。
・  ＡｇｇＢｉｎａｒｙ（例えば、ａ（＋＊））：ＡｇｇＢｉｎａｒｙ  ｈｏｐは２つの入力を取り、それぞれの入力は行列またはベクトルである。次いで、ＡｇｇＢｉｎａｒｙ  ｈｏｐはＢｉｎａｒｙ演算を実行し、その後に集約演算が続く（例えば、＋、Ｍｉｎ、Ｍａｘなど）。
・  Ｒｅｏｒｇ（例えば、ｒ（Ｔ））：ｒｅｏｒｇ  ｈｏｐは、行列の転置（transpose）など、行列内のすべてのセルのインデックスを変更する。
・  Ｄａｔａ：ｄａｔａ  ｈｏｐは行列、ベクトルまたはスカラーを読み取るか、行列、ベクトルまたはスカラーを書き込む。ｄａｔａ  ｈｏｐは、スクリプトの存続期間に関して一時的なものまたは永続的なものとすることができる。
【００２４】
ＨＯＰＤａｇを作成する際、１つのステートメント・ブロックは１つのＨＯＰＤａｇで表される。図５は、スクリプト１のステートメント・ブロック２におけるＷｈｉｌｅループの本体に対して上記で導入されたｈｏｐを使用するＨＯＰＤａｇを示す。一実施形態では、ステートメント・ブロック内の複数のステートメントを単一のＨＯＰＤａｇに結合することができる。例えば、Ｒｅａｄ  Ｗ  ｄａｔａ  ｈｏｐはｒ  Ｔ  ｒｅｏｒｇ  ｈｏｐに入れられ、ｒ  Ｔ  ｒｅｏｒｇ  ｈｏｐはＲｅａｄ  Ｗ  ｄａｔａ  ｈｏｐとともにａ（＋＊）ＡｇｇＢｉｎａｒｙ  ｈｏｐに入れられて、ステートメント・ブロックのｔ（Ｗ）％＊％Ｗ部分を表す。プログラムが構文解析され、解析されると、ｈｏｐはインスタンス化され、結び付けられて、プログラム内のステートメント・ブロックに対するＨＯＰＤａｇを構築する。図は結び付けられているＨＯＰＤａｇを示しているが、ＨＯＰＤａｇを結び付ける必要はないことに留意されたい。
【００２５】
グレー表示されたＲｅａｄ  ｄａｔａ  ｈｏｐは、行列Ｗ、Ｈ、およびＶならびに反復の開始時におけるスカラーｉのライブイン（live-in）変数を表す。グレー表示されたＷｒｉｔｅ  ｄａｔａ  ｈｏｐは、次の反復に渡す必要がある、反復の終了時におけるライブアウト（live-out）変数を表す。これらの（一時的なものである）ｄａｔａ  ｈｏｐは、１つのステートメント・ブロックのＨＯＰＤａｇの一時的なＷｒｉｔｅ  ｄａｔａ  ｈｏｐ（シンク）を次のステートメント・ブロックのＨＯＰＤａｇの一時的なＲｅａｄ  ｄａｔａ  ｈｏｐ（ソース）またはｗｈｉｌｅループの次の反復にマップすることによって、異なるステートメント・ブロックのＨＯＰＤａｇを互いに暗黙的に結び付ける。
【００２６】
図２に戻って参照し、２０５に進むと、ＬＯＰコンポーネント１０５は、ＨＯＰＤａｇを下位物理実行グラフ（ＬＯＰＤａｇ）に変換する。下位演算子（ｌｏｐ）は、ＭａｐＲｅｄｕｃｅ環境における基本演算を表す。それぞれのｌｏｐは、入力としてキーと値のペアの１つまたは複数のセットを取り、出力として１つまたは複数のキーと値のペアを生成する。以下はシステムＭＬ１０１でサポートされるｌｏｐである。
・  ｂｉｎａｒｙ：ｂｉｎａｒｙ  ｌｏｐは、それぞれの入力がキーと値のペアのセットである２つの入力を伴う計算を実行する。
・  ｕｎａｒｙ：ｕｎａｒｙ  ｌｏｐは、一方の入力がキーと値のペアのセットであり、他方の入力がスカラー値である計算を実行する。
・  ｇｒｏｕｐ：ｇｒｏｕｐ  ｌｏｐは、同じキーを用いてすべてのキーと値のペアをグループ化する。
・  ａｇｇｒｅｇａｔｅ：ａｇｇｒｅｇａｔｅ  ｌｏｐは、同じキーに関連付けられた値のセットにおいて集約関数を適用する。
・  ｔｒａｎｓｆｏｒｍ：ｔｒａｎｓｆｏｒｍ  ｌｏｐは、それぞれの入力キーで変換関数（例えば、ｔｒａｎｓｐｏｓｅ）を適用する。
・  ｄａｔａ：ｄａｔａ  ｌｏｐは、入力データ・ソースまたは出力データ・シンクを表す。
・  行列積をサポートするｌｏｐ：
○  ｍｍｃｊ：ｍｍｃｊ  ｌｏｐは、クロス積ベースの行列積（ＣＰＭＭ：crossproduct based matrix multiplication）におけるクロス積計算に対応する。
○  ｍｍｒｊ：ｍｍｒｊ  ｌｏｐは、複製ベースの行列積（ＲＭＭ：replicationbased matrix multiplication）における計算に対応する。
【００２７】
ＬＯＰＤａｇを作成する一実施形態では、ＨＯＰＤａｇはボトムアップ方式で処理され、それぞれのｈｏｐが１つまたは複数のｌｏｐに変換される。図６は、（図３に示される、アルゴリズム１からの）ｂｉｎａｒｙ  ｈｏｐ  Ｃ／Ｄの対応するｌｏｐ６００の例を示す。下部で、２つのｄａｔａ  ｌｏｐがそれぞれ、入力行列に対するキーと値のペアの１つのセットを返す。概念上、個々の行列内のそれぞれのセルに対する１つのエントリが返される。しかし、通常、ｄａｔａ  ｌｏｐはそれぞれのキーに対する複数のセルを返す（返されるセルの数は適切なブロッキング・ストラテジによって決定される）。次いで、ｇｒｏｕｐ  ｌｏｐは、２つの入力に対する複数のエントリをグループ化する。次いで、その結果は、２つの入力行列からの対応するセル値の除算を実行するために、ｂｉｎａｒｙ  ｌｏｐに渡される。
【００２８】
一実施形態では、コストベースの最適化をＬＯＰＤａｇの作成に使用することができる。ＬＯＰＤａｇを作成する際、ｈｏｐを１つまたは複数のｌｏｐに変換するための複数の選択肢が存在し得る。したがって、関与する行列の様々なデータ特性を考慮するコストベースの最適化を使用して、ｈｏｐに対して選択されたｌｏｐのグループに関する変換コストを下げることができる。コストベースの最適化の一例として、後述するような、行列積を実行する複数の方法から選択することが挙げられる。
【００２９】
図２に戻り、２０５に進むと、ＬＯＰコンポーネント１０５はＬＯＰＤａｇを少なくとも１つのＭａｐＲｅｄｕｃｅジョブにコンパイルする。それぞれのｌｏｐを別個のＭａｐＲｅｄｕｃｅジョブに変換することは、入力データの複数のスキャンおよび中間結果をもたらす。したがって、複数のｌｏｐが単一のＭａｐＲｅｄｕｃｅジョブにパッケージされる場合、通常、結果として生じるスキャンの減少は効率の改善をもたらす。複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにパッケージすることを支援する、ｌｏｐの複数の特性が存在する。例えば、２つのそのような特性は以下の通りである。
・  ロケーション（location）、つまり、ｌｏｐをＭａｐもしくはＲｅｄｕｃｅのいずれかまたはその両方で実行することができるか。
・  キー特性（key characteristics）、つまり、入力キーがグループ化される場合、出力キーがグループ化されて生成されるか、また、ｌｏｐが新しい出力キーを生成するかどうか。
【００３０】
一実施形態では、欲張りピギーバッキング発見的アルゴリズム（greedypiggybacking heuristic algorithm）（以下、アルゴリズム２とする）を使用して、複数のｌｏｐを解析し、複数のｌｏｐを１つのＭａｐＲｅｄｕｃｅジョブにグループ化する。
アルゴリズム２：ピギーバッキング  −  一緒に評価することができるｌｏｐを単一のＭａｐＲｅｄｕｃｅジョブにパッキングする  
入力: LOP-Dag
出力: MapReduceジョブ(MRJobs)のワークフロー
[NMap, NMapOrRed, NMapAndRed, NRed] =TopologicalSort(LOP-Dag);
while(LOP-Dag内のノードが代入されたままである) do
Job ← 新しいMapReduceジョブを作成する;
addNodesByLocation(NMap ∪ NMapOrRed, Map, Job);
addNodesByLocation(NMapAndRed, MapAndReduce, Job);
addNodesByLocation(NMapOrRed ∪ NMapAndRed ∪ NRed, Reduce, Job);
JobをMRJobsに追加する;
end while
return MRJobs
{特定の実行ロケーションに代入する準備ができているノードを追加する方法}
Method: addNodesByLocation ( S, loc, Job )
while(true) do
Z ← Φ
while (Sが空ではない) do
n ← S.next()
if (nがまだ代入されておらず、nのすべての子孫が代入されている) then
if (locがMapである) then
nをZに追加する
else if (locがMapAndReduceである) then
nがZおよびロケーションがMapAndReduceであるJobにいかなる子孫lopも有さない場合、nをZに追加する
else if (locがReduceである) then
if (nがgroup lopである) then
nがZまたはJobに子孫group lopを有する場合のみ、nをZに追加し、これらの2つのgroup lop間のlopはいずれもキーを変更しない
else
nがgroup lopでない場合、nをZに追加する
end if
end if
end if
end while
break Zが空である場合
locに基づいてZをJob.Map、Job.MapAndReduceまたはJob.Reduceに追加する
end while
【００３１】
スクリプト１の例を続けると、図７は、ステップ７についてのｌｏｐをＭａｐＲｅｄｕｃｅジョブにパッケージする例７００を示す。７０１（７００の左側の部分）は、ＨＯＰＤａｇ５００（図５）の「Ｈ  Ａｓｓｉｇｎｍｅｎｔ」とラベル付けされた部分に対して生成されたＬＯＰＤａｇを示す。７０２（７００の右側の部分）は、ＬＯＰＤａｇ７０１の対応するＭａｐＲｅｄｕｃｅジョブを示す。
【００３２】
図２に戻り、２０６に進むと、ランタイム・コンポーネント１０６はランタイム中の（１つまたは複数の）ＭａｐＲｅｄｕｃｅジョブの実行を最適化する。一実施形態では、システムＭＬ１０１のランタイム・コンポーネント１０６において３つの主な考慮事項、すなわち、（１）行列およびベクトルのキーと値の表現、（２）ＭａｐＲｅｄｕｃｅにおいて個々のＬＯＰＤａｇを実行するＭＲランタイム、および（３）実行を指揮する制御モジュールが存在する。
【００３３】
行列およびベクトルのキーと値の表現に関して、システムＭＬ１０１は、行列およびベクトルをブロックに分割（ブロッキングと呼ばれる）し、ブロック内の局所疎性（local sparsity）を利用して、行列およびベクトルを表すキーと値のペアの数を最適化する。ブロックは、指定されたブロックサイズを使用する、より小さい矩形サブ行列である。それぞれのブロックはキーと値のペアで表される。キーはブロックＩＤを示す。値はブロック内のセル値のすべてを保持する。局所疎性は個々のブロックの疎性を指す。ブロック内の値の配置は、ブロック内の疎性（すなわち、ブロック内の非ゼロ値の部分）に基づいて決定される。
【００３４】
一実施形態では、動的なブロックレベル演算はブロックの局所疎性に基づく。したがって、局所疎性情報を使用して、ブロック毎のランタイム時における適切な実行を決定する。一実施形態では、個々のブロックが密または疎であり得るということを考慮するための別個のアルゴリズムが各ｌｏｐ内にある。
【００３５】
例えば、行列積が２つの個々のブロックで実行される場合、ｌｏｐで選択される実際の乗算アルゴリズムは、この２つの入力ブロックの局所疎性に基づいて決定される。両方のブロックが密である場合、ランタイムは両方のブロックですべてのセルを循環させるアルゴリズムを選択する。しかし、ブロックの一方が疎である場合、ランタイムは疎のブロックで非ゼロのセルのみを循環させるアルゴリズムを選択し、非ゼロのセルは密なブロック内の対応するセルにおける値で乗算される。
【００３６】
ＭａｐＲｅｄｕｃｅにおいて個々のＬＯＰＤａｇを実行するＭＲランタイムに関して、汎用ＭａｐＲｅｄｕｃｅジョブ（Ｇ−ＭＲ）はシステムＭＬ１０１における主な実行エンジンである。Ｇ−ＭＲは、１つまたは複数のｌｏｐを用いて、ピギーバッキング・アルゴリズム（上記のアルゴリズム２）によってインスタンス化される。Ｇ−ＭＲの例示的なインスタンス化を示すと、図７の７０２で１とマークされたＭａｐＲｅｄｕｃｅジョブは、３つのｌｏｐ、すなわち、ｄａｔａ  Ｗ、ｔｒａｎｓｆｏｒｍ、およびｍｍｃｊを含む。ＭａｐＲｅｄｕｃｅジョブをインスタンス化するために、Ｇ−ＭＲは以下のようにパラメータ化される。
・  ＭａｐＲｅｄｕｃｅジョブのＭａｐフェーズは、ＬＯＰコンポーネント１０５によって指示された通りに、ｄａｔａ、ｔｒａｎｓｆｏｒｍ、およびｍｍｃｊのｍａｐ部分を順に実行する。
・  ＭａｐＲｅｄｕｃｅジョブのＲｅｄｕｃｅフェーズは、ｍｍｃｊのｒｅｄｕｃｅ部分を実行する。
【００３７】
ランタイム・コンポーネント１０６の制御モジュールは、ＤＭＬスクリプトのすべてのＭａｐＲｅｄｕｃｅジョブの実行を指揮する。一実施形態では、制御モジュールは以下の操作、すなわち、（ｉ）命令スケジューリングおよび（ｉｉ）命令実行を実行する。制御モジュールで実行されるそのような操作としては、スクリプトにおけるスカラー計算（例えば、スカラー算術演算および述部評価）およびＤＭＬスクリプトの実行時のメタデータ操作（例えば、中間結果の削除）が挙げられる。
【００３８】
システムＭＬ１０１は、分散ネットワーク１０７上でアプリケーションを実行するために結果として生じるジョブをフレームワークに送ることによって、結果として生じるＭａｐＲｅｄｕｃｅジョブを実行することができる。フレームワークの一例は、分散ノード１０８ａ〜ｎでジョブを処理するためのＡｐａｃｈｅ（Ｒ）  Ｈａｄｏｏｐ！である。
【００３９】
行列積
システムＭＬ１０１は、少なくとも２つの行列積アルゴリズム、ＲＭＭおよびＣＰＭＭをサポートする。ＲＭＭおよびＣＰＭＭを示すために、ＡおよびＢを、ＡにＭｂ×ＫｂブロックおよびＢにＫｂ×Ｎｂブロックを有するブロック化された行列とする。ブロックレベルでの行列積計算は、
【数１】
0005705338.tif 000002
に対応し、ここでインデックスはブロックＩＤを示す。
【００４０】
図８は、実行するのにＭａｐＲｅｄｕｃｅジョブを１つだけ必要とするＲＭＭアルゴリズム８００を示す。ＲＭＭを含む実行計画のＬＯＰＤａｇは、単一のｍｍｒｊ  ｌｏｐ（Ｇ−ＭＲで実施される）を含む。ＲＭＭアルゴリズム８００では、リデューサはＣのそれぞれの結果ブロックを計算する必要があるＡおよびＢのすべてのブロックにアクセスしなければならない。それぞれのブロックＡはいくつかの結果ブロックの計算に寄与するので、マッパはいくつかの結果ブロックを計算するためのＡのコピーの数をそれに対応するリデューサに送る。同じことがそれぞれのブロックＢについても実行され、これでリデューサはＣを計算するためのすべての必要なブロックを有することになる。
【００４１】
図９は、実行するのに２つのＭａｐＲｅｄｕｃｅジョブを必要とするＣＰＭＭアルゴリズム９００を示す。ＣＰＭＭは、３つのｌｏｐ、すなわち、ｍｍｃｊ、ｇｒｏｕｐ、およびａｇｇｒｅｇａｔｅのシーケンスとしてＬＯＰＤａｇで表される。図７に戻って参照すると、例７００はＷＴＷの計算に関するＣＰＭＭ評価を示す。第１のＭａｐＲｅｄｕｃｅジョブのマッパは、２つの入力行列ＡおよびＢを読み取り、共通キーｋによってＡおよびＢの入力ブロックをグループ化する。したがって、リデューサはクロス積を実行して、Ｃ、（
【数２】
0005705338.tif 000003
）を計算する。第２のＭａｐＲｅｄｕｃｅジョブでは、マッパは前のＭａｐＲｅｄｕｃｅジョブから結果を読み取り、すべての
【数３】
0005705338.tif 000004
をキー（ｉ，ｊ）によってグループ化する。Ｒｅｄｕｃｅフェーズでは、ａｇｇｒｅｇａｔｅ  ｌｏｐが
【数４】
0005705338.tif 000005
を計算する。
【００４２】
ＣＰＭＭの場合、システムＭＬ１０１はｍｍｃｊの最適化された実装を含むことができる。一実施形態では、最適化された実装は、リデューサにおいて部分的な集約を可能にするローカル・アグリゲータ（local aggregator）である。第１のＭａｐＲｅｄｕｃｅ出力は、１≦ｋ≦Ｋｂの場合、
【数５】
0005705338.tif 000006
である。Ｋｂが利用可能なリデューサの数ｒより大きいとき、それぞれのリデューサは複数のグループを処理することができる。例えば、リデューサはｋ＝ｋ’およびｋ＝ｋ’’でクロス積を適用することができ、次いで、その同じリデューサが
【数６】
0005705338.tif 000007
および
【数７】
0005705338.tif 000008
の両方を計算する。ＣＰＭＭについて先に記載したように、第１のＭａｐＲｅｄｕｃｅジョブからの出力は
【数８】
0005705338.tif 000009
として第２のＭａｐＲｅｄｕｃｅジョブに集約される。したがって、
【数９】
0005705338.tif 000010
および
【数１０】
0005705338.tif 000011
を別々に出力する代わりに、ローカル・アグリゲータはリデューサ内で部分的に集約することができる。
【００４３】
一実施形態では、部分的な集約が大きすぎてメモリに収まらなくなるのを防ぐために、ディスクベースのローカル・アグリゲータを実装することができる。ディスクベースのローカル・アグリゲータは、メモリ内のバッファ・プールを使用して、ローカル集約を実行するように構成される。クロス積の結果がディスクにあふれる場合、その結果をソートして、その後のグループについての部分的な集約が効率的に実行されることを保証することができる。
【００４４】
行列積に関して、システムＭＬ１０１はＣＰＭＭおよびＲＭＭから選択する。一実施形態では、システムＭＬ１０１は、異なるアルゴリズムを使用するためのコスト・モデルを比較することによって、選択を最適化する。ＲＭＭの場合、マッパは、ＡおよびＢのそれぞれのブロックについて計算されるＣのブロックの集約数に等しい回数だけ、ＡおよびＢのそれぞれのブロックを複製する（Ａについては数ＮｂおよびＢについては数Ｍｂとして記録される）。結果として、Ｎｂ｜Ａ｜＋Ｍｂ｜Ｂ｜データがＭａｐＲｅｄｕｃｅジョブでシャッフルされる。したがって、ＲＭＭのコスト・モデルは、コスト（ＲＭＭ）＝シャッフル（Ｎｂ｜Ａ｜＋Ｍｂ｜Ｂ｜）＋ＩＯｄｆｓ（｜Ａ｜＋｜Ｂ｜＋｜Ｃ｜）である。
【００４５】
ＣＰＭＭの場合、第１のＭａｐＲｅｄｕｃｅジョブでは、マッパはＡおよびＢのブロックを読み取り、これらのブロックをリデューサに送る。したがって、シャッフルされるデータの量は｜Ａ｜＋｜Ｂ｜である。先に記載したように、リデューサはそれぞれのｋについてクロス積を実行し、ローカル・アグリゲータを適用して、リデューサ内のｋの異なる値における結果を部分的に集約する。したがって、それぞれのリデューサによって生成される結果セットのサイズは｜Ｃ｜によって制限される。したがって、ジョブにｒ個のリデューサがあるとき、ＤＦＳに書き込まれるデータの量はｒ｜Ｃ｜によって制限される。第２のＭａｐＲｅｄｕｃｅジョブでは、第１のＭａｐＲｅｄｕｃｅジョブからのデータが読み取られ、シャッフルされ、リデューサに入れられて、最終結果を生成する。したがって、ＣＰＭＭのコストは以下のコスト・モデル、すなわち、コスト（ＣＰＭＭ）≦シャッフル（｜Ａ｜＋｜Ｂ｜＋ｒ｜Ｃ｜）＋ＩＯｄｆｓ（｜Ａ｜＋｜Ｂ｜＋｜Ｃ｜＋２ｒ｜Ｃ｜）によって制限される。
【００４６】
したがって、一実施形態では、システムＭＬ１０１はコスト（ＲＭＭ）をコスト（ＣＰＭＭ）と比較して、特定の行列積のための適切なアルゴリズムを決定する。一例では、ＡおよびＢの両方が非常に大きい場合、通常、ＣＰＭＭは（ＲＭＭのシャッフル・オーバーヘッドが大きいので）ＲＭＭよりもうまく機能する。別の例では、１つの行列が１つのブロックに収まるほど十分に小さい場合、オーバーヘッドが十分に低いので、通常、ＲＭＭはＣＰＭＭよりもうまく機能する。データ・シャッフルおよびＩＯｄｆｓ操作が同じサイズであるとき、データ・シャッフルはネットワーク・オーバーヘッドおよびローカル・ファイル・システムＩＯおよび外部ソートを必要とするので、より高価な操作であることに留意されたい。
【００４７】
システムおよび方法の実施のための例示的なコンピュータ・アーキテクチャ
図１０は、本開示に記載されたシステムおよび方法を実施するための例示的なコンピュータ・アーキテクチャを示す。図１０の例示的なコンピューティング・システムは、１）１つまたは複数のプロセッサ１００１、２）メモリ制御ハブ（ＭＣＨ：memory control hub）１００２、３）システム・メモリ１００３（ＤＤＲ  ＲＡＭ、ＥＤＯ  ＲＡＭなどの異なるタイプのものが存在する）、４）キャッシュ１００４、５）Ｉ／Ｏ制御ハブ（ＩＣＨ：I/O control hub）１００５、６）グラフィックス・プロセッサ１００６、７）ディスプレイ／スクリーン１００７（ブラウン管（ＣＲＴ：Cathode Ray Tube）、薄膜トランジスタ（ＴＦＴ：Thin FilmTransistor）、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、ＤＰＬなどの異なるタイプのものが存在する）、または８）１つまたは複数のＩ／Ｏデバイス１００８、あるいはこれらすべてを含む。
【００４８】
１つまたは複数のプロセッサ１００１は、コンピューティング・システムが実施するどのようなソフトウェア・ルーチンをも実行するために、命令を実行する。命令は、データ上で実行されるある種の動作を必要とすることが多い。データおよび命令の両方がシステム・メモリ１００３およびキャッシュ１００４に記憶される。通常、キャッシュ１００４はシステム・メモリ１００３よりも短い待ち時間を有するように設計される。例えば、キャッシュ１００４は、（１つまたは複数の）プロセッサと同じ（１つまたは複数の）シリコン・チップ上に組み込まれる、またはより高速なＳＲＡＭセルで構成される、あるいはその両方が行われることがあるが、システム・メモリ１００３は、より低速なＤＲＡＭセルで構成されることがある。より頻繁に使用される命令およびデータをシステム・メモリ１００３ではなくキャッシュ１００４に記憶する傾向があることによって、コンピューティング・システムの全体的な性能効率が改善する。
【００４９】
システム・メモリ１００３は、意図的に、コンピューティング・システム内の他のコンポーネントが利用できるようになっている。例えば、様々なインターフェースからコンピューティング・システム（例えば、キーボードおよびマウス、プリンタ・ポート、ＬＡＮポート、モデム・ポートなど）に受け取られた、またはコンピューティング・システムの内部記憶素子（例えば、ハード・ディスク・ドライブ）から取り出されたデータは、ソフトウェア・プログラムの実施において１つまたは複数のプロセッサ１００１によって操作される前に、システム・メモリ１００３内で一時的にキューに入れられることが多い。同様に、ソフトウェア・プログラムが決定するデータは、コンピューティング・システム・インターフェースのうちの１つを介してコンピューティング・システムから外部のエンティティに送られるか、内部記憶素子に記憶されるべきであり、送信または記憶される前に、システム・メモリ１００３内で一時的にキューに入れられることが多い。
【００５０】
ＩＣＨ１００５は、そのようなデータがシステム・メモリ１００３とそれに対応する適切なコンピューティング・システム・インターフェース（および、コンピューティング・システムがそのように設計されている場合、内部記憶デバイス）との間で適切に渡されることを保証する役割を担う。ＭＣＨ１００２は、時間的に互いに近接して発生し得る、（１つまたは複数の）プロセッサ１００１、インターフェースおよび内部記憶素子の間のシステム・メモリ１００３のアクセスに対する様々な競合する要求を管理する役割を担う。
【００５１】
１つまたは複数のＩ／Ｏデバイス１００８はまた、典型的なコンピューティング・システム内に実装される。Ｉ／Ｏデバイスは、一般に、コンピューティング・システム（例えば、ネットワーキング・アダプタ）間とのデータ転送、またはコンピューティング・システム内の大規模な不揮発性ストレージ（例えば、ハード・ディスク・ドライブ）の役割を担う。ＩＣＨ１００５は、これ自体と観測されるＩ／Ｏデバイス１００８との間に双方向のポイント・ツー・ポイント・リンクを有する。
【００５２】
特許請求されるシステムの異なる実施形態のコンポーネントは、ソフトウェア、ハードウェア、ファームウェア、またはこれらの任意の組合せを含むことができる。コンポーネントは、著作権のある（proprietary）ソフトウェアまたは一般に公開されている（public）ソフトウェアを実行する、公共用プロセッサまたは専用プロセッサあるいは汎用プロセッサが利用できるソフトウェア・プログラムとすることができる。ソフトウェアは、署名の作成および編成ならびに再コンパイル管理専用に書かれた特化したプログラムとすることもできる。例えば、システムのストレージは、ハードウェア（フロッピー（Ｒ）・ディスケット、光ディスク、ＣＤ−ＲＯＭおよび光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ、磁気または光カード、伝播媒体または他のタイプの媒体／機械可読媒体など）、ソフトウェア（ハードウェア・ストレージ・ユニット上への情報の記憶を必要とする命令など）、またはこれらの任意の組合せを含むことができるが、これらに限定されない。
【００５３】
さらに、本発明の要素を、機械実行可能命令を記憶するための機械可読媒体として提供することもできる。機械可読媒体は、フロッピー（Ｒ）・ディスケット、光ディスク、ＣＤ−ＲＯＭおよび光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ、磁気または光カード、伝播媒体または電子命令の記憶に適した他のタイプの媒体／機械可読媒体を含むことができるが、これらに限定されない。
【００５４】
図２および図４に示される例示的な方法の場合、本発明の実施形態は、上述したような様々なプロセスを含むことができる。このプロセスは、汎用プロセッサまたは専用プロセッサに特定のステップを実行させる機械実行可能命令において具体化され得る。あるいは、これらのプロセスは、そのプロセスを実行するための配線論理を含む特定のハードウェア・コンポーネントによって、またはプログラムされたコンピュータ・コンポーネントとカスタム・ハードウェア・コンポーネントの任意の組合せによって実行され得る。
【００５５】
本発明の実施形態は、提示される様々なプロセスのすべてを必要とするものではなく、提示される特定のプロセスを用いずに、または提示されていない追加のプロセスを用いて、本発明の実施形態を実施する方法に関して、当業者が想到できるものである。例えば、１つのマシンが図１０に記載されているが、本開示の実施形態は複数のマシンにまたがって具体化され得る。例えば、変換を分散コンピューティング環境で実行することができ、方法の部分を分散ネットワーク内に配置された異なるコンピュータ上で実行することができる。加えて、図１に示されるように、ジョブの実行を分散コンピューティング環境で実行することができる。
【００５６】
概括
本発明の実施形態の上記の説明は、例示および説明のみを目的として提示されたものであり、網羅的であることまたは本発明を開示された明確な形態に限定することを意図していない。多くの修正形態および適応形態は、本発明の精神および範囲から逸脱することなく、当業者には明らかである。
【図１】
0005705338.tif 000012
【図２】
0005705338.tif 000013
【図３】
0005705338.tif 000014
【図４】
0005705338.tif 000015
【図５】
0005705338.tif 000016
【図６】
0005705338.tif 000017
【図７】
0005705338.tif 000018
【図８】
0005705338.tif 000019
【図９】
0005705338.tif 000020
【図１０】
0005705338.tif 000021