Статья

Название статьи КОММУТАЦИОННАЯ СХЕМА ПАРАЛЛЕЛЬНЫХ ПАРНЫХ ПЕРЕСТАНОВОК ДЛЯ СПЕЦИАЛИЗИРОВАННОГО ПРОДУКЦИОННОГО УСТРОЙСТВА
Автор Е. А. Титенко, А. В. Крипачев, А. Л. Марухленко
Рубрика РАЗДЕЛ I. ПРИНЦИПЫ ПОСТРОЕНИЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Месяц, год 08, 2018
Индекс УДК 681.3+004.32
DOI 10.23683/2311-3103-2018-8-29-38
Аннотация Достигается цель - сокращение временных затрат на генерацию сочетаний элементов множества. Элементы множества формируются из образцов (левых частей) продукционных правил. Основная задача заключается в построении эффективных по времени схем (алгоритмов) параллельной генерации сочетаний элементов массива. Применительно к продукционным системам такие схемы необходимы для активации подмножества продукций, применимых к символьным данным на текущем шаге. За основу взят и развит известный алгоритм параллельного пузырька. Схема коммутации «параллельный пузырек» состоит из двух чередующихся вариантов коммутации элементов в пары. Эти коммутации основаны на локальном объединении в пары элементов массива, имеющих смежные индексы. Такое локальное объединение элементов в пары приводит к «малым» перемещениям элементов по длине массива и регулярному характеру генерации пар. В каждой паре выполняется операция сравнения-обмена операндов. Для продукционных систем операция сравнения сводится к поиску пересечений образцов и формированию списка конфликтных слов. Сокращение времени генерации сочетаний основывается на построении вариантов коммутации с распределенным объединением элементов в пары с шагом, равным 4. Разработанная схема коммутации содержит на нечетных шагах коммутации с локальным объединением элементов в пары. На четных шагах выполняется коммутация-ускоритель с распределенным объединением элементов в пары. Моделирование работы разработанной схемы коммутации осуществлялось на типовых задачах сортировки и полного перебора пар элементов. Установлено сокращение временных затрат по сравнению со схемой «параллельный пузырек» на 15–18 %. В работе определена линейная зависимость времени сортировки с углом наклона меньше 1. Это позволяет использовать схему коммутации для продукционных систем большого размера. Локальные и распределенные связи в схеме коммутации сохраняют свойство регулярности. Эта особенность определяет аппаратную реализацию схемы в виде параллельного коммутатора с естественным масштабированием. Данная схема может использоваться в специализированном продукционном устройстве для декомпозиции продукционной системы на независимые подмножества продукций.

Скачать в PDF

Ключевые слова Коммутационная сеть; параллельная сортировка; реконфигурация связей.
Библиографический список 1. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. – М.: Изд-во Янус-К, 2003. – 380 с.
2. Левин И.И., Дордопуло А.И., Мельников А.К., Гудков В.А. Методы и средства архитектурно-независимого программирования высокопроизводительных вычислительных систем // Десятая Всероссийская мультиконференция по проблемам управления (МКПУ-2017). – Ростов-на-Дону – Таганрог: Изд-во ЮФУ, 2017. – С. 145-147.
3. Бурцев В.С. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ. – М.: ТОРУС ПРЕСС, 2006. – 416 с.
4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. – 608 с.
5. Кравец О.Я., Подвальный Е.С., Титов В.С., Ястребов А.С. Архитектура вычислительных систем с элементами конвейерной обработки: учеб. пособие. – СПб: Политехника, 2009. – 152 с.
6. Сергеев С.Л. Архитектуры вычислительных систем: учебник. – СПб.: БХВ-Петербург, 2010. – 231 с.
7. Фет Я.И. Параллельные процессоры для управляющих систем. – М.: Энерго-атомиздат, 1981. – 160 с.
8. Ва Б.У. Лоурай М.Б., Гоцзе Ли. ЭВМ для обработки символьной информации // ТИИЭР. – 1989. – T. 77, № 4. – С. 5-40.
9. Титенко Е.А. Общая структурная схема реконфигурируемого мультипроцессора // Вестник Воронежского государственного технического университета. – 2011. – T. 7, № 9.
– С. 53-57.
10. Довгаль В.М., Титов В.С., Титенко Е.А. Стратегии быстрых символьных вычислений для исчислительной продукционной системы // Известия высших учебных заведений. Приборостроение. – 2008. – T. 51, № 2. – С. 44-47.
11. Титенко Е.А., Евсюков В.С. Продукционные системы и теорема о конфликтных словах // Известия Тульского государственного университет. Серия технологическая системотехника. – 2006. – Вып. 15. – С. 92-98.
12. 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. – P. 914-918.
13. Титенко Е.А. Метод и однородное вычислительное устройство k-приблизительного поиска вхождений по образцу // Вестник Воронежского государственного технического университета. – 2011. – T. 7, № 7. – С. 70-78.
14. Casbeer D.W. Forest fire monitoring with multiple small UAVs // Proceedings of the 2005 American Control Conference. – 2005. – P. 3530-3535.
15. Spry S.C., Girard A.R., Hedrick J.K. Convoy Protection using Multiple Unmanned Aerial Vehicles: Organization and Coordination // Proc. of the 24th American Control Conference, Portland, OR., June 2005.
16. Tonetti S., Hehn M., Lupashin S., D'Andrea R. Distributed control of antenna array with formation of UAVs // In World Congress. – 2011, August. – Vol. 18, No. 1. – P. 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.
– P. 193-212.
18. Корнеев В.В., Киселев А.В. Современные микропроцессоры. – СПб.: BHV-СПб. 2003.
– 448 с.
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. – P. 32-40.

Comments are closed.