Многопроцессорное планирование с использованием моделируемого отжига с пользовательским типом данных
В этом примере показано, как использовать моделируемый отжиг для минимизации функции с помощью пользовательского типа данных. Здесь моделируемый отжиг настраивается для решения многопроцессорной задачи планирования.
Многопроцессорная задача планирования
Задача многопроцессорного планирования состоит в нахождении оптимального распределения задач на наборе процессоров. Указывается количество процессоров и количество задач. Время, затраченное на выполнение задачи процессором, также указывается как данные. Каждый процессор запускается независимо, но каждый может запускать только одно задание за раз. Мы называем назначение всех заданий доступным процессорам «расписанием». Цель задачи - определить кратчайший график для данного набора задач.
Сначала мы определяем, как выразить эту проблему с точки зрения пользовательской задачи оптимизации типа данных, которая simulannealbnd функция может решить. Мы придумываем следующую схему: сначала пусть каждая задача представлена целым числом от 1 до общего количества задач. Точно так же каждый процессор представлен целым числом от 1 до количества процессоров. Теперь мы можем хранить количество времени, которое данное задание займет на данном процессоре в матрице, называемой «длины». Количество времени «t», которое процессору «i» требуется для выполнения задачи «j», будет сохранено в длинах (i, j).
Мы можем представлять график аналогичным образом. В заданном расписании строки (целое число от 1 до количества процессоров) будут представлять процессоры, а столбцы (целое число от 1 до количества задач) будут представлять задачи. Например, расписанием [1 2 3; 4 5 0; 6 0 0] будут задачи 1, 2 и 3, выполненные на процессоре 1, задачи 4 и 5, выполненные на процессоре 2, и задача 6, выполненная на процессоре 3.
Здесь мы определяем наше количество задач, количество процессоров и массив длин. Различные коэффициенты для различных строк представляют собой тот факт, что различные процессоры работают с различными скоростями. Мы также определяем «sampleSchedule», который будет нашей начальной точкой входом к simulannealbnd.
rng default % for reproducibility numberOfProcessors = 11; numberOfTasks = 40; lengths = [10*rand(1,numberOfTasks); 7*rand(1,numberOfTasks); 2*rand(1,numberOfTasks); 5*rand(1,numberOfTasks); 3*rand(1,numberOfTasks); 4*rand(1,numberOfTasks); 1*rand(1,numberOfTasks); 6*rand(1,numberOfTasks); 4*rand(1,numberOfTasks); 3*rand(1,numberOfTasks); 1*rand(1,numberOfTasks)]; % Random distribution of task on processors (starting point) sampleSchedule = zeros(numberOfProcessors,numberOfTasks); for task = 1:numberOfTasks processorID = 1 + floor(rand*(numberOfProcessors)); index = find(sampleSchedule(processorID,:)==0); sampleSchedule(processorID,index(1)) = task; end
Моделируемый отжиг для пользовательского типа данных
По умолчанию моделируемый алгоритм отжига решает задачи оптимизации, принимая, что переменные принятия решений являются типами данных double. Поэтому функция отжига для генерации последующих точек принимает, что текущая точка является вектором типа double. Однако, если DataType опция установлена на 'custom', моделируемый решатель отжига может также работать с задачами оптимизации с участием произвольных типов данных. В качестве переменной принятия решений можно использовать любую допустимую структуру данных MATLAB ®. Для примера, если мы хотим simulannealbnd чтобы использовать sampleSchedule в качестве переменной принятия решений, пользовательский тип данных может быть задан с помощью матрицы целых чисел. В дополнение к установке DataType опция на 'custom' нам также нужно обеспечить пользовательскую функцию отжига через AnnealingFcn опция, которая может генерировать новые точки.
Пользовательские функции отжига
В этом разделе показано, как создать и использовать необходимую пользовательскую функцию отжига. Пробной точкой для многопроцессорной задачи планирования является матрица процессора (строки) и задач (столбцы), как обсуждалось ранее. Пользовательская функция отжига для многопроцессорной задачи планирования будет принимать график заданий как вход. Функция отжига затем изменит этот график и вернет новый график, который был изменен на величину, пропорциональную температуре (как принято при моделируемом отжиге). Здесь мы отображаем нашу пользовательскую функцию отжига.
type mulprocpermute.m
function schedule = mulprocpermute(optimValues,problemData)
% MULPROCPERMUTE Moves one random task to a different processor.
% NEWX = MULPROCPERMUTE(optimValues,problemData) generate a point based
% on the current point and the current temperature
% Copyright 2006 The MathWorks, Inc.
schedule = optimValues.x;
% This loop will generate a neighbor of "distance" equal to
% optimValues.temperature. It does this by generating a neighbor to the
% current schedule, and then generating a neighbor to that neighbor, and so
% on until it has generated enough neighbors.
for i = 1:floor(optimValues.temperature)+1
[nrows ncols] = size(schedule);
schedule = neighbor(schedule, nrows, ncols);
end
%=====================================================%
function schedule = neighbor(schedule, nrows, ncols)
% NEIGHBOR generates a single neighbor to the given schedule. It does so
% by moving one random task to a different processor. The rest of the code
% is to ensure that the format of the schedule remains the same.
row1 = randinteger(1,1,nrows)+1;
col = randinteger(1,1,ncols)+1;
while schedule(row1, col)==0
row1 = randinteger(1,1,nrows)+1;
col = randinteger(1,1,ncols)+1;
end
row2 = randinteger(1,1,nrows)+1;
while row1==row2
row2 = randinteger(1,1,nrows)+1;
end
for j = 1:ncols
if schedule(row2,j)==0
schedule(row2,j) = schedule(row1,col);
break
end
end
schedule(row1, col) = 0;
for j = col:ncols-1
schedule(row1,j) = schedule(row1,j+1);
end
schedule(row1,ncols) = 0;
%=====================================================%
function out = randinteger(m,n,range)
%RANDINTEGER generate integer random numbers (m-by-n) in range
len_range = size(range,1) * size(range,2);
% If the IRANGE is specified as a scalar.
if len_range < 2
if range < 0
range = [range+1, 0];
elseif range > 0
range = [0, range-1];
else
range = [0, 0]; % Special case of zero range.
end
end
% Make sure RANGE is ordered properly.
range = sort(range);
% Calculate the range the distance for the random number generator.
distance = range(2) - range(1);
% Generate the random numbers.
r = floor(rand(m, n) * (distance+1));
% Offset the numbers to the specified value.
out = ones(m,n)*range(1);
out = out + r;
Целевая функция
Нам нужна целевая функция для многопроцессорной задачи планирования. Целевая функция возвращает общее время, необходимое для данного расписания (что является максимумом времени, которое каждый процессор тратит на свои задачи). Как таковая, целевой функции также нужна матрица длин, чтобы иметь возможность вычислить общее время. Мы собираемся попытаться минимизировать это общее время. Здесь мы отображаем нашу целевую функцию
type mulprocfitness.m
function timeToComplete = mulprocfitness(schedule, lengths)
%MULPROCFITNESS determines the "fitness" of the given schedule.
% In other words, it tells us how long the given schedule will take using the
% knowledge given by "lengths"
% Copyright 2006 The MathWorks, Inc.
[nrows ncols] = size(schedule);
timeToComplete = zeros(1,nrows);
for i = 1:nrows
timeToComplete(i) = 0;
for j = 1:ncols
if schedule(i,j)~=0
timeToComplete(i) = timeToComplete(i)+lengths(i,schedule(i,j));
else
break
end
end
end
timeToComplete = max(timeToComplete);
simulannealbnd вызовет нашу целевую функцию всего с одним аргументом x, но наша функция соответствия имеет два аргумента: x и «длины». Мы можем использовать анонимную функцию, чтобы захватить значения дополнительного аргумента, матрицы длин. Создадим указатель на функцию 'ObjectiveFcn' к анонимной функции, которая принимает один вход x, но вызывает 'mulprocfitness' с x и «длины». Переменная «lenths» имеет значение, когда создается указатель на функцию 'FitnessFcn', поэтому эти значения захватываются анонимной функцией.
% lengths was defined earlier
fitnessfcn = @(x) mulprocfitness(x,lengths);
Мы можем добавить пользовательскую функцию построения графика, чтобы построить график времени, которое задачи берут на каждый процессор. Каждая полоса представляет процессор, и различные цветные фрагменты каждой полки являются различными задачами.
type mulprocplot.m
function stop = mulprocplot(~,optimvalues,flag,lengths)
%MULPROCPLOT PlotFcn used for SAMULTIPROCESSORDEMO
% STOP = MULPROCPLOT(OPTIONS,OPTIMVALUES,FLAG) where OPTIMVALUES is a
% structure with the following fields:
% x: current point
% fval: function value at x
% bestx: best point found so far
% bestfval: function value at bestx
% temperature: current temperature
% iteration: current iteration
% funccount: number of function evaluations
% t0: start time
% k: annealing parameter 'k'
%
% FLAG: Current state in which PlotFcn is called. Possible values are:
% init: initialization state
% iter: iteration state
% done: final state
%
% STOP: A boolean to stop the algorithm.
%
% Copyright 2006-2015 The MathWorks, Inc.
persistent thisTitle %#ok
stop = false;
switch flag
case 'init'
set(gca,'xlimmode','manual','zlimmode','manual', ...
'alimmode','manual')
titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
thisTitle = title(titleStr,'interp','none');
toplot = i_generatePlotData(optimvalues, lengths);
ylabel('Time','interp','none');
bar(toplot, 'stacked','edgecolor','none');
Xlength = size(toplot,1);
set(gca,'xlim',[0,1 + Xlength])
case 'iter'
if ~rem(optimvalues.iteration, 100)
toplot = i_generatePlotData(optimvalues, lengths);
bar(toplot, 'stacked','edgecolor','none');
titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
thisTitle = title(titleStr,'interp','none');
end
end
function toplot = i_generatePlotData(optimvalues, lengths)
schedule = optimvalues.x;
nrows = size(schedule,1);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:nrows
if max(nnz(schedule(i,:))) > maxlen
maxlen = max(nnz(schedule(i,:)));
end
end
schedule = schedule(:,1:maxlen);
toplot = zeros(size(schedule));
[nrows, ncols] = size(schedule);
for i = 1:nrows
for j = 1:ncols
if schedule(i,j)==0 % idle process
toplot(i,j) = 0;
else
toplot(i,j) = lengths(i,schedule(i,j));
end
end
end
Но помните, что при моделируемом отжиге текущий график не обязательно является лучшим расписанием, найденным до сих пор. Создадим вторую пользовательскую функцию построения графика, которая покажет нам лучшее расписание, которое было обнаружено до сих пор.
type mulprocplotbest.m
function stop = mulprocplotbest(~,optimvalues,flag,lengths)
%MULPROCPLOTBEST PlotFcn used for SAMULTIPROCESSORDEMO
% STOP = MULPROCPLOTBEST(OPTIONS,OPTIMVALUES,FLAG) where OPTIMVALUES is a
% structure with the following fields:
% x: current point
% fval: function value at x
% bestx: best point found so far
% bestfval: function value at bestx
% temperature: current temperature
% iteration: current iteration
% funccount: number of function evaluations
% t0: start time
% k: annealing parameter 'k'
%
% FLAG: Current state in which PlotFcn is called. Possible values are:
% init: initialization state
% iter: iteration state
% done: final state
%
% STOP: A boolean to stop the algorithm.
%
% Copyright 2006-2015 The MathWorks, Inc.
persistent thisTitle %#ok
stop = false;
switch flag
case 'init'
set(gca,'xlimmode','manual','zlimmode','manual', ...
'alimmode','manual')
titleStr = sprintf('Current Point - Iteration %d', optimvalues.iteration);
thisTitle = title(titleStr,'interp','none');
toplot = i_generatePlotData(optimvalues, lengths);
Xlength = size(toplot,1);
ylabel('Time','interp','none');
bar(toplot, 'stacked','edgecolor','none');
set(gca,'xlim',[0,1 + Xlength])
case 'iter'
if ~rem(optimvalues.iteration, 100)
toplot = i_generatePlotData(optimvalues, lengths);
bar(toplot, 'stacked','edgecolor','none');
titleStr = sprintf('Best Point - Iteration %d', optimvalues.iteration);
thisTitle = title(titleStr,'interp','none');
end
end
function toplot = i_generatePlotData(optimvalues, lengths)
schedule = optimvalues.bestx;
nrows = size(schedule,1);
% Remove zero columns (all processes are idle)
maxlen = 0;
for i = 1:nrows
if max(nnz(schedule(i,:))) > maxlen
maxlen = max(nnz(schedule(i,:)));
end
end
schedule = schedule(:,1:maxlen);
toplot = zeros(size(schedule));
[nrows, ncols] = size(schedule);
for i = 1:nrows
for j = 1:ncols
if schedule(i,j)==0
toplot(i,j) = 0;
else
toplot(i,j) = lengths(i,schedule(i,j));
end
end
end
Моделируемый метод отжига Опций Setup
Мы выбираем пользовательские отжиг и функции построения графика, которые мы создали, а также изменяем некоторые опции по умолчанию. ReannealInterval установлено на 800, потому что более низкие значения для ReannealInterval кажется, повышает температуру, когда решатель начинает делать много местного прогресса. Мы также уменьшаем StallIterLimit в 800, поскольку значение по умолчанию делает решатель слишком медленным. Наконец, мы должны задать DataType на 'custom'.
options = optimoptions(@simulannealbnd,'DataType', 'custom', ... 'AnnealingFcn', @mulprocpermute, 'MaxStallIterations',800, 'ReannealInterval', 800, ... 'PlotFcn', {{@mulprocplot, lengths},{@mulprocplotbest, lengths},@saplotf,@saplotbestf});
Наконец, мы вызываем моделируемый отжиг с помощью нашей информации о задаче.
schedule = simulannealbnd(fitnessfcn,sampleSchedule,[],[],options); % Remove zero columns (all processes are idle) maxlen = 0; for i = 1:size(schedule,1) if max(nnz(schedule(i,:)))>maxlen maxlen = max(nnz(schedule(i,:))); end end % Display the schedule schedule = schedule(:,1:maxlen)
Optimization terminated: change in best function value less than options.FunctionTolerance.
schedule =
22 34 32 0 0 0 0 0
5 0 0 0 0 0 0 0
19 6 12 11 39 35 0 0
7 20 0 0 0 0 0 0
30 15 10 3 0 0 0 0
18 28 0 0 0 0 0 0
31 33 29 4 21 9 25 40
24 26 14 0 0 0 0 0
13 16 23 0 0 0 0 0
38 36 1 0 0 0 0 0
8 27 37 17 2 0 0 0
