Given n points on a plane, a rectilinear Steiner minimal tree (RSMT) connects these points through some extra points called Steiner points to achieve a tree with minimal total wire length. Taking blockages into account dramatically increases the problem complexity. It is extremely unlikely that an efficient optimal algorithm exists for rectilinear Steiner minimal tree construction with rectilinear blockages (RSMTRB). Although there exist some heuristic algorithms for this problem, they have either poor quality or expensive running time. In this paper, we propose an efficient and effective approach to solve RSMTRB. The connection graph we used in this approach is called spanning graph which only contains O(n) edges and vertices. An O(n log n) time algorithm is proposed to construct spanning graph for RSMTRB. The experimental results show that this approach can achieve a solution with significantly reduced wire length. The total run time increased is negligible in the whole design flow.

In this paper, we propose a fast algorithm to construct a performance-driven routing tree with simultaneous buffer insertion and wire sizing in the presence of wire and buffer obstacles. Recently, several algorithms have been published addressing the routing tree construction problem. However, all these algorithms are slow and not scalable. In this paper, we propose an algorithm which is fast and scalable with problem size. The main idea of our approach is to specify some important high-level features of the whole routing tree so that it can be broken down into several components. We apply stochastic search to find the best specification. Since we need very few high-level features, the size of stochastic search space is small and can be searched in very little time. The solutions for the components are either pre-generated and stored in lookup tables, or generated by extremely fast algorithms whenever needed. Since it is efficient to obtain solutions for components, it is also efficient to construct and evaluate the whole routing tree for each specification. Experimental results show that, for trees of moderate size, our algorithm out performs the previous algorithms in both quality and runtime.

A floorplan can be defined as a rectangular dissection of the floorplan region. Simple and tight asymptotic bounds on the number of floorplans for different dissection structures help us to evaluate the size of the solution space of different floorplan representation. They are also interesting theoretically. However, only loose bounds exist in the literature. In this paper, we derive tighter asymptotic bounds on the number of slicing, mosaic and general floorplans. Consider the floorplanning of n blocks. For slicing floorplan, we prove that the exact number is n!((-1)/sup n+1//2)/spl Sigma//sub k=0//sup n/(3+/spl radic/8)/sup n-2k/(/sub k//sup 1/2/)(/sub n - k//sup 1/2/) and the tight bound is /spl Theta/(n!2/sup 2.543n//n/sup 1.5/) [9] . For mosaic floorplan, we prove that the tight bound is /spl Theta/(n!2/sup 3n//n/sup 4/). For general floorplan, we prove a tighter lower bound of /spl Omega/(n!2/sup 3n//n/sup 4/) and a tighter upper bound of O(n!2/sup 5n//n/sup 4.5/).

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Nonslicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and nonredundant topological representation for nonslicing structure. In this paper, we propose the first representation of this kind. Like some previous work (Zhou et al. 2001), we have also made use of a mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules (that will increase the size of the solution space significantly), our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan such that every nonslicing floorplan can be obtained uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!2/sup 3n//n/sup 1.5/), which is the size without empty room insertion, but every nonslicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Non-slicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and non-redundant topological representation for non-slicing structure. In this paper, we will propose the first representation of this kind. Like some previous work [9], we have also made used of mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules, our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan in such a way that every non-slicing floorplan can be obtained by this method uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!23n/n1.5) but every non-slicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.