Методы моделирования сложных систем. Параллельные вычислительные структуры. Свойства параллельных структур. Архитектура параллельных структур

РТУ МИРЭА Дизайн Дизайн И. И. Гайдель Гайдель 2007 2007 Методы моделирования сложны х систем Лекция 2 Дизайн И. Гайдель 2007 Структура курса 1. Понятие сложной системы. 2. Параллельные вычислительные структуры. Свойства параллельных структур. Архитектура параллельных структур. Матричные процессоры. 3. Моделирование сложных систем. Средства описания сложных систем. 4. Сетевые модели. Сети Петри. 5. Тензорные методы исследования сложных систем. Диакоптика. Дизайн И. Гайдель 2007 Понятие сложной системы Под сложной системой функционирования которой составляющие. будет пониматься такая допускает декомпозицию система, закон на отдельные Под структурой сложной системы понимается организация системы из отдельных элементов (подсистем), для которых указываются, во-первых, способ соединения между собой и с окружающей средой, а во-вторых, распределение функций, выполняемых системой. Отличительными особенностями подобных систем являются параллелизм, недетерминированность, наличие взаимодействующих процессов, сочетание синхронного и асинхронного управления и др. Дизайн И. Гайдель 2007 Понятие сложной системы (эмерджентность) Композиция подсистем дает возможность сложной системе приобрести новые свойства, которые отсутствуют на подсистемном уровне и не могут быть сведены к свойствам подсистемного уровня. Системны й эффект (эмердже́нтность ) (от англ. emergent — возникающий, неожиданно появляющийся) — наличие у какой-либо системы особых свойств, не присущих её элементам, а также сумме элементов, не связанных особыми системообразующими связями (несводимость свойств системы к сумме свойств её компонентов). В вычислительной технике, например, эмерджентность можно выразить так: один компьютер или множество компьютеров, подключенных к интерент, не являются ГРИДсистемой. В биологии – множество клеток не является организмом. Или понятия наследуемость, эволю ция, рождаемость неприменимы к отдельной особи, но применимы к популяции или виду в целом. В классификации систем эмерджентность может являться основой их систематики как критериальный признак системы. Дизайн И. Гайдель 2007 Структурны й подход в проектировании сложны х систем Современные подходы, используемые при анализе и синтезе структур сложных систем, основаны на методах декомпозиции, координации и агрегации, структурном подходе, подходе, основанном на теории сложности и др. Однако противоречия между сложностью создаваемых современных систем и традиционными подходами к их проектированию определяют на сегодня одну из основных задач теории систем - разработка методологии и создание систем автоматизированного проектирования, решающих основные задачи синтеза. Данная проблема включает в себя разработку методов и алгоритмов, помогающих вести направленный поиск оптимальных характеристик системы, а также позволяющих контролировать изменение этих характеристик в процессе проектирования. Указанные потребности привели к возникновению и интенсивному развитию системного подхода к проектированию сложных систем, в концепцию которого органически вписывается структурны й подход, приобретающий еще большее значение на современном этапе. Дизайн И. Гайдель 2007 Структурны й подход в проектировании сложны х систем В соответствии со структурным подходом выделяют следующие этапы: 1) выработка ряда гипотез, касающихся структур подсистем, из которых будет состоять проектируемая система; 2) формирование из данных подсистем законченных структур-кандидатов; 3) проведение анализа каждой структуры с целью определения характеристик, что позволяет сократить число структур-кандидатов и, в конечном итоге, выбрать окончательную структуру. Механизм построения альтернативных вариантов на основе обобщенной модели позволяет проектировщику получить все множество возможных структур, из которых выбираются оптимальные. Однако NP-сложность задач получения множества альтернативных вариантов не позволяет широко использовать данный подход на практике. Кроме того, поиск наилучшего варианта структуры сопряжен с необходимостью количественной оценки каждой структурыкандидата, а это в свою очередь требует наличие соответствующих математических теорий и методов. Дизайн И. Гайдель 2007 Формальны е методы представления сложны х систем Другим важным вопросом, требующим решения при проектировании сложных систем, является представление имеющихся данных и параллельных процессов в виде специальных формальных объектов, удобных для проведения над ними вычислительных и имитационных экспериментов. С большой долей достоверности можно отметить, что большинство современных сложных систем характеризуются такими свойствами, как параллелизм, недетерминированность, многоуровневость представления, сочетание синхронных и асинхронных процессов, однородность и др. Поэтому выбор формализованного языка, в наибольшей степени учитывающего особенности современных систем, является основной задачей начального этапа проектирования. Дизайн И. Гайдель 2007 Формальны е методы представления сложны х систем В качестве формализованного языка для описания сложных систем и протекающих в них процессов будем использовать сетевой формализм сети Петри (СП). Преимущества СП при описании указанных сложных систем широко описаны в литературе. Недостатком данного аппарата является отсутствие инструментария для количественной оценки моделей, выраженных в терминах СП. С другой стороны теория структур и теория сложности предоставляют алгоритмы и методы, позволяющие строить оценочные шкалы для получения количественных характеристик элементов дискретного пространства. В нашем курсе мы затронем теорию структур СП, в которой объединяются возможности сетей Петри и теории структур. Дизайн И. Гайдель 2007 Процесс проектирования сложны х систем В конце 60-х годов специалисты, традиционно занимавшиеся созданием крупномасштабных систем, стали осознавать необходимость упорядоченности действий в процессе проектирования сложных систем. Таким образом, разработчики начали формализовать процесс создания систем, разбивая его на следующие фазы: выработка цели - определение функций системы, анализ - определение подсистем и процедур взаимодействия, синтез - разработка подсистем по отдельности, объединение - соединение подсистем в единое целое, тестирование - проверка работы системы, внедрение - введение системы в действие, эксплуатация - использование системы. . Дизайн И. Гайдель 2007 Процесс проектирования сложны х систем Данная последовательность всегда выполнялась итерационно, потому что требования пользователей постоянно менялись. С этой концепцией создания систем постоянно возникали сложности. Эксплуатационные расходы, возникавшие после сдачи системы, стали существенно превышать расходы на ее создание. Исследования показали, что наибольший процент ошибок приходится на два первых этапа (выработка цели и анализ). Однако стоимость обнаружения и исправления допущенных ошибок становилась выше на более поздних стадиях реализации проекта. Например, исправление ошибки на стадии анализа стоит в два раза дороже, чем на стадии выработки цели, на стадии тестирования - в 10 раз, а на стадии эксплуатации - в 100 раз. Дизайн И. Гайдель 2007 Процесс проектирования сложны х систем В ходе проектирования перед разработчиком структуры сложного объекта встают следующие задачи. 1. Каким образом построить множество альтернативных вариантов структуры проектируемого объекта и в какой форме представить это множество? 2. Какую степень детализации модели выбрать для анализа каждого альтернативного варианта с целью выбора наилучшего? 3. Какие методы использовать для уменьшения трудоемкости перебора и сравнения вариантов? Представление о множестве альтернативных вариантов структуры формируется у проектировщика на основании опыта проектирования, научных законов, известных прототипов и близких решений, интуиции. С ростом числа альтернативных вариантов задача синтеза наилучшего варианта может быть практически неразрешимой, если ориентироваться на явное представление всего множества вариантов. Дизайн И. Гайдель 2007 Процесс проектирования сложны х систем Традиционные подходы к созданию систем приводили к возникновению многих проблем. Не было единого подхода. Результаты одного этапа не согласовывались с результатами других. Результаты проектирования с трудом поддавались оценкам, как качественным, так и количественным. Утверждалось, что когда проектировщики пользуются методологиями типа структурного проектирования и проектированием сверху вниз, они решают плохо поставленные задачи. Кроме того, выявление ошибок в создании таких систем становилось все менее доступным с помощью аппаратных средств или программного обеспечения. В результате противоречия между усложнением создаваемых систем и традиционными подходами к их проектированию стали определять на сегодня одну из центральных проблем теории систем - синтез эффективных структур сложных систем. Среди проектировщиков был выдвинут тезис: совершенствование методов анализа и синтеза есть ключ к созданию систем, эффективных по стоимости, производительности и надежности. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем В настоящее время известны различные подходы к анализу и синтезу структур сложных ВС. К ним относятся: - методы агрегативного описания сложных систем, - логико-комбинаторный подход, - подход, основанный на теории сложности, - структурный подход, - методы декомпозиции, координации и агрегации, - тензорный анализ. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Агрегативны й подход. Н.П.Бусленко рассматривает непрерывно-дискретные системы как обобщающий (самый общий и самый сложный) класс сложных систем и называет такие системы агрегативными. Понятие агрегата вместе с разработанными для него моделирующими алгоритмами использовалось при создании систем автоматического моделирования для сложных систем управления в 70-х годах. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Логико-комбинаторны й подход Одним из подходов к синтезу структур сложных систем является логикокомбинаторный подход. В основе данного подхода лежит использование особенных скобочных нормальных форм (о.ск.н.ф.) булевых функций и контекстно-свободных плекс-грамматик. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Логико-комбинаторны й подход Представление множества альтернативных вариантов в виде о.ск.н.ф. обладает следующими достоинствами: 1) позволяет уменьшить трудоемкость выбора оптимального варианта структуры; 2) наглядно представляет систему блоков, подблоков, из которых строятся варианты структуры; 3) достаточно легко может быть преобразовано в другие формы представления. Однако описание вариантов структур в виде о.ск.н.ф. имеет и ряд недостатков, к которым можно отнести: 4) ограниченность выразительных возможностей булевых функций, например, по сравнению с теорией графов; 5) определенную трудоемкость идентификации специальной скобочной записи альтернативного варианта, что отрицательно сказывается при решении комбинаторных задач, близких к NP-сложным. В связи с этим логико-комбинаторный подход имеет ограниченную форму применимости и не является эффективным при проектировании структур сложных систем. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Поиск наилучшего варианта структуры сложной системы сопряжен с необходимостью количественной оценки каждой структуры, а это в свою очередь требует наличия соответствующих математических теорий и методов. В этом плане особый интерес представляют теория структур и теория сложности. Использование данных теорий при проектировании позволяет управлять процессом поиска и значительно уменьшить сложность решаемых задач. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Теория сложности Один из основоположников теории сложности Глейк писал, что двадцатый век останется в истории науки, как век создания теории относительности, квантовой теории и теории хаоса. Именно благодаря им ученые были вынуждены отказаться от детерминизма в науке, перестать смотреть на мир как на механическую модель Ньютона. Сегодня наука требует холистического взгляда на мир во всей его сложности, взаимосвязанности и взаимозависимости. Принцип холизма гласит: целое всегда есть нечто большее, чем простая сумма его частей. С холистической позиции, весь мир — это единое целое, а выделяемые нами отдельные явления и объекты имеют смысл только как часть общности. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Теория сложности Все теории управления смотрят на организацию как на нечто стремящееся к порядку и стабильности. Теория сложности сосредотачивает свое внимание на элементах в организации, которые традиционно относили к помехам, беспорядку, хаосу и неразберихе. Теория сложности подчеркивает, что именно в этом беспорядке находятся ростки будущего развития и преображения. Пионером в теории сложности традиционно считают Эдварда Лоренца. Он работал над проблемами долгосрочных прогнозов погоды. Используя достаточно простую математическую модель, построенную всего на двенадцати формулах, он с помощью компьютера симулировал различные метеорологические условия. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Теория структур (теория решеток) Следует отметить, что современная алгебра изучает операции и отношения на множествах. Непустое множество с определенными на нем операциями и отношениями принято называть алгебраической системой. Простейшим примером такой системы является частично упорядоченное множество. Частично упорядоченное множество L, в котором для любых двух элементов a и b существует точная нижняя и точная верхняя грани, называется структурой или решеткой. Мы будем использовать термин «структура». Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Декомпозиция , агрегатирование Декомпозиция — разделение целого на части. Также декомпозиция — это научный метод, позволяющий заменить решение одной большой задачи решением серии меньших задач, пусть и взаимосвязанных, но более простых. Декомпозиция, как процесс расчленения, позволяет рассматривать любую исследуемую систему как сложную, состоящую из отдельных взаимосвязанных подсистем, которые, в свою очередь, также могут быть расчленены на части. В качестве систем могут выступать не только материальные объекты, но и процессы, явления и понятия. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Декомпозиция , агрегатирование Агрегатирование - метод конструирования изделий на основе применения унифицированных и стандартных составных частей путём изменения характера их соединений и пространственного сочетания, применительно к заданным условиям. Агрегатирование сокращает трудоёмкость проектирования и изготовления изделий, упрощает их эксплуатацию, позволяет производить агрегатный ремонт, облегчает проведение модернизации отдельных морально устаревших составных частей. (Большой энциклопедический политехнический словарь) Агрегатирование позволяет скомпоновать новую машину с уже спроектированных и освоенных производством сборочных единиц и агрегатов, а не создавать ее как оригинальную, единственную в своем роде. Это позволяет значительно увеличить мощности предприятий без лишних затрат, без увеличения производственных площадей. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Тензорны й подход Исследование, расчет и проектирование сложных систем давно является одной из основных проблем современной науки. Многообразие объектов, которые называют сложными системами, столь велико, что трудно найти между ними что-то общее, кроме их сложности. Накопленный опыт разработки таких систем показывает, что установилось мнение об индивидуальности каждой сложной системы, необходимости разрабатывать специально для нее теорию, методы расчета и проектирования. Это снижает эффективность разработок, не позволяет использовать уже полученные результаты при разработке новых систем. Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Тензорны й подход Для того, чтобы получить единый подход к исследованию сложных систем любой структуры и различной природы, предназначена тензорная методология. Роль тензорных методов сформулирована в книге академика В.Г. Афанасьева "Общество: системность, познание, управление" [1]: "...Тензорный анализ позволяет отделить субъективное в изучении явления, связанное с позицией ученого, с выбором той или иной системы координат, от объективного, объективной реальности, которая не зависит от точки зрения, от системы координат". Дизайн И. Гайдель 2007 Подходы к анализу структур сложны х систем Тензорны й подход Тензорное исчисление возникло в математике для решения проблем, методологически аналогичных тем, которые решаются при анализе сложных систем. Понятие тензора связано с преобразованием систем координат и является, закономерным развитием представлений о пространстве. Впервые систематически идею использования тензорного подхода изложил американский инженер Г.Крон, который использовал тензорные методы при анализе электрических машин. В дальнейшем тензорные методы развивались как в работах отечественных, так и в работах зарубежных ученых В нашем курсе мы рассмотрим вопросы применения тензорных методов при исследовании сложных систем, представляемых сетями Петри. Дизайн И. Гайдель 2007 Пример сложной системы с разделяемы ми ресурсами Обедаю щие философы Дизайн И. Гайдель 2007 Спасибо за внимание!