社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

不定サイクル演算に対応した分散制御における動的演算バインディング
山下 真司†

石浦菜岐佐†† 関西学院大学 理工学部 〒 669–1337 兵庫県三田市学園 2-1
あらまし

オペランドや実行時の状況によって実行サイクル数が変動する不定サイクル演算器を含む回路を効率的に制御するための分散制御方式において, 演算を実行するタイミングや順序だけでなく, 演算器も動的に決定できる方式を提案する. Del Barrio の分散制御方式は, 演算器毎に状態機械を設けて演算の実行制御を行うものであり, 回路規模の増加は少ないが, 同一演算器に割り当てられた演算の実行順序は変更できない. Pilato の分散制御方式は, 演算毎にその実行の可否を表わす状態変数を設けて演算の実行を制御するため, 演算の実行順序を動的に変更できるが, 各演算を実行する演算器は固定されていた. 本稿の制御方式は, Pilato の方式を拡張することにより, 各演算が実行可能になった時点で空いている演算器を使用できるようにするものである. 評価実験を行なったところ, 回路規模や遅延は増加するが, 実行サイクル数を約 6〜10% 削減できることが確認できた.
キーワード

高位合成, 分散制御, 動的演算バインディング

Dynamic Operation Binding in Distributed Controller for Supporting
Functional Units with Variable Latency
Shinji YAMASHITA† and Nagisa ISHIURA†† Kwansei Gakuin University, 2-1 Gakuen, Sanda, Hyogo, 669–1337, Japan
Abstract This article presents a new distributed method for controlling circuits with variable latency units, which
can dynamically assign operations to functional units as well as it adjusts timing and order of operation execution.
The Del Barrio’s method controls each functional unit with a dedicated state machine and adaptively changes thetiming of operation execution, but the execution order of the operations for each unit is fixed. The Pilato’s method
allows the change of execution order by assigning a state variable to each operation to express its executability, buteach operation is bound to a fixed functional unit. Our method extends the Pilato’s method so that operations may
be processed using either one of free units as soon as they are executable. A preliminary experiment shows thatexecution cycles are reduced by 6 to 10%, though there is significant increase in circuit size and delay.
Key words High-Level Synthesis, Distributed Controller, Dynamic Operation Binding

1. は じ め に
近年の半導体技術の発展に伴い, 益々大規模で複雑な集積回まう.
これに対し, 演算器からの完了信号をもとに制御を実行時に変更する可変スケジューリング [2] が提案されている. 可変ス路が実装できるようになっている. その設計を効率化する手段

ケジューリングは, 可能な実行サイクル数の全組み合わせに対として, プログラミング言語などの動作記述を入力としてハーする制御パターンを網羅した状態機械で演算の実行を制御する

ドウェアの設計記述を自動生成する高位合成技術 [1] の実用化方式であり, 各演算の実行タイミングを動的に変更する効率的が進められている.

な制御が可能になる. しかし, 状態数が著しく増加し, 合成され従来の高位合成では, 全ての演算が固定のサイクル数で完了することを前提として, 演算を実行するタイミングや演算器をるハードウェアの回路規模や遅延が許容できないほど大きくなる恐れがある.

決定する. しかし, オペランドの値や利用状況に依存して実行

この問題を解決する手法として, 分散制御があげられる. 分

時にサイクル数が変化する不定サイクル演算も存在する. 回路

散制御は, 独立に動く複数の状態機械で演算の制御を行うもの

中にこのような演算器が含まれる場合, 固定されたタイミングであり, 制御回路の規模を抑えつつ, 不定サイクル演算の実行をで演算の実行を制御すると, どうしても無駄な待ちが生じてし効果的に制御することができる.

—1—

分散制御の方式としては, Del Barrio の方式 [4] と Pilato の方式 [5] が提案されている. Del Barrio の分散制御方式は, 演
M1

算器毎に状態機械を割り当て, その演算器に割り当てられた演

M2

A1

M1M2算の実行を制御する方式である. 異なる演算器にバインディン

f2

グされている演算は, 独立に動作タイミングを変更できるため,

f1 : a = x1 * y1;

集中制御方式のように制御回路が大きくなるのを防ぐことがで

f1

f2 : b = x2 * y2;

f1

f2

f3 : c = x3 * y3;

きる. しかし, 同一演算器に割り当てられている演算は, 設計時

f4 : d = a + b;に決められた順序でしか実行ができないため, 後の演算が先に

f5 : e = b + z;
f6 : f = c + z;

実行可能になっても前の演算が終わるまでそれを実行できない.

Pilato の分散制御方式は, 各演算に対して実行の可否を表す 1

A1

f1ビットの状態変数を割り当てて制御する方式であり, 同一演算器に割り当てられている演算の実行順序も動的に変更すること

f4× × ×f2

f4ができる. しかし, 設計時に決められた演算器以外で演算を実

f3

f4

f5

f5

f6

f6+f5行することはできないため, 同一演算器に割り当てられた複数

f3

f3

f6++の演算が同時に実行可能になっても, 一方の演算は順番待ちをしなければならない.

(a) データフローグラフ(b) スケジューリング

(c) 固定制御方式

図 1 不定サイクル演算を考慮しない制御

そこで本研究では, 演算の実行タイミングと実行順序だけでなく, 実行を行う演算器も実行時に決定できる制御方式を提案
する. 本制御手法は Pilato の分散制御手法を, 各演算を複数の演算器にバインディングできるように拡張したものである. 評
価を行なったところ, 動的演算バインディングを適用した結果,

M1

M2

Pilato の制御方式に比べ回路規模 (LUT 数) は 2〜26%増加し,

M1

A1

M2

きた.

f3

f1

M1

M2

f2

f2

遅延は 17〜38%増加したが, 平均サイクル数は 6〜10%削減で

A1

f5

2. 不定サイクル演算に対応した分散制御

f6

2. 1 不定サイクル演算

f4A1

f2

f1

f3

f4

f1

f5

f3f4

不定サイクル演算とは, オペランドの値や利用状況に依存しf5て実行時にサイクル数が変化する演算である. 例えば, 乗除算
では, オペランドの値によっては少ないサイクル数で計算を完f6了するものがある. キャッシュを持つメモリシステムへのアクセスでは, キャッシュにヒットするかどうかに依存してサイクルf6(a) 可変スケジューリング

数が変化する. また, 回路の経年劣化に伴って遅延が増えるこ

図2(b) Del Barrio の方式(c) Pilato の方式

不定サイクル演算を考慮した制御とによりサイクル数が増加する場合もある.
図 1(a) のようなデータフローグラフが与えられたとき, 加算を 1 サイクルで行う加算器 A1 と乗算を 1〜3 サイクルで行う乗算器 M1, M2 でこれを実行する場合を考える. (b) は, 乗算

M1 M2 A1

S1に 3 サイクルを要するとしてスケジューリングした例である.

f1S2M1 M2 A1

ここで, 演算 f2, f3 が 1 サイクルで完了したとする. 従来の制

f1

御手法 (c) では, 演算の f2, f3 の後続の演算の実行を早めるこ

2. 2 可変スケジューリング

!d1, d2

f5

S5!d1, d2

f3

d1, d2S4

M1 M2 A1
f1

M1 M2 A1

f4

f3

図 1 の例に対し, 可変スケジューリングによって制御を行なっ!d2

d2

S10

S9

M1 M2 A1

f6

M1 M2 A1

S12

f4

f3

S11

d1, !d2

f4

S7

d1, d2M1 M2 A1M1 M2 A1
f3

S13

f5

f4

M1 M2 A1

S16

f2

f6!d1

d2

M1 M2 A1
f5

S14

M1 M2 A1
f4

d1

S15M1 M2 A1

S8!d1

d1

M1 M2 A1た例を図 2(a) に示す. この例は, 図 1(c) と同様に演算 f1 が 3サイクル, 演算 f2, f3 が 1 サイクルで完了している. 演算 f5 は

f2

f4

可変スケジューリング [2] は, 演算器からの完了信号を基に各的に実行し, 全体の実行サイクル数を減少させるものである.

f3!d1, d2
S6f3

演算の実行タイミングを動的に変更することにより演算を効率

M1 M2 A1

d1, d2M1 M2 A1!d1, !d2

S3

d1, !d2

d1, !d2とはできない. また, 乗算器 M2 は 2 サイクル目以降空いているにもかかわらず, 演算 f3 を実行することはできない.

f3!d1, !d2

f2

M1 M2 A1

S17

M1 M2 A1
f5f6

S18

M1 M2 A1

依存する演算 f2 が 1 サイクル目に完了するため 2 サイクル目に実行することができる. また, 演算 f3 は演算 f2 を完了した乗図 3 可変スケジューリングの状態機械の例

算器 M2 で 2 サイクル目に実行できるため, 演算 f6 は 3 サイク—2—

C1
S1
S2

C2

f1

C3

f2

S1

f3

S1
S2
S3

start

donestart

M1

done

M2

start

start

f4

rop1
aop1

EM1
f5

done1

done1

rop2

rop3

EM3
A1

図 4 Del Barrio の分散制御方式ル目に実行することができる. 結果, この例では合計 4 サイクdone3

done5

done5
done6

done

M2

RM3

start
done

A1

rop6

EM6

aop6
done6

機械の例を図 3 に示す. この状態機械は乗算器 M1, M2 の完了

END

信号 d1, d2 の真偽に基づいて状態を遷移させる. 例えば, 状態

end

S1 は乗算器 M1 で演算 f1 を, 乗算器 M2 で演算 f2 を実行し,する.

start

rop4

aop5

り実現できる. 図 1 の例に対する可変スケジューリングの状態

d1 と d2 の真偽によって状態 S1, S2, S3, S6 のいずれかに遷移

RM2

rop5

EM5

イクル数の組み合わせに対応する状態機械を構築することによ

done3

done4

done4

このような制御は, あらかじめ全演算の可能な全ての実行サ

aop3

aop4

EM4

ルで実行を完了することができる.

M1

done2

done2

done

start
done

aop2

EM2

f6

RM1

図 5 Pilato の分散制御方式における制御回路の構成

しかし, 入力の動作記述によっては状態数が膨大になる可能性がある [3]. 状態数の増加は制御回路やデータパスのマルチプレクサの増大につながり, 面積と遅延が許容できないほど大きくなる恐れがある.

2. 3 Del Barrio の分散制御方式
Del Barrio の分散制御方式は, １つの演算器に１つの状態機械を割り当て, それぞれの状態機械で演算器に割り当てられた演算の実行を制御するものである. 図 1 の例に対する, Del Barrioの分散制御の例を図 4 に示す. 状態機械 C1, C2, C3 はそれぞれ演算器 M1, M2, A1 で実行する演算に対応する状態を持っている. これらの状態機械は, 図 3 の状態機械を演算器毎に分解したものと見ることができる. これによって, 制御のための状態機械を大きくすることなく, 異なる演算器にバインディングされてた演算の動作タイミングを独立に変更することができる.
しかし, 同一演算器にバインディングされている演算は, 設計時に決めた順序でしか実行できない. 図 1 の例に対し, DelBarrio の方式で制御を行なった例を図 2(b) に示す. 図 1(c) に比べると演算 f6 の実行を 1 サイクル早めることができるため,合計 6 サイクルで実行が完了する. しかし, 演算 f5 は 2 サイクル目に実行可能になっているにもかかわらず, 演算 f4 より先に実行することはできないため, 5 サイクル目まで実行できない.

2. 4 Pilato の分散制御方式
Pilato の分散制御方式は, 各演算に対して実行の可否を表す1 ビットの状態変数を割り当てて制御する方式である. その状
態変数が 1 になり, 割り当てられた演算器が空いていれば演算の実行を行う. これにより, 異なる演算器にバインディングされている演算だけでなく, 同一演算器にバインディングされている演算同士でも実行順序を動的に決定することができる. 図2(c) に示す. Del Barrio の方式 (b) では演算 f5 は f4 の後にしか実行できなかったが, Pilato の方式では演算 f4 を追い越して2 サイクル目に演算 f5 を実行できるため, 合計 5 サイクルで実行を完了することができる.

