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

• Автор: Евсюков, Вячеслав Сергеевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Курск
• Количество страниц: 184 с. : ил.

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

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

1.1.1. Введение в теорию обработки символьной информации.

1Л.2. Современное состояние процессов обработки символьной

информации.

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

1Л .4. Быстрые символьные вычисления.

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

1.2.1. Архитектура Фон Неймана.

1.2.2. Гарвардская архитектура.
1.2.3. I и Iархитектуры.
1.2.4. Суперскалярные и VIпроцессоры
1.2.5. Процессоры логического вывода.
1.3. Классификации вычислительных систем.
1.4. Параллелизм вычислений и его типы.
1.4.1. Параллелизм на уровне инструкций
1.4.2. Параллелизм данных
1.4.3. Параллелизм задач.
1.4.4. Кластеризация вычислительных систем.
1.4.5. Закон Амдала
1.5. Программные методы для организации параллельных вычислений
1.6. Экспертные системы и символьная обработка.
1.7. Исчислительные продукционные системы
1.8. Сущность предлагаемого подхода к созданию методов параллельного поиска вхождений и пересечений символьных данных.
1.9. Выводы по главе.
ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ УСКОРЕНИЯ ПРОЦЕССОВ ПОИСКА ПРИ РАБОТЕ ИС ЧИСЛИТЕЛЬНЫХ ПРОДУКЦИОННЫХ СИСТЕМ.
2.1. Теоретический базис конструктивных символьных вычислений
2.2. Продукционные исчисления
2.3. Проблемы генерации ветвящихся конструктивных процессов
2.4. Теорема о конфликтных словах
2.5. Разработка методов параллельного поиска вхождений и пересечений символьных данных
2.5.1. Метод ассоциативного параллельного поиска вхождений.
2.5.2. Метод матричного параллельного поиска вхождений и пересечений
2.6. Выводы по главе.
ГЛАВА 3. РАЗРАБОТКА СПЕЦИАЛИЗИРОВАННЫХ УСТРОЙСТВ ПАРАЛЛЕЛЬНОГО ПОИСКА ВХОЖДЕНИЙ И ПЕРЕСЕЧЕНИЙ.
3.1. Технические устройства для поиска вхождений и пересечений.
3.2. Разработка ассоциативного устройства поиска вхождений.
3.2.1. Разработка структурнофункциональной организации устройства
3.2.2. Разработка структурных схем основных блоков устройства
3.2.3. Разработка алгоритмов работы устройства и описание его функционирования.
3.3. Разработка матричного устройства поиска вхождений и пересечений
3.3.1. Разработка структурнофункциональной организации устройства
3.3.2. Разработка структурных схем основных блоков устройства
3.3.3. Разработка алгоритмов работы устройства и описание его функционирования
3.4. Расчет аппаратной сложности разработанных устройств.
3.5. Выводы по главе.
ГЛАВА 4. МОДЕЛИРОВАНИЕ РАБОТЫ УСТРОЙСТВА ПАРАЛЛЕЛЬНОГО ПОИСКА ВХОЖДЕНИЙ И ПЕРЕСЕЧЕНИЙ И РАЗРАБОТАННЫХ МЕТОДОВ ПОИСКА ВХОЖДЕНИЙ И ПЕРЕСЕЧЕНИЙ.
4.1. Синтез имитационной модели и моделирование работы матричного устройства
4.1.1. Описание моделирующей среды.
4.1.2. Синтез имитационной модели.
4.1.3. Моделирование работы устройства.
4.2. Программное моделирование работы разработанных методов поиска
4.2.1. Описание программноаппаратной среды моделирования
4.2.2. Программные модели устройств.
4.2.3. Показатель скорости работы моделируемых устройств
4.2.4. Экспериментальные исследования скорости работы моделируемых устройств.
4.3. Выводы по главе
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ 3.
ВВЕДЕНИЕ
Актуальность


В области символьной обработки в настоящее время все шире используются регулярные выражения 1. Регулярные выражения система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец, задающий правило поиска, также иногда называют шаблоном, маской. Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Характерной особенностью языков символьной обработки данных является переход от линейной структуры памяти к более сложной и гибкой списочной структуре. Для систем искусственного интеллекта, систем поддержки принятия решений, экспертных систем и задач ОСИ активно используют Лиспориентированные вычислительные комплексы, для задач логического вывода Прологмашины. Данные программноаппаратные комплексы требуют высокой квалификации программистов, но позволяют решать специфичные для них задачи менее затратными методами. Языки программирования для символьной обработки данных представлены в табл. Таблица 1. Внут реннее однонапр. Распознавание по образцу огранич. Автоматический возврат отсутств. Главным отличием символьных архитектур процессоров от архитектур Фон Неймановского тина является минимально адресуемая единица представления данных. Если для числовых процессоров таковой единицей является бит байт данных, то для символьных архитектур это символ слово. Следовательно, символьные процессоры работают на более высоком уровне абстракции представления данных, не исключая выполнения специфичных для числовых процессоров задач. В виду того, что для символьных вычислений используется небольшое количество типовых операторов сравнение и подстановка их архитектура весьма напоминает ШБСпроцессоры. Но объем программного кода, скорость исполнения и суммарная эффективность системы зависят от того, насколько алгоритм, заложенный в программном коде, и процессор соответствуют друг другу. Говоря иначе, на символьном процессоре численные задачи будут выглядеть не лучше, чем на числовом процессоре символьные задачи. Однако, поскольку множество символов включает в себя числа как подмножество, символьные процессоры теоретически могут лучше работать с числами, чем числовые процессоры с символами, используя внутренний параллелизм однотипных операторов и множество данных. Символьные процессоры, как правило, выполняются в виде рекурсивных автоматов с программируемой логикой или матричных структур. Машины, предназначенные непосредственно для ОСИ например, машины класса i с встроенными устройствами последовательного сопоставления. Символьные сопроцессоры и акселераторы с памятью, подключенные к универсальным ЭВМ в качестве спецпроцессоров например, фирмы i и имеющие специализированный программируемый модуль сопоставления программноаппаратная реализация. ЭВМ универсального применения с введенными в их систему специальных команд для эффективного решения задач символьной обработки и, соответственно, сопоставления например, микропроцессор 0, рабочая станция . Универсальные компьютеры персональные компьютеры и рабочие станции, суперкомпьютеры, мультипроцессорные системы, VIмашины и т. ОСИ. Для числовых процессоров единица измерения производительности количество операций с плавающей запятой в секунду. Для символьных процессоров, в зависимости от их назначения, за единицу измерения производительности можно считать количество подстановок в секунду на заданном алфавите, наборе продукций и входном обрабатываемом слове или количество логических выводов в секунду I для систем искусственного интеллекта. Например, предполагалось, что прототип компьютера пятого поколения будет обладать производительностью между 0 млн. I, в то время, как типовые рабочие станции были способны на производительность около 0 тысяч I. Компьютеры пятого поколения широкомасштабная правительственная программа в Японии по развитию компьютерной индустрии и искусственного интеллекта, предпринятая в е годы .