Henri Casanova
email: henric@hawaii.edu

Suraj Pandey
email: surajp@hawaii.edu

James Oeth
email: oeth@isi.edu

Ryan Tanaka
email: ryanyt@hawaii.edu

Frédéric Suter
email: frederic.suter@cc.in2p3.fr

Rafael Ferreira Da Silva

WRENCH: A Framework for Simulating Workflow Management Systems

Keywords: Scientific Workflows, Workflow Management Systems, Simulation, Distributed Computing

Scientific workflows are used routinely in numerous scientific domains, and Workflow Management Systems (WMSs) have been developed to orchestrate and optimize workflow executions on distributed platforms. WMSs are complex software systems that interact with complex software infrastructures. Most WMS research and development activities rely on empirical experiments conducted with full-fledged software stacks on actual hardware platforms. Such experiments, however, are limited to hardware and software infrastructures at hand and can be labor-and/or time-intensive. As a result, relying solely on realworld experiments impedes WMS research and development. An alternative is to conduct experiments in simulation.

In this work we present WRENCH, a WMS simulation framework, whose objectives are (i) accurate and scalable simulations; and (ii) easy simulation software development. WRENCH achieves its first objective by building on the SimGrid framework. While SimGrid is recognized for the accuracy and scalability of its simulation models, it only provides low-level simulation abstractions and thus large software development efforts are required when implementing simulators of complex systems. WRENCH thus achieves its second objective by providing highlevel and directly re-usable simulation abstractions on top of SimGrid. After describing and giving rationales for WRENCH's software architecture and APIs, we present a case study in which we apply WRENCH to simulate the Pegasus production WMS. We report on ease of implementation, simulation accuracy, and simulation scalability so as to determine to which extent WRENCH achieves its two above objectives. We also draw both qualitative and quantitative comparisons with a previously proposed workflow simulator.

I. INTRODUCTION

Scientific workflows have become mainstream in support of research and development activities in numerous scientific domains [START_REF] Taylor | Workflows for e-Science: scientific workflows for grids[END_REF]. Consequently, several Workflow Management Systems (WMSs) have been developed [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF]- [START_REF] Albrecht | Makeflow: A portable abstraction for data intensive computing on clusters, clouds, and grids[END_REF] 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 [START_REF] Vydyanathan | Toward optimizing latency under throughput constraints for application workflows on clusters[END_REF], [START_REF] Benoit | Optimizing latency and reliability of pipeline workflow applications[END_REF], throughput [START_REF] Gu | Maximizing workflow throughput for streaming applications in distributed environments[END_REF], [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[END_REF], jitter [START_REF] Chen | Temporal dependency-based checkpoint selection for dynamic verification of temporal constraints in scientific workflow systems[END_REF], reliability [START_REF] Kandaswamy | Fault tolerance and recovery of scientific workflows on computational grids[END_REF]- [START_REF] Chen | Dynamic and fault-tolerant clustering for scientific workflows[END_REF], power consumption [START_REF] Fard | A multi-objective approach for workflow scheduling in heterogeneous environments[END_REF], [START_REF] Pietri | Energy-constrained provisioning for scientific workflow ensembles[END_REF]). 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?"). Realworld experiments, especially when large-scale, 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. Realworld 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 [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF]- [START_REF] Carothers | ROSS: A High-Performance, Low Memory, Modular Time Warp System[END_REF]. Some simulation frameworks have also been developed specifically for the scientific workflow domain [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[END_REF], [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF]- [START_REF] Cao | GridFlow: Workflow Management for Grid Computing[END_REF].

We claim that advances in simulation capabilities in the field have made it possible to simulate WMSs that execute large workflows on large-scale platforms accessible via diverse CI services 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 [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF], [START_REF]The SimGrid Project[END_REF], which has been one of the drivers of the above advances and whose simulation models have been extensively validated [START_REF] Bedaride | Toward Better Simulation of MPI Applications on Ethernet/TCP Networks[END_REF]- [START_REF] Lèbre | Adding Storage Simulation Capacities to the SimGrid Toolkit: Concepts, Models, and API[END_REF], to develop a WMS simulation framework called WRENCH [START_REF]The WRENCH Project[END_REF]. More specifically, this work makes the following contributions:

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 a case study with the Pegasus [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF] production WMS, we evaluate the ease-of-use, accuracy, and scalability of WRENCH, and compare it with a previously proposed simulator, WorkflowSim [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF]. This paper is organized as follows. Section II discusses related work. Section III outlines the design of WRENCH and describes how its APIs are used to implement simulators. Section IV presents our case study. Finally, Section V concludes with a brief summary of results and a discussion of future research directions.

II. RELATED WORK

