As very large scale integration technology scales to deep submicron, design for interconnections becomes increasingly challenging. The traditional bus routing follows a sequential bit-by-bit order, and few works explicitly target interbit regularity for signal groups via multilayer topology selection. To overcome these limitations, we present Streak, an efficient framework that combines topology generation and wire synthesis with a global view of optimization and constrained metal layer track resource allocation. In the framework, an identification stage decomposes binding groups into a set of representative objects; with the generated backbones, equivalent topologies are accompanied by the bits in every object; then a formulation guides the routing considering wire congestion and design regularity. Furthermore, a bottom-up clustering methodology based on layer prediction targets to enhance the routability; a post-refinement stage is developed to match the source-to-sink distance deviation among bits in one group. Experimental results using industrial benchmarks demonstrate the effectiveness of the proposed technique.

As very large scale integration technology scales to deep submicrometer and beyond, interconnect delay greatly limits the circuit performance. The traditional 2-D global routing and subsequent net by net assignment of available empty tracks on various layers lacks a global view for timing optimization. To overcome the limitation, this paper presents a timing driven incremental layer assignment tool, to reassign layers among routing segments of critical nets and noncritical nets. Lagrangian relaxation techniques are proposed to iteratively provide consistent layer/via assignments. Modeling via min-cost flow for layer shuffling avoids using integer programming and yet guarantees integer solutions via uni-modular property of the inherent model. In addition, multiprocessing of K × K partitions of the whole chip provides runtime speed up. Furthermore, a slew targeted optimization is presented to reduce the number of violations incrementally through iteration-based Lagrangian relaxation, followed by a post greedy algorithm to fix local violations. Certain parameters introduced in the models provide tradeoff between timing optimization and via count. Experimental results in both ISPD 2008 and industry benchmark suites demonstrate the effectiveness of the proposed incremental algorithms.

As VLSI technology scales to deep sub-micron, design for interconnections becomes increasingly challenging. The traditional bus routing follows a sequential bit-by-bit order, and few works explicitly target inter-bit regularity for signal groups via multilayer topology selection. To overcome these limitations, we present Streak, an efficient framework that combines topology generation and wire synthesis with a global view of optimization and constrained metal layer track resource allocation. In the framework, an identification stage decomposes binding groups into a set of representative objects; with the generated backbones, equivalent topologies are accompanied by the bits in every object; then a formulation guides the routing considering wire congestion and design regularity. Experimental results using industrial benchmarks demonstrate the effectiveness of the proposed technique.

Modern technologies provide wide and thick metal layers that must be wisely used to reduce the delay of critical interconnections. After global routing, incremental layer assignment can improve the circuit timing by properly selecting critical interconnect segments to be routed in the faster (but very limited) wires on upper layers. Existing techniques based on net-by-net iterative improvement may get stuck at locally-optimal solutions depending on net ordering. Recent techniques rule out such drawback through the simultaneous iterative improvement of all nets, but they unfortunately rely on objective functions that may guide the optimization off critical paths. As opposed to all reported techniques, which rely on simplified, overly pessimistic timing models, this paper proposes the decoupling of incremental layer assignment from the timing analysis and the exploitation of flow conservation conditions so as to enable the use of an external signoff timing engine. The novel technique was experimentally compared with two state-of-the art works, leading to 50% less timing violations under total negative slack metric and 35% less timing violations under worst negative slack metric with similar overhead in number of vias.

With VLSI technology nodes scaling into the nanometer regime, interconnect delay plays an increasingly critical role in timing. For layer assignment, most works deal with via counts or total net delays, ignoring critical paths of each net and resulting in potential timing issues. In this article, we propose an incremental layer assignment framework targeting delay optimization in timing the critical path of each net. A set of novel techniques are presented: self-adaptive quadruple partition based on K × K division benefits the runtime; semidefinite programming is utilized for each partition; and the sequential mapping algorithm guarantees integer solutions while satisfying edge capacities; additionally, concurrent mapping offers a global view of assignment and post delay optimization reduces the path timing violations. The effectiveness of our work is verified by ISPD’08 benchmarks.

With VLSI technology nodes scaling into nanometer regime, interconnect delay plays an increasingly critical role in timing. For layer assignment, most works deal with via counts or total net delays, ignoring critical paths of each net and resulting in potential timing issues. In this paper we propose an incremental layer assignment framework targeting at delay optimization for critical path of each net. A set of novel techniques are presented: self-adaptive quadruple partition based on KxK division benefits the run-time; semidefinite programming is utilized for each partition; post mapping algorithm guarantees integer solutions while satisfying edge capacities. The effectiveness of our work is verified by ISPD'08 benchmarks.

As VLSI technology scales to deep submicron and beyond, interconnect delay greatly limits the circuit performance. The traditional 2D global routing and subsequent net by net assignment of available empty tracks on various layers lacks a global view for timing optimization. To overcome the limitation, this paper presents a timing driven incremental layer assignment tool, TILA, to reassign layers among routing segments of critical nets and non-critical nets. Lagrangian relaxation techniques are proposed to iteratively provide consistent layer/via assignments. Modeling via min-cost flow for layer shuffling avoids using integer programming and yet guarantees integer solutions via uni-modular property of the inherent model. In addition, multiprocessing of K × K partitions of the whole chip provides run time speed up. Certain parameters introduced in the models provide trade-off between timing optimization and via count. Experimental results in both ISPD'08 and industry benchmark suites demonstrate the effectiveness of the proposed incremental algorithms.

In this paper, we propose a new global router, BOB-Router, endowed with the ability to use over-the-block routing resources to the greatest extent in addition to traditional routing concepts of minimizing wirelength, via count and overflow. In previous global routing formulations, the routing resources over the IP blocks were either dealt as routing blockages leading to a significant waste, or simply treated in the same way as outside-the-block routing resources, which violates the slew constraints and thus fail buffering. Utilizing over-the-block routing resources could dramatically improve the routing solution, yet requires special attention, since the slew, affected by different RC on different metal layers, must be constrained by buffering and is easily violated. Moreover, even all nets are slew-legalized, the routing solution could still suffer from heavy congestion problem. For the first time, BOB-Router tries to solve the over-the-block global routing problem through minimizing overflows, wirelength and via count simultaneously without violating slew constraints. BOB-Router generates a slew-legalized initial solution followed by a Lagrangian-multiplier-based pricing phase and RC-constrained A* search to help explore new buffering-aware topologies on all metal layers. Our experimental results show that BOB-Router completely satisfies the slew constraints and significantly outperforms the obstacle-avoiding global routers in terms of wirelength, via count and overflows.

In this paper, we study an often overlooked but very important and practical problem of building Buffering-aware Over-the-Block rectilinear Steiner minimum tree (BOB-RSMT). In most previous works, the routing resources over the IP blocks were simply treated as routing blockages, resulting in significant waste of routing resources on higher metal layers not utilized by internal intra-block routing. On the other hand, routing over large IP blocks needs special attention as there is no way to insert buffers inside hard IP blocks, which can lead to unresolvable slew/timing violations. In this paper, we propose a novel BOB-RSMT algorithm which helps reclaim the "wasted" over-the-block routing resources while meeting user-specified slew constraints. Our algorithm incrementally and efficiently migrates initial tree structures with buffering-awareness to meet slew constraints while minimizing wire length. It can handle complex blocks including rectilinear shapes. Our experiments on various benchmarks demonstrate very promising results. By utilizing over-the-block routing resources intelligently, we can save the outside-block wire length as well as the total wire length significantly compared with the conventional obstacle-avoiding rectilinear Steiner minimum tree (OA-RSMT) algorithms. BOB-RSMT also reduces the repeater count/area needed to satisfy slew constraints, which is very important for modern design closure.

The traditional repeater insertion in an integrated circuit (IC) is aimed at eliminating cycle (setup) time violations at the worst process corner. Subsequently, special measures are adopted to remedy hold-time violations identified at the best process corner. However, aggressive delay reduction for fixing setup time violations could introduce new hold-time violations that did not exist before. Designers are usually un-ware of these newly created hold-time violations as they do not compare hold-time violations pre and post repeater insertion. However, identifying these nets and rerunning them with the presented technique to deal with hold time requirements can reduce the number of repeaters and design turn-around time. The power vs. delay trade-off technique presented is found to be extremely useful in limiting the number of repeaters to an acceptable limit. Concurrent treatment of setup time and hold time helps in better timing convergence for the affected nets by avoiding creation of new violations. Satisfying a minimum and a maximum slews along with accurate RC and gate timing models helps attain good timing correlation/convergence with a static timer.

Article Free Access Share on A new time-domain macromodel for transient simulation of uniform/nonuniform multiconductor transmission-line interconnections Authors: Monjurul Haque University of Iowa, Iowa City, IA University of Iowa, Iowa City, IAView Profile , Ali El-Zein IBM, Poughkeepsie, NY and University of Iowa, Iowa City, IA IBM, Poughkeepsie, NY and University of Iowa, Iowa City, IAView Profile , S. Chowdhury Motorola, Austin, TX and University of Iowa, Iowa City, IA Motorola, Austin, TX and University of Iowa, Iowa City, IAView Profile Authors Info & Claims DAC '94: Proceedings of the 31st annual Design Automation ConferenceJune 1994 Pages 628–633https://doi.org/10.1145/196244.196596Published:06 June 1994Publication History 4citation219DownloadsMetricsTotal Citations4Total Downloads219Last 12 Months3Last 6 weeks2 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

This paper extends the time-domain modal analysis for simulating transmission lines to include lossy coupled systems of arbitrary geometries. It provides exact solution for the case where the dielectric medium is homogeneous and an approximate one for the case of an inhomogeneous medium. A numerical example is given, illustrating the accuracy of the proposed method.>

A method of characteristics solution of a nonuniform transmission line having frequency-dependent per-unit-length parameters is formulated. The method, in general, requires the use of FFT to incorporate the frequency-dependent components of the distributed parameters in the time-domain equations. For skin-effect frequency-dependence, an analytical technique to avoid the use of FFT is presented. Also, a formula for estimating the discretization error is given.>

A method for computing the moments of a nonuniformly distributed RLGC element is presented. A recursive formula for the evaluation of moments of hybrid parameters, characterizing the distributed element, is derived from the spectral method solution of a system of ordinary differential equations.>

Article Free Access Share on Analysis and reliable design of ECL circuits with distributed RLC interconnections Authors: Monjurul Haque View Profile , S. Chowdhury View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 697–701https://doi.org/10.1145/157485.165095Online:01 July 1993Publication History 0citation306DownloadsMetricsTotal Citations0Total Downloads306Last 12 Months0Last 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 SiteeReaderPDF

The crosstalk in a system containing n(n>or=2) lossless microstrip transmission lines is formulated as a linear function in time. The maximum crosstalk is computed by evaluating the crosstalk at certain breakpoints in time. The technique also provides the pattern (rising or falling) of input voltages and their relative delays for which the maximum crosstalk occurs. This pattern is usually determined by the system parameters. Since the maximum crosstalk determines the faulty vs fault-free operation, the pattern found could be used for testing integrated logic circuits during the design stage.>