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

  • Е.А. Титенко Юго-Западный государственный университет
  • А.В. Крипачев Юго-Западный государственный университет
  • А.Л. Марухленко Юго-Западный государственный университет
Ключевые слова: Коммутационная сеть, параллельная сортировка, реконфигурация связей

Аннотация

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

Литература

1. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturno-protsedurnoy organizatsiey vychisleniy [Modular-scalable multiprocessor system with structural-procedural organization of computing]. Moscow: Izd-vo YAnus-K, 2003, 380 p.
2. Levin I.I., Dordopulo A.I., Mel'nikov A.K., Gudkov V.A. Metody i sredstva arkhitekturno-nezavisimogo programmirovaniya vysokoproizvoditel'nykh vychislitel'nykh sistem [Methods and means of architecture-independent programming of high-performance computing sys-tems], Desyataya Vserossiyskaya mul'tikonferentsiya po problemam upravleniya (MKPU-2017) [Tenth all-Russian multiconference on control problems (ICPD-2017)]. Rostov-on-Don – Taganrog: Izd-vo YuFU, 2017, pp. 145-147.
3. Burtsev V.S. Parallelizm vychislitel'nykh protsessov i razvitie arkhitektury superEVM [Paral-lelism of computing processes and development of supercomputer architecture]. Moscow: TORUS PRESS, 2006, 416 p.
4. Voevodin V.V., Voevodin Vl.V. Parallel'nye vychisleniya [Parallel computation]. Saint Peters-burg: BKHV-Peterburg, 2002, 608 p.
5. Kravets O.Ya., Podval'nyy E.S., Titov V.S., Yastrebov A.S. Arkhitektura vychislitel'nykh sistem s elementami konveyernoy obrabotki: ucheb. Posobie [Architecture of computer systems with elements of conveyor processing: tutorial]. Saint Petersburg: Politekhnika, 2009, 152 p.
6. Sergeev S.L. Arkhitektury vychislitel'nykh sistem: uchebnik [Architectures of computing sys-tems: textbook]. Saint Petersburg:, 2010, 231 p.
7. Fet Ya.I. Parallel'nye protsessory dlya upravlyayushchikh system [Parallel processors for con-trol systems]. Moscow: Energoatomizdat, 1981, 160 p.
8. Va B.U. Louray M.B., Gotsze Li. 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.
9. Titenko E.A. Obshchaya strukturnaya skhema rekonfiguriruemogo mul'tiprotsessora [General block diagram of reconfigurable multiprocessor], Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin of Voronezh state technical University], 2011, Vol. 7, No. 9, pp. 53-57.
10. Dovgal' V.M., Titov V.S., Titenko E.A. Strategii bystrykh simvol'nykh vychisleniy dlya ischislitel'noy produktsionnoy sistemy [Strategies of fast symbolic calculations for the calculus production system], Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie [Journal of Instrument Engineering], 2008, Vol. 51, No. 2, pp. 44-47.
11. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh [Pro-duction systems and the theorem on conflict words], Izvestiya Tul'skogo gosudarstvennogo universitet. Seriya tekhnologicheskaya sistemotekhnika [News of Tula state University. A se-ries of technological systems engineering], 2006, Issue 15, pp. 92-98.
12. Titenko E.A., Degtyarev S.V. Approximate search in the sample on the basis manber-wu meth-od, Journal of Fundamental and Applied Sciences, 2017, Vol. 9, No. 2, pp. 914-918.
13. Titenko E.A., Evsyukov V.S. Produktsionnye sistemy i teorema o konfliktnykh slovakh [The method and homogeneous computing device of k-approximate search of occurrences on a sample], Izvestiya Tul'skogo gosudarstvennogo universitet. Seriya tekhnologicheskaya sistemotekhnika [Bulletin of Voronezh state technical University], 2006, Issue 15, pp. 92-98.
14. Casbeer D.W. Forest fire monitoring with multiple small UAVs, Proceedings of the 2005 American Control Conference, 2005, pp. 3530-3535.
15. Spry S.C., Girard A.R., Hedrick J.K. Convoy Protection using Multiple Unmanned Aerial Ve-hicles: Organization and Coordination, Proc. of the 24th American Control Conference, Port-land, OR., June 2005.
16. Tonetti S., Hehn M., Lupashin S., D'Andrea R. Distributed control of antenna array with for-mation of UAVs, In World Congress, 2011, August, Vol. 18, No. 1, pp. 7848-7853.
17. Chung J. Cooperative Control of UAVs Using a Single Master Subsystem for Multi-task Multi-target Operations, Advances in Intelligent Systems and Computing, 2015, Vol. 345, pp. 193-212.
18. Korneev V.V., Kiselev A.V. Sovremennye mikroprotsessory [Modern microprocessor]. Saint Petersburg: BHV-SPb. 2003, 448 p.
19. King A. Distributed Parallel Symbolic Execution. B.S., Kansas State University, 2005.
20. Hwang K., Briggs F.A. Computer Architecture and Parallel Processing, 1984, pp. 32-40.
Опубликован
2019-04-03
Выпуск
Раздел
РАЗДЕЛ I. ПРИНЦИПЫ ПОСТРОЕНИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