Search on a Hypercubic Lattice using Quantum Random Walk

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

Power Efficient Redundant Execution for Chip Multiprocessor

This paper describes the design of a power efficient microarchitecture for transient fault detection in chip multiprocessors (CMPs) We introduce a new per-core dynamic voltage and frequency scaling (DVFS) algorithm for our architecture that significantly reduces power dissipation for redundant execution with a minimal performance overhead. Using cycle accurate simulation combined with a simple first order power model, we estimate that our architecture reduces dynamic power dissipation in the redundant core by an mean value of 79% and a maximum of 85% with an associated mean performance overhead of only 1:2%

Generation of Minimum Leakage Input Vectors with Constrained NBTI Degradation

Technology scaling has caused Negative Bias Temperature Instability (NBTI) to emerge as a major circuit reliability concern. Simultaneously leakage power is becoming a greater fraction of the total power dissipated by logic circuits. As both NBTI and leakage power are highly dependent on vectors applied at the circuit’s inputs, they can be minimized by applying carefully chosen input vectors during periods when the circuit is in standby or idle mode. Unfortunately input vectors that minimize leakage power are not the ones that minimize NBTI degradation, so there is a need for a methodology to generate input vectors that minimize both of these variables.This paper proposes such a systematic methodology for the generation of input vectors which minimize leakage power under the constraint that NBTI degradation does not exceed a specified limit. These input vectors can be applied at the primary inputs of a circuit when it is in standby/idle mode and are such that the gates dissipate only a small amount of leakage power and also allow a large majority of the transistors on critical paths to be in the “recovery” phase of NBTI degradation. The advantage of this methodology is that allowing circuit designers to constrain NBTI degradation to below a specified limit enables tighter guardbanding, increasing performance. Our methodology guarantees that the generated input vector dissipates the least leakage power among all the input vectors that satisfy the degradation constraint. We formulate the problem as a zero-one integer linear program and show that this formulation produces input vectors whose leakage power is within 1% of a minimum leakage vector selected by a search algorithm and simultaneously reduces NBTI by about 5.75% of maximum circuit delay as compared to the worst case NBTI degradation. Our paper also proposes two new algorithms for the identification of circuit paths that are affected the most by NBTI degradation. The number of such paths identified by our algorithms are an order of magnitude fewer than previously proposed heuristics.

FREP: A Soft-Error Resilient Pipelined RISC Architecture

Soft error has become one of the major areas of attention with the device scaling and large scale integration. Lot of variants for superscalar architecture were proposed with focus on program re-execution, thread re-execution and instruction re-execution. In this paper we proposed a fault tolerant micro-architecture of pipelined RISC. The proposed architecture, Floating Resources Extended pipeline (FREP), re-executes the instructions using extended pipeline stages. The instructions are re-executed by hybrid architecture with a suitable combination of space and time redundancy.

Generalized asymptotic expansions for the wavenumbers in infinite flexible in vacuo orthotropic cylindrical shells

Analytical expressions are found for the wavenumbers and resonance frequencies in flexible, orthotropic shells using the asymptotic methods. These expressions are valid for arbitrary circumferential orders n. The Donnell-Mushtari shell theory is used to model the dynamics of the cylindrical shell. Initially, an in vacuo cylindrical isotropic shell is considered and expressions for all the wavenumbers (bending, near-field bending, longitudinal and torsional) are found. Subsequently, defining a suitable orthotropy parameter epsilon, the problem of wave propagation in an orthotropic shell is posed as a perturbation on the corresponding problem for an isotropic shell. Asymptotic expressions for the wavenumbers in the in vacuo orthotropic shell are then obtained by treating epsilon as an expansion parameter. In both cases (isotropy and orthotropy), a frequency-scaling parameter (eta) and Poisson's ratio (nu) are used to find elegant expansions in the different frequency regimes. The asymptotic expansions are compared with numerical solutions in each of the cases and the match is found to be good. The main contribution of this work lies in the extension of the existing literature by developing closed-form expressions for wavenumbers with arbitrary circumferential orders n in the case of both, isotropic and orthotropic shells. Finally, we present natural frequency expressions in finite shells (isotropic and orthotropic) for the axisymmetric mode and compare them with numerical and ANSYS results. Here also, the comparison is found to be good. (C) 2011 Elsevier Ltd. All rights reserved.

On the Limits of Spatial Reuse and Cooperative Communication for Dense Wireless Networks

We consider a dense ad hoc wireless network comprising n nodes confined to a given two dimensional region of fixed area. For the Gupta-Kumar random traffic model and a realistic interference and path loss model (i.e., the channel power gains are bounded above, and are bounded below by a strictly positive number), we study the scaling of the aggregate end-to-end throughput with respect to the network average power constraint, P macr, and the number of nodes, n. The network power constraint P macr is related to the per node power constraint, P macr, as P macr = np. For large P, we show that the throughput saturates as Theta(log(P macr)), irrespective of the number of nodes in the network. For moderate P, which can accommodate spatial reuse to improve end-to-end throughput, we observe that the amount of spatial reuse feasible in the network is limited by the diameter of the network. In fact, we observe that the end-to-end path loss in the network and the amount of spatial reuse feasible in the network are inversely proportional. This puts a restriction on the gains achievable using the cooperative communication techniques studied in and, as these rely on direct long distance communication over the network.

Jointly Optimal Power Control and Hop Length for a Single Cell, Dense, Ad hoc Wireless Network

We consider a dense, ad hoc wireless network confined to a small region, such that direct communication is possible between any pair of nodes. The physical communication model is that a receiver decodes the signal from a single transmitter, while treating all other signals as interference. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organise into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first argue that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc network (described above) as a single cell, we study the optimal hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (Thetaopt bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form dopt(Pmacrt) x Thetaopt with dopt scaling as Pmacrt 1 /eta, where Pmacrt is the available time average transmit power and eta is the path loss exponent. Under certain conditions on the fading distribution, we then pro- - vide a simple characterisation of the optimal operating point.

Multiclass Core Vector Machine

Even though several techniques have been proposed in the literature for achieving multiclass classification using Support Vector Machine(SVM), the scalability aspect of these approaches to handle large data sets still needs much of exploration. Core Vector Machine(CVM) is a technique for scaling up a two class SVM to handle large data sets. In this paper we propose a Multiclass Core Vector Machine(MCVM). Here we formulate the multiclass SVM problem as a Quadratic Programming(QP) problem defining an SVM with vector valued output. This QP problem is then solved using the CVM technique to achieve scalability to handle large data sets. Experiments done with several large synthetic and real world data sets show that the proposed MCVM technique gives good generalization performance as that of SVM at a much lesser computational expense. Further, it is observed that MCVM scales well with the size of the data set.

Quantum Random Walks without Coin Toss

We construct a quantum random walk algorithm, based on the Dirac operator instead of the Laplacian. The algorithm explores multiple evolutionary branches by superposition of states, and does not require the coin toss instruction of classical randomised algorithms. We use this algorithm to search for a marked vertex on a hypercubic lattice in arbitrary dimensions. Our numerical and analytical results match the scaling behaviour of earlier algorithms that use a coin toss instruction.

Wavelet based spectral finite element modelling and detection of de-lamination in composite beams

In this paper, a model for composite beam with embedded de-lamination is developed using the wavelet based spectral finite element (WSFE) method particularly for damage detection using wave propagation analysis. The simulated responses are used as surrogate experimental results for the inverse problem of detection of damage using wavelet filtering. The WSFE technique is very similar to the fast fourier transform (FFT) based spectral finite element (FSFE) except that it uses compactly supported Daubechies scaling function approximation in time. Unlike FSFE formulation with periodicity assumption, the wavelet-based method allows imposition of initial values and thus is free from wrap around problems. This helps in analysis of finite length undamped structures, where the FSFE method fails to simulate accurate response. First, numerical experiments are performed to study the effect of de-lamination on the wave propagation characteristics. The responses are simulated for different de-lamination configurations for both broad-band and narrow-band excitations. Next, simulated responses are used for damage detection using wavelet analysis.

Influence of Spatial Scales on the Performance of Saturated Subsurface Flow and Transport Models

Numerical modeling of saturated subsurface flow and transport has been widely used in the past using different numerical schemes such as finite difference and finite element methods. Such modeling often involves discretization of the problem in spatial and temporal scales. The choice of the spatial and temporal scales for a modeling scenario is often not straightforward. For example, a basin-scale saturated flow and transport analysis demands larger spatial and temporal scales than a meso-scale study, which in turn has larger scales compared to a pore-scale study. The choice of spatial-scale is often dictated by the computational capabilities of the modeler as well as the availability of fine-scale data. In this study, we analyze the impact of different spatial scales and scaling procedures on saturated subsurface flow and transport simulations.

Voltage and Temperature-Aware SSTA Using Neural Network Delay Model

With the emergence of voltage scaling as one of the most powerful power reduction techniques, it has been important to support voltage scalable statistical static timing analysis (SSTA) in deep submicrometer process nodes. In this paper, we propose a single delay model of logic gate using neural network which comprehensively captures process, voltage, and temperature variation along with input slew and output load. The number of simulation programs with integrated circuit emphasis (SPICE) required to create this model over a large voltage and temperature range is found to be modest and 4x less than that required for a conventional table-based approach with comparable accuracy. We show how the model can be used to derive sensitivities required for linear SSTA for an arbitrary voltage and temperature. Our experimentation on ISCAS 85 benchmarks across a voltage range of 0.9-1.1V shows that the average error in mean delay is less than 1.08% and average error in standard deviation is less than 2.85%. The errors in predicting the 99% and 1% probability point are 1.31% and 1%, respectively, with respect to SPICE. The two potential applications of voltage-aware SSTA have been presented, i.e., one for improving the accuracy of timing analysis by considering instance-specific voltage drops in power grids and the other for determining optimum supply voltage for target yield for dynamic voltage scaling applications.

Insulating State and Breakdown of Fermi Liquid Description in Molecular-Scale Single-Crystalline Wires of Gold

Electrical transport measurements on ultrathin single-crystalline Au nanowires, synthesized via a wet chemical route, show an unexpected insulating behavior. The linear response electrical resistance exhibits a power-law dependence on temperature. In addition, the variation of current over a wide range of temperature and voltage obeys a universal scaling relation that provides compelling evidence for a non-Fermi liquid behavior. Our results demonstrate that the quantum ground state In ultrathin nanowires of simple metallic systems can be radically different from their bulk counterparts and can be described In terms of a Tomonaga-Luttinger liquid (TLL), in the presence of remarkably strong electron-electron interactions.

Ferromagnetic transition and specific heat of Pr(0.6)Sr(0.4)MnO(3)

The critical properties of orthorhombic Pr(0.6)Sr(0.4)MnO(3) single crystals were investigated by a series of static magnetization measurements along the three different crystallographic axes as well as by specific heat measurements. A careful range-of-fitting-analysis of the magnetization and susceptibility data obtained from the modified Arrott plots shows that Pr(0.6)Sr(0.4)MnO(3) has a very narrow critical regime. Nevertheless, the system belongs to the three-dimensional (3D) Heisenberg universality class with short-range exchange. The critical exponents obey Widom scaling and are in excellent agreement with the single scaling equation of state M(H,epsilon) = vertical bar epsilon vertical bar(beta) f(+/-)(H/vertical bar epsilon vertical bar((beta+gamma)); with f(+) for T > T(c) and f(-) for T < T(c). A detailed analysis of the specific heat that account for all relevant contributions allows us to extract and analyze the contribution related to the magnetic phase transition. The specific heat indicates the presence of a linear electronic term at low temperatures and a prominent contribution from crystal field excitations of Pr. A comparison with data from literature for PrMnO(3) shows that a Pr-Mn magnetic exchange is responsible for a sizable shift in the lowest lying excitation.

Energy-efficient redundant execution for chip multiprocessors

Relentless CMOS scaling coupled with lower design tolerances is making ICs increasingly susceptible to wear-out related permanent faults and transient faults, necessitating on-chip fault tolerance in future chip microprocessors (CMPs). In this paper, we describe a power-efficient architecture for redundant execution on chip multiprocessors (CMPs) which when coupled with our per-core dynamic voltage and frequency scaling (DVFS) algorithm significantly reduces the energy overhead of redundant execution without sacrificing performance. Our evaluation shows that this architecture has a performance overhead of only 0.3% and consumes only 1.48 times the energy of a non-fault-tolerant baseline.