The parallel quicksort algorithm part 2—simulation

This paper is the second of a two part series in which a general purpose sorting algorithm i.e. Quicksort is adapated for execution on an M.I.M.D. computer system. In this part, the parallel algorithm derived in Part 1 is simulated and qualitative agreement with the results from the run-time analysis was obtained.     

Hypercube computing: Connected components

Several approaches to finding the connected components of a graph on a hypercube multicomputer are proposed and analyzed. The results of experiments conducted on an NCUBE hypercube are also presented. The experimental results support the analysis.This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.     

Mesh-connected parallel computer PAX for scientific applications

Nearest-neighbor-mesh connection plus global broadcasting/control bus characterizes the architecture of the processor array PAX, that was constructed for and is now operating in many typical scientific applications. Not only these inter-processor connections, but also an MIMD structure of the machine were found effective in the particle transport problems, that require asynchronous operation.

The paper describes the bases of architecture of two recent versions of the PAX computer, their hardware and software systems, and, based on the implementation of scientific applications, the effectiveness of the PAX type architecture is presented.     

Design and optimization of parallel computers for processing mass data

Problems of high-performance processing of mass cluster data are considered. Estimates of execution times of parallel data processing programs and a heuristic algorithm of optimization of cluster architectures for such problems are proposed. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 117–129, July–August 2006.     

Static scheduling for barrier MIMD architectures

In a SIMD or VLIW machine, conceptual synchronizations are accomplished by using a static code schedule that does not require run-time synchronization. The lack of run-time synchronization overhead makes these machines very effective for fine-grain parallelism, but they cannot execute parallel code structures as general as those executed by MIMD architectures, and this limits their utility.In this paper we present a timing analysis that allows a compiler for a MIMD machine to eliminate a large fraction of the run-time synchronization by making efficient use of static code scheduling. Although these techniques can be adapted to be applied to most MIMD machines, this paper centers on the analysis and scheduling for barrier MIMD machines. Barrier MIMDs are asynchronous multiple instruction stream/multiple data stream architectures capable of parallel execution of variable execution-time instructions and arbitrary control flow (e.g., while loops and calls). However, they also incorporate a special hardware barrier synchronization mechanism that facilitates static scheduling by providing a mechanism which the compiler can use to enforce precise timing constraints. In other words, the compiler tracks relative timing between processors and uses static code scheduling until the timing imprecision becomes too large, at which point the compiler simply inserts a barrier to reduce that timing imprecision to zero (or a small constant).This paper describes new scheduling and barrier placement algorithms for barrier MIMDs that are based loosely on the list scheduling approach employed for VLIWs [Ellis 1985]. In addition, the experimental results from scheduling thousands of synthetic benchmark programs for a parameterized barrier MIMD machine are presented.     

A MIMD implementation of a parallel Euler solver for unstructured grids

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a MIMD (multiple instruction/multiple data stream) parallel computer. Three partitioning strategies for distributing the work load onto the processors are discussed. Issues pertaining to the communication costs are also addressed. We find that the spectral bisection strategy yields the best performance. The performance of this unstructured computation on the Intel iPSC/860 compares very favorably with that on a one-processor CRAY Y-MP/1 and an earlier implementation on the Connection Machine.The authors are employees of Computer Sciences Corporation. This work was funded under contract NAS 2-12961     

多Transputer系统上的并行消隐算法及其图形显示

本文讨论了三维物体隐面消除的并行处理问题。给出了一类ＭＩＭＤ并行深度缓冲器算法，并在多Ｔｒａｎｓｐｕｔｅｒ系统上实现。文中还对这些算法的效率进行了比较。     

On solving systems of ordinary differential equations on MIMD-computers

The error of solution of Cauchy problems for systems of ordinary differential equations is estimated in the case where the input data are approximate. It is shown how to prepare a program for computing the right-hand sides of the system automatically and simultaneously. Diagrams are presented to illustrate the efficiency of parallelization. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 175–182, March–April 2007.     

A parallel sorting algorithm for a novel model of computation

The computational complexity of a parallel algorithm depends critically on the model of computation. We describe a simple and elegant rule-based model of computation in which processors apply rules asynchronously to pairs of objects from a global object space. Application of a rule to a pair of objects results in the creation of a new object if the objects satisfy the guard of the rule. The model can be efficiently implemented as a novel MIMD array processor architecture, the Intersecting Broadcast Machine. For this model of computation, we describe an efficient parallel sorting algorithm based on mergesort. The computational complexity of the sorting algorithm isO(nlog² n), comparable to that for specialized sorting networks and an improvement on theO(n ^1.5) complexity of conventional mesh-connected array processors.     

A bistability throughput phenomenon in a shared-memory MIMD machine

This paper examines a previously unanalyzed bistability phenomenon with respect to the number of threads that are doing useful work. This phenomenon is illustrated by a single work queue on a shared-memory machine. An analysis of designs that use two separate memory accesses to lock and unlock critical sections (split transaction) and that employ a first come/first serve queuing mechanism for shared-memory locations is presented. A bistability in the number of threads working, brought about by these conditions, is analyzed and experimentally demonstrated. A simple analysis is presented which predicts the throughput at a critical section of code as a function of the number of applied threads. The study concludes that the mean size of the work items that can be executed in parallel without the possibility of stalling is proportional to the square of the number of threads applied.