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

л \ ' /

Г) '

Ленинградский ордена Трудового Красного Знамени институт точной механики и оптики

На правах рукописи

ЖУРАВЛЕВ Олег Владимирович

УДК 681.324

МОДЕЛИ И МЕТОДЫ ИССЛЕДОВАНИЯ МНОГОПРОЦЕССОРНЫХ УПРАВЛЯВШИХ КОМПЛЕКСОВ С ПРИОРИТЕТНОЙ ОБРАБОТКОЙ ДАННЫХ

05.13.13. - Вычислительные машины, комплексы, системы и сети

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Ленинград - 1Э90

Работа выполнена на кафедре вычислительной техники Ленинградского ордена Трудового Красного Знамени института точной механики и оптики

Научный руководитель - кандидат технических наук, доиент

I

Т.Н. Алиев

Официальные оппоненты: доктор технических наук, профессор

О.М. Брехов

кандидат технических наук, старший научный сотрудник Г.Г. Сигалов

I

Ведущее предприятие - ЦНИИ АСУ ГА г. Рига

./¿тУращита диссертации состоится . 1990г. в

часов на заседании специализированного Совета К С53.26.04 Ленинградского ордена Трудового Красного Знамени института точной механики н оптики (197101, Ленинград, Саблннская, 14)

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

Автореферат разослан " "_ 1990г.

Ученый секретарь специализированного Совета, доктор технических наук,

Профессор Е.С. Моисеев

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

ВВЕДЕНИЕ

вычислительной техники в различного рода системах уг1равления объектами и процессами. Возрастающая сложность объектов управления п широкий диапазон применения вычислительны), машин, реализуемых в последнее время на базе микропроцессорной Техники, приводит к повышению требований по их производительности, надежности и эффективности организации планирования и управления вычислительными процессами, Одним из эффективных способов организации управляющих средств, позволяющих обеспечить требования по временным и надежностным характеристикам, является использование многопроцессорных управляющий комплексов (МУК)* Исследование таких сложных объектов как МУК проводится на моделях, отображающих основные особенности их ФункцИониройания. Для моделирования процессов случайного характера поступления и обработки запросов в МУК используется аппарат теории массового обслуживания (ТМО), позволяющий получить качественные и количественные оценки характеристик функционирования при изменении рабочей нагрузки, способов обработки Данных, Числа и быстродействий устройств, конфигурации МУК. Достаточно полно структурно-функциональные особенности организации МУК отображают модели ТМО, представляемые в виде систем (СМО) и сетей (СеМО) массового ' обслуживания. При наложении ряда ограничений на параметры моделей, их расчет возможен с использованием точных аналитических методов. Поскольку, в случае неоднородного и неэкспоненциального характера нагрузки, приоритетна)! способов обработки данных, затруднено создание в общем виде таких методов, то важной проблемой является разработка Приближенных методов. Разрабатываемые приближенные аналитические методы направлены на решение двух взаимосвязанных задач исследования ИУК - анализа и синтеза. Алгоритмизация методов реаения этих задач 1 Н их реализация. позволяет создать инженерную методику системного проектирования МУК и обеспечивает не только проведение мероприятий по улучшению качества функционирования, но и суп1ественно сокращает затраты и повышает степень' обоснованности принимаемых решений на этапе предварительного проектирования.

предметом исследований являвтся кногопрси-тссорнш* упюрхяжше комплексы с приоритетной обработкой данных.

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

Указанная цель достигается решением следующих задач: ,

1) разработкой аналитических методов расчета системных характеристик с приоритетными дисциплинами обработки запросов в процессорах на основе моделей ТНО, допускаюаих точное регоение.

2) разработкой и тщательной аттестацией с использованием имитационного моделирования приближенных истодов расчета системных характеристик МУК с неоднородной приоритетной нагрузкой на основе многоканальных СМО и замкнутых СЕМО:

2) разработкой метода оценки комплексной производительности с учетом реальной нагрузки процессоров и приоритетного способа их арбитрам;

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

5) разработкой инженерной методики системного проектирования МУК, реализованной в виде комплекса программ.

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

Научная новизна работы.

1. Разработаны точные л приближенные аналитические методы расчета средних характеристик асинхронно-организованных КУК с неоднородной приоритетной нагрузкой;

2. Иа основе разработанных методов расчета проведены исследования, позволившие выявить свойства, присущие МУК с асинхронной организацией и приоритетной обработкой данных.

3. Разработана методика оценки и проведено исследование комплексной производительности магистральных МУК на модели конфликтов с учетом реальной загрузки процессоров и возможности организации приоритетного арбитража.

4. Разработаны методы распределения неоднородной нагрузки в МУК с аеннкронкол и синхронной организацией.

5. Разработана кнженериак методика системного проектирование КУК с неоднородно'; прпогжтлтноГ; нагрузкэС:

Практическую ценность работы представляй-.':

3 ; инженерные методы анализа, синтеза I! методика системного проектирования ПУК с приоритетной обработкой данных и .заданным;« ограничением»! на времена пребывания запросов разных классов.

") комплекс программ, реализующий-методы анализа, синтеза и методику системного проектирования МУК с приоритетной обрлботкой цантп.

Реализация и внедрение результатов исследований. Ра-работшшая методика и комплекс программ системного исследования и проектирования МУК на основе аналитически:: моделей ТМО и теории расписаний внедрены в ряда организаций, занпмагедихся проектированием и эксплуатация МУК, а таю.е использовались при проведении научно-исследовательских работ по хоздоговорной тематике и учебно:; процессе на кафедре В? ЛИТКО. Достигнутый экономический и технический эффект подтверждается актами а гнэдреник.

Апробация работы. Основные результаты диссертационной саботи докладывались и обсуждались на еяедукщи;; конференция;; и семинара;:: IV всесосоюзной школе-семинара "Распределенные автоматизированные системы массового обслуживания" {Кутаиси, 1987); XI Всесоюзной ыкояе-семинаре "Вычислительные сети" (Одесса, 1986); X Всесоюзной школе-семинаре по теории телетргФика (Батуми, 1388); научно-технической конференции профессорско-преподавательского состава ЛИТМО (Ленинград, 1909);

Публикации. По материалам диссертации опубликовано весень печатных работ. Компоненты программного комплекса сданы в ГоеФЛП.

Структура и объем работы. Диссертация состоит из введения, -ттырех глав, списка литературы ( 102 наиненсваннЯ) и.приложения. Эбъен работы - 120 страниц машинописного текста, 13 рисунка, 15 таблиц.

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

Первая глава работы посвящена принципам организации МУК, постановке задач анализа и синтеза, инженерной методики системного проектирования.

Анализ общих принципов организации управлявших комплексов позволил выявить особенности, присущие им, в том числе

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

Исследование МУК предполагав^ построение множества моделей, учитывающих перечисленные особенности. Для определения диапазона этих моделей проведена классификация МУК на основе ряда признаков. Так в зависимости от моментов поступления и длительностей обработки запросов, выделены комплексы со"случайным характером поступления и обработки запросов (асинхронные) и. с детерминированным характером (синхронные). Запросы, поступающие в комплекс от объекта управления могут бить зависимыми, если очередной запрос одного класса поступает после окончания обработки предыдущего запроса этого же класса, и независимыми. Среди признаков для классификации МУК также используются: способ организации оперативной памяти (общей, локальной и смешанной), тип нагрузки (однородная и неоднородная); способ диспетчеризации (приоритетная и бесприоритетная); ремонтоспоеобность (с истомением и восстановлением процессоров); организация обработки данных (симметричная и распределенная).

Основным направлением, Принятым в работе, является разработка на основе аппарата ТМО аналитических методов, позволяющих получить результаты на этапе анализа в явном виде и использовать их при разработки методов решения задач синтеза. Разделение моделей ТМО, отображающих Функционирование комплексов с различной организацией поступления • и обработки запросов, проводится на основе признака зависимости моментов поступления запросов. Наибольшим концептуальным подобием обладают модели в виде Многоканальных СМО и двухфазных ЗСеМО, описывающие соответственно независимый и зависимый характер поступления запросов. Традиционные методы решения этих моделей не учитывают неэкспоненциальный характер обработки запросов разных классов, наличие приоритетов между ними.

Для описания моделей используется совокупность параметров: вычислительной нагрузки ( й--средний интервал поступления запросов, $ - средняя трудоемкость их обработки); структуры (И -чисао процессоров, V - и* быстродействие); управления обработкой данных; конфликтов ( - средний интербал обработки

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

способы управления обработкой данных разных классов на основе дисциплин обслуживания (ЛО) со сметанными приоритетами (СП).

Такие ДО задаются в виде матрицы приоритетов (МП). Элемент МП

*

определяет отношение приоритетности £■ -класса запросов к ^'-классу. Если Ц'У ~ 0 " нет приоритета (БП) , - 1 -

относительный приоритет (ОП), = 2 -абсолютный приоритет

(ЯП).

Эффективным средством исследования МУК является метод средних значений, приемлемый в ин.тенерных приложениях. Разработка приближенных методов расчета моделей ТМО требует проведения мероприятий по их тщательной аттестации, Универсальным средством аттестации приближенных методов является имитационное моделирование, реализованное в работе на алгоритмическом языке (лРЗБ для ЭВМ ЕС-1045 и "Искра 1030". Аттестация разработанных приближенных методов проводится также с помощью существующих й разрабатываемых точных методов.

Во второй главе описаны методы анализа системных характеристик ЛУК с асинхронной организацией поступления и обработки независимых запросов.

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

В качестве модели функционирования МУК с асинхронной организацией поступления и обработки независимых запросов используется модель в виде многоканальной СМО. Число обслуживающих приборов в модели равно числу однородных процессоров Н . В.СМО поступает Н классов запросов, которые образуют простейшие потоки со средними интервалами поступления Д; ,..., . Вычислительная нагрузка предполагается однородной, т.е. длительности обработки запросов разных Классов распределены по экспоненциальному закону с одним и тем же средним с . Емкость накопителя многоканальной СМО может быть ограничена в зависимости от значения емкости буфера в МУК $ или неограниченной, если емкость памяти, отводимая под буфер входных данных, достаточна для размещения любого числа запросов.

Лля расчета средних значений системных характеристик МУК с

однородной нагрузкой и ДО СП з случае нрогрянич^нчого и ограниченного буфера входных данных были ;дзра*етаии точки', .методы расчета.

¡Заражения для расчета ср»,дн«>1 ¡ниш очереди ¿¿ вероятности заполнения ограниченного буферл вход.чих дашы..

запросами & -класса получены на основе законе, '•охганвн!'.;: по';.: г енной кэгруэкп: С fíí'fí'-^iMjllS t , где - (/, ¡Uf:.¡¡J Прочей evi

исследования влияния приоритетов на системные характеристик.! обработки запросов дкя комплекса, ьинолнлацего Фунпп..,! коммутационных средств ъ узлах сети передачи дчш.ьи, прегстезленного в виде разомкнутой двухфазной СеКС. Нсследо.з.чпп?; показали, что для ДО СП при сильной ограниченности ккодннк

данных ( »£< // ), из-за значительных потерь низкоприоритетных пакетов, их средние; временные характеристик и обработки .могут иметь меньшие* значения по сравнению с соотаетстсугмаднш характеристиками обработки данных высокоприоритетных классов. Такое свойство произвольного упорядочивания средних вреисл о.кнданиа и пребывания 11L обработки данных ¿¿-класса

прояюлается при ДО Oí! и ДО СП, схожих с ДО ОП. Описанный эффект обусловлен тем, что среднее время о.т.идания обработки данных ¿-класса определяется ьез учета пакетов потерянных по причине полной занятости буфера входных данных, а также пакетов, стесненных высокоприоритетными пакетами данных: 'Id¿

Для ДО СП в предположении однородности нагрузки МУК с емкостью буфера, достаточной для размещения данных любого числа запросов, получены точные аналитические зависимости, позволлюдие

вычислить средние времена ожидании ¿ .....'¿¿¡¡у запросов классов

1.....Н и на их основе средние времена пребывания:

На основе аналитических выражений проведен анализ влияния числа процессоров на временные системные характеристики обработки данных разных классов. Выявлены свойства МУК при условии сохранения суммарной загрузки комплекса, которое может быть достигнуто двумя способами: 1) увеличением интенсивности поступления запросов; 2) увеличением времени обработки запросов в процессорах за счет использования процессоров с меньшим быстродействием V . Установлено, что в первом случае время ожидания и время пребизания 'Ж запросов уменьшается с ростом

числа процессоров, а за втором случае Бремя пребывания 2¿'

растет, несмотря на то, что время ожидания '1£' уменьшается.

• i

Про:- нм!с .. т. "Ра такл:-:- покамли, что при у<гелич«наи числа п;ь-и.?<7roi'OL- з .Lu ръъ скоткг-ыениг значении Л/ ¡i >ú равно-:'-':

V/ií-К.

йриолижчннля нетоллка расчета МУК с приоритетно)! неоднородной >«гг.умсл|1 заключает он а' прс-обра зовпнии модели вида /Чн/fcf/A' с г.роьзг.олыимй законами распределении времен обработки запросов и г'кэига."гмм'нум чо производительности модель вида Мн/Си/^- путем поел«до»«тельного пересчета параметров.

lia перзом этап*» "pe о opa зова ни я осуществляется переход от bnjif.'i'i с MfottKcpo/iHUM потоком запросов к модели с однородном потопом: суммарная интенсивность 0¡.)среднее время

обраочтг.и fi -/'лj¡.hjj\ ; коч.К'нииент вариации длительности otípaoci'itn запросов . í'a, ~ ¡C)'j£ , где ¿Ú - дисперсия длительности обработки.

Из следую«."!' этапе - переход от многоканальной СИО с

однородной нагрузкой, каждый из приборов которой характеризуется —т

быегродейстпиек /• , к оянокаиальиой СМО с эквивалентны).;

быстродействием - '/ , где - поправочный коэффициент

времени обработки запросов. Коэффициент определяется из условия эквивалентности моделей, основанном на равенстве отиогаенш: средних времен ожиданий запросов в многоканальной и озноканальноц СУП: ■ Коэффициент поправки времени обработки

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

Последний ?тслп - подстановка значения ^ п известное аналитическое „рига^енпг; среднего времени ожидания запросов э подели вида / О}* /1 с ДО СН. Выбор в качестве основной характеристик.!! преобразования среднего времени о.т.пданил объясняется его оольиен чувствительностью по сраьненшэ со временем пребывания.

При проведении аттестации (около 300 экспериментов) разработанного приближенного метода расчета характеристик функционирования М!>К с приоритетной неоднородной нагрузкой было установлено, что при ДО СП погрешности среднего времени пребывания ясех классов запросов во всей диапазоне за.рузок не презнгаает 20%. Максимальные погрешности ьременп пребывания наблюдаются для ДО оП при равенстве нагрузок всех классов, неоднороднее!и их времен обработки и различном способе назначении приоритетов ме.тлу ними. Детальный анализ позволил выявить эффект

?

изменения средних времен ожидания запросов в НУК по сравнению с однопроцессорными системами.

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

Характерной особенностью МУК с зависимым поступлением запросов всех классов является опрос датчиков управляемого объекта, проводимый только после окончания обработки предыдущего запроса соответствующего класса, т.е. в любой момент времени в комплексе может находиться не более одного запроса каждого класса. Для анализа характеристик обработки зависимых запросов в МУК используются модели с конечными источниками запросов, представляющие собой двухфазные замкнутые сети массового обслуживания. Первая фаза модели представляется в виде /^-■многоканальных СМО без очереди, -приборов в каждой из которых отображают процесс поступления запросов ¿-класса в МУК. Количество заявок /6-класса, находящихся в ЗСеМО равняется числу приборов ¡-¡Л /¿-многоканальной СМО. Время подготовки запросов распределено по экспоненциальному закону со средним значением (¿=1,Н). Вторая Фаза модели отображает процесс обработки запросов процессорами и представляет собой совокупность одноканальных СМО с очередью. Длительности обработки запросов разных классов распределены по произвольному закону со средними значениями и коэффициентами вариации . Выбор запросов

из очереди на обработку выполняется в соответствии с ДО СП.

Сложность разработки заключается в том, что даже для однопроцессорных систем в случае произвольных законов и приоритетных ДО не существует точных методов , которые могли быть использованы при решении задач синтеза, а известные приближенные методы дают большие погрешности. Для двухфазной ЗСеМО с обслуживанием заявок на основе статических ДО СП разработан приближенный рекурентный метод расчета верхних и нижних оценок характеристик обслуживания " заявок, позволяющий значительно снизить погрешности расчета характеристик по сравнению с известными алгоритмами. Расчет характеристик дфухф&зной йСеМО ^ с ДО СП проводится по ргкурентной схеме, начиная с вектора <( ,

иного (0.....0) последовательно прибавляя по одной заявке к

з'-дому классу в векторе X ' и используя зависимости верхней ¡¿"^ и нижней У^с."^ сценок времени пребывания, определяются рактеристики обслуживания всех классов заявок, начиная с заявок мого высокого приоритета. Процесс вычисления ведется для зличных состояний вектора текущего числа заявок & ' ~ (Л* ,,.., // ) при условии,что А^ ^И/с. • тех пор пока вектор А. " не анет'равным вектору ННа)•

Тщательная аттестация данной модели (было проведено около 200 епериментов) показала, что погрешности расчета среднего времени ебывания не превышают 15%, а погрешности загрузок приборов и тенсивностей движения заявок разных классов не превышает 10%. ихение погрешностей расчета характеристик обработки запросов стигается за счет: использования _п£и расчете ммарных загрузок и классов, имеющих более

сокне_приоритеты (АП или ЙП и ОП) и полученных для текущего

ктора А ; усреднения на каждом шаге верхних и нижних оценок емени пребывания.

Аналитическое исследование МУК с зависимыми запросами на дели в виде ЗСеМО показали различный эффект назначения иоритетов по сравнению с разомкнутыми моделями. Например, при

больших загрузках процессоров классы запросов с

¿«у

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

Для определения комплексной производительности МУК через эффициенты снижения быстродействий , . . . , процессоров

....И используется модель в виде двухфазной ЗСеМО. Первая Фаза дели отображает процесс обработки команд, программ, их частей оками обработки, а вторая фаза - процесс арбитража и доступа оцессоров к общей памяти I! внешним ресурсам. В частном случае ной общей магистрали модель представляется в виде ЗСМО.

С целью определения коэффициентов ОС-1. (¿=1,М) снижения

ш

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

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

Известные методики расчета комплексной производительно ориентированы на случай предельной загрузки процессору» з^дач.-.ж а значит, на случай максимальных конфликтов. С цель:о учи реальной нагрузки процессоров ( ,11- 1,1':'), обгабатидег-л.

поступающие запросы в заданные временные сроки, разработ.» методика оценки фактического числа конфликтных ситукций. Дли:": методика основана на анализе всевозможных комбинаций чне; конфликтующих процессоров при доступе >с обшей систеиж магистрали и решается с использованнен комбинаторных истодов.

Вероятность того, что в произвольный мококт времени в К'-'К симметричной обработкой конфликтует Л--процессоров равна:

Рц "-- С}/ ' ■ где - число сочетании из /'/ по//

& - загрузкс'1 одного процессора МУК, описываемого модель;? виде Мн/Сн/№.

На основе разработанного приоритетного метода средни значений и методики оценки фактического числа конфликте проводится расчет коэффициентов ( ¿-г 1,Н) снижения быстро

действия процессоров: п л 1 / /, г> \

¿& = (-2ЕИ /£ ■ С,1} / П*. ,

О

где £-¡1 - средняя длина очереди /¿-процессора при доступе г. об'::е магистрали. Комплексная' производительность \'1< с учета коэффициентов и номинального быстродействия процессор

В работе представлено также аналитическое выражение дг

расчета комплексной производительности МУК с функинг.нальич

разделением нагрузки по процессорам. Модель представляется б вид

совокупности одноканальнш: СМО. Если коэффициенты использованп

процессоров 1, . . . ,Н равны соответственно , . . . , . т

вероятность конфликта процессоров, образующих векто

/1 =( , • • ■ , Ки ) определяется' по следующей формуле: £ " I! И

равна:

Исходный коэффициент ОЦ снижения производительност

