高位合成ツールJavaRockの回路分割システム

全文

(1)組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. 高位合成ツール JavaRock の回路分割システム松田和也† 船田悟史 ††. 三好健文 †† 中條拓伯†. 高位合成ツール JavaRock には，RTL でのアルゴリズム記述の煩雑さを克服し，Java 言語で記述したプログラムをハードウェア化することが期待されている．しかしながら，Java で記述したアプリケーションプログラムをハードウェア化する際には，1 つの FPGA に格納できないような規模の回路に対する場合や，FPGA のリソース使用量の増加により動作周波数が低化する場合に問題となる．そこで，JavaRock の BlockRAM の利用に着目し，クラスタリングに適用することで，複数の FPGA に回路を分割するシステムを考案し，実装を行った．本論文では，JavaRock によって生成された VHDL のコードを対象として回路分割を行い，レジスタ数や LUT 数，BlockRAM 消費量を調査することで，提案する回路分割システムが有効であることを確認した．. Circuit Partitioning System of a High-Level Synthesis Tool JavaRock Kazuya Matsuda,† Takefumi Miyoshi,†† Satoshi Funada†† and Hironori Nakajo† A High-Level Synthesis Tool JavaRock is expected to overcome the complexity to describe algorithms at an RTL for implementation of a Java program into hardware. However, there are two big problems to implement a Java application in hardware; an increasing scale of a circuit to implement in a single FPGA and decreasing operating frequency due to large usage of slices in an FPGA. Thus, we focus on usage of BlockRAM in an FPGA with a highlevel synthesis tool JavaRock. Moreover, we design and implement a system to partition a circuit into plural FPGAs with applying clustering. In this paper, VHDL codes, which are generated by JavaRock, are targets of our circuit partitioning. We investigate the amount of registers and LUTs, usage of consumed BlockRAM in order to conﬁrm that our proposed circuit partitioning system is eﬀective．. や Lime6) ，JavaRock7) など，様々なものがある．し. 1. はじめに. かしながら，高位合成は，複数の FPGA に回路を分. 一般的なハードウェア設計に用いられる VHDL や. 割するための機能を備えていない．そのため，1 つの. Verilog-HDL といったハードウェア記述言語（HDL）. FPGA に格納できないような規模の回路に対する場合. に代わり，高位合成を利用したハードウェア設計に期. や FPGA のリソース使用量の増加により動作周波数. 待が寄せられている．HDL を利用したレジスタ転送. が低化する場合に問題となる．大規模回路を搭載でき. レベル（Register Transfer Level; RTL）における設. る高性能な FPGA は高価であり，コストパフォーマン. 計では，論理回路やレジスタ間の処理を記述すること. スの点で不利である．そのため，規模の小さな FPGA. は可能であるが，複雑なアルゴリズムを記述する際に. を複数利用することで，低価格で回路を動作させると. は，煩雑な記述が要求される．そのため，RTL よりも. いう要求があり，そのようなニーズへの対応を考えた．. 高い抽象レベルで記述できる高位合成は有用となる．. CyberWorkBench を対象とした回路分割手法8) で. 高位合成としては， C 言語をベースとする. は，FPGA の回路規模により分割点を決定する．C 言. SystemC1) ， ImpulseC2) ，CyberWorkBench3) や. 語は手続き型言語であるため，変数に対する処理回路. 4). 5). LegUp をはじめ，Java 言語をベースとする JHDL. を把握することは困難であり，分割回路間に跨る変数の扱いが問題となる．一方，Java 言語はオブジェク. † 東京農工大学 Tokyo University of Agriculture and Technology †† 株式会社イーツリーズ・ジャパン e-trees.Japan,Inc.. ⓒ 2013 Information Processing Society of Japan. ト指向言語であるため，関連する変数や処理はクラスにまとめられる．Java 言語をベースとする高位合成では，1 つのクラスが 1 つのモジュールに変換される. 49.

(2) 組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. ため，モジュール単位の分割を行うことで，分割回路間に跨る変数を把握することは容易となる．. int i = 10; while ( i > 0) { i - -;. そこで，Java 言語をベースとする JavaRock を対象とし，FPGA の回路規模や FPGA 間の BlockRAM アクセス，結線数を考慮した回路分割を行う．本論文では，JavaRock が生成する回路を複数の FPGA に自. }. 図 1 Java サンプルプログラム Fig. 1 Sample program of Java. 動的に分割するシステムを考案し，実装と評価を行う．. JavaRock の特徴に着目することで，JavaRock の生成回路を効率的に分割し，複数の FPGA に格納する．まず，高位合成ツール JavaRock の概要について述べる．次に，この JavaRock が生成する回路に対する分割手法について説明し，回路分割システムの概要を述べる．さらに，Java 言語で記述したアプリケーションプログラムに対する回路分割を行い，実装したシステムを評価し，考察を行い，本論文をまとめる．. case conv_integer ( s a m p l e _ m e t h o d _ s t a t e ) is … when 2 = > i_sample_0 <= c o n v _ s t d _ l o g i c _ v e c t o r (10 , i_sample_0 ’ length ); s a m p l e _ m e t h o d _ s t a t e <= s a m p l e _ m e t h o d _ s t a t e + 1; when 3 = > …. 図 2 ステートマシンの変換例 Fig. 2 Example of a state machine conversion. 2. 高位合成ツール JavaRock 2.1 概. 要. JavaRock は，Java 言語で記述されたプログラムを HDL に変換するためのコンパイラである9) ．JavaRock は Java 言語のソースを VHDL のコードに変換する．入力とする Java 言語のソースプログラムは，JVM （Java Virtual Machine）上でソフトウェアとしても実行でき，機能レベルでのデバックが可能である．しかしながら，JavaRock ではシグナルやステートマシンのビット数に対する最適化は行われない．したがって，リソース使用量に関しては，既存の合成・配. U_A : s i m p l e d u a l p o r t r a m generic map ( DEPTH = > A_DEPTH , WIDTH = > A_WIDTH ) port map ( clk = > clk , we = > A_we_field_rdata , raddr = > A_raddr_field_rdata , rdata = > A_rdata_field_wdata , waddr = > A_waddr_field_rdata , wdata = > A _ w d a t a _ f i e l d _ r d a t a );. 図 3 配列の変換例 Fig. 3 Example of an array. 置配線ツールによる最適化に依存する．また，JavaRock を用いたハードウェアとソフトウェアの協調設計10) や Reconfigurable Android（FPGA を搭載した Android）における開発環境としての. JavaRock の利用11) が検討されている．. マシンに変換されることとなる．. 2.3 配列宣言 JavaRock では，Java プログラム内で宣言された boolean や int，char 型の変数は，VHDL のシグナル. 2.2 逐次処理と制御文. 変数に変換される．一方で，配列宣言された変数に対. 一般的に Java プログラムは逐次実行される．そこ. しては FPGA に内蔵された BlockRAM に変換され. で，JavaRock ではプログラム内の 1 文をステートマ. る．そのため， BlockRAM へのアドレス指定を行う. シンの 1 ステートに変換することで，逐次処理を実現. ことで，読み込みや書き込みが可能となる．. する．したがって，図 1 のプログラムにおける変数 i. 例として，配列 A を宣言した場合の VHDL のコー. への代入は，図 2 の VHDL のコードに変換される．こ. ドを図 3 に示す．配列アクセスには，アドレス信号や. こでは，sample method state の形で示されたステー. データ信号，制御信号が必要となり，信号線数が多く. トマシンが，メソッド全体の処理を管理する．このス. なる．また，変数の型や配列サイズに合わせ，Block-. テートマシンに対して，インクリメントを行うことで，. RAM に確保する領域が指定される．. 次のステートへ処理が移行する．また，プログラム内で使用される if 文や while 文，. for 文といった制御文もステートマシンで実現され，メソッド全体のステートマシンに内包される．すなわち，メソッド全体のステートマシンに対するサブステート. ⓒ 2013 Information Processing Society of Japan. 3. JavaRock の生成回路を対象とした回路分割手法本章において，JavaRock が生成した VHDL ファイルを対象とした回路分割手法について述べる．提案手. 50.

