Search

Distributed e-Infrastructure is a key component of modern BIG Science. Service discovery in e-Science environments, such as Worldwide LHC Computing Grid (WLCG), is a crucial functionality that relies on service registry. In this paper we re-formulate the requirements for the service endpoint registry based on our more than 10 years experience with many systems designed or used within the WLCG e-Infrastructure. To satisfy those requirements the paper proposes a novel idea to use the existing well-established Domain Name System (DNS) infrastructure together with a suitable data model as a service endpoint registry. The presented ARC Hierarchical Endpoints Registry (ARCHERY) system consists of a minimalistic data model representing services and their endpoints within e-Infrastructures, a rendering of the data model embedded into DNS-records, a lightweight software layer for DNS-record management and client-side data discovery. Our approach for the ARCHERY registry required minimal software development and inherits all the benefits of one of the most reliable distributed information discovery source of the internet, the DNS infrastructure. In particular, deployment, management and operation of ARCHERY is fully relying on DNS. Results of ARCHERY deployment use-cases are provided together with performance analysis. [ABSTRACT FROM AUTHOR]

This paper discusses the load-balanced task allocation problem in the grid transaction processing system to maximize reliability. Finding the solution of optimal load-balanced task allocation is known to be an NP-hard. This paper presents a load-balanced task allocation based cuckoo search-ant colony optimization (LBTA_CSACO) method for this problem. The LBTA_CSACO is based on the cooperative behavior of cuckoo search and ant colony optimization to nd a collection of task allocation solutions. This paper also models the reliability of the system with the help of the availability of the system. The motive of this work is to maximize the reliability of the system. After the simulation, six existing algorithms are taken for the comparison of the results; Honey Bee Optimization (HBO), Ant Colony Optimization (ACO), Hierarchical Load Balanced Algorithm (HLBA), Dynamic and Decentralized Load Balancing (DLB), and Randomized respectively. [ABSTRACT FROM AUTHOR]

This paper applies the slicing technique to extract the contour feature line. The sliced data are projected on the plane to obtain the feature line of the slice profile by grid computing, which can directly establish a three-dimensional model. Due to redundancy and the uneven distribution of the point cloud, it is difficult to determine the slice thickness, causing projection error and disconnection of the contour line. In this paper, the projection error and efficiency of calculation are improved with twice data layer compression to extract the point cloud data generated by the contour. In the contour feature extraction, the line segment code is established using its structure to calculate the contour boundary by connectivity judgment. Through experimental comparison, the algorithm using the line segment to determine the boundary is more effective and robust than the eight neighborhood algorithm. [ABSTRACT FROM AUTHOR]

Cloud computing is the fastest growing distributed computing paradigm that provides online IT resources on demand by following a pay-as-you-go billing model. The success of this computing paradigm enables cloud providers to offer an extensive collection of parallel computing resources to deal with Big Data workflow scheduling problems. Although, workflow scheduling has been extensively studied, however, most of them are unable to achieve user-specified deadline constraints at the cheap cost. In this paper, a Dynamic Cost-Efficient Deadline-Aware (DCEDA) heuristic algorithm is proposed for scheduling Big Data workflow that produces the cheapest schedule while achieving the deadline constraints. DCEDA dynamically takes appropriate scheduling decisions for workflow tasks based on the fact that deadline constraint is not violated in the future. Also, it continuously monitors the VM pool for identifying the active idle VMs that incur extra costs and overheads, and subsequently de-provision them. The experimental analysis based on Montage workflow and randomly generated synthetic workflow with various characteristics prove that DCEDA delivers better performance in comparison to the existing algorithms. [ABSTRACT FROM AUTHOR]

Scheduling of transactions in the grid computing system is known to be an NP-hard problem. In order to solve this problem, this paper introduces a hybrid approach named cuckoo search-ant colony optimization. The approach is to dynamically generate an optimal schedule by clustering the resources considering their load so as to complete the transactions within their deadlines as well as utilizing the resources in an efficient way. The approach also balances the load of the system before scheduling the transactions. We use cuckoo search method for making clusters of resources based on their load. We use ant colony optimization for selecting the appropriate and optimal resources. We evaluate the performance of the proposed algorithm with six existing algorithms. The results illustrate that an important advantage of the cuckoo search-ant colony optimization algorithm is its speed of clustering and ability to obtain faster and feasible load balanced schedules. [ABSTRACT FROM AUTHOR]

Security is a major concern of modern real-time applications, besides requiring stringent latency bound. However, encryption algorithms are computation intensive task which impacts the timeliness of the real-time applications. Therefore, there exists a trade-off between the desired level of security and the service guarantee. In this paper, we propose a security-aware dynamic scheduling algorithm (SADSA) using a grid of computational elements (CEs) which performs this trade-off and tries to maximize the instantaneous average security level of the packets besides providing a guaranteed service. As packets arrive, we first assign them to the CEs based on the utilization value of a CE, which is the ratio of completion time and a deadline of the last packet in a CE. The security level of all the packets is then dynamically adjusted to meet the minimum required security level while maximizing the average security level of all the packets in that CE. We first show that the proposed assignment algorithm is NP-hard, is 2-competitive to the optimal solution, and that the proposed algorithm provides a sub-optimal solution. Further, using extensive simulation, we show that the proposed SADSA algorithm performs better in terms of guarantee ratio, average security level and overall performance compared to the existing algorithms. [ABSTRACT FROM AUTHOR]

Cloud computing has become the most attractive platform compared to grid computing, that offers several services such as infrastructure as a service, platform as a service, and software as a service, where the users can consume these services on the cloud and pay based on their consumption and on the fulfilment of Quality of Service (QoS) constraints such as deadline and budget. Hence, to schedule the tasks effectively, cost monetary must be considered while optimising implementation time performance under users' defined constraints. In this paper, the Deadline Budget Scheduling (DBS) model is proposed to execute the users' tasks on Virtual Machines (VMs) under the QoS constraints at less execution time. In our proposal, users' tasks will be assigned to appropriate VM which meets either of the two constraints namely (deadline and budget) or one of the constraints based on user satisfaction. Makespan and cost are calculated to evaluate our proposed DBS model with state of the art algorithms. The experimental results illustrate that DBS outperforms other algorithms by minimizing the makespan and cost. [ABSTRACT FROM AUTHOR]

Due to the explosive increase in the production and sharing of digital visual media such as photos, animations, films and video clips, the need to intentionally or unintentionally create mosaic blocks to effectively cover user-designated regions within images has grown. In this paper, a method using boundary characteristics to effectively detect the grid-type mosaic blocks existing within the input image is proposed. Initially, the Canny edge is detected from the input image. Then, the boundary characteristics of mosaic blocks are extracted from the detected edges, and the candidate regions which may contain mosaic blocks are detected. After this stage, geometric characteristics are used to eliminate non-mosaic blocks and select actual mosaic blocks. In the experiment performed in this paper, it was observed that the method using boundary characteristics achieved more robust detection of the grid-type mosaic blocks from various input images than other existing methods. The mosaic-detection method proposed in this paper is expected to be valuable for applications in various fields. [ABSTRACT FROM AUTHOR]

Many research institutions are deploying computing clusters based on a shared/buy-in paradigm. Such clusters combine shared computers, which are free to be used by all users, and buy-in computers, which are computers purchased by users for semi-exclusive use. The purpose of this paper is to characterize the typical behavior and performance of a shared/buy-in computing cluster, using data traces from the Shared Computing Cluster (SCC) at Boston University that runs under this paradigm as a case study. Among our main findings, we show that the semi-exclusive policy, which allows any SCC user to use idle buy-in resources for a limited time, increases the utilization of buy-in resources by 17.4%, thus significantly improving the performance of the system as a whole. We find that jobs allowed to run on idle buy-in resources arrive more frequently and run for a shorter time than other jobs. Finally, we identify the run time limit (i.e., the maximum time during which a job is allowed to use resources) and the type of parallel environment as two factors that have a significant impact on the different performance experienced by shared and buy-in jobs. [ABSTRACT FROM AUTHOR]

The large choice of Distributed Computing Infrastructures (DCIs) available allows users to select and combine their preferred architectures amongst Clusters, Grids, Clouds, Desktop Grids and more. In these hybrid DCIs, elasticity is emerging as a key property. In elastic infrastructures, resources available to execute application continuously vary, either because of application requirements or because of constraints on the infrastructure, such as node volatility. In the former case, there is no guarantee that the computing resources will remain available during the entire execution of an application. In this paper, we show that Bag-of-Tasks (BoT) execution on these 'Best-Effort' infrastructures suffer from a drop of the task completion rate at the end of the execution. The SpeQuloS service presented in this paper improves the Quality of Service (QoS) of BoT applications executed on hybrid and elastic infrastructures. SpeQuloS monitors the execution of the BoT, and dynamically supplies fast and reliable Cloud resources when the critical part of the BoT is executed. SpeQuloS offers several features to hybrid DCIs users, such as estimating completion time and execution speedup. Performance evaluation shows that BoT executions can be accelerated by a factor 2, while offloading less than 2.5 % of the workload to the Cloud. We report on several scenarios where SpeQuloS is deployed on hybrid infrastructures featuring a large variety of infrastructures combinations. In the context of the European Desktop Grid Initiative (EDGI), SpeQuloS is operated to improve QoS of Desktop Grids using resources from private Clouds. We present a use case where SpeQuloS uses both EC2 regular and spot instances to decrease the cost of computation while preserving a similar QoS level. Finally, in the last scenario SpeQuloS allows to optimize Grid5000 resources utilization. [ABSTRACT FROM AUTHOR]

