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

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

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

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

Оптимизация выполняется как с помощью, так и без использования параллельных вычислений на двухъядерных 64-разрядных AMD ®, 2 4 ГГц, 3 4 ГБ Linux ® и четырёхъядерных 64-разрядных AMD, 2 5 ГГц 7 4 ГБ 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 различных значений.