Методы оптимизации процессов программных вычислений и эффективно вычислимые алгоритмы для метаязыка описания сетей массового обслуживания
На правах рукописи
Евдокимов Алексей Викторович
МЕТОДЫ ОПТИМИЗАЦИИ ПРОЦЕССОВ ПРОГРАММНЫХ ВЫЧИСЛЕНИЙ И ЭФФЕКТИВНО ВЫЧИСЛИМЫЕ АЛГОРИТМЫ
ДЛЯ МЕТАЯЗЫКА ОПИСАНИЯ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ
Специальность 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 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга). В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, А.А. Маркова, А.Н. Колмогорова и других. Оптимизации алгоритмов посвящена теория частичных вычислений, разработанная Й. Футамурой,
В.Ф. Турчиным, А.П. Ершовым.
Теории формальных грамматик и грамматическому разбору выражений посвящены труды таких ученых как Н. Хомский, А. Ахо, Д. Ульман, Д. Грис, Д. Кнут.
Теории и языкам ИМ посвящены работы Дж. Гордона, Е. Сейджвика, А. Лоу, В. Кельтона, В.В. Емельянова. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов. Отметим книги Л. Клейнрока, Г.Т. Артамонова и О.М. Брехова по моделям функционирования ЭВМ.
Современное состояние теории массового обслуживания обеспечили работы А.К. Эрланга и А.А. Маркова, А.Я. Хинчина, А.А. Боровкова, Б.В. Гнеденко, В.А. Каштанова, И.Н. Коваленко, Т.Л. Саати, Д.Г. Кендалла, Дж. Литтла. Из современных работ по СеМО следует выделить многочисленные труды В.М. Вишневского, В.А. Ивницкого.
Цели и задачи исследования. Основной целью исследования является разработка методов преобразования вычислительных процессов к оптимизированным рекурсивным видам эффективно вычислимых алгоритмов на основе математического аппарата теории программирования, теории рекурсивных функций и методов частичных вычислений.
Для достижения поставленной цели необходимо решение следующих задач.
- Выделение класса систем, обладающих высокой степенью распределенности и значительным числом разнородных объектов обслуживания и требующих значительных объемов вычислений, возникающих в связи с внедрением новых принципов передачи и обработки информации, а также требованием оперативной поддержки принятия решений за ограниченное время.
- Разработка методов оптимизации процессов программных вычислений и способов преобразования алгоритмов к эффективному, теоретически обоснованному базису.
- Разработка рекурсивных форм эффективно вычислимых алгоритмов описания и моделирования систем.
- Построение метаязыка описания и структурирования данных для
СеМО с применением предложенной технологии оптимизации. - Разработка методики представления и моделирования СеМО, описывающей реальные информационные системы с помощью разработанного метаязыка.
- Исследование информационных систем с использованием разработанной среды ИМ.
Теоретико-методологическая основа исследования. В работе используются теоретические и практические разработки, связанные с построением и анализом формальных грамматик. В качестве теоретической базы при построении наиболее эффективных алгоритмов применяется математический аппарат теории рекурсивных функций. Для оптимизации программ использовался аппарат частичных вычислений. При разработке методик анализа и преобразования данных использовались современные методы и средства представления информации. Основой прикладных аспектов теоретических исследований явились труды отечественных и зарубежных авторов, посвященные проблемам, связанным с теорией массового обслуживания.
В диссертационном исследовании используются принципы системного, структурно-функционального и сравнительного анализа.
Информационно-эмпирической базой исследования послужили экспериментально-статистические и экспертные данные о конфигурации и функционировании сложных систем массового обслуживания, являющихся предметом исследования.
Научная новизна работы заключается в разработке методов реструктуризации и оптимизации вычислений в ИМ на основе эффективных алгоритмов. К наиболее существенным научным результатам работы относятся следующие.
- Исследована теоретическая база представления алгоритмов распознавания языков представления СеМО и предложены методы реализации программных процедур эффективными способами.
- Разработана технология оптимизации вычислений в программных модулях с использованием методов частичных вычислений и алгоритмов рекурсивных преобразований.
- Предложен метаязык структурированного описания СеМО XML-QS с эффективными методами вычислений, в том числе:
- для существующих языковых описаний СеМО разработаны алгоритмы их преобразования к языку XML-QS;
- разработан вычислительно-эффективный алгоритм распознавания входного языка;
- показан класс СеМО, для описания которых применим данный язык.
- Разработана методика представления информационных систем на метаязыке XML-QS и алгоритмы ее применения.
- Разработаны алгоритмы линейной и полиномиальной сложности, на основе которых создано программное обеспечение для имитации СеМО.
Практическая ценность. Предложенные теоретические подходы к представлению СеМО и их формальному описанию используются в интегрированных информационно-управляющих системах в подсистемах поддержки принятия решений.
Практическую ценность представляют следующие результаты.
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 с помощью -рекурсии, если:
- для
;
, где
- наименьшее y, для которого выполняется отношение
.
Аналогично, f определено из g и h с помощью -рекурсии, если:
1. ;
2. .