An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements

Grid computing is increasingly considered as a promising next-generation computational platform that supports wide-area parallel and distributed computing. In grid environments, applications are always regarded as workflows. The problem of scheduling workflows in terms of certain quality of service (QoS) requirements is challenging and it significantly influences the performance of grids. By now, there have been some algorithms for grid workflow scheduling, but most of them can only tackle the problems with a single QoS parameter or with small-scale workflows. In this frame, this paper aims at proposing an ant colony optimization (ACO) algorithm to schedule large-scale workflows with various QoS parameters. This algorithm enables users to specify their QoS preferences as well as define the minimum QoS thresholds for a certain application. The objective of this algorithm is to find a solution that meets all QoS constraints and optimizes the user-preferred QoS parameter. Based on the characteristics of workflow scheduling, we design seven new heuristics for the ACO approach and propose an adaptive scheme that allows artificial ants to select heuristics based on pheromone values. Experiments are done in ten workflow applications with at most 120 tasks, and the results demonstrate the effectiveness of the proposed algorithm.     

Parallel numerical applications on grid environments

Grid computing for electromagnetics is one of the few available books that present real applications running on grids. It's a practical book for researchers who want to set up a computational grid and understand the perspectives that grid computing platforms offer. It would also be suitable as a classroom text for undergraduate physics or electrical engineering students with some knowledge of computer networks, C programming, and numerical analysis.     

Autonomic workflow execution in the grid

Mobile agents are being leveraged in both workflow management and grid computing contexts. The convergence of these two research streams supports execution in the grid where tasks are allowed to vary in their level of interdependence. The result is an expansion of grid applications beyond those which consist of homogeneous computations decomposed and performed in parallel to those which support the parallel execution of sequences of interdependent tasks that constitute a workflow. However, grid computation of critical workflows requires that the grid platform exhibits the autonomic characteristic of self-healing in order to ensure workflow execution. To address this issue, in this work, we first develop a model for dynamic fault tolerance technique selection, which can be embedded generically in a mobile agent workflow management system. We then augment an existing architecture for flexible fault tolerance in the grid with our model, thus allowing the system to optimally configure its fault tolerance mechanisms through awareness of the computational environment. The result is a foundation for autonomic workflow management in the grid.     

Influence of Network Characteristics on Application Performance in a Grid Environment

In grid computing, a key issue is how limited network resources can be shared by communications by various applications more effectively in order to improve application-level performance, e.g., by reducing the completion time for an individual application and/or set of applications. Communication by an application changes the condition of the network resources, which may, in turn, affect communications by other applications, and thus may degrade their performance. In this paper, we examine the characteristics of traffic generated by typical grid applications, and the effect of the round-trip time and bottleneck bandwidth on the application-level performance (i.e., completion time) of these applications. Our experiments showed that the impact of network conditions on the performance of various applications and the impact of application traffic on network conditions differed considerably depending on the application. These results suggest that effective allocation of network resources must take into account the network-related properties of individual applications.     

A Semantically Enriched Clinical Guideline Model Enabling Deployment in Heterogeneous Healthcare Environments

Clinical guidelines are developed to assist healthcare practitioners to make decisions on patient's medical problems, and as such they communicate with external applications to retrieve patient data to initiate medical actions through clinical workflows, and transmit information to alert/reminder systems. The interoperability problems in the healthcare information technology domain prevent wider deployment of clinical guidelines because each deployment requires a tedious custom adaptation phase. In this paper, we provide machine-processable mechanisms that express the semantics of clinical guideline interfaces so that automated processes can be used to access the clinical resources for guideline deployment and execution. To be able to deploy the semantically extended guidelines to healthcare settings semiautomatically, the underlying application's semantics must also be available. We describe how this can be achieved based on two prominent implementation technologies in use in the eHealth domain: integrating healthcare enterprise cross-enterprise document sharing integration profile for discovering and exchanging electronic healthcare records and Web service technology for interacting with the clinical workflows and wireless medical sensor devices. The system described in this paper is realized within the scope of the SAPHIRE Project.      

The design and applications of a recursive molecular modelingframework

