ABSTRACT

CCS CONCEPTS

KEYWORDS

INTRODUCTION
1
With recent progress in the integrated circuit technology, the scale and the complexity of the hardware implemented in a chip are growing rapidly. While such systems need enormous design efforts, there is a strong demand to reduce time to market. High-level synthesis is one of the promising means to prototype hardware *Currently with Japan System Techniques Co., Ltd. (JAST), Osaka, Japan design from existing software assets on which many researches have been conducted [1]. In conventional high-level synthesis methods, operations are scheduled assuming that functional units take the same number of clock cycles for the same operations. The scheduling is determined statically and does not change during run time. However, in ac- tual datapaths, some functional units exhibit different latencies for the same operation depending on operands or their environment. Although the traditional scheduling is still valid if the maximum latencies are assumed for such units, wasteful waits occur when the units take less latencies than those of the worst case. One way to solve this problem is to adjust operation scheduling dynamically [2]. However, the conventional datapath control using a single state machine ends up with impractical circuit size because an enormous amount of states are necessary to express all the com- bination of delay variations of the functional units. As a promising alternative, distributed control has been recently proposed [3, 4] which controls a datapath with multiple finite state machines. Different schemes for distributed controllers have been proposed by Del Barrio [3] and Pilato [4]. All these methods, however, deal with a case where computation is expressed with a single DFG. This may be appropriate for accelerating kernels in DSP applications, but not for prototyping control centric systems. In order to apply the distributed control to larger systems, an extension of the Del Barrio's distributed control to handle multiple DFGs was proposed in [5]. Rather than simply patchworking the state transition graphs for the DFGs, it enabled dynamic operation motion across multiple DFGs, which realized efficient execution like loop scheduling and trace scheduling. However, the effect of dynamic code motion was limited when branch conditions were computed at the end of the DFGs, for early units must idle-wait until the branch target was fixed. To address this issue, we extend the method of [5] with specu- lative execution based on branch prediction. By this method, the idle units may compute operations in predicted next DFGs even if branch targets have not been fixed. Experimental results on two examples shows that the execution cycles were reduced by 11.1% to 21.9% when the prediction hit rate was 75%. RSP’17, October 15-20, 2017, Seoul, Republic of Korea
VARIABLE LATENCY UNITS AND
2
DISTRIBUTED CONTROL
2.1
Variable latency units
Functional units in datapaths may exhibit different latencies for the same operation, depending on operand values, states of the units, and environment factors. For example, shift/add-based multipliers and dividers can omit part of the computation when some part of multiplicand or intermediate remainder becomes zero. Memory accesses may take different cycles depending on address histories. Let us consider executing a DFG in Figure 1 (a) with an adder A which takes 1 cycle and a multiplier M which takes either 1 or 2 cycles. In the conventional high-level synthesis, the operations are scheduled as (b) assuming operations 2 and 4 may take 2 cy- cles. Even when operation 2 completes in 1 cycle, scheduling is unchanged as shown in (c), where the second cycle is wasteful. Toda [2] proposed dynamic scheduling based on the completion signals from functional units which enables scheduling as shown in Figure 1 (d). However, the controller for this dynamic scheduling needed huge amount of states, so the resulting circuit might be impractically large.
Distributed control
2.2
As an approach to realizing dynamic scheduling with reasonable cir- cuit size, distributed control has recently been proposed which con- trols functional units using multiple finite state machines (FSMs). In the Del Barrio's method [3], an FSM is assigned to each func- tion unit in a datapath. The function unit to execute each operation is determined beforehand. The order of the operations executed by each unit is also fixed and the controller dynamically decides the timing to execute the operations. The Pilato's method [4] controls the datapath by assigning a state variable to each operation. As Del Barrio's method, the function unit to execute each operation is determined beforehand but the order as well as the timing of execution of the operations is determined dynamically. However, these methods only discusses the case where compu- tation is expressed by a single DFG. They have not addressed the issue of handling a CDFG consisting of multiple DFGs, which is essential in synthesizing hardware from specification expressed in programming languages like C.
2.3
Del Barrio’s distributed control
In the conventional control method, a whole datapath is controlled by a single FSM (finite state machine), as shown in Figure 2 (a). On the other hand, in Del Barrio's distributed control, separate FSM A and FSM M control function units A and M , respectively, as in (b). This allows each unit to choose execution timing independently. Figure 2 (c) is the details of the FSMs in (b). The formulation in this paper is slightly different from the original one in [3], but essentially the same. One state S i is assigned to an operation i in the DFG, in which S i controls the execution of i. At S i , the FSM waits for start i = 1 where start i becomes 1 if all the operations on which i depends are finished. In the case of Figure 2, start1 = 1, start2 = 1, start3 = (s2 ∧ endM) V Done2, starts = (s 3 A end A ) V Done3, where s i means that the FSM is in state S i , and end u is the comple- tion signal from unit u. Done i stands for completion of operation i, whose initial value is 0 and is updated as follows. if s 1 ∧ end A then Done 1 = 1, if s2 ∧ end M then Done2 = 1, if s 3 ∧ end A then Done 3 = 1, if s 4 ∧ end M then Done 4 = 1. When state is S i and start i = 1, FSM u sets the enable signal en u of unit u. enA = ((s1 A start1) V (s3 A start3)) A ExeA, enM = ((s2 A start2) V (s4 A start4)) A ExeM where Exe u means that unit u is in operation, which is defined as follows. if en A then Exe A = 1 else if end A then Exe A = 0, if en M then Exe M = 1 else if end M then Exe M = 0. Del Barrio's method in [3] covers a loop with a single DFG, where operations in the next iteration may be executed without waiting for the completion of a certain iteration. However, it does not handle a CDFG consisting of multiple DFGs; it does not cover conditional jumps, for example. Speculative Execution in Distributed Controllers for High-Level Synthesis
2.4
Distributed control beyond the borders of
dataflow graphs
Shimizu [5] proposed an extension of the Del Barrio's distributed control to handle multiple DFGs, where dynamic motion of opera- tions across multiple DFGs was achieved. In the case of the centralized FSM, the control is transferred to one of the next DFGs after all the operations in the current DFG are finished. However, in the presence of variable latency operations, not all the units finish their task in an DFG simultaneously, so some of them must wait for each other at the end of the DFG. To overcome this inefficiency, the method of [5] enabled operations in the next DFG to start execution before concluding the current DFG. For example, in Figure 3 (a), where two units are controlled by two controllers, the operations corresponding to S0 and S3 are finished, then the control of the second FSM can be transferred from S3 to S11, without waiting for the completion of S1, if DFG3 is known to be the next DFG of DFG1. In [5] the extension of the distributed control was formulated under the restriction that only one DFG ahead of the current DFG may be executed, i.e. at most two DFGs may be executed at the same time. A self loop is eliminated by duplicating the DFG, as shown in Figure 3 (b).
SPECULATIVE EXECUTION IN
3
DISTRIBUTED CONTROL
Overview
3.1
In the control method in [5], however, dynamic scheduling across DFGs works only when the next DFG is fixed. Suppose S1 in DFG1 in Figure 4 (a) determines the target of the conditional branch. Although the second (right) unit has finished the computation at S3, it cannot proceed to the next state until S1 decides the next DFG. Since it is often the case that conditional operations to decide branch directions are computed at the very end of the DFGs, conservative synchronization limits the effect of dynamic scheduling. To address issue, we propose to extend the distributed control of [5] with speculative execution. At the situation where next DFG to be executed is not known, one of them is chosen based on branch prediction. As shown in Figure 4 (b), the second unit proceed from S3 to S11 without waiting for the completion of S1, if the branch from DFG1 to DFG3 is predicted. If the prediction hits, there may be reduction in execution cycles. If the prediction misses, the inter- mediate results of the speculative execution are cancelled and the state is forced to the head of the correct DFG, as shown in Figure 4 (c). This causes no loss in execution cycles on prediction misses, and we have a chance of speeding-up circuits on prediction hits. To avoid complication, we place the same restriction as in [5] that only one DFG ahead of the current DFG may be executed. We call a DFG a main DFG if some FSMs are executing operations in the DFG and the other FSMs have completed execution for the DFG. We call a DFG a frontier DFG if it is a successor DFG of the main DFG and operations in the DFG are being executed. In Figure 4 (b), DFG1 is a main DFG and DFG3 is a frontier DFG. The frontier DFG does not always exist; there is no frontier DFG in Figure 4 (a). Cancellation of execution is done based on a register save/restore policy. Just before speculative execution starts, the contents of the registers that may be written during speculative execution are copied to the save registers. In the case of prediction misses, the saved values are written back to the registers when the FSMs transition to the right states.
Formulation
3.2
The formulation of the distributed control method in this section is basically based on that of [5], but it is refined partly to make it RSP’17, October 15-20, 2017, Seoul, Republic of Korea easier to incorporate speculative execution, and partly to enhance readability. Let U be the set of units in the datapath. e u is the completion signal of u ∈ U at the current cycle. In our scheme, each u ∈ U is controlled by an FSM, denoted as F u , where each state of F u controls the execution of an operation. Let σ μ be the current state of F μ . Let D be the set of DFGs in the CDFG. Let S u,d = {su,d ,su,d ,... be the set of the states for u in DFG d, where σ u transitions s q ,d through s ψ , d  in this order. Namely, s ψ , d  and s ψ , d  are the initial and the final states in the DFG d for unit u . For design convenience, we assume that S u d ≠ φ . If there is no operation for u in DFG d , we insert a dummy state. 3.2.1  End and ready signals. For d ∈ D and s ∈ Su d, r(s), e(s), E(s), and e(d) are defined as follows. Intuitively, r(s) means that the operation at s is ready for execution. e (s) means that the execution of the operation at s ends at the current cycle, E(s) means that the execution of the operation at s has been completed before the current cycle, and e(d) means that execution of all the operations in DFG d finishes at the current cycle. Let P s be the set of the states (operations) that (the operation of) s depends on. E 0 (s) and E ′ (s) are the initial value and the next value (the value at the next cycle) of E(s), respectively; E(s) is set when e(s) = 1 and reset at the end of the DFG execution.
The operation of s starts execution when (σ μ = s) ∧ r(s). 3.2.2 State transition. When σ u = s i ,d , where 0 ≤ i < f , the next state σ ν within a DFG d is defined as follows.
State transition across DFGs is a little complicated. The state machine F u can transition from the last state of DFG d to the first state of a next DFG d 1 if and only if the two conditions are met. (1) Transition from d to d 1 is fixed. (2) d 1 is executed either as a main DFG or as a frontier DFG in the next cycle. The first condition is formulated using δ(d,d 1 ) and Δ(d,d 1 ) for two DFGs d and d 1 . δ(d,d 1 ) means that transition from d to d 1 is triggered at the current cycle, and Δ( d,d 1 ) mean that transition from d to d 1 has been fixed before the current cycle. If d 1 is the unique successor to d , then δ(d,d,) = 1 and Δ(d,d,) = 1. Other- wise, δ(d,d 1 ) and Δ(d,d 1 ) are defined as follows, assuming that the transition from d to d 1 is determined by the output o μ of unit u at state sc ∈ Su,d. Δ0(d,d1) and Δ′ (d,d1) are the initial and the next values of Δ(d,d 1 ), respectively; Δ(d,d 1 ) is set when δ(d,d 1 ) = 1
DFG in the current cycle, and m ( d ) that d will be executed as a main DFG in the next cycle. M 0 ( d ) and M ′ ( d ) are the initial and the next values of M(d).
Let DFGs d 1 ,d 2 , · · · ,d k be successors of DFG d . They may be executed as a main or a frontier DFG in the next cycle if M(d)Vm(d). Thus, when σ u = s u ,d , the next state σ u is written as follows.
Inter-DFG dependency. For inter-DFG dependency, such 3.2.3 as s 1 → s 2 in Figure 5 (a), the end signals E (s) do not work well. For example, in Figure 5 (a), if s 2 waits for E (s 1 ) signal which will be reset as soon as DFG1 finishes, s 2 can never start execution. If reset of E(s 1 ) is postponed until the end of s 2 , then s 3 in the next iteration starts without waiting for the completion of s1 in the next iteration. To solve this problem, we introduce E(s 1 ,s 2 ) for every inter-DFG dependency from s 1 to s 2 . It is set when s 1 is finished and reset when $2 is reset. Speculative Execution in Distributed Controllers for High-Level Synthesis RSP’17, October 15-20, 2017, Seoul, Republic of Korea Note that s 1 and s 2 in E(s 1 ,s 2 ) are not always executed. For example, in Figure 5 (b), suppose branch from DFG d 1 to DFG d 4 is taken. If s 8 would waits for E(s 5 ,s 8 ), s 8 could never start execution, because s5 is not executed and E(s5,s8) will never be set. Moreover, E(s 1 ,s 4 ) would not reset in this iteration. Then if branch from d 1 to d 2 might be taken in the next iteration, s 4 would start execution without waiting for the completion of s 1 . This kind of confusion is resolved by setting/resetting the end signal E(s1,s2) when directions of branches are determined. ● If it is known that the DFG of s 1 will never be executed in the current iteration, then E(s 1 ,s 2 ) is set. ● If it is known that the DFG of s 2 will never be executed in the current iteration, then E(s 1 ,s 2 ) is reset. ● If it is known that both the DFGs of s1 and of s2 will never be executed in the current iteration, then the initial value is set to E($1,$2). For example, in Figure 5 (b), branch from d 1 to d 4 is determined when Δ(d 1 ,d 4 ) V δ(d 1 ,d 4 ) becomes true, and at this point, it is also determined that d 2 and d 3 will not be executed in this iteration. Thus, E(s 1 , s 4 ) = 0, E(s 3 , s 6 ) = 0, and E(s 5 , s 8 ) = 1 are enforced. The initial and next values of E(s1,s2), denoted as E0(s1,s2) and E ′ ( s 1 , s 2 ), respectively, are defined as follows, where γ ( σ 1 ) and γ ( σ 2 ) are the conditions in which s 1 and s 2 , respectively, will not be executed in the current iteration.
With the extended end signals, equation (1) defining ready signal r(s) is revised as follows, where Ps is the set of the states that s depends on in the same DFG as s , and X s is the set of the states that s depends on in the other DFGs.
3.2.4 Speculative execution. We assume B(d,d,) denotes that branch from d to d 1 is predicted. The prediction may be either static or dynamic. Branch prediction changes the state transition in the following way: 1) it allows transition to the state in the predicted DFG, and 2) it forces the transition to the correct states. This is incorporated into the formulation by revising the equations (6) and (13). Let d 1 ,d 2 , · · · ,d k be successor DFGs of DFG d and let branch from d to d 1 be predicted (namely, B(d,d 1 ) = 1 is assumed). Then state transition is modified as follows. ● State transition from the last state of d State transition regarding branch prediction occurs only when none of the other branches occur. Thus we only have to correct the last else clause of equation (13).
● State transition within d 1 Equation (6) must be corrected so that branch prediction misses are handled.
As for the register values, save must be done when B(d,d1) holds in equation (17), restore must be done when either of δ(d,d 2 ) V △(d,d2) through δ(d,dk) V Δ(d,dk) holds in (18). At the same time as the register restore, the end signals for inter-DFG dependency must be adjusted according to the equation (15).
EXPERIMENTAL RESULTS

