страница 1
|
|||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные - страница №1/1
министерство образования и науки российской федерации Московский физико-технический институт (государственный университет) УТВЕРЖДАЮ Проректор по учебной работе Ю.А. Самарский П Р О Г Р А М М Апо курсу ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ по направлению 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. Смежные вопросы методов оптимизации и их распараллеливание. Метод Ньютона. Симплекс-метод. Многокритериальная оптимизация. Литература
http://www.parallel.ru/
http://parallel.ru/tech/tech_dev/MPI/mpibook.pdf
http://parallel.ru/info/parallel/openmp/ Дополнительная литература
http://www.mcs.anl.gov/~itf/dbpp/
http://www.mpi-forum.org/
http://www.openmp.org
http://www.mcs.anl.gov/research/projects/mpi/mpptest/ Подписано в печать 27.01.11. Формат 60 ´ 84. Бумага офсетная. Печать офсетная. Усл. печ. л. 0,5. Уч.-изд. л. 0,4. Тираж 100 экз. Заказ № Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ» 141700, Моск. обл., г. Долгопрудный, Институтский пер., 9. |
|