ALGORITHMIC SKELETONS FOR BRANCH & BOUND

Michael Poldner and Herbert Kuchen

Algorithmic skeletons are predefined components for parallel programming. We will present a skeleton for branch & bound problems for MIMD machines with distributed memory. This skeleton is based on a distributed work pool. We discuss two variants, one with supply-driven work distribution and one with demand-driven work distribution. This approach is compared to a simple branch & bound skeleton with a centralized work pool, which has been used in a previous version of the skeleton library Muesli. Based on experimental results for two example applications, namely the $n$-puzzle and the traveling salesman problem, we show that the distributed work pool is clearly better and enables good runtimes and in particular scalability. Moreover, we discuss some implementation aspects such as termination detection as well as overlapping computation and communication.

IMPACT OF WRAPPED SYSTEM CALL MECHANISM ON COMMODITY PROCESSORS

Satoshi Yamada, Shigeru Kusakabe and Hideo Taniguchi

Split-phase style transactions separate issuing a request and receiving the result of an operation in different threads, and are useful in hiding latencies of unpredictably long operations. We apply this style to system calls in order to reduce overhead caused by system call mechanism on commodity processors. This style is also useful in enhancing locality of reference when executing the same system calls in multiple threads. In this paper, we evaluate the effectiveness of split-phase system call on commodity processors, and we call this mechanism as Wrapped System Call (WSC) mechanism. WSC mechanism can be effective even on commodity platforms which do not have explicit fine-grain multithread support. We evaluate WSC mechanism based on a performance evaluation model by using a simplified benchmark. We also apply WSC mechanism to variants of cp program to observe the effect on the enhancement of locality of reference. When we apply WSC mechanism to cp program, the combination of our split-phase style system calls and our scheduling mechanism is effective in improving throughput by reducing mode changes and exploiting locality of reference.

A HYBRID TOPOLOGY ARCHITECTURE FOR P2P FILE SHARING SYSTEMS

Juan Pedro Muñoz-Gea, Josemaría Malgosa-Sanahuja, Pilar Manzanares-Lopez, Juan Carlos Sanchez-Aarnoutse and Antonio M. Guirado-Puerta

Over the Internet today, there has been much interest in emerging Peer-to-Peer (P2P) networks because they provide a good substrate for creating data sharing, content distribution, and application layer multicast applications. There are two classes of P2P overlay networks: structured and unstructured. Structured P2P networks can efficiently locate items, but the searching process is not user friendly. Conversely, unstructured P2P networks have an easy mechanism to search a content, but the lookup process is inefficient. In this paper, we propose a hybrid structured and unstructured topology in order to take advantages of both kind of networks. In addition, our proposal guarantees that if a content is at any place in the network, it will be reachable with probability one. Simulation results show that the behaviour of the network is stable and that the network distributes the contents efficiently to avoid network congestion.

A METHODOLOGY FOR ADAPTIVE RESOLUTION OF NUMERICAL PROBLEMS ON HETEROGENEOUS HIERARCHICAL CLUSTERS

Wahid Nasri, Sonia Mahjoub and Slim Bouguerra

Solving a target problem by using a single algorithm or writing portable programs that perform well is not always efficient on any parallel environment due to the increasing diversity of existing computational supports where new characteristics are influencing the execution of parallel applications. The inherent heterogeneity and the diversity of networks of such environments represent a great challenge to efficiently implement parallel applications for high performance computing. Our objective within this work is to propose a generic framework based on adaptive techniques for solving a class of numerical problems on cluster-based heterogeneous hierarchical platforms. Toward this goal, we refer to adaptive approaches to better adapt a given application to a target parallel system. We apply this methodology on a basic numerical problem, namely solving the matrix multiplication problem, while determining an adaptive execution scheme minimizing the overall execution time depending on the problem and architecture parameters.

TOWARDS A QUALITY MODEL FOR GRID PORTALS

Mª Ángeles Moraga, Coral Calero, Mario Piattini and David Walker

Researchers require multiple computing resources when conducting their computational research; this makes necessary the use of distributed resources. In response to the need for dependable, consistent and pervasive access to distributed resources, the Grid came into existence. Grid portals subsequently appeared with the aim of facilitating the use and management of distributed resources. Nowadays, many Grid portals can be found. In addition, users can change from one Grid portal to another with only a click of a mouse. So, it is very important that users regularly return to the same Grid portal, since otherwise the Grid portal might disappear. However, the only mechanism that makes users return is high quality. Therefore, in this paper and with all the above considerations in mind, we have developed a Grid portal quality model from an existing portal quality model, namely, PQM. In addition, the model produced has been applied to two specific Grid portals.

