автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Метод, алгоритм и специализированное устройство параллельной обработки символьной информации

На правах рукописи

У

005043253 //'

Зерин Иван Сергеевич

МЕТОД, АЛГОРИТМ И СПЕЦИАЛИЗИРОВАННОЕ УСТРОЙСТВО ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ

05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 / МАЙ 2012

КУРСК-2012

005043253

Работа выполнена в Юго-Западном государственном университете

Научный руководитель: кандидат технических наук, доцент

Титенко Евгений Анатольевич

Официальные оппоненты: Фисун Александр Павлович,

доктор технических наук, профессор, филиал ФГУП «РЧЦ ЦФО» в Орловской области (г. Орел), заместитель директора филиала

Мусакин Евгений Юрьевич, кандидат технических наук, доцент, НИЦ (г.Курск) ФГУП «18 ЦНИИ» МО РФ, начальник отдела

Ведущая организация: Госуниверситет - учебно- научно-

производственный комплекс (г. Орел)

Защита состоится 30 мая 2012 г. в 16:00 ч. в конференц-зале на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке Юго-Западного государственного университета.

Автореферат разослан 28 апреля 2012 г.

Учёный секретарь диссертационного совета Д 212.105.02

Е.А. Титенко

Актуальность.

Современный этап развития устройств вычислительной техники (ВТ) характеризуется организацией параллельных вычислений с использованием таких форм распараллеливания, которые свойственны естественному интеллекту в части применения базовой схемы принятия решений «условие-»действие». Особая система правил (продукционная система) как формализация данной схемы, а также аппаратно-программные средства, поддерживающие базовые продукционные операции составляют основу продукционной парадигмы вычислений, применяемой для параллельной обработки символьной информации (ОСИ).

Тем не менее, системы продукций и основные продукционные операции в них (точный или приблизительный поиск по образцу, пересечение/объединение/дополнение фрагментов строк, модификация данных, реконфигурация структуры и др.) получили ограниченную аппаратную поддержку в современной ВТ. Они, как правило, реализуются программно, что приводит к неудовлетворительным временным характеристикам специализированных устройств при решении задач ОСИ. Повышенное внимание к вопросу временной оценки задач ОСИ объясняется тем, что процессы символьных вычислений присутствуют в компьютерных системах распознавания образов, системах поддержки принятия решений, основанных на моделях обработки знаний, естественно-языковых системах, криптографических системах, информационно-поисковых системах и др. В целом, задачи ОСИ по экспертным оценкам занимают до 80% от общего объема прикладных вычислительных задач в различной постановке. Экстенсивный подход к решению задач ОСИ заключается в применении известных типов архитектур вычислительных устройств и систем обработки числовой информации, что составляет основное противоречие исследования, не позволяющее достигнуть необходимой производительности символьных вычислений.

Создание нетрадиционных архитектур устройств ОСИ, основанных на идеологии PIM-процессоров (Processor In Memory), является перспективным направлением развития высокопроизводительных средств ВТ и определяет разработку технических решений (узлы, блоки операционной части) и алгоритмов работы, структурно-функциональной организации для однородных вычислительных устройств ОСИ с реконфигурируемой операционной частью.

Теоретические и прикладные исследования продукционных систем (ПС) рассматривались в работах А.А. Маркова, Н.М. Нагорного, Н.А. Шанина, В.И. Городецкого, В.М. Довгаля, А. Ньюэлла, М. Саймона, Дж. Люгера, Э. Поста и других ученых. Тем не менее, свойственные задачам ОСИ вопросы и технические решения предсказания и разрешения конфликтов при параллельном применении продукционных правил нашли частичное отражение в трудах известных ученых, что определяет актуальность исследования.

Научно-техническая задача - поддержка параллельных вычислений на основе продукционных систем и специализированных устройств для реализации высокоскоростных символьных вычислений.

Объект исследования - вычислительные процессы и устройства обработки символьной информации.

Предмет исследования - методы, алгоритмы и схемотехнические решения безотступной модификации строковых данных с итерационными фрагментами на основе продукционной парадигмы вычислений.

Цель работы заключается в сокращении затрат времени на поддержку символьных вычислений продукционных систем путем разработки метода разрешения конфликтов, метода реконфигурации, алгоритма и схемотехнических решений блоков и узлов для специализированного устройства с однородной операционной частью обработки символьной информации.

Основные задачи диссертационного исследования:

1. Анализ основных направлений развития вычислительных устройств для организации параллельных вычислений. Анализ ограничений существующих методов и аппаратных решений для поддержки базовых продукционных операций.

2. Разработка метода разрешения конфликтов для безотступной модификации символьных данных. Обоснование логического условия расстановки приоритетов продукций.

3. Разработка метода реконфигурации и алгоритма для поддержки базовой операции - модификации строковых данных (операции замены).

4. Разработка структурно-функциональной организации специализированного устройства с однородной операционной частью модификации символьных данных, алгоритма работы устройства, а также схемотехнических решений основных блоков и узлов.

5. Экспериментальная проверка работоспособности технических решений устройства, оценка аппаратной и временной сложности созданного устройства.

Методы исследования основаны на теории проектирования ЭВМ, схемотехнике, аппарате продукционных систем, ассоциативной памяти, математической логике, а также теории алгоритмов и прикладного программирования.

Научная новизна и результаты, выносимые на защиту:

1. Создан метод разрешения конфликтных ситуаций, основанный на анализе множественных пересечений частей продукций, с последующей расстановкой приоритетов их срабатывания и позволяющий задать детерминированную схему срабатывания продукций.

2. Создан метод реконфигурации для параллельной замены строк, основанный на динамической реконфигурации структуры данных (матрица -строка) и динамическом формировании маски для выделения рабочей области матрицы и позволяющий корректно выполнять операцию замены при произвольных сочетаниях длин образца и модификатора продукции.

3. Разработана структурно-функциональная организация специализированного устройства параллельной замены с однородной операционной частью, содержащей двумерный массив ячеек с реконфигурируемыми связями, а также функциональную схему формирования двоичных векторов-масок строк, что позволяет корректно выполнять

безотступную модификацию данных при произвольных сочетаниях длин образца и модификатора продукции.

4. Разработан алгоритм параллельной замены текущего вхождения, состоящий из четырех аппаратных шагов (замещение, раздвижка, вставка и корректирующее удаление символов), основанный на управляемой циклической реконфигурацией массива элементов из одномерного в двумерный вид и обратно при выполнении аппаратных шагов и позволяющий корректно выполнять операцию замены по безотступной технологии.

Практическая ценность работы состоит в следующем:

1. Разработанный алгоритм замены, основанный на динамической реконфигурации структуры данных, а так же на динамическом выделении рабочей области матрицы, позволяет выполнять базовую операцию символьной обработки по безотступной технологии, что сокращает время выполнения задач ОСИ.

