- •Организация эвм и систем
- •Содержание
- •Глава 1. Становление и эволюция цифровой вычислительной техники 8
- •Глава 2. Архитектура системы команд 37
- •Глава 3. Программная модель процессора на примере Intel i8086 71
- •Глава 4. Интерфейсы и шины в вычислительной системе 87
- •Глава 5. Системы ввода/вывода. Организация обмена в вычислительной системе 116
- •Глава 6. Основные направления в архитектуре процессоров 129
- •Глава 7. Подсистема памяти 169
- •Глава 8. Внешние накопители 197
- •Глава 9. Основы параллельных вычислений 220
- •Глава 10. Архитектура многопроцессорных систем 237
- •Глава 1. Становление и эволюция цифровой вычислительной техники
- •1.1. Определение понятия «архитектура»
- •1.2. Уровни детализации структуры вычислительной машины
- •1.3. Эволюция средств автоматизации вычислений
- •1.3.1. Нулевое поколение (1492-1945)
- •1.3.2. Первое поколение(1937-1953)
- •1.3.3. Второе поколение (1954-1962)
- •1.3.4. Третье поколение (1963-1972)
- •1.3.5. Четвертое поколение (1972-1984)
- •1.3.6. Пятое поколение (1984-1990)
- •1.3.7. Шестое поколение (1990–)
- •1.4. Концепция машины с хранимой в памяти программой
- •1.4.1. Принцип двоичного кодирования
- •1.4.2. Принцип программного управления
- •1.4.3. Принцип однородности памяти
- •1.4.4. Принцип адресности
- •1.6 Типы структур вычислительных машин и систем
- •1.6.1. Структуры вычислительных машин
- •1.6.2. Структуры вычислительных систем
- •1.6.3. Перспективные направления исследований в области архитектуры
- •Контрольные вопросы
- •Глава 2. Архитектура системы команд
- •2.1. Понятие архитектуры системы команд
- •2.2. Классификация архитектур системы команд
- •2.2.1. Классификация по составу и сложности команд
- •2.2.2. Классификация по месту хранения операндов
- •2.3. Форматы команд
- •2.3.1. Длина команды
- •2.3.2. Разрядность полей команды
- •2.3.3. Количество адресов в команде
- •2.4. Выбор адресности команд
- •2.4.1. Адресность и емкость запоминающего устройства
- •2.4.2. Адресность и время выполнения программы
- •2.4.3. Адресность и эффективность использования памяти
- •2.5. Способы адресации операндов
- •2.5.1. Непосредственная адресация
- •2.5.2. Прямая адресация
- •2.5.3. Косвенная адресация
- •2.5.4. Регистровая адресация
- •2.5.5. Косвенная регистровая адресация
- •2.5.6. Адресация со смещением
- •2.5.7. Относительная адресация
- •2.5.8. Базовая регистровая адресация
- •2.5.9. Индексная адресация
- •2.5.10. Страничная адресация
- •2.6. Цикл команды
- •2.7. Основные показатели вычислительных машин
- •Контрольные вопросы
- •Глава 3. Программная модель процессора на примере Intel i8086
- •3.1. Программная архитектура i80х86
- •3.2. Микропроцессор i8086
- •3.3. Доступ к ячейкам памяти
- •3.4. Команды микропроцессора
- •3.5. Основные группы команд и их краткая характеристика
- •3.6. Способы адресации в архитектуре i80x86
- •Контрольные вопросы
- •Лабораторная работа №1. Программная архитектура процессора i8086
- •Глава 4. Интерфейсы и шины в вычислительной системе
- •4.1. Структура взаимосвязей вычислительной машины
- •4.2. Типы шин
- •4.2.1. Шина «процессор-память»
- •4.2.2. Шина ввода/вывода
- •4.2.3. Системная шина
- •4.3. Иерархия шин
- •4.3.1. Вычислительная машина с одной шиной
- •4.3.2. Вычислительная машина с двумя видами шин
- •4.3.3. Вычислительная машина с тремя видами шин
- •4.4. Физическая реализация шин
- •4.4.1. Механические аспекты
- •4.4.2. Электрические аспекты
- •4.5. Распределение линий шины
- •4.6. Выделенные и мультиплексируемые линии
- •4.7. Арбитраж шин
- •4.7.1. Схемы приоритетов
- •4.7.2. Схемы арбитража
- •4.8. Основные интерфейсы современных вм на базе архитектуры ia-32
- •4.8.1. Интерфейс pci
- •4.8.2. Порт agp
- •4.8.3. Pci Express
- •Глава 5. Системы ввода/вывода. Организация обмена в вычислительной системе
- •5.1. Основные функции модуля ввода-вывода
- •5.1.1. Локализация данных
- •5.1.2. Управление и синхронизация
- •5.1.3. Обмен информацией
- •5.2. Методы управления вводом/выводом
- •5.3. Система прерываний и исключений в архитектуре ia-32
- •5.4. Расширенный программируемый контроллер прерываний (apic)
- •Глава 6. Основные направления в архитектуре процессоров
- •6.1. Конвейеризация вычислений
- •6.1.1. Синхронные линейные конвейеры
- •6.1.2. Метрики эффективности конвейеров
- •6.1.3. Нелинейные конвейеры
- •6.2. Конвейер команд
- •6.3. Конфликты в конвейере команд
- •6.4. Методы решения проблемы условного перехода
- •6.5. Предсказание переходов
- •6.5.1. Статическое предсказание переходов
- •6.5.2. Динамическое предсказание переходов
- •6.6. Суперконвейерные процессоры
- •6.7. Архитектуры с полным и сокращенным набором команд
- •6.8. Основные черты risc-архитектуры
- •6.9. Преимущества и недостатки risc
- •6.10. Суперскалярные процессоры
- •Лабораторная работа №4. Исполнительные устройства вм
- •Глава 7. Подсистема памяти
- •7.1. Характеристики систем памяти
- •7.2. Иерархия запоминающих устройств
- •7.3. Основная память
- •7.4. Блочная организация основной памяти
- •7.5. Организация микросхем памяти
- •7.6. Синхронные и асинхронные запоминающие устройства
- •7.7. Оперативные запоминающие устройства
- •7.8 Статическая и динамическая оперативная память
- •7.9. Статические оперативные запоминающие устройства
- •7.10. Динамические оперативные запоминающие устройства
- •Лабораторная работа №5. Расширенная работа с памятью и передача управления в программе
- •Глава 8. Внешние накопители
- •8.1. Магнитные диски
- •8.1.1. Организация данных и форматирование
- •8.1.2. Внутреннее устройство дисковых систем
- •8.2. Массивы магнитных дисков с избыточностью
- •8.2.1. Концепция массива с избыточностью
- •8.2.2. Повышение производительности дисковой подсистемы
- •8.2.3. Повышение отказоустойчивости дисковой подсистемы
- •8.2.4. Raid уровня 0
- •8.2.5. Raid уровня 1
- •8.2.6. Raid уровня 2
- •8.2.7. Raid уровня 3
- •8.2.8. Raid уровня 4
- •8.2.9. Raid уровня 5
- •8.2.10. Raid уровня 6
- •8.2.11. Raid уровня 7
- •8.2.12. Raid уровня 10
- •8.2.13. Raid уровня 53
- •8.2.14. Особенности реализации raid-систем
- •8.3. Оптическая память
- •Контрольные вопросы
- •Глава 9. Основы параллельных вычислений
- •9.1. Уровни параллелизма
- •9.1.1. Параллелизм уровня задания
- •9.1.2. Параллелизм уровня программ
- •9.1.3. Параллелизм уровня команд
- •9.2. Метрики параллельных вычислений
- •9.2.1. Профиль параллелизма программы
- •9.2.2. Ускорение, эффективность, загрузка и качество
- •9.3. Закон Амдала
- •9.4. Закон Густафсона
- •9.5. Классификация параллельных вычислительных систем. Классификация Флинна
- •Контрольные вопросы
- •Глава 10. Архитектура многопроцессорных систем
- •Классификация многопроцессорных систем
- •Организация коммуникационной среды в системах с разделяемой памятью.
- •Когерентность кэш- памяти в smp- системах.
- •Когерентность кэш- памяти в mpp-системах.
- •Организация прерываний в мультипроцессорных системах.
- •Заключение
- •Библиографический список
9.2.2. Ускорение, эффективность, загрузка и качество
Рассмотрим параллельное выполнение программы со следующими характеристиками:
О(п) — общее число операций (команд), выполненных на п-процессорной системе;
Т(п) — время выполнения O(п) операций на «-процессорной системе в виде числа квантов времени.
В общем случае Т(п) < O(п), если в единицу времени п процессорами выполняется более чем одна команда, где п > 2. Примем, что в однопроцессорной системе T(1) = O(1).
Ускорение (speedup), или точнее, среднее ускорение за счет параллельного выполнения программы — это отношение времени, требуемого для выполнения наилучшего из последовательных алгоритмов на одном процессоре, и времени параллельного вычисления на п процессорах. Без учета коммуникационных издержек ускорение S(n) определяется как
.
Как правило, ускорение удовлетворяет условию S(n) < п.
Эффективность (efficiency) n-процессорной системы — это ускорение на один процессор, определяемое выражением
.
Эффективность обычно отвечает условию 1/п ≤ Е(п) ≤ п. Для более реалистичного описания производительности параллельных вычислений необходимо промоделировать ситуацию, когда параллельный алгоритм может потребовать больше операций, чем его последовательный аналог.
Довольно часто организация вычислений на п процессорах связана с существенными издержками. Поэтому имеет смысл ввести понятие избыточности (redundancy) в виде
.
Это отношение отражает степень соответствия между программным и аппаратным параллелизмом. Очевидно, что 1 < R(n) < п.
Определим еще одно понятие, коэффициент полезного использования или утилизации (utilization), как
.
Тогда можно утверждать, что
и .
Рассмотрим пример. Пусть наилучший из известных последовательных алгоритмов занимает 8с, а параллельный алгоритм занимает на пяти процессорах 2с. Тогда:
S(n) = 8/2 = 4;
E(n) = 4/5 = 0,8;
R(n) = 1/0,8 – 1 = 0,25.
Собственное ускорение определяется путем реализации параллельного алгоритма на одном процессоре.
Если ускорение, достигнутое на п процессорах, равно п, то говорят, что алгоритм показывает линейное ускорение.
В исключительных ситуациях ускорение S(n) может быть больше, чем п. В этих случаях иногда применяют термин суперлинейное ускорение. Данное явление имеет шансы на возникновение в двух следующих случаях:
Последовательная программа может выполняться в очень маленькой памяти, вызывая свопинги (подкачки), или, что менее очевидно, может приводить к большему числу кэш-промахов, чем параллельная версия, где обычно каждая параллельная часть кода выполняется с использованием много меньшего набора данных.
Другая причина повышенного ускорения иллюстрируется примером. Пусть нам нужно выполнить логическую операцию А1 v А2, где как А1, так и А2 имеют значение «Истина» с вероятностью 50%, причем среднее время вычисления Аi, обозначенное как T(Аi), существенно различается в зависимости от того, является ли результат истинным или ложным.
Пусть T(Аi)= 1c для Аi = 1; T(Аi)= 100c для Аi = 0. Теперь получаем четыре равновероятных случая (Т — «истина», F — «ложь», таблица 9).
-
Таблица 9
А1
А2
Последовательный
Параллельный
Т
Т
F
F
Т
F
Т
F
1с + 0
1с + 0
100 с + 1с
100 с +100 с
1 с
1с
1с
100с
∑
303/4с ≈ 76с
103/4с ≈ 26с
Таким образом, параллельные вычисления на двух процессорах ведут к среднему ускорению:
.
Отметим, что суперлинейное ускорение вызвано жесткостью последовательной обработки, так как после вычисления еще нужно проверить A2. К факторам, ограничивающим ускорение, следует отнести:
Программные издержки. Даже если последовательные и параллельные алгоритмы выполняют одни и те же вычисления, параллельным алгоритмам присущи добавочные программные издержки — дополнительные индексные вычисления, неизбежно возникающие из-за декомпозиции данных и распределения их по процессорам; различные виды учетных операций, требуемые в параллельных алгоритмах, но отсутствующие в алгоритмах последовательных.
Издержки из-за дисбаланса загрузки процессоров. Между точками синхронизации каждый из процессоров должен быть загружен одинаковым объемом работы, иначе часть процессоров будет ожидать, пока остальные завершат свои операции. Эта ситуация известна как дисбаланс загрузки. Таким образом, ускорение ограничивается наиболее медленным из процессоров.
Коммуникационные издержки. Если принять, что обмен информацией и вычисления могут перекрываться, то любые коммуникации между процессорами снижают ускорение. В плане коммуникационных затрат важен уровень гранулярности, определяющий объем вычислительной работы, выполняемой между коммуникационными фазами алгоритма. Для уменьшения коммуникационных издержек выгоднее, чтобы вычислительные гранулы были достаточно крупными и доля коммуникаций была меньше.
Еще одним показателем параллельных вычислений служит качество параллельного выполнения программ — характеристика, объединяющая ускорение, эффективность и избыточность. Качество определяется следующим образом:
.
Поскольку как эффективность, так и величина, обратная избыточности, представляют собой дроби, то Q(n) < S(n). Поскольку Е(п) — это всегда дробь, a R(n) — число между 1 и п, качество Q(n) при любых условиях ограничено сверху величиной ускорения S(n).