Инструментарий для анализа производительности масштабируемых программных систем

УДК 681.3

Г.Б. Берсенев, Д.И. Малинин

ИНСТРУМЕНТАРИЙ ДЛЯ АНАЛИЗА ПРОИЗВОДИТЕЛЬНОСТИ МАСШТАБИРУЕМЫХ ПРОГРАММНЫХ СИСТЕМ

Рассматриваются существующие технологии создания моделей производительности и предлагается использовать "облегченный" набор инструментальных средств (математических и программных) для анализа производительности масштабируемых программных систем, а также включить редактор MS Visio в инструментальную среду для анализа производительности программных систем.

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

Создание программных систем обычно производится в соответствии с определенной моделью жизненного цикла [1]. Наиболее известными моделями являются модель водопада, модель временных прототипов, модель эволюционирующих прототипов (модель инкрементной разработки), спиральная модель, унифицированный процесс разработки программных систем. В последних двух моделях процессы разработки управляются рисками, важнейшими из которых является риск не достигнуть необходимой производительности или риск создать не масштабируемую (не расширяемую) в необходимых диапазонах программную систему. В связи с этим на протяжении всего жизненного цикла программной системы создаются и используются модели производительности [2, 3].

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

Существующие технологии создания моделей производительности основаны на многоэтапном преобразовании UML моделей сценариев производительности (диаграмм прецедентов, последовательностей или действий) с использованием достаточно дорогостоящих программных инструментальных средств [1 - 4]. При этом CASE-средство, использующие UML для визуального моделирования и создания программных систем, экспортирует UML диаграммы в формате XML. Эти XML диаграммы считываются одной

из инструментальных программ (XPRIT в [3]), которая запрашивает дополнительные параметры, необходимые для построения моделей ПО, и передает построенные модели ПО в виде XML файла в формате S-PMIF 2.0 (Software Performance Model Interchange Format) в другую инструментальную программу (например, в SPEED [2 - 4]) для получения оценок характеристик производительности без учета задержек в очередях. После решения всех проблем производительности с помощью самых простых моделей -моделей выполнения ПО - SPE-ED строит в интерактивном режиме модель работы системы в виде сети систем массового обслуживания (СеМО) и передает ее в виде XML файла в формате PMIF 2.0 в программу анализа СеМО (в [2 - 4] для аналитического и имитационного моделирования СеМО используется инструментальная программа QNAP).

В данной работе предлагается использовать «облегченный» набор инструментальных средств (математических и программных) для анализа производительности масштабируемых программных систем. Соответствующий подход основывается на следующих концепциях:

- более широкое использование моделирования производительности и масштабируемости программных систем на ранних этапах их создания;

- возможность использования офисных программ для подготовки моделей производительности и их анализа (например, программ Visio и Excel пакета Microsoft Office).

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

Существует множество различных методов анализа моделей производительности [5, 6]. На рисунке приведена классификация моделей производительности, в которой жирной рамкой выделены исследуемые виды моделей работы системы, а в таблице представлены результаты анализа ограничений, присущих выделенным моделям. Для этих моделей авторами предложены оригинальные методы и приближения, учитывающие современные уровни масштабирования программных систем [7-10].

Для включения редактора Visio в инструментальную среду для анализа производительности программных систем были разработаны:

- набор мастеров (Masters), определяющих типы элементов модели, их графические изображения и перечни атрибутов элементов-фигур (Shapes) модели работы системы;

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

- библиотека в виде набора классов на языке C# для обработки визуальной мидели, сохраненной в Visio в виде Visio-XML документа, формирования из нее XML файла модели работы системы и экспорта этой модели в программу моделирования посредством интерфейса XML DOM.

Модели производительности программных систем

Разработанный инструментарий реализован в виде распределенной среды и в виде интегрированной настольной инструментальной системы, причем каждая реализация содержит инструментальные средства для аналитического и имитационного моделирования СеМО. Настольная инструментальная система состоит из вспомогательного математического модуля MathHelpersLibrary, библиотеки моделей системы QNModelsLibrary и библиотеки решателей QNSolversLibrary. Библиотека моделей системы содержит класс основной модели - одноуровневой или двухуровневой СеМО (LQNModel), классы моделей узлов, маршрутов, заявок, а также вспомогательные классы VisioXMLParser и XMLVisioDocument, позволяющие выполнять преобразование Visio-документа, сохраненного, как XML-документ. В библиотеку входит класс ModelXMLSerializer, позволяющий преобразовывать LQNModel в модель на языке XML. В модели LQNModel используются 6 типов узлов: многоканальный узел обслуживания, пул процессов (потоков), терминальный узел, неограниченный источник заявок, сток заявок, узел сбора статистики (различных типов).

Основные ограничения математического инструментария

для анализа СеМО

Модель Метод/Аналитическое выражение Ограничения

М/М/с Аналитическое выражение с < 130

0/0/1 Аналитическое выражение Набор различных выражений

ОЯЗ/с Аналитическое выражение Приближения через 0/0/1 и М/М/с

М/М/с/Ы Аналитическое выражение с< 130, #< 170

Открытая однородная СеМО 2-го порядка Диффузионное приближение Одноканальные узлы обслуживания

Замкнутая однородная СеМО размерности

Замкнутая однородная СеМО размерности

Неоднородная по маршрутам СеМО размерности

Многоуровневая СеМО размерности (Ь,М,Ы) Имитационное моделирование Большая вычислительная сложность, зависит от Ь, М, N и заданной точности

Модели Маркова большой размерности Декомпозиция и решение системы уравнений баланса потоков вероятностей Сложность реализации: распределенное по узлам компьютерной сети решение системы уравнений

Библиотека решателей ОЫ8о1уегз1лЬгагу состоит из набора классов, реализующих методы анализа СеМО. Наряду с точными методами реализованы разработанные авторами методы аналитического расчета замкнутых СеМО, использующие линейные, гиперболические и асимптотические приближения для многоканальных узлов СеМО [7 - 10]. Методы позволяют анализировать СеМО большой размерности, имеют небольшую вычислительную сложность, которая практически не зависит от числа узлов СеМО и числа пользователей.

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

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

- как аналитический метод с априорно зафиксированной точностью решения уравнения (примерно 0,01).

Базовым классом для всех решателей является модель решателя -SolverModel. Данный класс содержит анализируемую модель (LQNModel), класс представления результата анализа (ResultModel), а также списки делегатов, нотифицирующие о ходе выполнения анализа на каждом этапе. Результат анализа модели может быть сохранен как XML-документ с помощью методов класса ResultXMLSerializer.

Для максимального использования возможностей многоядерных процессоров каждый решатель реализован в виде отдельного потока посредством класса SolverModelThread, что позволяет производить одновременный анализ одной или нескольких моделей различными методами.

Библиографический список

1. Гома X. UML. Проектирование систем реального времени, параллельных и распределенных приложений: пер. с англ. / X. Гома - М.: ДМК Пресс, 2002. - 704 с.

2. Смит К. У. Эффективные решения: практическое руководство по созданию гибкого и масштабируемого программного обеспечения / К.У. Смит, JI. Дж. Уильямс. - М.: Издательский дом "Вильямс", 2003. -448 с.

3. Smith С. From UML models to software performance results: An SPE process based on XML interchange formats / C. Smith, C. Llado // Worhhop on Software and Performance. - 2005.

4. Smith C. Performance model interchange format (PMIF 2.0): XML definition and implementation / C. Smith, C. Llado // Proc. of the First International Conference on the Quantitative Evaluation of Systems. - September 2004.

- P. 38-47.

5. Вишневский B.M. Теоретические основы проектирования компьютерных сетей - М.: Техносфера, 2003. - 512 с.

6. Башарин Г.П. Анализ очередей в вычислительных сетях. Теория и методы расчета / Г. П. Башарин, П. П. Бочаров, Я. А. Коган. - М.: Наука, 1989.-336 с.

