Fernando Chirigati

Vítor Silva

Eduardo Ogasawara

Daniel De Oliveira

Jonas Dias

Fábio Porto

Patrick Valduriez
email: patrick.valduriez@inria.fr

Marta Mattoso

Evaluating Parameter Sweep Workflows in High Performance Computing *

Keywords: H.4.1 [Information Systems Applications]: Workflow management. H.2.8 [Database Management]: Scientific. I.6.7 [Simulation and Modeling]: Simulation Support Systems Environments Measurement, Performance, Experimentation Scientific Workflows, Execution Model, Parameter Sweep, High Performance Computing (HPC)

Scientific experiments based on computer simulations can be defined, executed and monitored using Scientific Workflow Management Systems (SWfMS). Several SWfMS are available, each with a different goal and a different engine. Due to the exploratory analysis, scientists need to run parameter sweep (PS) workflows, which are workflows that are invoked repeatedly using different input data. These workflows generate a large amount of tasks that are submitted to High Performance Computing (HPC) environments. Different execution models for a workflow may have significant differences in performance in HPC. However, selecting the best execution model for a given workflow is difficult due to the existence of many characteristics of the workflow that may affect the parallel execution. We developed a study to show performance impacts of using different execution models in running PS workflows in HPC. Our study contributes by presenting a characterization of PS workflow patterns (the basis for many existing scientific workflows) and its behavior under different execution models in HPC. We evaluated four execution models to run workflows in parallel. Our study measures the performance behavior of small, large and complex workflows among the evaluated execution models. The results can be used as a guideline to select the best model for a given scientific workflow execution in HPC. Our evaluation may also serve as a basis for workflow designers to analyze the expected behavior of an HPC workflow engine based on the characteristics of PS workflows.

INTRODUCTION 1

#

Many scientific experiments are based on computer simulations.

There is now a growing use of scientific workflows to organize and manage these experiments. Workflows can be characterized as models of processes, composed of activities and their dependencies [START_REF] Van Der Aalst | Workflow Management: Models, Methods, and Systems[END_REF]. Scientific workflows are data-centric workflows that represent scientific experiments as graphs, where nodes correspond to activities and edges correspond to data being passed between activities. Activities invoke scientific programs that prepare, process and analyze scientific data.

Scientific workflows are typically defined, executed and monitored by Scientific Workflow Management Systems (SWfMS) [START_REF] Deelman | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF][START_REF] Mattoso | Towards Supporting the Life Cycle of Large-scale Scientific Experiments[END_REF]. Currently, several SWfMS are available, e.g. Taverna [START_REF] Hull | Taverna: a tool for building and running workflows of services[END_REF], Kepler [START_REF] Altintas | Kepler: an extensible system for design and execution of scientific workflows[END_REF], VisTrails [START_REF] Callahan | VisTrails: visualization meets data management[END_REF], Pegasus [START_REF] Gil | Wings for Pegasus: Creating Large-Scale Scientific Applications Using Semantic Representations of Computational Workflows[END_REF], and Swift [START_REF] Zhao | Swift: Fast, Reliable, Loosely Coupled Parallel Computation[END_REF]. Each SWfMS supports its own language for expressing workflows and it is backed by a well-defined execution model. As a result of such heterogeneity, the execution of a scientific workflow presents distinguishable behaviors when run by different SWfMS.

An important characteristic of scientific workflows is their focus on data intensive processing. A typical example is the iterative evaluation of a workflow over different input parameter values, known as parameter sweep [START_REF] Walker | Challenges in executing large parameter sweep studies across widely distributed computing environments[END_REF]. In some scenarios, the space of parameter values may be as large as thousands of elements. In this context, in order to produce results in a reasonable time, a High Performance Computing (HPC) environment is needed. Some SWfMS, such as Pegasus, Swift and Chiron, provide support for HPC environments [START_REF] Ogasawara | Chiron: Scientific Workflow Engine[END_REF]. Others, due to restrictions on their execution engines, need to be combined with a specialized HPC middleware, e.g. MapReduce [START_REF] Dean | MapReduce: a flexible data processing tool[END_REF] and Hydra [START_REF] Ogasawara | Exploring many task computing in scientific workflows[END_REF].

All of these parallel execution engines need to choose the best model for a given scientific workflow execution in HPC. When it comes to data-intensive execution on HPC environments, more aspects, such as data transfer methods, have to be taken into account by the workflow engine.

A typical distributed or parallel database query optimizer considers different combinations of algorithms and data transfer methods before designing the execution plan [START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. For example, when optimizing the execution of two joins, it can ship the entire relation produced by the first join to the next or the second join can fetch tuples as needed and the two joins will execute in a parallel pipeline model.

In a similar way, the workflow execution engine optimizer can choose the data transfer method, among several, from waiting for all data to be generated by the first activity to be entirely sent to the next activity, or to starting the second activity as the first generates its partial results in a pipeline execution model. This pipeline depends on the constraints of the application, but it is often possible to choose between different options. Kepler allows for the workflow designer to choose the execution model while selecting a director for the workflow. However, choosing between the data transfer execution models is not simple for the workflow designer in data-intensive workflows. Even when the choice is made by the optimizer of the workflow execution engine, it is difficult to predict the performance behavior. If this decision is static, i.e. made before the execution begins, and fixed for the whole workflow it may lead to poor performance.

To address this problem, we developed a study to measure and compare the performance of different execution models in running parameter sweep (PS) workflows. As PS workflows may follow different patterns [START_REF] Russell | Workflow control-flow patterns: A revised view[END_REF] and workflow activities may have different characteristics and execution times, our study defines five PS workflow patterns. These PS workflow patterns are evaluated using metrics that are focused on workflow execution time. Besides the design of the PS workflow patterns, we have also developed a data generator tool to fully recreate PS workflow scenarios. It creates input data for all PS workflow patterns based on two independent variables that can be used to characterize the size and complexity of the scientific experiment.

Our experimental study aims to evaluate the behavior of PS workflows on four different execution models we implemented. These models are related to parallel tasks dispatching strategies over computing resources. It is possible to make an analogy between each evaluated execution model and classical datatransfer methods such as MapReduce or pipeline execution models. In our experimental evaluation, we were able to measure performance differences of distinct execution models to execute variations of scientific workflows. We were also able to measure the scalability of the evaluated execution models.

The paper is organized as follows. Section 2 gives some background on the different targets of computational environments. In Section 3, a characterization of scientific workflow activities is presented in detail. Section 4 describes the design of our study. Section 5 shows the experimental evaluation. Section 6 presents related work. Section 7 concludes the paper.

COMPUTATIONAL ENVIRONMENT

When we evaluate PS workflows in HPC, there are different characteristics of the computational environment that need to be taken into account. The performance of a workflow execution model in HPC may vary significantly under different environments, which may lead to unfair comparisons. Concerning our research, we are interested in HPC environments, such as clusters, grids [START_REF] Foster | The Grid: Blueprint for a New Computing Infrastructure[END_REF] and clouds [START_REF] Vaquero | A break in the clouds: towards a cloud definition[END_REF]. However, in this paper, we focus on cluster systems with distributed memory and shared disk storage -a very common architecture in many research centers.

Clusters are usually a set of homogeneous computing nodes connected through a high speed and low latency network. On a distributed memory cluster, each processor has its own private memory. The communication between processes is done through message passing such as MPI [START_REF] Gropp | Using MPI -2nd Edition: Portable Parallel Programming with the Message Passing Interface[END_REF]. Too much communication may present an overhead. However, in the PS workflow scenario, each process (or task) executes an instance of a workflow activity using a given combination of parameters. Thus, the processes usually do not share or exchange data, so there would be no communication between processes. In contrast, on a shared memory system, processes share a single memory space. They can take advantage of the single memory space to communicate, reading and writing shared parameters in the memory. PS workflow cannot take too much advantage of shared memory system because their processes usually do not exchange data.

PS workflow activities can be distributed through a scheduler and executed in parallel by several nodes of a cluster to speed up execution time. Distributed memory systems need very efficient scheduling and dispatching mechanisms to improve task distribution [START_REF] Raicu | Many-task computing for grids and supercomputers[END_REF] that should take advantage of stable and homogeneous characteristics of the cluster to improve the execution performance. Data storage and access may also impact the performance of the execution model when executing scientific workflows. Considering the data storage options, clusters can deploy either shared-nothing or shared-disk architectures [START_REF] Bouganim | Dynamic load balancing in hierarchical parallel database systems[END_REF]. A shared-nothing architecture relies on exclusive access to local disks. The data is split through the environment nodes that can only access its data partition. In shared-disk, all nodes share the same disk space.

CHARACTERIZATION OF PS WORKFLOWS

A scientific workflow is a data-centric workflow composed of a set of activities. Activities execute programs that consume and produce data (parameters values and files). An output data produced by an activity can be consumed as input data to another activity, establishing a dependency relation between those activities. The workflow engine executes workflow activities respecting their dependency order. During the execution of an experiment, scientists explore the behavior of their workflow model under different inputs. A common problem in scientific experiments is to run a scientific workflow many times as a parameter sweep. In these scenarios, we usually have a set of input data, which may be consumed and transformed by many activities to produce a final set of output data for the entire experiment. Consequently, each activity of a workflow is executed repeatedly by consuming elements of the set of the input data to produce elements of the set of output data. Figure 1 shows an example of a PS workflow representation, where S is the set of input data consumed by the workflow, R is the produced set of output data, and s i and r i are, respectively, elements of the set of input data and elements of the set of output data. Activity A consumes a particular s i , produces data u i that is consumed by activity B, and activity B produces data v i that is consumed by activity C to produce r i .

As PS workflows run activities repeatedly, it is important to characterize activities by the way in which they consume and produce data [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF][START_REF] Provchallenge | Provenance Challenge Wiki[END_REF]. In this scenario, activities can be interpreted as functions that transform data according to a particular ratio of consumption/production [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF][START_REF] Provchallenge | Provenance Challenge Wiki[END_REF]. Under this criterion, we consider four basic types of activities (Map, Split Map, Reduce and Join). Activities that execute a Map function (Figure 2a) are the ones that produce a single output data for each input data consumed, i.e. with an input/output ratio of 1:1. Activities that execute a Split Map function (Figure 2b) are the ones that produces a set of output data for each input data, i.e. with an input/output ratio of 1:n. Activities that execute Reduce function (Figure 2c) are the ones that produce a single output data from a set of input data, i.e. with an input/output ratio of n:1. Finally, activities that execute Join function (Figure 2d) are the ones that consume a set of data that may come from a fixed set of m different activities to produce a single set of output data, i.e. with an input/output ratio of n:n. Furthermore, it is important to characterize patterns that are presented in many PS workflows, i.e., characterize the way in which the aforementioned types of activities are commonly combined. Although we do not intend to entirely cover all possible PS scientific workflows, it is possible to observe five PS workflow patterns (Sequence, Thread Split, Thread Merge, Parallel Split and Synchronization) that are present in many real PS workflows, such as in Provenance Challenges Workflows [START_REF] Provchallenge | Provenance Challenge Wiki[END_REF], Computational Fluid Dynamics (CFD) [START_REF] Ogasawara | Exploring many task computing in scientific workflows[END_REF], Bioinformatics [START_REF] González-Vélez | A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers[END_REF][START_REF] Callaghan | Metrics for heterogeneous scientific workflows: A case study of an earthquake science application[END_REF], ultra-deep-water oil exploitation [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF], algorithmic skeletons [START_REF] González-Vélez | A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers[END_REF] and characterization papers [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF][START_REF] Coutinho | Many task computing for orthologous genes identification in protozoan genomes using Hydra[END_REF]. These PS workflow patterns are related to previously characterized workflow patterns [START_REF] Russell | Workflow control-flow patterns: A revised view[END_REF] and we use the same notation as described in this work. previous Maps produce all output data, the Reduce activity is then executed, consuming all input data at once and producing its single output data. Another relevant pattern is the Parallel Split pattern (WP-2) (Figure 3d), which corresponds to a broadcast of the output of a particular Map to n different following Map activities, i.e., the following n activities receives a copy of the same output data, and these activities may execute concurrently. Finally, in the Synchronization pattern (WP-3) (Figure 3e), the input data comes from n different types of Map activities and joined to produce a set of output data. The synchronization pattern requires synchronism, i.e. the Join activity only executes when its set of input data is ready to be consumed. In Figure 4, we illustrate two real PS workflows characterized and composed according to the type of activity (Map, SplitMap, Reduce, Join). The OrthoMCL workflow (Figure 4a) [START_REF] Coutinho | Many task computing for orthologous genes identification in protozoan genomes using Hydra[END_REF] provides a scalable method for identifying orthologous groups regarding genome evolution. The Risers Fatigue Analysis workflow, or simply RFA workflow (Figure 4b) [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF], aims at computing the fatigue of risers, tubular structures that are used to pump oil from ultra-deep-water of the ocean to the surface. In both workflows, it is possible to observe the presence of the proposed workflow patterns and type of activities.

EVALUATION STUDY DESIGN

Workflow engine designers may want to know which execution model provides the best performance for executing their scientific workflow in a particular computational environment. Typically, a PS workflow is repeatedly executed by exploring different combinations of input data (parameters and files). Therefore, choosing an adequate execution model may lead to an economy in scale. The workflow execution performance may considerably vary according to different parallelization strategies and different computational environments. The goal of our study is to establish a reference for performance comparison between four different execution models for PS workflow execution. Besides, it aims to be reproducible so that other workflow optimizers may adequate the study to their models of execution.

Workload Configuration

We introduce the workflow workload configuration by discussing the independent variables of our study, named scaling factors.

The scaling factors allow us to customize the workload of our PS workflow patterns to make it representative of different types of scientific experiments. Scaling factors are represented as integer values that characterize the complexity of activities and the size of input parameter space. The parameter space involves the parameters sets to be explored in the parameter sweep like shown on Figure 5. In our study, parameter sets are identified by a key parameter k i and each parameter set is consumed by an instance of a given activity A, for example. The parameter sweep involves the execution of the same activity for each parameter set. Changes in scaling factors influence the cardinality of the parameter space and the parameter values that specifies the duration of the activity. Thus, the factors may significantly affect the performance of PS workflow execution. Table 1 shows the description of scaling factors.

Figure 5. Parameter space consumption by an activity of a workflow

ISF is the scaling factor responsible for defining the number of times the workflow is executed using different input data, i.e., the cardinality of the input parameter space. The cardinality is defined as 2 ISF + 8 , for ISF 1. This arbitrary definition creates parameter spaces with at least 512 (2 9 ) input parameter sets. ACF is a positive integer value that is related to the duration (in seconds) of the activities. The duration of each activity follows a Gamma distribution (, ), where = 2 ACF and = 1, for ACF 1.

Gamma distribution is commonly used to represent expected queue time, which makes it convenient to represent also the duration of activities.

While ISF is used to generate the right amount of data for the parameter space for each PS workflow pattern, the ACF is used to specify the duration of the activities.

Table 1. The scaling factors used in the study.

Variable Description

Instance Scale Factor (ISF)

Integer value that defines the cardinality of the input parameter space for the PS workflow.

Activity Cost Factor (ACF)

Integer value that defines a basis to specify the duration of the activity execution.

PS Workflow Patterns

Representative PS workflow patterns can be executed with different types of activity. They correspond to building blocks in PS workflows, which, once executed, stress the workflow engine.

Figure 6. Map PS workflow pattern

We designed five PS workflow patterns that refer directly to the five patterns defined in Section 3. We used four different activities: M, S, R, and J. PS workflow patterns are designed as combinations of these activities. Activity M is related to the Map function, consuming a single input data to produce a single output data. The S type is related to the Split Map function and fragments the input data into several output data. The R type is related to Reduce function and aggregates several input data into a single output data. Activity J is related to the Join function. Our PS workflow patterns focus on activities that are data-centric and computational intensive.

Figure 7. Broadcast PS workflow pattern

Map PS workflow pattern (Figure 6) represents a sequential flow of activities, based on the WP-1 pattern (Figure 3a). It is a fundamental building block for workflows [START_REF] Russell | Workflow control-flow patterns: A revised view[END_REF] and can be found in several of them [START_REF] Bharathi | Characterization of scientific workflows[END_REF], thus becoming an essential part to be considered by our study. It defines activities that are sequenced, i.e., one activity is executed once the previous one has been completed. This flow of activities is executed for each input parameter set identified by k i in the parameter space. In Figure 6, each input parameter set identified by k i contains the parameters ta i and tb i that indicates the duration of the activities M A and M B , respectively, related to the ACF value. The remaining parameter p represents a random value that is consumed by activity M A , which produces an output pa that is later consumed by M B .

Figure 8. Split Map PS workflow pattern

Broadcast (Figure 7) and Split Map (Figure 8) PS workflow patterns are based on the WP-2 (Figure 3d) and the WP-42 (Figure 3b) patterns, respectively. They are important as they increase the number of data that need to be processed in PS workflows [START_REF] Bharathi | Characterization of scientific workflows[END_REF], which is particularly significant when considering HPC environments. In Figure 7, each output data produced by activity M C is broadcasted, i.e., replicated in branches to the following activities: M D and M E . Again, the parameters tc, td and te are related to ACF and indicate the duration for activities M C , M D and M E , respectively. The input parameter space also contains the input random parameter p that is consumed by activity M C to create the output pc, which is later broadcasted. In Figure 8, each parameter value xf of activity S F (outer for each) is decomposed, or fragmented, into multiple smaller data (x ff ), which are consumed by activity M G (inner for each). Activity S F also produces the parameter tg that indicates the duration for the activity M G based on the chosen ACF value.

Figure 9. Join PS workflow pattern

Join (Figure 9) and Reduce (Figure 10) PS workflow patterns are based on the WP-3 pattern (Figure 3e) and the WP-41 (Figure 3c) respectively. In the Join PS workflow pattern, activities M H and M I are executed for each parameter set in their respective input parameter space. Activity J J is responsible for combining their sets of output data into a single set according to a given criteria. Differently from the Join PS workflow pattern, in Reduce PS workflow pattern, multiple output data (pl i ) of the same activity M L are combined into a single output data in reduce activity R M . In other words, a single output data in R M is produced for each subset of M L 's output data. These PS workflow patterns are important because they may represent a reduction in the number of data that need to be processed by PS workflows [START_REF] Bharathi | Characterization of scientific workflows[END_REF].

The proposed PS workflow patterns specify the design of the workflows in our evaluation study, using the scaling factors defined in the workload configuration to setup their execution. ACF is used to specify the duration of the activities, given by the parameters starting with t in Figure 6 to Figure 10. Besides, the ISF factor is used to generate the right amount of data for the input parameter space for each PS workflow pattern. After generating the input data, running a PS workflow pattern includes the execution of activities (M, S, J or R) using the correct parameters. To simplify the command line execution, each activity of the PS workflow patterns can be invoked using a particular Java program. Since there are four activity types, we developed four Java programs named M.jar, S.jar, J.jar and R.jar. They require a small fingerprint to be used (more specifically, the ability to run Java programs). The syntax to invoke the activities programs varies according to the type of activity (M, S, J or R) and also includes their parameters values. Table 2 shows the input and output parameters for each program and their command line syntax. The activity program M.jar receives three input parameters. The k parameter is the key of the parameter set in the parameter space. The t parameter is the duration of the activity associated to the ACF factor and finally p i is the random value that flows across the workflow. The activity program S.jar receives only the key parameter k and the file to be fragmented indicated by parameter x f . The activity program J.jar receives two files as input parameters j a and j b and creates a new file j o . The activity J is characterized as a n:n data consumption/production ratio function, thus it consumes two datasets to join them on a single parameter space using their keys to combine them. As previously mentioned, the parameter spaces are stored as CSV files, thus activity J consumes two CSV files to produce a single one. The activity program R.jar receives the input files r i to be reduced to the single output value v. The program R.jar executes a sum of all values of p found inside the input file r i .

Depending on the execution model being evaluated, it may be interesting to use a native Join or Reduce function to perform these operations instead of using activity programs J.jar or R.jar. Using a native function would give more accurate and fair results for the given model. For example, when using Hadoop, scientists can program Hadoop Reduce function to execute activity program R instead of using R.jar.

Performance Metrics

We divide performance metrics into four metrics, all of them related to the execution time of PS workflows. Table 3 presents metrics used in our evaluations.

The two main metrics for comparison are Elapsed Time (T E ) and Score (S E ). T E is the elapsed time to run the workflow using the input data. Score is computed as the sum of the Efficiency (E) result from each PS workflow pattern. The score aims to be a simple value that can be used to compare different execution models. Table 4 shows the formulas for each metric. The Speedup (S) is computed as a division between the time of the sequential execution (T 1 ) and the time of the parallel execution (T E ).

The efficiency E is computed as S/p, where p is the number of cores. The score metric, S E , is computed as the average of the results for efficiency E x for each PS workflow pattern x. The speedup, the efficiency and the score are metrics used to measure the performance for PS workflow patterns. In this way, the metric S E supports the comparison between different execution models, considering all PS workflow patterns.

Although we propose these given metrics related to execution time, we believe that a broader study regarding the best metrics to evaluate PS workflows, similar to what was done is [START_REF] Callaghan | Metrics for heterogeneous scientific workflows: A case study of an earthquake science application[END_REF], is necessary. We leave this for future work.

Table 3. Evaluation metrics used in the study

Metric Description

Elapsed Time (T E ) Total workflow execution time (in minutes).

Speedup (S)

Value that corresponds to the equivalent sequential execution time over the parallel execution time.

Efficiency (E)

Value between 0 and 1 that represents how efficient the available cores are used to execute the workflow.

Score (S E )

Metric used to define the performance of the execution model considering all PS workflow patterns.

Table 4. Metrics and their formulas used in the study

Metric Formula

Speedup (S)

Efficiency (E) Score (S E )

EXPERIMENTAL EVALUATION

In order to evaluate PS workflows using different execution models, we implemented four distinct models to execute the experimental study on top of Chiron workflow engine. The execution models use different task dispatching and workflow orchestration strategy. Each different execution model resembles a different HPC approach. Thus, the main purpose of this study is to evaluate the performance differences between these four execution models in a high performance computing cluster with shared disk storage.

To achieve our main goal, we performed four analyses. The first used small scaling factors to check if the results would show differences in performance even using small input parameter spaces and short-term activities. The second analysis increases ACF to see how it impacts the results. The third analysis uses the Map PS workflow pattern to evaluate the scalability of the four execution models and the fourth analysis evaluates the efficiency of the models for four different scaling factors configuration fixing the number of cores. The computational environment used during the experiments is a SGI Altix ICE 8200 distributed memory shared-disk cluster with 32 nodes, each one with 2 quadcore processors and 8 GB of memory. The cluster runs GNU/Linux 2.6.32.12-0.7 x86_64.

The four implemented execution models are the combination of two variable characteristics: task dispatching and workflow data transfer orchestration strategy. The task dispatching strategy can be static (STA) or dynamic (DYN). Static means that the model sends bags of tasks to the working processors, which need to process all the tasks in the bag before asking for new tasks. The dynamic strategy sends one task at a time as the working processors becomes idle. Static and dynamic strategies had already been studied before [START_REF] Yu | A Taxonomy of Workflow Management Systems for Grid Computing[END_REF][START_REF] Prodan | Dynamic scheduling of scientific workflow applications on the grid: a case study[END_REF][START_REF] Pautasso | Parallel computing patterns for Grid workflows[END_REF]. The second characteristic, the workflow data transfer orchestration strategy, can vary from First Activity First (FAF) to First Tuple First (FTF) [START_REF] Ogasawara | An Algebraic Approach for Data-Centric Scientific Workflows[END_REF]. FAF means that all the task of the first activity needs to be processed (i.e. all its data generated) before the start of the second activity, and so on. FTF, though, lets the PS workflow run in parallel on a pipeline fashion, running the tasks as any part of their input data becomes available. The FAF characteristic can be related to Intra-Operator Parallelism in parallel database systems while FTF can be related to Inter-Operator Parallelism [START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. The combination of Static, Dynamic, FAF and FTF characteristics creates the four execution models as seen in Table 5.

Table 5. Execution models

Static Dynamic

First Activity First STA_FAF DYN_FAF

First Tuple First STA_FTF DYN_FTF

The STA_FAF resembles a MapReduce approach combined with a general SWfMS (e.g., VisTrails). DYN_FAF model is similar to a traditional SWfMS combined with a specialized HPC middleware Nimrod/K [START_REF] Abramson | Nimrod/K: towards massively parallel dynamic grid workflows[END_REF]). STA_FTF is similar to pipeline DAG workflow schedulers, such as Pegasus [START_REF] Deelman | Pegasus: Mapping Large-Scale Workflows to Distributed Resources[END_REF], while DYN_FTF is more similar to SWfMS, such as Swift [START_REF] Zhao | Swift: Fast, Reliable, Loosely Coupled Parallel Computation[END_REF].

Although we are not using different tools for each different execution model, our objective is to evaluate the behavior of PS workflows execution raising differences between those execution models. These differences evidence the need of a workflow engine that supports different execution models and an optimizer that can choose the model according to the PS workflow scaling factors.

Figure 12. Evaluation results using ACF=1 and ISF=1

In our first analysis, we considered the smallest possible scaling factor for the PS workflow patterns, considering both ACF=1 and ISF=1. These factors generated 512 input parameters for each PS workflow pattern, with activities that take an average of 2 seconds to be processed. The purpose of this analysis is to evaluate if it is possible to raise performance differences even for small datasets and short-term activities. We measured the execution time for all PS workflow patterns using 8, 16, 32, 64 and 128 cores. Then, we computed the score for each execution model as the average of the efficiency of each PS workflow pattern execution. The results are shown on Figure 12. To make the charts clearer we are showing data labels for the execution models with best and the worst performance. In this case, we depict the labels for STA_FTF that got the best performance and for DYN_FAF that got the worst.

Figure 13. Evaluation results for ACF=6 and ISF=1

The decrease in the score as we increase the number of cores is expected due to the small quantity of parallel tasks per PS workflow pattern and the short-term activities. The two static execution models performed slightly better than the dynamic ones, when it comes to the average efficiency of the parallelism (score). However, differences in total execution time between the two approaches in some specific cases are more than twenty five percent. This is interesting to observe because, since we have short-term tasks, it is more efficient to dispatch bags of tasks often than to dispatch one task at a time repeatedly. The static models reduce the communication overhead to transmit task over the working nodes. The FTF model also performed better than FAF. This is reasonable because it reduces the time the working nodes wait to obtain new tasks, since they do not need to wait until a given activity finished to obtain tasks from the next activity.

Figure 14. Average speedup for the Map PS workflow pattern

In the second analysis, we used ACF=6 and ISF=1. This scenario evaluates the impact of the activity cost. Using ACF=6, the average duration of an activity would be around 64 seconds. The results are shown on Figure 13. Again, we used the score metric as the average of the efficiency of each PS workflow pattern execution. Data labels are shown for the DYN_FTF and STA_FAF execution models. The overall score decreases and we see that dynamic models are more efficient than static ones. This is expected since dynamic models are more flexible and reduce the idleness of working nodes, sending new tasks as they need, providing a working load balance.

The first two analyses showed how we could present performance differences between the execution models. Also, varying the scale factor produces differences in the results, as desired. It is possible to manipulate the scaling factors ACF and ISF to evaluate an execution model according to the characteristics of an experiment. Additionally, the results may reflect the behavior of the model under a given computational environment.

The third analysis aims at evaluating the scalability of the execution models. We have used a single PS workflow pattern, i.e. a workflow that is a combination of Map patterns. This is interesting because it checks if a single PS workflow pattern is capable of revealing the most suitable execution model to use on a specific workflow pattern. For this third analysis, we used four combinations of ACF and ISF as presented in Table 6. The results present the average speedup for each execution model and are shown on Figure 14. To maintain the clarity of the graph, we are showing error bars only for the worst and best results. All execution models scale well but the speed degrades specially after 64 cores. This may be due to the small size of the input parameter space, i.e., there are too many cores to process and not so many input data. This scenario reduces efficiency since it increases idleness in the working nodes. This is reinforced by the fact that the dynamic models performed better, since their dispatching strategy aims at reducing the overall idleness of the execution.

The DYN_FTF is especially good in this scenario since there is almost no waits to dispatch a new task. The last analysis uses the same configuration of ACF and ISF described in Table 6. However the number of cores is fixed to 32 since the previous analysis showed it is the configuration that best suits the chosen scaling factors. Besides, this analysis aims at evaluating the score of each parallel execution model for each individual combination of ACF and ISF, so we can have a deeper look at their impact on the execution models. The results are shown on Figure 15. The dynamic models are the more efficient parallel execution models for all given scenarios since it is the most flexible model, naturally reducing the idleness in the working nodes. Differences in score between the evaluated execution models are up to 14%. Also, we see that greater ACF or ISF are the targets of parallel computing thus more efficient. This is reasonable since the cost benefit of dynamic distribution and communication overhead does not pay for small quantity of shortterm tasks.

Our evaluation was capable of performing different types of analysis regarding what parallel execution model best suits different experiment characteristics. It offers an overview of the behavior of the models using a given ACF and ISF as we performed in our first and second analysis. It was also possible to evaluate the speedup of the execution models for a specific PS workflow pattern of greater interest, like we did in the third analysis. It is also possible to make a deeper investigation varying ACF and ISF for all PS workflow patterns to check their impact on the score of the execution models on a set of cores of the computing environment.

With this study we evaluated the behavior of PS workflow using different execution models in an HPC cluster with shared disk storage. The study shows that, in general, the DYN_FTF execution model is the most efficient parallel execution model in most situations. However, if the PS workflow deals with shortterm activities, it may be interesting to use a static model to reduce task-dispatching overhead. FTF models also tend to be more efficient than FAF in most situations although sometimes they present very close performance results. Besides, we noticed considerable elapsed time differences between the models when running different combinations of ACF and PS workflow patterns. Thus it may be more interesting to have all execution models available in the workflow engine. Scientists and workflow designers can use this study as a preliminary analysis to choose the best execution model to run their specific workflows in parallel. Indeed, our evaluation study design is a step towards a benchmark for PS workflows. More information about this project can be found in the Scientific Workflow Benchmark home page [32]. [START_REF] Bharathi | Characterization of scientific workflows[END_REF] describes basic workflow structures that are composed into complex scientific workflows, providing a characterization of workflows and presenting several real scientific applications. However, they do not present an evaluation using their workflow patterns on different execution models in order to measure their performance behavior. Other studies [START_REF] Thain | Pipeline and batch sharing in grid workloads[END_REF][START_REF] Ostermann | On the Characteristics of Grid Workflows[END_REF] evaluate workloads to characterize different types of workflows in grid infrastructures but also do not present different comparison metrics nor evaluations using different execution models. The work by Gillman et al. [START_REF] Gillmann | Benchmarking and Configuration of Workflow Management Systems[END_REF] proposes a benchmark that specifies an ecommerce workflow, in order to stress the components of a Workflow Management System. Despite the fact that our study and Gillman's benchmark share some principles of measuring the performance of execution model approaches, their work is related to business workflows, i.e. more control-centric, considering structures such as conditional branching. Our focus is on PS workflows, i.e. data-centric workflows, which may involve longterm activities.

The work of Vassiliadis et al. [START_REF] Vassiliadis | Towards a Benchmark for ETL Workflows[END_REF] propose a unified way to construct and measure the efficiency and the effectiveness of Extraction-Transform-Load (ETL) workflows. They are centered in ETL processes, proposing a principled organization of workflow patterns for this scenario. Goderis et al. [START_REF] Goderis | Seven Bottlenecks to Workflow Reuse and Repurposing[END_REF] introduce a study in the field of scientific workflow discovery, to identify the practice and attitudes of scientists. From this study, they establish three benchmarks, focused on the requirements of semantic workflow discovery tools. They do not stress different execution models to evaluate the performance of workflow execution though. Another interesting initiative is the Yahoo! Cloud Serving Benchmark (YCSB) [START_REF] Cooper | Benchmarking Cloud Serving Systems with YCSB[END_REF]. It aims at facilitating performance comparisons between cloud data serving systems and it is restricted to cloud computing environments. Besides, it is not related to PS workflows; it aims at a more generic performance evaluation for data transactions over the cloud.

There are also several tools for HPC that can be used for performance comparisons. The LINPACK benchmark [START_REF] Petitet | HPL -A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers Available at[END_REF] aims at measuring the performance of an HPC environment by solving various systems of linear equations, and the results are mainly reported through the amount of floating point operations per second. A portable implementation of this benchmark, HPL, is used in the TOP500 project, which ranks and details supercomputers. The NAS Parallel Benchmarks (NPB) [START_REF] Bailey | The Nas Parallel Benchmarks[END_REF] comprises a set of benchmarks for the performance evaluation of highly parallel supercomputers. These benchmarks consist of five parallel kernels and three pseudo-applications, in order to simulate the computation and the data movement characteristics of computational fluid dynamics applications. Both HPL and NAS are designed to stress HPC environments to measure their performance. However, their applications are not suitable for PS workflows since they are not designed for parameter exploration experiments. They also do not show different parallel workflow execution models. We can also find in the literature some work with regard to MapReduce systems, such as MRBench [START_REF] Kim | MRBench: A Benchmark for MapReduce Framework[END_REF] and HiBench [START_REF] Huang | The HiBench benchmark suite: Characterization of the MapReduce-based data analysis[END_REF]. It is important to notice, however, that these initiatives intend to measure the performance of HPC architectures, and not the performance of execution models to execute PS workflow in HPC, which is our focus. Additionally, we observed that PS workflows might have different performance in the same architecture, which reinforces the need for PS evaluations on different parallel execution models.

CONCLUSION

In this paper, we studied the behavior of typical PS workflows to provide a reference for workflow engine designers or optimizers in identifying the most suitable execution model. We defined five PS workflow patterns and four types of activities based on workflow typical characterizations. Each PS workflow pattern corresponds to a specific workflow pattern and can be used to evaluate the performance of different parallel execution models under different distributed computing environments such as clusters, grids or clouds. This way, the results reveal the probable behavior of PS workflows when using the evaluated execution model, helping to identify the most adequate model for different scenarios.

To validate our proposal, we used the designed PS workflow patterns to evaluate and compare four execution models on a shared-disk HPC cluster. The main goal of our study is to identify variations in performance of these four different execution models. Our first two analyses detected performance differences for small datasets with both short-term and long-term activities.

Our third analysis measured the scalability of the execution models on a specific PS workflow pattern and the last analysis had a deeper look on the behavior of the execution models for different combinations of the scaling factors ACF and ISF.

Overall, the results show that dynamic execution models are more suitable for most PS workflow executions. However, static execution models are more efficient when dealing with short-term activities. Besides, static execution models tend to provide better performance, due to its simplicity. Considering that most PS workflows need HPC, the proposed study can be used as a basis for selecting the best execution model for a given PS workflow. Additionally, our study is a step towards a benchmark specially designed for the evaluation of PS workflow execution performance, particularly in HPC.

Figure 1 .

 1 Figure 1. PS workflows

Figure 2 .

 2 Figure 2. Activities with data consumption and production: Map (a); Split Map (b); Reduce (c); Join (d)

Figure 3 .

 3 Figure 3. Workflow patterns mapped in PS workflows: WP-1 (a); WP-42 (b); WP-41(c); WP-2(d); WP-3(e)The Sequence pattern (WP-1) (Figure3a) corresponds to a sequence of Map activities, i.e., a Map activity is enabled after the completion of the preceding Map activity. The Thread Split pattern (WP-42) (Figure3b) corresponds to a sequence of SplitMap and Map activities. The input data for the SplitMap activity generates a set of output data. Each element of this output data is individually consumed by the Map activity further down the workflow. The Thread Merge pattern (WP-41) (Figure3c) corresponds to a sequence of Map and Reduce activities. When previous Maps produce all output data, the Reduce activity is then executed, consuming all input data at once and producing its single output data. Another relevant pattern is the Parallel Split pattern (WP-2) (Figure3d), which corresponds to a broadcast of the output of a particular Map to n different following Map activities, i.e., the following n activities receives a copy of the same output data, and these activities may execute concurrently. Finally, in the Synchronization pattern (WP-3) (Figure3e), the input data comes from n different types of Map activities and joined to produce a set of output data. The synchronization pattern requires synchronism, i.e. the Join activity only executes when its set of input data is ready to be consumed.

Figure 4 .

 4 Figure 4. OrthoMCL (a) and RFA (b) workflows

Figure 10 .

 10 Figure 10. Reduce PS workflow pattern 4.3 Running PS Workflow Patterns After configuring the workload, i.e. the desired values for ACF and ISF, two more steps are necessary to run the PS workflow patterns: generating input data using the data generator tool and executing, in fact, the PS workflow patterns. Each PS workflow pattern involves running a particular PS workflow. These PS workflow patterns require a particular set of input data to produce a set of output data. The dataset generator program is responsible for creating all necessary data to execute the parameter sweep execution. In order to generate the set of input data, it is necessary to specify the required PS workflow pattern and the values of the scaling factors (ISF and ACF).Figure 11(a) shows the input parameters generated by the program for each PS workflow pattern. For example, the input parameters generated for the Map PS workflow pattern are k, ta, tb and p. Additionally, Figure 11(b) shows an example of the generated set of input data for the Map PS workflow pattern, considering ISF=2 and ACF=1. The set of input data, i.e., the parameter space file is generated as a CSV (comma separated values) file.

  Figure 11(a) shows the input parameters generated by the program for each PS workflow pattern. For example, the input parameters generated for the Map PS workflow pattern are k, ta, tb and p. Additionally, Figure 11(b) shows an example of the generated set of input data for the Map PS workflow pattern, considering ISF=2 and ACF=1. The set of input data, i.e., the parameter space file is generated as a CSV (comma separated values) file.

Figure 11 .

 11 Figure 11. Input parameters for the PS workflow patterns cases (a) and an example for Map (b)

Figure 15 .

 15 Figure 15. Evaluation results using four combinations of ACF and ISF but fixing the number of cores6. RELATED WORKAlthough there has been much work on workflows and workloads characterization in general, to the best of our knowledge, there has been very little work focused on performance comparison on dataintensive workflows such as PS workflow. The work by Bharathi et al.[START_REF] Bharathi | Characterization of scientific workflows[END_REF] describes basic workflow structures that are composed into complex scientific workflows, providing a characterization of workflows and presenting several real scientific applications. However, they do not present an evaluation using their workflow patterns on different execution models in order to measure their performance behavior. Other studies[START_REF] Thain | Pipeline and batch sharing in grid workloads[END_REF][START_REF] Ostermann | On the Characteristics of Grid Workflows[END_REF] evaluate workloads to characterize different types of workflows in grid infrastructures but also do not present different comparison metrics nor evaluations using different execution models. The work by Gillman et al.[START_REF] Gillmann | Benchmarking and Configuration of Workflow Management Systems[END_REF] proposes a benchmark that specifies an ecommerce workflow, in order to stress the components of a Workflow Management System. Despite the fact that our study and Gillman's benchmark share some principles of measuring the performance of execution model approaches, their work is related to business workflows, i.e. more control-centric, considering structures such as conditional branching. Our focus is on PS workflows, i.e. data-centric workflows, which may involve longterm activities.

Table 2 . Command lines to invoke the activity programs used in the study

 2

	Name	Input	Output	Command line
	M.jar	k, t, p i	p o	java -jar A.jar -K=k -T=t -P=p i
	S.jar	k, x f	x ff	java -jar S.jar -K=k -X=x f
	J.jar	j a , j b	j o	java -jar J.jar -J=j a ,j b
	R.jar	r i	v	java -jar R.jar -R=r i

Table 6 . ACF and ISF values for analysis three and four

 6

	ACF 2	2	4	6
	ISF 1	2	1	1

ACKNOWLEDGMENTS

We would like to thank the High Performance Computing Center (NACAD-COPPE/UFRJ), where the experiments were executed.

* Work partially sponsored by CAPES, CNPq and INRIA (Datluge and Sarava projects).

# Currently at Polytechnic Institute of NYU.


Frédéric Rousseaux

Erwan Bocher

Antoine Gourlay

Gwendall Petit

Frederic Rousseaux

Toward a coupling between GIS and agent simulation: USM, an OrbisGIS

Keywords: urban environment, simulation, agent-based modeling, spatial analysis, GIS, opensource

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and context

The modeling of a city's evolution is one of the most exciting fields in urban studies research. The interest of such a model lies more in the past than the future: understanding how a city was made rather as opposed to how it might evolve. Such a model can necessitate expertise from numerous fields. From urban network analysis to spatial organisation and social patterning, modeling is a matter of choice. Our model simulates a set of alternative planning scenarios and urban development options. City growth reveals important issues to be taken into account in the city planning process and in territorial diagnoses, and analysis of potential alternatives is an essential step for both technicians and policy makers.

Using a spatio-dynamic urban evolution model, we discuss the implementation of agentbased modeling in an open-source geographical information system (GIS). Our model simulates the evolution of urban structures as a function of different scenarios at the city block scale in Nantes-Métropole, France.

From an agent-based paradigm to a GIS representation

A spatial simulation necessarily describes a given phenomenon and the space in which it is embedded. This description requires appropriate (and often very specialized) software. One of the main technical challenges is to link geographical information systems with simulation platforms. GIS, with the richness of related tools--geographical databases, spatial analysis, cartographic representations--are needed to realistically describe the spatial environment of the simulation, but do not possess dynamic capabilities. On the other hand, agent-based modeling platforms allow simulation of phenomena in a dynamic context but lack geographic and spatial analysis tools. Agent-based models have an individual-centric structure that identifies the active entities (the agents) and defines their behaviour, which can be influenced by interactions with other agents as well as the environment. "The environmental model is critical for the Multi-Agent System as it strongly affects the agents' decision making and behaviour." [START_REF] Schule | Coupling GIS and multi-agent simulation towards infrastructure for realistic simulation[END_REF] Coupling spatial capabilities (e.g., managing georeferenced vector data) and agent based simulation platforms (e.g., assigning behaviour and rules to geographic features) has already been implemented in open-source toolkits such as REPAST S, based on the geotools library [START_REF] North | Discovering Strategic Solutions with Agent-Based Modeling and Simulation[END_REF], GAMA [START_REF] Taillandier | GAMA: a simulation platform that integrates geographical information data, agent-based modeling and multi-scale control[END_REF], or the simpler NETLOGO [START_REF] Wilensky | NetLogo. Center for Connected Learning and Computer-Based Modeling[END_REF] and its GIS extension. In this paper, we 1 propose the description of an agent-based model implementation in the open-source GIS platform OrbisGIS [START_REF] Bocher | OrbisGIS : Geographical Information System designed by and for research[END_REF]. This platform is characterised by high-performance processing, easy handling on important geographical databases as well as complete cartographic representation capabilities. OrbisGIS stores geographical data in a GDMS database and performs spatial analysis chains using its own language [START_REF] Bocher | OrbisGIS : Geographical Information System designed by and for research[END_REF].

Description of the Urban Simulation Model (USM)

First, we describe in our model a geographic environment (Nantes-Métropole) at the city block scale by means of a large-scale database (BD TOPO, IGN). The model includes road networks, amenities, land-use characterizations, planning rules, and cadastral plots.

In our model we characterize two classes of agents which have their own behaviour and are capable of evolving in both time and space. Using geographic vector data in an agent-based model allows us to consider a geographical object as agent [START_REF] Taillandier | GAMA: a simulation platform that integrates geographical information data, agent-based modeling and multi-scale control[END_REF].

The first type of agent is linked to the cadastral plot, and is characterized as an evolving homogeneous urban structure. Each plot agent is identified with a method based on a remote sensing classification. Five categories of urban structures are defined based on density of buildings, ranging from very low to very high (Figure 1). The plot is determined according to specific evolutionary rules, based on planning rules and attractiveness. As an example, a given zone can evolve from a non-building structure to a building structure or from an existing building structure to a denser building structure depending on local urban rules and the number of households it contains. Households are the second type of agent. This agent is described by average age and income, factors which influence the need for space and the corresponding type of urban structure (e.g., house with a garden or building). Each household searches for a satisfactory plot to settle, considering the housing category and neighbourhood corresponding to similar incomes and the social segregation model [START_REF] Schelling | Dynamic Models of Segregation[END_REF]. If a given plot is not suitable, the household moves on and tries another plot. The more attractive and easier build a plot is, the faster the urban structure becomes dense.

The massive number of agents in the model (100 000 households, 60 000 plots) and the high level of geographical environment detail require a very high-performance platform with complete GIS capabilities. We developed our model from scratch as a plugin in OrbisGIS.

USM, an OrbisGIS plugin

OrbisGIS is an open-source GIS written in Java and developed at the IRSTV (Institut de Recherche Sciences et Techniques de la Ville) in Nantes, France since 2007 [START_REF] Bocher | OrbisGIS : Geographical Information System designed by and for research[END_REF]. The power of OrbisGIS lies in its GDMS (Generic DataSource Management System) library, which offers its own SQL language and an abstract data layer to read, write and process huge amounts of data [START_REF] Bocher | Geospatial Free and Open Source Software in the 21st Century Lectures Notes in Geoinformation and Cartography (LNG\&C) series[END_REF]. GDMS implements the Simple Feature SQL standard to perform data processing with spatial operators (ST Buffer, ST Intersects, etc.). All spatial analysis methods are expressed with SQL functions, just as in PostGIS#. Moreover, GDMS offers an application programming interface (API), and OrbisGIS is a graphical interface that allows creating custom processes and user interfaces. The USM model takes advantage of these two aspects. It is structured in two main components:

The first part is an object-oriented implementation of the model described above, using GDMS files to store results, to read input configuration files and data as well as to run all geographic processes. Its API can be used directly to run simulations and also allows users to provide custom algorithms for some parts of the computation. The second part is a graphical interface accessible through OrbisGIS using the Java Swing GUI library. The USM user interface allows one to configure the model or open a previously configured one, and then to run it (Figure 2). During the simulation execution, the state of several key parameters is visible using dynamic charts, including the number of incoming, outgoing and total households (Figure 3). Each step is stored in a separate GDMS file and can be linked to the input parcel data to display the result of the simulation as a thematic map. For users, a complete visual wizard interface has been developed. All the parameters of the model's configuration can be saved. After the simulation, the user can display each step of the process in OrbisGIS, access all GIS primitives and use them for spatial analysis or dynamic cartography.

Results and further work

Our plugin's processing time is very short considering the large number of agents. Most of the processing time is linked to the movement of agents. The model can treat very large sets of geographic data (more than 100 000 parcels) without significant increase in processing time. Nevertheless, the number of movers can increase it, albeit lightly. As an example, 5 000 agents takes 10 minutes of computation.

Concerning the case study, we tested two scenarios in Nantes-Métropole, a major metropolitan area, located near the west coast of France. Both scenarios propose a time scale of 2010 to 2030. Different categories of urban structures are numbered 1 to 5 in Figure 4. Each category is an indicator determined from a set of variables (density, building height, percent empty space, etc.). Commercial and industrial areas are a specific category that we ignore in this model due to very specific transition rules. The first scenario (Figure 5) simulates a political desire to curb urban sprawl and favours densification. The second scenario (Figure 6) does not constrain urbanization and "let's the city live". As a consequence, in 2030 the model shows important urban sprawl, to the detriment of agricultural and natural areas, especially on the northwest area of the city. Comparing the two maps reveals spatial disparities, particularly in the southwest area of the metropolis where the structure of the plot varies from high densities (mainly orange) to low densities (mainly yellow). A similar trend can be observed in the northwest where structures with lower densities appear. By contrast in the vicinity of the city center (located in the center of the map), structure plots are denser in scenario 1 as compared to to scenario 2.

One of the major interests of this GIS model is to view the results of a simulation in light of demographic data or other spatial information (e.g., land uses, traffic network distribution). The relevance of the model can then be evaluated in relation to the territory and how it changes. This is the most interesting aspect of the model; the results of the simulation can be discussed and improved upon with city planners and urban engineers.

Figure 1 :

 1 Figure 1: Initial step of the simulation

Figure 2 :

 2 Figure 2: Frame to setup the USM configuration parameters

Figure 3 :

 3 Figure 3: Dynamics charts are showing each step of the simulation

Figure 4 :

 4 Figure 4: categories of urban structures

Figure 5 : 1 Figure 6 :

 516 Figure 5: Results of scenario 1

Acknowledgments

This research is part of the VegDUD project, funded by the French Research Agency (Agence Nationale de la Recherche, ANR) under contract ANR-09-VILL-0007. The research partners of VegDUD are: IRSTV, IFSTTAR, Plante et Cité, LaSie (Univ. of La Rochelle), LPGN (Univ. of