РАСПРЕДЕЛЕНИЕ ПОТОКОВ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В СИСТЕМАХ РАСПОЗНАВАНИЯ ОБРАЗОВ В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ
20 И. М. Гостев, А. Г. Подгорбунский
УДК 519.92:681.3(07)
И. М. ГОСТЕВ, А. Г. ПОДГОРБУНСКИЙ
РАСПРЕДЕЛЕНИЕ ПОТОКОВ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В СИСТЕМАХ РАСПОЗНАВАНИЯ ОБРАЗОВ В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ
Рассматриваются два алгоритма управления видеопотоками в распределенной системе по обработке изображений и распознаванию образов на основе теории графов. Представлен алгоритм управления распределенной системой посредством контроллера потока. Приведено математическое описание статического (граф определен до начала работы системы) и динамического (граф может быть перестроен в процессе работы системы в зависимости от особенностей видеопотока) распределения информационных потоков.
Ключевые слова: алгоритм управления, графическая информация, распознавание объектов, реальный масштаб времени.
Введение. Несмотря на постоянное повышение быстродействия компьютеров построение систем обработки изображений и распознавания образов в реальном масштабе времени сопряжено с преодолением ряда проблем. В работе [1] показано, что быстродействие вычислительной системы для обработки видеопотока должно быть пропорциональным размеру изображения, для телевизионного формата оно превышает мощность одного компьютера примерно в 25—30 раз. Для решения этой проблемы были разработаны параллельные алгоритмы, позволяющие реализовать такую систему в распределенной среде, при этом каждый из элементов системы выполняет свою операцию по обработке изображения и распознавания образов. Для управления всей системой обработки видеопотока и распознавания объектов используется контроллер, который распределяет задания по вычислительным узлам системы, осуществляет контроль и синхронизацию их выполнения.
В работах [1, 2] была предложена и развита идея построения распределенной системы обработки и распознавания изображений в режиме реального времени, основанной на принципах конвейера и разбиения потока на участки. В настоящей работе рассматривается способ моделирования параллельных вычислений, основанный на применении ориентированных графов [3].
Математическая модель процессов. Разделим методы распределения потока на статические и динамические. В первом случае маршрут потоков информации определяется на этапе начальной инициализации системы и далее остается неизменным; размер фрагмента потока, его маршрут и методы обработки заранее определены. При динамическом распределении маршрут и размеры фрагментов определяются на стадии обработки.
Рассмотрим односвязный ориентированный ациклический граф, имеющий один исток и один сток, вершинами которого являются узлы вычислительной сети, реализованные в виде экземпляров метода, а дугами — каналы передачи потока. Методом назовем процедуру обработки изображения, реализованную в виде библиотечной функции. Входными данными метода будут фрагменты изображения и его параметры, необходимые для процедуры обработки. В результате работы метода получаются выходное изображение и/или некоторые другие данные, полученные в результате применения процедуры, формат которых зависит от конкретного метода. С помощью методов осуществляются разделение исходного потока на фрагменты, их параллельная обработка и последующее объединение нескольких потоков в один — результирующий. Всем процессом управляет компонент, называемый „контроллером потока“.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распределение потоков графической информации в системах распознавания образов 21
Поскольку процесс обработки изображения представляет собой последовательность (цепочку) нескольких методов, то в вычислительной сети каждому методу будет сопоставлен один или несколько узлов, его реализующих — экземпляров. Совокупность одинаковых экземпляров образует ярус сети, соответствующий данному методу цепочки. Входная информация поступает на некоторый узел только с узлов яруса, соответствующего предыдущему методу цепочки. Все выходы узла направлены только на узлы яруса, соответствующего следующему методу в цепочке. Первый и последний ярусы содержат по одному узлу. Каждый метод характеризуется относительной вычислительной сложностью процедуры, началом и
( )концом смещения фрагмента изображения по высоте y− , y+ и начальными условиями. На( )пример, смещение по высоте y− , y+ означает, что для метода l с параметрами начала и
конца фрагмента [s1, s2 ] необходим фрагмент l[s1 − y− , s2 + y+ ] . Алгоритм построения вычислительной среды. Статическое распределение потока.
Рассмотрим алгоритм статического распределения потока. Пусть исходный поток представляет собой одно длинное изображение — „ленту“. Фрагмент потока — непрерывный участок изображения, содержащий целое число строк. Промежуточные потоки состоят из последовательности фрагментов. Если поток состоит из фрагментов одинаковой длины, следующих через равные промежутки, то он может быть описан схемой потока.
Схема фрагмента потока представляет собой сочетание S, L, P где S — начальная
строка первого фрагмента, L — длина каждого фрагмента в строках, P — промежуток от конца предыдущего фрагмента до начала следующего. Таким образом, S, L, P определяет
последовательность фрагментов
[S + (L + P)i, S + (L + P)i + L], i ∈ N .
Две схемы называются смежными, когда при объединении двух соседних фрагментов их описание (состоящее из всех фрагментов первого и второго потока) также определяется схемой потока. Результирующая схема потока носит название объединенной. Символом
Ξi ( S, L, P ) обозначается схема потока, скорректированная в соответствии со смещениями
по y для i-го метода (необходимого методу на входе, чтобы производить поток S, L, P на
выходе):
( )Ξi S, L, P = S − yi− , L + yi− + yi+ , P − yi− − yi+ .
Алгоритм состоит из двух шагов — прямого и обратного. На первом происходят определение количества вершин в каждом ярусе и построение связей между ними путем равномерного последовательного разделения потока. На втором шаге происходит коррекция соединений и разметки с целью исключения каналов, по которым передаются очень малые относительно среднего потока на ярусе фрагменты.
Входом алгоритма являются цепочка методов M1, …, M N , относительная вычислительная сложность c1, …, cN , пропускная способность эталонного метода qe , требуемая пропускная способность цепочки q ; выходом — построенный граф вычислительной сети
G = {V , E} , ребра и вершины которого размечены схемами потоков M → { S, L, P },
M ' → { S, L, P }.
Шаг 1. Для каждого i ∈[1, N ] определить ярус Gi = {Vi , ∅} , где
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
22 И. М. Гостев, А. Г. Подгорбунский
Vi
=
⎧⎨vik ⎩
|
k
=
1...
⎡ ⎢⎢
qe q
c
⎤ ⎥⎥
⎫ ⎬ ⎭
— набор упорядоченных узлов методов, являющихся экземплярами метода Mi .
∪Положить V = i∈[1,n]Vi ; E = ∅ . Приписать истоку схему потока 0, L, 0 , где L — ис-
ходная длина блока, задаваемая контроллером потока на этапе конфигурации. Положить
{( )}M = ∅, M ′ = v11, 0, L, 0 , для каждого узла vik разметить его следующим образом:
⎢ ⎢ ⎣
k− | Vi
1⎥
|
⎥ ⎦
,
⎢k ⎣⎢| Vi
⎥ |⎥⎦
−
⎢ ⎢ ⎣
k+ | Vi
1⎥
|
⎥ ⎦
,
L
−
⎢k ⎣⎢| Vi
⎥ |⎦⎥
+
⎢ k +1⎥
⎢ ⎣
|
Vi
|
⎥ ⎦
.
Для каждой пары узлов vik и vik+′1 , i ∈[1, N −1], k ∈ [1,| Vi |] , k ′ ∈[1,| Vi+1 |] в случае если
( )M ′(vik ) ∩ Ξi (M ′(vik+′1)) ≠ ∅ , добавить дугу между узлами E = E ∪ vik , vik+′1 и пометить ее схе-
мой-пересечением:
{(( ) ( ) ( ( )))}M = M ∪ vik ,vik+′1 , M ′ vik ∩ Ξi M ′ vik+′1 .
Шаг 2. Для каждого яруса Vi , i = N , ..., 2 для каждого узла vik ∈Vi , k ∈ [1,| Vi |] .
а) Убедиться, что объединенная схема выходов совпадает со схемой узла:
{ ( )} ( )∪( )vik ,v ∈E M vik ,v = M ′ vik .
В случае, если это не так и объединенная схема включает схему узла, то вычислить множество недостающих схем
{ ( )} ( ( ))∪( )vik ,v ∈E M vik ,v Ξi M ′ vik
и каждый недостающий элемент этого множества прибавить к одной их схем входящих ребер узла, имеющих схему, смежную с недостающей, и наибольшую длину.
б) Удалить входные дуги, длина схемы которых меньше определенного порога, и схемы этих дуг приписать дугам наибольшей длины, имеющим смежные схемы.
Динамическое распределение потока. При динамическом распределении потока между обрабатывающими узлами маршрут, по которому пройдет конкретный фрагмент изображения, определяется на стадии выполнения. При этом из-за смещений по высоте для обработки данного фрагмента может потребоваться несколько строк предыдущего или последующего фрагмента, непосредственно прилегающего к данному. А так как заранее неизвестно, какие именно фрагменты пройдут через данный экземпляр метода, невозможно сказать, требуется сохранять этот фрагмент или нет. Кроме того, чтобы обеспечить обработку данного фрагмента с учетом смещений по высоте, требуется разместить предыдущий и последующий фрагменты непосредственно до и после него. Указанные факторы усложняют процедуру управления памятью и требуют реализации дополнительных условий маршрутизации на этапе обработки потока, включающих взаимодействие с контроллером потока, который координирует в этом случае маршрутизацию. Это противоречит одной из основных концепций, положенных в основу проектирования системы, согласно которой взаимодействие контроллера потока с методами на этапе обработки должно быть минимальным. Однако обе проблемы могут быть решены с помощью передачи избыточного количества фрагментов, так чтобы каждый фрагмент на каждом ярусе сети мог быть обработан независимо. В этом случае освободить память, занимаемую фрагментом, можно сразу после его обработки. Единственным и очевидным недостатком такого метода является повышение общего объема пересылаемой по сети
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распределение потоков графической информации в системах распознавания образов 23
информации, однако при больших значениях длины пересылаемых фрагментов и небольшом количестве ярусов эти издержки сравнительно малы.
Приведем алгоритм построения сети с динамическим избыточным распределением потока. При этом в отличие от статического метода, где схема потока, приписанная конкретному узлу или дуге сети, определяет, какие именно фрагменты изображения и в каком порядке пройдут через данную дугу или узел, эта схема определяет, какие фрагменты могут пройти через узел или дугу. Все узлы одного яруса являются равнозначными в том смысле, что любой узел предыдущего яруса может передать обработанный фрагмент любому из узлов следующего яруса.
На вход алгоритма поступает цепочка методов M1, …, M N с относительной вычисли-
тельной сложностью c1, …, cN , пропускной способностью эталонного метода qe , требуемой пропускной способностью цепочки q . На выходе получаем построенный граф вычислительной
сети G = {V , E} , ребра и вершины которого размечены схемами потоков M → { S, L, P },
M ' → { S, L, P }.
Для каждого i ∈[1, N ] определить ярус Gi = {Vi ,∅} .
∪Положить V = i∈[1, n]Vi ; E = ∅ . Приписать стоку схему потока 0, L, 0 , где L — ис-
ходная длина блока, задаваемая контроллером потока на этапе конфигурации. Положить раз-
{( )}метку M = ∅, M ′ = v1N , 0, L,0 .
Для каждого яруса i ∈[ N −1, 1] разметить все его вершины схемами
( ) ( )N N
N
∑ ∑ ∑− y−j , L +
y −j
+y
+ j
,−
y
− j
+ y +j
.
j=i j=i
j=i
Для каждой пары узлов vik и vik+′1 , i ∈[1, N −1], k ∈ [1,| Vi |] , k ′ ∈[1,| Vi+1 |] добавить дугу
между ними
( )E = E ∪ vik , vik+′1
и пометить ее схемой S, L, P :
( ) ( )N N
N
∑ ∑ ∑−
y
− j
,
L
+
y
− j
+ y +j
,−
y
− j
+ y +j
.
j =i +1
j=i+1
j=i+1
В построенной таким образом сети каждый узел каждого яруса соединен дугой с каж-
дым узлом последующего яруса. При большом количестве узлов в соседних ярусах это может
привести к значительной дополнительной нагрузке на сетевые ресурсы вычислительной сис-
темы (каждая дуга соответствует двум дополнительным потокам в процессах отправляющего
и принимающего узлов). Для снижения нагрузки при вычислении множества дуг можно ис-
пользовать первый алгоритм, а для разметки дуг и узлов — второй. Тогда каждый узел может
послать обработанный фрагмент любому из узлов следующего яруса, и простейшим способом
маршрутизации обработанных фрагментов из данного узла станет чередующаяся рассылка
фрагментов последовательно каждому из узлов следующего яруса. При этом будет достигать-
ся равномерное распределение загрузки между всеми узлами каждого яруса в предположе-
нии, что каждый из них обладает равным количеством ресурсов.
Обсуждение и выводы. Подводя итог, можно выделить следующие преимущества и
недостатки статического и динамического способа распределения потока.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
24 И. М. Гостев, А. Г. Подгорбунский
Распределенная система обладает высокой отказоустойчивостью — при выходе из строя одного из узлов сети его функции перераспределяются между остальными узлами того же яруса. Поэтому при динамическом распределении потоков неисправный узел будет заменен. При статическом методе распределения отказ узла приведет к появлению в выходном изображении необработанных участков.
Динамическое распределение дает возможность более гибкой балансировки загрузки узлов вычислительной сети. Если какой-то узел перегружен, его работу можно распределить на другие узлы того же яруса. Статическое распределение не позволяет этого делать. При динамическом распределении суммарный объем пересылаемых данных возрастает вследствие избыточной передачи строк, появляется дополнительная нагрузка на узлы, связанная с маршрутизацией и балансировкой исходящих фрагментов. По сравнению со статическим методом возрастают число потоков приема и передачи фрагментов и число сетевых соединений.
В целом преимущества динамического метода превосходят его недостатки.
СПИСОК ЛИТЕРАТУРЫ
1. Gostev I. M., Sevastianov L. A. About construction distributed calculation in real time system of image processing and pattern recognition // Proc. Int. Conf. „Distributed computation and GRID in science and education“. Dubna JINR. June, 2004. P. 79—85.
2. Gostev I. M., Sevastianov L. A. Internal Architecture of Distributed Real-time System of Image Processing and Pattern Recognition // Proc. XX Int. Symp. on Nuclear Electronics & Computing (NEC 2005). Varna, Bulgaria. September, 2005.
3. Мелихов А. Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971. 416 с.
Иван Михайлович Гостев Александр Глебович Подгорбунский
Сведения об авторах — д-р техн. наук; доцент; Московский государственный институт
электроники и математики (Технический университет), кафедра кибернетики; E-mail: igostev@gmail.com — аспирант; Московский государственный институт электроники и математики (Технический университет), кафедра кибернетики; E-mail: shurikp@gmail.com
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 519.92:681.3(07)
И. М. ГОСТЕВ, А. Г. ПОДГОРБУНСКИЙ
РАСПРЕДЕЛЕНИЕ ПОТОКОВ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В СИСТЕМАХ РАСПОЗНАВАНИЯ ОБРАЗОВ В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ
Рассматриваются два алгоритма управления видеопотоками в распределенной системе по обработке изображений и распознаванию образов на основе теории графов. Представлен алгоритм управления распределенной системой посредством контроллера потока. Приведено математическое описание статического (граф определен до начала работы системы) и динамического (граф может быть перестроен в процессе работы системы в зависимости от особенностей видеопотока) распределения информационных потоков.
Ключевые слова: алгоритм управления, графическая информация, распознавание объектов, реальный масштаб времени.
Введение. Несмотря на постоянное повышение быстродействия компьютеров построение систем обработки изображений и распознавания образов в реальном масштабе времени сопряжено с преодолением ряда проблем. В работе [1] показано, что быстродействие вычислительной системы для обработки видеопотока должно быть пропорциональным размеру изображения, для телевизионного формата оно превышает мощность одного компьютера примерно в 25—30 раз. Для решения этой проблемы были разработаны параллельные алгоритмы, позволяющие реализовать такую систему в распределенной среде, при этом каждый из элементов системы выполняет свою операцию по обработке изображения и распознавания образов. Для управления всей системой обработки видеопотока и распознавания объектов используется контроллер, который распределяет задания по вычислительным узлам системы, осуществляет контроль и синхронизацию их выполнения.
В работах [1, 2] была предложена и развита идея построения распределенной системы обработки и распознавания изображений в режиме реального времени, основанной на принципах конвейера и разбиения потока на участки. В настоящей работе рассматривается способ моделирования параллельных вычислений, основанный на применении ориентированных графов [3].
Математическая модель процессов. Разделим методы распределения потока на статические и динамические. В первом случае маршрут потоков информации определяется на этапе начальной инициализации системы и далее остается неизменным; размер фрагмента потока, его маршрут и методы обработки заранее определены. При динамическом распределении маршрут и размеры фрагментов определяются на стадии обработки.
Рассмотрим односвязный ориентированный ациклический граф, имеющий один исток и один сток, вершинами которого являются узлы вычислительной сети, реализованные в виде экземпляров метода, а дугами — каналы передачи потока. Методом назовем процедуру обработки изображения, реализованную в виде библиотечной функции. Входными данными метода будут фрагменты изображения и его параметры, необходимые для процедуры обработки. В результате работы метода получаются выходное изображение и/или некоторые другие данные, полученные в результате применения процедуры, формат которых зависит от конкретного метода. С помощью методов осуществляются разделение исходного потока на фрагменты, их параллельная обработка и последующее объединение нескольких потоков в один — результирующий. Всем процессом управляет компонент, называемый „контроллером потока“.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распределение потоков графической информации в системах распознавания образов 21
Поскольку процесс обработки изображения представляет собой последовательность (цепочку) нескольких методов, то в вычислительной сети каждому методу будет сопоставлен один или несколько узлов, его реализующих — экземпляров. Совокупность одинаковых экземпляров образует ярус сети, соответствующий данному методу цепочки. Входная информация поступает на некоторый узел только с узлов яруса, соответствующего предыдущему методу цепочки. Все выходы узла направлены только на узлы яруса, соответствующего следующему методу в цепочке. Первый и последний ярусы содержат по одному узлу. Каждый метод характеризуется относительной вычислительной сложностью процедуры, началом и
( )концом смещения фрагмента изображения по высоте y− , y+ и начальными условиями. На( )пример, смещение по высоте y− , y+ означает, что для метода l с параметрами начала и
конца фрагмента [s1, s2 ] необходим фрагмент l[s1 − y− , s2 + y+ ] . Алгоритм построения вычислительной среды. Статическое распределение потока.
Рассмотрим алгоритм статического распределения потока. Пусть исходный поток представляет собой одно длинное изображение — „ленту“. Фрагмент потока — непрерывный участок изображения, содержащий целое число строк. Промежуточные потоки состоят из последовательности фрагментов. Если поток состоит из фрагментов одинаковой длины, следующих через равные промежутки, то он может быть описан схемой потока.
Схема фрагмента потока представляет собой сочетание S, L, P где S — начальная
строка первого фрагмента, L — длина каждого фрагмента в строках, P — промежуток от конца предыдущего фрагмента до начала следующего. Таким образом, S, L, P определяет
последовательность фрагментов
[S + (L + P)i, S + (L + P)i + L], i ∈ N .
Две схемы называются смежными, когда при объединении двух соседних фрагментов их описание (состоящее из всех фрагментов первого и второго потока) также определяется схемой потока. Результирующая схема потока носит название объединенной. Символом
Ξi ( S, L, P ) обозначается схема потока, скорректированная в соответствии со смещениями
по y для i-го метода (необходимого методу на входе, чтобы производить поток S, L, P на
выходе):
( )Ξi S, L, P = S − yi− , L + yi− + yi+ , P − yi− − yi+ .
Алгоритм состоит из двух шагов — прямого и обратного. На первом происходят определение количества вершин в каждом ярусе и построение связей между ними путем равномерного последовательного разделения потока. На втором шаге происходит коррекция соединений и разметки с целью исключения каналов, по которым передаются очень малые относительно среднего потока на ярусе фрагменты.
Входом алгоритма являются цепочка методов M1, …, M N , относительная вычислительная сложность c1, …, cN , пропускная способность эталонного метода qe , требуемая пропускная способность цепочки q ; выходом — построенный граф вычислительной сети
G = {V , E} , ребра и вершины которого размечены схемами потоков M → { S, L, P },
M ' → { S, L, P }.
Шаг 1. Для каждого i ∈[1, N ] определить ярус Gi = {Vi , ∅} , где
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
22 И. М. Гостев, А. Г. Подгорбунский
Vi
=
⎧⎨vik ⎩
|
k
=
1...
⎡ ⎢⎢
qe q
c
⎤ ⎥⎥
⎫ ⎬ ⎭
— набор упорядоченных узлов методов, являющихся экземплярами метода Mi .
∪Положить V = i∈[1,n]Vi ; E = ∅ . Приписать истоку схему потока 0, L, 0 , где L — ис-
ходная длина блока, задаваемая контроллером потока на этапе конфигурации. Положить
{( )}M = ∅, M ′ = v11, 0, L, 0 , для каждого узла vik разметить его следующим образом:
⎢ ⎢ ⎣
k− | Vi
1⎥
|
⎥ ⎦
,
⎢k ⎣⎢| Vi
⎥ |⎥⎦
−
⎢ ⎢ ⎣
k+ | Vi
1⎥
|
⎥ ⎦
,
L
−
⎢k ⎣⎢| Vi
⎥ |⎦⎥
+
⎢ k +1⎥
⎢ ⎣
|
Vi
|
⎥ ⎦
.
Для каждой пары узлов vik и vik+′1 , i ∈[1, N −1], k ∈ [1,| Vi |] , k ′ ∈[1,| Vi+1 |] в случае если
( )M ′(vik ) ∩ Ξi (M ′(vik+′1)) ≠ ∅ , добавить дугу между узлами E = E ∪ vik , vik+′1 и пометить ее схе-
мой-пересечением:
{(( ) ( ) ( ( )))}M = M ∪ vik ,vik+′1 , M ′ vik ∩ Ξi M ′ vik+′1 .
Шаг 2. Для каждого яруса Vi , i = N , ..., 2 для каждого узла vik ∈Vi , k ∈ [1,| Vi |] .
а) Убедиться, что объединенная схема выходов совпадает со схемой узла:
{ ( )} ( )∪( )vik ,v ∈E M vik ,v = M ′ vik .
В случае, если это не так и объединенная схема включает схему узла, то вычислить множество недостающих схем
{ ( )} ( ( ))∪( )vik ,v ∈E M vik ,v Ξi M ′ vik
и каждый недостающий элемент этого множества прибавить к одной их схем входящих ребер узла, имеющих схему, смежную с недостающей, и наибольшую длину.
б) Удалить входные дуги, длина схемы которых меньше определенного порога, и схемы этих дуг приписать дугам наибольшей длины, имеющим смежные схемы.
Динамическое распределение потока. При динамическом распределении потока между обрабатывающими узлами маршрут, по которому пройдет конкретный фрагмент изображения, определяется на стадии выполнения. При этом из-за смещений по высоте для обработки данного фрагмента может потребоваться несколько строк предыдущего или последующего фрагмента, непосредственно прилегающего к данному. А так как заранее неизвестно, какие именно фрагменты пройдут через данный экземпляр метода, невозможно сказать, требуется сохранять этот фрагмент или нет. Кроме того, чтобы обеспечить обработку данного фрагмента с учетом смещений по высоте, требуется разместить предыдущий и последующий фрагменты непосредственно до и после него. Указанные факторы усложняют процедуру управления памятью и требуют реализации дополнительных условий маршрутизации на этапе обработки потока, включающих взаимодействие с контроллером потока, который координирует в этом случае маршрутизацию. Это противоречит одной из основных концепций, положенных в основу проектирования системы, согласно которой взаимодействие контроллера потока с методами на этапе обработки должно быть минимальным. Однако обе проблемы могут быть решены с помощью передачи избыточного количества фрагментов, так чтобы каждый фрагмент на каждом ярусе сети мог быть обработан независимо. В этом случае освободить память, занимаемую фрагментом, можно сразу после его обработки. Единственным и очевидным недостатком такого метода является повышение общего объема пересылаемой по сети
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распределение потоков графической информации в системах распознавания образов 23
информации, однако при больших значениях длины пересылаемых фрагментов и небольшом количестве ярусов эти издержки сравнительно малы.
Приведем алгоритм построения сети с динамическим избыточным распределением потока. При этом в отличие от статического метода, где схема потока, приписанная конкретному узлу или дуге сети, определяет, какие именно фрагменты изображения и в каком порядке пройдут через данную дугу или узел, эта схема определяет, какие фрагменты могут пройти через узел или дугу. Все узлы одного яруса являются равнозначными в том смысле, что любой узел предыдущего яруса может передать обработанный фрагмент любому из узлов следующего яруса.
На вход алгоритма поступает цепочка методов M1, …, M N с относительной вычисли-
тельной сложностью c1, …, cN , пропускной способностью эталонного метода qe , требуемой пропускной способностью цепочки q . На выходе получаем построенный граф вычислительной
сети G = {V , E} , ребра и вершины которого размечены схемами потоков M → { S, L, P },
M ' → { S, L, P }.
Для каждого i ∈[1, N ] определить ярус Gi = {Vi ,∅} .
∪Положить V = i∈[1, n]Vi ; E = ∅ . Приписать стоку схему потока 0, L, 0 , где L — ис-
ходная длина блока, задаваемая контроллером потока на этапе конфигурации. Положить раз-
{( )}метку M = ∅, M ′ = v1N , 0, L,0 .
Для каждого яруса i ∈[ N −1, 1] разметить все его вершины схемами
( ) ( )N N
N
∑ ∑ ∑− y−j , L +
y −j
+y
+ j
,−
y
− j
+ y +j
.
j=i j=i
j=i
Для каждой пары узлов vik и vik+′1 , i ∈[1, N −1], k ∈ [1,| Vi |] , k ′ ∈[1,| Vi+1 |] добавить дугу
между ними
( )E = E ∪ vik , vik+′1
и пометить ее схемой S, L, P :
( ) ( )N N
N
∑ ∑ ∑−
y
− j
,
L
+
y
− j
+ y +j
,−
y
− j
+ y +j
.
j =i +1
j=i+1
j=i+1
В построенной таким образом сети каждый узел каждого яруса соединен дугой с каж-
дым узлом последующего яруса. При большом количестве узлов в соседних ярусах это может
привести к значительной дополнительной нагрузке на сетевые ресурсы вычислительной сис-
темы (каждая дуга соответствует двум дополнительным потокам в процессах отправляющего
и принимающего узлов). Для снижения нагрузки при вычислении множества дуг можно ис-
пользовать первый алгоритм, а для разметки дуг и узлов — второй. Тогда каждый узел может
послать обработанный фрагмент любому из узлов следующего яруса, и простейшим способом
маршрутизации обработанных фрагментов из данного узла станет чередующаяся рассылка
фрагментов последовательно каждому из узлов следующего яруса. При этом будет достигать-
ся равномерное распределение загрузки между всеми узлами каждого яруса в предположе-
нии, что каждый из них обладает равным количеством ресурсов.
Обсуждение и выводы. Подводя итог, можно выделить следующие преимущества и
недостатки статического и динамического способа распределения потока.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
24 И. М. Гостев, А. Г. Подгорбунский
Распределенная система обладает высокой отказоустойчивостью — при выходе из строя одного из узлов сети его функции перераспределяются между остальными узлами того же яруса. Поэтому при динамическом распределении потоков неисправный узел будет заменен. При статическом методе распределения отказ узла приведет к появлению в выходном изображении необработанных участков.
Динамическое распределение дает возможность более гибкой балансировки загрузки узлов вычислительной сети. Если какой-то узел перегружен, его работу можно распределить на другие узлы того же яруса. Статическое распределение не позволяет этого делать. При динамическом распределении суммарный объем пересылаемых данных возрастает вследствие избыточной передачи строк, появляется дополнительная нагрузка на узлы, связанная с маршрутизацией и балансировкой исходящих фрагментов. По сравнению со статическим методом возрастают число потоков приема и передачи фрагментов и число сетевых соединений.
В целом преимущества динамического метода превосходят его недостатки.
СПИСОК ЛИТЕРАТУРЫ
1. Gostev I. M., Sevastianov L. A. About construction distributed calculation in real time system of image processing and pattern recognition // Proc. Int. Conf. „Distributed computation and GRID in science and education“. Dubna JINR. June, 2004. P. 79—85.
2. Gostev I. M., Sevastianov L. A. Internal Architecture of Distributed Real-time System of Image Processing and Pattern Recognition // Proc. XX Int. Symp. on Nuclear Electronics & Computing (NEC 2005). Varna, Bulgaria. September, 2005.
3. Мелихов А. Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971. 416 с.
Иван Михайлович Гостев Александр Глебович Подгорбунский
Сведения об авторах — д-р техн. наук; доцент; Московский государственный институт
электроники и математики (Технический университет), кафедра кибернетики; E-mail: igostev@gmail.com — аспирант; Московский государственный институт электроники и математики (Технический университет), кафедра кибернетики; E-mail: shurikp@gmail.com
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2