In DSP and VLSI design, there are many variational parameters that are unknown during the design stage, but significantly affect chip performance. Some uncertainties are due to manufacturing process fluctuations, others depend on the dynamic context in which the chip is used, such as input patterns, temperature and voltage. Chip designers need to consider these uncertainties as early as possible to ensure chip performance, improve yield and reduce design cost. However, it is a challenging task to model uncertainties and predict the joint impacts of them, which often either requires high computational cost or yields unsatisfactory accuracy.; Interval algebra provides a general solution to modeling and manipulating uncertainties. The idea is to replace scalar quantities with bounded intervals, and propagate intervals through arithmetic operations. A recent technique---affine arithmetic---advances the field in handling correlated intervals. However, it still produces overly conservative bounds due to the inability to consider probability information.; The goal of this dissertation is to improve the accuracy of affine arithmetic and broaden its application in DSP and VLSI design. To achieve this goal, we develop a probabilistic interval method that enhances the interval representation and computations with probability information. First, we provide a probabilistic interpretation for affine intervals based on the Central Limit Theory. Based on this interpretation, we present a probabilistic bounding method that returns less pessimistic bounds of affine intervals. Second, we propose an enhanced interval representation form that utilizes probability information to handle asymmetric affine intervals. This addresses a fundamental issue of current affine arithmetic, i.e., it only represents center-symmetric intervals. This restriction highly limits the accuracy of nonlinear interval functions. By introducing center-asymmetric affine intervals, we are able to design better algorithms for nonlinear interval functions. We present the improved algorithms for common nonlinear functions, with emphasis on the multiplication and the division algorithms. Finally, we also realize that in many applications, detailed probability distribution within an interval is more desirable than its bounds. Therefore, another contribution of this dissertation is to enable our interval method to estimate not only the bounds, but also the distribution within an interval. We demonstrate the effectiveness of our techniques by several applications in DSP and VLSI design.
展开▼
