(57)【特許請求の範囲】
【請求項１】
コンピュータに、
プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、前記第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定し、
前記プログラムを、前記配列変数の要素の先頭に、特定した前記段数分の要素を追加したプログラムに変換する、
処理を実行させることを特徴とする変換プログラム。
【請求項２】
前記変換する処理は、さらに、前記第１の演算にかかるサイクル数が前記第２の演算にかかるサイクル数より大きい場合、前記段数分の要素を追加したプログラムを、前記配列変数の要素間に、前記第１の演算にかかるサイクル数と前記第２の演算にかかるサイクル数との差の分の要素を追加したプログラムに変換することを特徴とする請求項１に記載の変換プログラム。
【請求項３】
前記特定する処理は、前記複数の演算に用いられる演算回路の数と、スカラ変数に対して割り当てられた第１の記憶領域のサイズと、前記第１の記憶領域に同時にアクセス可能な演算回路の数と、配列変数に対して割り当てられた第２の記憶領域のサイズと、前記第２の記憶領域に同時にアクセス可能な演算回路の数と、に基づいて、前記段数を特定することを特徴とする請求項１または２に記載の変換プログラム。
【請求項４】
コンピュータが、
プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、前記第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定し、
前記プログラムを、前記配列変数の要素の先頭に、特定した前記段数分の要素を追加したプログラムに変換する、
処理を実行することを特徴とする変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変換プログラム、および変換方法に関する。
【背景技術】
【０００２】
従来、複数の演算を複数の段階に分けて、演算ごとにＰＥ（Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔ）を割り当てて、複数の演算が実行される場合がある。このとき、複数の段階のうちにメモリなどのハードウェア資源を共有する２つの段階があると、前段の演算の終了まで後段の演算の開始を待ち合わせることになる。待ち合わせは、例えば、ＰＥを用いてＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）を実行することにより行われる。ＮＯＰとは、何も演算せずに待機することである。
【０００３】
関連する技術としては、例えば、同期命令に応じてパイプライン演算器のパイプライン接続の実行開始タイミングを制御するものがある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−５４０３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術では、複数の段階のうちにハードウェア資源を共有する２つの段階がある場合には、複数の演算の各々の演算を割り当てた演算回路以外に、待ち合わせを行うために別の演算回路を用意することになる。
【０００６】
１つの側面では、本発明は、複数の演算を実行するために用いられる演算回路の数の増加を抑制することができる変換プログラム、および変換方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、前記第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定し、前記プログラムを、前記配列変数の要素の先頭に、特定した前記段数分の要素を追加したプログラムに変換する変換プログラム、および変換方法が提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、複数の演算を実行するために用いられる演算回路の数を低減することができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、変換装置１００のプログラム変換処理の一例を示す説明図である。
【図２】図２は、実施の形態にかかる変換装置１００のハードウェア構成例や対象デバイスのハードウェア構成例を示すブロック図である。
【図３】図３は、オペランド情報３００の記憶内容の一例を示す説明図である。
【図４】図４は、実行サイクル情報４００の記憶内容の一例を示す説明図である。
【図５】図５は、メモリ情報５００の記憶内容の一例を示す説明図である。
【図６】図６は、変換装置１００の機能的構成例を示すブロック図である。
【図７】図７は、変換前プログラムＰ１の一例を示す説明図である。
【図８】図８は、変換装置１００の変換処理の一例を示す説明図である。
【図９】図９は、変換後プログラムＰ２の一例を示す説明図である。
【図１０】図１０は、変換後プログラムＰ２の実行の一例を示す説明図である。
【図１１】図１１は、サイクル数に差がある場合の変換装置１００の変換処理の一例を示す説明図である。
【図１２】図１２は、サイクル数に差がある場合の変換後プログラムＰ３の実行の一例を示す説明図（その１）である。
【図１３】図１３は、サイクル数に差がある場合の変換後プログラムＰ３の実行の一例を示す説明図（その２）である。
【図１４】図１４は、サイクル数に差がある場合の変換後プログラムＰ３の実行の一例を示す説明図（その３）である。
【図１５】図１５は、変換装置１００の変換処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明にかかる変換プログラム、および変換方法の実施の形態を詳細に説明する。
【００１１】
（変換装置１００のプログラム変換処理の一例）
図１は、変換装置１００のプログラム変換処理の一例を示す説明図である。変換装置１００は、変換プログラムを実行するコンピュータである。変換装置１００は、例えば、変換対象となるプログラムＰ１を、配列の先頭にダミー要素を追加したプログラムＰ２に変換する。
【００１２】
以下の説明では、変換対象となるプログラムＰ１を「変換前プログラムＰ１」と表記する場合がある。変換前プログラムＰ１とは、複数の段階に分けて実行される配列を用いた複数の演算を規定したプログラムである。また、以下の説明では、変換装置１００が変換したプログラムＰ２を「変換後プログラムＰ２」と表記する場合がある。
【００１３】
図１の例では、変換前プログラムＰ１は、配列ａ［Ｎ］およびｂ［Ｎ］についての複数の演算となる多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」を規定したプログラムである。ここで、変数ｉは、１〜Ｎの自然数である。
【００１４】
多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」は、複数の段階に分けて並列実行される。多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」は、例えば、第１の演算「ｂ［ｉ］×ｃ」を行う第１の段階と、第２の演算「第１の演算「ｂ［ｉ］×ｃ」の演算結果×ａ［ｉ］」を行う第２の段階と、に分けて実行される。以下の説明では、第１の演算「ｂ［ｉ］×ｃ」の演算結果を「ｙ［ｉ］」と表記する場合がある。
【００１５】
ここで、変換装置１００は、第１の演算を行う第１の段階から第２の演算を行う第２の段階までの段数「１」を特定する。次に、変換装置１００は、変換前プログラムＰ１に規定された第２の演算に用いる配列ａ［Ｎ］を、特定した段数「１」の分のダミー要素を先頭に追加した配列ａ［１＋Ｎ］に変換する。以下の説明では、便宜上、ダミー要素を先頭に追加する前の配列ａ［Ｎ］と、追加した後の配列ａ［１＋Ｎ］と、を区別するために、追加した後の配列ａ［１＋Ｎ］を「ａ’［１＋Ｎ］」と表記する場合がある。
【００１６】
ここで、配列ａ［Ｎ］の各々の要素ａ［ｉ］は、配列ａ’［１＋Ｎ］の各々の要素ａ’［ｉ＋１］に置換される。換言すれば、要素ａ’［０］はダミー要素として追加され、要素ａ［０］は要素ａ’［１］に、要素ａ［１］は要素ａ’［２］に、・・・、要素ａ［Ｎ］は要素ａ’［１＋Ｎ］に置換される。
【００１７】
これにより、１サイクル目において、第１の演算「ｂ［０］×ｃ」が実行される時には、第２の演算「ｙ［］×ａ’［０］」がダミーとして並列実行される。このため、変換装置１００は、第２の演算において、第１の演算の演算結果ｙ［０］が入力される前に、演算「ｙ［］×ａ’［１］（＝ａ［０］）」が実行されて、多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」が失敗することを防止することができる。
【００１８】
結果として、変換後プログラムＰ２を実行するコンピュータは、第２の演算の前にＮＯＰを用いて配列ａ［Ｎ］の要素の入力を遅延させなくてもよくなり、複数の演算を実行するために用いられるリソースの増加を抑制することができる。ここで、リソースとは、ＰＥである。このため、変換後プログラムＰ２を実行するコンピュータは、限られたリソースをＮＯＰに割り当てることなく、リソースをＮＯＰ以外の演算に割り当てることができるため、リソースを有効に活用することができる。また、変換後プログラムＰ２を実行するコンピュータは、ＮＯＰにリソースを割り当てなくてもよいため、より多くのリソースを使用する演算を実現することができる。変換後プログラムＰ２を実行するコンピュータは、変換装置１００であってもよいし、変換装置１００とは異なる別デバイスであってもよい。
【００１９】
（変換装置１００のハードウェア構成例）
図２は、実施の形態にかかる変換装置１００のハードウェア構成例や対象デバイスのハードウェア構成例を示すブロック図である。図２において、変換装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、メモリ（Ｍｅｍｏｒｙ）２０２と、ＰＥ−Ａｒｒａｙ２０３と、ペリフェラル（Ｐｅｒｉｐｈｅｒａｌ）２０４と、を有する。また、各構成部はバス２００によってそれぞれ接続されている。
【００２０】
ここで、ＣＰＵ２０１は、変換装置１００の全体の制御を司る。メモリ２０２は、ブートプログラムや変換プログラムなどのプログラムを記憶している。また、メモリ２０２は、ＣＰＵ２０１のワークエリアとして使用される。ＰＥ−Ａｒｒａｙ２０３は、配列状に配置された複数のＰＥを有する。ＰＥは、各々、並列してパイプライン処理を行う。
【００２１】
ペリフェラル２０４とは、周辺機器である。ペリフェラル２０４は、例えば、磁気ディスクドライブ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ディスプレイ、キーボード、マウス、スキャナ、またはプリンタなどである。
【００２２】
磁気ディスクドライブは、ＣＰＵ２０１の制御にしたがって磁気ディスクに対するデータのリード／ライトを制御する。ディスプレイは、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。ディスプレイは、例えば、液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００２３】
キーボードは、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウスは、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００２４】
スキャナは、画像を光学的に読み取り、変換装置１００内に画像データを取り込む。なお、スキャナは、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を有してもよい。また、プリンタは、画像データや文書データを印刷する。
【００２５】
（オペランド情報３００の記憶内容の一例）
次に、図３を用いて、オペランド情報３００の記憶内容の一例について説明する。オペランド情報３００は、例えば、図２に示したメモリ２０２などの記憶領域によって実現される。
【００２６】
図３は、オペランド情報３００の記憶内容の一例を示す説明図である。図３に示すように、オペランド情報３００は、命令ごとに、当該命令についての入力の数と、当該命令についての出力の数と、を記憶する。図３の例では、オペランド情報３００は、加算命令と、入力の数「２」と、出力の数「１」と、を対応付けて記憶する。
【００２７】
（実行サイクル情報４００の記憶内容の一例）
次に、図４を用いて、実行サイクル情報４００の記憶内容の一例について説明する。実行サイクル情報４００は、例えば、図２に示したメモリ２０２などの記憶領域によって実現される。
【００２８】
図４は、実行サイクル情報４００の記憶内容の一例を示す説明図である。図４に示すように、実行サイクル情報４００は、命令ごとに、当該命令の実行にかかるサイクルの数を記憶する。図４の例では、実行サイクル情報４００は、加算命令と、加算命令の実行にかかるサイクルの数「１」と、を対応付けて記憶する。
【００２９】
（メモリ情報５００の記憶内容の一例）
次に、図５を用いて、メモリ情報５００の記憶内容の一例について説明する。メモリ情報５００は、例えば、図２に示したメモリ２０２などの記憶領域によって実現される。
【００３０】
図５は、メモリ情報５００の記憶内容の一例を示す説明図である。図５に示すように、メモリ情報５００は、記憶領域ごとに、当該記憶領域のサイズと、当該記憶領域に同時にアクセス可能な演算回路の数と、を記憶する。図５の例では、メモリ情報５００は、スカラ変数に割り当てられた記憶領域と、当該記憶領域のサイズ「２ｋＷｏｒｄ」と、同時アクセス可能なデータ数「３２」と、を記憶する。
【００３１】
（変換装置１００の機能的構成例）
次に、図６を用いて、変換装置１００の機能的構成例について説明する。
【００３２】
図６は、変換装置１００の機能的構成例を示すブロック図である。変換装置１００は、特定部６０１と、変換部６０２と、制御部６０３と、を含む。特定部６０１と、変換部６０２と、制御部６０３とは、例えば、図２に示したメモリ２０２などの記憶装置に記憶されたプログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。また、変換装置１００は、特定部６０１、変換部６０２と制御部６０３は別であってもよい。すなわち、変換部６０２から得た結果を対象となる別デバイスの制御部６０３へ反映することができる。
【００３３】
ここで、変換装置１００は、変換前プログラムＰ１において、第１の段階に実行される第１の演算の結果を、第２の段階に実行される第２の演算が用いる場合に、変換前プログラムＰ１を変換後プログラムＰ２に変換する動作を行うことができる。以下の説明では、変換前プログラムＰ１を変換後プログラムＰ２に変換する動作を「第１の動作」と表記する場合がある。
【００３４】
また、変換装置１００は、第１の段階に実行される第１の演算のサイクル数が、第２の段階に実行される第２の演算のサイクル数より大きい場合に、変換後プログラムＰ２をさらに変換後プログラムＰ３に変換する動作を行うことができる。以下の説明では、変換後プログラムＰ２をさらに変換後プログラムＰ３に変換する動作を「第２の動作」と表記する場合がある。
【００３５】
また、変換装置１００は、変換後プログラムＰ２、または変換後プログラムＰ３を、ＰＥ−Ａｒｒａｙ２０３を用いて並列実行する動作を行うことができる。以下の説明では、変換後プログラムＰ２、または変換後プログラムＰ３を、ＰＥ−Ａｒｒａｙ２０３を用いて並列実行する動作を「第３の動作」と表記する場合がある。
【００３６】
＜第１の動作＞
まず、第１の動作について説明する。第１の動作は、上述したように、変換前プログラムＰ１において、第１の段階に実行される第１の演算の結果を、第２の段階に実行される第２の演算が用いる場合に、変換前プログラムＰ１を変換後プログラムＰ２に変換する動作である。第１の動作は、特定部６０１と、変換部６０２と、によって実現される。
【００３７】
特定部６０１は、プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定する。
【００３８】
ここで、プログラムとは、コンピュータに対する命令を記述したデータである。プログラムとは、例えば、Ｃ言語で記述されたソースコードである。プログラムとは、具体的には、上述した変換前プログラムＰ１であって、複数の段階に分けて実行される複数の演算が規定されたデータである。変換前プログラムＰ１の一例は、図７に後述する。
【００３９】
複数の段階に分けて実行される複数の演算とは、数の演算子を含む演算である。複数の段階に分けて実行される複数の演算とは、例えば、多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」である。第１の演算とは、複数の演算に含まれる演算のうちのいずれかの演算である。第１の演算とは、例えば、多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」のうちの演算「ｂ［ｉ］×ｃ」である。また、第２の演算とは、第１の演算以降に実行される演算であって、第１の演算の演算結果と、配列変数と、を用いた演算である。第２の演算とは、例えば、多項式の演算「ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］」のうちの演算「ｙ［ｉ］×ａ［ｉ］」である。
【００４０】
特定部６０１は、例えば、複数の演算に用いられる演算回路の数と、第１の記憶領域のサイズと、第１の記憶領域の同時アクセス可能数と、第２の記憶領域のサイズと、第２の記憶領域の同時アクセス可能数と、に基づいて、段数を特定する。
【００４１】
ここで、演算回路とは、複数の演算のいずれかの演算が割り当てられて実行される回路である。演算回路とは、例えば、上述したＰＥ−Ａｒｒａｙ２０３に含まれるＰＥである。第１の記憶領域とは、スカラ変数に対して割り当てられた領域である。第１の記憶領域とは、例えば、メモリ２０２内の領域である。第１の記憶領域の同時アクセス可能数とは、第１の記憶領域に同時にアクセス可能な演算回路の数である。第２の記憶領域とは、配列変数に対して割り当てられた領域である。配列変数は、上述したベクトル変数である。第２の記憶領域の同時アクセス可能数とは、第２の記憶領域に同時にアクセス可能な演算回路の数である。
【００４２】
特定部６０１は、具体的には、オペランド情報３００と、実行サイクル情報４００と、メモリ情報５００と、に基づいて、変換前プログラムＰ１をコンパイルして、コントロールデータフローグラフ（ＣＤＦＧ：Ｃｏｎｔｒｏｌ／Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ）を作成する。ここで、ＣＤＦＧは、分岐やループなどの制御の流れを表すコントロールグラフと、演算間のデータの流れを表すデータフローグラフと、を含む。次に、特定部６０１は、タイミング情報をトレースして、タイミング調整を行い、配列変数に対して用いられるＮＯＰの数を特定する。これにより、特定部６０１は、配列に追加すべきダミー要素の数を特定することができる。特定されたデータは、例えば、メモリ２０２などの記憶装置に記憶される。
【００４３】
変換部６０２は、プログラムを、配列変数の要素の先頭に、特定した段数分の要素を追加したプログラムに変換する。変換部６０２は、例えば、変換前プログラムＰ１に規定された配列変数の先頭の要素に、特定部６０１によって特定されたＮＯＰの数の分のダミー要素を追加することにより、変換後プログラムＰ２を作成する。変換部６０２は、具体的には、変換前プログラムＰ１に規定された配列ａ［Ｎ］を配列ａ’［ｓ＋Ｎ］に変換して、変換後プログラムＰ２を作成する。ｓは、ＮＯＰの数である。
【００４４】
ここで、配列ａ［Ｎ］の各々の要素ａ［ｉ］は、配列ａ’［ｓ＋Ｎ］の各々の要素ａ’［ｓ＋ｉ］に置換される。換言すれば、ｓが「１」の場合であれば、要素ａ［０］はダミー要素として追加され、要素ａ［０］は要素ａ’［１］に、要素ａ［１］は要素ａ’［２］に、・・・、要素ａ［Ｎ］は要素ａ’［１＋Ｎ］に置換される。
【００４５】
これにより、変換部６０２は、ＮＯＰを用いなくても配列変数を遅延させることができる変換後プログラムＰ２を作成することができる。変換後プログラムＰ２は、例えば、メモリ２０２などの記憶装置に記憶される。また、変換部６０２は、変換後プログラムＰ２を出力してもよい。出力形式としては、例えば、ディスプレイへの表示、プリンタへの印刷出力、Ｉ／Ｆによる外部装置への送信がある。
【００４６】
＜第２の動作＞
次に、第２の動作について説明する。第２の動作は、上述したように、第１の段階に実行される第１の演算のサイクル数が、第２の段階に実行される第２の演算のサイクル数より大きい場合に、変換後プログラムＰ２をさらに変換後プログラムＰ３に変換する動作である。第２の動作は、変換部６０２によって実現される。
【００４７】
変換部６０２は、さらに、第１の演算にかかるサイクル数が第２の演算にかかるサイクル数より大きい場合、段数分の要素を追加したプログラムを変換する。この場合、変換部６０２は、段数分の要素を追加したプログラムを、配列変数の要素間に、第１の演算にかかるサイクル数と第２の演算にかかるサイクル数との差の分の要素を追加したプログラムに変換する。
【００４８】
変換部６０２は、例えば、第１の演算にかかるサイクル数が「２」、第２の演算にかかるサイクル数が「１」である場合、第１の演算にかかるサイクル数が第２の演算にかかるサイクル数より大きいと判定する。次に、変換部６０２は、第１の演算にかかるサイクル数が「２」と第２の演算にかかるサイクル数が「１」との差「１」を算出する。そして、変換部６０２は、変換後プログラムＰ２に規定された配列変数ａ［１＋Ｎ］の要素間に、算出した差「１」の分のダミー要素を追加して、変換後プログラムＰ３を作成する。
【００４９】
すなわち、変換部６０２は、配列ａ［１＋Ｎ］を、配列ａ［１＋ｄ×Ｎ＋Ｎ］に変換する。ｄは、第１の演算にかかるサイクル数と第２の演算にかかるサイクル数との差である。以下の説明では、便宜上、ダミー要素を要素間に追加する前の配列ａ［１＋Ｎ］と、追加した後の配列ａ［１＋ｄ×Ｎ＋Ｎ］と、を区別するために、追加した後の配列ａ［１＋Ｎ］を「ａ”［１＋ｄ×Ｎ＋Ｎ］」と表記する場合がある。
【００５０】
ここで、配列ａ［Ｎ］の各々の要素ａ［ｉ］は、配列ａ”［ｓ＋ｄＮ＋Ｎ］の各々の要素ａ”［ｓ＋ｄｉ＋ｉ］に置換される。換言すれば、ｓが「１」、ｄが「１」の場合であれば、要素ａ”［０］は段数分のダミー要素として追加される。また、この場合であれば、要素ａ”［１］はサイクル数の差の分のダミー要素として追加され、要素ａ”［３］はサイクル数の差の分のダミー要素として追加され、・・・要素ａ”［２Ｎ］はサイクル数の差の分のダミー要素として追加される。また、この場合であれば、要素ａ［０］は要素ａ”［２］に、要素ａ［１］は要素ａ”［４］に、・・・、要素ａ［Ｎ］は要素ａ’［１＋２Ｎ］に置換される。
【００５１】
これにより、変換部６０２は、サイクル数が異なる場合であっても、ＮＯＰを用いなくても配列変数を遅延させることができる変換後プログラムＰ３を作成することができる。変換後プログラムＰ３は、例えば、メモリ２０２などの記憶装置に記憶される。また、変換部６０２は、変換後プログラムＰ３を出力してもよい。出力形式としては、例えば、ディスプレイへの表示、プリンタへの印刷出力、Ｉ／Ｆによる外部装置への送信がある。
【００５２】
＜第３の動作＞
次に、第３の動作について説明する。第３の動作は、変換後プログラムＰ２、または変換後プログラムＰ３を、ＰＥ−Ａｒｒａｙ２０３を用いて並列実行する動作である。第３の動作は、制御部６０３によって実現される。
【００５３】
制御部６０３は、第１の演算を第１の演算回路に割り当てて、第２の演算を第２の演算回路に割り当てて、第１の演算と第２の演算とを並列実行させる。制御部６０３は、例えば、変換後プログラムＰ２、または変換後プログラムＰ３をコンパイルして、タイミング調整を行って、ＰＥ−Ａｒｒａｙ２０３に演算を割り振って並列実行させる。また、制御部６０３は、バリッド信号をＰＥ−Ａｒｒａｙ２０３に送信して、ダミー要素を用いた演算の演算結果を破棄させてもよい。
【００５４】
ここで、第２の演算回路は、追加した要素にかかる演算結果を破棄する。ＰＥは、例えば、ダミー要素を用いた演算の演算結果を破棄して、出力となる配列変数ｘ［Ｎ］に記憶しない。また、第２の演算回路は、追加した要素にかかる演算結果を、配列変数の要素のうちの末尾から段数分の要素で上書きしてもよい。ＰＥは、例えば、ダミー要素を用いた演算の演算結果を出力となる配列変数ｘ［Ｎ］に記憶するが、元々の配列変数の要素を用いた演算の演算結果で上書きする。
【００５５】
（変換前プログラムＰ１の一例）
次に、図７を用いて、変換前プログラムＰ１の一例について説明する。
【００５６】
図７は、変換前プログラムＰ１の一例を示す説明図である。図７に示すように、変換前プログラムＰ１の１行目は、定義文であって、「Ｎ」を「１０」と定義する。変換前プログラムＰ１の４行目〜２０行目は、ｍａｉｎ関数である。変換前プログラムＰ１の６行目〜９行目は、変数宣言であって、ｉｎｔ型の配列ａ［Ｎ］とｂ［Ｎ］とを宣言し、ｉｎｔ型の変数ｃ＝１０を宣言し、ｉｎｔ型の配列ｘ［Ｎ］を宣言し、ｉｎｔ型の変数ｉを宣言する。
【００５７】
変換前プログラムＰ１の１１行目〜１４行目は、ループ文である。変換前プログラムＰ１の１２行目は、代入文であって、ａ［ｉ］にｉを代入する。変換前プログラムＰ１の１３行目は、代入文であって、ｂ［ｉ］にｉ×１０を代入する。変換前プログラムＰ１の１６行目〜１８行目は、ループ文である。変換前プログラムＰ１の１７行目は、多項式の演算ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［ｉ］を行う文である。
【００５８】
（変換装置１００の変換処理の一例）
次に、図８を用いて、図７に示した変換前プログラムＰ１を変換する場合に行われる変換装置１００の変換処理の一例について説明する。
【００５９】
図８は、変換装置１００の変換処理の一例を示す説明図である。図８において、変換装置１００は、変数の定義を行う。変換装置１００は、例えば、メモリ情報５００に基づいて、配列ａ［１０］、ｂ［１０］、およびｘ［１０］、をベクタ領域に割り当てる。変換装置１００は、具体的には、ｖＭＥＭ０＝：ａ［１０］、ｖＭＥＭ１＝：ｂ［１０］、およびｖＭＥＭ２＝：ｘ［１０］と割り当てる。
【００６０】
また、変換装置１００は、例えば、メモリ情報５００に基づいて、変数ｃ、およびｉを、スカラ領域に割り当てる。変換装置１００は、具体的には、ｓＭＥＭ０：＝ｃ、およびｓＭＥＭ１：＝ｉと割り当てる。
【００６１】
次に、変換装置１００は、変数入力と変数出力とにかかる演算を、ＰＥに割り当てる。変換装置１００は、例えば、変換前プログラムＰ１の１７行目の演算「ｂ［ｉ］×ｃ」を、ＰＥ１に割り当てる。以下の説明では、演算「ｂ［ｉ］×ｃ」の演算結果を「ｙ［ｉ］」と表記する場合がある。また、変換装置１００は、例えば、変換前プログラムＰ１の１７行目の演算「ｙ［ｉ］×ａ［ｉ］」を、ＰＥ２に割り当てる。また、変換装置１００は、例えば、変換前プログラムＰ１の１１行目の演算「ｉ＜Ｎ」を、ＰＥ３に割り当てる。また、変換装置１００は、例えば、変換前プログラムＰ１の１１行目の演算「ｉ＋＋」を、ＰＥ４に割り当てる。また、変換装置１００は、例えば、変換前プログラムＰ１の１３行目の演算「ｂ［ｉ］＝ｉ×１０」を、ＰＥ５に割り当てる。
【００６２】
そして、変換装置１００は、演算パスを作成する。変換装置１００は、例えば、変換前プログラムＰ１をコンパイルして、ＣＤＦＧを作成する。ＣＤＦＧは、分岐やループなどの制御の流れを表すコントロールグラフと、演算間のデータの流れを表すデータフローグラフと、を含む。次に、変換装置１００は、タイミング情報をトレースする。そして、変換装置１００は、最大レイテンシパスを特定する。
【００６３】
次に、変換装置１００は、タイミング調整を行う。そして、変換装置１００は、タイミング調整において、ＮＯＰを用いるか否かを判定する。次に、変換装置１００は、ＮＯＰを用いると判定した場合、ＮＯＰに対する入力となる変数が、ベクタ領域に割り当てられた変数であるか否かを判定する。そして、変換装置１００は、ベクタ領域に割り当てられた変数である場合、ＮＯＰの数に応じて、ＮＯＰの演算に対する入力となる配列に、ダミー要素を追加する。
【００６４】
変換装置１００は、図７に示した変換前プログラムＰ１の例では、配列ａ［Ｎ］にダミー要素を追加して配列ａ’［１＋Ｎ］に変更して、変換前プログラムＰ１を変換後プログラムＰ２に変換する。ここで、配列ａ［Ｎ］の各々の要素ａ［ｉ］は、配列ａ’［１＋Ｎ］の各々の要素ａ［１＋ｉ］に置換される。換言すれば、要素ａ’［０］はダミー要素として追加され、要素ａ［０］は要素ａ’［１］に、要素ａ［１］は要素ａ’［２］に、・・・、要素ａ［Ｎ］は要素ａ’［１＋Ｎ］に置換される。これにより、変換装置１００は、ＮＯＰを用いなくても実行可能な変換後プログラムＰ２を作成することができる。
【００６５】
（変換後プログラムＰ２の一例）
次に、図９を用いて、図８に示した変換処理によって変換前プログラムＰ１を変換した変換後プログラムＰ２の一例について説明する。
【００６６】
図９は、変換後プログラムＰ２の一例を示す説明図である。変換後プログラムＰ２の２行目では、定義文が追加され、ダミー要素の数「Ｐ＿ＤＥＬＡＹ」が「１」と定義される。変換後プログラムＰ２の６行目では、変数宣言が変換され、ｉｎｔ型の配列ａ［Ｎ］の代わりに、ｉｎｔ型の配列ａ［Ｐ＿ＤＥＬＡＹ＋Ｎ］が宣言される。
【００６７】
変換後プログラムＰ２の１２行目では、代入文が変換され、ａ［Ｐ＿ＤＥＬＡＹ＋ｉ］にｉが代入される。変換後プログラムＰ２の１７行目では、多項式が変換され、多項式の演算ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［Ｐ＿ＤＥＬＡＹ＋ｉ］が行われる。
【００６８】
（変換後プログラムＰ２の実行の一例）
次に、図１０を用いて、変換装置１００による図９に示した変換後プログラムＰ２の実行の一例について説明する。
【００６９】
図１０は、変換後プログラムＰ２の実行の一例を示す説明図である。図１０の例は、変換装置１００が、ＰＥ−Ａｒｒａｙ２０３を用いて、図９に示した変換後プログラムＰ２における１６行目〜１８行目を実行した場合の一例である。
【００７０】
変換装置１００は、多項式の演算ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［１＋ｉ］のうちの演算ｂ［ｉ］×ｃをＰＥ１に割り当てる。また、変換装置１００は、多項式の演算ｘ［ｉ］＝（ｂ［ｉ］×ｃ）×ａ［１＋ｉ］のうちの演算ｙ［ｉ］×ａ［１＋ｉ］をＰＥ２に割り当てる。
【００７１】
図１０において、１サイクル目に、（１）ＰＥ１は、配列ｂ［Ｎ］のうちのｂ［０］と、変数ｃと、を読み出して、演算ｂ［０］×ｃを行う。同時に、（２）ＰＥ２は、配列ａ［１＋Ｎ］のうちのダミー要素となるａ［０］を読み出すが、ＰＥ１の演算結果が入力されていないため、演算結果を破棄して、終了する。これにより、ＰＥ２は、ＮＯＰの代わりに、ダミー要素についてのダミー演算を行う。次に、ＰＥ１とＰＥ２とは、２サイクル目に移行する。
【００７２】
２サイクル目に、（３）ＰＥ１は、配列ｂ［Ｎ］のうちのｂ［１］と、変数ｃと、を読み出して、演算ｂ［１］×ｃを行う。同時に、（４）ＰＥ２は、配列ａ［１＋Ｎ］のうちのａ［１］を読み出して、ＰＥ１の演算が終了しているためＰＥ１の演算結果ｙ［０］を取得して、演算ｙ［０］×ａ［１］を行う。これにより、ＰＥ２は、ＮＯＰがなくても、ｙ［０］と、ａ［１］と、の入力タイミングを同期させて、演算ｙ［０］×ａ［１］を行うことができる。以降のサイクルにおいても、同様に、ＰＥ１とＰＥ２とは、正常に演算を行うことができる。
【００７３】
（サイクル数に差がある場合の変換装置１００の変換処理の一例）
次に、図１１を用いて、第１の演算と、第２の演算と、のサイクル数に差がある場合の変換装置１００の変換処理の一例について説明する。
【００７４】
図１１は、サイクル数に差がある場合の変換装置１００の変換処理の一例を示す説明図である。ここでは、説明の簡略化のため、演算「ｂ［ｉ］×ｃ」が２サイクルかかる演算であるとし、演算「ｙ［ｉ］×ａ［１＋１×ｉ＋ｉ］」が１サイクルかかる演算であるとする。
【００７５】
図１１において、変換装置１００は、ダミー要素を追加した配列ａ［１＋Ｎ］を、配列ａ［１＋Ｎ］の要素間に、さらに演算「ｂ［ｉ］×ｃ」と演算「ｙ［ｉ］×ａ［ｉ］」とのサイクル数の差「１」の分のダミー要素を追加したａ”［１＋１×Ｎ＋Ｎ］に変更する。このようにして、変換装置１００は、変換後プログラムＰ２を、さらに変換後プログラムＰ３に変換する。
【００７６】
ここで、配列ａ［Ｎ］の各々の要素ａ［ｉ］は、配列ａ”［１＋１×Ｎ＋Ｎ］の各々の要素ａ”［１＋１×ｉ＋ｉ］に置換される。換言すれば、要素ａ”［０］は段数分のダミー要素として追加される。また、要素ａ”［１］はサイクル数の差の分のダミー要素として追加され、要素ａ”［３］はサイクル数の差の分のダミー要素として追加され、・・・要素ａ”［２Ｎ］はサイクル数の差の分のダミー要素として追加される。また、要素ａ［０］は要素ａ”［２］に、要素ａ［１］は要素ａ”［４］に、・・・、要素ａ［Ｎ］は要素ａ”［１＋２Ｎ］に置換される。これにより、変換装置１００は、サイクル数が異なる場合であっても、ＮＯＰを用いなくても配列変数を遅延させることができる変換後プログラムＰ３を作成することができる。
【００７７】
（サイクル数に差がある場合の変換後プログラムＰ３の実行の一例）
次に、図１２〜図１４を用いて、サイクル数に差がある場合の変換装置１００による変換後プログラムＰ３の実行の一例について説明する。
【００７８】
図１２〜図１４は、サイクル数に差がある場合の変換後プログラムＰ３の実行の一例を示す説明図である。ここでも、図１１と同様に、説明の簡略化のため、演算「ｂ［ｉ］×ｃ」が２サイクルかかる演算であるとし、演算「ｙ［ｉ］×ａ［１＋１×ｉ＋ｉ］」が１サイクルかかる演算であるとする。変換装置１００は、図１０と同様に、演算ｂ［ｉ］×ｃをＰＥ１に割り当てる。また、変換装置１００は、演算ｙ［ｉ］×ａ［１＋１×ｉ＋ｉ］をＰＥ２に割り当てる。
【００７９】
図１２において、１サイクル目に、（５）ＰＥ１は、配列ｂ［Ｎ］のうちのｂ［０］と、変数ｃと、を読み出して、演算ｂ［０］×ｃを行う。同時に、（６）ＰＥ２は、配列ａ［１＋１×Ｎ＋Ｎ］のうちのダミー要素となるａ［０］を読み出すが、ＰＥ１の演算結果が入力されていないため、演算結果を破棄して、終了する。これにより、ＰＥ２は、ＮＯＰの代わりに、ダミー要素についてのダミー演算を行う。次に、ＰＥ１とＰＥ２とは、２サイクル目に移行する。
【００８０】
２サイクル目に、（７）ＰＥ１は、（５）の続きを行い、演算ｂ［０］×ｃを行う。同時に、（８）ＰＥ２は、配列ａ［１＋１×Ｎ＋Ｎ］のうちのダミー要素となるａ［１］を読み出すが、ＰＥ１の演算結果が入力されていないため、演算結果を破棄して、終了する。これにより、ＰＥ２は、ＮＯＰの代わりに、ダミー要素についてのダミー演算を行う。次に、ＰＥ１とＰＥ２とは、図１３に示す３サイクル目に移行する。
【００８１】
図１３において、３サイクル目に、（９）ＰＥ１は、配列ｂ［Ｎ］のうちのｂ［１］と、変数ｃと、を読み出して、演算ｂ［１］×ｃを行う。同時に、（１０）ＰＥ２は、配列ａ［１＋１×Ｎ＋Ｎ］のうちのａ［２］を読み出して、ＰＥ１の演算が終了しているためＰＥ１の演算結果ｙ［０］を取得して、演算ｙ［０］×ａ［２］を行う。これにより、ＰＥ２は、ＮＯＰがなくても、ｙ［０］と、ａ［２］と、の入力タイミングを同期させて、演算ｙ［０］×ａ［２］を行うことができる。次に、ＰＥ１とＰＥ２とは、４サイクル目に移行する。
【００８２】
４サイクル目に、（１１）ＰＥ１は、（９）の続きを行い、演算ｂ［１］×ｃを行う。同時に、（１２）ＰＥ２は、配列ａ［１＋１×Ｎ＋Ｎ］のうちのダミー要素となるａ［３］を読み出すが、ＰＥ１の演算結果が入力されていないため、演算結果を破棄して、終了する。これにより、ＰＥ２は、ＮＯＰの代わりに、ダミー要素についてのダミー演算を行う。次に、ＰＥ１とＰＥ２とは、図１４に示す５サイクル目に移行する。
【００８３】
図１４において、５サイクル目に、（１３）ＰＥ１は、配列ｂ［Ｎ］のうちのｂ［２］と、変数ｃと、を読み出して、演算ｂ［２］×ｃを行う。同時に、（１４）ＰＥ２は、配列ａ［１＋１×Ｎ＋Ｎ］のうちのａ［４］を読み出して、ＰＥ１の演算が終了しているためＰＥ１の演算結果ｙ［１］を取得して、演算ｙ［１］×ａ［４］を行う。これにより、ＰＥ２は、ＮＯＰがなくても、ｙ［１］と、ａ［４］と、の入力タイミングを同期させて、演算ｙ［１］×ａ［４］を行うことができる。以降のサイクルにおいても、同様に、ＰＥ１とＰＥ２とは、正常に演算を行うことができる。
【００８４】
（変換装置１００の変換処理手順の一例）
次に、図１５を用いて、変換装置１００の変換処理手順の一例について説明する。
【００８５】
図１５は、変換装置１００の変換処理手順の一例を示すフローチャートである。図１５において、変換装置１００は、変換前プログラムＰ１を取得する（ステップＳ１５０１）。次に、変換装置１００は、メモリ情報５００に基づいて、取得した変換前プログラムＰ１をコンパイルする（ステップＳ１５０２）。そして、変換装置１００は、ＣＤＦＧを作成する（ステップＳ１５０３）。
【００８６】
次に、変換装置１００は、マッピングを行う（ステップＳ１５０４）。そして、変換装置１００は、配置配線についての情報を作成する（ステップＳ１５０５）。次に、変換装置１００は、タイミング調整を行う（ステップＳ１５０６）。そして、変換装置１００は、タイミング調整が成功したか否かを判定する（ステップＳ１５０７）。
【００８７】
ここで、タイミング調整が失敗した場合（ステップＳ１５０７：Ｎｏ）、変換装置１００は、ステップＳ１５０４に戻る。一方で、タイミング調整が成功した場合（ステップＳ１５０７：Ｙｅｓ）、変換装置１００は、ＮＯＰを用いるか否かを判定する（ステップＳ１５０８）。
【００８８】
ここで、ＮＯＰを用いない場合（ステップＳ１５０８：Ｎｏ）、変換装置１００は、変換処理を終了する。一方で、ＮＯＰを用いる場合（ステップＳ１５０８：Ｙｅｓ）、変換装置１００は、ＮＯＰの演算に対する入力となる変数が、配列であるか否かを判定する（ステップＳ１５０９）。
【００８９】
ここで、配列ではない場合（ステップＳ１５０９：Ｎｏ）、変換装置１００は、変換処理を終了する。一方で、配列である場合（ステップＳ１５０９：Ｙｅｓ）、変換装置１００は、ＮＯＰの数に応じて、ＮＯＰの演算に対する入力となる配列に、ダミー要素を追加する（ステップＳ１５１０）。ここで、他の演算とのサイクル数の差を抑制するためのＮＯＰがある場合は、さらにダミー要素を追加してもよい。
【００９０】
次に、変換装置１００は、ダミー要素を追加した変換後プログラムＰ２を出力する（ステップＳ１５１１）。そして、変換装置１００は、変換処理を終了する。これにより、変換装置１００は、ＮＯＰを用いなくても実行可能な変換後プログラムＰ２を作成することができる。
【００９１】
以上説明したように、変換プログラムによれば、第１の演算を実行する段階から、第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数分のダミー要素を、配列変数の要素の先頭に追加して、プログラムを変換することができる。これにより、変換プログラムは、ＮＯＰを用いなくても実行可能な変換後プログラムＰ２を作成することができる。
【００９２】
結果として、変換後プログラムＰ２を実行するコンピュータは、第２の演算の前にＮＯＰを用いて配列ａ［Ｎ］の要素の入力を遅延させなくてもよくなり、複数の演算を実行するために用いられるリソースの増加を抑制することができる。このため、変換後プログラムＰ２を実行するコンピュータは、限られたリソースをＮＯＰに割り当てることなく、リソースをＮＯＰ以外の演算に割り当てることができるため、リソースを有効に活用することができる。また、変換後プログラムＰ２を実行するコンピュータは、ＮＯＰにリソースを割り当てなくてもよいため、より多くのリソースを使用する演算を実現することができる。
【００９３】
また、変換プログラムによれば、さらに、変換後プログラムＰ２を、配列変数の要素間に、第１の演算にかかるサイクル数と第２の演算にかかるサイクル数との差の分の要素を追加して、プログラムを変換することができる。これにより、変換プログラムは、サイクル数が異なる場合であっても、ＮＯＰを用いなくても配列変数を遅延させることができる変換後プログラムＰ３を作成することができる。
【００９４】
また、変換プログラムによれば、各種情報に基づいて、変換前プログラムＰ１をコンパイルして、ＣＤＦＧを作成し、タイミング調整を行い、配列変数に対して用いられるＮＯＰの数を特定することができる。各種情報とは、オペランド情報３００と、実行サイクル情報４００と、メモリ情報５００と、である。これにより、変換プログラムは、配列に追加すべきダミー要素の数を特定することができる。
【００９５】
また、変換プログラムによれば、第１の演算と第２の演算とをＰＥ−Ａｒｒａｙ２０３に並列実行させることができる。また、ＰＥは、追加した段数分の要素にかかる演算結果を破棄することができる。これにより、ダミー要素の演算結果を記憶することがなくなり、元々の要素の演算結果が正しく記憶される。
【００９６】
また、変換プログラムによれば、第１の演算と第２の演算とをＰＥ−Ａｒｒａｙ２０３に並列実行させることができる。また、ＰＥは、追加した段数分の要素にかかる演算結果を、元々の要素の演算結果で上書きすることができる。これにより、ダミー要素の演算結果を記憶することがなくなり、元々の要素の演算結果が正しく記憶される。
【００９７】
ここで、変換前プログラムＰ１を実行するためのチップを作成する場合が考えられる。この場合、変換プログラムによれば、変換前プログラムＰ１を変換後プログラムＰ２、または変換後プログラムＰ３に変換することによって、チップを作成するために用いられるリソースの量を低減することができる。これにより、チップに用意すべきリソースの量を低減することができるため、チップ面積を低減することができ、製造コストを低減することができる。
【００９８】
なお、本実施の形態で説明した変換方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本変換プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本変換プログラムは、インターネット等のネットワークを介して配布してもよい。
【００９９】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１００】
（付記１）コンピュータに、
プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、前記第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定し、
前記プログラムを、前記配列変数の要素の先頭に、特定した前記段数分の要素を追加したプログラムに変換する、
処理を実行させることを特徴とする変換プログラム。
【０１０１】
（付記２）前記変換する処理は、さらに、前記第１の演算にかかるサイクル数が前記第２の演算にかかるサイクル数より大きい場合、前記段数分の要素を追加したプログラムを、前記配列変数の要素間に、前記第１の演算にかかるサイクル数と前記第２の演算にかかるサイクル数との差の分の要素を追加したプログラムに変換することを特徴とする付記１に記載の変換プログラム。
【０１０２】
（付記３）前記特定する処理は、前記複数の演算に用いられる演算回路の数と、スカラ変数に対して割り当てられた第１の記憶領域のサイズと、前記第１の記憶領域に同時にアクセス可能な演算回路の数と、配列変数に対して割り当てられた第２の記憶領域のサイズと、前記第２の記憶領域に同時にアクセス可能な演算回路の数と、に基づいて、前記段数を特定することを特徴とする付記１または２に記載の変換プログラム。
【０１０３】
（付記４）前記第１の演算を第１の演算回路に割り当てて、前記第２の演算を第２の演算回路に割り当てて、前記第１の演算と前記第２の演算とを並列実行させ、
前記第２の演算回路は、追加した前記段数分の要素にかかる演算結果を破棄することを特徴とする付記１〜３のいずれか一つに記載の変換プログラム。
【０１０４】
（付記５）前記第１の演算を第１の演算回路に割り当てて、前記第２の演算を第２の演算回路に割り当てて、前記第１の演算と前記第２の演算とを並列実行させ、
前記第２の演算回路は、追加した前記段数分の要素にかかる演算結果を、前記配列変数の要素のうちの末尾から前記段数分の要素で上書きすることを特徴とする付記１〜３のいずれか一つに記載の変換プログラム。
【０１０５】
（付記６）コンピュータが、
プログラムに規定された、演算順序に従って複数の段階に分けて実行される複数の演算のうち、第１の演算を実行する段階から、前記第１の演算の演算結果と配列変数とを用いた第２の演算を実行する段階までの段数を特定し、
前記プログラムを、前記配列変数の要素の先頭に、特定した前記段数分の要素を追加したプログラムに変換する、
処理を実行することを特徴とする変換方法。
【符号の説明】
【０１０６】
１００  変換装置
６０１  特定部
６０２  変換部
６０３  制御部
【図１】
0006050193.tif 000002
【図２】
0006050193.tif 000003
【図３】
0006050193.tif 000004
【図４】
0006050193.tif 000005
【図５】
0006050193.tif 000006
【図６】
0006050193.tif 000007
【図７】
0006050193.tif 000008
【図８】
0006050193.tif 000009
【図９】
0006050193.tif 000010
【図１０】
0006050193.tif 000011
【図１１】
0006050193.tif 000012
【図１２】
0006050193.tif 000013
【図１３】
0006050193.tif 000014
【図１４】
0006050193.tif 000015
【図１５】
0006050193.tif 000016