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

ГУДЗЕНКО ДМИТРИЙ ЮРЬЕВИЧ Г

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА ПЕРИОДИЧНОГО ПЕРЕРАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ В РАСПРЕДЕЛЕННОЙ ИВС

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

РГ6 ОД

-О

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

АВТОРЕФЕРАТ

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

Москва - 2000

Работа выполнена в Московском Государственном Техническом Университете им. Н.Э.Баумана

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

профессор [Соломатин Н.?\ Официальные оппоненты - доктор технических наук,

профессор Брехов О.М. Кандидат технических наук, с.н.с. Троицкий И.И.

Ведущая организация Информационный центр Главного агенства воздушных сообщений ГА

Защита диссертации состоится 2000 г. на

заседании диссертационного совета Д.053.Г5.03 при Московском Государственном Техническом Университете им. Н.Э.Баумана по адресу: 107005, г.Москва, 2-я Бауманская ул., д.5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э.Баумана

Отзыв на автореферат в одном экземпляре, заверенный печатью, просим направлять в адрес совета института

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

Ученый секретарь Диссертационного совета

к.т.н.,доцент С.Р.Иванов

Подписано к печати "_"_2000г.

Заказ_Объем 1 п.л. Тираж 100 экземпляров. Типография

МГТУ, 107005, г.Москва, 2-я Бауманская ул., д.5.

гЗ^.Ш.О^-аЯЛ , О

1. Общая характеристика работы

1.1. Актуальность проблемы

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

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

Предметом исследования являются методы и алгоритмы реконфигурации распределенных ИВС.

1.2. Цель и основные задачи исследования

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

Для достижения данной цели в работе решаются следующие задачи:

• классификация методов и моделей анализа эффективности распределения информации в распределенных ИВС;

• разработка и анализ метода размещения подструктур РБД по узлам РИВС при изменяющихся нагрузках;

• разработка метода агрегирования модели распределенной ИВС в виде СМО на базе критериев замены;

• разработка и анализ метода определения периодичности перераспределения подструктур РБД;

• разработка алгоритмов периодичного перераспределения подструктур РБД по узлам распределенной ИВС.

1.3. Методы исследования

При разработке формальных моделей компонент в диссертации использовались методы общей теории систем и классический теоретико-множественный аппарат. Системный анализ функционирования информационно-вычислительных систем проводился на базе реальных статистических данных, с использование математических и статистических пакетов ^а^иса, МаШСаё и др.). При разработке моделей и алгоритмов оптимизации функционирования распределенных ИВС использовалась теория графов, методы математического программирования, теория случайных процессов, имитационное моделирование, теория массового обслуживания и др.

1.4. Научная новизна

Научную новизну работы составляют:

• структурная декомпозиция модели распределенной ИВС на основе замены моделями СМО и имитационными алгоритмами;

• метод размещения информации в условиях нарушения устойчивости;

• агрегированная модель распределенной ИВС;

• формальная модель оценки прогноза рабочей нагрузки;

о алгоритм периодического перераспределения подструктур

РБД.

1.5. Достоверность научных положений, рекомендаций и выводов

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

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

1.6. Практическая ценность и реализация результатов работы

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

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

Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения на кафедрах ИУ6 МГТУ им.Н.Э.Баумана, НИИ АРГОН, ООО "К-Системс".

1.7. Апробация работы

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

• на Российских, межрегиональных и международных научно-технических конференциях, симпозиумах и семинарах (1985-2000гг.);

• на заседании кафедры ИУ6 МГТУ им.Н.Э.Баумана.

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

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

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

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

Во введении обосновывается актуальность работы. Ставятся цели и задачи исследований. Приводится краткое содержание глав диссертации.

2.1. Анализ и классификация моделей и методов распределения информации в РИВС

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

Анализ методов решения задачи распределения информации в РИВС

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

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

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

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

Классификация моделей н методов

Разнообразие постановок и методов решения задачи размещения информации в РИВС, обусловленное различными целями и проблемами на этапах проектирования и эксплуатации, привело к необходимости выработки единого систематического подхода к выбору признаков и построения классификации.

Каждый тип модели задачи размещения является объектом в классификации К, Он может быть формально представлен в виде булевского вектора Г, индексированного номерами признаков классификации:

