Multi-Comparand Associative Machine and its Application to Relational Algebra Operations

A.S. Nepomniaschaya

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 a group of the relational algebra operations on the MCA-machine. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity.

Problems in programming 2010; 2-3: 185-192


Full Text:

PDF

References


Falkoff A.D. Algorithms for parallel-search memories // J. of the ACM. – 1962. – 9. Р. 448–510.

Fernstrom C., Kruzela J., Svensson B. LUCAS Associative Array Processor. Design, Programming and Application Studies, Lecture Notes in Computer Science. – Berlin; Springer-Verlag, 1986. – 216 р.

Foster C.C. Content Addressable Parallel Processors, Van Nostrand Reinhold Company, New York, 1976.

Irakliotis L.J., Betzos G.A., Mitkas P.A. Optical associative processing, in: A. Krikelis, C.C. Weems (Eds.) // Associative Processing and Processors, IEEE Computer Society – 1997. – Р. 155–178.

Kapralski A. Sequential and Parallel Processing in Depth Search Machines – Singapore; World Scientific, 1994.

Kokosinski Z. An associative processor for multi-comparand parallel searching and its selected applications // Proc. Int. Conf. on Parallel and Distributed Processing Techniques and Applications, PDPTA'97, Las Vegas, USA. – 1997. – Р. 1434–1442.

Kokosinski Z., Sikora W. An FPGA implementation of multi-comparand multi-search associative processor // Proc. 12th Int. Conf. FPL'2002, Lect. Notes in Comp. Sci. – Berlin; Springer-Verlag, v. 2438, 2002. – Р. 826–835.

Louri A., Hatch J.A. Jr. An optical associative parallel processor for high–speed database processing, Computer. // 1994. – v. 27. – Р. 65–72.

Muraszkiewicz M.R. Cellular array architecture for relational database implementation // Future Generations Computer Systems 1988, v. 4. – Р. 31–38.

Nepomniaschaya A.S. Language STAR for associative and parallel computation with vertical data processing // Proc. of the Intern. Conf. on Parallel Computing Technologies, World Scientific. – Singapore. – 1991. – Р. 258–265.

Nepomniaschaya A.S., Kokosinski Z. Associative graph processor and its properties // Proc. of the Intern. Conf. PARELEC'2004, IEEE

Computer Society. – Dresden, Germany, 2004 – Р. 297–302.

Nepomniaschaya A.S., Fet Y.I. Investigation of some hardware accelerators for relational algebra operations // Proc. of the First Aizu Intern. Symp. on Parallel Algorithms / Architecture Synthesis, IEEE Computer Society. – Aizu-Wakamatsu, Fukushima, Japan, 1995. – Р. 308–314.

Nepomniaschaya A.Sh. A language STAR for associative and bit-serial processors and its application to relational algebra // Bulletin of the Novosibirsk Computing Center, Ser. Computer Science, Issue 1, NCC Publisher. – 1993. – Р. 23–36.

Nepomniaschaya A.S. An associative version of the Bellman-Ford algorithm for finding the shortest paths in directed graphs // Proceedings of the 6-th Intern. Conf. PaCT–2001, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2001. – v. 2127. Р 285–292.

Nepomniaschaya, Dvoskina M.A. A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors, Fundamenta Informaticae // IOS Press, Amsterdam. – v. 43. – 2000. – Р. 227–243.

Nepomniaschaya A.S. Efficient implementation of Edmonds' algorithm for finding optimum branchings on associative parallel processors // Proc. of the Eighth Intern. Conf. on Parallel and Distributed Systems (ICPADS'01), IEEE Computer Society. – KyongJu City, Korea. – 2001. – Р . 3–8.

Nepomniaschaya A.S. Efficient update of tree paths on associative systems with bit-parallel processing // Bulletin of the Novosibirsk

Computing Center. Ser. Computer Science, Issue: 23, NCC Publisher. – 2005. – Р. 71–83.

Ozkarahan E. Database Machines and Database Management. – Prentice-Hall, Inc. 1986.

Parhami B. Search and data selection algorithms for associative processors / A. Krikelis, C.C. Weems (еds.) // Associative Processing and Processors, IEEE Computer Society. – 1997. – Р. 10–25.

Ullman J.D Principles of Database Systems, Computer Science Press. – 1980.


Refbacks

  • There are currently no refbacks.