РЕАЛИЗАЦИЯ ОПЕРАЦИИ ВСТАВКИ ПОДДЕРЕВА ПРИ АППАРАТНО-ОРИЕНТИРОВАННОЙ ОБРАБОТКЕ R-ВЫРАЖЕНИЙ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 004.384:004.272:004.414.2
Э. И. ВАТУТИН, И. В. ЗОТОВ, В. С. ТИТОВ, М. М. АЛЬ-АШВАЛ
РЕАЛИЗАЦИЯ ОПЕРАЦИИ ВСТАВКИ ПОДДЕРЕВА ПРИ АППАРАТНО-ОРИЕНТИРОВАННОЙ ОБРАБОТКЕ R-ВЫРАЖЕНИЙ
Рассматривается устройство, позволяющее реализовать операцию вставки поддерева в дерево при аппаратно-ориентированной обработке R-выражений, возникающей при выполнении эквивалентных преобразований параллельных алгоритмов.
Ключевые слова: логический мультиконтроллер, параллельный алгоритм логического управления, разбиение, оптимизация, R-выражение, ориентированное дерево, спецпроцессор.
Построение систем логического управления, ориентированных на реализацию параллельных управляющих алгоритмов в базисе логических мультиконтроллеров (ЛМК), требует декомпозиции комплексных параллельных алгоритмов теоретически неограниченной сложности на множество частных алгоритмов ограниченной сложности [1]. Получение оптимального набора частных алгоритмов (разбиения) представляет собой сложную комбинаторную задачу, решение которой возможно лишь с помощью эвристических алгоритмов. Качество решения этой задачи существенно влияет на аппаратную сложность ЛМК и определяет, в конечном счете, время выполнения алгоритма. Эффективным путем решения данной задачи является параллельно-последовательный метод декомпозиции [2—5].
Один из ключевых этапов параллельно-последовательной декомпозиции — построение множества сечений, покрывающего все вершины исходного алгоритма. Формирование сечений осуществляется посредством выполнения трудоемких операций подстановки над множеством так называемых R-выражений, описывающих алгоритм управления. Как показывают исследования, упрощение и ускорение этих операций возможно путем их сведения к действиям над деревьями. Такие действия, в свою очередь, допускают разбиение на ряд более простых (элементарных) операций [6]. Схематично операции подстановки могут быть представлены следующим образом:
⎧⎪⎪⎪⎪⎪⎩⎨ij::
XR AR
→ →
BR CR
⇒
i : X R → BR′ (u-подстановка);
⎧⎪⎪⎪⎪⎪⎨⎩ij::
CR BR
→ →
AR XR
⇒
j : BR′ → X R (d-подстановка),
где X R — некоторое R-выражение, не участвующее в подстановке; BR′ — R-выражение, получаемое из R-выражения BR после удаления поддерева AR и вставки вместо него дерева CR .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
64 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
Методика практической реализации операций над R-выражениями, а также представление их в виде деревьев, допускающее преобразование в табличный вид, приведены в работах [7, с. 38; 8]. Здесь напомним следующее: каждый элемент а дерева X, представленного совокупностью наборов листьев L1X , L2X ,..., LXNL( X ) , узлов T1X ,T2X ,...,TNXT ( X ) и связей между ними, кодируется набором полей. С учетом ряда особенностей обработки, наборы листьев и узлы дерева кодируются отдельно. Узлы дерева представлены следующими полями: тип узла
( ( ))(ТУ) — параллельный или альтернативный t TiX ; ссылка на предка (СП) — номер узла-
( ( ))предка u TiX ; номер соответствия (НС) — номер изоморфного эквивалента в соседнем
( ( ))дереве nr TiX ; тип соответствия (ТС) — отсутствующее, полное или частичное соответст-
( ( ))вие Δ TiX ; наборам листьев дерева при этом соответствуют поля множества вершин (МВ) —
двоичный вектор с единичными битами в позициях, соответствующих номерам присутствующих в наборе вершин, а также перечисленные выше поля СП, НС и ТС.
Табличное представление R-выражений подчиняется ряду следующих требований [8]. 1. Корень дерева хранится в позиции с номером 0. Значение поля СП корня указывает на заведомо несуществующий элемент дерева. 2. Для каждого узла дерева его потомки хранятся в позициях с номерами, превосходящими номер позиции самого узла (при этом порядок хранения потомков не важен). 3. Все узлы и наборы листьев дерева хранятся в смежных позициях (без „пропусков“). 4. Каждому узлу дерева соответствует не более одного дочернего набора листьев, в дереве не может быть „пустых“ наборов листьев, не содержащих вершин. 5. Если дерево представлено единственным набором листьев (без узлов), то в составе этого набора может быть всего один элемент (одна вершина алгоритма управления). 6. В составе корректного дерева не может быть совпадения типа узлов у любой пары смежных узлов. 7. Дерево содержит, по меньшей мере, один набор листьев. Число узлов дерева может быть нулевым. В настоящей статье предложена аппаратная реализация операции вставки поддерева. Она выполняется непосредственно после операции удаления поддерева, r-изоморфного [7, 8] дереву AR , в результате которого может быть нарушено требование № 3. Рассматриваемая операция состоит из двух стадий: на первой производится копирование элементов дерева, на второй — настройка связей для скопированных элементов. В результате выполнения операции копирования элементов дерева C R должны быть учтены требования № 2 и 4. При этом в общем случае требования № 3 и 6 в результате выполнения операции вставки поддерева не выполняются, что обусловливает необходимость удаления „пропусков“ непосредственно после рассматриваемой операции. Общие принципы выполнения первой стадии продемонстрированы на рис. 1 (белые квадраты — свободные позиции, темные квадраты — занятые позиции, крестами помечены удаленные элементы, стрелками обозначены операции копирования элементов дерева). На первой стадии при копировании узлов дерева (см. рис. 1, а) необходимо соблюдение требования № 2 корректности дерева. Наиболее простой способ обеспечить выполнение этого требования — последовательная вставка „новых“ узлов, начиная с позиции с номером, превосходящим номера уже имеющихся узлов дерева BR , с сохранением порядка их следо-
вания. Номер такой позиции может быть определен как NχT = g0↑ (ΧT ) +1, где
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
65
( ( ) ( ) ( )) ( )ΧT (B) = χ T0B , χ T1B , ..., χ TnB−1 — вектор двоичных признаков χ TiX свободных пози-
ций среди узлов дерева BR , g0↑ (Χ) — функция выделения позиции старшего нуля в двоич-
ном векторе Χ [9]. Копирование наборов листьев (см. рис. 1, б) не нарушает требований корректности дерева и поэтому может быть осуществлено непосредственно в первую свободную
ячейку с младшим номером, который определяется как g1↓ (ΧL ) , где
( ( ) ( ) ( )) ( )ΧL (B) = χ LB0 , χ L1B , ..., χ LBm−1 — вектор двоичных признаков χ LiX свободных пози-
ций среди наборов листьев дерева BR , g1↓ (Χ) — функция выделения позиции младшей еди-
ницы в двоичном векторе Χ [9]. Подобный способ копирования наборов листьев уменьшает число действий, затрачиваемых впоследствии на ликвидацию пустых позиций.
При добавлении каждого нового элемента в дерево BR также необходимо инкрементиро-
( ) ( )вать значение NT BR (при добавлении узла) или NL BR (при добавлении набора листьев).
а) Узлы дерева BR (после удаления поддерева)
0
б) Наборы листьев BR (после удаления поддерева) 0
Наборы листьев дерева СR 0
1 11
2 22
3 33
4 44
5 6 7 NχT 8 9
Узлы дерева CR
i′ = i + NχT
0 1
2
3
5 6 7 8 9
5 6
N Lmax
10 4 10 i′ = g1↓ ( ΧL )
11 5 11
( )ΧL =
χ1L
,
χ
L 2
,
...,
χ
L N
L
max
−1
… … … …
NTmax
NTmax
N Lmax
Рис. 1
Вторая стадия начинается с корректировки значений полей СП „новых“ элементов де-
рева BR , скопированных в него из дерева CR . Прежде всего корректировке подвергаются
( ) ( )значения
полей
СП,
обозначаемые
как
u (⋅) ,
„новых“
элементов:
u LBi
:= u LiB
+
N
T χ
,
( ) ( )u
T
B j
:= u
T
B j
+ NχT . Подобные формулы корректировки объясняются достаточно просто:
нулевой
узел
(корень)
дерева
CR
попадает
в
дереве
BR
в
позицию
с
номером
N
T χ
,
первый
—
в позицию
N
T χ
+1 и т.д.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
66 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
После выполнения указанных корректировок необходимо настроить связь скопирован-
ного поддерева из „новых“ элементов с уже присутствующими элементами дерева BR (точ-
нее, с узлом, r-изоморфным корню дерева AR , при частичном соответствии, или его предком при полном соответствии). Детали реализации настройки связи между деревьями представлены в табл. 1 и проиллюстрированы на рис. 2, где а, б, в соответствуют трем различным случаям выполнения операции подстановки, приведенным в таблице.
Таблица 1
Наличие в дереве AR узлов
(σ A )
ТС корня дерева AR
(Δ(T0A ))
Формула обновленного значения поля СП корневого элемента скопированного дерева
Полное: Δ=11 1
Частичное: Δ=10
x = u (⎜⎜⎝⎜⎛⎜TnBr T0A) ⎟⎟⎟⎠⎟⎞⎟
( )x = nr T0A
0 Полное, частичное: Δ= 1*
x
=
u
⎜⎜⎜⎛⎝⎜
LB
nr
(
L0A
)
⎟⎞⎟⎠⎟⎟⎟
Особым случаем, не указанным в табл. 1, является ситуация, когда дерево CR не содержит узлов, что обозначим нулевым значением двоичного признака σC . В этом случае при выполнении описанных выше действий возможно нарушение требования № 4, если у элемента дерева BR , на который производится настройка поля СП добавляемого набора листьев LC0
дерева CR , уже есть дочерний набор листьев LBk . Правильным действием в подобной ситуа-
ции является добавление элементов вектора LC0 к элементам вектора LBk : LBk := LBk ∪ LC0 вместо добавления еще одного набора листьев.
Алгоритм преобразования выполняется следующим образом.
1. Если дерево CR не содержит узлов (σC = 0) и узел дерева BR с номером х, опреде-
ляемым согласно табл. 1, имеет дочерний набор листьев LBk (что в дальнейшем будем обозна-
( )чать с использованием двоичного признака κ TiX , равного в данном случае единице), пе-
рейти к п. 7.
2. Определить значение
N
T χ
:=
g0↑ (ΧT
)+1.
Если
ΧT = 00...0
(все элементы в таблич-
ном представлении заняты), установить признак ошибки ε1 := 1 и перейти к п. 8, в противном
случае установить признак ε1 := 0 .
( )3. Копирование узлов: скопировать узлы TiC дерева CR , i = 0, NT C R −1, в смежные
позиции дерева BR , начиная с позиции NχT . При недостаточном количестве свободных по-
зиций сформировать признак ошибки εT := 1 и перейти к п. 8, в противном случае положить εT := 0 .
4. Копирование наборов листьев: скопировать наборы листьев LCi дерева CR ,
( )i = 0, NL C R −1 , в дерево BR , причем i-й набор листьев дерева CR копируется в позицию ( )k = g1↓ (ΧL ) , а сама позиция помечается как используемая: χ LBk := 0 . В случае если на ка-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
67
ком-либо из шагов ΧL = 00...0 (свободной позиции нет), установить признак ошибки εL := 1 и перейти к п. 8, в противном случае положить εL := 0 .
5. Увеличить значения текущего количества узлов и текущего количества листьев дере-
( ) ( ) ( ) ( ) ( ) ( )ва BR : NT BR := NT BR + NT C R , NL BR := NL BR + NL C R .
6. Модифицировать значения полей СП „новых“ элементов дерева BR , скопированных
( ) ( ) ( ) ( )из дерева
CR , за исключением корневого, как
u
LiB
:= u
LiB
+
N
T χ
,
u
T
B j
:= u
T
B j
+ NχT .
Для „нового“ элемента дерева BR , соответствующего корневому элементу дерева CR , установить значение поля СП согласно табл. 1. Перейти к п. 8.
7. Осуществить объединение наборов листьев: LBk := LBk ∪ LC0 .
8. Конец алгоритма. Схема, реализующая предложенный алгоритм, приведена на рис. 3 (сокращения, использованные в схеме, аналогичны принятым в работе [7]). Регистр 1 хранит текущее количе-
ство узлов дерева BR и инкрементируется по мере добавления в дерево BR новых узлов. Коммутатор 2 используется для выбора значения вектора, подаваемого на вход элемента В.УЭ(у) [7, 10] в качестве адреса записи. Элементы 3 и 4 используются при инициализации значений вектора В.УЭ(у). Шифратор 5 предназначен для преобразования значения номера свободной позиции с выхода схемы выделения старшего нуля (СВСН) из унитарного в двоичное представление, сохраняющегося в регистре 6. Элемент задержки 7 обеспечивает запись значения в регистр 6 только по окончании его формирования на выходе схемы СВСН. Эле-
мент ИЛИ—НЕ 8 используется для формирования сигнала ошибки ε1 . Регистры 9 и 27 пред-
назначены для хранения числа узлов и наборов листьев дерева CR соответственно. Коммутатор 10 в совокупности с дешифратором 11 обеспечивают запись в сдвиговый регистр 12 значения текущего числа элементов (наборов листьев или узлов) в унитарном коде в зависимо-
сти от этапа обработки. Элемент И 13 запрещает прохождение синхросигнала c1 при инициализации значения В.УЭ(нл) на входы элемента В.УЭ(у) и регистра 6. Регистр 14 хранит
текущее количество наборов листьев дерева BR , инкрементируемое по мере добавления новых наборов листьев. Коммутатор 15 в совокупности с элементами 16 и 17 обеспечивает ини-
циализацию значения вектора УЭ наборов листьев дерева BR (в ходе дальнейшей обработки значения вектора УЭ изменяются согласно алгоритму обработки с использованием перечисленных элементов). Шифратор 18 используется для преобразования значения текущего рассматриваемого элемента из унитарного кода в двоичный. Сумматор 19 обеспечивает формирование на его выходе значения NTχ + i очередной свободной позиции и признака ошибки εT . Дешифратор 20 преобразует значение NTχ + i в унитарный код для его дальнейшего использования в качестве адреса записи. Коммутаторы 21, 23, 28, 31, 46 и 47 используются для
выбора значения элемента дерева BR модифицируемого элемента в зависимости от этапа алгоритма и особенностей обработки. Сумматор 22 обеспечивает формирование обновленного значения поля СП копируемого элемента. Элемент ИЛИ 24 служит для прохождения синхросигнала записи на вход элемента В.СП(у). Элементы 25 и 26 обеспечивают прохождение син-
хросигналов c2 и c3 на вход регистра 12. Элемент ИЛИ—НЕ 29 служит для формирования
признака ошибки εL . Сумматор 30 используется для корректировки значения поля СП копируемого набора листьев. Элемент ИЛИ 32 обеспечивает прохождение синхросигнала на вход элемента В.МВ, активирующего модификацию поля МВ в зависимости от ситуации.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
а)
Дерево B R
Дерево A R
| a 1а 2
11 •
Удаление
•
11
поддерева а 3а 4
а3а 4
Дерево B R ′ |
а 1а 2
• а 3а 4
Вставка поддерева
Дерево B R″
|2
а 1а 2
•
а 3а 4
Дерево A R 1•
а3а4
3
Дерево СR ...
1 — i:=nr(T0A) 2 — j:=u(TiB) B 3 — u(T0C= TNχT):=j
б) Дерево B R
Дерево A R
Дерево B R ′
Дерево B R″
Дерево A R
| 10 |
Удаление
|
Вставка
|
1|
а 1а 2 10 •
11 а2
• поддерева
а1
поддерева • а1
• а2
•
а3а 4
11 а 3а 4
а 3а 4
а 3а 4
а3а4 2
Дерево С R
... 1 — i:=nr(T0A)B 2 — u(T0C= TNχT):=i
в)
Дерево B R • 10
а 1а 2
Дерево A R Удаление а 1 поддерева
Дерево
B
R
′ Вставка
• поддерева
а2
Дерево B R″
•
2 а2
1
Дерево A R а1
Дерево С R ...
1 — i:=nr(L0A) 2 — j:=u(LiB) B 3 — u(T0C= TNχT):=j
3
Рис. 2
&
C1 13 7
0 РгТКУВ 0
310=0... 0112
1 . .
.
1 . .
.
1 1 0
1 2 4
DC D2n 1
n-1 L
+1
n-1 D3 1
0 2n
D2 0
& &
-1 1
D1 1
&
1 D0
&
&0
0 0 1 1
&1 2 wa
&
ΧT 0
&3 14
В.УЭ (у)
wd
d
1 0
& &
& 0
& 0
5
( )g
↑ 0
ΧT
+1 CD
0& 0
6
0 1
РPгNχT
0 1
..
..
..
n-1 n-1
L
1 ε1 8
1 ρ СМНП 1
1 Cw 1&
0 & 1
9 10
1
РгТКУС 27
&1
11 DC
12
0 RG 0 1 1i
ra С.ТУ rd
wd
1
& 0
1
РгТКЛС
&
.. ..
18 19
20
C2
1
.. n-1 n-1
CD
SUM
DC
0 DSL
C
wa В.ТУ
C3
26 1 DSR 25 C
εT Cw
L
СВСН
& 0
1
0
0 РгТКЛВ 0 11 .. .. .. n-1 n-1
L
+1
-1
14
СМНП 2 & 1 15
1 &
wa
& 16 17
1
В.УЭ (нл)
wd
d ΧL
Cw
22 SUM
ra
С.СП (у)
rd
rd
ra С.МВ
d МВ0
( )СВМЕ g1↓ ΧL
ra
С.СП (нл)
rd
50 1
&1
21
&
23 &1
&
24 1
39 1 σC
29 εL 1
48
0 РгПСП 0
45
1 1&& ..
. . 44 ..
n-1 n-1
L
32 1
31 &1
&
28 &1
&
wa
wd В.СП Cw (у)
ra
rd
Cw wd
В.МВ wa ra
rd
30 SUM
&1
46
&
&1
& 47
1 49
33 &1
А.ТС (у)
d δ0+
&
А.НС (у)
d НС0
DC
34 РгТКУА
37 1
38 σA
А.НС (нл)
d НС0
35 DC
ra
В.СП (нл)
rd
wd
wa В.СП Cw (нл)
owd
ad
43 1κ
& 40
& 1 36
& 41
& 42
& СП’
C4
Рис. 3
70 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
Коммутатор 33 обеспечивает формирование на своем выходе значения предка корня подставляемого дерева в зависимости от типа соответствия. Дешифратор 34 обеспечивает преобразо-
вание номера узла, r-изоморфного корневому узлу дерева AR , из двоичного кода в унитарный. Дешифратор 35 обеспечивает преобразование номера набора листьев, r-изоморфного
нулевому набору листьев дерева AR , из двоичного кода в унитарный. Коммутатор 36 обеспечивает формирование на своем выходе значения номера узла-предка для корня подставляемо-
го дерева. Регистр 37 хранит значение текущего числа узлов дерева AR , используемое для формирования значения признака σA на выходе элемента ИЛИ 38, подаваемого на вход ком-
мутатора 36. Элемент ИЛИ 39 используется для формирования признака σC . Элемент ИЛИ 43 обеспечивает формирование признака κ , используемого в совокупности с элементами
40—42, 44 и 45 для управления прохождением синхросигнала c4 . Регистр-защелка 48 ис-
пользуется для хранения значения первой свободной позиции, формируемого на выходе схемы выделения младшей единицы (СВМЕ). Элемент ИЛИ 49 обеспечивает прохождение синхросигнала записи к элементу В.СП(нл) в зависимости от обрабатываемой ситуации. Блок элементов ИЛИ 50 используется при объединении уже имеющегося набора листьев с единст-
венным набором листьев, входящим в состав подставляемого дерева CR .
Вычислительные затраты на выполнение отдельных элементарных операций рассмот-
ренного выше алгоритма приведены в табл. 2.
Таблица 2
Действие
Программная реализация, Аппаратная реализация,
шаг, не более
шаг, не более
Определение значений вектора ΧT
NT 1
Определения значения
N
T χ
NT 1
Копирование узлов
Определение значений вектора ΧL Определение младшей свободной позиции в ΧL
NT NL NL
NT 1 1
Копирование наборов листьев
NL NL
Корректировка СП
NL 1
Итого
3NT
+ 2NL
+
N
2 L
NT + NL + 4
Анализ показывает, что при использовании предлагаемого устройства, по сравнению с программной реализацией, преимущество по времени обработки составляет
3NT + 2NL NT + NL
+ NL2 +4
≈
NR
раз,
где NR = NL + NT , что достигается благодаря использованию схем маскировки неисполь-
зуемых позиций (СМНП 1 и 2) и схемы выделения старшего нуля (СВСН), а также возможности ассоциативного поиска информации в памяти акселератора [7, 10].
СПИСОК ЛИТЕРАТУРЫ
1. Организация и синтез микропрограммных мультимикроконтроллеров / И. В. Зотов, В. А. Колосков, В. С. Титов и др. Курск: КурскГТУ, 1999. 368 с.
2. Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
71
3. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917.
4. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Свид. об официальной регистрации программы для ЭВМ. № 2005613091 от 28.11.05.
5. Ватутин Э. И., Волобуев С. В., Зотов И. В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Параллельные вычисления и задачи управления (PACO’08). М.: ИПУ РАН, 2008. С. 643—685.
6. Ватутин Э. И., Зотов И. В. Поиск базового сечения в задаче разбиения параллельных алгоритмов / Курск. гос. техн. ун-т. Курск, 2003. 30 с. Деп. в ВИНИТИ. 24.11.03, № 2036-B2003.
7. Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов логического управления // Изв. вузов. Приборостроение. 2009. Т. 52, № 2. С. 37—45.
8. Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 11. С. 49—56.
9. Ватутин Э. И., Зотов И. В., Титов В. С. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселераторов // Изв. КурскГТУ. 2008. № 4 (25). С. 32—39.
10. Ватутин Э. И. Однородная среда электронной модели дерева для аппаратно-ориентированной обработки R-выражений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2008). Курск: КурскГТУ, 2008. Ч. 1. С. 90—92.
Эдуард Игоревич Ватутин Игорь Валерьевич Зотов Виталий Семенович Титов Муджиб Мохаммед Ахья Аль-Ашвал
Сведения об авторах — канд. техн. наук; Курский государственный технический универ-
ситет, кафедра вычислительной техники; E-mail: evatutin@rambler.ru — д-р техн. наук, профессор; Курский государственный технический университет, кафедра вычислительной техники; E-mail: zotovigor@yandex.ru — д-р техн. наук, профессор; Курский государственный технический университет, кафедра вычислительной техники; E-mail: titov-kstu@rambler.ru — аспирант; Курский государственный технический университет, кафедра вычислительной техники; E-mail: mogibm2007@yandex.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 14.04.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
УДК 004.384:004.272:004.414.2
Э. И. ВАТУТИН, И. В. ЗОТОВ, В. С. ТИТОВ, М. М. АЛЬ-АШВАЛ
РЕАЛИЗАЦИЯ ОПЕРАЦИИ ВСТАВКИ ПОДДЕРЕВА ПРИ АППАРАТНО-ОРИЕНТИРОВАННОЙ ОБРАБОТКЕ R-ВЫРАЖЕНИЙ
Рассматривается устройство, позволяющее реализовать операцию вставки поддерева в дерево при аппаратно-ориентированной обработке R-выражений, возникающей при выполнении эквивалентных преобразований параллельных алгоритмов.
Ключевые слова: логический мультиконтроллер, параллельный алгоритм логического управления, разбиение, оптимизация, R-выражение, ориентированное дерево, спецпроцессор.
Построение систем логического управления, ориентированных на реализацию параллельных управляющих алгоритмов в базисе логических мультиконтроллеров (ЛМК), требует декомпозиции комплексных параллельных алгоритмов теоретически неограниченной сложности на множество частных алгоритмов ограниченной сложности [1]. Получение оптимального набора частных алгоритмов (разбиения) представляет собой сложную комбинаторную задачу, решение которой возможно лишь с помощью эвристических алгоритмов. Качество решения этой задачи существенно влияет на аппаратную сложность ЛМК и определяет, в конечном счете, время выполнения алгоритма. Эффективным путем решения данной задачи является параллельно-последовательный метод декомпозиции [2—5].
Один из ключевых этапов параллельно-последовательной декомпозиции — построение множества сечений, покрывающего все вершины исходного алгоритма. Формирование сечений осуществляется посредством выполнения трудоемких операций подстановки над множеством так называемых R-выражений, описывающих алгоритм управления. Как показывают исследования, упрощение и ускорение этих операций возможно путем их сведения к действиям над деревьями. Такие действия, в свою очередь, допускают разбиение на ряд более простых (элементарных) операций [6]. Схематично операции подстановки могут быть представлены следующим образом:
⎧⎪⎪⎪⎪⎪⎩⎨ij::
XR AR
→ →
BR CR
⇒
i : X R → BR′ (u-подстановка);
⎧⎪⎪⎪⎪⎪⎨⎩ij::
CR BR
→ →
AR XR
⇒
j : BR′ → X R (d-подстановка),
где X R — некоторое R-выражение, не участвующее в подстановке; BR′ — R-выражение, получаемое из R-выражения BR после удаления поддерева AR и вставки вместо него дерева CR .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
64 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
Методика практической реализации операций над R-выражениями, а также представление их в виде деревьев, допускающее преобразование в табличный вид, приведены в работах [7, с. 38; 8]. Здесь напомним следующее: каждый элемент а дерева X, представленного совокупностью наборов листьев L1X , L2X ,..., LXNL( X ) , узлов T1X ,T2X ,...,TNXT ( X ) и связей между ними, кодируется набором полей. С учетом ряда особенностей обработки, наборы листьев и узлы дерева кодируются отдельно. Узлы дерева представлены следующими полями: тип узла
( ( ))(ТУ) — параллельный или альтернативный t TiX ; ссылка на предка (СП) — номер узла-
( ( ))предка u TiX ; номер соответствия (НС) — номер изоморфного эквивалента в соседнем
( ( ))дереве nr TiX ; тип соответствия (ТС) — отсутствующее, полное или частичное соответст-
( ( ))вие Δ TiX ; наборам листьев дерева при этом соответствуют поля множества вершин (МВ) —
двоичный вектор с единичными битами в позициях, соответствующих номерам присутствующих в наборе вершин, а также перечисленные выше поля СП, НС и ТС.
Табличное представление R-выражений подчиняется ряду следующих требований [8]. 1. Корень дерева хранится в позиции с номером 0. Значение поля СП корня указывает на заведомо несуществующий элемент дерева. 2. Для каждого узла дерева его потомки хранятся в позициях с номерами, превосходящими номер позиции самого узла (при этом порядок хранения потомков не важен). 3. Все узлы и наборы листьев дерева хранятся в смежных позициях (без „пропусков“). 4. Каждому узлу дерева соответствует не более одного дочернего набора листьев, в дереве не может быть „пустых“ наборов листьев, не содержащих вершин. 5. Если дерево представлено единственным набором листьев (без узлов), то в составе этого набора может быть всего один элемент (одна вершина алгоритма управления). 6. В составе корректного дерева не может быть совпадения типа узлов у любой пары смежных узлов. 7. Дерево содержит, по меньшей мере, один набор листьев. Число узлов дерева может быть нулевым. В настоящей статье предложена аппаратная реализация операции вставки поддерева. Она выполняется непосредственно после операции удаления поддерева, r-изоморфного [7, 8] дереву AR , в результате которого может быть нарушено требование № 3. Рассматриваемая операция состоит из двух стадий: на первой производится копирование элементов дерева, на второй — настройка связей для скопированных элементов. В результате выполнения операции копирования элементов дерева C R должны быть учтены требования № 2 и 4. При этом в общем случае требования № 3 и 6 в результате выполнения операции вставки поддерева не выполняются, что обусловливает необходимость удаления „пропусков“ непосредственно после рассматриваемой операции. Общие принципы выполнения первой стадии продемонстрированы на рис. 1 (белые квадраты — свободные позиции, темные квадраты — занятые позиции, крестами помечены удаленные элементы, стрелками обозначены операции копирования элементов дерева). На первой стадии при копировании узлов дерева (см. рис. 1, а) необходимо соблюдение требования № 2 корректности дерева. Наиболее простой способ обеспечить выполнение этого требования — последовательная вставка „новых“ узлов, начиная с позиции с номером, превосходящим номера уже имеющихся узлов дерева BR , с сохранением порядка их следо-
вания. Номер такой позиции может быть определен как NχT = g0↑ (ΧT ) +1, где
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
65
( ( ) ( ) ( )) ( )ΧT (B) = χ T0B , χ T1B , ..., χ TnB−1 — вектор двоичных признаков χ TiX свободных пози-
ций среди узлов дерева BR , g0↑ (Χ) — функция выделения позиции старшего нуля в двоич-
ном векторе Χ [9]. Копирование наборов листьев (см. рис. 1, б) не нарушает требований корректности дерева и поэтому может быть осуществлено непосредственно в первую свободную
ячейку с младшим номером, который определяется как g1↓ (ΧL ) , где
( ( ) ( ) ( )) ( )ΧL (B) = χ LB0 , χ L1B , ..., χ LBm−1 — вектор двоичных признаков χ LiX свободных пози-
ций среди наборов листьев дерева BR , g1↓ (Χ) — функция выделения позиции младшей еди-
ницы в двоичном векторе Χ [9]. Подобный способ копирования наборов листьев уменьшает число действий, затрачиваемых впоследствии на ликвидацию пустых позиций.
При добавлении каждого нового элемента в дерево BR также необходимо инкрементиро-
( ) ( )вать значение NT BR (при добавлении узла) или NL BR (при добавлении набора листьев).
а) Узлы дерева BR (после удаления поддерева)
0
б) Наборы листьев BR (после удаления поддерева) 0
Наборы листьев дерева СR 0
1 11
2 22
3 33
4 44
5 6 7 NχT 8 9
Узлы дерева CR
i′ = i + NχT
0 1
2
3
5 6 7 8 9
5 6
N Lmax
10 4 10 i′ = g1↓ ( ΧL )
11 5 11
( )ΧL =
χ1L
,
χ
L 2
,
...,
χ
L N
L
max
−1
… … … …
NTmax
NTmax
N Lmax
Рис. 1
Вторая стадия начинается с корректировки значений полей СП „новых“ элементов де-
рева BR , скопированных в него из дерева CR . Прежде всего корректировке подвергаются
( ) ( )значения
полей
СП,
обозначаемые
как
u (⋅) ,
„новых“
элементов:
u LBi
:= u LiB
+
N
T χ
,
( ) ( )u
T
B j
:= u
T
B j
+ NχT . Подобные формулы корректировки объясняются достаточно просто:
нулевой
узел
(корень)
дерева
CR
попадает
в
дереве
BR
в
позицию
с
номером
N
T χ
,
первый
—
в позицию
N
T χ
+1 и т.д.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
66 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
После выполнения указанных корректировок необходимо настроить связь скопирован-
ного поддерева из „новых“ элементов с уже присутствующими элементами дерева BR (точ-
нее, с узлом, r-изоморфным корню дерева AR , при частичном соответствии, или его предком при полном соответствии). Детали реализации настройки связи между деревьями представлены в табл. 1 и проиллюстрированы на рис. 2, где а, б, в соответствуют трем различным случаям выполнения операции подстановки, приведенным в таблице.
Таблица 1
Наличие в дереве AR узлов
(σ A )
ТС корня дерева AR
(Δ(T0A ))
Формула обновленного значения поля СП корневого элемента скопированного дерева
Полное: Δ=11 1
Частичное: Δ=10
x = u (⎜⎜⎝⎜⎛⎜TnBr T0A) ⎟⎟⎟⎠⎟⎞⎟
( )x = nr T0A
0 Полное, частичное: Δ= 1*
x
=
u
⎜⎜⎜⎛⎝⎜
LB
nr
(
L0A
)
⎟⎞⎟⎠⎟⎟⎟
Особым случаем, не указанным в табл. 1, является ситуация, когда дерево CR не содержит узлов, что обозначим нулевым значением двоичного признака σC . В этом случае при выполнении описанных выше действий возможно нарушение требования № 4, если у элемента дерева BR , на который производится настройка поля СП добавляемого набора листьев LC0
дерева CR , уже есть дочерний набор листьев LBk . Правильным действием в подобной ситуа-
ции является добавление элементов вектора LC0 к элементам вектора LBk : LBk := LBk ∪ LC0 вместо добавления еще одного набора листьев.
Алгоритм преобразования выполняется следующим образом.
1. Если дерево CR не содержит узлов (σC = 0) и узел дерева BR с номером х, опреде-
ляемым согласно табл. 1, имеет дочерний набор листьев LBk (что в дальнейшем будем обозна-
( )чать с использованием двоичного признака κ TiX , равного в данном случае единице), пе-
рейти к п. 7.
2. Определить значение
N
T χ
:=
g0↑ (ΧT
)+1.
Если
ΧT = 00...0
(все элементы в таблич-
ном представлении заняты), установить признак ошибки ε1 := 1 и перейти к п. 8, в противном
случае установить признак ε1 := 0 .
( )3. Копирование узлов: скопировать узлы TiC дерева CR , i = 0, NT C R −1, в смежные
позиции дерева BR , начиная с позиции NχT . При недостаточном количестве свободных по-
зиций сформировать признак ошибки εT := 1 и перейти к п. 8, в противном случае положить εT := 0 .
4. Копирование наборов листьев: скопировать наборы листьев LCi дерева CR ,
( )i = 0, NL C R −1 , в дерево BR , причем i-й набор листьев дерева CR копируется в позицию ( )k = g1↓ (ΧL ) , а сама позиция помечается как используемая: χ LBk := 0 . В случае если на ка-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
67
ком-либо из шагов ΧL = 00...0 (свободной позиции нет), установить признак ошибки εL := 1 и перейти к п. 8, в противном случае положить εL := 0 .
5. Увеличить значения текущего количества узлов и текущего количества листьев дере-
( ) ( ) ( ) ( ) ( ) ( )ва BR : NT BR := NT BR + NT C R , NL BR := NL BR + NL C R .
6. Модифицировать значения полей СП „новых“ элементов дерева BR , скопированных
( ) ( ) ( ) ( )из дерева
CR , за исключением корневого, как
u
LiB
:= u
LiB
+
N
T χ
,
u
T
B j
:= u
T
B j
+ NχT .
Для „нового“ элемента дерева BR , соответствующего корневому элементу дерева CR , установить значение поля СП согласно табл. 1. Перейти к п. 8.
7. Осуществить объединение наборов листьев: LBk := LBk ∪ LC0 .
8. Конец алгоритма. Схема, реализующая предложенный алгоритм, приведена на рис. 3 (сокращения, использованные в схеме, аналогичны принятым в работе [7]). Регистр 1 хранит текущее количе-
ство узлов дерева BR и инкрементируется по мере добавления в дерево BR новых узлов. Коммутатор 2 используется для выбора значения вектора, подаваемого на вход элемента В.УЭ(у) [7, 10] в качестве адреса записи. Элементы 3 и 4 используются при инициализации значений вектора В.УЭ(у). Шифратор 5 предназначен для преобразования значения номера свободной позиции с выхода схемы выделения старшего нуля (СВСН) из унитарного в двоичное представление, сохраняющегося в регистре 6. Элемент задержки 7 обеспечивает запись значения в регистр 6 только по окончании его формирования на выходе схемы СВСН. Эле-
мент ИЛИ—НЕ 8 используется для формирования сигнала ошибки ε1 . Регистры 9 и 27 пред-
назначены для хранения числа узлов и наборов листьев дерева CR соответственно. Коммутатор 10 в совокупности с дешифратором 11 обеспечивают запись в сдвиговый регистр 12 значения текущего числа элементов (наборов листьев или узлов) в унитарном коде в зависимо-
сти от этапа обработки. Элемент И 13 запрещает прохождение синхросигнала c1 при инициализации значения В.УЭ(нл) на входы элемента В.УЭ(у) и регистра 6. Регистр 14 хранит
текущее количество наборов листьев дерева BR , инкрементируемое по мере добавления новых наборов листьев. Коммутатор 15 в совокупности с элементами 16 и 17 обеспечивает ини-
циализацию значения вектора УЭ наборов листьев дерева BR (в ходе дальнейшей обработки значения вектора УЭ изменяются согласно алгоритму обработки с использованием перечисленных элементов). Шифратор 18 используется для преобразования значения текущего рассматриваемого элемента из унитарного кода в двоичный. Сумматор 19 обеспечивает формирование на его выходе значения NTχ + i очередной свободной позиции и признака ошибки εT . Дешифратор 20 преобразует значение NTχ + i в унитарный код для его дальнейшего использования в качестве адреса записи. Коммутаторы 21, 23, 28, 31, 46 и 47 используются для
выбора значения элемента дерева BR модифицируемого элемента в зависимости от этапа алгоритма и особенностей обработки. Сумматор 22 обеспечивает формирование обновленного значения поля СП копируемого элемента. Элемент ИЛИ 24 служит для прохождения синхросигнала записи на вход элемента В.СП(у). Элементы 25 и 26 обеспечивают прохождение син-
хросигналов c2 и c3 на вход регистра 12. Элемент ИЛИ—НЕ 29 служит для формирования
признака ошибки εL . Сумматор 30 используется для корректировки значения поля СП копируемого набора листьев. Элемент ИЛИ 32 обеспечивает прохождение синхросигнала на вход элемента В.МВ, активирующего модификацию поля МВ в зависимости от ситуации.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
а)
Дерево B R
Дерево A R
| a 1а 2
11 •
Удаление
•
11
поддерева а 3а 4
а3а 4
Дерево B R ′ |
а 1а 2
• а 3а 4
Вставка поддерева
Дерево B R″
|2
а 1а 2
•
а 3а 4
Дерево A R 1•
а3а4
3
Дерево СR ...
1 — i:=nr(T0A) 2 — j:=u(TiB) B 3 — u(T0C= TNχT):=j
б) Дерево B R
Дерево A R
Дерево B R ′
Дерево B R″
Дерево A R
| 10 |
Удаление
|
Вставка
|
1|
а 1а 2 10 •
11 а2
• поддерева
а1
поддерева • а1
• а2
•
а3а 4
11 а 3а 4
а 3а 4
а 3а 4
а3а4 2
Дерево С R
... 1 — i:=nr(T0A)B 2 — u(T0C= TNχT):=i
в)
Дерево B R • 10
а 1а 2
Дерево A R Удаление а 1 поддерева
Дерево
B
R
′ Вставка
• поддерева
а2
Дерево B R″
•
2 а2
1
Дерево A R а1
Дерево С R ...
1 — i:=nr(L0A) 2 — j:=u(LiB) B 3 — u(T0C= TNχT):=j
3
Рис. 2
&
C1 13 7
0 РгТКУВ 0
310=0... 0112
1 . .
.
1 . .
.
1 1 0
1 2 4
DC D2n 1
n-1 L
+1
n-1 D3 1
0 2n
D2 0
& &
-1 1
D1 1
&
1 D0
&
&0
0 0 1 1
&1 2 wa
&
ΧT 0
&3 14
В.УЭ (у)
wd
d
1 0
& &
& 0
& 0
5
( )g
↑ 0
ΧT
+1 CD
0& 0
6
0 1
РPгNχT
0 1
..
..
..
n-1 n-1
L
1 ε1 8
1 ρ СМНП 1
1 Cw 1&
0 & 1
9 10
1
РгТКУС 27
&1
11 DC
12
0 RG 0 1 1i
ra С.ТУ rd
wd
1
& 0
1
РгТКЛС
&
.. ..
18 19
20
C2
1
.. n-1 n-1
CD
SUM
DC
0 DSL
C
wa В.ТУ
C3
26 1 DSR 25 C
εT Cw
L
СВСН
& 0
1
0
0 РгТКЛВ 0 11 .. .. .. n-1 n-1
L
+1
-1
14
СМНП 2 & 1 15
1 &
wa
& 16 17
1
В.УЭ (нл)
wd
d ΧL
Cw
22 SUM
ra
С.СП (у)
rd
rd
ra С.МВ
d МВ0
( )СВМЕ g1↓ ΧL
ra
С.СП (нл)
rd
50 1
&1
21
&
23 &1
&
24 1
39 1 σC
29 εL 1
48
0 РгПСП 0
45
1 1&& ..
. . 44 ..
n-1 n-1
L
32 1
31 &1
&
28 &1
&
wa
wd В.СП Cw (у)
ra
rd
Cw wd
В.МВ wa ra
rd
30 SUM
&1
46
&
&1
& 47
1 49
33 &1
А.ТС (у)
d δ0+
&
А.НС (у)
d НС0
DC
34 РгТКУА
37 1
38 σA
А.НС (нл)
d НС0
35 DC
ra
В.СП (нл)
rd
wd
wa В.СП Cw (нл)
owd
ad
43 1κ
& 40
& 1 36
& 41
& 42
& СП’
C4
Рис. 3
70 Э. И. Ватутин, И. В. Зотов, В. С. Титов, М. М. Аль-Ашвал
Коммутатор 33 обеспечивает формирование на своем выходе значения предка корня подставляемого дерева в зависимости от типа соответствия. Дешифратор 34 обеспечивает преобразо-
вание номера узла, r-изоморфного корневому узлу дерева AR , из двоичного кода в унитарный. Дешифратор 35 обеспечивает преобразование номера набора листьев, r-изоморфного
нулевому набору листьев дерева AR , из двоичного кода в унитарный. Коммутатор 36 обеспечивает формирование на своем выходе значения номера узла-предка для корня подставляемо-
го дерева. Регистр 37 хранит значение текущего числа узлов дерева AR , используемое для формирования значения признака σA на выходе элемента ИЛИ 38, подаваемого на вход ком-
мутатора 36. Элемент ИЛИ 39 используется для формирования признака σC . Элемент ИЛИ 43 обеспечивает формирование признака κ , используемого в совокупности с элементами
40—42, 44 и 45 для управления прохождением синхросигнала c4 . Регистр-защелка 48 ис-
пользуется для хранения значения первой свободной позиции, формируемого на выходе схемы выделения младшей единицы (СВМЕ). Элемент ИЛИ 49 обеспечивает прохождение синхросигнала записи к элементу В.СП(нл) в зависимости от обрабатываемой ситуации. Блок элементов ИЛИ 50 используется при объединении уже имеющегося набора листьев с единст-
венным набором листьев, входящим в состав подставляемого дерева CR .
Вычислительные затраты на выполнение отдельных элементарных операций рассмот-
ренного выше алгоритма приведены в табл. 2.
Таблица 2
Действие
Программная реализация, Аппаратная реализация,
шаг, не более
шаг, не более
Определение значений вектора ΧT
NT 1
Определения значения
N
T χ
NT 1
Копирование узлов
Определение значений вектора ΧL Определение младшей свободной позиции в ΧL
NT NL NL
NT 1 1
Копирование наборов листьев
NL NL
Корректировка СП
NL 1
Итого
3NT
+ 2NL
+
N
2 L
NT + NL + 4
Анализ показывает, что при использовании предлагаемого устройства, по сравнению с программной реализацией, преимущество по времени обработки составляет
3NT + 2NL NT + NL
+ NL2 +4
≈
NR
раз,
где NR = NL + NT , что достигается благодаря использованию схем маскировки неисполь-
зуемых позиций (СМНП 1 и 2) и схемы выделения старшего нуля (СВСН), а также возможности ассоциативного поиска информации в памяти акселератора [7, 10].
СПИСОК ЛИТЕРАТУРЫ
1. Организация и синтез микропрограммных мультимикроконтроллеров / И. В. Зотов, В. А. Колосков, В. С. Титов и др. Курск: КурскГТУ, 1999. 368 с.
2. Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51—62.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9
Реализация операции вставки поддерева
71
3. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO’04). М.: ИПУ РАН, 2004. С. 884—917.
4. Ватутин Э. И., Зотов И. В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Свид. об официальной регистрации программы для ЭВМ. № 2005613091 от 28.11.05.
5. Ватутин Э. И., Волобуев С. В., Зотов И. В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Параллельные вычисления и задачи управления (PACO’08). М.: ИПУ РАН, 2008. С. 643—685.
6. Ватутин Э. И., Зотов И. В. Поиск базового сечения в задаче разбиения параллельных алгоритмов / Курск. гос. техн. ун-т. Курск, 2003. 30 с. Деп. в ВИНИТИ. 24.11.03, № 2036-B2003.
7. Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении параллельных алгоритмов логического управления // Изв. вузов. Приборостроение. 2009. Т. 52, № 2. С. 37—45.
8. Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 11. С. 49—56.
9. Ватутин Э. И., Зотов И. В., Титов В. С. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселераторов // Изв. КурскГТУ. 2008. № 4 (25). С. 32—39.
10. Ватутин Э. И. Однородная среда электронной модели дерева для аппаратно-ориентированной обработки R-выражений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание — 2008). Курск: КурскГТУ, 2008. Ч. 1. С. 90—92.
Эдуард Игоревич Ватутин Игорь Валерьевич Зотов Виталий Семенович Титов Муджиб Мохаммед Ахья Аль-Ашвал
Сведения об авторах — канд. техн. наук; Курский государственный технический универ-
ситет, кафедра вычислительной техники; E-mail: evatutin@rambler.ru — д-р техн. наук, профессор; Курский государственный технический университет, кафедра вычислительной техники; E-mail: zotovigor@yandex.ru — д-р техн. наук, профессор; Курский государственный технический университет, кафедра вычислительной техники; E-mail: titov-kstu@rambler.ru — аспирант; Курский государственный технический университет, кафедра вычислительной техники; E-mail: mogibm2007@yandex.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 14.04.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 9