Донецкий национальный технический университет

Зима Константин Михайлович

Реферат выпускной работы

ПАРАЛЛЕЛЬНАЯ МОДЕЛИРУЮЩАЯ СРЕДА ДЛЯ ДИСКРЕТНЫХ СИСТЕМ

Актуальность

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

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

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

Необходимо решить следующие задачи:

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

Никто не может предсказать принесёт ли планируемая или предложенная организация производства и логистических систем желаемые результаты и как новые инструкции на выполнение работы, рабочее время и размеры партий отразятся на всё процессе. Решения относительно предложенных изменений, которые приведут к значимым экономическим последствиям должны быть оценены осторожно и объективно.

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

• Определение правил приоритета в планировании использования машин. В каком порядке должна происходить обработка на машине ? Какой эффект окажет этот порядок на время ожидания и коэффициент загрузки.
• Нормирование потока материалов. Сколько грузоподъемников необходимо в конкретном магазине ? Насколько высока загруженность транспортных средств ?
• Изучение системы заказов магазина. Какую закупку необходимо произвести и когда ?
• Изучение стратегии эксплуатации. Какое влияние поломки оказывают на производительность системы ? Нужно производить планово-предупредительный ремонт или починку ?
• Изучение сложных систем с очередями. Какая последовательность обработки даёт лучший результат ? Сколько обслуживающих приборов необходимо использовать.
• Анализ степени риска в инвестиционных проектах. Какая вероятность успеха инвестиционного проекта ? Какая вероятность понесения убытков ?

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

В задачи количественного изучения системы входят:

• Анализ динамики поведения системы при постоянных входных данных.
• Анализ динамики поведения системы при изменяющихся входных данных
• Анализ альтернатив в проектировании системы
• Определение необходимых входных данных для получения желаемых выходных данных.

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

• Определение правил приоритета в планировании использования машин. В каком порядке должна происходить обработка на машине ? Какой эффект окажет этот порядок на время ожидания и коэффициент загрузки.
• Нормирование потока материалов. Сколько грузоподъемников необходимо в конкретном магазине ? Насколько высока загруженность транспортных средств ?
• Изучение системы заказов магазина. Какую закупку необходимо произвести и когда ?
• Изучение стратегии эксплуатации. Какое влияние поломки оказывают на производительность системы ? Нужно производить планово-предупредительный ремонт или починку ?
• Изучение сложных систем с очередями. Какая последовательность обработки даёт лучший результат ? Сколько обслуживающих приборов необходимо использовать.
• Анализ степени риска в инвестиционных проектах. Какая вероятность успеха инвестиционного проекта ? Какая вероятность понесения убытков ?

Обзор систем дискретного моделирования

GPSS

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

Недостатки:

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

Другие продукты на базе GPSS:

Большим преимуществом системы моделирования GPSS/PC-TM для учебного процесса являлись наглядные, легко интерпретируемые диаграммы, представляющие текущую и накапливаемую статистику по функциональным и статистическим объектам GPSS (к сожалению, в новой версии GPSS for Window статистика по объектам дифференцирована и не столь наглядна). В новом продукте Minuteman Software GPSS World предложен целый ряд дополнительных возможностей, основные из которых:

• по всем классам объектов и переменных реализованы динамические графические окна, в которых представляется в реальном времени промежуточная и выходная статистика;
• гибкий процедурный язык PLUS, который может быть использован для целей построения моделей и в процедурах проведения эксперимента;
• средства поддержки факторного анализа, традиционный дисперсионный (ANOVA) и регрессионный анализ; оптимизация на основе методологии анализа поверхности отклика (RSA);
• элементы непрерывного моделирования;
• решены проблемы с целочисленным модельным временем.

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

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

Пакет	Производи- тель	Построение моделей				Анима- ция	Эксперимент		Страти- фикация
		Идео- графический режим конструиро- вания моделей	Построе- ние моде- лей через програм- мирова- ние	Верифи- кация в реальном времени	Средства для обра- ботки вх./вых. статистики		Анализ чувстви- тельности	Опти- мизация
