BC/NW 2016 № 1 (28):4.1

ИССЛЕДОВАНИЕ СХОДИМОСТИ МЕТОДА ТАНГЕНСОВ ПРИ РАСЧЕТЕ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ

Абросимов Л.И., Сокин Д.В.

Введение

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

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

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

Рисунок 1. Узел как система

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

Основные параметры сообщений:

·  – интенсивность поступления сообщений (усредненное количество сообщений, поступающих на вход узла в единицу времени);

·  – интенсивность обслуживания сообщений узлом (усредненное количество сообщений, поступающих на вход узла в единицу времени).

Основные характеристики узлов, как систем массового обслуживания:

·  – время обслуживания сообщений узлом;

·  – время задержки сообщений в системе  (в узле и очереди на обслуживание);

·  – коэффициент загрузки узла ;

·  (формула Литтла) – количество сообщений в системе обслуживания (в узле и очереди на обслуживание);

·  – количество сообщений в очереди на обслуживание.

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

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

Постановка задачи

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

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

 ,                                                         (1)

где  – заданное количество сообщений в контуре  – математическое ожидание количества сообщений в узле , контура .

Для определения математического ожидания количества сообщений  для каждого отдельного узла  определенного контура , в системе обслуживания, используется формула Литтла (2):

 ,                                                    (2)

где  – время задержки сообщений в системе  (в узле и очереди на обслуживание).

При этом для уменьшения погрешности при расчете характеристик замкнутых систем необходимо использовать коэффициент ограниченности очереди  (3):

 , (3)

А при учете, что в рамках задачи при составлении нелинейных уравнений все  определенного контура принимаются равными, т.е. , формула (1) преобразуется к виду (4):

 ,                               (4)

что позволит нам составить нелинейные уравнения в канонической форме (5):

,                                         (5)

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

В качестве метода решения таких систем был выбран метод Тангенсов, предложенный профессором Абросимовым Л. И. [1], который, в отличие от метода дихотомии, обеспечивает гарантированное решение нелинейных уравнений при достаточно большой загрузке сети.

Алгоритм метода тангенсов

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

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

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

,                                            (6)

где  – базовое значение интенсивности поступающих сообщений контура  на 0-й итерации;  – интенсивность обработки сообщений узлом ;  – количество контуров, проходящих через узел .

Уравнение (6) выполняется для всех контуров , после чего происходит решение первого уравнения пошаговым методом.

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

,                                      (7)

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

Рисунок 2. Вычисление первого тангенса

После этого начинается сам циклический процесс определения , посредством соотношений:

                                      (8)

,                                (9)

где  – значение приращения .

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

· если , то , а ;	(10)
· если , то .

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

Рисунок 3. Сходимость пошаговой процедуры

Циклический пошаговый процесс продолжается до тех пор, пока на
каком-то шаге  не будет выполнено условие окончания:

                                   (11)

где  – заданная точность вычислений.

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

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

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

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

Итерационная процедура продолжается до тех пор, пока не будет выполнено условие окончания цикла:

Исследование сходимости алгоритма метода тангенсов

Рассмотрим следующий пример. Дана простая вычислительная сеть с тремя узлами и двумя замкнутыми контурами (рисунок 4). Контур  обслуживают узлы 1 и 3, а контур  обслуживают узлы 2 и 3. Для рассматриваемой вычислительной сети составляется система из двух нелинейных уравнений, и задаются исходные данные. Необходимо рассчитать интенсивности поступления сообщений  для рассматриваемой системы.

Рисунок 4. Исходные данные примера.

Результаты пошаговой процедуры для первой итерации контура 1, при , представлены в таблице 1.

Таблица 1. Результаты пошаговой процедуры для 1 итерации контура 1, при .

Шаг	0	1	2	3	4	5	6
	0	2,5000	4,3077	4,5759	4,4418	4,4516	4,4467
	4	2,8923	0,4291	-0,4410	0,0315	-0,0004	0,0156

По этим результатам был построен график функции «» (рис. 5), где в качестве ограничений выступают значения «» по первому слагаемому (красная граница) и «» по второму слагаемому (оранжевая граница). Основной границей является минимальное между ними (), т.е. значение «», представляющее границу для .

Рисунок 5. График функции «», построенный по данным таб. 1.

По результатам выполнения алгоритма метода тангенсов были получены значения, представленные в таблице 2.

Таблица 2. Результаты вычислений нелинейных уравнений баланса.

Итерация	0	1	2	3	4	5	6
	5,0000	4,4467	4,1028	3,8134	3,6916	3,5655	3,5277
	5,0000	5,4926	5,8603	6,0585	6,1328	6,2041	6,2244

На основании результатов был нарисован график сходимости алгоритма (рис. 6).

Рисунок 6. Иллюстрация сходимости алгоритма по данным таб. 2.

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

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

При первом этапе сначала вычислялось значение  для первого контура, а затем для второго (на всех итерациях). Во время второго этапа порядок был противоположным. Таким образом, были получены значения для обоих этапов, представленные в таблице 5.

Таблица 3. Результаты вычислений нелинейных уравнений баланса.

Контур 1
	7,4205	5,7363	4,8038	4,2469	3,9115	3,7321	3,5778	3,5314	3,2455	3,1507	2,9208	2,5253	1,7619	0
	0	3,0264	4,4664	5,2730	5,6846	5,9947	6,1087	6,1974	6,6284	6,7905	7,0973	7,6366	8,6203	10
Контур 2
	10	7,4205	5,7363	4,8038	4,2469	3,9115	3,7321	3,5778	3,5314	3,1507	2,9208	2,5253	1,7619	0
	0	3,0264	4,4664	5,2730	5,6846	5,9947	6,1087	6,1974	6,2225	6,6284	6,7905	7,0973	7,6366	8,6203

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

Рисунок 7. Развернутый график сходимости алгоритма по данным таб. 3.

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

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

Рисунок 8. Случаи не сходимости алгоритма.

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

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

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

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

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

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

Разработанная программа

Для ускорений расчетов в процессе исследования была написана консольная программа, блок-схема алгоритма которой изображена на рисунке 9. Блок-схемы функций, используемых программой, приведены на рисунках 10 и 11.

Рисунок 9. Блок-схема программы

Рисунок 10. Блок-схемы функций программы (Часть 1).

Рисунок 11. Блок-схема функции (часть 2).

В отличие от описанного ранее алгоритма метода тангенсов, алгоритм программы имеет некоторые отличительные особенности. В частности, составление нелинейных уравнений происходит внутри программы исходя из исходных данных, после чего сразу решается. Кроме того вместо нумерации шагов и итераций была введена система буферов, позволяющая хранить три различных значения. Так же здесь не указаны некоторые функции, как например функция инициализации исходных данных () и функция задания начальных условий (), а так же функции вывода результатов, и т.п. Программа писалась на языке C/C++ в программной среде
Microsoft Visual Studio 2011, под 32-х битную версию Windows 7.

Расшифровки и пояснения

Исходные данные:

·

·

·

·

y=((1E-08)∙x3)+(0,0039∙x2)+(0,2407∙x) + 1512        (13)

График с аппроксимирующей линией функции (13), с прогнозом вперед на 200 периодов изображен на рисунке 17.

Рисунок 17. Полиномиальная аппроксимация степени 2 для объема
выделенной памяти, с прогнозом на 200 периодов вперед.

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

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

Литература

1. Абросимов Л.И.

Базисные методы проектирования и анализа сетей ЭВМ: учебное пособие / Л.И. Абросимов. – М.: Университетская книга, 2015. – 248 с. – ISBN 978-5-98699-153-5.