Введение к работе
Актуальность темы. Мир сейчас переживает третью компьютерную революцию, заключающуюся в преобразовании вычислительной машины из автономного аппарата в устройство лля связи с внешним миром и получения услуг. Подавляющее большинство современных приложений ЭВМ (по мнению экспертов - более 90%) оперирует информацией, представленной в символьной форме.
В тоже время, базовыми операциями процессорных элементов современных вычислительных машин остаются сложение, вычитание, умножение и сдвиг. Такой семантический разрыв между символьным характером обрабатываемых данных и числовыми методами их обработки оказывает существенное влияние на эффективность вычислений. Пользователям для повседневной работы приходится приобретать суперсовременные компьютеры, способные выполнять сотни миллионов арифметических операций в секунду, только для того, чтобы получить приемлемое время отработки мощных программных систем, требуемых для адаптации обрабатываемой символьной информации к системам команд имеющихся процессоров.
Работы над созданием высокоэффективных вычислительных устройств обработки символьной информации (ОСИ) ведутся как на уровне отдельных исследовательских институтов и фирм-производителей вычислительной техники, так и в рамках национальных и межгосударственных программ. Разработаны и выпускаются серийно большое количество различных специализированных и универсальных ЭВМ, процессоров и процессорных элементов ОСИ. Но до настоящего времени ни один из таких проектов с радикальными изменениями в архитектуре по сравнению с существующими не стал основой массовых машин широкого применения. Поэтому поиск эффективных методов обработки символьной информации и создание на их основе вычислительных устройств является актуальной и перспективной проблемой.
Работа выполнена по плану Госкомвуза РФ на 1992-1995 г.г. от '16.03.92 г. № 10-36-41, ИН/10-20-03. (тема "Разработка и исследование характеристик процессорных элементов систем обработки символьной информации"), а также по распоряжению Госкомвуза РФ от 19.02.93 г. К' 10 "Технические системы обработки символьной информации и изображений" (международный проект).
Цели и задачи. Цель диссертационной работы заключается в разработке средств акселерации работы систем продукций А. А. Маркова и построении на их основе высокопроизводительных последовательных устройств ОСИ.
Для достижения поставленной цели были решены следующие задачи.
-
Разработка способов модификации нормальных алгорифмов с целью повышения эффективности их применения для построения высокоскоростных устройств ОСИ.
-
Исследование применимости теории алгорифмов для автоматизации проектирования комбинационных схем.
-
Разработка эффективных алгоритмов реализации процессов ОСИ на основе модифицированных систем марковских продукций.
-
Моделирование работы последовательных устройств ОСИ, в основу алгоритмов функционирования которых положены модифицированные системы марковских продукций.
-
Разработка структур высокопроизводительных устройств ОСИ.
-
Разработка языка программирования верхнего уровня и его компиляторов на языки исполнительного уровня для каждого из разработанных устройств.
Методы исследования. В процессе решения поставленных задач использовались: теория алгоритмов, теория нормальных алгорифмов, конструктивная математическая логика, методы математического моделирования, теория цифровых авто-
матов, теория проектирования элементов и устройств вычислительной техники и систем управления.
Научная новизна работы состоит в следующем.
1. Предложены и исследованы средства акселерации ра
боты систем марковских продукций для реализации высоко
скоростных процессов ОСИ. Рассмотрены возможности исполь
зования служебных символов .для ускорения процессов пере
дачи управления на множестве продукций и повышения скоро
сти сканирования обрабатываемых слов, а также реализации
арифметических процессов; разработаны скоростные методы
конкатенации и обработки сложных атомарных структур дан
ных и реализации сильноветвящихся алгоритмов ОСИ. Введены
в рассмотрение в качестве средств акселерации алфавитные,
счетные и строковые конструктивы.
-
Предложен метод формального синтеза комбинационных схем по заданной схеме продукций, позволяющий получать функциональные схемы блоков устройств на основе их математических моделей, представленных в виде марковских алгорифмов.
-
Созданы высокоэффективные алгоритмы реализации последовательных процессов ОСИ, на их основе разработаны варианты структур устройств и осуществлено сопоставление данных устройств с известными техническими ревениями ПО показателям временной и аппаратной сложности.
Практическая ценность диссертационной работы:
разработаны технические решения трех вариантов устройств ОСИ последовательного принципа действия, отличающиеся минимальной аппаратной сложностью, при высоких скоростных показателях;
разработаны программные средства моделирования процессов ОСИ;
создан язык описания модифицированных систем марковских Продукций и компиляторы для его перевода на машинные языки предлагаемых вариантов устройств ОСИ;
разработаны оригинальные алгоритмы решения тестовых задач на базе модифицированных марковских продукций;
осуществлен структурный синтез параллельного двоичного знакоразрядного сумматора.
На защиту выносятся: 1. Методы модификации канонических марковских продукций для эффективной реализации конструктивных процессов, методы сокращения числа холостых шагов работы систем продукций, а также алфавитные конструктивы и шаблоны вхождений .
-
Арифметические и строковые конструктивы, "окна" просмотра (сканирования) обрабатываемых слов, базисные формы передачи управления и конкатенации фрагментов, а также способ синтеза комбинационных схем по заданной системе продукций.
-
Результаты исследования производительности устройств и средства моделирования процессов ОСИ на основе решения тестовых задач.
-
Алгоритмы функционирования, системы команд, структурные схемы и схемные решения блоков последовательных устройств ОСИ, результаты оценки их аппаратной сложности, а также язык программирования верхнего уровня и компиляторы для перехода к языкам исполнительного уровня для каждого варианта предлагаемых устройств.
Реализация и внедрение результатов исследований. Результаты диссертационной работы нашли применение при выполнении госбюджетных и хоздоговорных НИР Курского государственного технического университета (г/б-7, г/б-15, х/д-378), а также практически реализованы и внедрены в информационном центре УВД Курской области и учебном про-
цессе Курского государственного технического университета.
Апробация работы. Предварительные результаты диссертационной работы докладывались и получили положительную оценку на Международной научной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (Курск, 1993г.) и Юбилейной конференции ученых Курского политехнического института (Курск, 1994г..) .
Публикации. Результаты, полученные в диссертационной работе, нашли отражение в 5 печатных работах, 5 авторских свидетельствах и 1 патенте.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и заключения, содержащих 148 страниц основного текста, 55 рисунков и 27 таблиц, а также списка использованных источников из 84 наименований на 9 страницах и 14 приложений на 150 станицах;
