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

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

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

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

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

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

Содержание слайда: Химия Есть формула вещества (лекарственный препарат), найти, как это вещество вступает в реакцию, насколько оно устойчиво и как действует

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

Содержание слайда: Оценка времени и ресурсов Количество атомов 29 Количество электронов N=130 Количество базисных функций 280 Количество операций N5~1013 Задачу необходимо решать десятки/сотни раз ~1015 Время на процессоре производительностью 1 млрд. операций в секунду около недели Памяти около 4 Гбайт Необходимо несколько процессоров

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

Содержание слайда: Как решается задача Используются приближенные методы классической физики количество операций MN2 , где M количество итераций, N количество атомов Требует интенсивного обмена между процессорами Время расчета – несколько недель

Содержание слайда: Микро (нано) электроника Исследование поведения атомов на поверхности кремния для создания новых технологий Требует квантово-физических расчетов

Содержание слайда: Ядерная физика Взаимодействие ионизирующего излучения с веществом Моделируется поведение большого количества частиц Обработкая данных с ускорителей

Содержание слайда: Использование распределенных вычислений Интернет приложения Высоконадежные системы Параллельные вычисления

Содержание слайда: Программа курса Лекции (40 часов) Семинарские занятия (30 часов) Практические занятия (30 часов) Лабораторные занятия (40 часов)

Содержание слайда: Лекции Введение (1 лекция) Средства параллельных и распределенных вычислений (9 лекций) Теоретические основы параллельных вычислений (5 лекций) Разработка параллельных и распределенных систем (5 лекций) Контрольные работы (2 занятия) Зачет

Содержание слайда: Семинарские занятия (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 години) Языки программирования с внутренним параллелизмом и поддержкой распределенных систем

Содержание слайда: Лабораторные работы (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)

Содержание слайда: Практические занятия (6 занятий) Разработка программ на основе интерфейса 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-х узлах кластера – уровень приложений, на каждом узле используется многопоточная обработка – уровень процедур, а каждый поток выполняется на процессоре с конвейерной обработкой – уровень инструкций

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

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

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

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

Содержание слайда: Пример декомпозиции Расчет прогноза погоды для Украины Территория разбивается на более мелкие области и для каждой области выполняется расчет на своем процессоре, параллельно с остальными

Содержание слайда: Связь Разные процессоры должны обмениваться между собой информацией

Содержание слайда: Пример связи Расчет прогноза погоды для Украины Между соседними областями должен выполняться обмен информацией о состоянии погоды на границе областей

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

Содержание слайда: Использование специальных параллельных алгоритмов Пример: найти сумму for (i=0; i<N; i++) S+=a[i]; В таком виде задача существенно последовательная Для распараллеивания воспользуемся ассоциативность сложения

Содержание слайда: Пример - конвейер

Содержание слайда: Состояния конвейера

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

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

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

Содержание слайда: Примеры параллельных систем

Содержание слайда: Законы Гроша (Grosch) и Мура (Moore) Закон Гроша: Производительность компьютера пропорциональна квадрату стоимости компьютера (сейчас уже не работает) Закон Мура: Производительность последовательных процессоров возрастает в два раза каждые 18-24 месяца

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

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

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

Содержание слайда: Распределенные вычисления Вычисление выполняется в нескольких адресных пространствах (с помощью нескольких процессов) Процесс (task) – единица выполнения задания, которая включает выполняющийся код и ресурсы, которые это код использует и которые защищены от доступа других процессов Адресное пространство – это то, как память и другие ресурсы представляются процессу

Содержание слайда: Распределенные программы

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

Содержание слайда: Использование ресурсов, которые находятся на разных компьютерах Доступ к удаленным сетевым ресурсам Предоставление доступа пользователей других машин к своим ресурсам Распределенные вычисления сейчас стали синонимом слова Интернет

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

Содержание слайда: Децентрализация Данные очень большого объема можно разнести по нескольким физическим системам Пример: большие поисковые системы

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

Содержание слайда: Сложности Декомпозиция, связь, синхронизация Усложнение программирования

Содержание слайда: Параллельные и распределенные вычисления Много общего в целях и подходах Не все параллельные вычисления являются распределенными Не все распределенные вычисления являются параллельными

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

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

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

Содержание слайда: Вопросы