DS0 0/9/,.,,.,,,.,.,.0%,.%.,,,, Speculative Execution in Distributed Controllers for High-Level Synthesis Shimizu iho Ishiura Nagisa bstract: This article proposes a method of incorporating speculative execution into distributed control which enables dynamic scheduling of operations beyond the boundaries of basic blocks. In the presence of variable latency units, the static scheduling scheme in conventional high-level synthesis causes wasteful waits. Distributed control enables dynamic scheduling of operations, of which we previously proposed an extension to allow operation motion across two dataflow graphs. In this article, we further introduce speculative execution based on branch prediction into our previous scheme. Experimental results on two examples showed that the execution cycles were reduced by.% on average as compared with our previous method without speculative execution, while the circuit size was increased by.0%. Keywords: high-level synthesis, distributed controller, dynamic scheduling, branch prediction, speculative execution.,.,,., C Kwansei Gakuin University, - Gakuen, Sanda, Hyogo, 9, Japan [].,,,.,.,, c 0 Information Processing Society of Japan
DS0 0/9/ a b c d u t (a) (b) (c) (d) [].,., Del Barrio [], Pilato [], [].,,. [],.,.,,.,.,,.,, 0%,..,,, 0,.,.,. (variable-latency unit)., (a) ( DFG )., (b).,, (c) FS S0 S S S S S S FS FS S S S S (a) (b) Del Barrio DFG FS FS en S S en Del Barrio. [],, (d).,,.. Del Barrio Del Barrio [], (a),. DFG,,,.,. (a), FS. (b) Del Barrio., FS,, FS. Del Barrio., ready S., done, done S =. 0,, done 0,.,.,, ready S = S done S. Si i. running =., = (running = 0) (S ready S ) (S ready S )., c 0 Information Processing Society of Japan
DS0 0/9/ DFG S0 S S S DFG S0 S main S S,,. DFG S S DFG DFG S S9 S S S S S0 S S S DFG frontier S9 S S0 S (a) (b).,,. Del Barrio, Pilato,,,,. Del Barrio, DFG,., DFG,.., DFG [].,, DFG DFG, DFG.,, FS, (a), S0 S,, DFG DFG.,, DFG DFG S., DFG. [], DFG, DFG.,,,.,,.,, %., DFG..,,.,, DFG., DFG. DFG,,.,., DFG [],...., DFG, DFG. (b), DFG, DFG. U. u U o u, e u. DFG D. DFG d D u U FS F d,u, S d,u. F d,u f d,u. DFG d s S d,u, γ(s), Γ(s), ζ(d). Γ(s), s, γ(s), s, e(d), DFG d. σ d,u F d,u, Γ 0 (s) Γ (s), Γ(s). γ(s) = Γ(s) ((σ d,u = s) e u) e(d) = γ(f d,u ) u U Γ 0(s) = 0 Γ (s) = if e(d) then 0 else γ(s), e(d), u U, F d,u. (e, d) DFG e d, δ(e, d) DFG e c 0 Information Processing Society of Japan
DS0 0/9/ d. d e DFG, (e, d) = δ(e, d) =. e DFG, t u e d, δ(e, d) (e, d). ( 0 (e, d) (e, d), (s).) δ(e, d) = (e, d) ((σ e,d = t) e u o u) 0(e, d) = 0 (e, d) = if e(e) then 0 else δ(e, d) (d) DFG d. d DFG P d, (d) 0 (d) (d). 0(d) = if d DFG then else 0 (d) = if e(d) then 0 else (d) e P d (e(e) δ(e, d)) F(d) DFG d, F 0 (d) F (d). F 0(d) = 0 F (d) = if (d) then 0 else F(d).. e P d ( (e) δ(e, d)) [] DFG d (d) F(d).,, DFG e d B(e, d), DFG d P(d), DFG d (d) F(d) P(d). B(e, d),,. P(d) P 0 (d) P (d). P 0(d) = 0 P (d) = if (d) F (d) then 0 else P(d) e P d ( (e) B(e, d)) DFG d, DFG R., d r R t r, r u. r, t r r, t r. P(d) P (d) ( ) r = r t r = if e u then o u else t r P(d) P (d) ( ) r = if e u then o u else r t r = t r P(d) P (d) () r = if e u then o u else t r t r = t r. Verilog HDL, [].,,.,.. CDFG, DFG. () bicubic (a) DFG,,,. (b). (b),.,. (c),.,. () m-lerp (a) DFG,,, EQ (). (b), (c).... (c) (c) /,. r, r =.0, r = 0.0. %. [], r..%,,., r =.0. DFG, c 0 Information Processing Society of Japan 9
DS0 0/9/ ( ) ( ) [] ( ) r =.0 r = 0. r = 0.0 r =.0 r = 0. r = 0.0 bicubic 990 9 0 9 0 m-lerp 9 9 9 09 :, r:, : % () ( ) [] ( ) FFs LUTs delay [ns] FFs LUTs delay [ns] FFs LUTs delay [ns] bicubic 0. 9. 9.0 m-lerp 9.9 99..0.,. r = 0., r = 0.0,,... Xilinx ISE (.), FPG (Spartan E). []., FFs, LUTs, delay. FFs.%, LUTs.%, [] FFs 0.9%, LUTs.0%,.., DFG, DFG, DFG., [].0%.%., /.,,,,.,,., JSPS K000. [] Daniel D. Gajski, Nikil D. Dutt, llen C-H Wu, and Steve Y-L Lin: High-Level Synthesis: Introduction to Chip and System Design, Kluwer cademic Publishers (99). [] Yuki Toda, Nagisa Ishiura, and Kousuke Sone: Static scheduling of dynamic execution for high-level synthesis, in Proc. SSII 009, pp. 0 (ar. 009). [] lberto. Del Barrio, Seda Ogrenci emik, aría C. olina, José. ías, and Román Hermida: Distributed Controller for anaging Speculative Functional Units in High-Level Synthesis, in Proc. (DTE 0), pp. 0 (ar. 0). [] Christian Pilato, Vito Giovanni Castellana, Silvia Lovergine, and Fabrizio Ferrandi: runtime adaptive controller for supporting hardware components with variable latency, in Proc. NS/ES (HS-0), pp. 0 (June 0). [], :,, VLD0 (Jan. 0). [], :,, -- (Sept. 0). [], :,, VLD0 (Dec. 0). c 0 Information Processing Society of Japan 0
DS0 0/9/ P CP P XB X0 weight DFG dist_x a d0 I (a) b P0 dist_x dist_x P 9 0 weight d0 c c c c DFG d0 R dy C0 dx R R dx D R D D R R EQ X = = = = = = c dx 0 = = C R R DFG C DFG SX Y (a) SY dy 0 = = R DFG R * R dy R * R 9 C0 dy 0 D C d0 d0 c c DFG 9 0 d DFG = = c = = d d DFG d d DFG = = d 9 d 0 (b) = = d d 9 0 (c) = = = = DFG (b) R * R R * R 9 0 bicubic (c) m-lerp c 0 Information Processing Society of Japan