Search

Presents the special issue in the journal "Parallel Processing Letters," which contains the best papers from the Centre Interantional de Rencontres Mathématiques workshopin October 2001. "Scheduling Issues in Survivality Applications Using Hybrid Fault Models," by A. W. Krings, W. S. Harrison, A. Azadmanesh and M. McQueen"; "Parallel Tabu Search Approaches for Two-Dimensional Cutting," by J. Blazewicz, A. Moret-Salvador and R. Walkowiak"; "Strategies for Workload Balancing in Cluster-Based Image Databases," by F. Drews, K. Ecker, O. Kao and S. Schomann.

The article presents an introductory statement to the special issue of the "Parallel Processing Letters." The most recent important advances in the aspects of hardware⁄software support for high performance computing is featured. The editor believe that all of these papers and topics will not only provide novel ideas, new results, work in progress and state-of-the-art techniques in the area, but also stimulate the future research activities in the area of high performance computing with applications.

In this paper, we explore the problem of mapping linear chain applications onto large-scale heterogeneous platforms. A series of data sets enter the input stage and progress from stage to stage until the final result is computed. An important optimization criterion that should be considered in such a framework is the latency, or makespan, which measures the response time of the system in order to process one single data set entirely. For such applications, which are representative of a broad class of real-life applications, we can consider one-to-one mappings, in which each stage is mapped onto a single processor. However, in order to reduce the communication cost, it seems natural to group stages into intervals. The interval mapping problem can be solved in a straightforward way if the platform has homogeneous communications: the whole chain is grouped into a single interval, which in turn is mapped onto the fastest processor. But the problem becomes harder when considering a fully heterogeneous platform. Indeed, we prove the NP-completeness of this problem. Furthermore, we prove that neither the interval mapping problem nor the similar one-to-one mapping problem can be approximated in polynomial time by any constant factor (unless P=NP). [ABSTRACT FROM AUTHOR]

The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O( m) moves under the unfair distributed daemon. [ABSTRACT FROM AUTHOR]

Federated, secure, standardized, scalable, and transparent mechanism to access and share resources, particularly data resources, across organizational boundaries that does not require application modification and does not disrupt existing data access patterns has been needed for some time in the computational science community. The Global Federated File System (GFFS) addresses this need and is a foundational component of the NSF-funded eXtreme Science and Engineering Discovery Environment (XSEDE) program. The GFFS allows user applications to access (create, read, update, delete) remote resources in a location-transparent fashion. Existing applications, whether they are statically linked binaries, dynamically linked binaries, or scripts (shell, PERL, Python), can access resources anywhere in the GFFS without modification (subject to access control). In this paper we present an overview of the GFFS and its most common use cases: accessing data at an NSF center from a home or campus, accessing data on a campus machine from an NSF center, directly sharing data with a collaborator at another institution, accessing remote computing resources, and interacting with remote running jobs. We present these uses cases and how they are realized using the GFFS. [ABSTRACT FROM AUTHOR]

The increasing complexity of available infrastructures with specific features (caches, hyperthreading, dual core, etc.) or with complex architectures (hierarchical, parallel, distributed, etc.) makes it extremely difficult to build analytical models that allow for a satisfying prediction. Hence, it raises the question on how to validate algorithms if a realistic analytic analysis is not possible any longer. As for some many other sciences, the one answer is experimental validation. Nevertheless, experimentation in Computer Science is a difficult subject that today still opens more questions than it solves: What may an experiment validate? What is a "good experiment"? How to build an experimental environment that allows for "good experiments"? etc. In this paper we will provide some hints on this subject and show how some tools can help in performing "good experiments", mainly in the context of parallel and distributed computing. More precisely we will focus on four main experimental methodologies, namely in-situ (real-scale) experiments (with an emphasis on PlanetLab and Grid'5000), Emulation (with an emphasis on Wrekavoc) benchmarking and simulation (with an emphasis on SimGRID and GridSim). We will provide a comparison of these tools and methodologies from a quantitative but also qualitative point of view. [ABSTRACT FROM AUTHOR]

The emergence of Grid infrastructures like EGEE has enabled the deployment of large-scale computational experiments that address challenging scientific problems in various fields. However, to realize their full potential, Grid infrastructures need to achieve a higher degree of dependability, i.e., they need to improve the ratio of Grid-job requests that complete successfully in the presence of Grid-component failures. To achieve this, however, we need to determine, analyze and classify the causes of job failures on Grids. In this paper we study the reasons behind Grid job failures in the context of EGEE, the largest Grid infrastructure currently in operation. We present points of failure in a Grid that affect the execution of jobs, and describe error types and contributing factors. We discuss various information sources that provide users and administrators with indications about failures, and assess their usefulness based on error information accuracy and completeness. We describe two real-life case studies, describing failures that occurred on a production site of EGEE and the troubleshooting process for each case. Finally, we propose the architecture for a system that could provide failure management support to administrators and end-users of large-scale Grid infrastructures like EGEE. [ABSTRACT FROM AUTHOR]

This paper describes our research on using Genetic Programming to obtain transition rules for Cellular Automata, which are one type of massively parallel computing system. Our purpose is to determine the existence of a limit of chaos for three dimensional Cellular Automata, empirically demonstrated for the two dimensional case. To do so, we must study statistical properties of 3D Cellular Automata over long simulation periods. When dealing with big three dimensional meshes, applying the transition rule to the whole structure can become a extremely slow task. In this work we decompose the Automata into pieces and use OpenMp to parallelize the process. Results show that using a decomposition procedure, and distributing the mesh between a set of processors, 3D Cellular Automata can be studied without having long execution times. [ABSTRACT FROM AUTHOR]

In this paper, we present a new architecture to build grids that can execute parallel programs based on legacy code. This architecture is layer based and software component performances are validated with benchmarks. To illustrate the construction of a grid using the proposed architecture, we develop a case study that consists of a grid oriented to efficient execution of Java bytecode for which we validate and integrate legacy code of parallel linear algebra. [ABSTRACT FROM AUTHOR]

In this paper, we present an program that enables the transformation of a non-terminating alternator into a terminating alternator. Our solution is stabilization preserving and has the potential to preserve maximal concurrency (if available) provided by the non-terminating alternator. It can also be used to transform a program that is stabilizing in interleaving semantics into a program that is stabilizing in powerset semantics. We also discuss how the terminating alternator can be used to enable a process to gain an understanding of system stability. [ABSTRACT FROM AUTHOR]

This paper analyses the micro-threaded model of concurrency making comparisons with both data and instruction-level concurrency. The model is fine grain and provides synchronisation in a distributed register file, making it a promising candidate for scalable chip-multiprocessors. The micro-threaded model was first proposed in 1996 as a means to tolerate high latencies in data-parallel, distributed-memory multi-processors. This paper explores the model's opportunity to provide the simultaneous issue of instructions, required for chip multiprocessors, and discusses the issues of scalability with regard to support structures implementing the model and communication in supporting it. The model supports deterministic distribution of code fragments and dynamic scheduling of instructions from within those fragments. The hardware also recognises different classes of variables from the register specifiers, which allows the hardware to manage locality and optimise communication so that it is both efficient and scalable. [ABSTRACT FROM AUTHOR]

We discuss nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs and present a new optimal diffusion scheme for general graphs. In the first part of the paper, we introduce the Alternating-Direction load balancing scheme, which reduces the number of load balance iterations by a factor of 2 for cartesian products of graphs. The resulting flow is theoretically analyzed and can be very high for certain cases. Therefore, we further present the Mixed-Direction scheme which needs the same number of iterations but computes in most cases a much smaller flow. In the second part of the paper, we present a simple optimal diffusion scheme for general graphs, calculating a balancing flow which is minimal in the l2 norm. It is based on the spectra of the graph representing the network and needs only m — 1 iterations to balance the load with m being the number of distinct eigenvalues. Known optimal diffusion schemes have the same performance, however the optimal scheme presented in this paper can be implemented in a very simple manner. The number of iterations of optimal diffusion schemes is independent of the load scenario and, thus, they are practical for networks which represent graphs with known spectra. Finally, our experiments exhibit that the new optimal scheme can successfully be combined with the Alternating-Direction and Mixed-Direction schemes for efficient load balancing on product graphs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The common definition for robust solutions considers a solution robust if it remains optimal (or near optimal) when the parameters defining the fitness function are perturbed. We call this parameter robustness or temporal robustness. In this paper we propose an alternate definition for robustness, which we call spatial or solution robustness, if both the solution and the neighbourhood around the solution has high fitness. With this definition, we created a set of functions with useful properties to allow for the testing of solution robustness. We then focus on the effect of the precision (density) of the search space and find that it has a drastic effect on both the number of solutions and their quality. [ABSTRACT FROM AUTHOR]

This paper is intended as a survey of the state of the art of some branches of Biomolecular Computing. Biomolecular Computing aims to use biological hardware (biomare), rather than chips, to build a computer. We discuss the following three main research directions: DNA computing, membrane systems, and gene assembly in ciliates. DNA computing combines practical results together with theoretical algorithm design. Various search problems have been implemented using DNA strands. Membrane systems are a family of computational models inspired by the membrane structure of living cells. The process of gene assembly in ciliates has been formalized as an abstract computational model. Biomolecular Computing is a field in full development, with the promise of important results from the perspective of both Computer Science (models of computation) and Biology (understanding biological processes). [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of gathering information in a specific node (or sink) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most dT in the graph, but when doing so it generates interference that does not allow nodes at distance up to dI (dI ≥ dT) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is NP-HARD, for any values of dI and dT. If dI > dT, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. [ABSTRACT FROM AUTHOR]

Computing the 1-D Fast Fourier Transform (FFT) using the conventional six-step FFT algorithm on parallel computers requires intensive all-to-all communication due to the necessity of matrix transpose in three steps. This all-to-all communication is a limiting factor in improving the performance of FFT in its parallel implementations. In this paper, we present two parallel algorithms for implementing the 1-D FFT without all-to-all communication between processors, at the expense of increased inner-processor computation as compared to the conventional six-step FFT algorithm. Our analysis reveals the advantage of these two algorithms over the six-step FFT algorithm in parallel systems where the cost of inter-processor communication outweighs the cost of inner-processor computation. As a case study, we choose a 32-node Beowulf cluster with fast processors (running at 2 GHz) but relatively slow inter-processor communication (over a 100 Mbit/s switch). Simulation results on this cluster demonstrate that the proposed no-communication FFT algorithms can achieve a speedup ranging from 1.1 to 1.5 over the six-step FFT algorithm. [ABSTRACT FROM AUTHOR]

Leader-based protocols rest on a primitive able to provide the processes with the same unique leader. Such protocols are very common in distributed computing to solve synchronization or coordination problems. Unfortunately, providing such a primitive is far from being trivial in asynchronous distributed systems prone to process crashes. (It is even impossible in fault-prone purely asynchronous systems.) To circumvent this difficulty, several protocols have been proposed that build a leader facility on top of an asynchronous distributed system enriched with synchrony assumptions. This paper introduces a novel approach to implement an eventual leader protocol, namely a time-free behavioral assumption on the flow of messages that are exchanged. It presents a very simple leader protocol based on this assumption. It then presents a second leader protocol combining this timeless assumption with eventually timely channels. As it considers several assumptions, the resulting hybrid protocol has the noteworthy feature to provide an increased overall assumption coverage. A probabilistic analysis shows that the time-free assumption is practically always satisfied. [ABSTRACT FROM AUTHOR]

Data-Driven Multithreading is a non-blocking multithreading model of execution that provides effective latency tolerance by allowing the computation processor do useful work, while a long latency event is in progress. With the Data-Driven Multithreading model, a thread is scheduled for execution only if all of its inputs have been produced and placed in the processor's local memory. Data-driven sequencing leads to irregular memory access patterns that could affect negatively cache performance. Nevertheless, it enables the implementation of short-term optimal cache management policies. This paper presents the implementation of CacheFlow, an optimized cache management policy which eliminates the side effects due to the loss of locality caused by the data-driven sequencing, and reduces further cache misses. CacheFlow employs thread-based prefetching to preload data blocks of threads deemed executable. Simulation results, for nine scientific applications, on a 32-node Data-Driven Multithreaded machine show an average speedup improvement from 19.8 to 22.6. Two techniques to further improve the performance of CacheFlow, conflict avoidance and thread reordering, are proposed and tested. Simulation experiments have shown a speedup improvement of 24% and 32%, respectively. The average speedup for all applications on a 32-node machine with both optimizations is 26.1. [ABSTRACT FROM AUTHOR]

In this paper, we describe in detail a novel SQL service based on radix tree data structures and we show how to multithread the service in order to execute it on distributed platforms. The SQL service is currently developed in the context of SMP platforms but should be deployed in the future on grid platforms. The development of the SQL service is part of the Grid Explorer project. The project (French part) aims at building a grid emulator to study the behavior of grids. One need in the project is for a database software to store experimental conditions and to analyze traces of execution (for instance, to find in "real time" frequent episodes for the CPU load metric in order to predict the future state of the grid). We plan to use our SQL service on an SMP platform for this purpose. [ABSTRACT FROM AUTHOR]

This research addresses scheduling issues in networked computer systems with survivability requirements, i.e. systems in which essential services must survive malicious acts. In order to achieve survivability based on spatial redundancy, agreement algorithms are needed as a mechanism to consolidate results of individual replicas. The potentially enormous overhead associated with communication and voting schemes of the algorithms put unique burdens on the scheduler as the efficiency of scheduling determines the suitability of the agreement algorithm. This paper derives agreement task graphs, representing computations, and inter-process communication based on phantom tasks. Task graph primitives are identified and it is shown how their scheduling directly influences the performance of the agreement algorithm. Finally, the notion of dynamic k-of-N precedence is introduced and its impact on resource reclaiming for early stopping algorithms is discussed. [ABSTRACT FROM AUTHOR]

The classical way of tuning parallel/distributed applications is based on the analysis of the monitoring information obtained from an execution of the application. However, this "measure and modify" approach is not feasible when the applications have a dynamic behavior. In this case, another approach is required to accomplish performance expectations. This paper presents a solution based on the dynamic tuning approach that addresses these issues. In this approach, an application is monitored, its performance bottlenecks are detected and the application is modified automatically during the execution, without stopping, recompiling or re-running it. The introduced modifications adapt the behavior of the application to dynamic variations. [ABSTRACT FROM AUTHOR]

Interconnecting computers into clusters or computational grids promises many benefits for users of computational science and engineering, especially in terms of performance and costs. This situation is additionally supported by programming libraries like MPI and PVM, which are portable across different platforms and allow to exploit the available computing power. Consequently, the number of applications utilizing these computing structures is steadily increasing. Yet, there are also some pitfalls with possibly serious consequences, that must not be ignored by software developers. This paper describes some critical issues related to nondeterministic program behavior. With such kinds of programs different program executions are observed although the same input data are provided, leading to the irreproducibility effect, the completeness problem, and the probe effect. The impact of these effects, their weight for software developers, and how they are affected on supercomputer architectures and cluster environments are discussed. These critical issues need to be pointed out to users in order to raise their understanding and awareness of the problems. While the irreproducibility effect is believed to be sufficiently solved by record&replay mechanisms, existing solutions for the probe effect are only partially successful, and only very few approaches address the completeness problem. A simple solution for the latter is offered by automatic event manipulation and artificial replay, which is however restricted by time and memory constraints. In addition, this solution to the completeness problem also solves the probe effect in nondeterministic parallel programs. [ABSTRACT FROM AUTHOR]

A novel parallelization of the Lepp-bisection algorithm for triangulation refinement on multicore systems is presented. Randomization and wise use of the memory hierarchy are shown to highly improve algorithm performance. Given a list of selected triangles to be refined, random selection of candidates together with pre-fetching of Lepp-submeshes lead to a scalable and efficient multi-core parallel implementation. The quality of the refinement is shown to be preserved. [ABSTRACT FROM AUTHOR]

We present a novel “lazy” list-based implementation of a concurrent set object. It is based on an optimistic locking scheme for inserts and removes and includes a simple wait-free membership test. Our algorithm improves on the performance of all previous such algorithms. [ABSTRACT FROM AUTHOR]