Основы построения и функционирования вычислительных систем

1.

ВОЕННО-КОСМИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ А.Ф. МОЖАЙСКОГО
Кафедра информационно-вычислительных систем и сетей
РАЗДЕЛ 3. Вычислительные системы
Тема 7. Основы построения и функционирования
вычислительных систем
Доктор технических наук профессор,
БАСЫРОВ А.Г.

2.

ОРГАНИЗАЦИЯ ЭВМ И СИСТЕМ
Лекция №24
Параллелизм как основа
высокопроизводительных вычислений
Цель: сформировать у обучающихся знания о принципах
параллельных вычислений
Учебные вопросы:
1.Основные понятия параллельных вычислений
2.Метрики и законы параллельных вычислений
3.Способы высокопроизводительной обработки
информации
2

3.

Учебный вопрос № 1
Основные понятия параллельных
вычислений
3

4.

Основные понятия параллельных вычислений
4
Параллельные вычисления – совокупность вопросов,
относящихся к созданию ресурсов параллелизма в
процессе решения задач и гибкому управлению
реализацией этого параллелизма с целью достижения
наибольшей
эффективности
использования
вычислительной системы.
Параллельная
вычислительная
система
–
вычислительная система, содержащая не менее двух
вычислительных модулей, способных согласованно
одновременно (параллельно) осуществлять обработку
информации.
Параллельные процессы – процессы обработки данных,
у которых интервалы времени выполнения перекрываются
за счет использования различных ресурсов одной и той же
системы [ГОСТ 19781-90].

5.

Задачи параллельной обработки информации
ПРОБЛЕМАТИКА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
разработка параллельных вычислительных систем
(архитектура параллельных вычислительных систем)
анализ эффективности параллельных вычислений для
оценивания получаемого ускорения вычислений
(методы анализа сложности)
создание и развитие параллельных алгоритмов для
решения прикладных задач в разных областях
(методы организации параллельных вычислений)
создание и развитие системного программного
обеспечения для параллельных вычислительных систем
(параллельное программирование - языки, среды
разработки, библиотеки).
5

6.

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

7.

Способы организации параллельной обработки информации
РЕЖИМЫ ВЫПОЛНЕНИЯ НЕЗАВИСИМЫХ
ЧАСТЕЙ ПРОГРАММЫ
многозадачный режим
(режим разделения времени)
параллельное выполнение
распределенные вычисления
7

8.

Способы организации параллельной обработки информации
многозадачный режим
(режим разделения времени)
Процесс 1
Процесс 2
Процесс 3
ЦП
ЦП
ЦП
ЦП
ЦП
t=6
мультипрограммирование
ЦП
8
параллельное
выполнение
ЦП1
ЦП1
ЦП2
ЦП2
ЦП3
ЦП3
t=2
мультипроцессирование

9.

Уровни параллелизма
ЧЕТЫРЕ УРОВНЯ ПАРАЛЛЕЛИЗМА
Параллелизм заданий - каждый процессор загружается
своей собственной независимой от других вычислительной
задачей
Параллелизм на уровне программы - вычислительная
программа разбивается на части, которые могут
выполняться одновременно на различных процессорах
Параллелизм команд - реализован на низком уровне
(например, конвейеры и т.д.)
Параллелизм на уровне машинных слов
и арифметических операций
9

10.

Уровни параллелизма
10

11.

Виды параллелизма
11
Параллелизм данных
Параллелизм задач
одна операция
выполняется сразу над
всеми элементами
массива данных
вычислительная задача
разбивается на несколько
подзадач и каждый
процессор загружается своей
собственной подзадачей
высокопроизводительный
ФОРТРАН (High Performance
FORTRAN) и параллельные
версии языка С
специализированные библиотеки
MPI (Message Passing Interface),
PVM (Parallel Virtual Machines).

12.

Учебный вопрос № 2
Метрики и закономерности
параллельных вычислений
12

13.

Метрики и законы параллельной обработки информации
Метрики параллельных вычислений –
показатели качества функционирования
вычислительной системы при параллельной
обработке информации
Закон параллельных вычислений –
зависимость значения метрики от параметров
параллельной обработки информации
13

14.

