Участник:Svetlanalarina/Алгоритм поиска наилучшего времени регулирования для СУ 2го порядка

Основные авторы описания: С. Ларина (414 группа)

1 Свойства и структура алгоритмов

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

1.1 Общее описание алгоритма

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

Для лучшего понимания объектов и терминов в данном алгоритме, стоит описать глоссарий:

$\Delta$ трубка - это линии отклонения на 5-10% от установившегося значения системы.

Время регулирования $t_p$ - это время, когда график функции, которая описывает динамическую систему, сходит в $\Delta$ трубку и более не выходит за её пределы.

Перерегулирование $\sigma$ - отклонение графика от установившегося значения, который выражается в процентах.

1.2 Математическое описание алгоритма

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

$\begin{cases} \Delta = A_1e^{s_1 t_p}+A_2e^{s_2 t_p}, \\ A_1+A_2=1. \end{cases}$,

где заданы полюса $s_1 \lt s_2 \lt 0$ и известно $\Delta$.

Мой алгоритм поиска $t_p$ заключается в том, что я задаю конкретный диапазон, в который должно входить мое время $t_p \in [t_1,t_2]$. Затем для каждого $t_i \in [t_1,t_2]$ производится подбор соответствующих $A_1$ и $A_2$ с помощью уравнений описанных выше. Эти коэффициенты нужны для подстановки в следующее выражение на перерегулирование $\sigma$:

$\sigma = e_{max} \cdot 100 \%, \\ e_{max} = A_1e^{s_1 t_{max}}+A_2e^{s_2 t_{max}}.$

Для $n$ различных $t_i$ на отрезке будем находить перерегулирования $\sigma_i$, а так же сохранять соответствующие ему коэффициенты $A_{1,i}, A_{2,i}$ и непосредственно само значение $t_i$.

Сравнивая $\sigma_i$, находим наименьшее из них. Таким образом, получим результат алгоритма: минимальное время регулирования и минимальное перерегулирование.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром является поиск по конкретным $t_i \in [t_1,t_2]$ коэффициентов и перерегулирования. Для сравнения перерегулирований возможны параллельные и не параллельные алгоритмы сортировки или поиска, пока это вопрос реализации.

1.4 Макроструктура алгоритма

Основными операциями являются нахождение $A_{1}, A_{2}$ и $\sigma$ (далее будем называть их парамтерами) из следующих выражений:

$A_1 = \dfrac{\Delta - e^{s_2 t_p}}{e^{s_1 t_p} - e^{s_2 t_p}}\\ A_2=1-A1, \\ \sigma = A_1e^{s_1 t_{max}}+A_2e^{s_2 t_{max}} \cdot 100 \%.$

Так же в программе используется в функции редукции поиск минимального $\sigma$ простым последовательным сравнением.

1.5 Схема реализации последовательного алгоритма

1) Считывание данных, а именно $t_{1}, t_{2}, s_1, s_2, t_{max}, cut$, где $cut$ - количество $t_i$ (разбиение);

2) Разделение необходимого числа $t_i$ между процессами;

3) Вычисление всеми процессами $A_{1}, A_{2}$ и $\sigma$ на каждом $t_i$ (описано в макроструктуре);

4) Поиск в цикле наилучшего набора параметров;

5) Сравнение наборов от каждого процесса с помощью функции редукции (предусмотренной в MPI), и поиск тем самым результирующего набора. Для этого необходимо описать функцию сравнений наборов параметров по $\sigma$.

1.6 Последовательная сложность алгоритма

Сложность вычислительного ядра можно оценить примерно следующим образом: Для разбиения n понадобится:

$13n$- арифметических операций, $5n$- взятий экспоненты, а так же как минимум $n$сравнений.

1.7 Информационный граф

Граф алгоритма опишем аналитически и в виде рисунка.

Вершины это начальные данные $t_i$, которые разнятся от процесса к процессу. Далее в вершинах функции $f$, осуществляющие поиск по $t_i$ набора $[\sigma,A_1,A_2,t_i]$, которых существует блоком для передачи в результат. Затем от функции $f$ наборы переходят на операцию сравнения наборов по параметру $\sigma$. В качестве результата получаем удовлетворяющий нас набор.

1.8 Ресурс параллелизма алгоритма

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

Большее время будет задействовано при редукции и сравнении наборов. Но количество сравнений всегда равно $(n-1)$. Что касается вычисления функции $f$, то оно содержит простую арифметику. Если у нас малое количество временных точек, то имеем неэффективное распараллеливание. Но при увеличении ресурсов, а именно когда каждый процесс получит по одному значению, параллелизм может быть ограничен накладными расходами. Имеем не лучше, чем константное время.

1.9 Входные и выходные данные алгоритма

Вход: один набор $t_{1}, t_{2}, s_1, s_2, t_{max}, n$, где $n$ - количество $t_i$ (разбиение);

Выход: $\sigma,A_1,A_2,t_{reg}$ или само уравнение $e(t) = A_1e^{s1t}+A_2e^{s2t}$ и найденные критерии качества $\sigma,t_{reg}$ (для полной иллюстрации найденного процесса регулирования).

2 Программная реализация алгоритма

2.1 Масштабируемость алгоритма и его реализации

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

Число процессоров $[4:128]$;

Размер разбиения отрезка $[10^4:10^7]$.

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

На графиках представлена масштабируемость для данного алгоритма. По вертикали производительность (отношение вычислительной сложности ко времени программы), а по горизонтали число процессов. $w$ - число разбиений отрезка.

Вычисления в вычислительной части легкие. Соответственно время выполнения программы достаточно мало.

Можно увидеть, что действительная продуктивное распараллеливание возникает только в случае огромного разбиения и куда большего времени загруженности процессоров. Это реально продемонстрировать, взяв разбиение $\gt =10^9$, но возникает проблема актуальности решаемой задачи.

Если мы возьмем разбиение отрезка очень большое, то тогда необходимо брать и куда больший интервал разбиения. Например, для $10^9$ значений нет смысла брать $[t_1,t_2] = [1.5 , 6]$ (в секундах). Задача же поиска времени регулирования теряет смысл при $\gt 10$ секундах.

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

2.2 Существующие реализации алгоритма

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

3 Литература

Ким Д.П. - Теория автоматического управления. Том 1. Линейные системы - 2003;

Ким Д.П. - Теория автоматического управления. Том 2. Линейные системы - 2004.