Chirp: a practical global filesystem for cluster and Grid computing

Traditional distributed filesystem technologies designed for local and campus area networks do not adapt well to wide area Grid computing environments. To address this problem, we have designed the Chirp distributed filesystem, which is designed from the ground up to meet the needs of Grid computing. Chirp is easily deployed without special privileges, provides strong and flexible security mechanisms, tunable consistency semantics, and clustering to increase capacity and throughput. We demonstrate that many of these features also provide order-of-magnitude performance increases over wide area networks. We describe three applications in bioinformatics, biometrics, and gamma ray physics that each employ Chirp to attack large scale data intensive problems.     

Distributed computing as a virtual supercomputer: Tools to run and manage large-scale BOINC simulations

Distributed computing (DC) projects tackle large computational problems by exploiting the donated processing power of thousands of volunteered computers, connected through the Internet. To efficiently employ the computational resources of one of world's largest DC efforts, GPUGRID, the project scientists require tools that handle hundreds of thousands of tasks which run asynchronously and generate gigabytes of data every day. We describe RBoinc, an interface that allows computational scientists to embed the DC methodology into the daily work-flow of high-throughput experiments. By extending the Berkeley Open Infrastructure for Network Computing (BOINC), the leading open-source middleware for current DC projects, with mechanisms to submit and manage large-scale distributed computations from individual workstations, RBoinc turns distributed grids into cost-effective virtual resources that can be employed by researchers in work-flows similar to conventional supercomputers. The GPUGRID project is currently using RBoinc for all of its in silico experiments based on molecular dynamics methods, including the determination of binding free energies and free energy profiles in all-atom models of biomolecules.     

On the design of global object space for efficient multi-threading Java computing on clusters

The popularity of Java and recent advances in compilation and execution technology for Java are making the language one of the preferred ones in the field of high-performance scientific and engineering computing. A distributed Java Virtual Machine supports transparent parallel execution of multi-threaded Java programs on a cluster of computers. It provides an alternative platform for high-performance scientific computations. In this paper, we present the design of a global object space for a distributed JVM. It virtualizes a single Java object heap across machine boundaries to facilitate transparent object accesses. We leverage runtime object connectivity information to detect distributed shared objects (DSOs) that are reachable from threads at different nodes to facilitate efficient memory management in the distributed JVM. Based on the concept of DSO, we propose a framework to characterize object access patterns, along three orthogonal dimensions. With this framework, we are able to effectively calibrate the runtime memory access patterns and dynamically apply optimized cache coherence protocols to minimize consistency maintenance overhead. The optimization devices include an object home migration method that optimizes the single-writer access pattern, synchronized method migration that allows the execution of a synchronized method to take place remotely at the home node of its locked object, and connectivity-based object pushing that uses object connectivity information to optimize the producer–consumer access pattern. Several benchmark applications in scientific computing have been tested on our distributed JVM. We report the performance results and give an in-depth analysis of the effects of the proposed adaptive solutions.     

Evolvable agents,a fine grained approach for distributed evolutionary computing: walking towards the peer-to-peer computing frontiers

In this work we propose a fine grained approach with self-adaptive migration rate for distributed evolutionary computation. Our target is to gain some insights on the effects caused by communication when the algorithm scales. To this end, we consider a set of basic topologies in order to avoid the overlapping of algorithmic effects between communication and topological structures. We analyse the approach viability by comparing how solution quality and algorithm speed change when the number of processors increases and compare it with an Island model based implementation. A finer-grained approach implies a better chance of achieving a larger scalable system; such a feature is crucial concerning large-scale parallel architectures such as peer-to-peer systems. In order to check scalability, we perform a threefold experimental evaluation of this model: first, we concentrate on the algorithmic results when the problem scales up to eight nodes in comparison with how it does following the Island model. Second, we analyse the computing time speedup of the approach while scaling. Finally, we analyse the network performance with the proposed self-adaptive migration rate policy that depends on the link latency and bandwidth. With this experimental setup, our approach shows better scalability than the Island model and a equivalent robustness on the average of the three test functions under study.     

GridSAT: Design and Implementation of a Computational Grid Application

We present the latest instantiation of GridSAT [1], a distributed and complete satisfiability solver that is explicitly designed to aggregate Grid resources for application performance. GridSAT was previously shown to outperform the state-of-the-art sequential solvers. In this work, we explore the unprecedented solving power GridSAT enables through algorithmic and implementation innovations. We describe the implementation techniques that allow GridSAT to leverage a variety of high-end batch-scheduled resources, clusters, interactive workstations, and personal computing resources through autonomous scheduling, checkpoint scheduling, and work migration. These innovations have allowed GridSAT to solve a set of ‘hard’ and previously unsolved industrial and community satisfiability problems. In addition to this new solution power, GridSAT also outperforms the otherwise highest performance general solvers on the annual SAT competition [21] performance benchmarks.This work was supported by grants from the National Science Foundation, numbered CAREER-0093166, EIA-9975020, ACI-0103759, and CCR-0331654 and by the San Diego Supercomputer Center and the TeraGrid project.     

Scheduling in a dynamic heterogeneous distributed system using estimation error

In real-world dynamic heterogeneous distributed systems, allocating tasks to processors can be an inefficient process, due to the dynamic nature of the resources, and the tasks to be processed. The information about these tasks and resources is not known a priori, and thus must be estimated online. We utilize the accuracy of these estimates, and when combined with different objectives, such as minimizing makespan and evenly distributing load, naturally gives rise to a family of four different scheduling algorithms. The algorithms have been implemented on a real-world heterogeneous distributed system with up to 90 processors. A set of real-world problems from the areas of cryptography, bioinformatics, and biomedical engineering were used as a test-set to measure the effectiveness of the scheduling algorithms. We have found that considering estimation error when allocating tasks to processors can provide more efficient solutions, than when estimation error is not considered. We have found that using a simple heuristic, combined with estimation error, can in some cases provide solutions approaching the efficiency of complicated well-known evolutionary algorithms.     

Model-driven auto-scaling of green cloud computing infrastructure

Cloud computing can reduce power consumption by using virtualized computational resources to provision an application’s computational resources on demand. Auto-scaling is an important cloud computing technique that dynamically allocates computational resources to applications to match their current loads precisely, thereby removing resources that would otherwise remain idle and waste power. This paper presents a model-driven engineering approach to optimizing the configuration, energy consumption, and operating cost of cloud auto-scaling infrastructure to create greener computing environments that reduce emissions resulting from superfluous idle resources. The paper provides four contributions to the study of model-driven configuration of cloud auto-scaling infrastructure by (1) explaining how virtual machine configurations can be captured in feature models, (2) describing how these models can be transformed into constraint satisfaction problems (CSPs) for configuration and energy consumption optimization, (3) showing how optimal auto-scaling configurations can be derived from these CSPs with a constraint solver, and (4) presenting a case study showing the energy consumption/cost reduction produced by this model-driven approach.     

Javelin: Parallel computing on the internet

Java offers the basic infrastructure needed to integrate computers connected to the Internet into a seamless distributed computational resource: an infrastructure for running coarse-grained parallel applications on numerous, anonymous machines. First, we sketch such a resource’s essential technical properties. Then, we present a prototype of Javelin, an infrastructure for global computing. The system is based on Internet software that is interoperable, increasingly secure, and ubiquitous: Java-enabled Web technology. Ease of participation is seen as a key property for such a resource to realize the vision of a multiprocessing environment comprising thousands of computers. Javelin’s architecture and implementation require participants to have access to only a Java-enabled Web browser. Experimental results are given in the form of a Mersenne Prime application and a ray-tracing application that run on a heterogeneous network of several parallel machines, workstations, and PCs. Two key areas of current research, fault-tolerance and scalability, are subsequently explored briefly.     

Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system

We present a multi-heuristic evolutionary task allocation algorithm to dynamically map tasks to processors in a heterogeneous distributed system. It utilizes a genetic algorithm, combined with eight common heuristics, in an effort to minimize the total execution time. It operates on batches of unmapped tasks and can preemptively remap tasks to processors. The algorithm has been implemented on a Java distributed system and evaluated with a set of six problems from the areas of bioinformatics, biomedical engineering, computer science and cryptography. Experiments using up to 150 heterogeneous processors show that the algorithm achieves better efficiency than other state-of-the-art heuristic algorithms.     

Cooperative power-aware scheduling in grid computing environments

Energy usage and its associated costs have taken on a new level of significance in recent years. Globally, energy costs that include the cooling of server rooms are now comparable to hardware costs, and these costs are on the increase with the rising cost of energy. As a result, there are efforts worldwide to design more efficient scheduling algorithms. Such scheduling algorithm for grids is further complicated by the fact that the different sites in a grid system are likely to have different ownerships. As such, it is not enough to simply minimize the total energy usage in the grid; instead one needs to simultaneously minimize energy usage between all the different providers in the grid. Apart from the multitude of ownerships of the different sites, a 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. In this paper, we propose a cooperative, power-aware game theoretic solution to the job scheduling problem in grids. We discuss our cooperative game model and present the structure of the Nash Bargaining Solution. Our proposed scheduling scheme maintains a specified Quality of Service (QoS) level and minimizes energy usage between all the providers simultaneously; energy usage is kept at a level that is sufficient to maintain the desired QoS level. Further, the proposed algorithm is fair to all users, and has robust performance against inaccuracies in performance prediction information.     

