Утверждаю
| Вид материала | Рабочая программа |
- Утверждаю утверждаю, 21.26kb.
- «утверждаю» «утверждаю», 262.03kb.
- Утверждаю утверждаю, 393.06kb.
- «Утверждаю» «Утверждаю» Председатель Совета доу заведующий мдоу №25, 113.74kb.
- Кикбоксинг против наркомании и детской преступности «Утверждаю» «Утверждаю», 78.29kb.
- Утверждаю: утверждаю, 156.74kb.
- «утверждаю» «утверждаю» Председатель республиканского Директор маоудод «цдтт №5» совета, 42.86kb.
- Утверждаю» «Утверждаю», 163.81kb.
- «Динамо», 49.89kb.
- Утверждаю: утверждаю: Председатель Глава администрация оо «Гомельский рыболовный клуб», 78.23kb.
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего
профессионального образования «Чувашский государственный университет
имени И.Н.Ульянова»
УТВЕРЖДАЮ
Декан ФИВТ ______________ Б.М.Калмыков
"_____"__________________2011 г.
Рабочая программа дисциплины
Параллельное программирование
Направление подготовки
230100.62 «Информатика и вычислительная техника»
Профиль подготовки
Вычислительные машины, комплексы, системы и сети
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
г. Чебоксары
2011
1. Цели освоения дисциплины
Суперкомпьютерный технологии и высокопроизводительные вычисления с использованием многопроцессорных вычислительных систем (МВС) становятся важным фактором научно-технического прогресса; их применение принимает всеобщий характер.
Цель дисциплины состоит в изучении математических моделей, методов и технологий параллельного программирования для (МВС) в объеме, достаточном для успешного начала работ в области параллельного программирования. Излагаемый набор знаний и умений составляет теоретическую основу для методов разработки сложных программ и включают такие темы, как цели и задачи параллельной обработки данных, принципы построения параллельных вычислительных систем, моделирование и анализ параллельных вычислений, принципы разработки параллельных алгоритмов и программ, технологии и системы разработки параллельных программ, параллельные численные алгоритмы для решения типовых задач вычислительной математики. Изучение курса поддерживается расширенным лабораторным практикумом.
Основной задачей изучения дисциплины является формирование у студентов теоретических знаний и практических навыков разработки алгоритмов и программ и их реализации на (МВС) (суперкомпьютерах).
Изложение дисциплины опирается на основные дисциплины: Вычислительная математика, Архитектура вычислительных систем, Вычислительные системы и сети, Программное обеспечение сетей ЭВМ.
Знания, полученные студентами в данной дисциплине, будут использоваться при подготовке выпускных квалификационных работ.
2. Место дисциплины в структуре ООП по направлению подготовки 230100.62 «Информатика и вычислительная техника».
Профессиональный цикл. Базовая часть.
Операционные системы. При изучении дисциплины "Параллельное программирование" используется материал дисциплин: "Информатика", "Программирование". Дисциплина "Параллельное программирование" является одной из основных для дисциплин «Технологии программирования», «Структуры и алгоритмы компьютерной обработки данных».
3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Параллельное программирование»:
Выпускник должен обладать следующими профессиональными компетенциями:
– стремиться к саморазвитию, повышению своей квалификации и мастерства (ОК-6);
– иметь навыки работы с компьютером как средством управления информацией (ОК-12);
– участвовать в настройке и наладке программно-аппаратных комплексов (ПК-9);
– инсталлировать программное и аппаратное обеспечение для информационных и автоматизированных систем (ПК-11).
В результате изучения базовой части циклов студент должен:
Знать:
• Методы параллельных вычислений для задач вычислительной математики (матричные вычисления, решение систем линейных уравнений, сортировка, обработка графов, уравнения в частных производных, многоэкстремальная оптимизация).
• Основные подходы к разработке параллельных программ.
Уметь:
• Строить модель выполнения параллельных программ.
• Оценивать эффективности параллельных вычислений.
• Анализировать сложность вычислений и возможность распараллеливания разрабатываемых алгоритмов.
• Применять общие схемы разработки параллельных программ для реализаций собственных алгоритмов.
• Оценивать основные параметры получаемых параллельных программ, таких как ускорение, эффективность и масштабируемость.
Владеть:
- основами разработки параллельных программ для МВС с применением технологий MPI, OpenMP, CUDA.
4. Структура и содержание дисциплины «Операционные системы»
Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часов, 64 часов аудиторная нагрузка, 34 часа – самостоятельная работа.
| Вид учебной работы | Всего часов |
| Общая трудоемкость дисциплины | 144/4 ЗЕТ |
| Аудиторные занятия | 64 |
| - лекции | 32 |
| - практические занятия | |
| - лабораторные работы | 32 |
| - другие виды аудиторных занятий | |
| Самостоятельная работа | 34 |
| Курсовой проект (работа) | |
| Контроль самостоятельной работы | 10 |
| Аттестация | 36 Экзамен (7 семестр) |
4.1. Разделы дисциплины и виды занятий
| № п/п | Раздел Дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||
| лек | лаб | пр | СРС | КСР | |||||
| | Состояние и проблемы параллельных вычислений | 7 | 1-2 | 4 | 4 | | 4 | 1 | Собеседование, Л/Р, индивидуальное домашнее задание. |
| | Моделирование и анализ параллельных алгоритмов | 7 | 3-4 | 4 | 4 | 4 | 1 | Собеседование, Л/Р, тестирование. | |
| | Этапы разработки параллельных алгоритмов | 7 | 5-6 | 4 | 4 | 4 | 1 | Собеседование, Л/Р, устный опрос. | |
| | Средства разработки параллельных программ | 7 | 7-8 | 4 | 4 | 4 | 1 | Собеседование, Л/Р, устный опрос. | |
| | Интерфейс передачи сообщений - MPI | 7 | 9-10 | 4 | 4 | 4 | 1 | Собеседование, Л/Р, индивидуальное домашнее задание | |
| | Технология программирования OpenMP | 7 | 11-12 | 4 | 4 | 4 | 1 | Собеседование, Л/Р, индивидуальное домашнее задание. | |
| | Программирование МВС с графическими процессорами | 7 | 13-14 | 4 | 4 | 4 | 2 | Собеседование, Л/Р, тестирование. | |
| | Типовые параллельные алгоритмы | 7 | 15-18 | 4 | 4 | 6 | 2 | Собеседование, Л/Р, устный опрос. | |
| ИТОГО | 32 | 32 | | 34 | 10 | | |||
Раздел 1. Состояние и проблемы параллельных вычислений
Современное состояние суперкомпьютерной вычислительной техники. Списки ТОР500 и ТОР50. Российские достижения. Перспективы развития суперкомпьютерной техники и параллельных вычислений. Использование мировых сетевых ресурсов для параллельных вычислений.
Раздел 2. Моделирование и анализ параллельных алгоритмов
Концепция неограниченного параллелизма. Графовые модели параллельных алгоритмов в виде «операнды-операции». Ярусно-параллельная форма графа алгоритма, высота, ширина алгоритма. Описание параллельного выполнения алгоритма, расписание. Асимптотические оценки времени выполнения. Каскадные вычисления, их реализация на векторных процессорах. Оценки эффективности параллельных алгоритмов: ускорение и эффективность. Закон Амдала. Влияние времени передачи данных на эффективность алгоритма.
Раздел 3. Этапы разработки параллельных алгоритмов
Две модели программирования: последовательная и параллельная. Параллелизм данных и параллелизм задач. Схемы вычислительного процесса для параллельных программ: SPMD, Хозяин/Работник. Основные этапы разработки параллельного алгоритма: декомпозиция, проектирование обменов между задачами, укрупнение, планирование вычислений.
Раздел 4. Средства разработки параллельных программ
Использование распространенных языков программирования и коммуникационных библиотек и интерфейсов. Традиционные последовательные языки и распараллеливающие компиляторы, проблема выделения потенциального параллелизма последовательных программ. Специальные комментарии и директивы компилятору.
Параллельные языки программирования и расширения стандартных языков. Средства автоматического распараллеливания, параллельные компиляторы. Параллельные предметные библиотеки. Инструментальные системы для проектирования параллельных программ.
Раздел 5. Интерфейс передачи сообщений - MPI
Общие принципы построения и реализации MPI. Разработчики, история создания. Шесть общих функций MPI, коммуникаторы. Функции обмена сообщениями типа «точка-точка»: блокирующий и неблокирующий обмен, синхронные и стандартные посылки сообщений.
Коллективные функции обмена данных: широковещательная рассылка, функции сбора и рассыпания данных. Функции редукции данных.
Создание групп процессов, области связи, коммуникаторы. Обмен данными внутри группы, межгрупповой обмен. Топология обменов. Декартовы топологии.
Примеры параллельных программ на основе обработки массивов.
Раздел 6. Технология программирования OpenMP.
Последовательные и параллельные нити программы. Директивы OpenMP, функции времени выполнения, переменные окружения. Классы переменных. Организация параллельных секций. Параллельные циклы. Директивы взаимоисключения и синхронизации.
Применение функций и переменных окружения для выполнения параллельных программ.
Раздел 7. Программирование МВС с графическими процессорами
Применение графических процессоров в параллельном программировании. Модель потоковых вычислений, CUDA. Расширения языка С. Работа с памятью. Примера программ матричных вычислений.
Раздел 8. Типовые параллельные алгоритмы
Умножение матриц: линейное, блочное разбиение матриц. Алгоритмы Фокса и Кеннона. Решение систем линейных уравнений. Алгоритмы параллельной сортировки.
5. Образовательные технологии
- По курсу «Параллельное программирование» ряду студентов выдаются индивидуальные задания на лабораторные работы, связанные с изучением организации хранения данных во внешней памяти для операционных систем Windows и Linux.
- В дополнение к лабораторным работам каждый студент получает индивидуальное задание по написанию реферата на заданную тему. Список тем охватывает развитие аппаратных и программных средств ПК, операционных систем, компьютерных сетей.
- Читаются проблемные лекции, посвященные новым технологиям создания многопользовательских многозадачных операционных систем.
- Для рейтингового контроля успеваемости используется программа электронного тестирования.
6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов
6.1. Лабораторные занятия
Лабораторная работа №1. Численное интегрирование с использованием функций MPI.
Лабораторная работа №2. Параллельные программы в среде OpenMP.
Лабораторная работа №3. Агрегирование данных для операций передачи.
Лабораторная работа №4. Параллельные алгоритмы на массивах.
6.2. Индивидуальные занятия
Индивидуальные занятия по курсу проводятся в индивидуальном порядке в соответствии с целями и задачами дисциплины.
6.3. Контрольные задания и вопросы для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины, а также для контроля самостоятельной работы обучающегося по отдельным разделам дисциплины
6.3.1. Аннотация к тестовым заданиям
Тестовые задания по учебной дисциплине «Параллельное программирование» содержат 30 вопросов по теоретическим и практическим разделам курса и включают в себя вопросы следующих типов: выбор правильного ответа, установление правильной последовательности, сопоставление значений, ввод правильного ответа.
Задания структурированы по следующим разделам: назначение и основные функции операционных систем, процессы в мультипрограммной среде, дисциплины планирования процессов, стратегии распределения памяти, прерывания и организация подсистемы ввода/ вывода.
6.3.2. Элементы содержания курса «Параллельное программирование», включенные в тест
1. Вычислительные процессы. Формальная модель. Свойства процесса.
2. Система процессов. Независимые процессы. Взаимодействие процессов.
3. Классы параллельных ВС
4. Отображение системы процессов. Синхронизация
5. Показатели параллельных ВС и вычислений
6. MPI: Стандарт MPI. Общие понятия. Области связи и коммуникаторы.
7. Общие процедуры MPI: Инициализация, Завершение.
8. Общие процедуры MPI: Определение общего числа параллельных процессов в группе. Определение номера процесса в группе.
9. MPI: Прием/передача сообщений между отдельными процессами.
10. MPI: Групповые (коллективные) взаимодействия. Рассылка целого сообщения процессам. Сборка данных от процессов.
11. MPI: Групповые (коллективные) взаимодействия: Рассылка частей сообщения процессам. Сборка частей сообщения с процессов.
12. MPI: Функции поддержки распределенных операций: Выполнение глобальных операций с возвратом результатов в главный процесс. Выполнение глобальных операций с возвратом результатов во все процессы.
13. MPI: Синхронизация процессов.
14. Процессы и потоки в POSIX
15. OpenMP: Общие понятия. Область применения.
16. Директивы OpenMP: Директивы для определения параллельной области.
17. OpenMP: Директивы для распределения вычислений внутри параллельной области: Директива for.
18. OpenMP: Директивы для распределения вычислений внутри параллельной области: Директива sections. Директива single.
19. OpenMP: Директивы для распределения вычислений внутри параллельной области: Объединение директив parallel и for (sections).
20. Проблема тупиков. Виды тупиков. Методы борьбы с тупиками в параллельных программных системах.
21. Централизованный метод обнаружения тупиков в параллельных программных системах
22. Децентрализованный метод обнаружения тупиков в параллельных программных системах
23. Предотвращение тупиков в параллельных программных системах
24. Синхронизация логического времени в параллельных программных системах
25. Синхронизация физического времени в параллельных программных системах
26. Распределение процессов по процессорам. Критерии и подходы.
27. Распределение процессов по процессорам. Централизованный метод “Up-Down”
28. Распределение процессов по процессорам. Иерархический алгоритм.
29. Распределение процессов по процессорам. Стохастические алгоритмы.
30. Модель мультипотоковых вычислений Блумова-Лейзерсона.
6.3.3. Перечень объектов контроля (виды знаний, умений, контролируемых заданиями теста)
| 1 | Определение основных функций операционной системы. |
| 2 | Анализ требований, предъявляемых к дисциплинам планирования процессов. |
| 3 | Анализ условий перехода процесса из одного состояния в другое. |
| 4 | Оценка стратегий распределения памяти, выявление преимуществ и недостатков. |
| 5 | Технология организации обмена данными с внешними устройствами. |
| 6 | Инсталляция, настройка и обслуживание системного и прикладного программного обеспечения. |
7. Учебно-методическое и информационное обеспечение дисциплины
а) Основная литература
1 Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем: Учебник – М.: Изд-во МГУ, 2010 (25 экз)
2 Линев А.В., Боголепов Д.К., Бастраков С.И. Технологии параллельного программирования для процессоров новых архитектур: Учебник – Учебник – М.: Изд-во МГУ, 2010 (25 экз)
3 Старченко А.В., Данилкин Е.А., и др. Практикум по методам параллельных вычислений: Учебник. – М.: Изд-во МГУ, 2010 (25 экз)
4 Воеводин В.В. Вычислительная математика и структура алгоритмов: Учебник. – М.: Изд-во МГУ, 2010 (25 экз)
б) Дополнительная литература
1 Гергель В.П. Теория и практика параллельных вычислений. – [Интернет-ресурс] URL: ссылка скрыта.
2 Гергель В.П. Введение в методы параллельного программирования – [Электронный ресурс]: [сайт].URL:ссылка скрыта.
3 Антонов А.С. Параллельное программирование с использованием технологииOpenMP: Учебн. пособие. – М.: Изд-во МГУ, 2007.[Электронный ресурс]:[сайт].URL: ru/info/parallel/openmp.
4 Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебн. Пособие. – М.: Изд-во МГУ, 2003 [Электронный ресурс]: [сайт]. URL:ru/info/parallel/antonov
5 Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.:БХВ-Петербург, 2002 (20 экз)
6 Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование, алгоритмы. – М.: Радио и связь, 1986.
Большинство учебных материалов по параллельным вычислениям размещены в интернете. Рекомендуется использовать сайты:
ссылка скрыта – НИИВЦ МГУ
ссылка скрыта – Интернет-центр системы образовательных ресурсов в области СКТТ
ссылка скрыта – Интернет университет информационных технологий
ссылка скрыта – Центр суперкомпьютерных технологий Нижегородского государственного университета
в) Учебно-методические руководства
1 Фефелов Н.П. Операционные системы. Руководства по лабораторным работам. – [Электронный ресурс] – Сетевой диск R кафедры АСУ.
2 Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI. – Минск:БГУ, 2002. – Сетевой диск R кафедры АСУ.
3 Букатов А.А., Дацюк В.Н., Жегуло А.И. Многопроцессорные системы и параллельное программирование. – Ростов-на-Дону: РГУ, 2000. – Сетевой диск R кафедры АСУ.
4 Немнюгин С.А. Средства программирования для многопроцессорных вычислительных систем. – СПб: СПбГУ, 2007 – Сетевой диск R кафедры АСУ.
8. Материально-техническое обеспечение дисциплины
Для проведения занятий по курсу «Параллельное программирование» используется лаборатория З-105 кафедры МиАОИС, задействуются 10 персональных компьютеров.
Компьютерные программы .NET FrameWork, Visual Studio.
Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки 230100.62 «Информатика и вычислительная техника» профиль подготовки «Автоматизированные информационно-управляющие системы и комплексы».
Автор ___________________________ Артемьев Э.И.
Зав. кафедрой ____________________ Артемьев И.Т.