Внешней памятью ЭВМ (базой данных)

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

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

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

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

Кроме того, известно количество информационных массивов F, в которых размещены информационные элементы, но в каких массивах и в каком количестве их находится в том или ином массиве неизвестно.

Известными являются также следующие данные:

- А={а_j; j=1,.., m} – множество последовательно выполняемых процедур в проектируемой системе обработки данных;

         - R={r_ℓ ; ℓ =1,.., L} – множество информационных элементов, обрабатываемых процедурами множества А;

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

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

– среднее время считывания i-го модуля из внешней памяти в оперативную память ЭВМ, ;

       - t_f^с – среднее время считывания f-го массива из внешней памяти в оперативную память ЭВМ, ;

       - t_f^з – среднее время записи результатов в f-й массив, находящийся в в оперативной памяти ЭВМ, .

 

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

 

     1, если j-я по порядку выполнения процедура включается в состав i-го модуля;  

=

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

 

i=1,.., V; V- возможное число модулей;

           1, если ℓ -й информационный элемент включается в f-й массив;

=

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

 

f=1,.., F; F≤ L;

 

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

 

 

 

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

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

 

 

 

 

Другими словами, ( ) = 1, если массив с номером f содержит хотя бы один информационный элемент, необходимый для выполнения хотя бы одной процедуры из модуля с номером i.

Таким образом, переменные y_iℓ ^с(з) и z_if^с(з) служат для формализации взаимосвязи системы разрабатываемых модулей с отдельными информационными элементами и массивами при считывании и записи в процессе обмена с внешней памятью ЭВМ.

 Задачу разбиения ИЛМ АСОИУ на функциональные модули с минимальным временем обмена с внешней памятью ЭВМ (базой данных) можно теперь формализовать формулируется следующим образом.

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

 

В этом выражении 1-е слагаемое – условие обработки информации всеми процедурами модуля, причем одновременно 2 модуля не обрабатываются и учет времени считывания модулей, причем процедуры выполняется последовательно; 2-е и 3-е слагаемые – учет времени считывания (записи) информационных массивов.

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

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

- на общее число процедур в составе каждого модуля:

где - допустимое число процедур в i-ом модуле;

- на число информационных элементов, обрабатываемых процедурами каждого модуля:

где - максимальное допустимое число информационных элементов обрабатываемых i-ым модулем;

- на сложность интерфейса между всеми модулями системы обработки данных:

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

- на сложность интерфейса между отдельными модулями системы обработки данных:

для заданных i и i′,

где - максимальное число общих переменных (информационных элементов), обрабатываемых модулями i и i′;

- на однократность включения процедур в программные модули:

- на включениеотдельных процедур в состав одного модуля:

x_ij+x_ij′ ≤ 1, для заданных j и j′, i=1,.., V;

- на передачу управления из модуля до завершения обработки информации всеми процедурами модуля:

_- на дублирование информационных элементов в массивах:

где k - допустимая степень дублирования информационных элементов в массивах системы;

- на размер записи каждого массива:

где - максимально допустимое число информационных элементов в f-ом массиве.

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

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться: