Yield-preferred via insertion is an effective method to reduce the yield loss caused by via failures. The existing methods to apply the redundant-cut vias in metal layers are not efficient nor adequate. In this paper, we present an effective and efficient yield-preferred via insertion method based on a novel geotopological layout platform, GEOTOP. Our method chooses the most yield-favored via candidate and insert it into the layout without causing any design rule violations. Experiments with real industry designs show that our method can achieve very high rate of yield-preferred via without increasing the design die size within acceptable running time

This paper presents a cost-effective area-IO DRAM (aDRAM)/Logic integration implemented with CLC (Chip-Laminate-Chip)-based System-in-a-Package (SiP) technology. By inserting 512 area-IOs into the area-IO DRAM, the bandwidth of the area-IO DRAM can achieve 10GB/s when working under 166MHz. An interface module with configurable IO width was also developed to make this implementation platform able to be adapted by various applications. A performance analysis, including bandwidth and power is also presented in this paper. It is demonstrated that area-IO DRAM/Logic integration with SiP technology provides significant cost-effective implementation methodology compared with embedded DRAM and off-chip DRAM.

This paper proposes an innovative domain-specific cell based ASIC design flow to narrow the performance gap between the full custom ASIC design method and conventional standard-cell based ASIC design method. The flow can improve the design performance and still preserve the efficiency of the standard ASIC design flow. Targeting on digital signal processing applications, a domain-specific cell library is provided to augment of standard cell libraries. Experimental results of designing macros such as FFT, FIR etc. are shown in the paper. Based on this methodology a 64-tap FFT can achieve up to 24X performance improvement, with the power/spl times/delay/spl times/area (PDA) criteria, over the conventional designed ASICs.

This paper deals with area minimization of power network for very large-scale integration designs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. During the optimization, a penalty method, conjugate gradient method, circuit sensitivity analysis, and merging adjoint networks are applied, which enables the algorithm to optimize large circuits. The experiment results prove that this algorithm is robust and can achieve the objective of minimizing the area of power network in a short runtime.

Post-layout is an important stage in the modern very large scale integration (VLSI) design. In this stage, the extraction and verification tools can get the most accurate results with the complete layout information, and the layout problems can be detected precisely for further design improvements or optimizations. But the problem is that the design optimization is very hard to perform in post-layout. Every design modification is under tight geometry constraints. Usually the designer either changes layout manually by layout editor, or goes back to previous placement or routing stage in order to have the preferred results. How to modify the layout becomes a bottleneck in the post-layout optimization. In this paper, we propose a new method to resolve this problem called the triangulation encoding graph (TEG) method. Based on an improved topological layout representation and a set of layout operation algorithms, TEG provides an incremental layout modification environment for post-layout optimizations. Experimental results show that TEG is efficient and effective in processing industry VLSI designs.

One of the main challenges in developing an effective crosstalk noise management strategy is to develop a crosstalk noise estimate which is both accurate and leads to a tractable optimization problem that can be used to optimally redistribute uncommitted routing resources to resolve crosstalk noise violations. Devgan's [4] estimate comes very close to meeting these objectives, however, it is extremely pessimistic for nets with long couplings or aggressor nets with short rise times. The increased complexity of more sophisticated estimates, such as that proposed by Vittal et. al. [13] lead to a crosstalk management problem that is very hard to solve. In this paper we develop two estimates, similar in form to Devgan's estimate, that are based on local approximations of Vittal's estimate. Our estimates are substantially more accurate than Devgan's estimate while still allowing us to formulate the crosstalk management problem in a form that can be solved efficiently.

Post-layout is an important stage in modern VLSI design. With the completed detail routing, it is the only stage where extraction and verification tools can get accurate results for further optimization. But the problem is that design optimization or modification is very hard to perform in the post-layout stage, because most layout elements are under tight geometry constraints due to the routing. In this paper we propose a new method to resolve this problem, named TEG. Based on an improved topological layout representation and a set of layout operation algorithms, TEG provides an incremental layout modification environment for post-layout applications. Experimental results showed TEG was efficient and effective in processing industry VLSI designs.