¿-процессора зависит от вероятности ) пребывания систем:

гост о янл !5 /1 л ер.?дк»?й длины очереди ¿-¿¡/'.у при доступе к *',.?!ямаг'истрп;т I -проигссора:

о

4/г, - «нскество всевозможных состоянии, описывающих >оимо,1«йстпия «шел« процессоров равного -/2- ( ¡1 = 1,Ы ).

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

,'¿е.'-'И конфликтов применяются при параметризации моделей стемнык этим^теристпк гаункционирования МУК. Так при расчете •чтннх зр«!»:1 обработки звпросо» ^ -класса используется

состн сыение: С^ — Ь^' / ¡¿^ , где - средняя

■■/лоемкееть обработки запросов у -класса.

Четвертая гла«-д посэягеена решению задач синтеза и разработки тоники системного проектирования МУК с приоритетной нагрузкой.

Лля )!У" с относительными ограничениями под минимальным числом

I

оияееоров /V// понимается такое число, начиная с которого мо.тет холиться ДО, обеспечивающая выполнение ограничений по времени ебыванмя запросов. Лля определение минимального числа онесссрок с учетом заданных оременннх ограничений используется глчпгнетко, у базирующиеся на законе сохранения времени = бнванпя: % .ЗрЕЗ^-/^.', где и соответствуют

?лпему времени пребывания и ограничению на эту характеристику прогон ¿-класса. Так как коэффициент поправки времени,

зпботки и модели 7//// определяется довольно сложной

снулой, зависящей от числа процессоров, то получение реиения п простого аналитического неравенства невозможно. Для ;еделечия минимального числа процессоров использована итерация, которой, параметром цикла является число* процессоров.

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

с со з, но и добиться требуемых вероятностей потерь иЛ^, . . . , росок, происходящих по причине полной занятости буфера ны >;.

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

^k 'RL.'/1!'ß/L'fo . На основе разработанного точноп аналитического выражения для расчета '^Х. ( -1,/ij и довольж простых проведанных преобразований получено еледуюые« неравенство: , Где аналитическое

выражение зависящее от /С , N , и ßfe9 . Полученное неравенств! представляет собой Необходимое условие существования ДО обеспечивающей выполнение ограничений на вероятности потер| данных разных классов,

При организации оперативной памяти как локальной, МУ1 представляет собой совокупность процессорных блоков (ПБ) объединенных общей магистралью. Задача выбора эффективны; способов обработки данных в ПБ тесно связана с решением задач! распределения нагрузки и размещения программ.

Задача распределения нагрузки для МУК с асинхронно! организацией Поступления и обработки запросов заключается i разработке эффективного алгоритма разделения неоднородно!

нагрузки ....., где Jfe -¿{. (йЛ'Рк'М. и разкешеки:

прикладных программ длиной ( {6=1,11) по № ПБ. При это!

ДОЛЖНЫ быть выполнены временные И структурные ограничения:

, где - ограничения По емкост!

локальной Памяти ПБ. Решение этой задачи распределения невозмпжт получить на основе формализованных методов, например "задач! назначения", по причине её многопараметрической ограниченности Разработан эвристический алгоритм распределения нагрузки п< критерию равномерного использования мощностей проиессороз i емкостей локальной памяти для всех блоков обработки Первоначально все Н классов запросов разбиваются на С множеств i зависимости от близости значений J^ . Каждое из С множеств упорядочивается по убыванию параметров J^ и , образуя внутр; Него два подмножества Cjry и . Дальнейшее выполнение алгоритме заключается в последовательном закреплении запросов ч программ и; обработки за одним из ПБ, до тех пор, пока значения ¿¿и Qu, суш соответствующих параметров назначенных запросов из приблизятся i средним величинам 6 ^ и ^ с допустимым!

верхними И нижними отклонениями. После назначения каждого и' классов запросов на ПБ в зависимости от соотношения коэффициенте] использования каждого из ресурсов (процессора и памяти^ следуюши класс запросов выбирается из соответствующих подмножеств С.^и Ср с целью выравнивания этих коэффициентов. Данный алгоркт;

овторяется N раз н при распределении на ft- -ПБ (i4=l,N) не »итывается нагрузка классов запросов, распределенных на ПБ^ . . . ,ПБ .

Задача распределения нагрузки в синхронных МУК решается на ¿терминированной модели в рамках теории расписаний и заключается составлении расписания обработки запросов всего множества яассов за интервал времени минимальной длительности, /чествующий алгоритмы не учитывают моментов и периодов эступления, ограничений на времена пребывания запросов

J3HUX классов. Разработанный алгоритм составления расписания *зируется на расписании с прерываниями низкоприоритетных тросов и состоит излнескольких этапов: определения длительности 1кла обработки 7"~ /М и его корректировки до величины Т'

эатной значению ф-mlnjO^ Л = 1,hJ. , минимальной из всех значений нтервалов поступления запросов, с учетом числа поступающих inpocoB за цикл T'j первоначальное распределение запросов: зрректировка распределения запросов за счет изменения моментов к поступления запросов с учетом временных ограничений.

Задача выбора способов обработки данных в процессорах или ПБ

сдается в классе ДО СП и сводится к определению значений

1ементов Цц МП , при которых выполняются временные ограничения: f. ,11 л /if

А^г Щ. . Разработка формализованных методов решения задачи ■бора оптимальных ДО является довольно сложной задачей и в общем )де не решена, что приводит к необходимости использования Зфектнвныл 'эвристических алгоритмов, основанных на гленаправленном переборе различных ДО. На основании юрядочености запросов по критерию Si> f^it+i 1ассам запросов имеющий меньший индекс ¡С- назначается приоритет ; ниже, чем запросам класса Отношение определяет долю

тустимого времени пребывания , отводимую под обработку о >оцессоре. В качестве первоначального варианта ДО может быть ¡брана ДО ОП или ДО АП. Каждый последующий вариант назначения чюритетов формируется по результатам расчетов предыдущего [рианта ДО. Показателем, определявшим необходимость изменения 'иоритетов запросов, является относительное отклонение >емени пребывания tl^ ■ — , (¿=ТГн). На каждом

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

Общая схема методики системного проектирования отобравает

розеине совокупности взаимосвязанных задач анализа и синтез;., сводится к построению множества структур, обсспечиваки:; выполнение различных ограничений. В процессе проек.тнроьан; различные структуры отличаются незду собой параметрами, моделям; методами распределений нагрузки, методами расчета характеристик ДО. Б процессе Проектирования необходимо учитывать слелуг,::м Фактору: ограниченность структур МУК, представляющих с;'. ' сочетание централизации и децентрализации ресурсов; неэяинсичпсч и естественный параллелизм решаемых задач: предел ы-п характеристики ресурсов. Общая схема методики состоит из трг основных этапов: 1) предварительного; 2) проектирования: модификации и уточнения. На предварительном этапе на основ,•ли1 параметров рабочей нагрузки выбирается первоначальная структур КУК. При построения модели следует учитывать такие фашор! характер поступления и обработки запросов, взиимось л поступления запросов в классах; способ организации дычиелнтелыш процессов! На основании этих факторов выбирается модель и мет;: расчета характеристик обработки запросов. Параметры иодел конфликтов зависят от способа организации оперативной памяти связи ведущих блоков или модулей с общими ресурсами.

Этап системного проектирования состоит в последовательно решении перечисленных в этой главе задач синтеза.

При выполнении этапа модификации и уточнения общий подхо заключается в развитии структуры в сторону обеспечения залами:) ограничений путем устранения её "узких" мест. Выполнен» ограничении может бить обеспечено за счет: увеличения числа П обработки Или быстродействий процессоров; увеличения емкосте локальной памяти ПБ; использования большего числа или боле производительных магистралей, связывавших ПБ с общими ресурсами Разработанный комплекс программ .реализующий методику системног Проектирования МУК, создан на базе персон.' чьим г профессиональны ЭВМ "Искра 1030". На всех этапах методики системног проектирования представляятся промежуточные результаты рекомендации для решения каждой из задач анализа и синтеза, направление модификации и уточнения структур МУК, обеспечивающн временные ограничения, определяется пользователем. Возможност применения методики системного проектирования продемонстрирован: для сосредоточенной и распределенной структур комплекса предназначенного для управления движущимся обтекточ.

ОСНОВКНЕ РЕЗЪ'ЛЬ'ГЙТН РЙБОТЫ

;. Ра?г-1бп>тань: точные аналитические методы расчета и ••оведено исследование характеристик функционирования

;ин:сронко-оргачизоБанних МУК с однородной приоритетной нагрузкой | исноге многоканальной СМО с ограниченным и неограниченным ;.'?|№н входных данных.

'Л. )'а?работднн и исследованы приближенные аналитические •■соли расчета характеристик неоднородной нагрузки асинхронных Л: нгн нс-гксноненикальних распределениях длительностей обработки

"Снове многоканальной СМО и двухфазной ЗСЕМО, погрешности п'орых не превкиагат 20%.

Разработана методика оценки комплексной производительности

проведено исследование характеристик модели конфликтов, едставленнон в виде ЗСМО, с учетом реальной нагрузки оцессоров, приоритетного и бесприоритетного способа их битра.та.

. Разработаны методы решения следующих задач синтеза МУК: а) ряделение минимального числа процессоров обработки, еспечивакщих ограничения по времени пребывания запросов разных ассов; б) выбор емкости буфера входных данных в условиях его раниченности; б) распределение неоднородной ' нагрузки п змеиение программ обработки запросов множества классов по оцессорным блокам для асинхронных и синхронных МУК.

1-.. Разработана методика системного проектирования МУК. правленная на определение структурных параметров и эффективных эссбов обработки данных на основе дисциплин обслуживания со лианными приоритетами, обеспечивающими выполнение временных оаниченнй.

6. Разработан комплекс программ, реализующий в диалоговом г.ине методику системного проектирования ПУК с приоритетной мботкой данных.

По материалам диссертации опубликованы следующие работы:

1. Алиев Т.К., Журавлев О.В. Модели и методы анализа >гопроцессорных вычислительных систем //Архитектура и актирование вычислительных систем. Анализ и синтез :пределенкых систем. - Рига: Риж. политехи, ин-т, 1387. - с. 70.

2. Алиев Т.Я., Журавлев 0.3. Расчет характеристик приоритетных

многопроцессорных управляющих комплексов с однородной нагрузко! //Изв. вузов СССР, Приборостроение. - 198S. - М1. - С. 25-29.

3. Алиев Т.И., Журавлев О.В. Приоритетная модель системы t множественным доступом и конечными источникам» нагрузки // Распределенные автоматизированные системы массового обслуживания. IV Всесоюзная школа-семинар. Тезисы докладов.- М.,1907

с.79-80.

4. Алиев Т.И., Журавлев O.E., Муравьева Л.А. Модел! обслуживания на основе дисциплин со смешанными приоритетам! //Труды десятой всесоюзной школы-семинара по теории телетрафика.

- И.: 11ППИ АН СССР, 19в8. - с.21-28.

5. Новиков Г.И., Алиев Т.П., Журавлев О-В. Приоритетная йоде.) узла передачи данных ■ с ограниченным выходным буфером / Двенадцатый всесоюзный семинар По вычислительным сетям. Тезис докладов. - U. > 19871 - ч.2. - с. 260-263.

6. Алиев Т.И.( Куравлев О.В., Муравьева Л.А. Расче характеристик многоканальной системы массового обслуживания однородной нагрузкой и приоритетными дисциплинами (50880001319)/ Алгоритмы И программы. - 1989. - N7 (89.07.0024). - с. 5.

7. Алиев Т.И.) Журавлев О.В, Муравьева Л.А. Анализ способ! управления потоками заявок (50880001316)// Алгоритмы И программь

- 1989. - N7 (89.07.0021). - с.4.

8. Алиев Т.И., Куравлев О.В., Муравьева Л.А. Расчет характеристик сетей массового обслуживания (5088000131В)// Алгоритмы и программы. - 1989. - М7 (89.07.0023). - с.4-5.

Подписано к Печати 03.03.90г. М-30119 Объем 1 п.л.

Заказ 270 Тираж 100 экз. Бесплатно.

Ротапринт. ЛИТМО. 190000, Ленинград, пер.Гривцова, 14