Норенков И.П. Основы автоматизированного проектирования

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

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

синтеза

системах

автоматизированного

проектирования

)

конструктив

максимальным числом связей

с уже

распределенными

конструктивами,

т. е.

конструктив, которому

соответствует

столбец

матрице

максимальной суммой элементов.

Примеры правил выбора блока:

gj)

минимально загруженный блок;

)

максимально загруженный блок;

блок, имеющий максимальное число связей

распределяемым конст-

руктивом,

т. е.

блок

максимальным элементом

(

текущей матрицы

Y в

/-м

столбце,

где

—

номер распределяемого конструктива.

Пару правил

называют эвристикой

случае задачи

приведен-

ными

выше примерами правил имеем

3x3

= 9

возможных эвристик.

Кластеризация.

Иногда требуется равномерное распределение элемен-

тов по

имеющимся блокам. Тогда возникает задача кластеризации, которую

можно

рассматривать

как

разновидность задачи компоновки, отличающуюся

типом

ограничений: вместо ограничения типа неравенства

на

объем кластера

(блока) вводится ограничение типа равенства

на

число элементов (компонен-

тов)

кластере.

Таким образом, ограничение

(4.33)

принимает

вид п =

егЛ(п/т)

или

ent(n/m)

те

= п,

7=1

где

п -

число элементов

у'-м

кластере,

ent(«/w)

—

целая часть частного

от

деления числа элементов

п на

число кластеров

т.

Другими словами, требуется

равномерное распределение элементов

по

кластерам, минимизирующее связ-

ность кластеров

друг

другом.

частности,

некоторых алгоритмах разме-

щения

микросхем

на

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

кластеризации

—

разделения множества микросхем

на два

минимально свя-

занных подмножества одинаковой (при четном

и)

мощности.

Очевидно,

что в

задаче кластеризации после соответствующей корректи-

ровки

можно использовать правила выбора очередного элемента

и его

разме-

щения

одном

из

кластеров, аналогичные правилам

задаче компоновки. Так,

правиле

загрузка кластера будет оцениваться

не его

внутренним трафи-

ком

(связностью),

числом размещенных

в нем

элементов.

Во

всех правилах

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

тот

кластер,

кото-

ром еще не

исчерпан лимит

на

размещение. Правила

5",-

используются

без

изменений.

При

вычислении целевой функции штрафы

за

нарушение ограниче-

ний

не

предусматриваются,

так как

учет

ограничений введен

эвристики.

Возможны

другие варианты множества эвристик. Например, можно

ис-

пользовать правила,

которых очередным размещаемым элементом выбира-

ется следующий элемент:

£,)

строке которого

матрице связей находится максимальный элемент

матрицы;

iS"

)

имеющий максимальную суммарную связность

с уже

размещенными

элементами;

Основы автоматизированного

193

проектирования

Математическое

обеспечение

синтеза

проектных

решений

)

имеющий минимальную суммарную связность

с еще не

размещенными

элементами.

Для

выбранного

по

одному

из

правил

S^-

элемента

определяется клас-

тер,

котором:

}

)

имеется элемент, максимально связанный

Р',

)

уже

размещенные элементы максимально связаны

(максимальна

суммарная связность).

Из

этих правил можно скомбинировать шесть разных эвристик

добавить

эвристику,

которой сначала определяется кластер

L по

признаку минимальной

загруженности,

затем

для

него выбирается элемент

по

признаку максималь-

ной

связности

с уже

размещенными

в L

элементами. Ограничения

на

макси-

мально

допустимое число элементов

кластере введены

эвристики.

Размещение

двумерных

разногабаритных

компонентов.

Эта

задача

известна

как

задача размещения электронных компонентов

(в

кристаллах

БИС

или

на

печатных

платах)

или как

двумерная задача упаковки грузов

контейне-

ры

(в

последнем случае

ее

часто обозначают 2DBPP

(2D Bin

Packing

Problem)).

Рассмотрим подход

к ее

решению

помощью НСМ.

этой задаче задана полубесконечная полоса (контейнер

открытым вер-

хом и

шириной

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

высотой

основанием шириной

(

число компонентов равно

Требуется

упаковать

компоненты

контейнер

минимизацией высоты Язаполненной

ча-

сти

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

основанием, параллельным

дну

контейнера, повернутая

на

90°).

При

решении задача разбивается

на

подзадачи,

каждой

из

подзадач выби-

рается

слева наиболее низкий незаполненный участок контейнера

выполня-

ется

его

заполнение

по

одной

из

следующих эвристик:

Э,)

выбирается

еще не

размещенный компонент, обеспечивающий наимень-

ший

горизонтальный зазор

gap>0

(рис.

4.14);

если

gap>0,

то

компонент разме-

щается

вплотную

тому краю участка,

на

котором меньше

(по

абсолютной

величине) вертикальный зазор

г;

если компонентов

gap>0

нет,

то

участок

шириной

а и

высотой

объявляется пустотелым

заполняется фиктивным

компонентом;

)

то же, что и в

Э,,

но

выбирается компо-

нент,

обеспечивающий минимальный вертикаль-

ный

зазор

z при

исходной ориентации компонен-

та;

если таких компонентов нет,

то

делается

попытка

найти подходящий компонент

при

повер-

нутой ориентации;

)

то же, что и в

но

сначала исследуются

компоненты

при

повернутой ориентации;

)

для

очередного размещения выбирается

компонент

наибольшей площадью среди

еще

Рис.

4.14.

Размещение компо-

не

размещенных компонентов

случае положи-

нента

очередном участке

тельного зазора gap.

gap

194

4 4

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

синтеза

системах

автоматизированного

проектирования

Синтез

расписаний.

Задачи синтеза расписаний требуется решать

во

многих

приложениях, например

при

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

ных

процессов, распределении ресурсов, выборе числа

типов процессоров

для

многопроцессорных специализированных комплексов

и т. п.

Рассмотрим постановку

подход

решению одной

из

основных разновид-

ностей

задач синтеза расписаний, обозначаемой JSSP

(Job

Shop Scheduling

Problem).

исходным данным относятся:

множество

работ

А =

{А

...,

};

множество

исполнителей, называемых также машинами

(или

серверами)

М={М

,М

,...,М

};

матрица

Р =

где

—

затраты времени

на

выполнение работы

