Разрабатываемых на проектных стадиях создания АС

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

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

Пусть в результате диагностического анализа проектируемой АС для заданного комплекса задач управления определено множество программных модулей 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-й массив

_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 модуля, связанные с 6 информационными элементами. Эта связь и частота использования модулей в процессе функционирования АСУ приведены в таблице 1.

Таблица 1

Номер модуля	Информационные элементы, считываемые модулями из БД	Информационные элементы, записываемые модулями в БД	Средняя частота использования модуля в единицу времени
	2, 3, 4, 5	1, 4
	1, 2, 6
	4, 5, 6

Длины соответствующих информационных элементов в килобайтах приведены в таблице 2.

Таблица 2

Информационный элемент
Длина элемента, (КБ)

Представим исходные данные в виде направленного двудольного графа , где - множество модулей системы, - множество информационных элементов, - матрица смежности графа, показывающая связи модулей с информационными элементами и имеющая следующий вид (см. табл. 1):

.

Граф изображен на рис. 1, где - модули; - информационные элементы; - массивы. Дуга направлена от модуля к элементу, если этот элемент записывается модулем, и от элемента к модулю, если элемент считывается модулем.

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

Среднее число обменов системы программных модулей с внешней памятью (базой данных) при размещении информационных элементов по массивам так, как показано на рис. 1, равно 100. Если, однако, в массив поместить элементы , в массив - элементы , а в массив - элемент , то среднее число обменов сократится до 90. Таким образом, имеет место улучшение ранее составленного варианта размещения элементов по массивам.

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

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

Очевидно, что число слоев такого дерева равно , а число вершин в слое (- номер информационного элемента) рано .

После построения -го слоя дерева вариантов для каждого из них проверяются условия (4), (5) и (6) и среди им удовлетворяющих выбирается вариант с минимальным значением функционала (3).

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

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

. (7)

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

. (8)

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

, (9)

где - приращение оценки в вершине дерева ветвления.

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

. (10)

Величины и в выражении (10) определяются по следующим формулам:

(11)

(12)

В выражениях (11) и (12) величина - это число образуемых массивов в й вершине дерева ветвления, а и - булевы переменные, определяемые по формулам (1) и (2) соответственно при условии, что информационные элементы распределены по информационным массивам согласно й вершине дерева ветвления.

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

1. Вводят исходные данные задачи в виде массивов и матриц и .

2. По формулам (7) и (8) вычисляют верхнюю и нижнюю границы и.

3. Распределяют информационный элемент в информационный массив (строят первый слой дерева вариантов).

4. Полагая , помещают элемент последовательно в информационный массив с номером (строят второй слой дерева вариантов).

5. Для каждой вершины го слоя (варианта распределения рассматриваемых информационных элементов по информационным массивам) последовательно проверяют выполнимость условий (4) и (6), полагая , где - номер рассматриваемой вершины. Для тех вершин, у которых условия (4) и (6) не выполняются, полагают , для остальных вершин значения вычисляют по формулам (9) – (12).

6. Находят вершину рассматриваемого го слоя с номером таким, что имеет место равенство , где - множество номеров построенных вершин этого слоя.

7. Проверяют, все ли слои дерева вариантов построены. Если да, то выполняют п. 9, в противном случае выполняют пункт 8.

8. Запоминают номер вершины рассматриваемого го слоя и строят вершины -го слоя, взяв в качестве исходной вершину с номером . После построения всех вершин -го слоя переходят к п. 5.

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

Дерево вариантов применительно к рассмотренной выше задаче распределения 6 информационных элементов по информационным массивам приведены на рис. 2.

Точное решение этой задачи состоит в следующем: 1-й, 2-й и 3-й информационные элементы помещают в 1-й информационный массив; 4-й и 5-й информационные элементы помещают во 2-й информационный массив; 6-й информационный элемент составляет 3-й информационный массив. Общее время считывания, поиска и передачи требуемых данных при этом равно 90.

Лекция 17.

3.9.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).

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

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

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

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

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

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

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)

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

Лекция 24

ГЛАВА 4. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ДОКУМЕНТОВ,

Дата добавления: 2014-01-07