(57)【要約】【課題】不定ループ処理部分を含む逐次型言語プログラムを、パイプライン処理時に分岐ハザードを発生させないプログラムに変換する技術を提供する。【解決手段】プログラム変換装置において、逐次型言語プログラムを入力する入力手段と、前記逐次型言語プログラムにおける不定ループ処理部分を、固定ループ部品の組み合わせを実行するプログラムに変換する変換手段と、前記変換がなされた前記逐次型言語プログラムを出力する出力手段とを備える。【選択図】図３
2019032658.tif 000002
【特許請求の範囲】
【請求項１】
逐次型言語プログラムを入力する入力手段と、
前記逐次型言語プログラムにおける不定ループ処理部分を、固定ループ部品の組み合わせを実行するプログラムに変換する変換手段と、
前記変換がなされた前記逐次型言語プログラムを出力する出力手段と
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記変換手段は、
前記不定ループ処理部分における最大ループ回数の２を底とする対数を取り、当該対数の整数部分の値をＮとする場合に、Ｎ＋１個の固定ループ部品を作成し、前記組み合わせとして、当該Ｎ＋１個の固定ループ部品の中の固定ループ部品の組み合わせを用いる
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
前記不定ループ処理部分から変換される前記プログラムは、
前記不定ループ処理部分の実行時に定まるループ回数をビット展開し、ビット展開で得られたビット列における１に対応する固定ループ部品の組み合わせを実行するプログラムである
ことを特徴とする請求項１又は２に記載のプログラム変換装置。
【請求項４】
プログラム変換装置が実行するプログラム変換方法であって、
逐次型言語プログラムを入力する入力ステップと、
前記逐次型言語プログラムにおける不定ループ処理部分を、固定ループ部品の組み合わせを実行するプログラムに変換する変換ステップと、
前記変換がなされた前記逐次型言語プログラムを出力する出力ステップと
を備えることを特徴とするプログラム変換方法。
【請求項５】
前記変換ステップにおいて、前記プログラム変換装置は、
前記不定ループ処理部分における最大ループ回数の２を底とする対数を取り、当該対数の整数部分の値をＮとする場合に、Ｎ＋１個の固定ループ部品を作成し、前記組み合わせとして、当該Ｎ＋１個の固定ループ部品の中の固定ループ部品の組み合わせを用いる
ことを特徴とする請求項４に記載のプログラム変換方法。
【請求項６】
前記不定ループ処理部分から変換される前記プログラムは、
前記不定ループ処理部分の実行時に定まるループ回数をビット展開し、ビット展開で得られたビット列における１に対応する固定ループ部品の組み合わせを実行するプログラムである
ことを特徴とする請求項４又は５に記載のプログラム変換方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載の前記プログラム変換装置における各手段として機能させるための変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逐次型言語プログラムを、並列型環境への展開に適したプログラムに変換する技術に関連するものである。
【背景技術】
【０００２】
ＯＳＳ（Open Source Soft）や汎用部品を用いたネットワーク構築が検討されているが、その性能が課題となっている。解決策として、ＣＰＵ、ＦＰＧＡ（Field Programmable Gate Array）等のチップを分散配置するヘテロジニアスコンピューティングの研究が行われている。しかし、ヘテロジニアスコンピューティングでは各チップのアーキテクチャが異なり，開発言語が異なるという課題がある。
【０００３】
そこで、ｐａｃｋｅｔ転送処理等をＦＰＧＡで実現するにあたり、処理をＣ言語などの逐次型言語で記述してＨＤＬ（Hardware Design Language）などの並列型言語に展開する高位合成（High Level Synthesis）ツールを使用する研究がなされている。高位合成ツールに関する先行技術文献として、例えば非特許文献１〜５がある。
【０００４】
図１は、従来技術における高位合成ツールの使用例を説明するための図である。図１に示すように、逐次型言語を用いたＣ言語プログラム等の既存プログラムは、通常は、Ｌｏａｄ  Ｍｏｄｌｕｅに変換されて、ＩＡサーバなどにより実行される。一方、当該既存プログラム（Ｓ１）をＦＰＧＡなどの並列型環境（ハードウェア）に展開する場合には、まず、当該既存プログラムを高位合成ツールにより、並列型言語のプログラムに変換する（Ｓ２、Ｓ３）。そして、当該並列型言語のプログラムからビットストリーム（スイッチの接続関係等を示すデータ）を生成し（Ｓ４）、ビットストリームをＦＰＧＱなどの並列型環境にダウンロードする（Ｓ５）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】https://www.oki.com/jp/otr/2015/n225/pdf/otr225_r09.pdf
【非特許文献２】https://www.ipsj.or.jp/award/9faeag0000004ej9-att/3ZA_2.pdf
【非特許文献３】https://www.ite.or.jp/contents/keywords/FILE-20160413134849.pdf
【非特許文献４】http://catalog.lib.kyushu-u.ac.jp/handle/2324/6069/matsunaga03_1.pdf
【非特許文献５】https://www.jstage.jst.go.jp/article/essfr/6/1/6_37/_pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
Ｃ言語などの逐次型言語を用いたプログラムは、逐次を前提に作成されているため、そのまま並列型環境に展開するとパイプライン等の並列型環境のメリットを生かせない問題がある。逐次処理を並列化する上で障害となる要因の１つとして分岐ハザードがある。図２を参照して分岐ハザードについて説明する。
【０００７】
パイプラインは先行実行処理であるが、図２の左側に示すように、「繰り返し」か「分岐終了」かの分岐命令があると、その先のどちらを先行実行していいか分からないため、そこで処理がストップしてしまう。予想でどちらかのブロックを実行したとしても、その予想が外れた場合には、変数を元に戻すなど、大きなペナルティが課せられる。
【０００８】
ただし、図２の右上に示すように、ループ数が固定（例：IP checksumなどの入力パケット長に左右されない処理。これを以下、「固定ループ」と呼ぶ。）である場合、形式的な分岐はあっても、実質的な分岐がないので、最適化により分岐ハザードの完全削除が可能である。
【０００９】
一方、図２の右下に示すように、ループ数が条件により異なる場合（UDP CHKSUMなどの入力パケット長によりループ回数が定まる処理。以下、これを「不定ループ」と呼ぶ。）、実質的な分岐となり、各周回毎に分岐ハザードが発生し、性能障害原因になる。
【００１０】
本発明は上記の点に鑑みてなされたものであり、不定ループ処理部分を含む逐次型言語プログラムを、パイプライン処理時に分岐ハザードを発生させないプログラムに変換する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
開示の技術によれば、逐次型言語プログラムを入力する入力手段と、
前記逐次型言語プログラムにおける不定ループ処理部分を、固定ループ部品の組み合わせを実行するプログラムに変換する変換手段と、
前記変換がなされた前記逐次型言語プログラムを出力する出力手段と
を備えることを特徴とするプログラム変換装置が提供される。
【発明の効果】
【００１２】
開示の技術によれば、不定ループ処理部分を含む逐次型言語プログラムを、パイプライン処理時に分岐ハザードを発生させないプログラムに変換する技術を提供することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】従来技術を説明するための図である。
【図２】課題を説明するための図である。
【図３】本発明の実施の形態の概要を説明するための図である。
【図４】本発明の実施の形態におけるプログラム変換装置の機能構成図である。
【図５】プログラム変換装置のハードウェア構成例を示す図である。
【図６】プログラム変換処理を説明するための図である。
【図７】プログラム展開例を示す図である。
【図８】プログラム展開例を示す図である。
【図９】従来構成と提案構成の比較を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を説明する。以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１５】
（実施の形態の概要）
図３を参照して本実施の形態の概要を説明する。本実施の形態においては、固定ループでは分岐ハザードが発生しないことに着目し、図３のＳ１２に示す、高位合成前の変換ツールにより、逐次言語型プログラム（Ｓ１１）における不定ループ処理部分を固定ループ部品の組み合わせを有するプログラムに変換することとしている。図３のＳ１３〜Ｓ１６は図１のＳ２〜Ｓ５と同様である。
【００１６】
すなわち、本実施の形態では、不定ループ処理部分を含む逐次型言語プログラムを高位合成などにより、並列実行環境に展開する前に、変換ツールを用いて分岐ハザードを回避したパイプライン可能なプログラムに変換する。以下、本実施の形態における構成、処理をより詳細に説明する。
【００１７】
（装置構成）
図４は、本実施の形態におけるプログラム変換装置１００の機能構成図である。図４に示すように、プログラム変換装置１００は、入力部１０１、変換部１０２、出力部１０３を有する。
【００１８】
入力部１０１は、逐次型言語プログラム（例：Ｃ言語プログラム）を入力する。変換部１０２は、入力された逐次型言語プログラムにおける不定ループ処理部分を固定ループ部品の組み合わせを実行するプログラムに変換する。変換部１０２における処理の詳細は後述する。出力部１０３は、変換された逐次型言語プログラムを出力する。出力された逐次型言語プログラムは、例えば図３に示すように、高位合成ツールに入力され、並列型環境への展開がなされる。
【００１９】
（プログラム変換装置１００のハードウェア構成）
上述したプログラム変換装置１００は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、プログラム変換装置１００が有する機能は、コンピュータに内蔵されるＣＰＵやメモリ等のハードウェア資源を用いて、プログラム変換装置１００で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メール等、ネットワークを通して提供することも可能である。なお、上記プログラムを「変換プログラム」あるいは「変換ツール」と称してもよい。
【００２０】
図５は、本実施の形態におけるプログラム変換装置１００のハードウェア構成例を示す図である。図５のプログラム変換装置１００は、それぞれバスＢで相互に接続されているドライブ装置１５０、補助記憶装置１５２、メモリ装置１５３、ＣＰＵ１５４、インタフェース装置１５５、表示装置１５６、及び入力装置１５７等を有する。
【００２１】
プログラム変換装置１００での処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ又はメモリカード等の記録媒体１５１によって提供される。プログラムを記憶した記録媒体１５１がドライブ装置１５０にセットされると、プログラムが記録媒体１５１からドライブ装置１５０を介して補助記憶装置１５２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１５１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１５２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２２】
メモリ装置１５３は、プログラムの起動指示があった場合に、補助記憶装置１５２からプログラムを読み出して格納する。ＣＰＵ１５４は、メモリ装置１５３に格納されたプログラムに従ってプログラム変換装置１００に係る機能を実現する。インタフェース装置１５５は、ネットワークに接続するためのインタフェースとして用いられる。表示装置１５６はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１５７はキーボード及びマウス、ボタン、又はタッチパネル等で構成され、様々な操作指示を入力させるために用いられる。
【００２３】
（変換部１０２における処理の具体例）
次に、プログラム変換装置１００の変換部１０２が実行する処理をより具体的に説明する。
【００２４】
ここでは、逐次型言語プログラムにおいて、＃ＰＲＡＧＭＡ記述子などにより、不定ループにおける最大ループ数が指定されているものとする。
【００２５】
入力部１０１から変換対象の逐次型言語プログラムが入力されると、当該逐次型言語プログラムは、メモリ装置１５３等に格納される。当該メモリ装置に格納された逐次型言語プログラムに対し、変換部１０２（ハードウェアとしてはＣＰＵ１５４）が以下で説明する変換処理を実行する。なお、生成される固定ループ部品、ビット展開プログラム等もメモリ装置１５３等に格納され、出力時に、出力部１０３から出力される。
【００２６】
変換部１０２はまず、入力された逐次型言語プログラムにおける不定ループ処理部分を検出すると、＃ＰＲＡＧＭＡ記述子などにより、その最大ループ数を取得する。そして、不定ループ処理部分の最大ループ数の２を底とする対数を取り、その整数部分Ｎを求め、ループ回数（２＾０，２＾１，・・・，２＾Ｎ）の固定ループの関数部品（固定ループ部品）を作成する。また、実行時のループ回数をビット展開し、ビットが立つ固定ループ部品を実行するプログラムを生成する。なお、「ビットが立つ固定ループ部品を実行する」処理のプログラムについては、固定ループ部品の中に組み込まれていてもよいし、固定ループ部品とは別のプログラムとして生成されてもよい。
【００２７】
これにより、変換部１０２により変換処理が行われた逐次型言語プログラムを実行すると、不定ループ処理部分の実行の時点で、ループ回数をビット展開し、ビットが立つ（ビットが１である）固定ループ部品を実行する動作が実現される。
【００２８】
具体例を図６を参照して説明する。この例では、不定ループ処理部分の最大ループ数が＃ＰＲＡＧＭＡ記述子により１０００と指定されているものとする。この場合、変換部１０２は、入力された逐次型言語プログラムから当該不定ループ処理部分を検出すると、最大ループ数として、＃ＰＲＡＧＭＡ記述子の記述から１０００を取得する。そして、変換部１０２は、２を底とする１０００の対数を取り、その整数部分である９を得る。
【００２９】
そして、変換部１０２は、０から９までの各整数を用い、ループ回数が２＾０（＝１）の固定ループ部品、ループ回数が２＾１（＝２）の固定ループ部品、ループ回数が２＾２（＝４）の固定ループ部品、ループ回数が２＾３（＝８）の固定ループ部品、ループ回数が２＾４（＝１６）の固定ループ部品、ループ回数が２＾５（＝３２）の固定ループ部品、ループ回数が２＾６（＝６４）の固定ループ部品、ループ回数が２＾７（＝１２８）の固定ループ部品、ループ回数が２＾８（＝２５６）の固定ループ部品、及び、ループ回数が２＾９（＝５１２）の固定ループ部品を作成する。各固定ループ部品のループ内ブロックの処理内容は同じである。すなわち、２を底とする最大ループ数の対数を取り、その整数部分をＮとした場合に、Ｎ＋１個の固定ループ部品が作成される。
【００３０】
更に、変換部１０２は、実行時に定まるループ回数（例：実行時に入力されるパケット長）をビット展開し、ビットが立つ固定ループ部品を実行する動作を行うプログラムを生成する。前述したように、ビットが立つ固定ループ部品を実行する処理のプログラムについては、各固定ループ部品が有してもよい。
【００３１】
変換部１０２により変換処理された逐次型言語プログラムには、不定ループ処理部分から展開された固定ループ部品と、実行時に定まるループ回数をビット展開するプログラムが含まれる。なお、これらを合わせて「固定ループ部品の組み合わせを実行するプログラム」と称してもよい。
【００３２】
変換部１０２により変換処理された逐次型言語プログラムにおける不定ループ処理相当部分をコンピュータが実行する場合において、当該不定ループ処理におけるループ回数が５９７であるとする。この場合、まず、５９７がビット展開されて１００１０１０１０１が得られる。ビット展開されたビット列における最下位ビット（右端のビット）から順に、各ビットが、ループ回数が２＾０（＝１）の固定ループ部品、ループ回数が２＾１（＝２）の固定ループ部品、ループ回数が２＾２（＝４）の固定ループ部品、ループ回数が２＾３（＝８）の固定ループ部品、ループ回数が２＾４（＝１６）の固定ループ部品、ループ回数が２＾５（＝３２）の固定ループ部品、ループ回数が２＾６（＝６４）の固定ループ部品、ループ回数が２＾７（＝１２８）の固定ループ部品、ループ回数が２＾８（＝２５６）の固定ループ部品、ループ回数が２＾９（＝５１２）の固定ループ部品に対応付けられる。
【００３３】
そして、ビットが立つ（ビット＝１である）固定ループ部分が実行される。この例では、ループ回数が１，４，１６，６４，５１２の固定ループ部品が実行される。
【００３４】
各ループ部分は固定ループであるため、変換処理された逐次型言語プログラムが、高位合成ツールを経て、並列型環境に展開された場合において、当該プログラムの実行により分岐ハザードを発生させないパイプライン処理が可能である。
【００３５】
より具体的なプログラムの変換例（展開例）を図７、図８に示す。図７に示すように、この例では展開前において、不定ループ処理(for ( i = 0 ; i < n ; i++ ) {…)が記述されており、その最大ループ数が１０００であることが記述されている。
【００３６】
変換部１０２（変換ツール）は、前述した方法で図７に示す不定ループ処理部分を各固定ループ部品に展開する。また、図７の例では、各固定ループ部品について、実行時にパイプライン処理を行うことが記述されている。
【００３７】
そして、図８に示すように、変換後のプログラムの実行において、実行時のループ回数ｎをビット展開したビット列においてビットが１に対応する固定ループ部品が実行される。図８の例では、「if ( nをビット展開したものにビットが立っていれば）」として、各固定ループ部品内に、当該固定ループ部品を実行するか否かのロジックが組み込まれている。ただし、これは一例である。各固定ループ部品内に、固定ループ部品を実行するか否かのロジックを組み込まずに、固定ループ部品とは別のプログラムとして、ｎをビット展開したものにビットが立っていれば、該当の固定ループ部品を実行するロジックが備えられていてもよい。
【００３８】
図９は、逐次型言語プログラムにおける不定ループ処理の実行時の従来構成と、提案構成（本実施の形態の構成）との比較を示す。ここでは実行時のループ回数が前述した５９７である例を示している。
【００３９】
図９の左側に示すように、従来構成では、５９７回の分岐ハザードが発生してしまう。一方、図９の右側に示す提案構成では、不定ループ処理部分から展開された固定ループ部品の組み合わせが実行されるので、分岐ハザードは発生しない。
【００４０】
（実施の形態の効果）
以上、説明したように、本実施の形態では、Ｃ言語などの逐次型言語のループ処理プログラムを高位合成などにより、ＦＰＧＡなどの並列実行環境に展開する際に、変換ツールを用いてパイプライン（並列）可能なプログラムに変換することにより、逐次環境向けプログラムと、並列環境向けプログラムの共通化を可能としている。また、逐次型言語で作成された既存のプログラムを並列環境に適用することが容易になる。具体的には、不定ループ処理を、ループ回数２＾ｎとした固定ループ部品の組み合わせに変換することにより、分岐ハザードを消去し、高速化が実現される。
【００４１】
（実施の形態のまとめ）
以上、説明したように、本実施の形態によれば、逐次型言語プログラムを入力する入力手段と、前記逐次型言語プログラムにおける不定ループ処理部分を、固定ループ部品の組み合わせを実行するプログラムに変換する変換手段と、前記変換がなされた前記逐次型言語プログラムを出力する出力手段とを備えることを特徴とするプログラム変換装置が提供される。
【００４２】
実施の形態で説明した入力部１０１、変換部１０２、出力部１０３は、入力手段、変換手段、出力手段の例である。
【００４３】
前記変換手段は、前記不定ループ処理部分における最大ループ回数の２を底とする対数を取り、当該対数の整数部分の値をＮとする場合に、Ｎ＋１個の固定ループ部品を作成し、前記組み合わせとして、当該Ｎ＋１個の固定ループ部品の中の固定ループ部品の組み合わせを用いることとしてもよい。
【００４４】
前記不定ループ処理部分から変換される前記プログラムは、前記不定ループ処理部分の実行時に定まるループ回数をビット展開し、ビット展開で得られたビット列における１に対応する固定ループ部品の組み合わせを実行するプログラムであることとしてもよい。
【００４５】
また、本実施の形態により、コンピュータを、前記プログラム変換装置における各手段として機能させるための変換プログラムが提供される。
【００４６】
以上、本実施の形態について説明したが、本発明はかかる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００４７】
１００  プログラム変換装置
１０１  入力部
１０２  変換部
１０３  出力部
１５０  ドライブ装置
１５１  記録媒体
１５２  補助記憶装置
１５３  メモリ装置
１５４  ＣＰＵ
１５５  インタフェース装置
１５６  表示装置
１５７  入力装置
【図１】
2019032658.tif 000003
【図２】
2019032658.tif 000004
【図３】
2019032658.tif 000005
【図４】
2019032658.tif 000006
【図５】
2019032658.tif 000007
【図６】
2019032658.tif 000008
【図７】
2019032658.tif 000009
【図８】
2019032658.tif 000010
【図９】
2019032658.tif 000011