TL;DR
This paper introduces TFA, a novel algorithm that efficiently calculates signal delay and transition times in high-speed VLSI circuits. By intelligently categorizing circuit nets and applying different calculation methods based on complexity, TFA achieves accuracy comparable to complex methods while being significantly faster, making it practical for modern chip design.
What Problem Does This Paper Address?
As microprocessors shrink and clock speeds increase, accurately predicting signal delays and transition times (slews) in the intricate network of wires (interconnects) on a chip becomes crucial for successful design. Traditional methods like the Elmore delay are fast but often too inaccurate for modern designs, while more accurate methods like Asymptotic Waveform Evaluation (AWE) are computationally too expensive for the massive scale of today's chips. This creates a critical gap: designers need a timing analysis tool that is both highly accurate and computationally efficient to ensure their designs function correctly and can be optimized effectively. The paper addresses this by proposing a method that balances accuracy and speed for interconnect delay and slew calculation.
Methods
The core of the paper is the Threshold-based Filtering (TFA) algorithm. TFA tackles the accuracy-speed trade-off by classifying circuit nets into three categories:
- Low Complexity Nets: For these, the computationally inexpensive Elmore delay (based on the first moment of the impulse response) is sufficient.
- Medium Complexity Nets: These require a more sophisticated approach, utilizing the first two moments of the impulse response. The paper derives an analytical equation for delay and slew calculation based on these moments, particularly highlighting the role of the ratio of the second to the square of the first moment ($m_2/m_1^2$).
- High Complexity Nets: For the most complex nets, where higher-order moments become significant, TFA resorts to the more accurate but computationally intensive AWE method.
The key innovation lies in the intelligent classification of nets. This is achieved by analyzing characteristics like the input slew, the ratio of the input slew to the Elmore delay ($\mu$), and the $m_2/m_1^2$ ratio ($\eta$). These parameters act as thresholds to decide which calculation method to apply, ensuring that computational resources are only spent on the nets that truly require it.
Datasets
The paper evaluates its algorithm on a large industrial 90nm VLSI circuit with over 120,000 gates and approximately 1.67 million delay stages. This is a real-world benchmark, not a newly introduced dataset.
Key Insights and Ideas
- The "sweet spot" for Elmore delay: The paper demonstrates that for certain conditions (e.g., when the 70% transition point is considered), Elmore delay can be surprisingly accurate and insensitive to higher-order moments. This insight is leveraged in the classification.
- $m_2/m_1^2$ as a critical indicator: The ratio of the second to the square of the first moment ($m_2/m_1^2$) is shown to be a crucial factor in determining the accuracy of moment-based delay calculations. When this ratio exceeds a certain threshold, higher-order moments (and thus AWE) become necessary.
- Slew accuracy is paramount: The authors emphasize that errors in slew calculation can be amplified along a timing path, making accurate slew estimation as important as delay estimation.
- Intelligent filtering is key: The core idea is that not all nets are created equal in terms of their impact on timing accuracy. By filtering nets and applying the appropriate level of analysis, significant computational savings can be achieved without sacrificing overall accuracy.
Key Results
The TFA algorithm achieved results that are highly competitive:
- Accuracy: TFA's delay and slew estimations were comparable to the full-blown AWE-based calculators.
- Speed: TFA achieved runtimes only 14% higher than the simple Elmore-delay calculator, while being significantly faster (62% faster) than the AWE-based analysis.
- Error Reduction: TFA resulted in less than 6ps error in both slew rate and stage delays compared to AWE-based results.
- Practicality: The algorithm was successfully implemented in a commercial, high-capacity static timing analyzer and tested on a large industrial design.
Limitations and Future Work
- Parameter Tuning: The accuracy of TFA is dependent on the chosen threshold values ($\phi$, $\mu$, and $\eta$). While the paper provides specific values used in their experiments, optimal tuning might be design-specific.
- Future Work: The paper suggests that as $\phi$, $\mu$, and $\eta$ approach certain limits, TFA can effectively reduce to either the Elmore-based or AWE-based methods, indicating a seamless transition between different analysis complexities. Further exploration of these parameter sensitivities and their impact on different circuit types could be a direction for future work. The authors also imply that the analytical equations derived for medium complexity nets could be further refined.
Summary updated