Retiming Synchronous Circuitry
This paper shows how the technique of retiming can be used to transform a given sycnhronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph, and we give an O(|V||E|log|V|) algorithm for determining an equivalent circuit with the smalles...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149118 |
| _version_ | 1826216681618276352 |
|---|---|
| author | Leiserson, Charles E. Saxe, James B. |
| author_facet | Leiserson, Charles E. Saxe, James B. |
| author_sort | Leiserson, Charles E. |
| collection | MIT |
| description | This paper shows how the technique of retiming can be used to transform a given sycnhronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph, and we give an O(|V||E|log|V|) algorithm for determining an equivalent circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomimal-time optimal solution to the problem of pipelining combinatorial circuitry with minimum register cost. We also give a characterization of optimal retiming based on an efficiently solvable mixed-integer linear programming problem. |
| first_indexed | 2024-09-23T16:51:43Z |
| id | mit-1721.1/149118 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:51:43Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491182023-03-30T03:02:50Z Retiming Synchronous Circuitry Leiserson, Charles E. Saxe, James B. This paper shows how the technique of retiming can be used to transform a given sycnhronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph, and we give an O(|V||E|log|V|) algorithm for determining an equivalent circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomimal-time optimal solution to the problem of pipelining combinatorial circuitry with minimum register cost. We also give a characterization of optimal retiming based on an efficiently solvable mixed-integer linear programming problem. 2023-03-29T14:28:38Z 2023-03-29T14:28:38Z 1986-05 https://hdl.handle.net/1721.1/149118 MIT-LCS-TM-309 application/pdf |
| spellingShingle | Leiserson, Charles E. Saxe, James B. Retiming Synchronous Circuitry |
| title | Retiming Synchronous Circuitry |
| title_full | Retiming Synchronous Circuitry |
| title_fullStr | Retiming Synchronous Circuitry |
| title_full_unstemmed | Retiming Synchronous Circuitry |
| title_short | Retiming Synchronous Circuitry |
| title_sort | retiming synchronous circuitry |
| url | https://hdl.handle.net/1721.1/149118 |
| work_keys_str_mv | AT leisersoncharlese retimingsynchronouscircuitry AT saxejamesb retimingsynchronouscircuitry |