Path Reduction with Register Repositioning

Abstract Circuits with large numbers of paths present difficulties for path delay fault testing and timing analysis.  By repositioning registers we can in many cases substantially reduce the number of paths in the circuit.  The proposed method applies on an acyclic representation of the circuit after some its edges are removed.  We present an integer linear program for repositioning registers such that they minimize the number of paths in acyclic circuits with at most one register on each I/O path.  In the more general case of sequentially deep circuits, we first decompose the circuit in to sequentially shallow acyclic subcircuits.  Our results show that in many cases local optimization for path reduction often results in a global reduction as well.