Abstract data types for SIMD hypercube machines

The authors investigate an efficient implementation of abstract data types on single-instruction multiple-data (SIMD) hypercube machines. Methods of merging distributed clients and servers to allow efficient parallel operations are presented. In particular, parallel primitives are proposed as well as normalized representation schemas for efficiently implementing various abstract data types. Since the performance of an abstract data type component can vary considerably depending on the placement of its data elements on the physical processors, mapping strategies to reduce communication costs are discussed. These abstract components can serve as building blocks for implementing other parallel components, such as parsers, constraint resolvers, and pattern recognizers