Модели вычислительной сложности алгоритма

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

· время обработки программы процессором:

,

где q - среднее значение вычислительной сложности (трудоемкости) алгоритма программы с размерностью [q] = экв. операция = ЭО;

В - быстродействие процессора с размерностью [В] = ЭО/С;

· размер рабочей области, занимаемой программой и ее данными в оперативной памяти V_ОЗУ;

· среднее время обращения к ВЗУ за время выполнения программы:

,

где q_Ф - средний объем информации, передаваемый между ОЗУ и ВЗУ при обращении к файлам в ходе выполнения программы, с размерностью [q_Ф] = байт;

t_O – время обращения к ВЗУ для передачи одного байта информации между ОЗУ и ВЗУ

· среднее время ввода информации с дисплея:

t_∂ВЗ = q_∂ВВt_ВИП,

где q_∂ВВ - средний объем информации, вводимой с клавиатуры в ОЗУ и индицируемой на экране дисплея за время выполнения программы, с размерностью [q_∂ВВ] = байт;

t_ВИП - среднее время ввода с клавиатуры, индикации на экране и передачи в ОЗУ одного байта информации;

· среднее время вывода информации на дисплей:

t_∂ = q_∂ф t_ПИ,

где q_∂ф - средний объем информации, передаваемой в дисплейный файл вывода в ходе выполнения программы, с размерностью [q_∂Ф] = байт;

t_ПИ - среднее время передачи из ОЗУ в дисплей и индикации на дисплее одного байта информации;

· среднее время вывода данных на печать: t_n = q_nФt_nδ,

где q_nФ - средний объем информации, передаваемой в файл (буфер) данных, выводимых на печать, с размерностью [q_nФ] = байт;

t_nδ - среднее время передачи и печати одного символа (байта) информации.

При детальном анализе производительности и профиля загрузки устройств ЭВМ и ВС [1] могут потребоваться следующие дополнительные параметры рабочей нагрузки: среднее время ввода информации с перфоленты или перфокарты, или магнитного диска; среднее время обращения к ОЗУ (чаще всего учитывается в составе названного выше параметра υ); среднее время обращения к ПЗУ; среднее время передачи информации по каналу ввода-вывода или по системной шине под управлением контролера прямого доступа в память; среднее время передачи информации через адаптер межпроцессорной связи, адаптер канал-канал или по логическому каналу связи между прикладными программами в сети ЭВМ или локальной вычислительной сети и т.п.

Значительная часть исходных данных q, q_Ф, q_ВВ, q_∂Ф, q_nФ, требуемых для вычисления параметров рабочей нагрузки, может быть найдена в результате аналитического (теоретического) анализа процессоров случайного функционирования алгоритмов прикладных программ. Случайное функционирование алгоритма моделируется вероятностными цепями Маркова [1-3]. Алгоритм представляется в виде частично взвешенного графа Маркова со следующими тремя видами вершин-операторов:

- функциональный оператор (рис.1а) отображает затраты времени на арифметико-логическое преобразование данных и взвешивается числом эквивалентных операций (ЭО) Ki, требуемых для осуществления названного преобразования:

Ki = ,

где m_i - число операций в данном i -м преобразовании;

t_ij - время выполнения процессором j -й операции в i -м преобразовании;

t_эо - время выполнения базовой эквивалентной операции, в качестве которой выбирается любая короткая операция из системы команд процессора.

Данный тип вершины имеет любое число входов и только один выход;

- оператор ввода-вывода (рис.1б) отображает затраты времени на обращение к определенному файлу с целью передачи (записи или чтения) требуемого по исследуемой программе количества информации l_i. Вершина взвешивается числом l_i в байтах, соответствующим однократному обращению к файлу; имеет любое число входов и только один вход;

а)

б)

в)

г)

2 1

нет да

Рис.1. Условные обозначения вершин операторов Маркова: а) функциональный оператор; б) оператор ввода-вывода; в) оператор перехода; г) модель оператора перехода ГСА.

- оператор перехода (рис.1в) отображает правило выбора одного из возможных путей дальнейшего развития вычислительного процесса в зависимости от значения предиката и диапазонов изменения его аргументов. Он имеет любое число входов и не менее двух выходных дуг, каждая из которых взвешивается вероятностью перехода. Сумма вероятностей по всем выходным дугам должна равняться единице. Для отображения вычислительной сложности предиката используется дополнительный функциональный оператор, включаемый в граф непосредственно перед соответствующим оператором перехода (рис. 1г).

Вероятности переходов определяются свойствами имитируемого предиката, например, если предикат имеет вид:

X < 0 ® да,

X ³ 0 ® нет,

где Х - переменная с диапазоном изменения, найденным путем анализа исследуемой программы, например:

-1 < X < 3,

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

Р₁ = ¼; Р₂ = ¾.

Если предикат применен для формирования программного цикла с параметром N, определяющим число прохождений цикла: N £ 9, то, учитывая, что полная группа случайных событий в данном случае состоит из 10 событий, значения вероятностей переходов для вхождения в цикл и выхода из цикла соответственно равны:

Р₁ = 0,9; Р₂ = 0,1.

Кроме названных вершин-операторов в графе Маркова используются начальная вершина без входов и только одним выходом и конечная вершина с любым числом входов и без выхода.

Алгоритм любой программы может быть представлен в виде графа Маркова. Наиболее наглядный путь его построения состоит в следующем:

- текст моделируемой программы на алгоритмическом языке заменяется эквивалентной блок-схемой, или граф-схемой, ее алгоритма (ГСА);

- каждый арифметический оператор или группа операторов на линейном участке программы заменяется функциональным оператором графа Маркова;

- каждый оператор условного перехода ГСА замещается в графе Маркова оператором, имитирующим затраты времени на вычисление значения предиката, и оператором перехода;

- все процедуры ввода, вывода и обращений к ВЗУ отображаются в графе Маркова соответствующими операторами ввода-вывода.

При допущении, что все вероятности переходов являются постоянными величинами и не зависят от хода выполнения алгоритма в прошлом до данного перехода, процесс выполнения алгоритма может быть представлен в виде марковского дискретного случайного процесса. Если в графе Маркова общее количество вершин равно К, то марковский процесс описывается К состояниями S₁,..., S_К; каждое из которых соответствует событию пребывания в одной из вершин графа: V₁, или V₂,.., или V_К, где Vi – условное обозначение одной вершины графа Маркова. Состояния S₁,..., S_К-1 – невозвратные, S_К – конечное поглощающее состояние.

Описанная марковская модель алгоритма позволяет найти средние значения чисел n₁,..., ni,..., n_k-1, пребывания марковского процесса в невозвратных состояниях S₁,..., S_к-1 как решение следующей системы линейных алгебраических уравнений, описывающих граф Маркова [3]:

n_i = δ_1i + , i = , (1.1)

где Pij - вероятность перехода из вершины j в вершину i;

δ_1i - символ Кронекера, который в общем случае определяется в виде:

δ_ji =

В данной системе уравнений j=1, и поэтому символ δ_1i равен единице только при i= 1, т.е. δ₁₁ = 1. Это соответствует случаю, когда алгоритм начинается с вершины V₁ и поэтому число пребываний в начальном состоянии S₁ сразу же будет равно единице:

n₁ = 1.

В остальных (К-2)-х невозвратных состояниях процесс попадает в i -е состояние Si (в вершину Vi) из других (К-2)-х вершин под номерами

j = 1,..., i-1, i + 1,..., K-1

с вероятностями P_ij. Поэтому, если процесс находился в состоянии Sj в среднем nj раз, то он переходил из состояния S_j в состояние S_i в среднем P_jin_j раз. Тогда для получения среднего числа n_i пребываний процесса в состоянии S_i (вершина V_i) достаточно просуммировать произведения P_jin_j по всем (К-2)-м состояниям S_j, j ¹ i, из которых процесс может перейти в данное состояние Si.

Найденные описанным выше способом средние числа {n_i} пребываний алгоритма в вершинах V₁,..., V_k-1 за один его прогон (транзакцию) позволяют достаточно просто вычислить следующие характеристики его вычислительной сложности [3]:

· среднее число эквивалентных операций, выполняемых за один прогон (транзакцию) алгоритма:

q = ,

где S_ф - подмножество функциональных операторов графа Маркова;

· среднее количество информации, передаваемой между ОЗУ и ВЗУ при обращении к файлу имени F_h за один прогон алгоритма:

q_hФ = , h = ,

где S_h - подмножество вершин ввода-вывода, в которых отображено обращение к файлу F_h;

Н - общее число имен файлов, к которым происходит обращение при выполнении моделируемой программы;

· среднее количество информации, передаваемой при одном обращении к файлу имени F_h:

q_h = .

Порядок системы уравнений (1.1), описывающих реальные алгоритмы, может оказаться достаточно высоким. Поэтому в инженерной практике широко применяются программно-аналитические марковские модели алгоритмов, одна из которых в файле имени "Алгоритм" используется в данной лабораторной работе. Основные задачи пользователя программно-аналитической модели:

- освоение описанной выше методики построения марковских моделей алгоритмов;

- освоение технологии обработки информации программой "Алгоритм";

- подготовка данных для определения на ПЭВМ вычислительной сложности алгоритма;

- интерпретация и обработка результатов вычислений.

3. Порядок выполнения лабораторной работы

3.1. Подготовка исходных данных:

3.1.1. Выбрать одну из стандартных прикладных программ [4]. Для получения достаточно большой вычислительной сложности рекомендуется выбирать программу, содержащую циклы и вложенные подциклы, назначая большое количество итераций.

3.1.2. По тексту программы составить блок-схему (граф-схему) ее алгоритма (ГСА).

3.1.3. Конкретизировать численные значения входных параметров исследуемой стандартной программы. Численные значения параметров циклов следует выбирать достаточно большими для получения вычислительной сложности, целесообразной для обработки исследуемой программы на ЭВМ.

3.1.4. На основании ГСА построить граф Маркова. Пронумеровать его вершины (К-1)-го невозвратных состояний.

3.1.5. Вычислить весовые коэффициенты K_i, L_i, P_ij вершин и дуг переходов. Веса указать в вершинах и на дугах схемы графа Маркова.

3.2. Выполнение расчетов на ПЭВМ:

3.2.1. Загрузить с дискеты и запустить программу "Алгоритм".

3.2.2. Ввести, пользуясь меню программы, параметры графа Маркова. Число вершин К вводить на единицу больше помеченных на графе (К-1)- го невозвратных состояний. При вводе параметров оператора перехода вначале указывается номер соседней вершины графа по направлению перехода, а затем – значение вероятности перехода. Номер последней К- й поглощающей вершины вводить цифрой нуль. Направление перехода к последней К- й поглощающей вершине указывается ее действительным К- тым номером, а при вводе описания этой последней К- й вершины величина ее номера указывается равной нулю.

3.2.3. Выполнить вычисления на ПЭВМ.

3.2.4. Вывести по меню результаты расчетов на экран монитора. Зарегистрировать полученные результаты в рабочей тетради.

3.2.5. Интерпретировать полученные результаты, сравнивая предполагаемые и полученные на ЭВМ числа пребываний {n_i} в вершинах графа Маркова.

