Thermal optimization plays a crucial role in the design of advanced systems in package. Due to the large number of thermal simulations needed for full design space exploration, reductions in simulation run-time are critical. Here, we propose a data-driven approach to physics simulation by using neural networks (NNs) to cast the temperature solution process into an image-to-image translation problem. We first model the power generation map, conductivity map, and boundary conditions (BCs) into separate channels of an image. We then generate temperature solutions by training a generative adversarial network, composed of a U-Net shaped generator and a discriminator. The resultant NN model can handle diverse thermal simulation scenarios with accuracy. More importantly, our model can handle BCs, power maps, and physical package designs which are unseen during the training. Experiments show that speed wise, it enables near real-time design, providing a$2581\times $and$9171\times $speedup over a custom sparse matrix optimized finite element method and ABAQUS, respectively. Comparisons with state-of-the-art methods have demonstrated the accuracy, efficiency, and versatility of the proposed work.

The concept of minimum cycle mean (MCM) in a directed graph has many applications in the design of circuits and systems. The algorithm by Young, Tarjan, and Orlin (YTO), when implemented with a binary heap, has been reported to be the fastest MCM algorithm in practice even when it has higher asymptotic time complexity than Karp’s algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp’s algorithm can also be memory hungry, thereby limiting its application to only small size problems. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp’s algorithm to improve its runtime performance. The early termination also allows memory to be allocated on an on-demand basis, which can reduce the memory requirement of Karp’s algorithm. In our evaluation based on graphs constructed from IWLS 2005 benchmark circuits and randomly generated graphs, we empirically observe that the HO algorithm (or Karp’s algorithm with early termination technique from the HO algorithm) has much less memory usage than YTO, but it lags behind YTO in runtime performance. We propose several improvements to the early termination technique of the HO algorithm. While further improving its memory advantage over YTO, we significantly improve the runtime performance of the HO algorithm to the extent that the proposed algorithm has runtime performance that is comparable to YTO for circuit-based graphs and for dense randomly generated graphs.

Timing violations in high performance communication channels in system-on-chips (SoC) may occur in the late stages of the physical design process. To address that, latency insensitive systems (LISs) employ pipelining in the communication channels through the insertion of relay stations. Although the functionality of an LIS is robust with respect to the communication latencies, imbalances in relay station insertion may degrade the throughput of the system. While having a large number of buffer queues can eliminate such performance loss, the system may not have adequate area to accommodate these buffers. The problem of buffer queue sizing for maximizing throughput while meeting buffer area constraints has been solved using a mixed-integer linear program (MILP) formulation; however, such an approach is not scalable. In this work, we formulate the buffer queue sizing problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use a minimum cycle mean algorithm to determine from which edges buffers can be removed safely. Experimental results on large LISs suggest that the proposed approach is scalable. Moreover, quality of the solutions, in terms of the throughput and the size of buffer queues, is observed to be as good as that of the MILP-based approach.

Clock trees can be constructed based on static arrival time constraints or dynamic implied skew constraints. Dynamic implied skew constraints allow the full timing margins to be utilized. However, the dynamic skew constraints require a high run-time complexity to be evaluated. In contrast, static arrival time constraints are more restrictive but can be evaluated in constant time. Consequently, there is a tradeoff between timing margin utilization and run-time. In this paper, a scalable clock tree synthesis (CTS) framework is proposed for the construction of low-cost useful skew trees (USTs) with high timing quality. The scalability is based on combining the use of arrival time constraints with virtual minimum and maximum delay offsets, which facilitates that a pair of smaller subtrees can be joined into a larger subtree in constant time. The ability to quickly join subtrees is leveraged to perform a high degree of solution space exploration, which translates into the construction of USTs with low-cost. In particular, clock trees with various routing tree topologies, buffer tree topologies, buffer sizes, and stem wire lengths are explored. Moreover, the arrival time constraints are specified with the objective of being the least restrictive to reduce cost. Furthermore, the constraints are respecified throughout the tree construction process using a slack graph (SG) to expose additional timing margins. The high timing quality is obtained by seamlessly integrating arbitrary timing models using the SG. Finally, the proposed CTS framework is integrated with a clock tree optimization framework to demonstrate that the constructed USTs are capable of meeting timing constraints under the influence of on-chip variations.

The clock network of a circuit is a main contributor to the power consumption of any ASIC design. A key technique that is used to reduce power consumption is to cluster flipflops or latches into groups and to place each group of flipflops close together to reduce the clock wire length. In this paper, we introduce a clock tree synthesis methodology that incorporates clustering with a previously published useful-skew clock tree synthesis technique to minimize the clock wire length. The clustering process is guided by bounded arrival time constraints, which enable its efficiency. Experimental results show that the proposed methodology reduces up to 34% of the total power consumption while meeting all timing constraints.

This paper addresses a delay-driven layer assignment problem with consideration of via delay and coupling effect in the global routing stage. A negotiation-based framework is proposed to balance delay, congestion, and via count. Coupling capacitance is considered using a probabilistic look-up table. Finally, the proposed algorithm uses both parallel wires and wide wires to reduce wire delay. The effectiveness of our layer assignment algorithm is supported by extensive experimental results.

CoFlow scheduling improves data-intensive application performance by improving their networking performance. State-of-the-art CoFlow schedulers in essence approximate the classic online Shortest-Job-First (SJF) scheduling, designed for a single CPU, in a distributed setting, with no coordination among how the flows of a CoFlow at individual ports are scheduled, and as a result suffer two performance drawbacks: (1) The flows of a CoFlow may suffer the out-of-sync problem -- they may be scheduled at different times and become drifting apart, negatively affecting the CoFlow completion time (CCT); (2) FIFO scheduling of flows at each port bears no notion of SJF, leading to suboptimal CCT.

There are striking differences between constructing clock trees based on dynamic implied skew constraints and based on static arrival time constraints. Dynamic implied skew constraints allow the full timing margins to be utilized, but the constraints are required to be updated (with high time complexity). In contrast, static arrival time constraints are decoupled and are not required to be updated. Therefore, the constraints can be obtained in constant time, which facilitates the exploration of various tree topologies. On the other hand, arrival time constraints do not allow the full timing margins to be utilized. Consequently, there is a trade-off between topology exploration and timing margin utilization. In this paper, the advantages of static arrival time constraints are leveraged to construct clock trees with useful skew while exploring various tree topologies. Moreover, the constraints are specified and respecified throughout the synthesis process reduce the cost of the constructed clock trees. It is experimentally demonstrated that the proposed approach results in clock trees with 16% lower average capacitive cost compared with clock trees constructed based on dynamic implied skew constraints.

Modern clock networks are required to operate in multiple corners and in multiple modes (MCMM). An initially constructed clock tree may contain different timing violations in different mode and corner combinations. Clock tree optimization (CTO) is employed to remove these timing violations. We propose a CTO framework based on slack redistribution using a reduced slack graph. The main idea is to reduce the MCMM problem to an equivalent single-corner single-mode (SCSM) problem using delay adjustment linearization. Using the equivalent SCSM problem, a linear program is solved to determine a set of delay adjustments to remove the timing violations. Next, the delay adjustments are realized using feasible delay adjustment ranges. The experimental results show that the proposed framework obtains average reductions of 84% and 83% in the total negative slack and the worst negative slack, respectively, at the expense of a 4% capacitive overhead.

Clock trees must be constructed to function even under the influence of on-chip variations (OCV). Bounding the latency of a clock tree, i.e., the maximum delay from the tree root to any sequential element, is important because the latency correlates with the maximum magnitude of the skews caused by OCV. In this paper, a latency constraint graph (LCG) that captures the latencies of a set of subtrees and the skew constraints between the subtrees is introduced. The minimum latency of a clock tree that can be constructed from the corresponding subtrees is equal to the (negative of the) length of a shortest path in the LCG, which can be computed in $O(VE)$. Based on the LCG, we propose a framework that consists of a latency-aware clock tree synthesis (CTS) phase and a clock tree optimization (CTO) phase to construct latency-bounded clock trees. When applied to a set of synthesized circuits, the framework is capable of constructing latency-bounded clock trees that have higher yield compared to clock trees constructed in previous studies.

The clock networks of many modern circuits have to operate in multiple corners and multiple modes (MCMM). We propose to construct mode-reconfigurable clock trees (MRCTs) based on mode separation and scenario compression. The technique of scenario compression is proposed to consider the timing constraints in multiple scenarios at the same time, compressing the MCMM problem into an equivalent single-corner multiple-mode (SCMM), or single-corner single-mode (SCSM) problem. The compression is performed by combining the skew constraints of the different scenarios in skew constraint graphs based on delay linearization and dominating skew constraints. An MRCT consists of several clock trees and mode separation involves, depending on the active mode, selecting one of the clock trees to deliver the clock signal. To limit the overhead, the bottom part (closer to the clock sinks) of all the different clock trees are shared and only the top part (closer to the clock source) of the clock network is mode reconfigurable. The reconfiguration is realized using OR-gates and a one-input-multiple-output demultiplexer. The experimental results show that for a set of synthesized MCMM circuits, with 715 to 13, 216 sequential elements, the proposed approach can achieve high yield.

Previous studies on human-pose estimation (HPE) rely on the design of factors to represent underlying probability distributions that model human poses. However, designing those factors manually is laborious. Moreover, manually designed factors might not represent underlying probability distributions properly. In this paper, we utilize feedforward neural networks (NNs) to design factors of our previous work on HPE and build an NN-based HPE system. We first propose a mapping that converts a Bayesian network to a feedforward NN. Then, the system is built based on the proposed mapping that consists of two steps: 1) structure identification and 2) parameter learning. In the structure identification, we develop a bottom-up approach to build a feedforward NN while preserving a Bayesian-network structure. In the parameter learning, we create a part-based approach to learn synaptic weights by decomposing a feedforward NN into parts. Using the proposed mapping, our previous work of an action-mixture model (AMM) for HPE is converted to a feedforward NN called NN-AMM. Based on the concept of distributed representation, NN-AMM is further modified to a scalable feedforward NN called NND-AMM. The NN-based HPE system is then built by using viewpoint-and-shape-feature-histogram features extracted from 3-D-point-cloud input and NND-AMM to estimate 3-D human poses. The results showed that the proposed mapping could design AMM factors automatically. NND-AMM could provide more accurate human-pose estimates with fewer hidden neurons than both AMM and NN-AMM could. Both NN-AMM and NND-AMM could adapt to different types of input, showing the adaptability of using feedforward NNs to design factors.

Incorporating timing constraints explicitly imposed by the data and control paths during clock network synthesis can enhance the robustness of the synthesized clock networks. With these constraints, a clock scheduler can be used to guide the synthesis of a clock network by specifying a set of feasible arrival times at the respective sequential elements. Clock scheduling can be either static or dynamic. In static clock scheduling, a clock schedule is first specified; next, a clock network is constructed realizing the prescribed schedule. Clock trees constructed using this approach may consume significant routing resources. In dynamic clock scheduling, the clock tree and clock schedule are both simultaneously constructed and determined, respectively. In earlier studies, the scalability of dynamic clock scheduling, which is essentially a shortest path problem, has been limited. The bottleneck is in finding the shortest paths between different vertices in an incrementally changing weighted graph. In this work, we present two clock schedulers that address the scalability issues by exploiting the sparsity of this weighted graph. Experimental results show that the proposed clock schedulers are one to two orders of magnitude faster compared to a published scheduler in an earlier work. The proposed clock schedulers are scalable, and are tested on a synthesized circuit with 348 710 cells, 57 491 sequential elements, and 496 727 explicit timing constraints.

The clock networks of modern circuits must be able to operate in multiple corners and multiple modes (MCMM). Earlier studies on clock network synthesis for MCMM designs focus on the legalization of an initial clock network that has timing violations in different corners or modes. We propose a mode reconfigurable clock tree (MRCT) that is based on a correct-by-construction approach. An MRCT consists of multiple clock trees. Depending on the active mode, the MRCT is reconfigured such that one of the clock trees is activated to deliver the clock signal. To limit the overhead, the bottom part of the network (closer to the clock sinks) is shared among all of the clock trees, and only the top part of the network (closer to the clock source) is mode reconfigurable. The reconfiguration is realized using or-gates and a single one-input-multiple-output demultiplexer. The MRCT is constructed in a bottom-up fashion by iteratively merging subtrees to form larger subtrees. When two subtrees cannot be merged because of mode-incompatible constraints, an or-gate is inserted to separate the incompatible modes. Corner-incompatible constraints are resolved by reducing safety margins of appropriate skew constraints. The experimental results show that for a set of synthesized MCMM circuits with 715 to 13; 216 sequential elements, the proposed approach can achieve high yield.

Previous studies on human-pose estimation rely on the design of factors to represent underlying probability distributions. However, designing factors is laborious and yet, the designed factors may not represent the underlying probability distributions. In this paper, we propose to use a neural network to automatically design factors in one of the existing models called the action-mixture model (AMM). Factors that are designed automatically by neural networks can be adapted to different situations. The semantic meaning of random variables in AMM can be transferred to a neural network, rendering the semantic meaning of hidden neurons transparent to users. The design process consists of two stages: structure identification and parameter learning. In the structure identification, we propose a bottom-up approach to build a neural network while preserving the structure of AMM. In the parameter learning, we propose a part-based approach to learn synaptic weights by decomposing a neural network into parts. Synaptic weights that have been learnt in one part can be used as initial weights for learning synaptic weights in another part. Based on the concept of distributed representation, the proposed two-stage, neural-network-based design process is used to design a scalable neural network to realize an AMM. Experimental results showed that the scalable neural network outperformed AMM and some existing works.

The construction of clock trees for modern designs is challenging because the clock trees need to be constructed with adequate safety margins such that the skew constraints are satisfied even under variations. The amount of safety margin required in a skew constraint is dependent on the distance of the corresponding sequential elements in the tree topology. In certain cases, the amount of safety margin that can be inserted may be limited. Consequently, the corresponding sequential elements should be placed close in the topology, i.e., the point of divergence to these elements is low in the clock tree, in order to reduce the influence of variations. By using safety margins and lowering the point of divergence, we present a framework for the construction of useful skew trees with large safety margins inserted in the skew constraints. The framework, called UST-LSM, first identifies tight skew constraints by the detection of negative cycles in a weighted skew constraint graph. Next, the corresponding sequential elements of these skew constraints are clustered early in tree topology. Compared to earlier studies, we can allow larger safety margins in skew constraints spanning between sequential elements within a subtree. This translates into an improvement of yield from 46.8% to 98.8% on a synthesized benchmark with 7,674 sequential elements and 63,440 skew constraints.

Clock trees are commonly used to deliver clock signals to sequential elements in circuits. However, by construction, tree structures are inherently prone to failure caused by variations. The robustness of a clock tree can be improved by inserting redundancy in the form of cross links or multilevel fusion trees. Such near-tree structures can provide robustness at low cost. In this paper, we establish that the locations of the inserted redundancy are crucial in providing cost-effective robustness. We present two methods to systematically insert redundancy. The redundancy is realized by either inserting cross links or performing local merges. Moreover, we present a vertex reduction method that reduces the amount of redundancy that needs to be inserted in our near-tree structures. Empirical results show that our structures are more robust to variations and have lower power consumption compared to the state-of-the-art clock networks. Furthermore, our near-tree structures provide smooth trade-offs between cost and robustness, reducing clock skews by 11%-39% at an expense of 3%-68% higher power consumption.

We propose an analytical placer for generating placement results that can be detailed-routed faster and have fewer violation of design rules. By including a group of pin density constraints in its mathematical formulation, the placer manages to alleviate pin congestion when distributing cells. Moreover, for mixed-size circuits, we adopt a scaled smoothing method to minimize the possible negative influence of fixed macro blocks in placement. As a result, we have few cells overlapping with fixed blocks after global placement, implying that the global placement solution resembles a legal solution more and that legalization has less perturbance to the placement quality. Also, in the final placement result, fewer cells are around macro blocks, whose negative effect in the future routing stage can thus be reduced. Routing solutions obtained by a commercial router show that for most benchmark circuits, detailed routing solutions with fewer violations can be achieved on the placement results generated by our analytical placer.

Wire sizing can be used to reduce the delays of critical nets. However, because of the forbidden pitch issue in sub-20nm designs, wide wires may no longer be an attractive solution because of the restrictive wire spacing requirement from advanced lithography. In this work, we investigate the suitability of the parallel wiring technique, in which multiple parallel wires are used to route the same net, as an alternative to routing a net using a single wide wire. In particular, we study the trade offs between parasitics, timing, power, and routing resources. Our study reveals that wire sizing using both parallel wires and wide wires can be advantageous. Moreover, if high layout densities are required, parallel wiring can be a viable approach in solving timing problems for sub-20nm designs.

To obtain high yield for 3D ICs, random open defects, process variations, and thermal induced stress are key issues that must be addressed when synthesizing 3D clock networks. Current research on 3D clock synthesis often focuses on the construction and optimization of a 3D clock tree topology. Moreover, extra circuitry has been proposed to enable pre-bond testing and substitution of through silicon vias (TSVs) with random open defects. However, tree structures inherently have limited robustness to variations and may suffer failures arising from defects and/or process variations. To counter such problems, we propose to use TSVs to add redundancy in a 3D clock network. The proposed 3D network would have a complete 2D clock network on each die, facilitating pre-bond testing. Also, cross links would be inserted within each die using wires and across dies using TSVs to improve timing robustness within each die and across dies, respectively. Moreover, clock buffers are placed outside of zones that have high TSV-induced stress that could influence carrier mobility. Experimental results show that the proposed 3D clock networks have no failures due to random open defects, and on the average have 53% lower skew compared to 3D tree structures.

Estimating human poses is an important step towards developing robots that can understand human motion. Since a human is highly articulated, changing viewpoints of sensors on robots can improve the accuracy of human-pose estimation. We propose a two-phase approach that determines the best viewpoint of a depth sensor for human-pose estimation. The proposed approach measures the quality of potential viewpoints and selects one of them as the best viewpoint for each human pose. Based on the quality of viewpoints, human poses can be directly mapped to the best viewpoint without reconstructing the human body. Thus, the proposed approach provides a discriminative mapping to determine the best viewpoint for estimating different human poses. To measure the quality of a potential viewpoint, the viewpoint is first instantiated by representing the depth sensor of the viewpoint using the finite projective camera model. The quality of the viewpoint is expressed in terms of the error of humanpose estimates. A mapping is derived by minimizing the error in a human-pose estimate among different viewpoints. The proposed two-phase approach has been evaluated on a benchmark database. Experimental results showed that the best viewpoint for a human pose could be determined by evaluating the quality of potential viewpoints. The mean error and standard deviation of human-pose estimates were reduced by using the best viewpoint determined by the proposed two-phase approach.

By modifying an existing Mixed Integer Programming (MIP) model for optimizing the placement of cells in sliding windows, we develop a detailed placer for large-scale mixed-size circuits. To make it possible to optimize the placement of larger sliding windows in reasonable time, we reduce the number of integer variables in the modified MIP model such that when compared with the original complete MIP model, the solution time is shortened greatly while the solution quality does not degrade much. Experimental results on DAC12 benchmark circuits show that our detailed placer manages to further reduce half-perimeter wirelength (HPWL) of the placement results generated by many other existing detailed placement techniques. Moreover, by making use of a commercial router, we also evaluate the routability of the placement results before and after the application of our detailed placer. Both the routed wirelength and the number of vias in routing solutions are reduced, while the number of design rule violations does not change much for most circuits, implying the routablity of placement results are not perturbed.

The eight papers in this special section highlight several studies on contemporary and emerging issues in physical design.

This paper focuses on human-pose estimation using a stationary depth sensor. The main challenge concerns reducing the feature ambiguity and modeling human poses in high-dimensional human-pose space because of the curse of dimensionality. We propose a 3-D-point-cloud system that captures the geometric properties (orientation and shape) of the 3-D point cloud of a human to reduce the feature ambiguity, and use the result from action classification to discover low-dimensional manifolds in human-pose space in estimating the underlying probability distribution of human poses. In the proposed system, a 3-D-point-cloud feature called viewpoint and shape feature histogram (VISH) is proposed to extract the 3-D points from a human and arrange them into a tree structure that preserves the global and local properties of the 3-D points. A nonparametric action-mixture model (AMM) is then proposed to model human poses using low-dimensional manifolds based on the concept of distributed representation. Since human poses estimated using the proposed AMM are in discrete space, a kinematic model is added in the last stage of the proposed system to model the spatial relationship of body parts in continuous space to reduce the quantization error in the AMM. The proposed system has been trained and evaluated on a benchmark dataset. Computer-simulation results showed that the overall error and standard deviation of the proposed 3-D-point-cloud system were reduced compared with some existing approaches without action classification.

