Этот пример смотрит на то, почему настолько трудно дать конкретный ответ на вопрос, "Как мое (параллельное) приложение выполнит на моей многожильной машине или в моем кластере?" Ответ, обычно данный, "Он зависит от вашего приложения, а также вашего оборудования", и мы попытаемся объяснить, почему это - все, что можно сказать без большей информации.
Этот пример показывает конкуренцию для доступа к памяти, что мы можем столкнуться на регулярном многоядерном компьютере. Этот пример иллюстрирует случай всех рабочих, работающих на том же многоядерном компьютере только с одним центральным процессором.
Связанные примеры:
Чтобы упростить проблему под рукой, мы протестируем способности компьютера в сравнении с эталоном выполнить проблемы параллели задачи, которые не включают диск IO. Это позволяет нам игнорировать несколько факторов, которые могут влиять на параллельные приложения, такие как:
Объем межпроцессного взаимодействия
Сетевая пропускная способность и задержка для межпроцессного взаимодействия
Запуск процесса и времена завершения работы
Время, чтобы отправить запросы процессам
Дисковая IO эффективность
Это оставляет нас с только:
Время, проведенное, выполняя задачу, параллельно коду
Чтобы изучить, почему стоит выполнить такой простой сравнительный тест, рассмотрите следующий пример: Если один человек может заполнить один блок воды, нести его некоторое расстояние, опорожнить его и забрать его, чтобы пополнить его через одну минуту, сколько времени потребуется два человека, чтобы пойти тот же цикл обработки с одним блоком каждый? Эта простая аналогия тесно отражает сравнительные тесты параллели задачи в этом примере. На первый взгляд кажется абсурдным, что должно быть любое уменьшение в КПД, когда два человека одновременно делают то же самое по сравнению с одним человеком.
Если все вещи совершенны в нашем предыдущем примере, два человека завершают один цикл с блоком воды каждый за одну минуту. Каждый человек быстро заполняет один блок, несет блок месту назначения, опорожняет его и идет назад, и они убеждаются, что никогда не вмешались или прервали друг друга.
Однако предположите, что они должны заполнить блоки от одного, маленького водного шланга. Если бы они прибывают в шланг одновременно, нужно было бы ожидать. Это - один пример конкуренции для совместно используемого ресурса. Возможно, эти два человека не должны одновременно использовать шланг, и шланг поэтому удовлетворяет их потребности; но если у вас есть 10 человек, транспортирующих блок каждый, некоторым придется всегда ожидать.
В нашем случае водный шланг соответствует компьютерному оборудованию, которое мы используем, в частности доступ к памяти компьютера. Если несколько программ запускают одновременно на одном ядре процессора каждого, и им всем нужен доступ к данным, которые хранятся в памяти компьютера, некоторым программам, вероятно, придется ожидать из-за пропускной способности ограниченной памяти.
Чтобы взять нашу аналогию немного далее, предположите, что у нас есть конкуренция в шланге, когда два человека несут один блок каждый, но затем мы изменяем задачу и просим, чтобы они несли воду вполне немного еще дальше от шланга. При выполнении этой модифицированной задачи эти два человека тратят большую пропорцию своего времени, делая, работают, i.e., идя с блоками и меньшей пропорцией их времени, споря по совместно используемому ресурсу, шлангу. Им, поэтому менее вероятно, будет нужен шланг одновременно, таким образом, эта модифицированная задача будет иметь более высокий параллельный КПД, чем исходный.
В случае сравнительных тестов в этом примере это соответствует, с одной стороны, под управлением программам, которые требуют большого доступа к памяти компьютера, но они выполняют очень мало, работают с данными, однажды выбранными. Если с другой стороны, программы выполняют много расчетов с данными, это становится не важным, сколько времени это взяло, чтобы выбрать данные, время вычисления омрачит потраченное ожидание времени доступа к памяти.
Предсказуемость доступа к памяти алгоритма также эффекты, как спорил доступ к памяти, будет. Если к памяти получат доступ регулярным, предсказуемым способом, мы не испытаем ту же сумму конкуренции как тогда, когда к памяти получают доступ неправильным способом. Это видно далее ниже, где, например, вычисления сингулярного разложения приводят к большему количеству конкуренции, чем умножение матриц.
Код, показанный в этом примере, может быть найден в этой функции:
function paralleldemo_resource_bench
Мы будем использовать параллельный пул, чтобы вызвать наши тестовые функции параллели задачи, таким образом, мы запустим путем проверки, открыт ли пул. Обратите внимание на то, что, если параллельный пул использует рабочих, работающих на нескольких компьютерах, вы не можете испытать ни одну конкуренцию ресурса, что мы пытаемся проиллюстрировать.
p = gcp; if isempty(p) error('pctexample:backslashbench:poolClosed', ... ['This example requires a parallel pool. ' ... 'Manually start a pool using the parpool command or set ' ... 'your parallel preferences to automatically start a pool.']); end poolSize = p.NumWorkers;
Для наших вычислений мы создаем входную матрицу, достаточно большую, что она должна быть принесена из памяти компьютера на центральный процессор каждый раз, когда она обрабатывается. Таким образом, мы делаем его столь большим, что мы сознательно вызываем конкуренцию ресурса.
sz = 2048; m = rand(sz*sz, 1);
Эти расчеты очень просты: Неоднократно суммируйте единый массив. Поскольку расчеты очень легки, мы ожидаем видеть конкуренцию ресурса при выполнении нескольких копий этой функции одновременно с большим входным массивом.
function sumOp(m) s = 0; for itr = 1:100 % Repeat multiple times to get accurate timing s = s + sum(m); end end
Ядро функции синхронизации состоит из простого spmd
оператор. Заметьте, что мы сохраняем минимальное время выполнения, наблюдаемое для данного уровня параллелизма, n
. Как утверждено вначале, мы тестируем проблем параллели задачи в сравнении с эталоном, измеряя только фактическое время выполнения. Это означает, что мы не тестируем эффективности в сравнении с эталоном MATLAB, Parallel Computing Toolbox™ или spmd
построение языка. Скорее мы тестируем способности в сравнении с эталоном нашей ОС и оборудования, чтобы одновременно запустить несколько копий программы.
function time = timingFcn(fcn, numConcurrent) time = zeros(1, length(numConcurrent)); for ind = 1:length(numConcurrent) % Invoke the function handle fcn concurrently on n different labs. % Store the minimum time it takes all to complete. n = numConcurrent(ind); spmd(n) tconcurrent = inf; for itr = 1:5 labBarrier; tic; % Measure only task parallel runtime. fcn(); tAllDone = gop(@max, toc); % Time for all to complete. tconcurrent = min(tconcurrent, tAllDone); end end time(ind) = tconcurrent{1}; clear tconcurrent itr tAllDone; if ind == 1 fprintf('Execution times: %f', time(ind)); else fprintf(', %f', time(ind)); end end fprintf('\n'); end
Мы измеряемся, сколько времени это берет, чтобы одновременно оценить n
копии суммирования функционируют для различных значений n
. Поскольку вычисления суммирования так просты, мы ожидаем сталкиваться с конкуренцией ресурса когда рабочие множители этих расчетов одновременно на многожильном центральном процессоре. Следовательно, мы ожидаем, что он займет больше времени, чтобы выполнить функцию суммирования, когда мы выполним несколько таких оценок одновременно, чем это берет, чтобы выполнить сингл такая оценка на в противном случае неактивном центральном процессоре.
tsum = timingFcn(@() sumOp(m), 1:poolSize);
Execution times: 0.367254, 0.381174, 0.395128, 0.421978
Мы теперь смотрим на более в вычислительном отношении интенсивную проблему, то из вычисления БПФ нашего вектора. Поскольку БПФ более в вычислительном отношении интенсивен, чем суммирование, мы ожидаем, что не будем видеть тех же ухудшений эффективности, когда параллельная оценка множественных вызовов БПФ функционирует, как мы видели с вызовами функции суммирования.
function fftOp(m) for itr = 1:10 % Repeat a few times for accurate timing fft(m); end end tfft = timingFcn(@() fftOp(m), 1:poolSize);
Execution times: 1.078532, 1.196302, 1.358666, 1.570749
Наконец, мы смотрим на еще более в вычислительном отношении интенсивную проблему или, чем БПФ или, чем суммирование. Доступ к памяти в умножении матриц является также очень регулярным, таким образом, эта проблема поэтому имеет потенциал, который будет выполняться вполне эффективно параллельно на многожильной машине.
function multOp(m) m*m; %#ok<VUNUS> % No need to repeat for accurate timing. end m = reshape(m, sz, sz); tmtimes = timingFcn(@() multOp(m), 1:poolSize); clear m;
Execution times: 0.667003, 0.768181, 0.846016, 0.989242
Мы создаем простую столбчатую диаграмму, показывающую ускорение, достигнутое путем выполнения нескольких вызовов функции одновременно. Этот вид графика показывает ускорение с тем, что известно как слабое масштабирование. Слабое масштабирование состоит в том, где количество процессов/процессоров варьируется, и проблемный размер на каждом процессе/процессоре фиксируется. Это оказывает влияние увеличения общего проблемного размера, когда мы увеличиваем число процессов/процессоров. С другой стороны, сильное масштабирование состоит в том, где проблемный размер фиксируется, и количество процессов/процессоров варьируется. Эффект этого - это, когда мы увеличиваем число процессов/процессоров, работы, сделанной каждым процессом/процессором уменьшения.
allTimes = [tsum(:), tfft(:), tmtimes(:)]; % Normalize the execution times. efficiency = bsxfun(@rdivide, allTimes(1, :), allTimes); speedup = bsxfun(@times, efficiency, (1:length(tsum))'); fig = figure; ax = axes('parent', fig); bar(ax, speedup); legend(ax, 'vector sum', 'vector fft', 'matrix mult', ... 'Location', 'NorthWest') xlabel(ax, 'Number of concurrent processes'); ylabel(ax, 'Speedup') title(ax, ['Effect of number of concurrent processes on ', ... 'resource contention and speedup']);
Смотря на график выше, мы видим, что эти простые проблемы масштабируются очень по-другому на том же компьютере. Когда мы также смотрим на то, что другие проблемы и различные компьютеры могут показать совсем другое поведение, должно стать ясно, почему невозможно дать общий ответ на вопрос, "Как мое (параллельное) приложение выполнит на моей многожильной машине или в моем кластере?" Ответ на тот вопрос действительно зависит от приложения и рассматриваемого оборудования.
Конкуренция ресурса не зависит только от функции, которую мы выполняем, но также и от размера данных, которые мы обрабатываем. Чтобы проиллюстрировать это, мы измеряем времена выполнения различных функций с различными размерами входных данных. Как прежде, мы тестируем способности в сравнении с эталоном нашего оборудования выполнить эти расчеты одновременно, и мы не тестируем в сравнении с эталоном MATLAB или его алгоритмов. Мы используем больше функций, чем прежде так, чтобы мы могли исследовать эффекты различных шаблонов доступа к памяти, а также эффекты различных размеров данных.
szs = [128, 256, 512, 1024, 2048]; description = {'vector sum', 'vector fft', 'matrix mult', 'matrix LU', ... 'matrix SVD', 'matrix eig'};
Мы циклично выполняемся через различные размеры данных и функции, мы хотим протестировать в сравнении с эталоном, и измерить наблюдаемое ускорение. Мы сравниваем последовательное время выполнения со временем, которое требуется, чтобы выполнить одновременно столько вызовов, сколько у нас есть лаборатории в пуле.
speedup = zeros(length(szs), length(description)); for i = 1:length(szs) sz = szs(i); fprintf('Using matrices of size %d-by-%d.\n', sz, sz); j = 1; for f = [{@sumOp; sz^2; 1}, {@fftOp; sz^2; 1}, {@multOp; sz; sz}, ... {@lu; sz; sz}, {@svd; sz; sz}, {@eig; sz; sz}] op = f{1}; nrows = f{2}; ncols = f{3}; m = rand(nrows, ncols); % Compare sequential execution to execution on all labs. tcurr = timingFcn(@() op(m), [1, poolSize]); speedup(i, j) = tcurr(1)/tcurr(2)*poolSize; j = j + 1; end end
Using matrices of size 128-by-128. Execution times: 0.001472, 0.001721 Execution times: 0.002756, 0.004069 Execution times: 0.000221, 0.000367 Execution times: 0.000200, 0.000369 Execution times: 0.001314, 0.002186 Execution times: 0.006565, 0.009958 Using matrices of size 256-by-256. Execution times: 0.005472, 0.005629 Execution times: 0.010400, 0.013956 Execution times: 0.002175, 0.002994 Execution times: 0.000801, 0.001370 Execution times: 0.008052, 0.009112 Execution times: 0.042912, 0.057383 Using matrices of size 512-by-512. Execution times: 0.021890, 0.022754 Execution times: 0.055563, 0.083730 Execution times: 0.011029, 0.017932 Execution times: 0.005655, 0.009090 Execution times: 0.052226, 0.067276 Execution times: 0.262720, 0.353336 Using matrices of size 1024-by-1024. Execution times: 0.090294, 0.110154 Execution times: 0.317712, 0.445605 Execution times: 0.097819, 0.131056 Execution times: 0.037662, 0.057474 Execution times: 0.392037, 0.937005 Execution times: 1.063107, 1.579232 Using matrices of size 2048-by-2048. Execution times: 0.365510, 0.422942 Execution times: 1.067788, 1.560758 Execution times: 0.667548, 0.980306 Execution times: 0.271354, 0.391217 Execution times: 4.111523, 7.820437 Execution times: 6.101292, 8.984251
Когда мы смотрим на результаты, мы должны иметь в виду, как функция взаимодействует с кэшем на центральном процессоре. Для небольших размеров данных мы всегда работаем из кэша центрального процессора на все эти функции. В этом случае мы ожидаем видеть совершенное ускорение. Когда входные данные являются слишком большими, чтобы поместиться в кэш центрального процессора, мы начинаем видеть ухудшение эффективности, вызванное конкуренцией для доступа к памяти. Это происходит несколькими способами, но для этого примера, следующее является самым важным:
Функция выполняет относительно небольшое количество расчета с данными. Сумма вектора является хорошим примером этого.
Функциональные данные о доступах в маленьких фрагментах или имеют неправильные шаблоны доступа к данным. Следующий график показывает это с вычислениями собственного значения (eig) и сингулярным разложением (svd).
fig = figure; ax = axes('parent', fig); plot(ax, speedup); lines = ax.Children; set(lines, {'Marker'}, {'+', 'o', '*', 'x', 's', 'd'}'); hold(ax, 'on'); plot(ax, repmat(poolSize, 1, length(szs)), '--'); hold(ax, 'off'); legend(ax, [description, {'ideal speedup'}], 'Location', 'SouthWest'); ax.XTick = 1:length(szs); ax.XTickLabel = arrayfun(@(x) {sprintf('%d^2', x)}, szs); yl = ylim; ylim([0, max([poolSize + 0.1, yl(2)])]) xlabel(ax, 'Number of elements per process'); ylabel(ax, 'Speedup') title(ax, 'Effect of data size on resource contention and speedup');
end