Метод и устройство расположения задач в реконфигурируемых вычислительных системах

DOI: 10.34759/trd-2021-120-13

Авторы

Масюков И. И.

Юго-Западный государственный университет, ЮЗГУ, ул. 50 лет Октября, 94, Курск, 305040, Россия

e-mail: ilmas46ru@gmail.com

Аннотация

В статье рассматривается разработанные модель, алгоритм и устройство расположения задач в реконфигурируемых вычислительных системах позволяющие снизить время поиска конфигурации. Модель описывает построение устройства и четыре условия расположения вершин между ПЛИС, позволяющих уменьшить вычислительную сложность алгоритма. Разработанный алгоритм в совокупности процедур выбора, хранения и присвоения допускает реализацию на текущих аппаратных средствах. В ходе экспериментальных исследований разработанного устройства проводился анализ быстродействия и полученной конечной конфигурации, показавший, что время работы алгоритма зависит от количества вершин. Результаты исследования позволяют сделать вывод, что разработанное устройство быстрее аналогичных программных средств в 5,17 раза. Таким образом, о преимуществе аппаратной реализации представленного метода и алгоритма.

Ключевые слова:

реконфигурируемая вычислительная система, ПЛИС, конфигурация, алгоритм, граф

Библиографический список

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — Санкт-Петербург: БХВ-Петербург, 2015. — 608 с.

2. Гузик В.Ф., Каляев И.А., Левин И.И. Реконфигурируемые вычислительные системы. — Таганрог: Южный федеральный университет, 2016. — 472 с.

3. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. — Ростов на Дону: ЮНЦ РАН, 2008. — 320 с.

4. Масюков И.И., Борзов Д.Б., Титов Д.В., Соколова Ю.В. Математическая модель и аппаратно-ориентированный алгоритм планирования размещения программ в системах на кристалле // Труды МАИ. 2021. № 119. URL http://trudymai.ru/published.php?ID=159791. DOI: 10.34759/trd-2021-119-13

5. Борзов Д.Б., Кошелев М.А., Соколова Ю.В. Моделирование реконфигурируемой системы реального времени с учетом уменьшения временных затрат обработки информации // Труды МАИ. 2021. № 117. URL: http://trudymai.ru/published.php?ID=156284. DOI: 10.34759/trd-2021-117-13

6. Коновалов И.С., Остапенко С.С., Кобак В.Г. Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи о покрытии множества // Вестник Донского государственного технического университета. 2017. № 3(90). С. 137ndash;144.

7. Добряков В.А., Енгалычев А.Н., Назаров А.В. Начальное размещение базовых элементов комплементарных металл-окисел-полупроводниковых больших интегральных схем методом случайных назначений // Труды МАИ. 2014. № 72. URL: http://trudymai.ru/published.php?ID=47562

8. Заозерская Л.А., Колоколов А.А. Исследование и решение двухкритериальной задачи о покрытии множества // Проблемы информатики. 2009. № 1(2). С. 14ndash;23.

9. Лебедев Б.К., Лебедев О.Б. Покрытие на основе методов роевого интеллекта // Проблемы разработки перспективных микро- и наноэлектронных систем. 2016. № 1. С. 187-194.

10. Панкратов А.В., Якимов В.Л., Маковский В.Н. Анализ избыточности битовой последовательности для проектов программируемых логических интегральных схем // Труды МАИ. 2015. № 82. URL: http://trudymai.ru/published.php?ID=58828

11. Борзов Д.Б., Басов Р.Г., Титов В.С., Соколова Ю.В. Устройство планирования загрузки процессоров в мультипроцессорных системах критического назначения // Труды МАИ. 2020. № 115. URL: http://trudymai.ru/published.php?ID=119942. DOI: 10.34759/trd-2020-115-14

12. Соловьев В.В. Основы языка проектирования цифровой аппаратуры Verilog. — М.: Горячая Линия-Телеком, 2021. — 364 с.

13. Моисеев Д.В., Чинь В.М., Мозолев Л.А., Моисеева С.Г., Фам С.К. Маршрутизация полета легкого беспилотного летательного аппарата в поле постоянного ветра на основе решения разновидностей задачи коммивояжера // Труды МАИ. 2015. № 79. URL: http://trudymai.ru/published.php?ID=55782

14. Зотов В.Ю. Особенности архитектуры нового поколения ПЛИС с архитектурой FPGA фирмы Xilinx // Компоненты и технологии. 2010. № 12. С. 17-24.

15. Pedroni V.A. Digital Electronics and Design with VHDL, 1st edition, Burlington, Morgan Kaufmann, 2008, 717 p.

16. Ledin J. Architecting High-Performance Embedded Systems: Design and build high-performance real-time digital systems based on FPGAs and custom circuits, Birmingham, Packt Publishing, 2021, 376 p.

17. Deschamps J., Sutter D. G., Cantoacute; E. Guide to FPGA Implementation of Arithmetic Functions, Berlin, Springer, 2012, 472 p.

18. Оре О. Теория графов. — М.: Либроком, 2009. — 354 с.

19. Уилсон Р. Введение в теорию графов. — М.: Вильямс, 2020. — 240 с.

20. Матафонов Д.Е. Создание и отработка маршрутизатора в стандарте SpaceWire на отечественной программируемой логической интегральной схеме // Труды МАИ. 2018. № 103. URL: http://trudymai.ru/published.php?ID=100780

21. Кордовер К.А., Жданов А.А., Данилов А.М. Универсальный блок управления массивом запоминающих устройств наземного отладочного комплекса // Труды МАИ. 2013. № 65. URL: http://trudymai.ru/published.php?ID=35985

22. Коновалов И.С., Фатхи В.А., Кобак В.Г. Применение генетического алгоритма для решения задачи покрытия множеств // Вестник Донского государственного технического университета. 2016. № 3(86). С. 125-132.

Скачать статью