Analytical Timing Driven Global Placement of Structured ASIC
In the paper we developed an algorithm of structured ASIC global placement based on iteration of solution of convex problem and fast legalization. To achieve high quality of the developed algorithm for structured ASIC technology novel approaches are required in comparison to ASIC state of the art algorithm [3]. Developed algorithm allows obtaining higher quality and faster solution than previously used methodology. Physical synthesis CAD tools for structured ASIC are limited in approaches and methods they can use because of technology peculiarities, similar to FPGA CAD limitation. On the other hand, designers demand from structured integrated circuits and physical design tools features close to ASIC. Complexity of the structured ASIC grows. The number of the logical elements, speed of clocks, power consumption requirements significantly exceed FPGA capability. Global placement of the structured ASIC is the most crucial stage in the physical synthesis flow and for large circuits determines circuit features. New methods for design optimization are required. Min-cut and SA methods can't provide good global solution any more. The state of art approach for ASIC optimization is to use primal-dual optimization approach. An idea originated in SimPL tool [2]. In [2] a solution of the constrained functional is obtained via iterations, on every iteration quadratic convex part and constrained parts are sequentially solved. This approach has already been applied to FPGA placement in [4-5]. In this work we apply ideas from [2-3] for structured ASIC global placement. To achieve production level quality we solved a set of problems which were not yet discussed in previous works. We developed a new fast legalization method based on the network flow, we introduced a two stage global placement to achieve high quality block memory placement, developed a novel parallel linear solution preconditioner, efficient timing optimization scheme is applied. Developed algorithm shows improvements over previously used method [1] which was very well tuned for the structured ASIC technology. It gives 5-10x speed up, significant wire length decrease and no timing degradation in comparison to [1].