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


DOI: 10.34759/trd-2021-119-13

Авторы

Масюков И. И.1*, Борзов Д. Б.1**, Титов Д. В.1***, Соколова Ю. В.2****

1. Юго-Западный государственный университет, ЮЗГУ, ул. 50 лет Октября, 94, Курск, 305040, Россия
2. Научно-производственное объединение им. С.А. Лавочкина, ул. Ленинградская, 24, Химки, Московская область, 141400, Россия

*e-mail: ilmas46ru@gmail.com
**e-mail: borzovdb@mail.ru
***e-mail: amazing2004@inbox.ru
****e-mail: jv.sokolova@mail.ru

Аннотация

В данной работе представлена математическая модель и аппаратно-ориентированный алгоритм планирования программ в системах на кристалле, который позволит уменьшить временную задержку расчета новой топологии реконфигурируемой вычислительной системы и повысит ее отказоустойчивость. Производится программное моделирование разработанного алгоритма и алгоритма, основанного на идеях метода ветвей и границ для следующих типов графов: кольцевой, полносвязный, планарный, Кэли прямого произведения, звезда с применением построения Халина, двудольный.

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

система на кристалле, реконфигурация, архитектура, размещение, ПЛИС, конфигурация, математическая модель, алгоритм

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

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

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

  3. Суворова Е.А., Шейнин Ю.Е. Проектирование цифровых систем на VHDL. — СПб.: БХВ—Петербург, 2003. — 576 с.

  4. Губанов Д.А., Стешенко В.Б., Храпов В.Ю., Шипулин С.Н. Перспективы реализации алгоритмов цифровой фильтрации на основе ПЛИС фирмы ALTERA // Chip News. 1997. № 9. С. 26 — 33.

  5. Стешенко В.Б. Школа схемотехнического проектирования устройств обработки сигналов // Компоненты и технологии. 2000. № 3. С. 43 — 46.

  6. Набатов А.Н., Веденяпин И.Э., Мухтаров А.Р. Применение онтологического подхода к процессу проектирования информационной системы // Труды МАИ. 2018. № 102. URL: http://trudymai.ru/published.php?ID=99177

  7. Кондрашин М.А., Арсенов О.Ю., Козлов И.В. Применение технологии виртуализации и облачных вычислений при построении сложных распределенных моделирующих систем // Труды МАИ. 2016. № 89. URL http://trudymai.ru/published.php?ID=73411

  8. Кудрявцев В.Б., Подколзин, А.С., Болотов А.А. Основы теории однородных структур. — М.: Наука, 1990. — 296 с.

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

  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. Zhang L., Wong T.N. Solving integrated process planning and scheduling problem with constructive metaheuristics // Information Science, 2016, vol. 340 — 341, pp. 1 — 16. DOI: 10.1016/j.ins.2016.01.001

  13. Zhang S., Wong, T.N. Integrated process planning and scheduling: An enhanced ant colony optimization heuristic with parameter tuning // Journal of Intelligent Manufacturing, 2018, vol. 29, pp. 585 — 601. URL: https://doi.org/10.1007/s10845-014-1023-3

  14. Бобынцев Д.О., Борзов Д.Б. Минимаксиминный критерий оценки качества размещения параллельных подпрограмм в матричных мультиконтроллерах // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2012. № 2-1. С. 27 — 31.

  15. Оре О. Теория графов. — М.: Наука, 1968. — 352 с.

  16. Масюков И.И. Математическая модель и алгоритм устройства планирования программ в системах на кристалле // Бюллетень науки и практики. 2016. № 5. С. 40 — 44. DOI: 10.5281/zenodo.54825

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

  18. Струченков В.И. Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач. — М.: Солон-Пресс, 2016. — 192 с.

  19. Головицына М.В., Литвинов В.П. Методы, модели и алгоритмы в автоматизированном проектировании промышленных изделий. — М.: Инфра-М, 2016. — 284 с.

  20. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. — М.: ФИЗМАТЛИТ, 2003. 240 c.


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

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2024

 Вход