Правительство Российской Федерации
Санкт-Петербургский государственный университет
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ |
Технология синхронного распараллеливания в многопоточных системах Technology of Synchronous Concurrency on multithreaded systems Язык(и) обучения___________русский___________________________________ |
Трудоёмкость_3_зачётных единицы
Регистрационный номер рабочей программы________________
Санкт-Петербург
2014
Раздел 1. Характеристики, структура и содержание учебных занятий.
1.1. Цели и результаты учебных занятий.
Cформировать у слушателей общее представление о содержании, задачах и методах современного синхронного распараллеливания на многопоточных системах как самостоятельной научной и инженерной дисциплины, о диапазоне и разнообразии его типичных задач и приложений.
Обеспечить формирование принципов операционного, аналитического и алгоритмического принципов мышления и соответствующих навыков для работы в области параллельных вычислений, необходимых для решения различных научных и практических задач, включая этапы постановки, моделирования, решения и анализа задачи, отбора необходимых технических средств, а также формирование соответствующих компетенций, в том числе навыков работы в коллективе. Изложить основы технологий распараллеливания и методик синхронизации работы вычислительных систем. Дать основу для дальнейшей самостоятельной работы в этой области.
Поставленные цели достигаются путём решения следующих задач курса: изучение общих структур и подходов в предметных областях основных разделов параллельного программирования на многопоточных системах, ознакомление с основными задачами синхронизации и технологией их решения различными средствами многопоточных систем на примерах математических моделей и их приложений; развитие навыков самостоятельного решения практических задач.
1.2. Требования к подготовленности обучающегося к освоению содержания учебных занятий (пререквизиты).
Успешное освоение курсов «программирование», «структуры и алгоритмы компьютерной обработки данных», «архитектура ЭВМ» или аналогичных по содержанию в объеме первых двух курсов математических факультетов университетов.
1.3. Перечень результатов обучения (learning outcomes)
В процессе изучения дисциплины “Технология синхронного распараллеливания в многопоточных системах” обучаемые приобретают следующие
знания | · проблем современной информатики, ее связи с другими научными дисциплинами; · корректных постановок классических задач синхронизации и распараллеливания; · примитивов синхронизации, их свойств и способов использования; · способов оценивания эффективности параллельных программ; |
умения | · грамотно пользоваться языком предметной области; · выявлять возможности в распараллеливании; · находить точки синхронизации; · подбирать необходимые средства реализации параллельных вычислений; · делать анализ и грамотную оценку эффективности разрабатываемых алгоритмов. |
навыки | · разработки и освоения методов распараллеливания вычислений способами и средствами организации параллельных потоков на вычислительных системах с общей памятью; · работы с компьютером как средством управления информацией; · выявления и объяснения возникновения накладных расходов в параллельных программах. |
Знать содержание дисциплины "Технология синхронного распараллеливания в многопоточных системах", в частности, иметь базовые представления о средствах синхронизации, способах их использования на вычислительных машинах с общей памятью. Иметь представление о методах распараллеливания научных вычислений.
Уметь применять полученные знания на практике, формализовывать поставленные задачи и находить эффективные способы их реализации на многопоточных системах.
1.4 Перечень и объём активных и интерактивных форм учебных занятий:
В качестве основных форм занятий (общее количество 30 часов) предполагается чтение лекций.
Также предполагается, что самостоятельную работу (всего 15 часов) в предлагаемом курсе студенты выполняют с обязательным использованием компьютера.
Раздел 2. Организация, структура и содержание учебных занятий
Трудоёмкость, объёмы учебной работы и наполняемость групп обучающихся | ||||||||||||||||||
Период обучения (модуль) | Контактная работа обучающегося с преподавателем | Самостоятельная работа | Объём активных и интерактивных форм учебных занятий | Трудоёмкость | ||||||||||||||
лекции | семинары | консультации | практические занятия | коллоквиумы | текущий контроль | итоговая аттестация | под руководством преподавателя | в присутствии преподавателя | сам. раб. с использованием методических материалов | текущий контроль (сам. раб.) | промежуточная аттестация (сам. раб.) | итоговая аттестация (сам. раб.) | ||||||
ОСНОВНАЯ ТРАЕКТОРИЯ | ||||||||||||||||||
очная форма обучения | ||||||||||||||||||
Семестр 7 | 30 | 15 | 10 | 3 |
2.1.1. Основной курс.
Формы текущего контроля успеваемости, виды промежуточной и итоговой аттестации | |||
Период обучения (модуль) | Формы текущего контроля успеваемости | Виды промежуточной аттестации | Виды итоговой аттестации (только для программ итоговой аттестации и дополнительных образовательных программ) |
ОСНОВНАЯ ТРАЕКТОРИЯ | |||
очная форма обучения | |||
Семестр 7 | экзамен | ||
2.2. Структура и содержание учебных занятий Базовый курс Основная траектория Очная форма обучения Период обучения: Семестр 7 |
| ||
№ п. п. | Наименование темы (раздела, части) | Вид учебных занятий | Кол-во часов |
1 | Тема 1. Обзор параллельных вычислений, синхронизации процессов | лекции | 6 |
по методическим материалам | 1 | ||
2 | Тема 2. Блокировки и барьеры | лекции | 6 |
по методическим материалам | 4 | ||
3 | Тема 3. Семафоры | лекции | 8 |
по методическим материалам | 4 | ||
4 | Тема 4. Мониторы | лекции | 8 |
по методическим материалам | 4 | ||
5 | Тема 5. Научные вычисления | лекции | 2 |
по методическим материалам | 2 | ||
Тема 1. Обзор параллельных вычислений, синхронизации процессов
Структуры аппаратного обеспечения. Приложения и стили программирования. Примера параллелилизма: итеративный и рекурсивный. Обзор программной нотации. Структуры аппаратного обеспечения. Приложения и стили программирования. Примера параллелилизма: итеративный и рекурсивный. Обзор программной нотации.
Тема 2. Блокировки и барьеры
Задача критической секции. Решение с помощью активных блокировок. Решению со справедливой стратегией – алгоритм разрыва узла, алгоритм билета, алгоритм поликлиники. Барьерная синхронизация – разделяемый счетчик, флаги и управляющие процессы, симметричные барьеры. Алгоритмы, параллельные по данным – параллельные префиксные вычисления, сеточные вычисления, синхронные мультипроцессоры. Параллельные вычисления с портфелем задач – умножение матриц, адаптивная квадратура.
Тема 3. Семафоры
Синтаксис и семантика. Основные задачи и методы – критические секции, барьеры, производители и потребители, кольцевые буферы. Задача об обедающих философах. Задача о читателях и писателях – как задача исключения, использование условной синхронизации. Метод передачи эстафеты. Распределение ресурсов и планирование – постановка задачи, общая схема решения, распределение по схеме «кратчайшее задание».
Тема 4. Мониторы
Синтаксис и семантика – взаимное исключение, условные переменные, дисциплины сигнализации, дополнительные операции с условными переменными. Методы синхронизации – кольцевые буферы, читатели и писатели, распределение ресурсов. Планирование работы диска – использование отдельного монитора, использование посредника, использование вложенного монитора.
Тема 5. Научные вычисления
Понятие об эффективности и оптимальности параллельной программы. Виды и влияние накладных расходов. Сеточные вычисления. Уравнения Лапласа. Метод последовательных итераций Якоби, с разделяемыми переменными, с передачей сообщений. Многосеточные методы. Точечные вычисления. Матричные вычисления.
Лабораторный практикум
Учебным планом не предусмотрен.
Раздел 3. Обеспечение учебной дисциплины
3.1. Методическое обеспечение
3.1.1. Методические указания по освоению дисциплины
Успешное освоение дисциплины возможно благодаря посещению лекций, самостоятельной работе, включающей в себя чтение специальной литературы по разделам темы.
3.1.2. Методическое обеспечение самостоятельной работы:
Самостоятельная работа студентов в рамках данной дисциплины необходима и предполагает изучение методических материалов.
3.1.3. Методика проведения текущего контроля успеваемости и промежуточной аттестации и критерии оценивания:
Общая аттестация складывается из следующих компонентов:
· Итоги выполнения проверочных работ (по каждой из тем).
· Результаты экзамена.
3.1.4. Методические материалы для проведения текущего контроля успеваемости и промежуточной аттестации (контрольно-измерительные материалы):
Примерный краткий перечень вопросов к экзамену.
1. Программа и ее история. Поиск образца в файле: распараллеливание. Поиск максимального значения в массиве: синхронизация.
2. Синхронизация типа «производитель-потребитель» (задача копирования массива).
3. Логика программирования: последовательные операторы, параллельные операторы.
4. Устранение взаимного вмешательства.
5. Доказательство свойств безопасности. Стратегии планирования и справедливость.
6. Задача критической секции. Активные блокировки (протоколы «проверить-установить», «проверить-проверить-установить»). Реализация операторов await.
7. Алгоритм разрыва узла. Алгоритм билета. Алгоритм поликлиники.
8. Барьерная синхронизация.
9. Распараллеливание префиксных вычислений.
10. Сеточные вычисления: итерации Якоби.
11. Параллельные вычисления с портфелем задач.
12. Семафоры: основные определения. Задача критической секции, барьеры.
13. Разделенные двоичные семафоры. Кольцевые буферы.
14. Задача об обедающих философах.
15. Задача о читателях и писателях как задача исключения.
16. Решение задачи о читателях и писателях с использованием условной синхронизации.
17. Метод передачи эстафеты.
18. Распределение ресурсов и планирование (постановка задачи и общая схема решения). Распределение ресурсов по схеме «кратчайшее задание».
19. Мониторы: синтаксис и семантика; взаимное исключение. Условные переменные; порядок сигнализации.
20. Кольцевые буферы; читатели и писатели; «кратчайшее задание». Задача о спящем парикмахере.
21. Планирование работы диска: использование отдельного монитора.
22. Планирование работы диска: использование посредника; вложенные мониторы.
23. Характеристики параллельной программы (ускорение, эффективность, накладные расходы).
24. Метод итераций Якоби: последовательная программа, программа с разделяемыми переменными.
25.Многосеточные методы.
3.1.5. Методические материалы для оценки обучающимися содержания и качества учебного процесса.
Для оценки содержания и качества учебного процесса может применяться анкетирование или опрос в соответствии с методикой и графиком, утверждаемым в установленном порядке.
3.2. Кадровое обеспечение
3.2.1. Образование и (или) квалификация штатных преподавателей и иных лиц, допущенных к проведению учебных занятий:
К чтению лекций привлекаются преподаватели, имеющие базовое образование и/или ученую степень соответствующую профилю преподаваемой дисциплины.
3.2.2. Обеспечение учебно-вспомогательным и (или) иным персоналом не требуется.
3.3. Материально-техническое обеспечение
3.3.1. Характеристика аудиторий (помещений, мест) для проведения занятий:
Стандартно оборудованные лекционные аудитории, в том числе и для проведения интерактивных лекций: доска, видеопроектор, экран, др. оборудование.
3.3.2. Характеристика аудиторного оборудования, в том числе неспециализированного компьютерного оборудования и программного обеспечения общего пользования: для самостоятельной работы студентов требуются компьютеры.
3.3.3. Характеристика специализированного оборудования: Нет.
3.3.4. Характеристика специализированного программного обеспечения: При использовании электронных документов каждый обучающийся во время занятий и самостоятельной подготовки должен быть обеспечен рабочим местом в компьютерном классе с выходом в Интернет и корпоративную сеть факультета.
3.3.5. Перечень и объёмы требуемых расходных материалов:
Мел, фломастеры цветные, губки в объеме, необходимом для организации и проведения занятий по заявкам преподавателей, подаваемым в установленные сроки, доступ преподавателя и студентов в компьютерные классы.
3.4. Информационное обеспечение
3.4.1. Список обязательной литературы:
1. , , Параллельные алгоритмы. Разработка и реализация. Учебное пособие. М., Национальный открытый университет Интуит-Бином. Лаборатория знаний. 2012, 343с.
2. Э. Таненбаум "Современные операционные системы", СПб.: Питер, 2010, 1120 с.
3.4.2. Список дополнительной литературы
1. , Воеводин Вл. В. Параллельные вычисления. СПб, 2004, 608 с.
2. Операционные системы. Параллельные и распределенные системы. СПб, 2004, 800 с.
3.4.3. Перечень иных информационных источников
Параллельное и распределенное программирование на С++. М.: Издательский дом «Вильямс», 2004, 672 с. Ресурсы сети Интернет.Разработчик рабочей программы: доцент мат-мех факультета СПбГУ t. *****@***ru
