(57)【要約】【課題】ループ飛び出しがあっても計算機処理をより短時間で実行することにある。【解決手段】計算機装置１は、指示文解析部３０を用いて入出力装置６から入力された入力プログラム１０から直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出し、ループ解析部４０を用いて入力ループを解析して解析結果を変換候補ループテーブル１６に格納し、ループ変換部５０を用いて変換候補ループテーブル１６に格納された解析結果を利用して入力ループを出力ループに変換した出力プログラム１２を入出力装置６に出力する。【選択図】図１
2019219992.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも主記憶装置を有しプログラムを実行することにより情報を処理する計算機装置と、前記計算機装置に対する入出力を行う入出力装置とを備えた計算機システムであって、
前記主記憶装置は、
指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、
変換候補ループテーブルと、を有し、
前記計算機装置は、
前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出し、
前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを前記入出力装置に出力することを特徴とする計算機システム。
【請求項２】
前記計算機装置は、
前記ループ解析部を用いて、前記解析結果として、前記入力ループの入力実行コストと前記出力ループの出力実行コストの比較結果を前記変換候補ループテーブルに格納することを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記計算機装置は、
前記指示文解析部を用いて、前記入力プログラムを解析して前記入力ループを抽出し、抽出した前記入力ループを変換候補ループとして前記変換候補ループテーブルに格納し、
前記ループ解析部を用いて、前記変換候補ループテーブルに格納された前記入力ループを解析し、前記入力ループの構造がループ飛び出し処理を持つループ飛び出しループであり、かつ前記出力ループの前記出力実行コストが前記入力ループの前記入力実行コストより小さい場合の実行コスト情報を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記実行コスト情報を参照して、前記入力ループを前記ループ飛び出し処理のない前記出力ループに変換し、変換した前記出力ループを持つ前記出力プログラムを前記入出力装置に出力することを特徴とする請求項２に記載の計算機システム。
【請求項４】
前記計算機装置は、
ＦＰＧＡ又はＧＰＵを用いたアクセラレータを更に有し、
前記アクセラレータは、
前記ループ解析部を用いて、前記入力実行コストと前記出力実行コストを計算し、前記入力実行コストと前記出力実行コストの前記比較結果を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記比較結果として前記出力実行コストが前記入力実行コストより小さい場合に、前記入力ループを前記出力ループに変換することを特徴とする請求項２に記載の計算機システム。
【請求項５】
少なくとも主記憶装置を有する計算機装置によりプログラムを実行して情報を処理する計算機処理方法であって、
前記主記憶装置に、指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、変換候補ループテーブルとを格納しておき、
前記計算機装置により、
前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出し、
前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを入出力装置に出力することを特徴とする計算機処理方法。
【請求項６】
前記計算機装置により、
前記ループ解析部を用いて、前記解析結果として、前記入力ループの入力実行コストと前記出力ループの出力実行コストの比較結果を前記変換候補ループテーブルに格納することを特徴とする請求項５に記載の計算機処理方法。
【請求項７】
前記計算機装置により、
前記指示文解析部を用いて、前記入力プログラムを解析して前記入力ループを抽出し、抽出した前記入力ループを変換候補ループとして前記変換候補ループテーブルに格納し、
前記ループ解析部を用いて、前記変換候補ループテーブルに格納された前記入力ループを解析し、前記入力ループの構造がループ飛び出し処理を持つループ飛び出しループであり、かつ前記出力ループの前記出力実行コストが前記入力ループの前記入力実行コストより小さい場合の実行コスト情報を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記実行コスト情報を参照して、前記入力ループを前記ループ飛び出し処理のない前記出力ループに変換し、変換した前記出力ループを持つ前記出力プログラムを前記入出力装置に出力することを特徴とする請求項６に記載の計算機処理方法。
【請求項８】
前記計算機装置は、ＦＰＧＡ又はＧＰＵを用いたアクセラレータを更に有し、
前記アクセラレータにより、
前記指示文解析部を用いて、前記入力プログラムからＦＰＧＡ実行又はＧＰＵ実行を指示する前記指示文を持つループである前記入力ループを抽出し、
前記ループ解析部を用いて、前記入力実行コストと前記出力実行コストを計算し、前記入力実行コストと前記出力実行コストの前記比較結果を前記変換候補ループテーブルに格納し、
前記ループ変換部を用いて、前記比較結果として前記出力実行コストが前記入力実行コストより小さい場合に、前記入力ループを前記出力ループに変換することを特徴とする請求項６に記載の計算機処理方法。
【請求項９】
少なくとも主記憶装置を有する計算機装置に情報を処理して実行させる計算機処理プログラムであって、
前記計算機装置に、
指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、変換候補ループテーブルとを前記主記憶装置に格納する処理と、
前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出する処理と、
前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納する処理と、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを入出力装置に出力する処理と、
を実行させることを特徴とする計算機処理プログラム。
【請求項１０】
前記計算機装置に、
前記ループ解析部を用いて、前記解析結果として、前記入力ループの入力実行コストと前記出力ループの出力実行コストの比較結果を前記変換候補ループテーブルに格納する処理を実行させることを特徴とする請求項９に記載の計算機処理プログラム。
【請求項１１】
前記計算機装置に、
前記指示文解析部を用いて、前記入力プログラムを解析して前記入力ループを抽出し、抽出した前記入力ループを変換候補ループとして前記変換候補ループテーブルに格納する処理と、
前記ループ解析部を用いて、前記変換候補ループテーブルに格納された前記入力ループを解析し、前記入力ループの構造がループ飛び出し処理を持つループ飛び出しループであり、かつ前記出力ループの前記出力実行コストが前記入力ループの前記入力実行コストより小さい場合の実行コスト情報を前記変換候補ループテーブルに格納する処理と、
前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記実行コスト情報を参照して、前記入力ループを前記ループ飛び出し処理のない前記出力ループに変換し、変換した前記出力ループを持つ前記出力プログラムを前記入出力装置に出力する処理と、
を実行させることを特徴とする請求項１０に記載の計算機処理プログラム。
【請求項１２】
前記計算機装置は、ＦＰＧＡ又はＧＰＵを用いたアクセラレータを更に有し、
前記アクセラレータに、
前記指示文解析部を用いて、前記入力プログラムからＦＰＧＡ実行又はＧＰＵ実行を指示する前記指示文を持つループである前記入力ループを抽出する処理と、
前記ループ解析部を用いて、前記入力実行コストと前記出力実行コストを計算し、前記入力実行コストと前記出力実行コストの前記比較結果を前記変換候補ループテーブルに格納する処理と、
前記ループ変換部を用いて、前記比較結果として前記出力実行コストが前記入力実行コストより小さい場合に、前記入力ループを前記出力ループに変換する処理と、
を実行させることを特徴とする請求項１０に記載の計算機処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機システム、計算機処理方法及び計算機処理プログラムに関する。
【背景技術】
【０００２】
計算機システムにおけるプログラム実行において、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を補助してプログラムを高速に実行するアクセラレータを用いることが一般的になってきている。
【０００３】
アクセラレータには、プログラマブルな回路素子であるＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、画像処理プロセッサであるＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などがある。
【０００４】
例えば、米国Ａｍａｚｏｎ  Ｗｅｂ  Ｓｅｒｖｉｃｅｓ（ＡＷＳ）は、ＦＰＧＡを搭載したインスタンスであるＡＷＳ  Ｆ１インスタンスや、ＧＰＵを搭載したインスタンスであるＡＷＳ  ＥＣ２  Ｅｌａｓｔｉｃ  ＧＰＵインスタンスを、クラウドサービスとして広くユーザに提供してビジネスを行っている。
【０００５】
従来これらのアクセラレータを用いていたのは、ディープラーニングや科学技術計算のような数値計算系のプログラムであった。このようなプログラムの多くには、ループ中からのループ飛び出しがなく、そのためＦＰＧＡやＧＰＵ等で容易に並列実行が可能で実行速度の高速化が期待できるものである。
【０００６】
しかし、最近、数値計算系のプログラム以外でも、ハッシュテーブルのような探索プログラムをＦＰＧＡやＧＰＵ等を用いて高速化しようという試みもあらわれはじめている。ハッシュテーブルのような検索プログラムでは、ハッシュテーブル中の検索にループ飛び出しが必要である。例えば、特許文献１には、このようなループ飛び出しに関する技術が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１１−１２０００３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１は、ループ飛び出し条件が成立するかどうか確認しながら少しずつループ並列実行を行う。また、ループ飛び出し条件が成立したら、別途保存しておいたループ内で保存される変数値を用いてループ飛び出し後に使われる変数の値を生成する。しかし、この生成は逐次処理として行わなければならず、処理時間が長くなり計算機の性能向上の妨げとなる。
【０００９】
本発明の目的は、ループ飛び出しがあっても計算機処理をより短時間で実行することにある。
【課題を解決するための手段】
【００１０】
本発明の一態様の計算機システムは、少なくとも主記憶装置を有しプログラムを実行することにより情報を処理する計算機装置と、前記計算機装置に対する入出力を行う入出力装置とを備えた計算機システムであって、前記主記憶装置は、指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、変換候補ループテーブルと、を有し、前記計算機装置は、前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出し、前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納し、前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを前記入出力装置に出力することを特徴とする。
【００１１】
本発明の一態様の計算機処理方法は、少なくとも主記憶装置を有する計算機装置によりプログラムを実行して情報を処理する計算機処理方法であって、前記主記憶装置に、指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、変換候補ループテーブルとを格納しておき、前記計算機装置により、前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出し、前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納し、前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを入出力装置に出力することを特徴とする。
【００１２】
本発明の一態様の計算機処理プログラムは、少なくとも主記憶装置を有する計算機装置に情報を処理して実行させる計算機処理プログラムであって、前記計算機装置に、指示文解析部とループ解析部とループ変換部とを有するプログラム変換処理部と、変換候補ループテーブルとを前記主記憶装置に格納する処理と、前記指示文解析部を用いて、前記入出力装置から入力された入力プログラムから直後のループが変換候補であることを指示する指示文を持つループである入力ループを抽出する処理と、前記ループ解析部を用いて、前記入力ループを解析して解析結果を前記変換候補ループテーブルに格納する処理と、前記ループ変換部を用いて、前記変換候補ループテーブルに格納された前記解析結果を利用して、前記入力ループを出力ループに変換した出力プログラムを入出力装置に出力する処理と、を実行させることを特徴とする。
【発明の効果】
【００１３】
本発明一態様によれば、ループ飛び出しがあっても計算機処理をより短時間で実行することができる。
【図面の簡単な説明】
【００１４】
【図１】実施例１の計算機システムの構成を示す図である。
【図２】ＦＰＧＡを用いたアクセラレータの構成を示す図である。
【図３】ＧＰＵを用いたアクセラレータの構成を示す図である。
【図４】計算機処理方法を示す図である。
【図５】入力プログラムの例を示す図である。
【図６】出力プログラムの例を示す図である。
【図７】条件式ｃｏｎｄｉｔｉｏｎが０回成立する出力プログラムの動作模式図である。
【図８】条件式ｃｏｎｄｉｔｉｏｎが１回成立する出力プログラムの動作模式図である。
【図９】指示文解析部のフローチャートである。
【図１０】変換候補ループテーブルについて示す図である。
【図１１】ループ解析部のフローチャートである。
【図１２】ループ構造チェック部のフローチャートである。
【図１３】ループ構造について示す図である。
【図１４】前判定ループ本体構造チェック部のフローチャートである。
【図１５】後判定ループ本体構造チェック部のフローチャートである。
【図１６】実行コストチェック部のフローチャートである。
【図１７】ループ変換部のフローチャートである。
【図１８】単一ループ変換部のフローチャートである。
【図１９】ループテンプレート作成部のフローチャートである。
【図２０】初期化処理挿入部のフローチャートである。
【図２１】終了処理挿入部のフローチャートである。
【図２２】ループ本体変換部のフローチャートである。
【図２３】実施例２のＦＰＧＡ向けの入力プログラムの例を示す図である。
【図２４】実施例２のＦＰＧＡ向けの実行コストチェック部のフローチャートである。
【図２５】実施例２のＦＰＧＡ向けのアクセラレータ選択係数計算部のフローチャートである。
【図２６】実施例３のＧＰＵ向けの入力プログラムの例を示す図である。
【図２７】実施例３のＧＰＵ向けの実行コストチェック部のフローチャートである。
【図２８】実施例３のＧＰＵ向けのアクセラレータ選択係数計算部のフローチャートである。
【発明を実施するための形態】
【００１５】
最初に、実施の形態について説明する。以下では、プログラムをＣ言語で記述するが、本発明の範囲は記述言語に限定されず、ＯｐｅｎＣＬ（Ｏｐｅｎ  Ｃｏｍｐｕｔｉｎｇ  Ｌａｎｇｕａｇｅ）等のアクセラレータ向け言語、Ｖｅｒｉｌｏｇ  ＨＤＬやＶＨＤＬ等のハードウェア記述言語等でも適用可能である。
【００１６】
ハッシュテーブルのような検索プログラムでは、ハッシュテーブル中の検索にループ飛び出しが必要である。下記のループは、ハッシュテーブル中からｋｅｙが一致する場合のｖａｌｕｅを求める操作を記述したプログラムである。行左端の数字は行番号を表す。
【００１７】
１：  ｆｏｒ  （ｉ＝０；  ｉ＜ｈａｓｈ＿ｔａｂｌｅ＿ｓｉｚｅ；  ｉ＋＋）  ｛
２：      ｉｆ  （ｉｎｐｕｔ＿ｋｅｙ  ＝＝  ｈａｓｈ＿ｔａｂｌｅ［ｉ］．ｋｅｙ）  ｛
３：          ｏｕｔｐｕｔ＿ｖａｌｕｅ  ＝  ｈａｓｈ＿ｔａｂｌｅ［ｉ］．ｖａｌｕｅ；
４：          ｂｒｅａｋ；
５：      ｝
６：  ｝
【００１８】
このプログラムは、１行目のループで、ループ制御変数ｉを用いてハッシュテーブルを端からたどり、２行目のｉｆ文で、ハッシュテーブル構造体配列要素ｈａｓｈ＿ｔａｂｌｅ［ｉ］に格納されたｈａｓｈ＿ｔａｂｌｅ［ｉ］．ｋｅｙが、ユーザが入力したｉｎｐｕｔ＿ｋｅｙと等しいか調べ、等しい場合は３行目でｈａｓｈ＿ｔａｂｌｅ［ｉ］．ｖａｌｕｅの値を取り出してｏｕｔｐｕｔ＿ｖａｌｕｅに代入し、４行目でループを飛び出して処理を終了するものである。このようなループ飛び出しを持つループ（以下、ループ飛び出しループと記述）は、ハッシュテーブル探索に必須の処理である。
【００１９】
ループ飛び出しループは、実際にループを実行しないとループ飛び出しが行われるループ繰り返し回数がわからないため、従来はコンパイラによる並列化等の高速化変換を行うことが困難で、ループ繰り返しを１つずつループ飛び出しが発生するまで逐次的に実行せざるを得えない。そのため、ＦＰＧＡやＧＰＵ等を利用する際のプログラム性能向上のボトルネックとなっていた。
【００２０】
一方ハッシュテーブルでは、ｈａｓｈ＿ｔａｂｌｅ［ｉ］．ｋｅｙの値に重なりがないことがわかっている。そのため、上記プログラムの２行目のｉｆ文は、１行目のループが最初の繰り返し（ｉ＝０）から最後の繰り返し（ｉ＝ｈａｓｈ＿ｔａｂｌｅ＿ｓｉｚｅ−１）まで実行されても０回（ハッシュテーブル中にｋｅｙがない場合）または１回（ハッシュテーブル中にｋｅｙがある場合）しか成立しないことという特徴がある。
【００２１】
実施形態は、この特徴を利用して、ループ飛び出し条件がループ中で０回または１回しか成立しないループ飛び出しループに関して、指示文を用いてループ飛び出し条件がループ中で０回または１回しか成立しないループであることを指示する。そして、指示されたループを変換してループ飛び出しをなくすことにより、並列化コンパイラ等による並列化を適用可能とする。
【００２２】
実施形態によれば、ループ飛び出し条件がループ中で０回または１回しか成立しないループ飛び出しループに関して、ＦＰＧＡやＧＰＵ等のアクセラレータでより短時間で実行できる。実施形態は、ＦＰＧＡやＧＰＵなどのアクセラレータを用いたプログラム開発に適用することができる。
以下、図面を用いて、実施例について説明する。
【実施例１】
【００２３】
実施例１は、アクセラレータの種類を指定せずにプログラムを変換する場合の計算機の処理方法である。図１を参照して、実施例１に係る計算機システム７のハードウェア構成について説明する。
【００２４】
図１に示すように、計算機装置１は、主記憶装置２、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３、ＦＰＧＡやＧＰＵ等のアクセラレータ４及び外部記憶装置５を有し、入出力装置６と接続されている。主記憶装置２には、プログラム変換処理部１８と変換候補ループテーブル１６が配置されている。プログラム変換処理部１８内には、指示文解析部３０、ループ解析部４０及びループ変換部５０が配置されている。外部記憶装置５には、入力プログラム１０と出力プログラム１２が配置されている。
【００２５】
図２を参照して、ＦＰＧＡを用いたアクセラレータであるＦＰＧＡアクセラレータ４のハードウェア構成について説明する。
図２に示すように、ＦＰＧＡ（４ｂ）は、アクセラレータ内部にあるＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）（４ａ）と接続されている。また、ＤＲＡＭ（４ａ）は、入出力インタフェース４ｃを介して、アクセラレータ外部にあるＣＰＵ３（図１参照）とＰＣＩ  Ｅｘｐｒｅｓｓ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｅｘｐｒｅｓｓ）などの通信路（図示せず）で接続されている。
【００２６】
図３を参照して、ＧＰＵを用いたアクセラレータであるＧＰＵアクセラレータ４のハードウェア構成について説明する。
図３に示すように、ＧＰＵ（４ｄ）は、アクセラレータ内部にあるＤＲＡＭ（４ａ）と接続されている。また、ＤＲＡＭ（４ａ）は、入出力インタフェース４ｃを介して、アクセラレータ外部にあるＣＰＵ１３（図１参照）とＰＣＩ  Ｅｘｐｒｅｓｓなどの通信路（図示せす）で接続されている。
【００２７】
ここでは、ＦＰＧＡやＧＰＵをアクセラレータの例として挙げたが、Ｉｎｔｅｌ（登録商標）  ＸｅｏｎＰｈｉのようなメニーコアプロセッサ等がアクセラレータであってもよい。
【００２８】
図４を参照して、プログラム変換処理部１８の構成について説明する。ここで、点線矢印は制御の流れ（制御フロー）を、実線矢印はデータの流れ（データフロー）を示している。
【００２９】
図４に示すように、入力プログラム１０がプログラム変換処理部１８に入力されると、指示文解析部３０が入力プログラム１０を解析して指示文付きループを検出し、検出したループを変換候補ループとして、変換候補ループテーブル１６を作成して登録する。
【００３０】
次に、ループ解析部４０が、変換候補ループテーブル１６に登録された前記変換候補ループを解析する。そして、ループの構造がループ飛び出し処理を持つループ飛び出しループであり、実施例１の変換方法適用時の前記変換候補ループの実行コストが非適用時の実行コストより小さい場合の情報を変換候補ループテーブル１６に格納する。
【００３１】
次に、ループ変換部５０が、変換候補ループテーブル１６に格納された、実施例１の変換方法適用時の前記変換候補ループの実行コストが非適用時の実行コストより小さい前記変換候補ループをループ飛び出しのないループに変換し、出力プログラム１２を出力する。
【００３２】
図５を参照して、入力プログラム１０の一例について説明する。
各行左端の数字は理解を補助するための行番号である。１行目は指示文であり、指示文を含む行であることを意味する「＃ｐｒａｇｍａ」文字列と、指示文本体である「ＬＯＯＰ＿ＴＲＡＮＳ」と、指示文本体に付随するオプショナルな文字列である「ｄｅｖｉｃｅ」から構成され、以下の形式で記述される。
＃ｐｒａｇｍａ  ＬＯＯＰ＿ＴＲＡＮＳ  ｄｅｖｉｃｅ
【００３３】
「ｄｅｖｉｃｅ」は、「指定しない（空文字列）」、「ＦＰＧＡ」、「ＧＰＵ」の３種類を選べるものとするが、これ以外の選択肢があってもかまわない。また、これ以外の形式の指示文であってもかまわない。図５では「指定しない（空文字列）」であるとする。２〜７行目は指示文の指示対象となるループであり、３行目に条件文、４行目に条件文下の代入文、５行目にループ飛び出し文ｂｒｅａｋがある。このループを以下では本体ループと呼ぶ。
【００３４】
３行目の条件文の条件式は「ｃｏｎｄｉｔｉｏｎ」と記述されているが、これは条件式一般を意味し、「ｃｏｎｄｉｔｉｏｎ」という名前の変数を意味しない。例えば、「ｃｏｎｄｉｔｉｏｎ」は「ｉ＝＝３」という、ループ制御変数ｉの値によって結果が変わる条件式であってよい。同様に、４行目の条件文下の代入文の右辺「ｅｘｐ」であるが、これは代入文右辺に現れる式一般を意味し、「ｅｘｐ」という名前の変数を意味しない。
【００３５】
例えば、「ｅｘｐ」は「ｉ＋３」という、ループ制御変数ｉの値によって結果が変わる式であってよい。なお本指示文を書いてよいループは、２〜７行目のループから５行目のループ飛び出し文ｂｒｅａｋを削除したループを実行した場合に、条件式「ｃｏｎｄｉｔｉｏｎ」の成立回数が０回または１回の場合だけである。
【００３６】
図６を参照して、出力プログラム１２の一例について説明する。
各行左端の数字は理解を補助するための行番号である。１〜４行目は初期化処理であり、１行目で新たに設けた一時変数ｖａｒ＿ｏｒｇを、入力プログラム１０の４行目の代入文左辺に表れる変数ｖａｒで初期化し、また２〜４行目は新たに設けた一時配列ｖａｒ＿ｔｍｐ［ｉ］を０で初期化するループである。
【００３７】
ｉはループのループ制御変数であり、このループの繰返し範囲はｉ＝０，１，．．．，Ｎ−１と、入力プログラム１０の本体ループと等しい。２〜４行目のループを以下では初期化ループと呼ぶ。５〜９行目は、入力プログラム１０の本体ループからループ飛び出し文ｂｒｅａｋを削除し、入力プログラム１０の４行目の代入文左辺を前記一時配列ｖａｒ＿ｔｍｐ［ｉ］で置き換えたループである。
【００３８】
ｉはループ制御変数である。このループを以下では本体変換後ループと呼ぶ。１０〜１５行目は終了処理であり、１０〜１２行目では前記一時配列ｖａｒ＿ｔｍｐ［ｉ］を前記変数ｖａｒに加算するループであり、以下では終了処理ループと呼ぶ。ｉはループ制御変数であり、このループの繰返し範囲はｉ＝０，１，．．．，Ｎ−１と、入力プログラム１０の本体ループと等しい。また１３〜１５行目では、前記一時変数ｖａｒ＿ｏｒｇと前記変数ｖａｒの値が異なっていたら、前記変数ｖａｒから前記一時変数ｖａｒ＿ｏｒｇの値を減算する。以上で図６の説明を終了する。
【００３９】
図７を参照して、出力プログラム１２の条件式「ｃｏｎｄｉｔｉｏｎ」が、前記本体変換後ループ中で０回成立する場合の、変数ｖａｒである１３ａ、一時変数ｖａｒ＿ｏｒｇである１３ｂ、一時配列ｖａｒ＿ｔｍｐ［ｉ］である１３ｃの値の動きを示した一例について説明する。
【００４０】
ループ長Ｎは３、変数ｖａｒの初期値は１１と仮定している。プログラム１２ａ〜１２ｄは、出力プログラム１２を処理内容で４つに分割したプログラム片である。プログラム１２ａ〜１２ｄの行左端の番号は連番で打った行番号である。黒矢印は、プログラム１２ａ〜１２ｄの入出力を表す。
【００４１】
最初に、出力プログラム１２の初期化処理１２ａが実行される。初期化処理１２ａが終了した時点での変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇ、一時配列ｖａｒ＿ｔｍｐ［ｉ］の値は、それぞれ１１、１１、（０，０，０）である。（０，０，０）は、一時配列ｖａｒ＿ｔｍｐ［０］、ｖａｒ＿ｔｍｐ［１］、ｖａｒ＿ｔｍｐ［２］の値をまとめて表記したものである。
【００４２】
次に、出力プログラム１２の本体変換後ループ１２ｂが実行される。条件式ｃｏｎｄｉｔｉｏｎの成立回数が０回を仮定しているため、変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇ、一時配列ｖａｒ＿ｔｍｐ［ｉ］の値は変化せず１１、１１、（０，０，０）のままである。
【００４３】
次に、出力プログラム１２の終了処理中のループ１２ｃが実行される。これは変数ｖａｒに一時配列ｖａｒ＿ｔｍｐ［ｉ］の値を加算するループである。本体変換後ループ１２ｂの終了時点で一時配列ｖａｒ＿ｔｍｐ［ｉ］の各要素の値は全て０なので、変数ｖａｒには０が加算されることになり、前記ループ１２ｃの終了時点で変数ｖａｒの値は変わらず１１である。
【００４４】
最後に、出力プログラム１２の終了処理中の条件処理１２ｄが実行される。前記条件処理１２ｄの実行開始前の変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇの値は両方とも１１であるので、前記条件処理１２ｄの１３行目の条件文ｖａｒ＿ｏｒｇ！＝ｖａｒは成立せず、１４行目の代入文ｖａｒ−＝ｖａｒ＿ｏｒｇは実行されない。従って、前記条件処理１２ｄ終了後の変数ｖａｒの値１３ａは１１のままである。これは、前記入力プログラム１０を、同じ前提条件で実行した場合の結果と等しい。
【００４５】
図８を参照して、出力プログラム１２の条件式「ｃｏｎｄｉｔｉｏｎ」が、前記本体変換後ループ中で１回成立する場合の、変数ｖａｒである１３ａ、一時変数ｖａｒ＿ｏｒｇである１３ｂ、一時配列ｖａｒ＿ｔｍｐ［ｉ］である１３ｃの値の動きを示した一例について説明する。ここで、ループ長Ｎは３、変数ｖａｒの初期値は１１と仮定している。
【００４６】
最初に、出力プログラム１２の初期化処理１２ａが実行される。初期化処理１２ａが終了した時点での変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇ、一時配列ｖａｒ＿ｔｍｐ［ｉ］の値は、それぞれ１１、１１、（０，０，０）である。
【００４７】
次に、出力プログラム１２の本体変換後ループ１２ｂが実行される。条件式「ｃｏｎｄｉｔｉｏｎ」の成立回数が１回を仮定しているため、７行目の代入文ｖａｒ＿ｔｍｐ［ｉ］＝ｅｘｐは１回だけ実行される。ループ制御変数ｉの値が１のときに条件式ｃｏｎｄｉｔｉｏｎが成立すると仮定して、このときのｅｘｐの値を３とすると、本体変換後ループ１２ｂ実行後の変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇ、一時配列ｖａｒ＿ｔｍｐ［ｉ］の値は、それぞれ１１、１１、（０，３，０）である。
【００４８】
次に、出力プログラム１２の終了処理中のループ１２ｃが実行される。これは変数ｖａｒに一時配列ｖａｒ＿ｔｍｐ［ｉ］の値を加算するループである。本体変換後ループ１２ｂの終了時点で一時配列ｖａｒ＿ｔｍｐ［ｉ］の各要素の値は（０，３，０）なので、変数ｖａｒには３が加算されることになり、前記ループ１２ｃの終了時点で変数ｖａｒの値は１４に変化する。
【００４９】
最後に、出力プログラム１２の終了処理中の条件処理１２ｄが実行される。前記条件処理１２ｄの実行開始前の変数ｖａｒ、一時変数ｖａｒ＿ｏｒｇの値はそれぞれ１４、１１であるので、前記条件処理１２ｄの１３行目の条件文ｖａｒ＿ｏｒｇ！＝ｖａｒが成立し、１４行目の代入文ｖａｒ−＝ｖａｒ＿ｏｒｇは実行される。これは１４から１１を減算した結果を変数ｖａｒに代入する処理なので、前記条件処理１２ｄ終了後の変数ｖａｒの値１３ａは３に変わる。これは、前記入力プログラム１０を、同じ前提条件で実行した場合の結果と等しい。
【００５０】
図７、図８より、前記条件式「ｃｏｎｄｉｔｉｏｎ」が０回または１回成立する場合には、それぞれ入力プログラム１０と出力プログラム１２の結果（変数ｖａｒの出力値）が一致することが分かる。
【００５１】
図９を参照して、プログラム変換処理１８の詳細な説明を行う。図９は指示文解析部３０のフローチャートである。
【００５２】
最初に、ステップ３０ａで入力プログラム１０の先頭行を得る。次に、ステップ３０ｂで、現在の行に指示文があるか確認する。指示文がない場合（分岐Ｎｏ）は、ステップ３０ｄで入力プログラム１０の最終行であるか確認し、最終行である場合（分岐Ｙｅｓ）は処理を終了する。最終行でない場合（分岐Ｎｏ）はステップ３０ｅで入力プログラム１０を１行辿り、ステップ３０ｂに戻る。
【００５３】
ステップ３０ｂで指示文がある場合（分岐Ｙｅｓ）は、次にステップ３０ｃで変換候補ループテーブル１６を作成して、指示文の次の行（前記本体ループ先頭行）と指示文で指定されたｄｅｖｉｃｅを変換候補ループテーブル１６に登録する。ただしｄｅｖｉｃｅが空文字列の場合は何も登録しない。次に、ステップ３０ｄを実行する。
【００５４】
図１０を参照して、変換候補ループテーブル１６について説明する。
矢印とそれに続く内容は、テーブル各行の意味の説明である。１行目に前記本体ループ先頭行の行番号、２行目に指示文で指定されたｄｅｖｉｃｅ、３行目にループ構造フラグ、４行目に実行コストフラグ、５行目に変換フラグ、６行目に次の変換候補ループテーブル１６へのポインタを格納する。
【００５５】
図１０では作成直後の変換候補ループテーブル１６の状態を図示しており、各行には１行目から順に初期値である−１、ｎｏｎｅ、ＮＧ、ＮＧ、ＮＧ、ＮＵＬＬが入っている。図９のステップ３０ｃで作成された変換候補ループテーブル１６には、入力プログラム１０にあるように、１行目に「２」（本体ループ先頭行が２行目であるため）、２行目に「ｎｏｎｅ」（指示文中のｄｅｖｉｃｅが空文字列であると仮定しているため）が登録される。入力プログラム１０中に複数の指示文がある場合は、変換候補ループテーブル１６の６行目を用いて、複数の変換候補ループテーブル１６をポインタで繋いだ連結リストとする。
【００５６】
図１１はループ解析部４０のフローチャートである。
最初に、ステップ４０ａで、変換候補ループテーブル１６の先頭のループを取り出す。これは、変換候補ループテーブル１６をポインタで繋いだ連結リストの先頭の変換候補ループテーブル１６から、１行目に登録された行を先頭とするループを入力プログラム１０から取り出すことである。
【００５７】
次に、ループ構造チェック部４０ｂを実行し、続いてステップ４０ｃで変換候補ループテーブル１６の３行目のループ構造フラグがＯＫであるか調べ、ＯＫであれば（分岐Ｙｅｓ）実行コストチェック部４０ｄを実行し、ＯＫでなければ（分岐Ｎｏ）ステップ４０ｇを実行する。実行コストチェック部４０ｄの実行後、ステップ４０ｅで変換候補ループテーブル１６の４行目の実行コストフラグがＯＫであるか調べ、ＯＫであれば（分岐Ｙｅｓ）ステップ４０ｆを実行し、ＯＫでなければ（分岐Ｎｏ）ステップ４０ｇを実行する。
【００５８】
ステップ４０ｆでは変換候補ループテーブル１６の５行目の変換フラグにＯＫを設定し、ステップ４０ｇを実行する。ステップ４０ｇでは、前記取り出したループが登録されている変換候補ループテーブル１６が変換候補ループテーブル１６をポインタで繋いだ連結リストの末尾であるか調べ、末尾でなければ（分岐Ｎｏ）、ステップ４０ｈで連結リストを１つたどって次の変換候補ループテーブル１６に登録されたループを取り出してループ構造チェック部４０ｂに戻り、末尾であれば（分岐Ｙｅｓ）終了する。
【００５９】
図１２はループ構造チェック部４０ｂのフローチャートである。
最初に、ステップ４０ｂ１で、ループが前判定ループかどうか判定する。前判定ループとは、ループ本体の実行前にループ継続条件を判定するループであり、図１３のループ構造図のプログラム１４ａのようなｆｏｒ文やプログラム１４ｂのようなｗｈｉｌｅ文が該当する。プログラム１４ａは、ループ制御変数初期値設定文、ループ継続条件判定式、ループ制御変数更新文を持つｆｏｒ文で書かれたループであり、プログラム１４ｂは、ループ制御変数初期値設定文、ループ継続条件判定式、ループ制御変数更新文を持つｗｈｉｌｅ文で書かれたループである。ループ制御変数初期値設定文とは、ループ制御変数をｉとしたときにｉ＝０のようにループ制御変数の初期値を設定する文である。
【００６０】
ループ継続条件判定式とは、ループ上限値をＮとしたときにｉ＜Ｎのように次のループ繰り返しを実行するかどうかを判定する式である。ループ制御変数更新文とは、ｉ＋＋のように次のループ繰り返しでのループ制御変数の値を計算する文である。プログラム１４ａ、プログラム１４ｂともに、ループ本体には代入文のみ書けるものとする。前判定ループである場合（分岐Ｙｅｓ）は、前判定ループ本体構造チェック部４０ｂ２を実行し、そうでない場合（分岐Ｎｏ）はステップ４０ｂ３を実行する。
【００６１】
ステップ４０ｂ３では、ループが後判定ループかどうか判定する。後判定ループとは、ループ本体の実行後にループ継続条件を判定するループであり、図１３のループ構造図のプログラム１４ｃのようなｄｏ−ｗｈｉｌｅ文が該当する。プログラム１４ｃは、ループ制御変数初期値設定文、ループ継続条件判定式、ループ制御変数更新文を持つｄｏ−ｗｈｉｌｅ文で書かれたループである。プログラム１４ｃでは、ループ本体には代入文のみ書けるものとする。後判定ループである場合（分岐Ｙｅｓ）は、後判定ループ本体構造チェック部４０ｂ４を実行し、そうでない場合（分岐Ｎｏ）はループ構造チェック部４０ｂを終了する。
【００６２】
また、後判定ループ本体構造チェック部４０ｂ４の実行後、ループ構造チェック部４０ｂを終了する。以上ではｆｏｒ文、ｗｈｉｌｅ文、ｄｏ−ｗｈｉｌｅ文で書かれたループを取り上げたが、同様な構造をｇｏｔｏ文とｉｆ文で実装するループであってもよい。
【００６３】
図１４は前判定ループ本体構造チェック部４０ｂ２のフローチャートである。
最初に、ステップ４０ｂ２ａを実行し、ループ継続条件判定式が成立した場合に実行される次の処理がループ飛び出し条件の評価であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｂに進み、そうでなければ（分岐Ｎｏ）前判定ループ本体構造チェック部４０ｂ２を終了する。
【００６４】
次に、ステップ４０ｂ２ｂを実行し、ループ飛び出し条件が成立した場合に実行される次の処理が１つ以上の代入文であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｃに進み、そうでなければ（分岐Ｎｏ）前判定ループ本体構造チェック部４０ｂ２を終了する。次にステップ４０ｂ２ｃを実行し、前記１つ以上の代入文の実行後にループ飛び出し処理があるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｄに進み、そうでなければ（分岐Ｎｏ）前判定ループ本体構造チェック部４０ｂ２を終了する。
【００６５】
次に、ステップ４０ｂ２ｄを実行し、ループ飛び出し条件が不成立の場合に実行される次の処理がループ制御変数更新文であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｅを実行し、そうでなければ（分岐Ｎｏ）前判定ループ本体構造チェック部４０ｂ２を終了する。
【００６６】
最後に、ステップ４０ｂ２ｅを実行し、変換候補ループテーブル１６の３行目にあるループ構造フラグにＯＫを設定して、前判定ループ本体構造チェック部４０ｂ２を終了する。
【００６７】
図１５は後判定ループ本体構造チェック部４０ｂ４のフローチャートである。
最初に、ステップ４０ｂ４ａを実行し、ループ制御変数初期化文の次の処理がループ飛び出し条件の評価であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｂを実行し、そうでなければ（分岐Ｎｏ）後判定ループ本体構造チェック部４０ｂ４を終了する。
【００６８】
次、にステップ４０ｂ２ｂを実行し、ループ飛び出し条件が成立した場合に実行される次の処理が１つ以上の代入文であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｃに進み、そうでなければ（分岐Ｎｏ）後判定ループ本体構造チェック部４０ｂ２を終了する。
【００６９】
次に、ステップ４０ｂ２ｃを実行し、前記１つ以上の代入文の実行後にループ飛び出し処理があるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｄに進み、そうでなければ（分岐Ｎｏ）後判定ループ本体構造チェック部４０ｂ２を終了する。
【００７０】
次に、ステップ４０ｂ２ｄを実行し、ループ飛び出し条件が不成立の場合に実行される次の処理がループ制御変数更新文であるか調べ、そうであれば（分岐Ｙｅｓ）ステップ４０ｂ２ｅを実行し、そうでなければ（分岐Ｎｏ）後判定ループ本体構造チェック部４０ｂ２を終了する。
【００７１】
最後、にステップ４０ｂ２ｅを実行し、変換候補ループテーブル１６の３行目にあるループ構造フラグにＯＫを設定して、後判定ループ本体構造チェック部４０ｂ２を終了する。
【００７２】
図１６は、実行コストチェック部４０ｄのフローチャートである。
最初に、ステップ４０ｄ１で、変換候補ループテーブル１６の２行目に登録されたデバイス種がｎｏｎｅであるか確認し、ｎｏｎｅであれば（分岐Ｙｅｓ）ステップ４０ｄ４で変換候補ループテーブル１６の５行目の変換フラグをＯＫとして終了する。ｎｏｎｅでなければ（分岐Ｎｏ）なにもせずに終了する。
【００７３】
図１７は、ループ変換部５０のフローチャートである。
最初に、ステップ５０ａで、変換候補ループテーブル１６から変換フラグがＯＫのループを探し、存在すれば（分岐Ｙｅｓ）そのループを選択してステップ５０ｂを実行し、存在しなければ（分岐Ｎｏ）ループ変換部５０を終了する。
【００７４】
次に、ステップ５０ｂで、前記変換対象ループから指示文を削除する。これは、図５の入力プログラム１０から１行目を削除することを意味する。この入力プログラム１０から１行目を削除したループ（入力プログラム１０の２〜７行目）を、以下では変換対象ループと呼ぶ。
【００７５】
次に、単一ループ変換部５０ｃを実行し、前記変換対象ループから出力プログラム１２に変換する。次にステップ５０ｄで、変換候補ループテーブル１６の前記変換対象ループの変換フラグをＮＧに書き換え、その後ステップ５０ａに戻る。
【００７６】
図１８は、単一ループ変換部５０ｃのフローチャートである。
前記変換対象ループに対して、最初にループテンプレート作成部５０ｃ１を実行し、次に初期化処理挿入部５０ｃ２を実行し、次に終了処理挿入部５０ｃ３を実行し、最後にループ本体変換部５０ｃ４を実行し、単一ループ変換部５０ｃを終了する。
【００７７】
図１９は、ループテンプレート作成部５０ｃ１のフローチャートである。
ステップ５０ｃ１ａで、前記変換対象ループから、ループ制御変数初期値設定文、ループ継続条件判定式、ループ制御変数更新文と、ｆｏｒ文またはｗｈｉｌｅ文またはｄｏ−ｗｈｉｌｅ文を抜き出したものを作成し、これをループテンプレートと呼ぶ。前記ループテンプレートは、図１３のプログラム１４ａ、プログラム１４ｂ、プログラム１４ｃからループ本体を削除したものに等しい。
【００７８】
図２０は、初期化処理挿入部５０ｃ２のフローチャートである。
ステップ５０ｃ２ａで、前記変換対象ループのループ飛び出し条件下にある代入文を１つ選択する。選択順は、プログラムで前記代入文が実行される順でなければならない。次に、ステップ５０ｃ２ｂでは、前記選択した代入文の左辺変数を、新たに作成した一時変数に代入する文を作成し、前記変換対象ループの直前に挿入する。これは図６の出力プログラム１２では、１行目の代入文を挿入することに当たる。
【００７９】
次に、ステップ５０ｃ２ｃでは、前記ループテンプレートをコピーして用いて、新たに作成した一時配列要素に０を代入する初期化ループを作成し、前記変換対象ループの直前に挿入する。これは図６の出力プログラム１２では、２〜４行目のループを挿入することに当たる。次にステップ５０ｃ２ｄでは、前記変換対象ループのループ飛び出し条件下にある代入文を全て選択したか調べ、全て選択していれば（分岐Ｙｅｓ）初期化処理挿入部５０ｃ２を終了し、そうでなければ（分岐Ｎｏ）ステップ５０ｃ２ａに戻る。
【００８０】
図２１は、終了処理挿入部５０ｃ３のフローチャートである。
最初に、ステップ５０ｃ３ａでは、前記変換対象ループのループ飛び出し条件下にある代入文を１つ選択する。選択順は、プログラムで前記代入文が実行される順の逆順でなければならない。
【００８１】
次に、ステップ５０ｃ３ｂでは、前記一時変数と前記選択された代入文の左辺変数の値を比較する条件文を作成し、値が異なった場合に、前記左辺変数から前記一時変数の値を減算する文を作成し、前記変換対象ループ直後に挿入する。これは図６の出力プログラム１２では、１３〜１５行目のｉｆ文と代入文を挿入することに当たる。
【００８２】
次に、ステップ５０ｃ３ｃでは、ループテンプレートをコピーして用いて、前記左辺変数に前記一時配列要素を加算する終了処理ループを作成し、前記変換対象ループ直後に挿入する。これは図６の出力プログラム１２では、１０〜１２行目のループを挿入することに当たる。
【００８３】
次に、ステップ５０ｃ３ｄでは、前記変換対象ループのループ飛び出し条件下にある代入文を全て選択したか調べ、全て選択していれば（分岐Ｙｅｓ）終了処理挿入部５０ｃ３を終了し、そうでなければ（分岐Ｎｏ）ステップ５０ｃ３ａに戻る。
【００８４】
図２２は、ループ本体変換部５０ｃ４のフローチャートである。
最初に、ステップ５０ｃ４ａでは、前記変換対象ループのループ飛び出し条件下にある代入文を１つ選択する。選択順は、プログラムで前記代入文が実行される順でなければならない。次にステップ５０ｃ４ｂでは、前記選択した代入文の左辺変数を、前記一時配列要素で置き換える。これは図６の出力プログラム１２では、７行目の代入文の左辺をｖａｒ＿ｔｍｐ［ｉ］で置き換えることに当たる。
【００８５】
次に、ステップ５０ｃ４ｃでは、前記変換対象ループのループ飛び出し条件下にある代入文を全て選択したか調べ、全て選択していればステップ５０ｃ４ｄを実行し、そうでなければステップ５０ｃ４ａに戻る。
【００８６】
最後に、ステップ５０ｃ４ｄでは、前記変換対象ループからループ飛び出し文を削除する。これは図６の出力プログラム１２では、７行目と８行目の間にあったｂｒｅａｋ文（図５の入力プログラム１０の５行目のｂｒｅａｋ文と同一）を削除することに当たる。
【００８７】
入力プログラム１０をプログラム変換処理１８で変換した出力プログラム１２は、初期化ループと終了処理ループがループ繰り返しにまたがる変数依存関係（ループ運搬フロー依存）を持たないループであり、変換後本体ループが総和型ループである。このため、従来技術の並列化コンパイラ、例えば、Ｉｎｔｅｌ（登録商標）  Ｃコンパイラで容易にループ並列化が可能なものであり、入力プログラム１０の実行時間より出力プログラム１２の実行時間のほうが短くなることが期待できる。
【実施例２】
【００８８】
実施例２は、アクセラレータがＦＰＧＡと指示文で指定された場合にプログラムを変換する場合の計算機処理方法である。図２３を参照して、実施例２に対応した入力プログラム１０の一例について説明する。
【００８９】
図５の入力プログラム１０と比較すると、１行目の指示文に、指示文本体に付随するオプショナルな文字列「ＦＰＧＡ」が新たに加わっている。
【００９０】
図２４は、実施例２に対応した、実行コストチェック部４０ｄのフローチャートである。
【００９１】
ステップ４０ｄ１ａで、変換候補ループテーブル１６の２行目に登録されたデバイス種がＦＰＧＡであるか確認し、ＦＰＧＡであれば（分岐Ｙｅｓ）アクセラレータ選択係数計算部４０ｄ２を実行し、ＦＰＧＡでなければ（分岐Ｎｏ）実行コストチェック部４０ｄを終了する。アクセラレータ選択係数計算部４０ｄ２の実行後はステップ４０ｄ３を実行して、アクセラレータ選択係数計算部の返値がＯＫか調べ、ＯＫであれば（分岐Ｙｅｓ）変換候補ループテーブル１６の実行コストフラグをＯＫにして実行コストチェック部４０ｄを終了し、そうでなければ（分岐Ｎｏ）実行コストチェック部４０ｄを終了する。
【００９２】
ここで、ＦＰＧＡ向けのアクセラレータ選択係数の計算方法について説明する。変換候補ループとして入力プログラム１０、変換候補ループを本発明の方式で変換した変換後ループとして出力プログラム１２を例に用いる、入力プログラム１０の実行コストをＱｃ、出力プログラム１２の実行コストをＱｐとし、アクセラレータ選択係数Ａ＝Ｑｃ／Ｑｐと定義すると、Ａ＞１であれば変換後ループの実行コストのほうが小さい、すなわちＣＰＵ実行よりもＦＰＧＡ実行のほうが高速に実行できることになる。
【００９３】
ここで、入力ループ１０のループ長をＮ、ループ本体の実行コストをＬとする。ハッシュテーブルの場合、ループ長Ｎはハッシュテーブルのエントリ数に対応し十分長いことがわかっているのでＮ＞＞Ｌを仮定する。入力ループ１０はどのループ繰り返しでループを飛び出すか実行するまで分からないが、平均的にはループ長Ｎの１／２だけループ繰り返しを実行したところでループを飛び出すと仮定する。
【００９４】
すると、Ｑｃ＝Ｌ＊Ｎ／２と書くことができる。また、出力プログラム１２の１〜４行目の前記初期化処理の実行コストをＱｐ１、５〜９行目のループの実行コストをＱｐ２、１０〜１５行目の前記終了処理の実行コストをＱｐ３とすると、Ｑｐ＝Ｑｐ１＋Ｑｐ２＋Ｑｐ３となる。出力プログラム１２の１行目の代入文の実行コストをＱｐ１ａ、２〜４行目のループの実行コストをＱｐ１ｂとすると、Ｑｐ１＝Ｑｐ１ａ＋Ｑｐ１ｂであるが、ループ長Ｎが十分に大きければＱｐ１ａ＜＜Ｑｐ１ｂは明らかなので、Ｑｐ１≒Ｑｐ１ｂとしてもよい。
【００９５】
同様に、出力プログラム１２の１０〜１２行目のループの実行コストをＱｐ３ａ、１３〜１５行目のｉｆ文の実行コストをＱｐ３ｂとすると、Ｑｐ３＝Ｑｐ３ａ＋Ｑｐ３ｂであるが、ループ長Ｎが十分に大きければＱｐ３ａ＞＞Ｑｐ３ｂは明らかなので、Ｑｐ３≒Ｑｐ３ａとしてよい。
【００９６】
以上より、Ｑｐ≒Ｑｐ１ｂ＋Ｑｐ２＋Ｑｐ３ａと近似できる。Ｑｐ１ｂ、Ｑｐ２、Ｑｐ３ａが対象とするループは、最近のＦＰＧＡ向けコンパイラ、例えばＩｎｔｅｌ  ＨＬＳコンパイラであれば、容易にパイプライン並列化が可能である。そこで、これら３ループのパイプライン実行開始コストをそれぞれＳ１、Ｓ２、Ｓ３、パイプライン開始間隔をそれぞれＩＩ１、ＩＩ２、ＩＩ３とすると、パイプライン実行コスト＝パイプライン実行開始コスト＋パイプライン開始間隔×（ループ長−１）を用いて、
Ｑｐ１ｂ＝Ｓ１＋ＩＩ１＊（Ｎ−１）
Ｑｐ２＝Ｓ２＋ＩＩ２＊（Ｎ−１）
Ｑｐ３ａ＝Ｓ３＋ＩＩ３＊（Ｎ−１）
と書き表すことができる。
【００９７】
パイプライン実行開始コストＳ１、Ｓ２、Ｓ３はループ本体の実行コストＬに対して十分小さいのでＳ１≦Ｌ、Ｓ２≦Ｌ、Ｓ３≦Ｌを仮定し、ＩＩ＝ｍａｘ（ＩＩ１，  ＩＩ２，  ＩＩ３）とすると、
Ｑｐ＝Ｑｐ１ｂ＋Ｑｐ２＋Ｑｐ３ａ
＝｛Ｓ１＋ＩＩ１＊（Ｎ−１）｝＋  ｛Ｓ２＋ＩＩ２＊（Ｎ−１）｝＋  ｛Ｓ３＋ＩＩ３＊（Ｎ−１）｝
≦｛Ｌ＋ＩＩ＊（Ｎ−１）｝＋  ｛Ｌ＋ＩＩ＊（Ｎ−１）｝＋  ｛Ｌ＋ＩＩ＊（Ｎ−１）｝        ≦３＊｛Ｌ＋ＩＩ＊（Ｎ−１）｝
＜３＊（Ｌ＋ＩＩ＊Ｎ）
となる。
【００９８】
Ａ＝Ｑｃ／Ｑｐ
＞（Ｌ＊Ｎ／２）／｛３＊（Ｌ＋ＩＩ＊Ｎ）｝
＞Ｌ＊Ｎ／（Ｌ＋ＩＩ＊Ｎ）／６
となる。
【００９９】
ＩＩは必ず１サイクル以上の数になるので、前記Ｎ＞＞ＬよりＬ＋ＩＩ＊Ｎ≒ＩＩ＊Ｎとすることができる。
【０１００】
以上より、
Ａ＞  Ｌ＊Ｎ／（Ｌ＋ＩＩ＊Ｎ）／６＞Ｌ＊Ｎ／（ＩＩ＊Ｎ）／６
＞Ｌ／ＩＩ／６
となり、Ｌ／ＩＩ／６＞１かどうかを判定すれば、ＦＰＧＡを利用したほうが高速実行できるかどうかが判定可能である。
【０１０１】
図２５は、アクセラレータ選択係数計算部４０ｄ２のＦＰＧＡ向けのフローチャートである。
最初に、ステップ４０ｄ２ａで、前記変換対象ループのループ本体を取り出し、ループ本体のＣＰＵでの計算時間Ｌを求める。これは、入力プログラム１０のループ本体を解析して、各変数のメモリアクセスにかかるサイクル数と演算にかかるサイクル数の和をとればよい。
【０１０２】
次に、ステップ４０ｄ２ｂで、前記変換対象ループをコピーしたコピーループを作成する。次に前記コピーループに対して単一ループ変換部５０ｃを適用する。単一ループ変換部５０ｃの出力の一例は出力プログラム１２と同じプログラムである。次にステップ４０ｄ２ｃでは、前記出力プログラム１２の前記初期化ループ（２〜４行目）、前記本体変換後ループ（５〜９行目）、前記終了処理ループ（１０〜１２行目）のパイプライン開始間隔ＩＩ１、ＩＩ２、ＩＩ３を求め、そこからＩＩ＝ｍａｘ（ＩＩ１，  ＩＩ２，  ＩＩ３）を求める。
【０１０３】
各ループのパイプライン開始間隔は、出力プログラム１２を高位合成処理系、例えばＩｎｔｅｌ  ＨＬＳコンパイラに入力して、その出力メッセージから求めることができる。
【０１０４】
次に、ステップ４０ｄ２ｄでＬ／ＩＩ／６＞１かどうか計算し、Ｌ／ＩＩ／６＞１であれば（分岐Ｙｅｓ）ステップ４０ｄ２ｅでアクセラレータ選択係数計算部４０ｄ２がＯＫを返し、そうでなければ（分岐Ｎｏ）ステップ４０ｄ２ｆでＮＧを返す。
【０１０５】
入力プログラム１０をプログラム変換処理１８で変換した出力プログラム１２は、初期化ループと終了処理ループがループ繰り返しにまたがる変数依存関係（ループ運搬フロー依存）を持たないループであり、変換後本体ループが総和型ループである。このため、従来技術の並列化コンパイラ、例えばＩｎｔｅｌ（登録商標）  ＨＬＳコンパイラで容易にパイプライン並列化が可能なものであり、入力プログラム１０の実行時間より出力プログラム１２の実行時間のほうが短くなることが期待できる。
【０１０６】
例えば、入力プログラム１０、出力プログラム１２と同等のプログラムを、アクセラレータ向けプログラミング言語であるＯｐｅｎＣＬ言語で記述し、Ｉｎｔｅｌ（登録商標）  ＨＬＳコンパイラと同じ最適化処理を持つＩｎｔｅｌ（登録商標）  ＦＰＧＡ  ＳＤＬ  ｆｏｒ  ＯｐｅｎＣＬコンパイラでコンパイルした場合、入力プログラム１０と同等のＯｐｅｎＣＬプログラムは実行サイクル数が５０サイクルであるが、出力プログラム１２と同等のＯｐｅｎＣＬプログラムはループパイプライン化が適用され、実行サイクル数が１０サイクルと、約５倍に高速化される。
【実施例３】
【０１０７】
実施例３は、アクセラレータがＧＰＵと指示文で指定された場合にプログラムを変換する場合の計算機処理方法である。図２６を参照して、実施例３に対応した入力プログラム１０の一例について説明する。
【０１０８】
図５の入力プログラム１０と比較すると、１行目の指示文に、指示文本体に付随するオプショナルな文字列「ＧＰＵ」が新たに加わっている。
【０１０９】
図２７は、実施例３に対応した、実行コストチェック部４０ｄのフローチャートである。
【０１１０】
ステップ４０ｄ１ｂで、変換候補ループテーブル１６の２行目に登録されたデバイス種別がＧＰＵであるか確認し、ＧＰＵであれば（分岐Ｙｅｓ）アクセラレータ選択係数計算部４０ｄ２を実行し、ＧＰＵでなければ（分岐Ｎｏ）実行コストチェック部４０ｄを終了する。アクセラレータ選択係数計算部４０ｄ２の実行後はステップ４０ｄ３を実行して、アクセラレータ選択係数計算部の返値がＯＫか調べ、ＯＫであれば（分岐Ｙｅｓ）変換候補ループテーブル１６の実行コストフラグをＯＫにして実行コストチェック部４０ｄを終了し、そうでなければ（分岐Ｎｏ）実行コストチェック部４０ｄを終了する。
【０１１１】
ここで、ＧＰＵ向けのアクセラレータ選択係数の計算方法について説明する。変換候補ループとして入力プログラム１０、変換候補ループを本発明の方式で変換した変換後ループとして出力プログラム１２を例に用いる、入力プログラム１０の平均実行コストをＱｃ、出力プログラム１２の実行コストをＱｐとし、アクセラレータ選択係数Ａ＝Ｑｃ／Ｑｐと定義すると、Ａ＞１であれば変換後ループの実行コストのほうが小さい、すなわちＣＰＵ実行よりもＧＰＵ実行のほうが高速に実行できることになる。
【０１１２】
ここで、入力ループ１０のループ長をＮ、ループ本体の実行コストをＬとする。入力ループ１０はどのループ繰り返しでループを飛び出すか実行するまで分からないが、平均的にはループ長Ｎの１／２だけループ繰り返しを実行したところでループを飛び出すと仮定する。するとＱｃ＝Ｌ＊Ｎ／２と書くことができる。そこで、出力プログラム１２の１〜４行目の前記初期化処理の実行コストをＱｐ１、５〜９行目のループの実行コストをＱｐ２、１０〜１５行目の前記終了処理の実行コストをＱｐ３とすると、Ｑｐ＝Ｑｐ１＋Ｑｐ２＋Ｑｐ３となる。
【０１１３】
出力プログラム１行目の代入文の実行コストをＱｐ１ａ、２〜４行目のループの実行コストをＱｐ１ｂとすると、Ｑｐ１＝Ｑｐ１ａ＋Ｑｐ１ｂであるが、ループ長Ｎが十分に大きければＱｐ１ａ＜＜Ｑｐ１ｂは明らかなので、Ｑｐ１≒Ｑｐ１ｂとしてもよい。
【０１１４】
同様に、出力プログラム１２の１０〜１２行目のループの実行コストをＱｐ３ａ、１３〜１５行目のｉｆ文の実行コストをＱｐ３ｂとすると、Ｑｐ３＝Ｑｐ３ａ＋Ｑｐ３ｂであるが、ループ長Ｎが十分に大きければＱｐ３ａ＞＞Ｑｐ３ｂは明らかなので、Ｑｐ３≒Ｑｐ３ａとしてよい。以上より、Ｑｐ≒Ｑｐ１ｂ＋Ｑｐ２＋Ｑｐ３ａと近似できる。
【０１１５】
Ｑｐ１ｂ、Ｑｐ２、Ｑｐ３ａが対象とするループは、最近のＧＰＵ向けコンパイラ、例えばＰＧＩアクセラレータコンパイラであれば、容易にループ並列化が可能である。そこで、これら３ループのループ本体の実行コストをＬ１、Ｌ２、Ｌ３、並列実行に利用するＧＰＵのコア数をｐとすると、
Ｑｐ≒Ｑｐ１ｂ＋Ｑｐ２＋Ｑｐ３ａ＝Ｌ１＊Ｎ／ｐ＋Ｌ２＊Ｎ／ｐ＋Ｌ３＊Ｎ／ｐ＝（Ｌ１＋Ｌ２＋Ｌ３）＊Ｎ／ｐ
となる。
【０１１６】
Ｌ１≒Ｌ、Ｌ２≒Ｌ、Ｌ３≒Ｌは入力プログラム１０、出力プログラム１２より明らかなので、
Ｑｐ≒３＊Ｌ＊Ｎ／ｐ
となる。
【０１１７】
以上より
Ａ＝Ｑｃ／Ｑｐ≒（Ｌ＊Ｎ／２）／（３＊Ｌ＊Ｎ／ｐ）＝ｐ／６
と書き表すことができ、ｐ／６＞１かどうかを判定すれば、ＧＰＵを利用したほうが高速実行できるかどうかが判定可能である。以上でＧＰＵ向けのアクセラレータ選択係数の計算方法の説明を終了する。
【０１１８】
図２８は、アクセラレータ選択係数計算部４０ｄ２のＧＰＵ向けのフローチャートである。
最初に、ステップ４０ｄ２ｇで、ＧＰＵの実行コア数ｐを求める。これは、例えばｌｓｇｐｕコマンドの出力から求めることができる。次にステップ４０ｄ２ｈで、ｐ／６＞１か調べ、ｐ／６＞１であれば（分岐Ｙｅｓ）ステップ４０ｄ２ｉでアクセラレータ選択係数計算部４０ｄ２がＯＫを返し、そうでなければ（分岐Ｎｏ）ステップ４０ｄ２ｊでＮＧを返す。以上で図２８の説明を終了する。
【０１１９】
入力プログラム１０をプログラム変換処理１８で変換した出力プログラム１２は、初期化ループと終了処理ループがループ繰り返しにまたがる変数依存関係（ループ運搬フロー依存）を持たないループであり、変換後本体ループが総和型ループであるため、従来技術の並列化コンパイラ、例えばＰＧＩアクセラレータコンパイラで容易にループ並列化が可能なものであり、入力プログラム１０の実行時間より出力プログラム１２の実行時間のほうが短くなることが期待できる。
【符号の説明】
【０１２０】
１  計算機システム
２  主記憶装置
３  ＣＰＵ
４  アクセラレータ
５  外部記憶装置
６  入出力装置
１０  入力プログラム
１２  出力プログラム
１６  変換候補ループテーブル
１８  プログラム変換処理部
３０  指示文解析部
４０  ループ解析部
５０  ループ変換部
【図１】
2019219992.tif 000003
【図２】
2019219992.tif 000004
【図３】
2019219992.tif 000005
【図４】
2019219992.tif 000006
【図５】
2019219992.tif 000007
【図６】
2019219992.tif 000008
【図７】
2019219992.tif 000009
【図８】
2019219992.tif 000010
【図９】
2019219992.tif 000011
【図１０】
2019219992.tif 000012
【図１１】
2019219992.tif 000013
【図１２】
2019219992.tif 000014
【図１３】
2019219992.tif 000015
【図１４】
2019219992.tif 000016
【図１５】
2019219992.tif 000017
【図１６】
2019219992.tif 000018
【図１７】
2019219992.tif 000019
【図１８】
2019219992.tif 000020
【図１９】
2019219992.tif 000021
【図２０】
2019219992.tif 000022
【図２１】
2019219992.tif 000023
【図２２】
2019219992.tif 000024
【図２３】
2019219992.tif 000025
【図２４】
2019219992.tif 000026
【図２５】
2019219992.tif 000027
【図２６】
2019219992.tif 000028
【図２７】
2019219992.tif 000029
【図２８】
2019219992.tif 000030