АППАРАТНО-ОРИЕНТИРОВАННЫЙ МЕТОД УСКОРЕННОГО ПОИСКА ВХОЖДЕНИЙ ОБРАЗЦА НА ОСНОВЕ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ
Аннотация
Операция поиска вхождений образца в тексте является общезначимой в современных вы-
числительных средствах при решении проблемно-поисковых задач. Наибольший интерес пред-
ставляют аппаратно-программные решения, имеющие однородную структуру и регулярные связи
между вычислительными блоками. Целью работы является сокращение временных затрат на
поиск вхождений на основе применения параллельного поиска в ассоциативной памяти и метода
распараллеливания по итерациям. Предлагаемый метод использует ассоциативную память для
параллельного поиска вхождений и динамическую реконфигурации структуры исходной строки из
одномерного вида в матричную форму. Вовлечение в реконфигурацию всех элементов влечет из-
быточные затраты внутренней блочной памяти на последовательный просмотр частичных вхо-
ждений по одному множеству стартовых позиций, кратных длине образца (второй символьный
операнд. Вместо этого предложен метод совмещения во времени поиска частичных вхождений по
двум наборам подстрок, кратных длине образца, с одновременным пропорциональным уменьшени-
ем элементов разрядного среза ассоциативной памяти по каждому набору, что позволяет на те-
кущем шаге поиска обрабатывать несколько символов образца. Количественные оценки времени
поиска определяются количеством операций сравнения и записи подстрок в общем цикле работы,
а также пропорциями времени данных операций. Показано, что для образцов более 10 элементов
временной выигрыш составляет примерно в 1,8-2 раза. Данный эффект получен за счет исключе-
ния шагов последовательного сдвига с переходами между граничными элементами строк. Разра-
ботанный метод обеспечивает конвейерную обработку потока строковых операндов с совмеще-
нием просмотра на текущем шаге поиска неединичного множества символов обрабатываемой
строки. Сокращение времени поиска обеспечивается введением конвейера, количество ступеней которого зависит от коэффициента редукции размера разрядного среза, что позволяет аппарат-
но реализовать структурно-процедурный подход, применяемый в реконфигурируемых вычисли-
тельных системах.
Литература
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.
