Растригин Л.А. Адаптация сложных систем

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

связи между соответствующими элементами. Матрица (6.2.3) здесь

симметрична. Веса вершин (6.2.13) агрегированного графа Г'

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

объемов и площа-

дей. Например, при компоновке схемы в процессе ее разделения на

блоки значения c

(i = l, ..., m) определяются допустимыми размерами

блоков, плат, сборок, и т. д.

6.2.2.2. Адаптивная сегментация

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

обеспечения вычислительной

системы*

В этом случае следует воспользоваться стохастической по-

становкой задачи. Здесь агрегированными вершинами a'

являются

сегменты матобеспечения, расположенные во внешней памяти ВС.

Размеры этих сегментов ограничены объемом оперативной памяти

процессора. В этом случае c

= c (l = 1, ..., т), где с — часть объема

памяти, выделяемой для информации, поступающей из внешней

памяти, и ограничения имеют детерминированный характер.

Вероятностные свойства среды X здесь определяют обращаемость

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

простейшем случае определяются стохастической матрицей

Р = || p

т×т

(6.2.25)

где p

— вероятность перехода от l-го блока информации к k-му.

Располагая этой информацией, естественно считать, что В = Р, т. е.

матрица связей блоков информации совпадает со стохастической

матрицей (6.2.25), и нет необходимости производить осреднение

(6.2.17), так как оно уже сделано при определении матрицы (6.2.25).

Тогда при известной матрице переходов (6.2.25) задача оптимальной

сегментации принимает детерминированный характер. Решение этой

задачи методами адаптации будет рассмотрено ниже.

6.2.2.3. Адаптация расположения блоков

информации

на магнитных дисках**

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

процесс минимизации времени на обращение к внешней памяти.

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

записи-считывания.

Пусть т — число цилиндров магнитного барабана; a

— ин-

формация, располагаемая на l-м цилиндре (a

<c, где с — ин-

формационный объем цилиндра); p

— вероятность обращения

* См. подраздел 2.2.5.1.

** См. подраздел 2.2.5.2.

к информации, расположенной на l-м цилиндре. Среднее время

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

(6.2.26)

где φ(l,k) — время перемещения головки от l-го цилиндра к k-му

(например, в простейшем случае φ(l, k) = w |l—k|, где w —

коэффициент размерности).

Обозначим буквой U вариант расположения информации, об-

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

(6.2.27)

Выражение (6.2.27) означает, что информация a

с l-го цилиндра

переводится на k-й. Таким образом, адаптация как процесс управления

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

вектором:

U = (u

, ..., и

) (6.2.28)

с различными компонентами из отрезка натурального ряда От 1 до т.

Задачу синтеза оптимального расположения информации на

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

целочисленной минимизации:

(6.2.29)

где

Р = (p

, ..., p

) (6.2.30)

— вектор вероятностей обращения к блокам информации a

,...

(6.2.31)

Очевидно, что

оптимальное расположение U

зависит от состояния среды — вектора

Р:

= U

(P). (6.2.32)

При известном векторе Р задача адаптации, как видно, сводится к

задаче оптимизации (6.2.29), т. е. является детерминированной.

При неизвестном или изменяющемся Р приходится пользоваться

его оценкой

(6.2.33)

на базе конечного времени наблюдения за процессом

работы магнитного диска. Процесс адаптации должен быть построен

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

, ..., U

, ..., (6.2.34)

каждая из которых использует последнюю оценку (6.2.33), отражала

оптимальное расположение информации на дисках по критерию

(6.2.29) в каждый конкретный момент времени.

Легко заметить, что полученная задача не является задачей о

разрезании графа — тут ничего не «разрезается» и не агрегируется.

Эта задача ближе к так называемой задаче о назначениях (см.,

например, работу [126], с. 158—164). Ее можно сформулировать

следующим образом.

Введем двоичную переменную u

такого рода: u

=1 обозначает

расположение l-го блока информации a

на k-м цилиндре (l, k = l, ..., m)

и u

= 0 в противном случае. Тогда минимизируемый функционал

(6.2.26) можно записать в форме

(6.2.35)

При этом должны выполняться следующие очевидные огра-

ничения:

(6.2.36)

Первое из них выражает очевидное требование, чтобы на каждом

k-м цилиндре располагался только один информационный блок.

Второе ограничение связано с тем, что каждый l-й блок должен

располагаться только на одном цилиндре, а третье определяет

бинарность искомого вектора

U = (u

, u

, ..., u

), (6.2.37)

содержащего т

компонент.

(6.2.38)

где отмечена зависимость вероятностей от состояния среды X.

6.2.2.4. Обобщение предыдущей задачи

Это случай, когда на каждом цилиндре магнитного диска

располагается не один блок информации, а много [277]. Тогда задача

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

дисках становится эквивалентной задаче об агрегации графа (6.2.1) —

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

форме (6.2.11), а в виде

(6.2.39)

Здесь U — агрегация в виде (6.2.10), указывающая на рас-

положение информационных блоков a

(i=1,...,m). В процессе

адаптации решается следующая задача:

(6.2.40)

где

(6.2.41)

Последнее условие в

выражении (6.2.41) означает, что при агрегации каждый

информационный блок попадает только на один цилиндр. Вообще

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

перестанет быть задачей о разрезании графа, так как некоторые

вершины как бы «расщепляются» в процессе агрегации.

6.2.3. Адаптивная агрегация графа

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

6.2.3.1. Методы агрегации (разрезания) графа

Существует целый ряд методов агрегации (разрезания) графа; их

подробный обзор приводится в работе [111]. Эти методы

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

случайного поиска).

Задача адаптации в этом случае имеет вид

Детерминированные методы используют для разрезания графа

известный метод ветвей и границ [27, 66, 201], а также различного

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

задачу [1, 2, 38, 106, 129, 147, 224]. Однако такие методы не позволяют

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

лишь одно локальное решение. Именно это обстоятельство заставляет

искать стохастические подходы к решению задачи о разрезании графа

большой размерности.

Стохастический подход к разрезанию графа связан с намеренным

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

быть сделано по-разному. Простейшей схемой является рандомизация

перебора [37, 53, 97].

Рассмотрим стохастические методы, решающие задачу разрезания

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

шага в процесс разрезания с последующей оценкой его

эффективности.

6.2.3.2. Операции преобразования агрегации

Введем операции преобразования агрегации U:

N+1

= ψ

N+1

) , (6.2.42)

где U

— агрегация на N-м этапе, a ψ

N+1

— оператор ее изменения на

следующем, (N+1)-м этапе. Задача агрегации графа заключается в

определении оператора изменения агрегации.

Назовем операцией первого рода перенос одной (i-й) вершины из

одного (k-го) сегмента в другой (l-й). Здесь сегментами названы

вершины агрегированного графа Г'. Эту операцию, символически

изображенную на рис. 6.2.1, будем обозначать тройкой

ψ = ‹ kil ›, (6.2.43)

причем i I

и i I

Эффект от такой операции легко вычислить. Очевидно, что в

агрегированном графе Г' произойдут следующие изменения:

а'

→ а'

— а'

; (6.2.44)

а'

→ а'

+ а'

выражающие изменение сегментов, а также

(6.2.45)

Рис. 6.2.1. Операция первого рода. Рис. 6.2.2. Операция второго рода.

выражающие изменение связей между сегментами. Изменение

критерия (6.2.11) имеет вид

(6.2.46)

Знак этого приращения

определяет, очевидно, эффективность операции (разумеется, при

соблюдении ограничений (6.2.12)). Операция второго рода связана с

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

ее четверкой

ψ = ‹ kilj ›, (6.2.47)

где, очевидно, и

При этом происходят следующие изменения в агрегированном

графе Г':

а'

→ а'

— а

+ a

;

а'

→ а'

+ а

— a

; (6.2.48)

Приращение критерия Q при этом равно

(6.2.49)

Легко видеть, что

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

последовательность выполнения двух операций первого рода:

‹ kilj › = ‹ kil › ‹ ljk ›. (6.2.50)

Произведение (6.2.50) коммутативно, так как результат не зависит

от порядка проведения операций первого рода. Это хорошо видно из

выражения (6.2.49), где первые два члена определяют результат

операции ‹ kil ›, а вторые два — операции ‹ ljk ›.

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

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

вершины и сегменты, участвующие в этой операции. Будем исходить

из какой-то (например, случайной) исходной сегментации графа.

6.2.3.3. Алгоритм устранения нарушения ограничений

Так как соблюдение ограничений S на объем сегментов (6.2.12)

имеет больший приоритет, чем оптимизация значений критерия, то в

этом случае критерием выбора операции и сегмента является только

нарушение ограничений. Алгоритм устранения нарушений S состоит в

следующем:

1. Определяется номер сегмента, в котором нарушается ог

раничение:

k : a'

> c

. (6.2.51)

Если таких сегментов несколько, то все они, кроме одного (k-го),

исключаются из рассмотрения до тех пор, пока не будет устранено

нарушение (6.2.51).

2. Среди оставшихся сегментов, удовлетворяющих ограни

чению, ищется сегмент с максимальным «запасом»:

(6.2.52)

3. В сегменте I

определяется

вершина, вес которой макси

мально приближается снизу к запасу (6.2.52), т. е. решается

задача

(6.2.53)

Здесь возможны два варианта. Если такая

вершина находится в I

, то с ней производится операция первого рода

(6.2.43), а далее — переход к п. 1. Если же такой вершины не

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

4. Для этого из всех оставшихся сегментов случайно выби

рается один (l-й) с вероятностью

(6.2.54)

Рис. 6.2.3. Блок-схема алгоритма, устраняющего нарушение ограничения.

Пунктирные стрелки а и б — для случая адаптивного разрезания (см. п.

6.2.3.6).

5. В сегменте I

случайно выбирается одна вершина а

, а в сегменте

ищется (j-я) вершина, обладающая свойством

— ∆a'

≤ a

< a

. (6.2.55)

Если такая j-я вершина в I

найдется, то производится операция

второго рода вида (6.2.47). При этом в случае

— a

≥ a'

— c

(6.2.56)

нарушение в I

устраняется полностью, далее — по п. 1. В противном

случае нарушение уменьшается и следует обратиться к п. 5. При этом

новую вершину a

целесообразно исключить из случайного

«розыгрыша».

Если же в I

не найдется вершины, удовлетворяющей условию

(6.2.55), то следует обратиться к п. 4, исключив из рассмотрения a

Указанное исключение вершин в конце концов исчерпывает

сегмент I

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

исключая l-й из дальнейшей «игры».

Блок-схема этого алгоритма показана на рис. 6.2.3.

6.2.3.4. Локальная минимизация

критерия при неизменной

среде [115]

Пусть ограничения S выполнены (априори или с помощью

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

(6.2.11) X=const решается следующим алгоритмом.

1. Случайным образом выбирается пара сегментов (k-й и l-й) с

вероятностью

(6.2.57)

(тем самым стохастически выбирается максимально

связанная пара сегментов).

2. Для каждого из сегментов пары определяется «запас»:

∆a'

= c

— a'

; (6.2.58)

∆a'

= c

— a'

и выбирается сегмент с наименьшим запасом (пусть это k-й сегмент, т.

е. ∆a'

<∆a'

3. Строится множество {Z} номеров элементов k-гo сег

мента, удовлетворяющих условию

≤ ∆a'

(z I

),. (6.2.59)