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

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

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

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

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

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

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

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

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

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

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

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

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

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

системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Процессы

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

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

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

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

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

Приложение

Диск

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CPU1

CPU10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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