Введение к работе
Актуальность
Современное развитие вычислительной техники характеризуется тем, что простое повышение производительности ЭВМ не определяет качества обработки информации. Нужны новые подходы, которые формируются в рамках интеллектуализации вычислительных средств (ВСр), т.е. в наделении ВСр дополнительными возможностями анализа информации. Составляющей частью этого направления является развитие систем логического вывода (ЛВ).
Системы логического вывода могут использоваться как специализированные системы, в частности экспертные системы (ЭС), так и как важные составляющие части других систем обработки информации, например, при работе с традиционными базами данных (БД) для расширения их функциональных возможностей и повышения производительности. Таким образом, интеллектуализация ВСр представляет собой одну из ведущих тенденций в разработке ЭВМ нового поколения, и доля таких ВСр, как универсальных, так и специализированных, будет постоянно расти. Известные аппаратные решения и проекты специализированных процессоров ЛВ не удовлетворяют требованиям, предъявляемым современными системами ЛВ, поскольку их архитектура ориентирована либо на последовательную реализацию логических задач, либо на параллельную реализацию посредством большого числа процессорных элементов. Вследствие этого, необходимо выявить специфику логических задач и алгоритмов их реализации и учесть ее в архитектуре вновь разрабатываемых ВСр.
Логические задачи характеризуются тем, что сложность их может неограниченно возрастать, а это приводит к необходимости их реализации на параллельных ВСр. В то же время логические задачи имеют довольно малую ширину реального параллелизма и неравномерное распределение параллельных участков алгоритма ЛВ. В результате проблематичным является эффективное использование существующих параллельных ВСр для их решения.
з Специфика логических задач проявляется также в том, что их сложность
и ширина реализуемого параллелизма изменяются в очень широких пределах, вследствие чего использование специализированных аппаратных средств с фиксированной структурой также является нецелесообразным. Вследствие этого, при разработке архитектуры ВСр для поддержки ЛВ необходима разработка, исследование и модификация таких алгоритмов ЛВ, которые обеспечивали бы увеличение ширины реального параллелизма и сокращение сложности его основных этапов применительно к реализации на СБИС. Кроме того, эффективные архитектурные решения средств аппаратной поддержки ЛВ целесообразно искать на основе результатов, полученных в области реализации параллельных вычислений, и построении этих средств на принципах параллельности, переменности и модульности, сформулированных для модели коллектива вычислителей Э.В.Евреиновым. Эти принципы могут быть реально воплощены в рамках достижений теории однородных структур и перестраиваемых автоматов, разработанной Э.В. Евреиновым, Ю.Т. Косаревым, И.В. Прангишвили, Е.И. Пупыревым.
Основные результаты исследований и модификации алгоритмов ЛВ, полученные в данной работе, базируются на основе достижений в области разработки систем логического вывода, большой вклад в которую внесли такие ученые, как Робинсон Дж., МасловС., Ковальский Р., Колмероэ А., Уоррен Д.
Целью диссертационной работы являлось повышение производительности систем логического вывода путем разработки и исследования эффективных алгоритмов операций ЛВ и архитектуры вычислительных средств.
Достижение этой цели предполагало решение следующих задач:
анализа способов ускорения логического вывода на всех его этапах, в частности на этапе трансляции и обхода дерева логического вывода, с целью их систематизации и оценки возможности реализации; ;
разработки и исследования способов повышения реального параллелиз-
ма логических задач за счет выявления параллельных ветвей обработки, не тре
бующих обмена данными; _ . - - - -
снижения основной трудоемкости операций ЛВ и разработки на основе модификации их алгоритмов системы макрокоманд, ориентированных на аппаратурную реализацию и уменьшающих сложность этапа трансляции;
разработки и исследования структуры специализированных средств аппаратной поддержки логического вывода, удовлетворяющих требованиям модульности, перестраиваемое и наращиваемости их вычислительной мощности.
Основные методы исследования.
При решении поставленных задач в работе использовались методы тео- . рии вычислительных систем, однородных структур и перестраиваемых автоматов, логического вывода, имитационного моделирования и аппарат теории множеств.
Научная новизна полученных результатов заключается в том, что:
разработан способ увеличения ширины реального параллелизма логических задач, позволяющий применить для их решения параллельные ВСр;
разработана абстрактная машина ЛВ, система макрокоманд и алгоритмы их реализации для специализированного макропроцессора на основе модификации абстрактной машины Уоррена;
- разработана модульная структура специализированного макропроцессо
ра на основе перестраиваемых функционально автономных блоков.
Практическая значимость полученных результатов состоит в разработке способа повышения реального параллелизма логических задач, позволившего предложить эффективную структуру ВСр, обладающую оптимальными параметрами по скорости и загрузке системы для задач с различной шириной па-
раллелизма. Предложенные алгоритмы и структуры позволяют понизить трудоемкость операций ЛВ и повысить скорость обработки баз знаний большого объема в среднем на один-два порядка в зависимости от сложности решения задач по сравнению с известными аппаратными решениями.
Результаты диссертации использовались при разработке программы подготовки данных в рамках программного комплекса «Депонет» (ОАО «Реестр»), в комплексе научно-исследовательских программ по финно-угроведению (Научный центр финно-угроведения республики Марий-Эл) и в учебном процессе по дисциплинам "Организация ЭВМ, комплексов и систем", "Вычислительные комплексы, системы и сети" и "Архитектура ВС" для студентов специальности 22.01.00,22.03.00, 22.05.00.
Апробация результатов диссертации. Результаты исследований докладывались на конференциях:
- ежегодных научно-технических конференциях профессорско-
преподавательского состава МарГТУ, Йошкар-Ола, 1995-1997 гг.;
IX Всероссийской научно-технической конференции "Однородные вычислительные структуры, среды и распределенные системы", 1996 г., Москва;
Всероссийской научной конференции "Цифровая обработка многомерных сигналов", 1996 г., Йошкар-Ола;
LI научной сессии, посвященной дню радио, 1996 г., Москва;
третьей международной конференции по вопросам развития БД и информационных систем (ADBIS'96), 1996 г., Москва;
пятом международном симпозиуме по вопросам развития БД и информационных систем (ADBIS'97), 1997 г., Санкт-Петербург;
ежегодной НТК студентов и аспирантов вузов России «Радиоэлектроника и электротехника в народном хозяйстве», 1998 г., Москва.
6 Публикации результатов диссертации. По основным результатам дис-
ертационной работы опубликовано 15 работ, в том числе 5 статей, 10 тези-
ов докладов на конференциях, в том числе двух международных.
Структура и объем работы.
Диссертация состоит из введения, пяти глав с выводами, заключения, писка литературы и приложения. Основная часть работы изложена на 159 траницах машинописного текста и содержит 31 рисунков и 17 таблиц,