Dynamic Range Estimation for Systems with Control-flow Structures

Bin Wu


It has been widely recognized that the dynamic range information of an application can be exploited to reduce the datapath bitwidth of either processors or ASICs, and therefore the overall circuit area, delay and power consumption. Many analytical approaches are proposed for dynamic range estimation. However, because the intractable nature of control-flow structures, all of currently available methods only consider the systems consisting of pure dataflow structures/operations while the general digital applications always contain some control-flow structures, such as conditional branches and loops, which depend on the randomness of inputs or other variables. Failing to handle the general control-flow structures seriously restricts the applicability of analytical methods for dynamic range estimation, and makes the lack-of-insight and costly profiling the only solution for many applications. In this paper, we propose the first analytical method with the capability of handling the general control-flow structures (especially random branches and loops) by utilizing a powerful mathematic tool, polynomial chaos expansion (PCE). Our method brings the application scope of analytical method for range estimation to the general systems with control-flow structures for the first time, and it achieves high accuracy and orders of magnitude more efficiency than profiling.