Г=(УьУ2,...,У17,УшХ (1)

где /-ому признаку, ¡е[1,18], соответствует элемент вектора %е(0,1). ^=1, если /-ый признак присутствует в модели, ^=0 в противном случае. На Г не накладывается никаких дополнительных ограничений. Такая формализация позволяет провести анализ классификации К, выявить ее недостатки; на основе анализа сформулировать требования к построению классификации К*, свободной от выявленных недостатков.

Проведен анализ недостатков рассмотренных методов и на основе проведенной формализации сформулированы требования к разрабатываемой классификации А"* (Т1-Т4):

Т1. (Требование полноты) Построение К* должно проводиться на основании анализа достаточно большого количества работ, посвященных задаче размещения информации в РИВС.

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

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

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

Характеристики задачи распределения информации

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

2.2. Разработка алгоритма размещения информации по узлам РИВС с учетом изменения рабочей нагрузки

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

Формализация задачи распределения информации в РИВС при пропорциональных изменениях рабочей нагрузки

Для представления структуры РИВС используется модель в виде взвешенного ориентированного графа О без петель, удовлетворяющего в общем случае условию сильной связности:

ОНУ, Ц). (2)

Множество вершин орграфа К={у,}, 1=1.Л, 1=1 соответствует множеству узлов хранения и обработки информации в РИВС, множество дуг Ц={ мк}, к=\ ..К, К=\Ц, иаУ2 - множеству коммуникационных каналов между узлами. Ориентация дуг соответствует возможным направлениям передачи информации по коммуникационным каналам.

Вес ¡-ой вершины - вектор, элементы которого

соответствуют элементам вектора ^с:"^, имеющих значение 1 в формализованной модели постановки \¥ задачи распределения информации в РИВС в соответствии с разработанной классификацией.

Определим рабочую нагрузку для узла I как поток запросов Л5у (л - номер запроса) к подструктурам РБД Ь3. Обработка каждого запроса 5 в общем случае состоит из 5 этапов, каждому из которых соответствует свой информационно-вычислительный процесс (ИВП).

Этап 1. Реализация ИВП Р13у в исходном узле \ состоит в обработке потока запросов КЛ^ в узле I с интенсивностью

Этап 2. Реализация ИВП Р25у состоит в передаче сообщения длины ЬГ; из узла 1 в к, к?4 (к - целевой узел размещения подструктуры Вр к которому идет поток запросов 112^ через коммуникационные каналы). Если к=1, то этапы 2 и 4 не имеют места.

Этап 3. Реализация ИВП Р35у в узле к состоит в обработке потока запросов с интенсивностью \ук2-

Этап 4. Реализация ИВП Р4^ состоит в передаче сообщения длины Ь25; из узла к в 1 (к?ч), представляемых как обработка потока запросов Я48ц в каналах (дуги ик1сЬиы и, --•, иы).

Этап 5. Реализация ИБП Р55ц в узле К состоит в обработке потока запросов 115^ в узле 1.

Для предложенной модели сформулирована цель оптимизации, согласно которой оптимальным будет Ь размещений М\ (1=1..Ь), таких, что для интервала пропорциональных изменений рабочей нагрузки Хе[Я,А;Я.в], М\ удовлетворяет условию:

п=1/=1 ]=1 и=1/=1 У=1