Pilato の分散制御方式は, 演算毎に生成される Execution
Manager (EM) と演算器毎に生成される Resource Manager(RM) によって制御を行う. 図 1 の例に対し, Pilato の分散制御方式の制御回路を構成した例を図 5 に示す. この例では,

EM1〜EM6 は演算 f1〜f6 に対応しており, RM1, RM2, RM3はそれぞれ乗算器 M1, M2, 加算器 A1 に対応している. この回路全体の開始信号 (start) が 1 になると, 演算 f1, f2, f3 に対応した EM1, EM2, EM3 が活性化し, 各演算の実行要求信号(rop1, rop2, rop3) の送信を開始する. rop1 と rop2 を受け取った RM1 は, 優先順位に従って演算 f1 を乗算器 M1 で実行する.

RM1 は演算 f1 の実行開始信号 (aop1) を EM1 とデータパスに送信し, aop1 を受け取った EM1 は rop1 の送信を終了する.

M1 による演算 f1 の実行が完了すると RM1 は EM1 に演算 f1の完了信号 (done1) を送信する. done1 を受け取った EM1 は演算 f1 に依存する演算 f4 に done1 を送信する. EM4 は done1と done2 の両方を受け取ると活性化し, rop4 の送信を開始, 以下同様に行う. この回路全体の終了制御機械 (END) は done4,done5, done6 を全て受け取ると終了信号 (end) を出力する.
しかし, Pilato の方式では, 演算を実行する演算器を変更することはできない. 図 2(c) の例では, 演算 f3 が実行可能で, 2サイクル目には乗算器 M2 が空いているにも関わらず, 演算 f3は乗算器 M1 でしか実行できないため, 4 サイクル目まで実行が開始できない.

1 の例に対し, Pilato の分散制御方式で制御を行なった例を図—3—

startstart

rop1_1

rop1

aop1_1

EM1

aop1

EM1

done1_1

done1

rop2_1aop2_1

EM2

RM1

done2_1

start
done

rop3_1

M1

EM3

done2

done2

aop1_2

rop3_2

done1_2

RM2

done2_2

startdoneM2

rop3_2

done4
rop5

EM5

RM3

done5

start
done

end

EM6
done6

start
doneA1

EM6
done6

aop6
done6

A1

rop6

END

end

END

rop5

end

RM3

done5
rop6

done4

done5

aop5

done5

aop4

aop5

M2

aop4

done4

rop4

EM5

done

rop4EM4

done3_2

done4

start

done3_2

aop3_2EM4

RM2

aop3_2

done1

rop2_2

done1

aop3_1

aop2

EM2

rop1_2

done2

M1

rop2

done3_1

aop2_2

done

done3

aop3_1

done3

start

done3_1

rop3_1

EM3

RM1

図 8 割り当てを限定した場合の制御回路の構成

aop6
done6

ていなければ実行開始信号 aop1 1 は 0 になるので, RM2 への実行要求信号 (rop1 2) が 1 になる. 演算器 M2 が空いていれ

図 6 本稿の制御回路の構成ば実行開始信号 aop1 2 が 1 になり実行を開始する. 実行開始
信号 aop1 1 か aop1 2 のどちらか一方が 1 になれば, EM1 へ

3. 分散制御における動的演算バインディング
3. 1 動的な演算バインディングの実行開始信号 (aop1) は 1 になる. また, 完了信号 done1 1
か done1 2 のどちらか一方が 1 になれば, EM1 への完了信号(done1) は 1 になる. EM2〜EM6 も同様である.