In this paper, we present a recursive molecular model that is suitable for multi-resolution analysis in a variety of application areas. Our approach allows ease of use by computer scientists and biologists by proposing a software interface for molecular analysis that hides programming details. We demonstrate that our design is flexible enough for use in desktop analytical applications, in large-scale parallel simulations, and as a server for remote molecular analysis across wide-area networks     

Markov decision process (MDP) framework for software power optimization using call profiles on mobile phones

We present an optimization framework for delay-tolerant data applications on mobile phones based on the Markov decision process (MDP). This process maximizes an application specific reward or utility metric, specified by the user, while still meeting a talk-time constraint, under limited resources such as battery life. This approach is novel for two reasons. First, it is user profile driven, which means that the user’s history is an input to help predict and reserve resources for future talk-time. It is also dynamic: an application will adapt its behavior to current phone conditions such as battery level or time before the next recharge period. We propose efficient techniques to solve the optimization problem based on dynamic programming and illustrate how it can be used to optimize realistic applications. We also present a heuristic based on the MDP framework that performs well and is highly scalable for multiple applications. This approach is demonstrated using two applications: Email and Twitter synchronization with different priorities. We present experimental results based on Google’s Android platform running on an Android Develepor Phone 1 (HTC Dream) mobile phone.     

QoS specification languages for distributed multimedia applications: a survey and taxonomy

Following considerable research into quality-of-service-aware application programming interface design and QoS specification language development for multimedia systems, we present a survey and taxonomy of existing QoS specification languages. As computer and communication technology evolves, distributed multimedia applications are becoming ubiquitous, and quality of service (QoS) is becoming ever more integral to those applications. Because they consume so many resources (such as memory and bandwidth), multimedia applications need resource management at different layers of the communications protocol stack to ensure end-to-end service quality, and to regulate resource contention for equitable resource sharing. However, before an application can invoke any QoS-aware resource management mechanisms and policies - such as admission control, resource reservation, enforcement, and adaptation - it must specify its QoS requirements and the corresponding resource allocations. Furthermore, the application must describe how QoS should be scaled and adapted in cases of resource contention or resource scarcity during runtime. Our goal in this article is to systematically classify and compare the existing QoS specification languages that span several QoS layers with diverse properties. The provided taxonomy and the extensive analysis will give us a detailed look at the existing QoS specification languages along with their properties and relations.     

Semantic-driven grid-enabled computer-aided engineering of aperture-antenna arrays

In this paper, we propose a novel architecture for computer-aided engineering (CAE) of rectangular aperture arrays that takes advantage of semantic grid computing technologies. This allows the implementation of the CAE environment in a service-oriented framework, where CAE applications are built up at run time, by exploiting remote services through the grid. The identification and localization of remote services and their orchestration is simplified by semantic facilities, centered around a CAE ontology. This provides a structured, conceptual representation of hardware and software resources, including CAE services, which is understandable both by humans and software agents. The implemented prototype demonstrates how semantic grids satisfy the strong need for cooperation tools in the CAE of microwave circuits and antennas, and represents an effective pathway towards the automatic generation of design tools, attained by integrating electromagnetic software available through the Web.     

GCM: a grid extension to Fractal for autonomous distributed components

This article presents an extension of the Fractal component model targeted at programming applications to be run on computing grids: the grid component model (GCM). First, to address the problem of deployment of components on the grid, deployment strategies have been defined. Then, as grid applications often result from the composition of a lot of parallel (sometimes identical) components, composition mechanisms to support collective communications on a set of components are introduced. Finally, because of the constantly evolving environment and requirements for grid applications, the GCM defines a set of features intended to support component autonomicity. All these aspects are developed in this paper with the challenging objective to ease the programming of grid applications, while allowing GCM components to also be the unit of deployment and management.     

Grid computing for electromagnetics: a beginner's guide with applications

The demand for computing power in computational electromagnetics (CEM) is continuously increasing. Meanwhile, cooperative engineering is becoming more and more present in daily research and development workflows. Projects are often developed by teams, which interact remotely, and need tighter and tighter connectivity. Grid computing (GC), from the perspective of progress in computer networks, seems a promising way to satisfy both the need of high-performance computing platforms, and the requirements for effective cooperative computing. In this paper, researchers involved in CEM are introduced to grid computing, and to the use of grid computing for CEM. Two real applications are proposed, with a critical discussion on potential benefits and drawbacks with respect to alternative strategies.     

