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

3.7.1. Постановка задачи

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

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

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

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

1) минимизация времени обмена с внешней памятью,

2) минимизация суммарных затрат на хранение и использование полученной системы информационных массивов,

3) минимизация времени решения одной какой-либо, обычно наиболее важной, задачи.

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

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

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

3.7.2. Задача и модель определения числа и состава информационных массивов

Пусть в результате диагностического анализа проектируемой АС для заданного комплекса задач управления определено множество программных модулей M={m₁, m₂,…, m_v,…, m_V}, где V – число таких модулей. Для каждого модуля m_v установлена средняя частота его функционирования Q_v (v=1,..,V) в заданный интервал времени, например, в сутки. Известно также множество информационных элементов D={d₁, d₂,…, d_ℓ,…, d_L}, где L – число таких элементов, с которыми связаны модули множества M. Каждый информационный элемент d_ℓ характеризуется длиной записи, например, в байтах λ_ℓ. Величины λ_ℓ (ℓ=1,..,L) образуют вектор Λ={λ₁, λ₂,…, λ_ℓ,…, λ_L}.

Для каждого модуля m_v (v=1,..,V) информационный элемент d_ℓ (ℓ=1,..,L) может быть входом, выходом или модуль m_v никак не связан с информационным элементом d_ℓ. В первом случае будем говорить, что модуль m_v считывает элемент d_ℓ, а во втором – модуль m_v записывает элемент d_ℓ.

Связь между модулями и информационными элементами может быть задана в виде двух матриц. B^с=║b_vℓ^c║ и B^з=║ b_vℓ^з ║, где b_vℓ^c(b_vℓ^з) равен единице, если ℓ-й информационный элемент (ℓ=1,..,L) считывается (записывается) v-м модулем (v=1,..,V) и равен нулю в противном случае.

Обозначим через F возможное число информационных массивов, по которым распределяются информационные элементы. Очевидно, что F≤L.

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

1, если ℓ-й информационный элемент размещен в f-й массив

x_ℓf=

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

1, если

z_vf^с= (1)

0, если

1, если

z_vf^з= (2)

0, если

Другими словами z_ℓf^с(з) принимает значение 1, если модуль m_v связан с информационным элементом d_ℓ, который находится в массиве f.

Переменные x_ℓf (ℓ=1,..,L; f=1,..,F) образуют матрицу X=║ x_ℓf ║, определяющую распределение информационных элементов по информационным массивам. Матрицы Z^c=║ z_ℓf^с ║ и Z^з=║ z_ℓf^з ║ размерности V*F каждая определяют связь программных модулей с информационными массивами.

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

(3)

при ограничениях

(4)

(5)

(6)

где z_ℓf^с и z_ℓf^з определяются выражениями (1) и (2);

N_f – ограничения на общее число информационных элементов в f-м массиве;

- ограничения на длину записи в f-м массиве.

Значения величин , N_f, f=1,..,F определяются разработчиком АСУ исходя из ограничений, наложенных на внешние запоминающие устройства выбранной ЭВМ.

Задача (1) – (6) относится к классу задач целочисленного нелинейного программирования и может быть решена методом ветвей и границ. Алгоритм решения этой задачи будет рассмотрен в следующем семестре.

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

M – множество модулей: M={m_v; v=1,..,V};

B – множество определяемых информационных массивов: B={b_f; f=1,..,F};

Z^с(з) – множество дуг, связывающих множество модулей с множеством массивов: Z^с(з)=║z_vf^с(з)║.

 

Рис. 3.19. Графовая модель задачи

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

Как об этом уже говорилось, критериями, используемыми для решения данных задач, являются: 1) минимизация суммарных затрат на создание, хранение и эксплуатацию информационных массивов и программных модулей СОД либо 2) минимизация общего времени обработки данных или времени решения одной из задач обработки данных.

Введем необходимые обозначения:

I={1, 2,…, i,…, I₀} – множество задач обработки данных;

 

N=║n_iv║ - матрица принадлежности модуля к задаче,

 

т.е.

1, если модуль v используется для решения задачи i;

n_iv=

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

 

M^с(з)=║m_vf^с(з)║ - матрица принадлежности массива к модулю,

т.е.

1, если f-й массив считывается (записывается) v-м модулем

m_vf^с(з)=

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

P_i – частота решения i-й задачи в АСОИУ;

q_vⁱ – частота использования v-го модуля при решении i-й задачи;

N_f – количество информационных элементов в одной записи f-го массива;

L_f – число записей в f-ом массиве;

R_f=N_f*L_f – объем (размер) информационного массива f (общее число информационных элементов в массиве);

C₀ – стоимость единицы рабочего времени процессора для решения вычислительных задач;

