Фрагменты модулей циклических программ

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

В [3] предложен метод независимых фрагментов для синтеза структуры модулей, реализующих таблицы решений. При этом независимым считается такой фрагмент, который можно вставить в любом месте последовательности фрагментов модуля. Независимость местоположения такого фрагмента обусловлена тем, что анализируемые в нем данные не формируются в указанной последовательности фрагментов, а формируемые в независимом фрагменте данные не анализируются в данной последовательности фрагментов. Поэтому независимые фрагменты могут выполняться параллельно (псевдопараллельно). На рис. 2 показаны возможные варианты реализации модуля с двумя независимыми фрагментами. В вариантах “а” и “б” фрагменты переставлены местами без искажения существа программы; в варианте “в” фрагменты реализуются параллельно.

Рис.2. Варианты реализации модуля с независимыми фрагментами:

а) и б) - последовательная реализация,

в) - параллельная реализация: двойная горизонтальная линия обозначает распараллеливание программы, жирная горизонтальная черта обозначает завершение параллельных процессов.

Зависимым фрагментом является такой, местоположение которого зависит от местоположения другого (других) фрагмента в модуле. Будем различать сверху- и снизу зависимые фрагменты. Сверху-зависимый фрагмент должен быть расположен всегда ниже некоторого фрагмента, в котором формируются переменные, используемые в данном (зависимом) фрагменте. Снизу-зависимый фрагмент должен размещаться всегда выше фрагмента, в котором используются переменные, формируемые в данном фрагменте. Два зависимых фрагмента, один из которых является сверху зависимым от второго, а второй снизу зависимым от первого, будем называть взаимно зависимыми фрагментами. Их нельзя менять местами и нельзя реализовывать параллельно. На рис. 3 приведен пример модуля с взаимно зависимыми фрагментами. Между взаимно зависимыми фрагментами могут находиться другие, зависимые или не зависимые от них. Рис.3. Модуль с зависимыми фрагментами.

Фиксированным будем называть зависимый фрагмент, местоположение которого в модуле строго определено. Например, в модуле распознавания символа, введенного с клавиатуры, первым должен быть снизу зависимый фрагмент непосредственно ввода символа. Операторы “начало” и “конец” модуля есть фиксированные фрагменты.

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

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

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