A design of a parallel dictionary using skip lists. (English) Zbl 0871.68066

Gabarró, Joaquim; Martínez, Conrado; Messeguer, Xavier

Theor. Comput. Sci. 158, No. 1-2, 1-33 (1996).

Summary: We present a top-down design of a parallel PRAM dictionary using skip lists. More precisely, we give detailed algorithms to search for, insert or delete \(k\) elements in a skip list of \(n\) elements in parallel. The algorithms are iterative and easy to implement on real machines. We discuss some implementation issues and give concrete examples in \(C^{\ast}\). The algorithms run on an EREW PRAM in expected time \(O(\log n+\log k)\) using \(k\) processors. We also show an explicit protocol to avoid read conflicts thus obtaining an efficient EREW version of our algorithms.
Although the asymptotic performance of the parallel skip list algorithms is not better compared to that of other parallel dictionaries, they are a practical alternative. Skip list algorithms are very simple and there is a small probability of large deviations from their expected performance.

MSC:

68P10	Searching and sorting
68W10	Parallel algorithms in computer science

References:

[1]	Atallah, M. J.; Kosaraju, S. Rao, A generalized dictionary machine for VLSI, IEEE Trans. Comput., C-34, 2, 151-155 (1985) · Zbl 0555.68011
[2]	Bast, H.; Dietzfelbinger, M.; Hagerup, T., A perfect parallel dictionary, (Havel, I. M.; Koubek, V., Proc. 17th Math. Foundations Comput. Sci.. Proc. 17th Math. Foundations Comput. Sci., Lecture Notes in Computer Science, Vol. 598 (1992), Springer: Springer Berlin), 133-141 · Zbl 1493.68134
[3]	Blelloch, G. E., Scans as primitive parallel operations, IEEE Trans. Comput., 38, 11, 1526-1538 (1989)
[4]	Bougé, L.; Guyadec, Y. Le; Ultard, G.; Virot, B., A proof system for a simple data-parallel programming language, (Girault, C., Proc. IFIP WG10.3 Internat. Conf. on Appl. in Parallel and Distributed Computing (1994), Elsevier: Elsevier Amsterdam)
[5]	Chernoff, H., A measure of asymptotic efficiency for tests of hypothesis based on sum of observations, Ann. Math. Statist., 23, 493-507 (1952) · Zbl 0048.11804
[6]	Devroye, L., A limit theory for random skip lists, Ann. Appl. Probab., 2, 3, 597-609 (1992) · Zbl 0754.68039
[7]	Dietzfelbinger, M.; der Heide, F. Meyer aur, (Proc. 17th ICALP. Proc. 17th ICALP, Lecture Notes in Computer Science, Vol. 443 (1990), Springer: Springer Berlin) · Zbl 0765.68026
[8]	Dietzfelbinger, M.; der Heide, F. Meyer auf, An optimal parallel dictionary, Inform. Control., 102, 2, 196-217 (1993) · Zbl 0786.68023
[9]	Duboux, T.; Ferreira, A.; Gastado, M., MIMD dictionary machines: from theory to practice, (Bougé, L.; Cosnard, M.; Robert, Y.; Trystram, D., Proc. 2nd Joint Internat. Conf. on Vector and Parallel Processing (CONPAR92-VAPPV). Proc. 2nd Joint Internat. Conf. on Vector and Parallel Processing (CONPAR92-VAPPV), Lecture Notes in Computer Science, Vol. 634 (1992), Springer: Springer Berlin), 545-550
[10]	Gabarró, J.; Gavaldà, R., An approach to correctness of data parallel algorithms, J. Parallel and Distributed Computing, 22, 185-201 (1994)
[11]	Gabarró, J.; Martínez, C.; Messeguer, X., Parallel update and search in skip lists, (Baeza-Yates, R., Computer Science 2: Research and Applications (1994), Plenum: Plenum New York), 15-26
[12]	Gastaldo, M., Dictionary machine on SIMD archictectures, (Tech. Report. 93-19 (1993), Laboratoire de l’Informatique du Parallélisme (LIP))
[13]	Gil, J.; Matias, Y.; Vishkin, U., Towards a theory of nearly constant time parallel algorithms, (Proc. 32nd Foundations of Comput. Sci. (1991)), 698-710
[14]	Higham, L.; Schenk, E., Maintaining B-trees on an EREW PRAM, J. Parallel and Distributed Computing, 22, 329-335 (1994) · Zbl 0939.68599
[15]	Hillis, W. D.; Steele, G. L., Data parallel algorithms, Comm. ACM, 29, 12, 1170-1183 (1986)
[16]	Kirschenhofer, P.; Martínez, C.; Prodinger, H., Analysis of an optimized search algorithm for skip lists, Theoret. Comput. Sci., 144, 199-220 (1995) · Zbl 0874.68082
[17]	Kirschenhofer, P.; Prodinger, H., The path length of random skip lists, Acta Inform., 31, 8, 775-792 (1994)
[18]	Leiserson, C. E., Area-efficient VLSI computation, (Ph.D. Thesis, Carnegie-Mellon University, 1981 (1983), MIT Press), ACM Doctoral Dissertation Award 1982
[19]	Messeguer, X., A sequential and parallel implementation of skip lists, Tech. Report LSI-94-41-R, LSI-UPC (1994)
[20]	Papadakis, T., Skip lists and probabilistic analysis of algorithms, (Ph.D. Thesis (1993), University of Waterloo), available as Tech. Report CS-93-28
[21]	Papadakis, T.; Munro, J. I.; Poblete, P. V., Analysis of the expected search cost in skip lists, (Gilbert, J. R.; Karlsson, R., Proc. 2nd Scandinavian Workshop on Algorithm Theory. Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 447 (1990), Springer: Springer Berlin), 160-172 · Zbl 1502.68102
[22]	Paul, W.; Vishkin, U.; Wagener, H., Parallel computation on 2-3 trees, (Díaz, J., Proc. 10th Internat. Colloquium on Automata, Programming and Languages. Proc. 10th Internat. Colloquium on Automata, Programming and Languages, Lecture Notes in Computer Science, Vol. 154 (1983), Springer: Springer Berlin), 597-609 · Zbl 0531.68017
[23]	Paul, W.; Vishkin, U.; Wagener, H., Parallel computation on 2-3 trees, RAIRO Inform. Théor., 398-404 (1983) · Zbl 0531.68017
[24]	Pugh, W., A skip list cookbook, (Tech. Report CS-TR-2286.1 (1990), Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland: Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland College Park, MD), also published as UMIACS-TR-89-72.1
[25]	Pugh, W., Skip lists: a probabilistic alternative to balanced trees, Comm. ACM, 33, 6, 668-676 (1990)
[26]	Schwartz, J. T., Ultracomputers, ACM Trans. Programming Languages Sys., 2, 4, 484-521 (1980) · Zbl 0468.68027
[27]	Sen, S., Some observations on skip-lists, Inform. Process Lett., 39, 3, 173-176 (1991) · Zbl 0735.68018