Лекционный материал по дисциплине

Литература.

ГЛАВА 2. СЛУЧАИ, ДОПУСКАЮЩИЕ ПРИМЕНЕНИЕ ЭФФЕКТИВНЫХ ПРОЦЕДУР

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧ ПРОЕКТИРОВАНИЯ ОПТИМАЛЬНЫХ ПРОГРАММНЫХ КОМПЛЕКСОВ

ВВЕДЕНИЕ

Оглавление

СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ ИНСТИТУТ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Другие элементы диаграммы классов

Отношения между классами

Компоненты класса

Тема 6. Процесс проектирования и производства ПО. Объектно-ориентированная методология

Цели и задачи темы:

1. Рассмотреть основные понятия объектно-ориентированной методологии разработки ПО.

2. Познакомиться с обзором языка UML.

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

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

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

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

· Объекты предметной области или концептуальные классы.

· Ассоциации между концептуальными классами.

· Атрибуты концептуальных классов.

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

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

Диаграмма классов (class diagram) ­ диаграмма, предназначенная для представления модели статической структуры программной системы в терминологии классов объектно-ориентированного программирования.

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

Разработка диаграммы классов преследует следующие цели:

· определить сущности предметной области и представить их в форме классов с соответствующими атрибутами и операциями;

· определить взаимосвязи между сущностями предметной области и представить их в форме типовых отношений между классами;

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

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

Класс (class) ­ элемент модели, который описывает множество объектов, имеющих одинаковые спецификации характеристик, ограничений и семантики.

Xарактеристика (feature) ­ понятие, предназначенное для описания особенностей структуры и поведения экземпляров класса. В нотации UML 2.1.1 различают два типа характеристик класса: структурные характеристики (их называют свойствами или атрибутами) и характеристики поведения (их принято называть операциями или методами класса).

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

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

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

Рис. 1. Варианты изображения класса на диаграмме классов

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

Атрибуты класса (attribute) служат для представления отдельной структурной характеристики или свойства, которое является общим для всех объектов данного класса.

Некоторые параметры атрибута класса:

· Имя (name) ­ единственный обязательный элемент атрибута;

· Тип (type) ­ некоторый тип данных, соответствующий типам данных того языка программирования, который предполагается использовать для реализации данной модели;

· Видимость (visibility) ­ уровень доступности: public (общедоступный), private (закрытый, доступен только внутри класса), protected (защищенный, доступен только для элементов, которые имеют отношение обобщения с текущим элементом), package (пакет, пакетная видимость).

Видимость в нотации UML 2.1.1 допускается помечать соответствующим символом:

Ø + - общедоступный, public;

Ø - ­ закрытый, private;

Ø # ­ защищенный, protected;

Ø ~ ­ пакетный, package.

Видимость может вовсе не указываться или указываться другими модификаторами, соответствующими конкретному языку программирования, например, в C++ имеется видимость friend (дружественный), которая не специфицирована в UML.

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

Некоторые параметры операции класса:

· Имя операции (operation name) ­ единственный обязательный элемент операции;

· Список параметров (parameter list) представляет собой перечень разделенных запятыми формальных параметров операции;

· Тип возвращаемого значения (return type) ­ специфицирует тип возвращаемого значения;

· Видимость (visibility) ­ совпадает с видимостью атрибутов.

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

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

Ассоциация (association) ­ произвольное отношение или взаимосвязь между классами. Бинарная ассоциация (ассоциация между двумя классами) обозначается сплошной линией. В качестве дополнительных символов могут использоваться: имя ассоциации, имена, видимость и кратность концов ассоциации (рис. 2). Частным случаем бинарной ассоциации является рефлексивная ассоциация (класс связывается сам с собой).

Рис. 2. Графическое изображение ненаправленной бинарной ассоциации между классами

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

