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

Рис.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.