7. Берсенев Г.Б. Приближенный метод анализа неоднородных замкнутых стохастических сетей с многолинейными узлами / Г.Б. Берсенев // Изв. ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Вып. 1. Вычислительная техника. - 2005. - С. 27 -34.

8. Берсенев Г.Б. Обобщенная модель узла с ограниченной очередью / Г.Б. Берсенев // Вестник ТулГУ. Сер. Вычислительная техника. Вып. 1. -Тула: Изд-во ТулГУ, 2007. - С. 88 - 92.

9.Берсенев Г.Б. Приближения и методы для анализа терминальных стохастических сетей / Г.Б. Берсенев, Д.И. Малинин // Изв. ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Вып. 1. Вычислительная техника. - 2006. - С. 171 - 179.

10. Берсенев Г.Б. Анализ двухуровневых терминальных стохастических моделей процессов обработки данных / Г.Б. Берсенев, Д.И. Малинин // ХЫП Всероссийская конференция по проблемам математики, информатики, физики и химии: Тез. докл. Секции математики и информатики. - М.: РУДН, 2007. - С. 62.

Получено 17.01.08.

УДК 004.932.4

Ф.А. Данилкин, Д.В. Хмельницкий

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

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

В настоящее время область применения низкочастотной нелинейной фильтрации прямоугольным ядром (ННФПЯ) [1,2] заметно расширилась. Первоначально данный вид фильтрации использовался для обработки цифровых изображений архивных документов с целью повышения качества их визуального восприятия. Существующие ранее методы: медианная фильтрация, линейное контрастирование и бинаризация на основе разделения гистограммы, традиционно применяющиеся для этой цели, в большинстве случаях оказываются менее эффективными.

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

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

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

Таким образом, разработка быстрого алгоритма ННФПЯ является актуальной задачей.

Рассмотрим цифровое монохромное изображение /:

1 = Цх,у), Ь

где Ь(х,у) - яркость точки изображения с координатой (х,у); \У, Я - ширина и высота изображения.

В результате ННФПЯ монохромного цифрового изображения I получим результирующее изображение яркостная характеристика каждой точки которого описывается следующим выражением:

х+Р„ у+Рн

X х геа

г=ьъУ)=--р;£-р;+Рн----------------------------------,

£ X гес

м>=х-Р„ И-у-Рн

где

гес1(£ ц/) =

- одномерная прямоугольная функция; Р\у ,Р1,Рн - параметры фильтрации.

Для упрощения формулировок введем следующие обозначения:

р\=(Щ +1). Р'МгРц +0. г*-№» + !)•

Физический смысл фильтрации заключается в том, что каждая точка результирующего изображения Ь'(х,у) получается как среднее арифметическое всех точек, находящихся в параллелепипеде с размерами (Р'ту,?Н’Р/,)> координата центральной точки которого равна (Цд:,у),х,у).

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

Для определения интегральной величины сложности введем следующие определения:

ta - максимальное время выполнения операции сложения;

гт - максимальное время выполнения операции умножения;

- максимальное время выполнения операции деления;

кт = — - количество операций сложения, эквивалентных по вре-

мени выполнения одной операции умножения;

кт = — - количество операций сложения, эквивалентных по вре-

мени выполнения одной операции деления.

Интегральную величину сложности алгоритма Н будем искать следующим образом: Ь = Ъ,а +Нткт +%с,ка.

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

На рис. 1 представлена блок-схема алгоритма фильтрации по базовому методу (2).

Рис. 1. Алгоритм фильтрации по базовому методу

Максимальная сложность базового алгоритма составляет

П = 2 НЩР'„

Заметим, что каждая точка изображения участвует в формировании

переменных Б и С до Р\ Р н раз. Эта особенность является основной

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

Определим функцию гистограммы яркости локального окна

Ну51

