Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Михайлов Денис Васильевич

• Михайлов Денис Васильевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Михайлов Денис Васильевич

ВВЕДЕНИЕ

1 МЕТОДЫ И СРЕДСТВА РЕШЕНИЯ ЗАДАЧ, ОПИСАННЫХ ПОСЛЕДОВАТЕЛЬНЫМ ИНФОРМАЦИОННЫМ ГРАФОМ

1.1 Кризис архитектуры фон Неймана

1.3 МВС со структурной реализацией вычислений

1.4 Распараллеливание информационного графа

1.5 Выводы

2 МЕТОДЫ ПРЕОБРАЗОВАНИЯ ОДНОРОДНОГО ИНФОРМАЦИОННОГО ГРАФА ИЗ ПОСЛЕДОВАТЕЛЬНОЙ В ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНУЮ ФОРМУ

2.1 Преобразование однородного графа, состоящего из ассоциативных операций

2.2 Преобразование однородного графа, состоящего из ассоциативных операций произвольной латентности

2.3 Преобразование информационного графа задачи вычисления числа Фибоначчи

2.4 Выводы

3 МЕТОДЫ ПРЕОБРАЗОВАНИЯ СМЕШАННОГО ИНФОРМАЦИОННОГО ГРАФА ИЗ ПОСЛЕДОВАТЕЛЬНОЙ В ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНУЮ ФОРМУ

3.1 Преобразование смешанного последовательного графа, одна из операций которого является дистрибутивной по отношению к другой

3.2 Применимость полученных алгоритмов для преобразования графов произвольной формы

3.3 Анализ устойчивости распараллеленного фильтра

3.4 Преобразование смешанного графа, содержащего условные операции

3.5 Выводы

4 МЕТОДЫ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИОННЫХ ГРАФОВ, СОСТОЯЩИХ ИЗ МАКРООПЕРАЦИЙ

4.1 Преобразование графа решения СЛАУ методом прогонки

4.2 Преобразование графа решения СЛАУ с трёхдиагональной матрицей методом Гаусса-Зейделя

4.3 Преобразование графа решения СЛАУ с плотной матрицей методом Гаусса-Зейделя

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом»

ВВЕДЕНИЕ

В современном мире сложность задач, решаемых на вычислительной технике, постоянно растёт. Компьютерное моделирование природных и антропогенных процессов, задачи криптографии, радиолокации, поиска по базам данных и т.д. - всё это требует громадных вычислительных затрат, которые возрастают вместе с ростом требований к скорости получения результатов и их качеству. Например, вычислительная сложность задачи коммивояжёра зависит от размера массива входных данных факториально [1], а вычислительная сложность прямого хода алгоритма Гаусса с выбором ведущей строки зависит от размера СЛАУ кубически [2]. Многие описанные задачи содержат фрагменты, которые могут быть описаны с помощью последовательного информационного графа.

Однопроцессорные и многопроцессорные рабочие станции, построенные на базе универсальных процессоров CPU, обладают недостаточной производительностью при решении задач описанного класса из-за особенности архитектуры таких систем: снижения реальной производительности системы при выполнении большого количества межпроцессорных обменов, сопоставимого с количеством выполняемых операций [3]. Гибридные вычислительные системы традиционной архитектуры, построенные на базе универсальных процессоров CPU и графических ускорителей GPU, не позволяют решать вычислительно-трудоемкие сильносвязанные задачи, требующие повышенной точности вычислений с достаточной скоростью. Такие системы также подвержены снижению реальной производительности при использовании нескольких GPU из-за накладных расходов на синхронизацию выходных потоков данных [4].

Вычислительные системы, построенные на базе заказных микросхем ASIC [5], позволяют решить проблему недостаточной производительности, однако имеют высокую стоимость разработки и производства. Также при изменении алгоритма вычислений, старые чипы невозможно использовать в вычислениях, и возникает необходимость производства новых микросхем для замены старых [6].

Применение таких вычислительных элементов целесообразно при организации массового выпуска конечного продукта, что создаёт значительные ограничения области применения.

Программируемые логические интегральные схемы (ПЛИС) [7] и построенные на их основе реконфигурируемые вычислительные системы (РВС), потенциально позволяют решать различные вычислительно-трудоемкие задачи. В то же время существует большой класс задач, алгоритм решения которых соответствует последовательным информационным графам, которые теоретически не поддаются эффективному распараллеливанию [8].

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

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

Степень разработанности темы исследования. В диссертации был

выполнен анализ существующих вычислительно-трудоемких задач, описанных

последовательным информационным графом; существующих малогабаритных

вычислительных средств традиционной архитектуры, построенных на базе CPU и

GPU; специальных вычислительных средств, построенных на базе заказных

микросхем ASIC и реконфигурируемых вычислительных систем; методов

создания эффективных параллельных программ для РВС. Метод структурного

распараллеливания решения задач на РВС, реализованный Левиным И.И.,

позволяет создавать параллельно-конвейерные вычислительные структуры и

эффективные программные решения, обладающие свойством масштабируемости,

что позволяет при увеличении вычислительного ресурса добиться близкого к

линейному роста производительности. Данный метод для решения задач на РВС в

6

дальнейшем был модернизирован: Семерниковым Е.А. - для задач цифровой обработки сигналов, Дордопуло А.И. - для автоматического создания параллельных программ для РВС. Однако данный структурный метод в общем случае не может быть применен к распараллеливанию задач с информационным графом. В работе Алексеева К.Н. был предложен подход к изменению топологии графа для частного случая с целью снижения аппаратных затрат при обработке в реальном масштабе времени. В данной работе впервые решается задача создания эффективных параллельно-конвейерных программ, для решения ряда задач, описанных последовательным информационным графом, путём изменения топологии при сохранении информационной эквивалентности.

Проведённый в диссертации обзор существующих аппаратных решений в области высокопроизводительных вычислительных систем, показал, что универсальные процессоры, которые являются основным аппаратным средством создания суперкомпьютеров в настоящее время, обладают низкой реальной производительностью для широкого круга задач. При этом рост пиковой производительности таких систем за последние годы также замедлился. Это вызвано как сложностями технической реализации (необходимость интенсивного теплоотвода, дальнейшая миниатюризация и т.д.), так и фундаментальными ограничениями (закон Амдала). Важной проблемой подобных систем является то, что они построены по архитектуре фон Неймана, что обуславливает высокую долю служебных команд и, как следствие, низкую реальную производительность системы. Также реальная производительность таких систем при решении сильносвязанных задач значительно снижается и может составлять 3-5% от пиковой [3]. Эти же проблемы есть и у систем, построенных с использованием графических ускорителей.

При этом ПЛИС демонстрируют близкий к линейному рост производительности от поколения к поколению, а реальная производительность систем, построенных на их основе, составляет не менее 60% от пиковой [9]. Это обусловлено структурной реализацией вычислений в системах, построенных на

основе ПЛИС, при которой информационный граф вычислительного процесса близок к информационному графу задачи.

ПЛИС значительно менее ограничены сложностями технической реализации по сравнению с универсальными процессорами, но фундаментальные ограничения наподобие закона Амдала действуют и на них. Существуют задачи, информационные графы которых являются последовательными. Однако в случае, если операции информационного графа задачи обладают некоторыми свойствами (ассоциативность, дистрибутивность), такой граф может быть распараллелен. Таким образом, актуальной является задача разработки методов создания параллельно-конвейерных программ для задач, описанных последовательным информационным графом для реализации их на РВС.

