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



Скачать 64.58 Kb.
Pdf просмотр
Дата14.03.2017
Размер64.58 Kb.
Просмотров262
Скачиваний0
ТипРеферат

Введение. Параллельные
программы как расширение
последовательных
Алексей А. Романенко
arom@ccfit.nsu.ru

О чем лекция?

Компьютеры. История. Тенденции.

Что такое параллельная программа
(ПП)?

Для чего нужна ПП?

Особенности ПП.

Средства разработки ПП.

пр.

Содержание
1.
Последовательная программа
2.
Приложения, требующие больших
вычислений.
3.
Для чего нужна параллельная программа?
4.
Параллелизм внутри компьютера.
5.
Архитектура современных процессоров.
6.
Что такое пареллельная программа?
7.
Типы параллелизма.

Содержание
8.
Типы вычислителей.
9.
Особенности параллельной программы.
10.
Закон Амдала
11.
Среда разработки
12.
Подходы к разработке параллельных
программ. Стоимость разработки.
13.
Вопросы для самоконтроля

История
George Boole
Charles Babbage
Alan Turing
John von Neumann
Claude Elwood Shannon
Norbert Wiener
Henry Edward Roberts

Науки

Информатика — наука о способах получения, накоплении, хранении, преобразовании, передаче и использовании информации

Кибернетика - наука об общих закономерностях процессов управления и передачи информации в машинах, живых организмах и обществе

Altair 8800 Computer with
8-inch floppy disk system
Разностная машина
Арифмометр

Последовательная
программа
Программа выполняет вычисление какой-либо функции F = G(X)
например:
a*x
2
+b*x+c=0, a != 0.
x1=(-b-sqrt(b
2
-4ac))/(2a), x2=(-b+sqrt(b
2
-4ac))/(2a)
Машина тюринга

Моделирование плазмы
N
10 6
dX
j
F
j dT
2
F
j sum i
(q i
, q j
)
Сложность
O(N*N) более 10 12
* 100...1000 операций

Требуются большие
вычислительные ресурсы

Ядерная физика, гидродинамика, ...

Биоинформатика

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

Газо и нефте добыча

Медицина

Обработка сигналов

пр.

Параллельная
программа
ПП – программа, которая позволяет среде выполнения одновременно исполнять некоторые операции
/
+/-
*
sqrt
-b
-
2
a
*
b b
*
*
4
a c

Параллелизм инструкций
Cache
Registers
ALU1
ALU2

Параллелизм инструкций
IF – Выборка инструкции
ID – декодирование инструкции
EX – Исполнение
MEM – доступ к памяти
WB – запись результата

Векторные операции
MMX, 3DNow, SSE, SSE2
X1
X2
X3
X4
Y1
Y2
Y3
Y4
X1+Y1 X2+Y2 X3+Y3 X4+Y4
+
=

Загрузка данных
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
выигрыш
Вычисления в 2 раза быстрее

Загрузка данных
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C
LD
C

Многоядерность

Параллельная программа – система взаимодействующих процессов

Типы параллелизма

На уровне бит

Параллелизм инструкций

Параллелизм данных

Параллелизм задач

Параллелизм на уровне бит
Увеличение разрядности слова с целью более быстрого вычисления операций над большими данными
Переход от 4 битных процессоров к 8 битовым, затем к 16- ти битовым. Сейчас де-факто стандартом являются процессоры с 32 разрядным словом

Параллелизм
данных
Исть множество данных
D
D.
Для каждого X
i из
D
D вычисляем F(X
i
)
D
D можно распределить по выч. узлам так
D
D =
D
D'

D
D'',
D
D'

D
D'' = 0
Обрабатываем
D
D' на CPU1,
D
D'' на CPU2 параллельно
D
D’
D’’
CPU1
CPU2

Параллельно процессы обрабатываю абсо- лютно разные данные абсолютно разными способами.
Масштабируется хуже, чем задачи с параллелизмом по данным
Параллелизм задач

