Les Ingénieurs-Chercheurs P Dubrulle

M Asavoe

P Aubry

S Carpov

F Galéa

R Sirdey

K Trabelsi

D Irofti

M Jan

B Ben Hedia

Y Mouafo

P Ruf Avec Qui J'ai

M Ait Aba

F Hebbache

E Laarouchi

D Vert

M Zuber

B Binder

G Bettonte

E Lenormand

A Madi

José, Ingrid Voudrais Spécialement Remercier Joannes

Jeannot Fawaz

Catherine Auriol

Juliette Valentin

Philippe Glanon

Philippe ©2020

Glanon

J'adresse ma

Keywords: système cyber-physiques, ordonnancement multiprocesseur, graphes de flots de données statiques, architectures hétérogènes, pipeline logiciel, débit maximal. ©2020 cyber-physical systems, multiprocessor scheduling, static dataflow graphs, heterogeneous architectures, software pipelining, maximum throughput ©2020 Philippe

Avant tout, je tiens à remercier mon directeur de thèse, monsieur Chokri Mraidha et mon encadrante, madame Selma Azaiez. Je me suis senti chanceux d'avoir mené pendant trois ans, mes travaux de thèse sous leur direction au CEA LIST. Ils ont cru en moi dès le début de ma thèse et m'ont constamment motivé et encouragé pendant ces trois années. Je les remercie plus particulièrement pour leurs encadrements de qualité, leurs disponibilités, leur spontanéité et pour leur professionnalisme remarquable qui m'ont permis de bien mener mes travaux de thèse dans le temps imparti.

Résumé

Les systèmes cyber-physiques sont des systèmes distribués qui intègrent un large panel d'applications logicielles et de ressources de calcul hétérogènes connectées par divers moyens de communication (filaire ou non-filaire). Ces systèmes ont pour caractéristique de traiter en temps-réel, un volume important de données provenant de processus physiques, chimiques ou biologiques. Une des problématiques rencontrée dans la phase de conception des systèmes cyber-physiques est de prédire le comportement temporel des applications logicielles. Afin de répondre à cette problématique, des stratégies d'ordonnancement statique sont nécessaires. Ces stratégies doivent tenir compte de plusieurs contraintes, notamment les contraintes de dépendances cycliques induites par l'exécution des boucles de calculs spécifiées dans les programmes logiciels ainsi que les contraintes de ressource et de communication inhérentes aux architectures matérielles de calcul. En effet, les boucles étant l'une des parties les plus critiques en temps d'exécution pour plusieurs applications de calcul intensif, le comportement temporel et les performances optimales des applications logicielles dépendent de l'ordonnancement optimal des structures de boucles spécifiées dans les programmes de calcul. Pour prédire le comportement temporel des applications logicielles et fournir des garanties de performances dans la phase de conception au plus tôt, les stratégies d'ordonnancement statiques doivent explorer et exploiter efficacement le parallélisme embarqué dans les patterns d'exécution des programmes à boucles intensives tout en garantissant le respect des contraintes de ressources et de communication des architectures de calcul.

L'ordonnancement d'un programme à boucles intensives sous contraintes ressources et communication est un problème complexe et difficile. Afin de résoudre efficacement ce problème, il est indispensable de concevoir des heuristiques. Cependant, pour concevoir des heuristiques efficaces, il est important de caractériser l'ensemble des solutions optimales pour le problème d'ordonnancement. Une solution optimale pour un problème d'ordonnancement est un ordonnancement qui réalise un objectif optimal de performance.

List of Figures

General Context and Problem Statement

During the past decades, advances in hardware and software technologies have led to the development of modern computing systems called cyber-physical systems (CPSs). These systems are attracting a lot of attention in recent years and are being considered as innovative technologies that can improve human life and address many technical, socio-economical and environmental challenges.

What are CPSs? There is a plethora of definitions in the literature [START_REF] Herwan | Cyber-physical system architecture for machining production line[END_REF][START_REF] Lee | A cyber-physical systems architecture for industry 4.0-based manufacturing systems[END_REF][START_REF] Monostori | Cyber-physical production systems: Roots, expectations and R&D challenges[END_REF][START_REF] Haque | Review of Cyber-Physical System in Healthcare[END_REF][START_REF] Lee | Introduction to Embedded Systems, A Cyber-Physical Systems Approach[END_REF][START_REF] Lee | Cyber Physical Systems: Design Challenges[END_REF]] that may agree with our vision. We believe that CPSs are integrations of distributed computing components which interact with each other through wired or wireless communication resources to sense and control physical processes. Unlike traditional embedded systems (smartphones, digital watches, etc.), which are designed as standalone devices, the focus in a CPS is on networking several devices or sub-systems and commanding them remotely in order to interact with physical processes. CPSs find applications in a wide range of domains including manufacturing, healthcare, environment, transportation. In the manufacturing industry, they are being introduced to characterize the upcoming of the fourth industrial revolution, frequently noted as Industry 4.0 [START_REF] Herwan | Cyber-physical system architecture for machining production line[END_REF][START_REF] Lee | A cyber-physical systems architecture for industry 4.0-based manufacturing systems[END_REF][START_REF] Jazdi | Cyber physical systems in the context of Industry 4.0[END_REF][START_REF] Monostori | Cyber-physical production systems: Roots, expectations and R&D challenges[END_REF]. A manufacturing CPS (also called cyber-physical production system) is a production system where equipment such as robots, automated guided vehicles (AGVs), sensors and controllers interact with each other to control and monitor manufacturing operations at all levels of the production, from physical transformation processes through machines up to logistics network. In the healthcare sector, CPSs are being used to remotely monitor the health conditions of in-hospital and in-home patients and to provide healthcare services [START_REF] Haque | Review of Cyber-Physical System in Healthcare[END_REF]. A healthcare CPS is a system that collects the health data of patients through various medical sensors, transmits these data to a gateway via a wired or a wireless communication medium, stores the data in a cloud server and makes these data accessible to caregivers. In environment and transportation areas, large scale CPSs named smart cities [START_REF] Shih | Designing CPS/IoT applications for smart buildings and cities[END_REF] are being deployed to improve the service efficiency and quality of life in the cities. A smart city is one including digitally connected service systems such as transportation, power distribution and public safety systems, which are integrated using various information and communication technologies. In such a city, we will travel in driverless cars that communicate with each other on smart roads and in planes that coordinate to reduce delays. Homes and offices will be powered by a smart grid that use sensors to analyze the environment and optimize energy in real time.

Design Requirements. Each of the CPSs previously presented consists of multiple software applications and embedded computing platforms. The software applications are es-2 ©2020 Philippe Glanon 1.1. General Context and Problem Statement sentially loop-intensive applications -i.e. applications that perform repetitive computations -that generate a huge volume of data processed by the computing platforms. These platforms are usually multiprocessor systems that include a finite number of heterogeneous processing resources, each communicating with the other ones through different communication means. Thus, the computations of software applications can be easily parallelized by distributing data across different processing resources. An important design requirement of CPSs is that the processing resources of a computing platform may be shared between the computations of one or more applications. This requirement can lead to resource conflicts and/or communication bottlenecks when different computations need to access the same resources at the same time, and thus, it can cause a loss of parallelism and a noticeable deterioration of performance achievable by the software applications. To prevent such a situation, CPS designers often need to explore the parallelization choices of computations to different types of multiprocessor architectures. For this purpose, the design approaches for CPSs should be based as much as possible on formal models of computation that deal both with time, concurrency and parallelism. These models should be implementable and analyzable so that the designers may use them to predict the timing behaviour of CPS applications and to provide performance guarantees for these applications at design stage.

Among the popular models of computation, dataflow models are of high interest.

Dataflow models. Dataflow modeling paradigm is characterized by a data-driven style of control where data are processed while flowing through a networks of computation nodes.

A dataflow model is a directed graph where nodes (called actors) describe the computations performed by a loop-intensive application and edges are FIFO channels that describe the dependency relations between the computations. When an actor fires, it consumes a finite number of data tokens and produces a finite number of data tokens. A set of firing rules indicates when the actor is enabled to fire. Dataflow models are often classified into dynamic and static models. Dynamic dataflow models are known to be more expressive than static dataflow models. However, the Turing-completeness and non-decidability of these models has motivated the research community to adopt static dataflow models when it comes to implement and analyze the behaviour of an application. Various types of static dataflow models exists. One of the most known is synchronous dataflow (SDF) model. In a SDF graph, the number of tokens consumed and produced by each actor at each firing is predefined at design stage. SDF graphs has been traditionally used to design streaming and multimedia applications. There interests are increasingly growing nowadays in the CPS design because of their semantics that enables to describe different levels of parallelism in loop-intensive applications and to analyze the timing behaviour and performance of these ©2020 Philippe Glanon applications through the construction of static-order schedules (i.e. infinite repetitions of firing sequences of actors) with bounded FIFO channels.

Scheduling. Scheduling a static dataflow graph consists in finding "when" the firings of each actor must be executed. An optimal schedule of a static graph is a schedule that achieves an optimal performance goal. Interesting performance indicators often analyzed to evaluate the optimality of schedules for static dataflow graphs are usually throughput and latency. From a CPS perspective, the study of these metrics is important to predict the timing behaviour of CPS applications and to provide performance guarantees for these applications. Scheduling strategies for static dataflow graphs can be classified into selftimed schedules (also called as soon as possible schedules) and periodic schedules. In a selftimed schedule, the instances of actors are executed as soon as possible the required data are available while in a periodic schedule, the instances of actors are executed according to a fix time period. Self-timed schedules are known as scheduling strategies that achieve optimal throughput for static dataflow graphs. However, these schedules are more difficult to implement than periodic schedules. A common way to get around the implementation complexity of self-timed schedules is to implement software pipelined (SWP) schedules [START_REF] Udupa | Software Pipelined Execution of Stream Programs on GPUs[END_REF][START_REF] Lam | Software pipelining: An effective scheduling technique for VLIW machines[END_REF]. SWP schedules are a subclass of periodic schedules widely used to analyze the timing behaviour of loop-intensive applications. These schedules provide the same guarantees than self-timed schedules in terms of throughput achievement.

Problem statement.

In this thesis, we address the following problem: given a CPS application modeled by a SDF graph and a CPS platform described by a heterogeneous multiprocessor architecture with a fixed number of communicating processing resources, how can one construct an optimal SWP schedule that achieves the highest performance of the SDF graph under the resource and communication constraints of the given architecture?