Search engines have greatly influenced the way people access information on the Internet, as such engines provide the preferred entry point to billions of pages on the Web. Therefore, highly ranked Web pages generally have higher visibility to people and pushing the ranking higher has become the top priority for Web masters. As a matter of fact, Search Engine Optimization (SEO) has became a sizeable business that attempts to improve their clients’ ranking. Still, the lack of ways to validate SEO’s methods has created numerous myths and fallacies associated with ranking algorithms. In this article, we focus on two ranking algorithms, Google’s and Bing’s, and design, implement, and evaluate a ranking system to systematically validate assumptions others have made about these popular ranking algorithms. We demonstrate that linear learning models, coupled with a recursive partitioning ranking scheme, are capable of predicting ranking results with high accuracy. As an example, we manage to correctly predict 7 out of the top 10 pages for 78% of evaluated keywords. Moreover, for content-only ranking, our system can correctly predict 9 or more pages out of the top 10 ones for 77% of search terms. We show how our ranking system can be used to reveal the relative importance of ranking features in a search engine’s ranking function, provide guidelines for SEOs and Web masters to optimize their Web pages, validate or disprove new ranking features, and evaluate search engine ranking results for possible ranking bias.

Routability has become a critical issue in VLSI design flow. To avoid producing an unroutable design, many placers [4-7] invoke global routers to get a congestion map and then move cells to reduce congestion based on this map. However, as cells move, the accuracy of the congestion map degrades, thereby affecting the effectiveness of the placer in minimizing congestions. Moreover, most global routers [8-13] ignore local congestion. If placers are guided by these routers, it may produce hard-to-route placement solutions in terms of detailed routing. This work develops a routability optimizer, called Ropt, to reduce both global and local routing congestion levels of a given placement. Based on a local-routability-aware routing model, Ropt builds a global routing instance to obtain global and local congestion information for guiding global re-placement. In addition, this work presents a new legalization scheme to preserve the global routing instance after legalization. Finally, local detailed placement further minimizes the local congestion and wirelength. For the evaluation of Ropt, we use an academic global router and a commercial router to obtain both global and detailed routing results, respectively. Experimental results reveal that Ropt can improve the routing quality (in terms of congestion, wirelength, and violation) and routing runtime of a given placement solution.

Estimating human poses is an important step towards developing robots that can understand human motions and improving their cognitive capabilities. This paper presents a geometric feature for estimating human poses from a 3D point cloud input. The proposed feature can be considered as an extension of the idea of visual features, such as color/edge, of color/grayscale images, and it contains the geometric structure of the point cloud. It is derived by arranging the 3D points into a tree structure, which preserves the global and local properties of the 3D points. Shown experimentally, the tree structure (spatial ordering) is particularly important for estimating human poses (i.e., articulated objects). The 3D orientation (pan, tilt and yaw angles) and shape features are then extracted from each node in the tree to describe the geometric distribution of the 3D points. The proposed feature has been evaluated on a benchmark dataset and compared with two existing geometric features. Experimental results show that the proposed feature has the lowest overall error in human-pose estimation.

This paper presents a 3D-point-cloud system that extracts a 3D-point-cloud feature (VISH) from the observation of a depth sensor to reduce feature/depth ambiguity and estimates human poses using the result of action classification and a kinematic model. Based on the concept of distributed representation, a non-parametric action-mixture model is proposed in the system to represent high-dimensional human-pose space using low-dimensional manifolds in searching human poses. In each manifold, the probability distribution is estimated by the similarity of features. The distributions in the manifolds are then redistributed according to the stationary distribution of a Markov chain that models the frequency of actions. After the redistribution, the manifolds are combined according to the distribution determined by the action classification. In addition, the spatial relationship between human-body parts is explicitly modeled by a kinematic chain. Computer-simulation results showed that multiple low-dimensional manifolds can represent human-pose space. The 3D-point-cloud system showed reduction of the overall error and standard deviation compared with other approaches without using action classification.

Process and environmental variations affect the reliability of clock networks. By synthesizing non-tree structures, the robustness of clock networks can be improved at the expense of higher capacitance. A cheap way of converting a tree structure to a non-tree structure is to insert cross links. Unfortunately, the robustness seems to improve only when the links are sufficiently short. Other non-tree structures such as meshes and multilevel fusion trees improve the robustness more effectively, but with much higher cost. In this work, we develop a new non-tree topology by merging a sub-clock tree with all other sub-clock trees that contain sequential elements that require strict synchronization. Results show that when compared with the state-of-the-art solutions, clock networks constructed with the proposed structure have similar capacitance but notable improved robustness. moreover, the clock networks can satisfy tight skew constraints even when simulated under a more stringent variations model, with 22% lower capacitance when compared to solutions in earlier studies.

Routability is a critical issue in VLSI design flow. To address this issue, the routability-driven placement contests [1, 2] held at ISPD11 and DAC12 promote the development of routability-driven placers such as those in [4-6]. ISPD11 and DAC12 contests adopt metrics that are based on global routing solutions to evaluate the routability of placement solutions. However, such global-routing-based metrics typically ignore local congestion, and they cannot evaluate the actual routability effectively. In this work, we develop a translator that allows us to feed the placement solutions of mPL [3], NTUplace [4], Ripple [5], and SimPLR [6] into a commercial router for detailed routing. We then analyze the detailed routing result of each placement solution to better understand the issues that may cause routing violations. Moreover, we examine the suitability of using the ISPD11 and DAC12 metrics in predicting routability. Our findings indicated that the metrics might not reliably predict actual routability, in terms of the number of (detailed) routing violations.

It has been predicted that a processor's caches could occupy as much as 90% of chip area a few technology nodes from the current ones. In this article, we investigate the use of multilevel spin-transfer torque RAM (STT-RAM) cells in the design of processor caches. We start with examining the access (read and write) scheme for multilevel cell (MLC) STT-RAM from a circuit design perspective, detailing the read and write circuits. Compared to traditional SRAM caches, a multilevel cell (MLC) STT-RAM cache design is denser, fast, and requires less energy. However, a number of critical architecture-level issues remain to be solved before MLC STT-RAM technology can be deployed in processor caches. We shall offer solutions to the issue of bit encoding as well as tackle the write endurance problem. In particular, the latter has been neglected in previous works on STT-RAM caches. We propose a set remapping scheme that can potentially prolong the lifetime of a MLC STT-RAM cache by 80× on average. Furthermore, a method for recovering the performance that may be lost in some applications due to set remapping is proposed. The impacts of process variations of the MLC STT-RAM cell on the robustness of the memory hierarchy is also discussed, together with various enhancement techniques, namely, ECC and design redundancy.

This Special Section considers several studies that emphasize cross-domain physical optimization. The first paper applies physical optimization techniques that cut across the discrete and continuous domains; a geometric programming method is applied to solve the classical floorplanning problem. The second paper introduces a subfield scheduling approach that considers both ebeam lithography throughput and the thermal effect in the ebeam writing process. The third paper presents techniques that make the circuit layout compatible with multiple-patterning lithography. The fourth paper describes an integrated design methodology for microfluidic chips that encompasses operation scheduling, chip layout generation, control pin assignment, and wiring solution. The fifth paper crosses the boundaries of datapath design and random logic; it proposes a placement flow that simultaneously places a mixture of random logic and datapath cells found in hybrid designs. The short paper replaces flipflops with pulsed latches, and utilizes the time-borrowing property of pulsed latches and clock gating to achieve power efficiency.

Considering routability issue in the early stages of VLSI design flow can avoid generating an unroutable design. Several recent routablity-driven placers [8--11] adopt a built-in global router to estimate routing congestion. While the routability of the placement solution improves, the performance of these placers degrades. Many of these built-in global router and state-of-the-art academic global routers use maze routing to seek a detoured path. Although very effective, maze routing is relatively slower than other routing algorithms, such as pattern routing and monotonic routing algorithms. This work presents two efficient routing algorithms, called unilateral monotonic routing and hybrid unilateral monotonic routing, to replace maze routing and to realize a highly fast maze-free global router that is suited to act as a built-in routing congestion estimator for placers. Experimental results indicate that RCE achieves similar routing quality when compared with [20], as well as an over 20-fold runtime speedup in large benchmarks.

Existing detailed placement optimization methods typically involve the use of enumeration to determine the optimal location of a small number of cells. We propose two Mixed Integer Programming (MIP) models that can optimize the detailed placement of more cells efficiently. Compared with existing models, the first proposed model has fewer integer variables. The second proposed model, derived based on Dantzig-Wolfe decomposition principle, is with tighter bounds during its solution. Experimental results show that both models are capable of optimizing in reasonable time the detailed placement of much larger problem instances than existing models. Experiments on large-scale real benchmark circuits also show that detailed placer based on advanced MIP models can effectively reduce half-perimeter wirelengh (HPWL), as well as routed wirelength and vertical vias, of the original placement results generated by enumeration approach.

We propose a global placement algorithm that employs size scaling of circuit components to provide continuity during placement. In the context of mixed-size placement, size scaling is utilized to handle significant variations among the sizes of the components, thereby avoiding additional complexity that is often associated with multiple levels of smoothing. By using the optimal region approach to first determine an initial placement, the size scaling approach allows the global placement algorithm to converge to better placement solutions.

The eight papers in this special section are extended versions of papers presented at the 2011 International Symposium on Physical Design (ISPD 2011), held in Santa Barbara, CA.

It is of critical importance to efficiently and accurately predict global resonances of a 3-D integrated circuit system that involves arbitrarily shaped lossy conductors and inhomogeneous materials. A quadratic eigenvalue solver of linear complexity and electromagnetic accuracy is developed in this paper to fulfill this task. Without sacrificing accuracy, the proposed eigenvalue solver has shown a clear advantage over state-of-the-art eigenvalue solvers in fast CPU time. It successfully solves a quadratic eigenvalue problem of over 2.5 million unknowns associated with a large-scale 3-D on-chip circuit embedded in inhomogeneous materials in 40 min on a single 3 GHz 8222SE AMD Opteron processor.

Passivity is an important property of circuits and systems to guarantee stable global simulation. Nonetheless, nonpassive models may result from passive underlying structures due to numerical or measurement error/inaccuracy. A postprocessing passivity enforcement algorithm is therefore desirable to perturb the model to be passive under a controlled error. However, previous literature only reports such passivity enforcement algorithms for pole-residue models and regular systems (RSs). In this paper, passivity enforcement algorithms for descriptor systems (DSs, a superset of RSs) with possibly singular direct term (specifically,D+DTorI-DDT) are proposed. The proposed algorithms cover all kinds of state-space models (RSs or DSs, with direct terms being singular or nonsingular, in the immittance or scattering representation) and thus have a much wider application scope than existing algorithms. The passivity enforcement is reduced to two standard optimization problems that can be solved efficiently. The objective functions in both optimization problems are the error functions, hence perturbed models with adequate accuracy can be obtained. Numerical examples then verify the efficiency and robustness of the proposed algorithms.

In this paper, we formulate a problem of simultaneous redundant via insertion and line end extension for via yield optimization. Our problem is more general than previous works in the sense that more than one type of line end extension is considered and the objective function to be optimized directly accounts for via yield. We present a zero-one integer linear program based approach, that is equipped with two speedup techniques, to solve the addressed problem optimally. In addition, we describe how to modify our approach to exactly solve a previous work. Extensive experimental results are shown to demonstrate the effectiveness and efficiency of our approaches.

The International Symposium on Physical Design (ISPD) 2010 contest presents the challenge of synthesizing clock distribution networks that are tolerant to severe power-supply and wire-width variations. In particular, a robust clock network should satisfy the local clock skew (LCS) constraint, i.e., the clock skew between any pair of sequential elements that are closer than a user-specified distance is below a user-specified limit, even in the presence of variations. In this paper, we identify a few factors that help in tolerating these variations in clock trees. Our proposed clock tree router uses a two-stage flow to construct low-power clock trees for which the LCS constraints are met. Our clock tree router has been tested on ISPD'10 contest benchmark circuits. Extensive Monte-Carlo simulations showed that low power clock tree solutions could effectively handle variations, even when we imposed more stringent conditions in the experimental setup.

Cross links have been used to reduce skew variations in clock trees. In earlier studies cross links are inserted between the sinks of DC-connected trees. In this paper, we propose a link insertion scheme that inserts cross links between internal nodes of a clock tree. In addition to reducing the skew variability, the proposed approach also reduces the total cross link length. Our work also improves the correlation of sink delays for those sinks within a subtree that have similar path lengths to the cross link. Monte-Carlo (MC) simulations on the ISPD-2010 benchmarks showed that our work could handle variations effectively. In addition to meeting all the design constraints, the solutions produced by our approach have on the average 32% lower capacitance than the least capacitance obtained by the top three teams in the ISPD-2010 design contest [1].

We introduce a technique that utilizes distributing computing resources for the efficient optimization of a traditional physical design problem. Specifically, we present a detailed placement strategy designed to exploit distributed computing environments, where the additional computing resources are employed in parallel to improve the optimization time. A Mixed Integer Programming (MIP) model and branch-and-cut optimization strategy are employed to solve the standard cell placement problem. By exploiting the problem structure, our algorithm improves upon the solutions afforded by existing optimization algorithms. First, an efficient batch-branching technique can eliminate several integer decision variables during each step of the optimization procedure. This batch-branching scheme can be performed serially or in parallel. In addition, custom cutting-planes are shown to significantly reduce the run time for optimizations as they efficiently refine the feasible region in order to quickly produce integer solutions. Our serial branch-and-cut strategies allow for significant reductions in wirelength, relative to the state-of-the-art commercial software package CPLEX, assuming a fixed allotment of time. Furthermore, we show that distributed computing resources can be used to significantly reduce the time required to achieve reductions in wirelength.

Passivity is a crucial property of macromodels to guarantee stable global (interconnected) simulation. However, weakly nonpassive models may be generated for passive circuits and systems in various contexts, such as data fitting, model order reduction (MOR) and electromagnetic (EM) macromodeling. Therefore, a post-processing passivity enforcement algorithm is desired. Most existing algorithms are designed to handle pole-residue models. The few algorithms for state space models only handle regular systems (RSs) with a nonsingular D+DTterm. To the authors' best knowledge, no algorithm has been proposed to enforce passivity for more general descriptor systems (DSs) and state space models with singular D+DTterms. In this paper, a new post-processing passivity enforcement algorithm based on perturbation of Hamiltonian-symplectic matrix pencil, PEDS, is proposed. PEDS, for the first time, can enforce passivity for DSs. It can also handle all kinds of state space models (both RSs and DSs) with singular D+DTterms. Moreover, a criterion to control the error of perturbation is devised, with which the optimal passive models with the best accuracy can be obtained. Numerical examples then verify that PEDS is efficient, robust and relatively cheap for passivity enforcement of DSs with mild passivity violations.

Search engines have greatly influenced the way people access information on the Internet as such engines provide the preferred entry point to billions of pages on the Web. Therefore, highly ranked web pages generally have higher visibility to people and pushing the ranking higher has become the top priority for webmasters. As a matter of fact, search engine optimization (SEO) has became a sizeable business that attempts to improve their clients' ranking. Still, the natural reluctance of search engine companies to reveal their internal mechanisms and the lack of ways to validate SEO's methods have created numerous myths and fallacies associated with ranking algorithms; Google'sin particular. In this paper, we focus on the Google ranking algorithm and design, implement, and evaluate a ranking system to systematically validate assumptions others have made about this popular ranking algorithm. We demonstrate that linear learning models, coupled with a recursive partitioning ranking scheme, are capable of reverse engineering Google's ranking algorithm with high accuracy. As an example, we manage to correctly predict 7 out of the top 10 pages for 78% of evaluated keywords. Moreover, for content-only ranking, our system can correctly predict 9 or more pages out of the top 10 ones for 77% of search terms. We show how our ranking system can be used to reveal the relative importance of ranking features in Google's ranking function, provide guidelines for SEOs and webmasters to optimize their web pages, validate or disapprove new ranking features, and evaluate search engine ranking results for possible ranking bias.

An algorithm is presented for the fast and accurate simulation of power/ground mesh structures. Our method is a direct (non-iterative) approach for simulation based upon a parallel matrix inversion algorithm. The new dimension of flexibility provided by our algorithm allows for a more accurate analysis of power/ground mesh structures using resistance, inductance, capacitance, interconnect models. Specifically, we offer a method that employs a sparse approximate inverse technique to consider more reluctance coupling terms for increased accuracy of simulation. Our algorithm shows substantial computational improvement over the best known direct and iterative numerical techniques that are applicable to these large-scale simulation problems.

As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality.

In this paper, we proposed a new adder design called variable-latency adder (VL-adder). This technique allows the adder to work at a lower supply voltage than that required by a conventional adder while maintaining the same throughput. The VL-adder design can be further modified to overcome the effects of negative bias temperature instability (NBTI) on circuit delay. By applying VL-adder concept to a 64-bit carry-select adder design, more than 40% energy saving is obtained when a similar throughput is maintained.

State-of-the-art integral-equation-based solvers rely on techniques that can perform a matrix-vector multiplication in O(N) complexity. In this work, a fast inverse of linear complexity was developed to solve a dense system of linear equations directly for the capacitance extraction of any arbitrary shaped 3D structure. The proposed direct solver has demonstrated clear advantages over state-of-the-art solvers such as FastCap and HiCap; with fast CPU time and modest memory consumption, and without sacrificing accuracy. It successfully inverts a dense matrix that involves more than one million unknowns associated with a large-scale on-chip 3D interconnect embedded in inhomogeneous materials. Moreover, we have successfully applied the proposed solver to full-wave extraction.

This paper studies the effects of clustering as a pre-processing step and routability estimation in the placement flow. The study shows that when clustering and routability estimation are considered, the placer effectively improves the routed wirelength for the circuits of IBM-PLACE 2.0 standard-cell Benchmark Suite [1] and results in the best average routed wirelength when compared against state-of-the-art academic placers.

There has been much work on the next generation of memory technologies such as MRAM, RRAM and PRAM. Most of these are non-volatile in nature, and compared to SRAM, they are often denser, just as fast, and have much lower energy consumption. Using 3-D stacking technology, it has been proposed that they can be used instead of SRAM in large level 2 caches prevalent in today's microprocessors. However, one of the key challenges in the use of these technologies, such as MRAM, is their higher fault probabilities arising from the larger process variation, defects in its fabrication, and the fact that the cache is much larger. This seriously affect yield. In this paper, we propose a fault resilient set associative cache architecture which we called the salvage cache. In the salvage cache, a faulty cache block is sacrificed and used to repair faults found in other blocks. We will describe in detail the architecture of the salvage cache as well as provide results of yield simulations that show that a much higher yield can be achieved viz-a-viz other fault tolerant techniques. We will also show the performance savings that arise from the use of a large next-generation L2 cache.

One important trend in today's microprocessor architectures is the increase in size of the processor caches. These caches also tend to be set associative. As technology scales, process variations are expected to increase the fault rates of the SRAM cells that compose such caches. As an important component of the processor, the parametric yield of SRAM cells is crucial to the overall performance and yield of the microchip. In this article, we propose a microarchitectural solution, called the buddy cache that permits large, set-associative caches to tolerate faults in SRAM cells due to process variations. In essence, instead of disabling a faulty cache block in a set (as is the current practice), it is paired with another faulty cache block in the same set—the buddy. Although both cache blocks are faulty, if the faults of the two blocks do not overlap, then instead of losing two blocks, buddying will yield a functional block from the nonfaulty portions of the two blocks. We found that with buddying, caches can better mitigate the negative impacts of process variations on performance and yield, gracefully downgrading performance as opposed to catastrophic failure. We will describe the details of the buddy cache and give insights as to why it is both more performance and yield resilient to faults.

