Использование parfor Ускорить код Монте-Карло

В этом примере показано, как ускорить код Монте-Карло при помощи parfor-циклы. Методы Монте-Карло встречаются во многих областях, включая физику, математику, биологию и финансы. Методы Монте-Карло включают выполнение функции много раз с случайным распределением входов. С помощью Parallel Computing Toolbox можно заменить for-цикл с parfor-цикл, чтобы легко ускорить код.

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

Аукцион в долларах

Аукцион в долларах - игра без нуля, впервые представленная Мартином Шубиком в 1971 году. В игре игроки выставляют ставки на купюру в один доллар. После того, как игрок делает ставку, каждый другой игрок может принять решение сделать ставку выше, чем предыдущий участник. Аукцион заканчивается, когда больше никто из игроков не решает сделать ставку. Самый высокий претендент получает одну долларовую купюру, однако, в отличие от типичного аукциона, как самый высокий, так и второй по величине претендент отдают свою ставку аукционеру.

Стохастическая модель

Можно смоделировать игры, подобные долларовому аукциону, используя стохастическую модель. Состояние (текущая ставка и количество активных игроков) может быть смоделировано с помощью марковских процессов, и поэтому можно ожидать, что результаты ( рыночное значение) будут иметь четко определенную статистику. Результаты получены из условного распределения, и поэтому долларовый аукцион идеально подходит для анализа Монте-Карло. На рыночное значение влияют следующие факторы:

  • Количество игроков, (nPlayers)

  • Действия игроки принимают

В этом примере следующий алгоритм определяет, какие действия принимают игроки (торги или выбытие) в зависимости от состояния.

  1. Установите ставку на предыдущую ставку плюс incr.

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

  3. Если ранее не было размещено ни одной заявки, перейдите к разделу 8.

  4. Если предыдущее предложение меньше 1, сгенерируйте случайное число от 0 до 1. Если случайное число меньше dropoutRate, перейдите к 7.

  5. Вычислим сколько денег gain может быть получен, если игрок делает выигрышную ставку.

  6. Вычислим сколько денег loss игрок проигрывает, если они являются вторым по значимости участником торгов. Если gain больше loss, перейдите к 8.

  7. Игрок выпадает. Удалите игрока из набора игроков, затем перейдите к 9.

  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')

Вычислительная скорость увеличивается с количеством работников.

Для просмотра документации необходимо авторизоваться на сайте