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

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

Евдокимов Алексей Викторович

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

Специальность 05.13.17 – Теоретические основы информатики

Автореферат

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

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

Ростов-на-Дону – 2008 г.

Работа выполнена на кафедре «Информатика» в государственном образовательном учреждении высшего профессионального образования «Ростовский государственный университет путей сообщения»

Защита состоится _19 июня 2008 г. в 14 часов 20 мин. на заседании диссертационного совета Д 212.208.21 в Таганрогском технологическом институте Южного федерального университета по адресу: 347928, г. Таганрог, ГСП-17А, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в научной библиотеке ЮФУ по адресу: 344006, г. Ростов-на-Дону, ул. Пушкинская 148, научная библиотека ЮФУ.

Автореферат разослан « 16» мая 2008 г.

Ученый секретарь

диссертационного совета Д 212.208.21

доктор технических наук, профессор Чернов Н.И.

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

Актуальность работы

Существует особая трактовка понятия «эффективность вычислений», смысл которой был заложен в работах Тьюринга, Поста, Черча, Клини, Гёделя, которые не могли предвидеть нынешнего прогресса в области компьютерных систем и сетей. Тем не менее, модели вычислений, заложенные в их работах, могут являться математическим фундаментом для построения эффективных программных комплексов с применением современных вычислительных систем и аппарата математического моделирования.

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

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

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

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

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

Теория алгоритмов сформировалась в 20 веке и впервые появилась в трудах Э. Бореля (1912) и Г. Вейля (1921). Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга). В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, А.А. Маркова, А.Н. Колмогорова и других. Оптимизации алгоритмов посвящена теория частичных вычислений, разработанная Й. Футамурой,
В.Ф. Турчиным, А.П. Ершовым.

Теории формальных грамматик и грамматическому разбору выражений посвящены труды таких ученых как Н. Хомский, А. Ахо, Д. Ульман, Д. Грис, Д. Кнут.

Теории и языкам ИМ посвящены работы Дж. Гордона, Е. Сейджвика, А. Лоу, В. Кельтона, В.В. Емельянова. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов. Отметим книги Л. Клейнрока, Г.Т. Артамонова и О.М. Брехова по моделям функционирования ЭВМ.

Современное состояние теории массового обслуживания обеспечили работы А.К. Эрланга и А.А. Маркова, А.Я. Хинчина, А.А. Боровкова, Б.В. Гнеденко, В.А. Каштанова, И.Н. Коваленко, Т.Л. Саати, Д.Г. Кендалла, Дж. Литтла. Из современных работ по СеМО следует выделить многочисленные труды В.М. Вишневского, В.А. Ивницкого.

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

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

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

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

В диссертационном исследовании используются принципы системного, структурно-функционального и сравнительного анализа.

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

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

1. Исследована теоретическая база представления алгоритмов распознавания языков представления СеМО и предложены методы реализации программных процедур эффективными способами.
2. Разработана технология оптимизации вычислений в программных модулях с использованием методов частичных вычислений и алгоритмов рекурсивных преобразований.
3. Предложен метаязык структурированного описания СеМО XML-QS с эффективными методами вычислений, в том числе:
1. для существующих языковых описаний СеМО разработаны алгоритмы их преобразования к языку XML-QS;
2. разработан вычислительно-эффективный алгоритм распознавания входного языка;
3. показан класс СеМО, для описания которых применим данный язык.
4. Разработана методика представления информационных систем на метаязыке XML-QS и алгоритмы ее применения.
5. Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО.

Практическая ценность. Предложенные теоретические подходы к представлению СеМО и их формальному описанию используются в интегрированных информационно-управляющих системах в подсистемах поддержки принятия решений.

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

1. Разработан, внедрен и адаптирован комплекс программ для имитационного моделирования работы автоматизированных систем управления, описываемых в виде СеМО. Внедрение этого комплекса позволило определить «узкие места» в системах управления и предложить обоснованные рекомендации по их устранению.

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

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

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском симпозиуме по прикладной и промышленной математике (2007 г. Сочи), на Международной конференции «Математика. Экономика. Образование» (2006 г., Новороссийск); на Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (2006 г., Новочеркасск); Международной научно-практической конференции «Экономико-организационные проблемы проектирования и применения информационных систем» (2006 г., Кисловодск), на научно-теоретических и научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2003 – 2007 гг.).

Основные положения и результаты, выносимые на защиту:

– эффективно вычислимые алгоритмы на основе рекурсивных функций;

– процедура оптимизации программных модулей на базе частичных вычислений;

– метаязык описания систем и сетей массового обслуживания XML-QS;

– принципы и методы представления СеМО;

– метод преобразования формальных описаний СеМО к языку XML-QS;

– алгоритм распознавания разработанного метаязыка.

Публикации

По результатам проведенных теоретических и экспериментальных ис­следований опубликовано 16 печатных работ, из них 3 – в журналах, включенных в список рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы и приложений. Объем диссертационной работы – 162 страницы, из них основного текста 135 с.

Основное содержание работы

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

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

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

– эффективность алгоритмов и скорость вычислений в этих системах не анализируется и не оценивается, тогда как в системах реального времени, которые описываются и имитируются с помощью СеМО, эта задача, как правило, является актуальной;

– невозможность изменения параметров системы в ходе имитационного эксперимента, однако, такие изменения характерны для реальных систем, рассматриваемых в ходе исследования;

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

– большинство существующих систем ИМ не позволяют графически задавать структуру СеМО и настраивать параметры каждого узла, которые могут описываться законами распределения; в самом узле нельзя задавать разные алгоритмы выборки заявок из очереди.

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

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

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

Рассмотрим предлагаемую методику на примере СеМО, приведенной на рис. 1.

Рис. 1. Пример СеМО с отказами и повторными вызовами

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

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

Пусть также определена функция:

где – индикатор сравнения.

Таким образом, для каждого из узлов приведенного примера справедливо:

Для случая, приведенного на рис. 2, введем дополнительный узел n (узел 6). При этом следует отметить, что .

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

Суммарное время пребывания заявки в системе будет описываться функцией , вид которой зависит от конфигурации системы, n – узел в котором завершается обслуживание заявки. Для примера рис. 2

.

Рис. 2. Пример преобразования СеМО для рекурсивного описания

Приведенные формулы удовлетворяют следующему свойству µ-рекурсивных функций.

Функция f называется определенной на отношении R с помощью -рекурсии, если:

1. для ;
2. , где - наименьшее y, для которого выполняется отношение .

Аналогично, f определено из g и h с помощью -рекурсии, если:

1. ;

2. .