4
RTL circuits have been designed in Verilog HDL for two benchmark circuits, in order to compare centralized control, distributed control without speculative execution [5], and proposed distributed control with speculative execution. In this experiment, we assume that mul- tiplication takes 1 or 2 cycles depending on operands, and all the other operations take 1 cycle. We assume static branch prediction both in centralized and distributed control. In the both benchmarks, conditional operations to decide the branch directions can be sched- uled only in the last steps of the DFGs. (1) bicubic: The CDFG in Figure 6 (a) is executed with two ALUs (A1 and A2) and two multipliers (M1 and M2). Figure 6 (b) is an example of binding and scheduling for distributed control (deter- mined manually). DFG0 is duplicated to remove the self loop. d0, d0c, d 1, and d 2 are dummy states. Figure 6 (c) is a result of loop and trace scheduling for centralized scheduling. (2) m-lerp: The CDFG in Figure 7 (a) is executed with a compara- tor (EQ), two ALUs (A1 and A2), and two multipliers (M1 and M2). The binding and scheduling examples for distributed and central- ized control are shown in Figure 7 (b) and (c), respectively. TABLE 1 (a) summarizes the comparison of the execution cycles for the three control schemes. The computation shown in CDFGs in Figure 6 (b) and Figure 7 (b) were iterated for 128 times. r is the probability where the multiplication takes two cycles; r = 1.0 means all the multiplications took 2 cycles, while r = 0.0 means all the multications took 1 cycle.
multiplication 1 ～ 2 cycles,   r : probability of 2 cycle multiplication SE: distributed control with speculative execution (proposed)
Column "pred. hit rate" shows the hit rate of branch prediction (the input data were generated randomly). Column "CC" shows the results of the classical centralized control scheme, with the scheduling and biding in Figure 6 (c) and Figure 7 (c) where all the multiply operations were assumed to take 2 cycles. Columns "DC" and "SE" are both results of distributed control, where the former is without speculative execution [5] and the latter is with speculative execution (the proposed method). They both are based on the same scheduling and binding in Figure 6 (b) and Figure 7 (b) Comparison between DC and SE shows that the proposed method needed fewer execution cycles than the previous method. Naturally, the reduction rate is higher when the prediction hit rate is higher and r is lower. When the prediction hit rate was 75%, the execution cycles were reduced by 11.1% to 21.9%. As compared with CC, the proposed method took little more cycles when r = 1.0. This is because of the limitation of our method that only 2 DFGs can be executed simultaneously. However, when r is smaller, the execu- tion cycles were reduced significantly due to the effect of dynamic scheduling. TABLE 1 (b) summarizes the result of logic synthesis. The logic synthesizer was Xilinx Vivado (2016.4) and the target was Artix-7 (xc7a100tcsg324-3). Subcolumns "FFs," "LUTs,", and "delay," show the number of the flip-flops, the number of the look-up tables, and the critical path delay of each circuit. Introduction of speculative execution increases circuit size in terms of LUT count by 3.3% on average, though the LUT count is as much as 2 times larger than that of the centralized control. However, the critical path delay is almost the same. The critical path delay is increased by speculative execution by 4.6% on average, but it is only 2.4% larger than that of the centralized control. The cancellation of speculative execution based on the formu- lation in 3.2.4 worked only for the two benchmarks with manual design. However, in order to handle more general cases, especially with complicated inter-DFG dependency, we might add some limi- tations or further refine the formulation.
5
CONCLUSION
This paper has proposed a method of introducing speculative exe- cution in the distributed control beyond the border of DFGs. This contributes to enhance speed performance by increasing the oppor- tunity of dynamic operation motion across DFGs. Currently, the circuits are designed by hand as well as the sched- uling and biding are determined manually. We are now working on a scheduling and biding method suitable for our distributed control and automatic circuit generation framework.
ACKNOWLEDGMENTS
Authors would like to express their appreciation to Dr. Hiroyuki Kanbara of ASTEM/RI, Prof. Hiroyuki Tomiyama of Ritsumeikan University, and Mr. Takayuki Nakatani (formerly with Ritsumeikan University) for their valuable comments. We would also like to thank to the members of Ishiura Lab. of Kwansei Gakuin University for their cooperation and discussion. This work is partly supported by JSPS KAKENHI under Grant No. 16K00088.
REFERENCES
[1] Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, and Steve Y-L Lin. 1992. High-Level Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers. [2] Yuki Toda, Nagisa Ishiura, and Kousuke Sone. 2009. Static scheduling of dynamic execution for high-level synthesis. In Proceedings of the Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2009). (March 2009), 107–112. [3] Alberto A. Del Barrio, Seda Ogrenci Memik, Maria C. Molina, José M. Mendias, and Román Hermida. 2011. A distributed controller for managing specula- tive functional units in high-level synthesis. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems. 30, 3 (March 2011), 350–363. DOI:http://doi.org/10.1109/TCAD.2010.2089565 [4] Christian Pilato, Vito Giovanni Castellana, Silvia Lovergine, and Fabrizio Fer- randi. 2011. A runtime adaptive controller for supporting hardware com- ponents with variable latency. In Proceedings of 2011 NASA/ESA Confer- ence on Adaptive Hardware and Systems (AHS 2011). (June 2011), 153–160. DOI:http://doi.org/10.1109/AHS.2011.5963930 [5] Miho Shimizu and Nagisa Ishiura. 2016. Extending Distributed Control for High- Level Synthesis beyond Borders of Basic Blocks. In Proceedings of the Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2016). (October 2016), 172–177. Speculative Execution in Distributed Controllers for High-Level Synthesis RSP’17, October 15-20, 2017, Seoul, Republic of Korea