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

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

071

*] 3 * На правах рукописи

УДК 681.324

Тарханян Анаит Геворговна

Анализ и выбор распределенных информационно-вычислительных систем на основе оптимизационно-имита» >1Х схем

Специальность Применение вычислительной техники, ма" [этических методов в научных исследован.

АВТОРЕФЕРАТ

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

Ереван-1995

Работа выполнена в Институте проблем информатики и автоматизации Национальной академии наук Республики Армения.

Научный руководитель член-корр. HAH РА,

доктор технических наук, профессор

Ю. Г.Шукурян

Официальные оппоненты академик HAH РА,

доктор технических наук, профессор

Р.В. Атоян кандидат ф.-м. наук, с.н.с.

В. Г. Саакян

Ведущая организация Ереванский научно-исследовательский

институт средств связи.

}, о ¿Защита состоится в оч час, на заседании специализированного совета N 037 "Математичекая кибернетика и информатика: 375044, г. Ереван, ул. П.Севака, 1.

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

Автореферат разослан " <к$ "

1995 г.

Ученый секретарь специализированного совета к.э.н, с.н.с.

А. Е. Мелконян

Сдано в печать 27. 11. 1995 г. Бум. 60x84. Объем 1 печ. лист. Заказ 53. Тираж 100 экз.

(

Актуальность '• проблемы. Распределенная обработка является одной из важнейших особенностей современных информационных технологий. Она характеризуется взаимодействием ма\ых компьютерных систем через коммутационные сети, в частности локальные вычислительные, сети (ЛВС), обеспечением общего использования удаленных вычислительных ресурсов и превращаением совокупности таких систем в единый объект -распределенную информационно-вычислительную систему (РИВС). РИВС яв.\яется основой для построения систем автоматизации научных исследований, проектирования, банковской деятельности и т.д.

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

В указанном комплексе задач актуальной является проблема выбора стандартных аппаратно-программных

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

На сегодняшний день для РИВС наиболее широкое распространение получила архитектура Клиент-Сервер (АКС), предусматривающая взаимодействие узлов Клиентов с узлами Серверами посредством межпроцессных связей. Однако, для такой архитектуры отсутствует формализация большинства проектных процедур, а алгоритмическая реализация существующими. методами {CASE-Tools) часто оказывается неудовлетворительной.

Диссертационная работа посвящена решению задач анализа и выбора РИВС с архитектурой Клиент-Сервер.

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

- анализ, постановка и исследование задачи выбора

РИВС;

- разработка практического метода выбора РИВС;

- создание инструментальных средств выбора РИВС.

Методы исследований. Выполненная работа

характеризуется комплексным по уходом к решению поставленных проблем выбора . РИВС. Математическую

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

Научная новизна. В диссертации получены следующие результаты:

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

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

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

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

Теоретические исследования проводились в рамках темы КП2-93, выполняемой в ИПИА HAH РА.

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

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

-на семинарах Института проблем информатики и автоматизации НАН РА;

-на семинарах и на заседаниях кафедры "ЭВМ" Ереванского политехнического института;

-на VI Всесоюзной научно-технической конференции по проблемам управления развития систем, Киев, 1991 г.;

-на XVI Всесюзной школе-семинаре по вопросам вычислительных сетей, Москва, 1991 г.."

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

Объем работы. Диссертация состоит из введения, трех глав, заключения, изложенных на 132 страницах машинописного текста, содержит 18 страниц рисунков и таблиц, приложение и список литературы из 154 наименований.

Содержание работы

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

В первой главе проведен анализ структурных решений ри проектировании РИВС, выделены особенности )ункционирования РИВС при архитектуре Клиент-Сервер.

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

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

^ ~ { С0П | п=1..Г\т} - это множество сегментов одсетей) <эп, определяющих локальную вычислительную сеть 4ВС, характеризуемый узлами - серверами Эп , узлами-лентами Кл, (Ьп = Ба^Кп) 11 методом доступа е(юп). змпонента В структуры - это множество узлов-соединений

между парами сегментов ЛВС PIÍBC (повторители, мое транспортные станции и т.д.).

Элемент hP множества Н={ hp | р= 1..Р } допусти? типов средств в ыч 1i ом ггельно й техники (СВТ), из кото] возможно построение РИВС, определяется следутоп кортежем:

hP =<V, R, D, G >,

где V - тип процессора, R - объем ОЗУ, D - объем жесткого диска,

G - скоростные характеристики жесткого диска.

Распределением фА множества задач А= {а.,| u= 1....U по узлам РИВС называется отображение:

(рА: А -> Q,

ставящее в соответствие задаче a.i еА узел РИВС, на которог эта задача будет решаться. Задача 2-й представляете: совокупностью следующих параметров:

аа = < Vp,rp1gp,dp,pp/<y,'>,

где ур - объем вычислений на СВТ р-ого типа, гр - требуемый объем ОЗУ, gp - требуемый объем жесткого диска, dp - интенсивность обращения к жесткому диску, рр - интенсивность обращения к ЛВС. Параметр ср определяет управляющую

информационную среду (операционную систему (ОС) и :истему управления базами данных (СУБД) ), связанную с "ВТ р-ого типа.

При заданном распределении задач каждая пара узлов , j характеризуется трафиком л^ (фА) РИВС, который [оказывает интенсивность обмена данными между этими ■злами (ед. информации/сек).

Зафиксируем некоторое распределение задач по злам. Тогда распределением Hm СВТ по узлам сети при словпи распределения задач срл называется отображение:

Нп : п U В -> H

Обозначим через Wm - { Н,„ / фА} rn-ый вариант груктуры РИВС, с распределением Нт при условии фл (ш-й вариант конфигурации). Каждое распределение средств ВТ совместно с трафиком характеризует качество РИВС, ее гоимость и временные характеристики.

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

Основывая '.ъ на вышеизложенном, критерием |)фектишюсти i работе выбран стоимостной фактор, а раничением npi. выборе РИВС - время решения задач в гстеме.

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

Дано W= {Wm } • Необходимо найти такую РИВ WcpI, \\"Cpt € W, чтобы стоимость

С(Wopt) = min {C(Wm) .

m

где C(Wm) стоимость при выполнении условия

c<D\

где t™- время решения задачи аи в варианте РИВС

■учетом наличия в системе других задач и Da - директивно время решения задачи аи в РИВС.

Стоимость РИВС представляется следующим образом:

N Srj

c=Z(ScIk + Sc2.) + Co.

n k=l S=1

где c'k" стоимость k-го к\иента в n-ом сегменте; С2,;- стоимость s-ro сервера в п-ом сегменте; Со - постоянная составляющая стоимости сетевы: соединений, включающая стоимость прокладки н реальном объекте, стоимость подключения к сети (сетевьи интерфейсные платы, транспортные станции и т.д.), стоимост; аппаратуры соединения сегментов сетей (повторителей мостов, маршрутизаторов) и т.д.

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

С= Г(С1ы, сим =1,2.

Временные характеристик I системы зависят не только от "пропускной способности" элементов (физическая скорость передачи или обработки данных), но и, главным образом, от режимов и способов обработки/передачи данных. Тем самым, на всех этапах выполнения запросов время не может быть представлено в виде констант или простых зависимостей, а может быть описано как некоторая случайная величина с "соотв* ^ствующеи функцией распределения. В общем виде суммарное время решения задачи в РИВС не подчиняется никакому из известных (классических) распределений. На практике почти полностью исключена возможность аналитического представления столь сложных вероятностно-временных характеристик, что приводит к необходимости их определения путем имптащтонного моделирования.

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

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

Во второй главе определены основные требования к разрабатываемому методу и последовательность этапов выбора РИВС. Необходимость учета динамики функционирования приводит к использованию имитационных моделей. Однако, использование имитационного моделирования для полнофакторного п •^рс^ора возможных конфигураций РИВС на представляется возможным из-за 1\ТР-полноты задачи. Возникает задача направленного моделирования, при котором совместно используются оптимизационные и имитационные модели, что получило в литературе название оптимизационно-имитационного подхода.

Использование этого подхода заключается в разработке специальной оптимизационно-имитационной схемы (ОИС). Разработана ОИС для выбора РИВС: разработана ее структура, последовательность и вложенность оптимизационных и имитационных моделей, их связанность через различные контуры (генерация, анализ, коррекция); выбрана информационная • среда реализации; выбраны принципы управления ОИС с учетом лица, принимающего решения (ЛПР); в ОИС предусмотрена база моделей (БМ). Схематично ОИС представлена на рисунке.

Анализ языковых средств моделирования позволил выбрать для комплекса программных средств (КПС) язык Паскаль и СИМПАС (система имитационного моделирования на Паскале). Это дало ' возможность создать

ОИС для решения задачи выбора РИВС

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

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

(БМ), что также является особенностью разработанной ОИС. В БМ единообразно представляются модели различной природы (аналитические, имитационные, смешанные).

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

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

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

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

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

Описаны разработанные алгоритмы и соответствующие имитационные программы на языке Паскаль. Обобщенная модель РИВС с архитектурой клиент-сервер и методом доступа ЛВС CSMA/CD описана как сеть массового эблуживания. Проведены исследования характеристик модели, получены выражения, характеризующие время решения задач в РИВС. Например, для РИВС, функционирующей под Novell Netware 3.11, получены зависимость времени ответа от размера буфера сервера, твисимость времени ответа от количества клиентов при различных моделях процессора клиентов и типов шин :ервера, загрузка процессоров клиента и т.д. Даны рекомендации по выбору серверов и клиентов. В работе •акже разработана имитационная модель сервера определенной базы данных. Модель исследована при >азл1гчных режимах обслуживания, для каждого из которых юлучены зависимости количества обслуженных, количества [еобслуженных запросов, времени ответа ov размера буфера ервера. Даны рекомендации по выбору режимов бслуживания, конфигурации сервера и т.д.

На основе совокупности программ, объединенных в 1ПС объемом более 5000 строк на языке Паскаль и метода ыбора РИВС разработаны методики выбора и оценки, аскрыта сущность методики выбора, приведены ее основные гаги. Методика ориентирована на автоматизацию процесса роектирования РИВС. Разработаны инструментальные

средства оценки вариантов РИВС в рамках методики оценк на основе обосчованных математичских моделей.

1

Заключение

Результаты выполненных исследований позволяю сделять следующие выводы по диссертации:

1.Проведен анализ структурных ре пений пр: проектировании РИВС. Сформулирована задача выбор РИВС на основе разработанной концептуальной мод ел: структуры.

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

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

4.В рамках метода разработана методика оценки РИВС, основанная на аналитических и статистических результатах моделирования.

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

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

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

Основное содержание диссертации отражено в ледующих работах:

1.Тарханян А.Г. Оптимизационно-имитационные одели в сетевом планировании крупномасштабных ероприятий// Тезисы докладов VI Всесоюзной научно-знхической конференции по проблемам управления азвитием систем. АН СССР.- Киев,- 1991.- С. 47 - 48.

2.Тарханян А.Г. О методе выбора конфигурации определенных информационно-вычислительных систем на

г

1зе локальных вычислительных сетей. Препринт 94-013.-эеван: Издательство Национальной Академии Наук эмении.-1994.

3.Тарханян А.Г. Разработка методики оцеш

распределенных информационно-вычис иггельных систе:

»

Институт проблем информатики и автоматизащ Национальной Академии Наук Республик с Армения,- Ерева. 1995 г., с. 38, 11 табл.- Библиогр.: 11 назв.- Рус.- Деп. АрмНИИНТИ 05.06.95, N 23-Ар-95

4.Тарханян А. Г., Торосян С.С. Исследованг вычислительного процесса сервера распределенной баз данных локальной вычислительной сети. Известия Академи Наук Армении. Серия технические науки,- В печати с 1991 г.

5.Тарханян А.Г., Хачиян Н.Г. Программный комплек для прокетирования локальных вычислительных сетей/ Тезисы докладов XVI Всесоюзной школы-семинара п вычислительным сетям. Ч. 1. Москва,- 1991,- С. 93-97.

Ut3i|mifituqfip Uûuihfitn QLnpq.fi fdiupfvujûjujO "Puj2hnliuô fiü$npúuig|inG-hui2ilnriujljiuü hiui3uil|iupqbpfi hbmiuqnmnLüp Ii GÜinprupjniüQ oujmfiútiqujghnú-tiúfiuiuigfinü ufubiíiuübph hfiiîmû фш "

UinbüiufununLpjruü|] йфрфиб t ршгГифиб fiG$npthug[inü-ИшгЦп^ш^шй hmúuiljujpqbpfi (РМ^) ljiunnLgi{iuáp}i

фпрйш^шдфхк* Qüwpúiuü hitipgbpft hbinoiqnmúuJÜQ L PM^-fi pGinpiîujû qnpójipujjjiü úfipngübpfi ( úuupbúuiinhljujljmü únt)b|übp|i, püpujgujl|ujpqbp[i L ópujqpbpfi) бгш^йшйр:

4bpnhh2JWl йщшшшЦйЬр(1 huuJiup ui2tuuiinuiGenn5 àLiul|bpo|4bi U hbmiuqnimlb|. Ьй hbuiLjuj|. fuünhpübpD

- PM^-fi pûinpùujû luhüqpfi tlbp|niónLLÍ[], htupguuqpruiÎQ U hbiniuqninnLÚQ;

- Ph^-fi рйтрйшй qnpóüujl|ui& tfbpnrjfi (Згш^пиЗр;

- PMR-h pbuipüiuü qnpó|iguij|iü úíipngübpp uinbqdnLúp:

^buiiuqnmrupjriLüübpli i5iupbúuim|ibujl|ujü hfiiigü bü

Ijtuqúniir i5iupbiîujinfil|iul|ujû ópiuqpuJiJnpnLtfn. (5шиш)ш^шй ищшишр^шй mburupjruDQ, |ii5liinujgtinü únrjbiiuilnpüujQ uibunLpjruûp:

UmbDiufunurupjujCi úbp итшдЦЬ[ Ьй hbinbjuiL hüßüopliüiul) mpnjniüpübp'

- 0ЬшЦЬрац4ш0 t Ph^H-fi рйтрйшй [uhûqpfi Gnp Ьшрдшг^ргийр 1^п0дЬщ1ЛГ)1Ш[ únobiji bfiúrnú Црш, huJ24h шпйЬ^пЦ mibüm-UbriLlbp l)umnigi{ujóp|];

- ú2mL|ilmó t РЬЯЯ-fi hfibpuuptxiiiLj pCiinpúujG bquiüiuljQ, hhi5üi|m¿> ou^mfii5hqujgfiriü-fiúfimiug|inü ¿ntnbgúiuü Црш;

- й2шЦ1|ш0 t aijq bquuGuil(fr ЦпйдЬицттш^ nipi|ujqfiáQ, hbimuqnimlujô bü рОтрйшй фni[bp[i fuür^hpübpp b |32ш1)11ш6 bü LnLáúuuG Иш13шщштши[ишй рйршдш^шрдЬрр:

PMR-h Qüinpúujü Ь^шйш1)р fipiuqnpóiliuó t ópmqpmjtiü úfigngübpfi hiuùai|jint.i5: bqiuûujl|fi L uijn. hiuiíiu|jifi oqinujqnpánt.ú{] pnLjL t шш^и ршр0ршдйЬ[ Pb^^-fi CnufiJiuqáúiutí прш1)р Ь 1(рбштЬ[ Qiutuujqddiuû (tiuúiuíiujL(G: