parfor
Ускорить код Монте-КарлоВ этом примере показано, как ускорить код Монте-Карло при помощи parfor
-циклы. Методы Монте-Карло встречаются во многих областях, включая физику, математику, биологию и финансы. Методы Монте-Карло включают выполнение функции много раз с случайным распределением входов. С помощью Parallel Computing Toolbox можно заменить for
-цикл с parfor
-цикл, чтобы легко ускорить код.
Этот пример запускает простую стохастическую симуляцию, основанное на долларовом аукционе. Выполните несколько симуляций, чтобы найти рыночное значение для банкноты в один доллар с помощью метода Монте-Карло. В этом примере аукцион в долларах рассматривается как функция черного ящика, которая производит выходы, которые зависят от случайных процессов. Чтобы узнать больше о модели, смотрите Dollar Auction. Чтобы увидеть, как ускорить код Монте-Карло в целом, смотрите Использование цикла parfor для оценки рыночного значения.
Аукцион в долларах - игра без нуля, впервые представленная Мартином Шубиком в 1971 году. В игре игроки выставляют ставки на купюру в один доллар. После того, как игрок делает ставку, каждый другой игрок может принять решение сделать ставку выше, чем предыдущий участник. Аукцион заканчивается, когда больше никто из игроков не решает сделать ставку. Самый высокий претендент получает одну долларовую купюру, однако, в отличие от типичного аукциона, как самый высокий, так и второй по величине претендент отдают свою ставку аукционеру.
Можно смоделировать игры, подобные долларовому аукциону, используя стохастическую модель. Состояние (текущая ставка и количество активных игроков) может быть смоделировано с помощью марковских процессов, и поэтому можно ожидать, что результаты ( рыночное значение) будут иметь четко определенную статистику. Результаты получены из условного распределения, и поэтому долларовый аукцион идеально подходит для анализа Монте-Карло. На рыночное значение влияют следующие факторы:
Количество игроков, (nPlayers
)
Действия игроки принимают
В этом примере следующий алгоритм определяет, какие действия принимают игроки (торги или выбытие) в зависимости от состояния.
Установите ставку на предыдущую ставку плюс incr
.
Выберите игрока наугад из игроков, которые не являются предыдущим участником конкурса.
Если ранее не было размещено ни одной заявки, перейдите к разделу 8.
Если предыдущее предложение меньше 1, сгенерируйте случайное число от 0 до 1. Если случайное число меньше dropoutRate
, перейдите к 7.
Вычислим сколько денег gain
может быть получен, если игрок делает выигрышную ставку.
Вычислим сколько денег loss
игрок проигрывает, если они являются вторым по значимости участником торгов. Если gain
больше loss
, перейдите к 8.
Игрок выпадает. Удалите игрока из набора игроков, затем перейдите к 9.
Игрок делает ставку.
Если осталось 2 или более игроков, перейдите к шагу 1.
Вспомогательная функция dollarAuction
моделирует аукцион в долларах. Для просмотра кода смотрите dollarAuction.m
. Функция принимает три входов: nPlayers
, incr
, и dropoutRate
. Установите каждое из значений.
nPlayers = 20; incr = 0.05; dropoutRate = 0.01;
Запустите случайный сценарий путем выполнения dollarAuction
функция. Сохраните выходы bids
и dropouts
.
[bids,dropouts] = dollarAuction(nPlayers,incr,dropoutRate);
Когда игра продолжается, некоторые игроки размещают заявки, а некоторые выбывают. Если ставка превышает 1, игроки блокируются в «войне торгов», пока не останется только один игрок.
Таблица dropouts
содержит две переменные: Player
, уникальный номер, присвоенный каждому игроку; Epoch
, раунд торгов, когда Player
выпал. Использование findgroups
для группирования dropouts.Epoch
, и использовать splitapply
чтобы получить количество игроков, которые выбывают в каждом из уникальных раундов в dropouts.Epoch
.
[G,epochs] = findgroups(dropouts.Epoch); numberDropouts = splitapply(@numel,dropouts.Epoch,G);
Изначально отсева нет. Добавить эту информацию в epochs
и numberDropouts
путем предварительной обработки 1
и 0
.
epochs = [1;epochs]; numberDropouts = [0;numberDropouts];
Использование nPlayers
и cumsum
вычислить количество игроков, оставшихся от numberDropouts
. Рассчитать ставки можно используя incr
и epochs
. Использование stairs
для построения графика предложения с учетом совокупной суммы numberDropouts
.
playersRemaining = nPlayers - cumsum(numberDropouts); stairs(incr*epochs,playersRemaining) xlabel('Bid') ylabel('Number of players remaining')
Можно оценить рыночную стоимость счета-фактуры со значением origValue
при помощи методов Монте-Карло. Здесь вы производите модель Monte-Carlo и сравниваете скорость с и без Parallel Computing Toolbox. Установите количество испытаний nTrials
используется для случайной выборки результатов.
nTrials = 10000;
Можно выборить возможные результаты путем выполнения вспомогательной функции dollarAuction
несколько раз. Использование for
-цикл для производства nTrials
выборки, хранящие последнюю ставку из каждого испытания в B
. Каждый раз, когда вы запускаете dollarAuction
функция, вы получаете различные результаты. Однако, когда вы запускаете функцию много раз, результаты, которые вы получаете из всех запусков, будут иметь четко определенную статистику.
Запишите время, необходимое для вычисления nTrials
симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс пять раз, затем возьмите минимальное истекшее время.
t = zeros(1,5); for j = 1:5 tic B = zeros(1,nTrials); for i = 1:nTrials bids = dollarAuction(nPlayers,incr,dropoutRate); B(i) = bids.Bid(end); end t(j) = toc; end forTime = min(t)
forTime = 21.4323
Использование histogram
для построения гистограммы окончательных предложений B
. Использование xline
наложение графика на исходное значение (один доллар) и среднюю рыночную стоимость, заданную mean
.
histogram(B); origLine = xline(1,'k','LineWidth',3); marketLine = xline(mean(B),'k--','LineWidth',3); xlabel('Market value') ylabel('Frequency') legend([origLine, marketLine],{'Original value','Market value'},'Location','NorthEast')
При заданных алгоритме и входных параметрах средняя рыночная стоимость больше исходного значения.
parfor
-цикл для оценки рыночного значенияВы можете использовать Parallel Computing Toolbox, чтобы легко ускорить код Монте-Карло. Сначала создайте параллельный пул с четырьмя рабочими, использующими 'local'
профиль.
p = parpool('local',4);
Starting parallel pool (parpool) using the 'local' profile ... Connected to the parallel pool (number of workers: 4).
Замените for
-цикл с parfor
-цикл. Запишите время, необходимое для вычисления nTrials
симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс 5 раз, затем возьмите минимальное истекшее время.
t = zeros(1,5); for j = 1:5 tic parfor i = 1:nTrials bids = dollarAuction(nPlayers,incr,dropoutRate); B(i) = bids.Bid(end); end t(j) = toc; end parforTime = min(t)
parforTime = 5.9174
С четырьмя рабочими результаты указывают, что код может запускаться в три раза быстрее, когда вы используете parfor
-цикл.
parfor
- циклыКогда вы генерируете случайные числа в parfor
-loop, каждый запуск цикла может привести к различным результатам. Чтобы создать воспроизводимые результаты, каждая итерация цикла должна иметь детерминированное состояние для генератора случайных чисел. Для получения дополнительной информации см. Раздел «Повторение случайных чисел в циклах parfor».
Вспомогательная функция dollarAuctionStream
принимает четвертый аргумент, s
. Эта поддерживающая функция использует указанный поток, чтобы получить случайные числа. Для просмотра кода смотрите dollarAuctionStream.m
.
Когда вы создаете поток, субпотоки этого потока являются статистически независимыми. Для получения дополнительной информации смотрите RandStream
. Чтобы убедиться, что ваш код каждый раз производит одинаковое распределение результатов, создайте поток генератора случайных чисел в каждой итерации цикла, затем установите Substream
свойство индексу цикла. Замените dollarAuction
с dollarAuctionStream
, затем используйте s
чтобы запустить dollarAuctionStream
на работника.
Запишите время, необходимое для вычисления nTrials
симуляции. Чтобы уменьшить статистический шум за истекшее время, повторите этот процесс пять раз, затем возьмите минимальное истекшее время.
t = zeros(1,5); for j = 1:5 tic parfor i = 1:nTrials s = RandStream('Threefry'); s.Substream = i; bids = dollarAuctionStream(nPlayers,incr,dropoutRate,s); B(i) = bids.Bid(end); end t(j) = toc; end parforTime = min(t)
parforTime = 8.7355
Вы можете масштабировать свой код от рабочего стола до кластера с большим количеством работников. Дополнительные сведения о масштабировании с рабочего стола на кластер см. в разделе Шкале с рабочего стола на кластер.
Использование delete
для завершения работы существующего параллельного пула.
delete(p);
Вычислите вспомогательную функцию dollarAuctionStream
в parfor
-цикл. Запустите ту же parfor
-цикл с различными числами работников и запись истекшего времени. Чтобы уменьшить статистический шум за истекшее время, запустите parfor
-цикл пять раз, затем взять минимальное истекшее время. Запишите минимальное время в массиве elapsedTimes
. В следующем коде замените MyCluster
с именем профиля кластера.
workers = [1 2 4 8 16 32]; elapsedTimes = zeros(1,numel(workers)); % Create a pool using the 'MyCluster' cluster profile p = parpool('MyCluster', 32);
Starting parallel pool (parpool) using the 'MyCluster' profile ... Connected to the parallel pool (number of workers: 32).
for k = 1:numel(workers) t = zeros(1,5); for j = 1:5 tic parfor (i = 1:nTrials, workers(k)) s = RandStream('Threefry'); s.Substream = i; bids = dollarAuctionStream(nPlayers,incr,dropoutRate,s); B(i) = bids.Bid(end); end t(j) = toc; end elapsedTimes(k) = min(t); end
Analyzing and transferring files to the workers ...done.
Вычислите вычислительное ускорение путем деления elapsedTimes(1)
по временам в elapsedTimes
. Исследуйте сильное масштабирование путем построения графика скорости относительно количества работников.
speedup = elapsedTimes(1) ./ elapsedTimes; plot(workers,speedup) xlabel('Number of workers') ylabel('Computational speedup')
Вычислительная скорость увеличивается с количеством работников.