DAシンポジウム
Design Automation Symposium

DAS20212021/9/2

汎用高位合成系をバックエンドとする
RISC-V 機械語からのバイナリ合成
中道 凌1

石浦 菜岐佐2

近藤 匠1

概要：本稿では, バイナリ合成系の容易な実装手法として汎用の高位合成システムをバックエンドとして利用する方法を提案し, これに基づいて RISC-V 機械語からのバイナリ合成系を実装する. 本手法ではリンク済みの機械語プログラムを入力として与え, これを実行する CPU と機能等価なハードウェアの設計記述を合成する. この際, 機械語プログラムから CDFG (control data ﬂow graph) ではなく高位合成可能な C
プログラムを生成し, これを高位合成システムの入力としてハードウェアの設計記述を合成する. 提案手法に基づいて RISC-V の RV32IM 命令セットを対象とするバイナリ合成系を実装した結果, C プログラムを高位合成したものと比べ回路規模は 1.04–3.75 倍に増加するものの, 実行サイクル数とクリティカルパス遅延はほとんど同等のハードウェアを合成することができた.
キーワード：システム設計技術, バイナリ合成, 高位合成, RISC-V

Binary Synthesis from RISC-V Executable CodeUsing General-Purpose High-Level Synthesizer
Nakamichi Ryo1

Ishiura Nagisa2

Kondo Takumi1

Abstract: This artcle proposes a facile way to implement binary synthesizers which utilize existing highlevel synthesizers as their backends, and demonstrates its application to implement a binary synthesizer for
the RISC-V instruction set. We assume a type of binary synthesizers which take a linked executable binary
code as input and generate a design description of hardware which is functionally exquivalent to a CPU
running the code. In our method, a C program in place of a CDFG (control dataﬂow graph) is generated
from a binary code, which is fed into existing high-level synthesizers to produce a hardware design. In an
experiment using a commercial high-level synthesizer, the execution cycles and critical path delay of thecircuits, generated by our binary synthesizer from RV32IM binaries compiled from C codes, are almost thesame as those of the circuits generated by the high-level synthesizer from the C codes, though the circuit sizeis 1.04 to 3.73 times larger.
Keywords: System design technology, binary synthesis, high-level synthesis, RISC-V

1. はじめに現在, 組込みシステムは高機能化が進む一方, 性能だけでなく小型化や低消費電力化の要求が益々厳しくなっている.

これを解決する一手法として, ソフトウェアで行っていた処理の一部または全部を, 専用ハードウェア化する手法がある.
一般にハードウェアの設計は抽象度が低く, 開発コストが高くなる傾向がある. そこで, 効率的なハードウェア設

1

2

関西学院大学 大学院理工学研究科
Graduate School of Science and Technology, Kwansei Gakuin
Univ.
関西学院大学 工学部
School of Engineering, Kwansei Gakuin Univ.

ⓒ 2021 Information Processing Society of Japan計の手法として, 高位合成技術 (high-level synthesis) [1] を利用した設計手法が提案されている. 既存のプログラムを元に高位合成によって専用ハードウェアを合成することに39

DAシンポジウム
Design Automation Symposium

DAS20212021/9/2

より, 開発コストの削減が期待できる.

!"#$?@E=#$

しかし, 外部機器を制御するようなシステムでは, 割り込%&'()*+,-.'()*+

みハンドラや特殊な命令・レジスタを利用するプログラム/0/0

がアセンブリやインラインアセンブリで書かれることがあ

1234
%567

り, そのような場合には高位合成をそのまま適用することができない.

89:;<=>)

バイナリ合成 [2] は高位合成と同様の技術を用いて, 機?@>AB>)

械語プログラムからハードウェア設計記述を生成する手法である. 文献 [2] は MIPS, ARM, MicroBlaze, 文献 [3] で

C5DF$

は MIPS, 文献 [4] では RISC-V の機械語からハードウェ

C5D

ア設計記述を生成している. 文献 [5], [6] では MIPS のア

図 1

高位合成/バイナリ合成の流れ

センブリで書かれた割り込みハンドラを含むプログラムを
バイナリ合成によりハードウェア化している.

する.

バイナリ合成系は命令セットアーキテクチャ (ISA) ご

C 言語等のプログラミング言語は単一のメモリ空間を備とに処理系が必要となる. 既開発の高位合成系やオープン

えた計算機構による実行を想定しているが, 高位合成で合ソースの高位合成系 [7] が利用できる場合には, 機械語プ

成される回路の計算モデルは必ずしもこれに一致しない.

ログラムを中間表現の CDFG (control dataﬂow graph) にこのため, グローバル変数やポインタを用いて複数の関数変換する処理系を作成すればバイナリ合成系が実装できるやスレッド間でデータを共有するようなプログラムを高位[4]. しかし, その際にもデータフロー解析の処理が必要に合成でハードウェア化するためには, メモリアクセスを陽なる等, フロントエンドの CDFG へのポーティングにも比に扱うための書き換えが必要になる. また, 機器を制御す較的大きな工数が必要になることがある.

るようなシステムは, 割り込みハンドラや特殊な命令・レ

本稿では, バイナリ合成系の容易な実装手法として汎用ジスタを利用するプログラムがアセンブリやインラインア

高位合成システムをバックエンドとして利用する方法を提センブリで書かれることがあり, このようなシステムには案する. 機械語プログラムから高位合成可能な C プログラ

直接高位合成を適用することができない.

ムを生成し, これを汎用高位合成システムによってハードウェア化する. データフロー解析, スケジューリング, バイ
ンディング等の処理は汎用高位合成系が行うため, アセン
ブリコードから C プログラムへの変換系を実装するだけで容易にバイナリ合成系を開発できる.

2.2 バイナリ合成
バイナリ合成 [2] は機械語プログラムの一部または全部からハードウェア記述を合成する技術である.
文献 [2] では MIPS, ARM, MicroBlaze の機械語プログ

本手法に基づき RISC-V 機械語プログラムを入力とする

ラムの指定部分をハードウェアに合成するバイナリ合成手

バイナリ合成系を実装した. C プログラムをコンパイルし法を提案している. また 文献 [3] は MIPS R3000 を対象て得た RISC-V 機械語プログラムを用いて評価実験を行っに, 実行可能な機械語プログラム全体をハードウェア化すた結果, 元のプログラムから高位合成を行った場合と比べる手法, および, 機械語プログラムの指定部分を CPU と密て回路規模は 1.04–3.75 倍に増加するものの, 実行サイク結合したコプロセッサに合成する手法を提案している.

ル数とクリティカルパス遅延はほとんど同等のハードウェ
アを合成することができた.

2. 高位合成とバイナリ合成
2.1 高位合成

バイナリ合成は, ソースプログラムが書かれている言語に依存することなく (あるいはソースコードが存在せず機
械語プログラムのみ入手可能な場合でも) ソフトウェアをハードウェア化できる. 文献 [5], [6] では, MIPS のアセンブリやインラインアセンブリによって書かれた外部割り込

高位合成 [1] は, C 言語等の手続き型言語で書かれたハーみハンドラを含むシステムをバイナリ合成によりハード

ドウェアの動作記述から論理合成可能なレジスタ転送レベ

ウェア化している. 文献 [4] では, RISC-V からのバイナリ

ルのハードウェア設計記述を自動合成する技術である.

合成系において, インラインアセンブリで書かれたカスタ

一般的な高位合成の処理の流れを図 1 に示す. まず, 与

ム命令を含むプログラムをハードウェア化している.

えられた動作記述を解析し, 中間表現である CDFG を生成

バイナリ合成ではプログラム中に出現するメモリアクセ

する. CDFG に対して演算の実行のタイミングを決定する

スをそのままハードウェア化できるため, グローバル変数

スケジューリング, 演算器やレジスタの割当を決定するバやポインタを用いたプログラムもそのまま合成対象にでき

インディングを行い, レジスタ転送レベルのハードウェア

る. また, 機械語プログラムの解析や盗用を避ける目的で設計記述 (HDL; Hardware Description Language) を生成

バイナリ合成により CPU とコードをハードウェアに置きⓒ 2021 Information Processing Society of Japan40

DAシンポジウム
Design Automation Symposium

IM

DM

DAS20212021/9/2

DM

bin
prog

*.$*%

/01'()*+!"#$%& '()*+

!"#$*

,#-.*

2!"#$3

%#F

!"#$%
& 45

CPU

& '()*+

HW
図 26789:;<

本稿で想定するバイナリ合成=>?@A!BCDE

図 3

本手法によるバイナリ合成の流れ換えるという用法も考えられる.
バイナリ合成系の処理の流れを図 1 に示す. 機械語プロ!!!
<0-,+84=9><0-,?+@
AA+>:?+B/=/&%3+54&50#/+&/;-#$/&##$%$-9+4-=$CDE$+./&0+F+*G#$%$-9+4-=$CDE$+&%G#$%$-9+4-=$CDE$+#5G#$%$-9+4-=$CDE$+;5G#$%$-9+4-=$CDE$+$5G!!!

グラムから CDFG を生成すれば, 後続の処理は高位合成と共通である. 文献 [4] の RISC-V 用バイナリ合成系は,MIPS 用バイナリ合成系 [3] の CDFG 生成部だけを新規開発して実装している. このように既開発の高位合成系/バイナリ合成系やオープンソースの高位合成系が利用できる
場合には CDFG をインタフェースとしてフロントエンド

AA+>D?+H/I0&J#$%$-9+4-=$)E$+HKHECLBMNOMPG#$%$-9+4-=$)E$+HKHEDLBMNOMPG#$%$-9+4-=$)E$+HKHE:LBMNOMPG#$%$-9+4-=$)E$+HKHE*LBMNOMPG

を実装すればバイナリ合成系が得られる. しかし, 高級言語
レベルでデータフロー解析や制御解析を行なっている場合には, フロントエンドの実装にも工数を要することがある.

3. 高位合成系をバックエンドとするバイナリ
合成
本稿では, 新しい命令セットアーキテクチャに対するバイナリ合成系を容易に実装する手法として, 機械語プログ
ラムから CDFG ではなく高位合成可能な C プログラムを!!!
"#$%&$'()*******(+%,,- ./&01./&01*)******2(+34- #51*67889)******)(+0&- #51#51*)******9(+34- %*1*62)*****:*(+%,,- ;51%*12)*****:2(+34- $*1*6)****!!!

AA+>C?+Q=#$&49$-0=##$%&$(#5 F+*67889+""+:DG#5 F+#5 R+>*?G%*+F+*62+""+:DG;5 F+%*+N+>2?G$*+F+*6)****+""+:DG!!!

生成し, これを汎用高位合成システムの入力としてハード
S

ウェアの設計記述を合成する方法を提案する.
図 4

本手法で生成する C プログラムの構成

3.1 合成の流れ
本稿のバイナリ合成では, 図 2 に示すように, 命令メモ
リ内のプログラムとこれを実行する CPU およびデータメ
モリを機能的に等価なハードウェアに変換する.

3.2 ALU 演算命令と符号の扱い
レジスタはレジスタと同じビット長の符号なし整数型のローカル変数に変換する. 図 4 の (1) は 32 ビットのレジ

図 3 に本手法によるバイナリ合成の流れを示す. 入力はスタの変換例であり, uint32 t はバックエンドの高位合成

リンク済みの実行可能な機械語プログラムである. これを系が 32 ビット符号なし整数として扱う C 言語の型になる

逆アセンブルしたものから, プロセッサ上でその命令列をように定義する.

実行するのと機能等価な C プログラムを生成し, これを汎加減算や論理演算, シフト演算を行う命令は, 各命令の動用高位合成系に入力して, ハードウェア設計記述を生成す

作を C 言語の文で表現する. RISC-V の 32 ビット ALU

る. データフロー解析, スケジューリング, バインディング

命令の変換例を表 1 に示す. 例えば “add rd,rs1,rs2” と等の処理は汎用高位合成系が行うため, アセンブリコード

いう命令は “rd = rs1 + rs2;” という C 言語の文に変から C プログラムへの変換処理系を実装するだけで容易換すればよい.

にバイナリ合成系を開発できる.

レジスタを符号なし整数型の変数で表現しているため,アセンブリコードから生成する C プログラムの構成法

命令がオペランドを符号付き整数として扱っている場合には種々考えられるが, 本稿では図 4 に示すように 1 つのア

は C プログラム中に型変換 (キャスト) が必要になる. しセンブリコードから 1 つの C 言語の関数を生成する. 関かし, 2 の補数表現を用いる CPU であれば, 符号なし整数

数は, レジスタとメモリをローカル変数として宣言する部

として演算を行っても計算結果は一致する. 例えば, “addi分 (図中 (1)(2)) と, 命令列を C 言語のコードに変換した

sp,sp,-32” は “sp = sp + (-32);” に変換すれば, C 言

部分 (図中 (3)) から成る.

語の型変換で −32 は 4294967264 に変換されて sp に加算ⓒ 2021 Information Processing Society of Japan

41

DAシンポジウム
Design Automation Symposium#define SINT8(u)DAS20212021/9/2((int8_t)((u) & 0x7f) + (((u) & 0x80) ? -128 : 0))#define SINT16(u) ((int16_t)((u) & 0x7fff) + (((u) & 0x8000) ? -32768 : 0))#define SINT32(u) ((int32_t)((u) & 0x7fffffff) + (((u) & 0x80000000) ? -2147483648 : 0))
図 5
表 1
命令

符号なしから符号付きへの変換例

ALU 演算命令の変換例
C プログラム

add a5,a4,a5

a5 = a4 + a5;

addi sp,sp,-32

sp = sp + (-32);

and a4,a4,a5

a5 = a4 & a5;

sll a5,a5,a0

a5 = a5 << (a0 & 31);

sra a6,a4,a6

a6 = SINT32(a4) >> (a6 & 31);

srl a7,a4,a7

a7 = a4 >> (a7 & 31);

.0

./.

.1

.2

.3

!!"

!"

$%&'(

#"
#-

#"

され, 結果の下位 32 ビットが sp に代入されるが, 得られ)*+,'(

図 6

メモリの扱いる表現を符号付き整数と見れば, sp の値に −32 を加算した結果に等しくなる.

#define LB 0x7ffbfec

しかし, 算術シフト命令 (表 1 の sra) のように, 必ず C
言語の符号付き整数型の演算を用いなければならない場合には, 型変換 (キャスト) が必要になる. 多くの C コンパ
イラでは, 符号なし整数を同精度の符号付き整数変数に代#define GB 0xc0000000#define MA_G(a) ( (((a) - GB) / 4) )#define MA_L(a) ( (((a) - LB) / 4) + GN )#define MA(a) ( ((a) >= GB) ? MA_G(a) : MA_L(a) )図 7

メモリアドレスのインデックスへの変換例

入した場合には単純にコピーを行うコードを生成する. しかし, 最上位ビットが 1 となっている符号なし整数を同精

ビット右シフトすればよい.

度の符号付き整数型に変換すると, C 言語の仕様上は未定• mulhsu 命令は符号付き 32 ビットの rs1 と 符号なし

義動作となり結果は保証されない. そこで安全のため, 図 5

32 ビットの rs2 の乗算結果の上位 32 ビットをレジに示すマクロ (SINT32, SINT16, SINT8) を用いて未定義動

スタ rd に格納する命令である. これは 両オペランド

作のない型変換を行うようにする.

*1

を符号付き 64 ビット整数型に拡張して乗算を行い, 結
果を 32 ビット右シフトすればよい.

3.3 乗算命令
計算の中間結果が汎用レジスタのビット数を超える場合
は, ビット数に応じた整数型を用いる. RISC-V の 32 ビッ
ト乗算命令の変換例を表 2 に示す.

• mul 命令は符号なし 32 ビットレジスタ rs1, rs2 の乗算結果の下位 32 ビットをレジスタ rd に格納する命

3.4 ロード/ストア命令
本稿では, バイト単位でアドレッシングが可能で, かつ主としてワード単位でアクセスが行われるメモリを想定し,
図 4 のように 1 バイトデータの配列変数をワードのバイト数だけ用意して記憶する.