Метрики параллельной обработки информации
Метрики параллельных вычислений
1) Степень параллелизма
2) Индекс параллелизма
3) Ускорение
4) Эффективность
5) Утилизация
6) Избыточность
7) Сжатие
8) Качество
9) Стоимость
Обозначения
• n – количество процессоров, используемых для
организации параллельных вычислений;
• O(n) – объем вычислений - количество
операций, выполняемых n процессорами в ходе
решения задачи;
• T(n) – общее время вычислений (решения
задачи) с использованием n процессоров.
14

15.

Метрики параллельной обработки информации
Степень параллелизма D(t) (DOP, Degree Of
Parallelism) – число ВМ ВС, параллельно
участвующих в выполнении программы в
каждый момент времени t.
DOP позволяет определить среднее число p
операций
программы,
которые
можно
выполнять одновременно.
Графическое представление степени
параллелизма называют профилем
параллельной программы
15

16.

Профиль параллельной программы
16
Средний параллелизм
ti – интервал времени
загрузки i процессоров ВС
Общий объем вычислений O(n) за заданный
период пропорционален площади под кривой
профиля параллелизма:
Δ - производительность одиночного процессора ВС - количество
операций в единицу (квант) времени, не учитывая издержек, связанных
с обращением к памяти и пересылкой данных

17.

Метрики параллельной обработки информации
Индекс параллелизма - средняя
скорость параллельных вычислений
Ускорением параллельных вычислений, получаемым
при использовании параллельного алгоритма для n
процессоров, по сравнению с последовательным
вариантом выполнения вычислений называется величина:
где Т(1) – время исполнения алгоритма на одном
процессоре,
T(n) – время исполнения параллельного алгоритма на
n процессорах.
17

18.

Метрики параллельной обработки информации
Эффективностью n-процессорной ПВС
называется величина:
E(n) = S(n) / n,
т.е. ускорение, приходящееся на один процессор
Величина эффективности определяет среднюю долю
времени выполнения параллельного алгоритма, в
течение которого процессоры реально используются
для решения задачи
18

19.

Метрики параллельной обработки информации
Утилизация учитывает вклад каждого
процессора при параллельном вычислении
в виде количества операций, выполненных
процессором в единицу времени.
Избыточность – отношение объема
параллельных вычислений к объему
эквивалентных
последовательных
вычислений:
Сжатие
–
избыточности:
величина,
обратная
19

20.

Метрики параллельной обработки информации
20
Избыточность и сжатие характеризуют
эффективность параллельных вычислений путем
сравнения объема вычислений, выполненного при
параллельном и последовательном решении задачи.
Утилизация может быть выражена через метрики
избыточности и эффективности
здесь учитывается соотношение T(1) = O(1).

21.

Метрики параллельной обработки информации
Качество – метрика, связывающая метрики
ускорения, эффективности и сжатия.
Качество является более объективным показателем
улучшения производительности за счет параллельных
вычислений.
21

22.

Метрики параллельной обработки информации
22
Стоимость вычислений – произведение
количества процессоров на время параллельной
обработки.
Стоимостно-оптимальный параллельный метод
обработки информации – метод, стоимость которого
является
пропорциональной
времени
выполнения
наилучшего последовательного алгоритма.

23.

Закономерности параллельной обработки информации
!
23
На практике не удается добиться
увеличения
производительности
прямо
пропорционального числу процессоров
Варианты использования
вычислительной мощности ВС при
увеличения числа процессоров
1
2
Объем вычислений не изменяется.
Цель расширения ВС — сократить
время вычислений.
Время вычислений с расширением
системы не меняется, но при этом
увеличивается объем решаемой задачи.
Цель – за заданное время выполнить
максимальный объем вычислений.
закон
Амдала
закон
Густафсона

24.

Закономерности параллельной обработки информации
Законы параллельных вычислений определяют
зависимость ускорения от количества процессоров и
свойств алгоритма задачи.
свойства алгоритма
f - доля операций, которые должны выполняться
последовательно (одним из процессоров)
0≤f≤1
f = 0 - полностью распараллеливаемая программа
f = 1 - полностью последовательная программа
последовательная часть ts
распараллеливаемая часть tp
программа
24

25.

Закономерности параллельной обработки информации
Закон Амдала
25

26.

Закономерности параллельной обработки информации
26
Закон Амдала
Ускорение для n-процессорной вычислительной системы:
S = T(1) / T(n),
Время параллельного выполнения задачи:
(1 f ) T (1)
T (n) f T (1)
n
T (1)
n
S ( n)
T (n) 1 (n 1) f
закон Амдала
Пример. Если в программе 10% последовательных операций (f=0,1),
то сколько бы процессоров не использовалось, принципиально
невозможно получить ускорение более, чем в 10 раз.

27.

Закономерности параллельной обработки информации
Закон Амдала
Зависимость коэффициента
ускорения от числа процессоров
Зависимость коэффициента
ускорения от доли
последовательных операций
программы
27

28.

Закономерности параллельной обработки информации
Закон Густавсона
1 процессор
n процессоров
28

29.

Закономерности параллельной обработки информации
Закон Густавсона
Для оценивания возможности ускорения вычислений,
когда их объем увеличивается с ростом количества
процессоров в системе (при постоянстве общего времени
вычислений), используется закон ГУСТАВСОНА:
Выражение известно как закон масштабируемого
ускорения или закон Густавсона
(иногда называют закон Густавсона-Барсиса)
29

30.

Учебный вопрос № 3
Способы высокопроизводительной
обработки информации
30

31.

Конвейерная обработка информации
Идея конвейеризации вычислений состоит разбиении
сложной операции на множество более простых, которые
могут выполняться одновременно
При движении объектов по конвейеру на разных его участках
выполняются разные операции, а при достижении каждым объектом
конца конвейера он окажется полностью обработанным
структура конвейера
31

32.

Конвейерная обработка информации
32
Принципы конвейерной обработки
Выполнение каждой команды складывается из
ряда последовательных этапов (шагов, стадий,
ступеней), суть которых от команды к команде не
меняется
В каждый момент времени процессор работает над
различными стадиями выполнения нескольких
команд, причем на выполнение каждой стадии
выделяются отдельные аппаратные ресурсы
команда 1
ступень 1
ступень 2
ступень 3
…
ступень 2
ступень 3
ступень N
команда 2
ступень 1
…
ступень N

33.

Конвейерная обработка информации
Выполнение команд в пятиступенчатом конвейере
Ступени конвейера:
1. IF (Instruction Fetch) - считывание команды в
процессор;
2. ID (Instruction Decoding) - декодирование команды;
3. OR (Operand Reading) - считывание операндов;
4. EX (Executing) - выполнение команды;
5. WB (Write Back) - запись результата.
33

34.

Конвейерная обработка информации
34
Пример расчета времени работы конвейера
Пусть для выполнения отдельных стадий обработки
требуются следующие затраты времени (в усл. ед.):
TIF = 20, TID = 15, TOR = 20, TEX = 25, TWB = 20.
Тогда, предполагая, что дополнительные расходы времени
составляют dt = 5 единиц, получим время такта:
T = max {TIF, TID, TOR, TEX, TWB} + dt = 30.
При последовательной обработке время выполнения N
команд составит:
Tпосл = N*(TIF + TID + TOR + TEX + TWB) = 100N.
При конвейерной обработке после получения результата
выполнения первой команды, результат очередной команды
появляется в следующем такте работы процессора.
Следовательно, Tконв = 5T + (N-1) · T = T· (N+4).

35.

Конвейерная обработка информации
Время работы конвейера
Количество
команд
Время
последовательного
выполнения
конвейерного
выполнения
1
100
150
2
200
180
10
1000
420
100
10000
3120
При
длительной
работе
конвейера
его
быстродействие будет существенно превышать
быстродействие,
достигаемое
при
последовательной обработке команд.
Это увеличение возрастает с сокращением
длительности такта конвейера и ростом
количества выполненных команд.
35

36.

Метрики конвейерной обработки информации
36
1.Ускорение – отношение времени обработки
без конвейера ко времени при наличии конвейера.
Теоретически наилучшее время обработки входного потока из N
значений на конвейере с K ступенями и тактовым периодом Тк
определяется выражением:
T NK ( K N 1) T к
Ускорение S вычислений за счет их конвейеризации
NK T K
NK
S
( K N 1) T K K N 1
!
При N→∞ ускорение стремится к величине, равной
количеству ступеней в конвейере.

37.

Метрики конвейерной обработки информации
37
2. Эффективность конвейера –
доля ускорения, приходящаяся на
одну ступень конвейера
S
N
E
K K N 1
3. Пропускная способность или
производительность Р –
эффективность, деленная на
длительность тактового периода
N
P
T K ( K N 1)
При N→∞ эффективность стремится к
единице, а производительность – к
частоте тактирования конвейера:
F
1
TK

38.

Конвейерная обработка информации
38
Количество подопераций (ступеней) называют
глубиной конвейера
Данные, подаваемые в конвейер, должны быть
независимыми.
Если очередной операнд зависит от результата
предыдущей операции, возникают периоды простоя в
работе конвейера ("пузыри")
Команда 1
результат
ЯП
операнд
Команда 2
команда 1
IF
ID
OR
EX
WR
OR
EX
команда 2
IF
ID
WR

39.

Конвейерная обработка информации
39
КОНФЛИКТЫ - ситуации в конвейерной обработке,
которые препятствуют выполнению очередной команды в
предназначенном для нее такте
Конфликты делятся на три группы:
1) структурные, 2) по управлению, 3) по данным
Структурные конфликты возникают в том случае, когда
аппаратные средства процессора не могут поддерживать все
возможные комбинации команд в режиме одновременного
выполнения с совмещением
Конфликты по управлению возникают при конвейеризации команд
переходов и других команд, изменяющих значение счетчика команд
Конфликты по данным возникают в случаях, когда выполнение
одной команды зависит от результата выполнения предыдущей
команды

40.

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

41.

Конвейерная обработка информации
Длина конвейера команд в популярных
микропроцессорах
Тип микропроцессора
Количество ступеней в
конвейере команд
MIPS R4400
UltraSPARC I
Pentium III
Itanium
UltraSPARC III
Pentium IV Willamette
Pentium IV Prescott
Intel Core
8
9
10
10
14
22
31
14
(K>6)
41

42.

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

43.

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

44.

Суперскалярная обработка информации
44
Суперскалярная
обработка
обработка
с
многопотоковым конвейером команд, при которой
процессор может выполнять больше одной команды за такт
В суперскалярном процессоре последовательный поток команд
исходной программы преобразуется в
несколько параллельных
потоков, проходящих через несколько исполнительных устройств
К1
К3
Конвейер 1
ФБ 1
К1
К2
К2 … Кm
последовательный
поток команд
Конвейер 2
…
…
К4
Кm
программа
параллельные
потоки команд
ФБ 2
Конвейер N
ФБ k
Память (регистры)
К1
К2
К3
К4
…
Кm
исполнительные
устройства

45.

Суперскалярная обработка информации
45
В суперскалярных процессорах одновременная работа нескольких
конвейеров создает проблему последовательности поступления команд
на исполнение и проблему последовательности завершения команд
проблемы
1
2
неупорядоченная выдача команд - очередность выдачи
декодированных команд на исполнительные блоки отличается
от последовательности, предписанной программой
конфликт по функциональному блоку (структурный
конфликт) - на один ФБ претендуют несколько команд,
поступивших из разных конвейеров
Недостаток суперскалярных микропроцессоров:
необходимость синхронного продвижения команд в
каждом из конвейеров

46.

Суперскалярная обработка информации
46

47.

VLIW - обработка информации
VLIW (very long instruction word) — архитектура
процессоров с несколькими вычислительными
устройствами, одновременно исполняющими
одну команду, содержащую несколько операций
47

48.

VLIW - обработка информации
48
Идея VLIW базируется на том, что задача эффективного
планирования параллельного выполнения нескольких
команд возлагается на «разумный» компилятор.
1
компилятор исследует исходную программу с целью
обнаружить все команды, которые могут быть выполнены
одновременно, причем так, чтобы это не приводило к
возникновению конфликтов
2
компилятор пытается объединить такие команды в пакеты,
каждый из которых рассматривается так одна сверхдлинная
команда
3
каждое поле сверхдлинной команды отображается на свой
функциональный блок, который исполняет простую команду
VLIW-архитектура - статическая суперскалярная архитектура,
в которой распараллеливание кода производится на этапе
компиляции, а не динамически во время исполнения

