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

• Автор: Зерин, Иван Сергеевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Курск
• Количество страниц: 191 с. : ил.

СОДЕРЖАНИЕ
Введение
ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ АППАРАТНЫХ АРХИТЕКТУР И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ
1Л. Обработка символьной информации и быстрые символьные
вычисления
1.2. Аппаратные архитектуры для высокопроизводительных вычислений. Анализ их ограничений
1.2.1. С1БС и ШБС-архитектуры
1.2.2. Суперскалярные и УЫУ-процессоры
1.2.3. Архитектуры с общей и распределенной памятью
1.2.4. Символьные процессоры и архитектуры
1.2.5. Программируемые логические интегральные схемы
1.2.6. Процессоры логического вывода
1.3. Ассоциативно параллельные процессоры
1.4. Анализ программных средств для символьных вычислений
1.5. Сущность предлагаемого подхода
1.6. Выводы по главе
ГЛАВА 2. РАЗРАБОТКА МЕТОДА РАЗРЕШЕНИЯ
КОНФЛИКТОВ Г РИ МНОЖЕСТВЕННЫХ ПЕРЕСЕЧЕНИЯХ ОБРАЗЦА И МОДИФИКАТОРА ПРОДУКЦИИ. ОБОСНОВАНИЕ ЛОГИЧЕСКОГО УСЛОВИЯ РАССТАНОВКИ ПРИОРИТЕТОВ ПРОДУКЦИЙ
2.1. Конструктивные объекты. Отношения на словах
2.2. Алгоритмическая система А.А.Маркова
2.3. Индикатор пересечений образца и модификатора продукции
2.4. Безотступное выполнение операции замены
2.5. Множественные пересечения между образцом и
модификатором продукции
2.6. Конфликтные ситуации при срабатывании продукций с множественными пересечениями образца и модификатора
2.7. Расстановка приоритетов срабатывания продукций
2.8. Выводы по главе
ГЛАВА 3. РАЗРАБОТКА ТЕХНИЧЕСКИХ РЕШЕНИЙ И
СПЕЦИАЛИЗИРОВАННОГО УСТРОЙСТВА ПАРАЛЛЕЛЬНОЙ ЗАМЕНЫ СИМВОЛЬНОЙ ИНФОРМАЦИИ. СТРУКТУРНОФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ
СПЕЦИАЛИЗИРОВАННОГО УСТРОЙСТВА ЗАМЕНЫ
3.1. Требования и предложения для схемотехнических решений и функциональные узлы для модификации символьных данных (строк)

3.2. Схемотехническое решение и алгоритм для замены строк на
базе циклического условного сдвигателя
3.2.1. Разработка структурно-функциональной организации устройства
3.2.2. Разработка алгоритмов работы устройства и описание
его функционирования
3.3. Разработка специализированного устройства с однородной операционной частью для параллельной замены строк на
основе ассоциативной матрицы
3.3.1. Разработка метода реконфигурации для параллельной
замены строк на основе ассоциативной памяти
3.3.2. Разработка структурно-функциональной организации устройства замены
3.3.3. Разработка структурных схем основных блоков
устройства замены
3.3.4. Разработка алгоритмов работы устройства и описание
его функционирования
3.4. Расчет аппаратной сложности разработанных устройств
3.5. Выводы по главе
ГЛАВА 4. МОДЕЛИРОВАНИЕ РАБОТЫ УСТРОЙСТВА
ПАРАЛЛЕЛЬНОЙ ЗАМЕНЫ ВХОЖДЕНИЙ И РАЗРАБОТАННОГО МЕТОДА РАЗРЕШЕНИЯ КОНФЛИКТОВ
4.1. Синтез имитационной модели и моделирование работы
устройства замены с однородной операционной частью
4.1.1. Описание моделирующей среды
4.1.2. Синтез имитационной модели условного циклического сдвигателя
4.1.3. Синтез имитационной модели устройства замены с однородной операционной частью
4.1.4. Анализ характеристик синтезированных моделей
устройств
4.2. Программное моделирование работы разработанного метода разрешения конфликтных ситуаций
4.2.1. Описание программно-аппаратной среды
моделирования
4.2.2. Приложение для моделирования методов замены
4.2.3. Показатель скорости работы моделируемых методов
4.2.4. Экспериментальные исследования скорости работы моделируемых методов
4.3. Выводы по главе
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК

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

зарубежных производителей и представляют собой объединение множества традиционных коммерчески доступных процессорных узлов. Подобные решения имеют существенные недостатки, связанные с невысокой скоростью межпроцессорного обмена, а так же в довольно больших накладных расходах связанных с необходимостью синхронизации множества процессов. Эти недостатки не так существенны при решении независимых друг от друга задач, однако при решении задач, трудно поддающихся распараллеливанию производительность подобных систем составляет 5-10% от пиковой [36].
Если идти по пути копирования западных образцов, отставание будет только нарастать. В этой ситуации перспективным является направление реконфигурируемых многопроцессорных вычислительных систем. Такой подход позволяет пользователю программировать архитектуры системы под специфику решаемой задачи, с целью получения производительности близкой к пиковой. Данная концепция развивается давно и была отражена в работах A.B. Каляева [37], Э.В. Евреинова [38], В.Г. Хорошевского [39].
Исследования реконфигурируемых многопроцессорных
вычислительных систем развивалась по двум направлениям - однородные вычислительные структуры и многопроцессорные вычислительные системы с программируемой архитектурой. Однородная вычислительная структура представляет собой матрицу одинаковых и одинаково соединенных друг с другом универсальных ячеек, каждая из которых может быть запрограммирована на выполнение логической функции. Ячейка при этом является универсальным вычислительным элементом, который является простейшим однобитовым процессором, который выполняет операцию над одним поступившим разрядом данных.
При реализации многопроцессорных вычислительных систем с программируемой архитектурой было предложено строить процессорный узел из нескольких элементарных процессоров, при этом каждый из таких макропроцессор мог реализовывать более сложные операции над данными