Spatial Timing Analysis With Exact Propagation of Delay and Application to FPGA Performance

This paper introduces a method for delay approximation in timing analysis for spatial variation where the parameters representing the sources of variation are based on a convolution of random variation with a basis function. This results in delay models that need only include nine nonzero random variables for each edge in a typical spatial correlation model, less than previous work. As a result the symbolic representation of all potentially critical delays can be carried through the entire timing analysis without the need for approximate maximum function of statistical delays, producing a conservative but accurate upper bound on timing to meet a specified yield target. The algorithm has been applied to a set of field-programmable gate array designs and used to show that it is computationally efficient even with large designs. Further, because the timing is pessimistic but accurate, it removes the need for guardbanding the timing analysis compared to previous approaches. The representation of all potentially critical paths in a symbolic form also enables fast Monte-Carlo (MC) algorithms to supplement the deterministic ones. We show a combined deterministic and MC algorithm that is on average within 0.35% of ideal, and has a 10
^-6
probability of an optimistic result.