'Give a man a fish, feed him for a day. Teach a man to fish, feed him for a lifetime'-Lau Tzu. Large-scale grid computing projects such as TeraGrid and Open Science Grid provide researchers vast amounts of compute resources but with requirements that could limit access, delay results due to potentially long job queues, and involve environments and policies that might affect a user's work flow. In many scenarios and in particular with the advent of Infrastructure-as-a-Service (IaaS) cloud computing, individual users and communities can benefit from less restrictive, dynamic systems that include a combination of local resources and on-demand resources provisioned by one or more IaaS provider. These types of scenarios benefit from flexibility in deploying resources, remote access, and environment configuration. In this paper, we address how small groups can dynamically create, join, and manage grid infrastructures with low administrative overhead. Our work distinguishes itself from other projects with similar objectives by enabling a combination of decentralized system organization and user access for job submission in addition to a web 2.0 interfaces for managing grid membership and automate certificate management. These components contribute to the design of the 'Grid Appliance,' an implementation of a wide area overlay network of virtual workstations (WOW), which has developed over the past six years into a mature system with several deployments and many users. In addition to an architectural description, this paper contains lessons learned during the development and deployment of 'Grid Appliance' systems and a case study backed by quantitative analysis that verifies the utility of our approach. [ABSTRACT FROM AUTHOR]

Loosely coupled applications composed of a potentially very large number (from tens of thousands to even billions) of tasks are commonly used in high-throughput computing and many-task computing paradigms. To efficiently execute large-scale computations which can exceed the capability in a single type of computing resources within expected time, we should be able to effectively integrate resources from heterogeneous distributed computing (HDC) systems such as clusters, grids, and clouds. In this paper, we quantitatively analyze the performance of three different real scientific applications consisting of many tasks on top of HDC systems based on a partnership of distributed computing clusters, grids, and clouds to understand the application and resource characteristics, and show practical issues that normal scientific users can face during the course of leveraging these systems. Our experimental study shows that the performance of a loosely coupled application can be significantly affected by the characteristics of a HDC system, along with hardware specification of a node, and their impacts on the performance can vary widely depending on the resource usage pattern of each application. We then devise a preference-based scheduling algorithm that can reflect characteristics and resource usage patterns of various loosely coupled applications running on top of HDC systems from our experimental study. Our preference-based scheduling algorithm can allocate the resources from different HDC systems to loosely coupled applications based on the preferences of the applications for the HDC systems. We evaluate the overall system performance over various preference types, using trace-based simulations, which can be determined based on different factors such as CPU specifications and application throughputs. Our simulation results demonstrate the importance of understanding the application and resource characteristics on effective scheduling of loosely coupled applications on the HDC systems. [ABSTRACT FROM AUTHOR]

Abstract   The performance skeleton of an application is a short running program whose performance in any scenario reflects the performance of the application it represents. Specifically, the execution time of the performance skeleton is a small fixed fraction of the execution time of the corresponding application in any execution environment. Such a skeleton can be employed to quickly estimate the performance of a large application under existing network and node sharing. This paper presents a framework for automatic construction of performance skeletons of a specified execution time and evaluates their use in performance prediction with CPU and network sharing. The approach is based on capturing the execution behavior of an application and automatically generating a synthetic skeleton program that reflects that execution behavior. The paper demonstrates that performance skeletons running for a few seconds can predict the application execution time fairly accurately. Relationship of skeleton execution time, application characteristics, and nature of resource sharing, to accuracy of skeleton based performance prediction, is analyzed in detail. The goal of this research is accurate performance estimation in heterogeneous and shared computational grids. [ABSTRACT FROM AUTHOR]

Data Grid integrates geographically distributed resources for solving data sensitive scientific applications. Dynamic data replication algorithms are becoming increasingly valuable in solving large-scale, realistic, difficult problems, and selecting replica with multiple selection criteria-availability, security and time- is one of these problems. The current algorithms do not offer balanced QoS levels and the mechanism of rating QoS parameters. In this paper, we propose a new replica selection strategy, which based on response time and security. However, replication should be used wisely because the storage size of each Data Grid site is limited. Thus, the site must keep only the important replicas. We also present a new replica replacement strategy based on the availability of the file, the last time the replica was requested, number of access, and size of replica. We evaluate our algorithm using the OptorSim simulator and find that it offers better performance in comparison with other algorithms in terms of mean job execution time, effective network usage, SE usage, replication frequency, and hit ratio. [ABSTRACT FROM AUTHOR]

Large-scale scientific applications from various scientific domains (e.g., astronomy, physics, pharmaceuticals, chemistry, etc.) usually require substantial amounts of computing resources and storage space. International Grid computing resources can be a viable choice for supporting these challenging applications so that effectively locating suitable computing resources with minimal allocation overhead can be crucial. However, Grid resource availability is highly unstable and current Grid Information Service (GIS) cannot provide accurate state information. This can make it very difficult for users to schedule the jobs on the Grid system and to map tasks on appropriate available resources. In this paper, we present SCOUT system that can periodically profile Grid computing elements based on available number of CPU cores and average response time, and monitor the performance of each CE in the Virtual Organizations (VO). Micro-benchmark experimental results demonstrate that leveraging profiled data by SCOUT can improve the success rate of task executions and reduce the average response time. [ABSTRACT FROM AUTHOR]

Computational grids have the potential for solving large-scale scientific problems using heterogeneous and geographically distributed resources. At this scale, computer resources and network failures are no more exceptions, but belong to the normal system behavior. Therefore, one of the most valuable characteristics of grid tools, apart from the performance they can achieve, is fault tolerance, which is a significant and complex issue in grid computing systems. In this paper, we propose a fault tolerant model for grid computing systems namely DCFT. This model is based on dynamic colored graphs without replication of computer resources. The proposed faut tolerance model consists of two stages. In the first stage, each node is described by a state vector. We color each attribute of the state vector as three colors (green, blue and red) based on its level of performance. In the second stage, we classify the nodes of a grid into three categories: the identical computer resources in term of performance, the more efficient ones and the less efficient ones. We used the colors of the nodes to develop a new strategy for fault tolerance based on the level of performance. A simulation of the proposed model using SimGrid simulator and Graphstream is conducted. Experimental results show that the proposed model performs very well in a large grid environment. [ABSTRACT FROM AUTHOR]

Agent-based simulation models with large experiments for a precise and robust result over a vast parameter space are becoming a common practice, where enormous runs intrinsically require highly intensive computational resources. This paper proposes a grid based simulation environment, named Social Macro Scope (SOMAS) to support parallel exploration on agent-based models with vast parameter space. We focus on three types of simulation methods for agent-based models with various objectives (1) forward simulation to conduct experiments in a straightforward way by simply operating sets of parameter values to perform sensitivity analysis; (2) inverse simulation to search for solutions that reduce the error between simulated results and actual data by means of solving 'inverse problem', which executes the simulation steps in a reverse order and employs optimization algorithms to fit the simulation results to the desired objectives; and (3) model selection to find an optimal model structure with subset of parameters and procedures, which conducts two-layer optimization to obtain a simple and more accurate simulation result. We have confirmed the practical scalability and efficiency of SOMAS by one case study in history simulation domain. [ABSTRACT FROM AUTHOR]

Cyber-physical systems (CPS) are composed of collaborating computational elements that control physical entities. The human desire to acquire useful information and to automatically control devices anytime and anywhere has increased the necessity to develop systems with high reliability. However, the CPS associated with the physical world and cyber world involve managing complexity and incurring the respective maintenance costs, such that it has been impossible to produce systems that are completely reliable. Thus, this paper presents an 'Autonomic Control System for High-reliable Cyber-Physical Systems' that is comprised of eight processes, including fault analysis, fault event analysis, fault modeling, fault state interpretation, fault strategy decision, fault detection, diagnosis & reasoning, and maneuver execution. These processes facilitate the design and implementation of an autonomic control system that is superior to what was available before. As proof of the approach, we used an intelligent service robot (ISR) as a case study. The experimental results show that the ISR is able to detect a fault event during autonomic control of the CPS. [ABSTRACT FROM AUTHOR]

For natural group movement of non player characters (NPCs) in a computer game, an efficient planning algorithm is necessary. This paper presents a grid window-based path planning algorithm for realistic group movement. The global path is planned in a static environment and the path is locally repaired to avoid dynamic obstacles during execution. The planning and execution processes are performed for the group, not for individual NPCs by using a 2D virtual grid window covering all the NPCs. The movement of each NPC is generated inside the grid window without complicated procedures to detect collisions. We implement and test the algorithm on a polygonal world modeling a real game background. The simulation results show that the proposed method provides natural group movement and dynamic obstacle avoidance, and the experimental result with various numbers of NPCs shows consistent performance. [ABSTRACT FROM AUTHOR]

Grid computing uses distributed interconnected computers and resources collectively to achieve higher performance computing and resource sharing. Task scheduling is one of the core steps to efficiently exploit the capabilities of Grid environment. Recently, heuristic algorithms have been successfully applied to solve task scheduling on computational Grids. In this paper, Gravitational Search Algorithm (GSA), as one of the latest population-based metaheuristic algorithms, is used for task scheduling on computational Grids. The proposed method employs GSA to find the best solution with the minimum makespan and flowtime. We evaluate this approach with Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) method. The results demonstrate that the benefit of the GSA is its speed of convergence and the capability to obtain feasible schedules. [ABSTRACT FROM AUTHOR]

The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration. In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a difficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores. [ABSTRACT FROM AUTHOR]

Energy efficiency and high computing power are basic design considerations across modern-day computing solutions due to different concerns such as system performance, operational cost, and environmental issues. Desktop Grid and Volunteer Computing System (DGVCS) so called opportunistic infrastructures offer computational power at low cost focused on harvesting idle computing cycles of existing commodity computing resources. Other than allowing to customize the end user offer, virtualization is considered as one key techniques to reduce energy consumption in large-scale systems and contributes to the scalability of the system. This paper presents an energy efficient approach for opportunistic infrastructures based on task consolidation and customization of virtual machines. The experimental results with single desktops and complete computer rooms show that virtualization significantly improves the energy efficiency of opportunistic grids compared with dedicated computing systems without disturbing the end-user. [ABSTRACT FROM AUTHOR]

An optimization of power and energy consumptions is the important concern for a design of modern-day and future computing and communication systems. Various techniques and high performance technologies have been investigated and developed for an efficient management of such systems. All these technologies should be able to provide good performance and to cope under an increased workload demand in the dynamic environments such as Computational Grids (CGs), clusters and clouds. In this paper we approach the independent batch scheduling in CG as a bi-objective minimization problem with makespan and energy consumption as the scheduling criteria. We use the Dynamic Voltage Scaling (DVS) methodology for scaling and possible reduction of cumulative power energy utilized by the system resources. We develop two implementations of Hierarchical Genetic Strategy-based grid scheduler ( Green-HGS-Sched) with elitist and struggle replacement mechanisms. The proposed algorithms were empirically evaluated versus single-population Genetic Algorithms (GAs) and Island GA models for four CG size scenarios in static and dynamic modes. The simulation results show that proposed scheduling methodologies fairly reduce the energy usage and can be easily adapted to the dynamically changing grid states and various scheduling scenarios. [ABSTRACT FROM AUTHOR]

High performance and distributed computing systems such as peta-scale, grid and cloud infrastructure are increasingly used for running scientific models and business services. These systems experience large availability variations through hardware and software failures. Resource providers need to account for these variations while providing the required QoS at appropriate costs in dynamic resource and application environments. Although the performance and reliability of these systems have been studied separately, there has been little analysis of the lost Quality of Service (QoS) experienced with varying availability levels. In this paper, we present a resource performability model to estimate lost performance and corresponding cost considerations with varying availability levels. We use the resulting model in a multi-phase planning approach for scheduling a set of deadline-sensitive meteorological workflows atop grid and cloud resources to trade-off performance, reliability and cost. We use simulation results driven by failure data collected over the lifetime of high performance systems to demonstrate how the proposed scheme better accounts for resource availability. [ABSTRACT FROM AUTHOR]

There have been recent research activities on GPS-based FNET to prevent wide-area blackouts by monitoring frequency deviation. This paper introduces a system for monitoring regional frequencies in power grid developed as an advanced research project for intelligent wide-area protective relaying in South Korea. The system is implemented by modeling an actual 345 kV transmission system of South Korea using EMTP-RV and by measuring voltages and currents at five regions. The frequencies are estimated using our previous proposed method, a frequency estimation algorithm with gain compensation. The monitoring system implemented is used to examine frequency propagation effects and various fault conditions. Simulation results showed that the proposed system could achieve good performance regarding the frequency monitoring under both steady states and dynamic fault conditions. [ABSTRACT FROM AUTHOR]

Event traces are helpful in understanding the performance behavior of parallel applications since they allow the in-depth analysis of communication and synchronization patterns. However, the absence of synchronized clocks on most cluster systems may render the analysis ineffective because inaccurate relative event timings may misrepresent the logical event order and lead to errors when quantifying the impact of certain behaviors or confuse the users of time-line visualization tools by showing messages flowing backward in time. In our earlier work, we have developed a scalable algorithm called the controlled logical clock that eliminates inconsistent inter-process timings postmortem in traces of pure MPI applications, potentially running on large processor configurations. In this paper, we first demonstrate that our algorithm also proves beneficial in computational grids, where a single application is executed using the combined computational power of several geographically dispersed clusters. Second, we present an extended version of the algorithm that-in addition to message-passing event semantics-also preserves and restores shared-memory event semantics, enabling the correction of traces from hybrid applications. [ABSTRACT FROM AUTHOR]

In this paper, we propose and evaluate a flexible architecture for desktop grids that supports multiple task allocation policies on top of a structured P2P overlay. In our proposal, a Bag-of-Tasks application is submitted to random nodes and placed in their local queue, that is processed in a FIFO way. When a node becomes idle, a task allocation policy is executed that fetches tasks from remote nodes. The proposed architecture is flexible since it is decoupled from both the P2P middleware and the P2P overlay. A prototype of the proposed architecture was implemented on top of the JXTA middleware, using the Chord P2P search overlay. The results obtained in a 16-machine heterogeneous desktop grid show that very good performance gains are obtained with multiple task allocation policies. Also, a speedup of 9.85 was achieved for an application composed of 270 network flow balancing tasks, reducing its wallclock execution time from 32.51 min to 3.3 min. [ABSTRACT FROM AUTHOR]

Job scheduling is one of the most challenging issues in Grid resource management that strongly affects the performance of the whole Grid environment. The major drawback of the existing Grid scheduling algorithms is that they are unable to adapt with the dynamicity of the resources and the network conditions. Furthermore, the network model that is used for resource information aggregation in most scheduling methods is centralized or semi-centralized. Therefore, these methods do not scale well as Grid size grows and do not perform well as the environmental conditions change with time. This paper proposes a learning automata-based job scheduling algorithm for Grids. In this method, the workload that is placed on each Grid node is proportional to its computational capacity and varies with time according to the Grid constraints. The performance of the proposed algorithm is evaluated through conducting several simulation experiments under different Grid scenarios. The obtained results are compared with those of several existing methods. Numerical results confirm the superiority of the proposed algorithm over the others in terms of makespan, flowtime, and load balancing. [ABSTRACT FROM AUTHOR]

Computational grids have been emerging as a new paradigm for solving large complex problems over the recent years. The problem space and data set are divided into smaller pieces that are processed in parallel over the grid network and reassembled upon completion. Typically, resources are logged into a resource broker that is somewhat aware of all of the participants available on the grid. The resource broker scheme can be a bottleneck because of the amount of computational power and network bandwidth needed to maintain a fresh view of the grid. In this paper, we propose to place the load of managing the network resource discovery on to the network itself: inside of the routers. In the proposed protocol, the routers contain tables for resources similar to routing tables. These resource tables map IP addresses to the available computing resource values, which are provided through a scoring mechanism. Each resource provider is scored based on the attributes they provide such as the number of processors, processor frequency, amount of memory, hard drive space, and the network bandwidth. The resources are discovered on the grid by the protocol's discovery packets, which are encapsulated within the TCP/IP packets. The discovery packet visits the routers and look up in the resource tables until a satisfactory resource is found. The protocol is validated by simulations with five different deployment environments. [ABSTRACT FROM AUTHOR]

Cluster computing is receiving exponential popularity as a choice for high performance computing. This is mainly due to its effective cost performance ratio. Resource management systems (RMS) are the key component to manage the resources of clusters efficiently and have a very vital role in the performance of distributed parallel systems especially a job scheduling module. In this paper, we have empirically evaluated four resource management systems (SGE, TORQUE, and MAUI Scheduler and SLURM) with special focus on job scheduler component. These schedulers have been evaluated on a more comprehensive set of metrics such as throughput, CPU, memory and network utilization. Experiments were carried out on three different size testbeds with a range of scheduler configurations such as FCFS, Backfilling, Fair share and SJF scheduling techniques. A head-to-head comparison of different scheduling techniques has also been presented which highlights the effect of RMS on the performance of scheduling techniques. It has been observed from results that relative difference among the performance of scheduling techniques reached up to 63%. We conclude from the experiments that there is no single choice of RMS which can be identified as the best but SLURM performs better than others in most of the cases. [ABSTRACT FROM AUTHOR]

Desktop grid systems and applications have generated significant impacts on science and engineering. The emerging convergence of grid and peer-to-peer (P2P) computing technologies further opens new opportunities for enabling P2P Desktop Grid systems. This paper presents a taxonomy for classifying P2P desktop grid implementation paradigms, aiming to summarize the state-of-the-art technologies and explore the current and potential solution space. To have a comprehensive taxonomy for P2P desktop grid paradigms, we investigate both computational and data grid systems. Moreover, to ease the understanding, the taxonomy is applied to selected case studies of P2P desktop grid systems. The taxonomy is expected to be used as a survey of the state-of-the-art, a design map, a guideline for novice researchers, a common vocabulary, or a design space for simulation and benchmark, and to be extended as the technologies rapidly evolve. [ABSTRACT FROM AUTHOR]

User satisfaction and scheduling on grids makes predictability of response times and quality-of-service highly desirable. However, existing approaches for response-time prediction still show significant prediction errors, mostly due to problems in dynamic arrival of jobs with potentially higher priority and hard-to-anticipate packing and backfilling effects. The same problems imply that quality-of-service cannot be solved with standard approaches from communication systems. Thus, this paper presents a scheduling approach which provides a more suitable framework for service guarantees and predictability. The approach is based on coarse-grain preemption, combined with an innovative separation of job classes. Resource shares can be determined as necessary to meet target service levels. A further extension permits limited dynamic resource allocation to adapt to variations in machine load and job mixes. The feasibility of service control is demonstrated with various workloads. [ABSTRACT FROM AUTHOR]

