Parallel Computing

article

Parallel implementation of a VARMAX algorithm -- Practical aspects and experiences

Ralf Östermark, Martin Saarinen

Parallel Computing > 1994 > 1994 > 3 > 7

In the paper we test the efficiency and speedup achieved by parallel computation of the main computational block of a VARMAX-Search algorithm, as compared to the time absorbance of a standard sequential algorithm. The VARMAX-search algorithm is an extension of a fast estimation algorithm, originally presented by Spliid [10]. Whereas the original algorithm assumed that the model orders where known...

article

Parallel recombinative simulated annealing: A genetic algorithm

Samir W. Mahfoud, David E. Goldberg

Parallel Computing > 1994 > 1994 > 3 > 15-16

This paper introduces and analyzes a parallel method of simulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, calledparallel recombinative simulated annealing , is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and...

article

Transposition of banded matrices in hypercubes: A nearly isotropic task

Emmanouel A. Varvarigos, Dimitri P. Bertsekas

Parallel Computing > 1994 > 1994 > 3 > 6-7

A class of communication tasks, called isotropic, was introduced in [15], and minimum completion time algorithms for all tasks in this class were found. Isotropic tasks are characterized by a type of symmetry with respect to origin node. In this paper we consider the problem of transposing a sparse matrix of size N N with a diagonal band of size 2 ^β ⁺ ¹ + 1, which is stored by columns...

article

Parallel load-balancing: An extension to the gradient model

F.J. Muniz, E.J. Zaluska

Parallel Computing > 1994 > 1994 > 3 > 13

This paper describes the design and the implementation of an effective and scalable dynamic load-balancing mechanism suitable for a loosely-coupled MIMD system with a interconnected topology. The proposed algorithm extends the well-known gradient model to improve the overall execution time. A prototype system has been implemented using a network of transputer processors. A load generator spawns...

article

Parallel FFT algorithms using radix 4 butterfly computation on an eight-neighbor processor array

Kuninobu Tanno, Toshihiro Taketa, Susumu Horiguchi

Parallel Computing > 1994 > 1994 > 3 > 8

Fast Fourier transform (FFT), which has wide and variety application areas, requires very high speed computation. Since parallel processing of FFT is very attractive for high speed FFT computation, many processor arrays and multiprocessor systems have been proposed with efficient FFT algorithms. As a result of the recent development of VLSI technology, several massively parallel computers have been...

article

An improved spectral bisection algorithm and its application to dynamic load balancing

R. Van Driessche, D. Roose

Parallel Computing > 1994 > 1994 > 3 > 9

The efficient parallel execution of grid-oriented scientific calculations requires a partitioning of the grid that minimises both load imbalance and interprocessor communication. For unstructured static grids, good partitions are obtained with the recursive spectral bisection heuristic, applied to the interdependency graph of the grid. We will describe an alternative spectral bisection algorithm...

article

An assessment of assignment schemes for dependency graphs

Sathiamoorthy Manoharan, Nigel P. Topham

Parallel Computing > 1994 > 1994 > 3 > 13

The recent past has seen a number of publications proposing assignment schemes that do not ignore communication costs. Yet, little effort has been made to comparatively assess the performance and end-results of these schemes. This paper presents a comparative assessment of assignment schemes for dependency graphs that take into account the communication costs.To generate an assignment, some parameters...

article

An efficient permutation-based parallel algorithm for range-join in hypercubes

Hong Shen

Parallel Computing > 1994 > 1994 > 3 > 14-15

The range-join of sets R and S is defined to be the set containing all tuples (r, s) that satisfy e ₁ ≤ r-s ≤e ₂ where r R, s S, e ₁ and e ₂ are fixed constants. This paper proposes an efficient parallel range-join algorithm in hypercubes. To compute the range-join of two sets R and S on a hypercube of p processors (p≤ R =m≤ S =n), the proposed...

article

Fast parallel algorithms for the maximum sum problem

Zhaofang Wen

Parallel Computing > 1994 > 1994 > 3 > 11

A problem in pattern recognition is to find the maximum sum over all rectangular subregions of a given (n n) matrix of real numbers. The problem has one-dimensional (1D) and two-dimensional (2D) versions. For the 1D version, it is to find the maximum sum over all contiguous subvector of a given vector of n real numbers. We give an algorithm for the 1D version running in O(log n) time using O((n)/(log...

article

Speed-up of scalable iterative linear solvers implemented on an array of transputers

A. Asenov, D. Reid, J.R. Barker

Parallel Computing > 1994 > 1994 > 3 > 12

A detailed model is presented for the speed-up of parallel linear iterative solvers. The mapping of a topologically rectangular discrete grid onto a processor array of N M transputers leads to step-like behaviour in the local communication and calculation time. This results in a typical oscillatory behaviour of speed-up when problem sizes are increased monotonously. The theory is compared...

article

Parallel routing algorithms for incomplete hypercube interconnection networks

M.S. Horng, D.J. Chen, Kuo-Lung Ku

Parallel Computing > 1994 > 1994 > 3 > 10

Hypercube interconnection networks have been receiving considerable attention in the supercomputing environment. However, the number of processors must be exactly 2 ^r for an r-cube complete hypercube. This restriction severely limits its applicability. In this paper, we address three variant hypercube topologies with more flexibility in system sizes, the labelled hypercubes l _m ...

article

A binary tree implementation of a parallel distributed tridiagonal solver

Juan C. Agüí, Javier Jiménez

Parallel Computing > 1994 > 1994 > 3 > 17

A divide-and-conquer algorithm for the resolution of distributed linear tridiagonal systems of equations is implemented within a binary tree connection architecture. A new scheme for the distribution of the data among the computing nodes allows a dilation-one implementation of a recursive substitution scheme for the solution of the global system. In this way, computation time decreases linearly...

article

An effective routing algorithm in incomplete hypercubes

Shu-Hua Hu, Hsing-Lung Chen

Parallel Computing > 1994 > 1994 > 3 > 9-10

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple...

article

Running air pollution models on the connection machine

Zahari Zlatev, Jerzy Wasniewski

Parallel Computing > 1994 > 1994 > 3 > 5

The concentrations of air pollutants have in general been steadily increasing during the last three decades. Therefore there is an increasing need to control the air pollution: air pollution should be reduced to acceptable levels and/or kept under these levels in order to prevent damage to, and even destructions of ecosystems. However, the reduction of air pollution is an expensive process. This...

article

Controlling correlations in parallel Monte Carlo

A. De Matteis, S. Pagnutti

Parallel Computing > 1994 > 1994 > 3 > 17

Effects and detection of correlations in parallel Monte Carlo are discussed, on the assumption that each processor uses a sequence of truly random numbers, but the sequences are mutually correlated. Depending on the parallel implementation of the algorithm, effects may concern the mean value of the solution or only its variance. In the first case an alternative implementation of the algorithm is...

article

A general purpose subroutine for Fast Fourier Transform on a distributed memory parallel machine

A. Dubey, M. Zubair, C.E. Grosch

Parallel Computing > 1994 > 1994 > 3 > 11

One issue which is central in developing a general purpose FFT subroutine on a distributed memory parallel machine is the data distribution. It is possible that different users would like to use the FFT routine with different data distributions. Thus there is a need to design FFT schemes on distributed memory parallel machines which can support a variety of data distributions. In this paper we...

article

A parallel implementation of the column subtraction algorithm

T.H.C. Smith, G.L. Thompson

Parallel Computing > 1994 > 1994 > 3 > 16

We have implemented Harche and Thompson's column subtraction algorithm for the set partitioning problem on a CM-200 Connection Machine. The implementation involved partitioning the large array of processors in the CM-2 into segments and letting each segment explore a different part of the search tree generated by the column subtraction algorithm. Our reported computational results indicate that...

article

Parallel image processing applications on a network of workstations

Chi-kin Lee, Mounir Hamdi

Parallel Computing > 1994 > 1994 > 3 > 14

Concurrent computing on networks of distributed computers has gained tremendous attention and popularity in recent years. In this paper, we use this computing environment for the development of efficient parallel image convolution applications for grey-level images and binary images. Significant speedup was achieved using different image sizes, kernel sizes, and number of workstations. We also present...

article

Use of linear algebra kernels to build an efficient finite element solver

Howard C. Elman, Dennis K.-Y. Lee

Parallel Computing > 1994 > 1994 > 3 > 6

For scientific codes to achieve good performance on computer with hierarchical memories, it is necessary that the ratio of memory references to arithmetic operations be low. In this paper, we show that Level 3 BLAS linear algebra kernels can be used to satisfy this requirement to produce an efficient implementation of a parallel finite element solver on a shared memory parallel computer with a fast...

article

Systolic algorithms for digital image filtering

D.J. Evans, S.A. Amin

Parallel Computing > 1994 > 1994 > 3 > 12

Many low-level image processing operations, termed local operators, require access to the four or eight neighbouring intensity values of a pixel, when computing the new value for the pixel and need large amounts of computing, i.e. banded matrix operations. However, these algorithms contain explicit parallelism which can be efficiently exploited by processor arrays. The purpose of this paper is to...

INFONA - science communication portal

Parallel Computing

Parallel implementation of a VARMAX algorithm -- Practical aspects and experiences

Parallel recombinative simulated annealing: A genetic algorithm

Transposition of banded matrices in hypercubes: A nearly isotropic task

Parallel load-balancing: An extension to the gradient model

Parallel FFT algorithms using radix 4 butterfly computation on an eight-neighbor processor array

An improved spectral bisection algorithm and its application to dynamic load balancing

An assessment of assignment schemes for dependency graphs

An efficient permutation-based parallel algorithm for range-join in hypercubes

Fast parallel algorithms for the maximum sum problem

Speed-up of scalable iterative linear solvers implemented on an array of transputers

Parallel routing algorithms for incomplete hypercube interconnection networks

A binary tree implementation of a parallel distributed tridiagonal solver

An effective routing algorithm in incomplete hypercubes

Running air pollution models on the connection machine

Controlling correlations in parallel Monte Carlo

A general purpose subroutine for Fast Fourier Transform on a distributed memory parallel machine

A parallel implementation of the column subtraction algorithm

Parallel image processing applications on a network of workstations

Use of linear algebra kernels to build an efficient finite element solver

Systolic algorithms for digital image filtering

Filter options

Publication date

Year

Content availability

Keywords

INFONA - science communication portal

Parallel Computing

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Year

Content availability

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options