Modern Cyber-Physical Systems (CPS) often in-volve dependent real-time processes bound to different timing constraints. These CPSs can be modeled using PolyGraph, a formalism that extends the Cyclo-Static Dataflow model with explicit real-time constraints. Unlike traditional real-time approaches where timing constraints are specified for every process, PolyGraph can offer greater flexibility by binding real-time con-straints for only a subset of processes (e.g., processes associated with hardware components such as sensors and actuators), along with end-to-end latency specifications. In that case, processes without specified timing constraints only inherit ones from pro-cesses with explicit and specified timing constraints due to data dependencies. This paper aims to formalize a method to derive timing constraints for an entire PolyGraph model where only a subset of processes has explicit timing constraints in the model. We demonstrate how this approach eases scheduling constraints and enables early detection of missed deadlines through two examples from a vehicle ADAS and the Ingenuity Mars helicopter.

This paper investigates the possibility of using an analog quantum computer as commercialized by D-Wave to solve large QUBO problems by means of a single invocation of the quantum annealer. Indeed this machine solves a spin glass problem with programmable coefficients but subject to quite strong topology restrictions on the set of non-zero coefficients. Rather than mapping problem variables onto multiple qbits, an approach which requires many invocations of the annealer to solve small size problems, it is tempting to investigate the existence of sparse relaxations compliant with the qbits interconnection topology of the machine, hence solvable in one invocation of the annealing oracle, but still providing good-quality solutions to the original problem. This paper provides an experimental setup which aims to determine whether or not such convenient relaxations do exist or, rather, are easy to find. Our experiments suggest that it is not the case and, therefore, that solving even moderate size arbitrary problems with a single call to a quantum annealer is not possible at least within the constraints of the so-called Chimera topology. We conclude the paper with a number of perspectives that this results imply on the design of heuristics taking profit of a quantum annealing oracle to solve large scale problems.

Data flow formalisms are commonly used to model systems in order to solve problems of buffer sizing and task scheduling. A prerequisite for static analysis of a modeled system is the existence of a periodic schedule in which the sizes of communication channels can be bounded for an unbounded execution (consistency), and that communication dependencies do not introduce a deadlock in such an execution (liveness). In the context of Cyber-Physical Systems, components are often interfaced with the physical world and have frequency constraints. The existing data flow formalisms lack expressiveness to fully cover the expected behavior of these components. We propose an extension to Synchronous Data Flow (SDF) formalism, called Polygraph, that includes frequency constraints and adjustable communication rates. We show that with these extensions, the conditions for a model to be consistent and live are no longer sufficient, and we extend the corresponding theorems with necessary and sufficient conditions to preserve these properties. We also introduce a framework to check the liveness of a Polygraph model, implemented in the tool DIVERSITY, along with preliminary experiments to validate this approach.

Low-Level analysis of Worst Case Execution Time (WCET) is an important field for real-time system validation. It stands between computer architecture and mathematics, as it relies strongly on variants of abstract interpretation. One of the features that causes the largest uncertainty regarding WCET evaluation for low-level analysis of sequential execution on a single processor is taking Cache Memory-related Delays (CMRD) and Cache-related Preemption Delays (CRPD) correctly into account. Research work from the 1990s provides a good basic framework for this problem as long as a task runs without preemption. But when preemption of tasks is allowed, although several formalisms exist, their predictive power is lower and the usual approach relies on analyses of NP-hard problems. In this article, we want to show some potential advantages of using a formalism inspired by Quantum Computing (QC) to evaluate CMRDs with preemptions while avoiding the NP-hard problem underneath. The experimental results, with a classic (non-quantum) numerical approach, on a selection of Malardalen benchmark programs display very good accuracy, while the complexity of the evaluation is a low-order polynomial of the number of memory accesses. While it is not yet a fully parallel quantum algorithm, we provide a first roadmap on how to reach such an objective.

