Dynamic conditional branch balancing during the high-level synthesis of control-intensive designs

We present two novel strategies to increase the scope for application of speculative code motions: (1) Adding scheduling steps dynamically during scheduling to con-ditional branches with fewer scheduling steps. This in-creases the opportunities to apply code motions such as conditional speculation that duplicate operations into the branches of a conditional block. (2) Determin-ing if an operation can be conditionally speculated into multiple basic blocks either by using existing idle re-sources or by creating new scheduling steps. These strategies lead to balancing of the number of steps in the conditional branches without increasing the longest path through the conditional block. Algorithms for these strategies have been implemented within the Spark high-level synthesis framework that accepts a behav-ioral description in ANSI-C as input and produces syn-thesizable register-transfer level VHDL. Experiments on two moderately complex industrial-strength appli-cations, namely, MPEG-1 and the GIMP image pro-cessing tool, demonstrate that conditional speculation is ineffective without using these strategies. 1