КОММУТАЦИОННАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ СРАВНЕНИЙ ЭЛЕМЕНТОВ ДЛЯ ПРОДУКЦИОННЫХ СИСТЕМ, УПРАВЛЯЕМЫХ ПОТОКОМ ДАННЫХ

  • E.A. Титенко
  • E.В. Талдыкин
Ключевые слова: Параллельная сортировка, схема коммутаций, однородное устройство

Аннотация

В статье достигается цель - сокращение временных затрат на генерацию сочетаний
элементов множества. Элементы множества формируются из образцов (левых частей) про-
дукционных правил. Основная задача заключается в построении эффективных по времени схем
(алгоритмов) параллельной генерации сочетаний элементов массива. Применительно к продук-
ционным системам такие схемы необходимы для активации подмножества продукций, приме-
нимых к символьным данным на текущем шаге. За основу взят и развит известный алгоритм
параллельного пузырька. Схема коммутации «параллельный пузырек» состоит из двух чере-
дующихся вариантов коммутации элементов в пары. Эти коммутации основаны на локальном
объединении в пары элементов массива, имеющих смежные индексы. Такое локальное объеди-
нение элементов в пары приводит к «малым» перемещениям элементов по длине массива и ре-
гулярному характеру генерации пар. В каждой паре выполняется операция сравнения-обмена
операндов. Для продукционных систем операция сравнения сводится к поиску пересечений об-
разцов и формированию списка конфликтных слов. Сокращение времени генерации сочетаний
основывается на построении вариантов коммутации с распределенным объединением элемен-
тов в пары с шагом, равным 4. Разработанная схема коммутации содержит на нечетных ша-
гах коммутации с локальным объединением элементов в пары. На четных шагах выполняется
коммутация-ускоритель с распределенным объединением элементов в пары. Моделирование
работы разработанной схемы коммутации осуществлялось на типовых задачах сортировки и
полного перебора пар элементов. Установлено сокращение временных затрат по сравнению с
четно-нечетной сортиовкой на 15-18%. В работе определена линейная зависимость времени
сортировки с углом наклона меньше 1. Это позволяет использовать схему коммутации для
продукционных систем большого размера. Локальные и распределенные связи в схеме коммута-
ции сохраняют свойство регулярности. Эта особенность определяет аппаратную реализацию
схемы в виде параллельного коммутатора с естественным масштабированием. Данная схема
может использоваться в специализированном продукционном устройстве для декомпозиции
продукционной системы на независимые подмножества продукций.

Литература

