Retiming

<h2 id="formal-description">Formal description</h2>
<p>The initial formulation of the retiming problem as described by Leiserson and Saxe is as follows. Given a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> 
  
    
      
        G
        :=
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G:=(V,E)}
  
 whose vertices represent <a href="/facts/Logic_gates/RHLulvKI">logic gates</a> or combinational delay elements in a circuit, assume there is a directed edge 
  
    
      
        e
        :=
        (
        u
        ,
        v
        )
      
    
    {\displaystyle e:=(u,v)}
  
 between two elements that are connected directly or through one or more registers.  Let the <i>weight</i> of each edge 
  
    
      
        w
        (
        e
        )
      
    
    {\displaystyle w(e)}
  
 be the number of registers present along edge 
  
    
      
        e
      
    
    {\displaystyle e}
  
 in the initial circuit.  Let 
  
    
      
        d
        (
        v
        )
      
    
    {\displaystyle d(v)}
  
 be the <a href="/facts/Propagation_delay/tUcrAwwe">propagation delay</a> through vertex 
  
    
      
        v
      
    
    {\displaystyle v}
  
.  The goal in retiming is to compute an integer <i>lag</i> value 
  
    
      
        r
        (
        v
        )
      
    
    {\displaystyle r(v)}
  
 for each vertex such that the retimed weight 
  
    
      
        
          w
          
            r
          
        
        (
        e
        )
        :=
        w
        (
        e
        )
        +
        r
        (
        v
        )
        −
        r
        (
        u
        )
      
    
    {\displaystyle w_{r}(e):=w(e)+r(v)-r(u)}
  
 of every edge is non-negative. There is a proof that this preserves the output functionality.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h3>Minimizing the clock period with network flow</h3>
<p>The most common use of retiming is to minimize the <a href="/facts/Clock_period/w055Woaj">clock period</a>.  A simple technique to optimize the clock period is to search for the minimum feasible period (e.g. using <a href="/facts/Binary_search/FFmQzunc">binary search</a>).
</p><p>The feasibility of a clock period 
  
    
      
        T
      
    
    {\displaystyle T}
  
 can be checked in one of several ways.  The <a href="/facts/Linear_program/GduXFQxT">linear program</a> below is feasible if and only if 
  
    
      
        T
      
    
    {\displaystyle T}
  
 is a feasible clock period.  Let 
  
    
      
        W
        (
        u
        ,
        v
        )
      
    
    {\displaystyle W(u,v)}
  
 be the minimum number of registers along any path from 
  
    
      
        u
      
    
    {\displaystyle u}
  
 to 
  
    
      
        v
      
    
    {\displaystyle v}
  
 (if such a path exists), and 
  
    
      
        D
        (
        u
        ,
        v
        )
      
    
    {\displaystyle D(u,v)}
  
 is the maximum delay along any path from 
  
    
      
        u
      
    
    {\displaystyle u}
  
 to 
  
    
      
        v
      
    
    {\displaystyle v}
  
 with W(u,v) registers.  The dual of this program is a <a href="/facts/Minimum_cost_circulation_problem/u0ymlLF0">minimum cost circulation problem</a>, which can be solved efficiently as a network problem.  The limitations of this approach arise from the enumeration and size of the 
  
    
      
        W
      
    
    {\displaystyle W}
  
 and 
  
    
      
        D
      
    
    {\displaystyle D}
  
 matrices.
</p>
<table><tbody><tr><td>Given</td><td colspan="2">                    w        (        e        )        ,        W        (        u        ,        v        )        ,        D        (        u        ,        v        )              {\displaystyle w(e),W(u,v),D(u,v)}   and a target clock period                     T              {\displaystyle T}  </td></tr><tr><td>Find</td><td colspan="2">                    r        (        v        )        :        V        →                  Z                      {\displaystyle r(v):V\to \mathbb {Z} }  </td></tr><tr><td>Such that</td></tr><tr><td></td><td>                    r        (        u        )        −        r        (        v        )              {\displaystyle r(u)-r(v)}  </td><td>                    ≤        w        (        e        )              {\displaystyle \leq w(e)}  </td></tr><tr><td></td><td>                    r        (        u        )        −        r        (        v        )              {\displaystyle r(u)-r(v)}  </td><td>                    ≤        W        (        u        ,        v        )        −        1              {\displaystyle \leq W(u,v)-1}   if                     D        (        u        ,        v        )        >        T              {\displaystyle D(u,v)>T}  </td></tr></tbody></table>
<h3>Minimizing the clock period with MILP</h3>
<p>Alternatively, feasibility of a clock period 
  
    
      
        T
      
    
    {\displaystyle T}
  
 can be expressed as a mixed-integer <a href="/facts/Linear_program/GduXFQxT">linear program</a> (MILP).  A solution will exist and a valid lag function 
  
    
      
        r
        (
        v
        )
      
    
    {\displaystyle r(v)}
  
 will be returned if and only if the period is feasible.