(3) 組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. 図 4 分割対象の階層構造 Fig. 4 Layered structure of the target circuit. 図 5 分割対象の位置座標 Fig. 5 Position coordinate of the target circuit. . 法では，以下の 3 点を考慮し，拡張した k-means 法に適用することで，回路分割を行う．. (1). FPGA のリソース使用量を閾値（任意に指定した FPGA のリソース使用率）以下に制限．. (2). 同一 BlockRAM にアクセスするモジュールを. 1 つの FPGA にまとめて格納． (3). FPGA 間の結線数を FPGA の I/O ブロック数以下に限定．. 以下では，回路分割の詳細について述べる．. 3.1 2 次元座標への変換提案手法では，k-means 法によるクラスタリングを行うため，回路全体を 2 次元座標に変換する．ここでは，図 4 に示す階層関係を持つ回路を例として説明する．ノード D は，Java プログラム内において配列宣言が行われた（BlockRAM を利用する）モジュール. 図 6 拡張 k-means 法のアルゴリズム Fig. 6 Algolithm of the extension k-means. であり，ノード U は，配列の要素を利用する（ノー. . ド D の BlockRAM にアクセスする）モジュールである．ノード S は，複数クラスによりインスタンス化さ. ルゴリズムである．初期クラスタ代表点の選定方法を. れたクラスを変換したモジュール（以下では，重複モ. 変更し，各座標の所属クラスタを決定するための条件. ジュールと呼ぶ）である．. を追加する．. 図 5 が図 4 の回路に対する 2 次元座標への変換結. 本来の k-means 法では，初期のクラスタ重心はラ. 果である．トップモジュールを中心に階層ごとに座標. ンダムに選択される．しかしながら，提案手法では. を配置し，座標間の距離 D は. BlockRAM の利用に主眼を置いているため，ランダ. {. D=. V 1 × (1 − R). (ノード U ). V 2 × (1 − R). (otherwise). ムに選択することは不適切である．ノード D とノー. (1). ド U の位置座標に従い，初期クラスタ重心の設定を行う．. で定められる．変数 V1，V2 は座標間距離の基準値. また，複数の FPGA にまたがる信号伝達は，クリ. を示し，V 1 < V 2 の関係にある．また，変数 R は. ティカルパスになりうる．同一 BlockRAM を利用する. FPGA の I/O ブロック数に対する各モジュールの信. モジュールを同一クラスタに所属させ，1 つの FPGA. 号線使用率を示す．ただし，ノード S は，図 5 には含. にまとめて格納する．. めない．このモジュールに関する処理は後述する．. 3.2 拡張 k-means 法. 3.3 回路分割拡張 k-means 法を用いた回路分割について述べる．. 次に，回路分割に利用したクラスタリングのアルゴ. 提案手法では，まず，トップモジュールに対する処理を. リズムについて述べる．クラスタリング適用後に，各. 行う．トップモジュール直下のモジュール群を 1 つの. モジュールの所属クラスタが格納する FPGA となる．. クラスタとして扱う．図 4 の回路では，4 つのクラスタ. 図 6 が提案手法のために拡張した k-means 法のア. が存在するものとし，各クラスタに所属するモジュー. ⓒ 2013 Information Processing Society of Japan. 51.

(4) 組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. ルの位置座標の平均座標を求める．得られた平均座標とトップモジュールとの最短距離を探索し，トップモジュールの所属クラスタを決定する．次に，各クラスタに所属するモジュール群の回路規模を見積もり，閾値以下であるかを判断する．閾値以下のクラスタ集合の中で回路規模が大きいクラスタを選択し，FPGA に格納する．閾値以上のクラスタが存在する場合は，拡張 k-means 法を適用し，再分割を行う．細分化したクラスタは，回路規模の小さい. FPGA に格納される．また，FPGA の個数がクラス. 図 7 回路分割システムの全体図 Fig. 7 Overall view of circuit partitioning system. タ数を上回る場合は，回路規模が最大の FPGA に格. . 納されたクラスタに対して拡張 k-means 法を適用し，再分割する．細分化したクラスタは未使用の FPGA に格納される．いずれの場合においても，FPGA のリソース使用率は閾値以下となる．さらに，重複モジュールを格納する FPGA を決定する．まず，重複モジュールと接続関係にある回路を格納した FPGA 群の結線数を探索する．FPGA の I/O ブロック数とリソース使用量に余裕がある FPGA を. 図 8 回路分割システムの構成 Fig. 8 Configuration of circuit partitioning system. 選択し，重複モジュールを格納する．その他の FPGA. . は，重複モジュールを格納した FPGA と接続することで，重複モジュールの機能を利用する．また，重複モジュールが階層関係を持つ場合はモジュール群として扱い，同一の FPGA に格納する．. 3.4 FPGA 統合. の回路規模，接続関係を記述したレポートを出力する．回路分割システムの構成を図 8 に示す．本論文では，論理合成ツールとして，Xilinx 社の XST（Xilinx. Synthesis Technology）12) を利用する．. 分割回路を格納した FPGA に対する統合処理を行. JavaRock ではリソース削減のための最適化を論理. うことで，FPGA の結線数を I/O ブロック数以下に. 合成ツールに依存する．したがって，論理合成ツール. 収める．ある FPGA の結線数が利用する FPGA の. の設定により，ステートマシンがワンホット・エンコー. I/O ブロック数を上回る場合，その FPGA を統合対. ドされ，必要以上にリソースを消費するという問題が. 象とする．統合対象と接続関係にある FPGA 群に対. 生じる．そこで，回路分割システムではステートマシ. し，リソース使用量が最小の FPGA を選択し，統合. ンを対象に最適化処理を行い，ユーザ任意にエンコー. する．また，FPGA の I/O ブロック数とリソース使. ド方式を指定可能とする．. 用量に余裕があり，統合の余地がある場合には，統合処理を繰り返す．. 4. 回路分割システムの概要. エンコード部において，VHDL ファイルのエンコード方式が指定され，Java ファイルとともにパーサで解析される．回路規模を見積もるためには，論理合成ツールを利用する必要があるため，パーサは XST. 本章で，JavaRock の回路分割システムの概要を説. を呼び出し，見積もり対象に対する論理合成を行う．. 明する．システムの全体図を図 7 に示す．回路分割シ. XST が出力するレポートからレジスタ数や LUT 数，. ステムの入力は，Java ファイル群と VHDL ファイル. BlockRAM 数などの情報を取得する．解析された回. 群，本ツール用の設定ファイルの 3 つである．. 路情報は，2 次元座標への変換プログラムに渡される．. Java ファイルは，JavaRock に対する入力である．. 回路情報の 2 次元座標への変換については，前章で. VHDL ファイルは，この Java ファイルを JavaRock. 触れた．トップモジュールを中心に階層ごとに座標が. に与えた際に得られる出力である．設定ファイルには，. 配置され，座標データは回路分割に利用される．. FPGA デバイス名と個数，閾値が記述される．. 座標データに対して拡張 k-means 法を適用すること. 回路分割システムは出力として，FPGA ごとに. で，回路が分割され，FPGA に格納される．FPGA の. VHDL ファイルをフォルダ分けする．また，各 FPGA. I/O ブロック数とリソース使用量の観点から FPGA. ⓒ 2013 Information Processing Society of Japan. 52.

(5) 組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. 表 1 XC3S1200E のリソース量 Table 1 Amount of resources in XC3S1200E 個数レジスタ数. LUT 数スライス数 Block RAM 数 I/O ブロック数. 17344 17344 8672 28 250. 図 9 k-means の階層関係 Fig. 9 Layered structure of k-means. . 表 2 評価対象回路のリソース使用量 Table 2 Amount of resources in the target circuit for evaluation 評価対象 k-means 法テストプログラム. レジスタ数. 3406(19%) 6509(37%). LUT 数 5816(33%) 11043(63%). BRAM 数 8(28%) 30(107%) 図 10 テストプログラムの階層関係 Fig. 10 Layered structure of test program. は統合され，利用する FPGA の個数が最小化される．. 5. 評. . 価. Xilinx 社の FPGA である XC3S1200E の利用を想定し，回路分割の評価を行う．XC3S1200E のリソース量を表 1 に示す．評価実験を行った PC のスペックは，Intel Core i5-750 Processor 2.66GHz，メインメ. 表 3 k-means 分割時の各 FPGA のリソース使用量 Table 3 Amount of resources in k-means for partitioning レジスタ数. FPGA1 FPGA2. 2376(13%) 1030(5%). LUT 数 3680(21%) 2136(12%). BRAM 数 6(21%) 2(7%). 結線数. 82(32%) 82(32%). モリは 4GB，OS は Windows7 である．論理合成には，XilinxISE14.4 を使用する．回路分割システムの評価を行うために，アプリケーションプログラムを JavaRock によりハードウェア化する．評価対象として，通常の k-means 法のプログラムとソートや行列演算などをまとめたテストプログ. 図 11 k-means の分割結果 Fig. 11 Partitioning result of k-means. ラムを利用する．k-means 法のプログラムは実アプリ. . ケーションプログラムでの回路分割を想定する．また，テストプログラムでは複数のモジュールが配列の要素を使用し，重複モジュールが存在する場合を想定する．. RAM の利用は 1 つの FPGA のみで行われる．また，重複モジュールを格納した FPGA と接続することで，. 評価対象の回路構成（図 9，図 10）とリソース使用. 重複モジュールの機能を利用するため，分割前のリソー. 量 (表 2) を示す．図 9，図 10 の回路のリソース使用量. ス使用量よりも分割後の各 FPGA のリソース使用量. がそれぞれ 25%，40%以下に収まるように分割する．. の総和の方が少なく済む．4 つの FPGA は，FPGA. k-means 法には 2 つの FPGA を利用し，テストプロ. の I/O ブロック数内に収まるように 3 つに統合され，. グラムには 4 つの FPGA を利用して評価を行う．. FPGA のリソース使用量は 40%以下となる．. k-means 法のプログラムに対して，回路分割を行った結果が図 11 である．元回路の階層関係は分割後も. 6. 考. 察. 保持される．このときの各 FPGA のリソース使用量. JavaRock では，配列宣言された変数は BlockRAM. を表 3 に示す．各 FPGA のリソース使用量は 25%以. に変換される．そのため，配列の要素を利用するモ. 内に収められる．. ジュールには，BlockRAM アクセスのためのアドレ. 次に，テストプログラムに対する分割結果（図 12）. ス信号やデータ信号，制御信号が必要となり，信号線. と各 FPGA のリソース使用量 (表 4) を示す．配列宣. 数が多くなる．例として，BlockRAM アクセスを行. 言を行うモジュールと配列の要素を利用するモジュー. うモジュールの信号線のビット数 (表 5) を示す．配列. ルは同一 FPGA に格納される．そのため，FPGA 間. を利用するために 32 ビットの信号線が 3 つ追加され，. に跨る BlockRAM アクセスは存在せず，同一 Block-. 合計で 96 本の信号線が必要となる．配列を利用する. ⓒ 2013 Information Processing Society of Japan. 53.

(6) 組込みシステムシンポジウム2013 Embedded Systems Symposium 2013. ESS2013 2013/10/17. 表 4 テストプログラム分割時の各 FPGA のリソース使用量 Table 4 Amount of resources in test program for partitioning レジスタ数. FPGA1 FPGA2 FPGA3. 2927(16%) 1444(8%) 1184(6%). LUT 数 4307(24%) 2603(15%) 2481(14%). BRAM 数 8(28%) 10(35%) 8(28%). 結線数. 112(44%) 56(22%) 56(22%). 減を行った．提案する回路分割システムでは，Xilinx 社の論理合成ツールのみに対応するため，Altera 社をはじめとした他のベンダのツールへの対応を考える必要がある．また，複数種類の FPGA を対象とした回路分割手法の検討も行う．今後は，JavaRock を利用したハードウェア設計をさらに簡易化するために，. FPGA 間の通信インタフェースを考案し，実装と評価を行いたいと考えている．. 参. 図 12 テストプログラムの分割結果 Fig. 12 Partitioning result of test program. 表 5 各信号線のビット数 Table 5 Number of bit in each signal. insertsort method busy notify method busy notify method request reset insertsort method request clk input port insertsort data raddr input port insertsort data length input port insertsort data rdata. 1 1 1 1 1 1 32 32 32. ビットビットビットビットビットビットビットビットビット. ための信号線がモジュール内の信号線の 94%を占めており，その他の信号線と比較して，大きな比重となる．通信に利用される FPGA のピン数には限りがあるため，FPGA 間に跨る BlockRAM アクセスがある場合に，ピン数が不足する可能性がある．そのため，配列を利用するモジュール群を同一 FPGA にまとめることは，複数 FPGA 間での BlockRAM アクセスを避けるだけでなく，結線数を削減する面でも有用である．. 7. まとめ高位合成ツール JavaRock が生成する回路を対象に，回路分割システムを実装した．Java プログラム内での配列宣言が，FPGA 内蔵の BlockRAM に対応付けられることに着目し，クラスタリングを適用することで回路分割を行った．実験では，k-means 法と評価用のプログラムを対象に，指定した FPGA のリソース使. 考. 文. 献. 1) SystemC. http://www.systemcjapan.com/ 2) ImpulseC. http://www.impulseaccelerated. com/ 3) CyberWorkBench. http://www.nec.co.jp/soft/ cwb/ 4) Andrew Canis, Jongsok Choi, Mark Aldham, Victor Zhang, Ahmed Kammoona, Jason H. Anderson, Stephen Brown, and Tomasz Cza- jkowski : legup: high-level synthesis for fpga-based processor/accelerator systems , ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA), pp. 33-36 (2011) 5) JHDL. http://www.jhdl.org/ 6) Joshua Auerbach, David F. Bacon, Perry Cheng and Rodric Rabbah : Lime: a Javacompatible and synthesizable language for heterogeneous architectures, OOPSLA ’10 Proceedings of the ACM international conference on Object oriented programming systems languages and applications, pp.89-108 (2010) 7) JavaRock. http://javarock.sourceforge.net/ 8) 國上太旗, 宮島敬明, 天野英晴 : 高位合成における回路分割の実装, 電子情報通信学会技術研究報告, Vol.112, No.173, pp.55-60 (2012) 9) 三好健文, 船田悟史 : FPGA 向け高位合成言語としての Java の活用手法の検討, 情報処理学会第 53 回プログラミングシンポジウム, pp.59-68(2012) 10) 三好健文, 船田悟史 : JavaRock を用いた HW/SW 協調設計の検討, 信学技報, Vol.112, No.70, CPSY2013-21, pp.119-124(2012) 11) 榎戸健二, 三好健文, 小池恵介, 船田悟史, 藤波香織, 中條拓伯 : Reconfigurable Android における JavaRock によるハードウェア・アクセラレーション, 組み込みシステムシンポジウム 2012 論文集, Vol.2012, pp.144-153(2012) 12) Xilinx XST ユーザーガイド. http://japan. xilinx.com/support/documentation/swmanuals/ xilinx11/xstv6s6.pdf.. 用量に収まるように分割した．また，FPGA の I/O ブロック数とリソース使用量の観点から，分割回路を格納した FPGA を統合し，利用する FPGA の個数の削. ⓒ 2013 Information Processing Society of Japan. 54.

(7)