TY - JOUR
T1 - Algorithms for the parallel alternating direction access machine
AU - Chlebus, Bogdan S.
AU - Czumaj, Artur
AU - Ga̧sieniec, Leszek
AU - Kowaluk, Mirosław
AU - Plandowski, Wojciech
N1 - Funding Information:
(Work partially supported by EC Cooperative Action IC-1000 (project ALTEC: Algorithms for Future Technologies) and a research grant from Matsushita Electric Industrial Company Ltd. 1Work partially supported by DFG-Graduiertenkolleg \Parallele Rechnernetzwerke in der Produktion-stechnik", ME 872=4-1, by EU ESPRIT Long Term Research Project 20244 (ALCOM-IT), and by DFG Leibniz Grant Me872=6-1. E-mail addresses: chlebus@mimuw.edu.pl (B.S. Chlebus), Leszek@csc.liv.ac.uk (L. Gasieniec), kowaluk @mimuw.edu.pl (M. Kowaluk), wojtekpl@mimuw.edu.pl (W. Plandowski).
PY - 2000/8/28
Y1 - 2000/8/28
N2 - We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine (PADAM). 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.
AB - We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine (PADAM). 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.
KW - Algorithm
KW - Parallel computation
KW - Routing
KW - Simulation
UR - http://www.scopus.com/inward/record.url?scp=0347899652&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347899652&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(99)00280-7
DO - 10.1016/S0304-3975(99)00280-7
M3 - Article
AN - SCOPUS:0347899652
SN - 0304-3975
VL - 245
SP - 151
EP - 173
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -