An important development in cluster computing is the availability of multiprocessor workstations. These are able to provide additional computational power to the cluster without increasing network overhead and allow multiparadigm parallelism, which we define to be the simultaneous application of both distributed and shared memory parallel processing techniques to a single problem. In this paper we compare execution times and speedup of parallel programs written in a pure message-passing paradigm with those that combine message passing and shared-memory primitives in the same application. We consider three basic applications that are common building blocks for many scientific and engineering problems: numerical integration, matrix multiplication and Jacobi iteration. Our results indicate that the added complexity of combining shared- and distributed-memory programming methods in the same program does not contribute sufficiently to performance to justify the added programming complexity.

The paper describes initial findings regarding the performance tradeoffs between cluster computing where the participating processors are independent machines connected by a high speed switch and desktop multiprocessing where the processors reside within a single workstation and share a common memory. While interprocessor communication time has typically been cited as the limiting force on performance in the cluster, bus and memory contention have had similar effects in shared memory systems. The advent of high speed interconnects and improved bus and memory access speeds have enhanced the performance curves of both platforms. We present comparisons of the execution times of three applications with varying levels of data dependencies-numerical integration, matrix multiplication, and Jacobi iteration across three environments: the PVM distributed memory model, the PVM shared memory model, and the Solaris threads package.

The advantages of workstation clusters as a parallel computing platform include a superior price-performance ratio, availability, scalability, and ease of incremental growth. However, the performance of traditional LAN technologies such as Ethernet and FDDI rings are insufficient for many parallel applications. This paper describes APACHE (Automated Pvm Application CHaracterization Environment), an automated analysis system that uses an application-independent model for predicting the impact of ATM on the execution time of iterative parallel applications. APACHE has been used to predict the performance of several core applications that form the basis for many real scientific and engineering problems. We present a comparison of the performance predicted by APACHE with observed execution times to demonstrate the accuracy of our model. Finally, we present a method for a simple cost-benefit analysis that can be used to determine whether an investment in ATM equipment is justified for a particular workstation cluster environment.

This paper investigates the usefulness of block partitioning in cluster computing in light of recent network improvements such as FDDI and high-speed switch technology. Mathematical characterizations of the communication costs for contiguous partitioning and block decomposition in both a ring-connected and switched network are presented. Simulations of ring and switch technologies indicate that as network speeds increase and as the effects of message-preparation latency dominate, the advantages claimed for block decomposition diminish.

Rapid increases in computing and communication performance are exacerbating the long-standing problem of performance-limited input/output. Indeed, for many otherwise scalable parallel applications. input/output is emerging as a major performance bottleneck. The design of scalable input/output systems depends critically on the input/output requirements and access patterns for this emerging class of large-scale parallel applications. However, hard data on the behavior of such applications is only now becoming available. In this paper, we describe the input-output requirements of three scalable parallel applications (electron scattering, terrain rendering, and quantum chemistry, on the Intel Paragon XP/S. As part of an ongoing parallel input/output characterization effort, we used instrumented versions of the application codes to capture and analyze input/output volume, request size distributions, and temporal request structure. Because complete traces of individual application input/output requests were captured, in-depth, off-line analyses were possible. In addition, we conducted informal interviews of the application developers to understand the relation between the codes' current and desired input/output structure. The results of our studies show a wide variety of temporal and spatial access patterns, including highly read-intensive and write-intensive phases, extremely large and extremely small request sizes, and both sequential and highly irregular access patterns. We conclude with a discussion of the broad spectrum of access patterns and their profound implications for parallel file caching and prefetching schemes.

Abstract With the increased performance capabilities of desktop computers, networked computing has become a popular vehicle for using parallelism to solve a variety of computationally intense problems. However, node heterogeneity and high communication costs may limit performance unless the problem space is carefully partitioned across the network in a way that considers both the capabilities of the machines and the high network communication costs. We describe an advisory system that is designed to help the programmer, compiler or run‐time environment choose the best decomposition strategy for partitioning specific data‐parallel applications across a given collection of machines. The system includes provisions for assessing the capabilities of the participating machines and the network in light of the current workload. Given information about the problem space, the machine speeds and the network, the system provides a ranking of three standard partitioning methods. We test the validity of our system by comparing the observed relative performance with predicted relative performance of different data decompositions on a program with a variable number of floating point operations and a 5‐point stencil communication pattern.

Networked computing has become a popular method for using parallelism to solve a variety of computationally intense problems. However, high communication costs and processor heterogeneity may limit performance unless the problem space is carefully partitioned. We propose a decomposition advisory system that is designed to help choose the best data partitioning strategy. The goal of this research is to determine the partitioning scheme(s) expected to yield the best performance for a particular data-parallel problem with known regular communication patterns on a collection of heterogeneous processors. Given information about the problem space and the network, the system provides a ranking of standard partitioning methods.>

The authors present a block data decomposition algorithm for two-dimensional grid problems. Their method includes local balancing to accommodate heterogeneous processors, and they characterize the conditions that must be met for their partitioning strategy to be of value. While they concentrate on the workstation network model of parallel processing because of its high communication costs and inherent heterogeneity, their method is applicable to other parallel architectures.>