значение которой равно количеству точек яркости с, находящихся в локальном окне с размерами (Р'ру,Р//), центром которого является точка с

координатами (х,у). Рассмотрим множество всех точек локального окна:

^ <1<х + Р^,у-Рн <у <у + Рн).

Представим данное множество в виде объединения непересекаю-щихся подмножеств точек одинаковой яркости:

255 ,

Р = и р1>

к=0

где Рк = т.]\ Рк е Р. и и /) = к).

Заметим, что мощность

Р‘

г?к

каждого из подмножества г равна

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

Ну$^с,х,у,Р'1у,Р'н) =

Р

Запишем выражение (2) через множество Р:

X геМ

Г= Ь'

X геа

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

• • равно 0, попали в подмножество а остальные в :

^0 = {0'’Л

^1 = Л,

Тогда выражение (6) примет вид

'ЛЦ-пМ)

Г= Ь'

II.

Рассмотрим множество . Из определения прямоугольной функции (3) следует, что в него входят точки, яркость которых лежит в диапазоне [Цх,у) - , Ь(х,у) + /^ ]. Разделим множество Р1 на Р\

непересекающихся подмножеств, каждое из которых содержит точки одной яркости:

Р\к = № Д£(/,;) = *},

где Цх,у) -Рь<к < Цх,у) + Рь.

Выражение (9) можно записать как

Цх9у)+Рі

і

/'= Г(х,у) =

Д*оО+/Ъ

X II

к=Цх,у)-Р1 (*,,К)еРхк

Учитывая, что яркости всех точек к-го множества одинаковые, вы ражения '^Цмг.к) и £1 примут вид:

Таким образом, получили формулу вычисления процедуры ННФПЯ по гистограмме локального окна. Переход к расчету яркости по гистограмме делает возможным применить принцип быстрого алгоритма фильтрации «скользящим средним» для нахождения гистограммы локальной области и тем самым оптимизировать процедуру ННФПЯ. Однако для вычисления результирующего значения теперь требуется Р'I умножений,

которые отсутствуют в базовом алгоритме. Оптимизируем выражение (14) с целью минимизации операций умножения.

Рассмотрим числитель формулы (14). Для упрощения формальной записи введем обозначения:

{у>МУ-Р\

'£Цп,И) = Цп.И),

XI =Р\

(п,Н)еР\

С учетом (11) и (12) выражение (10) запишется как

/У г ^)+Р.

к=1'(х,у)-Рі

Заметим, что Р\ = Рк, поэтому Рк = Яу5/(с, х,у,Р\у, Р^). Следовательно

Цх.у)+Р,,

'^Ну81(к,х,у,Р№>Рн )к

к-Ц х,у)-Р,

0[ = Ну*г{\ + Цх,у) - п = Р'1-

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

5, = / + Ц.х,у)- Р1',х,у,Рт,Рн)(/ + Цх,у)-Р1) =

= 01-(И-Цх,у)-Р1).

Разложим произведение (15) в сумму следующим образом:

1+Цх.у)-Р,

5, = = 6,+С,+... + С,+С(.

,-0 '-------------.-------'

1+Цх.у)-Р1 раз

Очевидно, что с увеличением г на единицу количество слагаемых тоже увеличится на единицу. Запишем все слагаемые 5,- построчно с разложением произведения в сумму по формуле (16), как показано на рис. 2.

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

Цх,у)-Р1. раз

8о=

8!=

8П.1_

С> + Со + С> --------------- Со

Цх,у)-Р1+1 раз

О* + С1 + С]

с,

1 1 г 5 1

! ! 1

5

1 1 1 1

1 } 1 1 1

! ]

1 1 * ! *

С,, + с„., + сп.,-----------------------сп.,

Цх,у)+Рь-1 раз Сп + Сп + С„ ------------- С)

+

+

+

в, \

Сп-1 + Сп.,\

с, + сп + с„\

Ь(х,у)+Р раз

Рис. 2. Представление слагаемых, числителя

Сумма последнего столбца = (?„. Сумма предпоследнего столбца

Тп-\ - Оп + (3„_1 = (?„_! + Тп. Таким образом, методом индукции получаем итеративную формулу вычисления суммы слагаемых в столбце:

7} =7м+С,.

При I = 0 получим сумму последнего столбца прямоугольной облас-

п с=Цх,у)+Р1

ти: Т0 = 7}+1 + С0 = Т}+2 + С} + (?0 = X С/ = £#^(с,х,у,Р^,Рн), т.е.

7=0 с=Ь(х,у)-Р1

То эквивалентно знаменателю выражения (14). Сумма всех слагаемых тре-

п

угольной области будет равна £7}, а прямоугольной - Т0(Ь(х,у)- Рс).

/=1 '

Итак, процедура фильтрации (14) примет вид

Т0-(Цх,у)-РО+^Т{

г= Ь'(х,у) =----------------М_

70

Составим блок-схему алгоритма ННФПЯ по формуле (18). Для того чтобы избавиться от дополнительных проверок выхода яркости с за диапазон допустимых значений аргумента функции гистограммы, положим, что

Ну$1(с,х,у,Р^,Рн),с € [0,255].

Реализация алгоритма фильтрации по (18) приведена на рис. 3.

Рис. 3. Алгоритм ННФПЯ по

Процедуры Hystl, Hyst2 и Hyst3 модифицируют гистограмму при сдвиге окна вправо, влево и вниз. Процедура Out рассчитывает значение очередной точки гистограммы. Типовая реализация данных процедур показана на рис. 4.

Массив V

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

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

Out

Hystl

Hyst2

Hyst3

начало

начало

начало

^ Цикл 1

Ь=у-Рн..у+рн

Цикл 1 h=y-PH. у+Рн

/Цикл!4

W=X-P\v..X+P\v

V(L(x-Pw,h))=

V(L(x-Pw,h»+l

V(L(x+Pw,h))=

V(L(x+Pw,h))-l

V(L(x-P\y,h))~

V(L(x-Pw,h))-l

і

V(L(w,y-PH))=

V(L(w,y-PH))+l

V(L(x+Pw,h»=

V(L(x+Pw>h))+l

V(L(w,y+P„))=

V(L(w,y+Pn))-l

Цикл 1

конец

С

Цикл 1

конец

Цикл 1

конец

о

Рис. 4. Алгоритмы процедур Hystl

На практике фильтрация обычно производится квадратным окном (Р1=Рц) с апертурой 5-40 пикселей и параметром в цветовой области

Р1 = 5...30 градаций. В таблице приведены времена выполнения базового и

быстрого алгоритмов для цветного изображений с размером 640x480 точек на ЭВМ с частотой процессора 1,8 ГГц.

Времена выполнения процедуры ННФПЯ для базового и быстрого алгоритмов

1 11 21 31 41

1 160 340 431 531 631

180 1051 1853 2694 4106

11 520 701 802 911 1011

2513 5058 9213 13409 19348

2І 972 1151 1252 1362 1462

8442 9564 17245 25807 37364

31 1402 1593 1692 1793 1892

17505 17805 26318 39627 53227

41 2063 2213 2334 2433 2554

30193 31005 33718 54288 72444

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

Таким образом, предложенный алгоритм вычисления ННФПЯ позволяет сократить время обработки в 20 - 40 раз.

Библиографический список

1. Котов В.В. Низкочастотная фильтрация изображений угасающих документов/ В.В. Котов, Д.В. Хмельницкий // ХЬ Всероссийская конференция по проблемам математики, информатики, физики и химии: Тез. докл. Секции физики. - М.: РУДН, 2004. С. 86-89.

2. Данилкин Ф.А. Повышение качества визуального восприятия

слабоконтрастных документов с помощью нелинейной низкочастотной фильтрации / Ф.А. Данилкин, Д.В. Хмельницкий // Интеллектуальные и информационные системы: Материалы межрегиональной научно-

технической конференции. - Тула: Изд-во ТулГУ, 2004. С. 79-81.

Получено 17.01.08