На рис. 2 конец ассоциации класса Сотрудник имеет имя работник, общедоступную видимость и кратность 1..*. Конец ассоциации класса Компания имеет имя работодатель, общедоступную видимость и кратность 1. Наличие указанных кратностей будет означать, что в рамках рассматриваемой модели любой конкретной компании может соответствовать несколько конкретных сотрудников. Этот факт может быть интерпретирован так: в компании работают несколько сотрудников, общее число которых заранее неизвестно и ничем не ограничено. С другой стороны, любому сотруднику будет всегда соответствовать единственная компания. Это означает, что в рамках рассматриваемой модели недопустима одновременная работа сотрудников в нескольких компаниях. Заметим, что символ кратности 0..* означает, что отдельные компании могут совсем не иметь сотрудников в своем штате.

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

Рис. 3. Программный код, сгенерированный по модели на рис.2

В качестве примера ассоциации со специфицированной навигацией рассмотрим отношение между классами Многоугольник и Линия (рис. 4). Классы связаны бинарной ассоциацией с навигацией, т.е. класс Многоугольник должен содержать информацию о своих сторонах. Программный код, сгенерированный на основании модели показан на рис. 5.

Рис. 4. Графическое изображение бинарной ассоциации с навигацией

При генерации программного кода для ассоциации с навигацией происходит добавление в код класса нового атрибута с именем рассматриваемого конца ассоциации, имеющий соответствующую видимость и кратность (рис. 5).

Рис.5. Программный код, сгенерированный для классов рис. 4

Нотация UML 2.1.1 допускает различные комбинации наличия и отсутствия навигации у концов ассоциации. На рис. 6 изображен случай, когда оба конца связи имеют навигацию. Двустороннюю ассоциацию принято либо показывать двумя стрелками, либо не показывать стрелок вообще (рис. 6).

Рис.6. Варианты изображение двусторонней ассоциации

Более общий случай представляет собой n-арная ассоциация, которая связывает некоторым отношением ассоциации более двух классов. В качестве значения n может выступать произвольное натуральное число больше 1. N-арная ассоциация графически обозначается ромбом, от которого ведут линии к классам. Имя n-арной ассоциации пишется рядом с ромбом. Порядок классов в такой ассоциации не фиксируется.

На рис. 7 рассмотрен пример 4-арной ассоциации Игра между классами ФутбольнаяКоманда, Год и Дата.

Рис.7. Графическое изображение 4-арной ассоциации

Обобщение (generalization) ­ отношение между более общим классификатором (родителем или предком) и более специальным классификатором (дочерним или потомком).

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

Отношение обобщения является направленным (стрелка указывает на общий класс) и может использоваться для представления иерархических взаимосвязей между классами. На рис.8 показано отношение обобщения классов Квадрат и Прямоугольник. Класс Квадрат наследует от класса Прямоугольник все атрибуты. Класс Квадрат имеет дополнительный атрибут цветКонтура.

Рис. 8. Графическое изображение отношения обобщения в UML

Отношение обобщения, которое называют также отношением классификации или наследования, допускает, чтобы от одного класса-предка одновременно наследовали несколько классов-потомков (рис.9). В нотации UML 2.1.1 допускается также, чтобы класс-потомок наследовал от нескольких классов-предков (множественное наследование).

Рис. 9. Пример графического изображения отношения обобщения для нескольких классов-потомков

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

Агрегация является частным случаем отношения ассоциации, от которой она наследует такие свойства, как имена концов ассоциаций, кратность и ограничения. Однако агрегациями могут быть только бинарные ассоциации.

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

Графическое изображение агрегации показано на рис.10. Незакрашенный (пустой) ромб размещается на агрегированном конце ассоциации.

Рис.10. Диаграмма классов для иллюстрации отношения агрегации на примере ПК

Композиция (composition) или композитная агрегация предназначена для спецификации более сильной формы отношения «часть-целое», при которой с уничтожением объекта класса-контейнера уничтожаются и все объекты, являющиеся его составными частями.

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

Графически отношение композиции представлено на рис.11. Ромб с заливкой указывает на класс-композит.

Рис.11. Диаграмма классов для иллюстрации отношения композиции

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

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

Зависимость означает отношение типа «поставщик/клиент» между элементами модели, т.е. модификация элемента-поставщика оказывает влияние на элемент­клиент. Клиент­ зависимый в некотором контексте от поставщика элемент модели. Семантика клиента не является полной без поставщика.

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

