Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

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

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

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

АВТОРЕФЕРАТ

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

КУРСК - 2012

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

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

Официальные оппоненты: Фисун Александр Павлович, доктор технических наук, профессор, филиал ФГУП РЧЦ ЦФО в Орловской области (г.

Орел), заместитель директора филиала Мусакин Евгений Юрьевич, кандидат технических наук, доцент, НИЦ (г.Курск) ФГУП л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 - Элементы и устройства вычислительной техники и систем управления по пункту Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения техникоэкономических и эксплуатационных характеристик.

Апробация работы. Основные научные результаты работы докладывались и обсуждались на 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 рисунков, таблиц и список литературы из 75 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Во введении обоснована актуальность темы по организации и аппаратной поддержке параллельных вычислений в рамках аппарата продукционных систем, а так же сформулированы цель и задача исследования, научная новизна и основные положения выносимые на защиту, практическая ценность работы, и другие характеристики работы.

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

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

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

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

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

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

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

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

O M, (1) где O - образец, M - модификатор. O и M - слова в заданном алфавите A, - является метасимволом, не принадлежащим A.

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

Безвозвратность вычислений достигается благодаря использованию конструктивной дизъюнкции:

(Oо = Mн)V(Oн = Mо)V(Оо = М)V(Он = М)V(O = CMD), (2) где Он, Оо - собственные начало и окончание образца соответственно, Мн, Мо - собственные начало и окончание модификатора соответственно, C и D - слова в заданном алфавите А.

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

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

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

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

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

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

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

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

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

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

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

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

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

Для обоснования корректности вычислений при множественных пересечениях частей продукций доказаны следующие утверждения Утверждение 1. Если в продукции присутствуют множественные пересечения образца и модификатора, состоящие из центрального (O = CMD) и правостороннего (Oо = Mн) пересечений, то приоритет срабатывания принадлежит продукции с центральным аннулирующим процессом.

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

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

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

LMR LM M M R LM M RН RО LН LО M Н M О R LН LО M M R Н - О Н О Н О | | | | | | | | L O R L O R L O R L O R Рис. 1. Варианты разбиения цепочки LMR:

L,R - слова в заданном алфавите А; Lн, Lo и Rн, Ro - собственные начала и окончания слов L,R соответственно (начала и окончания могут быть пустыми);

Mн, Мц, Мо - собственные начало, тело (центр) и окончание цепочки М (начала и окончания могут быть пустыми).

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

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

1) продукция с центральным типом пересечения (O = CMD) 2) продукция с правосторонним типом пересечения (Oо = Mн) 3) продукция с левосторонним типом пересечения (Oн = Mо) Доказанная последовательность срабатывания конфликтующих продукций обеспечивает корректность результата при выполнении безотступной технологии вычислений.

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

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

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

Ц строка-образец O длиной m символов, где O A*, O = o1o2Еom;

Ц строка-модификатор P длиной r символов, где P A*, P = p1p2Еpr, 0

Ц обрабатываемая строка S длиной k символов, где S A*, S = s1s2Еsk, (knm ), n-натуральное число.

Требуется найти и осуществить замену первого вхождения O на P в S, т.е. разработать такой алгоритм, что справедливо i((O(1,m) S(i,i m 1)) (S s s...s p p...p s...s ),1 i w, w k m 1, 1 2 i 1 1 2 r i m k где k>0, m>0,w>0.

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

1) m < r;

2) m = r;

3) m > r.

Первый вариант (m

Параллельная замена строки обеспечивается путем представления исходной строки S длиной до k=nm символов в виде двухмерной матрицы из n строк по m символов в каждой строке, где m число символов в образце. На рис.

2 представлено пошаговое выполнение операции замены для случая m < r при А={0,1} и S=1101100111100110, O=1001 и P=110011.

Модификатор P представляется в виде двух подстрок P1, P2 по m символов каждый. При этом выравнивание символов в P2 выполняется по правому краю, а не заполненные разряды P2 дополняются 0 (на рис. 2 такие разряды для наглядности отмечены символом x).

P1= 1 1 0 P2= x x 0 1 М1= 1 1 1 O= 1 0 0 1 M1 O= 1 0 0 1 M1 1 0 0 1 MS= 1 1 0 1 0 S= 1 1 0 1 1 1101 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 а) б) в) P1= 1 1 0 P2= x x 0 O= 1 0 0 1 M1 O= 1 0 0 1 M1 1 0 0 1 MS= 1 1 0 0 0 S= 1 1 0 0 0 1 1 0 0 1 x x 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 г) д) е) Рис. 2. Пошаговое выполнение операции замены Метод реконфигурации для параллельной замены строк реализуется следующим образом. Подстрока P1 длиной в m символов подается на информационные входы матрицы и в параллельном коде замещает данные в i-й строке матрицы, где i- номер строки матрицы, выбранной для операции замены.

