Abstract
The multi-comparand associative search paradigm is shown to be efficient in processing complex search problems from many application areas including computational geometry, graph theory, and list/matrix computations. In this paper the first FPGA implementation of a small multi-comparand multi-search associative processor is reported. The architecture of the processor and its functions are described in detail. The processor works in a combined bit-serial/bit-parallel mode. Its main component is a multi-comparand associative memory with up to 16 programmable prescription functions (logic searches). Parameters of implemented FPGA devices are presented and discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Digby D.W.: A search memory for many-to-many comparisons. IEEE Transactions on Computers C-22 (1973) 768–772
Fernstrom C., Kruzela I., Svensson B.: LUCAS associative array processor. Design, programming and application studies, LNCS 216 (1986)
Foster C.C.: Content addresable parallel processors. Van Nostrand Reinhold (1976)
Herbordt M.C., Weems C.C.: Associative, multiassociative and hybrid procesing. [in:] Krikelis A. Weems C.C. (eds): Associative processing and processors. IEEE Computer Society Press (1997) 26–49
Herrmann F.P. et al.: A dynamic three-state memory cell for high-density associative processors. IEEE Journal of Solid-State Circuits 26 (1991) 537–541
Higuchi T. et al.: The IXM2 parallel associative processor for AI. Computer 27 (1994) 53–63
Jalaleddine S.M.S., Johnson L.G.: Associative IC memories with relational search and nearest-match capabilities. IEEE Journal of Solid-State Circuits 27 (1992) 892–900
Kapralski A., Kokosiński Z., Mól W.: An electronic circuit for the maximum selection in a RAM. Patent No. 146021, Polish Patent Office (1989)
Kapralski A.: The maximum and minimum selector SELRAM and its application for developing fast sorting machines. IEEE Transactions on Computers 38 (1989) 1572–1576
Kapralski A.: Supercomputing for solving a class of NP-complete and isomorphic complete problems. Computer Systems Science & Eng. 7 (1992) 218–228.
Kapralski, A.: Sequential and parallel processing in depth search machines. World Scientific (1994)
Knuth D.E.: The art of computer programming. Sorting and searching, Addison-Wesley (1973)
Kokosiński Z.: Mask and pattern generation for associative supercomputing. Proc. 12th Int. Conf. on Applied Informatics AI’94, Annecy, France (1994) 324–326
Kokosiński 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
Krikelis A. Weems C.C. (eds): Associative processing and processors. IEEE Computer Society Press (1997)
Louri A., Hatch J.A.: An optical associative parallel processor for high-speed database processing. Computer 27 (1994) 65–72.
Parhami B.: Extreme-value search and general selection algorithms for fully parallel associative memories. The Computer Journal 39 (1996) 241–250
Schultz K.J., Gulak P.G.: Fully parallel integrated CAM/RAM using preclassification to enable large capacities. IEEE Journal of Solid-State Circuits 31 (1996) 689–699
Sikora W.: Synthesis of a programmable associative memory operating on two data sets. MS thesis, Politechnika Krakowska, Kraków, Poland (2000)
Stüttgen H.: A hierarchical associative processing system. LNCS 195 (1986)
Yamagata T. et al.: A 288-kb fully parallel content addressable memory using a stacked-capacitor cell structure. IEEE Journal of Solid-State Circuits 27 (1992) 1927–1933
Yau S.S., Fung H.S.: Associative processor architecture-a survey. Computing Surveys 9 (1977) 3–27
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kokosiński, Z., Sikora, W. (2002). An FPGA Implementation of a Multi-comparand Multi-search Associative Processor. In: Glesner, M., Zipf, P., Renovell, M. (eds) Field-Programmable Logic and Applications: Reconfigurable Computing Is Going Mainstream. FPL 2002. Lecture Notes in Computer Science, vol 2438. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46117-5_85
Download citation
DOI: https://doi.org/10.1007/3-540-46117-5_85
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44108-3
Online ISBN: 978-3-540-46117-3
eBook Packages: Springer Book Archive