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

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

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

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

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

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

4-1909

 

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

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

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

матрицу L:

О, Р₂ - О,

где 1у — 1 — если информационный элемент Dj используется при выпол­нении операции А:!,/ - 0 -- противном случае;

При таком представлении задача состоит в разбиении множе­ства операций преобразования данных матрицы L на непересека-

98

 

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

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

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

Граф алгоритма представляет собой древовидный граф, узла­ми которого являются операции над данными, а дугами — связи (отношения) между операциями в алгоритме. В корне графа рас­положена головная (начальная) операция Ао, ОТ которой после ее выполнения происходит переход к операции А\ или Л2 , затем к Аз, А4,..., Л_т(рис. 4.5).

 

 

к Ат,) в процессе выполнения алгоритма. Для детерминирован­ных алгоритмов число обращений г,у > 1, для вероятностного ал­горитма число г,у <1, так как оно определяет вероятность обра­щения операции к операции Л/. При анализе алгоритмов решения вычислительных задач можно выделить общие совокуп­ности операций (пересечения графов). На рис. 4.6 алгоритмы Р\ и Р2 имеют три общие операции, составляющие подмножество операций, входящих одновременно и в множество операций ал­горитма Р\, и в множество операций алгоритма Рг (заштрихо­ванная часть рис. 4.6).

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

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

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

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