Scheduling an application graph under resource and/or communication constraints is a NPhard problem [START_REF] Singh | Mapping on multi/manycore systems: Survey of current and emerging trends[END_REF][START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. Therefore, the problem tackled by this thesis is NP-hard. The main objective of the thesis is to propose efficient strategies to solve this scheduling problem.

Contributions

In order to solve the problem stated above, we have made several contributions to the scheduling of SDF graphs. Our main contributions are the following ones:

• First, we characterize the set of admissible SWP schedules that achieve optimal throughput/latency for timed SDF graphs and we propose linear programming mod-4 ©2020 Philippe Glanon 1.3. Thesis Organization els to compute these schedules.

• Secondly, we show that the problem can be model as an integer linear programming (ILP) model with precise optimization constraints and objective. The ILP model accommodates pipeline, task and data parallelism in SDF graphs and it characterizes the set of SWP scheduling solutions that achieves optimal throughput.

• Thirdly, we propose a guaranteed decomposed SWP scheduling heuristic, that generates approximated SWP scheduling solutions for the problem.

Thesis Organization

This thesis is organized into two parts:

• Part 1. This part presents the motivations, state-of-the-art and a detailed formulation of the problem tackled by this thesis. The part consists of two chapters. The first chapter (chapter 2) gives a quick overview of design requirements and tools for cyber-physical systems. In this chapter, we show why heterogeneous multiprocessor architectures and synchronous dataflow (SDF) model are suited to the design of cyber-physical systems and we present the motivations that pushed us to be interested in the scheduling of SDF graphs on multiprocessor architectures under resources and communication constraints. In the second chapter (chapter 3), we review the basics of the SDF model, we formulate the main problem tackled by this thesis and we present some related works.

• Part 2. In this part we present our contributions. The part is organized into four chapters. In the first chapter (chapter 4), we propose a theorem that characterizes the set of admissible SWP schedules for timed SDF graphs. In this chapter, we also present two linear programming models, one enabling to compute SWP schedules that achieve maximum throughput for timed SDF graphs and the other to compute SWP schedules that achieve minimum latency. In the second chapter (chapter 5), we extend the characterizations made in chapter 4 to formulate an ILP model used to generate SWP scheduling solutions that achieve maximum throughput for SDF graphs on heterogeneous multiprocessor architectures under resource and communication constraints. In this chapter, we also present our decomposed SWP scheduling heuristic that generates approximated scheduling solutions for the resource-constrained and communication-constrained scheduling problem. In the third chapter ©2020 Philippe Glanon (chapter 6), we validate of our contributions thanks to experimental results made with synthetic benchmarks and real-world application benchmarks. In the fourth chapter (chapter 7), we summarize our contributions and present some open research challenges.

©2020 Philippe Glanon

Introduction

This chapter presents the background and motivations of this thesis. In the chapter, we give a quick overview of cyber-physical systems, the multiprocessor architectures, the parallel programming models and we present the motivations that pushed us to be interested in the scheduling of SDF graphs on heterogeneous multiprocessor architectures under resources and communication constraints.

Architecture of Cyber-Physical Systems

Cyber-physical systems (CPSs) can generally be represented as a control-loop structure like that depicted in figure 2.1. There are three parts in this structure. Firstly, there is a physical plant, which represents the "physical part" of a CPS. This part can include human operators, mechanical parts, biological or chemical processes. Secondly, there are computing platforms, each with its own sensors, computing features and/or actuators.

Thirdly, there is a network fabric, which provides the mechanisms for the platforms to communicate. Together, the platforms and the network fabric constitute the "cyber part" of a CPS. and/or a providing specific computing performance. A systematic question that arises when designing the "cyber" part of a CPS, is whether a homogeneous or heterogeneous architectures should be used. In order to provide an answer to this question, Amdahl's law [START_REF] Amdahl | Validity of the single processor approach to achieve large scale computing capabilities[END_REF] can be used to compute the performance provided by both types of systems. This law finds the maximum expected improvement of an overall computer system when only a part of the system is improved. Let speedup be the original execution time of a software program divided by an enhanced execution time. The modern version of Amdahl's law states that if a fraction 𝑓 of a software program is enhanced by a speedup 𝑆, then the overall speedup of this program is given by:

𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑒𝑛ℎ𝑎𝑛𝑐𝑒𝑑 (𝑓 , 𝑆) = 1 (1 -𝑓 ) + 𝑓 𝑆 (2.1)
In the context of multicore and multiprocessor systems, the authors in [START_REF] Hill | Amdahl's law in the multicore era[END_REF] have provided a corollary of Amdahl's law. Let us consider a multiprocessor system (or a multicore machine) with 𝑛 processors (or cores). Under Amdahl's law, the overall speedup of such a system depends on the fraction 𝑓 of software program that can be parallelized, the number 𝑛 of processors in the system and the number 𝑟 of base processors that can be combined to build one bigger processor (or core). In the case of a homogeneous multiprocessor system, one processor is used to execute sequentially the software program at performance 𝑝𝑒𝑟 𝑓 (𝑟 )

and 𝑛/𝑟 processors are used to execute in parallel the program at performance perf (r)×𝑛/𝑟 .

Thus, the overall speedup obtained with this system is given by:

𝑆𝑝𝑒𝑒𝑑𝑢𝑝 ℎ𝑜𝑚𝑜𝑔𝑒𝑛𝑒𝑜𝑢𝑠 (𝑓 , 𝑛, 𝑟 ) = 1 1 -𝑓 perf(r) + 𝑓 • 𝑟 perf(r) • 𝑛 (2.2)
In the case of a heterogeneous multiprocessor system, only the processor with more computation resources is used to execute sequentially at performance perf(r). In the parallel fraction, however, it gets performance perf(r) from the large processor and performance 1 from each of the 𝑛 -𝑟 base processors. Thus, the overall speedup obtained with this system is given by: √ 𝑟 as done in [START_REF] Hill | Amdahl's law in the multicore era[END_REF]. As it can be seen, for a same number of processing units, the speedups obtained with a heterogeneous system is much better than those obtained with a homogeneous system. This observation is an important reason for using heterogeneous multiprocessor architectures for CPSs design.

𝑆𝑝𝑒𝑒𝑑𝑢𝑝 ℎ𝑒𝑡𝑒𝑟𝑜𝑔𝑒𝑛𝑒𝑜𝑢𝑠 (𝑓 , 𝑛, 𝑟 ) = 1 1 -𝑓 perf(r) + 𝑓 perf(r) + 𝑛 -𝑟 (2.

Parallel Programming Paradigm

Previously shown, heterogeneous multiprocessor architectures have an attractive advantage to carry out efficiently parallel computations in CPSs. In order to efficiently exploit the potential of these architectures, different hardware programming mechanisms have been proposed. However, their utilization is extremely complex for designers and programmers.

To overcome this complexity, many programming approaches focus on the specification of software applications intended to run on these computer architectures. Thus, a plethora of application programming models have been proposed to allow users to write their software programs and to specify parallelism in these programs. These models can be classified into multithreading and dataflow models.

Multithreading Programming Models

Multithreading is a programming paradigm based on the utilization of threads to specify concurrency and parallelism in software programs. A thread is a way of making a program to execute two or more computational tasks at the same time. A thread consists of its own program counter, its own stack and a copy of registers of central processing unit (CPUs), but it shares other things like the code that is executing, heap and some data structures.

Several multithreading programming models exist. PThread, OpenMP, MPI and OpenCL Pthread. Pthread also known as POSIX thread [START_REF] Butenhof | Programming With Posix Threads[END_REF] is a low-level application programming model for writing concurrent software programs for shared-memory computer architectures (refer to figure 2.4a). It consists of a library of functions used to define threads accessing to a shared-memory space. The programming model is built on the top of imperative programming language like C and it supports different variants of operating systems including Unix, Windows and Mac OS. Although Pthread has its place in specialized situations, the mechanisms for synchronizing threads is not explicitly defined, which makes the utilization of this programming model difficult for programmers to develop correct and maintainable computer programs [START_REF] Lee | The Problem with Threads[END_REF][START_REF] Diaz | A survey of parallel programming models and tools in the multi and many-core era[END_REF].

OpenMP.

OpenMP [17] is a high-level programming model to write parallel software programs for shared-memory computer systems ranging from desktops to supercomputers.

The implementation of OpenMP exists for three different programming languages including Fortran, C and C++. Contrary to POSIX Thread, the utilization of threads OpenMP is highly structured and threads are implicitly synchronized. In an OpenMP program, when an executing thread encounters a "parallel" directive, it will create a group of threads and become the master thread of this group. Then the group of threads executes the program code assigned to it. When the group has terminated its execution, the master thread collects the results from the group of threads and serially executes from that point on. For example if a "for" loop that will iterate over an array containing 100 elements would be parallelized on a processor with 4 cores, OpenMP will be used to create four threads and execute one thread on each core. The "for" loop will be wrapped in a parallel directive where the limit of threads is four. Then, when the initial thread encounters this directive a fork would occur, four tasks would be created and the goal for each task is to iterate over a subset of the array. This will increase the performance by four times, sometimes more if it benefits from super-linear speedup [17]. Recently, OpenMP has been extended for heterogeneous multiprocessor architectures, which makes it one of the two predominant models for programming many parallel computing systems, the other being Message Passing Interface (MPI) [START_REF]Message Passing Interface Forum. MPI : A Message-Passing Interface Standard[END_REF].

MPI.

As opposed to Pthread and OpenMP, MPI [START_REF]Message Passing Interface Forum. MPI : A Message-Passing Interface Standard[END_REF] is a programming model that was developed for writing portable software programs for distributed-memory computer architectures (refer to figure 2.4b). Similar to OpenMP, the implementations of MPI is also available for C, C++, and Fortran programming languages. Programming with MPI have an attractive advantage that it provides point-to-point and collective communication mod-©2020 Philippe Glanon els to specify the communicating threads, without having to manage their synchronization.

In an MPI program, a computation comprises one or more threads that communicate by calling library routines to send and receive messages to other threads. In most MPI implementations, a fixed set of threads is created at the program initialization, and one thread is created per processor. However, these threads may execute different programs. Hence, the MPI programming model is sometimes referred to as a multiple program multiple data model to distinguish it from the single program multiple data model in which every processing element executes the same program. MPI programming model remains the dominant model used for designing parallel computing application today [START_REF] Sur | High-performance and Scalable MPI over InfiniBand with Reduced Memory Usage: An In-depth Performance Analysis[END_REF].

OpenCL. OpenCL [START_REF] Group | Opencl-the open standard for parallel programming of heterogeneous systems[END_REF] is a low-level standardized programming model designed to support the development of portable software programs intended to run on heterogeneous computing systems with shared memory architectures. OpenCL views a computing system as a set of devices which might be central processing units (CPUs), graphics processing units (GPUs), digital signal processors (DSPs) or field-programmable gate arrays (FPGAs) attached to a host processor (a CPU). OpenCL programs are divided into host and kernel code. In the host program, kernels and memory movements are queued into command queues associated with a device. The kernel language provides features like vector types and additional memory qualifiers. A computation must be mapped to work-groups of work-items that can be executed in parallel on the processing cores of a device. OpenCL programming model is a good option for mapping threads on different processing units.

However, it might be a too low-level programming model for many application-level programmers who would be better served using MPI and OpenMP programming models.

In summary, all of the above mentioned programming models won for general purpose parallel computer systems which involve either shared memory or distributed memory communication mechanisms. However, their utilization is inappropriate in the context of CPSs because of the non-determinism of thread-based programs which can lead to communication overheads, high latencies and/or low throughput and thus decrease the performance of many CPS applications.

A B 2 (a) KPN 1 A B 1 2 (b) HSDF 3 A B 2 2 (c) SDF A [1,2] B [1] 2 (d) CSDF

Dataflow Programming Models

Dataflow programming is a visual programming paradigm that appeared with Karp and

Miller [START_REF] Karp | Properties of a model for parallel computations: Determinacy, termination, queueing[END_REF] can produce a token of data on a channel whenever it wants and must wait when it tries to consume a data token from an empty channel until this data arrives on this channel.

The non-blocking write semantics ensures that actor can produce tokens continuously on the channels while the blocking read semantics ensures that any execution order of actors ©2020 Philippe Glanon will yield the same histories of tokens on the channels. KPN is a Turing-complete model [START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF] that has a high expressiveness to provide a fine-grained description of many computer programs which are inherently partitioned into separate tasks communicating via streams of data. However, like many Turing complete models, KPN is not decidable, i.e. it does not allow deadlocks and performance analysis of computer programs at design time.

HSDF. This model is introduced in 1968 by Reiter [START_REF] Reiter | Scheduling parallel computations[END_REF]. HSDF (figure 2 the HSDF model by allowing the specification of different production and consumption rates on the channels. Thus, actors can produce and consume tokens at different rates.

In a SDF model, when an actor fires, it consumes a fixed number of tokens -which is predetermined in design time -from each of its incoming channels, and it produces a fixed number of tokens on each of its outgoing channels. CSDF. This model is a static dataflow graph introduced in 1995 by Bilsen [START_REF] Bilsen | Cyclo-static data flow[END_REF]. It can be seen as an extension of the SDF model. In a CSDF model (figure 2.5d), the production and consumption rates associated to the FIFO channels are decomposed into finite sequences (also called phases) which may change periodically between the execution instances of 16 phases where it consumes one token in the first phase and two tokens in the second phase.

CSDF is not more expressive than SDF but it is more succinct for describing the computer programs of very large parallel computer systems. However, the complexity to analyze CSDF programs is larger than the analysis complexity of a SDF programs with an equal number of actors [START_REF] Stuijk | Predictable mapping of streaming applications on multiprocessors[END_REF].

To summarize, SDF, HSDF, and CSDF are static dataflow models that impose a restriction on the KPN model to allow static analysis of computer systems at design time.

A detailed comparison of all of these dataflow models have been provided by Stuijk in 2007 [START_REF] Stuijk | Predictable mapping of streaming applications on multiprocessors[END_REF] according to four criteria including expressiveness, succinctness, implementation efficiency and analysis potential. Table 2.1 presents a summarized comparison of these dataflow models. From this table, we can clearly see that, SDF model is the one that provides a good compromise. In this thesis, we will focus on the utilization of SDF graphs to specify parallelism in CPS applications and to analyze the performance achievable by these applications on heterogeneous multiprocessor architectures.

Deployment of Loop-Intensive Applications

A key aspect in the design of a CPS is the software deployment through which the computations of CPS applications are scheduled and mapped on the PUs of heterogeneous multiprocessor architectures. Scheduling a computation consists to find "when" this computation must start its execution while mapping a computation consists in finding "where" the computation should be executed. The scheduling and mapping of computations for

©2020 Philippe Glanon A[k] ← A[k-1] ⊙ D[k-3] B[k] ← B[k-1] ⊙ A[2k] ⊙ A[2k+1] C[k] ← A[floor(k/2)] D[k] ← D[k-1] ⊙ B[floor(k/2)] ⊙ C[2k] ⊙ C [2k+1]
(a) Loop-intensive program CPS applications depend on many parameters which include for instance, the number of PUs available on the multiprocessor architectures, the worst-case execution times of computations onto the PUs and the inter-PUs communication latencies. In addition to these parameters, loop-carried dependencies should be considered. Actually, loops usually being the most time-critical parts of many software applications, the performance achievable by the applications depends on the optimal execution of loops embedded in the software programs. Therefore, to predict the timing behaviour of CPS applications and to provide performance guarantee at design stage, there is a need of exploring and exploiting the parallelism embedded in the execution pattern of loops. For this purpose, we will show that SDF graphs can be very helpful.

Modeling and Exploitation of Parallelism

SDF graphs provide various mechanisms to model and exploit different levels of parallelism such as data, task and pipeline parallelisms in loop-intensive programs. Actually, the actors of a SDF graph that describes a loop-intensive program can be specified either as stateful or as stateless. A stateful actor is an actor whose execution instances are scheduled in a sequential order while a stateless actor is an actor whose execution instances are scheduled out of order, or in parallel across different PUs. These types of actors respectively enable to specify pipeline and data parallelisms in loop-intensive programs. A stateful actor is often described as a node with a self-loop channel, where the channel consists of a fixed number of tokens that represents the distance separating the successive execution instances of the stateful actor. Figure 2.6 depicts a loop-intensive program and its equivalent SDF graph.

The loop-intensive program of four instructions and four computing functions (𝐴, 𝐵, 𝐶 and 𝐷). Each instruction is a logical and/or arithmetic operation that describes one or several dependency relations between the different invocations of the functions. For instance, the

instruction 𝐴[𝑘] ← 𝐴[𝑘 -1] ⊙ 𝐷 [𝑘 -3
] is an arithmetic (or logical) operation that describes two dependency relations: a dependency from the (𝑘 -1) 𝑡ℎ invocation of actor A to the 𝑘 𝑡ℎ invocation of this actor and a dependency from the (𝑘 -3) 𝑡ℎ invocation of actor 𝐷 to the 𝑘 𝑡ℎ invocation of actor A. This loop-intensive program is graphically described by the SDF graph shown in Fig. 2.6b. This graph consists of four actors (𝐴, 𝐵, 𝐶, 𝐷), each describing a computing funtion of the program. Actors 𝐴, 𝐵 and 𝐷 are stateful actors while actor 𝐶 is a stateless actor. All of these actors are connected by a set of channels, each describing the flows of data exchanged between the computations, and some containing an initial number of tokens describing the distance separating the successive execution instances of connected actors. When deploying this graph on a multiprocessor architecture, data parallelism can be exploited by scheduling and mapping the execution instances of the actor 𝐶 on a dataparallel processor or on different PUs. At the same time, pipeline parallelism can be exploited by scheduling and mapping the execution instances of a stateful actor on different PUs in such a way that the successive executions of these execution instances can overlap over time. Alongside with data and pipeline parallelisms, task parallelism can also be exploited by scheduling and mapping the execution instances of actors 𝐵 and 𝐶 on different PUs. Figure 2.7 illustrates the exploitation of these three types of parallelisms. The joint exploitation of task, data and pipeline parallelisms is known to improve the performance achievable by loop-intensive applications [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF]. Therefore, to ensure performance guarantee for CPS applications, it is important that the scheduling and mapping strategies for these applications exploit efficiently these three kinds of parallelisms.

The two most prominent performance measurements for applications modeled by SDF graphs are latency, which reflects the delay induced by a channel to transfer a token of data between dependent execution instances, and throughput, which indicates for each actor, the execution rate per unit time. From a CPS perspective, the study of these properties are of a high interest to characterize the timing behaviour of loop-intensive programs and to provide performance guarantee for CPS applications. Consequently, in this thesis, we focus on the characterization and analysis of these two performance metrics.

Scheduling under resource and communication constraints

An important design requirement for CPS applications is that, the heterogeneous multiprocessor architectures on which the computations are intended to be deployed, must contain ©2020 Philippe Glanon a finite number of processing and communication resources, and these resources have to be shared between the computations of one or more applications. This requirement can often lead to resource conflicts and/or communication bottlenecks when different computations need to access the same resources at the same time, and thus can cause a loss of parallelism and an deterioration of performance achievable by CPS applications. In order to prevent such a situation, there is a need of developing static scheduling and mapping strategies that can accommodate the resource and communication constraints of multiprocessor architectures to reduce in the early design stage of the applications, the over-allocation of resources needed for computations to meet their timing constraints. Since most of CPS applications are essentially loop-intensive applications, it is important that the scheduling strategies respect the loop-carried dependencies constraints of these application, and ensure that the performance achievable by a computation is not influenced by the other computations assigned to the same resources.

Scheduling computations with dependency relations on multiprocessor architectures under resource and/or communication constraints is a NP-complete problem well-known in the literature [START_REF] Singh | Mapping on multi/manycore systems: Survey of current and emerging trends[END_REF][START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. Many authors have proposed several static scheduling approaches to tackle this problem with the goal of optimizing different performance metrics. A detailed survey of these approaches can be found in [START_REF] Singh | Mapping on multi/manycore systems: Survey of current and emerging trends[END_REF]. Among the existing works, there are a number [START_REF] Schwarzer | Throughputoptimizing Compilation of Dataflow Applications for MultiCores using Quasi-Static Scheduling[END_REF][START_REF] Lesparre | Efficient evaluation of mappings of dataflow applications onto distributed memory architectures[END_REF][START_REF] Bodin | K-Periodic Schedules for Evaluating the Maximum Throughput of a Synchronous Dataflow Graph[END_REF][START_REF] Stuijk | Predictable mapping of streaming applications on multiprocessors[END_REF][START_REF] Udupa | Software Pipelined Execution of Stream Programs on GPUs[END_REF][START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF] that uses SDF graphs to tackle the problem. However, most of these works are limited to the scheduling of SDF graphs on homogeneous multiprocessor architectures. Among the works [START_REF] Avinash | Heuristics on Reachability Trees for Bicriteria Scheduling of Stream Graphs on Heterogeneous Multiprocessor Architectures[END_REF][START_REF] Paul | Mapping stream programs onto heterogeneous multiprocessor systems[END_REF][START_REF] Gilbert | A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures[END_REF]

Conclusion

In this chapter, we have presented the background and motivations that pushed us to be interested in the scheduling of SDF graphs on heterogeneous multiprocessor architectures under resource and communication constraints. In the next chapter we will review the basics of the SDF model and will present a succinct formulation of the main problem tackled by this thesis.

Introduction

In this chapter we review the basics of the synchronous dataflow (SDF) model, which was introduced informally in the previous chapter, then we formulate the problem tackled by this thesis and we succinctly describe our main contributions. The chapter is organized as follows. Section 3.2 presents basic definitions and structural properties of SDF graphs.

Section 3.3 reviews the static scheduling strategies for SDF models. Section 3.4 presents a succinct description of the main problem tackled by this thesis as well as the related works.

Synchronous Dataflow Graphs

Definition

A SDF graph is a multi-rate dependency graph 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) where:

• 𝑉 is a finite set of nodes called actors.

• 𝐸 ⊆ 𝑉 2 is a finite set of arcs representing First-in First-out (FIFO) channels.

• 𝑃 = {𝑝 𝑒 ∈ ℕ * | 𝑒 = (𝑖, 𝑗) ∈ 𝐸} is the set of production rates given by the function 𝑝 : 𝐸 → ℕ * that associates a production rate 𝑝 𝑒 with each channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸.

• 𝐶 = {𝑐 𝑒 ∈ ℕ * | 𝑒 = (𝑖, 𝑗) ∈ 𝐸} is the set of consumption rates given by the function 𝑐 : 𝐸 → ℕ * that associates a consumption rate 𝑐 𝑒 with each channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸.

• 𝑀 0 = {𝑚 0 (𝑒) ∈ ℕ| 𝑒 = (𝑖, 𝑗) ∈ 𝐸} is the set of initial markings given by the function 𝑚 0 : 𝐸 → ℕ that associates a fixed number 𝑚 0 (𝑒) of tokens with each channel 𝑒 ∈ 𝐸. For the rest of the manuscript, let us denote the execution instances of actors in terms of firings and let us denote the timed SDF graphs as 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿).

2 1 2 2 1 1 2 1 1 1 3 1 1 1 1 1 1 1 1 1 A, 3 B, 4 C, 2 D, 2

Consistency Analysis

Consistency is a property that has been introduced initially by Lee and Messerschmitt [START_REF] Lee | Synchronous data flow[END_REF] to ensure that actors of a SDF graph can be statically scheduled with a bounded number of tokens. Let us consider a SDF graph 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) and let Θ be the topology matrix of this graph, where Θ is a matrix of size |𝐸| × |𝑉 | defined by:

Θ 𝑒𝑖 =          𝑝 𝑒 if 𝑒 = (𝑖, 𝑗), 𝑗 ∈ 𝑉 -𝑐 𝑒 if 𝑒 = ( 𝑗, 𝑖), 𝑗 ∈ 𝑉 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝐺 𝑠𝑑 𝑓 is said consistent if the rank of the matrix Θ is equal to |𝑉 | -1.
To illustrate this property, let us consider the SDF graph shown in figure 2.6b. The topology matrix of this graph is given by:

Θ =             1 -2 0 0 2 0 -1 0 0 2 0 -1 0 0 1 -2 -1 0 0 1             A B C D e=(A, B) e=(A, C) e=(B, D) e=(C, D) e=(D, A) Considering this topology matrix, it is possible to check that 𝑟𝑎𝑛𝑘 (Θ) = |𝑉 | -1 = 3.
This means that the SDF model described by this matrix is consistent. Actually, the consistency property ensures the existence of a minimum vector 𝑞 ∈ ℕ * |𝑉 | with coprime components such that Θ.𝑞 𝑇 = 0. This vector is called the repetition vector and its components are called granularities or repetition factors. The granularity 𝑞 𝑖 of an actor 𝑖 ∈ 𝑉 corresponds to the minimum number of firings required for this actor to achieve a single iteration 1 .

Thus, checking the consistency of a SDF model is equivalent to checking the existence of 1 An iteration of a SDF graph is an execution sequence that brings back the graph to its initial state.

24

©2020 Philippe Glanon 3.2. Synchronous Dataflow Graphs a repetition vector. For any SDF graph, the existence condition of a repetition vector is defined by:

𝑝 𝑒 × 𝑞 𝑖 = 𝑐 𝑒 × 𝑞 𝑗 ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸. (3.1)
Let us going back to the SDF graph depicted in figure 2.6b, if we want to check the existence of a repetition vector for this graph, we must try to solve the following system of equations:

                                   1 × 𝑞 𝐴 = 1 × 𝑞 𝐴 1 × 𝑞 𝐴 = 2 × 𝑞 𝐵 2 × 𝑞 𝐴 = 1 × 𝑞 𝐶 1 × 𝑞 𝐵 = 1 × 𝑞 𝐵 2 × 𝑞 𝐵 = 1 × 𝑞 𝐷 1 × 𝑞 𝐶 = 2 × 𝑞 𝐷 1 × 𝑞 𝐷 = 1 × 𝑞 𝐴 1 × 𝑞 𝐷 = 1 × 𝑞 𝐷
The solution of this system of equations gives a repetition vector

𝑞 = [𝑞 𝐴 , 𝑞 𝐵 , 𝑞 𝐶 , 𝑞 𝐷 ] = [2, 1, 4, 2]
which proves that the SDF graph is consistent.

Liveness Analysis

Liveness is a property which ensures that every actor of a static dataflow model can be fired infinitely often without encountering deadlocks during the execution of the model.

Liveness checking is a well-known problem extensively studied in the dataflow community.

In 1971, Commoner et al. [START_REF] Commoner | Marked directed graphs[END_REF] have proposed the following theorem that serves as necessary and sufficient condition to ensure the liveness of marked graphs, which are named homogeneous synchronous dataflow (HSDF) graphs in the dataflow community.

Theorem 3.1 (Commoner et al. [64]). A HSDF graph is live if and only if the token count of every directed circuit is positive.

Based on this theorem, 2.6b. This HSDF representation also called linear constraint graph, is obtained with the algorithm of de Groote et al. [START_REF] De Groote | Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs[END_REF], which enables to generate for any consistent SDF graph, an equivalent HSDF graph with fewer channels.

The different steps of this algorithm are explicitly detailed by Algorithm 1. Considering the equivalent HSDF graph, the algorithm of Commoner et al. [START_REF] Commoner | Marked directed graphs[END_REF] can easily be applied to check liveness. For this liveness checking technique, it is important to mention that the transformation of a SDF graph to an equivalent HSDF graph may lead sometimes to a graph of exponential size, and thus can make exponential the time and space complexity of this technique. The second technique for liveness checking [START_REF] Ghamarian | Liveness and Boundedness of Synchronous Data Flow Graphs[END_REF] consists in performing the symbolic execution of the SDF graph -i.e. to execute all the actors of the model exactly as many times as indicated by the repetition vector -until the graph reaches a repetitive where 𝑔𝑐𝑑 (𝑝 𝑒 , 𝑐 𝑒 ) is the greatest common divisor of 𝑝 𝑒 and 𝑐 𝑒 . As it can be noted, Theorem 3.2 is based on the normalized SDF graphs. A SDF graph is said normalized if for every actor the consumption and production rates are identical. Normalization is a concept introduced by Marchetti and al. [START_REF] Marchetti | Kordon A sufficient condition for the liveness of weighted event graphs[END_REF] to simplify the liveness analysis of SDF graphs. Let Using this normalized SDF graph, Theorem 3.2 can easily be applied with a polynomialtime algorithm [START_REF] Marchetti | Kordon A sufficient condition for the liveness of weighted event graphs[END_REF] based on depth first search to ensure the existence of a live marking.

1 2 1 1 1 B 1 C 1 C 2 A 1 A 2 C 3 C 4 D 1 D 2
It is important to remind that Theorem 3.2 is actually a sufficient condition that ensures the liveness property for SDF graphs but it is not a necessary condition. As counter example, figure 3.5 shows a normalized SDF graph for which Theorem 3.2 does not hold since ∑ ∀𝑒=(𝑖,𝑗) ∈𝜇 𝑚 0 (𝑒) = 9 , and

∑ ∀𝑒=(𝑖,𝑗) ∈𝜇 𝑐 𝑒 -𝑔𝑐𝑑 (𝑝 𝑒 , 𝑐 𝑒 ) = 12;
However, a live marking can be obtained by the execution sequence DDDBAAAC that achieves an iteration of the graph.

Static Scheduling of Synchronous Dataflow Graphs

Static scheduling of SDF graphs have been the object of many studies in the dataflow community. Scheduling a SDF graph consists in associating a starting time to the firings of each actor according to a given strategy that does not violate the precedence constraints imposed by the channels. A SDF graph can be statically scheduled if and only if it is consistent and live. Consistency and liveness are the fundamental properties ensuring that a SDF graph can be executed repetitively with a bounded number of tokens without encountering deadlocks. This section reviews the basics of static scheduling techniques for SDF graphs.

Basic Definitions and Theorems

Self-timed Schedules Versus Periodic Schedules

Admissible schedules for SDF graphs can be classified into self-timed and periodic schedules. In a self-timed schedule, the firing of an actor is executed as soon as the necessary tokens of data are available while in a periodic schedule, the firing of an actor is executed according to a specific time period often called initiation interval.

Definition 3.3 (self-timed schedule).

Let 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live SDF graph, let 𝜎 be an admissible schedule for 𝐺 𝑡 𝑠𝑑 𝑓 and let P (𝐸) ⊆ ℕ 2 , be a set of tuples (𝑘 𝑖 , 𝑘 𝑗 ) such that ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, there exists a dependency relation from ⟨𝑘 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 , 𝑗⟩. The schedule 𝜎 is said self-timed if and only if the following conditions holds.

• Condition 1: 𝜎 (𝑘 𝑖 , 𝑖) ≥ 0, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ ℕ. • Condition 2: 𝜎 (𝑘 𝑗 , 𝑗) ≥ 𝜎 (𝑘 𝑖 , 𝑖) + 𝛿 𝑖 , ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀(𝑘 𝑖 , 𝑘 𝑗 ) ∈ P (𝐸).
The self-timed schedule of any SDF graph consists of a finite sequence of firings, called the transient phase followed by a sequence of firings which is repeated infinitely often and is called the periodic phase.

Static Scheduling of Synchronous Dataflow Graphs

SDF graph presented in figure 3.1. This schedule shows three iterations of the graph, each described with a specific colour. We recall that the iteration of a SDF graph is the sequence of firings that brings back the graph to its initial state. The sequence of firings in the first iteration describes the transient phase while the sequences of firings in the other iterations describe the periodic phase. In this schedule, the number of processing resources that execute the firings of actors is assumed to be unbounded and the firings of stateless actors can be executed in parallel on different processing resources. Self-timed schedule is a scheduling strategy that achieves optimal throughput and provide performance guarantee for applications modeled by SDF graphs [START_REF] Sriram | Embedded multiprocessors: scheduling and synchronization, 2nd edn[END_REF][START_REF] Stuijk | Predictable mapping of streaming applications on multiprocessors[END_REF]. However, the time complexity to compute the sequences of firings describing the transient phase is commonly admitted to be exponential and difficult to evaluate. This makes the computation of self-time schedules exponential and difficult to implement.

In order to surround the implementability complexity of self-timed schedules, r-periodic schedules [START_REF] Hanen | Cyclic scheduling[END_REF] have been introduced.

Definition 3.4 (Periodic Schedules). Let 𝐺 𝑡

𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live timed SDF graph and let 𝜎 be an admissible a schedule for 𝐺 𝑡 𝑠𝑑 𝑓 . The schedule 𝜎 is said periodic with period 𝜆 ∈ ℚ + * , if for any actor 𝑖 ∈ 𝑉 there exists 𝑠 𝑖 ∈ ℚ + such that the following set of equations hold:

𝜎 (𝑘 𝑖 , 𝑖) = 𝑠 𝑖 + 𝑘 𝑖 • 𝜆, ∀𝑘 𝑖 ∈ ℕ (3.3)
where 𝑠 𝑖 is the time at which an actor 𝑖 must be scheduled to fire and 𝜆 is the time period between two successive iterations of 𝐺 𝑡 𝑠𝑑 𝑓 in the schedule 𝜎. In the class of periodic schedules, software pipelined (SWP) schedules [START_REF] Govindarajan | Minimizing Register Requirements Under Resource-constrained Rate-optimal Software Pipelining[END_REF][START_REF] Govindarajan | A Novel Framework for MultiRate Scheduling in DSP Applications[END_REF][START_REF] Govindarajan | Rate Optimal Schedule for multi-rate DSP computation[END_REF][START_REF] Lam | Software pipelining: An effective scheduling technique for VLIW machines[END_REF] are of a hight interest.

Definition 3.5 (SWP Schedules). Let 𝐺 𝑡

𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live SDF graph and 𝜎 be a schedule of 𝐺 𝑡 𝑠𝑑 𝑓 . The schedule 𝜎 is said software pipelined with period 𝜆 if the following set of constraints hold: time at which the firing ⟨𝑘 𝑖 , 𝑖⟩ is scheduled in the 𝑛 𝑡ℎ iteration of 𝐺 𝑠𝑑 𝑓 and 𝜎 (𝑘 𝑖 , 𝑖) ∈ ℚ + the time at which the firing ⟨𝑘 𝑖 , 𝑖⟩ must be scheduled to start. Figure 3.7 depicts a SWP schedule of the timed SDF graph shown in figure 3.1. In this schedule, the number of processing resources that execute the firings of actors is assumed to be unlimited and the firings of stateless actors can be executed in parallel on different processing resources. As it can be noted, the firings of each actor are executed according to a time period (𝜆 = 9) that enables to overlap the successive iterations of the SDF graph. Like self-timed schedules, SWP schedules achieve maximum throughput for applications modeled by SDF graphs; however, they are easier to implement than self-time schedules. In this thesis, we will focus on the SWP scheduling strategy to deploy the loop-intensive programs modeled by SDF graphs on heterogeneous multiprocessor architectures.

𝜎 (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖) = 𝜎 (𝑘 𝑖 , 𝑖) + 𝑛 × 𝜆, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑛 ∈ ℕ (3.

Throughput Evaluation

Let 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a live and consistent SDF graph and let 𝜎 be an SWP schedule of period 𝜆 for 𝐺 𝑡 𝑠𝑑 𝑓 . The throughput of an actor 𝑖 ∈ 𝑉 is the average number of firings occurred within a time interval in the schedule 𝜎 and the throughput of 𝐺 𝑡 𝑠𝑑 𝑓 is defined as the average number of stable iterations initiated per time unit in the schedule 𝜎. More formally, if we denote by 𝛽 𝑖 the throughput of actor 𝑖 ∈ 𝑉 , then 𝛽 𝑖 is given by: As 𝜆 is proportional to 𝛽, we will note that the schedules that minimize the period 𝜆 for a SDF graph maximize implicitly the throughput 𝛽.

𝛽 𝑖 = lim
It is well known that the period 𝜆 achievable by a SDF graph in a given schedule, is governed by the loop-carried dependencies induced by the channels of this graph. In order to handle these dependencies, the SDF graph is often transformed into an equivalent HSDF graph which exhibits all the dependency relations between the different firings of actors.

Using the equivalent HSDF graph, the period 𝜆 is given by:

𝜆 = max ∀𝐶∈𝑐𝑦𝑐𝑙𝑒𝑠 𝑑 (𝐶) 𝑚(𝐶) (3.6)
where 𝑑 (𝐶) is the sum of delays (i.e the sum of WCETs) of nodes in a cycle 𝐶 of the HSDF graph, and 𝑚(𝐶) is the sum of tokens around 𝐶 [START_REF] Sriram | Embedded multiprocessors: scheduling and synchronization, 2nd edn[END_REF][START_REF] Dasdan | Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems[END_REF][START_REF] Govindarajan | Minimizing Register Requirements Under Resource-constrained Rate-optimal Software Pipelining[END_REF]. The minimum period achievable by the HSDF graph is then given by the cycles with the minimum value of 𝜆.

Latency Evaluation

The latency T of a SDF graph is the maximum time required to complete a single iteration of this graph. In other words, this time corresponds to the response time of the SDF graph in a given schedule. Going back to the timed SDF graph of our running example (refer to figure 3.1) and the SWP schedule of this SDF graph (refer to figure 3.7), one can note that the length of the maximum time interval required to achieve a single iteration of the graph is T = 14, which corresponds to the latency (or the response time) of this graph. The minimum latency achievable by a SDF graph depends on the minimum latency induced by the channels of this graph. The latency induced by a channel is generally defined in terms of firings. Let 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live SDF graph and let 𝜎 be a SWP schedule of 𝐺 𝑠𝑑 𝑓 . Let (𝑘 𝑖 , 𝑘 𝑗 ) be a couple of positive integers. If the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 , 𝑗⟩ then, the latency induced by the channel between these firings is the time elapsed between the end of ⟨𝑘 𝑖 , 𝑖⟩ and the beginning of ⟨𝑘 𝑗 , 𝑗⟩. More formally, this latency is given by:

T 𝑘 𝑖 𝑘 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝛿 𝑖 (3.7)
Using equation 3.7, one can characterize the set of admissible schedules that achieve minimum latency for 𝐺 𝑡 𝑠𝑑 𝑓 . We will note that the schedules that minimize latency for a SDF graph do not necessarily maximize throughput for this graph. In the next chapter, we will ©2020 Philippe Glanon show how to characterize the SWP schedules that achieve minimum latency for a timed SDF graph as well as the SWP schedules that achieve maximum throughput.

Problem Formulation and Related Works

In this section, we formulate and illustrate the main problem tackled by this thesis and we present related works.

Let 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) be a cyclic, consistent, live and non-timed SDF graph, that describes a loop-intensive application and let 𝐺 ℎ𝑚𝑎 = (𝑅, Δ, Γ) be an heterogeneous multiprocessor architecture (HMA) on which 𝐺 𝑠𝑑 𝑓 is intended to be deployed, where:

• 𝑅 is a finite set of heterogeneous processing units (PUs), each connecting with the other ones through logic communication links.

• Δ is a matrix of size |𝑅| × |𝑉 | that specifies the computation costs Δ 𝑥𝑖 , where Δ 𝑥𝑖 is the worst-case execution time of a single firing of an actor 𝑖 ∈ 𝑉 on a PU 𝑥 ∈ 𝑅.

• Γ is a matrix of size |𝑅|×|𝑅| that specifies the communication costs Γ 𝑥𝑦 , where Γ 𝑥𝑦 = Γ 𝑦𝑥 is the worst-case delay to transmit a single token of data from 𝑥 to 𝑦. Note that if

𝑥 = 𝑦 then Γ 𝑥𝑦 = Γ 𝑦𝑥 = 0 otherwise Γ 𝑥𝑦 ≠ 0 and thus Γ 𝑦𝑥 ≠ 0.
Problem. Assuming the SDF graph 𝐺 𝑠𝑑 𝑓 and the architecture model 𝐺 ℎ𝑚𝑎 , the problem tackled here is to find an optimal SWP schedule 𝜎 of period 𝜆 for 𝐺 𝑠𝑑 𝑓 -i.e. a SWP schedule that achieves maximum throughput -under the following constraints: 34 ©2020 Philippe Glanon

Problem Formulation and Related Works

• 𝑐𝑦𝑐𝑙𝑖𝑐𝑖𝑡𝑦 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠: each firing of each actor 𝑖 ∈ 𝑉 is executed cyclically on the PUs of 𝐺 ℎ𝑚𝑎 according to a period 𝜆 such that:

𝜎 (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖) = 𝜎 (𝑘 𝑖 , 𝑖) + 𝑛 × 𝜆, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑛 ∈ ℕ
where 𝑞 𝑖 is the granularity of actor 𝑖 ∈ 𝑉 .

• 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠: each firing of each actor 𝑖 ∈ 𝑉 can only be assigned to a single PU 𝑥 ∈ 𝑅 and the execution of two firings assigned to this PU cannot overlap.

• 𝑝𝑟𝑒𝑐𝑒𝑑𝑒𝑛𝑐𝑒 𝑎𝑛𝑑 𝑐𝑜𝑚𝑚𝑢𝑛𝑖𝑐𝑎𝑡𝑖𝑜𝑛 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠: for any (𝑘 𝑖 , 𝑘 𝑗 ) ∈ ℕ 2 and any channel 𝑒 = (𝑖, 𝑗) ∈ 𝑉 , if the channel 𝑒 induces a dependency relation from a firing ⟨𝑘 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 , 𝑗⟩ and if these firings are respectively assigned to the PUs 𝑥, 𝑦 ∈ 𝑅, such that 𝑥 ≠ 𝑦, then, there exists a non-zero communication costs Γ 𝑥𝑦 between these firings and the following inequality is satisfied:

𝜎 (𝑘 𝑗 , 𝑗) ≥ 𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 + Γ 𝑥𝑦 .
In order to illustrate this problem, let us consider the system architecture depicted in figure 3.8. This architecture describes a cyber-physical system (CPS), which is a feedback control system. This system consists of sensors, actuators and a heterogeneous computing system.

The heterogeneous computing system is a multiprocessor computing system composed of three heterogeneous PUs, each connected with the other ones through communication links that enable data parallel transmission, and each offering a specific performance to execute the computations of the CPS applications. Each pair of PUs is connected with a single communication link, which has a specific cost for data transmission. Let us assume that this computing system is intended to execute the loop-intensive program described by the non-timed SDF graph of our running example (refer to figure 2.6b). The computation and communication costs matrices for executing the actors of these graphs are given by figure 3.8b. Considering these matrices, we are looking for an optimal SWP that achieves maximum throughput for SDF graph under the resource and communication constraints of the architecture considered.

Readers who are familiar with the literature of software pipelining of loop-intensive programs [START_REF] Jiang | Synthesizing distributed pipelining systems with timing constraints via optimal functional unit assignment and communication selection[END_REF][START_REF] Hatanaka | A software pipelining algorithm of streaming applications with low buffer requirements[END_REF][START_REF] Wei | Software Pipelining for Stream Programs on Resource Constrained Multicore Architectures[END_REF][START_REF] Udupa | Software Pipelined Execution of Stream Programs on GPUs[END_REF][START_REF] Feautrier | Fine-grain scheduling under resource constraints[END_REF][START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF][START_REF] Govindarajan | Minimizing Register Requirements Under Resource-constrained Rate-optimal Software Pipelining[END_REF][START_REF] Hanen | Cyclic scheduling on parallel processors: an overview[END_REF][START_REF] Ning | A novel framework of register allocation for software pipelining[END_REF][START_REF] Lee | An effective methodology for functional pipelining[END_REF][START_REF] Lam | Software pipelining: An effective scheduling technique for VLIW machines[END_REF] will find the optimality objective of this problem very ambitious because of the consideration of resource constraints, which make NP-hard, the complexity to solve this problem. Whether communication constraints are considered further, the space of solutions for the problem is reduced and thus, the ©2020 Philippe Glanon Jiang et al., [START_REF] Jiang | Synthesizing distributed pipelining systems with timing constraints via optimal functional unit assignment and communication selection[END_REF] This thesis complexity to find an optimal solution is NP-hard in the strong sense. Consequently, to solve efficiently the problem, heuristics are necessary. However, before designing efficient heuristics, we need to characterize the set of optimal solutions. For this purpose, the problem can be formulated as an integer linear program (ILP), which can be solved by means of ILP solvers to generate optimal solutions even in non-polynomial time. Based on the performance achievable by the ILP solver, we could thus, characterize efficient scheduling heuristics for the problem.

ILP-based Scheduling Approaches

During the past decades, a variety of ILP formulations have been proposed to tackle the resource-constrained SWP scheduling problems of loop-intensive programs.

Feautrier et al. [START_REF] Feautrier | Fine-grain scheduling under resource constraints[END_REF] and Govindarajan et al. [START_REF] Govindarajan | Minimizing Register Requirements Under Resource-constrained Rate-optimal Software Pipelining[END_REF] have proposed discrete-time ILP formulations for solving the resource-constrained SWP scheduling of loop-intensive programs.

These ILP formulations hold both for architectures with homogeneous resources and those with heterogeneous resources. However, none of the proposed ILP models consider communication constraints, which are inherent to the SWP scheduling problem tackled by this thesis. Moreover, in their ILP formulations, Feautrier [START_REF] Feautrier | Fine-grain scheduling under resource constraints[END_REF] and Govindarajan et al.

[49] assumed that the loop-intensive programs are described with single-rate dependency graphs -i.e HSDF graphs -, which are particular cases of SDF graphs (refer to the previous chapter). Although SDF graphs can be converted into HSDF graphs, it could be interesting to avoid the conversion costs of SDF graphs by formulating an ILP model that operates directly on the SDF graphs.

Recently, Udupa et al. [START_REF] Udupa | Software Pipelined Execution of Stream Programs on GPUs[END_REF]

Scheduling Heuristics

Aside the ILP-based scheduling techniques, we have investigated the existing heuristics for tackling the resource-constrained SWP scheduling of static dataflow graphs. Indeed, there exists a number of heuristics in the literature, that deal with the resource-constrained SWP scheduling of loop-intensive programs modeled by single-rate dependency graphs.

Hanen and Munier [START_REF] Hanen | Cyclic scheduling on parallel processors: an overview[END_REF] have proposed heuristics for acyclic dependency graphs, to derive resource-constrained SWP schedules on architectures with homogeneous resources.

Basically, the idea of these heuristics consists of two steps. The first step is to add some arcs to the acyclic dependency graphs. These new arcs link nodes to be executed on the same group of processing resources. The second step is to partition the processing resources into groups and to pipeline nodes on these resources. The proposed heuristics look quite powerful, although not guaranteed.

Wang and Eisenbeis [START_REF] Wang | Decomposed software pipelining[END_REF], Robert et al. [START_REF] Robert | Circuit Retiming Applied to Decomposed Software Pipelining[END_REF], Gasperoni and Schwielgelshohn [START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF] have introduced decomposed SWP scheduling heuristics, to derive resource-constrained SWP schedules for cyclic dependency graphs. Given a loop modeled by a single-rate cyclic dependency graph, the general idea of decomposed SWP scheduling heuristics consists of four steps. In the first step, the cyclic dependency graph is scheduled under unlimited resources i.e. without resource constraints. In the second step, some information from the schedule obtained in the first step is available to delete some arcs in the cyclic dependency graph so as to obtain an acyclic dependency graph. This acyclic dependency graph is scheduled under resource constraints in the third step using a list scheduler. Finally, in the fourth step, a resource-constrained SWP schedule is deduced using the information obtained in the schedules performed in the first and third steps. Although these heuristics are guaranteed, none of them consider neither architectures with heterogeneous resources, nor with communication constraints.

©2020 Philippe Glanon

This Work

Table 3.1 summarizes the related works previously presented and it highlights the criteria considered by these works to schedule loop-intensive applications modeled by static dataflow graphs. In this work we consider both cyclicity, resource, precedence and communication constraints to schedule loop-intensive applications modeled by SDF graphs on heterogeneous multiprocessor architectures. To the best of our knowledge, there is no work in the current literature that tackles such a scheduling problem. In order to solve this problem, we propose:

• An ILP model to characterize the set of optimal SWP schedules that maximizes throughput for SDF graphs on heterogeneous multiprocessor architectures. Our ILP model accommodates both cyclicity, resource, precedence, communication constraints and it exploits efficiently task, data and pipeline parallelisms specified in the application graphs.

• A SWP scheduling heuristic based upon the heuristic of Gasperoni and Schwielgelshohn, that generates approximated SWP scheduling solutions for the problem.

Conclusion

In this chapter, we have reviewed the basics of SDF models and the static scheduling strategies to execute these models. We have also presented a detailed description of the main problem tackled by this thesis, as well as the related works. In the next part of the manuscript, we will detail explicitly our contributions.

©2020 Philippe Glanon

Part II Contributions

Introduction

In this chapter, we characterize the software pipelined (SWP) schedules that achieve optimal throughput/latency for timed SDF graphs. Characterizations made in this chapter will be extended in the next chapter to provide an integer linear programming formulation for the SWP scheduling problem of SDF graphs under resource and communication constraints. The current chapter is organized as follows. In section 4.2, we characterize the set of admissible SWP schedules for timed SDF graphs. In section 4.3, we characterize and compute the SWP schedules that achieve maximum throughput for timed SDF graphs. In section 4.4 we characterize the SWP schedules that achieve minimum latency for timed SDF graphs and we conclude in section 4.5.

Characterization of Admissible SWP Schedules

Let us consider a timed SDF graph 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) with a repetition vector 𝑞 and let us assume that 𝐺 𝑡 𝑠𝑑 𝑓 is live and consistent. According to definition 3.2, a schedule is said admissible for 𝐺 𝑡 𝑠𝑑 𝑓 if and only if it fulfils the precedence constraints imposed by every channel of 𝐺 𝑡 𝑠𝑑 𝑓 . In order to characterize the set of precedence constraints that must be fulfilled by the set of admissible SWP schedules for 𝐺 𝑡 𝑠𝑑 𝑓 , we first need to define and formalize the dependency relations induced by every channel in 𝐺 𝑡 𝑠𝑑 𝑓 . For this purpose, let us consider the following notations. For each actor 𝑖 ∈ 𝑉 , 𝑘 𝑖 , 𝑞 𝑖 and 𝛿 𝑖 represent respectively the firing index, the granularity and the worst-case execution time to process a single firing of this actor. For any channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸, 𝑝 𝑒 , 𝑚 0 (𝑒) and 𝑐 𝑒 are respectively the production rate, the initial marking and the consumption rate of the channel 𝑒.

Dependency relations induced by channels

(𝑘 𝑖 , 𝑘 𝑗 ) ∈ ℕ 2 .

The channel 𝑒 induces a strict dependency relation from a firing ⟨𝑘 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 , 𝑗⟩ if and only if each of the following conditions hold:

• Condition 1: ⟨𝑘 𝑗 , 𝑗⟩ cannot be executed before the end of ⟨𝑘 𝑖 , 𝑖⟩.

• Condition 2: ⟨𝑘 𝑗 , 𝑗⟩ can be executed before the end of ⟨𝑘 𝑖 + 1, 𝑖⟩.

• Condition 3: ⟨𝑘 𝑗 -1, 𝑗⟩ can be executed before the end of ⟨𝑘 𝑖 , 𝑖⟩.

In order to formalize definition 4.1, we have established the following lemma.

𝑐 𝑒 > 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }.
Proof. Let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel and let (𝑘 𝑖 , 𝑘 𝑗 ) ∈ ℕ 2 . After the execution of firings ⟨𝑘 𝑖 , 𝑖⟩ and ⟨𝑘 𝑗 , 𝑗⟩, the number of tokens remaining on the channel 𝑒 is equal to 𝑚 0 (𝑒) + (𝑘 𝑖 + 1) • 𝑝 𝑒 -(𝑘 𝑗 + 1) • 𝑐 𝑒 . Using this characterization, we can formalize the conditions stated in definition 4.1.

