The effects of false paths in high-level synthesis

Abstract

The author discusses the effects of false paths and their consequences in scheduling and allocation during high-level synthesis. False paths through the control-flow graph may occur due to sequences of conditional operations. The detection of false paths during scheduling may result in a smaller number of states, improved operator sharing, and smaller control logic. A heuristic algorithm is presented for the detection and elimination of false paths during path-based scheduling. Results for benchmark examples are presented. For the designs which contained false paths, the percentage of false paths varied from 5% to 83%. A reduction of 15% in the final cell count for one benchmark was obtained by eliminating false paths. Even though the proposed algorithm is heuristic and cannot guarantee the detection of all false paths, it did find all false paths in the small to medium size examples tried. In most cases the condition trees are small, with few data dependencies, which increases the probability of a false path being found by the algorithm.