Нижегородский государственный университет им.

 

"Статистическое моделирование и параллельные вычисления"

Программа специального курса

 

Нижний Новгород

2005


 

Лист регистрации версий документа

 

Дата

Автор изменения

Номер версии

Комментарии

17.02.05

1.0

Создание

20.10.05

2.0

1) Переработанный вариант программы курса.

2) Программа курса адаптирована для прочтения в виде специального курса для студентов старших курсов, магистрантов, обучающихся по специальностям “Прикладная математика”, “Информационные системы” и “Информационные технологии” и стажеров студенческих лабораторий при факультетах физико-математического профиля.

3) Внесены существенные изменения в содержание (наполнение) разделов.

4) Установлено соответствие с рекомендациями CC2001.

25.10.05

3.0

Скорректирована программа

 

Предпосылки создания курса

Статистическое моделирование – численный метод решения математических задач, при котором искомые величины представляют вероятностными характеристиками какого-либо случайного явления, это явление моделируется, после чего нужные характеристики приближённо определяют путём статистической обработки «наблюдений» модели.

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

НЕ нашли? Не то? Что вы ищете?

Привязка содержания курса к параллельным вычислениям связана со следующими факторами:

-        задачи статистического моделирования как правило требуют больших вычислительных ресурсов;

-        алгоритмы статистического моделирования чаще всего допускают эффективное распараллеливание.

 

Рекомендации Computing Curricular 2001

Данный курс затрагивает следующие разделы знания:

-        CS101I. Основы программирования.

-        CS102I. Объектно-ориентированные парадигмы.

-        CS103. Структуры данных и алгоритмы.

-        MA271. Статистика и эмпирические методы вычислений.

-        CS314. Параллельные алгоритмы.

-        CS304. Методы вычислений.

-        CS305. Численный анализ.

-        CS307. Статистическое моделирование.

-        CS308. Математическое программирование.

-        CS302. Вероятность и статистика.

 

Целевая аудитория

Данный курс предназначен для студентов старших курсов, магистрантов, обучающихся по специальностям «Прикладная математика», «Информационные технологии», «Информационные системы» и стажеров студенческих лабораторий, обучающихся на факультетах физико-математического профиля.

 

Цели и задачи курса

Целью курса является ознакомление с некоторыми задачами и алгоритмами статистического моделирования и методами генерации псевдослучайных чисел, а также рассмотрение основных методов распараллеливания данных задач и их эффективной реализации на многоядерных архитектурах.

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

В результате изучения теоретической части курса студент будет знать:

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

-        Некоторые приемы тестирования качества генераторов случайных чисел.

-        Некоторые приемы вычисления многомерных интегралов методом Монте-Карло.

-        Некоторые задачи стохастической оптимизации (в частности, моделирование методом «имитации отжига»).

-        Некоторые задачи финансовой математики и алгоритмы их решения.

В результате освоения практической части курса студент будет уметь:

-        Использовать библиотеку Intel® MKL для решения задач статистического моделирования (в том числе на системах с общей и разделяемой памятью).

-        Самостоятельно реализовывать генераторы случайных чисел различных распределений.

-        Проводить тестирование качества генераторов случайных чисел.

-        Проводить эксперименты на многопроцессорных и многоядерных системах.

 

Дисциплины, изучение которых необходимо при освоении данного курса

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

-        теория вероятностей;

-        математическая статистика;

-        основы программирования;

-        алгоритмы и структуры данных;

-        численные методы.

Содержание курса

1.      Введение в методы Монте-Карло

-        Статистическое моделирование как научное направление, его место в науке и технике. Приложения статистического моделирования.

-        Примеры задач: оценивание числа p методом статистического моделирования (Задача Бюффона, другие примеры).

-        Случайность. Неопределенность. Хаос.

-        Имитация случайности.

2.      Генераторы случайных чисел. Равномерное распределение.

-        Важность равномерного распределения.

-        Некоторые классы линейных генераторов (мультипликативный, линейный конгруэнтный, обобщение мультипликативного генератора (рекурсия более высокого порядка). GFSR генераторы. R250 и MT).

-        Меры качества генераторов.

-        Эмпирические тесты. Примеры (случайное блуждание, Craps, парковка, и др.)

-        Генераторы в параллельных вычислениях (WH, MT).

3.      Генераторы случайных чисел неравномерных распределений.

-        Метод обратной функции.

-        Метод принятия/отклонения альтернатив.

-        Использование свойств распределений.

-        Intel® Math Kernel Library. VSL.

4.      Монте-Карло интегрирование.

-        Квадратурные формулы и статистический подход.

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

5.      Стохастическая оптимизация

-        Изингова модель. «Имитация отжига» как задача глобальной оптимизации. Методы распараллеливания.

-        Примеры задач (Задача коммивояжера. Задача о композиции микросхем. Задача о расписании).

6.      Имитационное моделирование, приложения в задачах финансовой математики.

-        Финансовые рынки. Классическая модель Блэка-Шоулса.

-        Имитационное моделирование Блэка-Шоулса.

-        Понятие опциона. Виды опционов.

-        Задача об определении цены опциона Европейского, Бермудского и Американского типа. Алгоритмы и их эффективная реализация. Алгоритм Boadie-Glasserman Random Trees. Методы распараллеливания.

7.      Задачи статистического моделирования и их эффективное решение на многоядерных архитектурах.

-        Обзор архитектур (IA-32, IA-64, multicore architecture & HT technology).

-        Оптимизация под многоядерные архитектуры.

 

План курса

Лекции

№

Тема

Часов

1

Введение в методы Монте-Карло

4

2

Генераторы случайных чисел. Равномерное распределение.

2

3

Генераторы случайных чисел неравномерных распределений.

2

4

Монте-Карло интегрирование.

2

5

Стохастическая оптимизация.

2

6

Имитационное моделирование, приложения в задачах финансовой математики.

2

7

Задачи статистического моделирования и их эффективное решение на многоядерных архитектурах.

2

 

Итого:

16

 

Лабораторные работы

№

Тема

Часов

1

Оценивание p методами Монте-Карло. Сравнение скорости сходимости методов.

2

2

Реализация мультипликативного генератора «минимального стандарта». Оптимизация средствами компилятора.

2

3

Реализация эмпирических тестов (Runs-Up тест и др.) и тестирование базовых генераторов библиотеки MKL.

2

4

Параллельные реализации методов оценивания p. Применение генераторов и сервисных функций библиотеки MKL.

2

5

Вычисление многомерных интегралов. Сравнение квадратурных формул, прямого моделирования методом Монте-Карло, квази-Монте-Карло. Выборка по важности.

2

6

Решение задач финансовой математики методом Монте-Карло.

4

7

Оптимизация задач финансовой математики под многоядерные архитектуры.

2

 

Итого:

16

 

Рекомендуемая литература

Основная литература

1.      Г. Крамер. Математические методы статистики. М: «Мир», 1975

2.      J. Gentle. Random Number Generation and Monte Carlo Methods. Springer-Verlag NY, 1998

3.      , . Статистическое моделирование. М: «Наука», 1982

4.      D. E. Knuth. The Art of Computer Programming, Volume 2, Seminumerical Algorithms, 2nd edition, Addison-Wesley Publishing Company, Reading, Massachusetts, 1981.

5.      P. Glasserman. Monte Carlo Methods in Financial Engineering.-Series: Stochastic Modelling and Applied Probability, Vol. 53.-2003, XIII, 596 p.

 

Дополнительная литература

6.      VSL Notes. http://www.intel.com/software/products/mkl/docs/vslnotes.htm

7.      MKL Reference Manual. http://www.intel.com/software/products/mkl/docs/mklman.htm

8.      P. L'Ecuyer. Uniform Random Number Generation. Annals of Operations Research, 53 (1994), pp. 77-120.

9.      S. Maidanov, A. Naraikin. Making the Monte Carlo Approach Even Easier and Faster. NASA Tech Briefs, May 2004, vol. 28, No. 5, pp. 55-57 (e-version: http://cache-www.intel.com/cd/00/00/09/55/95571_95571.pdf).

10.  S. Maidanov. Monte Carlo European Options Pricing Implementation Using Various Industry Library Solutions. http://cache-www.intel.com/cd/00/00/06/13/61382_61382.pdf

11.  J. A. Chandy. Parallel algorithms for standard cell placement using simulated annealing. Phd, 1996.

12.  J. M. Varanelli. On the acceleration of simulated annealing. Phd, 1996.

13.  L. Stentoft Least Squares Monte-Carlo and GARCH Methods for American Options: Theory and Applications Phd, 2004. http://www.econ.au.dk/vip_htm/lstentoft/papers/2004-1_ls.pdf