(57)【要約】      （修正有）【課題】スクリプト駆動ソフトウエアツールのアプリケーションを並列処理する。【解決手段】ソフトウエアツール記述言語内のスクリプトを自動解析して“スクリプト断片４”セットを加えた並列計算仕様を生成する。これらの組み合わせはオリジナルスクリプトと同等の機能である。スクリプト断片４を加えた計算仕様を並列ランタイムシステム５で実行することにより、オリジナルソフトウエアツール６及び／又は補助プログラム７の多重インスタンスを並列処理させる。結果処理は入力データを読み込み出力データ９を生成し、オリジナルスクリプト同様の計算を行う。アナライザ、ランタイム、オリジナルソフトウエアツール及び補助プログラムの組み合わせは、与えられたスクリプトと入力データのため、オリジナルソフトウエアツール単独と同様の出力データを生成するが、多重プロセッサを並列に使用することによって処理能力を改善する。【選択図】図１
2006236360.tif 000002
【特許請求の範囲】
【請求項１】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、前記スクリプトを自動的に解析するステップと、該解析に基づいて並列計算仕様を生成するステップとを含み、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、すくなくとも処理ステップとデータセットデフィニションを含むステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップであって、前記直列データフローグラフは、有向エッジによって接続されたノードを持ち、該ノードは、データセット、処理ステップ、中間結果を表すものであるステップと、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項２】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、前記スクリプトを自動的に解析するステップと、該解析に基づいて、スクリプト断片セットに加え並列計算仕様を生成するステップとを含み、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、すくなくとも処理ステップとデータセットの定義を含むステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップであって、前記直列データフローグラフは、有向エッジによって接続されたノードを持ち、該ノードは、データセット、処理ステップ、中間結果を表すものであるステップと、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成するステップと、
（ｄ）前記並列データフローグラフを解析し、幾つかの処理ステップをスクリプト駆動ソフトウェアツールが実行できるような形でスクリプト断片を生成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項３】
前記直列データフローグラフの構成は、
（ａ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｂ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｃ）前記処理ステップ表内のステートメントによって使用される、前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成するステップと、
を含むことを特徴とする、請求項１又は２記載の方法。
【請求項４】
前記並列データフローグラフの構成は、
（ａ）前記直列データセット表に基づいてデータセットの並列データセット表を構成するステップと、
（ｂ）前記直列処理ステップ表に基づいてステートメントの並列処理ステップ表を構成するステップと、
（ｃ）前記直列データセットアクセス表に基づいてデータセットアクセス表を構成するステップと、
（ｄ）前記並列処理ステップ表内で確認される各処理ステップについて、対応する定義済み並列処理書換え規則が前記処理ステップ用に存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義するステップと、
を含むことを特徴とする、請求項３記載の方法。
【請求項５】
前記並列データフローグラフの第１の部分の分割方法が前記並列データフローグラフの第１の部分の分割方法と競合するか否かを判定し、必要な場合に分割競合をリペアするため単数又は複数の付加的な処理ステップを前記並列データフローグラフに挿入することによって、前記構成された並列データフローグラフ内に存在する少なくとも幾つかの分割競合を解決するステップをさらに含むことを特徴とする請求項４記載の方法。
【請求項６】
少なくとも１つの定義済み並列処理書換え規則は、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択されるアルゴリズムであることを特徴とする請求項４記載の方法。
【請求項７】
前記並列計算仕様を生成するステップは、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択されるアルゴリズムを適用することを含むことを特徴とする請求項１または２記載の方法。
【請求項８】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムはコンピュータに自動的に前記スクリプトを解析させ、該解析に基づいて並列計算仕様を生成させるためのインストラクションを備えるものであって、該並列計算仕様は並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、すくなくとも処理ステップとデータセットデフィニションを含むステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップであって、前記直列データフローグラフは、有向エッジによって接続されたノードを持ち、ノードは、データセット、処理ステップ、中間結果を表すものであるステップと、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項９】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムはコンピュータに自動的に前記スクリプトを解析させ、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成させるためのインストラクションを備えるものであって、該並列計算仕様とスクリプト断片セットは並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、すくなくとも処理ステップとデータセットデフィニションを含むステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップであって、前記直列データフローグラフは、有向エッジによって接続されたノードを持ち、該ノードは、データセット、処理ステップ、中間結果を表すものであるステップと、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成するステップと、
（ｄ）前記並列データフローグラフを解析し、幾つかの処理ステップをスクリプト駆動ソフトウェアツールが実行できるような形でスクリプト断片を生成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項１０】
前記直列データフローグラフを構成するステップは、
（ａ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｂ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｃ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを示す直列データセットアクセス表を構成するステップと、
を含むことを特徴とする請求項８または９記載のコンピュータプログラム。
【請求項１１】
前記並列データフローグラフを構成するステップは、
（ａ）前記直列データセット表に基づいてデータセットの並列データセット表を構成するステップと、
（ｂ）前記直列処理ステップ表に基づいてステートメントの並列処理ステップ表を構成するステップと、
（ｃ）前記直列データセットアクセス表に基づいてデータセットアクセス表を構成するステップと、
（ｄ）前記並列処理ステップ表内で確認される各処理ステップについて、対応する定義済み並列処理書換え規則が前記処理ステップ用に存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連するエントリを直列処理エントリとして定義するステップと、
を含むことを特徴とする請求項１０記載のコンピュータプログラム。
【請求項１２】
前記並列データフローグラフの第１の部分の分割方法が前記並列データフローグラフの第１の部分の分割方法と競合するか否かを判定し、必要な場合に分割競合をリペアするため単数又は複数の付加的な処理ステップを前記並列データフローグラフに挿入することによって、前記構成された並列データフローグラフ内に存在する少なくとも幾つかの分割競合を解決するステップをさらに含むことを特徴とする請求項１１記載のコンピュータプログラム。
【請求項１３】
少なくとも１つの定義済み並列処理書換え規則は、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択されるアルゴリズムであることを特徴とする請求項１１記載のコンピュータプログラム。
【請求項１４】
前記並列計算仕様を生成するステップは、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択される少なくとも１つの定義済み並列処理書換えアルゴリズムを適用することを含むことを特徴とする請求項８または９記載のコンピュータプログラム。
【請求項１５】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理し、前記スクリプトを自動的に解析して、該解析に基づいて並列計算仕様を生成するためのシステムであって、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析して、少なくとも処理ステップとデータセットデフィニションを含むステートメントにする手段と、
（ｂ）前記構文解析したステートメントより、その直列データフローグラフを構成する手段であって、前記直列データフローグラフは有向エッジによって接続されたノードを持ち、該ノードは、データセット、処理ステップおよび中間結果を表すものである手段と、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成する手段と、
を含むことを特徴とするシステム。
【請求項１６】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理し、スクリプトを自動的に解析して、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成するためのシステムであって、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析して、少なくとも処理ステップとデータセットデフィニションを含むステートメントにする手段と、
（ｂ）前記構文解析したステートメントより、その直列データフローグラフを構成する手段であって、前記直列データフローグラフは有向エッジによって接続されたノードを持ち、該ノードは、データセット、処理ステップおよび中間結果を表すものである手段と、
（ｃ）前記直列データフローグラフのノードより、並列ランタイムシステムによって実行される並列データフローグラフを構成する手段と、
（ｄ）前記並列データフローグラフを解析して、スクリプト駆動ソフトウェアツールによっていくつかの処理ステップが実行できるような形でスクリプト断片を生成する手段と、
を含むことを特徴とするシステム。
【請求項１７】
前記直列データフローグラフを構成するための手段は、
（a）前記スクリプトによって使用されるデータセットの直列データセット表を構成する手段と、
（b) 前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成する手段と、
（c）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成する手段と、
を含むことを特徴とする請求項１５または１６記載のシステム。
【請求項１８】
前記並列データフローグラフを構成するための手段は、
（a）前記直列データセット表に基づいてデータセットの並列データセット表を構成する手段と、
（b) 前記直列処理ステップ表に基づいてステートメントの並列処理ステップ表を構成する手段と、
（c）前記直列データセットアクセス表に基づいてデータセットアクセス表を構成する手段と、
（d）前記並列処理ステップ表内の確認される各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連するエントリを直列処理エントリとして定義する手段と、
を含むことを特徴とする請求項１５または１６または１７記載のシステム。
【請求項１９】
前記並列データフローグラフの第１の部分の分割方法が前記並列データフローグラフの第１の部分の分割方法と競合するか否かを判定し、必要な場合に分割競合をリペアするため単数又は複数の付加的な処理ステップを前記並列データフローグラフに挿入することによって、前記構成された並列データフローグラフ内に存在する少なくとも幾つかの分割競合を解決する手段をさらに含むことを特徴とする請求項１８記載のシステム。
【請求項２０】
少なくとも１つの定義済み並列処理書換え規則は、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択されるアルゴリズムであることを特徴とする請求項１８記載のシステム。
【請求項２１】
前記並列計算仕様を生成する手段は、単純分割、キーベース分割、ローカル-グローバル除算、外部パラレリズムアルゴリズム、ステートメント分解からなる群から選択される、少なくとも１つの定義済み並列処理書換えアルゴリズムを適用する手段を含むことを特徴とする請求項１５または１６記載のシステム。
【請求項２２】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、前記スクリプトを自動的に解析するステップと、該解析に基づいて並列計算仕様を生成するステップとを含み、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項２３】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、スクリプトを自動的に解析するステップと、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成するステップとを含み、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項２４】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、前記スクリプトを自動的に解析するステップと、該解析に基づいて並列計算仕様を生成するステップとを含み、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成するステップと、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成するステップと、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成するステップと、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連するエントリを直列処理エントリとして定義するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項２５】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するための方法において、前記スクリプトを自動的に解析するステップと、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成するステップとを含み、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップし、この構成ステップは、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成するステップと、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成するステップと、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成するステップと、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とする方法。
【請求項２６】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムは、コンピュータに自動的に前記スクリプトを解析させ、該解析に基づいて並列計算仕様を生成させるインストラクションを備えるものであって、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項２７】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムは、コンピュータに自動的に前記スクリプトを解析させ、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成させるためのインストラクションを備えるものであって、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成するステップと、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成するステップと、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項２８】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムは、コンピュータに自動的に前記スクリプトを解析させ、該解析に基づいて並列計算仕様を生成させるインストラクションを備えるものであって、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成するステップと、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成するステップと、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成するステップと、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項２９】
コンピュータリーダブル媒体上に存在し、スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのコンピュータプログラムにおいて、前記コンピュータプログラムは、コンピュータに自動的に前記スクリプトを解析させ、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成させるインストラクションを備えるものであって、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、
（ａ）前記スクリプトを構文解析し、ステートメントにするステップと、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成するステップと、この構成ステップは、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成するステップと、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成するステップと、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成するステップと、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義するステップと、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成するステップと、
によって、前記スクリプトと同等な機能を提供することを特徴とするコンピュータプログラム。
【請求項３０】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのシステムにおいて、前記スクリプトを自動的に解析する手段と、該解析に基づいて並列計算仕様を生成するための手段を含み、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析し、ステートメントにする手段と、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成する手段と、この手段は、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成する手段と、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成する手段と、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成する手段と、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成する手段と、
を含むことを特徴とするシステム。
【請求項３１】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのシステムにおいて、スクリプトを自動的に解析する手段と、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成するための手段を含み、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析し、ステートメントにする手段、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成する手段、この手段は、
（ｉ）前記スクリプトによって使用されるデータセットの直列データセット表を構成する手段と、
（ｉｉ）前記スクリプトによって実行されるステートメントの直列処理ステップ表を構成する手段と、
（ｉｉｉ）前記処理ステップ表内のステートメントによって使用される前記データセット表内のデータセットを指し示す直列データセットアクセス表を構成する手段と、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成する手段と、
を含むことを特徴とするシステム。
【請求項３２】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのシステムにおいて、前記スクリプトを自動的に解析する手段と、該解析に基づいて並列計算仕様を生成するための手段を含み、前記並列計算仕様は、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析し、ステートメントにする手段と、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成する手段と、この手段は、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成する手段と、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成する手段と、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成する手段と、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義する手段と、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成する手段と、
を含むことを特徴とするシステム。
【請求項３３】
スクリプト駆動ソフトウェアツールのスクリプトに基づくコンピュータアプリケーションプログラムを並列処理するためのシステムにおいて、前記スクリプトを自動的に解析する手段と、該解析に基づいてスクリプト断片セットに加え並列計算仕様を生成するための手段を含み、前記並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されるとき、前記スクリプトと同等な機能を提供し、前記システムは、
（ａ）前記スクリプトを構文解析し、ステートメントにする手段と、
（ｂ）前記構文解析したステートメントより直列データフローグラフを構成する手段と、この手段は、
（ｉ）前記直列データセット表に基づくデータセットの並列データセット表を構成する手段と、
（ｉｉ）前記直列処理ステップ表に基づくステートメントの並列処理ステップ表を構成する手段と、
（ｉｉｉ）前記直列データセットアクセス表に基づき並列データセットアクセス表を構成する手段と、
（ｉｖ）前記並列処理ステップ表内の確認された各処理ステップに対して、対応する並列処理書換え規則が存在するか否かを確定し、存在する場合には、前記対応する定義済み並列処理書換え規則を適用して、並列データセット表、並列処理ステップ表、データセットアクセス表内の関連するエントリを並列処理エントリとして再定義し、また存在しない場合には、前記関連エントリを直列処理エントリとして定義する手段と、
を含むものであって、
（ｃ）前記直列データフローグラフより並列データフローグラフを構成する手段と、
を含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理システムの計算の制御、特にスクリプト駆動ツールの並列処理アプリケーションに関する。
【０００２】
著作権の通知
この特許書類の開示部分は著作権保護の対象となる材料を含む。著作権者は、特許商標庁の特許ファイルまたは記録に掲載されている限り、あらゆる特許開示の複製に異議はないが、それ以外については全ての如何なる著作権も留保する。
【背景技術】
【０００３】
シングルプロセッサコンピュータの計算速度は過去３０年の間に途方もなく進歩した。しかしながら、世界最速のシングルプロセッサコンピュータをさえ上回る計算力が多くの分野で必要とされている。１つの例はトランザクション処理であり、これは複数のユーザがコンピュータリソースに同時にアクセスするものであるが、システムが商用に耐えるためには応答時間が短くなければならない。もう１つの例はデータベースマイニングであり、何百ギガバイトもの情報が処理されねばならず、直列式コンピュータ上でのデータの処理は何日または何週間もかかる。したがって、種々の“並列処理”システムがそのような問題を対処するために開発されている。この議論において、並列処理システムは、ローカルの（例えば、SMPコンピュータ等のマルチプロセッサシステム）、またはローカルに分置された（例えば、クラスタまたはMPPsとして結合された多重プロセッサ）、またはリモートの、またはリモートに分置された（例えば、LANまたはWANネットワークを介して結合された多重プロセッサ）多重中央処理装置（CPUs）、またはそれらのあらゆる組み合わせを使用するコンピュータシステムのあらゆる構成を含む。
【０００４】
しかしながら、そのような並列処理システムの存在にもかかわらず、全てのプログラムまたはソフトウエアツールが並列処理に利点を有するように設計されているわけではない。例えば、幾つかの商業的に重要なソフトウエアツールは以下の特徴を共有する：
・ソフトウエアツールは種々の機能を行う能力がある。
・それらの機能の実施は一連の処理ステップとそれら処理ステップ間のデータの置換えとを特定する“記述言語”によって制御される。
・ユーザはツールとその記述言語との組み合わせを使用するアプリケーションを書き込む。
・ソフトウエアツールは並列処理を使用しない、または最小限に使用する。
【０００５】
そのようなソフトウエアツールの１例は“SAS（登録商標）ソフトウエアシステム”、すなわちSAS Institute, Inc.によって作成されたデータ解析システムである。このツールによって提供される機能はデータ変換、データ統合、データセット管理、多種多様の統計的処理を含む。ユーザは“SAS”とも呼ばれる言語内にスクリプトを書き込むことによってSASアプリケーションを構築する。そのようなツールの第２例はSyncSort Inc.によって作成された“SyncSort（登録商標）”である。このアプリケーションによって提供される機能はデータフィルタリング、データソーティング、データ統合を含む。ユーザは“Syncsort”スクリプトを書き込むことによって“Syncsort”アプリケーションを構築する。
【０００６】
そのようなソフトウエアツールで構築されたアプリケーションが大量のデータの処理に使用されるとき、実行時間は極めて大きくなる。多数のプロセッサがシングルアプリケーションに適用できる並列処理は、そのようなデータ量の多いアプリケーションをスピードアップさせる可能性を有する。理想的には、シングルプロセッサ上で作動させると１０時間かかるジョブは６０プロセッサ上で作動させると１０分ぐらいに短縮することもできる。そのようなパフォーマンス向上は、もちろん、並列処理システムを利用できる能力があるソフトウエアを有するかどうかに依存する。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
これらのソフトウエアツールのユーザは、ほとんどの場合、新しいおよび／または異なるツールをどのように使用するか、またはツールの現行のアプリケーションをどのように変更するかを進んで学習しようとはしない。例えば、SASのユーザは一般的に全く新しい記述言語を学習したいとか現行のSASアプリケーションを変更したいと思わないだろう。そのようなユーザにパラレリズムの恩恵をもたらすため、発明者は、記述言語内に表されているように、ツールのアプリケーションを自動的に並列処理することが望ましいであろうと考えた。
【課題を解決するための手段】
【０００８】
本発明は特定のスクリプト駆動ソフトウエアツールのアプリケーションを並列処理するためのシステムおよび方法を含む。好ましい実施形態において、ソフトウエアツール記述言語内のスクリプトは、自動的に解析されて“スクリプト断片”のセットを加えた並列計算のための仕様を生成し、それらの組み合わせはオリジナルスクリプトと機能的に同等である。スクリプト断片を加えた並列計算仕様は次に並列ランタイムシステムによって実行され、これによりオリジナルソフトウエアツールおよび／または補助プログラムの多重インスタンスが並列処理として作動する。結果として起こるプロセスは入力データを読み込み、出力データを生成し、オリジナルスクリプトによって特定されたのと同様の計算を行う。アナライザ、ランタイムシステム、オリジナルソフトウエアツール、補助プログラムの組み合わせは、所定のスクリプトおよび入力データのため、オリジナルソフトウエアツール単独と同様の出力データを生成することになるが、“処理能力”全体の実質的な改善のため多重プロセッサを並列に使用する能力を有する。
【０００９】
一方で、本発明はスクリプト駆動ソフトウエアツールのスクリプトに基づいてコンピュータアプリケーションプログラムを並列処理するための方法、システム、およびコンピュータプログラムを含み、スクリプトを自動的に解析することとこの解析に基づいて並列計算仕様を生成することとからなり、この並列計算仕様は、並列ランタイムシステムによって実行されたときにスクリプトと同等の機能を提供する。別の側面において、本発明はスクリプト駆動ソフトウエアツールのスクリプトに基づいてコンピュータアプリケーションプログラムを並列処理するための方法、システム、およびコンピュータプログラムを含み、スクリプトを自動的に解析することとこの解析に基づいてスクリプト断片セットに加えた並列計算仕様を生成することとからなり、この並列計算仕様とスクリプト断片セットは、並列ランタイムシステムによって実行されたときにスクリプトと同等の機能を提供する。
【００１０】
本発明の１または複数の実施形態の詳細を添付図面および以下の説明において述べる。本発明のその他の特徴、目的、および利点は、明細書、図面および特許請求の範囲から明らかとなるだろう。各図面の同じ参照番号および記号は同じ要素を示す。
【発明を実施するための最良の形態】
【００１１】
概要
図１は、本発明の好ましい実施形態のデータフロー図である。SAS等の言語のソフトウエアツールスクリプト１は、自動的に解析２されて、“スクリプト断片”４のセットに加えた並列計算３用仕様を生成する。スクリプト断片４に加えた並列計算仕様３の組み合わせはオリジナルスクリプト１と機能的に同等である。スクリプト断片を加えた並列計算仕様は次に並列ランタイムシステム５によって実行され、それは例えばAb Initio Software CorporationからのCo>Operating System（商標名）ランタイムシステムとすることができる。そのような実行は、オリジナルソフトウエアツール６および／または補助プログラム７の多重インスタンスの並列作動を引き起こす。結果処理６、７は入力データ８を読み込み出力データ９を生成し、オリジナルスクリプト１によって特定されたのと同様の計算を行う。アナライザ、ランタイムシステム、ツール、補助プログラムの組み合わせ１０は、所定のスクリプト１と入力データ７のため、オリジナルソフトウエアツール６単独と同様の出力データ８を生成するが、“処理能力”全体に実質的な改善を獲得するため多重プロセッサを並列に使用する。
【００１２】
好ましい実施形態を適用するため、各スクリプト１用ソフトウエアツール６および記述言語は特定の条件を満足するべきである：
・記述言語は処理ステップおよびデータセットディフィニション（例えば、ファイル、データベース、一時的データセット）等のステートメントのシーケンスで構成されるべきである。
・記述言語は処理ステップによって読み込まれる／書き込まれるあらゆるデータを明白または暗黙に特定すべきである。これは処理ステップ間で情報を通過させることに使用される一時的データセット；データセットディフィニションステートメント内で定義される外部データセット；および処理ステップのなかで（場合によっては暗黙に）参照される外部データセットを含むこともできる。
・方法は処理ステップの少なくとも幾つかを並列処理することに（例えば、従来のアルゴリズムから）知られているべきである。並列処理方法はデータを部分集合内へ分割し各部分集合上で指示された処理ステップを作動すること；手続きの別々に利用可能な並列インプリメンテーションを挿入すること；データを分割内へ分割し各部分集合上で“グローバル手続き”を作動し、次にグローバル手続きの出力上で“ローカル手続き”を作動させることを含む（グローバルおよびローカル手続きはベース記述言語内でインプリメントされるのが好ましいが、必ずしもそうする必要はない。）。
【００１３】
図２は、イニシャルスクリプト１を自動的に解析２しスクリプト断片４に加えた並列計算３の仕様を生成するための好ましい方法を示すデータフロー図である。スクリプト解析方法２は以下のようにインプリメントできる：
・ステップ101：入力スクリプト１をステートメント102のシーケンス内へ分割する。
・ステップ103：処理ステップ間のデータ交換を表す直列データフローグラフ104を生成するためステートメント102のシーケンスを処理する。
・ステップ105：直列データフローグラフ 104を並列処理し、それにより並列データフローグラフ106を生成する。
・ステップ107：“スクリプト断片4”を発生しオリジナルスクリプト駆動アプリケーションが幾つかの処理ステップを実行できるよう、並列データフローグラフ106を、選択的に、解析する。
・ステップ108：結果データフローグラフ106がその結果並列計算３の仕様に複写できる。
【００１４】
アルゴリズムの幾つかの点で、行われている計算は“データフローグラフ”として表される。２つの場合があり：直列データフローグラフ104は、オリジナルアプリケーションによって、直列で、行われる計算を表し；並列データフローグラフ106は、並列ランタイムシステム５とオリジナルソフトウエアツール６と補助プログラム７の組み合わせによって、並列に、行われる計算を表す（以下でさらに説明する）。それらのデータフローグラフ104、106は種々の方法で表すことができるが、グラフ形状（例えば図３）かまたはグラフ（例えば図６）の頂点およびエッジを表す表としてのどちらかで表されることが最も多い。両方の表記は便利な指図として使用される。
【００１５】
図３は、グラフ形状の直列データフローグラフ104の例である。そのようなグラフは例えば、スクリプトによって読み込まれているデータセット201、202；スクリプトによって書き込まれているデータセット208；スクリプト内に含まれる処理ステップ203、205、207；および、明白にか暗黙にかのどちらかで、１つのステップから別のステップへ通過したあらゆる中間結果204、206を表す頂点のセットを典型的に有する。
【００１６】
典型的な直列データフローグラフ104は各処理ステップによってアクセスされたデータセットを示す有向エッジ220〜226のセットも有する。説明された実施形態において、処理ステップ220、221、223、225の中に向けられたエッジは、データセット／中間結果が読み込まれていることを示し、一方処理ステップ222、224、226の外に向けられたエッジは、データセット／中間結果が処理ステップによって書き込まれていることを示している。
【００１７】
図４は、グラフ形状の並列データフローグラフ106の例である。典型的に、並列データフローグラフは以下を除いて対応する直列データフローグラフと一致する：
・オリジナル処理ステップ203、205の幾つかは、（太線によって示された）並列実行が記されている。
・オリジナル中間結果204、206の幾つかは、（太線によって示された）“分割”されたデータセットとして記されている。
・オリジナルデータセットアクセス220、221、222、223、224の幾つかは、（太線によって示された）並列データにアクセスしているとして記されている。
・幾つかの新しい中間結果212、213、215、217、処理ステップ210、211、214、216、データセットアクセス227〜234は、種々の処理ステップによって要求された様にデータを分割するために加えられている。新しい中間結果212、213、215の幾つかは分割されたとして記されている。新しい処理ステップ210、211、214の幾つかは並列実行が記されている。新しいデータセットアクセス228、230、231、232、233の幾つかは並列データにアクセスしているとして記されている。
・分割キーに関する表記（例えば、“BY v2, v3”）は、種々の処理ステップ205、データセット215、206、およびデータセットアクセス223、224、232、233に加えられている。それらの表記は、以下に説明されるように、データ分割の仕方を示す。
【００１８】
本発明がスクリプト駆動ツールをベースにしたアプリケーションの並列処理に一般的に適用可能である一方、本発明の方法は、アプリケーションとアプリケーションの記述言語のセマンティックとによって提供されるファシリティの詳細を基に、各特定のスクリプトベースツール用に調整することを要求する。本発明の方法はまた、使用されている特定の並列ランタイムシステムに幾分調整することを要求する。丁度言及されたアプリケーション特定情報に加えて、ここに含まれる方法が与えられると、そのような調整は当業プログラマーによって行うことができる。SASアプリケーションを並列処理することにおいて生じる幾つかの特定の問題にどのように対応するかの詳細は以下で述べられる。
【００１９】
スクリプト駆動アプリケーションの実施例
本発明によって対応される問題の幾つかを説明するため、解析と呼ばれる仮定データ解析プログラムが、その記述言語に沿って、説明される。この仮定プログラムおよび記述言語の目的は、普通の従来型の記述言語の特徴を説明すること、およびスクリプト駆動ツールのアプリケーションを並列処理する方法を説明することに使用されることになる種々の例のための基礎を提供することである。
【００２０】
仮定“解析”プログラムは以下の基本能力を有する：
・ファイルまたはリレーショナルデータベースからデータを読み込むこと。
・ファイルまたはリレーショナルデータベースにデータを書き込むこと。
・データセットの各レコード上で単純な算出を行うことによって１つのデータセットをもう１つのデータセットへ変換すること。
・データセットを連結すること。
・集約関数“SUM”、“MIN”、“MAX”を計算すること。それら集約関数は完全なデータセットに適用できる。交互に、“グループ分けされた統合”が（SQL“GROUP BY”またはSAS“BY”および“CLASS”ステートメントにあるように）計算される。これは以下で説明される。
・解析アルゴリズムのアプリケーションによってデータを解析すること。
【００２１】
１．アプリケーションの発動
この実例において、アプリケーションはアプリケーションの名前（“analyze”）、スクリプトを含んでいるファイルの名前、およびゼロ以上のコマンドラインパラメータを特定する“コマンドライン”を介して発動される。例えば、以下のコマンドラインは“analyze”アプリケーションを作動させ、スクリプト”script1”を使用しコマンドラインパラメータ”datafile1”を特定する：
analyze script1 datafile1
コマンドラインパラメータはフォーム＄＜number＞の構成によって、必要に応じて、＄１は第１コマンドラインパラメータを参照、＄２は第２コマンドパラメータを参照、以下同様なように、スクリプトのなかから参照されることができる。コマンドラインパラメータの参照はデータセット宣言内のファイル名の場所で使用できる。
【００２２】
２．データセット宣言
データセットはレコードのシーケンスである。実施例において、各レコードはスペースセパレイテッドデータフィールドのリストで構成され、データセットの第１レコードはデータフィールドの名前を含む（簡略するために、幾つかの例ではフィールド名のリストを省く）。例えば：
custno   month   year   balance   limit
00001     01     98     0400    1000
00001     02     98     0600    1000
00001     03     98     0200    1000
00002     01     98     0100    3000
00002     02     98     0000    3000
【００２３】
データセットは以下のように宣言される：
INPUT datasetname fileneme
読み込まれるデータセットを宣言する。”filename”はデータを含んでいるファイルの名前を入力する。”datasetname”はスクリプト内の他の場所でデータセットを参照するのに使用できる。
OUTPUT datasetname filename
上記のとおりだが、データセットがアプリケーションによって書き込まれることを宣言する。
TEMP datasetname filename
上記のとおりだが、一時的データセットがアプリケーション内で使用されることを宣言する。
DB_IN datasetname tableneme
INPUTステートメントと同様だが、表名と呼ばれるリレーショナルデータベース表からそのデータを得る。データのタイプはデータベースをクエリーすることによって確定される。
DB_OUT datasetname tablename
OUTPUTステートメントと同様だが、そのデータを表名と呼ばれるリレーショナルデータベース表に送る。
【００２４】
例えば、処理されることになるデータがファイル内にある場合、入力データセットは以下のように宣言される：
INPUT customers customers.dat
代わりに、データがデータベース表内にあった場合、入力データセットは以下のように宣言される：
DB_IN customers cust_table
コマンドラインパラメータはデータセット用ファイルに名前を付けることにも使用できる。例えば：
INPUT customers $1
【００２５】
３．処理ステップ
仮定analyzeアプリケーションは以下の処理ステップを定義する：コピー、連結、統合、解析。それらの処理ステップの各々はシングル出力を生成し、各ステップは、連結ステップを除いて、シングル入力からそのデータを得る。
【００２６】
デフォルトでは、１つの処理ステップの出力は次の処理ステップの入力として使用されることになる。例えば、以下のスクリプトにおいてstep1の出力はstep2の入力として使用されることになる：
step1
step2
【００２７】
データステートメントが処理ステップの前に即座に来る場合、そのときは処理ステップはデータステートメントからその入力を得ることになる。同様に、データステートメントが処理ステップの後に即座に来る場合、そのときは処理ステップは特定されたデータセットにそのデータを書き込むことになる。例えば、以下のスクリプトにおいて、step1はindataデータセットからその入力を読み込み、outdataデータセットにその出力を書き込むことになる：
INPUT indata input.data
step1
OUTPUT outdata output.data
【００２８】
それらのルールはフォームOUTPUT＝datasetまたはINPUT＝datasetの節をあらゆる処理ステップに加えることによって無効にできる。例えば、以下のスクリプトにおいてstep1はindataからそのデータを得て、outdataに書き込むことになる：
INPUT indata input.data
OUTPUT outdata output.data
step1 INPUT=indata OUTPUT=outdata
【００２９】
４．コピーステートメント
コピーステートメントは以下の構文を有する：
COPY field=expression, field=expression...
コピーステートメントは１つのデータセットをもう１つのデータセットにコピーする。出力データセット内の各レコードは示されたエクスプレッションを、入力レコード内のフィールドを表すエクスプレッション内の変数で、評価することによって構成される。例えば、以下のデータセットが処理されると仮定する：
v1   v2   v3
1    2    3
2    4,    2
ここでサンプルスクリプト：
INPUT indata input.data
COPY v1=v1, v2=v2, v3=v3, v4=v1+v2+v3
OUTPUT outdata output.data
以下の出力が生成される：
v1   v2   v3   v4
1    2    3    6
2    4    3    8
【００３０】
５．連接ステートメント
連接ステートメントは以下の構文を有する：
CONCATENATE dataset1 dataset2...
このステートメントの出力は各特定されたデータセットを読み込みそれらのレコードの全てをシングル出力データセットに書き込むことの結果である。出力データの大きさは問題ではない。しかしながら、データセット内のフィールドのリストは合致しなければならない。実施例において、CONCATENATEオペレーションは他の処理ステートメントによって使用されるデフォルト入力ルールに従わない。（すなわち、前のステートメントの出力を入力として取得しない）
【００３１】
６．統合ステートメント
統合ステートメントはレコードのセット全体の中の以下の統合の計算に使用される：SUM、MIN（minimum）、MAX（maximum）。統合ステートメントは以下の構文を有する：
AGGREGATE field=aggop expression,field=aggop expression...[BY key, key...]
【００３２】
“統合操作”（aggop）はキーワードSUM、MIN、MAXの１つで構成される。特定されるBY節がない場合、そのときはAGGREGATEオペレーションの出力は、示されたエクスプレッションの合計／最小／最大を（適切に）含むシングルレコードであり、データセット全体にわたって計算される。例えば、以下のデータセットが処理されると仮定する：
value
1
2
3
4
ここでサンプルスクリプト：
INPUT indata input.data
AGGREGATE v1=MIN value, v2=MAX value, v3=SUM value
OUTPUT outdata output.data
これは以下の出力を生成する：
v1   v2   v3
1    4    10
【００３３】
BY節が特定される場合、そのときはデータは部分集合に分割され、各部分集合はBY節内で特定されるすべてのキーのための同一値を有する。統合はそのような部分集合各々のために計算される。BY節内のキーは各出力レコードの前面に置かれることになる。例えば、以下のデータセットが処理されると仮定する：
k1   k2   value
1     2     7
3     4     1
3     4     2
3     4     3
ここでサンプルスクリプト：
INPUT indata input.data
AGGREGATE v1=MIN value, v2=MAX value, v3=SUM value BY k1, k2
OUTPUT outdata output.data
これは以下の出力を生成する：
k1   k2   v1   v2   v3
1    2    7    7    7
3    4    1    3    6
【００３４】
７．解析ステートメント
解析ステートメントはレコードの集合に基づいてシングル整数値を計算するアルゴリズムの発動に使用される。統合と同様に、解析ステートメントは選択的なBY節を取得する。解析ステートメントは単数または複数のステートメントが並列処理できない場合取られる測定を説明するために含まれる。
ANALYZE [BY key,key...];
【００３５】
並列ランタイムシステムの実施例
見本アプリケーションを並列に作動させるため、“並列ランタイムシステム”を用いることが必要である。これはプログラムが多重プロセッサ上で同時に作動されることを許すソフトウエアシステムである。ここで開示する方法は何らかの特定の並列ランタイムシステムを特定するものではないが、例示的説明のみを目的として、単純ランタイムシステムについて説明する。サンプルランタイムシステムは四つのステートメント：実行、単純分割、ハッシュ分割、およびギャザーを有する。サンプルランタイムシステムは解析システムによって使用されるのと同様のフォーマットのデータを使用する。
【００３６】
１．実行ステートメント
runステートメントは（以下の）フォームを有する：
run count program argument1 argument2 ...
runステートメントは、コマンドライン上の特定されたアーグュメントをプログラムインスタンスへ渡す特定されたプログラムのcountインスタンスを発効する。例えば、run 3 myprogram arg1ステートメントはmyprogramの３つのインスタンスを並列に作動し、各インスタンスにコマンドラインパラメータarg1を提供する。
【００３７】
あらゆる引数は選択的に、セミコロンで分割されたカウント要素のリストで構成することができる。例えば、引数a；b；cは3要素a、b、およびcのリストとして翻訳される。プログラムが作動されるとき、各プログラムのnth実施はそのようなリストの各々のnth要素で呼ばれる。例えば、ステートメント実行２myprogram a1；a2  b1；b2はmyprogramの２つのインスタンスを並列に作動する。第１インスタンスは引数a1 b2が与えられ第２インスタンスは引数a2  b2が与えられる。
【００３８】
２．単純分割ステートメント
単純分割ステートメントは（以下の）フォームを有する：
simple-partition input putput
単純分割ステートメントは入力ファイルのセミコロンで分割されたリストからレコードを得て、それらを出力ファイルのセミコロンで分割されたリスト間に配分する。配分は、データをほぼ同等に配分できるあらゆる方法により行うことができる。例えば、ラウンドロビン分割において、各入力ファイルからのkth入力レコードは、mが出力ファイル数である場合出力ファイル（k mod m）に書き込まれる。この操作は並列に行われる。例えば、以下の２つの入力ファイル“in1”と“in2”が処理されると仮定する：
in1:
v1
0
1
2
in2:
v1
3
4
5
simple-partition in1；in2 out1；out2；out3ステートメントを使用することは結果が以下の三つの出力ファイルとなる：
out1:
v1
0
3
out2:
v1
1
4
out3:
v1
2
5
【００３９】
３．ハッシュ分割ステートメント
hash-partitionステートメントは（以下の）フォームを有する：
hash-partition key input output
hash partitionステートメントは入力ファイルのセミコロンで分割されたリストからレコードを得て、それらを出力ファイルのセミコロンで分割されたリスト間に配分する。ステートメントはキーフィールドのセミコロンで分割されたリストが特定されることを要求する。各入力レコードのために、ハッシュ分割オペレーションは特定されたキー値に基づいて“ハッシュ関数”を計算し、この関数を使用してレコードが書き込まれることになる出力ファイルを確定する。例えば、kがキーフィールドの値の合計でありmが出力ファイル数である場合、ハッシュ関数は（k mod m）+1として計算できる。これが行われるとき、所定のキー値を有するすべてのレコードは最後には同様の出力ファイル内にある。この操作は並列に行われる。例えば、２つの入力ファイル“in1”と“in2”が処理されると仮定すると仮定する。
in1:
v1   v2
0    0
0    1
2    2
in2:
v1   v2
0    3
1    4
2    5
hash\partition v1 in1;in2 out1;out2;out3ステートメントを使用すると、結果として以下の三つの出力ファイルが得られる：
out1:
v1   v2
0    0
0    1
0    3
out2:
v1   v2
1    4
out3:
v1   v2
2    2
2    5
【００４０】
４．ギャザーステートメント
gatherステートメントは（以下の）フォームを有する：
gather input output
入力はファイルのセミコロンで分割されたリストであり、出力はシングルファイルである。入力ファイル内のレコードは結合されてシングル出力ファイルになる。この操作は並列に行われる。
【００４１】
本発明の好ましい実施形態
以下のサブセクションは図２で示された“解析スクリプト”２ステップの好ましい実施形態を説明する。
【００４２】
１．ステップ101−ステートメントへの分割
図１と図２を再び参照すると、ステップ101はオリジナルスクリプト１をステートメント102のシーケンスに分割している。これは主にオリジナルスクリプトを構文解析し“解析木”を生成することの問題である。コンピュータ言語を構文解析する方法はよく知られている：ほとんどの場合、要求される全ては“文法”を書き込み、その文法を“Yacc”等の“構文解析ルーチン生成系”で処理することである。結果は構文解析を行うためのプログラムになる。
【００４３】
図５はイニシャルスクリプト１の例とそれが含むステートメント102のシーケンスのレプリゼンテーションを示す。それらのステートメントはデータセット201、202、208と処理ステップ203、205、207とにカテゴライズされる。便宜上、テキスト識別子（例えば“ステップ１”）はステートメントに加えられている。
【００４４】
２．ステップ103−直列データフローグラフの構成
ステップ103は直列データフローグラフ104の構成である。これはステートメント102のシーケンスを解析することによって行われる。その目的はデータセット、処理ステップ、中間結果をあらわすノードの集合を生成し、各処理ステップで読み込まれまたは書き込まれるデータセット／一時的結果を示すエッジの集合を生成することである。
【００４５】
この実例において、直列データフローグラフ104は３つの表で表される：データセット表601、処理ステップ表602、（処理ステップによってデータセットアクセスをあらわす）データセットアクセス表603。図６はデータセット表、処理ステップ表、データセットアクセス表の例を示しているダイアグラムである。
【００４６】
実施形態において、データセット表601内の各エンティティは以下で構成される：
・各データセットの名前。
・データセットのクラス（例えば、入力、出力、一時的）。
・データのロケーションに関する表示（例えば、ファイル名）。
・データセットがオリジナルスクリプト内に明白に存在していたかどうかの表示。
・オリジナルスクリプト内に存在するその他のあらゆる情報。
【００４７】
実施形態において、処理ステップ表602内の各エンティティは以下で構成される：
・各処理ステップの名前。
・行われている操作。
・あらゆるパラメータまたはスクリプト内に供給されたその他の情報（例えば、統合エクスプレッション、あらゆるBY節）。
【００４８】
実施形態において、データセットアクセス表603内の各エンティティは以下で構成される：
・処理ステップの名前。
・その処理ステップによってアクセスされるデータセットの名前。
・アクセスの方向（例えば入力対出力）。
・データセットンロールに関する表示。例えば、処理ステップは２つの入力“オールド”と“ニュー”を読み込み２つの出力“アウトプット”と“エラー”を書き込むことができる。ほとんどの処理ステップはシングル入力から読み込み（例えば“in”）、シングル出力に書き込む（例えば“out”）。
【００４９】
図７はステップのシーケンスを直列データフローグラフ内に変換することの例を示すフローチャートである。好ましい実施形態において、この方法は以下のステップを含む。
・ステップ500：まず始めにデータセット601、処理ステップ602、データセットアクセス603のための空の表を生成する（図６にも見える）。
・ステップ501：ステートメント102をスキャンし各データセット201、202、208と、ステートメント102で確認されるグローバル変数のためデータセット表601にエントリを生成する。各エントリは（データセットステートメントからの付加的なデータセット特定情報に加えた）グローバル変数またはデータセットの名前を抽出し、データセットまたはグローバル変数がオリジナルスクリプトに明白に存在していたことを言及することによって構成される。
・ステップ502：あらゆる処理ステップ203、205、207がまだ解析されておらず処理ステップ表602に加えられていないかどうかを確定する。全ての処理ステップが解析されている場合、アナリシスが行われる（ステップ512）。
・ステップ503：次に解析される処理ステップを選択する。
・ステップ504：そのような処理ステップの各々のため処理ステップ表602にエントリを生成する。このエントリは処理ステップのための名前を含む。それらの名前は、例えば“ステップナンバーズ”のシーケンスを発生することによって、自動的に発生される。各エントリは処理ステップステートメントから抽出されるあらゆるパラメータも含むべきである。
・ステップ505：データセット201、202、208が現在の処理ステップによって明白に参照されることを確定し、そのような参照の各々のためデータセットアクセス表603に１つのエントリを生成する。
・ステップ506：現在の処理ステップが現行のデータセットを暗黙に参照しているかどうかを確定する。もしそうであるなら、暗黙入力への各参照が処理されるまで以下のようにループする：
・どのデータセットが暗黙に参照されているかを確定するため処理ステップのコンテキストを試験する。
・ステップ508：現在の処理ステップである“processing step”と暗黙に参照されたデータセットである“dataset”と共に、データアクセス表603でエントリを生成する。ほとんどすべての場合において、暗黙参照のこのフォームは“implicit input”に対しものになる。
・ステップ509：現在の処理ステップが新しいデータセットを暗黙に生成しているかどうかを確定する。もしそうであるなら、新しいデータセットへの各参照が処理されるまで以下のようにループする：
・ステップ510：新しい暗黙データセットのためデータセット表601にエントリを生成する。これは新しいデータセット識別子を生成しデータセットが明白に生成されていなかったことを言及することを含む。
・ステップ511：現在の処理ステップである“processing step”と新しく生成された中間結果データセットである“dataset”と共に、データセットアクセス表603にエントリを生成する。ほとんど全ての場合において、暗黙参照のこのフォームは“implicit output”に対するものになる。
【００５０】
暗黙データセット参照の解消のための正確な方法（ステップ507とステップ510）は、処理されている記述言語のセマンティックに依存する。しかしながら、この解消のためのルールは典型的に極めて単純であり、そのような解消ストラテジーの実施はルーティンプログラミングの問題であるべきである。上記のanalyze記述言語での暗黙データセット解消のために使用されるルールは、このタスクを行う１つの方法の典型である：
・処理ステップが入力データを要求する場合、および特定される入力データセットがない場合、および前のステートメントがデータセットである場合、そのときは前のステートメントのデータセットは、現在の処理ステップの入力として暗黙に参照される。
・処理ステップが入力データを要求する場合、および特定される入力データセットがない場合、および前のステートメントが処理ステップである場合、そのときは前の処理ステップの出力は、現在の処理ステップの入力として暗黙に参照される。
・処理ステップが出力を生成する場合、および特定される出力データセットがない場合、および次のステートメントがデータセットである場合、そのときは次のステートメントのデータセットは、現在の処理ステップの出力として暗黙に参照される。
・処理ステップが出力を生成する場合、および特定される出力がない場合、および次のステートメントが処理ステップである場合、そのときは新しい中間データセットは、現在の処理ステップの出力として暗黙に生成され暗黙に参照される。
【００５１】
暗黙参照の解消の例として、図６を参照されたい。図６に示されたサンプルスクリプト１は、処理ステップ表602に示された、三つの処理ステップ203、205、207を含む。この例のため、イクスプリシットおよび暗黙データセット参照は以下のとおりである：
・第１処理ステップ203は“CONCATENATE”操作であり、それはデータセットindata1 201とindata2 202とから明白に読み込むことができる。特定される出力データセットはなく、それ故処理ステップはデータセット表601の中間結果“temp1”204を暗黙に生成し参照する。
・第２処理ステップ205は“AGGREGATE”操作であり、特定される入力データセットはなく、それ故操作はその入力として前のステップ203の出力“temp1”204を暗黙に参照する。特定される出力データセットはなく、それ故処理ステップはデータセット表601の中間結果“temp2”206を暗黙に生成し参照する。
・最終処理ステップ207は“ANALYZE”操作であり、特定される入力データセットはなく、それ故操作はその入力として前のステップ205の出力“temp2”206を暗黙に参照する。特定される出力データセットはないが、しかし次の操作は出力データセット“outdata”208であり、それ“outdata”は暗黙に参照される。
【００５２】
３．ステップ105−直列データフローグラフの並列処理
ａ．概観
このセクションは、アプリケーションの個々のステップの幾つかを並列処理するための方法のレパートリーが与えられ、どのように直列データフローグラフ104から並列データフローグラフ106を自動的に発生することが可能かを述べる。働かせるこの方法のため、並列処理レパートリーは直列データフローグラフ104のシングルヴェルテックスを試験し並列データフローグラフ106に単数または複数のヴェルテックスとエッジを発生できるデータベース、プログラム、またはアルゴリズムとして要約されるべきである。直列および並列データフローグラフのためのレプレゼンテーションに加えたパラレリゼイション方法の適切なレパートリーが与えられると、そのようなレパートリーアプリケーション方法の構成はルーティンプログラミングの問題となるべきである。
【００５３】
図８は並列処理方法のレパートリーを示す表900である。一般に、各並列処理方法は、適用テスト901、書換え規則902、および最適性の幾つかのノーション（例えば、並列処理方法が考慮されるオーダーによって表される）を有する。図８は以下でさらに詳しく述べられる。
【００５４】
多数の方法がレパートリーに含まれる計算を並列処理することで知られている。本発明は主として（独占的ではないが）（以下を）伴う技術の特定のファミリーの１つを利用した：
・入力データを多重ディスジョイン部分集合に分類する。これは“分割”と呼ばれる。そのような部分集合の各々は“分割”と呼ばれる。分割の多数のフォームが知られており、データが部分集合に分類される仕方で異なる。
・プログラムの多重インスタンスを作動させ、各インスタンスがデータの異なる分割を処理するように手配する。これは“分割された実行”と呼ばれる。
【００５５】
入力データが適当に分割できる場合、そのときは分割された実行は一般に性能上大きな改善を導くであろう。例えば、データが３０通りに分割される場合、そのときは処理ステップの各インスタンスはデータの３０分の１を処理し、したがって直列実行のもと要求されるであろう３０分の１の時間でその仕事を完了するべきである。分割のさらなる議論のため、本発明の譲受人に譲渡された98年10月６日発行の米国特許第5,819,021号、表題「OVERPARTITIONING SYSTEM AND METHOD FOR INCREASING CHECKPOINTS IN COMPONENT-BASED PARALLEL APPLICATIONS」を参照されたい。米国特許第5,819,021号の教示と内容はここで参照によって具体化される。
【００５６】
図９は、直列データフローグラフ104を並列処理するための好ましい方法を示すフローチャートである。方法は、その入力として、直列データフローグラフ 104を取り、好ましくはデータセット601、処理ステップ602、およびデータアクセス表603として表される。方法は、その出力として、並列データフローグラフ 106を生成し、好ましくは並列データセット表801、並列処理ステップ表802、および並列データアクセス表803として表される。図１０はイニシャル並列データセット、処理ステップ、およびデータアクセス表の例を示しているダイアグラムである。方法は以下のステップを含む：
・ステップ700：並列データセット表801、並列処理ステップ表802、および並列データアクセス表803をイニシャライズする。これは直列データセット表601、直列処理ステップ表602、および直列データアクセス表603に含まれる情報をコピーし、“分割”データ要素をイニシャライズすることによって行われる。ノーマル（直列）ファイル201、202、208に記憶されたデータセットのため、分割データ要素は、それらのファイルが並列でないことを意味する、“直列”にイニシャライズされる。さもなければ、分割データ要素は、並列処理の仕方がまだ確定されていないことを意味する、空欄のままになるであろう。
・ステップ701：システムはまだ処理されていない処理ステップを繰り返し探すであろう。これは空欄の“分割”データ要素を有するステップのため処理ステップ表802をスキャンすることによって行うことができる。
・ステップ707：全てのステップが並列処理されていない場合、そのときは分割競合解消アルゴリズムはデータが正しく分割されていることを保証するよう発動される。このアルゴリズムは以下で議論される。一度これが行われると、並列処理は完了する（ステップ708）。
・ステップ702：グラフが処理されていないステップを含む場合、そのときは１つのステップが（例えば、任意に）選択される。
・ステップ703：並列処理レパートリー表９００は次に、丁度選択されたステップに適用できる並列処理をロケイトするため、コンサルトされる。
・ステップ705：並列処理方法がロケイトされた場合、そのときはその書換え規則902は並列データセット表801、並列処理ステップ表802、および並列データアクセス表803の情報を変更するよう適用される。一度これが行われると、アルゴリズムは（ステップ701で）別の処理されていない要素を捜す。
・ステップ706：ロケイトされた並列処理方法がなかった場合、そのときはステップの“分割”方法は、ステップが直列で作動されねばならないことを示す、“直列”にセットされる。一度これが行われると、アルゴリズムは（ステップ701で）別の処理されていない要素を捜す。
【００５７】
ｂ．例
前記方法は以下の仕方で直列データフローグラフに適用することができる。上で述べたように、図１０はイニシャル並列データセット表、イニシャル処理ステップ表、およびイニシャルデータセットアクセス表の例である。図１１は並列処理の後で競合の解消の前の、図１０の並列データセット表、処理ステップ表、およびデータセットアクセス表を示すダイアグラムである（図６、図８、図９でも見ることができる）。
・ステップ700：イニシャライゼイション。
・並列データセット表801がイニシャライズされる。
・入力データセット201、202および出力データセット208が“直列”として記される。
・その他全ての情報が直列データセット表601から単純にコピーされる。
・直列処理ステップ表602のコンテンツは並列処理ステップ表802を生成するためコピーされる。
・直列データセットアクセス表603のコンテンツは並列データセットアクセス表803を生成するためコピーされる。
・ステップ701：未処理ステップ203（並列処理ステップ表802のアプリケーションステップ１）が選択される。
・ステップ703：並列処理レパートリー表900を参照することによって、CONCATENATE（“CONCAT”）操作903が“単純分割”によって並列処理できる。
・ステップ705：単純分割のための書換え規則は以下のアクション（図１１を見よ）を行う：
・処理ステップ203は“単純”分割が記されている。
・ステップの入力220、221とステップの出力222は単純分割されたデータにアクセスしているとして記されている。
・ステップ701：ループバックし、未処理の次のステップ205（並列処理ステップ表802のアプリケーションステップ２）が選択される。
・ステップ703：並列処理レパートリー表900を参照することによって、“AGGREGATE BY”操作906が“キーベース分割”によって並列処理できることを確定する。
・ステップ705：キーベース分割のための書換え規則は以下のアクション（図１１を見よ）を行う：
・処理ステップ205は“v2、v3によって”分割されたように記されている。
・ステップの入力223とステップの出力224は“v2、v3によって”分割されたように記されている。
・ステップ701：ループバックし、未処理の次のステップ207（並列処理ステップ表802のアプリケーションステップ３）が選択される。
・ステップ703：並列処理レパートリー表900を参照することによって、示されている並列処理方法がないことを確定する。
・ステップ706：従って、処理ステップは直列実行（図１１を見よ）が記されている。
・処理ステップ２０７のための分割方法は“直列”にセットされる。
・ステップの入力225とステップの出力226は“直列”として記されたそれらの分割方法を有する。
・ステップステップ701：ループバックし、もはや未処理ステップはロケイトされていない。
・ステップ707：競合を分割することは解決される（直後の議論を見よ）。この処理の結果は図１１のように示される。
【００５８】
ｃ．分割競合の解消
一度全ての処理ステップが直列として並列処理されるかまたはマークされるかのどちらかであると、分割競合は解決できる（図９のステップ707）。実施形態において、このアルゴリズムのスタート時に、全ての処理ステップは、“直列”、単純“または”キーによる“等の、分割方法がラベルされるだろう。類似して、全ての外部データセットは分割方法がラベルされるだろう。データセットアクセスも分割方法で記されるだろう。この点において、グラフは”分割競合“を含むことができる。例えば、データセットアクセスエントリとそれらがアクセスするデータセットとの間のミスマッチがしばしばあるだろう。例えば、図１１のアプリケーションステップ１は”単純“並列分割が記される入力220、221を有するが、それらがアクセスするデータセット201、202は”直列“として記される。もう１つの例として、一時的データセットは埋められるそれらの分割方法をまだ有することがない。
【００５９】
図１２は分割競合を解決するための好ましい方法を示しているフローチャートである（図９のステップ707）。
・ステップ1600：何らかの未処理ステップがグラフ内にあるかどうかを確定する。もしなければ、そのときはアルゴリズムが行われる（ステップ1601）。
・ステップ1602：全ての上流ステップが処理されているように処理ステップを選択する。
・ステップ1603：処理ステップが未処理である何らかのデータセットアクセスを有するかどうかを確定する。そのようなアクセスがない場合、そのときはステップは処理されたとして記され（ステップ1604）、アルゴリズムは処理するため次のステップを探す（ステップ1600で）。
・ステップ1605：現在の処理プロセスステップと関連する未処理データセットアクセスを選択する。
・ステップ1606：データセットアクセスの分割方法がデータセットの分割方法と整合するかどうかを確定する。実施形態において、以下の規則が適用される：
・データセットの分割方法が空欄の場合、そのときはミスマッチが存在する。
・データセットの分割方法が直列で、アクセスの方法が直列でない場合、そのときはミスマッチが存在する。
・データセットの分割方法が“単純”または“キーによる”で、アクセスの方法が直列の場合、そのときはミスマッチが存在する。
・データセットの分割方法が“単純”で、アクセスの方法が“キーによる”の場合、そのときはミスマッチが存在する。
・データセットの分割方法が“キーによる”で、アクセスの方法が“キーによる”であるが、キーが異なる場合、そのときはミスマッチが存在する。
・さもなければ分割方法は整合し、アクセスは処理されたとして記すことができ（ステップ1607）、アルゴリズムは別の未処理データセットアクセスを捜す（ステップ1603で）。
・ステップ1608：データセットの分割方法が空欄（これは一時的データセットにアクセスしているとき起こる）場合、そのとき、データセット分割方法は、データセットアクセスの分割（ステップ1609）と同様になるようにセットされ、その後アクセスは処理されたとしてマークされ（ステップ1607）アルゴリズムは別の未処理データセットアクセスを（ステップ1603）で捜す。
【００６０】
データセットの分割方法が空欄でない場合、そのときは分割競合をリペアするため（“アダプタ”と呼ばれる）単数または複数の付加的な処理ステップを挿入する必要がある。アダプタは１つのデータセットを読み込み幾つかの望ましい分割を有する第２のデータセットを生成する。さらにアダプタの議論は本発明の譲受人に譲渡された96年７月２日に発効された米国特許出願番号08/678,411、表題「EXECUTING COMPUTATIONS EXPRESSED AS GRAPHS」の中で述べられている。米国特許出願番号08/678,411の教示と内容はここで参照によって具体化される。
【００６１】
選択されたアダプタは出力データセットによって要求された分割に依存する：
・単純分割アダプタはパラレルデータセットを生成する。その入力は直列データセットであり、その出力は単純に分割されたデータセットである。
・ギャザーアダプタは直列データセットを生成する。その入力は分割されたデータセットであり、その出力は直列データセットである。
・ハッシュ分割アダプタはキーの幾つかのセットによって分割されたデータセットを生成する。望ましいキーはパラメータとしてハッシュ分割操作に渡される。その入力はあらゆる（直列、単純に分割された、またはキー分割された）データセットであり、その出力は特定されたキー上で分割されたデータセットである。
【００６２】
アダプタが挿入されたオーダーはデータアクセスのタイプに依存する。したがって、方法は以下のように続く：
・ステップ1610：データセットアクセスが処理されている処理ステップの入力（対出力）を表しているかどうかを確定する。
・ステップ1611：参照が入力に対する場合、そのときは一時的データセットによってフォローされるアダプタはソースデータセットと処理ステップとの間に挿入される。アダプタの分割はソースデータセットのそれと整合し、一方一時的データセットの分割はデータセットアクセスのそれと整合するだろう。
・ステップ1612：参照が出力に対する場合、そのときはアダプタによってフォローされる一時的データセットは処理ステップとディスティネーションデータセットとの間に挿入される。アダプタの分割はソースデータセットのそれと整合し、一方一時的データセットの分割はデータセットアクセスのそれと整合するだろう。
・一度アダプタと一時的データセットが挿入されていると、アクセスは“処理された”と記され（ステップ1607）アルゴリズムは別の未処理データセットアクセスを（ステップ1603で）捜すだろう。
【００６３】
ｄ．例
上記のように、図１１は並列処理後、競合解消の前の図１０の並列データセット表、並列処理ステップ表、並列データセットアクセス表を示す。図１３は並列処理ステップ表のアプリケーションステップ１の解消後の図１１を示しているダイアグラムである。図１４は並列処理ステップ表のアプリケーションステップ２の解消後の図１３を示すダイアグラムである。図１５は並列処理ステップ表のアプリケーションステップ３の解消後の図１４を示すダイアグラムである。図１２に示された方法のアプリケーションは結果として以下の処理ステップになる：
・ステップ1600、1602：アルゴリズムはアプリケーションステップ１（処理ステップ203）が処理されていない（図１１を見よ）ことを確定する。
・ステップ1603、1604：アルゴリズムはアプリケーションステップ１の第１入力220がまだ処理されていないことを確定する。
・ステップ1606：データセット201は“直列”と記され、アクセス220は“単純”と記され、それ故競合が存在する。
・ステップ1608：データセット201の分割は空欄がない。
・ステップ1610：データセットアクセス参照220は入力に参照を付ける。
・ステップ1611：全てのアダプタと一時的データセットは入力と処理ステップとの間に挿入される。
・単純分割アダプタアプリケーションステップ１ａが生成される（図１３を見よ）。上記のように、分割器は単純に分割されたデータセットを生成し、それは処理されているデータセットアクセス参照220によって要求された分割に整合する。
・分割器の分割は、入力201と整合するため、“直列”にセットされる。
・一時的データセット“テンプ３”212が生成される。一時的データセットの分割は、データセットアクセス参照220と整合するため、“並列”にセットされる。
・新しいデータセットアクセス参照227、228が入力201、アダプタ210、および一時的データセット212とリンクするため生成される。新しいデータセットアクセス参照227、228 の“分割”属性はそれらが（直列および単純、それぞれ）参照するデータセットと整合するためセットされる。
・現行のデータセットアクセス参照220は一時的データセット“テンプ３”212を引用するため再び目標にされる。
・ステップ1607：データセットアクセス参照220は処理されたと記される。
・ステップ1603、1604、1606、1608、1610、1611、1607：操作の同様のシリーズはステップ１によって参照される第２の入力データセット、すなわちindata2、のため繰り返される。これは結果として新しい分割アダプタアプリケーションステップ１ｂ211、一時的データセット“テンプ４”213、およびデータセットアクセス参照229、230の生成になる。
・ステップ1603、1604、1606：アルゴリズムはアプリケーションステップ１（処理ステップ203）の出力データセット参照222を処理する。
・ステップ1608：アクセスされているデータセットの分割、“テンプ１”204、は空欄である。
・ステップ1609：データセット“テンプ１”204の分割は“並列”にセットされ、データセットアクセス参照222の分割と整合する。
・ステップ1607： データセットアクセス参照222は“処理された”と記される。
・ステップ1603：アルゴリズムはアプリケーションステップ１（処理ステップ203）がもはや未処理アクセスを有しないことを確定する。
・ステップ1604：アルゴリズムはアプリケーションステップ１（処理ステップ203）を“処理された”と記す。
【００６４】
このときのグラフの状態は図１３に示される。アルゴリズムは以下のように継続する：
・ステップ1600、1602：アルゴリズムは次に処理のためアプリケーションステップ２（処理ステップ205）を選択する。
・ステップ1603、1605、1606、1608、1610：アルゴリズムは処理のためアプリケーションステップ２の入力223を選択し、一時的データセット“テンプ１”204と処理ステップ205との間にアダプタと一時的データセットを挿入する必要があることを確定する。
・ステップ1611：アダプタは、上記のように（図１４を見よ）、挿入される。このとき、データセットアクセス223が“v2、v3による”分割“を特定するので、”アダプタが選択される。これは結果としてアダプタアプリケーションステップ２ａ211、一時的データセット“テンプ５”215、および２つのデータセット参照231、232の生成になる。
・ステップ1607、1603、1605、1606、1608：アルゴリズムは処理のためアプリケーションステップ２の出力224を選択し、アウトプトの分割方法が空欄であることを確定する。
・ステップ1609：アルゴリズムは分割方法を“v2、v3によって”データセットアクセス参照224から一時的データセット“テンプ２”206にプロパゲイトする。
・ステップ1607、1603、1604：アルゴリズムはアプリケーションステップ２上で仕事を終える。
【００６５】
このときのグラフの状態は図１４に示される。アルゴリズムは以下のように継続する：
・ステップ1600、1602：アルゴリズムは処理のためアプリケーションステップ３（処理ステップ207）を選択する。
・ステップ1603、1605、1606、1608、1610：アルゴリズムは処理のためアプリケーションステップ３の入力225を選択し、一時的データセット“テンプ２”206と処理ステップ207との間にアダプタと一時的データセットを挿入する必要があることを確定する。
・ステップ1611：アダプタは、上記のように（図１５を見よ）、挿入される。このとき、データセットアクセス参照225が“直列”分割“を特定するので、”ギャザー”アダプタが選択される。これは結果としてアダプタアプリケーションステップ３ａ216、一時的データセット“テンプ６”217、および２つのデータセット参照233、234の生成になる。
・ステップ1607、1603、1605、1606：アルゴリズムは処理のためアプリケーションステップ３の出力226を選択し、データセットアクセス参照226のための分割が出力データセット“outdata”208の分割と整合することを確定する。
・ステップ1607、1603、1604：アルゴリズムはアプリケーションステップ３の出力226を“処理された”と記し、アプリケーションステップ３がさらなるデータセットアクセスを有しないことを確定する。
・ステップ1600、1601：アルゴリズムは未処理の処理ステップが存在しないことを確定し、終了する。
いまや完全に並列処理された、グラフの最終状態は、図１５に示されておリ、これは並列処理されたデータフローグラフ106を構成する。
【００６６】
４．ステップ107−スクリプト断片の生成
多くの場合、オリジナルスクリプト駆動ツール６を用いて、処理ステップを実行することは可能である。これを実行するための発明の具体例として、スクリプト断片４を、そのような処理ステップに対して、任意に生成することが可能である。図１６は、スクリプト断片を生成するための好ましい方法を示すフローチャートである。
・ステップ2001：システムは、全ステップが終了したかどうかを確認する。そうであれば,アルゴリズムは終了する。
・ステップ2002：システムは、未処理ステップを選択する。
・ステップ2003：ステップがオリジナルツール６により実行されない場合、処理された時（ステップ2009）、それが表示される。そしてアルゴリズム（ステップ2001）を繰り返す。各処理ステップが、オリジナルツール６により実行されるためには、下記の動作が必要となる。
・ステップ2004：いかなる入力に対しても、宣言は生成される。宣言により、実行時に利用可能な情報を参照することができる。例えば、宣言により、コマンドライン引数を参照することができる。
・ステップ2005：処理ステップ自体のテキストが生成される。多くの場合、処理ステップのテキストはオリジナルスクリプト１のものと、同一である。
・ステップ2006：いかなる出力に対しても、宣言は生成される。宣言により、実行時に利用可能な情報を参照することができる。例えば、宣言により、コマンドライン引数を参照することができる。
・ステップ2007：入力宣言、処理ステップ、出力宣言がファイルに書き込まれる。このファイルは、“スクリプト断片”４と呼ばれ、一般にオリジナルスクリプトの１断片を含む。図１７に、数スクリプトを含む、スクリプト断片ファイルの１例を示す。
・ステップ2008：並列処理ステップ表802は、スクリプトを参照するために、修正される。なおステップは、スクリプト駆動ツール６を呼び出すことにより、実行されることに注意する。
・ステップ2009：カレントステップが処理された時、表示される。そしてアルゴリズム（ステップ2001）を繰り返す。
【００６７】
例えば、図１５に示すアプリケーションは、スクリプトの生成に必要な３処理ステップ203、205、207を含む。図１７に示す結果は、３スクリプト断片2101、2101、2103から成る。
・１番目のスクリプト断片2101、スクリプト1は、１番目の処理ステップ203に対応する。そして２入力データセット（インデータ１とインデータ２）と１出力データセット（アウトデータ）と１処理ステップ（CONCATENATE操作）を宣言する。データセットにより使用されるファイル名は、コマンドライン（図１５に登録のパラメータを参照）から得られる。
・２番目のスクリプト断片2102、スクリプト２は、２番目の処理ステップ205に対応し、１入力と出力（インデータ、アウトデータ）および１処理ステップ（AGGREGATE操作）を宣言する。データセットで使用されるファイル名は一般に、コマンドラインから得られる。
・3番目のスクリプト断片2103、スクリプト３は、３番目の処理ステップ207に対応し、１入力と出力（インデータ、アウトデータ）および１処理ステップ（解析オペレーション）を宣言する。データセットで使用されるファイル名は一般に、コマンドラインから得られる。
【００６８】
スクリプトと解析アプリケーションのリファレンスは、並列処理ステップ表802に挿入される。図１８は、図１５にスクリプト断片生成後の図である。この段階で，並列処理ステップ表802は、並列インフラストラクチャが直ぐに実行できる構成要素で完全に構成されている、ことに注意する。
【００６９】
５．ステップ108−並列計算仕様の生成
具体例で、並列データフローグラフ106は、米国特許出願第08/678,411号の技法を使用し、直ぐに実行されることが可能である。しかし、並列計算仕様を生成して、並列データセット、処理ステップ、およびデータセットアクセス表の全データセットと並列処理オペレーションを結合させて、１ファイルにすることは、一般に有効である。このようなファイルの１形式は、テキストファイルとすることが可能である。これは、テキストファイルの入力に適応するランタイムシステムを使用する場合には、有利である。従って、好ましい具体例で、２を解析するスクリプトの最終ステップは、このような並列計算仕様の108を生成する。
【００７０】
図１９は、並列計算仕様を生成する１方法のフローチャートである。よい具体例では、このアルゴリズムは下記のとおり進行する。
・ステップ2301：システムは、各一時的データセットに対して仕様を生成する。例えば、各一時的データセットを格納するために使用されるファイル名のリストを生成することにより、実行されることが可能であった。並列データセットに対して，ファイルの一定数ｎが生成された。これに対し、シングルファイルは、シリアルファイルに明記された。
・ステップ2302：未処理ステップが残る場合、その処理が実行される。
・ステップ2303：他の方法では、それまでの処理ステップがすでに処理されているので、アルゴリズムが次の未処理の処理ステップを選択する。
・ステップ2304：システムは並列コマンドを生成し、指定の処理ステップを実行する。
・ステップ2305：カレント処理ステップは、処理されると、表示される。アルゴリズムは、いかなる未処理ステップ（ステップ2302）をもテストするためにループ化する。
【００７１】
図２０は、一時的データセットの生成を示す図である。２一時的ファイルリストが、各並列一時的データセット204、206、212、213、215に対して生成されている。また、シングル一時的ファイルは、各シリアル一時的データセット217に対して生成されている
【００７２】
図２１は、最終並列計算仕様３を示す図である。図２０の並列処理ステップ表802の各処理ステップは、実例の並列ランタイムシステム（すなわち、実行、単純区分，ハッシュ区分、ギャザー）でサポートされた４ステートメントの１例のようにコード化されている。図２０のデータセットアクセスリファレンス表803の各リファレンスは、コマンドラインでデータセットファイル名のリストを含めて明記されている。
【００７３】
並列計算仕様３に、スクリプト断片４を加えると、並列ランタイムシステム５により実行される。これはオリジナルソフトウエアツール６および、あるいは補足プログラム７を並列に実行させるものである。結果として生じるプロセス６、７は、オリジナルスクリプト１で明記されたのと同一の計算を実行するが、全体のスループットは非常に向上する。
【００７４】
並列処理方式の例
この章では、並列処理レパ−トリ表あるいはデータベース900（図８）の定義に使用される並列処理方式の数例を簡潔に解説する。
【００７５】
１．単純区分による並列処理
多くの場合、処理ステップを並列処理することは可能である。これを行うには、データを区分した後、各区分で処理ステップの１インスタンスを実行することである。これが一般的に有用であるのは、（１）オペレーションが各レコードで実行される場合、(２)あるレコードで実行されているオペレーションが、他のレコードで実行されているオペレーションとは、無関係である場合。本発明で用いられているように、この技術は“単純区分”と呼ばれる。いかなる区分方式も使用されることは，可能であるが、なるべくほぼ等しい量のデータが各区分に存在する方式を使用する。
【００７６】
前述の仮定解析アプリケーションで、CONCATENATE操作と印刷オペレーションは、単純区分（図８の並列処理規則903）により並列処理されることは可能である。図２２のデータフローダイアグラムは、印刷オペレーションを並列処理している１例である。シリアルバージョン1001のオペレーションでは、シリアルデータセット1003が印刷処理ステップ1004により処理されると、出力データセット1005を生成する。印刷オペレーションの並列バージョン1002では、入力データセット1003が分割され、Ｎ区分1006になる。次に印刷オペレーション1007のＮインスタンスが実行され、各々が入力データ区分1006をアクセスする。結果は、Ｎ出力データセット1008に書き込まれる。出力データセット1008は、シリアルバージョンプログラムにより生成された出力1005を、分割表示したもので構成することに注意する。
【００７７】
よい具体例で、単純区分に対する改訂規則902は、“前”オペレーション1020とその入力1021と出力1022よりも太い線を用いることにより、“後”のデータフローシンボルを生成する。
【００７８】
２．キーべース区分による並列処理
多数のオペレーションは、“キーフィールド”をベースにする１あるいはそれ以上の入力データを区分することにより、並列処理されることが可能である。これが一般に有用である事例は、（１）あるオペレーションがキーの共有値を共有しながら、一連のレコードで実行される場合、（２）このようなある一連のレコードで実行されるオペレーションは、一連の異なるレコードで実行されるオペレーションとは無関係である。
【００７９】
本発明で使用されように、この技術は“キーベース区分”と呼ばれる。キーベース区分は、データが分割されて区分になることが、必要である。２レコードｒ１とｒ２が、キーＫと同一値をもつ場合、同一区分に入れられることになる。例えば、下記事項により達成されることが可能である。
・ハッシュ機能を定義すること。すなわち数値機能ｆがキー値Ｖに適用されると、0＜ｈ＜＝Ｎ（Ｎは，区分番号）などの値ｈを生成する。
・ハッシュ機能ｆを入力データセットの各レコードに適用すること、およびそれらのレコードを、ｈの値に従って正確な区分に導くこと。
【００８０】
仮定の解析アプリケーションで、AGGREGATE操作と解析オペレーションは、“BY”節を組み込むことも可能である。このような場合、キーベース区分（図８の並列処理規則904を参照）を使用して、並列処理されることが可能である。図２３のデータフローダイアグラムは、AGGREGATE操作オペレーションを並列処理する例を示すものである。シリアルバージョン1101では、シリアルデータセット1103が、BY節を含むAGGREGATE操作処理ステップ1104で処理され、出力データセット1105を生成することが可能である。AGGREGATE操作オペレーションの並列処理バージョン1102では、入力データセット1103がハッシュ機能を用いることにより、Ｎ区分1106に分割される。次に、AGGREGATE操作オペレーション1107のＮインスタンスが実行され、各々が入力データの１区分1106をアクセスしている。その結果は、次に、Ｎ出力データセット1108に述べられる。出力データセット1108は、シリアルバージョンのプログラムにより生成された出力1105のキー区分表示から成ることに注意する。
【００８１】
よい具体例で、キーベース区分方法の改訂規則902は、“前”処理ステップ1120とその入力と出力1121、1122に“キーにより区分された”と表示をつけることである。これは、“後”のデータフローグラフのシンボルと表記に、キーと同一の太い線を用いることにより図で示される。
【００８２】
３．区分データファイルのアクセス
並列処理の利点は、計算が決して制限されないことである。特に、並列処理は、データに対するアクセスを非常にスピードアップさせるための能力を備える。例えば、シングルストレージデバイスは、５メガバイト／秒の速度でデータを転送することが可能である。次に、そのようなデバイスを10集めると、50メガバイト／秒の速度でデータを転送することが可能となる。この理由により、マルチプルストレージデバイスでデータを区分することは、有益である。
【００８３】
図２４のブロックダイアグラムは、区分データセットを格納する１方法を示すものである。この方法は、データセット中の複数ファイル中のレコードを分割し、なるべく各ファイルが異なるディスク上で格納されるように配置している。この方法は、シリアルファイルで用いられる方法と比較すると、最もよく理解されることが可能である。シリアルケース1200では、シングルファイル1201は一連のレコード1202を格納するために使用される。このデータセットは、シングルファイル名1203で参照される。区分データセット1204では、数ファイル1205が使用される。各ファイルは、データセット1206の１区分を格納する。この場合、一連ファイル名1207がデータセットを参照するために使用することが可能である。この系列はなるべく、リスト内の個々のファイルを区分するために、１列に区切り符号（例、１セミコロン）を用いて表示されることが可能である。
【００８４】
米国特許出願第08/876,734号で許可され、本発明の指定代理人を任命し、1997年6月16日に正式提出された、名称“A PARALLEL VIRTUAL FILE SYSTEM“（これによる開示内容は、参考資料として本明細書中に含まれる）では、ファイルセットの管理に対する改良方法を述べる。この方法1208で、“管理ファイル”1209は、区分データセット1206から成るデータファイル1205の名称1210を格納するために使用することができる。区分データセット1206は次に、管理ファイルを呼び出すシングルファイル名1211を使用すると、参照することができる。
【００８５】
区分データセットに対するサポートには、並列処理方式レパ―トリ表900中のエントリ905が必要となる。このレパ―トリ表には、適用範囲テスト901が含まれる。このテストは、データセットに含まれるファイル名を調べて、それが区分データセットを呼び出すかどうかを確認する。対応する改訂規則902は、データセットの区分モードを、例えば、“単純”あるいは、同様の表記に設定する。
この方式は、並列アプリケーションが、区分データファイルをアクセスすることができるオリジナルツール6の機能性を、僅かに拡張している点が例外的である。
【００８６】
４．ローカル-グローバル除算による並列処理
処理ステップの中には、入力データベースの全内容に基づいて計算された出力値を生成するものがある。例えば、仮定の解析アプリケーションでは、AGGREGATE操作ステートメント（BY節を使用しない）が呼び出されると、全入力データセットで使用された、あるフィールドの最大値を検索する。多くの場合、入力データの区分、各区分の“ローカル結果”の計算、数“ローカル結果”の組み合わせを行うと、このようなデータセット全体の計算を実行することが可能となる。ほとんどの場合、“グローバルコンビネーション”ステップで実行される非並列ワークの量は、“ローカル計算”ステップで実行される並列ワークに比較すると、非常に少ない。むしろ“ローカル”と“グローバル”ステップは、オリジナルソフトウエアツール6で実行されることになる。しかし、必要であれば、１あるいは両ステップが、新しい特殊目的コードで実行される場合がある。
【００８７】
この並列処理の方式は、“ローカル-グローバル除算”と呼ばれる。ローカルとグローバルステージで実行される正確な計算は、並列処理されている処理ステップ次第である。仮定の解析アプリケーションのAGGREGATE操作オペレーションの場合、ローカルステージは、オリジナルスクリプト１で指定されるローカルAGGREGATE操作の計算から成る。次に、同一の全AGGREGATE操作オペレーションを、ローカルAGGREGATE操作の結果に加える。図２５は、ローカルグローバル並列処理のデータフローダイアグラムである。シリアルオペレーション1300では、シリアルデータセット1301から開始できる。次に、AGGREGATE操作オペレーション1302は、１フィールドの最小値と、他の1303の最大値を検索する。このオペレーション1304の並列バージョンは、入力を区分1305に分割する必要がある。次に、AGGREGATE操作オペレーション1306の１インスタンスを各区分に加えている。これにより、各区分内に、2フイールド1307の最小値と最大値が生じる。これらのローカル結果は次に、グローバルAGGREGATE操作ステップ1308に送られ、全データセット1309で最小値／最大値を計算する。
【００８８】
好適な具体例として、ローカル-グローバル除算906に対する改訂規則902は、下記事項からなる。
・オリジナルオペレーション1320を、ローカルオペレーション1323、一時的中間データセット1324、グローバルオペレーション1325と入れ替えること。
・ローカルオペレーションと中間データセット1326との間、および中間データセットとグローバルオペレーション1327との間に、データセットアクセスを加えること。
・ローカルオペレーション1323と中間データセット1324を太い線を用いて、“区分”と表示する。
・グローバルオペレーション1325を細い線を用いて続きのように表示すること。
・太い線を用いて、アクセスリファレンス1326、1327を区分されたように中間データセットとダイアグラムで表示する。
・オリジナルオペレーション1320に対する入力1321をローカルステージ1323に結び付け、太い線を用いて、区分1328とダイアグラムで表示する。
・オリジナルオペレーション1320の出力1322を、グローバルステージ1325と結び付け、細い線を用いて、続き1329とダイアグラムで表示する。
【００８９】
５．外部パラレリズム−補足プログラム
オリジナルソフトウエアツール6を用いて、処理ステップを並列処理できない場合がある。このような場合、ステップの“外部並列”インプリメンテーションを採用することが、可能な場合がある。外部並列インプリメンテーションは、補足プログラムであり、オリジナルアプリケーションの機能性を、ある程度まで反復する。これにより、並列処理されることが可能となる。外部並行処理ルーチンのインプリメンテーションは、並列処理されているオペレーションの特性次第である。この章では、このような外部ルーチンが、アプリケーションの並列バージョンに組み込まれる一般的方法を解説する。
【００９０】
例えば、仮定の解析アプリケーションには、並列処理されることができない、“データベースアンロード”オペレーションを含む。例えば、アンロードされているデータベース表を区分している場合である（それを実行するには、データベース表に許容できない修正が必要となる）。
【００９１】
しかし、これは“外部パラレリズムデータベースアンロード“プログラムを供給することにより、並列処理されることができる場合がある。図２６は、外部パラレリズムの１例を示すデータフローダイアグラムである。オリジナルシリアルアプリケーション1400は、”イントリンシックアンロード“ルーチン1402を使用してアクセスされるために、データベース表1401を呼び出す。ルーチン1402が一連のデータレコード1403にアクセスすることを可能としている。並列インプリメンテーション1404は、同一のデータベース表1401を使用し、共にデータベース表をスキャンするために、”外部アンロード“プログラム1405の数インスタンスを使用する。すなわち各プログラムは、オリジナル表の区分1406を生成する。
【００９２】
好適な具体例として、外部パラレリズム907、908に対する改訂規則902は、下記事項から成る。
・オリジナルオペレーション1420を、外部並列ルーチン1423と入れ替えること。
・大抵の場合、分割された実行に対する外部並列ルーチン1423に、太い線のダイアグラムを書くこと。
・大抵の場合、入力1421と出力1422および対応する区分データアクセスリファレンス1424、1425に太い線のダイアグラムを書くこと。
【００９３】
６．ステートメント分解による並列処理
オリジナルソフトウエアツール6を使用して、処理ステップの並列処理ができない場合や、ステップの並列処理をするために、外部パラレリズムを使用することが望ましくない場合や不可能な場合がある。このような場合、ステートメント分解により処理ステップを並列処理することが可能となる。ステートメント分解が使用されると、処理ステップは，複数の独立したタスクを実行する。この場合、処理ステップは、ステップのオリジナルタスクを別々のタスクに分解し、各タスクが別のステップで処理されると、並列処理されることが可能である。この後、各新ステップは、同時に処理されオリジナルステップの並列実行を有効に遂行する。次に、分離されたステップの結果は、互いに連結され、一連の出力を生成する。
【００９４】
図２７は、ステートメント分解の例を示すデータフローダイアグラムである。好適な具体例では、ステートメント分解による並列処理の改訂規則は、下記事項から成る。
・オリジナルオペレーション1702を分解されたオペレーション1704、一時的中間データセット1705、フィールド連結オペレーション1706の組み合わせと入れ替えること。フィールド組み合わせオペレーション1706は、一時的中間データセット1705のレコードのフィールドを組み合わせる。
・分解されたオペレーションと中間データセットとの間、および中間データセットと組み合わせオペレーションとの間にそれぞれ、データセットアクセス1707、1708を加えること。
・分解されたオペレーション1704と中間データセット1705を“区分”として太い線でダイアグラムを書くこと。
・組み合わせオペレーション1706を細い線で続きの表示をつけること。
・アクセス1707、1708を中間データセットに、太いダイアグラムを用いて書く。
・オリジナルオペレーション1702の入力1701を分解されたオペレーション1704に結び付け、区分1709を太いダイアグラムで書く。
・オリジナルオペレーション1702の出力1703を組み合わせオペレーション1706に結び付け、それらを細い線でシリアル1710と表示をつける。
【００９５】
SAS特定の改訂規則
発明は一般に各種スクリプト言語に適応可能であるが、下記に、発明が特にSAS言語に適応可能である理由を、数例を用いて説明する。技術の中の通常の１技能は、原理と例をここで利用することができることが必要であり、本発明で用いるためには、SASの他の見地に適応することである。
【００９６】
１．PROC MEANS改訂規則−ローカル-グローバル除算の例
SASシステムは、MEANS手順を含み、この手順は、例えば、単純もしくはキーベース区分により並列処理できるとはかぎらない。しかし、MEANS手順は一般に、ローカル-グローバル除算改訂規則を適用させることにより、並列処理されることが可能である。図２８は、データフローダイアグラムであり、シリアルSASスクリプトがMEANS手順1505を用いて、データセット1501で記述統計法を計算し、出力ファイル1502を生成する例を示すものである。並列インプリメンテーションは、同一データセット1501を必要とし、単純区分を用いて、区分データセット1504を生成する。次に、SASMEANS手順1505の数インスタンスを用いて、データセット1506の最小値、最大値、総計、合計、平方値の合計に対するローカル値を生成する。外部統計マージングアプリケーション1507のシングルインスタンスは、ローカル値を結合して、全結果1502を生成する。ローカル値1506をマージして、全結果1502を生成するために必要なアルゴリズムは、技術中で熟知されている。
【００９７】
２．PROC FREQ改訂規則−ローカル-グローバル除算の例
SASシステムは、FREQ（frequency）手順を含み、この手順は、例えば単純もしくはキーベース区分により並列処理できるとはかぎらない。しかしFREQ手順は、一般にローカル-グローバル除算改訂規則を適用されることにより、並列処理されることが可能である。図２９は、データフローダイアグラムであり、シリアルSASスクリプトが手順1605を用いて、データセット1601で表駆動統計を計算し、出力ファイル1602を生成する例を示す。並列インプリメンテーションは、同一データセット1601を必要とし、単純区分を用いて、区分データセット1604を生成する。次に、SASFREQ手順1605の数インスタンスを用いて、データセット1606に対するローカル周波数表を生成する。シングルインスタンスFREQ手順1607は、ローカル値を結合して、全結果1602を生成する。（SAS本具体例の言語仕様に対応するために、シングルFREQインスタンス1607が、SASステートメント“WEIGHT COUNT”を含む必要があるのは、局部的結果1606を正確にマージするためである）
【００９８】
３．PROC UNIVARIATE改訂規則−ステートメント分解の例
SASシステムは、UNIVARIATE手順を含み、この手順は、例えば単純もしくはキーベース区分により並列処理できない。UNIVARIATE手順は一般に、ステートメント分解改訂規則を適用させることにより、並列処理されることが可能である。図３０は、データフローダイアグラムであり、シリアルSASスクリプトがUNIVARIATE手順1805を用いて、データセット1801でUNIVARIATE統計を計算し、出力ファイル1802を生成する例を示すものである。並列インプリメンテーションは、同一データセット1801を必要とし、カラム区分を用いて、区分データセット1804を生成する。次に、SASUNIVARIATE手順1805の数インスタンスを使用する。各インスタンスは、各変数（カラム区分）に対するUNIVARIATE統計を生成し、ローカルデータセット1806を生成している。シングル連結ステップは次に，ローカルUNIVARIATEデータセット1806を結合して、全結果1802を生成する。
【００９９】
４．データステップ改訂規則−単純区分もしくはキーベース区分の例
SASシステムは、“データステップ”と呼ばれる手続き上のステップを含む。一般に、SASプログラムは一連のデータステップとSAS手続きで構成される。SASデータステップは、仮定の解析アプリケーションのスクリプト言語のAGGREGATE操作ステートメントと同様のシングルあるいはグループ化されたレコードオペレーションを実行することができる。SASデータステップが入力および出力に対するSASデ―タセットを使用し、BYステートメントを含んでいない場合、単純区分が並列でデータステップを計算するために使用することができる。SASデータステップが、入力および出力に対するSASデータセットを使用し、BYステートメントを含む場合、キーベース区分による並列処理が並列でデータステップを計算されるために使用されることができる。このような後者の場合、SASBYステートメントで指定されたキーは、ハッシュ区分オペレーションで，キーとして用いられる。
【０１００】
５．SASスクリプト断片
下記は、SAS1プログラムと分割される予定の断片の例である。これら断片は、適用されている特定の改訂規則の構成内で適合するために、修正される必要があることに注意すること。その上、一時的データセットに対するリファレンス（下記の各所に記載されている。すなわちデータセット名で、libnameステートメントより接頭語のないものである）は、改訂規則により生成されている、シリアルあるいは並列データセットの適切なリファレンスと入れ替えられる必要がある。
libname ext “.”;
data one;
set ext.customer;
by region;
age = today()-birthdt;
proc means data=one;
var age;
proc freq data=one;
tables age*region;
proc univariate data=one;
var age income numkids;
Fragment 1:
libname ext “.”;
data parallel.one;
set ext.customer;
by region;
age = today()-birthdt;
Fragment 2:
proc means data=parallel.one;
var age;
Fragment 3:
proc freq data=one;
tables age*region;
Fragment 4:
proc univariate data=one;
var age income numkids;
【０１０１】
６．マクロとプリプロセッサ
SAS言語を用いると、ユーザは便宜上“マクロ”（コマンドの集まり）を生成し、使用することが可能となる。しかし、マクロは、基礎をなすSASコマンドを“隠す”ものである。発明の実用的具体例をSASスクリプトに容易に適用させるために、全マクロを展開させて、元の基礎をなすコマンドを露出させる必要がある。SASシステムの本具体例は、特にマクロ展開のためのツールを提供していないので、代替の方法が使用される。例えば１具体例では、マクロ展開の方式は、元のSASプログラムを、構文チェックモードで実行することにより、得られる。SASの本具体例は、この機能によりログファイルを生成する。この機能は、本質的には展開された形態の基礎をなすSAS全コマンドを含むものである。ログファイルを読み取り解析することにより、SASバージョン“未処理”コードは、本発明のアナライザ2により、得ることおよび処理されることができる。（ログファイルは、それ自体法定のSASコードではなく、不正のないプロセスで、リーガルコマンドに写像され、解釈されなければならない。
【０１０２】
マクロの展開方法を得るための代替の方法は、SASマクロ言語によりマクロプリプロセッサを書くことである。それらを書くためのプリプロセッサと方法は、技術の中でよく知られている。
【０１０３】
７．大域的SASデータ
SASシステムは、主な2記憶領域で大域的データを生成し、参照する。すなわちマクロ変数とフォーマットである。どちらの場合も、このような大域的データの生成と参照は、SASパースツリーの検査により、見つけられることが可能である。例えば、図６および図７の参照として、SASステップによる大域的データの生成は、ステートメントが501をスキャンされている間に、見つけられる。そのようなリファレンスはいかなるものも、大域的データエントリがデータセット表601で生成される原因となる。さらにSASステップによる大域的データのリファレンスは、データセットアクセス表603が、ステップ505で生成されている時に、見つけて示される。この方法で、いかなるマクロ変数あるいはSASフォーマットも生成され、それらを必要とする後のSASステップに提供される。
【０１０４】
コンピュータの実例
発明は、ハードウエアおよびソフトウエア、あるいは両者の組み合わせに採用されることができる。他の方法が指定されていない場合、発明の１部に含まれるアルゴリズムは本来、特定のコンピュータや他の装置に関係をもたない特に、各種汎用機械は、この文章中の教えに従って書かれたプログラムで使用されることができる。あるいは、必要な方法を実行するために、専用装置を組み立てることが都合の良い場合がある。しかし、なるべくなら発明は、１もしくはそれ以上のコンピュータプログラムを実行している、プログラム可能なシステム上で、各々少なくとも１データストレージシステム（摘発性および不摘発性記憶装置および、もしくは記憶素子を含む）、少なくとも１入力装置、少なくとも１出力装置で構成する装置で実行される。プログラムコードは、入力データに適用され、この文章で記述される機能を実行し、出力情報を生成する。出力情報は、既知の方法で１あるいはそれ以上の出力装置に振り当てられる。
【０１０５】
このようなプログラムは、コンピュータシステムと通信するために、目的のコンピュータ言語（機械語、アセンブリ語、高水準手続き言語、あるいはオブジェクト指向プログラム言語）で実行される。いずれの場合も、言語はコンパイルされる。すなわち解釈される。
【０１０６】
このような各コンピュータプログラムは、汎用あるいは特殊目的のプログラム可能なコンピュータにより読み取られ、なるべく記憶媒体あるいは装置（例えば、ROM、CD−ROM、あるいは磁気、光学媒体）に格納される。記憶媒体や装置は、記述されている手続きを実行するために、コンヒュ―タにより読み出され、コンピュータを機能させている。革新的なシステムは、コンピュータプログラムで環境設定されている、コンピュータ読み取り可能、記憶媒体で実装されることであると、考えられる。そのように環境設定された記憶媒体は、コンピュータがここに述べた機能を実行するために、特定の定義済み動作を実行させる。
【０１０７】
本発明の多数の具体例を説明した。それでも、発明の意図と範囲から逸脱しないように、各種修正がされるのは、推察できることである。例えば、ステップはさまざまな手順で実行され、同一の結果を達成する。従って、他の実例は、次の請求時である。
【図面の簡単な説明】
【０１０８】
【図１】本発明の好ましい実施形態のデータフロー図である。
【図２】自動的にイニシャルスクリプトを解析しスクリプト断片を加えた並列計算の仕様を生成するための好ましい方法を示すデータフロー図である。
【図３】グラフ形状の直列データフローグラフの例である。
【図４】グラフ形状の並列データフローグラフの例である。
【図５】イニシャルスクリプトとそれが含むステートメントのシーケンスのレプリゼンテーションとの例を示す。
【図６】データセット表、処理ステップ表、データセットアクセス表の例を示すダイアグラムである。
【図７】ステップのシーケンスを直列データフローグラフの中へ変換する例を示すフローチャートである。
【図８】並列処理方法のレパートリーを示す表である。
【図９】直列データフローグラフを並列処理するための好ましい方法を示すフローチャートである。
【図１０】イニシャル並列データセット表、イニシャル処理ステップ表、イニシャルデータアクセス表の例を示すダイアグラムである。
【図１１】並列処理後、競合解消前の、図１０の並列データセット表、並列処理ステップ表、並列データアクセス表を示すダイアグラムである。
【図１２】分割競合を解決するための好ましい方法を示すフローチャートである。
【図１３】並列処理ステップ表のアプリケーションステップ１解消後の図１１を示すダイアグラムである。
【図１４】並列処理ステップ表のアプリケーションステップ２解消後の図１３を示すダイアグラムである。
【図１５】並列処理ステップ表のアプリケーションステップ３解消後の図１４を示すダイアグラムである。
【図１６】スクリプト断片を発生するための好ましい方法を示すフローチャートである。
【図１７】幾つかのスクリプトを含むスクリプト断片ファイルの例を示している。
【図１８】スクリプト断片発生後の図１５を示すダイアグラムである。
【図１９】並列計算仕様を発生するための１つの方法のフローチャートである。
【図２０】一時的データセットの発生を示すダイアグラムである。
【図２１】最終並列計算仕様３を示すダイアグラムである。
【図２２】COPYオペレーションを並列処理する例を示すデータフロー図である。
【図２３】AGGREGATEオペレーションを並列処理する例を示すデータフロー図である。
【図２４】分割されたデータセットを記憶するための１つの方法を示すブロック図である。
【図２５】ローカル−グローバル並列処理のデータフロー図である。
【図２６】外部パラレリズムの例を示すデータフロー図である。
【図２７】ステートメント分解の例を示すデータフロー図である。
【図２８】データセット上の記述統計学を算出し出力ファイルを生成するためMEANS手続きを使用する直列SASスクリプトの例を示すデータフロー図である。
【図２９】データセット上の表駆動統計学を算出し出力ファイルを生成するためFREQ手続きを使用する直列SASスクリプトの例を示すデータフロー図である。
【図３０】データセット上の単変量統計学を算出し出力ファイルを生成するためUNIVARIATE手続きを使用する直列SASスクリプトの例を示すデータフロー図である。
【図１】
2006236360.tif 000003
【図２】
2006236360.tif 000004
【図３】
2006236360.tif 000005
【図４】
2006236360.tif 000006
【図５】
2006236360.tif 000007
【図６】
2006236360.tif 000008
【図７】
2006236360.tif 000009
【図８】
2006236360.tif 000010
【図９】
2006236360.tif 000011
【図１０】
2006236360.tif 000012
【図１１】
2006236360.tif 000013
【図１２】
2006236360.tif 000014
【図１３】
2006236360.tif 000015
【図１４】
2006236360.tif 000016
【図１５】
2006236360.tif 000017
【図１６】
2006236360.tif 000018
【図１７】
2006236360.tif 000019
【図１８】
2006236360.tif 000020
【図１９】
2006236360.tif 000021
【図２０】
2006236360.tif 000022
【図２１】
2006236360.tif 000023
【図２２】
2006236360.tif 000024
【図２３】
2006236360.tif 000025
【図２４】
2006236360.tif 000026
【図２５】
2006236360.tif 000027
【図２６】
2006236360.tif 000028
【図２７】
2006236360.tif 000029
【図２８】
2006236360.tif 000030
【図２９】
2006236360.tif 000031
【図３０】
2006236360.tif 000032