×

zbMATH — the first resource for mathematics

Algorithms for the parallel alternating direction access machine. (English) Zbl 0946.68047
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.
MSC:
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W05 Nonnumerical algorithms
68U20 Simulation (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Aggarwal, A.K. Chandra, M. Snir, On communication latency in PRAM computations, in: Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989, pp. 11-21.
[2] Blum, M.; Floyd, R.W.; Pratt, V.R.; Rivest, R.L.; Tarjan, R.E., Time bounds for selection, J. comput. system sci., 7, 448-461, (1972) · Zbl 0278.68033
[3] B.S. Chlebus, A. Czumaj, L. Ga̧sieniec, M. Kowaluk, W. Plandowski, Parallel alternating-direction access machine, in: Proc. 21st Internat. Symp. on Mathematical Foundations of Computer Science, 1996, Lecture Notes in Computer Science, Vol. 1113, pp. 267-278.
[4] B.S. Chlebus, A. Czumaj, J.F. Sibeyn, Routing on the PADAM: degrees of optimality, in: Proc. Euro-Par’97 Parallel Processing, 1997, Lecture Notes in Computer Science, Vol. 1300, pp. 272-279. · Zbl 0996.68652
[5] M. Dietzfelbinger, F. Meyer auf der Heide, Dynamic hashing in real time, in: J. Buchmann, H. Ganzinger, W.J. Paul (Eds.), Informatik: Festschrift zum 60. Geburtstag von Günter Hotz, B.G. Teuber Verlagsgesellschaft, Leipzig, 1992, pp. 95-119. A preliminary version appeared as: M. Dietzfelbinger, F. Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, in: Proc. 17th Internat. Colloq. on Automata, Languages and Programming, 1990, pp. 6-19.
[6] Hwang, K., Advanced computer architectureparallelism, scalability, programmability, (1993), McGraw-Hill New York
[7] Hwang, K.; Cheng, C.-M., Simulated performance of a RISC-based multi-processor using orthogonal-access memory, J. parallel distrib. comput., 13, 43-57, (1991)
[8] K. Hwang, M. Dubois, D.K. Panda, S. Rao, S. Shang, A. Uresin, W. Mao, H. Nair, M. Lytwyn, F. Hsieh, J. Liu, S. Mehrotra, C.M. Cheng, OMP: a RISC-based multiprocessor using orthogonal-access memories and multiple spanning buses, in: Proc. 1990 Internat. Conf. on Supercomputing, 1990, pp. 7-22. ACM SIGARCH Computer Architecture News 18 (3) (1990) 7-22.
[9] Hwang, K.; Tseng, P.-S.; Kim, D., On orthogonal multiprocessor for parallel scientific computations, IEEE trans. comput., 38, 47-61, (1989) · Zbl 0665.68002
[10] JáJá, J., An introduction to parallel algorithms, (1992), Addison-Wesley Reading, MA · Zbl 0781.68009
[11] H. Kadota, K. Kaneko, I. Okabayashi, T. Okamoto, T. Mimura, Y. Nakakura, A. Wakatani, M. Nakajima, J. Nishikawa, K. Zaiki, T. Nogi, Parallel computer ADENART — its architecture and application, in: Proc. Fifth ACM Internat. Conf. on Supercomputing, 1991, pp. 1-8.
[12] H. Kadota, K. Kaneko, Y. Tanikawa, T. Nogi, VLSI parallel computer with data transfer network: ADENA, in: Proc. Internat. Conf. on Parallel Processing, Vol. I, 1989, pp. 319-322.
[13] Karp, R.M.; Ramachandran, V., Parallel algorithms for shared-memory machines, (), 870-941 · Zbl 0900.68267
[14] Kruskal, C.P.; Rudolph, L.; Snir, M., A complexity theory of efficient parallel algorithms, Theoret. comput. sci., 71, 95-132, (1990) · Zbl 0699.68069
[15] Leighton, F.T., Introduction to parallel algorithms and architecturesarrays, trees, hypercubes, (1991), Morgan Kaufman Publishers San Mateo, California
[16] T. Leighton, Methods for message routing in parallel machines, in: Proc. 24th ACM Symp. on Theory of Computing, 1992, pp. 77-96.
[17] T. Leighton, F. Makedon, Y. Tollis, A \(2n−2\) step algorithm for routing in an \(n× n\) array with constant size queues, in: Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989, pp. 328-335. · Zbl 0833.68058
[18] T. Leighton, C.G. Plaxton, A (fairly) simple circuit that (usually) sorts, in: Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 264-274.
[19] Mehlhorn, K.; Vishkin, U., Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta inform., 21, 339-374, (1984) · Zbl 0548.68044
[20] F. Meyer auf der Heide, Hashing strategies for simulating shared memory on distributed memory machines, in: F. Meyer auf der Heide, B. Monien, A.L. Rosenberg (Eds.), Proc. First Heinz Nixdorf Symposium Parallel Architectures and their Efficient Use, Lecture Notes on Computer Science, Vol. 678, 1992, pp. 20-29.
[21] Nogi, T., Parallel computation on ADENA, ()
[22] T. Nogi, T. Imamura, K. Sakai, Y. Obayashi, NAS parallel benchmark results on ADENART, Parallel CFD’94, Kyoto, 1994. · Zbl 0850.76539
[23] S. Rajasekaran, Mesh connected computers with fixed and reconfigurable buses: packet routing, sorting and selection, in: Proc. European Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 726, 1993, pp. 309-320.
[24] S. Saini, D.H. Bailey, NAS parallel benchmark results 12-95, Technical Report NAS-95-021, NASA Ames Research Center, Moffett Field, CA 94035-1000, 1995. This report is available electronically at http://www.nax.nasa.gov/NAS/TechReports/NASreports/NAS-95-021/NAS-95-021.htm.
[25] Sherson, I.D.; Ma, Y., Analysis and applications of the orthogonal access multiprocessor, J. parallel distrib. comput., 7, 232-255, (1989)
[26] Sibeyn, J.F.; Chlebus, B.S.; Kaufmann, M., Deterministic permutation routing on meshes, J. algorithms, 22, 111-141, (1997) · Zbl 0872.68062
[27] J.F. Sibeyn, M. Kaufmann, R. Raman, Randomized routing on meshes with buses, in: Proc. European Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 726, 1993, pp. 333-344.
[28] Stout, Q., Mesh connected computers with broadcasting, IEEE trans. comput., 32, 826-830, (1983) · Zbl 0525.68030
[29] Valiant, L.G., General purpose parallel architectures, (), 943-972 · Zbl 0900.68257
[30] A.J. van der Steen, J.J. Dongarra, Overview of Recent Supercomputres, NHSA Review, 1996 Volume, 1st issue, 1996. This report is available electronically at http://www.crpc.rice.edu/NHSEreview/ORS/.
[31] R.A. Wagner, Y. Han, Parallel algorithms for bucket sorting and the data dependent prefix problem, in: Proc. 15th Internat. Conf. on Parallel Processing, 1986, pp. 924-930.
[32] A.C. Yao, Probabilistic computations: towards a unified measure of complexity, in: Proc 18th Annual Symp. on Foundations of Computer Science, 1977, pp. 222-227.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.