A Survey of Data-Intensive Scientific Workflow Management <s> Fine-Grained Parallelism <s> Whereas a consensus has been reached on defining the set of workflow patterns for business process modeling languages, no such patterns exists for workflows applied to scientific computing on the Grid. By looking at different kinds of parallelism, in this paper we identify a set of workflow patterns related to parallel and pipelined execution. The paper presents how these patterns can be represented in different Grid workflow languages and discusses their implications for the design of the underlying workflow management and execution infrastructure. A preliminary classification of these patterns is introduced by surveying how they are supported by several existing advanced scientific and Grid workflow languages. <s> BIB001 </s> A Survey of Data-Intensive Scientific Workflow Management <s> Fine-Grained Parallelism <s> This third edition of a classic textbook can be used to teach at the senior undergraduate and graduate levels. The material concentrates on fundamental theories as well as techniques and algorithms. The advent of the Internet and the World Wide Web, and, more recently, the emergence of cloud computing and streaming data applications, has forced a renewal of interest in distributed and parallel data management, while, at the same time, requiring a rethinking of some of the traditional techniques. This book covers the breadth and depth of this re-emerging field. The coverage consists of two parts. The first part discusses the fundamental principles of distributed data management and includes distribution design, data integration, distributed query processing and optimization, distributed transaction management, and replication. The second part focuses on more advanced topics and includes discussion of parallel database systems, distributed object management, peer-to-peer data management, web data management, data stream systems, and cloud computing. New in this Edition: New chapters, covering database replication, database integration, multidatabase query processing, peer-to-peer data management, and web data management. Coverage of emerging topics such as data streams and cloud computing Extensive revisions and updates based on years of class testing and feedback Ancillary teaching materials are available. <s> BIB002
The fine-grained parallelism is realized within a workflow or a sub-workflow (for meta-workflows). Three types of parallelism exist at this level: data parallelism, independent parallelism and pipeline parallelism. Data parallelism deals with the parallelism within an activity while independent parallelism and pipeline parallelism handle the parallelism between different activities. Data Parallelism Data parallelism, similar to intraoperator parallelism in BIB002 , is obtained by having multiple tasks performing the same activity, each on a different data chunk. As shown in Fig. 7b , data parallelism happens when the input data of an activity can be partitioned into different chunks and each chunk is processed independently by a task in a different computing node or processor. As the input data needs be partitioned, e.g. by a partitioning task, the activity result is also partitioned. Thus, the partitioned output data can be the base for data parallelism for the next activities. However, to combine the different results to produce a single result, e.g. the final result to be delivered to the user, requires special processing, e.g. by having all the tasks writing to a shared disk or sending their results to a task that produces the single result. Data parallelism can be static, dynamic or adaptive BIB001 . If the number of data chunks is indicated before execution and fixed during execution, the data parallelism is static. If the number of data chunks is determined at run-time, the data parallelism is dynamic. In addition, if the number is automatically adapted to the execution environment, the data parallelism is adaptive. The adaptive data parallelism can determine the best number of data chunks to balance the workflow execution, to increase parallelism degree while maintaining a reasonable overhead. Independent Parallelism Different activities of a workflow can be executed in parallel over several computing nodes. Two activities can be either independent, i.e. the execution of any activity does not depend on the output data of the other one, or dependent, i.e. there is a data dependency between them. Independent parallelism exploits independent activities while pipeline parallelism (see next subsection) deals with dependent activities. Independent parallelism is achieved by having tasks of different independent activities executed simultaneously. As shown in Fig. 7c , independent parallelism occurs when a scientific workflow has more than one independent part in the workflow graph and the activities in each part have no data dependencies with those in another part. To achieve independent parallelism, a SWfMS should identify activities that can be executed in parallel. SWfMSs can partition the workflow into independent parts (or workflow fragments) of activities to achieve independent parallelism. Pipeline Parallelism With pipeline parallelism (see Fig. 7d ), several dependent activities with a producerconsumer relationship are executed in parallel by different tasks. One output data chunk of one activity is consumed directly by the next dependent activities in a pipeline fashion. The advantage of pipeline execution is that the result of the producer activity does not need to be entirely materialized. Instead, data chunks can be consumed as soon as they are ready, thus saving memory and disk accesses. Hybrid Parallelism As shown in Fig. 7e , the three basic types of parallelism can be combined to achieve higher degrees of parallelism. A SWfMS can first perform data parallelism within each activity. Then, it can partition the workflow into independent parts or workflow fragments for independent activities, e.g. with each part or fragment for execution in a different computing node. Finally, pipeline parallelism can be applied for executing dependent activities in parallel. In addition, the parallelism strategies may also be changed at runtime, according to the parallel computing environment behavior  . For the activities that process output data produced by more than one activity, the data is generally merged for the follow-up activity. This merging operation can also be found in the shuffle phase of the MapReduce program execution. By combining these mechanisms, the degree of parallelism can be maximized at different execution layers. We illustrate different types of parallelism, including their combination in hybrid parallelism, with the example shown in Fig. 7 . In this figure, one task Rectangles represent data chunks. "i 1 " stands for the first part of input data. "a1 " stands for the output data corresponding to the first part of input data after being processed by activity A consists of one activity and the related input data. Fig. 7a presents the sequential execution of Activity A, B, C and two parts of input data, i.e. i 1 and i 2 . Since there is no parallelization, the corresponding tasks, i.e. Activity A and Data i 1 , Activity A and Data i 2 , Activity B and Data i 3 , Activity B and Data i 4 , Activity C and Data a 1 , b 1 , Activity C and Data a 2 , b 2 , are executed one after another. Figure 7b describes the execution with data parallelism. The processing of each part of input data is done in different computing nodes in parallel, i.e. the processing of input data i 1 , i 3 and that of input data i 2 , i 4 are done at the same time. Figure 7c shows independent parallelism. Activity A and B are executed at different computing nodes at the same time. Figure 7d shows pipeline parallelism, i.e. the parallel execution of Activity A (or B) and Activity C. Activity A (or B) can be done at the same time as Activity C while processing the different parts of input data. While Activity C is processing Data a 1 and b 1 at Node 2, which corresponds to the input data i 1 and i 3 , Activity A (or B) can process the input data i 2 (or i 4 ). Figure 7e shows hybrid parallelism. Thus, the tasks, i.e. Activity A and Data i 1 , Activity A and Data i 2 , Activity B and Data i 3 , Activity B and Data i 4 can be executed in parallel in different computing nodes. Activity C can begin execution once both Data a 1 and b 1 (or both Data a 2 and b 2 ) are ready. This parallelism combines data parallelism, independent parallelism and pipeline parallelism.