Диссертация является завершённым исследованием, в котором впервые решается задача создания методов создания параллельно-конвейерных программ для задач, описанных последовательным информационным графом.

Целью работы является создание методов повышения реальной производительности РВС при решении задач, которые могут быть описаны последовательным информационным графом.

Объектом исследования является программное обеспечение РВС.

Предметом исследования являются методы создания параллельно-конвейерных программ для задач с последовательным информационным графом.

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

Для достижения указанной цели решены следующие задачи:

1) проведен анализ существующих вычислительно-трудоемких задач, описанных последовательным информационным графом, которые не могут быть эффективно решены существующими вычислительными средствами традиционной архитектуры, построенными на базе CPU и GPU;

2) разработан метод преобразования последовательного информационного графа в параллельно-конвейерную форму;

3) разработан метод распараллеливания информационных графов адаптивных рекурсивных фильтров, позволяющий определить необходимую степень распараллеливания для сохранения устойчивости фильтра;

4) на основе преобразованных графов синтезированы вычислительные структуры для решения СЛАУ методом прогонки и методом Гаусса-Зейделя, а также для решения задачи адаптивной цифровой фильтрации в зависимости от имеющихся в наличии вычислительных ресурсов.

Методы исследований. В ходе исследований были использованы: методы структурной организации вычислений на РВС; методы теории графов; структурно-процедурный метод организации вычислений на РВС; методы цифровой обработки сигналов; методика многокритериальной редукции вычислительной структуры задачи. Практические исследования проведены на реконфигурируемых вычислительных системах различных архитектур и конфигураций.

Научная новизна диссертационной работы заключается в том, что в ней разработаны:

1) метод преобразования последовательного информационного графа содержащего ассоциативные и дистрибутивные операции в параллельно-конвейерную форму, отличающийся учётом латентности вычислительных блоков, реализующих операции и имеющегося вычислительного ресурса;

2) метод определения необходимой степени распараллеливания информационного графа рекурсивного фильтра, учитывающий латентность сумматоров и умножителей, размер доступного вычислительного ресурса и исходные параметры фильтра, и обеспечивающий устойчивость преобразованного фильтра, отличающийся возможностью работы с адаптивными рекурсивными фильтрами;

3) вычислительные структуры, синтезированные на основе

преобразованных последовательных информационных графов в зависимости от

9

имеющихся в наличии вычислительных ресурсов, для решения СЛАУ методом прогонки и методом Гаусса-Зейделя, а также для решения задач адаптивной цифровой фильтрации.

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

Автором показано, что метод распараллеливания информационных графов рекурсивных фильтров, позволяющий определить необходимую степень распараллеливания в зависимости от доступного вычислительного ресурса и свойств исходного фильтра, и гарантирующий устойчивость синтезированного фильтра, может быть применён для преобразования информационного графа адаптивного фильтра.

Автором показано, что для графа, не тождественного элементарному пути, при применении разработанного метода преобразования, возможен переход к параллельно-конвейерному виду (на примере графа решения СЛАУ методом прогонки). Автором показано, что для графа решения СЛАУ методом Гаусса-Зейделя применение предложенного метода распараллеливания позволяет добиться ускорения по сравнению с последовательной реализацией даже в том случае, когда оборудования не хватает для реализации базового подграфа целиком.

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

Применение предложенного метода для преобразования информационного графа решения СЛАУ методом прогонки (методом Томаса) позволяет синтезировать вычислительные структуры, обеспечивающие значительное ускорение по сравнению с последовательной реализацией. В частности, вычислительная структура, синтезированная на РВС «Тайгета» (8 ПЛИС ХС7УХ485Т), позволила добиться ускорения примерно в 4660 раз.

Применение предложенного метода для преобразования информационного графа решения СЛАУ методом Гаусса-Зейделя для случая, когда имеющегося оборудования не хватает для реализации полного базового подграфа, позволяет избежать разрыва потока данных и добиться ускорения по сравнению с последовательной реализацией. Вычислительная структура, синтезированная на РВС «Тайгета», позволила добиться ускорения примерно в 11000 раз.

Создана программа [10], позволяющая определять необходимую степень распараллеливания информационного графа адаптивного рекурсивного фильтра, исходя из свойств исходного фильтра и размера доступного аппаратного ресурса.

Создана программа на языке программирования SET@L [11], позволяющая выполнять преобразование информационного графа в зависимости от имеющегося вычислительного ресурса.

Использование результатов работы. Результаты диссертационного

исследования внедрены при выполнении ряда работ в Научно-исследовательском

центре Супер-ЭВМ и нейрокомпьютеров (ООО «НИЦ СЭ и НК»), акт от 7 апреля

2022 г., утверждён техническим директором ООО «НИЦ СЭ и НК», и в ПАО

«Радиофизика», акт об использовании от 07 февраля 2022 г., утвержден

генеральным директором ПАО «Радиофизика». Методика синтеза

вычислительной структуры на основе преобразованного графа в зависимости от

имеющихся в наличии вычислительных ресурсов, позволяет создавать

эффективные параллельно-конвейерные программы для РВС. Результаты работы

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

для РВС. Алгоритм определения необходимой степени распараллеливания для

информационных графов адаптивных фильтров и алгоритм преобразования

11

топологии информационного графа с дистрибутивными операциями реализованы в виде программного продукта.

В учебном процессе кафедры интеллектуальных и многопроцессорных систем (ИМС) Института компьютерных технологий и информационной безопасности (ИКТИБ) Южного федерального университета (ЮФУ), акт от «23» мая 2022 г., утвержден директором ИКТИБ ЮФУ. Материалы диссертации использовались в лекционном курсе по дисциплине «ПЛИС-технологии и методы создания эффективных прикладных программ для РВС» (тема № 5 «Soft-процессоры. Программирование soft-процессоров») и в лекционном курсе по дисциплине «Математические методы цифровой обработки сигналов и изображений» (тема №4 «Синтез цифровых фильтров») для подготовки магистров направления подготовки 01.04.02 Прикладная математика и информатика (образовательная программа «Прикладная математика для высокопроизводительных вычислительных систем»).

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

Апробация работы. Основные результаты, представленные в диссертации,

докладывались и обсуждались на всероссийских научно-технических

конференциях: X всероссийской мультиконференции по проблемам управления

(МКПУ-2017), с. Дивноморское, Геленджик, 2017 г., XIV ежегодной молодежной

научной конференции студентов, аспирантов и молодых ученых «Достижения и

перспективы молодых учёных в интересах развития Юга России», 2018 г., 5-й

Всероссийской научно-технической конференции "Суперкомпьютерные

технологии" (СКТ-2018), 2018 г., XV Ежегодной научной конференции молодых

ученых «Вклад молодых ученых Южного макрорегиона в реализацию Стратегии

развития Российской Федерации: цели, задачи, результаты», 2019 г., XII

12

всероссийской мультиконференции по проблемам управления (МКПУ-2019), с. Дивноморское, Геленджик, 2019 г., XVI ежегодной молодежной научной конференции «Юг России: вызовы времени, открытия, перспективы», Таганрог, 2020 г., XVII Ежегодной молодежной научной конференции "Наука и технологии Юга России", 2021.

Наиболее значительными публикациями по теме диссертации являются:

1. Михайлов, Д.В. Алгоритм предсказания устойчивости конвейеризованных адаптивных рекурсивных фильтров в системах управления // Известия ЮФУ. Технические науки. - 2019. - №7 (209). - С. 152-159. DOI: 10.23683/2311-3103-2019-7-152-159 (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Михайловым Д.В. предложен метод определения устойчивости адаптивного рекурсивного цифрового фильтра, учитывающий латентность блоков фильтра и количество доступного оборудования.

2. Михайлов, Д.В. Представление графов с ассоциативными операциями на языке программирования SET@L / Д.В. Михайлов, И.И. Левин, А.И. Дордопуло, И.В. Писаренко // Известия ЮФУ. Технические науки. - 2020. -№ 3 (213). - С. 98-109. DOI: 10.18522/2311-3103-2020-3-98-111 (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Михайловым Д.В., предложен метод преобразования последовательного информационного графа, содержащего ассоциативные операции, в параллельно-конвейерную форму.

3. Михайлов, Д.В. Преобразование некоторых видов последовательных информационных графов в параллельно-конвейерную форму // Известия ЮФУ. Технические науки. - 2020. - №7 (217). - С. 78-93. DOI: 10.18522/2311-3103-20207-78-93 (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Михайловым Д.В. предложен метод преобразования последовательного информационного графа, содержащего ассоциативные и дистрибутивные операции, в параллельно-конвейерную форму.

4. Михайлов, Д.В. Метод определения устойчивости рекурсивного адаптивного конвейеризованного фильтра / Д.В. Михайлов, И.И. Левин // Радиотехника. - 2020. - №3 (6) - С. 5-11. DOI: 10.18127/j00338486-202003(06)-01 (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Михайловым Д.В. на основе метода определения устойчивости адаптивного рекурсивного цифрового фильтра, учитывающий латентность блоков фильтра и количество доступного оборудования, построен алгоритм определения необходимой степени конвейеризации фильтра с учётом его параметров и доступного оборудования.

5. Михайлов, Д.В. Преобразование последовательного информационного графа метода прогонки в параллельную форму // Известия ЮФУ. Технические науки. - 2021. - №7 (224). - С. 177-188. DOI: 10.18522/23113103-2021-7-177-188 (ведущий рецензируемый журнал, входит в перечень ВАК).

В работе Михайловым Д.В. описано применение метода преобразования последовательного информационного графа, содержащего ассоциативные и дистрибутивные операции, в параллельно-конвейерную форму, для распараллеливания информационного графа решения СЛАУ методом прогонки.

6. Mikhailov, D. Resource-independent description of information graphs with associative operations in SET@L programming language / I.I. Levin, D. Mikhailov, A.I. Dordopulo, I. Pisarenko, A. Melnikov // Lecture Notes in Computer Science. - 2021. - Vol. 12942 LNCS. - P. 74-87. DOI: 10.1007/978-3-030-86359-3_6 (научное рецензируемое издание, индексируемое в базе Scopus).

В работе Михайловым Д.В. описан алгоритм преобразования последовательного информационного графа, содержащего ассоциативные операции, в параллельно-конвейерную форму, пригодный для реализации на языке программирования SET@L.

7. Свидетельство о государственной регистрации программ для

ЭВМ № 2022611800, РФ. Программа преобразования топологии

информационных графов с дистрибутивными операциями // Левин И.И.,

14

Михайлов Д.В., Писаренко И.В. Зарегистр. в Реестре программ для ЭВМ 01.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

Вклад Михайлова Д.В. в создание зарегистрированной программы для ЭВМ состоит в разработке алгоритма преобразования информационных графов из последовательной в параллельно-конвейерную форму.

8. Свидетельство о государственной регистрации программ для ЭВМ № 2022612769, РФ. Программа определения необходимой степени конвейеризации адаптивного рекурсивного фильтра // Михайлов Д.В., Семёнов И.С. Зарегистр. в Реестре программ для ЭВМ 28.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

Вклад Михайлова Д.В. в создание зарегистрированной программы для ЭВМ состоит в разработке алгоритма определения необходимой степени конвейеризации адаптивного рекурсивного фильтра.

9. Михайлов, Д.В. К вопросу построения адаптивных рекурсивных фильтров / Д.В. Михайлов, О.В. Ершова, Е.В. Кириченко, Е.А. Семерников // Суперкомпьютерные технологии (СКТ-2018). Материалы 5-й Всероссийской научно-технической конференции. - 2018. - С. 154-157.

В работе Михайловым Д.В., описан метод преобразования последовательного информационного графа, содержащего ассоциативные операции, в параллельно-конвейерную форму.

10. Михайлов, Д.В. Устойчивость конвейеризованных адаптивных рекурсивных фильтров в системах управления // Материалы XII Мультиконференции по проблемам управления (МКПУ-2019): в 4 томах. - 2019. -Г 3. - С. 118-119.

11. Михайлов, Д.В. Алгоритм преобразования линейного информационного графа в параллельную форму / XVI ежегодная молодежная научная конференция «Юг России: вызовы времени, открытия, перспективы». Материалы конференции XVI Ежегодной молодежной научной конференции. -2020. - С 57.

12. Михайлов, Д.В. Преобразование некоторых видов последовательных информационных графов в параллельно-конвейерную форму / XIV Мультиконференция по проблемам управления (МКПУ-2021). Материалы XIV мультиконференции по проблемам управления (МКПУ-2021): в 4 томах. - 2021. -Т. 2. - а 266-269.

Во всех работах, выполненных в соавторстве, определен личный вклад автора.

Личный вклад автора. Все представленные в диссертации результаты получены автором лично.

Положения, выдвигаемые на защиту:

1) существующие методы и средства решения задач с последовательными информационными графами характеризуются низкой производительностью;

2) созданные новые методы позволяют повысить реальную производительность РВС при решении ряда задач, описанных последовательным информационным графом;

3) созданный модернизированный метод распараллеливания информационных графов рекурсивных фильтров, позволяет определить необходимую степень распараллеливания в зависимости от доступного вычислительного ресурса и свойств исходного фильтра, гарантирует устойчивость синтезированного фильтра и может быть применён к адаптивным фильтрам.

Результаты, выносимые на защиту:

1) метод преобразования последовательных информационных графов в параллельно-конвейерную форму, отличающийся от известных возможностью реализовывать вычислительную структуру в зависимости от доступного вычислительного ресурса, от топологии графа и свойств операций;

2) метод распараллеливания информационных графов рекурсивных

фильтров, позволяющий определить необходимую степень распараллеливания в

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

16

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

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

Структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения и списка использованных источников.

В первой главе приведен анализ существующих вычислительно-трудоемких задач, описанных последовательным информационным графом; существующих малогабаритных вычислительных средств традиционной архитектуры, построенных на базе CPU и GPU; специальных вычислительных средств, построенных на базе заказных микросхем ASIC и реконфигурируемых вычислительных систем; методов создания эффективных параллельных программ для РВС.

Рассмотрены проблемы распараллеливания вычислительных задач и ограничения, накладываемые законом Амдала. Показаны способы распараллеливания вычислительных задач: параллельное выполнение и конвейерная обработка - и области их применения.

Было показано, что РВС применяются для решения широкого круга задач и удовлетворяют требованиям к производительности вычислительно-трудоемких задач, описанных последовательным информационным графом, однако существующие средства создания параллельных программ для РВС не позволяют реализовать эффективную вычислительную структуру задачи.

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

способы нахождения минимально необходимого аппаратного ресурса задачи при заданном темпе поступления и обработки данных.

Рассмотрено два случая: когда доступного оборудования хватает для реализации информационного графа целиком, и когда требуется реализация по частям. Для реализации информационного графа по частям рассмотрены два случая: когда вычислительный блок, реализующий операцию, имеет единичную латентность, и когда его латентность больше единицы. Описан переход от преобразованного графа к вычислительной структуре и способ редукции графа в зависимости от доступного вычислительного ресурса для этих двух случаев. В первом случае вычислительная структура будет состоять из двух частей: пирамидальной части и одиночного блока, охваченного обратной связью. Во втором к этим частям добавится ещё одна, осуществляющая окончательное корректное выполнение базовой операции. Вычислено достигаемое ускорение по сравнению с последовательной реализацией вычислительной структуры, для случая: количество входных данных 100000, латентность блока базовой операции 10, количество одновременно реализуемых блоков 100 - ускорение составит около 10900 раз.

Список литературы диссертационного исследования кандидат наук Михайлов Денис Васильевич, 2022 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Колесников А.В., Кириков И.А., Листопад С.В., Румовская С.Б., Доманицкий А.А. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред. А.В. Колесникова. — М.: ИПИ РАН, 2011. — 295 с., ил. — ISBN 978-5-90203088-1 (дата обращения: 17.02.2022). - Текст: электронный.

2. Самарский А.А., Гулин А.В. Численные методы: Учеб. Пособие для вузов. -М.: Наука. Гл. ред. физ-мат. лит., 1989. - 432 с.

3. Каляев И.А. Архитектура семейства реконфигурируемых вычислительных систем на основе ПЛИС / И.А. Каляев, И.И. Левин, Е.А. Семерников. -Текст: непосредственный // Штучний штелект. - 2008. - №3. - С. 663-673.

4. Степаненко С.А. Оценки ускорения вычислений гибридными реконфигурируемыми системами / С.А. Степаненко. - Текст: непосредственный // Известия ЮФУ. Технические науки, 2014. - №12. - С.74-83.

5. ASIC basics tutorial: сайт. - URL: http://www.radio-electronics.com/info/data/semicond/asic/asic.php (дата обращения: 28.05.2021).

- Текст : электронный.

6. ASIC Design Development and Layout: сайт. - URL: https://www.radio-electronics.com/info/data/semicond/asic/designs-development-layout.php (дата обращения: 27.05.2021). - Текст : электронный.

7. Maxfield C. The Design Warrior's Guide to FPGAs / C. Maxfield // - Изд-во «Newnes», 2004. - 542 с. - URL: http://www.mdio-electronics.com/info/data/semicond/asic/asic.php (дата обращения: 28.05.2021).

- Текст : электронный.

8. Иванов А.И. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач / А.И. Иванов, П.М. Коновальчик. - Текст: непосредственный // Информационные технологии. Москва. - 2004. - №2 12. - С. 38-43.

9. Левин И.И. Семейство высокопроизводительных реконфигурируемых вычислительных систем / И.И. Левин. - Текст: непосредственный // Вестник Томского Государственного Университета. - 2008. - №2 (3). С. 77-93.

10. Свидетельство о государственной регистрации программ для ЭВМ № 2022612769, РФ. Программа определения необходимой степени конвейеризации адаптивного рекурсивного фильтра // Михайлов Д.В., Семёнов И.С. Зарегистр. в Реестре программ для ЭВМ 28.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

11. Свидетельство о государственной регистрации программ для ЭВМ № 2022611800, РФ. Программа преобразования топологии информационных графов с дистрибутивными операциями // Левин И.И., Михайлов Д.В., Писаренко И.В. Зарегистр. в Реестре программ для ЭВМ 01.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

12.Can supercomputing technology help us predict how climate change will be? | Digital Future Society: сайт. - URL: https://digitalfuturesociety.com/interviews/can-supercomputing-technology-help-us-predict-how-climate-change-will-be/. (дата обращения: 19.05.2021). -Текст : электронный.

13.Supercomputers Assist in Search for New, Better Cancer Drugs: Researchers use advanced computers to virtually discover and experimentally test new chemotherapy drugs and targets - Science Daily: сайт. - URL: https://www.sciencedaily.com/releases/2017/05/170501131709.htm (дата

обращения: 19.05.2021). - Текст : электронный.

14.Piyush Mehrotra, Supporting Big Data Analytics at the NASA Advanced Supercomputing (NAS) Division / Piyush Mehrotra, L. Harper Pryor. - Текст : электронный // — NASA, 2014. URL:

https://www.exascale.org/bdec/sites/www.exascale.org.bdec/files/whitepapers/me hrotra.pdf (дата обращения: 19.04.2021).

15.Supercomputing the Emergence of Material Behavior: сайт. - URL: https://www.tacc.utexas.edu/-/supercomputing-the-emergence-of-material-behavior (дата обращения: 19.05.2021). - Текст : электронный.

16.'Automated Dermatologist' Detects Skin Cancer With Expert Accuracy, — CNN: сайт. - URL: https://edition.cnn.com/2017/01/26/health/ai-system-detects-skin-cancer-study/index.html (дата обращения: 19.05.2021). - Текст : электронный.

17.Механов, В. Б. Особенности архитектуры универсальных микропроцессоров: учебное пособие / В. Б. Механов. - Пенза : Изд-во ПГУ, 2010. - 176 с. - Текст : непосредственный.

18. Процессоры Intel® Core™ i7: сайт. - URL: https: //www.intel .ru/content/www/ru/ru/products/detail s/processors/core/i7 .html (дата обращения: 19.05.2021). - Текст : электронный.

19. Процессоры Intel® Core™ : сайт. - URL: i9https://www.intel .ru/content/www/ru/ru/products/details/processors/core/i9.htm Цдата обращения: 19.05.2021). - Текст : электронный.

20.David E. Culler. Parallel Computer Architecture - A Hardware/Software Approach / David E. Culler, Jaswinder Pal Singh, Anoop Gupta // Morgan Kaufmann Publishers, 1999. ISBN 1-55860-343-3, pg 15. -Текст : непосредственный.

21.Джон Бэкус. Можно ли освободить программирование от стиля фон-Неймана? Функциональный стиль и соответствующая алгебра программ // Лекции лауреатов премии Тьюринга = Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. — М.: Мир, 1993. — С. 84—158. — 560 с. — 2000 экз. — ISBN 5-03-002130-2.

22.Thomas Scherrer Z80-Family Official Support Page: сайт. - URL: http://www.z80.info/_(дата обращения: 15.01.2020). - Текст: электронный.

23.Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD, and VIA CPUs, By Agner Fog. Technical University of Denmark. Copyright © 1996 - 2021. - p. 442. URL:

https://www.agner.org/optimize/instruction_tables.pdf (дата обращения: 16.01.2021). - Текст : электронный.

