ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ДАННЫХ

(16-20 часов)

  1. Введение. Большие задачи и суперкомпьютеры.
    Суперкомпьютеры в компьютерном мире. Примеры современных суперкомпьютеров, Top500, производительность, объемы оперативной и внешней памяти, энергопотребление, размещение.
    Вычислительно сложные задачи, примеры, разнообразие задач в различных прикладных областях.
    Развитие элементной базы компьютеров и их архитектуры, их влияние на увеличение производительности компьютеров.
    Последовательная, параллельная и конвейерная обработка данных. Ускорение выполнения программ. Пиковая и реальная производительность компьютеров.
    История появления параллелизма и конвейерности в архитектуре компьютеров.
    Иерархия памяти в компьютерах как средство повышения скорости выполнения программ, локальность вычислений и локальность использования данных, кэш-память.
    Закон Амдала и его следствия, суперлинейное ускорение.
    Последовательные и параллельные алгоритмы. Проблема отображения программ и алгоритмов на архитектуру параллельных вычислительных систем. Этапы решения задач на параллельных вычислительных системах.

  2. Архитектура параллельных вычислительных систем.
    Компьютеры с общей и распределенной памятью, принципы организации, сходства и различия, достоинства и недостатки. Соответствие двум основным задачам параллельных вычислений.
    Архитектуры SMP, NUMA, ccNUMA.
    Компьютеры с общей памятью. Коммутация процессоров и модулей памяти, степень неоднородности доступа к памяти. Причины снижения производительности на реальных программах.
    Компьютеры с распределенной памятью. Вычислительные узлы и коммуникационная сеть, топология связи между узлами, свойства топологий. Вычислительные кластеры: узлы, коммуникационные технологии, программное обеспечение, латентность и пропускная способность, вспомогательные сети. Причины снижения производительности на реальных программах.
    Скалярные и векторные команды. Скалярные, конвейерные и векторные функциональные устройства. Соотношение между понятиями двух блоков: "функциональное устройство, команда, обработка, компьютер" и "скалярный, векторный, конвейерный".
    Векторно-конвейерные компьютеры. Структура памяти и регистров, функциональные устройства, различные уровни параллельной и конвейерной обработки. Векторизация программ. Причины снижения производительности на реальных программах.
    Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность, EPIC. Мультитредовость/гипертрейдинг.
    Неоднородные распределенные вычислительные системы и среды, понятие метакомпьютинга. Отличительные свойства вычислительных сред. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов.
    Компьютеры с реконфигурируемой архитектурой, FPGA, концепция data-flow компьютеров.
    Современные микропроцессоры, особенности архитектуры, иерархия памяти. Эффективность выполнения программ.

  3. Технологии параллельного программирования.
    Схемы вычислительного процесса для параллельных программ: SPMD, Мастер/Рабочие. Процессы и нити, адресное пространство, синхронизация, обмен данными.
    Традиционные последовательные языки и распараллеливающие компиляторы, проблема выделения потенциального параллелизма последовательных программ. Спецкомментарии и директивы компилятору. Расширения существующих языков программирования. Специальные языки параллельного программирования. Программирование с использованием библиотек и интерфейсов передачи сообщений. Параллельные предметные библиотеки. Специализированные пакеты и программные комплексы высокого уровня.
    Технологии параллельного программирования: эффективность, продуктивность, переносимость.
    Технологии параллельного программирования MPI, OpenMP, Linda: структура параллельной программы, базовые конструкции, достоинства и недостатки, связь с архитектурой компьютера.
    Вспомогательный инструментарий для создания эффективных параллельных программ.

  4. Производительность параллельных вычислительных систем.
    Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM, NPB, HPCC, APEX.

  5. Введение в теорию анализа структуры программ и алгоритмов.
    Графовые модели программ. Граф управления и информационный граф программы, информационная и операционная история реализации программ. Взаимосвязь графовых моделей. Граф алгоритма как компактная параметрическая форма представления информационной истории. Информационная независимость операций и возможность их параллельного исполнения. Построение графа алгоритма для линейного класса программ. Длина критического пути графа алгоритма как мера степени параллельности. Ярусно-параллельная форма графа алгоритма, высота, ширина, каноническая ЯПФ. Виды параллелизма: конечный, массовый, координатный, скошенный. Эквивалентные преобразования программ, элементарные преобразования циклов. Зависимость степени параллелизма программ от формы записи алгоритма и выбора структур данных.

Основная литература:

  1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
  2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. - М.: Изд. факультета ВМиК МГУ, 2003.
  3. В.В.Корнеев. Параллельные вычислительные системы. - М.: Изд-во "Нолидж", 1999. - 320 с.
  4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература:

  1. Воеводин Вл.В., Жуматий С.А. Вычислительное дело и кластерные системы. - М.: Изд-во МГУ, 2007. - 161 с.
  2. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. - М.: Изд-во МГУ, 2004. - 71 с.

© Лаборатория Параллельных информационных технологий НИВЦ МГУ