We have developed mapping and hierarchical self-organizing neural networks for placement of very large scale integrated (VLST) circuits. In this paper, we introduce MHSO and MHSO2 as two versions of mapping and hierarchical self-organizing network (MHSO) algorithms. By using the MHSO, each module in the placement wins the competition with a probability density function that is defined according to different design styles, e.g., the gate arrays and standard cell circuits. The relation between a placement carrier and movable modules is met by the algorithm's ability to map an input space (somatosensory source) into an output space where the circuit modules are located, MHSO2 is designed for macro cell circuits. In this algorithm, the shape and dimension of each module is simultaneously considered together with the wire length by a hierarchical order. In comparison with other conventional placement approaches, the MHSO algorithms have shown their distinct advantages. The results for benchmark circuits so far obtained are quite comparable to simulated annealing (SA), but the computation time is about eight-ten times faster than with SA.

We propose an efficient strategy for qualitative analysis of measured polymer spectra based on fast wavelet transforms and fuzzy set theory. First a wavelet transform is applied to the measured data acting as a feature extractor. Thus huge data sets are enormously compressed and only a few typical features (wavelet coefficients) locating the spectra peaks remain for the identification process. Then, a fuzzy classification algorithm separates different spectra into various clusters thus giving a qualitative interpretation of the ingredients due to calculated membership values. For that we implemented a fuzzy c-means algorithm, a fuzzy Kohonen cluster algorithm and special rule based approach with fuzzy if-then rules.

A new strategy taken from statistical and nuclear physics enables a qualitative and macroscopic approach to combinatorial optimization. For this purpose the mean field approximation is interpreted in a fuzzy manner and the strategy is tested at some NP complete layout problems. The described applications concerning graph partitioning, linear ordering and two dimensional assignment show performance comparable with simulated annealing, but much faster. Especially a new fuzzy net model can treat hypergraphs without splitting multi pin nets into two point nets.

Fast hierarchical optimization methods applied to VLSI-floorplanning and placement play a major role in advancing the state of the art in physical design, because circuits get more and more complex. This paper presents a new approach for floorplanning and placement using fuzzy logic as the framework for optimal partitioning. Two hierarchical partitioning strategies are described, both based on the fuzzy c-means algorithm (FCM), well known in the area of clustering and pattern recognition. The first method outlined is applied to a modified GORDIAN procedure, combining wire-length minimization by force directed relaxation (FDR) and a fast clustering technique instead of min-cut. The second approach outlined specifies different similarities between the cells using one fuzzy similarity relation for each feature. A simple example with 16 mesh connected cells and a benchmark example with 33 cells are given to demonstrate the performance of the strategy.>

A description is presented of a novel optimization procedure called diffusion which can be used in global circuit placement for suppressing inter-module and module-to-chip boundary overlaps. A salient feature of the proposed diffusion procedure is that multiple decisions on the moves of all variables (module positions) are simultaneously made such that a global, analytic objective function is minimized. Various strategies are discussed to speed up the convergence, and to prevent the solution from being stuck at local minima. A net force model is used with the diffusion procedure to minimize the inter-module wire length besides reducing the inter-module and module-to-chip overlaps. Various experimental results are given. Further potential applications of the proposed procedure include multilayer placement, and placement in an arbitrarily-shaped region.>

In this paper, we present a new, quasi-parallel approach to the loose routing problem for gate array LSI design. It is based on a new modeling for the decomposition problem of each net using a compact net graph which maps sets of feed-throughs instead of individual ones. The loose routing is done by calculation of a minimum spanning tree in this net graph and by a proper embedding of the tree as a set of single-channel subnets and feed-throughs. Moreover, a hierarchical approach is proposed, leading to a quasi-parallel embedding of all nets. It also allows different routing priorities for single connections within multiterminal nets. The hierarchical loose routing concept presented here is implemented in the fully integrated gate array design system MEGA and has been successfully tested on several industrial design examples.

Some of the essentials for layout of complex VLSI circuits are hierarchical design based on macrocells of arbitrary size and shape, power nets with local varying width, signal nets with individual width and very compacted layouts which still have to guarantee all geometrical design rules. This paper is devoted to the problem of automatic routing with real geometries. VWROUT, a Variable Width Routing System is presented. This includes planar power net routing with variable width on a single layer, loose and final routing of signal nets with variable width on two layers (H-V routing), and layout compaction with design-rule verification. Though automatic routing systems have been developed successfully, the intention of this paper is to demonstrate that layout programs of today have not yet become perfect. A lot of effort in software development is necessary in order that automatic layouts can compared with manual designs.

A two-dimensional channel routing program for hierarchical IC layout with orthogonal building blocks of variable size and shape is presented. A two dimensional channel model and a one layer channel router are used. A detailed description of the routing scheme which avoids the generation of “switch box” problems is given. The behavior of the two-dimensional routing algorithm to single and coupled channel intersections is demonstrated.

This paper presents a new algorithm for the initial placement of hierarchical VLSI circuits. The components to be placed are orthogonal macrocells of variable shape and size. This algorithm combines the advantages of force directed placement and min-cut algorithm. It provides an initial placement which avoids overlapping between cells and includes an estimation of routting area. This algorithm is suitable for regular cell arrangements, too.