2. Проведена оценка аппаратной сложности разработанного устройства, содержащего ассоциативную матрицу ячеек с реконфигурируемыми связями, которая показала, что с точки зрения аппаратных затрат на отдельную ячейку матрицы рациональным соотношением длин образца и текста является соотношение 1:5. Данное соотношение позволяет выбирать рациональную по аппаратным затратам ширину операционной части (матрицы) с учетом длин обрабатываемых данных.

3. Проведены экспериментальные исследования скоростных характеристик разработанного устройства, которые показали, что разработанное устройство имеет преимущество в 4-5 раз по отношению к циклическому условному сдвигателю (аналогу) на задаче модификации данных с типовыми параметрами (практически значимые длины фрагмента текста, образца модификатора, варьируемая позиция вхождения), что позволяет определить сферы применения разработанного устройства для решения различных задач ОСИ.

Реализация результатов работы. Результаты диссертационной работы внедрены в НИЦ (г.Курск) ФГУП «18 ЦНИИ» МО РФ, используются в учебном процессе Юго-Западного государственного университета в рамках дисциплины «Системы искусственного интеллекта» кафедры программное обеспечение вычислительной техники, а также нашли применение в Курском ОАО «Прибор» (г. Курск) при создании спецузлов бортовых систем управления.

Соответствие паспорту специальности. Диссертационная работа соответствует паспорту научной специальности 05.13.05 - «Элементы и устройства вычислительной техники и систем управления» по пункту 2 «Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик».

Апробация работы. Основные научные результаты работы докладывались и обсуждались на IX Международной Научно-практической Конференции «Компьютерные технологии в науке, производстве, социальных, и экономических процессах» (г.Новочеркасск, 2008), II Международной научно-

практической конференции «Ценности и интересы современного общества» (г.Курск, 2008), VIII Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображения и символьной информации» (г.Курск, 2008), Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г.Ульяновск, 2009), IX Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображения и символьной информации» (г.Курск, 2010), а также рассматривались на семинарах кафедры вычислительной техники и программного обеспечения вычислительной техники Юго-Западного государственного университета в 2009-2012 гг.

Публикации по работе. По результатам выполненных разработок и исследований опубликованы 13 работ, в том числе 6 работ в рецензируемых научных журналах и изданиях, получено свидетельство о регистрации программы для ЭВМ №2008612281.

Личный вклад. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя сводится к следующему: в [1] описан метод разрешения конфликтных ситуаций для итерационных строковых фрагментов; в [2,3,5] проведен анализ возникновения конфликтных ситуаций при работе продукций, предложен метод их разрешения; в [4] предложен подход реконфигурации однородной вычислительной структуры устройства; в [6] разработан метод реконфигурации и структурно-функциональная схема ассоциативной запоминающей матрицы для параллельного поиска и замены строк; в [7] разработан алгоритм автоматического преобразования продукций к акселерационным формам; в [8] предложено использование итерационных фрагментов для формирования записи искомых подстрок; в [9,10] получены данные результатов моделирования работы акселерационной и канонической форм продукций; в [13] проведена алгоритмизация схемы параллельной замены вхождений, позволяющей корректно выполнять операцию замены по безотступной технологии.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и двух приложений. Основное содержание диссертации изложено на 161 странице машинописного текста, содержит 28 рисунков, 15 таблиц и список литературы из 75 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении обоснована актуальность темы по организации и аппаратной поддержке параллельных вычислений в рамках аппарата продукционных систем, а так же сформулированы цель и задача исследования, научная новизна и основные положения выносимые на защиту, практическая ценность работы, и другие характеристики работы.

В первой главе анализируются варианты организации систем и устройств ВТ для параллельных вычислений: SMP-, МРР-архитектуры,

мультиконвейерные реконфшурируемые структуры, архитектуры ассоциативных параллельных процессоров, производится сравнительный анализ технических и программных решений высокоскоростной обработки информации, обосновывается выбор класса однородных параллельных процессоров для обработки символьной информации.

Показано, что временная трудоемкость задач ОСИ определяется такими характеристиками как возвратный механизм работы ПС, вариативность образования следующей позиции вхождения после текущего срабатывания продукции, обязательность отступа в начальную позицию после текущей модификации данных, нерегулярность расположения измененных фрагментов по структуре данных и др.

Установлено, что развитие перспективных процессорных архитектур (VLIW-, EPIC-, мультиконвейеры и др.), ориентированных исключительно на обработку числовых данных, не обеспечивает необходимого повышения производительности решения задач ОСИ, так как для них требуются эффективные решения по разрешению конфликтов при обработке множественных потоков. Известные методы и алгоритмы разрешения конфликтов не предназначены для анализа структурно-лингвистических свойств символьных данных и не поддерживают безотступную технологию параллельных символьных вычислений.

Данные обстоятельства делают актуальной задачу проектирования специализированных однородных устройств ОСИ с аппаратной поддержкой базовых продукционных операций.

Сущность предлагаемого в работе подхода заключается в разработке методов и средств аннуляции возвратных переходов по данным при параллельном исполнении ПС, а также в организации и исследовании однородных устройств ОСИ на базе ассоциативной матрицы с реконфигурируемыми связями между ячейками матрицы. Предметной стороной предлагаемого подхода является сокращение избыточных затрат времени на аппаратную поддержку базовой операции модификации данных, используемой как массовая команда для различных прикладных продукционных систем.

Во второй главе производится структурно-лингвистический анализ продукционных правил по А.А.Маркову с учетом существования итерационных фрагментов, рассматриваются существующие методы акселерации и их ограничения, а так же рассмотрено влияние структурных отношений между образцом и модификатором на время и корректность выполнения конструктивных процессов модификации данных (замена строк). Анализируются причины появления множественных пересечений частей продукций в алгоритмической системе A.A. Маркова, определяются логические условия, при которых множественные пересечения приводят к неэквивалентным результатам.

Продукцией (продукционным правилом) называется выражение:

О - ► М, (1)

где О - образец, М - модификатор. О и М - слова в заданном алфавите А, —> -является метасимволом, не принадлежащим А. ■

Работа продукции заключается в поиске вхождения образца О и его последующей замены на модификатор М. При этом после каждой замены для корректности вычислений выполняется возвратный переход на первый символ обрабатываемой строки. Возвратные переходы порождают непродуктивные временные затраты, что привело к созданию модифицированной продукционной системы, основным достоинством которой, является возможность срабатывания продукций по безвозвратному принципу. Безвозвратность вычислений достигается благодаря использованию конструктивной дизъюнкции:

(Оо = Мн) V(Oh = M0)V(00 = M)V(Oh = M)V(0 = CMD), (2)

где Он, 00 — собственные начало и окончание образца соответственно, М„, Мо -собственные начало и окончание модификатора соответственно, С и D - слова в заданном алфавите А.

Если дизъюнкция (2) истинна, то продукция сама себя активирует, то есть потенциально создает заменой образца на модификатор новую позицию вхождения своего образца в уже просмотренной части обрабатываемого слова В этом случае, формируется особая форма продукции, позволяющая выполнять вычисления по безотступной технологии. При ложном значении дизъюнкции (2), продукция не может создавать подстановки собственного модификатора в просмотренной части слова, что является необходимым и достаточным условием для ее работы по безотступной технологии.

Для возможности однозначного определения первого символа сопоставления в обрабатываемом тексте, после выполнения очередной замены при безотступной замене применяется метасимвол «!». В этом случае продукция (1) принимает вид:

Ю —* M!, (3)

где ! - метасимвол-маркер начальной позиции сопоставления.

Между тем в продукционной парадигме присутствует особый случай пересечения образца и модификатора, называемым множественным пересечением, приводящий к конфликтным ситуациям при параллельной работе продукций.

Множественным пересечением образца и модификатора продукции называется случай, когда конструктивная дизъюнкция (2) истинна двумя и более своими членами, которые определяют типы пересечений слов.

Исходя из определения множественного пересечения частей продукции по дизъюнкции (2), выделяются 32 варианта множественных пересечений слов, ■ из которых 4 варианта пересечений являются предельными:

1. (Он = М) & (00 = М) & (О = CMD) = 1 (4)

2. (0„ = Мо) & (00 = М) & (О = CMD) = 1 (5)

3. (00 = М„) & (Он = Мо) & (О = CMD) = 1 (6)

4. (00 = М„) & (0„ = М) & (О = CMD)= 1 ' (7)

Тем не менее, попарное рассмотрение предельных случаев множественных пересечений (4), (5), (6), (7) приводит к возможности выделить наиболее общий случай множественного пересечения. При этом значимыми парами предельных случаев являются: (4) и (5); (5) и (6); (6) и (7).

При рассмотрении выражений (4) и (5) видно, что отличие заключается в первом члене конъюнкции. При этом Он = М является частным случаем 0„ - Н>, так как Он = М = М„МЦМ0 = И,, если Мн и Мц представить пустыми словами. В то же время обратное равенство Он = И, = М„МцМо = М не является верным, так как в данном случае нельзя утверждать, что Мн и Мц являются пустыми словами. Таким образом, выражение (4) является частным случаем (5). Исходя из этого, (4) и (5) можно объединить в (5).

При рассмотрении выражений (5) и (6) можно утверждать, что О0 - М является частным случаем 0„ = М„, так как 00 = М = М„МЦМ0 = М„, если Мц и М0 представить пустыми словами. В то же время обратное равенство 00 - Мн -М„МцМ0 = М не является верным, так как в данном случае нельзя утверждать, что Мц и М0 являются пустыми словами. Таким образом, выражение (5) является частным случаем (6). Исходя из этого, (5) и (6) можно объединить в (6).

К выражениям (6) и (7), в свою очередь, можно применить рассуждения аналогичные рассуждениям по выражениям (4) и (5), что позволяет рассматривать (7), как частный случай (6). Таким образом, выражение (7) являются частным случаем (6). Исходя из этого, (6) и (7) можно объединить в

(6).

Выражение (6) является наиболее общим случаем множественных пересечений в продукции. При рассмотрении всех возможных комбинаций типов пересечений из выражения (6), установлено, что потенциально конфликтную ситуацию могут создать продукции, удовлетворяющие

следующей конъюнкции:

(00 = М„)&(0 = СМ0)=1 (Ю

Таким образом, конъюнкция (8) является индикатором продукции, потенциально создающей конфликтную ситуацию.

Для обоснования корректности вычислений при множественных пересечениях частей продукций доказаны следующие утверждения

Утверждение 1. Если в продукции присутствуют множественные пересечения образца и модификатора, состоящие из центрального (О - СМБ) и правостороннего (О. = Мн) пересечений, то приоритет срабатывания принадлежит продукции с центральным аннулирующим процессом.

Утверждение 2. Если в продукции присутствуют множественные пересечения образца и модификатора, состоящие из центрального (О - СМВ) и левостороннего (Он = М0) пересечений, то приоритет срабатывания принадлежит продукции с центральным аннулирующим процессом.

Основой доказательства данных утверждений- является структурно-лингвистический анализ конструктивных объектов (слов с итерационными фрагментами) на предмет эквивалентности результирующего слова, полученного по возвратному и безвозвратному принципам вычислений. Структурно-лингвистический анализ слов основан на их равноправном множественном представлении (рис. 1), порождающем различные варианты разложения текущего слова на составные части и задающем различные конструктивные процессы преобразования.

ькт

I

ь

Ь О Я ь о л Рис. 1. Варианты разбиения цепочки 1МЯ: ЬД - слова в заданном алфавите А; Ь,„ Ь0 иЯ,Л - собственные начала и окончания слов ЬД соответственно (начала и окончания могут быть пустыми); М„, М„, Н, - собственные начало, тело (центр) и окончание цепочки М (начала и окончания могут быть пустыми).

Вышеприведенные рассуждения позволили разработать метод разрешения конфликтных ситуаций при множественных пересечениях. Сущность метода заключается в такой расстановке приоритетов конфликтующих пересечений слов, чтобы обеспечить, с одной стороны безотступность вычислений, и, с другой стороны, корректность результата. При определении дизъюнкцией (2) множественных пересечений и возникновении конфликтной ситуации, приоритет выполнения присваивается продукциям в следующем порядке:

1) продукция с центральным типом пересечения (О = СМС>)

2) продукция с правосторонним типом пересечения (00 = Мн)

3) продукция с левосторонним типом пересечения (Он =

Доказанная последовательность срабатывания конфликтующих

продукций обеспечивает корректность результата при выполнении безотступной технологии вычислений.

В третье главе описана структурная схема специализированного устройства с однородной операционной частью для параллельной замены строк на основе ассоциативной матрицы, а так же схемотехнические решения функциональных узлов, участвующих в процессах замещения, раздвижки вставки и корректирующего удаления символов в строке. Разработаны метод реконфигурации для параллельной замены строк и алгоритм функционирования специализированного устройства замены строки (далее устройство замены) для практически значимых длин образца и модификатора. Производится оценка аппаратной сложности разработанного устройства.

Для создания алгоритма представляется целесообразным дать краткое описание базовой продукционной операции модификации данных (краткую постановку задачи модификации).

Задача замены строки формулируется следующим образом. Пусть в рабочем алфавите А заданы объекты:

- строка-образец О длиной т символов, где О еА*, О = 0!02...0т;

- строка-модификатор Р длиной г символов, где РеА* Р = п,п, п 0<г<2ш;

- обрабатываемая строка Б длиной к символов, где веА*, 8 = (к<п-ш ), п-натуралыюе число.

Требуется найти и осуществить замену первого вхождения О на Р в Я, т.е. разработать такой алгоритм, что справедливо

АЛ-А^-у»), 1 < / < м' = к — т + \,

три

