Publications associées à EDF-schedulability of synchronous periodic task systems is coNP-hard

Publications associées (25)

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Analysis of Dampers in Time-Sensitive Networks With Non-Ideal Clocks

Jean-Yves Le Boudec, Ehsan Mohammadpour

Dampers are devices that reduce delay jitter in the context of time-sensitive networks, by delaying packets for the amount written in packet headers. Jitter reduction is required by some real-time applications; beyond this, dampers have the potential to so ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

From C/C plus plus Code to High-Performance Dataflow Circuits

Paolo Ienne, Andrea Guerrieri, Lana Josipovic

High-level synthesis (HLS) tools typically generate statically scheduled datapaths. Static scheduling implies that the resulting circuits have a hard time exploiting parallelism in code with potential memory dependences, with control dependences, or where ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Grid-Aware Real-Time Control of Electric Vehicles

Roman Rudnik

Electric vehicles (EVs) are already part of today's reality and their number is expected to grow rapidly in the near future. A large-scale penetration of EVs will increase the power consumption during charging periods. Hence, the uncoordinated and random c ...

EPFL2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Combining Dynamic & Static Scheduling in High-level Synthesis

Paolo Ienne, Lana Josipovic

A central task in high-level synthesis is scheduling: the allocation of operations to clock cycles. The classic approach to scheduling is static, in which each operation is mapped to a clock cycle at compile-time, but recent years have seen the emergence o ...

ASSOC COMPUTING MACHINERY2020

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Bridging the gap between dataplanes and commodity operating systems

Georgios Prekas

The conventional wisdom is that aggressive networking requirements, such as high packet rates for small messages and microsecond-scale tail latency, are best addressed outside the kernel, in a user-level networking stack. In particular, dataplanes borrow d ...

EPFL2018

Hybrid, Job-Aware, and Preemptive Datacenter Scheduling

Pamela Isabel Delgado Borda

Scheduling in datacenters is an important, yet challenging problem. Datacenters are composed of a large number, typically tens of thousands, of commodity computers running a variety of data-parallel jobs. The role of the scheduler is to assign cluster reso ...

EPFL2018

Analysis of EEG Correlates of Perceived Difficulty in Dynamically Changing Flying Tasks

José del Rocio Millán Ruiz, Ricardo Andres Chavarriaga Lozano, Ping-Keng Jao

Real-time workload estimation can be an important tool to improve human-machine interaction. Despite multiple efforts in this sense, most studies focused on tasks designed to have extreme conditions of workload (high vs low), and these levels remain rather ...

IEEE2018

Near-optimal Deployment of Dataflow Applications on Many-core Platforms with Real-time Guarantees

Alena Simalatsar, Stefanos Skalistis

Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of inte ...

IEEE2017

Efficient Adaptive Hard Real-time Multi-processor Systems

Stefanos Skalistis

Modern computing systems are based on multi-processor systems, i.e. multiple cores on the same chip. Hard real-time systems are required to perform particular tasks within certain amount of time; failure to do so characterises an unaccepted behavior. Hard ...

EPFL2017

Don't cry over spilled records: Memory elasticity of data-parallel applications and its application to cluster scheduling

Willy Zwaenepoel, Syed Mohammad Aunn Raza, Calin Iorgulescu, Florin Dinu

Understanding the performance of data-parallel workloads when resource-constrained has significant practical importance but unfortunately has received only limited attention. This paper identifies, quantifies and demonstrates memory elasticity, an intrinsi ...

The USENIX Association2017

Improved hardness results for unique shortest vector problem

Divesh Aggarwal

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique s ...

Elsevier2016

Axo: Tolerating Delay Faults in Real-Time Systems

Jean-Yves Le Boudec, Simon Bliudze, Wajeb Saab, Maaz Mashood Mohiuddin

We address delay faults: faults that cause a software component to take more time for completing an action than a given deadline. Such faults are particularly of interest in real- time mission-critical control applications that use general-purpose computin ...

2016

A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand

Colin Neil Jones

This paper describes an employee scheduling system for retail outlets; it is a constraint-based system that exploits forecasts and stochastic techniques to generate schedules meeting the demand for sales personnel. Uncertain scenarios due to fluctuating de ...

Elsevier2015

Low Complexity Scheduling and Coding for Wireless Networks

Siddhartha Brahma

The advent of wireless communication technologies has created a paradigm shift in the accessibility of communication. With it has come an increased demand for throughput, a trend that is likely to increase further in the future. A key aspect of these chall ...

EPFL2015

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Pascal Frossard

In free viewpoint video, a viewer can choose at will any camera angle or the so-called "virtual view" to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera vi ...

2015

Online Energy-Efficient Task-Graph Scheduling for Multicore Platforms

David Atienza Alonso, Karim Kanoun

Numerous Directed-Acyclic Graph (DAG) schedulers have been developed to improve the energy efficiency of various multi-core platforms. However, these schedulers make a priori assumptions about the relationship between the task dependencies, and they are un ...

Institute of Electrical and Electronics Engineers2014