Search results for "Online algorithm"
showing 10 items of 19 documents
Online Scheduling of Task Graphs on Hybrid Platforms
2018
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous \(4\sqrt{m/k}\)-competitive online algorithm [2], where m is the number of CPUs and k the number of GPUs (\(m\ge k\)). We prove that no online algorithm can have a competitive ratio …
Convergence of direct recursive algorithm for identification of Preisach hysteresis model with stochastic input
2015
We consider a recursive iterative algorithm for identification of parameters of the Preisach model, one of the most commonly used models of hysteretic input-output relationships. The classical identification algorithm due to Mayergoyz defines explicitly a series of test inputs that allow one to find parameters of the Preisach model with any desired precision provided that (a) such input time series can be implemented and applied; and, (b) the corresponding output data can be accurately measured and recorded. Recursive iterative identification schemes suitable for a number of engineering applications have been recently proposed as an alternative to the classical algorithm. These recursive sc…
Online detection of rem sleep based on the comprehensive evaluation of short adjacent eeg segments by artificial neural networks
1997
Abstract 1. 1. For scientific and clinical requirements the present objective is a robust automatic online algorithm to detect rapid eye movement (REM) steep from single channel sleep EEG data without using EMG or EOG information. 2. 2. For data preprocessing 20 seconds time periods of the continuous EEG activity are digitally filtered in 7 frequency bands. Then the RMS values of these filtered signals are calculated along segments of 2.5 seconds. The resulting matrix of RMS values is representing information on the power of the signal localized in time and frequency and serves as input to an artificial neural network. A pooled set of EEG data together with the corresponding manual evaluati…
Incremental linear model trees on massive datasets
2013
The existence of massive datasets raises the need for algorithms that make efficient use of resources like memory and computation time. Besides well-known approaches such as sampling, online algorithms are being recognized as good alternatives, as they often process datasets faster using much less memory. The important class of algorithms learning linear model trees online (incremental linear model trees or ILMTs in the following) offers interesting options for regression tasks in this sense. However, surprisingly little is known about their performance, as there exists no large-scale evaluation on massive stationary datasets under equal conditions. Therefore, this paper shows their applica…
The on-line curvilinear component analysis (onCCA) for real-time data reduction
2015
Real time pattern recognition applications often deal with high dimensional data, which require a data reduction step which is only performed offline. However, this loses the possibility of adaption to a changing environment. This is also true for other applications different from pattern recognition, like data visualization for input inspection. Only linear projections, like the principal component analysis, can work in real time by using iterative algorithms while all known nonlinear techniques cannot be implemented in such a way and actually always work on the whole database at each epoch. Among these nonlinear tools, the Curvilinear Component Analysis (CCA), which is a non-convex techni…
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
Online optimization of a multi-conversion-level DC home microgrid for system efficiency enhancement
2017
In this paper, an on-line management system for the optimal efficiency operation of a multi-bus DC home distribution system is proposed. The operation of the system is discussed with reference to a distribution system with two conversion stages and three voltage levels. In each of the conversion stages, three paralleled DC/DC converters are implemented. A Genetic Algorithm performs the on-line optimization of the DC network’s global efficiency, generating the optimal current sharing ratios of the concurrent power converters. The overall DC/DC conversion system including the optimization section is modelled using MATLAB/Simulink. Thanks to the implemented online algorithm, considering …
Algorithms for Computing Abelian Periods of Words
2012
Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.
Fast computation of abelian runs
2016
Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $\sigma$ and a Parikh vector $\mathcal{P}$, returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(\sigma+p)$, where $p$ is the norm of $\mathcal{P}$, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$, for any given norm $p$. Finally, we give an $O(n^2)$-time offline randomi…
Online Hyperparameter Search Interleaved with Proximal Parameter Updates
2021
There is a clear need for efficient hyperparameter optimization (HO) algorithms for statistical learning, since commonly applied search methods (such as grid search with N-fold cross-validation) are inefficient and/or approximate. Previously existing gradient-based HO algorithms that rely on the smoothness of the cost function cannot be applied in problems such as Lasso regression. In this contribution, we develop a HO method that relies on the structure of proximal gradient methods and does not require a smooth cost function. Such a method is applied to Leave-one-out (LOO)-validated Lasso and Group Lasso, and an online variant is proposed. Numerical experiments corroborate the convergence …