I very much appreciate the honor given to me at this conference and wish to thank the organizers for their kindness. According to the preliminary program the invited talks include placement, routing, clock distribution, etc by well-known authors. Their contributions to the field have made a great impact to the advancement of physical design. Some of them are my former students. I want to thank all of them for coming to the beautiful city of Santa Barbara for this meeting. In addition there are other related areas which could have been included at this meeting. For example, floor-planning, timing and performance driven layout, the power and ground problem are all important areas which have been studied. Also, interconnect is certainly of current and future interest. The multi-dimensional problem which makes placement, routing more interesting. As technology advances active layers will provide more possibility for efficient design. We are now in the deep sub-micron stage, there are limitations as to what one can do. Also, nano-devices and circuits are within our reach. In essence, the field of Physical Design has enormous opportunity for researchers in universities and industry to make contributions. Collaborative efforts and joint work are needed to speed up the advances in this field. I am certain that these topics will be covered in future ISPD meetings. I look forward to seeing you and many others at the next meeting. Finally, many thanks to all the sponsors and especially to Prof. Yao-Wen Chang for inviting me.

To address the performance limitation brought by the scaling issues of on-chip global wires, a new configuration for global wiring using on-chip lossy transmission lines is proposed and optimized. We propose a signaling structure to compensate the distortion and attenuation of on-chip transmission lines, which uses passive compensation and inserts repeated transceivers composing sense amplifiers and inverter chains. An optimization flow for designing this scheme based on eye-diagram prediction and sequential quadratic programming (SQP) is devised. This flow is used to study the latency, power dissipation and throughput performance of the new global wiring scheme as the technology scales from 90 nm to 22 nm. Comparing to repeated RC wire, experimental results demonstrate that at 22 nm technology node, the new scheme can reduce the normalized delay by 80%-95%, the normalized energy consumption by 50%-94%. The normalized latency is 10 ps/mm, the energy per bit is 20 pJ/m, and the throughput is 15 Gbps/mum. All performance metrics are scalable with technology, which makes this approach a potential candidate to break the "interconnect wall" of digital system performance.

A low power passive equalizer using RL terminator is proposed and optimized in this work. The equalizer includes an inductor in series with the resistive terminator, which boosts high frequency components and therefore improves the interconnect bandwidth with little overhead on power consumption. An analytic estimation method for eye-opening and jitter based on tritonic step response is also introduced in this work, which enables the optimization procedure. Our experimental results show that our estimation method is accurate and a board level transmission line of 50cm wire length can achieve 15Gb/s data rate. With 15GHz frequency input, the power consumption of the equalizer is less than 2.5mW, and the total power is 5mW.

This paper introduces an accumulative prediction method to predict the eye diagram for high speed signaling systems. We use the step responses of pull-up and pull-down to extract the worst-case eye diagram, including the eye height and jitter. Furthermore, the method produces the input patterns of the worst-case intersymbol interference. The algorithm handles signals of either symmetric or asymmetric rise/fall time. Experimental results demonstrate the accuracy and efficiency of the proposed method.

In this paper, we introduce an efficient transistorlevel simulation tool with SPICE-accuracy for deepsubmicrometer very large-scale integration circuits with strong-coupling effects. The new approach uses multigrid for huge networks of power/ground, clock, and interconnect with strong coupling. Mutual inductance can be incorporated without error-prone matrix sparsification approximations or expensive matrix inversion. Transistor devices are integrated using a novel two-stage Newton–Raphson method to dynamically model the linear network and nonlinear devices boundary. Orders-ofmagnitude speedup over Berkeley SPICE3 is observed for sets of real deep-submicrometer design circuits.

In this paper, we introduce a general operator splitting method for transient simulation of VLSI circuits. The proposed approach generates special partitions of the circuits and alternates the explicit and implicit integrations between the partitions. We prove that the method is unconditionally stable independent of the step size. The splitting scheme greatly reduces the nonzero fill-ins generated in direct methods like LU decomposition. Orders of magnitude speedup over Berkeley SPICE3 is observed for sets of circuits.

In this paper, we introduce an efficient transistor level simulation tool with SPICE-accuracy for deep-submicron(DSM) VLSI circuits with strong coupling effects. The new approach uses multigrid for large networks of power/ground, clock and signal interconnect. Transistor devices are integrated using a novel two-stage Newton-Raphson method to dynamically model the linear network and nonlinear devices interface. Orders of magnitude speedup over Berkeley SPICE3 is observed for sets of DSM design circuits.

In today's deep submicron technology the coupling capacitances among individual on-chip RC trees have an essential effect on the signal delay and crosstalk, and the interconnects should be modeled as coupled RC trees. We provide simple explicit formulas for the Elmore delay and higher order voltage moments, and a linear order recursive algorithm for the voltage moment computation for lumped and distributed coupled RC trees. By using the formulas and algorithms, the moment matching method can be efficiently implemented to deal with delay and crosstalk estimation, model order reduction and optimal design of interconnects.

In today's deep submicrometer technology the coupling capacitances among individual on-chip RC trees have an essential effect on the signal delay and crosstalk, and the interconnects should be modeled as coupled RC trees. In this paper we provide simple exact explicit formulas for the Elmore delay and higher order voltage moments and a linear order recursive algorithm for the voltage moment computation for lumped and distributed coupled RC trees. By using the formulas and algorithms, the moment-matching method can be efficiently implemented to deal with delay and crosstalk estimation, model order reduction, and optimal design of interconnects. As an application of the algorithm, we provide a new efficient and accurate model for crosstalk estimation in coupled RC trees. Simulation results show it works better than existing methods.

In this paper, we present an approximation algorithm by linear programming(LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.

In this paper, we provide a new passive model order reduction algorithm on interconnects, which is based on the Chebyshev expansion of their impulse response. The Chebyshev coefficient matrices of the impulse response of the reduced order model up to a given order remain the same as those of the original network, so that the time domain transient response of the reduced order model matches that of the original network well. Compared with the model order reduction algorithms based on the frequency domain response, it is more efficient in dealing with complicated transient waveforms of interconnects where strong inductance effects are involved.

With the increase in signal speed and the development of process technology, distributed RC line model is found to be more suitable for on-chip interconnects than lumped RC model, especially for interconnects around and below 0.25 /spl mu/m. In this paper, we first describe a new explicit form for crosstalk approximation for coupled RC lines. Then we introduce a novel passive model order reduction technique for distributed RC lines. These two parts serve as two steps in static noise analysis of full on-chip interconnect networks called pruning process and static analysis process.

A new Chebyshev expansion based model for distributed interconnect networks is presented in this paper. Unlike the moment methods, this new model is optimal and it does not require the knowledge of expansion points. An automatic order selection scheme is also included in the new model. By using the integrated congruence transform, we guarantee the passivity of the new model for distributed interconnect networks. Because of the orthogonality of Chebyshev polynomials, the Modified Gram-Schmidt algorithm can be simplified. In the experimental examples, the new model is found to be accurate and efficient.

This paper presents a new performance-driven MCM router, named MRC, with special consideration of crosstalk reduction. Router MRC completes an initial routing with an adequate performance trade-off including wire length, vias, number of layers, timing and crosstalk. Then a crosstalk reduction algorithm is used to make the routing solution crosstalk-free without a significant influence on other routing performances. Thus, efficiently handling timing and crosstalk problems becomes the unique feature of MRC. Router MRC has been implemented and tested on MCM benchmarks and the experimental results are very promising.

In this paper, \ve provide a multipoint moment matching model for mult iport distributed interconnect net~vorks.We introd uce a ne~v concept: integratcd-congruence transform ~vhichcan be apphed to the partial differential equations of a distributed line and generate a passive finite order system as its model.Lloreover, ~vedso provide an efficient algorithm b~sed on the L2 Hilbert space theory so that exact moment matching at multiple points can be obtained.

This paper proposes a placement method for a mixed set of hard, soft, and pre-placed modules, based on a placement topology representation called sequence-pair. Under one sequence-pair, a convex optimization problem is efficiently formulated and solved to optimize the aspect ratios of the soft modules. The method is used in two ways: i) directly applied in simulated annealing to present the most exact placement method, ii) applied as a post process in an approximate placement method for faster computation. The performance of these two methods are reported using MCNC benchmark examples.

Article Free Access Share on Physical design: reminiscing and looking ahead Author: Ernest S. Kuh Department of Electrical Engineering, and Computer Sciences, University of California, Berkeley Department of Electrical Engineering, and Computer Sciences, University of California, BerkeleyView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997https://doi.org/10.1145/267665.267714Published:01 April 1997Publication History 4citation163DownloadsMetricsTotal Citations4Total Downloads163Last 12 Months7Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, we propose an efficient timing-driven global router, TIGER, for gate array and standard cell layout design. Unlike other conventional global routing techniques, interconnection delays are modeled and included during the routing and rerouting process in order to minimize the maximum channel density for gate arrays or the total track number for standard cells, as well as to satisfy the timing constraints in TIGER. The timing-driven global routing problem is formulated as a multiterminal, multicommodity network flow problem with integer flows under additional timing constraints. Two novel performance-driven Steiner tree algorithms are proposed to generate the initial global routing trees. A critical-path-based timing analysis method is used to guarantee the satisfaction of timing constraints. Experimental results based on MCNC (ISCAS) benchmarks show that TIGER can obtain better results than or comparable results with TimberWolf 5.6.

For the generation of a risk-free layout solution of a chip, crosstalk synthesis should be pursued at various stages in the routing process. This paper proposes a post global routing crosstalk optimization approach, which to our knowledge, is the first to estimate and reduce crosstalk risk at the global routing level. It consists of two parts: region-based crosstalk risk estimation and crosstalk risk reduction at the global routing level. In the first part, crosstalk risk graphs are first introduced for each routing region representing its current crosstalk situation. The crosstalk risk of each region, which indicates whether a risk-free routing solution of the region is possible, is then quantitatively defined and estimated using a graph-based approach. In the second part, the risk tolerance bound of each net is partitioned appropriately among its routing regions via integer linear programming for accurate (minimized) crosstalk risk estimation. If high risk regions still exist after bound partitioning, net ripping-up and rerouting is applied to reduce their crosstalk risks. At the end of the entire optimization process, a risk-free global routing solution is obtained together with partitions of nets' risk tolerance bounds which reflect the current crosstalk situation of the chip. These can greatly facilitate the generation of a risk-free final solution at later stages in the layout process. The proposed approach has been implemented and tested on CBL/NCSU benchmarks and the experimental results are very promising.

A genetic algorithm for building-block placement of ICs and MCMs is presented that simultaneously minimizes layout area and an Elmore-based estimate of the maximum path delay while trying to meet a target aspect ratio. Explicit design space exploration is performed by using a vector-valued, 3-dimensional cost function and searching for a set of distinct solutions representing the best trade-offs of the cost dimensions. From the output solutions, the designer can choose the solution with the preferred trade-off. In contrast to existing approaches, the required properties of the output solutions are specified without using weights or bounds. Consequently, the practical problems of specifying these quantities are eliminated. Promising experimental results are obtained for various placement problems, including a real-world design. Solution sets representing good, balanced cost trade-offs are found using a reasonable amount of runtime. Furthermore, the performance is shown to be comparable to that of simulated annealing in the special case of 1-dimensional optimization, in which direct comparison is possible.

In this paper, we propose a global routing algorithm for multi-layer building-block layouts. The algorithm is based on successive rip up and rerouting while satisfying edge capacity constraints as well as achieving higher routability and good routing flexibility. The initial solution consists of nets routed independently by the SERT-C algorithm which minimizes the Elmore delay at critical sink of a Steiner tree. Then, all the nets with the most congested edge, i.e., the edge with maximum flow, are ripped up and rerouted by using an iterative hierarchical approach. For each iteration, a window is specified according to the span of the ripped-up nets or an upper bound if the span is too large. Rerouting is done hierarchically within the window by using integer programming to optimize the flow uniformity. The algorithm terminates when the flow uniformity can not be further improved. The algorithm has been implemented and interfaced with a placement tool. Experiments show that the algorithm can improve the flow uniformity by 19% to 97%. The final results include the number of routing layers needed to complete the routing. Thus, the method is also useful in determining the required number of layers for pack aging design using multi-chip models.

In this paper we use the method of characteristics to derive a new simulation model of lossy transmission lines, and we present the sensitivity analysis in the time-domain. The simulation model is as fast as the recursive convolution model based on moment matching and Pade' approximation, but does not have the stability problem. The sensitivity analysis model is particularly useful for transmission line circuits containing nonlinear elements, and is believed to be the first time-domain model. Also we show that any nonlinear circuit element has a very simple linear model in sensitivity analysis. Furthermore, we demonstrate that for any circuits, the modified nodal admittance (MNA) matrices in simulation and in sensitivity analysis are the same, therefore no LU decomposition is needed in sensitivity analysis. The contributions in this paper have been implemented into a general-purpose program CSSC which shows excellent accuracy and efficiency in both simulation and sensitivity analysis of transmission line circuits.

Previous approaches for crosstalk synthesis often fail to achieve satisfactory results due to limited routing flexibility. Furthermore, the risk tolerance bounds partitioning problem critical for constrained optimization has not been adequately addressed. This paper presents the first approach for crosstalk risk estimation and reduction at the global (instead of detailed) routing level. It quantitatively defines and estimates the risk of each routing region using a graph-based optimization approach and globally adjusts routes of nets for risk reduction. At the end of the entire optimization process, a risk-free global routing solution is obtained together with partitions of nets' risk tolerance bounds which reflect the crosstalk situation of the chip. The proposed approach has been implemented and tested on CBL/NCSU benchmarks and the experimental results are very promising.

In this paper, we present new moment models for uniform, nonuniform and coupled transmission lines. The moment model of a line is based on the relationships between the two port currents (KCL) and the two port voltages (KVL) of the line. The parameters of the model depend on the mean values of the voltage moments and the weighted voltage moments of the line. Simple formulas are given to compute these mean values efficiently. By using such models and moment matching techniques, interconnects modeled as transmission line networks can be efficiently simulated. In addition, by using moment sensitivities, we demonstrate that wire sizing optimization can be carried out for layout design.

Most existing performance-driven and clock routing algorithms construct optimal routing topology for each net individually without considering its routability on the chip, so they can not guarantee performance after all nets are routed. This paper proposes a new approach for post routing performance optimization via multi-link insertion and non-uniform wiresizing, which improves the performance of a net topology obtained from a global routing solution. Unlike previous approaches, it can achieve reduction in both maximum delay and skew to satisfy user specified constraints and minimizes the routing resource consumed. During optimization, the topology of the net is kept routable. Experiments show that link insertion and wiresizing can improve net performance significantly, and among all approaches, multi-link insertion and wiresizing achieves the best performance and area efficiency.

This paper proposes one-dimensional spacing algorithms that minimize [maximize] the degree of separation [proximity] among the specified elements of a given integrated circuit layout. Number of problems on chip and MCM systems such as poor performance, higher crosstalk, lower yield etc. are related to the degree of separation [proximity]. The proposed algorithms utilize the attractive [repulsive] constraints to shrink [expand] the distances among the specified elements while keeping the layout free of any design rule errors. The spacing problem is reduced to a parametric linear programming problem and a network simplex algorithm is proposed for solving it. The proposed algorithms are implemented into a system called PERFECT for performance enhancement and crosstalk reduction. Given a routed design, PERFECT minimizes delay due to the coupled capacitance, which could contribute as much as 50-75% to the interconnect delay in near future. PERFECT utilizes the repulsive constraints between interconnect segments for the purpose. The experimental results show a significant delay improvement and the crosstalk reduction for submicron technologies.>

Moment matching methods are widely used in delay estimation of interconnects modeled as transmission line networks. In this paper, we analyze the contribution of a transmission line to the moments of a resistor-transmission line-capacitor (R-T-C) network and provide a method to form a lumped moment matching model of the line. When the transmission lines are replaced by their pth order moment matching models, the network is transformed into a lumped R-L-C network such that these two networks have identical moments up to the order of p for each corresponding output node voltage. We also provide a recursive formula to compute the moments of the R-L-C network so that the moment matching techniques can be efficiently used in the delay estimation.>

This paper presents two performance-driven Steiner tree algorithms or global routing which consider the

In this paper, we propose an eflicient timing-driven global routing algorithm.Unlike other conventional global routing techniques, interconnection delays

Rediscoveredand mathematically proved that a partitioning problem under timing and capacity constraints can be formulated exuctly as a Quadratic Boolean Programming Problem.'fMs new formulation allows arbitrary component sizes, arbitrary capacities of partitions, arbitrary interconnection costs and delay models between partitions.We then found a generalizatior@nhancementof Burkard's heuristic to efficiently solve the problem.Seven industrial circuits were used to compare our method against two other heuristics based on the traditional approach of component interchanges.Test results showed the superiority of our new method in terms of both solution quality and CPU usage,for problems under very tight Tirnhg and Capacity Constraints.

With the shrinking of feature size on silicon, the coupled capacitance between adjacent wires is contributing a significant factor to the interconnect delay, which already dominates the circuit performance. In the near future coupled capacitance could contribute as much as 50-75% to the interconnect delay which has been largely ignored by performance-oriented layout tools. Given a routed design, this work minimizes the delay and the peak cross-talk by re-adjusting the space between interconnects. It can reduce the circuit delay significantly and, in addition, reduce the peak cross-talk problem. An efficient technique based on the network simplex algorithm is used to solve the problem in the paradigm of compaction.

A circuit simulation technique based on a stepwise equivalent conductance model of a nonlinear resistive device is introduced. The major advantage of this technique is that it eliminates the need to employ Newton-Raphson iterations for the implicit integration. The technique, when applicable, is consistent, absolutely stable, and convergent. It is demonstrated that a second order of accuracy (the local truncation error for integration is of the cubic order of the time step used) is achieved by solving linear equations for each integration step. When applied to digital MOS circuits, the technique takes advantage of the fact that voltage waveforms can be modeled to a good approximation as piecewise-linear functions and thus provides further speedup in the simulation. The program, called SWEC, has been implemented, and has proved to be accurate and efficient on a large number of circuit examples. The results are compared with those for Relax2.3.iSPLICE3.0 XPsim. and SPECS2.>

An efficient algorithm, RITUAL (residual iterative technique for updating all Lagrange multipliers), for obtaining a placement of cell-based ICs subject to performance constraints is described. Using sophisticated mathematical techniques, one is able to solve large problems quickly and effectively. The algorithm is very simple and elegant, making it easy to implement. In addition, it yields very good results, as is shown on a set of real examples. The algorithm was tested on the ISCAS set of logic benchmark examples using parameters for 1 mu m CMOS technology. On average , there is a 25% improvement in the wire delay for these examples compared to TimberWolf-5.6 with a small impact on the chip area.>

