A HARDWARE-ORIENTED METHOD OF ACCELERATED SEARCH BY TEMPLATE BASED ON STRUCTURAL-PROCEDURAL COMPUTING
Abstract
The operation of searching for occurrences of a pattern in a text is generally significant in modern
computing tools for solving problem-searching tasks. Of greatest interest are hardware and software solutions
that have a homogeneous structure and regular connections between computing blocks. The aim of
the work is to reduce the time costs for searching for occurrences based on the use of parallel search in
associative memory and the method of parallelization by iterations. The proposed method uses associative
memory for parallel search for occurrences and dynamic reconfiguration of the structure of the original
string from a one-dimensional form to a matrix form. The method is critical to such resources as the number
of memory access channels, the volume of block memory for creating and parallel operation of an
array of associative cells. Involvement of all elements in the reconfiguration entails excessive costs of the
internal block memory for sequential viewing of partial entries by one set of starting positions multiples of
the sample length (the second symbolic operand). Instead, an approach is proposed to combine in time the
search for partial entries by two sets of substrings multiples of the sample length, with a simultaneous
proportional reduction in the elements of the bit slice of the associative memory for each set, which allows
processing several sample symbols at the current search step. Quantitative estimates of search time are
determined by the number of comparison and substring writing operations in the overall work cycle, as
well as the proportions of the time of these operations. It is shown that for samples of more than 10 elements,
the time gain is approximately 1.8-2 times. This effect is obtained by eliminating the steps of sequential
shift with transitions between the boundary elements of the strings. The developed method provides
pipeline processing of a stream of string operands with a combination of viewing at the current
search step of a non-unit set of characters of the processed string. The search time is re duced by introducing
a pipeline, the number of stages of which depends on the reduction coefficient of the bit slice size,
which allows hardware implementation of the structural-procedural approach used in reconfigurable
computing systems.
References
and methods in parallel processes]. Moscow: Nauka, 1986, 296 p.
2. Guzik V.F., Kalyaea I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy: ucheb. posobie [Reconfigurable
computing systems: textbook]. Taganrog: Izd-vo YuFU, 2016, 472 p.
3. Korneev V.V. Vychislitel'nye sistemy [Computing systems]. Moscow: Gelios ARV, 2004, 510 p.
4. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM: Sb. statey [Parallelism
of computing processes and development of supercomputer architectures: Collection of articles],
compilers V.P. Torchigin, Yu.N. Nikol'skaya, Yu.V. Nikitin. Moscow: TORUS PRESS, 2006, 416 p.
5. Levin I.I., Fedorov A.M., Doronchenko Yu.I., Raskladkin M.K. Perspektivnye vysokoproizvoditel'nye
rekonfiguriruemye vychisliteli s immersionnym okhlazhdeniem [Promising high-performance reconfigurable
computers with immersion cooling], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU.
Engineering Sciences], 2020, No. 7 (217), pp. 6-19. DOI: 10.18522/2311-3103-2020-7-6-19.
6. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-scalable multiprocessor systems with structuralprocedural
organization of computations]. Moscow: Izd-vo "Yanus-K", 2003, 380 p.
7. Lothaire M. Applied Combinatorics on Words. In: Encyclopedia of Mathematics and its Applications.
Cambridge: Cambridge University Press, 2005.
8. Lyuger Dzh.F. Iskusstvennyy intellekt: strategii i metody resheniya slozhnykh problem [Artificial
intelligence: strategies and techniques for solving complex problems]. Moscow: Izdatel'skiy dom
«Vil'yams». 2003, 864 p.
9. Ognev I.V., Borisov V.V., Sutula N.A. Assotsiativnye pamyat', sredy, sistemy [Associative memory,
environments, systems]. Moscow: Goryachaya liniya – Telekom, 2016, 420 p.
10. Adamov A.A., Eysymont L.K. Varianty arkhitekturnykh resheniy EKB dlya sistem iskusstvennogo
intellekta [Variants of architectural solutions for electronic components for artificial intelligence systems],
Proektirovanie budushchego. Problemy tsifrovoy real'nosti: Tr. 3-y Mezhdunarodnoy
konferentsii [Designing the future. Problems of digital reality: proceedings of the 3rd International
Conference.]. Moscow: IPM im. M.V. Keldysha, 2020, pp. 112-131.
11. Levin I.I., Pelipets A.V. Metodologiya rasparallelivaniya po iteratsiyam pri reshenii zadach lineynoy
algebry na rekonfiguriruemykh vychislitel'nykh sistemakh [Methodology of parallelization by iterations
in solving problems of linear algebra on reconfigurable computing systems], Vestnik
komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and Information Technologies],
2016, No. 7 (145), pp. 34-40.
12. Levin I.I., Podoprigora A.V. Modifitsirovannyy metod obrabotki bol'shikh razrezhennykh
nestrukturirovannykh matrits na rekonfiguriruemykh vychislitel'nykh sistemakh [Modified method for
processing large sparse unstructured matrices on reconfigurable computing systems], Vychislitel'nye
metody i programmirovanie [Computational methods and programming], 2024, Vol. 25, No. 2,
pp. 142-154.
13. Dobritsa V.P., Titenko E.A., Khalin Yu.A., Kiselev A.V. Sistemy iskusstvennogo intellekta [Artificial
intelligence systems]. Kursk: ZAO «Universitetskaya kniga», 2023, 143 p.
14. Eysymont L.K., Molyakov A.S., Zaborovskiy V.S., Fedorov S.A. Simvol'naya obrabotka: epizody
otechestvennoy istorii i perspektivy [Symbolic processing: episodes of Russian history and prospects],
Mater. 2-y Vserossiyskoy nauchno-tekhnicheskoy konferentsii «Superkomp'yuternye tekhnologii (CKT-
2012)», s. Divnomorskoe, 2012 [Materials of the 2nd All-Russian Scientific and Technical Conference
“Supercomputer Technologies (SKT-2012)”, With. Divnomorskoe, 2012], pp. 202-206.
15. Makkonell Dzh. Osnovy sovremennykh algoritmov [Fundamentals of modern algorithms]. 2nd ed.
Moscow: Tekhnosfera, 2004, 368 p.
16. Okulov S.M. Algoritmy obrabotki strok [String processing algorithms]. Moscow: BINOM.
Laboratoriya znaniy, 2009, 255 p.
17. Rybina G.V. Osnovy postroeniya intellektual'nykh system [Fundamentals of building intelligent systems].
Moscow: Finansy i statistika, 2010, 430 p.
18. Hume A., Sunday D. Fast string searching, Software Practice and Experience, November 1991,
Vol. 21, No. 11, pp. 1221-48.
19. Popov E.V. Staticheskie i dinamicheskie ekspertnye sistemy [Static and dynamic expert systems].
Moscow: Finansy i statistika, 1996, 211 p.
20. Titenko E.A., Titov V.S., Konoval'chik A.P. Vysokoproizvoditel'nye vychislitel'nye sistemy na osnove
PLIS [High-performance computing systems based on FPGA], Izvestiya Yugo-Zapadnogo
gosudarstvennogo universiteta [Bulletin of the South-West State University], 2012, No. 4-2 (43), pp. 73.
21. Emel'yanov S.G., Titenko E.A., Zerin I.S. Odnorodnye vychislitel'nye struktury dlya parallel'nykh
simvol'nykh vychisleniy [Homogeneous computing structures for parallel symbolic computations],
Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [Bulletin of the South-West State University],
2011, No. 6-2 (39), pp. 77a-82.
22. Tipikin A.P., Titenko E.A. Modifikatsiya tsikla raboty mashiny vyvoda dlya parallel'nykh
vychislitel'nykh ustroystv [Modification of the output machine operation cycle for parallel computing
devices], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [Bulletin of the South-West State
University], 2011, No. 6-2 (39), pp. 92-96.
23. Zerin I.S., Atakishchev O.I., Titenko E.A. [i dr.]. Metod, algoritm i tekhnicheskoe reshenie
parallel'nogo poiska i podstanovki na assotsiativnoy pamyati [Method, algorithm and technical solution
for parallel search and substitution on associative memory], V mire nauchnykh otkrytiy [In the
world of scientific discoveries], 2012, No. 1-1 (25).
24. Levin I.I., Podoprigora A.V. Metod rasparallelivaniya po bazovym makrooperatsiyam dlya obrabotki
bol'shikh razrezhennykh nestrukturirovannykh matrits na RVS [Method of parallelization by basic
macro-operations for processing large sparse unstructured matrices on RCS], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2022, No. 6 (230), pp. 72-83.
25. Dobritsa V.P., Titenko E.A., Khalin Yu.A., Katykhin A.I. Modeli predstavleniya i obrabotki znaniy v
informatsionno-analiticheskikh sistemakh [Models of representation and processing of knowledge in
information and analytical systems]. Kursk: ZAO «Universitetskaya kniga», 2023, 172 p.
26. Ovchinkin O.V., Titova G.S., Khalin Yu.A. [i dr.]. Issledovanie sistem upravleniya: ucheb. posobie
[Research of control systems: textbook]. Kursk: ZAO Universitetskaya kniga, 2018, 172 p.