Notes towards a definition of human-centred computing

Current usage of the expression human-centred in computing contexts suffers from a lack of clarity, and involves internal contradictions. It is not enough to base the concept of human-centredness on ideas of social utility, collaborative working or human controllability. However, the concept of human action (which embodies reference to human freedom) provides a theoretical underpinning to human-centredness by combining, from a human standpoint, concern with process and concern with goals. This has consequences for the design process, prompting us to include new concerns in our system specifications and providing some pointers towards human-centred design methodology.     

Distributed computing with advice: information sensitivity of graph coloring

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring. A preliminary version of this paper appeared in the proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), July 2007. A part of this work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais, as a postdoctoral fellow. P. Fraigniaud received additional support from the ANR project ALADDIN. A. Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.     

企业私有云计算基础架构研究与设计

随着信息化在企业中的深入运用,传统IT架构慢慢显现出弊端：基础资源利用率偏低、管理上太分散;面对管理或业务出现变化时,旧的业务系统难以快速响应.怎样实现业务同IT建设的协同,怎样对IT系统现有数据进行利用,这些都成为当下企业立刻要解决的.“云计算”作为眼下信息领域炙手可热的技术,一方面它能对现有IT资源进行很好地整合,另一方面面对业务变化时它能实现IT建设的迅速响应,因此它的研发为解决企业的上述难题提供了希望.     

Cloud-DLS: Dynamic trusted scheduling for Cloud computing

Clouds are rapidly becoming an important platform for scientific applications. In the Cloud environment with uncountable numeric nodes, resource is inevitably unreliable, which has a great effect on task execution and scheduling. In this paper, inspired by Bayesian cognitive model and referring to the trust relationship models of sociology, we first propose a novel Bayesian method based cognitive trust model, and then we proposed a trust dynamic level scheduling algorithm named Cloud-DLS by integrating the existing DLS algorithm. Moreover, a benchmark is structured to span a range of Cloud computing characteristics for evaluation of the proposed method. Theoretical analysis and simulations prove that the Cloud-DLS algorithm can efficiently meet the requirement of Cloud computing workloads in trust, sacrificing fewer time costs, and assuring the execution of tasks in a security way.     

An algorithm for computing the diagnoses with minimal cardinality in a distributed system

In fault diagnosis, the set of minimal diagnoses is commonly calculated. However, due to for example limited computation resources, the search for the set of minimal diagnoses is in some applications focused on to the smaller set of diagnoses with minimal cardinality. The key contribution in this paper is an algorithm that calculates the diagnoses with minimal cardinality in a distributed system. The algorithm is constructed such that the computationally intensive tasks are distributed to the different units in the distributed system, and thereby reduces the need for a powerful central diagnostic unit.     

On the complexity of global computation in the presence of link failures: the general case

Summary This paper presents (m logn) and (mn) messages lower bounds on the problem of computing a gobal sensitive function in biderectional networks with link failures (i.e., dynamically changing topology), wheren andm are the total number of nodes and links in the network. The (m logn) lower bound is under the assumption thatn is a-priori known to the nodes, while the second bound is for the case in which such knowledge is not available. A global sensitive function ofn variables is a function that may not be computed without the knowledge of the values of all then variables (e.g. maximum, sum, etc). Thus, computing such a function at one node of a distributed network requires this node to communicate with every other node in the network. Though lower bounds higher than (m) messages are known for this problem in the context of link failures, none holds for dense bidirectional networks. Moreover, we are not aware of any other nontrivial lower bound higher than (m) for dense bidirectional networks. Yehuda Afek received a B.Sc. in Electrical Engineering from the Technion and an M.Sc. and Ph.D. in Computer Science from the University of California, Los-Angeles. In 1985 he joined the Distributed Systems Research Department in AT&T Bell Laboratories as a Member of Technical Staff. In 1988 he joined the Computer Science Department in Tel-Aviv University, where he now holds a permanent position. From 1989 to 1994 he was also a consultant for AT&T Bell Laboratories. His interests include communication protocols, distributed computing and asynchronous shared memory systems. Danny Hendler was born in Kiryat-Haim near Haifa, Israel, on April 17th 1961. He received his B.Sc. and M.Sc. in Computer Science from Tel-Aviv University, Israel, in 1986 and 1993, respectively. In the past 8 years he has worked as a free lance software-consultant, specializing mainly in communication, telephony and voice-mail applications.