17009072
Steiner network construction for timing critical nets
Conventionally, signal net routing is almost always implemented as Steiner trees. However, non-tree topology is often superior on timing performance as well as tolerance to open faults and variations. These advantages are particularly appealing for timing critical net routings in nano-scale VLSI designs where interconnect delay is a performance bottleneck and variation effects are increasingly remarkable. We propose Steiner network construction heuristics which can generate either tree or non-tree with different slack-wirelength tradeoff, and handle both long path and short path constraints. Incremental non-tree delay update techniques are developed to facilitate fast Steiner network evaluations. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches
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.
7189153
Antenna avoidance in layer assignment
The sustained progress of very-large-scale-integration (VLSI) technology has dramatically increased the likelihood of the antenna problem in the manufacturing process and calls for corresponding considerations in the routing stage. In this paper, the authors propose a technique that can handle the antenna problem during the layer-assignment (LA) stage, which is an important step between global routing and detailed routing. 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 the LA stage. 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 76% antenna-violation reduction and 99% via-violation reduction.
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.
4103897
Component-wise mapping of media-needs to a distributed presentation environment
Whereas formal specification and verification have shown value by improving reliability and trustworthiness of traditional industrial systems, we made a contribution by applying them to the field of distributed multimedia presentations in an ambient intelligence context. We investigate a mapping problem in which media needs are to be satisfied using given presentation resources. The goal of the investigation is to see whether Broy's stream-based component framework can be used to model media-related interfaces and constraints in an elegant way. The formalization will serve as a framework for the development of an automated mapper that can handle real media needs and real presentation resources. It combines the well-known notations of Z with an underlying concurrency theory. We show that not only verification issues can be handled such as bandwidth and delay constraints, but also architecture-level issues such as network structural media-type compatibilities
15785982
In-Register Duplication: Exploiting Narrow-Width Value for Improving Register File Reliability
Protecting the register value and its data buses is crucial to reliable computing in high-performance microprocessors due to the increasing susceptibility of CMOS circuitry to soft errors induced by high-energy particle strikes. Since the register file is in the critical path of the processor pipeline, any reliable design that increases either the pressure on the register file or the register file access latency is not desirable. In this paper, we propose to exploit narrow-width register values, which present the majority of the generated values, for duplicating a copy of the value within the same data item, called in-register duplication (IRD), eliminating the requirement of additional copy registers. The datapath pipeline is augmented to efficiently incorporate parity encoding and parity checking such that error recovery is seamlessly supported in IRD and the parity checking is overlapped with the execution stage to avoid increasing the critical path. Our experimental evaluation using the SPEC CINT2000 benchmark suite shows that IRD provides superior read-with-duplicate (RWD) and error detection/recovery rates under heavy error injection as compared to previous reliability schemes
52807519
An Adaptive Architecture for Presenting Interactive Media Onto Distributed Interfaces
This paper introduces an adaptive architecture for presenting interactive timed media onto distributed networked devices. The architecture is put into the test in a storytelling application for children. The interactive story is documented in StoryML, an XML-based language, and presented to multiple interface devices organized in an agent-based architecture. This allows the separation of the content from concrete physical devices, the definition of abstract media objects and the automatic adaptation of the same content to different environments of physical devices. Since both the content and the interaction are timed, issues of streaming and synchronization in this architecture are also addressed.
15891166
Energy-conscious compilation based on voltage scaling
As energy consumption has become a majorconstraint in current system design, it is essential to look beyond the traditional low-power circuit and architectural optimizations. Further, software is becoming an increasing portion of embedded/portable systems. Consequently, optimizing the software in conjunction with the underlying low-power hardware features such as voltage scaling is vital.In this paper, we present two compiler-directed energy optimization strategies based on voltage scaling: static voltage scaling and dynamic voltage scaling. In static voltage scaling, the compiler determines a single supply voltage level for the entire input program. We primarily aim at improving the energy consumption of a given code without increasing its execution time. To accomplish this, we employ classical loop-level compiler optimizations. However, we use these optimizations to create opportunities for voltage scaling to save energy, rather than increase program performance.In dynamic voltage scaling, the compiler can select different supply voltage levels for different parts of the code. Our compilation strategy is based on integer linear programming and can accommodate energy/performance constraints. For a benchmark suite of array-based scientific codes and embedded video/image applications, our experiments show average energy savings of 31.8% when static voltage scaling is used. Our dynamic voltage scaling strategy saves 15.3% more energy than static voltage scaling when invoked under the same performance constraints.
9430332
Analyzing data reuse for cache reconfiguration
Classical compiler optimizations assume a fixed cache architecture and modify the program to take best advantage of it. In some cases, this may not be the best strategy because each nest might work best with a different cache configuration and transforming a nest for a given fixed cache configuration may not be possible due to data and control dependences. Working with a fixed cache configuration can also increase energy consumption in loops where the best required configuration is smaller than the default (fixed) one. In this paper, we take an alternate approach and modify the cache configuration for each nest, depending on the access pattern exhibited by the nest. We call this technique compiler-directed cache polymorphism (CDCP). More specifically, in this paper, we make the following contributions. First, we present an approach for analyzing data reuse properties of loop nests. Second, we give algorithms to simulate the footprints of array references in their reuse space. Third, based on our reuse analysis, we present an optimization algorithm to compute the cache configurations for each loop nest. Our experimental results show that CDCP is very effective in finding the near-optimal data cache configurations for different nests in array-intensive applications.