РАСШИРЕННАЯ ПРОДУКЦИОННАЯ МАШИНА ВЫВОДА ДЛЯ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
Аннотация
Актуальность. В работе развивается теоретический подход организации параллельных
вычислений на основе продукционной модели управления потоком данных. Продукционная пара-
дигма параллельных вычислений имеет необходимые условия построения новых архитектур и ор-
ганизации высокопроизводительных параллельных вычислений. Рассматриваются продукционные
системы, управляющие наборами левых частей продукций (образцами). Цель – повышение эффек-
тивности параллельного вывода решений за счет сокращения непродуктивных затрат времени на
перебор возможных альтернатив в пространстве графа вывода. Метод решения основан на соз-
дании расширенной машины символьного вывода для реализации параллельных вычислений. Маши-
на символьного вывода – это абстрактная система, систематизирующая продукционный вывод
как последовательность четырех вычислительно-поисковых этапов. Машина вывода задает об-
щий вид однородной вычислительной системы. Главное отличие – декомпозиция базы продукцион-
ных правил на отдельные подмножества на основе алгебры продукций и структуризации отноше-
ний между продукциями. Вместо единой «плоской» структуры предлагается базу продукций де-
композировать на части – ввести систему независимых подмножеств продукций. Параллельный
вывод реализуется по отдельным подмножествам без потери общности, при этом перебор воз-
можных альтернатив является сокращенным. Каждое подмножество продукций имеет специ-
альное слово-маркер, по значению которого активизируется только одно подмножество продук-
ций. Оно загружается в операционную часть однородной вычислительной системы для параллель-
ного исполнения. Результаты. Показано, что количественные оценки сокращения времени вывода
зависят от общего числа продукций, количества образуемых подмножеств и их размера. Модели-
рование показало, что даже простейшая декомпозиция на два подмножества (одно подмножест-
во состоит из 2-х продукций) дает временной выигрыш (1,07-1,52) раз, пропорциональный общему
числу продукций. Выводы. Построенная расширенная машина символьного вывода является осно-
вой для последующего создания архитектуры однородной вычислительной системы с комбинацией
централизованного и локального управления, что позволяет вычислительным блокам однородной
операционной части параллельно работать без избыточного обращения к обшей памяти.
Литература
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: manual]. Taganrog: Izd-vo YuFU, 2016, 472 p.
3. Bulyga F.S., Kureychik V.M. Sravnitel'nyy analiz metodov vektorizatsii tekstovykh dannykh bol'shoy
razmernosti [Comparative analysis of methods for vectorizing high-dimensional text data], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2023, No. 2 (232), pp. 212-226.
4. Titenko E.A., Emel'yanov S.G., Zerin I.S. Odnorodnye vychislitel'nye struktury dlya parallel'nykh
simvol'nykh vychisleniy [Homogeneous computational structures for parallel symbolic computations],
Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [News of the South-West State University],
2011, No. 6 (39), Part 2, pp. 77-82.
5. Lothaire M. Algebraic Combinatorics on Words. Cambridge: Cambridge University Press; 2002.
(In Eng). – DOI: https:// doi.org/10.1017/CBO9781107326019.
6. Lothaire M. Applied Combinatorics on Words. In: Encyclopedia of Mathematics and its Applications.
Cambridge: Cambridge University Press, 2005.
7. 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.
8. Ognev I.V., Borisov V.V., Sutula N.A. Assotsiativnye pamyat', sredy, sistemy [Associative memory,
environments, systems], Moscow: Goryachaya liniya – Telekom, 2016, 420 p.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v
optimizatsii [Bioinspired optimization methods]. Moscow: Fizmatlit, 2009, 384 p.
10. Adamov A.A., Eysymont L.K. Varianty arkhitekturnykh resheniy EKB dlya sistem iskusstvennogo
intellekta [Options for ECB architectural solutions 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. Va B.U., Louray M.B., Gotsze Li. EVM dlya obrabotki simvol'noy informatsii [Computer for processing
symbolic information], TIIER [TIIER], 1989, Vol. 77, No. 4, pp. 5-40.
12. 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.
13. 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)» [Materials of the 2nd All-Russian Scientific and Technical Conference “Supercomputer Technologies
(SKT-2012)”]. Divnomorskoe, 2012, pp. 202-206.
14. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektur superEVM: Sb. statey [Parallelism
of computing processes and development of supercomputer architectures: collection of articles:
Articles]. Moscow: TORUS PRESS, 2006, 416 p.
15. Wichert A. Artificial intelligence and a universal quantum computer, AI Communications, 2016,
Vol. 29. Issue 4, pp. 537-543.
16. Bova V.V., Kravchenko Yu.A., Rodzin S.I. Metody i algoritmy klasterizatsii tekstovykh dannykh
(obzor) [Methods and algorithms for clustering text data (review)], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2022, No. 4 (228), pp. 122-143.
17. Rybina G.V. Osnovy postroeniya intellektual'nykh system [Fundamentals of building intelligent systems].
Moscow: Finansy i statistika. 2010, 430 p.
18. Popov E.V. Staticheskie i dinamicheskie ekspertnye sistemy [Static and dynamic expert systems].
Moscow: Finansy i statistika. 1996, 211 p.
19. Dovgal' V.M. Metody modifikatsii formal'nykh sistem obrabotki simvol'noy informatsii [Methods for
modifying formal systems for processing symbolic information]. Kursk: Izd-vo Kursk. gos. tekhn. unt,
1996, 115 p.
20. Titenko E.A. Produktsionnaya model' i abstraktnaya mashina dlya realizatsii raspredelennykh
parallel'nykh vychisleniy [Production model and abstract machine for implementing distributed parallel
computing], Telekommunikatsii [Telecommunications], 2012, No. 6, pp. 7-11.
21. 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 [News of the South-West State
University], 2011, No. 6-2 (39), pp. 92-96.
22. Tutov E.B., Titenko E.A., Atakishchev A.O., TSukanov K.S. Primenenie kontekstno-svobodnykh grammatik
dlya obrabotki tekstov na estestvennom yazyke [Application of context-free grammars for processing
texts in natural language], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya:
Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie [News of the South-
Western State University. Series: Management, computer technology, computer science. Medical instrumentation],
2012, No. 2-1, pp. 97-101.
23. Dovgal' V.M., Titenko E.A. Parallel'nye strategii vyvodov dlya sistem podderzhki prinyatiya resheniya
[Parallel inference strategies for decision support systems], Vestnik novykh meditsinskikh tekhnologiy
[Bulletin of new medical technologies], 2006, Vol. 13, No. 1, pp. 143-144.
24. 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.
25. Karri Kh.B. Osnovaniya matematicheskoy logiki [Foundations of mathematical logic]: transl. from
english. Moscow: Mir, 1969, 568 p.