автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Организация аппаратно-программных средств системы дедуктивного логического вывода

Государственный комитет Российской Федерации по высшему образованию

Марийский государственный технический университет

1 • ОД

и Е^ЬЗ На правах рукописи

удк 681.324

Васяева Наталия Семеновна

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

Специальность 05.13.13 - «Вычислительные комплексы, системы и сети»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Йошкар-Ола -1998

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

Научный руководитель - кандидат технических наук, доцент

A.А. Власов

Официальные оппоненты:

доктор технических наук, профессор

B.Н. Вагин

кандидат технических наук, старший научный сотрудник Ю.С. Затуливетер

Ведущая организация: Институт высокопроизводительных вычислений и баз данных (г. Санкт-Петербург)

Защита состоится 8 июня 1998 г. в «_» часов на заседании Специализ*

рованного Совета Д002.68.01 института проблем управления РАН по адрес 117806, Москва, ГСП-7, ул. Профсоюзная, 65

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан «_» мая 1998 г.

Ученый секретарь

специализированного

совета, кандидат технических наук

Е.В. Юркевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность

Современное развитие вычислительной техники характеризуется тем, что простое повышение производительности ЭВМ не определяет качества обработки информации. Нужны новые подходы, которые формируются в рамках интеллектуализации вычислительных средств (ВСр), т.е. в наделении ВСр дополнительными возможностями анализа информации. Составляющей частью этого направления является развитие систем логического вывода (ЛВ).

Системы логического вывода могут использоваться как специализированные системы, в частности экспертные системы (ЭС), так и как важные составляющие части других систем обработки информации, например, при работе с традиционными базами данных (БД) для расширения их функциональных возможностей и повышения производительности. Таким образом, интеллектуализация ВСр представляет собой одну из ведущих тенденций в разработке ЭВМ нового поколения, и доля таких. ВСр, как универсальных, так и специализированных, будет постоянно расти. Известные аппаратные решения и проекты специализированных процессоров ЛВ не удовлетворяют требованиям, предъявляемым современными системами ЛВ, поскольку их архитектура ориентирована либо на последовательную реализацию логических задач, либо на параллельную реализацию посредством большого числа процессорных элементов. Вследствие этого, необходимо выявить специфику логических задач и алгоритмов их реализации и учесть ее в архитектуре вновь разрабатываемых ВСр.

Логические задачи характеризуются тем, что сложность их может неограниченно возрастать, а это приводит к необходимости их реализации на параллельных ВСр. В то же время логические задачи имеют довольно малую ширину реального параллелизма и неравномерное распределение параллельных участков алгоритма ЛВ. В результате проблематичным является эффективное использование существующих параллельных ВСр для их решения.

Специфика логических задач проявляется также в том, что их сложность и ширина реализуемого параллелизма изменяются в очень широких пределах, вследствие чего использование специализированных аппаратных средств с фиксированной структурой также является нецелесообразным. Вследствие этого, при разработке архитектуры ВСр для поддержки ЛВ необходима разработка, исследование и модификация таких алгоритмов ЛВ, которые обеспечивали бы увеличение ширины реального параллелизма и сокращение сложности его основных этапов применительно к реализации на СБИС. Кроме того, эффективные архитектурные решения средств аппаратной поддержки ЛВ целесообразно искать на основе результатов, полученных в области реализации параллельных вычислений, и построении этих средств на принципах параллельности, переменности и модульности, сформулированных для модели коллектива вычислителей Э.В.Евреиновым. Эти принципы могут быть реально воплощены в рамках достижений теории однородных структур и перестраиваемых автоматов, разработанной Э.В. Евреиновым, Ю.Т. Косаревым, И.В. Прангишвили, Е.И. Пупыревым.

Основные результаты исследований и модификации алгоритмов ЛВ, полученные в данной работе, базируются на основе достижений в области разработки систем логического вывода, большой вклад в которую внесли такие ученые, как Робинсон Дж., МасловС., Ковальский Р., Колмероэ А., Уоррен Д.

Целью диссертационной работы являлось повышение производительности систем логического вывода путем разработки и исследования эффективных алгоритмов операций ЛВ и архитектуры вычислительных средств.

Достижение этой цели предполагало решение следующих задач:

- анализа способов ускорения логического вывода на всех его этапах, в частности на этапе трансляции и обхода дерева логического вывода, с целью их систематизации и оценки возможности реализации; ;

- разработки и исследования способов повышения реального параллелиз-

ма логических задач за счет выявления параллельных ветвей обработки, не требующих обмена данными; _ ____________ - - - -------

- снижения основной трудоемкости операций ЛВ и разработки на основе модификации их алгоритмов системы макрокоманд, ориентированных на аппаратурную реализацию и уменьшающих сложность этапа трансляции;

- разработки и исследования структуры специализированных средств аппаратной поддержки логического вывода, удовлетворяющих требованиям модульности, перестраиваемое™ и наращиваемости их вычислительной мощности.

