4.3. организация планирования обработки вычислительных задач

4.4. преобразование данных

 

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

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

ЭВМ и начинает исполняться после предварительной обработки

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

и изменение структур и элементов данных и т.п.) в количестве

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

последовательным набором машинных команд (машинной программой).

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

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

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

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

4-1909

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

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

На пересечении строки и столбца ставится 1, если операция и

информационный связаны. Другими словами, получим

матрицу L:

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

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

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

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

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

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

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

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

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

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