Способы построения циклических вычислительных процессов (стр. 2 из 4)

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

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

3. Число маршрутов в модулях циклических программ

Рассмотрим влияние зависимости фрагментов на критерий сложности модулей по Липаеву, то есть на число маршрутов в модулях. В дальнейшем под термином “маршрут” (“путь”) будем подразумевать так называемые условные (объясняется ниже) маршруты (пути).

Обозначим S - общее число маршрутов (путей) в модуле, а Sn - число путей в n-ом фрагменте этого модуля.

Пусть модуль содержит только зависимые фрагменты (рис. 3). Управляющий граф [1] этого модуля изображен на рис. 4,а, из которого следует, что фрагмент 1 содержит 5 маршрутов, а фрагмент 2 - 3 маршрута. Так как каждый маршрут фрагмента 2 зависит от маршрутов фрагмента 1, то общее число маршрутов в данном модуле равно произведению чисел маршрутов каждого из фрагментов, то есть S = S1 * S2.

Рис.4. Расчетные маршрутные схемы (РМС):

а) управляющий граф модуля по рис.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” показывает три нулевых и пять единичных путей.