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

• Алексеев Кирилл Николаевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Алексеев Кирилл Николаевич

ВЕДЕНИЕ

1. МЕТОДЫ И СРЕДСТВА РЕШЕНИЯ ВЫЧИСЛИТЕЛЬНО-ТРУДОЕМКИХ ЗАДАЧ РЕАЛЬНОГО ВРЕМЕНИ

1.1 Вычислительные задачи реального времени

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

1.3 Вычислительные системы специального назначения и реконфигурируемые вычислительные системы

1.4 Методы и средства программирования РВС

1.5 Принципы решения задач реального времени на реконфигурируемых вычислительных системах

1.6 Выводы

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

2.1 Алгоритм методики синтеза параллельно-конвейерных программ для решения на РВС задач реального времени с функционально-регулярным информационным графом

2.2 Применение методики решения задач реального времени с функционально-регулярным информационным графом на примере задачи прогнозирования кратных волн алгоритмом SRMP

2.2.1 Математическая постановка задачи прогнозирования кратных волн алгоритмом SRMP

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

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

2.3.1 Описание информационного графа операции сортировки массивов данных

2.3.2 Определение наиболее эффективного алгоритма сортировки для заданного темпа поступления и обработки данных

2.4 Выводы

3. МЕТОДИКА СИНТЕЗА ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНЫХ ПРОГРАММ

ДЛЯ РЕШЕНИЯ ЗАДАЧ РЕАЛЬНОГО ВРЕМЕНИ С ФУНКЦИОНАЛЬНО-НЕРЕГУЛЯРНЫМ ИНФОРМАЦИОННЫМ ГРАФОМ

3.1 Алгоритм методики синтеза параллельно-конвейерных программ для решения на РВС задач реального времени с функционально -нерегулярным информационным графом

3.2 Применение методики для решения задач реального времени с функционально-нерегулярным информационным графом на примере

обратной кинематической задачи сейсморазведки

3.2.1 Синтез эффективной вычислительной структуры обратной кинематической задачи сейсморазведки

3.3 Применение методики для решения задач реального времени с функционально-нерегулярным информационным графом на примере решения задачи кодирования потока данных методом Хаффмана

3.3.1 Построение информационного графа задачи кодирования потока методом Хаффмана

3.3.2 Синтез эффективной вычислительной структуры задачи кодирования потока методом Хаффмана

3.4 Выводы

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

РЕШЕНИЯ ЗАДАЧ РЕАЛЬНОГО ВРЕМЕНИ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

4.1 Описание разработанных программных средств

4.2 Синтез параллельно-конвейерной программы для решения обратной кинематической задачи сейсморазведки

4.3 Синтез параллельно-конвейерной программы для решения задачи кодирования потока методом Хаффмана

4.4 Выводы

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

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

ВЕДЕНИЕ

В настоящее время существует множество вычислительно-трудоемких задач реального времени, решение которых необходимо получить за короткий заданный промежуток времени, а обработку входных данных необходимо выполнять в темпе их поступления. К таким задачам, например, относятся: кодирование и декодирование мультимедийного потока и телекоммуникационных данных [1-3], обнаружение подвижных объектов и радиолокация [4-7], прогнозирование процессов в опережающем масштабе времени [8], защита данных в компьютерных сетях и шифрование информационного потока [9], вычислительные задачи в атомной энергетике [10, 11], задачи обработки геофизических данных [12]. Зачастую необходимость решения подобных задач возникает на бортах подвижных объектов или на удаленных промышленных участках.

Для решения большинства задач реального времени применяются малогабаритные ЭВМ и рабочие станции, основным вычислительным компонентом которых являются универсальные процессоры (CPU) [13]. Однако подобные устройства не позволяют достигать необходимого уровня производительности при решении вычислительно-трудоемких задач, для которых характерно большое количество межпроцессорных обменов и обменов данными между вычислительными элементами и памятью, так как в данных условиях существенно уменьшается реальная производительность большинства вычислительных машин традиционной архитектуры [14-16].

В настоящее время широко распространены графические ускорители (GPU) в виде плат расширения PCIe или выполненные в виде COM-модулей [17]. Архитектура GPU предназначена для выполнения малого количества команд над большими потоками данных. Малогабаритные гибридные многопроцессорные вычислительные системы (МВС), основными вычислительными элементами которых являются CPU и GPU, способны выполнять некоторые специализированные вычисления намного быстрее универсальных

вычислительных средств, однако при обеспечении решения задач в формате двойной точности по стандарту IEEE 754 эффективность GPU резко снижается [15, 18]. Использование в одном вычислительном узле нескольких ускорителей для ряда задач также приводит к уменьшению реальной производительности системы из-за необходимости организации интенсивных межпроцессорных обменов и синхронизации выходных потоков данных различных модулей [19]. Таким образом, применение гибридных систем будет эффективно не для всех вычислительно-трудоемких задач реального времени, а только для определенных специализированных вычислений, не требующих больших пересылок данных.

Задачи реального времени могут эффективно решаться благодаря применению специализированных заказных микросхем (ASIC) [20, 21], созданных для решения определенной задачи. Однако процесс разработки таких микросхем является очень трудоемким и, как следствие, занимает значительно больше времени по сравнению с программированием вычислителей традиционной архитектуры [20, 22]. Недостатком таких систем является высокая стоимость заказных микросхем, вследствие чего их применение экономически выгодно, в первую очередь, для изделий массового потребления [23, 24]. Поскольку вычислительно-трудоемкие задачи реального времени зачастую необходимо решать в областях, не связанных с выпуском массовых продуктов, стоимость специализированных вычислителей, построенных на базе заказных кристаллов, намного выше стоимости универсальных вычислительных систем и разработки для них программного обеспечения (ПО). Другим недостатком является узкая направленность вычислительных систем, построенных на базе заказных микросхем, что в случае изменения используемых алгоритмов решения задачи приводит необходимости разрабатывать новые микросхемы [20].

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

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

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

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

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

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

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

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

Объектом исследований является системное программное обеспечение реконфигурируемых вычислительных систем.

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

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

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

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

2) провести анализ существующих методов и средств создания параллельно-конвейерных программ для РВС;

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

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

5) разработать синтезатор параллельно-конвейерных программ для решения задач реального времени на РВС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- при создании комплекса системного программного обеспечения для высокопроизводительных реконфигурируемых вычислительных систем, НИОКР, шифр «Поколение», №НЦ-160217 от 12.08.2016;

- при реализации параллельно-конвейерных программ, выполняющих обработку данных в режиме реального времени в рамках СЧ ОКР по созданию

системы обработки сетевого трафика, шифр «Ликование-СН-Н/Т» (контракт №16/14-р от 16.09.2016);

- при реализации модельных параллельно-конвейерных программ в рамках работы по созданию высокопроизводительного настольного реконфигурируемого компьютера, шифр «Терциус», №НЦ-170210 от 01.12.2017;

Также результаты диссертации внедрены в научно-производственном объединении «СОЮЗНЕФТЕГАЗСЕРВИС» (ООО НПО «СНГС») при выполнении НИОКР № гос. рег. 115092410004 по договору № 2-26-06-СКИФ/НИР/15 от 22.06.2015, инв. № 001Ю/15, Таганрог, НИЦ СЭ и НК, шифр «Нефть» , 2015. - 275 с.

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

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: XII ежегодной научной конференции студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону, 2016 г.; 4-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2016)», с. Дивноморское, Геленджик, 2016 г.; XIII ежегодной молодежной научной конференции студентов, аспирантов и молодых ученых «Исследования и разработки передовых научных на-правлений», Ростов-на-Дону, 2017 г.; X всероссийской мультиконференции по проблемам управления (МКПУ-2017), с. Дивноморское, Геленджик, 2017 г.; XIV ежегодной молодежной научной конференции студентов, аспирантов и молодых ученых «Достижения и перспективы молодых ученых в интересах развития Юга России», Ростов-на-Дону, 2018 г.; 5-й Всероссийской научно-технической конференции

«Суперкомпьютерные технологии (СКТ-2018)», с. Дивноморское, Геленджик, 2018 г.; международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2019)», Калининград, 2019 г.; XV ежегодной научной конференции молодых ученых «Вклад молодых ученных южного макрорегиона в реализацию стратегии развития Российской федерации: цели, задачи, результаты», Ростов-на-Дону, 2019 г.; XV международной научно-технической конференции "Dynamic of Technical Systems", Ростов-на-Дону, 2019 г.

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

1. Levin I., Dordopulo A., Gudkov V., Gulenok A., Bovkun A., Yevstafiyev G., Alekseev K. Software Development Tools for FPGA-Based Reconfigurable Systems Programming // In: Communications in Computer and Information Science (CCIS), vol 1129, pp 625-640, Springer, Cham. 10 December 2019, DOI: https://doi.org/10.1007/978-3-030-36592-9_51, Publisher ISBN978-3-030-36591-2, https://link.springer.com/chapter/10.1007/978-3-030-36592-9_51 (научное рецензируемое издание, индексируемое в базе Scopus);

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

2. Alekseev K., Levin I., Sorokin D. Application of the methodology of creating parallel-pipeline programs for reconfigurable computer systems on the example of implementation of surface-related multiple prediction problem in real time // In: XV International Scientific-Technical Conference "Dynamic of Technical Systems" (DTS-2019) AIP Conf. Proc. 2188, 050039-1-050039-10; https://doi.org/10.1063/1.5138466 Published by AIP Publishing. 978-0-7354-1935-3/$30.00 (научное рецензируемое издание, индексируемое в базе Scopus);

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

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

3. Писаренко И.В., Алексеев К.Н., Мельников А.К. Ресурсонезависимое представление сортирующих сетей на языке программирования Set@l // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2019. - № 11 (185). - С. 53-60. DOI: 10.14489/vkit.2019.11.pp.053-060. http://vkit.ru/index. php/ current-issue-rus/857-053-060. (ведущий рецензируемый журнал, входит в перечень ВАК);

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

4. Алексеев К.Н., Левин И.И. Реализация обратной кинематической задачи сейсморазведки для микросейсмического мониторинга на реконфигурируемых вычислительных системах в реальном масштабе времени // Известия ЮФУ. Технические науки. - Ростов/Д: Изд-во ЮФУ, 2018. - №8 (202). - С. 221-231. DOI 10.23683/ 2311-3103-2018-8-221-230. ISSN 1999-9429, http://izv-tn.tti.sfedu.ru/in-dex.php/izv_tn/article/view/42/29 (ведущий рецензируемый журнал, входит в перечень ВАК);

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

задачи, выполнен расчет требуемого аппаратного ресурса и получена оценка эффективности предложенной реализации.

5. Алексеев К.Н., Левин И.И., Сорокин Д.А. Структурно-процедурная реализация на реконфигурируемых вычислительных системах кодирования Хаффмана в реальном масштабе времени // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2018. - № 9. - С. 3-10. ISSN 1810-7206. (DOI: 10.14489/vkit.2018.09.pp.003-010), http://www.vkit.ru/index.php/current-issue-rus/751-003-010 (ведущий рецензируемый журнал, входит в перечень ВАК);

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

6. Алексеев К.Н., Сорокин Д.А., Матросов А.Ю., Семерникова Е.Е. Структурно-процедурная реализация алгоритма прогнозирования кратных волн на ПЛИС // Известия ЮФУ. Технические науки. - Ростов/Д.: Изд-во ЮФУ, 2016. - № 12. - С. 16-28 (ведущий рецензируемый журнал, входит в перечень ВАК);

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

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

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

8. Алексеев К.Н. Методика синтеза параллельно-конвейерных программ для РВС при решении задач класса реального времени с функционально регулярным информационным графом // Материалы XV ежегодная научная конференция молодых ученых «Вклад молодых ученных южного макрорегиона в реализацию стратегии развития Российской федерации: цели, задачи, результаты», г. Ростов-на-Дону, 15.04.2019 - 26.04.2019 гг. - г. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2019. - С. 90.

9. Alekseev K.N., Sorokin D.A., Matrosov A.Y., Sememikova E.E. Real-time Implementation of the Problem of Surface-Related Multiple Prediction on RCS // In: Parallel Computational Technologies (13th International Conference, PCT 2019), Immanuel Kant Baltic Federal University, Kaliningrad, Russia, April 2-4, 2019. - Pp. 91 -98. http://ome-ga. sp.susu.ru/pavt2019/short/145.pdf

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

10. Алексеев К.Н. Построение и обработка многомерных структур данных типа «дерево» в режиме реального времени на РВС // Материалы 5-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2018)»: в 2 т. - Ростов/Д; Таганрог: Изд-во ЮФУ, 2018. - Т. 1. -С. 123-126. ISBN 978-5-9275-2834-9 (Т. 1).

11. Алексеев К.Н. Методика синтеза параллельных программ для решения задач реального масштаба времени на РВС // Материалы XIV ежегодной

молодежной научной конференции студентов, аспирантов и молодых ученых «Достижения и перспективы молодых ученых в интересах развития Юга России»: тезисы докладов (г. Ростов-на-Дону, 12-26 апреля 2018 г.). - Ростов н/Д: Изд-во ЮНЦ РАН, 2018. - 222 с. - С. 65. ISBN 978-5-4358-0167-5.

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Алексеев Кирилл Николаевич, 2020 год

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

1. Кривошеев В.И. Современные методы цифровой обработки сигналов (цифровой спектральный анализ) // Учебно-методический материал по программе повышения квалификации «Современные системы мобильной цифровой связи, проблемы помехозащищенности и защиты информации». Нижний Новгород, 2006. - 117 с.

2. Цифровое телевизионное вещание: везде и всегда, для всех и для каждого // Сборник под редакцией д.т.н. Бутенко В.В. - Москва: Научно-исследовательский институт радио (НИИР), 2014. - 481 с.

3. Лайнос Р. Цифровая обработка сигналов: Второе издание. Пер. с англ. -Москва: «Бином-Пресс», 2006. - 656с.

4. Распоряжение Правительства Российской Федерации от 3 декабря 2014 г. N 2446-р г. Москва [электронный ресурс]. - Режим доступа: http://www.apkbg.ru/files/2446.pdf (Дата обращения: 11.12.2018).

5. Петров В.В., Коробкин В.В., Сивенков А.Б. Комплексные системы безопасности современного города: учебное пособие. - Ростов-на-Дону-Таганрог: Издательство ЮФУ, 2017. - 157 с.

6. Масленникова И.Л., Чистова Г.К., Акиншин Р.Н. Возможности вычислительной техники и обработки информации радиолокационных систем // Материалы III Всероссийской конференции «Радиолокация и радиосвязь» - ИРЭ РАН, 2009. - С. 897 - 902.

7. Захарова Л.Н., Захаров А.И., Сорочинский М.В., Котельникова В.А., Рябоконь Г.П., Леонов В.М. Совместный анализ данных оптических и радиолокационных сенсоров: возможности и ограничения // Радиотехника и электроника, 2011. - Т. 56. - № 1. - С. 5-19

8. Sukhinov A.I., МкШпа A.V., Chistyakov A.E., Semenyakina A.A. Practical Aspects of the Implementation of the Parallel Algorithm for Solving the Ctenophore Population Interaction Problem in the Azov Sea // 12th International Conference Parallel Computational Technologies (PCT'2018), Don State

Technical University, Rostov-on-Don, Russia, April 2-6, 2018. - Pp. 185-196. http://omega.sp. susu.ru/pavt2018/short.html.

9. Жданов, О.Н., Золотарев, В.В. Методы и средства криптографической защиты информации: Учебное пособие // СибГАУ. - Красноярск, 2007. - 217 с.

10. Дистанционный мониторинг обстановки окружающей среды вокруг атомных электростанций с космических аппаратов [электронный ресурс]. - Режим доступа: http://sovzondconference.ru/distancionnyj-monitoring-obstanovki-okruzhajushhej (Дата обращения: 11.12.2018).

11. Скалозубов В.И., Билей Д.В., Габлая Т.В., и др. Развитие и оптимизация систем контроля атомных электростанций с ВВЭР // НАН Украины, Институт проблем безопасности АЭС. - Чернобыль, 2008. - 512 с.

12. Внедрение и использование цифровых технологий в энергетике, исходя из принципов экономической целесообразности и повышения доступности энергетической инфраструктуры и распределенной энергетики. 2018 [электронный ресурс]. - Режим доступа: https://minenergo.gov.ru/node/10877 (дата обращения: 14.11.2018).

13. Воройский Ф.С. Информатика. Новый систематизированный толковый словарь-справочник (Введение в современные информационные и телекоммуникационные технологии в терминах и фактах). 3-е изд., - Москва: ФИЗМАТЛИТ, 2003. - 760 с.

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

15. Степаненко С.А. Мультипроцессорные среды суперЭВМ. Масштабирование производительности. - Москва: ФИЗМАТЛИТ, 2016. -312 с.

16. Курин Е.А., Денисов М.С. Применение высокопроизводительных вычислительных систем в задаче подавления многократно отраженных волн-помех // Технологии сейсморазведки. - 2011. - №4. - С. 35-40.

17. Dongarra J.J. High performance computing systems: status and outlook // Cambridge University Press, 2012. - 94 с.

18. Ефремов А.А. Проблемы вычислений с высокой точностью при использовании графических ускорителей NVIDIA // Молодой ученый. Математика. - Казань, 2015. - №11 (91). - С. 45-48.

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

20. Maxfield C. The Design Warrior's Guide to FPGAs - Изд-во «Newnes», 2004. -542 с.

21. ASIC basics tutorial [электронный ресурс]. - Режим доступа: http://www.radio-electronics.com/info/data/semicond/asic/asic.php (дата обращения: 06.12.2018).

22. Comparing Hardware for Artificial Intelligence: FPGAs vs. GPUs vs. ASICs [электронный ресурс]. - Режим доступа: http://eecatalog.com/intel/2018/07/24/comparing-hardware-for-artificial-intelligence-fpgas-vs-gpus-vs-asics (дата обращения: 06.12.2018).

23. Maxfield C. Bebop to the Boolean Boogie: An Unconventional Guide to Electronics. Third Edition - Изд-во «Newnes», 2008. - 568 с.

24. ASIC Design Development and Layout [электронный ресурс]. - Режим доступа: https://www.radio-electronics.com/info/data/semicond/asic/designs-development-layout.php (дата обращения: 06.12.2018).

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

26. Levin I.I., Dordopulo A.I. Programming methods of hybrid reconfigurable computer systems // Parallel Computational Technologies (12th International Conference, PCT 2018, Rostov-on-Don, Russia, April 2-6, 2018. - Pp. 49-64.

27. Язык высокого уровня COLAMO [электронный ресурс]. - Режим доступа: http://superevm.ru/index.php?page=yavu-colamo (дата обращения: 20.12.2018).

28. Yamada H. Real-time computation and recursive functions not real-time computable. IRE Trans- Electronic Computers, 1962. - Т. 11. - № 6. С. 753-760.

29. Марченков С.С., Матросов В.Л. Сложность алгоритмов и вычислений. Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет. Том 16. Москва: ВИНИТИ, 1979. - С. 103-149.

30. Толковый словарь по вычислительным системам / Под ред. Иллингуорта В. и др.: Пер. с англ. Белоцкого А.К. и др.; Под ред. Масловского Е.К. - Москва: Машиностроение, 1989. - 568 с.

31. English-Russian dictionary of computers [электронный ресурс]. - Режим доступа: https://slovar-vocab.com/english-russian/computer-vocab.html (дата обращения: 13.12.2018).

32. Воройский Ф.С. Информатика. Энциклопедический систематизированный словарь-справочник: введение в современные информационные и телекоммуникационные технологии в терминах и фактах. - М.: Физматлит, 2006. - 767 с.

33. Кочергин В.И. Большой англо-русский толковый научно-технический словарь компьютерных информационных технологий и радиоэлектроники: В 9-ти томах (Т.1 - 460 с., Т.2 - 436 с., Т.3 - 511 с., Т.4 - 407 с., Т.5 - 398 с., Т.6 -488 с., Т.7 - 587 с., Т.8 - 399 с., Т.9 - 456 с.). - Томск: Изд-во Томского Университета, 2016.

34. Albers S. Online algorithms: a survey // Springer-Verlag. Mathematical Programming, 2003. - № 7. - С. 1-26.

35. Сорокин С. Системы реального времени // СТА, 1997, №2, С. 22-29.

36. Хакерская атака [электронный ресурс]. - Режим доступа: https://ru.wikipedia.org/wiki/DoS-атака (Дата обращения: 10.12.2018)

37. Отчет Cisco по информационной безопасности за 2018 год [электронный ресурс]. - Режим доступа: https://www.cisco.com/c/dam/global/ru_ru/assets/offers/assets/cisco_2018_acr_ru. pdf (Дата обращения: 10.12.2018).

38. Cisco [электронный ресурс]. - Режим доступа: https://www.cisco.com/ (Дата обращения: 10.12.2018).

39. Netscout [электронный ресурс]. - Режим доступа: https://www.netscout.com/ (Дата обращения: 10.12.2018).

40. LDA Tecnologies [электронный ресурс]. - Режим доступа: http://www.ldatech.com/ (Дата обращения: 10.12.2018).

41. WatchGuard Technologies [электронный ресурс]. - Режим доступа: https://www.watchguard.com/ (Дата обращения: 10.12.2018).

42. Altell [электронный ресурс]. - Режим доступа: http://www.altell.ru/ (Дата обращения: 10.12.2018).

43. Ильченко Д.Н. Методы и средства оптимизации автоматных моделей поиска информационных структур в потоке данных для реализации на реконфигурируемых вычислительных системах: диссертация ... кандидата технических наук: 05.13.11 / Ильченко Дмитрий Николаевич; [Место защиты: ФГАУ ВПО "Южный федеральный университет"].- Ростов-на-Дону, 2014.200 с.

44. Электронная подпись [электронный ресурс]. - Режим доступа: https://m.wikipedia.org/wiki/Электронная_подпись (Дата обращения: 10.12.2018).

45. Ватолин Д., Ратушняк А., Смирнов В., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - Москва: Издательство ДИАЛОГ-МИФИ, 2003. - 384 с.

46. Алексеев К.Н., Сорокин Д.А., Левин И.И. Структурно-процедурная реализация на реконфигурируемых вычислительных системах кодирования Хаффмана в реальном масштабе времени // Вестник компьютерных и информационных технологий, 2018. - №9. - С. 3-9.

47. Обертов Д.Е. Спектральный анализ данных с акселерометров для задач обнаружения и идентификации транспортных средств // Научно-технический вестник информационных технологий, механики и оптики. - №6 (82), 2012. -С. 44-50.

48. Nvidia self-driving safety report 2018 [электронный ресурс]. - Режим доступа: https://www.nvidia.com/content/dam/en-zz/Solutions/self-driving-cars/safety-report/NVIDIA-Self-Driving-Safety-Report-2018.pdf (Дата обращения: 11.12.2018).

49. Лазарева Т.Я., Мартемьянов Ю.Ф. Основы теории автоматического управления: Учебное пособие. - 2-е изд., Тамбов: Изд-во ТГТУ, 2004. - 352 с.

50. Ендачев Д.В. Прогнозирование характеристик криволинейного движения беспилотного автомобиля: диссертация ... кандидата Технических наук: 05.05.03 / Ендачев Денис Владимирович; [Место защиты: ФГУП Центральный ордена Трудового Красного Знамени научно-исследовательский автомобильный и автомоторный институт НАМИ], 2016. -185 с.

51. Smith S.W. The scientist and engineer's guide to digital signal processing. 2th ed., San Diego: California Technical Publishing, 1999. - 857 с.

52. Каляев И.А., Коробкин В.В., Кухаренко А.П., Макеев В.В., Поваров В.П., Румянцев К.Е. Инновационные разработки Южного научного центра РАН в области создания систем управления для атомной энергетики // Инновации, 2006. - №10. - С. 65-68.

53. Коробкин В.В., Поваров В.П. Информационно-управляющая система машины перегрузочной нового поколения // Известия вузов. Ядерная энергетика. - №3. - 2017. - С. 98-107.

54. Шмаков Ф.Д. Методика обработки и интерпретации данных наземного микросейсмического мониторинга ГРП // Технологии сейсморазведки. -Новосибирск: Изд-во ГЕО, 2012. - № 3. - С. 65-72.

55. Шмаков Ф.Д. Программный комплекс решения обратных кинематических задач микросейсмического мониторинга // Вестник НГУ. Серия: Информационные технологии. - Новосибирск: Изд-во НГУ, 2010. - Том № 8. - № 2. - С. 34-42.

56. Курин Е.А. Сейсморазведка и суперкомпьютеры. // Вычислительные методы и программирование. - 2011. - №12. - С. 34-39.

57. DELL: Мобильная рабочая станция — выбор профессионала [электронный ресурс]. - Режим доступа: https://habr.com/company/dell/blog/400851/ (дата обращения: 18.12.2018).

58. Сравнение процессоров Intel по количеству ядер [электронный ресурс]. -Режим доступа: https://ark.intel.com/ru/Search/FeatureFilter?productType=processors&CoreCount Min=72 (дата обращения: 19.12.2018).

59. Lenovo [электронный ресурс]. - Режим доступа: https://www.lenovo.com/ru/ru/ (дата обращения: 25.12.2018).

60. Fujitsu [электронный ресурс]. - Режим доступа: http://www.fujitsu.com/ru/ (дата обращения: 25.12.2018).

61. DELL Решения для работы [электронный ресурс]. - Режим доступа: https://www.dell.com/ru/business/p/?~ck=mn (дата обращения: 27.12.2018)

62. Hewlett Packard [электронный ресурс]. - Режим доступа: https://www8.hp.com/us/en/home.html (дата обращения: 27.12.2018).

63. RVi [электронный ресурс]. - Режим доступа: https://rvi-cctv.ru/ (дата обращения: 26.12.2018).

64. Информационные технологии РФЯЦ-ВНИИЭФ [электронный ресурс]. -Режим доступа: http://www.vniief.ru/resources/e350ba0045ad9a7b9a2fbeae94c0706c/Catalog_IT.p df (дата обращения: 25.12.2018).

65. Таненбаум Э., Остин Т. Архитектура компьютера. 6-е изд. - СПб.: Питер, 2013. - 816 с.

66. Hennessy J., and Patterson D., Computer Architecture: A Quantitative Approach. 5th ed., Waltham: Morgan Kaufmann, 2011. - 857 с.

67. Harris D.M., Harris S.L. Digital Design and Computer Architecture. New York: Morgan Kaufman, 2013. - 1621 с.

68. Patterson D.A., Hennessy J.L. Computer Organization and Design. The hardware and software interface. 5th ed., Waltham: Morgan Kaufmann, 2014. - 793 с.

69. Аладышев О.С., Дикарев Н.И., Овсянников А.П., Телегин П.Н., Шабанов Б.М. СуперЭВМ: области применения и требования к производительности // Известия ВУЗов. Электроника, 2004. - №1. - С. 13-17.

70. Серверная продукция Intel [электронный ресурс]. - Режим доступа: https: //www.intel .ru/content/www/ru/ru/products/servers .html (дата обращения : 25.12.2018).

71. Т-Платформы. Серверы. [электронный ресурс]. - Режим доступа: https://t-platforms.ru/production/servers/? (дата обращения: 25.12.2018).

72. Программа Скиф-Недра [электронный ресурс]. - Режим доступа: http://skifnedra.ru/ (дата обращения: 25.12.2018).

73. РСК микроЦОД [электронный ресурс]. - Режим доступа: http://www.rscgroup.ru/ru/our-solutions/rsk-mikrocod-ot-16-do-64-uzlov-do-100-tflops (дата обращения: 25.12.2018).

74. РСК Поле [электронный ресурс]. - Режим доступа: https://servernews.ru/965557 (дата обращения: 25.12.2018).

75. IBM Power System AC922 Introduction and Technical Overview [электронный ресурс]. - Режим доступа: https://www.redbooks.ibm.com/redpapers/pdfs/redp5472.pdf (дата обращения: 25.12.2018).

76. Supermicro products [электронный ресурс]. - Режим доступа: https://www.supermicro.com/products/index.cfm (дата обращения: 25.12.2018).

77. Gigabyte products [электронный ресурс]. - Режим доступа: https://b2b.gigabyte.com/ (дата обращения: 25.12.2018).

78. Cavium ThunderX2 CN99XX Product Brief [электронный ресурс]. - Режим доступа: https://www.marvell.com/documents/cmvd78bk8mesogdusz6t/ (дата обращения: 25.12.2018).

79. NVIDIA. Решения для дата-центров [электронный ресурс]. - Режим доступа: https://www.nvidia.com/ru-ru/data-center/products/ (дата обращения: 25.12.2018).

80. Ang J.A., Barrett R.F., Hammond S.D., Rodrigues A.F. Emerging high performance computing systems and next generation engineering analysis applications // In Pacific Rim Workshop on Innovations in Civil Infrastructure Engineering. National Taiwan University of Science and Technology, 2013.

81. Chelva M.S., Halse S.V. A Performance Study of GPU, FPGA, DSP, and Multicore Processors For Embedded Vision Systems // ITSI Transactions on Electrical and Electronics Engineering (ITSI-TEEE). - 2015. -№5,6, том №3. - С. 61-66.

82. ASIC Design Services [электронный ресурс]. - Режим доступа: https://anysilicon.com/vendor_category/asic_design (дата обращения: 06.12.2018).

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

84. Угрюмов Е.П. Цифровая схемотехника: учебное пособие для вузов. -2-е изд., перераб. и доп. - СПб.: Изд-во «БХВ-Петербург», 2007. - 800 с.

85. Intel Устройства FPGA [электронный ресурс]. - Режим доступа: https://www.intel.ru/content/www/ru/ru/fpga/devices.html (дата обращения: 05.12.2018).

86. Xilinx [электронный ресурс]. - Режим доступа: https://www.xilinx.com (дата обращения: 05.12.2018).

87. Measuring Device Performance and Utilization: A Competitive Overview [электронный ресурс]. - Режим доступа: https://www.xilinx.com/support/documentation/white_papers/wp496-comp-perf-util.pdf (дата обращения: 05.12.2018).

88. List of FPGA Companies [электронный ресурс]. - Режим доступа: http://hardwarebee.com/list-fpga-companies (дата обращения: 06.12.2018)

89. UltraScale FPGA Product Tables and Product Selection Guide [электронный ресурс]. - Режим доступа:

https://www.xilinx.com/support/documentation/selection-guides/ultrascale-fpga-product-selection-guide.pdf (дата обращения: 04.06.2019).

90. Intel Stratix 10 FPGAs [электронный ресурс]. - Режим доступа: https://www. intel. com/content/www/us/en/products/programmable/fpga/stratix-10.html (дата обращения: 05.12.2018).

91. Intel Arria 10 FPGAs [электронный ресурс]. - Режим доступа: https://www. intel. com/content/www/us/en/products/programmable/fpga/arria-10.html (дата обращения: 05.12.2018).

92. Achronix [электронный ресурс]. - Режим доступа: https://www.achronix.com (дата обращения: 05.12.2018).

93. Lattice Semiconductor [электронный ресурс]. - Режим доступа: https://www.latticesemi.com (дата обращения: 05.12.2018).

94. Microsemi [электронный ресурс]. - Режим доступа: https://www.microsemi.com (дата обращения: 05.12.2018).

95. Efinix [электронный ресурс]. - Режим доступа: https://www.efinixinc.com (дата обращения: 05.12.2018).

96. GW2A series of FPGA Products. Data Sheet [электронный ресурс]. - Режим доступа: https://alcom.nl/wp-content/uploads/2018/10/Gowin_041018_DS 102-1.2E_GW2A-series-of-FPGA-Products-Data-Sheet.pdf (дата обращения: 05.12.2018).

97. EnSilica [электронный ресурс]. - Режим доступа: http://www.ensilica.com (дата обращения: 05.12.2018).

98. ADM-PCIE-9H7 [электронный ресурс]. - Режим доступа: https://www.alpha-data.com/pdfs/adm-pcie-9h7.pdf (дата обращения: 05.12.2018).

99. Nallatech 520N [электронный ресурс]. - Режим доступа: https://mk0nallatech1gx00yy0.kinstacdn.com/wp-content/uploads/Nallatech-520N-Product-Brief-V9.pdf (дата обращения: 05.12.2018).

100. Opal Kelly XEM7305 [электронный ресурс]. - Режим доступа: https://opalkelly.com/products/xem7305 (дата обращения: 05.12.2018).

101. Enclustra FPGA Modules [электронный ресурс]. - Режим доступа: https://www.enclustra.com/en/products/fpga-modules (дата обращения: 05.12.2018).

102. Metromatics FPGA Modules [электронный ресурс]. - Режим доступа: https://metromatics.com.au/product-tag/fpga (дата обращения: 05.12.2018)

103. Annapolis Micro Systems FPGA boards https://www.annapmicro.com/product-category/fpga-boards-2/ (дата обращения: 05.12.2018).

104. Netcope FPGA boards [электронный ресурс]. - Режим доступа: https://www.netcope.com/en/products/fpga-boards (дата обращения: 05.12.2018)

105. CommAgility products hardware [электронный ресурс]. - Режим доступа: https://www.commagility.com/products/hardware (дата обращения: 05.12.2018).

106. LDA Technologies [электронный ресурс]. - Режим доступа: http://www.ldatech.com (дата обращения: 05.12.2018).

107. Achieve High-Performance Computing in Three Easy Steps [электронный ресурс]. - Режим доступа: https://www.micron.com/resource-details/c4c19baa-895b-4080-896c-ad9d1fe7aa3b (дата обращения: 05.12.2018).

108. Abaco systems advanced RF and DSP solutions [электронный ресурс]. - Режим доступа: https://www.abaco.com/products/advanced-rf-dsp-solutions (дата обращения: 05.12.2018).

109. SciEngines Rivyera S6-LX150 [электронный ресурс]. - Режим доступа: https://www.sciengines.com/wp-

content/uploads/RIVYERA_S6_LX 150_REV3 8_DATASHEET.pdf (дата

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

110. Горбунов В.С., Лабошин Л.Ю., Лукашин А.А., Титов А.Г. Исследование возможности предоставления реконфигурируемых вычислительных ресурсов на базе ПЛИС в виде облачного сервиса // Материалы Международной суперкомпьютерной конференции "Научный сервис в сети Интернет: все грани параллелизма". - 2013. - С. 130-134.

111. Kalyaev I.А., Levin I.I., Semernikov E.A., Shmoilov V.I. Reconfigurable Multipipeline Computing Structures Published by Nova Science Publishers, Inc. (New York, USA). 2012. 345 p. ISBN: 978-1-61942-854-6.

112. Левин И.И., Семерников Е.А., Раскладкин М.К. Методы сопряжения вычислительных узлов и блоков в программах для реконфигурируемых вычислителей: Учебное пособие. - Таганрог: Изд-во ЮФУ, 2012. - 130 с.

113. DiniGroup Products overview [электронный ресурс]. - Режим доступа: https://www.dinigroup.com/web/products.php (дата обращения: 05.12.2018)

114. Samtec [электронный ресурс]. - Режим доступа: https://www.samtec.com (дата обращения: 05.12.2018).

115. Dordopulo A., Fedorov A., Levin I., Doronchenco Y. High-Performance Reconfigurable Computer Systems with Immersion Cooling // In: Sokolinsky L., Zymbler M. (eds) Parallel Computational Technologies. PCT 2018. Communications in Computer and Information Science, vol 910. Springer, Cham. - Pp. 62-76.

116. Левин И.И., Дордопуло А.И., Сорокин Д.А., Доронченко Ю.И., Федоров А.М. Российские суперкомпьютеры с реконфигурируемой архитектурой // Шестой Национальный Су-перкомпьютерный Форум, (НСКФ-2017), ИПС имени А.К. Айламазяна РАН, г. Переславль-Залесский, Россия, 28 ноября-01 декабря 2017 г.

117. Kalyaev I.A., Levin I.I., Dordopulo A.I., Slasten L.M. Reconfigurable computer systems based on Virtex-6 and Virtex-7 FPGAs // Proc. 12th IFAC Conf. on Programmable Devices and Embedded Systems, Velke Karlovice, Czech Republic, September 25-27, 2013. Vol. 12, Issue 1. Oxford: Elsevier, 2013. - Рр. 210-214.

118. Левин И.И., Дордопуло А.И., Сорокин Д.А., Каляев З.В., Доронченко Ю.И. Реконфигурируемые компьютеры на основе ПЛИС Xilinx Virtex UltraScale // Parallel Computational Technologies (13th International Conference, PCT 2019, Immanuel Kant Baltic Federal University, Kaliningrad, Russia, April 2-4, 2019. -Pp. 288-298.

119. Kontron [электронный ресурс]. - Режим доступа: https://www.kontron.com (дата обращения: 06.12.2018).

120. VanCourt T.D. LAMP: Tools for creating application-specific FPGA coprocessors: dissertation for the degree of Doctor of Philosophy. - Boston University, College of Engineering, 2006. - 418 с.

121. Barbacci M.R., Grout S., Lindstrom G., Maloney M.P., Organick E.I., Rudisill D. Ada as a Hardware Description Language: An initial report. Proceedings of the Conference on Computer Hardware Description Languages and their Applications. 1985.

122. Design Automation Standards Committee of the IEEE Computer Society. IEEE Standard Verilog Hardware Description Language. - The Institute of Electrical and Electronics Engineers, New York, 2001. - 778 c.

123. Design Automation Standards Committee of the IEEE Computer Society. IEEE Standard VHDL Language Reference Manual. - The Institute of Electrical and Electronics Engineers, New York, 2000. - 290 c.

124. Chu P.P. RTL Hardware Design Using VHDL: Coding for Eflciency, Portability, and Scalability. - John Wiley & Sons, 2006. - 669 c.

125. Nane R., Sima V.M., Pilato C., Choi J., Fort B., Canis A., Chen Y.T., Hsiao H., Brown S. A Survey and Evaluation of FPGA High-Level Synthesis Tools. // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016. - №35 (10). - Рр: 1591-1604.

126. Vivado Design Suite. User Guide. High-Level Synthesis [электронный ресурс]. -Режим доступа: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2018_2/ug902-vivado-high-level-synthesis.pdf (дата обращения: 12.12.2018).

127. Vivado Design Suite User Guide [электронный ресурс]. - Режим доступа: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2018_2/ug994-vivado-ip-subsystems.pdf (дата обращения: 11.12.2018).

128. Intel High-Level Synthesis Compiler [электронный ресурс]. - Режим доступа: https://www. intel. com/content/www/us/en/soft-ware/programmable/quartus-prime/hls-compiler.html (дата обращения: 12.12.2018).

129. Каляев И.А., Левин И.И., Семерников Е.А. Принципы построения многопроцессорных вычислительных систем на основе ПЛИС // Вестник Бурятского государственного университета. Сер. 9: математика и информатика. - Улан-Удэ: Изд-во Бурятск. гос. ун-та, 2008. - С.184-196. ISBN 1994-0866.

130. Bambu: A Free Framework for the High-Level Synthesis of Complex Applications [электронный ресурс]. - Режим доступа: https://panda.dei.polimi.it/?page_id=31 (дата обращения: 12.12.2018).

131. Impulse C [электронный ресурс]. - Режим доступа: https://en.wikipedia.org/wiki/Impulse_C (дата обращения: 12.12.2018).

132. BSV High-Level HDL [электронный ресурс]. - Режим доступа: https://bluespec.com/54621-2/ (дата обращения: 12.12.2018).

133. Cadence FPGA Development [электронный ресурс]. - Режим доступа: https://www.cadence.com/content/cadence-

www/global/en_US/home/solutions/fpga-development.html (дата обращения: 12.12.2018).

134. Mitrionics [электронный ресурс]. - Режим доступа: https://en.wikipedia.org/wiki/Mitrionics (дата обращения: 20.12.2018).

135. Mitrion-C [электронный ресурс]. - Режим доступа: http://mitc-openbio.sourceforge.net/ (дата обращения: 20.12.2018).

136. Nallatech [электронный ресурс]. - Режим доступа: https://www.nallatech.com/ (дата обращения: 20.12.2018).

137. OpenCL Overview Development [электронный ресурс]. - Режим доступа: https://www.khronos.org/opencl/ (дата обращения: 20.12.2018).

138. Левин И.И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений: диссертация на соискание ученой степени доктора технических наук, по специальностям: 05.13.11

"Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", 05.13.15 - "Вычислительные машины и системы", научные консультанты: академик РАН, д.т.н., проф. Каляев А.В., чл.-корр. РАН, д.т.н., проф. Каляев И.А., дис. совет ТРТУ Д 212.259.05, 2004. - 363 с.

139. Дордопуло А.И., Левин И.И. Ресурсонезависимое программирование гибридных реконфигурируемых вычислительных систем // Труды Международной ко-нференции «Суперкомпьютерные дни в России» (Russian Supercomputing Days 2017), 25-26 сентября 2017, Москва, Россия. - М.: Изд-во МГУ, 2017. - С. 714-723.

140. Среда разработки вычислительных структур Fire!Constructor [электронный ресурс]. - Режим доступа: http://superevm.ru/index.php?page=fire-constructor (дата обращения: 20.12.2018).

141. Левин И.И., Дордопуло А.И., Гудков В.А. Программирование реконфигурируемых вычислительных узлов на языке COLAMO: Учебное пособие. 2-е изд. доп. - Ростов-на-Дону: Изд-во ЮФУ, 2016. - 114 с.

142. Сорокин Д.А. Методы решения задач с переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И. Дис. совет Д 212.208.24 ЮФУ от 15.06.2012 г., протокол № 5. - 165 с.

143. Сорокин, Д.А., Дордопуло А.И. Методика сокращения аппаратных затрат в сложных системах при решении задач с существенно-переменной интенсивностью потоков данных // Известия ЮФУ. Технические науки. -Таганрог: Изд-во ТТИ ЮФУ, 2012. - №4. - С. 213-219.

144. Карпов Д.В. Теория графов // СПб.: Санкт-Петербургское отделение Мат. института им. В.А. Стеклова РАН, 2017. - 482 с.

145. Левин И.И. Пелипец А.В. Эффективная реализация распараллеливания на реконфигурируемых системах // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2018. - № 8. - С. 11-16.

146. Пелипец А.В. Методы и средства решения задач линейной алгебры на высокопроизводительных реконфигурируемых вычислительных системах: диссертация на соискание ученой степени кандидата технических наук, по специальности 05.13.11 "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей", научный руководитель: д.т.н., проф. Левин И.И. - Таганрог, 2016. - 199 с.

147. Алексеев К.Н. Методика синтеза параллельно-конвейерных программ для РВС при решении задач класса реального времени с функционально-регулярным информационным графом // XV ежегодная научная конференция молодых ученых «Вклад молодых ученных южного макрорегиона в реализацию стратегии развития Российской федерации: цели, задачи, результаты», г. Ростов-на-Дону, 15.04.2019 - 26.04.2019 гг. - г. Ростов-на-Дону: Изд-во ЮНЦ РАН, 2019. - С. 90.

148. Хмелевской В.К. Геофизические методы исследования земной коры. Книга 1. - Дубна: Международный университет природы, общества и человека "Дубна", 1997.

149. Денисов М.С., Фиников Д.Б. Методы подавления кратных волн в сейсморазведке. Часть 1 // Технологии сейсморазведки. - 2007. - №1. - С. 516.

150. Verschuur D. J., Berkhout A. J., Wapenaar C. P. A. Adaptive surface-related multiple elimination // Geophysics. - 1992. - №9. - Рр. 1166-1177.

151. Berkhout, A.J., Verschuur D.J. Estimation of multiple scattering by iterative inversion, Part I: theoretical considerations. // Geophysics. - 1997. - №5. - Рр. 1586-1595.

152. Van Dedem E.J., Verschuur D.J. 3D surface-related multiple prediction: A sparse inversion approach // Geophysics. - 2005. - №3. - Рр. 31-43.

153. Artman B., Alvarez G., Matson K. Image-space surface-related multiple prediction // Geophysics. - 2007. - №2. - Рр. 113-122.

154. Verschuur E. A perspective on 3D surface-related multiple elimination. // Geophysics. Dragoset B., Moore I., Bisley R. - 2010. - №5. - C. 245-261.

155. Выбор направления исследований и разработки высокопроизводительных вычислительных систем «СКИФ-ГЕО» второй базовой конфигурации, обеспечивающих формирование оптимальных конфигураций аппаратных средств и программного обеспечения для решения расчетных геолого-геофизических задач : отчет о НИР / ООО НИЦ СЭ и НК ; рук. Ю.И. Доронченко ; исполн.: Д.А. Сорокин. Таганрог, 2015. 275 с. № 115092410004 по договору № 2-26-06-СКИФ/НИР/15 от 22.06.2015, инв. № 001-0/15.

156. Sorokin D.A., Matrosov A.Y., Semernikova E.E., Alekseev K.N. Real-time Implementation of the Problem of Surface-Related Multiple Prediction on RCS // Parallel Computational Technologies (13th International Conference, PCT 2019, Immanuel Kant Baltic Federal University, Kaliningrad, Russia, April 2-4, 2019. -Pp. 91-98.

157. Сорокин Д.А., Матросов А.Ю., Семерникова Е.Е., Алексеев К.Н. Структурно-процедурная реализация алгоритма SRMP на ПЛИС // Труды 4-й Всероссийской научно-технической конференции "Суперкомпьютерные технологии" (СКТ-2016) 19-24 сентября 2016 г., с. Дивноморское, Россия. -Ростов-на-Дону. Изд-во ЮФУ, 2016. - С. 92-96. ISBN 978-5-9275-1283-6

(Т.1).

158. Сорокин Д.А., Матросов А.Ю., Семерникова Е.Е., Алексеев К.Н. Структурно-процедурная реализация алгоритма прогнозирования кратных волн на ПЛИС // Известия ЮФУ. Технические науки. - Ростов/Д.: Изд-во ЮФУ, 2016. - № 12. - С. 16-28.

159. Alekseev K., Sorokin D., Levin I. Application of the methodology of creating parallel-pipeline programs for reconfigurable computer systems on the example of implementation of surface-related multiple prediction problem in real time // XV International Scientific-Technical Conference "Dynamic of Technical Systems"

(DTS-2019) AIP Conf. Proc. 2188, 050039-1-050039-10; https://doi.Org/10.1063/1.5138466 Published by AIP Publishing. 978-0-7354-1935-3/$30.00 (Scopus).

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

161. Введение в цифровую фильтрацию. Под ред. Р. Богнера и А. Константинидиса. - М.: Мир, 1976. - 216 с.

162. Семерников Е.А., Доронченко Ю.И. Конвейерный макропроцессор цифровой обработки сигналов со структурно-процедурной организацией вычислений // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2005. -№8. - С. 49-55.

163. UltraScale Architecture and Product Data Sheet: Overview [электронный ресурс]. - Режим доступа: https://www.xilinx.com/support/documentation/data_sheets/ds890-ultrascale-overview.pdf (дата обращения: 05.12.2018).

164. Performance and Resource Utilization for Floating-point v7.1 [электронный ресурс]. - Режим доступа: https://www.xilinx.com/support/documentation/ip_documentation/ru/floating-point.html (дата обращения: 06.05.2019).

165. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. 2-е изд.: Пер. с английского - М.: Издательский дом «Вильямс», 2001.

166. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989, 360 с.

167. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. Пер. с англ. под ред. А. Шеня. - М.: МЦНМО, 2014. - 320 с.

168. Скворцов С.В., Пюрова Т.А. Параллельные алгоритмы сортировки данных и их реализация на платформе CUDA // Вестник РГРТУ, 2016. -№58. - С. 4248.

169. Писаренко И.В., Алексеев К.Н., Мельников А.К. Ресурсонезависимое представление сортирующих сетей на языке программирования Set@l // Вестник компьютерных и информационных технологий. - М.:

Машиностроение, 2019. - № 11 (185). - С. 53-60. DOI: 10.14489/vkit.2019.11.pp.053-060. http://vkit.ru/index. php/ current-issue-rus/857-053-060.

170. Batcher K.E. Sorting Networks and their Applications // Proc. AFIPS Spring Joint Comput. Conf. 1968. Vol. 32. P. 307314.

171. Левин И.И., Пономарев И.М. Структурная реализация сортировки массивов на основе сети Батчера // Материалы международной научно-технической конференции «Искусственный интеллект. Интеллектуальные и многопроцессорные системы». - Таганрог: Изд-во ТРТУ, 2004. Т.1. - С.202-206.

172. Пономарев И.М. Разработка и исследование методов синтеза параллельных алгоритмов для многопроцессорных систем со структурно-процедурной организацией вычислений: дис. канд. техн. наук. - Таганрог, 2003. - 246 с.

173. Алексеев К.Н. Методика синтеза параллельных программ для решения задач реального масштаба времени на РВС // XIV Ежегодная молодежная научная конференция студентов, аспирантов и молодых ученых «Достижения и перспективы молодых ученых в интересах развития Юга России»: тезисы докладов (г. Ростов-на-Дону, 12-26 апреля 2018 г.). - Ростов н/Д: Изд-во ЮНЦ РАН, 2018. - 222 с. - С. 65. ISBN 978-5-4358-0167-5.

174. Ilya Levin, Alexey Dordopulo, Vyacheslav Gudkov, Andrey Gulenok, Alexander Bovkun, Georgyi Yevstafiyev, Kirill Alekseev Software Development Tools for FPGA-Based Reconfigurable Systems Programming // In: Communications in Computer and Information Science (CCIS), vol 1129, pp 625-640, Springer, Cham. 10 December 2019, DOI: https://doi.org/10.1007/978-3-030-36592-9_51, Publisher ISBN978-3-030-36591 -2, https://link.springer.com/chapter/10.1007/978-3-030-36592-9_51

175. Алсынбаев К.С., Козлов А.В. Средства распознавания и визуализации разломов и зон техногенной трещиноватости на основе обработки данных микросейсмического мониторинга // Вестник Балтийского федерального

университета им. И. Канта. - Калининград: Изд-во БФУ им. И. Канта, 2014. -№ 4. - С. 127-134.

176. Ерохин Г.Н., Алсынбаев К.С., Брыксин В.М., Савеленко В.В., Строков В.И., Козлов А.В., Козлов М.В. Алгоритмы интерпретации и визуализации результатов обработки данных постоянно действующего мониторинга месторождений углеводородов // Марчуковские научные чтения - 2017: труды международной научной конференции (г. Новосибирск, 25 июня-14 июля 2017 г.). - Новосибирск: Институт вычислительной математики и математической геофизики СО РАН, 2017. - С. 289-295.

177. Внедрение и использование цифровых технологий в энергетике исходя из принципов экономической целесообразности и повышения доступности энергетической инфраструктуры и распределенной энергетики. 2018 [электронный ресурс]. - Режим доступа: https://minenergo.gov.ru/node/10877 (дата обращения: 14.11.2018).

178. Бетелин В.Б. «Цифровое месторождение» - путь к трудноизвлекаемым запасам углеводородов // Инновации. - Санкт-Петербург: Трансфер, 2014. -№1. - С. 37 - 38.

179. Шмаков Ф.Д., Бортников П.Б. Решение обратной кинематической задачи локации источника сейсмического излучения для горизонтально-слоистой среды // Вестник югорского государственного университет. - Ханты-Мансийск: Югорский государственный университет, 2011. - № 3(22). -С. 107-111.

180. Глоговский В.М., Лангман С.Л. Свойства решения обратной кинематической задачи сейсморазведки // Технологии сейсморазведки. - Новосибирск: ИНГГ СО РАН, 2009. - № 1. - С. 10-17.

181. Гапеев Д.Н., Ерохин Г.Н., Седайкин Р.Д., Строков В.И. Опыт применения микросейсмического мониторинга для контроля заводнения на месторождении Северная Трува // Вестник Балтийского федерального университета им. И. Канта. - Калининград: Изд-во БФУ им. И. Канта, 2015. -№ 10. - С. 133-139.

182. Алексеев К.Н. Реализация задачи разложения симметричных положительно определенных матриц методом Холецкого на РВС // труды XIII ежегодной молодежной научной конференции студентов, аспирантов и молодых ученых «Исследования и разработки передовых научных направлений»: тезисы докладов (г. Ростов-на-Дону, 17-27 апреля 2017 г.). - Ростов н/Д: Изд-во ЮНЦ РАН, 2017. - 356 с. - С. 147. ISBN 978-5-4358-0150-7.

183. Алексеев К.Н., Левин И.И. Реализация обратной кинематической задачи сейсморазведки для микросейсмического мониторинга на реконфигурируемых вычислительных системах в реальном масштабе времени // Известия ЮФУ. Технические науки. - Ростов/Д: Изд-во ЮФУ, 2018. - №8 (202). - С. 221-231. DOI 10.23683/2311-3103-2018-8-221-230. ISSN 1999-9429.

184. Lelewer D.A., Hirschberg D. S. Data Compression - ACM Comput. Surv., 1987. -№ 19. - С. 261-296.

185. Ватолин Д., Ратушняк А., Смирнов В., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: Издательство ДИАЛОГ-МИФИ, 2003. - 384 с.

186. WinZIP [электронный ресурс]. - Режим доступа: https://www.winzip.com/win/ru/ (дата обращения: 04.06.2019).

187. WinRAR [электронный ресурс]. - Режим доступа: https://www.win-rar.com/start.html?&L=4 (дата обращения: 04.06.2019).

188. 7-Zip [электронный ресурс]. - Режим доступа: https://www.7-zip.org/ (дата обращения: 04.06.2019).

189. Алексеев К.Н., Семерникова Е.Е., Сорокин Д.А. Структурно-процедурная реализация кодирования алгоритмом Хаффмана в задачах управления // Материалы 10-й Всероссийской мультиконференции по проблемам управления (МКПУ-2017), 11 - 16 сентября 2017 г. - Ростов/Д.: Изд-во ЮФУ, 2017. - Т.3. - С. 126-127.

190. Deutsch P. RFC 1951-DEFLATE Compressed Data Format Specification Version 1.3, 1996. [электронный ресурс]. - Режим доступа: http://www.faqs.org/rfcs/rfc1951.htm (дата обращения: 04.06.2019).

191. Series Product Tables and Product Selection Guide, 2018 [электронный ресурс]. - Режим доступа: https://www.xilinx.com/support/documentation/selection-guides/7-series-product-selection-guide.pdf#K7 (дата обращения: 10.06.2018).

192. Раскладкин М.К. Библиотека масштабируемых интерфейсов для реконфигурируемых вычислительных систем на основе ПЛИС // Высокопроизводительные параллельные вычисления на кластерных системах: Материалы девятой международной конференции-семинара. -Владимир, 2009. - 438 с. ISBN 978-5-89368-958-7

193. Алексеев К.Н. Построение и обработка многомерных структур данных типа «дерево» в режиме реального времени на РВС // Суперкомпьютерные технологии (СКТ-2018): материалы 5-й Все-российской научно-технической конференции: в 2 т. - Ростов/Д; Таганрог: Изд-во ЮФУ, 2018. - Т. 1. - С. 123126.

194. Алексеев К.Н. Разработка высокоскоростного регистрового интерфейса доступа для ПЛИС // XII Ежегодная научная конференция студентов и аспирантов базовых кафедр Южного научного центра РАН: тезисы докладов (г. Ростов-на-Дону, 15-28 апреля 2016 г.). - Ростов н/Д: Изд-во ЮНЦ РАН, 2016. - 316 с. - ISBN 978-5-4358-0130-9. - С. 100-101. http://www.ssc-ras.ru/ckfinder/userfiles/files/TezisBK_2016.pdf.

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

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

АЛЕКСЕЕВ КИРИЛЛ НИКОЛАЕВИЧ

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

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

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.1. РЕДУКЦИЯ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНОМ СТРУКТУРЫ ЗАДАЧИ ПРОГНОЗИРОВАНИЯ КРАТНЫХ ВОЛН

Выполним операцию редукции производительности вычислительной структуры задачи прогнозирования кратных волн. Порядок выполнения различных методов редукции описан во второй главе настоящей диссертации, а именно: редукция по базовым подграфам, редукция по операциям, редукция по разрядности операндов. Начальный коэффициент редукции для ПЛИС семейства КПех Шта8са1е: г° = 2.7 • 1012.

Число базовых подграфов в подзадаче Р12 можно рассчитать по формуле:

Ыд12 = п^п^т, (П. 1.1)

где п = т = 8192. Так как г° > Ыд12, согласно пункту 2.2.3° методики, пересчитаем коэффициент редукции по формуле:

г1 = [г0/Ыд12]. (П.1.2)

Сократим количество базовых подграфов до одного. В данном случае г1 = 4. Перейдем к редукции базового подграфа задачи с коэффициентом редукции г1.

Количество базовых операций БПФ определим по формуле [159]:

Ыор = (5/2)^^2 5, (П.1.3)

где 5 = 4096. Так как в данном случае г1 < Иор, согласно пункту 2.2.4° методики, необходимо сократить количество базовых операций в г1 раз и перейти к пункту 2.2.10°.

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

Ызг = ^2 5-^2Г\ (П.1.4)

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

Выполним редукцию по операциям в каждом слое графа БПФ отдельно. Количество операций после редукции рассчитаем по следующей формуле:

и5% = [иор/^2 5^г11 (П. 1.5)

В данном случае N $ор = 512, а буферная память будет использована только в двух последних слоях вычислительной структуры.

Согласно пункту 2.2.10° методики, переходим к выполнению редукции производительности вычислительной структуры подзадачи Р5рш. Так как

щРзрш = , как и при редукции подзадачи Р12, сокращаем количество базовых подграфов до одного и проводим редукцию по операциям с коэффициентами г1. Количество операций разделения потоков данных после редукции N ррЫ1- = 512.

Согласно пункту 2.2.10° методики, переходим к выполнению редукции производительности вычислительной структуры подзадачи Р3. Разделим подзадачу операции свертки трасс Р3 на две подзадачи:

Рз = Р1^Р2, (П. 1.6)

где подзадаче Р3 выполняется комплексное умножение данных одного слоя приемников с данными слоя источников; в подзадаче Р3 выполняется

суммирование результатов подзадачи Р3. р1 р

Так как N д3 = Ыд12, как и при редукции подзадачи Р12, сокращаем количество базовых подграфов до одного и проводим редукцию по операциям с коэффициентами г1. Количество операций комплексного умножения после редукции = 512.

Подзадача Р3 состоит из п^т^ б базовых подграфов, выполняющих сложение п значений. Граф подзадачи Р3 состоит из ассоциативных операций, в связи с чем имеется возможность выбрать топологию графа. В данном случае была выбрана топология «пирамида», полученная путем применения принципа

р2 р2

«деление пополам». Так как г° > N д3, где N д3 - количество базовых подграфов в

подзадаче Р2, согласно разработанной методике, рассчитаем коэффициент редукции г1 и сократим количество базовых подграфов до одного. В нашем случае г1 = 9. Так как Мааа = 4095, где - количество операций

комплексного сложения в базовом подграфе подзадачи Р2, согласно пункту 2.1.4° методики, сократим количество операций в г1 раз. Таким образом, а = 455.

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

Подзадача Р4 состоит из п • т базовых подграфов обратного БПФ. Для

п Р

заданных параметров задачи справедливо неравенство г 0 > Ыд4, поэтому согласно пункту 2.2.3° методики, пересчитаем коэффициент редукции г1 и сократим количество базовых подграфов до одного. В нашем случае г1 = 40233.

Количество базовых операций БПФ Иор = 24576. Так как в данном случае г1 > Иор, согласно пункту 2.2.5° методики, рассчитаем коэффициент редукции г2 и сократим количество базовых операций БПФ до одной. В нашем случае г2 = 1, поэтому переходим к пункту 2.1.10° методики. Таким образом, редуцированная подзадача Р4 будет состоять из одной базовой операции обратного БПФ.

РЕДУКЦИЯ НЕЧЕТНО-ЧЕТНОЙ СОРТИРУЮЩЕЙ СЕТИ

АЛЕКСЕЕВ КИРИЛЛ НИКОЛАЕВИЧ

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

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

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.2. РЕДУКЦИЯ НЕЧЕТНО-ЧЕТНОЙ СОРТИРУЮЩЕЙ СЕТИ

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

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

Если г0 расположен в интервале п/2 < г0 < п(п — 1)/2, нечетно-четную сортирующую сеть необходимо сократить до одной итерации, рассчитать новый коэффициент редукции 1 и уменьшить количество выполняемых операций в 1 раз с округлением в большую сторону.

Если г0 > п(п — 1)/2, количество выполняемых операций сокращается до одной, состоящей из одного двусортировщика. В таком виде структура сортирующей сети будет аналогична структуре, представленной на рис. 2.12, и будет отличаться только порядком выполнения операций.

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

РЕДУКЦИЯ СОРТИРУЮЩЕЙ СЕТИ ПОИСКА МИНИМУМА И

МАКСИМУМА

АЛЕКСЕЕВ КИРИЛЛ НИКОЛАЕВИЧ

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

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

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.3. РЕДУКЦИЯ СОРТИРУЮЩЕЙ СЕТИ ПОИСКА МИНИМУМА И

МАКСИМУМА

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

Iter 1

Iter 2

Iter n/2

KiO>

k5^~

kn-4^~ kn-3O—

kn-P->r kn o-*

CC

CC

u

CC

CC

CC

CC

CC

CC

CC

CC

CC

CC

CC

CC

CC

CC

т-ж» cc

CC

CC

CC

CC

-M

CC

ж

4

CC

CC

CC

• ••

CC

ve W

CC

Ж •

1"

CC

CC

-+OK i -+0k2

CC • •

CC

J*

CC

CC

CC

CC

CC

CC

CC

CC

V->cK n/2-1

n/2

CC

CC

CC

CC

CC

CC

-*°K n-1

~+oK'n

Рис. П. 3.1. Схема информационного графа сортирующей сети поиска минимума

и максимума

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

сортирующей сети можно определить по формулам:

П1гег = п/2, т = 3п — 4/2. (П.3.1)

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

Предельная редукция сортирующей сети по числу операций в итерациях при г° = 2п-3 приводит к тому, что остается п/2 изоморфных итераций, состоящих из двух двусортировщиков CC.

После того как все итерации стали изоморфны, можно выполнять редукцию по итерациям. Если коэффициент редукции г°>п(п-1)/2, количество операций в сортирующей сети поиска минимума и максимума, состоящей из одной итерации, необходимо сократить до одной. В этом случае структура сети становится аналогичной как структуре редуцированной сети поиска минимума, представленной на рис. 2.12, так и структуре редуцированной сети поиска максимума. Если обработка массива будет выполняться в порядке следования итераций, порядок получения адресов от адресных генераторов AGI и AG2 будет соответствовать алгоритму так называемой «коктейльной» или «шейкерной» сортировки. Принцип данной сортировки основан на нахождении максимума в массиве данных за один проход по массиву, а также минимума - за проход по массиву в обратную сторону.

ОПТИМИЗАЦИЯ НЕЧЕТНО-ЧЕТНОЙ СОРТИРУЮЩЕЙ СЕТИ И

РЕДУКЦИЯ СЕТИ БАТЧЕРА

АЛЕКСЕЕВ КИРИЛЛ НИКОЛАЕВИЧ

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

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

комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук Научный руководитель:

доктор технических наук, профессор Левин И.И.

П.4.1. ОПТИМИЗАЦИЯ НЕЧЕТНО-ЧЕТНОЙ СОРТИРУЮЩЕЙ СЕТИ

Все квадратичные сортирующие сети являются избыточными, так как в них выполняется больше сравнений, чем это необходимо [165]. На данный момент не существует единой формулы, которой можно описать необходимое количество сравнений, в связи с чем для массивов разных размерностей его определяют эмпирическим путем. Однако можно получать более эффективные сортирующие сети путем оптимизации рассмотренных квадратичных сортирующих сетей, учитывая их свойства и особенности. В качестве примера выполним оптимизацию нечетно-четной сортирующей сети и приведем её к сети Батчера путем применения принципа «деления пополам».

Рассмотрим исходный массив данных как две непересекающиеся последовательности, выполним их сортировку отдельно, используя нечетно-четные сети, и объединим две отсортированные последовательности в один результирующий массив, используя так называемую сеть слияния. Количество выполняемых сравнений в каждой нечетно-четной сортирующей сети размерностью п/2 можно определить по следующей формуле:

NcZmp~add = п(п — 2)/8. (П. 4.1)

Количество сравнений в сети слияния, объединяющей две последовательности размерностью п/2 в одну размерностью п, по формуле:

N™Zp!e = nlog2n/2. (П.4.2)

Если исходный массив состоит из п> 4 элементов, количество сравнений нечетно-четной сети, выполняющей сортировку п элементов, будет больше, чем общее количество сравнений в двух нечетно-четных сетях и сети слияния:

М 1 ■ М even-add i iumer9e гтл л ол

Ncomp > 2 Ncomp + Ncomp , (n.4.3)

п(п — 1)/2 > 2 • п(п — 2)/8 + п(^2 п)/2, п/2 > log2 п.

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

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

К1 о-*-К2 0->

сс

К3 о->" К40->

сс

К50->

сс

К70->" К8о->

сс

Кп-3°~* гг

К„.2&+ сс

Кп-1 0-> Кп о—>

сс

сс —> сс

X

сс —> сс

сс —> сс

X

сс —> сс

• •

• •

• •

сс —> сс

X

сс —► сс

сс —> сс

X

сс —> сс

сс —> сс

X

сс —> сс