Ebook: Parallel Programming, Models and Applications in Grid and P2P Systems

Grids and P2P systems have emerged as distributed computing paradigms for the development of large-scale distributed applications. With the fast developments in Internet technologies and the continuous improvements in the connected computational resources, Grid and P2P appeared as the disruptive technologies that can greatly impact not only on scientific and academic activities but also in business and enterprise productivity.

Computational grids were motivated by the need to develop computational frameworks to support large-scale applications that benefit from the large computing potential offered by such distributed infrastructures. As a matter of fact, the first successful stories of Grid-enabled applications are found from scientific computing domain. On the other hand, P2P systems appeared as the new paradigm after client-server and web-based computing. Differently from centralized or hierarchical models of Grid systems, P2P systems distinguish for their very large scale, decentralized and self-organizing nature. Although P2P systems have become popular for file sharing, these systems are very rapidly evolving to an important distributed computing paradigm.

During the past years considerable research efforts and, as a consequence, important advances are reported for programming models, middleware and communication libraries for Grid and P2P systems. However, Grid and P2P applications still remain difficult to develop in practice for many users, mainly, because Grid/P2P middleware provide fundamental services but they are often “low level”. Moreover, such middle-ware are neither standard nor complete as regarding the needs of different domain applications, requiring thus some ad hoc development. Researchers and developers of the Grid and P2P systems are addressing issues that concern both systems, which are yielding to new insights on large-scale distributed application development in such systems.

The chapters of this volume bring recent advances in Grid and P2P programming models, middleware, communication libraries as well as their application to the resolution of real life problems. The book consists of an introductory chapter and eleven chapters selected out of nineteen chapter proposals. Chapters were carefully reviewed by the editor and blind reviewers; each chapter received at least two review reports. The chapters of the volume are organized as follows.

Chapter 1 introduces the Grid and P2P paradigms, in view of their common and different features. Most commonly used programming models, middleware and communication libraries are surveyed by emphasizing their advantages and drawbacks. Also, some applications from massive processing of regularly sequenced data using Grid and P2P approaches are given.

Chapter 2 by Cong-Vinh addresses the use of categorical structures to establish a formal basis for specifying tasks parallel, data parallel, peer-to-peer structures and self-organization in Large Scale Distributed Networks (LSDNs). The aim of the chapter is to formalize parallel programming in LSDNs, including parallel composition of tasks in LSDNs, category in categories and categorical aspects of self-configuration in P2P networks.

In chapter 3, Pllana et al. study the use of hybrid models for performance modelling and prediction of large scale parallel systems. This approach combines mathematical modelling with discrete event. A high-level performance model is thus obtained, which combines the evaluation speed of mathematical models with the structure awareness and fidelity of the simulation model.

Chapter 4 by Pujol Ahulló and García López performs a comparison of the recent works on the family of similarity queries including range queries, k-nearest neighbour queries and spatial queries as richer queries for distributed systems based on peer-to-peer networks. The authors have identified a set of evaluation parameters and have used them for the comparison analysis of different systems.

Genaud and Rattanapoka, in the fifth chapter, present P2P-MPI, a peer-to-peer framework for message passing parallel programs in large scale distributed systems. It uses MPJ (Message Passing for Java) communication library. P2P-MPI is intended as a light-weight, self-contained software package that facilitates the development and maintenance of parallel programs with minimum efforts to users. Experimental results are presented for allocation and performance, fault-tolerance and replicas using the grid testbed Grid5000.

In the sixth chapter, Quan and Tang report parallel implementations for mapping Service Level Agreement (SLA)-based workflows onto Grid resources. The proposed approach aims at overcoming the limitations of the mapping module, which could be the bottleneck of the systems when many requests are to be during a short period of time. Parallelized mapping algorithms to increase the capability of the SLA workflow broker are presented and performance measurements are experimentally evaluated.

