Пример, иллюстрирующий ускорение оптимизации

Основной вычислительной нагрузкой при использовании Simulink Design Optimization является моделирование модели. Методы оптимизации обычно требуют многочисленных моделирований на одну итерацию оптимизации. Поскольку многие из симуляций независимы, полезно использовать параллельные вычисления для распределения этих независимых симуляций между различными процессорами.

Рассмотрим модель Simulink HL20 самолета, который осуществляет корабли с аэрокосмической Blockset™. Модель HL20 представляет собой сложную модель и включает механические, электрические, радиоэлектронные и экологические компоненты. Типичное моделирование модели HL20 занимает около 60 секунд.

При посадке самолет подвергается двум порывам ветра с разных направлений, которые вызывают отклонение самолета от номинальной траектории на взлетно-посадочной полосе. Simulink Design Optimization используется для настройки 3 параметров контроллера так, чтобы боковое отклонение самолёта от номинальной траектории при наличии порывов ветра поддерживалось в пределах пяти метров.

Оптимизация выполняется как с использованием, так и без использования параллельных вычислений на двухъядерных 64-разрядных машинах AMD ®, 2 .4GHz, 3 .4GB Linux ® и четырехъядерных 64-разрядных машинах AMD, 2 .5GHz, 7 .4GB Linux. Скорость, наблюдаемая для этой проблемы, показана ниже.

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

Когда оптимизация принесет пользу от параллельных вычислений?

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

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

Каждый из них рассматривается в следующих разделах.

Количество параметров и их влияние на параллельные вычисления

Количество имитаций, выполняемых методом оптимизации, тесно связано с количеством параметров.

Метод градиентного спуска и параллельные вычисления

Рассмотрим моделирование, требуемое методом оптимизации на основе градиента для каждой итерации:

Из этих моделирований моделирование, необходимое для вычисления градиентов, является независимым и распределенным. Давайте рассмотрим это более подробно:

Np  = 1:16;   %Number of parameters (16 = 4 filtered PID controllers)
Nls = 1;      %Number of line search simulations, assume 1 for now
Nss = 1;      %Total number of serial simulations, start with nominal only

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

Nss = 1+Np*2+Nls;

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

Nw  = 4;      %Number of parallel processors
Nps = 1 + ceil(Np/Nw)*2+Nls;

Соотношение Nss/Nps дает нам ускорение, которое мы строим ниже

Nls = 0:5;      %Vary the number of line search simulations
figure;
hAx  = gca;
xlim([min(Np) max(Np)]);
for ct = 1:numel(Nls)
  Rf = (1+Nls(ct)+Np*2)./(1+Nls(ct)+ceil(Np/Nw)*2);
  hLine = line('parent',hAx,'xdata',Np,'ydata',Rf);
  if ct == 1
     hLine.LineStyle = '-';
     hLine.Color = [0 0 1];
     hLine.LineWidth = 1;
  else
     hLine.LineStyle = '-.';
     hLine.Color = [0.6 0.6 1];
     hLine.LineWidth = 1;
  end
end
grid on
title('Gradient descent based relative speedup')
xlabel('Number of parameters')
ylabel('Serial time/parallel time')
annotation('arrow',[0.55 .55],[5/6 2/6])
text(8.5,1.75,'Increasing number of line searches')

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

График также показывает локальные максимумы при 4,8,12,16 параметрах, которые соответствуют случаям, когда вычисления градиента параметров могут быть равномерно распределены между параллельными процессорами. Напомним, что для HL20 проблемы самолета, которая имеет 3 параметра, наблюдаемое ускорение четырехъядерного процессора составило 2,14, что хорошо соответствует этому сюжету.

Метод поиска шаблона и параллельные вычисления

Метод оптимизации поиска шаблона по своей сути подходит для параллельной реализации. Это происходит потому, что на каждой итерации доступны один или два набора решений-кандидатов. Алгоритм оценивает все эти решения-кандидаты и затем генерирует новое решение-кандидат для следующей итерации. Оценка возможных решений может выполняться параллельно, поскольку они независимы. Давайте рассмотрим это более подробно:

Поиск шаблона использует два набора решений-кандидата, набор поиска и набор опроса. Количество элементов в этих наборах пропорционально количеству оптимизированных параметров

Nsearch = 15*Np;     %Default number of elements in the solution set
Npoll   = 2*Np;      %Number of elements in the poll set with a 2N poll method

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

Nps = ceil(Nsearch/Nw)+ceil(Npoll/Nw);

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

Nss = 0.5*(Nsearch+Npoll);

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

figure;
hAx  = gca;
xlim([min(Np) max(Np)]);
Rp1 = (Nss)./( Nps );
Rp2 = (Npoll)./( ceil(Npoll/Nw) );
line('parent',hAx,'xdata',Np,'ydata',Rp1,'color',[0 0 1]);
line('parent',hAx,'xdata',Np,'ydata',Rp2,'color',[0.6 0.6 1]);
grid on
title('Pattern search based relative speedup')
xlabel('Number of parameters')
ylabel('Serial time/ parallel time')
legend('Search and poll sets','Poll set only')

Темная кривая - это ускорение при оценке наборов решений и опросов, а более легкая нижняя кривая - ускорение при оценке только набора опросов. Ожидаемое ускорение над оптимизацией должно лежать между двумя кривыми. Обратите внимание на то, что даже при наличии только одного параметра метод поиска шаблона получает преимущества от распределения. Также напомним, что для HL20 проблемы самолета, которая имеет 3 параметра, наблюдаемое четырехъядерное ускорение составило 2,81, что хорошо соответствует этому сюжету.

Накладные расходы на распределение оптимизации

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

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

Есть также некоторые издержки, связанные с передачей данных к удаленным процессорам и от них. Simulink Design Optimization использует общие пути для предоставления удаленным процессорам доступа к моделям, а возвращаемые данные ограничиваются значениями нарушения целей и ограничений. Поэтому эти накладные расходы обычно намного меньше, чем открытие пула MATLAB ® и загрузка модели. Это было верно для HL20 оптимизации самолета, но может быть верно не во всех случаях. Однако анализ, показанный ниже, может быть расширен для покрытия дополнительных накладных расходов.

findOverhead = false; % Set true to compute overhead for your system.
if findOverhead
  % Compute overhead.
  wState = warning('off','MATLAB:dispatcher:pathWarning');
  t0 = clock;
  parpool                         %Open the parallel pool
  load_system('airframe_demo')    %Open a model
  set_param('airframe_demo','SimulationCommand','update')  %Run an update diagram for the model
  Toverhead = etime(clock,t0)
  close_system('airframe_demo')
  delete(gcp)                     %Close the parallel pool
  warning(wState);
else
  % Use overhead observed from experiments.
  Toverhead = 28.6418;
end

Рассмотрим алгоритм на основе градиента со следующим количеством последовательных симуляций на одну итерацию:

Nw  = 4;                      %Four parallel processors
Np  = 4;                      %Four parameters optimized
Nls = 2;                      %Assume 2 line search simulations
Nss = 1+Np*2+Nls;             %Serial simulations without parallel computing
Nps = 1+ceil(Np/Nw)*2+Nls;    %Serial simulations with parallel computing

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

Niter = 1;
Ts    = 10:10:60;                %Time to simulate model once
Tst   = Niter*Nss*Ts;            %Total serial optimization time
Tpt   = Niter*Nps*Ts+Toverhead;  %Total parallel optimization time
figure;
hAx  = gca;
xlim([min(Ts) max(Ts)]);
Rp = (Tst)./( Tpt );
line('parent',hAx,'xdata',Ts,'ydata',Rp,'color',[0 0 1]);
Niter = 2^1:4;
for ct = 1:numel(Niter)
   Rp = ( Niter(ct)*Nss*Ts )./(Niter(ct)*Nps*Ts+Toverhead);
   line('parent',hAx,'xdata',Ts,'ydata',Rp,'color',[0.6 0.6 1]);
end
grid on
title('Effect of parallel overhead on optimization speedup')
xlabel('Time to simulate model once')
ylabel('Serial time/ parallel time')
annotation('arrow',[0.55 0.55],[0.45 0.85]);
text(38,2.05,'Increasing number of iterations')

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

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

Неопределенные параметры и их влияние на параллельную оптимизацию

При использовании Simulink Design Optimization можно изменять некоторые параметры (например, жесткость пружины) и оптимизировать параметры перед этими изменениями. Неопределенные параметры определяют дополнительные моделирования, которые необходимо оценивать в каждой итерации. Однако концептуально эти дополнительные моделирования можно рассматривать как расширение моделирования без неопределенных параметров. Это означает, что там, где проводилось одно моделирование, теперь выполняется несколько моделирований. В результате неопределенные параметры не влияют на скорость свободной оптимизации накладных расходов, и расчеты в предыдущих разделах являются действительными.

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

Nu = [0 10];                        %Number of uncertain scenarios
Nss = (1+Nu)*(1+Np*2+Nls);          %Serial simulations without parallel computing
Nps = (1+Nu)*(1+ceil(Np/Nw)*2+Nls); %Serial simulations with parallel computing
figure;
hAx  = gca;
xlim([min(Ts) max(Ts)]);
for ct = 1:numel(Nu)
   Rp = (Ts*Nss(ct))./(Ts*Nps(ct)+Toverhead);
   line('parent',hAx,'xdata',Ts,'ydata',Rp,'color',[0 0 1]);
end
grid on
title('Effect of uncertain parameters on optimization speedup')
xlabel('Time to simulate model once')
ylabel('Serial time/ parallel time')
annotation('arrow',[0.45 0.45],[0.4 0.9])
text(31,2.05,'Increasing number of uncertain variables')

Нижняя кривая - это случай без неопределенных параметров, а верхняя кривая - случай с неопределенным параметром, который может принимать 10 различных значений.