Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лекции 66 часа Экзамен 5,6 семестр семинары 66 часа Зачет нет лабораторные... 1 125.37kb.
Лекции 32 час Экзамен 8 семестр семинары 16 Зачет с оценкой нет лабораторные... 1 31.5kb.
Лекции 2 часа Практические занятия 52 часа срс 27 часов Всего 81... 1 150.96kb.
Лекции (64 часа), экзамен в 8-м семестре семинары (64 часа) 1 46.71kb.
Современные проблемы физики рабочая программа 2 353.6kb.
Лекции 18 час. Практические / лабораторные занятия 1 8 час. 1 79.9kb.
Менеджмент Институциональная экономика Дисциплина «Институциональная... 1 10.3kb.
Программа дисциплины «Пол, гендер и сексуальность» 1 195.98kb.
Лекции 34 часа, семинарские занятия (415 группа) 34 часа кафедра... 1 22.82kb.
Лекции 72 часа Форма контроля экзамен (в письменной форме), промежуточные... 1 28.42kb.
Забайкальский край муниципальный район «балейский район» 1 290.41kb.
Учебная программа для специальностей 1 430102 электроэнергетические... 1 47.23kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные - страница №1/1


министерство образования и науки российской федерации

Московский физико-технический институт

(государственный университет)


УТВЕРЖДАЮ

Проректор по учебной работе

Ю.А. Самарский

« 27 » января 2011 г.

П Р О Г Р А М М А



по курсу ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ

ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

по направлению 010900

факультет ФУПМ

кафедра математических основ управления

курс IV

семестр – 8


лекции – 32 часа Экзамен – нет

семинары – 32 часа Зачет с оценкой – 8 семестр

лабораторные занятия – нет


самостоятельная работа – 2 часа в неделю

ВСЕГО ЧАСОВ – 64




Программу составил к.ф.-м.н. И.Н. Коньшин




Программа обсуждена на заседании кафедры

математических основ управления

12 января 2011 года

Заведующий кафедрой С.А. Гуз


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


Данный курс является введением в параллельные методы дискретного программирования.

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

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

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

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

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



Программа курса
1. Многопроцессорные вычислительные системы, их классификация. Архитектуры с общей и распределенной памятью. Статический и динамический параллелизм. Параллельные вычисления. Основные понятия: параллельная эффективность, ускорение. Измерение параллельной производительности.

2. Вычислительные системы с общей памятью. Произвольный доступ к памяти, PRAM архитектура. Программный интерфейс OpenMP. Программирование в языках C и Fortran. Процессы, вычислительные нити, потоки. Синхронизация доступа к общим данным, семафоры. Примеры программ.

3. Вычислительные системы с распределенной памятью. Кластеры. Программный интерфейс MPI. Основные типы функций: инициализация вычислений, парные обмены, коллективные обмены, барьеры. Примеры программ.

4. Параллельные методы вычислительной математики. Степень параллелизма алгоритма, зернистость алгоритма. Зависимость по данным. Методы декомпозиции, разбиение области и распределение данных по процессорам.

5. Линейная алгебра. Прямые методы решения линейных систем. Базовые способы распределения данных по процессорам. Организация обменов. Параллельная эффективность основных алгоритмов.

6. Линейная алгебра. Итерационные методы решения линейных систем. Ускорение сходимости итерационных методов. Распределение данных по процессорам. Параллельная эффективность вычислений.

7. Параллельные методы линейного программирования. Задачи оптимизации. Прямая и двойственная задача. Метод Ньютона. Варианты распределения данных по процессорам, параллельная реализация и параллельная эффективность.

8. Задачи дискретной оптимизации. Задача о ранце.

Метод динамического программирования. Структуры данных, организация обменов. Параллельная реализация.

9. Метод ветвей и границ. Дерево ветвления. Параллельная реализация. Балансировка дерева вычислений. Пороговое число ветвлений. Комбинированные алгоритмы.

10. Другие задачи дискретной оптимизации и параллельные версии их решения. Задачи транспортного типа. Задачи теории графов.

Методы динамического программирования, параллельная реализация МДП для задачи о ранце.

Алгоритмы приближенного решения задачи о комивояжере (декомпозиция, параллельное решение подзадач, приближенное решение).

11. Смежные вопросы методов оптимизации и их распараллеливание.

Метод Ньютона. Симплекс-метод. Многокритериальная оптимизация.

Литература





  1. Воеводин В.В., Воеводин В.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.

  2. Богачев К.Ю. Основы параллельного программирования. – М.: Бином, 2003.

  3. Лупин С.А., Посыпкин М.А. Технологии параллельного программирования. – М.: ИД "Форум" Инфра-М, 2008.

  4. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI: учебное пособие. – Минск: БГУ, 2002.

  5. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. – М.: Физматлит, 2007.

  6. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. – М.: Мир, 1991.

  7. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing. – The Benjamin/Cummings Publishing Company, 2003.

  8. Информационно-аналитические материалы по параллельным вычислениям.

http://www.parallel.ru/

  1. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. – М.: МГУ, 2002.

http://parallel.ru/tech/tech_dev/MPI/mpibook.pdf

  1. Антонов А.С. Параллельное программирование с использованием технологии OpenMP: учебное пособие. – М.: МГУ, 2009.

http://parallel.ru/info/parallel/openmp/

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





  1. Сигал И.Х., Иванова А.П. Методы оптимизации. Начальный курс. Часть 1-2. Курс лекций. – М.: МИИТ, 2006.

  2. Посыпкин М.А., Сигал И.Х, Галимьянова Н.Н. Параллельные алгоритмы в задачах дискретной оптимизации: вычислительные модели, библиотека, результаты экспериментов. – М.: ВЦ РАН, 2006.

  3. Group W., Lusk E., Skjellum A. Using MPI. Portable Parallel Programming with the Message-Passing Interface. – MIT Press, 1994.

  4. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. – MPI: The Complete Reference. MIT Press, Boston, 1996.

  5. Chandra R., Dagum L., Kohr D., Maydan D., McDonald J., Melon R. Parallel Programming in OpenMP. – Morgan Kaufmann Publishers, 2000.

  6. Foster I. Designing and Building Parallel Programs.

http://www.mcs.anl.gov/~itf/dbpp/

  1. Документация по MPI.

http://www.mpi-forum.org/

  1. Документация по OpenMP.

http://www.openmp.org

  1. Измерение производительности MPI.

http://www.mcs.anl.gov/research/projects/mpi/mpptest/

Подписано в печать 27.01.11. Формат 60 ´ 84. Бумага офсетная.

Печать офсетная. Усл. печ. л. 0,5. Уч.-изд. л. 0,4.

Тираж 100 экз. Заказ №


Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт (государственный университет)

Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ»



141700, Моск. обл., г. Долгопрудный, Институтский пер., 9.