Таксономия Флинна
Single data
SISD
MISD
Multiple data
SIMD
MIMD
Single instruction
Multiple instruction

Таксономия Флинна
SISD - последовательный компьютер.
SIMD – векторные компьютеры, векторные операции (SSE, MMX)
MISD – вырожденный тип. Конвейер (???)
MIMD – ПК (набор ПК), которые могут одновременно выполнять разные задачи.

Классы параллельных машин

многоядерные

SMP

С распределенной памятью

Кластера

GRID системы

Спец.процессоры

На базае FPGA

Графические процессоры

Векторные процессоры

Особенности параллельных
программ

недетерминизм

ошибки

Мертвые блокировки

Ошибки соревнования

Масштабируемость

Недетерминизм
Особенность программы, когда невозможно сказать, какой из параллельных процессов раньше начался или закончился
Time
A
B
C
Time
A
B
C
Time
A
B
C
Time
A
B
C

Ошибки соревнования
// thread 1
int k;
for(k=0, i=100; i< 200; i++){
k = (k + arr[i])%0xFF;
}
sum = (sum + k)%0xFF;
// thread 0
int k;
for(k=0, i=0; i< 100; i++){
k = (k + arr[i])%0xFF;
}
sum = (sum + k)%0xFF;
Программа выполняется на SMPсистеме.
Переменная sum разделяемая
Требуется синхронизация

Мертвые блокировки
Процесс P1 блокирует ресурс B, в то же время процесс P2 блокирует ресурс A. Если P1 попытается заблокировать ресурс A, а P2 - B, они заблокируются навсегда.
При неправильных методах борьбы с этой ошибкой мертвая блокировка может перерости в живую.
A
B
P1
P2

Масштибируемость
Добавляя ПП вычичлительных ресурсов мы ожидаем, что она будет работать быстрее. Это не всегда так
Способность программы ускоряться при добавлении ресурсов называется масштабируемостью
Степень масштабируемости
– количество
CPUs (вычислительных узлов) при котором добавление еще одного не приводит к существенному росту производительности

Закон Амдала
N – Количество CPU
P – Часть программы, которая может быть распараллелена

Системы с распределенной и
общей памятью
+
-
Системы с общей памятью
Проще программировать
Высокая стоимость, низкая масштабируемость
Системы с распраделенной памятью
Высокая масштабируемость,
Низкая стоимость
Сложнее программировать

Среды разработки

Директивы компилятора

HPF

OpenMP

MPI

POSIX Threads

пр.

Подходы к разработке ПП
Необходимо ответить на вопросы:
1. Стоит ли программу параллелить?
2. Почему надо параллелить программу? Ограничение по памяти/процессорного времени.
3. Какая часть программы должна быть распараллелина?
4. Какой инструмент наиболее адекватен для программирования?
5. Какой вычислительный комплекс у нас есть (имеем доступ) или будем иметь в будущем?
6. Сколько времени я потручу на распараллеливанию?
Высокая степень параллелизма и масштабируемости приводит к более высокой стоимости программы.

Вопросы для самопроверки

Что такое параллельная программа?

Назовите несколько компьютерных систем и сопоставьте их с классами систем в таксономии Флинна

Какая разница между параллелизм задач и данных?

Можно ли разработать параллельную программу для вычисления чисел
Фибоначи?

Document Outline

  • Slide 1
  • Slide 2
  • Slide 3
  • Slide 4
  • Slide 5
  • Slide 6
  • Slide 7
  • Slide 8
  • Slide 9
  • Slide 10
  • Slide 11
  • Slide 12
  • Slide 13
  • Slide 14
  • Slide 15
  • Slide 16
  • Slide 17
  • Slide 18
  • Slide 19
  • Slide 20
  • Slide 21
  • Slide 22
  • Slide 23
  • Slide 24
  • Slide 25
  • Slide 26
  • Slide 27
  • Slide 28
  • Slide 29
  • Slide 30
  • Slide 31
  • Slide 32
  • Slide 33
  • Slide 34
  • Slide 35
  • Slide 36



Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал