Обзор и сравнительный анализ библиотек

on

Введение. В настоящее время основным средством исследования сложных технологических и экономических систем является имитационное моделирование, с использованием которого решаются задачи оптимизации производственных процессов, оценивается отказоустойчивость роботизированных сборочных линий и конвейеров, исследуются режимы загрузки оборудования, отыскиваются эффективные стратегии комплексного управления логистическими процессами, проводится анализ финансово-экономического состояния предприятия, прогнозируются результаты различных управленческих решений и т. п. Важнейшими компонентами имитационных моделей, придающими им сходство с реальными явлениями, являются псевдослучайные числа (ПСЧ). Кроме того, ПСЧ находят широкое применение в численном анализе, тестировании алгоритмов, играх, сетевых протоколах и криптографии . С ростом размерности приложений и увеличением ответственности разработчиков программных систем, использующих имитационное моделирование для проектирования и отладки механизмов управления крупными промышленными комплексами, ужесточаются требования к генераторам ПСЧ. Возникла потребность в разработке генераторов, которые кроме способности удовлетворять заданным статистическим свойствам должны также обладать высокой производительностью. Вероятно, указанная потребность сложилась прежде всего у программистов, активно работающих с языками С и С++. Действительно, язык С++ и его предшественник С широко применяются в системном программировании, на них пишутся операционные системы, драйверы, трансляторы, интерфейсы различного назначения, программы, которые взаимодействуют с операционной системой и т. д. Кроме того, к универсальности языка программирования добавляется богатый набор разнообразных библиотек, позволяющих быстро и эффективно решать различные задачи программирования. Отсюда можно сделать вывод, что языки С и С++ являются наиболее популярным инструментарием разработчиков промышленных программных продуктов, в частности автоматизированных 66 Обзор и сравнительный анализ библиотек генераторовпсевдослучайных чисел 67 систем управления, описанных в работе . Интерес к повышению эффективности генераторов ПСЧ у специалистов, пишущих на языках С и C++, подтверждается наличием соответствующего раздела в предварительной версии нового стандарта C++. Таким образом, в данной работе прежде всего изучаются средства генерации ПСЧ, активно используемые программистами, пишущими на языках C и C++. Рассматривается библиотека векторной статистики (Vector Statistic Library (VSL)) от компании Intel, содержащая набор генераторов ПСЧ и являющаяся частью пакета MKL (Intel Math Kernel Library). По сути, VSL является набором процедур, которые возвращают массив ПСЧ с заданными свойствами. Также рассматривается библиотека генераторов ПСЧ, расширяющая возможности инструментария С++ Visual Studio 2008 (полное название Standard C++ Library TR1 Extensions for Visual Studio 2008). В данной библиотеке (назовем ее Microsoft random) генераторы ПСЧ реализованы в виде шаблонов классов, интерфейсы которых соответствуют промежуточной версии стандарта С++ (документ ISO/IEC DTR 19768). Кроме того, исследуются стандартные средства получения ПСЧ, встроенные в большинство компиляторов С и С++, проводятся обзор основных возможностей библиотек Intel VSL и Microsoft random и сравнительный анализ библиотек. 1. Средства генерации ПСЧ. Рассмотрим стандартные средства получения ПСЧ. 1.1. Стандартный генератор. Современные средства разработки программного обеспечения, как правило, содержат стандартный генератор — генератор целочисленной равномерно распределенной псевдослучайной величины от нуля до некоторого большого значения. В качестве метода получения случайной последовательности традиционно использовался линейный конгруэнтный метод либо его частный случай — мультипликативный метод . В настоящее время стремительно набирает популярность генератор ПСЧ, называемый вихрем Мерсенна (Mersenne twister), разработанный в 1997 г. японскими учеными М. Мацумото и Т. Нисимура . Принцип работы генератора основывается на свойствах простых чисел Мерсенна, вихрь-преобразование, которое обеспечивает равномерное распределение ПСЧ в 623 измерениях. (Для сравнения, у линейных конгруэнтных генераторов оно не превышает 5, кроме того, они проигрывают в производительности.) Существует несколько реализаций алгоритма, различающихся размером используемого простого числа Мерсенна, наиболее распространенным из которых является MT19937, обеспечивающий большой период, равный числу Мерсенна 219937 ? 1, что более чем достаточно практически для всех существующих приложений. Тем не менее появилась и критика генератора, в частности со стороны Д. Марсалья (George Marsaglia), являющегося признанным экспертом в области ПСЧ. Вихрь Мерсенна не является криптостойким генератором, что существенно затрудняет его использование в криптографии. Отмечалось, что генератор сложен в реализации. Метод генерации ПСЧ, предложенный Марсалья (multiply-with-carry), имеет простую реализацию, больший период и выигрывает в производительности. Однако появились и более эффективные реализации MT19937, исследования и усовершенствование генератора продолжаются. В то же время ряд исследователей в области методов Монте-Карло продолжает использовать хорошо изученный и статистически надежный линейный конгруэнтный метод, отмечая неудовлетворительные статистические свойства других генераторов. Таким образом, вопрос о наилучшем выборе генератора целочисленной равномерно распределенной псевдослучайной величины остается открытым и является делом вкуса. Обращение к стандартному генератору может иметь вид int rand (); 68 Получаем число от нуля до предопределенного большого числа (RAND_MAX). Однако стандартные генераторы, встроенные в компилятор, демонстрируют низкое качество . В частности, младшие биты в случайном числе обладают плохими статистическими свойствами, поэтому rand() % n нельзя назвать хорошим способом генерирования случайных чисел от 0 до n?1, более приемлемый результат получается, если предварительно получить ПСЧ с равномерным распределением от 0 до 1, т. е. использовать код следующего вида: (double(rand()) /RAND_MAX)*n; Генераторы ПСЧ с произвольным распределением, а также практически все генераторы случайных объектов (например, графов) основаны на использовании базового генератора, т. е. генератора ПСЧ, равномерно распределенных на интервале от 0 до 1. Источником для данных ПСЧ служит последовательность целочисленных равномерно распределенных псевдослучайных чисел, для генератора которойтакже будем использовать указанный термин. Последовательность ПСЧ, полученную с помощью базового генератора, будем называть базовой последовательностью. Конструкция базовых генераторов предполагает определение начального значения псевдослучайной последовательности (инициализация генератора), от которого посредством рекуррентных вычислений строятся ПСЧ. Если начальное значение фиксировано при каждом обращении к генератору, то последовательность ПСЧ будет повторяться. Иногда такая ситуация устраивает пользователей, например при отладке программ. Однако часто каждое новое выполнение программы необходимо начинать с новым начальным значением. Инициализировать генератор ПСЧ некоторым числом (i) можно следующим образом: int srand (int i); Начальное значение рекомендуется выбирать из окружения программы, часто для этого используются биты счетчика реального времени. Таким образом, стандартные средства генерации ПСЧ ограничиваются возможностью инициализации генератора и доступом к базовой последовательности. Возможность, например, изменять параметры генератора или получать ПСЧ с распределением, отличным от равномерного, в стандартных средствах отсутствует. 1.2. Библиотека VSL компании Intel Corporation. Поставляемая компанией Intel библиотека VSL генераторов ПСЧ входит в пакет Intel Math Kernel Library, позиционируемый как средство для математических расчетов с высокой производительностью, реализуемых с использованием языков программирования FORTRAN, C и С++. Для использования функций библиотеки VSL в (C/C++)-программах необходимо в соответствующей среде разработки указать путь до заголовочного файла mkl_vsl.h, который содержится в папке include корневой директории пакета. По сути, библиотека является набором процедур, интерфейс которых выглядит следующим образом: status = v type Rng distribution ( method, stream, n, r, ). Здесь v — символ, индикатор того, что функция содержится в библиотеке VSL; type — тип генерируемых данных (используется один из трех символов: s : для типа real; d : для типа double; i : для типа int; префикс Rng указывает на то, что процедура является генератором ПСЧ с функцией распределения, название которой раскрывает параметр distribution method — метод генерации ПСЧ с заданным распределением(метод обратной функции, метод отбраковки и т. п.); steram — идентификатор случайного потока Обзор и сравнительный анализ библиотек генераторов псевдослучайных чисел 69 (их может быть несколько); n — размер выборки ПСЧ; r — имя массива, который хранит сгенерированную выборку; status — флаг ошибки VSL (выполнение процедуры прошло успешно, ошибок нет; параметры распределения заданы некорректно; ошибка в инициализации базового генератора; система не может выделить память; некорректный идентификатор случайного потока и т. д.); distribution parameters — список параметров функции распределения генерируемой случайной величины. Следует отметить, что параметры обращения к генератору n и r являются независимыми, т. е. массив r должен быть описан заранее и содержать количество элементов, не меньшее, чем n. Функции библиотеки можно разделить на три группы: методы выбора и инициализации базового генератора, генераторы для наиболее распространенных функций распределения, дополнительные возможности, заключающиеся в методах манипуляции потоками, средствах подключения пользовательских генераторов и обработки сгенерированных ПСЧ. Библиотека содержит следующие базовые генераторы: — 32-битный мультипликативный генератор MCG(1132489760, 231 -1) ; — 32-битный генератор на основе виткового регистра сдвига с обобщенной отдачей GFSR(250,103) ; — комбинированный рекурсивный генератор MRG-32k3a ; — 59-битный мультипликативный генератор MCG(1313, 259) и генератор Уичмана-Хилла из библиотеки NAG Numerical Libraries ; — генератор квазислучайных чисел Соболь ; — генератор квазислучайных чисел Niederreiter . Имеется также ряд генераторов для основных функций распределения, приведенных в таблице. Некоторые генераторы реализованы несколькими методами, пользователь может указать конкретный метод посредством выбора параметра method. В приведенном ниже примере проводится оценка математического ожидания экспоненциально распределенной случайной величины по выборке из 10 000 значений. #include mkl_vsl.h int main(); { double r; /* массив для хранения ПСЧ */ double s; /* выборочное среднее */ VSLStreamStatePtr stream; int i, j; /* Инициализация */ s = 0.0; vslNewStream( stream, VSL_BRNG_MT19937, 280775); /* Генерация */ for ( i=0; i 10; i$++$ ) { vdRng Exponential (VSL_METHOD_DEXPONENTIAL_ICDF, stream, 1000, r, 1.0 ); for ( j=0; j 1000; j$++$ ) 70 Наполнение библиотек генераторов ПСЧ Блок ВозможностиIntel VSL Microsoft random Выбор начального значения Да Да Линейный конгруэнтный метод Да Да Базовые Вихрь Мерсенна Да Да функции Метод Марсалья (multiply-with-carry) Нет Да Квазислучайные числа Да Нет Доступ к базовой последовательности Нет Да Нормальное Да Да Равномерное Да Да Экспоненциальное Да Да Гамма Да Да Непрерывные Бета Да Нет распределения Коши Да Нет Вейбулла Да Нет Логнормальное Да Нет Рэлея Да Нет Лапласа Да Нет Равномерное Да Да Пуассона Да Да Дискретные Геометрическое Да Да распределения Гипергеометрическое Да Нет Биномиальное Да Да Отрицательное биномиальное Да Нет { s += r; } } s /= 10000.0; /* Удаление потока */ vslDeleteStream( stream ); /* Вывод результата */ printf( Sample mean of normal distribution = %f\n, s ); return 0; } Подробная информация о наполнении библиотеки и руководство по ее эксплуатации содержатся в работе . 1.3. Библиотека random компании Microsoft Corporation. Прототипом библиотеки Microsoft random можно считать соответствующую библиотеку в BOOST C++, которая изначально была основана на виртуальных функциях, а затем появился прототип с использованием шаблонов. После исправления ошибок, связанных с непортабельностью кода, обходом ограничений на инициализацию членов класса внутри объявления класса, улучшения интерфейса и компилятора в 2000 г. библиотека ПСЧ стала официальной частью BOOST C++. Предложения по улучшению интерфейсов библиотек были учтены экспертами комитета по стандартизации C++. В 2005 г. улучшенная версия интерфейсов вошла в предварительную версию (С++)-стандарта , известного также под названием TR1 (technical report 1). Обзор и сравнительный анализ библиотек генераторов псевдослучайных чисел 71 Интерфейсы, предложенные в стандарте, нашли применение в указанной выше библиотеке генераторов ПСЧ, реализованной Microsoft. Отметим, что TR1 не содержит рекомендаций по выборуметода генерации случайных величин с заданным распределением, их выбор фиксирован и определяется предпочтениями программистов Microsoft. Библиотека находится в свободном доступе на сайте Она снабжена инсталлятором, легко интегрируется с C++ Visual Studio 2008. Набор базовых генераторов включает линейный конгруэнтный метод, вихрь Мерсенна, метод Марсалья. Пользователь может самостоятельно устанавливать параметры метода, а также использовать базовые генераторы с предустановленными рекомендуемыми параметрами, прошедшими проверку. Функции распределения, покрываемые генераторами библиотеки, перечислены в таблице. В следующем примере показан интерфейс шаблонного класса для генерации ПСЧ с распределением Пуассона: template class IntType = int, class RealType = double class poisson_distribution { public: typedef RealType input_type; typedef IntType result_type; // конструктор и функции — члены класса explicit poisson_distribution(const RealType mean = RealType(1)); RealType mean() const; void reset(); template class UniformRandomNumberGenerator result_type operator()(UniformRandomNumberGenerator urng); }; Интерфейсы для генерации ПСЧ с другими законами распределений отличаются незначительно. Единственным классом, который не является шаблонным, является класс для распределения Бернулли. Приведенный ниже код демонстрирует модель использования возможностей библиотеки на примере оценки математического ожидания экспоненциальной случайной величины. #include random #include iostream int main() { std::tr1::mt19937 U(280775); std::tr1::exponential_distribution double dist(1.0); double s = 0.0; for ( int i = 0; i 10000; i$++$) { s+=dist(U); } s/=10000.0; std::cout «sample mean = » s std::endl; return (0); } 72 Здесь в качестве базового генератора используется вихрь Мерсенна MT19937, объем выборки равен 10 000 ПСЧ. 2. Сравнительный анализ библиотек. Выполним сравнительный анализ библиотек. 2.1. Качественные показатели. Поскольку библиотека Microsoft