Введение в параллельные и распределенные вычисления

распределенные вычисления
Судаков А.А.
“Параллельные и распределенные вычисления” Лекция 1

Александр Александрович

кандидат физико-математических наук,
доцент радиофизического факультета Киевского национального университета

имени Тараса Шевченко,
руководитель лаборатории параллельных вычислений информационно-вычислительного центра Киевского национального университета имени Тараса Шевченко

параллельных и распределенных систем
Технологии построения параллельных и распределенных систем
Практические

навыки построения и работы с параллельными и распределенными системами
Практические навыки разработки параллельных и распределенных программ

?
Все современные компьютерные системы используют элементы параллельной обработки информации
Многопроцессорность, конвейерная

обработка …
Все современные компьютерные системы используют распределенные вычисления
Многозадачность, базы данных, файловые сервера…
Пользователи привыкли к тому, что можно работать «сразу» с несколькими компьютерами и программами
Интернет, локальные сети, связанные объекты…
Некоторые задачи можно сегодня решить только с помощью параллельных и распределенных вычислений
получение «чрезвычайно» высокой производительности
получение высокой надежности и отказоустойчивости
Некоторые ресурсы распределены по определению
Специалисты по компьютерным системам должны в этом разбираться

требующие параллельных вычислений
Квантовая физика, химия, молекулярная биология
Микроэлектроника
Статистическое моделирование (метод Монте-Карло)
Ядерная

физика

препарат), найти, как это вещество вступает в реакцию, насколько оно

устойчиво и как действует

определяются типом атомов, положением ядер и электронной конфигурацией
Для нахождения электронной

конфигурации необходимо решать уравнения квантовой физики
Количество операций, и объем оперативной памяти, необходимые для решения определяются числом электронов молекулы N
Количество операций пропорционально N4-N7
Объем оперативной памяти пропорционален N3-N4

атомов 29
Количество электронов N=130
Количество базисных функций 280
Количество операций N5~1013
Задачу необходимо

решать десятки/сотни раз ~1015
Время на процессоре производительностью 1 млрд. операций в секунду около недели
Памяти около 4 Гбайт
Необходимо несколько процессоров

для которого нужно подобрать лекарственный препарат, который будет на него

действовать
Количество атомов несколько тысяч

методы классической физики
количество операций MN2 , где M количество итераций,

N количество атомов
Требует интенсивного обмена между процессорами
Время расчета – несколько недель

атомов на поверхности кремния для создания новых технологий
Требует квантово-физических расчетов

с веществом
Моделируется поведение большого количества частиц
Обработкая данных с ускорителей

системы

Параллельные вычисления

занятия (30 часов)
Практические занятия (30 часов)
Лабораторные занятия (40 часов)

и распределенных вычислений (9 лекций)
Теоретические основы параллельных вычислений (5 лекций)
Разработка

параллельных и распределенных систем (5 лекций)
Контрольные работы (2 занятия)
Зачет

операционные системы
Задачи, требующие параллельных вычислений и соответствующее программное обеспечение: 3D

анимация, математические пакеты, физические, химические, экономические и д.р. задачи
WWW технология, Java и их применение
MS Windows домен, Active directory, NetBios
Средства коммуникации для параллельных кластеров: Myrinet, SCI
Промышленные высоконадежные кластеры
Промышленные высокопроизводительные системы (суперкомпьютери, кластеры)
Распределенные файловые системы (NFS, AFS, GFS), SAN
Метакомпьютеры и GRID системы, globus, condor
Компиляторы и реализации библиотек для разработки параллельних и распределенных программ
Распределенные и параллельные системы управления базами данных
Средства создания параллельных программ для MS Windows (COM, Corba, .NET)
Pear-to-pear системы
Параллельные алгоритмы поиска, шифрования и дешифрования (2 години)
Языки программирования с внутренним параллелизмом и поддержкой распределенных систем

в командной строке Linux (15.05.2012)
Работа на удаленных машинах по

SSH, RSH (16.05.2012)
Распределенные системы имен (NIS) (17.05.2012)
Сетевые файловые системы (NFS, amd) (18.05.2012)
Менеджер ресурсов и менеджер заданий, кластер типа Beowulf (21.05.2011-22.05.2012)
Запуск PVM и MPI на кластере Beowulf (23.05.2012)

программ на основе интерфейса socket
Разработка многопоточных программ
Разработка с использованием RPC
Разработка

расчетных MPI программ
Разработка расчетных OpenMP программ
Измерение производительности

http://www.parallel.ru
Обчислювальний кластер Київського національного університету імені Тараса Шевченка http://www.cluster.kiev.ua

