Mapping Abstract Complex Workflows onto Grid Environments

In this paper we address the problem of automatically generating job workflows for the Grid. These workflows describe the execution of a complex application built from individual application components. In our work we have developed two workflow generators: the first (the Concrete Workflow Generator CWG) maps an abstract workflow defined in terms of application-level components to the set of available Grid resources. The second generator (Abstract and Concrete Workflow Generator, ACWG) takes a wider perspective and not only performs the abstract to concrete mapping but also enables the construction of the abstract workflow based on the available components. This system operates in the application domain and chooses application components based on the application metadata attributes. We describe our current ACWG based on AI planning technologies and outline how these technologies can play a crucial role in developing complex application workflows in Grid environments. Although our work is preliminary, CWG has already been used to map high energy physics applications onto the Grid. In one particular experiment, a set of production runs lasted 7 days and resulted in the generation of 167,500 events by 678 jobs. Additionally, ACWG was used to map gravitational physics workflows, with hundreds of nodes onto the available resources, resulting in 975 tasks, 1365 data transfers and 975 output files produced.     

Adaptive service scheduling for workflow applications in Service-Oriented Grid

When the workflow application is executed in Service-Oriented Grid (SOG), performance issues such as service scheduling should be considered, to achieve high and stable performance in execution. However, most of the prior works on workflow management neither study the performance issues nor provide evaluation methodologies on the performance of Grid Services. Therefore, it is infeasible to apply for the service scheduling problem in SOG. In this paper, we propose and model evaluation metrics for the Grid Service performance. The metrics are extracted based on common properties of Grid Services and are used to quantify and evaluate the performance of an individual Grid Service. With these metrics, we develop a service scheduling scheme with a list scheduling heuristic, to choose proper and optimal Grid Services for tasks in workflow applications. It ensures high performance in the execution of the workflow applications. In addition, we propose a low-overhead rescheduling method, referred to as Adaptive List Scheduling for Service (ALSS), to adapt to the dynamic nature of a grid environment. ALSS provides stable performance for workflow applications, even in abnormal circumstances. Finally, we design an experimental environment with actual traces and perform simulations to quantify the benefits of our approach. Throughout the experiments, we demonstrate that ALSS outperforms conventional scheduling methods. Our scheme produces a scheduling performance that is superior to AHEFT by 50.2%, SLACK by 50.8%, HEFT by 68.3%, MaxMin by 72.0%, MinMin by 71.0%, and Myopic by 69.8%.     

Practical Experience from Porting and Executing the Wien2k Application on the EGEE Production Grid Infrastructure

While the Grid promises to deliver a large number of computation nodes to a user, this computation power is not usable without the proper adaption of the application for the Grid. In this paper, we describe the methods used to port and execute a particular application, Wien2k, on the EGEE production Grid. First, the process of porting the application is described. Then, we investigate the measures necessary to execute the application in this production Grid environment efficiently. Although the focus is on this special application, we describe generic methods which can be applied to all applications. We specifically address: Creating a workflow from an application and mapping this workflow to a Grid workflow using the activity attraction pattern. We discuss workflow engines which support cycles in their application workflow. We investigate naïve and worker scheduling techniques. A short introduction into licensing on the Grid is given. Optimisation techniques such as deployment re-use are discussed. Different data transfer mechanisms, centralised data transfer, data re-use, storage element data transfer, and peer-to-peer data transfer are compared. The paper is concluded with suggestions for further workflow porting.     

Campus Grids Meet Applications: Modeling, Metascheduling and Integration

Air Quality Forecasting (AQF) is a new discipline that attempts to reliably predict atmospheric pollution. An AQF application has complex workflows and in order to produce timely and reliable forecast results, each execution requires access to diverse and distributed computational and storage resources. Deploying AQF on Grids is one option to satisfy such needs, but requires the related Grid middleware to support automated workflow scheduling and execution on Grid resources. In this paper, we analyze the challenges in deploying an AQF application in a campus Grid environment and present our current efforts to develop a general solution for Grid-enabling scientific workflow applications in the GRACCE project. In GRACCE, an application’s workflow is described using GAMDL, a powerful dataflow language for describing application logic. The GRACCE metascheduling architecture provides the functionalities required for co-allocating Grid resources for workflow tasks, scheduling the workflows and monitoring their execution. By providing an integrated framework for modeling and metascheduling scientific workflow applications on Grid resources, we make it easy to build a customized environment with end-to-end support for application Grid deployment, from the management of an application and its dataset, to the automatic execution and analysis of its results.The work has been performed as part of the University of Houston’s Sun Microsystems Center of Excellence in Geosciences [38].     

Application of if-conversion to verification and optimization of workflows

Based on the workflow analysis graphs proposed in [1] and the well-known if-conversion method [2], a new algorithm of workflow verification is developed. This algorithm is based on the Boolean algebra principles, which is reflected in its name—Boolean Verification Algorithm (BVA). The BVA operates with arbitrary overlapping structures of the graph and with cycles. In the case of dense graphs, the time complexity of the algorithm does not exceed that of most other algorithms of workflow verification [3–6]. In the course of verification, the BVA determines an execution condition for each node of the graph, which makes it possible to create an additional algorithm of workflow optimization. Unlike the well-known algorithms of structural workflow optimization based on pattern transformations [7, 8], the proposed optimization algorithm allows for maximum (within a cycle) parallelization of workflows containing arbitrary overlapping structures.     

Verifying workflow processes: a transformation-based approach

Workflow modeling is a challenging activity and designers are likely to introduce errors, especially in complex industrial processes. Effective process verification is essential at design time because the cost of fixing errors during runtime is substantially higher. However, most user-oriented workflow modeling languages lack formal semantics that hinders such verification. In this paper, we propose a generic approach based on the model transformation to verify workflow processes. The model transformation includes two steps: first, it formalizes the desirable semantics of each modeling element; secondly, it translates a workflow process with clear semantics to an equivalent Petri net. Thus, we can verify the original workflow process using existing Petri net theory and analysis tools. As a comprehensive case study, verifying workflow processes in an industrial modeling language (TiPLM) is presented. Experimental evaluations on verifying real-world business processes validate our approach.     

Workflow-Based Data Parallel Applications on the EGEE Production Grid Infrastructure

Setting up and deploying complex applications on a Grid infrastructure is still challenging and the programming models are rapidly evolving. Efficiently exploiting Grid parallelism is often not straight forward. In this paper, we report on the techniques used for deploying applications on the EGEE production Grid through four experiments coming from completely different scientific areas: nuclear fusion, astrophysics and medical imaging. These applications have in common the need for manipulating huge amounts of data and all are computationally intensive. All the cases studied show that the deployment of data intensive applications require the development of more or less elaborated application-level workload management systems on top of the gLite middleware to efficiently exploit the EGEE Grid resources. In particular, the adoption of high level workflow management systems eases the integration of large scale applications while exploiting Grid parallelism transparently. Different approaches for scientific workflow management are discussed. The MOTEUR workflow manager strategy to efficiently deal with complex data flows is more particularly detailed. Without requiring specific application development, it leads to very significant speed-ups.     

A Framework for Adaptive Fault-Tolerant Execution of Workflows in the Grid: Empirical and Theoretical Analysis

In this paper, we propose and evaluate a framework for fault tolerant workflow execution in Grid environments. Different from previous work in the literature, our system dynamically chooses an appropriate fault tolerance technique while using a user-defined rule-based system. We also provide a generic interface that can be used to add fault tolerance techniques to the framework. The results obtained with real workflows in an experimental Grid environment show that the overhead introduced by our framework in a failure-free execution is, in the worst evaluated case, approximately 10 %. Moreover, we show that, using our framework, workflows are able to execute successfully in the presence of failures and that the framework can dynamically choose an appropriate fault tolerance technique. The main contributions of our work are twofold: the developed framework and the model-based dependability analysis we performed on it. The purpose in carrying out a model-based dependability analysis consists on evaluating the interaction between our framework and the distributed Grid environment beyond the physical limitations of an empirical evaluation. By doing this, we provide means to plan the assurance of QoS in the Grid resource allocation, while applying the fault-tolerance mechanisms we implement in our framework regardless of the underlying middleware.     

