Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userManaging Varying Worst Case Execution Times on DVS Platforms
108
0
0.0
(
0
)
Added by
Vandy Berten
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Energy efficient real-time task scheduling attracted a lot of attention in the past decade. Most of the time, deterministic execution lengths for tasks were considered, but this model fits less and less with the reality, especially with the increasing number of multimedia applications. Its why a lot of research is starting to consider stochastic models, where execution times are only known stochastically. However, authors consider that they have a pretty much precise knowledge about the properties of the system, especially regarding to the worst case execution time (or worst case execution cycles, WCEC). In this work, we try to relax this hypothesis, and assume that the WCEC can vary. We propose miscellaneous methods to react to such a situation, and give many simulation results attesting that with a small effort, we can provide very good results, allowing to keep a low deadline miss rate as well as an energy consumption similar to clairvoyant algorithms.
rate research
Read More
Estimating Worst-Case Execution Time (WCET) is of utmost importance for developing Cyber-Physical and Safety-Critical Systems. The systems scheduler uses the estimated WCET to schedule each task of these systems, and failure may lead to catastrophic events. It is thus imperative to build provably reliable systems. WCET is available to us in the last stage of systems development when the hardware is available and the application code is compiled on it. Different methodologies measure the WCET, but none of them give early insights on WCET, which is crucial for system development. If the system designers overestimate WCET in the early stage, then it would lead to the overqualified system, which will increase the cost of the final product, and if they underestimate WCET in the early stage, then it would lead to financial loss as the system would not perform as expected. This paper estimates early WCET using Deep Neural Networks as an approximate predictor model for hardware architecture and compiler. This model predicts the WCET based on the source code without compiling and running on the hardware architecture. Our WCET prediction model is created using the Pytorch framework. The resulting WCET is too erroneous to be used as an upper bound on the WCET. However, getting these results in the early stages of system development is an essential prerequisite for the systems dimensioning and configuration of the hardware setup.
Despite the attempts of well-designed anonymous communication tools to protect users from tracking or identification, flaws in surrounding software (such as web browsers) and mistakes in configuration may leak the users identity. We introduce Nymix, an anonymity-centric operating system architecture designed top-to-bottom to strengthen identity- and tracking-protection. Nymixs core contribution is OS support for nym-browsing: independent, parallel, and ephemeral web sessions. Each web session, or pseudonym, runs in a unique virtual machine (VM) instance evolving from a common base state with support for long-lived sessions which can be anonymously stored to the cloud, avoiding de-anonymization despite potential confiscation or theft. Nymix allows a user to safely browse the Web using various different transports simultaneously through a pluggable communication model that supports Tor, Dissent, and a private browsing mode. In evaluations, Nymix consumes 600 MB per nymbox and loads within 15 to 25 seconds.
Flow routing over inter-datacenter networks is a well-known problem where the network assigns a path to a newly arriving flow potentially according to the network conditions and the properties of the new flow. An essential system-wide performance metric for a routing algorithm is the flow completion times, which affect the performance of applications running across multiple datacenters. Current static and dynamic routing approaches do not take advantage of flow size information in routing, which is practical in a controlled environment such as inter-datacenter networks that are managed by the datacenter operators. In this paper, we discuss Best Worst-case Routing (BWR), which aims at optimizing the tail completion times of long-running flows over inter-datacenter networks with non-uniform link capacities. Since finding the path with the best worst-case completion time for a new flow is NP-Hard, we investigate two heuristics, BWRH and BWRHF, which use two different upper bounds on the worst-case completion times for routing. We evaluate BWRH and BWRHF against several real WAN topologies and multiple traffic patterns. Although BWRH better models the BWR problem, BWRH and BWRHF show negligible difference across various system-wide performance metrics, while BWRHF being significantly faster. Furthermore, we show that compared to other popular routing heuristics, BWRHF can reduce the mean and tail flow completion times by over $1.5times$ and $2times$, respectively.
Recent commercial hardware platforms for embedded real-time systems feature heterogeneous processing units and computing accelerators on the same System-on-Chip. When designing complex real-time application for such architectures, the designer needs to make a number of difficult choices: on which processor should a certain task be implemented? Should a component be implemented in parallel or sequentially? These choices may have a great impact on feasibility, as the difference in the processor internal architectures impact on the tasks execution time and preemption cost. To help the designer explore the wide space of design choices and tune the scheduling parameters, in this paper we propose a novel real-time application model, called C-DAG, specifically conceived for heterogeneous platforms. A C-DAG allows to specify alternative implementations of the same component of an application for different processing engines to be selected off-line, as well as conditional branches to model if-then-else statements to be selected at run-time. We also propose a schedulability analysis for the C-DAG model and a heuristic allocation algorithm so that all deadlines are respected. Our analysis takes into account the cost of preempting a task, which can be non-negligible on certain processors. We demonstrate the effectiveness of our approach on a large set of synthetic experiments by comparing with state of the art algorithms in the literature.
In this paper, we consider the worst-case regret of Linear Thompson Sampling (LinTS) for the linear bandit problem. citet{russo2014learning} show that the Bayesian regret of LinTS is bounded above by $widetilde{mathcal{O}}(dsqrt{T})$ where $T$ is the time horizon and $d$ is the number of parameters. While this bound matches the minimax lower-bounds for this problem up to logarithmic factors, the existence of a similar worst-case regret bound is still unknown. The only known worst-case regret bound for LinTS, due to cite{agrawal2013thompson,abeille2017linear}, is $widetilde{mathcal{O}}(dsqrt{dT})$ which requires the posterior variance to be inflated by a factor of $widetilde{mathcal{O}}(sqrt{d})$. While this bound is far from the minimax optimal rate by a factor of $sqrt{d}$, in this paper we show that it is the best possible one can get, settling an open problem stated in cite{russo2018tutorial}. Specifically, we construct examples to show that, without the inflation, LinTS can incur linear regret up to time $exp(Omega(d))$. We then demonstrate that, under mild conditions, a slightly modified version of LinTS requires only an $widetilde{mathcal{O}}(1)$ inflation where the constant depends on the diversity of the optimal arm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
