МЕТОДЫ ИССЛЕДОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Исполнитель

МЕТОДЫ ИССЛЕДОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

План

1. Методы определения характеристик  вычислительных систем

2. Метод повторных экспериментов

3. Методы генерации случайных величин и последовательностей

1. Методы определения характеристик
вычислительных систем

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

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

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

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

                                                                                           (1)

где  — коэффициент загрузки k-го устройства;  — среднее время обслуживания одной заявки k-м устройством; N_ok— количество обслуженных устройством заявок за время моделирования Т_т

Определение условий удовлетворения стохастических ограничений при имитационном моделировании производится путем простого подсчета количеств измерений, вышедших и не вышедших за допустимые пределы.

Расчет математического ожидания и дисперсии выходной характеристики. В случае анализа стационарного эргодического процесса функционирования системы вычисление математического ожидания и дисперсии характеристики у производится усреднением не по времени, а по множеству N значений, измеренных по одной реализации процесса достаточной продолжительности. В целях экономии основной памяти ВС, на которой проводится моделирование, математическое ожидание и дисперсия вычисляются в ходе моделирования путем наращивания итогов при появлении очередного измерения случайной характеристики по рекуррентным формулам. Математическое ожидание случайной величины у для ее n-го измерения у_n:

                                                                                   (2)

где m_n-1 — математическое ожидание, вычисленное по предыдущим п — 1 измерениям.

Дисперсия для n-го измерения:

                                                                     (3)

где  — дисперсия, вычисленная по предыдущим п — 1 измерениям. Вначале дисперсия принимается равной нулю.

При большом количестве измерений эти оценки являются состоятельными и несмещенными.

Расчет среднего по времени значения выходной характеристики. В процессе моделирования постоянно ведется подсчет длины очереди к каждому устройству и занимаемой емкости накопителей. При этом отслеживается максимальное значение и вычисляется среднее по времени значение. Например, средняя длина очереди вычисляется по формуле

{spoiler=Подробнее}

                                                                                           (4)

Рис. 1. Временная диаграмма изменения длины очереди

где i — номер очередного изменения состояния очереди (занесения заявки в очередь или исключения из очереди) (рис. 1); N—количество изменений состояния очереди; _i; — интервал времени от (i-1)-го до 1-го изменения состояния; l_i — число заявок в очереди в интервале

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

                                                                                         (5)

где q_i — емкость накопителя, занятая в интервале времени между двумя последовательными, обращениями к накопителю.

Формулы (4) и (5) приводят к виду, удобному для вы­числения путем наращивания итогов.

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

Перед началом моделирования задаются предположительные границы изменения интересующей выходной характеристики y, т. е. нижний y_H  и верхний y_B пределы, и указывается число ин­тервалов гистограммы N_g. По этим данным вычисляется интервал

Затем в процессе моделирования по мере появления измерений характеристики у, определяется число попаданий этой случайной величины в i-й интервал гистограммы R_i; и подсчитывается общее число измерений N. По полученным данным вычисляется относи­тельная частота по каждому интервалу:

Этих данных достаточно для построения гистограммы относи­тельных частот: на оси абсцисс откладываются пределы изменения анализируемой характеристики у; весь диапазон изменения под­разделяется на заданное число интервалов; над каждым t-м интервалом проводится отрезок, параллельный оси абсцисс, на расстоянии, равном G_i от оси абсцисс (рис. 2).

Рис. 2. Гистограмма относитель­ных частот

Отметим, что площадь гистограммы относительных частот равна единице, так же, как интеграл от плотнос­ти вероятности в пределах от минус до плюс бесконеч­ности равен единице. Пло­щадь гистограммы равняется сумме площадей прямоугольников, построенных на каждом i-ом интервале:

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

При необходимости выдвигается гипотеза о том, что получен­ное эмпирическое распределение согласуется с некоторым теоре­тическим распределением, имеющим аналитическое выражение для функции или плотности распределения. Эта гипотеза про­веряется по тому или другому критерию. Например, при использовании критерия хи-квадрат в качестве меры расхо­ждения используется выражение

                                                                                   (6)

где p_i — определенная из выбранного теоретического распределе­ния вероятность попадания случайной величины в i-й интервал.

Из теоремы Пирсона следует, что для любой функции распре­деления F(у) случайной величины у при N  распределение величины  имеет вид

                                                 (7)

где z — значение случайной величины  k = Ng —(r +1) — число степеней свободы распределения хи-квадрат; r — количе­ство параметров теоретического закона распределения; Г (k/2) — гамма-функция.

Функция распределения хи-квадрат табулирована по вычисленному значению и числу степеней свободы с помощью таблиц определяется вероятность (7). Если она превышает заданный уровень значимости С, то выдвинутая гипотеза при­нимается.

2. Метод повторных экспериментов

Характеристики нестационарных процессов. Для системы, процесс функционирования которой отличается от стационарного эргодического, нельзя вычислять вероятностные характеристики по одной реализации процесса, поскольку оценки могут получиться смещенными или несостоятельными. Следует ожидать, что если на ВС поступает поток заявок, интенсивность которого изменяется во времени, как это показано, например, на рис. 3. выходные характеристики такой системы относятся к нестационарным случайным функциям (процессам).

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

                                                                           (8)

где  — оператор преобразования, лежащий в основе определения характеристики — количество реализации, по которым производится усреднение.

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

                                                                               (9)

Полной вероятностной характеристикой случайного процесса может служить многомерная функция распределения вероятности мгновенных значений процесса.  Случайный процесс Y(t) считается исчерпывающе описанным в вероятностном смысле на интервале , если задана его N_r- мерная функция распределения:

                                              (10)

которая соответствует любому сочетанию моментов времени t_r на интервале (О, Т) при произвольном N_r, в том числе при . Исходя из этих предпосылок, при исследовании стоха­стических систем необходимо получать для каждой выходной характеристики совокупности N_i реализации, причем по каждой реализации следует измерять значения no N_r сечениям (отсчетам), как это показано на рис. 3. Таким способом могут быть получены вероятностные оценки выходных характеристик, если они являются нестационарными или стационарными неэргодическими процессами.

Рис. 7. Реализации нестационарного случайного процесса

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

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

Исследование систем с нестационарным режимом путем имитационного моделирования с применением метода повторных экспериментов сводится к следующему. Проводится N_i имитационных экспериментов. При каждом последующем эксперименте параметры системы и нагрузки устанавливаются на исходные значения и в процессе каждого эксперимента остаются неизменными или изменяются по одним и тем же зависимостям. Датчики случайных чисел устанавливаются в начальное состояние только один раз — перед моделированием и до конца моделирования вырабатывают последовательности случайных чисел.

Рис. 4. Алгоритм моделирования по методу повторных экспериментов

Период моделирования Т_m по каждому эксперименту разделяется на N_r сечений. Интервал времени моделирования между двумя соседними сечениями будем называть прогоном. В каждом эксперименте для фиксированных моментов времени  определяются численные значения выходных характеристик.

По каждому i-му сечению для всех выходных характеристик может определяться эмпирическая многомерная функция  или плотность распределения, оцениваться математическое ожидание m_y(t_r), корреляционная функция  или дисперсия D_y (t_r) по всей совокупности N_i реализации.

Для обеспечения статистической достоверности результатов обычно требуется проведение нескольких сотен или тысяч экспериментов с измерением и обработкой вектора выходных характеристик по нескольким десяткам сечений. Очевидно, что выполнение этой работы «вручную» не представляется возможным в приемлемые сроки. Это означает, что на ВС должно быть возложено не только проведение имитации, но и реализация метода повторных экспериментов.

Машинный алгоритм повторных экспериментов представлен на рис. 4.  В первом блоке выполняется ввод данных о моделируемой системе и нагрузке, а также производится инициализация программы. Отдельно выделен блок настройки датчиков случайных чисел, чтобы подчеркнуть, что датчикам задаются начальные значения до основных циклов моделирования. В дальнейшем датчики вырабатывают неповторяющиеся последовательности случайных чисел. Затем вводятся и размещаются в соответствующих массивах и переменных исходные данные. В частности, задаются количества прогонов N_r, экспериментов N_i и период моделирования Т_m.

В следующем блоке выполняется имитационное моделирование процесса функционирования так, как это описано в п. 2, по тому или другому алгоритму. В ходе имитации изменяются значения тех переменных параметров, которые заданы как функции времени, и постоянно отслеживается достижение конца прогона, т. е. событие, когда текущее модельное время станет равным t_r. При выполнении этого условия определяются, вычисляются и запоминаются статистические данные по r-му сечению, после чего имитация продолжается.

Если выполнено N_r прогонов, т. е. завершен очередной эксперимент, формируется номер следующего эксперимента и управление передается блоку подготовки исходных данных. После проведения N_i экспериментов завершается обработка и вывод результатов моделирования.

Расчет характеристик по методу повторных экспериментов. При анализе систем с нестационарным процессом функционирования путем имитационного моделирования с использованием метода повторных экспериментов для каждой выходной характеристики, которая является случайным процессом, зачастую оценивается математическое ожидание, корреляционная функция или дисперсия, а также могут быть построены по каждому сечению гистограммы, чем определяется многомерная плотность распре­деления вероятностей.

Математическое ожидание случайного процесса Y (t) — это неслучайная функция т_у(t), которая при каждом значении аргумента t_r представляет собой математическое ожидание соответствующего сечения случайной функции:

Корреляционная функция случайного процесса — это тоже неслучайная функция двух аргументов К_у(t, t'), которая при каждой паре значений аргументов t,t' равна корреляционному моменту соответствующих сечений случайной функции:

При равенстве t=t' корреляционная функция превращается в дисперсию случайной функции:

В соответствии с формулой (9) N_r-мерная плотность распределения вероятностей оценивается по формуле:

                                         (11)

где значения функции  равны 1 при  и равны 0, если хотя бы одно из этих неравенств для i-й реализации не выполняется.

В результате вычисления по формуле (11) получается многомерная плотность распределения вероятностей, подобная той, которая изображена на рис. Важно отметить, что для проверки выполнения стохастических ограничительных условий типа (1.5) нет необходимости вычислять плотность распределения по формуле (11), а достаточно подсчитать общее количество N_y и количество N_p значений измерения случайной величины, попадающих между ограничивающими пределами, по всей совокупности экспериментов, а затем определить вероятность выполнения ограничительного условия:

                                          P_y=N_P/N_y                                                (12)

При моделировании вычисления результатов производятся в конце каждого прогона путем наращивания итогов. В частности, количественные вероятностные значения таких выходных характеристик, как длины очередей к каждому устройству, времена реакции по каждому потоку заявок и времена загрузки каждого устройства, определяются по r-му сечению для i-го эксперимента по следующим формулам. Оценка математического ожидания длины очереди к устройству:

                                                                              (13)

где L_i-1 — математическое ожидание длины очереди за предыдущие (i-1) экспериментов; l_i — длина очереди по r-му сечению для i-го эксперимента.

Дисперсия длины очереди

где D[L_i-1] — дисперсия длины очереди за предыдущие (i — 1) экспериментов; в первом эксперименте дисперсия принимается равной нулю.

По временам реакции и загрузки при достаточно большом количестве сечений, когда процесс можно считать стационарным на протяжении одного прогона, текущие значения математических ожиданий и дисперсии вычисляются по формулам (2) и (3) соответственно. Тогда в r-м сечении i-го эксперимента оценка математического ожидания времени загрузки каждого устройства при обслуживании одной заявки:

где V_i-1 — математическое ожидание времени загрузки за предыдущие (i— 1) экспериментов; N_z(i-1) — число загрузок устройства на r-м прогоне по предыдущим (i — 1) экспериментам;  — математическое ожидание времени загрузки на r-м прогоне в i-м эксперименте; n_zi — число загрузок устройства на r-м прогоне в i-м эксперименте.

Дисперсия времени загрузки каждого устройства на r-м прогоне

где D [V_i-1] — дисперсия, вычисленная по предыдущим (i — 1) экспериментам; d_i —дисперсия, вычисленная в i-м  эксперименте.

Коэффициенты загрузки устройств вычисляются по формуле (1).

Оценки математического ожидания и дисперсии времени реакции U_i по каждому потоку в r-м сечении i-го эксперимента выполняются по формулам, аналогичным (15) и (16). Для экономии места в памяти моделирующей ВС обновленные статистические характеристики по r-му сечению записываются на место прежних, вычисленных в (i — 1) эксперименте.

3. Методы генерации случайных величин и последовательностей

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

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

                                                                             (17)

где А, С — константы; М — достаточно большое положительное целое число.

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

Моделирование случайных событий и дискретных величин.  Для моделирования случайного события X, наступающего с ве­роятностью Р, берется значение  случайного числа, равномерно распределенного на интервале (0,1), и сравнивается с Р. Если  Р, то считается, что произошло событие X.

Предположим, что дискретная случайная величина Y может принимать значения y₁, …, y_n вероятностями р₁, ..., р_п..  При этом

.

Тогда берется значение  случайного числа, распределенного равномерно на интервале (0, 1), и определяется такое k, принад­лежащее совокупности (1, n), при котором удовлетворяется не­равенство

Тогда случайная величина Y принимает значение у_k..

 Моделирование случайных непрерывных величин. Пусть непре­рывная случайная величина Y имеет произвольный закон распре­деления. Предположим, что она задается эмпирической плот­ностью распределения f* (у) — гистограммой (рис. 5, а). Из гистограммы определяется эмпирическая функция распределения F* (у) — дискретная кумулятивная функция (рис. 5, б) для сере­дин интервалов группирования случайной величины в пределах (y_min,   y _max).

Для определения одного конкретного значения случайной величины Y берется значение α случайного числа, равномерно распределенного на интервале (0, 1). Затем находится такое k, при котором

Рис. 5. Графики для определения значе­ния случайного числа по дискретной и интегральной функции распределения

Тогда искомое случайное число равное (рис. 5, б). Это же правило применимо и при задании случайной непрерывной вели­чины интегральной функцией распределения F (у), как показано на рис. 5, б. Оно вытекает из теоремы: если случайная вели­чина Y имеет плотность распределения F (у), то ее распределение

                                                                                       (18)

является равномерным на интервале (0, 1).

Для некоторых законов распределения (экспоненциальный, Эрланга) имеются простые аналитические зависимости у = Ф (). Например, пусть требуется получить конкретное значение слу­чайного числа Y с экспоненциальным законом распределения. Подставим в формулу (18) а и плотность распределения:

После интегрирования получается

Разрешая это уравнение относительно у_k,, имеем

Учитывая, что если случайная величина  подчинена равно­мерному закону распределения в интервале (0, 1), то случайная величина  также имеет равномерный закон распре­деления в интервале (0, 1), последнее соотношение можно заме­нить следующим:

                                                                                           (19)

Процедура определения конкретного значения случайного числа с заданным законом распределения называется случайным испытанием или «бросанием жребия».

Моделирование случайных процессов сводится на практике к определению последовательностей случайных величин. Исход­ными данными являются функции распределения, определенные в требуемые моменты времени, и последовательность случайных чисел  подчиняющаяся равномерному закону распре­деления в интервале (0, 1). Конкретные значения случайных процессов в нужные моменты времени находят по изложенным выше правилам.

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

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

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

1. Измерямые характистики ВС.
2. Основные формулы для расчета выходных характеристик ВС.
3. Методика пострения гистограммы и ее использование для иследования ВС.
4. Основная идея метода повторных экспериментов.
5. Что понимается под датчиком случайных величин?
6. Какие методы (алгоритмы, программы) генерации последовательностей случайных величин вы знаете?
7. Примеры использования датчиков случайных чисел.

   {/spoilers}