bluuebunny/crossref_metadata_2025_split huggingface dataset:
Parallel processing architectures used in a realtime display application
Authors: Vaughan J. R. , Brookes G. R. , Fletcher M. A. , Wills D. P. M. 
Published: November 2006

AbstractData which is stored as a terrain data base is to be displayed graphically in a real‐time application. Various parallel configurations of processing elements have been used to achieve the required performance. The results which have been achieved using transputers as the processing elements are presented in this report.
Performance of dynamic load balancing algorithms for unstructured mesh calculations
Authors: Williams Roy D. 
Published: November 2006

AbstractIf a finite element mesh has a sufficiently regular structure, it is easy to decide in advance how to distribute the mesh among the processors of a distributed‐memory parallel processor, but if the mesh is unstructured the problem becomes much more difficult. The distribution should be made so that each processor has approximately equal work to do, and such that communication overhead is minimized.If the mesh is solution‐adaptive, i.e. the mesh and hence the load‐balancing problem change discretely during execution of the code, then it is most efficient to decide the optimal mesh distribution in parallel. In this paper three parallel algorithms, orthogonal recursive bisection (ORB), eigenvector recursive bisection (ERB) and a simple parallelization of simulated annealing (SA) have been implemented for load balancing a dynamic unstructured triangular mesh on 16 processors of an NCUBE machine.The test problem is a solution‐adaptive Laplace solver, with an initial mesh of 280 elements, refined in seven stages to 5772 elements. We present execution times for the solver resulting from the mesh distributions using the three algorithms, as well as results on imbalance, communication traffic and element migration.The load‐balancing itself is fastest with ORB, but a very long run of SA produces a saving of 21% in the execution time of the Laplace solver. ERB is only a little slower than ORB, and yet produces a mesh distribution whose execution time is 15% faster than ORB.
Performance of a particle‐in‐cell plasma simulation code on the BBN TC2000
Authors: Sturtevant Judy E. , Campbell Phil M. , Maccabe Arthur B. 
Published: November 2006

AbstractThe BBN TC2000 is a multiple instruction, multiple data (MIMD) machine that combines a physically distributed memory with a logically shared memory programming environment using the unique Butterfly switch. Particle‐in‐cell (PIC) plasma simulations model the interaction of charged particles with electric and magnetic fields. This paper describes the implementation of both a 1‐D electrostatic and a 2 1/2‐D electromagnetic PIC (particle‐in‐cell) plasma simulation code on a BBN TC2000. Performance is compared to implementation of the same code on the shared memory Sequent Balance 21000.
Numerical simulation of three‐dimensional thermal convection on the array processor DAP 510
Authors: Erhard W. , Schäfer M. 
Published: November 2006

AbstractIn this paper we deal with the numerical simulation of time dependent three‐dimensional thermal convection on the array processor DAP 510. Applying finite differences in combination with a pressure correction method to the underlying non‐linear system of partial differential equations, we reduce the numerical solution of the problem to the solution of a sequence of sparse linear systems. Using polynomial preconditioned conjugate gradient methods for the solution of these systems results in a highly parallel algorithm for the simulation of the considered flows on the DAP 510. Using this parallel algorithm, data can be mapped in different ways onto the processor array. Depending on the number of grid points, several methods are shown. Numerical experiments illustrate the capabilities of the proposed algorithm.
Fault‐tolerant parallel programming in Argus
Authors: Bal Henri E. 
Published: November 2006

AbstractFault tolerance is an issue ignored in most parallel languages. The overhead of making parallel, high‐performance programs resilient to processor crashes is often too high, given the low probability of such events. If parallel systems become more large‐scaled, however, processor failures will become likely, so they should be dealt with. Two approaches to this problem are feasible. First, the system can make programs fault‐tolerant transparently. It can log messages, make checkpoints, and so on. Second, the programmer can write explicit code for handling failures in an application‐specific way. The latter approach is potentially more efficient, but also requires more work from the programmer. In this paper, we intend to get some initial insight into how hard and efficient explicit fault‐tolerant parallel programming is. We do so by implementing four parallel applications in Argus, a language supporting parallelism as well as fault tolerance. Our experiences indicate that the extra effort needed for fault tolerance varies much between different applications. Also, trade‐offs can frequently be made between programming effort and efficiency. One lesson we learned is that fault tolerance should not be added as an afterthought, but is best taken into account from the start. As another result, the ability to integrate transparent and explicit mechanisms for fault tolerance would sometimes be highly useful.
Computation and data movement on RP3
Authors: Brochard Luigi , Freau Alex 
Published: November 2006

AbstractWe present in this paper a study of the computation and communication costs on RP3 and on some issues about algorithm designs on a three‐level memory hierarchy multi‐processor. Using very simple algorithms (vector‐add, vector‐sum, saxpy, … ), we compare different implementations which differ on data localization (global or local) and data cacheability (cacheable or non‐cacheable). This comparison is done using a performance monitoring system (VPMC) that records instructions, data movement, cache requests and misses. The output of the VPMC was then used as input to an analytical performance model which we used to compute the elemental computation and communication times of every basic algorithm. Regarding cacheability (marking the data cacheable instead of non‐cacheable), we found it worthwhile as long as data are blocked adequately. For our simple 1‐D data structures, a block size equal to a multiple of the cache line size gives the best results. However, considering possible load imbalance, a block size equal to the cache line seems optimal. Regarding localization (copying data from global to local, working on local data instead of global and copying data back), we found it ineffective, at least with the RP3 local and global communication speed ratios (1:10:15).
Designing Algorithms on RP3
Authors: Brochard Luigi , Freau Alex 
Published: November 2006

AbstractWe study here the behavior of two numerical algorithms (matrix multiplication and finite difference method) on a three‐level memory hierarchy multi‐processor RP3. Using different versions of these algorithms, which differ on data placement (global, local, global and cacheable, local and cacheable) and on data access (blocked or non‐blocked), we study the impact of these parameters on the performance of the program. This performance analysis is done using a very accurate monitoring system (VPMC) which records instructions, memory requests, cache requests and misses. We perform also a theoretical performance analysis of these programs using a model of computation and communication. Good agreement is found between theoretical and experimental results. As a conclusion we discuss the use of local memory on such a machine and show that it is ineffective with RP3 cache, local and global memory communication speed ratios. We also discuss optimal use of cache and show that the optima can only be realized under some cache properties (private store‐in cache with user control of write‐back) and show that blocked optimal algorithms are to be used to find it. Comparing programming of shared and distributed memory multi‐processors, we remark that optimized algorithms for shared memory systems utilize the same blocking techniques used for programming distributed memory systems, leading to a common programming paradigm.
Parallel‐processing applications for data analysis in the social sciences
Authors: Skvoretz John , Smith Shelley A. , Baldwin Chuck 
Published: November 2006

AbstractWe examine parallel‐processing applications to the analysis of large data sets typically used in social science research. Our research uses a parallel environment which makes it possible to have 1024 processors working simultaneously on a problem. The application is tested using various configurations of number of processors and block‐size of data reads on the estimation of a linear model of earnings for the California portion of the 15% sample of the 1970 Census. Performance factors assessed include total execution time, speed‐up and efficiency. Execution times are also compared with reference to execution times on an IBM 3081 using SPSS‐X. Results indicate that optimal configurations of number of processors and data block‐size can produce significantly faster execution times for linear model estimation on relatively large (80,000 cases) data sets. We also discuss other applications of parallel processing to statistical analyses commonly found in social science.
Data parallel sorting for particle simulation
Authors: Dagum Leonardo 
Published: November 2006

AbstractSorting on a parallel architecture is a communications intensive event which can incur a high penalty in applications where it is required. In the case of particle simulation, only integer sorting is necessary, and sequential implementations easily attain the minimum performance bound of O(N) for N particles. Parallel implementations, however, have to cope with the parallel sorting problem which, in addition to incurring a heavy communications cost, can make the minimum performance bound difficult to attain. This paper demonstrates how the sorting problem in a particle simulation can be reduced to a merging problem, and describes an efficient data parallel algorithm to solve this merging problem in a particle simulation. The new algorithm is shown to be optimal under conditions usual for particle simulation, and its fieldwise implementation on the Connection Machine is analysed in detail. The new algorithm is about four times faster than a fieldwise implementation of radix sort on the Connection Machine.
Hypercube clock synchronization
Authors: Dunigan Thomas H. 
Published: November 2006

AbstractAlgorithms for synchronizing the times and frequencies of the clocks of Intel and Ncube hypercube multiprocessors are presented. Bounds for the error in estimating clock offsets and frequencies are formulated in terms of the clock read error and message transmission time. Clock and communication performance of the Ncube and Intel hypercubes are analysed, and performance of the synchronization algorithms is presented.
Efficient communication primitives on hypercubes
Authors: Ho Ching‐Tien , Raghunath M. T. 
Published: November 2006

AbstractWe give practical algorithms, complexity analysis and implementation for one‐to‐all broadcasting, all‐to‐all personalized communication and matrix transpose (with two‐dimensional partitioning of the matrix) on hypercubes. We assume the following communication characteristics: circuit‐switched, e‐cube routing and one‐port communication model.For one‐to‐all broadcasting, we give an algorithm that combines the well‐known recursive doubling algorithm[1] and the algorithm based on edgedisjoint spanning trees[2]. The measured times of the combined algorithm are always superior to those of the edge‐disjoint spanning tree algorithm and outperform the recursive doubling algorithm. For all‐to‐all personalized communication we propose a hybrid algorithm that combines the well‐known recursive doubling algorithm[3,4] and the recently proposed direct‐route algorithm[5,6] Our hybrid algorithm balances between data transfer time and start‐up time of these two algorithms, and its communication complexity is estimated to be better than the two previous algorithms for a range of machine parameters. For matrix transpose with two‐dimensional partitioning of the matrix, we relate a two‐phase algorithm to the previous result in Reference 7. The algorithm is predicted to be better than the recursive transpose algorithm[8] by n nearest‐neighbor communications[4]. It takes advantage of circuit‐switched routing and is congestion‐free within each phase. We also suggest a way of storing the matrix such that the transpose operation can be realized in one phase without congestion.
A fast poisson solver for distributed memory multiprocessors
Authors: Serafino D. Di , Murli A. , Perla F. 
Published: November 2006

AbstractWe present a parallel algorithm for distributed memory multiprocessors, which is based on generalized marching (GM), one of the fastest methods in the class of fast Poisson solvers.The GM algorithm is not suited for any but very coarse‐grain parallel processing. The main difficulty with parallelization is that the number of independent processes and the amount of work in each process change exponentially and in inverse proportion of each other.To improve parallelism, the matrices involved in GM are diagonalized performing multiple FFTs. In this way, independent processes extending across all the algorithm are obtained.The parallel GM has been tested on an Ncube/10 and a Symult S2010, running the Express communication system. A performance evaluation has been carried out using a scaled efficiency model and some classical parameters.
Parallelizing the spectral transform method. Part II
Authors: Walker David W. , Worley Patrick H. , Drake John B. 
Published: November 2006

AbstractThe spectral transform method is a widely used numerical technique for solving partial differential equations on the sphere in global climate modeling. This paper describes the parallelization and performance of the spectral method for solving the non‐linear shallow water equations on the surface of a sphere using a 128‐node Intel iPSC/860 hypercube. Solving the shallow water equations represents a computational kernel of more complex climate models. This work is part of a research program to develop climate models that are capable of much longer simulations at a significantly finer resolution than current models. Such models are important in understanding the effects of the increasing atmospheric concentrations of greenhouse gases, and the computational requirements are so large that massively parallel multiprocessors will be necessary to run climate model simulations in a reasonable amount of time.The spectral method involves the transformation of data between the physical, Fourier and spectral domains. Each of these domains is two‐dimensional. The spectral method performs Fourier transforms in the longitude direction followed by summation in the latitude direction to evaluate the discrete spectral transform. A simple way of parallelizing the spectral code is to decompose the physical problem domain in just the latitude direction. This allows an optimized sequential FFT algorithm to be used in the longitude direction. However, this approach limits the number of processors that can be brought to bear on the problem. Decomposing the problem over both directions allows the parallelism inherent in the problem to be exploited more effectively‐the grain size is reduced, so that more processors can be used.Results are presented that show that decomposing over both directions does result in a more rapid solution of the problem. The results show that, for a given problem and number of processors, the optimum decomposition has approximately equal numbers of processors in each direction. Load imbalance also has an impact on the performance of the method. The importance of minimizing communication latency and overlapping communication with calculation is stressed. General methods for doing this, that may be applied to many other problems, are discussed.
Parallel program design using high‐level Petri nets
Authors: Gorton Ian 
Published: November 2006

AbstractPetri nets are proposed as a general‐purpose design and modelling tool for parallel programs. The advantages of Petri nets for this purpose are discussed, and a solution to the Dining Philosophers problem is developed using simple Place‐Transition nets. The limitations of Place‐Transition nets are described, and the Dining Philosophers problem is used to illustrate how Coloured Petri nets can overcome these limitations. A more complex example of a Coloured Petri net is then given, and it is shown how a collection of processes in the Occam programming language can be developed directly from the properties of the net. Another Petri net model of a simple process farm is given, and a solution is developed in Parallel C: this further highlights the suitability of Petri nets as a design tool for parallel programs.
Massively parallel solution of quadratic programs via successive overrelaxation
Authors: De Leone R. , Roth M. A. Tork 
Published: November 2006

AbstractSerial and parallel successive overrelaxation (SOR) solutions of specially structured large‐scale quadratic programs with simple bounds are discussed. By taking advantage of the sparsity structure of the problem, the SOR algorithm was successfully implemented on two massively parallel Single‐Instruction‐Multiple‐Data machines: a Connection Machine CM‐2 and a MasPar MP‐1. Computational results for the well known obstacle problems show the effectiveness of the algorithm. Problems with millions of variables have been solved in a few minutes on these massively parallel machines, and speed‐ups of 90% or more were achieved.
Empirical analysis of overheads in cluster environments
Authors: Schmidt Brian K. , Sunderam Vaidy S. 
Published: November 2006

AbstractIn concurrent computing environments based on heterogeneous processing elements interconnected by general‐purpose networks, several classes of overheads contribute to lowered performance. The most obvious limitations are network throughput and latency, but certain other factors also play a significant role. In an attempt to gain some insight into the nature of these overheads, and to propose strategies to alleviate them, empirical measurements of native communication performance as well as application execution performance were conducted, using the PVM network computing system. These experiments and our analyses have identified load imbalance, the parallelism model adopted, communication delay and throughput, and within‐host overheads as the primary factors affecting performance in cluster environments. Interestingly, we find that agenda parallelism and load balancing strategies contribute significantly more to better performance than improved communications or system tuning. Drawing general conclusions on how these inefficiencies may be overcome is inadvisable because of the tremendous variability of many parameters in general purpose network environments; we therefore propose several potential approaches, including model selection criteria, partitioning strategies, and software system heuristics, to reduce overheads and enhance performance in network based environments.
Solving an advection‐diffusion problem on the connection machine
Authors: Berggren Martin 
Published: November 2006

AbstractAn algorithm is presented that solves a linear advection‐diffusion problem using a least‐squares formulation and a conjugate gradient method to solve the corresponding minimization problem. An implementation in CM‐Fortran on a Thinking Machines CM‐2 is compared with a serial implementation on an IBM RS6000. The maximum speed‐up obtained is a factor of 70. For fine grids, the CPU time scales almost ideally when the number of processors is increased from 4096 to 8192.
High‐performance emulation of hierarchical structures on hypercube supercomputers
Authors: Ziavras Sotirios G. , Shah Devenkumar P. 
Published: November 2006

AbstractThe problem or emulating multilevel structures on hypercube supercomputers is studied in the paper. The frequently used pyramid belongs to the class of multilevel structures. Several algorithms have been published in the literature for the emulation of pyramids by hypercubes. The paper extends the most important of these algorithms to make them applicable for multilevel structures. Results for the Connection Machine system CM‐2 with 16,384 processors are presented and comparative analysis of the new algorithms is carried out. It is shown that very often higher performance can be obtained for multilevel structures other than the pyramid.
Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems
Authors: Barnard Stephen T. , Simon Horst D. 
Published: November 2006

AbstractIf problems involving unstructured meshes are to be solved efficiently on distributed‐memory parallel computers, the meshes must be partitioned and distributed across processors in a way that balances the computational load and minimizes communication. The recursive spectral bisection method (RSB) has been shown to be very effective for such partitioning problems compared to alternative methods, but RSB in its simplest form is expensive. Here a multilevel version of RSB is introduced that attains about an order‐of‐magnitude improvement in run time on typical examples.
SuperPascal—a publication language for parallel scientific computing
Authors: Hansen Per Brinch 
Published: November 2006

AbstractParallel computers will not become widely used until scientists and engineers adopt a common programming language for publication of parallel scientific algorithms. This paper describes the publication language SuperPascal by examples. SuperPascal extends Pascal with deterministic statements for parallel processes and synchronous message communication. The language permits unrestricted combinations of recursive procedures and parallel statements. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single‐pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables. A portable implementation of SuperPascal has been developed on a Sun workstation under Unix.
Parallel search for the interpretation of aerial images
Authors: Narayanan P. J. , Davis Larry S. 
Published: November 2006

AbstractIn this paper, we present a parallel search scheme for model‐based interpretation of aerial images, following a focus‐of‐attention paradigm. Interpretation is performed using the gray level image of an aerial scene and its segmentation into connected components of almost constant gray level. Candidate objects are generated from the window as connected combinations of its components. Each candidate is matched against the model by checking if the model constraints are satisfied by the parameters computed from the region. The problem of candidate generation and matching is posed as searching in the space of combinations of connected components in the image, with finding an (optimally) successful region as the goal. Our implementation exploits parallelism at multiple levels by parallelizing the management of the open list and other control tasks as well as the task of model matching. We discuss and present the implementation of the interpretation system on a Connection Machine CM‐2. The implementation reported a successful match in a few hundred milliseconds whenever they existed.