This PhD thesis is devoted to the study of combinatorial optimization problems related to massively parallel embedded architectures when taking into account uncertain data (e.g. execution time). Our focus is on chance constrained programs with the objective of nding the best solution which is feasible with a preset probability guarantee.

A qualitative analysis of the uncertain data we have to treat (dependent random variables, multimodal, multidimensional, dicult to characterize through classical distributions) has lead us to design a non parametric method, the so-called robust binomial approach, valid whatever the joint distribution and which is based on robust optimization and statistical hypothesis testing. We also propose a methodology for adapting approximate algorithms for solving stochastic problems by integrating the robust binomial approach when verifying for solution feasibility. The practical

CARLIER and Mr. Dritan NACE, professors at Université de Technologie de Compiègne, for directing my research work and guiding my steps with their eminent expertise in the eld of combinatorial optimization. Thanks to their constant and careful supervision, I learned the good practices required in order to fulll a high quality research and I was able to nish my Phd dissertation in time without any further delay.

My foremost appreciation also goes to Mr. Renaud SIRDEY, my Phd supervisor at CEA, for his permanent support, his endless ideas helping me progress during these last three years, for the condence he had in me and for his contagious enthusiasm for Science. I wish to thank Mrs. Alix MUNIER, professor at Université Paris 6, and Mr.

Walid BEN-AMEUR, professor at Telecom SudParis, for honoring me in accepting to report this thesis and for their valuable remarks and suggestions. Also, I want to address my thanks to Mr. Aziz MOUKRIM, professor at Université de Technologie de Compiègne, for accepting to be president of the examining committee. I want to address my gratitude to all those who made possible this work.

I especially think of the members of LaSTRE laboratory, from CEA: the coee breaks, the discussions, the advices, the after-works together not only made this an enjoyable professional experience, they were also important for my personal growth and enrichment.

A grateful thought goes to my Phd old fellows Nicolas, Ilias and Thomas for the good moments during the lunches we had together at Resto 1... Also, many thanks to my deskmates from the Phd cage at NanoInnov -Vincent, Simon, Safae, Karl, Moez, the two Amira -for all their help, for all the sweets we shared and for bearing with me and with my continuous complains -J'en ai marre, Ca marche pas!!!, Oh-la-la! just to name a few... A special thought for The Three Musketeers-Pascal, Sergiu and Julien -thanks to their jokes and their support, overcoming the inherent moments dicult of a Phd was less complicated. I want to express my acknowledgments to all those who helped improve this thesis, by re-readings or by providing experimental data: Safae, Vincent, Karl, Pascal, Julien, Sergiu (again) and also Cyril, Loïc, Paul and Lilia.

Many thanks to my friends outside work -Linda, Corina, Mihaela & Marius, Valentin, Anca -due to their presence, I managed to keep my head outside the box of my Phd topic, see the outside world and realize that there is a life out there.

Finally, my heartfelt thanks my family, for their comforting words and their support, from my earliest childhood until now. It's also thanks to them that I became what I am now and I succeeded to get so far. I wish to thank my mother for always being beside me, my aunt (Monica) and my grandmothers for their pieces of advice as well as my little cousins (Vladut and Alex) for their unconditional love. I would like to pay tribute to my father, which was the rst one to persuade me to follow this path and which would have been happy to live this moment.

Last, but not least, my warmest thanks to Andrei, my constant supporter, for his kindness and his love, for his help and for the lost weekends, and for simply standing beside me, while facing the ups and downs of being a Phd student.

Résumé

Ce travail de thèse de doctorat est dédié à l'étude de problèmes d'optimisation combinatoire du domaine des architectures massivement parallèles avec la prise en compte des données incertaines tels que les temps d'exécution. On s'intéresse aux programmes sous contraintes probabilistes dont l'objectif est de trouver la meilleure solution qui soit réalisable avec un niveau de probabilité minimal garanti.

Une analyse qualitative des données incertaines à traiter (variables aléatoires dépendantes, multimodales, multidimensionnelles, diciles à caractériser avec des lois de distribution usuelles), nous a conduit à concevoir une méthode qui est non paramétrique, intitulée approche binomiale robuste . Elle est valable quelle que soit la loi jointe et s'appuie sur l'optimisation robuste et sur des tests d'hypothèse statistique. On propose ensuite une méthodologie pour adapter des algorithmes de résolution de type approchée pour résoudre des problèmes stochastiques en intégrant l'approche binomiale robuste an de vérier la réalisabilité d'une solution. La pertinence pratique de notre démarche est enn validée à travers deux problèmes issus de la compilation des applications de type ot de données pour les architectures manycore.

Le premier problème traite du partitionnement stochastique de réseaux de processus sur un ensemble xé de n÷uds, en prenant en compte la charge de chaque n÷ud et les incertitudes aectant les poids des processus. An de trouver des solutions robustes, un algorithme par construction progressive à démarrages multiples a été proposé ce qui a permis d'évaluer le coût des solutions et le gain en robustesse par rapport aux solutions déterministes du même problème.

Le deuxième problème consiste à traiter de manière globale le placement et le routage des applications de type ot de données sur une architecture clustérisée. L'objectif est de placer les processus sur les clusters en s'assurant de la réalisabilité du routage des communications entre les tâches. Une heuristique de type GRASP a été conçue pour le cas déterministe, puis adaptée au cas stochastique clusterisé. relevance of our approach is validated through two problems arising in the compilation of dataow application for manycore platforms.

The rst problem treats the stochastic partitioning of networks of processes on a xed set of nodes, by taking into account the load of each node and the uncertainty aecting the weight of the processes. For nding stochastic solutions, a semi-greedy iterative algorithm has been proposed which allowed measuring the robustness and cost of the solutions with regard to those for the deterministic version of the problem.

The second problem consists in studying the global placement and routing of dataow applications on a clusterized architecture. The purpose being to place the processes on clusters such that it exists a feasible routing, a GRASP heuristic has been conceived rst for the deterministic case and afterwards extended for the chance constrained variant of the problem.

Introduction

As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality.

Albert Einstein

The world we are living in is subject to permanent changes, where uncertainty is encountered each day, everywhere, under various avors, aecting individuals as well as collective consciousness. We can choose to ignore it, which is the most convenient path, or we can embrace the uncertainty surrounding us, accept it and take it into account in our quest of the Truth.

Unfortunately, when making decisions, uncertainty is often neglected and the best decision is selected by applying classical methods from the combinatorial optimization eld, without worrying about the variations of the data. Combinatorial optimization, one of the most popular branches of mathematics over the last half of century, with a widespread area of application from logistics and transportation to planning and scheduling, nance or engineering design, allows to solve combinatorial problems by nding the best solution from a set of nite but potentially enormous size.

Dantzig, one of the greatest pioneers in the elds of operations research and management science, considered optimization under uncertainty amongst the most promising and important areas of combinatorial optimization. A fervent promoter of the subject of stochastic optimization throughout the last thirty years, he emphasized during an interview in 2000 1 :

Planning under uncertainty. This, I feel, is the real eld that we should be all working in. Those of us who were doing the planning right from the very beginning understood that the real problem was to be able to do planning under uncertainty. The mathematical models that we put together act like we have a precise knowledge about the various things that are happening and we don't. Introduction bandwidth, memory, etc.). As such, the resolution of related optimization problems via operations research techniques has spread from compilers backend throughout the overall compilation process. To cite only a few, we can mention the instruction scheduling and buer problems or more recent optimization problems such as the dimensioning of communication buers or the partitioning and placement of process networks. Or, even if a common characteristic of these problems is the presence of uncertain data such as execution times or network latencies, the research focusing on applying techniques from optimization under uncertainty is still at the beginning.

Our works are situated in this context, of optimizing under uncertainty for the compilation of applications for embedded manycore.

Hence, this dissertation deals with the application of the most appropriate methods from the eld of optimization under uncertainty to the resolution of combinatorial problems arising in compilation for massively multi-core embedded systems.

Such platforms, composed of several parallel cores, a number of memory mechanisms and an infrastructure connecting all the components together, require applications that can eciently take advantage of the available resources and of the parallelism.

One viable way of programming applications for the new generation of embedded architectures is based on dataow models, in which applications are expressed as set of tasks communicating through FIFO channels.

Our applicative work focuses mainly on the partitioning, placement and routing of dataow applications under the assumption of uncertain data (in particular unitary execution times). These combinatorial optimization problems related to resource allocation are part of the several steps composing the compilation process of a dataow application.

Since the general topic of the present study has been introduced, let us now mention some of the research questions which drew our attention and guided our research path:

For a given optimization problem from embedded domain, what is the benet of taking into account uncertainty instead of solving the deterministic version? How can be captured, analyzed and expressed the uncertainty occurring in compilation of applications for embedded systems? What are the most relevant models and resolution techniques of uncertain optimization when dealing with combinatorial problems from the embedded domain?

Once found, how these resolution methods for optimizing under uncertainty can be applied in an operational manner for solving the application case studies?

Throughout our present dissertation, we will show the importance of optimization under uncertainty. Moreover, applying it for solving problems for soft real-time embedded systems can be benecial and even mandatory in some cases in order to nd robust solutions. For these types of applications and a given optimization problem, we are looking for the best solution which is guaranteed to be feasible with a target probability (for example, the best solution which is feasible with a probability of 0.9). When designing soft real-time systems for a large class of applications (audio encoding, multimedia, telecommunications, etc.), breaking requirements, even if not desirable, is acceptable if it happens with a suciently low probability since the overall required Quality of Service (QoS) is not compromised. A typical example consists of a possible loss of some frames from a group of pictures in an MPEG encoding. As such, by accounting for data variations when dimensioning our system we can avoid oversizing, expensive in terms of hardware, or undersizing, expensive in terms of reliability. Also, we could estimate the robustness of an already dimensioned system and nd scenarios which are not feasible or not acceptable. We are not considering the case of safety-critical systems (nuclear plant control and command, automotive, avionics), for which the design has to be based on the worst-case scenario since any break of the requirements cannot be accepted due to the highly potential risks.

For answering the other questions, which are in some sense inter-related, we began by analyzing the sources of uncertainty aecting data from optimization problems in an embedded environment and in particular the execution times. As the state of art and some basic qualitative examples have pointed out, execution times are dicult to characterize and do not follow classical distributions laws. At best, we can arm that they are random variables of a bounded support, dependent and multidimensional.

The above conclusions have limited our choice to resolution approaches which can be applied for embedded eld without making simplifying or making erroneous assumptions about the uncertain data. Other prerequisite we are focusing on is the ability to nd solutions which are guaranteed with a minimal probability threshold. Also, considering the complexity of the combinatorial problems and the size of the instances in the compilation process, we have to be able to t the uncertainty treatment into approximation methods, heuristics or metaheuristics.

Between the existing optimization approaches we are aware of, the only one making almost no assumptions on the uncertain data is the one based on scenarios.

Its original form is too conservative, since it searches for solutions satisfying all the scenarios. Therefore, we preferred to extend it and conceive a new method, the robust binomial approach, which can nd solutions which are guaranteed to hold for a minimal required probability with a high condence level. The only assumption we are making is the existence of a sample with a sucient size of independent and identically distributed observations for the uncertain data (which can exhibit dependencies).

Moreover, the robust binomial approach can be easily integrated within an heuristic or metaheuristic in the oracle deciding the feasibility of a potential solution.

We, thus, proposed an overall framework for solving problems with probabilistic constraints using heuristics and the robust binomial approach. Also, assuming an approximate resolution algorithm had already been implemented to solve a problem in the deterministic case, we thought of the necessary steps for adapting (meta)heuristics to the stochastic version of the same problem.

We then applied the robust binomial approach to the stochastic partitioning of process networks for which we consider uncertain weights for the processes. For the other application case, the joint placement and routing of dataow applications, we rst design a GRASP (Greedy Randomized Adaptative Search Procedure) treating the deterministic case since this problem has not been yet treated in a global manner.

Afterwards, we attacked the stochastic problem supposing the tasks have uncertain weights and integrating the robust binomial approach into the GRASP.

The present manuscript, resuming our contribution, is organized into this introduction, four chapters and a conclusion. (Part of the work of this thesis has also been subject of several publications, referenced on a separated page.) Let us now give a brief overview of each chapter.

Chapter 1 introduces the context and gives more details about the motivations of our research. The rst two sections present the emergence of massively parallel embedded systems, the main hardware components of a manycore architecture as well as the diculties in developing applications for this kind of systems. Then, we provide an overview of the dataow paradigm, an alternative to sequential programming which seems more appropriate for programming manycore applications.

Sigma-C, a dataow programming model and language conceived by the CEA and the associated compilation process, are the subject of the following section. We conclude the chapter with a motivation section, in which we also provide a short qualitative analysis of execution times, one of the main uncertainty source for embedded systems, related to optimization problems.

Chapter 2 is dedicated to optimization under uncertainty and, in particular, to the robust binomial approach, the non-parametric resolution method we conceived to cope with uncertain data dicult to model or to characterize. Some general considerations about the dierent techniques for optimization under uncertainty, such as stochastic programming and robust optimization, are given in the rst part. The second section presents the general structure of the type of problems we are interested in, joint chance constrained programs for which we search the best solution feasible for all constraints with a minimal probabilistic guarantee.

We show the diculties in solving chance constrained programs and we discuss existing work, classied in convexity studies, robust optimization methods, sampling techniques and (meta)heuristics. The next section explains more in details the robust binomial approach, the statistics beyond it, the way it can be applied for solving a chance constrained problem and the methodology for integrating it into an existing metaheuristic. The last part proposes some possible extensions of the robust binomial approach to more general problems (with more than one initial probability level requirement or uncertain objective function).

In Chapter 3 we study the stochastic problem of partitioning networks of processes onto a xed number of nodes. Given a dataow application, the objective is to assign the tasks to a xed number of processors in order to minimize the total communications (which correspond to minimizing communications between processors) while respecting the capacity of each processor in terms of resources (memory footprint, core occupancy etc.). An extension of the Node Capacitated Graph Partitioning problem, this application case is known to be NP-hard. The stochastic version we study here is the partitioning for which the weights of the tasks are uncertain resources (processor occupancy, memory footprint) and thus, we have to solve the chance constrained program for which the capacity of each processor is respected for each resource with a minimal probability target. For clarication purposes, a preliminary section introduces the concepts and the greedy heuristic on which our resolution algorithm is based. The adaptations made for integrating the robust binomial approach into the existing semi-greedy heuristic are presented in a separated section and experimental results are given at the end.

The tests performed have two main purposes: showing the importance of taking into account data variations and measuring the price of robustness compared to the deterministic version. Running under the same assumptions as the stochastic algorithm, the method for the deterministic problem is unable to nd feasible solutions on a large number of cases. As for the price of robustness, the stochastic solutions are consistent with those found in the deterministic case. More important, they are guaranteed to hold with a high probabilistic and condence levels.

The other application case, the joint placement and routing problem, is studied in Chapter 4 from both the deterministic and stochastic perspectives. The purpose is to map dataow applications on a clusterized parallel architecture by making sure that the capacities of the clusters are respected and that, for the found placement, there exists a routing through the links of the underlying Network on Chip (NoC), respecting the maximal available bandwidth. Each of the two subproblems, tasks placement and respectively routing, are NP-hard and treating them together, in a single step, could be convenient mainly in the case of applications with high bandwidth demands (such as multimedia or computer vision), for which the bandwidth resources of the NoC can become critical. Moreover, treating them separately, in a sequential manner, can lead to placements for which the routing is impossible subsequently.

The introductory sections present the formal description of the problem and existing deterministic mapping approaches, static or dynamic. As for the stochastic case, we give some related works but to the best of our knowledge, the exact same problem has not been yet addressed in the literature. The next section proposes a GRASP (Greedy Randomized Adaptative Search Procedure) heuristic for solving the deterministic version. In order to solve the chance-constrained problem when the resources of the tasks are uncertain, we extended the GRASP via the robust binomial approach and the necessary changes are given in another section. Extensive computational results on synthetic benchmarks and a real application from the image processing eld are given at the end for the deterministic case as well as for the stochastic one.

List of Publications

Introduction

One of the key requirements when designing embedded systems solutions nowadays is the performance in terms of computer power for all supported applications. The evolution of latest applications like video and image processing based on sophisticated compression and decompression algorithms (MPEG 4, H.264, etc.), 3D video games, scientic computing or data security determines a demand in computer power ten to a hundred times superior to that of a few years ago and even make the performance requirements for these embedded systems exceed the abilities of most desktop computers.

Unfortunately, over the last past years, it has become obvious that the performance oered by traditional sequential single core processors has not kept step with the demand. Even if, according to the original Moore's law [START_REF] Moore | Progress in digital integrated electronics[END_REF], the number of transistors which can be placed on a single chip has continued to double every two years, the performance of practical computing does not follow the same exponential growth rate 1 . Several causes exist for this phenomenon, called Moore's gap: poor returns from single CPU mechanisms such as caching and pipelining, the power envelopes (both active and leakage related), wire delay, etc.

Between the viable solutions to improve performance we can cite the conversion of additional transistors into computing power at relatively low clock frequency by designing and using ecient parallel processing systems.

1. The Pentium 4, rst implemented with the same technology as the Pentium 3 (0.18-micron) is a popular example demonstrating the break in performance scaling. Despite that Pentium 4 had 50% more transistors than Pentium 3, its performance, based on the SPECint 2000, was only 15% greater. (http://www.embedded.com/design/mcus-processors-and-socs/4007064/Goingmulticore-presents-challenges-and-opportunities)

CHAPTER 1. RESEARCH CONTEXT AND MOTIVATIONS

The present multi-core architectures are achieving more performance by the use of several processing elements (roughly a dozen) and the next generation of manycore chips is even more powerful, containing hundreds if not thousands of cores. As such, we are entering into a manycore era in which the updated Moore's law states that the number of cores on a chip doubles every two years. NVidia graphics, IBM Cell BE, etc) and homogeneous chips (e.g. Intel Xeon, IMB Power, STM, Tilera, Kalray, etc) [START_REF] Louise | Programmability in the age of the manycore, beyond Stream Programming[END_REF] However, in order to eciently exploit the parallelism 2 and to fully take advan- tage of the computing power these manycore may provide, their design requires new programming and execution paradigms as well as innovative compilation technologies. After a brief description of the hardware architecture of a type of embedded manycores, the next subsections are describing the challenges manycore have to face and some appropriate programming and execution models allowing to eciently exploit the parallelism. and Multiple Instruction Multiple Data (MIMD). Between these categories, the rst one corresponds to a casual sequential processor, only the last three making parallel execution possible. As such, almost all parallel systems today are either SIMDs, easier to program but for which the parallelism is more dicult to exploit, or MIMDs, for which each processor is executing its own program ow. More exible than SIMD and allowing non-structured data and conditional or data-dependent algorithms, the MIMD is a more usual implementation of the many-core concept.

Furthermore, according to the memory organization, existing MIMD can be grouped into DMM (Distributed Memory Machines) and SMM (Shared Memory Machines). In the distributed memory machines, each processing element has its own local memory to which it has direct access. The access to other processor's local memory is a message-passing operation performed using the interconnection network. In a shared memory system, the processors have a common memory space and communications between them are realized by reading and writing data to a shared address in the memory. One of the advantages of the SMM over a DMM is the ease of communication via the shared memory and without data replication.

However, due to bandwidth limits, the number of processors in a SMM is limited because using a larger number of processors results in an increase in the access times at eective memory bus. As such, the SMMs can provide more computing power while DMMs are more scalable.

Manycore architectures

A massively multi-core (manycore) processor is a parallel computing system, composed of a number of processing cores, a mix of local and shared memory, distributed global memory or multilevel cache hierarchy and an infrastructure for inter-cores communication. The eciency in such a system is determined by a high scalability and computing power.

In a clustered massively multi-core chip, the processing elements are organized in clusters, interconnected via a Network-On-Chip (NoC). This type of architecture represents a DMM in which the nodes are not single processors, but SMMs. As such, it provides a solution for the problem of scalability of the SMMs, for which it is dicult to exceed 32 processors [START_REF] Sinnen | Task scheduling for parallel systems[END_REF], and for the performance issues of the DMMs.

As illustrated in Fig. 1.2 [START_REF] Carpov | Scheduling for memory management and prefetch in embedded multi-core architectures[END_REF], each cluster contains more processing elements, with a processing core and a private cache memory, as well as a shared memory space. The entire processor is connected through a memory access controller to an additional external memory. The external memory is used for storing application data and instructions. The processors belonging to the same cluster exchange their data eciently, using the local shared memory space. For communication of processors on dierent clusters, data transfers are assured by the Network-On-Chip. In order to transfer data between clusters in an eective manner, the NoC must provide enough bandwidth. Therefore, an important factor in designing ecient manycore systems is the choice of an appropriate interconnection network.

An alternative to the basic communication structures in a System-On-Chip (e.g. traditional bus-based communication and dedicated link-to-link points), a well designed chip network can avoid performance bottleneck which appear in manycore For more details about the current research and practices concerning the NoC, we refer the reader to [START_REF] Bjerregaard | A survey of research and practices of Network-on-chip[END_REF].

Challenges of programming for manycores

According to Gustafson's law [START_REF] Gustafson | Reevaluating Amdahl's law[END_REF], as more computing power becomes available, new classes of complex applications (e.g. software and cognitive radio, autonomous vehicles, virtual and augmented reality) emerge. However, programming these applications for manycore systems is a dicult task, since there are at least three diculties to overcome: handle limited and dependent resources (memory, NoC), be able to run correctly large parallel programs and eciently exploit the underlying parallel architectures.

The rst issue is already solved in existing embedded manycore like Kalray MPPA platforms or ST-Micro Storm using some kind of hierarchical memory architecture, with distributed memories close to the processing elements and a shared on-chip memory for communication with other clusters and the outside world.

For taking advantage of manycores architectures in terms of computing • Easy synchronization between program tasks. Since one of the most dicult and error-prone jobs in parallel programming is explicit synchronization, it is recommended to avoid synchronization structures or mask their use.

• Execution determinism. For constant entry dataset, computation results should be independent of the execution hazards coming, for example, from task scheduling and allocation.

• Possibility to easily integrate existing code. This is necessary in order to migrate or integrate legacy software developed in familiar languages for embedded programmers.

In [START_REF] Jantsch | Models of computation and languages for embedded system design[END_REF], Jantsch identies and divides un-timed models adapted to non critical In such models, inter-tasks synchronization is realized implicitly, via the data.

In the following sections, we are concentrating on dataow models and languages and, in particular, Sigma-C.

Dataow models and stream programming

Dataow paradigm seems to be a good candidate for programming manycore applications, which satisfy most of the properties stated before. With the rst models emerging in the early 1970s, dataow languages provide an ecient and simple solution to express programs, which can be executed on a parallel architecture, without worrying about data synchronization. Since a history of the evolution of dataow computation models is beyond the scope of this chapter, we refer the interested reader to the following texts [START_REF] Bic | Advanced Topics in Dataow Computing and Multithreading[END_REF], [START_REF] Iannucci | Multithreaded computer architecture : a summary of the state of the art[END_REF].

There exist several formalisms for dataow models dierent in their expressive power and the guarantees they provide. Before describing more in detail some of the most representative dataow models, let us introduce some general features of dataow programming.

Taxonomy

In a dataow model, a program is described as a directed graph, consisting of nodes representing tasks (also named actors) and arcs that represent unidirectional communication channels. The actors of a dataow application can be atomic or a hierarchically specied subgraph. Data, quantized into tokens, is carried exclusively through the channels, considered to be First-In-First-Out (FIFO) queues. A token consists of the smallest indivisible quantum of data traversing the channels. Since the communications channels are unbounded, they can potentially carry an innite number of tokens. The ow passing through a channel is denoted as a stream.

The execution of a dataow process is a sequence of rings or evaluations. When an actor is executed, it consumes a certain quantity of data tokens on its input channels and it produces a number of result tokens written on its output channels.

Any node can re (perform its computation) when all the required data is available on its input channels. Since there can be more actors ring in the same time, one of the interesting properties supported by dataow languages is the concurrency. Synchronization between actors is realized exclusively via the data traversing the channels. Because the program execution depends on the availability of the data, these models belong to the family of data-driven models of computation.

The number of tokens produced or consumed may vary for each ring and is dened in the ring rules of an actor. An actor can have one or several ring rules and can be static or dynamic. For a dynamic actor, the choice of the ring rule is data-dependent and consequently, its behavior for future rings cannot be predictable. A static actor can have one or more ring rules while a dynamic actor has at least two.

In function of how the consumption and production of tokens and the ring rules are specied, dataow computing models can be divided in plenty dierent classes.

For a deeper insight description of dataow computation models, we refer the reader to [START_REF] Girault | Hierarchical nite state machines with multiple concurrency models[END_REF], [START_REF] Wipliez | Classication of dataow actors with satisability and abstract interpretation[END_REF], [START_REF] Jantsch | Models of computation and languages for embedded system design[END_REF], [START_REF] Najjar | Advances in the dataow computational model[END_REF]. The most representative dataow models (cf.

Dataow models 1.3.2.1 Dataow process networks

A dataow process [START_REF] Lee | Dataow process networks[END_REF] is a particular type of Kahn process consisting of a sequence of rings and a network of such processes is called a dataow process network (DPN). In a Kahn process network [START_REF] Kahn | The semantics of simple language for parallel programming[END_REF], which is the least constraint model, the network processes communicate with each other only via unbounded FIFO channels, with reading data from these channels being blocking and writing data asynchronous. As such, because the channel size is innite, writing always succeeds and does not stall the processes while reading can be realized only from a non-empty channel and when the channel contains sucient tokens. This model assures execution determinism (the data produced by a KPN are a function of entries of the KPN) and monotonicity (a KPN needs only partial information of the input stream to produce partial information of the output stream). The last property allows parallelism, because a process can start the computation of output events without needing the whole input. Testing an input channel for the existence of tokens without consuming them is forbidden. Since there is a total order of events inside a process but no order relation between events in dierent processes, KPN are only partially ordered. Another view of KPNs, as pointed out by [START_REF] Parks | Bounded Schedule of Process Networks[END_REF], is a set of Turing machines connected by one-way tapes, in which each machine operates on its own working tape. Unfortunately, as a consequence related to the halting problem 3 , the questions for important properties such termination and memory boundedness are undecidable.

Synchronous Dataow model

One solution consists in using restrictions of KPN where these questions are decidable. Synchronous dataow (SDF) [START_REF] Lee | Synchronous data ow[END_REF] model imposes that a process consumes and produces a xed quantity of tokens for each ring. All the agents are static and their ring rules do not change during the execution. The model is not synchronous in the same sense as for synchronous languages 4 , the term synchronous referring to producing and consuming a xed number of tokens, specied a priori, for each 3. The halting problem states that, given a nite-length program that runs on a Turing machine, it is undecidable to decide always in nite time whether or not the program will terminate.

Unlike synchronous reactive languages for dataow dominated systems, like Signal or

Lustre, there is no notion of clocks.

actor. More, production and consumption rates on all arcs are related through balance equations.

Suppose that an actor A produces O A tokens on an output connected to actor B (cf. Fig. 1.5-a) which requires I B tokens on its input in order to execute. Suppose also that the actor A res r A times and actor B has a frequency rate of r B . According to the balance principle, the following equation can be written:

r A * O A = r B * I B .
This type of equation can be expressed for each arc in the SDF, forming a system of balance equations. For the simple graph in Fig. 1.5-b, the equations are: This system is then solved by the compiler to nd the vector r = [r 1 , r 2 , r 3 ] of rings. As shown in [START_REF] Lee | Static scheduling of synchronous data ow programs for digital signal processing[END_REF], for a connected dataow, if there is a non-trivial solution for the balance equations, then the solution is unique and it is the smallest positive integer. If there is no solution, the graph has inconsistent execution rates and there is no bounded memory innite execution of the dataow. Given a solution, a partial ordering constraints between rings can be specied and a precedence graph can be constructed.

r 1 * a = r 2 * f r 1 * b = r 3 * c r 3 * d = r 2 * e.
Thanks to the balance principle, the questions of bounded memory and deadlock are decidable. That and other properties such as determinism and static scheduling at compile time make the SDF a reliable and popular model at the basis of (many) embedded software such as Ptolemy [START_REF] Buck | Readings in hardware/software co-design[END_REF], COSSAP [START_REF] Kunkel | COSSAP : A stream driven simulator[END_REF], System Canvas and DSP Canvas from Angeles Design Systems [START_REF] Murthy | System Canvas : a new design environment for embedded DSP and telecommunication systems[END_REF] or Cocentric System Studio from Synopsys.

Even if the SDF model is convenient for certain applications, it comes with a relatively high price: because the number of tokens produced and consumed is xed, they cannot depend on the data and the application cannot use conditional variations in the ow.

Cyclo-Static Dataow Model

A more exible extension of SDF is the Cyclo-Static Dataow (CSDF) model [START_REF] Bilsen | Cycle-static dataow[END_REF] which permits that the number of tokens produced and consumed vary from one activation to another in a cyclic manner. As shown in Fig. 1.6-a, every agent j has a sequence of rings [r j (1), r j (2), . . . , r j (P j )] of length P j , the production on the output channel u is dened as a sequence of constant integers O u j (1), O u j (2), ..., O u j (P j ) and the consumption on edge u is dened as a sequence I u j (1), I u j (2), ..., I u j (P j ) . The n-th execution of the task j corresponding to the code of the function r j ((n -1) mod P j + 1 produces O u j ((n -1) mod P j + 1) tokens on edge u. A cyclostatic actor j has a ring rule evaluated as true for its nth ring if and only if all the input channels contain at least I u j ((n -1) mod P j + 1) tokens.

Dynamic Dataow Model

A wider dataow model in which data control execution is allowed is the dynamic dataow model (DDF) [START_REF] Najjar | Advances in the dataow computational model[END_REF]. By extending the balance equations, the number of tokens produced or consumed may vary dynamically and thus, the consumption and production cannot be known at compile time. Many of existing dynamic dataow languages are derived from static dataow model, by including a limited set of dynamic actors, whose behavior depends on the data.

One of the dynamic dataow models is the boolean dataow, obtained by the addition of two dynamic actors: select and switch (see Fig. 1.7) to the synchronous dataow model. One of the main advantages of this model, as shown by Buck [START_REF] Buck | Scheduling dynamic dataow graphs with bounded memory using the token ow model[END_REF], is its Turing completeness. This means that with this programming model, one can implement an universal Turing machine. However, even if it is more exible and sometimes, it is possible to make approximate scheduling analysis, this model does not allow to answer critical questions like deadlock freeness or bounded memory.

Stream programming

Based on dataow models, stream programming seems a more appropriate framework to express and describe massive parallelism than imperative languages. By their theoretical background, stream languages can guarantee important application properties such as: functional determinism, memory bounded execution or absence of race conditions. Stream programming provides a good choice for applications intended for manycore systems.

A rst language to take into account dataows was Lucid [START_REF] Ashcroft | Lucid, a nonprocedural language with iteration[END_REF] in which even if the program description is sequential, the program can be represented as a KPN.

Nowadays, due to the new manycore architecture, there is a regain in interest in steam programming and numerous languages have been proposed. Between the most successful, we can mention StreamIt [START_REF] Amarasinghe | Language and compiler design for streaming applications[END_REF], StreamC [START_REF] Khailany | Imagine : media processing with streams[END_REF], Cg [START_REF] Mark | Cg : a system for programming graphics hardware in a C-like language[END_REF], Brook [START_REF] Buck | Brook Specication v0.2[END_REF],

ArrayOL [START_REF] Boulet | Array-OL Revisited, Multidimensional Intensive Signal Processing Specication[END_REF] or the more recent ΣC [START_REF] Goubier | ΣC : a programming model and langage for embedded manycores[END_REF]. Even if all these programs are based on dataow models, they are dierent in the format and type of the streams, the structure of the underlying graph, the expression of data reorganisation and the type of production/consumption (static or dynamic). For a more detailed classication of main stream languages, we refer the reader to [START_REF] De Oliveira Castro | Expression et optimisation des réorganisations de données dans du parallélisme de ots[END_REF].

In the sequel, we are introducing more in detail the ΣC programming model and language for embedded manycore and give an overview of the compilation process of such a stream program (see [START_REF] Aubry | Extended cyclostatic dataow program compilation and execution for an integrated manycore processor[END_REF], [START_REF] Goubier | ΣC : a programming model and langage for embedded manycores[END_REF] for details). ΣC is a dataow programming model and language designed for parallel programming of high performance embedded manycores processors and computing grids. ΣC model, based on process networks with process behavior specications, has slightly more expressive power than SDF and CSDFs while being less general than BDF.

As such, it has sucient expressive power for most applications, while allowing to perform a formal analysis for verifying properties like absence of deadlock or memory bounded execution. As a programming language, ΣC relates to StreamIt [START_REF] Amarasinghe | Language and compiler design for streaming applications[END_REF] or Brook [START_REF] Buck | Brook Specication v0.2[END_REF], and more, it is designed as an extension of the C language, with keywords to dene and connect agents (individual tasks in the stream model). In addition to all the aspects oered by dataow programing, ΣC has the ability to specify the productions and consumptions of each task, which information can be used later in the compilation phase for checking.

An application in ΣC is described as a static instantiation graph of interconnected agents, which does not evolve through time (remains the same during the execution, without any agent creation or destruction or change in the topology). An agent is the basic unit of this programming model, behaving as a cyclic machine with variable amount of data. At each transition of the agent corresponds a either xed or variable number of data produced and consumed on its ports. Except the user agents, specic to each application, there are several system agents for data distribution and synchronization: Split, Join (both for distribution of data in a round-robin fashion), Dup (for data duplication), Select, Merge, Sink. Similar to agents, subgraphs implement only composition and consist of links and data distribution network. For a detailed specication of ΣC language, we refer the reader to [START_REF] Goubier | ΣC : a programming model and langage for embedded manycores[END_REF].

The main characteristics of ΣC will be illustrated through an example, consisting in a moving targets tracking application, a real case study used across this document for an experimental validation of our optimization algorithms.

Example of a ΣC application: Motion detection

The motion detection example represents a video processing application, performing a target tracking on a sequence of related input video frames. Sequential video frames are analyzed and the movement of targets between the frames is outputted. The main idea is to look for temporal redundancy between successive images, using a Block Matching Algorithm (BMA). The current frame from the video sequence is divided into horizontal strips for which we measure the absolute dierence between each pixel and the corresponding pixel from the previous frame. For improving the algorithm, a median lter is then applied with the aim of smoothening the strips. For each horizontal strip s, the standard deviations of the absolute dierence are computed by macro-blocks and the minimum is selected according to the equation:

σ s = min N i=1 (x i -m) 2 N
where N is the size of the macro-block (given as an input parameter), x i is the absolute dierence in intensity for pixel i and m is the average over x i . Afterwards, a corresponding binary image B is constructed, by applying to the image a lter, such as, for each pixel i:

B i = 1 if x i -m ≥ min s (σ s ) 0 otherwise.
Using this binary image, the connected components are computed for each strip, where there is a dierence in pixels. At the end, the connected components for dierent strips which are overlapping or have common edges are merged. Finally, in the output image, the remaining connected components identifying the moving targets are represented with bounding boxes.

Figure 1.8 [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF] gives an overview of the main components of the ΣC dataow graph for the motion target application. The network is described from left to right.

The tasks io belonging to a special class of ΣC agents provide a way to handle the input/output. The left ones are in charge of reading two consecutive frames, of height H and width W , and the right one is displaying the current image with the targets identied by surrounding rectangles. The next tasks s are data distribution agents of type Split which take as input the current, and respectively, the previous image, and divide them into N B S strips (in a round robin fashion). Production of these system agents is given by the N B S parameter and the application size directly depends on this level of granularity, the further treatments being realized for each strip. As such, the following tasks ∆ are computing the absolute dierence for pixels by strips which is then used by σ to compute the standard deviation by macro-block and select the minimum for each strip. The outputs of ∆ agents serve also as inputs for the t agents to construct a binary version of each strip which is further employed by the c tasks to detect connected components by strip. First m vertex representing a subgraph (including a join system agent and a user agent dening a median lter) compute the minimum deviation between all strips and broadcast the result to all strips. The second m vertex is another subgraph for merging together the bounding boxes found for each strip. The empty vertex is the Dup agent, used to duplicate data over all output channels. Designing and implementing a parallel application using a dataow programming language, as the one dened in previous sections, is not enough for running it on an embedded system. The dataow computation only species the application constraints and we need an execution model for a formal specication on how to execute the dataow on an embedded platform. It is the role of the compiler chain to connect the dataow application to the execution model consisting of several steps: parallelism reduction, scheduling, etc. The dierent steps a compilation process is composed of will be illustrated through ΣC example.

As shown in Fig. 1.9 [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF], the compilation process for ΣC language is organized into four passes. It is important to remark that the code is generated once for all and it is not intended to be modied unless by substitution and only by a C preprocessor.

Compilation of the parallelism

The purpose of the second pass, the ΣC middle-end, is to instantiate and connect the agents, by executing at compile time the corresponding codes generated by the rst pass. The C code, calling adapted APIs, is compiled and executed on the workstation for building the data structure representing the network of processes and generating the data for the agent instances.

This pass also involves a certain number of manipulations on the network of processes. Once the construction of the application graph is complete, parallelism reduction techniques are applied such as the application is rendered compliant with an abstract specication of the system resources.

The parallelism reduction makes use of pattern detection and substitution, by replacing some parts of the instantiation graph with another subgraph. The modications on the graph include instance and port creation, deletion or modication and are allowed as long as they do not modify the semantic of the application or the user code. For more details on this compiler extension for dataow languages, please refer to [START_REF] Cudennec | Parallelism reduction based on pattern substitution in dataow oriented programming languages[END_REF], [START_REF] Carpov | Throughput constrained parallelism reduction in cyclo-static dataow applications[END_REF]. The built-ins system agents (split, join, dup etc.) are further combined and transformed into shared memory buers or NoC transfers. During this stage, it is possible to verify the hierarchical coherence of the agents (for each subgraph verify that its composition implements correctly its state machine) and to perform a safe computation of a dealock-free lowest bound for the buers sizes of the links (see [START_REF] Sirdey | A linear programming approach to general dataow process network verication and dimensioning[END_REF]).

At the end of this pass, it is already possible to make a rst execution based on POSIX primitives which allows a functional adjustment of the application code, independent of the architecture.

Resource allocation

The third pass is in charge of resource allocation (in the larger sense). First, it supports a dimensioning of communication buers taking into account the execution times of the tasks and the application requirements in terms of bandwidths (non functional constraints). Next, in order to realize a connection with the execution model, it constructs a folded (and thus, nitely representative) unbounded partial ordering of task occurrences (see [START_REF] Galea | Méthode de cadencement d'applications ot de données cyclostatiques[END_REF] for details). This step consists in computing a vector giving, for each agent, the number of occurrences needed for reaching back the initial state. This vector is the basis of an execution cycle which can be repeated innitely in bounded memory. Then, the vector can be used to realize a rst symbolic execution taking into account the partial ordering of tasks occurrences and a second execution which adds to the partial ordering the dependences between production and consumption.

This pass is also responsible of placement followed by routing. Informally, the objectives are: grouping together (under capacity constraints for each cluster of the architecture) tasks which communicate the most, mapping these groups of tasks to the clusters (with a distance criterion) and, nally, computing routing paths for the data traversing the NoC. As such, this step implies the resolution of several discrete optimization problems, which form the object of the present study and which will be presented more in detail in the sequel.

In order to reach an appropriate level of performance, the resource allocation can be performed in a feedback-directed fashion. Certain data (e.g. temporal), characteristic to the application, can be obtained through measuring and simulation and reintegrated to the instances of the problems to solve for obtaining results of better quality. Other parameters can also be evaluated through static analysis.

Runtime generation and link edition

The last pass, the ΣC back-end, is responsible of generating the nal C code and the runtime tables. Based on the partial orderings from the third pass, the runtime tables make the link with the execution model, by setting parameters of the system such as the conguration parameters of the NoC or the data structures describing the inter-task communication buers. Also, during this stage and using C back-up compiler tools, are realized the link edition and the loadbuild.

1.5 Research Motivations 1.5.1 NP-dicult optimization problems related to manycores

As seen in the previous sections, the compilation process of an application for a massively parallel architecture is becoming rather complex and requires solving a number of dicult and large-size optimization problems. Nowadays, the compiler design implies the application of operations research techniques not only to the so-called back-end (by solving optimization problems such as buer sizing and instruction scheduling e.g. [START_REF] Hanen | Cyclic scheduling on parallel processors : An overview[END_REF], [START_REF] Bilsen | Cyclo-static data ow[END_REF], [START_REF] Lemerre | Equivalence between schedule representations : Theory and applications[END_REF]) but also more upward and all the long of the compilation process, in order to eciently allocate and exploit the inter-related resources oered by parallel architectures. Between the more recent optimization problems, we can mention the placement/routing for multi-cores or the construction of a partial order under throughput constraints application (e.g. [START_REF] Galea | A parallel simulated annealing approach for the mapping of large process networks[END_REF], [START_REF] Galea | Méthode de cadencement d'applications ot de données cyclostatiques[END_REF]). As such, developing and testing optimization techniques taking into account uncertainty for this eld seem benecial and even necessary. However, we notice only a few studies which take into consideration parameter variations and apply the techniques of optimization under uncertainty to the embedded domain (e.g. [START_REF] Carpov | Memory bandwidth-constrained parallelism dimensioning for embedded many-core microprocessors[END_REF], [START_REF] Lee | Online robust optimization framework for QoS guarantees in distributed soft real-time systems[END_REF], [START_REF] Lombardi | Stochastic allocation and scheduling for conditional task graphs in multiprocessor systems-on-chip[END_REF]).

In order to conceive and develop methods of optimization under uncertainty which are adequate to the domain of compilation for manycores, one should rst be able to identify, analyze and, if possible, model the sources of uncertainty specic to this area. As such, one of the research questions to which we are trying to provide elements of response in our study is related to the uncertainty sources and we proceed in the next section with a qualitative analysis of these ones, with a particular emphasis on the execution times.

Also, when designing or implementing an optimization algorithm, one has to compute the computational complexity of the examined problem, in general in function of the size of input data. Since another important characteristic of the optimization problems related to compilation for manycores is their large size and, as we show in the next chapter, dealing with uncertainty for the input parameters increases the complexity, the approximate algorithms seem a more appropriate choice to tackle these problems.

Another important issue we must take into account when conceiving optimization methods for dimensioning embedded systems is their response-time requirements.

For safety-critical applications (hard real-time systems) like nuclear power plant control or ight management systems, all the timing constraints have to be met which often go along with a worst-case approach. Even if it leads to an over-sizing of the systems, worst-case approach is favored since missing any deadline is highly risky and unacceptable. Our methodology is more oriented towards the dimensioning of soft real-time systems, such as multimedia applications (video encoding, virtual reality etc.) for which missing a deadline from time to time is acceptable, resulting only in a decrease of the quality of service. Almost all of the probability based studies related to real-time systems are intended for this kind of systems. Thus, even if the dimensioning is no longer guaranteed in all cases, we admit acceptable deviations and in consequence, avoid oversizing (expensive in terms of hardware) or undersizing (expensive in terms of reliability). Moreover, for a system already dimensioned, we could estimate the level of robustness and specify deviation scenarios for which the system is no feasible or scenarios which could be acceptable.

Furthermore, we are projecting our proposed methodology in the framework of iterative compilation and we consider that a rst validation of the embedded application was realized a priori, through for example a simulation or a rst execution on the target architecture. The analytical technique most often used in practice for validation of an embedded system remains testing, with the scope of checking for the existence of certain properties or qualities. A systematic procedure for testing Most of the approaches for optimization under uncertainty make assumptions about the underlying probability model or use simulations without making a true connection and without a thorough validation with the experimental data. Instead, one of the central ideas of the methodology we propose (see chapter 2), using an oracle for computing the probability and for deciding of the feasibility of a solution, is to take advantage and to rationally exploit the observations of the random data.

As such, we suppose a pre-treatment step, in which the observations are analyzed and, in function of the complexity of the modeling process, further behavior is decided. The purpose of this pre-treatment is to build a probability model and estimate its parameters without forgetting to validate it, according to the steps described previously. If the estimated distribution associated to the model is too complicated to be analytically described or computed, and thus it is necessary to employ simulation methods to approximate it, it is better for the overall computation time that the oracle directly exploits the sample in deciding the solution feasibility.

Instead, if the estimated distribution of the model has a nice analytical form which integration demands a computational time clearly inferior to the time the oracle requires for directly exploiting the sample, it is more appropriate for our approximation method to rely on the model.

Before presenting in detail the methodology, let us now return to the uncertainty data of our context application, in particular the execution times.

Characterization of the uncertainties in the context of manycores 1.5.3.1 Overview of the execution times

There are two main sources of uncertainty related to the execution times of embedded systems:

1. intrinsic dependency on the data. Since usually the computation code of an application depends on the input data, there are several treatments which could be executed by the application, translating into dierent data-dependent paths, with potentially dierent execution times.

2. extrinsic uncertainty due to architecture characteristics. Variations of execution times are also related to the speculative components (such as caches, pipelines or branch prediction) of modern hardware architectures on which the application is executed.

These sources of uncertainty are not independent and one must take into account both execution paths and hardware mechanisms.

As described previously, we assume that the embedded application consists of a number of tasks or agents, which work together to achieve the required functionalities. In Current approaches for determining bounds or estimates of the execution times are divided into static methods and measurement-based methods. Methods belonging to rst class compute bounds on the execution time, without relying on executing the code on real hardware or on a simulator. They analyze the task code, using some (abstract) models for the hardware architecture, in order to cover the set of all possible control-ow paths and obtain upper bounds. The disadvantage is that they rely on the specication of a processor model and behavior resulting in imprecise results and often overestimated bounds. However, static analysis can be realized without running the program and as such, it avoids implementing complex simulations of the target system. Another important advantage of static methods is their safety, the bounds they produced being safe and guaranteed to be always superior to the execution time. As such, they are used for safe scheduling analysis in hard real-time systems. Such static approaches are described in [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF], [START_REF] Wilhelm | The worst-case execution-time problem : overview of methods and survey of tools[END_REF]. The second class of methods, based on measurements execute the application or parts of it on the target architecture or a simulator for a given set of inputs. Thus, they can take the measured times and derive or give a distribution of the minimal and maximal observed times but they are not safe since some context-dependent execution paths could be missed. Because they do not need to model the processor behavior, they are simpler to apply to new target architectures and they are able to produce more precise estimates for BCET and respectively WCET, especially for complex processors and applications.

Amongst the issues the above approaches are analyzing we can enumerate: the data-dependent control ows, the context dependence of execution times or the timing anomalies. The control-ow analysis (CFA) applied to the task's controlow graph (data structure describing the set of all execution paths) determines information about the possible ow of control through the task (infeasible paths, execution frequencies of the dierent paths, etc.) and it has been called a highlevel analysis. For modern processors exhibiting caches and pipelines, the context independence of individual instructions is no longer true since the execution times of each individual instruction may vary by several orders of magnitude in function of the state of the processor. For a task containing two successive code snippets A and B, the execution time of B depends on the execution state produced by the execution of A. As such, there is a need for a so-called low-level analysis or processbehavior analysis to study the behavior of components such as pipelines [START_REF] Healy | Integrating the timing analysis of pipelining and instruction caching[END_REF], memory caches [START_REF] Louise | A new paradigm for cache related wcet computation[END_REF], [START_REF] Mueller | Timing analysis for instruction caches[END_REF] and branch prediction [START_REF] Carpov | Scheduling for memory management and prefetch in embedded multi-core architectures[END_REF]. Timing anomalies aect modern powerful processors [START_REF] Lundqvist | Timing anomalies in dynamically scheduled microprocessors[END_REF] because of the inuence of one instruction on the global execution time of the whole task. One of the anomalies is caused by speculation of the cache on the results of conditional branches. Another type of timing anomalies are scheduling-caused and usually occur when a set of instructions, with potential dependencies between them, can be scheduled dierently on the pipeline units or other hardware resources. In function on the chosen scheduling, executing the instruction or pipelining takes dierent times.

For a detailed overview and survey of methods and tools for estimating WCET, we refer the reader to [START_REF] Wilhelm | The worst-case execution-time problem : overview of methods and survey of tools[END_REF].

Estimating execution times distributions

While the methods for estimating bounds for execution times are getting more and more complex, by also taking into account the speculative behavior of the target architecture, they remain justied mainly for hard real-time systems. Instead, for soft real-time systems, there are more and more studies based on probabilistic analysis and approaches for scheduling (e.g. [START_REF] Burns | A probabilistic framework for schedulability analysis[END_REF], [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF], [START_REF] Manolache | Memory and time-ecient schedulability analysis of task sets with stochastic execution time[END_REF]) considering that the execution times of the tasks follow probability distributions.

The problem of estimating the execution times consists in predicting the execution time of a task on a variety of machines in function of the data set and with a high level of accuracy. The existing solutions to this problem can be divided into three main classes: code analysis [START_REF] Reistad | Static dependent costs for estimating execution time[END_REF], analytic proling [START_REF] Freund | Optimal selection theory for superconcurrency[END_REF], [START_REF] Yang | Estimation of execution times on heterogeneous supercomputer architectures[END_REF], [START_REF] Khokhar | Heterogeneous computing : Challenges and opportunities[END_REF] and statistic prediction [START_REF] Iverson | Run-time statistical estimation of task execution times for heterogeneous distributed computing[END_REF], [START_REF] Devarakonda | Predictability of process resource usage : a measurement-based study on unix[END_REF].

An execution time estimate found by analysis of the source code of a task is typically limited to a specic class of architectures and a particular code type.

Consequently, code analysis is not very adapted to treat heterogeneous computing.

The proling technique, rst presented by Freund [START_REF] Freund | Optimal selection theory for superconcurrency[END_REF], determines the composition of a task in terms of primitive code types. Code proling data is then combined with benchmark data (obtained on each machine and measuring the performance for each code type). The main disadvantage of this type of methods is that they cannot determine the variations in the input data set. The third category, the statistical prediction algorithms, makes predictions from previous observations. Each time a task executes on a machine, the execution time is measured and added to the set of past observations. The quality of estimation depends on the size of the set of observations. The advantage is that these methods can compensate for parameters of the input data and the machine type without any supplementary information about the internal code or the machine.

A recent work [START_REF] Mazouz | Study of variations of native program execution times on multi-core architectures[END_REF] is going further with the analysis, by studying the variations of execution times on multi-core architectures. The experimental work is conducted on samples from two benchmarks SPEC CPU, large sequential applications and SPEC OMP2001 benchmarks, OpenMP applications, by executing each program 30

times on an 8 cores Linux machine with the same train input data each time. The normality check (using the standard Shapiro-Wilk test) for both benchmarks proved that the distribution of execution times is not a Gaussian function in almost all cases.

Also, contrary to sequential SPEC CPU applications, OpenMP applications have a more important variability of execution times. By executing 30 times several applications from the SPEC OMP benchmark on dierent software congurations (sequential and multi-threads), the study shows that if the sequential and single threaded versions do not have important variations, when using a larger thread level parallelism (more than 1 thread), the overall execution times decrease with a deeper disparity. More, the mean condence intervals (obtained with Student's test)

are not always tight.

Execution times: a qualitative analysis and basic examples

Even if it is reasonable to assume, in embedded computing, that the execution time have probability distributions of bounded support (no innite loops), we have to cope with the fact that the distributions are intrinsically multimodal.

Let us give some simple examples. For example, for the computing kernel in

for i = 1 to n do if condition then S 1 else S 2
end if end for complicated application like X264 encoder clearly shows that the distribution of execution times is dicult to model and that it is multimodal. Fig. 1.11 shows the envelope of executions times for each frame when the X264 is executed on a Linux machine, taking as input a video benchmark of size 1280×720, with 24 frames per second.

Hence, it is dicult to model these probabilities laws through usual distributions such as the normal or uniform ones, which are unimodal. Furthermore, in the case Figure 1.11: Envelope of execution times for frame treatment in a X264 encoder of a process network, we cannot overlook the problem of dependency between these random variables. An easy example consists in the target tracking pipeline for which the execution times of each of the pipeline elementary tasks depend, to a certain degree, on the number of eectively treated targets. In Table 1.3, another example is presented consisting of two elementary tasks both depending on same input data d, dicult to characterized, and each task having two modes for its execution times. As such, the execution time of task T 1 is dependent to a certain degree of execution time of task T 2. if f (d) then

S 1 else S 2 end if if g(d) then S 3 else S 4
end if

Conclusion

Besides explaining more in details the motivations which conducted our research, this introductory chapter also serves in positioning the context and presenting some fundamental concepts related to manycore systems and dataow programming (see also [START_REF] Stan | L'apport de l'optimisation sous incertitudes pour les systèmes temps réel embarqués[END_REF] for more details on the research motivations).

Also, a qualitative analysis of uncertainty sources for manycore applications is presented and, as the previous section emphasizes, it is appropriate to assume that the execution times are random variables characterized by complicated multimodal joint distributions, presumably better dened as unions of orthotopes rather than, a Gaussian or even a mixture of Gaussians.

We do not build further on this assumption for our non parametric robust binomial approach. Since the choice of a probability model seems dicult, the robust binomial approach we propose in chapter 2 is non parametric with almost none or few assumptions on the distributions of the uncertain data. After an introduction in which are presented the existing techniques of solving optimization programs under uncertainty and the diculties in solving such problems, the next chapter explains in detail the robust binomial approach and possible extensions. The idea of this generic non parametric method is simple and rst occurred with the desire to conceive algorithms which match the research context we introduced in this chapter, that is compilation of dataow applications for manycore systems.

As described in section 1.5, the optimization problems related to compilation for manycore systems are NP-dicult problems, characterized by their large sizes and manipulation of uncertain data, dicult to fully describe but for which we could dispose of experimental samples.

In Chapter 3 and 4, the robust binomial approach was applied in order to solve two of the optimization problems arising in the compilation process: the stochastic partitioning of process networks and the more general problem of placement and routing of process networks (which, for a ΣC, corresponds to the third pass of compilation). A general introduction on the practical relevance of taking into account uncertainty into an optimization problem and dierent ways of expressing uncertainty are given in section 2.1. Next section focuses on chance constrained programs: after exposing the algorithmic diculties encountered when facing this kind of problems, a classication of related studies is proposed and each category is presented more in details.

The principles of the non-parametric method we developed, entitled robust binomial approach, are presented in section 2.3. Based on statistical hypothesis tests, the robust binomial method nds approximate solutions to chance-constrained problems (optimization programs with uncertainty aecting the constraints, see details below), guaranteed with a given reliability level 1 -ε and a condence level of 1 -α (both ε, α ∈ (0, 1)). In order to eciently nd (N S, α)-statistically admissible solutions (notion dened in section 2.3.4), the robust binomial approach can be combined with existing (meta)heuristic, by modifying the oracle deciding the feasibility of a possible solution. The general methodology of adapting an existing algorithm in order to solve the stochastic version of a problem as well as an example for bin packing are presented in section 2.3.5. Possible extensions for the problems with more initial probability levels or random data in the objective functions are given in the last section.

2.1 What is it meant by optimization under uncertainty?

2.1.1 From a deterministic problem to its stochastic counterpart...

A large majority of algorithms and methods conceived for solving combinatorial optimization problems suppose that input data are known precisely. As such, a generic way of mathematically representing an optimization problem is as follows:

min x g (x) s.t. G i (x, ξ i ) ≤ 0 , i ∈ {1, . . . , m} (2.1)
where x ∈ R n is the design parameter, g (x) ∈ R is the objective function and we have m inequality constraints G(x, ξ) ∈ R with ξ = (ξ 1 , . . . , ξ m ) a m-dimensional parameter vector.

However, for real-world optimization problems, one might ask if the formulation above is as general and practical as it seems since the design space is often characterized by data which are uncertain or inexact.

Beginning with the seminal works of Dantzig [START_REF] Dantzig | Linear programming under uncertainty[END_REF], Charnes and Cooper [START_REF] Charnes | Chance-constrained programming[END_REF],

Miller and Wagner [START_REF] Miller | Chance constrained programming with joint constraints[END_REF], Bellman and Zadeh [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF], optimization under uncertainty remains one of the most active domains of research, both in theory and algorithms, and thanks to recent studies, there is an increased regain of interest. The recent case study of Ben-Tal and Nemirovski [START_REF] Ben-Tal | Robust optimization : Methodology and applications[END_REF] on a collection of 90 problems from NETLIB library showed that systems optimized in the classical sense (see formulation 2.1) can be very sensitive to small changes and that only 1% perturbation of the data can severely aect the feasibility properties of deterministic solutions.

One such example from [START_REF] Ben-Tal | Robust optimization : Methodology and applications[END_REF] is an antenna design problem in which only 5% errors can entirely destroy the radiation characteristics established during nominal optimization. Another example analyzed in [START_REF] Ben-Tal | Robust optimization : Methodology and applications[END_REF] is a LP program PILOT4 from Netlib library with 1000 variables and 410 constraints, constraint j being: with A j ∈ R n the line j of the constraints matrix and x ∈ R n . This kind of ugly coecients could model certain technological processes and we could make the hypothesis that they cannot be specied with high accuracy and thus, they are uncertain and have inaccurate last digits. For the optimal solution x * when the uncertain coecients are perturbed within 0.01% margin by independent random perturbations, distributed uniformly, the constraint is violated by at most 150% of the right hand side with a probability of 0.18. In the worst case (all uncertain coecients are perturbed with 0.01%), the constraint is violated in x * by 450% of the right hand side.

[A j ] T x ≡ -
Let us give another simple example from [START_REF] Hong | Sequential convex approximations to joint chance constrained programs : A Monte Carlo Approach[END_REF] illustrating that the optimal solution of problem 2.1 might actually be unfeasible if uncertainty on the parameter

vector ξ is ignored. Let ξ = (ξ 1 , . . . , ξ m ) with ξ 1 , . . . , ξ m , m independent observations of a standard normal distribution, x ∈ R, g (x) = x and G i (x, ξ) = ξ i -x, for all i = 1, . . . , m.
If the uncertainty on the parameter is ignored and ξ is substituted by the expected value E (ξ) in problem 2.1, then the optimal solution is obtained for x * = 0. However, the probability that x * = 0 is a feasible solution equals to

P{G i (x * , ξ i ) ≤ 0 , ∀i ∈ {1, . . . , m}} = P{x * ≥ ξ i , ∀i ∈ {1, . . . , m}} = 0.5 m
As the value of m increases, this probability becomes very weak (e.g. for m = 7, it is less than 0.01).

As shown by the previous case studies, taking into account uncertainty aecting the parameters required for optimization is necessary in order to nd optimal solutions which are feasible in a meaningful sense. Nevertheless, as we will point out in the next section, optimizing under uncertainty induces several supplementary diculties and a crucial point is the way uncertainty is formalized and the underlying assumptions.

Uncertainty setting

When formulating an optimization problem under uncertainty two aspects need to be dened: the way uncertainty is expressed and the dynamicity of the problem (or the time when uncertain data is revealed with respect to the time when decisions are taken). [START_REF] Bianchi | A survey on metaheuristics for stochastic combinatorial optimization[END_REF] proposes a classication of optimization problems under uncertainty in function of uncertainty and dynamicity, shown in Figure 2.1.

The classical Deterministic Combinatorial Optimization Problems (DCOP) correspond to the case of perfect knowledge about the data and, since we are supposing all information is known at decision stage, they are static models.

In Stochastic Combinatorial Optimization Problems (SCOP), it is assumed that uncertain information can be described by random variables which can be characterized by probability distributions. Static SCOPs are a priori optimization problems where the decisions are taken and optimal solutions are found in the presence of randomness, at one single step, before the actual realization of the random variables.

Dynamic SCOPs consider that decision cannot be made until random variables are revealed and associated random events have happened. As such, decisions are taken after random events occur in a single stage, in the case of simple recourse problems or in several stages, for multi-stage recourse problems. For both static and dynamic models, there are decisions and observations of the random variables, the order of succession being given by dierent schemes: for static models, rst decision, then observation while for dynamic problems, at least one decision is preceded by at least one observation. Another way of representing uncertainty in optimization problems, although minor in the related literature, is by fuzzy quantities for random parameters and by fuzzy sets for constraints to which, instead of probabilities, there are associated possibilities. For more details about fuzzy approaches, we refer the interested reader to [START_REF] Bellman | Decision-making in a fuzzy environment[END_REF] and [START_REF] Liu | Fuzzy random chance-constrained programming[END_REF].

Robust optimization does not need any knowledge about the probability distribution of random data and instead uncertain information is set based. Usually, the decision making process searches for solutions that are feasible for any realization of the uncertainty in the given set. Robust optimization methods are gaining increasing attention lately with recent studies (e.g. [START_REF] Bertsimas | The price of robustness[END_REF], [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], etc.) showing the theoretical and practical potential of such approaches as well as making connections with stochastic programming.

The top category from Fig. 2.1 corresponds to Pure Online problems, for which the output is produced incrementally, without knowing the complete input and without making any assumption on the new data. The performance is evaluated against the optimal solutions found by an abstract competitor, with a perfect knowledge about past and future data.

Since, in the present manuscrit, we are concentrating on static stochastic programs with uncertainty aecting the constraints, let us provide more background about the general structure, the diculties in solving this type of problems and the existing resolution techniques.

2.2 Chance constrained programming

Problem statement

The general form of the chance constrained problem we consider here is the following :

min x g (x) (CCP) s.t. P (G(x, ξ) ≤ 0) ≥ 1 -ε
where x ∈ R n is the decision variable vector, ξ ∈ Ω -→ R D represents a random vector and g : R n -→ R is the objective function. We suppose that there exists a probability space (Ω, Σ, P), with Ω, the sample space, Σ, the set of events, i.e. subsets of Ω, and P, the probability distribution on Σ. G : R n × R D -→ R m is the function for the m constraints, 0 ≤ ε ≤ 1 is a scalar dening a prescribed probability level and P(e) of an event e is the probability measure on the set Σ.

This type of problem, where all constraints should be satised simultaneously with a probability level of at least 1 -ε, is known in the literature as a joint chance constrained program. Another variant of optimization problems with uncertainty aecting the constraints is the separate chance constrained program in which dierent probabilities levels ε i can be assigned to dierent constraints:

min x g (x) s.t. P (G i (x, ξ) ≤ 0) ≥ 1 -ε i , ∀i ∈ 1, . . . , m (2.2)
The dierence between (CCP) and (2.2) formulations is that in separate chance constraints the reliability is required for each individual feasible region while in joint chance constraints the reliability is assured on the whole feasible space. Even if appealing for their more simple structure, the separate chance constrained programs have the important drawback of not properly characterizing safety requirements [START_REF] Prékopa | Stochastic Programming[END_REF]. As such, while separate chance constraints could be used in the case when some constraints are more critical than others, joint chance constraints seems a more appropriate choice for guaranteeing an overall reliability target for the system.

Remark on robust optimization As described briey previously, robust optimization constitutes an attractive alternative to chance constrained programming for which uncertain parameters are characterized through a set of possible events.

The main criticism of classical robust approaches (e.g. the so called max-min or worst-case approach, the regret maxmin, etc) is their over-conservatism since they are searching for solutions that are feasible for all possible events from the uncertainty set. As such, the obtained solutions are often of large cost, being guaranteed even for events with a low probability to occur. Recent approaches, more exible, try to rectify this drawback, by making particular assumptions about the uncertainty set of the parameters and proposing deterministic counterparts to the original robust problem. For example, Ben-Tal and Nemirovski [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF] propose particular relaxations of original optimization problems transforming linear and quadratic robust programs into deterministic second order cone programs and respectively semi-denite programs, under the assumption that the uncertainty set is ellipsoidal.

Bertsimas and Sim [START_REF] Bertsimas | The price of robustness[END_REF] model uncertain data as symmetric and bounded random variables and give a linear deterministic counterpart for robust linear problems with J parameters subject to uncertainty in which at most Γ ≤ J uncertain parameters are allowed to vary. Quite often, even if these transformations provide deterministic convex approximations, the obtained equivalent belongs to a class of complexity more complex than the one of the original program.

Even if robust methods construct solutions which are immune to data uncertainty, in general the quality of the solution is not assessed with probabilistic considerations as in the case of chance constrained programming. However, from our perspective, the probability of constraints to respect a given reliability target is a more intuitive notion, often easier to set for a decision maker.

Moreover, allowing even a very small probability ε for constraint violation can lead to a signicant improvement of the optimal solution. The following example, similar to the one from [START_REF] Calaore | Uncertain convex programs : Randomized solutions and condence levels[END_REF], illustrates the fact that, in some situations, the optimal objective obtained using a chance constrained model can be signicantly dierent from the optimum attained by solving the robust approach. Let compare the optimal solution of the robust problem EX_RCP with the one of its stochastic equivalent program EX_CCP from Table 2.1, when the uncertainty set δ is uniformly distributed in [0, 1] and

f (x, δ) = 10 7 -x if δ ∈ [0, 10 -7 ] -x if δ ∈ (10 -7 , 1]
The optimal solution of the EX_RCP formulation is equal to 10 7 . Or, when setting

{x : f (x, δ) ≤ 0}
a probability level ε > 10 -7 , the probabilistic equivalent EX_CCP will not take into account the violation of constraints for which the uncertainty measure is smaller than ε and thus, the objective found will be equal to zero.

In the following, we will describe only the robust approaches which are accompanied by probabilistic considerations.

Algorithmic challenges

Introduced by the seminal works of Charnes and Cooper [START_REF] Charnes | Cost horizons and certainty equivalents : An approach to stochastic programming of heating oil[END_REF] and Miller and Wagner [START_REF] Miller | Chance constrained programming with joint constraints[END_REF], chance constrained programs have been extensively studied in the literature of stochastic optimization. Since probabilistic constraints arise naturally in various contexts, there are a wide range of potential applications for this kind of programs, from engineering design to nance and management. For more details on concrete applications of CCP, please refer to [START_REF] Prékopa | Stochastic Programming[END_REF].

However, as one may expect, chance constrained optimization problems are inherently dicult to address and although this class of problems have been studied

for the last fty years, there is still a lot of work to be made towards practical resolution methods. There is not a general method of resolution for chance constrained programs, the choice of the algorithm depending on the way random and decision variables interact. Basically, the major diculties associated to joint CCP are:

• Convexity of chance constraints.

For joint chance constrained programs, having this structural property would allow using resolution tools from convex optimization eld and thus, nding a global optimal solution. However, the convexity of the feasible set for the probabilistic constraints from CCP program depends not only on the convexity of function G in x but also on the distribution of the random parameter ε. In general, the distribution function of random variables can never be concave or convex. Worse, even if each G i (x, ε) is convex, the union of all constraints may not be convex. Let us give a simple example, inspired from [START_REF] Sahinidis | Optimization under uncertainty : State-of-the-art and opportunities[END_REF], showing that even when the functions G i are linear, the overall program correspond to a non-linear non-convex problem. min x g (x) Even if any (x 1 , x 2 ) from S 1 is feasible for the whole problem and again, any point from S 2 is feasible, the complete set of the problem is dened as the union of S 1 and S 2 which turns out to be non convex (as shown in Fig. 2.2).

s.t. P 2x 1 + x 2 ≥ b 1 x 1 + x 2 ≥ b 2 ≥ 0.5 x 1 ≥ 0 , x 2 ≥
• Evaluation of the probabilistic constraints. In order to evaluate, for a given x, the probability that G(x, ξ) ≤ 0, we need to know the probability distribution of the random vector ξ. So, a rst problem raises, the one of modeling random data in practical applications when the involved distributions are not always known exactly and have to be estimated from historical data. Another sensible point is the choice of the reliability level ε which is dicult to be established in absence of any knowledge about the underlying probability distribution. The second problem is numerical since typically ξ is multidimensional and there are no ways to compute exactly and eciently the corresponding probabilities with high accuracy. As such, the multivariate distribution of ξ, if given, is often approximated by Monte-Carlo simulations or bounding arguments.

Another crucial aspect when designing algorithms for CCP problems is whether the distribution is continuous or discrete and also if the components of the random data are independent. One of the biggest challenges arises for programs in which decision variables and random data are correlated and cannot be decoupled.

Convexity studies

Theoretical approaches [START_REF] Charnes | Chance-constrained programming[END_REF], [START_REF] Miller | Chance constrained programming with joint constraints[END_REF],

Particular assumptions on the distribution [START_REF] Prékopa | Stochastic Programming[END_REF], [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF] Robust optimization Relatively simple to apply [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], [START_REF] Bertsimas | The price of robustness[END_REF], [START_REF] Chen | A robust optimization perspective on stochastic programming[END_REF], [START_REF] Calaore | The scenario approach to robust control design[END_REF], [START_REF] Calaore | Uncertain convex programs : Randomized solutions and condence levels[END_REF], [START_REF] Campi | A sampling-and-discarding approach to chanceconstrained optimization : Feasibility and optimality[END_REF], [START_REF] Xu | Optimization under probabilistic envelope constraints[END_REF] [94], [START_REF] Ben-Ameur | Routing of uncertain trac demands[END_REF], [START_REF] Ben-Ameur | Robust routing and optimal partitioning of a trac demand polytope[END_REF], [START_REF] Gaivoronski | Knapsack problem with probability constraints[END_REF] Approximations and sampling Compute bounds and approximate solutions [START_REF] Pagnoncelli | Sample average approximation method for chance constrained programming : Theory and applications[END_REF], [START_REF] Nemirovski | Convex approximations of chance constrained programs[END_REF], [START_REF] Rockafellar | Optimization of Conditional Value-at-Risk[END_REF],

Usually computationally demanding [START_REF] Hong | Sequential convex approximations to joint chance constrained programs : A Monte Carlo Approach[END_REF], [START_REF] Ben-Tal | On safe tractable approximations of chanceconstrained linear matrix inequalities[END_REF], [START_REF] Dentcheva | Concavity and ecient points of discrete distributions in probabilistic programming[END_REF], [START_REF] Dentcheva | Bounds for probabilistic integer programming problems[END_REF], [START_REF] Luedtke | A sample approximation approach for optimization with probabilistic constraints[END_REF], [START_REF] Pal | A genetic algorithm based stochastic simulation approach to chance constrained interval valued multiobjective decision making problems[END_REF], [START_REF] Li | Robust model predictive control under chance constraints[END_REF] (Meta)Heuristics Use of precedent techniques for computing distribution [START_REF] Tanner | A general heuristic method for joint chanceconstrained stochastic programs with discretely distributed parameters[END_REF], [START_REF] Loughlin | Chance-constrained genetic algorithms[END_REF], [START_REF] Beraldi | Beam search heuristic to solve stochastic integer problems under probabilistic constraints[END_REF], [START_REF] Bertsimas | Robust optimization with simulated annealing[END_REF], [START_REF] Aringhieri | Solving chance-constrained programs combining tabu search and simulation[END_REF]

Convexity studies

Some of the earliest studies from stochastic optimization were interested in establishing conditions in which the probabilistic distributions and the functions dening the constraints dene a convex feasible space. As such, almost all exact solutions existing for chance constrained programs require a continuous distribution and a convex structure of the problem.

Charnes and Cooper [START_REF] Charnes | Chance-constrained programming[END_REF] studied the case of single chance constraints (m = 1) when the continuous random variables are only on the right hand-side of the constraints (i.e. completely decoupled of the decision variables) and proposed a deterministic nonlinear equivalent problem. Also, when m = 1 and the randomness is continuous and on the left hand-side, Kataoka [START_REF] Kataoka | A stochastic programming model[END_REF] proved that these chance constrained programs are convex for independently normal distribution and ε ≥ 0.5.

For joint chance constrained programs with more than one constraint, the most dicult case to solve is the one in which the random distributions are aecting the left hand-side. Instead, for random right hand-side parameters, Prékopa [START_REF] Prékopa | Stochastic Programming[END_REF] showed that if the random variables have a log-concave distribution (e.g. the multivariate normal distribution, uniform distribution are log-concave), then the initial probabilistic program can be rewritten as a convex deterministic equivalent problem.

Prékopa also proved that for normal distributed left hand-side parameters, if all covariance and cross-variance matrices for columns or rows are proportional between them, then the problem is convex. A later study of Henrion [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF] gives conditions in which program is convex for left hand-side random parameters normally distributed with independent components.

To the best of our knowledge, existing studies determined convexity conditions only for linear probabilistic constraints with normal distributions in left hand-side or log-concave distributions on the right hand-side.

Robust approaches

Some of the recent studies providing less conservative solutions to robust optimization problems [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF], [START_REF] Bertsimas | The price of robustness[END_REF], [START_REF] Ghaoui | Robust solutions to uncertain semidenite programs[END_REF] have also taken into account probabilistic requirements. Under quite mild assumptions about distributions such as independence of components, known mean symmetry and bounded support, Bertsimas and Sim [START_REF] Bertsimas | The price of robustness[END_REF] and Ben-Tal and Nemirovski [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF] propose deterministic counterparts and probability bounds against constraint violation for robust linear optimization problems.

However, dependence between uncertain parameters is considered in [START_REF] Bertsimas | The price of robustness[END_REF] only for a specic model in which, for the constraint matrix of random parameters, only some coecients from a same row are correlated. The assumption of distributional symmetry is also limiting for many applications, which leads to [START_REF] Chen | A robust optimization perspective on stochastic programming[END_REF], another study proposing a generalization of the approach of Bertsimas and Sim to asymmetric random variables, using forward and backward deviation measures. Still, this approach is not applicable when we don't know the support, even if the rst two moments of the distribution are known. Also, in some situations when the ratio between deviation measures and the standard deviation is large, the approximation found can be too conservative.

Other models, based on the polyhedral properties of the robust problems, with a direct application for the network eld, have been proposed in [START_REF] Ben-Ameur | Routing of uncertain trac demands[END_REF] and [START_REF] Klopfenstein | Optimisation robuste de réseaux de télécommunications[END_REF].

Other exact methods, inspired from the scenario approach coming from the robust optimization eld, consist in supposing that the probability distribution is discrete, as well as having a bounded support. As such, the probability for each scenario is supposed to be known or computable. Under these assumptions, the problem is formulated as a mixed-integer linear program (MILP) and solved with exact approaches.

An example is the model used in [START_REF] Gaivoronski | Knapsack problem with probability constraints[END_REF] for solving the quadratic knapsack problem with probability constraints, solved using semidenite programming. Although the structure is similar to the one used in our robust binomial approach, this model makes the assumption that the distribution of the random constraint matrix m × n is known and has the form A∈Ω p A δ A , with A∈Ω p A = 1, Ω the event set and δ ξ the Dirac distribution centered at point ξ ∈ R m×n . The equivalent to a linear chance constrained program is the following

MILP: min c T x (2.3) s.t. Ax ≤ b + (1 -χ A )L, A ∈ Ω A∈Ω p A χ A ≥ (1 -ε) χ A ∈ {0, 1}, A ∈ Ω.
in which c ∈ R n is the cost vector, x ∈ R n is the decision variable vector, χ A ∈ R m is a vector of binary variables and L is a suitable large problem-dependent constant.

The main drawback of this MILP formulation is that its linear relaxation is often weak.

Other studies (e.g. [START_REF] Calaore | The scenario approach to robust control design[END_REF], [START_REF] Calaore | Uncertain convex programs : Randomized solutions and condence levels[END_REF], [START_REF] Xu | Optimization under probabilistic envelope constraints[END_REF], [START_REF] Campi | A sampling-and-discarding approach to chanceconstrained optimization : Feasibility and optimality[END_REF]) were interested in establishing theoretical links between chance constrained programs and equivalent scenario-based formulations (in [START_REF] Calaore | Uncertain convex programs : Randomized solutions and condence levels[END_REF] they are using the notion of sample instead of scenario). Their corresponding key results consist in providing explicit bounds on the number of scenarios or samples required to obtain the required predened level of probabilistic reliability.

Bounds and approximations

As seen previously, convexity or even quasi-convexity for the probabilistic constraint from problem (CCP) are not always easy to verify and prove. Also, the mixed-integer linear formulation remains interesting to apply when the number of scenarios to take into account is limited. As such, other directions of research consist either in discretization and sampling the distribution or in developing convex approximations.

Between the convex approximations, we can cite the Conditional Value At Risk (CVar) [START_REF] Rockafellar | Optimization of Conditional Value-at-Risk[END_REF], Bernstein approximation [START_REF] Nemirovski | Convex approximations of chance constrained programs[END_REF] or the quadratic approximation of Ben-Tal and Nemirovski [START_REF] Ben-Tal | On safe tractable approximations of chanceconstrained linear matrix inequalities[END_REF]. Usually, the proposed approximations nd feasible but suboptimal solutions to the original problem without any guarantees on their quality. Furthermore, most of them are applicable only on single chance constraints and so, the joint chance constraints have to be approximated by a set of individual chance constraints, making the solutions for approximations more conservative.

1 Another major drawback of these convex approximations are that they require assumptions on the structure of G(x, ξ) and on the stochastic nature of ε. For example, between the assumptions of Bernstein approximation we can enumerate the independence of the random variables ε i and the fact that the moment generating function for the distributions are supposed to be eciently computable. The approximation 1. In order to guarantee the satisfaction of joint constraints, a possible choice consists in using Boole's inequality:

P i G i (x, ξ i ) ≤ 0 ≤ i P (G i (x, ξ i ) ≤ 0) with P (G i (x, ξ i ) ≤ 0) ≥ 1 -ε i , i = 1, . . . , m and i ε i = ε.
programs are commonly solved using non-linear optimization techniques such as the reduced gradient algorithm. If the function approximating the chance constraints is analytically tractable (e.g. for Bernstein approximation), then its evaluation is easy. Otherwise, one must make use of simulation methods such as Monte-Carlo for evaluating these functions (see [START_REF] Rockafellar | Optimization of Conditional Value-at-Risk[END_REF]).

Simulation techniques are also used quite often when a direct evaluation of the feasibility of chance constraints is not possible and the probability has no available closed form. The approximation methods based on sampling are replacing the actual distribution by an empirical distribution estimated by simulation. Originally developed for stochastic programs with objective expressed as an expected value, the Sample Average Approximations (SAA) techniques have been applied for chance constrained programs in [START_REF] Luedtke | A sample approximation approach for optimization with probabilistic constraints[END_REF] and [START_REF] Pagnoncelli | Sample average approximation method for chance constrained programming : Theory and applications[END_REF]. In [START_REF] Luedtke | A sample approximation approach for optimization with probabilistic constraints[END_REF], the sampling method is used to nd upper bounds to the chance constrained problem and solving an equivalent mixed-integer formulation of small size. The paper also provides theoretical results on the size of the sample required in order to guarantee a feasible solution with a high probability for initial problems in which the randomness is in the righthand side. In [START_REF] Pagnoncelli | Sample average approximation method for chance constrained programming : Theory and applications[END_REF] they are establishing conditions of convergence of a solution to the sample approximation of the original problem in function of the sample size and the probability level.

However, the use of Monte-Carlo simulations is too computationally demanding when ε is small and the assumptions made in order to obtain tractable approximations are restricting their applicability to particular cases (e.g. in order to generate Monte Carlo samples, the methods require the full joint distribution).

For solving CCP with random right-hand side, another family of methods which discretize the distribution are based on the notion of p-ecient points [START_REF] Prékopa | The discrete moment problem and linear programming[END_REF], [START_REF] Dentcheva | Concavity and ecient points of discrete distributions in probabilistic programming[END_REF], [START_REF] Dentcheva | Bounds for probabilistic integer programming problems[END_REF]. If F (.) is the cumulative distribution of the random parameters ξ and p ∈ [0, 1], a point v ∈ Z s is called a p-ecient point if F (v) ≥ p and there is no y ≤ v, with y = v such that F (y) ≥ p. While earliest study [START_REF] Prékopa | The discrete moment problem and linear programming[END_REF] focused in reformulating the CCPs into exact deterministic formulations, the more recent ones [START_REF] Dentcheva | Bounds for probabilistic integer programming problems[END_REF] are trying to identify useful p-ecient points.

(Meta)heuristics

Actually, since dealing with uncertainty in optimization problems is highly complicated and dicult, the approaches that guarantee to nd optimal solutions are more appropriate when solving small size instances and even so, they require a lot of computational eort. In contrast, approaches based on heuristics or metaheuristics are capable of nding good and even optimal solutions to problem instances of realistic size, in a smaller computation time.

However, to the best of our knowledge and as pointed in [START_REF] Bianchi | A survey on metaheuristics for stochastic combinatorial optimization[END_REF], a survey on existing metaheuristics for dealing with stochastic combinatorial optimization problems, there are only a few heuristics proposed for solving formulation (CCP), corresponding to no-recourse static programs and with uncertainty aecting the constraints.

In [START_REF] Loughlin | Chance-constrained genetic algorithms[END_REF], the approach consists in using a Monte-Carlo simulation in a genetic algorithm tness function. For each uncertain parameter, a statistical distribution must be obtained or assumed and the sampling is carried out using either Monte-Carlo sampling or Latin Hypercube Sampling. If the estimated reliability of meeting one or more constraints is less than the prescribed probability level, the current solution is penalized. As such, the use of sampling is dierent from our approach and no theoretical guarantees are provided for establishing the number of necessary realizations.

Another method for solving CCPs, suggested in [START_REF] Aringhieri | Solving chance-constrained programs combining tabu search and simulation[END_REF], combines a tabu search heuristic with simulation. The evaluation of the feasibility of a solution is realized using two dierent methods. The rst one consists in randomly generating T values for each random variable and computing the average over them in order to evaluate the constraints. The second method uses the central limit theorem to obtain a normal approximation of a sum of independent random variables. Although the rst method is sample based, no statistical tools are used in order to determine and reduce T , which is the dimension of the sample employed to estimate the constraint feasibility. Furthermore, the second evaluation makes the simplifying assumption of independence of the random variables.

Another tabu search heuristic is proposed in [START_REF] Tanner | A general heuristic method for joint chanceconstrained stochastic programs with discretely distributed parameters[END_REF] for solving joint chance constrained stochastic programs with random parameters having discrete distributions.

The main focus in [START_REF] Tanner | A general heuristic method for joint chanceconstrained stochastic programs with discretely distributed parameters[END_REF] is on exploiting the scenario structure: identifying subsets of scenarios that are more important in nding good solutions, adding or removing scenarios at each iteration step. Though the ideas presented are interesting, it seems that the maintenance of the set of scenarios to work with can be quite computationally demanding.

A beam search heuristic, based on the classical Branch and Bound scheme, is suggested in [START_REF] Beraldi | Beam search heuristic to solve stochastic integer problems under probabilistic constraints[END_REF] for solving chance constrained programs with integer variables and random right-hand side. In order to evaluate which nodes to explore further, the heuristic is using the lower bound of the optimal solution, computed using the notion of p-ecient point. Since the denition of p-ecient point is using the conditional marginal distribution function, this method supposes as known and computable the distribution of the uncertain variables.

2.3 Robust binomial approach (RBA)

Basic ideas and motivations

Most of the studies mentioned above are making assumptions (e.g., existing analytical form of the distribution, independence of the random vector components) which are either restrictive, or dicult to verify or not always adequate to represent the uncertainty of real-life applications.

We have found that, in many real world situations, the probability distribution is not explicitly known or its integration is too dicult. As illustrated in the previous chapter in section 1.5.3, one such example consists of the execution times of medium-grained computer programs which are random variables dicult to fully describe analytically. However, in practice, we have at our disposal some observations for the uncertain data, obtained, for example, when performing tests on the target architecture. These observations can be directly employed in order to construct an equivalent optimization problem, more robust and compatible with the variations of the real data, with the condition that the available sample is suciently representative of the entire distribution 2 .

To the best of our knowledge, the only tractable approximation of the probabilistic constrained programs, which does not impose any restrictions on the structure of the uncertain data 3 , is the one derived from the general scenario approach ( [START_REF] Calaore | The scenario approach to robust control design[END_REF], [START_REF] Campi | A sampling-and-discarding approach to chanceconstrained optimization : Feasibility and optimality[END_REF]).

The optimization problem (CCP) can then be approximated by the convex program:

min x g (x) (RC P N S ) s.t. G(x, ξ(i) ) ≤ 0; i = 1 . . . N S
where ξ (1) , . . . , ξ (N S) is a sample of size N S of independent and identically distributed observations of ξ and ξ(i) is a realization of ξ (i) . Let us recall that ξ is a random vector and that no assumptions are required on its joint probability distribution, in particular with respect to the independence of its components. The scenario approach searches for solutions which satisfy the probabilistic constraints for all the realizations of ξ. The acronym RCP N S refers to the fact that this new formulation is a robust program where, instead of having m constraints, we have N S × m constraints.

As such, the proposed approximation to the original program is often too conservative by nding feasible but suboptimal solutions. Theoretical justication of this approximation scheme can be found in [START_REF] De Farias | On constraint sampling in the linear programming approach to approximate linear programming[END_REF], [START_REF] Calaore | Uncertain convex programs : Randomized solutions and condence levels[END_REF].

Our idea is to take advantage of the experimental data and revisit the scenario approach using elementary tools from statistical hypothesis testing theory and directly exploiting the available sample.

Also, in order to face the computational complexity which is one of the major drawbacks of the sample-based method, we propose a general way of integrating it in almost any heuristic algorithm. In this manner, even if the application case requires a high level of precision for the probability constraint threshold ε (which involves the analysis of a large sample), our approximation remains computationally tractable and, as we shall see in the next section, statistically meaningful.

Our algorithm design methodology consists in leveraging existing heuristics for the deterministic case without destructuring them signicantly (i.e. at small cost in terms of software engineering) and with an acceptable performance hit.

2. An assumption that can be in practice checked, to some extent, using static program analysis

techniques. An assumption which also relies reasonably on the expertise of test engineers in terms of designing validation cases representative of real-world system operation.

3. We impose no restriction in particular with respect to random vector component independence

Statistical hypothesis testing

Before presenting the statistical results on which our method is based, let us introduce the following notation:

x decision vector ξ uncertainty vector p 0 P(G(x, ξ) ≤ 0) ξ (1) , . . . , ξ (N S) i.i.d. random variables corresponding to N S observations of ξ ξ(i) realization of observation ξ (i) χ i

Bernoulli variable equal to 1 if G x, ξ (i) ≤ 0 and 0 otherwise.

So the random variable χ = N S i=1 χ i follows, by denition a Binomial distribution with parameters N S and p 0 (χ ∼ B(N S, p 0 )). Let us now consider a realization χ of χ. If χ (corresponding to the number of times the inequality G(x, ξ) ≤ 0 is satised on a sample of size N S) is suciently large (for instance, larger than k(N S, 1-ε, α)) we say that the constraint P(G(x, ξ) ≤ 0) ≥ 1 -ε is statistically satised.

The value of the threshold k(N S, 1 -ε, α) (to which, for simplicity sake, we will refer, from now on, as k) will be chosen so that the probability we accept the constraint by error is smaller than a xed α, in which case p 0 is strictly smaller than 1 -ε:

P(χ ≥ k) ≤ α (2.4)
For any xed p 0 < 1 -ε, P(χ ≥ k) is smaller than P(χ ≥ k) when χ ∼ B(N S, 1 -ε). So we can choose k such that P(χ ≥ k) ≤ α.

Given x and ε, the parameter α can be interpreted as the type I error of the statistical hypothesis test with the following composite hypothesis:

H 0 : P (G(x, ξ) ≤ 0) < 1 -ε H 1 : P (G(x, ξ) ≤ 0) ≥ 1 -ε
Short reminder on some general notions. Hypothesis testing is a method consisting in deciding, based on a set of observations, if a default position, called null hypothesis (H 0 ), should be accepted or rejected in favor of the alternative hypothesis (H 1 ). The type I error or the signicance level of the test is dened as the risk of rejecting the null hypothesis, when it is in fact true. The roles of the two hypothesis are not symmetrical: the null hypothesis is usually the statement which we do not want to reject if true. Therefore, it is the opposite of what we want to demonstrate:

the research hypothesis H 1 . As such, we want to minimize the type I error. For example, in the diagnostic check of a disease, we want especially to avoid telling a person is in good health when in reality he is sick: in this situation, the null hypothesis should be chosen that the person is sick 4 . Type II error or the β risk is the probability not to reject H 0 whereas H 1 is true. Usually, type II error is more dicult to estimate. Schema 2.3 represents the four possibilities and the corresponding probabilities of matching and mismatching between the decision believed to be the truth and the state of nature which is the actual reality.

H 0 H 1 H 0 1 -α β H 1 α 1 -β
In our case, H 0 corresponds to the hypothesis made by caution, which is (in- tuitively) the hypothesis we wish to reject only if we have statistically signicant reasons to do so. We consider that this is the correct setting if we wish to condently achieve robustness: in a conservative way, by taking small values for α (the type I error), we make no claims of a false null hypothesis without good evidence. Hence, we can conclude, with a high condence level of at least 1 -α, that p 0 ≥ 1 -ε. For a xed value of α and ε and giving the sample size N S, we are searching the minimal k for the sample N S such that P(χ > k) ≤ α. The variable χ is the statistic test, following a binomial distribution under the assumption H 0 , k is the critical value of this statistic test and the set of χ > k corresponds to W , the one-tailed rejection region of H 0 .

In practice, we determined k and, respectively W , the rejection region for a xed α and p 0 = 1 -ε. We were looking for the threshold minimal k such that, if P (G(x, ξ) ≤ 0) ≤ 1 -ε, then:

P{observe k realizations satisfying the constraints} ≤ α Remark 1. If the two hypothesis were inversed, we will obtain a dierent statistical hypothesis test:

H 0 : P (G(x, ξ) ≤ 0) ≥ 1 -ε H 1 : P (G(x, ξ) ≤ 0) < 1 -ε
In this case, we will be interested in accepting the null hypothesis and minimizing the probability 1-α that we are wrong (with α the type I error). As such, for a xed α , we would be looking for a threshold minimal k for which, if P (G(x, ξ) ≤ 0) ≥ 1 -ε, the following inequality holds:

P{observe k' realizations satisfying the constraints} ≤ α

In Fig. 2.3, a binomial distribution of parameters N S = 1000 and p 0 = 0.9 is simulated and for α and α values xed to 0.05, the thresholds k and k were found at 883 and respectively 915. The rejection regions for the two statistical hypothesis tests are pointed in a darker color while the lighter area corresponds to β, the type II error for both tests, more dicult to evaluate.

In the following we are using the rst statistical hypothesis test.

Remark 2. For N S large enough, the binomial law B(N S, p) with p = 1 -ε could be approximated with a normal distribution N (N S * p, N S * p * (1 -p)). This approximation 5 can be further improved using a continuity correction. Remark 3 An alternative to hypothesis testing is to make use of condence intervals. Having stated the hypothesis and established α as well as the hypothesized value, a (1 -α)100% condence interval (CI) is built such that the null hypothesis is rejected if the hypothesized value does not exist in CI. The above approach is justied by the denition of an unknown parameter θ of a two-sided condence interval of form θ l ≤ θ ≤ θ u with unreliability α. This entails all the values θ 0 for which the null hypothesis H 0 : θ = θ 0 would not have been rejected in the observed sample when a two-sided test with α as type I error would have been applied. Any value θ 0 outside the bounds is improbable'.

In our case, when establishing the number of successes χ ≥ k such that the null hypothesis H 0 : p 0 = 1 -ε is not rejected (for a signicance level α against H 1 : p 0 > 1 -ε), we can also determine an one-sided binomial condence interval for the proportion of successes k/N S with a given reliability 1 -α and p 0 = 1 -ε.

There are several ways of computing condence intervals for a binomial proportion: the exact Clopper-Pearson interval [START_REF] Clopper | The Use of Condence or Fiducial Limits Illustrated in the Case of the Binomial[END_REF], the normal approximation interval (also called Wald interval) [START_REF] Wald | Condence limits for continuous distribution functions[END_REF], Agresti and Coull interval [START_REF] Agresti | Approximate Is Better than "Exact" for Interval Estimation of Binomial Proportions[END_REF] etc.

The textbook condence interval most commonly used for a binomial proportion remains the normal approximation interval. In our case, if p = χ N S is the proportion of constraints being respected, the interval we are looking for is p+z 1-α 1 N S p(1 -p) with z 1-α the 1 -α percentile of a standard normal distribution. It is widely recognized that this condence interval performs poorly especially when the sample proportion p is too near to 0 or 1, in which case the normal approximation is not adequate (see Remark 2).

The exact Clopper-Pearson interval is the inversion of the equal-tail binomial test. By guaranteeing that the actual probability is always equal to or above the nominal condence level, it is however rather conservative. Under the hypotheses stated above, for N S = 1000, p 0 = 0.9, α = 0.01 and k = 921 the 99% percent condence interval using Clopper-Pearson method is [0.8989388, 1.0000000] (R command binom.test(921,1000,0.9,alternative="g",0.99)). If we keep the null hypothesis and we state dierently the alternative hypothesis: H 1 : p 0 < 1 -ε, the 99% percent Clopper-Pearson condence interval for N S = 1000, p 0 = 0.9, α = 0.01 and k = 921, is [0.0000000, 0.9396377].

For a detailed study comparing the dierent alternatives for interval estimation of a binomial proportion, we refer the reader to [START_REF] Brown | Interval Estimation for a Binomial Proportion[END_REF]. Along with the risk I error, the condence interval could be used to measure the probability feasibility of a solution to (CCP) problem.

Let get back now to the robust binomial approach with an analysis on the threshold k.

Sensitivity analysis on the values of parameters for RBA

This subsection tries to determine the inuence of parameters ε, α and N S on the threshold k.

The initial reliability level 1 -ε from (CCP) is problem specic and thus, can be more or less high depending on the guarantee the decision maker wants to have on the constraints. The level of α ∈ (0, 1) for a statistical test is commonly set between 1% and 10% and again depends on how much risk the decision maker is willing to take.

Table 2.4 shows some minimal values for k in function of the sample size N S, ε = 0.10 and α = 0.05. For example, for establishing that an inequality holds with a preset probability level of 1 -ε = 0.90 and with a condence level 1 -α = 0.95, for a sample of size 50, the threshold k needed is at 48 and P (χ ≥ 48) ≈ 0.034. It should also be noted that, for a practical use, the parameters ε and α should be of the same order of magnitude. Table 2.5 gives a deeper insight about the minimal number of constraints to respect depending on ε, the prescribed probability level and α, the condence level when N S, the size of the sample, is equal to 100, 1000 and 10000. It should be remarked that for respecting higher probability and condence levels, a more important sample size is needed. However, a sample size of 1000 seems sucient even when ε = 0.01 and α = 0.01. Also, it is possible to obtain the same value of k for dierent values of ε and α (for example, for a sample of size 1000, we obtain k = 948 for ε = 0.07 and α = 0.01 and same value also for ε = 0.05 and α = 0.6). We can also establish in advance the minimal size of the sample required for a xed level of the probability 1 -ε (with ε ∈]0, 1[) and a prespecied condence level 1 -α (with α ∈]0, 1[).

In particular, if p 0 = 1 -ε and P(χ = N S) > α then we can arm that the sampling size is insucient (which is true for N S = 10 and N S = 20, see Table 2

.4).

This formula provides an easy way to determine the minimal number of realizations that need to be drawn in order to statistically signicantly (α) achieve the desired probability level (1 -ε). We remark that its computation does not depend on the number of decision variables as in [START_REF] Calaore | The scenario approach to robust control design[END_REF], nor on complicated complexity measures from Vapnik-Chervonenkis theory as in [START_REF] Vidyasagar | Randomized algorithms for robust controller synthesis using statistical learning theory[END_REF].

Let us now analyze the eect of varying the condence level 1-α on the threshold k for a xed probability level 1 -ε and a xed sample size. Fig. 2.4 (a) shows the values of k for dierent values of ε when the sample size is 1000 and α taking dierent values in (0, 1). It seems that the more risk we are accepting, the more the value of k diminishes (linearly) and so the less is the number of realizations needed for satisfying the constraints. However, for an acceptable risk error α (less than 10%), the variation of k in function of α does not look so important (in average a dierence of 7 additional realizations for respecting the constrains and accept a smaller risk of 0.01 instead of 0.1 for a sample size of 1000). Instead, the value of the initial reliability level 1 -ε has a greater impact on the threshold k for same sample size. Fig. 2.4 (b) shows the variations of k in function of ε ∈ (0, 1) for a xed condence level (0.01, 0.03, etc.) when the sample size is 1000. As expected, for an important probability guarantee, the number of realizations satisfying the constraints has to be higher. For a sample of size 1000 and dierent levels of 1 -α, we remark an augmentation of 85 in average for the value of k when ε = 0.01 than the value of k for ε = 0.1. Same phenomenon happens for a sample of size 10000, when in average we have to have 883 more realizations satisfying the constraints for ε = 0.01 than for ε = 0.1.

Chance constraints and sampling

The statistical theory above can be applied for obtaining a statistically signicant approximation model to the initial program (CCP). Let us rst dene the notion of (N S,α)-statistically admissible solution for a chance constrained program. Denition 2.1. Let ε, α ∈ (0, 1) and let suppose we are given a sample of size N S for ξ. A solution x (N S,α) ∈ R n is (N S, α)-statistically admissible with a condence level of 1 -α for a sample size of N S if, for p 0 = P(G(x N S,α , ξ) ≤ 0), P(χ ≥ k) ≤ α, with χ ∼ B(N S, p 0 ).

In order to obtain a relevant equivalent program to (CCP) model, we make the following assumptions about the random vector ξ, represented by a sample of size N S of observations ξ (i) , with i = 1, . . . N S: Assumption 2.1. N S, the size of the sample for the uncertain vector ξ, is nite and suciently representative.

Assumption 2.2. The sample for ξ is composed of independent and identically distributed (i.i.d.) observations: ξ (1) , . . . , ξ (N S) .

We would like to attract the attention of the reader on the fact that we are not treating time series. As such, our second assumption of independence, is on the dierent observations of the random vector and not on its components which (as already stated) can be dependent. Additionally, the assumptions above remain quite general. As many previous studies do not mention, these assumptions are also necessary in the case of methods using a probability model, as the model itself must be validated e.g. on a Kolmogorov-Smirnov hypothesis test using an i.i.d. sample of experimental data. Moreover, the rst assumption is not very restrictive, since even if the number of initial observations is not sucient, we can resort to statistical methods for resampling, such as bootstrapping [START_REF] Efron | An introduction to the Bootstrap[END_REF]. However, it is important that the initial sample is representative of the distribution. We underline that we are not concerned by the acquisition of representative experimental data. This stage has to be realized a priori at system level, for example during the validation stage and needs to be done regardless of the method used for solving the chance constrained program.

If we take the case of a video encoder for example, the validation tests should provide representative samples of video sequences which can be used for building our approximation program. Afterwards, in order to validate the robust approach, we need other video samples, statistically identical but, of course, dierent from the rst ones. It should also be remarked that in contrast with other existing methods, our sample acquisition as well as possible treatments (such as parameter estimation or bootstrapping) are made before applying the robust binomial approach, intended to nd an approximate solution to the (CCP) problem.

Let dene the binary variable χi for realization ξi :

χi = 1 if G x, ξ(i) ≤ 0, 0 otherwise.
Since the sum N S i=1 χ i follows a Binomial distribution of parameters N S and p 0 (again, by construction), we can determine k(N S, 1 -ε, α). Therefore, we can use χi , the realization of the variables χ i , and replace the probability constraint P(G(x, ξ) ≤ 0) ≥ 1 -ε to obtain the (RBP) formulation, equivalent to (CCP):

min x g (x) (RBP) s.t. N S i=1 χi ≥ k(N S, 1 -ε, α) G(x, ξ(i) ) ≤ (1 -χi )L; i = 1, . . . , N S (2.5) χi ∈ {0, 1}; i = 1, . .

. , N S

The rst constraint assures that the number of constraints which are satised for the given sample are superior to the threshold k, xed in advance in function of N S, ε and α. Constraints 2.5 verify the respect of the constraint for each realization i, making the link between x, ξ(i) and χi , with L a constant of large size, depending on the problem structure but generally easy to nd. For example, for a knapsack constraint m i=1 w i x i ≤ C with w i ≥ 0 the weights of the items to be placed, supposed uncertain, x i binary variables and C the maximal capacity allowed, L = m i=1 w i . Theorem 2.1. A feasible solution for (RBP) problem is a (N S, α)-statistically admissible solution.

The proof is immediate and it is justied by the way (RBP) is formulated. The variables χ i associated to ξ (i) correspond to Bernoulli independent observations (see assumption 2.2) and their sum is following a binomial distribution of parameters N S and p 0 = 1 -ε. A feasible solution for (RBP) have to respect the rst constraint, which assures that, with a condence level of 1 -α, the threshold k is respected.

Minimizing the objective function g(x) for (RBP) model is equivalent to solving the initial program (CCP) with a condence level of at least 1 -α. Additionally, we emphasize once more that the validity of this approximation is independent of any particular assumption on the joint distribution of the random vector ξ, in particular with respect to inter-component dependencies. Although it is well illustrated on the mathematical formulation (RBP), it should be stressed out that our approach is not really appropriate in a mathematical programming setting, since, for example, the reformulation of an original linear problem contains many binary variables and it is more complex to deal with. However, the method can be easily and eciently adapted to heuristic approaches. Furthermore, we can make use of the existing heuristic algorithms developed for the deterministic version of a problem and extend them to the stochastic case.

Having at our disposal a sample verifying assumptions 2.1 and 2.2, any constructive algorithm relying on an oracle for testing solution admissibility can be turned into an algorithm for the stochastic case. This can be done by modifying the said oracle so as to count the number of constraint violations for the given realizations and take an admissibility decision based on the threshold k.

The main steps of an overall optimization process for solving a CCP program integrating an heuristic based on the robust binomial approach are presented in integrate the stochastic oracle to the chosen heuristic 13: end if 14: validation of the method We are not concerned in this chapter by the rst two steps: formulating the problem as a (CCP) program and the acquisition of a sample for the uncertainty data ξ, which are taken as granted. Our interest resides in the resolution techniques and our belief is that solving the problem should be realized by taking into account the specicities of ξ, which justies step 3.

During this preliminary step, the samples we have at our disposal are analyzed: if a nice analytical distribution model can be associated (e.g. Gaussian laws), then we proceed with an estimation method for nding the corresponding parameters.

If, on the contrary, data analysis suggests that the distribution underneath is too complicated to be analytically described, we verify that the condition of applicability of the robust binomial approach are veried.

Since the rst assumption remains general and must also hold for estimation methods, we only have to make sure we dispose of a sucient sample. As such, if the theoretical minimal size, computed in function of ε and a chosen condence level α, is inferior to the size of the current sample, we can resort to re-sampling techniques such as bootstrapping. If there are approximate resolution approaches which have been developed for solving the deterministic version of the same problem (step 6), we choose an appropriate (meta)heuristic 6 and adapt it, by replacing the admissibility deterministic oracle with a stochastic one (steps 6-8). The stochastic oracle is either exploiting directly the samples with the robust binomial approach or, if a distribution model is assumed, makes use of the estimated parameters for verifying the probability constraint. If no heuristic conceived for the deterministic case has been found, we have to conceive one and integrate a stochastic admissibility oracle (steps 10-12).

Let us now give more insight about the redesign-for-the-stochastic-case methodology when we have at our disposal (which is often the case) an existing (meta)heuristic solving the deterministic version of the problem.

RBA and adapting (meta)heuristics

The robust binomial approach can be applied without major eort within a greedy method already developed for the deterministic version. Since greedy algorithms provide an easy and quick way of nding good quality solutions, they are often a popular choice for a rst optimization of large-sized problems. Table 2.7

shows the general structure of a greedy algorithm for the deterministic case as well as its adaptation for the stochastic case. The input is problem specic and consists, for the deterministic case, in giving the structure of the objective g, the constraint function G, the parameter vector ξ as well as the domain of denition for the decision variables.

For the chance constrained version, in which we consider ξ as random, we also specify a sample of size N S for ξ, the probability level ε and in order to apply the robust binomial approach the condence level α. In both cases, R represents the set of decisions not yet made (or residual), D the set of admissible decisions, g(S) the solution value for solution S, d * the current optimal decision and S * the optimal overall solution, built in a greedy fashion. While there are residual decisions to be made, an oracle is evaluating them for deciding the admissible decisions. Between 6. The notion of appropriate heuristic is subjective and consists usually in nding a satisfactory trade-o between implementation eort, quality of the solution and computational time.

the admissible decisions, only the one with the greatest improvement on the optimal solution value is kept and the overall solution S * is updated. If no admissible decision is found by the oracle, the algorithms stops. As seen, the only major dierence when considering chance constraints is in establishing the set of admissible solutions, by using a stochastic oracle O s instead of the original one O (line 3). The deterministic oracle is establishing the admissibility of a residual decision by verifying the respect of the constraints, while the stochastic oracle is applying the RBA and veries if a residual decision is (N S, α)-stochastically admissible by comparing the number of constraints respected by the sample with the threshold k, established in advance in function of N S, ε and α (see the procedures for O and O s in Table 2.8). end if 12: end while Output: S * Such a context assures a practical and tractable implementation of our approach even for cases when a very high number of constraints is demanded. These situations can arise when ε is set to be really small (e.g. less than 10 -5 ) and thus, it is required to have a large minimal size of the sample. For example, a problem with probability level ε = 10 -5 and, accordingly, a condence level α = 10 -5 , requires a sample of minimal size 10 6 which, although large, is not prohibitive. Additionally, in order to obtain a more rapid computation, the operation of counting the constraint violations can be parallelized without major eort 7 . if G(r, ξ(i) ) < 0 then

Output: T rue, F alse

Of course, any optimization algorithm relying on an oracle to determine whether or not a solution is admissible (e.g. a neighboring method) can be turned into an algorithm solving the stochastic case using the same method. For example, the same methodology could be used to integrate RBA into an existing GRASP (Greedy Randomized Adaptative Search Procedure) algorithm to solve the stochastic version of the problem. GRASP, a multi-start heuristic is composed of a construction phase and an improvement phase.

The rst phase consists in building a feasible solution S with a greedy randomized algorithm and its adaptation for the stochastic case could be an algorithm similar to the one shown in Table 2.7.

The second phase takes the solution S and tries to ameliorate it, through a local search procedure, by exploring the neighborhood of S. The only dierence between a generic local search method for the deterministic case and its adaptation to the stochastic version consists in deciding which of the neighbors n of S is a possible new admissible solution, based on a deterministic oracle O(n) or a stochastic oracle O s (n) respectively. The structure of the oracles O and O s could be the same as before or they could be implemented more eciently, using the fact that the neighbors are obtained from a current admissible and respectively (N S, α)-statistically admissible solution. Let us provide an example of a possible application of the RBA method along with a hill climbing heuristic for the classical problem of bin packing. The variant of bin packing we consider here is the following: Bin packing example. Giving a set of n items, each item i having a certain weight w i and a value p i , the objective is to place these items in a xed number of m bins while respecting the available weight C j of each bin j in order to maximize the overall value. The problem can then be formulated as follows:

max P = n i=1 m j=1 p i x ij (2.6) s.t. n i=1 w i x ij ≤ C j ∀j = 1, . . . , m (2.7)
m j=1 x ij = 1 ∀i = 1, . . . , n (2.8)
x ij ∈ {0, 1} ∀i = 1, . . . , n; ∀j = 1, . . . , m.

(2.9)

where x ij are binary variables such that:

x ij = 1 if item i is put in bin j 0 otherwise.
Constraints (2.7) verify the respect of the maximal capacity for each bin while constraints (2.8) make sure that the item i has been allocated to a single bin.

Supposing that the weights of the items w i ∈ R are random and we want a probability of validity for the constraints on the bin weights superior to a threshold 1 -ε, we obtain the chance constrained version of the bin packing problem. Thus, constraints (2.7) are replaced with:

P n i=1 w i x ij ≤ C j ; ∀j = 1, . . . , m ≥ 1 -ε
Let us dene the notions of admissible solution and respectively (N S, α)-statistically admissible solutions for the bin packing problem. Denition 2.2. A placement of items into the m bins is a deterministic admissible solution to the bin packing problem if it respects constraints (2.7)-(2.9). Denition 2.3. Let ε, α ∈ (0, 1) and let assume that we dispose of a sample of size N S of i.i.d. realizations wi (1) , . . . , wi (N S) for all weights of the items i = 1, . . . , n. A placement of items into the m bins is a (N S, α)-statistically admissible solution if constraints (2.8)-(2.9) are respected and if:

N S p=1 χp ≥ k(N S, ε, α)
with k computed as described before and:

χp = 1 if N S i=1 wi (p) x ij ≤ C j ; ∀j = 1, . . . , m 0 otherwise.
Table 2.9 gives the main steps of a simple hill climbing heuristic for bin packing for the deterministic and respectively, stochastic case, making use of the notions dened before. The initial solution s 0 could be a random allocation of items to the bins or it could be constructed into a greedy fashion, through First-Fit Decreasing (FFD) or Best-Fit Decreasing (BFD) algorithms. end if 12: until stop=T rue Output: s A simple neighborhood N of a current solution s can consist in moving an item into a dierent bin or exchanging items placed in dierent bins. Once neighborhood N has been dened, the possible neighbors are analyzed and are kept (in N a ) only when are considered to be an admissible solution and respectively a (N S, α)statistically admissible solutions (line 5). The best neighbor bestN is chosen and if it improves the total value of the solution, it is kept for the following iteration (lines 6-9).

The only major dierence between these two algorithms is in deciding the list N a of admissible neighbors with the help of a stochastic oracle O s instead of the deterministic oracle O. While in the deterministic case, the oracle veries the respect of the capacity of each bin, the stochastic oracle veries, for the given sample, that the capacity of each bin is respected with a threshold ε and a condence level α (see

Def. 2.3).

This methodology could be extended to adapt other (meta)heuristics such as simulated annealing, tabu search or genetic algorithms for solving the stochastic version of a problem with the RBA approach. Both based on local search, simulated annealing and tabu search methods are similar to the hill climbing with respect to the exploration of neighborhoods for a current solution. As such, their adaptation to the stochastic case could follow the same approach as in the case of hill climbing heuristic. For the genetic algorithms, one way to solve the stochastic version is to integrate the robust binomial approach into the tness evaluation function and penalizing those individuals which do not respect the threshold k of minimal constraints to be satised.

Generalization of the RBA 2.3.6.1 Chance constrained programs with more than one probability levels

The robust binomial approach can be easily generalized to treat dierent levels of reliability for chance constrained programs. Actually, the probability constraint from CCP only guarantees that the constraint will be respected with a probability level 1 -ε. However, when the constraint is not respected with probability ε, it does not provide any information about the degree of violation. Note that knowing the magnitude of the constraint violation can also be important, especially for heavy-tail distributions (although the eciency of the RBA has not been yet assessed for these type of distributions).

One solution is to enforce dierent levels of protection by dening alternative thresholds for probabilistic guarantees when the primary target is not achieved.

Let suppose that the r probability levels are ε 1 = ε < ε 2 < • • • < ε r and ∀j = 1 . . . r, ε j ∈ (0, 1). As such, if the probability constraint P (G(x, ξ) ≤ 0) ≥ 1 -ε j is not achieved, then the probability target 1 -ε j+1 is set instead. This results in a program with a set of at most r independent probability constraints. It should however be noted that the larger r is, the larger is the computational eort to solve this type of problem.

These successive independent chance constrained programs could still be replaced by applying for each of them our robust binomial approach under the assumptions made earlier. Eventually, in order to reduce the complexity burden, we can verify in advance if the constraint G(x, ξ) ≤ 0 is satised or not for realization ξi and store the result for exploiting it later when verifying the probability constraint for each threshold 1 -ε j . However, with this approach, the nal solutions will hold only for each individual ε j instead of being guaranteed for dierent levels of probability.

A more interesting way of enforcing dierent levels of protection is by considering them simultaneously, from the beginning. Let suppose again that we have r probability levels ε 1 > ε 2 > • • • > ε r with ∀j = 1 . . . r, ε j ∈ (0, 1) and this time, for each of them we have dierent targets to meet 0 ≤ M 1 < M 2 < • • • < M r for the constraint function G(x, ξ). As such, we are looking for a solution which satises each of the r probabilistic constraints :

min x g (x) (C CP r ) s.t. P (G(x, ξ) ≤ M j ) ≥ 1 -ε j , ∀j = 1 . . . r
Example. Let give a short example for better illustrating this possible extension of the RBA. Let suppose that we want to guarantee the satisfaction of the constraints with respect to three targets 0, M 2 and M 3 with three dierent probability thresholds: 0.75, 0.85 and respectively 0.95. As such, we must solve the following chance constrained program:

min x g (x) s.t. P (G(x, ξ) ≤ 0) ≥ 0.75 P (G(x, ξ) ≤ M 2 ) ≥ 0.85 P (G(x, ξ) ≤ M 3 ) ≥ 0.95
As such, we are looking for a solution which provides alternative guarantees when the rst constraint is not respected, by allowing to achieve M 2 with a probability of at least 85% and M 3 with at least 95% probability.

In order to solve this generalization which assures simultaneously dierent probability levels, the robust binomial approach has to be applied for each threshold 1 -ε j . We obtain the following approximation for (C CP r ) formulation:

min x g (x) s.t. N S i=1 χj i ≥ k j (N S, 1 -ε j , α) j = 1, . . . , r G(x, ξ(i) ) ≤ (1 -χj i )L + M j ; i = 1, . . . , N S; j = 1, . . . , r χj i ∈ {0, 1}; i = 1, . . . , N S; j = 1, . . . , r
with k j the number of minimal constraints to get respected for probability level 1 -ε j (we suppose the same condence level 1 -α for all but it is not mandatory). χj i corresponds to a binary varible such that, ∀j = 1, . . . , r :

χj i = 1 if G x, ξ(i) ≤ M j , 0 otherwise.
Again, due to the computational complexity (an increase factor of r compared to the original (RBP) program), it is more appropiate to make use of heuristic approaches and conceive a stochastic oracle for checking feasibility of the solutions, by counting the number of respected constaints.

Programs with random objective function

Until now, we have considered chance constrained problems of the form CCP, thus static programs with randomness aecting only the constraints. Although, there can be cases in which the objective function of this problem is also random.

For a static program when only the objective function to minimize h(x, ν) is random (with ν the random data), there are several ways to handle the uncertainty (see [START_REF] Prékopa | Stochastic Programming[END_REF] for more details):

1. Converting the problem into a deterministic one by considering the expectation value of the random variable.

Use a policy based on the notion of ecient points (as dened previously).

Another variant of this principle is to replace the objective function by a linear combination of expectation and standard deviation. [START_REF] Kataoka | A stochastic programming model[END_REF].

Introduce a probabilistic constraint and a new objective function

4. For linear programs with ν having a continuous distribution, build an equivalent problem using the basis which are primal feasible for the problem.

The method we consider here belongs to the third category of approaches, with the rst model introduced by Kataoka in 1963 [START_REF] Kataoka | A stochastic programming model[END_REF] which studied the case of a multivariate distribution for ν. Let us consider the program:

min x z = h (x, ν) s.t.
x ∈ D

P (h(x, ν) ≤ u) ≥ 1 -p (2.11)
x ∈ D

(2.12)

where p ∈ (0, 1) is a probability threshold and D the set of initial constraints. This means nding x * such that u(x * ) ≤ u(x), ∀x ∈ D which is equivalent to searching for the superior bound of an unilateral condence interval for h such that x ∈ D.

Of course, the above approach makes sense in situations when the central limit theorem cannot be applied. If the number of random variables ν is large enough and the magnitude of the variation is not too large, a more appropriate choice seems to make use of the expectation E(h(x, ν)).

For a general problem with uncertainty both in objective function and in constraints, we consider that the robust binomial approach could be easily combined with the above stochastic model, if the random variables aecting the constraints are independent from those appearing in the objective function. While the probability in constraints is treated via the robust binomial approach which determines the feasible set D, for guaranteeing the result with a high probability, we are looking for an upper bound for the condence interval of the objective function.

Conclusion

Taking into account uncertainty is a crucial aspect when solving an optimization problem, which has a great inuence on the quality of the overall solution. As such, optimization under uncertainty and in particular stochastic programming and robust optimization remain between the most active domains of research nowadays.

Nevertheless, due to the diculties related to solve problems with uncertain parameters, most of the existing approaches make simplifying assumptions which are not always consistent with the real data.

The robust binomial approach takes advantage of experimental data and reinterprets the scenario approach (between the only existing methods without particular assumptions about the distribution of random variables) with tools from statistical hypothesis. As such, for a sample of size N S, it provides a safe approximation, guaranteed with a condence level 1 -α (with α ∈ (0, 1)), to chance constrained programs with a required 1 -ε threshold on the probability constraints. We also present the necessary steps for integrating the robust binomial approach in an existing approximate algorithm (in the admissibility oracle). The founding principles of the robust binomial approach and a case study consisting in stochastic partitioning of process networks are subject of the journal paper [START_REF] Stan | The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks[END_REF].

Next chapters are dedicated to the application of the robust binomial approach to optimization problems occurring in the compilation process of a dataow application for manycore. Nevertheless, due to its simplicity and the reduced number of assumptions it requires, the robust binomial approach along with the methodology of solving an uncertain optimization problem from Chapter 2 are generic and thus, applicable to other domain elds.

Chapter 3 Our interest is mainly in demonstrating the practical relevance of solving a stochastic problem by integrating the robust binomial approach into an existing heuristic developed for the deterministic case (as we conceptually explained in 2.3). As such, we want to show that having at our disposal an algorithm for the deterministic case, it is relatively easy in terms of software engineering (notably)

Graph partitioning under uncertainty

to adapt it to the chance constrained version of the same problem. In the latter case, the solutions found are of consistent quality (with respect to the ones provided by the original algorithm) and more importantly, guaranteed to be robust to data variations with a condence level of 1 -α and a required probability level of 1 -ε.

Since a multi-start constructive algorithm was already developed for partitioning networks of processes, we took advantage of the existing implementation in order to adapt the admissibility oracle and solve the stochastic case. The original greedy algorithm for the deterministic problem is given in section 3.3.2 and the associated computational results are presented in section 3.5. Therefore, we are not claiming that this existing algorithm is a best-in-class graph partitioning algorithm. What we do claim is that, using a slight adaptation of this algorithm, we can easily obtain robust solutions. Thus our experiments focus on showing that the algorithm for the stochastic version provides results consistent with those of the original one and attempt to quantify the price of robustness.

Problem statement

We begin by a formal description of the problem of process networks partitioning:

As mentioned in Chapter 1, a dataow application can be modeled as a directed graph in which the vertices are the tasks and the arcs are the channels. One of the (numerous) tasks of a dataow compilation chain consists in mapping this graph onto the hardware resources of the target microprocessor architecture. Thus, in this chapter, we study the problem of assigning the weighted vertices of such a graph to a xed set of partitions. We aim to minimize the sum of costs for edges having their extremities in dierent partitions (representing the processors), without exceeding the limited capacity (e.g. the memory footprint) of each partition. This application is an extension of the more abstract NP-hard problem of Node Capacitated Graph Partitioning (NCGP) [START_REF] Garey | Some simplied NP-complete graph problems[END_REF], [START_REF] Ferreira | The node capacitated graph partitioning problem : A computational study[END_REF].

Let G = (V, A) be a directed graph where the set of vertices V = v 1 , v 2 , . . . , v |V | represents the tasks and the arcs (v, w) ∈ A correspond to the channels of a process network. Let N be the set of disjoint nodes on a parallel architecture on which we want to map our graph. The resources (essentially memory footprint and computing core occupancy resources) are given by the set R and the capacities of the nodes are given by the multi-dimensional array C ∈ R +|R| . For the sake of simplicity, our study was limited to the case of homogeneous nodes: i.e. all nodes have the same capacity.

Let us also dene two functions. s : V -→ R +|R| , is the size function for the vertex weights, with s(v) r being the weight of vertex v for resource r. The second function, dened for the edges, is the anity function q : A -→ R +|R| where q((v, w)) > 0 denotes the weight of edge (v, w) ∈ A and q((v, w)) = 0 if no edge (v, w) exists between the vertices v and w. In the remaining, we will use the following simplied notation: Q vw = q((v, w)) for each arc (v, w) ∈ A and S vr = s(v) r , for r ∈ R and v ∈ V .

The partitioning problem we work on consists in nding an assignment of vertices to nodes, denoted f : V -→ N , that satises the capacity constraints for all resources:

v∈V :f (v)=n S vr ≤ C r , ∀n ∈ N, ∀r ∈ R, (3.1)
by minimizing the objective function:

(v,w)∈A:f (v) =f (w)

Q vw

The stochastic case we consider for the graph partitioning with capacity constraints is taking into account the uncertainty aecting the node weights, being a relatively novel problem, as we will show in the following.

Related works

Deterministic graph partitioning

Since the graph partitioning problem and especially the bisection problem (a particular version of the problem for |N | = 2, also NP-hard) have been of great interest in the past, many dierent resolution methods were developed for treating the deterministic case. There are several surveys (see [START_REF] Fjällström | Algorithms for graph partitioning : A survey[END_REF], [START_REF] Elsner | Graph partitioning -a survey[END_REF], [START_REF] Bichot | Partitionnement de graphe[END_REF]) resuming the existing algorithms for deterministic graph partitioning.

Due to the NP-hardness of graph partitioning, the literature addressing the exact resolution of this problem is relatively sparse. Among the most successful exact deterministic approaches are the branch-and-price or column generation methods [START_REF] Johnson | Min-cut clustering[END_REF], [START_REF] Mehrotra | Cliques and clustering : A combinatorial approach[END_REF]. Interesting results are also obtained in [START_REF] Ferreira | The node capacitated graph partitioning problem : A computational study[END_REF], in which the polyhedral structure of the problem is analyzed and classes of strong valid inequalities are included in a branch-and-cut algorithm. We should also mention the existence of a few approaches exploiting lower bounds for the problem. Particularly new lower bounds of rather good quality were found using semidenite programming [START_REF] Lisser | Graph partitioning using linear and semidenite programming[END_REF] as well as multi-commodity ows [START_REF] Sensen | Lower bounds and exact algorithms for the graph partitioning problem using multicommodity ows[END_REF]. Nevertheless, these exact methods can handle only relatively small graphs and are too slow to be applied to larger graphs (with, for example, more than a thousand vertices). Mainly for this reason, these methods are not adequate to our application where we have to partition instances with a number of vertices varying roughly between 500 and 4000 on 16 to 64 nodes. Therefore, we turn our attention to heuristics, the usual and more practical methods for tackling such problems. There are a large number of such methods, either global or local, that dier with respect to cost (time and memory space required to run the algorithm) and partition quality, i.e. the optimal solution or the cut size. One of the earliest and most popular algorithms, due to Kerninghan and Lin [START_REF] Kernighan | An Ecient Heuristic Procedure for Partitioning Graphs[END_REF], originally proposed for the bisection case, is of quite high complexity (for a graph with |E| edges, O(|E|) for Fiduccia adaptation [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF] or in the original version O(|E| 2 log(|E|))). Also, it demands a lot of computational eort for being adapted to the capacitated generalized problem. Among local metaheuristics, one of the most used to solve the graph partitioning problem is simulated annealing, mainly because of its simplicity [START_REF] Johnson | Optimization by simulated annealing : An experimental evaluation ; part i, graph partitioning[END_REF], [START_REF] Kirkpatrick | Optimization by simulated annealing : Quantitative studies[END_REF]. However, it highly depends on the structure of the problem and for large sized instances, the required execution time may become prohibitive.

For very large graphs, rather good results were found by global approaches, such as the multilevel and hierarchical methods [START_REF] Hendrickson | A multilevel algorithm for partitioning graphs[END_REF], [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] or the more recent method of fusion-ssion [START_REF] Bichot | A new method, the fusion ssion, for the relaxed graph partitioning problem and comparisons with some multilevel algorithms[END_REF].

Stochastic graph partitioning

Previous work related to the stochastic form of the problem treated in the present dissertation is quite scarce. Fan et Pardalos studied a problem relatively close to ours: partition the vertex set of a graph into several disjoints subsets so that the sum of weights of the edges between the disjoint subsets is minimized, with a cardinality constraint on each subset and the uncertainty aecting the edge weights. In [START_REF] Fan | Robust optimization of graph partitioning and critical node detection in analyzing networks[END_REF], assuming there is no information on the probability distribution other than that the weights on the links are independent and bounded in known intervals, they formulate the problem using a robust optimization model, similar to [START_REF] Bertsimas | The price of robustness[END_REF]. The equivalent linear programming formulation is then solved by an algorithm based on a decomposition method.

In a more recent study [START_REF] Fan | On the two-stage stochastic graph partitioning problem[END_REF], they introduce the two-stage stochastic graph partitioning, assuming that the distribution of edge weights has nite explicit scenarios. Having as objective to minimize the expected weight of edges in the set of cuts over all scenarios, they present a nonlinear stochastic mixed integer model and propose an equivalent integer programming formulation for solving the problem using CPLEX. Taskin et al. [START_REF] Caner Taskin | Cutting plane algorithms for solving a stochastic edge-partition problem[END_REF] study the stochastic edge-partition problem,

where the edge weights are uncertain, and are realized only after the node-tosubgraph assignments have been made. They introduce a two-stage cutting plane algorithm with integer variables in both stages and, to overcome the computational diculties, they also prescribe a hybrid integer/constraint programming method as an alternative.

The approaches above dier in several aspects from our study. First, in our case, the problem formulation is not the same, dealing with multidimensional capacity constraints on the nodes instead of cardinality constraints. Consequently, uncertainty is addressed in a dierent manner, the assumption of uncertainty being made on the weights of the vertices rather than on the weights of the edges. Finally, we remark that the existing methods are exact and thus, mostly suited for small-size instances of the problem, the numerical experiments being performed on graphs with at most 100 vertices. On the contrary, for the processes placement problem, we are interested in practice to partition much larger graphs.

3.3 Preliminaries: Deterministic algorithm

Relative anity

Before describing the randomized greedy heuristic our stochastic algorithm is based on, let us recall the notion of relative anity, initially introduced in [START_REF] David | Etude et realisation d'une architecture modulaire et recongurable : Projet MODULOR[END_REF] (see also [START_REF] Stan | A heuristic algorithm for stochastic partitioning of process networks[END_REF]).

Let S and T be two disjoint subsets of V .

Denition 3.1. The anity of S for T is given by :

α(S, T ) = (v,w)∈δ(S,T ) Q vw .
with δ(S, T ) = {(v, w) : v ∈ S; w ∈ T }. It follows that α(S, T ) = α(T, S).

Denition 3.2. The total anity of S (similarly for T ) is given by

β(S) = α(S, V \ S).
Denition 3.3. The relative anity of S for T is dened as

γ(S, T ) = 1 2 α(S, T ) 1 β(S) + 1 β(T )
where α(S,T ) β(S) represents the contribution to the total anity of S of the edges adjacent to S and T .

Let us illustrate these notions through a simple example [START_REF] David | Etude et realisation d'une architecture modulaire et recongurable : Projet MODULOR[END_REF] on the undirected graph shown in Figure 3.1a. We suppose that we only have one resource and that all the vertices have unitary weights and we want to partition the graph into two

v∈V \W :f (v)=n S vr + v∈V \W :f (v)=m S vr ≤ C r
The assignments are favored over fusions and, when tie-breaking with respect to relative anity, the heuristic prioritizes the assignment of vertices with heavier weights on less loaded nodes and the fusion of the most loaded nodes. We also formally dene the relations of heavier vertex and more loaded node which are being used in the algorithm for the multidimensional case.

Denition 3.6. The vertex v is smaller or lighter than the vertex w if:

max r∈R S vr C r < max r∈R S wr C r (3.2)
Denition 3.7. The node n is more loaded than the node m if:

max r∈R 1 C r   C r - v∈V \W :f (v)=n S vr   < max r∈R 1 C r   C r - v∈V \W :f (v)=m S vr  
The algorithm, to which we will refer as RG_PART, takes as input the set of unassigned vertices W (initially equal to V ), the set of nodes N , the set of resources R and the vertex weights S vr . A basic version of the algorithm is given underneath.

γ 1 = γ({v * }, {v ∈ V \ W : f (v) = n * }) 4: Find an admissible fusion (n * 1 , n * 2 ) (n * 1 ∈ N , n * 2 ∈ N ) cf. Def. 3.
γ 2 = γ({v ∈ V \ W : f (v) = n * 1 }, {v ∈ V \ W : f (v) = n * 2 }) 5: If γ 1 ≥ γ 2 then assign v *

Output: assignment f

Since greedy algorithms tend to sometimes get trapped with poor quality solutions, a type of diversication strategy is required. This is the reason why a randomized version of the algorithm is executed several times (i.e. in a a multi-start fashion). The randomization strategy consists in executing the algorithm rst on the list of vertices sorted by their decreasing weights (see step 2 of the algorithm and for multi-resource case, Eq. 3.2) and several times afterwards using randomized versions of the list of vertices.

The algorithm being given for the deterministic version of our problem, we can now turn to the case we are interested in, the one in which the weights of the vertices are uncertain.

Chance constrained version

The robust binomial approach described in chapter 2 can be easily applied for solving the stochastic version of the capacitated graph partitioning problem. All we have to do is to combine the statistical hypothesis testing with the heuristic algorithm RG_PART by counting the number of times the constraints are violated by an initial sample.

For the stochastic version of our graph partitioning problem, formally stated in section 3.1, we make the assumptions that the task weights S vr are random variables and that we dispose of a relevant sample of N S independent and identically distributed realizations of the uncertain vector of task weights. For i = 1 to N S, let S(i) vr be the realization of the i-th observation for resource r.

Let us also note the event e nr = { v∈V :f (v)=n S vr ≤ C r }. The capacity constraint, expressed for the deterministic case in equation (3.1), becomes:

P n∈N r∈R e nr ≥ 1 -ε.
In order to ensure that the probabilistic constraint is satised with a given condence level at every step of the algorithm, it is necessary to redene the notions of admissible assignment and admissible fusion.

Denition 3.8. An assignment of vertex v to node n is stochastically admissible if the sum:

N S i=1
χ({∃n = n, ∃r :

w:f (w)=n S(i) wr > C r } ∨ {∃r : S(i) vr + w:f (w)=n S(i) wr > C r }),
is less than N S -k(N S, 1 -ε, α), where χ(P a ) = 1 if and only if the predicate P a is true.

This calculation can be simplied by using an ad hoc data structure, a boolean bi-dimensional array of size |N | × N S, denoted t, indicating for the partial current partitioning if, for every node, the sample i has already induced a violation. Thus, the assignment of a vertex v to a node n is stochastically admissible if:

N S i=1 χ(t[n , i] ∨ {∃r : S(i) vr + w:f (w)=n S(i) wr > C r }) < N S -k(N S, 1 -ε, α)
With the use of the boolean array, the computation of an admissible assignment increases in complexity linearly, with a factor of N S, compared to the deterministic case.

If the vertex v is eectively assigned to node n then the boolean array is updated with:

t[n, i] := t[n, i] ∨ (∃r : S(i) vr + w:f (w)=n S(i) wr > C r )
Denition 3.9. A fusion between nodes n and m is stochastically admissible if the sum:

N S i=1
χ({∃n , r :

w:f (w)=n S(i) wr > C r } ∨ {∃r : w:f (w)=n S(i) wr + v:f (v)=m S(i) vr > C r }),
is less than N S -k(N S, 1 -ε, α), where χ(P f ) = 1 if and only if the predicate P f is true,.

Analogously, we can simplify P f by using the same boolean matrix |N | × N S. Once the fusion is realized, the entries for nodes n and m are updated as follows:

t[n, i] := t[n, i] ∨ (∃r : w:f (w)=n S(i) wr + v:f (v)=m S(i) vr > C r ) t[m, i] := f alse
As for the computation complexity, we remark a linear increase with a factor of N S in comparison to the deterministic version.

Also, since we have to deal with a sample of size N S, we can redene the way we compare the vertices and the nodes weights, by taking into account the average over all realizations as follows.

Denition 3.10. The vertex v is smaller or lighter in average than the vertex w if:

max r∈R N S i=1 S(i) vr N S * C r < max r∈R N S i=1

S(i)

wr N S * C r Denition 3.11. The node n is more loaded than the node m in average if:

max r∈R 1 C r C r - v∈V \W :f (v)=n S(i) vr N S < max r∈R 1 C r C r - v∈V \W :f (v)=m S(i) vr N S
The above denitions can then be easily integrated in the algorithm described in section 3.3.2, without any major destructuring. As such, the algorithm Alg. It should be noted that the only remarkable dierences between the algorithm RG_PART and its stochastic counterpart RG_PART_STOCH are in Step 3 and

Step 4 when deciding if the current assignment or fusion is admissible. Additionally, the algorithm for the chance constrained case needs as input the N S realizations of S vr , the tasks weights for each resource, 1 -ε the prescribed probability level and 1 -α the condence level.

By using the robust binomial approach within a heuristic approach, we also overcome the computational eort of taking into account the uncertainties of the weights of the vertices. We could even further improve the performances of the heuristic by parallelizing the computations of admissible assignments and of admissible fusions.

(v * , n * ) (v * ∈ W , n * ∈ N ) cf. Def.
3.8, if any, with maximal relative anity:

γ 1 = γ({v * }, {v ∈ V \ W : f (v) = n * }) 4: Find an admissible stochastic fusion (n * 1 , n * 2 ) (n * 1 ∈ N , n * 2 ∈ N ) cf. Def. 3.9, if
any, with maximal relative anity: Output: assignment f

γ 2 = γ({v ∈ V \ W : f (v) = n * 1 }, {v ∈ V \ W : f (v) = n * 2 }) 5: If γ 1 ≥ γ 2 then assign v *

Computational results

In this section, we report on the computation experiments of applying the above sample-based randomized greedy heuristic to the chance constrained version of graph partitioning with uncertainty aecting the weights of the vertices. All these experiments have been carried out on a Linux PC workstation, with a 3.80 GHz Pentium(R) processor, 3 GB of memory and Ubuntu 10.04 as operating system. In the rest of the section, we report about the benchmark, the random variables used in our computation and dierent evaluation measures. Then we discuss the results of the heuristic for the chance constrained version in comparison with the heuristic for the deterministic case.

Benchmark and Uncertain Parameters Generation

Since, to the best of our knowledge, there are no probabilistic instances dened for the graph partitioning problem with uncertain weights on the nodes, we tested our algorithm on two modied sets of test problems, originally intended for the deterministic case.

The rst set of instances consists of some examples of grids, representative in size for our application. Besides, these instances are easy to modify and we can use them to test dierent congurations of the parameters for our method. The second set is dened by instances publicly available dened in Johnson et al. [START_REF] Johnson | Min-cut clustering[END_REF] and initially used for bisection. The tests on this second set were performed in order to conrm the eectiveness of our stochastic algorithm (both in terms of solution quality and running time) on a set of representative instances.

It should be noted that the instance Grid 23x23, from the rst data set, with 529 vertices and 16 nodes, is the closest in size to the real instances we have to deal with in our application context, at least as a rst step.

The number of vertices for Johnson instances varies between 124 and 1000 and, for both sets, we consider the case of mono-dimensional resources.

In the deterministic case, the tests were performed for unitary weights for edges and vertices.

We have generated the random variables representing the weights of the vertices by simulating a joint bimodal distribution. The two modes are uniform in their intervals and selected in an equally likely manner.

The rst mode is represented by the hypercube:

[0.8, 0.9] |V | , and the second one, by the hypercube:

[1.1, 1.2] |V | .

Results for the deterministic version

Table 3.1 shows the experimental results obtained by applying the RG_PART heuristic for graph partitioning on the rst data set with deterministic vertices weights. All the results were obtained for the monodimensional case (the capacity of each node is indicated in column C) with unitary weights for edges and vertices.

The column Multi in Table 3.1 shows the solutions found by running the multistart version of the heuristic (with 10 iterations) and the column Time shows the running time for one iteration in average over 10 iterations. The RG_PART heuristic was applied on the larger sizes instances of Johnson et al. [START_REF] Johnson | Min-cut clustering[END_REF], with unitary weights for edges and vertices. As illustrated by Table 3.2, the solutions are reasonably close to the optimum (*) or to the best known solutions (column Best known). Furthermore, for most instances we observed that the solutions values found have an average dierential approximation ratio [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] of 5.22% compared to the best known value.

Although these results are only of moderate quality, our goal in this experimental part is to provide them for serving, in the next section, as a starting point for measuring the price of robustness of the solutions obtained by the algorithm derived for the stochastic case.

Results for the chance constrained version

We have tested our adaptation of the algorithm for the stochastic case on the same problems varying the parameters ε and α in the range {0.01, 0.05}. To obtain a set of stochastic instances, we have considered that the weights of the vertices are random variables with the aforementioned bimodal distribution and we generated corresponding samples of size 100 and respectively 1000. Choosing a smaller size for the sample may make the solution infeasible, and larger values of N S increase computation time of the problem.

The method has been implemented in C language and, for each instance, 10 random iterations of our algorithm were executed. Tables 3.3 -3.5 summarize the numerical results for the grid problems for dierent values of the parameters N S, ε and α. The computational results for the second data set, the Johnson instances, are reported in Tables 3.6 -3.8.

For each instance from the data sets, we performed two tests. The rst test consists in keeping the same node capacity as for deterministic case (see columns C from Tables 3.1 -3.2) and progressively increasing the number of nodes used in the deterministic case until the probabilistic constraint is satised.

The numerical results of this test, reported in section 1st test of Tables 3.3 -3.8 are: the minimal number of nodes for which the probabilistic constraint is respected (column #nodes), the solution value (column sol) and the average execution time for 10 iterations (column time).

For the second test, we maintain the same number of nodes as in the deterministic case, but we gradually increase the capacity of all nodes (starting from one used in the deterministic case) until nding a feasible solution, satisfying the probabilistic constraint.

The results of this second test, reported in section 2nd test of Tables 3 It is worthwhile noting that the solutions obtained in the second test, by increasing the node capacity, are of better quality than the solutions of the rst experiment (see columns sol) and can be adjustable more accurately. For example, in Table 3.4 for Grid 10 × 10, for nding a feasible solution, we must add two more nodes.

However, in this case the solution found is too conservative since all the constraints are veried. Since, however, in practice it is easier to modify the number of nodes than the capacity of each node, we also investigated the results found by the rst test.

Our main purpose with these tests is to get an idea of the cost of the robustness of the solutions, independently of concrete application constraints.

In evaluating the performance of our heuristic method, between the main aspects we consider are: the capacity and the number of nodes needed for nding a feasible solution, the time factor and the robustness and quality of the solutions.

In our rst test, we were interested in the number of nodes needed for the stochastic case compared to the deterministic one. Our computational results show that the ratio between the number of nodes for stochastic partitioning and the number of nodes for deterministic partitioning for the same instance is 1.5, except for Grid 23 × 23, for which the ratio is equal to ≈1.14. The same ratio of 1.5 was found for the Johnson instances.

For the second test, we analyzed the required increase in capacity for solving the stochastic version of the problems. The stochastic solutions of the instances reported in Tables 3.3 -3.5 are obtained for an equally large increase in the capacity of the nodes in the order of 1.1. For the Johnson instances, the capacity of nodes for stochastic partitioning is superior to the nominal capacity with ≈ 1.15. As one may expect, keeping the same probability and condence levels and changing the sample size does not signicantly aect the minimal capacity of the nodes for which a valid solution is found. On the contrary, imposing a higher probability and condence levels demands a minimal capacity of nodes slightly larger (in the order of 0.001). Following the run of each instance, we have also observed a particular behavior consisting in a threshold eect of the solutions, sensible to the node capacity variations. One example is the problem U1000.10 for which an augmentation of the capacity from 576.06 to 576.20 results in a largely better solution (69 against 115). Concerning the time factor, the overall execution time of our method mainly depends on the number of vertices and on the size of the sample. We note that the running time needed to solve Johnson instances is considerably higher than the time required for the grid problems, the reason being the presence of instances of larger size (e.g., G1000.0025-G1000.02, U1000.05-U1000.40). As expected, the larger is the sample size, the higher is the computation time, with an average of 48.04 sec. for a sample size of 1000 (Table 3.7) against 25.93 sec. for a sample size of 100 (Table 3.6) for the second test. It should also be noted that the computation time for the rst test is, in average, superior to the time for nding solutions in the second one.

By comparison of Table 3.7 and 3.8, it appears that when a higher probability level ε and condence level α are imposed, a slightly higher execution time is needed.

Although these results could be improved (e.g. by code optimization and parallelism), such execution durations are already acceptable in our application context with respect to the usual compilation duration of a dataow process network on a many core architecture.

The running times found for the stochastic version of the algorithm conrm the theoretical remarks (see Section 3.4) on a linear increase in complexity with a factor of N S in comparison of the deterministic case.

In order to measure the quality and the robustness of the stochastic solutions, the algorithm RG_PART was re-run with the same input parameters as the ones found with the chance constrained method. We kept the same number of nodes and respectively the same capacity of each node as the ones for which the chance constrained methods found feasible solutions and we considered unitary weights for arcs and unitary weights for tasks (which is the expected value of the distribution of our uncertain data).

As expected, for the rst test consisting in increasing the number of nodes, the quality of the stochastic solutions is almost always worse than for the deterministic version and than for the solutions found by the second test. One exception is the instance U500.05, from Table 3.6 but this result is assumed to be due to the heuristic nature of our approach, which, by construction, provides no guarantees with respect to monotony.

Instead, the stochastic solutions of the second test are quite often close in quality to the solutions found when running RG_PART algorithm. By analyzing Tables 3.6-3.7, for ε, α = 0.05 we found out that there are 14 and respectively 15 instances with a gap in the stochastic solution quality of less than 5% from the deterministic solutions. When analyzing the results for a probability level of 0.99 and a level of condence of 0.99 (Table 3.8), we remark a number of 14 stochastic solutions close (a relative 5% gap) to the deterministic ones.

By comparing the quality of solutions for dierent values of the input parameters (N S, ε, α) it comes out that for the same probability and condence levels, the obtained solutions when varying the sample size are quite similar, revealing that the performance of our algorithm does not deteriorate as the number of samples increases. It should be noted that it is however necessary to determine the minimal size of the sample needed to solve the problem with the required probability level.

The required sample size for ε, α = 0.01, is at least 459, which justies our choice not to conduct tests for these values on the samples of size 100.

Concerning the robustness of the solutions found by the presented approach,

we measured the number of times the deterministic solution is not satised on the used samples. The percentage of samples on which the deterministic solution is not satisfying the capacity constraints 3.1 is, in average, for Tables 3.6-3.8 between 48,24% and 50.04%.

Analyzing the overall results, we observe that our stochastic heuristic conrms the capacity of computing good solutions, within an admissible average running time, even for large instances. The quality of the solutions is comparable to the deterministic case (i.e. the price of robustness is reasonable). Moreover we guarantee that our solutions are robust to the uncertainties aecting the weights of the vertices.

Conclusion

In this chapter, we addressed the stochastic problem of partitioning communicating networks of process, with a theoretical equivalent in the Node Capacitated Graph Partitioning problem. The objective is the assignment of processes corresponding to the dataow of an embedded application to a xed number of nodes (clusters) and minimizing the communications inter-clusters while respecting the capacity of each node. The uncertain random variables are the weights of the processes for which we dispose of a sample of size N S and thus, we want to make sure the capacity constraints are getting respected with a probability of at least 1 -ε.

In order to solve this problem, the RBA approach introduced in Chapter 2 was integrated within a greedy algorithm, originally intended for the deterministic case.

The criteria for dening an admissible assignment of a vertex (process) to a node and an admissible fusion of two nodes were modied to assure that the number of constraints respected by the sample are superior to the threshold k established in function of N S, ε and α (see section 2.3 from Chapter 2 for details).

Since the chance-constrained graph partitioning is a relatively new problem and no stochastic instances were available in the literature, we had to generate two benchmarks adapted from the instances for the deterministic version, by generating random variables following a bimodal uniform distribution.

Numerical results showed that the obtained solutions have often a quality consistent with those computed for the deterministic version. More importantly, the solutions found are robust and guaranteed with a preset statistical signicance level, to hold to data variations aecting the constraints. We also showed that not taking into account the stochastic nature of our data and considering only the deterministic case may lead to non feasible solutions with quite high probability (in average 50% of cases). Furthermore, this approach can solve with an acceptable computation time problems close in dimensions to the real instances a compiler would have to treat.

Chapter 4

Joint placement and routing under uncertainty This chapter addresses the problem of application mapping, classied as one of the most urgent problems to be solved for implementing embedded systems [START_REF] Marwedel | Mapping of applications to MPSoCs[END_REF], [START_REF] Marculescu | Outstanding research problems in NoC design : System, microarchitecture, and circuit perspectives[END_REF]. Several workshops dedicated to mapping applications onto multi-core systems have been created in order to move beyond state-of-art in this domain (e.g.

M-SCOPES [43]

). There are dierent mapping methodologies varying in function of application and architecture models, constraints and assumptions imposed by the system, the metrics to be optimized, information available about the platform, etc.

The purpose of this work is to propose a placement method for dataow process networks (DPNs), which also takes into account the computation of routing paths.

As such, it provides an alternative approach to the sequential placement and routing steps of the resource allocation compilation step of a ΣC program (presented in section 1.4.3.3), which targets specic application domains (e.g. multimedia and networking) characterized by high bandwidth demands. Even if the two sub-problems of tasks mapping and routing have already been addressed in the literature, the novelty of our method consists in treating together task mapping and routing, and thus, taking into account the routing when placing the networks of processes, without any particular assumption on the network (here a Network-On-Chip) topology, both for deterministic and stochastic cases.

Before presenting the GRASP algorithm we conceived for the deterministic case (section 4.3.1), section 4.2 presents some existing mapping approaches. By adapting the GRASP using the general methodology introduced in 2.3, we solve the stochastic version of the same problem in section 4.4. Computational results, using both synthetic and real benchmarks, are shown and analyzed in the last part. We begin by a formal description of the problem.

Problem statement

The optimization problem we study consists in placing at design time the tasks of a DPN onto the network of clusters, such that the total bandwidth is minimal and for each pair of communicating tasks, there is a shortest routing path between tasks situated on dierent clusters.

The clusterized architecture is represented by a directed graph G = (N, A, R, B a ) with N the set of nodes (clusters) and A the set of arcs between nodes, corresponding to the NoC links.

B a : A -→ R describes the bandwidths between dierent clusters of the target architecture, with B a ((n i n j )) > 0 the maximal capacity for arc (n i , n j ) and B a ((n i n j )) = 0 if nodes n i and n j are not connected. R is the set of resources (essentially memory footprint and computing core occupancy) we have at our disposal. The capacities of the nodes are given by a multi-dimensional array

C n ∈ R +|R| .
For the sake of simplicity, we restrain our study to the case of homogeneous nodes and arcs for G, hence we suppose all nodes have the same capacity C nr for each resource r ∈ R and all arcs have the same maximal bandwidth B a .

Let DP N = (V, E, S, Q) represent the network of processes with V the set of vertices (tasks) and E the set of communication channels. S : V -→ R +|R| , is a size function for the tasks, with s tr being the weight of task t for resource r. The function Q : E -→ R characterizes the communication between tasks where q t i t j > 0 denotes the weight of arc (t i , t j ) ∈ E and q t i t j = 0 if no arc (t i , t j ) exists between t i and t j .

Let g : V → N be a mapping of tasks to the nodes. As such, we are interested in nding an admissible routable assignment g of tasks to nodes that minimizes the cost of the inter-clusters communication:

(tt )∈E:g(t) =g(t ) q tt (4.1)

In the context of our present work, an admissible assignment is a mapping of tasks to nodes which satises the capacity constraints:

t∈V :g(t)=n s tr ≤ C nr , ∀n ∈ N, ∀r ∈ R, (4.2)
and furthermore, it ensures that there exists a feasible routing between every two communicating tasks: {∀(t, t ) ∈ E and g(t) = g(t ) and q tt ≥ 0} : ∃route(t,t') (4.3) which route respects the maximal capacity B a of the links of the network. As such, the last condition veries if all the bandwidths can be accommodated across the network G without exceeding the maximal capacity of the arcs in terms of bandwidth.

In order to simplify communication protocols, the search of possible routes will be limited to a single unsplittable commodity ow using a shortest-path routing strategy.

In our approach, we prioritize the minimization of the bandwidths and we analyze the dierence, for an obtained placement between the routing our algorithm is using and an ideal one (using a shortest-path strategy).

Since the tasks mapping is equivalent to the Quadratic Assignment Problem which is NP-hard [START_REF] Garey | Some simplied NP-complete graph problems[END_REF] and the unsplittable ow problem can be restricted to the Directed Edge Disjoint Paths problem, also NP-hard [START_REF] Korte | Combinatorial Optimization : Theory and Algorithms[END_REF], the joint problem is straightforwardly NP-hard in the strong sense.

Regarding the size of instances specic to the application context, our method has to be able to map networks of processes with a few hundreds tasks on architectures having at least a dozen of nodes. For an experimental validation of our approach, one of the benchmarks consists of data coming from a motion target dataow expressed in ΣC (as described in section 1.4.2) which has to be placed on a NoC in the form of a bi-dimensional torus 4 × 4. The following section presents some of the methods belonging to these two categories for the deterministic case, with a particular emphasis on the static placement, since this is the case we are most interested in. For a detailed survey on mapping strategies, please refer to [START_REF] Singh | Mapping on multi/manycore systems : survey of current and emerging trends[END_REF] Actually, even if most of the existing studies treating task mapping belong to this category, they remain dierent in the architectures they are targeting (homogeneous or heterogeneous), the optimization goal they x and the restrictions they impose on the system. Moreover, we have to remark that even if the task mapping was and remains a relatively well studied problem (with the rst works by Stone [START_REF] Stone | Multiprocessor scheduling with the aid of network ow algorithms[END_REF] and Lo [START_REF] Lo | Heuristic algorithms for task assignment in distributed systems[END_REF]), the routing aspect has been often neglected, the scheduling problem drawing more the researchers attention. Also, usually, the objective of existing techniques is a placement with load balancing thus for which the tasks are equally distributed between all the processing elements (e.g. [START_REF] Walshaw | Partitioning & mapping of unstructured meshes to parallel machine topologies[END_REF], [START_REF] Ercal | Task allocation onto a hypercube by recursive mincut bipartitioning[END_REF], [START_REF] Diekmann | Load balancing strategies for distributed memory machines[END_REF]) while for our current approach, the interest is in minimizing the number of used clusters.

Related works

For the mapping of applications expressed as dataow process networks and for which the target architecture is a multi/manycore system, we can cite [START_REF] Orsila | Parameterizing simulated annealing for distributing Kahn process networks on multiprocessor SoCs[END_REF], [START_REF] Castrillon | Communication-aware mapping of KPN applications onto heterogeneous mpsocs[END_REF], [START_REF] Bonetti | An ecient and complete approach for throughput-maximal sdf allocation and scheduling on multi-core platforms[END_REF], [START_REF] Choi | Executing synchronous dataow graphs on a SPM-based multicore architecture[END_REF], [START_REF] Galea | A parallel simulated annealing approach for the mapping of large process networks[END_REF]. In [START_REF] Orsila | Parameterizing simulated annealing for distributing Kahn process networks on multiprocessor SoCs[END_REF], a simulated annealing algorithm is proposed for distributing Kahn Process Networks on Multiprocessors SoCs (MpSoCS) with at most four Processing Elements (PE) connected with dual shared bus. [START_REF] Galea | A parallel simulated annealing approach for the mapping of large process networks[END_REF] proposes a parallelized simulated annealing approach for the DPNs mapping on a square torus architecture.

Since this method is quite computationally demanding (roughly twenty minutes for a 31 × 31 square grid of tasks using 6 computing cores), it is more appropriate to be applied at the end of the development cycle of embedded applications. [START_REF] Castrillon | Communication-aware mapping of KPN applications onto heterogeneous mpsocs[END_REF] presents an algorithm which, executed repeatedly, allows process and communication mapping of applications expressed as Kahn Process Networks onto a homogeneous MpSoC, with the objective of minimizing the application makespan. In [START_REF] Bonetti | An ecient and complete approach for throughput-maximal sdf allocation and scheduling on multi-core platforms[END_REF], the authors address both mapping and scheduling of SDF applications on homogeneous multi-core platforms, using a Constraint Programming-based algorithm to maximize the throughput. Another method for solving the mapping and scheduling of a SDF application on a multi-core architecture, based on a genetic algorithm ( [START_REF] Choi | Executing synchronous dataow graphs on a SPM-based multicore architecture[END_REF]), takes into account the limited size of scratchpad memory (SPM) of the cores and tries to minimize the execution latency.

It is worth mentioning that the problem we address is dierent in constraints and objectives from the similar optimization problems occurring in VLSI (Very-Large-Scale-Integration) design ow for creating integrated circuits. In the latest case, the placement consists in taking a list of electronic components (which compose the circuit) and arranging them geometrically in a limited space while the routing is in charge of the design of the wiring connecting the placed components. The result of the placement and routing (usually two steps realized sequentially) is called layout, which is the geometric description of the circuits parts and of the paths followed by the wires. Nowadays, the placement and routing for integrated circuits is usually made automatically with the help of EDA (Electronic Design Automation) tools (the most popular being those from Mentor Graphics, Cadence and Synopsys) and there are numerous dedicated algorithms (like FastPlace [START_REF] Viswanathan | FastPlace : ecient analytical placement using cell shifting, iterative local renement and a hybrid net model[END_REF], FastRoute [START_REF] Pan | FastRoute : A step to integrate global routing into placement[END_REF],

ROOSTER [START_REF] Roy | Seeing the forest and the trees : Steiner wirelength optimization in placement[END_REF] or IPR [START_REF] Pan | IPR : an integrated placement and routing algorithm[END_REF], just to name a few).

Several approaches [START_REF] Marcon | Time and energy ecient mapping of embedded applications onto NoCs[END_REF], [START_REF] Srinivasan | A technique for low energy mapping and routing in Network-on-Chip architectures[END_REF], [START_REF] Murali | A Methodology for mapping multiple use-cases onto Networks on Chips[END_REF], [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF] for multi/manycore platforms propose conguration of the NoC according to the application in order to meet tasks requirements while tting a specic SoC architecture. A branch-and-bound algorithm is proposed in [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF] for the mapping of intellectual property blocks -IP (like CPU or DSP cores, video stream processors, input/output devices) on an architecture organized as regular tiles (composed of a processing core and a router), related by a NoC. The objective is to minimize the total energy spent on communication, by ensuring that each IP goes to exactly one tile, no tile can host more than one IP and having a routing constraint related to bandwidth usage. At each step, the algorithm assures a minimal and deadlock-free routing which respects the maximal load for each link of the NoC by incorporating a list of routing paths as part of the solution, instead of a single routing path. [START_REF] Murali | A Methodology for mapping multiple use-cases onto Networks on Chips[END_REF] conceives dynamic re-conguration mechanisms to match the NoC conguration to the communication characteristics of each use-case. A design methodology, restricted to AEthereal NoCs, is introduced for mapping, path selection and resource reservation in the network, by taking as input use-cases of the SoC. The objective of the mapping process is to design the smallest size NoC, with the smallest number of switches that satises the constraints for all use-cases. Instead, we consider that the manycore specication and in particular NoC characteristics such maximal bandwidth for links are rigid.

As such, the placement and routing of tasks are realized afterwards (without worrying about scheduling) during the compilation process of a dataow application.

Between the only approaches similar treating the same problem under same constraints as ours of which we are aware of is [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF] which solves the problem as a master(placement)/slave(routing) couple. As such, the overall problem is split into two sub-problems, less complex. The assignment is solved using a semi-greedy algorithm while the routing paths are computed optimally with a mixed linear integer programming. However, the sequential resolution can un-structure the initial problem and the found placement may not be routable so there can be feasibility issues for the routing problem downstream as a result of relaxing some constraints for the upstream problem. The typical example consists of a placement non routable we cannot route because the ows between the nodes of the network exceed the maximal bandwidth capacity for the links B a .

Dynamic mapping

In contrast with static approaches, dynamic mapping is performed at run time and as a consequence, the time taken by the mapping algorithm to nd a solution adds to the overall application execution time. As such, a compromise must be made between the quality of the solution and the running time. Greedy algorithms are typically used to provide an ecient mapping, optimizing dierent criteria such as reliability, energy consumption, execution time, etc. Once tasks mapping is performed, task migration (consisting in relocation of tasks) is a popular technique to respond to possible changes occurring at run time (e.g. performance bottleneck, new application entering the system, etc.).

Besides being suited for dynamic workload scenarios (the number of tasks executing in parallel varies in time), dynamic mapping has several advantages such as: adaptability to changes in the amount of available resources, possibility to upgrade the system (with new applications or standards not known at design time)

or capability to avoid defective processing cores.

The platform manager, responsible for handling the mapping, can use a centralized management approach (one single core for the whole platform), distributed management (several communicating cores for managing several regions-clusters of the platform) or a mixture of centralized and distributed management. The centralized manager is more adapted to small platforms since this type of management is not scalable and can become a hot spot while the distributed management can be employed for larger architectures.

Also, the mapping process can be performed entirely at run time (on-the-y mapping) or by using design time analysis (DSE) results. On-the-y mapping requires ecient heuristics, independent of the architecture and that can be used to assign tasks coming from new applications (unknown at design time). The mapping based on previously analysis results is possible for an application known at design time and selected by making use of light heuristics between a series of already computed assignments at design time and stored on the system. Therefore, the intensive computation analysis takes place at design-time, taking as input the application and the architecture descriptions and producing a number of possible mappings. Such type of task assignment, also called hybrid mapping, performs better than on-the-y mapping but it is less exible since it must be aware at design time of the application requirements.

For more details on existing dynamic mapping methodologies, we invite the interested reader to refer to [START_REF] Singh | Mapping on multi/manycore systems : survey of current and emerging trends[END_REF].

Stochastic mapping

While there are quite numerous studies analyzing the stochastic behavior of task execution times for soft real-time applications (e.g. for scheduling purpose), there are almost no works on optimizing the design of an application and taking into account the fact that task execution times are stochastic.

In [START_REF] Manolache | Task mapping and priority assignment for soft real-time applications under deadline miss ratio constraints[END_REF], stochastic mapping and priority assignment of graph tasks on a multiprocessor hardware architecture is performed via a tabu search heuristic with the goal to optimize the ratio of deadlines missed. The underneath assumption is that for each task and each processor, a set of execution time probability density functions is available.

Lombardi et al. [START_REF] Lombardi | Stochastic allocation and scheduling for conditional task graphs in multiprocessor systems-on-chip[END_REF] address the stochastic problem of allocation and scheduling of conditional tasks graphs (CTG) for multiprocessor platforms, by guaranteeing that for each run time scenario encapsulated by the graph, the temporal and resource constraints are satised. As such, they are searching for an unique assignment of starting time and resources to tasks, minimizing the expected value of the communication cost. By analyzing the task graph, they propose an exact analytical stochastic formulation of the objective and solve the allocation using Integer Linear

Programming and the scheduling with Constraint Programming.

[141] studies the static robust resource allocation to application for distributed systems that are periodic sensor-driven when the execution times of the applications are independent random variables. While the objective function consists of minimizing the period between sequential data sets produced by the sensors, the probabilistic constraint is on the performance characteristic of the system. In order to compute this probability and to make sure it is superior to a minimal QoS (Quality of Service), bootstrap or FFT (Fast Fourier Transform) methods are used and the obtained approximation of the cumulative density function is further employed by the four greedy heuristics the authors design.

We can then arm that, to the best of our knowledge, the stochastic problem of joint placement and routing of dataow applications for manycore has not been yet addressed in the literature. Let us now get back for a moment to the GRASP algorithm we conceived for the deterministic problem, which, due to the robust binomial approach, can be adapted to solve the stochastic case.

Deterministic algorithm

We recall that our work is concerning the static placement and routing of applications for embedded manycore in the context of an iterative compilation. The objective is to place the tasks of an application to the nodes of the network and in the same time, mono-route the ows on the Network-On-Chip. As such, in order to design a resolution method for the joint mapping and routing, an important aspect to decide is for which step of the development cycle of embedded applications this algorithm is intended. The beginning of the development of an embedded application requires a short programmer/target feedback loop when the programmer is able to obtain a rst working version of the application with a well coarse-grained structure.

Thus, the beginning of the cycle requires for fast heuristics and can accept solutions of moderate quality. At the end of the development cycle, since more human and computing times are invested (e.g. acceptable compilation times of up to one night), more ne-grained optimizations are aorded. Hence, at this point of the cycle, one can accept more computationally intensive algorithms and more powerful computer systems.

Other algorithmic aspects to be considered are the problem complexity and the size of real instances to deal with, both factors making the building of a tractable exact resolution for both mapping and routing dicult and inecient.

As such, we turned our attention to approximate algorithms and in particular to the GRASP metaheuristic, which seems a more suited choice to tackle this problem especially for the beginning of the development cycle of an application.

GRASP & Preliminaries

Introduced in the nineties by Feo and Resende [START_REF] Feo | Greedy randomized adaptive search procedures (GRASP)[END_REF], GRASP (Greedy Randomized Adaptative Search Procedure) is a multi-start metaheuristic, each iteration involving two phases: construction and local search. The construction phase builds a feasible solution using a greedy randomized algorithm. During the local phase, the neighborhood of the current solution is investigated in the search of better solutions.

At the end, the best overall solution is kept as the result.

Alg. 4.1 illustrates the main blocks of our GRASP method for nding routable mappings of tasks to clusters. The input parameters are the set of tasks V , the set of nodes N , the set of resources R, the maximum number of iterations to be performed and also the parameter k used for controlling the amount of randomness (this is the probabilistic aspect of the construction phase). The mapping g c found by the construction phase is further exploited in local search phase and optimized.

If the resulting mapping g of this post-optimization is better than the previous best mapping g b then we update g b . Algorithm 4.1: GRASP for joint placement and routing

Input: V , N , R, k, MaxIterations 1: g b ← null 2: for i = 1 to MaxIterations do 3: g c ← construction_phase(V , N , R, k) 4: g ← local_search_phase(g c ) 5:
update best assignment g b with g if needed 6: end for Output: best assignment g b Before explaining in more details each one of the two stages of our approach, let us recall the notions of total and relative anity, initially introduced in [START_REF] David | Etude et realisation d'une architecture modulaire et recongurable : Projet MODULOR[END_REF].

Let S and T be two disjoint subsets of V . where α(S,T ) β(S) represents the contribution to the total anity of S of the edges adjacent to S and T .

Construction phase

The greedy constructive method from the rst step of our GRASP is inspired from an existing algorithm, initially used for partitioning networks of processes and which was based on the notion of relative anity ( [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF], [START_REF] Stan | A heuristic algorithm for stochastic partitioning of process networks[END_REF]). We modied it in order to deal with routing and we changed the randomization strategy to intensify the diversity of the solutions.

The main idea of our constructive algorithm is to verify at each step of the mapping, that the ows between the assigned tasks can be routed by making use of the previous computed ows and trying to nd feasible paths for the new or modied ows. At each step of the mapping, the computation of new routing paths is realized through a single source shortest-path algorithm on a reduced graph G obtained from the original network G and whose arcs are weighted with a residual capacity C ra .

Let G = (N, A ) be the reduced graph with the same number of vertices N as G and A the set of arcs in G weighted with a positive residual capacity.

Let F be the set of ows between tasks and for each ow f ∈ F , s(f ), d(f ) and w(f ) are respectively the source, the sink (or the destination) and the demand (the weight) for ow f . Let sp(f ) be the shortest path in G by which the ow f is accommodated.

So sp(f ) is composed of a set of nodes {n 1 , n 2 , . . . , n m } ∈ |N | × |N | × . . . |N | with m ∈ {0, |N | -1}, n 1 = g(s(f )) and n m = g(d(f )), such that ∀i = {1, . . . , m -1}, ∃(n i , n i+1 ) ∈ A , C r (n i ,n i+1 ) ≥ w(f )
and the length of this path is minimal.

Initially, A = A and ∀a ∈ A , C ra = B a and afterwards, it is updated as follows:

C ra = C ra - f ∈F w(f ) * χ a with χ a = 1 if a ∈ sp(f ) 0 otherwise.
Let us now dene the notions of admissible assignment and admissible fusion, which for the current approach, verify not only the respect of capacity resources but also the existence of a routing.

Let W be the set of vertices not yet assigned to a node. Denition 4.4. An assignment of task t to node n is admissible if it satises the capacity constraints for node n:

s tr + t ∈V \W :g(t )=n s t r ≤ C r , ∀r ∈ R
and there is a feasible routable path for every ow f between t and all the other tasks t ∈ V \ W with g(t) = g(t ) and (tt ) ∈ E: After each assignment or fusion, G and F are updated accordingly, by modifying C ra and by adding and/or removing ows (in the case of a fusion). The overall framework of the greedy randomized construction algorithm is presented in Alg.4.2.

{∃sp(f ) ∈ G : s(f ) = t ∧ d(f ) = t ∧ w(f ) = q tt > 0} {∃sp(f ) ∈ G : s(f ) = t ∧ d(f ) = t ∧ w(f ) = q t t > 0}
Initially, a partial solution is set as the rst min(|V |, |N |) tasks in lexicographic order assigned to the N nodes with the condition that this initial mapping is also routable.

Then, the list [rcl] of k best decisions is constructed in a greedy fashion, by choosing between an admissible assignment or an admissible fusion, the ones with the highest anity. Between the parameters we can set before running our algorithm, we can also dene which type of anity (relative or absolute) we want to choose as criterion for deciding between several candidates in the constructive part.

Once a decision c i is chosen at random from [rcl], we evaluate its nature (assignment or fusion) and make the corresponding changes for C ra and F . Output: Assignment g c (V )

c i from [rcl] 5: If c i is an assignment (v * ∈ W, n * ∈ N ), then update set W . Else, c i is a fusion (n * 1 ∈ N, n * 2 ∈ N ),
If c i is an assignment of task t i to node n, the set W is updated: W = W \{t i }, the incoming / outgoing ows between the task t i and the other tasks already assigned are computed and added to the set F and the residual capacities of the arcs of the network are reduced accordingly.

If c i is a merge of two nodes (n * 1 ∈ N, n * 2 ∈ N ), the necessary modications are made such that all vertices from node n * 1 are transferred to node n * 2 , the ows of the tasks already assigned are updated for taking into account the fusion and the residual capacities of the arcs of G are also recomputed.

Local search phase

Afterwards, the quality of the constructed solution S for g c , the assignment obtained previously, is improved through a local search procedure. The neighborhood structures are classical: either 1-OPT by transferring single tasks already placed to others nodes or 2-OPT, consisting in generating a new solution from S by interchanging pairs of tasks assigned to dierent nodes. The use of this type of neighborhoods is appropriate under the assumption of a relative homogeneity for the tasks weights. Also, when setting the parameters of the local optimization we can choose between a rst (in which the current solution is replaced by the rst better local solution) or best improving search strategy. In practice, it has been observed that for many applications, quite often, both search strategies lead to the same nal solution, but with smaller computation times when a rst improving strategy is used [START_REF] Feo | Greedy randomized adaptive search procedures (GRASP)[END_REF].

The subtlety of our approach consists in selecting the tasks to move and exchange from the set:

EX t = {t ∈ V : (∃n = g(t) ∈ N : α(t, n) -α(t, g(t)) > 0)}
with α(t, n), the anity of task t for node n (see [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF], [START_REF] Stan | A heuristic algorithm for stochastic partitioning of process networks[END_REF]).

Once the set EX t is constructed, only admissible transfers or admissible exchanges are analyzed. The routability aspect is veried using the same principles as described previously and each time a local optimization occurs and the placement is modied, the reduced graph and the set of ows F are also updated. Denition 4.6. For a given assignment g, a transfer of task t to a node n is admissible if: the capacity of node n remains respected for each resource t 1 :g(t 1 )=n s t 1 r +s tr ≤ C nr , ∀r ∈ R the ows f ∈ F between t and other tasks t for which g(t ) = n and w(f ) > 0 are reroutable.

The solution S of the new placement when moving t to node n can be easily computed using S: S = S + g(t )=g(t) q ttg(t )=n q tt . Denition 4.7. For a given assignment g, an exchange of two tasks t and t from node g(t) to node g(t ) and vice versa is admissible only if: the capacity constraints for the associated nodes are respected Since, except for the exchanged tasks, all the others remain on the same nodes, the computation of the value for the solution S corresponding to a 2-OPT neighborhood can be realized quickly based on S and the bandwidths of exchanged tasks.

The new value of the solution when moving t to g(t ) and t to g(t) will be:

S = S + g(t)=g(t i ) (q tt i -q t t i ) + g(t )=g(t i )
(q t t i -q tt i )

Stochastic algorithm

For the stochastic version of the joint placement and routing, we consider that the random data are the weights of the tasks and we obtain the associated chanceconstrained problem, in which constraints 4.3 are being replaced by the probability constraints for the capacities of the nodes:

P   t∈V :g(t)=n s tr ≤ C nr , ∀n ∈ N ; ∀r ∈ R   ≥ 1 -ε.
with ε ∈ (0, 1).

We also assume that, for the weights of each task t ∈ V , for each resource r ∈ R, we have at our disposal a sample of sucient size N S of i.i.d. realizations s(1) tr , . . . , s(NS)

tr .

As such, in order to solve this stochastic problem, we can use the same methodology as the one described in Chapter 2, Section 2.3.5, and adapt the existing GRASP by integrating the robust binomial approach.

Let us recall that the necessary changes for modifying an algorithm for the deterministic case into one solving the chance-constrained version were at the level of the oracle deciding the admissibility of a solution. A solution is accepted in the stochastic case if the number of times the original constraint is respected is superior to the threshold k established in function of N S, the size of the sample, the initial probability level 1 -ε and of the condence level 1 -α with α ∈ (0, 1).

For the GRASP conceived for the joint deterministic placement and routing, the oracle of the greedy constructive step which decides if a decision (either assignment or fusion) is feasible is based on the notions of admissible assignment and admissible fusion. Therefore, we have to modify these two notions in order to take into account the stochastic nature of the tasks weights.

Since the constructive part is inspired from the existing algorithm for graph partitioning which we have also adapted to the stochastic case, under the same assumptions, the notions of stochastic admissible assignment and stochastic admissible fusion will be similar to those from Chapter 3 with the exception of the routability aspect to be taken into account.

s(i) t r > C r }),
is less than N S -k(N S, 1 -ε, α), where χ(P a ) = 1 if and only if the predicate P a is true. there is a feasible routable path for every ow f between t and all the other tasks t ∈ V \ W with g(t) = g(t ) and (tt ) ∈ E:

{∃sp(f ) ∈ G : s(f ) = t ∧ d(f ) = t ∧ w(f ) = q tt > 0} {∃sp(f ) ∈ G : s(f ) = t ∧ d(f ) = t ∧ w(f ) = q t t > 0} Denition
s(i) t 1 r + s(i) tr - s(i) t r > C r }}
where χ(P a ) = 1 if and only if predicate P a is true.

Besides these changes when dening the admissible neighborhoods, the local search remains the same as for the deterministic problem.

Let us now provide some experimental results obtained by applying the GRASP method for deterministic and respectively stochastic case.

4.5 Computational results

Benchmarks

Deterministic instances

In order to test our GRASP algorithm, we used several sets of test problems:

grids to be placed on square grids, a modied version of Johnson instances [START_REF] Johnson | Min-cut clustering[END_REF],

random data generated with TGFF 1 and a real image processing application to be compiled using the compilation chain and placed on a manycore architecture.

The rst set of instances consists of undirected DPNs grids, representative in size for our application context, with unitary weights for tasks and for communication channels. Besides, these instances are easy to modify and we can use them to test dierent congurations. Table 4.1 shows grids instances details, with column #Vertices the number of vertices to be placed and column #Nodes the number of clusters for a homogeneous tore architecture on which the vertices have to be placed. The results are giving for a maximal bandwidth for the links of the dierent NoCs set to B a = 1000. The end column Sol. reports the solutions obtained by the semi-greedy algorithm for tasks mapping described in [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF].

The second set is composed of publicly available undirected graphs, rst used for bipartitioning [START_REF] Johnson | Min-cut clustering[END_REF], with dierent topologies and a number of vertices varying between 124 and 1000. We consider unitary weights for the channels between each communicating pair of vertices as well as unitary mono-dimensional weights for the vertices. The initial instances were adapted to be placed on a torus 2D of 4×4 nodes with maximal capacity on the arcs B a = 1000.

The real application we test here is the motion target application, video processing and tracking a sequence of related input video frames as described in Chapter 1. Modifying the number of strips in which the images of the video sequence are divided induces a modication of the number of tasks to be placed. There are three The number of incoming and outgoing arcs a task can have is limited to two. We considered the mono-resource case in which the capacity constraints are on the occupation ratios of each node.

The capacities of nodes n ∈ N of the architecture are equal and are computed as:

C n = x * V i=1 s i /N with s i the weight of task i and x ∈ {1.01, 1.25, 1.5, 1.75, 2}. As for the maximal bandwidth B a on the arcs of the target architecture, we create and sort the list of communications weights of the channels between tasks l = {q t i t j > 0 : t i , t j ∈ V } and then choose B a as max(q t i t j ) + y i=1 l[i] with y ∈ {5, 6, 7, 8}.

Therefore, the most restricted instances are those with limited capacity on the nodes when x = 1.01 and with limited maximal bandwidth for the arcs of the network when y = 5.

Stochastic instances

The tests for the chance-constrained version of the placement and routing were performed on the above instances, transformed to stochastic benchmarks with random weights for the tasks.

For the grids instances, we generated the random variables representing the weights of the vertices by simulating a joint bimodal distribution with each mode uniform in its intervals and selected in an equally likely manner. The rst mode is represented by the hypercube: [0.8, 0.9] |V | , and the second one, by the hypercube:

[1.1, 1.2] |V | .
As for the TGFF instances, we considered small variations on the weight w t of each task t, following a bimodal uniform distribution : [w t -3%w t , w t -1%w t ] × [w t + 1%w t , w t + 3%w t ].

For the target motion detector, we consider the case when this ΣC application is composed of 57 tasks and has to be mapped on a Kalray architecture [START_REF] Dupont De Dinechin | A Distributed Run-Time Environment for the Kalray MPPA-256 Integrated Manycore Processor[END_REF], with a frequency of the chip of 400MHz. We use a simulation with ISS (Instruction Set Simulator) to obtain the processor cycles for each execution of an agent and thus, deducing the execution times(knowing that a cycle corresponds to 2.5 ns).

104CHAPTER 4. JOINT PLACEMENT AND ROUTING UNDER UNCERTAINTY

Instead of computing the core occupancy for each agent based on the mean of these executions (as it is made in the deterministic case), we take a sample of minimum 30 occupation rates of each occurrence for an agent and apply the GRASP for the stochastic case to place the application. Each task is repeated 1 times per execution cycle and the application is dimensioned to get 30 frames per second in output. As such, the occupancy ratio of each occurrence of an agent, having a processor cycle

Results for the deterministic version

Our GRASP algorithm was tested for dierent congurations, with k ∈ {2, 3, 4}

(see Alg. 4.2, line 3), total versus relative anity during construction, best improvement and rst improvement, 1-OPT versus 2-OPT for local search phase, etc.

We have decided to stop our algorithm when a number of maximal iterations or when a time limit of 10 minutes are reached.

Since we prioritize the minimization of the bandwidths (cf. Eq.4.1) we guarantee just that this mapping is routable. As such, we are not guaranteeing an optimal routing and instead, we are analyzing the dierence, for an obtained placement, between the routing our algorithm is using and an ideal one, (using a shortest-path strategy), by measuring the average for all ows f ∈ F of fraction: lb = length(sp(f ))

length r with length r being the shortest path in the NoC between s(f ) and d(f ).

Table 4.2 shows some of the placement results obtained for grids instances when the number of iterations is equal to max(100, |V |log|V |), the notion of relative anity is used, the maximal bandwidth B a = 1000 and the number of selections k ∈ {2, 3, 4}. The column GR represents the results of the construction part while columns PS-1 and PS-2 are the complete results with post-optimization, when 1-OPT and respectively 2-OPT neighborhoods are used. As shown, the local search is useful and better results are obtained for k = 2 and k = 3. Overall the quality of solutions is comparable with the one found by the algorithm from [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF].

GRASP solutions have an average deviation from the solutions found by the semigreedy method in [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF] of ≈5% for k = 2 (with 2-OPT) and less than 10% for k = 3 and k = 4 (both 1-OPT and 2-OPT), with the advantage that we also ensure the routability. In average, the results found using 2-OPT are better than those with 1-OPT. When the capacity of arcs B a is large enough, our method is able to accommodate the ows via the shortest paths and lb = 1 in all cases. Instead, when limiting more the capacity of the links, the average of lb tends to increase to 1.05.

For the second set, as shown in Table 4.3 the best values for the placement of our GRASP were obtained with the notion of relative anity, when k = 2 and k = 3

with solutions of better quality than those found by [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF], (reported in columns Greedy) for 18 and respectively 17 instances (out of a total of 25). Also, the results are denitely better for k = 2 instead of k = 4 (for 20 out of 25 instances).

For the target motion application, Table 4.4 shows the results obtained for a number of processes varying between 60 and 300 (column |V |) in function of the number of strips (column ST). These results, obtained with the GRASP approach for k ∈ {2, 3, 4}, using the notion of total anity and a number of iterations equal to max(100, |V |log|V |), are compared with those obtained by the method currently implemented in the compilation chain (column [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF]) for the placement of the application on a 2D torus 4 × 4 with B a = 10000000. The GRASP method provides better results in almost all cases. It should however be noted that when relative anity is used instead, the results of the GRASP are of lower quality. Since the capacity of the network is large enough with regard to the ows to be routed, the bound lb is equal to 1 for all instances, meaning that the routes found are following shortest paths.

The same instances were used to place the target motion application on the same homogeneous NoC but this time with a maximal bandwidth for each arc B a = 100000. While none of the placements found by the method from [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF] is routable afterwards, the current method is nding placements which are also routable, with an average of 1.17 for lb.

Extensive tests were also performed on the random TGFF graphs. One of the rst tests was to compare the quality of the solutions for a dierent number of maximal iterations, when k = 2, relative anity is used and local search is based on exchanges of tasks. As expected, more the number of iterations is higher, more the quality of solutions increases, with ≈50% of cases in which the solutions are better for max(100, |V |log|V |) iterations.

We then compared the quality of the placements for a number of selections equal to 2 and post optimization based on 2-OPT, when the notions of total and relative anity are used. It seems that the relative anity is a better criterion to choose for the construction part, with 1113 instances with solutions of higher quality against 268 when using the absolute anity.

Another test consisted in testing the GRASP (with k = 2, the number of iterations max(100, |V |log|V |) and a 2-OPT strategy) against the sequential algorithm from [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF]. The last one solves rst the placement with a greedy method and afterwards the routing with a MILP. The GRASP is able to nd more solutions (for a total of 1920 instances), with 1358 instances against 927 for the algorithm in [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF].

For 25,5% of the total number of graphs, our algorithm nds a routable placement while the other does not nd a placement or nds a placement which is not routable.

When both algorithms nd a solution, the value of the placement of the GRASP is better or within 5% of the value found by the other method for 28.7% of cases.

For the routing, in 38.3% of solved cases, the values are within 7% from the optimal routing found by the MILP from the sequential algorithm.

Results for the stochastic version

The tests for the stochastic version of the placement and routing are performed with the following conguration for the GRASP: the number of selections k = 2, relative anity as criterion of choice in the constructive part, local search based on 2-OPT and the maximal number of iterations xed to max(100, |V |log|V |). We decided to stop the algorithm as before, when the maximal number of iterations is reached or a time limit of 10 minutes are reached.

The experiments consist in evaluating aspects such as the quality of the placements, the time required and the price of robustness. First we keep the same capacity for all nodes as in the deterministic case and afterwards, if needed, increase the capacity of all nodes with a factor of {1.15, 1.25, 1.5, 1.75} until a feasible solution for the chance-constrained case is found.

The stochastic version of the GRASP was tested on the grids problems by varying the parameters ε ∈ {0.05, 0.1} and α in {0.01, 0.05} for a sample size of 100 and respectively 1000. Tables 4.5-4.6 report the solutions obtained with column sol.

for the solution value, columns time for the execution time and C n the increase factor required for the capacity of each node in order to nd a feasible solution. As it can be seen, the quality of the solutions is coherent with those found by the deterministic algorithm. Also, we can remark that the eort to achieve robustness for the solutions is not so high. For instances grid4×4 and grid10×10 it is necessary an increase of 1.25 and respectively 1.15 in the capacity of the node in order to nd a solution. For the other instances, the stochastic GRASP is able to nd solutions by keeping the same C n . As expected, the execution time of the method depends on the number of vertices and on the size of the sample, with a superior overall execution time when using a sample size of 1000 instead of a sample of 100 realizations.

We also tested the algorithm on the 1920 stochastic TGFF instances for a sample size of 100, when ε = 0.95 and α = 0.05. Table 4.7 shows the average time needed to nd solutions for sets of instances having same number of vertices V : 50, 100

and respectively 200 and conrms our assessment on the computational complexity increasing with the number of vertices. As reported in Table 4.8, the majority of robust solutions (68.33%) are found without the need to increase the capacity of each node C n (column 1). While in ≈14% of cases a multiplication factor of 1.15 for C n is required to reach probabilistic solutions (usually for initial instances with limited node capacity), for 12.4% of instances, our method is unable to nd solutions (column NA). We can remark however that for the last category, the initial deterministic GRASP also has not found solutions and only 11 additional instances are not solved for the chanceconstrained version. Moreover, the stochastic method nds more feasible solutions than its deterministic counterpart, since it is more exible by allowing the increase of the node capacity.

We have also compared the quality of the solutions with those found in the deterministic case when the capacity of the node remains the same. The results are synthesized in Table 4.9 where the value of the stochastic solution sol s is compared to the deterministic solution sol d . For more than 40% of the 1312 instances, the solutions obtained are of better quality than in the deterministic case and in more Finally, we tested the stochastic algorithm on real data obtained by running the motion target application on ISS simulator with four dierent inputs, ε = 0.1 and α = 0.05. The size of the samples for the computation ratios of the tasks as well as the values of the placements and routing are reported in Table 4.10. Each time we obtain same results for placement and for routing as the GRASP for the deterministic case and the sequential algorithm from [START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF]. One possible explanation is the small sizes of the instances and the reduced quantity of resources they require:

for each input, only two out of the 16 clusters are used to map the application.

Conclusion

In this chapter we addressed the problem of joint placement and routing of dataow applications on a clusterized architecture, for both deterministic and stochas-110CHAPTER 4. JOINT PLACEMENT AND ROUTING UNDER UNCERTAINTY tic cases. In order to nd routable placements, we have designed a GRASP for the deterministic version which was further adapter for the stochastic case using the robust binomial approach introduced in Chapter 2. For each assignment of a task to a cluster or a change on the current mapping, the routability is veried via a shortest-path algorithm on a residual graph, build from the initial architecture and updated constantly.

Extensive experiments were performed either on random generated instances or on real data obtained for the motion target application. When tested on a benchmark composed of 1920 synthetic graphs, for 25% of cases, our GRASP method found mappings which are also routable while a sequential algorithm (doing rst the placement and the routing afterwards) did not nd any valid solutions. Also, for the benchmark consisting of motion target data, for a reduced maximal available bandwidth on the arcs of the network, our algorithm is able to nd routable placements of good quality. The heuristic method for the deterministic problem and some preliminary results are introduced in [151].

As for the stochastic problem, the GRASP is able to nd solutions of good quality without paying too much of a price to obtain robustness. The tests run on grids, random graphs and motion target data showed that taking into account the variations of the data is particularly important in cases when the available resources are limited.

With the arrival of new embedded applications, more complex to deal with and more computationally demanding, we feel that the joint placement and routing can be applied as a possible alternative to map these programs. Moreover, for situations where the clusters resources become tight, solving the mapping by considering uncertainty may prove to be useful.

Chapter 5

Conclusion and future work

The new generation of manycore embedded systems, containing hundreds if not thousands of cores, requires new programming and execution models for parallel applications in order to fully take advantage of the available computing power.

Dataow paradigm seems a good solution to program applications for these manycore architectures which can overcome the associated diculties (limited and dependent resources, parallelism, etc). However, in order to deploy dataow applications on the target platforms and eciently exploit the resources, one must resort to optimization techniques from the operations research eld all along the compilation process. Additionally, one common particularity of the optimization problems related to this domain is the presence of uncertain data (such as execution times or network latencies).

In this thesis, we have treated optimization under uncertainty in the context of massively parallel embedded systems. The overall purpose was to apply operation research techniques in order to solve optimization problems from the compilation of dataow programs for manycores when the data are uncertain.

Taking into account the specicities (dependency, multidimensionality etc.) of execution times, one of major sources of uncertainty for the manycore context, we have conceived a new method for solving chance constrained programs which can be applied without any particular assumption on the random variables. Based on the scenario optimization method, known to be easily applied, and on basic statistic tools, the robust binomial approach is extensible to numerous other application domains. The only requirement is to have at our disposal a suciently representative sample of observations. The approach is truly algorithmic ecient if we make use of it within the framework of approximate algorithms or of heuristics, when deciding the feasibility of a solution.

A general methodology has been designed for adapting existing (meta)heuristics to solve the stochastic problems by integrating the robust binomial approach. In this way, complex problems can be tackled in order to nd robust solutions, guaranteed with a minimal reliability threshold and with a high condence level. Moreover, extending an algorithm already developed to solve the stochastic case of a same problem is relatively easy in terms of software engineering. Therefore, applying (meta)heuristics enhanced with the robust binomial approach may be a exible and viable alternative to address real-world size chance constrained problems.

The robust binomial approach was validated while studying two optimization problems from the compilation of embedded dataow applications: the partitioning as well as the joint placement and routing of networks of processes.

CHAPTER 5. CONCLUSION AND FUTURE WORK

For the rst problem, consisting of nding a partition of processes onto a xed number of nodes when the processes have uncertain weights, we have proposed a greedy resolution method.

The second problem having as objective the minimal assignment of the processes which is also routable, was treated in both deterministic and stochastic cases. A GRASP heuristic was rst developed for the deterministic version and afterwards adapted to solve the stochastic case with variations on the weights of the processes.

For each problem, the quality of the solutions found by the resolution methods proposed has been established with experimental tests on synthetic benchmarks and even on practical instances (a motion target application).

Clearly, many other research directions remain to be explored, related to either the general optimization under uncertainty methodology or to the application context.

With regards to the robust binomial approach, it would be interesting to nd new ways to improve it. An example would consist in nding a method for classifying the set of observations from the initial sample in dierent groups, targeting dierent probability levels for the constraints. Since our method focuses on nding feasible but suboptimal solutions to chance constrained programs, one of the area needing further investigation concerns the quality of the proposed solutions. As such, one appealing direction of research would be to nd specic contexts for which the heuristics integrating the robust binomial approach provide high quality approximation algorithms or for which theoretical upper bounds can be established. Also, another open question for a given chance constrained problem is the choice of the best metaheuristic to be applied.

Overall, we feel the need for further approaches for optimization under uncertainty developed from a data-driven perspective. While many real-world domains are characterized by huge and rich amounts of data, most existing models from stochastic optimization literature miss a direct connection with the data! Consequently, we consider treatment, analysis and exploration of experimental data as a prerequisite in designing techniques of optimization under uncertainty appealing in a practical sense. A rst step has been taken in this direction by the study of mixtures of Uniform and Gaussian distributions since there can be particular cases in which random data can be associated to such distributions. Estimation of parameters for these laws from a given sample, equivalent to a combinatorial optimization problem, can be a preceding step for resolution of chance constrained program which could take further advantage of it.

With regards to the application studies we covered, there are also subject to further investigations. For instance, for the stochastic partitioning of process networks, it is worth considering working on series-parallel graphs, which are similar in structure to the dataow application we have to deal with. Regarding the joint placement and routing problem, the GRASP method could be improved by the development of a more powerful local search algorithm based on cyclic exchanges of tasks. Additionally, the study of stochastic problem could be completed by taking into account the uncertainty on the inter-tasks bandwidths.

It should be emphasized that the problems we dealt with are close to the execution model for a real-world manycore architecture. Therefore, the resolution algorithms we conceived could be considered for a future integration into ΣC compilation chain, the result of a collaboration between CEA List laboratory 1 and Kalray, a semiconductor industry partner 2 . Furthermore, they target a broad spec- trum of multimedia applications from video encoding standards to motion targeting application or cognitive radio.

Of course, parallel implementations could facilitate the integration of heuristics based on the robust binomial approach and, in general, of optimization techniques to cope with uncertainty, into the compilation process for embedded manycore.

As a consequence, another interesting direction of research is to nd the most appropriate methods for parallelizing such algorithms, making ecient use of the resources oered by modern workstations (multi-cores, GPU of graphic cards etc.).

Furthermore, due to the intrinsic presence of uncertain data all along the compilation chain, other combinatorial problems than those we studied can be tackled from the stochastic point of view. Finally, we hope that our contribution is a good starting point for applying stochastic optimization to embedded manycores and that, in the future of this emerging eld, operations research techniques for dealing with uncertainty will become current practice.

•

  O. Stan, R. Sirdey, J. Carlier, D. Nace. L'apport de l'optimisation sous incertitudes pour les systèmes temps-réel embarqués. (Ecole de temps réel -ETR11), Brest, France. 2011 • O. Stan, R. Sirdey, J. Carlier, D. Nace. A Heuristic Algorithm for Stochastic Partitioning of Process Networks. (Proceedings of the 16th IEEE International Conference on System Theory, Control and Computing -ICSTCC), Sinaia, Romania. 2012 • O. Stan, R. Sirdey, J. Carlier, D. Nace. A GRASP for placement and routing of dataow process networks on manycore architectures. (Proceedings of the 8th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing -3PGCIC), Compiègne, France. 2013 • O. Stan, R. Sirdey, J. Carlier, D. Nace. The Robust Binomial Approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks. (Submitted to Journal of Heuristics), . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Massively parallel embedded systems . . . . . . . . . . . 16 1.3 Dataow models and stream programming . . . . . . . . 19 1.4 Sigma-C programming model and compilation . . . . . . 24 1.5 Research Motivations . . . . . . . . . . . . . . . . . . . . . 29

  Fig. 1.1 [108] captures the general exponential evolution trend of the number of individual computing units according to the release years of chips.

Figure 1 . 1 :

 11 Figure 1.1: Number of individual processing units in heterogeneous chips (e.g. AMD,NVidia graphics, IBM Cell BE, etc) and homogeneous chips (e.g. Intel Xeon, IMB Power, STM, Tilera, Kalray, etc)[START_REF] Louise | Programmability in the age of the manycore, beyond Stream Programming[END_REF]

Figure 1 . 2 :

 12 Figure 1.2: Clustered massively multi-core architecture(a -processor, b -processor cache, c -cluster shared memory, d -cluster, e -cluster interconnection network (NoC), f-external memory access controller, g -external memory, h -network adapter)[START_REF] Carpov | Scheduling for memory management and prefetch in embedded multi-core architectures[END_REF]

Fig. 1 .

 1 Fig.1.3 shows a sample of 4-by-4 grid-based NoC and its fundamental components.

Figure 1 . 3 :

 13 Figure 1.3: A structured 4×4 grid NoC and its components[START_REF] Bjerregaard | A survey of research and practices of Network-on-chip[END_REF]

  embedded systems into two categories: models based on rendez-vous and dataow process networks. In a rendez-vous model, tasks are modeled through concurrent sequential processes which communicate with each other only at certain synchronization points. Common examples of rendez-vous models are the CSP (Communicating sequential processes), the CCS (Calculus of Communicating Systems) or the model of communication used by the ADA language. In a dataow process network, the tasks are modeled by sequential processes which exchange data through communications channels. As such, a dataow program can be represented as a directed graph with the nodes representing the processes and the arcs representing the channels.

Fig. 1

 1 .4) are: Synchronous DataFlow (SDF), Cyclo-Static DataFlow (CSDF) and Dynamic DataFlow (DDF), with its subclass of Boolean DataFlow (BDF), all being particular classes of Kahn Process Networks (KPN).

Figure 1 . 4 :

 14 Figure 1.4: Representative dataow models.

  Figure 1.5: SDF model

  Figure 1.6: CSDF model

Figure 1 . 7 :

 17 Figure 1.7: Dynamic actors[START_REF] Carpov | Scheduling for memory management and prefetch in embedded multi-core architectures[END_REF]

1. 4

 4 Sigma-C programming model and compilation 1.4.1 Sigma-C programming language

Figure 1 . 8 :

 18 Figure 1.8: A ΣC graph example[START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF]

Figure 1 . 9 :

 19 Figure1.9: ΣC compilation chain[START_REF] Sirdey | Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles[END_REF]

  Most of existing studies treating optimization problems for embedded parallel architectures propose deterministic models. Still, one of characteristics of these systems is the presence of intrinsic uncertain data occurring in the denition of these problems, such as execution times or latencies. Moreover, experimental studies from both elds of operations research and program compilation (for details, see sections 1.5.3 and respectively 2.1.1) have shown that considering a xed value for the uncertain parameters, respectively execution times (usually the mean value), can lead to wrong estimates and optimization solutions not always feasible.

Fig. 1 .

 1 10 [158] several relevant properties of the execution time for a task are revealed. The darker upper curve represents the set of all execution time. The shortest execution time is often called best-case execution time (BCET) and the longest is called worst-case execution time (WCET). The other envelope represents a subset of the measures of the execution times. The minimum and maximum of the lower curve are the minimal, respectively the maximal observed execution times. Since, in most cases, the space of all possible executions is too large to fully explore, and also because of the undecidability problem associated to the running of an arbitrary program, it is not possible to determine the exact worst and best case execution times.

Figure 1 . 10 :

 110 Figure1.10: Some properties of the execution times of a real-time task[START_REF] Wilhelm | The worst-case execution-time problem : overview of methods and survey of tools[END_REF]

Figure 2 . 1 :

 21 Figure 2.1: Conceptual classication of combinatorial optimization problems (COP)[START_REF] Bianchi | A survey on metaheuristics for stochastic combinatorial optimization[END_REF]

0 where b 1

 1 and b 2 are two dependent random variable such P (b 1 = 5, b 2 = 3) = 0.5 and P (b 1 = 2, b 2 = 4) = 0.5. Let S 1 be the polyhedral set satisfying 2x 1 + x 2 ≥ 5 and x 1 + x 2 ≥ 3 and S 2 the polyhedral set satisfying 2x 1 + x 2 ≥ 2 and x 1 + x 2 ≥ 4.

Figure 2 . 2 :

 22 Figure 2.2: Example of a non-convex chance constrained program

5 .

 5 Approximation justied by De Moivre-Laplace theorem (rst proved in 1718), showing the convergence in distribution of a binomial law towards a Laplace-Gaussian distribution.

Figure 2 . 3 :

 23 Figure 2.3: Example of test statistics

Figure 2 . 4 :

 24 Figure 2.4: (a)NS=1000 (b)NS=10000

3: while R = ∅ do 4 :D

 4 = {r ∈ R : O(r) = T rue} while Output: S * Input: g and G functions Input: ξ(1) , . . . , ξ(NS) , ε, α 1: R = {r : residual decisions} 2: S * = ∅ 3: while R = ∅ do 4: D = {r ∈ R : O s (r) = T rue}

  7.A one line OpenMP pragma will do the trick.

  Input: r ∈ R, G, ξ(1) , . . . , ξ(NS) Input: N S, ε, α 1: Compute k(N S, ε, α) 2: nbRespConstr = 0 3: for i = 1 to N S do 4:

N

  a = {n a ∈ N : O(n a ) = T rue} stop=T rue Output: s Input: n, p i for i = 1, . . . , n, m, C j for j = 1, . . . , m Input: wi (1) , . . . , wi (N S) , ∀i = 1, . . . , n ε, α ∈ (0, 1) Input: s 0 , initial solution 1: s = s 0 2: stop=F alse 3: repeat 4: N a = {n a ∈ N : O s (n a ) = T rue} 5: bestN = argmax na∈Na P (n a ) 6:if P (bestN) ≥ P (s )

(2. 10 )

 10 with D the set of constraints. Solving 2.10 consists in nding an x * such that z * = h(x * , ν) ≤ z = h(x, ν), ∀x ∈ D. If we are interested in a robustness on the result with a guaranteed probability 1 -p, the following stochastic model should be solved:

Contents 3 . 1 74 3. 4 77 3. 5

 31744775 Problem statement . . . . . . . . . . . . . . . . . . . . . . 72 3.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3 Preliminaries: Deterministic algorithm . . . . . . . . . . Chance constrained version . . . . . . . . . . . . . . . . . Computational results . . . . . . . . . . . . . . . . . . . . 79 This chapter is dedicated to the problem of stochastic partitioning of process networks, arising in the resource allocation step of the compilation process of a dataow application for manycore systems (see Chapter 1 for more details on the context).

  nodes of capacity equal to 2. A greedy partitioning using the total anity would have begun by putting together the vertices B and C, resulting in a solution of cost 4. Instead, a greedy partitioning based on relative anity would match the vertices A and B (and C and D), with γ({A}, {B}) = γ({C}, {D}) = 0.7 and γ({B}, {C}) = 0.6, obtaining a solution of cost 3 (see 3.1b).

Figure 3 . 1 :

 31 Figure 3.1: (a) A graph example (b)2-partition using the relative anity[START_REF] David | Etude et realisation d'une architecture modulaire et recongurable : Projet MODULOR[END_REF]

Algorithm 3 . 1 :

 31 RG_PARTInput: W , N , R, S vr for each {v ∈ V , r ∈ R} 1: Initialization W = V 2: Assign the rst min(|V |, |N |) vertices in lexicographic order to the |N | nodes and update the set W 3: Find an admissible assignment (v * , n * ) (v * ∈ W , n * ∈ N ) cf. Def. 3.4, if any, with maximal relative anity:

3 . 2 ,

 32 named RG_PART_STOCH, is used for solving the chance constrained version of the Node Capacitated Graph Partitioning problem.

Algorithm 3 . 2 :

 32 RG_PART_STOCHInput: W , N , R, ε, α, N S, S(i)vr for each {v ∈ V , r ∈ R, i = 1...N S } 1: Initialization W = V 2:Assign the rst min(|V |, |N |) vertices in lexicographic order to the |N | nodes and update the set W 3: Find an admissible stochastic assignment

. 3 - 3 .

 33 8 are: the minimal capacity of each node for which we obtain a feasible solution (column C), the solution value (column sol) and the average execution time for 10 iterations (column time).

Contents 4 . 1 91 4. 3 95 4. 4 100 4. 5

 419139541005 Problem statement . . . . . . . . . . . . . . . . . . . . . . 90 4.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . Deterministic algorithm . . . . . . . . . . . . . . . . . . . Stochastic algorithm . . . . . . . . . . . . . . . . . . . . . . Computational results . . . . . . . . . . . . . . . . . . . . 102

  As shown in Fig.4.1, there are dierent criteria for classifying mapping technologies in function of the target architecture, when the placement takes place (at run time or design time) or the hierarchy involved. For static mappings, the

Figure 4 . 1 :

 41 Figure 4.1: Classifying mapping approaches...

  .

4. 2 . 1

 21 Deterministic mapping 4.2.1.1 Static mapping Static mapping methodologies are adapted to static workload scenarios for predened applications with known behavior (in terms of computation and communication) and for xed architectures. Since they are performed at design time and have a global view of the system, they can found better quality mappings compared with run time mapping (which explore only the neighborhoods of the mapped tasks).

Denition 4 . 1 .

 41 The anity of S for T is given by :α(S, T ) = (v,w)∈δ(S,T ) q vw .with δ(S, T ) = {(v, w) : v ∈ S; w ∈ T }. It follows that α(S, T ) = α(T, S).

Denition 4 . 2 .

 42 The total anity of S (similarly for T ) is given by β(S) = α(S, V \ S).

Denition 4 . 3 .

 43 The relative anity of S for T is dened as γ(S, T )

98CHAPTER 4 .

 4 JOINT PLACEMENT AND ROUTING UNDER UNCERTAINTY Denition 4.5. A fusion between the nodes n and m is admissible if:

  t∈V \W :g(t)=n s tr + t∈V \W :g(t)=m s tr ≤ C r , ∀r ∈ R and all the ows for tasks belonging to n and m are reroutable through G .

Algorithm 4 . 2 :

 42 GRASP for joint placement and routing: construction_phase Input: V , N , R, k 1: Initialization of the set of unassigned tasks W = V 2: Assign the rst min(|V |, |N |) vertices to the |N | nodes and update sets W , F 3: Build the list of k restricted candidate decisions [rcl] made of admissible assignments (cf. Def.4.4) and admissible fusions (cf. Def.4.9) 4: Select at random

108CHAPTER 4 .

 4 JOINT PLACEMENT AND ROUTING UNDER UNCERTAINTY

Table 1 .

 1

1, there are two modes for the executions times, possible with dierent variances, corresponding to the two sequences of instructions. Instead, for the

Table 1.1: A code snippet with a 2 modes distribution if condition then S 1 else S 2 end if code in Table 1.2 with n taking values between

1 and N , S 1 and S 2 being two linear sequences of instructions, the distribution has 2N modes (the gure showing a possible envelope of the distribution for the case when N = 4). Running a more

Table 1.2: Another code snippet with multi-modal distribution

Table 1 . 3

 13

: Code snippet showing possible tasks dependency T1 T2 Execution times T1 and T2

  15.79081x 826 -8.598819x 827 -1.88789x 828 -1.362414x 829 -1.526049x 830 -0.031883x 849 -28.725555x 850 -10.792065x 851 -0.19004x 852 -2.757176x 853 -12.290832x 854 + 717.562256x 855 -0.057865x 856 -3.785417x 857 -78.30661x 858 -122.163055x 859 -6.46609x 860 -0.48371x 861 -0.615264x 862 -1.353783x 863 -84.644257x 864 -122.459045x 865 -43.15593x 866 -1.712592x 870 -0.401597x 871 + x 880 -0.946049x 898 -0.946049x 916 ≥ b ≡ 23.387405

Table 2 .

 2

	1: Example of robust formulation (EX_RCP) against chance constrained program (EX_CCP)
	EX_CCP	EX_RCP
	min x∈R n x

s.t. P (f (x, δ) > 0) ≤ ε min x∈R n x s.t. x ∈ x∈R n ,δ∈∆

Table 2 . 2 :

 22 Methods for solving chance constrained programs

	Category	Characteristics	Some references

Table 2 .

 2 3: The two types of errors when making decisions using statistical hypotheses

4. Example suggested at: http://phdtutor.com/stat_course/Hypothesis_Testing.aspx `````````````D ecision State of nature

Table 2 .

 2 4: Examples values for k(N S, 0.90, 0.05) in function of N S.

	N S k(N S, 0.90, 0.05)
	10	-
	20	-
	30	29
	40	38
	50	48
	100	94
	1000	915

Table 2 .

 2 5: Values of k in function of α and ε

				NS=100		NS=1000		NS=10000
	H H α	H	H H H ε	0.01	0.05	0.1	0.01	0.05	0.1	0.01	0.05	0.1
	0.01	-	99	96	996	965	921	9922	9550	9069
	0.05	-	98	94	995	961	915	9916	9536	9049
		0.1	-	98	94	994	959	912	9913	9528	9038

Table 2 .

 2 6.

Table 2 .

 2 6: Solving a chance constrained problem with a RBA-based heuristic...

	1: problem formulation: g, G, x, ξ, ε
	2: sample acquisition for ξ
	3: pre-treatment of the sample: preliminary analysis, bootstrapping etc.
	4: check existence of heuristic for solving the deterministic version
	5: if ∃heuristic for deterministic case then
	6:	choice of the appropriate existing heuristic for deterministic case
	7:	replace the admissibility oracle with a stochastic one
	8:	integrate the stochastic oracle to the chosen heuristic
	9: else
	10:	choice of an appropriate heuristic
	11:	dene a stochastic admissibility oracle
	12:

Table 2 .

 2 7: General schema for a constructive algorithm

	Deterministic	Stochastic
	Input: g and G functions, ξ

1: R = {r : residual decisions} 2: S * = ∅

Table 2 .

 2 8: Deterministic oracle vs. stochastic oracle

	Deterministic oracle O	Stochastic oracle O s
	Input: r ∈ R, G, ξ 1: if G(r, ξ) < 0 then 2: return T rue 3: end if 4: return F alse Output: T rue, F alse

Table 2 .

 2 9: General schema for hill climbing heuristic: bin packing problem

	Deterministic	Stochastic

Input: n, w i and p i for i = 1, . . . , n, m, C j for j = 1, . . . , m Input: s 0 , initial solution 1: s = s 0 2: stop=F alse 3: repeat 4:

  to n * and update the set W . Else merge n * 1 , n

*

2 6: If W = ∅ or there is neither any admissible assignment nor any admissible fusion, stop. Else, go to Step 3.

  to n * and update the set W . Else merge n * 1 , n *

	2 .

6: If W = ∅ or there is neither any admissible assignment nor any admissible fusion, stop. Else, go to Step 3.

Table 3 .

 3 1: Computational results of RG_PART heuristic for deterministic case: grid problems

	Inst.	#Vertices	#Nodes	C Multi Time (sec.)
	Grid 4 × 4	16	4	4	8	≈0
	Grid 10 × 10	100	5	20	28	≈0
	Grid 23 × 23	529	14	40	150	0.12

Table 3 .

 3 2: Computational results of RG_PART heuristic for deterministic case: Johnson instances

	Name	|V |	C Best known Multi
	Gsub.500	500	250	206	236
	G1000.0025	1000	500	95	118
	G1000.005	1000	500	445	509
	G1000.01	1000	500	1362	1461
	G1000.02	1000	500	3382	3526
	G124.02	124	62	13*	15
	G124.04	124	62	63*	68
	G124.08	124	62	178	183
	G124.16	124	62	449	471
	G250.01	250	125	29*	36
	G250.02	250	125	114	127
	G250.04	250	125	357	378
	G250.08	250	125	828	855
	G500.005	500	250	49*	61
	G500.01	500	250	218	253
	G500.02	500	250	626	669
	G500.04	500	250	1744	1825
	U1000.05	1000	500	1*	6
	U1000.10	1000	500	39*	69
	U1000.20	1000	500	222	299
	U1000.40	1000	500	737	866
	U500.05	500	250	2*	12
	U500.10	500	250	26*	68
	U500.20	500	250	178*	196
	U500.40	500	250	412	412

Table 3 .

 3 3: Computational results of the stochastic method for N S = 100, ε = 0.05,

		α = 0.05: grid problems
		1st test			2nd test
	Name	#nodes	sol	time	C	sol	time
	Grid 4 × 4	6	14	≈ 0	4.71	12	≈ 0
	Grid 10 × 10	6	38	0.02 s	23.3	29	0.01 s
	Grid 23 × 23	16	182	1.12 s	44.1	173	0.99 s

Table 3 .

 3 4: Computational results of the stochastic method for N S = 1000, ε = 0.05, α = 0.05: grid problems

			1st test		2nd test
	Name	#nodes	sol	time	C	sol	time
	Grid 4 × 4	6	14	≈ 0	4.712	12	≈ 0
	Grid 10 × 10	6	37	0.16 s	23.273	37	0.13 s
	Grid 23 × 23	16	182	11.23 s	44.13	172	9.65 s
	Table 3.5: Computational results of the stochastic method for N S = 1000, ε = 0.01, α = 0.01: grid problems
			1st test		2nd test
	Name	#nodes	sol	time	C	sol	time
	Grid 4 × 4	6	14	≈ 0	4.74	10	≈ 0
	Grid 10 × 10	6	37	0.15 s	23.36	37	0.13 s
	Grid 23 × 23	16	182	10.75 s	44.183	193	9.67 s

Table 3 .

 3 6: Computational results of the stochastic method for N S = 100, ε = 0.05, 1 -α = 0.95: Johnson problems

		1st test		2nd test
	Name	#nodes	sol	time	C	sol	time
	Gsub.500	3	301	5,57	288,300	244	5,55
	G1000.0025	3	135	58,97	575,800	131	70,11
	G1000.005	3	649	62,23	575,900	513	72,10
	G1000.01	3	1865	65,30	575,900	1456	77,36
	G1000.02	3	4481	68,78	575,940	3579	74,10
	G124.02	3	18	0,16	71,650	21	0,11
	G124.04	3	91	0,16	71,650	72	0,11
	G124.08	3	233	0,16	71,670	199	0,11
	G124.16	3	585	0,16	71,680	475	0,12
	G250.01	3	40	0,75	144,200	38	0,64
	G250.02	3	162	0,76	144,260	128	0,63
	G250.04	3	485	0,78	144,250	393	0,64
	G250.08	3	1074	0,77	144,200	862	0,65
	G500.005	3	68	5,14	288,370	67	5,20
	G500.01	3	308	5,36	288,340	269	5,04
	G500.02	3	860	5,42	288,280	679	5,44
	G500.04	3	2287	5,56	288,270	1835	5,60
	U1000.05	3	17	67,76	576,100	16	73,50
	U1000.10	3	101	65,55	576,100	110	77,74
	U1000.20	3	417	67,80	576,200	303	75,23
	U1000.40	3	1370	68,26	576,300	1018	77,00
	U500.05	3	10	5,05	288,390	7	5,27
	U500.10	3	88	5,58	288,270	66	5,38
	U500.20	3	278	5,49	288,200	396	5,43
	U500.40	3	663	5,23	288,380	574	5,28

Table 3 .

 3 7: Computational results of the stochastic method for N S = 1000, ε = 0.05, 1 -α = 0.95: Johnson problems

			1st test			2nd test
	Name	#nodes	sol	time	C	sol	time
	Gsub.500	3	298	26,72	288,240	252	18,94
	G1000.0025	3	136	139,30	576,030	134	119,48
	G1000.005	3	653	143,70	576,060	528	123,52
	G1000.01	3	1866	141,00	576,060	1470	125,70
	G1000.02	3	4482	140,86	576,040	3599	127,95
	G124.02	3	17	1,39	71,662	17	0,91
	G124.04	3	87	1,37	71,654	68	0,92
	G124.08	3	237	1,36	71,660	182	0,93
	G124.16	3	599	1,35	71,653	479	0,91
	G250.01	3	39	5,84	144,310	39	4,00
	G250.02	3	163	5,81	144,310	129	4,04
	G250.04	3	483	5,78	144,295	387	3,99
	G250.08	3	1080	5,75	144,257	872	3,98
	G500.005	3	69	26,67	288,240	68	18,88
	G500.01	3	320	26,74	288,240	258	19,00
	G500.02	3	853	26,87	288,250	668	19,15
	G500.04	3	2283	26,76	288,250	1829	19,18
	U1000.05	3	18	140,90	576,050	6	125,70
	U1000.10	3	74	139,40	576,060	115	126,80
	U1000.20	3	417	141,40	576,030	339	126,80
	U1000.40	3	1370	143,51	576,080	1032	132,60
	U500.05	3	16	26,73	288,300	2	19,49
	U500.10	3	105	26,90	288,260	75	19,32
	U500.20	3	289	27,15	288,250	289	19,21
	U500.40	3	663	26,73	288,240	569	18,89

Table 3 .

 3 8: Computational results of the stochastic method for N S = 1000, ε = 0.01, 1 -α = 0.99: Johnson problems

			1st test			2nd test
	Name	#nodes	sol	time	C	sol	time
	Gsub.500	3	298	25,32	288,610	240	18,94
	G1000.0025	3	137	141	576,470	132	121,51
	G1000.005	3	654	140,77	576,520	519	127,54
	G1000.01	3	1870	141,66	576,520	1467	125,74
	G1000.02	3	4475	141,23	576,530	3544	128,78
	G124.02	3	17	1,35	71,865	17	0,9
	G124.04	3	87	1,34	71,825	73	0,92
	G124.08	3	237	1,33	71,851	187	0,92
	G124.16	3	599	1,33	71,831	484	0,91
	G250.01	3	39	5,73	144,548	40	4
	G250.02	3	163	5,73	144,530	132	4
	G250.04	3	483	5,65	144,515	383	4,06
	G250.08	3	1085	5,65	144,523	856	3,95
	G500.005	3	69	25,33	288,490	68	19,38
	G500.01	3	320	25,32	288,540	258	19
	G500.02	3	853	25,2	288,530	687	19,6
	G500.04	3	2283	25,25	288,520	1852	19,3
	U1000.05	3	20	141,79	576,550	1	125,76
	U1000.10	3	74	140,69	576,520	90	128,03
	U1000.20	3	421	143,14	576,570	339	131,14
	U1000.40	3	1376	145,14	576,580	1137	127,47
	U500.05	3	16	26,73	288,570	2	19,17
	U500.10	3	105	25,75	288,560	62	19,03
	U500.20	3	289	25,4	288,560	289	19,15
	U500.40	3	663	25,08	288,570	569	19,41

  4.9. A fusion between the nodes n and m is stochastically admissible if:

	the sum N S i=1 χ(P t 1 :g(t 1 )=n	s(i) t 1 r > C r }
	∨ {∃r :	s(i) t 1 r +	s(i) t r -	s(i) tr > C r }
	t 1 :t 1 =t;g(t 1 )=g(t)
	∨ {∃r :
	t 1 :t 1 =t ;g(t 1 )=g(t )
	the sum
	N S
	χ({∃n , r :
	i=1
					s(i) t r > C r }
		t :g(t )=n
	∨ {∃r :	s(i) t r +	s(i) tr > C r }
	t :g(t )=n
	∨ {∃r :	s(i) t r -	s(i) tr > C r }}
	t :t =t;g(t )=n i
	where χ(P a ) = 1 if and only if predicate P a is true.

t:g(t)=n s(i) tr > C r } ∨ {∃r : t:g(t)=n s(i) tr + t :g(t )=m

s(i) t r > C r }),

is less than N S -k(N S, 1 -ε, α), where χ(P f ) = 1 if and only if the predicate P f is true. all the ows for tasks belonging to n and m are reroutable through G .

Therefore, the only major modications for the greedy algorithm 4.2 are during the step 2 and 3 in which the admissibility criterion are used.

As for the post-optimization step, the local search is based on the notions of admissible transfer or admissible exchange which are dened with regards to the weights of the tasks and the capacity of each node. Thus, we have to modify these two notions by applying the robust binomial approach.

Denition 4.10. For a given assignment g, a transfer of task t, already assigned to node n i = g(t), to another node n is stochastically admissible if: the ows f ∈ F between t and other tasks t for which g(t ) = n and w(f ) > 0 are reroutable. the sum N S i=1 χ(P a ) < N S -k(N S, 1 -ε, α) with P a :{{∃n = n = n i , ∃r : Denition 4.11. For a given assignment g, an exchange of two tasks t and t from node g(t) to node g(t ) and vice versa is stochastically admissible if: the ows in F having as source or sink t and/or t are still routable. a ) < N S -k(N S, 1 -ε, α) with P a :{{∃n = g(t) = g(t ), ∃r :

Table 4 .

 4 The random tasks graphs instances generated with TGFF are 1920 graphs with the number of vertices V varying between {50, 100, 200} to be placed on a clusterized bi-dimensional architecture with N = 4 or N = 16 nodes. For each set of graphs composed of 50, 100 and respectively 200 vertices, four seeds are used for generating dierent communications and occupancy ratios.

		1: Grid instances
	Inst.	#Vertices	#Nodes	C n Sol.
	Grid 4 × 4	16	4	4	8
	Grid 10 × 10	100	16	7	70
	Grid 12 × 12	144	4	40	31
	Grid 18 × 18	324	9	40	88
	Grid 23 × 23	529	16	40	162
	kinds of resources for the node capacity: cardinality, computing core occupancy and
	memory footprint. The application has to be placed on a bi-dimensional torus 4 × 4.

Table 4 .

 4 2: Results of GRASP method for grid problems

			k=2			k=3			k=4
	Name	GR	PS-1	PS-2	GR	PS-1	PS-2	GR	PS-1	PS-2
	Grid4x4.inst	11	11	10	12	10	11	13	12	10
	Grid10x10.inst	73	69	69	75	70	69	76	69	69
	Grid12x12.inst	34	31	30	34	31	30	36	31	33
	Grid18x18.inst	92	86	88	91	91	91	99	98	91
	Grid23x23.inst	174	164	173	184	173	177	190	184	182

Table 4 .

 4 5: Computation results for N S = 100: grid problems

	instance	α	sol.	ε = 0.05 C n time sol. C n ε = 0.1	time
	grid4×4	0.01 0.05	10 10	1.25 1.25	≈0 ≈0	12 12	1.25 1.25		≈0 ≈0
	grid10×10	0.01 0.05	74 72	1,15 1,15	0,92 0,52	76 69	1,15 1,15		0,56 0,48
	grid12×12	0.01 0.05	30 32	1 1	77 58,5	28 28	1 1	77,68 67
	grid18×18	0.01 0.05	92 94	1 1	600 600	89 94	1 1		600 600

Table 4 .

 4 6: Computation results for N S = 1000: grid problems

	instance	α	sol.	ε = 0.05 C n time	sol.	ε = 0.1 C n	time
	grid4×4	0.01 0.05	10 10	1,25 1,25	≈0 ≈0	12 8	1,25 1,25		≈0 ≈0
	grid10×10	0.01 0.05	75 76	1,15 1,15	0,69 0,72	78 79	1,15 1,15		0,79 0,95
	grid12×12	0.01 0.05	29 30	1 1	230 235,3	31 29	1 1	210,6 263
	grid18×18	0.01 0.05	95 91	1 1	600 600	94 93	1 1		600 600

Table 4 .

 4 7: Computation time for N S = 100, ε = 0.05, α = 0.05: TGFF problems

			V
		50	100	200
	#instances	640	640	640
	Time (sec.)	16,91	140,69	486,68

Table 4 .

 4 8: Repartition of solutions for N S = 100, ε = 0.05, α = 0.05 in function of C n : TGFF problems cases, the value of the stochastic solution is at most 5% dierent from the one of the deterministic instance.

		Multiplication factor for C n
		1	1.15	1.25	1.5	1.75
	% instances	68,33	13,91	1,46	1,09	2,81
	than 38% of

Table 4 .

 4 9: Quality of stochastic vs. deterministic solutions for same C n : TGFF problems

		%instances
		<sol d	41.92
		{sol d ; sol d + 5%}	38.87
	sol s	{sol d + 5%; sol d + 7%}	5.11
		{sol d + 7%; sol d + 10%} 4.88
		Other	9.22

Table 4 .

 4 10: Results stochastic GRASP for ε = 0.1 and α = 0.05: motion target application

	Inst.	#Vertices	#Nodes	N S Sol. placement Sol. routing
	scenario1.list	57	16	33	16480	16480
	scenario2.list	57	16	85	16512	16512
	scenario3.list	57	16	35	16504	16504
	scenario4.list	57	16	85	16552	16552

Tasks Graph for Free: http://ziyang.eecs.umich.edu/ dickrp/tg/

http://www-list.cea.fr/

http://www.kalray.eu/

Acknowledgements

First of all, I want to address my grateful acknowledgments to Mr. Jacques