Отношение зависимости графически отображается пунктирной направленной линией (рис.12). Стрелка направлена от класса-клиента (от зависимого класса) к классу­поставщику (независимому классу).

Рис.12. Пример отношения зависимости класса-клиента (Этап) от класса-поставщика (Договор)

Реализация (realization) ­ специализированное отношение зависимости между двумя элементами модели, один из которых представляет некоторую спецификацию (поставщик), а другой представляет его реализацию (клиент).

Отношение реализации означает, что множество элементов клиента является реализацией множества элементов поставщика, которое служит в качестве спецификации. Зависимость изображается в форме пунктирной линии с треугольником на конце (к реализуемому элементу). На рис.13 показан пример отношения реализации.

Рис.13. Графическое изображение отношения реализации на диаграмме классов

Кроме перечисленных элементов диаграмма классов может включать: интерфейсы (interface), шаблоны (template), множество обобщения (generalization set), квалификаторы (qualifier), ассоциации-классы (assotiation class) и другие элементы.

(ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ)

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ИНФОРМАЦИИ

УЧЕБНОЕ ПОСОБИЕ

ПО КУРСУ:

«ПРОЕКТИРОВАНИЕ ОПТИМАЛЬНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ»

Составитель: М. Х. Томаев

Владикавказ 2008

ВВЕДЕНИЕ

Глава 1. Постановка задач проектирования оптимальных программных комплексов

1.1 Условные обозначения, определения и допущения:

1.2 Формальные постановки оптимизационных задач.

1.3 Оптимальное кэширование пользовательских файлов.

1.4 Объединение и декомпозиция моделей.

Глава 2. Случаи, допускающие применение эффективных процедур

2.1 Минимизация нижней границы времени однократного зацикливания циклящихся процедур.

2.2 Минимизация нижней границы времени выполнения ветвящихся программных алгоритмов.

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

Литература.

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

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

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

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

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

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

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

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

Все методы оптимизации можно условно разделить на машинно-зависимые, машинно-независимые и универсальные.

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

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

Многие современные автоматизированные системы разработки содержат инструменты, использующие подобные методы.

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

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

X = X+1;

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

X++;

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

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

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

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

Целью работы является создание средств программной поддержки технологии проектирования оптимального программного обеспечения, способного эффективно использовать ресурсы применяемых вычислительных систем. Поскольку существуют различные цели оптимизации программного обеспечения, задачей работы является разработка средств программной поддержки, предназначенных для разработки программных единиц, гарантирующих: а) минимизацию верхней границы времени поиска решения прикладной задачи для конечных алгоритмов; б) минимизацию верхней границы объема используемой оперативной памяти при условии, что время счета не превысит некоторой заданной величины; в) минимизацию верхней границы времени однократного зацикливания для циклящихся процедур. Таким образом, реализация данной работы позволяет, за счёт более эффективного использования ресурсов применяемых вычислительных средств, создавать более эффективное программное обеспечение, обладающее высоким быстродействием и сравнительно невысокими требованиями к объёму используемой оперативной памяти. Реализация работы приведёт, следовательно, к снижению потребности в дорогих ЭВМ и. соответственно, снизит затраты на решение прикладных задач. Отсюда следует актуальность представленной работы.

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

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

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

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

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

Теоретические принципы оптимизации программных продуктов подробно изложены в трудах Гроппена В.О., Летичевского А.А., Касьянова В.Н., Левитина В.В.

1.1 Условные обозначения, определения и допущения:

- подмножество операторов алгоритма пользователя,

реализуемых j-й программной единицей;

- верхняя граница времени работы j-ой программной

единицы;

- верхняя граница объема оперативной памяти,

используемого j-ой программной единицей;

- объем свободной оперативной памяти;

- булева переменная, равная единице, если i-й оператор

алгоритма пользователя реализуется j-й программной единицей, и нулю в противном случае;

- взвешенный ориентированный граф, вершины которого

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

- множество терминальных вершин графа;

- множество контуров на графе.

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

- подмножество программных единиц, реализующих

операторы, отвечающие дугам, принадлежащим контуру

;

- j-ое подмножество программных единиц, реализующих

все операторы, отвечающие дугам пути;

- множество операторов алгоритма пользователя ();

- вершина графа, отвечающая начальному

состоянию вектора переменных;

- число файлов, используемых в алгоритме пользователя;

- вероятность обращения к -му файлу;

- прогнозируемый размер -го файла;

- размер кэш-блока, предназначенного для сканирования

-го файла;

Определения пути и контура на ориентированном графе соответствуют принятым в [16,17]. Обозначения, используемые локально, вводятся по ходу изложения.

1.2 Формальные постановки оптимизационных задач.

Дополнительные определения.

Вершиной ветвления принято называть графовое представление начального состояния оператора условного перехода.

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

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

Линейные и ветвящиеся алгоритмы состовляют класс конечных программных алгортмов.

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

Если же и множество контуров и множество терминальных вершин на графе являются непустыми, то соответствующий алгоритм называю склонным к зацикливанию.

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

Если же в текущий момент работы программы в памяти может находиться лишь один из последовательно загружаемых модулей, то такой режим функционирования называетсяCHAIN.

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

где вершина s – соответствует начальному состояние алгоритма, а t- конечному.

Z(i,j)=1, если существует оператор, соответствующий переходу из i-го состояния в j-е(т.е. существует дуга (i,j)).

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

1. Поиск решения для режима Overlay осуществляется согласно приведенному ниже алгоритму.

Алгоритм 3.3.

1..

2..

3. На графе G(q,n) удаляются все дуги, вес которых

4. На полученном графе ищется кратчайший путь из в, длина которого равна D(q,n).

5. Если то перейти к шагу 7, в противном случае - к следующему шагу.

6..

7. Если q=n, то перейти к шагу12, если же – к следующему шагу.

8..

9. Если, то перейти к шагу 10, если же -к шагу 12.

10..

11. Перейти к шагу 5.

12. Конец алгоритма. Величина равна минимальному значению целевой функции задачи (1.3).

При переходе к ветвящимся и циклящимся алгоритмам, выбор цели оптимизации тесно связан с учетом человеческого фактора. Так, достаточно разумным представляется допущение, что пользователь-пессимист будет стремиться минимизировать верхнюю границу времени счета либо объема используемой оперативной памяти, а оптимист – нижнюю [11,14]. В первом случае оптимальная декомпозиция конечного алгоритма, минимизирующая верхнюю границу времени поиска решения его программной реализацией применительно к ЭВМ, объём свободной оперативной памяти которой равен V, в режиме CHAIN может быть определена с помощью следующей модели (1.1):

Система (1.1) представляет собой формальную постановку антагонистической позиционной игры двух лиц с полной информацией [103,104]: минимизирующий игрок объединяет операторы в программные единицы, а максимизирующий выбирает условия их завершения. Можно показать, что поиск оптимальной декомпозиции оптимистом соответствует «игре с болваном», в которой второй игрок действует в интересах первого, что существенно облегчает поиск решения [12,13]. Очевидно, что учет человеческого фактора должен отражаться системой автоматизированного проектирования программных продуктов.

Формальная постановка задачи, аналогичной (1.1), для программиста-оптимиста, стратегия которого состоит в том чтобы минимизировать нижнюю границу времени поиска решения, будет отличаться лишь целевой функцией:

Ниже представлена формулировка задачи минимизации верхней границы времени выполнения для алгоритмов, функционирующих в режиме OVERLAY:

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

Так же как и для режима CHAIN, переходу к оптимистической стратегии оптимизации соответствует замена целевой функции на.

Аналогичная декомпозиция зацикленного алгоритма[71-75], который реализуется программными единицами, функционирующими в режиме CHAIN, при пессимистической стратегии (минимизация верхней границы времени однократного зацикливания), может осуществляться на следующей модели, отличающейся от (1.1) лишь целевой функцией:

Аналогичная задача для зацикленных алгоритмов, функционирующих в режиме OVERLAY соответствует замене единственного неравенства на соответствующее неравенство в модели (1.3).

Формулировка задачи минимизации нижней границы времени однократного зацикливания, отличается от (1.4) целевой функцией.

