Search results for "Markov"

Unbiased Branches: An Open Problem

2007

The majority of currently available dynamic branch predictors base their prediction accuracy on the previous k branch outcomes. Such predictors sustain high prediction accuracy but they do not consider the impact of unbiased branches, which are difficult-to-predict. In this paper, we evaluate the impact of unbiased branches in terms of prediction accuracy on a range of branch difference predictors using prediction by partial matching, multiple Markov prediction and neural-based prediction. Since our focus is on the impact that unbiased branches have on processor performance, timing issues and hardware costs are out of scope of this investigation. Our simulation results, with the SPEC2000 in…

Self-stabilizing Balls & Bins in Batches

2016

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…

Greedy versus Dynamic Channel Aggregation Strategy in CRNs: Markov Models and Performance Evaluation

2011

Part 1: - PE-CRN 2011 Workshop; International audience; In cognitive radio networks, channel aggregation techniques which aggregate several channels together as one channel have been proposed in many MAC protocols. In this paper, we consider elastic data traffic and spectrum adaptation for channel aggregation, and propose two new strategies named as Greedy and Dynamic respectively. The performance of channel aggregation represented by these strategies is evaluated using continuous time Markov chain models. Moreover, simulation results based on various traffic distributions are utilized in order to evaluate the validity and preciseness of the mathematical models.

model reduction for continuous-time Markovian jump systems with incomplete statistics of mode information

2013

This paper investigates the problem of model reduction for a class of continuous-time Markovian jump linear systems with incomplete statistics of mode information, which simultaneously considers the exactly known, partially unknown and uncertain transition rates. By fully utilising the properties of transition rate matrices, together with the convexification of uncertain domains, a new sufficient condition for performance analysis is first derived, and then two approaches, namely, the convex linearisation approach and the iterative approach, are developed to solve the model reduction problem. It is shown that the desired reduced-order models can be obtained by solving a set of strict linear…

Approximate survival probability determination of hysteretic systems with fractional derivative elements

2018

Abstract A Galerkin scheme-based approach is developed for determining the survival probability and first-passage probability of a randomly excited hysteretic systems endowed with fractional derivative elements. Specifically, by employing a combination of statistical linearization and of stochastic averaging, the amplitude of the system response is modeled as one-dimensional Markovian Process. In this manner the corresponding backward Kolmogorov equation which governs the evolution of the survival probability of the system is determined. An approximate solution of this equation is sought by employing a Galerkin scheme in which a convenient set of confluent hypergeometric functions is used a…

Methods cooperation for multiresolution motion estimation

2002

For a medical application, we are interested in an estimation of optical flow on a patient's face, particularly around the eyes. Among the methods of optical flow estimation, gradient estimation and block matching are the main methods. However, the gradient-based approach can only be applied for small displacements (one or two pixels). Gener- ally, the process of block matching leads to good results only if the searching strategy is judiciously selected. Our approach is based on a Markov random field model, combined with an algorithm of block match- ing in a multiresolution scheme. The multiresolution approach allows de- tection of a large range of speeds. The large displacements are detect…

Using Fourier local magnitude in adaptive smoothness constraints in motion estimation

2007

Like many problems in image analysis, motion estimation is an ill-posed one, since the available data do not always sufficiently constrain the solution. It is therefore necessary to regularize the solution by imposing a smoothness constraint. One of the main difficulties while estimating motion is to preserve the discontinuities of the motion field. In this paper, we address this problem by integrating the motion magnitude information obtained by the Fourier analysis into the smoothness constraint, resulting in an adaptive smoothness. We describe how to achieve this with two different motion estimation approaches: the Horn and Schunck method and the Markov Random Field (MRF) modeling. The t…

Anti-tempered Layered Adaptive Importance Sampling

2017

Monte Carlo (MC) methods are widely used for Bayesian inference in signal processing, machine learning and statistics. In this work, we introduce an adaptive importance sampler which mixes together the benefits of the Importance Sampling (IS) and Markov Chain Monte Carlo (MCMC) approaches. Different parallel MCMC chains provide the location parameters of the proposal probability density functions (pdfs) used in an IS method. The MCMC algorithms consider a tempered version of the posterior distribution as invariant density. We also provide an exhaustive theoretical support explaining why, in the presented technique, even an anti-tempering strategy (reducing the scaling of the posterior) can …

Efficient solution of the first passage problem by Path Integration for normal and Poissonian white noise

2015

Abstract In this paper the first passage problem is examined for linear and nonlinear systems driven by Poissonian and normal white noise input. The problem is handled step-by-step accounting for the Markov properties of the response process and then by Chapman–Kolmogorov equation. The final formulation consists just of a sequence of matrix–vector multiplications giving the reliability density function at any time instant. Comparison with Monte Carlo simulation reveals the excellent accuracy of the proposed method.

On risk sensitive control of regular step Markov processes

2001