49.

49
1) Устранение компилятором зависимости между командами
до их выполнения.
2) Отсутствие зависимостей между командами ведет к
упрощению
аппаратных
средств
процессора
и
к
существенному подъему его быстродействия.
3) Наличие
множества
функциональных
блоков
дает
возможность выполнять несколько команд параллельно.
1) Требуются
компиляторы,
способные
анализировать
программу, искать в ней независимые команды, связывать такие
команды в строки длиной 256 - 1024 бит, обеспечить их
параллельное выполнение.
2) Компилятор должен учитывать конкретные детали аппаратных
средств.
3) При определенных ситуациях программа оказывается
недостаточно гибкой.
НЕДОСТАТКИ
ПРЕИМУЩЕСТВА
Особенности VLIW - систем

50.

Примеры процессоров с VLIW - архитектурой
сигнальные процессоры TMS320C6x
(Texas Instruments)
процессор Crusoe (Transmeta)
процессоры с архитектурой IA-64
(Intel Itanium)
процессоры Эльбрус-2000 (Е2к, Россия)
50

51.

ВC с явным параллелизмом команд (EPIC)
51
EPIC ( Explicitly Parallel Instruction Computing) - архитектура
IA-64 - усовершенствованный вариант технологии VLIW
Команда 2
Команда 1
Команда 0
Шаблон
27 26
21 20
14 13
7 8
39
Код
операции
Предикат
РОН
операнда 1
РОН
операнда 2
0
РОН
результата
АРХИТЕКТУРА IA-64
128 64-разрядных регистров общего назначения (РОН)
128 80-разрядных регистров с плавающей запятой
64 однобитовых регистров предикатов
Варианты составления связки команд
К1 || К2 || К3
К1 & К2 || К3
К1 || К2 & К3
К1 & К 2 & К3

52.

ВC с явным параллелизмом команд (EPIC)
52
Предикация ‒ способ обработки условных ветвлений.
при которой компилятор указывает, что обе ветви
выполняются на процессоре параллельно
1
Если в программе встречается условное ветвление, то команды
из разных ветвей помечаются разными регистрами предиката
(РП), далее они выполняются совместно, но их результаты не
записываются, пока значения РП не определены.
2
3
Когда вычисляется условие ветвления, РП,
соответствующий
«правильной»
ветви,
устанавливается в 1, а другой ‒ в 0.
Перед записью результатов процессор проверяет поле предиката
и записывает результаты только тех команд, поле предиката
которых указывает на РП с единичным значением

53.

ОСОБЕННОСТИ АРХИТЕКТУРЫ EPIC
53
1) большое количество регистров;
2) масштабируемость архитектуры до большого
количества функциональных блоков;
3) явный параллелизм в машинном коде — поиск
зависимостей между командами осуществляет
не процессор, а компилятор;
4) предикация — команды из разных ветвей
условного предложения снабжаются полями
предикатов и запускаются параллельно
5) предварительная
загрузка:
данные
из
медленной основной памяти загружаются
заранее

54.

ЗАКЛЮЧЕНИЕ
54
Два основных типа архитектур
современных процессоров
Суперскалярные
С широким
командным словом
динамическая
статическая
Кто планирует
выполнение
команд
аппаратура во время
выполнения программы
компилятор до
выполнения программы
Недостаток
сложность аппаратуры
слабая мобильность ПО,
сложный компилятор
Достоинство
высокая мобильность и
простота ПО
высокая
производительность
Примеры
архитектур
SPARC
Эльбрус
Тип
компиляции
программ

55.

Задание на самостоятельную работу
Задание:
1. Повторить материал лекции по конспекту
2. Изучить рекомендованную литературу [3, с.23-36],
[4, с.450-462];
Ответить на следующие вопросы:
в
каком
случае
параллельная
обработка
информации не дает ускорения?;
в каких диапазонах изменяются значения метрик
«ускорение» и «эффективность»?;
какое количество команд необходимо подать на
вход пятиступенчатого конвейера для достижения им
ускорения 4,5?
55