An improved approach for alternative wires identification

Redundancy addition and removal (RAR) is a restructuring technique used in the synthesis and optimization of logic designs and physical designs. It finds alternative wires to replace a given target wire without changing the functionality of the circuit. Previous approaches apply two-stage algorithms for this problem. First, they build up a set of candidate wires for the target wire. Second, they perform redundancy test on each candidate wire to determine if it is an alternative wire. Recently, a one-stage algorithm RAM-FIRE (Chang et al., 2003) is proposed. It conducts three logic implications to identify backward alternative wires without trial-and-error redundancy tests. However, the number of alternative wires it can find is smaller than that obtained by the previous two-stage approaches. Here, we propose an improved one-stage algorithm, which only conducts two logic implications. The experimental results show that compared to RAMFIRE, our approach only requires 83% cpu time on average, while obtaining the same number of backward alternative wires. As extending to finding both backward and forward alternative wires, on average our approach gets 157% improvement with 32% cpu time overhead.