令である. C 言語の 32 ビット符号なし整数型の演算

配列変数は必要なサイズだけを用意し, CPU がアクセスでは結果の下位 32 ビットだけが残るので, 単に “rdするアドレスを配列のインデックスに変換する. 例えば図= rs1 * rs2;” という文に変換すればよい.

6 のように, スタック領域の開始番地と必要サイズがそれ• mulh 命令は符号付き 32 ビットレジスタレジスタ rs1,

ぞれ LB, LN (ワード), ヒープ領域 (グローバル領域) の開

rs2 の乗算結果の上位 32 ビットをレジスタ rd に格始番地と必要サイズがそれぞれ GB, GN (ワード) の場合,納する命令である. これは rs1 と rs2 を符号付き 32

合計 LN+GN ワード分の配列を用意し, メモリのアドレス

ビット整数型に変換した後, 符号付き 64 ビット整数型

がどちらの領域のものかに応じてその開始番地を減じるこに拡張して計算を行い, 結果を 32 ビット右シフトしとによりアドレスをインデックスに変換する. 変換のためたものを rd に代入すればよい.

のマクロの例を図 7 に示す. MA(a) は, アドレス a に対応• mulhu 命令は符号なし 32 ビットレジスタレジスタ*1

するインデックスを与える.

rs1, rs2 の乗算結果の上位 32 ビットをレジスタ rd

複数バイトのロード/ストアは, 複数バイトデータの並列に格納する命令である. これは rs1 と rs2 を符号な読み書きに変換可能な C コードに変換する. 変換例を表 3

し 64 ビット整数型に拡張して乗算を行った結果を 32に示す. “lw”, “lh”, “lb” はそれぞれ 4 バイト, 2 バイト,

LLVM では最適化によってこれが単純なコピーにコンパイルされる.

ⓒ 2021 Information Processing Society of Japan

1 バイトのロード, “sw”, “sh”, “sb” はそれぞれ 4 バイト,
2 バイト, 1 バイトのストア命令である.
42

DAシンポジウム
Design Automation Symposium

DAS20212021/9/2

表 2

乗算命令の変換例

命令

表 3
命令

lw rd,offset(rs)C プログラム

mul rd,rs1,rs2

rd = rs1 * rs2;

mulh rd,rs1,rs2

rd = ((int64 t)SINT32(rs1) * (int64 t)SINT32(rs2)) >> 32;

mulhu rd,rs1,rs2

rd = ((uint64 t)rs1 * (uint64 t)rs2) >> 32;

mulhsu rd,rs1,rs2

rd = ((int64 t)SINT32(rs1) * (int64 t)rs2) >> 32;

ロード/ストア命令の変換例
C プログラムrd = (MEM 3[MA(rs+offset)] << 24)+ (MEM 2[MA(rs+offset)] << 16)+ (MEM 1[MA(rs+offset)] << 8)!!!
"#####$%&'($$)'(*+,-./+*0"#####$"&'($$)'(#+,-./+#"#####$1&'234'(*+(5+"#####-%"#####-#&'672'(#+(*+(5"#####-%&'($$'(5+(5+(#!!!

!!!
(*'8',-./'9':*0;<(#'8',-./'9':#;<)=':>?@A:(*;'B'>?@A:(5;; C/4/'D"#####-%<(#'8'(*'E :(5;<D"#####-%&(5'8'(5'9':(#;<!!!

+ (MEM 0[MA(rs+offset)]);lh rd,offset(rs)

図 8

rd = (MEM 1[MA(rs+offset)] << 8)

分岐命令の変換例+ (MEM 0[MA(rs+offset)]);lb rd,offset(rs)rd = (MEM 0[MA(rs+offset)]);sw rs2,offset(rs1)

MEM 3[MA(rs1+offset)] = (rs2 >> 24);!!!
(&&&&&)*3$4#5$"#6(&&&&&1(!!!

!!!
"#$%$&'(&&&&&)*+),-./.$0(&&&&&1(,0(&&&&&2&3!!!
0(&&&&&1(3!!!

MEM 2[MA(rs1+offset)] = (rs2 >> 16);
MEM 1[MA(rs1+offset)] = (rs2 >> 8);
MEM 0[MA(rs1+offset)] = (rs2 & 255);
sh rs2,offset(rs1)

MEM 1[MA(rs1+offset)] = (rs2 >> 8);
MEM 0[MA(rs1+offset)] = (rs2 & 255);

sb rs2,offset(rs1)

図 9

ジャンプ命令の変換例

MEM 0[MA(rs1+offset)] = (rs2 & 255);

3.5 制御移転命令!!!
"#####"$%&'()*+,)-.#/)'0!!!

分岐命令は分岐条件を計算する文と goto 文に変換する.

blt (branch if less than) 命令の変換例を図 8 に示す. 分
岐条件が成立すれば, 分岐先アドレスに対応するラベルの

図 10

!!!
12*/)'*3*#*44*#5"#####6$0*7-8-*("#####6$9,(:,*12*/)'*3*#*44*#5"#####;"0*7-8-*("#####;"9,(:,*12*/)'*3*#*44*#5"#####<#0*7-8-*("#####<#9,(:,*12*/)'*3*#*44*#5"#####=60*7-8-*("#####=69,(:,*12*/)'*3*#*44*#5"#####=$0*7-8-*("#####=$9!!!

レジスタジャンプ命令の変換例

文にジャンプする. これを実現するため, 前処理で関数の先頭や分岐先に指定されているアドレスを列挙し, これら

ロールステータスレジスタに関する命令を除く全 55 命令のアドレスにある命令に対応する文にラベルを付与するよ中 45 命令を処理可能とした. バックエンドの高位合成系

うにする.

としては Vivado HLS (2020.01) を用い, アセンブリを C

本稿では, 1 つのアセンブリコードから 1 つの C 言語の関数を生成するので, サブルーチンの呼び出しと戻りについても goto 文を用いて書き換えられる.
呼び出しに用いられるジャンプ命令は, 仕様に従って戻プログラムに変換する処理系は Python 3.7.7 で実装した.
実装したシステムのテストは, C プログラムを入力とする高位合成系と本手法のバイナリ合成系でそれぞれ回路を生成し, それらのシミュレーション結果が一致するかをり番地を記憶した後にジャンプするようにすればよい. jal

確認することにより行った. テスト手法を図 11 に示す.

(jump and link) 命令の変換例を図 9 に示す. ra に次の命

まず, 合成対象の関数とテストベンチを用意する. 合成対令のアドレスを戻り番地として格納し, アドレス 800000d8

象の関数はこのまま高位合成に入力することができ, テに対応するラベル L800000d8 にジャンプしている.

ストベンチを用いてハード/ソフト協調シミュレーション

サブルーチンからの戻りに用いられるレジスタジャンプ(Co-Simulation) を行って “result hls” を得る. 一方, バイ

命令は分岐先が実行時の値に依存するため, ジャンプ先のナリ合成は合成対象の関数は関数名を “main” へと書き

候補を前処理で列挙しておき, 条件分岐文によって分岐先換えてコンパイルすることによりリンク済みの機械語プが選択されるようにする. jalr (jump and link register)

ログラムを得る. この機械語プログラムを入力として本命令の変換例を図 10 に示す. レジスタ ra にオフセット手法によるバイナリ合成を行い, Co-Simulation によって(図においては 0) を加えたアドレスに対応するラベルに“result bs” を得る. “result hls” と “result bs” を照合する

ジャンプする.

ことにより動作確認が行える.

4. 実装と実験6 本の C プログラムから得られる RISC-V 機械語プログ
ラムに対して本手法でバイナリ合成を行った. コンパイラ

提案手法に基づき, RISC-V 機械語プログラムを入力とには riscv32-unknown-elf をターゲットとする gcc-10.2.0

するバイナリ合成系を実装した. 対象とした命令セットはを用い, 最適化オプションには –O3 を指定した. 結果を

RV32IM であり, fence 命令や ebreak, ecall 命令, コント

表 4 に示す. “binary search” は整数配列に対して二分探ⓒ 2021 Information Processing Society of Japan

43

DAシンポジウム
Design Automation Symposium

DAS20212021/9/2

表 4

合成結果
本手法

HLS
delay

delay

命令数

FF

LUT

38

230

523 (1.31)

0

21 (0.80)

5.924

170

639 (3.36)

090,002 (1.00)

6.514

1,152

2,031 (3.73)

010,416 (0.92)

6.830

1,526

1,413 (1.04)

3

216 (1.02)

8.470

29

546

534 (1.07)

02,443 (0.91)

6.880

221

3,757

4,975 (1.07)

67

264 (1.03)

8.470

FF

LUT

DSP

cycle

binary search

164

405

0

26

6.720

bubble sort

112

190

0

90,3006.514

37heap sort

247

544

0

11,300

7.040

103

lcm

1,419

1,363

3

211

8.470

39

prime

464

499

0

2,679

8.250

FSM

2,917

4,639

64

257

8.470

[ns]

DSP

cycle

[ns]

GCC optimization: –O3, High-Level Synthesizer: Xilinx Vivado (2020.1), Target: Xilinx Artix-7 (xc7a100tcsg324-1)
表 5

FSM において状態数を変化させた結果

高位合成
状態数

表 6

本手法

delay

FF

LUT

DSP

cycle

8.470

127

1,708

2,505

34

274

8.470

266

8.470

221

3,757

4,975

67

264

8.470

257

8.470

423

6,708

9,117

194

256

8.470

256

258

8.644

809

10,826

16,512

258

258

8.644

512

257

8.670

1,645

24,80730,121

770

257

8.670

1,024

258

8.470

3,627

53,98366,440

1,026

257

8.470

LUT

DSP

cycle

16

1,639

2,379

32

273

32

3,078

4,679

64

64

5,798

9,364

128

128

11,822

18,732

256

24,35037,302512

60,81072,386[ns]

最適化オプションを変化させたバイナリ合成結果の比較(a) binary search
命令数

HLS

FF

LUT

cycle

delay
[ns]

164

405

22

6.720

65

407

1,530

104

8.661

本手法 –O1

37

264

625

29

7.557

–O2

42

198

530

21

7.113

–O3

38

230

523

21

5.924

HLS

)*%&+$#(&()!*$./"0'()!*+$,--2

FGHI&J

delay

FF

LUT

cycle

247

544

11,300

7.040

[ns]

–O0

159

3,553

9,881

64,9568.661

本手法 –O1

92

3,299

4,335

13,106

8.661

–O2

84

3,441

4,790

15,365

8.591

–O3

103

1,152

2,031

10,416

6.830

KLMNO

!"#$%&!"'()!*+$,
--2
%&'()

!"#!$"%&'(&!"#$(b) heap sort

[ns]

#$=>
)*%&(&

–O0

命令数

delay

命令数

FF

!"#$%&!"'()!*+$,--./"0'+1--2-./012342?/*+,-./01:8345-./012345@ABC?D.8E9?A/@ABC?D.8E9?A/

673.891:83

図 11

;<

673.89123

実装したシステムの動作概要とテスト手法

索を行うプログラム, “bubble sort”, “heap sort” は整数配列をそれぞれバブルソート, ヒープソートでソートするプでは高位合成と同程度である. 実行サイクル数やクリティ

ログラム, “lcm” は 2 整数の最小公倍数を求めるプログ

カルパス遅延はすべてのプログラムで高位合成と同程度と

ラム, “prime” は素数判定を行うプログラム, “FSM” はラなった. “bubble sort” や “heap sort” で回路規模が増大

ンダムに生成した状態遷移機械 (32 状態で, 遷移先の計算した原因は現在調査中である.

に剰余演算を用いている) で 128 回の状態遷移を行うプ

表 6 は “binary search” と “heap sort” について, 機械

ログラムである. “HLS” は参考のために元の C プログラ

語プログラムを得る際のコンパイラの最適化オプションを

ムを Vivado HLS で直接高位合成した結果である. “FF”,–O0, –O1, –O2, –O3 と変化させて実験した結果である. 最“LUT”, “DSP” はそれぞれの使用数, “cycle” は実行サイ

適化を行わない –O0 に比べて –O1, –O2, –O3 で回路規模

クル数, “delay” はクリティカルパス遅延 (ns) を示す. “命と実行サイクル数が減少しているが, 最適化の強度が必ず令数” は機械語プログラムの命令数である.

しも回路の規模や性能の改善に直結しているわけではない.

回 路 規 模 (FF 数 と LUT 数) は, “bubble sort” や

これは, CPU での実行に適した最適化が必ずしもバックエ“heap sort” で 3 倍以上の増加が見られるが, それ以外

ンドの高位合成における最適化にマッチしないためと考えⓒ 2021 Information Processing Society of Japan

44

DAシンポジウム
Design Automation Symposium

DAS20212021/9/2

られる.
また, 機械語プログラムの規模 (命令数) と回路規模の関係を見るために, 状態遷移を行うプログラムの状態数を変化させて合成を行った. 結果を表 5 に示す. 遷移回数はす
べて 128 回である. 命令数にほぼ比例して回路規模や演算器数は増加するが, 実行サイクル数やクリティカルパス遅延が著しく増加することはなかった.

5. おわりに
本稿ではバックエンドとして汎用高位合成システムを利用したバイナリ合成システムの容易な実装手法を提案した.
高位合成に比べて回路規模が増加することはあるが, 実行
サイクル数やクリティカルパス遅延は同程度のハードウェ
アを合成することができた.
今回の方式では動作確認と高位合成との比較を行うためにデータメモリをハードウェア内部に組み込んだが, ヒー
プ (グローバル) 領域のデータは外部のメモリとして扱う必要があると考えている. また, レジスタジャンプやメモ
リアクセスの効率化を行う等, 高位合成の入力に適した C
プログラムの生成が今後の課題として挙げられる.
謝辞 本研究に関して有益な御助言を頂いた京都高度技術研究所の神原弘之氏, 立命館大学の冨山宏之教授, 元立命館大学の中谷嵩之氏, 元関西学院大学の浜名将輝氏に感謝致します. また, 本研究に関してご協力, ご討議頂いた関西
学院大学石浦研究室の諸氏に感謝いたします. 本研究は一部 JSPS 科研費 19H04081 の助成による.
参考文献
[1]

[2]

[3]

[4]

[5]

[6]

[7]

Gajski, D. D., Dutt, N. D., Wu, A. C. and Lin, S. Y.:
High―Level Synthesis: Introduction to Chip and System
Design，Springer Science & Business Media (2012).
Stitt, G. and Vahid, F.: Binary synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 12, No. 3, pp. 1–30 (2008).
Ishiura, N., Kanbara, H. and Tomiyama, H.: ACAP: Binary synthesizer based on MIPS object codes, Proc. ITCCSCC 2014, pp. 725–728 (2014).
浜名将輝，石浦菜岐佐： RISC-V 機械語プログラムからのバイナリ合成，研究報告システムと LSI の設計技術 (SLDM)，
Vol. 2020, No. 19, pp. 1–5 (2020).
伊藤直也，石浦菜岐佐，冨山宏之，神原弘之： 外部割込みのハンドラを含むプログラムからの高位合成，DA シンポ
ジウム 2014 論文集， Vol. 2014, pp. 121–126 (2014).
Ito, N., Oosako, Y., Ishiura, N., Kanbara, H. andTomiyama, H.: Binary synthesis implementing externalinterrupt handler as independent module, 2017 International Symposium on Rapid System Prototyping (RSP),
IEEE, pp. 92–98 (2017).
Canis, A., Choi, J., Aldham, M., Zhang, V., Kammoona, A., Czajkowski, T., Brown, S. D. and Anderson, J. H.: LegUp: An open-source high-level synthesis tool for FPGA-based processor/accelerator systems,
ACM Transactions on Embedded Computing Systems(TECS), Vol. 13, No. 2, pp. 1–27 (2013).

ⓒ 2021 Information Processing Society of Japan

45