C_υ – приведенная стоимость единицы рабочего времени носителя информации υ-го типа с внешней памятью ЭВМ;

S_υ – стоимость блока управления υ-го типа носителя информации; υ=1,..,υ₀

τ_v^υ – время считывания v-го модуля, размещенного на υ-м типе носителя;

t_fμ^υ(с), t_fμ^υ(з) – время считывания (записи) f-го массива, организованного с использованием μ-го способа (можно использовать разные способы доступа к данным: прямой, произвольный по ключам и т.п., можно по-разному организовывать саму структуру данных: реляционная, иерархическая, сетевая и смешанная) и размещенного на υ-м типе носителя информации;

T_v – процессорное время реализации v-го модуля;

d_υ – объем запоминающего устройства υ-го типа носителя информации;

a_v – размер v-го модуля;

Δτ_v – время работы процессора при поиске v-го модуля;

Δτ_f^с (Δτ_f^з) – время работы процессора при считывании (записи) f-го массива.

Введем переменные:

1, если f-й массив организован μ-м методом и размещен на υ-м типе носителя информации

x_fμ^υ=

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

 

 

1, если v-й модуль размещен на υ-м типе носителя информации

y_v^υ=

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

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

Полные приведенные затраты C на решение задач АСОИУ являются суммой капитальных С_к и эксплуатационных затрат С_э, т.е. С=С_к+С_э.

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

(1)

- наименьшая целая часть, большая или равная α, где α – число носителей памяти типа υ=1,..,υ₀.

Эксплуатационные затраты, в общем случае, содержат следующие составляющие:

- Стоимость непосредственной вычислительной работы процессора С_э^обр; при решении задач i=1,..,I₀;

- Стоимость процессорного времени при формировании адресов С_э^ФА; для поиска нужных модулей и информационных элементов в соответствующих массивах;

- Стоимость записи и считывания массивов и модулей, т.е. стоимость обмена между оперативной и внешней памятью С_э^обм. -важно только это слагаемое

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

(2)

(3)

(4)

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

где С_к и С_э^обм определяются формулами (1) и (3) при ограничениях:

- на время T_i обмена с внешней памятью ЭВМ при решении i-й задачи: (5)

- на используемый объем носителя информации υ-го типа:

(6)

- на совместное размещение модулей и массивов в одном блоке носителя υ-го типа:

 

y_v^υ+x_fμ^υ≤1 для заданных υ и (f, μ); (7)

 

- на размещение модулей на различных носителях:

(8)

- на размещение массивов на различных носителях:

(9)

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

для заданного υ (10)

для заданного υ. (11)

2) Рассмотрим постановку и решение задачи выбора оптимальных методов организации массивов и модулей во внешней памяти, минимизирующих: 1) общее время обработки данных; 2) время решения одной из задач управления.

В первом случае критерий имеет вид:

(12)

Во втором – зафиксировав некоторое i:

(13)

В этих задачах кроме ограничений (5) – (11) учитывается дополнительное ограничение на суммарные затраты П на создание и эксплуатацию АСУ:

С_к+С_э^обм≤П (14), где С_к и С_э^обм определяются формулами (1) и (3).

Сформулированные задачи являются задачами целочисленного линейного программирования с булевыми переменными.

3.7.4. Задача определения оптимальной величины блока данных

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

- система модулей программного обеспечения;

- множества информационных массивов и их связей с системой модулей;

- способы и характеристики размещения массивов и программных модулей на устройствах внешней памяти.

Введем необходимые переменные и обозначения:

L_fυ – число записей f-го массива, размещенного на υ-м типе запоминающего устройства;

M=║m_vf║, v=1,..,V ; f=1,..,F – матрица связи массивов с модулями системы:

2, если f-й массив считывается и записывается v-м модулем,

m_vf= 1, если f-й массив только считывается v-м модулем,

0, если f-й массив не используется v-м модулем;

X_fυ – целочисленная переменная, определяющая число записей в блоке при считывании и записи в f-й массив, размещенный на υ-м типе запоминающего устройства;

Требуется выбрать множество переменных {x_fυ} таким образом, чтобы минимизировать общее число обращений к внешней памяти с учетом технологических ограничений. Эта задача формулируется следующим образом:

(15)

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

- на объем оперативной памяти D_v, доступной для данного v-го модуля:

(16)

- на допустимый минимальный d_υ и максимальный объема блока, размещенного в υ-м типе запоминающего устройства:

d_υ ≤ x_fυ ≤ , f=1,..,F ; υ=1,..,υ₀ (17)

- на целочисленность величины блока:

x_fυ ≥ 1, где x_fυ – целое , f=1,..,F ; υ=1,..,υ₀ (18)

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