МОДУЛЬ 2. АСОИУ КАК ОБЪЕКТ ПРОЕКТИРОВАНИЯ

(6-й весенний семестр, 3-й курс)

ГЛАВА 5. МОДУЛЬНЫЙ ПРИНЦИП ПРОЕКТИРОВАНИЯ АСОИУ

Общая постановка задачи

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

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

Модульное проектирование АСОИУ обладает рядом преимуществ:

— упрощается процесс разработки и отладки программного и информационного обеспечения АСОИУ;

— упрощается последующая модификация системы, так как модульные программы могут быть улучшены путем простой замены отдельных модулей, которые функционально эквивалентны, но имеют лучшие системные характеристики;

— улучшается организация управляющих программ;

— появляются возможности внедрения передовых методов разработки и автоматизации проектирования АСОИУ.

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

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

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

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

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

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

Основой для формализованной постановки и решения задач анализа и синтеза модульных АСОИУ является определение модулей системы и межмодульного интерфейса.

Могут быть выделены различные способы разбиения информационного и программного обеспечения АСОИУ на отдельные модули:

функциональный – по числу информационных и управляющих связей между модулями;

ресурсный – по имеющимся возможностям технического и программного обеспечения разработки;

элементный – по использованию типовых и стандартных элементов решений;

смешанный – обеспечивающий выше перечисленные.

Перейдем к формализации.

Пусть А={a₁, a₂, …, a_m} – множество задач, выявленных на предпроектной стадии. Каждое a_i в общем случае характеризуется n – мерным вектором показателей x_i, которыми являются время выполнения, число входных и выходных переменных, требуемый объем памяти и т.д.

Все задачи информационно взаимосвязаны. Это можно задать орграфом Г=(A, D), у которого вершины А={a₁, a₂, …, a_m} – это задачи, а ребра D – информационные связи между задачами (процедурами).

Пусть граф Г задан матрицей смежности ║ d_ij║, причем d_ij=1, если существует информационная дуга из задачи a_i в задачу a_j, и d_ij=0 в противном случае. Каждая дуга между элементами a_i и a_j характеризуется некоторым параметром ρ _ij, который может быть и вектором. Будем считать, что ρ _ij=0, если d_ij=0.

Обозначим через Е={θ } – множество всех возможных разбиений множества А на отдельные подмножества, т.е. каждое θ таково, что

Θ =(А₁^θ, …, А_ℓ^θ, …, А_{L(θ )}^θ), , , i, j=1,.., L(θ ), i≠ j.

Рассмотрим некоторое разбиение θ. Подмножество А_ℓ^θєθ будем в дальнейшем называть модулем.

Для данного разбиения θ множество дуг исходного графа Г распадается на L(θ )+1 попарно не пересекающихся подмножеств: а) подмножество внутреннее G_ℓ^θ дуг, соединяющих вершины из А_ℓ^θ; б) подмножество внешнее D^θ дуг, концы которых лежат в разных модулях. Внешние дуги, входящие в какой-либо элемент модуля А_ℓ^θ называют его входом, а выходящие из какого-либо элемента – выходом.

Разбиению θ можно сопоставить агрегированный граф Г^θ, получающийся из исходного графа Г в результате объединения всех вершин подмножества А_ℓ^θ в одну для каждого ℓ =1,.., L(θ ). Из вершины А_r^θ в вершину А_k^θ идет дуга тогда и только тогда, когда в графе Г имеется дуга, направленная от некоторой вершины a_iє А_r^θ в вершину a_jє А_k^θ. Дугам графа Г^θ сопоставим параметры r≠ k,

где C_rk^θ={(i, j): a_iєA_r^θ, a_jєA_k^θ, d_ij=1}.

Агрегированный граф Г^θ описывает разбиение исходной системы на модули.

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

5.2. Постановка и модель решения задачи разбиения ИЛМ АСОИУ на

функциональные модули с минимальным числом информационных связей

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

Исходными данными для задачи являются:

1) множество различных типов входных, промежуточных и выходных данных,

2) множество необходимых процедур преобразования данных.

При этом задачи относятся к одному и тому же уровню (см. л. 8).

Отношение, т.е. оператор отображения множества процедур к множеству информационных элементов можно представить в виде двудольного графа, дуги которого соединяют процедуры с соответствующими информационными данными (см. рис. 4.5.1).

Рис. 4.5.1. Двудольный граф связи процедур и информационных элементов

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

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

Для формализации задачи введем следующие обозначения:

А={a₁, a₂, …, a_j, …, a_m} – множество задач, далее процедур системы обработки данных

R={r₁, r₂, …, r_ℓ, …, r_L} – множество информационных элементов

1, если информационный элемент r_ℓ используется для выполнения

процедуры а_j

0, в противном случае

Введем в рассмотрение следующие переменные:

1, если процедура а_jвходит в модуль А_i, j=1,.., m; i=1,.., M=2^m-1

0, в противном случае

и связанные с ней переменные:

1, если ; i=1,.., M; ℓ =1,.., L

y_{ℓ i}=

0, если

т.е. y_{ℓ i}=1, если r_ℓ - й информационный элемент используется процедурой a_j, которая размещается в модуле А_i.

При этих обозначения суммарное число различных информационных элементов, являющихся общими для различных модулей А_i, i=1,.., M равно

(1)

При ограничениях:

1. На число выделяемых модулей M₀≤ M (2)
Каждая процедура хотя бы в одном модуле должна находиться:

j=1,.., m (3)
3. Число процедур в одном модуле может быть ограничено некоторой величиной N: i=1,.., M₀ (4)
4. Некоторые процедуры j и j` должны быть разнесены по разным модулям, т.е.

x_ij+x_ij_`≤ 1, i=1,.., M₀ (5)

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

i=1,.., M₀ (6)

6. Ограничения на сложность взаимодействия информационных элементов и процедур внутри модулей, т.е.

i=1,.., M₀ (7)

7. Ограничения на количество сложных связей между информационными элементами и некоторой парой i и i` модулей, т.е.

(8)

Задача (1)-(8) является задачей квадратичного целочисленного программирования.

Для удобства решения она может быть сведена к линейной форме путем линеаризации выражений (1) и (8).

Введем переменную

1, если ℓ -й информационный элемент необходим для модулей А_i и A_i`

Z_{ℓ ii`}=

0, в противном случае

Тогда критерий (1) может быть записан так:

(9)
Ограничение (8) при этом будет иметь вид:

для заданных i и i` (10)

Задача разбиения, представленная выражениями (9), (2)-(7), (10) имеет линейный вид и может быть решена с использованием стандартных методов.

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

Пусть граф задачи содержит пять процедур и шесть информационных элементов (см. рис. 4.5.2).

d_ℓ a_r

Рис. 4.5.2. Граф взаимосвязи процедур с информационными элементами

Матричная форма соотношений между процедурами и информационными элементами приведена в таблице 4.5.1.

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

Рассмотрим решение задачи при следующих ограничениях:

1) общее число модулей V=2;

2) общее число информационных элементов в каждом из модулей L_v≤ 6, v=1, 2;

3) общее число процедур в каждом модуле M_v≤ 4, v=1, 2.

Таблица 4.5.1. Матричная форма соотношений