В.П. Гергель, Р.Г. Стронгин Основы параллельных вычислений для многопроцессорных вычислительных машин. Нижний новгород: Изд-во ННГУ им. Лобачевского, 2000, 176 с.
К. Хьюз, Т. Хьюз. Параллельное и распределенное программирование с использование С++. Перс. с англ. М: Издательский дом «Вильямс», 2004, 672 с.
И. Н Молчанов. Введение в алгоритмы параллельных вычислений. — К.: Наукова Думка, 1990. — 128 с.
Distributed information systems http://www.iks.inf.ethz.ch/education/ws04/eai/

распределенные вычисления?

вычислений
Параллельные вычисления – для вычисления одновременно используется несколько физических устройств

Распределенные

вычисления – вычисление выполняется в нескольких адресных пространствах (с помощью нескольких процессов)

не одновременная работа нескольких устройств
Основное использование параллелизма
Уровни параллелизма
Сложности, связанные с

параллелизмом
Истинный и псевдопараллелизм

промежутки времени 1 и 2 «происходит» процесс A

В промежутки времени

2 и 3 «происходит» процесс B

В промежуток времени 2 процессы A и B «происходят» одновременно, то есть параллельно

не параллельно
Когда процесс A выполняется, процесс B – не выполняется

Процессы

A и B выполняются не параллельно

массив из нескольких дисков
Заводской конвейер
Бригада рабочих, которые копают яму
Одновременная работа

диска и процессора (ассинхронный режим)
Параллельная работа нескольких видеоадаптеров

свою программу

на
предварительное
считывание
данных с диска
время

Выполнение
других действий
Получение
данных
Использование
даннх
Получение
запроса
Считывание

данных

Выдача данных

Приложение

Диск

Многозадачная операционная система с разделением времени
Сеть Ethernet с общей средой

передачи данных (CMACD)
Синхронный режим доступа к жесткому диску

времени
Каждая программа получает свой квант времени
Переключение между программами происходит быстро
Кажется,

что все программы выполняются одновременно
На самом деле – не параллельно

увеличение производительности

которые выполняются в единицу времени
Чем сложнее задача, тем большая производительность

системы нужна для ее решения в обозримом времени
Если увеличить количество операций, которые выполняются одновременно, то возрастет производительность системы

физических принципов построения компьютерных систем (оптические компьютеры, наноэлектроника, высокомолекулярная электроника)
Экстенсивные:
Увеличение

тактовой частоты устройств
Использование параллельной обработки

Физические основы современных компьютерных технологий были разработаны лет 30 назад

(физика полупроводников и диэлектриков)
Новые физические методы станут технологиями примерно лет через 30

тактовой частоте
Увеличение тактовой частоты приводит к увеличению потребляемой мощности

и к необходимости усиленного охлаждения
Увеличение тактовой частоты приводит возрастанию влияния паразитных обратных связей и к необходимости введения новых технических решения

выкопает яму за 1 час, то 2 рабочих – за

30 минут
Если одни процессор медленно…, то можно поставить 2, 3, 100 … и будет быстро
Можно повышать производительность без введения принципиально новых физических и технических решений
Никаким другим методом сегодня нельзя достичь такого повышения производительности, как за счет параллельной обработки

единиц (fine graine)
уровень инструкций
На уровне средних структурных единиц
Уровень подпрограмм
На

уровне крупных структурных единиц (course graine)
Уровень объектов
Уровень приложений

инструкций
Две (или больше) машинных инструкций выполняется одновременно
Суперскалярные и векторные процессоры
Конвейеры

Есть во всех современных процессорах (SSE, MMX)

процедура (функция, метод) выполняется на своем процессоре
Используется при многопоточном программировании
Поток

– часть процесса, которая выполняется параллельно с другими такими же частями

каждого объекта выполняются одновременно с методами других объектов
Объект – это

данные и те действия (методы, функции), которые с этими данными можно выполнять
Используются в многопоточных программах и распределенных объектных системах (COM, CORBA)

приложение выполняется на своем процессоре или на своем компьютере одновременно

с другими приложениями
Используется для кластерных вычислений и других распределенных систем

задачи – свой
Для повышения скорости вычислений — повышать уровень
Для

уменьшения задержек — понижать уровень
Часто в одной и той же параллельной программе применяется сразу несколько уровней
Например, параллельная программа выполняется на 4-х узлах кластера – уровень приложений, на каждом узле используется многопоточная обработка – уровень процедур, а каждый поток выполняется на процессоре с конвейерной обработкой – уровень инструкций

специальных параллельных алгоритмов
Необходимость специальных параллельных программ
Необходимость специальных аппаратных устройств для

параллельных вычислений

– последовательность операций, которую необходимо выполнить для решения задачи
Параллельный алгоритм

– последовательность нужно разбить на одновременно выполняемые последовательности - распараллелить
Очень часто задача распараллеливания чрезвычайно сложна
Иногда применяются свои уникальные «параллельные» подходы
Не все алгоритмы можно эффективно распереллелить

параллельный алгоритм имеет три составляющие:
Декомпозиция
Связь
Синхронизация

