Презентация Введение в параллельные и распределенные вычисления

Смотреть слайды в полном размере
Презентация Введение в параллельные и распределенные вычисления


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

Презентация содержит 73 слайда и доступна для скачивания в формате ppt. Размер скачиваемого файла: 919.00 KB

Просмотреть и скачать

Pic.1
Введение в параллельные и распределенные вычисления Судаков А. А. “Параллельные и распределенные выч
Введение в параллельные и распределенные вычисления Судаков А. А. “Параллельные и распределенные вычисления” Лекция 1
Pic.2
Автор курса и преподаватель Судаков Александр Александрович кандидат физико-математических наук, доц
Автор курса и преподаватель Судаков Александр Александрович кандидат физико-математических наук, доцент радиофизического факультета Киевского национального университета имени Тараса Шевченко, руководитель лаборатории параллельных вычислений информационно-вычислительного центра Киевского национального университета имени Тараса Шевченко
Pic.3
Задачи курса Теоретические основы работы параллельных и распределенных систем Технологии построения
Задачи курса Теоретические основы работы параллельных и распределенных систем Технологии построения параллельных и распределенных систем Практические навыки построения и работы с параллельными и распределенными системами Практические навыки разработки параллельных и распределенных программ
Pic.4
Для чего это нужно ? Все современные компьютерные системы используют элементы параллельной обработки
Для чего это нужно ? Все современные компьютерные системы используют элементы параллельной обработки информации Многопроцессорность, конвейерная обработка … Все современные компьютерные системы используют распределенные вычисления Многозадачность, базы данных, файловые сервера… Пользователи привыкли к тому, что можно работать «сразу» с несколькими компьютерами и программами Интернет, локальные сети, связанные объекты… Некоторые задачи можно сегодня решить только с помощью параллельных и распределенных вычислений получение «чрезвычайно» высокой производительности получение высокой надежности и отказоустойчивости Некоторые ресурсы распределены по определению Специалисты по компьютерным системам должны в этом разбираться
Pic.5
Научные и промышленные задачи, требующие параллельных вычислений Квантовая физика, химия, молекулярн
Научные и промышленные задачи, требующие параллельных вычислений Квантовая физика, химия, молекулярная биология Микроэлектроника Статистическое моделирование (метод Монте-Карло) Ядерная физика
Pic.6
Химия Есть формула вещества (лекарственный препарат), найти, как это вещество вступает в реакцию, на
Химия Есть формула вещества (лекарственный препарат), найти, как это вещество вступает в реакцию, насколько оно устойчиво и как действует
Pic.7
Как решается задача Свойства вещества определяются типом атомов, положением ядер и электронной конфи
Как решается задача Свойства вещества определяются типом атомов, положением ядер и электронной конфигурацией Для нахождения электронной конфигурации необходимо решать уравнения квантовой физики Количество операций, и объем оперативной памяти, необходимые для решения определяются числом электронов молекулы N Количество операций пропорционально N4-N7 Объем оперативной памяти пропорционален N3-N4
Pic.8
Оценка времени и ресурсов Количество атомов 29 Количество электронов N=130 Количество базисных функц
Оценка времени и ресурсов Количество атомов 29 Количество электронов N=130 Количество базисных функций 280 Количество операций N5~1013 Задачу необходимо решать десятки/сотни раз ~1015 Время на процессоре производительностью 1 млрд. операций в секунду около недели Памяти около 4 Гбайт Необходимо несколько процессоров
Pic.9
Молекулярная биохимия Есть вирусный белок для которого нужно подобрать лекарственный препарат, котор
Молекулярная биохимия Есть вирусный белок для которого нужно подобрать лекарственный препарат, который будет на него действовать Количество атомов несколько тысяч
Pic.10
Как решается задача Используются приближенные методы классической физики количество операций MN2 , г
Как решается задача Используются приближенные методы классической физики количество операций MN2 , где M количество итераций, N количество атомов Требует интенсивного обмена между процессорами Время расчета – несколько недель
Pic.11
Микро (нано) электроника Исследование поведения атомов на поверхности кремния для создания новых тех
Микро (нано) электроника Исследование поведения атомов на поверхности кремния для создания новых технологий Требует квантово-физических расчетов
Pic.12
Ядерная физика Взаимодействие ионизирующего излучения с веществом Моделируется поведение большого ко
Ядерная физика Взаимодействие ионизирующего излучения с веществом Моделируется поведение большого количества частиц Обработкая данных с ускорителей
Pic.13
Использование распределенных вычислений Интернет приложения Высоконадежные системы Параллельные вычи
Использование распределенных вычислений Интернет приложения Высоконадежные системы Параллельные вычисления
Pic.14
Программа курса Лекции (40 часов) Семинарские занятия (30 часов) Практические занятия (30 часов) Лаб
Программа курса Лекции (40 часов) Семинарские занятия (30 часов) Практические занятия (30 часов) Лабораторные занятия (40 часов)
Pic.15
Лекции Введение (1 лекция) Средства параллельных и распределенных вычислений (9 лекций) Теоретически
Лекции Введение (1 лекция) Средства параллельных и распределенных вычислений (9 лекций) Теоретические основы параллельных вычислений (5 лекций) Разработка параллельных и распределенных систем (5 лекций) Контрольные работы (2 занятия) Зачет
Pic.16
Семинарские занятия (15 занятий) Распределенные операционные системы Задачи, требующие параллельных
Семинарские занятия (15 занятий) Распределенные операционные системы Задачи, требующие параллельных вычислений и соответствующее программное обеспечение: 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 години) Языки программирования с внутренним параллелизмом и поддержкой распределенных систем
Pic.17
Лабораторные работы (6 работ) Работа в командной строке Linux (15. 05. 2012) Работа на удаленных маш
Лабораторные работы (6 работ) Работа в командной строке 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)
Pic.18
Практические занятия (6 занятий) Разработка программ на основе интерфейса socket Разработка многопот
Практические занятия (6 занятий) Разработка программ на основе интерфейса socket Разработка многопоточных программ Разработка с использованием RPC Разработка расчетных MPI программ Разработка расчетных OpenMP программ Измерение производительности
Pic.19
Литература Параллельные вычисления в России Обчислювальний кластер Київського національного універси
Литература Параллельные вычисления в России Обчислювальний кластер Київського національного університету імені Тараса Шевченка В. П. Гергель, Р. Г. Стронгин Основы параллельных вычислений для многопроцессорных вычислительных машин. Нижний новгород: Изд-во ННГУ им. Лобачевского, 2000, 176 с. К. Хьюз, Т. Хьюз. Параллельное и распределенное программирование с использование С++. Перс. с англ. М: Издательский дом «Вильямс», 2004, 672 с. И. Н Молчанов. Введение в алгоритмы параллельных вычислений. — К. : Наукова Думка, 1990. — 128 с. Distributed information systems
Pic.20
Что такое параллельные и распределенные вычисления?
Что такое параллельные и распределенные вычисления?
Pic.21
Определение параллельных и распределенных вычислений Параллельные вычисления – для вычисления одновр
Определение параллельных и распределенных вычислений Параллельные вычисления – для вычисления одновременно используется несколько физических устройств Распределенные вычисления – вычисление выполняется в нескольких адресных пространствах (с помощью нескольких процессов)
Pic.22
Особенности параллельных вычислений Одновременная и не одновременная работа нескольких устройств Осн
Особенности параллельных вычислений Одновременная и не одновременная работа нескольких устройств Основное использование параллелизма Уровни параллелизма Сложности, связанные с параллелизмом Истинный и псевдопараллелизм
Pic.23
Параллельно – значит одновременно В промежутки времени 1 и 2 «происходит» процесс A В промежутки вре
Параллельно – значит одновременно В промежутки времени 1 и 2 «происходит» процесс A В промежутки времени 2 и 3 «происходит» процесс B В промежуток времени 2 процессы A и B «происходят» одновременно, то есть параллельно
Pic.24
Не одновременно – значит не параллельно Когда процесс A выполняется, процесс B – не выполняется Проц
Не одновременно – значит не параллельно Когда процесс A выполняется, процесс B – не выполняется Процессы A и B выполняются не параллельно
Pic.25
Примеры параллельного выполнения Двухпроцессорный компьютер Дисковый массив из нескольких дисков Зав
Примеры параллельного выполнения Двухпроцессорный компьютер Дисковый массив из нескольких дисков Заводской конвейер Бригада рабочих, которые копают яму Одновременная работа диска и процессора (ассинхронный режим) Параллельная работа нескольких видеоадаптеров
Pic.26
Двухпроцессорный компьютер
Двухпроцессорный компьютер
Pic.27
Асинхронный режим чтения диска
Асинхронный режим чтения диска
Pic.28
Примеры не параллельного выполнения Многозадачная операционная система с разделением времени Сеть Et
Примеры не параллельного выполнения Многозадачная операционная система с разделением времени Сеть Ethernet с общей средой передачи данных (CMACD) Синхронный режим доступа к жесткому диску
Pic.29
Операционная система с разделением времени Каждая программа получает свой квант времени Переключение
Операционная система с разделением времени Каждая программа получает свой квант времени Переключение между программами происходит быстро Кажется, что все программы выполняются одновременно На самом деле – не параллельно
Pic.30
Использование параллелизма Единственная цель - увеличение производительности
Использование параллелизма Единственная цель - увеличение производительности
Pic.31
Производительность Производительность – количество операций, которые выполняются в единицу времени Ч
Производительность Производительность – количество операций, которые выполняются в единицу времени Чем сложнее задача, тем большая производительность системы нужна для ее решения в обозримом времени Если увеличить количество операций, которые выполняются одновременно, то возрастет производительность системы
Pic.32
Пути повышения производительности Интенсивные: Использование новых физических принципов построения к
Пути повышения производительности Интенсивные: Использование новых физических принципов построения компьютерных систем (оптические компьютеры, наноэлектроника, высокомолекулярная электроника) Экстенсивные: Увеличение тактовой частоты устройств Использование параллельной обработки
Pic.33
Новые технологии Наилучший вариант, но… Физические основы современных компьютерных технологий были р
Новые технологии Наилучший вариант, но… Физические основы современных компьютерных технологий были разработаны лет 30 назад (физика полупроводников и диэлектриков) Новые физические методы станут технологиями примерно лет через 30
Pic.34
Увеличение тактовой частоты Производительность пропорциональна тактовой частоте Увеличение тактовой
Увеличение тактовой частоты Производительность пропорциональна тактовой частоте Увеличение тактовой частоты приводит к увеличению потребляемой мощности и к необходимости усиленного охлаждения Увеличение тактовой частоты приводит возрастанию влияния паразитных обратных связей и к необходимости введения новых технических решения
Pic.35
Параллельные вычисления Если один рабочий выкопает яму за 1 час, то 2 рабочих – за 30 минут Если одн
Параллельные вычисления Если один рабочий выкопает яму за 1 час, то 2 рабочих – за 30 минут Если одни процессор медленно…, то можно поставить 2, 3, 100 … и будет быстро Можно повышать производительность без введения принципиально новых физических и технических решений Никаким другим методом сегодня нельзя достичь такого повышения производительности, как за счет параллельной обработки
Pic.36
Уровни параллелизма Уровень мелких структурных единиц (fine graine) уровень инструкций На уровне сре
Уровни параллелизма Уровень мелких структурных единиц (fine graine) уровень инструкций На уровне средних структурных единиц Уровень подпрограмм На уровне крупных структурных единиц (course graine) Уровень объектов Уровень приложений
Pic.37
Параллелизм на уровне машинных инструкций Две (или больше) машинных инструкций выполняется одновреме
Параллелизм на уровне машинных инструкций Две (или больше) машинных инструкций выполняется одновременно Суперскалярные и векторные процессоры Конвейеры Есть во всех современных процессорах (SSE, MMX)
Pic.38
Параллелизм на уровне процедур Каждая процедура (функция, метод) выполняется на своем процессоре Исп
Параллелизм на уровне процедур Каждая процедура (функция, метод) выполняется на своем процессоре Используется при многопоточном программировании Поток – часть процесса, которая выполняется параллельно с другими такими же частями
Pic.39
Параллелизм на уровне объектов Методы каждого объекта выполняются одновременно с методами других объ
Параллелизм на уровне объектов Методы каждого объекта выполняются одновременно с методами других объектов Объект – это данные и те действия (методы, функции), которые с этими данными можно выполнять Используются в многопоточных программах и распределенных объектных системах (COM, CORBA)
Pic.40
Параллелизм на уровне приложений Каждое приложение выполняется на своем процессоре или на своем комп
Параллелизм на уровне приложений Каждое приложение выполняется на своем процессоре или на своем компьютере одновременно с другими приложениями Используется для кластерных вычислений и других распределенных систем
Pic.41
Какой уровень лучше? Для каждой задачи – свой Для повышения скорости вычислений — повышать уровень Д
Какой уровень лучше? Для каждой задачи – свой Для повышения скорости вычислений — повышать уровень Для уменьшения задержек — понижать уровень Часто в одной и той же параллельной программе применяется сразу несколько уровней Например, параллельная программа выполняется на 4-х узлах кластера – уровень приложений, на каждом узле используется многопоточная обработка – уровень процедур, а каждый поток выполняется на процессоре с конвейерной обработкой – уровень инструкций
Pic.42
Сложности, связанные с параллелизмом Необходимость специальных параллельных алгоритмов Необходимость
Сложности, связанные с параллелизмом Необходимость специальных параллельных алгоритмов Необходимость специальных параллельных программ Необходимость специальных аппаратных устройств для параллельных вычислений
Pic.43
Параллельные алгоритмы Классическое определение: Алгоритм – последовательность операций, которую нео
Параллельные алгоритмы Классическое определение: Алгоритм – последовательность операций, которую необходимо выполнить для решения задачи Параллельный алгоритм – последовательность нужно разбить на одновременно выполняемые последовательности - распараллелить Очень часто задача распараллеливания чрезвычайно сложна Иногда применяются свои уникальные «параллельные» подходы Не все алгоритмы можно эффективно распереллелить
Pic.44
Декомпозиция, связь и синхронизация Каждый параллельный алгоритм имеет три составляющие: Декомпозици
Декомпозиция, связь и синхронизация Каждый параллельный алгоритм имеет три составляющие: Декомпозиция Связь Синхронизация
Pic.45
Декомпозиция Декомпозиция – разбиение задачи на части, которые выполняются параллельно Декомпозиция
Декомпозиция Декомпозиция – разбиение задачи на части, которые выполняются параллельно Декомпозиция данных – данные, с которыми работает программа разбиваются на меньшие части и с каждой частью выполняются свои операции Декомпозиция функций – последовательность действий разбивается на участки, которые выполняются параллельно
Pic.46
Пример декомпозиции Расчет прогноза погоды для Украины Территория разбивается на более мелкие област
Пример декомпозиции Расчет прогноза погоды для Украины Территория разбивается на более мелкие области и для каждой области выполняется расчет на своем процессоре, параллельно с остальными
Pic.47
Связь Разные процессоры должны обмениваться между собой информацией
Связь Разные процессоры должны обмениваться между собой информацией
Pic.48
Пример связи Расчет прогноза погоды для Украины Между соседними областями должен выполняться обмен и
Пример связи Расчет прогноза погоды для Украины Между соседними областями должен выполняться обмен информацией о состоянии погоды на границе областей
Pic.49
Синхронизация Обеспечение того, что все параллельно выполняющиеся части в определенные моменты време
Синхронизация Обеспечение того, что все параллельно выполняющиеся части в определенные моменты времени находятся в нужном состоянии Например, задача решена, только когда все параллельно выполняющиеся части завершают свою работу Чтобы данные, считанные из переменной корректными, нужно гарантировать, что их в эту переменную записали
Pic.50
Использование специальных параллельных алгоритмов Пример: найти сумму for (i=0; i<N; i++) S+=a[i]
Использование специальных параллельных алгоритмов Пример: найти сумму for (i=0; i<N; i++) S+=a[i]; В таком виде задача существенно последовательная Для распараллеивания воспользуемся ассоциативность сложения
Pic.51
Пример - конвейер
Пример - конвейер
Pic.52
Состояния конвейера
Состояния конвейера
Pic.53
Сложность Параллельный алгоритм получается значительно сложнее последовательного При небольшом колич
Сложность Параллельный алгоритм получается значительно сложнее последовательного При небольшом количестве слагаемых или при большом количестве процессоров можно получить не выигрыш а проигрыш в скорости При очень большом количестве слагаемых и не очень большом количестве процессоров выигрыш в скорости будет существенным по сравнению с последовательным случаем Эффективность распараллеливания зависит от задачи
Pic.54
Специальные параллельные программы Последовательная программа выполняется на одном процессоре, потом
Специальные параллельные программы Последовательная программа выполняется на одном процессоре, потому не получает никакого преимущества от параллельного выполнения Для параллельных программ кроме самих вычислений необходимо реализовать связь и синхронизацию Необходимо реализовать декомпозицию Для упрощения существуют специальные компиляторы и библиотеки Сложность отладки и профилирования
Pic.55
Аппаратные средства параллельных вычислений Для параллельных вычислений нужно несколько процессоров
Аппаратные средства параллельных вычислений Для параллельных вычислений нужно несколько процессоров или компьютеров Несколько процессоров/компьютеров всегда в сумме дороже, чем один процессор/компьютер Необходимо обеспечение высокоскоростных каналов связи между процессорами/компьютерами С увеличением количества и сложности оборудования часто уменьшается его надежность
Pic.56
Примеры параллельных систем
Примеры параллельных систем
Pic.57
Законы Гроша (Grosch) и Мура (Moore) Закон Гроша: Производительность компьютера пропорциональна квад
Законы Гроша (Grosch) и Мура (Moore) Закон Гроша: Производительность компьютера пропорциональна квадрату стоимости компьютера (сейчас уже не работает) Закон Мура: Производительность последовательных процессоров возрастает в два раза каждые 18-24 месяца
Pic.58
Истинный и псевдопараллелизм Для многозадачных операционных систем с одним процессором одновременног
Истинный и псевдопараллелизм Для многозадачных операционных систем с одним процессором одновременного выполнения получить нельзя, но кажется, что задачи выполняются одновременно В такой ситуации проблемы параллелизма остаются, а повышения производительности нет - псевдопараллелизм
Pic.59
Параллелизм и конкуренция Concurrent и Parallel - синонимы Параллелизм – одновременность выполнения
Параллелизм и конкуренция Concurrent и Parallel - синонимы Параллелизм – одновременность выполнения задачи Конкуренция – одновременность использования ресурсов
Pic.60
Выводы относительно параллелизма Производительность последовательных ЭВМ не может возрастать до беск
Выводы относительно параллелизма Производительность последовательных ЭВМ не может возрастать до бесконечности Единственный способ получить чрезвычайно высокую производительность на существующем техническом уровне – это использовать параллельные вычисления на уровне инструкций, процедур, объектов, приложений Современные (даже последовательные компьютеры) используют параллелизм Использование параллельных вычислений ведет к удорожанию оборудования Параллельные вычисления требуют разработки специальных алгоритмов и использования специальных средств программирования Не все задачи можно эффективно распараллелить
Pic.61
Распределенные вычисления Вычисление выполняется в нескольких адресных пространствах (с помощью неск
Распределенные вычисления Вычисление выполняется в нескольких адресных пространствах (с помощью нескольких процессов) Процесс (task) – единица выполнения задания, которая включает выполняющийся код и ресурсы, которые это код использует и которые защищены от доступа других процессов Адресное пространство – это то, как память и другие ресурсы представляются процессу
Pic.62
Распределенные программы
Распределенные программы
Pic.63
Преимущества распределенных систем Возможность использования ресурсов, которые находятся на разных а
Преимущества распределенных систем Возможность использования ресурсов, которые находятся на разных аппаратных платформах или принадлежат разным программам Возможность специализации ресурсов Возможность децентрализации Возможность создания избыточности ресурсов для повышения надежности
Pic.64
Использование ресурсов, которые находятся на разных компьютерах Доступ к удаленным сетевым ресурсам
Использование ресурсов, которые находятся на разных компьютерах Доступ к удаленным сетевым ресурсам Предоставление доступа пользователей других машин к своим ресурсам Распределенные вычисления сейчас стали синонимом слова Интернет
Pic.65
Специализация Если есть ресурс, который необходим большому количеству людей, то его необязательно ра
Специализация Если есть ресурс, который необходим большому количеству людей, то его необязательно размещать на компьютерах всех пользователей, которым он нужна Можно создать один ресурс, к которому будет выполняться доступ многих пользователей
Pic.66
Децентрализация Данные очень большого объема можно разнести по нескольким физическим системам Пример
Децентрализация Данные очень большого объема можно разнести по нескольким физическим системам Пример: большие поисковые системы
Pic.67
Обеспечение надежности Создается несколько копий одного ресурса и в случае выхода из строя одной коп
Обеспечение надежности Создается несколько копий одного ресурса и в случае выхода из строя одной копии, все остальные будут доступны Пример: несколько копий базы данных, или несколько задач, которые выполняют одни и те же действия
Pic.68
Сложности Декомпозиция, связь, синхронизация Усложнение программирования
Сложности Декомпозиция, связь, синхронизация Усложнение программирования
Pic.69
Параллельные и распределенные вычисления Много общего в целях и подходах Не все параллельные вычисле
Параллельные и распределенные вычисления Много общего в целях и подходах Не все параллельные вычисления являются распределенными Не все распределенные вычисления являются параллельными
Pic.70
Система с совместно используемой памятью Параллельная, но не распределенная Все программы могут совм
Система с совместно используемой памятью Параллельная, но не распределенная Все программы могут совместно использовать одни и те же данные
Pic.71
Система с зеркалированием Компьютер A выполняет работу, а компьютер B является резервным на случай в
Система с зеркалированием Компьютер A выполняет работу, а компьютер B является резервным на случай выхода компьютера A из строя Компьютеры не работают одновременно
Pic.72
Выводы Параллельные и распределенные вычисления позволяют решать проблемы производительности, надежн
Выводы Параллельные и распределенные вычисления позволяют решать проблемы производительности, надежности и обеспечения доступа к ресурсам Тем не менее использование параллельных и распределенных вычислений требует усложнения алгоритмов, программирования и аппаратных средств У параллельных и распределенных вычислений много общего, но есть некоторые отличия
Pic.73
Вопросы
Вопросы


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!