Э;((0(1,/н) = Б(и + т-1))|(5 = где к>0, т>(),№>().

При реализации операции замены подстрок следует рассмотреть варианта соотношения длин образца О и модификатора Р:

1) ш <г;

2) т = г;

3) т>г.

Первый вариант (ш<г) включает последовательность шагов замещения, раздвижки, вставки и корректирующего удаления символов из обрабатываемой строки, второй и третий варианты основаны на процессах замещения или удаления символов из обрабатываемой строки соответственно. Данное обстоятельство позволяет рассматривать первый вариант, как общий предельный случай реализации операции замены подстрок.

Параллельная замена строки обеспечивается путем представления исходной строки 8 длиной до к=пхш символов в виде двухмерной матрицы из п строк по т символов в каждой строке, где ш число символов в образце. На рис. 2 представлено пошаговое выполнение операции замены для случая т < г при А={0,1} и Б=1101100111100110, 0=1001 и Р=110011.

Модификатор Р представляется в виде двух подстрок Р1, Р2 по т символов каждый. При этом выравнивание символов в Р2 выполняется по правому краю, а не заполненные разряды Р2 дополняются 0 (на рис. 2 такие разряды для наглядности отмечены символом «х»).

Рх= Р2 = 0= Б =

Рх =

Р2 = 0= Й =

110 X X 0 10 0

1 1 0 1

1 0 0 1

1 1 1 0

0 1 1 0

а)

110 0 1111 х х 0 1 10 0 1

0= Б =

10 0 1

1 1 0 1

1 1 0 0

1 1 1 0

0 1 1 0

Мх

1 1 о о

М,=

1101

1 о

б)

1 1 0 0

—

1 1 1 0

0 1 1 0

М1 1 1 о о

о=

1 0 0 1 мп

В)

10 0 1

1 1 0 0 0 1 1 0 0 0

X X 0 1 1 0 1 1 1 1

1 1 1 0 1 1 0 0 1 1

0 1 1 0 1 1 0 — 1

д)

е)

Рис. 2. Пошаговое выполнение операции замены Метод реконфи1урации для параллельной замены строк реализуется следующим образом. Подстрока Р1 длиной в т символов подается на информационные входы матрицы и в параллельном коде замещает данные в ¡-й

строке матрицы, где ¡- номер строки матрицы, выбранной для операции замены. Управление номером строки матрицы осуществляется на основе внешней маски строк М1, содержащей единственную логическую «1» в 1-ой позиции 0 = 2 на рис. 2а). После замещения первой подстроки Р1 выполняется загрузка нового значения маски М1 (рис. 26), которая своими логическими «1» выделяет «верхнюю» часть матрицы. На основе установленного значения маски М1 с подачей т тактовых импульсов выполняется сдвиг влево на ш символов над элементами строки 8 только в выделенной части матрицы (рис. 2в). Процессы, отраженные на рис. 2в, приводят к освобождению ¡-ой строки матрицы для дальнейших преобразований, а выдвигаемые первые т символов строки Э поступают на информационный выход матрицы.

Следующий этап данного метода заключается в том, что на информационные входы матрицы подается подстрока Р2 длиной в ш символов. На рис. 2г представлена вставка в параллельном коде второй подстроки Р2 в 1-ую строку, ранее освобожденную сдвигом.

Следующий этап операции параллельной замены подстрок связан с загрузкой нового значения маски строк М1 (рис. 2д), которая своими логическими «1» выделяет «нижнюю» часть матрицы. На заключительном этапе на основе установленного значения маски М1 с подачей 2ш-г тактовых импульсов выполняется сдвиг влево на 2ш-г символов над элементами строки 8 только в выделенной части матрицы (рис. 2е). Процессы, отраженные на рис. 2е, приводят к удалению 2ш-г незначащих разрядов из ¡-ой строки матрицы и формированию корректного результата.

В случае, если г=ш, то операция замены строки сводится лишь к выполнению этапа замещения в параллельном коде модификатора Р вместо образца О (рис. 2а). В случае, если г<ш, то операция замены строки выполняется в два этапа: этап замещения строки-образца на строку-модификатор (рис. 2а) и этап сдвига влево на ш-г символов над элементами строки 8 только в «нижней» части матрицы (рис. 2е).

В итоге разработан метод, основанный на динамической реконфигурации структуры данных, (метод реконфигурации для модификации данных), который заключается в следующем:

• на нечетных шагах метода производится параллельная замена разрядов замаскированной строки матрицы на разряды модификатора (или его части);

• на четных шагах, производится реконфигурация матрицы из двумерной структуры данных в одномерную, что позволяет выполнять сдвиг замаскированных строк матрицы;

• однонаправленный процесс модификации завершается при условии, когда все символы из последней строки матрицы сдвинуты в вышестоящую строку матрицы.

Устройство замены содержит блок синхронизации и выбора режима работы, блок адресации строк, блок хранения образцов (11АМ1), блок хранения модификаторов (ЯАМ2), блок хранения строк (ЯАМЗ), операционный блок, блок результатов опроса (рис. 3).

Рис. 3. Структурно-функциональная организация устройства с однородной операционной частью Новизна структурно-функциональной устройства замены состоит в возможности динамического формирования маски и выделения с ее помощью рабочей области матрицы для выполнения шагов замещения, раздвижки, вставки или корректирующего удаления символов.

Основным блоком устройства является операционный блок, который работает в одном из пяти состояний: запись, чтение, ассоциативный поиск, реконфигурация, замена строки. Схема операционного блока представлена на рис. 4.

Рис. 4. Схема операционной части устройства замены

Граф-схема алгоритма работы однородного операционного блока при выполнении операции замены изображена на рис. 5.

Новизна разработанного алгоритма состоит в аппаратной реализации четырех шагов: замещения, раздвижки, вставки и корректирующего удаления символов при выполнении базовой продукционной операции замены строк.

(_ Нкадо ^

-РЕЖИХГ.0 "СТАРТ 1"*0 •СТАРТ 2"=0

\ ВЛ<

тежим*»1 "СТАРТ |-=1 ■СТАРТ 2*^0

метриты

! ■РЕЖИМ'-О . "СТАРТ 1-50 "СТАРТ 2"=0

1

■РЕЖИМА 1 'СТАРТ 1"»0 ■СТАРТ

уия алеаметэ«

ОЧ?

! ___

С "о—Ц ^ ( Кони

Рис. 5. Граф-схема алгоритма работы однородного операционного блока при выполнении операции замены Основным элементом однородного операционного блока является ассоциативная запоминающая ячейка, схема которой представлена на рис. 6, содержащая выделенный элемент 26 сравнения кода хранимого в ЯЗ-тригтсрс символа строки и кода текущего символа образца.

Рис. 6. Схема ассоциативного запоминающего элемента однородного операционного блока

Динамическое выделение строк матрицы в операционном блоке производится с помощью преобразователя кода (рис. 7), который выполняет преобразование единичного позиционного кода в нормализованный унитарный код. Например, для выделения «верхней» части матрицы, преобразователь кода исходную последовательности 01...0М1,0,+1...0П, преобразует в последовательность 1,...1А+1...0„, где 1-й. - «верхняя» часть матрицы, п -общее число строк в матрице.

9п

82 ' 8л

Рис. 7. Структурная организация преобразователя кода Преобразователь кода состоит из п-однородных ячеек 1 ]-Нп (Рис.8), каждая из которых выполняет преобразование одного разряда исходной последовательности, подаваемой на входы 81-Н$„. Результирующий нормализованный унитарный код подается на выходы 9^9П. Два управляющих сигнала («СТАРТ 1» и «СТАРТ 2»), указывают направление нормализации (левая, правая), что позволяет выделять «верхнюю» и «нижнюю» части матрицы.