Sequence analysis has become essential to the study of genomes and biological research in general. Basic Local Alignment Search Tool (BLAST) leads the way as the most accepted method for performing necessary query searches and analysis of discovered genes. Combating growing data sizes, with the goal of speeding up job runtimes, scientist are resorting to grid computing technologies. However, grid environments are characterized by dynamic, heterogeneous, and transient state of available resources causing major hindrance to users when trying to realize user-desired levels of service. This paper analyzes performance characteristics of NCBI BLAST on several resources and captures influence of resource characteristics and job parameters on BLAST job runtime across those resources. Obtained results are summarized as a set of principles characterizing performance of NCBI BLAST across homogeneous and heterogeneous environments. These principles are then applied and verified through creation of a grid-enabled BLAST wrapper application called Dynamic BLAST. Results show runtime savings up to 50% and resource utilization improvement of approximately 40%. [ABSTRACT FROM AUTHOR]

Concept hierarchies greatly help in the organization and reuse of information and are widely used in a variety of information systems applications. In this paper, we describe a method for efficiently storing and querying data organized into concept hierarchies and dispersed over a DHT. In our method, peers individually decide on the level of indexing according to the granularity of the incoming queries. Roll-up and drill-down operations are performed on a per-node basis in order to minimize the required bandwidth for answering queries on variable aggregation levels. We motivate our approach by applying it on a large-scale Grid system: Specifically, we apply our fully decentralized scheme that creates, queries and updates large volumes of hierarchical data on-line and replace the traditional centralized and strictly indexed information systems. Our extensive experimental results support this argument on many diverse configurations: Our system proves very efficient in skewed workloads, both over single and multiple hierarchy levels at the same time. It adapts to sudden changes in popularity and effectively stores and updates large amounts of data at very low cost. [ABSTRACT FROM AUTHOR]

Abstract  Scheduling parallel tasks in multi-cluster grid can be seen as two interdependent problems: cluster allocation and scheduling parallel task on the allocated cluster. In this paper both rigid and moldable parallel tasks are considered. We propose a theoretical model of utility-oriented parallel task scheduling in multi-cluster grid with advance reservations. On the basis of the model we present an approximation algorithm, a repair strategy based genetic algorithm and greedy heuristics MaxMax, T-Sufferage and R-Sufferage to solve the two interdependent problems. We compare the performance of these algorithms in aspect of utility optimality and timing results. Simulation results show on average the (1+α)-approximation algorithm achieves the best trade-off between utility optimality and timing. Genetic algorithm could achieve better utility than greedy heuristics and approximate algorithm at expensive time cost. Greedy heuristics do not perform equally well when adapted to different utility functions while the approximation algorithm shows its intrinsic stable performance. [ABSTRACT FROM AUTHOR]

Abstract  Advances in virtualization technology have focused mainly on strengthening the isolation barrier between virtual machines (VMs) that are co-resident within a single physical machine. At the same time, a large category of communication intensive distributed applications and software components exist, such as web services, high performance grid applications, transaction processing, and graphics rendering, that often wish to communicate across this isolation barrier with other endpoints on co-resident VMs. State of the art inter-VM communication mechanisms do not adequately address the requirements of such applications. TCP/UDP based network communication tends to perform poorly when used between co-resident VMs, but has the advantage of being transparent to user applications. Other solutions exploit inter-domain shared memory mechanisms to improve communication latency and bandwidth, but require applications or user libraries to be rewritten against customized APIs—something not practical for a large majority of distributed applications. In this paper, we present the design and implementation of a fully transparent and high performance inter-VM network loopback channel, called XenLoop, in the Xen virtual machine environment. XenLoop does not sacrifice user-level transparency and yet achieves high communication performance between co-resident guest VMs. XenLoop intercepts outgoing network packets beneath the network layer and shepherds the packets destined to co-resident VMs through a high-speed inter-VM shared memory channel that bypasses the virtualized network interface. Guest VMs using XenLoop can migrate transparently across machines without disrupting ongoing network communications, and seamlessly switch between the standard network path and the XenLoop channel. In our evaluation using a number of unmodified benchmarks, we observe that XenLoop can reduce the inter-VM round trip latency by up to a factor of 5 and increase bandwidth by a up to a factor of 6. [ABSTRACT FROM AUTHOR]

Abstract  The analysis of data usage in a large set of real traces from a high-energy physics collaboration revealed the existence of an emergent grouping of files that we coined “filecules”. This paper presents the benefits of using this file grouping for prestaging data and compares it with previously proposed file grouping techniques along a range of performance metrics. Our experiments with real workloads demonstrate that filecule grouping is a reliable and useful abstraction for data management in science Grids; that preserving time locality for data prestaging is highly recommended; that job reordering with respect to data availability has significant impact on throughput; and finally, that a relatively short history of traces is a good predictor for filecule grouping. Our experimental results provide lessons for workload modeling and suggest design guidelines for data management in data-intensive resource-sharing environments. [ABSTRACT FROM AUTHOR]

