Optimality and stability study of timing-driven placement algorithms

This work studies the optimality and stability of timing-driven placement algorithms. The contributions of this work include two parts: 1) We develop an algorithm for generating synthetic examples with known optimal delay for timing driven placement (T-PEKO). The examples generated by our algorithm can closely match the characteristics of real circuits. 2) Using these synthetic examples with known optimal solutions, we studied the optimality of several timing-driven placement algorithms for FPGAs by comparing their solutions with the optimal solutions, and their stability by varying the number of longest paths in the examples. Our study shows that with a single longest path, the delay produced by these algorithms is from 10% to 18% longer than the optima on the average, and from 34% to 53% longer in the worst case. Furthermore, their solution quality deteriorates as the number of longest paths increases. For examples with more than 5 longest paths, their delay is from 23% to 35% longer than the optima on the average, and is from 41% to 48% longer in the worst case.