Arena	Rockwell Software	Да	Да	Да	Нет/Да	Да	Да	Да	Иерархи- ческие многоуров- невые структуры
Extend	Imagine That, Inc.	Да	Да	Да	Да	Да	Да	Да	Иерархи- ческие многоуров- невые структуры
GPSS/H Prof	Wolverine Software Corporation	Нет	Да	Да	Нет	Да	Нет	Нет	-
GPSS World for Windows	Minuteman Software	Нет	Да	Да	Нет/Да	Нет	Да	Да	-
Pro Model	Pro Model Corporation	Да	Да	Да	Да	Да	Да	Да	Вложенные структуры
Taylor Enterprise Dynamics	F&H Simulations	Да	Да	Да	Да	Да	Да	Да	Вложенные структуры
Witness	Lanner Group, Inc	Да	Да	Да	Да	Да	Да	Да	Вложенные структуры

Система дискретного моделирования Arena:

Архитектура Arena

Основа технологий Arena - язык моделирования SIMAN и система Cinema Animation. SIMAN, впервые реализованный в 1982г. - чрезвычайно гибкий и выразительный язык моделирования. Он постоянно совершенствуется путем добавления в него новых возможностей. Для отображения результатов моделирования используется анимационная система Cinema animation, известная на рынке с 1984 г. Процесс моделирования организован следующим образом. Сначала пользователь шаг за шагом строит в визуальном редакторе системы Arena модель. Затем система генерирует по ней соответствующий код на SIMAN, после чего автоматически запускается Cinema animation.

Интерфейс Arena включает в себя всевозможные средства для работы с данными, в том числе электронные таблицы, базы данных, ODBC, OLE, поддержку формата DXF.

Интегрированная система моделирования и оптимизации ISSOP/ARENA:

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

Принцип работы ISSOP/ARENA представлен на следующем рисунке

Параллельная оптимизация статических и динамических имитационных моделей

Введение

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

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

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

Параллельная оптимизация статических имитационных моделей

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

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

Разаработка ПМС (Параллельной моделирующей среды)

В качестве основной структуры ПМС для даннй работы предлагается следующая организация

Параллельная оптимизация динамических имитационных моделей

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

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

Необходимые дополнения для параллельной обработки

Реализация системы коммуникации

Параллельная обработка при оптимизации должна достигаться с наименьшими затратами для пользователя. Для этих целей необходимо сконцентрировать отдельные компьютеры для объединения их в виртуальную ЭВМ. Для этих целей используется общая сетевая технология (Ethernet, Fast Ethernet), а также технология RPC (Remote Procedure Calls), предоставленная операционной системой.

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

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

Таким образом, достигается крупноячеистость, при которой достигается практически идеальное ускорение решения.

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

Распараллеливание процесса генерации и вычисления различных стартовых точек

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

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

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

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

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

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

Применение стратегий распараллеливания в ISSOP/ARENA

При решении задачи по снижению времени обслуживания рассматриваются 4 влияющих фактора:

• Повышение производительности процессоров и их применение
• Повышение степени параллельной обработки внутри процессоров
• Применение нескольких ЭВМ с распределением вычислений между ними
• Применение параллельных ВС

Экспериментальная реализация среды

Экспериментальная реализация среды состоит в реализации распараллеливания на различных типах ВС.

Возможности ISSOP/ARENA позволяют применить её на ЭВМ любого класса. Реализация может быть осуществлена на кластере либо на сосредоточенной параллельной ЭВМ.

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

Список литературы

1. Бусленко Н.П. Автоматизация имитационного моделирования сложных систем. М.: Наука, 1977, 240с.
2. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978, 400с.
3. Томашевський В.М. Iмiтацiйне моделювання систем i процесiв: Навч. посiбник. - К.: IСДО, 1994.
4. Шрайбер Т.Дж. Моделирование на GPSS: М.: Машиностроение, 1980.
5. Круг В. Моделирование и оптимизация: 2002, 250c.