Calendar

Given a digital circuit (made of logical gates and registers), or a parallel loop, is it possible to construct a new circuit computing the same function but using less registers?
We show that the minimal number of registers is the size of a minimal cut in a periodic infinite graph corresponding to an unfolding of the initial circuit.
We also show when it coincides with the retiming technique introduced by Leiserson and Saxe and when it outperforms optimal retiming.