941903
Performance driven global routing through gradual refinement
We propose a method for VLSI interconnect global routing that can optimize routing congestion, delay and number of bends, which are often competing objectives. Routing flexibilities under timing constraints are obtained and exploited to reduce congestion subject to timing constraints. The wire routes are determined through gradual refinement according to probabilistic estimation on congestions so that the congestion is minimized while the number of bends on wires are limited. The experiments on both random generated circuits and benchmark circuits confirm the effectiveness of this method.
18212343
Coupling aware timing optimization and antenna avoidance in layer assignment
The sustained progress of VLSI technology has altered the landscape of routing which is a major physical design stage. For timing driven routings, traditional approaches which consider only wire self capacitance become inadequate since the wire delay is affected more by coupling capacitance in ultra-deep submicron designs. Furthermore, the technology scaling dramatically increases the likelihood of the antenna problem in manufacturing and requests corresponding considerations in the routing stage. In this paper, we propose techniques that can be applied to handle the coupling aware timing and the antenna problem simultaneously during layer assignment which is an important step between global routing and detailed routing. An improved probabilistic coupling capacitance model is suggested for coupling aware timing optimization without performing track assignment. The antenna avoidance problem is modeled as a tree partitioning problem with a linear time optimal algorithm solution. This algorithm is customized to guide antenna avoidance in layer assignment. A linear time optimal jumper insertion algorithm is also derived. Experimental results on benchmark circuits show that the proposed techniques can lead to an average of 270ps timing slack improvement validated by track assignment, 76% antenna violation reduction and 99% via violation reduction.
1271597
An improved AMG-based method for fast power grid analysis
The continuing VLSI technology scaling leads to increasingly significant power supply fluctuations, which needs to be modeled accurately in circuit design and verification. Meanwhile, the huge size of power grid requires its analysis to be fast and highly scalable. Algebraic multigrid (AMG) has been recognized as a promising approach for fast power grid analysis. We propose several techniques to improve AMG-based power grid analysis: (1) dynamic reduction threshold; (2) weighted interpolation; and (3) a new error smoothing scheme. Experimental results on power grid with up to 1.6 million nodes show that these techniques can improve accuracy by over 10 times compared to a reported industrial method while retaining the same fast speed
10406726
Associative Skew Clock Routing for Difficult Instances
In clock network synthesis, sometimes skew constraints are required only within certain groups of clock sinks and do not exist between different groups. This is the so-called associative skew clock routing problem. Although the number of constraints is reduced, the problem becomes more difficult to solve due to the enlarged solution space. The perhaps only previous work used a very primitive delay model and cannot handle difficult instances in which sink groups are intermingled. We reuse existing techniques to solve this problem, including the difficult instances, based on a more accurate and popular delay model. Experimental results show that our algorithm can reduce the total clock routing wirelength by 12% on average compared to greedy-DME which is one of the best zero skew routing algorithms
14326045
A simple yet effective merging scheme for prescribed-skew clock routing
In order to achieve multi-GHz operation frequency for VLSI design, clock networks need to be designed in a very elaborated manner and be able to deliver prescribed useful skews rather than merely zero-skew. Although traditional zero-skew clock muting methods can be extended directly to prescribed skews, they tend to result in excessive wirelength as the differences among delay-targets for clock sinks are neglected. In this paper, we propose the maximum delay-target and minimum merging-cost merging scheme for prescribed-skew clock routing. This scheme is simple yet surprisingly effective on wirelength reduction. Experimental results on benchmark circuits show that our merging scheme yields 53%-61% wirelength reduction compared to traditional clock routing methods.
35082628
Porosity-aware buffered Steiner tree construction
In order to achieve timing closure on increasingly complex IC designs, buffer insertion needs to be performed on thousands of nets within an integrated physical synthesis system. Modern designs may contain large blocks which severely constrain the buffer locations. Even when there may appear to be space for buffers in the alleys between large blocks, these regions are often densely packed or may be needed later to fix critical paths. Therefore, within physical synthesis, a buffer insertion scheme needs to be aware of the porosity of the existing layout to be able to decide when to insert buffers in dense regions to achieve critical performance improvement and when to utilize the sparser regions of the chip. This work addresses the problem of finding porosity-aware buffering solutions by constructing a "smart Steiner tree" to pass to van Ginneken's topology-based algorithm. This flow allows one to fully integrate the algorithm into a physical synthesis system without paying an exorbitant runtime penalty. We show that significant improvements on timing closure are obtained when this approach is integrated into a physical synthesis system.
18592986
Simulation Study of TCP Performance Over Mobile IPV4 and Mobile IPV6
Mobile IPv6 (MIPv6) is a protocol to deal with mobility for the next generation Internet (IPv6). However, the performance of MIPv6 has not yet been extensively investigated. Knowledge of how MIPv6 affects TCP performance, especially in comparison with MIPv4, can provide directions for further improvement. In this report, an intensive simulation study of TCP performance over MIPv4 and MIPv6 has been conducted. Simulation using the famous network simulator NS-2 will be used to highlight differences when TCP is used in hybrid wireless environment, over these two Mobile IP protocols. Initial simulation has shown a solid improvement in performance for MIPv6 when IPv6 Route Optimisation features are used. During the course of simulation, a consistent event causing dropped TCP throughput was identified. Out of order arrival of packets would occur when the mobile node initiated a handover. This out of order arrival invokes TCP congestion control falsely which reduces throughput. The difference in overall throughput of MIPv4 compared to MIPv6 is roughly proportional to the difference in packet size attributed to IPv6’s increased header size. Another contribution of this work is to provide modifications and new functions such as node processing time, to the NS-2 simulator to make such investigation possible. To the best of our knowledge, no similar publication has been reported.
15489348
A Gradient Based Weighted Averaging Method for Estimation of Fingerprint Orientation Fields
Estimation of orientation fields is an essential module in a fingerprint recognition system. Conventional gradient based approaches are popular but very sensitive to noise. In this paper, we propose a new implementation that is more resistant to noise. Our basic idea is to conduct redundant estimation over four overlapping neighborhoods for each target block. Following this idea, we devise a weighted averaging scheme operated on the base blocks directly. Thus, each block (including the target one) in the overlapping neighborhoods has different impact on estimation of the dominant orientation fields. Our preliminary experiment results suggest that the proposed weighted averaging algorithm is more robust against noise in comparison with other gradient based methods.
14468769
Exploring Wakeup-Free Instruction Scheduling
Design of wakeup-free issue queues is becoming desirable due to the increasing complexity associated with broadcast-based instruction wakeup. The effectiveness of most wakeup-free issue queue designs is critically based on their success in predicting the issue latency of an instruction accurately. Consequently, the goal of this paper is to explore the predictability of instruction issue latency under different design constraints and to identify the impediments to performance in such wakeup-free architectures. Our results indicate that structural problems in promoting instructions to the head of the instruction queue from where they are issued in wakeup-free architectures, the limited number of candidate instructions that can be considered for instruction issue, and the resource conflicts due to non-availability of issue ports all have a significant impact in degrading the performance of broadcast free architectures. Based on these observation, we explore an architecture that attempts to overcome the structural limitations by employing traditional selection logic and by using pre-check logic to reduce the impact of resource conflicts while still employing a wakeup-free strategy based on predicted instruction issue latencies. Finally, we improve this technique by limiting the selection logic to a small segment of the issue queue.
8637956
Dense and Switched Modular Primitives for Bond Graph Model Design
This paper suggests dense and switched modular primitives for a bond-graph-based GP design framework that automatically synthesizes designs for multi-domain, lumped parameter dynamic systems. A set of primitives is sought that will avoid redundant junctions and elements, based on preassembling useful functional blocks of bond graph elements and (optionally) using a switched choice mechanism for inclusion of some elements. Motivation for using these primitives is to improve performance through greater search efficiency and thereby to reduce computational effort. As a proof of concept for this approach, an eigenvalue assignment problem, which is to find bond graph models exhibiting minimal distance errors from target sets of eigenvalues, was tested and showed improved performance for various sets of eigenvalues.
7383154
Asymmetrically Banked Value-Aware Register Files
Designing high-performance low-power register files is of critical importance to the continuation of current performance advances in wide-issue and deeply-pipelined superscalar microprocessors. In this paper, we propose a new microarchitecture, the asymmetrically-banked value-aware register file (AB-VARF), to exploit the prevailing narrow-width register values for low-latency and power-efficient register file designs. The register bit-widths of different banks in our AB-VARF register files are specifically customized to capture different narrow-width values. Augmented with a value width predictor, the register renaming logic is slightly tuned to rename predicted narrow-width registers to the corresponding narrow-width banks. Our experimental evaluation with SPEC CINT2000 benchmark suites shows that AB-VARF reduces the energy consumption by 92.6% over a conventional register file, on the average, at the cost of a 6.6% performance loss to an ideal 1-cycle monolithic register file.