Cédric Flageul

Iztok Tiselj

Convergence rate of individual and global quantities in Direct Numerical Simulations

Keywords: Direct Numerical Simulation, Uncertainty Quantification, Sampling Error

Typical individual quantities in Direct Numerical Simulations of statistically steady flows are converging at a rate of 1/ √ T , where T is the averaging time of the simulation. However, global quantities that represent integral momentum balance in the computational domain can exhibit a faster convergence rate of 1/T . This faster convergence rate is analysed and explained. Theoretical predictions are supported with a Direct Numerical Simulation.

1

T , with T the averaging time.

However, following Oliver et al. [START_REF] Oliver | Estimating uncertainties in statistics computed from direct numerical simulation[END_REF] , it is known that individual statistical quantities are converging slower, at a rate of 1 √ T . This is the expected convergence rate for an uncorrelated signal, and for a weakly correlated one approaching independence at large separations, such as a turbulent signal (Theorem 27.4 in Billingsley [START_REF] Billingsley | Probability and measure[END_REF] ).

In the present paper, we show that both aforementioned convergence rates hold and are not contradictory. This is confirmed by statistics taken from a DNS. Thus, we demonstrate that the methodology for evaluation of statistical uncertainties proposed by Thompson et al. [START_REF] Thompson | A methodology to evaluate statistical errors in DNS data of plane channel flows[END_REF] is not conservative as it provides an error which is converging faster than individual quantities.

The structure of the remaining part of the paper is as follows. First, we show that the residual norms proposed by Thompson et al 2 are converging at a rate of [START_REF] Oliver | Estimating uncertainties in statistics computed from direct numerical simulation[END_REF] T . Then, we show DNS results in agreement with our analysis, alongside with some concluding remarks and comments.

The following is tailored to the time scheme used by Andrade et al. [START_REF] Andrade | Analysis of uncertainties and convergence of the statistical quantities in turbulent wall-bounded flows by means of a physically based criterion[END_REF] . It could be simply adapted to fit another time scheme. The velocity in direction i and at time step n is written u n i . The pressure at time step n is written p n . The time step is written dt. Spatial derivativation in direction i is written ∂ i and δ i,j is the Kronecker delta. In the present study, X, Y and Z stand for the streamwise, wall-normal and spanwise directions, respectively. The prediction step is a combination of a 2 nd order Adams-Bashforth and Crank-Nicolson, and there is an imposed constant source term (f ) in the streamwise direction driving the flow:

u * i -u n i dt = - 3 2 ∂ j u n i u n j + 1 2 ∂ j u n-1 i u n-1 j -∂ i p n + 1 Re ∂ jj u * i + u n i 2 -f δ iX (1)
The correction step enforces the continuity equation

u n+1 i -u * i dt = -∂ i p n+1 + ∂ i p n (2)
as the pressure p n+1 is obtained with the following Poisson equation:

∂ ii p n+1 = ∂ ii p n + ∂ i u * i dt (3)
From equation (2), one can derive

u * i = u n+1 i + dt ∂ i p n+1 -∂ i p n (4)
Equation ( 4) allows us to eliminate u * i . The resulting time scheme is:

u n+1 i -u n i dt = - 3 2 ∂ j u n i u n j + 1 2 ∂ j u n-1 i u n-1 j -∂ i p n+1 + 1 Re ∂ jj u n+1 i + u n i 2 + dt 2 ∂ i p n+1 -p n -f δ iX (5)
At this point, the time-discrete momentum equation ( 5) is averaged in time. This corresponds to a summation a) Electronic mail: cedric.flageul@ijs.si b) Electronic mail: iztok.tiselj@ijs.si from the time step n = 1 to n = N , followed by a division by N :

u N +1 i -u 1 i N dt + 1 2N ∂ j u N i u N j -u 0 i u 0 j - 1 N Re ∂ jj u N +1 i -u 1 i 2 + dt 2 ∂ i p N +1 -p 1 + ∂ i p N +1 -∂ i p 1 N = N k=1 -∂ j u k i u k j -∂ i p k + 1 Re ∂ jj u k i -f δ i,X N (6)
On the right-hand side of equation ( 6) is the exact momentum equation averaged in time over the simulation. Thus, the left-hand side of this equation corresponds to a residual. When N is large enough, the velocity and pressure fields at the initial time steps are independent from the ones at the final time steps. As the flow is statistically steady, the initial and final fields are described by the same probability density function. Therefore, the collected statistics will converge towards the exact time-averaged momentum equation at a rate of 1 N , or 1 T . This convergence rate was obtained without any specific assumption. Thus, it does not depends on the geometry or on the Reynolds number, and is valid everywhere inside the computational domain, as long as the initial turbulent flow is fully developped.

Hereafter, we focus on the streamwise and spanwise momentum equations which are useful as indicators of the statistical uncertainty in the channel flow. Both equations are averaged over the homogeneous directions X and Z. Quantities averaged in space are written with one overbar. The resulting space-averaged time-averaged discrete momentum equations are:

u N +1 X -u 1 X N dt + 1 2N ∂ Y u N X u N Y -u 0 X u 0 Y - 1 N Re ∂ Y Y u N +1 X -u 1 X 2 = N k=1 -∂ Y u k X u k Y + 1 Re ∂ Y Y u k X -f N (7) u N +1 Z -u 1 Z N dt + 1 2N ∂ Y u N Z u N Y -u 0 Z u 0 Y - 1 N Re ∂ Y Y u N +1 Z -u 1 Z 2 = N k=1 -∂ Y u k Z u k Y + 1 Re ∂ Y Y u k Z N (8)
To measure the convergence rate, we define the following quantities:

E X 0 (y) = N k=1 -∂ Y u k X u k Y + 1 Re ∂ Y Y u k X -f N E Z 0 (y) = N k=1 -∂ Y u k Z u k Y + 1 Re ∂ Y Y u k Z N E i 0 2 = 1 Re τ Reτ y + =0 E i 0 y + 2 (9)
Based on this, one can recover the residual error E i R , as defined by Andrade et al. [START_REF] Andrade | Analysis of uncertainties and convergence of the statistical quantities in turbulent wall-bounded flows by means of a physically based criterion[END_REF] :

E i R y + = y + l=0 E i 0 (l) ( 10
)
E i R 2 = 1 Re τ Reτ y + =0 E i R y + 2 (11)
The residual error E i U , also defined by Andrade et al. [START_REF] Andrade | Analysis of uncertainties and convergence of the statistical quantities in turbulent wall-bounded flows by means of a physically based criterion[END_REF] , can be obtained by integrating

E i R . Obviously, E i 0 , E i R and E i U
should have the same convergence rate.

For the spanwise momentum equation, the global quantity E Z 0 2 is completed by the following individual quantities:

Z -Conv = 1 Re τ Reτ y + =0   N k=1 ∂ Y u k Z u k Y N   2 (12)
Z -Dif f = 1 Re τ Reτ y + =0   N k=1 1 Re ∂ Y Y u k Z N   2 (13)
Regarding the conversion towards wall-units, a friction velocity -the theoretical one -can be derived from the constant source term f used in the momentum equation. Another friction velocity -the measured one -can be derived from the averaged streamwise velocity. In the present study, the former is used as it is not plagued by any statistical uncertainty. The definition of E i R , as given by equation (10), uses an integration constant to enforce E i R (y + = 0) = 0. In the present study, we weakly enforce this condition at y + = 0 by using an integration constant derived from the theoretical friction velocity, as in Andrade et al. [START_REF] Andrade | Analysis of uncertainties and convergence of the statistical quantities in turbulent wall-bounded flows by means of a physically based criterion[END_REF] . This choice, combined with the symmetry of the case at hand, strongly enforces

E i R (y + = Re τ ) = 0.
Hereafter, we present DNS results supporting our analysis. For convenience, all quantities plotted are integrated squared residuals. Thus, expected convergence rates are also squared and individual quantities are expected to converge at a rate of The present DNS was performed with the pseudospectral code previously used in Flageul and Tiselj [START_REF] Flageul | Impact of unresolved smaller scales on the scalar dissipation rate in direct numerical simulations of wall bounded flows[END_REF] . The friction Reynolds number is 180. The shape and the resolution of the computation is equal to the DNS of Moser et. al. [START_REF] Moser | Direct numerical simulation of turbulent channel flow up to Reτ = 590[END_REF]

L X = 4πh, L Y = 2h, L Z = 4πh 3 , ∆ + X = 17.7, 0.054 ≤ ∆ + Y ≤ 4.
4 and ∆ + Z = 5.90. This resolution was recognized as slightly under-resolved DNS in the study by Vreman and Kuerten 7 . This is not really an issue here as this paper is focused only on statistical uncertainty and not on the numerical accuracy. The time step in the DNS is 0.027 wall-units, and statistics are collected every 10 time steps. 4 million time steps are performed, so the averaging time is 108 000 wall-units and the effective averaging time, as proposed by Vinuesa et. al. [START_REF] Vinuesa | Convergence of numerical simulations of turbulent wall-bounded flows and mean cross-flow structure of rectangular ducts[END_REF] , is T = T uτ h L X L Z L X,min L Z,min = 1 760, with L X,min = 6h and L Z,min = 3h.

As shown in Figure 1, the global quantities E X 0 2 and E X R 2 associated with the streamwise momentum equation are converging at the expected rate of 1 T 2 . As shown in Figure 2, the squared residuals associated with individual quantities are converging at a rate of 1 T , while the squared residual associated with the global quantity E Z 0 2 is converging at the faster rate of 1 T 2 . For the sake of completeness, regressions were performed to extract the convergence rate of the quantities plotted in Figures 1 and2. The regression was restricted to averaging times longer than 10 4 samples -10 5 time steps, or 2 700 time units -to limit transient effects. Table I shows that the convergence rate of global quantities is very close to the theoretical prediction. Table II shows that the individual quantities are also converging at a rate very close to the theoretical prediction (Oliver et al. [START_REF] Oliver | Estimating uncertainties in statistics computed from direct numerical simulation[END_REF] , Billingsley [START_REF] Billingsley | Probability and measure[END_REF] ).

The authors have presented an original analysis show- Squared residuals 2.11 ing that different quantities can have different convergence rates, and have provided DNS evidences supporting it. Overall, individual quantities are expected to converge at a rate of 1 √ T . However, a few global quantities, directly related to the integral equations solved are converging faster, at a rate of [START_REF] Oliver | Estimating uncertainties in statistics computed from direct numerical simulation[END_REF] T . The only global quantities the authors could identify are the ones directly derived from the conservation equations solved, as expressed equation (6).

T 1 T 2 E Z 0 2 Z -Conv Z -Dif f
E X 0 2 E Z 0 2 E X R 2 E Z R 2 Convergence Rate T -1.98 T -2.05 T -1.87 T -
One could try to multiply equation ( 5) by u n+1 i + u n i to obtain an equation for the kinetic energy as a global quantity. However, summation over time steps no longer leads to simplification. Thus, it seems that no other global quantity converging at a rate of 1 T can be derived on this ground, except linear transformations of the previous ones. As integration and derivation are linear transformations, the time-averaged equation of conservation of vorticity is also a global quantity converging at a rate of 1 T . The present analysis was focused on the momentum equation, but will also apply to transported scalars, such as the temperature or the enthalpy. In addition, this analysis is not restricted in any way to simple geometries such as the channel flow studied here and can be directly applied to DNS of more complex geometries. The main requirement is that the case studied must be statistically steady. The other is that the DNS should rely on a classical combination of implicit and explicit time schemes. The presented analysis should also apply to time schemes with a variable time step.

As a side remark, our analysis shows that the residuals associated with the global momentum equation depend only on the initial and final fields. Thus, provided one has kept those fields, one can estimate the error on the averaged momentum equation without using any averaged quantity. Indeed, this is of very limited use, except for an efficient on-the-fly estimation of this global error during the simulation.

A potentially interesting error estimator regarding individual statistical quantities for cases with symmetry or invariance under rotation could be derived from the lack of symmetry or invariance in the measured profile. This is left for future prospects. As a side note, the authors would like to stress that convergence rates correspond to asymptotic limits and long averaging time can be necessary to observe them, especially for low probability events (Bauer et al. [START_REF] Bauer | On the convergence and scaling of high-order statistical moments in turbulent pipe flow using direct numerical simulations[END_REF] ).

TABLE I .

 I Convergence rate for global quantities, averaging time T + > 2 700.

	1 T and 1 T 2
	FIG. 2. Convergence of individual and global quantities as-
	sociated with the spanwise momentum as a function of the
	averaging time. Dotted green line: E Z 0	2 . Dashed red line:
	Z -Conv. Dashed blue line: Z -dif f . Black lines: Conver-
	gence rates of 1 T and 1 T 2 .

TABLE II .

 II Convergence rate for individual quantities, averaging time T + > 2 700.

		Z -Conv	Z -dif f
	Convergence Rate	T -1.22	T -1.11

The authors would like to thank the Slovenian Re-search Agency for funding the study under the research project P2-0026. Data associated with the present paper are available online at https://repo.ijs.si/CFLAG/ convergence_rate under the GNU GPL v3 licence.


However, improved phylogenetic analyses of nucleotide sequences (RY-coding) from the same genes consistently retrieve the classical hypothesis of hexapod monophyly.

Text (741 words)

A recent paper (1) suggested, rather cautiously, that hexapods (insects plus collembolans in their dataset) might be diphyletic, rather than forming a monophyletic group. In their results, collembolans appeared well separated from other insects and emerged before crustaceans. Such an unexpected result has huge consequences for the interpretation of both morphological and developmental evolution in arthropods (2) and therefore deserves further scrutiny especially from the methodological point of view.

The authors drew their conclusions from maximum likelihood and Bayesian analyses at the amino acid level of four of the 12 mitochondrial proteins for both the original data set of 35 taxa and a reduced data set of 15 taxa. However, phylogenetic analyses of amino acids currently suffer from potential caveats. First, the currently available models of mitochondrial amino acid substitution are based on empirically deduced matrices from mammalian dominated sequence databases. Second, the maximum likelihood implementation used by the authors does not model the variation of rate across sites, known to be one of the most important parameter of the likelihood model (3). And third, bias in nucleotide composition also affects the amino acid composition of the gene product causing potential problems for phylogenetic reconstruction (4). Some of these pitfalls might be avoided by analyzing nucleotide sequences for which more realistic models of sequence evolution and powerful reconstruction methods are available.

In particular, we have recently shown in the case of mammalian complete mitochondrial genomes (5) that it is possible to deal with saturation and base composition heterogeneity by recoding the nucleotides into purines (R) and pyrimidines (Y). This provided a solution to longstanding controversies concerning the position of the root of the mammalian tree (5).

Applying this strategy on nucleotides from the original Nardi et al. data set strongly suggests that by correcting for different artifacts it is possible to extract a useful historical signal. Unlike the authors (1), we were able to retrieve the bee (Apis) and the louse (Heterodoxus) within insects (Fig. 1). The artefactual position of these taxa as sister-groups of ticks was explained as being a consequence of their very high shared AT nucleotide composition reflected in their amino acid content (1). From our results, base composition heterogeneity seems to be more easily accommodated in phylogenetic reconstructions using nucleotides. More importantly, our analysis conforms with classical views of arthropod phylogeny: collembolans are sister-group of insects, and these monophyletic hexapods group with crustaceans into Pancrustacea (Fig. 1). One remaining problem with this tree concerns the paraphyly of myriapods induced by the nesting of the centipede (Lithobius) inside chelicerates.

-4 -However, as noted by the authors (1), their 35 taxa dataset also suffers from extreme rate heterogeneity among taxa, rendering it difficult to draw firm conclusions from. Thus, to check the collembolan position further, they reduced their data set to 15 taxa with more homogeneous rates and amino acid compositions. Despite their conservative analysis, they still reported collembolans outside both insects and crustaceans, rendering hexapods diphyletic. However, such a reduced dataset is particularly prone to systematic biases from low taxon sampling (6). In fact, deleting taxa with very anomalous rates and nucleotide composition can be helpful, but care is required not to delete taxa that then leave long isolated branches potentially leading to long branches attraction phenomena (7). More specifically, the inclusion of a single outgroup can have a strong impact on the phylogenetic reconstruction even in the absence of rate heterogeneity (8). In the case of placental mammal mitogenomics, taxon sampling has been shown to be a major source of phylogenetic error (9) and we found that increasing the number and diversity of taxa gave excellent agreement between nuclear and mitochondrial data (10).

To maximize taxon sampling, we constructed a well balanced 25 taxa data set designed to break isolated long branches (especially in the outgroup) without adding strong rate heterogeneity. Phylogenetic analyses of this nucleotide data set including RY-coded third codon positions produced a tree where Arthropoda, Pancrustacea, Hexapoda, Insecta and Pterygota all appear as monophyletic groups, though with variable support (Fig. 2).

Moreover, this topology is much more compatible with the current views on arthropod phylogeny (11). The probability of randomly selecting a topology compatible with this prior hypothesis is so small (10) that it provides strong evidence in favor of its veracity.

Delsuc et al.

Hexapods resurrected

-5 -Obviously, additional complete mitochondrial genomes are needed to strengthen the tree further, but with the data and methods currently at hand, the hypothesis of a common ancestry for extant hexapods cannot be rejected.

-6 -Postdoctoral Grant from the French Ministry of Foreign Affairs to FD and by the New Zealand Marsden Fund.

- 2 -

 2 Abstract Nardi et al. (Science, 21 March 2003, 1887) suggested that extant hexapods might be diphyletic based on the analysis of amino acids sequences of mitochondrial genes.

Fig. 1 :

 1 Fig.1: Bayesian 50% majority rule consensus tree with associated branch lengths obtained

Fig. 2 :

 2 Fig. 2: Maximum likelihood (ML) phylogram obtained using nucleotide sequences of

  Figure 1


Changjiang Gou
email: changjiang.gou@ens-lyon.fr

Anne Benoit
email: anne.benoit@ens-lyon.fr

Mingsong Chen
email: mschen@sei.ecnu.edu.cn

Loris Marchal
email: loris.marchal@ens-lyon.fr

Tongquan Wei
email: tqwei@sei.ecnu.edu.cn

Reliability-aware energy optimization for throughput-constrained applications on MPSoC

Keywords: Scheduling, MPSoC, energy minimization, throughput, reliability

Multi-Processor System-on-Chip (MPSoC) has emerged as a promising platform to meet the increasing performance demand of embedded applications. However, due to limited energy budget, it is hard to guarantee that applications on MPSoC can be accomplished on time with a required throughput. The situation becomes even worse for applications with high reliability requirements, since extra energy will be inevitably consumed by task re-executions or duplicated tasks. Based on Dynamic Voltage and Frequency Scaling (DVFS) and task duplication techniques, this paper presents a novel energy-efficient scheduling model, which aims at minimizing the overall energy consumption of MPSoC applications under both throughput and reliability constraints. The problem is shown to be NP-complete, and several polynomial-time heuristics are proposed to tackle this problem. Comprehensive simulations on both synthetic and real application graphs show that our proposed heuristics can meet all the given constraints, while reducing the energy consumption.

I. INTRODUCTION

Many smart applications in areas such as Internet of Things (IoT), augmented reality, and robotics, increasingly require high performance on embedded processing platforms. The three main criteria are i) computational performance, expressed as the throughput of the application; ii) reliability, i.e., most datasets must be successfully computed; and iii) energy efficiency. This is mainly because: i) applications such as audio/video coding or deep learning-based inference are delaysensitive, hence throughput should be properly guaranteed; ii) emerging safety-critical applications such as self-driving vehicles and tactile internet impose extremely stringent reliability requirements [START_REF] Fettweis | The tactile internet: Applications and challenges[END_REF]; iii) devices on which smart applications are running are often battery-operated, hence systems should be energy-efficient.

In order to meet all these design constraints, Multi-Processor System-on-Chip (MPSoC) is becoming a new paradigm that enables efficient design of smart applications. By integrating multiple cores together with an interconnection fabric (e.g., Network-on-Chip) as communication backbone, MPSoC can be tailored as multiple application-specific processors with high throughputs but low energy consumption [START_REF] Blake | A survey of multicore processors[END_REF], [START_REF] Wolf | Multiprocessor System-on-Chip (MPSoC) Technology[END_REF].

As one of the most effective power management techniques, Dynamic Voltage and Frequency Scaling (DVFS) has been widely used by modern MPSoCs [START_REF] Chen | Energy Optimization for Realtime Multiprocessor System-on-chip with Optimal DVFS and DPM Combination[END_REF]. By properly lowering the processing voltages and frequencies of dedicatedly mapped tasks, DVFS enables smart applications to be carried out with a reduced energy consumption, while ensuring a given throughput. However, scaling down voltages and frequencies of processors generates serious reliability problems. Various phenomena such as high energy cosmic particles and cosmic rays may cause the change of binary values held by transistors within CMOS processors by mistake, resulting in notorious transient faults (i.e., soft errors). Along with the increasing number of transistors integrated on a chip according to Moore's Law, the susceptibility of MPSoC to transient faults will increase by several orders of magnitude [START_REF] Zhao | Generalized reliability-oriented energy management for real-time embedded applications[END_REF]. In other words, the probability of incorrect computation or system crashes will become higher due to soft errors.

To mitigate the impact of soft errors, checkpointing and task replication techniques have been widely used to ensure system reliability [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF], [START_REF] Spasic | Energy-efficient mapping of realtime applications on heterogeneous MPSoCs using task replication[END_REF]. Tasks can be replicated if they do not have an internal state. This increases their reliability as it is extremely unlikely to have errors on two or more copies. Although checkpointing and task replication techniques are promising on enhancing the system reliability, frequent utilization of such fault-tolerance mechanisms is very time or resource consuming, which will in turn cost extra energy and degrade the system throughput. Clearly, the MPSoC design objectives (i.e., energy, reliability, and throughput) are three contradictory requirements when we need to decide the voltage and frequency level assignments for tasks. Although there exist dozens of approaches that can effectively handle the trade-off between energy and reliability issues, few of them consider the throughput requirement, see Section II. Hence, given throughput and reliability constraints, how to achieve a fault-tolerant schedule that minimizes the energy consumption for a specific DVFS-enabled MPSoC platform is becoming a major challenge for designers of smart applications.

To address the above problem, this paper proposes a novel scheduling approach that can generate energy-efficient and soft error resilient mappings for applications on a given MPSoC platform. We focus on pipelined linear chain applications, which are ubiquitous in processing of streaming datasets in the context of embedded systems [START_REF] Huang | Embedding Formal Performance Analysis into the Design Cycle of MPSoCs for Real-time Streaming Applications[END_REF]. Datasets continuously and periodically enter through the first task, and several datasets can be processed concurrently by different tasks. The throughput is the number of datasets that can be processed per time unit, and we consider the inverse of the throughput, called period, which is the time interval at which we can periodically start processing new datasets. The three major contributions are the following:

1) We propose a novel model that can formally express both performance and reliability constraints for mapping applications on MPSoCs, by bounding the expected period (for performance) and the probability of exceeding the target expected period (for reliability). The goal is to decide which tasks to duplicate, and at which speed to operate them, so that the energy consumption is minimized, while meeting the constraints. 2) We prove that without performance and reliability constraints, the problem is polynomially tractable, whereas adding both constraints results in an NP-complete problem. 3) We design novel task scheduling heuristics for reliabilityaware energy optimization on MPSoCs, which enforce the constraints and aim at minimizing the energy consumption. Extensive simulations demonstrate that heuristics can meet the constraints and considerably reduce the energy consumption compared to naive approaches.

The reminder of the paper is organized as follows. Related work is discussed in Section II. Then, we formalize the application model and optimization problem in Section III. Section IV studies the complexity of the problem variants, and in particular proves that the complete version of the problem is NP-complete. The heuristics are introduced in Section V, and they are thoroughly evaluated in Section VI on both real and synthetic applications. Finally, Section VII concludes and provides directions for future work.

II. RELATED WORK

MPSoCs have been deployed in various embedded applications such as image processing, process control, and autonomous navigations. Typical MPSoC consists of many fully connected identical processors with independent clock domains, such as AsAP2 [START_REF] Truong | A 167-processor 65 nm computational platform with per-processor dynamic supply voltage and dynamic clock frequency scaling[END_REF] and KiloCore [START_REF] Bohnenstiehl | Kilocore: A fine-grained 1,000-processor array for task-parallel applications[END_REF], which has 164 and 1000 identical processors respectively, communication on-chip is accomplished by a high-throughput and lowlatency circuit-switched network and a packet router. They are especially designed for embedded multimedia applications, and featured as high energy efficiency and performance and easy to program [START_REF] Truong | A 167-processor 65 nm computational platform with per-processor dynamic supply voltage and dynamic clock frequency scaling[END_REF]. Throughput maximization problem has been a subject of continuing interest as the demands for MPSoC-enabled high performance computing drastically increase. Zhang et al. [START_REF] Zhang | Distributed workload dissemination for makespan minimization in disruption tolerant networks[END_REF] optimize the throughput in disruption tolerant networks via distributed workload dissemination, and design a centralized polynomial-time dissemination algorithm based on the shortest delay tree. Li et al. [START_REF] Li | Energy-efficient stochastic task scheduling on heterogeneous computing systems[END_REF] specifically consider stochastic characteristics of task execution time to tradeoff between schedule length (i.e., throughput) and energy consumption. A novel Monte Carlo based task scheduling is developed to maximize the expected throughput without incurring a prohibitively high time overhead [START_REF] Zheng | Stochastic DAG scheduling using a Monte Carlo approach[END_REF]. Albers et al. [START_REF] Albers | Online makespan minimization with parallel schedules[END_REF] introduce an online algorithm to further maximize throughput with parallel schedules. However, reliability issues are not considered in these works.

Reliability can be achieved by reserving some CPU time for re-executing faulty tasks due to soft errors [START_REF] Zhao | Generalized reliability-oriented energy management for real-time embedded applications[END_REF]. In [START_REF] Marwedel | Mapping of Applications to MPSoCs[END_REF], the authors present a representative set of techniques that map embedded applications onto multicore architectures. These techniques focus on optimizing performance, temperature distribution, reliability and fault tolerance for various models. Dongarra et al. [START_REF] Dongarra | Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems[END_REF] study the problem of scheduling task graphs on a set of heterogeneous resources to maximize reliability and throughput, and proposed a throughput/reliability tradeoff strategy. Wang et al. [START_REF] Wang | A reliability-aware task scheduling algorithm based on replication on heterogeneous computing systems[END_REF] propose replication-based scheduling for maximizing system reliability. The proposed algorithm incorporates task communication into system reliability and maximizes communication reliability by searching all optimal reliability communication paths for current tasks. These works explore the reliability of heterogeneous multicore processors from various aspects, and present efficient reliability improvement schemes, however, these works do not investigate the energy consumed by MPSoCs, which interplays with system reliability.

Extensive research effort has been devoted to reduce energy consumption of DVFS-enabled heterogeneous multi-core platforms considering system reliability. Zhang et al. [START_REF] Zhang | Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[END_REF] propose a novel genetic algorithm based approach to improve system reliability in addition to energy savings for scheduling workflows in heterogeneous multicore systems. In [START_REF] Spasic | Energy-efficient mapping of realtime applications on heterogeneous MPSoCs using task replication[END_REF], Spasic et al. present a novel polynomial-time energy minimization mapping approach for synchronous dataflow graphs. They use task replication to achieve load-balancing on homogeneous processors, which enables processors to run at a lower frequency and consume less energy. In [START_REF] Das | Combined DVFS and Mapping Exploration for Lifetime and Soft-error Susceptibility Improvement in MPSoCs[END_REF], Das et al. propose a genetic algorithm to improve the reliability of DVFS-based MPSoC platforms while fulfilling the energy budget and the performance constraint. However, their task mapping approach tries to minimize core aging together with the susceptibility to transient errors. In [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF], the authors consider the problem of achieving a given reliability target for a set of periodic real-time tasks running on a multicore system with minimum energy consumption. The proposed framework explicitly takes into account the coverage factor of the fault detection techniques and the negative impact of DVFS on the rate of transient faults leading to soft errors. In [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], the authors propose energy-efficient scheduling algorithms with reliability goal for embedded systems, but they do not consider pipelined applications, and hence do not need to consider the throughput.

Hence, although above works explore various techniques to save energy, to the best of our knowledge, none of them consider system throughput in addition to reliability and energy. Our approach is thus the first attempt to model and optimize at the same time performance, reliability, and energy for workflow scheduling on MPSoC.

III. MODELS AND OPTIMIZATION PROBLEMS

We consider the problem of scheduling a pipelined workflow onto a homogeneous multi-core platform that is subject

o j-1 o j o j+1 w j w j+1 0 3 1 0 2 5 4
T 1 T 2 T 3 Figure 1: Linear chain workflow application. to failures. The goal is to minimize the expected energy consumption for executing a single dataset, given some constraints on the expected and worst-case throughput of the workflow. In the following subsections, we detail how to model applications, platforms, failures, energy cost, period (which is the inverse of the throughput), and how to formally define the optimization problems.

A. Applications

We focus on linear chain workflow applications, where task dependencies form a linear chain: each task requests an input from the previous task, and delivers an output to the next task. There are n tasks T 1 , . . . , T n . Furthermore, the application is pipelined, i.e., datasets continuously enter through the first task, and several datasets can be processed concurrently by the different tasks.

We assume that the initial data reside in memory, and the final data stay in memory. Task T j is characterized by a workload w j , and the size of its output file to the next task is o j , as illustrated in Fig. 1 (except for the last task). In the example, we have w 1 = 2, w 2 = 5, w 3 = 4, and

o 1 = 3, o 2 = 1.
Once the first dataset reaches task T 3 , while it is processed by T 3 , dataset 2 is transferred between T 2 and T 3 , dataset 3 is processed by T 2 , dataset 4 is transferred between T 1 and T 2 , and dataset 5 is processed by T 2 . At the next period, all dataset numbers are incremented by one.

B. Platforms

The target platforms are embedded systems composed of p homogeneous computing cores. Each core can run at a different speed with a corresponding error rate and a power consumption. If task T j is executed on a core operating at speed s(j) and if it is not subject to a failure, it takes a time wj s(j) to execute a single dataset.

We focus on the most widely used speed model, the discrete model, where cores have a discrete number of predefined speeds, which correspond to different voltages at which the core can be operating. Switching is not allowed during the execution of a given task, but two different executions of a task can be executed at different speeds. The set of speeds is {s min = s 1 , s 2 , . . . , s K = s max }. The continuous model is used mainly for theoretical studies, and let the speed take any value between the minimum speed s min and the maximum speed s max .

All cores are fully interconnected by a network on chip (NoC). The bandwidth β is the same between any two cores, hence it takes oj β for task T j to communicate a dataset to task T j+1 . The network on chip enables cores to communicate simultaneously with others while they are computing, i.e., communications and computations can be overlapped. Therefore, while task T j is processing dataset k, it is receiving the input for dataset k -1 from the previous task, and sending the output for dataset k + 1 to the next task. Hence, these operations overlap, and take respectively a time oj-1 β and oj β . We follow the model of [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF], [START_REF] Bohnenstiehl | Kilocore: A fine-grained 1,000-processor array for task-parallel applications[END_REF], where cores are equipped with a router, and on which there are registers. We can use the registers to store intermediate datasets, hence having buffers between cores. If datasets are already stored in the input buffer of a core, and if there is empty space in the output buffer, then the core can process a dataset without having to wait for the previous or next core.

C. Failure model and duplication

Embedded system platforms are subject to failures, and in particular transient errors caused by radiation. When subject to such errors, the system can return to a safe state and repeat the computation afterwards. According to the work of [START_REF] Zhu | Reliability-aware dynamic energy management in dependable embedded real-time systems[END_REF], radiation-induced transient failures follow a Poisson distribution. The fault rate is given by:

λ(s) = λ 0 e d smax -s smax -s min ,
where s ∈ [s min , s max ] denotes the running speed, d is a constant that indicates the sensitivity to DVFS, and λ 0 is the average failure rate at speed s max . λ 0 is usually very small, of the order of 10 -5 per hour [START_REF] Assayad | Tradeoff exploration between reliability, power consumption, and execution time for embedded systems[END_REF]. Therefore, we can assume that there are no failures when running at speed s max . We can see that a very small decrease of speed leads to an exponential increase of failure rate.

The failure probability of executing task T j (without duplication) on a processor running at speed s k is therefore f j (s k ) = λ(s k ) wj s k . If an error strikes, we resume the execution by reading the dataset again from local memory (i.e., the input has been copied before executing the task, we re-execute the task on the copy), and this re-execution is done at maximum speed so that no further error will strike the same dataset on this task. We assume that the time to prepare re-execution is negligible. Still, this slows down the whole workflow since other tasks may need to wait.

We propose to duplicate some tasks to mitigate the effect of failures and have a reliable execution. This means that two identical copies of a same task are executed on two distinct cores, both cores running at the same speed. In this case, if a failure occurs in only one copy, we can keep going with the successful copy. However, it may increase the energy cost and communication cost. Similarly to one execution at the maximum speed, we assume that an error on a duplicated task is very unlikely (i.e., at least one copy will be successful), and hence f j (s k ) = 0 if T j is duplicated.

Let m j = 1 if task T j is duplicated, and m j = 0 otherwise. Let s k be the speed at which T j is processed. The failure probability for T j is therefore f j (s k ) = (1 -m j )λ(s k ) wj s k , i.e., it is zero if the task is duplicated, and λ(s k ) wj s k otherwise (the instantaneous error rate at speed s k times the time to execute task T j ).

If we do not account for communications, the expected execution time of task T j running at speed s k is:

t j = w j s k + f j (s k ) w j s max .
Indeed, with duplication, at least one execution will be successful, while with a single execution, if there is a failure, we re-execute the task at maximum speed and there are no further failures.

Note that if a task T j is duplicated, this implies that further communications may be done, but they will occur in parallel. Both processors on which T j is executed are synchronized, and only one of them obtaining a correct result will do the output communication (to one or two processors, depending on whether T j+1 is duplicated or not). The copy subject to soft errors can be detected by acceptance test or sanity test [START_REF] Haque | On reliability management of energy-aware real-time systems through task replication[END_REF], and the synchronization cost is assumed to be negligible.

D. Energy

We follow a classical energy model, see for instance [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF], where the dissipated dynamic power for speed s k is s 3 k , and hence the energy consumed for a single execution of task T j running at speed s k is

wj s k × s 3 k = w j s 2 k .
We focus on the dynamic power, and ignore the leakage (or static) power, since we assume that the platform is continuously on, and we cannot switch any core off.

We further account for possible failures and duplication, hence obtaining the expected (dynamic) energy consumption for T j running at speed s k for one dataset:

E j (s k ) = (m j + 1)w j s 2 k + f j (s k )w j s 2 max .
Indeed, if task T j is duplicated (m j = 1), we always pay for two executions (2w j s 2 k ) but there is no energy consumed following a failure, while without duplication (m j = 0), we account for the energy consumed by the re-execution in case of a failure.

We assume that the energy consumed by communications and buffers is negligible compared to the energy consumed by computations [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF]. Therefore, the expected energy consumption of the whole workflow to compute a single dataset is the sum of the expected energy consumption of all tasks.

E. Period definition and constraints

As stated before, each task is mapped onto a different processor, or a pair of processors when duplicated, and different tasks are processing different datasets. In steady-state mode, the throughput is either constrained by the task with the longest execution time, or by the longest communication time, which is slowing down the whole workflow. The time required between the execution of two consecutive datasets corresponds to this bottleneck time and is called the period. It is the inverse of the throughput.

In this work, we are given a target period P t , hence the target throughput is 1 Pt . This corresponds for instance to the rate at which datasets are produced. We consider two different constraints: i) ensure that the expected period is not exceeding P t , hence the target becomes a bound, and/or ii) ensure that the probability of exceeding the target P t for a given dataset is not greater than proba t . This second constraint corresponds to real-time systems, where a dataset is lost if its execution exceeds the target period P t , and the probability proba t (0 ≤ proba t ≤ 1) expresses how many losses are tolerated. If proba t = 1, there is no constraint, while proba t = 0 means that no losses are tolerated.

Recall that the objective is to minimize the expected energy consumption per dataset of the whole workflow. Some tasks may be duplicated, and each task may run at a different speed. The communication between two consecutive tasks T j and T j+1 takes a constant time oj β , and it must fit within the target period. Therefore, we assume that for all 1 ≤ j < n, oj β ≤ P t . We assume in this section that the set of duplicated tasks is known: we set m i to 0 or 1 for each task T i . Furthermore, let s(i) be the speed at which task T i is executed, for 1 ≤ i ≤ n.

We first consider the case without failures and express the period in this case. Then, we express the expected period when the platform is subject to failures. Note that we assume that there is a sufficient number of buffers between cores, so that a failure does not necessarily impact the period, given that the cores have access to datasets stored in buffers, and can use empty buffers to store output datasets. Finally, we explain how to compute the probability that a dataset exceeds the target period P t .

1) Period without failures: In the case without failures, the period is determined by the bottleneck task computation or communication: P nf = max 1≤i≤n wi s(i) , oi β . We denote by L the set of tasks whose execution time is equal to P nf , i.e., L = T i | wi s(i) = P nf . If the bottleneck time P nf is achieved by a communication, this set may be empty.

2) Expected period: We consider that each processor is equipped with three or more buffers, two of them holding an input (resp. output) dataset being received (resp. sent), and the other buffers are used for storing intermediate datasets: a buffer is filled when the task is completed, but the following processor is not yet ready to receive the next dataset (i.e., the output buffer is still in use). We consider the period in steadystate, after the initialization has been done, i.e., all processors are currently working on some datasets.

The set of tasks L is empty if the computation time for all tasks is strictly smaller than the period P nf . When subject to a failure, tasks not in L can use data stored in buffers and process datasets at a faster pace than the period, until they have caught up with the time lost due to the failure.

However, errors in tasks of L are impacting the period, and therefore, if such a task is subject to failure, the re-execution time is added to the period. The expected period can therefore be expressed as follows:

P exp = P nf + j∈L f j (s(j)) w j s max . (1)
Indeed, the period P nf is achieved when there is either no failure, or a failure in a task not in L. In case of a failure while executing a task T j in L, the period is P nf + wj smax , and this happens with a probability f j (s(j)). As discussed before, we assume that there is no failure during re-execution, and that the probability of having two failures while executing a single dataset is negligible.

Note that this formula also holds when some tasks are duplicated. If task j ∈ L is duplicated (m j = 1), it will never fail and hence its period will be P nf . In this case, f j (s(j)) = 0 by definition, hence the formula remains correct.

3) Bounding the probability of exceeding the period bound: For the second constraint, we focus on the actual period of each dataset, rather than the expected period, and we estimate the probability at which the period of a dataset exceeds P t . We consider that P nf ≤ P t , otherwise the bound can never be reached, and the probability is always one.

The actual period, denoted by P act , is a random variable that ranges from P nf to max 1≤i≤n wi s(i) + wi smax . We define the set of tasks that may exceed the target period P t in case of failures:

S excess = T i | w i s(i) + w i s max > P t .
Therefore, if a failure strikes a task in S excess on a given dataset, the target period P t may not be met for this dataset. An error happens on task i with probability f i (s(i)). Since failures are independent, the period of a dataset will not exceed the bound if and only if no task in the set S excess has a failure, i.e., this happens with a probability Ti∈Sexcess (1

-f i (s(i))).
Hence, the probability of exceeding the bound is given by:

P (Pact > Pt) = 1 - T i ∈Sexcess (1 -fi(s(i))) ≈ T i ∈Sexcess fi(s(i)), (2)
considering that the failure probabilities are small, and that f i (s(i)) × f j (s(j)) = 0 for any 1 ≤ i, j ≤ n. This approximation is in line with the assumption that we do not consider two consecutive failures in a same task. Finally, the second constraint that we consider, after the one on the expected period described above, is to bound the probability of exceeding the target period P t by the target probability proba t :

P (P act > P t ) ≤ proba t .

F. Optimization problems

The objective is to minimize the expected energy consumption per dataset of the whole workflow, and we consider two constraints. The goal is to decide which tasks to duplicate, and at which speed to operate each task. More formally, the problem is defined as follows:

(MINENERGY). Given a linear chain composed of n tasks, a computing platform with p homogeneous cores that can be operated with a speed within set S, a failure rate function f , and a target period P t , the goal is to decide, for each task T j , whether to duplicate it or not (set m j = 0 or m j = 1), and at which speed to operate it (choose s(j) ∈ S), so that the total expected energy consumption is minimized, under the following constraints: i) The expected period P exp should not exceed P t ; ii) The probability of exceeding the target period P t should not exceed the target probability proba t .

Note that if there is a task k such that P t < w k smax or P t < o k β , then there is no solution (the target period can never be met).

If P t is large enough, the problem will not be constrained since in all solutions, the expected period will always be under the target period. This is the case for P t ≥ max( wi smin + wi smax ) and P t ≥ max( o k β ). In this case, each task running at the slowest possible speed, and being re-executed after a failure, will not exceed P t . This problem without constraints is denoted as MINENERGY-NOC.

We also consider the particular cases where only one or the other constraint matters. MINENERGY-PERC is the problem where we do only consider the first constraint on the expected period while MINENERGY-PROBAC is the problem where we do only focus on the probability of exceeding the target period.

IV. COMPLEXITY ANALYSIS

A. Without errors

When the workflow is free of errors, a task T j running at speed s j takes exactly a time wj sj , and consumes an energy of w j s 2 j . Hence, to minimize the energy consumption, one must use the smallest possible speed such that the target period is not exceeded, hence s j = max wj Pt , s min in the continuous case. Since we consider discrete speeds, the optimal speed for task T j is therefore the smallest speed larger than or equal to wj Pt within the set of possible speeds. This is true for all tasks, hence the problem can be solved in polynomial time.

B. Without constraints

We consider the MINENERGY-NOC problem, and propose the BestEnergy algorithm to optimally solve this problem. The idea is to use the speed that minimizes the energy consumption for each task, since we do not have any constraint about exceeding the target period. For each task, either we execute it at this optimal speed, or it may be even better (in terms of energy consumption) to duplicate it and run it at the smallest possible speed s min .

Theorem 1. MINENERGY-NOC can be solved in polynomial time, using the BestEnergy algorithm, both for the discrete and for the continuous energy model.

Proof. Given a task of weight w executed at speed s without duplication, the energy consumption is

E(s) = w × s 2 + λ 0 w 2 s 2 max e d smax -s smax -s min s
. The (continuous) speed that minimizes this energy consumption can be obtained by deriving E(s):

E (s) = 2ws - λ 0 w 2 s 2 max s 2 + λ 0 dw 2 s 2 max s(s max -s min ) e d smax -s smax -s min .
E (s) is a monotonically increasing function, and we let s * be the speed such that E (s * ) = 0, hence E(s * ) is minimum.

If the task is not duplicated, for MINENERGY-NOC-CONT, the optimal speed is s opt = max{s * , s min }. In the discrete case MINENERGY-NOC-DISC, s opt is simply the speed that minimizes the energy consumption, hence s opt = argmin s∈{smin,...,smax} {E(s)}. Now, if the task is duplicated, we assume that it will not be subject to error, hence the energy consumption at speed s is 2ws 2 . Therefore, it is minimum when the task is executed at the minimum speed, and the corresponding energy consumption is 2ws 2 min , both in discrete and continuous case. BestEnergy is a greedy algorithm that sets the speed of each task at s opt (not using duplication), and then greedily assigns remaining processors to tasks that would gain most from being duplicated (if any), see Algorithm 1. It is easy to see that it is optimal, since any other solutions could only have a greater energy consumption. The time complexity is O(n log n), for sorting the tasks by possible gains. The loops take a time O(n + p) = O(n) since we cannot use more than p = 2n processors.

Algorithm 1 -BestEnergy(n, p)

1: for i = 1 to n do 2:
Compute sopt(i) for task Ti, the speed that minimizes energy consumption if Ti is not duplicated;

3: si ← sopt(i), mi ← 0; 4:
gi ← E(si) -2wis 2 min {Possible gain in energy if Ti is duplicated}; 5: end for 6: Sort tasks by non-increasing gi, Tj is the task with max gi; 7: pav ← p -n {Number of available processors}; 8: while gj > 0 and pav > 0 do C. With the probability constraint Theorem 2. MINE-DEC is NP-complete, even when duplicating tasks is not possible.

In the decision version of MINE-DEC, the goal is to find an assignment set of speeds such that the probability of exceeding the target period P t does not exceed proba t , and such that the energy consumption does not exceed a given energy threshold E t . The proof, which can be found in the companion research report [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained MPSoC applications[END_REF], is based on a reduction from the Partition problem, known to be NP-complete [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. The idea is to have only two possible speeds, and one must decide at which speed to operate each task. We set as many processors as tasks, so that no duplication can be done.

V. HEURISTICS

We provide here several heuristics, all designed for the more realistic case of discrete speeds. We start with basic heuristics that will be used as baseline. Then we design heuristics aiming at bounding the expected period, and finally heuristics for bounding the probability of exceeding the target period. All heuristics are of polynomial complexity at most O(n log n).

Algorithm 2 -MaxSpeed(n, p)

1: for i = 1 to n do 2:
si ← smax, mi ← 0; 3: end for 4: return < si, mi >; Algorithm 3 -DuplicateAll(n, p)

1: if p ≥ 2n then 2: for i = 1 to n do 3:
Choose si as the smallest possible speed so that w i s i ≤ Pt, mi ← 1;

A. Baseline heuristics

We first outline the baseline heuristics that will serve as a comparison point, but may not satisfy the constraints. First, the BestEnergy algorithm described in Section IV-B is providing a lower bound on the energy consumption, but since it means that many tasks are running at the minimum speed, we expect the period to be large, and it may well exceed the bound.

Another simple solution consists in having each task executed at the maximum speed s max . We refer to this heuristic as MaxSpeed (see Algorithm 2).

The third baseline heuristic, DuplicateAll (see Algorithm 3), duplicates all tasks, assuming that there are twice more processors than tasks (p ≥ 2n), and the corresponding speeds for each tasks used in this case are the ones derived in Section IV-A. Indeed, there will not be any errors in this case, and we aim at respecting the target period P t .

Note that both MaxSpeed and DuplicateAll will always satisfy the bounds, since there will be no errors, and hence the expected period is equal to the period without failure. However, both heuristics may lead to a large waste of energy. They provide an upper bound on the energy consumption when using a naive approach. They both run in time O(n), provided that we have a constant number of speeds.

B. Bounding the expected period

In this section, we focus on the constraint on the expected period, hence targeting the MINENERGY-PERC problem.

1) Heuristic Threshold: The Threshold heuristic aims at reaching the target expected period P t (see Algorithm 4). The first step consists in setting all task speeds to the smallest speed such that wi si ≤ P t . If P exp is still larger than P t , then one of the tasks with largest duration ( wi si ) is duplicated: this allows P nf to be smaller than P t and constant from this moment on. Note that in the special case of a communication time reaching P t , there is no need to duplicate a task to have P nf = P t .

According to Equation (1), P exp = P nf + j∈L f j (s(j)) wj smax . We made sure that P nf is smaller than or equal to P t . In order to make P exp ≤ P t , each task T i of L has to be either run at a higher speed (which removes it from L), or duplicated Algorithm 4 -Threshold(n, p) (which sets f (s(i)) to 0). We greedily duplicate tasks for which duplication costs less energy, until there remains no more processors. Then, we speed up other tasks. Finally, we use the same technique as in BestEnergy to attempt to reduce again the energy of non-duplicated tasks: if the minimum speed s for energy consumption is larger than the actual s i of a task T i , its speed is increased to s.

Here again, assuming a constant number of speeds, the complexity is dominated by the sorting at line 14, since all other loops are in O(n). The time complexity is hence O(n log n).

2) Heuristic Closer: The previous Threshold heuristic uses duplication: at least one task is duplicated (in order to fix P nf ), which requires spare processors. We propose another heuristic that does not have this requirement. In the Closer heuristic (see Algorithm 5), after setting all task speeds to the smallest ones so that wi si ≤ P t , we increase the speed of all tasks in L while P exp > P t by scaling all tasks simultaneously: we set a coefficient and make sure that for each task, its speed is not smaller than coef × s i , where s i is the initial speed of T i . The coefficient is gradually increased until P exp ≤ P t . Finally, we use the same technique as in BestEnergy to attempt to further reduce the energy consumption of tasks.

This heuristic is iterating while the criteria is not met, and the time to converge depends on the parameter ∆s, and finishes at the latest when coef × s min ≥ s max , in which case tasks of set L will be set at speed s max . The number Algorithm 5 Closer(n, p, ∆s)

C. Bounding the probability of exceeding P t

In this section, we design a heuristic focusing on the constraint on the probability of exceeding P t , thus for the MINENERGY-PROBAC problem.

BestTrade (see Algorithm 6) aims at finding the best tradeoff between energy consumption and the probability of exceeding P t . We consider for each task two critical speeds:

• s i c is the speed such that w i /s i c + w i /s max = P t ; it corresponds to the minimum speed that a task can take without belonging to the S excess set; • s i d = w i /P t is the minimum speed that can be assigned to a task: if it is set to a smaller speed, its duration will always exceed the target period. The idea of the algorithm is first to set all tasks to the smallest speeds that are not smaller than their s i c speed. For some tasks, this might be equal to their minimum speed (the smallest possible speed not smaller than s i d ). In this case, there is no room for reducing speed again without exceeding the target period. For other tasks, we sort them by non-increasing weight: tasks with higher weights contribute the most to the energy dissipation and are thus first slowed down: we select the task T i with the largest weight, reduce its speed to the minimum possible speed not smaller than w i /P t . We continue with the tasks of smaller weight, until P (P act > P t ) ≥ proba t . At last, if P (P act > P t ) > proba t , we undo the last move to make P (P act > P t ) < proba t .

We then consider duplication: if duplicating a task T i (and setting its speed to the smallest speed that is not smaller than s i d ) is beneficial compared to the current solution (and if a processor is available), the task is duplicated.

The only while loop is reducing at each iteration the speed of one of the tasks, so the number of iterations is bounded by n. The overall complexity is therefore O(n log n) for the sorting at line 6. 1) Synthetic applications: Fig. 2 presents the results of all heuristics, both in terms of energy consumption, and in terms of constraints, when we vary the parameter κ, hence the tightness of the bound on the expected period. On Fig. 2a, the black dashed lines represent the minimum, maximum and average period bound. BestTrade, Closer and DuplicateAll are overlapped by Threshold. All chains have 0.5p nodes. Apart from MaxSpeed, which always meets the bound, and BestEnergy, which never meets the bound, all heuristics succeed to meet the bound on the expected period.

Fig. 2b shows the probability of exceeding the period bound, and the horizontal black dashed line is the target proba t . Du-plicateAll is overlapped by MaxSpeed, and only BestTrade succeeds to always meet the bound. Closer and Threshold give very similar results, but sometimes exceed the bound (when 0.4 ≤ κ ≤ 0.8). BestEnergy may result in a probability of 0 when κ = 0.95, but for other values κ, its probability is always 1, which is not depicted in the figure .  Finally, Fig. 2c depicts the energy consumption, normalized by the result of BestEnergy. It does not include the energy cost of heuristic MaxSpeed, which is 215 times larger than BestEnergy. Closer, Threshold and BestTrade are very close to each other in this set of simulations, so some of them are overlapped. DuplicateAll consumes significantly more energy than the other heuristics. Overall, Fig. 2 shows that BestTrade is the best heuristic for these applications: it allows us to always meet both the expected period bound and the probability bound, and it offers similar energy performance as other heuristics. Threshold and Closer are also good options, however they often exceed the probability bound.

2) Real applications: Fig. 3 shows the performance of the heuristics on real applications, as a function of κ. In Fig. 3a, the dashed line represents the average period bound. Best-Trade, DuplicateAll, Closer and Threshold give very similar results and thus overlap. All heuristics except BestEnergy meet the period target. For probability bound, as shown in Fig. 3b, only BestTrade always meets the target. DuplicateAll and MaxSpeed both give a probability of 0 as before. Closer and Threshold sometimes exceed the target probability by a large factor. Finally, Fig. 3c shows the energy required by each heuristic. In this setting, BestTrade is the most energy saving heuristic, closely followed by Closer. Threshold requires more energy, and DuplicateAll even more. Not surprisingly, MaxSpeed is the heuristic that costs the most energy, around 254 times larger than BestEnergy (so it is not included in Fig. 3c). This shows that BestTrade is also the best choice for real applications.

VII. CONCLUSIONS

In this paper, we have studied the problem of optimizing the energy consumption of linear chain applications on MPSoCs, which have both reliability and performance constraints. We proposed a new model that allows us to select the frequency of the cores for different tasks and to duplicate some tasks. It takes into account the expected period, the probability of exceeding the period and the energy efficiency. We proved that minimizing the energy consumption is easy without performance and reliability constraints, but that the problem becomes NP-complete when adding these constraints and when considering a discrete set of possible speeds. We then proposed several heuristics for choosing the tasks' processing speed and which tasks to duplicate. One of the proposed heuristics, BestTrade, is able to meet the bounds on the expected period and on the probability of exceeding the target period, while reducing the energy consumption. Future work will target more complex allocation schemes, in which several tasks may be mapped onto the same core, and more complex task graphs than linear chains (i.e., general directed acyclic graphs). Based on the present results, we expect the problems to become even more complex, but we believe that it will be possible to reuse some ideas derived from the study of linear chains.

9 :

 9 mj ← 1, sj ← smin, pav ← pav -1; 10: j ← the index of next task in the sorted list; 11: end while 12: return < si, mi >;

Figure 3 :

 3 Figure 3: Energy consumption and constraints on real applications, as a function of κ.

1 :

 1 for all tasks Ti do 2: si ← the smallest speed such that w i s i ≤ Pt, mi ← 0; 3: end for 4: pav ← p -n (number of available processors); 5: if Pt > max( o k β ) and pav ≥ 1 then 6: Select a task T k with largest duration (break tie by selecting one with smallest w k ), set m k ← 1 and pav ← pav -1; 7: end if 8: if Pexp > Pt then

	9:	Q ← {tasks of L with mi = 0};
	10:	for all tasks Tj in Q do
	11:	s ← the smallest speed that is larger than sj;
	12:	gj ← wj * (s 2 + fj(s)s 2 max -2s 2 j ) (Possible gain in energy
		if Tj is duplicated);
	13:	end for
	14:	Sort tasks of Q by non-increasing gi;
	15:	for all task Tj in Q do
	16:	if pav > 0 then
	17:	mj ← 1, pav ← pav -1;
	18:	else
	19:	sj ← the smallest speed that is larger than sj;
	20:	end if
	21:	end for
	22: end if
	23: for all tasks Ti with mi = 0 do
	24:	Compute the speed s that minimizes Ei(s);
	25:	if si < s then
	26:	si ← s;
	27:	end if
	28: end for
	29: return < si, mi >;

1 :

 1 for all tasks Ti do 2:s i ← the smallest speed such that w i s i ≤ Pt, mi ← 0; 3: end for 4: Set coef ← 1; 5: while Pexp > Pt do , and the complexity is in O(N it × n). If we set ∆s such that N it = O(log n), the time complexity is O(n log n).

	6:	coef ← coef + ∆s;
	7:	for all tasks Ti of set L do
	8:	si ← smallest speed not smaller than coef × s i ;
	9:	end for
	10: end while
	11: for all task Ti do
	12:	Compute the speed s that minimizes Ei(s);
	13:	if si < s then
	14:	si ← s;
	15:	end if
	16: end for
	17: return < si, mi >
	of iteration is therefore bounded by N it = 1 ∆s	smax smin -1

Table II :

 II Real application examples.

	Application	Size	Average	SD
			(node's weight)	(node's weight)
	CRC encoder	46	14.20	3.71
	N-point FFT	13	1621.31	818.25
	Frequency hopping radio	16	11815.81	19720.21
	16x oversampler	10	2157.4	3724.84
	Radix sort	13	179.92	26
	Raytracer	5	142.8	188.59
	Time-delay equalization	27	23264.78	10020.25
	Insertion sort	6	475.83	270.04

ACKNOWLEDGMENT

This work is supported by the National Natural Science Foundation of China (NSFC) under Grant No.61872147.

Algorithm 6 BestTrade(n, p)

We assume all weights are different (wi = wj for i = j); 2: for j = 1 to j = n do 3: sj ← smallest possible speed not smaller than wj/(Ptwj/smax), mj = 0; 4: end for 5: S reduce ← tasks that have possible speeds between wj/Pt and wj/(Pt -wj/smax); 6: Sort tasks of S reduce by non-increasing weight; 7: k = 1; 8: while P (Pact > Pt) < proba t do 9:

Reduce speed of the k-th task in S reduce to the smallest that is not smaller than wj/Pt; Set speed of the (k -1)-th task in S reduce to the smallest that is not smaller than wj/(Pt -wj/smax);

VI. SIMULATION RESULTS

In this section, we evaluate all proposed algorithms through extensive simulations on both real applications and synthetic ones. For reproducibility purposes, the code is available at github.com/gouchangjiang/Pipeline on MPSoC.

Given a computing platform and an application, we set the target period P t and probability proba t so that all assumptions made in the model are true:

• When all tasks are executed with the minimum speed s min , the maximum failure rate is not than 10 -2 . With such a failure rate, the failure of two copies of a duplicated task is very unlikely, and the approximation in Equation ( 2) holds. • When all tasks are processed with speed s max , the maximum failure rate is not larger than 10 -4 , which means that the failure of a task running at maximum speed is very unlikely. • P t should not be smaller than any task duration when running at maximum speed, otherwise, there is no way to meet the target period: P t ≥ max(wi) smax . We set P t = a + κ * (b -a), where a = max(w i /s max , o i ) and b = max(w i /s min + w i /s max , o i ): a (respectively b) is the maximal time spent on a task (either on computation or on communication), when running at the maximum (resp. minimum) speed. This way, P t is never smaller than a, which satisfies the third condition above. Similarly, we avoid the case P t ≥ b, in which the target is too loose, as even the minimum speed can achieve it. A small κ leads to a tighter target period. Under the above three conditions, we set κ to values from 0.05 to 0.95, by increment of 0.01. The target probability is set to proba t = 0.05 for synthetic applications and proba t = 0.01 for real applications. ∆s in Closer is set as 10 -3 . We use the result of heuristic BestEnergy described in Section IV-B as a comparison basis, as it gives the minimum energy consumption of the system without any constraints.

A. Multi-core embedded systems

We simulate a multi-core computing platform with 512 cores. Based on AsAP2 and KiloCore, two state-of-art MP-SoCs described in Section II, the frequency/voltage options are listed in Table I. NoC on chips enables extremely fast communications. We describe the value of β together with the output (input) file sizes o i below in the next subsection. The failure rate is computed as described in Section III-C as λ(s) = λ 0 e d smax -s smax -s min . Based on the settings in [START_REF] Zhu | Reliability-aware dynamic energy management in dependable embedded real-time systems[END_REF], we set λ 0 = 10 -6 and d = 4.

B. Streaming applications

We use a benchmark proposed in [START_REF] Thies | Language and Compiler Support for Stream Programs[END_REF] for testing the StreamIt compiler. It collects many applications from varied representative domains, such as video processing, audio processing and signal processing. The stream graphs in this benchmark are mostly parametrized, i.e., graphs with different lengths and shapes can be obtained by varying the parameters. Table II lists some linear chain applications (or application whose major part is a linear chain) from [START_REF] Thies | Language and Compiler Support for Stream Programs[END_REF]. Some applications, such as time-delay equalization, are more computation intensive than others.

Following the same idea, we also generated synthetic applications in order to test the algorithms on larger applications. We generated 3,000 linear chains, each has 0.5p nodes, where p is the number of cores. The weights of the nodes w i follow a truncated normal distribution with mean value 2,000, where the values smaller than 100 or larger than 4,000 are removed. The standard deviation is 500. This ensures that the execution time is not too long so that failure rate is acceptable. The communication time ( oi β ) follows a truncated normal distribution with mean value 0.001 * P t , values that are larger than P t are replaced by P t . Here P t = a + 0.05 * (b -a).

C. Simulation results

We present both results on synthetic applications and on real applications. On each plot, we show the minimum, mean, and maximum values of each heuristic. In some cases, only the mean is plotted to ease readability, when the minimum and maximum do not bring any meaningful information.


Vincent Leon

Yang Ren

Marie-Louise Saboungi
email: saboungi@cnrs-orleans.fr

Effect of Nanoscale Confinement on the β-α Phase Transition in Ag 2 Se

The confinement of silver selenide was investigated using mesoporous silica. Results from x-ray diffraction and electron microscopy show that the confined material still exhibits a β to α transition similar to the one that takes place in the bulk crystalline state but with a transition temperature that depends significantly on the confinement conditions. Decreasing the pore size leads to an increase of the transition temperature, opposite to the behavior of the melting point observed in several metallic and organic materials. In the free particles, on the other hand, no size dependence is observed with particle sizes down to 4 nm.

 Moreover, β-Ag 2 Se has been recently shown to exhibit a significant magnetoresistance (MR) by manipulating small departures from stoichiometry. 12 This large magnetic response, a near-linear increase of the resistance with the applied magnetic field without saturation at high fields, is comparable in magnitude to the colossal MR observed in manganese

perovskites, 13 but occurring here in a non-magnetic material. 14 Here we report a procedure for confining Ag 2 Se in an inorganic matrix and a study of the effects of confinement on the phase transition temperature. Porous silica was chosen as the matrix because it is chemically inert, the size and shape of the pores are well controlled 15 and, in the case of selenium-based particles, the interactions between silica and selenium are very weak. 16 In order to achieve confinement, we performed a direct synthesis of silver chalcogenide inside the pores of a mesoporous silica presenting an ordered array of pores with a diameter between 2 and 10 nm. This procedure has the advantage of taking place at room temperature under soft synthesis conditions. Mesoporous silica (SBA-15) was prepared following the procedure described by Zhao et al. 17 The choice of SBA-15 as porous silica host instead of, e.g., MCM-41 was dictated by the reported higher stability of the walls and the presence of microporous connections between the mesopores. 18 Typically, 3 g of porosity agent are dissolved in 22.5 g of water and diluted in 90 g of HCl (pH 2). The porosity agents used here are poly(ethylene oxide)-poly(propylene oxide)-poly(ethylene oxide) triblock copolymers with different chain lengths to provide different pore sizes. 19 Then 6.375 g of the silica precursor TEOS (tetraethoxysilane, 99.99%, Alfa Aesar) are added under vigorous stirring for 20 h at 35 °C. The solution is aged under different conditions, summarized in Table 1, depending on the pore size needed. Finally, the obtained gel is calcinated at 550 °C for 12 hours to remove the polymer template. For each sample, surface areas were calculated using the BET adsorption-desorption method and pore size distributions were analyzed by the BJH method. An impregnation technique to obtain some polyvinyl alcohol-selenide nanocomposites, was used to synthesize a composite material with silver selenide inside silica pores. 20 Silver nitrate (AgNO 3 ) and sodium selenosulfate (Na 2 SeSO 3 ) were used as silver and selenium sources respectively. Typically, 500 mg of mesoporous silica is placed in a 50 ml flask and 5 ml of an aqueous solution of AgNO 3 (0.1 M) is added, under constant stirring at room temperature for 3 h. Then 0.5 ml of an aqueous solution of Na 2 SeSO 3 (pH 10) is added under the same conditions (room temperature, 3 h stirring). This solution is prepared by adding 4 g (0.05 mol) of selenium powder to 50 ml of a 1M aqueous solution of Na 2 SO 3 . The mixture is refluxed at 70 °C for 24 h and then filtrated under vacuum and stored at 60 °C to avoid decomposition. A few drops of ammonia solution are added to reach a pH value of 10. The dark solution of sodium selenosulfate is then filtrated, washed with deionized water to remove solvents, and dried under vacuum. Ag 2 Se was synthesized inside pores of different size, but the conditions just described were the same for each sample.

In order to determine whether the Ag 2 Se is inserted into the silica pores, we used transmission electron microscopy (Philips CM20) and scanning electron microscopy (SEM, Hitachi). Figure 1 clearly shows Ag 2 Se inside 2 nm-size mesopores; the fact that some parts of the pores are not filled with Ag 2 Se just indicates that the proportions of silica and aqueous solutions of silver and selenium ions have to be adjusted to have a homogenous filling of the pores. It can also be seen that the material fills the pores as nanowires rather than nanoparticles. Consequently, it is interesting to compare the results obtained for these samples with both bulk Ag 2 Se and Ag 2 Se nanoparticles. For the synthesis of Ag 2 Se, we used the method described by Dusastre et al., 21 where silver and selenium powders are mixed in stoichiometric proportion in n-butylamine as solvent (or more precisely surface activator) to give particles with an average size of about 150 nm (Figure 2). We synthesized Ag 2 Se nanoparticles using the doublemicroemulsion method 22,23 involving microemulsions of Ag + and Se 2-in a ternary AOT/n-heptane/water system. This method is suitable for controlling the size of the particles by adjusting the ratio of surfactant (AOT) to water. Here, we chose to generate nanoparticles with a reasonably narrow size distribution around a diameter of 3.9 nm (Figure 3).

To study the variations in T β α for the different conditions of Ag 2 Se, we made structural measurements using the high-energy X-ray diffractometer at beam line 11-ID-C of the Advanced Photon Source at a photon energy of 115 keV. Powdered samples were placed in thin capillaries (1 to 3 mm diameter) and x-ray diffraction (XRD) measurements were carried out at different temperatures using a controlled heater. During a typical measurement, the temperature is increased by 1 K in the region the phase transition temperature, up to 200°C, and then cooled down to room temperature with the same protocol. For the bulk, XRD measurements show that T β α takes place at around 140 ±1°C . As shown in Figure 4, the transition between β -Ag 2 Se and α-Ag 2 Se for 150 nm-sized particles occurs also at around 140 °C : the three main peaks characterizing β-Ag 2 Se at Q = 23.9 (112), 27.9 (031) and 30.0 nm -1 (113) are replaced by the two main peaks of α-Ag 2 Se at Q = 25.3 (200) and 30.9 nm -1 (11). It appears that the size effect on T β α is negligible for free particles. This lack of size dependence is not universal since, in the case of an oxide like SrBi 2 Ta 2 O 9 , for example, the ferroelectric phase transition temperature is strongly dependent on the diameter of the particles. 24 Using the same protocol, XRD measurements for silver selenide confined inside 8, 3.5 and 2 nm diameter pores were carried out showing that T βα is 141, 142 and 146 °C, respectively. For illustration purpose, Figure 5 shows a typical spectra collected in the case of 2 nm pores and Figure 6 the dependence of T βα on pore size. The measured increase of T β α with decreasing pore size contrasts with the lack of size effect found for the free particles. A size effect on the phase transition of some metallic particles have been reported, with a decrease in melting point with decreasing particle size in gold, for example. 25 It has also been shown that the melting transition of some confined organic molecules has the opposite behavior than the one found here. 26,27 Results for the effect of confinement on the glass transition appear to be more complicated, with different behaviors observed for the same material depending on the experimental methods used. 1 In conclusion, we have developed a procedure for direct synthesis of Ag 2 Se inside the pores of a mesoporous silica containing an ordered array of pores with a diameter between 2 and 10 nm, and found a steady decrease in the temperature of the β→α transition with decreasing pore size. On the other hand, no such effect is observed in free nanoparticles down to a size of 3.9 nm. Since the β→α transition can be regarded in some sense as a melting of the Ag + sublattice, it is interesting that the behavior of both types of nanoscale Ag 2 Se is quite different from that observed for the melting point in several systems reported. In future work, we plan to investigate the off-stoichiometric compositions that exhibit high MR and determine the effect of 3-D nanoscale confinement on the p-type or n-type materials. This will provide an interesting comparison with the results reported for silver chalcogenides thin films 7,28 and wires, 9,29 corresponding to 1-D and 2-D confinement, respectively. This work was supported by the Office of Science, US Department of Energy, under Contract W-31-109-ENG-38, the Centre National de la Recherche Scientifique and the Université d'Orléans. We acknowledge helpful discussions with D. L. Price and thank the staff of the Advanced Photon Source for technical assistance.

Figure 1 .

 1 Figure 1. TEM picture of the silver selenide inside mesoporous silica.

Figure 2 .Figure 3 .

 23 Figure 2. TEM picture of particles obtained by the method proposed by Dusastre et al.21

Figure 4 .Figure 5 .Figure 6 .

 456 Figure 4. XRD of Ag 2 Se particles with an average size of 250 nm.

Table 1 .

 1 Synthesis parameters and pore size of mesoporous silica.

	Template	Block copolymer	Aging temperature (°C)/time (h)	Mesophase	BET surface area (m 2 /g)	Pore size (nm)
	EO 100 PO 39 EO 100 Pluronic F88	80/12	cubic	700	2.0
	EO 20 PO 70 EO 20 Pluronic P123	80/12	hexagonal	690	3.5
	EO 20 PO 70 EO 20 Pluronic P123	80/48	hexagonal	650	8.0