To minimize the leakage power dissipation of present-day on-chip Decaps, we propose a gated decoupling capacitor (GDecap) technique that deactivates a Decap when it is not needed. The application of the proposed GDecap technique on an eight-way clock-gated clustered pipeline showed that on average, 41.7% Decap leakage power was reduced, with negligible (~ 0.037%) worst-case performance degradation, at the 70-nm technology node. GDecap design incurred an area overhead of around 5.36% when compared with a conventional Decap design.

This paper presents an efficient technique for the estimation of the routed wirelength during global placement using the wire density of the net. The proposed method identifies congested regions of the chip and incorporates the model of the routed wirelength into the objective function in order to effectively alleviate these regions from congestion. The method is integrated in the analytical placement framework and the two-level structure improves the scalability of the placer and speeds up the algorithm. The proposed analytical placer provides the best-so-far average routed wirelength in the IBM version2 benchmark suite.

We present an efficient technique for the fast and accurate extraction of inductance of large-scale on-chip interconnects. Several simulation techniques exploit the sparsity of L−1for reducing storage and computational costs during computation. Recently, band matching technique was introduced for sparsification of L−1. We extend the band-matching technique for inductance extraction problems. We introduce an efficient technique to invert the approximate band-matched impedance matrix Rƒ + jω̃Lƒ. The new technique relies on a numerically stable and efficient representation for inverses of banded matrices. Numerical results show that our approach is both accurate as well as computationally efficient, with orders-of-magnitude improvement over traditional techniques.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double-cut via insertion (DVI) in a post-routing stage, where a single via can have at most one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing optimal DVI solution, with up to 35.3 times speedup over existing heuristic algorithms.

Redundant via insertion is highly effective in improving chip yield and reliability. In this paper, we study the problem ofdouble-cutviainsertion(DVI) in a post-routing stage, where a single via can have, at most, one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing an optimal DVI solution, with up to 73.98 times speedup over existing heuristic algorithms.

We propose a frequency-domain modeling technique with applications on the statistical timing analysis of clock mesh/grid networks. Using transmission lines to model clock mesh edges, we express the means and (co)variances of the sink arrival times as polynomial functions of the arrival times of the input signals and the wire widths of the mesh edges, with up to second order accuracy. Experimental results show that the proposed frequency-domain statistical timing analysis technique is efficient and accurate. The relative mean error is less than 1% and relative variance error less than 3%.

The cache hierarchy of state-of-the-art - especially multicore - microprocessors consumes a significant amount of area and energy. A significant amount of research has been devoted especially to reducing the latter. One of the most important microarchitectural techniques proposed for the energy management is dynamic voltage scaling (DVS). In DVS solutions, each cache operates at a number of different voltages. Most of the research in DVS techniques have been around how the voltages can be adjusted and tuned. In this paper, we depart from the use of DVS for energy conservation by examining static voltage assignments for caches. We propose the use of voltage scaled cache hierarchies (VOSCH) as a means to conserve both static and dynamic energy. In VOSCH, the caches are powered at progressively lower supply voltages as the cache level increases. Compared to DVS solutions, VOSCH is simple, potentially more robust and can conserve more energy. We also experimented with more aggressive designs that included the addition of small cache structures to VOSCH. Even greater energy savings were achieved without having to sacrifice performance.

Negative bias temperature instability (NBTI) has become a dominant reliability concern for nanoscale PMOS transistors. In this paper, we propose variable-latency adder (VL-adder) technique for NBTI tolerance. By detecting the circuit failure on-the-fly, the proposed VL-adder can automatically shift data capturing clock edge to tolerate NBTI-induced delay degradation on critical timing paths. VL-adder operates with a fixed supply voltage and clock period, avoiding the high design and manufacturing costs incurred by existing NBTI-tolerant techniques. Compared to other related lower-power adder designs, VL-adder technique always provides better energy efficiency through the whole chip lifetime with very limited performance degradation (4.6% or less).

We present a two-stage congestion-driven placement flow. First, during each refinement stage of our multilevel global placement framework, we replace cells based on the wirelength weighted by congestion level to reduce the routing demands of congested regions. Second, after the global placement stage, we allocate appropriate amounts of white space into different regions of the chip according to a congestion map by shifting cut lines in a top-down fashion and apply a detailed placer to legalize the placement and further reduce the half-perimeter wirelength while preserving the distribution of white space. Experimental results show that our placement flow can achieve the best routability with the shortest routed wirelength among publicly available placement tools on IBM v2 benchmarks. Our placer obtains 100% successful routings on 16 IBM v2 benchmarks with shorter routed wirelengths by 3.1% to 24.5% compared to other placement tools. Moreover, our white space allocation approach can significantly improve the routability of placements generated by other placement tools.

A high performance communication architecture, SAMBA-bus, is proposed in this paper. In SAMBA-bus architecture, multiple compatible bus transactions can be performed simultaneously with only a single bus access grant from the bus arbiter. Experimental results show that, compared with a traditional bus architecture, the SAMBA-bus architecture can have up to 3.5 times improvement in the effective bandwidth, and up to 15 times reduction in the average communication latency. In addition, the performance of SAMBA-bus architecture is affected only slightly by arbitration latency, because bus transactions can be performed without waiting for the bus access grant from the arbiter. This feature is desirable in SoC designs with large numbers of modules and long communication delay between modules and the bus arbiter

We present a technique for the fast and accurate simulation of large-scale VLSI interconnects with nonlinear devices, called SASIMI. The numerical efficiency of this technique is realized through linear-algebraic techniques that exploit the sparsity and structure of the matrices that are encountered in VLSI structures. Numerical results show that SASIMI is up to 1400 times as fast as commercial-grade SPICE, for moderate-size circuits, with little sacrifice in simulation accuracy.

Technology scaling and sub-wavelength optical lithography is associated with significant process variations. We propose a self-adaptive variable supply-voltage scaling (SAVS) technique for multi-issue out-of-order pipeline to improve parametric yield with minimal power dissipation. Our error-correction circuitry and recovery mechanism allow the proposed fault-tolerant pipeline to work at a dynamically tuned supply voltage with a very low error rate. Experiments on an 8-issue, out-of-order superscalar processor show that SAVS can achieve 93.3% yield with 8.66% total power reduction under a scaled Vdd, compared to the same yield achieved by conventional microarchitecture. The increased execution time is negligible (0.014%).

We present a new algorithm for discretizing interconnects, a step that is typically performed to account for the nonuniformity of current flow at high frequencies. The algorithm is based on an easily-computable measure that correlates well with the model accuracy. This measure is used to refine the discretization of interconnects in an adaptive scheme so as to systematically trade off computation against model accuracy. We apply the proposed discretization technique on two classes of problems in the analysis of VLSI interconnects: simulation and frequency-dependent inductance extraction. Numerical results establish that with the interconnect discretizations generated by our algorithm, a reduction in simulation and extraction times by a factor between three and seven can be realized with negligible sacrifice in model accuracy (<1% error)

Recent successful techniques for the efficient simulation of largescale interconnect models rely on the sparsification of the inverse of the inductance matrix L. While there are several techniques for sparsifying L-1, the stability of these approximations for general interconnect structures has not been established, i.e., the sparsified reluctance and inductance matrices are not guaranteed to be positive-definite. In this paper, we present a novel technique for reluctance sparsification for general interconnect structures that enjoys several advantages: First, the resulting sparse approximation is guaranteed to be positive definite. Second, the approximation is optimal, in a certain well-defined sense. Third, owing to its computational efficiency and numerical stability, the algorithm is applicable for very large problem sizes. Finally our approach yields a compact representation of both inductance and reluctance matrices for general cases.

This paper formally models and studies latency-insensitive systems (LISs) through max-plus algebra. We introduce state traces to model behaviors of LISs and obtain a formally proved performance upper bound achievable by latency-insensitive design. An implementation of the latency-insensitive protocol that can provide robust communication through back-pressure is also proposed. The intrinsic performance of the proposed implementation is acquired based on state traces. It is also proved that the proposed implementation can always reach the best performance achievable by latency-insensitive design.

This paper presents two recently developed algorithms for efficient model order reduction. Both algorithms enable the fast solution of continuous-time algebraic Riccati equations (CAREs) that constitute the bottleneck in the passivity-preserving balanced stochastic truncation (BST). The first algorithm is a Smith-method-based Newton algorithm, called Newton/Smith CARE, that exploits low-rank matrices commonly found in physical system modeling. The second algorithm is a project-and-balance scheme that utilizes dominant eigenspace projection, followed by a simultaneous solution of a pair of dual CAREs through completely separating the stable and unstable invariant subspaces of a Hamiltonian matrix. The algorithms can be applied individually or together. Numerical examples show the proposed algorithms offer significant computational savings and better accuracy in reduced-order models over those from conventional schemes.

Logic duplication, a commonly used synthesis technique to remove trapped inverters in reconvergent paths of Domino circuits, incurs high area and power penalties. In this article, we propose a synthesis scheme to reduce the duplication cost by allowing inverters in Domino logic under certain timing constraints for both simple and complex gates. Moreover, we can include the logic duplication minimization during technology mapping for synthesis of Domino circuits with complex gates. In order to guarantee the robustness of such Domino circuits, we perform the logic optimization as a postlayout step. Experimental results show significant reduction in duplication cost, which translates into significant improvements in area and power. As a byproduct, the timing performance is also improved owing to smaller layout area and/or logic depth.

Logic duplication to resolve the logic reconvergent paths problem encountered in Domino logic synthesis is expensive in terms of area and power. In this paper, we propose a combined logic duplication minimization and technology mapping scheme for Domino circuits with complex gates. The logic duplication is performed as a post-layout step as the duplication cost is minimized based on accurate timing information. Experimental results show significant improvements in area, power, and delay.

As the minimum feature sizes of VLSI circuits get smaller while the clock frequency increases, the effects of process variations become significant. We propose a UST/DME based approach to perform simultaneous non-zero clock skew scheduling and clock tree routing, taking into consideration the effects of process variations on clock skews. Our approach ensures that the generated clock tree has a high tolerance to process variations while minimizing the total capacitance of the clock tree, which is proportional to the total wirelength and the total number of buffers. Monte Carlo simulations show that our approach generates clock trees that are highly tolerant to process variations.

The sparsification of the reluctance matrix L-1 (where L denotes the usual inductance matrix L) has been widely used in several recent investigations to make the problem of simulation of interconnects tractable. Although these sparsification techniques work well in practice, the stability of these approximations has not been established, i.e., the sparsified reluctance and inductance matrices are not guaranteed to be positive-definite. In this work, we propose a band matching method that enjoys two advantages: First, we exploit the elegant structure of the inverse of banded matrices so as to construct an approximate inductance matrix L whose band entries match the band entries of original L, and whose inverse is a banded matrix. This approach yields a compact representation of both inductance and reluctance matrices. Second, we establish that the compact approximant L is guaranteed to be positive-definite. Simulation results show that our approach enjoys an approximation accuracy that is comparable to that of existing methods.

Incremental physical design is an important methodology towards achieving design closure for high-performance large-scale circuits. Placement tools must accommodate incremental changes to the layout and netlist due to physical synthesis techniques without perturbing the original metrics. We present an incremental placement approach using floorplan sizing to manage the resources and demands of the whole chip region in order to accommodate the changes due to gate sizing and buffer insertion. The experimental results show that this approach can accommodate a wide range of incremental changes without a loss in wirelength and routability. Most important, it also maintains the stability of a placement such that the convergence of physical synthesis iterations can be greatly enhanced.

SAMBA bus [1] is a high performance bus architecture that can deliver multiple transactions in one bus cycle under single-winner bus arbitration. The bus architecture displays several advantages such as, high bandwidth, low latency, and low performance penalty from arbitration delay, all of which make it more scalable than traditional buses. However, its scalability may be limited by the bus access logic delay. As a module is connected to the bus through its interface unit, which is connected in series on the bus, the bus logic delay increases linearly as the bus size increases. In this paper, we propose to increase the scalability of SAMBA buses through two methods: control signal lookahead and module clustering. The control signal lookahead technique can determine the bus access control signal in advance, thereby reducing the effective delay of each interface unit. Module clustering, on the other hand, can reduce the number of interface units attached to a bus. Experimental results show that combining these two methods can effectively reduce the bus logic delay, and thus increase the scalability of SAMBA buses.

3D packaging via System-On-Package (SOP) is a viable alternative to System-On-Chip (SOC) to meet the rigorous requirements of today's mixed signal system integration. In this work, we propose a 3D module and decap (decoupling capacitance) placement algorithm that simultaneously reduces the power supply noise and wire congestion. We provide efficient algorithms for 3D power supply noise and congestion analysis to guide our 3D module placement process. In addition, we allocate white spaces around the modules that require decaps to suppress the power supply noise while minimizing the area overhead. In our experimentation, we achieve improvements in both decap amount and congestion with only small increase in area, wirelength, and runtime.

We present a statistical based non-tree clock distribution construction algorithm that starts with a tree and incrementally insert cross links, such that the skew variation of the final clock network is within a certain confidence interval under variations in wire width. Monte Carlo simulations show that the robustness of the final clock network can be significantly improved with a small increase in wire length.

In this paper we propose a novel low-power Carry-Select Adder (CSA) design called Cascaded CSA (C2SA). Based on the prediction of the critical path delay of current operation, C2SA can automatically work with one or two clock-cycle latency and a scaled supply voltage to achieve power improvement. Post-layout simulations of a 64-bit C2SA in 180nm Technology show that C2SA can operate at a lower supply voltage, attaining 40.7% energy saving, while maintaining a similar (average) Latency Per Operation (LPO) compared to standard CSA

Recursive bisection is a popular approach for large scale circuit placement problems, combining a high degree of scalability with good results. In this paper, we present a bisection-based approach for both standard cell and mixed block placement; in contrast to prior work, our horizontal cut lines are not restricted to row boundaries. This technique, which we refer to as a fractional cut, simplifies mixed block placement and also avoids a narrow region problem encountered in standard cell placement. Our implementation of these techniques in the placement tool Feng Shui 2.6 retains the speed and simplicity for which bisection is known, while making it competitive with leading methods on standard cell designs. On mixed block placement problems, we obtain substantial improvements over recently published work. Half perimeter wire lengths are reduced by 29% on average, compared to a flow based on Capo and Parquet; compared to mPG-ms, wire lengths are reduced by 26% on average.

Skewed logic circuits belong to a noise-tolerant high-performance static circuit family. Skewed logic circuits can achieve performance comparable to that of Domino logic circuits but with much lower power consumption. Two factors contribute to the reduction in power. First, by exploiting the static nature of skewed logic circuits, we can alleviate the cost of logic duplication which is typically required to overcome the logic reconvergence problem in both Domino logic and skewed logic circuits. Second, a selective clocking scheme can be applied to a skewed logic circuit to reduce the clock load and hence, clock power. In this article, we propose a two-step synthesis scheme of skewed logic circuits. In the first step, an integer linear programming-based approach is presented to overcome the logic reconvergence problem in skewed logic circuits with minimal logic duplication cost. In the second step, a dynamic programming-based heuristic is applied to achieve an optimal selective clocking scheme. Experimental results show that the average power saving of skewed logic circuits over Domino logic circuits is 41.1%.

We propose an integrated architectural and physical planning approach to minimize the current surge in high-performance clock-gated microprocessors. In our approach, we use priority assignment optimization (PAO) and dynamic functional unit (FU) selection (DFS) to balance current demand in the floorplan. Two complementary methods-FU ordering with submodule design and issue pattern management-are also proposed to enhance the above techniques. Experimental results show that at the 0.18-/spl mu/m technology node, the PAO can reduce the peak noise by 11.75% and consequently, the decoupling capacitance (Decap) requirement by 24.22% without any degradation in instructions per cycle (IPC). Moreover, an enhanced DFS reduces the peak noise by 13.39% as well as Decap requirement by 29.58%. Experiments at the 90-nm technology node show that our methodology can further reduce the peak noise and the Decap requirement by 16.57% and 44.85% with PAO, or 18.16% and 47.58% with DFS. We also show that our approach does not increase the clock period for 0.18-/spl mu/m technology and beyond.

Logic duplication, a commonly used synthesis technique to remove trapped inverters in reconvergent paths of Domino circuits, incurs high area and power penalties. In this paper, we propose a synthesis scheme to reduce the duplication cost by allowing inverters in Domino logic under certain timing constraints. In order to guarantee the robustness of such Domino circuits, we perform the reduction of logic duplication at the physical level. Experimental results show significant reduction in duplication cost, which translates into significant improvements in area, power, and/or delay.

This paper presents an efficient t o-stage project-and-balance scheme for passivity-preserving model order reduction. Orthogonal dominant eigenspace projection is implemented by integrating the Smith method and Krylov subspace iteration. It is followed by stochastic balanced truncation herein a novel method, based on the complete separation of stable and unstable invariant subspaces of a Hamiltonian matrix, is used for solving two dual algebraic Riccati equations at the cost of essentially one. A fast-converging quadruple-shift bulge-chasing SR algorithm is also introduced for this purpose. Numerical examples confirm the quality of the reduced-order models over those from conventional schemes.

A very fast Smith-method-based Newton algorithm is introduced for the solution of large-scale continuous-time algebraic Riccati equations (CAREs). When the CARE contains low-rank matrices, as is common in the modeling of physical systems, the proposed algorithm, called the Newton/Smith CARE or NSCARE algorithm, offers significant computational savings over conventional CARE solvers. The effectiveness of the algorithm is demonstrated in the context of VLSI model order reduction, wherein stochastic balanced truncation (SBT) is used to reduce large-scale passive circuits. It is shown that the NSCARE algorithm exhibits guaranteed quadratic convergence under mild assumptions. Moreover, two large-sized matrix factorizations and one large-scale singular value decomposition (SVD), necessary for SBT, can be omitted by utilizing the Smith method output in each Newton iteration, thereby significantly speeding up the model reduction process.

This work introduces an efficient and accurate interconnect simulation technique. A new formulation for typical VLSI interconnect structures is proposed which, in addition to providing a compact set of modeling equations, also offers a potential for exploiting sparsity at the simulation level. Simulations show that our approach can achieve 50 /spl times/ improvement in computation time and memory over INDUCTWISE (which in turn has been shown to be 400 /spl times/ faster than SPICE) while preserving simulation accuracy.

We present a congestion-driven placement flow. First, we consider in the global placement stage the routing demand to replace cells in order to avoid congested regions. Then we allocate appropriate amounts of white space into different regions of the chip according to the congestion map. Finally, a detailed placer is applied to legalize placements while preserving the distributions of white space. Experimental results show that our placement flow can achieve the best routability with the shortest routed wirelength among all publicly available placement tools. Moreover, our white space allocation approach can significantly improve the routabilities of placements generated by other placement tools.

Many current designs contain a large number of standard cells intermixed with larger macro blocks. The range of size in these “mixed block ” designs complicates the placement process considerably; traditional methods produce results that are far from satisfactory. In this paper we extend the traditional recursive bisection standard cell placement tool Feng Shui to directly consider mixed block designs. On a set of recent benchmarks, the new version obtains placements with wire lengths substantially lower than other current tools. Compared to Feng Shui 2.4, the placements of a Capo-based approach have 29 % higher wire lengths, while the placements of mPG are 26 % higher. Run times of our tool are also lower, and the general approach is scalable.

We present an integer linear programming-based approach for solving the logic reconvergence problem in skewed logic circuits with minimal logic duplication cost. A simplification technique is applied to reduce the complexity of the ILP problem greatly so that the run time is more affordable. Experimental results show that an average of 18% of original gates are duplicated in skewed logic circuits, whereas 65% in Domino logic circuits are duplicated. The average power saving over Domino logic circuits is 40.9%.

In this paper, we propose a metric for effective inductive coupling: the matrix (R + jωL)-1, where R and L are the resistance and inductance matrices. We use this metric to analyze the effectiveness of shields on reducing inductive coupling. Our analysis shows how the resistances of shields affect the effective inductive coupling between signal nets. SPICE simulations are carried out to validate the proposed metric.

The determination of the set (or window) of segments that are inductively coupled to a significant degree with a given segment plays a fundamental role in window-based techniques for the extraction of the susceptance of interconnect structures. We present a measure that quantifies the degree of coupling between segments in a window, thereby paving the way for an adaptive scheme for determining the coupling window associated with each segment. This measure has the properties that: (i)~it is well-correlated with the simulation error that is inherent in window-based susceptance extraction techniques, and (ii)~it can be computed efficiently using incremental and computation reuse techniques.

We propose a novel compact BDD structure, called noncrossing ordered BDD (NCOBDD), that can be mapped directly to a regular circuit structure. Compared with other BDD-based regular structures, NCOBDD-mapped circuits reduce the costs of area, power and latency, while preserving the regularity of the structures. We also present an algorithm that uses a top-down level-by-level sweep to construct minimal NCOBDDs. Experimental results show that for asymmetric benchmark circuits, the average reduction on area, power and latency are 61.6%, 53.1% and 69.2%, respectively, compared with yet another decision diagram (YADD) [A. Mukherjee et al., (1999)].

We propose an integrated architectural/physical planning approach to reduce the power supply noise due to current surge in high performance, general-purpose, clock-gated microprocessors. The proposed approach combines dynamic selection of functional units on-the-fly, dynamic issue width scaling and physical planning with soft module, to balance the current demand across layout. Experimental results show that the proposed approach could reduce the peak noise by 6.54% and consequently, the decoupling capacitance requirement by 21.8%. The degradation in IPC (instruction Per Cycle) due to the selection logic and issue width scaling is only 1.86e-7 (without increasing clock cycle period) in 0.18 /spl mu/m technology.

The authors present a novel wire duplication-based interconnect modeling technique. The proposed modeling technique exploits the sparsity of the L/sup -1/ matrix, where L is the inductance matrix, and constructs a sparse and stable equivalent circuit by windowing the original inductance matrix. The resulting circuit model is sparse and exhibits the same stability property as the K method. Numerical results show that the proposed wire duplication model has high accuracy and is more efficient than many existing techniques.

We present a framework for passivity-preserving model reduction for RLC systems that includes, as a special case, the well-known PRIMA model reduction algorithm. This framework provides a new interpretation for PRIMA, and offers a qualitative explanation as to why PRIMA performs remarkably well in practice. In addition, the framework enables the derivation of new error bounds for PRIMA-like methods. We also show how the framework offers a systematic approach to computing reduced-order models that better approximate the original system than PRIMA, while still preserving passivity.

Presents a new passive model reduction algorithm based on the Laguerre expansion of the time response of interconnect networks. We derive expressions for the Laguerre coefficient matrices that minimize a weighted square of the approximation error, and show how these matrices can be computed efficiently using Krylov subspace methods. We discuss the connections between our method and other methods such as PRIMA. Numerical simulations show that our method can better approximate the original model as compared to PRIMA.

We present a unified framework that considers flipflop and repeater insertion and the placement of flip-flop/repeater blocks during RT or higher level design. We introduce the concept of independent feasible regions in which flip-flops and repeaters can be inserted in an interconnect to satisfy both delay and cycle time constraints. Experimental results show that, with flip-flop insertion, we greatly increase the ability of interconnects to meet timing constraints. Our results also show that it is necessary to perform interconnect optimization at early design steps as the optimization will have even greater impact on the chip layout as feature size continually scales down.

In this paper, we present a novel wire duplication-based interconnect modeling technique. The proposed modeling technique exploits the sparsity of the L−1 matrix, where L is the inductance matrix, and constructs a sparse and stable equivalent RLC circuit by windowing the original inductance matrix. The model avoids matrix inversions. Most important, it is more accurate and more efficient than many existing techniques.

In this paper we propose a new exact closed form mutual inductance equation for on-chip interconnects. We express the mutual inductance between two parallel rectangular conductors as a weighted sum of self-inductances. We do not place any restrictions on the alignment of the two parallel rectangular conductors. Moreover they could be co-planar or reside on different layers. Most important, experimental results show that our formula is numerically more stable than that derived by Hoer and Love (1965) for long parallel onchip interconnects.

We investigate the problem of decoupling capacitance (decap) allocation for power supply noise suppression at floorplan level. First, we assume that a floorplan is given and consider the decap placement as a postfloorplan step. Second, we consider the decap placement as an integral part of a floorplanning methodology (noise-aware floorplanning). In both cases, the objective is to minimize the floorplan area while suppressing the power supply noise below the specified limit. Experimental results on MCNC benchmark circuits show that, for postfloorplan decap placement, the white space allocated for decap is about 6%-9% of the chip area for the 0.25-/spl mu/m technology. The power-supply noise is kept below the specified limit. Compared to postfloorplan approach, the peak power-supply noise can be reduced by as much as 40% and the decap budget can be reduced by as much as 21% by using noise-aware floorplanning methodology. The total area is also reduced due to the reduced total decap budget gained from reduced power supply noise.

In this article, we propose new approaches for solving the useful-skew tree (UST) routing problem [Xi and Dai 1997]: clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for the zero-skew tree (ZST) [Edahiro 1992; Chao et al. 1992] and bounded-skew tree (BST) [Cong and Koh 1995; Huang et al. 1995; Kahng and Tsao 1997; Cong et al. 1998] routings; hence, the names UST/DME and Greedy-UST/DME for our UST algorithms. Our novel contribution is that we simultaneously perform skew scheduling and tree routing so that each local skew range is incrementally refined to a skew value that minimizes the wirelength increase during the bottom-up merging phase of DME. As a result, not only is the skew schedule feasible, but also the wirelength increase is minimized at each merging step of clock tree construction. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total routing wirelength.

3-Dimensional (3-D) integration offers numerous advantages over conventional structures. Double-gate (DG) transistors can be fabricated for better device characteristics, and multiple device layers can be vertically stacked for better interconnect performance. In this paper, we explore the suitable device structures and interconnect architectures for multi-device-layer integrated circuits and study how 3-D SOI circuits can better meet the performance and power dissipation requirements projected by ITRS for future technology generations. Results demonstrate that DGSOI circuits can achieve as much as 20% performance gain and 8% power delay product reduction than SGSOI (single-gate SOI). More important, for an interconnect-dominated circuits, multi-device-layer integration offers significant performance improvement. Compared to 2-D integration, most 3-D circuits can be clocked at much higher frequencies (double or even triple). Multi-device-layer circuits, with suitable SOI device structures, can be a viable solution for future low power high performance applications.

We present a solution to the problem of repeater block planning under both delay and signal transition time constraints for a given floorplan. Previous approaches have considered only meeting the target delay of a net. However it has been observed that the repeater planning for meeting the delay target can cause signals on long interconnects to have very slow transition rates. Experimental results show that our new approach satisfies both timing constraints for an average of 79% of all global nets for six MCNC benchmark floorplans studied (at 1 GHz frequency), compared with an average of 22% for the repeater block planner reported previously.

Article Share on Selectively clocked skewed logic (SCSL): low-power logic style for high-performance applications Authors: Naran Sirisantana School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN School of Electrical and Computer Engineering, Purdue University, West Lafayette, INView Profile , Aiqun Cao School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN School of Electrical and Computer Engineering, Purdue University, West Lafayette, INView Profile , Shawn Davidson School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN School of Electrical and Computer Engineering, Purdue University, West Lafayette, INView Profile , Cheng Kok Koh School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN School of Electrical and Computer Engineering, Purdue University, West Lafayette, INView Profile , Kaushik Roy School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN School of Electrical and Computer Engineering, Purdue University, West Lafayette, INView Profile Authors Info & Claims ISLPED '01: Proceedings of the 2001 international symposium on Low power electronics and designAugust 2001Pages 267–270https://doi.org/10.1145/383082.383160Published:06 August 2001Publication History 2citation164DownloadsMetricsTotal Citations2Total Downloads164Last 12 Months1Last 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

We investigate the problem of decoupling capacitance allocation for power supply noise suppression at floorplan level. Decoupling capacitance budgets for the circuit modules are calculated based on the power supply noise estimates. A linear programming technique is used to maximize the allocation of the existing white space in the floorplan for the placement of decoupling capacitors. An incremental heuristic is proposed to insert more white space into the existing floorplan to meet the remaining demand required for decoupling capacitance fabrication. Experimental results on six MCNC benchmark circuits show that the white space allocated for decoupling capacitance is about 6%-12% of the chip area for the 0.25μμ technology, and the power supply noise can be kept below 10%Vdd.

This paper studies interconnect sizing and space (ISS) problem with consideration of coupling capacitance for performance optimization of single or multiple critical nets. We introduce the formulation of symmetric and asymmetric wire sizing. We develop efficient bound computation algorithms for ISS optimization and prove their optimality under general interconnect resistance and capacitance models. Our experiments show that our algorithms are very effective and obtain significant performance improvement compared to previous wire-sizing/spacing algorithms.

In this paper, we study the interconnect layout optimization problem under a higher order resistance-inductance-capacitance model to optimize not only delay, but also waveform for interconnects with nonmonotone signal response in the context of multichip-module global routing. We propose a unified approach that considers topology optimization and waveform optimization simultaneously. Using a new incremental moment-computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. Our algorithm considers a large class of routing topologies, ranging from shortest path Steiner trees to bounded-radius Steiner trees and Steiner routings. We construct a set of required arrival-time Steiner (RATS) trees, providing smooth tradeoffs among signal delay, waveform, and routing area. When combined with the MINOTAUR MCM global router (Cong and Madden, 1998), (Madden, 1998) that we have developed, the RATS-tree solutions prove to be effective in reducing overall routing congestion.

In this paper, we present a repeater block planning algorithm for interconnect-centric floorplanning. We introduce the concept of independent feasible regions for repeaters and derive an analytical formula for their computation. We develop a routability-driven repeater clustering algorithm to perform repeater block planning based on iterative deletion. The goal is to obtain a high-quality solution for the repeater block locations so that performance-driven interconnect synthesis at the routing stage can be carried out with ease while minimizing the chip area. Experimental results show that our method increases the percentage of all global nets that meet their target delays from 67.5% to 85%. Moreover, our approach minimizes the expected routing congestion, making it easier for performance-driven routers to synthesize global nets that require the insertion of repeaters to meet timing constraints.

Circuit interconnect has become a substantial obstacle in the design of high performance systems. In this paper we explore a new routing paradigm that strikes at the root of the interconnect problem by reducing wire lengths directly. We present a non-Manhattan Steiner tree heuristic, obtaining wire length reductions of much as 17% on average, when compared to rectilinear topologies. Moreover, we present a graph-based interconnect optimization algorithm, called the GRATS-tree algorithm, which allows performance optimization beyond what can be obtained through wire length reduction alone. The two tree construction algorithms are integrated into a new global router that allows large scale non-Manhattan design. Although we consider circuit placements performed under rectilinear objectives, our global router can reduce maximum congestion levels by as much as 20%. In general we find that the non-Manhattan approach requires additional Steiner points and bends; realization of non-Manhattan routing structures requires additional vias. We observe that the increase in via cost is much less dramatic than might be expected; the benefits of wire length reduction may outweigh the additional via cost.

We propose new approaches for solving the useful-skew tree (UST) routing problem, Clock routing subject to general skew constraints. The clock layout synthesis engine of our UST algorithms is based on the deferred-merge embedding (DME) paradigm for zero-skew tree and bounded-skew tree routings; hence, the names UST/DME and Greedy-UST/DME for our algorithms. They simultaneously perform skew scheduling and tree routing such that each local skew range is incrementally refined to a skew value that minimizes the wirelength during the bottom-up merging phase of DME. The resulting skew schedule is not only feasible, but is also best for routing in terms of wirelength. The experimental results show very encouraging improvement over the previous BST/DME algorithm on three ISCAS89 benchmarks under general skew constraints in terms of total wirelength.

3-D technology promises higher integration density and lower interconnection complexity and delay. At present, however, not much work on circuit applications has been done due to lack of insight into 3-D circuit architecture and performance. In this paper, we investigate the interconnect distributions of 3-D circuits. We divide the 3-D interconnects into horizontal wires and vertical wires and derive their wire-length distributions, respectively. Based on the stochastic wire-length distributions, we calculate 3-D circuit interconnect delay distribution. We show that 3-D structures effectively reduce the number of long delay nets, significantly reduce the number of repeaters needed, and dramatically improve the performance. With 3-D structures, a circuit can work at a much higher clock rate (double, even triple) than with 2-D. However, we also show that the impacts of vertical wires on chip area and interconnect delay may limit the number of device layers that we can integrate.

In this paper, we propose an approach for the analysis of power supply noise in the frequency domain for power/ground (P/G) networks of tree topologies. We model the P/G network as a linear time invariant (LTI) pseudo-distributed RLC network and the gates (or cells) as time-varying current sources. Voltage fluctuation caused by the switching events is calculated based on the effective impedances seen by the corresponding current sources and the spatial correlation between the nodes of the power network. Superposition is applied to the LTI system to obtain the overall noise spectrum at any node of the power supply network. Inverse Fast Fourier Transformation (IFFT) is then performed on the frequency domain noise spectrum to obtain the time domain noise waveform. The proposed algorithm has a complexity of O(n/sup 2/). Experimental results show that our approach can produce accurate noise waveforms.

In this paper, we propose a novel twisted-bundle layout structure for minimizing inductive coupling noise. In this structure, we create several routing regions and re-order the routing of nets in each of these routing regions. The purpose is to create complementary and opposite current loops in the twisted-bundle layout structure, such that the magnetic fluxes arising from any signal net within a twisted group cancel each other in the current loop of a net of interest. The effectiveness of the twisted-bundle structure in minimizing coupling inductance has been verified by the application of FastHenry extraction on a 16-bit bus structure. We achieve about two orders of magnitude reduction in inductive coupling. SPICE simulations also show that the 16-bit twisted-bundle bus structure is able to maintain high signal integrity at high frequency of operation.

In this paper, we present a noise-immune high-performance static circuit family called skewed logic. Skewed logic circuits in comparison with Domino logic have better scalability and they are more suitable for low voltage applications because of better noise margins. Skewed logic and its variations have been compared with Domino logic in terms of delay, power and dynamic noise immunity. Comparison between skewed and Domino circuits on a 0.25µm 700 MHz 16 × 16 bits pipelined multiplier shows superior properties of skewed circuits over Domino in terms of clock power dissipation and peak current consumption.

In this paper, we propose an event-driven simulation based approach to estimate the worst case IR drop and Ldi/dt inductive noise an the power supply network. The switching noise is modeled as a weighted sum of the switching currents and the rates of change of the switching currents, where the weights are respectively the effective resistance and inductance (on the P/G network) experienced by each switching current. Monte Carlo and genetic algorithm are employed to search for the worst case input vector pair(s) that induce the maximum switching noise. The worst case input patterns are used in the SPICE simulation to verify the switching noise waveforms on the power supply network. Experimental results show that the worst case switching noise on the power supply network for ISCAS85 benchmark circuits implemented in TSMC 0.25 /spl mu/m technology can be as high as 40% of the supply voltage V/sub dd/.

In this paper we present a repeater block planning algorithm for interconnect-centric floorplanning.We introduce the concept of independent feasible regions for repeaters and derive an analytical formula for their computation.We develop a routability-driven repeater clustering algorithm to perform repeater block planning based on iterative deletion.The goal is to obtain a high quality solution for the repeater block locations so that performance-driven interconnect synthesis at the routing stage can be carried out with ease, while minimizing the chip area.Experimental results show that our method increases the percentage of all global nets that meet their target delays from 67.5% in [8] to 85%.Meanwhile, our approach is able to minimize the expected routing congestion, making it easier for performance-driven routers to synthesize global nets that require the insertion of repeaters to meet timing constraints.

We study the minimum-cost bounded-skew routing tree problem under the pathlength (linear) and Elmore delay models. This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew. Our bounded-skew routing algorithm, called the BST/DME algorithm, extends the DME algorithm for exact zero-skew trees via the concept of a merging region . For a prescribed topology , BST/DME constructs a bounded-skew tree (BST) in two phases: (i) a bottom-up phase to construct a binary tree of merging regions which represent the loci of possible embedding points of the internal nodes, and (ii) a top-down phase to determine the exact locations of the internal nodes. We present two approaches to construct the merging regions: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and a dynamic programming-based selection technique to consider merging points that are interior to, as well as on the boundary of, the merging regions. When the topology is not prescribed, we propose a new Greedy -BST/DME algorithm which combines the merging region computation with topology generation. The Greedy-BST/DME algorithm very closely matches the best known heuristics for the zero-skew case and for the unbounded-skew case (i.e., the Steiner minimal tree problem). Experimental results show that our BST algorithms can produce a set of routing solutions with smooth skew and wire length tradeoffs.

The paper presents an efficient approach to perform global interconnect sizing and spacing (GISS) for multiple nets to minimize interconnect delays with consideration of coupling capacitance, in addition to area and fringing capacitances. We introduce the formulation of symmetric and asymmetric wire sizing and spacing. We prove two important results on the symmetric and asymmetric effective fringing properties which lead to a very effective bound computation algorithm to compute the upper and lower bounds of the optimal wire sizing and spacing solution for all nets under consideration. Our experiments show that in most cases the upper and lower bounds meet quickly after a few iterations and we actually obtain the optimal solution. To our knowledge, this is the first in depth study of global wire sizing and spacing for multiple nets with consideration of coupling capacitance. Experimental results show that our GISS solutions lead to substantially better delay reduction than existing single net wire sizing solutions without consideration of coupling capacitance.

Studies the interconnect layout optimization problem under a higher-order RLC model to optimize not just the delay but also the waveform for RLC circuits with non-monotone signal response. We propose a unified approach that considers topology optimization, wire-sizing optimization and waveform optimization simultaneously. Our algorithm considers a large class of routing topologies, ranging from shortest-path Steiner trees to bounded-radius Steiner trees and Steiner routings. We construct a set of required-arrival-time Steiner (RATS) trees, providing a smooth trade-off among signal delay, waveform and routing area. Using a new incremental moment computation algorithm, we interleave topology construction with moment computation to facilitate accurate delay calculation and evaluation of waveform quality. Experimental results show that our algorithm is able to construct a set of topologies providing a smooth trade-off among signal delay, signal settling time, voltage overshoot and routing cost.

In this paper, we study the simultaneous buffer and wire sizing (SBWS) problem for delay and power dissipation minimization. We prove the BS/WS relation for optimal SBWS solutions. This relation leads to a polynomial time algorithm for computing the lower and upper bounds of the optimal SBWS solutions, which enables an efficient optimal algorithm for computing optimal SBWS solutions. We have applied the SBWS algorithms to the clock nets in a spread spectrum IF transceiver chip and HSPICE simulations show that our algorithms can reduce skew and power by a factor of 3.5X and 2.6X, respectively, when compared to the manual layout of the clock nets in the original chip.

We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary of, the merging regions. Our new algorithms allow accurate control of Elmore delay skew, and show the utility of merging points inside merging regions.

In this paper, we present a new clock routing algorithm which minimizes total wirelength under any given path-length skew bound. The algorithm constructs a bounded-skew tree (BST) in two steps: (i) a bottom-up phase to construct a binary tree of shortest-distance feasible regions which represent the loci of possible placements of clock entry points, and (ii) a top-down phase to determine the exact locations of clock entry points. Experimental results show that our clock routing algorithm, named BST/DME, can produce a set of routing solutions with skew and wirelength trade-off.

In this paper, we study the simultaneous driver and wire sizing (SDWS) problem under two objective functions: i) delay minimization only, or ii) combined delay and power dissipation minimization. We present general formulations of the SDWS problem under these two objectives based on the distributed Elmore delay model with consideration of both capacitive power dissipation and short-circuit power dissipation. We show several interesting properties of the optimal SDWS solutions under the two objectives, including an important result which reveals the relationship between driver sizing and optimal wire sizing. These results lead to polynomial time algorithms for computing the lower and upper bounds of optimal SDWS solutions under the two objectives, and efficient algorithms for computing optimal SDWS solutions under the two objectives. We have implemented these algorithms and compared them with existing design methods for driver sizing only or independent driver and wire sizing. Accurate SPICE simulation shows that our methods reduce the delay by up to 12%-49% and power dissipation by 26%-63% compared with existing design methods.>