On-chip inductance extraction is difficult due to the global effect of inductance, and simulating the resulting dense partial inductance matrix is even more difficult. Furthermore, it is well known that simply discarding smallest terms to sparsify the inductance matrix can render the partial inductance matrix indefinite and result in an unstable circuit model. Recently a new circuit element, K , has been introduced to capture global effect of inductance by evaluating a corresponding sparse K matrix [1]. However, the reason that K has such local properties is not clear, and the positive semi-definiteness of the corresponding sparse K matrix is not proved. In this paper, we present the physical interpretation of K. Based on the physical interpretation, we explain why the faraway mutual K can be ignored (locality) and prove that after ignoring faraway mutual K ,the resultant K matrix is positive definite (stability). Together with a RKC equivalent circuit model, the locality and stability enables us to simulate RKC circuit directly and efficiently for real circuits. A new circuit simulation tool, KSim, has been developed by incorporating the new circuit element K into Berkeley SPICE. The RKC simulation matches better with the full partial inductance matrix simulation with significant less computing time and memory usage, compared to other proposed methods, such as shift-truncate method [2, 3].

Aggressive technology scaling will push us into a 50nm regime within a decade. Most entries in current ITRS for the technology node are painted out in red, indicating "No know solutions". In the physical implementation domain, we are facing severe challenges in various aspects such as interconnect performance degradation, signal integrity, reliability, manufacturing variability, etc. These challenges will continue to grow for the future. In this panel, our panelists will present their own view of the most difficult challenges in the 50nm regime, and possible solutions to break through the red brick wall as well, followed by a live discussion on the approaches we should take for successful 50nm physical implementation.

A mixed potential integral equation (MPIE) technique combined with fast multi-layer Green's functions and Gaussian Jacobi high order techniques is used to compute the 3-D frequency dependent inductances and resistances in lossy multi-layered substrates. Compared to FastHenry, a multipole-accelerated 3-D inductance extraction program, the algorithm presented here is more accurate and faster for lossy multi-layer structures for two reasons. First, substrate and optional ground plane loss and coupling effect are efficiently modeled by multilayer Green's functions, while the Green's functions are efficiently calculated via a window-based acceleration technique. Second, Gaussian Jacobi-based high order techniques are used to capture the singularity of the current distribution at metal edges, leading to significant reduction of problem size and speed-up of computation.

This paper deals with area minimization of power distribution networks for VLSIs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. Experimental results prove that this algorithm has achieved the objectives of minimizing the area of power/ground networks with higher speeds.

Abstract|In this paper, a fast eÆcient Method of Moments(MoM) based on a new subdomain par-titioning technique is presented for rapidly extract-ing the distributed capacitance and inductance of spiral inductors. By using this approach, the an-alytical formula of Green's function for multi-layer substrates is obtained through the prioritized wave-tracing method. The computing time is much faster than the state of art capacitance and inductance solvers, such as FMMS[6]. Good agreement between numerical results and measurement data is shown to demonstrate the accuracy of the proposed new method. I.

Abstract | A eld-programmable multi-chip mod-ule containing one ORCA 3T/125 FPGA and 4 MByte DRAM was built using chip-on-chip technology. Mod-ule architecture and physical design issues are pre-sented. A PCI board consisting of four chip-on-chip modules is also built as the test vehivle. The design environment for this multi-chip module, including vi-sual or C++ design entry and bit-serial datapath syn-thesis system, is also discussed. Some ongoing ap-proaches, like double-\nip technology and area IO are also addressed.

This paper describes C++ class library and bit-serial datapath synthesis algorithm designed to support variable-precision computation on reconfigurable hardware in adaptive computing systems (ACSs). The enhanced synthesis system compiles C++ design entries into smaller datapath circuits with the shorter latencies compared to the fixed-precision bit-serial circuits.

On-chip inductance extraction and analysis is becoming increasing critical. Inductance extraction can be difficult, cumbersome and impractical on large designs as inductance depends on the current return path-which is typically unknown prior to extracting and simulating the circuit model. In this paper we propose a new circuit element, K, to model inductance effects, at the same time being easier to extract and analyze. K is defined as inverse of partial inductance matrix L, and has locality and sparsity normally associated with a capacitance matrix. We propose to capture inductance effects by directly extracting and simulating K, instead of partial inductance, leading to much more efficient procedure which is amenable to full chip extraction. This proposed approach has been verified through several simulation results.

In thii paper we propose a new, and effective, approach to cross-talk noise avoidance routing.In our new approach we attack the cross-talk noise problem immediately following topological routing, which is the point in the routing process that gives the best trade off between the ability to detect cross-talk noise problems and the ability to correct the problems.We formulate the heart of this new approach as a convex, nonlinear, mathematical programming problem which determines an optimal set of wire spacings under cross-talk noise constraints.This new mathematical programming formulation is based on a detailed knowledge of the underlying cross-talk noise mechanisms and accounts for coupling capacitance, interconnect resistance, and aggressor net signal rise time on nets with arbitrarily complex tree topologies.Finally, by slightly restricting this programming problem we formulate it as a linearly constrained, convex, nonlinesr, mathematical program which can be quickly and efficiently solved using sequential quadratic programming.

In tegral equation approaches based on layered media Green's functions are often used to extract models of integrated circuit structures. The primary advan tage of these approaches over equiv alen t-sourcebased schemes is the dramatic reduction in problem size. When combined with an SVD-accelerated sc heme for the solution of the associated dense linear system, this leads to a substantial speedup.

Based on the sequence pair structure [1], this paper pr~ poses a novel method to represent arbitrary shaped rectilinear blocks.The necessmy and sufficient conditions are derived such that non-overlapped packing of arbitrary rectilinear blocks can rdw'aysbe guaranteed regardl~s of the dimensions of the blocks.A stochastic search is applied, three sequence pair operations are defined to search the fewible solution space both continuously and exhaustively.Theo retied results derived in this paper sho~v that an optimal solution can always be reachable through finite steps of the stochastic search.As such, the algorithm becom~a significant breakthrough in the general packing problem both theoretically and practically.search is applied on the optimization of convex block packing.L& cal moves are defined to search the feasible solution space both continuously and exhaustively.

In this paper, we formulate the problem of top olo gy constrained rectiline ar blo ck packing in la yout reuse. A specific class of rectilinear shaped blocks, ordered convex r ectiline ar blo cks, is represen ted in bounded slicing grid (BSG) structure. The Non-overlapped pac king is guaranteed. Based on both sequence pair (SP) and BSG structures, w e propose an algorithm to compact the ordered con vexbloc ks under the topological constrain ts, in whic hthe x and y directions are independently compacted. By augumenting or further partitioning the arbitrary rectilinear blocks in to the ordered con vexshapes, this method can be extended to handle the topology constrained rectilinear block pac king. Furthermore, our recent theoretical progress is briefly reported at the end of this paper, in which arbitrarily rectilinear shaped blocks are represented in SP structure. Three necessary and sufficient constrain ts are deriv ed on the sequence pair, such that the non-overlapping compaction is guaranteed.

In this paper, we present our datapath synthesis and layout tools which are targeted toward large-scale configurable systems with the logic capacity of up to millions of gates which consists of an easy design entry using C++, customized bit-serial circuit library for SRAM-based FPGAs, bit-serial pipeline circuit generator, and a circuit partitioner.

A new method of non-slicing floorplanning is proposed, which is based on the new representation for non-slicing floorplans, called bounded slicing grid (BSG) structure. We developed a new greedy algorithm based on the BSG structure, running in linear time, to select the alternative shape for each soft block so as to minimize the overall area for general floorplan, including non-slicing structures. We propose a new stochastic optimization method, named genetic simulated annealing (GSA) for general floorplanning. Based on BSG structure, we extend SA-based local search and GA-based global crossover to L-shaped, T-shaped blocks and obtain high density packing of rectilinear blocks.

In was projected by the National TechnologyRoadmap for Semiconductors that by the year 1998 thefeature size will shrink to 0.25μm and the chips maycontain as many as 28 million transistors.As the widthof wires shrinks, resistance increases more rapidly thancapacitance decreases.As the result, interconnect contributes50% of total delay in 0.35μm technology andis expected to contribute up to 70% in 0.25μm.Interconnectdelay on chip dominates the gate delay.Largeheight to width ratio, 2:1 in 1998 and 2.5:1 in 2001,and many interconnect layers, 5-8 in 1998 and 8-10 in2001, make lateral coupling increasingly more significantthan coupling to ground.Cross talk not only causes awrong logic result on one particular clock cycle, but alsoleads to a different timing behavior of neighboring lines.Delay cannot be calculated accurately without takingcross talk into account.Not to mention conformal dielectricsand non-orthogonal conductor cross sections.The above technology shift calls for 3D parasitic extraction.However, it is prohibitively expensive to extractevery net in 3D; in fact, it is not necessary to do so.Beforepresenting the multi-tiered extraction methodology,I will first classify various extracion methodologies.

As devices and lines shrink into the deep submicron range, the propagation delay of signals can be effectively improved by repowering the signals using intermediate buffers placed within the routing trees. Almost no existing timing driven floorplanning and placement approaches consider the option of buffer insertion. As such, they may exclude solutions, particularly early in the design process, with smaller overall area and better routability. In this paper, we propose a new methodology in which buffered trees are used to estimate wire delay during floorplanning. Instead of treating delay as one of the objectives, as done by the majority of previous work, we formulate the problem in terms of delay bounded buffered trees (DBB-tree) and propose an efficient algorithm to construct a DBB spanning tree for use during floorplanning. Experimental results show that the algorithm is very effective. Using buffer insertion at the floorplanning stage yields significantly better solutions in terms of both chip area and total wire length.

The paper presents a unique approach to improve yield given a routed layout. Currently after routing has been completed and compacted, it generally proceeds to verification without further modifications. However, to improve manufacturability, the authors introduce a concept called even wire distribution, a key element of the SURF physical design tool. To alleviate congestion, they first move vias and wires towards less dense areas in a manner which preserves the existing wiring paths. Depending on the locally available area, they then increase wire spacing to reduce defect sensitivity, without changing the area of the design. Carafe, an inductive fault analysis tool is used to evaluate the new layout.

Measured Equation of Invariance(MEI) is a new concept in computational electromagnetics.It has been demonstrated that the MEI technique can be used to terminate the meshes very close to the object boundary and still strictly preserves the sparsity of the FD equations.Therefore, the nal system matrix encountered by MEI is a sparse matrix with size similar to that of integral equation methods.However, complicated Green's function and disagreeable Sommerfeld integrals make the traditional MEI very dicult, if not impossible, to be applied to analyze multilayer and multiconductor interconnects.In this paper, we propose the Geometry Independent MEI(GIMEI) which substantially improved the original MEI method.We use GIMEI for capacitance extraction of general three-dimension VLSI interconnect.Numerical results are i n g o o d agreement with published data and those obtained by using FASTCAP [1], while GIMEI is generally an order of magnitude faster than FASTCAP and uses signi cant less memory than FAST-CAP.

Instead of zero-skew or assuming a fixed skew bound, we seek to produce useful skews in clock routing. This is motivated by the fact that negative skew may allow a larger timing budget for gate sizing. We construct a useful-skew tree (UST) such that the total clock and logic power (measured as a cost function) is minimized. Given a required clock period and feasible gate sizes, a set of negative and positive skew bounds are generated. The allowable skews within these bounds and feasible gate sizes form the feasible solution space of our problem. We use a merging segment perturbation procedure and a simulated annealing approach to explore various tree configurations. This is complemented by a bi-partitioning heuristic to generate appropriate connection topology and take advantage of useful skews. Experimental results have shown 11% to 22% total power reduction over previous methods of clock routing with zero-skew or single fixed skew bound and separately sizing logic gates.

Developing applications for a large-scale configurable system composed of state-of-the-art FPGA technology is a grand challenge. FPGAs are inherently resource limited devices in terms of logic, routing, and IO. Without a careful circuit implementation strategy, one would waste a large portion of the potential capacity of the configurable hardware. Also, high-level design entry support is essential for such large-scale hardware. A C++ design tool has been implemented which maps the computational algorithms onto bit-serial pipeline networks which exhibit high performance and maximize the device utilization of each FPGA. With this tool, the designer is able to develop applications in a very short time, and also is able to try out different algorithm implementations easily to see the trade-offs in terms of performance and hardware size instantaneously. Based on this C++ design tool, a number of DSP applications such as 1D and 2D filters, adaptive filters, Inverse Discrete Cosine Transform, and digital neural networks were designed.

No abstract available.

In this paper, we present a new capacitance extraction method named Dimension Reduction Technique (DRT) for 3D VLSI interconnects. The DRT converts a complex 3D problem into a series of cascading simple 2D problems. Each 3D problem is solved separately, so we can choose the most efficient method according to the arrangement of conductors. More importantly, it is very easy to obtain the analytical solutions of 2D problem in many layers such as the pure dielectric layers and the layers with parallel signal lines. Therefore, the domain that has to be analyzed numerically is minimized. This leads to the drastic reduction of the computing time and memory needs. We have used the DRT to extract the capacitances of multilayered and multiconductor cross-overs, bends, via with signal lines and open-end. The results are in good agreement with those of Ansoft's SPICELINK and MIT's FastCap, but the computing time and memory size used by the DRT are several even tens times less than those used by SPICELINK and FastCap.

Due to process, manufacturing and system operating conditions in a real environment, clock jitter is inevitable. In the presence of jitter, zero or near-zero skew are not really safe for reliable clock operations. Appropriate skew or useful skew can serve as a safety margin to guard against clock jitter. In two-phase clocking, the nonoverlapping interval of two-phase clocks provides an additional degree of freedom to improve either the clock tree cost or jitter-tolerance. We construct a two-phase jitter-tolerant useful-skew tree (JT-UST) such that the susceptibility to clock jitter and the clock tree cost is minimized. Following the Deferred-Merge Embedding (DME) framework, we use a simulated annealing approach to explore the routing topologies and embeddings. Experimental results have shown 63% to 100% reduction of jitter-prone sink pairs over previous clock routing methods while having very comparable clock tree costs.

Many practical routing problems such as BGA, PGA, pin redistribution and test fixture routing involve routing with interchangeable pins. These routing problems, especially package layout, are becoming more difficult to do manually due to increasing speed and I/O. Currently, no commercial or university router is available for this task. In this paper, we unify these different problems as instances of the interchangeable pin routing (IPR) problem, which is NP-complete. By representing the solution space with flows in a triangulated routing network instead of grids, we developed a min-cost max-flow heuristic considering only the most important cuts in the design. The heuristic handles multiple layers, prerouted nets, and all-angle, octilinear or rectilinear wiring styles. Experiments show that the heuristic is very effective on most practical examples. It had been used to route industry designs with thousands of interchangeable pins.

To achieve path delay balance, instead of making faster paths slower by elongating wires used in most zero skew clock routing methods, we make slower paths faster by the wire sizing. The wire sizing technique is frequently used by IC designers to minimize the clock skew caused by the unbalanced RC delays and transmission line noises. However, manual sizing takes a long time and lacks accurate relationship between the timing and wire widths. This paper formulates the optimal clock sizing problem and proposes a sizing optimization algorithm based on Gauss-Marquardt's least square minimization method. The minimum skew is achieved by this method due to its uphill mechanism of searching the global minimum by selecting a proper Lagrange multiplier dynamically at each iteration. The optimization is guided by the delay calculation based on a distributed RLC interconnect model which takes into the account the nonnegligible inductance in high-speed long interconnects (such as on the substrate of a multichip module). The algorithm and delay model can handle a general clock network including loops such as a clock mesh. For testing examples of equal path length clock trees, this algorithm can further achieve 10/spl times/ skew reduction and 14% path delay reduction after the sizing.

A new concept of chip and package co-design for the clock network is presented in this paper. We propose a two level clock distribution scheme which partitions the clock network into two levels. First, the clock terminals are partitioned into a set of clusters. For each cluster, a local on-chip clock tree is used to distribute the clock signal from a locally inserted buffer to terminals inside this cluster. The clock signal is then distributed from the main clock driver to each of local buffers by means of a global clock tree, which is a planar tree with equal path lengths. With the flip chip area I/O attachment, the planar global clock tree can be put on a dedicated package layer. The interconnect on the package layer has two to four order smaller resistance than that on the chip layer. The main contribution of this paper is a novel algorithm to construct a planar clock tree with equal path lengths-the length of the path from the clock source to each destination is exactly the same. In addition, the path length from the source to destinations is minimized.

No abstract available.

Article Buffer insertion and sizing under process variations for low power clock distribution Share on Authors: Joe G. Xi National Semiconductor, Corp., Santa Clara, CA and Computer Engineering, University of California, Santa Cruz, Santa Cruz, CA National Semiconductor, Corp., Santa Clara, CA and Computer Engineering, University of California, Santa Cruz, Santa Cruz, CAView Profile , Wayne W. M. Dai Computer Engineering, University of California, Santa Cruz, Santa Cruz, CA Computer Engineering, University of California, Santa Cruz, Santa Cruz, CAView Profile Authors Info & Claims DAC '95: Proceedings of the 32nd annual ACM/IEEE Design Automation ConferenceJanuary 1995 Pages 491–496https://doi.org/10.1145/217474.217576Online:01 January 1995Publication History 54citation550DownloadsMetricsTotal Citations54Total Downloads550Last 12 Months3Last 6 weeks0 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 SiteGet Access

Field�programmable hardware exhibits a new trend to� wards computation�intensive applications. The basic idea is to completely customize the hardware architec�

Area-IO provide a way to eliminate the IO bottleneck of field programmable logic devices (FPLDs) created the mismatch between the ability of perimeter bonds to provide IO and and the propensity of logic to demand it. Whether the incorporation of area IO into FPLD architectures has undesirable side effects is a question that has not yet been answered. In this paper, we examine the architectural impact of area-IO on FPLDs from a theoretical and experimental standpoint and show that the introduction of area IO generally improves the routability and delay of a set of benchmark circuits. 1 1 Introduction The application of area-IO to Field Programmable Logic Devices (FPLDs) originally stemmed from our work on Field Programmable Multi-Chip Modules (FPMCM).[DGI + 94] In this section we introduce areaIO and present reasons why area-IO are desirable even in the context of single-chip FPLDs. We then propose a specific area-IO architecture whose characteristics will be the subject the remain...

This paper presents a linear time algorithm to reduce a large RC interconnect network into subnetworks which are approximated with lower order equivalent RC circuits. The number of RC elements can be reduced between 50% and 90%. Instead of increasing approximation order for a network with large number of ports which will result in inefficiency at best and ill-conditioned matrices at worst, we partition the original network into several subnetworks, each of which is approximated by lower order model. The reduced circuits are guaranteed to be stable. The experiment results show that the number of circuit elements in a reduced network is O(N) for typical clock networks, where N is the number of external ports. The simulation time can be reduced by two to three orders of magnitude while the response of the reduced circuits is within five percent of that of the original circuits.

Fanout routing for Ball Grid Array (BGA) packages becomes non-trivial when the I/O pin count increases. When the number of I/Os gets larger and larger, the number of I/Os we can put on a package may not be limited by the available area but sometimes by the ability to fan them out on the next level of interconnect-the PCB or MCM substrate. This paper presents an efficient algorithm (EVENFANOUT) which generates the optimal uniform distribution of wires. We have found the three cuts that is decisive on the routability of the package using EVENFANOUT. These decisive cuts form the base for design optimization of the package.

This paper describes two novel macromodels for incorporating the single and coupled transmission lines characterized by the frequency-dependent losses into a scattering-parameter (S-parameter) macromodel based simulator. This approach computes the moments of the S-parameter based upon the frequency-dependent parasitic functions: R(f), L(f), C(f), and G(f) which characterize either the single or the coupled transmission lines. These same moments can be used later to construct the macromodels. Once the macromodels are built, the transient analysis can be performed by using the S-parameter based macromodel simulator.

