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

ИНФОРМАЦИЯ

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

(16-20 часов)

Введение. Большие задачи и суперкомпьютеры.
Суперкомпьютеры в компьютерном мире. Примеры современных суперкомпьютеров, Top500, производительность, объемы оперативной и внешней памяти, энергопотребление, размещение.
Вычислительно сложные задачи, примеры, разнообразие задач в различных прикладных областях.
Развитие элементной базы компьютеров и их архитектуры, их влияние на увеличение производительности компьютеров.
Последовательная, параллельная и конвейерная обработка данных. Ускорение выполнения программ. Пиковая и реальная производительность компьютеров.
История появления параллелизма и конвейерности в архитектуре компьютеров.
Иерархия памяти в компьютерах как средство повышения скорости выполнения программ, локальность вычислений и локальность использования данных, кэш-память.
Закон Амдала и его следствия, суперлинейное ускорение.
Последовательные и параллельные алгоритмы. Проблема отображения программ и алгоритмов на архитектуру параллельных вычислительных систем. Этапы решения задач на параллельных вычислительных системах.
Архитектура параллельных вычислительных систем.
Компьютеры с общей и распределенной памятью, принципы организации, сходства и различия, достоинства и недостатки. Соответствие двум основным задачам параллельных вычислений.
Архитектуры SMP, NUMA, ccNUMA.
Компьютеры с общей памятью. Коммутация процессоров и модулей памяти, степень неоднородности доступа к памяти. Причины снижения производительности на реальных программах.
Компьютеры с распределенной памятью. Вычислительные узлы и коммуникационная сеть, топология связи между узлами, свойства топологий. Вычислительные кластеры: узлы, коммуникационные технологии, программное обеспечение, латентность и пропускная способность, вспомогательные сети. Причины снижения производительности на реальных программах.
Скалярные и векторные команды. Скалярные, конвейерные и векторные функциональные устройства. Соотношение между понятиями двух блоков: "функциональное устройство, команда, обработка, компьютер" и "скалярный, векторный, конвейерный".
Векторно-конвейерные компьютеры. Структура памяти и регистров, функциональные устройства, различные уровни параллельной и конвейерной обработки. Векторизация программ. Причины снижения производительности на реальных программах.
Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность, EPIC. Мультитредовость/гипертрейдинг.
Неоднородные распределенные вычислительные системы и среды, понятие метакомпьютинга. Отличительные свойства вычислительных сред. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов.
Компьютеры с реконфигурируемой архитектурой, FPGA, концепция data-flow компьютеров.
Современные микропроцессоры, особенности архитектуры, иерархия памяти. Эффективность выполнения программ.
Технологии параллельного программирования.
Схемы вычислительного процесса для параллельных программ: SPMD, Мастер/Рабочие. Процессы и нити, адресное пространство, синхронизация, обмен данными.
Традиционные последовательные языки и распараллеливающие компиляторы, проблема выделения потенциального параллелизма последовательных программ. Спецкомментарии и директивы компилятору. Расширения существующих языков программирования. Специальные языки параллельного программирования. Программирование с использованием библиотек и интерфейсов передачи сообщений. Параллельные предметные библиотеки. Специализированные пакеты и программные комплексы высокого уровня.
Технологии параллельного программирования: эффективность, продуктивность, переносимость.
Технологии параллельного программирования MPI, OpenMP, Linda: структура параллельной программы, базовые конструкции, достоинства и недостатки, связь с архитектурой компьютера.
Вспомогательный инструментарий для создания эффективных параллельных программ.
Производительность параллельных вычислительных систем.
Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM, NPB, HPCC, APEX.
Введение в теорию анализа структуры программ и алгоритмов.
Графовые модели программ. Граф управления и информационный граф программы, информационная и операционная история реализации программ. Взаимосвязь графовых моделей. Граф алгоритма как компактная параметрическая форма представления информационной истории. Информационная независимость операций и возможность их параллельного исполнения. Построение графа алгоритма для линейного класса программ. Длина критического пути графа алгоритма как мера степени параллельности. Ярусно-параллельная форма графа алгоритма, высота, ширина, каноническая ЯПФ. Виды параллелизма: конечный, массовый, координатный, скошенный. Эквивалентные преобразования программ, элементарные преобразования циклов. Зависимость степени параллелизма программ от формы записи алгоритма и выбора структур данных.

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

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

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

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