Полный Свод знаний и умений
1. Математические основы параллельных вычислений
1.1. Графовые модели программ
1.1.1. Операционное и информационное отношение
1.1.2. Компактные модели и истории
1.1.3. Граф управления, информационный граф, операционная история, информационная история
1.1.4. Свойства информационной зависимости и информационной независимости
1.1.5. Ярусно-параллельная форма, критический путь графа
1.1.6. Ациклические графы и топологическая сортировка
1.1.7. Граф вычислений
1.1.8. Граф вызовов функций
1.1.9. def-use цепочки
1.1.10. граф зависимостей по данным
1.1.11. граф информационных связей
1.1.12. граф несовместимости переменных
1.1.13. Решетчатые графы (граф алгоритма)
1.2. Концепция неограниченного параллелизма
1.3. Тонкая информационная структура программ
1.3.1. Теория построения графа алгоритма
1.3.2. Параллельная структура программ
1.3.3. Виды параллелизма: конечный, массовый, координатный, скошенный
1.3.4. Избыточные вычисления
1.4. Эквивалентные преобразования программ
1.4.1. Теория эквивалентных преобразований программ
1.4.2. Элементарные преобразования циклов
1.4.3. Неэквивалентные преобразования программ
1.5. Модели вычислений для компьютерных систем
1.5.1. Модели вычислений для систем с общей памятью: PRAM, QSM, DSM, NUMA.
1.5.2. Модели вычислений для систем с распределенной памятью: BSP, LogP.
1.5.3. Оценка коммуникационной трудоемкости: модель Хокни.
1.6. Математические модели параллельных вычислений
1.6.1. Модель взаимодействия последовательных процессов (CSP).
1.6.2. Сети Петри для моделирования параллельных вычислений.
1.6.3. Модель параллельных программ в виде системы «процесс-ресурс».
1.7. Математические модели систолических массивов
2. Параллельные вычислительные системы (компьютерные основы)
2.1. Основы машинных вычислений
2.1.1. Представление чисел в компьютере, операции, округление и точность представления чисел
2.2. Основы построения компьютерных систем
2.2.1. Процессоры.
- Скалярные, векторные и конвейерные функциональные устройства.
- Характеристики работы вычислительных устройств: загруженность, эффективность, производительность
- Дополнительные виды процессоров: ускорители вычислений, графические процессоры, процессоры с программируемой логикой (FPGA), спецпроцессоры.
2.2.2. Память.
- Кэш, основная память, общая память с неоднородным доступом, распределенная память. Модели согласованности (consistency) доступа к памяти.
- Характеристики доступа к памяти: цикл доступа, пропускная способность канала доступа к памяти, интенсивность промахов доступа к кэш памяти.
2.2.3. Сеть передачи данных.
- Топология межпроцессорной передачи данных, типовые схемы.
- Характеристики эффективности сетей: латентность, пропускная способность, длина максимального пути, связность.
- Схемы коммутации, коммуникационные технологии, их основные характеристики.
2.3. Параллельные вычислительные системы
2.3.1. Разрядно-параллельная обработка, независимый ввод/вывод, опережающий просмотр вперед, расслоение памяти, SSE/Altivec инструкции….
2.3.2. Параллелизм на уровне машинных команд (суперскалярность, VLIW, EPIC).
2.3.3. Развитие архитектуры процессоров для поддержки параллелизма: гипер- и мульти- трейдинг, многоядерность.
2.4. Многопроцессорные вычислительные системы
2.4.1. Классическая схема фон Неймана. Классификация Флинна. Детализация класса MIMD.
2.4.2. Общие принципы организации компьютеров с общей и распределенной памятью, две задачи параллельных вычислений. Мульпроцессоры и мультикомпьютеры.
2.4.3. Другие архитектуры: неоднородные вычислительные системы, векторно-конвейерные системы, потоко-ориентированные (data-flow) системы.
2.4.4. Характеристики эффективности многопроцессорных систем: пиковая и реальная производительность, ускорение, масштабируемость.
2.4.5. Оценка производительности. Законы Амдала, Густавсона-Барсиса. Тесты производительности NAS Parallel Benchmark, HPC Challenge Benchmark Suite. Тест Linpack.
2.5. Многопроцессорные вычислительные системы с общей памятью
2.5.1. Системы с однородной общей памятью: архитектура SMP.
2.5.2. Системы с неоднородной общей памятью: NUMA, ccNUMA, DSM.
2.5.3. Примеры систем (SGI Altix, Hewlett-Packard Superdome,…).
2.5.4. Преимущества и недостатки архитектуры.
2.6. Многопроцессорные вычислительные системы с распределенной памятью
2.6.1. MPP-системы и вычислительные кластеры. Использование SMP систем в качестве вычислительных узлов.
2.6.2. Высокопроизводительные системы гибридной архитектуры.
2.6.3. Примеры систем (системы Cray T3х, XTx, IBM BlueGene /L /P /Q, RoadRunner, Tianhe, K, суперкомпьютер «Ломоносов»,…).
2.6.4. Преимущества и недостатки архитектуры.
2.7. Графические процессоры
2.7.1. Архитектура графических процессоров и причины её возникновения
2.7.2. Организация памяти на графических процессорах (глобальная, константная, разделяемая, текстурная, регистровая, локальная типы памяти)
2.7.3. Особенности программирования и оптимизации программ, использующих графические процессоры.
2.7.4. Преимущества и недостатки графических процессоров.
2.8. Вычислительные системы транспетафлопсной и экзафлопсной производительности
2.8.1. Понятие суперкомпьютера. Динамика повышения производительности суперкомпьютерных систем. Закон Мура. Примеры суперкомпьютерных систем.
2.8.2. Рейтинги систем рекордной производительности Тор500 и Тор50. Оценка закономерностей развития систем на основе данных рейтингов (динамика повышения производительности, используемые технологии, области приложений).
2.8.3. Возможные пути достижения экзафлопсной производительности. Международные инициативы.
2.8.4. Проблемы на пути создания систем экзафлопсной производительности: стена памяти, масштабируемость, энергопотребление.
2.9. Распределенные вычислительные системы
2.9.1. Метакомпьютинг, грид-технологии. Примеры грид-систем.
2.9.2. Облачные вычисления. Системы и технологии поддержки.
2.9.3. Универсальные и специализированные распределенные вычислительные среды, средства и системы.
2.10. Проблемы функционирования суперкомпьютерных центров и центров обработки данных
2.10.1. Операционные системы параллельных вычислительных систем. Системы управления заданиями, планирования распределения вычислительной нагрузки.
2.10.2. Администрирование суперкомпьютерных вычислительных систем. Системы мониторинга и поддержки надежности функционирования. Обеспечение технической и информационной безопасности.
2.10.3. Устройства параллельного ввода/вывода. Параллельные файловые системы.
2.10.4. Проблемно-ориентированное программное обеспечение: прикладные пакеты, библиотеки алгоритмов и программ, среды разработки, доступ к удаленным ресурсам и сервисам.
2.10.5. Системы научно-технической визуализации. Виртуальная реальность, системы трехмерной и стерео визуализации.
2.10.6. Инфраструктура поддержки работы пользователей суперкомпьютерных вычислительных систем.
3. Технологии параллельного программирования (основы программной инженерии)
3.1. Общие принципы разработки параллельных программ
3.1.1. Основные способы организации параллельных вычислений.
- Уровни организации параллелизма. Параллелизм на уровне команд. Распараллеливание циклов. Параллельное выполнение моделей и программ.
- Параллелизм по данным. Основные схемы распределения данных.
- Параллелизм задач. Распараллеливание функциональных языков.
- Централизованные схемы организации параллельных вычислений: клиент-сервер, мастер- рабочие.
- Создание параллельных процессов на основе одной и той же программы (схема SPMD, single program multiple data).
- Методы организации информационного взаимодействия: общие данные, передача сообщений, использование удаленных процедур, схема рандеву.
- Шаблоны параллельного программирования.
- Распараллеливание последовательных программ.
3.1.2. Эффективность, переносимость и продуктивность технологий параллельного программирования. Поиск компромисса.
3.2. Основы параллельного программирования
3.2.1. Основные понятия: процесс, поток, ресурс, взаимодействие процессов и потоков.
3.2.2. Поддержка параллельного выполнения на уровне современных операционных систем
3.2.3. Взаимодействие и взаимоисключение потоков: алгоритмы взаимоисключения, семафоры, мониторы, атомарные операции.
3.2.4. Синхронизация потоков: условные переменные, Барьерная синхронизация. Низкоуровневые примитивы синхронизации (atomic reads/writes, compare-exchange и т.д.)
3.2.5. Основные операции приемо-передачи данных. Коллективные операции. Процедуры редукции данных. Односторонний доступ к данным.
3.2.6. Свойства параллельных программ: детерминированность, безопасность, живучесть, справедливость.
3.2.7. Проблемы организации параллелизма: избыточная синхронизация, гонка потоков, взаимоблокировка, бесконечное откладывание.
3.2.8. Проблема блокировки. Модели параллельных программ для обнаружения и исключения потоков.
3.2.9. Классические задачи синхронизации: поставщик-потребитель, читатели-писатели, обедающие философы, спящий парикмахер.
3.3. Методы и технологии разработки параллельных программ
3.3.1. Традиционные языки программирования и распараллеливающие компиляторы. Векторизация программ.
3.3.2. Программные библиотеки для разработки параллельных программ: Shmem, Linda, MPI, PVM.
3.3.3. Надъязыковые средства для организации параллелизма: Cray Fortran, DVM, OpenMP, HPF.
3.3.4. Параллельные расширения традиционных языков программирования: CAF, UPC.
3.3.5. Параллельные языки программирования: Occam, SISAL, НОРМА.
3.3.6. Параллельные языки программирования для систем с распределенной общей памятью: Chapel, X10.
3.3.7. Параллельные языки программирования для графических процессоров: CUDA, OpenCL.
3.3.8. Средства и технологии для поддержки метакомпьютинга и распределенных вычислений: Globus, gLite, UNICORE, BOINC, X-Com, Map/Reduce…
3.3.9. Технологии программирования FPGA-компьютеров.
3.3.10. Автоматизация распараллеливания и оптимизации программ
3.3.11. Элементы схемотехники, Языки описания электронных схем, VHDL
3.4. Параллельные проблемно-ориентированные библиотеки и комплексы программ
3.4.1. Параллельные проблемно-ориентированные библиотеки: BLAS, Lapack, Scalapack, FFTW, PETSc, MKL, …
3.4.2. Параллельные прикладные пакеты и программные комплексы: GAUSSIAN, ANSYS, FlowVision, GAMESS, PRIRODA, Gromacs, CHARMM …
3.5. Параллельные и распределенные системы баз данных
3.5.1. Межтранзакционный и внутритранзакционный параллелизм. Межзапросный и внутризапросный параллелизм. Межоперационный и внутриоперационный параллелизм. Горизонтальный (кустовой) и вертикальный (конвейерный) параллелизм. Фрагментный параллелизм.
3.5.2. Определение параллельной системы баз данных. Требования к параллельной системе баз данных: масштабируемость (ускорение и расширяемость), производительность, доступность данных.
3.5.3. Архитектура параллельных систем баз данных. Одноуровневые архитектуры: архитектура с разделяемыми памятью и дисками, архитектура с разделяемыми дисками, архитектура без совместного использования ресурсов. Иерархические архитектуры. Гибридная архитектура.
3.5.4. Организация межпроцессорных обменов при выполнении запроса.
3.5.5. Методы распределения данных и балансировки загрузки при выполнении запросов.
3.6. Инструментальные среды для разработки параллельных программ
3.6.1. Среды разработки. Распараллеливающие компиляторы. Отладчики параллельных программ. Анализаторы эффективности.
3.6.2. Системы поддержки командной разработки. Средства контроля версий. Системы управления проектами.
3.7. Методы повышения эффективности параллельных программ
3.7.1. Оптимизация количества потоков. Повышение эффективности работы с памятью.
3.7.2. Методы балансировки вычислительной нагрузки. Минимизация информационного взаимодействия.
3.7.3. Использование потоко-ориентированных библиотек.
4. Параллельные алгоритмы решения задач
4.1. Общие принципы разработки параллельных алгоритмов
4.1.1. Этапы решения задач на параллельных вычислительных системах: задача-модель-метод-алгоритм-программа-вычислительный эксперимент.
4.1.2. Общая схема разработки параллельных алгоритмов: декомпозиция вычислений, анализ информационных зависимостей, масштабирование, распределение нагрузки (Фостер).
4.1.3. Показатели качества параллельных алгоритмов: ускорение, эффективность, масштабируемость. Возможность суперлинейного ускорения.
4.1.4. Обеспечение эффективности параллельных вычислений: балансировка вычислительной нагрузки, низкая эффективность информационного взаимодействия. Зависимость степени параллелизма программ от формы записи алгоритма и структур данных.
4.1.5. Основные базовые алгоритмы: алгоритмы полного перебора, «жадные» алгоритмы, перебор с возвратом, алгоритмы «разделяй и властвуй», метод ветвей и границ.
4.1.6. Основные методы декомпозиции данных: регулярные данные, разреженные структуры, неоднородные данные, графовые и сетевые структуры.
4.1.7. Оценка вычислительной сложности последовательных и параллельных алгоритмов.
4.2. Учебные алгоритмы параллельного программирования
4.2.1. Векторные операции: сумма элементов вектора, скалярной произведение.
4.2.2. Матричные вычисления: матрично-векторное умножение, умножение плотных матриц.
4.2.3. Базовые алгоритмы вычислительной математики: методы интегрирования, алгоритмы сортировки, методы обработки графов.
4.3. Параллельные алгоритмы матричных вычислений
4.3.1. Методы вычислений для плотных матриц: транспонирование, сложение и умножение матриц. Обработка симметричных матриц.
4.3.2. Методы вычислений для разреженных матриц. Хранение и обработка ленточных матриц.
4.3.3. Решение систем линейных алгебраических уравнений (СЛАУ): метод Гаусса, метод простой итерации, методы типа сопряженных градиентов с предобуславливанием (GMRES, BiCG, QMR). Пакеты Azteс и Linpack параллельного решения СЛАУ
4.3.4. Решение задач на собственное значение: метод QR-разложения, проекционные методы, метод вращения, степенной метод. Их параллельные реализации. Пакет Scalapack
4.4. Параллельные алгоритмы сортировки и поиска данных
4.4.1. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками).
4.4.2. Эффективные алгоритмы сортировки (быстрая сортировка, пирамидальная сортировка, сортировка слиянием).
4.4.3. Алгоритм бинарного поиска. Бинарные деревья поиска.
4.5. Параллельные алгоритмы обработки графов
4.5.1. Методы представления графов (списки смежности, матрица смежности).
4.5.2. Методы обхода графов в глубину и ширину.
4.5.3. Алгоритмы поиска кратчайшего пути (алгоритмы Дейкстры и Флойда).
4.5.4. Методы построение минимального остовного дерева (алгоритмы Прима и Крускала).
4.6. Параллельные алгоритмы решения дифференциальных уравнений в частных производных
4.6.1. Методы аппроксимации дифференциальных уравнений в частных производных – метод конечных разностей (МКР) и метод конечных элементов (МКЭ). Явные и неявные схемы.
4.6.2. Методы получения однородных и неоднородных сеток. Методы сгущения сеток и оценки их качества. Методы декомпозиции области. Многосеточные алгоритмы. Параллельная реализация алгоритмов построения сеток и конечных элементов.
4.6.3. Блочные методы декомпозиции данных. Четно-нечетная нумерация узлов области расчета Волновые схемы выполнения расчетов.
4.6.4. Исследование устойчивости и сходимости параллельных вычислительных алгоритмов.
4.7. Параллельные алгоритмы решения оптимизационных задач
4.7.1. Параллельные алгоритмы локальной оптимизации. Решение задачи о седловой точке.
4.7.2. Параллельные алгоритмы задач многоэкстремальной оптимизации.
4.8. Параллельные алгоритмы Монте-Карло
4.8.1. Алгоритмы параллельной генерации псевдослучайных чисел.
4.8.2. Численное решение задач методами Монте-Карло.
4.9. Параллельные алгоритмы для других классов вычислительно-трудоемких задач
4.9.1. Решение нелинейных уравнений и систем: методы простой итерации, Ньютона, хорд.
4.9.2. Приближение функций: полиномы Лагранжа, Ньютона, Чебышева, сплайны.
4.9.3. Численное дифференцирование и интегрирование
4.9.4. Численные методы решения обыкновенных дифференциальных уравнений.
4.9.5. Быстрое преобразование Фурье
4.9.6. Задача N-тел
4.9.7. Алгоритмы криптографии
4.9.8. Построение характеристического многочлена матрицы через ее степени.
5. Параллельные вычисления, большие задачи и конкретные предметные области
5.1. Параллельные методы решения вычислительно сложных задач наук о Земле
5.1.1. Анализ изменения климата и прогноз погоды.
5.1.2. Анализ загрязнения окружающей среды.
5.1.3. Анализ разработки полезных ископаемых. Обработка результатов сейсморазведки.
5.2. Параллельные методы решения вычислительно сложных задач наук о жизни
5.2.1. Разработка новых лекарств.
5.2.2. Генная инженерия.
5.2.3. Медицинская диагностика и разработка новых методов лечения.
5.3. Параллельные методы решения вычислительно сложных задач инженерных расчетов
5.3.1. Автоматизированное проектирование сложных изделий
5.3.2. Имитационное моделирование
5.3.3. Поиск оптимальных вариантов
5.4. Параллельные методы решения вычислительно сложных задач квантовой химии
5.4.1. Вычислительные методы, основанные на теории функционала плотности. Квантовая молекулярная динамика. Метод Кара-Паринелло.
5.5. Параллельные методы решения задач атомистического моделирования
5.5.1. Метод классической молекулярной динамики: распараллеливание на системах с общей памятью. Метод декомпозиции по частицами.
5.5.2. Метод классической молекулярной динамики: распараллеливание на системах с распределенной памятью. Метод декомпозиции по пространству.
5.6. Параллельные методы решения вычислительно сложных задач оборонной тематики
5.7. Прямые и обратные задачи механики реагирующих сред