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