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

Для уменьшения СОП следует так изменить МЦП, чтобы уменьшилось число ЛСП  и число путей S. Этого можно добиться, создавая независимые или условно-независимые фрагменты с заменой нескольких ЛСП, определяющих маршруты фрагмента, на одну ЛСП с образованием множественного оператора выбора. Решение данной задачи обеспечивается типовой реализацией МЦП, рассматриваемой ниже.  
 

8. Реализация модулей  циклических программ  С-автоматами 

В качестве типовой реализации МЦП с ЛСП  предлагается использовать модель С-автомата [6], ориентированную на программную  реализацию. Применение моделей конечных автоматов в программировании не ново (например, [7]). В частности R-технология [8] использует модель автоматов Мили, а технология программирования алгоритмов логического управления [9] использует модель автоматов Мура. Программы различного профиля, в том числе и логического управления, требуют, в общем случае, объединения указанных моделей в одну, то есть использовать С-автомат [10].

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

Алгоритм  МЦП задается графом переходов С-автомата , пример которого изображен на рис. 8. Граф содержит три вершины, отмеченные внутри прямоугольников, им соответствующих, дробными отметками. В числителе указан идентификатор состояния (символы a,b,c), который может быть либо целым произвольным числом либо произвольным символом. В знаменателе указан идентификатор оператора (Za,Zb,Zc), обязательно выполняющегося в данном состоянии. У вершины может быть петля, также отмеченная дробъю, в числителе которой указано условие, например Xa, а в знаменателе - идентификатор оператора, соответственно Ya, выполняющегося, если условие Xa = 1 (без перехода в другое состояние). Вершины связаны дугами, помеченные аналогично, например, дуга из состояния “a” в состояние “b” отмечена дробью “Xab/Yab”, где Yab - оператор, выполняемый при наличии условия Xab, и после реализации Yab новым состоянием автомата становится “b”. Условия, помечающие дуги, исходящие из одной вершины, включая петлю, должны быть попарно ортогональны.

Рис.8. Граф переходов С-автомата.

Практика  программирования показывает, что, в  общем случае, переход из одного состояния, например из “а”, в другое состояние, например в “с”, может осуществляться с реализацией не одного (Yac), а нескольких операторов, следующих в соответствии с выполнением ряда условий. Например, по условию Xac1 реализуется оператор Yac1, и выполняется переход из “а” в “с”; по условию Xac2 реализуется оператор Yac2, и выполняется такой же переход. Ортогональных условий вида Xack одинакового перехода из состояния “а” в состояние “с” с реализацией соответствующих операторов вида Yack может быть несколько (k = 1,2,...,Lac). Таким образом граф С-автомата, в общем случае, является мультиграфом.

9. Типовая структура  модуля, реализующего  С-автомат 

Типовая структура МЦП, реализующего С-автомат (согласно рис.8) представлена на рис.9, где используется оператор множественного выбора [11] для определения состояния Т автомата. При этом образуются три похожих условно-независимых фрагмента, первый из которых включает компоненты (Za, Xa, Ya, Xab, Yab, Xac, Yac). Этот фрагмент, в свою очередь, включает снизу-зависимый фрагмент Za. Из этого следует достаточно простой расчет числа условных путей в МЦП:

S = D(Za) * [E(Xa) * D(Ya) + F(Xa) * E(Xab) * D(Yab) +

+ F(Xa) * F(Xab) * E(Xac) * D(Yac) + F(Xa) * F(Xab) * F(Xac)] +

+ D(Zb) * [E(Xb) * D(Yb) + F(Xb) * E(Xba) * D(Yba) +

+ F(Xb) * F(Xba) * E(Xbc) * D(Ybc) + F(Xb) * F(Xba) * F(Xbc)] +

+ D(Zc) * [E(Xc) * D(Yc) + F(Xc) * E(Xca) * D(Yca) +

+ F(Xc) * F(Xca) * E(Xcb) * D(Ycb) + F(Xc) * F(Xca) * F(Xcb)].  

Здесь обозначены: D(Za) - число путей во фрагменте Za, E(Xa) - число единичных путей в ЛБГ, реализующем логическое условие Xa, F(Xa) - число нулевых путей в этом ЛБГ.

Рис.9. Структура  МЦП, реализующего С-автомат 

Если  фрагменты Za,Ya, Yab, Yac и подобные им не включают в себя независимых фрагментов, то число условных путей совпадает с числом реальных путей.

Если  ЛСП Т (номер или символ состояния  С-автомата) является единственной ЛСП  в этом МЦП, то СОП вычисляется  тривиально: просто складываются число  дуг и петель с числом вершин графа  переходов.

В общем случае, операторы Z и Y могут быть составными и/или включающими обращения к подпрограммам, то есть любыми допустимыми в языке программирования операторами.  

10. Оптимизация структуры  модуля, реализующего  С-автомат 

Если  логические условия X содержат как операции И так и операции ИЛИ, то они подлежат оптимизации по числу путей. При этом для каждого условия ищется такая перестановка его членов, которая дает наименьшее значение числа путей, согласно методу [12]. В результате оптимизации уменьшается число как единичных так и нулевых путей в ЛБГ, реализующем условие X. Аналогично оптимизируются логические условия, содержащиеся в операторах Z, Y. После оптимизации общее число путей в МЦП должно уменьшиться.

Другой  оптимизацией является повышение быстродействия МЦП. Самой простой оптимизацией является переразмещение условно-независимых фрагментов, начинающихся с операторов Z. Для этого определяются вероятности p(Za) , p(Zb), p(Zc) пребывания МЦП в состояниях “a”, “b”, “c” соответственно. Затем условно-независимые фрагменты размещаются в операторе множественного выбора согласно убыванию соответствующих им вероятностей p(Z).

Более сложной является оптимизация по быстродействию путем перестановок условий Xa, Xab, Xac с соответствующими фрагментами Ya, (Yab,”T=b”) и так далее. Для выполнения такой оптимизации полагаем, что задано исходное логическое выражение вида “Xa || Xab || Xac”. В данном выражении следует выполнить оптимизирующую перестановку членов согласно методу [13]. После этого указанные условия с соответствующими фрагментами переставляются местами согласно оптимальной перестановке выше приведенного логического выражения. Если критерий быстродействия является доминирующим для программы, то оптимальные перестановки по [13] следует получить как для каждого из логических выражений Xa, Xab, Xac так и для логических выражений, входящих в операторы Z и Y.  

11. Табличная реализация  С-автомата 

В случае, когда условия Xa, Xab, Xac представляют собой выражения вида “V == v1”, “V == v2”, “V == v3”, соответственно, где V - переменная, обозначающая, например, символ с клавиатуры или сообщение оконной функции приложения для операционной системы Windows [14], а v1, v2, v3 - значения переменной V, то состояние после перехода можно вычислить, используя табличный метод [2,11]. При табличной реализации существенно уменьшается число путей в МЦП.

Если, кроме  того, операторы Z и Y представить в  виде подпрограмм, то предлагаемая ниже табличная реализация является наиболее эффективной.

Пусть a = 0, b = 1, c = 2, Xa: “V == 0”, Xab: “V == 1”, Xac: “V == 2”, Xb: “V == 3” и так далее. Составим по графу переходов (рис.8) таблицу переходов и сопоставим ей соответствующий программный двухмерный массив МП (рис.10), строки которого соответствуют переменной V, а столбцы - переменной состояния Т, элементами массива являются номера состояний после перехода. Составим также таблицу 2 выходов Мили и сопоставим ей двухмерный массив ММ (рис.10), строки которого соответствуют переменной V, а столбцы - переменной Т. Если строки МП (ММ) имеют одинаковое значение V, то они склеиваются. Составим вектор ВВ выходов Мура с элементами {Za, Zb, Zc}.

Рис.10. Массивы МП и ММ.  

На основании  изложенного структура МЦП (за исключением  инициализации Т = 0 и массивов ММ, МП, ВВ) принимает вид:

Преобразовать входное сообщение с помощью оператора множественного выбора в значение переменной V;

Выполнить подпрограмму ВВ[T];

Выполнить подпрограмму MM[V][T];

T = МП[V][T].

Конец.

Проще по структуре МЦП трудно представить. При этом S = R = P = 9 (по первой операции).  
 
 
 
 
 
 
 
 
 
 
 
 
 

Список  литературы  

1. Липаев  В.В. Качество программного обеспечения. - М.: Финансы и статистика, 2003 – 200с.
2. Майерс Г. Надежность программного обеспечения. - М.: Мир, 2000 – 130с.
3. Кузнецов Б.П. Структурирование бинарных программ - Сер. - 2003, № 29, с. 27 - 35.
4. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. 1. Синтез и анализ. - Техническая кибернетика - 2004, № 5, с.132 - 142.
5. Кузнецов Б.П., Шалыто А.А. Система преобразований некоторых форм представления булевых функций. - А и Т, 2005, № 11, с. 120 - 127.
6. Баранов С.И. Синтез микропрограммных автоматов. - Л.: Энергия, 2009-220с
7. Байцер Б. Архитектура вычислительных комплексов. Том 1. - М.: Мир, 2009-250с.
8. Вельбицкий И.В. и др. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6. - М.: Статистика, 2000 – 200с.
9. Шалыто А.А. и др. Алгоритмизация и программирование задач логического управления техническими средствами. - С.-Пб.:Моринтех, 2006- 260с.
10. Кузнецов Б.П. Стандартная реализация управляющих программ. - Судостроительная промышленность. Сер. Системы автоматизации проектирования, производства и управления. 2006, вып. 1, с.51 - 55.
11. Джамп Д. AutoCAD. Программирование. - М.: Радио и связь, 2002.
12. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. III. Оптимизация числа и суммарной длины путей. - Теория и системы управления, 2005, № 5, с. 214 -223.
13. Кузнецов Б.П. Длительность вычислений на линейных бинарных графах. - А и Т, 2004, № 9, с. 166 - 172.
14. Петзолд Ч. Программирование для Windows 95. Том I. - СПб.: BHV - Санкт-Петербург, 2007.