на части, которые выполняются параллельно
Декомпозиция данных – данные, с которыми

работает программа разбиваются на меньшие части и с каждой частью выполняются свои операции
Декомпозиция функций – последовательность действий разбивается на участки, которые выполняются параллельно

погоды для Украины
Территория разбивается на более мелкие области и для

каждой области выполняется расчет на своем процессоре, параллельно с остальными

CPU1

CPU10

между собой информацией

для Украины
Между соседними областями должен выполняться обмен информацией о состоянии

погоды на границе областей

параллельно выполняющиеся части в определенные моменты времени находятся в нужном

состоянии
Например, задача решена, только когда все параллельно выполняющиеся части завершают свою работу
Чтобы данные, считанные из переменной корректными, нужно гарантировать, что их в эту переменную записали

найти сумму
for (i=0; i

последовательная
Для распараллеивания воспользуемся ассоциативность сложения

сложнее последовательного
При небольшом количестве слагаемых или при большом количестве процессоров

можно получить не выигрыш а проигрыш в скорости
При очень большом количестве слагаемых и не очень большом количестве процессоров выигрыш в скорости будет существенным по сравнению с последовательным случаем
Эффективность распараллеливания зависит от задачи

выполняется на одном процессоре, потому не получает никакого преимущества от

параллельного выполнения
Для параллельных программ кроме самих вычислений необходимо реализовать связь и синхронизацию
Необходимо реализовать декомпозицию
Для упрощения существуют специальные компиляторы и библиотеки
Сложность отладки и профилирования

параллельных вычислений нужно несколько процессоров или компьютеров
Несколько процессоров/компьютеров всегда в

сумме дороже, чем один процессор/компьютер
Необходимо обеспечение высокоскоростных каналов связи между процессорами/компьютерами
С увеличением количества и сложности оборудования часто уменьшается его надежность

национального
Университета имени Тараса Шевченко
Кластеры Института кибернетики
НАН Украины имени Глушкова

Мура (Moore)
Закон Гроша: Производительность компьютера пропорциональна квадрату стоимости компьютера (сейчас

уже не работает)
Закон Мура: Производительность последовательных процессоров возрастает в два раза каждые 18-24 месяца

операционных систем с одним процессором одновременного выполнения получить нельзя, но

кажется, что задачи выполняются одновременно
В такой ситуации проблемы параллелизма остаются, а повышения производительности нет - псевдопараллелизм

Parallel - синонимы
Параллелизм – одновременность выполнения задачи
Конкуренция – одновременность использования

ресурсов

ЭВМ не может возрастать до бесконечности
Единственный способ получить чрезвычайно высокую

производительность на существующем техническом уровне – это использовать параллельные вычисления на уровне инструкций, процедур, объектов, приложений
Современные (даже последовательные компьютеры) используют параллелизм
Использование параллельных вычислений ведет к удорожанию оборудования
Параллельные вычисления требуют разработки специальных алгоритмов и использования специальных средств программирования
Не все задачи можно эффективно распараллелить

нескольких адресных пространствах (с помощью нескольких процессов)
Процесс (task) – единица

выполнения задания, которая включает выполняющийся код и ресурсы, которые это код использует и которые защищены от доступа других процессов
Адресное пространство – это то, как память и другие ресурсы представляются процессу

на одной машине и служат для
решения общей задачи
Программы выполняется

на разных машинах и служат для решения
общей задачи

ресурсов, которые находятся на разных аппаратных платформах или принадлежат разным

программам
Возможность специализации ресурсов
Возможность децентрализации
Возможность создания избыточности ресурсов для повышения надежности

на разных компьютерах
Доступ к удаленным сетевым ресурсам
Предоставление доступа пользователей других

машин к своим ресурсам
Распределенные вычисления сейчас стали синонимом слова Интернет

необходим большому количеству людей, то его необязательно размещать на компьютерах

всех пользователей, которым он нужна
Можно создать один ресурс, к которому будет выполняться доступ многих пользователей

можно разнести по нескольким физическим системам
Пример: большие поисковые системы

одного ресурса и в случае выхода из строя одной копии,

все остальные будут доступны
Пример: несколько копий базы данных, или несколько задач, которые выполняют одни и те же действия

общего в целях и подходах
Не все параллельные вычисления являются

распределенными
Не все распределенные вычисления являются параллельными

памятью
Параллельная, но не распределенная
Все программы могут совместно использовать одни и

те же данные

выполняет работу, а компьютер B является резервным на случай выхода

компьютера A из строя
Компьютеры не работают одновременно

позволяют решать проблемы производительности, надежности и обеспечения доступа к ресурсам
Тем

не менее использование параллельных и распределенных вычислений требует усложнения алгоритмов, программирования и аппаратных средств
У параллельных и распределенных вычислений много общего, но есть некоторые отличия