Virtual workflow system for distributed collaborative scientific applications on Grids

Grid computing has become an effective computing technique in recent years. This paper develops a virtual workflow system to construct distributed collaborative applications for Grid users. The virtual workflow system consists three levels: abstract workflow system, translator and concrete workflow system. The research highlight of the implementation is that this workflow system is developed based on CORBA and Unicore Grid middleware. Furthermore, this implementation can support legacy application developed with Parco and C++ codes. This virtual workflow system can provide efficient GUI for users to organize distributed scientific collaborative applications and execute them on Grid resources. We present the design, implementation, and evaluation of this virtual workflow system in the paper.     

A grid workflow Quality-of-Service estimation based on resource availability prediction

Accurate estimation of workflow Quality of Service (QoS) enhances the efficiency of scheduling algorithms. The availability and performance variations of Grid computing resources have made this estimation a great challenge. Most workflow QoS estimation algorithms are based on static performance of resources. In this paper, based on resources availability prediction, we propose an algorithm called WQE for estimating the QoS of a Grid workflow. WQE consists of two phases: resource monitoring and analysis and workflow QoS computation. In the first phase, two prediction algorithms are proposed to stochastically predict the availability state of resources. In the second phase, the QoS of each activity is estimated based on the host availability prediction result. The QoS of basic structures is computed by aggregating the QoS of their operands. Using a tree structure corresponding to the workflow, the QoS of basic structures is used to compute the total QoS of the workflow. The simulation results on Notre Dame University trace showed that the proposed method has higher estimation accuracy in comparison with HEFT.     

网格工作流研究现状及存在问题

网格计算成为当前业界研究的热点,网格工作流能够方便地构建、执行、管理和监控网格应用,使得网格应用能够自动、高效地实施。由于网格的动态性、分布性、异构性和自治性导致传统工作流的一些方法和技术不能有效地处理网格环境中的有关问题。本文首先比较了网格工作流与传统工作流的不同,指出了网格工作流研究的必要性,然后介绍了当前网格工作流研究的现状,归纳了三种网络工作流规范及四种网格工作流系统。最后,给出了网格工作流研究存在的问题及研究方向。     

基于网格服务的工作流技术

网格工作流是将工作流技术应用到网格环境中。研究了在OGSA框架下,网格工作流的概念、特点,基于OGSA工作流层次结构和网格工作流执行的基本过程,提出了网格工作流研究中所要解决的几个关键问题,包括网格工作流描述语言、规划与调度、执行与管理、监测与错误处理、动态与优化处理、使用与开发环境。     

一种多学科设计优化工作流验证方法

在多学科设计优化集成系统中,设计过程和优化求解算法均通过可视化工作流实现,工作流有效性验证对提高设计效率和提高系统的用户体验具有重要意义。当前验证方法主要针对办公自动和企业管理系统中的工作流验证问题,多学科设计优化集成系统中的工作流验证问题研究较少。在分析前期工作验证技术的基础上,针对以循环结构为特征的优化环,提出一种基于图论方法的,名为浓缩环(concentration-loop)的验证算法。结合发射平台数字化设计系统的设计与实现,对该算法进行了验证。     

Applying Propositional Logic to Workflow Verification

The increasing complexity of business processes in the era of e-business has heightened the need for workflow verification tools. However, workflow verification remains an open and challenging research area. As an indication, most of commercial workflow management systems do not yet provide workflow designers with formal workflow verification tools. We propose a logic-based verification method that is based on a well-known formalism, i.e., propositional logic. Our logic-based workflow verification approach has distinct advantages such as its rigorous yet simplistic logical formalism and its ability to handle generic activity-based process models. In this paper, we present the theoretical framework for applying propositional logic to workflow verification and demonstrate that logic-based workflow verification is capable of detecting process anomalies in workflow models.     

A Taxonomy of Workflow Management Systems for Grid Computing

With the advent of Grid and application technologies, scientists and engineers are building more and more complex applications to manage and process large data sets, and execute scientific experiments on distributed resources. Such application scenarios require means for composing and executing complex workflows. Therefore, many efforts have been made towards the development of workflow management systems for Grid computing. In this paper, we propose a taxonomy that characterizes and classifies various approaches for building and executing workflows on Grids. We also survey several representative Grid workflow systems developed by various projects world-wide to demonstrate the comprehensiveness of the taxonomy. The taxonomy not only highlights the design and engineering similarities and differences of state-of-the-art in Grid workflow systems, but also identifies the areas that need further research.     

网格环境下费用约束的科学工作流可靠调度算法

网格基础设施是目前科学工作流应用规划、部署和执行的主要支撑环境.然而由于网格资源的自治、动态及异构性,如何在保障用户QoS约束下有效调度科学工作流是一个研究热点.针对费用约束下的科学工作流调度问题,为了提高其执行的可靠性,本文使用随机服务模型描述资源节点的动态服务能力并考虑本地任务负载对资源执行性能的影响,给出一种资源可靠性的评估方法,在此基础上提出一种费用约束下的科学工作流可靠调度算法RSASW.仿真实验结果表明RSASW算法相对于GAIN3,GreedyTime-CD及PFAS算法,对工作流的执行具有很好的可靠性保障.     

An innovative workflow mapping mechanism for Grids in the frame of Quality of Service

The advent of Grid environments made feasible the solution of computational intensive problems in a reliable and cost-effective way. As workflow systems carry out more complex and mission-critical applications, Quality of Service (QoS) analysis serves to ensure that each application meets user requirements. In that frame, we present a novel algorithm which allows the mapping of workflow processes to Grid provided services assuring at the same time end-to-end provision of QoS based on user-defined parameters and preferences. We also demonstrate the operation of the implemented algorithm and evaluate its effectiveness using a Grid scenario, based on a 3D image rendering application.     

Performance metrics and ontologies for Grid workflows

Many Grid workflow middleware services require knowledge about the performance behavior of Grid applications/services in order to effectively select, compose, and execute workflows in dynamic and complex Grid systems. To provide performance information for building such knowledge, Grid workflow performance tools have to select, measure, and analyze various performance metrics of workflows. However, there is a lack of a comprehensive study of performance metrics which can be used to evaluate the performance of a workflow executed in the Grid. Moreover, given the complexity of both Grid systems and workflows, semantics of essential performance-related concepts and relationships, and associated performance data in Grid workflows should be well described. In this paper, we analyze performance metrics that performance monitoring and analysis tools should provide during the evaluation of the performance of Grid workflows. Performance metrics are associated with multiple levels of abstraction. We introduce an ontology for describing performance data of Grid workflows and illustrate how the ontology can be utilized for monitoring and analyzing the performance of Grid workflows.     

基于微粒群算法的网格工作流优化调度问题的研究

网格工作流中的调度问题是一个复杂且具有挑战性的问题,它影响着网格工作流执行成功与否及效率的高低.针对具有时序和因果约束关系的网格工作流优化调度问题进行了研究,建立了网格工作流的任务调度模型和调度问题的目标模型,并应用微粒群算法来优化网格工作流中任务的调度.实验结果证明该算法优于传统的调度算法.     

Visual Grid Workflow in Triana

In this paper, we describe the graphical abstractions for Grids and services that have been implemented within the Triana problem solving environment. We provide an overview of the ways in which Triana interacts with services (e.g., Web and P2P services) and then how we interact with core Grid components, such as resource managers and data management systems through the extensive use of the GridLab GAT interface. We describe in detail the GAT philosophy and implementation and then show how the various GAT primitives can be represented in an intuitive fashion within a Triana workflow. This approach, which we refer to as the Visual GAT, differs substantially from other approaches because we do not tie our implementation to any specific underlying Grid middleware technologies; rather, we base our implementation on application level requirements and model such primitives from a user’s perspective by hiding as much complexity as possible without undermining the core capabilities required. We provide a use case to demonstrate the Visual GAT implementation and show how legacy applications can seamlessly be distributed and integrated in a dynamic fashion within complex data-driven workflow scenarios.