5855159
Skew spreading for peak current reduction
This paper presents a circuit optimization technique called skewspreading. Given an edge-triggered sequential circuit, skew spreadingderives the required clock arrival times for all registers so that theskews are distributed evenly in a preselected time window without changing the operating frequency of the circuit. Skew spreading is ideal for peak current reduction, since it distributes clock activities and the ensuing signal activities widely in time. We have developed a skew spreading algorithm and applied it to a suite of benchmark circuits. Simulation results demonstrate that the variance of the resulting skew from the uniform distribution can be reduced to 4% on the average. In comparison to other gate-level peak current reduction techniques, our scheme achieves an average improvement of 17% with a speedup of up to 13.9 times.
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%.
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.
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%.
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
36513177
A Bayesian network approach to explaining time series with changing structure
Many examples exist of multivariate time series where dependencies between variables change over time. If these changing dependencies are not taken into account, any model that is learnt from the data will average over the different dependency structures. Paradigms that try to explain underlying processes and observed events in multivariate time series must explicitly model these changes in order to allow non-experts to analyse and understand such data. In this paper we have developed a method for generating explanations in multivariate time series that takes into account changing dependency structure. We make use of a dynamic Bayesian network model with hidden nodes. We introduce a representation and search technique for learning such models from data and test it on synthetic time series and real-world data from an oil refinery, both of which contain changing underlying structure. We compare our method to an existing EM-based method for learning structure. Results are very promising for our method and we include sample explanations, generated from models learnt from the refinery dataset.
6032766
A Novel Volume Constrained Smoothing Method for Meshes
In general, mesh smoothing is performed by minimizing the discrete energy function for the surface. One of the major problems in mesh smoothing is to prevent the mesh from shrinking. In this paper, we propose a novel volume constraint to address the shrinking problem in mesh smoothing. Our key observation is that the mesh can be efficiently smoothed patch by patch in a signal processing manner, and then a local volume preserving constraint can be easily imposed to the energy minimization problem associated with the small patch, called the smoothing stencil, so as to effectively avoid the mesh shrinkage. In our implementation, the smoothing stencil is the 1-ring neighboring region of an edge or a triangle. And the constrained minimization problem is solved by a 2-step approximation method for efficiency. A series of examples demonstrate that the proposed smoothing method can be applied to remove noise from a mesh or remove rough detail from an original mesh to generate a smooth model in object reconstruction and geometry modeling.
848425
Location awareness in unstructured peer-to-peer systems
Peer-to-peer (P2P) computing has emerged as a popular model aiming at further utilizing Internet information and resources. However, the mechanism of peers randomly choosing logical neighbors without any knowledge about underlying physical topology can cause a serious topology mismatch between the P2P overlay network and the physical underlying network. The topology mismatch problem brings great stress in the Internet infrastructure. It greatly limits the performance gain from various search or routing techniques. Meanwhile, due to the inefficient overlay topology, the flooding-based search mechanisms cause a large volume of unnecessary traffic. Aiming at alleviating the mismatching problem and reducing the unnecessary traffic, we propose a location-aware topology matching (LTM) technique. LTM builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries. LTM is scalable and completely distributed in the sense that it does not require any global knowledge of the whole overlay network. The effectiveness of LTM is demonstrated through simulation studies.
16058917
Learning Dynamic Bayesian Networks from Multivariate Time Series with Changing Dependencies
Many examples exist of multivariate time series where dependencies between variables change over time. If these changing dependencies are not taken into account, any model that is learnt from the data will average over the different dependency structures. Paradigms that try to explain underlying processes and observed events in multivariate time series must explicitly model these changes in order to allow non-experts to analyse and understand such data. In this paper we have developed a method for generating explanations in multivariate time series that takes into account changing dependency structure. We make use of a dynamic Bayesian network model with hidden nodes. We introduce a representation and search technique for learning such models from data and test it on synthetic time series and real-world data from an oil refinery, both of which contain changing underlying structure. We compare our method to an existing EM-based method for learning structure. Results are very promising for our method and we include sample explanations, generated from models learnt from the refinery dataset.
12770105
A tractable probabilistic model for Affymetrix probe-level analysis across multiple chips
MOTIVATION
Affymetrix GeneChip arrays are currently the most widely used microarray technology. Many summarization methods have been developed to provide gene expression levels from Affymetrix probe-level data. Most of the currently popular methods do not provide a measure of uncertainty for the expression level of each gene. The use of probabilistic models can overcome this limitation. A full hierarchical Bayesian approach requires the use of computationally intensive MCMC methods that are impractical for large datasets. An alternative computationally efficient probabilistic model, mgMOS, uses Gamma distributions to model specific and non-specific binding with a latent variable to capture variations in probe affinity. Although promising, the main limitations of this model are that it does not use information from multiple chips and does not account for specific binding to the mismatch (MM) probes.


RESULTS
We extend mgMOS to model the binding affinity of probe-pairs across multiple chips and to capture the effect of specific binding to MM probes. The new model, multi-mgMOS, provides improved accuracy, as demonstrated on some bench-mark datasets and a real time-course dataset, and is much more computationally efficient than a competing hierarchical Bayesian approach that requires MCMC sampling. We demonstrate how the probabilistic model can be used to estimate credibility intervals for expression levels and their log-ratios between conditions.


AVAILABILITY
Both mgMOS and the new model multi-mgMOS have been implemented in an R package, which is available at http://www.bioinf.man.ac.uk/resources/puma.