In this paper, we present a new methodology for structure optimization of block-based design. Instead of merging area and delay criteria, we segregate them into two independent steps. Solutions optimized for delay in the first step are optimized for area with a block-sizing algorithm in the second step. The fully optimized solutions eventually return to the first optimization step, if the user constraints are not met, using a structure-extraction module. A condition to this approach is that the area optimization phase does not alter the quality reached during delay optimization. We propose a framework for area optimization of delay-optimized structures based on structure similarities. We present a new model to represent block placements that share the same qualities for global routing. Using this model, we formally define the relation of similarity and exhibit several properties and theorems to validate our approach. The modules composing the area optimization phase are presented and experimental results confirm the validity of our methodology.

Floorplanning is an important step of IC design. Traditionally, floorplan representation has been segregated between slicing and non-slicing structures. We present a heuristic that translates any arbitrary structure into a slicing one, topologically equivalent to the initial one after a 1-D compaction.

This paper shows how algorithmic techniques and parallel processing can speed up general connectivity computation. A new algorithm, called Concurrent Group Search Algorithm (CGSA), is proposed that divides N(N-1)/2 vertex pairs into N-1 groups. Within each group general connectivities of all pairs can be calculated concurrently. Our experimental results show that this technique can achieve speedup of 12 times for one circuit. In addition, group computations are parallelized on a 16-node IBM SP2 with a speedup of 14 times over its serial counterpart observed. Combining the two approaches could result in a total speedup of up to 170 times, reducing CPU time from over 200 hours to 1.2 hour for one circuit. Our new model is better than those without clustering because it characterizes the connection graph more accurately, is faster to compute and produces better results. The best performance improvements are 43% for one circuit and 49% for another.

A new model for general connectivity is defined and its application to placement is presented in this paper. The new model is based on better understanding and analysis of connection graphs. Its computation time in the worst case is O(N/sup k+2/), where N is the number of cells in a connection graph and k is the order of general connectivity. 41 placements for three circuits were carried out with our new model and the results are compared with those from the conductance model proposed by an earlier paper. Our new model is better than the conductance model because ours characterizes the connection graph more accurately, is faster to compute, and produces better results. The best performance improvements for the three circuits are 35.4% (HK5601), 37.8%(HK5852), and 19.2%(HK5851).

It is demonstrated that sufficient and reasonable utilization of the constrained horizontal and vertical routing resources is the key to achieving a high completion rate in this one-and-one-half layer routing approach. By using the minimum intersection graph to order the nets, the number of intersections among the nets is minimum, the number of intersection columns is as small as possible, and the total length of poly-bars used in wiring is as short as possible. From this the requirements for the horizontal and vertical routing resources are as few as possible. A reasonable assignment of the horizontal routing resources can be achieved by operating the active track matrices of the nets at the predicted columns, while the optimal assignment of the vertical routing resources is obtained by using the cluster assignment algorithm of the incidence intersection columns. Guided by the wiring tracks in the predicted columns and using the poly-bars assigned, the channel routing can be implemented with high performance by scanning the channel from left to right and column by column.>