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

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

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

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

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

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

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

[math]\displaystyle{ \Delta }[/math] трубка - это линии отклонения на 5-10% от установившегося значения системы.

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

Перерегулирование [math]\displaystyle{ \sigma }[/math] - отклонение графика от установившегося значения, который выражается в процентах.

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

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

[math]\displaystyle{ \begin{cases} \Delta = A_1e^{s_1 t_p}+A_2e^{s_2 t_p}, \\ A_1+A_2=1. \end{cases} }[/math],

где заданы полюса [math]\displaystyle{ s_1 \lt s_2 \lt 0 }[/math] и известно [math]\displaystyle{ \Delta }[/math].

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

[math]\displaystyle{ \sigma = e_{max} \cdot 100 \%, \\ e_{max} = A_1e^{s_1 t_{max}}+A_2e^{s_2 t_{max}}. }[/math]

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

Сравнивая [math]\displaystyle{ \sigma_i }[/math], находим наименьшее из них. Таким образом, получим результат алгоритма: минимальное время регулирования и минимальное перерегулирование.

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

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

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

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

[math]\displaystyle{ 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 \%. }[/math]

Так же в программе используется в функции редукции поиск минимального [math]\displaystyle{ \sigma }[/math] простым последовательным сравнением.

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

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

2) Разделение необходимого числа [math]\displaystyle{ t_i }[/math] между процессами;

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

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

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

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

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

[math]\displaystyle{ 13n }[/math]- арифметических операций, [math]\displaystyle{ 5n }[/math]- взятий экспоненты, а так же как минимум [math]\displaystyle{ n }[/math]сравнений.

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

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

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

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

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

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

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

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

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

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

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

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

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

Число процессоров [math]\displaystyle{ [4:128] }[/math];

Размер разбиения отрезка [math]\displaystyle{ [10^4:10^7] }[/math].

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

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

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

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

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

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

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

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

Литература

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

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