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

• Масюков Илья Игоревич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Масюков Илья Игоревич

Введение

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

1.1 Суперкомпьютеры. Архитектуры и принципы построения

1.2 Особенности архитектуры реконфигурируемых вычислительных систем

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

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

Выводы по главе

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

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

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

2.3 Исследование этапов метода

Выводы по главе

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

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

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

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

Выводы по главе

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

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

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

Выводы по главе

Заключение

Список литературы

Приложение А

Приложение Б

Приложение В. Листинг программы

Список сокращений и условных обозначений

РВС Реконфигурируемая вычислительная система

ПЛИС Программируемая логическая интегральная схема

МВС Многопроцессорные вычислительные системы

ВУ Вычислительное устройство

ЭВМ Электронно-вычислительная машина

МПВМИ Модуль поиска вершины с максимальной инцидентностью

МПСВ Модуль поиска смежной вершины

МПВСТЗ Модуль поиска вершины, смежной только заданной

МУОЗУ1 Модуль управления ОЗУ1

МУПОЗУ Модуль управления промежуточным ОЗУ

МПиПЗП Модуль поиска и присвоения задач ПЛИС

LAB Logic array blocks (массив логических блоков)

LUT Look-Up Table (таблица поиска или таблица истинности)

Введение

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

Актуальность темы исследования.

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

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

Исследованием реконфигурируемых вычислительных систем занимались как российские, так и зарубежные ученые: Каляев И.А., Левин И.И., Гузик В.Ф.,

Семерников Е.А., Шмойлов В.И., Ahmad B., Ahmadinia A., Arslan T., Ahmed G.A., Zamani M.S., Sedighi M., Mishra A.

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

Работа выполнена при поддержке Минобрнауки Российской Федерации в рамках в Госзадания №1.12.20Ф «Исследование алгоритмов, моделей и методов повышения эффективности функционирования сложных технических систем».

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

В соответствии с поставленной целью в работе решаются следующие основные задачи:

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

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

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

4. Экспериментальное исследование разработанного устройства, анализ полученных результатов и сравнение времени работы с существующими аппаратными средствами.

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

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

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

проектирования, проектирования ЭВМ, основы теории построения алгоритмов, теории графов, теории множеств, теории автоматов.

Научная новизна и положения, выносимые на защиту:

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

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

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

Практическая ценность результатов исследования:

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

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

3. Зарегистрирована программа для ЭВМ №2021661030 «Программа планирования конфигурации ПЛИС в системах реального времени», позволяющая сократить время расположения в 1,94 раз.

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

Реализация и внедрение. Результаты диссертационной работы внедрены в ООО ОКБ «Авиаавтоматика» в условиях опытно-промышленных испытаний устройства планирования программ в системах на кристалле, реализующего аппаратное ускорение поиска конфигурации системы на ПЛИС в режиме реального времени.

Предложенный метод, алгоритм и устройство расположения задач в реконфигурируемых вычислительных системах, используются в образовательном процессе кафедры «Вычислительная техника» Юго-Западного государственного университета в рамках дисциплин «ЭВМ и периферийные устройства» по направлению подготовки 09.03.01 и «Периферийные устройства» по направлению подготовки 09.04.01, что подтверждается соответствующими актами внедрения.

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.05 - «Элементы и устройства вычислительной техники и систем управления» проблематика, рассмотренная в диссертации, соответствует пунктам 1 и 2 паспорта специальности:

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

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

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Всероссийских и Международных конференциях в 2012-2021 годах: «Машиностроение и техно

сфера XXI века» (г. Донецк, 2012, 2013, 2015, 2016, 2017), «Информационно-измерительные диагностические и управляющие системы» (г. Курск, 2013, 2016), «Современные научные исследования» (г. Екатеринбург, 2014), «Интеллектуальные информационные системы: тенденции, проблемы, перспективы» (г. Курск, 2015), «Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений» (г. Курск, 2015, 2017, 2021), «Интеллектуальные и информационные системы» (г. Тула 2016, 2021), а также на научных семинарах кафедры «Вычислительная техника» Юго-Западного государственного университета (г. Курск, 2015-2021).

Личный вклад автора. Выносимые на защиту научные положения разработаны соискателем лично. В научных работах, выполненных в соавторстве, личный вклад соискателя состоит в следующем: описание метода устройства расположения задач в реконфигурируемых вычислительных системах [39, 64, 65, 67, 69, 71, 73, 74, 76, 78, 81, 83, 85, 90], алгоритм работы устройства расположения задач в РВС [39, 61, 62, 83, 85, 94, 104], разработка структурной и функциональной схемы устройства расположения задач в РВС [40, 58, 62, 94, 98, 112], разработка описания устройства расположения задач в РВС, на языке описания аппаратуры [104].

Публикации. По теме диссертации опубликованы 22 научные работы, в том числе 3 статьи в научных рецензируемых изданиях, входящих в перечень ВАК РФ, 2 работы, входящие в международную базу данных Scopus, получен 1 патент РФ на изобретение и 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка литературы, включающего 117 наименований, и приложений. Диссертационное исследование изложено на 152 страницах машинописного текста и содержит 52 рисунка, 8 таблиц.

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

основных направлений исследования.

1.1 Суперкомпьютеры. Архитектуры и принципы построения.

Суперкомпьютеры - специализированный класс

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

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

- Ops (operations per second) - количество операций в секунду для данных с фиксированной запятой;

- Flops (float operations per second) - количество операций в секунду для данных с плавающей запятой.

Существует три понятия о производительности суперкомпьютеров [2]:

- пиковая производительность - максимально теоретически возможная производительность суперкомпьютера;

- тестовая производительность - производительность, достигаемая при решении тестовой задачи;

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

Архитектура вычислительной системы - это совокупность ее свойств и характеристик [3]. Одной из первых архитектур вычислительной системы (ВС) является фон-неймоновская архитектура, предложенная Яношем Лайош Нейманом. Отличительной особенностью данной архитектуры является наличие

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

Следующим этапом развития архитектур суперЭВМ стало применение многопроцессорных вычислительных устройств и распараллеливание задач между ними. Однако, вопрос организации межпроцессорной связи, доступа к памяти и т.п. привел к появлению множества различных архитектур и их классификации [5].

Одной из классификаций многопроцессорных систем является Классификация М. Филина (M. Flynn) [6]. В основе классификации лежит понятие потока - последовательности команд и данных для процессора. Данная классификация является начальной при определении архитектуры ВС. Количество потоков команд и данных легли в основу разбиения ВС на четыре класса архитектуры:

- SISD (Single Instruction stream/Single Data stream) - одиночный поток команд и одиночный поток данных или ВС последовательного типа. Команды в устройстве обрабатываются последовательно, каждая команда соответствует данным из памяти данных. В подобных системах один поток данных передается из памяти данных, а один поток команд генерируется в устройстве управления. Примером систем, с приведенной архитектурой, являются CDC 6600, PDP-11, VAX 11/780.

- SIMD (Single Instruction stream/Multiple Data stream) - одиночный поток команд и множественный поток данных. Подобные ВС используют векторный набор команд, позволяющий выполнять параллельно одну арифметическую операцию над множеством данных из памяти данных. В таких системах одно управляющее устройство передает команды на каждый процессор, которые выполняют ее над своим набором данных. Примером данных систем являются матричные ВС ILLIACIV, ICLDAP, Goodyear MPP.

- MISD (Multiple Instruction stream/Single Data stream) - множественный поток команд и одиночный поток данных. К ним относятся отказоустойчивые ВС, избыточно выполняющие однотипные операции для отслеживания ошибок.

- MIMD (Multiple Instruction stream/ Multiple Data stream) - множественный поток команд и данных. В подобных ВС каждому процессору соответствует свой поток команд и данных, память может быть общей или распределенной, что позволяет работать процессорам асинхронно и независимо над решением общей задачи. Большинство современных суперЭВМ относятся к данному типу архитектуры. Пример подобной ВС служит Intel Xeon Phi, основанный на микроархитектуре Larrabee.

Однако представленная выше классификация, является в большинстве применений обобщенной. Поэтому появились другие классификации архитектур ВС, различающие их по числу процессоров, связи между ними, способу организации памяти и т.п. Например, для классификации многопроцессорных систем выделены два больших класса SMP (Symmetric Multi Processing) и MPP (Massive Parallel Processing) [7].

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

Архитектурой, призванной решить проблему SMP, является ccNUMA (Cache Coherent Non Uniform Memory Access) - NUMA с когерентностью кэш-памяти. В этой архитектуре память разделена физически между различными процессорами, но логически объединена в единое адресное поле. Это позволяет сохранить удобство программирования системы и увеличить масштабируемость. Однако из-за когерентности памяти, появляется ее деление на три уровня: кэш-память процессора, локальная оперативная память, удаленная оперативная память. Разница времени доступа к памяти с различных уровней достигает нескольких раз, что затрудняет создание высокоэффективных программ для подобных ВС.

Несмотря на данные ограничения, архитектура позволяет создавать ВС с 256 процессорами. Примерами таких систем являются SUN StarFire 15K, SGI Origin 3000, HP Superdome.

Проблемы SMP систем нивелируются в ВС с архитектурой MPP, представляющих собой множество процессоров с распределенной памятью, объединяемых между собой в вычислительные узлы. Узел состоит из оперативной памяти, нескольких процессоров, коммутаторов и устройств ввода-вывода. Процессоры в такой системе имеют доступ только к локальной памяти, а связь с другими узлами происходит за счет передачи сообщений. Это позволяет решить проблему когерентности и одновременного доступа к памяти. Такие системы имеют возможность объединения в вычислительное поле, состоящие из нескольких тысяч процессоров. Например, ASCI White содержит 8192 процессоров, а BlueMountain - 6144 процессоров. Однако для MPP системы необходима высокоэффективная коммутационная система. Существует множество вариантов соединения узлов (тор, полный граф, гиперкуб и т.д.), но в последнее время широкое распространение получила иерархическая система, так как позволяет организовать прямой доступ между различными узлами, не используя промежуточные узлы.

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

Также получили распространение PVP (Parallel Vector Processor) системы, входящие в класс MPP архитектур, отличительной особенностью которых является наличие векторно-конвейерных процессоров, выполняющих однотипную обработку векторов данных. Несколько таких процессоров способны работать с

одновременным доступом к памяти, при этом объединяться между собой по средствам коммутационной системы [8]. Примером данных систем являются суперкомпьютеры CRAY.

Одним из вариантов MPP архитектуры являются кластерные ВС. Кластер -это модульные серверные ВС, соединенные между собой в единое вычислительное поле за счет применение скоростного интерконнекта [9]. Основной идеей кластерной системы является использование в качестве узлов компьютеров различного класса. Данная отличительная особенность позволяет собирать относительно недорогие ВС. Интерконнект выполняется преимущественно за счет применения сетевых технологий соединения ВС, что также снижает конечную стоимость системы. Однако при необходимости обеспечить более высокую производительность коммутационной системы применяют более дорогостоящие решения, например Mellanox, Tofu Interconnect, EDR InfiniBand и т.п. К преимуществам кластеров относятся гибкость и масштабируемость. Однако в задачах, где критичен обмен данными между узлами, кластерные системы не показывают высокой производительности [10].

Дальнейшим развитием кластерных систем стали гибридные вычислительные системы (ГВС), где в узлах кластеров находятся дополнительные сопроцессоры высокоскоростной обработки данных. Самым распространенным акселератором является графический процессор (ГП), позволивший значительно ускорить процесс обработки графических данных [11]. Применение процессора в совокупности с ГП позволило повысить производительность суперкомпьютеров без эквивалентного увеличения потребляемой электроэнергии [12]. ГП представляет собой векторный многоядерный микропроцессор SMID класса, включающий несколько сотен потоковых процессоров с общей памятью. Представителем данного класса суперкомпьютеров является Titan, созданный фирмой Cray, включающий 18688 16-ядерных процессоров Opteron 2.200GHz и 14-ядерных вычислительных акселераторов на базе GPU NVIDIATeslaK20x.

Большинство суперкомпьютеров из списка ТОП-500 имеют кластерную архитектуру [13]. Из-за особенностей построения пиковая производительность

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

Перечисленные классы архитектур суперкомпьютеров используются в построении современных ВС, однако присущие им недостатки ведут к необходимости поиска новых подходов их построения. Ведется множество исследований, направленных на создание квантовых компьютеров [16], оптических компьютеров [17], биокомпьютеров [18] и т.п., но они далеки от массового применения. Однако существует подход построения ВС, основанный на принципе реконфигурации архитектуры под решаемую задачу. Данный принцип не позволяет решать всех проблем выше представленных подходов, но позволяет повысить производительность суперкомпьютеров [19].

1.2 Особенности архитектуры реконфигурируемых вычислительных систем

Для решения представленных в пункте 1.1 проблем кластерных суперЭВМ разработан подход с применением реконфигурируемой архитектуры в основе вычислительной системы (РВС), позволяющий адаптировать архитектуру вычислительного устройства под решаемую задачу, что минимизирует непродуктивные временные затраты на организацию вычислительного процесса, обеспечивая повышение производительности и эффективность использования энергии [20].

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

между ними. Основная идея РВС заключается в структурном решении информационного графа, а именно в аппаратной реализации задач и связей между ними [21].

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

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

Для создания РВС определены следующие требования к элементной базе

[23]:

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

- низкая стоимость, относительно существующих вычислительных аналогов;

- возможность реализации на аппаратном уровне узкоспециализированных вычислительных структур;

- возможность реализации распараллеливаемых структур;

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

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

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

Вторая проблема решается объединением нескольких плат в один вычислительный массив, каждая ячейка которого является базовым модулем. Но такое решение усугубляет первую проблему, так как дополнительно необходим межмодульный обмен. Частично данную проблему можно решить введением единого интерфейса как между отдельными ПЛИС на одном модуле, так и между модулями. Структура базового модуля описана на рисунке 1. 1 [25]

и

ЭГТ)

эп*

МАП,

о;

МАЛ,

МАП„

бм|

3

Ь

м, —►

м, —»■

К;

БМ;.

эгь

ЭГЬ

эпт,

МАПп

МАП,

МАПП

3

Ь

а) б)

Рисунок 1.1 - Структуры модулей: а - структура базового модуля, б -

обобщенная структура модульно-наращиваемой РВС

Все модули включают в себя макропроцессоры (на рисунке 1.1 - МАП^),

объединенные между собой коммутатором (второй уровень, на рисунке 1.1

обозначен К2). В свою очередь, макропроцессоры состоят из элементарных

процессоров (рисунок 1.1 ЭПи), соединенных еще одним коммутационным (первый

уровень, на рисунке 1.1 К:) устройством, что образует двухуровневую

коммутационную систему. Увеличение вычислительной мощности РВС

достигается за счет объединения нескольких модулей через коммутатор второго

уровня в единый вычислительный массив.

ПЛИС разрешающего поля соединены ортогональной системой между собой

с ближайшими физически расположенными на плате ПЛИС, что позволяет

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

Структурная реализация вычислений не требует использования большого объема памяти для хранения промежуточных данных, так как большая их часть не нужна для дальнейших вычислений. Данная особенность позволяет снизить общий объем требуемой памяти. Однако более критичным для распределенных вычислений, из-за множества параллельно выполняемых задач, является число блоков распределенной памяти. Для уменьшения объема внешних микросхем ОЗУ также используется внутренняя память ПЛИС.

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

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

Описанная архитектура и принципы построения вычислительных систем, в основе которых лежит ПЛИС, является одним из перспективных средств решения сильно связных задач. Она позволяет реализовать множество узкоспециализированных вычислителей для каждой задачи информационного графа на каждой итерации его решения, что позволяет повысить энергоэффективность и достичь практически линейного роста производительности от увеличения вычислительных ресурсов [28].

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

Список литературы

1. Малявко А.А. Суперкомпьютеры и системы. Построение вычислительных кластеров. Учебное пособие / А.А. Малявко, С.А. Менжулин. — Новосибирск: НГТУ, 2018. — 96 с.

2. Митропольский Ю.А. Мультиархитектурные вычислительные суперсистемы. Перспективы развития / Ю.А. Митропольский. — Москва: Техносфера, 2016. — 146 с.

3. Борзов Д.Б. Параллельные вычислительные системы (архитектура, принципы размещения задач) (монография) / Д.Б. Борзов, В.С. Титов. — Курск: изд-во ЮЗГУ, 2009. — 152 с.

4. Борзов Д.Б. Информатика. Учебное пособие / Д.Б. Борзов, И.Е. Чернецкая.

— Курск: изд-во ЮЗГУ, 2010. — 305 с.

5. Воеводин В.В. Параллельные вычисления / В.В. Воеводин, В.В. Воеводин.

— СПб.: БХВ-Петербург, 2004. — 608 с.

6. Flynn M. Very high-speed computing systems / M. Flynn // Proceedings of the IEEE. — 1966. — № 12 (54). — C.1901-1909.

7. René J.C. Server Architectures: Multiprocessors, Clusters, Parallel Systems, Web Servers, Storage Solutions / J.C. René. — North Dakota: Digital Press, 2004. — 784 с.

8. Hennessy J.L. Computer Architecture: A Quantitative Approach / J.L. Hennessy. — Burlington: Morgan Kaufmann, 2011. — 856 с.

9. Цилькер Б.Я. Организация ЭВМ и систем: Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. — СПб.: Питер, 2011. — 688 с.

10. Bader D.A. Cluster Computing: Applications / D.A. Bader, R. Pennington // The International Journal of High-Performance Computing Applications. — 2001. — № 2 (15). — C.181-185.

11. Czarnul P. Parallel Programming for Modern High Performance Computing Systems / P. Czarnul. — London: CRC Press, 2018. — 323 с.

12. Cai Y. GPU Computing and Applications / Y. Cai, S. See. — Berlin: Springer, 2015. — 280 с.

13. Top500 [Электронный ресурс] URL: www.top500.org

14. Kim J. High Performance Datacenter Networks: Architectures, Algorithms, and Opportunities / J. Kim. — San Rafael: Morgan & Claypool, 2011. — 115 с.

15. Воеводин В.В. Суперкомпьютеры и парадоксы неэффективности / B.D. Воеводин // Открытые системы. — 2009. — № 10. — C.17-20.

16. Feynman R.P. Simulating physics with computers / R.P. Feynman // International Journal of Theoretical Physics. — 1982. — № 21 (6). — C.467-488. doi.org/10.1007/BF02650179

17. Tucker R.S. The role of optics in computing / R.S. Tucker // Nature Photonics.

— 2010. — № 4. — C.405. doi.org/10.1038/nphoton.2010.162

18. Deamer D. A giant step towards artificial life? / D. Deamer // Trends in Biotechnology. — 2005. — № 23 (7). — C.336-338.

19. Реконфигурируемые вычислительные системы для решения вычислительно трудоемких задач / Н.Н. Дмитренко, И.А. Каляев, И.И. Левин, Е.А. Семерников // Научный сервис в сети интернет: решение больших задач: Всероссийская научная конференция / Новороссийск. — Новороссийск: Издательство Московского университета, 2008. — C.265-270.

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

21. Реконфигурируемые мультиконвейерные вычислительные структуры / И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов. — Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. — 344 с.

22. Левин И.И. Реализация итерационных методов решения систем линейных уравнений в задачах математической физики на реконфигурируемых вычислительных системах / И.И. Левин, А.И. Дордопуло, А.В. Пелипец // Вестник ЮУрГУ. Серия Вычислительная математика и информатика. — 2016. — № 5 (4).

— C.5-18.

23. Реконфигурируемые вычислительные системы на основе ПЛИС семейства Уп!ех-6 / И.А. Каляев, И.И. Левин, Е.А. Семерников, А.И. Дордопуло // Параллельные вычислительные технологии: Международная научная конференция / Москва. — Челябинск: Издательский центр ЮУрГУ, 2011. — С.203-210.

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

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

26. Средства программирования реконфигурируемых вычислительных систем на основе ПЛИС У1йех-7 с использованием софт-архитектур / [И.И. Левин, А.И. Дордопуло, В.Б. Коваленко, В.А. Гудков, А.А. Гуленок] // Вестник ЮжноУральского Государственного Университета. Серия: Вычислительная математика и информатика. — 2015. — № 4 (2). — С.20-32.

27. Современные высокопроизводительные вычислительные системы с реконфигурируемой архитектурой на основе ПЛИС ХШпх Уп!ех-7 и Уйех иЬ^са1е / И.И. Левин, И.А. Дордопуло, И.А. Каляев, Ю.И. Доронченко, М.К. Раскладкин // Суперкомпьютерные дни в России: Международная конференция / Москва. — Москва: Издательский дом "МГУ им. М.В. Ломоносова", 2015. — С.435-446.

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

29. Дордопуло А.И. Ресурсонезависимое программирование гибридных реконфигурируемых вычислительных систем / А.И. Дордопуло, И.И. Левин // Суперкомпьютерные дни в России: Международная конференция / Москва. — Москва: Издательский дом "МГУ им. М.В. Ломоносова", 2017. — С.714-723.

30. Перспективные высокопроизводительные реконфигурируемые вычислительные системы на основе ПЛИС У1йех-6 и У1йех-7 / И.И. Левин, И.А.

Каляев, И.А. Дордопуло, Е.А. Семерников // параллельные вычисления и задачи управления: Международная конференция / Москва. — Москва: Институт проблем управления им. В.А. Трапезникова РАН, 2012. — C.242-253.

31. Cray XD1 Supercomputer [Электронный ресурс] URL: http://www.hpc.unm.edu/~tlthomas/buildout/Cray_XD1_Datasheet.pdf

32. Maxwell - a 64 FPGA Supercomputer / R. Baxter, S. Booth, M. Bull, G. Cawood и др.// Second NASA/ESA Conference on Adaptive Hardware and Systems. — Edinburgh, 2007. DOI: 10.1109/AHS.2007.71

33. The FHPCA [Электронный ресурс] URL: www.fhpca.org

34. Implementation, performance, and science results from a 30.7 TFLOPS IBM BladeCenter cluster / C.A. Stewart, D.S. McCaulay, M.R. Link, G. Rodgers // Concurrency and Computation Practice and Experience. — 2009. — № 22 (2). — C.157-174. DOI:10.1002/cpe.1539

35. Hypercomputer System [Электронный ресурс] URL: http://www.StarBridgeSystems.com.

36. Sci Engines. COPACOBANA and RIVYERA [Электронный ресурс] URL: http://www.sciengines.com/technology-platform/sciengines-hardware/

37. DINIGroup. Big FPGA Boards: High Performance Computing. [Электронный ресурс] URL: http://www.dinigroup. com/

38. Chen Y. Multi-FPGA digital hardware design for detailed large-scale real-time electromagnetic transient simulation of power systems / Y. Chen, V. Dinavahi // IET Generation Transmission & Distribution. — 2013. — № 7 (5). — C.451-463. DOI:10.1049/iet-gtd.2012.0374

39. Masyukov I.I. Methods of Critical Systems Reconfiguration / D.B. Borzov, I.I. Masyukov, E.A. Titenko // 2018 International Russian Automation Conference (RusAutoCon). - Sochi, 2018. - Pp.1-5. DOI:10.1109/RUSAUTOCON.2018.8501613.

40. Masyukov I.I. Planning of Program Placement in Cubic Multiprocessor Systems / D.B. Borzov, I.I. Masyukov, S.A. Sizov // 2018 International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM). - Moscow, 2018. -Pp. 1-5. DOI:10.1109/ ICIEAM.2018.8728715.

41. Коновалов И.С. Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи о покрытии множества / И.С. Коновалов, С.С. Остапенко, В.Г. Кобак // Вестник Донского государственного технического университета. — 2017. — № 3 (90). — С137-144. https://doi.org/10.23947/1992-5980-2017-17-3-137-144

42. Кононов А.В. Приближенные алгоритмы для ЫР-трудных задач. Учебно-методическое пособие. / А.В. Кононов, П.А. Кононова. — Новосибирск: РИЦ НГУ, 2014. — 117 с.

43. Курейчик В.В. Алгоритмы разбиения графа на основе генетического поиска / В.В. Курейчик // Известия ТРТУ. — 1999. — № 3 (13). — С97-104.

44. Курейчик В.В. Двухуровневый алгоритм разбиения графа на части / В.В. Курейчик, Д.В. Заруба // Известия ЮФУ. Технические науки. — 2019. — № 2 (204). — С6-15.

45. Ватутин Э.И. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений / Э.И. Ватутин, В.С. Титов // Известия Южного федерального университета. Технические науки. — 2014. — № 12 (161). — С111-120.

46. Пат. № 2713757, МПК G06F 15/17. Реконфигурируемая вычислительная система / О.А. Будкина, К.И. Воротников, Ф.В. Демин, В.Н. Конотопцев, В.В. Парамонов, И.С. Сергеев, А.В. Симонов, А.Г. Титов, А.А. Цыбов. Заявитель и патентообладатель: Федеральное государственное унитарное предприятие «Научно-ислледовательский институт «Квант»». - №2019113296; заявл. 29.04.2019; опубл. 07.02.2020; Бюл. №4.

47. Пат. № 2699254, МПК G06F 15/16. Реконфигурируемая вычислительная система с многоуровневой подсистемой мониторинга и управления / О.А. Будкина, К.И. Воротников, Ф.В. Демин, В.В. Парамонов, А.В. Симонов, А.Г. Титов, А.А. Цыбов. Заявитель и патентообладатель: Федеральное государственное унитарное предприятие «Научно-ислледовательский институт «Квант»». - №2018138289; заявл. 30.10.2018; опубл. 04.09.2019; Бюл. №25.

48. Пат. № 182316, МПК G06F 15/16, G06F 17/00. Проблемно-ориентированное вычислительное устройство / К.И. Воротников, В.С. Горбунов, Ф.В. Демин, Л.Р. Карев, В.Н. Конотопцев, И.С. Сергеев, А.Г. Титов. Заявитель и патентообладатель: Фонд перспективных исследований. - №2018121753; заявл. 14.06.2018; опубл. 14.08.2018; Бюл. №23.

49. Пат. № 144358, МПК G06F 15/16. Вычислительный модуль / О.А. Будкина, К.И. Воротников, Т.М. Пестерева, А.В. Симонов, А.С. Степанов, А.Г. Титов. Заявитель и патентообладатель: Федеральное государственное унитарное предприятие «Научно-ислледовательский институт «Квант»». - №2014114410/08; заявл. 11.04.2014; опубл. 20.08.2014; Бюл. №23.

50. Пат. № 2572379, МПК G06F 3/12. Реконфигурируемое устройство аппаратной реализации генетического алгоритма / М.В. Ляшов, А.Н. Берёза, Ю.В. Алексеенко. Заявитель и патентообладатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Донской государственный технический университет» (ДГТУ). - №2014130458/08; заявл. 22.07.2014; опубл. 10.01.2016; Бюл. №1.

51. Пат. № 144357, МПК G06F 15/16. Реконфигурируемый вычислительный модуль / О.А. Будкина, К.И. Воротников, Т.М. Пестерева, К.И. Симонов, А.С. Степанов, А.Г. Титов. Заявитель и патентообладатель: Федеральное государственное унитарное предприятие «Научно-ислледовательский институт «Квант»». - №2014114409/08; заявл. 11.04.2014; опубл. 20.08.2014; Бюл. №23.

52. Пат. № 166961, МПК G06F 15/00. Вычислительный модуль / А.А. Выпазова, Н.А. Выпазова, В.Б. Евтухов, А.В. Симонов, А.С. Степанов, Е.В. Суслина, А.А. Цыбов. Заявитель и патентообладатель: Федеральное государственное унитарное предприятие «Научно-ислледовательский институт «Квант»». - №2016127261/08; заявл. 06.07.2016; опубл. 20.12.2016.

53. Пат. № 2502126, МПК G06F 15/00. Многопроцессорная вычислительная система / И.И. Левин, Л.И. Виневская. Заявитель и патентообладатель: Федеральное государственное автономное образовательное учреждение высшего

профессионального образования Южный федеральный университет. -№2012118775/08; заявл. 04.05.2012; опубл. 20.12.2013; Бюл. №35.

54. Пат. № 2282236, МПК G06F 15/16. Модуль многопроцессорной системы / И.И. Левин, Л.И. Виневская. Заявитель и патентообладатель: Научно-исследовательский институт многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета (НИИ МВС ТРТУ). - №2004136937/09; заявл. 16.12.2004; опубл. 20.08.2006; Бюл. №23.

55. Пат. № 2519387, МПК G06F 7/57, G06F 9/06. Способ и аппаратура для обеспечения поддержки альтернативных вычислений в реконфигурируемых системах-на-кристалле / Д.С. Артамонов, О.А. Вихров. Заявитель и патентообладатель: Министерство промышленности и торговли Российской Федерации. - №2012133011/08; заявл. 02.08.2012; опубл. 10.06.2014; Бюл. №16.

56. Пат. № 188978, МПК G06F 17/14. Унифицированная реконфигурируемая схема коммутации быстрого преобразования Фурье / П. С. Поперечный, И.Ю. Поперечная, Я.Я. Петрикович, Т.В. Солохина. Заявитель и патентообладатель: Акционерное общество Научно-производственный центр "Электронные вычислительно-информационные системы" (АО НПЦ "ЭЛВИС"). - №2018144349; заявл. 14.12.2018; опубл. 30.04.2019; Бюл. №13.

57. Пат. № 2461867, МПК G06F 7/50. Реконфигурируемый вычислительный конвейер / С.В. Дыдыкин, М.П. Авдеев, В.С. Попов, А.А. Холостов. Заявитель и патентообладатель: Государственная корпорация по атомной энергии «Росатом» -Госкорпорация «Росатом» Федеральное государственное унитарное предприятие «Российский Федеральный ядерный центр - Всероссийский научно-исследовательский институт экспериментальной физики - ФГУП «РФЯЦ-ВНИИЭФ». - №2011125953/08; заявл. 23.06.2011; опубл. 20.09.2012; Бюл. №26.

58. Пат. №2688236 Российская Федерация, МПК G06F 17/10. Устройство для подсчета минимального значения интенсивности размещения в многопроцессорных кубических циклических системах при однонаправленной передаче информации / Борзов Д.Б., Масюков И.И., Титенко Е.А.; заявитель и патентообладатель: Федеральное государственное бюджетное образовательное

учреждение высшего образования "Юго-Западный государственный университет" (ЮЗГУ). — №2018120597; заявл. 05.06.2018; опубл. 21.05.2019

59. Hopcroft J. Introduction to Automata Theory, Languages, and Computation / J. Hopcroft, R. Motwani, J. Ullman. — London: Pearson, 2006. — 560 с.

60. Андреев А.М. Многопроцессорные вычислительные системы. Теоретический анализ, математические модели и применение / А.М. Андреев, Г.П. Можаров, В.В. Сюзев. — Москва: МГТУ им. Н. Э. Баумана, 2011. — 336 с.

61. Масюков И.И. Алгоритм переразмещения подпрограмм в отказоустойчивых мультикомпьютерах / Ю.В. Соколова, Д.Б. Борзов, И.И. Масюков // Машиностроение и техносфера XXI века: сборник трудов XVIII международной научно-технической конференции. - Донецк, 2012. - С. 101-103.

62. Масюков И.И. Проектирование и реконфигурация систем логического управления высокой готовности / Д.Б. Борзов, И.И. Масюков, Д.А. Миронов // Машиностроение и техносфера XXI века: сборник статей научно-технической конференции. - Донецк, 2013. - С. 88-92.

63. Page D. Practical Introduction to Computer Architecture. Texts in Computer Science / D. Page. — London: Springer, 2009. — 647 с.

64. Масюков И.И. Метод устранения избыточных вычислений в многопроцессорных системах / Д.Б. Борзов, И.И. Масюков, Миронов Д. А. // Информационно-измерительные диагностические и управляющие системы: сборник материалов III международной научно-технической конференции. -Курск, 2013. - С. 57-61.

65. Масюков И.И. Методы аппаратной реализации планирования программ в многопроцессорных системах / Д.Б. Борзов, И.И. Масюков // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2015): материалы XII международной научно-технической конференции. - Курск, 2015. - С. 249-251.

66. Shiva S.G. Advanced Computer Architectures / S.G. Shiva. — Boca Raton: CRC Press, 2005. — 352 с.

67. Масюков И.И. Планирование загрузки процессоров в мультипроцессорных системах критического назначения / Д.Б. Борзов, И.И. Масюков // Известия Юго-Западного государственного университета. - 2018. - №26. - С. 168-175. DOI: 10.21869/2223-1560-2018-22-6-168-174.

68. Multicore Computing: Algorithms, Architectures, and Applications / S. Rajasekaran, L. Fiondella, M. Ahmed, R.A. Ammar. — Boca Raton: Chapman and Hall/CRC, 2013. — 452 с.

69. Масюков И.И. Использование модели, метода, алгоритма и устройства составления плана расположения задач в реконфигурируемых вычислительных системах / И.И. Масюков, Д.Б. Борзов // Интеллектуальные и информационные системы (Интеллект - 2021): сборник трудов всероссийской научно-технической конференции. - Тула, 2021. - С.150-152.

70. Масюков И.И. Проектирование и реконфигурация систем логического управления высокой готовности / Д.Б. Борзов, И.И. Масюков, Д.А. Миронов // Машиностроение и техносфера XXI века: сборник статей научно-технической конференции. - Донецк, 2013. - С. 88-92.

71. Масюков И.И. Общие положения устройства акселератора планирования программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Интеллектуальные информационные системы: тенденции, проблемы, перспективы: сборник статей III региональной заочной научно-практической конференции. - Курск, 2015. - С. 102-103.

72. Bobda C. Introduction to Reconfigurable Computing / C. Bobda. — Berlin: Springer, 2007. — 375 с.

73. Масюков И.И. Применение планирования конфигурации ПЛИС в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Интеллектуальные и информационные системы (Интеллект - 2016): сборник трудов всероссийской научно-технической конференции. - Тула, 2016. - С.226-227.

74. Масюков И.И. Подход к реализации устройства планирования программ в ПЛИС / И.И. Масюков, Д.Б. Борзов // Современные научные исследование:

инновации и опыт: III Международная научно-практическая конференция. -Екатеринбург, 2014. - С.83-84.

75. Schneider Beck Fl. A.C. Dynamic reconfigurable architectures and transparent optimization techniques / A.C. Schneider Beck Fl., L. Carro. — Berlin: Springer, 2010. — 194 с.

76. Масюков И.И. Подход к задаче планирования размещения программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Машиностроение и техносфера ХХ1 века: сборник трудов XXII международной научно-технической конференции. - Донецк, 2015. - С.10-12.

77. Cardoso J.M. Reconfigurable Computing / J.M. Cardoso, M. Hubner. — Berlin: Springer, 2011. — 308 с.

78. Масюков И.И. Планирование размещения программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Машиностроение и техносфера ХХ1 века: сборник статей XXIII международной научно-технической конференции. - Донецк, 2016. - С.12-14.

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

80. Кормен Т.Х. Алгоритмы. Построение и анализ / Т.Х. Кормен, Ч.И. Лейзерсон. — Москва: Вильямс, 2019. — 1328 с.

81. Масюков И.И. Общие положения о перспективах развития и архитектуре реконфигурируемых вычислительных систем / И.И. Масюков, Д.Б. Борзов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2017): сборник материалов XIII международной научно-технической конференции. -Курск, 2017. - С. 237-239.

82. Дасгупта C. Алгоритмы / C. Дасгупта, Х. Пападимитриу, У. Вазирани. — Москва: МЦНМО, 2014. — 319 с.

83. Масюков И.И. Математическая модель и алгоритм устройства планирования программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Бюллетень науки и практики. - 2016. - №5. - С.40-44.

84. Еремеев А.В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А.В. Еремеев, Л.А. Заозерская, А.А. Колоколов // Дискретный анализ и исследование операций. — 2000. — № 2. — C.22-46.

85. Масюков И.И. Математическая модель и аппаратно-ориентированный алгоритм планирования размещения программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов, Титов Д.В., Соколова Ю.В. // Труды МАИ. - 2021. - №119. DOI: 10.34759/trd-2021-119-13.

86. Epp S.S. Discrete mathematics with applications / S.S. Epp. — Boston: Cengage Learning, 2020. — 1057 с.

87. Белоусов А.И. Дискретная математика / А.И. Белоусов, С.Б. Ткачев. — Москва: Издательство МГТУ им. Н. Э. Баумана, 2015. — 744 с.

88. Лекции по дискретной математике / М.Н. Вялый, В.В. Подольский, А.А. Рубцов и т.д. — Москва: Изд. дом Высшей школы экономики, 2021. — 496 с.

89. Матросов В.Л. Математическая логика / В.Л. Матросов, М.С. Мирзоев. — Москва: Прометей, 2020. — 229 с.

90. Масюков И.И. Реконфигурируемая вычислительная система на базе ПЛИС. Метод поиска конфигурации / И.И. Масюков, Д.Б. Борзов // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание - 2021): материалы XVI международной научно-технической конференции. - Курск, 2021. - С.177-179.

91. Марчук Г.И. Методы вычислительной математики / Г.И. Марчук. — Санкт-Петербург: Лань, 2009. — 608 с.

92. Прокушев Л.А. Дискретная математика. Основы теории графов и алгоритмизации задач / Л.А. Прокушев. — Санкт-Петербург: СПбГУАП, 2000. — 82 с.

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

94. Масюков И.И. Программная модель алгоритма планирования размещения программ в системах на кристалле / И.И. Масюков, Д.Б. Борзов // Машиностроение и техносфера ХХ1 века: сборник статей XXIV международной научно-технической конференции. - Донецк, 2017. - С.154-155.

95. Stephens R. Essential Algorithms: A Practical Approach to Computer Algorithms / R. Stephens. — Hoboken: Wiley, 2013. — 624 с.

96. Bhargava A. Grokking algorithms: an illustrated guide for programmers and other curious people / A. Bhargava. — Shelter Island: Manning Publications, 2016. — 256 с.

97. Клейнберг Д. Алгоритмы: разработка и применение. Классика Computers Science / Д. Клейнберг, Е. Тардос. — СПб: Питер, 2016. — 800 с.

98. Масюков И.И. Структурная схема устройства планирования конфигурации ПЛИС / И.И. Масюков, Д.Б. Борзов // Информационно-измерительные диагностические и управляющие системы (Диагностика - 2016): сборник материалов IV региональной научно-технической конференции. - Курск, 2016. - С. 89-91.

99. Антипенский Р.В. Схемотехническое проектирование моделирование радиоэлектронных устройств / Р.В. Антипенский, А.Г. Фадин. — Москва: Техносфера, 2007. — 128 с.

100. Пат. №2688236 Российская Федерация, МПК G06F 17/10. Устройство для подсчета минимального значения интенсивности размещения в многопроцессорных кубических циклических системах при однонаправленной передаче информации / Борзов Д.Б., Масюков И.И., Титенко Е.А.; заявитель и патентообладатель: Федеральное государственное бюджетное образовательное учреждение высшего образования "Юго-Западный государственный университет" (ЮЗГУ). — №2018120597; заявл. 05.06.2018; опубл. 21.05.2019.

101. Ушенина И.В. Проектирование цифровых устройств на ПЛИС / И.В. Ушенина. — Санкт-Петербург: Лань, 2019. — 408 с.

102. Kilts S. Advanced FPGA Design: Architecture, Implementation, and Optimization / S. Kilts. — River Street Hoboken NJ: Wiley-IEEE Press, 2007. — 352 с.

103. Readler B. Verilog by Example: A Concise Introduction for FPGA Design / B. Readler. — New York: Full Arc Press, 2011. — 124 с.

104. Масюков И.И. Борзов Д.Б. Программа планирования конфигурации ПЛИС в системах реального времени / Свидетельство о государственной регистрации программы для ЭВМ № 2021661030, заявл. 30.06.2021, опубл. 05.07.2021.

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

106. Chu P.P. FPGA Prototyping by Verilog Examples / P.P. Chu. — Hoboken: Wiley-Interscience, 2008. — 528 с.

107. Ульман Д.Д. Введение в теорию автоматов, языков и вычислений / Д.Д. Ульман, Д.Э. Хопкрофт. — Москва: Вильямс, 2016. — 528 с.

108. Брауэр В. Введение в теорию конечных автоматов / В. Брауэр. — Москва: ЁЁ Медиа, 2012. — 272 с.

109. MAX 10 FPGA Device Architecture [Электронный ресурс] URL: https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/max-

10/m10_architecture.pdf

110. Simpson P.A. FPGA Design / P.A. Simpson. — Berlin: Springer, 2015. —

260 с.

111. Стешенко В.Б. Плис фирмы "ALTERA". Элементная база, система проектирования и языки описания аппаратуры / В.Б. Стешенко. — Москва: ДМК Пресс, 2016. — 576 с.

112. Масюков И.И. Метод и устройство расположения задач в реконфигурируемых вычислительных системах / И.И. Масюков // Труды МАИ. -2021. - №120. D0I:10.34759/trd-2021-120-13.

113. Intel Quartus User Guides [Электронный ресурс] URL: https://www.intel.com/content/www/us/en/programmable/support/support-resources/support-centers/quartus-support.html

114. Churiwala S. Principles of VLSI RTL Design / S. Churiwala, S. Garg. — Berlin: Springer, 2011. — 192 с.

115. ModelSim User's Manual [Электронный ресурс] URL: https://www.microsemi.com/document-portal/doc_view/131619-modelsim-user

116. Hassan A. NoC-DPR: A new simulation tool exploiting the Dynamic Partial Reconfiguration (DPR) on Network-on-Chip (NoC) based FPGA / A. Hassan, H. Mostafa, H.A. Fahmy // Integration. — 2018. — № 63. — C.204-212. doi.org/10.1016/j.vlsi.2018.04.003

117. Using Graph Isomorphism for Mapping of Data flow Applications on Reconfigurable Computing Systems / A. Mishra, M. Agarwa, A.R. Asati, K.S. Raju // Microprocessors and Microsystems. — 2017. — № 51. — C.343-355. doi.org/10.1016/j.micpro.2016.12.008

11б

Приложение А

117

Приложение Б

Приложение В. Листинг программы

module top_level (

input wire CLK, START,

input wire [7:0] QUANTITY_VERTEX, input wire [7:0] SIZE_FPGA,

input wire [7:0] IN_DATA_RAM_INPUT_LINE, ADDRES_RAM_INPUT_LINE, input wire WE_RAM_INPUT_LINE,

input wire [7:0] IN_DATA_RAM2_INPUT_LINE, ADDRES_RAM2_INPUT_LINE, input wire WE_INPUT_RAM2,

output wire algorithm_done,

output wire [15:0] OUT_DATA_OUT_RAM,

output wire [7:0] ADDRES_OUT_RAM

);

wire error;

wire [7:0] ADDRES_RAM_MODULE_LINE, ADDRES_RAM2_MODULE_LINE, ADDRES_INPUT_RAM, ADDRES_INPUT_RAM2, ADDRES_INPUT_RAM3; wire [7:0] IN_DATA_INPUT_RAM, IN_DATA_INPUT_RAM3,

IN_DATA_RAM_MODULE_LINE;

wire [15:0] IN_DATA_OUT_RAM;

wire WE_INPUT_RAM, WE_RAM_MODULE_LINE, WE_INPUT_RAM3, WE_OUT_RAM; wire [7:0] vertex_incidence, data_out_hanging_virtex;

wire [7:0] OUT_DATA_INPUT_RAM, OUT_DATA_INPUT_RAM2, OUT_DATA_INPUT_RAM3; wire ready_find_max_incidence, ready_find_max_edge;

wire [7:0] vertex_max_incidence, adjacent_vertex, data_hanging_virtex, input_module_addr;

wire [7:0] input_module_data, addres_from_max_incidence, addres_from_max_edge, addres_from_hanging_virtex, data_to_find_hanging_virtex;

wire [7:0] data_to_fifo, data_FIFO;

wire [8:0] incidence_vertex_cnt;

wire read_FIFO, read_FIFO_1, read_FIFO_2; wire data_ready_RAM1;

wire ready_find_hanging_virtex, all_ready_find_hanging_virtex;

wire clear_reference_vertex, ready_clear_reference_vertex;

wire enable_FIFO, clear_FIFO, whrite_FIFO, empty_FIFO, full_FIFO, fifo_ready;

wire RE_from_max_incidence, RE_from_max_edge, RE_from_hanging_virtex,

ready_to_find_hanging_virtex, RE_RAM1, all_data_read_fifo;

wire check_RAM1_empty, clear_black_list, add_vertex_of_FIFO_in_black_list,

clear_vertex_of_FIFO_in_RAM1, start_clear_vertex_from_FIFO;

wire RAM1_empty, RAM1_empty_busy, clear_black_list_busy, black_list_empty,

add_vertex_of_FIFO_in_black_list_busy;

wire start_find_max_edge_2, start_find_max_incidence_2;

wire start_find_max_edge, start_find_max_incidence, algorithm_start;

wire add_max_edge_vertex_in_black_list_busy, add_max_edge_vertex_in_black_list;

wire no_fit;

assign start_find_max_edge = ready_find_max_incidence || start_find_max_edge_2; assign start_find_max_incidence = algorithm_start || start_find_max_incidence_2; assign read_FIFO = read_FIFO_1 || read_FIFO_2;

assign WE_INPUT_RAM = WE_RAM_INPUT_LINE ? WE_RAM_INPUT_LINE : WE_RAM_MODULE_LINE;

assign ADDRES_INPUT_RAM = WE_RAM_INPUT_LINE ? ADDRES_RAM_INPUT_LINE : ADDRES_RAM_MODULE_LINE;

assign IN_DATA_INPUT_RAM = WE_RAM_INPUT_LINE ? IN_DATA_RAM_INPUT_LINE : IN_DATA_RAM_MODULE_LINE;

assign ADDRES_INPUT_RAM2 = WE_INPUT_RAM2 ? ADDRES_RAM2_INPUT_LINE : ADDRES_RAM2_MODULE_LINE;

INPUT_RAM RAM1(.address(ADDRES_INPUT_RAM), .clock(CLK),

.data(IN_DATA_INPUT_RAM), .wren(WE_INPUT_RAM), .q(OUT_DATA_INPUT_RAM));

INPUT_RAM RAM2(.address(ADDRES_INPUT_RAM2), .clock(CLK),

.data(IN_DATA_RAM2_INPUT_LINE), .wren(WE_INPUT_RAM2),

.q(OUT_DATA_INPUT_RAM2));

INPUT_RAM RAM3(.address(ADDRES_INPUT_RAM3), .clock(CLK),

.data(IN_DATA_INPUT_RAM3), .wren(WE_INPUT_RAM3), .q(OUT_DATA_INPUT_RAM3));

RAM_OUT RAM_OUT(.address(ADDRES_OUT_RAM), .clock(CLK),

.data(IN_DATA_OUT_RAM), .wren(WE_OUT_RAM), .q(OUT_DATA_OUT_RAM));

sync_start sync_start(

.clk(CLK), .start(START), .algorithm_start(algorithm_start)

);

find_max_incidence find_max_incidence(

.clk(CLK), .start( start_find_max_incidence),

.data_from_RAM(input_module_data), .quantity_vertex(QUANTITY_VERTEX),

.data_ready_RAM1(data_ready_RAM1),

// output

.addres_to_RAM(addres_from_max_incidence), .RE(RE_from_max_incidence),

.vertex_max_incidence(vertex_max_incidence),

.ready(ready_find_max_incidence),

.incidence(vertex_incidence)

);

find_max_edge find_max_edge(

.clk(CLK), .start( start_find_max_edge), .vertex_max_incidence (vertex_max_incidence), .quantity_vertex(QUANTITY_VERTEX), .data_RAM(input_module_data), .data_ready_RAM1(data_ready_RAM1), // output

.adjacent_vertex(adjacent_vertex),

.addr_to_RAM(addres_from_max_edge), .RE(RE_from_max_edge), .ready(ready_find_max_edge)

);

rule_find_hanging_virtex rule_find_hanging_virtex ( // input .clk(CLK),

.ready(ready_find_hanging_virtex), .all_ready(all_ready_find_hanging_virtex), .data_max_incidence(vertex_max_incidence), .data_max_edge(adjacent_vertex), .ready_max_incidence(ready_find_max_incidence), .ready_max_edge(ready_find_max_edge), //output

.data_to_find_hanging_virtex(data_to_find_hanging_virtex), .ready_to_find_hanging_virtex(ready_to_find_hanging_virtex), .ready_find_haning_vertex(ready_find_haning_vertex)

);

find_hanging_virtex find_hanging_virtex ( //input

.clk(CLK), .quantity_vertex(QUANTITY_VERTEX),

.start(ready_to_find_hanging_virtex), .reference_virtex(data_to_find_hanging_virtex), .data_max_edge(adjacent_vertex), .data_max_incidence(vertex_max_incidence), .data_RAM(input_module_data), .data_ready_RAM1(data_ready_RAM1), // Output

.addr_to_RAM(addres_from_hanging_virtex), .RE(RE_from_hanging_virtex), .ready(ready_find_hanging_virtex), .all_ready(all_ready_find_hanging_virtex), .hanging_virtex(data_out_hanging_virtex)

);

addres_from_module_to_RAM1 addres_from_module_to_RAM1( .clk(CLK),

.RE_from_max_incidence(RE_from_max_incidence), .RE_from_max_edge(RE_from_max_edge),

.RE_from_hanging_virtex(RE_from_hanging_virtex), .addres_from_max_incidence(addres_from_max_incidence), .addres_from_max_edge(addres_from_max_edge),

.addres_from_hanging_virtex(addres_from_hanging_virtex), //output

.RE(RE_RAM1), .input_module_addr(input_module_addr)

);

data_to_RAM3 data_to_RAM3( .clk(CLK),

.data_max_edge(adjacent_vertex), .ready_max_edge(ready_find_max_edge), .data_to_find_hanging_virtex(data_out_hanging_virtex), .ready_to_find_hanging_virtex(ready_find_hanging_virtex),

.data_RAM3(OUT_DATA_INPUT_RAM3),

.clear_RAM3(clear_FIFO),

.read_fifo (read_FIFO),

.cnt_vertex_in_RAM3(), .fifo_ready (fifo_ready), .data_out(data_FIFO),

.empty_FIFO(empty_FIFO), .all_data_read_fifo(all_data_read_fifo),

.WE(WE_INPUT_RAM3),

.data_from_RAM3(IN_DATA_INPUT_RAM3),

.addr_RAM3(ADDRES_INPUT_RAM3)

);

cnt_incidence_vertex cnt_incidence_vertex( .clk(CLK),

.vertex_ready(ready_find_max_incidence), .ready_find_max_edge(ready_find_max_edge),

.ready_find_haning_vertex(ready_find_haning_vertex),

.num_incidence_vertex(vertex_incidence),

.no_fit(no_fit),

.cnt_incidence_vertex(incidence_vertex_cnt), .error()

);

data_to_RAM1 data_to_RAM1( .clk(CLK),

.input_module_addr(input_module_addr), .RE(RE_RAM1),

.input_FIFO_data(data_FIFO), .input_data_RAM1(OUT_DATA_INPUT_RAM),

.QUANTITY_VERTEX(QUANTITY_VERTEX),

.vertex_max_incidence(vertex_max_incidence), .adjacent_vertex(adjacent_vertex), .FIFO_ready(fifo_ready), .all_data_read_fifo(all_data_read_fifo),

.check_RAM1_empty(check_RAM1_empty), .clear_black_list(clear_black_list), .add_vertex_of_FIFO_in_black_list(add_vertex_of_FIFO_in_black_list), .clear_vertex_of_FIFO_in_RAM1(clear_vertex_of_FIFO_in_RAM1),

.add_max_edge_vertex_in_black_list(add_max_edge_vertex_in_black_list), .add_max_edge_vertex_in_black_list_busy(add_max_edge_vertex_in_black_list_busy),

.clear_reference_vertex(clear_reference_vertex),

.out_data_of_RAM1(IN_DATA_RAM_MODULE_LINE), .out_addr_RAM1(ADDRES_RAM_MODULE_LINE),

.out_data_of_RAM1_from_module(input_module_data),

.WE(WE_RAM_MODULE_LINE), .data_ready(data_ready_RAM1),

.FIFO_en(read_FIFO_1), .start_clear_vertex_from_FIFO(start_clear_vertex_from_FIFO),

.RAM1_empty(RAM1_empty), .RAM1_empty_busy(RAM1_empty_busy), .clear_black_list_busy(clear_black_list_busy), .black_list_empty(black_list_empty),

.add_vertex_of_FIFO_in_black_list_busy(add_vertex_of_FIFO_in_black_list_busy), .ready_clear_reference_vertex(ready_clear_reference_vertex)

);

check_size_fpga check_size_fpga( .clk(CLK),

.quantity_vertex (QUANTITY_VERTEX), .reference_vertex(vertex_max_incidence), .all_ready_find_hanging_virtex (all_ready_find_hanging_virtex),

.empty_FIFO(empty_FIFO), .fifo_ready(fifo_ready), .all_data_read_fifo(all_data_read_fifo),

.data_FIFO(data_FIFO),

.data_RAM2(OUT_DATA_INPUT_RAM2),

.size_fpga(SIZE_FPGA),

.cnt_incidence_vertex(incidence_vertex_cnt),

.RAM1_empty(RAM1_empty), .RAM1_empty_busy(RAM1_empty_busy), .clear_black_list_busy(clear_black_list_busy), .black_list_empty(black_list_empty), .add_vertex_of_FIFO_in_black_list_busy(add_vertex_of_FIFO_in_black_list_busy), .start_clear_vertex_from_FIFO(start_clear_vertex_from_FIFO), .ready_clear_reference_vertex(ready_clear_reference_vertex),

.add_max_edge_vertex_in_black_list(add_max_edge_vertex_in_black_list), .add_max_edge_vertex_in_black_list_busy(add_max_edge_vertex_in_black_list_busy),

.read_FIFO(read_FIFO_2), .clear_FIFO(clear_FIFO),

.addr_RAM2(ADDRES_RAM2_MODULE_LINE),

.addr_RAM_OUT (ADDRES_OUT_RAM), .data_RAM_OUT (IN_DATA_OUT_RAM), .WE_DATA_OUT (WE_OUT_RAM),

.check_RAM1_empty(check_RAM1_empty), .clear_black_list(clear_black_list), .add_vertex_of_FIFO_in_black_list(add_vertex_of_FIFO_in_black_list), .clear_vertex_of_FIFO_in_RAM1(clear_vertex_of_FIFO_in_RAM1), .clear_reference_vertex(clear_reference_vertex),

.start_find_max_edge_2(start_find_max_edge_2), .start_find_max_incidence_2(start_find_max_incidence_2),

.algorithm_done(algorithm_done), .error(error), .no_fit(no_fit), .fit()

);

endmodule

module addres_from_module_to_RAM1 ( input wire clk,

input wire RE_from_max_incidence, RE_from_max_edge, RE_from_hanging_virtex,

input wire [7:0] addres_from_max_incidence, addres_from_max_edge, addres_from_hanging_virtex,

output reg RE,

output reg [7:0] input_module_addr

);

reg [7:0] sm;

initial begin

sm <= 0; RE <= 0;

input_module_addr <= 8'd0;

end

always @(posedge clk) begin

case (sm)

8'd0: begin

if(RE_from_max_incidence) begin

input_module_addr <= addres_from_max_incidence; RE <= 1; sm <= 1;

end

else if(RE_from_max_edge) begin

input_module_addr <= addres_from_max_edge; RE <= 1; sm <= 1;

end

else if(RE_from_hanging_virtex) begin

input_module_addr <= addres_from_hanging_virtex; RE <= 1; sm <= 1;

end

else begin

input_module_addr <= 8'd0; RE <= 0; sm <= 0;

end

end

8'd1:begin

RE <= 0; sm <= 2;

end

8'd2: begin

sm <= 0;

end endcase

end

endmodule

module check_size_fpga ( input wire clk,

input wire [7:0] quantity_vertex, reference_vertex,

input wire [7:0] size_fpga_LE, size_fpga_RAM, size_fpga_DSP,

input wire [8:0] cnt_incidence_vertex,

input wire all_ready_find_hanging_virtex,

output reg [7:0] addr_RAM2,

input wire [7:0] data_RAM2,

input wire empty_FIFO,

output reg clear_FIFO,

output reg read_FIFO,

input wire [7:0] data_FIFO,

input wire fifo_ready, all_data_read_fifo,

output reg check_RAM1_empty,

input wire RAM1_empty, RAM1_empty_busy,

output reg clear_black_list,

input wire black_list_empty, clear_black_list_busy,

output reg clear_reference_vertex,

input wire start_clear_vertex_from_FIFO,

input wire ready_clear_reference_vertex,

output reg add_vertex_of_FIFO_in_black_list,

input wire add_vertex_of_FIFO_in_black_list_busy,

input wire add_max_edge_vertex_in_black_list_busy,

output reg add_max_edge_vertex_in_black_list,

output reg WE_DATA_OUT,

output reg [7:0] addr_RAM_OUT,

output reg [15:0] data_RAM_OUT,

output reg clear_vertex_of_FIFO_in_RAM1,

output reg start_find_max_edge_2, start_find_max_incidence_2, algorithm_done, error, no_fit,

fit);

reg [8:0] tmp_size_fpga_LE, tmp_size_fpga_RAM, tmp_size_fpga_DSP; reg add_reference_vertex;

reg no_first_round, tmp_no_first_round, tmp_all_data_read_fifo, first_round; reg [7:0] mass_posted_vertex [15:0]; reg [3:0] cnt_mass;

reg [7:0] addr_to_mass_posted_vertex; reg [7:0] cnt_posted_vertex; reg algorithm_done_2, flag_change_nomber; reg [7:0] tmp_addr_RAM_OUT; reg [7:0] num_fpga;

reg [8:0] all_vertex_weight_LE, tmp_all_vertex_weight_LE; reg [8:0] all_vertex_weight_RAM, tmp_all_vertex_weight_RAM; reg [8:0] all_vertex_weight_DSP, tmp_all_vertex_weight_DSP; reg [7:0] current_size_fpga_LE, tmp_current_size_fpga_LE; reg [7:0] current_size_fpga_RAM, tmp_current_size_fpga_RAM; reg [7:0] current_size_fpga_DSP, tmp_current_size_fpga_DSP; reg [2:0] cnt_pause_RAM; reg [7:0] sm; initial begin

read_FIFO <= 0; clear_FIFO <= 0;

addr_RAM2 <= 0; no_fit <= 0; fit <= 0;

addr_RAM_OUT <= 0; data_RAM_OUT <= 0; WE_DATA_OUT <= 0; no_first_round <= 0; check_RAM1_empty <= 0; clear_black_list <= 0; add_vertex_of_FIFO_in_black_list <= 0; clear_vertex_of_FIFO_in_RAM1 <= 0; clear_reference_vertex <= 0; start_find_max_edge_2 <= 0; start_find_max_incidence_2 <= 0; algorithm_done <= 0; add_max_edge_vertex_in_black_list <= 0; tmp_addr_RAM_OUT <= 0; add_reference_vertex <= 0; error <= 0; num_fpga <= 0; all_vertex_weight_LE <= 0; tmp_all_vertex_weight_LE <= 0; all_vertex_weight_RAM <= 0; tmp_all_vertex_weight_RAM <= 0; all_vertex_weight_DSP <= 0; tmp_all_vertex_weight_DSP <= 0; tmp_size_fpga_LE <= 0; tmp_size_fpga_RAM <= 0; tmp_size_fpga_DSP <= 0; first_round <= 0; tmp_all_data_read_fifo <= 0; cnt_pause_RAM <= 1; cnt_mass <= 0;

addr_to_mass_posted_vertex <= 0; cnt_posted_vertex <= 0; algorithm_done_2 <= 0; addr_to_mass_posted_vertex <= 0; flag_change_nomber <= 0; tmp_no_first_round <= 0; current_size_fpga_LE <= 0; tmp_current_size_fpga_LE <= 0; current_size_fpga_RAM <= 0; tmp_current_size_fpga_RAM <= 0; current_size_fpga_DSP <= 0; tmp_current_size_fpga_DSP <= 0; sm <= 0;

end

always @(posedge clk) begin case(sm)

8'd0: begin

if(!first_round) begin

current_size_fpga_LE <= size_fpga_LE;

current_size_fpga_RAM <= size_fpga_RAM; current_size_fpga_DSP <= size_fpga_DSP; first_round <= 1;

end

tmp_size_fpga_LE <= 0; tmp_size_fpga_RAM <= 0; tmp_size_fpga_DSP <= 0; no_fit <= 1'b0; fit <= 1'b0;

if(all_ready_find_hanging_virtex) begin error <= 0; sm<= 1;

end

end

8'd1: begin

if(all_ready_find_hanging_virtex) sm <= 2;

end

8'd2: begin

if(add_reference_vertex) begin sm <= 5;

end

else begin

addr_RAM2 <= |3'd000,reference_vertex[7:3]|; if(cnt_pause_RAM[2]) begin cnt_pause_RAM <= 1; sm <= 3;

end

else begin

cnt_pause_RAM <= cnt_pause_RAM - 1; sm <= 2;

end

end

end

8'd3: begin

all_vertex_weight_LE <= all_vertex_weight_LE + data_RAM2; sm <= 80;

end

8'd80: begin

addr_RAM2 <= |3'd000,reference_vertex[7:3]| + quantity_vertex; if(cnt_pause_RAM[2]) begin cnt_pause_RAM <= 1; sm <= 81;

end

else begin

cnt_pause_RAM <= cnt_pause_RAM - 1; sm <= 80;

end

end

8'd81: begin

all_vertex_weight_RAM <= all_vertex_weight_RAM + data_RAM2; sm <= 82;

end

8'd82: begin

addr_RAM2 <= |3'd000,reference_vertex[7:3]| + (quantity_vertex << 1); if(cnt_pause_RAM[2]) begin cnt_pause_RAM <= 1; sm <= 83;

end

else begin

cnt_pause_RAM <= cnt_pause_RAM - 1; sm <= 82;

end

end

8'd83: begin

all_vertex_weight_DSP <= all_vertex_weight_DSP + data_RAM2; sm <= 4;

end

8'd4: begin if(

end else begin

if(empty_FIFO) begin sm <= 10;

end

else begin

sm <= 5;

end

end

end

8'd5: begin

read_FIFO <= 1; sm <= 6;

end

8'd6: begin

read_FIFO <= 0; if(fifo_ready) begin

if(all_data_read_fifo) begin

tmp_all_data_read_fifo <= 1;

(all_vertex_weight_LE > current_size_fpga_LE) || (all_vertex_weight_RAM > current_size_fpga_RAM) || (all_vertex_weight_DSP > current_size_fpga_DSP)) begin if(current_size_fpga_LE == size_fpga_LE) begin error <= 1; sm <= 0;