16196571
Dual-Vt design of FPGAs for subthreshold leakage tolerance
In this paper we propose a dual-Vt FPGA architecture for reduction of subthreshold leakage power. A CAD flow has been proposed based on the dual-Vt assignment algorithm and placement for realizing the dual-Vt FPGA architecture. Logic elements within the logic blocks are the candidates for dual-Vt assignment. We propose an architecture in which there are two kinds of logic blocks, one with all high-Vt logic elements and another with a fixed percentage of high-Vt logic elements. These two kinds of logic blocks are then placed in such a way that the FPGA architecture remains regular. Results indicate that in the ideal case of dual-Vt assignment, over 95% of the logic elements can be assigned high-Vt. Results show that leakage savings of 55% can be achieved. Design tradeoffs for various ratios of the two kinds of logic blocks are investigated. The dual-Vt FPGA CAD flow is intended for development and evaluation of dual-Vt FPGA architectures
14111853
An analytical state dependent leakage power model for FPGAs
In this paper we present a state dependent analytical leakage power model for FPGAs. The model accounts for subthreshold leakage and gate leakage in FPGAs, since these are the two dominant components of total leakage power. The power model takes into account the dependency of gate and subthreshold leakage on the probability of the state of circuit inputs. The leakage power model has two main components, one which computes the probability of a state for a particular FPGA circuit element, and the other which computes the leakage of the FPGA circuit element for a given input using analytical equations. This FPGA power model is particularly important for rapidly analyzing various FPGA architectures across different technology nodes
1885434
Cost and availability tradeoffs in replicated data concurrency control
Techniques for optimizing a static voting type algorithm are presented. Our basic optimization models are based on minimizing communications cost subject to given reliability constraints. Two models are presented; in the first model the reliability constraint is failure tolerance, while in the second it is availability. Other simpler models that are special cases of these two basic models and rise from making simplifying assumptions such as equal vote values or constant inter-site communications costs are also discussed. We describe a semi-exhaustive algorithm and efficient heuristics for solving each model. The algorithms utilize a novel signature based method for identifying equivalent vote combinations, and an efficient procedure for computing availability. Computational results for the various algorithms are also given. Finally, the optimized static algorithm was compared against the available copies method, a dynamic algorithm, to understand the relative performance of the two types of algorithms. We found that if realistic reconfiguration times are assumed, then no one type of algorithm is uniformly better. The factors that influence relative performance have been identified. 16 refs., 2 figs., 10 tabs.
6288937
Iterative error diffusion halftoning using a zero phase error filter
The halftone quality of an error diffusion halftone depends on the error filter response. Apart form the magnitude response being a low pass, it is desirable to have a zero phase response. We propose the iterative error diffusion halftoning algorithm that allows use of non-causal error filter (such as zero phase error filter). We present simulation results showing that the proposed halftoning scheme is substantially better, specially in retaining the sharpness of the edges and in truthfullness.
16229780
A Multiresolution Model of Auditory Excitation Pattern and Its Application to Objective Evaluation of Perceived Speech Quality
This paper proposes a multiresolution model of auditory excitation pattern and applies it to the problem of objective evaluation of subjective wideband speech quality. The model uses wavelet packet transform for time-frequency decomposition of the input signal. The selection of the wavelet packet tree is based on an optimality criterion formulated to minimize a cost function based on the critical band structure. The models of the different auditory phenomena are reformulated for the multiresolution framework. This includes the proposition of duration dependent outer and middle ear weighting, multiresolution spectral spreading, and multiresolution temporal smearing. As an application, the excitation pattern is used to define an objective measure of auditory distortion of a distorted speech signal compared to the undistorted one. The performance of this objective measure is evaluated with a database of various kinds of NOISEX-92 degraded wideband speech signals in predicting the subjective mean opinion score (MOS) and is compared with the fast Fourier transform (FFT)-based ITU-T PESQ P.862.2 algorithm. The proposed measure is found to achieve comparable correlation between subjective MOS and objective MOS as PESQ P.862.2, with a trend suggesting better correlation for the nonstationary degradations compared to the stationary ones. Further refinement of the measure for distortion types other than additive noise is anticipated
46145059
Primal-Dual Algorithms for Connected Facility Location Problems
We consider the Connected Facility Location problem. We are given a graph G = (V, E) with cost ce on edge e, a set of facilities F ? V, and a set of demands D ? V. We are also given a parameter M ? 1. A solution opens some facilities, say F, assigns each demand j to an open facility i(j), and connects the open facilities by a Steiner tree T. The cost incurred is ?i?F fi + ?j?D djci(j)j + M ?e?T ce. We want a solution of minimum cost. A special case is when all opening costs are 0 and facilities may be opened anywhere, i.e., F = V. If we know a facility v that is open, then this problem reduces to the rent-or-buy problem. We give the first primal-dual algorithms for these problems and achieve the best known approximation guarantees. We give a 9-approximation algorithm for connected facility location and a 5-approximation for the rent-or-buy problem. Our algorithm integrates the primal-dual approaches for facility location [7] and Steiner trees [1,2]. We also consider the connected k-median problem and give a constant-factor approximation by using our primal-dual algorithm for connected facility location. We generalize our results to an edge capacitated version of these problems.
8488383
Sorting and selection with structured costs
The study of the effect of priced information on basic algorithmic problems was initiated by M. Charikar et al. (2000). The authors continue the study of sorting and selection in the priced comparison model, i.e., when each comparison has an associated cost, and answer some of the open problems suggested by Charikar et al. If the comparison costs are allowed to be arbitrary, we show that one cannot get good approximation ratios. A different way to assign costs is based on the idea that one can distill out an intrinsic value for each item being compared, such that the cost of comparing two elements is some "well-behaved" or "structured" function of their values. We feel that most practical applications will have some structured cost property. The authors study the problems of sorting and selection (which includes finding the maximum and the median) in the structured cost model. We get a variety of approximation results for these problems, depending on the restrictions we put on the structured costs. We show that it is possible to get much improved results with the structured cost model than the case when we do not have any assumptions on comparison costs.