Active Grid Information Server for grid computing

We describe the Active Grid Information Server for performing expressive resource discovery searches and resource management in a grid environment. We represent server meta-data, such as their CPU power, storage capacity and bandwidth as points in a multi-dimensional space and then express queries as predicates over these points. The design of the system is driven by its application as a part of the information infrastructure for computational grids. Such grids provide an infrastructure for sharing computing resources; an information infrastructure is their inherent part which collects resource data and provides search functionality. Our approach complements current solutions such as MDS by adding Event Condition Action rules and an ability to efficiently handle dynamic attributes. An Event Condition Action rule-based system can support ad hoc, adaptive, flexible, and dynamic schedulers that are modifiable at runtime. We evaluate our Active Grid Information Server by evaluating Event Condition Action rules for termination, confluence, and conflict.     

Efficient Smoke Simulation on Curvilinear Grids

We present an efficient approach for performing smoke simulation on curvilinear grids. Our technique is based on a fast unconditionally‐stable advection algorithm and on a new and efficient solution to enforce mass conservation. It uses a staggered‐grid variable arrangement, and has linear cost on the number of grid cells. Our method naturally integrates itself with overlapping‐grid techniques, lending to an efficient way of producing highly‐realistic animations of dynamic scenes. Compared to approaches based on regular grids traditionally used in computer graphics, our method allows for better representation of boundary conditions, with just a small increment in computational cost. Thus, it can be used to evaluate aerodynamic properties, possibly enabling unexplored applications in computer graphics, such as interactive computation of lifting forces on complex objects. We demonstrate the effectiveness of our approach, both in 2‐D and 3‐D, through a variety of high‐quality smoke animations.     

Towards efficient data distribution on computational desktop grids with BitTorrent

Datacentric applications are still a challenging issue for large-scale distributed computing systems. The emergence of new protocols and software for collaborative content distribution over the Internet offers a new opportunity for efficient and fast delivery of a high volume of data. This paper presents an evaluation of the BitTorrent protocol for computational desktop grids. We first present a prototype of a generic subsystem dedicated to data management and designed to serve as a building block for any desktop grid system. Based on this prototype we conduct experiments to evaluate the potential of BitTorrent compared to a classical approach based on FTP data server. The preliminary results obtained with a 65-node cluster measure the basic characteristics of BitTorrent in terms of latency and bandwidth and evaluate the scalability of BitTorrent for the delivery of large input files. Moreover, we show that BitTorrent has a considerable latency overhead compared to FTP but clearly outperforms FTP when distributing large files or files to a high number of nodes. Tests on a synthetic application show that BitTorrent significantly increases the communication/computation ratio of the applications eligible to run on a desktop grid system.     

Boosting gLite with cloud augmented volunteer computing

The paper details the result of the EU FP7 EDGI project focusing on the cloud developments and usability improvements. Volunteer desktop grids, like BOINC, are designed to handle millions of parameter sweep type jobs and millions of desktop machines as worker nodes. Seamless transfer of gLite jobs to desktop grids was already implemented by EDGI; however this huge number of DG resources could not be utilized efficiently due to slow completion time caused by unpredictable behavior of the volunteer resources. The paper details how clouds have been utilized to shorten completion time on the EDGeS@home volunteer desktop grid to boost the performance of the supported gLite VO and also details how this service can be exploited by the gLite user communities of EGI (European Grid Initiative) all over Europe.     

The grid, the load and the gradient

An important concern for an efficient use of distributed computing is dealing with load balancing to ensure all available nodes and their shared resources are equally exploited. In large scale systems such as volunteer computing platforms and desktop grids, centralized solutions may introduce performance bottlenecks and single points of failure. Accordingly fully distributed alternatives have been considered, due to their inherent robustness and reliability. In extremely dynamic contexts, scheduling middlewares should adapt their job scheduling policies to the actual availability and overcome the volatility and heterogeneity typical of the underlying nodes. To deal with the dynamicity of a large pool of resources, self-organizing and adaptive solutions represent a promising research direction. Solutions based on bio-inspired methodologies are particularly suitable, as they inherently provide the desired features. In this paper we present a fully distributed load balancing mechanism, called ozmos, which aims at increasing the efficiency of distributed computing systems through peer-to-peer interaction between nodes. The proposed algorithm is based on a Chord overlay, and employs ant-like agents to spread information about the current load on each node, to reschedule tasks from overloaded systems to underloaded ones, and to relocate incompatible tasks on suitable resources in heterogeneous grids. By means of several evaluation scenarios we demonstrate the effectiveness of the proposed solution in achieving system-wide load balancing, both with homogeneous and heterogeneous resources. In particular we consider the load balancing performance of our approach, its scalability, as well as its communication efficiency.     

基于模糊粒子群优化的计算网格工作调度算法

网格计算是利用网络把分散的计算资源组织起来解决复杂问题的计算模式，工作调度是待解决的主要问题之一。本文提出一种基于模糊粒子群优化的网格计算工作调度算法，该算法利用模糊粒子群优化动态地产生网格计算工作调度的优化方案，使现有计算资源完成所有工作的时间最小化。实验结果表明，与基于遗传算法、模拟退火、蚁群算法的工作调度方法相比，所提出的算法在时间和精度上具有一定的优势。     

A resource management and fault tolerance services in grid computing

In grid computing, resource management and fault tolerance services are important issues. The availability of the selected resources for job execution is a primary factor that determines the computing performance. In this paper, we propose a resource manager for optimal resource selection. Our resource manager automatically selects the set of optimal resources among candidate resources that achieves optimal performance using a genetic algorithm. Typically, the probability of a failure is higher in the grid computing than in a traditional parallel computing and the failure of resources affects job execution fatally. Therefore, a fault tolerance service is essential in computational grids. And grid services are often expected to meet some minimum levels of Quality of Service (QoS) for a desirable operation. To address this issue, we also propose a fault tolerance service that satisfies QoS requirements. We extend the definition of failures from the conventional notion of failures in distribute systems in order to provide a fault tolerance service that deals with various types of resource failures, which include process failures, processor failures, and network failures. We also design and implement a fault detector and a fault manager. The implementation and simulation results indicate that our approaches are promising in that (1) the resource manager finds the optimal set of resources that guarantees efficient job execution, (2) the fault detector detects the occurrence of resource failures and (3) the fault manager guarantees that the submitted jobs complete and the performance of job execution is improved due to job migration even if some failures occur.     

Using interpolation to improve path planning: The Field D* algorithm

We present an interpolation‐based planning and replanning algorithm for generating low‐cost paths through uniform and nonuniform resolution grids. Most grid‐based path planners use discrete state transitions that artificially constrain an agent's motion to a small set of possible headings (e.g., 0, π/4, π/2, etc.). As a result, even “optimal” grid‐based planners produce unnatural, suboptimal paths. Our approach uses linear interpolation during planning to calculate accurate path cost estimates for arbitrary positions within each grid cell and produce paths with a range of continuous headings. Consequently, it is particularly well suited to planning low‐cost trajectories for mobile robots. In this paper, we introduce a version of the algorithm for uniform resolution grids and a version for nonuniform resolution grids. Together, these approaches address two of the most significant shortcomings of grid‐based path planning: the quality of the paths produced and the memory and computational requirements of planning over grids. We demonstrate our approaches on a number of example planning problems, compare them to related algorithms, and present several implementations on real robotic systems.     

基于角色的多Agent的网格资源管理框架与分配策略

提出了一种适应计算网格分布动态环境的基于角色的多代理的资源管理框架,其核心的三种角色代理都采用BDI（Belief,Desire,Intention）代理模型,利用BDI代理的智能交互,进行协同合作以管理复杂的网格资源。还初步探讨了基于此框架的网格资源优化分配的策略和方法。     

一种自适应的网格计算资源组织与发现机制

