Didier Wion
email: didier.wion@ujf-grenoble.fr

Josep Casadesús

N 6 -methyl-adenine: an epigenetic signal for DNA-protein interactions

N 6 -methyl-adenine is found in the genomes of bacteria, archaea, protists, and fungi. Most bacterial DNA adenine methyltransferases are part of restriction-modification systems. In addition, certain groups of Proteobacteria harbor solitary DNA adenine methyltransferases that provide signals for DNA-protein interactions. In γ-Proteobacteria, Dam methylation regulates chromosome replication, nucleoid segregation, DNA repair, transposition of insertion elements, and transcription of specific genes. In Salmonella, Haemophilus, Yersinia, Vibrio, and pathogenic E. coli, Dam methylation is required for virulence. In α-Proteobacteria, CcrM methylation regulates the cell cycle in Caulobacter, Rhizobium, and Agrobacterium, and plays a role in Brucella abortus infection.

Introduction

In microbial genomes, the most common DNA modification is postreplicative base methylation. C 5 -methyl-cytosine and N 6

-methyl-adenine are found in the genomes of many fungi, bacteria, and protists, while N 4

-methyl-cytosine is only found in bacteria 1

. N 6 -methyladenine is also present in archaeal DNA 2 . Base modification in bacterial genomes is performed by two classes of DNA methyltransferases: (i) those associated with restrictionmodification systems 3

, and (ii) solitary methyltransferases that do not have a restriction enzyme counterpart. Examples of the latter are the N 6

-adenine methylases Dam and CcrM, and the C 5 -cytosine methylase Dcm 4-7

. In eukaryotes, C 5 -methyl-cytosine (m5C) plays roles in gene expression, chromatin organization, genome maintenance and parental imprinting, and has attracted ample interest because of its involvement in human disease 8

. In contrast, the functions of the prokaryotic Dcm enzyme remain unknown 4

.

Diverse groups of Proteobacteria use N 6

-methyl-adenine (m6A) as a signal for genome defense, DNA replication and repair, nucleoid segregation, regulation of gene expression, control of transposition, and host-pathogen interactions 4-7 (Figure 1). Methylation of the amino group of adenine lowers the thermodynamic stability of DNA 9 and alters DNA curvature 10

. Such structural effects can influence DNA-protein interactions, especially for proteins that recognize their cognate DNA binding sites by both primary sequence and structure 11

. All known functions of m6A in Proteobacteria rely on regulating the interaction between DNA-binding proteins and their cognate DNA sequences. Typically, m6A is used as a signal to indicate when and where a given DNA-protein interaction must occur [START_REF] Messer | Timing and targeting: the biological functions of Dam methylation in E. coli[END_REF] .

DNA adenine methylation and restriction-modification systems

The discovery of restriction-modification systems (R-M) was the consequence of observations made in the early 1950's on host-controlled variation of bacterial viruses 13,14

. The molecular explanation of this phenomenon came several years later, when it was shown that growth of phages in bacteria was restricted by endonucleases which attack unmethylated viral DNA whereas host DNA is protected by a specific methylation pattern 15

. R-M systems are found in both Eubacteria and Archaea, and are believed to have evolved to protect bacteria against viruses. m6A is with m5C and m4C, one of the three methylated bases ensuring the protection of DNA against endonuclease digestion. Hence, R-M systems contain both a restriction enzyme and a cognate DNA adenine or cytosine methyltransferase 3

. R-M systems have been classified in three types on the basis of structural features, position of DNA cleavage, and cofactor requirements. In types I and III, the DNA adenine or cytosine methyltransferase is part of a multisubunit enzyme catalyzing both restriction and modification 3

. In contrast, type II R-M systems have two separate enzymes, a restriction endonuclease and a DNA-adenine (or cytosine) methyltransferase which recognize the same target 3

. In addition to these three types of R-M systems in which adenine or cytosine methylation protects against endonuclease cleavage, restriction systems specific for methylated bases have also been described 16

. Thus, the pattern of adenine methylation extends the coding capacity of DNA to a new function, the distinction between "self" and "nonself" 17

. This classical viewpoint considering R-M systems as a barrier against foreign DNA invasion has progressively evolved to include new biological functions or concepts such as the involvement of R-M systems in genetic exchange 18 and maintenance of species identity 19

.

Other evidence suggests that, in type II R-M systems, the couple made by the methyltransferase and the cognate restriction endonuclease behaves as a "selfish" element in a host parasite-type interaction with bacteria 20

. This view originates from the observation that type II R-M genes are often linked with mobile elements and that their loss may cause cell death through restriction cleavage of the genome. This cell death occurs because R-M methyltransferases are distributive and not processive. Therefore, the residual methyltransferase activity is unable to protect all the restriction sites against cleavage by the remaining endonuclease molecules.

Dam: a solitary methyltransferase of γ γ γ γ-Proteobacteria

The first solitary DNA adenine methyltransferase found to provide signals with physiological significance was the Dam enzyme of E. coli [START_REF] Marinus | Escherichia coli and Salmonella: Cellular and Molecular Biology[END_REF][START_REF] Low | An update on the roles of Dam methylation in bacteria, including evolutionary aspects 8. Esteller, M. Aberrant DNA methylation as a cancer-inducing mechanism[END_REF]7 . Dam transfers a methyl group from Sadenosyl-methionine to the amino group of the adenine moiety embedded in 5'-GATC-3' sites 4

. Methylation occurs shortly (but not immediately) after DNA replication; hence, passage of the replication fork leaves GATC sites transiently hemimethylated. The E. coli Dam enzyme methylates both hemimethylated and unmethylated GATC sites with similar efficiency 4

. Based on the organization of amino acid domains, Dam is classified in the α group of DNA amino methyltransferases, and shares significant identity with DpnIIA, MboIA and other DNA methylases which are part of restriction-modification systems 6,7

. This relatedness suggests that Dam has evolved from an ancestral restriction-modification system.

A difference, however, is that the Dam methylase is highly processive while R-M modification methylases are not 21

.

Homologs of the E. coli Dam methylase are found in the orders Enterobacteriales, Vibrionales, Aeromonadales, Pasteurellales and Alteromonadales 6

. In E. coli and Salmonella, dam mutations cause pleiotropic defects but do not impair viability [START_REF] Marinus | Escherichia coli and Salmonella: Cellular and Molecular Biology[END_REF][START_REF] Torreblanca | DNA adenine methylase mutants of Salmonella typhimurium and a novel Dam-regulated locus[END_REF] . In Vibrio cholerae, a dam mutation is lethal [START_REF] Julio | DNA adenine methylase is essential for viability and plays a role in the pathogenesis of Yersinia enterocolitica and Vibrio cholerae[END_REF] , and may prevent replication initiation in both chromosomes 24

. Dam methylation is also essential in certain strains of Yersinia

Regulation of transposition by Dam methylation

In the bacterial transposons IS10 and IS50, Dam methylation represses transposition by two independent mechanisms: (i) In the IS10 transposase promoter, methylation of a GATC site overlapping the -10 module hinders binding of RNA polymerase and inhibits transcription of the transposase gene. Passage of the replication fork renders the GATC transiently hemimethylated, and permits transcription 48

. In an analogous fashion, transcription of the IS50 transposase gene from the P 1 promoter is repressed by methylation of two GATC sites located in the -10 module 49

. (ii) In both IS10 and IS50, methylation of GATCs at the ends of the transposon inhibit transposase activity at these ends 48-50

. In IS10, only one of the two hemimethylated species is active for transposition 48

, an asymmetry that further reduces the frequency of IS10 transposition and contributes to lower the mutation rate. An additional advantage of using Dam hemimethylation as a signal is that transposition occurs during DNA replication: a host cell with two chromosomes will more likely survive transposition events affecting essential loci. As in every host-pathogen interaction, increased host survival can be viewed as a favorable factor for transposon endurance.

Regulation of phase variation by Dam methylation

Phase variation, the reversible generation of variants of surface antigens, is frequent among pathogenic bacteria. Pap (pyelonephritis-associated pili) of uropathogenic E. coli mediate adhesion to the mucosa in the urinary tract 51

. Synthesis of Pap pili is turned ON or OFF by a mechanism that gives rise to two populations, one with pili, the other without. The switch rate from ON to OFF is 100-fold higher than from OFF to ON 51 . Because pili are highly immunogenic, phase variation may contribute to stealth invasion of the urinary tract.

60

. Switching from the OFF to the ON state simply requires a decrease in active (oxidized) OxyR, which will lead to operator release; after DNA replication, the agn43 operator will be methylated (Figure 4). Besides hindrance of repressor binding, Dam methylation plays a second role in the agn43 promoter: methylation of the upstream GATC site increases transcription initiation, which occurs precisely at the G nucleotide of the GATC

61

.

Inheritance of Dam methylation patterns

Early studies envisaged that GATC sites remained hemimethylated for a short time lapse, and the occurrence of unmethylated DNA was viewed as a non-physiological condition 4,6

. The discovery of SeqA introduced the notion that the duration of hemimethylation at certain GATCs could be extended by sequestration and concomitant hindrance of Dam methylase activity. However, SeqA-mediated sequestration is temporary, and the sequestered GATC sites are fully methylated before cell division. In contrast, methylation-blocking proteins like Lrp and OxyR permit the formation of GATC sites that are stably undermethylated, and inherited as such 6

.

Heritable methylation patterns like those found in pap and agn43 may not be rare exceptions.

The E. coli chromosome contains at least 50 sites that are stably hemimethylated or unmethylated (see Box 1), and a subset of these are located in putative regulatory regions . As a consequence, newly replicated plasmid molecules will be in two differerent epigenetic states: one will permit Lrp binding and subsequent traJ synthesis, while the other will not. This epigenetic switch may moderate the activation of conjugal transfer, thereby limiting the metabolic and energetic burden placed on the host by the plasmid conjugation apparatus.

Roles of Dam methylation in bacterial virulence

Initial evidence for a relationship between Dam methylation and bacterial virulence was provided by the regulation of adhesin-encoding genes 6,52

. However, the effect of dam mutations on the infection of model animals was first reported in Salmonella enterica [START_REF] Heithoff | An essential role for DNA adenine methylation in bacterial virulence[END_REF][START_REF] Portillo | DNA adenine methylase mutants of Salmonella typhimurium show defects in protein secretion, cell invasion, and M cell cytotoxicity[END_REF][START_REF] Giacomodonato | Host response to a dam mutant of Salmonella enterica serovar Enteritidis with a temperature sensitive phenotype[END_REF] . Dam mutants of Salmonella are attenuated in the mouse model [START_REF] Heithoff | An essential role for DNA adenine methylation in bacterial virulence[END_REF][START_REF] Portillo | DNA adenine methylase mutants of Salmonella typhimurium show defects in protein secretion, cell invasion, and M cell cytotoxicity[END_REF][START_REF] Giacomodonato | Host response to a dam mutant of Salmonella enterica serovar Enteritidis with a temperature sensitive phenotype[END_REF] , and present pleiotropic virulence-related defects: (i) Envelope instability with leakage of proteins and release of membrane vesicles , and raises the possibility that Dam-regulated genes are also found in other pathogens.

Dam methylation and bacteriophage infection

The genomes of certain phages of enteric bacteria have few GATC sites, while other phage genomes show a GATC content similar to that found in the bacterial host genome

88

. P1 circular molecules with hemimethylated and unmethylated pac sites are thus produced. In the second stage of replication (rolling circle), P1 Dam methylase, the product of a late gene, is allowed to methylate only one pac site per concatemer; the other pac sites are protected (but not cut) by protein 9. This mechanism permits headful packaging, and avoids cutting of pac sites inside a concatemer 88

.

The solitary CcrM methylase of α α α α-Proteobacteria

The CcrM methylase was discovered in Caulobacter crescentus [START_REF] Zweiger | A Caulobacter DNA methyltransferase that functions only in the predivisional cell[END_REF][START_REF] Marczynski | Control of chromosome replication in Caulobacter crescentus[END_REF] . Unlike Dam, CcrM belongs to the β group of DNA amino methyltransferases, and shares homology with the HinfI methylase of H. influenzae 5

m6A in eukaryotic genomes

The numerous functions performed by m6A in prokaryotic DNA contrast with the paucity of data regarding the role or even the presence of m6A in eukaryotes. Indeed, the first attempts to determine the base composition of eukaryotic DNA found m5C as the only methylated base in these genomes

93

. However, there is now accumulating evidence demonstrating the presence of m6A in several lower eukaryotes

94

. Thus, m6A has been detected in the DNA of Penicillium chrysogenum 95 , the green alga Chlamydomonas reinhardtii [START_REF] Hattman | Comparative study of DNA methylation in three unicellular eucaryotes[END_REF] , and several ciliates such as Oxytricha fallax, Paramecium aurelia, Stylonichia mytilius, and Tetrahymena pyriformis [START_REF] Hattman | DNA-[adenine] methylation in lower eukaryotes[END_REF] . A distinct feature of ciliate protozoa is the existence of a nuclear dimorphism leading to two kinds of nuclei in the same cell: a germ line nucleus (micronucleus) and a polyploid somatic nucleus (macronucleus)

97

. The finding that adenine methylation is restricted to macronuclear DNA has lead to the suggestion that m6A could be involved in the control of deletions and chromosome fragmentation which occur during macronucleus formation

94

. Unfortunately, proteins interacting with m6A in lower eukaryotes have not yet been characterized. Also, adenine DNA methyltransferase genes have been reported in Chlorella viruses [START_REF] Van Etten | DNA methylation of viruses infecting a eukaryotic Chlorella-like green alga[END_REF] . In some cases, these adenine DNA methyltransferases are associated with cognate restriction enzymes

Perspectives and concluding remarks

Since the discovery of methylated bases in DNA, investigations on DNA methylation have mainly concerned m5C and mammals. Consequently, considerable progress has been made in understanding how DNA methylation affects transcriptional regulation, chromatin structure, and genome stability in higher eukaryotes. Quantitatively, less work has been performed on the role of adenine methylation in bacteria. However, an emerging idea is that adenine methylation in bacteria could be the counterpart of cytosine methylation in mammals. This offers an opportunity for the cross-fertilization of ideas between bacterial and mammalian epigenetic research.

The widespread functions of GATC and GANTC methylation in bacteria illustrate both the efficiency and the versatility of m6A as an epigenetic signal for the control of DNA-protein interactions. Methylation patterns at the pap operon [START_REF] Van Der Woude | Epigenetic phase variation of the pap operon in Escherichia coli[END_REF][START_REF] Hernday | Self-perpetuating epigenetic pili switches in bacteria[END_REF] and the agn43 gene [START_REF] Haagmans | Phase variation of Ag43 in Escherichia coli: Dam-dependent methylation abrogates OxyR binding and OxyR-mediated repression of transcription[END_REF] illustrate how E. coli lineages can inherit loci in different epigenetic states, a phenomenon reminiscent of genomic imprinting. In turn, differential regulation of IS10 and traJ in sister DNA molecules 48,68 shows that bacterial DNA molecules in different epigenetic states can coexist in the same cell, as in X-chromosome inactivation. These examples show that epigenetic phenomena are not restricted to the kingdom Eukarya, and outline the utility of m6A as an epigenetic signal. Furthermore, the discovery of CcrM suggests that other solitary adenine methyltransferases may exist in bacteria. They can be expected to be identified when new whole genome sequences become available, and their study is likely to provide new insights into the biological roles of m6A.

Use of m6A to control DNA-protein interactions avoids the problem created by the high mutability of m5C, which undergoes relatively high frequencies of deamination, giving rise to thymine

101

. This might also explain why, in bacterial species that use m6A as an epigenetic signal, solitary m5C methyltransferases do not seem to have been selected to control crucial DNA-protein interactions. For example, no biological function has been yet found for Dcm in E. The existence of DNA-binding proteins (e. g., transcription factors) that recognize hemimethylated sites could thus permit an ordered sequence of events occuring during DNA synthesis.

Furthermore, reduction of energetically expensive pili synthesis may have selective value for the population 52 . 52 . 52 (

 525252 Switching of Pap phase variation is controlled at the transcriptional level by a mechanism involving Dam methylation and the leucine-responsive regulatory protein, Lrp52. The upstream-regulatory sequence of the papBA operon contains six binding sites for Lrp (Figure3). Two of these sites contain GATC motifs (GATC dist , located in site 5, and GATC prox , located in site 2). In the OFF state, Lrp binds cooperatively and with high affinity to sites 1, 2, and 3, and prevents RNA polymerase binding and transcription of the pap operon. Lrp binding at sites 1-3 reduces the affinity of Lrp for sites 4, 5, and 6. Owing to Lrp binding at sites 1-3, methylation of nascent DNA molecules after passage of the replication fork is prevented, and GATC prox becomes unmethylated after two rounds of replication. In contrast, the GATC dist located in the unbound site 5 can undergo a normal cycle of hemimethylation / methylation. The high affinity of Lrp for the unmethylated GATCprox and its inability to bind a methylated GATC dist will create a feedback loop that propagates the OFF state. Hence, methylation of GATC dist and unmethylation of GATC prox are hallmarks the OFF state (Figure 3). Switching to the ON state requires that Lrp is translocated to the cognate binding sites 4-6. One of them (number 5) contains GATC dist . Translocation requires the ancillary protein PapI, which increases the affinity of Lrp for both sites 4-6 and 1-3, likely by biding to the GATCs present within these regions 52,53 . However, the affinity of PapI/Lrp for sites 4-6 is much higher than for sites 1-3, tending to move PapI-Lrp to sites 4-6 at low PapI levels. Methylation of GATC prox inhibits binding of PapI/Lrp, thus facilitating movement of PapI/Lrp to sites 4-6 53 . Hence, unmethylation of GATC dist and methylation of GATC prox define the pattern of the ON state One of the pap products, PapB, activates papI transcription, thereby creating a positive feedback loop that will propagate the ON state Figure 3). David Low's model for pap regulation envisages that switching in both directions requires replication, and that a critical factor for switching is the PapI level 53 . The latter is regulated by hitherto unknown mechanisms, and an appealing hypothesis is that PapI synthesis may be indirectly controlled by the ribosome by regulating PapB expression (D. A. Low, pers. comm.). Additional regulators of the pap operon include the nucleoid protein H-NS 52 and the RimJ N-acetyltransferase 54 which repress Pap pili synthesis at low temperature, the cyclic AMP-dependent regulator CRP

6 . 6 . 64 . 66 . 68 . 68 . 68 . 68 .A 48 .

 6664666868686848 Interestingly, the distribution of undermethylated GATC sites in the E. coli genome varies depending on growth conditions, raising the possibility that transduction of environmental or physiological signals can change the methylation state of certain GATCs 62,63 . DNA demethylases have not been described in bacteria; hence, active demethylation of GATC sites is unlikely to occur. Current evidence indicates that GATC undermethylation is caused by binding of proteins involved in gene regulation or nucleoid organization Local differences in the processivity of Dam methylase, which is influenced by the sequence context of GATC sites, may also contribute to GATC undermethylation Regulation of bacterial conjugation by Dam methylation Conjugal transfer of the Salmonella virulence plasmid (pSLT) and the F sex factor is repressed by Dam methylation 65,In pSLT, repression of mating by Dam methylation involves two concerted actions: (i) transcriptional activation of the finP gene, the product of which is a small RNA that inhibits conjugation 67 ; and (ii) transcriptional repression of the traJ gene, which encodes a transcriptional activator of the transfer operon At the finP promoter, Dam methylation prevents transcriptional repression by the nucleoid protein H-NS 67 . At the traJ promoter, Dam methylation prevents binding of Lrp, an activator of traJ transcriptionThe upstream activating sequence (UAS) of traJ contains two Lrp-binding sites (Figure5), both necessary for transcriptional activation. One site contains a GATC, and its methylation state affects Lrp binding: GATC methylation reduces Lrp binding, and residual Lrp protein bound to the UAS forms a complex that does not permit promoter activation. In contrast, GATC unmethylation and GATC hemimethylation permit Lrp binding, and formation of an activating complex near the -35 module This mechanism may regulate conjugal transfer in response to the occurrence of plasmid replication and the presence of sufficient Lrp remarkable trait of traJ regulation by Lrp and Dam methylation is that hemimethylated DNA molecules exhibit different properties depending on the location of m6A, in a fashion reminiscent of IS10 control When the traJ non-coding strand is methylated, Lrp-mediated activation is permitted; when m6A lies on the traJ coding strand, activation by Lrp is hindered68

82 , 83 . 83 . 83 . 85 . 86 . 85 . 85 . 85 .

 828383838586858585 Scarcity of GATC sites in the genomes of virulent phages may protect against cutting by hostMutH On the other hand, certain phages have dam genes which may contribute to protection against MutH by ensuring that GATC sites are methylated during the lytic cycle Dam methylation regulates transcription of the cre gene of phage P1[START_REF] Sternberg | Bacteriophage P1 cre gene and its regulatory region. Evidence for multiple promoters and for regulation by Dam methylation[END_REF] and the mom gene of Mu The mom gene encodes a DNA modification function that generates N 6 This unusual, modified base protects Mu DNA from a variety of hostcontrolled restriction systems. Transcription of mom is regulated by Dam methylation in a fashion reminiscent of agn43: methylation of three closely spaced GATC sites prevents binding of the repressor protein OxyR. In the mom promoter, however, the OxyR binding region is located upstream the -35 module OxyR is able to bind a hemimethylated mom promoter, and may limit mom expression during lytic phage development 85 . This action may explain why Mom-mediated modification of Mu DNA is more efficient after induction of a lysogen than during an exogenous lytic cycle Note that DNA methylation of phage DNA is usually incomplete during the lytic cycle, probably because the speed of rolling-circle replication exceeds the capacity of the Dam methylase Packaging of P1 DNA into capsids proceeds by a processive headful mechanism that uses concatemeric phage DNA molecules produced by rolling circle replication. Packaging is initiated at the pac site, a 162 bp sequence that contains seven GATC sites. Protein 9, the P1 packaging enzyme, can only cut pac if most of its GATC sites are methylated 87 . P1 produces its own Dam methylase, and the importance of m6A in P1 infection is indicated by the observation that a P1 Dam mutant produces only 5% of the normal phage titer upon infection of a Dam host. A tentative explanation is that protein 9, which is the product of an early phage gene, binds hemimethylated pac sites produced by theta replication, and protects them from the host Dam methylase

.. 90 . 90 . 90 ., 90 ; 5 ( 90 .and prevents replication initiation 90 ., 90 . 90 . 92 .

 9090909059090909092 The target for CcrM is 5'-GANTC-3'. Like Dam, CcrM is highly processive; hovever, unlike Dam, CcrM is more active on hemimethylated DNA than on unmethylated DNA 5 CcrM is an essential cell function, and participates in the regulation of the Caulobacter cell cycle 5,89,CcrM homologs have been found in Agrobacterium tumefaciens 5 , Rhizobium meliloti 5 , and Brucella abortus 91 . In both Agrobacterium and Rhizobium, CcrM is essential and participates in cell cycle regulation, suggesting that the roles of CcrM methylation may be conserved among α-Proteobacteria 5 . CcrM is also essential in Brucella, and aberrant CcrM expression impairs the ability of this pathogen to grow inside macrophages91 . Regulation of the Caulobacter cell cycle by CcrM methylation Caulobacter crescentus is a dimorphic bacterium with two different cell types: the replicating stalked cell and the non-replicating swarmer cell These cells differ in morphology and behaviour: the swarmer cell harbors a flagellum and is motile, while the stalked cell is nonmotile. Cell division yields one swarmer cell and one stalked cell CcrM methylase is only produced during the late stage of chromosome replication, which occurs only in the stalked cell 5the Caulobacter chromosome of stalked cells therefore remains hemimethylated until CcrM is produced. Activation of the Caulobacter replication origin (Cori) requires full methylation; hence, synthesis of CcrM methylase is a hallmark for completion of one cell cycle, and CcrM-mediated methylation of Cori provides a signal for the initiation of the next replication round Figure 6). Shortly after cell division, CcrM is degraded in both daughter cells 5,In the non-dividing swarmer cell, chromosome replication is prevented by CtrA, a global regulator that plays a major role in cell cycle regulation. CtrA binds to the replication origin, which is methylated, During swarmer-to-stalked cell differentiation, CtrA is degraded, and remains undetectable until chromosome replication has started. Absence of CcrM prevents methylation after DNA replication, and leaves the origin (and most of the chromosome) hemimethylated until the late stages of replication, when a burst in CcrM synthesis occurs. Transcription of the ccrM gene is activated by CtrA, which progressively accumulates in the stalked cell as chromosome replication progresses 5However, activation of ccrM transcription by CtrA is inhibited by methylation of two GANTC sites located in the leader of the ccrM coding sequence 5 . This inhibition may contribute to delay ccrM transcription until the replication fork reaches ccrM, and may serve to prevent earlier activation by CtrA 5,Synthesis of the key cell cycle regulator CtrA is also regulated by GANTC methylation. One of the two ctrA promoters (P 1 ) contains a GANTC site near its -35 module 92 . Transcription from P 1 is repressed when the GANTC is methylated. Passage of the replication fork renders the promoter hemimethylated, and activates transcription. This mechanism may serve to boost ctrA gene transcription in response to replication progression. In turn, CtrA accumulation will turn on synthesis of the CcrM methylase as soon as the replication fork reaches the ccrM gene This model is supported by elegant genetic evidence: if the ctrA gene is moved to an ectopic position near the replication terminus, ctrA transcription from the methylationsensitive P1 promoter remains repressed, and CtrA accumulates more slowly 92 .

99 .

 99 The existence of viral adenine DNA methyltransferases suggests a potential for horizontal gene transfer among unicellular eukaryotes 100 . A systematic study of the phylogenetic distribution of m6A in eukaryotes could determine whether vertical transmission or lateral gene transfer may explain the presence of m6A in some protists.

coli 4 . 64 .Figure 1 .

 4641 Figure 1. Overview of the roles of m6A in enteric bacteria: (i) defense against phages and transposons; (ii) regulation of chromosome replication, chromosome segregation, and reorganization of the nucleoid after DNA replication; (iii) DNA strand discrimination for mismatch repair: (iv) regulation of conjugal transfer of plasmids; (v) packaging of phage DNA into capsids; and (vi) transcriptional regulation of fimbrial operons and other virulence genes. When known, the methylation-sensitive DNA-binding proteins involved in each process are also indicated.

Figure 2 .

 2 Figure 2. Dam-directed mismatch repair. Assembly of the MutHLS complex at a mismatch is followed by MutH-mediated cleavage of the newly synthesized strand (shown in yellow) at the nearest GATC. Transient GATC hemimethylation in the newly synthesized strand provides the signal for strand discrimination. Depending on the distance, cleavage may require DNA looping (not drawn for simplicity).

Figure 3 .

 3 Figure 3. Regulation of the pap operon of uropathogenic E. coli (reproduced from ref. 52). Top panel: DNA adenine methylation states of the pap regulatory region. In the ON state, binding of Lrp to sites 4, 5, and 6 prevents methylation of GATC dist , while the unbound

Figure 4 .

 4 Figure 4. (Adapted from ref. 60). Model for switching in the agn43 gene. Methylation of GATC sites in the agn43 operator prevents binding of the OxyR repressor, and defines the ON state. After DNA replication, SeqA and OxyR compete for binding to the hemimethylated operator. SeqA binding is only transient and permits GATC methylation, thus propagating the ON state. In contrast, OxyR binding hinders GATC methylation, and agn43 is switched OFF in the following replication round. Switching to the ON state occurs when OxyR leaves the operator, permitting GATC methylation.

Figure 5 .

 5 Figure 5. Model for regulation of traJ transcription in the Salmonella virulence plasmid.The transcriptional activator Lrp binds to two cognate sites in the traJ UAS. Lrp binding to the downstream site is inhibited by GATC methylation; as a consequence, traJ is not transcribed in a non-replicating plasmid. Passage of the replication fork leaves the traJ UAS hemimethylated. However, activation of transcription occurs only in one daughter plasmid DNA molecule, because methylation of the coding strain does not permit formation of the Lrp-DNA activating complex.

Figure 6 .

 6 Figure 6. (Adapted from ref. 5). In Caulobacter crescentus, asymmetric cell division produces a non-replicating swarmer cell and a replicating stalked cell. In the swarmer cell, CtrA binding to the chromosomal origin of replication (Cori) inhibits DNA replication initiation, whereas CtrA proteolysis allows replication to occur in the stalked cell. Hence, DNA replication is only initiated on the methylated Cori of the stalked cell. Because CcrM methylase is degraded after cell division, passage of the replication fork is not followed by methylation of the daughter DNA strands. The extent of hemimethylation indicates the distance covered by the replication machinery, and can be viewed as a measure of time.

  23 .

	Dam-directed mismatch repair
	Chromosome replication, nucleoid segregation and Dam methylation
	Mismatched base pairs inevitably arise during DNA replication, and their repair requires a
	The replication origin (oriC) of the E. coli chromosome contains 11 GATC sites in 254 bp, a discrimination between the template strand and the newly synthesized, error-prone strand.
	density 10-fold higher than expected from a random distribution 4 . Chromosome replication This information is provided by transient lack of adenine methylation in the newly
	starts when the initiator protein DnaA binds at the oriC and separates the two strands of the synthesized DNA strand 40 . After recognition of a mismatched base pair by the MutS protein, a
	double helix 25 . DnaA binding at the oriC region is only possible if the oriC GATCs are complex involving MutS, MutL and MutH is formed 40 (Figure 2). When part of the ternary
	methylated; a hemimethylated origin is inactive 4,25 . complex assembled at a DNA mismatch, MutH is a GATC-specific endonuclease that cleaves
	the phosphodiester bond 5' to the G nucleotide in the non-methylated, newly synthesized
	Upon DNA replication, the GATC sites of oriC are not immediately methylated, and remain DNA strand. Transient GATC hemimethylation in the newly synthesized strand thus provides
	hemimethylated for up to one-third of the cell cycle 26 . The cause of this delay is that the the signal for strand discrimination by MutH 40 . The resulting 3' end is a substrate for the
	hemimethylated origin is sequestered by a protein called SeqA; as a consequence, in the UvrD helicase, and for exonucleases which degrade the daughter strand past the erroneously
	daughter oriC's, methylation of the newly synthesized strand by the Dam methylase is incorporated nucleotide 40,41 . Resynthesis of the gap by DNA polymerase III and
	prevented 27,28 . As long as SeqA-mediated hindrance of GATC methylation persists, the oriC phosphodiester bond formation by ligase then follow 40 .
	remains hemimethylated, and the start of a new replication cycle is delayed 29 .
	MutH endonuclease is also active on unmethylated GATC duplexes. Hence, in Dam -	strains,
	Dam methylation also has a role in the regulation of DnaA synthesis. One of the promoters of assembly of the MutHLS complex at a mismatch can result in MutH-mediated cleavage of
	the dnaA gene (dnaA2) is only active if its 3 GATC sites are methylated 30,31 . Methylation of GATC sites in both DNA strands 42 . This explains the sensitivity of Dam -mutants to agents
	the dnaA2 promoter is regulated by a sequestration mechanism analogous to that operating at that cause mismatches and other DNA lesions recognized by MutS 43-46 , as well as the
	oriC 25,26 . Because oriC and dnaA are separated by only 50 kb, both regions may be dependence of Dam -mutants on recombination and other DNA repair functions 4,22 . Another
	sequestrated almost simultaneously by SeqA 26,32 . Besides SeqA, a protein of unknown relevant phenotype of Dam -mutants is an elevated frequency of transition mutations,
	function that binds to hemimethylated DNA has been shown to contribute to dnaA consistent with the failure of MutHLS to deal properly with mismatches 4,22 . Interestingly,
	repression 33 . overproduction of Dam methylase results in higher mutation rates than its absence	4 . An
	explanation is that excess Dam methylase shortens the transient hemimethylation of newly
	Hemimethylation of oriC provides a signal for nucleoid segregation. The hemimethylated replicated DNA molecules, thereby preventing MutH-mediated incisions at hemimethylated
	origins of the two daughter chromosomes bind to segregation-driving proteins located in the GATC's 4 . It must be noted that the level of Dam methylase is tightly adjusted to growth rate 47	,
	outer membrane probably to permit sufficient (but not excessive) delay in the methylation of newly replicated 34,35 . SeqA also has a role in the process, as indicated by the observation that
	SeqA overproduction inhibits sister chromosome segregation and cell division 36 . SeqA binds DNA.
	also to hemimethylated GATC sites behind replication forks, and may play a role in nucleoid
	organization 37-39 .

Acknowledgments

Work in our laboratories is supported by grants from the Lejeune Foundation (to D. W.), and from the Spanish Ministry of Education and the European Regional Fund (to J. C., GEN2003-20234-CO6-03 and BIO2004-CO3455-CO2-02). We are grateful to David Low and Francisco Antequera for helpful discussions. D.W. thanks Profs. A. L. Benabid and F.

Berger for their support.


Minyu Cui
email: minyu.cui@irisa.fr

Angeliki Kritikakou
email: angeliki.kritikakou@irisa.fr

Lei Mo

Emmanuel Casseau
email: emmanuel.casseau@irisa.fr

Near-optimal Energy-Efficient Partial-Duplication Mapping of Real-Time Parallel Applications

Keywords: Fault tolerant, Task mapping, DVFS, Real-time execution, Reliability, Energy minimization

Minimizing energy consumption, as well as meeting real-time and reliability constraints, are major goals during system deployment. When complex platforms, such as multicore architectures with DVFS, and parallel applications are considered, these goals are significantly impacted by task mapping. To minimize energy consumption, while meeting real-time and reliability constraints, this work proposes a task mapping approach to jointly solve the problem of task allocation, task scheduling, frequency assignment, and task duplication. A novel heuristic algorithm is proposed to cope with this NP-hard problem, consisting of a pruning phase, which maintains only the task configurations that satisfy reliability constraints, and a mapping phase, which minimizes total energy consumption under real-time and precedence constraints. The obtained results show that the proposed heuristic obtains near-optimal results, with low computation time, compared to optimal solvers, while it achieves better energy consumption and finds more solutions compared to other heuristic approaches.

1 Introduction

Context

The execution of embedded real-time parallel applications on multicore platforms require guarantees for real-time execution [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Huang | Energy-efficient fault-tolerant mapping and scheduling on heterogeneous multiprocessor real-time systems[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] and reliability [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Due to technology size reduction, multicore platforms are susceptible to transient faults [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. Reliability is defined as the probability of executing a task without faults. Typical techniques to increase reliability are the execution of tasks with high frequency [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and task replication [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. However, both techniques can lead to large energy consumption. Dynamic Voltage and Frequency Scaling (DVFS) is a well-known energy management technique, which optimizes energy consumption by scaling down the processor supply voltage and frequency [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. However, this has a negative impact on reliability, since more transient faults occur at a low voltage and frequency level [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Therefore, during the task mapping not only task allocation and scheduling, but also frequency assignment and task replication should be incorporated in the optimisation process to achieve energy efficiency, while meeting real-time and reliability constraints.

Related work and motivation

Table 1 summarises representative State-of-the-Art (SoA) task mapping approaches that minimize energy consumption considering DVFS, under Real-Time (RT) and Reliability (R) constraints. The platform consists of Homogeneous (HO), Heterogeneous (HE) or Single (S) processor. The applied fault tolerance policy can be task Recovery (Rec.) or task Replication (Rep.). A task is executed successfully, if at least one replica is executed without faults [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. Last, the proposed solving method can Optimal (O) or Heuristic (H).

Approaches exist without applying a fault tolerance policy, e.g., the task mapping problem is decomposed into a sub-problem that satisfies the reliability constraint and another that minimizes resources [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and a whale optimization algorithm is proposed [START_REF] Deng | Reliability-aware task scheduling for energy efciency on heterogeneous multiprocessor systems[END_REF]. In [START_REF] Roeder | Energy-aware scheduling of multi-version tasks on heterogeneous real-time systems[END_REF], the scheduling algorithm for dependent multi-version tasks is studied based on Forward List Scheduling with the goal of minimise the total energy consumption under real-time constraint. Approaches execute a recovery task, e.g., individual [START_REF] Zhang | Joint optimization of energy efficiency and system reliability for precedence constrained tasks in heterogeneous systems[END_REF] or shared [START_REF] Huang | Energy-efficient fault-tolerant mapping and scheduling on heterogeneous multiprocessor real-time systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF], or both [START_REF] Guo | Reliability-aware power management for parallel realtime applications with precedence constraints[END_REF], with maximum frequency, exploring available time slack to meet the reliability constraint. Last, approaches apply task replication. Some works decide the required number of replicas per task to always meet the reliability constraint, e.g., for independent tasks on homogeneous platform [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF] and dependent tasks on heterogeneous platforms [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. In [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF], all replicas of a task are executed at same frequency, whereas in [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF] no real-time constraints are taken into account. In [START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF] the number of replicas per task is given. In the first phase, half-plus-one copies per task are executed. If a fault occurs, the second phase is applied to execute the remaining number of copies. Other works decide among different reliability mechanisms for each task. In [12], a heuristic explores among three reliability mechanisms in sequence to decide single task execution, task duplication and task triplication, without the requirements of always meeting the real-time and reliability constraints. In [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF], a heuristic determines which tasks to be duplicated, removing the need of a recovery task for all tasks. An optimal approach decides which task to duplicate, taking into account reliability and real-time constraints for independent [13] and independent tasks [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF].

Overall, optimal approaches are applicable only for small problem sizes and existing heuristics, either do not fully guarantee real-time or reliability constraints, or use a high number of replicas, leading to large energy consumption with a negative impact on execution time, and thus, potentially no feasible solution.

Contributions

This work addresses the task mapping problem of parallel applications on homogeneous multicore platforms with DVFS, with the goal of minimizing total energy consumption, under real-time and reliability constraints. An effective heuristic is proposed, considering multiple non-functional properties of execution time, energy and reliability, that combines task allocation, task scheduling, frequency assignment and selective task duplication. Unlike the majority of SoA techniques, original and duplicated tasks can have different operating frequencies, being more suitable for real-world systems [START_REF] Zhou | Resource management for improving soft-error and lifetime reliability of real-time MPSoCs[END_REF]. A pruning phase maintains only the task configurations that satisfy reliability constraints. A mapping phase minimizes total energy consumption under real-time and precedence constraints. Last, but not least, the proposed method is evaluated both with task graphs from real applications and randomly generated graphs. The experiment results show that our approach provides near-optimal energy sav- The rest of the paper is organized as follows. Section 2 introduces the system model. Section 3 presents the formulation of the proposed approaches. Section 4 presents the evaluation results. Finally, Section 5 concludes this study.

System Model

Table 2 shows the main notations. For the sake of paper presentation, when original and duplicated tasks must be distinguished in mathematical formulations, the subscript k ∈ {o, d} indicates the original task ( o ) or the duplicated task ( d ). If no subscript exists, the mathematical formulation is valid for both.

Task Model

This work considers a real-time application modelled as a Directed Acyclic Graph (DAG) G(V, E), where V denotes the set of N frame-based, nonpreemptive, dependent tasks {τ o 0 , . . . , τ o N -1 }, while E represents the edges, corresponding to the tasks' precedence constraints. Tasks are released at time 0 and have a global deadline D, given by the application frame. If a task has no predecessors (successors), it is an entry task τ entry (exit task τ exit ). A task is ready for execution when all its predecessors have been completed. Each task τ i is described by a tuple {W i , R th i }, where W i is the Worst Case Execution Cycles (WCEC) and R th i is its reliability threshold. Each task has its own reliability constraint, since functions of an application exhibit distinct vulnerabilities, due to variations in the spatial and temporal vulnerabilities of different instructions [12].

Platform Model

The target platform has a shared-memory multicore architecture with M homogeneous processors M = {θ 0 , . . . , θ M -1 }. Each processor supports DVFS and has L pairs of frequency/voltage level {(f 0 , v 0 ), . . . , (f L-1 , v L-1 )}. As the relationship of voltage and frequency is almost linear [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF][START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF], we use the term frequency scaling to express the simultaneous change of voltage and frequency. We consider intra-task DVFS. When task τ i is executed with frequency f l , its execution time is Wi f l . The power consumption is modeled as the sum of static power P sta l and dynamic power P dyn l considering a voltage/frequency level (v l , f l ) [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Specifically,

P l = P sta l + P dyn l = P sta l + C ef f v 2 l f l , (1)
where C ef f is the effective switching capacitance.

Fault Model and Reliability

This work addresses transient faults, having a higher occurrence than permanent faults during the useful lifetime of the system [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF]. During this period, the fault model, where the fault occurrence is given by a Poisson distribution with an average fault rate λ(f l ) at frequency f l , is typically used [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF][START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF]. The failure rate per time unit of a processor at frequency f l is given by

λ(f l ) = λ 0 × 10 d0 fmax-f l fmax-f min , (2)
where f max = max ∀l {f l }, f min = min ∀l {f l }, λ 0 is the average failure rate of the processor corresponding to f max , and d 0 is a positive constant, indicating the sensitivity of failure rates to voltage scaling [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. The reliability of task τ i is defined as the probability of executing τ i without any fault. Based on the exponential model in [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF], the reliability of a task executed at f τi is calculated as

R i (f l ) = e -ϕi(f l ) , (3)
where ϕ i (f l ) = λ(f τi ) × et i,l , and et i,l is the execution time of task τ i at frequency f l . If the reliability of original task τ o i is larger than its reliability threshold R th i , the execution is considered as reliable [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and the task reliability is given by R i = R o i . Otherwise, the task τ o i is duplicated and executed on a different processor, since it is unlikely that the execution of both original and duplicated tasks on different processors fail [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. The duplicated task τ d i has the same characteristics with the original task τ o i . When the duplicated task τ d i is executed, its reliability is R d i and depends on the frequency it is executed. Then, the task reliability, after duplication, is

R i = 1 -(1 -R o i )(1 -R d i ). (4)
As our approach finds an offline optimal task mapping solution, with the goal of minimizing energy consumption, we consider only task duplication, i.e., a single replica per task, in order not to unnecessarily increase the number of replicas, in case no faults occur. An online mechanism can be applied to further improve the energy consumption of our solution (by not executing the duplicated task, when the first execution is correct), and to deal with the low probability cases, where both original and duplicated tasks are faulty. In this work, cores are assumed to operate below a temperature threshold, where temperature impact on reliability is low [START_REF] Skadron | Temperature-aware microarchitecture: Modeling and implementation[END_REF].

Problem under study

Given a DAG task graph G and M processors, the goal is to minimize the total energy consumption by deciding the: 1) task duplication, 2) assignment of frequencies to tasks, 3) allocation of tasks to processors, 4) start time of tasks, subject to reliability, real-time and task precedence constraints.

Proposed Approach

To solve the problem under study, we propose a Heuristic for Reliability-aware Fault-tolerant Task Mapping (H RAFTM), described in Algorithm 1. The algorithm consists of two phases:

1. Phase A obtains, per task, the set of possible configurations that meet the reliability constraint, ordered in decreasing energy consumption. 2. Phase B obtains the application mapping, by allocating tasks to processors using the least total energy consumption, under task precedence and realtime constraints.

H RAFTM is based on the following definitions:

Definition 1 (Configuration). A configuration j of a task τ i is denoted as

C j i = {f o i , f d i , et o i , et d i , E o i , E d i , R i }, where f o i (f d i ) is the assigned frequency, et o i (et d i ) is the required execution time, E o i (E d i )
is the energy consumption of the original (duplicated) task, and R i is the reliability of the task (taking into account task duplication). If the task is not duplicated, we have

f d i = et d i = E d i = 0. Definition 2 (Task Mapping). A mapping of a task τ i , under the task con- figuration C j i , is denoted as T M C j i i = {θ o i , θ d i , st o i , st d i }, where θ o i (θ d i )
is the allocated processor, and st o i (st d i ) is the start time of the original (duplicated) task. If a task is not duplicated, then f d i = 0, and the duplicated task takes no execution time, i.e., its start time is equal with its final time,

st d i = f t d i .
Definition 3 (Application Mapping). The mapping of the application (AM) is given by the set of mappings of N original tasks and S ⊆ N duplicated tasks. The mapping is valid if task precedence and real-time constraints are satisfied.

The next paragraphs describe in details the two phases of the proposed approach and illustrate them using the application DAG example of Fig. 1. 3.1 Phase A: Task configurations, under reliability constraint.

Phase A (Lines 1-9) is applied per task. For each task (Line 1), a Reliability, execution Time, Energy consumption (RTE) table is created based on all possible configurations (Line 2). For instance, part of the RTE of task τ 5 is depicted in Fig 1 . A pruning step removes the task configurations that do not satisfy the reliability constraint (Line 3). i) Reliability Constraint: A task must be executed meeting its reliability requirement, i.e., R i ≥ R th i . For instance, assuming that the reliability of τ 5 is R th 5 = 0.9994, the configurations C 0 5 , C 1 5 and C 2 5 are pruned in this step. The result is the Feasible Configurations (F C) of the task. F C i considering only the original task τ o i (when f d i = 0 no duplicated task exists) serve as Baseline Configurations (BC) (Line 4). In our illustration example, the BC of τ 5 are C 3 5 , C 4 5 and C 5 5 . The next step prunes any feasible configuration with duplicated tasks, if both the energy consumption and the execution time are larger than any defined BC i (Lines 5-7), e.g., C RT E i = {C j i : C j i is a configuration of τ i } ;

3:

F C i = RT E i -{C j i : R i < R th i };
4:

BC i = {F C i : f d i = 0}; 5:
for each configuration bc in BC i do 6:

P C i = F C i -{F C i : f d i = 0 ∧ min{et o i , et d i } ≥ et bc ∧ {E o i , E d i } > E bc }; 7:
end for Phase B uses Phase A task configurations and performs the application mapping, subject to the following constraints:

SC i = rP C i [0]; 16: Compute T M SCi i (st i = EST i in
ii) Precedence constraints: Based on the dependencies defined by the task graph, a task τ i can start execution only when all its predecessors are completed. Task predecessors include also the duplicated tasks, since our approach is applied offline, and thus, strict scheduling is considered where a task can be executed after all its predecessors are finished. Then, the Earliest Start Time (EST) of τ i given by

EST i = 0, if τ i = τ entry max τj ∈P red{τi} {EF T j }, else (5)
where P red{τ i } is the set of τ i 's predecessors, and EF T j = EST j + et j is the Earliest Finish Time (EFT) of task τ j .

iii) Deadline constraint: The application must be finished before the deadline D. The Schedule Length, SL, of task graph G, under a given application mapping AM , is determined by the latest finish time of exit tasks:

SL AM = max{f t τexit } ≤ D. (6)
Due to precedence constraints, the start time of a task is st i ≥ EST i . Our goal is to exploit the available time slack to save energy, thus, we initially consider that tasks start execution as soon as possible, i.e., st i = EST i , ∀τ i . iv) Non-overlapping constraint: Only a single task should be executed on a processor at a given time instance. Taking into account the earliest available time, avail[m], when processor θ m is ready for a task execution, EST i is modified as

EST i =      0, if τ i = τ entry max max τj ∈P red{τi} {EF T j }, avail[m],
, else

The text paragraphs describe the three steps of Phase B (Lines 10-26):

Step 1 (Lines 10-13): Priorities are given to tasks for task allocation based on the upward rank value [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], rank i , which is common for original and duplicated tasks (Lines 10-12):

rank i = et i , if τ i = τ exit et i + max τj ∈Succ{τi} {rank j }, else (8)
where et i = ( L l=1 W i /f l )/L is the average computation time of τ i and Succ{τ i } the immediate successors of τ i . Then, the Priority List (PL) is ordered in decreasing rank value (Line 13).

Step 2 (Lines 14-23): The initial application mapping AM 0 is generated to check if the problem is feasible and whether time slack is available. For all task, AM 0 uses the first configuration in rP C i as the Selected Configuration SC i (Line 15). Setting st i = EST i to Eq. 7, we obtain the task mapping (T M SCi i ) per task (Line 16). The set of all task mappings provides the AM 0 (Line 18). Then, its schedule length SL AM0 is obtained (Line 19). If it is higher than the deadline, the problem is infeasible (Lines 20-21), and the algorithm stops. If it is equal to the deadline, the initial application mapping is the final mapping and the algorithm stops (Lines 22-23).

Step 3: (Lines 25-26) If the initial schedule length is less than the deadline (Line 24), time slack exists. Overall, different task configurations and different tasks that can be relaxed in order to obtain energy savings. Algorithm 2 Algorithm 2: Mapping Relaxation Algorithm.

1: AM = AM 0 , SL = SL 0 ; 2: while SL < D and rP C i > 1(∀τ i ) do 3:

for each task τ i in N do 4:

N C A i = rP C i [0]; 5: N C B i = rP C i [j] with max k∈{o,d} (ES j τ k i /T I j τ k i ) ;
6:

N C i = (E N C A i ≤ E N C B i ?N C A i : N C B i ); 7:
Compute T M N Ci i , i ∈ N (st i = EST i in Eq. 7);

8:

AM i = {T M N Ci i }; 9:
Compute SL AMi (Eq. 6);

10:

SLI i = SL AMi -SL;
11:

Gain i = k∈{o,d} (ES N C i τ k i /T I N C i τ k i
))

SLIi

;

12:

end for 13:

for each task τ i in N do 14:

Compute slack AMi (Eqs. 7, 9, 10); for each configuration pc in rP C τ rel do 20:

rP C τ rel = rP C τ rel -{rP C τ rel : E pc ≥ E SCτ rel }; 21:
end for 22: end while decides the task to be relaxed and its configuration. Initially, the current mapping (schedule length) is initialised with the initial mapping (schedule length) (Line 1). The algorithm is applied iteratively, until the schedule length reaches the deadline or all tasks reach their configuration with the least energy consumption (Line 2). First, a local search decides a new configuration per task (Lines 3-12). We combine two criteria to select a potential New Configuration (N C i ) for a task. ) is the time increase of task τ i in configuration j, compared to the current selected configuration SC i . The final selected configuration N C i is the one with the minimum energy consumption (Line 6). After selecting a new task configuration, all task mappings are updated accordingly (Line 7). The new application mapping AM i (Line 8) and its schedule length SL AMi (Line 9) are obtained. The difference of SL AMi with the schedule length of the current mapping SL provides the Schedule Length Increase (SLI i ), when task τ i changes its current configuration SC i to N C i (Line 10). With this in-formation, the overall gain (Gain i ), considering both energy and time, that this configuration modification will bring to the overall mapping, is computed (Line 11). After the local search finishes, the global decision takes place (Lines 13-22). The time slack of each task in the current mapping (slack AMi ) based on task mobility through Eqs. 7, 9, 10 (Lines 13-15):

slack AMi = LF T i -EST i -et i . (9)
The Latest Finish Time (LFT) of τ i is:

LF T i =        D, if τ i = τ exit min    min τp∈P roc{τi} {LST τp }, min τj ∈Succ{τi} {LST τj },    , else (10)
where LST i = LF T i -et i is the Latest Start Time (LST) of task τ i . P roc{τ i } is the processor that the task is allocated, and τ p are the tasks, scheduled after task τ i , on the same processor. The task (and its corresponding configuration) to be relaxed (τ rel ) is the task with highest overall gain, whose time increase in this new configuration is not larger than its available slack in the current mapping (Line 16). Last, the selected configuration (SC) for the relaxed task, the application mapping and its schedule length are updated (Lines 17-18) and all configurations that have a higher energy consumption than the selected one are removed from rP C τ rel (Lines 19-21). ) and on the right the initial schedule configuration for each task. The total energy consumption of AM 0 is E AM0 = 48.12 mJ and schedule length is SL AM0 = 1.3515 sec. Since the schedule length is lower than the deadline, there exists some time slack. During relaxation (step 3), the task τ 1 is selected, along with the configuration where both original and duplication copies are executed with frequency f 2 , since this task and configuration provide the highest gain, since the energy consumption is reduced without increasing the schedule length (Inf means positive infinity in Fig. 3 and the one with most energy saving is selected if there are multiple Inf cases). The updated application mapping is depicted in Fig. 3. The algorithm continues to apply relaxation, as long as time slack is still available, by selecting the next task and configuration with the highest gain. The final application mapping is depicted in Fig 4, with an energy consumption equal to E = 41.67 mJ and a schedule length of SL = 1.3971 sec.

Time complexity

In the proposed heuristic approach, the maximum number of possible configurations for each task is L + 2 L (denoted as K). Phase A takes O(N K) time to obtain the possible configuration space for all tasks. Phase B firstly Fig. 4: Illustration example (Fig. 1): Final application mapping.

*Scheduled configuration C j i f o i f d i SLI i Gain i (GHz) (GHz) (sec) C 0 0 1.0 - - - C 0 1 1.0 - - - C 0 2 1.0 1.0 - - C 0 3 1.0 - - - C 0 4 1.0 - - - C 0 5 1.0 - - -
requires O(N logN ) time to create the priority list (PL). When task mapping is computed based on Eq. 7, for each single task mapping, the complexity is O(2logN ) considering the worst case that both original and duplication copies are executed. For each single application mapping, it traverses N tasks, so the time complexity is O(2N logN ). For each experiment, considering the worst case when deadline is very relaxed so that all configurations for all tasks have to be explored in the relaxation algorithm, the total complexity of the whole application mapping under this very relaxed deadline is O(2N 2 KlogN ).

Experimental Results

This section evaluates the proposed heuristic (H RAFTM) with i) the optimal solver using Gurobi 9.0.2 (O RAFTM) as in [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF], and ii) two SoA heuristics a) the Reliability-Aware Mapping (H RAM), that meets the reliability constraint without task duplication, similar to [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and ESRG algorithm in [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], and b) the Task Duplication Mapping (H TDM), applying task duplication for all tasks, similar to [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], when the number of replicas is two, or to [START_REF] Tosun | Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures[END_REF], with 100% task duplication. To evaluate the approaches, the following metrics are used:

1. Feasibility, i.e., the number of experiments where a solution is found out of the total number of experiments (NE). 2. Energy Consumption (EC) of proposed heuristic approach, compared to the energy consumption of the optimal approach O RAFTM two SoA heuristic approaches H RAM and H TDM. 3. Reliability Improvement (RI) (RI = R i -R th i ), i.e., the task reliability above the task reliability threshold. 4. Computation time (CT), i.e., the time required for each approach to find a solution.

Note that, an approach may fail to find a solution, especially in strict deadlines. In order to fairly compare the energy consumption, reliability improvement and the computation time, we present the average values of the experiments where both compared approaches (i.e., O RAFTM vs H RAFTM, H RAFTM vs H RAM, or H RAFTM vs H TDM) were able to find a solution.

The model of the processor is based on a 32-bit RISC-V Instruction Set Architecture (ISA) with 5-stage pipeline [START_REF] Rokicki | What you simulate is what you synthesize: Designing a processor core from c++ specifications[END_REF]. Regarding DVFS, L = 6 voltage/frequency levels are used [START_REF] Quan | Feasibility analysis for temperature-constraint hard realtime periodic tasks[END_REF] (Table 3), considering 64 nm technology. The number of processors in the experiments is M = 2, 4, 6. The task graphs are obtained both from real-world applications and randomly generated tasks. Regarding real-word applications, two commonly used parallel applications with different shapes of parallelism have been considered, i.e., Fast Fourier Transformation (FFT) (N = 15) and Gaussian Elimination (GE) (N = 14) [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF]. Fig 5 depicts the shape of parallelism obtained by FFT and GE DAGs. Random generation is used for comparison with optimal approach (N = 10) and for evaluation of the scalability of the heuristics (100). To obtain realistic values for the W i of a task, common benchmarks from MiBench suite were executed on the processor. The execution cycles and memory accesses are counted and WCEC is computed, assuming that all cores may conflict during a memory access. The obtained range is [1 × 10 8 , 4 × 10 8 ], and it is used to randomly select the W i of a task. The reliability threshold R th i of a task is selected within the range [0.9990, 0.9995], considering a typical magnitude 10 -3 for reliability target [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. For each application task graph, a number of experiments (denoted as N E) is performed, each time with different task characteristics (W i and R th i ). For each experiment, D is tuned from strict to relaxed deadlines, starting from SL AM0 of the initial application mapping and increased with a step of 0.1 seconds for small randomly generated DAGs and real-world DAGs and 0.5 seconds for large randomly generated DAG. Regarding feasibility, when M = 2, the H RAFTM feasibility is very close to the optimal feasibility, as shown in Fig. 6a, except for a few cases when the deadline is strict. The average difference before achieving 100% feasibility is 3.3%. With the number of processors increasing to M = 4 (Fig. 6c) and M = 6 (Fig. 6e), H RAFTM and O RAFTM achieve the same feasibility, since more resources are available to execute the original and potentially duplicated tasks.

Comparison with optimal approach

Regarding energy consumption in Fig. 6b and3.38% (M = 6) more energy than the optimal solutions. With the processor number increasing, the energy consumption of both proposed heuristic and optimal solution flattens at earlier deadlines, since there are more processors resource available to perform the task mapping, and thus, more options to start the tasks earlier.

Regarding reliability improvement, H RAFTM provides more reliability improvement than optimal solutions at the price of consuming slightly more energy under the same deadlines, as depicted in Fig. 7a The average computation time of O RAFTM and H RAFTM is computed over the number of experiments than found a feasible solution. Table 4, Table 5 and Table 6 show the results in seconds per deadline D. It can be observed that although few tasks and processors are used, the time to obtain the optimal solution is very long, on average 10 4 more than the proposed H RAFTM. Overall, the obtained results show that i) H RAFTM provides near-optimal solutions, and the solutions tend to converge to the optimal ones with the number of processors increasing, ii) as expected, H RAFTM takes significantly less time to obtain the results compared to the optimal approaches.

Comparison with other heuristics

This section evaluates the behavior of the proposed H RAFTM heuristic to H RAM and H TDM heuristics, considering real-world application DAGs and large random generated DAGs.

Real-word DAG

The quality of solutions obtained by H RAFTM, H RAM and H TDM heuristics for the FFT (N = 15) are compared in Fig. 8 and Fig. 10, and for the GE (N = 14) in Fig. 9 and Fig. 11, considering M = 2, M = 4 and M = 6 processors, and N E = 20 experiments.

The feasibility of the three heuristics for FFT and GE benchmarks is depicted in the left column of Fig. 8 and Fig. 9. Comparing to H TDM, the proposed H RAFTM can find solutions in significantly more experiments than H TDM, especially when the deadline is not fully relaxed or number of cores is reduced. When tasks meet their reliability constraint, H RAFTM does not need to duplicate these tasks. However, H TDM duplicates all tasks, and thus, it is able to find solutions only when the deadline is relatively relaxed or several processors exist to run the tasks in parallel. Before obtaining 100% feasibility for both approaches, on average, H RAFTM finds a solution in more experiments than H TDM, i.e., 70.2% for FFT and 59.4% for GE (M = 2), 47.5% for FFT and 14.5% for GE (M = 4) and 47.5% for FFT and 2.2% for GE (M = 6). Note that, H RAFTM and H RAM have the same feasibility. This behavior is explained as follows: when H RAM finds a solution, it means the reliability constraint of all tasks can be met by executing only the original task with a high frequency. In this case, H RAFTM is also able to find this solution. The energy consumption obtained by the solutions of the three heuristics for FFT and GE is depicted in the right column of Fig. 8 and Fig. 9. Comparing H RAFTM and H RAM, we observe that they consume similar energy at very strict deadlines, when the number of processors is small. In this case, H RAFTM behaves similarly to H RAM, i.e., mainly executing the original tasks with the frequency required to achieve the reliability constraint. With deadline relaxing, H RAFTM starts to consume less energy than H RAM. H RAFTM achieves this gain by exploring the available time slack to duplicate tasks in order to save energy, e.g., up to ∼50.9% for FFT at relaxed deadlines. Similarly, when more processors are available, H RAFTM can take advantage of these resources and execute duplicated task in parallel. Comparing H RAFTM and H TDM, as H TDM applies task duplication for every task, it cannot find solutions in very strict deadlines. H RAFTM consumes significantly less energy than H TDM. H RAFTM selects the task configuration, if exists, with only the original task, meeting the reliability constraint and consuming less energy than configurations with duplicated tasks. Since H TDM duplicates all tasks, its energy consumption can be significant, when it finds a solution. In relaxed deadlines, H RAFTM behaves similar to H TDM, i.e. duplicates the tasks when less energy is consumed.

The average reliability improvement obtained by the solutions of the three heuristics is depicted in the left column of Fig. 10 and Fig. 11. H RAFTM achieves higher reliability than RAM, except in very strict deadlines. As explained above, when there is not available time slack to perform duplication, H RAFTM behaves similarly to H RAM as most of the tasks are executed with only their original copy. Compared to H TDM, H RAFTM provides lower reliability for tight deadlines, as it duplicates only a part of the task-set. The same reliability improvement can be achieved in relaxed deadlines, since both H RAFTM and H TDM duplicate tasks similarly.

The computation time of H RAFTM, H RAM and H TDM heuristics is depicted in the right column of Fig. 10 and Fig. 11. Overall, when the deadline increases, the trend of computation time for H RAM is to remain stable, for H RAFTM to slightly increase and for H TDM to increase with a higher factor. The computation time to obtain a feasible solution increases with deadline relaxing, due to the fact that the proposed heuristic explores the P C space for each task, based on the deadline constraints. Therefore, the more relaxed the deadline is, the larger is the P C space to be explored per task, and thus, more time is needed. Note that, H TDM is the most expensive approach in terms of computation time. This behavior is due to the fact that all tasks are duplicated, which increases the total number of tasks to be scheduled and the number of P Cs in each task P C space, and thus, the time to find a solution. For H RAM, it only executes original tasks, thus it has a reduced number of P Cs in the P C space, taking the least time to obtain a solution. However, it provides less energy savings as explained above, especially at relaxed deadlines. the deadline is not fully relaxed or number of cores is reduced H RAFTM has increased feasibility compared to H TDM, i.e., 84.8% for M = 2, 85.7% for M = 4 and 83.8% for M = 6. Moreover, as the number of processors is increased the energy consumption is reduced as lower frequencies can be selected and partial task duplication can be applied by H RAFTM, as long as the reliability constraint is met. Regarding computation time, it is increased when the number of tasks increases as expected, but still remains low compared to the prohibited computation time required for the optimal approach. For a small randomly generated task with N = 10 (Table 5 when M = 4 and Table 6 when M = 6), the proposed heuristic takes less than 1 sec to find a solution for all experiments whereas for a large randomly generated task with N = 100, the average com-putation time (considering all experiments and deadlines) is 144 sec (M = 2), 159 sec (M = 4) and 212 sec (M = 6). Comparing the computation time of the three heuristics for large DAGs N = 100, the average computation time for H RAM is 52 sec (M = 2), 66 sec (M = 4) and 75 sec (M = 6). For H TDM, the average computation time is 488 (M = 2), 501 sec (M = 4) and 718 sec (M = 6). Overall, we observe that the H TDM is the more time consuming approach, and H RAM the least time consuming approach. However, H TDM is not able to always find solutions, whereas H RAFTM finds solutions with always same or less energy consumption compared to H RAM and H TDM.

Large random generated DAGs

Conclusion

A heuristic algorithm is proposed to obtain the task mapping of parallel applications, under real-time, reliability and task dependency constraints. The goal is to minimize total energy consumption by deciding frequency assignment, task allocation, task scheduling and task duplication. Based on the experimental results from real-world applications and randomly generated task graphs, the proposed heuristic achieves near-optimal results, with low computation time. Compared to similar heuristics, it achieves better energy consumption and is able to find solutions even when the other approaches fail. As future work, we will propose similar heuristics for other DVFS schemes provided by platforms, such as assigning a common frequency at cluster, processor and platform level.

  Part of RT E 5 * with W 5 = 1.4728 × 10 8 and R th 5 = 0.9994 *Processor model based on Table3

1 Fig. 1 :

 11 Fig. 1: Illustration example: Application DAG (N = 6) and part of RT E 5 .

  N C A i explores rP C i sequentially, by selecting always the first configuration. N C B i selects the j configuration in rP C i with the highest value (

Fig. 2 ,

 2 Fig. 3 and Fig. 4 illustrate the application mapping process for the DAG in Fig 1, when M = 3 processors and D = 1.4. Fig 2 shows on the left the initial application mapping AM 0 (step 1 and step 2

Fig. 2 :Fig. 3 :

 23 Fig.2: Illustration example (Fig.1): Initial application mapping AM 0 .

Fig. 5 :

 5 Fig. 5: Real-world application DAG.

Fig. 6

 6 Fig. 6 and 7 compare the quality of solutions obtained by O RAFTM and H RAFTM approaches. We present the results of N E = 10 considering random graphs with N = 10 tasks, M = 2, M = 4 and M = 6 processors.Regarding feasibility, when M = 2, the H RAFTM feasibility is very close to the optimal feasibility, as shown in Fig.6a, except for a few cases when the deadline is strict. The average difference before achieving 100% feasibility is 3.3%. With the number of processors increasing to M = 4 (Fig.6c) and M = 6 (Fig.6e), H RAFTM and O RAFTM achieve the same feasibility, since more resources are available to execute the original and potentially duplicated tasks.Regarding energy consumption in Fig.6b, Fig 6d, and Fig 6f, H RAFTM generally consumes slightly more energy than O RAFTM. When deadline is relaxed, H RAFTM and O RAFTM obtain solutions with the same energy consumption. H RAFTM consumes on average 7.3% (M = 2), 4.4% (M = 4)and 3.38% (M = 6) more energy than the optimal solutions. With the processor number increasing, the energy consumption of both proposed heuristic and optimal solution flattens at earlier deadlines, since there are more processors

  Fig. 6 and 7 compare the quality of solutions obtained by O RAFTM and H RAFTM approaches. We present the results of N E = 10 considering random graphs with N = 10 tasks, M = 2, M = 4 and M = 6 processors.Regarding feasibility, when M = 2, the H RAFTM feasibility is very close to the optimal feasibility, as shown in Fig.6a, except for a few cases when the deadline is strict. The average difference before achieving 100% feasibility is 3.3%. With the number of processors increasing to M = 4 (Fig.6c) and M = 6 (Fig.6e), H RAFTM and O RAFTM achieve the same feasibility, since more resources are available to execute the original and potentially duplicated tasks.Regarding energy consumption in Fig.6b, Fig 6d, and Fig 6f, H RAFTM generally consumes slightly more energy than O RAFTM. When deadline is relaxed, H RAFTM and O RAFTM obtain solutions with the same energy consumption. H RAFTM consumes on average 7.3% (M = 2), 4.4% (M = 4)and 3.38% (M = 6) more energy than the optimal solutions. With the processor number increasing, the energy consumption of both proposed heuristic and optimal solution flattens at earlier deadlines, since there are more processors

= 6 Fig. 6 :

 66 Fig. 6: Feasibility and Energy Consumption (EC in mJ) of optimal and heuristic approached for M = 2, M = 4 and M = 6 (N = 10)

  , Fig 7b, and Fig 7c.

= 6 Fig. 7 :

 67 Fig. 7: Reliability Improvement (RI) of optimal and heuristic approached for M = 2, M = 4 and M = 6 (N = 10)

= 6 Fig. 8 :

 68 Fig. 8: Feasibility and energy consumption (EC in mJ) of FFT (N = 15) for M = 2, M = 4 and M = 6.

= 6 Fig. 9 :

 69 Fig. 9: Feasibility and Energy Consumption (EC in mJ) of GE (N = 14) for M = 2, M = 4 and M = 6.

Fig. 12 and 6 Fig. 10 :

 12610 Fig. 12 and Fig. 13 compare the quality of solutions obtained by H RAFTM, H RAM and H TDM heuristics for a large randomly generated task graph with N = 100, M = 2, M = 4 and M = 6 processors, and N E = 10 experiments. Previous observations regarding feasibility, energy consumption, reliability improvement and computation time for the three heuristics are also verified by the experiments with the large randomly generated DAG. For instance, as

= 6 Fig. 11 :

 611 Fig. 11: Reliability improvement (RI) and Computation Time (CT in seconds) of GE (N = 14) for M = 2, M = 4 and M = 6.

= 6 Fig. 12 :

 612 Fig. 12: Feasibility and Energy Consumption (EC in mJ) of large randomly generated DAG (N = 100) for M = 2, M = 4 and M = 6.

= 6 Fig. 13 :

 613 Fig. 13: Reliability Improvement (RI) and Computation Time (CT in seconds) of large randomly generated DAG (N = 100) for M = 2, M = 4 and M = 6.

Table 1 :

 1 Comparison with representative SoA approaches

	Ref.	Task model I. D.	Fault tol.	Platform	Constraints Solution

Table 2 :

 2

	Notations	Definitions
	τ o i /τ d i (v l , f l )	the original/duplicated copy of task τ i the l th voltage/frequency level
	W i	WCEC of task τ i
	D	the global deadline
	R th i	reliability threshold of task τ i
	SL	schedule length of DAG G
	EST i	earliest start time of task τ i
	LF T i	latest finish time of task τ i
	st i	actual start time of task τ i
	f t i	actual finish time of task τ i
	et i	execution time of task τ i
	slack i	time slack of task τ i
	P red{τ i }	all immediate predecessors of task τ i
	Succ{τ i }	all immediate successors of task τ i
	proc{m}	task set that are allocated on processor θm
	SC i	Selected configuration of task τ i in current task mapping
	N C i	New checked configuration of task τ i

Main Notations and their definitions ings, with low computation time compared to optimal solvers, while it has better energy consumption and feasibility compared to other heuristics.

  10 5 and C 26 5 in our illustration example of Fig 1. The result is the Possible Configurations (P C). The P C are ranked based on decreasing energy consumption (rP C i ) (Line 8).

	Algorithm 1: Proposed H RAFTM algorithm.
	Require: Task graph (G) and set of processors (M ).
	Ensure: Application mapping (AM ).
	// Phase A
	1: for each task τ i in N do
	2:

  Compute rank i (Eq. 8); 12: end for 13: P L = {N : ordered in decreasing rank i }; 14: for each task τ i in P L do

	8:	rP C i = {P C i : P C i decreasing energy consumption};
	9: end for
		// Phase B
	10: for each task τ i in N do
	11:
	15:

  Eq. 7); 17: end for 18: AM 0 = {T M SCi

	25:	AM relaxation (Algorithm 2);
	26: end if
	3.2 Phase B: Application mapping, under precedence and real-time
	constraints.

i }; 19: Compute SL AM0 (Eq. 6); 20: if SL AM0 > D then 21: Infeasible problem, algorithm stops. 22: else if SL AM0 = D then 23: AM = AM 0 , algorithm stops. 24: else if SL AM0 < D then

Table 3 :

 3 Processor characteristics

	v l (V)	0.85	0.90	0.95	1.00	1.05	1.1
	f l (GHz)	0.801	0.8291	0.8553	0.8797	0.9027	1.0
	C ef f	7.3249	8.6126	10.238	12.315	14.998	18.497

Table 4 :

 4 Computation time (seconds) for N = 10, M = 2

	D	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0	2.1
	O RAFTM 424.8	523.4	537.1	275.5	432.2	739.7	832.7 1,645.6 2,349.0
	H RAFTM 0.15	0.13	0.14	0.17	0.17	0.20	0.22	0.23	0.29
	D	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0
	O RAFTM 3,358.1 5,368.3 4,543.9 9,335.6 11,974.2 13,038.4 19,364.5 27,312.9 19,378.6
	H RAFTM 0.32	0.31	0.36	0.33	0.36	0.35	0.41	0.42	0.42
	D	3.1	3.2	3.3	3.4	3.5	3.6	3.7	3.8-4
	O RAFTM 13,155.9 21,493.1 24,228.4 77,477.5 5,472.0 4,868.6 4,096.3	2.5
	H RAFTM 0.49	0.52	0.47	0.52	0.56	0.58	0.59	0.63

Table 5 :

 5 Computation time (seconds) for N = 10, M = 4

	D	1.0	1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0
	O RAFTM 14.9 61.0 74.9 138.2 202.1 256.9 327.3 219.0 1039.3 1054.7 126.8
	H RAFTM 0.19 0.26 0.27 0.30 0.35 0.27 0.33 0.43	0.47	0.50	0.57
	D	2.1	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0	-
	O RAFTM 58.7 123.1 4.9	1.9	1.4	0.6	1.8	1.0	1.8	2.3	-
	H RAFTM 0.59 0.66 0.64 0.70 0.68 0.67 0.68 0.69	0.66	0.78	-

Table 6 :

 6 Computation time (seconds) for N = 10, M = 6

	D	1.0	1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0
	O RAFTM 0.83 58.10 26.95 89.89 81.87 109.82 58.60 62.77 59.77 14.69 2.49
	H RAFTM 0.32 0.27 0.33 0.48 0.54	0.50	0.58 0.68 0.69 0.70 0.67
	D	2.1	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0	-
	O RAFTM 0.74 0.65 0.63 0.66 0.66	0.64	0.64 0.63 0.60 0.60	-
	H RAFTM 0.76 0.74 0.76 0.80 0.84	0.77	0.76 0.76 0.71 0.72	-

√ √ √ √ √

This work is founded by China Scholarship Council (CSC).