An algorithm is presented for assigning off-chip I/O pads for a logic circuit. The technique, which is based on the analysis of the circuit structure and path delay constraints, uses linear placement, goal-programming, linear-sum assignment and I/O pad clustering to assign locations to I/O pads. The I/O pad assignment is then used by placement tools. Experimental data show that as a result of using the I/O pad assignment procedure, the total interconnection length and circuit delay (after placement and routing) are reduced by 8-15% and 3-4%, respectively. This technique is general and can handle I/O pad assignment prior to logic synthesis or detailed placement procedures.>

In this paper we focus on routing techniques for opti-mizing clock signals in small-cell (e.g., standard-cell, sea-of gate, etc...) ASICs. In previously reported work, the routin P of the clock net has been ordinary g obal routing techniques base a” erformed using on a minimum or minimal Steiner tree that have little under-of clock routing problems. We F resent a novel to clock routing that all but e rminates clock yields excellent phase delay results for a wide range of chip sizes, net sizes (pin count), minimum fea-ture sizes, and pin distributions on both randomly cre-ated and standard industrial benchmarks. For certain classes of pin distributions we have proven theoretically and observed exnerimentallv a decrease in skew with an increase in net Bize. In practice, we have observed a two to three order magnitude reduction in skew when compared to a minimum rectilinear spanning tree.

This paper presents a heuristic approach to the optimal selection of standard cells in VLSI circuit design. We are considering a cell library composed of several templates (3-5) for each type of cell. These templates differ in area, driving capabilities, intrinsic delay, and capacitive loading. When realizing a logically synthesized circuit, we select the best templates from the cell library to minimize the total area of the cells under delay constraints. We have found a very successful heuristic approach to attack this discrete optimization problem.

An algorithm was developed for the placement of small-cell ICs subject to performance constraints that is efficient in terms of speed and memory usage. The approach models wirelength using a nonlinear cost function similar to that of R.S. Tsay et al. (1988) and a timing model which uses a block-oriented representation of paths like that of M.A.B. Jackson and E.S. Kuh (1989). The timing constraints are implicitly represented using a network and nonlinear programming techniques are used to solve the wirelength minimization problem while satisfying the constraints. This allows critical paths to dynamically adjust while the placement changes to minimize wirelength. The solution of the nonlinear programming problem yields an initial placement of cells that may violate slot constraints. The authors propose hierarchical solution techniques to resolve the slot constraints. By exploiting structure inherent in the formulation, a large reduction is achieved in the number of variables that represent the problem. Additionally, developing special techniques to take advantage of the interaction between the timing model and the physical position of the cells enabled the authors to achieve a speed-up of 10-15 times over Jackson and Kuh (1989) even with a crude implementation of the algorithm.>

A hierarchical technique is presented for floorplanning and pin assignment of general cell layouts. Given a set of cells with their shape lists, a layout aspect ratio, relative positions of the external I/O pads and upper bound delay constraints for a set of critical nets, the authors determine shapes and positions of the cells, locations of the floating pins on cells and a global routing solution such that a linear combination of the layout area, the total interconnection length and constraint violations for critical nets is minimized. Floorplanning, pin assignment and global routing influence one another during the hierarchical steps of the algorithm. The pin assignment algorithm is flexible and allows various user specified constraints such as pre-specified pin locations, feedthrough pins, length-critical nets and planar net topologies. Placement, timing and floorplanning results for a Xerox general cell benchmark are reported.>

The current status of VLSI layout and directions for future research are addressed, with emphasis on the authors' own work. Necessary terminology and definitions and, whenever possible, a precise formulation of the problems are provided. Placement and floorplanning for both the sea-of-gates and building-block designs are examined. The former emphasizes the connectivity specification, whereas the latter must also consider module shape and size. Global routing based on a method of successive cuts on a chip is discussed. This is a hierarchical top-down approach that is useful for both of the above designs. A two-dimensional detailed routing problem and the rip-up and rerouting problem are also discussed. The field of computational geometry and its application to layout-in particular, to gridless routing and compaction-are reviewed, and layout engines are considered.>

In a recent work of the authors (1987), a simulation-based directed search approach for generating test vectors for combinational circuits was proposed. In this method, the search for a test vector is guided by a cost function computed by the simulator. Event-driven simulation deals with circuit delays in a very natural manner. Signal controllability information required for the cost function is incorporated in a new form of logic model called the threshold-value model. These concepts are extended to meet the needs of sequential circuit test generation. Such extensions include handling of unknown values, analysis of feedback loops, and analysis of race conditions in the threshold-value model. A threshold-value sequential test generation program, TVSET, is implemented. It automatically initializes the circuit and generates race-free tests for synchronous and asynchronous circuits.>

The increasingly important role of the interconnect in the timing performance of present and future integrated circuit technologies underscores the need to reconsider conventional physical design CAD tools, and devise new ways to influence performance during layout. Interconnects are not perfect conductors, they introduce parasitic elements that load the logic gates and distort the temporal properties of the design as viewed by the logic designer. Cell placement that minimizes wirelength as the sole objective does not solve the problem, leaving a margin for performance improvement that has not been fully exploited. This paper presents a novel approach to performance-driven placement, combining timing analysis and physical design to dynamically optimize the performance of the chip during placement. The ideas are embodied in a program named Allegro, and preliminary results tested on Sea-of-Gate designs are encouraging.

Placement and related aspects of the BEAR macrocell layout system are described. A combination of top-down and bottom-up heuristics is used to make best use of a hierarchical description. The interdependency of placement and routing is considered explicitly. Experimental results show a considerable improvement over previous approaches.>

Dynamic layout representation is a key problem in developing a building block layout system. We have unified topological and geometrical representations, and developed efficient methods to update topological information after geometrical operations. The experimental results are very promising. This representation is the key for information flow in BEAR — a new building block layout system being developed at U. C. Berkeley.

A new algorithm for channel spacing is discussed in this paper. In contrast to existing compaction algorithms, we rely on the geometric method and bypass the constraint graph during the whole spacing process.

A new methodology for hierarchical floor planning and global routing for building block layout is presented. Unlike the traditional approach, which separates placement and global routing into two consecutive stages, our approach accomplishes both jobs simultaneously in a hierarchical fashion. The global routing problem is formulated at each level as a series of the minimum Steiner tree problem in a special class of partial 3-trees, which can be solved optimally in linear time. The floor planner with a maximum of five rooms per level has been implemented in the C language, running on a VAX 8650 under 4.3 BSD UNIX. The experimental results on examples with a large number of irregular blocks show that our approach out-performs other well-known deterministic algorithms, and gives results that are comparable to random-based algorithms but with a computing time an order of magnitude less. Due to the unique goal-oriented and pattern-directed features of our floor planner, it accepts specifications for overall aspect ratio and I/O pad positions, thus making our approach suitable for hierarchical design.

In the traditional approach to channel routing, terminals must be located on grid points and wire segments must be placed on grid lines. Without using the grids, we can take advantage of the two interconnection layers with variable wire width and spacing. Terminals are no longer required to be on grids, and nets may even have different wire widths. The new gridless approach which we propose is based on design rules. The objective is to minimize the routing area, while keeping the constraints of wire widths and spacing satisfied. This router is also capable of handling channels with irregular boundaries, and cyclic constraints. The algorithm has been implemented in C language, and will be integrated into our BBL (Berkeley Building-Block Layout) system.

We present a new routing region definition and ordering (RRDO) scheme for building block layout. Given an arbitrary placement of rectangular blocks (including the case with cycles in the channel precedence constraints), without modifying the placement, our scheme defines and orders channels so that when a new channel is being routed, its width can be expanded or contracted without destroying the previously routed channels. The cycles in the channel precedence constraints are broken by introducing a new kind of channel--the L-shaped channels. Unlike switchboxes, L-shaped channels can be expanded or contracted to permit the completion of routing without rerouting other existing channels. An efficient greedy RRDO algorithm has been implemented, which tries to generate as few L-shaped channels as possible since L-shaped channels are harder to route than straight channels. Our algorithm represents routing regions by a floor plan graph, for which we provide a precise definition and a construction algorithm. The experimental results of the RRDO algorithm are promising.