Many simulation frameworks have been developed for parallel and distributed computing research and development. They span domains such as HPC [START_REF] Tikir | PSINS: An Open Source Event Tracer and Execution Simulator for MPI Applications[END_REF]- [START_REF] Bagrodia | Parallel Simulation of Large-Scale Parallel Applications[END_REF], Grid [START_REF] Bell | OptorSim -A Grid Simulator for Studying Dynamic Data Replication Strategies[END_REF]- [START_REF] Ostermann | Dynamic Cloud Provisioning for Scientific Grid Workflows[END_REF], Cloud [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF]- [START_REF] Kecskemeti | DISSECT-CF: A simulator to foster energy-aware scheduling in infrastructure clouds[END_REF], Peer-to-peer [START_REF] Montresor | PeerSim: A Scalable P2P Simulator[END_REF], [START_REF] Baumgart | OverSim: A Flexible Overlay Network Simulation Framework[END_REF], or Volunteer Computing [START_REF] Taufer | SimBA: A Discrete Event Simulator for Performance Prediction of Volunteer Computing Projects[END_REF]- [START_REF] Kondo | SimBOINC: A Simulator for Desktop Grids and Volunteer Computing Systems[END_REF]. Some frameworks have striven to be applicable across some or all or the above domains [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF], [START_REF] Carothers | ROSS: A High-Performance, Low Memory, Modular Time Warp System[END_REF]. 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 [START_REF]The ns-3 Network Simulator[END_REF], on cycle-accurate CPU simulation [START_REF] León | Instruction-Level Simulation of a Cluster at Scale[END_REF] or emulation for computation). In this case, the scalability challenge can be handled by using Parallel Discrete Event Simulation [START_REF] Fujimoto | Parallel Discrete Event Simulation[END_REF], 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 [START_REF] Velho | On the Validity of Flow-level TCP Network Models for Grid and Cloud Simulations[END_REF].

A number of simulators have been developed that target scientific workflows. Some of them are stand-alone simulators [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[END_REF], [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF]- [START_REF] Tsai | Pewss: A platform of extensible workflow simulation service for workflow scheduling research[END_REF]. Others are integrated with a particular WMS to promote more faithful simulation and code reuse [START_REF] Ostermann | Integration of an Event-Based Simulation Framework into a Scientific Workflow Execution Environment for Grids and Clouds[END_REF], [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF] or to execute simulations at runtime to guide on-line scheduling decisions made by the WMS [START_REF] Cao | GridFlow: Workflow Management for Grid Computing[END_REF].

The authors in [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF] 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 [START_REF] Hirales-Carbajal | A Grid simulation framework to study advance scheduling strategies for complex workflow applications[END_REF], [START_REF] Tsai | Pewss: A platform of extensible workflow simulation service for workflow scheduling research[END_REF], [START_REF] Cao | GridFlow: Workflow Management for Grid Computing[END_REF]. But it is also the case with workflow simulators built on top of generic simulation frameworks that provide convenient userlevel abstractions but fail to model the details of the underlying infrastructure, e.g., the simulators in [START_REF] Malawski | Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[END_REF], [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF], [START_REF] Ostermann | Integration of an Event-Based Simulation Framework into a Scientific Workflow Execution Environment for Grids and Clouds[END_REF], which build on the CloudSim [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF] or GroudSim [START_REF] Ostermann | Dynamic Cloud Provisioning for Scientific Grid Workflows[END_REF] frameworks. These frameworks have been shown to lack in their network modeling capabilities [START_REF] Velho | On the Validity of Flow-level TCP Network Models for Grid and Cloud Simulations[END_REF]. 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 [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF] the authors have improved the network model in GroudSim and also use a separate simulator, DISSECT-CF [START_REF] Kecskemeti | DISSECT-CF: A simulator to foster energy-aware scheduling in infrastructure clouds[END_REF], for simulating cloud infrastructures accurately. Both [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF] and [START_REF] Kecskemeti | DISSECT-CF: A simulator to foster energy-aware scheduling in infrastructure clouds[END_REF] acknowledge that the popular SimGrid [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF], [START_REF]The SimGrid Project[END_REF] 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 laborintensive. In this work, we address this issue by developing a simulation framework that provides convenient, reusable, high-level abstractions but that builds on SimGrid so as to benefit from its scalable and accurate simulation models. Furthermore, unlike [START_REF] Ostermann | Integration of an Event-Based Simulation Framework into a Scientific Workflow Execution Environment for Grids and Clouds[END_REF], [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF], we do not focus on integration with any specific WMS. The argument in [START_REF] Kecskemeti | Fostering Energy-Awareness in Simulations Behind Scientific Workflow Management Systems[END_REF] is that standalone simulators, such as that in [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF], 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 a case study with the Pegasus WMS [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF].

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 [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF], [START_REF] Matha | Simulation of a workflow execution as a real Cloud by adding noise[END_REF]. These techniques can be adopted by most of the aforementioned frameworks, including the one proposed in this work.

III. WRENCH A. Objective and Intended Users

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 III-D) 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 III-E), 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.

B. Software Architecture Overview

Figure 1 depicts WRENCH's software architecture. At the bottom layer is the Simulation Core, which simulates low-level software and hardware stacks using the simulation abstractions and models provided by SimGrid (see Section III-C). 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 implementations, so as to capture specifics of currently available CI services used in production. For instance, in its current version WRENCH provides a "batch-scheduled cluster" compute service, a 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 III-D). 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. One such project is the simulated Pegasus implementation for our case study in Section IV. 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 III-E). Here again, these simulators are not part of WRENCH, but implemented as stand-alone projects.

C. Simulation Core

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 [START_REF] Bobelin | Scalable Multi-Purpose Network Representation for Large Scale Distributed System Simulation[END_REF].

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 [START_REF] Bedaride | Toward Better Simulation of MPI Applications on Ethernet/TCP Networks[END_REF]- [START_REF] Lèbre | Adding Storage Simulation Capacities to the SimGrid Toolkit: Concepts, Models, and API[END_REF], and its simulation models have been shown to provide compelling advantages over other simulation frameworks in terms of both accuracy and scalability [START_REF] Casanova | Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms[END_REF]. 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 II), SimGrid is the only one to offer all the above desirable characteristics.

D. WRENCH Developer API

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. Then, if desired, the WMS can submit pilot jobs [START_REF] Turilli | A Comprehensive Perspective on Pilot-Job Systems[END_REF] to compute services that support them, if any (line 6). 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 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 process analyze the workflow and to interact with CI services to execute the workflow. These methods were designed based on current and envisioned capabilities of current state-of-the-art WMSs. We refer the reader to the WRENCH Web site [START_REF]The WRENCH Project[END_REF] 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 higher-level simulation abstractions meaning that distributed systems must be implemented essentially from scratch, with many message-based interactions. All message-based communication 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 control. 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 database of pending requests, provides a simple API to check on the status of these requests, and automatically generates 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 nontrivial 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 but 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 Pegasus case study (Section IV).

E. WRENCH User API

With the User API one can quickly build a simulator, which typically follows these steps:

1 The above steps can be implemented with only a few lines of C++. An example WRENCH simulator is shown in Figure 2, which uses a WMS implementation (called SomeWMS) that has already been developed using the WRENCH Developer API (see previous section). After initializing the simulation (lines 5-6), the simulator instantiates a platform (line 8) and a workflow (line 10-11). A workflow is defined as a set of computation tasks and data files, with control and data dependencies between tasks. Each task can also have a priority, which can then be taken into account by a WMS for scheduling purposes. Although the workflow can be defined purely programmatically, in this example the workflow is imported from a workflow description file in the DAX format [START_REF]Pegasus' DAX Workflow Description Format[END_REF]. At line 13 the simulator creates a storage service with 1PiB capacity accessible on host storage_host. This and other hostnames are specified in the XML platform description file. At line 17 the simulator creates a compute service that corresponds to a 4-node batch-scheduled cluster. The physical characteristics of the compute nodes (node [START_REF] Taylor | Workflows for e-Science: scientific workflows for grids[END_REF][START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF][START_REF] Fahringer | Askalon: A development and grid computing environment for scientific workflows[END_REF][START_REF] Wilde | Swift: A language for distributed parallel scripting[END_REF]) are specified in the platform description file. This compute service has a 1TiB scratch storage space. Its behavior is customized by passing a couple of property-value pairs to its constructor. It will be subject to a background load as defined by a trace in the standard SWF format [START_REF]The Standard Workload Format[END_REF], and its batch queue will be managed using the EASY Backfilling scheduling algorithm [START_REF] Lifka | The ANL/IBM SP Scheduling System[END_REF]. The simulator then creates a second compute service (line 22), which is a 4-host cloud service, customized so that it does not support pilot jobs. Two helper services are instantiated, a data registry service so that the WMS can keep track of file locations (line 26) and a network monitoring service that uses the Vivaldi algorithm [START_REF] Dabek | Vivaldi: A Decentralized Network Coordinate System[END_REF] to measure network distances between the two hosts from which the compute services are accessed (batch_login and cloud_gateway) and the my_host host, which is the host that runs these helper services and the WMS (line 28). At line 34, the simulator specifies that the workflow data file input_file is initially available at the storage service. It then instantiates the WMS and passes to it all available services (line 36), and assigns the workflow to it (line 39). The crucial call is at line 41, where the simulation is launched and the simulator hands off control to WRENCH. When this call returns the workflow has either completed or failed. Assuming it has completed, the simulator then retrieves the ordered set of task completion events (line 43) and performs some (in this example, trivial) mining of these events (line 45). For brevity, the example in Figure 2 omits try/catch clauses. Also, note that although the simulator uses the new operator to instantiate WRENCH objects, the simulation object takes ownership of these objects (using unique or shared pointers), so that there is no memory deallocation onus placed on the user. This example showcases only the most fundamental features of the WRENCH User API, and we refer the reader to the WRENCH Web site [START_REF]The WRENCH Project[END_REF] 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.

IV. CASE STUDY: SIMULATING A PRODUCTION WMS

In this section, we present a WRENCH-based simulator of a state-of-the-art WMS, Pegasus [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF], as a case study 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 [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF]. 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 [START_REF] Frey | Condor dagman: Handling inter-job dependencies[END_REF]. Individual workflow tasks are managed by a workload management framework, HTCondor [START_REF] Thain | Distributed computing in practice: the condor experience[END_REF], which supervises task executions on local and remote resources.

A. Implementing Pegasus with WRENCH

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 will be included in the next WRENCH release 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 Condor 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, all 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 IV-B).

The simulator code, details on the simulation calibration procedure, and experimental scenarios used in the rest of this section are all publicly available online [START_REF]The WRENCH Pegasus Simulator[END_REF].

B. Experimental Scenarios

We consider experimental scenarios defined by particular workflow instances to 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 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 [START_REF] Ferreira Da Silva | Using simple pid controllers to prevent and mitigate faults in scientific workflows[END_REF]: 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 diseaserelated mutations. We consider a 1000Genome instance that comprises 71 tasks. • Montage [START_REF] Deelman | Pegasus: a Workflow Management System for Science Automation[END_REF]: A compute-intensive astronomy workflow 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. We use these platforms, deploying on each a submit node (which runs Pegasus, DAGMan, and HTCondor's job submission and central manager services), four worker nodes (4 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.

C. Simulation Accuracy

To evaluate the accuracy of our simulator, we consider 3 particular experimental scenarios: 1000Genome on ExoGENI, Montage-1.5 on AWS-t2.xlarge, and Montage-2.0 on AWS-m5.xlarge. Each execution is repeated 5 times and the overall workflow execution times, or makespans, are recorded.

The third column in Table I shows average relative differences between actual and simulated makespans. We see that simulated makespans are close to actual makespans across the board (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, e.g., these models capture many features of the TCP protocol. And indeed, when comparing real-world and simulated executions we observe average relative error below 3% for data movement operations. The many processes involved in a workflow execution with Pegasus interact by exchanging (typically small) control messages. Our simulator simulates these interactions. 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 overhead due to a message exchange. When comparing real-world to simulated executions we observe average relative simulation error below 1% for these data registration overheads.

To draw comparisons with a state-of-the-art simulator, we repeated the above simulations using WorkflowSim [START_REF] Chen | WorkflowSim: A Toolkit for Simulating Scientific Workflows in Distributed Environments[END_REF]. WorkflowSim does not provide a detailed simulated HTCondor implementation, does not offer the same simulation calibration capabilities as WRENCH, and is built on top of the CloudSim simulation framework [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF]. Nevertheless, we have painstakingly calibrated our WorkflowSim simulator so that it models the hardware and software infrastructures of our experimental scenarios as closely as possible. For each of the 3 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 II) and thus suffers from simulation bias w.r.t. data transfer times. Second, WorkflowSim does not capture all the relevant details of the system and its execution. By contrast, implementing a fully detailed simulator with WRENCH can be done in 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 real-world 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 real-world execution. Table I 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 ECFDs. 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. righthand, side. We observe that the simulated ECDFs ("wrench") track the real-world ECDFs ("pegasus") closely. We repeated these simulations using WorkflowSim, 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 right-hand 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 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. Core i7 with 16GiB of RAM. For these scenarios, simulation times are more than 100x and up to 2500x shorter than realworld 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.

D. Simulation Scalability

To evaluate the scalability of our simulator, we use a workflow generator [START_REF] Ferreira Da Silva | Community resources for enabling and evaluating research on scientific workflows[END_REF] 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 4core nodes). Figure 6 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 40 minutes on a standard laptop computer.

Figure 6 also includes results obtained with WorkflowSim. We find that WorkflowSim has a larger memory footprint than our WRENCH-based simulator (by a factor ∼1.48 for 10,000task workflows). However, WorkflowSim is faster than our WRENCH-based simulator (by a factor ∼1.81 for 10,000task workflows), with roughly similar trends. The reason why WorkflowSim is faster is because it simply does not simulate many aspects of the execution. The downside, as seen in the previous section, is that its simulation results are inaccurate.

V. CONCLUSION

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 a case study for the Pegasus production WMS 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 realworld 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.1 was released in August 2018. We refer the reader to http://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 (as was done for Pegasus in Section IV). Although we have designed WRENCH with knowledge of these WMSs and with the intent of making their implementations with WRENCH feasible, 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 case study, 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 study 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.

Fig. 1 :

 1 Fig. 1: The four layers in the WRENCH architecture from bottom to top: simulation core, simulated core services, simulated WMS implementations, and simulators.

Algorithm 1

 1 Blueprint for a WMS execution 1: procedure MAIN(workf low) while workf low execution has not completed/failed do

Fig. 2 :

 2 Fig. 2: Example fully functional WRENCH simulator. Try-catch clauses are omitted.

Fig. 3 :

 3 Fig. 3: Overview of the WRENCH Pegasus simulation components, including components for DAGMan and HTCondor frameworks. Red boxes denote Pegasus services developed with WRENCH's Developer API, and white boxes denote WRENCH reused components.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Empirical cumulative distribution function of task submit times (left) and task completion times (right) for sample real-world ("pegasus") and simulated ("wrench" and "workflowsim") executions of Montage-2.0 on AWS-m5.xlarge.

Fig. 6 :

 6 Fig. 6: Average simulation time (in seconds. left vertical axis) and memory usage (maximum resident set size, right vertical axis) in MiB vs. workflow size.

TABLE I :

 I Average simulated makespan error (%), and p-values and Kolmogorov-Smirnov (KS) distances for task submission and completion dates, computed for 5 runs of each of our 3 experimental scenarios.

  TableIIshows average simulated makespans and simulation execution times for our 3 experimental scenarios. Simulations are executed on a single core of a MacBook Pro 3.5 GHz Intel

	Experimental Scenario	Avg. Workflow Avg. Simulation
	Workflow	Platform	Makespan (s)	Time (s)
	1000Genome	ExoGENI	761.0 ±7.93	0.3 ±0.01
	Montage-1.5	AWS-t2.xlarge 1,784.0 ±137.67	8.3 ±0.09
	Montage-2.0 AWS-m5.xlarge	2,911.8 ±48.80	28.1 ±0.52

TABLE II :

 II Simulated workflow makespans and simulation times averaged over 5 runs of each of our 3 experimental scenarios.

Acknowledgments. This work is funded by NSF contracts #1642369 and #1642335, "SI2-SSE: WRENCH: A Simulation Workbench for Scientific Worflow Users, Developers, and Researchers", and by CNRS under grant #PICS07239. We thank Martin Quinson, Arnaud Legrand, and Pierre-Franc ¸ois Dutot for their valuable help.


Rachid Riad
email: riadrachid3@gmail.com

Corentin Dancette
email: corentin.dancette@gmail.com

Julien Karadayi
email: julien.karadayi@gmail.com

Neil Zeghidour
email: neil.zeghidour@gmail.com

Thomas Schatz
email: thomas.schatz.1986@gmail.com

Emmanuel Dupoux
email: emmanuel.dupoux@gmail.com

Sampling strategies in Siamese Networks for unsupervised speech representation learning

Keywords: language acquisition, speech recognition, sampling, Zipf's law, weakly supervised learning, unsupervised learning, Siamese network, speech embeddings, ABX, zero resource speech technology

Recent studies have investigated siamese network architectures for learning invariant speech representations using samedifferent side information at the word level. Here we investigate systematically an often ignored component of siamese networks: the sampling procedure (how pairs of same vs. different tokens are selected). We show that sampling strategies taking into account Zipf's Law, the distribution of speakers and the proportions of same and different pairs of words significantly impact the performance of the network. In particular, we show that word frequency compression improves learning across a large range of variations in number of training pairs. This effect does not apply to the same extent to the fully unsupervised setting, where the pairs of same-different words are obtained by spoken term discovery. We apply these results to pairs of words discovered using an unsupervised algorithm and show an improvement on state-of-the-art in unsupervised representation learning using siamese networks.

Introduction

Current speech and language technologies based on Deep Neural Networks (DNNs) [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF] require large quantities of transcribed data and additional linguistic resources (phonetic dictionary, transcribed data). Yet, for many languages in the world, such resources are not available and gathering them would be very difficult due to a lack of stable and widespread orthography [START_REF] Adda | Breaking the unwritten language barrier: The bulb project[END_REF].

The goal of Zero-resource technologies is to build speech and language systems in an unknown language by using only raw speech data [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF]. The Zero Resource challenges (2015 and 2017) focused on discovering invariant sub-word representations (Track 1) and audio terms (Track 2) in an unsupervised fashion. Several teams have proposed to use terms discovered in Track 2 to provide DNNs with pairs of same versus different words as a form of weak or self supervision for Track 1: correspondence auto-encoders [START_REF] Kamper | Unsupervised neural network based feature extraction using weak topdown constraints[END_REF][START_REF] Renshaw | A comparison of neural network methods for unsupervised representation learning on the zero resource speech challenge[END_REF], siamese networks [START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF][START_REF] Zeghidour | A deep scattering spectrumdeep siamese network pipeline for unsupervised acoustic modeling[END_REF].

This paper extends and complements the ABnet Siamese network architecture proposed by [START_REF] Synnaeve | Phonetics embedding learning with side information[END_REF][START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF] for the sub-word modelling task. DNN contributions typically focus on novel architectures or objective functions. Here, we study an often overlooked component of Siamese networks: the sampling procedure which chooses the set of pairs of same versus different to-kens. To assess how each parameter contributes to the algorithm performance, we conduct a comprehensive set of experiments with a large range of variations in one parameter, holding constant the quantity of available data and the other parameters. We find that frequency compression of the word types has a particularly important effect. This is congruent with other frequency compression techniques used in NLP, for instance in the computation of word embeddings (word2vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]). Besides, Levy et al. [START_REF] Levy | Improving distributional similarity with lessons learned from word embeddings[END_REF] reveals that the performance differences between wordembedding algorithms are due more to the choice of the hyperparameters, than to the embedding algorithms themselves.

In this study, we first show that, using gold word-level annotations on the Buckeye corpus, a flattened frequency range gives the best results on phonetic learning in a Siamese network. Then, we show that the hyper-parameters that worked best with gold annotations yield improvements in the zero-resource scenario (unsupervised pairs) as well. Specifically, they improve on the state-of-the-art obtained with siamese and auto-encoder architectures.

Methods

We developed a new package abnet3 1 using the pytorch framework [START_REF] Paszke | Automatic differentiation in pytorch[END_REF]. The code is open-sourced (BSD 3-clause) and available on github, as is the code for the experiments for this paper 2 .

Data preparation

For the weakly-supervised study, we use 4 subsets of the Buckeye [START_REF] Pitt | The buckeye corpus of conversational speech: labeling conventions and a test of transcriber reliability[END_REF] dataset from the ZeroSpeech 2015 challenge [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF] with, respectively, 1%, 10%, 50%, and 100% of the original data (see Table 1). The original dataset is composed of American English casual conversations recorded in the laboratory, with no overlap, no speech noises, separated in two splits: 12 speakers for training and 2 speakers for test. A Voice Activity Detection file indicates the onset and offset of each utterance and enables to discard silence portions of each file. We use the orthographic transcription from word-level annotations to determine same and different pairs to train the siamese networks.

In the fully unsupervised setting, we obtain pairs of same and different words from the Track 2 baseline of the 2015 Ze-roSpeech challenge [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF]: the Spoken Term Discovery system from [START_REF] Jansen | Towards spoken term discovery at scale with zero resources[END_REF]. We use both the original files from the baseline, and a rerun of the algorithm with systematic variations on its For the speech signal pre-processing, frames are taken every 10ms and each one is encoded by a 40 log-energy Melscale filterbank representing 25ms of speech (Hamming windowed), without deltas or delta-delta coefficients. The input to the Siamese network is a stack of 7 successive filterbank frames. The features are mean-variance normalized per file, using the VAD information.

ABnet

A Siamese network is a type of neural network architecture that is used for representation learning, initially introduced for signature verification [START_REF] Bromley | Signature verification using a" siamese" time delay neural network[END_REF]. It contains 2 subnetworks sharing the same architecture and weights. In our case, to obtain the training information, we use the lexicon of words to learn an embedding of speech sounds which is more representative of the linguistic properties of the signal at the sub-word level (phoneme structure) and invariant to non-linguistic ones (speaker ID, channel, etc). A token t is from a specific word type w (ex: "the","process" etc.) pronounced by a specific speaker s. The input to the network during training is a pair of stacked frames of filterbank features x1 and x2 and we use as label y = 1({w1 = w2}). For pairs of identical words, we realign them at the frame level using the Dynamic Time Warping (DTW) algorithm [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]. Based on the alignment paths from the DTW algorithm, the sequences of the stacked frames are then presented as the entries of the siamese network. Dissimilar pairs are aligned along the shortest word, e.g. the longest word is trimmed. With these notions of similarity, we can learn a representation where the distance between the two outputs of the siamese network e(x1) and e(x2) try to respect as much as possible the local constraints between x1 and x2. To do so, ABnet is trained with the margin cosine loss function:

lγ(x1, x2, y) = -cos(e(x1), e(x2)), if y = 1 max(0, cos(e(x1), e(x2)) -γ), otherwise
For a clear and fair comparison between the sampling procedures we fixed the network architecture and loss function as in [START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF]. The subnetwork is composed of 2 hidden layers with 500 units, with the Sigmoid as non-linearity and a final embedding layer of 100 units. For regularization, we use the Batch Normalization technique [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF], with a loss margin γ = 0.5. All the experiments are carried using the Adam training procedure [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] and early-stopping on a held-out validation set of 30% of spoken words. We sample the validation set in the same way as the training set.

Sampling

The sampling strategy refers to the way pairs of tokens are fed to the Siamese network. Sampling every possible pairs of tokens becomes quickly intractable as the dataset grows (cf. Table 1).

There are four different possible configurations for a pair of word tokens (t1, t2) : whether, or not, the tokens are from the same word type, w1 = w2. and whether, or not, the tokens are pronounced by the same speaker, s1 = s2.

Each specific word type w is characterized by the total number of occurrences nw it has been spoken in the whole corpus. Then, is deduced the frequency of appearances fw ∝ nw, and rw its frequency rank in the given corpus. We want to sample a pair of word tokens, in our framework we sample independently these 2 tokens. We define the probability to sample a specific token word type w as a function of nw. We introduce the function φ as the sampling compression function:

P(w) = φ(nw) ∀w φ(n w ) (1)
When a specific word type w is selected according to these probabilities, a token t is selected randomly from the specific word type w. The usual strategy to select pairs to train siamese networks is to randomly pick two tokens from the whole list of training tokens examples [START_REF] Bromley | Signature verification using a" siamese" time delay neural network[END_REF][START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF][START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF]. In this framework, the sampling function corresponds φ : n → n. Yet, there is a puzzling phenomenon in human language, there exists an empirical law for the distribution of words, also known as the Zipf's law [START_REF] Zipf | The psycho-biology of language[END_REF]. Words types appear following a power law relationship between the frequency fw and the corresponding rank rw: a few very high-frequency types account for almost all tokens in a natural corpus (most of them are function words such as "the","a","it", etc.) and there are many word types with a low frequency of appearances ("magret","duck","hectagon"). The frequency ft of type t scales with its corresponding rt following a power law, with a parameter α depending on the language:

fw ∝ 1 r α w , α ≈ 1
One main effect on the training is the oversampling of word types with high frequency, and this is accentuated with the sampling of two tokens for the siamese. These frequent, usually monosyllabic, word types do not carry the necessary phonetic diversity to learn an embedding robust to rarer co-articulations, and rarer phones. To study and minimize this empirical linguistic trend, we will examine 4 other possibilities for the φ function that compress the word frequency type:

φ : n → 2 √ n, φ : n → 3 √ n φ : n → log(1 + n), φ : n → 1
The first two options minimize the effect of the Zipf's Law on the frequency, but the power law is kept. The log option removes the power law distribution, yet it keeps a linear weighting as a function of the rank of the types. Finally with the last configuration, the word types are sampled uniformly.

Another important variation factor in speech realizations is the speaker identity. We expect that the learning of speech representations to take advantage of word pairs from different speakers, to generalize better to new ones, and improve the ABX performance. Buckeye-100%). The siamese loss is such that "Same" pairs are brought together in embedding space, and "Different" pairs are pulled apart. Should we reflect this statistic during the training, or eliminate it by presenting same and different pairs equally?

We manipulate systematically the proportion of pairs from different word types fed to the network:

P w -=
#Sampled pairs with non-matching word types #Sampled pairs

Evaluation with ABX tasks

To test if the learned representations can separate phonetic categories, we use a minimal pair ABX discrimination task [START_REF] Schatz | Evaluating speech features with the minimal-pair abx task: Analysis of the classical mfc/plp pipeline[END_REF][START_REF] Schatz | Evaluating speech features with the minimal-pair abx task (ii): Resistance to noise[END_REF]. It only requires to define a dissimilarity function d between speech tokens, no external training algorithm is needed. We define the ABX-discriminability of category x from category y as the probability that A and X are further apart than B X when A and X are from category x and B is from category y, according to a dissimilarity function d. Here, we focus on phone triplet minimal pairs: sequences of 3 phonemes that differ only in the central one ("beg"-"bag", "api"-"ati", etc.). For the within-speaker task, all the phones triplets belong to the same speaker (e.g. A = begT 1 , B = bagT 1 , X = bag T 1 ) Finally the scores for every pair of central phones are averaged and subtracted from 1 to yield the reported within-talker ABX error rate. For the across-speaker task, A and B belong to the same speaker, and X to a different one (e.g. A = begT 1 , B = bagT 1 , X = bag T 2 ). The scores for a given minimal pair are first averaged across all of the pairs of speakers for which this contrast can be made. As above, the resulting scores are averaged over all contexts over all pairs of central phones and converted to an error rate.

Results

Weakly supervised Learning

Sampling function φ

We first analyze the results for the sampling compression function φ Figure 1. For all training datasets, we observe a similar pattern for the performances on both tasks: the word frequency compression improves the learning and generalization. The result show that, compared to the raw filterbank features baseline, all the trained ABnet networks improve the scores on the phoneme discrimination tasks, even in the 1% scenario. Yet, the improvement with the usual sampling scenario φ : n → n is small in all 4 training datasets. The optimal function for the within and across speaker task on all training configuration is the uniform function φ : n → 1. It yields substantial improvements over the raw filterbanks for ABX task across-speaker ( 5.6 absolute points and 16.8% relative improvement for the 1%-Buckeye training). The addition of data for these experiments improves the performance of the network, but not in a substantial way: the improvements from 1%-Buckeye to 100%-Buckeye, for φ : n → 1, is 1.9 absolute points and 7.9% relative. These results show that using frequency compression is clearly beneficial, and surprisingly adding more data is still advantageous but not as much as the choice of φ. Renshaw et al. [START_REF] Renshaw | A comparison of neural network methods for unsupervised representation learning on the zero resource speech challenge[END_REF], found similar results with a correspondence auto-encoder, training with more training data did not yield improvements for their system. We now look at the effect on the ABX performances of the proportion of pairs of words pronounced by two different speakers Figure 2. We start from our best sampling function configuration so far φ : n → 1. We report on the graph only the two extreme training settings. The variations for the 4 different training splits are similar, and still witness a positive effect with additional data on the siamese network performances. Counterintuitively, the performances on the ABX tasks does not take advantage of pairs from different speakers. It even shows a tendency to increase the ABX error rate: for the 100%-Buckeye we witness an augmentation of the ABX error-rate (2.9 points and 11.6% relative) between P s -= 0 and P s -= 1. One of our hypothesis on this surprising effect, might be the poor performance of the DTW alignment algorithm directly on raw filterbanks features of tokens from 2 different speakers.

Proportion of pairs with different word types P w -

We next study the influence of the proportion of pairs from different word types P w -Figure 3. In all training scenarios, to privilege either only the positive or the negative examples is not the solution. For the different training splits, the optimal number for P w -is either 0.7 or 0.8 in the within and across speaker ABX task. We do not observe a symmetric influence of the positive and negative examples, but it is necessary to keep the same and different pairs. The results collapsed, if the siamese network is provided only with positive labels to match: the network will tend to map all speech tokens to the same vector point Now, we transfer the findings about sampling from the weakly supervised setting, to the fully unsupervised setting. We report in Table 2 our results for the two ZeroSpeech 2015 [START_REF] Versteegh | The zero resource speech challenge 2015[END_REF] corpus: the same subset of the Buckeye Corpus as earlier and a subset of the NCHLT corpus of Xitsonga [START_REF] De Vries | A smartphone-based asr data collection tool for under-resourced languages[END_REF]. To train our siamese networks, we use as [START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF], the top-down information from the baseline for the Track 2 (Spoken Term Discovery) of the ZeroSpeech 2015 challenge from [START_REF] Jansen | Towards spoken term discovery at scale with zero resources[END_REF]. The resulting clusters are not perfect, whereas we had perfect clusters in our previous analysis. In Thiolière et al. [START_REF] Thiolliere | A hybrid dynamic time warping-deep neural network architecture for unsupervised acoustic modeling[END_REF] the sampling is done with : P w -= P s -= 0.5, and φ = n → n. This gives us a baseline to compare our sampling method improvements with our own implementation of siamese networks.

First, the "discovered" clusters -obtained from spoken term discovery system -don't follow the Zipf's law like the gold clusters. This difference of distributions diminishes the impact of the sampling compression function φ.

We matched state-of-the-art for this challenge only on the ABX task within-speaker for the Buckeye, otherwise the modified DPGMM algorithm proposed by Heck et al. stays the best submissions for the 2015 ZeroSpeech challenge.

Spoken Term discovery -DTW-threshold δ

Finally, we study the influence of the DTW-threshold δ used in the spoken discovery system on the phonetic discriminability of siamese networks. We start again from our best finding from weakly supervised learning. The clusters found by the Jansen et al. [START_REF] Jansen | Towards spoken term discovery at scale with zero resources[END_REF] system are very sensitive to this parameter with a tradeoff between the Coverage and the Normalized Edit Distance (NED) introduced by [START_REF] Ludusan | Bridging the gap between speech technology and natural language processing: an evaluation toolbox for term discovery systems[END_REF] We find that ABnet is getting good results across the various outputs of the STD system shown in Table 3 and improves over the filterbanks results in all cases. Obtaining more data with the STD system involves a loss in words quality. In contrast with the weakly supervised setting, there is an optimal tradeoff between the amount and quality of discovered words for the sub-word modelling task with siamese networks.

Conclusions and Future work

We presented a systematic study of the sampling component in siamese networks. In the weakly-supervised setting, we established that the word frequency compression had an important impact on the discriminability performances. We also found that optimal proportions of pairs with different types and speakers are not the ones usually used in siamese networks. We transferred the best parameters to the unsupervised setting to compare our results to the 2015 Zero Resource challenge submissions. It lead to improvements over the previous neural networks architectures, yet the Gaussian mixture methods (DPGMM) remain the state-of-the-art in the phonetic discriminability task. In the future, we will study in the same systematic way the influence of sampling in the fully unsupervised setting. We will then try to leverage the better discriminability of our representations obtained with ABnet to improve the spoken term discovery, which relies on frame-level discrimination to find pairs of similar words. Besides, power law distributions are endemic in natural language tasks. It would be interesting to extend this study to other tasks (for instance, language modeling).

#

  Sampled pairs pronounced by different speakers #Sampled pairsGiven the natural statistics of the dataset, the number of possible "different" pairs exceeds by a large margin the number of possible "same" pairs (∼ 1% of all token pairs for the Gold 1% Gold 10% Gold 50% Gold

Figure 1 :

 1 Figure 1: ABX across-speaker error rates on test set with various sampling compression functions φ for the 4 different Buckeye splits used for weakly supervised training. Here, the proportions of pairs with different speakers P s -and with different word types P w -are kept fixed: P s -= 0.5, P w -= 0.5

3. 1 . 2 .

 12 Proportion of pairs from different speakers P s -

Figure 2 :

 2 Figure 2: Average ABX error rates across-speaker with various proportion pairs of different speakers P s -, with φ : n → 1 and P w -= 0.5.

Figure 3 :

 3 Figure 3: Average ABX error rates across-speaker with various proportion pairs with different word types P w -, where φ : n → 1 and P s -= 0.5

3. 2 .

 2 Applications to fully unsupervised setting 3.2.1. ZeroSpeech 2015 challenge

Table 1 :

 1 Statistics

		Duration	#tokens #words #possible pairs
	1%	3.0 min	1006	355	∼ 5.10 5
	10%	29.9 min	7189	1297	∼ 2.10 7
	50%	149.5 min	34912	3112	∼ 6.10 8
	100% 299.1 min	69543	4538	≥ 2.10 9
		for the 4 Buckeye splits used for the weakly
	supervised training, the duration in minutes expressed the total
	amount of speech for training
	similarity threshold parameter.

Table 2 :

 2 ABX discriminability results for the ZeroSpeech2015 datasets. The best error rates for each conditions for siamese architectures are in bold. The best error rates for each conditions overall are underlined.

	Models	English	Xitsonga
		within across within across
	baseline (MFCC)	15.6	28.1	19.1	33.8
	supervised topline (HMM-GMM)	12.1	16.0	04.5	03.5
	Our ABnet with P w -= 0.7, P s -= 0, φ : n → 1	10.4	17.2	9.4	15.2
	CAE, Renshaw et al. [5]	13.5	21.1	11.9	19.3
	ABnet, Thiolière et al. [6]	12.0	17.9	11.7	16.6
	ScatABnet, Zeghidour et al. [7]	11.0	17	12.0	15.8
	DPGMM Chen et al. [23]	10.8	16.3	9.6	17.2
	DPGMM+PLP+bestLDA+DPGMM Heck et al. [24]	10.6	16.0	8.0	12.6

Table 3 :

 3 ]. Number of found clusters, NED, Coverage, ABX discriminability results with our ABnet with P w -= 0.7, P s -= 0, φ : n → 1, for the ZeroSpeech2015 Buckeye for various DTW-thresholds δ in the Jansen et al.[START_REF] Jansen | Towards spoken term discovery at scale with zero resources[END_REF] STD system. The best results for each metric are in bold.

	δ	#clusters NED Coverage ABX across
	0.82	27,770	0.792	0.541	18.2
	0.83	27,758	0.792	0.541	18.1
	0.84	27,600	0.789	0.541	18.4
	0.85	26,466	0.76	0.54	18.4
	0.86	22,627	0.711	0.527	18.2
	0.87	16,108	0.569	0.485	18.2
	0.88	9,853	0.442	0.394	17.7
	0.89	5,481	0.309	0.282	17.6
	0.90	2,846	0.228	0.182	17.9
	0.91	1,286	0.179	0.109	18.6
	0.92	468	0.179	0.058	19.2

Acknowledgements

The team's project is funded by the European Research Council (ERC-2011-AdG-295810 BOOTPHON), the Agence Nationale pour la Recherche (ANR-10-LABX-0087 IEC, ANR-10-IDEX-0001-02 PSL* ), Almerys (industrial chair Data Science and Security), Facebook AI Research (Doctoral research contract), Microsoft Research (joint MSR-INRIA center) and a Google Award Grant.