Основные методы исследования.

При решении поставленных задач в работе использовались методы тео- . рии вычислительных систем, однородных структур и перестраиваемых автоматов, логического вывода, имитационного моделирования и аппарат теории множеств.

Научная новизна полученных результатов заключается в том, что:

- разработан способ увеличения ширины реального параллелизма логических задач, позволяющий применить для их решения параллельные ВСр;

- разработана абстрактная машина ЛВ, система макрокоманд и алгоритмы их реализации для специализированного макропроцессора на основе модификации абстрактной машины Уоррена;

- разработана модульная структура специализированного макропроцессора на основе перестраиваемых функционально автономных блоков.

Практическая значимость полученных результатов состоит в разработке способа повышения реального параллелизма логических задач, позволившего предложить эффективную структуру ВСр, обладающую оптимальными параметрами по скорости и загрузке системы для задач с различной шириной па-

раллелизма. Предложенные алгоритмы и структуры позволяют понизить трудоемкость операций ЛВ и повысить скорость обработки баз знаний большого объема в среднем на один-два порядка в зависимости от сложности решения задач по сравнению с известными аппаратными решениями.

Результаты диссертации использовались при разработке программы подготовки данных в рамках программного комплекса «Депонет» (ОАО «Реестр»), в комплексе научно-исследовательских программ по финно-угроведению (Научный центр финно-угроведения республики Марий-Эл) и в учебном процессе по дисциплинам "Организация ЭВМ, комплексов и систем", "Вычислительные комплексы, системы и сети" и "Архитектура ВС" для студентов специальности 22.01.00,22.03.00, 22.05.00.

Апробация результатов диссертации. Результаты исследований докладывались на конференциях:

- ежегодных научно-технических конференциях профессорско-преподавательского состава МарГТУ, Йошкар-Ола, 1995-1997 гг.;

- IX Всероссийской научно-технической конференции "Однородные вычислительные структуры, среды и распределенные системы", 1996 г., Москва;

- Всероссийской научной конференции "Цифровая обработка многомерных сигналов", 1996 г., Йошкар-Ола;

- П научной сессии, посвященной дню радио, 1996 г., Москва;

- третьей международной конференции по вопросам развития БД и информационных систем (АВВ1Б'96), 1996 г., Москва;

- пятом международном симпозиуме по вопросам развития БД и информационных систем (АВВ18'97), 1997 г., Санкт-Петербург;

- ежегодной НТК студентов и аспирантов вузов России «Радиоэлектроника и электротехника в народном хозяйстве», 1998 г., Москва.

Публикации результатов диссертации. По основным результатам дис-ертационной работы опубликовано 15 работ, в том числе 5 статей, 10 тези-ов докладов на конференциях, в том числе двух международных.

Структура и объем работы.

Диссертация состоит из введения, пяти глав с выводами, заключения, писка литературы и приложения. Основная часть работы изложена на 159 траницах машинописного текста и содержит 31 рисунков и 17 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе проведен анализ основных технических решений систем

огического вывода, дана краткая характеристика логических задач, выделены )акторы, влияющие на их сложность, определены основные направления по-ышения эффективности систем ЛВ, выявлены основные тенденции в развитии редств аппаратной поддержки и обоснованы основные направления исследований.

В работе рассмотрены статические характеристики логических задач, по-азано их влияние на структуру и объем базы данных и базы правил. Выделены >сновные трудности распараллеливания логической обработки, вытекающие из пецифики логических задач. Хотя потенциальный параллелизм большинства адач достаточно велик, основным препятствием непосредственной реализации [араллельных вычислений является нерегулярный характер и малая доля ре-льного параллелизма, а также связность ветвей дерева вывода через общие пе-¡еменные.

В первой главе сделан обзор известных технических решений и проектов [роцессоров логического вывода. Анализ этих технических решений позволил ыявить основные направления организации систем ЛВ такие, как:

- построение системы на основе ТЖС-процессоров;

- применение различных видов конвейерной организаций системы;

- использование ансамбля процессоров с синхронным и асинхронн принципом управления;

- использование сети транспьютеров.

Анализ литературы показал, что в большинстве публикаций оценки пр лагаемых структурных решений носят качественный характер и представля! в основном, генерацию вариантов построения аппаратных средств ЛВ без ких-либо количественных оценок эффективности их применения и сложно« технической реализации. А для реализованных технических решений в бо шинстве случаев отсутствуют данные, отражающие их эффективность при шении различных классов задач.

Одним из важных результатов анализа технических решений было ус новление того факта, что в большинстве аппаратных решений не учитыва) фактор связности ветвей дерева логического вывода по переменным. Это п] водило к большому числу обменов данными между параллельно работающи устройствами. В работе выделены достоинства, недостатки и возможные п спекгавы развития рассмотренных технических решений. Показано, что в рз проектов были заложены, но не достаточно развиты идеи предварительной п< готовки альтернативных решений, генерации пар потенциально унифицир; мых термов и оптимизации трассы логического вывода.

Были проанализированы различные трансляторы с языка логичесш программирования Пролог и абстрактные машины, лежащие в основе логи ских вычислений. Среди моделей абстрактных машин логического вывода н; большее распространение получила последовательная машина Уоррена, ос» ным недостатком которой является то, что она не ориентирована на паралле. ные вычисления и не учитывает специфику решаемых задач. Из этого был с, лан вывод о необходимости модификации машины Уоррена с целью повыи ния эффективности ее параллельной реализации.

На основе анализа литературы выделены и рассмотрены основные спо(

8 ___________________

бы повышения производительности систем логического вывода, которые в целом заключаются в индексировании данных, в более детальном анализе логических программ на этапе трансляции для учета специфики решаемых задач, а также в распараллеливании вычислений.

Анализ тенденций развития систем логического вывода и специфики задач, решаемых такими системами, позволил сформулировать основные направления исследования, такие как:

а) выявление соответствия между параллелизмом логического уровня н реализуемым параллелизмом и отыскание способов увеличения ширины реального параллелизма логических задач;

. б) разработка способов повышения эффективности предварительной обработки, в том числе на этапе трансляции, за счет более детального анализа логических задач;