This paper describes a new approach to find a tighter bound of the transformation of the min-max problems into the one of least-square estimation. It is well known that the above transformation of one problem to the other can lead to the proof that their target functions linearly bound each other. However, this linear bound is not a tight one. In this paper, we prove that if we transform the min-max problem into two least-square estimation problems, where one minimizes the root-mean-square (RMS) of the original function and the other one minimizes the RMS of the difference between the original function and an arbitrary constant, one can obtain a tighter bound between their target functions. The tighter bound given by this new approach depends on the outcome of the second least-square estimation problem, so there is a great incentive to choose the arbitrary constant which gives the smallest RMS of the second least-square estimation problem. For a problem with a large number of variables, this new tighter bound can be two to three order tighter than the old one.

This paper presents a simple and robust method of designing the lossy-transmission-line interconnects for multichip modules (MCM). This method uses wire-sizing to meet the electrical damping criteria to propagate high-speed signals through unterminated lossy transmission lines on the substrates of multichip modules. Based on an improved scattering-parameters (S-parameters) macro-model of transmission lines, wire-sizing optimal design method relates the layout parameter (line width) and the transfer function (damping ratio, and natural undamped frequency) to the signal propagation delay. The optimal design method results in fast and stable signal propagation for single-source multi-receiver networks on multichip modules without using termination resistors.>

A Scattering-Parameters {S-Parameters) based macromodel of distributed-lumped networks is presented.The networb can include capacitive cutsets, inductive loops, RLC meshes, and lossy transmission lines.An ef)cienl network

To achieve delay balance, instead of making the faster path slower by elongating branches, we make slower paths faster by sizing. Given a general clock network, which may includes loops, together with a set of feasible widths for each branch, we formulate the optimal sizing of the clock network as a constrained optimization problem. By turning the skew minimization problem into a least-squares estimation problem, a modified Gauss-Marquardt's method is used to determine the optimal widths. An efficient initial sizing algorithm is proposed to speed up the sizing process. Instead of using zero-order delay model (path length) or one-order delay model (Elmore delay), we employ a generalized delay model which can handle general RLC and transmission line networks. Experimental results show that this method significantly reduces both the clock skew and path delays from source to terminals.

In the design of high speed digital VLSI circuits, it is preferable that the clock net be routed on the metal layer with the smallest RC delay. This strategy not only avoids the difficulties of having different electrical parameters on different layers, but also eliminates the delay and attenuation of the clock signal through vias. The clock phase-delay is also decreased. An algorithm, based on max-min optimization, to construct a planar clock tree which can be embedded on a single metal layer is presented. The clock tree achieves equal path lengths, i.e., the lengths of the paths from the clock source to each clock terminal are exactly the same. In addition, the path length from the source to clock terminals is minimized. Some examples including industrial benchmarks have been tested, and the results are promising.>

4 multi-layer topological router for generating rubberband sketches is described.The router uses hierarchical top-down partitioning to perform global routing for all nets The local router uses a region connectivity graph to generate shortest-path rubber-band routing.

The SURF routing system employs a grid-less flexible

A novel methodology and efficient algorithms are presented for performance driven routing based on computational geometry. A dynamic data representation using constrained triangulation is the key to achieving the efficient routability testing and incremental updating of topological routing. Variable width, variable spacing, evenly distributed spacing and thermal via insertion are used to handle crosstalk, switching noise, and thermal resistance problems.>

Hierarchical placement and floorplanning algorithms for rectangular blocks are described and implemented as part of the BEAR building block layout system developed at the University of California at Berkeley. The algorithm combines the goal orientation of top-down approaches with the block orientation of bottom-up techniques. The result is a meet-in-the-middle strategy. It considers the mutual dependency between placement and routing explicitly by incorporating a novel method of hierarchical routing area estimation. If the layout includes flexible blocks, the placement result can be further optimized by resizing these blocks subject to constraints on their areas and aspect ratios. Placement and floorplanning are refined more and more (with possible topological change) as routing proceeds. Global routing is updated incrementally to eliminate the need for iterations between placement and routing, thus achieving a more uniform design flow.>

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 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.

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.