Reversible statistical max/min operation: Concept and applications to timing

The increasing significance of variability in modern sub-micron manufacturing process has led to the development and use of statistical techniques for chip timing analysis and optimization. Statistical timing involves fundamental operations like statistical-add, sub, max and min to propagate timing information (modeled as random variables with known probability distributions) through a timing graph model of a chip design. Although incremental timing during optimization updates timing information of only certain parts of the timing-graph, lack of established reversible statistical max or min techniques forces more-than-required computations. This paper describes the concept of reversible statistical max and min for correlated Gaussian random variables, and suggests potential applications to statistical timing. A formal proof is presented to establish the uniqueness of reversible statistical max. Experimental results show run-time savings when using the presented technique in the context of chipslack computation during incremental timing optimization. © 2012 ACM.