в) поиск эффективных способов представления схемы данных и организации ее адекватного отображения в памяти ЭВМ;

г) обеспечение фильтрации заведомо ложных направлений логического вывода;

д) поиск и разработка алгоритмов операций ЛВ, ориентированных на аппаратурную реализацию;

е) синтез структурных решений, учитывающих современные достижения в области логической обработки и технологии СБИС.

Вторая глава посвящена анализу характеристик реализации алгоритмов логического вывода, его основных этапов и операций с целью выявления наиболее трудоемких. Разработаны алгоритмы основных макроопераций ЛВ и дана оценка их эффективности.

В качестве основных этапов логического вывода выделены этап трансляции запроса, этап его логической обработки и этап интерпретации результата. Указанная последовательность этапов отражает последовательность прохожде-

ния информационных потоков в системе ЛВ. Выделены функции этих этапов и дана оценка их сложности.

Проведен анализ этапов ЛВ с целью разделения функций между компонентами вычислительной системы (ВС). В диссертации принят подход к построению ВС по типу «базовая ЭВМ - функционально-ориентированный процессор», где специализированные аппаратные средства названы специализированным макропроцессором (СМП).

Разгрузка главной ЭВМ является актуальной проблемой для случаев, когда главная машина работает в сети в многозадачном режиме. Вследствие этого, на универсальную ЭВМ целесообразно возложить выполнение всех функций транслятора, а также интерпретацию результата логического вывода, поскольку эти этапы не требуют больших вычислительных затрат.

По сложности вычислений и трудоемкости этап ЛВ на несколько порядков превосходит другие этапы. Для универсальных ЭВМ и, в особенности ПЭВМ, работающих в качестве сервера, на которых обычно решаются такие задачи, подобная нагрузка достаточно ощутима. Следовательно, функции этого этапа целесообразно возложить на специализированные аппаратные средства.

Установлено, что сложность алгоритма логического вывода, его вид и конфигурация зависят от динамических характеристик логической задачи, которые отражают абсолютные и средние показатели вычислительного процесса, такие как ширина и глубина пространства поиска, максимальное число операций унификации, ширина логического параллелизма и др. В диссертационной работе выделены динамические характеристики логических задач и дано их формальное описание на основе статических характеристик.

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

сражены посредством системы команд Уоррена на основе динамических ха-истеристик логических задач. С учетом этого, трудоемкость логической обра-этки представляется следующим выражением.

i\€03 U

1=1 г=1

+ i/h

i Увоз_л *униф' <3+18J+1воз_и ^воз

Л-Минд+18

ы

;е f— число фактов i-ro предиката; N - максимальное число аргументов пре-якатов; И - число вхождений i-ro предиката в тела других предикатов с учетом тоженных вызовов; а - число аргументов литерала с учетом вложенных струк-ф; Wp, Двоз_и »W .^униФ * труД°емкость операций загрузки, возврата к бли-:айшей ИЛИ-верпшне дерева ЛВ, возврата и ближайшей И-вершине, индекси-ования и унификации соответственно.