A new constructive placement and partitioning method based on resistive network optimization is proposed. The objective function used is the sum of the squared wire length. The method has the feature which includes fixed modules in the formulation. The overall algorithm comprises the following subprograms: optimization, scaling, relaxation, partitioning and assignment. The method is efficient because it takes advantage of net-list sparsity and has a complexity of O[n1.4 log n]. Another added special feature is that irregular-size modules within cell rows are allowed. Thus the method is particularly useful in standard-cell and gate-array designs. Experimental results on four 4K gate-array placements are illustrated, and they are far superior than manual placements.

In this paper, we present a heuristic algorithm for single-row routing. Our approach is based on the interval graphical representation of the given net list. The objective function for minimization is the street congestion. The problem is known to be intractable in the sense of NP-completeness, thus a polynomial-time heuristic algorithm is proposed. It has been implemented and tested with various examples. So far it has always produced optimal solutions.

This paper deals with the layering problem of multilayer PWB wiring, associated with single-row routing. The problem to be considered is restricted to the special case of street capacities up to two in each layer, and it is reduced to a problem of the interval graph by relaxing some restrictions in the original problem. Then, a heuristic algorithm is proposed for this problem.

Abstract Problems on layout for ICs (integrated circuits) and PCBs (printed circuit boards) are usually solved by heuristic approaches because they are complex. This article considers a special problem of double‐row planar routing. The problem represents a generalization of the permutation layout problem to which estimation of bounds and some algorithms have been proposed recently. Our approach is based on the interval graphical representation introduced in the single‐row single‐layer PCB problem. The objective function for minimization is the breadth of the realization, i.e., the total number of vertical tracks required to realize a given net list specified in terms of terminals on two parallel rows. The problem is shown to be intractable in the sense of NP‐completeness; however, a polynomial‐time heuristic algorithm is proposed. An upper bound for the breadth for an initial solution is given. Iterative improvement is next used. The algorithm has been programmed in FORTRAN and ran on the VAX 11/780 computer.

In the layout design of LSI chips, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two-layer channel. Nets are routed with horizontal segments on one layer and vertical segments on the other. Connections between two layers are made through via holes. Two new algorithms are proposed. These algorithms merge nets instead of assigning horizontal tracks to individual nets. The algorithms were coded in Fortran and implemented on a VAX 11/780 computer. Experimental results are quite encouraging. Both programs generated optimal solutions in 6 out of 8 cases, using examples in previously published papers. The computation times of the algorithms for a typical channel (300 terminals, 70 nets) are 1.0 and 2.1 s, respectively.

The problem of single-row routing has its origin in the design of multilayer printed circuit board. It has been shown that the problem can be reduced to an ordering problem by using a novel interval graphical representation. Criteria for optimum single-row routing for the purpose of minimizing the street congestion have been obtained. Extensions of the single-row routing problem can be made in several directions. In particular, the problem of double-row routing can be formulated in a similar fashion. A solution is given; and, furthermore it is demonstrated that the problem is directly related to the problem of channel routing in polycell layout.

This paper gives a graph-theoretic approach to the design of one-dimensional logic gate arrays using MOS or I/sup 2/L units. The incidence relation between gates and nets is represented by a graph H = (V, E), and a possible layout of gates and nets is characterized by an interval graph H = (V,E O F), where F is called an augmentation. It is shown that the number of tracks required for between-gate wiring is equal to the clique number (chromatic number) of H, and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be an NP-complete problem. Instead a polynomial-time algorithm for finding a minimal augmentation is presented, where an augmentation is minimal if no proper subset of it is an augmentation. An algorithm for gate sequencing with respect to a given augmentation is also presented.