1. Betelin V.B., Kushnirenko A.G., Rayko G.O. Problemy obespecheniya rosta proizvoditel'nosti
otechestvennykh superEVM v period do 2020 goda [Problems of ensuring the productivity growth
of domestic supercomputers in the period up to 2020], Informatsionnye tekhnologii i vychislitel'nye
sistemy [Information technologies and computing systems], 2010, No. 3, pp. 15-18.
2. Korneev V.V. Sleduyushchee pokolenie superkomp'yuterov [The next generation of supercomputers],
Otkrytye sistemy [Open systems], 2008, No. 8, pp. 14-19.
3. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy: ucheb. posobie
[Reconfigurable computing systems: textbook], under the general editorship of I.A. Kalyaeva.
Taganrog: Izd-vo YuFU, 2016, 472 p.
4. Voevodin, V.V., Voevodin Vl.V. Parallel'nye vychisleniya [Parallel computing]. St. Petersburg:
BKhV-Peterburg, 2002, 608 p.
5. Ognev I.V., Borisov V.V., Sutula N.A. Assotsiativnaya pamyat', sredy, sistemy [Associative
memory, environments, and systems]. Moscow: Goryachaya liniya – Telekom, 2016, 416 p.
6. King A. Distributed Parallel Symbolic Execution. B.S., Kansas State University, 2005,
pp. 181-197.
7. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-stackable multiprocessor systems with structural
and procedural organization of calculations]. Moscow: Izd-vo Yanus-K, 2003, 380 p.
8. Fet Ya.I. Parallel'nye protsessory dlya upravlyayushchikh system [Parallel processors for control
systems]. Moscow: Energoatomizdat, 1981, 160 p.
9. Va B.U., Louray M.B., Li Gotsze. EVM dlya obrabotki simvol'noy informatsii [Computer for
processing symbolic information], TIIER [Proceedings of the Institute of Electrical and Radio
Electronics Engineers], 1989, Vol. 77, No. 4, pp. 5-40.
10. Artamonov D.S., Putrya M.G. Metod optimizatsii vychislitel'nogo protsessa na
rekonfiguriruemykh vychislitel'nykh sredakh [Method of optimization of the computational
process on reconfigurable computing environments], Informatsionnye tekhnologii
vychislitel'nye sistemy [Information Technologies computing systems], 2010, No. 3, pp. 19-26.
11. Putrya F.M. Arkhitekturnye osobennosti protsessorov s bol'shim chislom vychislitel'nykh
yader [Architectural features of processors with a large number of computing cores],
Informatsionnye tekhnologii [Information technologies], 2009, No. 4, pp. 2-7.
12. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM [Parallelism
of computing processes and the development of the architecture of supercomputers].
Moscow: TORUS PRESS, 2006, 416 p.
13. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh
[Productional systems and the theorem on conflict words], Izvestiya Tul'skogo
gosudarstvennogo universitet [Izvestiya Tulskogo gosudarstvennogo universiteta], 2006,
Issue 15, pp. 92-98.
14. Titenko E.A. Obshchaya strukturnaya skhema rekonfiguriruemogo mul'tiprotsessora [General
block diagram of a reconfigurable multiprocessor], Vestnik Voronezhskogo gosudarstvennogo
tekhnicheskogo universiteta [Bulletin of the Voronezh State Technical University], 2011,
Vol. 7, No. 9, pp. 53-57.
15. Titenko E.A. Metod i odnorodnoe vychislitel'noe ustroystvo k-priblizitel'nogo poiska vkhozhdeniy
po obraztsu [A method and a homogeneous computing device for k-approximate search for occurrences
in a sample], Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin
of the Voronezh State Technical University], 2011, Vol. 7, No. 7, pp. 70-78.
16. Titenko E.A. Metod parallel'nogo poiska po obraztsu i matrichnoe ustroystvo dlya ego
realizatsii [Method of parallel search by sample and matrix device for its implementation],
Informatsionnye sistemy i tekhnologii [Information systems and technologies], 2011, No. 4
(66), pp. 24-30.
17. Wichert A. Artificial intelligence and a universal quantum computer, AI Communications,
2016, Vol. 29, Issue 4, pp. 537-543.
18. Titenko E.A., Degtyarev S.V. Approximate search in the sample on the basis manber-wu method,
Journal of Fundamental and Applied Sciences, 2017, Vol. 9, No. 2, pp. 914-918.
19. Titenko E.A., Zerin I.S. Ischislitel'naya sistema produktsiy i protsedura raspoznavaniya
konfliktov dannykh [Calculative system of products and the procedure for recognizing data
conflicts], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and
Information Technologies], 2012, No. 2, pp. 24-29.
20. Lyuger Dzh.F. Iskusstvennyy intellekt: strategii i metody resheniya slozhnykh problem [Artificial
intelligence: strategies and methods for solving complex problems]. Moscow: Izd. dom
«Vil'yams». 2003, 864 p.
21. Titenko E.A., Kripachev, Marukhlenko A.L. Kommutatsionnaya skhema parallel'nykh parnykh
perestanovok dlya spetsializirovannogo produktsionnogo ustroystva [Switching scheme of
parallel pair permutations for a specialized production device], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (203), pp. 29-38.
22. Makkonell Dzh. Osnovy sovremennykh algoritmov [Fundamentals of modern algorithms].
2nd ed.: transl. from engl., ed. by S.K. Lando. Moscow: Tekhnosfera, 2004, 386 p.
23. Knut D. Sortirovka i poisk [Sorting and searching]. Vol. 3. Moscow: Vil'yams, 2000, 500 p.
24. Batcher K.E. Sorting Networks and their Applications, Proc. AFIPS Spring Joint Comput.
Conf., 1968, Vol. 32, pp. 307314.
25. Pisarenko I.V., Alekseev K.N., Mel'nikov A.K. Resursonezavisimoe predstavlenie
sortiruyushchikh setey na yazyke programmirovaniya Set@l [Resource-independent representation
of sorting networks in the programming language Set@l], Vestnik komp'yuternykh i
informatsionnykh tekhnologiy [Bulletin of Computer and Information Technologies], 2019,
No. 9, pp. 3-10.
Опубликован
2021-02-25
Выпуск
Раздел
РАЗДЕЛ I. ПРИНЦИПЫ ПОСТРОЕНИЯ И АРХИТЕКТУРА СУПЕРКОМПЬЮТЕРОВ