Исследование дискретных математических моделей систем коммутации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК РЕСПУБЛИКИ БЕЛАРУСЬ ИНСТИТУТ МАТЕМАТИКИ

РГб о

2 1 ПАР М На правах рукописи

ЛОШКАРЕВА Светлана Юрьевна

ИССЛЕДОВАНИЕ ДИСКРЕТНЫХ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СИСТЕМ КОММУТАЦИИ

01.01.09 — Математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Минск 1994

Работа выполнена.на кафадре уразнений катоматической физики Белорусского Государственного Университета им. В.И.Ленкна.

Научный руководитель - кандидат фиаико-штематических наук, доцент Горлов Валерий Васильевич

Официальные ошюнонти: доктор физико-математических наук,

профессор Метельский Николай Николаевич;

кандидат технических наук,

доцент Шпаковский Геннадий Иванович

Ведущая организация - Вычислительный центр Академии Наук . Российской Федерации

Заздта диссертации состоится " £ •" ¿'¿/у/.^с'л^г3 1994г, в часов на заседании специализированного совета

К 006.019.01 по присуждении ученой степени кандидата наук в Институте математики Академии Наук Беларуси по адресу: 220072, г. Минск, Сурганова, II.

С диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси.

- Автореферат разослан " & " ¿¿¿¿У/^Г*} 1994г..

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

д.И. Астровский © Лошкарева С.О., 1994

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

оль диссертационной работы состоит в следующем: . Получить оценки временных параметров систем коммутации, писываемых математическими моделями " Л-сеть". . Получение формул для. временных и сложностных параглетров роцесса полного обмена информацией в системах коммутации со труктурой, описываемой различит,от классами графов. агчная новизну. Получены оценка для среднего времени функциони-ования модели типа Л-сеть при реализации в модели произволь— ого пакета связей. Предложен алгоритм реализации пакета связей этой модели. Для этого алгоритма получена форлула для среднего исла тактов реализации пакета связей близкая к нижней границе редка го времени функционирования моделей типа Л-сеть. Найдены ормулы для числа пакетов связей /перестановок/, реализуемых П/-сетью за минимальное время, и для максимального числа актов реализации перестановки. Получена верхняя оценка среднего ремени реализации перестановки в Л-сети. Для модели системы комя/утации со структурой "полный граф"

получена формула, задающая среднее время реализации пакетов связей, сдасываеьда: перестановками. Найдены формулы для значащ параметров, характеризугашх время обмана и загрузку систвш при полном информационном обмане в мододях со структурой "связан— най граф", "двудольный граф" и "дерево". Апообатая работу. Материалы длосертации были доложены на II и III Всесоюзном семинаре по диокретной математике, У1Г и У111 и IX Всесоюзных конферэвдаях по теоретической кибернетике, I и П Республиканских научно-практических конференциях творческой молодежи, на 71 Международной конференции по теории сложности, на II конференции математиков Беларуси. Публикация. По материалам диссертации имеется 9 публикаций. Сттягктура и объем работы. Дисоертация состоит из введения, двух глаз и библиографии из 42 наименований. Общий объем работы составляет 85 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

Д петаой главд рассматривается дискретная модель сиотеш коммггации типа Л,-сеть.

-сеть ^^ связывает А/= Л * входных и выходных полю сов и состоит из А/ каскадов, занумерованных числами

от I до & . В каждом каскаде расположено ^/Z промежуточных узлов, занумерованных сверху вниз в лексиографическом порядке двоичными наборами длины С Путь связи cJ.fi

>т входного полюса о номером «Г = 2 ... до выходного голюса о номером р = ... / т.е. реализация связи а^ / определяется двоичным разложением чисел 5" И р : в К -ом каскаде сети, К £ £ связь поступает на промежуточны® узел з номером через входаой полюс узла о

зомером <1к и покидает этот узел через выходной полюс с номером

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

В первом параграфе рассматривается модель с централизованным установлением приоритетов и разделением связей. ОПРЕДЕЛЕНИЕ I. Пакетом связей а $ е называется произвольное непустое множество наборов .из 0 и I длины 2 £ вида ЗГ— - -{¿±...<¿1 /31... ре У где Xрассматриваетея как номер входного полюса ЛЪ-сотп $ £ , а уз = как номер выходного полюса сети, которое адресована связь, поступившая на входной полюо 5* ,

ОПРЕДЕЛЕНИЕ 2. Расстоянием ^[Л/Ъ) между полюсами оэти и называется число

где

Пусть и ¿"(Г — произвольная пара связей в ,

ОПРЕДЕЛЕНИЕ 3. Связь <¿¡0 имеет приоритет перед связвю если <^сгО, ^ .

Доказало, что при ^(Л/а) (/7.? связи О^з и не блокируют друг друга.

Рассматриваемая в § 1.1 модель функционирует следующим образ

1. На входные полюса сети $ $ подается пакет связей ЗГ .

2. Находится множество И(Я\={]>1 За/ь

3. пусть II (л) = {$>ь, ^ <°> "

Тогда вначале в Л -сети реализуются связи Ар , для которых ) ; затем эти связи удаляются из пакета Я" и реа-

лизуются связи с расстоянием между входом и выходом равным ^ и.т.д.

ОПРЕДЕЛЕНИЕ 4. Числом тактов реализации пакета У в данной модели называется число (ур) — / (Я) I

Пусть Тр {?) ^ ~Г(С - среднее число тактов

реализации пакета в Л -сети . Основной результат § 1.1: ТЕОРША 1,1.4 _ . е

Тс = & (¿-я Ь

т.е. ТС Ш ~Xе*

Во втором параграфе первой главы рассматривается, модель с децентрализованным разделением связей. Эта модель также имеет структуру Л -сети, пакеты, связей те же, что и в предыдущей модели / определение I/.

ОПРЕДЕЛЕНИЕ 5, Пусть ¿1уЭ - произвольная связь. Расстояние (<Ир ) ; 4 ¿X 4 задается следующим образом:

где _ го. , сХ«>/Зк £

Предполагается ,что J>o J = J>i Рассматриваемая в § 1.2 модель функционирует следующим образом:

1. На входы Л -сети подается пакет связей Ж .

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

3. Входные полюса сети рассматриваются как нулевой каскад. Тогда связи пакета, не блокированные в К-L ~ом каскаде сети, 1 поступают в узлы К -го каскада.

4. В случае, если две связи поступают одновременно на один и тот же выходной полюс L промежуточного узла И каскада о номером

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

5. Множество 14 £ связей из пакета "Ж , нэ блокированных в Л -сети, считается реализованным в первый такт работы пакета и удаляется из пакета ЗГ .

6«, Часть связей пакета ЗГ не реализованная в J ~ый такт работы пакета, т.е. множество связей 3T\(i4i I/ 14z\/,.. I/ Mj ) по правилам 1-5 реачизуется в J + 1 -ом такте.

Таким образом,все множество связей пакета JT однозначно разбивается на непересекающиеся подмножества U £ ) ___) U^

такие,что связи из U'L не блокируют друг» друга, но блокируют

связи из U i+± ' ..

к

0ПР1ЦШЛШИЕ б. Пусть JT = . I/ М; Ui /? ~0, тогда числом ■

t=1 > о

тактов реализации пакета Ж в данной модели называется число

Основные результата § 1.2 изложены в следующих теоремах» ТЕОРЕМА 1.2.3.1. Максимальное время реализации пакета связей в сети разно

/яа* +

Пусть 1~п (£) = Л ¿Т -среднее число тактов

сС

реализации пакета связей в Л -сети в рассматриваемой модш ТЕОРЕМА Г.2.4.2. , ,

Из теорем £.2.3*1 и 1.2.4.2 следует:

^ тг-ртьеи пко^граФе первой главы рассматривается реализация пакетов, описываемых невыраженными перестановками

р

\ 1о Ч ' * ' /

в модели, функционирование которой описано в 6 1.2. В перестанов шэ Р число (-(( определяет номер выходного полюса Л-сети для связи, поступившей на К-ый входной полюс. Основные результаты этого параграфа содержатся в следующих теоремах: ТЕОРЕМА 1.3.1. Пусть Р — невырожденная перестановка, (Р) ' число тактов реализации перестановки в модели. Тогда

_ (я-*** - ем

7х т* р> ' ий^-МА-х, е.асч

а

Пусть Т0 = (<£ ¡) 7~т\ (Р) - среднее время реализации н р

фестановки в <А -соти £ ЮРЕМА Г.3.2.2

[л (е-*) л - (е-и/г ; е^лкя

ТР(е)- р (е-1) * _ (е-я)/я -I;

ЗОРЕМА Г.3.3. Число перестановок, реализуемых Л -сетью I один такт, равно Я ^ , где М - С' Я .

В петаом пашгщ<Ье второй главы рассмотрена дискретная мато-«ическая модель системы коммутации со структурой "полный граф", редставляющая собой полный граф о помеченными вершинами Кп . прюины Кп рассматриваются как процессоры, обладающие в началь— 1й момент времени информацией, дуги Кп — как каналы связи, здель функционирует следующим образом:

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

. Для разрежения конфликтов используется следующая система лрто—

ятотов: если - номера процессоров, от которых

процессор £ поступили требования обмена / приема или передачи

нформзции/, то будет осуществлена связь с веракной р, где

Э=г «1Г/1 р1 ; если процессор, находящийся в вершине Р 1 - V (Ь.

анят, то реализуется следующее по приоритетности требование.

Па,чзтн связей являются ношроъдэннши перестановкам;! без еподвгешгх точек, т.е. VI I . Пусть и п - удо-

бство таких перестановок, 7~ (7Г) — время реализации пакета Тер Сч) I I Т(Л~} - среднее вромя реализация.

ТЕОРЕМА 2.1,1

где

'с/, М = Дз-u)^ , п--и .

вд втором параграфе второй главы рассмотрена задача о полном обмене информацией в системах коммутации, структура которых описывается различными классами графов. Эта . модель была предложена в Г31 . В дальнейшем Г 5" Л данная модель исследовалась для систем со структурой "связанный граф" и " дерево".

Пусть (г - (V) ) — граф со множеством вершин /процессоров/ V и множеством дуг / каналов связи / Е . Пусть G-n f , ~Г/г обозначает соответственно множество воех связанных графов / бее петель и параллельных дуг /, множество всех деревьев и множество воех двудольных графов о Л вершинами.

Отображение V множества дуг в множество Z всех под-

множеств множества натуральных чисел называется допустимым отображением /или расписагшем работы системы/ если: I. Для любых смежных дуг е, е' € Е Wey f\ f(e') = 02. Для любых двух различных вершин xft XtTe И существует монотонный (V) иГ)~путь, т.е. такой путь

^аГ г/ ¿а /Г..,г что оуществуют числа >С[ £ f(б^У такие,что

Х{ < Хл < .. - < Хг. 3. Для любой дуги е и любого числа Д е *Р(е) для

отображения такого.что

>' te') - |

^ieO ¿е'Фе

но выполняется условие 2. 8

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

Пусть М(йг) обозначает множество всех допустимых отображений графа . На множестве пар <р), где £ ) и №(

вводятся следующие функционалы:

(6-, V) Е (0-, V)

а> (ь

тах | \у у (в) | • чге1/ ее£ яГее

Функционал »ложно интерг ротировать как суммарно а время

работы; Е(в-у V) - как число используемых: каналов; ~Г *Р) ~ как число тактов параллельного обмена информацией. <2? (<£/ У) можно интерпретировать как максимальную загрузну канала связи, а С (0-) ¥ ) - как максимальную загрузку процессора.

ее£

' .{{ее £ : *(е) ф I

I V 4>(е.)\

еее

так I ?(е) I е<? Е

и.гл)

С(Ы) =

Пусть обозначает один из класоов функционалов (Х..2. I )3 а X - один из классов &п} В>п.; Тц. • Рассматривается функции:

(Х.п) - (пип тхп (=(£. Г) 1 ' 6-ех

Рх (Х,п) ттп тау Я^/РУ

Р, (Х.п) - тсх тхп 3 б-ех Гел/М

(Х.п) = Г) •

* ' 6еХ Гет)

В § 2.2 найценй явные формулы для каадой лз функций /Г^J рз ^ рц для различных классов графов* Основные результаты полученные в данном параграфе, вместе о результатами, полученными в Г-3-&3 приведены в таблице I. Результаты, полученные в § 2,2.занимает весь третий столбец и все последние восемь строк таблицы

Таблица X

6n Tn ßn

bi Яп-Ч hr/4 Zn-3 Zn-Ч

Lz Zñ -3 Zn-3 Zh-3 h***

Ls, Zn-3 Zh~3 Г\ъ4 Zn-3

L, Ь « (!) Zh-3 KA n^zk n -ZK+l

/7-1 л-i h-1

Ex h-i h-i

fi-i ft—i h-í

(TT h-í К*- n*ZK

T, Zl&fahí-i ¿ffi.ru n^Zp C&fanl+í n~Zp+Z&

T2 2n~3 Za~3 Zñ-3

..7У Zñ -3 Zn-3 Zh-3

Ъ f ^ r4 i m Zh - 3 K*- n=ZK к+л n=ZK+±

3bd ± Z h?Z Z h

«в*... 2. h?Z Z r>?Z Z n?Z

Я h?Z Z П7Л z

Z h?Z Z Z h

Ci ¿t h*<i

Cz ч h*3

Сз Zñ-3 n*Z Zh-3 h*Z Zh-Ъ h ?Z

c« Zn~ 3 ji ?z Zn~3 /1.5*1 Zn-3 n * 2

Автор выражает свою глубокую и иокренга» благодарность своему научному руководителю В .В. Горлову за постановку задач и постоянное внимание к работе.

Основные результаты диссертации опубликованы в следующих работах:

1. Лошкарева С.Ю. С числе пакетов связей реализуемых Л-сетью в один такт //проблемы теоретической кибернетики: Теэ.докл.УЫ Всесовз.конф.-йркутск,1985.-С.125~126.

2. Лошкарева С.Ю. Об одной модели систем коммутации// Проблемы теоретической кибернетики: Тез.докл.НП Всесоюз.конф..-Горысий,1988.-Ч.2.-С.20.

3 .Лошкарева С.Ю. О прохождении пакетов связей через Л .-сеть // Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Тез.докл.1 Республ.науч.-практ. конф.творческой мсяодежи.-Минск,1988.-С.169.

4. Лошкарева С.Ю. 0 числе пакетов максимальной сложности в сети// Вестн.БГУ.С9р.:Физ.-мат.науки»-1988.-М.-С.6?.

5. Лошкарева С.Ю. Пакеты связей в К~ -сетях// Труда семинара по дискретной математике и ее приложениям/ Под ред. О.Б.Лупанова.-М.:Изд-во Моск. ун-та, 1999..- С.154-155.

6. Лошкарева С.Ю. 0 реализации произвольного набора векторов *!Ь~ сетью// Актуальные проблемы социально-гуманитарных и естественных наук: Тез.науч.конф.посвяденной 70-летию Б1У.-Минск,1991,-С.192.

7. Лошкарева С.Ю. 0 применении бесконечномерных вычетов при вычислении некоторых комбинаторннх сумм// Материалы 47-ой науч.-технич.конф.посвященной 70-летию ШИ.-Минск,1991.-Ч,1.-С,166.

8. Лошкарева С.Ю. О функционалах "максимальная загрузка канала" и "максимальная загрузка процессора" в задаче о полном обмене информацией// Тез.докл. II конф.математиков Беларуси.-Гродно, 1992,-Ч.4.-С.87.

12

9.LoshKctryoi'a S. Some Characteristics oj the Graph Inform a tion Exchange Systems // J.Ttifprm. Process. Цвете*. (i993rVoJ.13, ¡Jo ZrP. ir^oo.

Список цитированной литературы:

1. batcher (<.Е. Soring A/etvorKs <W Шгг- tyffcca-trons //Spring Joint Computer Conference, - /36*, ~ p. 30/-3J3.

2. Горлов В.В.,Шпаковский Г.И. О системе коммутации многопроцессорных ЭВМ // Модели информационных сетей и коммутационных систем: Сб.науч.ст./АН СССР. Ин-т проблем передачи информ.; Ред.: А.И.Харкевич и дт>.-М.:Наука,1982»-С.12У-135.

3%hajr\a£ Ач mzitier ¿летегес/х £, О Cure

jor Telephone Юг s ease //Con. /71а¿-b. B.t J972, -iS'l^J.- P.

A.Tha Teinphant Probft'm for Connected Graphs / Btirosch 6., G-or^ou,' liiW.jLaSahn Sxemvrec/u // //

£ГК : - лт. - Шло, fa do/u p. ss/~573.

5. Labcthn A\ The Те Cephone Pro #¿#/>7 for Trees . //

ЕГК, ~ 1Ш. - Vo e ы t A/o 91 - P. У Г6~.