Scientific workflows have become mainstream in support of research and development activities in numerous scientific domains [1]. Consequently, several Workflow Management Systems (WMSs) have been developed [2,3,4,5,6,7] that allow scientists to execute workflows on distributed platforms that can accommodate executions at various scales. WMSs handle the logistics of workflow executions and make decisions regarding resource selection, data management, and computation scheduling, the goal being to optimize some performance metric (e.g., latency [8,9], throughput [10,11], jitter [12], reliability [13,14,15], power consumption [16,17]). WMSs are complex software systems that interact with complex software infrastructures and can thus employ a wide range of designs and algorithms.
In spite of active WMS development and use in production, which has entailed solving engineering challenges, fundamental questions remain unanswered in terms of system designs and algorithms. Although there are theoretical underpinnings for most of these questions, theoretical results often make assumptions that do not hold with production hardware and software infrastructures. Further, the specifics of the design of a WMS can impose particular constraints on what solutions can be implemented effectively, and these constraints are typically not considered in available theoretical results. Consequently, current research that aims at improving and evolving the state of the art, although sometimes informed by theory, is mostly done via "real-world" experiments: designs and algorithms are implemented, evaluated, and selected based on experiments conducted for a particular WMS implementation with particular workflow configurations on particular platforms. As a corollary, from the WMS user's perspective, quantifying accurately how a WMS would perform for a particular workflow configuration on a particular platform entails actually executing that workflow on that platform.
Unfortunately, real-world experiments have limited scope, which impedes WMS research and development. This is because they are confined to application and platform configurations available at hand, and thus cover only a small subset of the relevant scenarios that may be encountered in practice. Furthermore, exclusively relying on real-world experiments makes it difficult or even impossible to investigate hypothetical scenarios (e.g., "What if the network had a different topology?", "What if there were 10 times more compute nodes but they had half as many cores?"). Real-world experiments, especially when largescale, are often not fully reproducible due to shared networks and compute resources, and due to transient or idiosyncratic behaviors (maintenance schedules, software upgrades, and particular software (mis)configurations). Running real-world experiments is also time-consuming, thus possibly making it difficult to obtain statistically significant numbers of experimental results. Real-world experiments are driven by WMS implementations that often impose constraints on workflow executions. Furthermore, WMSs are typically not monolithic but instead reuse CyberInfrastructure (CI) components that impose their own overheads and constraints on workflow execution. Exploring what lies beyond these constraints via real-world executions, e.g., for research and development purposes, typically entails unacceptable software (re-)engineering costs. Finally, running real-world experiments can also be labor-intensive. This is due to the need to install and execute many full-featured software stacks, including actual scientific workflow implementations, which is often not deemed worthwhile for "just testing out" ideas.
An alternative to conducting WMS research via real-world experiments is to use simulation, i.e., implement a software artifact that models the functional and performance behaviors of software and hardware stacks of interest. Simulation is used in many computer science domains and can address the limitations of real-world experiments outlined above. Several simulation frameworks have been developed that target the parallel and distributed computing domain [18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]. Some simulation frameworks have also been developed specifically for the scientific workflow domain [35,36,37,11,38,39,40].
We claim that advances in simulation capabilities in the field have made it possible to simulate WMSs that execute large workflows using diverse CI services deployed on large-scale platforms in a way that is accurate (via validated simulation models), scalable (fast execution and low memory footprint), and expressive (ability to describe arbitrary platforms, complex WMSs, and complex software infrastructure). In this work, we build on the existing open-source SimGrid simulation framework [33,41], which has been one of the drivers of the above advances and whose simulation models have been extensively validated [42,43,44,45,46], to develop a WMS simulation framework called WRENCH [47]. More specifically, this work makes the following contributions 1 :
1 A preliminary shorter version of this paper appears in the proceedings 1. We justify the need for WRENCH and explain how it improves on the state of the art.
2. We describe the high-level simulation abstractions provided by WRENCH that (i) make it straightforward to implement full-fledged simulated versions of complex WMS systems; and (ii) make it possible to instantiate simulation scenarios with only few lines of code.
3. Via two case studies with the Pegasus [2] production WMS and the WorkQueue [49] application execution framework, we evaluate the ease-of-use, accuracy, and scalability of WRENCH, and compare it with a previously proposed simulator, WorkflowSim [35].
This paper is organized as follows. Section 2 discusses related work. Section 3 outlines the design of WRENCH and describes how its APIs are used to implement simulators. Section 4 presents our case studies. Finally, Section 5 concludes with a brief summary of results and a discussion of future research directions.
Many simulation frameworks have been developed for parallel and distributed computing research and development. They span domains such as HPC [18,19,20,21], Grid [22,23,24], Cloud [25,26,27], Peer-to-peer [28,29], or Volunteer Computing [30,31,32]. Some frameworks have striven to be applicable across some or all or the above domains [33,34]. Two conflicting concerns are accuracy (the ability to capture the behavior of a real-world system with as little bias as possible) and scalability (the ability to simulate large systems with as few CPU cycles and bytes of RAM as possible). The aforementioned simulation frameworks achieve different compromises between these two concerns by using various simulation models. At one extreme are discrete event models that simulate the "microscopic" behavior of hardware/software systems (e.g., by relying on packet-level network simulation for communication [50], on cycle-accurate CPU simulation [51] or emulation for computation). In this case, the scalability challenge can be handled by using Parallel Discrete Event Simulation [52], i.e., the simulation itself is a parallel application that requires a parallel platform whose scale is at least commensurate to that of the simulated platform. At the other extreme are analytical models that capture "macroscopic" behaviors (e.g., transfer times as data sizes divided by bottleneck bandwidths, compute times as numbers of operations divided by compute speeds). While these models are typically more scalable, they must be developed with care so that they are accurate. In previous work, it has been shown that several available simulation frameworks use macroscopic models that can exhibit high inaccuracy [43].
A number of simulators have been developed that target scientific workflows. Some of them are stand-alone simulators [35,36,37,11,53]. Others are integrated with a particular WMS to promote more faithful simulation and code reuse [38,39,54] or to execute simulations at runtime to guide on-line scheduling decisions made by the WMS [40].
The authors in [39] conduct a critical analysis of the stateof-the-art of workflow simulators. They observe that many of these simulators do not capture the details of underlying infrastructures and/or use naive simulation models. This is the case with custom simulators such as that in [40,36,37]. But it is also the case with workflow simulators built on top of generic simulation frameworks that provide convenient user-level abstractions but fail to model the details of the underlying infrastructure, e.g., the simulators in [35,38,11], which build on the CloudSim [25] or GroudSim [24] frameworks. These frameworks have been shown to lack in their network modeling capabilities [43]. As a result, some authors readily recognize that their simulators are likely only valid when network effects play a small role in workflow executions (i.e., when workflows are not data-intensive).
To overcome the above limitations, in [39,54] the authors have improved the network model in GroudSim and also use a separate simulator, DISSECT-CF [27], for simulating cloud infrastructures accurately. The authors acknowledge that the popular SimGrid [33,41] simulation framework offers compelling capabilities, both in terms of scalability and simulation accuracy. But one of their reasons for not considering SimGrid is that, because it is low-level, using it to implement a simulator of a complex system, such as a WMS and the CI services it uses, would be too labor-intensive. In this work, we address this issue by developing a simulation framework that provides convenient, reusable, high-level abstractions but that builds on Sim-Grid so as to benefit from its scalable and accurate simulation models. Furthermore, unlike [38,39,54], we do not focus on integration with any specific WMS. The argument in [39] is that stand-alone simulators, such as that in [35], are disconnected from real-world WMSs because they abstract away much of the complexity of these systems. Instead, our proposed framework does capture low-level system details (and simulates them well thanks to SimGrid), but provides high-level enough abstractions to implement faithful simulations of complex WMSs with minimum effort, which we demonstrate via two case studies.
Also related to this work is previous research that has not focused on providing simulators or simulation frameworks per se, but instead on WMS simulation methodology. In particular, several authors have investigated methods for injecting realistic stochastic noise in simulated WMS executions [35,55]. These techniques can be adopted by most of the aforementioned frameworks, including the one proposed in this work.
WRENCH's objective is to make it possible to study WMSs in simulation in a way that is accurate (faithful modeling of real-world executions), scalable (low computation and memory footprints on a single computer), and expressive (ability to simulate arbitrary WMS, workflow, and platform scenarios with minimal software engineering effort). WRENCH is not a simulator but a simulation framework that is distributed as a C++ library. It provides high-level reusable abstractions for developing simulated WMS implementations and simulators for the execution of these implementations. There are two categories of WRENCH users:
1. Users who implement simulated WMSs -These users are engaged in WMS research and development activities and need an "in simulation" version of their current or intended WMS. Their goals typically include evaluating how their WMS behaves over hypothetical experimental scenarios and comparing competing algorithm and system design options. For these users, WRENCH provides the WRENCH Developer API (described in Section 3.4) that eases WMS development by removing the typical difficulties involved when developing, either in real-world or in simulation mode, a system comprised of distributed components that interact both synchronously and asynchronously. To this end, WRENCH makes it possible to implement a WMS as a single thread of control that interacts with simulated CI services via high-level APIs and must react to a small set of asynchronous events. 2. Users who execute simulated WMSs -These users simulate how given WMSs behave for particular workflows on particular platforms. Their goals include comparing different WMSs, determining how a given WMS would behave for various workflow configurations, comparing different platform and resource provisioning options, determining performance bottlenecks, engaging in pedagogic activities centered on distributed computing and workflow issues, etc. These users can develop simulators via the WRENCH User API (described in Section 3.5), which makes it possible to build a full-fledged simulator with only a few lines of code. Users in the first category above often also belong to the second category. That is, after implementing a simulated WMS these users typically instantiate simulators for several experimental scenarios to evaluate their WMS.
Figure 1 depicts WRENCH's software architecture. At the bottom layer is the Simulation Core, which simulates lowlevel software and hardware stacks using the simulation abstractions and models provided by SimGrid (see Section 3.3). The next layer implements simulated CI services that are commonly found in current distributed platforms and used by production WMSs. At the time of this writing, WRENCH provides services in 4 categories: compute services that provide access to compute resources to execute workflow tasks; storage services that provide access to storage resources for storing workflow data; network monitoring services that can be queried to determine network distances; and data registry services that can be used to track the location of (replicas of) workflow data. Each category includes multiple service implemen- tations, so as to capture specifics of currently available CI services used in production. For instance, WRENCH includes a "batch-scheduled cluster" compute service, a "cloud" compute service, and a "bare-metal" compute service. The above layer in the software architecture consists of simulated WMS, that interact with CI services using the WRENCH Developer API (see Section 3.4). These WMS implementations, which can simulate production WMSs or WMS research prototypes, are not included as part of the WRENCH distribution, but implemented as stand-alone projects. Two such projects are the simulated Pegasus and Workqueue implementations used for our case study in Section 4. Finally, the top layer consists of simulators that configure and instantiate particular CI services and particular WMSs on a given simulated hardware platform, that launch the simulation, and that analyze the simulation outcome. These simulators use the WRENCH User API (see Section 3.5).
Here again, these simulators are not part of WRENCH, but implemented as stand-alone projects.
WRENCH's simulation core is implemented using Sim-Grid's S4U API, which provides all necessary abstractions and models to simulate computation, I/O, and communication activities on arbitrary hardware platform configurations. These platform configurations are defined by XML files that specify network topologies and endpoints, compute resources, and storage resources [56].
At its most fundamental level, SimGrid provides a Concurrent Sequential Processes (CSP) model: a simulation consists of sequential threads of control that consume hardware resources. These threads of control can implement arbitrary code, exchange messages via a simulated network, can perform computation on simulated (multicore) hosts, and can perform I/O on simulated storage devices. In addition, SimGrid provides a virtual machine abstraction that includes a migration feature. Therefore, SimGrid provides all the base abstractions necessary to implement the classes of distributed systems that are relevant to scientific workflow executions. However, these abstractions are low-level and a common criticism of SimGrid is that implementing a simulation of a complex system requires a large software engineering effort. A WMS executing a workflow using several CI services is a complex system, and WRENCH builds on top of SimGrid to provide high-level abstractions so that implementing this complex system is not labor-intensive.
We have selected SimGrid for WRENCH for the following reasons. SimGrid has been used successfully in many distributed computing domains (cluster, peer-to-peer, grid, cloud, volunteer computing, etc.), and thus can be used to simulate WMSs that execute over a wide range of platforms. SimGrid is open source and freely available, has been stable for many years, is actively developed, has a sizable user community, and has provided simulation results for over 350 research publications since its inception. SimGrid has also been the object of many invalidation and validation studies [42,43,44,45,46], and its simulation models have been shown to provide compelling advantages over other simulation frameworks in terms of both accuracy and scalability [33]. Finally, most SimGrid simulations can be executed in minutes on a standard laptop computer, making it possible to perform large numbers of simulations quickly with minimal compute resource expenses. To the best of our knowledge, among comparable available simulation frameworks (as reviewed in Section 2), SimGrid is the only one to offer all the above desirable characteristics.
With the Developer API, a WMS is implemented as a single thread of control that executes according to the pseudo-code blueprint shown in Algorithm 1. Given a workflow to execute, a WMS first gathers information about all the CI services it can use to execute the workflow (lines 2-3). Examples of such information include the number of compute nodes provided by a compute service, the number of cores per node and the speed of these cores, the amount of storage space available in a storage service, the list of hosts monitored by a network monitoring service, etc. Then, the WMS iterates until the workflow execution is complete or has failed (line 4). At each iteration it gathers dynamic information about available services and resources if needed (line 5). Example of such information include currently available capacities at compute or storage services, current network distances between pairs of hosts, etc. Based on resource information and on the current state of the workflow, the WMS can then make whatever scheduling decisions it sees fit (line 7). It then enacts these decisions by interacting with appropriate services. For instance, it could decide to submit a "job" to a compute service to execute a ready task on some number of cores at some compute service and copy all produced files to some storage service, or it could decide to just copy a file between storage services and then update a data location service to keep track of the location of this new file replica. It could also submit one or more pilot jobs [57] to compute services if they support them. It is the responsibility of the developer to implement all decision-making algorithms employed by the WMS. At the end of the iteration, the WMS simply waits for a workflow execution event to which it can react if need be. Most common events are job completions/failures and data transfer completions/failures.
The WRENCH Developer API provides a rich set of methods to create and analyze a workflow and to interact with CI services to execute a workflow. These methods were designed based on current and envisioned capabilities of current stateof-the-art WMSs. We refer the reader to the WRENCH Web site [47] for more information on how to use this API and for the full API documentation. The key objective of this API is to make it straightforward to implement a complex system, namely a full-fledged WMS that interact with diverse CI services. We achieve this objective by providing simple solutions and abstractions to handle well-known challenges when implementing a complex distributed system (whether in the real world or in simulation), as explained hereafter.
SimGrid provides simple point-to-point communication between threads of control via a mailbox abstraction. One of the recognized strengths of SimGrid is that it employs highly accurate and yet scalable network simulation models. However, unlike some of its competitors, it does not provide any higherlevel simulation abstractions meaning that distributed systems must be implemented essentially from scratch, with messagebased interactions between processes. All message-based interaction is abstracted away by WRENCH, and although the simulated CI services exchange many messages with the WMS and among themselves, the WRENCH Developer API only exposes higher-level interaction with services ("run this job", "move this data") and only requires that the WMS handle a few events. The WMS developer thus completely avoids the need to send and receive (and thus orchestrate) network messages.
Another challenge when developing a system like a WMS is the need to handle asynchronous interactions. While some service interactions can be synchronous (e.g., "are you up?", "tell me your current load"), most need to be asynchronous so that the WMS retains control. The typical solution is to maintain sets of request handles and/or to use multiple threads of con-trol. To free the WMS developer from these responsibilities, WRENCH provides already implemented "managers" that can be used out-of-the-box to take care of asynchronicity. A WMS can instantiate such managers, which are independent threads of control. Each manager transparently interacts with CI services, maintains a set of pending requests, provides a simple API to check on the status of these requests, and automatically generates high-level workflow execution events. For instance, a WMS can instantiate a "job manager" through which it will create and submit jobs to compute services. It can at any time check on the status of a job, and the job manager interacts directly (and asynchronously) with compute services so as to generate "job done" or "job failed" events to which the WMS can react. In our experience developing simulators from scratch using SimGrid, the implementation of asynchronous interactions with simulated processes is a non-trivial development effort, both in terms of amount of code to write and difficulty to write this code correctly. We posit that this is one of the reasons why some users have preferred using simulation frameworks that provide higher-level abstractions than SimGrid even though they offer less attractive accuracy and/or scalability features. WRENCH provides such higher-level abstractions to the WMS developers, and as a result implementing a WMS with WRENCH can be straightforward.
Finally, one of the challenges when developing a WMS is failure handling. It is expected that compute, storage, and network resources, as well as the CI services that use them, can fail through the execution of the WMS. SimGrid has the capability to simulate arbitrary failures via availability traces. Furthermore, failures can occur due to the WMS implementation itself, e.g., if it fails to check that the operations it attempts are actually valid, if concurrent operations initiated by the WMS work at cross purposes. WRENCH abstracts away all these failures as C++ exceptions that can be caught by the WMS implementation, or caught by a manager and passed to the WMS as workflow execution events. Regardless, each failure exposes a failure cause, which encodes a detailed description of the failure. For instance, after initiating a file copy from a storage service to another storage service, a "file copy failed" event sent to the WMS would include a failure cause that could specify that when trying to copy file x from storage service y to storage service z, storage service z did not have sufficient storage space. Other example failure causes could be that a network error occurred when storage service y attempted to receive a message from storage service z, or that service z was down. All CI services implemented in WRENCH simulate well-defined failure behaviors, and failure handling capabilities afforded to simulated WMSs can actually allow more sophisticated failure tolerance strategies than currently done or possible in real-world implementations. But more importantly, the amount of code that needs to be written for failure handling in a simulated WMS is minimal.
Given the above, WRENCH makes it possible to implement a simulated WMS with very little code and effort. The example WMS implementation provided with the WRENCH distribution, which is simple but functional, is under 200 lines of C++ (once comments have been removed). See more discussion of the effort needed to implement a WMS with WRENCH in the context of our case studies (Section 4).
With the User API one can quickly build a simulator, which typically follows these steps: The above steps can be implemented with only a few lines of C++. An example is provided and described in Appendix A. This example showcases only the most fundamental features of the WRENCH User API, and we refer the reader to the WRENCH Web site [47] for more detailed information on how to use this API and for the full API documentation. In the future this API will come with Python binding so that users can implement simulators in Python.
Analyzing and interpreting simulation logs is often a laborintensive process, and users of simulators typically develop sets of scripts for parsing and extracting specific knowledge from the logs. In order to provide WRENCH users with a rapid, first insight on their simulation results, we have been developing a Web-based "dashboard" that compiles simulation logs into a set of tabular and graphical JavaScript components. The dashboard presents overall views on task life-cycles, showing breakdowns between compute and I/O operations, as well as a Gantt chart and 2-and 3-dimensional plots of task executions and resource usage during the simulated workflow execution. An overview of energy consumption per compute resource can also be visualized in the dashboard. The dashboard is currently under development and will be available for users in the next WRENCH release. Figure 2 shows a screenshot of a simple simulated workflow execution.
In this section, we present two WRENCH-based simulators of a state-of-the-art WMS, Pegasus [2], and an application execution framework, WorkQueue [49], as case studies for evaluation and validation purposes.
Pegasus is being used in production to execute workflows for dozens of high-profile applications in a wide range of scientific domains [2]. Pegasus provides the necessary abstractions for scientists to create workflows and allows for transparent execution of these workflows on a range of compute platforms including clusters, clouds, and national cyberinfrastructures. During execution, Pegasus translates an abstract resource-independent workflow into an executable workflow, determining the specific executables, data, and computational resources required for the execution. Workflow execution with Pegasus includes data management, monitoring, and failure handling, and is managed by HTCondor DAGMan [58]. Individual workflow tasks are managed by a workload management framework, HTCondor [59], which supervises task executions on local and remote resources. Workflow executions with Pegasus follow a "push model," i.e., a task is bound to a particular compute resource at the onset of the execution and is always executed on that resource if possible.
WorkQueue is being used in production by a wide range of researchers across many scientific domains for building large- scale master-worker applications that span thousands of machines drawn from clusters, clouds, and grids [60]. WorkQueue allows users to define tasks, submit them to a workqueue abstraction, and wait for their completions. During execution, WorkQueue starts standard worker processes that can run on any available compute resource. These worker processes perform data transfers and execute tasks, making it possible to execute workflows. Worker processes can also be submitted for execution on HTCondor pools, which is the approach evaluated in this paper. Workflow executions with WorkQueue follow a "pull model," i.e., late-binding of tasks to compute resources based on when resources becomes idle.
Since Pegasus relies on HTCondor, first we have implemented the HTCondor services as simulated core CI services, which together form a new Compute Service that exposes the WRENCH Developer API. This makes HTCondor available to any WMS implementation that is to be simulated using WRENCH, and has been included as part of the growing set of simulated core CI services provided by WRENCH.
HTCondor is composed of six main service daemons (startd, starter, schedd, shadow, negotiator, and collector). In addition, each host on which one or more of these daemons is spawned must also run a master daemon, which controls the execution of all other daemons (including initialization and completion). The bottom part of Figure 3 depicts the components of our simulated HTCondor implementation, where daemons are shown in red-bordered boxes. In our simulator we implement the 3 fundamental HTCondor services, implemented as particular sets of daemons, as depicted in the bottom part of Figure 3 in borderless white boxes. The Job Execution Service consists of a startd daemon, which adds the host on which it is running to the HTCondor pool, and of a starter daemon, which manages task executions on this host. The Central Manager Service consists of a collector daemon, which collects information about all other daemons, and of a negotiator daemon, which performs task/resource matchmaking. The Job Submission Service consists of a schedd daemon, which maintains a queue of tasks, and of several instances of a shadow daemon, each of which corresponds to a task submitted to the HTCondor pool for execution.
Given the simulated HTCondor implementation above, we then implemented the simulated Pegasus WMS, including the DAGMan workflow engine, using the WRENCH Developer API. This implementation instantiates all services and parses the workflow description file, the platform description file, and a Pegasus-specific configuration file. DAGMan orchestrates the workflow execution (e.g., a task is marked as ready for execution once all its parent tasks have successfully completed), and monitors the status of tasks submitted to the HTCondor pool using a pull model, i.e., task status is fetched from the pool at regular time intervals. The top part of Figure 3 depicts the components of our simulated Pegasus implementation (each shown in a red box).
By leveraging WRENCH's high-level simulation abstractions, implementing HTCondor as a reusable core WRENCH service using the Developer API required only 613 lines of code. Similarly, implementing a simulated version of Pegasus, including DAGMan, was done with only 666 lines of code (127 of which are merely parsing simulation configuration files). These numbers include both header and source files, but exclude comments. We argue that the above corresponds to minor simulation software development efforts when considering the complexity of the system being simulated.
Service implementations in WRENCH are all parameterizable. For instance, as services use message-based communications it is possible to specify all message payloads in bytes (e.g., for control messages). Other parameters encompass various overheads, either in seconds or in computation volumes (e.g., task startup overhead on a compute service). In WRENCH, service implementations come with default values for all these parameters, but it is possible to pick custom values upon service instantiation. The process of picking parameter values so as to match a specific real-world system is referred to as simulation calibration. We calibrated our simulator by measuring delays observed in event traces of real-world executions for workflows on hardware/software infrastructures (see Section 4.3).
The simulator code, details on the simulation calibration procedure, and experimental scenarios used in the rest of this section are all publicly available online [61].
WorkQueue implements a master-worker paradigm by which running worker processes can be assigned work dynamically. In our simulator, we implement workers as pilot jobs, a popular mechanism for late-binding of computation to resources [57], which is implemented in WRENCH. As WorkQueue does not provide automated mechanisms for starting workers, i.e., triggering pilot job submissions, at runtime, our simulated implementation limits the number of concurrently running pilot jobs based on available compute resources (i.e., cores are not oversubscribed). The simulator implementation has two main components: (1) a workflow system for orchestrating tasks execution and assigning compute tasks to workers; and (2) a scheduler for submitting pilot jobs to compute services. As WRENCH provides a consistent interface across all compute services, our simulator can simulate the execution of WorkQueue on any compute service provided they are configured to support pilot job execution.
Due to WRENCH's providing high-level simulation abstractions, implementing WorkQueue using the WRENCH Developer API requires only 485 lines of code (113 of which are merely parsing simulation configuration files). These numbers include both header and source files, but exclude comments. Similarly to the WRENCH-based Pegasus simulator, we argue that the simulation software development effort is minimal when considering the complexity of the system being simulated. The simulator code, details on the simulation calibration procedure, and experimental scenarios used in the rest of this section are all publicly available online [62].
We consider experimental scenarios defined by particular workflow instances to be executed on particular platforms. Due to the lack of publicly available detailed workflow execution traces (i.e., execution logs that include data sizes for all files, all execution delays, etc.), we have performed real workflow executions with Pegasus and WorkQueue, and collected raw, time-stamped event traces from these executions. These traces form the ground truth to which we can compare simulated executions. We consider these workflow applications:
• 1000Genome [63]: A data-intensive workflow that identifies mutational overlaps using data from the 1000 genomes project in order to provide a null distribution for rigorous statistical evaluation of potential disease-related mutations. We consider a 1000Genome instance that comprises 71 tasks.
for generating custom mosaics of the sky. For this experiment, we ran Montage for processing 1.5 and 2.0 square degrees mosaic 2MASS. We thus refer to each configuration as Montage-1.5 and Montage-2.0, respectively. Montage-1.5, resp. Montage-2.0, comprises 573, resp. 1,240, tasks.
for accelerating genome assembly. For this experiment, we ran SAND for a full set of reads from the Anopheles gambiae Mopti form. We consider a SAND instance that comprises 606 tasks. We use these platforms, deploying on each a submit node (which runs Pegasus and DAGMan or WorkQueue, and HT-Condor's job submission and central manager services), four worker nodes (4 or 24 cores per node / shared file system), and a data node in the WAN:
• ExoGENI: A widely distributed networked infrastructureas-a-service testbed representative of a "bare metal" platform. Each worker node is a 4-core 2.0GHz processor with 12GiB of RAM. The bandwidth between the data node and the submit node was ∼0.40 Gbps, and the bandwidth between the submit and worker nodes was ∼1.00 Gbps.
• AWS: Amazon's cloud platform, on which we use two types of virtual machine instances: t2.xlarge and m5.xlarge. The bandwidth between the data node and the submit node was ∼0.44 Gbps, and the bandwidth between the submit and worker nodes on these instances were ∼0.74 Gbps and ∼1.24 Gbps, respectively. • Chameleon: An academic cloud testbed, on which we use homogeneous standard cloud units to run an HTCondor pool. Each unit consists of a 24-core 2.3GHz processor with 128 GiB of RAM. The bandwidth between the submit node and worker nodes on these instances were ∼10.00 Gbps. To evaluate the accuracy of our simulators, we consider 4 particular experimental scenarios: 1000Genome on ExoGENI, Montage-1.5 on AWS-t2.xlarge, Montage-2.0 on AWS-m5.xlarge, and SAND on Chameleon. The first three scenarios are performed using Pegasus, and the last one is performed using WorkQueue. For each scenario we repeat the realworld workflow execution 5 times (since real-world executions are not perfectly deterministic), and also run a simulated execution execution using the WRENCH-based simulators described in the previous section. For each execution, real-world or simulated, we keep track of the overall application makespan, but also of time-stamped individual execution events such as task submission and completions dates.
The fourth column in Table 1 shows average relative differences between actual and simulated makespans. We see that simulated makespans are close to actual makespans for all three Pegasus scenarios (average relative error is below 5%). One of the key advantages of building WRENCH on top of SimGrid is that WRENCH simulators benefit from the high-accuracy network models in SimGrid. In particular, these models capture many features of the TCP protocol (without resorting to packetlevel simulation). And indeed, when comparing real-world and simulated executions we observe average relative error below 3% for data movement operations. Furthermore, the many processes involved in a workflow execution interact by exchanging (typically small) control messages, and our simulators simulate these message exchanges. For instance, each time an output file is produced by a task a data registry service is contacted so that a new entry can be added to its database of file replicas, which incurs some communication overhead. When comparing real-world to simulated executions we observe average relative simulation error below 1% for these data registration overheads. Overall, a key reason for the high accuracy of our simulators is that they simulate data and control message transfers accurately.
To draw comparisons with a state-of-the-art simulator, we repeated the above Pegasus simulation experiments using Work-flowSim [35]. WorkflowSim simulates workflow executions based on execution models similar to that of Pegasus and is built on top of the CloudSim simulation framework [25]. However, WorkflowSim does not provide a detailed simulated HT-Condor implementation, and does not offer the same simulation calibration capabilities as WRENCH. Nevertheless, we have painstakingly calibrated the WorkflowSim simulator so that it models the hardware and software infrastructures of our experimental scenarios as closely as possible. For each of the 3 Pegasus experimental scenarios, we find that the relative average makespan percentage error is 12.09 ±2.84, 26.87 ±6.26, and 13.32 ±1.12, respectively, i.e., from 4x up to 11x larger than the error values obtained with our WRENCH-based simulator. The reasons for the discrepancies between WorkflowSim and real-world results are twofold. First, WorkflowSim uses the simplistic network models in CloudSim (see discussion in Section 2) and thus suffers from simulation bias w.r.t. communication times. Second, WorkflowSim does not capture all the relevant system details of the system and of the workflow execution. By contrast, our WRENCH-based simulator benefits from the accurate network simulation models provided by SimGrid, and it does capture low-level relevant details although implemented with only a few hundred lines of code.
In our experiments, we also record the submission and completion dates of each task, thus obtaining empirical cumulative density functions (ECDFs) of these times, for both realworld executions and simulated executions. To further validate the accuracy of our simulation results, we apply Kolmogorov-Smirnov goodness of fit tests (KS tests) with null hypotheses (H 0 ) that the real-world and simulation samples are drawn from the same distributions. The two-sample KS test results in a miss if the null hypothesis (two-sided alternative hypothesis) is rejected at 5% significance level (p-value ≤ 0.05). Each test for which the null hypothesis is not rejected (p-value > 0.05), indicates that the simulated execution statistically matches the realworld execution. Table 1 shows p-value and KS test distance for both task submission times and task completion times. The null hypothesis is not rejected, and we thus conclude that simulated workflow task executions statistically match real-world executions well. These conclusions are confirmed by visually comparing ECDFs. For instance, Figure 4 shows real-world and simulated ECDFs for sample runs of Montage-2.0 on AWS-m5.xlarge, with task submission, resp. completion, date ECDFs on the left-hand, resp. right-hand, side. We observe that the simulated ECDFs ("wrench") track the real-world ECDFs ("pegasus") closely. We repeated these simulations using Work-flowSim, and found that the null hypothesis is rejected for all 3 simulation scenarios. This is confirmed visually in Figure 4, where the ECDFs obtained from the WorkflowSim simulation ("workflowsim") are far from the real-world ECDFs.
Although KS tests and ECDFs visual inspections validate that the WRENCH-simulated ECDFs match the real-world ECDFs statistically, these results do not distinguish between individual tasks. In fact, there are some discrepancies between real-world and simulated schedules. For instance, Figure 5 shows Gantt charts corresponding to the workflow executions shown in Figure 4, with the real-world execution on the lefthand side ("pegasus") and the simulated execution on the righthand side ("wrench"). Tasks executions are shown on the vertical axis, each shown as a line segment along the horizontal time axis, spanning the time between the task's start time and the task's finish time. Different task types, i.e., different executables, are shown with different colors. In this workflow, all tasks of the same type are independent and have the same priority. We see that the shapes of the yellow regions, for example, vary between the two executions. These variations are explained by implementation-dependent behaviors of the workflow scheduler. In many instances throughout workflow execution several ready tasks can be selected for execution, e.g., sets of independent tasks in the same level of the workflow. When the number of available compute resources, n, is smaller than the number of ready tasks, the scheduler picks n ready tasks for immediate execution. In most WMSs, these tasks are picked as whatever first n tasks are returned when iterating over data structures in which task objects are stored. Building a perfectly faithful simulation of a WMS would thus entail implementing/using the exact same data structures as that in the actual implementation. This could be labor intensive or perhaps not even possible depending on which data structures, languages, and/or libraries are used in that implementation. In the context of this Pegasus case study, the production implementation of the DAGMan scheduler uses a custom priority list implementation to store ready tasks, while our simulation version of it stores workflow tasks in a C++ std::map data structure indexed by task string IDs. Consequently, when the real-world scheduler picks the first n ready tasks it typically picks different tasks than those picked by its simulated implementation. This is the cause the discrepancies seen in Figure 5.
Similar to results obtained with our Pegasus simulator, we observe small (below 4%) average relative differences between actual and simulated makespans using WorkQueue for executing the SAND workflow on the Chameleon cloud platform (4th experimental scenario in Table 1). The two-sample KS tests for both task submissions and completions indicate that simulated workflow task executions statistically match real-world executions with the WorkQueue application execution framework. Figure 6 shows real-world ("workqueue") and simulated ("wrench") ECDFs of task submission, resp. completion, dates on the left-hand, resp. right-hand, side. The real-world and simulated task completion ECDFs closely match. However, for task submission dates, although the real-world and simulated ECDFs show very similar trends, the former exhibits a step function pattern while the latter does not. After investigating this inconsistency, we found that in the real-world experiments execution events are recorded in logs as jobs are generated, but not when they are actually submitted to the HTCondor pool. As a result, our ground truth is biased for task submission dates as many tasks appear to be submitted at once. An additional (small) source of discrepancy is that in the real-world execution monitoring data from the HTCondor pool is pulled at regular intervals (about 5s), while in our simulated execution there is no such delay (this delay could be added by modifying our simulator's implementation). We hypothesize that the simulated execution may actually be closer to the real-world execution than what is reported in the real-world execution logs (verifying this hypothesis would require re-engineering the actual WorkQueue implementation to improve its logging feature). More generally, the above highlights the difficulties involved in defining what constitutes a sensible ground truth and obtaining this ground truth via real-world executions.
Figure 7 shows Gantt charts corresponding to the SAND executions shown in Figure 6. In the real-world execution, we observe the same step function pattern seen in Figure 6, for the same reasons. But we also note other discrepancies between real-world and simulated executions. For instance, at the end of the real-world execution, there is a gap in the Gantt chart. This gap corresponds to tasks with sub-second durations, which are not visible due to the chart's resolution. In the real-world executions, all these tasks are submitted in sequence, hence the gap. By contrast, in the simulated execution these tasks are not submitted in sequence. The reason is exactly the same phenomenon as that observed for Pegasus in the previous section. During workflow execution there are often more ready tasks than available workers, and WorkQueue must pick some of these tasks for submissions. This is done by removing the desired number of tasks from some data structure, and, here again the real-world WorkQueue implementation and our simulation of it use different such data structures: the former uses a std::vector, while the latter uses a std::map.
Overall, the result in this and in the previous sections show that WRENCH makes it possible to accurately simulate the ex-ecution of scientific workflows on production platforms. This was demonstrated for two qualitatively different systems: the Pegasus WMS (which uses a push model to perform earlybinding of tasks to compute resources) and the WorkQueue application execution framework (which uses a pull model to perform late-binding of tasks to compute resources).
In this section, we evaluate the speed and the memory footprint of WRENCH simulations. Results with WRENCH version 1.2 were presented in the preliminary version of this work [48], while results presented in this section are obtained with version 1.4. Between these two versions a number of performance improvements were made, which explains why the results presented here are superior. About 30% of the performance gain is due to using more appropriate data structures (e.g., whenever possible replacing C++ std::map and std::set data structures by std::unordered map and std::unordered set since the latter have O(1) average case operations). About 50% of the gain is due to the removal of a data structure to keep track of all in-flight (simulated) network messages, so as to avoid memory leaks when simulating host failures. This feature is now only activated whenever simulation of host failures is done. The remaining 20% is due to miscellaneous code improvements (e.g., avoiding pass-byvalue parameters, using helper data structures to trade off space for time).
Table 2 shows average simulated makespans and simulation execution times for our 4 experimental scenarios. Simulations are executed on a single core of a MacBook Pro 3.5 GHz Intel Core i7 with 16GiB of RAM. For these scenarios, simulation times are more than 100x and up to 2500x shorter than real-world workflow executions. This is because SimGrid simulates computation and communication operations as delays computed based on computation and communication volumes using simulation models with low computational complexity.
To further evaluate the scalability of our simulator, we use a workflow generator [65] to generate representative randomized configurations of the Montage workflow with from 1, 000 up to 10, 000 tasks. We generate 5 workflow instances for each number of tasks, and simulate the execution of these generated workflow instances on 128 cores (AWS-m5.xlarge with 32 4-core nodes) using our WRENCH-based Pegasus simulator. Figure 8 shows simulation time (left vertical axis) and maximum resident set size (right vertical axis) vs. the number of tasks in the workflow. Each sample point is the average over the 5 workflow instances (error bars are shown as well). As expected, both simulation time and memory footprint increase as workflows become larger. The memory footprint grows linearly with the number of tasks (simply due to the need to store more task objects). The simulation time grows faster initially, but then linearly beyond 7,000 tasks. We conclude that the simulation scales well, making it possible to simulate very large 10,000-task Montage configurations in under 13 minutes on a standard laptop computer.
Figure 8 also includes results obtained with WorkflowSim. We find that WorkflowSim has a larger memory footprint than our WRENCH-based simulator (by a factor ∼1.41 for 10,000task workflows), and it is slower than our WRENCH-based simulator (by a factor ∼1.76 for 10,000-task workflows). In our previous work [48], WorkflowSim was faster than our WRENCH-based simulator (by a factor ∼1.81 for 10,000-task workflows), with roughly similar trends. The reason for this improvement is a set of memory management optimizations that were applied to the WRENCH implementation, and in particular for handling message objects exchanged between processes. These optimizations have significantly improved the scalability of WRENCH, and it is likely for several other optimizations are possible to push scalability further. These optimizations have also decreased the workflow simulation time significantly when compared to the earlier WRENCH release, e.g., by a factor ∼2.6 for 10,000-task workflows. Overall, our experimental results show that WRENCH not only yields accurate simulation results but also can scalably simulate the execution of large-scale complex scientific applications running on heterogeneous platforms.
In this paper, we have presented WRENCH, a simulation framework for building simulators of Workflow Management Systems. WRENCH implements high-level simulation abstractions on top of the SimGrid simulation framework, so as to make it possible to build simulators that are accurate, that can run scalably on a single computer, and that can be implemented with minimal software development effort. Via case studies for the Pegasus production WMS and WorkQueue application execution framework, we have demonstrated that WRENCH achieves these objectives, and that it favorably compares to a recently proposed workflow simulator. The main finding is that with WRENCH one can implement an accurate and scalable simulator of a complex real-world system with a few hundred lines of code. WRENCH is open source and welcomes contributors. WRENCH is already being used for several research and education projects, and Version 1.5 was released in February 2020. We refer the reader to https://wrench-project.org for software, documentation, and links to related projects.
A short-term development direction is to use WRENCH to simulate the execution of current production WMSs and application execution frameworks (as was done for Pegasus and WorkQueue in Section 4). Although we have designed WRENCH with knowledge of many such systems in mind, we expect that WRENCH APIs and abstractions will evolve once we set out to realize these implementations. Another development direction is the implementation of more CI service abstractions in WRENCH, e.g., a Hadoop Compute Service, specific distributed cloud Storage Services. From a research perspective, a future direction is that of automated simulation calibration. As seen in our Pegasus and WorkQueue case studies, even when using validated simulation models, the values of a number of simulation parameters must be carefully chosen in order to obtain accurate simulation results. This issue is not confined to WRENCH, but is faced by all distributed system simulators. In our case studies, we have calibrated these parameters manually by analyzing and comparing simulated and real-world execution event traces. While, to the best of our knowledge, this is the typical practice, what is truly needed is an automated calibration method. Ideally, this method would process a (small) number of (not too large) real-world execution traces for "training scenarios", and compute a valid and robust set of calibration parameter values. An important research question will then be to understand to which extent these automatically computed calibrations can be composed and extrapolated to scenarios beyond the training scenarios.