Физически (4) означает минимизацию верхней границы времени однократного зацикливания в контурах множества, соответствующей одному из критериев качества программных реализаций алгоритмов такого рода.

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

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

Так как такие операторы безусловного перехода имеют нулевые времена счета и объемы занимаемой памяти, то, очевидно:

Отсюда следует, что оптимальной декомпозиции такого рода отвечает равенство:

(1.6),

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

Если целью оптимизации является декомпозиция конечного алгоритма, которой отвечает программная реализация, минимизирующая объём используемой оперативной памяти в режиме CHAIN при условии, что верхняя граница времени счета не превысит времени [18,22,25], то система (1.1) преобразуется к виду:

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

Аналогичный подход к зацикленным алгоритмам приводит к формальной постановке, отличающейся от (1.8) лишь последним ограничением:

Здесь представляет собой верхнюю границу времени однократного зацикливания [7, 19, 41].

Очевидно, что систему (1.7) и её модификации можно также рассматривать, как формальное описание антагонистической позиционной игры двух лиц с полной информацией и нулевой суммой, что позволяет использовать для её решения те же подходы, что и для решения системы (1.1).

Наконец, несколько строк об алгоритмах, склонных к зацикливанию, т.е. таких, которые могут как благополучно завершиться, так и бесконечно циклиться [69, 85]. Граф, соответствующий процедурам такого рода, обладает непустыми множествами контуров и терминальных вершин:. Рассмотренные выше модификации конечного алгоритма, преобразующие его в зацикленный введением фиктивных операторов безусловного перехода с “нулевыми” характеристиками, позволяют избежать оптимизации по Парето [61, 62] применительно к склонным к зацикливанию алгоритмам и свести их оптимальную декомпозицию к оптимальной декомпозиции зацикленных процедур. Это позволяет далее отказаться от поиска решения многокритериальных задач оптимальной декомпозиции алгоритмов пользователя.

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

Это можно отобразить в следующем алгоритме:

Алгоритм 2.

1. Цене игры присваивается значение, равное бесконечности.

2. Все вершины первого яруса дерева игры считаем не просмотренными.

3. На множестве не просмотренных вершин первого яруса выбираем произвольную вершину.Если таковой нет, т.е. все вершины первого яруса просмотрены, переходим к шагу 12, в противном случае –к следующему шагу.

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

5. Если на полученном графе образовались вершины, в которые не заходит ни одна дуга, исключая, естественно, корневую вершину, то они отбрасываются вместе с инцидентными им дугами [36, 35], причем процедура повторяется до тех пор, пока на новом графе единственной вершиной такого рода не явится корневая вершина дерева игры.

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

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

8. -номер последнего яруса дерева.

9. Каждой вершине, принадлежащей -му ярусу, присваивается потенциал:

1-e, если t четно либо равно нулю;

2-е, если t нечетно и существует дуга

10. Величина t уменьшается на единицу.

11. Если t=1, то выбранную на шаге 3 последней итерации вершину 1-го яруса считаем просмотренной, цена игры перейти к шагу 3, в противном случае – к шагу 9.

12. Конец алгоритма.

1.3 Оптимальное кэширование пользовательских файлов.

Другим аспектом проектирования оптимальных программных продуктов является размещение данных в памяти ЭВМ и определение оптимальных размеров кэш-блоков [44, 57, 105]. Если все файлы пользователя первоначально размещены на внешнем носителе, а в оперативной памяти созданы блоки кэширования, каждый из которых предназначен для сканирования «своего» файла, причём a priori известны размер каждого файла и вероятность обращения к нему либо число таких обращений, то формальная постановка задачи минимизации числа обращений к внешним носителям имеет вид [15, 18]:

(1.10)

Очевидно, что, если существует оптимальное решение (1.10), в котором, то

это означает, что й файл должен быть размещён в оперативной памяти. Если перемещения такого рода запрещены, то нижней границе решения системы отвечает вектор для которого справедливо:

(1.11)

В [3, 8] предложен алгоритм поиска решения (1.10), использующий систему (1.11) в качестве отправной точки, в окрестностях которой ищутся целочисленные планы.

Если в рассмотренных выше моделях справедливо:

(1.12),

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

Алгоритм оптимального размещения используемых файлов.

1. Если число массивов меньше объема оперативной памяти, выделенной для работы с файлами, то переход к шагу 9, в противном случае – к следующему шагу.

2. K=0.

3. Если, то переход к шагу 6, в противном случае к следующему шагу.

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

- размер -го массива;

4. Рассчитываются оптимальные размеры кэш-блоков по формуле,

где - число обращений к -му массиву.

5. Определяем суммарное число обращений к внешним

носителям на данной итерации:

6. K = K+1

7. Если К < 2^m, то переход к шагу 3, в противном случае к следующему шагу.

8. Определяем k-ую итерацию, на которой число обращений к внешней памяти было минимальным:

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

9. Конец алгоритма.

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

1.4 Объединение и декомпозиция моделей.

Учёт условия (1.12) в моделях (1.1) и (1.3), позволяет формально поставить задачу поиска таких стратегий композиции программных единиц и размещения данных в двухуровневой памяти ЭВМ, которые бы минимизировали верхнюю границу числа обращений к внешним носителям. Применительно к зацикленным алгоритмам это означает проектирование их программной реализации, минимизирующей верхнюю границу числа обращений к внешним носителям в ходе однократной циркуляции в любом контуре. Формальная постановка такой объединенной задачи для программ, функционирующих в режиме chain имеет вид:

(1.13)

Переходу к режиму overlay соответствует следующая формальная постановка:

(1.14)

Аналогичные задачи для ветвящихся алгоритмов представлены в следующих моделях (1.15) и (1.16), соответственно для алгоритмов, функционирующих в режимах CHAIN и OVERLAY:

(1.15)

(1.16)

Поиск решения (1.13)-(1.16) осуществляется последовательным разделением величины на две части - и:.

Первое слагаемое левой части играет роль размера свободной оперативной памяти, используемой для размещения программных единиц, а второе слагаемое представляет собой размер свободной оперативной памяти, используемой для хранения и кэширования файлов. Это позволяет осуществить декомпозицию (1.13) на две подзадачи - одной из них является поиск оптимальной композиции программных единиц при условии, что объем используемой оперативной памяти не превысит величины, а другая отличается от (1.10) тем, что величина заменяется в ней на. Значение целевой функции (1.13) равно сумме целевых функций обеих подзадач. Таким образом поиск решения (1.13) сводится к поиску минимума функции. Поскольку последняя является унимодальной [12, 76], поиск решения может вестись с помощью дихотомии, интерполяции или квадратичной аппроксимации.

2.1 Минимизация нижней границы времени однократного зацикливания циклящихся процедур.

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

1. Пусть целью оптимизации является поиск оптимальной декомпозиции зацикленного алгоритма, множество контуров, которого содержит только простые контура (рис.2.1),

тогда существует множество вершин, для которых выполняется:

, при (2.1)

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

Рис.2.1 Исходный граф.

Рис. 2.2. Модифицированное представление алгоритма.

2.2 Минимизация нижней границы времени выполнения ветвящихся программных алгоритмов.

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

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

(2.3)

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

Теорема. Решение задачи, формальная постановка которой

представлена в модели (2.2) соответствует решению задачи поиска минимального пути (2.4) на графе из начального состояния в вершину S.

Доказательство.

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

Пусть – решение задачи (2.2), а – решение задачи поиска кратчайшего пути на из начального состояния в вершину s модифицированного графа.

Рис. 2.3. Модифицированное графическое представление алгоритма пользователя.

(2.4)

1. Пусть.

Отсюда следует, что минимальный путь, соответствующий решению задачи (2.4) меньше, чем путь, соответствующий решению (2.2). Так как согласно равенству (2.3) вес каждой дуги, заходящей в вершину нулю, то не является минимальным среди всех возможных путей в одну из терминальных вершин, а соответствующая программная декомпозиция не соответствует нижней границе времени счета, что противоречит целевой функции задачи (2.2).

2. Пусть.

Т.е. соответствующий решению задачи поиска кратчайшего пути (2.4) путь длиннее, чем, но это возможно только в случае, когда существует, что противоречит условию (2.3).

Теорема доказана.

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

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

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

Задачу определения оптимальной аппаратной конфигурации ЭВМ, минимизирующей время обслуживания прикладных вычислительных процессовможно описать следующей моделью (1):

Используемые обозначения:

- число задач;

- число типов аппаратных подсистем;

- частотная полоса аппаратной подсистемы -го типа, выделяемая для обслуживания -ой задачи;

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

- коэффициент, отражающий зависимость времени решения -ой задачи от скорости работы аппаратной подсистемы j-го типа;

- время обслуживания -ой задачи аппаратной подсистемой -го типа:;

- время решения задачи системой (ЭВМ):;

- коэффициент, отражающий зависимость стоимости аппаратуры от скорости (частоты) её работы;

- верхняя граница стоимости ЭВМ

- верхняя граница частоты (производительности) -й аппаратной подсистемы.

(1)

Модифицировав систему (1) получим задачу оптимального распределения вычислительных ресурсов имеющегося парка ЭВМ для обслуживания заданного множества прикладных процессов – модель (2).

В модели используются следующие дополнительные обозначения:

- булева переменная, равная единице, если -ая задача обслуживается -ой ЭВМ, и единице в противном случае;

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

(2)

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

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

Рис.1. Оптимум в пространстве критериев

Пользуясь описанным подходом, задачу (1) можно представить в виде следующей модели (3):

(3)

Аналогично, задача (2) преобразуется к виду:

(4)

Выразим Цели задач (3) и (4) можно сформулировать также в виде функций (5) и (6) соответственно:

Результаты решения описанных выше задач требуют дополнительной аппроксимации на множестве имеющейся на рынке номенклатуры аппаратных продуктов. Точность полученных в результате решения задач (1)-(4) результатов (т.е. требуемых частотных характеристик комплектующих для ЭВМ) ограничена линейным характером зависимости частоты работы устройства от стоимости оборудования. На практике, зависимость стоимости от частоты работы устройства для оборудования, созданного на основе новейших дорогих технологий носит скорее экспоненциальный или полиномиальный характер. Однако для устройств среднего и начального классов использование линейной характеристики представляется оправданным.

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

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

Станция 1

Рис.1. Пример топологии ЛВС.

Рис.2. Представление топологии ЛВС в виде орграфа.

На графе, соответствующем топологии ЛВС, добавим фиктивные дуги из вершин, соответствующих рабочим станциям (в данном случае 3,4,5,7,8,9), к вершине, соответствующей серверу хранения данных (вершина 1). Веса этих фиктивных дуг примем равными требуемым каждой станцией значениям мощности входящего потока данных.

Приняв следующие обозначения:

- количество узлов ЛВС;

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

- стоимость коммутации оборудованием -го типа;

- булева константа, равная 1, если существует дуга () и 0 - в противном случае;

- множество вершин, соответствующих вершинам источникам, т.е. клиентским рабочим станциям;

- множество индексов контуров, включающих дугу ();

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

зависимости от требуемой мощности входящего потока для каждой (-ой) рабочей станции;

- пропускная способность на участке между узлами и при использовании оборудования -го типа;

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

сформулируем задачу:

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

1. Гроппен В.О. Оптимизация программного обеспечения ЭВМ на базе игровых моделей// Автоматика и телемеханика № 8, 1986 г., стр. 135-143.

2. Гроппен В.О. Принципы оптимизации программного обеспечения ЭВМ.// Изд. РГУ, Ростов-на-Дону, 1993 г.

3. Гроппен В.О. Эффективные стратегии использования кэш-памяти.// Автоматика и телемеханика № 1, 1993 г., с. 173-179.

4. Ветров А. Г., Луцикович В. В. Система построения трансляторов ТУ. Основные принципы выполнения оптимизации транслируемых программ.— Препринт/ИПМ АН СССР.— М„ 1979-№33-15 с.

5. Гроппен В.О. Мазин В.В. Лавровский В.Л. Теоретические основы создания эффективного программного обеспечения ЭВМ// Тез. Докладов научно-технической конференции посвященной 60-летию СКГМИ, Владикавказ,1991г. С.202-203.

Дата добавления: 2013-12-13