Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.08.2024
Просмотров: 46
Скачиваний: 0
Тогда согласно (5-2) и (5-3) имеем
іѳі = |
Ѳ/ (Ж (/ - 1) - Ж (/)); |
|
Ui = |
П) (Ж (/ — 1) — Ж (/')). |
(5-5) |
Следовательно согласно (5-1) и (5-5) имеем / V
Т (А (п, s, m)) = log2 2 |
П |
(О X |
\/ = /о |
|
|
IX Ѳ/яНМ ( 7 - 1 ) - Ж |
(/))>). |
(5-6) |
Если предположить, что «ветвистость» вычислительного процесса по ярусам одинакова и аппроксимировать функции
<2ѳ (/), Q* (/) |
и М (/) |
прямыми, то |
|
|
||
Т (Л (п, s, |
т)) Ä |
log, (8Ѵ0Ѳ.8В-^ (С) X |
||||
|
|
V |
(Ж (7 - |
1) - |
Ж(7))3 |
|
|
X Ѳ-я. У |
|||||
Очевидно, |
|
У * / о |
|
|
|
|
|
|
|
|
|
|
|
/W o |
|
|
|
|
|
|
|
_ |
(Я + |
S + |
logs (S + m))a |
||
|
|
|
|
i1 |
|
I |
|
|
|
|
|
|
|
где р —число ярусов |
|
|
|
|
|
|
М (j0) = |
log, ((s + |
OT)-2rt+5) = |
a + |
s + loga (s + m)\ |
||
Ж (7V) = 0.
Тогда
T (A (n, s, m ))^ lo g 3^ v Se .6 ,.^ (C ).0 .n .
(5-7)
Формулы (5-6), (5-7) выражают связь трудоемкости реше ния задачи синтеза автомата реализующего оператор A(?2,s, т) с информационными характеристиками языков, применя емых при синтезе, числом переменных, критерием синтеза С и числом шагов процесса.
98
В качестве критерия На ограниченность вычислительных средств, естественно, взять
Т [А(7і, s, пг)) < Тдоп (А (п, s, m)), |
(5-8) |
Удоп —допустимая трудоемкость решения задачи синтеза.
Из анализа формул (5-6) -г-(5-8) замечаем, что для выпол нения (5-8) можем варьировать в основном только Ѳ и я, т. е. проводить синтез на языках с малыми Ѳ и я характеристика ми, так как остальные параметры являются заданными. Отсю да возникает интересная задача поиска языка, обладающего наряду с такими свойствами как полнота, непротиворечи вость, хорошими и информационными свойствами (малая ве личина Ѳ, я), благодаря которым размещение информации о функционировании автомата потребует наименьшего объема памяти при допустимом усложнении алгоритма исследова ния, что особенно важно при использовании ЦВМ при ре шении задачи синтеза.
При больших числах переменных п, s, пг естественным и практическим единственным решением задачи синтеза логи ческих структур является решение с помощью ЦВМ, отсюда чрезвычайная актуальность поставленной задачи, т. е. поиск языка с малыми Ѳ, я и особенно с малой величиной я, харак теризующей компактность представления оператора на этом языке, так как если машинное время решения задачи прак тически допускает значительные увеличения, то объем памя ти ЦВМ эффективно можно увеличивать только в ограни ченных пределах.
Представление автоматного оператора А (?i;s,m ) на су ществующих двоичных одновходовых и двухвходовых матри цах при большом числе переменных становится некомпакт ным.
Нетрудно подсчитать, что я-характеристика наиболее ком пактных двоичных двухвходовых матриц при представлении
автоматного оператора А |
(п, s пг) равна |
Я = |
(S - f in)- 2"+s |
|
п S ’ |
при представлении одной булевой функции [ (х\, хч, ... хп)
я — —
п
Следовательно, я-характеристика растет с ростом числа переменных как показательная функция.
7* |
99 |
Более компактным языком является язык частотных мат риц отношений, я-характеристика которого растет как сте пенная функция.
Наряду с компактностью представления А (п, s, т) на языке частотных матриц отношений, предлагаемый язык имеет следующие преимущества перед существующими язы ками структурного этапа:
а) арифметический характер вычислений при синтезе структур (на данном языке операции не с двоичными векто рами, а с числами), что позволяет наиболее эффективно ис пользовать возможности существующих ЦВМ при автомати зации синтеза структур;
б) возможность не работать со словами переменной дли ны (при числе переменных, превышающих длину машинной ячейки);
в) практическая независимость объема памяти, необходи мого для представления автоматного оператора, от числа обобщенных состояний \XZ+Z~Y) синтезируемого автомата.
§ 5-2. Программа синтеза булевых ясг-мультиструктур
В качестве примера организации вычислительного про цесса при синтезе автоматов рассмотрим синтез булевых ясг-мультиструктур, представляющих суперпозицию булевых
мультиструктур типа я и сг, и в которых веса |
и хі являют |
ся идентификаторами вершин синтезируемого графа. Син тез ведем на языке частотных матриц отношений.
Блок-схема программы имеет следующий вид [10]:
1.Блок 1 (Q -*-F)\ перевод матрицы инцидентности Q модели, в частотную матрицу отношений F (Q -*■ F).
2.Блок 2 (Рі): выделение подструктур типа G*. Сверты вание построенных подструктур.
3.Блок 3 (Р2): выделение подструктур типа Ga. Сверты вание построенных подструктур.
4.Условие 1 (Уі): была ли найдена хотя бы одна под структура G* при предыдущем выполнении Б 2?
Если G* была найдена, то переход к Р2.
Если G* |
не была найдена, то переход к пункту 5. |
5. Конец. |
_ _ |
100
Запишем работу блоков Q->-F, Р1 и Р2 на языке АЛГОЛ-60
Begin integer i, j, in, n, M, N, r, s, m l, nl, a, |
q, P |
||||
|
integer array |
a [1 |
: N\ 1 : M], f [1 : M; |
1 : M ], k [1 : M] * |
|
Q |
F: begin for m: = 1 |
step 1 until M do |
|
||
|
begin for n : = |
in step 1 |
until M do |
|
|
|
begin f [in, ft] |
: = 0-0; |
|
|
|
|
for |
t: = 1 step 1 |
until Ns do |
|
|
|
|
a [i, in] = 1 |
Д a \i, n] = 1 |
then |
|
|
f |
[m, |
n] : = / [m, n] + l |
■ ■ |
|
|
end |
|
|
|
|
|
end |
|
|
|
■ |
|
end |
|
|
|
|
Здесь M — число столбцов матрицы Q, a N — число ее строк.
Перед началом работы алгоритма каждой букве сопостав ляется коэффициент, равный 1. Далее, при свертывании G” в вершину а коэффициент этой дуги приравнивается произ ведению коэффициентов вершин графа G*; при выделении G° — сумме коэффициентов вершин, образующих G”. При этом коэффициент вершины а несет информацию о количе стве путей, проходящих через эту а. При свертывании выде ленного подграфа коэффициенты его вершин приравнивают ся нулю, и таким образом исключаются из дальнейшего рас смотрения.
P I: |
begin coef: = 1; |
for г: = 1 |
step 1 |
until M |
do; |
|
|||||
|
k[r]:=coef; |
c: — 585/4,096**; |
a: = 0 ; |
e: = 0; |
begin |
||||||
|
for k: = 1 step 1 until (M — 1) |
do begin |
begin |
in: = k; |
|||||||
|
1 1 : = k; |
s: = |
k; |
r: — k; |
if |
k [/•] = |
0 then go to end else |
||||
|
p: = f[in, n] |
end; cycle |
n: |
begin |
n: =>n |
+ 1 ; |
tn: = n; |
||||
|
r: = n; |
if k[r] = 0 then |
go |
to M else |
R: = |
|
|||||
|
if p — R then go to^ L else go to_M end; |
|
|
|
|||||||
L: |
begin |
in: = |
s; |
T :— f[m, |
ft]; |
if |
T = p |
then begin ne- |
|||
*Описание составлено для всех трех блоков.
**Это означает, что С принимает значение указателя типа подграфа. Для G* это число равно 111100... 0.
101
