New analytical procedure for automatic cell placement in gate-arrays

A fully automated constructive global placement method based on analytical function minimisation is described. It is meant to be applied to the gate-array placement problem, which is known to be a most restrictive one. A penalty function approach is used to convert the problem into an unconstrained optimisation. The objective function is constructed of two parts: the first one, reflecting the attraction criterion, generates the so-called ´relative placement´, while the second one assembles the repulsion requirements (in which the essential geometric requirements are incorporated), and generates the so-called ´geometric placement´ or ´final placement´. The geometric requirements are introduced sequentially so that a strategy is proposed to enable the final solution (which becomes suboptimal in the sense that a longer interconnection length is obtained) to be kept as near as possible to the relative one. No convergence problems are encountered even for complex examples. Among the introduced penalty functions the most important one is the nonoverlapping penalty function. Here, a new, good approximation of the rectangular module shape is introduced enabling analytical definition of the constraints. It was recognised that, for complex placement problems, the nonoverlapping penalty was not strong enough to ensure nonoverlapping. Hence a new repulsive penalty is introduced which takes into account the module dimensions. Fully automatic row assignment of the modules is ensured by another new penalty. The gate assignment is performed automatically but, in order to avoid integer programming, it is performed as a separate post-processing phase. Examples of complex design were produced utilising 90% of the gate-array central area.