Тарасов В.Н., Коннов А.Л., Мельник Е.В. Компьютерное моделирование: лабораторный практикум

Подождите немного. Документ загружается.

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

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

Государственное образовательное учреждение

высшего профессионального образования

«Оренбургский государственный университет»

Кафедра вычислительной техники

В.Н. ТАРАСОВ, А.Л. КОННОВ, Е.В. МЕЛЬНИК

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

Рекомендовано к изданию редакционным издательским советом государст-

венного образовательного учебного высшего профессионального образова-

ния «Оренбургский государственный университет»

Оренбург 2005

УДК [681.324:519.8+004.421](075.8)ББК 22.20я7

ББК 22.20я7

Т 19

Рецензенты:

декан факультета информатики, заведующий кафедрой информационных

систем и технологий Самарского государственного аэрокосмического

университета, заслуженный работник высшей школы РФ, Академик меж-

дународной академии информатизации, д.т.н., профессор С.А. Прохоров;

д.т.н., профессор А.Н. Коварцев.

Тарасов В.Н.

T 19 Компьютерное моделирование.[Текст]: лабораторный практикум.

В.Н. Тарасов, А.Л. Коннов, Е.В. Мельник. – Оренбург: ГОУ

ОГУ, 2005. – 128 с.

Лабораторный практикум предназначен для студентов специально-

стей направления 230100 – Информатика и вычислительная техника.

ББК 22.20я7

©Тарасов В.Н., Коннов А.Л., Мельник Е.В., 2005

Введение

Моделирование является одним из наиболее распространенных спосо-

бов изучения различных процессов и явлений и широко используется в науч-

ных исследованиях и инженерной практике. Различают физическое и матема-

тическое моделирование. При физическом моделировании модель воспроиз-

водит изучаемый процесс с сохранением его физической природы. Под мате-

матическим моделированием понимают способ исследования различных про-

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

но описываемых одинаковыми математическими соотношениями. Например,

детерминистические объекты могут быть описаны конечными автоматами,

дифференциальными уравнениями, а стохастические объекты, учитывающие

случайные факторы - вероятностными автоматами, системами массового об-

служивания и марковскими процессами.

Построение математической модели сложной системы в целом часто

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

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

темы вплоть до элементов, сохраняя связи между подсистемами. Тогда слож-

ную систему можно определить как многоуровневую конструкцию из взаимо-

действующих элементов, объединяемых в подсистемы различных уровней. В

качестве такой системы можно рассматривать автоматизированные системы

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

пу.

Любую сложную систему будем рассматривать как совокупность эле-

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

дач или же подчиненную единой цели. Если цели и задачи системы определе-

ны, то ставится вопрос об оценке качества ее функционирования с помощью

показателей эффективности. В зависимости от назначения системы показа-

тели эффективности могут быть различными, но чаще всего в качестве основ-

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

торая в свою очередь включает различные классы индексов. В таблице 1 при-

ведены основные классы количественных индексов производительности вы-

числительных систем.

Расчет показателей эффективности сложных систем, т.е. задача анализа

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

бует привлечения специальных математических методов и, как правило, реша-

ется с помощью ЭВМ. Показатели эффективности зависят от структуры сис-

темы, значений ее параметров, характера воздействия внешней среды, внеш-

них и внутренних случайных факторов, поэтому их можно считать функцио-

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

кие функционалы широко используются в теории сложных систем и систем-

ном анализе.

Таблица 1 - Основные классы количественных индексов производительности

вычислительных систем

Класс индекса Примеры индексов Общее определение

Продуктивность Пропускная способность

Скорость выработки

Максимальная выработка

(максимум пропускной спо-

собности)

Скорость выполнения команд

Скорость обработки данных

Объем информации, обра-

батываемой системой в

единицу времени

Реактивность Время ответа

Время прохождения

Время реакции

Время между предъявле-

нием системе входных

данных и появлением со-

ответствующей выходной

информации

Использование Коэффициенты использования

оборудования (центральный

процессор, канал ввода–выво-

да, устройство ввода-вывода)

Коэффициент использования

операционной системы

Коэффициент использования

общего модуля программного

обеспечения (например, ком-

пилятора)

Коэффициент использования

базы данных

Отношение времени ис-

пользования указанной

части системы (или ее ис-

пользования для заданной

цели) в течение заданного

интервала времени к дли-

тельности этого интервала

В связи с тем, что сложные системы функционируют в условиях дейст-

вия случайных факторов, значения функционалов являются случайными вели-

чинами и поэтому в задачах анализа производительности пользуются средни-

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

пускаемых за смену, средняя прибыль (для производственных процессов),

средняя стоимость перевозки (для транспорта), среднее время ожидания в

очереди (для систем массового обслуживания) и другие.

Таким же путем можно характеризовать и другие свойства сложных сис-

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

Для того, чтобы получить ответы на вопросы о производительности дан-

ной системы, разработчик системы на ранних этапах проектирования (систем-

ного проектирования) должен получить информацию об индексах производи-

тельности при определенных значениях параметров системы. Эту необходи-

мую для исследования информацию можно получить посредством методов

оценки производительности как от самой системы (методы измерения), если

она существует, так и от модели системы (методы моделирования).

В настоящее время существует целый арсенал измерительных средств,

как аппаратных, так и программных и микропрограммных. Под моделью сис-

темы будем понимать такое ее представление, которое состоит из определен-

ного объема организованной информации о ней и построено с целью ее изуче-

ния. Для одной и той же системы может быть построен ряд различных моде-

лей в зависимости от точек зрения и степени детализации системы (расчлене-

ния на компоненты).

Место и роль концептуальных (мыслимых) моделей при проектирова-

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

альные (математические) модели играют фундаментальную роль в оценке

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

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

ектных решений по сложным системам, в том числе и уже существующих сис-

тем в процессе их эксплуатации.

Концептуальные модели являются основой методов измерения, а также

двух классов методов моделирования: имитационного и аналитического.

Очень распространенное и удобное описание поведения системы осно-

вывается на концепциях состояния и перехода между состояниями. Состоя-

ние системы в момент времени определяется как множество значений интере-

сующих нас параметров системы в момент времени. Любое изменение этих

значений параметров означает переход системы в другое состояние. Если по-

ведение модели во времени в основном воспроизводит поведение системы и

прослеживается эволюция решений уравнений модели на заданном интервале

времени с сохранением хронологической последовательности изменения пе-

ременных состояния модели и системы, то мы имеем имитационную модель.

В аналитическом моделировании уравнения модели решаются чаще

всего путем эквивалентных формульных преобразований, которые не отража-

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

ют численные методы (типа решения задачи Коши для дифференциальных

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

то копирующую эволюцию реальной системы.

Существенным условием применимости любой модели является ее аде-

кватность реальной системе и при оценке производительности системы точ-

ность модели должна быть определена к индексам производительности, вы-

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

на модели, должны быть достаточно близки к значениям моделируемой систе-

мы при тех же входных воздействиях.

На рисунке 1 показана иллюстрация этого определения для простого

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

водительности взято общее время t

общ

обработки N заданий. Модель считается

точной, если

<−

общобщ

tt , где

- заданная максимальная ошибка, а

общ

t - ре-

зультат моделирования.

При проектировании, когда моделируемая система не существует физи-

чески или не доступна для эксперимента, моделируемую систему представля-

ют в виде концептуальной модели в действительности. Тогда точность модели

можно оценить по схеме, представленной на рисунке 2.

Система

A при рабочей нагрузке W имеет производительность P, где P-

совокупность индексов производительности (скаляры, средние и дисперсии

функционалов). Модель системы

′

при нагрузке W

′

имеет производительность

′

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

точности

′

и W

′

. Если точность модели не удовлетворительна, то в модель не-

обходимо внести изменения, а процесс проверки повторить. Эта операция на-

зывается калибровкой модели. Критерии калибровки и меры точности для

вычислительных систем приведены в таблице 2 .

Рисунок 2 - Схема итеративной процедуры калибровки

Да

′

W′

′

Ошибка

Приемлемо ?

Нет

Сравнение

(критерий

калибровки)

Система

Модель

системы

Входной поток

из N заданий

Общее время t

общ

Сравнение

Модель потока

заданий

Общее время мо-

дели t

′

общ

Точность

модели

Рисунок 1- Иллюстрация понятия точности модели

Таблица 2-Критерии калибровки модели (индекс производительности: время

прохождения задания)

Основание критерия Ошибка

Среднее время прохождения задания

()

∑

−

Время прохождения отдельного задания

()

∑

−

Продолжительность отдельного шага задания

()

∑∑

−

jiji

Символ Определение

Время прохождения задания j в системе

′

Время прохождения задания j в модели

Время выполнения шага i задания j в системе

′

Время выполнения шага i задания j в модели

Общее число заданий

Число шагов в задании j

Существующие методы и модели анализа производительности вычисли-

тельных систем представлены следующей структурной схемой (рисунок 3).

Здесь алгебраические и аппроксимационные методы образуют класс

методов и моделей аналитического вероятностного моделирования. Алгеб-

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

нием о пуассоновских входных потоках и экспоненциальности времени об-

служивания (когда известны точные результаты для вероятности состояния се-

тевой модели в виде произведения), что далеко не всегда имеет место при ис-

следовании реальных процессов.

Следующий момент связан с неоднородностью реальных потоков. Не-

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

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

родностью используемых в сложных системах управления средств вычисли-

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

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

Игнорирование же этих двух важных факторов при использовании экспонен-

циальных сетей для решения задачи анализа производительности вычисли-

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

делирования.

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

дов. Среди них в пособии выделены методы диффузионной аппроксимации

процессов функционирования систем массового обслуживания.

Под методом имитационного моделирования будем понимать способ

вычисления статистических характеристик интересующих нас случайных

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

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

экономикой, планировании, исследовании операций, проектировании термин

«имитационный эксперимент» означает способ выбора рационального

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

рукции проектируемого изделия) путем сравнивания различных вариантов.

В дальнейшем будем различать аналитическое вероятностное моделиро-

вание от имитационного моделирования в том смысле, как различаются тео-

рия вероятностей и математическая статистика.

В настоящее время существует несколько десятков специализированных

имитационных систем моделирования или же проблемно – ориентированных

систем, и их число растет.

В данном пособии для решения простейших задач по моделированию

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

Материал пособия изложен в той логической последовательности, кото-

рая приведена на рисунке 3. При этом в классе приближенных методов и мо-

делей (аппроксимационный подход) изложены научные и практические ре-

зультаты Тарасова В.Н. в данной области.

Рисунок 3 - Существующие методы и модели анализа производительно-

сти вычислительных систем

Методы и средства моделирования

вычислительных систем

Алгебраический

подход

Аппроксимационный

подход

Имитационные

модели

Экспонен

циальные

сети

Модели

диффузионной

аппроксимации

Модели

баланса

потоков

Модели спе-

циализирован-

ных систем

зык

GPSS

1 Задание на лабораторную работу №1

1 Изучить теоретический материал к лабораторной работе.

2 Сгенерировать временной ряд с заданным законом распределения с объёмом

выборки, равным N=500 (количество реализации для каждого модельного экс-

перимента равно 29).

3 Проверить качество генерирования, воспользовавшись для определения па-

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

тов.

4 Определить погрешности оценки параметров модели.

5 Пункты 2-4 повторить для объёмов выборки N=1000, 2000, 5000.

1.1 Содержание отчёта

1 Цель работы.

2 Метод и алгоритм моделирования некоррелированных временных ря-

дов для заданного закона распределения.

3 Обратная функция закона распределения вероятностей.

4 Пример реализации некоррелированного временного ряда.

5 Примеры гистограмм для различного объёма выборки - N=500, 1000,

2000, 5000, М=20.

6 Значения параметров, определенные по методу моментов, и модуль

относительной

погрешности оценки параметров закона распределения для

N=500, 1000, 2000. 5000, представленные в табличной форме (количество реа-

лизации для каждого модельного эксперимента равно 29). Для определения

параметра закона распределения и вычисления погрешности оценки параметра

можно воспользоваться пакетом Excel.

7 Графическая зависимость максимальной по модулю относительной по-

грешности оценки параметров закона распределения от объёма выборки -

N=500, 1000, 2000, 5000. Для построения графических зависимостей можно

воспользоваться пакетом Excel.

8 Выводы по работе.

Пример оформления результатов выполненной лабораторной работы для

экспоненциального закона распределения приведен ниже (пункты 4-7 отчёта).

Рисунок 1.1 - Генерирование ПСП с экспоненциальным законом распределе-

ния методом инверсного преобразования