МЕТОД РЕКОНФИГУРАЦИИ ОПЕРАЦИОННОЙ ЧАСТИ МУЛЬТИПРОЦЕССОРА СТРУКТУРНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ
52 Е. А. Титенко
УДК 004.31
Е. А. ТИТЕНКО
МЕТОД РЕКОНФИГУРАЦИИ ОПЕРАЦИОННОЙ ЧАСТИ МУЛЬТИПРОЦЕССОРА СТРУКТУРНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ
Представлен метод распознавания структурных дескрипторов для ветвящихся процессов, показана организация соединений между продукционными устройствами в мультипроцессоре.
Ключевые слова: структурное распознавание, мультипроцессор, ветвящиеся вычислительные процессы, продукция.
Современные теоретические, программные и технические средства обработки разнородной информации все в большей степени ориентируются на организацию параллельных распределенных вычислений [см. лит.]. Такие инструментальные средства должны содержать блоки (модули) для упреждающего распознавания структурных особенностей взаимодействия параллельных процессов и последующей реконфигурации под граф решаемой задачи. Основная проблема заключается в том, что проектирование современных многопроцессорных устройств и машин не учитывает специфики взаимодействия вычислительных процессов решаемой задачи, что приводит к дополнительным затратам времени на обменные процессы между параллельно работающими устройствами или блоками при организации параллельных вычислений. Таким образом, семантический разрыв между аппаратными средствами проектировщика и алгоритмическими средствами пользователя порождает временную избыточность. Особенно остро эта проблема проявляется при организации параллельных вычислений с ветвящимися процессами, возникающими в задачах структурного распознавания образов в различных предметных областях: в динамических экспертных системах, в системах обработки знаний.
В настоящей статье представлен перспективный вариант реализации гибкой динамически реконфигурируемой коммутационной структуры мультипроцессора, являющейся основой его операционной части.
Метод реконфигурации соединений продукционных устройств основан на упреждающем структурном распознавании символьных дескрипторов конфликтных ситуаций и динамической реконфигурации структуры операционной части мультипроцессора в однородную.
Был разработан инвариантный по возможностям метод прогнозирования соединений параллельно работающих устройств в соответствии с графом решаемой задачи на основе продукционной парадигмы организации вычислений. Целесообразность выбора продукционной парадигмы для организации параллельных вычислений определяется следующими факторами:
— модульность и однородность состава системы продукций, что позволяет динамически реконфигурировать соответствующие аппаратные средства;
— гибкость реализации различных схем управления; — потенциальный параллелизм и асинхронность продукционных вычислений. Целесообразно использовать вычислительную продукционную систему. Одной из основных причин ограничения области применения многопроцессорных устройств является возникновение конфликтных ситуаций, существенно ограничивающих возможности таких систем в задачах распознавания реального уровня сложности. Вследствие конфликтной ситуации структура образца j-й продукции в обрабатываемом слове нарушается, что препятствует срабатыванию i-й продукции при пересечении образцов i, j (i ≠ j) продукционной системы. Попарное пересечение образцов i, j (i ≠ j) продукционной системы является логическим условием отношения зависимости между продукциями, вследствие чего возникают недетер-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Метод реконфигурации операционной части мультипроцессора
53
минированность в процессах принятия решения и непродуктивные затраты времени на поиск и распознавание эталонных описаний в массивах разнородных данных большой размерности. Конфликтные ситуации сужают потенциальные возможности программных и аппаратных средств, что недопустимо в задачах распознавания динамично возникающих в графе решаемой задачи ситуаций конфликтов между параллельными процессами за общий ресурс.
В связи с этим важнейшей задачей проектирования мультипроцессорной организации системы является метод реконфигурации, основанный на упреждающем распознавании и нейтрализации конфликтных ситуаций. Основное преимущество предлагаемого метода распознавания структурных дескрипторов конфликтов заключается в извлечении дополнительной информации, основанной на рекурсивном обнаружении парных пересечений образцов.
Исследование вариантов пересечения слов и синтез на их основе конфликтных слов определили структуру аналитического модуля распознавания, входящего в состав мультипроцессора (рис. 1, где 1 — модуль проверки условия зацикливания, 2 — модуль поиска пересечений слов, 3 — модуль построения дополнений, 4 — модуль объединения слов, n — количе-
ство продукций, O1, ..., On — входной список образцов, m — количество дескрипторов кон-
фликтных ситуаций, v — количество промежуточных дескрипторов конфликтных ситуаций,
K1, ..., Km — выходной список дескрипторов конфликтных ситуаций, K1, ..., Kv — промежу-
точный список дескрипторов конфликтных ситуаций).
{О1, …, Оn }
{K1, …, Kv}
Входные данные
10
3 1
2 0
4
1 Выходные данные
Зацикливание
{K1, …, Km} Рис. 1
На основе полученных дескрипторов конфликтных ситуаций K1, ..., Km вычисляются
настроечные значения соединений продукционных устройств в операционной части. Рассмотрим общие принципы построения мультипроцессора с реконфигурируемыми
соединениями. Под мультипроцессором понимается символьное устройство для аппаратной поддержки ветвящихся продукционных вычислений. Каждое продукционное процессорное устройство (ППУ) аппаратно реализует базовые операции поиска и преобразования строковых данных. Принципы однородности и модульной наращиваемости архитектуры символьного мультипроцессора предписывают ставить в соответствие каждой продукции вычислительной системы отдельное ППУ с собственной внутренней памятью. Тогда массовые параллельные вычисления в мультипроцессоре определяются сбалансированной подсистемой коммутации ППУ в составе операционной части в соответствии с графом решаемой задачи.
Исходя из общесистемных принципов организации параллельных вычислений в задачах с ветвящимися конструктивными процессами операционная часть символьного мультипроцессора будет содержать два настаиваемых яруса ППУ. Эти ярусы являются независимыми друг от друга, поэтому возможно их параллельное функционирование. Первый ярус ориентирован
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
54 Е. А. Титенко
на работу ППУ в соответствии с установленными соединениями и обеспечивает текущие вычисления по графу решаемой задачи. Второй ярус операционной части мультипроцессора осуществляет настройку новых соединений ППУ для работы на следующем шаге по графу решаемой задачи.
Попеременное переключение двух параллельно работающих ярусов ППУ является отличительной чертой предлагаемого технического решения. Это обстоятельство позволяет осуществлять расслоение общего графа решаемой задачи на самостоятельные подграфы, в которых параллельные вычисления комбинируются с последовательными. Независимость подграфов вычислений создает предпосылки для параллельного функционирования двух ярусов ППУ с децентрализованным управлением каждым ярусом. В связи с этим архитектура символьного мультипроцессора получается гибридной, так как в ней совмещаются детерминированные принципы синхронного управления конвейерных соединений ППУ и недетерминированные принципы асинхронного управления параллельных соединений ППУ.
На рис. 2 приведена структура яруса операционной части мультипроцессора для обеспечения ветвящихся вычислительных процессов.
D0 G11
r1
G21
MX DMX
ППУ1
G12 r2
ППУ2
G22
MX DMX
… G1 i–1 ri–1
ППУi–1
G2 i–1
ХРАНИЛИЩЕ ДАННЫХ
MX DMX
…… ……
l …p G1 RG
РАБОЧАЯ ПАМЯТЬ
G1i ri
G2i
MX DMX
ППУi
l …p RG G2
MX
G2p rp ППУp
DMX
G2p Dp+1
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 55
Входные регистры G1 и G2 хранят настроечные векторы соединений ППУ между собой. Настроечные векторы вычисляются аналитическим модулем распознавания структурных дескрипторов конфликтов, сам модуль не входит в состав операционной части. Основу однородной структуры операционной части составляет вычислительно-коммутационный блок, содержащий собственно ППУ, входной мультиплексор (MX) с двумя входами, выходной демультиплексор (DMX) с двумя выходами (r — индикатор номера продукционного устройства). Введение двух коммутирующих узлов в вычислительно-коммутационный блок обеспечивает гибкую настройку соединений конвейерных или параллельных видов с объединением необходимого на текущем уровне количества ППУ.
Таким образом, разработана структура операционной части мультипроцессора, отличающаяся поддержкой ветвящихся вычислительных процессов и имеющая в своем составе два параллельно работающих яруса продукционных процессорных устройств на основе структурного распознавания дескрипторов конфликтов и динамической упреждающей реконфигурации яруса ППУ под следующий шаг вычислений по структуре графа задачи.
ЛИТЕРАТУРА
Каляев А. В., Левин И. И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Изд-во „Янус-К“, 2003. 380 с.
Евгений Анатольевич Титенко
Сведения об авторе — канд. техн. наук, доцент; Курский государственный технический уни-
верситет, кафедра программного обеспечения вычислительной техники; E-mail: johntit@mail.ru
Рекомендована кафедрой программного обеспечения вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 004.31
Е. А. ТИТЕНКО
МЕТОД РЕКОНФИГУРАЦИИ ОПЕРАЦИОННОЙ ЧАСТИ МУЛЬТИПРОЦЕССОРА СТРУКТУРНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ
Представлен метод распознавания структурных дескрипторов для ветвящихся процессов, показана организация соединений между продукционными устройствами в мультипроцессоре.
Ключевые слова: структурное распознавание, мультипроцессор, ветвящиеся вычислительные процессы, продукция.
Современные теоретические, программные и технические средства обработки разнородной информации все в большей степени ориентируются на организацию параллельных распределенных вычислений [см. лит.]. Такие инструментальные средства должны содержать блоки (модули) для упреждающего распознавания структурных особенностей взаимодействия параллельных процессов и последующей реконфигурации под граф решаемой задачи. Основная проблема заключается в том, что проектирование современных многопроцессорных устройств и машин не учитывает специфики взаимодействия вычислительных процессов решаемой задачи, что приводит к дополнительным затратам времени на обменные процессы между параллельно работающими устройствами или блоками при организации параллельных вычислений. Таким образом, семантический разрыв между аппаратными средствами проектировщика и алгоритмическими средствами пользователя порождает временную избыточность. Особенно остро эта проблема проявляется при организации параллельных вычислений с ветвящимися процессами, возникающими в задачах структурного распознавания образов в различных предметных областях: в динамических экспертных системах, в системах обработки знаний.
В настоящей статье представлен перспективный вариант реализации гибкой динамически реконфигурируемой коммутационной структуры мультипроцессора, являющейся основой его операционной части.
Метод реконфигурации соединений продукционных устройств основан на упреждающем структурном распознавании символьных дескрипторов конфликтных ситуаций и динамической реконфигурации структуры операционной части мультипроцессора в однородную.
Был разработан инвариантный по возможностям метод прогнозирования соединений параллельно работающих устройств в соответствии с графом решаемой задачи на основе продукционной парадигмы организации вычислений. Целесообразность выбора продукционной парадигмы для организации параллельных вычислений определяется следующими факторами:
— модульность и однородность состава системы продукций, что позволяет динамически реконфигурировать соответствующие аппаратные средства;
— гибкость реализации различных схем управления; — потенциальный параллелизм и асинхронность продукционных вычислений. Целесообразно использовать вычислительную продукционную систему. Одной из основных причин ограничения области применения многопроцессорных устройств является возникновение конфликтных ситуаций, существенно ограничивающих возможности таких систем в задачах распознавания реального уровня сложности. Вследствие конфликтной ситуации структура образца j-й продукции в обрабатываемом слове нарушается, что препятствует срабатыванию i-й продукции при пересечении образцов i, j (i ≠ j) продукционной системы. Попарное пересечение образцов i, j (i ≠ j) продукционной системы является логическим условием отношения зависимости между продукциями, вследствие чего возникают недетер-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Метод реконфигурации операционной части мультипроцессора
53
минированность в процессах принятия решения и непродуктивные затраты времени на поиск и распознавание эталонных описаний в массивах разнородных данных большой размерности. Конфликтные ситуации сужают потенциальные возможности программных и аппаратных средств, что недопустимо в задачах распознавания динамично возникающих в графе решаемой задачи ситуаций конфликтов между параллельными процессами за общий ресурс.
В связи с этим важнейшей задачей проектирования мультипроцессорной организации системы является метод реконфигурации, основанный на упреждающем распознавании и нейтрализации конфликтных ситуаций. Основное преимущество предлагаемого метода распознавания структурных дескрипторов конфликтов заключается в извлечении дополнительной информации, основанной на рекурсивном обнаружении парных пересечений образцов.
Исследование вариантов пересечения слов и синтез на их основе конфликтных слов определили структуру аналитического модуля распознавания, входящего в состав мультипроцессора (рис. 1, где 1 — модуль проверки условия зацикливания, 2 — модуль поиска пересечений слов, 3 — модуль построения дополнений, 4 — модуль объединения слов, n — количе-
ство продукций, O1, ..., On — входной список образцов, m — количество дескрипторов кон-
фликтных ситуаций, v — количество промежуточных дескрипторов конфликтных ситуаций,
K1, ..., Km — выходной список дескрипторов конфликтных ситуаций, K1, ..., Kv — промежу-
точный список дескрипторов конфликтных ситуаций).
{О1, …, Оn }
{K1, …, Kv}
Входные данные
10
3 1
2 0
4
1 Выходные данные
Зацикливание
{K1, …, Km} Рис. 1
На основе полученных дескрипторов конфликтных ситуаций K1, ..., Km вычисляются
настроечные значения соединений продукционных устройств в операционной части. Рассмотрим общие принципы построения мультипроцессора с реконфигурируемыми
соединениями. Под мультипроцессором понимается символьное устройство для аппаратной поддержки ветвящихся продукционных вычислений. Каждое продукционное процессорное устройство (ППУ) аппаратно реализует базовые операции поиска и преобразования строковых данных. Принципы однородности и модульной наращиваемости архитектуры символьного мультипроцессора предписывают ставить в соответствие каждой продукции вычислительной системы отдельное ППУ с собственной внутренней памятью. Тогда массовые параллельные вычисления в мультипроцессоре определяются сбалансированной подсистемой коммутации ППУ в составе операционной части в соответствии с графом решаемой задачи.
Исходя из общесистемных принципов организации параллельных вычислений в задачах с ветвящимися конструктивными процессами операционная часть символьного мультипроцессора будет содержать два настаиваемых яруса ППУ. Эти ярусы являются независимыми друг от друга, поэтому возможно их параллельное функционирование. Первый ярус ориентирован
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
54 Е. А. Титенко
на работу ППУ в соответствии с установленными соединениями и обеспечивает текущие вычисления по графу решаемой задачи. Второй ярус операционной части мультипроцессора осуществляет настройку новых соединений ППУ для работы на следующем шаге по графу решаемой задачи.
Попеременное переключение двух параллельно работающих ярусов ППУ является отличительной чертой предлагаемого технического решения. Это обстоятельство позволяет осуществлять расслоение общего графа решаемой задачи на самостоятельные подграфы, в которых параллельные вычисления комбинируются с последовательными. Независимость подграфов вычислений создает предпосылки для параллельного функционирования двух ярусов ППУ с децентрализованным управлением каждым ярусом. В связи с этим архитектура символьного мультипроцессора получается гибридной, так как в ней совмещаются детерминированные принципы синхронного управления конвейерных соединений ППУ и недетерминированные принципы асинхронного управления параллельных соединений ППУ.
На рис. 2 приведена структура яруса операционной части мультипроцессора для обеспечения ветвящихся вычислительных процессов.
D0 G11
r1
G21
MX DMX
ППУ1
G12 r2
ППУ2
G22
MX DMX
… G1 i–1 ri–1
ППУi–1
G2 i–1
ХРАНИЛИЩЕ ДАННЫХ
MX DMX
…… ……
l …p G1 RG
РАБОЧАЯ ПАМЯТЬ
G1i ri
G2i
MX DMX
ППУi
l …p RG G2
MX
G2p rp ППУp
DMX
G2p Dp+1
Рис. 2
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Размещение параллельных подпрограмм в мультимикроконтроллерах с учетом отказов 55
Входные регистры G1 и G2 хранят настроечные векторы соединений ППУ между собой. Настроечные векторы вычисляются аналитическим модулем распознавания структурных дескрипторов конфликтов, сам модуль не входит в состав операционной части. Основу однородной структуры операционной части составляет вычислительно-коммутационный блок, содержащий собственно ППУ, входной мультиплексор (MX) с двумя входами, выходной демультиплексор (DMX) с двумя выходами (r — индикатор номера продукционного устройства). Введение двух коммутирующих узлов в вычислительно-коммутационный блок обеспечивает гибкую настройку соединений конвейерных или параллельных видов с объединением необходимого на текущем уровне количества ППУ.
Таким образом, разработана структура операционной части мультипроцессора, отличающаяся поддержкой ветвящихся вычислительных процессов и имеющая в своем составе два параллельно работающих яруса продукционных процессорных устройств на основе структурного распознавания дескрипторов конфликтов и динамической упреждающей реконфигурации яруса ППУ под следующий шаг вычислений по структуре графа задачи.
ЛИТЕРАТУРА
Каляев А. В., Левин И. И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Изд-во „Янус-К“, 2003. 380 с.
Евгений Анатольевич Титенко
Сведения об авторе — канд. техн. наук, доцент; Курский государственный технический уни-
верситет, кафедра программного обеспечения вычислительной техники; E-mail: johntit@mail.ru
Рекомендована кафедрой программного обеспечения вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2