This paper proposes a new heuristic algorithm for the building block compaction problem considering routing region. At first, we define generalized constraint graphs which are constructed by adding channel edges to the conventional constraint graphs, and by which we can estimate the chip area including routing region. Secondly, we describe an iterative improvement method based on the graphs. In this method blocks on the chip are successively compacted two dimensionally with considering the necessary channel width. Finally, experimental results are shown to compare our method with the previous method.

A new algorithm for timing driven placement based on the fuzzy theory is proposed. In this method, the signal delay on the longest path, the chip area and the total wire length can be simultaneously minimized. Introducing the probability measures of fuzzy events, falling down into the local optimal solutions can be avoided. At first, we define the fuzzy placement relation using the graph distance matrix and fuzzy distance relation matrix, and we give a new placement method based on the fuzzy placement relation and the probability measures of fuzzy events. Secondly, we extend this placement method so as to apply to the timing driven placement problem by introducing a fuzzy membership functions which represent the signal delay on the longest path and the chip area. Finally, experimental results are shown to compare our method with one of the previous methods.

This paper presents an efficient optimal block terminal assignment algorithm based on the integer programming for a data path synthesis. The problem is to assign buses to commutable terminals on functional units such that the number of buses is minimum, when the scheduling and allocation of operations and registers have been done. Three methods are used in the algorithm to decrease the amount of computation.

This paper deals with the wire length expressions using differentiable nonlinear functions, as a result they can be used in analytical placement methods. These expressions can be applicable to clique, bipartite-graph, and half-perimeter net models, and quadratic and Manhattan metrics to estimate the wire lengths.

In this research report a new VLSI block placement algorithm based on the Fuzzy theory is presented. The algorithm has such a feature that many factors related to the cost and performance of VLSI chips can be simultaneously considered. First, we explain the rules used to estimate the routes of wires. Using these rules the chip size containing the wiring space can be estimated. Then, three membership functions corresponding to the wire length and chip size are defined on the basis of the Fuzzy theory. Next, the Fuzzy inference space is introduced in order to determine the position of the VLSI blocks by using the membership functions, and a block placement algorithm using the Fuzzy inference is proposed. In the algorithm, the set of blocks is partitioned into subsets called piled blocks, the blocks in each subset are piled up from the bottom of the chip, and the piled blocks are arranged from the left side to the right side of the chip. In this placement process, Fuzzy inference is used as a criteria corresponding to the wire length and chip area to choose a candidate of block to be located. Experimental results are shown, and they are far superior to those obtained by other methods published in the literature so far.

A new timing driven placement method based on the fuzzy theory is proposed. In this method, the longest path delay, the chip area and the wire length can be simultaneously minimized. Introducing the probability measures of fuzzy events, falling down into the optimal solutions can be avoided.

This paper presents a mathematical formulation of a data path allocation and floorplanning problem using the mixed integer linear programming, and shows some experimental results. We assume that a data flow graph and the scheduled result are given in advance. The chip area and total wire length are used for the quality measures of the solution for the problem. This method is applied to some examples, and compared with the other method reported previously in the points of the solution and computation time.

We propose a new multiple folding algorithm for the gate matrix layout, and apply it to generation of rectangular blocks with flexible size. The algorithm consists of two phases, the net partitioning and the gate arangement, and both algorithms are based on the multi-way mini-cut technique. In the first and second phases, the width and height of the multiple folded gate matrix block are directly minimized, resperctively, such that the area is minimized and desired aspect ratio of the block is obtained. The features of the present algorithm are as hollows: (1) Dead space on the gate matrix block can be minimized, (2) the aspect ratio can be controlled finely, (3) since polar graphs are successfully used in the second phase, the efficiency of the algorithm can be much improved. The experimental results show the effectiveness of our algorithm.