Abstract   One of the distinct characteristics of computing platforms shared by multiple users such as a cluster and a computational grid is heterogeneity on each computer and/or among computers. Temporal heterogeneity refers to variation, along the time dimension, of computing power available for a task on a computer, and spatial heterogeneity represents the variation among computers. In minimizing the average parallel execution time of a target task on a spatially heterogeneous computing system, it is not optimal to distribute the target task linearly proportional to the average computing powers available on computers. In this paper, effects of the temporal and spatial heterogeneity on performance of a target task have been analyzed in terms of the mean and standard deviation of parallel execution time. Based on the analysis results, an approach to load balancing for minimizing the average parallel execution time of a target task is described. The proposed approach whose validity has been verified through simulation considers temporal and spatial heterogeneities in addition to the average computing power on each computer. [ABSTRACT FROM AUTHOR]

Abstract  Effective overlap of computation and communication is a well understood technique for latency hiding and can yield significant performance gains for applications on high-end computers. In this paper, we propose an instrumentation framework for message-passing systems to characterize the degree of overlap of communication with computation in the execution of parallel applications. The inability to obtain precise time-stamps for pertinent communication events is a significant problem, and is addressed by generation of minimum and maximum bounds on achieved overlap. The overlap measures can aid application developers and system designers in investigating scalability issues. The approach has been used to instrument two MPI implementations as well as the ARMCI system. The implementation resides entirely within the communication library and thus integrates well with existing approaches that operate outside the library. The utility of the framework is demonstrated by analyzing communication-computation overlap for micro-benchmarks and the NAS benchmarks, and the insights obtained are used to modify the NAS SP benchmark, resulting in improved overlap. [ABSTRACT FROM AUTHOR]

Abstract   In response to a joint call from US’s NSF and UK’s EPSRC for applications that aim to utilize the combined computational resources of the US and UK, three computational science groups from UCL, Tufts and Brown Universities teamed up with a middleware team from NIU/Argonne to meet the challenge. Although the groups had three distinct codes and aims, the projects had the underlying common feature that they were comprised of large-scale distributed applications which required high-end networking and advanced middleware in order to be effectively deployed. For example, cross-site runs were found to be a very effective strategy to overcome the limitations of a single resource. The seamless federation of a grid-of-grids remains difficult. Even if interoperability at the middleware and software stack levels were to exist, it would not guarantee that the federated grids can be utilized for large scale distributed applications. There are important additional requirements for example, compatible and consistent usage policy, automated advanced reservations and most important of all co-scheduling. This paper outlines the scientific motivation and describes why distributed resources are critical for all three projects. It documents the challenges encountered in using a grid-of-grids and some of the solutions devised in response. [ABSTRACT FROM AUTHOR]

Abstract   Pervasive Grid adoption is predicated on the availability of widely deployed usable software and a user community willing to use it. Currently, widespread adoption of Grids, even within technically sophisticated communities, is limited, and determining and eliminating these barriers to adoption are essential in order for Grids to becoming widely capitalized. Through a series of face-to-face interviews conducted during the summer of 2004, we have identified issues relating to job submission, file transfer, usability, and systems management that must be resolved in order to improve the usability of Grid infrastructures. The background to these issues and some possible solutions are described in this paper. [ABSTRACT FROM AUTHOR]

Abstract   The LTER Grid Pilot Study was conducted by the National Center for Supercomputing Applications, the University of New Mexico, and Michigan State University, to design and build a prototype grid for the ecological community. The featured grid application, the Biophony Grid Portal, manages acoustic data from field sensors and allows researchers to conduct real-time digital signal processing analysis on high-performance systems via a web-based portal. Important characteristics addressed during the study include the management, access, and analysis of a large set of field collected acoustic observations from microphone sensors, single signon, and data provenance. During the development phase of this project, new features were added to standard grid middleware software and have already been successfully leveraged by other, unrelated grid projects. This paper provides an overview of the Biophony Grid Portal application and requirements, discusses considerations regarding grid architecture and design, details the technical implementation, and summarizes key experiences and lessons learned that are generally applicable to all developers and administrators in a grid environment. [ABSTRACT FROM AUTHOR]

Abstract   Gridcast is an R&D project investigating grid ideas and technologies in the broadcasting technical infrastructure. In this paper I discuss the business and technical issues in building infrastructures to support broadcasters and outline the structure of the Gridcast grid-based service oriented architecture for broadcasting playout support. [ABSTRACT FROM AUTHOR]

The home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problemsThe home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote “independent living” specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers’ contract limitations and customers’ needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified $$(1 + \lambda )$$(1+λ) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problems [ABSTRACT FROM AUTHOR]