The emergence of new applications in high-performance computing is driving the need for more efficient computing machines. As supercomputer architectures become increasingly complex, the combinatorial explosion of design spaces and the time-consuming nature of design simulations lead to challenging design space exploration problems. This work introduces an automated search framework to achieve power-performance-area efficient Arm Neoverse V1 processor designs. Based on multi-objective Bayesian optimization, we propose a new exploration algorithm named SEBO by enhancing the three main stages of the optimization. Experimental results show that SEBO can not only compete with the top state-of-the-art baseline algorithms, but also outperforms them in terms of the quality and diversity of the returned Pareto-optimal designs.

Neural network accelerators are designed to process Neural Networks (NN) optimizing three Key Performance Indicators (KPIs): latency, power, and chip area. This work is based on the study of Gemini, an industrial prototype near memory computing inference accelerator designed using a high-level synthesis technique. Gemini is an output stationary configurable accelerator that achieves its performance based on two structural parameters. The measurement of the KPIs requires simulations that are time-consuming and resource-intensive. This paper presents a high-level practical estimator that can instantly predict the KPIs depending on the NN and the Gemini configuration. The latency is accurately derived using an analytical model based on the architecture, the operators scheduling and the NN characteristics. The power and the chip area are computed analytically and the models are calibrated using simulations. Finally, we show how to use the estimator to derive Pareto optima for choosing the best Gemini configurations for a VGG-like NN.

In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters.

Automotive and avionics embedded systems are usually composed of several tasks that are subject to complex timing constraints. In this context, the LET paradigm was introduced to improve the determinism of a system of tasks that communicate data through shared variables. The age latency corresponds to the maximum time for the propagation of data in these systems. Its precise evaluation is an important and challenging question for the design of these systems. We consider in this paper a set of multi-periodic tasks that communicate data following the LET paradigm. Our main contribution is the development of mathematical and algorithmic tools to model precisely the dependency between tasks executions to experiment with an original methodology for computing the age latency of the system. These tools allow to handle the whole graph instead of particular chains and to extract automatically the critical parts of the graph. Experiments on randomly generated graphs indicate that systems with up to 90 periodic tasks and a hyperperiod bounded by 100 can be handled within a reasonable amount of time.

Summary This paper presents an efficient algorithm with performance guarantee to solve task scheduling problem on hybrid platforms with energy constraint and communication delays. The underlying platform architecture in this work is composed of two types of resources, CPU and GPU, often called hybrid parallel multicore platforms. We focus on finding a generic approach to schedule applications presented by Directed Acyclic Graph (DAG), which minimizes the makespan by considering communication delays and respecting an energy constraint. A two‐phase algorithm is proposed with a performance guarantee of 6 compared with the optimal solution; the first phase consists in solving the assignment problem to find the type of processor assigned to execute the tasks (CPU or GPU) using a linear program. In the second phase, we calculate the start execution time of each task to generate a feasible schedule. Finally, we test our algorithm on a large number of instances. These tests demonstrate that the proposed algorithm achieves a close‐to‐optimal performance.

Synchronous Dataflow (SDF) is the most commonly used dataflow Model of Computation (MoC) for the specification of Digital Signal Processing (DSP) systems. The Interface-Based SDF (IBSDF) model extends the semantics of the SDF model by introducing a graph composition mechanism based on hierarchical interfaces. Computing the throughput of an application is essential when designing DSP systems. This article introduces and assesses new methods to compute the throughput of DSP applications specified with IBSDF graphs. First, a basic method inspired from the state-of-the-art techniques that relies on a transformation of the IBSDF graph to an equivalent non-hierarchical graph of potentially exponential size. Second, a new technique that takes advantage of the hierarchy semantics of the IBSDF MoC to speed-up the throughput evaluation without any conversion. The proposed technique makes it possible to compute the throughput of large IBSDF graphs in a few milliseconds, where the basic method fails to produce a result.

The Synchronous Dataow Graph (SDFG) and Cyclo-Static Dataow Graph (CSDFG) are two well-known models, used practically by industry for many years, and for which there is a large number of analysis techniques. Yet, basic problems such as the throughput computation or the liveness evaluation are not well solved, and their complexity is still unknown. In this paper, we propose K-Iter, an iterative algorithm based on K-periodic scheduling to compute the throughput of a CSDFG. By using this technique, we are able to compute in less than a minute the throughput of industry applications for which no result was available before.

The search of a mapping of a Synchronous Data Flow Graph (SDFG) on a distributed architecture that achieves a given throughput while satisfying memory constraints is a difficult challenge. Solving this problem calls for evaluating throughput and buffer capacities associated to a mapping. Since the available mapping evaluation methods are not polynomial with respect to the SDFG description, mapping techniques using them are not scalable. This paper develops a polynomial method for the evaluation of any given SDFG mapping on a distributed architecture. The method is based on a simple transformation of the SDFG to model communications through a Network on Chip. The key result is that the size of the memory required in order to guarantee the liveness or a given throughput of an application may be evaluated in polynomial time. Experimentally, computing the memory size guaranteeing liveness of a mapping of a 670-node H264 graph on a 4-cluster architecture takes 70 ms on an Intel Core i5-660 processor and grows linearly with graph size.

The increasing complexity of embedded applications in modern cars has increased the need of computational power. To meet this requirement the European automotive standard AUTOSAR has introduced the use of multi-core platforms in it version 4.x. In the industry, the applications are often designed and validated by high level models such as Matlab/Simulink before being implemented on AUTOSAR. However, passing from a Simulink synchronous model to a multi-core AUTOSAR implementation is not trivial. In this paper, we present an approach to model formally the synchronous semantic of any multi-periodic Simulink system by Synchronous Dataflow Graph. Our model is constructed on a formal equivalence between the data dependencies imposed by the communication mechanisms in Simulink and the precedence constraints of a synchronous dataflow graph. The resulting graph is equivalent in size to the Simulink description and allows multi/many-core accurate implementation analysis.

Weighted Petri nets provide convenient models of many man-made systems. Real applications are often required to possess the fundamental Petri net properties of liveness and reversibility, as liveness preserves all the functionalities (fireability of all transitions) of the system and reversibility lets the system return to its initial state (marking) using only internal operations. Characterizations of both behavioral properties, liveness and reversibility, are known for well-formed weighted Choice-Free and ordinary Free-Choice Petri nets, which are special cases of Equal-Conflict Petri nets. However, reversibility is not well understood for this larger class, where choices must share equivalent preconditions, although characterizations of liveness are known. In this paper, we provide the first characterization of reversibility for all live Equal-Conflict Petri nets by extending, in a weaker form, a known condition that applies to the Choice-Free and Free-Choice subclasses. We deduce the monotonicity of reversibility in the live Equal-Conflict class. We also give counter-examples for other classes where the characterization does not hold. Finally, we focus on well-formed Equal-Conflict Petri nets, for which we offer the first polynomial sufficient conditions for liveness and reversibility, contrasting with the previous exponential time conditions.

Dataflow modeling is a highly regarded method for the design of embedded systems. Measuring the performance of the associated analysis and compilation tools requires an efficient dataflow graph generator. This paper presents a new graph generator for Phased Computation Graphs (PCG), which augment Cyclo-Static Dataflow Graphs with both initial phases and thresholds.

Join-Free Petri nets, whose transitions have at most one input place, model systems without synchronizations, while Choice-Free Petri nets, whose places have at most one output transition, model systems without conflicts. These classes respectively encompass the state machines (S-systems) and the marked graphs (T-systems). Whereas a structurally bounded and structurally live Petri net is said to be “well-formed”, a bounded and live Petri net is said to be “well-behaved”. Necessary and sufficient conditions for the well-formedness of Join-Free and Choice-Free nets have been known for some time, yet the behavioral properties of these classes are still not well understood. In particular polynomial sufficient conditions for liveness, that is, polynomial in time and with a polynomial initial number of tokens, have not been found until now. Besides, home markings , which can be reached from every reachable marking thus allowing for the construction of systems that can return to their initial data distribution, are not well apprehended either for these subclasses. We extend results on weighted T-systems to the class of weighted Petri nets and present transformations which preserve the language of the system and reduce the initial marking. We introduce a notion of balancing that makes possible the transformation of conservative systems into so-called “token-conservative” systems, whose number of tokens is invariant, while retaining the feasible transition sequences. This transformation is pertinent for all well-formed Petri nets and leads to polynomial sufficient conditions of liveness for well-formed Join-Free and Choice-Free nets. Finally, we also provide polynomial live and home markings for Fork-Attribution systems.

Cyclo-Static DataFlow Graphs (CSDFG in short) is a formalism commonly used to model parallel applications composed by actors communicating through buffers. The liveness of a CSDFG ensures that all actors can be executed infinitely often. This property is clearly fundamental for the design of embedded applications.

The design of streaming applications (e.g. multimedia or network packet processing) must consider several optimizations such as the minimization of the whole surface of the memory needed on a Chip. The problem tackled in this paper is the minimization of the whole surface of the memory needed to reach a minimum fixed throughput. The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput. The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to its capacity. A polynomial simple algorithm that minimizes the overall surface of memory for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently. For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.