R4-5

SASIMI 2016 Proceedings

Introducing Real Constraints in Partitioned ILP-Based Binding
in High-Level Synthesis
Nagisa Ishiura and Yuuki Oosako
School of Science and Technology, Kwansei Gakuin University, Sanda, Hyogo, Japan

Abstract— This paper presents an eﬃcient ILP
based method of binding in high-level synthesis. The
binding problem can be broken into subproblems
based on partitioning of the set of control steps. To
incorporate a global view in solving each subproblem
by ILP, constraints for other unsolved subproblems
without integer restrictions are added. Experiments
on some designs shows that this produces better solutions within less computation time.

I. Introduction
High-level synthesis [1] now plays an indispensable role
in VLSI design. Among the primary tasks in high-level
synthesis, binding, which assigns operations and values ina CDFG (control dataﬂow graph) to functional units andregisters in a datapath, is the most CPU intensive andhas the largest impact on the quality of the synthesizedcircuits in terms of the size and the critical path delay.
While graph or ﬂow based polynomial time algorithms[2, 3] are typically employed to ﬁnd reasonable binding
solutions within practical time, ILP (integer linear programming) is also used to get high-quality solutions forsmall to medium designs [4, 5]. Although ILP formulation is also convenient in incorporating various new factors
into binding, computation time for large models often getsprohibitive. To curve the CPU time, the models may bepartitioned into smaller models and solved piece by piece,
but this drops the quality of solutions, for optimization isattempted based only on local information.
To address this issue, this paper proposes to incorporate
constraints of other subproblems without integer restriction into those of a subproblem in focus. Experiments onsome designs yielded better solutions within less computation time than the simple partitioning method.
II. ILP formulation of Binding
Given a scheduled CDFG, we try to ﬁnd an assignmentof operations and values to functional units and registers
which minimizes the total cost of functional units andmultiplexers. As formulated in [6], we force all the paths
including false paths (produced by chaining) not to exceed
the clock period. In case we encounter a contradiction, weresolve it by allocating extra functional units (as in [5])instead of altering the scheduling (as in [6]).
Let F and R be the sets of the available functional
units and the registers in the datapath, respectively. Let
U = F ∪ R. We call u ∈ U a unit. Let Wu and Tu bethe sets of the output terminals and the input terminals
of unit u. Let W and T be the sets of all the output
terminals and all the input terminals, respectively. Fort ∈ W ∪ T , let ut denote the unit that t belongs to. Letdu ∈ Z + and cu ∈ Z + be the delay and the cost of unitu, respectively. Let pmax be the maximum permissible
critical path delay of the datapath. Let the cost of thek-input multiplexer be (k − 1) · cmux . Let O and V be thesets of the operations and the values of a given scheduled
DFG, respectively, and let N = O ∪ V . We call n ∈ N anode. Let Pn and Qn be the sets of the output ports andthe input ports of node n. Let P and Q be the sets ofall the output ports and all the input ports, respectively.
For p ∈ P ∪ Q, let np denote the node that p belongs to.
E ⊆ P × Q represents the data dependency of the DFG.
Let S be the set of the steps. For n ∈ N , Un be the set ofthe units which can execute n, and sn be the step where
n is executed. Let tp,u be the terminal corresponding toport p when the node that p belongs to is bound to unit
u. Let Ns,u = {n ∈ N | sn = s, u ∈ Un }.
The base variables for our ILP formulation is:• xn,u (n ∈ N , u ∈ U ): 0-1 variable where xn,u = 1 iﬀ
node n is bound to unit u.
In addition, the following auxiliary variables are used:• cw,t (w ∈ W , t ∈ T ): 0-1 variable where cw,t = 1 iﬀ
there is a connection from w to t.
• mt (t ∈ T ): integer variable representing the multiplexer cost on t.
• uu (u ∈ U ): 0-1 variable where uu = 1 iﬀ unit u isused.
• pu (u ∈ U ): integer variable representing the maximum path delay from registers to the outputs of u.
We have the following six constraints.
1. Each node is bound to a unit:xn,u = 1∀n ∈ N :u∈Un

2. Each unit is used at most once during a step:
xn,u ≤ 1∀s ∈ S ∀u ∈ U :u∈Ns,u3. For each data dependency, there is a corresponding
connection:∀(p, q) ∈ E ∀u ∈ Unp ∀v ∈ Unq :xnp ,u + xnq ,v − 1 ≤ ctu,p ,tq,v .
4. Multiplexer cost:cw,t − 1.
∀t ∈ T : mt =w∈W

5. Path delay:(a) ∀u ∈ R : pu = 0.
(b) ∀(w, t) ∈ (W × T ) : puw + (dut − D) ≤ put ,where D is a constant greater than pmax .
(c) ∀u ∈ F : pu ≤ pmax .

- 303 -

The objective in our formulation is to minimize the sumof the costs of the used units and the multiplexers.

c u uu +cmux mt .
Minimizeu∈U

TABLE I
Experiments on small scale examples.

t∈TIII.

Partitioned and Partially Real
Constrained Approach
When the ILP model for binding is too large to solve, it
may be partitioned. One simple way is to determine thebinding for k steps at a time. To lessen the degradation ofsolution quality, this paper proposes to incorporate constraints regarding other steps without integer restriction,
into those of the steps that are being solved.
At each iteration, we partition the set of steps S into
four disjoint sets SS , SI , SR , and SN . SS is the set ofthe already solved steps and SI is the set of the steps
to be solved at the current iteration. SR is the set ofthe steps in which constraints are relaxed. All the constraints regarding SN are ignored in the current iteration.
In the initial iteration, SS is empty and binding for SI issearched using the integer constraints of SI and the realconstraints of SR . Then, in the next iteration, SS is set
to SS ∪ SI and new SI and SR is chosen. It is preferable
to set SR = S − (SS ∪ SI ), but SR are chosen so that thesubproblem is solved within feasible time.
In this formulation, all the auxiliary variables cw,t , mt ,uu , pu are now real variables. xn,u are handled as follows:• xn,u where n ∈ SS is replaced by its solution.
• xn,u where n ∈ SI is unchanged.
• xn,u where n ∈ SR is a real variable (0 ≤ xn,u ≤ 1).
• All the constraints 1–3 regarding xn,u where n ∈ SSare removed.
IV. Experimental results
A binding program based on the proposed method has
been implemented. CPLEX 12.6.1.0 is used as an ILPsolver. The main program itself is written in Perl5, andILP models and results are passed via intermediate ﬁles.
Steps for SI and SR are simply chosen in the order ofappearance in given CDFG ﬁles.
TABLE I summarizes the result of the experiment on
three models. “ellip” has 75 nodes which are scheduled
into 17 steps where chaining up to three operations has
been performed. In the ﬁrst run, |SI | and |SR | are set to
1 and 0, respectively, which is equivalent to the bipartite
matching based method [2]. The cost is in terms of thetotal cost function in ILP where the costs of an ALU, amultiplier, an MUX, and a register are 32, 128, 32, and 32,respectively. The CPU time was on 1.7GHz Core i7 with
8GB memory for “ellip” and “s2m”, and 3.4GHz Corei7 with 16GB memory for “RSA.” By solving 5 steps ata time, the cost is reduced signiﬁcantly. However, ourmethod with |SI | = 1 and SR being the set of all theunsolved steps found better solution within less computation time. Similar result is obtained on the second model“s2m” with almost the same size. The third model is an
RSA codec whose CDFG is generated from a C programby a high-level synthesizer. Chaining is not performed.
Since the number of the nodes in a step varies largely,
we partitioned the step set by the number of nodes. s(n)is the minimum number of the next steps that include nellip

|N |
75|S|
17s2m8114RSA 5,417 854

|SI |
|SR |
1050
1
all
1060
70
1all
10s(30)0s(30) s(870)s(350)
0s(400)0cost
CPU [s]1,456
1.07 ∗
1,296
357.99 ∗1,264
20.68 ∗
1,264
0.59 ∗
1,168
1.89 ∗
1,136
5.98 ∗
1,136
3.27 ∗
12,032 2950.61 ∗∗9,728
206.05 ∗∗8,992 8271.24 ∗∗
9,408 8913.13 ∗∗9,248 7555.20 ∗∗N : set of nodes, S: set of steps
SI : set steps solved by ILP, SR : set steps solved by LPcost: ALU=32, multiplier=128, MUX=32(#in−1), register=32
all: all the unsolved steps (namely, SR = S ∪ SS ∪ SI and SN = φ)s(n): the minimum number of the next steps that include n nodes* 1.7GHz Core i7 (8GB memory), ** 3.4GHz Core i7 (16GB memory)nodes; when the next 3 and 4 steps have 25 and 35 nodes,
respectively, then s(30) = 3. By solving multiple steps
at a time, costs become signiﬁcantly less than the bipartite matching method1 , but the proposed method founda better solution with the same amount of CPU time.
Note that the result is highly dependent on the model,
due to the complex nature of the biding problem. There
were also cases where the normal partitioning methodwith SR = φ found better solution than our method.
V. Conclusion
This paper has presented a method of incorporating a
global view in partitioned ILP based binding. We are now
working on further experiments to reﬁne the method.
Acknowledgement
Authors would like to thank all the members of IshiuraLab. of Kwansei Gakuin University. This work was partly
supported by JSPS KAKENHI Grant Number 16K00088 .

References[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 (1992).
[2] C.-Y. Huang, Y.-S. Chen, Y.-L. Lin, and Y.-C. Hsu: “Datapath allocation based on bipartite weighted matching,” inProc. 27th DAC, pp. 499-504 (June 1990).
[3] J. Cong and J. Xu: “Simultaneous FU and register binding based on network ﬂow method,” in Proc. DATE 2008,
pp. 1057–1062 (Mar. 2008)[4] W.-T. Shiue and C. Chakrabarti: “ILP-based scheme forlow power scheduling and resource binding,” in Proc. ISCAS 2000, vol. 3, pp. 279–282 (May 2000).
[5] Y. Hara-Azumi and H. Tomiyama: “Clock-constrained simultaneous allocation and binding for multiplexer optimization in high-level synthesis,” in Proc. ASP-DAC 2012,
pp. 251–256 (Jan.–Feb. 2012).
[6] A. Kondratyev, L. Lavagno, M. Meyer, Y. Watanabe:“Share with care: A quantitative evaluation of sharing
approaches in high-level synthesis,” in Proc. DATE 2013,
pp. 1547–1552 (Mar. 2013).
1 The CPU time for |S | = 1 is unexpectedly large because ofI
many ﬁle I/Os for repetitive invocations the ILP solver. Proper
implementation will reduce it to far smaller time.

- 304 -