Опишите модели преобразования данных.

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

· по критерию минимизации времени обработки (в режиме реального времени)

· по критерию минимизации объемов затрачиваемых вычислительных ресурсов (в мультипрограммном режиме).

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

Задачей управления процедурой преобразованияданных является,

· минимизация информационных потоков между памятью ЭВМ и операциями (процессором),

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

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

Граф преобразования данных

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

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

На пересечении строки и столбца ставится 1, если операция и информационный элемент связаны. Другими словами, получим матрицу L:

— если информационный элемент используется при выполнении операции A;

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

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

Данная задача может быть сведена к задаче линейного программирования и решена с использованием стандартных приклад­ных программ.

Нарисуйте и объясните примеры графов алгоритмов и вычислительного графа программной системы.

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

Граф алгоритма представляет собой древовидный граф, узла­ми которого являются операции над данными, а дугами — связи (отношения) между операциями в алгоритме. В корне графа рас­положена головная (начальная) операция а0, от которой после ее выполнения происходит переход к операции А1 или a2 , затем к А3,А 4, ., Ат

Граф алгоритма

Приведенный граф можно разметить, написав возле дуг чис­ло обращений rij от операции Аi, к операции aj (например, от А1 к A3) в процессе выполнения алгоритма. Для детерминирован­ных алгоритмов число обращений rij ≥1, для вероятностного ал­горитма число rij < 1, так как оно определяет вероятность обра­щения операции Аi, к операции Аj.

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

Рис.Объединение графов алгоритмов

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

Фрагмент вычислительного гра­фа программной системы, головным является вычислительный модуль М0. Ему подчинены модули, находящиеся на нижележа­щих уровнях. На самом нижнем уровне расположены модули, выполняющие элементарные типовые операции.

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

Изложенный подход реализуется методом структурного програм­мирования, применяемым при создании программных комплексов.

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

В чем состоит принцип параллельной обработки данных?

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