6.2.2. Примеры практических задач агрегации графа

6.2.2.1. Компоновка электронной аппаратуры

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

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

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

6.2.2.2. Адаптивная сегментация программного обеспечения вычислительной системы

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

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

где — вероятность перехода от блока информации к Располагая этой информацией, естественно считать, что т. е. матрица связей блоков информации совпадает со стохастической матрицей (6.2.25), и нет необходимости производить осреднение (6.2.17), так как оно уже сделано при определении матрицы (6.2.25). Тогда при известной матрице переходов (6.2.25) задача оптимальной сегментации принимает детерминированный характер. Решение этой задачи методами адаптации будет рассмотрено ниже.

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

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

Пусть — число цилиндров магнитного барабана; — информация, располагаемая на цилиндре где с — информационный объем цилиндра); — вероятность обращения

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

где — время перемещения головки от цилиндра к (например, в простейшем случае где — коэффициент размерности).

Обозначим буквой вариант расположения информации, образующийся из исходного с помощью перестановки:

где

Выражение (6.2.27) означает, что информация цилиндра переводится на Таким образом, адаптация как процесс управления в данном случае однозначно определяется следующим целочисленный вектором:

с различными компонентами из отрезка натурального ряда От 1 до . Задачу синтеза оптимального расположения информации на магнитных цилиндрах теперь можно сформулировать как задачу целочисленной минимизации:

где

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

Очевидно, что оптимальное расположение зависит от состояния среды — вектора Р:

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

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

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

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

Легко заметить, что полученная задача не является задачей о разрезании графа — тут ничего не «разрезается» и не агрегируется. Эта задача ближе к так называемой задаче о назначениях (см., например, работу [126], с. 158—164). Ее можно сформулировать следующим образом.

Введем двоичную переменную такого рода: обозначает расположение блока информации на цилиндре в противном случае. Тогда минимизируемый функционал (6.2.26) можно записать в форме

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

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

содержащего компонент.

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

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

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

Это случай, когда на каждом цилиндре магнитного диска располагается не один блок информации, а много [277]. Тогда задача оптимального расположения блоков информации на магнитных дисках становится эквивалентной задаче об агрегации графа (6.2.1) — с той лишь разницей, что критерий оптимальности записывается не в форме (6.2.11), а в виде (6.2.39)

Здесь агрегация в виде (6.2.10), указывающая на расположение информационных блоков . В процессе адаптации решается следующая задача:

Последнее условие в выражении (6.2.41) означает, что при агрегации каждый информационный блок попадает только на один цилиндр. Вообще говоря, это условие может быть снято, но тогда решаемая задача перестанет быть задачей о разрезании графа, так как некоторые вершины как бы «расщепляются» в процессе агрегации.