Current trends in computer architecture show that we are aiming toward more cores and even more heterogeneity. As an extensive knowledge of processor's internals cannot be a prerequisite to their programming and for the sake of portability, these systems necessitate the compilation flow to evolve and cope with heterogeneity issues. This is even more so true for embedded systems. In this paper, we show how to start from a specific Intermediate Representation (IR) to explore the configuration space of program-part mappings on heterogeneous targets thank to a GCC pluggin. Then we define a simple execution model with predictable performance and use execution time from generated elementary kernels to predict the performance of the whole application. We show a very good accuracy of this framework to predict real world performance on experimental results and how we can use it to choose the best parallel configuration.

Conference of 10th International Conference on Evaluation of Novel Approaches to Software Engineering, ENASE 2015 ; Conference Date: 29 April 2015 Through 30 April 2015; Conference Code:112383

In this paper, we consider the problem of multiprocessor scheduling for safety-critical streaming applications modeled as acyclic data-flow graphs. To the best of our knowledge, most existing works have proposed periodic scheduling that ignore latency or can even have a negative impact on it: the results are quite far from those obtained under Self-Timed scheduling (STS). In this paper, we introduce a new scheduling policy noted Self-Timed Periodic (STP), which is an execution model combining self-timed scheduling with periodic scheduling. The proposed framework shows that the use of both strategies is possible and that they complement each other, STS improves the performance metrics of the programs, while the periodic model captures the timing aspects. We evaluate the performance of our scheduling policy for a set of 10 real-life streaming applications. We find that in most of the cases, our approach gives a significant improvement in latency compared to the Static Periodic Schedule (SPS), and results which are close to the best case latency of STS.

The ever-growing number of cores in Chip Multi-Processors (CMP) brings a renewed interest in stream programming to solve the programmability issues raised by massively parallel architectures. Stream programming languages are flourishing (StreaMIT, Brook, ∑C, etc.). Nonetheless, their execution support have not yet received enough attention, in particular regarding the new generation of many-cores.

In this paper we refine a Markovian model previously applied to modelize a subset of dynamic branch predictors related WCET delays, in order to take the finiteness of Branch History Table (BHT) into account. The base of the model allows the modeling of a deterministic or non deterministic automaton or set of automata thanks to a Markovian model. We previously applied this formalism to cache related delay and cache related preemption delays and simple dynamic branch prediction with infinite BHT. Now we would like to take into account the finiteness of the BHT in the previous model in order to estimate extend our model of static analysis of Worst Case Execution Time (WCET). For illustration, we chose the case of a dynamic prediction based on a two bit saturating counter, with a LRU policy for replacement policy.

Stream languages offer a simple multi-core programming model and achieve good performance. Yet expressing data rearrangement patterns (like a matrix block decomposition) in these languages is verbose and error prone. In this paper, we propose a high-level programming language to elegantly describe n-dimensional data reorganization patterns. We show how to compile it to stream languages.

One of the major challenges of multicore architectures is not only to aim toward high performance but also to efficiently harness the computing power of these systems. This is especially true for embedded systems where problems of energy and silicon efficiencies are critical. Multicore architectures provide significant gains for explicitly multi-threaded or dataflow applications. However, single-task applications commonly found in embedded systems do not fit well with current multicore architectures. To maximize performance and efficiency of the chip, communication and allocation-synchronization problems need to be addressed in concert with a coherent and carefully crafted approach of the programming interface. This paper focuses on allocation-synchronization problems and the programming interface of these architectures. The proposed mechanism is based on an intermediate level of parallelism and provides a solution for allocating and synchronizing processing cores with an easy to use instruction set architecture. This mechanism avoids global synchronization of cores when interruptions or exceptions occur on the main processor. This increases core utilizations among all applications executed on the chip and thus, chip efficiency. A preliminary evaluation has shown significant improvements in terms of performance, energy and silicon efficiencies of the chip.