• Condition 1 can be reformulated as follows: After the execution of the firing ⟨𝑘 𝑖 -1, 𝑖⟩, there are not enough tokens on the channel 𝑒 so that the firing ⟨𝑘 𝑗 , 𝑗⟩ may be executed.

By formalizing this assumption, we get the following inequality which ensures that if ⟨𝑘 𝑗 , 𝑗⟩ is executed just after ⟨𝑘 𝑖 -1, 𝑖⟩ and before the end of ⟨𝑘 𝑖 , 𝑖⟩, then, the number of tokens remaining on the channel 𝑒 is strictly lower to 0.

𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -(𝑘 𝑗 + 1) • 𝑐 𝑒 < 0 (4.1)
• Condition 2 can be reformulated as follows: After the execution of ⟨𝑘 𝑗 , 𝑗⟩ and ⟨𝑘 𝑖 + 1, 𝑖⟩, the number of tokens remaining on the channel 𝑒 is greater or equal to 0. By formalizing this assumption, we get the following inequality:

𝑚 0 (𝑒) + (𝑘 𝑖 + 1) • 𝑝 𝑒 -(𝑘 𝑗 + 1) • 𝑐 𝑒 ≥ 0 (4.2)
• Condition 3 can be reformulated as follows: After the execution of ⟨𝑘 𝑗 -1, 𝑗⟩ and ⟨𝑘 𝑖 , 𝑖⟩, the number of tokens remaining on the channel 𝑒 is greater of equal to 0. By formalizing this assumption we get the following inequality:

𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 ≥ 0 (4.3)
Combining equations (4.1), (4.2) and (4.3), we get:

𝑐 𝑒 > 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }.
Actually, lemma 4.1 is a necessary and sufficient condition that ensures the existence of a dependency relation between any couple of firings. A similar lemma has been established 42

𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 = ⌈ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 } -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒 ⌉ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 = ⌊ 𝑐 𝑒 -𝑔𝑐𝑑 𝑒 -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒 ⌋ such that 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 ,
𝑐 𝑒 > 𝑚 0 (𝑒) + (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 ) • 𝑝 𝑒 -(𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 ) • 𝑐 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 } which leads to: 𝑐 𝑒 > 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 + 𝑛 • 𝑞 𝑖 • 𝑝 𝑒 -𝑛 ′ • 𝑞 𝑗 • 𝑐 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }.

©2020 Philippe Glanon

Since 𝐺 𝑡 𝑠𝑑 𝑓 is consistent, according to equation (3.1) we can write 𝑞 𝑖 • 𝑝 𝑒 = 𝑞 𝑗 • 𝑐 𝑒 and thus, the inequality above becomes:

𝑐 𝑒 > 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 + (𝑛 -𝑛 ′ ) • 𝑞 𝑖 • 𝑝 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }
Now, as we assume that 𝑛 -𝑛 ′ = 𝑋 , we get the following inequality:

𝑐 𝑒 > 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 + 𝑋 • 𝑞 𝑖 • 𝑝 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }
Since 𝑐 𝑒 can be divided by 𝑔𝑐𝑑 𝑒 , the inequality above can be rewritten as:

𝑐 𝑒 -𝑔𝑐𝑑 𝑒 ≥ 𝑚 0 (𝑒) + 𝑘 𝑖 • 𝑝 𝑒 -𝑘 𝑗 • 𝑐 𝑒 + 𝑋 • 𝑞 𝑖 • 𝑝 𝑒 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 }
which is equivalent to:

𝑐 𝑒 -𝑔𝑐𝑑 𝑒 -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒 ≥ 𝑋 ≥ 𝑚𝑎𝑥 {0, 𝑐 𝑒 -𝑝 𝑒 } -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒
Since 𝑋 is an integer value, we can write:

⌊ 𝑐 𝑒 -𝑔𝑐𝑑 𝑒 -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒 ⌋ ≥ 𝑋 ≥ ⌈ 𝑚𝑎𝑥 {0,
𝑛 -𝑛 ′ = 𝑋 • 𝑥 + 𝑧 • 𝑞 𝑗 • 𝑐 𝑒 + 𝑋 • 𝑦 -𝑧 • 𝑞 𝑖 • 𝑝 𝑒 Since 𝐺 𝑡
𝑠𝑑 𝑓 is consistent, according to equation (3.1) we can write 𝑞 𝑖 • 𝑝 𝑒 = 𝑞 𝑗 • 𝑐 𝑒 and thus, the equality above can be simplified and rewritten as:

𝑛 -𝑛 ′ = (𝑥 + 𝑦) • 𝑋 44 ©2020 Philippe Glanon

A necessary and sufficient condition for admissibility

Maximum Throughput for Timed SDF graphs

In this section, we characterize the SWP schedules that achieve maximum throughput for timed SDF graphs. For this purpose, let us consider a consistent and live timed SDF graph 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿). Since the schedules that maximize throughput for 𝐺 𝑡 𝑠𝑑 𝑓 minimize implicitly the iteration period (refer to section 3.3), we can compute the SWP schedules 𝜎 that achieve maximum throughput for 𝐺 𝑡 𝑠𝑑 𝑓 with the following linear programming model.

(𝑃 1 )                      𝑚𝑖𝑛 𝜆 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝛿 𝑖 ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 (1) 𝜎 (𝑘 𝑖 , 𝑖) ∈ ℚ + ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ) (2) 𝜆 ∈ ℚ + * (3)
Constraint ( 1) is actually a set of precedence constraints that must be fulfilled by any admissible SWP schedule 𝜎 with period 𝜆 for 𝐺 𝑡 𝑠𝑑 𝑓 . These constraints are derived from theorem 4.1 which characterizes the set of admissible SWP schedules for timed SDF graphs. Constraints ( 2) and ( 3) are integrity constraints on the decisions variables of the model (𝑃 1 ). The number of variables in the model (𝑃 1 ) is given by 𝑉 𝑘 = 1+ ∑ ∀𝑖∈𝑉 𝑞 𝑖 and the number of constraints 𝐶 𝑘 is bounded on the upper side by ∑ ∀𝑒=(𝑖,𝑗)∈𝐸 𝑞 𝑖 • 𝑞 𝑗 , where 𝑞 𝑖 is the granularity of an actor 𝑖. Since the computation of 𝑉 𝑘 and 𝐶 𝑘 depends on the granularity of actors of 𝐺 𝑡 𝑠𝑑 𝑓 , the time and space complexity to solve the model (𝑃 1 ) depends on the size of the repetition vector 𝑞 of 𝐺 𝑡 𝑠𝑑 𝑓 and the size of each component of this vector.

For any timed SDF graph, the model (𝑃 1 ) can be instantiated and solved with a linear programming solver such as CPLEX 1 . Considering the timed SDF graph depicted in figure 3.1, the instantiation of (𝑃 1 ) gives the following system of equations:

                                                                                                     𝑚𝑖𝑛 𝜆 e=(A,A): 𝜎 (1, 𝐴) -𝜎 (0, 𝐴) ≥ 3 𝜎 (0, 𝐴) -𝜎 (1, 𝐴) ≥ -𝜆 + 3 e=(A,B): 𝜎 (0, 𝐵) -𝜎 (0, 𝐴) ≥ 3 𝜎 (0, 𝐵) -𝜎 (1, 𝐴) ≥ 3 e=(A,C): 𝜎 (0, 𝐶) -𝜎 (0, 𝐴) ≥ 3 𝜎 (1, 𝐶) -𝜎 (0, 𝐴) ≥ 3 𝜎 (2, 𝐶) -𝜎 (1, 𝐴) ≥ 3 𝜎 (3, 𝐶) -𝜎 (1, 𝐴) ≥ 𝜆 + 3 e=(B,D): 𝜎 (0, 𝐷) -𝜎 (0, 𝐵) ≥ 4 𝜎 (1, 𝐷) -𝜎 (0, 𝐵) ≥ 4 e=(C,D): 𝜎 (0, 𝐷) -𝜎 (0, 𝐶) ≥ 2 𝜎 (0, 𝐷) -𝜎 (1, 𝐶) ≥ 2 𝜎 (1, 𝐷) -𝜎 (2, 𝐶) ≥ 2 𝜎 (1, 𝐷) -𝜎 (3, 𝐶) ≥ 2 e=(D,D): 𝜎 (1, 𝐷) -𝜎 (0, 𝐷) ≥ 2 𝜎 (0, 𝐷) -𝜎 (1, 𝐷) ≥ -𝜆 + 2 e=(D,A): 𝜎 (1, 𝐴) -𝜎 (0, 𝐷) ≥ -𝜆 + 2 𝜎 (0, 𝐴) -𝜎 (1, 𝐷) ≥ -2𝜆 + 2 𝜎 (𝑘 𝑖 , 𝑖) ∈ ℚ + ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ) 𝜆 ∈ ℚ + *
The solution obtained with CPLEX for this system of equations is given by 𝜆 * = 9 and thus, the maximum throughput achievable by the SDF graph is given by 𝛽 * = 1 9

. Now, using the values of 𝜆 * and 𝜎 (𝑘 𝑖 , 𝑖) * , we can describe the SWP schedules that achieve maximum throughput for the SDF graph.

(𝑃 2 )                          𝑚𝑖𝑛 T 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝛿 𝑖 , ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 (1) T ≥ 𝜎 (𝑘 𝑖 , 𝑖) + 𝛿 𝑖 , ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ) (2) 𝜎 (𝑘 𝑖 , 𝑖) ∈ ℚ + ∀𝑖 ∈ 𝑉 ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ( 3
) 𝜆 ∈ ℚ + * (4)
Constraint (1) characterizes the set of precedence constraints that must be fulfilled by any admissible schedule of 𝐺 𝑡 𝑠𝑑 𝑓 . This constraint also ensures that the minimum latency induced by every channel of 𝐺 𝑡 𝑠𝑑 𝑓 between two firings is greater or equal to 0. Indeed, according to corollary 4.1, if a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 induces a dependency relation from a

𝑞 𝑖 • 𝑞 𝑗 + ∑ ∀𝑖∈𝑉 𝑞 𝑖 ,
where 𝑞 𝑖 is the granularity of an actor 𝑖.

For any timed SDF graph, the model (𝑃 2 ) can be instantiated and solved with CPLEX.

Like the linear programming model (𝑃 1 ), it is important to mention that the time and space complexity to solve (𝑃 2 ) for a timed SDF graph depends both on the size of the repetition vector of this graph and the size of the components of this vector. achievable by this schedule is suboptimal compared to the throughput

𝛽 * = 1 9
achievable by the schedule depicted in figure 3.7. This shows that the schedules that achieve minimum latency for a timed SDF graph do not necessarily achieve maximum throughput.

Conclusion

In this chapter, we have characterized admissible SWP schedules for timed SDF graphs and we have proposed two linear programming models (𝑃 1 ) and (𝑃 2 ) which enable respectively to compute the SWP schedules that achieve maximum throughput and minimum latency for timed SDF graphs. We will note that these models consider only the precedence constraints of timed SDF graphs and they do accommodate neither resource nor communication constraints. In the next chapter, we will consider both precedence, resource, and communication constraints to compute SWP schedule of SDF graphs on heterogeneous multiprocessor architectures.

©2020 Philippe Glanon

Introduction

In this chapter, we study the software pipelined (SWP) scheduling problem of SDF graphs on heterogeneous multiprocessor architectures (HMAs) under resource and communication constraints with the goal of optimizing throughput. The chapter is structured into two parts. In the first part, we present our integer linear programming (ILP) model for an exact resolution of the scheduling problem. In the second part, we present a decomposed SWP scheduling heuristic build upon the heuristic of Gasperoni and Schwielgelshohn, which provides approximated solutions for the scheduling problem.

An Integer Linear Programming Model

In this section, we present an ILP formulation for the problem described in section 3.

Cyclicity Constraints

In order to ensure that each firing of each actor is executed cyclically according to a period 𝜆, our ILP model incorporates the set of cyclicity constraints that must be fulfilled by any SWP schedule 𝜎. These constraints are expressed by equation (3.4).

Resource Constraints

When scheduling 𝐺 𝑠𝑑 𝑓 on 𝐺 ℎ𝑚𝑎 , we need to ensure that each firing of each actor is assigned exactly to one PU. In order to formulate these constraints, we define a 0 -1 integer variable 𝑤 𝑥,𝑘 𝑖 ,𝑖 such that:

𝑤 𝑥,𝑘 𝑖 ,𝑖 = { 1
if the firing ⟨𝑘 𝑖 , 𝑖⟩ has been assigned to the PU 𝑥. 0 otherwise.

©2020 Philippe Glanon

Using this variable, we formulate the following set of resource constraints which ensure that each firing of each actor is assigned to a single PU:

∑ ∀𝑥 ∈𝑅 𝑤 𝑥,𝑘 𝑖 ,𝑖 = 1, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ) (5.1)
Since 𝐺 𝑠𝑑 𝑓 consists of stateless actors whose firings may be executed in parallel and/or stateful actors whose firings may be pipelined, we need to ensure that the execution of independent firings of actors cannot overlap on a same PU. For this purpose, we formulate the following set of inequalities:

               𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 -𝜎 (𝑘 𝑗 , 𝑗) ≤ 𝑀 (1 -𝑤 𝑥,𝑘 𝑖 ,𝑖 • 𝑤 𝑥,𝑘 𝑗 ,𝑗 ) 𝑜𝑟 𝜎 (𝑘 𝑗 , 𝑗) + Δ 𝑥 𝑗 -𝜎 (𝑘 𝑖 , 𝑖) ≤ 𝑀 (1 -𝑤 𝑥,𝑘 𝑖 ,𝑖 • 𝑤 𝑥,𝑘 𝑗 ,𝑗 ) ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) (5.2)
Actually, equation (5.2) is a set of non-linear disjunctive constraints which assert that two firings assigned to the same PU cannot be executed at the same time on this PU.

In these constraints we use M, a big integer value such that the constraints hold only for the firings assigned to the same computing unit, i.e 𝑤 𝑥,𝑘 𝑖 ,𝑖 = 𝑤 𝑥,𝑘 𝑗 ,𝑗 = 1. The disjunctive constraints described by equation (5.2) could be linearized in two steps. First, we replace 𝑀 (1 -𝑤 𝑥,𝑘 𝑖 ,𝑖 • 𝑤 𝑥,𝑘 𝑗 ,𝑗 ) by 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 ) and then equation (5.2) becomes:

               𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 -𝜎 (𝑘 𝑗 , 𝑗) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 ) 𝑜𝑟 𝜎 (𝑘 𝑗 , 𝑗) + Δ 𝑥 𝑗 -𝜎 (𝑘 𝑖 , 𝑖) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 ) ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) (5.3)
Second, we introduce another 0 -1 integer variable 𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 such that:

𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 = { 1
if the firing ⟨𝑘 𝑖 , 𝑖⟩ is scheduled before the firing ⟨𝑘 𝑗 , 𝑗⟩. 0 otherwise. Now, using the variable 𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 the set of disjunctive constraints described by equation (5.3) could be linearized and rewritten as:

54 ©2020 Philippe Glanon 5.2. An Integer Linear Programming Model          𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 -𝜎 (𝑘 𝑗 , 𝑗) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 ) + 𝑀 (1 -𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ) 𝜎 (𝑘 𝑗 , 𝑗) + Δ 𝑥 𝑗 -𝜎 (𝑘 𝑖 , 𝑖) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 ) + 𝑀𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) (5.4)
Simplifying further, equation (5.4) becomes:

         𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 -𝜎 (𝑘 𝑗 , 𝑗) ≤ 𝑀 (3 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 -𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ) 𝜎 (𝑘 𝑗 , 𝑗) + Δ 𝑥 𝑗 -𝜎 (𝑘 𝑖 , 𝑖) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 + 𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ) ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) (5.5)
Equation (5.5) is actually a set of linear constraints that enforces a ILP solver to schedule the firings ⟨𝑘 𝑖 , 𝑖⟩ before ⟨𝑘 𝑗 , 𝑗⟩ when the both firings are assigned to the same PU. Otherwise, it enforces the firings ⟨𝑘 𝑗 , 𝑗⟩ to be scheduled before ⟨𝑘 𝑖 , 𝑖⟩ on the PU.

Communication and Precedence Constraints

In order to ensure that our ILP formulation can generate admissible SWP schedules, we should incorporate the precedence constraints induced by every channel of 𝐺 𝑠𝑑 𝑓 . By Theorem 4.1, a SWP pipelined schedule 𝜎 is said admissible for a timed SDF graph 𝐺 𝑡 𝑠𝑑 𝑓 , if and only if for every channel 𝑒 = (𝑖, 𝑗) of 𝐺 𝑡 𝑠𝑑 𝑓 , the following precedence constraints are fulfilled:

𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝛿 𝑖 ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 (5.6)
Actually, the constraints expressed by equation (5.6) were constructed for timed SDF graphs regardless of communication constraints of a HMA and by assuming that the worst case cost to execute a single firing of any actor is equal to 𝛿 𝑖 . However, regarding the description of 𝐺 ℎ𝑚𝑎 (refer to section 3.4), the execution cost of a single firing of every actor depends on the PU on which this firing is assigned. Moreover, whether a channel 𝑒 = (𝑖, 𝑗)

of 𝐺 𝑠𝑑 𝑓 induces a dependency relation between two firings ⟨𝑘 𝑖 , 𝑖⟩ and ⟨𝑘 𝑗 , 𝑗⟩, which are assigned respectively to a PU 𝑥 ∈ 𝑅 and a PU 𝑦 ∈ 𝑅 (with 𝑥 ≠ 𝑦), there exists a non-zero communication cost between these firings. In order to consider these different costs in our ILP formulation, we reformulate the precedence constraints described by equation (5.6) and we get the following set of precedence and communication constraints:

𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + ∑ ∀𝑥 ∈𝑅 Δ 𝑥𝑖 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 + ∑ ∀𝑥 ∈𝑅 ∑ ∀𝑦∈𝑅 Γ 𝑥𝑦 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 • 𝑤 𝑦,𝑘 𝑗 ,𝑗 , ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 (5.7) ©2020 Philippe Glanon
Actually, equation (5.7) is a set of non-linear constraints, each associated with a pair of dependent firings. These constraints could be linearized and rewritten as follows:

𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + Δ 𝑥𝑖 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 + Γ 𝑥𝑦 • (𝑤 𝑥,𝑘 𝑖 ,𝑖 + 𝑤 𝑦,𝑘 𝑗 ,𝑗 -1), ∀𝑥, 𝑦 ∈ 𝑅, ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 (5.8)
In order to justify the equivalence between the constraints described by equations (5.7) and

(

𝑢 = Δ 𝑥 * 𝑖 , 𝑣 = Γ 𝑥 * 𝑦 * = Γ 𝑥 * 𝑦 * (𝑤 𝑥 * ,𝑘 𝑖 ,𝑖 + 𝑤 𝑥 * ,𝑘 𝑗 ,𝑗 -1)
and thus, the constraints described by equations (5.7) and (5.8) can be rewritten as follows:

𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝑢 + 𝑣 (5.9)
which proves the equivalence between equations (5.7) and (5.8).

56

©2020 Philippe Glanon To summarize, our ILP model incorporates equations (3.4), (5.1), (5.5) and (5.8) as constraints and 𝜆 as objective function. A compact description of the model is given by:

An Integer Linear Programming Model

(𝑃 3 )                                                          𝑚𝑖𝑛 𝜆 𝜎 (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖) = 𝜎 (𝑘 𝑖 , 𝑖) + 𝑛 × 𝜆, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑛 ∈ ℕ. (3.4) ∑ ∀𝑥 ∈𝑅 𝑤 𝑥,𝑘 𝑖 ,𝑖 = 1, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ).
(5.1)

𝜎 (𝑘 𝑖 , 𝑖) + Δ 𝑥𝑖 -𝜎 (𝑘 𝑗 , 𝑗) ≤ 𝑀 (3 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 -𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ), ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ). (5.5.1) 𝜎 (𝑘 𝑗 , 𝑗) + Δ 𝑥 𝑗 -𝜎 (𝑘 𝑖 , 𝑖) ≤ 𝑀 (2 -𝑤 𝑥,𝑘 𝑖 ,𝑖 -𝑤 𝑥,𝑘 𝑗 ,𝑗 + 𝑑 𝑘 𝑖 ,𝑖,𝑘 𝑗 ,𝑗 ), ∀𝑥 ∈ 𝑅, ∀𝑖, 𝑗 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ). (5.5.2) 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + Δ 𝑥𝑖 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 + Γ 𝑥𝑦 • (𝑤 𝑥,𝑘 𝑖 ,𝑖 + 𝑤 𝑦,𝑘 𝑗 ,𝑗 -1), ∀𝑥, 𝑦 ∈ 𝑅, ∀𝑒 = (𝑖, 𝑗) ∈ 𝐸, ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 .
(5.8)

𝑤 𝑥,𝑘 𝑖 ,𝑖 ∈ {0, 1}, ∀𝑥 ∈ 𝑅, ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ). (𝐼 1 ) 𝜎 (𝑘 𝑖 , 𝑖) ∈ ℚ + ∀𝑖 ∈ 𝑉 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ). (𝐼 2 ) 𝜆 ∈ ℚ + * . ( 𝐼 3 )
where constraints (𝐼 1 ), (𝐼 2 ) and (𝐼 3 ) are integrity constraints on the decision variables of the model (𝑃 3 ). For any SDF graph 𝐺 𝑠𝑑 𝑓 and any architecture 𝐺 ℎ𝑚𝑎 , the ILP model (𝑃 3 ) can be instantiated and solved with the ILP solver of CPLEX. Let us consider the non-timed SDF graph shown in figure 2.6b and the architecture on which this graph is intended to be deployed (figure 3.8). An optimal scheduling solution obtained with our ILP formulation for this graph is depicted in figure 5.1, where 𝜆 * = 6 and:

𝜎 (0, 𝐴) * = 0 𝜎 (0, 𝐶) * = 2 𝜎 (3, 𝐶) * = 4 𝜎 (1, 𝐴) * = 1 𝜎 (1, 𝐶) * = 2 𝜎 (0, 𝐷) * = 5 𝜎 (0, 𝐵) * = 3 𝜎 (2, 𝐶) * = 3 𝜎 (1, 𝐷) * = 7 ©2020 Philippe Glanon
In this schedule, one can note that each firing of each actor is executed cyclically according to the period 𝜆 * and data parallelism is exploited since some firings of the stateless actor 𝐶 can execute out of order on different PUs. Although the ILP solver of CPLEX can find a schedule that optimizes the value of 𝜆, the time to find this schedule can be exponential for some instances of SDF graphs and architecture models. Therefore, we should design approximated techniques to solve efficiently the problem. For this purpose we focus on decomposed SWP scheduling approaches. Decomposed SWP scheduling is a technique which consists in separating the SWP scheduling problem of a dataflow graph into two sub-problems, the first being to satisfy the precedence and cyclicity constraints of (𝑃 3 ) the graph and the second being to satisfy the resource constraints.

Decomposed Software Pipelined Scheduling

In this section, we present a heuristic denoted by heterogeneous cyclic scheduling (HCS)

that is designed to solve the scheduling problem described by the ILP model (𝑃 3 ). HCS is a decomposed SWP scheduling heuristic based upon the heuristic of Gasperoni and Schwielgelshohn [START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF], one of the first decomposed SWP scheduling heuristic for executing cyclic dataflow graphs under resource constraints. In the first subsection, we briefly describe the heuristic of Gasperoni and Schwielgelshohn that we denote by GS, and in the second subsection, we present in detail our heuristic.

GS Heuristic

Description. Let 𝐺 𝑡 ℎ𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑀 0 , 𝛿) be a timed HSDF graph -i.e. a timed SDF graph, where the production and consumption rates of actors are all equal to 1 -and let us consider a multiprocessor architecture with 𝑝 identical PUs for 𝐺 𝑡 ℎ𝑠𝑑 𝑓 , where 𝑝 is a finite number (𝑝 ≠ ∞) and the inter-PU communication costs are negligible. The main idea of GS is the following. Assume that we have an optimal SWP schedule 𝜎 ∞ of period 𝜆 ∞ of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 for unlimited resources -i.e. a SWP schedule with 𝑝 = ∞ -and that we want to deduce a SWP schedule 𝜎 of period 𝜆 of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 under resource constraints -i.e. a SWP schedule with 𝑝 ≠ ∞ -. A way of building 𝜎 is to keep the structure of 𝜎 ∞ and to reorganize the execution of actors within this latter schedule in such a way as to find the period 𝜆 that meets both resource and precedence constraints. In order to achieve this, GS proceeds in four steps. Each of these steps is described by Algorithm 2: 58 ©2020 Philippe Glanon

foreach channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 𝑎𝑑𝑔 do if (𝜎 ∞ (𝑛, 𝑗) mod 𝜆 ∞ < 𝜎 ∞ (𝑛, 𝑖) mod 𝜆 ∞ + 𝛿 𝑖 ) then delete 𝑒 from 𝐸 𝑎𝑑𝑔 ; end end Set 𝐺 𝑎𝑑𝑔 = (𝑉 , 𝐸 𝑎𝑑𝑔 , 𝛿); //
foreach 𝑖 ∈ 𝑉 do for 𝑛 ≤ 𝑇 do 𝜎 (𝑛, 𝑖) = 𝜎 𝑎 (𝑖) + ( 𝑛 + ⌊ 𝜎 ∞ (𝑛, 𝑖) 𝜆 ∞ ⌋ ) • 𝜆 end end return 𝜎; • Step 1. A SWP schedule 𝜎 ∞ of period 𝜆 ∞ is built for 𝐺 𝑡 ℎ𝑠𝑑 𝑓
with an infinite number of resources. Since this schedule is not constrained by the number of resources, it can be constructed in polynomial-time using an algorithmic approach [START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF] or by instantiating and solving the linear programming model (𝑃 1 ).

• Step 2. The dependency information described by the repetitive patterns of the schedule 𝜎 ∞ are used to construct an acyclic dependency graph 𝐺 𝑎𝑑𝑔 = (𝑉 , 𝐸 𝑎𝑑𝑔 , 𝛿),

©2020 Philippe Glanon

where 𝐸 𝑎𝑑𝑔 is a set that contains every channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸, except the channels for which the following inequality is checked:

𝜎 ∞ (𝑛, 𝑖) mod 𝜆 ∞ + 𝛿 𝑖 > 𝜎 ∞ (𝑛, 𝑗) mod 𝜆 ∞ , ∀𝑛 ∈ ℕ (5.10)
where 𝜎 ∞ (𝑛, 𝑗) mod 𝜆 ∞ and 𝜎 ∞ (𝑛, 𝑗) mod 𝜆 ∞ respectively are the times at which nodes 𝑖 and node 𝑗 start for the first time in the schedule 𝜎 ∞ . Actually, the inequality above holds only for loop-carried dependency channels (i.e a channel with tokens) between the firings of any pair of actors. Consequently, every channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 𝑎𝑑𝑔 is a direct dependency channel (i.e a channel without tokens).

• Step 3. A list-scheduling of 𝐺 𝑎𝑑𝑔 is performed under resource constraints to determine a schedule 𝜎 𝑎 of length 𝜆.

• Step 4. A valid SWP schedule 𝜎 of period 𝜆 is calculated with the following approximation equation, which ensures the respect of cyclicity constraints for every actor of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 while satisfying both resource and precedence constraints.

𝜎 (𝑛, 𝑖) = 𝜎 𝑎 (𝑖) + ( 𝑛 + ⌊ 𝜎 ∞ (𝑛, 𝑖) 𝜆 ∞ ⌋ ) • 𝜆, ∀𝑖 ∈ 𝑉 , ∀𝑛 ∈ ℕ (5.11)
The correctness of the heuristic 𝐺𝑆 can be found in [START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF]. To better explain the heuristic 𝐺𝑆, we illustrate the different steps described above, through the following example.

Example. Let 𝐺 𝑡 ℎ𝑠𝑑 𝑓 be the timed HSDF graph depicted in figure 5.2a and let us assume that we want to schedule this graph on a multiprocessor architecture with two identical PUs (i.e. 𝑝 = 2). Applying the first step of algorithm 2, an optimal SWP schedule 𝜎 ∞ of period 𝜆 ∞ can be calculated for 𝐺 𝑡 ℎ𝑠𝑑 𝑓 by instantiating and solving the linear programming model (𝑃 1 ) with CPLEX. Figure 5.2b shows a schedule 𝜎 ∞ for 𝐺 𝑡 ℎ𝑠𝑑 𝑓 , where 𝜆 ∞ = 5. Based on this schedule 𝜎 ∞ , one can derive in step 2, an acyclic dependency graph 𝐺 𝑎𝑑𝑔 , which contains only the direct dependency channels of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . Actually, the graph 𝐺 𝑎𝑑𝑔 is obtained by deleting all the dependency channels of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 for which the condition stated in equation 5.10 holds. For instance, let us consider the channel (𝑐, 𝑎) within the graph 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . In each iteration of the schedule 𝜎 ∞ , one can note that the execution of 𝑛 𝑡ℎ firing of actor 𝑎 starts before the execution of the 𝑛 𝑡ℎ firing of actor 𝑐 finishes, i.e 𝜎 ∞ (𝑛, 𝑐) mod 𝜆 ∞ + 𝛿 𝑐 > 𝜎 ∞ (𝑛, 𝑎) mod 𝜆 ∞ . This means that the dependency relation from 𝑎 to 𝑐 is not a direct dependency but rather a loop-carried dependency; thus, the channel (c,a) can be removed from the set of channels of 𝐺 𝑎𝑑𝑔 . Figure 5.2c depicts the acyclic graph 𝐺 𝑎𝑑𝑔 derived from 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . Now, in the third step, the graph 𝐺 𝑎𝑑𝑔 is scheduled under resource constraints (p=2) by means of a list scheduler 𝜎 𝑎 that executes as soon as possible the actors of 𝐺 𝑎𝑑𝑔 on the 𝑝 identical resources. Figure 5.2d depicts this schedule whose length is 𝜆 = 6 for our example. Finally, in the fourth step, a SWP schedule 𝜎 is calculated under resource constraints using the approximation stated by equation . For our example, this schedule is depicted in figure 5.2e. As it can be noted, the period of the schedule 𝜎 is given by length of the schedule 𝜎 𝑎 . Hence, the performance of GS depends on that of the schedule 𝜎 𝑎 .

Theoretical performance. Gasperoni and Schwielgelshohn have given a theoretical upper bound to the iteration period 𝜆 of the schedule returned by algorithm 2. Let 𝜆 * be the period of an optimal SWP schedule 𝜎 of 𝐺 𝑠𝑑 𝑓 for 𝑝 identical PUs. The upper bound of 𝜆 ©2020 Philippe Glanon is characterized by the following inequality:

𝑝 • 𝜆 ≤ 𝑝 • 𝜆 * + (𝑝 -1) • Φ
where Φ is the length of the longest path in 𝐺 𝑎𝑑𝑔 . Owing to channel deletion strategy, Φ ≤ 𝜆 ∞ + 𝛿 𝑚𝑎𝑥 -1 (see lemma 1 in [START_REF] Gasperoni | Generating Close to Optimum Loop-Schedules on Parallel Processors[END_REF]). Thus, the inequality above can be rewritten as:

𝑝 • 𝜆 ≤ 𝑝 • 𝜆 * + (𝑝 -1)(𝜆 ∞ + 𝛿 𝑚𝑎𝑥 -1)
which leads to:

𝜆 𝜆 * ≤ 2 - 1 𝑝 + ( 𝑝 -1 𝑝 ) ( 𝜆 ∞ + 𝛿 𝑚𝑎𝑥 -1 𝜆 * )

HCS Heuristic

Let 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑀 0 , 𝑃, 𝐶) be a consistent, live and non-timed SDF graph and let 𝐺 ℎ𝑚𝑎 = (𝑅, Δ, Γ) be the architecture on which 𝐺 𝑠𝑑 𝑓 is intended to be deployed. The heuristic HCS shares the same idea with the heuristic GS. However, the main difference between these heuristics is that HCS accommodates both the resource and communication constraints of heterogeneous multiprocessor architectures to schedule SDF graphs. Before presenting HCS, we first convert 𝐺 𝑠𝑑 𝑓 into an equivalent homogeneous SDF graph 𝐺 ℎ𝑠𝑑 𝑓 = (𝑉 ′ , 𝐸 ′ , 𝑀 ′ 0 ). The construction of 𝐺 ℎ𝑠𝑑 𝑓 = (𝑉 ′ , 𝐸 ′ , 𝑀 ′ 0 ) is performed using Algorithm 1, which generates for any consistent SDF graph, an equivalent homogeneous representation with a minimal number of channels. Actually, 𝑉 ′ is a set of nodes 𝑖 𝑘 where 𝑖 ∈ 𝑉 and 𝑘 ∈ [1, 𝑞 𝑖 ], 𝑞 𝑖 being the granularity of actor 𝑖. 𝐸 ′ is the set of arcs between these firings and 𝑀 ′ 0 is a function, that associates with each arc 𝑒 ′ = (𝑖 𝑘 , 𝑗 𝑘 ′ ) ∈ 𝐸 ′ , an initial number of tokens. Previously presented, figure 3.2 depicts the equivalent homogeneous graph obtained with Algorithm 1 for the non-timed SDF graph of our running example (refer to figure 2.6b).

HCS takes as inputs 𝐺 𝑠𝑑 𝑓 , 𝐺 ℎ𝑠𝑑 𝑓 and 𝐺 ℎ𝑚𝑎 , and it outputs a SWP schedule of 𝐺 ℎ𝑠𝑑 𝑓 on 𝐺 ℎ𝑚𝑎 . The heuristic is illustrated by Algorithm 3. Actually, HCS consists of four steps. Each of these steps are described below.

where 𝑝𝑟𝑒𝑑 (𝑖 𝑘 ) is the set of direct predecessors of 𝑖 𝑘 in the graph 𝐺 𝑎𝑑𝑔 , 𝐴𝐹𝑇 ( 𝑗 𝑘 ′ ) is the actual finishing time of the node 𝑗 𝑘 ′ and 𝑝𝑟𝑜𝑐 ( 𝑗 𝑘 ′ ) is the processing resource on which the node 𝑗 𝑘 ′ is mapped to. For nodes without predecessors, 𝑟𝑒𝑎𝑑𝑦 (𝑥, 𝑖 𝑘 ) is set to zero.

• Step 4. A valid SWP schedule 𝜎 of period 𝜆 for 𝐺 ℎ𝑠𝑑 𝑓 is derived under the resource and communication constraints of 𝐺 ℎ𝑚𝑎 . In order to derive this schedule, we first calculate the period 𝜆 with the information provided by the schedule 𝜎 𝑎 and the communication matrix Γ, where 𝜆 is the minimum time required to process both the computations and communications of every actor in a single iteration of 𝐺 ℎ𝑠𝑑 𝑓 . Using this period we derive the schedule 𝜎 with the following cyclicity equation:

𝜎 (𝑛, 𝑖 𝑘 ) = 𝜎 𝑎 (𝑖 𝑘 ) + 𝑛 • 𝜆.
(5.16) By equation (5.16), this inequality can be rewritten as:

Correctness of HCS

𝜎 𝑎 ( 𝑗 𝑘 ′ ) + (𝑛 + 𝑚 0 (𝑒 ′ )) • 𝜆 -𝜎 𝑎 (𝑖 𝑘 ) -𝑛 • 𝜆 ≥ Δ 𝑥 * 𝑖 + Γ 𝑥 * 𝑦 * .
Simplifying further and reordering, we get:

𝜎 𝑎 ( 𝑗 𝑘 ′ ) ≥ 𝜎 𝑎 (𝑖 𝑘 ) + Δ 𝑥 * 𝑖 + Γ 𝑥 * 𝑦 * -𝑚 0 (𝑒 ′ ) • 𝜆.
This implies that, the schedule 𝜎 fulfils the precedence and communication constraints induced by loop-carried dependency channels of 𝐺 ℎ𝑠𝑑 𝑓 and the proof is achieved.

Illustration of HCS

In order to illustrate the different steps of the heuristic HCS, let 𝐺 𝑠𝑑 𝑓 , 𝐺 ℎ𝑠𝑑 𝑓 and 𝐺 ℎ𝑚𝑎 respectively be the non-timed SDF graph shown in figure 2.6b, the equivalent HSDF graph of this graph (refer to figure 3.2) and the multiprocessor architecture of our running example (refer to figure 3.8).

•

Step 1: 𝐺 ℎ𝑠𝑑 𝑓 is set into a timed HSDF graph 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . Figure 5.3a depicts the graph 𝐺 𝑡 ℎ𝑠𝑑 𝑓 , where for any value of 𝑘, the time budgets of nodes are given by 𝛿 𝐴 𝑘 =7, 𝛿 𝐵 𝑘 =5, 𝛿 𝐶 𝑘 =8, and 𝛿 𝐷 𝑘 =5. Considering these time budgets, an optimal SWP schedule 𝜎 ∞ of period 𝜆∞ is calculated for 𝐺 𝑡 ℎ𝑠𝑑 𝑓 without considering resource and communication constraints. Figure 5.3c presents the schedule 𝜎 ∞ of period 𝜆 ∞ = 17 for our running example. This schedule is obtained by instantiating and solving the linear programming model (𝑃 2 ).

• Step 2: an acyclic dependency graph 𝐺 𝑎𝑑𝑔 is generated by deleting all the loopcarried dependency channels in 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . Figure 5.3b illustrates this acyclic dependency graph for our running example. 25 (d) List schedule of 𝐺 𝑎𝑑𝑔 under resource and communication constraints In order to validate the heuristic HCS, we need to study and to characterize the performance achievable by the heuristic HCS according to the performance achievable by an ILP solver for different instances of SDF graphs and multiprocessor architectures. In the next chapter, we will present and discuss in detail the performance results obtained.

©2020 Philippe Glanon

A 1 C 1 B 1 C 2 A 2 D 2 D 1 A 1 C 3 C 4
P 1 P 2 P 3 A 1 D 2 Iteration 1 C 2 B 1 C 1 C 3 A 2 C 4 C 2 A 1 B 1 C 1 D 1 A 2 C 4 D 2 A 1 C 2 B 1 C 1 A 2 C 3 0 1 2 3

Conclusion

In this chapter, we have presented an ILP model and a heuristic denoted by HCS for the scheduling and throughput optimization problem of SDF graphs on heterogeneous multiprocessor architectures under resource and communication constraints. The next chapter will be dedicated to the performance evaluation and discussion.

©2020 Philippe Glanon

Introduction

In this chapter, we present the performance results for the heuristic HCS. Performance evaluation have been achieved using synthetic benchmarks and real-world application benchmarks. All experiments were performed on a PC Intel(R) core TM i7-7600U running at 2.80GHz with 16GB of RAM. In order to calculate an exact scheduling solution for a given benchmark, we use the ILP solver of CPLEX 12.5.0 and OPL script language to instantiate and solve our ILP formulation for the benchmark.

Evaluation Metrics

Our experiments are based on the following performance metrics:

• Solving Time: the time to find a scheduling solution.

• Bound Gap (BG): this metric is the average ratio between the scheduling solutions obtained with HCS and the ILP solver of CPLEX. It enables to evaluate how far the throughput of schedules returned by the heuristic HCS is from the throughput of schedules generated with the ILP solver. The value of BG is given by:

𝐵𝐺 = 𝜆 ℎ𝑐𝑠 -𝜆 𝑐𝑝𝑙𝑒𝑥 𝜆 𝑐𝑝𝑙𝑒𝑥 × 100 (6.1)
where 𝜆 ℎ𝑐𝑠 and 𝜆 𝑐𝑝𝑙𝑒𝑥 are respectively the periods of scheduling solutions obtained with HCS and CPLEX. A low percentage of BG means that the scheduling solution obtained with HCS is very close to the solution obtained with the ILP solver.

Conversely, a high percentage of BG implies that the solution obtained with HCS is suboptimal compared to that obtained with the ILP solver.

• Speedup. Speedup is defined as the sequential execution time of a SDFG divided by the latency (T ) of this graph, where T is the amount of time required to execute all the firings of every actor in each stable iteration of the graph. To calculate the sequential execution time of a SDFG, we assign the firings of every actor to the single PU that minimizes the cumulative computation costs and we characterize the speedup by the following equation:

𝑆𝑝𝑒𝑒𝑑𝑢𝑝 = min 𝑥 ∈𝑅 [ ∑ 𝑖 ∈𝑉 𝑞 𝑖 × Δ 𝑥𝑖 ] T (6.2) ©2020 Philippe Glanon

Experiments with Synthetic Benchmarks

Benchmarks Generation

In order to achieve a broad range of experiments, we have generated synthetic SDF graphs using Turbine 1 , a multi-functional tool presented in [START_REF] Bodin | Fast and efficient dataflow graph generation[END_REF], that randomly generates consistent, live, cyclic and acyclic dataflow graphs. General settings for a SDFG shape are the number of actors (NA) and the outgoing degree (outDeg) of an actor. In order to generate heterogeneous computing architecture for each SDF graph, we have adapted Turbine

( 1-𝐻 𝐹𝑆 2 ) ≤ Δ 𝑥𝑖 ≤ Δ𝑖 × ( 1+ 𝐻 𝐹𝑆 2 ) .
Replacing 𝑀𝐶𝐶, 𝐻 𝐹𝑆, Δ 𝑥𝑖 , Δ𝑖 respectively by MIPC, HFC, Γ 𝑥𝑦 , Γ𝑥𝑦 in this distribution, we generate the communication cost matrix. By definition, we set Γ 𝑥𝑦 = Γ 𝑦𝑥 for each pair (𝑥, 𝑦)

of PUs and whether 𝑥 is equal to 𝑦, we set the value of Γ 𝑥𝑦 to 0.

The following sets were considered for the experiments: NA={10, 20, 30, 40, 50,

Performance Results

Time complexity. In order to characterize the time complexity of the heuristic HCS, we compared the solving times of the ILP solver with the solving times of the heuristic. We have limited the running time of CPLEX to 8 hours. Figure 6.2 shows the results obtained. In figure 6.2a, it can be observed that the average speedup of all the benchmarks increases as when as the values of NP get increased.

Conversely, in figure 6.2b and figure 6.2c we respectively observed that, the speedup of the heuristic gradually decreases when the values of HFS and HFC are increased but it is still greater to 1. This means that the speedup of the heuristic get improved when the number of processing resources get greater. However, whether these resources have a high variability in computation and communication costs of actors, the speedup of the heuristic may decrease but will still be greater to 1. The interpretation of these results is that, if we take a higher risk to increase the value of HFS and HFC, we will certainly loose task, data or pipeline parallelism but, there is still a guarantee that the latency of scheduling solutions returned by the heuristic could not be worse than the sequential execution time of the application graphs.

74

©2020 Philippe Glanon

Experiments with StreamIt Benchmarks

In addition to experiments performed with the synthetic benchmarks, we have also performed experiments with real-world applications to validate the performance of HCS.

StreamIt Benchmarks

Experiments were performed with the application benchmarks of StreamIt [START_REF] Thies | StreamIt: A language for streaming applications[END_REF]. These benchmarks are streaming applications that embed the common properties (data, task and pipeline parallelisms) of loop-intensive applications. Table 6.2 gives a brief description of the chosen benchmarks. A detailed description of each of these benchmarks is given in [START_REF] Thies | StreamIt: A language for streaming applications[END_REF]. We set the number of stateful actors for each application benchmark to approximately 10% of the total number of actors. In order to generate asymmetric computation and communication costs for the actors of each benchmark, we have adapted the StreamIt compiler with our architecture generation function previously described in section 5.3.1 and we consider the same values for the parameters of this function. For each benchmark and each architecture configuration, we ran both the heuristic and the ILP solver. In this experiment, we have also limited the running time of the ILP solver to 8 hours.

Performance Results

Time complexity. Table . 6.3 plots the results of average solving times of the heuristic HCS and the ILP solver of CPLEX. On one hand, when the number of processing resources (i.e. NP) is lower or equal to 8 the ILP solver is able to find a scheduling solution for all the streamIt benchmarks. However, on the other hand, when the number of processor is equal to 16, the ILP fails to find a scheduling solution for all the benchmark except for "fft ". Conversely, the scalability of the heuristic HCS find a solution for any number of processor and in some cases the heuristic is approximately 355 × faster than the ILP solver. These results are similar to the those observed with the synthetic application graphs and they validate the performance of the heuristic.

©2020 Philippe Glanon

Conclusion

In this chapter, we presented the performance of the ILP formulation and the heuristic HCS for the software pipelined schedule of SDF graphs on heterogeneous multiprocessor architectures under resource and communication constraints. Experiments were performed both with synthetic application graphs and application benchmarks of StreamIt. Experimental results show that the heuristic performs better for multiprocessor architectures with large number of processing resources and more is the number of processing resources on a given architecture, better is the performance of the heuristic. In terms of throughput achievement, the heuristic was able to generate scheduling solutions with an average gap ranging from 25% to 42%, which means that in the average case, the scheduling solutions obtained with the ILP solver of CPLEX is close to the optimal solutions in the range of 68% to 75%. For all the benchmarks and multiprocessor architectures considered, the speedup of heuristic vary in the range of 1 to 1.9. Although the heterogeneity degree of processing resources may have an effect of decreasing the speedup of the heuristic, there is a guarantee that the latency of scheduling solutions returned by the heuristic could not be worse than the sequential execution time of application graphs.

Conclusion

Cyber-physical systems (CPSs) are increasingly implemented in several application fields to address many technical challenges. These systems are composed by a set of loopintensive applications and heterogeneous multiprocessor architectures with a fixed number of processing resources, which are connected through different networks media.

A key activity in the design stage of CPSs is the deployment of loop-intensive applications on the heterogeneous multiprocessor architectures. The goal of this design activity is to predict the timing behaviour of applications and to provide performance guarantees at design stage. For this purpose, formal models of computation that deal with time, concurrency and parallelism are required to generate static order schedules for the applications while ensuring highest performance under the resource and communication constraints of architectures. In order to achieve this need, we have used synchronous dataflow (SDF) model of computation in this thesis and we have design exact and approximated software pipelined (SWP) scheduling techniques to execute these models under the resources and communication constraints of heterogeneous multiprocessor architectures. Our scheduling techniques are based on a set of provable mathematical theories and they exploit efficiently the parallelism embedded in the SDF models while providing performance guarantees in terms of throughput and latency.

In chapter 4, we have established a set of lemmas and theorems to characterize the admissible SWP schedules for timed SDF graphs. Using the established theorems, we have proposed linear programming models to find the admissible SWP schedules that achieve optimal throughput/latency for timed SDF graphs. In chapter 5, we have shown that the SWP schedules that achieve optimal throughput for a SDF graph under the resource and communication constraints of a heterogeneous multiprocessor architecture can be characterized and calculated with an integer linear programming (ILP) model. The proposed ILP model explore different levels of parallelism (task, data and pipeline) in SDF graphs while scheduling these graphs. In this chapter, we have also proposed a decomposed software pipelining heuristic that generates approximated SWP scheduling solutions for SDF graphs under resource and communication constraints. Thanks to experiments performed with synthetic and application benchmarks, our ILP model and heuristic are validated in chapter 6. To the best of our knowledge this thesis is the first that tackles the SWP scheduling of SDF graphs under the resources and communication constraints of heterogeneous multiprocessor architectures.

©2020 Philippe Glanon

Open Challenges

The theoretical foundations put forward in this thesis provides a basis for future research directions. In this section, we present three interesting challenges that could be investigated to improve and extend the works achieved in this thesis.

List scheduling heuristics for throughput improvement

Thanks to the experimental results presented in chapter 6, we have shown that the scheduling solutions obtained with the heuristic HCS achieve a throughput gap bounded at 50%

to the throughput achievable by the scheduling solutions obtained with our ILP formulation. In order to reduce this throughput gap, we need to investigate new list-scheduling algorithms that can improve the length of the schedule generated by algorithm 4. Since the period (implicitly the throughput) of SWP scheduling solutions obtained with the heuristic HCS depends on the length of schedules returned by algorithm 4, an improvement of scheduling solutions obtained with this algorithm will obviously improve the throughput of SWP scheduling solutions obtained with the heuristic HCS.

Scheduling under storage capacity

Apart from resource and communication constraints, the storage capacity of communication links in CPS architectures can be bounded. Therefore, the scheduling strategy developed in this thesis has to assign not only actors to processing units but also FIFO channels to the communication links while ensuring that the storage capacity is not overflowed.

This new constraint can reduce the searching-space for scheduling solutions that achieve optimal throughput/latency and increase the time complexity to find a solution. In order to overcome this problem, future research works should investigate time-efficient heuristics that deal both with storage, resource and communication constraints while providing good performance guarantees.

Real-time scheduling

The major drawback of static schedules (and SWP schedules in particular) is their inflexibility and difficult maintainability. Hence, to execute a SDF graph on a heterogeneous architecture, real-time scheduling policies should be investigated. Unlike in SWP schedules, each actor in a real-time schedule is mapped to a periodic real-time task; therefore, the firing of a given actor is strictly periodic (as opposite to SWP schedule). One advan-80 ©2020 Philippe Glanon 7.2. Open Challenges tage of this scheduling approach is that there exist a set of provable mathematical theories (such as rate-monotonic, fixed-priority scheduling, earliest-deadline first, etc) that can be used to decide whether or not a dataflow specification can be scheduled on a given architecture. Using real-time scheduling policies to implement dataflow graphs under resource and communication constraints has been subject of only few works. Investigating this research direction can be very helpful to improve the works achieved in this thesis.

©2020 Philippe Glanon

Title: Deployment of loop-intensive applications on heterogeneous multiprocessor architectures Keywords: cyber-physical systems, multiprocessor scheduling, cyclic scheduling, static dataow graphs, heterogeneous architectures, software pipelining, maximum throughput, Abstract: Cyber-physical systems (CPSs) are distributed computing-intensive systems, that integrate a wide range of software applications and heterogeneous processing resources, each interacting with the other ones through dierent communication resources to process a large volume of data sensed from physical, chemical or biological processes. An essential issue in the design stage of these systems is to predict the timing behaviour of software applications and to provide performance guarantee to these applications. In order tackle this issue, ecient static scheduling strategies are required to deploy the computations of software applications on the processing architectures. These scheduling strategies should deal with several constraints, which include the loop-carried dependency constraints between the computational programs as well as the resource and communication constraints of processing architectures intended to execute these programs. Actually, loops being one of the most time-critical parts of many computing-intensive applications, the optimal timing behavior and performance of applications depends on the optimal schedule of loops structures enclosed in the computational programs. Therefore, to provide performance guarantee for the applications, the scheduling strategies should eciently explore and exploit the parallelism embedded in the repetitive execution patterns of loops while ensuring the respect of resource and communications constraints of the processing architectures of CPSs. Scheduling a loop under resource and communication constraints is a complex problem. To solve it eciently, heuristics are obviously necessary. However, to design ecient heuristics, it is important to characterize the set of optimal solutions for the scheduling problem. An optimal solution for a scheduling problem is a schedule that achieve an optimal performance goal. In this thesis, we tackle the study of resource-constrained and communication-constrained scheduling of loopintensive applications on heterogeneous multiprocessor architectures with the goal of optimizing throughput performance for the applications. In order to characterize the set of optimal scheduling solutions and to design ecient scheduling heuristics, we use synchronous dataow (SDF) model of computation to describe the loop structures specied in the computational programs of software applications and we design software pipelined scheduling strategies based on the structural and mathematical properties of the SDF model.

6b. . . 20 3. 1 2 1. 2 4 1. 3 5 1 1 . 1 .

 2012243511 An example of timed SDF graph . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Equivalent HSDF graph for the SDF graph shown in figure 2.6b. The notation 𝑥 𝑦 in the nodes denotes the 𝑦 𝑡ℎ firing of a actor 𝑥, where 𝑦 ∈ [1, 𝑞 𝑥 ], 𝑞 𝑥 being the granularity of the actor 𝑥. . . . . . . . . . . . . . . . . . . . . 27 3.3 Symbolic execution trace of the SDF graph of Fig. 2.6b. Solid arcs are intra-iteration dependencies, dashed arcs are inter-iteration dependencies and the notation ⟨𝑛, 𝑘 𝑖 , 𝑖⟩ stands for the completion of the 𝑘 𝑡ℎ 𝑖 firing of an actor 𝑖 in the 𝑛 𝑡ℎ iteration of the SDF graph, where 𝑛 ∈ ℕ, 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑞 𝑖 being the granularity of the actor 𝑖. . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Normalized representation of the SDF graph depicted in figure 2.6b . . . . 28 3.5 Counter example showing that theorem 3.2 is not a necessary condition for liveness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.6 A self-timed schedule of the timed SDF graph depicted in figure 3.1. . . . 30 3.7 A SWP Schedule for the timed SDF graph depicted in figure 3.1. . . . . . 32 3.8 An example of architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1 A SWP Schedule of period 𝜆 = 10 and latency T * = 14 for the timed SDF graph depicted in figure 3.1. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 xi LIST OF FIGURES 5.1 An optimal scheduling solution obtained for the non-timed SDF graph and the architecture of our running example. . . . . . . . . . . . . . . . . . . . 5.2 An illustration example for the Heuristic GS (algorithm 2). . . . . . . . . . 5.3 Illustration of the Heuristic HCS. . . . . . . . . . . . . . . . . . . . . . . . 6.1 Results of BG for synthetic Benchmarks . . . . . . . . . . . . . . . . . . . 6.2 Results of average Speedup for synthetic Benchmarks . . . . . . . . . . . . 6.3 Results of BG for StreamIt Benchmarks . . . . . . . . . . . . . . . . . . . 6.4 Results of average speedup for StreamIt Benchmarks . . . . . . . . . . . . xii ©2020 Philippe Glanon List of Tables 2.1 Comparison of dataflow models. Notations: excellent (++++), very good (+++), good (++), less good (+) . . . . . . . . . . . . . . . . . . . . . . . 3.1 Related works on SWP scheduling of loops modeled by dataflow graphs . . 5.1 Scheduling list for the acyclic dependency graph of Fig. 5.3b . . . . . . . . 6.1 Results of Average Solving Times (sec) for different synthetic benchmarks . 6.2 Benchmarks Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Results of Average Solving Times (sec) of HCS versus ILP solver . . . . . . Context and Problem Statement . . . . . . . . . . . . . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . General Context and Problem Statement

9 2. 2 9 2. 3 15 2. 4

 9293154 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Architecture of Cyber-Physical Systems . . . . . . . . . . . . . . Parallel Programming Paradigm . . . . . . . . . . . . . . . . . . . 12 2.3.1 Multithreading Programming Models . . . . . . . . . . . . . . . . 12 2.3.2 Dataflow Programming Models . . . . . . . . . . . . . . . . . . . Deployment of Loop-Intensive Applications . . . . . . . . . . . . 17

2. 4 . 1

 41 Modeling and Exploitation of Parallelism . . . . . . . . . . . . . 18 2.4.2 Scheduling under resource and communication constraints . . . . 19 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Figure 2 .

 2 1 illustrates a CPS structure composed with two computing platforms.

Figure 2 . 1 :Figure 2 . 2 :

 2122 Figure 2.1: Example Structure of a CPS (Lee & Seshia [8])

Figure 2 .

 2 2 gives a graphical illustration of these different types of architectures. A homogeneous multiprocessor architecture includes multiple processing units (PUs) which have the same micro-architecture and/or provide the same computing performance while a heterogeneous architecture combines different types of PUs each having a specific micro-architecture

Figure 2 . 3 :

 23 Figure 2.3: Speedup of homogeneous and heterogeneous multiprocessor/multicore systems.

3 )

 3

Figure 2 . 4 :

 24 Figure 2.4: Multiprocessor architectures according to the memory access criteria

2. 3 .

 3 Parallel Programming Paradigm are four of the well-known multithreading programming models.

Figure 2 . 5 :

 25 Figure 2.5: Examples of the most popular dataflow model.

Figure 2 .

 2 5c shows an example of SDF graph composed of two actors (𝐴 and 𝐵) linked by a single channel. The production and consumption rates are indicated respectively at the source and the end of the channel. It should be noted SDF models are more expressive and compact than HSDF models.

Figure 2 . 6 :

 26 Figure 2.6: A loop-intensive program and its SDF representation

Figure 2 . 7 :

 27 Figure 2.7: Types of parallelism exploitable in the SDF graph shown in figure 2.6b.

3 . 1 23 3. 2 23 3. 2 . 1 23 3. 2 . 2 24 3. 2 . 3 25 3. 3 29 3. 3 . 1 33 3. 4 36 3. 4 . 2 37 3. 4 . 3 38 3. 5

 31232232123222423253293133436423743385 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Synchronous Dataflow Graphs . . . . . . . . . . . . . . . . . . . . Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Consistency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . Liveness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . Static Scheduling of Synchronous Dataflow Graphs . . . . . . . . Basic Definitions and Theorems . . . . . . . . . . . . . . . . . . . 29 3.3.2 Self-timed Schedules Versus Periodic Schedules . . . . . . . . . . 30 3.3.3 Throughput Evaluation . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.4 Latency Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . Problem Formulation and Related Works . . . . . . . . . . . . . 34 3.4.1 ILP-based Scheduling Approaches . . . . . . . . . . . . . . . . . Scheduling Heuristics . . . . . . . . . . . . . . . . . . . . . . . . This Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Figure 3 . 1 :

 31 Figure 3.1: An example of timed SDF graph

Figure 3 .

 3 1 shows a graphical representation of a timed SDF graph, where each node models an actor and the worst-case processing time associated with the execution of each instance of this actor.

Figure 3 . 3 :

 33 Figure 3.3: Symbolic execution trace of the SDF graph of Fig. 2.6b. Solid arcs are intra-iteration dependencies, dashed arcs are inter-iteration dependencies and the notation ⟨𝑛, 𝑘 𝑖 , 𝑖⟩ stands for the completion of the 𝑘 𝑡ℎ 𝑖 firing of an actor 𝑖 in the 𝑛 𝑡ℎ iteration of the SDF graph, where 𝑛 ∈ ℕ, 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑞 𝑖 being the granularity of the actor 𝑖.

Figure 3 . 4 :

 34 Figure 3.4: Normalized representation of the SDF graph depicted in figure 2.6b

  𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) be a consistent SDF graph with a repetition vector 𝑞 ∈ ℕ * (|𝑉 |) and let 𝑙𝑐𝑚 𝑞 be the least common multiple of the components of 𝑞. For every channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸, let us denote by 𝑛 𝑒 = 𝑙𝑐𝑚 𝑞 𝑞 𝑖 •𝑝 𝑒 (or 𝑛 𝑒 = 𝑙𝑐𝑚 𝑞 𝑞 𝑗 •𝑐 𝑒 ) the normalization factor of the channel 𝑒 where 𝑙𝑐𝑚 𝑞 is the least common multiple of the vector 𝑞. The normalized representation of 𝐺 𝑠𝑑 𝑓 is obtained by multiplying the weights (i.e. production rate, marking and consumption) of every channel by its corresponding normalization factor. Figure 3.4 shows the normalized representation of the SDF graph shown in figure 2.6b. 28 ©2020 Philippe Glanon3.3. Static Scheduling of Synchronous Dataflow Graphs

9 Figure 3 . 5 :

 935 Figure 3.5: Counter example showing that theorem 3.2 is not a necessary condition for liveness.

2 DFigure 3 . 6 :

 236 Figure 3.6: A self-timed schedule of the timed SDF graph depicted in figure 3.1.

  Figure 3.6 depicts a self-timed schedule of the timed 30 ©2020 Philippe Glanon

4 )Figure 3 . 7 :

 437 Figure 3.7: A SWP Schedule for the timed SDF graph depicted in figure 3.1.

  we denote by 𝛽 the throughput achievable by 𝐺 𝑠𝑑 𝑓 in the schedule 𝜎 then 𝛽 = min ∀𝑖∈𝑉 {𝛽 𝑖 }. Since, the period 𝜆 is the average time elapsed between two successive iterations of 𝐺 𝑡 𝑠𝑑 𝑓 , the throughput of 𝐺 𝑡 𝑠𝑑 𝑓 can be defined as the inverse of the period 𝜆. For instance, in the SWP schedule shown in figure 3.7, one can note that new iteration of 𝐺 𝑡 𝑠𝑑 𝑓 occurs 32 ©2020 Philippe Glanon 3.3. Static Scheduling of Synchronous Dataflow Graphs every 9 time units. Thus 𝜆 = 9 and 𝛽 = 1/9.

Figure 3 . 8 :

 38 Figure 3.8: An example of architecture

Definition 4 . 1 (

 41 Dependency Relation). Let us consider a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 and let

4. 2 .

 2 Characterization of Admissible SWP Schedules this latter equality can further be simplified using equation (4.4) and written as: 𝑛 -𝑛 ′ = 𝑋 which implies the existence of a dependency relation from the firings ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ and thus achieves the proof

Figure 3 . 6 𝜎 ( 1 , 12 4. 4

 361124 5 depicts a SWP schedule that achieves maximum throughput for the SDF graph with: 𝜎 (0, 𝐴) * = 0 𝜎 (0, 𝐶) * = 3 𝜎 (3, 𝐶) * = 𝐴) * = 3 𝜎 (1, 𝐶) * = 3 𝜎 (0, 𝐷) * = 10 𝜎 (0, 𝐵) * = 6 𝜎 (2, 𝐶) * = 6 𝜎 (1, 𝐷) * = Minimum Latency for Timed SDF graphs

Figure 4 . 1 :

 41 Figure 4.1: A SWP Schedule of period 𝜆 = 10 and latency T * = 14 for the timed SDF graph depicted in figure 3.1.

Figure 4 .

 4 Figure 4.1 depicts a SWP schedule that gives minimum latency for the timed SDF graph of our running example (refer to figure 3.1). In this schedule, the minimum latency achievable by the SDF graph is equal to T * = 14. Although this schedule achieves minimum latency for the graph, one can note that it does not achieve maximum throughput since throughput 𝛽 = 1 10 achievable by this schedule is suboptimal compared to the throughput

  4. Our ILP formulation consists of different constraints separated into resource, communication, cyclicity and precedence constraints. The inputs of the ILP model are a SDF graph 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) and a HMA 𝐺 ℎ𝑚𝑎 = (𝑅, Δ, Γ), and the scheduling entities are the firings of actors belonging to 𝐺 𝑠𝑑 𝑓 . It is important to recall that the SDF graphs considered in this thesis consist of stateful and/or stateless actors. The objective of this ILP formulation is to minimize the period 𝜆 (or conversely to maximize the throughput 𝛽) achievable by 𝐺 𝑠𝑑 𝑓 in a SWP schedule 𝜎. Let 𝑘 𝑖 ∈ ℕ and 𝑞 𝑖 ∈ ℕ * respectively denotes the firing index and the granularity of an actor 𝑖 ∈ 𝑉 .

DFigure 5 . 1 :

 51 Figure 5.1: An optimal scheduling solution obtained for the non-timed SDF graph and the architecture of our running example.

Figure 5 . 2 :

 52 Figure 5.2: An illustration example for the Heuristic GS (algorithm 2).

Figure 5 . 3 :• Step 3 :

 533 Figure 5.3: Illustration of the Heuristic HCS.

  with a function that takes as inputs five parameters (NP, HFS, HFC, MCC, MIPCC) and outputs asymmetric computation and communication cost matrices as described in Fig-ure3.8b. The parameter NP stands for the number of processing units (PUs) on a given architecture. HFS and HFC stand respectively for the heterogeneity factor for PUs speed and the heterogeneity factor for inter-PUs communication. A high percentage of HFS implies high difference in computation costs for the PUs and a high percentage of HFC implies high difference in communication costs. MCC and MIPCC stand respectively for the mean computation cost of the input SDFG instance and the mean inter-PUs communication cost. In order to generate the computation cost matrix, the generation function selects randomly a mean computation cost Δ𝑖 of every actor 𝑖 from an uniform distribution in the range of 0 to 0.2 ×𝑀𝐶𝐶 and then, the computation cost of every actor on every PU is randomly selected from an uniform distribution of range Δ𝑖 ×

1Figure 6 . 1 :Figure 6 . 2 :

 6162 Figure 6.1: Results of BG for synthetic Benchmarks

  Speedup and parallelism exploitation. Now, if we want to characterize the relative performance of HCS with respect to hardware features, we should study the variations of speedup for different types of heterogeneous multiprocessor architectures. For this purpose, we first set the parameters HFS and HFC respectively to 1.5 and 1.25 to evaluate the average speedup of HCS for different values of NP and then, we set the parameter NP to 4 to evaluate the speedup of HCS with respect to different values of HFS and HFC.

Figure 6 . 3 :Figure 6 . 4 :

 6364 Figure 6.3: Results of BG for StreamIt Benchmarks

7 . 1 7 . 2

 7172 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Open Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 List scheduling heuristics for throughput improvement . . . . . . 7.2.2 Scheduling under storage capacity . . . . . . . . . . . . . . . . . 7.2.3 Real-time scheduling . . . . . . . . . . . . . . . . . . . . . . . . .

Titre:

  Déploiement d'applications à boucles intensives sur des architectures multiprocesseur hétérogènesMots clés: Système cyber-physiques, ordonnancement multiprocesseur, ordonnancement cyclique, graphes de ots de données statiques, architectures hétérogènes, pipeline logiciel, débit maximal.

  2.1 Example Structure of a CPS (Lee & Seshia[START_REF] Lee | Introduction to Embedded Systems, A Cyber-Physical Systems Approach[END_REF]) . . . . . . . . . . . . . . .

9 2.2 Illustration of different types of multiprocessor architectures . . . . . . . . 10 2.3 Speedup of homogeneous and heterogeneous multiprocessor/multicore systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Multiprocessor architectures according to the memory access criteria . . . 12 2.5 Examples of the most popular dataflow model. . . . . . . . . . . . . . . . . 15 2.6 A loop-intensive program and its SDF representation . . . . . . . . . . . . 18 2.7 Types of parallelism exploitable in the SDF graph shown in figure 2.

  Output: an equivalent HSDF graph for 𝐺 𝑠𝑑 𝑓 Let 𝐺 ℎ𝑠𝑑 𝑓 = (𝑉 ′ , 𝐸 ′ , 𝑀 ′ 0 ) be an empty HSDF graph ;foreach actor 𝑖 ∈ 𝑉 do for 𝑘 = 1 . . . 𝑞 𝑖 do Add node 𝑎 𝑘 to 𝑉 ′ ; 𝑗) ∈ 𝐸 do for 𝑘 ′ = 1 . . . 𝑞 𝑗 do 𝜋 𝑖 𝑗 (𝑘 ′ ) ← ⌈ 𝑘 ′ • 𝑐 𝑒 -𝑚 0 (𝑒)

	end
	end
	foreach channel 𝑒 = (𝑖, 𝑝 𝑒	⌉ ;

Commoner et al

. have proposed a polynomial-time algorithm -using depth-first search -to check the liveness of HSDF graph. The algorithm proceeds in two steps. In the first step, it removes every channel with non-zero marking from the HSDF graph and in the second step, it checks if resulting HSDF graph contains cycles. If the resulting graph is acyclic then the initial HSDF graph is live otherwise, it is not live. ©2020 Philippe Glanon Algorithm 1: Transform a consistent SDF graph into a HSDF graph Input: a consistent SDF graph 𝐺 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 ) with a repetition vector 𝑞. 10 𝑘 ← (𝜋 𝑖 𝑗 (𝑘 ′ ) -1) mod 𝑞 𝑖 + 1; 11 Add arc 𝑒 ′ = (𝑖 𝑘 , 𝑗 𝑘 ′ ) to 𝐸 ′ and set 𝑚 0 (𝑒 ′ ) to -⌊ 𝜋 𝑖 𝑗 (𝑘 ′ ) -1 𝑞 𝑖 ⌋ ; 12 end 13 end 14 return 𝐺 ℎ𝑠𝑑 𝑓 ; Contrary to HSDF graphs, liveness checking for SDF graphs is a problem whose time complexity is not polynomial. Two techniques exist to check liveness for a consistent SDF graph. The first technique consists in transforming the SDF graph into an equivalent HSDF graph and applying the algorithm of Commoner et al. [64] to check liveness for the HSDF graph. Many polynomial-time algorithms exist in literature to transform a SDF graph into an equivalent HSDF graph [28, 34, 58]. Figure 3.2 shows an equivalent HSDF graph for the SDF graph depicted in figure

  Definition 3.2 (Admissible Schedules). Let 𝐺 𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live SDF graph. A schedule 𝜎 is said admissible for 𝐺 𝑡 𝑠𝑑 𝑓 if and only if it fulfils the precedence constraints imposed by every channel of 𝐺 𝑡 𝑠𝑑 𝑓 . More precisely, for every channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 and every couple (𝑘 𝑖 , 𝑘 𝑗 ) ∈ ℕ 2 , if the channel 𝑒 induces a dependency relation from a firing ⟨𝑘 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 , 𝑗⟩ then, the following constraint must be fulfilled by any admissible schedule 𝜎.

𝜎 (𝑘 𝑗 , 𝑗) ≥ 𝜎 (𝑘 𝑖 , 𝑖) + 𝛿 𝑖 (3.2)

Table 3 .

 3 1: Related works on SWP scheduling of loops modeled by dataflow graphs Litterature Multi-rate graphs Cyclic dependencies Hetero. architectures Resource constraints Com. constraints Feautrier et al.[START_REF] Feautrier | Fine-grain scheduling under resource constraints[END_REF]

	Govindarajan et al. [49]
	Hanen and Munier, [52]
	Wang et Eisenbeis, [53]
	Robert et al. [45]
	Gasperoni et al., [48]
	Udupa et al, [33]
	Hatanaka et al., [70]
	[Wei et al., 2012][68]

  Problem Formulation and Related Works graphical processing units (GPUs). Although this ILP formulation operates directly on SDF graphs and hold both the architectures with homogeneous or heterogeneous GPUs, it does not consider communication constraints. In this thesis, we aim at proposing a new ILP that operates directly on SDF graphs to optimize throughput while considering both resource, cyclicity and communication constraints. To the best of our knowledge, there is no work in the current literature that proposes such an ILP formulation.

have proposed an ILP formulation to tackle the resourceconstrained SWP scheduling problem of SDF graphs on multiprocessor architectures with 36 ©2020 Philippe Glanon

3.4.

  Let us consider a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 and let (𝑘 𝑖 , 𝑘 𝑗 ) ∈ ℕ 2 . The channel 𝑒 induces a strict dependency relation from a firing ⟨𝑘 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 , 𝑗⟩ if and only if the following inequalities hold:

	Lemma 4.1.
	©2020 Philippe Glanon

  ©2020 Philippe Glanon 4.2. Characterization of Admissible SWP Schedules by Marchetti and Munier[36] for 𝑘 𝑖 , 𝑘 𝑗 ∈ ℕ * . Let us consider for instance, the SDF graph shown in figure 2.6b and let us check if the channel 𝑒 = (𝐶, 𝐷) induces a dependency relation from ⟨1, 𝐶⟩ to ⟨0, 𝐷⟩. Applying lemma 4.1, we get 2 > 0 + 1 -0 ≥ 𝑚𝑎𝑥 {2 -1, 0}, which implies the existence of a dependency relation from ⟨1, 𝐶⟩ to ⟨0, 𝐷⟩. Now, to identify the dependency relations induced by every channel of 𝐺 𝑡 𝑠𝑑 𝑓 in a SWP schedule, we have established lemma 4.2. Before presenting this lemma, let us denote by 𝑔𝑐𝑑 𝑒 the greatest common divisor of the production rate 𝑝 𝑒 and the consumption rate 𝑐 𝑒 of a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 and let 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ∈ ℤ be two variables given by:

  𝑞 𝑗 , 𝑗⟩ be two firings, where 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) and 𝑛, 𝑛 ′ ∈ ℕ. 1. If the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ then, there exists 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } such that 𝑋 = 𝑛 -𝑛 ′ , and the absolute value of 𝑋 gives the number of iterations of 𝐺 𝑡 𝑠𝑑 𝑓 separating the execution of ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ from the execution of ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩. 2. Conversely, for any 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } there exists an infinite number of tuples (𝑛, 𝑛 ′ ) ∈ ℕ 2 such that 𝑛 -𝑛 ′ = 𝑋 and the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩. Let 𝑋 ∈ ℤ such that 𝑛 -𝑛 ′ = 𝑋 . If the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩, then by lemma 4.1 we get:

	Proof.
	1.

where 𝑘 𝑖 , 𝑘 𝑗 ∈ ℕ. Lemma 4.2. Let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel of 𝐺 𝑡 𝑠𝑑 𝑓 and let ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ and ⟨𝑘 𝑗 + 𝑛 ′ •

  𝑞 𝑖 • 𝑝 𝑒 . For any 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 . . . 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } and any large positive integer 𝑧, there exists an infinite number of couples (𝑛, 𝑛 ′ ) ∈ ℕ 2

	such that:

𝑐 𝑒 -𝑝 𝑒 } -𝑚 0 (𝑒) -𝑘 𝑖 • 𝑝 𝑒 + 𝑘 𝑗 • 𝑐 𝑒 𝑞 𝑖 • 𝑝 𝑒 ⌉ which leads to: 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 . 2. Conversely, let us consider a couple (𝑥, 𝑦) ∈ ℤ 2 such that: 𝑥 + 𝑦 = 1 (4.4) and let 𝑛 = 𝑋 • 𝑥 + 𝑧 • 𝑞 𝑗 • 𝑐 𝑒 and 𝑛 ′ = -𝑋 • 𝑦 + 𝑧 •

  Previously, we have shown that lemma 4.2 can be used to identify the dependency relations induced by every channel of 𝐺𝑡 𝑠𝑑 𝑓 in a SWP schedule. Using this lemma, we can now characterize the set of admissible SWP schedules for 𝐺 𝑡 𝑠𝑑 𝑓 . For this purpose, we have established the following theorem, which stands as necessary condition and sufficient condition for admissible SWP schedules of 𝐺 𝑡 𝑠𝑑 𝑓 . If we assume that 𝜎 is an admissible SWP schedule of 𝐺 𝑡 𝑠𝑑 𝑓 then by definition. 3.2 and definition. 3.5, we get the following precedence constraint between ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩: 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ (𝑛 -𝑛 ′ ) • 𝜆 + 𝛿 𝑖 (4.5) By lemma 4.2, there exists 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } such that 𝑛 ′ = 𝑛 -𝑋 . Using this equality in equation (4.5), we get: 𝑛 ′ ) ∈ ℕ 2 such that for any 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 }, the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩. Thus, for 𝑋 = 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 the dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ holds if and only if: 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝛿 𝑖 , ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) Conversely, if we assume this latter inequality, then by lemma 4.2, for any tuples (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 ) with 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), 𝑛, 𝑛 ′ ∈ ℕ and any 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , we can write 𝑛 -𝑛 ′ = 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 . Using this equality, the inequality above becomes: 𝜎 (𝑘 𝑗 , 𝑗) + 𝑛 ′ • 𝜆 ≥ 𝜎 (𝑘 𝑖 , 𝑖) + 𝑛 • 𝜆 + 𝛿 𝑖 (4.8)

	𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ (𝑛 -𝑛 ′ ) • 𝜆 + 𝛿 𝑖	(4.7)
	which is equivalent to:
	𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 • 𝜆 + 𝛿 𝑖	(4.6)
	Now, the right part of this inequality increases with 𝑋 and according to lemma 4.2, there
	exists (𝑛, ©2020 Philippe Glanon

Theorem 4.1. A SWP schedule 𝜎 with period 𝜆 is said admissible for 𝐺 𝑡 𝑠𝑑 𝑓 if and only if for any channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 the following set of precedence constraints is fulfilled by the schedule 𝜎: 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) ≥ 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 + 𝛿 𝑖 ∀𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), ∀𝑘 𝑗 ∈ [0, 𝑞 𝑗 ), ∀𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 ≥ 𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 Proof. Let us assume that a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ where 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) and 𝑛, 𝑛 ′ ∈ ℕ. Now, using definition. 3.5, equation (4.8) can be simplified and rewritten as: 𝜎 (𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗) ≥ 𝜎 (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖) + 𝛿 𝑖 (4.9) which implies that the schedule 𝜎 checks the dependency relation induced by the channel 𝑒 from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ and thus achieves the proof.

=

  In this section, we propose a linear programming model to compute the admissible SWP schedules that achieve minimum latency for timed SDF graph. Let 𝐺𝑡 𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑃, 𝐶, 𝑀 0 , 𝛿) be a consistent and live timed SDF graph and let T be the latency of 𝐺 𝑡 𝑠𝑑 𝑓 . Since the minimum latency achievable by 𝐺 𝑡 𝑠𝑑 𝑓 depends on the minimum latency achievable by every channel in 𝐺 𝑡 𝑠𝑑 𝑓 , we first need to characterize the latency induced by a SDF channel before formulating our linear programming model. For this purpose, we have established the following theorem. 𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) and 𝑛, 𝑛 ′ ∈ ℕ. If the channel 𝑒 induces a dependency relation from the firings ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩, then the latency between these firings is given by: By lemma 4.2, there exists 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } such that 𝑛 ′ = 𝑛 -𝑋 . Using this equality in equation (4.10), we get: 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 • 𝜆 -𝛿 𝑖 and the proof is thus achieved. Let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel of 𝐺 𝑡 𝑠𝑑 𝑓 , let 𝜎 be an admissible SWP schedule of 𝐺 𝑡 𝑠𝑑 𝑓 and let (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 ) be a tuple of positive integers, where 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑘 𝑗 ∈ [0, 𝑞 𝑗 ) and 𝑛, 𝑛 ′ ∈ ℕ. If the channel 𝑒 induces a dependency relation from a firing ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩, then the minimum latency between these firings is given by: T 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 -𝛿 𝑖 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 , gives the minimum latency T 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 induced by the channel 𝑒 between the firings ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ and ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ and we can write:

	4.4. Minimum Latency for Timed SDF graphs
	mum latency achievable by a SDF channel.
	Corollary 4.1. T 𝑚𝑖𝑛 𝑘
	T 𝑘 𝑛 𝑖 𝑘 𝑛 ′
	T 𝑘 𝑛 𝑖 𝑘 𝑛 ′ 𝑗
	Using theorem 4.2, we have derived the following corollary that characterizes the mini-
	48	©2020 Philippe Glanon

Theorem 4.2. Let 𝜎 be an admissible SWP schedule of 𝐺 𝑡 𝑠𝑑 𝑓 , let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel of 𝐺 𝑡 𝑠𝑑 𝑓 and let (𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 ) be a tuple of positive integers, where 𝑘 𝑖 ∈ [0, 𝑞 𝑖 ), 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 • 𝜆 -𝛿 𝑖 , where 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } Proof. Let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel that induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 +𝑛 ′ •𝑞 𝑗 , 𝑗⟩ in the schedule 𝜎. By equation (3.7) and definition 3.5, the latency induced by the channel 𝑒 is given by: T 𝑘 𝑛 𝑖 𝑘 𝑛 ′ 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) + (𝑛 ′ -𝑛) • 𝜆 -𝛿 𝑖 (4.10) Proof. Let 𝑒 = (𝑖, 𝑗) ∈ 𝐸 be a channel that induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩. By theorem 4.2, the latency induced by the channel 𝑒 between these firings is given by: T 𝑘 𝑛 𝑖 𝑘 𝑛 ′ 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 • 𝜆 -𝛿 𝑖 Now, according to lemma 4.2, if the channel 𝑒 induces a dependency relation from ⟨𝑘 𝑖 +𝑛•𝑞 𝑖 , 𝑖⟩ to ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩, there exists 𝑋 ∈ {𝑋 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 , . . . , 𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 } such that 𝑛 -𝑛 ′ = 𝑋 . Thus, 𝑋 = 𝑖 𝑘 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 -𝛿 𝑖 Using theorem 4.1 and corollary 4.1, we have derived the following linear programming model to compute the admissible SWP schedules that achieve minimum latency for 𝐺 𝑡 𝑠𝑑 𝑓 .

  firing ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ then the minimum latency between these firings is given by T 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 = 𝜎 (𝑘 𝑗 , 𝑗) -𝜎 (𝑘 𝑖 , 𝑖) -𝑋 𝑚𝑎𝑥 𝑘 𝑖 𝑘 𝑗 • 𝜆 -𝛿 𝑖 . Since latency is a positive value, for every channel that induces a dependency relation from ⟨𝑘 𝑖 + 𝑛 • 𝑞 𝑖 , 𝑖⟩ to a firing ⟨𝑘 𝑗 + 𝑛 ′ • 𝑞 𝑗 , 𝑗⟩ we can write T 𝑚𝑖𝑛 𝑘 𝑖 𝑘 𝑗 ≥ 0, which leads to constraint (1). Constraint (2) ensures that the latency of 𝐺 𝑡 𝑠𝑑 𝑓 is greater or equal to the finishing time of every firing of any actor within a single iteration of 𝐺 𝑡 𝑠𝑑 𝑓 . Constraints (3) and (4) are integrity constraints on the decisions variables of the model (𝑃 2 ). The number of variables in an instance of (𝑃 2 ) is given by 𝑉 𝑘 = 2 + ∑

∀𝑖∈𝑉

𝑞 𝑖

and the number of constraints 𝐶 𝑘 is bounded on the upper side by ∑ ∀𝑒=(𝑖,𝑗)∈𝐸

  5.8), let us consider a channel 𝑒 = (𝑖, 𝑗) ∈ 𝐸 and let ⟨𝑘 𝑖 , 𝑖⟩ and ⟨𝑘 𝑗 , 𝑗⟩ be two firings such that the execution of ⟨𝑘 𝑖 , 𝑖⟩ precedes the execution of ⟨𝑘 𝑗 , 𝑗⟩. Since each firing is assigned exactly to a single PU (i.e. ∑ 𝑥𝑦 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 • 𝑤 𝑥,𝑘 𝑖 ,𝑖 contain only one term different from zero. In fact, if ⟨𝑘 𝑖 , 𝑖⟩ is assigned to 𝑥 * ∈ 𝑅 and ⟨𝑘 𝑗 , 𝑗⟩ is assigned to 𝑦 * ∈ 𝑅, we can write 𝑤 𝑥 * ,𝑘 𝑖 ,𝑖 = 𝑤 𝑦

	𝑣 =	∑	∑	∀𝑥 ∈𝑅	𝑤 𝑥,𝑘 𝑖 ,𝑖 =	∑ ∀𝑥 ∈𝑅	𝑤 𝑥,𝑘 𝑗 ,𝑗 = 1), the two sums 𝑢 =	∑ ∀𝑥 ∈𝑅	Δ 𝑥𝑖 •𝑤 𝑥,𝑘 𝑖 ,𝑖 and
		∀𝑥 ∈𝑅

∀𝑦∈𝑅

Γ * ,𝑘 𝑗 ,𝑗 = 1,

  𝐺 𝑡 ℎ𝑠𝑑 𝑓 = (𝑉 , 𝐸, 𝑀 0 , 𝛿), an architecture with 𝑝 identical PUs. Output: A valid SWP schedule 𝜎 of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 over T iterations. // Step 1: Scheduling of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 without resource constraints. Compute an optimal SWP schedule 𝜎 ∞ of period 𝜆 ∞ for 𝐺 𝑡 ℎ𝑠𝑑 𝑓 under unlimited number of PUs and let 𝜎 ∞ (𝑛, 𝑖) be the starting time of the 𝑛 𝑡ℎ firing of actor 𝑖 ∈ 𝑉 in 𝜎 ∞ ; // Step 2: Construction of an acyclic dependency graph 𝐺 𝑎𝑑𝑔 𝐸 𝑎𝑑𝑔 ← 𝐸;

	5.3. Decomposed Software Pipelined Scheduling
	Algorithm 2: GS Heuristic
	Input:

  Step 3: Scheduling of 𝐺 𝑎𝑑𝑔 under resource constraints.Find a list schedule 𝜎 𝑎 of 𝐺 𝑎𝑑𝑔 under 𝑝 identical PUs and let 𝜆 be the length of this schedule 𝜎 𝑎 and 𝜎 𝑎 (𝑖) be the starting time of any node 𝑖 ∈ 𝑉 𝑎𝑑𝑔 in the

	schedule 𝜎 𝑎 ;
	// Step 4: Computation of a SWP schedule 𝜎 of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 under resource
	constraints.

  The schedule 𝜎 of period 𝜆 obtained with Algorithm 3 satisfies both resources, cyclicity, precedence and communication constraints.Proof. Resource constraints are obviously met because of the list scheduling algorithm (i.e. Algorithm 4), which ensures that any node in 𝐺 𝑎𝑑𝑔 is assigned to a single resource and the execution of firings allocated to the same resource are not overlapped. The respect of cyclicity constraints is ensured by equation 5.16, which guarantees that the computations and communications of every node 𝑖 𝑘 ∈ 𝑉 ′ are processed cyclically according to the period 𝜆. Now to ensure that precedence and communication constraints are fulfilled, let us consider a channel 𝑒 ′ = (𝑖 𝑘 , 𝑗 𝑘 ′ ) ∈ 𝐸 ′ and let us assume that the firings of nodes 𝑖 𝑘 and 𝑗 𝑘 ′ are respectively assigned to resources 𝑥 * and 𝑦 * .On one hand, if 𝑒 ′ is a direct dependency channel (i.e. 𝑒 ′ ∈ 𝐸 𝑎𝑑𝑔 ), then:𝜎 (𝑛, 𝑗 𝑘 ′ ) ≥ 𝜎 (𝑛, 𝑖 𝑘 ) + Δ 𝑥 * 𝑖 + Γ 𝑥 * 𝑦 * . 𝜎 𝑎 ( 𝑗 𝑘 ′ ) ≥ 𝜎 𝑎 (𝑖 𝑘 ) + Δ 𝑥 * 𝑖 + Γ 𝑥 * 𝑦 * .Since 𝜎 𝑎 is the schedule of the acyclic dependency graph 𝐺 𝑎𝑑𝑔 , this inequality always hold and thus, precedence and communication constraints are satisfied.On the other hand, if 𝑒 ′ is a loop-carried dependency channel (i.e. 𝑒 ′ ∉ 𝐸 𝑎𝑑𝑔 ), then: 𝜎 (𝑛 + 𝑚 0 (𝑒 ′ ), 𝑗 𝑘 ′ ) -𝜎 (𝑛, 𝑖 𝑘 ) ≥ Δ 𝑥 * 𝑖 + Γ 𝑥 * 𝑦 *

	5.3. Decomposed Software Pipelined Scheduling
	By equation (5.16), the inequality above can be rewritten and simplified as:
	66	©2020 Philippe Glanon

Theorem 5.1 (correctness of HCS).

  26 27 28 29 30 31 32 33 34 35 36

		37 38 39 40 41 42 43 44 45 46	47	49
	A 2	A 1	A 2		0	1	2	3	4	5	6	7	8
	C 2 C 1		C 2 C 1		P 1	A 1	A 2	C 2
		C 3			P 2		C 1	C 3	C 4
	B 1	C 4			P 3			B 1		D 1		D 2
		D 1	D 2
			Iteration 2
	(c) An optimal SWP schedule 𝜎 ∞ of 𝐺 𝑡 ℎ𝑠𝑑 𝑓

Table 5 .

 5 1: Scheduling list for the acyclic dependency graph of Fig. 5.3b 𝑖 𝑘 𝐴 1 𝐴 2 𝐶 1 𝐶 2 𝐵 1 𝐶 3 𝐶 4 𝐷 1 𝐷 2 Using the information provided by the list schedule 𝜎 𝑎 , the communication matrix Γ, and the SWP schedule 𝜎 ∞ , we derive a valid SWP schedule 𝜎 of period 𝜆 for 𝐺 ℎ𝑠𝑑 𝑓 under resource and communication constraints. Figure 5.3e depicts the schedule 𝜎 of period 𝜆 = 9 returned by the heuristic HCS for the application graph and the architecture of our running example. It can easily be proved that this schedule satisfies both cyclicity, resource, precedence and communication constraints and a new iteration of 𝐺 ℎ𝑠𝑑 𝑓 occurs according to the period 𝜆 = 9.

	𝑟𝑎𝑛𝑘 (𝑖 𝑘 ) 0	7	7	7 14 14 14 19 24
	• Step 4:

Table 6 .

 6 1: Results of Average Solving Times (sec) for different synthetic benchmarks

	Benchmarks	NP=2	NP=4		NP=8	NP=16
	-	HCS	ILP	HCS	ILP	HCS	ILP	HCS	ILP
	NA=10	2.44 176.45 7.29	302.36 18.77 4287.25 119.58 12480.02
	NA=20	4.17 208.11 9.03	543.08 22.68 6745.97 172.71	∞
	NA=30	5.92 324.21 11.82 675.57 27.11 8123.66	189.6	∞
	NA=40	6.98 395.64 14.09 793.41 35.79 9745.71	201.2	∞
	NA=50	8.71 417.08 16.78	906.5	43.16 12456.73 224.38	∞
	NA=100	10.16 745.67 22.27 1203.66 53.19 16289.92 378.45	∞

  Table.6.1 plots the results of the average solving times for our benchmarks. The ILP solver was able to find a scheduling solution for all multiprocessor architectures except for the 16-PUs architectures, where ∞ means that the solver fails to find a scheduling solution within 8 hours. Conversely, the scalability of HCS is easily visible and in some cases the heuristic is approximately 300 × faster than the ILP solver.

Throughput achievement. In order to evaluate how far the throughput measured with the heuristic HCS is from the throughput measured with the ILP, we studied the variations ©2020 Philippe Glanon

Table 6 .

 6 the synthetic benchmarks according to different values of NA and NP. Figure6.1 plots the results of minimum, average and maximum values of BG. For all the benchmarks, it can be observed that the average values of BG decrease as the values of NP increase.The interpretation of this result is that the throughput measured with heuristic HCS are getting closer to the throughput measured with the ILP solver as the number of PUs is getting greater. Moreover, it can globally be observed that the minimum and maximum values of BG respectively vary approximately in the ranges of 28 -36% and 40-48% as the value of NP increases. This means that the throughput of scheduling solutions returned by HCS are getting closer to the throughput of scheduling solutions obtained with the ILP solver in the ranges of 64 -72% in the best case and 52-60% in the worst case.

		2: Benchmarks Characteristics
	Benchmarks	Description	Number of Actors Stateful actors
	bitonicSort Recursive implementation of the bitonic sorting network	61	7
	fft	Fast Fourier Transform kernel	17	2
	filterBank	A filter bank to perform multi-rate signal processing	53	6
	radar	Radar Array Front-End	54	6
	tde	Time delay equalization	42	5
	of BG for

Table 6 .

 6 3: Results of Average Solving Times (sec) of HCS versus ILP solver

	6.4. Experiments with StreamIt Benchmarks
	Benchmarks	NP=2	NP=4	NP=8	NP=16
	-	HCS	ILP	HCS	ILP	HCS	ILP	HCS	ILP
	bitonicSort 5.81 776.72 15.97 3391.98 34.13 9017.86 114.05	∞
	fft	3.44 323.29 10.98 1798.13 21.13 6123.16 64.61 18765.57
	filterBank	5.62 747.08 15.18 3065.29 32.66 8656.55 99.08	∞
	radar	5.76 756.65 15.11 3168.76 33.25 8659.23 102.23	∞
	tde	5.12 685.64 14.01 2891.86 28.75 7745.71 82.24	∞

  Les systèmes cyber-physiques sont des systèmes distribués qui intègrent un large panel d'applications logicielles et de ressources de calcul hétérogènes connectées par divers moyens de communication (laire ou nonlaire). Ces systèmes ont pour caractéristique de traiter en temps-réel, un volume important de données provenant de processus physiques, chimiques ou biologiques. Une des problématiques rencontrée dans la phase de conception des systèmes cyber-physiques est de prédire le comportement temporel des applications logicielles. An de répondre à cette problématique, des stratégies d'ordonnancement statique sont nécessaires. Ces stratégies doivent tenir compte de plusieurs contraintes, notamment les contraintes de dépendances cycliques induites par l'exécution des boucles de calculs spéciées dans les programmes logiciels ainsi que les contraintes de ressource et de communication inhérentes aux architectures matérielles de calcul. En eet, les boucles étant l'une des parties les plus critiques en temps d'exécution pour plusieurs applications de calcul intensif, le comportement temporel et les performances optimales des applications logicielles dépendent de l'ordonnancement optimal des structures de boucles spéciées dans les programmes de calcul. Pour prédire le comportement temporel des applications logicielles et fournir des garanties de performances dans la phase de conception au plus tôt, les straté-gies d'ordonnancement statiques doivent explorer et exploiter ecacement le parallélisme embarqué dans les patterns d'exécution des programmes à boucles intensives tout en garantissant le respect des contraintes de ressources et de communication des architectures de calcul. L'ordonnancement d'un programme à boucles intensives sous contraintes ressources et communication est un problème complexe et dicile. An de résoudre ecacement ce problème, il est indispensable de concevoir des heuristiques. Cependant, pour concevoir des heuristiques ecaces, il est important de caractériser l'ensemble des solutions optimales pour le problème d'ordonnancement. Une solution optimale pour un problème d'ordonnancement est un ordonnancement qui réalise un objectif optimal de performance. Dans cette thèse, nous nous intéressons au problème d'ordonnancement des programmes à boucles intensives sur des architectures de calcul multiprocesseurs hétérogènes sous des contraintes de ressource et de communication, avec l'objectif d'optimiser le débit de fonctionnement des applications logicielles. Pour ce faire, nous utilisons les modèles de ots de données statiques pour décrire les structures de boucles spéciées dans les programmes de calcul et nous concevons des stratégies d'ordonnancement périodiques sur la base des propriétés structurelles et mathématiques de ces modèles an de générer des solutions optimales et approximatives d'ordonnancement.

Résumé:

©2020 Philippe Glanon

https://www.ibm.com/analytics/cplex-optimizer ©2020 Philippe Glanon

Remerciements

where Δ 𝑚𝑎𝑥 𝑖 is the worst delay to process a firing actor 𝑖 on the architecture 𝐺 ℎ𝑚𝑎 and Γ 𝑚𝑎𝑥 is the maximum inter-PU communication delay. Figure 5.3a illustrates the graph 𝐺 𝑡 ℎ𝑠𝑑 𝑓 for our running example, where for any value of 𝑘 the time costs of nodes are given by 𝛿 𝐴 𝑘 =7, 𝛿 𝐵 𝑘 =5, 𝛿 𝐶 𝑘 =8, and 𝛿 𝐷 𝑘 =5. Secondly, an initial SWP schedule 𝜎 ∞ is calculated. Actually, this schedule does not satisfy neither the resource constraints nor the communication of 𝐺 ℎ𝑚𝑎 , however it gives some interesting information about the dependency relations between the nodes of 𝐺 ℎ𝑠𝑑 𝑓 .

• Step 2. According to the dependency information given by the schedule 𝜎 ∞ , HCS constructs an acyclic dependency graph 𝐺 𝑎𝑑𝑔 = (𝑉 ′ , 𝐸 𝑎𝑑𝑔 , 𝛿), where 𝐸 𝑎𝑑𝑔 is the set of direct dependency channels of 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . Actually, the graph 𝐺 𝑎𝑑𝑔 is obtained by deleting every loop-carried dependency channel in 𝐺 𝑡 ℎ𝑠𝑑 𝑓 . The channel deletion strategy used is the same than that previously described for the heuristic GS. The list-scheduling algorithm consists of two phases:

-Prioritizing Phase. This phase requires the scheduling rank (i.e. the priority) of each node of 𝐺 𝑎𝑑𝑔 to be calculated firstly. The scheduling rank of a node 𝑖 𝑘 ∈ 𝑉 ′ is calculated by a recursive function rank given by:

where 𝑝𝑟𝑒𝑑 (𝑖 𝑘 ) is the set of immediate predecessors of 𝑖 𝑘 . For every node without predecessors, 𝑟𝑎𝑛𝑘 (𝑖 𝑘 ) is set to zero. Secondly, a scheduling list is generated by sorting the nodes of 𝐺 𝑎𝑑𝑔 by increasing order of scheduling ranks. Tie-breaking is randomly performed to sort the nodes with equal ranks. It can easily be shown that the increasing order of scheduling ranks provides a topological order of the nodes, which is a linear order that preserves the dependency relations.

-Mapping Phase. Nodes are selected from the scheduling list by increasing order of the ranks, and each node is allocated to the available processing resource 𝑥 ∈ 𝑅 that minimizes its earliest finishing time (EFT). To map a selected node on a selected processing resource, we use an insertion-based scheduling policy that tries to insert if possible the node in an earliest idle time slot of the resource (i.e an idle time interval between two already scheduled nodes on this resource) while ensuring the preservation of precedence constraints. Let 𝐸𝐹𝑇 (𝑥, 𝑖 𝑘 ) be the earliest finishing time of the node 𝑖 𝑘 ∈ 𝑉 ′ on the resource 𝑥 ∈ 𝑅. This function is defined as follows: