# Coping with Silent Errors for Workflows of Moldable Tasks

Qi Gao, Li Han, Sascha Hunold, Yves Robert, Frédéric Vivien

<figure><img src="image_1.png" /></figure>

To cite this version:

Qi Gao, Li Han, Sascha Hunold, Yves Robert, Frédéric Vivien. Coping with Silent Errors for Workflows of Moldable Tasks. RR-9589, INRIA. 2025. hal-05116521

HAL Id: hal-05116521

https://inria.hal.science/hal-05116521v1

Submitted on 17 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Ínria

# Coping with Silent Errors for Workflows of Moldable Tasks

Qi Gao, Li Han, Sascha Hunold, Yves Robert, Frédéric Vivien

## RESEARCH REPORT

Nº 9589

June 2025

Project-Team ROMA
<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /></figure>

# Coping with Silent Errors for Workflows of Moldable Tasks

Qi Gao*, Li Han*, Sascha Hunold†, Yves Robert, Frédéric Vivien

Project-Team ROMA

Research Report n° 9589 — June 2025 — 40 pages

**Abstract:** This work considers checkpointing strategies for workflows composed of moldable tasks that are subject to silent errors. We build upon CPA13, a state-of-the-art scheduling and mapping algorithm for moldable task graphs in an error-free environment, and we extend it in several directions to mitigate the impact of silent errors. We design new allocation and mapping strategies that avoid checkpointing either too few or too many tasks. We run an extensive set of simulations and report important gains over *CkptCrossover*, the baseline extension of CPA13, and two natural competitor strategies, *CkptAll* (checkpoint all tasks) and *CkptNone* (checkpoint no task). Our approach achieves a success rate of 97.5% over all experimental scenarios, while *CkptCrossover* and *CkptAll* have a rate around 80%, and *CkptNone* less than 20%. In addition, we achieve an average gain of 35% over the competitors whenever these are not timed out. All these results demonstrate the robustness and efficiency of our new approach.

**Key-words:** Silent errors, verification, checkpointing, moldable tasks, workflows

<footnote>* East China Normal University, Shanghai, China</footnote>

<footnote>† TU Wien, Wien, Austria</footnote>
# Résilience aux pannes silencieuses des graphes de tâches modelables

**Résumé** : Nous étudions ici les stratégies de prise de points de sauvegarde pour les work-flows composés de tâches modelables qui sont soumis à des pannes silencieuses. Nous partons de CPA13, un algorithme de placement et d'ordonnancement de graphes de tâches modelables à l'état de l'art, et nous l'étendons de différentes manières pour mitiger l'impact des erreurs silencieuses. Nous définissons de nouvelles stratégies d'allocation de ressources et de placement qui évitent de sauvegarder trop ou trop peu de tâches. Nous menons une vaste campagne de simulation et nous montrons que nous obtenons des gains significatifs par rapport à *CkptCrossover*, l'extension de CPA13 qui sert de référence, et à deux stratégies naturelles, *CkptAll* (toutes les tâches sont sauvegardées) et *CkptNone* (aucune tâche n'est sauvegardée).

Notre approche a un taux de succès de 97.5% sur l'ensemble des scénarios considérés, quand *CkptCrossover* et *CkptAll* ont un taux autour de 80%, et *CkptNone* un taux inférieur à 20%. De plus, nous obtenons un gain moyen de 35% par rapport aux autres solutions quand elles réussissent à exécuter l'application dans le temps imparti. Tous ces résultats montrent la robustesse et l'efficacité de notre approche.

**Mots-clés** : Erreurs silencieuses, vérification, points de sauvegarde, tâches modelables, graphes de tâches
# Contents

<table><tr><td>1</td><td>Introduction</td><td>4</td></tr><tr><td>2</td><td>Related Work</td><td>6</td></tr><tr><td>2.1</td><td>Moldable Tasks</td><td>6</td></tr><tr><td>2.1.1</td><td>Speedup Models</td><td>6</td></tr><tr><td>2.1.2</td><td>Algorithms and Communication Costs</td><td>7</td></tr><tr><td>2.2</td><td>Silent Errors</td><td>7</td></tr><tr><td>3</td><td>Framework</td><td>8</td></tr><tr><td>3.1</td><td>Model</td><td>8</td></tr><tr><td>3.1.1</td><td>Tasks and Platform</td><td>8</td></tr><tr><td>3.1.2</td><td>Fault-Tolerance Model</td><td>8</td></tr><tr><td>3.1.3</td><td>Optimization Objective</td><td>9</td></tr><tr><td>3.2</td><td>The CPA13 Algorithm</td><td>9</td></tr><tr><td>4</td><td>Algorithms</td><td>11</td></tr><tr><td>4.1</td><td>Which Tasks Should Be Checkpointed?</td><td>11</td></tr><tr><td>4.2</td><td>Assigning Linear Chains in the Mapping</td><td>12</td></tr><tr><td>4.3</td><td>Dynamic Programming for Linear Chains</td><td>13</td></tr><tr><td>4.4</td><td>Revisiting Processor Assignments for Each Task</td><td>14</td></tr><tr><td>5</td><td>Experiments</td><td>14</td></tr><tr><td>5.1</td><td>Experimental Methodology</td><td>15</td></tr><tr><td>5.1.1</td><td>DAGGEN Workflows</td><td>15</td></tr><tr><td>5.1.2</td><td>WfGen Workflows</td><td>15</td></tr><tr><td>5.1.3</td><td>Run-time Model</td><td>16</td></tr><tr><td>5.1.4</td><td>Platform and Failure Distribution</td><td>16</td></tr><tr><td>5.1.5</td><td>Checkpointing and Verification Cost</td><td>16</td></tr><tr><td>5.1.6</td><td>Competitors</td><td>17</td></tr><tr><td>5.2</td><td>Results</td><td>17</td></tr><tr><td>5.2.1</td><td>DAGGEN Workflows</td><td>17</td></tr><tr><td>5.2.2</td><td>WfGen Workflows</td><td>20</td></tr><tr><td>6</td><td>Conclusion</td><td>21</td></tr><tr><td>A</td><td>Additional Results</td><td>26</td></tr></table>
# 1 Introduction

Efficiently scheduling parallel workflows on high-performance computing (HPC) platforms is crucial for improving the application and system performance. These workflows are represented as Directed Acyclic Graphs (DAGs), where nodes are parallel tasks and edges enforce dependences between tasks. Parallel tasks are classified into three types, according to their degree of flexibility [10]: (i) rigid tasks, requiring a predefined fixed number of processors for execution; (ii) moldable tasks, for which the number of processors is decidable before the execution starts, but stays unchanged afterwards; and (iii) malleable tasks, where the number of processors may vary during execution. This work focuses on moldable tasks, because they can easily adapt to the number of available resources, contrarily to rigid tasks, while being easy to program and implement, contrarily to malleable tasks. Many computational kernels in scientific libraries, e.g., SLATE [13], are provided as moldable tasks that can be deployed on several 2D-grid sizes. Job schedulers like LSF [18] and SLURM [32] allow the user to specify a range of resources on which each task can be scheduled. Altogether, moldable tasks represent an excellent trade-off for deploying applications in a flexible but effortless way. This explains that moldable tasks have received considerable attention in the scheduling literature.

A moldable task $T$ is equipped with a speedup profile: there is a range of possible processor counts, and an execution time $W_p$ for each processor number in that count. The values of $W_p$ may obey several classical speedup-models (roofline, Amdahl, etc.) which we review in Section 2.1. This work applies to arbitrary speedup profiles.

This work aims at mitigating the impact of silent or transient errors on workflows of moldable tasks. Coping with these errors is a major challenge on today's HPC platforms [22]. Taking verified checkpoints is the best known method in HPC to enforce a correct execution despite several silent or transient errors striking during execution [16]. Checkpoints must be verified before being written to stable storage, so that only non-corrupted checkpoints are taken. The verification is conducted by applying some application-specific detection mechanism. Fortunately, many silent errors can be accurately detected by verifying the integrity of data using dedicated, lightweight detectors (e.g., [30, 14, 5]). We review application-specific detectors in Section 2.2.

The optimization objective is to minimize the expected makespan, which is defined as the expectation of the total time needed to execute the workflow. Indeed, because silent errors strike the tasks randomly and according to some probability distribution laws (see Section 3.1 for details), the total execution time of the workflow is no longer deterministic but becomes a random variable, and the objective is to minimize its average value. Placing checkpoints at the end of some judiciously chosen tasks is key to achieving this objective. While scheduling workflows of sequential tasks on error-prone platforms has been the subject of several studies (see Section 2.1.2), this work is the first to target the execution of workflows of moldable tasks on error-prone platforms.

On error-free platforms, several algorithms have been proposed mapping and scheduling workflows of moldable tasks. Finding the right number of processor for each task is a challenge that is specific to moldable task graphs. On the one hand, one would like to give as many processors as possible to each task, so as to decrease execution time. On the other hand, several tasks are likely to execute in parallel, and we should fairly distribute the computing resources across them. This work builds upon CPA13 [17], a state-of-the-art scheduling and mapping algorithm for moldable task graphs that starts with a single processor per task and carefully increases this number task by task, depending upon the criticality of the task and the width of its graph level. See Section 3.2 for a detailed description of the CPA13 algorithm.

To extend CPA13 to account for silent errors, a first approach is to checkpoint every task. This is likely to be too costly, in particular for scenarios with few errors and high checkpoint
costs. In fact, it is mandatory to checkpoint some tasks, but not all. In a nutshell, assume there
is a dependence from task *T* to task *T'*. If the set *alloc(*T*)* (processors assigned to *T*) is not
the same as the set *alloc(*T'*')* (processors assigned to *T''), then we need to checkpoint *T*. This
is because if *T'* is struck by an error and needs to be re-executed, then (i) nothing guarantees
when this re-execution can take place, because processors in *alloc(*T*)* may no longer be available
together before a long time; and (ii) the input files of *T* needed for the re-execution may well
have been erased from memory when needed for the re-execution. This scenario illustrates a
crossover dependence, which we define as a dependence from a source task to a sink task whose
assigned processor sets are not identical. With workflows of moldable tasks, it is likely that many
crossover dependences will arise from the mapping algorithm, unless this mapping is specifically
designed to avoid them. Altogether, a second approach is thus to use the CPA13 mapping and
scheduling algorithm, and to checkpoint the source task of every crossover dependence resulting
from the mapping. This approach will represent the baseline to assess further (more refined)
extensions to CPA13.

We improve the baseline approach along several steps:

1. Update the mapping: give priority to the creation of *isolated task chains* in the mapping phase, i.e., iteratively build chains of tasks that can be assigned to the same processor set without creating any crossover-dependence; then checkpoint only the last task of the chain.

2. Update the schedule: re-compute the number of processors assigned to each checkpointed task and decrease this number whenever accounting for errors actually decreases execution time in expectation. Indeed, the more processors, the higher the error rate, and one should trade-off between speed and reliability.

3. Within isolated task chains, it may well be the case that some intermediate tasks should be checkpointed in addition to the last task of the chain. We use an optimal dynamic programming algorithm to decide whether and where to place more checkpoints inside the chain.

Step 1) involves some risk because isolated chains need to be executed with the same processor set for each task within the chain, we may lose some parallelism there, so we have to weight this decision against the fact that isolated chains will save checkpoints. When checkpoint costs are high, Step 1) is likely to be beneficial, but it may well be not always the case. On the contrary, Steps 2) and 3) are always beneficial, and will lead to significant gains when the error rate is high.

Finally, we point out that, to the best of our knowledge, no published work for the error-free
execution of workflows of moldable tasks has even taken inter-task communications into account.
In general, when there is a dependence from a task *T* to a successor task *T'*, some data must
be sent from *T* to *T'*. However, the cost of the communication from *T* to *T'* is hard to model,
because it depends on many factors, the most important being how much the subset of processors
assigned to *T* differs from that assigned to *T'*; these subsets could be identical, or disjoint, or
anything in between (see Section 2.1.2 for more details). We also ignore communication costs in
this work on error-prone platforms, but we do account for checkpoint costs, which are expected
to be much higher than communication costs, because the I/O bandwidth of the platform is
expected to be an order of magnitude lower than that of the inter-processor network.

The main contributions of this work are the following:

* The design of the first mapping and scheduling algorithms for workflows of moldable tasks on error-prone platforms;

* A baseline extension of the CPA13 strategy where only crossover-dependences are checkpointed;

* A new processor allocation, task mapping and checkpointing heuristic based on several optimization strategies;
* An extensive simulation campaign, with comparison of several CPA13-inspired variants with the baseline and two naive competitor strategies, *CkptAll* (checkpoint all tasks) and *CkptNone* (checkpoint no task).

The paper is organized as follows. Section 2 surveys related work. Section 3 details the framework and provides background on the CPA13 algorithm. We detail our scheduling and checkpointing algorithms in Section 4. We give experimental results in Section 5. Finally, we provide concluding remarks and directions for future work in Section 6.

# 2 Related Work

First, we provide background on moldable tasks in Section 2.1, where we review standard speedup profiles and explain why inter-task communications have never been accounted for. Second, we survey silent errors and their mitigation techniques in Section 2.2.

## 2.1 Moldable Tasks

### 2.1.1 Speedup Models

The number of processors allocated to a moldable task can be determined by the scheduling algorithm at launch time, but once the task has started executing, its processor allocation cannot be changed. The execution time $W_{p_j}(T_j)$ of a task $T_j$ is a function of the number $p_j$ of processors allocated to it, chosen between 1 and $P$, the total number of processors. A very general model obeys the equation:

$$W_{p_j}(T_j) = \frac{w_j}{\min(p_j, \bar{p}_j)} + d_j + c_j(p_j - 1) \quad (1)$$

where $w_j$ denotes the total parallelizable work of the task (in time units), $\bar{p}_j$ denotes its maximum degree of parallelism, $d_j$ denotes its sequential work, and $c_j$ denotes the communication overhead when more than one processor is used. This general model includes several classical speedup profiles:

* *Roofline Model [11] (with $d_j = 0$ and $c_j = 0$):*

$$W_{p_j}(T_j) = \frac{w_j}{\min(p_j, \bar{p}_j)}. \quad (2)$$

This model assumes that the task has a linear speed-up until a maximum degree of parallelism $\bar{p}_j \le P$.

* *Communication Model [15] (with $\bar{p}_j = P$ and $d_j = 0$):*

$$W_{p_j}(T_j) = \frac{w_j}{p_j} + c_j(p_j - 1). \quad (3)$$

This model assumes that the work of the task can be perfectly parallelized, but there is a communication overhead when more than one processor is allocated to the task, and that overhead increases linearly with the number of allocated processors.

* *Amdahl's Model [1] (with $\bar{p}_j = P$ and $c_j = 0$):*

$$W_{p_j}(T_j) = \frac{w_j}{p_j} + d_j. \quad (4)$$

This model assumes that the task has a perfectly parallelizable fraction with work $w_j$ and an inherently sequential fraction with work $d_j$.
One can assume w.l.o.g. that $W_p$ is not increasing with $p$, i.e., more parallelism is never harmful to execution time. Whenever it is not true, simply keep some processors idle! For instance, consider a matrix product that executes faster on a 3 × 4 2D-grid than on a ring of 13 processors; the best strategy with 13 processors is to keep one processor idle and to enroll only 12; hence, enforcing $W_{13} = W_{12}$. Regardless, recall that this work applies to arbitrary speedup profiles.

In addition to the execution time function of the task $T_j$, one further defines the *area* of the task as a function of the processor allocation as follows: $A_j(T_j) = p_j \cdot W_{p_j}(T_j)$. Intuitively, the area represents the total amount of processor resource utilized over the entire period of task execution. The area is important because the probability that a silent error strikes a task depends upon its area (see below).

## 2.1.2 Algorithms and Communication Costs

Several algorithms for the error-free execution of workflows of moldable tasks have been proposed in the literature, including [29, 11, 4, 19, 6, 17]. None of them included communication costs in their model. Consider a dependence from a task $T$ to a successor task $T'$. The cost of the communication from $T$ to $T'$ is hard to model, because it depends on many factors:

* $T$ executes with a set $alloc(T)$ of $p$ processors, $T'$ executes with a set $alloc(T')$ of $q$ processors, and these processor sets can either overlap or not, with scenarios ranging from one set being included in the other (and equal if $p = q$) up to being completely distinct. The actual processor sets assigned to both tasks, not just the number, will have a dramatic impact on the communication cost.

* The data that must be communicated from $T$ to $T'$ may obey a different distribution for each task. For instance in numerical linear algebra, think of re-distributing a matrix whose tiles are distributed cyclically in both dimensions for $T$, but with a full block distribution for $T'$. The cost of the redistribution will heavily depend upon the format required by each task. Even if $T$ and $T'$ are assigned the same set of processors, inter-processor communications may well have to take place in between the execution of $T$ and $T'$.

This explains that communication costs, which include redistribution costs when the sets of assigned processors overlap, are never accounted for in the literature. In this work, we will also neglect inter-processor communication costs. However, I/O transfers to stable storage (for checkpointing and recovery) cannot be neglected, because their cost is an order of magnitude higher than inter-network exchanges.

## 2.2 Silent Errors

While fail-stop errors lead to fatal interruptions (such as a crash) and cause the loss of the entire memory of the processor, silent errors, a.k.a. silent data corruptions (SDCs), only impact a given task and lead to incorrect results. Silent errors may be caused, for instance, by arithmetic errors in the Arithmetic and Logic Unit (ALU), soft errors in the L1 cache which is usually not well protected, or in the L2 cache which might be protected by one parity bit, or bit flips in the dynamic random-access memory (DRAM) due to cosmic radiation, overheat and other sources [23, 24, 33, 34]. There are several hardware mechanisms to detect and correct silent errors, such as parity bits, error correcting codes (ECCs), and Chip-kill technology. Although many silent errors caused by one or multiple bits that spontaneously flip to the opposite state are caught by these hardware mechanisms, in reality, some bit flips still manage to pass undetected [27, 3]. In addition, the constant need to reduce component size and voltage increases the likelihood of silent errors, for instance incorrect numerical operations produced by an under-voltage ALU [9, 20].
Silent errors cause a job to produce erroneous results after an execution attempt. Fortunately, such errors can often be detected using lightweight detectors whose overhead is typically low (e.g., [30, 14, 5]). If an error is detected, the task needs to be re-executed followed by another error detection. This process repeats until the task completes successfully.

As a side note, we point out that in real-time systems, a common approach to accommodate for silent errors is to use replication and to schedule several replicas of each task [2, 25, 31]. The larger the number of replicas, the higher the reliability (e.g., achieving a probability 0.99 of a correct execution). However, within an HPC framework, replication is considered too costly; detectors and checkpoints are used instead.

# 3 Framework

This section provides an overview of the execution models, fault-tolerance model and optimization objective, along with the state-of-the-art scheduling algorithm for moldable tasks that we build upon. Key notations are summarized in Table 1.

## 3.1 Model

### 3.1.1 Tasks and Platform

The execution model of a task workflow is represented as a Directed Acyclic Graph (DAG) given by $G = (V, E)$, where $V$ is the set of nodes that represents tasks and $E$ is a set of edges that represents dependences between tasks. Each task $T_i \in V$ is moldable, meaning it can run in parallel on a set of $p$ processors where $p \in \{1, \dots, P\}$. The execution time of task $T_i$ with $p$ processors in an error-free environment is given by $W_p(T_i)$. We do not make any assumption about task speed-up profiles beyond the fact that execution times are non-increasing with the number of allocated processors. The number of processors allocated to tasks is decided before execution and cannot be changed afterwards. The immediate predecessors and successors of task $T_i$ are represented by $pred(T_i)$ and $succ(T_i)$, respectively. A dependence $(T_i, T_j) \in E$ means that the execution of task $T_j$ can only start after $T_i$ is completed and all input files needed are available in local memory. As explained in Section 1, inter-processor communication costs are ignored.

We consider scheduling workflows on a homogeneous platform consisting of $P$ identical processors. The platform is error-prone and susceptible to be struck by silent errors. Unlike fail-stop errors, when a silent error occurs, the processor does not halt execution immediately. Identifying silent errors requires verification mechanisms. To prevent the need to re-execute all tasks from scratch after an error, only verified checkpoints are taken. Once an error is detected through verification, the system rolls back to the latest checkpoint and restarts execution from there. Intermediate files are kept in local memory of the processor executing the task until either they are read by successors or are checkpointed into stable storage.

### 3.1.2 Fault-Tolerance Model

We assume that errors are i.i.d. (independent and identically distributed) across processors and that the error inter-arrival times at each processor is Exponentially distributed with Mean Time Between Errors (MTBE) $\mu = 1/\lambda$. Let $\lambda \ll 1$ be the Exponential error rate of the processor, then the error rate with $p$ processors is $\lambda' = p\lambda$. Consider a moldable task $T$ executing on $p$ processors, with execution time $W_p(T)$, and whose inputs are all checkpointed, i.e., stored on stable storage. The total execution time of $T$ is a random variable, because several execution
attempts may be needed before the task succeeds. If a verified checkpoint is placed after the execution of task T, with probability $e^{-p\lambda W_p(T)}$, no error occurs, and the total execution is then equal to $W_p(T) + V + C$, where V and C are verification cost and checkpoint cost respectively. With probability $1 - e^{-p\lambda W_p(T)}$, an error occurs, and its detection is delayed until the verification is carried out: thus the loss caused by the error is the entire execution time of the task plus the verification cost $W_p(T) + V$. After this error, there is a recovery time R, which is the time needed to restore files needed from stable storage, then we restart the execution of T. We use a general model where an unbounded number of errors can occur during task execution. A checkpoint will be taken until it has been verified that no error occurred during the task execution. The expected time to execute task T on p processors is given by:

$$E(T, p) = e^{-p\lambda W_p(T)}(W_p(T) + V + C) + (1 - e^{-p\lambda W_p(T)})(W_p(T) + V + R + E(T, p)) \quad (5)$$

which simplifies to:

$$E(T, p) = e^{p\lambda W_p(T)}(W_p(T) + V + R) + C - R. \quad (6)$$

Here, we assume that errors only strike during computations, and not during checkpoint, recovery, or verification. Also, Equations (5) and (6) use costs for checkpoints and recoveries that are independent of the number of processors involved. This is because we assume that the bottleneck for transfer to and back from stable storage is the limited capacity of the I/O system, so the time for these operations are basically the volume of data divided by the I/O bandwidth. Finally, in the experiments reported in Section 5, we assume that the cost of the verification is a fraction of the checkpoint cost, but our scheduling strategies can accommodate any verification cost.

### 3.1.3 Optimization Objective

Given a DAG with moldable tasks and a set of processors on which silent errors strike with Exponentially distributed inter-arrival times, the objective is to schedule the task executions and potential checkpoints such that the expected completion time (or makespan) is minimized. The schedule of the tasks consists of an assignment to processors and of a task ordering. Each processor executes tasks as soon as possible and resumes their processing when a silent error is detected by verification. Finally, the schedule of the checkpoints is the list of files that must be checkpointed after each task execution.

<table><caption>Table 1: Overview of notations</caption><tr><td><i>P</i></td><td>number of processors</td></tr><tr><td><i>succ</i>(<i>T</i>)</td><td>successors of task <i>T</i></td></tr><tr><td><i>pred</i>(<i>T</i>)</td><td>predecessors of task <i>T</i></td></tr><tr><td><i>W</i><sub>p</sub>(<i>T</i>)</td><td>execution time of <i>T</i> with <i>p</i> processors</td></tr><tr><td><i>alloc</i>(<i>T</i>)</td><td>processors allocated to task <i>T</i></td></tr></table>

## 3.2 The CPA13 Algorithm

Now, we briefly summarize the CPA13 algorithm, which serves as the baseline for our improved, fault-tolerant variant. The CPA13 algorithm is an extension of the CPA algorithm [26]. The CPA algorithm operates in two phases: first, it determines a processor allocation for each task;
<table><caption>**Algorithm 1: CPA13 Allocation Procedure**</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td><b>foreach</b> task $v_j \in V$ <b>do</b></td></tr><tr><td>2</td><td>&nbsp;&nbsp;&nbsp;&nbsp;assign $\alpha_j \leftarrow 1$ processor</td></tr><tr><td>3</td><td>&nbsp;&nbsp;&nbsp;&nbsp;mark $v_j$ as UNVISITED</td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;construct list $A_j$ of increasing allocations with improving efficiency</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;extract from $A_j$ the list <b>allot</b><sub>j</sub> of allocations with sufficient relative speedup</td></tr><tr><td>6</td><td><b>while</b> $L > W/P$ <b>do</b></td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;identify tasks $V_{CP}$ on the current critical path</td></tr><tr><td>8</td><td>&nbsp;&nbsp;&nbsp;&nbsp;compute used processors $\tilde{m}_d$ for each precedence level $d$ and VISITED tasks</td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;($v_b, \tilde{\alpha}_b, b_b$) $\leftarrow$ (<b>nil</b>, $m, 0.0$)</td><td><b>// initialize</b></td></tr><tr><td>10</td><td><b>foreach</b> $v_j \in V_{CP}$ <b>do</b></td></tr><tr><td>11</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;get next bigger allocation from <b>allot</b><sub>j</sub></td></tr><tr><td>12</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> enough processors are available for bigger allocation <b>and</b> benefit is currently the best<br/>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>then</b></td></tr><tr><td>13</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;remember task $v_j$ as $v_b$</td><td><b>// best task</b></td></tr><tr><td>14</td><td><b>if</b> $v_b$ was found <b>then</b></td></tr><tr><td>15</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;increase allocation of $v_b$</td></tr><tr><td>16</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mark $v_b$ as VISITED</td></tr><tr><td>17</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recompute $L$ and $W$</td></tr><tr><td>18</td><td><b>else</b></td></tr><tr><td>19</td><td>&nbsp;&nbsp;&nbsp;&nbsp;break</td></tr></tbody></table>

second, it maps the tasks with their assigned allocations onto the processors. Initially, CPA assigns one processor per task. It then repeatedly identifies the critical path and allocates an additional processor to the task on that path whose speedup most reduces the overall critical path length. This process continues until the critical path length $L$ falls below the average work per processor $\frac{W}{P}$.

The CPA13 algorithm [17] improves upon CPA in two major ways. First, its allocation procedure considers only allocations that yield a predefined minimum speedup, thereby avoiding the use of processors for negligible benefit. Second, in the mapping phase, CPA13 attempts to schedule a task on fewer processors if doing so does not increase its projected finish time. This strategy is similar to backfilling approaches employed in common batch schedulers such as SLURM [21].

In CPA13's allocation procedure (Algorithm 1), all promising allocations are first identified for each task. An allocation is considered promising if it reduces the runtime and yields a significant speedup. Processors are then iteratively added to tasks until the length of the critical path is no longer greater than the average work per processor across all tasks. To determine which task should receive additional processors, all tasks on the current critical path are examined, and the one whose reallocation provides the greatest relative runtime improvement is selected. If such a task exists, its allocation is increased, and both the critical path length and total work are recomputed.

In the mapping phase, shown in Algorithm 2, the task with the highest bottom level is selected, as it is critical for enabling the execution of many dependent tasks. The earliest time is determined at which the number of processors allocated by Algorithm 1 becomes available. Using this pre-computed allocation, the predicted finish time of the task is calculated. A smaller allocation and an earlier time slot are then searched for that would result in a shorter finish time. If such an allocation exists, the task's processor count is reduced accordingly, effectively
<table><caption>**Algorithm 2: CPA13 Mapping Procedure**</caption><tr><td>1:</td><td><b>while</b> not all tasks are scheduled do</td></tr><tr><td>2:</td><td>Select a ready task $v_j$ with the maximum bottom level</td></tr><tr><td>3:</td><td>Let $\tau$ be the earliest time when $\alpha_j$ processors are available</td></tr><tr><td>4:</td><td>Let $C \leftarrow \tau + p_j(\alpha_j)$ be the estimated completion time of $v_j$</td></tr><tr><td>5:</td><td>Perform a binary search on $allot_j$ to find the smallest processor count $a_j \le \alpha_j$ such that there exists $\tau_i \le \tau$ with $\tau_i + p_j(a_j) \le C$</td></tr><tr><td>6:</td><td>Schedule task $v_j$ on the first $a_j$ processors that are available at time $\tau_i$</td></tr></table>

“backfilling” the task. Further details of CPA13 are provided in the original publication [17].

# 4 Algorithms

This section details our scheduling and checkpointing strategies built upon CPA13 to cope with silent errors.

## 4.1 Which Tasks Should Be Checkpointed?

<figure><img src="image_5.png" /><figcaption>Figure 1: Illustrative example of a workflow and its corresponding schedule. There are two verified checkpoints (V followed by C), which are represented in color, while tasks are represented in white.</figcaption></figure>

Assuming the mapping and scheduling of tasks are determined by CPA13, the remaining challenge is to decide which tasks to checkpoint. In an error-free scenario, the optimal strategy is to checkpoint nothing onto stable storage, referred to as *CkptNone*. However, as the error rate increases, excessive time may be spent on re-executing tasks after errors, potentially making it impossible to complete the computation for large workflows and/or platforms. At the other end of the spectrum would be a checkpoint everything strategy, *CkptAll*, that minimizes re-execution costs but incurs the highest checkpoint redundancy overhead. Therefore, striking a better trade-off between these two extremes is crucial to achieving efficiency.

When attempting to insert checkpoints after some tasks but not all, the minimum strategy is to checkpoint all files generated by tasks that have non-identical processor sets with their predecessors, i.e., exactly the files corresponding to *crossover* dependences (see definition in Section 1). We use an example to illustrate the necessity of inserting checkpoints to cope with
each crossover dependence. Consider the workflow shown in Figure 1a, comprising 9 moldable
tasks, $T_i$, $1 \le i \le 9$, scheduled on 3 identical processors, $P_j$, $1 \le j \le 3$. The allocation
and scheduling obtained through the CPA13 algorithm is shown in Figure 1b. Assume that
two verified checkpoints are taken after tasks $T_7$ and $T_9$. Recall that the intermediate files are
retained in memory until they are either read by successor tasks or checkpointed to stable storage
(Section 3.1). Thus, the files corresponding to the dependences $T_4 \to T_5$ and $T_2 \to T_3$ are removed
from the local memories of processors $P_2$ and $P_3$ once task $T_5$ and $T_3$ start execution, respectively.
The verified checkpoint after task $T_7$ will only store files corresponding to dependence $T_7 \to T_8$
to stable storage, i.e., files generated and which have not already been read.

Assume an error was detected by the verification after task $T_7$, thus we need to re-execute
all predecessor tasks of $T_7$, including $T_7$ itself, that were executed after the latest checkpoint,
namely $\{T_1, T_6, T_7\}$. This is because the error detected may strike at any unverified task on
the path $T_1 \to T_6 \to T_7$. To start re-executing $T_1$, we need to wait for processor $P_1$ to be
available, since it is currently executing $T_3$. Hence, the crossover dependence triggers rollbacks
on multiple processors and cannot start immediately after an error is detected. Moreover, if the
error occurred during the execution of $T_1$, tasks $T_2$ and $T_4$ will no longer be correct, but this
can be detected only by the verification after task $T_9$. Then task $T_8$ needs to be re-executed
which needs output data of $\{T_3, T_5, T_7\}$. These files are neither checkpointed nor available in
local memory. As a result, the whole workflow will re-execute from scratch. This example shows
the importance of checkpointing all crossover dependences: this helps containing errors within
individual task processor sets, and preventing them from propagating across the whole platform
and triggering massive rollbacks. For each task $T$, if there is a dependence from $T$ to $T'$ and
$alloc(T) \neq alloc(T')$, a verified checkpoint will always be taken after task $T$. This involves storing
files needed for subsequent tasks to stable storage. Combining CPA13 with checkpointing for
every crossover dependence resulting from the mapping leads to a natural baseline *CkptCrossover*.
We now describe how this baseline is improved through three steps, detailed in Section 4.2 to
Section 4.4.

## 4.2 Assigning Linear Chains in the Mapping

Since CPA13 algorithm was not designed specifically to cope with faults, the scheduling obtained
always contains a significant number of crossover dependences. For the example workflow and
scheduling given by CPA13 shown in Figure 1b, all tasks except $T_8$ will be checkpointed with
strategy *CkptCrossover*. Note that we always take verified checkpoints after the exit tasks
to ensure that the whole workflow is executed correctly. Whenever an error is detected after
task $T_7$, using *CkptCrossover*, one could start re-execution right after reading the input files
corresponding to dependence $T_6 \to T_7$ from stable storage. Although this strategy isolates
processors, avoids massive rollbacks, and ensures immediate re-execution, it may generate large
overheads when checkpointing costs are high. We first try to update the mapping aiming at
reducing the number of crossover dependences, which is achieved by assigning linear chains to
the same set of processors.

A chain is defined as a sequence of tasks where the head task, represented as $T$, has a single
successor, $T'$, and $T$ is the only predecessor of $T'$, then $(T, T')$ is the start of a chain. We then
iteratively decide whether the chain can extend with $T''$ with the same condition. For the example
in Figure 1a, $\{T_2, T_3\}$, $\{T_4, T_5\}$, $\{T_6, T_7\}$, and $\{T_8, T_9\}$ are chains. We then replace a chain of
tasks with a single super-task and apply the CPA13 algorithm. Starting with one processor per
task or super-task, and looking at the current critical path as shown in Algorithm 1 to decide
the number of processors for each task/super-task. We assume that the level of a super-task
corresponds to the level of its head (i.e., the first task). This leads to a schedule where all
tasks within a chain are assigned the same set of processors, ensuring that there is no crossover dependence within the chain, except maybe for the sink task (which is always checkpointed). The number of processors assigned to a super-task obeys the rule of CPA13, except that the speed-up profiles of that super task must be recomputed on the fly.

Finally, since the set of processors is assigned to a super-task, it remains the same for each task that belongs to the linear chain making up that super-task. As a consequence, there is a potential loss of parallelism, since two different tasks in the chain may well have very different speed-up profiles. This is the price to pay when building super-tasks, whose main advantage is to avoid taking too many checkpoints by decreasing the number of crossover dependences.

## 4.3 Dynamic Programming for Linear Chains

As mentioned before, introducing super-tasks reduces the number of crossover dependences; hence, the number of mandatory checkpoints. Consider a super-tasks that represents a linear chain

$$T_1 \rightarrow T_2 \rightarrow \dots \rightarrow T_n.$$

By construction, only the last task $T_n$ of the linear chain is equipped with a checkpoint. However, if the linear chain is long and/or made up with lengthy tasks, it may well be useful to insert a few intermediate checkpoints within the chain. In other words, we would split the super-tasks into several smaller super-tasks in order to minimize re-execution cost.

To determine the optimal location of checkpoints within the chain, we provide a dynamic programming algorithm. According to Equation (6), the expected execution time of the whole chain with $p$ processors and a single checkpoint after $T_n$ is given by:

$$E(\{T_1, \dots, T_n\}, p) = e^{p\lambda \sum_{i=1}^{n} W_p(T_i)} \left( \sum_{i=1}^{n} W_p(T_i) + V_1^n + R_1^n \right) + C_1^n - R_1^n, \quad (7)$$

where $V_1^n$ and $C_1^n$ are the verification and checkpointing cost of all the files generated by $T_1, \dots, T_n$ and which have not been read yet, and $R_1^n$ is the recovery time to read all the input files needed to restart execution of these tasks.

Here $p$ is the number of processors assigned to the super-task by CPA13. We generalize Equation (6) and compute the expected time to execute tasks $T_i$ to $T_j$, where $1 \le i \le j \le n$, $T_i$ is preceded by a checkpoint, and $T_j$ is followed by a checkpoint:

$$E(i, j, p) = e^{p\lambda \sum_{k=i}^{j} W_p(T_k)} \left( \sum_{k=i}^{j} W_p(T_k) + V_i^j + R_i^j \right) + C_i^j - R_i^j, \quad (8)$$

where $V_i^j$ and $C_i^j$ are the verification and checkpointing cost of all the files generated by $T_i, \dots, T_j$ and which have not been read yet, and $R_i^j$ is the recovery time to read all the input files needed to restart execution of these tasks.

We let $E^{(opt)}(1, i, p)$ be the minimum expected time to execute tasks $T_1, \dots, T_i$ with a checkpoint after $T_i$. If we place no additional checkpoint, this time is $E(1, i, p)$ by definition. If we add at least one intermediate checkpoint, consider the last checkpoint that we add, say after $T_j$, where $j < i$. Then the expected time becomes $E^{(opt)}(1, j, p) + E(j + 1, i, p)$ where $E^{(opt)}(1, j, p)$
is called recursively as the best way to execute the shorter chain from $T_1$ to $T_j$. Altogether, we
derive the dynamic programming formulation

$$E^{(opt)}(1, i, p) = \min \left( E(1, i, p), \min_{1 \le j \le i-1} \left( E^{(opt)}(1, j, p) + E(j+1, i, p) \right) \right).$$

We are interested in computing $E^{(opt)}(1, n, p)$; we initialize the recurrence with $E^{(opt)}(1, 1, p) = E(1, 1, p)$. Because $p$ is fixed here, the cost of computing the optimal solution via the dynamic programming algorithm is $O(n^2)$.

## 4.4 Revisiting Processor Assignments for Each Task

On an error-free platform, the execution time $W_p(T)$ of each task $T$ is not increasing with the number of processors $p$. However, the error probability for a task $T$ executed on $p$ processors is $1 - e^{-p\lambda W_p(T)}$. As mentioned in Section 1, in general there is no super-linear speedup ratio, i.e., the work area $p \times W_p(T)$ is not decreasing with $p$, thus increasing the number of processors assigned may lead to higher error probability and longer execution time because of re-execution. Therefore, we should revisit processor assignments for each task, accounting for potential errors, and decrease the number of allocated processors whenever this reduces the expected execution time (which is computed according to Equation (6)). This optimization achieves a trade-off between speed and reliability and will be mostly beneficial when error rates are high.

After scheduling and checkpointing the workflow, consider a sequence of tasks $T_1, \dots, T_n$ ($n \ge 1$) scheduled on the same set of processors with a unique verified checkpoint at the end. The execution of $T_1, \dots, T_n$ is isolated, meaning that any error detected by the verification will only result in rollback of $T_1, \dots, T_n$ without propagating to other tasks or processors. The expected execution time with $p$ processors is given by Equation (7). This formula requires, by construction, that $T_1, \dots, T_n$ is a sub-chain or $n = 1$, which means no intermediate task needs input file from processors other than the $p$ processors used for the sub-chain. However, we heuristically use the formula even when this condition is not satisfied. In this case, we allow tasks to be the target of crossover dependences, and behave as if these crossover dependences were not existing: we discard any potential waiting time that may be due to these crossover dependences (because we have no means to estimate them).

We now revisit the processor assignment to reduce the expected execution time. The pseudo-code is given in Algorithm 3. For each isolated task sequence, we first try to find a better number of processors $p'$ assigned, where $1 \le p' \le p$ (Lines 1–3). If $p' \ne p$, we reduce the number of processors executing $T_1, \dots, T_n$ to $p'$ and keep the $p'$ processors that can start the execution the earliest (Lines 4–5); otherwise it remains unchanged. The maximum number of task sequences is $|V|$, and the time complexity to find the best number of processors for each sequence is $O(P)$. Therefore, the overall complexity is $O(|V| \times P)$.

# 5 Experiments

In this section, we present experimental results that quantify the effectiveness of our proposed scheduling and checkpointing algorithm. Section 5.1 details the parameters and benchmarks used during the experimental campaign. Then Section 5.2 presents the results.
<caption>**Algorithm 3:** Revisiting Processor Assignment</caption>

1 Set ← {{T<sub>1</sub>, ..., T<sub>n<sub>1</sub></sub>}, ..., {T<sub>1</sub>, ..., T<sub>n<sub>m</sub></sub>}}
2 **for** c **in** Set **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;p' ← arg min<sub>1≤q≤p</sub> E(c, q) ; // p is the initial number of processors
&nbsp;&nbsp;&nbsp;&nbsp;assigned to c
4 &nbsp;&nbsp;&nbsp;&nbsp;if p' ≠ p **then**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c is mapped to the first available p' processors among the total of p processors

**5.1 Experimental Methodology**

We consider two types of workflows in the simulation: (i) representative scientific workflows from the real-world applications generated by WfGen [8]; and (ii) synthetic (randomly generated) DAGs from DAGGEN [28].

**5.1.1 DAGGEN Workflows**

Four parameters influence the generation process of this benchmark, namely *width*, *regularity*, *density*, and *jump*. The *width* controls the degree of parallelism of the generated DAG, the *regularity* defines the uniformity of the number of tasks at each DAG level, the *density* specifies the number of edges, and the parameter *jump* determines if and how many DAG levels an edge may span. To better evaluate the effectiveness of our proposed strategy under chain-like structures, we implemented a new parameter based on the original generator, named *chain*, which influences the proportion of tasks within the DAG that belongs to a chain structure. Specifically, to generate a DAG with *N* nodes, we first define the number *v* of tasks belonging to chains as *v* = *chain* × *N*. Then we iteratively generate a series of random numbers *m*<sub>i</sub> within the range [1, max(10, 0.1 × (N − *v*))], until their cumulative sum reaches or exceeds number *v*. If the sum exceeds *v*, we adjust the last random number to ensure the total sum equals to *v*. Assume that the total number *v* is divided into *p* parts, *m*<sub>1</sub>, ..., *m*<sub>*p*</sub>. Finally, we use DAGGEN to generate an initial DAG with *r* = *N* − *v* + *p* nodes, and replace the top *p* largest nodes in the original DAG with a chain containing *m*<sub>i</sub> nodes. This ensures that the final generated DAG contains exactly *N* nodes.

We generate random DAGs with 50, 500, and 5000 nodes. For the purpose of better comparability, we use the same set of parameters that had been used for the experiments in [17]: *width* ∈ {0.2, 0.5, 0.8}, *regularity* ∈ {0.2, 0.8}, *density* = 0.2, *jump* ∈ {0, 1, 2, 4}, and *chain* ∈ {0.01, 0.1, 0.2, 0.5}. Therefore, for each size of DAG, 96 instances are considered. For each task, the number of operations is given in Flops. To get the sequential run-time of each task, two platform models are considered: the distributed Grid'5000 cluster (Grelon nodes) with *P* = 120 processors achieving 3.1 GFLOPS (measured via HP-Linpack benchmark), and the shared-memory system at Vienna University of Technology equipped with *P* = 48 processors operating at 6.7 GFLOPS (validated using the GotoBLAS2 library).

**5.1.2 WfGen Workflows**

WfGen generates realistic synthetic workflow instances with arbitrary numbers of tasks using
workflow recipes provided by WfChef[7], an automated tool that extracts structural patterns
from real workflow applications. We evaluated all the nine workflows provided by WfGen, namely
Epigenomics, Montage, Genome, Soykb, Cycle, Srasearch, Seismology, Bwa, and Blast. In this
section, we report results of Epigenomics and Soykb (introduced below in detail), which incorporate the chain structure of particular interest to us. Additional results can be found in appendix.

* Epigenomics: The epigenomics workflow is a data processing pipeline designed to execute a variety of genomic sequencing operations. Structurally, Epigenomics starts with a root task that forks into multiple parallel chains. The exit tasks of these chains subsequently join to a new chain.

* Soykb: The Soykb workflow is a genomics pipeline designed for resequencing soybean germplasm lines. Structurally, Soykb starts with multiple parallel chains, followed by fork and join subgraphs.

We generate WfGen workflows with target task counts set to 500 and 5000. These values represent the intended total task numbers; the actual number of tasks in each generated workflow may slightly vary depending on its specific structure. For each task $T_i$ in the workflow, the generator assigns: (1) a computational weight (in seconds); and (2) the sizes of output files required by its successors (in bytes).

### 5.1.3 Run-time Model

To obtain the parallel run-time of a moldable task, we apply Amdahl's law, which simply states that the speedup of a parallel application is limited by the fraction of sequential code. Let $W_1(T_i)$ denote the time required to execute task $T_i$ sequentially, and $\alpha$, $0 \le \alpha \le 1$ represent the fraction of the task that is non-parallelizable. Consequently, the runtime of the task on $p_i$ processors is given by $W_{p_i}(T_i) = \alpha W_1(T_i) + (1-\alpha) \frac{W_1(T_i)}{p_i}$. We randomly pick the parameter $\alpha$ from a uniform distribution between 0 and 0.25.

### 5.1.4 Platform and Failure Distribution

In the experiments, we consider different exponential processor failure rates. To consistently compare the results across different DAGs (with varying numbers of tasks and different task weights), we fix the probability that a task fails as $p_{fail}$, then simulate the corresponding failure rate. To be specific, for a given DAG $G = (V, E)$ and a given probability of failure value $p_{fail}$, we compute the average task weight as $\bar{w} = \sum_{i \in V} W_1(T_i)/|V|$, where $W_1(T_i)$ is the sequential execution time of the $i$-th task in $V$. We then derive the corresponding failure rate $\lambda$ such that $p_{fail} = 1 - e^{-\lambda \bar{w}}$. We conduct experiments with four $p_{fail}$ values: 0.1, 0.05, 0.01, and 0.005.

### 5.1.5 Checkpointing and Verification Cost

An important factor that influences the performance of checkpointing strategies, and more precisely of the checkpointing and recovery overheads, is the data-intensiveness of the application. The workflows generated by WfChef give task durations in seconds and file sizes in bytes, which makes it difficult to quantify data-intensiveness. We define the Communication-to-Computation Ratio (CCR) as the time needed to store all the files handled by a workflow (input, output, and intermediate files) divided by the time needed to perform all the computations of that workflow on a single processor. The total store time is the total file size divided by the bandwidth to stable storage. Instead of picking arbitrary bandwidth values, which would have different meanings for different workflows, we vary the CCR by scaling file data sizes by a factor. This makes it possible to consider and quantify the data-intensiveness of all workflows in a coherent manner across experiments and workflow classes and configurations. We assume that the recovery cost
$R$ equals the checkpointing cost of the same set of files and that $R = 0.8 \times (C + V)$, thus the verification cost $V$ is one-fourth of the checkpointing cost $C$.

### 5.1.6 Competitors

In the experiments, we compare our new strategy against the following baselines, all implemented on top of the CPA13 scheduling algorithm:

* *CkptAll*: every task is checkpointed;

* *CkptNone*: no checkpoint is performed;

* *CkptCrossover*: every crossover dependence is checkpointed, which is the minimum strategy to prevent errors from propagating across processors and triggering massive rollbacks.

All strategies are evaluated using a discrete-event simulator. For each workflow and parameter configuration, we perform 10 000 independent simulation trials. Due to potential cascading re-executions under high failure rates, some trials may not complete within a reasonable time frame. To ensure robustness, we report the geometric mean of the observed makespans over valid trials, defined as configurations where at least 5000 out of the 10 000 simulations complete successfully before a predefined timeout threshold. This filtering ensures statistical significance while avoiding bias from extreme outliers due to pathological failure scenarios. All source code and experimental artifacts are publicly available at [12].

## 5.2 Results

In this section, we compare the expected makespan of our proposed strategy with that of the three competitors (*CkptCrossover*, *CkptAll*, and *CkptNone*) across the two benchmark datasets. More precisely, we plot the relative expected makespan, defined as the ratio of the makespan of our strategy over the makespan of each competitor. Hence, a value smaller than 1 in the figures means that our strategy is better. To avoid unbounded rollbacks in case of large tasks and high probability of failures, etc., each simulation run is subject to a timeout threshold set to six times the DAG's critical path length, measured under a failure-free scenario where all tasks are checkpointed.

### 5.2.1 DAGGEN Workflows

Figures 2, 3 and 4 show relative expected makespans of our strategy to that of the competitors when the Communication-to-Computation Ratio increases using boxplots¹. Each figure is arranged in a grid where the three rows correspond to increasing failure probabilities (from top = low $p_{fail}$ to bottom = high $p_{fail}$), and the columns correspond to increasing portions of *chain* in the workflow (from left = few chains to right = more chains). On these figures, as explained above, data points below the y = 1 line denote cases where our strategy outperforms a competitor (i.e., achieves a lower expected makespan). We report the percentage of valid instances, i.e., those in which more than 5000 of the 10 000 simulation trials finished before the timeout threshold. These numbers are printed with the same color as the boxplot of the corresponding strategy above the horizontal axis in each figure, whenever the value is not 100%. To enable fair comparison across strategies, we consider only the intersection of valid instances (i.e., those completed by all compared strategies), with the exception of *CkptNone*, which is excluded from this intersection due to its frequent timeouts.
<figure><img src="image_6.png" /><figcaption>Figure 2: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 50 tasks, 48 processors, three different failure rates, three different percentages of chains, and varying Communication-to-Computation Ratio (CCR). Our strategy outperforms any strategy whose relative makespan is smaller than 1.</figcaption></figure>

A clear observation is that our strategy outperforms *CkptAll* and *CkptCrossover* in almost all of the cases. As the CCR increases, we achieve more significant improvements reaching up to 80% gain. This is because when checkpointing becomes expensive, we decide cautiously on which task to checkpoint, while *CkptAll* still pays all checkpoint overheads. In addition, *CkptAll* and *CkptCrossover* exhibit same performance in most scenarios. This is because the CPA13 does not avoid crossover dependencies by design, leading *CkptCrossover* to checkpoint almost all tasks, similarly to what *CkptAll* does. A slight advantage of *CkptCrossover* can occasionally be observed when mapping large graphs on relatively few processors and the failure probability is low, e.g., 5000 tasks on 48 processors with $p_{fail} = 0.005$. In such cases, more tasks are executed serially, which provides *CkptCrossover* more opportunities to save checkpointing cost induced by crossover dependencies. However, when the CCR decreases and the failure probability increases, *CkptAll* tends to outperform *CkptCrossover*. This is because the cost of re-execution due to failures becomes significantly higher than the overhead of checkpointing, making full protection more beneficial. In contrast, our strategy not only avoids crossover dependencies during the mapping phase, but also dynamically decides where to place checkpoints. As a result, it combines

<footnote n="1">¹Each boxplot consists of a bold line for the median, a box for the quartiles, whiskers that extend at most to 1.5 times the interquartile range from the box and additional points for outliers.</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 3: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 500 tasks, 120 processors, three different failure rates, three different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

the strengths of both approaches and consistently delivers superior performance.

Another common trend is the declining performance of *CkptNone* as the CCR decreases. This is because when checkpointing becomes cheaper, not checkpointing any task becomes a losing strategy (poorer resilience to failures, but little saving on checkpointing overhead). We achieve better results than *CkptNone* except in two particular infrequent scenarios: (i) when checkpointing is expensive (i.e., high CCR), and/or (ii) when failures are rare (i.e., low $p_{fail}$). In practice, under these extreme conditions, the optimal strategy is often to assume that no error will occur, and in the rare case that one error strikes, to simply restart the entire workflow execution. However, this disadvantage quickly diminishes as either the failure rate increases or the workflow scales up. Overall, *CkptNone* becomes worse whenever the failure rate increases (going from the topmost row to the bottom one in the figures), and/or when the number of tasks is large. When the failure rate is high and the workflows are large, *CkptNone* is unable to finish execution, yielding 0% valid instances (shown in blue numbers), which clearly illustrates its lack of robustness under stress in practice.
<figure><img src="image_8.png" /><figcaption>Figure 4: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 5000 tasks, 48 processors, three different failure rates, three different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

### 5.2.2 WfGen Workflows

Epigenomics and Soykb exhibit larger variance in task weights compared to DAGGEN workflows. For example, the median task execution time in Epigenomics is 12.26s, while there are a few tasks which run nearly for 900s. This leads to enormous rollbacks during the execution of these few extremely large tasks under high error rate scenarios. Table 2 reports the percentage of simulation runs that hit the timeout threshold across different strategies, failure rates, and CCRs. It is obvious that our strategy achieves the highest completion rates, while *CkptNone* suffers frequent timeouts, even under low failure rates, due to its lack of fault tolerance.

In Figure 5, we compare the performance of our strategy against the three baselines for Epigenomcis and Soykb workflows under two different failure scenarios ($p_{fail} = 0.01$ and $p_{fail} = 0.005$) because, according to Table 2, these are the only settings where most baseline strategies complete execution with sufficient valid trials. The overall performance trends are consistent with those observed on DAGGEN datasets. In the majority of cases, our strategy also achieves similar or better performances than the competitors, and it achieves the highest completion ratio with fewer task checkpoints. As explained in Section 4.2, we try to minimize checkpointing overhead by assigning linear chains to the same set of processors. As a consequence, there is a potential loss of parallelism, which explains the sometimes worse performance of our strategy. Overall, of
the four considered task scheduling and checkpointing heuristics, our approach never achieves significantly bad performance, and most of the time achieves the best performance. Moreover, Figure 6 analyzes the expected makespan of different strategies as the number of processors increases. The results show that our strategy achieves increasingly significant improvements with more processors, confirming the effectiveness of the processor reassignment mechanism proposed in Section 4.4.

Over the whole experimental campaign, our strategy achieves an average reduction in expected makespan of 35.7% and 37.6% compared to *CkptAll* and *CkptCrossover*, respectively. While *CkptNone* occasionally outperforms us in limited set of particular cases (e.g., low failure rates and high checkpoint costs), it fails to complete execution in most of the configurations, with a timeout rate of 83.1%, compared to 21.7% for *CkptCrossover* and 19% for *CkptAll*. In contrast, our strategy completes execution successfully in 97.5% of the cases across all settings. These results highlight not only the superior average performance of our method, but also its robustness and reliability under a wide range of scenarios in practice.

In addition to the results presented above, we conducted a more comprehensive set of experiments to evaluate the performance of our strategy across a broader range of workflows and parameter settings including additional workflows generated by WfGen. All results consistently confirm the trends observed in this section. Additional results can be found in appendix.

<table><caption>Table 2: Percentage of invalid instances, i.e., instance where more than half of the simulation trials reached the timeout, for WfGen workflows. For each cell, four columns of numbers represent *CkptAll*, *CkptCrossover*, *CkptNone* and our strategy respectively.</caption><thead><tr><th>CCR</th><th>10<sup>-3</sup></th><th>10<sup>-2</sup></th><th>10<sup>-1</sup></th><th>10<sup>0</sup></th><th>10<sup>1</sup></th></tr></thead><tbody><tr><th scope="row">P<sub>fail</sub></th><td colspan="5" style="text-align:center;">Epigenomics</td></tr><tr><th scope="row">0.1</th><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th scope="row">0.05</th><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th scope="row">0.01</th><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><th scope="row">0.005</th><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><th scope="row">0.1</th><td>25%</td><td>25%</td><td>100%</td><td>25%</td><td>50%</td></tr><tr><th scope="row">0.05</th><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>50%</td></tr><tr><th scope="row">0.01</th><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><th scope="row">0.005</th><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr></tbody></table><table><thead><tr><th>CCR</th><th>10<sup>-3</sup></th><th>10<sup>-2</sup></th><th>10<sup>-1</sup></th><th>10<sup>0</sup></th><th>10<sup>1</sup></th></tr></thead><tbody><tr><th scope="row">P<sub>fail</sub></th><td colspan="5" style="text-align:center;">Soykb</td></tr><tr><th scope="row">0.1</th><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th scope="row">0.05</th><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><th scope="row">0.01</th><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><th scope="row">0.005</th><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr></tbody></table>

# 6 Conclusion

This work provides the first study on mapping and scheduling workflows composed of moldable tasks onto parallel platforms that are subject to silent errors. This problem is critically important for scientific applications because (i) moldable tasks are omnipresent in scientific libraries, and (ii) silent errors represent a major threat to high-performance computing workloads.

We have extended CPA13, the state-of-the-art mapping and scheduling algorithm designed for error-free environments, by introducing novel processor allocation, task mapping, and checkpointing heuristic based on several optimization strategies. We have conducted an extensive simulation campaign, with a comparison of the CPA13-inspired baseline *CkptCrossover* and two natural competitor strategies, *CkptAll* (checkpoint all tasks) and *CkptNone* (checkpoint no task). Across all experiments, our method consistently demonstrated high robustness, completing 97.5% of all experimental scenarios, significantly outperforming *CkptCrossover* and *CkptAll* (both around 80%) and *CkptNone* (less than 20%). In addition, we achieved an average gain of 35% over the competitors in the subset of valid cases where they did not time out. These results
<figure><img src="image_9.png" /><figcaption>Figure 5: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Epigenomics and Soykb workflows with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> = 0.01 and *p*<sub>fail</sub> = 0.005, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 6: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Epigenomics and Soykb workflows with 500 tasks, setting *p*<sub>fail</sub> = 0.01 and *p*<sub>fail</sub> = 0.005, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>
confirm the efficiency and resilience of our approach in realistic execution conditions.

Future work will investigate even more demanding execution frameworks on extreme-scale platforms, where both fail-stop errors (such as processor crashes) and silent errors may strike during execution.

## References

[1] G. Amdahl. The validity of the single processor approach to achieving large scale computing capabilities. In *AFIPS Conference Proceedings*, volume 30, pages 483-485. AFIPS Press, 1967.

[2] Ismail Assayad, Alain Girault, and Hamoudi Kalla. Tradeoff exploration between reliability, power consumption, and execution time for embedded systems. *International Journal on Software Tools for Technology Transfer*, 15(3):229-245, 2013.

[3] Leonardo Bautista-Gomez, Ferad Zyulkyarov, Osman Unsal, and Simon McIntosh-Smith. Unprotected computing: A large-scale study of dram raw error rate on a supercomputer. In *SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis*, pages 645-655, 2016.

[4] Krishna P. Belkhale, Prithviraj Banerjee, and W. Springfield Av. A scheduling algorithm for parallelizable dependent tasks. In *IPPS*, pages 500-506, 1991.

[5] Chao Chen, Greg Eisenhauer, Matthew Wolf, and Santosh Pande. LADR: Low-cost application-level detector for reducing silent output corruptions. In *HPDC*, pages 156-167. ACM, 2018.

[6] Chi-Yeh Chen and Chih-Ping Chu. A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints. *IEEE Trans. Parallel Distrib. Syst.*, 24(8):1479-1488, 2013.

[7] Tainã Coleman, Henri Casanova, and Rafael Ferreira da Silva. Automated generation of scientific workflow generators with wfchef. *Future Generation Computer Systems*, 147:16-29, 2023.

[8] Tainã Coleman, Henri Casanova, Loïc Pottier, Manav Kaushik, Ewa Deelman, and Rafael Ferreira da Silva. Wfcommons: A framework for enabling scientific workflow research and development. *Future generation computer systems*, 128:16-27, 2022.

[9] R.G. Dreslinski, M. Wieckowski, D. Blaauw, D. Sylvester, and T. Mudge. Near-threshold computing: Reclaiming moore's law through energy efficient integrated circuits. *Proceedings of the IEEE*, 98(2):253-266, 2010.

[10] Dror G. Feitelson and Larry Rudolph. Toward convergence in job schedulers for parallel supercomputers. In *Job Scheduling Strategies for Parallel Processing*, pages 1-26. Springer, 1996.

[11] Anja Feldmann, Ming-Yang Kao, Jiří Sgall, and Shang-Hua Teng. Optimal on-line scheduling of parallel jobs with dependencies. *Journal of Combinatorial Optimization*, 1(4):393-411, 1998.

[12] Qi Gao. Coping with silent errors for workflows of moldable tasks: Simulation code. https://github.com/qqqqqqqqqi/moldable-workflows.git.
[13] Mark Gates, Ahmad Abdelfattah, Kadir Akbudak, Mohammed A. Al Farhan, Rabab Alo-mairy, Daniel Bielich, Treece Burgess, Sébastien Cayrols, Neil Lindquist, Dalal Sukkari, and Asim YarKhan. Evolution of the SLATE linear algebra library. *Int. J. High Perform. Comput. Appl.*, 39(1):3–17, 2025.

[14] Pierre-Louis Guhur, Hong Zhang, Tom Peterka, Emil Constantinescu, and Franck Cappello. Lightweight and accurate silent data corruption detection in ordinary differential equation solvers. In *Euro-Par*. Springer, 2016.

[15] Jessen T. Havill and Weizhen Mao. Competitive online scheduling of perfectly malleable jobs with setup times. *European Journal of Operational Research*, 187:1126–1142, 2008.

[16] Thomas Herault and Yves Robert, editors. *Fault-Tolerance Techniques for High-Performance Computing*, Computer Communications and Networks. Springer Verlag, 2015.

[17] Sascha Hunold. One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints. *Concurr. Comput. Pract. Exp.*, 27(4):1010–1026, 2015.

[18] IBM Spectrum. LSF (Load Sharing Facility). https://www.ibm.com/docs/en/spectrum-lsf/10.1.0, December 2022.

[19] Klaus Jansen and Hu Zhang. Scheduling malleable tasks with precedence constraints. In *SPAA*, page 86–95, 2005.

[20] P.K. Krause and I. Polian. Adaptive voltage over-scaling for resilient applications. In *Design, Automation Test in Europe Conference Exhibition (DATE)*, pages 1–6, 2011.

[21] David A. Lifka. The anl/ibm sp scheduling system. In Dror G. Feitelson and Larry Rudolph, editors, *Job Scheduling Strategies for Parallel Processing*, pages 295–303, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.

[22] Marc Snir et al. Addressing failures in exascale computing. *Int. J. High Perform. Comput. Appl.*, 28(2):129–173, 2014.

[23] Adam Moody, Greg Bronevetsky, Kathryn Mohror, and Bronis R De Supinski. Design, modeling, and evaluation of a scalable multi-level checkpointing system. In *SC'10: Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis*, pages 1–11. IEEE, 2010.

[24] T.J. O'Gorman. The effect of cosmic rays on the soft error rate of a DRAM at ground level. *IEEE Trans. Electron Devices*, 41(4):553–557, 1994.

[25] Xiao Qin and Hong Jiang. A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems. *Parallel Computing*, 32(5-6):331–356, 2006.

[26] Andrei Radulescu and Arjan J. C. van Gemund. A low-cost approach towards mixed task and data parallel scheduling. In Lionel M. Ni and Mateo Valero, editors, *Proceedings of the 2001 International Conference on Parallel Processing, ICPP 2002, 3-7 September 2001, Valencia, Spain*, pages 69–76. IEEE Computer Society, 2001.
[27] Vilas Sridharan, Nathan DeBardeleben, Sean Blanchard, Kurt B. Ferreira, Jon Stearley, John Shalf, and Sudhanva Gurumurthi. Memory errors in modern systems: The good, the bad, and the ugly. In *20th Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS)*, pages 297–310. ACM, 2015.

[28] Frederic Suter. Daggen: a synthetic task graph generator. https://github.com/frs69wq/daggen.

[29] Qingzhou Wang and Kam Hoi Cheng. A heuristic of scheduling parallel tasks and its analysis. *SIAM J. Comput.*, 21(2):281–294, 1992.

[30] Panruo Wu, Chong Ding, Longxiang Chen, Feng Gao, Teresa Davies, Christer Karlsson, and Zizhong Chen. Fault tolerant matrix-matrix multiplication: Correcting soft errors on-line. In *ScalA'11*, pages 25–28, 2011.

[31] Guoqi Xie, Gang Zeng, Renfa Li, and Keqin Li. *Scheduling Parallel Applications on Heterogeneous Distributed Systems*. Springer, 2019.

[32] Yongbin Yoo, Morris Jette, and Mark Grondona. Slurm: Simple linux utility for resource management. In *Job Scheduling Strategies for Parallel Processing*, volume 2862 of *Lecture Notes in Computer Science*, pages 44–60. Springer, 2003.

[33] J. F. Ziegler, H. W. Curtis, H. P. Muhlfeld, C. J. Montrose, and B. Chin. IBM experiments in soft fails in computer electronics. *IBM J. Res. Dev.*, 40(1):3–18, 1996.

[34] J.F. Ziegler, M.E. Nelson, J.D. Shell, R.J. Peterson, C.J. Gelderloos, H.P. Muhlfeld, and C.J. Montrose. Cosmic ray soft error rates of 16-Mb DRAM memory chips. *IEEE Journal of Solid-State Circuits*, 33(2):246–252, 1998.
A Additional Results

<figure><img src="image_11.png" /><figcaption>Figure 7: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 50 tasks, 48 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 8: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 50 tasks, 120 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Figure 9: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 500 tasks, 48 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Figure 10: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 500 tasks, 120 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Figure 11: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 5000 tasks, 48 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>Figure 12: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the DAGGEN workflows with 5000 tasks, 120 processors, four different failure rates, four different percentages of chains, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Figure 13: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Epigenomics workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting $p_{fail}$ to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<table><caption>Table 3: Percentage of invalid instances i.e., instance where more than half of the simulation trials reached the timeout, for WfGen workflows. For each cell, four columns of numbers represent *CkptAll*, *CkptCrossover*, *CkptNone* and our strategy respectively.</caption><thead><tr><th>CCR</th><th>10<sup>-3</sup></th><th>10<sup>-2</sup></th><th>10<sup>-1</sup></th><th>10<sup>0</sup></th><th>10<sup>1</sup></th></tr></thead><tbody><tr><td>p<sub>fail</sub></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td colspan="6">Epigenomics</td></tr><tr><td>0.1</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>0.05</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>0.01</td><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Soykb</td></tr><tr><td>0.1</td><td>25%</td><td>25%</td><td>100%</td><td>25%</td><td>50%</td></tr><tr><td>0.05</td><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Montage</td></tr><tr><td>0.1</td><td>50%</td><td>50%</td><td>100%</td><td>50%</td><td>50%</td></tr><tr><td>0.05</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Cycle</td></tr><tr><td>0.1</td><td>50%</td><td>50%</td><td>100%</td><td>25%</td><td>50%</td></tr><tr><td>0.05</td><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Genome</td></tr><tr><td>0.1</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.05</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Seismology</td></tr><tr><td>0.1</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.05</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Srasearch</td></tr><tr><td>0.1</td><td>25%</td><td>25%</td><td>100%</td><td>25%</td><td>25%</td></tr><tr><td>0.05</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td colspan="6">Bwa</td></tr><tr><td>0.1</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td><td>100%</td></tr><tr><td>0.05</td><td>100%</td><td>100%</td><td>100%</td><td>75%</td><td>100%</td></tr><tr><td>0.01</td><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td>0.005</td><td>25%</td><td>25%</td><td>100%</td><td>0%</td><td>25%</td></tr><tr><td colspan="6">Blast</td></tr><tr><td>0.1</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.05</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.01</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr><tr><td>0.005</td><td>0%</td><td>0%</td><td>100%</td><td>0%</td><td>0%</td></tr></tbody></table>
<figure><img src="image_18.png" /><figcaption>Figure 14: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Soykb workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Figure 15: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Montage workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 16: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Cycle workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 17: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Genome workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>Figure 18: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Seismology workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 19: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Srasearch workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_24.png" /><figcaption>Figure 20: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Bwa workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Figure 21: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Blast workflow with 500 and 5000 tasks, executing on 48 and 120 processors, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, and varying Communication-to-Computation Ratio (CCR).</figcaption></figure>
<figure><img src="image_26.png" /><figcaption>Figure 22: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Epigenomics workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Figure 23: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Soykb workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>
<figure><img src="image_28.png" /><figcaption>Figure 24: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Monatge workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 25: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Cycle workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>Figure 26: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Genome workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Figure 27: Expected Srasearch of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Srasearch workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>
<figure><img src="image_32.png" /><figcaption>Figure 28: Expected makespan of our strategy relative to that of *CkptAll*, *CkptCrossover*, and *CkptNone* for the Bwa workflow with 500 tasks, setting *p*<sub>fail</sub> to 0.005, 0.01, 0.05, and 0.1, setting Communication-to-Computation Ratio (CCR) to 0.001, 0.01, 0.1, 1, and 10, and varying the number of processors.</figcaption></figure>
Inria

RESEARCH CENTRE
Centre Inria de Lyon

Bâtiment CEI-2, Campus La Doua
56, Boulevard Niels Bohr - CS 52132
69603 Villeurbanne

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399