Search

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]

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]

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 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]

'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]

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]

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]

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]

In a world where many users rely on the Web for up-to-date personal and business information and transactions, it is fundamental to build Web systems that allow service providers to differentiate user expectations with multi-class Service Level Agreements (SLAs). In this paper we focus on the server components of the Web, by implementing QoS principles in a Web-server cluster that is, an architecture composed by multiple servers and one front-end node called Web switch. We first propose a methodology to determine a set of confident SLAs in a real Web cluster for multiple classes of users and services. We then decide to implement at the Web switch level all mechanisms that transform a best-effort Web cluster into a QoS-enhanced system. We also compare three QoS-aware policies through experimental results in a real test-bed system. We show that the policy implementing all QoS principles allows a Web content provider to guarantee the contractual SLA targets also in severe load conditions. Other algorithms lacking some QoS principles cannot be used for respecting SLA constraints although they provide acceptable performance for some load and system conditions. [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]

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]

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]

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]

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]

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]

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]

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]

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]

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   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   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]

This paper describes a novel technique for establishing a virtual file system that allows data to be transferred user-transparently and on-demand across computing and storage servers of a computational grid. Its implementation is based on extensions to the Network File System (NFS) that are encapsulated in software proxies. A key differentiator between this approach and previous work is the way in which file servers are partitioned: while conventional file systems share a single (logical) server across multiple users, the virtual file system employs multiple proxy servers that are created, customized and terminated dynamically, for the duration of a computing session, on a per-user basis. Furthermore, the solution does not require modifications to standard NFS clients and servers. The described approach has been deployed in the context of the PUNCH network-computing infrastructure, and is unique in its ability to integrate unmodified, interactive applications (even commercial ones) and existing computing infrastructure into a network computing environment. Experimental results show that: (1) the virtual file system performs well in comparison to native NFS in a local-area setup, with mean overheads of 1 and 18%, for the single-client execution of the Andrew benchmark in two representative computing environments, (2) the average overhead for eight clients can be reduced to within 1% of native NFS with the use of concurrent proxies, (3) the wide-area performance is within 1% of the local-area performance for a typical compute-intensive PUNCH application (SimpleScalar), while for the I/O-intensive application Andrew the wide-area performance is 5.5 times worse than the local-area performance. [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]

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]

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]

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]

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]

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]

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]

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]

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  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  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  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   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   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   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]

Grid computing systems are emerging as a computing infrastructure that will enable the use of wide-area network computing systems for a variety of challenging applications. One of these is the ever increasing demand for multimedia from users engaging in a wide range of activities such as scientific research, education, commerce, and entertainment. To provide an adequate level of service to multimedia applications, it is often necessary to simultaneously allocate resources including predetermined capacities from interconnecting networks to the applications. The simultaneous allocation of resources is often referred to as co-allocation in the Grid literature. In this paper, we formally define the co-allocation problem and propose a novel scheme called synchronous queuing (SQ) for implementing co-allocation with quality of service (QoS) assurances in Grids. Unlike existing approaches, SQ does not require advance reservation capabilities at the resources. This enables an SQ-based approach to over subscribe the resources and hence improve resource utilization. The simulation studies performed to evaluate SQ indicate that it outperforms an QoS-based scheme with strict admission control by a significant margin. [ABSTRACT FROM AUTHOR]

Smart grid requires sharing sensitive data to external researchers. Attribute encryption is a common technique used in data sharing. Unfortunately, existing revocation mechanisms do not consider the following two issues. One is that the revoked user may save intermediate values computed in the past to illegally decrypt the updated cipher text. The other is that the update parameters of keys can be leaked to the revoked user, which leads to revocation failure. To address the above issues, we propose a verifiable outsourcing decryption and data sharing scheme, in which we introduce version parameters of ciphertexts and keys, and associate the update parameters of keys with each user to achieve security-enhanced revocation. In addition, a formal security proof is given under the DBDH assumption. Finally, we evaluate the performance of the scheme and the results show that the proposed scheme is more effective than current schemes. [ABSTRACT FROM AUTHOR]

Traditional centralized cloud services face challenges, such as high communication delay, single point of failure, etc. Edge computing is one of distributed computing services in which resources are placed closer to users, and thus is more robust and can reduce communication delay. Although outsourcing data to the edge servers can bring great convenience, it also brings serious security threats. In order to provide image retrieval while ensuring users' data privacy, a privacy-preserving content-based image retrieval scheme in edge environment is proposed. Considering the distributed characteristics of edge environment and the requirement of lightweight computing, we design a secure interaction protocol completed through the collaborative cooperation of two or more edge servers. This scheme not only protects data privacy, but also has low communication overhead and delay as well as low computing complexity, therefore it is more suitable for edge computing environment. Theoretical analysis and experiments show that our scheme has high security, retrieval accuracy and efficiency. [ABSTRACT FROM AUTHOR]

The sensitivity analysis of a Cellular Genetic Algorithm (CGA) with local search is used to design a new and faster heuristic for the problem of mapping independent tasks to a distributed system (such as a computer cluster or grid) in order to minimize makespan (the time when the last task finishes). The proposed heuristic improves the previously known Min-Min heuristic. Moreover, the heuristic finds mappings of similar quality to the original CGA but in a significantly reduced runtime (1,000 faster). The proposed heuristic is evaluated across twelve different classes of scheduling instances. In addition, a proof of the energy-efficiency of the algorithm is provided. This convergence study suggests how additional energy reduction can be achieved by inserting low power computing nodes to the distributed computer system. Simulation results show that this approach reduces both energy consumption and makespan. [ABSTRACT FROM AUTHOR]

n efficient function of a complicated or dynamic high performance computing environment requires the scheduler to dispatch the submitted tasks according to the identification of the idling resources. A derivative problem is to provide accurate forecasts of the tasks runtimes. This is usually needed to assist scheduling policies and fine tune scheduling decisions, and also used for future planning of resource allocation when conducting advance reservation. However, the characteristics of the existing prediction strategies determine that the sole strategy is not appropriate for all kinds of heterogeneous tasks. Aiming at this problem, a multi-strategy collaborative prediction model (MSCPM) for the runtime of online tasks is proposed, and a novel concept named Prediction Accuracy Assurance ( PAA) as a criterion is introduced to quantitatively evaluate the precision of the prediction runtime provided by a specific prediction strategy. MSCPM uses the existing strategies of prediction runtime to generate multiple collaborative prediction schemes and takes the prediction result of the scheme which provides the optimal PAA. We evaluate the performance of the proposed model which recently integrates four simple yet widely used time series prediction strategies based on the gathered traces of three different tasks. The analysis results show that MSCPM can aggregate the superiority of the various existing prediction strategies and the evaluation criterion can pick out the near-optimal one within the prediction results provided by the integrated strategies. MSCPM provides an enhanced accuracy assurance for the prediction runtime of the online tasks in the computing environments. [ABSTRACT FROM AUTHOR]