5155570
Low-power repeater insertion with both delay and slew rate constraints
In this paper, a novel repeater insertion algorithm is presented to minimize the power dissipation of interconnect trees under given timing budgets and slew rate constraints. In contrast to traditional bottom-up dynamic programming approaches, the proposed algorithm combines a Lagrangian relaxation framework and a graph-based search method to derive possible solutions in a top-down fashion. As a result, it is capable of analyzing repeater slew rates efficiently. In addition, our scheme incorporates accurate circuit models and is therefore able to capture the precise delay and slew rate information, leading to high-quality interconnect designs. We have applied our scheme to interconnects of different topologies and various timing and slew rate constraints. Experimental results demonstrate the effectiveness of our approach in comparison with previous low-power repeater insertion schemes. Under tight timing constraints, our scheme can always derive repeater insertion solutions that meet both delay and slew rate requirements, whereas other schemes often fail. Under loose timing constraints, our algorithm achieves up to a 23% average power dissipation reduction for different interconnects specifications with shorter runtimes
17545097
Design of Rotary Clock Based Circuits
Rotary clock technique has been shown to reduce the power dissipation of clock distribution by up to 80%. However, to our knowledge, no practical digital synchronous circuit has been designed that utilizes the rotary technique due to the multi-phase nature of rotary clock signals and the strong coupling between a rotary clock network and the circuit it drives. In this paper, we make the first attempt to design rotary based circuit by proposing a unified clock and circuit design methodology. Given a sequential circuit and a clock frequency, our scheme derives a rotary clock network and a functionally equivalent circuit so that they can be integrated to operate reliably at the target frequency. We have applied our scheme to design several rotary clock based DSP modules. Simulation results show that all designs operate correctly with no timing violation. Compared with designs using conventional clock trees, our designs achieve an average clock power saving of more than 70%.
13241066
Retiming and clock scheduling for digital circuit optimization
This paper investigates the application of simultaneous retiming and clock scheduling for optimizing synchronous circuits under setup and hold constraints. Two optimization problems are explored: (1) clock period minimization and (2) tolerance maximization to clock-signal delay variations. Exact mixed-integer linear programming formulations and efficient heuristics are given for both problems. When both long and short paths are considered, circuits optimized by the combined application of retiming and clock scheduling can achieve shorter clock periods or demonstrate greater tolerance to clock-signal delay variations than circuits optimized by retiming or clock scheduling. Experiments with benchmark circuits demonstrate the effectiveness of the combined optimization. In comparison with the best result obtained by either of the two optimizations, the joint application of retiming and clock scheduling increased operating speeds by more than 8% on the average. It also increased tolerance to clock delay variations by an average of 12% over a broad range of target clock frequencies. Larger relative improvements were achieved for shorter clock periods, thus suggesting that simultaneous retiming and clock scheduling can play an important role in high-speed design.
10662727
Power macromodeling of global interconnects considering practical repeater insertion
In this paper, we present a simple yet highly effective power macromodeling technique for global interconnects that considers optimal repeater insertion. Specifically,our model estimates the interconnect power dissipation from the interconnect length, the timing budget, the repeater location flexibility, and the signal activity using an analytical function that is derived for a given repeater library and fabrication technology. In experiments with different standard cell libraries, the average error of our technique is less than 2%.
1752593
RITC: repeater insertion with timing target compensation
This paper investigates the problem of repeater insertion for global interconnects under given timing constraints. A novel technique is proposed to aggressively reduce the positive timing slack for maximal repeater reduction while maintaining timing closure. Our scheme is both fast and effective due to the judicious combination of accurate SPICE simulations and the simple Elmore delay model. In comparison with other repeater insertion solvers, our scheme achieves up to 41% reduction in total repeater width in comparable runtimes.
26613748
A Markov chain sequence generator for power macromodeling
In this paper, we present a novel sequence generator based on a Markov chain model. Specifically, we formulate the problem of generating a sequence of vectors with given average input probability p, average transition density d, and spatial correlation s as a transition matrix computation problem, in which the matrix elements are subject to constraints derived from the specified statistics. We also give a practical heuristic that computes such a matrix and generates a sequence of l n-bit vectors in O(nl + n/sup 2/) time. Derived from a strongly mixing Markov chain, our generator yields binary vector sequences with accurate statistics, high uniformity, and high randomness. Experimental results show that our sequence generator can cover more than 99% of the parameter space. Sequences of 2,000 48-bit vectors are generated in less than 0.05 seconds, with average deviations of the signal statistics p, d, and s equal to 1.6%, 1.8%, and 2.8%, respectively. Our generator enables the detailed study of power macromodeling. Using our tool and the ISCAS-85 benchmark circuits, we have assessed the sensitivity of power dissipation to the three input statistics p, d, and s. Our investigation reveals that power is most sensitive to transition density, while only occasionally exhibiting high sensitivity to signal probability and spatial correlation. Our experiments also show that input signal imbalance can cause estimation errors as high as 100% in extreme cases, although errors are usually within 25%.
18539924
Weights Modulo a Prime Power in Divisible Codes and a Related Bound
In this paper, we generalize the theorem given by R. M. Wilson about weights modulo pt in linear codes to a divisible code version. Using a similar idea, we give an upper bound for the dimension of a divisible code by some divisibility property of its weight enumerator modulo pe. We also prove that this bound implies Ward's bound for divisible codes. Moreover, we see that in some cases, our bound gives better results than Ward's bound
7819313
Constrained Fairing for Meshes
In this paper, we present a novel fairing algorithm for the removal of noise from uniform triangular meshes without shrinkage and serious distortion. The key feature of this algorithm is to keep all triangle centers invariant at each smoothing step by including some constraints in the energy minimization functional. The constrained functional is then minimized efficiently using an iterative method. Further, we apply this smoothing technique to a multiresolution representation to remove arbitrary levels of detail. A volume-preserving decimation algorithm is presented to generate the multiresolution representation. The experimental results demonstrate the combined algorithm's stability and efficiency.
9148979
Face detection using spectral histograms and SVMs
We present a face detection method using spectral histograms and support vector machines (SVMs). Each image window is represented by its spectral histogram, which is a feature vector consisting of histograms of filtered images. Using statistical sampling, we show systematically the representation groups face images together; in comparison, commonly used representations often do not exhibit this necessary and desirable property. By using an SVM trained on a set of 4500 face and 8000 nonface images, we obtain a robust classifying function for face and nonface patterns. With an effective illumination-correction algorithm, our system reliably discriminates face and nonface patterns in images under different kinds of conditions. Our method on two commonly used data sets give the best performance among recent face-detection ones. We attribute the high performance to the desirable properties of the spectral histogram representation and good generalization of SVMs. Several further improvements in computation time and in performance are discussed.
893749
A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks
Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm
292448
Efficient Network Utilization for Multimedia Wireless Networks
In this paper, we present an access scheme to satisfy the QoS requirements for two classes of traffic during the contention phase of packet-switched wireless communications. In the proposed scheme, difierent classes of users contend with other users for resources based on controlled class-dependent permission probabilities. We prove that our algorithm is stable for a large class of arrival processes. Under certain QoS requirements, we derive an upper-bound on the throughput for a general class of random access algorithms. We show that the throughput of our algorithm asymptotically approaches this upper-bound. We also show, through numerical examples, that our algorithm achieves high network utilization.