Design, implementation and evaluation of ParaDict, a data parallel library for dictionaries
Joaquim Gabarró, Jordi Petit · 1997
ParaDict, a data parallel library for dictionaries having two di#erent interfaces is presented. The first interface is written in C* for data parallel users and the second interface in C, for users that want to use a parallel library but are not willing to write parallel programs. An inneficient prototype implementation (using associative memories) and an e#cient implementation (using 2-3 trees) are presented. We have seen that C* is an adequate tool to code theoretical PRAM algorithms into readable programs. These programs were ran on a CM 200 with better times than other existing implementations. Morover, they also have much better asymptotic behaviour when compared to a sequential implementation on a workstation. Finally, the relationship between data parallelism and vectorization is explored, transforming C* code into C code plus compiler directives and running the result on a Convex C3480 machine. Keywords: Parallel libraries, dictionaries, 2--3 trees, data parallelism, design im...