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

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

Оглавление
ВВЕДЕНИЕ
ГЛАВА 1. Аналитический обзор систем обработки символьной информации на основе операции сопоставления и сущность предлагаемого подхода

1.1. Особенности задач ОСИ.

1.2. Аппаратные средства ОСИ

1.2.1. Основные направления развития технических средств ОСИ

1.2.2. Особенности существующих технических средств ОСИ.

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

1.4. Выводы.

ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ.

АКСЕЛЕРАЦИИ ПРОЦЕССОВ СОПОСТАВЛЕНИЯ.
2.1. Основные понятия и определения конструктивной семиотики
2.2. Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления.
2.4. Конвейеризация процесса сопоставления
2.5. Алфавитный способ сопоставления ассоциативный
2.6 Повышение скорости путем организации параллельного поиска на
основе характеристической нульединичной матрицы
2.7. Выводы.
ГЛАВА 3. ОПИСАНИЕ ИЗВЕСТНЫХ УСТРОЙСТВ СОПОСТАВЛЕНИЯ И РАЗРАБОТКА МАТРИЧНОГО УСТРОЙСТВА
3.1. Описание последовательного устройства сопоставления
3.1.1. Описание структурной схемы устройства
3.1.2. Описание алгоритмов и работа устройства
3.2. Описание конвейерного устройства сопоставления.
3.2.1. Структурная схема устройства
3.2.2. Описание и функционирования алгоритмов работы устройства
3.3. Описание ассоциативного устройства сопоставления.
3.3.1. Описание структурной схемы устройства
3.3.2. Описание и функционирование алгоритмов работы устройства.
3.4. Разработка матричного устройства сопоставления.
3.4.1. Структура устройства.
3.4.2. Структура блока управления БУ
3.4.3. Структура устройства БМП.
3.4.4. Разработка алгоритмов работы устройства и описание его функционирования
3.5. Расчет аппаратной сложности устройств сопоставления
ГЛАВА 4. ЭКСПЕРЕМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СКОРОСТИ РАЗРАБОТАННЫХ УСТРОЙСТВ СОПОСТАВЛЕНИЯ.
4.1. Разработка программных моделей устройств сопоставления.
4.2. Разработка способа измерения времени, затрачиваемого эталонным компьютером на выполнение процессов сопоставления.
4.3. Анализ алгоритмической сложности процедуры сопоставления
4.4. Исследование временных характеристик моделируемых устройств .
4.4.1. Исследование временных харакгеристик устройств на образцах, в структуре которых нет итерации
4.4.2. Исследование скорости работы устройств на образцах, в струкгуре которых имеется итерация в начале слова
4.4.3. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в конце слова.
4.4.4. Исследование скорости работы устройст в на образцах, в структуре которых имеется итерация в начале и конце слова
4.4.5. Исследование работы устройств на образцах, в структуре которых есть итерация в середине слова.
4.4.6. Исследование скорости работы устройств на образцах, состоящих из итерации
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
ПРИЛОЖЕНИЕ 1.
ПРИЛОЖЕНИЕ 2.
ПРИЛОЖЕНИЕ 3.
ПРИЛОЖЕНИЕ 4.
ПРИЛОЖЕНИЕ 5.
ВВЕДЕНИЕ
Актуальность


Вместе с тем целесообразно локализовать процессы сопоставления в рамках символьных вычислений с целью определения нагрузки и ресурса средств эффективного по времени выполнения сопоставления. Признаки классификации аппаратных средств ОСИ различны архитектурные особенности, особенности элементной базы, тенденции развития, принципы разработки, методология обработки последовательная, параллельная, связная, метод обработки парадигма программирования, технология программирования и обработки информации и др. Машины, предназначенные непосредственно для ОСИ например, машины класса i с встроенными устройствами последовательного сопоставления. Символьные сопроцессоры и акселераторы с памятью, подключенные к универсальным ЭВМ в качестве спецпроцессоров например, фирмы i и имеющие специализированный программируемый модуль сопоставления программноаппаратная реализация. ЭВМ универсального применения с введенными в их систему специальных команд для эффективного решения задач символьной обработки и, соответственно, сопоставления например, микропроцессор 0, рабочая станция . Универсальные машины персональные компьютеры и рабочие станции, супермашины, мультипроцессорные системы, Viмашины и т. ОСИ. Приведенная классификация не учитывает еще одно перспективное направление обработки данных, которое основывается на реконфигурируемых процессорах на основе i , . Реконфигурируемые процессоры создаются на основе статических ОЗУ и представляют собой аппаратную базу для решения различных задач синтез и обработка изображений и сигналов, манипуляции с базами данных, решение задач САПР, задачи криптографии и др В них удачно достигается как гибкость программных реализаций, так и производительность специализированных процессоров. Основным преимуществом технологии является то, что реконфигурация позволяет аппаратно реализовать вычислительный процесс в соответствии с поставленной задачей, исключая необходимость в разработке нового устройства для каждой области приложений. Иллюстрацией практического воплощения технологии являются два оригинальных проекта система Парижская исследовательская лаборатория ii i и машина Исследовательский центр по суперкомпьютерам , США . В этом же классе технических средств известна также разработка системы i Vi фирма Vi , США, содержащая матрицы класса ХС или ХС, связанных между собой мя программируемыми коммутаторами I0 фирма I, США. Следует подчеркнуть, что специфика задач ОСИ определяет потребности в высокой степени параллелизма систем обработки информации. На сегодняшний день имеются существенные трудности, которые вытекают из общих проблем параллельного программирования, включая реконфигурацию, программирование матриц транспьютеров и многопроцессорных систем , а также сложность создания компиляторов и диспетчеров. Из анализа различных публикаций видно, что работы но созданию высокопроизводительных вычислительных средств ОСИ ведутся крупнейшими научными институтами многих стран мира и такими промышленными гигантами, как I, I, x I, i, iii, и др. Научными центрами и фирмамипроизводителями определяются возможности использования новой элементной базы и новых принципов построения машин ИС на основе технологии, оптоэлектроиика, нейронные машины и машины с систолической структурой и т. Следует отметить, что в приведенных аппаратных реализациях используется широкий спектр алгоритмов выполнения операции сопоставления. При этом в основном используется программная поддержка КМПалгоритма, в микропроцессоре символьного компьютера фирмы i применяется программноаппаратная реализация КМПалгоритма, а в системе 5 аппаратная поддержка операции сопоставления с анализируемой глубиной отступа. I 2 x. С развитием полупроводниковых технологий и совершенствованием внутренней архитектуры вычислительные возможности процессоров в сравнительно короткий срок возросли в десятки тысяч раз. Производительность зависит не только от тактовой частоты, на которой работает ядро, но и от количества ядер в одном корпусе. Специалисты I предложили новую архитектуру, обеспечивающую эффективное снижение показателя Ii энергии, затраченной на выполнение одной инструкции.