The queue-read queue-write asynchronous PRAM model.

*(English)*Zbl 0902.68073Summary: This paper presents results for the queue-read, queue-write asynchronous parallel random access machine (QRQW ASYNCHRONOUS PARM) model, which is the asynchronous variant of the QRQW PRAM model. The QRQW PRAM family of models, which was introduced earlier by the authors, permit concurrent reading and writing to shared memory locations, but each memory location is viewed as having a queue which can service at most one request at a time. In the basic QRQW PRAM model each processor executes a series of reads to shared memory locations, a series of local computation steps, and a series of writes to shared memory locations, and then synchronizes with all other processors; thus this can be viewed as a bulk-synchronous model. In contrast, in the QRQW ASYNCHRONOUS PRAM model discussed in this paper, there is no imposed bulk-synchronization between processors, and each processor proceeds at its own pace. Thus, the QRQW ASYNCHRONOUS PRAM serves as a better model for designing and analyzing truly asynchronous parallel algorithms than the original QRQW PRAM. In this paper we elaborate on the QRQW ASYNCHRONOUS PRAM model, and we demonstrate the power of asynchrony over bulk-synchrony by presenting a work and time optimal deterministic algorithm on the QRQW ASYNCHRONOUS PRAM for the leader election problem and a simple randomized work and time optimal algorithm on the QRQW ASYNCHRONOUS PRAM for sorting. In contrast, no tight bounds are known on the QRQW PRAM for either deterministic or randomized parallel algorithms for leader election and the only work and time optimal algorithms for sorting known on the QRQW PRAM are those inherited from the EREW PRAM, which are considerably more complicated. Our sorting algorithm is an asynchronous version of an earlier sorting algorithm we developed for the QRQW PRAM, for which we use an interesting analysis to bound the running time to be \(O(\log n)\). We also present a randomized algorithm to simulate one step of a CRCW PRAM on a QRQW ASYNCHRONOUS PRAM in sublogarithmic time if the maximum contention in the step is relatively small.

##### MSC:

68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |

PDF
BibTeX
XML
Cite

\textit{P. B. Gibbons} et al., Theor. Comput. Sci. 196, No. 1--2, 3--29 (1998; Zbl 0902.68073)

Full Text:
DOI

##### References:

[1] | Adler, M., Asynchronous shared memory search structures, (), 42-51 · Zbl 0904.68027 |

[2] | Afek, Y.; Brown, G.M.; Merritt, M., Lazy caching, ACM trans. programming languages and systems, 15, 1, 182-205, (1993) |

[3] | Ajtai, M.; Komlos, J.; Szemeredi, E., Sorting in clogn parallel steps, Combinatorica, 3, 1, 1-19, (1983) · Zbl 0523.68048 |

[4] | Anderson, R.J., Primitives for asynchronous List compression, (), 199-208 · Zbl 0812.68066 |

[5] | Armen, C.; Johnson, D.B., Deterministic leader election on the asynchronous QRQW PRAM, Parallel process. lett., (1996), to appear. |

[6] | Aumann, Y.; Rabin, M.O., Clock construction in fully asynchronous parallel systems and PRAM simulation, (), 147-156 · Zbl 0977.68877 |

[7] | Batcher, K.E., Sorting networks and their applications, (), 307-314 · Zbl 0142.12903 |

[8] | Beame, P.; Håstad, J., Optimal bounds for decision problems on the CRCW PRAM, J. ACM, 36, 3, 643-670, (1989) · Zbl 0825.68378 |

[9] | Blelloch, G.E.; Gibbons, P.B.; Matias, Y.; Zagha, M., Accounting for memory bank contention and delay in high-bandwidth multiprocessors, (), 84-94 |

[10] | Cole, R., Parallel merge sort, SIAM J. comput., 17, 4, 770-785, (1988) · Zbl 0651.68077 |

[11] | Cole, R.; Zajicek, O., The APRAM: incorporating asynchrony into the PRAM model, (), 169-178 |

[12] | Cole, R.; Zajicek, O., The expected advantage of asynchrony, (), 85-94 · Zbl 0831.68047 |

[13] | Culler, D.; Karp, R.; Patterson, D.; Sahay, A.; Schauser, K.E.; Santos, E.; Subramonian, R.; von Eicken, T., Logp: towards a realistic model of parallel computation, (), 1-12 |

[14] | Dietzfelbinger, M.; Kutylowski, M.; Reischuk, R., Exact lower time bounds for computing Boolean functions on CREW prams, J. comput. system sci., 48, 2, 231-254, (1994) · Zbl 0822.68049 |

[15] | Dwork, C.; Herlihy, M.; Waarts, O., Contention in shared memory algorithms, (), 174-183 · Zbl 1310.68222 |

[16] | Gharachorloo, K.; Lenoski, D.; Laudon, J.; Gibbons, P.; Gupta, A.; Hennessy, J., Memory consistency and event ordering in scalable shared-memory multiprocessors, (), 15-26 |

[17] | Gibbons, P.B.; Gibbons, P.B., The asynchronous PRAM: a semi-synchronous model for shared memory MIMD machines, (), 158-168, Full version in |

[18] | Gibbons, P.B.; Merritt, M., Specifying nonblocking shared memories, (), 306-315 |

[19] | Gibbons, P.B.; Merritt, M.; Gharachorloo, K., Proving sequential consistency of high-performance shared memories, (), 292-303 |

[20] | Gibbons, P.B.; Matias, Y.; Ramachandran, V., QRQW: accounting for concurrency in PRAMs and asynchronous prams, () |

[21] | Gibbons, P.B.; Matias, Y.; Ramachandran, V., Efficient low-contention parallel algorithms, J. comput. system sci., 53, 3, 417-442, (1996) · Zbl 0870.68083 |

[22] | Special issue devoted to selected papers from the 1994 ACM Symp. on Parallel Algorithms and Architectures. |

[23] | Gibbons, P.B.; Matias, Y.; Ramachandran, V.; Gibbons, P.B.; Matias, Y.; Ramachandran, V., The queue-Read queue-write PRAM model: accounting for contention in parallel algorithms, (), 638-648, (1997), Preliminary version appears in · Zbl 0902.68073 |

[24] | Gottlieb, A.; Grishman, R.; Kruskal, C.P.; McAuliffe, K.P.; Rudolph, L.; Snir, M., The NYU ultracomputer — designing an MIMD shared memory parallel computer, IEEE trans. comput., C-32, 2, 175-189, (1983) |

[25] | JáJá, J., An introduction to parallel algorithms, (1992), AddisondashWesley Reading, MA · Zbl 0781.68009 |

[26] | Karp, R.M.; Ramachandran, V., Parallel algorithms for shared-memory machines, (), 869-941 · Zbl 0900.68267 |

[27] | Lamport, L., How to make a multiprocessor computer that correctly executes multiprocess programs, IEEE trans. comput., C-28, 9, 690-691, (1979) · Zbl 0419.68045 |

[28] | Liu, P.; Aiello, W.; Bhatt, S., An atomic model for message-passing, (), 154-163 |

[29] | Martel, C.; Park, A.; Subramonian, R., Work-optimal asynchronous algorithms for shared memory parallel computers, SIAM J. comput., 21, 6, 1070-1099, (1992) · Zbl 0759.68028 |

[30] | Nishimura, N., Asynchronous shared memory parallel computation, (), 76-84 |

[31] | () |

[32] | Reischuk, R., Probabilistic parallel algorithms for sorting and selection, SIAM J. comput., 14, 2, 396-409, (1985) · Zbl 0578.68040 |

[33] | Smith, B., Invited lecture, () |

[34] | Vishkin, U., On choice of a model of parallel computation, () |

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.