Fast Timing-Driven Gate Cloning

In this section, we present our algorithms for the cases where P is movable and P is fixed. We start with several new concepts. 

Treat the whole circuit image as a 2D plane H. For each fanin gate f) in F, the arri val time at any poin t V in // is A A r (f )+D (f), v), and D Fi,v) = rdis(Fi,v). Therefore, if we place a gate at v with the fanin set F, according to static timing 

So K (F) is the set of points which have minimum arrival time for all fanins. In the following, we will show that K(F) is either a single point or a line segment with 45 slope. Refer to Figs. 6.2 and 6.3 for examples of K F). 

If there is only a single fanin F, it is obvious that K (F) is the same point as the location of F itself, with AAT K F)) = AAT(F). If there are two fanins Fi and F2, then there are three cases. 

The next lemma states that for any point in the plane, its arrival time (required arrival time) can also be represented by the arrival time at (F) (AT(5)) and the shortest Manhattan distance between the point and K(F) (K(S)). The proof is straightforward, it is based on the merging process and the fact that computation of arrival time (or required arrival time) is a max (min) operation. 

---