Algorithms for the parallel alternating direction access machine

This paper describes a number of algorithms for the model for parallel computation called Parallel Alternating-Direction Access Machine (PADAM). The model has the memory modules of the global memory arranged as a 2-dimensional array, with each processor assigned to a row and a column. The processors can switch synchronously between row and column access modes. The PADAM is an abstraction of the parallel machines ADENART and USC/OMP originally designed for scientific and numeric applications. The previous work on this model was concerned with special-purpose applications. The algorithms presented in this paper have been developed as part of a study of the efficiency issues occurring naturally when PADAM is to be used as a general-purpose computer. The problems of inter-processor communication and of efficient use of memory are critical for designing algorithms on the PADAM, therefore we concentrate our study on these issues. We present an optimal routing scheme among memory modules. Next we develop algorithms for access of processors to all the memory blocks. Then we present general simulations of shared memory. Finally we present optimal algorithms for the following selected combinatorial problems: selection, merging, and sorting. (orig.)Available from TIB Hannover: RR 6673(53) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman