TY - GEN
T1 - On parallel searching (extended abstract)
AU - Snir, Marc
N1 - Publisher Copyright:
© 1982 ACM.
PY - 1982/8/18
Y1 - 1982/8/18
N2 - We investigate the complexity of seaching by comparisons a table of n elements on a synchronous, shared memory parallel computer with p processors. We show that O(Ign) steps are required if concurrent access to the same memory celt Ks not allowed, whereas only O(Ign/Igp) steps are required if simultaneous reads are allowed. We next show that it is possible to search in O(Ig(n)/p) steps if more general operations are used.
AB - We investigate the complexity of seaching by comparisons a table of n elements on a synchronous, shared memory parallel computer with p processors. We show that O(Ign) steps are required if concurrent access to the same memory celt Ks not allowed, whereas only O(Ign/Igp) steps are required if simultaneous reads are allowed. We next show that it is possible to search in O(Ig(n)/p) steps if more general operations are used.
UR - http://www.scopus.com/inward/record.url?scp=85051389718&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85051389718&partnerID=8YFLogxK
U2 - 10.1145/800220.806703
DO - 10.1145/800220.806703
M3 - Conference contribution
AN - SCOPUS:85051389718
SN - 0897910818
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 242
EP - 253
BT - Proceedings of the 1st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 1982
PB - Association for Computing Machinery
T2 - 1st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 1982
Y2 - 18 August 1982 through 20 August 1982
ER -