Fixed Points in Multi−Cycle Path Detection
Accurate timing analysis is crucial for obtaining the optimal clock frequency, and for other design stages such as power analysis. Most methods for estimating propagation delay identify multi-cycle paths (MCPs), which allow timing to be relaxed, but ignore the set of reachable states, achieving scal...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Published: |
IEEE
2015
|
| _version_ | 1797077474436186112 |
|---|---|
| author | D'Silva, V Kroening, D |
| author2 | Al−Hashimi, B |
| author_facet | Al−Hashimi, B D'Silva, V Kroening, D |
| author_sort | D'Silva, V |
| collection | OXFORD |
| description | Accurate timing analysis is crucial for obtaining the optimal clock frequency, and for other design stages such as power analysis. Most methods for estimating propagation delay identify multi-cycle paths (MCPs), which allow timing to be relaxed, but ignore the set of reachable states, achieving scalability at the cost of a severe lack of precision. Even simple circuits contain paths affecting timing that can only be detected if the set of reachable states is considered. We examine the theoretical foundations of MCP identification and characterise the MCPs in a circuit by a fixed point equation. The optimal solution to this equation can be computed iteratively and yields the largest set of MCPs in a circuit. Further, we define conservative approximations of this set, show how different MCP identification methods in the literature compare in terms of precision, and show one method to be unsound. The practical application of these results is a new method to detect multi-cycle paths using techniques for computing invariants in a circuit. Our implementation performs well on several benchmarks, including an exponential improvement on circuits analysed in the literature. |
| first_indexed | 2024-03-07T00:18:33Z |
| format | Conference item |
| id | oxford-uuid:7bb4ff9e-d226-44c7-89d1-82804ae8f1f1 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:18:33Z |
| publishDate | 2015 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:7bb4ff9e-d226-44c7-89d1-82804ae8f1f12022-03-26T20:52:19ZFixed Points in Multi−Cycle Path DetectionConference itemhttp://purl.org/coar/resource_type/c_5794uuid:7bb4ff9e-d226-44c7-89d1-82804ae8f1f1Department of Computer ScienceIEEE2015D'Silva, VKroening, DAl−Hashimi, BAccurate timing analysis is crucial for obtaining the optimal clock frequency, and for other design stages such as power analysis. Most methods for estimating propagation delay identify multi-cycle paths (MCPs), which allow timing to be relaxed, but ignore the set of reachable states, achieving scalability at the cost of a severe lack of precision. Even simple circuits contain paths affecting timing that can only be detected if the set of reachable states is considered. We examine the theoretical foundations of MCP identification and characterise the MCPs in a circuit by a fixed point equation. The optimal solution to this equation can be computed iteratively and yields the largest set of MCPs in a circuit. Further, we define conservative approximations of this set, show how different MCP identification methods in the literature compare in terms of precision, and show one method to be unsound. The practical application of these results is a new method to detect multi-cycle paths using techniques for computing invariants in a circuit. Our implementation performs well on several benchmarks, including an exponential improvement on circuits analysed in the literature. |
| spellingShingle | D'Silva, V Kroening, D Fixed Points in Multi−Cycle Path Detection |
| title | Fixed Points in Multi−Cycle Path Detection |
| title_full | Fixed Points in Multi−Cycle Path Detection |
| title_fullStr | Fixed Points in Multi−Cycle Path Detection |
| title_full_unstemmed | Fixed Points in Multi−Cycle Path Detection |
| title_short | Fixed Points in Multi−Cycle Path Detection |
| title_sort | fixed points in multi cycle path detection |
| work_keys_str_mv | AT dsilvav fixedpointsinmulticyclepathdetection AT kroeningd fixedpointsinmulticyclepathdetection |