Архитектурный вид -размещение программной системы, основанной на потоках данных

Эти архитектуры являются современным вариантом архитектур, управляемых портами сообщений. При использовании механизма портов программная система делится на несколько подсистем, каждая из которых может иметь один или несколько входных портов (очередей). Порт - это текущий список входных сообщений для подсистемы. Каждая подсистема рассматривается как асинхронный процесс, т.е. все подсистемы работают параллельно. Если одна из них хочет передать некоторые данные другой, она посылает их во входной порт этой другой подсистемы. Если подсистема готова обрабатывать какие-то данные, она читает их из своих входных портов. Для организации такой связи используются операции ПОСЛАТЬ и ПОЛУЧИТЬ.

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

Постановка задачи. Пусть имеется некоторая программная система, состоящая из нескольких асинхронно выполняющихся программных процессов: Р = {pt | i = 1, 2,..., п). В компьютерной системе имеется т вычислителей, на которых предполагается выполнение процессов Р. Обозначим эти вычислители множеством V = {v- | j = 1, 2,..., т). Известна загрузка вычислителей каждым процессом, заданная матрицей Z = |z(y|, /' = 1,2,..., и; _/= 1, 2, ...,т. Требуется выбрать оптимальное распределение компонентов программной системы по вычислителям, при котором обеспечивается нормальная работа без перегрузки системы.

Формализация задачи. Размещение компонентов ПС по вычислителям удобно представить двудольным графом вида G - (Р, V, Е), где Е - множество дуг, отображающих размещение процессов Р по вычислителям. Если ограничений на размещений компонентов Р по вычислителям нет, то в таком графе каждая вершина pt е Р соединена дугами со всеми вершинами V.

Поставим в соответствие дугам Е графа G множество переменных: X - {х^ | i = 1, 2,..., п; j = 1, 2,..., т). Каждая переменная Ху образуется по правилу Ху — 1, если будет принято решение выполнять процесс /?, на вычислителе v,. В противном случае Ху — 0.

Требуется так распределить множество процессов Р по вычислителям V, чтобы суммарная загрузка вычислителей была минимальной при условии того, что допустимая загрузка каждого вычислителя была < 1 и все процессы Р выполняются. Применительно к графовой интерпретации задача сводится к отысканию частичного графа G — (Р, V, Е0), где Еа с Е . При этом множество найденных дуг Е„ определит значение булевых переменных: Ха = {Ху | i = 1, 2,..., п; j = 1, 2,..., т).

Целевая функция в этом случае имеет следующий вид:

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

Поскольку все переменные задачи - двоичные, вторая группа ограничений имеет следующий вид:

Третья группа ограничений связана с допустимой загрузкой каждого вычислителя. Как отмечено выше, она не должна превышать единичного значения:

Решение задачи. Сформулированная задача (2.15)—(2.18) относится к классу задач линейного программирования с булевыми переменными. При малой размерности задачу можно легко решить полным перебором наборов переменных:

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >