ВЫЯВЛЕНИЕ ИЗОМОРФНЫХ ВХОЖДЕНИЙ R-ВЫРАЖЕНИЙ ПРИ ПОСТРОЕНИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 004.384:004.272:004.414.2
Э. И. ВАТУТИН, И. В. ЗОТОВ, В. С. ТИТОВ
ВЫЯВЛЕНИЕ ИЗОМОРФНЫХ ВХОЖДЕНИЙ R-ВЫРАЖЕНИЙ ПРИ ПОСТРОЕНИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ
Представлен алгоритм выяснения отношения изоморфизма R-выражений (сечений параллельного алгоритма), основанный на ряде их особых свойств и ориентированный на аппаратную реализацию. Приведено описание устройства (акселератора) на его основе, позволяющего проводить проверку отношения изоморфизма за линейное время.
Ключевые слова: логический мультиконтроллер, синтез, параллельный алгоритм логического управления, разбиение, оптимизация, ориентированные деревья.
Реализация параллельных управляющих алгоритмов в базисе логических мультиконтроллеров (ЛМК) требует их декомпозиции на множество частных алгоритмов ограниченной сложности [1]. Получение оптимального набора частных алгоритмов (разбиения) — сложная комбинаторная задача. Качество ее решения существенно влияет на аппаратную сложность ЛМК и определяет, в конечном счете, время выполнения алгоритма. Один из наиболее эффективных путей решения данной задачи предлагает развиваемый авторами параллельнопоследовательный метод декомпозиции [2—8]. Как было показано в статье [9], он позволяет формировать наиболее близкие к оптимальным варианты разбиения с учетом основных структурных и технологических ограничений базиса ЛМК.
Один из ключевых этапов параллельно-последовательной декомпозиции — построение множества сечений, покрывающего все вершины исходного алгоритма. Формирование сечений осуществляется путем выполнения трудоемких операций подстановки над множеством так называемых R-выражений, описывающих алгоритм управления. Как показывают исследования, упрощение и ускорение этих операций возможно путем их сведения к действиям над деревьями, в частности, к проверке изоморфизма.
В настоящей статье предложен алгоритм определения изоморфных вхождений R-выражений, основанный на ряде их специфических свойств, не присущих графам или деревьям общего вида, и обеспечивающий проверку изоморфизма за полиномиальное время. (Как известно [10], для решения задачи распознавания изоморфизма графов общего вида до сих пор не только не придумано эффективного универсального алгоритма, но и не доказана ее принадлежность к классу P или NP [11].) Следует отметить, что рассматриваемый вид изоморфизма R-выражений определяется исходя из возможности проведения операции подстановки [1, 3, 4] и несколько отличается от „классического“ понятия изоморфизма [10], определяемого для графов, ввиду чего далее будем именовать его r-изоморфизмом.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
38 Э. И. Ватутин, И. В. Зотов, В. С. Титов
При практической реализации операций над R-выражениями удобным является их представление в виде деревьев, допускающее преобразование в табличный вид (рис. 1). Каж-
дый элемент дерева X, представленного совокупностью наборов листьев L1X , L2X , ..., LnXL( X ) ,
узлов T1X , T2X , ..., TnXT ( X ) и связей между ними, кодируется набором полей. С учетом ряда осо-
бенностей обработки наборы листьев и узлы дерева кодируются отдельно. Узлы дерева представлены полями:
1) типа узла (ТУ) — параллельный или альтернативный; 2) ссылки на предка (СП) — номер узла-предка; 3) номера соответствия (НС) — номер изоморфного эквивалента в соседнем дереве; 4) типа соответствия (ТС) — может принимать значения „0*“ — соответствие отсутствует, „10“ — неполное (частичное) соответствие, „11“ — полное соответствие.
a99⋅(a94|a95|a128|(a65⋅a66⋅a82⋅a83⋅(a55|a56|a112) ⋅(a59|a104|a111))) • T0
a99 L0
| T1
a94a95a128 L1
• T2
a65a66a82a83
L2 | T3 L3
a55a56a112
| T4 L4
a59a104a111
Наборы листьев
Узлы
Тип Ссылка на узла предка
T0 • T1 | T2 • T3 |
— T0 T1 T2
T4 |
T2
T5 …
— ...
— …
NLmax —
—
Текущее количество узлов (NТ)
5
Текущее количество
наборов листьев
(NL) 5
№
L0 L1 L2 L3 L4 L5 … NLmax
Множество Ссылка на
вершин предка
99 94, 95, 128
T0 T1
65, 66, 82, 83 T2
55, 56, 112
T3
59, 104, 111 —
T4 —
……
——
Рис. 1
Наборам листьев дерева при этом соответствуют поля множества вершин (МВ) — двоичный вектор с единичными битами в позициях, соответствующих номерам присутствующих в наборе вершин, а также поля СП, НС и ТС. Во избежание путаницы при обозначении одноименных полей, соответствующих узлам и наборам листьев, будем обозначать их с указанием принадлежности к элементам дерева (например, СП(у) и СП(нл)).
Краткое описание свойств R-выражений, гарантирующих наличие единственно возможного изоморфного эквивалента поддерева и позволяющих исключить из рассмотрения проверку соответствия типов узлов деревьев, приведено ниже (ввиду ограниченного объема статьи доказательства лемм и теорем не приведены).
Необходимое условие 1 отсутствия r-изоморфизма. Если в дереве A найдется набор ли-
стьев LiA , не находящийся в отношении эквивалентности, обозначаемом как
L1 [~] L2 ⇔ ( L1 = L2 ) ∨ ( L1 ⊂ L2 ) ∨ ( L2 ⊂ L1 ) ,
ни с одним набором листьев дерева B, то дерево A не является r-изоморфным дереву B:
∃LiA ∈ A, ∀LBj ∈ B, LiA [~/ ] LBj → A[⊆/ ] B .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов 39
Необходимое условие 2 отсутствия r-изоморфизма. Если в деревьях А и В присутствует более одной пары наборов листьев с частичным соответствием ( LiA ⊂ LBj , где LiA — i-й набор листьев дерева A), рассматриваемые деревья не r-изоморфны.
Аксиома 1. Невозможно найти такие два набора листьев LiA и LAj , предком которых являлся бы один и тот же узел.
Аксиома 2. При движении по узлам любой ветви дерева типы узлов строго чередуются. Лемма 1 (об ортогональности наборов листьев в составе дерева). В пределах дерева все наборы листьев ортогональны: LiA ∩ LAj = ∅, ∀i ≠ j . Лемма 2 (о совпадении типа узлов-предков для вершин в составе различных наборов листьев). Любые две вершины, входящие в состав одного набора листьев LiX дерева X, могут одновременно войти в состав набора листьев LYj дерева Y только в том случае, если тип узла
предков наборов листьев LiX и LYj совпадает. С л е д с т в и е . У полностью или частично эквивалентных наборов листьев не может
быть предков разного типа. Теорема 1 (о единственности r-изоморфной пары наборов листьев). Набору листьев LiA
может соответствовать не более одного полностью или частично эквивалентного набора ли-
стьев LBj : LiA [~] LBj : ∃LBk , LiA [~] LBk , k ≠ j .
Теорема 2 (о единственности r-изоморфной пары поддеревьев). В деревьях A и B не может быть более одной пары совпадающих поддеревьев.
С л е д с т в и е . Дереву A может быть изоморфно не более одного поддерева из дерева B. Приведенные выше аксиомы, леммы, теоремы и необходимые условия позволяют сформулировать алгоритм выявления r-изоморфизма пары деревьев A и B, ориентированный на параллельную аппаратную реализацию, в следующем виде. 1. Установить значения полей ТС всех наборов листьев дерева A в „00“ (соответствия нет), значения полей НС всех наборов листьев дерева A в „11…1“ (ссылка на несуществующий элемент дерева B), значения полей ТС всех узлов дерева A в „11“ (полное соответствие), значения полей НС всех узлов дерева A в „11…1“.
2. Если nL ( A) > nL ( B) (количество наборов листьев в подставляемом дереве больше
количества наборов листьев в объемлющем), установить признак ϕ = 0 отсутствия изоморфного дереву A поддерева в составе дерева B. Перейти к п. 7.
3. Поочередно выбирать все наборы листьев дерева B. Для выбранного набора листьев LBj дерева B осуществить параллельное во времени сравнение поля МВ с полями МВ всех на-
( )боров листьев дерева A, сформировать признаки полного δ+ = LiA = LBj и частичного
( )δ− = LiA ⊆ LBj соответствия наборов листьев с их последующим сохранением в поле ТС набора
листьев LiA в формате ⎣⎡δ− | δ+ ⎦⎤ (на позиции старшего бита — признак δ− , младшего — δ+ ) и в
поле ТС предка набора листьев LiA . В случае полного или частичного соответствия между на-
борами листьев LiA и LBj сохранить номер j, соответствующий предположительно изоморф-
ному эквиваленту LiA в составе дерева B, в поле НС набора листьев LiA , а также значение
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
40 Э. И. Ватутин, И. В. Зотов, В. С. Титов
поля СП набора листьев LBj в поле НС предка набора листьев LiA (предположительно изо-
морфный эквивалент предка набора листьев LiA ). 4. Если хотя бы для одного набора листьев дерева A не нашлось полностью или
частично эквивалентного предположительно изоморфного набора листьев в составе дерева B, т.е.
( )⎛
⎜⎜⎝
∃LkA
: δ−k
=
0
⇔
λ
=
& δ− i=0, NL( A)−1
LiA
⎞ ≠ 1⎠⎟⎟ ,
установить признак ϕ = 0 отсутствия изоморфного дереву A поддерева в дереве B. Перей-
ти к п. 7. 5. Просмотреть все узлы дерева A, кроме корня, в направлении от узлов с большим но-
мером к узлам с меньшим номером. Откорректировать значения поля ТС предка каждого i-го
( )узла как ТС↑′ = f ТС↓ , ТС↑ в случае наличия предка у предположительно изоморфного
эквивалента текущего узла ( γ = 0) , установить ТС↑′ = 00 в противном случае ( γ = 1) . (Здесь
f ( x, y) — функция корректировки значения поля ТС узла-предка, x — значение поля ТС
узла-предка, y — узла-потомка, эквивалентная функции минимума двух аргументов для
всех случаев, кроме f (10,10) = f (10,11) = 00 .) Задать значения поля НС предка рассматри-
ваемого узла a[i] как НС↑ = b[a[i].НС].СП , где НС↑ — значение поля НС узла-предка те-
кущего узла. Если поля ТС всех узлов дерева A имеют значение „11“ или „10“, т.е.
( )⎛
⎜⎜⎝ ϕ0
=
& δ− i=0,NT ( A)−1
Ti A
⎞ = 1⎟⎠⎟ ,
в дереве B есть поддерево, изоморфное дереву A, причем подстановка изоморфизма определяется значениями полей НС (i-му элементу дерева A соответствует изоморфный эквивалент a[i].НС в дереве B). В противном случае в составе дерева B нет поддерева, изоморфного де-
реву A. Установить признак ϕ = ϕ0 . 7. Конец алгоритма. Рассмотрим пример работы описанного алгоритма. В качестве объемлющего дерева B
возьмем дерево, приведенное на рис. 1. Пример (см. таблицу) показывает, что в состав дерева B (рис. 1) входит поддерево, r-изоморфное изображенному на рис. 2 дереву A.
a66⋅ a83⋅(a59|a104|a111)⋅(a55|a56|a112) T0
•
a66a83
L0
| T1
T2
|
L1 a59a104a111
L2 a55a56a112
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Пример определения r-изоморфизма
№ итерации
Пояснение к действию
1–
2 NL ( A) = 3, NL ( B ) = 5, nL ( A) ≤ nL ( B )
3.1 j = 0, B.L0 .МВ = a99
3.2 j = 1, B.L1.МВ = a94 a95 a128
3.3 j = 2, B.L2 .МВ = a65a66 a82 a83 , i = 0, A : L0 → T0 , B : L2 → T2
3.4 j = 3, B.L3 .МВ = a55 a56 a112 , i = 2, A : L2 → T2 , B : L3 → T3
3.5 j = 4, B.L4 .МВ = a59 a104 a111 , i = 1, A : L1 → T1 , B : L4 → T4 4 λ =1&1&1=1
5.1 i = 2, A : T2 → T0 , A.T2 [~] B.T3 B : T3 → T2 , γ = 0, T0 .ТС = f (11, 10) = 10
5.2 i = 1, A : T1 → y0 , A.T1 [~] B.T4
B : T4 → T2 , γ = 0, T0 .ТС = f (11, 10) = 10 6 ϕ =1&1&1=1
L0 С НС 00 –1 00 –1
00 –1
00 1
10 2
10 2
10 2 10 2
Значения полей элементов дерева А L1 L2 T0 T1 ТС НС ТС НС ТС НС ТС НС 00 –1 00 –1 11 –1 11 –1 00 –1 00 –1 11 –1 11 –1
00 –1 00 –1 11 –1 11 –1
00 –1 00 1 11 –1 11 –1
00 –1 00 1 10 2 11 –1
00 –1 11 3 10 2 11 –1
11 4 11 3 10 2 11 4 11 4 11 3 10 2 11 4
T2 ТС НС 11 –1 11 –1
11 –1
11 –1
11 –1
11 3
11 3 11 3
10 2 11 4 11 3 10 2 11 4 11 3
10 2 11 4 11 3 10 2 11 4 11 3 10 2 11 4 11 3 10 2 11 4 11 3
C2 C1
ρ РгТКЛB
1
2 РгТКУA 0 1
C3
27 РгТКЛA
&1 3
&
1
6 1
σ 39 28 DC
4 DC
1 d0 d1
5 0 RG 0 1 1j .. .. .. n-1 n-1 DSL DSR C L
f0
& f1
& f2
ra В.МВ rd
d А.МВ
d 21 CD
38 DC
dn-2 dn-1 СМНП 1
СМНП 2
& fn-2 & fn-1
LBj 14
LB L1A LA
LBj LB L1A LA
15 &1
16 &
17 18 & δ+ δ0+
19 &&
20 δ− δ0−
ССБВ 1 LiB
LA2 LiB ССБВ 2 L2A
δ1+ δ1−
LBi LnA
δ+ n −1
LiB LnA
ССБВ n
δ− n −1
1 13
36 &
∆− 7
1
&
8 1
9
ra
А.СП (нл)
rd
wa
wd
А.ТС (нл)
Cw
d δ−
wa
wd
А.НС (нл)
Cw
22 DC
24 &1
&
&1
23
&
ra0
10 1
11 1
ra1 d
wa
А.ТС (у)
rd0
ТС ↑
wd rd1 ТС ↓
Cw
wa
12 1
wd А.НС Cw (у)
rd
ra
26
1 & 29 λ
δi−
1 25 &
&
37 1
34 DC
ra
B.СП (нл)
rd
ra
A.СП (у)
rd
ra
B.СП (у)
rd
СkП ↓
&
30
35 & 1
СП↓ DC 33
γ
δ−↓ δ+↓ δ−↑ &
δ−′ СОТСП
31 &
φ0 32
δ+↑ δ+′ ТС↑′
Рис. 3
Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов 43
На основании приведенного выше алгоритма синтезировано специализированное устройство, функциональная схема которого представлена на рис. 3. Регистры 1, 2 и 27 предна-
значены для хранения значений nL ( B) , nT ( A) и nL ( A) соответственно, при этом значения
полей обрабатываемых деревьев хранятся в элементах однородной среды электронной модели дерева (ОСЭМД) [12] В.МВ, А.МВ, А.СП(нл), А.ТС(нл), А.НС(нл), B.СП(нл), А.СП(у), В.СП(у), А.ТС(у) и А.НС(у), схема ячейки которой приведена на рис. 4.
wdj owdj
wai Cw
Caw ra0[i] ra1[i] raK[i]
θ
1 &1
&
2
D TT C [i.j]
&1 3 &?
&
dij dij
&& 45
& 3+K
? wa Cw Caw
ra0[i] ra1[i]
wd owd
? d
raK[i]
d
rd0[j] rd1[j] rdK[j]
11
1
rd0[j] rd1[j] rdK[j]
Рис. 4
Коммутаторы 3, 23—25 управляются сигналом ρ и предназначены для коммутации значений на разных этапах работы алгоритма. Дешифраторы 4, 22, 28, 33, 34, 38 используются для преобразования номеров позиций элементов дерева в табличном представлении из двоичного кода в унитарный, используемый на входах ra (сокр. от „read address“ — адрес чтения) элементов ОСЭМД. Шифратор 21 используется для обратного преобразования. Сдвиговый регистр 5 используется для поочередного выбора элементов обрабатываемых деревьев. Блоки элементов ИЛИ 7, запрета 8, ИЛИ 9—12 используются для формирования начальных значений полей на этапе инициализации. Элементы ИЛИ 6, ИЛИ 13 и И 36 используются для коммутации синхросигналов. Блок элементов запрета 26 в совокупности с элементом И 29 и схемой маскировки неиспользуемых позиций (СМНП) 1 используется для формирования значения признака λ . Схема СМНП 2 в совокупности с блоком элементов запрета 37, элементом ИЛИ 39, запрета 30, блоком элементов И 31 и элементом ИЛИ 32 используется для формиро-
вания результирующего признака r-изоморфизма ϕ, при этом на выходе элемента ИЛИ 39
формируется значение признака σ отсутствия узлов у дерева A. Элемент И 35, на выходе которого формируется значение признака γ , в совокупности со схемой определения типа соот-
ветствия предка (СОТСП) отвечает за формирование обновленного значения поля типа соответствия узла-предка (фактически схема СОТСП реализует рассмотренную выше функцию f). Блок элементов НЕ 14 в совокупности со схемами сравнения битовых векторов (ССБВ) 1—n, образованными блоками элементов И 15 и 16, ИЛИ 17, И-НЕ 19 и элементами И 18 и 20,
используется для формирования признаков δi+ и δi− полного и частичного соответствия
наборов листьев. Элемент задержки предназначен для задержки синхросигнала сдвига
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
44 Э. И. Ватутин, И. В. Зотов, В. С. Титов
содержимого регистра 5 на время, достаточное для формирования и записи обновленных зна-
чений полей на предыдущей итерации алгоритма.
По сравнению с программной реализацией предлагаемого алгоритма выигрыш в скоро-
сти достигается за счет параллельной инициализации значений полей ТС и НС узлов и набо-
ров листьев дерева A; параллельного сравнения выбранного j-го набора листьев дерева B со
всеми наборами листьев дерева A; параллельного сравнения компонентов битовых векторов,
соответствующих наборам листьев; параллельного чтения и записи значений различных по-
лей (А.ТС(нл), А.НС(нл), А.НС(у) и т.д.) из/в разные элементы ОСЭМД.
При программной реализации [3, 5, 6] имеют место дополнительные затраты на органи-
зацию стека возвратов при рекуррентном сравнении деревьев, сканирование наборов листьев
при этом фактически является условием завершения рекурсии: обработка элементов наборов
листьев производится последовательно. Просмотр узлов деревьев как при программной, так и
при аппаратной реализации осуществляется последовательно.
Последовательная программная реализация предложенного в статье алгоритма провер-
ки r-изоморфизма предполагает попарное сравнение наборов листьев деревьев A и B (каждое
сравнение наборов листьев требует O ( Lmax ) действий) с последующим просмотром узлов
дерева A снизу вверх. Ее асимптотическая временная сложность составляет
( ) ( )O
N
2 Lmax
Lmax
+
NT
O L3max ,
где NLmax — максимально возможное число наборов листьев в дереве, Lmax — размерность битовых векторов МВ наборов листьев (фактически число вершин в алгоритме управления).
Предложенное аппаратное решение обладает асимптотической временной сложностью
( ) ( )O NLmax + NTmax O Lmax ,
где NTmax — максимально возможное число узлов в дереве.
СПИСОК ЛИТЕРАТУРЫ
1. Организация и синтез микропрограммных мультимикроконтроллеров / И. В. Зотов, В. А. Колосков, В. С. Титов и др. Курск: КурскГТУ, 1999. 368 с.
2. Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 5162.
3. Поиск базового сечения в задаче разбиения параллельных алгоритмов / Э. И. Ватутин, И. В. Зотов. Курск: КурскГТУ. 2003. 30 с.
4. Ватутин Э. И., Зотов И. В., Титов В. С. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов // Изв. ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ, 2003. Т. 1, вып. 2. С. 70—77.
5. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917.
6. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов. Свид-во об офиц. регистрации программы для ЭВМ № 2005613091 от 28.11.05.
7. Ватутин Э. И., Зотов И. В. Программная система для построения разбиений параллельных управляющих алгоритмов // Идентификация систем и задачи управления (SICPRO’06). М.: ИПУ РАН, 2006. С. 2239—2250.
8. Ватутин Э. И., Зотов И. В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления. Свид-во об офиц. регистрации программы для ЭВМ № 2007613222 от 30.07.07.
9. Ватутин Э. И., Волобуев С. В., Зотов И. В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров // Идентификация систем и задачи управления (SICPRO’08). М.: ИПУ РАН, 2008. С. 1917—1940.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Параллельно-конвейерное устройство для векторизации аэрокосмических изображений 45
10. Зыков А. А. Основы теории графов. М.: Наука, 1987. 381 с.
11. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: Пер. с англ. М.: Вильямс, 2002. 528 с.
12. Ватутин Э. И. Однородная среда электронной модели дерева для аппаратно-ориентированной обработки Rвыражений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2008). Ч. 1. Курск: КурскГТУ, 2008. С. 90—92.
Сведения об авторах
Эдуард Игоревич Ватутин — аспирант; Курский государственный технический университет, кафедра
вычислительной техники; E-mail: evatutin@rambler.ru
Игорь Валерьевич Зотов
— д-р техн. наук, профессор; Курский государственный технический уни-
верситет, кафедра вычислительной техники;
E-mail: zotovigor@yandex.ru
Виталий Семенович Титов — д-р техн. наук, профессор; Курский государственный технический уни-
верситет, кафедра вычислительной техники; зав. кафедрой;
E-mail: titov@vt.kstu.kursk.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 004.384:004.272:004.414.2
Э. И. ВАТУТИН, И. В. ЗОТОВ, В. С. ТИТОВ
ВЫЯВЛЕНИЕ ИЗОМОРФНЫХ ВХОЖДЕНИЙ R-ВЫРАЖЕНИЙ ПРИ ПОСТРОЕНИИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ
Представлен алгоритм выяснения отношения изоморфизма R-выражений (сечений параллельного алгоритма), основанный на ряде их особых свойств и ориентированный на аппаратную реализацию. Приведено описание устройства (акселератора) на его основе, позволяющего проводить проверку отношения изоморфизма за линейное время.
Ключевые слова: логический мультиконтроллер, синтез, параллельный алгоритм логического управления, разбиение, оптимизация, ориентированные деревья.
Реализация параллельных управляющих алгоритмов в базисе логических мультиконтроллеров (ЛМК) требует их декомпозиции на множество частных алгоритмов ограниченной сложности [1]. Получение оптимального набора частных алгоритмов (разбиения) — сложная комбинаторная задача. Качество ее решения существенно влияет на аппаратную сложность ЛМК и определяет, в конечном счете, время выполнения алгоритма. Один из наиболее эффективных путей решения данной задачи предлагает развиваемый авторами параллельнопоследовательный метод декомпозиции [2—8]. Как было показано в статье [9], он позволяет формировать наиболее близкие к оптимальным варианты разбиения с учетом основных структурных и технологических ограничений базиса ЛМК.
Один из ключевых этапов параллельно-последовательной декомпозиции — построение множества сечений, покрывающего все вершины исходного алгоритма. Формирование сечений осуществляется путем выполнения трудоемких операций подстановки над множеством так называемых R-выражений, описывающих алгоритм управления. Как показывают исследования, упрощение и ускорение этих операций возможно путем их сведения к действиям над деревьями, в частности, к проверке изоморфизма.
В настоящей статье предложен алгоритм определения изоморфных вхождений R-выражений, основанный на ряде их специфических свойств, не присущих графам или деревьям общего вида, и обеспечивающий проверку изоморфизма за полиномиальное время. (Как известно [10], для решения задачи распознавания изоморфизма графов общего вида до сих пор не только не придумано эффективного универсального алгоритма, но и не доказана ее принадлежность к классу P или NP [11].) Следует отметить, что рассматриваемый вид изоморфизма R-выражений определяется исходя из возможности проведения операции подстановки [1, 3, 4] и несколько отличается от „классического“ понятия изоморфизма [10], определяемого для графов, ввиду чего далее будем именовать его r-изоморфизмом.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
38 Э. И. Ватутин, И. В. Зотов, В. С. Титов
При практической реализации операций над R-выражениями удобным является их представление в виде деревьев, допускающее преобразование в табличный вид (рис. 1). Каж-
дый элемент дерева X, представленного совокупностью наборов листьев L1X , L2X , ..., LnXL( X ) ,
узлов T1X , T2X , ..., TnXT ( X ) и связей между ними, кодируется набором полей. С учетом ряда осо-
бенностей обработки наборы листьев и узлы дерева кодируются отдельно. Узлы дерева представлены полями:
1) типа узла (ТУ) — параллельный или альтернативный; 2) ссылки на предка (СП) — номер узла-предка; 3) номера соответствия (НС) — номер изоморфного эквивалента в соседнем дереве; 4) типа соответствия (ТС) — может принимать значения „0*“ — соответствие отсутствует, „10“ — неполное (частичное) соответствие, „11“ — полное соответствие.
a99⋅(a94|a95|a128|(a65⋅a66⋅a82⋅a83⋅(a55|a56|a112) ⋅(a59|a104|a111))) • T0
a99 L0
| T1
a94a95a128 L1
• T2
a65a66a82a83
L2 | T3 L3
a55a56a112
| T4 L4
a59a104a111
Наборы листьев
Узлы
Тип Ссылка на узла предка
T0 • T1 | T2 • T3 |
— T0 T1 T2
T4 |
T2
T5 …
— ...
— …
NLmax —
—
Текущее количество узлов (NТ)
5
Текущее количество
наборов листьев
(NL) 5
№
L0 L1 L2 L3 L4 L5 … NLmax
Множество Ссылка на
вершин предка
99 94, 95, 128
T0 T1
65, 66, 82, 83 T2
55, 56, 112
T3
59, 104, 111 —
T4 —
……
——
Рис. 1
Наборам листьев дерева при этом соответствуют поля множества вершин (МВ) — двоичный вектор с единичными битами в позициях, соответствующих номерам присутствующих в наборе вершин, а также поля СП, НС и ТС. Во избежание путаницы при обозначении одноименных полей, соответствующих узлам и наборам листьев, будем обозначать их с указанием принадлежности к элементам дерева (например, СП(у) и СП(нл)).
Краткое описание свойств R-выражений, гарантирующих наличие единственно возможного изоморфного эквивалента поддерева и позволяющих исключить из рассмотрения проверку соответствия типов узлов деревьев, приведено ниже (ввиду ограниченного объема статьи доказательства лемм и теорем не приведены).
Необходимое условие 1 отсутствия r-изоморфизма. Если в дереве A найдется набор ли-
стьев LiA , не находящийся в отношении эквивалентности, обозначаемом как
L1 [~] L2 ⇔ ( L1 = L2 ) ∨ ( L1 ⊂ L2 ) ∨ ( L2 ⊂ L1 ) ,
ни с одним набором листьев дерева B, то дерево A не является r-изоморфным дереву B:
∃LiA ∈ A, ∀LBj ∈ B, LiA [~/ ] LBj → A[⊆/ ] B .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов 39
Необходимое условие 2 отсутствия r-изоморфизма. Если в деревьях А и В присутствует более одной пары наборов листьев с частичным соответствием ( LiA ⊂ LBj , где LiA — i-й набор листьев дерева A), рассматриваемые деревья не r-изоморфны.
Аксиома 1. Невозможно найти такие два набора листьев LiA и LAj , предком которых являлся бы один и тот же узел.
Аксиома 2. При движении по узлам любой ветви дерева типы узлов строго чередуются. Лемма 1 (об ортогональности наборов листьев в составе дерева). В пределах дерева все наборы листьев ортогональны: LiA ∩ LAj = ∅, ∀i ≠ j . Лемма 2 (о совпадении типа узлов-предков для вершин в составе различных наборов листьев). Любые две вершины, входящие в состав одного набора листьев LiX дерева X, могут одновременно войти в состав набора листьев LYj дерева Y только в том случае, если тип узла
предков наборов листьев LiX и LYj совпадает. С л е д с т в и е . У полностью или частично эквивалентных наборов листьев не может
быть предков разного типа. Теорема 1 (о единственности r-изоморфной пары наборов листьев). Набору листьев LiA
может соответствовать не более одного полностью или частично эквивалентного набора ли-
стьев LBj : LiA [~] LBj : ∃LBk , LiA [~] LBk , k ≠ j .
Теорема 2 (о единственности r-изоморфной пары поддеревьев). В деревьях A и B не может быть более одной пары совпадающих поддеревьев.
С л е д с т в и е . Дереву A может быть изоморфно не более одного поддерева из дерева B. Приведенные выше аксиомы, леммы, теоремы и необходимые условия позволяют сформулировать алгоритм выявления r-изоморфизма пары деревьев A и B, ориентированный на параллельную аппаратную реализацию, в следующем виде. 1. Установить значения полей ТС всех наборов листьев дерева A в „00“ (соответствия нет), значения полей НС всех наборов листьев дерева A в „11…1“ (ссылка на несуществующий элемент дерева B), значения полей ТС всех узлов дерева A в „11“ (полное соответствие), значения полей НС всех узлов дерева A в „11…1“.
2. Если nL ( A) > nL ( B) (количество наборов листьев в подставляемом дереве больше
количества наборов листьев в объемлющем), установить признак ϕ = 0 отсутствия изоморфного дереву A поддерева в составе дерева B. Перейти к п. 7.
3. Поочередно выбирать все наборы листьев дерева B. Для выбранного набора листьев LBj дерева B осуществить параллельное во времени сравнение поля МВ с полями МВ всех на-
( )боров листьев дерева A, сформировать признаки полного δ+ = LiA = LBj и частичного
( )δ− = LiA ⊆ LBj соответствия наборов листьев с их последующим сохранением в поле ТС набора
листьев LiA в формате ⎣⎡δ− | δ+ ⎦⎤ (на позиции старшего бита — признак δ− , младшего — δ+ ) и в
поле ТС предка набора листьев LiA . В случае полного или частичного соответствия между на-
борами листьев LiA и LBj сохранить номер j, соответствующий предположительно изоморф-
ному эквиваленту LiA в составе дерева B, в поле НС набора листьев LiA , а также значение
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
40 Э. И. Ватутин, И. В. Зотов, В. С. Титов
поля СП набора листьев LBj в поле НС предка набора листьев LiA (предположительно изо-
морфный эквивалент предка набора листьев LiA ). 4. Если хотя бы для одного набора листьев дерева A не нашлось полностью или
частично эквивалентного предположительно изоморфного набора листьев в составе дерева B, т.е.
( )⎛
⎜⎜⎝
∃LkA
: δ−k
=
0
⇔
λ
=
& δ− i=0, NL( A)−1
LiA
⎞ ≠ 1⎠⎟⎟ ,
установить признак ϕ = 0 отсутствия изоморфного дереву A поддерева в дереве B. Перей-
ти к п. 7. 5. Просмотреть все узлы дерева A, кроме корня, в направлении от узлов с большим но-
мером к узлам с меньшим номером. Откорректировать значения поля ТС предка каждого i-го
( )узла как ТС↑′ = f ТС↓ , ТС↑ в случае наличия предка у предположительно изоморфного
эквивалента текущего узла ( γ = 0) , установить ТС↑′ = 00 в противном случае ( γ = 1) . (Здесь
f ( x, y) — функция корректировки значения поля ТС узла-предка, x — значение поля ТС
узла-предка, y — узла-потомка, эквивалентная функции минимума двух аргументов для
всех случаев, кроме f (10,10) = f (10,11) = 00 .) Задать значения поля НС предка рассматри-
ваемого узла a[i] как НС↑ = b[a[i].НС].СП , где НС↑ — значение поля НС узла-предка те-
кущего узла. Если поля ТС всех узлов дерева A имеют значение „11“ или „10“, т.е.
( )⎛
⎜⎜⎝ ϕ0
=
& δ− i=0,NT ( A)−1
Ti A
⎞ = 1⎟⎠⎟ ,
в дереве B есть поддерево, изоморфное дереву A, причем подстановка изоморфизма определяется значениями полей НС (i-му элементу дерева A соответствует изоморфный эквивалент a[i].НС в дереве B). В противном случае в составе дерева B нет поддерева, изоморфного де-
реву A. Установить признак ϕ = ϕ0 . 7. Конец алгоритма. Рассмотрим пример работы описанного алгоритма. В качестве объемлющего дерева B
возьмем дерево, приведенное на рис. 1. Пример (см. таблицу) показывает, что в состав дерева B (рис. 1) входит поддерево, r-изоморфное изображенному на рис. 2 дереву A.
a66⋅ a83⋅(a59|a104|a111)⋅(a55|a56|a112) T0
•
a66a83
L0
| T1
T2
|
L1 a59a104a111
L2 a55a56a112
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Пример определения r-изоморфизма
№ итерации
Пояснение к действию
1–
2 NL ( A) = 3, NL ( B ) = 5, nL ( A) ≤ nL ( B )
3.1 j = 0, B.L0 .МВ = a99
3.2 j = 1, B.L1.МВ = a94 a95 a128
3.3 j = 2, B.L2 .МВ = a65a66 a82 a83 , i = 0, A : L0 → T0 , B : L2 → T2
3.4 j = 3, B.L3 .МВ = a55 a56 a112 , i = 2, A : L2 → T2 , B : L3 → T3
3.5 j = 4, B.L4 .МВ = a59 a104 a111 , i = 1, A : L1 → T1 , B : L4 → T4 4 λ =1&1&1=1
5.1 i = 2, A : T2 → T0 , A.T2 [~] B.T3 B : T3 → T2 , γ = 0, T0 .ТС = f (11, 10) = 10
5.2 i = 1, A : T1 → y0 , A.T1 [~] B.T4
B : T4 → T2 , γ = 0, T0 .ТС = f (11, 10) = 10 6 ϕ =1&1&1=1
L0 С НС 00 –1 00 –1
00 –1
00 1
10 2
10 2
10 2 10 2
Значения полей элементов дерева А L1 L2 T0 T1 ТС НС ТС НС ТС НС ТС НС 00 –1 00 –1 11 –1 11 –1 00 –1 00 –1 11 –1 11 –1
00 –1 00 –1 11 –1 11 –1
00 –1 00 1 11 –1 11 –1
00 –1 00 1 10 2 11 –1
00 –1 11 3 10 2 11 –1
11 4 11 3 10 2 11 4 11 4 11 3 10 2 11 4
T2 ТС НС 11 –1 11 –1
11 –1
11 –1
11 –1
11 3
11 3 11 3
10 2 11 4 11 3 10 2 11 4 11 3
10 2 11 4 11 3 10 2 11 4 11 3 10 2 11 4 11 3 10 2 11 4 11 3
C2 C1
ρ РгТКЛB
1
2 РгТКУA 0 1
C3
27 РгТКЛA
&1 3
&
1
6 1
σ 39 28 DC
4 DC
1 d0 d1
5 0 RG 0 1 1j .. .. .. n-1 n-1 DSL DSR C L
f0
& f1
& f2
ra В.МВ rd
d А.МВ
d 21 CD
38 DC
dn-2 dn-1 СМНП 1
СМНП 2
& fn-2 & fn-1
LBj 14
LB L1A LA
LBj LB L1A LA
15 &1
16 &
17 18 & δ+ δ0+
19 &&
20 δ− δ0−
ССБВ 1 LiB
LA2 LiB ССБВ 2 L2A
δ1+ δ1−
LBi LnA
δ+ n −1
LiB LnA
ССБВ n
δ− n −1
1 13
36 &
∆− 7
1
&
8 1
9
ra
А.СП (нл)
rd
wa
wd
А.ТС (нл)
Cw
d δ−
wa
wd
А.НС (нл)
Cw
22 DC
24 &1
&
&1
23
&
ra0
10 1
11 1
ra1 d
wa
А.ТС (у)
rd0
ТС ↑
wd rd1 ТС ↓
Cw
wa
12 1
wd А.НС Cw (у)
rd
ra
26
1 & 29 λ
δi−
1 25 &
&
37 1
34 DC
ra
B.СП (нл)
rd
ra
A.СП (у)
rd
ra
B.СП (у)
rd
СkП ↓
&
30
35 & 1
СП↓ DC 33
γ
δ−↓ δ+↓ δ−↑ &
δ−′ СОТСП
31 &
φ0 32
δ+↑ δ+′ ТС↑′
Рис. 3
Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов 43
На основании приведенного выше алгоритма синтезировано специализированное устройство, функциональная схема которого представлена на рис. 3. Регистры 1, 2 и 27 предна-
значены для хранения значений nL ( B) , nT ( A) и nL ( A) соответственно, при этом значения
полей обрабатываемых деревьев хранятся в элементах однородной среды электронной модели дерева (ОСЭМД) [12] В.МВ, А.МВ, А.СП(нл), А.ТС(нл), А.НС(нл), B.СП(нл), А.СП(у), В.СП(у), А.ТС(у) и А.НС(у), схема ячейки которой приведена на рис. 4.
wdj owdj
wai Cw
Caw ra0[i] ra1[i] raK[i]
θ
1 &1
&
2
D TT C [i.j]
&1 3 &?
&
dij dij
&& 45
& 3+K
? wa Cw Caw
ra0[i] ra1[i]
wd owd
? d
raK[i]
d
rd0[j] rd1[j] rdK[j]
11
1
rd0[j] rd1[j] rdK[j]
Рис. 4
Коммутаторы 3, 23—25 управляются сигналом ρ и предназначены для коммутации значений на разных этапах работы алгоритма. Дешифраторы 4, 22, 28, 33, 34, 38 используются для преобразования номеров позиций элементов дерева в табличном представлении из двоичного кода в унитарный, используемый на входах ra (сокр. от „read address“ — адрес чтения) элементов ОСЭМД. Шифратор 21 используется для обратного преобразования. Сдвиговый регистр 5 используется для поочередного выбора элементов обрабатываемых деревьев. Блоки элементов ИЛИ 7, запрета 8, ИЛИ 9—12 используются для формирования начальных значений полей на этапе инициализации. Элементы ИЛИ 6, ИЛИ 13 и И 36 используются для коммутации синхросигналов. Блок элементов запрета 26 в совокупности с элементом И 29 и схемой маскировки неиспользуемых позиций (СМНП) 1 используется для формирования значения признака λ . Схема СМНП 2 в совокупности с блоком элементов запрета 37, элементом ИЛИ 39, запрета 30, блоком элементов И 31 и элементом ИЛИ 32 используется для формиро-
вания результирующего признака r-изоморфизма ϕ, при этом на выходе элемента ИЛИ 39
формируется значение признака σ отсутствия узлов у дерева A. Элемент И 35, на выходе которого формируется значение признака γ , в совокупности со схемой определения типа соот-
ветствия предка (СОТСП) отвечает за формирование обновленного значения поля типа соответствия узла-предка (фактически схема СОТСП реализует рассмотренную выше функцию f). Блок элементов НЕ 14 в совокупности со схемами сравнения битовых векторов (ССБВ) 1—n, образованными блоками элементов И 15 и 16, ИЛИ 17, И-НЕ 19 и элементами И 18 и 20,
используется для формирования признаков δi+ и δi− полного и частичного соответствия
наборов листьев. Элемент задержки предназначен для задержки синхросигнала сдвига
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
44 Э. И. Ватутин, И. В. Зотов, В. С. Титов
содержимого регистра 5 на время, достаточное для формирования и записи обновленных зна-
чений полей на предыдущей итерации алгоритма.
По сравнению с программной реализацией предлагаемого алгоритма выигрыш в скоро-
сти достигается за счет параллельной инициализации значений полей ТС и НС узлов и набо-
ров листьев дерева A; параллельного сравнения выбранного j-го набора листьев дерева B со
всеми наборами листьев дерева A; параллельного сравнения компонентов битовых векторов,
соответствующих наборам листьев; параллельного чтения и записи значений различных по-
лей (А.ТС(нл), А.НС(нл), А.НС(у) и т.д.) из/в разные элементы ОСЭМД.
При программной реализации [3, 5, 6] имеют место дополнительные затраты на органи-
зацию стека возвратов при рекуррентном сравнении деревьев, сканирование наборов листьев
при этом фактически является условием завершения рекурсии: обработка элементов наборов
листьев производится последовательно. Просмотр узлов деревьев как при программной, так и
при аппаратной реализации осуществляется последовательно.
Последовательная программная реализация предложенного в статье алгоритма провер-
ки r-изоморфизма предполагает попарное сравнение наборов листьев деревьев A и B (каждое
сравнение наборов листьев требует O ( Lmax ) действий) с последующим просмотром узлов
дерева A снизу вверх. Ее асимптотическая временная сложность составляет
( ) ( )O
N
2 Lmax
Lmax
+
NT
O L3max ,
где NLmax — максимально возможное число наборов листьев в дереве, Lmax — размерность битовых векторов МВ наборов листьев (фактически число вершин в алгоритме управления).
Предложенное аппаратное решение обладает асимптотической временной сложностью
( ) ( )O NLmax + NTmax O Lmax ,
где NTmax — максимально возможное число узлов в дереве.
СПИСОК ЛИТЕРАТУРЫ
1. Организация и синтез микропрограммных мультимикроконтроллеров / И. В. Зотов, В. А. Колосков, В. С. Титов и др. Курск: КурскГТУ, 1999. 368 с.
2. Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 5162.
3. Поиск базового сечения в задаче разбиения параллельных алгоритмов / Э. И. Ватутин, И. В. Зотов. Курск: КурскГТУ. 2003. 30 с.
4. Ватутин Э. И., Зотов И. В., Титов В. С. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов // Изв. ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ, 2003. Т. 1, вып. 2. С. 70—77.
5. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917.
6. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов. Свид-во об офиц. регистрации программы для ЭВМ № 2005613091 от 28.11.05.
7. Ватутин Э. И., Зотов И. В. Программная система для построения разбиений параллельных управляющих алгоритмов // Идентификация систем и задачи управления (SICPRO’06). М.: ИПУ РАН, 2006. С. 2239—2250.
8. Ватутин Э. И., Зотов И. В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления. Свид-во об офиц. регистрации программы для ЭВМ № 2007613222 от 30.07.07.
9. Ватутин Э. И., Волобуев С. В., Зотов И. В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров // Идентификация систем и задачи управления (SICPRO’08). М.: ИПУ РАН, 2008. С. 1917—1940.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Параллельно-конвейерное устройство для векторизации аэрокосмических изображений 45
10. Зыков А. А. Основы теории графов. М.: Наука, 1987. 381 с.
11. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: Пер. с англ. М.: Вильямс, 2002. 528 с.
12. Ватутин Э. И. Однородная среда электронной модели дерева для аппаратно-ориентированной обработки Rвыражений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2008). Ч. 1. Курск: КурскГТУ, 2008. С. 90—92.
Сведения об авторах
Эдуард Игоревич Ватутин — аспирант; Курский государственный технический университет, кафедра
вычислительной техники; E-mail: evatutin@rambler.ru
Игорь Валерьевич Зотов
— д-р техн. наук, профессор; Курский государственный технический уни-
верситет, кафедра вычислительной техники;
E-mail: zotovigor@yandex.ru
Виталий Семенович Титов — д-р техн. наук, профессор; Курский государственный технический уни-
верситет, кафедра вычислительной техники; зав. кафедрой;
E-mail: titov@vt.kstu.kursk.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2