</p>
<table><tbody><tr><td>Given</td><td colspan="2">                    w        (        e        )        ,        d        (        v        )              {\displaystyle w(e),d(v)}   and a target clock period                     T              {\displaystyle T}  </td></tr><tr><td>Find</td><td colspan="2">                    r        (        v        )        :        V        →                  Z                      {\displaystyle r(v):V\to \mathbb {Z} }   and                     R        (        v        )        :        V        →                              R                                {\displaystyle R(v):V\to {\mathcal {R}}}  </td></tr><tr><td>Such that</td></tr><tr><td></td><td>                    r        (        v        )        −        R        (        V        )              {\displaystyle r(v)-R(V)}  </td><td>                    ≤        −        d        (        v        )                  /                T              {\displaystyle \leq -d(v)/T}  </td></tr><tr><td></td><td>                    R        (        v        )        −        r        (        v        )              {\displaystyle R(v)-r(v)}  </td><td>                    ≤        1              {\displaystyle \leq 1}  </td></tr><tr><td></td><td>                    r        (        u        )        −        r        (        v        )              {\displaystyle r(u)-r(v)}  </td><td>                    ≤        w        (        e        )              {\displaystyle \leq w(e)}  </td></tr><tr><td></td><td>                    R        (        u        )        −        R        (        v        )              {\displaystyle R(u)-R(v)}  </td><td>                    ≤        w        (        e        )        −        d        (        v        )                  /                T              {\displaystyle \leq w(e)-d(v)/T}  </td></tr></tbody></table>
<h3>Other formulations and extensions</h3>
<p>Alternate formulations allow the minimization of the register count and the minimization of the register count under a delay constraint.  The initial paper includes extensions that allow the consideration of fan-out sharing and a more general delay model.  Subsequent work has addressed the inclusion of register delays,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> load-dependent delay models,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> and hold constraints.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="problems">Problems</h2>
<p>Retiming has found industrial use, albeit sporadic.  Its primary drawback is that the state encoding of the circuit is destroyed, making debugging, testing, and verification substantially more difficult.  Some retimings may also require complicated initialization logic to have the circuit start in an identical initial state.  Finally, the changes in the circuit's topology have consequences in other logical and physical synthesis steps that make <a href="/facts/Design_closure/ddvtJGfs">design closure</a> difficult.
</p>
<h2 id="alternatives">Alternatives</h2>
<p>Clock skew scheduling is a related technique for optimizing sequential circuits.  Whereas retiming relocates the structural position of the registers, clock skew scheduling moves their temporal position by scheduling the arrival time of the clock signals.  The lower bound of the achievable minimum clock period of both techniques is the maximum mean cycle time (i.e. the total combinational delay along any path divided by the number of registers along it).
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Logic_synthesis/w35wWFfK">Logic synthesis</a></li>
<li><a href="/facts/Electronic_design_automation/o4la3fmX">Electronic design automation</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Leiserson, 1C. E.; Saxe, J. B. (1983). "Optimizing Synchronous Systems". <i>Journal of VLSI and Computer Systems</i>. 1 (1): 41–67.{{cite journal}}:  CS1 maint: numeric names: authors list (link)</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://people.csail.mit.edu/devadas/6.373/lectures/l10/">Presentation on retiming from MIT</a></li>
<li><a href="https://sites.google.com/site/mhutton1/2003_IWLS_BA_retime.pdf">A Safe and Complete Gate-Level Register Retiming Algorithm</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Charles E. Leiserson, Flavio M. Rose, JamesB. Saxe (1983). "Optimizing Synchronous Circuitry by Retiming". Third Caltech Conference on Very Large Scale Integration. Springer: 87–116. doi:10.1007/978-3-642-95432-0_7.{{cite journal}}:  CS1 maint: multiple names: authors list (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Charles E. LeisersonJames B. Saxe (June 1991). "Retiming synchronous circuitry". Algorithmica. 6 (1). Springer: 5–35. doi:10.1007/BF01759032. S2CID 18674287. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>K. N. Lalgudi, M. C. Papaefthymiou, Retiming edge-triggered circuits under general delay models , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.16, no.12, pp.1393-1408, Dec. 1997. <a href="https://doi.org/10.1109%2F43.664222" target="_blank">https://doi.org/10.1109%2F43.664222</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>K. N. Lalgudi, M. C. Papaefthymiou, Retiming edge-triggered circuits under general delay models , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.16, no.12, pp.1393-1408, Dec. 1997. <a href="https://doi.org/10.1109%2F43.664222" target="_blank">https://doi.org/10.1109%2F43.664222</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>M. C. Papaefthymiou, Asymptotically efficient retiming under setup and hold constraints , IEEE/ACM International Conference on Computer-Aided Design, 1998. <a href="https://doi.org/10.1145%2F288548.289060" target="_blank">https://doi.org/10.1145%2F288548.289060</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Retiming open-in-new

Retiming