(

на

машине

М;

вектор

С =

(С,,

...,

где С —

цена

за

единицу времени работы маши-

ны

М;

ограничения

на

время окончания работ

Т =

(Г,,

...,

где Т—

предель-

ное

время

для

завершения работы

А:,

штраф

добавляемый

общим затратам

Z при

нарушении какой-либо

ра-

ботой

соответствующего

ей

временного ограничения.

Необходимо составить расписание,

при

котором минимизируются затраты

на

выполнение всех работ

учетом штрафов.

других разновидностях задач синтеза расписаний могут быть

те или

иные

усложняющие решение отличия. Примерами отличий могут быть:

много-

стадийность

—

наличие нескольких стадий обслуживания каждой работы;

разделение работ

на

несколько

групп

учет дополнительных затрат

на

пере-

наладку

машин, требующейся

при

последовательном обслуживании

работ

раз-

ных

групп;

частичная упорядоченность работ,

т. е. для

некоторых

пар

работ

введены ограничения вида

где

5 —

время начала

2-й

работы;

—

время окончания

k-й

работы.

Каждая

эвристика

при

применении

для

синтеза расписаний метода

НСМ

включает

два

правила: одно

для

выбора очередной работы, другое

для

выбора

машины,

обслуживающей

эту

работу.

Например,

при

синтезе многостадийных расписаний

качестве очередной

может

выбираться

работа:

1-е

наименьшим

Г; 2 — с

наименьшим временем

окончания

обслуживания

на

предыдущей стадии

Е.

Примеры правил выбора

машин:

1 —

машина,

на

которой обслуживание данной работы будет наиболее

дешевым;

2 —

машина,

на

которой работа будет обслужена

за

наименьшее

время.

Эти

правила образуют четыре эвристики. Можно использовать допол-

нительные

правила, например правило, учитывающее затраты времени

на пе-

реналадку

машин.

'•

195

Математическое

обеспечение

синтеза проектных

решений

Маршрутизация

транспортных

средств.

Среди задач проектирования

маршрутов транспортных средств

при

перевозке различных грузов одной

из

наиболее

трудных

для

решения считается задача

VRPTW

(Vehicle Routing

Problem with Time Windows)

задача маршрутизации транспортных средств

временными окнами. Временным окном здесь называют временной интервал,

который нужно выполнить заказ

на

перевозку.

задаче заданы:

п —

число узлов-потребителей продукта

(k-й

узел-потребитель отождеств-

ляется

k-м

заказом);

z —

число узлов-источников продукта;

т —

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

—

общее число узлов;

—

исходное расположение потребителей, источников

серверов

узлах

транспортной сети;

—

матрица расстояний между узлами;

—

нижняя

верхняя границы временного окна

для

выполнения

/-го

заказа;

р —

число типов продукта.

Кроме

того,

для

узлов-потребителей

узлов-источников заданы объемы

соответственно заказанного

имеющегося продукта каждого типа,

для

серве-

ров —

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

за

единицу расстояния пробега, штрафы

за

нарушение временных ограничений

(выход

за

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

от

цены единицы

продукта каждого типа

и от

степени нарушения ограничений.

Требуется найти график движения транспортных средств

для

выполнения

всех заказов

минимальными затратами.

Каждая

эвристика

при

использовании

НСМ

включает

себя правила

для

выбора заказа (узла-потребителя), узла-источника продукта

транспортного

средства

(не

исключено,

что для

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

более

чем по

одному источнику

и/или

серверу).

Для

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

5,)

предпочтение отдается

узлу

максимальным суммарным объемом

за-

казанного продукта;

)

выбирается потребитель

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

iS"

)

выбирается потребитель

минимальной верхней границей временного

окна.

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

ся

источнику:

£?,)

минимальным расстоянием

до

выбранного

первой части узла-потре-

бителя;

)

минимальной суммой

расстояний

до

узла-потребителя

и до

ближай-

шего

узла,

котором имеется свободный сервер;

196

4.4. Методы структурного

синтеза

системах

автоматизированного

проектирования

)

минимальным значением

h =

(Z,+

/U,

где

—

расстояния

соответственно

до

узла-потребителя

и до

ближайшего узла,

котором имеет-

ся

свободный сервер,

—

суммарный объем заказанного продукта,

U—

сум-

марный

объем продукта

источнике.

Эвристика дополняется правилом,

котором выбирается сервер:

К,)

минимальным расстоянием

до

узла-потребителя;

)

минимальным временем освобождения

от

предыдущего обслужива-

ния;

)

минимальным временем выполнения маршрута.

Синтез

топологии

каналов

передачи

данных

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

сетях. Задачи определения топологии сетей различного рода

распределения

них

трафика относятся

сложным задачам структурного синтеза. Задачи,

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

чаются

во

многих приложениях

при

синтезе сетей

распределения

в них

мате-

риальных, транспортных, информационных потоков.

Рассмотрим следующую задачу. Пусть дано:

•

множество

узлов (вершин) сети,

N—

число узлов;

•

трафик,

для его

задания используется некоторая метрика; трафик задает-

ся

виде матрицы

Т, ее

элемент

есть трафик между узлами

nj;

•

матрица

стоимостей прокладки

и/или

аренды

(за

прогнозируемое время

эксплуатации) связи между парами узлов,

С —

стоимость связи между узла-

ми

у;

•

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

оборудования,

а тип

выбирается