An Incremental Approach to the Analysis and Transformation of Workflows Using Region Trees

The analysis of workflows in terms of structural correctness is important for ensuring the quality of workflow models. Typically, this analysis is only one step in a larger development process, followed by further transformation steps that lead from high-level models to more refined models until the workflow can finally be deployed on the underlying workflow engine of the production system. For practical and scalable applications, both analysis and transformation of workflows must be integrated to allow incremental changes of larger workflows. In this paper, we introduce the concept of a region tree (RT) for workflow models that can be used as the central data structure for both workflow analysis and workflow transformation. An RT is similar to a program structure tree and imposes a hierarchy of regions as an overlay structure onto the workflow model. It allows an incremental approach to the analysis and transformation of workflows, and thereby, significantly reduces the overhead because individual regions can be dealt with separately. The RT is built using a set of region-growing rules. The set of rules presented here is shown to be correct and complete in the sense that a workflow is region-reducible as defined through these rules if and only if it is semantically sound.     

Topology discovery services for monitoring the global grid

The dynamic joint optimization of both computational and network resources has the potential of guaranteeing optimal performance Io geographically distributed grid applications. A grid network information and monitoring service (NIMS) has been recently proposed to complement computational resource status information with network resource status information. NIMS information includes, but is not limited to, information already available in the network control plane (e.g., network topology, link capacity occupation, communication delay). This study first reviews some measurement methodologies and network sensors suitable for implementing NIMS components, and then describes some tools currently utilized for monitoring grid network infrastructures. Finally, two implementations of a NIMS component, called the topology discovery service (TDS), are proposed and evaluated. The TDS provides grid users (e.g., applications) or the programming environment middleware with up-to-date information on the grid network infrastructure topology and status. Both proposed implementations can be utilized in any global grid network based on commercial routers without requiring modifications of router management and control protocols.     

桥接桌面网格和服务网格

介绍一项新的欧盟第7框架基础架构研究项目:EDGeS(Enabling Desktop Grids for e-Science).该项目致力于搭建推动桌面网格和服务网格间互用性的桥梁技术.还对现有的网格系统进行了分类:桌面网格(例如BONIC和Xtrem Web)与服务网格(例如EGEE).然后进一步描述了对于桌面网格和服务网格应用间转换的解决方案.探讨了现有的、流行的桥梁技术,用户访问问题,分布式数据的部署与应用开发的问题.     

XML-based data model and architecture for a knowledge-based grid-enabled problem-solving environment for high-throughput biological imaging.

High-throughput biological imaging uses automated imaging devices to collect a large number of microscopic images for analysis of biological systems and validation of scientific hypotheses. Efficient manipulation of these datasets for knowledge discovery requires high-performance computational resources, efficient storage, and automated tools for extracting and sharing such knowledge among different research sites. Newly emerging grid technologies provide powerful means for exploiting the full potential of these imaging techniques. Efficient utilization of grid resources requires the development of knowledge-based tools and services that combine domain knowledge with analysis algorithms. In this paper, we first investigate how grid infrastructure can facilitate high-throughput biological imaging research, and present an architecture for providing knowledge-based grid services for this field. We identify two levels of knowledge-based services. The first level provides tools for extracting spatiotemporal knowledge from image sets and the second level provides high-level knowledge management and reasoning services. We then present cellular imaging markup language, an extensible markup language-based language for modeling of biological images and representation of spatiotemporal knowledge. This scheme can be used for spatiotemporal event composition, matching, and automated knowledge extraction and representation for large biological imaging datasets. We demonstrate the expressive power of this formalism by means of different examples and extensive experimental results.     

Analog neural optimization for ATM resource management

This paper addresses the issue of how to solve convex programming problems by analog artificial neural networks (ANNs), with applications in asynchronous transfer mode (ATM) resource management. We first show that the essential and difficult optimization problem of dimensioning the system of virtual subnetworks in ATM networks can be modeled as a convex programming task. Here the transformation of the problem into a convex programming task is a nontrivial step. We also present and analyze an analog ANN architecture that is capable of solving such convex programming tasks with time-varying penalty multipliers. The latter property makes it possible to perform quick sensitivity analysis with respect to the constraints in order to identify the bottleneck capacities in the network or those which give the highest return if we invest in extending them     

Combinatorial auctions for exchanging resources over a grid network

In grid systems, users compete for different types of resources such that they may execute their applications. Traditional grid systems are formed of organisations that join together for the purpose of collaborative projects. Resources of each of the participating organisation are pooled such that members of individual organisations may access the shared infrastructure. In general, each participant is both a provider and a consumer of resources. Whilst such systems address large organisations, in this paper we address democratic grid systems to satisfy needs of small organisations and even individuals, where on-demand grids may be formed by drawing idling resources available on the Internet. Whilst traditional grid systems resort to allocations that satisfy system specific objectives such as maximization of the resource utilisation, market mechanisms try to obtain allocations that are efficient economically. Economic mechanisms permit to achieve equilibrium between supply and demand and furthermore provide incentives for providers. Combinatorial auction has been argued as an effective mechanism to address the problem of resource allocation within grid systems. Auctions within which multiple types of resources in varying quantities may be traded eliminate the exposure problem by addressing co-allocation. In this paper, we describe a combinatorial exchange where multiple providers and multiple consumers may participate. We describe the winner determination problem that incorporates the time dimension, i.e. resource bundles may be requested for different time ranges, and describe a set of heuristics that have been designed to be fast. We show that these achieve a high level of efficiency as compared to exact solutions. The second part focusses on the pricing problem. The objective is to compute prices that represent the state of the market and bring trustworthy feedback to participants. Drawing on the approach taken by Kwasnica et al. (Manage Sci 51(3):419–434, 2005), we propose a pricing model that computes per-item pricing. Per-item pricing allows users to deduce the price of bundles that they require by linear summation. Furthermore, we propose a model that computes prices as a function of time, thus permitting users, in particular consumers to adjust their demand trading off price and time of execution.     

Accord: a programming framework for autonomic applications

The emergence of pervasive wide-area distributed computing environments, such as pervasive information systems and computational grids, has enabled new generations of applications that are based on seamless access, aggregation, and interaction. However, the inherent complexity, heterogeneity, and dynamism of these systems require a change in how the applications are developed and managed. In this paper, we present a programming framework that extends existing programming models/frameworks to support the development of autonomic self-managing applications. The framework enables the development of autonomic elements and the formulation of autonomic applications as the dynamic composition of autonomic elements. The operation of the proposed framework is illustrated using a forest fire management application.     

Interoperability of GADU in using heterogeneous grid resources for bioinformatics applications.

Bioinformatics tools used for efficient and computationally intensive analysis of genetic sequences require large-scale computational resources to accommodate the growing data. Grid computational resources such as the Open Science Grid and TeraGrid have proved useful for scientific discovery. The genome analysis and database update system (GADU) is a high-throughput computational system developed to automate the steps involved in accessing the Grid resources for running bioinformatics applications. This paper describes the requirements for building an automated scalable system such as GADU that can run jobs on different Grids. The paper describes the resource-independent configuration of GADU using the Pegasus-based virtual data system that makes high-throughput computational tools interoperable on heterogeneous Grid resources. The paper also highlights the features implemented to make GADU a gateway to computationally intensive bioinformatics applications on the Grid. The paper will not go into the details of problems involved or the lessons learned in using individual Grid resources as it has already been published in our paper on genome analysis research environment (GNARE) and will focus primarily on the architecture that makes GADU resource independent and interoperable across heterogeneous Grid resources.     

Programming video cards for computational electromagnetics applications

Recently, programming tools have become available to researchers and scientists that allow the use of video cards for general-purpose calculations in computational electromagnetics applications. Over the past few years, developments in the field of graphic processing units (GPUs) for video cards have vastly outpaced their general central processing unit (CPU) counterparts. As specifically applied to vector mathematic operations, the newest generation GPUs can generally outperform current CPU architecture by a wide margin. With the addition of large onboard memory units with significantly higher memory bandwidth than those found in the main system, graphic cards can be utilized as a highly efficient vector mathematic coprocessor. In the past, this power has been harnessed by writing low-level assembly code for the video cards. Recently, new tools have become available to make programming possible in high-level languages. By formulating proper procedures to realize general vector computations on the GPU, it will be possible to increase the processing power available by at least an order of magnitude compared to the current generation of CPUs.