5 Микроанализ производительности вычислительных систем: Пер. с англ./Под ред. В. В. Мартынюка. — М.: Радио и связь, 1983. — 360 с., ил.
В пер.: 2 р.
Дается описание большой группы методов исследования производительности и эффективности вычислительных систем. Примененный в книге общий подход, основанный на использовании аналитических методов, определяется автором как микроанализ. Рассматриваются структуры, принцип действия и организация современных микро-ЭВМ.
Для широкого круга специалистов, занимающихся конструированием ЭВМ и использованием современных микро-ЭВМ в составе различных автоматических систем.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В настоящее время в связи с обилием разнообразной вычислительной техники для ее потенциальных пользователей весьма актуальной становится задача квалифицированной оценки производительности тех или иных ЭВМ применительно к конкретным видам прикладной деятельности с учетом стоимости вычислительного обслуживания. Поэтому разработчикам новых средств вычислительной техники приходится уделять особое внимание производительности и добиваться ее оптимизации еще до создания работающих макетов, прибегая обычно к различным методам аналитического моделирования.
Предлагаемая книга является подробным руководством по оценке производительности аппаратного и программного обеспечения мини- и микро-ЭВМ аналитическими методами и предназначена для специалистов по вычислительной технике, а также может использоваться как пособие для студентов соответствующих специальностей.
Автор книги Б. Байцер уже известен советским читателям по опубликованной в 1974 г. в издательстве «Ми,р» двухтомной монографии «Архитектура вычислительных комплексов». Присущий ему стиль изложения характеризуется живостью и непринужденностью, хотя иногда и перегружен рассуждениями общего характера.
В предлагаемой книге, сознательно сводя к минимуму формальные обоснования описываемых методов, автор часто облекает их в форму полезных практических, советов и предостережений о том, как избежать распространенных ошибок. Следует заметить, что не все даваемые автором рекомендации представляются бесспорными, однако, как правилр, они верно отражают существо дела. Часто встречающиеся по ходу изложения шутливые замечания, приправленные в оригинале изрядной дозой сленга, накладывают на книгу своеобразный отпечаток. Читателю следует иметь в виду, что среди контрольных задач, приводимых в конце каждой главы, попадаются и шуточные, нацеленные, по-видимому, на проверку того, насколько читатель сохранил чувство здравого смысла и юмора.
Несмотря на присущую ей некоторую поверхностность, данная книга знакомит читателей с различными аспектами анализа производительности небольших вычислительных систем в том объеме, который во многих случаях может оказаться достаточным. Тем _ читателям, которым потребуется более глубокое и систематическое освоение материала, мы рекомендуем обратиться также К монографий Д. Феррари «Оценка производительности вычисли-гельных систем», опубликованной в издательстве «Мир» в 1981 г. 5ля удобства параллельного изучения приняты меры по терминологическому согласованию переводов этих двух книг.
В приложении стандартные программы статистических расче-'ов воспроизводятся без изменений, поскольку они предназнача-
S
СОДЕРЖАНИЕ
Стр.
Предисловие редактора перевода ...... . ....... ^
Предисловие автора ....... . • • • • • • • • • *
1. ВВЕДЕНИЕ ........... - ...... ?
К Обзор содержания книги ....... ...... 6
1.1. Анализ производительности (6). 1.2. Введение (6). 1.3. Временной анализ (7). 1.4. Системный анализ (7): 1.5. Заключение (7)
2. Анализ производительности . . . ......... °
2.1. Почему необходим анализ (8). 2.2. Кто анализирует (8). 2.3. Результаты анализа (9). 2.4. Модели и их построение (9). 2.5. Целесообразность анализа (10). 2.6. Методы оценки производительности (12). 2.7. Обзор предложенного подхода (14)
2. СТРУКТУРА, РЕСУРСЫ И ПРИМЕНЕНИЕ ЭВМ ...... . . 14
1. Краткий обзор .... ^_ .......... 1*
2. Типичная ЭВМ ......... ...... "
2.1. Общие замечания (14). 2.2. Магистраль (15). 2.3. ПЗУ (15). 2.4. ОЗУ (16). 2.5. Адаптер ПДП (16). 2.6. Устройства (t7). 2.7. АЛУ (17). 2.8. Прерывания (17). 2.9. Пря-
мые каналы. (18) •
3. Ресурсы ................. ч*
3.1. Что такое ресурс (18). 3.2. Потребление ресурса, относительная потребность, коэффициент использования и эффективность (19). 3.3. Характеристики ресурсов (23) -
4. Уточнение целей- ............... 24
5. Упражнения , . ....... ....... 25
3. ПАРАМЕТРЫ И МЕРЫ ПРОИЗВОДИТЕЛЬНОСТИ ....... 26
1. Краткий обзор .......... ...... 26
2. Статистический подход ............. 26
3. Определение пропускной способности .......... 27
3.1. Транзакции (27). 3.2. Одновременные транзакции (29). 3.3. Различные типы транзакций (29). 3.4. Упрощающие допущения (30). 3.5. Заключение (31)
4. Задачи и транзакции ... ........ ... 32
4.1. Определения (32). 4.2. Пример (33). 4.3. Сравнение блок-схем транзакции и процесса (35). 4.4. Зачем нужна блок-схема транзакции (36)
5. Задержка, задержка, задержка и еще раз задержка ....... 37
5.1. Какая задержка имеется в виду (37). 5.2.' Входные задержки (37). 5.3. Выходные задержки (37). 5.4. Странные задержки (38). 5.5. Задержки из-за внешней перегруженности (38). 5.6. Время обработки, задержка обработки, задержка (38). 5.7. Заключение (39)
в. Зависимость пропускной способности от задержки . . . . . . '39
6.1. Пропускная способность и задержка (39). 6.2. Что ожидает пользователь (40).
6.3. Игры в «кошки-мышки» (41). 6.4. Семейство кривых пропускная способность — задержка (42). 6.5. Согласование реальных и идеальных спецификаций (42)
- 7. Объективная и субъективная интенсивности . . ...... 44
7.1. Общее представление (44). 72. Упрощенная модель задержки (46). 7.3. Разъяснение (47). 7.4. Многоресурсность (47)
8. Снова о производительности ............ 43
8.1. Как достичь желаемой производительности (48) . 8.2. Уточнение целей анализа (48)
9. Заключение .......... ...... <ч
10. Упражнения ......... ........ 50
4. ПРЕДВАРИТЕЛЬНЫЙ ПРИБЛИЖЕННЫЙ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ 51
1. Краткий обзор . . ........... . . 51
2. Обзор аналитического процесса . . ..... . . . . . 51
2.1. Идеальный случай (51). 2.2. Реальный случай (51). 2.3. Аппаратное и программ-
ное обеспечение (52)
8. Некоторые «плохие* методики . . . ........ 54
3.1. Общие замечания (54). 3.2. Смеси команд (54). 3.3. Эталонные программы (55).
3.4. Экстраполяция от изученных систем (56). 3.5. Вера, надежда и милосердие (57)
4. Оценка времени обработки . ........... 57
4.1. Общие замечания (57). 4.2. С-чего начать (57). 4.3. Как получить время обработ-
ки (62). 4.4. Некоторые советы и предостережения (64). ,4.5. Подпрограммы и подпроцессы (65)
5. «Кирпичная стена» н другие приближенные опенки ....... 66
5.1. Границы (66). 5.2. «Кирпичная . стена» (67). 5.3. Несколько более удобная сте-
на (68). 5.4-. Некоторые менее идеальные системы (69). 5.5. Несколько ресурсов (71)
в. Анализ для худшего и лучшего случаев . ...... 71
6.1. Обоснование (71). 6.2. Принципы (72). 6.3. Худший из худших и лучший из лучших (72). 6.4. Некоторые предостережения (73). 6.5. Насколько хорошо и насколько
• плохо (73)
7. Упражнения ........ ........ 74
Б. СТАТИСТИЧЕСКИЙ АНАЛИЗ ВРЕМЕНИ ОБРАБОТКИ И ДРУГИХ РЕСУРСОВ 76
1. Идея . ... . ..... . . ; ...... 76
2. Каким образом . ...... . ....... 76
3. Некоторые определения ....... ...... 77
3.1. Что такое блок-схема (77). 3.2. Процессы (77). 3.3. Выбор реи-.-ния (78). 3.4. Примечания (78). 3.5. ВероятнФсти (78)
357
. - --------~г..ю~ j "trvMtt^anH ......... 1 7*9
4.1. Последовательные процессы (79). 4.2. Последовательные сочленения (79). 4.3. Расщепление сочленений (79). 4.4. Последовательные выборы решений (80). 4.5. Слияние сочленений и выборов решений (80). 4.6. Сочленения и процессы (81). 4.7. Выборы решений (82)
5. Простой анализ............... 82
5.1. Общие замечания (82). _5.2. _Правило последовательных связей 182) B.S Ппзпптш
. .. аелных связе ). 5.3. Правило
параллельных связей (83). 5.4. Правило цикла (83). 5.5. Пример (83). 5.6. Заключение (85). 5.7. Некоторые практические приемы и рекомендации (86)
6. Числа, параметры и алгебраические выражения........ 87
6.1. Зачем нужны параметры (87). 6.2. Как сократить число параметров и как работать с ними (87.). 6.3. Численные и алгебраические результаты. Проблемы (89).
6.4. Обратная сторона медали (89)
7. Упражнения................ д$
6. ДРУГОЙ ПОДХОД К РАССМОТРЕНИЮ БЛОК-СХЕМ ТРАНЗАКЦИИ И ПРОЦЕССОВ................. 9!
'1. Краткий обзор............... 91
2. Блок-схемы транзакций и процессов как многоресурсные модели . . . 91 2,1. Общие замечания (91). 2.2. Процедуры (92). 2.3. Учет действий (93)
3. Особые замечания об анализе............ 93
3.1. Время выполнения команды и время доступа к памяти (93). 3.2. Канал (95).
3.3. Запросы на буфер и очередь (95). 3.4. Операции ввода — вывода и прерывания (97)
4. Анализ задержки в рамках более полной блок-схемы транзакции . . . 98, 4.1. Блок-схема транзакции как модель задержки (98). 4.2. Еще одна модель (99).
4.3. Обсуждение модели (100). 4.4. Упрощение процесса (101). 4.5. Смешанные модели (103)
5. Упражнения.................103
7. ГРАНИЦЫ И ВОЗМОЖНОСТИ АНАЛИТИЧЕСКИХ МЕТОДОВ.....104
1. Краткий обзор............... 104
2. Вероятности и способы их определения ...... .* . . 104
2.1. Проблема (104). 2.2. Вероятности, зависящие от типа транзакции (106). 2.3. Признаки типов транзакций (108). 2.4. Вероятности, зависящие от характеристик транзакции (109). 2.5. Вероятности, определяемые размером пакета (110). 2.6. Вероятности, зависящие от длины очереди (111). 2.7. Переключатели управления процессами (114)
3. Процедуры разворачивания блок-схемы . . . . . . . . 114'
3.1. Зачем, как и когда (114). 3.2. Дальнейшие аналитические эквиваленты (116). 3.3. Когда больше ничего не. остается (Н7)
4. Проверка на значимость............ .119
4.1. Назначение (118). 4.2. Принцип определения (118). 4.3. С чего начать (11.8). 4.4. Функциональные вероятности (119). 4.5. Другие приемы упрощения алгебраических выражений (120)
5. Контроль подмодели.............. 121
5.1. Зачем нужны подмодели (121). 5.2. Принципы и практика (121)
6. Моменты более высокого порядка..........123
6.1. Общие замечания (123). 6.2. Правила для стандартного отклонения (124). 6.3. Природа окончательного распределения (125). 6.4. Предостережение (126)
7. Упражнения.............., . 126
8. УПРОЩЕННЫЙ АНАЛИЗ.............128
1. Краткий обзор............... 128
2. Матричное представление блок-схемы . . . . . . . . . . 128
3. Алгоритм упрощения . . . . ........ . . 130
3.1. Общее описание процедуры (130). 3.2. Исключение узла с применением уравнений перекрестных членов (130). 3.3. Объединение параллельных связей (133). 3.4. Исключение циклов (134). 3.5. Завершение анализа блок-схемы (134)
4. Некоторые практические советы.....(..... 137
5. Связи и функции........... .''.'. . . 141
6. Аналитическая основа .......... . . . 141
7. Упражнения........... .'...,. 142 ч
9. ПРЕРЫВАНИЯ, ПДП и замедление........... 142
1. Краткий обзор . . . . . j...... j . -. 142
2. Что^ такое замедление.............. 142
3. Источники замедления...........".'.*' 143
3.1. Общие замечания (143). 3.2. Соперничество за память (143). 3.3. Соперничество
за ЦП (144). 3.4. Соперничество за магистраль (146). 3.5. Соперничество за канал (148)
4.. Замедление и соперничество на символьном уровне . . . . . . 148
4.1. Предварительные условия (148). 4,2. Буферизация (148). 4.3. Синхронные источники (149). 4.4. Источники с некратными интенсивностями (149). 4.5. Асинхронные запросы (150) х
5. Замедление' при исчерпывании ресурса.........150
5.1, Принципы (150). 5.2. Иерархия приоритетов (151). 5.3. Типичные структуры приоритетов (151)
6. Замедление высокого порядка........... 153
6.1. Характеристики и примеры (153). 6;2. Смешанные замедления (154) . J
7. Локальное и глобальное замедление . . ..,,.,.« 156 358
Стр.
7.1. Общие замечания (155). 7.2. Локальное замедление в сравнении с глобальным (155). 7.3. Проблема распределения замедления (157). 7.4. Как решается Проблема распределения замедления (158)
8. Ретроспективный взгляд на замедление.........[5»
9. Упражнения . . ...............16°
10. ВНЕШНИЕ УСТРОЙСТВА, ЗАПАЗДЫВАНИЕ И ПЛАНИРОВАНИЕ ... 161
1. Краткий обзор...............}<»
2. Основные концепции.......• •„•.,• • • •
2.1. Физические и экономические аспекты запаздывания (161). 2.2. Как уменьшать запаздывание (162). 2.3. Пространственные свойства доступа и поведение устройств (163). 2.4. Факторы запаздывания (166) ' _
3. Ленточные запоминающие устройства — линейные устройства .... 167 3.1. Механика (167). 3.2. Задача о запаздывании (168). 3.3. Задачи о перемотке (168).
3.4. Другие устройства с линейным доступом (170)
4. Барабан.................170
4.1. Общие соображения и состояние вопроса. (170). 4.2. Последовательный страничный и файловый барабаны (171). 4.3. .Пакетный страничный барабан без планирования (172). 4.4. Пакетный страничный барабан с планированием (172). 4.5. Барабан с непрерывным потоком задач (175) • .__
5. Диск..................'177
5.1. Общая характеристика (177). 5.2. Последовательный диск (179). 5.3. Непланируемый пакетный страничный диск (180). 5.4. Планируемый страничный пакетный
диск (180). 5.5. Диск с непрерывным поступлением задач (183)
в. Упражнения................185
И. ТЕОРИЯ ОЧЕРЕДЕЙ И СМЕЖНЫЕ ВОПРОСЫ........187
1. Краткий обзор...............187
2. Похвальное слово теории.............187
3. Основные понятия и обозначения...........188
3.1. Общие понятия (188). 3.2. Обозначения (189). 3.3. Функции и распределения плотностей вероятностей интервалов времени между двумя появлениями клиентов (190). 3.4. Распределение времени обслуживания (193). 3.5. Дисциплина в очереди (194). 3.6. Альтернатива: дискретная или непрерывная модель (194). 3.7. Пояснения к сводной таблице распределений (195). 3.8. Общеупотребительные формулы
и обозначения (195)
4. Системы с одним обслуживающим прибором...... . . 201
4.1. Системы типа (Af/G/1)—(M/G/1) : (G//°o/°o) (201). 4.2. Очереди типа (M/Af/1) — (M/Af/l) : (G//OO/OO) <203). 4.3. Очереди типа (G//G/1) :-(G//°°/°°) (204). 4.4. Другие простые системы с одним обслуживающим прибором (205)
5. Очереди с несколькими обслуживающими приборами ...... 205
5.1. Общие замечания (205). 5.2. Системы типа (М/М/с) : (G//OO/OO) (206). 5.3. Системы типа (MIMfc) : (G//W°°) (206)
р. Очереди с приоритетами.............207
6.1. Общие замечания (207). 6.2. Система (Af/G/1) : (NPRE/oo/oo) (208). 6.3. Система (Af/G/1) : (PRER/oo/oo) (209). 6.4. Комментарий (209)
7. Сетевые системы массового обслуживания .........209
7.1. Общие замечания (209). 7.2. Простейшие модели и допущения (212). 7.3. Уточнения (215)
8. Упражнения................ 216
12. АНАЛИЗ ЦИКЛИЧЕСКИХ СИСТЕМ........... 218
1. Краткий обзор...............218
2. Циклические системы . ............. 218
2.1. Первоначальное представление (218). 2.2. Работа системы и ее поведение (219).
2.3. Примеры циклических систем (220). 2.4. Сравнение циклических и ациклических систем (221). 2.5. Какие системы можно считать циклическими (223)
3. Анализ циклических систем — первый этап анализа ....... 224
3.1. Процедура (224). 3.2. Диаграмма цикла (224). 3.3. Прерывания, устройства прямого доступа и замедление (226). 3.4. Запаздывания ввода —вывода и другие зависимости (227). 3.5. Порядок процессов во времени (228)-
4. Вывод уравнения цикла—второй этап анализа...... . ' ?30
4.1. Начало цикла (230). 4.2. Уравнение цикла (232). 4.3. Вероятности, зависящие
от нагрузки системы (234). 4,4. Общий вид уравнения цикла (234)
5. Решение уравнения . . ............ 235
5.1. План процедуры (235). 5.2. Точка нулевой нагрузки (236). 5.3. Точки отказа (236). 5.4. Приближенная квазиидеальная модель (236). 5.5. Решение полиномиального уравнения методом Ньютона — Рафсона (237). 5.6. Построение всей кривой (238). 5.7. Побочные решения (240). 5.8. Распределение замедления (240)
6. Определение задержек............ 241
7. Другие ресурсы............ 243
8. Псевдоциклические системы............. 244
9. Упражнения . . . . . . . . . . ,.....245
13. АНАЛИЗ АСИНХРОННЫХ СИСТЕМ ..''.' 246
1. Краткий обзор.............' . . 246
2. Перспективный взгляд на асинхронные системы . . . . ! . '. 246 2.1. Области приложений и общая характеристика (246). 2.2. Сопоставление открытых и замкнутых сетей (247)
3. Базисная модель....... . ^ 249
3.1. Обзор процедуры (249). 3.2. Модель, ограничения и тяжкий груз проблем (249).
. 359
Стр.
3.3. Задачи, транзакции и ста-бильность потоков (251)
- 4. Процедура...... . . . . ... . . . . . 253
4.1. Первый шаг — разработка вспомогательных моделей (253)., 4.2. Второй шаг — решение уравнений баланса потоков (253). 4.3. Третий шаг —агрегаты вспомогательных моделей (254). 4.4. Четвертый и шестой шаги (255). 4.5. Пятый шаг (255)
5. Мультипрноритетные модели . .' -. . . ....... 256
5.1. Общие замечания (256). 5.2. Высокоприоритетные функции, замедление и глобальное замедление (257). 5.3. Разделимость уровней (258). 5.4. Анализ (259)
6. Коэффициент использования в сопоставлении с запросами и пригодность модели.................259
7. Упражнения .................260
14. ИСПОЛЬЗОВАНИЕ СТАТИЧЕСКОЙ И ДИНАМИЧЕСКОЙ ПАМЯТИ 264
1. Краткий обзор.......... . . . , 261
2. Сопоставление статической памяти с динамической.......262
2.1. О выборе памяти (262). 2.2. Статическая память (262). 2.3. Динамическая память (262). 2.4. Смешанные случаи '(263)
3. Оценки, для статической памяти...........264
3.1. Общие замечания (264). 3.2. Программная область памяти (264). 3.3. Память для
базы данных и таблиц (265). 3.4. Рабочие области (266). 3.5. Другие области статической памяти (266)
4. Общие принципы оценки динамической памяти.......267
4.1. Краткий обзор (267). 4.2. Анализ блоков очереди (268). 4.3. Реальные и возможные переполнения (269). 4.4. О приемлемости вероятностей (270)
5. Компоненты моделей . . . . .-• --—-........ 272
5.1. Общие замечания (272). 5.2. Число обслуживающих приборов (272). 5.3. Интен-
' сивност'ь поступления запросов (272). 5.4. Интервалы времени обслуживания н удерживания (273). 5.5. Потребность в ресурсах (274) •
6. Модели . . ;..............276
6.1. Общие замечания (276). 6.2. Сопоставление систем с потерей и с задержкой (276). 6.3. Первая модель — В-формула Эрланга (277). 6.4. Вторая модель — формула Пуассона. (277). 6.5. Третья модель — С-формула Эрланга (277). 6.6. Другие модели (278). 6.7. Буферы фиксированной длины (278)
7. О средних...............( . . . 279
8. Сводный обзор...............279
9. Упражнения................281
15. ТЕСТИРОВАНИЕ И ПРОВЕРКА ПРИГОДНОСТИ МОДЕЛЕЙ .... 283
1. Краткий обзор . . .............283
2. Разновидности ошибок . . . . '..........283
. 3. О тестировании на уровне составляющих блоков.......284
4. Тестирование на уровне системы . . .........285
4.1. Общие вопросы (285). 4.2. Особые точки кривой (285). 4.3. Осмысленность и-реалистичность' модели (287). 4.4. О смысле физически нереального поведения модели (288). 4.5. Поведение модели в предельных случаях (289). 4.6. Реакция на из-' менение параметров (290). 4.7. Прочие аспекты поведения модели (290)
. 5. Проверка пригодности модели . . . . - . . .... . • . 291
5.1. Общие принципы (291). 5.2. Тестовая нагрузка (291). 5.3. Измерения (295)
в. Сравнение модели с системой и эмпирические модели.....298
6.1. Общие замечания (298). 6.2. Линейный регрессионный анализ (299). 6.3. Кусочно-линейные приближения (300). 6.4. Преобразование переменных (300). 6.5. Многомерные приближения и устранение артефакта (301). 6.6. Оценка качества приближения (302) -
7. Сравнение.................303
8. Упражнения................ 305
16. НАСТРОЙКА - В ШУТКУ И ВСЕНЬЕЗ . .........306
1. Краткий обзор...............306
2. Настройка................ 306
2.1. Определения и необходимые предпосылки (306). 2.2. Устойчивость системы (307). 2.3. Устойчивость операционной среды (307). 2.4. Цель настройки -(308). 2.5. Полему новые системы плохо настроены (308). '2.6. Что мы называем настройкой (310)
3. Мощность системы и цели настройки..........310
3.1. Определение" понятия мощности системы (316). 3.2. Пересмотренные цели настройки (311). 3.3. Ограничительные ресурсы (313)
4. Диагностика периода настройки........... 314
4.1. Обнаружение простоев' (314). 4.2. Коэффициент единичного использования (316).
4.3. Эмпирическое обследование (318)
5. Процесс настройки.............. 318
5.1. Компромиссы между пропускной способностью и задержками (318). 5.2. Простои (320). 5.3. Команды управления (321). 5.4. Влияние перекрытий (324К 5.5. Открытые и закрытые подпрограммы (325)
6. Гипернастройка............... 325
7. Эксперименты на модели............ . 326
8. Упражнения.................. 326
Приложение I. Статистлческие программы и модели запаздывания. Листинги . . 328
Приложение II. Модели................ 335
Книги из списка литературы, переведенные на русский язык......349
Список литературы' . ...............350
Цена: 150руб.
