Narrow Results

The dominant trend in scientific computing today is the establishment of platforms that span multiple institutions to support applications at unprecedented scales. On most distributed computing platforms a requirement to achieve high performance is the careful scheduling of distributed application components onto the available resources. While scheduling has been an active area of research for many decades most of the platform models traditionally used in scheduling research, and in particular network models, break down for platforms spanning wide-area networks. In this paper we examine network modeling issues for large-scale platforms from the perspective of scheduling. The main challenge we address is the development of models that are sophisticated enough to be more realistic than those traditionally used in the field, but simple enough that they are still amenable to analysis. In particular, we discuss issues of bandwidth sharing and topology modeling. Also, while these models can be used to define and reason about realistic scheduling problems, we show that they also provide a good basis for fast simulation, which is the typical method to evaluate scheduling algorithms, as demonstrated in our implementation of the SIMGRID simulation framework.

This paper deals with the resolution of the Quadratic 3-dimensional Assignment Problem hereafter referred to as Q3AP. Q3AP is an extension of the well-known Quadratic Assignment Problem (QAP) and of the Axial 3-Assignment Problem (A3AP). It finds its application amongst others in Hybrid Automatic Repeat reQuest (HARQ) error-control mechanism used in wireless communication systems. This problem is computationally NP-hard. As far as we know, the largest Q3AP instance size solved to optimality is 13 whereas practical Q3AP instance size can be of 8, 16, 32 or 64. Sequential exact methods such branch-and-bound or sequential metaheuristics are therefore not suited to solve large size instances for the excessive needed computation time. In this paper, we propose parallel hybrid genetic-based metaheuristics for solving the Q3AP. The parallelism in our methods is of two hierarchical levels. The first level is an insular model where a fixed number of genetic algorithms (GA) evolve independently on separate islands and periodically exchange genetic material. The second level is a parallel transformation of individuals in each GA. Implementation has been done using ParadisEO framework, and the experiments have been performed on GRID5000, the French nation-wide computational grid. The experimental results produced by our method were confronted with those reported in the literature. The optimum or the best so far known solutions have been reached in a reasonable computation time.

In the present work, the effects of spatial constraints on the efficiency of task execution in systems underlain by geographical complex networks are investigated, where the probability of connection decreases with the distance between the nodes. The investigation considers several configurations of the parameters defining the network connectivity, and the Barabási–Albert network model is also considered for comparisons. The results show that the effect of connectivity is significant only for shorter tasks, the locality of connections implied by the spatial constraints reduces efficiency, and the addition of edges can improve the efficiency of the execution, although with increasing locality of the connections the improvement is small.

We address the challenging problem of algorithm and program design for the Computational Grid by providing the application user with a set of high-level, parameterised components called skeletons. We descrile a Java-based Grid programming system in which algorithmns are composed of skeletons and the computational resources for executing individual skeletons are chosen using performance prediction. The advantage of our approach is that skeletons are reusable for different applications and that skeletons' implementation can be tuned to particular machines. The focus of this paper is on predicting performance for Grid applications constructed using skeletons.

Two important tools of today's science and engineering are computational grids and visualization. While grid infrastructures offer a means to process large amounts of data across different, possibly distant resources, visualization aids in understanding the meaning of data. The Grid Visualization Kernel (GVK) addresses the connection of grid applications and visualization clients on the grid. The visualization capabilities of GVK are provided as flexible grid services via dedicated interfaces and protocols, while GVK itself relies on Globus services to implement the functionality of the visualization pipeline. This paper describes the concept of GVK and its core functionality for grid visualization services, and discusses how to use visualization in the grid environment.

In this paper we describe a services oriented software system to provide basic database support for efficient execution of applications that make use of scientific datasets in the Grid. This system supports two core operations: efficient selection of the data of interest from distributed databases and efficient transfer of data from storage nodes to compute nodes for processing. We present its overall architecture and main components and describe preliminary experimental results.

We describe an initial implementation of a platform for the analysis of gene promoter architecture for sets of genes from human and other higher organisms, using NorduGrid as the Grid Virtual Organization. The procedure leading from a set of co-regulated genes to a set of inferred common regulatory elements involves a number of computationally intensive, but well scalable steps. We show it is feasible to implement a high performance genomic regulatory sequence analysis pipeline on the Grid with minimal modification to the existing computational biology software components. We applied a job binning step to dramatically reduce the overhead for submitting a set of many small jobs to the Grid. Even with simple jobs and a relatively small size of the Grid, we observed up to 25-fold performance improvement over a comparable or more powerful single or dual-CPU platform. Our implementation of biological sequence alignment and transcription factor binding site algorithms on the Grid proves that even simple applications can take advantage of computational resources that adopted this computational paradigm.

This article describes a potential application of grid computing in structural biology. Three-dimensional electron microscopy allows the investigation of biological structures over a wide range of sizes, from cells to single macromolecules. Knowledge of the structure is critical to understanding the function of biological specimens. However, high resolution structure determination is computationally intensive. This contribution analyzes the potential benefits of grid computing in this field, and draws the conclusion that there are excellent opportunities to take advantage of computational grids.

Over recent years, non-rigid registration has become a major issue in medical imaging. It consists in recovering a dense point-to-point correspondence field between two images, and usually takes a long time. This is in contrast to the needs of a clinical environment, where usability and speed are major constraints, leading to the necessity of reducing the computation time from slightly less than an hour to just a few minutes. As financial pressure makes it hard for healthcare organizations to invest in expensive high-performance computing (HPC) solutions, cluster computing proves to be a convenient solution to our computation needs, offering a large processing power at a low cost. Among the fast and efficient non-rigid registration methods, we chose the demons algorithm for its simplicity and good performances. The parallel implementation decomposes the correspondence field into spatial blocks, each block being assigned to a node of the cluster. We obtained an acceleration of 11 by using 15 2GHz PC's connected through a 1GB/s Ethernet network and reduced the computation time from 40min to 3min30. In order to further optimize the costs and the maintenance load, we investigate in the second part the transparent use of shared computing resources, either through a graphic client or a Web one.

A computational and data grid was developed at the Center for Computational Research in Buffalo, New York, in order to provide a platform to support scientific and engineering applications across a variety of computer and storage systems. This proof-of-concept grid has been deployed using a critical scientific application in the field of structural biology. The design and functionality of the prototype grid is described, along with plans for a production level grid system based on Globus.

Several aspects of today's Grids are based on centralized or hierarchical services. However, as Grids increase their size from tens to thousands of hosts, functionalities should be decentralized to avoid bottlenecks and guarantee scalability. A way to ensure Grid scalability is to adopt Peer-to-Peer (P2P) models and techniques to implement non-hierarchical decentralized Grid services and systems. Pure decentralized P2P protocols based on a pervasive exchange of messages, such as Gnutella, appear to be inadequate for OGSA Grids, where peers communicate among them through Grid Services mechanisms. On the other hand, this class of protocols offers useful properties in dealing with Grid resources heterogeneity and dynamicity. This paper proposes a modified Gnutella discovery protocol, named Gridnut, which makes it suitable for OGSA Grids. In particular, Gridnut uses appropriate message buffering and merging techniques to make Grid Services effective as a way to exchange messages in a P2P fashion. We present the design of Gridnut and compare Gnutella and Gridnut performances under different network and load conditions.

The splitting of Quasi-Monte Carlo (QMC) point sequences into interleaved substreams has been suggested to raise the speed of distributed numerical integration and to lower the traffic on the network. The usefulness of this approach in GRID environments is discussed. After specifying requirements for using QMC techniques in GRID environments in general we review and evaluate the proposals made in literature so far. In numerical integration experiments we investigate the quality of single leaped QMC point sequence substreams, comparing the respective properties of Sobol', Halton, Faure, Niederreiter-Xing, and Zinterhof sequences in detail. Numerical integration results obtained on a distributed system show that leaping sensitivity varies tremendously among the different sequences and we provide examples of deteriorated results caused by leaping effects, especially in heterogeneous settings which would be expected in GRID environments.

Grid computing integrates heterogeneous, geographically distributed, Internet-ready resources that are administered under multiple domains. A key challenge in grid computing is to provide a high quality of service to users in a transparent fashion, hiding issues that include ownership, administration, and geographic location of a wide variety of resources that provide compute cycles, data storage, rendering cycles, imaging devices, and sensors, to name a few. Ensuring the functionality of a wide variety of resources under multiple administrative policies requires tools for discovering, repairing, and publishing information on the services offered by individual sites within a given grid. In this paper, we present the ACDC Operations Dashboard, an interactive, collaborative environment for collecting, addressing, and publishing operational service information for resources across a computational grid.

In this paper we address the problem of accurately estimating the runtime and communication time of a client request in a Network Enabled Server (NES) middleware such as GridSolve. We use a template based model for the runtime estimation and a client-server communication test for the transfer time estimation. We implement these two mechanisms in GridSolve and test them on a real testbed. Experiments show that they allow for significant improvement in terms of client execution time on various scenarios.

One motivation of Grid computing is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To achieve this goal, efficient task scheduling algorithms are essential. However, scheduling algorithms in the Grid present high diversities that need to be classified. In this paper, with the help of an abstract scheduling architecture, some key features of the task scheduling problem in the Grid are discussed, followed by a taxonomy of the scheduling algorithms. Some typical examples are given in each category to present a picture of the current research and help to find new research problems.

This paper presents a new approach to resource management and scheduling in computational grids, in order to simplify the vision users have from grid resources and their management. Scheduling decisions are moved to the site where resources are hosted, allowing quick response to changes in load and resource availability. Users do not need to be aware of the resources they use and are instead supplied with "virtual resources" representing the amount of computational power available to them in the site. This approach results in new challenges, like the management of two-level scheduling schema and the need to define a site capacity measure, but simplifies and optimizes scheduling in grids. In this paper we present details of this approach – called Site Resource Scheduler (SRS) – as well as some issues regarding its simulated performance and its deployment in a site. We show that the main advantage of this approach is an overall reduction in the execution time of tasks in most scenarios.

The emerging cloud computing model has recently gained a lot of interest both from commercial companies and from the research community. XtreemOS is a distributed operating system for large-scale wide-area dynamic infrastructures spanning multiple administrative domains. XtreemOS, which is based on the Linux operating system, has been designed as a Grid operating system providing native support for virtual organizations. In this paper, we discuss the positioning of XtreemOS technologies with regard to cloud computing. More specifically, we investigate a scenario where XtreemOS could help users take full advantage of clouds in a global environment including their own resources and cloud resources. We also discuss how the XtreemOS system could be used by cloud service providers to manage their underlying infrastructure. This study shows that the XtreemOS distributed operating system is a highly relevant technology in the new era of cloud computing where future clouds seamlessly span multiple bare hardware providers and where customers extend their IT infrastructure by provisioning resources from different cloud service providers.

This paper presents a parallel system capable of accelerating biological sequence alignment on the graphics processing unit (GPU) grid. The GPU grid in this paper is a desktop grid system that utilizes idle GPUs and CPUs in the office and home. Our parallel implementation employs a master-worker paradigm to accelerate an OpenGL-based algorithm that runs on a single GPU. We integrate this implementation into a screensaver-based grid system that detects idle resources on which the alignment code can run. We also show some experimental results comparing our implementation with three different implementations running on a single GPU, a single CPU, or multiple CPUs. As a result, we find that a single non-dedicated GPU can provide us almost the same throughput as two dedicated CPUs in our laboratory environment, where GPU-equipped machines are ordinarily used to develop GPU applications. In a dedicated environment, the GPU-accelerated code achieves five times higher throughput than the CPU-based code. Furthermore, a linear speedup of 30.7X is observed on a 32-node cluster of dedicated GPUs. We also implement a compute unified device architecture (CUDA) based algorithm to demonstrate further acceleration.

Several factors still hinder the deployment of computational grids over large scale platforms. Among them, the resource discovery is one crucial issue. New approaches, based on peer-to-peer technologies, tackle this issue. Because they efficiently allow range queries, Tries (a.k.a., Prefix Trees) appear to be among promising ways in the design of distributed data structures indexing resources. Despite their lack of robustness in dynamic settings, trie-structured approaches outperform other peer-to-peer fashioned technologies by efficiently supporting range queries. Within recent trie-based approaches, the fault-tolerance is handled by preventive mechanisms, intensively using replication. However, replication can be very costly in terms of computing and storage resources and does not ensure the recovery of the system after arbitrary failures.

Self-stabilization is an efficient approach in the design of reliable solutions for dynamic systems. It ensures a system to converge to its intended behavior, regardless of its initial state, in a finite time. A snap-stabilizing algorithm guarantees that it always behaves according to its specification, once the protocol is launched. In this paper, we provide the first snap-stabilizing protocol for trie construction. We design particular tries called Proper Greatest Common Prefix (PGCP) Tree. The proposed algorithm arranges the n label values stored in the tree, in average, in O(h + h′) rounds, where h and h′ are the initial and final heights of the tree, respectively. In the worst case, the algorithm requires an O(n) extra space on each node, O(n) rounds and O(n²) actions. However, simulations allow to state that this worst case is far from being reached and to confirm the average complexities, showing the practical efficiency of this protocol.

In this paper, we focus on the problem of scheduling a collection of similar task graphs on a heterogeneous platform, when the task graph is an intree. We rely on steady-state scheduling techniques, and aim at optimizing the throughput of the system. Contrarily to previous studies, we concentrate on practical aspects of steady-state scheduling, when dealing with a collection (or batch) of limited size. We focus here on two optimizations. The first one consists in reducing the processing time of each task graph, thus making steady-state scheduling applicable to smaller batches. The second one consists in degrading a little the optimal-throughput solution to get a simpler solution, more efficient on small batches. We present our optimizations in details, and show that they both help to overcome the limitation of steady-state scheduling: our simulations show that we are able to reach a better efficiency on small batches, to reduce the size of the buffers, and to significantly decrease the processing time of a single task graph (latency).