Algorithms for the parallel alternating direction access machine
type: Item
instance of: scholarly article
title: Algorithms for the parallel alternating direction access machine
zbMATH Open document ID: 0946.68047
DOI: 10.1016/S0304-3975(99)00280-7
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
review text: We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine. This model has the memory modules of the global memory arranged as a two-dimensional array, with each processor assigned to a row and a column, the processors can switch synchronously between row and column access modes. We study the issues of inter-processor communication and of efficient use of memory on the padam, and develop: an optimal routing scheme among memory modules, algorithms enhancing random access of processors to all memory blocks, and general simulations of shared memory machines. Finally, we present optimal algorithms for the problems of selection, merging, and sorting.
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68U20
zbMATH DE Number: 1493510
zbMATH Keywords: algorithm
zbMATH Keywords: parallel computation
zbMATH Keywords: routing
zbMATH Keywords: simulation
zbMATH Keywords: parallel alternating-direction access machine
author: Bogdan S. Chlebus
author: Artur Czumaj
author: Leszek Gąsieniec
author: Mirosław Kowaluk
author: Wojciech Plandowski
describes a project that uses: NAS Parallel Benchmarks
MaRDI profile type: Publication
cites work: Time bounds for selection
cites work: Q4536939
cites work: An orthogonal multiprocessor for parallel scientific computations
cites work: Q4023519
cites work: Q4385522
cites work: A complexity theory of efficient parallel algorithms
cites work: A \(2n-2\) step algorithm for routing in an \(n \times n\) array with constant-size queues
cites work: Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
cites work: Q4892116
cites work: Deterministic Permutation Routing on Meshes
cites work: Mesh-Connected Computers with Broadcasting
cites work: Q4385523
full work available at URL: s0304-3975(99)00280-7
OpenAlex ID: W2056181277
description: scientific article; zbMATH DE number 1493510