На основе анализа алгоритмов ЛВ выявлено, что к наиболее часто встре-ающимся операциям относятся операция унификации пары аргументов, опе-ация построения вершины дерева ЛВ и операция выбора текущей подцели, [оказано, что наиболее трудоемкими этапами ЛВ являются этапы унификации возврата при определении ложности обрабатываемой ветви, и существует не-бходимость снижения трудоемкости этих операций и уменьшения числа обра-атываемых ложных ветвей вывода.

Во второй главе модифицированы алгоритмы выполнения ряда операций [ сформированы на их основе макрооперации, ориентированные на аппаратурою реализацию. При оптимизации алгоритма унификации уменьшение длины [епи связанных переменных позволяет уменьшить трудоемкость операции де-юференсирования переменных за счет уменьшения числа операций чтения 1анных из памяти. Это обеспечивает существенное ускорение аппаратурной юализации данного алгоритма, но при программной его реализации трудоем-:ость макрооперации унификации возрастает в 1.1-1.4 раза, вследствие ориен-

тации алгоритма на параллельное выполнение.

.При синтезе операций выявилась необходимость фильтрации данных, чтобы избежать большого числа операций возврата, а также для сокращения суммарного числа операций унификации. В качестве метода фильтрации альтернативных утверждений был взят поиск данных по частичному сопоставлению. Формирование кодовых слов реализуется на основе метода кодирования наложением (МКН). В работе дана оценка трудоемкости и возможности аппаратурной реализации МКН, а также алгоритма поиска на его основе. Трудоемкость операции кодирования одного литерала, так же как и для унификации, зависит от типа его аргументов.

В качестве основных макроопераций были выделены: операция построения среды обрабатываемой вершины, операция возврата к ближайшей ИЛИ-вершине, операция унификации пары литералов и операция поиска альтернативных утверждений, причем отличительной особенностью двух последних операций от традиционных аналогов является динамическое разворачивание последовательности операндов внутри макрооперации. При формировании макроопераций учитывался принцип однотипности схемы алгоритмов операций ЛВ в соответствии с критерием максимальной вложенной сложности их реализации аппаратными средствами при минимальной необходимой управляющей информации. Для макроопераций даны оценки сложности их алгоритмов.

На основе анализа разработанных алгоритмов макроопераций показано, что при использовании традиционных средств параллельной обработки информации не удастся повысить эффективность систем ЛВ более чем на порядок. Для сложных логических задач эта величина будет еще меньше. В результате сделан вывод о целесообразности разработки новых подходы к организации вычислений, связанных с обходом дерева ЛВ, которые заключаются в выделении параллельных ветвей дерева ЛВ, не требующих обмена данными при их реализации.

Третья глава посвящена разработке абстрактной машины параллельного ЛВ и построению модели задач ЛВ, отражающей возможный параллелизм алгоритмов при их реализации на параллельных ВС. В процессе синтеза модифицированной машины вывода была разработана структура памяти машины, алгоритмы операций формирования трассы ЛВ и система макрокоманд.

Основной задачей при организации параллельных вычислений является задача преобразование параллелизма логического уровня в реализуемый параллелизм. Чтобы наметить пути решения этой задачи была построена модель задачи для классической машины Уоррена. Выделена длина скалярных участков (S) всего алгоритма ЛВ, длина независимых ветвей (D) и векторного параллелизма (V), выраженная в элементарных операциях. Модель представлена следующими выражениями.

5 lQkl+Ak1+ki

S + D + V 300£, +4 к2 +5 к}

D 300кх-к}

S + D + V 300^ +4 кг +5къ

V 5 кг

S + D + V 300А, +4к2 + 5кг

Из выражений видно, что значительная доля всех вычислений приходится на скалярные участки, участки локального параллелизма занимают в общем случае лишь 35-50% от всего объема вычислений. Параметры к)-к5 отражают коэффициенты, диапазон изменения которых следующий к|(1..5), к2(0..2000), к3(70..1500),к5(60..700).

Анализ модели задачи показал, что объем вычислений, который может быть реализован параллельно, явно недостаточен для получения требуемой производительности, из чего вытекает необходимость поиска и разработки способов повышения степени реального параллелизма алгоритмов решения логи-

ческих задач. С этой целью в работе предлагается следующее решение - разделять ветви дерева ЛВ на основные, частично связанные и независимые согласно степени их связности посредством общих переменных. Разработан алгоритм анализа литералов тела правил по степени связности и рассмотрены принципы формирования подпрограмм параллельной обработки независимых ветвей на этапе трансляции. Сформулированы функции транслятора и требования к его реализации. В качестве дополнительных функций выделены функции анализа типов литералов, индексирования утверждений по всем аргументам их головных литералов и формирования параллельных подпрограмм обработки.

Ширина возможного реализуемого параллелизма (Рг) зависит от числа несвязанных или частично связанных литералов и представлена следующим выражением, для которого величины Ь„ц Ьчсу означают число независимых и, соответственно, частично связанных по переменным литералов ^го правила ь-го предиката, с0 - число литералов тела цели программы, э - число предикатов логической программы; т; - число правил ¡-го предиката.

Использование предложенного решения позволяет повысить уровень внутреннего параллелизма в 2-3 раза.

На основе сформулированных требований к параллельным вычислениям на основе модификации машины Уоррена разработана абстрактная машина параллельного ЛВ. В рамках организации машины вывода рассмотрены способы представления данных, организация памяти машины и система команд.

В качестве основного способа представления данных взят способ разделения структур с упорядочением элементов по родству. Рассмотрена организация памяти данных, представленная в виде совокупности базы формальных параметров обработки (которые соответствуют заголовкам прайил) и базы фактических параметров (которые соответствуют литералам тел правил). В результа-

(3)

е предложена организация данных и метаданных системы ЛВ в виде совокуп-гости БД и индексных таблиц. Разработаны также форматы данных и структу-1Ы введенных индексных таблиц.

В третьей главе предложена система макрокоманд и даны ее качествен-ше и количественные оценки и сравнения с традиционной системой команд fоррена. За счет введения макрокоманд число команд с 22х сократилось до 7 ткрокоманд без учета модификаций. Это позволяет повысить уровень машин-юго языка и упростить работу транслятора. Кроме того, небольшое число мак-¡окоманд позволяют снизить нагрузку на управляющую шину, что является 1ажным для организации параллельных вычислений.

Даны оценки трудоемкости выполнения предложенных макрокоманд, доказано, что за счет концентрирования всех необходимых операций для обра-ютки одной вершины дерева ЛВ в трех макрооперациях, а не в 11 операциях ;ак в традиционной машине Уоррена, выигрыш в трудоемкости обработки од-¡ой вершины составляет 1.6-3.1 раза. За счет алгоритмической модификации шераций логической обработки удалось понизить основную трудоемкость на !0-50%, в зависимости от сложности запросов и решаемой логической задачи.

На основе анализа логических задач, алгоритмов ЛВ и предложенного ;пособа увеличения ширины реализуемого параллелизма составлена модель за-шчи ЛВ для решения на параллельных ВС. Эта модель представлена в двух ва-шантах, выраженная в элементарных машинных операциях и в условных тактах для случая параллельного выполнения разработанных операций.

Следующие формулы показывают соотношения длин различных участков шгоритма ЛВ для варианта модели, выраженного в элементарных операциях 4), и для варианта, выраженного в условных тактах (5), где коэффициент kt ¡мест диапазон возможных значений (80.. 12000) , а коэффициент фильтрации Сф изменяется в пределах от 0 до 1 и отражает степень эффективности исполь-ювакия операции поиска..

4 к,

5 + О + V 60 к, + Акъ + 6к2 +

В 56 к,

+ О + V 60 А, + 4 къ + 6 к2 + £4

V 4къ + 6к2 + k^

5 + £> + V 60 к, + 4 к3 + 6 к2 + к4

8 *

*+п* +г # 8*, + к,{.4кф + 1)

о * 7*,

5 * + I) * +У * 8 к, + к}(4кф + 1)

V * + 1)

(5)

Я*+П*+Г* 8*, + + 1)

За счет предложенных алгоритмических решений удалось на 2-3 порядка сократить трудоемкость скалярных участков и повысить долю локального параллелизма с 40% почти до 99%. Для последнего варианта модель задачи показывает уменьшение основной трудоемкости за счет использования операции поиска и параллельного выполнения ряда операций. В этом случае длина скалярных участков уменьшилась примерно в четыре раза, независимых ветвей -в восемь раз, а для векторных участков это уменьшение составляет в среднем на порядок. В отличие от первого варианта модели, для двух последних вариантов соотношение между величинами Б, Б и V изменилось и имеет вид 8<ЕХ<У, что говорит о возможности и целесообразности реализации модифицированных алгоритмов ЛВ параллельными ВСр.

Четвертая глава посвящена разработке и оптимизации структуры параллельных ВС для реализации ЛВ и разработке функциональных схем основных модулей. Сделана оценка интенсивности информационных потоков в ВС и получены оценки характеристик основных модулей и системы ЛВ в целом.

. С учетом современных тенденций проектирования вычислительных устройств на СБИС в работе выбрано направление создания архитектуры параллельного типа с переменным составом модулей, и поэтому в качестве основно-

) принципа формирования структуры взят принцип выделения функционально )тономных блоков (ФАБ), реализующих достаточно автономные этапы алго-пма ЛВ.

Для определения количества ФАБ и требований к их параметрам произ-;дена оцетгка основных этапов алгоритма по составу операций, трудоемкости интенсивности обмена данными с другими этапами алгоритма. На основе 1ализа этапов выполняемых в СМП ЛВ алгоритмов и полученных оценок ха-истеристик алгоритмов в качестве ФАБ выделены процессор поиска данных э частичному совпадению (ППДЧС) и процессор обработки (ПО).

Исходя из анализа алгоритмов работы ФАБ и их быстродействия, в чет-:ртой главе получены соотношения для частоты обмена между устройствами и эъемов передаваемой информации. Рассмотрена организация структуры каж-эго из ФАБ и всей вычислительной системы в целом.

В результате анализа характеристик обмена данными между ФАБ и памя->ю были даны количественные оценки характеристик структуры СМП ■абл.1), достаточные для решения логических задач, обладающих шириной ре-тьного параллелизма независимых ветвей 4..6 и шириной пространства поиска 10000..20000 утверждений.

Для согласования пропускной способности памяти и быстродействия роцессоров используется модульное многоблочное построение памяти данных ТД), памяти метаданных (ПМД) и рабочей памяти (РП). Обеспечение доступа Q и ППДЧС к ПМД, ПД и рабочей памяти осуществляется через коммутаци-нные структуры.

Особенностью структуры СМП является то, что реализация макроопера-ии поиска утверждений распределена между ППДЧС и интеллектуальными одулями ПМД. ППДЧС формирует эталон поиска, а собственно сам поиск существляется в ПМД. Перенесение операции сопоставления данных с этало-ом в память в среднем в 2-3 раза снижает нагрузку на магистрали, соединяюще эту память с процессорами обработки.

Таблица 1

Характеристики структуры специализированного макропроцессора

Компонент • структуры Число процессоров /модулей памяти Объем модуля памяти (байты) ' Общий объем памяти (байты)

... .по £ («4-6) - -

ППДЧС ± (»8-12) - -

Модуль ПМД к («6-8) 256К кх256К(»1,5-2М)

Модуль ПД к по 4 блока 1М 4кх256К(«6-8М)

Модуль РП т («4-6) 0, 5М тхО,5М(*2-4М)

ПО и ППДЧС построены на основе перестраиваемых автоматов, что позволяет повысить регулярность структуры этих процессоров и существенно снизить аппаратурные затраты, необходимые для их реализации. Настроечная информация для ППДЧС содержится в поле признака макрокоманды и настройка его на соответствующий алгоритм осуществляется при поступлении макрокоманды. Настройка ПО осуществляется динамически непосредственно во время выполнения операций за счет анализа вида операндов выполняемой макрокоманды.

В структуре выделен функциональный срез (ФС), состоящий из одного ПО и двух ППДЧС и являющийся основным элементом наращиваемости структуры. Под функциональным срезом в данном случае понимается минимальный набор ФАБ, достаточный для последовательного решения логической задачи любой сложности и отражающий ход выполнения алгоритма ЛВ. Выбор такого состава ФАБ в ФС произведен на основе анализа производительности ПО и ППДЧС и характеристик обмена между этими процессорами.

На основании анализа необходимой управляющей информации сформу-

юваны требования по управляющим функциям к центральному устройству )авления. Функции УУ, в основном, заключаются в распределении вычисли-ьных ресурсов макропроцессора, организации параллельного выполнения фокоманд и формировании результата ЛВ для главной ЭВМ.

Структурная организация СМП обеспечивает возможность наращивания ;ла функциональных процессоров в зависимости от требуемых характери-[к работы системы. В целом расширение системы осуществляется посредст-,1 добавления функциональных срезов. Однако возможно добавление и от-1ьных ПО и ппдчс. В работе сформулированы принципы наращивания вы-:лительной мощности в соответствии с характеристиками решаемого класса [ач.

С целью оценки возможности выполнения на СБИС СМП логического вода проводился расчет основных аппаратных затрат, необходимых для реа-зации ФАБ и представленных в элементарных вентилях. Так аппаратные за-1ты, необходимые для реализации ФС, составляют порядка 30200 вентилей, з делает возможным его реализацию на современной элементной базе, в ча-гости на программируемых логических интегральных схемах (ПЛИС).

В пятой главе построена и исследована имитационная модель аппаратно-

ограммных вычислительных средств для решения задач ЛВ.

\

Задачей моделирования являлась проверка корректности разработанных и дифицированных в третьей главе алгоритмов ЛВ, получение статистических енок параметров основных модулей и блоков системы и характеристик ин-рмационных потоков в моделируемой системе при решении различных логи-ских задач.

Система моделирования включает следующие подсистемы:

1) подсистему генерации логических программ в синтаксисе БЕС-Ю юлога;

2) подсистему, моделирующую работу транслятора логических программ;

3) подсистему, имитирующую структуру и функциональный состав апг ратных средств системы ЛВ, разработанных в четвертой главе диссертационн работы;

4) подсистему, организующую функционирование модели при выполе нш логической программы и обеспечивающую статистическую обработку р зультатов моделирования.

Система моделирования написана на языке программирования С++ и ра считана на использование операционной системы MS DOS версии 6.22 и пр менение транслятора Borland С++.

Модель аппаратных средств имитирует алгоритмы работы ФС систем логического вывода. Результаты исследований экстраполировались на всю си тему ЛВ. Экстраполяция возможна благодаря тому, что система в целом пре, ставляет собой объединенные коммутационными структурами ФС, работаювд под общим управлением.

Каждому ФАБ СМП в имитационной модели соответствует отдельнь модуль. Преобразование информации в модулях осуществляется строго по а горитмам операций, выполняемых процессорами. Кроме того, в модели по, держивается разбиение ФАБ на внутренние блоки. На вход программных мод лей подается необходимая управляющая информация в форматах, соответс вующих форматам разработанных в третьей главе макрокоманд. Структур хранения основных данных и метаданных в памяти полностью соответствуй предложенной в диссертации организации данных. Благодаря такой структу! имитационной модели явилось возможным потактовое моделирование работ СМП ЛВ.

На этапе генерации логических программ были получены задачи с ра личными динамическими характеристиками путем варьирования статически параметров. Эти задачи транслировались в исполнительный код и обрабатыв; лись согласно алгоритмам, заложенным в основной подсистеме. В подсистем трансляции логических программ включены как традиционные алгоритм:

трансляции, так и все алгоритмы, предложенные в третьей главе.

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

1. На основе создания БД, формирования индексных таблиц и исполнительного кода по предложенной системе макрокоманд была получена статистика, подтверждающая уменьшение объема исполнительного кода в среднем в 3,6 раза.

2. Показано, что для большинства задач отношение реального параллелизма независимых ветвей к потенциальному параллелизму задачи лежит в пределах 6-10%, и только в редких случаях достигает 50%.

3. Число одновременно обрабатываемых ветвей в среднем не превышает 4-5. Эта величина непосредственно влияет на выбор числа процессоров обработки в системе.

4. Анализа статистических данных работы процессора поиска показал, что коэффициент фильтрации к (10) для 56% запросов на поиск данных достигает 0.35-0.5. Для 10-12% запросов этот коэффициент имеет значение 0.1-0.2, и только в 1.3-2% к равен 1, что означает отсутствие фильтрации заведомо ложных альтернативных ветвей обработки.

5. Установлено увеличение производительности ЛВ при решении задач на СМП на один-два порядка по сравнению с известными аппаратными решениями (Aquarius, Tick-Warren, CHL), а также с программной реализаций системы команд Уоррена на процессоре Pentium. Сравнение проводилось по обычным и модифицированным алгоритмам с учетом традиционной для логических задач и предложенной в третьей главе организации данных в памяти.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Разработана структура СМП ЛВ и определен состав его ФАБ. Особенностью предложенной структуры является ее ориентированность на аппаратную реализацию макроопераций ЛВ и параллельную обработку ветвей дерева вывода. Структура СМП также удовлетворяет принципам модульности, наращиваемости и перестраиваемости, что позволяет формировать систему ЛВ в зависимости от характера решаемых задач.

2. Разработана функциональная организация основных блоков СМП -ППДЧС и ПО, и определены их характеристики. Предложена структура памяти данных, обеспечивающая требуемую пропускную способность при работе с этими функциональными блоками.

3. Впервые предложен способ увеличения реального параллелизма задач на основе анализа литералов тел правил по степени их связности общими переменными. Это позволило в 1.5-2 раза повысить ширину реализуемого параллелизма и практически исключить обмен данными между параллельно работающими процессорами.

4. Построена модель задачи ЛВ, позволившая оценить соотношения между скалярными и параллельными участками вычислений. Сравнение модели задачи, решаемой с помощью традиционных алгоритмов и модели, основанной на использовании предложенных алгоритмических и аппаратных решений, показало эффективность этих решений за счет увеличения доли параллельных вычислений, и уменьшения общего объема эквивалентных вычислений.

5. Разработана система макрокоманд СМП, учитывающая специфику параллельной аппаратной обработки, которая позволяет повысить уровень машинного языка, упростить этап трансляции и уменьшить объем управляющей информации, необходимой для работы функциональных процессоров.

6. Предложена организация памяти метаданных и рабочей памяти СМП, отличительной особенностью которых является перенесение части простых

пераций над данными непосредственно в память, что позволяет сократил бьем информационных потоков в системе. Установлена зависимость между бъемом памяти, количеством ее модулей и характеристиками решаемого клас-а задач.

7. Разработаны и модифицированы алгоритмы основных макроопераций [В, при программной реализации которых трудоемкость вычислений уменьшатся на 20-50%. Аппаратурная реализация этих алгоритмов на предложенной труктуре позволяет повысить производительность ЛВ на 1-2 порядка в зави-имости от сложности решаемых задач.

8. Модифицирован алгоритм, реализующий метод кодирования утверждений наложением,, в результате чего становится возможной аппаратная реа-изация фильтрации альтернативных утверждений предикатов и достигается меньшение в среднем на 30-50% потока данных, поступающих на устройства нификации.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Применение хеширования для увеличения производительности аппа-атной обработки нечисловой информации/ Васяева Е.С., Васяева Н.С.- Мате-иалы республиканской научно-методической конференции, посвященной 100-етию радио "Прикладные исследования в электронике и новые технологии в бучении студентов".- Йошкар-Ола, МарГТУ, 1995,- с.69-70.

2: Применение хеширования при аппаратурной реализации операций над азами данных/Васяева Е.С., Васяева Н.С., Власов A.A.; Марийск. политехи, [нститут,- Йошкар-Ола, 1995.- 9 с. Библиогр.: 4 назв.- Рус,- Деп. в ВИНИТИ 2.07.95, N2145-B95.

3. Васяева Е.С., Васяева Н.С. Разработка структур процессоров вторич-юй обработки на основе метода уникального хеширования// LI научная сессия, [освященная дню радио, 22-23 мая 1996 г., Москва, с.бб.

4. Васяева Е.С., Васяева Н.С. Реализация метода уникального хеширования в машинах баз данных// LI научная сессия, посвященная дню радио, 2223 мая 1996 г., Москва, с.68.

5. Logic-based information system for processing of archaeological materials/ E.S.Vasiayeva, N.S.Vasiayeva, V.V.Nickolayev// Proc. of 3-rd Int. Workshop an advances in DB and Infor. Syst. (ADBIS'96), Moscow, Sept. 10-13, 1996- Vol.2.-p.34-36.

6. Власов A.A., Васяева E.C., Васяева H.C. Структура средств аппаратной поддержки интегрированного представления знаний и данных в интеллектуальных системах// IX Всероссийская научно-техническая конференция "Однородные вычислительные структуры, среды и распределенные системы", 2021 ноября 1996 г., Москва, с.24.

7. Васяева Н.С., Власов А.А. Влияние на архитектуру вычислительны? средств систем искусственного интеллекта методов представления знаний i алгоритмов логического вывода// Материалы Всероссийской научной конфе ренции "Цифровая обработка многомерных сигналов", 9-12 декабря 1996 г. Йошкар-Ола, с.92-93.

8. Attributive-logical analysis and based on this analisis cartographica information system for processing of archaeological materials/ J.V.TJsko\ E.S.Vasiayeva, N.S.Vasiayeva, V.V.Nickolayev// Proc. of the first East-Europea: Symposium on Advances in Databases and Infor. Syst. (ADBIS'97), St. Petersburg Sept. 2-5, 1997.- Vol.2.- p.97-99.

9. Different approaches to effective execution of Prolog program: A.A.Vlasov, N.S.Vasiayeva// Proc. of the first East-European Symposium о Advances in Databases and Infor. Syst. (ADBIS'97), St. Petersburg, Sept. 2-: 1997.- Vol.2.-p.35-38.

10. Оценка эффективности различных способов ускорения логическо1 вывода/ Васяева Н.С., Власов А.А., Веприков В.М.; Марийск. государ, тех] унив,- Йошкар-Ола, 1997,- 14 с. Библиогр.: 14 назв. - Рус. - Деп. в ВИНИТ

.09.97 N2870-B97.

11. Васяева Н.С;, Власов A.A. Роль аппаратных средств в рамках техноло-и интеллектуальной обработки данных// Радиоэлектроника и электротехника «родном хозяйстве. Ежегод. НТК студ. и асп. вузов России. Тез. док. В 2х wax: Т.2.-М.: Изд-во МЭИ, 1998.- с.34-35.

12. Васяева Н.С., Дудник В.Ф., Волков И.Н. Моделирование архитектуры :пределенных средств поддержки дедуктивного логического вывода// Радао-лароншса и электротехника в народном хозяйстве. Ежегод. НТК студ. и асп. зов России. Тез. док. В 2х томах: Т.1.-М.: Изд-во МЭИ, 1998.- с.177-178.

13. Модификация абстрактной машины Уоррена для параллельной аппа-гурной реализации/ Васяева Н.С.; Марийск. государ. техн. унив- Йошкар-га, 1998.- 6 с. Библиогр.: 2 назв. - Рус. - Деп. в ВИНИТИ

14. Организация вычислений в специализированном макропроцессоре ло-ческого вывода/ Васяева Н.С., Власов A.A.; Марийск. государ. техн. унив,->шкар-Ола, 1998.- 6 с. Библиогр.: 3 назв. - Рус. - Деп. в ВИНИТИ

15. Структуры представления данных и знаний и их отображение на ар-тектуру вычислительных средств/ Васяева Е.С., Васяева Н.С., Власов A.A.; арийск. государ. техн. унив.- Йошкар-Ола, 1998,- 8 с. Библиогр.: 12 назв. -с. - Деп. в ВИНИТИ

Личный вклад автора в опубликованные работы заключается в следую-:м. В работах [6,7,10,11,14] на основании поставленных научным руководи-тем совместно с диссертантом задач были выполнены все аналитические вы-ды. Автору принадлежит идея применения аппарата хеширования для вы-лнения реляционной операции удаления дублирующих значений [1], идея паратурной реализации на основе этого алгоритма теоретико-множественных ераций [2,4]. Автор принимал непосредственное участие в проведении экспе-ментов [1,3,4,12]. Разработаны принципы представления дедуктивной базы иных по паспортизации. историко-археологических памятников на основе едикатов первого порядка [5,8]. Автору принадлежит идея модификации

операции унификации и снижения трудоемкости операции дереференсир< ния, а также разработка аппаратно-ориентированного алгоритма этой опера [9]. В работе [15] автором проведен анализ структур представления знаний.

Опубликованные работы [7,9,10-14] достаточно полно отражают сод жание диссертации.