Введение к работе
Актуальность.
Современный этап развития устройств вычислительной техники (ВТ) характеризуется организацией параллельных вычислений с использованием таких форм распараллеливания, которые свойственны естественному интеллекту в части применения базовой схемы принятия решений «условиедействие». Особая система правил (продукционная система) как формализация данной схемы, а также аппаратно-программные средства, поддерживающие базовые продукционные операции составляют основу продукционной парадигмы вычислений, применяемой для параллельной обработки символьной информации (ОСИ).
Тем не менее, системы продукций и основные продукционные операции в них (точный или приблизительный поиск по образцу, пересечение/объединение/дополнение фрагментов строк, модификация данных, реконфигурация структуры и др.) получили ограниченную аппаратную поддержку в современной ВТ. Они, как правило, реализуются программно, что приводит к неудовлетворительным временным характеристикам специализированных устройств при решении задач ОСИ. Повышенное внимание к вопросу временной оценки задач ОСИ объясняется тем, что процессы символьных вычислений присутствуют в компьютерных системах распознавания образов, системах поддержки принятия решений, основанных на моделях обработки знаний, естественно-языковых системах, криптографических системах, информационно-поисковых системах и др. В целом, задачи ОСИ по экспертным оценкам занимают до 80% от общего объема прикладных вычислительных задач в различной постановке. Экстенсивный подход к решению задач ОСИ заключается в применении известных типов архитектур вычислительных устройств и систем обработки числовой информации, что составляет основное противоречие исследования, не позволяющее достигнуть необходимой производительности символьных вычислений.
Создание нетрадиционных архитектур устройств ОСИ, основанных на идеологии PIM-процессоров (Processor In Memory), является перспективным направлением развития высокопроизводительных средств ВТ и определяет разработку технических решений (узлы, блоки операционной части) и алгоритмов работы, структурно-функциональной организации для однородных вычислительных устройств ОСИ с реконфигурируемой операционной частью.
Теоретические и прикладные исследования продукционных систем (ПС) рассматривались в работах А.А. Маркова, Н.М. Нагорного, Н.А. Шанина, В.И. Городецкого, В.М. Довгаля, А. Ньюэлла, М. Саймона, Дж. Люгера, Э. Поста и других ученых. Тем не менее, свойственные задачам ОСИ вопросы и технические решения предсказания и разрешения конфликтов при параллельном применении продукционных правил нашли частичное отражение в трудах известных ученых, что определяет актуальность исследования.
Научно-техническая задача – поддержка параллельных вычислений на основе продукционных систем и специализированных устройств для реализации высокоскоростных символьных вычислений.
Объект исследования – вычислительные процессы и устройства обработки символьной информации.
Предмет исследования – методы, алгоритмы и схемотехнические решения безотступной модификации строковых данных с итерационными фрагментами на основе продукционной парадигмы вычислений.
Цель работы заключается в сокращении затрат времени на поддержку символьных вычислений продукционных систем путем разработки метода разрешения конфликтов, метода реконфигурации, алгоритма и схемотехнических решений блоков и узлов для специализированного устройства с однородной операционной частью обработки символьной информации.
Основные задачи диссертационного исследования:
-
Анализ основных направлений развития вычислительных устройств для организации параллельных вычислений. Анализ ограничений существующих методов и аппаратных решений для поддержки базовых продукционных операций.
-
Разработка метода разрешения конфликтов для безотступной модификации символьных данных. Обоснование логического условия расстановки приоритетов продукций.
-
Разработка метода реконфигурации и алгоритма для поддержки базовой операции - модификации строковых данных (операции замены).
-
Разработка структурно-функциональной организации специализированного устройства с однородной операционной частью модификации символьных данных, алгоритма работы устройства, а также схемотехнических решений основных блоков и узлов.
-
Экспериментальная проверка работоспособности технических решений устройства, оценка аппаратной и временной сложности созданного устройства.
Методы исследования основаны на теории проектирования ЭВМ, схемотехнике, аппарате продукционных систем, ассоциативной памяти, математической логике, а также теории алгоритмов и прикладного программирования.
Научная новизна и результаты, выносимые на защиту:
-
Создан метод разрешения конфликтных ситуаций, основанный на анализе множественных пересечений частей продукций, с последующей расстановкой приоритетов их срабатывания и позволяющий задать детерминированную схему срабатывания продукций.
-
Создан метод реконфигурации для параллельной замены строк, основанный на динамической реконфигурации структуры данных (матрица – строка) и динамическом формировании маски для выделения рабочей области матрицы и позволяющий корректно выполнять операцию замены при произвольных сочетаниях длин образца и модификатора продукции.
-
Разработана структурно-функциональная организация специализированного устройства параллельной замены с однородной операционной частью, содержащей двумерный массив ячеек с реконфигурируемыми связями, а также функциональную схему формирования двоичных векторов-масок строк, что позволяет корректно выполнять безотступную модификацию данных при произвольных сочетаниях длин образца и модификатора продукции.
-
Разработан алгоритм параллельной замены текущего вхождения, состоящий из четырех аппаратных шагов (замещение, раздвижка, вставка и корректирующее удаление символов), основанный на управляемой циклической реконфигурацией массива элементов из одномерного в двумерный вид и обратно при выполнении аппаратных шагов и позволяющий корректно выполнять операцию замены по безотступной технологии.
Практическая ценность работы состоит в следующем:
-
Разработанный алгоритм замены, основанный на динамической реконфигурации структуры данных, а так же на динамическом выделении рабочей области матрицы, позволяет выполнять базовую операцию символьной обработки по безотступной технологии, что сокращает время выполнения задач ОСИ.
-
Проведена оценка аппаратной сложности разработанного устройства, содержащего ассоциативную матрицу ячеек с реконфигурируемыми связями, которая показала, что с точки зрения аппаратных затрат на отдельную ячейку матрицы рациональным соотношением длин образца и текста является соотношение 1:5. Данное соотношение позволяет выбирать рациональную по аппаратным затратам ширину операционной части (матрицы) с учетом длин обрабатываемых данных.
-
Проведены экспериментальные исследования скоростных характеристик разработанного устройства, которые показали, что разработанное устройство имеет преимущество в 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 наименований.
