Методы структурного синтеза




Синтез ВС и вычислительных процессов (ВП) включает три этапа:

· выбор типовых элементов структуры (синтез базиса);

· построение структуры (структурный синтез);

· параметризация элементов структуры (параметрический синтез).

Выбор типовых элементов структуры выполняется эмпирически. Для формализации используют матрицу «элементы — свойства» (или, что то же самое, матрицу «средства — цели»). Строкам этой матрицы соответствуют различные альтернативные элементы, выполняющие одни и те же функции, а столбцам — свойства этих элементов, важные для проектируемой ВС (ВП). В каждой клетке матрицы по балльной системе проставляется экспертная оценка i -го свойства у j -го элемента. Анализ этой матрицы проектировщиком позволит составить наглядное и достаточно полное представление о приемлемости того или иного элемента.

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

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

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

3) Направленный поиск по И—ИЛИ «дереву». Этот прием можно рассматривать как специальный случай построения частной структуры из общей. В качестве общей структуры выступает заранее составленное И—ИЛИ «дерево», в котором каждая группа путей от корневой вершины через вершины И, ИЛИ до терминальных вершин соответствует одной частной структуре
(рис. 3.5). Синтез по И—ИЛИ «дереву» удобно применить в тех случаях, когда объект легко декомпозируется на составляющие его части, которые декомпозируются на еще более мелкие и т. д., каждая декомпозиция порождает вершину типа И, а каждый уровень декомпозиции — ярус «дерева» из вершин И. Альтернативные варианты реализации каждой части объекта порождают вершину типа ИЛИ. Ветви «дерева», выходящие из вершин ИЛИ — имена способов реализации этих частей или их свойств, играющих определенную роль при синтезе. В качестве примера на рис. 3.5 приведено «дерево» И—ИЛИ для некоторого абстрактного объекта, который декомпозируется на части а, b, затем каждая из них соответственно на части c, d и e, f, g, h.


Рис. 3.5 – Структура И-ИЛИ дерева, где
1, 4, 5, 6 – вершины И; 2, 3, 8, 9 – вершины ИЛИ;
10, 11, 12, 13, 14, 15, 16 – терминальные вершины

Части a, c, h могут быть реализованы соответственно способами a1, a2, c1 , c2, h1, h2. При этом способ декомпозиции части а на с и d не зависит от способа реализации части а (a1 или a2), тогда как способ декомпозиции части b — зависит (при реализации b1, то b делится на е и f, а при реализации b2 или b3 — на g и h). Очевидно, если «дерево» состоит только из вершин И, то оно описывает одну структуру объекта. Альтернативный выбор структуры определяется вершинами ИЛИ. Обход «дерева» из вершин ИЛИ возможен либо в глубину, либо в ширину. При этом с каждой альтернативной реализацией (a1 или a2; c1, c2 или c3 и т. д.) связывается оператор перехода, разрешающий переход в следующую вершину И только при выполнении определенных ограничений в вершине ИЛИ. Ограничения могут быть глобальными, относящиеся ко всему объекту (общая масса или общая стоимость ВС, общее время вычислительного процесса и т. д.), и локальными, относящимися к данной реализуемой части объекта (условия стыковки с другими ЭВМ, ВС; ограничения на параметры части ВС).

Условием успешного окончания синтеза является прохождение по всем вершинам И до терминальных вершин. Практически строить «дерево» И— ИЛИ не обязательно, достаточно иметь «дерево» декомпозиции И, в каждой вершине которого нужно программно проверять альтернативные возможности реализации, задаваемые списком этих реализаций и списком ограничений. Отметим, что проверка этих ограничений означает, что синтез носит структурно-параметрический характер, поскольку в процессе синтеза отбираются элементы с определенными значениями параметров.

Направленный поиск по «дереву» состояний и свойств. Структурно-параметрический синтез можно выполнить не только на основе И—ИЛИ «дерева», но и с помощью «дерева» состояний и свойств (рис. 3.6).


Рис. 3.6 – Дерево состояний и свойств

Каждая вершина в этом «дереве» трактуется как задача, возможное решение которой обладает свойствами , а каждый оператор перехода имеет смысл: «Если решение задачи -1 должно обладать свойством а, то перейти к решению задачи ». Таким образом, чтобы решение задачи обладало свойством , нужно решить задачу , а чтобы решение задачи обладало нужным свойством , нужно решить задачу . Корневое состояние имеет смысл исходной задачи, промежуточные состояния , — смысл промежуточных задач, на которые разбивается исходная задача синтеза, а , , , , — смысл базовых, терминальных, неделимых далее подзадач. Рассмотрим методику синтеза. Пусть известно, что решение должно одновременно удовлетворять свойствам , b, h, с). Нужно найти терминальную вершину, имеющую указанные свойства.

Решение заключается в поиске пути от к той терминальной вершине, которая обладает указанными свойствами a, b, . В этом случае имеем (), (), (b), (), (, решение должно привести в . Приведенный пример позволяет иллюстрировать некоторые характерные особенности обработки знаний в ИИ при использовании «дерева» состояний.

1) Наследование свойств. Из рис. 3.6 видно, что состояние (c, d) на самом деле кроме свойств с, d должно также обладать и свойством а предыдущей вершины состояние (e, f) — свойством b, а состояние (d, h, c) — свойством . Вследствие этого более точным было бы обозначение этих состояний в виде (c, d, a), (e, f, b), (d, h, c, ). Аналогично можно было бы уточнить запись операторов в виде ; в виде и т. д. Обеспечиваемое последовательным прохождением вершин при поиске по «дереву» передача свойств отцовской вершины к дочерним называется в ИИ «наследованием свойству). Механизм автоматического наследования свойств позволяет упростить запись и реализацию операторов перехода, не учитывая в них свойств предыдущих состояний. Он «по умолчанию» обеспечивает присутствие в последующих состояниях свойств предыдущих. Заметим, однако, что «наследование свойств» в «дереве» поиска необязательно и его можно отменить, если условиться, что «отцовское» и «дочернее» состояние по своим свойствам друг с другом не связаны, например, относятся к понятиям с разной семантикой ( — рабочий, — станок). Если же состояния в «дереве» относятся к одному классу, то механизм наследования свойств позволяет «наращивать» свойства состояний в процессе последовательного раскрытия вершин «дерева». Это особенно важно при решении задач классификации и диагностики.

2) Наследование условий перехода. По аналогии с наследованием свойств состояний можно говорить о наследовании условий перехода в операторах перехода On. Это позволяет объяснить результат поиска. Например, приход к состоянию вызван наличием свойства в и одновременно свойства в , что легко установить, анализируя условия перехода в и . Обычно процесс последовательного применения операторов перехода к раскрытию вершин «дерева» состояний запоминается в программе поиска и может быть легко воспроизведен в виде «трассы поиска», вследствие чего процедуру объяснения результатов часто называют «трассировкой поиска».

3) Поиск правил по образцу. Этот часто используемый в работах по ИИ термин означает, что левая часть правила «если -1 обладает свойством а, то переход к » «сравнивается с образцами», т. е. с перечнем фактически имеющихся имен состояний и их свойств. Совпадение левой части правила с каким-либо образцом вызывает активизацию правила, т. е. срабатывание его правой части. Кроме описанных существует большое число других методов синтеза — метод морфологического ящика, весьма близкий к поиску по «дереву» состояний и «И—ИЛИ-дереву», методы «мозгового штурма» и контрольных вопросов, относящиеся к методам решения изобретательских задач, однако в САПР они не получили распространения из-за сложности их формализации.

Параметрический синтез

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

Решение состоит в определении такой цепочки причинно-следственной связи в формулах (ранжирование формул), в которой расчет по первой формуле в этой цепочке позволил бы найти величины, необходимые для расчета, по второй формуле и т. д. По существу данная задача состоит в планировании вычислений. Алгоритмы и программы, решающие эту задачу, в теории ИИ получили название концептуальных решателей или планировщиков. Суть алгоритма планирования заключается в следующем. Найдем сначала формулу с минимальным числом неизвестных, например, с одной неизвестной, и вычислим ее. Далее снова найдем новую формулу с новой неизвестной и также вычислим ее и т. д. Легко заметить, что если построить матрицу, столбцы которой соответствуют неизвестным (часть из них задана), а строки — номерам формул, то при отыскании искомой последовательности расчета эта матрица будет иметь строго трапециевидную структуру:

а) расчет только по формулам (рис. 3.7, а);

б) расчет с решением системы уравнений относительно X 7, X 6; На рисунке показан случай, когда X 1 рассчитывается по формуле на основе известных X2, X5, а для расчета X 7, X 6, нужно решить систему из двух уравнений, после чего X 4,. X 3 опять можно рассчитать по формулам (рис. 3.7, б).


Рис. 3.7 – Построение матрицы по алгоритму планирования:
а – расчет только по формулам; б – расчет с решением системы уравнений относительно X 7, X 6; 1, 7, 6, 4, 3 – номера формул;
X 2, X 5 - заданные вершины; X 1, X 7, X 6, X 4, X 3 - искомые вершины

Для автоматизации планирования можно каждую формулу заменить фреймовой системой инструкций. Например, для формулы X 1= f 1 (X 2, X 5) можно записать:

· если известно X5, X2, то известно X 1;

· если известно X 1, X2, то известно X5;

· если известно X5, X 1, то известно X2;

· если известно X5, X2, X 1, то неизвестных нет;

· если известно X 1, то неизвестно X2, X5 и т. д.

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


Рис. 3.8 – Алгоритм прямого определения структуры матрицы:
а – случай переопределения (число формул больше неизвестных);
б – случай недоопределения; 1, 7, 6, 4, 3 – номера формул

Заключение

Технические средства, информационное обеспечение САПР позволяют создавать качественно новые вычислительные системы.

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


Часть 4



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-03-24 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: