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

ЛАБОРАТОРИЯ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Факультет вычислительной математики и кибернетики

Лаборатория ITLabИсследованияПроекты 2003-2009 гг.Научно-производственные проектыПрименение библиотеки генераторов VSL для решения прикладных исследовательских задач Switch to English version  
Новости
О Лаборатории
Обучение
Исследования
Проекты 2011 г.
Проекты 2010 г.
Проекты 2003-2009 гг.
Образовательные комплексы
Семинар Лаборатории
Мероприятия
Вакансии Интел
Сотрудничество
Разработчики сайта
О нас пишут
Летняя школа 2011
Видео лекции
Клуб У.М.Н.И.К.
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

  

Применение библиотеки генераторов случайных чисел и сверток/корреляций (VSL) для решения прикладных исследовательских задач

Краткое описание

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

Общее описание предметной области

Основным исследуемым программным средством является библиотека генераторов случайных чисел и сверток/корреляций (VSL), входящая в состав Intel Math Kernel Library (Intel MKL).

Методология решения задач – статистическое моделирование.

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

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

Среди задач, где может быть использован и часто используется этот подход, часто указывают следующие задачи:

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

и многие другие.

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

Цели проекта

Целью проекта является проведение исследований в задачах финансовой математики и дискретной оптимизации с целью определения эффективных подходов к решению этих задач с использованием современной вычислительной техники Intel и программных средств Intel (библиотеки VSL).

Данная цель включает решение следующих задач:

  • Анализ текущего состояния, проведение экспериментов и выбор подходов к решению задач финансовой математики и дискретной оптимизации.
  • Эффективная последовательная реализация алгоритмов для решения указанных задач.
  • Параллелизация алгоритмов. Анализ ускорения и масштабируемости.
  • Разработка демонстрационных приложений, решающих указанные задачи в различных постановках.
  • Сравнительный анализ использования различных С++ компиляторов (Intel С++ Compiler, Microsoft C++ Compiler, GCC) в указанных задачах.
  • Сравнительный анализ использования различных библиотек для статистического моделирования (MKL, BOOST, NAG, IMSL).
  • Публикация статей по результатам проведенных исследований.

Коллектив

В рамках проекта создается коллектив в составе:

Intel:

Куратор  проекта:

Майданов Сергей.

Научный руководитель проекта:

Николаев Андрей, к.ф.-м.н.

IT Lab:

Куратор  проекта:

Мееров Иосиф (к.т.н., асс. каф. МО ЭВМ ВМК ННГУ).

Исследователи:

Гагаринова Светлана (студентка 3к ВМК ННГУ, стажер IT Lab)

Горбунова Анна (студентка 4к ВМК ННГУ, стажер IT Lab),

Живодеров Артем (студент 3к ВМК ННГУ, стажер IT Lab).

Козинов Евгений (студент 5к ВМК ННГУ, стажер IT Lab),

Корняков Кирилл (студент 4к ВМК ННГУ, стажер IT Lab),

Курина Нина (студентка 4к ВМК ННГУ),

Шишков Александр (студент 4к ВМК ННГУ, стажер IT Lab).

В проекте ранее участвовали:

Бадер Алексей (студент ВМК ННГУ, стажер IT Lab).

Основные (ожидаемые) результаты

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

  1. Аннотированные списки литературы по указанной тематике. Фиксация постановок задач задач финансовой математики и дискретной оптимизации. Выбор подходов к решению этих задач в указанных постановках.
  2. Последовательная реализация алгоритмов для решения указанных задач. Оптимизация созданных реализаций.
  3. Параллельная реализация алгоритмов. Анализ ускорения и масштабируемости.
  4. Разработка демонстрационных приложений, решающих указанные задачи в различных постановках.
  5. Сравнительный анализ использования различных С++ компиляторов (Intel С++ Compiler, Microsoft C++ Compiler, GCC) в указанных задачах.
  6. Сравнительный анализ использования различных библиотек для статистического моделирования (MKL, BOOST, NAG, IMSL).
  7. Публикация статей по результатам проведенных исследований.

Текущие исследования

Организационная составляющая:

  • Создан коллектив стажеров IT Lab.
  • Организована работа (планы, отчеты, собрания…).
  • Организован мини-проект для кандидатов из нового набора стажеров.

Учебная составляющая:

  • Начата разработка учебных материалов для ННГУ по теме «Статистическое моделирование и параллельные вычисления».
  • Проведено 4 семинара в лаборатории.