зависимости

от

трафика

соответствую-

щем

канале.

Необходимо минимизировать общие затраты

на

построение сети, склады-

вающиеся

из

затрат

на

прокладку

аренду связей

и на

обслуживающее обору-

дование.

Решение

задачи включает

две

процедуры:

выбор системы связей

—

кар-

каса

сети;

перенос трафика связей,

не

вошедших

каркас

называемых

хордами,

в те или

иные связи каркаса.

первой процедуре рассматривается полный граф

G =

{Y,

S}, S —

множе-

ство ребер (связей) полного графа. Каркас выбирается

виде покрывающего

дерева,

дальнейшем

нему могут добавляться некоторые другие связи.

Алгоритм выбора дерева основан

на

последовательном подключении

под-

множеству

(

вершин,

уже

включенных

дерево, очередной вершины

из

под-

множества

вершин,

еще не

включенных

дерево. Правило выбора подклю-

чаемой вершины

— ее

максимальная близость

дереву,

т. е. в

дерево

включается

связь

(&,/)

при

условии

min

W = min С

197

Математическое

обеспечение

синтеза проектных

решений

Начало исполнения алгоритма

—

включение

двух

вершин

kw.1,

которым

соответствует

минимальный элемент матрицы

С.

Поскольку

синтезируемой

сети

необходимо иметь резервные каналы

на

случай выхода

из

строя основных,

то в

построенном каркасе устраняются

висячие вершины

путем

их

соединения между собой.

Для

этого достаточно

построить

еще

одно дерево,

но уже на

графе, включающем только висячие

вершины. Таким образом, каркас будет содержать связи

двух

построенных

деревьев.

Алгоритм второй процедуры основан

на

классификации связей. Связи пер-

вого ранга

— это

связи каркаса. Связь второго ранга

— это

хорда

(/,

j),

такая,

что

имеется

вершина

k и

связи

(/,

К)

и (k, j)

включены

каркас. Хорда

Р-то

ранга

— это

хорда

(i,

j),

такая,

что

имеется вершина

k и

связи

(г, К) и (k, j)

являются связями

ранта,

меньше

Р,

причем одна

из них

имеет

рант

Р -

Результаты классификации хорд составляют матрицу

U, ее

элемент

U =

где

, —

ранг связи

(г, j).

Заполнение

матрицы

происходит

по

следующему алгоритму. Сначала всем

связям

(i,j)

первого уровня присваивается ранг

Р = 1, т. е.

принимаем

U — \.

Далее, если

= О и

имеется

>j,

такое,

что

and

=P)

= P and

1) =

true,

то

P +

Алгоритм выполняется

при

последовательном

увеличении

Р до

полного заполнения

Перенос трафика

из

хорд

связи каркаса происходит

по

эвристикам, выби-

раемым генетическим методом. Начиная

со

связей высшего ранга

кончая

связями

ранга

последовательно

каждой связи

(г, j)

применяется одна

из

следующих эвристик:

если

and

-1)

true,

то

трафик

из

связи

(/,_/)

переносится

связи

(г,

k) и

(j,K);

выбирается

соответствующее минимальной сумме

при

усло-

вии

= P -\ and

true;

трафик

из

связи

(г,

переносится

связи

(г,К)

(Д);

то же, что и п. 2, но с

измененным условием

Р - 1 and

<P-l)

true;

4) то же, что и п. 3, но

перенос трафика осуществляется только, если

С >

иначе связь присоединяется

каркасу.

результате переноса трафика часть связей ликвидируется. Благодаря

ге-

нетическому поиску, оставшаяся система связей

распределение

в них

трафи-

ка

оказываются близкими

оптимальным.

Упражнения

вопросы

для

самоконтроля

Дайте

формулировку

задачи

математического

программирования.

2. В чем

заключаются

трудности

решения

многокритериальных

задач

оптимизации?

3. Что

такое

«множество

Парето»?

198

Упражнения

вопросы

для

самоконтроля

4. Для

функции, заданной своими линиями

равного уровня (рис.

4.15),

постройте траекто-

рии

поиска методами конфигураций, дефор-

мируемого многогранника, наискорейшего

спуска

из

исходной точки

5. Как вы

считаете,

можно

ли

применять

метод проекции градиента

для

решения задач

оптимизации

ограничениями типа нера-

венств?

6. Что

такое «овражная целевая функция»?

Приведите пример такой функции

для

двумер-

ного

случая

виде

совокупности линий равно-

го

уровня.

Какие свойства характеризуют класс

NP-полных

задач?

Морфологическая таблица содержит

строк

и 24

столбца.

Сколько

различных

вариантов

структуры

представляет

данная табли-

ца?

Приведите пример

И-ИЛИ-графа

для

некоторого знакомого

вам

приложения.

10.

Приведите примеры продукций

из

знакомого

вам

приложения.

11.

Дайте предложения

по

постановке задачи компоновки модулей

блоки

для ее

решения

генетическими методами. Какова структура

хромосомы?

Рис. 4.15. Пример

для

построения

траекторий

поиска

МЕТОДИЧЕСКОЕ

ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННЫХ

СИСТЕМ

5.1.

Функции

сетевого

программного

обеспечения

Функции

характеристики

сетевых

операционных

систем

Принято выделять

в ПО АС

общесистемное

ПО,

системные среды

при-

кладное

ПО.

общесистемному

ПО

относят

ОС

используемых

ЭВМ и

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

систем,

также сетевое

ПО

типовых телекоммуникационных услуг. Основой

системной среды является система управления проектными данными,

или си-

стема

PDM

совместно

СУБД. Кроме

того,

состав

системной

среды

могут

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

сопровождения

ПО,

интел-

лектуальные средства поддержки принятия проектных

управленческих

ре-

шений. Прикладное

ПО

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

сами

пакетами программ

для

выполнения проектных

бизнес-процедур.

Различают

ОС со

встроенными сетевыми функциями

оболочки

над ло-

кальными

ОС. В

соответствии

другим признаком классификации сетевые

ОС

подразделяют

на

одноранговые

функционально несимметричные

(ОС для

систем клиент

—

сервер).

несимметричных

ОС

выделяют клиентскую

сер-

верную части.

случае использования несимметричной

ОС в

одноранговых

сетях

на

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

обе

части

ОС.

Основные функции сетевой

ОС:

•

управление каталогами

файлами;

•

управление ресурсами;

•

коммуникационные функции;

•

защита

от

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

•

обеспечение отказоустойчивости;

200

5.1.

Функции

сетевого

программного

обеспечения

•

управление

сетью.

Управление каталогами

файлами является одной

из

первоочередных фун-

кций

сетевой

ОС,

обслуживаемых специальной сетевой файловой подсисте-

мой.

Пользователь

получает

от

этой подсистемы возможность обращаться

файлам, физически расположенным

сервере

или в

другой станции данных,

применяя

привычные

для

локальной работы языковые средства.

Управление

ресурсами включает

себя функции запроса

предоставления

ресурсов. Управление удаленными ресурсами выполняется программами,

на-

зываемыми сетевыми службами.

Коммуникационные

функции обеспечивают адресацию, буферизацию, мар-

шрутизацию сообщений.

Защита

от

несанкционированного

доступа

возможна

на

любом

из

следую-

щих

уровней: ограничение доступа

определенное время,

(или)

для

опреде-

ленных станций,

(или) заданное число раз; ограничение совокупности доступ-

ных

конкретному пользователю директорий; ограничение

для

конкретного

пользователя

списка возможных действий (например, только чтение файлов);

пометка

файлов символами типа «только

чтение»,

«скрытность

при

просмотре

списка

файлов».

Отказоустойчивость определяется наличием

серверов автономных источ-

ников

питания, отображением

или

дублированием информации

дисковых

на-

копителях.

Отображение заключается

хранении двух

копий

данных

на

двух

дисках,

подключенных

одному контроллеру,

дублирование означает под-

ключение

каждого

из

этих двух дисков

разным контроллерам. Сетевая

ОС,

реализующая

дублирование дисков, обеспечивает более высокий уровень

от-

казоустойчивости. Дальнейшее повышение отказоустойчивости связано

дублированием серверов.

Чем

сложнее

сеть,

тем

острее встают вопросы управления сетью. Основ-

ные

функции управления сетью реализуются

в ПО,

поддерживающем протоко-

лы

управления, такие,

как

ICMP

SNMP

стеке

TCP/IP

или

протокол

CMIP

(Common

Management

Information

Protocol)

семиуровневой модели ISO.

Как

рассмотрено выше,

это ПО

представлено менеджерами

агентами.

Ме-

неджер

—

прикладная программа, выдающая сетевые команды. Агенты дово-

дят

эти

команды

до

исполнительных устройств

сигнализируют

событиях

состоянии устройств,

они

следят

за

трафиком

фиксируют аномалии, помога-

ют

восстановлению информации после сбоев, борются

вирусами

и т. п.

сетевых

ОС

обычно выделяют ядро, реализующее большинство

из

пере-

численных функций

и ряд

дополнительных программ (служб), ориентирован-

ных

на

реализацию протоколов, организацию распределенных вычислений

т. п. К

сетевому

ПО

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

для

разных

типов

ЛВС

(Ethernet,

TR,

AppleTalk

др.).

настоящее время выбор среди

ОС

происходит преимущественно между

тремя

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

—

UNIX, Windows

NT,

Novell

Netware.

201

Методическое

программное обеспечение автоматизированных систем

Областью применения

ОС

UNIX остаются крупные корпоративные сети

со

стеком протоколов

TCP/IP.

Отличительные свойства UNIX

—

высокая надеж-

ность, возможность легкого масштабирования сети.

Операционная

система Windows

предназначена

для

работы

сетях

кли-

ент —

сервер, ориентирована преимущественно

на

рабочие группы

средние

по

своим масштабам

сети.

ОС

асимметрична

—

включает

себя серверную

(Windows

Server)

клиентскую (Windows

Workstation) части.

Операционная

система Novell Netware

пока

сохраняет свои позиции

в не-

больших

сетях.

Состоит

из

серверной части

оболочек Shell, размещаемых

клиентских узлах.

Системы

распределенных

вычислений

При

выполнении проектных процедур

использованием более

чем

одного

узла

сети

различают режимы удаленного узла

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

(рис. 5.1).

режиме

удаленного

узла

основные процедуры приложения исполняются

на

терминальном

узле.

Связь

удаленным узлом используется

для

пересылки

файлов.

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

более

за-

метной инерционности связи,

чем

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

Дистанционное

управление

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

прямом

направлении

экранных изображений (обычно лишь изменений

них)

сжатом виде

обратном направлении, поэтому задержки меньше.

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

на

режиме дистанционно-

го

управления,

при

котором терминальный узел используется преимуществен-

но

для

интерфейса

пользователем

передачи команд управления,

основные

процедуры приложения исполняются

на

удаленном узле

(сервере).

Поэтому

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

ний.

Программное обеспечение организации распределенных вычислений

на-

зывают

ПО

промежуточного слоя (Middleware). Современная организация рас-

пределенных вычислений

сетях

Internet

/Intranet

основана

на

создании

и ис-

пользовании

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

различных

аппаратно-программных средах. Совокупность таких средств называют так-

же

многоплатформенной

распределенной

средой

—

MFC

(Crossware).

Экран

терминала

Файлы,

базы данных

Длинная

связь

при

дистанционном

управлении

Процедуры

приложения

Длинная

связь

удаленными

узлами

Рис.

5.1.

Режимы

удаленного

узла

дистанционного

управления

202