Seventh chapter by Gounaris et al. considers the parallel query processing on the Grid, research issues and challenges in a Grid setting. The authors analyze the Grid-oriented and/or service-based query processors and how they differ from traditional ones. The chapter focuses on scheduling parallel database queries over non-dedicated, distributed resources, alleviating the impact of increased data transfer cost and load balancing in the Grid setting.

In the eighth chapter Hellinckx et al. deal with runtime prediction in desktop Grids and its application in the prediction-aware mapping of jobs onto available resources aiming at reducing the number of jobs prematurely interrupted due to insufficient resource availability. A framework for efficiently executing parameter sweep applications based on both runtime prediction modelling techniques and resource availability is introduced. The prediction based scheduling is experimentally evaluated by simulation and real time scheduling and results are compared.

The ninth chapter by Mateos et al. presents an approach to just-in-time gridification of conventional Java applications. Gridification methods aim to facilitate running Grid applications by semi-automatically deriving the Grid-enabled version of an user application from its binary code. The authors propose BYG a gridification method for binary Java applications. The feasibility of the approach is experimentally shown.

Choy et al. in the tenth chapter exploit large scale distributing computing for solving linear algebra problems such as large size eigenvalue problem and bring interesting real life experiences for the resolution of such problems. Several linear algebra methods have been considered and parallelisation paradigms such as parametric parallelism are considered for their efficient resolution. Real size problem instances are solved using the prposed approach in a world-wide platform using XtremeWeb P2P middleware and OmniRPC Grid middleware.

Chapter eleven by Muñoz-Marí presents parallel implementations of Support Vector Machines (SVM) for earth observation problems (hyper spectral remote sensing). SVM have shown their efficiency for hyper spectral image classification but suffer from high computational cost. The authors present two parallel versions of SVMs for remote sensing image classification and experimental results are presented for the parallel implementation of SVM via Cholesky factorization in a complex multispectral image classification.

In the last chapter, Tantar et al. propose the use of landscape analysis in Grid-enabled meta-heuristics (hierarchical and multistage distributed evolutionary algorithms). Local search algorithms and parallel versions developed in ParadisEO framework are considered and analyzed. The parallelization model is based on a synchronous multi-start approach. The Protein Structure Prediction conformational sampling problem, which is known for its high computational cost, is considered as a case study. More than 500MB of raw data has been processed for the local search algorithms analysis.

By approaching Grid and P2P paradigms in an integrated and comprehensive way, we believe that this book will serve as a reference for the researchers and developers of the Grid and P2P computing community.

I would like to thank the authors of this volume for their contributions and the reviewers for their careful reviewing and interesting feedback to authors of the chapters. I am very grateful to Prof. Dr. Gerhard Joubert, Series Editor of “Advances in Parallel Computing” of IOS Press for his continuous and timely support to this book project and to Ms. Anne Marie de Rover (Head of Book Department, IOS Press) for the editorial assistance.

Fatos Xhafa

Department of Languages and Informatic Systems

Technical University of Catalonia, Spain

March 2009, Barcelona, Spain

Grid computing originated as paradigm for high performance computing and massive parallel processing. Currently, Grid systems have become an important paradigm for efficiently solving large scale complex problems from many fields. On the other hand, P2P paradigm originated from file sharing but each time more is being used for the development of large scale distributed platforms. Grid and P2P systems have thus followed different trajectories pushed by different motivations, needs and research communities. Yet, both paradigms are evolving in a way that each time more they are sharing common characteristics and are mutually benefiting from their best features. Among these characteristics, we could distinguish the cooperative model for solving complex problems by exploiting the large computing capacity offered by the nodes of the system altogether. As such, Grid and P2P systems have achieved notable success, in particular, for e-Science applications, a family of complex applications arising in science and engineering that need considerable computation power.

Despite of important advances in the design and use of Grid and P2P systems, they remain still difficult to implement and apply to real life problems. The main difficulties reside in the lack of easy-to-use middleware for Grid and P2P, in the complexities of setting up and in the tedious task of deploying real world Grid/P2P platforms as well as in experimental studies which are often complex and not easy to repeat. In this chapter we survey and analyze the advances in communication libraries and middleware for both Grid and P2P systems as well as their limitations when used in real Grid and P2P infrastructures. We also bring examples of real life applications based on regularly sequenced data that can be efficiently handled through Grid and P2P approaches.

