Методы измерения и оценки временных характеристик алгоритмов : На примере распределенной вычислительной сети Селькин, Михаил Владиславович

Введение к работе

Актуальность темы. Современный этап развития сетей ЭВМ и средств телекоммуникаций характеризуется увеличением количества полі, ;о«а гелей распределенных вычислительных сетей. Этот процесс наблюдается во многих сферах деятельности человека: при комплексировании систем автоматизации проектирования, АСУ технологическими процессами, сбора, хранении и анализа информации в медицинских учреждениях, робототехш:>;еск;іх систем, конторских и банковских систем. С увеличением числа пользователей систем обработки, хранения и анализа данных, распределенных во времени н пространстве, возникает необходимость формирования большого количества заявок. В формировании потока заявок участвуют пользователи, программное обеспечение распределенной вычислительной сети її сама распределенная вычислительная сеть. В указанной ситуация возникает задача повышения эффективности использования распределенных вычислительных сетей, которая решается путем упорядочивания процесса формирования заявок в распределенной вычислительной сети, для чего существует необходимость иметь достоверные данные о параметрах потока формируемых заявок.

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

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

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

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

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

_4-

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

В соответствии с поставленной целью автором решены следующие задачи:

. - разработан аппаратно-программный комплекс для измерения временных характернешк алгоритмов и оценки параметров по измеренным характеристикам;

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

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

проведены экспериментальные исследования, подтверждающие эффективность методов оценки временных характеристик в аппаратно-программном комплексе.

Вопросами развития теории параллельных систем, к которым относится распределенная вычислительная сеть, и аналитических методов их исследования посвящены работы отечественных ученых: В.М. Глушкова, В.Е. Котова, А.А. Маркова (случайные процессы), А.А. Маркова (теория алгоритмов), В.В Овчинникова, Е.В. Бойченко, А.В. Фролова (сети ЭВМ) И.В. Прангишвили, ИВ Жожнкашвнли и др., а также зарубежных специалистов; Дж. Питерсона, Д. Фсррари, С.А. Петри, Д. Кенига, Д. Штойяна, В. Кальфа и др.

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

Научная новизна работы заключается в следующем.

!. Разработаны .методы измерений н оценки временных характеристик компонента алгоритмов программного обеспечения распределенной ВЫЧИСЛИ ІСЛІ-НОК сені.

i>

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

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

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

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

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

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

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

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

Реализация результатов диссертационной работы. Прикладные результаты работы внедрены:

- в муниципальной больнице №1 г. Тулы с общим экономическим эф
фектом за один год 20600 руб в ценах 1998 г. Работа направлена на упорядо
чивание обслуживания распределенной базы данных сети MEDNET при кол
лективном использовании базы данных службами и отделами муниципальной
больницы №1 г. Тулы;

- в разработках Всероссийского научно-исследовательского института
«Сигнал» с экономическим эффектом 184600 руб. за 1999-2000 гг. в ценах
2000 г. Работа направлена на улучше. не временных характеристик алгорит
мических структур для систем управления приводами наведения объектов
специального назначения, а также при разработках ЛВС в НПК-1.

Теоретическне результаты работы внедрены в учебных курсах «Высокопроизводительны-; сета ЭВМ» и «Сети ЭВМ и средства телекоммуникаций» на кафедре ЭВМ Тульского государственного университета.

Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях и семинарах. 1. «Микроэлектроника и информатика - 98» (г. Москва, 1998 г.). 2. XV научная сессия, посвященная Дню Радио (г. Тула, ТулГУ, 1998 г.). 3. ХИ-ая международная .техническая научная конференция «Математические методы в технике и технологиях» (г. Нижний Новгород; 1998 г.). 4. Молодежная научная конференция «XXV Га-гаринские чтения» (г. Москва, МГАТУ, 1999 г.). 5. ХН-ая научно-техническая конференция ((Пути совершенствования ракетно-артиллеристских комплект сов, методов их эксплуатации и ремонта», (г. Тула, ТАИИ, 1999). 6. П-ая Всероссийская научно-техническая конференция (г. Нижний Новгород: НГТУ, 2000). 7.Военно-научная конференция №36 (г. Санкт-Петербург: ВАУ, 1999 г ) S. Научно-техническая конференция молодых специалистов, аспирантов и студентов «Техника XXI века глазами молодых специалистов» (г. Тула, Тульский Дом науки и техники, 2000). 9. Научно-практические конференции профессорско-преподавательского состава ТулГУ (г. Тула 1997-99 г.г.).

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

Характеристика работы. Диссертационная работа состоит из введения, четырех разделов и заключения, изложенных на 138 страницах машинописного текста, содержит 28 рисунков, 16 таблиц, список использованной литературы из 92 наименований, 3 приложения, изложенных на 40 страницах машинописного текста, акты внедрения в учебный и производственные процессы.