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

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

а для сети, зависящей от нагрузки,

При этом порядок требуемого объема памяти ЭВМ соответственно

Таким образом, ресурсы ЭВМ, необходимые для реализации алгоритма свертки, растут экспоненциально при увеличении R. Из п. 3.3.2 видно, что аналогично возрастают затраты на время и объем памяти ЭВМ для алгоритма анализа средних значений. Кроме того, при вычислении нормализующей константы возникает опасность переполнения или обнуления результатов в памяти ЭВМ.

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

3.4.1 Выбор масштаба (масштабирование)

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

числа слагаемых. Каждое из таких слагаемых является произведением вида

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

Решение системы уравнений баланса потоков

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

В связи с этим естественным путем борьбы с явлением переполнения или обнуления является выбор масштабного коэффициента (шкалирующего множителя) для ограничивающего значение . В настоящее время для борьбы с обнулением и переполнением разработан ряд методов [152,241]. Однако для реализации этих методов требуются дополнительные ресурсы ЭВМ.

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

Очевидное решение этой задачи имеет вид

Ясно, что описанный способ масштабирования не гарантирует решения проблемы переполнения или обнуления во всех случаях. Такая гарантия возможна, если ограничивать не отдельные слагаемые нормализующей константы, а величину в целом, что достигается, например, при использовании динамического шкалирования [241]. Однако предложенный выше способ в значительной мере снижает опасность обнуления или переполнения и, что особенно важно, практически не требует затрат ресурсов ЭВМ для своей реализации.

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

В таблице 3.5 представлены вычисленные в соответствии с алгоритмом Бузена значения функции . Из таблицы видно, что даже для рассматриваемой сети МО малой размерности значения возрастают очень быстро. Определим масштабный множитель и новые значения Новые значения величин приведены в таблице 3.6.

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

Таблица 3.5

Таблица 3.6