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

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

Современный этап развития устройств вычислительной техники (ВТ) характеризуется организацией параллельных вычислений с использованием таких форм распараллеливания, которые свойственны естественному интеллекту в части применения базовой схемы принятия решений «условие—"действие» [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 работ в рецензируемых научных журналах и изданиях, получено свидетельство о регистрации программы для ЭВМ № 2 008 612 281.

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

4.3. ВЫВОДЫ ПО ГЛАВЕ.

1. Моделирование в среде (ЗиаЛш разработанного устройства параллельной замены с однородной операционной частью и устройства аналога в виде условного циклического сдвигателя показало, что при длине текста в 20 символов и длине образца в 4 символа разработанной устройство с однородной операционной частью обладает аппаратной сложностью в 6,7 раза по сравнению с устройство аналогом.

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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