24.Bunch J. R. LINPACK Users' Guide / Bunch J.R., Dongarra J.J., Moler G.B., Stewart G.W. // — Society for Industrial and Applied Mathematics, 1979—1993. p. 20. — ISBN 0-89871-172-X. https://epubs.siam.org/doi/pdf/10.1137/1.9781611971811.fm (дата обращения: 16.01.2021). - Текст : электронный.

25.LAPACK —Linear Algebra PACKage: сайт. - URL: http://www.netlib.org/lapack (дата обращения: 19.04.2019). -Текст : электронный.

26.BLAS (Basic Linear Algebra Subprograms) : сайт. - URL: http://www.netlib.org/blas/ (дата обращения: 19.04.2019). -Текст : электронный.

27.Hydro X Series XG7 RGB 20-SERIES GPU Water Block (2080 TI FE) : сайт. -URL: https ://www. corsair. com/ww/en/Categories/Products/Custom-Cooling/Blocks/GPU-Blocks/Hydro-X-Series-XG7-RGB-20-SERIES-GPU-Water-Block-%282080-TI-FE%29/p/CX-9020005-WW (дата обращения:

15.03.2019). - Текст : электронный.

28.TSMC завершила разработку 5-нм техпроцесса — началось рисковое производство: сайт. - URL: https://3dnews.ru/985440_(дата обращения:

21.09.2020). - Текст : электронный.

29.Imec and Cadence Tape Out Industry's First 3nm Test Chip: сайт. - URL: https://www.hpcwire.com/off-the-wire/imec-cadence-tape-industrys-first-3nm-test-chip/Хдата обращения: 10.05.2020). - Текст : электронный.

30.Создан первый в мире процессор с топологией 2 нм: сайт. - URL: https://www.cnews.ru/news/top/2021-05-06_sozdan_pervyj_v_mire_protsessor (дата обращения: 25.05.2021). - Текст : электронный.

31.Гасик М.И. Теория и технология электрометаллургии ферросплавов : Учеб. для студентов вузов, обучающихся по специальности "Металлургия черных металлов и сплавов" / М.И. Гасик, Н.П. Лякишев. - М. : СП Интермет

192

Инжиниринг, 1999. - 764 с. - Текст: электронный // Свойства кремния и его соединений. URL: https://ttvsif.at.ua/page13.html_ (дата

обращения: 19.12.2019).

32.Мировой рекорд разгона AMD побит, снова процессором FX-8150: сайт. -

URL: https://3dnews.ru/news/619131_(дата обращения: 17.04.2021). -

Текст : электронный.

33.AMD Bulldozer Speed Record Broken Again at 8.58GHz: сайт. - URL: https://www.tomshardware.com/news/fx-8150-bulldozer-record-overclocking-speed,13903.html_(дата обращения: 09.02.2021). - Текст : электронный.

34. Процессоры Intel на ядре Nehalem достигнут частоты 10 ГГц уже к 2007 году: сайт. - URL: https: //overclockers.ru/hardnews/show/11644/Processory_Intel_na_yadre_Nehale

m_dostignut_chastoty_10_GGc_uzhe_k_2007_godu_(дата обращения:

15.06.2020). - Текст : электронный.

35. Многоядерные процессоры и грядущая параллельная революция: сайт. -URL: https://www.osp.ru/os/2007/04/4219910_ (дата обращения: 19.08.2019). -Текст : электронный.

36.Корнеев, В.В. Подход к программированию суперкомпьютеров на базе многоядерных мультитредовых кристаллов / В.В. Корнеев. - Текст: непосредственный // Вычислительные методы и программирование. - 2009. - Т. 10.- С. 123-128.

37. Секреты невозможных вычислений на GPU: сайт. - URL: https://habr.com/ru/company/combox/blog/425731/ (дата обращения: 19.02.2020). - Текст : электронный.

38. Аппаратное обеспечение: Гибридные вычислительные системы на основе графических процессоров NVIDIA Tesla: сайт. - URL:

http://www.remmag.ru/admin/upload_data/remmag/11 -1/OT.pdf_(дата

обращения: 19.11.2019). - Текст : электронный.

39.Дефицит видеокарт может продлиться до 2023 года: сайт. - URL: https://www.championat.com/cybersport/news-4324591-deficit-videokart-

193

mozhet-prodlitsya-do-2023-goda.html_^aTa обращения: 12.05.2021). - Текст : электронный.

40. Видеокарты AMD Radeon™ VII: сайт. - URL: https://www.amd.com/ru/products/graphics/amd-radeon-vii_ (дата обращения: 11.05.2021). - Текст : электронный.

41.Игровая видеокарта GEFORCE RTX 2080 Ti: сайт. - URL: https://www.nvidia.eom/ru-ru/geforce/graphics-cards/rtx-2080-ti/_ (дата обращения: 19.06.2021). - Текст : электронный.

42.Validity of the single processor approach to achieving large scale computing capabilities. AFIPS '67 (Spring): Proceedings of the April 18-20, 1967, spring joint computer conference April 1967 Pages 483-485 URL:https://doi.org/10.1145/1465482.1465560_(дата обращения: 27.05.2021).

43. ASIC Design Services: сайт. - URL: https://anysilicon.com/vendor_category/asic_design (дата обращения: 26.05.2021). - Текст : электронный.

44.Maxfield C. Bebop to the Boolean Boogie: An Unconventional Guide to Electronics. Third Edition / C. Maxfield. - Текст: непосредственный // -Newnes, - 2008. - 568 p.

45.Comparing Hardware for Artificial Intelligence: FPGAs vs. GPUs vs. ASICs: сайт. - URL: http://eecatalog.com/intel/2018/07/24/comparing-hardware-for-artificial-intelligence-fpgas-vs-gpus-vs-asics (дата обращения: 27.05.2021). -Текст : электронный.

46.Гузик В.Ф. Реконфигурируемые вычислительные системы : Учеб. пособие / В.Ф. Гузик, И.А. Каляев, И.И. Левин : под общей редакцией И.А. Каляева. -Ростов-на-Дону: Изд-во ЮФУ, - 2016. - 472 с. ISBN 978-5-9275-1980-7. -Текст: непосредственный.

47.Alpha Data, High Performance Reconfigurable Computing: сайт. - URL: http://www.alpha-data.com. (дата обращения: 14.05.2020). -Текст : электронный.

48.DINI Prototyping Products: сайт. - URL: http://www.dinigroup.com_^ara обращения: 14.05.2020). - Текст : электронный.

49. Научно-производственное предприятие «Цифровые решения» : сайт. - URL: http://www.dsol.ruXAara обращения: 14.05.2020). - Текст : электронный.

50.ИНСИС - АО Инструментальные системы: сайт. - URL: http://www.insys.ru (дата обращения: 14.05.2020). - Текст : электронный.

51.МикроЛАБ Системс: сайт. - URL: http://www.mlabsys.ru_(дaтa обращения: 14.05.2020). - Текст : электронный.

52.ЗАО «Скан Инжиниринг Телеком» : сайт. - URL: http://www.setdsp.ru_(дaтa обращения: 14.05.2020). - Текст : электронный.

53. Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров | НИЦ супер-ЭВМ и нейрокомпьютеров: сайт. - URL: http://www.superevm.ru_^ara обращения: 14.05.2020). - Текст : электронный.

54.Intel® FPGAs and Programmable Devices-Intel® FPGAs: сайт. - URL: https://www.altera.com_^ara обращения: 14.05.2020). - Текст : электронный.

55. Доронченко Ю.И. Перспективные высокопроизводительные реконфигурируемые вычислители с иммерсионным охлаждением / И.И. Левин, А.М. Федоров, Ю.И. Доронченко, М.К. Раскладкин. - Текст: непосредственный // Известия ЮФУ. Технические науки - 2020. - №7. - С. 6-19.

56.Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры / И.А. Каляев, И.И. Левин, Е.А. Семерников, В. И. Шмойлов: под общ. ред. И.А. Каляева. - Изд. 2-е, перераб. и доп. - Ростов н/Д : ЮНЦ РАН, 2009. - 344 с. - ISBN 978-5-902982-61-6. - Текст: непосредственный.

57.Левин И.И. Структурно-процедурная организация параллельных вычислений / И.И. Левин. - Текст: непосредственный // Материалы Четвертой Международной научной молодежной школы "Высокопроизводительные вычислительные системы". - Таганрог: Изд-во ТТИ ЮФУ - 2007. - С. 49-68.

58.Каляев А.В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений / А.В. Каляев, И.И.

195

Левин. - Москва: Изд-во "Янус-К", - 2003. - 380 с. - Текст: непосредственный.

59.Mike Santor. The future of instrumentation - the software-designed revolution / December 9th, 2015, Published in Articles: EngineerIT. - URL: https://www.ee.co.za/article/future-instrumentation-software-designed-revolution.html (Дата обращения: 23.06.2021). - Текст : электронный.

60.Тарасов И. Эволюция ПЛИС серии Virtex / И. Тарасов - Текст: непосредственный // Компоненты и технологии. - 2005. - № 1. - С. 90-96.

61. Тарасов И. Анализ предварительных характеристик FPGA «серии 7» фирмы Xilinx / И. Тарасов - Текст: непосредственный // Компоненты и технологии.

- 2010. - № 8. - С. 94-96.

62.Тарасов И. Описание архитектуры FPGA семейств UltraScale компании Xilinx / И. Тарасов - Текст: непосредственный // Компоненты и технологии.

- 2014. - № 2. - С. 38-46.

63. Алексеев К.Н. Реализация обратной кинематической задачи сейсморазведки для микросейсмического мониторинга на реконфигурируемых вычислительных системах в реальном масштабе времени / И.И. Левин, К.Н. Алексеев. - Текст: непосредственный // Известия ЮФУ. Технические науки.

- 2018. - №8. - С. 221-230.

64.Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач / И.А. Каляев, И.И. Левин. - Текст: непосредственный // Информационные технологии и вычислительные системы. - 2011. - №2. - С. 12-22.

65. Гудков В.А. Средства программирования реконфигурируемых многопроцессорных вычислительных систем / В.А. Гудков, А.А. Гуленок, А.И. Дордопуло, Л.М. Сластен. - Текст: непосредственный // Известия ТРТУ. - 2006. - С. 16-20.

66.Бовкун А.В. Методы и алгоритмы автоматической расстановки задержек в вычислительных структурах с обратными связями / А.В. Бовкун, А.А.

Гуленок, В.А. Гудков. - Текст: непосредственный // Вестник УГАТУ. -2013. - Т. 17. - №2 (55). - С. 125-130.

67.Гуленок А.А. Оптимизация блоков перекоммутации в вычислительных структурах параллельных программ для реконфигурируемых вычислительных систем / А.А. Гуленок. - Текст: непосредственный // Десятая Всероссийская Мультиконференция по проблемам управления (МКПУ-2017) материалы 10-й Всероссийской мультиконференции: в 3 томах. Издательство: Южный федеральный университет (Ростов-на-Дону) -2017. - C. 130-131.

68.Доронченко Ю. И. Реализация задачи фильтрации жидкости в пористой среде на реконфигурируемой вычислительной системе / Ю.И. Доронченко, И.И. Левин, А.Г. Коваленко. - Текст: непосредственный // Вычислительные технологии - 2016. - Т. 21. - № 3. - С. 45-55.

69. Катаев О.В. Аппаратно-программный комплекс обработки данных летных испытаний / О.В. Катаев, Э.В. Мельник, И.В. Петручук, Г.Л. Трунов, И.И. Левин, И.М. Пономарев. - Текст: непосредственный // Известия ТРТУ -2002. - № 2 (25). - С. 183-186.

70.Левин И.И. Многопроцессорные рабочие станции с программируемой архитектурой - эффективный инструмент решения сложных научно-технических задач / И.И. Левин, И.М. Пономарев, Р.В. Шахов, А.В. Шматок. - Текст: непосредственный // Известия ТРТУ - 2002. - № 2 (25). -С. 180-183.

71.Дордопуло А.И. Реализация итерационных методов решения систем линейных уравнений в задачах математической физики на реконфигурируемых вычислительных системах / И.И. Левин, А.И. Дордопуло, А.В. Пелипец. - Текст: непосредственный // Вестник ЮжноУральского государственного университета. Серия: Вычислительная математика и информатика - 2016. - Т. 5. - № 4. - С. 5-18.

72.Левин И.И. Решение задачи LU-декомпозиции на реконфигурируемых вычислительных системах: оценка и перспективы / И.И. Левин, А.В.

197

Пелипец, Д.А. Сорокин. - Текст: непосредственный // Известия ЮФУ. Технические науки - 2015. - № 7 (168). - С. 62-70.

73. Левин И.И. Методология распараллеливания по итерациям при решении задач линейной алгебры на реконфигурируемых вычислительных системах / И.И. Левин, А.В. Пелипец. - Текст: непосредственный // Вестник компьютерных и информационных технологий - 2016. - № 7 (145). - С. 34-40.

74.Касаркин А.В. Структурная реализация задачи нахождения всех максимальных клик графа на реконфигурируемых вычислительных системах / А.В. Касаркин, И.И. Левин. - Текст: непосредственный // Вестник компьютерных и информационных технологий - 2018. - № 10 (172). - С. 3-10.

75.Касаркин А.В. Реализация операций добавления и исключения элементов множества на реконфигурируемых вычислительных системах / А.В. Касаркин. - Текст: непосредственный // Десятая Всероссийская мультиконференция по проблемам управления (МКПУ-2017). материалы 10-й Всероссийской мультиконференции: в 3 томах с 2017. - С. 134-137.

76.Титенко Е.А. Схема коммутаций для выполнения парных операций в реконфигурируемом продукционном устройстве / Е.А. Титенко. - Текст: непосредственный // Вестник Воронежского государственного технического университета - 2018. - Т. 14. - № 3. - С. 34-40.

77. Бовкун А.В. Аппаратная реализация докинга лигандов на реконфигурируемых вычислительных системах / А.В. Бовкун, А.И. Дордопуло, Д.А. Сорокин. -Текст: непосредственный // Информатика, вычислительная техника и инженерное образование - 2011. - № 4 (6). - С. 32-48.

78.Дордопуло А.И. Оптимизация вычислительной структуры задач с переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах / А.И. Дордопуло, И.И. Левин, Д.А. Сорокин. -Текст: непосредственный // Известия ЮФУ. Технические науки - 2011. - № 12 (125). - С. 232-238.

79. Левина А.И. Решение задачи сборки молекулы ДНК на реконфигурируемой вычислительной системе / А.И. Левина, Е.Е. Семерникова, Д.А. Сорокин. -Текст: непосредственный // Известия ЮФУ. Технические науки - 2018. - № 8 (202). - С. 204-212.

80. Левин И.И. Реализация алгоритма волновой трассировки на многопроцессорной системе со структурной организацией вычислений. / И.И. Левин, И.М. Пономарев. - Текст: непосредственный //Деп. ВИНИТИ, N 1553-B95. - 1995. - 49 c.

81.Титенко Е.А. Способ и реконфигурируемое однородное устройство реализации продукционных операций / Е.А. Титенко. - Текст: непосредственный // Десятая Всероссийская мультиконференция по проблемам управления (МКПУ-2017). материалы 10-й Всероссийской мультиконференции: в 3 томах - 2017. - С. 157-159.

82.Крипачев А.В. Коммутационная схема параллельных парных перестановок для специализированного продукционного устройства / А.В. Крипачев, Е.А. Титенко, А.Л. Марухленко. - Текст: непосредственный // Известия ЮФУ. Технические науки - 2018. - № 8 (202). - С. 29-38.

83.Титенко Е.А. Схема коммутаций для выполнения парных операций в реконфигурируемом продукционном устройстве / Е.А. Титенко. - Текст: непосредственный // Вестник Воронежского государственного технического университета - 2018. - Т. 14. - № 3. - С. 34-40.

84.D. Chen and D. Singh, "Fractal video compression in OpenCL: An evaluation of CPUs, GPUs, and FPGAs as acceleration platforms," 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC), 2013, pp. 297-304, doi: 10.1109/ASPDAC.2013.6509612.

85.Кофман А. Введение в прикладную комбинаторику / А. Кофман. Под ред. Б.А. Севастьянова. Москва: Изд-во «Наука», Гл. редакция физико-математической литературы, 1975 г. - 480 с. - Текст: непосредственный.

86.Станишевский О.Б. Сверхскоростные СБИС для многопроцессорных вычислительных систем. / О.Б. Станишевский. - Текст: непосредственный //

199

XXX Всесоюзная школа семинар им. М.А. Гаврилова "Развитие теории дискретных систем и проблема логического проектирования СБИС". -Кишинев, - 1988.

87.Коваленко, А.Г. «Препроцессор языка программирования высокого уровня для реконфигурируемых вычислительных систем» : Специальность: 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» : диссертация на соискание учёной степени кандидата технических наук / Коваленко Алексей Геннадьевич; Южный Федеральный Университет. - Таганрог, 2013. 180 с. -Текст: непосредственный.

88.Воробьёв Н.Н. Числа Фибоначчи / Н.Н. Воробьёв. - Наука, 1978. - Т. 39., -144 с. - Текст: непосредственный.

89.Art of Problem Solving: сайт. - URL: https://artofproblemsolving.com/wiki/index.php/Binet%27s_Formula. (дата обращения: 19.05.2021). - Текст : электронный.

90.Рябко Б. Я. Основы современной криптографии для специалистов в информационных технологиях / Б. Я. Рябко, А.Н. Фионов. Научный мир, 2004. - 173 с. - Текст: непосредственный.

91.Гольденберг Л.М. Цифровая обработка сигналов. Справочник / Л.М. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. - М.: Радио и связь, 1985. -312 с. - Текст: непосредственный.

92.Гоулд Б. Теория и применение цифровой обработки сигналов / Л. Рабинер, Б. Гоулд. - М.: Мир, 1987. - 848 с. - Текст: непосредственный.

93.Сергиенко А.Б. Цифровая обработка сигналов / А.Б. Сергиенко. Москва, Санкт-Петербург.: Изд-во "Питер", 2002. - 604 с. - Текст: непосредственный.

94.Левин И.И. Устойчивость конвейерных рекурсивных фильтров / И.И. Левин, Е.А. Семерников. - Текст: непосредственный // Вестник Южного научного центра РАН - 2005. - Т. 1. - № 2. - С. 28-40.

95.Левин И.И. Метод определения устойчивости рекурсивного адаптивного конвейеризованного фильтра / И.И. Левин, Д.В. Михайлов. - Текст: непосредственный // Радиотехника. - 2020. - №3 (6) - С. 5-11.

96.Ильин В.П. Трехдиагональные матрицы и их приложения / В.П. Ильин, Ю.И. Кузнецов. - М.: Наука. Главная редакция физико-математической литературы, 1985г. - 208 с. - Текст: непосредственный.

97.Ортега Джеймс. Введение в параллельные и векторные методы решения линейных систем / Джеймс Ортега. - Москва : Изд-во Мир, 1991. - 367 с. -Текст: непосредственный.

98. Ершова О.В. К вопросу построения адаптивных рекурсивных фильтров / О.В. Ершова, Е.В. Кириченко, Д.В. Михайлов, Е.А. Семерников. - Текст: непосредственный // Суперкомпьютерные технологии (СКТ-2018), Материалы 5-й Всероссийской научно-технической конференции. - Издательство: Южный федеральный университет (Ростов-на-Дону). - 2018. - С. 154-157.

99.Михайлов Д.В. Устойчивость конвейеризованных адаптивных рекурсивных фильтров в системах управления / Д.В. Михайлов. - Текст: непосредственный // XII Мультиконференция по проблемам управления (МКПУ-2019), материалы XII Мультиконференции по проблемам управления (МКПУ-2019): в 4 томах. - Издательство: Южный федеральный университет (Ростов-на-Дону). - 2019. - С. 118-119.

100. Михайлов Д.В. Алгоритм предсказания устойчивости конвейеризованных адаптивных рекурсивных фильтров в системах управления / Д.В. Михайлов. - Текст: непосредственный // Известия ЮФУ. Технические науки. - 2019. - №7 (209). - С. 152-159.

101. Михайлов Д.В. Алгоритм преобразования линейного информационного

графа в параллельную форму / Д.В. Михайлов. - Текст: непосредственный //

XVI ежегодная молодежная научная конференция «Юг России: вызовы

времени, открытия, перспективы», Материалы конференции XVI Ежегодной

молодежной научной конференции. Ростов-на-Дону. - Издательство:

Федеральное государственное бюджетное учреждение науки "Федеральный

201

исследовательский центр Южный научный центр Российской академии наук" (Ростов-на-Дону). - 2020. - С. 57.

102. Дордопуло А.И. Представление графов с ассоциативными операциями на языке программирования SET@L / А.И. Дордопуло, И.И. Левин, Д.В. Михайлов, И.В. Писаренко. - Текст: непосредственный // Известия ЮФУ. Технические науки. - 2020. - №3 (213). - С. 98-109.

103. Михайлов Д.В. Преобразование некоторых видов последовательных информационных графов в параллельно-конвейерную форму / Д.В. Михайлов. - Текст: непосредственный // Известия ЮФУ. Технические науки. - 2020. - №7 (217). - С. 78-93.

МИХАЙЛОВ ДЕНИС ВАСИЛЬЕВИЧ

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

Таганрог - 2022

УТВЕРЖДАЮ Технический директор ООО «НИЦ СЭ и НК»,

к.т.н.

Ю.И. Доронченко

апреля 2022 г.

АКТ

о внедрении результатов кандидатской диссертации «Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом» конструктора 2 категории Общества с ограниченной ответственностью

«НИЦ супер-ЭВМ и нейрокомпьютеров» (ООО «НИЦ СЭ и НК») Михайлова Дениса Васильевича

Комиссия в составе председателя, заместителя директора по разработкам, к.т.н. Катаева О.В., и членов комиссии: начальника отдела, к.т.н. Сорокина Д.А., начальника отдела, к.т.н. Раскладкина М.К., составила настоящий акт о том, что в разработках Общества с ограниченной ответственностью «НИЦ супер-ЭВМ и нейрокомпьютеров» (ООО «НИЦ СЭ и НК») внедрены следующие результаты диссертации Михайлова Дениса Васильевича на тему «Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом»:

1. Алгоритм преобразования последовательных информационных графов в параллельно-конвейерную форму, позволяющий реализовывать вычислительную структуру в зависимости от доступного вычислительного ресурса, от топологии графа и свойств операций.

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

Указанные результаты диссертации Михайлова Д.В. были внедрены при реализации параллельно-конвейерных программ, выполняющих

обработку данных.

Основываясь на результатах диссертации совместно с Михайловым Д.В. созданы следующие программы:

- программа преобразования топологии информационных графов с дистрибутивными операциями (свидетельство о государственной регистрации программ для ЭВМ № 2022611800, РФ). Левин И.И., Михайлов Д.В., ГТисаренко И.В. Зарегистр. в Реестре программ для ЭВМ 01.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров»;

- программа определения необходимой степени конвейеризации адаптивного рекурсивного фильтра (свидетельство о государственной регистрации программ для ЭВМ №2022612769, РФ). Михайлов Д.В., Семёнов И.С. Зарегистр. в Реестре программ для ЭВМ 28.02.2022 г. Правообладатель: ООО «НИЦ супер-ЭВМ и нейрокомпьютеров».

Внедрение разработанных соискателем методов и средств позволило повысить удельную производительность (отношение производительности системы к задействованному аппаратному ресурсу РВС) прикладных параллельно-конвейерных программ за счет оптимизации топологии информационного графа, а именно при решении задачи вычисления автокорреляционной матрицы - более чем в 2 раза.

ПРЕДСЕДАТЕЛЬ КОМИССИИ

К.Т.Н.,

Заместитель директора по разработкам ООО «НИЦ СЭ и НК»,

ЧЛЕНЫ КОМИССИИ

Начальник отдела ООО «НИЦ СЭ и НК», к.т.н.

М.К. Раскладкин

к.т.н.

Начальник отдела ООО «НИЦ СЭ и НК»,

Д.А. Сорокин

МИХАЙЛОВ ДЕНИС ВАСИЛЬЕВИЧ

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

Таганрог - 2022 208

УТВЕРЖДАЮ Генеральный директор ПАР «Радиофизика»

/ ¿"¿Левитан Б.А.

2022 г.

АКТ

о внедрении результатов кандидатской диссертации «Методы создания

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

информационным графом» конструктора 2 категории Общества с ограниченной ответственностью

«НИЦ супер-ЭВМ и нейрокомпьютеров» (ООО «НИЦ СЭ и НК») Михайлова Дениса Васильевича

Комиссия в составе Топчиева С.А. (председатель), Фролова С.В., Смольниковой О.Н. (члены комиссии), составила настоящий акт о том, что в разработках Публичного акционерного общества «Радиофизика» (ПАО «Радиофизика») внедрены следующие результаты диссертации Михайлова Дениса Васильевича на тему «Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом».

1. Алгоритм распараллеливания информационных графов адаптивных рекурсивных фильтров, позволяющий определить необходимую степень распараллеливания в зависимости от доступного вычислительного ресурса и свойств исходного фильтра, и гарантирующий устойчивость синтезированного фильтра.

2. Вычислительные структуры, синтезированные на основе преобразованных в параллельно-конвейерную форму информационных графов адаптивных рекурсивных фильтров.

Указанные результаты диссертации Михайлова Д.В., безвозмездно переданные в ПАО «Радиофизика», были использованы при создании прикладных программ для систем цифровой обработки сигналов в рамках проекта ОКР «Развязка».

МИХАЙЛОВ ДЕНИС ВАСИЛЬЕВИЧ

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

Таганрог - 2022 211

УТВЕРЖДАЮ Директор

Института компьютерных технологий и информационной безопасности ^федерального университета

Г.Е. Веселое 2022 г.

АКТ

об использовании результатов кандидатской диссертации Михайлова Дениса Васильевича в учебном процессе кафедры интеллектуальных и многопроцессорных систем Института компьютерных технологий и информационной безопасности Южного федерального университета

Комиссия в составе:

председателя Никитиной A.B.

и членов комиссии Горбунова A.B., Чкана A.B., Механцева Б.Е.

составили настоящий акт о том, что результаты диссертационной работы «Методы создания параллельно-конвейерных программ для задач с последовательным информационным графом»,

представленной на соискание ученой степени кандидата технических наук, использованы в учебном процессе кафедры интеллектуальных и многопроцессорных систем (ИМС) Института компьютерных технологий и информационной безопасности (ИКТИБ) Южного федерального университета (ЮФУ).

Настоящий акт подтверждает, что в учебном процессе кафедры ИМС ИКТИБ ЮФУ используются следующие научно-теоретические и практические результаты кандидатской диссертации Михайлова Д.В.:

- метод преобразования последовательных информационных графов в параллельно-конвейерную форму;

- метод распараллеливания информационных графов адаптивных рекурсивных фильтров, позволяющий определить необходимую степень распараллеливания в зависимости от доступного вычислительного ресурса и свойств исходного фильтра, и гарантирующий устойчивость синтезированного фильтра;

- программа преобразования топологии информационных графов с дистрибутивными операциями (свидетельство о государственной регистрации программ для ЭВМ № 2022611800, РФ). Указанные материалы используются в лекционном курсе по дисциплине «ПЛИС-технологии и методы создания эффективных прикладных программ для РВС» (тема № 5 «Бой-процессоры. Программирование эой-процессоров») и в лекционном курсе по дисциплине «Математические методы цифровой обработки сигналов и изображений» (тема №4 «Синтез цифровых фильтров») для подготовки магистров направления подготовки 01.04.02 Прикладная математика и информатика (образовательная программа «Прикладная математика для высокопроизводительных вычислительных систем»).

Председатель комиссии:

Руководитель образовательной программы «Прикладная математика для

высокопроизводительных вычислительных систем»

д.т.н., доцент

профессор ИКТИБ ИТА ЮФУ,

Члены комиссии:

Зам. директора ИКТИБ ИТА ЮФУ по учебной работе, к.т.н., доцент

Лектор дисциплины

«Математические методы цифровой обработки сигналов и изображений», доцент ИКТИБ ИТА ЮФУ,

к.т.н.

Лектор дисциплины «ПЛИС-технологии и методы создания эффективных прикладных программ для РВС», доцент ИКТИБ ИТА ЮФУ,

^ХМ ! 7 Б.Е. Механцев

к.пед.н.