Исследовательская составляющая:

  • Подготовлен аннотированный список литературы по данным темам.
  • Выделены основные подходы к решению задач, подготовлен аналитический обзор материалов.
  • Зафиксированы постановки задач:
    • определение цены опционов Бермудского типа;
    • поиск оптимального размещения элементов на плате.
  • Изучены алгоритмы, основными из которых являются:
    • Broadie-Glasserman Random Trees,
    • Broadie-Glasserman Stochastic Mesh,
    • CAPO, Dragon, Timberwolf.
  • Работа с 2-мя популярными алгоритмами (BGRT-97, SM2004).
    • BGRT-97: Проектирование, реализация, тестирование, отладка, оптимизация, параллелизация, сбор данных (IA-32, EM64T, IPF; Windows & Linux).
    • SM2004: Проектирование, реализация, тестирование, отладка, работы над уменьшением дисперсии.
    • Результаты опубликованы в материалах Международного семинара Высокопроизводительные параллельные вычисления на кластерных системах
      (Н. Новгород, 2005).
    • Результаты опубликованы в материалах конференции "Технологии Microsoft в науке и практике программирования" 
      (Н. Новгород, 2006).
    • Реализован алгоритм Dragon.
      • Каркас приложения.
      • Структуры данных.
      • Импорт данных.
      • Разбиение на подграфы (бины).
      • Перемещение бинов.
      • Размещение в бине.
      • Simulated annealing (перемещение между бинами).
      • Жадная оптимизация.
  • Экспорт результатов.
  • Визуализация процесса получения решения.

Основные направления текущей работы:

  • Финансовая математика:
    • Многоопционная задача – выбор оптимального набора акций для выпуска опциона. Создание демонстрационного ролика на основе разрабатываемого приложения.
    • Работа над уменьшением дисперсии оценок и оптимизацией по скорости алгоритма Stochastic Mesh.
    • Сравнительный анализ алгоритмов Stochastic Mesh и Random Trees.
    • Определение подходов к получению линейного ускорения в параллельной реализации алгоритма Random Trees на многоядерных архитектурах.

  • Дискретная оптимизация:
    • Реализация фаз алгоритма Dragon.
    • Оптимизация фаз.
    • Подготовка демонстрационного ролика на основе разрабатываемого приложения.

Публикации

1.      Горбунова А.С., Козинов Е.А., Мееров И.Б., Николаев А.Ф., Шишков А.В. Параллельная реализация одного алгоритма нахождения цены опционов Бермудского типа // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы пятого Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2005. – С. 60-67.

2.      Горбунова А.С., Козинов Е.А., Мееров И.Б., Шишков А.В. Исследование причин снижения ускорения в параллельной реализации алгоритма определения справедливой цены опциона при использовании двухядерной конфигурации с поддержкой технологии Hyper-Threading //  Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р.Г. Стронгина. –  Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 58-64.

3.      Горбунова А.С., Козинов Е.А., Мееров И.Б., Шишков А.В. Реализация алгоритма Stochastic Mesh для определения справедливой цены опциона Бермудского типа в условиях многомерного финансового рынка с нулевой корреляцией // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 64-69.

4.      Горбунова А.С., Козинов Е.А., Мееров И.Б., Шишков А.В. Применение Монте-Карло интегрирования для нахождения цены многомерного Европейского опциона с нулевой корреляцией между акциями //      Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р.Г. Стронгина. –  Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 70-72.

5.      Гагаринова С.А., Живодеров А.В., Корняков К.В., Курина Н.В., Мееров И.Б. Об одном подходе к решению задачи о размещении // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р.Г. Стронгина. –  Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 215-219.

6.      Гагаринова С.А., Живодеров А.В., Корняков К.В., Курина Н.В., Мееров И.Б. Использование метода имитации отжига для решения задачи размещения элементов на схеме // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 220-225.

Участие в конференциях и семинарах

  1. Пятый Международный научно-практический семинар "ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ НА КЛАСТЕРНЫХ СИСТЕМАХ". Нижний Новгород, 22-25 ноября 2005 г.
  2. Конференция "Технологии Microsoft в теории и практике программирования". Нижний Новгород, 21-22 марта 2006 г.

Учебные материалы

Курс для ННГУ «Статистическое моделирование и параллельные вычисления»

программа курса;
лекционные материалы по 1 разделу;
презентация курса;
презентации лекций по 1 разделу.

Новости

14.11.2015
16.10.2015
16.10.2015
14.10.2015
20.09.2015

© ITLab, Нижний Новгород,  2009