A computing paradigm is currently at crucial point in its evolution: distributed computing (DC), marked by the increasing developments of large scale distributed networks (LSDNs). In DC, every application or service is split up into tasks that run simultaneously on multiple computers communicating over an LSDN. Hence, DC is a form of parallel computing in heterogeneity, decentralization, nondeterminism and dynamicity of the network. The overarching goal of DC is to support such LSDNs capable of management and high performance. Meeting this grand challenge of DC requires a fundamental approach to the aspects of tasks and data parallel not tackled before. To this end, taking advantage of the categorical structures we establish, in this chapter, a firm formal basis for specifying tasks parallel, data parallel, peer-to-peer structures and self-organization in LSDNs. All of these are to formalize parallel programming in LSDNs.

Performance is a key feature of parallel computing systems. However, the achieved performance when a certain parallel program is executed is significantly lower than the maximal theoretical performance of the parallel computing system. The model-based performance evaluation may be used to support the performance-oriented program development for parallel computing systems. In this book chapter we present a hybrid approach for performance modeling and prediction of parallel computing systems, which combines mathematical modeling and discrete-event simulation. We use mathematical modeling to develop parameterized performance models for components of the system. Thereafter, we use discrete-event simulation to describe the structure of system and the interaction among its components. As a result, we obtain a high-level performance model, which combines the evaluation speed of mathematical models with the structure awareness and fidelity of the simulation model. We evaluate empirically our approach with a real-world material science program that comprises more than 15,000 lines of code.

Structured peer-to-peer systems are a class of distributed data structures that provided initially only exact-match queries in a scalable way. Exact-match queries consist of retrieving single values from the network (i.e., put(key,value)/value←get(key)), in such a way that if the data exists, it is returned. Unfortunately, this service is not enough for modern distributed and parallel applications. Thereafter richer queries have been the focus on the field of distributed systems based on peer-to-peer networks. Range queries, k-nearest neighbour queries and spatial queries belong to the family of similarity queries. This sort of queries are used by a wide range of applications. This chapter performs a comparison of the last and most remarkable works in this field. To do so, a set of evaluation parameters are defined with which all systems are compared to. Examples of the analysed parameters are: overlay network topology, application domain, query correctness, completeness, storage and time efficiency and load balancing, to say the least. The goal, thus, is to provide an insight on peer-to-peer-enabled distributed and parallel algorithms that support similarity queries in the large scale.

This chapter describes the P2P-MPI project, a software framework aimed at the development of message-passing programs in large scale distributed networks of computers. Our goal is to provide a light-weight, self-contained software package that requires minimum effort to use and maintain. P2P-MPI relies on three features to reach this goal: i) its installation and use does not require administrator privileges, ii) available resources are discovered and selected for a computation without intervention from the user, iii) program executions can be fault-tolerant on user demand, in a completely transparent fashion (no checkpoint server to configure). P2P-MPI is typically suited for organizations having spare individual computers linked by a high speed network, possibly running heterogeneous operating systems, and having Java applications. From a technical point of view, the framework has three layers: an infrastructure management layer at the bottom, a middleware layer containing the services, and the communication layer implementing an MPJ (Message Passing for Java) communication library at the top. We explain the design and the implementation of these layers, and we discuss the allocation strategy based on network locality to the submitter. Allocation experiments of more than five hundreds peers are presented to validate the implementation. We also present how fault-management issues have been tackled. First, the monitoring of the infrastructure itself is implemented through the use of failure detectors. We theoretically evaluate several candidate protocols for these detectors to motivate our choice for the gossiping protocol called binary round robin. A variant of this protocol is also proposed for a greater reliability. Finally, the system scalability and the theoretical findings are validated through experiments. The second aspect of fault management concerns program executions. Fault-tolerance is provided by the communication library through replication of processes. We describe the underlying protocol and the properties that need to be met in order to insure the correctness of execution. We then discuss how to choose the number of replicas by quantifying how much more robust is an application using replication, depending on the failure model parameters.

Service Level Agreements (SLAs) are currently one of the major research topics in Grid Computing. Among many system components for supporting of SLA-aware Grid jobs, the SLA mapping module holds an important position and the capability of the mapping module depends on the runtime of the mapping algorithm. With the previously proposed mapping algorithms, the mapping module may develop into the bottleneck of the system if many requests come in during a short period of time. Besides that, the mapping module may also miss some high quality mapping solutions. This Chapter presents parallel mapping algorithms, which can either reduce the runtime of the mapping algorithms without reducing the quality of the mapping solutions or increase the quality of the mapping solutions without increasing the runtime of the mapping algorithms. Performance measurements thereby deliver evaluation results showing the quality of the method. The speedup of the algorithms and the quality of the solutions are significantly improved when using 8 CPUs comparing to using 1 CPU.

Database queries offer an easy-to-use declarative manner for describing complex data management tasks. Query processing technologies have been evolving for decades; however the emergence of the Grid creates a new setting in which novel research issues and challenges have arisen. This chapter discusses how Grid-oriented and/or service-based query processors differ from traditional ones, and focuses on three complementary research issues, namely, how to schedule parallel database queries over non-dedicated, distributed resources; how to mitigate the impact of increased data transfer cost; and how to perform load balancing in this new setting. In addition, we discuss how parallel spatio-temporal query processing techniques can be applied to a Grid environment. The discussion revolves around the development of the OGSA-DQP system, which is a pioneer open-source service-based query processing system that enables parallel query execution over Grid resources, and the way some of the most prominent issues about its performance were addressed. The unique characteristics of the scheduling problem of arbitrarily parallel queries over heterogeneous resources have motivated the development of a new hill-climbing algorithm. For the problems of increased data transmission cost and load balancing, due to the highly volatile conditions, techniques founded on control theory are examined. The emphasis of this chapter is on both the description of a real Grid-enabled parallel query processor and the presentation of the different approaches to tackling each of the afore-mentioned problems including the limitations of the current state-of-the-art solutions.

The efficient allocation of tasks to available resources is a key feature of resource management and scheduling systems. This is particularly true in large scale, distributed infrastructures spanning many administrative domains such as grids or peer-to-peer networks. The mapping of applications or tasks to the physical system is subject to many constraints, requirements and objectives. Some of these derive from the application that may e.g. have a complex work flow or a hard deadline. Others arise from the nature of the resources such as computational or network capacity. If the infrastructure has a dynamic configuration, such as a desktop grid, resource uptime and application runtime become critical factors in the scheduling algorithms.

The scheduling mechanism used in this chapter maps job runtimes onto resource uptimes. The main focus lies on runtime prediction and its application in the prediction-aware mapping of jobs onto available resources. The ultimate objective is a reduction in the number of jobs prematurely interrupted due to insufficient resource availability. We introduce a comprehensive framework for efficiently executing parameter sweep applications based on both runtime prediction modeling techniques and resource availability. The framework is built on top of the CoBRA research grid and is designed to be highly configurable. It allows for prediction models and scheduling paradigms to be easily added and compared. The main goal is to offer an environment in which prediction techniques can be tested and plugged into a real life scheduler.

This goal is archived by introducing the pluggable GIPSy (Grid Information Prediction System) framework into the Prediction based Grid Scheduler (PGS). For each of the GIPSy prediction components we propose different implementations. The different techniques are compared using two testing schemes. The first scheme is based on simulations within the GIPSy framework. The second compares round-trip times using the PGS scheduler. Each of the tests is based on a number of different applications with varying runtime behavior. A comparison to alternative scheduling approaches is also made and discussed.

Grid technologies allow developers to run applications with enormous demands for resources such as processing power, data and network bandwidth. However, exploiting Grid resources demands developers to alter their applications to explicitly access the services of specific Grid middlewares. This involves more development effort and requires expertise on Grid programming. A number of recent research efforts among the so-called gridification methods aim to avoid these problems by semi-automatically deriving the Grid-enabled version of an application from its binary code. However, most of these approaches produce coarse-grained Grid applications that prevent programmers from employing tuning mechanisms such as parallelism and distribution, and are rather inflexible, since they were not designed to reuse existing Grid middleware services. To solve these issues, we propose BYG (BYtecode Gridifier), a new gridification method to easily gridify binary Java applications. The chapter describes the prototype implementation of BYG and some experiments showing the feasibility of the approach. Results show that BYG can be used to conveniently gridify and efficiently execute a broad range of computing intensive applications.

Parallel and distributed programming for large scale computing platforms is a topical and challenging issue. Through our experience on the distribution and parallelization of linear algebra problems, especially the real symmetric eigenproblem, we present in this Chapter our approach to tackle this issue. It starts from very early choices related to numerical algorithms in order to determine an optimal communication paradigm. As an example, by choosing the Bisection algorithm, we underline how far is interesting the parametric-parallelism paradigm in the context of world-wide computing. We also emphasize the importance of data distribution on communication and we propose useful techniques to deploy an application on a web-based heterogeneous environment. In particular, out-of-core programming and data persistence are relevant in this context. We evaluate our case study application on nation and world-wide platforms by using the XtremWeb peer-to-peer middleware and the OmniRPC grid computing middleware. In addition, we perform evaluations on large size instances of the eigenproblem. Therefore, we show the feasibility of the global computing model for linear algebra problems.

Imaging spectroscopy, also known as hyperspectral remote sensing, is concerned with the measurement, analysis, and interpretation of spectra acquired from a given scene (or specific object) at a short, medium or long distance by an airborne or satellite sensor. Analysis in a timely manner of the acquired multi-dimensional images allows to develop applications with high social impact, such as urban growing monitoring, crop fields identification, target detection for military and defense/security deployment, wildland fire detection and monitoring, biological threat detection, biophysical parameter estimation, or monitoring of oil spills and other types of chemical contamination.

In this context, support vector machines (SVM) [1, 2, 3] have become one of the state-of-the-art machine learning tools for hyperspectral image classification. However, its high computational cost for large scale applications makes the use of SVM limited to off-line processing scenarios. Certainly, with the recent explosion in the amount and complexity of hyperspectral data, parallel processing has soon become a requirement in many remote sensing missions, especially with the advent of low-cost systems such as commodity clusters and distributed networks of computers In order to address this relevant issue, this chapter explores the development of two parallel versions of SVMs for remote sensing image classification.

Sequential minimal optimization is a very popular algorithm for training SVMs, but it still requires a large amount of computation time for solving large size problems. In this work, we evaluate the performance of a parallel implementation of the SVM based on the parallelization of the incomplete Cholesky factorization and present novel parallel implementations that balance the load across the available processors through standard Master-Worker decompositions. Both methodologies are theoretically analyzed in terms of scalability, computational efficiency and time response. The impact of the multi-class scheme is also analyzed. Results on real multispectral and hyperspectral datasets illustrate the performance of the methods. We finally discuss the possibility of obtaining processing results quickly enough for practical use via the Marenostrum supercomputer available at the Barcelona Supercomputing Center in Spain, and other massively parallel facilities at NASA's Goddard Space Flight Center in Maryland.

An ensemble of local search algorithms are discussed and analyzed, having different initial landscape perspectives as starting point - the conformational sampling problem is considered as a case study. Grid enabled hierarchical and multistage distributed evolutionary algorithms have been addressed in previous studies, combining complementary techniques and relying on different coordination models. For algorithmic constructions following the aforementioned outlines, the per se exploration results in an emergent behavior of the system. Nevertheless, in order to encompass a large spectrum of exploration characteristics and to harness the complete power of the combined techniques, landscape analysis has to be employed for guiding the exploration process. Due to the high complexity of real-life applications, landscape analysis represents a foreword measure in this direction, providing the means for adapting the exploration process as determined by the search landscape structure.