где Т(Рпу,М1,'к) - среднее время реализации процесса Рп5ц при рабочей нагрузке А. и размещении М\.

Размещение информации по узлам РИВС при пропорциональных изменениях рабочей нагрузки

В работе предлагается декомпозиция задачи поиска оптимального размещения 3 подструктур М на./ независимых задач поиска оптимального размещения каждой подструктуры т\, 3=1..5. Так как при размещении отдельно взятой подструктуры возможно / вариантов (по числу узлов), то размерность Щ преобразованной задачи равна Лц=1х1.

Сформулируем преобразованную задачу размещения: для каждой подструктуры РБД 0=1.Л) найти Ь размещений т}{ (1=1..Ь), таких, что для интервала пропорциональных изменений рабочей нагрузки А.е[А.Л;А,в], является оптимальным размещением.

При известной X задача нахождения тц сводится к выбору

я I —

наименьшего значения суммы £ Рп^, т^' ,Х) перебором всех 1*

я=1/=1

вариантов, где Т(Рп^,т 'среднее время реализации процесса

Рпц при рабочей нагрузке X и размещении т}\, полученное при учете влияния потоков к другим подструктурам путем использования С.

Время пребывания заявки в СМО 1преб складывается из времени ожидания в очереди ^»ид и времени обслуживания ^бсл

(^преб=^ожид~'~^обсл) •

Предполагается, что

3/^, прей = оба,' 3///И Гпф ожид = 00 . (4)

Поставлена задача декомпозиции и сформулировано необходимое условие адекватности декомпозиции:

т^=т}{(С(А/,Ш С'(Л/Д)=С(М*Д), {/«;}, (5)

где значения С*(Л/Д) определяются по исходной модели СМО (без декомпозиции); С(Л/,Х.)- коэффициенты, используемые при нахождении т/. Отметим, что в общем случае Если

Л/ =Со«5/, А.=Со«л/, то задача нахождения коэффициентов адекватной декомпозиции С может быть представлена как задача нахождения нулей (1+К)-мерной функции (1+К) переменных Р(С):

ДС)=|С-С*(Л/(ОД). (6)

Функция Г(С) имеет следующие особенности: вычисление функции связано с определением С* на исходной модели СМО и характеризуется сравнительно высокой трудоемкостью; даже если

непрерывна по С; нахождение частных производных д/1дс требует больших затрат, что не дает возможности использовать градиентные методы поиска.

Разработан алгоритм поиска корней функции Р(С), основанный на использовании методов прямого поиска на основе линейной аппроксимации.

Для "к^к^ сформулировано обобщенное условие устойчивости размещения: М. Рассмотрен характер изменений коэффициентов адекватной декомпозиции С при увеличении X.

23. Разработка метода периодичного перераспределения информации по узлам РИВС

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

Построение агрегированной модели РИВС

На более высоком уровне детализации целесообразно представление РИВС в виде другой, более обобщенной (агрегированной) модели. Агрегированная модель описывает поведение РИВС как элемента системы более высокого уровня (макросистемы). Такая модель может использоваться при построении модели макросистемы.

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

изменяющейся во времени интенсивностей входного потока запросов 8

X. Таким образом, агрегированная модель РИВС как элемент макросистемы функционально представим в виде Ттт (?.), для которой справедливы соотношения.

1. Область определения и диапазон значений функции удовлетворят условию:

УЯе [О, X'] ЗГ51|И(^)е[Г511т(0), сю). (7)

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

Зд Т

дХ

д Т

д2Т

>0,3

д2т

*

Х=Х

>0. (8)

Для формализации модели РИВС выбран аппарат теории массового обслуживания. Система представляется в виде сети МО, а ее элементы - в виде систем МО. Таким образом, для построения модели макросистемы в виде сети МО модель ее элемента (агрегированная модель РИВС) должна быть формализована в виде системы МО. Выбраны два типа СМО, наиболее часто используемые при анализе вычислительных систем: вариант одноканальных СМО -простейшая СМО ЩЩ1 и СМО с произвольным временем обслуживания M\G\l. В зависимости от области применения модели используются различные критерии.

Критерий соответствия границ требует равенства Tsmn и Т^щ в граничных точках области определения X:

тмт )- Тшт (x¿eg\ Ти¡q, (X'end ) = Tsum(Xend) , (9)

где VA. e [X^; Xená J A.beg > 0 Xaá < X'.

По критерию наименьших квадратов значения Е, г и v выбираются так, чтобы минимизировать взвешенную среднюю квадратическую ошибку на интервале (XbeS, A.end):

а2 = £ "Т у(фмт (*)- f™ (X))\IX. (Ю)

<=о x¡

В наиболее общем случае, когда для размещений Л^(Г5ШП(Я.)) не возможна замена моделью M|G|1, приближение функции (rsiim(?L)) может быть реализовано по методу наименьших квадратов на дискретном множестве точек.

Для каждой из предложенных агрегированных моделей количественная оценка адекватности реальному процессу в РИВС может быть получена сравнением характеристик Г5ШП(Я,) и Тиодели(Х) на дискретном множестве точек по критерию наименьших квадратов как средневзвешенная квадратичная ошибка о2.

Оценка прогноза изменений рабочей нагрузки Решение задачи рационального распределения подструктур РБД в РИВС требует информации об условиях функционирования системы, в частности, рабочей нагрузке в некоторый будущий период времени. Такая информация в общем случае не известна, так как рабочая нагрузка изменяется под влиянием большого количества факторов. Исчерпывающий учет факторов невозможен. Возникает задача прогноза рабочей нагрузки, т.е. определения Ц/), ¿е[1„аст;

/прогноза]; ^прогноза^наст, ГДв /наст " НЭСТОЯЩИЙ МОМеНТ Времени; ¡„раток '

некоторый будущий момент времени при заданной глубине прогноза.

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

N

прогноза (ЛП) на основе линейного фильтра у„ =1Y^djУ»-j+x„■

м

Соотношение может быть использовано для прогноза очередного значения % временного ряда по первым Означениями , ]=1...ЛГ. хп

определяет расхождение прогноза на временном шаге п.

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

1. Используя известные М предыдущих значений РН(Тт), вычисляется оценка ф] автокорреляции функции РН(() с задержками j=-M...M.

2. Используя полученные оценки и уравнение Берга-Андерсена, вычисляются значения коэффициентов к=0...М.

3. Далее определяются N коэффициентов ^ и по методу максимальной энтропии получается уп - прогноз значений рабочей нагрузки.

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

рационального распределения подструктур РБД в РИВС. С другой стороны, при увеличении глубины прогноза снижается точность прогнозной оценки, что снижает точность модели в целом. В работе проведен детальный анализ влияния глубины прогноза на его точность.

Алгоритмы периодичного перераспределения подструктур РБД по узлам РИВС

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

В первом варианте перераспределения не производится (¿=0). В этом случае для всех подинтервалов размещение т0 постоянно, как и на начале первого подинтервала:

= £ (Тх1 , тор, (*,))- Т1т (*., ,«„)). (П)

/=1

В втором варианте производится одно перераспределение перед к-ым подинтервалом (1=1). В этом случае интервал Т разбивается на 2 части - до и после перераспределения. Задачу перераспределения можно представить как задачу нахождения таких (к*,гпк ), что

Фтпк А(/>;). (12)

Значения могут бьггь получены следующим образом:

для каждого £е[1;/с] найти т\ и вычислить АДля нахождения т*к может быть использован метод полного перебора возможных размещений /пк, получаемых согласно соотношениям, представленным в главе 2. С целью исключения полного перебора предлагается более эффективный приближенный метод приведенной рабочей нагрузки, который сводится к определению рабочей нагрузки А' на двух частях интервала Т, т.е. ищется оптимальное размещение т\ для приведенной рабочей нагрузки и в качестве

приближения А(/,»**) используется А.Тпт^1,тк ^.

В третьем варианте производится Ь перераспределений перед -ыми подинтервалами. Количество перераспределений Ь и их периодичность могут быть либо заданы (например,

еженедельно), либо подлежать определению, исходя из известных (или оцениваемых) временных затрат на каждое перераспределение и его ожидаемой эффективности. Если (¿{к^}) заданы, то задача периодичного перераспределения сводится к нахождению {/иь} для каждого из I подинтервалов. Если определению подлежат все (2,{&ь}), то учитываются временные затраты Траспр на одно перераспределение. Они в большинстве случаев слабо зависят от объема перераспределяемой информации и могут считаться постоянными (время настройки системы).

Для случая произвольных изменений рабочей нагрузки агрегированная модель РИВС может быть представлена в виде гиперповерхности отклика типа Т(Л, Р), где А={А.;} - рабочая нагрузка в узлах, Р={р)} - множество параметров модели. Показано, что в виду сложности использования аналитических методов целесообразно определение Р численными методами многомерной оптимизации. Изменения рабочей нагрузки в этом случае являются многомерной функцией времени Л(1:). Для экстраполяции значений рабочей нагрузки требуется многомерная модификация метода линейного прогноза и, соответственно, многомерная модификация периодического перераспределения.

2.4. Экспериментальное исследование и реализация разработанных методов и алгоритмов

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

Программная реализация методики периодичного перераспределения информации в РИВС

В программно-имитационной модели реализована следующая схема порождения, отработки и уничтожения запросов. С интенсивностью в узле I возникает запрос к подструктуре ^ В соответствии с проведенным статистическим анализом показано, что допустимо приближение времен поступлений экспоненциальными распределениями. Появление в узле I запроса на подструктуру ] вызывает процесс передачи копии подструктуры] из узла ее хранения к в узел ¡. Передача копий подструктур осуществляется пакетами единичной длины. При продвижении пакета по узлам и каналам РИВС учитываются только задержки в каналах. Маршрут передачи

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

Программа разработана в среде Delphi-5. Помимо основного требования (реализация имитирующего алгоритма) программа имеет возможности хранения исходных параметров и результатов экспериментов в базе данных (InterBase), возможность генерация отчетов (интерфейс с Word) и другие системные функции. В пакете реализован лишь минимальный набор математических и статистических процедур. Особое внимание уделено разработке интерфейса с пакетом Statistica, в котором генерируются факторные планы экспериментов, а после имитационной процедуры формируются оценки параметров регрессионных и дисперсионных моделей.

Сравнительный анализ алгоритмов размещения

В план эксперимента включены следующие исследования:

• сравнительный анализ размещений, рассчитанных без учета задержек в каналах;

• сравнительный анализ размещений, рассчитанных без учета изменений рабочей нагрузки;

• анализ размещений для различных степеней фрагментации РБД (количество подструктур определяется при неизменном суммарном объеме с соответствующим приведением интенсивностей запросов);

• анализ влияния ограничен™ на \v,i и на эффективность размещений;

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

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

J значений У] по среднему у -, расположение связей по заданному количеству К (обеспечивающее полносвязность сети), по К значений ры по рк1, р^ по рк2, 1хЛ значений Я^ по /Ц.

