Курс «Распределенные и параллельные вычисления», ФИВТ, 3-й курс, осенний семестр
Темы лекций и контрольные вопросы (дифф. зачет)
Содержание
1. Темы курса 2
1.1. Принципы работы компьютерных сетей и сетевые протоколы 2
1.2. Проблематика решения задач в распределенной вычислительной среде 2
1.3. Основы программной архитектуры РВС 2
1.4. Распределенные сценарии решения декомпозируемых задач линейной алгебры 3
1.5. Грид-технологии 3
1.6. Параллельные вычисления 4
1.7. Классификации аппаратных архитектур многопроцессорных вычислительных систем (МВС) 4
2. Демонстрационные примеры и задачи 5
3. Рекомендуемые ссылки 7
4. Список основных вопросов на диф. зачете (экзамене) 8
Темы курса Принципы работы компьютерных сетей и сетевые протоколы
Принципы передачи данных по компьютерным сетям. Пакетная и канальная коммутация.
Понятие стека сетевых протоколов. Семиуровневая модель OSI-ISO. Модель DoD. Стек протоколов TCP/IP.
«Идеологические», технологические и математические аспекты темы решения вычислительных задач в распределенных вычислительных системах (РВС).
Классификация РВС по типам решаемых задач (High-Performance «super»Сomputing, High-Throughput Computing, Data-intensive computing, Many-Task Computing). Понятие декомпозируемых вычислительных задач.
Представление о РВС как о совокупности взаимодействующих (по сети) процессов. Понятие об основных типах программных (программно-аппаратных) архитектур (SISD, SIMD (GPU), MISD, MIMD).
Эволюция программных моделей (архитектур) распределенных вычислений. Влияние стилей «обычного» программирования: процедурный стиль - модель вызова удаленных процедур (RPC, Remote Procedure Call); объектно-ориентированный (ОО) стиль - OO промежуточное ПО; функциональный стиль - REST-сервисы. Модель РВС на принципах обмена сообщениями (MOM, Message Oriented Middleware).
Типовой «жизненный цикл» программной технологии и проблема ее адекватного выбора.
Примеры декомпозируемых задач: последовательность ассоциативных операций, принцип динамического программирования и возможности декомпозиции.
Основы программной архитектуры РВСОсновные элементы архитектуры процессов РВС. Серверный и клиентский фрагменты процессов (исполняемого кода). Каркасы и представители удаленных процедур (удаленных объектов). Маршаллинг и демаршаллинг при вызовах удаленных методов.
Различные способы взаимодействия клиентских и серверных компонент (по типам вызовов «удаленных» методов): синхронный (блокирующий), односторонний, асинхронный («отложенный»).
Основные этапы разработки РВС на основе существующих технологий объектно-ориентированного промежуточного ПО (ОО ППО) на примере программного инструментария Ice, Internet Communication Engine. Контрактный принцип проектирования.
Понятие и предназначение декларативных языков описания интерфейсов (на примере Slice). Применение «предкомпиляторов» для отображения описания типов данных и интерфейсов на декларативном языке в высокоуровневые языки программирования на этапе реализации РВС. Пример «проектирования» типов данных и интерфейса «арифметического калькулятора» на языке Slice.
Эволюция технологий ОО ППО: CORBA, Ice, Веб-сервисы (WSDL, SOAP, XML). Отношение OO ППО и архитектурного стиля REST, Representational State Transfer.
Распределенные сценарии решения декомпозируемых задач линейной алгебрыБазовые задачи линейной алгебры: перемножение матриц, обращение, LU-разложение. Ускорение перемножения матриц на основе блочной декомпозиции.
Обращение плохо-обусловленных матриц на основе символьных вычислений (в системе Maxima). Распределенные сценарии обращения: 1) LU-факторизация и параллельное вычисление столбцов обратной матрицы; 2) блочная декомпозиция и дополнения Шура. Количественные оценки ускорения. Проблема балансировки вычислительной нагрузки в сценарии 1) (на этапе независимого вычисления столбцов обратной матрицы). Принципы реализации сценария 2) на основе программного инструментария MathCloud (WebSolve, http://code. /p/websolve/) .
Грид-технологииКонцепция грид-вычислений, область применения и типы грид-систем. Понятие виртуальной организации. Отличие грид-систем от других распределенных вычислительных систем. Требования к программной инфраструктуре грид. Примеры грид-систем и технологий.
Сервисные грид-системы. Программное обеспечение сервисных гридов, основные компоненты. Обеспечение безопасности в грид. Управление ресурсами. Управление данными. Информационные сервисы.
Грид-системы из персональных компьютеров (ГСПК). Отличия от сервисных гридов. Программное обеспечение ГСПК. Технологии частных ГСПК на примере ПО Condor. Технологии добровольных вычислений на примере платформы BOINC.
Параллельные вычисленияХарактеристики поизводительности параллельных программ: ускорение, эффективность, формулы для их измерения. Закон Амдала.
Системы с распределенной и общей памятью. Основные средства программирования. Процессы и потоки.
Библиотека MPI. Модель SPMD. Точечные и коллективные обмены сообщениями. Библиотека MPI. Коммуникаторы и группы процессов.
Стандарт POSIX Threads. Создание и завершение потока. Организация критических секций с помощью механизма мьютексов.
Пакет OpenMP. Общая организация. Директивы parallel и for.
Графические сопроцессоры общего назначения (GP GPU). Основы архитектуры. Общие сведения о программном стеке CUDA.
Классификации аппаратных архитектур многопроцессорных вычислительных систем (МВС)Список задач для высокопроизводительных систем.
Классификации архитектур вычислительных систем. Классификации Флинна, уточнения Ванга-Бриггса, классификации Фенга и Хокни.
Архитектуры SMP, MPP, PVP. Кластерная архитектура.
Особенности организации памяти в современных персональных компьютерах и МВС. Различные виды памяти. Иерархия памяти.
Различные архитектуры МВС по типу доступа к памяти. (UMA. NUMA, NORMA и т. д.)
Демонстрационные примеры и задачи:
Диагностические утилиты Unix-подобных операционных систем:
- уровень сетевого доступа: arp, ifconfig; межсетевой уровень: route, netstat, ping, traceroute; транспортный уровень : netstat, netcat, telnet, host; прикладной уровень: netstat, tcpdump, nmap.
Распараллеливание последовательности ассоциативных операций. Задача «о двух саперных роботах» и ее решение методом динамического программирования. Возможность ускорения вычислений.
Знакомство с программным инструментарием MathCloud. Создание распределенной системы обработки изображений в визуальном редакторе сценариев.
Пример децентрализованной распределенной системы визуализации фрактальных множеств.
Распределенный сценарий LU-разложения на основе блочной декомпозиции и дополнения Шура.
Использование MPI при разработке параллельных приложений. Вычисление определенного интеграла функции: последовательная реализация, реализация с простой отправкой сообщений через MPI, реализация с коллективными операциями MPI.
Язык Erlang. Разработка последовательного кода: быстрая сортировка. Параллельные вычисления: порождение процессов, отправка и прием сообщений, регистрация процессов, разработка «кольца» процессов. Обработка ошибок в Erlang. Элементы OTP: gen_server.
:
Модели OSI и DoD.
Протоколы Frame Relay, SDH, ATM.
Протоколы транспортного уровня: TCP, UDP. Сеансовый уровень: SSH. Прикладной уровень: DNS, whois. Понятие о QoS.
Диагностические утилиты
- уровень сетевого доступа: arp, ipconfig/ifconfig; межсетевой уровень: route, netstat, ping, traceroute; транспортный уровень : netstat, netcat, telnet, host; прикладной уровень: netstat, nslookup, whois.
Распределённые системы. HPC и HTC. Различные виды взаимодействия удалённых процессов.
Пример децентрализованной распределенной системы визуализации фрактальных множеств.
Взаимодействие удалённых процессов. Обмен сообщениями и удалённые вызовы процедур. RMI, понятие proxy-класса.
Параллельные вычислительные системы. Различные подходы. Устранение зависимостей в циклах. Понятие об ускорении и эффективности, закон Амдала. Использование OpenMP для вычисления определенного интеграла функции, Qsort.
Использование MPI при разработке параллельных приложений. Вычисление определенного интеграла функции: последовательная реализация, реализация с простой отправкой сообщений через MPI, реализация с коллективными операциями MPI.
Использование GridGain для распределённых вычислений. Вычисление определённого интеграла функции.
Рекомендуемые ссылки Материалы к разделам 1.2–1.4
http://dcs. isa. ru/drupal/ru/staff/vladimirv/dccourse/ , . Основы параллельных вычислений для многопроцессорных вычислительных систем, Учебное пособие – Нижний Новгород: Изд-во ННГУ им. , 2003. 184 с. (http://lib. mipt. ru) Теория и практика параллельных вычислений: учебное пособие. – М.: Интернет-Университет ИТ; БИНОМ, 2007. – 423 с. (по материалам сайта http://intuit. ru) , Вл. В. Воеводин. Параллельные вычисления. СПб.:БХВ-Петербург, 2002. – 608 с. Проблемы вычислений в распределенной среде: организация вычислений в глобальных сетях. Сборник трудов ИСА РАН, М.: Эдиториал УРСС, 2004. Интернет Университет ИТ, http://www. intuit. ru Лейзерсон Ч, лгоритмы: построение и анализ, 2-е изд. : Пер. с англ. — М. : Издательский дом "Вильяме", 2005. — 1296 с. (http://lib. mipt. ru) (Раздел 28.3 «Решение систем линейных уравнений») Документация по Ice (Internet Communication Engine), http://www. Материалы к разделу 1.5: http://dcs. isa. ru/drupal/ru/staff/os/course , , Технологии параллельного программирования, Издательство: Форум Инфра-М, Учебное пособие, cерия Высшее образование, 2008, 208 страниц. , , Архитектуры и топологии многопроцессорных вычислительных систем. - М.: Интернет-университет информационных технологий - ИНТУИТ. ру », 2004, 176 стр. ISBN: 5-9556-0018-3 Список основных вопросов на диф. зачете Предмет распределенных вычислений и классификация по способам организации вычислительного сценария (High-Performance, High Throughput Computing, Data Intensive Computing, Many Task Computing.). Вызовы «удаленных» процедур (RPC) и обмен сообщениями (MOM) - как основные стили организации взаимодействия в РВС; их сходства и отличия. Представление о РВС как о совокупности взаимодействующих (по сети) процессов. Основные элементы архитектуры процессов РВС. Серверный и клиентский фрагменты процессов (исполняемого кода). Каркасы и представители удаленных процедур (удаленных объектов). Маршаллинг и демаршаллинг при вызовах удаленных методов. «Представители» и «каркасы» удаленных объектов. Различные способы взаимодействия клиентских и серверных компонент (по типам вызовов «удаленных» методов): синхронный (блокирующий), односторонний, асинхронный («отложенный»). Основные этапы разработки РВС на основе существующих технологий объектно-ориентированного промежуточного ПО (ОО ППО) на примере программного инструментария Ice, Internet Communication Engine. «Контрактный» принцип проектирования. Проектирование интерфейсов на языке Slice. Назначение предкомпилятора из Slice в различные языки программирования. Декомпозиция при вычислении обратной матрицы. Возможные схемы распределенного сценария вычислений: LU-разложение; блочная декомпозиция и дополнение Шура. Оценки эффективности реализации в РВС. LU-разложение матрицы. Сценарий распределенного LU-разложения на основе блочной декомпозиции и дополнения Шура. Концепция грид-вычислений, область применения и типы грид-систем. Понятие виртуальной организации. Отличие грид-систем от других распределенных вычислительных систем. Требования к программной инфраструктуре грид. Примеры грид-систем и технологий. Программное обеспечение сервисных гридов, основные компоненты. Обеспечение безопасности в грид. Управление ресурсами. Программное обеспечение сервисных гридов, основные компоненты. Управление данными. Информационные сервисы. Грид-системы из персональных компьютеров (ГСПК). Отличия от сервисных гридов. Технологии частных ГСПК на примере ПО Condor. Грид-системы из персональных компьютеров (ГСПК). Отличия от сервисных гридов. Технологии добровольных вычислений на примере платформы BOINC. Характеристики поизводительности параллельных программ: ускорение, эффективность, формулы для их измерения. Закон Амдала. Системы с распределенной и общей памятью. Основные средства программирования. Процессы и потоки. Библиотека MPI. Модель SPMD. Точечные и коллективные обмены сообщениями. Библиотека MPI. Коммуникаторы и группы процессов. Стандарт POSIX Threads. Создание и завершение потока. Организация критических секций с помощью механизма мьютексов. Пакет OpenMP. Общая организация. Директивы parallel и for. Графические сопроцессоры общего назначения (GP GPU). Основы архитектуры. Общие сведения о программном стеке CUDA. Классификации архитектур вычислительных систем. Классификации Флинна (SISD, SIMD, MISD, MIMD), уточнения Ванга-Бриггса, классификации Фенга и Хокни. Архитектуры SMP, MPP, PVP. Кластерная архитектура. Особенности организации памяти в современных персональных компьютерах и МВС. Различные виды памяти. Иерархия памяти. Различные архитектуры МВС по типу доступа к памяти. (UMA. NUMA, NORMA и т. д.)