! ±1-7

3

И

Рис. 8. Схема ячейки преобразователя кода Выполнена оценка аппаратных затрат разработанного устройства. Результаты расчета аппаратной сложности приведены в табл. 1. Устройство замены имеет наибольшую аппаратную сложность при минимальной длине образца. С увеличением длины образца аппаратная сложность устройства падает до точки соотношения длин образца и текста 1:5, после чего начинает расти.

Таблица 1

Длина строки 1000 1000 1000 1000 1000 1000 1000

Длина образца 10 50 100 200 500 800 1000

Количество транзисторов 4475846 1321086 978896 894726 1122384 1470084 1661870

В четвертой главе выполняется экспериментальная проверка работы устройства с однородной операционной частью для параллельной замены, проводится сравнительный анализ скорости работы безотступной замены при разрешении конфликтных ситуаций с помощью разработанного метода. Рассматривается процесс моделирования устройства в среде ОиаПт II.

В целях получения скоростных характеристик и аппаратной сложности разработанного устройства параллельной замены, проведено его моделирование в среде Quartus II на ПЛИС Stratix III EP3SE50F484C2.

В соответствии с разработанной структурно-функциональной организацией основной вычислительной составляющей устройства параллельной замены является операционный блок. Схема имитационной модели операционного блока устройства представлена на рис. 9.

Lpsg "С ff| 1 г « i= ~ J; jtj;

h к pJ и