资源发现是网格计算中一个重要的研究问题.计算资源作为支撑网格应用的基础资源,其组织与发现机制尤为重要,但现有的技术和方法在效率、可伸缩性、自适应的动态演化以及对查询方式的支持方面仍有较大的局限性.基于网格应用对计算资源需求特征的深入分析,通过引入计算资源的主属性概念,按照平衡二叉排序树对计算资源进行分类组织,提出基于资源分类树(resource category tree,简称RCT)的资源组织与发现机制.首先,讨论了基于RCT对计算资源的组织机制,包括RCT的基本概念和原理、支持资源动态加入和退出以及资源状态动态变化的自组织机制、负载感知的自适应演化机制和基于备份节点的容错机制;然后,在基于RCT的资源组织结构下,设计了支持4种查询方式的搜索算法,并对算法的复杂度进行了分析;最后,通过多组仿真实验对RCT的性能进行了评估.     

Game-Theoretic Approach for Load Balancing in Computational Grids

Load balancing is a very important and complex problem in computational grids. A computational grid differs from traditional high-performance computing systems in the heterogeneity of the computing nodes, as well as the communication links that connect the different nodes together. There is a need to develop algorithms that can capture this complexity yet can be easily implemented and used to solve a wide range of load-balancing scenarios. In this paper, we propose a game-theoretic solution to the grid load-balancing problem. The algorithm developed combines the inherent efficiency of the centralized approach and the fault-tolerant nature of the distributed, decentralized approach. We model the grid load-balancing problem as a noncooperative game, whereby the objective is to reach the Nash equilibrium. Experiments were conducted to show the applicability of the proposed approaches. One advantage of our scheme is the relatively low overhead and robust performance against inaccuracies in performance prediction information.     

Automatic benchmark profiling through advanced workflow‐based trace analysis

Benchmarking has proven to be crucial for the investigation of the behavior and performances of a system. However, the choice of relevant benchmarks still remains a challenge. To help the process of comparing and choosing among benchmarks, we propose a solution for automatic benchmark profiling. It computes unified benchmark profiles reflecting benchmarks' duration, function repartition, stability, CPU efficiency, parallelization, and memory usage. Our approach identifies the needed system information for profile computation and collects it from execution traces captured without benchmark code modifications. It structures profile computation as a reproducible workflow for automatic trace analysis, which efficiently manages important trace volumes. In this paper, we report on the design and the implementation of our approach, which involves the collection and analysis of about 500 GB of trace data coming from 2 different platforms (an x86 desktop machine and the Juno SoC board). The computed benchmark profiles provide valuable insights about the benchmarks' behavior and help compare different benchmarks on the same platform as well as the behavior of the same benchmark on different platforms.     

Decentralized proactive resource allocation for maximizing throughput of P2P Grid

Peer-to-peer Desktop Grids provide integrated computational resources by leveraging autonomous desktop computers located at the edge of the Internet to offer high computing power. The arbitrary arrival and serving rates of tasks on peers impedes the high throughput in large-scale P2P Grids. We propose a novel autonomous resource allocation scheme, which can maximize the throughput of self-organizing P2P Grid systems. Our design possesses three key features: (1) high adaptability to dynamic environment by proactive and convex-optimal estimation of nodes’ volatile states; (2) minimized task migration conflict probability (upper bound can be limited to 2%) of over-utilized nodes individually shifting surplus loads; (3) a load-status conscious gossip protocol for optimizing distributed resource discovery effect. Based on a real-life user’s workload and capacity distribution, the simulation results show that our approach could get significantly improved throughput with 23.6–47.1% reduction on unprocessed workload compared to other methods. We also observe high scalability of our solution under dynamic peer-churning situations.     

Zorilla: a peer‐to‐peer middleware for real‐world distributed systems

The inherent complex nature of current distributed computing architectures hinders the widespread adoption of these systems for mainstream use. In general, users have access to a highly heterogeneous set of compute resources, which may include clusters, grids, desktop grids, clouds, and other compute platforms. This heterogeneity is especially problematic when running parallel and distributed applications. Software is needed which easily combines as many resources as possible into one coherent computing platform. In this paper, we introduce Zorilla: peer‐to‐peer (P2P) middleware that creates a single distributed environment from any available set of compute resources. Zorilla imposes minimal requirements on the resource used, is platform independent, and does not rely on central components. In addition to providing functionality on bare resources, Zorilla can exploit locally available middleware. Zorilla explicitly supports distributed and parallel applications, and allows resources from multiple sites to cooperate in a single computation. Zorilla makes extensive use of both virtualization and P2P techniques. We will demonstrate how virtualization and P2P combine into a simple design, while enhancing functionality and ease of use. Together, these techniques bring our goal a step closer: transparent, easy use of resources, even on very heterogeneous distributed systems. Copyright © 2011 John Wiley & Sons, Ltd.     

Peer-to-peer for computational grids: mixing clusters and desktop machines

This paper presents a Peer-to-Peer (P2P) infrastructure that supports a large scale grid. The P2P infrastructure is implemented in Java and federates Java Virtual Machines (JVMs) for computation. The management of shared JVMs is decentralized, self-organized, and configurable.The P2P infrastructure was deployed as a permanent desktop grid, with which we have achieved a computation record by solving the NQueens problem for 25 queens. Thereafter, we have mixed this desktop grid with five highly heterogeneous clusters from the Grid’5000 platform. We analyze the behavior of this thousand CPU grid with two communicating applications: NQueens and Flow-Shop.     

Brokering strategies in computational grids using stochastic prediction models

In this paper we propose a new routing policy to route jobs to clusters in computational grids. This routing policy is based on index tables computed at each cluster. These tables can be computed off-line or on-line. Their computations use predictions about the average future behavior of the grid. We show how can be used in practice for task allocations in computational grids. We also report numerous simulations providing numerical evidence of the efficiency of our index routing policy compared with the classical brokers used in most production grids today.     

网格技术与信息资源存储和共享

“网格“是一个新出现的概念,代表了一种先进的技术和基础设施,是继Internet之后又一次重大的科技进步.网格旨在使互联网上所有资源(计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等)实现全面共享与协同工作,使整个因特网整合成一台巨大的超级计算机,为用户提供“即连即用“式的服务.介绍了网格的内涵、特点及两种主要的网格体系结构,对网格环境下信息资源的存储和共享进行了论述.     

Semantics and knowledge grids: building the next-generation grid

Just as the Internet is shifting its focus from information and communication to a knowledge delivery infrastructure, we see the Grid moving from computation and data management to a pervasive, worldwide knowledge management infrastructure. We have the technology to store and access data, but we seem to lack the ability to transform data tombs into useful data and extract knowledge from them. We review some of the current and future technologies that will impact the architecture, computational model, and applications of future grids. We attempt to forecast the evolution of computational grids into what we call the next-generation grid, with a particular focus on the use of semantics and knowledge discovery techniques and services. We propose a comprehensive software architecture for the next-generation grid, which integrates currently available services and components in Semantic Web, Semantic Grid, P2P, and ubiquitous systems. We'll also discuss a case study that shows how some new technologies can improve grid applications.     

Hierarchical line integration

This paper presents an acceleration scheme for the numerical computation of sets of trajectories in vector fields or iterated solutions in maps, possibly with simultaneous evaluation of quantities along the curves such as integrals or extrema. It addresses cases with a dense evaluation on the domain, where straightforward approaches are subject to redundant calculations. These are avoided by first calculating short solutions for the whole domain. From these, longer solutions are then constructed in a hierarchical manner until the designated length is achieved. While the computational complexity of the straightforward approach depends linearly on the length of the solutions, the computational cost with the proposed scheme grows only logarithmically with increasing length. Due to independence of subtasks and memory locality, our algorithm is suitable for parallel execution on many-core architectures like GPUs. The trade-offs of the method--lower accuracy and increased memory consumption--are analyzed, including error order as well as numerical error for discrete computation grids. The usefulness and flexibility of the scheme are demonstrated with two example applications: line integral convolution and the computation of the finite-time Lyapunov exponent. Finally, results and performance measurements of our GPU implementation are presented for both synthetic and simulated vector fields from computational fluid dynamics.