Способы построения циклических вычислительных процессов

а) управляющий  граф модуля по рис.3,

б) РМС  этого модуля,

в) РМС  модуля по рис. 2,в.

Управляющий граф не очень удобен для рисования  и подсчета общего числа маршрутов  модулей, фрагменты которых содержат сравнительно большое число путей  каждый. Поэтому вместо управляющего графа предлагается более простая расчетная маршрутная схема (РМС) модуля (рис.4,б). В РМС прямоугольниками обозначены: оператор начала - “нач”, оператор конца - “кон”, фрагмент n - “fn”. В нижней части прямоугольника, обозначающего фрагмент, указано число путей в данном фрагменте; в нижней части прямоугольника,обозначающего начало модуля указана константа единица. Рядом с дугой, соединяющей два прямоугольника, указывается число маршрутов, образованных всеми фрагментами, размещенными последовательно от начала модуля до того фрагмента, в который входит рассматриваемая дуга. В нижней части прямоугольника,обозначающего конец модуля, указывается общее число путей в модуле. Фрагменты, имеющие единственный путь в РМС не включаются.

В общем  случае, общее число S путей последовательности из N зависимых фрагментов определяется следующим образом:

S = S1 * S2 * ... * SN, где знак “*” обозначает  операцию произведения.

Рассмотрим  теперь независимые фрагменты. Как  уже упоминалось, независимые фрагменты  могут быть реализованы параллельно. Любой маршрут независимого фрагмента не связан с другими фрагментами модуля, поэтому он анализируется автономно. На рис. 4,в показана РМС модуля с двумя независимыми фрагментами. Для модуля с независимыми фрагментами РМС выполняется в варианте параллельного соединения фрагментов даже, если модуль реализован с последовательным включением этих фрагментов. Числа, указанные в РМС на рис.4,в интерпретируются так же, как и на рис. 4,б. Дополнительно поясним: дуги, исходящие из двойной черты (распараллеливание процесса) отмечены тем же числом, что и заходящая в двойную черту дуга; дуга, исходящая из жирной горизонтальной черты, обозначающей конец распараллеливания, отмечается числом, равным сумме чисел, помечающих заходящие в эту черту дуги. Тем самым устанавливается следующий факт.: общее число S анализируемых путей модуля, содержащего только независимые фрагменты, определяется суммой вида S = S1 + S2 + ... + SN, где N - число независимых фрагментов. Однако, реальный путь в последовательной программе проходит через все фрагменты, невзирая на их независимость. Поэтому число R реальных путей равно числу путей S, вычисленному из той посылки, что независимых фрагментов в модуле нет.

Отметим, что пути в РМС с параллельным включением независимых фрагментов будем называть условными, а величину S - числом условных (по умолчанию) путей, в отличие от величины R - числа реальных путей в МЦП. При этом S < R.

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

На рис. 5,а представлен модуль из девяти фрагментов, последовательно размещенных в соответствии с текстом последовательно реализуемой подпрограммы. Через дробь после обозначения фрагмента указано число путей в нем. Отметим, что произвольная группа следующих подряд фрагментов так же является фрагментом, который будем обозначать перечислением в скобках обозначений составляющих группу фрагментов. Пусть, например, имеет место следующая зависимость фрагментов в модуле (рис. 5,а): фрагменты (f1,f2,f3) и (f4,f5,f6,f7,f8,f9) независимы относительно начала и конца, фрагмент f3 сверху зависим от f1 (f2), фрагменты f1 и f2 независимы относительно начала и фрагмента f3, фрагмент f5 сверху зависим от f4, фрагмент (f6,f7) сверху зависим от f5, фрагмент (f8,f9) сверху зависим от f6 (f7), фрагменты f6 и f7 независимы относительно f5 и (f8,f9), фрагменты f8 и f9 независимы относительно (f6,f7) и конца.

Рис.5. Модуль с зависимыми и относительно независимыми фрагментами (а) и его РМС (б).

На основании  изложенного получена РМС (рис. 5,б) и  расчитано общее число условных путей в модуле (рис. 5,а) S = 1545, в то время как реальное число путей

R = 10 * 5 * 7 * 4 * 6 * 2 * 3 * 5 * 7 = 1764000

Данное  число на три порядка (!) превосходит  ранее полученное.

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

Введем  для МЦП коэффициент Kn независимости: Кn = S / R. Он имеет пределы: верхний, равный единице, (все фрагменты зависимые) и нижний, равный отношению суммы  числа путей фрагментов к R (все фрагменты независимы).  
 

4. Число маршрутов  во фрагментах, содержащих  булевы операции 

Ранее рассмотренные в примерах фрагменты  содержали конструкции логического  или множественного выбора, в условных вершинах которых содержались элементарные логические условия без знаков булевых операций “И” и “ИЛИ”. Поэтому число путей фрагмента определялось визуально без дополнительных построений. Однако наличие знаков булевых операций в логических выражениях требует построения специальной схемы для расчета числа путей как для единичного значения выражения так и для нулевого. В качестве такой схемы предлагается использовать линейный бинарный граф [4] (ЛБГ). Построение ЛБГ и расчет числа путей, порождаемых логическим выражением с булевыми операциями, рассмотрим на следующем примере.

Пусть в условной вершине некоторого фрагмента  представлено сложное логическое выражение  вида

( Sin(a) == Cos(b) && (! c % 5 || d > 3) && (e <= exp(f) || func(g)) ).

Здесь указаны: операции сравнения (“==“, “>“, “<=“), деления по модулю (“%”), булевы операции (“!” - инверсия, “&&” - И, “||” - ИЛИ), функции синуса, косинуса, экспоненты и некоторой целочисленной функции (func). Введем понятие “атом” - это подформула, ограниченная слева и справа знаками булевых операций. В данном случае атомами являются следующие подформулы: Sin(a) == Cos(b), c % 5, d > 3, e <= exp(f), func(g).

Если  в формуле содержится знак инверсии перед заключенной в скобки булевой  операцией, то знак этой операции изменяется (И на ИЛИ и наоборот), а знак инверсии исключается перед данной подформулой и ставится перед каждым членом замененной операции. В данной формуле этого не требуется.

Для построения ЛБГ разместим атомы друг под  другом в порядке обхода всей формулы слева направо (рис. 6) и соединим их дугами, направленными вниз. Атомы образуют вершины ЛБГ, а дуги - связь между соседними вершинами. Вслед за последним (нижним) атомом разместим две вершины, соответствующие результатам вычисления формулы - единичному и нулевому; нижний атом соединим дугами с указанными новыми вершинами. Все ранее построенные дуги называются основными дугами ЛБГ. Теперь построим дуги, называемые переходами.  
 

Рис.6. ЛБГ  и расчет числа его нулевых и единичных путей.

Переходы  строятся по обе стороны от оси  ЛБГ, образуемой основными дугами между  вершинами - атомами. Переходы строятся начиная с вершины, предшествующей последнему атому (в нашем случае с вершины “e <= exp(f)”). Переход  строится на той стороне от оси, где расположена вершина “результат 1”, если в формуле справа от соответствующего атома стоит знак ИЛИ. В примере это переходы от атомов “e <= exp(f)” и “!c%5”.Переход строится на другой стороне от оси, если в формуле справа от атома стоит знак И. Это переходы от атомов “d > 3” и “Sin(a) == Cos(b)”. Переход направляется к расположенной на стороне его построения вершине “результат 1(0)”, если упомянутый знак ИЛИ (И) принадлежит внешней операции формулы. Это переходы от атомов “Sin(a) == Cos(b)” и “d > 3”. В противном случае переход направляется к ниже расположенной вершине, соответствующей атому, размещенному справа от закрывающей скобки, ограничивающей операцию,которой принадлежит упомянутый знак ИЛИ (И), а если такого атома нет - к вершине “результат”. Это переходы от атомов “! c % 5” и “e <= exp(f)”. Знак булевой операции отрицания на расчет числа путей не влияет, поэтому в построенном, следуя вышесказанному, ЛБГ он игнорируется (см. рис. 6). Формальное описание синтеза ЛБГ представлено в [5]. Теперь рассмотрим процесс подсчета числа единичных и нулевых путей в построенном ЛБГ. Будем использовать специальную метку, представляющую собой два числа, разделенную знаком дроби. При этом левое число будет обозначать число нулевых путей, а правое - единичных. Например, метка “3 / 5” показывает три нулевых и пять единичных путей.

Логично предположить, что расчет числа путей  надо начинать от начальной вершины. Но предлагается более простой алгоритм подсчета, начиная с вершин “результат”. Под вершиной “результат 0” поставим метку “1 / 0”, а под вершиной “результат 1” - метку “0 / 1”. На каждой дуге, заходящей в вершину “результат” поставим такую же соответствующую метку. Далее, для каждой вершины ЛБГ, начиная с последнего атома и следуя вверх, выполнить следующее. Сложить метки “a0 / a1” и “b0 / b1”, указанные на исходящих из данной вершины дугах, в результате чего получится метка “c0 / c1”, где c0 = a0 + b0, c1 = a1 + b1. Полученную метку поставить на каждой заходящей в данную вершину дуге. В результате над самой верхней вершиной ЛБГ получается метка “s0 / s1”, где s0 - число нулевых путей, то есть число путей, определяющих результат 0, а s1 - число единичных путей, определяющих результат 1.  
 

5. Число путей во  фрагментах, содержащих  циклические операторы

В структурированных  программах циклические операторы  могут быть сведены к двум типам  фрагментов: с проверкой условия  цикла до входа в тело цикла  и - после тела цикла (рис. 7). Число S путей  таких фрагментов определяется четырьмя компонентами: числом Sp путей пролога цикла (где устанавливаются начальные значения переменных, используемых в условии и в теле цикла), числом St тела цикла ( в котором включим счетчики и другие операторы приращений) и числами S1 и S0 единичных и нулевых путей, соответственно, условия (“усл” на рис.7) выполнения цикла.

Рис.7. Два  типа циклических операторов.

В первом случае (рис. 7,а) тело цикла может  не выполниться ни разу, при этом анализируется S = Sp * S1 путей. Если условие  выполнено хотя бы один раз, то анализируется S = Sp * S1 * St * S0 путей. По максимуму принимаем последнее выражение для определения числа путей в циклических операторах первого типа.

Во втором случае (рис. 7,б) тело цикла всегда выполняется  хотя бы один раз, даже, если условие  не выполняется. При этом анализируется S = Sp * St * S0 путей. Если же условие цикла выполнится хотя бы один раз, то число путей S = Sp * St * S0 * St * S1. С учетом того, что пути тела цикла анализируются только один раз, получим S = Sp * St * S0 * S1.  

Таким образом, для любого из двух представленных типов фрагментов с циклическими операторами число анализируемых путей определяется выражением S = Sp * St * S1 * S0.  

6. Условно-независимые  фрагменты 

Кроме циклических операторов фрагменты  могут быть образованы операторами ветвления. Такими операторами являются условные (двоичного выбора) и операторы множественного выбора. Пример фрагмента с оператором двоичного выбора показан на рис. 2 (“фрагмент 1”). а с множественным выбором - на рис.3 (“фрагмент 2”). Фрагменты операторов выбора включают вершину, в общем случае, с целочисленной переменной (в том числе операция сравнения есть булева переменная с двумя значениями), из этой вершины исходит по крайней мере две помеченые дуги, заходящие в вершины, соответствующие операторам нижнего уровня и являющиеся вложенными фрагментами, которые и будем называть условно-независимыми. Такое название объясняется тем, что с позиции расчета числа путей эти вложенные фрагменты не зависят друг от друга. Поэтому число путей во фрагменте с оператором двоичного выбора определяется так: вычисляются числа единичных и нулевых путей логического условия (при наличии булевых операций в нем), считается число путей в каждом из условно-независимых фрагменте, которое умножается на соответствующее число единичных (нулевых) путей, и полученные произведения складываются. Для операторов недвоичного выбора просто складываются числа путей условно-независимых фрагментов.  

7. Структурный объем  памяти модулей  циклических программ 

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

ЛСП усложняют  анализ структуры модуля, так как  при разборе очередного цикла  необходимо помнить значения этих переменных, полученные в предшествовавшем цикле. Поэтому такого критерия как число маршрутов уже недостаточно. Введем новый критерий структурной сложности для МЦП с памятью, названный структурным объемом памяти (СОП) модуля. Введем обозначения: m - число ЛСП, используемых в модуле, i - порядковый номер маршрута модуля, содержащего всего S маршрутов, ai - число операций присваивания (инициализации, модификации) ЛСП на i-ом маршруте. Значение СОП определяется выражением

где “max” - операция взятия максимума из двух переменных.

Здесь предполагается, что S вычислено по РСМ. Нижняя оценка СОП вычисляется в предположении, что каждой переменной (ЛСП) на одном маршруте присваивается не более одного нового значения: Pmin = m * S.