§ 33. Некоторые особенности реализации метода Монте-Карло в современных универсальных вычислительных машинах и использование микроуправления

Существенным недостатком всех специализированных машин является их специализированность, т. е. приспособленность к сравнительно узкому классу задач. Поэтому специализированные машины хорошо используются только, если решаемые на них задачи встречаются достаточно часто в вычислительной практике. Так, широкое применение находят машины для решения систем обыкновенных дифференциальных уравнений (в том числе и выпускаемые серийно цифровые дифференциальные анализаторы).

Удачной оказалась группа цифровых вычислительных машин («Погода», «Кристалл»), предназначенных для вычисления сумм парных произведений вида

Такие машины легко применяются к вычислению коэффициентов Фурье для любых ортогональных систем, задач линейной алгебры (умножение матрицы на матрицу, матрицы на вектор, решение систем по методу простых итераций и т. п.), для задач рентгеноструктурного анализа и многих других. В обоих приведенных выше классах специализированных машин круг решаемых задач был издавна хорошо изучен.

Машины этих классов строились для решения задач, хотя и частных, но хорошо известных и широко применяемых в вычислительной практике. В задачах, решаемых по методу Монте-Карло, не накоплен еще достаточный вычислительный опыт. Эти задачи очень разнородны по своим параметрам.

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

случайных чисел, и неэкономичность использования возможностей обычных универсальных машин типа «Стрела», БЭСМ при решении задач по методу статистических испытаний.

Поясним сказанное примером. Рассмотрим простейший алгоритм — решение задачи Дирихле для уравнения Лапласа в прямоугольной области на плоскости методом блужданий (см. гл. V). Пусть область ограничена прямыми:

Тогда основной цикл вычислений состоит из следующих действий:

1. Прибавление к координатам блуждающей частицы случайного приращения.

2. Проверка выхода частицы на границу области. Эти действия повторяются наиболее часто, а именно раз за время решения задачи. Здесь — количество испытаний, среднее число узлов решетки, проходимых частицей до выхода ее на границу области. Все остальные действия повторяются, не более чем раз — только при выходе на границу. Эти положения подтверждаются блок - схемой программы решения данной задачи, приведенной на рис. 18.

Первое действие основного цикла состоит в выборе одной из равновероятных комбинаций 00, 01, 10, 11 и прибавлении к одной из координат частицы или у числа 1 или —1, в зависимости от выбранной комбинации.

Второе действие цикла заключается в проверке выполнения одного из равенств:

В специализированной машине этот цикл занимает один короткий такт сложения малоразрядных чисел (7—9 двоичных знаков). В обычной универсальной машине этот цикл требует примерно 10 операций над полноразрядными числами (в трехадресном коде типа машины «Стрела»).

(кликните для просмотра скана)

Действительно, этот цикл в универсальной машине выполняется примерно следующим образом:

а) выбираются два случайных числа полученных от датчика равномерно распределенных случайных чисел;

б) если преобразуется координата если

в) если новая координата образуется прибавлением единицы, если нет — вычитанием;

г) проверяются неравенства и если хотя бы одно из них не выполнено, то определяются граничные значения функции в точке

Таким образом, на универсальной машине цикл занимает в 10 раз больше времени по сравнению со специализированной только за счет служебных операций.

Кроме того, на обычных универсальных машинах время выполнения операций всегда будет больше, чем на специализированных ввиду того, что на универсальных машинах время операций рассчитывается в применении к полноразрядным (порядка сорока двоичных разрядов) числам, представленным в форме плавающей запятой, а на специализированных машинах операции выполняются над малоразрядными числами с фиксированной запятой.

Однако на некоторых современных универсальных вычислительных машинах (М-2, Урал-2 и др.) существует возможность по выбору выполнять действия с фиксированной или плавающей запятой.

Это позволяет заметно увеличивать производительность таких машин при решении задач по методу Монте-Карло. Так, при решении одной из крупных задач по моделированию сложного случайного процесса на машине Урал-2 была достигнута скорость порядка 11 000 операций в секунду, в то время как быстродействие этой же машины при использовании представления чисел в форме плавающей запятой составляет примерно 4000 операций в секунду.

На одной из последних американских машин ТХ-2 имеется возможность выполнять действия по желанию с числами, имеющими 36, 18 и 9 двоичных разрядов. При этом уменьшение разрядности чисел позволяет параллельно выполнять две или четыре арифметические операции. В случае задач, решаемых по методу Монте-Карло, всегда можно параллельно вести четыре испытания. В частности, для задачи Дирихле можно параллельно моделировать блуждания четырех частиц (некоторые легко преодолимые затруднения получаются из-за того, что частицы в разное время выходят на границу. Для этого можно только фиксировать точки выхода на границу, а потом уже вычислять суммарный штраф.) В машине ТХ-2 время сложения составляет при действиях с 36-разрядными числами - 150 000 операций в секунду, а при действиях с 9-разрядными числами - 600 000 операций в секунду. Поэтому при реализации метода Монте-Карло производительность машины ТХ-2 может составлять 2 400 000 операций в секунду.

Особенно широкие возможности возникают в вычислительных машинах с микроуправлением. Смысл микроуправления состоит в том, что каждая операция в машине изображается в виде так называемой микропрограммы, построенной из микрокоманд, так же как обычная программа строится из команд. Микрокоманды управляют простейшими операциями (так называемыми микрооперациями) такими, как открывание и закрывание группы клапанов, переброс триггеров. Меняя в маг шине набор микропрограмм, можно заменить набор операций.

Таким образом, в универсальной машине, решающей в течение длительного времени задачи по методу Монте-Карло, можно ввести наиболее приспособленный для этого набор операций и соответственно систему команд. Эти операции будут выполнять только минимально необходимые преобразования величин в машине. За счет этого производительность универсальной машины при решении некоторого класса монте - карловских задач можно довести до максимума, достижимого при данных технических характеристиках используемых элементов. В состав операций машины можно ввести такие, как;

одновременное преобразование координат х и у, хранимых в одной ячейке памяти; проверка группы неравенств типа с условным переходом по данному адресу при невыполнении хотя бы одного из этих неравенств и ряд других операций.

Наличие указанных команд в системе команд универсальной машины позволит при решении задачи Дирихле свести основной цикл всего к трем операциям вместо тринадцати и приблизит производительность универсальной машины к производительности специализированной. Эти же команды могут существенно помочь при решении других задач, связанных с проблемой блужданий.

С другой стороны, явно нецелесообразно вводить такие команды жестко в систему команд универсальной машины.

В самом деле, даже для других задач монте - карловского типа понадобятся десятки других аналогичных команд. Только использование микроуправления дает возможность введения в универсальные вычислительные машины команд такого типа.

Очень существенным является то обстоятельство, что в современных высокопроизводительных машинах (а метод статистических испытаний в основном приводит к задачам, решаемым именно на таких машинах) существует так называемая сверхоперативная или малая память. Выбор чисел из этой памяти происходит за время того же порядка или меньшее, чем время арифметической операции. Поэтому, например, при выполнении описанной выше сложной команды проверки неравенств числа а и нужно хранить в сверхоперативной памяти.

Дальнейший опыт решения задач по методу Монте-Карло на машинах высокой производительности позволит найти новые пути приспособления структуры универсальных машин к этим задачам и найти новые классы специализированных машин.