Search results for "Scheduling"
showing 10 items of 275 documents
A New Universal-Environment Adaptive Multi-processor Scheduler for Autonomous Cyber-Physical System
2012
International audience; Robot, spaceship and other applications that can be called autonomous Cyber-Physical Systems (CPS) are all smart embedded systems, which usually run in open environment by themselves with inhered intelligent capabilities. Besides the application intelligence, the researches of adaptive platform for such systems have also become topics recently. Based on the analysis of current work, a new environment adaptive scheduler (¦Á-S) for multiprocessor platform of a cyber-physical system is proposed in this article. And then, its related structures, models, and reasoning methods are studied deeply. Different from the existing ones, ¦Á-S can schedule all tasks according to th…
Design of a Real-time face detection parallel architecture using High-Level Synthesis
2008
Abstract We describe a High-Level Synthesis implementation of a parallel architecture for face detection. The chosen face detection method is the well-known Convolutional Face Finder (CFF) algorithm, which consists of a pipeline of convolution operations. We rely on dataflow modelling of the algorithm and we use a high-level synthesis tool in order to specify the local dataflows of our Processing Element (PE), by describing in C language inter-PE communication, fine scheduling of the successive convolutions, and memory distribution and bandwidth. Using this approach, we explore several implementation alternatives in order to find a compromise between processing speed and area of the PE. We …
Scheduling independent stochastic tasks on heterogeneous cloud platforms
2019
International audience; This work introduces scheduling strategies to maximize the expected number of independent tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The cloud platform is composed of several types of virtual machines (VMs), where each type has a unitexecution cost that depends upon its characteristics. The amount of budget spent during the execution of a task on a given VM is the product of its execution length by the unit execution cost of that VM. The execution lengths of tasks follow a variety of standard probability distributions (exponential, uniform, halfnormal, etc.), which is known beforehand and whose mean and stand…
Scheduling independent stochastic tasks under deadline and budget constraints
2018
This article discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow independent and identically distributed probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an ef…
Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs
2014
We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, {\it i.e.}coupled-tasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph $G_c$ is bipartite (star, chain, $\ldots$) In such context, we design some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When $G_c$ is a $k$-stage bipartite graph, we propose, among other, a $\frac{7}{6}$-approximation algorithm when $k=1$, and a $\frac{13}{9}$-approximation…
Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph
2012
International audience; This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of …
Joint routing and per-flow fairness in wireless multihop networks
2008
In wireless multihop networks communication between two end-nodes is carried out by hopping over multiple short wireless links. Traditional CSMA/CA based media access control does not work satisfactory in a multihop scenario, since an intended target of a communication may be subject to mutual interference imposed by concurrent transmissions from nodes which cannot directly sense each other, causing unfair throughput allocation. Although TDMA seems to be a more promising solution, careful transmission scheduling is needed in order to achieve error-free communication and fairness. In our previous work, a TDMA scheduling algorithm has been proposed that schedules the transmissions in a fair m…
Priority Enabled Grant-Free Access With Dynamic Slot Allocation for Heterogeneous mMTC Traffic in 5G NR Networks
2021
Although grant-based mechanisms have been a predominant approach for wireless access for years, the additional latency required for initial handshake message exchange and the extra control overhead for packet transmissions have stimulated the emergence of grant-free (GF) transmission. GF access provides a promising mechanism for carrying low and moderate traffic with small data and fits especially well for massive machine type communications (mMTC) applications. Despite a surge of interest in GF access, how to handle heterogeneous mMTC traffic based on GF mechanisms has not been investigated in depth. In this paper, we propose a priority enabled GF access scheme which performs dynamic slot …
An effective approach for the maintenance scheduling in large systems with required reliability level: A case study
2015
This paper deals with the problem of the maintenance scheduling in a multi-component system for which a required reliability level has to be warranted until the next planned stop for maintenance. Particularly, the tackled problem concerns both the determination of the elements set on which to perform preventive maintenance and the optimal number of maintenance crews in order to warranty the required reliability level at the minimum maintenance cost. The problem is formulated as a mathematical programming model that becomes very hard to solve for large practical systems. For such reason, a new effective approach based on a constrained genetic algorithm is herein proposed and tested with refe…
LPV model identification for gain scheduling control: An application to rotating stall and surge control problem
2006
Abstract We approach the problem of identifying a nonlinear plant by parameterizing its dynamics as a linear parameter varying (LPV) model. The system under consideration is the Moore–Greitzer model which captures surge and stall phenomena in compressors. The control task is formulated as a problem of output regulation at various set points (stable and unstable) of the system under inputs and states constraints. We assume that inputs, outputs and scheduling parameters are measurable. It is worth pointing out that the adopted technique allows for identification of an LPV model's coefficients without the requirements of slow variations amongst set points. An example of combined identification…