Рис. 9. Схема имитационной модели операционного блока однородного устройства в системе моделирования (ЗиагШБ Сравнение характеристик разработанного устройства производится с характеристиками условного циклического сдвигателя. Имитационная модель данного устройства так же создана в системе (ЗиагШв II.

Для моделирования устройств были выбраны следующие типовые параметры: длина образца - 4 символа (бита), длина модификатора — 8 символов (8 бит), длина строки - 20 символов (бит). Результаты моделирования приведены в табл. 2.

Таблица 2

Аппаратная сложность и скоростные показатели

Устройство Аппаратная сложность (LUT) Частота (Мгц) Время обработки тестового примера

Известный циклический условный сдвигатель 28 240 ~1080мс

Разработанное устройство замены с однородной операционной частью 188 210 ~240мс

Разработанный метод разрешения конфликтных ситуаций при множественных пересечения в продукции исследовался с помощью программного моделирования в сравнение с классическим возвратным методом замены. При определении алгоритмической сложности процессов замены под элементарной операцией понималась операция сравнения одного символа образца и одного символа текста на текущем шаге работы алгоритма, так же подсчитывалось число возвратов на первый символ обрабатываемого слова.

Результаты экспериментальной оценки временных затрат процессов замены всех вхождений для рассматриваемых методов приведены в таблицах 34 (для количества вхождений образцов 5 и 20 соответственно). При этом варьируемыми параметрами являлись длина генерируемого текста и число образцов входящих в строку, а статичными - мощность алфавита (2 символа), длина образца (4 символа), длина модификатора (4 символа). Базовая продукционная операция замены строк производилась по следующей методике:

1. Ввод продукции с конфликтным пересечением.

2. Генерация 10000 текстов заданной длины и с заданным количеством образцов равномерно распределенных по всему тексту.

3. Замещение в соответствии с методами замены всех вхождений образца на модификатор в каждом из сгенерированных текстов с фиксацией промежуточных результатов.

4. Получение средних значений количества сопоставлений символов и количества возвратных переходов в пространстве текста.

Таблица 3

Результаты экспериментальной оценки временной сложности методов замены (в

обрабатываемой строке 5 образцов)

Метод \ Длина текста (символы) 1000 5000

Сравнения Возвраты Сравнения Возвраты

Метод замены с возвратными переходами 4504 5 22585 5

Метод безотступной замены 1000 0 5000 0

Соотношение -4,5 - -4,5 -

Таблица 4

Результаты экспериментальной оценки временной сложности методов замены (в _обрабатываемой строке 20 образцов)_

Метод \ Длина текста (символы) 1000 5000

Сравнения Возвраты Сравнения Возвраты

Метод замены с возвратными переходами 12415 20 60836 20

Метод безотступной замены 1000 0 5000 0

Соотношение -12,4 - -12,2 -

Анализ результатов экспериментальных временных оценок методов замены (возвратный и безвозвратный) показал, что увеличение длины строки при неизменном числе образцов в строке, не влияет на соотношение числа операций сравнений. Рост числа образцов в строке, пропорционально

увеличивает соотношение числа операций сравнений, производимых методами, что увеличивает трудоемкость стандартной (с возвратами) реализации базовой операции замены строк.

В заключении сформулированы основные результаты и выводы диссертации.

В приложениях листинги программных модулей моделирующего приложения и акты внедрения результатов исследований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

В работе достигнута поставленная цель, заключающаяся в разработке метода разрешения конфликтов, метода реконфигурации, алгоритма и схемотехнических решений блоков и узлов для специализированного однородного реконфигурируемого устройства обработки символьной информации и решена научно-техническая задача поддержки параллельных вычислений на основе продукционных систем и специализированных устройств для реализации высокоскоростных символьных вычислений.

1. Создан метод разрешения конфликтных ситуаций для безотступной реализации операции замены в продукционной парадигме символьных вычислений. Метод основан на анализе множественных пересечений частей продукций, с последующей расстановкой приоритетов их срабатывания, что позволяет задать детерминированную схему срабатывания продукций.

2. Разработан метод реконфигурации для параллельной замены строк, основанный на матричном представлении обрабатываемой строки, а так же на динамической реконфигурации структуры данных и динамическом формировании маски для выделения рабочей области матрицы, что позволяет выполнять операцию замены всех вхождений за один направленный просмотр для практически значимых соотношений длин строк.

3. Разработана структурно-функциональная организация специализированного устройства с однородной операционной частью для параллельной замены, новизной которой является возможность динамического формирования маски и выделения с ее помощью рабочей области матрицы для выполнения шагов замещения, раздвижки, вставки и корректирующего удаления символов, а так же разработаны схемотехнические решения основных блоков и узлов специализированного устройства.

4. Разработан алгоритм работы устройства с однородной операционной частью, реализующий метод реконфигурации для параллельной замены строк, отличающийся применением безвозвратной параллельной технологии замены по столбцам ассоциативной матрицы, а так же возможностью выполнения-замены для практически значимых соотношениях длин строк, что открывает пути эффективного применения устройства в качестве символьного спецпроцессора-акселератора.

5. Проведенные экспериментальные исследования скоростных характеристик разработанного устройства на ПЛИС Б^йх III ЕР38Е50Р484С2 в среде (ЗиаПиБ II, показали, что однородное устройство для практически значимых ситуаций имеет скоростное преимущество в 4-5 раз по отношению к известному циклическому условному сдвигателю. Оценка аппаратной

сложности разработанного однородного устройства позволила получить рациональное, с точки зрения аппаратных затрат на отдельную ячейку матрицы, соотношение длин образца и текста, которое составило 1:5. Оценка временной сложности методов замены показала, что при длине строки в 1000 символов и 5 вхождениях соотношение скоростных характеристик возвратного метода и разработанного акселерационного метода составляет 4,5, при увеличении числа вхождений до 20 соотношение увеличивается до 12,4.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Рецензируемые научные журналы и издания

1. Гордиенко, В.В. Инструментальные средства организации символьных вычислений. Краткая история и перспективы. Часть 2. / В.В. Гордиенко, В.М. Довгань, И.С. Зерин [и др.]// Информационно-измерительные и управляющие системы. — 2009. №11. — М.:, Издательство «Радиотехника». — С. 72-76.

2. Зерин, И.С. Инструментальные средства акселерации символьных вычислений в системах обработки текстовой информации / И.С. Зерин, В.М. Довгаль, A.C. Ткаченко [и др.]// Экономика, статистика и информатика. Вестник УМО. - Научно-практический журнал. - 2011, №5. - С. 157-160.

3. Зерин, И.С. Инструментальные средства акселерации преобразования тестовой информации в системах обработки данных / И.С. Зерин, В.М. Довгаль, A.C. Ткаченко [и др.] // Естественные и технические науки. - 2011, № 5. - С. 254-255.

4. Емельянов, С.Г. Однородные вычислительные структуры для параллельных символьных вычислений / С.Г. Емельянов, Е.А. Титенко, И.С. Зерин // Известия Юго-Западного государственного университета. - 2011, №6(39). 4.2.-С. 77-82.

J. Зерин, И.С. Инструментальные средства быстрой обработки текстов в системах управления документами типовых организаций / И.С. Зерин, В.М. Довгаль, Л.Б. Белов // Информационно-измерительные и управляющие системы. -2011,№11,т.9.-С. 72-76.

6. Зерин, И.С. Метод, алгоритм и техническое решение параллельного поиска и подстановки на ассоциативной памяти / И.С. Зерин, О.И. Атакищев, Е.А. Титенко [и др.]// В мире научных открытий. Математика. Механика. Информатика. - Научный журнал. - 2012, №1. - С. 166-180.

Другие публикации

7. Довгаль, В.М. Автоматическая генерация акселерационной формы продукции / В.М. Довгаль, И.С. Зерин // Оптико - электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознование - 2008: сб. материалов VIII Междунар. конф. Ч. 1. - Курск, 2008. - С. 173-175.

8. Ткаченко, A.C. Усовершенствованный алгоритм поиска образца в продукции в символьных вычисления / A.C. Ткаченко, И.С. Зерин, A.B. Авдеев [и др.] // Компьютерные технологии в науке, производстве, социальных и экономических процессах: Материалы IX Междунар. Науч.-практ. Конф. (г.Новочеркасск. 7 нояб. 2008 г.). - Новочеркасск: ЮРГТУ, 2008. - С. 62-64.

9. Авдеев, A.B. Исследование возможностей акселерации классических алгоритмов символьной обработки в ERP-системах / A.B. Авдеев, И.С. Зерин, A.C. Ткаченко [и др.] // Компьютерные технологии в науке, производстве, социальных и экономических процессах: Материалы IX Междунар. Науч.-практ. Конф. (г.Новочеркасск. 7 нояб. 2008 г.). - Новочеркасск: ЮРГТУ, 2008. - С. 6467.

10. Зерин, И.С. К вопросу о применении акселерационных форм продукции в системах под держки принятия решений для социально-экономических объектов / И.С. Зерин, A.B. Авдеев, A.C. Ткаченко [и др.] // Компьютерные технологии в науке, производстве, социальных и экономических процессах: Материалы IX Междунар. Науч.-практ. Конф. (г.Новочеркасск. 7 нояб. 2008 г.). -Новочеркасск: ЮРГТУ, 2008. - С. 67-69.

11. Зерин, И.С. К вопросу об одном механизме акселерации обработки символьной информации с использованием продукционной парадигмы / И.С. Зерин // Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (1-5 декабря 2009 г. Россия, Ульяновск): сборник научных трудов. В 4 т. Т. 2. - Ульяновск: УлГТУ, 2009. - С. 467-469.

12. Зерин, И.С. К вопросу об одном механизме акселерации процесса замены образца на модификатор в марковских продукциях / И.С. Зерин // Оптико -электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание - 2010: сб. материалов IX Междунар. конф.; Курск, гос. техн. ун-т. - Курск, 2010. - С. 207209.

Свидетельство о регистрации программы

13. Свидетельство о государственной регистрации программы для ЭВМ. Программный продукт для преобразования линейных алгоритмов символьной обработки в параллельно-конвейерные формы / Зерин И.С., Довгаль В.М- per №2008612281, 08.05.2008.

Заявка на изобретение

14. Заявка 2010119752. Ассоциативная запоминающая матрица маскированного поиска вхождений / И.С. Зерин [и др.] (РФ.). М.: РосПатент; заявлено: 17.05.2010, приоритет: 17.05.2010.

Подписано в печать 27 апреля 2012 г. Формат 60x84 1/16. Печ.л. 1,0. Тираж 120 экз. Заказ /3 Юго-Западный государственный университет. 305040, г.Курск, ул. 50 лет Октября, 94.

61 12-5/2949

Юго-Западный государственный университет

и ......

На правах рукописи

Зерин Иван Сергеевич

МЕТОД, АЛГОРИТМ И СПЕЦИАЛИЗИРОВАННОЕ УСТРОЙСТВО ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ

05.13.05 - Элементы и устройства вычислительной техники

и систем управления

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель к.т.н., доцент Титенко Е.А.

КУРСК-2012

СОДЕРЖАНИЕ

Введение..........................................................................................................................4

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ АППАРАТНЫХ АРХИТЕКТУР И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ.........................................................................10

1Л. Обработка символьной информации и быстрые символьные

вычисления...................................................................................................10

1.2. Аппаратные архитектуры для высокопроизводительных вычислений. Анализ их ограничений........................................................17

1.2.1. CISC и RISC-архитектуры..............................................................18

1.2.2. Суперскалярные и VLIW-процессоры..........................................23

1.2.3. Архитектуры с общей и распределенной памятью......................28

1.2.4. Символьные процессоры и архитектуры......................................32

1.2.5. Программируемые логические интегральные схемы..................34

1.2.6. Процессоры логического вывода...................................................37

1.3. Ассоциативно параллельные процессоры..................................................40

1.4. Анализ программных средств для символьных вычислений...................46

1.5. Сущность предлагаемого подхода..............................................................53

1.6. Выводы по главе...........................................................................................54

ГЛАВА 2. РАЗРАБОТКА МЕТОДА РАЗРЕШЕНИЯ

КОНФЛИКТОВ Г?И МНОЖЕСТВЕННЫХ ПЕРЕСЕЧЕНИЯХ ОБРАЗЦА И МОДИФИКАТОРА ПРОДУКЦИИ. ОБОСНОВАНИЕ ЛОГИЧЕСКОГО УСЛОВИЯ РАССТАНОВКИ ПРИОРИТЕТОВ ПРОДУКЦИЙ...........................................................................................................56

2.1. Конструктивные объекты. Отношения на словах....................................56

2.2. Алгоритмическая система А.А.Маркова...................................................58

2.3. Индикатор пересечений образца и модификатора продукции...............64

2.4. Безотступное выполнение операции замены............................................67

2.5. Множественные пересечения между образцом и

модификатором продукции........................................................................71

2.6. Конфликтные ситуации при срабатывании продукций с множественными пересечениями образца и модификатора...................83

2.7. Расстановка приоритетов срабатывания продукций................................86

2.8. Выводы по главе.........................................................................................90

ГЛАВА 3. РАЗРАБОТКА ТЕХНИЧЕСКИХ РЕШЕНИЙ И

СПЕЦИАЛИЗИРОВАННОГО УСТРОЙСТВА ПАРАЛЛЕЛЬНОЙ ЗАМЕНЫ СИМВОЛЬНОЙ ИНФОРМАЦИИ. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ

СПЕЦИАЛИЗИРОВАННОГО УСТРОЙСТВА ЗАМЕНЫ..................................92

3.1. Требования и предложения для схемотехнических решений и функциональные узлы для модификации символьных данных (строк)...........................................................................................................92

3.2. Схемотехническое решение и алгоритм для замены строк на

базе циклического условного сдвигателя..................................................98

3.2.1. Разработка структурно-функциональной организации устройства........................................................................................98

3.2.2. Разработка алгоритмов работы устройства и описание

его функционирования..................................................................101

3.3. Разработка специализированного устройства с однородной операционной частью для параллельной замены строк на

основе ассоциативной матрицы...............................................................103

3.3.1. Разработка метода реконфигурации для параллельной

замены строк на основе ассоциативной памяти.........................103

3.3.2. Разработка структурно-функциональной организации устройства замены.........................................................................106

3.3.3. Разработка структурных схем основных блоков

устройства замены.........................................................................108

3.3.4. Разработка алгоритмов работы устройства и описание

его функционирования..................................................................115

3.4. Расчет аппаратной сложности разработанных устройств......................126

3.5. Выводы по главе.........................................................................................132

ГЛАВА 4. МОДЕЛИРОВАНИЕ РАБОТЫ УСТРОЙСТВА

ПАРАЛЛЕЛЬНОЙ ЗАМЕНЫ ВХОЖДЕНИЙ И РАЗРАБОТАННОГО МЕТОДА РАЗРЕШЕНИЯ КОНФЛИКТОВ........................................................134

4.1. Синтез имитационной модели и моделирование работы

устройства замены с однородной операционной частью......................134

4.1.1. Описание моделирующей среды..................................................134

4.1.2. Синтез имитационной модели условного циклического сдвигателя.......................................................................................136

4.1.3. Синтез имитационной модели устройства замены с однородной операционной частью..............................................138

4.1.4. Анализ характеристик синтезированных моделей

устройств........................................................................................139

4.2. Программное моделирование работы разработанного метода разрешения конфликтных ситуаций........................................................142

4.2.1. Описание программно-аппаратной среды

моделирования...............................................................................142

4.2.2. Приложение для моделирования методов замены.....................143

4.2.3. Показатель скорости работы моделируемых методов...............144

4.2.4. Экспериментальные исследования скорости работы моделируемых методов.................................................................147

4.3. Выводы по главе.........................................................................................152

ЗАКЛЮЧЕНИЕ..........................................................................................................154

БИБЛИОГРАФИЧЕСКИЙ СПИСОК......................................................................156

ВВЕДЕНИЕ

Актуальность.

Современный этап развития устройств вычислительной техники (ВТ) характеризуется организацией параллельных вычислений с использованием таких форм распараллеливания, которые свойственны естественному интеллекту в части применения базовой схемы принятия решений «условие—»действие» [5,11]. Особая система правил (продукционная система) как формализация данной схемы, а также аппаратно-программные средства, поддерживающие базовые продукционные операции составляют основу продукционной парадигмы вычислений, применяемой для параллельной обработки символьной информации (ОСИ) [4,5,55].

Тем не менее, системы продукций и основные продукционные операции в них (точный или приблизительный поиск по образцу, пересечение/объединение/дополнение фрагментов строк, модификация данных, реконфигурация структуры и др.) получили ограниченную аппаратную поддержку в современной ВТ. Они, как правило, реализуются программно, что приводит к неудовлетворительным временным характеристикам специализированных устройств при решении задач ОСИ [9]. Повышенное внимание к вопросу временной оценки задач ОСИ объясняется тем, что процессы символьных вычислений присутствуют в компьютерных системах распознавания образов, системах поддержки принятия решений, основанных на моделях обработки знаний, естественноязыковых системах, криптографических системах, информационно-поисковых системах и др [1,9-13,32,58,60]. В целом, задачи ОСИ по экспертным оценкам занимают до 80% от общего объема прикладных вычислительных задач в различной постановке [1]. Экстенсивный подход к решению задач ОСИ заключается в применении известных типов архитектур вычислительных устройств и систем обработки числовой информации, что составляет основное противоречие исследования, не позволяющее достигнуть необходимой производительности символьных вычислений.

Создание нетрадиционных архитектур устройств ОСИ, основанных на идеологии PIM-процессоров (Processor In Memory), является перспективным направлением развития высокопроизводительных средств ВТ и определяет разработку технических решений (узлы, блоки операционной части) и алгоритмов работы, структурно-функциональной организации для однородных вычислительных устройств ОСИ с реконфигурируемой операционной частью [14,40,46,47].

Теоретические и прикладные исследования продукционных систем (ПС) рассматривались в работах А.А. Маркова, Н.М. Нагорного, Н.А. Шанина, В.И. Городецкого, В.М. Довгаля, А. Ньюэлла, М. Саймона, Дж. Люгера, Э. Поста и других ученых. Тем не менее, свойственные задачам ОСИ вопросы и технические решения предсказания и разрешения конфликтов при параллельном применении продукционных правил нашли частичное отражение в трудах известных ученых, что определяет актуальность исследования.

Научно-техническая задача - поддержка параллельных вычислений на основе продукционных систем и специализированных устройств для реализации высокоскоростных символьных вычислений.

Объект исследования - вычислительные процессы и устройства обработки символьной информации.

Предмет исследования - методы, алгоритмы и схемотехнические решения безотступной модификации строковых данных с итерационными фрагментами на основе продукционной парадигмы вычислений.

Цель работы заключается в сокращении затрат времени на поддержку символьных вычислений продукционных систем путем разработки метода разрешения конфликтов, метода реконфигурации, алгоритма и схемотехнических решений блоков и узлов для специализированного устройства с однородной операционной частью обработки символьной информации.

Основные задачи диссертационного исследования:

1. Анализ основных направлений развития вычислительных устройств для организации параллельных вычислений. Анализ ограничений существующих методов и аппаратных решений для поддержки базовых продукционных операций.

2. Разработка метода разрешения конфликтов для безотступной модификации символьных данных. Обоснование логического условия расстановки приоритетов продукций.

3. Разработка метода реконфигурации и алгоритма для поддержки базовой операции - модификации строковых данных (операции замены).

4. Разработка структурно-функциональной организации специализированного устройства с однородной операционной частью модификации символьных данных, алгоритма работы устройства, а также схемотехнических решений основных блоков и узлов.

5. Экспериментальная проверка работоспособности технических решений устройства, оценка аппаратной и временной сложности созданного устройства.

Методы исследования основаны на теории проектирования ЭВМ, схемотехнике, аппарате продукционных систем, ассоциативной памяти, математической логике, а также теории алгоритмов и прикладного программирования.

Научная новизна и результаты, выносимые на защиту:

1. Создан метод разрешения конфликтных ситуаций, основанный на анализе множественных пересечений частей продукций, с последующей расстановкой приоритетов их срабатывания и позволяющий задать детерминированную схему срабатывания продукций.

2. Создан метод реконфигурации для параллельной замены строк, основанный на динамической реконфигурации структуры данных (.матрица - строка) и динамическом формировании маски для выделения рабочей

области матрицы и позволяющий корректно выполнять операцию замены при произвольных сочетаниях длин образца и модификатора продукции.

3. Разработана структурно-функциональная организация специализированного устройства параллельной замены с однородной операционной частью, содержащей двумерный массив ячеек с реконфигурируемыми связями, а также функциональную схему формирования двоичных векторов-масок строк, что позволяет корректно выполнять безотступную модификацию данных при произвольных сочетаниях длин образца и модификатора продукции.

4. Разработан алгоритм параллельной замены текущего вхождения, состоящий из четырех аппаратных шагов (замещение, раздвижка, вставка и корректирующее удаление символов), основанный на управляемой циклической реконфигурацией массива элементов из одномерного в двумерный вид и обратно при выполнении аппаратных шагов и позволяющий корректно выполнять операцию замены по безотступной технологии.

Практическая ценность работы состоит в следующем:

1. Разработанный алгоритм замены, основанный на динамической реконфигурации структуры данных, а так же на динамическом выделении рабочей области матрицы, позволяет выполнять базовую операцию символьной обработки по безотступной технологии, что сокращает время

выполнения задач ОСИ.

2. Проведена оценка аппаратной сложности разработанного устройства, содержащего ассоциативную матрицу ячеек с реконфигурируемыми связями, которая показала, что с точки зрения аппаратных затрат на отдельную ячейку матрицы рациональным соотношением длин образца и текста является соотношение 1:5. Данное соотношение позволяет выбирать рациональную по аппаратным затратам ширину операционной части (матрицы) с учетом длин обрабатываемых данных.

3. Проведены экспериментальные исследования скоростных характеристик разработанного устройства, которые показали, что разработанное устройство имеет преимущество в 4-5 раз по отношению к циклическому условному сдвигателю (аналогу) на задаче модификации данных с типовыми параметрами (практически значимые длины фрагмента текста, образца модификатора, варьируемая позиция вхождения), что позволяет определить сферы применения разработанного устройства для

решения различных задач ОСИ.

Реализация результатов работы. Результаты диссертационной работы внедрены в НИЦ (г.Курск) ФГУП «18 ЦНИИ» МО РФ, используются в учебном процессе Юго-Западного государственного университета в рамках дисциплины «Системы искусственного интеллекта» кафедры программное обеспечение вычислительной техники, а также нашли применение в Курском ОАО «Прибор» (г. Курск) при создании спецузлов бортовых систем управления.

Апробация работы. Основные научные результаты работы докладывались и обсуждались на IX Международной Научно-практической Конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (г.Новочеркасск, 2008), II Международной научно-практической конференции «Ценности и интересы современного общества» (г.Курск, 2008), VIII Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображения и символьной информации» (г.Курск, 2008), Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г.Ульяновск, 2009), IX Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображения и символьной информации» (г.Курск, 2010), а также рассматривались на семинарах кафедры

вычислительной техники и программного обеспечения вычислительной техники Юго-Западного государственного университета в 2009-2012 гг.

Публикации по работе. По результатам выполненных разработок и исследований опубликованы 13 работ, в том числе 6 работ в рецензируемых научных журналах и изданиях, получено свидетельство о регистрации программы для ЭВМ №2008612281.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и двух приложений. Основное содержание диссертации изложено на 161 странице машинописного текста, содержит 28 рисунков, 15 таблиц и список литературы из 75 наименований.

Области возможного использования. Результаты диссертационной работы могут быть использованы при проектировании однородных устройств поддержки параллельных вычислений, а также аппаратных и/или программных акселераторов символьных вычислений.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ АППАРАТНЫХ АРХИТЕКТУР И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ

В данной главе производится анализ современных средств ОСИ, сравнительный анализ существующих программных средств и технических решений высокопроизводительной обработки информации.

По результатам анализа в этой главе, устанавливается роль и место предлагаемых методов и технически решений для обработки символьных данных на основе продукционной парадигмы и специализированных устройств для их реализации.

1.1. ОБРАБОТКА СИМВОЛЬНОЙ ИНФОРМАЦИИ И БЫСТРЫЕ

СИМВОЛЬНЫЕ ВЫЧИСЛЕНИЯ

В современной вычислительной технике [1] особое положение занимает символьная информация, поскольку она наряду с графической информацией является основой взаимодействия человека с компьютерными информационными системами [11]. Символьная информация, характеризующаяся огромными размерами данных со сложной внутренней логической структурой, ставит ряд специфических проблем, среди которых ведущее положение занимает проблема ее высокоскоростной обработки с применением безотступной технологии манипуляции фрагментами данных переменной длины. Проблема повышения производительности технических средств обработки символьной информации, решаемая путем создания быстродействующих дискретных преобразователей информации, функционирующих на основе продукционной парадигмы и содержащих внутрисистемные алгоритмические ср