Parallel Implementation of Relational Algebra Operations on a Multi-Comparand Associative Machine

Authors

  • Anna Shmilevna Nepomniaschaya

Keywords:

SIMD architecture, data parallelism, operation of the exact match, associative parallel processor, bit-serial processing, bit-parallel processing, associative parallel algorithm

Abstract

In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to implement one group of the relational algebra operations on the MCA-machine. Then, we propose efficient associative algorithms for implementing another group of the relational algebra operations. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity.

Downloads

Download data is not yet available.

Author Biography

Anna Shmilevna Nepomniaschaya

Institute of Computational Mathematics and Mathematical Geophysics
Siberian Division of the Russian Academy of Sciences
pr. Lavrentieva 6
630090 Novosibirsk, Russia

Downloads

Published

2012-01-26

How to Cite

Nepomniaschaya, A. S. (2012). Parallel Implementation of Relational Algebra Operations on a Multi-Comparand Associative Machine. Computing and Informatics, 29(3), 467–487. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/94