Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functionsSimultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions

Access Restriction
Subscribed

 Author Reischuk, Rdiger Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The ability of the strongest parallel random access machine model WRAM is investigated. In this model different processors may simultaneously try to write into the same cell of the common memory. It has been shown that a parallel RAM without this option (PRAM), even with arbitrarily many processors, can almost never achieve sublogarithmic time. On the contrary, every function with a small domain like binary values in case of Boolean functions can be computed by a WRAM in constant time. The machine makes fast table look-ups using its simultaneous write ability. The main result of this paper implies that in general this is the “only way” to perform such fast computations and that a domain of small size is necessary. Otherwise simultaneous writes do not give an advantage. Functions with large domains for which any change of one of the $\textit{n}$ arguments also changes the result are considered, and a logarithmic lower time bound for WRAMs is proved. This bound can be achieved by machines that do not perform simultaneous writes. A simple example of such a function is the sum of $\textit{n}$ natural numbers. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 1 Page Count 16 Starting Page 163 Ending Page 178

Open content in new tab

Source: ACM Digital Library