本稿では, 演算の実行順序だけでなく, 演算を行う演算器も動本制御手法によるデータパスの構成を図 7 に示す. (a) は的に決定する分散制御方式を提案する. 本手法では, 各演算をPilato の方式 (図 5) のデータパス部分であり, (b) は本稿の方単一の演算器ではなく演算器の集合にバインディングし, 実行式 (図 6) のデータパス部分である. Pilato の方式では, 演算 f1,時の状況に応じて演算器を選択できるようにする.
図 1 の例に提案手法を適用し, 演算 f3 を乗算器 M1, M2 のf3 が乗算器 M1 で, 演算 f2 が乗算器 M2 で実行されるため, レジスタから M1 への入力は 4 つ, レジスタから M2 への入力はどちらでも実行できるように制御した場合, 可変スケジューリ2 つである. 本稿の方式では, 演算 f1, f2, f3 が両方の乗算器でングによる制御例 (図 2(a)) と同様に, 演算 f3 が乗算器 M2 で実行可能なため, M1, M2 共にレジスタからの入力が６つにな実行でき, 合計 4 サイクルで実行を完了することができる.

り, 結線やマルチプレクサが増加する.

3. 2 制御回路の構成
動的演算バインディングの制御回路は Pilato の分散制御方式の RM を複数連結することにより実現できる.

3. 3 演算器割り当ての限定
1 つの演算を多くの演算器で実行できるようにすると, 制御回路およびデータパスの規模と遅延が著しく増加する可能性が

図 5 の制御回路を動的演算バインディングに拡張した構成例ある. これは, 各演算を実行可能な演算器集合を限定することを図 6 に示す. ここでは, 乗算 f1, f2, f3 はいずれも乗算器 M1,により, ある程度防ぐことができる. 例えば, 図 6 および図 7(b)M2 の両方で実行可能であるとする. EM1〜EM6 は Pilato のの回路構成では, 演算 f1, f2, f3 全てを乗算器 M1 と M2 のどち方式と同じである. また, RM1, RM2, RM3 は乗算器 M1, M2,らでも実行可能としていたが, f1 は M1 で, f2 は M2 で, f3 の加算器 A1 に対応するものであり, 機能的には Pilato の方式とみ M1 と M2 の両方で実行可能とすれば, 図 8 および図 7(c) の同じである. 本制御方式が Pilato の制御方式と異なる点は, f1

ように, 実行サイクル数を増やすことなく制御回路およびデーが M1 と M2 の両方で実行可能であるため, EM1 から RM1 とタパスを簡単化できる.

RM2 両方への接続があることである. まず, EM1 から RM1への実行要求信号 (rop1 1) が 1 になり, 演算器 M1 が空いてこの例の場合には実行サイクル数は変化しないが, 一般には性能と回路規模のトレードオフになると考えられる.

いれば実行開始信号 aop1 1 を 1 にして実行を開始する. 空い—4—

x1

y1
aM1

y3
cx3f1, f3

M2x2

f2

y2
bzy1
ax1x3

M1 f1, f2,

A1 f4, f5,y3cx2

M2 f1, f2,f3

f6(a) Pilato の方式

y2bzx1

M1

A1 f4, f5,f3y1
af6(b) 動的演算バインディングx3f1, f3y3
cM2x2f2, f3y2bz

A1 f4, f5,f6(c) 割り当てを限定した動的演算バインディング

図 7 データパスの構成
表1

実験結果

(a) 2 次元正方行列の積 (乗算器 3 個, 加算器 2 個)
平均サイクル数

LUT 数

遅延 (ns)

Pilato [4]8.01(100.0%)5252(100.0%)

21.39(100.0%)

提案手法

7.24(90.4%)5912(112.6%)

29.49(137.9%)

提案手法 (限定)7.45(93.0%)5359(102.0%)

24.99(116.8%)(b) 8 個の乗算のツリー状加算 (乗算器 3 個, 加算器 2 個)
平均サイクル数

LUT 数

遅延 (ns)

Pilato [4]10.03(100.0%)5525(100.0%)

21.39(100.0%)

提案手法

9.26(92.3%)

6398(115.8%)28.06(131.2%)

提案手法 (限定)

9.39(93.6%)5996(108.5%)

26.59(124.3%)(c) 16 個の乗算のツリー状加算 (乗算器 3 個, 加算器 3 個)
平均サイクル数

LUT 数

遅延 (ns)

Pilato [4]16.92(100.0%)6577(100.0%)

25.31(100.0%)

提案手法

15.58(92.1%)

8291(126.1%)

33.10(130.8%)

提案手法 (限定)15.71(92.8%)7018(106.7%)

29.92(118.2%)

4. 実 験 結 果

5. む す び

Pilato の分散制御手法と本稿で提案する制御手法について, 平

本稿では, Pilato の分散制御方式を拡張することにより, 演

均サイクル数, 回路規模, 遅延を評価する実験を行なった. デー

算を行う演算器を動的に決定できる分散制御方式を提案した.

タフローグラフは, (a) 2 次元正方行列の積, (b) 8 個の乗算のシミュレータを用いて各手法の平均サイクル数を計測する実験

ツリー状加算, (c) 16 個の乗算のツリー状加算である. 加算はを行なった結果, 平均サイクル数を 6〜10%削減することがで1 サイクル, 乗算は 1〜3 サイクルで完了するものとし, (a) ときた.

(b) は乗算器 3 個と加算器 2 個, (c) は乗算器 3 個と加算器 2 個制御回路の構成法にはまだ改良の余地があるので, この点がを使用可能とした. 平均サイクル数の評価は, 乗算を 1 サイク今後の課題として挙げられる. また, 演算の演算器への割り当てルで完了する確率が 50%, 3 サイクルで完了する確率が 50%と方法によって, 実行サイクル数, 回路規模, 遅延が変化するので,してランダムに決定し, シミュレーションを 10000 回行なって効率的な割り当てを求めることも重要な課題であると考える.

平均を算出した. 回路規模 (LUT 数) と遅延は, Verilog HDL謝辞で実装した回路を Xilinx Spartan3E をターゲットとして ISE

本研究を行う上で多くのご助言, ご協力頂いた京都高度技術(Version 13.1) で論理合成することにより求めた. 結果を表 1研究所の神原弘之氏, 元立命館大学の中谷嵩之氏, 元京都大学のに示す. 「提案手法」は, 全ての演算を, 使用可能な演算器全矢野正治氏に感謝します. また, 本研究に関してご協力, ご討議ての集合に割り当てたものである. 「提案手法 (限定)」は, 演頂いた田村真平氏をはじめ, 関西学院大学石浦研究室の諸氏に算器の割り当てを限定したものであり, 使用可能数よりも 1 つ感謝します.

少ない演算器のみで従来のバインディングを行い, 各演算をバインディング結果の演算器とバインディングに使わなかった演算器に割り当てた. 平均サイクル数は, 提案手法では Pilato に比べて 8%〜10%減小し, 演算器の割り当てを限定した場合でも 6%〜7%減少した. LUT 数は, 提案手法では割り当てを限定しないと 12%〜26%増加するが, 割り当てを限定すると 2%〜9%の増加に抑えられた. 遅延は, 提案手法で 31%〜38%, 提案手法 (限定) で 17%〜24%増加した.

文献[1] Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, and Steve
Y-L Lin: High-Level Synthesis: Introduction to Chip andSystem Design, Kluwer Academic Publishers (1992).
[2] Yuki Toda, Nagisa Ishiura, and Kousuke Sone: “Staticscheduling of dynamic execution for high-level synthesis,”in Proc. SASIMI 2009, pp. 107–112 (March 2009).
[3] 曽根康介, 石浦菜岐佐: ”高位合成における可変スケジューリングの近似手法,” 電子情報通信学会技術研究報告, VLD2010-90,(Jan. 2011).

—5—

[4] Alberto A. Del Barrio, Seda Ogrenci Memik, Marı́a C.
Molina, José M. Mendı́as, and Román Hermida: “Usingspeculative functional units in high level synthesis,” in Proc.
DATE 2010, pp. 1779–1784 (March 2010).
[5] Christian Pilato, Vito Giovanni Castellana, Silvia Lovergine,and Fabrizio Ferrandi: “A Runtime Adaptive Controller for
Supporting Hardware Components with Variable Latency,”
in Proc. 2011 NASAIESA Conf. on Adaptive Hardware andSystems (AHS-2011), pp. 153–160 (June 2011).

—6—