LANGUAGE-BASED SUPPORT FOR SERVICE ORIENTED ARCHITECTURES: FUTURE DIRECTIONS

Pablo Giambiagi, Olaf Owe, Gerardo Schneider and Anders P. Ravn

The fast evolution of the Internet has popularized service-oriented architectures (SOA) with their promise of dynamic IT-supported inter-business collaborations. Yet this popularity does not reflect on the number of actual applications using the architecture. Programming models in use today make a poor match for the distributed, loosely-coupled, document-based nature of SOA. The gap is actually increasing. For example, interoperability between different organizations, requires contracts to reduce risks. Thus, high-level models of contracts are making their way into service-oriented architectures, but application developers are still left to their own devices when it comes to writing code that will comply with a contract. This paper surveys existing and future directions regarding language-based solutions to the above problem.

AN APPROACH TO MULTI AGENT COOPERATIVE SCHEDULING IN THE SUPPLY CHAIN, WITH EXAMPLES

Joaquim Reis

We present an approach to multi-agent cooperative supply-chain production distribution scheduling, together with some results of its application based on simulations. The approach emphasises a scheduling temporal perspective, it is based on a set of three steps each agent must perform, in which the agents communicate through an interaction protocol, and presupposes the sharing of some specific temporal information (among other) about the scheduling problem, for coordination. It allows the set of agents involved to conclude if a given scheduling problem has, or has not, any feasible solutions. In the first case, agent actions are prescribed to repair a first solution, if it contains constraint violations. The resulting overall agent scheduling behaviour is cooperative.

DEVELOPING A FAULT ONTOLOGY ENGINE FOR EVALUATION OF SERVICE-ORIENTED ARCHITECTURE USING A CASE STUDY SYSTEM

Binka Gwynne and Jie Xu

This paper reports on the current progress of research into the development and implementation of a Fault Ontology Engine. It was devised to facilitate the testing and evaluation of Service-Oriented Architecture, using ontologically supported software fault injection testing mechanisms. The aims of this research stem from the importance of SOA evaluation and the notion that testing and evaluation methods could be supported by autonomous software machines, due to the potential dynamics, size, and complexity of SOA, and the variety of resources offered as services. This paper contains descriptions of experimental work carried out in order to generate information for modelling the fault and failure domains of a real-world case study system. It is planned that analysis of the information from this case study system will be used in the Ontology Engine and adapted to support testing and evaluation mechanisms for SOA systems.

A PEER-TO-PEER SEARCH IN DATA GRIDS BASED ON ANT COLONY OPTIMIZATION

Uros Jovanovic and Bostjan Slivnik

A method for (1) an efficient discovery of data in large distributed raw datasets and (2) collection of thus procured data is considered. It is a pure peer-to-peer method without any centralized control and is therefore primarily intended for a large-scale, dynamic (data)grid environments. It provides a simple but highly efficient mechanism for keeping the load it causes under control and proves especially usefull if data discovery and collection is to be performed simultaneoulsy with dataset generation. The method supports a user-specified extraction of structured metadata from raw datasets, and automatically performs aggregation of extracted metadata. It is based on the principle of ant colony optimization (ACO). The paper is focused on effective data aggregation and includes the detailed description of the modifications of the basic ACO algorithm that are needed for effective aggregation of the extracted data. Using a simulator, the method was vigorously tested on the wide set of different network topologies for different rates of data extraction and aggregation. Results of the most significant tests are included.

AN APPROACH TO MULTI AGENT VISUAL COMPOSITION WITH MIXED STYLES

Joaquim Reis

Applications of computer systems that mix Art, Science and Engineeering have appeared as a result of the evolution of information technologies in the last three decades. Frequently, they involve the use of Artificial Intelligence techniques and they have appeared in the fields of music, literary arts and, more recently, visual arts. This article proposes a computational system based on creative intelligent agents that, by making use of the shape grammar formalism, can support visual composition synthesis activities. In this system, each agent gives its creative contribution through a style of its own. Different modes of agent contribution can be put into perspective like, for instance, cooperative or non cooperative modes, the resulting composition emerging from these contributions.