## Abstract

Classical retiming optimization algorithms do not consider circuits containing multiplexers or demultiplexers driven by a clock signal, because the associated retiming equations differ from the special classical form, which make applicable combinatorial algorithms of polynomial order. In order to provide an algorithm for multiplexer circuits it is shown here that retiming, being an integer linear programming problem inherently, can be relaxed to a linear programming formulation with real valued variables. This is due to the unimodularity of the matrices of the retiming formulation. Multiplexer circuits change this property in a way, which suggests how to use an integer linear programming problem to derive an polynomial retiming algorithm.

Original language | English |
---|---|

Pages (from-to) | 1736-1739 |

Number of pages | 4 |

Journal | Proceedings - IEEE International Symposium on Circuits and Systems |

Volume | 3 |

State | Published - 1995 |

Event | Proceedings of the 1995 IEEE International Symposium on Circuits and Systems-ISCAS 95. Part 3 (of 3) - Seattle, WA, USA Duration: 30 Apr 1995 → 3 May 1995 |