Введение в анализ производительности и оптимизацию программ
Курс по оптимизации программ рассчитан на студентов 3 курса бакалавриата естественно-научного профиля. В курсе дается краткий обзор системных основ высокопроизводительных вычислений (механизмы, влияющие на производительность программ), изучаются основные релевантные метрики и ключевые подходы, связанные с оптимизацией программ на разных уровнях (алгоритмическая оптимизация, оптимизация структур данных, компиляторная оптимизация). Обсуждается использование специализированного инструментария (Amplifier, Advisor). Приводятся примеры пошаговой оптимизации конкретных программ.
Курс ориентирован на начальный уровень владения материалом, на достаточно массовую подготовку студентов, прослушавших лишь базовые курсы по программированию на С и С++, алгоритмам и структурам данных, архитектурам ЭВМ. Предполагается, что курс читается параллельно с курсом по параллельному программированию в системах с общей памятью. Курс не является проблемно-ориентированным и не сфокусирован на конкретные области приложений (компьютерное зрение, компьютерная графика, искусственный интеллект, научные и инженерные расчеты…).
Объем курса – 32 часа – соответствует типовому университетскому курсу по выбору (16 учебных недель, 1 пара в неделю). В этот регламент, к сожалению, не помещаются проблемно-ориентированные дополнения, изучение соответствующих библиотек, обзорные лекции общего плана, а также продвинутые методы организации параллелизма. Курс формирует базовые знания и навыки в области анализа производительности и оптимизации программ и предоставляет возможность студентам самостоятельно углубиться в другие области.
Материалы курса включают программу курса, презентации лекций/практик/мастер-классов, коды программ. Курс открыто распространяется под лицензией Apache.
Авторы курса:
- Мееров Иосиф Борисович, к.т.н., доцент, зам. зав. каф. МОСТ
- Сысоев Александр Владимирович, к.т.н., доцент каф. МОСТ
- Линев Алексей Владимирович, зав. лаб. интернета вещей, каф. ПРИН
- Волокитин Валентин Дмитриевич, программист лаборатории СТиВВ, каф. МОСТ
- Козинов Евгений Александрович, к.т.н., преподаватель каф. МОСТ
- Панова Елена Анатольевна, инженер лаборатории СТиВВ, каф. МОСТ
Программа курса
Раздел I. Введение в предмет (3.5 лекции, 2 практики)
1.1. Анализ производительности и оптимизация программ: введение в предмет (суть, цели, задачи, основные принципы, критерии, примеры, структура курса). (лекция)
1.2. Архитектурные механизмы, влияющие на производительность. Уровни параллелизма. (лекция)
1.3. Основные метрики, методика их сбора и анализа. (лекция)
1.4. Практическое использование Intel C++ Compiler в среде разработки Microsoft Visual Studio. Компиляция и сборка из командной строки. (практика)
Раздел II. Оптимизация программ: алгоритмы и структуры данных (3 лекции,
2 практики)
2.1. Алгоритмическая оптимизация. Вычислительная сложность, практические аспекты (лекция)
2.2. Алгоритмическая оптимизация при реализации алгоритмов сортировки (лекция, практика)
2.3. Оптимизация структур данных при работе с разреженными матрицами (лекция, практика)
Раздел III. Программная оптимизация на примерах (1 лекция, 3 практики, 2 мастер-класса)
3.1. Векторизация циклов. Общие принципы и использование компилятора (лекция)
3.1.5. Инструменты для анализа производительности Intel VTune и Intel Advisor. Общее введение (мастер-класс)
3.2. Векторизация циклов. Использование транслятора Intel Compiler и помощника Intel Advisor (практика)
3.3. Рациональное использование иерархии памяти на примере задачи о транспонировании матриц. Использование профилировщика Intel VTune (практика)
3.4. Оптимизация вычислений, аспекты параллелизма, балансировка нагрузки. Задача о вычислении простых чисел (практика)
3.5. Пошаговая оптимизация программ в практических приложениях: вычисление формулы Блэка-Шоулса (векторизация, параллелизм, понижение точности, эквивалентные вычисления, NUMA…) (мастер-класс)
3.6. Пошаговая оптимизация программ в практических приложениях: численное интегрирование (векторизация, параллелизм, работа с памятью + MKL) (мастер-класс)