Kia Bazargan

This paper proposes two set-of-pairs-of-functions-to-be-distinguished (SPFD)-based rewiring algorithms to be used in a multi-tier rewiring framework, which employs multiple rewiring techniques. The first algorithm has two unique features: 1) a satisfiability problem (SAT) instance was devised so that an unsuccessful rewiring can be identified very quickly, and 2) unlike binary decision diagram-based methods that require all pairs of SPFD, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that the runtime of our algorithm is about three times faster than that of a conventional one under a simulated setting of such a framework and it scales well with the number of candidate wires considered. The efficacy of the framework can be further improved by the second proposed algorithm. The algorithm relies on a theory presented herein to allow adding a new wire outside of the restricted set of dominator nodes, a feature common in automatic-test-pattern-generation-based rewiring, but absent in existing SPFD-based ones. Although this algorithm may suffer from long runtimes in the same way conventional SPFD-based techniques do, experiments show that the number of wires which can be rewired increases 13% on average and the number of alternative wires also increases.

Traditionally, logic synthesis constrains the solution space of later design steps, such as physical design, because they are applied in sequence. Rewiring is a technique to restructure a circuit while maintaining its functionality. Since design properties and objectives can be considered during post-synthesis rewiring, it can help relieve constraints put forth by decisions made at earlier design steps. The extent of rewiring of a rewiring algorithm has a great impact on the success of the design flow. This paper presents a powerful rewiring technique that in addition to unifying all previously proposed set-of-pairs-of-functions-to-be-distinguished based rewiring techniques, it can perform rewiring with more than one wire which increases our ability to circumvent poorly-decided early design constraints. With this ability, the rewiring ability of using different numbers of wires is reported for the first time in this paper. Our technique can be used for run-lime/quality trade-off in any given rewiring application.

According to the ITRS predictions, controlling manufacturing yield is going to be a challenging task in future technologies. The effective yield of future FPGA architectures considering configurable logic blocks, switch boxes, connection boxes and routing segments is estimated in this paper. The results show that some degree of redundancy for logic blocks, routing and switch boxes is necessary. However, no more than one spare logic block per cluster, and at most one spare wire is required to obtain a satisfactory effective yield. The results also indicate that it is beneficial to increase logic cluster size of future FPGA architectures for better yield.