Управление номером строки матрицы осуществляется на основе внешней маски строк М1, содержащей единственную логическую л1 в i-ой позиции (i = 2 на рис. 2а). После замещения первой подстроки P1 выполняется загрузка нового значения маски M1 (рис. 2б), которая своими логическими л1 выделяет верхнюю часть матрицы. На основе установленного значения маски M1 с подачей m тактовых импульсов выполняется сдвиг влево на m символов над элементами строки S только в выделенной части матрицы (рис. 2в). Процессы, отраженные на рис. 2в, приводят к освобождению i-ой строки матрицы для дальнейших преобразований, а выдвигаемые первые m символов строки S поступают на информационный выход матрицы.

Следующий этап данного метода заключается в том, что на информационные входы матрицы подается подстрока P2 длиной в m символов.

На рис. 2г представлена вставка в параллельном коде второй подстроки P2 в iую строку, ранее освобожденную сдвигом.

Следующий этап операции параллельной замены подстрок связан с загрузкой нового значения маски строк M1 (рис. 2д), которая своими логическими л1 выделяет нижнюю часть матрицы. На заключительном этапе на основе установленного значения маски M1 с подачей 2m-r тактовых импульсов выполняется сдвиг влево на 2m-r символов над элементами строки S только в выделенной части матрицы (рис. 2е). Процессы, отраженные на рис. 2е, приводят к удалению 2m-r незначащих разрядов из i-ой строки матрицы и формированию корректного результата.

В случае, если r=m, то операция замены строки сводится лишь к выполнению этапа замещения в параллельном коде модификатора P вместо образца O (рис. 2а). В случае, если r

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

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

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

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

Устройство замены содержит блок синхронизации и выбора режима работы, блок адресации строк, блок хранения образцов (RAM1), блок хранения модификаторов (RAM2), блок хранения строк (RAM3), операционный блок, блок результатов опроса (рис. 3).

CLOCK +1 АдрМод +1 АдрОбр CLOCK ЧтОбр Чт/Зп мод +1 АдрСтр Блок управления и ЧтСтр Блок адресации Выб синхронизации ЧтМод Чт/Зп стр Чт/Зп обр Выб Выб Битовые RAM образцы DO DI A Битовые RAM Заявление на строки Битовый патент № Е R/W образец DO DI CS Битовая строка A Операционный блок Битовые RAM модифи R/W каторы Битовый DO DI CS модифи каторы A R/W CS Адрес вхождений Блок результатов поиска Рис. 3. Структурно-функциональная организация устройства с однородной операционной частью Новизна структурно-функциональной устройства замены состоит в возможности динамического формирования маски и выделения с ее помощью рабочей области матрицы для выполнения шагов замещения, раздвижки, вставки или корректирующего удаления символов.

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

Рис. 4. Схема операционной части устройства замены ПУСК СТОП П код д строк Адреса CLOCK K СБРОС С РЕЖИМ М СТАРТ СТАРТ матрицы Результат Настроечный й опроса а столбцов в Результаты ы Результаты ы опроса строк строк строка Результирующая Граф-схема алгоритма работы однородного операционного блока при выполнении операции замены изображена на рис. 5.

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

Начало длины модификатора Сигналы на ин- больше длины образца формационные входы матрицы "СБРОС"=1 "CLOCK"=Адрес строки для замены "РЕЖИМ"="СТАРТ 1"="СТАРТ 2"=0 Параллельная замена "РЕЖИМ"="СТАРТ 1"=Перекоммута- "СТАРТ 2"=ция элементов матрицы Сигналы на ин- формационные "РЕЖИМ"=входы матрицы "СТАРТ 1"="CLOCK"="СТАРТ 2"=Перекоммута- "CLOCK"=Запись новых ция элементов логических матрицы уровней параллельная замена "РЕЖИМ"="CLOCK"=длины образца и "СТАРТ 1"=модификатора равны "СТАРТ 2"=Запись новых логических уровней Результирующая Результирующая строка строка Конец Конец Рис. 5. Граф-схема алгоритма работы однородного операционного блока при выполнении операции замены Основным элементом однородного операционного блока является ассоциативная запоминающая ячейка, схема которой представлена на рис. 6, содержащая выделенный элемент 26 сравнения кода хранимого в RS-триггере символа строки и кода текущего символа образца.

Рис. 6. Схема ассоциативного запоминающего элемента однородного операционного блока Динамическое выделение строк матрицы в операционном блоке производится с помощью преобразователя кода (рис. 7), который выполняет преобразование единичного позиционного кода в нормализованный унитарный код. Например, для выделения верхней части матрицы, преобразователь кода исходную последовательности 01Е0i-11i0i+1Е0n, преобразует в последовательность 11Е1i0i+1Е0n, где 1 i - верхняя часть матрицы, n - общее число строк в матрице.

Рис. 7. Структурная организация преобразователя кода Преобразователь кода состоит из n-однородных ячеек 111n (Рис.8), каждая из которых выполняет преобразование одного разряда исходной последовательности, подаваемой на входы 818n. Результирующий нормализованный унитарный код подается на выходы 919n. Два управляющих сигнала (СТАРТ 1 и СТАРТ 2), указывают направление нормализации (левая, правая), что позволяет выделять верхнюю и нижнюю части матрицы.

Рис. 8. Схема ячейки преобразователя кода Выполнена оценка аппаратных затрат разработанного устройства.

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

Таблица Результаты расчета аппаратной сложности однородного устройства Длина 1000 1000 1000 1000 1000 1000 10строки Длина 10 50 100 200 500 800 10образца Количество 4475846 1321086 978896 894726 1122384 1470084 16618транзисто- ров В четвертой главе выполняется экспериментальная проверка работы устройства с однородной операционной частью для параллельной замены, проводится сравнительный анализ скорости работы безотступной замены при разрешении конфликтных ситуаций с помощью разработанного метода.

Рассматривается процесс моделирования устройства в среде Quartus II.

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

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

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

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

Таблица Аппаратная сложность и скоростные показатели разработанных устройств Устройство Аппаратная Частота (Мгц) Время обработки сложность тестового (LUT) примера Известный циклический 28 240 ~1080мс условный сдвигатель Разработанное устройство 188 210 ~240мс замены с однородной операционной частью Разработанный метод разрешения конфликтных ситуаций при множественных пересечения в продукции исследовался с помощью программного моделирования в сравнение с классическим возвратным методом замены. При определении алгоритмической сложности процессов замены под элементарной операцией понималась операция сравнения одного символа образца и одного символа текста на текущем шаге работы алгоритма, так же подсчитывалось число возвратов на первый символ обрабатываемого слова.

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

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

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

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

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

Таблица Результаты экспериментальной оценки временной сложности методов замены (в обрабатываемой строке 5 образцов) Метод \ Длина текста 1000 50(символы) Сравнения Возвраты Сравнения Возвраты Метод замены с 4504 5 22585 возвратными переходами Метод безотступной замены 1000 0 5000 Соотношение ~4,5 - ~4,5 - Таблица Результаты экспериментальной оценки временной сложности методов замены (в обрабатываемой строке 20 образцов) Метод \ Длина текста 1000 50(символы) Сравнения Возвраты Сравнения Возвраты Метод замены с 12415 20 60836 возвратными переходами Метод безотступной замены 1000 0 5000 Соотношение ~12,4 - ~12,2 - Анализ результатов экспериментальных временных оценок методов замены (возвратный и безвозвратный) показал, что увеличение длины строки при неизменном числе образцов в строке, не влияет на соотношение числа операций сравнений. Рост числа образцов в строке, пропорционально увеличивает соотношение числа операций сравнений, производимых методами, что увеличивает трудоемкость стандартной (с возвратами) реализации базовой операции замены строк.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ В работе достигнута поставленная цель, заключающаяся в разработке метода разрешения конфликтов, метода реконфигурации, алгоритма и схемотехнических решений блоков и узлов для специализированного однородного реконфигурируемого устройства обработки символьной информации и решена научно-техническая задача поддержки параллельных вычислений на основе продукционных систем и специализированных устройств для реализации высокоскоростных символьных вычислений.

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

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

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

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

5. Проведенные экспериментальные исследования скоростных характеристик разработанного устройства на ПЛИС Stratix III EP3SE50F484C2 в среде Quartus II, показали, что однородное устройство для практически значимых ситуаций имеет скоростное преимущество в 4-5 раз по отношению к известному циклическому условному сдвигателю. Оценка аппаратной сложности разработанного однородного устройства позволила получить рациональное, с точки зрения аппаратных затрат на отдельную ячейку матрицы, соотношение длин образца и текста, которое составило 1:5. Оценка временной сложности методов замены показала, что при длине строки в 1000 символов и вхождениях соотношение скоростных характеристик возвратного метода и разработанного акселерационного метода составляет 4,5, при увеличении числа вхождений до 20 соотношение увеличивается до 12,4.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Рецензируемые научные журналы и издания 1. Гордиенко, В.В. Инструментальные средства организации символьных вычислений. Краткая история и перспективы. Часть 2. / В.В. Гордиенко, В.М.

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

2. Зерин, И.С. Инструментальные средства акселерации символьных вычислений в системах обработки текстовой информации / И.С. Зерин, В.М.

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

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

254-255.

4. Емельянов, С.Г. Однородные вычислительные структуры для параллельных символьных вычислений / С.Г. Емельянов, Е.А. Титенко, И.С.

Зерин // Известия Юго-Западного государственного университета. - 2011, №6(39). Ч.2. - С. 77 - 82.

5. Зерин, И.С. Инструментальные средства быстрой обработки текстов в системах управления документами типовых организаций / И.С. Зерин, В.М.

Довгаль, Л.Б. Белов // Информационно-измерительные и управляющие системы.

Ц 2011, №11, т.9. - С. 72 - 76.

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

Информатика. - Научный журнал. - 2012, №1. - С. 166-180.

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

конф. Ч.1. - Курск, 2008. - С. 173-175.

8. Ткаченко, А.С. Усовершенствованный алгоритм поиска образца в продукции в символьных вычисления / А.С. Ткаченко, И.С. Зерин, А.В. Авдеев [и др.] // Компьютерные технологии в науке, производстве, социальных и экономических процессах: Материалы IX Междунар. Науч.-практ. Конф.

(г.Новочеркасск. 7 нояб. 2008 г.). - Новочеркасск: ЮРГТУ, 2008. - С. 62-64.

9. Авдеев, А.В. Исследование возможностей акселерации классических алгоритмов символьной обработки в ERP-системах / А.В. Авдеев, И.С. Зерин, А.С. Ткаченко [и др.] // Компьютерные технологии в науке, производстве, социальных и экономических процессах: Материалы IX Междунар. Науч.-практ.

Конф. (г.Новочеркасск. 7 нояб. 2008 г.). - Новочеркасск: ЮРГТУ, 2008. - С. 6467.

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

11. Зерин, И.С. К вопросу об одном механизме акселерации обработки символьной информации с использованием продукционной парадигмы / И.С.

Зерин // Всероссийская конференция с элементами научной школы для молодежи Проведение научных исследований в области обработки, хранения, передачи и защиты информации (1-5 декабря 2009 г. Россия, Ульяновск):

сборник научных трудов. В 4 т. Т. 2. - Ульяновск: УГТУ, 2009. - С. 467-469.

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

материалов IX Междунар. конф.; Курск. гос. техн. ун-т. - Курск, 2010. - С. 207209.

Свидетельство о регистрации программы 13. Свидетельство о государственной регистрации программы для ЭВМ.

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

№2008612281, 08.05.2008.

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

заявлено: 17.05.2010, приоритет: 17.05.2010.

Подписано в печать 27 апреля 2012 г. Формат 60х84 1/16. Печ.л. 1,0.

Тираж 120 экз. Заказ ____.

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

305040, г.Курск, ул. 50 лет Октября, 94.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям