This paper presents a set of techniques for placement-coupled timing-driven logic replication. Two components are at the core of the approach. First, is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second, the replication tree is introduced, which allows to induce large fanin trees from a given circuit, which can then be optimized by the embedder. The authors have built an optimization engine around these two ideas and report promising results for the field-programmable gate array (FPGA) domain including clock period reductions of up to 36% compared with a timing-driven placement from versatile place and route (VPR) (Marquardt , 2000) and almost double the average improvement of local replication (Beraudo and Lillis, 2003). These results are achieved with modest area and runtime overhead. In addition, issues that arise due to reconvergence in the circuit specification are addressed. The authors build on the replication tree idea and enhance the timing-driven fanin tree embedding algorithm to optimize subcritical paths, yielding even better delay improvements.

We present a set of techniques for placement-coupled, timing-driven logic replication. Two components are at the core of the approach. First is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second we introduce the Replication Tree which allows us to induce large fanin trees from a given circuit which can then be optimized by the embedder. We have built an optimization engine around these two ideas and report promising results for the FPGA domain including clock period reductions of up to 36% compared with a timing-driven placement from VPR [12] and almost double the average improvement of local replication from [1]. These results are achieved with modest area and runtime overhead.

Logic replication for placement level timing optimization is studied in the context of FPGAs. We make the observation that critical paths are dominated by interconnect delay and are frequently highly circuitous. We propose a systematic replication technique to “straighten ” such paths. The resulting algorithm has several components: cell selection, slot selection for a duplicate cell, fanout partitioning and placement legalization. This algorithm is described and promising preliminary experimental results are reported with up to 29 % improvement in critical path delay.