3.3. Предъявить преподавателю зарегистрированные результаты и их интерпретацию.

4. Содержание отчета.

4.1. Краткое описание методики составления марковской модели алгоритма прикладной программы.

4.2. Текст на алгоритмическом языке моделируемой прикладной программы. Словесное и математическое описание принципа ее функционирования.

4.3. Блок-схема (ГСА) алгоритма исследуемой программы.

4.4. Схема графа Маркова с указанием номеров и весов его вершин и вероятностей переходов на его дугах. Расчеты значений весов вершин и вероятностей переходов.

4.5. Зарегистрированные результаты вычислений на ПЭВМ и их интерпретация.

4.6. Расчеты основных параметров рабочей нагрузки, создаваемой в ЭВМ исследуемой программой, при параметрах процессора и других устройств, взятых из справочников [5,6].

4.7. Список использованных источников.

5. Контрольные вопросы.

5.1. Что такое рабочая нагрузка вычислительной системы?

5.2. Основные параметры рабочей нагрузки?

5.3. Табличный способ описания рабочей нагрузки многомерного потока входных заданий ВС?

5.4. Как увеличить объем вычислительной работы (загрузку) системы при неизменных параметрах рабочей нагрузки входных заданий?

5.5. Что такое классификация рабочей нагрузки? Зачем она применяется? Как вводится случайный разброс параметров рабочей нагрузки после ее классификации?

5.6. От каких характеристик вычислительной сложности алгоритма и как зависят параметры рабочей нагрузки?

5.7. Почему функционирование алгоритма представляется случайным дискретным процессом?

5.8. При каких допущениях дискретный случайный процесс считается марковским?

5.9. Как вычисляется вес функциональной вершины оператора графа Маркова?

5.10. Как зависят веса выходных дуг вершины-оператора перехода от свойств предиката? Чему равно значение вероятности перехода по выходным дугам функциональных вершин и вершин ввода-вывода?

5.11. Как имитируется в графе Маркова оператор условного перехода ГСА алгоритма?

5.12. Зачем в систему уравнений, описывающих граф Маркова, введен символ Кронекера?

5.13. Почему в системе уравнений, описывающих граф Маркова, суммирование выполняется только по (К-2)-м вершинам, исключая данную i-ю вершину?

5.14. Как, используя результаты марковского моделирования алгоритма программы, вычислить средний объем информации, передаваемой между ОЗУ и ВЗУ за одну транзакцию.

5.15. Как определить размер рабочей области ОЗУ, требуемый для хранения прикладной программы и данных?

Лабораторная работа № 2

ВЫБОР БЫСТРОДЕЙСТВИЯ ПРОЦЕССОРА И ДИСЦИПЛИН

ОБСЛУЖИВАНИЯ ВХОДНЫХ ЗАДАНИЙ

1. ЦЕЛЬ РАБОТЫ

Изучение элементов теории систем массового обслуживания (СМО) и методики ее применения для обоснованного выбора быстродействия процессора, видов и уровней приоритетов заданий во входной очереди. Практическое освоение интерактивного режима работы с программно-аналитической моделью центрального ядра вычислительной системы (ВС) при решении прямой и обратной задач анализа ВС.

2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПРИМЕНЕНИЮ ТЕОРИИ СМО ДЛЯ ОЦЕНКИ ХАРАКТЕРИСТИК ПРОИЗВОДИТЕЛЬНОСТИ ВС

Теория систем массового обслуживания (СМО) – основной математический аппарат, применяемый для аналитического описания случайных процессов функционирования ВС [2, 3]. Случайный характер процессов в ВС обусловлен колебаниями интенсивности потока входных заданий, существенными различиями параметров рабочей нагрузки разных прикладных программ, колебаниями вычислительной сложности алгоритмов программ в зависимости от изменения значений исходных данных. На основе простейших математических моделей ВС в виде СМО получен ряд важных аналитических формул, позволяющих приближенно вычислять характеристики ВС как математические ожидания неслучайных характеристик случайных величин. Для анализа поведения ВС при вариации функций распределения в широком диапазоне, названные формулы выведены в теории СМО для трех видов стандартных законов распределения случайных величин:

- экспоненциального ,

,

с плотностью распределения ,

,

где l = 1/Т - интенсивность потока заданий (заявок);

m = 1/n - интенсивность обслуживания (обработки) заявок;

τ - случайная величина интервала времени между соседними заявками;

Т = МО (t);

t₀ - случайная величина длительности обслуживания одной заявки;

n = МО (t₀).

Коэффициент вариации времени обслуживания:

,

где d₀ = - СКО случайной величины t₀.

Для экспоненциального закона распределения υ = 1, = ν^э;

- равномерного

с плотностью распределения

коэффициент вариации:

;

- постоянного (детерминированного) для неслучайных величин как частного случая равномерного закона:

t₀ = n = const,

а = в =t₀ = const,

u = d₀ = 0.

В теории СМО чаще всего применяется показательный экспоненциальный закон распределения как худший из названных выше по вариации u = 1, а равномерный и постоянный – для проверки диапазона изменения характеристик СМО в широком диапазоне функций распределения с вариациями:

u = 0 … 1.

В связи с отсутствием на начальных стадиях системотехнического проектирования ВС достаточно точных значений параметров ВС применяется приближенное математическое моделирование системы в виде трех типов простейших СМО:

- одноочередной одноканальной СМО с одномерным потоком входных заявок – ОООС (рис. 2.1);

- одноочередной одноканальной СМО с многомерным потоком входных заявок – ООМС (рис. 2.2);

- одноочередной многоканальной СМО с многомерным потоком входных заявок – ОММС (см. рис. 3.1 в описании лабораторной работы №3).

Рис. 2.1 ОООС

Рис. 2.2 ООМС

2.1. Аналитические формулы теории СМО для модели ОООС (рис. 2.1):

· загрузка обслуживающего устройства (ОУ):

,

где Т_n - полезное время работы ОУ;

Т - общее время работы системы с учетом простоев;

· коэффициент простоя ОУ:

h = 1 - r;

· время ответа, равное времени пребывания заявки в системе:

t_отв = u = w + v = ,

где w - среднее значение времени ожидания заявки в очереди;

· средняя длина очереди:

l = lw = ;

· время ожидания заявки в очереди:

w = ru = ;

· среднее число заявок, пребывающих в системе:

h = lu = l + r = .

Условие существования стационарного режима работы системы без перегрузки, при котором названные выше характеристики ВС не зависят от времени:

r < 1.

В этом режиме l и l_np являются конечными величинами, l_вых = l (рис. 2.1), вероятность потери заявок Р_n = 0.

Нестационарный режим наблюдается при перегрузках ВС, когда r > 1. При этом, если очередь неограничена, когда l_np = ¥,

l →¥, l_вых < l,

а при ограниченной очереди, когда l_np – конечная величина, Р_n ¹ 0.

2.2. Аналитические формулы теории СМО для модели ООМС (рис. 2.2.)

· загрузка системы:

R = ,

где m – количество разных типов заявок во входном многомерном потоке;

l_i, n_i, r_i – интенсивность, время обработки, загрузка ОУ по каждой заявке i -го типа в отдельности;

· суммарная интенсивность входного потока заявок:

l = ;

· средняя длина очереди:

l= ,

где w_i – время ожидания в общей очереди заявки i- го типа;

· среднее число заявок, пребывающих в системе:

n= ,

где u_i – время пребывания в системе заявки i -го типа;

· средне-взвешенное время обработки одной заявки в ОУ эквивалентной СМО типа ОООС:

n_ср = ;

· средне-взвешенное время ожидания одной заявки в очереди эквивалентной СМО типа ОООС:

w_ср = ;

· средне-взвешенное время ответа на одну заявку (время ее пребывания в системе) эквивалентной СМО типа ОООС:

t_отв = u_ср = .

Условие существования стационарного режима работы системы:

R < 1.

Зависимость от { r_i } и { n_i } времени ожидания w_i в очереди по каждому i -му типу входных заявок для модели ООМС определяется видом дисциплины обслуживания при выборке их из очереди и постановке на обслуживание:

· для бесприоритетной дисциплины обслуживания (FIFO, LIFO, случайная выборка из очереди) оно одинаково для всех i -х типов заявок [З]:

w = ,

где u _i - коэффициент вариации случайной длительности обслуживания в ОУ i- го типа входной заявки.

Для двух альтернативных законов распределения времени обслуживания заявок: экспоненциального и постоянного время ожидания соответственно равно:

w_э = ,

w_n= ;

· для относительных приоритетов (RP) при выборке из очереди без прерывания обработки находящейся на обслуживании заявки любого уровня приоритета [3]:

w_кэ =

где к – уровень приоритета заявки;

R_к-1 = ;

· для абсолютных приоритетов (АР) при выборке из очереди с прерыванием обработки заявки более низкого приоритета, находящейся на обслуживании, при экспоненциальном и постоянном распределении времен обслуживания и дообслуживания прерванных заявок время ожидания заявки к -го приоритета соответственно равно [3]:

w_кэ = ,

w_кn = .

По приведенным формулам вычисляются и строятся зависимости:

w_k = f (k, B), w_k = f (k, R), k = ,

где В – быстродействие процессора, которое может быть введено в указанные формулы с учетом выражения: n_i = q_i /В, если q_i – вычислительная сложность алгоритма обработки i- й заявки.

В результате сравнительного анализа названных зависимостей при разных видах и уровнях приоритетов обосновывается выбор вида дисциплины обслуживания и уточняется выбранное быстродействие процессора. Критерием выбора может быть минимизация времен ожидания заявок в очереди при достижении удовлетворительной загрузки процессора R = 0,7 … 0,9.

Обоснование желательного диапазона изменения величины быстродействия В процессора при построении и анализе зависимостей: w_k = f (k, B), k = , выполняется по следующим формулам для оценки величины В, которые составлены методами теории СМО для ВС оперативной обработки информации по критерию минимизации потерь из-за задержек в обслуживании заявок и простоев процессора [3]:

· при неограниченном времени ожидания, когда в явном виде не накладываются названные ограничения:

;

· при наложении явных ограничений на времена ожиданий заявок в очереди (w_i £ w , i= ):

+ ,

где w_i^* - предельно допустимое время ожидания в очереди заявки i- го типа;

q_i, q_i⁽²⁾ – вычислительная сложность алгоритма обработки i -й заявки и ее второй начальный момент, который в общем случае равен:

q_i⁽²⁾ = D(q_i) + q_i², а при экспоненциальном распределении времени обработки:

q_i⁽²⁾ = 2q_i²;

· оптимальное быстродействие для случая неограниченного времени ожидания и бесприоритетной дисциплины обслуживания [3]:

В_opt =

+ ,

где - суммарная интенсивность заявок во входном многомерном потоке;

к - постоянный коэффициент, отражающий уровень требований к степени уменьшения времен ожидания { w_i }.

Например, при К = 0: B_opt = .

Чаще всего принимают К = 0,1.

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

R = . (2.1)

Если полученная загрузка не удовлетворяет условию стационарности: R < 1, или она недопустимо мала, например, R < 0,5, следует изменить величину быстродействия В или значения интенсивностей входных заявок и повторить расчеты зависимостей:

w_к = f (k, B), к = .

Циклы расчетов повторяют до тех пор, пока одновременно не будет удовлетворен названный выше критерий выбора дисциплины обслуживания и достигнута удовлетворительная загрузка процессора (2.1).

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

- ускорение решения срочных задач;

- разрешение конфликтов между вычислительными процессами при мультипрограммной обработке.

Следовательно, уровни приоритетов некоторых заданий во входном многомерном потоке не могут быть выбраны произвольно. Названная выше экономия ресурсов обусловлена тем, что относительные и абсолютные приоритеты позволяют гарантировать для наиболее приоритетных заявок достижение конечных малых величин времен их ожидания в очереди даже в периоды, когда ВС работает с перегрузкой при R > 1. Это позволяет выбрать более дешевый процессор с меньшим быстродействием, намерено его перегружая (2.1). По закону сохранения времени ожидая заявок в очереди СМО типа ООМС [3]:

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

2.3. Методика интерактивного решения на ЭВМ

обратной задачи анализа ВС.

Рассмотренный математический аппарат может быть применен не только для решения на ЭВМ описанной выше (п.2.2) прямой задачи анализа ВС, завершаемой выбором подходящей величины быстродействия процессора В, но и более важной для инженерной практики обратной задачи анализа при заданной величине быстродействия В выбранного стандартного процесса. В последнем случае необходимо подобрать допустимые интенсивности поступления входных заданий { l_i } и следовательно - допустимую пропускную способность ВС:

ПС = l = ,

а также выбрать дисциплину их обслуживания при известных быстродействии В и вычислительных сложностях алгоритмов входных заданий { q_i }.

Обратная задача анализа может быть решена на ЭВМ в интерактивном режиме обработки методом последовательных приближений путем многократного решения описанной выше (п.2.2) прямой задачи с вариацией ее исходных данных { l_i }, { w_i^* }.

Для ускорения сходимости процесса последовательных приближений рекомендуется следующий способ выбора начального приближения при заданных В и { q_i }:

- вычислить множество времен обслуживания (обработки процессором) входных заданий:

n_i = q_i / B, i = ;

- принять допущение, что ограничения w_i^* на времена ожидания заявок в очереди не должны превышать времен их обслуживания: w_i^* £ n_i, и ввести в ЭВМ в качестве начального приближения:

(w_i^*)_нач =n_i, i = ;

- учитывая, что в стационарном режиме работы ВС время пребывания i- й заявки в системе равно:

u_{i =} w_i + n_i, i = ,

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

Т_i ³ u_i, i = ,

и задать начальное приближение по { l_i }, в виде:

l_i^нач = .

В конце каждого К -го шага интерактивных вычислений на ЭВМ сравнивается найденное значение В¢_min,k, соответствующее неограниченному времени ожидания, с заданным исходным значением В, и в зависимости от результатов сравнения корректируются величины { w^*_i,k }, вводимые в ЭВМ в следующем (К+1)-М шаге вычислений.

Если найденное в данном К-м шаге

В¢_min,k > В,

то использованные в К -м шаге величины { w^*_i,k } недоспустимо занижены, и их следует пропорционально увеличить при вводе в ЭВМ в (К+1)-м шаге приближений:

.

Если наблюдается обратное неравенство:

В¢_min,k < В,

то величины ограничений на времена ожидания следует по аналогии пропорционально уменьшить:

.

Следует соответственно изменить и вторую группу исходных данных { l_i,k+1 }, вводимых в (К+1)-м шаге решения:

l_i,k+1» (v_i + w^*_i,k+1)^-1, i= .

Последовательные шаги интерактивного решения обратной задачи путем решения в каждом К-м шаге прямой задачи завершаются, когда очередное найденное значение В¢_min,k приблизится к заданному быстродействию В выбранного стандартного процессора: В_min,k» В. Этот критерий косвенно соответствует обеспечению достаточно высокой загрузки процессора R» 0,7 … 0,9. В заключение необходимо выполнить поверочный расчет полученной фактической величины загрузки (2.1), а также весовых коэффициентов: к_i = l_i/l, i= , которые необходимы для дальнейших вычислений средневзвешенных временных характеристик ВС по модели типа ООМС.

Трудоемкие многократные расчеты по приведенным выше формулам автоматизируются с помощью программно-аналитической модели "Выбор". Основные задачи пользователя программы "Выбор":

- предварительное определение вычислительных сложностей { q_i } программ входных заданий ВС с помощью изученной в лаб. раб. №1 программы "Алгоритм";

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

В ³ ,

где - такое желательное значение интенсивности i- го типа входного задания, сумма которых обеспечивает требуемую по техническому заданию пропускную способность ВС:

,

при ориентировочных значениях весовых коэффициентов:

;

- вычисление параметров начального приближения;

- выполнение на ЭВМ интерактивных вычислений методом последовательных приближений с пересчетом в каждом шаге итераций исходных данных:

{l_i,} и {w^*_i};

- проверка подобранных в результате интерактивного расчета на ЭВМ значений { l_i, } по условию:

,

и, если это неравенство не выполняется, увеличение исходной величины В и повторение всех расчетов;

- проверочный расчет по формуле (2.1) фактически полученной величины загрузки R процессора и корректировка быстродействия В при неудовлетворительной загрузке;

- путем сравнения кривых w_k = f(k,B), полученных на ЭВМ, выбор подходящей дисциплины обслуживания и уровней приоритетов входных заданий;

- вычисление весовых коэффициентов {K_i}, требуемых для нахождения средневзвешенных значений характеристик ВС.

3. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

3.1. Загрузить с дискеты и запустить программу "Выбор",

3.2. Выбрать величину быстродействия В процессора и значения вычислительной сложности { q_i } трех входных заданий. Вычислить параметры начального приближения (w₁^*)_нач, (w₂^*)_нач, (w₃^*)_нач и интенсивностей поступления входных заданий l₁^нач, l₂^нач, l₃^нач по приведенным выше (п.2.3) формулам.

3.3. Ввести {li^нач},{q_i},{(w_i^*)_нач} соответственно в первую, вторую и третью колонки исходных данных.

3.4. Выполнить вычисление на ЭВМ результатов первого приближения и зарегистрировать их в рабочей тетради. Сравнить найденное значение В¢_min,1, соответствующее неограниченному времени ожидания, с исходной величиной В. Откорректировать третью и первую колонки в таблице исходных данных, вычисляя их по формулам для w^*_i,k+1 и l_i,k+1, приведенным выше (п.2.3).

3.5. Выполнить вычисление на ЭВМ результатов второго приближения. Зарегистрировать новое значение В¢_min,2 и сравнить его с исходной величиной В. Аналогично п.3.4 откорректировать третью и первую колонки в таблице исходных данных.

3.6. Повторять вычисления на ЭВМ с коррекцией исходных данных аналогично п.п.3.4, 3.5 до тех пор, пока очередное новое значение В¢_min,к не станет примерно равным В: В¢_min,к» В. Зарегистрировать все результаты вычислений последнего приближения В¢_min, В¢¢_min, В_орt и кривые w_k = f(k, B) для трех дисциплин обслуживания.

3.7. Выбрать наиболее подходящую дисциплину обслуживания и уровни приоритетов входных заданий согласно рекомендациям п.2.2.

3.8. Выполнить поверочный расчет фактически полученной величины загрузки процессора по формуле (2.1) и значения весовых коэффициентов к_i = l_i/l, i= .

3.9. Предъявить полученные результаты преподавателю.

4. СОДЕРЖАНИЕ ОТЧЕТА

4.1. Краткое описание методики интерактивного решения на ЭВМ обратной задачи анализа ВС по определению пропускной способности ВС и выбору дисциплины обслуживания входных заданий при заданном быстродействии В стандартного процессора.

4.2. Схема СМО типа ООМС.

4.3. Расчет параметров начального приближения.

4.4. Зарегистрированные результаты вычислений на ЭВМ первого приближения.

4.5. Последовательность зарегистрированных значений В¢_min,к и расчетов исходных данных прямой задачи {w^*_iк+1} и {l_i,к+1}, корректируемых в каждом К-м шаге интерактивных вычислений на ЭВМ.

4.6. Зарегистрированные результаты вычислений на ЭВМ последнего приближения: В¢_min, В¢¢_min, В_орt и кривые w_k = f(k, B), к = для всех трех дисциплин обслуживания.

4.7. Обоснование выбора вида дисциплины обслуживания и уровней приоритетов входных заданий.

4.8. Расчет фактически полученной величины загрузки и весовых коэффициентов.

4.9. Выводы с указанием достигнутой величины пропускной способности ВС, фактических величин времен ожидания в очереди и времен ответа по каждому типу входных заданий и описанием экономического выигрыша от введения выбранной дисциплины обслуживания.

4.10. Список использованных источников.

5. КОНТРОЛЬНЫЕ ВОПРОСЫ

5.1. Почему аналитическая теория СМО основана на использовании показательного экспоненциального закона распределения случайных величин?

5.2. Чем объяснить случайный характер процессов функционирования ВС?

5.3. Как средняя длина очереди и время ожидания в очереди зависят от загрузки обслуживающего устройства СМО типа ОООС?

5.4. Почему средние значения временных характеристик СМО типа ООМС должны вычисляться как средне-взвешенные?

5.5. Чем отличаются стационарный и нестационарный режим работы ВС?

5.6. В чем состоит экономический выигрыш от применения приоритетных дисциплин обслуживания?

5.7. Назначение приоритетных дисциплин обслуживания заявок в очередях современных ВС?

5.8. В чем состоят критерии выбора дисциплин обслуживания и уровней приоритетов?

5.9. Чем отличаются прямая и обратная задачи анализа ВС?

5.10. Зачем требуется предварительная ориентировочная оценка быстродействия процессора при решении обратной задачи анализа ВС?

5.11. Закон сохранения времени ожидания?

5.12. Обосновать способ выбора параметров начального приближения при интерактивном решении на ЭВМ обратной задачи анализа ВС?

5.13. Почему с уменьшением быстродействия процессора увеличивается его загрузка?

5.14. Как связаны между собой допустимая интенсивность потока входных заданий и пропускная способность ВС?

5.15. Как вычислить производительность ВС, зная ее пропускную способность?

Лабораторная работа №3

Выбор оптимального количества процессоров

и терминалов ВС

1. Цель работы

Освоение методики графо-аналитического синтеза базовой структуры многотерминальной многопроцессорной ВС (ММВС) и применения теории СМО для расчета основных ее параметров и характеристик. Приобретение практического навыка их оптимизации на ЭВМ в интерактивном режиме работы программно-аналитической модели ВС в виде СМО типа ОММС с ограниченной очередью.

2. Методика оптимального синтеза многопроцессорных ВС на основе элементарной теории СМО.

Если расчетная загрузка проектируемой ВС

ρ = λυ_ср > 1, (3.1)

где λ - суммарная интенсивность многомерного потока входных заданий, вычисляемая как λ = ;

υ_ср – средне-взвешенное время обработки процессором одного задания, вычисляемое по формуле:

υ_{ср =} , (3.2)

то однопроцессорная ВС будет работать в нестационарном режиме с перегрузкой. Чаще всего это наблюдается в многотерминальных ВС коллективного пользования, терминальная сеть которых создает сумматорный поток входных заданий достаточно высокой интенсивности λ. В этом случае степень загрузки R одного процессора может быть снижена до уровня, требуемого по условию стационарности: R < 1, путем применения параллельной обработки информации несколькими процессорами. Полагая, что параллельные каналы обработки однородны (одинаковы), загрузка каждого из М процессоров уменьшится в М раз:

.

Поэтому центральное обрабатывающее ядро современных ММВС строится по архитектуре многопроцессорных ВС (МПВС), многопроцессорных ВК(МПВК), многомашинных ВК (ММВК) или наиболее распространенного варианта – локальной вычислительной сети (ЛВС). Минимальное число M_min процессоров ММВС определяется следующей очевидной формулой, найденной из условия стационарности R £ 1:

M_min = ρ = λυ_ср при R_max = 1.

В связи с большими случайными колебаниями параметров рабочей нагрузки на входе центрального ядра ММВС создается очередь заявок на процессорную обработку. Предельная длина очереди l_пр всегда ограничивается из-за ограниченной емкости оперативной (V_озу) и внешней (V_взу) памятей ВС. При ограниченной очереди возможна потеря заявок в периоды перегрузок ВС из-за непредвиденных случайных колебаний рабочей нагрузки. Поэтому имеется конечная малая величина вероятности потери заявок Р'_пот. Она может быть уменьшена путем увеличения числа процессоров М и/или предельной длины очереди l_пр. Однако это приводит к увеличению стоимости ВС:

С = МС_пр + С_озу + С_взу,

где С_пр, С_озу, С_взу – стоимости основных устройств центрального ядра ММВС: процессора, оперативной и внешней памяти.

Следовательно, возникает следующая задача оптимального синтеза [7]:

- выбрать такое оптимальное число процессоров М_opt, которое гарантировало бы при заданной ограниченной длине очереди l_пр и допустимой вероятности потерь заявок Р_пот достижение минимальной стоимости системы по критерию:

С ® min

при ограничениях

l < l_пр ,

Р'_пот < Р_пот ,

где l - среднее значение длины очереди заявок;

Р'_пот - полученное в результате синтеза ВС значение вероятности потери заявок.

2.1. Выбор оптимального числа процессоров

В инженерной практике в качестве исходных данных названной выше задачи оптимального синтеза центрального ядра ММВС обычно назначаются:

- требуемая производительность системы П с размерностью [П] = ЭО/С;

- средние значения вычислительной сложности алгоритмов всех типов входных заданий: {θ_i}, i = при [θ] = ЭО;

- весовые коэффициенты заданий во входном многомерном их потоке:

i = , при [λ] = С ^-1;

- быстродействие В выбранного стандартного процессора с размерностью [ В] = ЭО/С;

- допустимая вероятность потери заявок Р_пот;

- стоимость процессора С_пр;

- номинальные величины емкостей выбранных ОЗУ – V_о и ВЗУ – V_в;

- стоимости ОЗУ и ВЗУ: С_озу, С_взу.

Необходимо найти оптимальное число процессоров (М_opt =?) и такую предельную длину очереди (l_пр =?), при которых стоимость ВС минимальна: С® min и соблюдаются ограничения:

l < l_пр, Р'_пот < Р_пот.

Здесь в дополнение к общей постановке задачи оптимального синтеза ставится задача нахождения такой допустимой величины l_пр, которая позволила бы при М = М_opt удовлетворить неравенство: Р'_пот < Р_пот. Эта сложная вариационная математическая задача может быть приближенно решена, если ядро ММВС промоделировать в виде СМО типа ОММС (рис 3.1) при допущении, что параллельные каналы обслуживающих устройств (УО) одинаковы.

Рис.3.1. Одноочередная многоканальная СМО с многомерным потоком входных заявок (ОММС)

Для модели ОММС в теории СМО выведена следующая формула вероятности потери заявок при заданном ограничении l_пр на длину очереди [7]:

Р'_пот = .

Отсюда, заменив Р'_пот на Р_пот, можно найти такую величину предельной длины очереди l_пр, при которой фактическая вероятность потери заявок Р'_пот не превысит допустимой Р_пот [7]:

l_пр = . (3.3)

Так как требуемая предельная длина очереди (3.3) определяется исходными значениями ρ, Р_nom и зависит от искомого числа процессоров М:

l_np = l_np(ρ, P_nom, M),

поставленная задача одновременного нахождения M_opt =? и l_np =? разрешима.

Используя формулу (3.3), предложен следующий метод интерактивного графо-аналитического решения на ЭВМ данной задачи оптимизации ММВС [7]. Преобразуем выражение стоимости ядра ММВС:

С = МС_np + С_озу + С_взу,

С = МС_np + (С_озу + С_взу),

N_n = MA + l_np, (3.4)

где N_n - относительное число единиц оборудования центрального ядра ММВС, приведенное к эквивалентному числу мест в очереди;

А - экономический коэффициент.

Введенные в (3.4) величины вычисляются по формуле:

, ,

где С₁ = - удельная стоимость одного места в очереди входных заданий, которая может быть найдена на основании справочных данных из технической документации на устройства ЭВМ и их ценников, а также данных, полученных в результате анализа вычислительной сложности алгоритмов входных заданий (см.лаб.раб.№1):

,

где V_o, V_в - номинальная величины емкостей выбранных ОЗУ и ВЗУ;

С_озу, С_взу - цены ОЗУ и ВЗУ системы;

V_oзу, V_взу - средне-взвешенные значения объемов памяти ОЗУ и ВЗУ, требуемых для хранения программы и данных одного входного задания:

,

,

где V_oi, V_Вi - объемы оперативной и внешней памяти, требуемые для хранения программы и данных i -го задания (см.лаб.раб.№1 и №2).

В результате этого преобразования данная задача сводится в соответствии с (3.4) к минимизации приведенного числа эквивалентных единиц оборудования[7]:

График зависимости N_n = f(M) при A = const, ρ = const, Pnom = const приведен на рис. 3.2. Он имеет явно выраженный минимум в точке M = Mopt.

Требуемый для расчета и построения графика (рис.3.2) диапазон изменения числа процессоров выбираются в виде:

[M]: M_min,..., M_max = 10M_min.

Зависимости N_n = f(M) при вариации исходных данных r, P_nom в широких диапазонах вычисляются на программно-аналитической модели "Канал".

Рациональный выбор минимального значения загрузки системы r_min = r₁ можно осуществить, зная требуемую величину П производительности ММВС и средне-взвешенное значение вычислительной сложности алгоритмов входных заданий:

,

которое определяет требуемую пропускную способность системы:

ПС = П/q.

Так как ПС = l, загрузка ВС:

.

Для нахождения M_opt выполнение однократного вычисления зависимости N_n = f(M) при фиксированных исходных данных r, Pnom (рис.3.2.) недостаточно. Требуется выполнить несколько таких расчетов с изменением исходных данных для учета случайных колебаний рабочей нагрузки, например при r = r₁, r₂, r₃, где r₂ = 2r₁, r₃ = 3r₁ и при P_nom = 10^-9... 10^-2.

Попутно может быть качественно (эмпирически) решена задача уточнения максимально допустимой величины загрузки r_∂ синтезируемой ВС. Сравнивая между собой полученные на ЭВМ значения N¹_nmin, N²_nmin, N³_nmin в точках минимумов по оси ординат при разных загрузках r₁, r₂, r₃ и соответствующие им оптимальные числа процессоров М¹_opt, M²_opt, M³_opt в точках минимумов по оси абцисс, можно пойти на увеличение загрузки до величины r_∂ по сравнению с исходной r_{min =} r₁, если это не потребует чрезмерного увеличения расходов оборудования по сравнению с N¹_min. Тем самым появляется возможность дополнительно повысить производительность системы до максимально допустимого уровня

П_¶ = ρ_¶ В > П

при умеренных затратах.

Таким образом, интерактивный процесс выбора числа процессоров завершается выбором допустимой величины загрузки r_∂,а в качестве оптимального числа процессоров можно выбрать среднее арифметическое:

,

где - оптимальные числа процессоров соответственно при P_nom = 10^-2, P_nom = 10^-9 ρ_¶ = const.

2.2. Расчет характеристик синтезированного ядра ММВС

На основании выбранных выше в п.2.1. величин ρ_∂ и M_opt вычисляются уточненные численные значения ожидаемых характеристик производительности синтезированного ядра многопроцессорной ВС [2, 3, 7]:

· предельно допустимая длина очереди l_np входных заданий по формуле (3.3);

· среднее значение длины l очереди к процессорам:

,

;

· допустимая суммарная интенсивность потока входных заданий, равная пропускной способности ВС:

,

где v_ср = q / В, а q находится по формуле (3.5). Отсюда легко перейти к величине достигаемой производительности:

П = q · ПС = rВ;

· среднее время ожидания заявки в очереди к процессорам:

w_cp = l/l;

· среднее время ответа центрального ядра ММВС на одно задание без учета времени работы на терминале:

t_отв = w_cp + v_cp.

2.3. Выбор требуемого числа терминалов многотерминальных ВС.

Найденная в п.п.2.1, 2.2 пропускная способность ММВС: ПС=l может быть достигнута только при условии, если терминальная сеть ВС сможет создать на входе центрального ядра системы поток заданий с интенсивностью не менее полученной в п.2.2 величины l. Для этого потребуется применить число терминалов М _т не менее следующего их минимального допустимого числа:

М _{т min} = r _т = ln _т ,

где r _т – загрузка терминальной сети;

n _т – среднее время работы пользователя на терминале при вводе одного задания.

Учитывая, что допустимая длина очереди l_np пользователей к терминальной сети должна быть минимальной, чтобы уменьшить потери их рабочего времени, и по этой же причине допускается сравнительно большая величина вероятности потери Р_nom заявок пользователей на входе в ММВС, возникает задача выбора такого числа терминалов М _т, которое обеспечивало бы интенсивность входных заданий центрального ядра ММВС не менее требуемой l при следующих исходных данных:

- заданной интенсивности заявки на выходе терминальной сети l_вых = l; - среднем времени работы на терминале по одному заданию: v _т = 20 … 200 с;

- предельных длинах очереди пользователей на входе всей терминальной сети: l_np = 0; 1; 2;

- допустимой вероятности потери заявок пользователей на входе терминальной сети: P_min = 0,01 … 0,1.

Поставленная задача может быть приближенно решена методами теории СМО, используя простейшую модель терминальной сети в виде СМО типа ОММС (рис.3.1). Для этого на инструментальной ЭВМ организуется итерационный вычислительный процесс, каждый цикл итерации которого выполняется по алгоритму:

М_Т := М_Т + 1

при М_Тнач = М_Тmin = r _т = ln _т до тех пор, пока не выполнится неравенство [7]:

.

Расчеты по приведенным выше громоздким формулам автоматизируются программно-аналитической моделью