ПРЕОБРАЗОВАНИЕ ДАННЫХ

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

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

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

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

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

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

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

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

. ,

где l_ij=1 - если информационный элемент D_j используется при выполнении операции A_i ;

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

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

i=1,...,m; j=1,...,n.

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

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

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

Граф - схема алгоритма представляет собой древовидный граф, узлами которого является операции над данными, а дугами - связи (отношения) между операциями в алгоритме. Операции в алгоритме выполнятся последовательно-параллельно, так что в корне графа расположена головная (начальная) операция A₀, от которой после ее выполнения происходит переход к операции A₁ или А₂, затем к А₃, А₄,..., А_m.(рис.3.14).

Рис. 3.14 Граф-схема алгоритма

Приведенный граф можно разместить, написав возле дуг число обращении r_ij от операции А_i к операции А_j (например, от А₁ к А₃) в процессе выполнения алгоритма. Число обращений в детерминированных алгоритмах r_ij ³1, для вероятностного алгоритма число r_ij <1,так как оно определяет вероятность обращения операции А_i к операции А_j. При анализе алгоритмов решения вычислительных задач, можно выделить общие совокупности операций (пересечения граф-схем). На рис. 3.15 алгоритмы P₁ и P₂ имеют три общие операции, составляющие подмножество операций, входящих одновременно и в множество операций алгоритма P₁, и в множество операций алгоритма P₂ (заштрихованная часть рис.3.15)

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

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

Рис. 3.16 Фрагмент вычислительного графа программной системы

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

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

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