Search

There has been a great deal of interest recently in the development of general-purpose bridging models for parallel computation. Models such as the BSP and LogP have been proposed as more realistic alternatives to the widely-used PRAM model. The BSP and LogP models imply a rather different style for designing algorithms when compared to the PRAM model. Indeed, while many consider data parallelism as a convenient style, and the shared-memory abstraction as an easy-to-use platform, the bandwidth limitations of current machines have diverted much attention to message-passing and distributed-memory models (such as the BSP and LogP) that account more properly for these limitations. In this paper we consider the question of whether a shared-memory model can serve as an effective bridging model for parallel computation. In particular, can a shared-memory model be as effective as, say, the BSP? As a candidate for a bridging model, we introduce the Queuing Shared Memory (QSM) model, which accounts for limited communication bandwidth while still providing a simple shared-memory abstraction. We substantiate the ability of the QSM to serve as a bridging model by providing a simple work-preserving emulation of the QSM on both the BSP, and on a related model, the (d,x)-BSP. We present evidence that the features of the QSM are essential to its effectiveness as a bridging model. In addition, we describe scenarios in which the high-level QSM more accurately models certain machines than the more detailed BSP and LogP models. Finally, we present algorithmic results for the QSM, as well as general strategies for mapping algorithms designed for the BSP or PRAM models onto the QSM model. Our main conclusion is that shared-memory models can potentially serve as viable alternatives to existing message-passing, distributed-memory bridging models.

Cluster of workstation or personal computers connected with high speed network has become one of major architectures of distributed memory parallel computers. However, software on the cluster environment is still not improved in performance. The distributed shared memory can be a solution of programming style on distributed memory parallel system including clusters because we know from experiences that shared memory model ease programming. However, it must be implemented with care for the performance problem where there is no hardware support for shared memory system. Another, but serious problem is the portability. In this paper, we discuss the design and implementation of portable distributed shared memory system. Our shared memory system is based on PVM in consideration of portability. Our contributions in this paper is the design and implementation of portable shared memory system on the cluster environment using faithful implementation of active messages fully in software, together with an enhancement of PVM to support active messages.

We investigate distributed parallel computation of a general dynamic programming problem given by a class of dynamic programming recurrences. Our approach is to partition the dynamic programming array into square blocks and use a kind of pipelining, instead of computing the array by diagonals, or by rows/columns, see [7]. One possibility is to make a coarse-grained implementation of systolic algorithms from [3, 4]. We choose a completely different approach and start with a new synchronous shared-memory algorithm for the problem. The fine-grained synchronous parallel computation is transformed into a coarse-grained message-passing algorithm. The dynamic programming array (usually very large) is distributed in such a way that each machine keeps only a small portion of the array and the whole array does not need to be stored in one large piece anywhere. The synchronous shared memory model is a better starting point for distributed implementation compared with any systolic algorithm (with much larger degree of synchronization), since it enables more alternative implementations. Incidentally, our approach gives also a new and simple alternative algorithm working on a mesh of processors. We discuss three alternative implementations and compare the suitability of PVM and MPI models for the problem.

IN SEARCH of efficient fault-tolerant algorithms, it is important to also consider the lower bounds for relevant problems. The efficiency achieved by a fault-tolerant Write-All algorithm in a particular parallel model needs to be contrasted with the lower bound results for the model. If there is a gap between the upper and lower bounds results, then there is a possibility of developing better algorithms.

The right model of parallel computation must possess various properties including accurately predicting the behavior of real programs on physical computers. It is argued that this property must be tested experimentally. Three experiments are reviewed supporting the hypothesis that the CTA machine model and the Phase Abstractions programming model predict accurately for real programs on physical computers. Data for ten MIMD computers is reported. Additionally, basic concepts connected with models of computation are reviewed, and several recently developed parallel models are critiqued.

Networks of workstations have become widely available. The consoles are mostly occupied, whilst the aggregate computational power remains idle. This problem has been addressed by several software packages that allow the remote management of processes and the communication between them. These solutions work reasonably well for message-passing programming and applications with a very coarse grain parallelism. The shared memory programming model is preferable, but its implementation on top of message-passing is cumbersome. Applications with a finer grain of parallelism yield unacceptable performance. At ENST, we are currently designing a device called WARPmemory that makes shared memory physically available to a number of workstations. Each workstation has a direct access link (high bandwidth, low latency) making data sharing and synchronization very fast. Message-passing can be optimiled also. It is important to our approac~h that an existing programming interface is used, thereby preserving existing investment in parallel software. WARPmemory is a transparent accelerator for parallel programming on a network of workstations.

Over the years, various programming techniques have been applied to get maximum performance out of high-end computers. Examples are vectorization and loop level parallelization on shared memory vector processors, and coarse-grained parallelism on distributed memory systems, like MPP computers and clusters of workstations. This paper discusses these programming techniques, using a simple but representative numerical example, concluding with the shared memory programming model of Convex Exemplar Series SPP systems. The architecture and programming model of this scalable parallel system will be discussed in some detail.

The medial axis transform (MAT) represents a region of a digital image as the union of maximal upright squares contained in the region. This paper presents algorithm to compute the contour, perimeter, and area of the region covered by a set of n upright rectangles in O ( n ) time using O ( n ) processors for the shared memory model, and using O ( n 2 ) processors for mesh-connected computers.

The problem of selecting thekth largest or smallest element of {x i +y j |x i eX andy j eY ∀i,j} whereX=(x 1,x 2, ..,x n ) andY=(y 1,y 2, ...,y n ) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n 1+1/β) processors is presented where β is a pre-assigned constant lying between 1 and 2.

We present a deterministic leader election protocol that can tolerate up to n−1 undetectable initial failures, where n is the number of processes. We assume an asynchronous shared memory model that supports only single writer and multi readers regular registers

We describe an O(log( n )) time with O( n ) processors optimal algorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing).

We focus on unreliable asynchronous shared memory model which support only atomic read and write operations. For such a model we provide a necessary condition for the solvability of problems in the precence of multiple undetectable crash failures. Also, by using game-theoretical notions, a necessary and sufficient condition is provided, for the solvability of problems in the precence of multiple undetectable initial failures