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

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

Задачи разбиения информационного графа на подграфы, оценка требуемых аппаратных ресурсов, занимаемых задачами, и конфигурация РВС выполняются на хост ЭВМ.
Из-за количества задач и связей между ними, используемых и доступных ресурсов ПЛИС, необходимо расположение задач между микросхемами.
В результате обзора РВС сделан вывод, что задачи, имеющие максимальное количество передаваемых между собой данных, следует располагать на одной ПЛИС, сократив нагрузку на коммутационную систему. Однако из-за конечности ресурсов ПЛИС, количества задач и их соединений, необходимо создать метод, правила и этапы которого позволят снизить вычислительную сложность алгоритма.
Для расположения задач в РВС существуют следующие методы: метод ветвей и границ, генетический алгоритм, гильотинный разрез, алгоритм имитации отжига, муравьиный алгоритм, метод роя частиц, метод пчелиного роя. К основному недостатку вышеперечисленных методов и алгоритмов при расположении задач в РВС относят большую вычислительную сложность, не допускающую их решение в хост ЭВМ, выполняющей задачу разбиения информационного графа на подграфы, а также функции организации работы системы, обработки сигналов ввода-вывода ввиду работы в режиме реального времени.
Аппаратные средства расположения задач на реконфигурируемом поле или обладают большим количеством операций перебора, увеличивающих время расположения [Amr Hassan, 2018], [Ashish Mishra, 2016] или не применимы к обозначенной в данной работе задаче [Zhi Chen, 2013].
Таким образом, разработка метода, алгоритма и устройства расположения задач в РВС является актуальной.
Во второй главе разработан метод расположения задач в РВС.
Опишем расположение задач в реконфигурируемых вычислительных
неориентированным, представляется = ( , ), где ∈ – номер задачи, =
системах. Подграф задачи, поступающий от хост ЭВМ, является взвешенным,
, ( , ), при , ∈ Е – связь между ними. Если = | | – количество задач в
̅̅̅̅̅ подграфе, то , = 1, .
Все связи сведены в матрицу смежности ( ) = [ , ] 1.1 1.2 … 1. … 1. ×
где , ∈ N.
,
, , 0,если ( , ) ∉ .
2.1 2.2 … 2. … 2.
.
= … . .1 .2 … . … .
…
(1)
{ .1 .2 … . … . }
Значение веса связей между задачами, описывающего интенсивность обмена информацией, определяется как:
={ ,еслидуга( , )∈ имеетвес ,, (2)
Сопоставим каждой вершине ∈ графа веса, описывающие

занимаемые задачами аппаратные ресурсы ПЛИС, из множества весов =
{{ 1, 1, 1},{ 2, 2, 2},…,{ , , }}, где – количество логических элементов ПЛИС, – количество ОЗУ, – количество цифровых сигнальных процессоров, получив множество взвешенных вершин:
( ) = { ( ), ( ), ( )}. (3) Расположение представлено множеством , состоящим из подмножеств ,
описывающих ПЛИС: = { 1,…, ,…, …, }, (4)
̅̅̅̅̅ ̃
где , , ∈ 1, N. Тогда – множество не расположенных вершин.
задаются тремя переменными – , , .
Аппаратные ресурсы, доступные для расположения задач на ПЛИС,

Под степенью вершины примем число ребер ( ) ⊆ ( ), инцидентных
и опишем ( ).
Множество вершин, соединенных с , назовем окрестностью и обозначим
( ). Тогда задача расположения сводится к нахождению множеств , такого,
что: ⊆ , ⊆ ∶ ∀ ∩ = ∅. (5) Если существует ребро, соединяющее вершины из разных множеств
подмножества , тогда вес этого ребра входит в множество :
(∃ ∶ ∈ , ∈ )→ ∈ . (6)

Целевая функция задачи расположения представлена следующим образом:
̃
= ∑ . (7)
, =1
Следовательно, для достижения максимальной производительности РВС суммарный вес ребер, соединяющих различные подмножества множества
должен стремиться к минимуму ( → ).
На основании представленного описания расположения задач в РВС
разработан метод, состоящий из следующих этапов.
1.Находим в матрице смежности ( ) «опорную» вершину ,
̅̅̅̅̅ (8)
имеющую максимальное число смежных вершин:
∈ ∶ ( )= ( ).
=1,
2. Определяем в матрице смежности вершину , смежную с «опорной»
ребром максимального веса:
∈ , ∈ : = (
),
( , ) ̅̅̅̅̅ , (9)
что позволяет выбрать для расположения самый нагруженный узел. 3.Выбираем из матрицы смежности вершины, смежные только с
«опорной» и/или только с выбранной на втором этапе метода:
=1,

( ∈ ( )∨ ∈ ( ))∧δ( )=1
∈ : {h h9 h . (10)
h
( h ∈ ( ) ∧ h ∈ ( )) ∧ δ( h) = 2
Обеспечивает минимизацию числа изолированных вершин на последних этапах расположения.
(11)
4.Проверяем, что сумма аппаратных ресурсов, необходимых для расположения выбранных вершин на текущем номере ПЛИС не превышает
доступных: ∑ ( ) ≤ ∧ ∑ ( )≤ ∧ ∑ ( )≤ .
∈ ∈ ∈
Если (11) верно, то запоминаем выбранные вершины для расположения. Данный шаг отсеивает вершины, которые ввиду занимаемых ресурсов не могут быть расположены на одной ПЛИС с «опорной».
( ) ≠ ∅. (12) В конце итерации присваиваем номера выбранных вершин множеству, соответствующему текущей ПЛИС, удаляем все связи с ними из матрицы
смежности
≔ ∪ { }
5. Повторяем этапы 2-4 пока есть смежные с «опорной» вершины:
{ ̃ ≔ ̃ { } ̅ ̅ ̅ ̅ ̅ . ( 1 3 ) , =0, , =0∀ =1,
= − ∑ ( ), ∈
и уменьшаем аппаратные ресурсы ПЛИС на количество занимаемых задачами
= − ∑ ( ), ∈
= − ∑ ( ).
(14)
∈
Позволяет максимально занять ресурсы ПЛИС задачами, имеющими связь к «опорной».
6. Повторяем этапы 1-5 пока в матрице смежности остались связанные
вершины
В случае присутствия изолированных вершин
∃ , > 0. ̃ (15) ∃ ∶( ( )=0)˄( ∈ ), (16)

располагаем их на множествах ПЛИС, не превышая значения ее доступных ресурсов (11), до тех пор, пока все вершины не будут расположены
= . (17) Отличительная особенность предложенного метода заключается в выделении из матрицы смежности подграфа задачи вершин, имеющих максимальную интенсивность обмена информацией и максимальное количество связей при возможности расположения на аппаратных ресурсах ПЛИС, что
позволяет располагать их на одной микросхеме и снижать интенсивность обмена информацией через коммутирующее устройство.
В третьей главе разработаны алгоритм и структурно-функциональная организация устройства расположения задач в РВС.
Для реализации предложенного метода разработан алгоритм расположения задач в РВС (рисунок 2).
Рисунок 2 – Алгоритм расположения задач в РВС
В начале алгоритм из матрицы смежности подграфа задачи выбирается вершина с максимальным числом соединений, далее по тексту называется «опорной» (1 этап метода). Следующим шагом определяется вершина, смежная к «опорной» ребром с максимальным весом (этап 2 метода). Для найденных на первом и втором шаге вершин находятся вершины смежные им и имеющие степень один (3 этап метода). На следующих шагах происходит сравнение суммы ресурсов выбранных вершин с доступными на ПЛИС, и, при необходимости, берется новое множество для расположения задач на ПЛИС. В случае, если сумма ресурсов вершин остается больше доступных, то возвращаемся к шагу 2 (4 этап метода). При выполнении вышеизложенных шагов, происходит присваивание номеров вершин к номеру множества текущей ПЛИС (5 этап метода). В заключении происходят две проверки, первая на расположении всех вершин со связями, а вторая на расположении всех изолированных вершин (6 этап метода).
В алгоритме вычислительно сложными шагами являются:
− поиск вершины с максимальной инцидентностью , при ее поиске
необходимо пройти по всей матрице смежности, из-за чего асимптотическая вычислительная сложность равняется ( 2);
− поиск вершины, соединенной с опорной ребром максимального веса , на данном шаге перебираются вершины, смежные с опорной, что дает асимптотическую вычислительную сложность ( );
− поиск вершины, смежной только с или , на котором проверяются все смежные вершины с опорными, что в самом плохом случае дает асимптотическую вычислительную сложность ( 2).
Таким образом, общая асимптотическая вычислительная сложность
алгоритма равняется
( 2) + ( 2) + ( ) ≈ ( 2),
что ниже относительно существующих алгоритмов. Например, алгоритм расположения, основанный на идеях генетического метода, имеет вычислительную сложность O(n3).
Структурно-функциональная схема устройства расположения задач в РВС, представлена на рисунке 3.

Рисунок 3 – Структурно-функциональная схема устройства расположения задач в РВС
Для функционирования устройства используется четыре ОЗУ: первое для хранения матрицы смежности подграфа информационного графа задачи; второе для хранения весов вершин; третье для обеспечения внутренней работы устройства; четвертое для хранения расположения.
Матрица смежности хранится в ОЗУ1, для каждой вершины выделено адресное пространство (слово) размером n-1, а позиция внутри слова описывает связь между вершинами. Данные, записанные в ОЗУ1, хранят вес связи между вершинами – если значение больше нуля, то связь есть.
Устройство состоит из следующих функциональных модулей:
− поиска вершины с максимальной инцидентностью (МПВМИ), структурно-функциональная схема которого приведена на рисунке 4, инициализирует работу по сигналу от хост ЭВМ или МПиПЗП. Чтение данных из ОЗУ1 начинается с начальной вершины. Если значение связи не «ноль», то значение регистра RG1, хранящего число инцидентных вершине ребер, инкрементируется. При достижении адреса в ОЗУ1 «начальный адрес» вершины плюс (n-1) полученное значение инцидентности сравнивается с сохраненным в RG2 регистре максимумом (в начале работы устройства значение регистра равно нулю). Если текущее значение инцидентности больше сохраненного – то значение инцидентности в RG3 и “начальный адрес” в RG4 текущей вершины перезаписываются. При достижении последней вершины, модуль выдает сигнал готовности;
Рисунок 4 – Структурно-функциональная организация модуля поиска вершины с максимальной инцидентностью
− поиска смежной вершины к заданной с максимальным весом ребра (МПСВ) инициализирует работу по сигналу от МПВМИ или МПиПЗП. По полученному номеру вершины от МПВМИ начинается чтение данных из ОЗУ1. Модуль последовательно перебирает вершины, смежные с заданной, и выделяет самую нагруженную связь;
− поиска вершины, смежной только заданной (МПВСТЗ), начинает работу от сигнала МПВМИ или МПСВ. Модуль считывает данные от ОЗУ1, если найдена связь с другой вершиной, то для нее начинается считывание данных. Если текущая вершина имеет связь только с опорной и/или смежной ей максимальным ребром и не является одной из них, то вершина найдена. Модуль перебирает все смежные вершины, после чего формируется сигнал «готов»;
− управления ОЗУ1 (МУОЗУ1). Осуществляет функции: чтение данных из ОЗУ1, хранение, обновление, стирание черного списка адресов вершин, проверка наличия вершин в ОЗУ1, очистка данных о вершинах из промежуточного ОЗУ в ОЗУ1, стирание данных об опорной вершине. По сигналу МУОЗУ1 записывает номера вершин из ОЗУ3 и МПСВ в «черный список», необходимый для обеспечения отсеивания вершин, которые не могут участвовать на текущей итерации в расположении;
− управления промежуточным ОЗУ (МУПОЗУ), работающий с ОЗУ как с FIFO. Выполняет функции последовательного чтения, стирания, записи данных из промежуточного ОЗУ;
− проверки и присвоения задач ПЛИС (МПиПЗП). Обеспечивает контроль за последовательностью работы остальных блоков и присваивает задачи ПЛИС. Считывает номера вершин из промежуточного ОЗУ, МПВМИ и выбирает из ОЗУ хранения весов соответствующие значения и суммирует их. Если суммарные ресурсы, занимаемые вершинами, не превышают значения доступных для текущей ПЛИС, то записываем в ОЗУ хранения расположения номера вершин с
номером множества ПЛИС. Модуль работает, пока номера всех вершин не будут присвоены номерам множеств ПЛИС и записаны в ОЗУ хранения расположения. В начале работы устройства хост ЭВМ заполняет ОЗУ1, ОЗУ хранения весов вершин. Далее выдается сигнал для инициализации работы МПВМИ, с мультиплексоров снимается сигнал от хост ЭВМ и память переключается на работу с устройством. В конце работы выдается сигнал «готов», хост ЭВМ выдает сигнал для переключения режима работы и считывает из ОЗУ хранения
расположения данные.
На основании разработанной структурно-функциональной схемы создана
программная модель с использованием языка описания аппаратуры Verilog, подтвержденная свидетельством о государственной регистрации программы для ЭВМ No 2021661030.
Отличительной особенностью разработанной структурно- функциональной схемы является наличие модулей поиска вершины с максимальным числом связей, поиска вершины, соединенной с заданной ребром с максимальным весом, поиска вершины, соединенной только с заданной, проверки и присвоения задач ПЛИС, и связях между ними, позволяющих в реальном масштабе времени располагать задачи в РВС. Разработанное описание устройства на языке Verilog позволило произвести экспериментальные исследования разработанного устройства и сравнить его с существующими аппаратными средствами, выполняющими схожие функции.
В четвертой главе представлено исследование разработанного устройства расположения задач в РВС и проводятся сравнения со средствами, выполняющими схожие функции.
Исследование разработанного устройства производилась в ПО Intel Quartus 19.1 на ПЛИС фирмы Intel семейства MAX10 10M50SCE144I7G, состоящей из 49760 логических элементов, включающих LUT с четырьмя входами, 1677312 бит встроенной памяти, 288 встроенных умножителей 9-ти битовых слов. У логических элементов семейства MAX10 существует два типа работы – нормальный и арифметический.
При компиляции модели устройства на языке Verilog в ПО Quartus получены характеристики роста занимаемых ресурсов от размера входных данных (рисунок 5, 6).
2500
2000
1500
1000
0
8 9 10 11 12 13 14 15 16 17
Разрядность шины входных данных, бит
y = 108,89x + 258,21
Рисунок 5 – Зависимость роста использования логических ячеек от размера входных данных
Количество логических элементов, шт.
1200000 1000000 800000 600000 400000 200000 0
-200000
8916
01
y = 6833,6×3 – 214051×2 + 2E+06x – 8E+06
21
41
Разрядность шины входных данных, бит
Рисунок 6 – Зависимость роста использования логической памяти от размера входных данных
Обзор рисунков 5 и 6 позволяет сделать вывод, что рост занимаемых ресурсов происходит по линейному закону, а рост к требованиям памяти – по полиномиальному. На ПЛИС 10M50SCE144I7G, используя только встроенную память, возможно реализовать устройство, обрабатывающее 65536 вершин.
80000
70000
60000
50000
40000
30000
20000
10000
0 20 40 60 80 100 120 140
Количество вершин, шт.
y = 6,073×2
– 203,54x +
1850,5
Рисунок 7 – Зависимость роста времени работы алгоритма от количества вершин в графе
На рисунке 7 приведен график роста времени работы устройства от размеров графа, доказывающий результаты исследования временой сложности алгоритма расположения задач в РВС, полученные теоретическим путем – O(n2).
Для сравнения времени работы с аналогами было проведено исследование работы устройства расположения задач в РВС на примере графа, представленного на рисунке 8. Частота разработанного устройства составила 100МГц.
Время, мкс Количество бит памяти, бит
Рисунок 8 – Пример графа для работы устройства расположения задач РВС
Занимаемые вершинами ресурсы для представленного на рисунке 8 графа приведены в таблице 1. Доступные ресурсы ПЛИС равны = 20, =
22, =25.
Таблица 1 – Веса вершин тестового графа
Номер вершины 0
2
4
Оценка времени работы устройства расположения задач в РВС проводилась в ПО ModelSim фирмы Mentor Graphics (рисунок 9).
Рисунок 9 – Результат работы устройства расположения задач в РВС
На рисунке 9 с левой стороны представлены имена переменных, а с правой – соответствующие значения, изменяющиеся во времени. RAM1 – значения памяти, в которой хранится матрица смежности подграфа задачи, RAM2 – память для хранения весов вершин, RAM_OUT – память для хранения конечного расположения, algorithm_done – сигнал окончания работы устройства. Из анализа рисунка 8 видно, что устройство завершило работу за 69,485мкс, выходные данные, а расположение по ПЛИС задач следующее:
− первой ПЛИС присвоены задачи 2, 1, 4; − второй ПЛИС присвоены задачи 5, 6, 7; − третьей ПЛИС присвоены задачи 0 и 3.
Номер
Веса вершины вершины Веса вершины

=8, =7, =6 5 =3, =5, =10
=5, =3, =4 6 =7, =4, =8 =10, =7, =8 7 =4, =3, =4 = 10, = 4, = 5
= 4, = 2, = 10

Сравнение времени расположения задач разработанного устройства с существующими аналогами приведены в таблице 2.
Таблица 2 – Результаты работы устройства в сравнении с аналогами
Метод
Суммарное время работы, мкс
Интенсивность обмена информацией между задачами через коммутирующее устройство
Amr Hassan, Hassan Mostafa, Hossam A.H. Fahmy
Устройство расположения задач в РВС
144,8 29
69,5 31
Ashish Mishra Mohit Agarwal, Abhijit Rameshwar Asati, Kota Solomon Raju
124,3
31
По результатам сравнительного анализа сделан вывод, что разработанное устройство расположения задач в РВС на базе ПЛИС на 3% менее эффективно в качестве расположения, но в 1,94 быстрее по времени расположения относительно существующих средств, что свидетельствует о достижении поставленной цели работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Диссертационная работа посвящена решению научно-технической задачи, заключающейся в разработке метода, алгоритма и устройства расположения задач в реконфигурируемых вычислительных системах, уменьшающих время расположения.
При решении поставленной в диссертационной работе задачи были получены следующие основные результаты:
1. Разработан метод расположения задач в реконфигурируемых вычислительных системах, отличающийся введением подграфа задачи, множества ПЛИС и правил расположения задач, позволивший располагать
нагруженные узлы на одной ПЛИС за счет итерационного выбора задач на основании количества их связей, интенсивности обмена информацией и используемых аппаратных ресурсов.
2. Создан алгоритм расположения задач в реконфигурируемых
вычислительных системах, отличающийся последовательным выделением из
подграфа задачи множества вершин на основе этапов разработанного метода, располагающий задачи с максимальным обменом информации на одном кристалле ПЛИС, отличающийся асимптотической вычислительной сложностью O(n2) для n вершин, которая ниже существующих решений.
3. Разработана структурно-функциональная организация устройства расположения задач в реконфигурируемых вычислительных системах, отличающаяся применением модулей поиска вершины с максимальным числом связей, поиска вершины, соединенной с заданной ребром с максимальным весом, поиска вершины, соединенной только с заданной, проверки и присвоения задач
ПЛИС, и связях между ними, позволяющая в реальном масштабе времени располагать задачи в реконфигурируемых вычислительных системах.
4.Разработано устройство на ПЛИС семейства Intel, позволившее произвести экспериментальное исследование устройства расположения задач в РВС, доказавшее асимптотическую сложность алгоритма и показавшее выигрыш во времени расположения относительно существующих средств в 1,94 раза.
Рекомендации. Результаты диссертационного исследования могут использоваться в системах высокой готовности, таких как бортовая авиация, наблюдения, радиолокации, распознавания объектов и т.д. Применение разработанного устройства позволит снизить затраты времени расположения задач в РВС.
Перспективы дальнейшей разработки темы. Использование более быстрых кристаллов ПЛИС позволит уменьшить время расположения задач в РВС. Также в результате применения принципов параллелизма возможно добиться параллельной работы некоторых узлов, что также позволит уменьшить время расположения.