Проведен анализ структуры РИВС НИИ АРГОН. Получены статистические оценки входных потоков, объемов и времен обработки. Сформирована модель прогнозирования рабочей нагрузки. Разработана модель настройки параметров алгоритмов перераспределения.

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

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

Приложение содержит документы об использовании результатов работы.

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

Основные выводы и результаты работы

1. Проведен анализ и классификация методов решения задачи распределения информации. Выделено 3 группы задач по цели оптимизации и определены методы решения для каждой группы. Для различных этапов жизненного цикла РИВС даны рекомендации по постановке задачи и применимости методов.

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

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

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

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

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

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

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

8. Разработан метод периодичного перераспределения подструктур РБД по узлам РИВС для случая пропорциональных изменений рабочей нагрузки. Определены пути модификации разработанного метода для случая произвольных изменений рабочей нагрузки.

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

10. Проведено экспериментальное исследование компонент метода периодичного перераспределения подструктур РБД по узлам РИВС - алгоритмов размещений подструктур РБД по узлам РИВС; способов построения агрегированной модели РИВС и методики прогноза рабочей нагрузки, а также метода в целом.

Публикации по теме диссертационной работы

1. Гудзенко Д.Ю., Пирумов Н.Р. Система имитационного моделирования на языке высокого уровня // Актуальные вопросы современного приборостроения: Тез. докл. Всесоюзной конференции. - Москва, 1985. - С.45-46. - д.с.п.

2. Гудзенко Д.Ю., Пирумов Н.Р. О реализации системы имитационного моделирования на языке высокого уровня (Паскаль)

//Актуальные вопросы современного приборостроения: Тез. докл. Всесоюзной конференции. - Москва, 1986. - С.64-65. - д.с.п.

3. Гудзенко Д.Ю., Медведев Н.В., Время пребывания задания в вычислительной системе и вероятность потери информации //Проектирование вычислительных машин и систем: Межвуз. сборник науч. трудов. - Рязань, 1987. - С.31-33.

4. Гудзенко Д.Ю. Подсистема интерактивного формирования программ-моделей в системе имитационного моделирования СНМПАС // Распределенные информационно-управляющие системы: Тез. докл. V Всесоюзной конференции - Саратов, 1988. - С.57.

5. Гудзенко Д.Ю., Марков A.A., Пирумов Н.Р. Применение общецелевой системы имитационного моделирования СИМПАС в полунатурных моделях // Математическое обеспечение комплексов полунатурного моделирования: Тезисы доклада Всесоюзной конференции. - Гродно, 1988. - С.61-62.

6. Гудзенко Д.Ю., Марков A.A., Пирумов Н.Р. Графический процессор для представления структур технических систем и формирования их моделей // Математическое обеспечение систем с машинной графикой: Тез. докл. V научно-технического семинара. -Ижевск, 1988. - С.24-25.

7. Гудзенко Д.Ю., Марков A.A., Пирумов Н.Р. Общецелевая система имитационного моделирования на Паскале // Деп. рук. ВИНИТИ. - 1989. - №42. - 63с.

8. Гудзенко Д.Ю., Марков A.A., Пирумов Н.Р. Система имитационного моделирования на языке Паскаль СИМПАС // Деп. рук. ВИНИТИ. - 1989. - №57. - 1 Юс.