This paper presents a heuristic floorplanning method that improves the method proposed by Vijayan and Tsay. It is based on tentative insertion of constraints, that intentionally produces redundant constraints to make it possible to search in a wide range of solution space. The proposed method can reduce the total area of blocks with the removal and insertion of constraints on the critical path in both horizontal and vertical constraint graphs. Experimental results for MCNC benchmarks showed that the quality of solutions of the proposed method is better than [7],[8] by about 15% on average, and even for the large number of blocks, the proposed method keeps the high quality of solutions.

This paper presents an efficient heuristic algorithm for min-cut bisection of weighted hypergraphs. The proposed algorithm is based on a heuristic algorithm proposed by Kahng, which was devised for non-weighted hypergraph bisection, adopting a non-weighted graph called intersection graph to represent a given hypergraph. In the proposed algorithm, instead of an intersection graph, a bipartite graph called netgraph is newly introduced to explicitly represent the weights of nodes of a hypergraph. Using the netgraph, it is easy to partition a weighted hypergraph into two hypergraphs with same size. Computation time of the proposed method is O(m2), where m is the number of nodes of a given hypergraph. Experimental results with real circuit data show that the proposed method produces better solutions in shorter computation time compared with existing methods.

In this paper, we propose a floorplanning method for VLSI building block layout. The proposed method produces a floorplan under the timing constraint for a given netlist. To evaluate the wiring delay, the proposed method estimates the global routing cost for each net with buffer insertion and wire sizing. The slicing structure is adopted to represent a floorplan, and the Elmore delay model is used to estimate the wiring delay. The proposed method is based on simulated annealing. To shorten the computation time, a table look-up method is adopted to calculate the wiring delay. Experimental results show that the proposed algorithm performs well for producing satisfactory floorplans for industrial data.

This paper presents a new timing-driven global routing method for standard cell layout. The proposed method can explicitly consider the timing constraint between two registers and minimize the channel density under the given timing constraint. In the proposed method, first, we determine the initial global routes. Next, we improve the global routes to satisfy the timing constraint between two registers as well as to minimize the channel density. Finally, for each cell row, the nets incident to terminals on the cell row are assigned to channels to minimize the channel density using 0-1 integer linear programming. We also show the experimental results of the proposed method implemented on an engineering workstation. Experimental results show that the proposed method is quite promising.

The graph bisection problem is to partition a given graph into two subgraphs with equal size with minimizing the cutsize. This problem is NP-hard, and hence several heuristic algorithms have been proposed. Among them, the Kernighan-Lin algorithm and the Fiduccia-Mattheyses algorithm are well known, and widely used in practical applications. Since those algorithms are iterative improvement algorithms, in which the current solution is iteratively improved by interchanging a pair of two nodes belonging to different subgraphs, or moving one node from one subgraph to the other, those algorithms tend to fall into a local optimum. In this paper, we present a heuristic algorithm based on subgraph migration to avoid falling into a local optimum. In this algorithm, an initial solution is given, and it is improved by moving a subgraph, which is effective to reduce the cutsize. The algorithm repeats this operation until no further improvement can be achieved. Finally, the balance of the bisection is restored by moving nodes to get a final solution. Experimental results show that the proposed algorithm gets better solutions than the Kernighan-Lin and Fiduccia-Mattheyses algorithms.

This paper presents a three layer over-the-cell (OTC) routing algorithm for standard cells with nonuniform OTC routing capacities in standard cell design. Since the number of available routing tracks on the second metal layer of OTC varies column by column, the proposed OTC routing method can effectively utilize the OTC regions. The proposed router performs two types of OTC routing. For the OTC regions near the channel, it performs planar routing. For the OTC regions far from the channel, it performs H-V routing on the second and third layers. Combining planar and H-V routings, the router can utilize the OTC effectively, that could hardly be achieved by existing algorithms. We also formulate the problem of selecting planar routable nets on the third layer as the maximum weighted planar routable net selection problem with nonuniform routing capacity, and propose an optimal algorithm. Experimental results show that the proposed router produces small height layouts as compared to those produced by the routers based on the existing cell model with uniform OTC routing capacity.

A new parallel merge algorithm suitable for VLSI implementation is proposed. This algorithm can merge a given set of sorted sequences in O (N) computation time, where N is a total number of keys in input sequences, and it works on a linear array of simple identical processors.

This paper presents a timing-driven iterative improvement circuit partitioning algorithm under path delay constraints for the general delay model. The proposed algorithm is an extension of the Fiduccia & Mattheyses (FM) method so as to handle path delay constraints and consists of the clustering and iterative improvement phases. In the first phase, we reduce the size of a given circuit, with a new clustering algorithm to obtain a partition in a short computation time. Next, the iterative improvement phase based on the FM method is applied, and then a new path-based timing violation removal algorithm is also performed so as to remove all the timing violations. From experimental results for ISCAS89 benchmarks, we have demonstrated that the proposed algorithm can produce the partitions which mostly satisfy the timing constraints.

The great technological progress in very large scale integration (VLSI) of electronic circuits has made it possible to implement a large distributed computing system on a single VLSI chip. Distributed algorithms suited for VLSI implementation are generally called 'VLSI algorithms', and many VLSI algorithms have been devised for solving several kinds of problems. This paper discusses a VLSI algorithm for pattern matching. We propose a new VLSI-oriented pattern matching algorithm in which regular expressions are adopted to represent a pattern. The proposed algorithm will be implemented on a configurable multi-processor system, which can dynamically change its interconnections among the processors according to the external inputs. Thus the pattern may be arbitrarily changed after the chip fabrication. We call such an algorithm the 'programmable' pattern matching machine (PPM for short). The programmability makes it possible for PPM to have wide applications which the previously known algorithms could hardly have. PPM consists of n(n1)/2 processors, where n is the length of a pattern, and can recognize a string of length m in m (independent of n) clock periods. PPM also has preferable properties, such as a regular structure and a simple control mechanism, for VLSI implementation.

This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.

This paper presents a timing-driven global routing algorithm based on coarse pin assignment, block reshaping, and positioning for VLSI building block layout. As opposed to conventional approaches, we combine pin assignment and global routing problems into one problem. The proposed algorithm determines global routes, coarse pin assignments, and block shapes and positions so as to minimize the chip area and total wire length of nets under the given timing constraints. It is based on an iterative improvement paradigm and performs rip-up and rerouting, block reshaping, and positioning in the manner of simulated evolution taking shapes of soft blocks and routing congestion into consideration until the solution is not further improved. The Elmore delay model is adopted for the interconnection delay model. Experimental results show the effectiveness of the proposed algorithm.

Multi-FPGA systems, which consist of multiple FPGAs and a printed circuit board connecting them, are useful and important tools for prototyping large scale circuits, including SoCs. In this paper, we propose a method for optimizing inter-FPGA signal transmission to accelerate the system frequency of multi-FPGA prototyping systems and shorten prototyping time. Compared with the number of I/O pins of an FPGA, the number of I/O signals between FPGAs usually becomes very large. Thus, time-multiplexed I/Os are used to resolve the problem. On the other hand, they introduce large delays to inter-FPGA I/O signals, and much lower the system frequency. To reduce the degradation of the system frequency, we have proposed a method for optimally selecting signals to be time-multiplexed and signals not to be time-multiplexed. However, this method assumes that there exist physical connections (i.e., wires on the printed circuit board) between every pair of FPGAs, and cannot handle I/O signals between a pair of FPGAs that have no physical connections between them. Thus, in this paper, we propose a method for obtaining indirect inter-FPGA routes for such I/O signals, and then combine the indirect routing method and the time-multiplexed signal selection method to realize effective time-multiplexing of inter-FPGA I/O signals on systems with various topologies.