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

РГ6 од

СМШ1-ПЕТЕРБУРГСКИЙ 'I 3 ¡ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХБИЧЕСЖМЙ УНИВЕРСИТЕТ

На правах рукописи

Тодорова Эмилия Стойчева

АРХИТЕКТУРА ПРОЦЕССОРА, ОРИЕНТИРОВАННОГО НА ЭФФЕКТИВНОЕ ВЫПОЛНЕНИЕ КОМПИЛИРОВАННЫХ ПРОЛОГ-ПРОГРАММ

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

комплексы, системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 19ЭЗ

Работа выполнена в Санкт-Петербургском государственном электротехническом университете

Научный руководитель -доктор технических наук, профессор ФОМИЧЕВ B.C.

Официальные оппоненты: доктор теглических наук, профессор ЯКОВЛЕВ В.Е. кандидат технических наук БНГОВО В.В.

Ведущая организация - Производственно-техническое управление радионавигации и связи акционерного общества "Севврозападяое пароходство"

Защита диссертации состоится

г п хээз г.

в часов на заседании спэциализиройиного совета К 063.86.12 Санкт-Петербургского государственного электротехнического университета по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомится в библиотеке университета. Автореферат разослан " 1993 г.

Ученый секретарь специализированного совета

Балаюга В.Н.

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

Актуальность проблема. Развитие науки последнего дэсятилетия требовало расширение исследований в области исскуственнсго [тэдлекта, практической реализация которых ориентирована на шэние широкого спектра задач - от чисто научных до оизводственных. Одним из направлений этих исследования является гическое программирование и языки программирования логичэского вода. Среди языков логического программирования ведущее место шмает Пролог. Использование Пролога поззоляет создавать шактные прогргпш и сокращать сроки их разработки. Однако аонаым препятствием при использовании Пролога является большоэ )эмя выполнения программы на универсальной ЭВМ, что является юдотвием семантического разрыва. Характерными особенностями юлог-вычислений являются:

- недетерминированность;

- использование тштрадициоешх сложных структур данных;

-наличие специфических операций, не имеющих аналогов среда

>угих языках: унификация, отсечение, возврат, двунаправленная |редача параметров."

Реализация этих особенностей требует архитектуру [сскослепиализироБанного типа, В решения этой задачи возможны два даода: реализация интерпретации и компиляции Пролог-программ. 1ализ работ в этой области показывает, что использование (мпиляции обеспечивает повшпоние скорости выполнения программ в юкслько раз по сравнению с интерпретацией за счет использования [сокоспециалпзированнсго алгоритма унификации применительно к ¡¡вдому заголовку клегв.

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

8 разработки систем, вшюлняэдих шлтлированиыв юлог-ирограммн применяются различные решения, спосоОсгаущив (вшвншо скорости вкпютчжя программ. Эти cnotioiu можно оделить на насколько групп й зависимости or уровня, на котором «меняются:

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

. -уровень архитектуры: решения, касающиеся абстрактной машинь способы представления и манипуляции над данными; спосос распределения и управления памятью; способы выполнения команд;

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

Рассмотренные способы повышения эффективности выполнен! Пролог-программ позволяют сделать вывод о факторах, от которь зависит эффективность выполнения программы:

-модель вычислений и возможность усовершенствования на уров! модели;

-адекватность отображения вычислительной модели на внСраянс архитектуре;

-выбор аппаратных средств для реализации архитектуры. Целью данной работы является разработка "Специализирован®: архитектуры Пролог-процессора, выполнявдего компилирована Пролог-программы. Достижение этой цели предполагает решеш следующих задач:

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

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

-разработка системы моделирования и ее применение с цел: оценки результатов решения предыдущих задач;

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

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

Научная новизна состоит в следующем:

- предложен способ процедурной интерпретации Пролог-програм» который в отличии от принятого предусматривает дифференцирована

гадхад р рекурсивным и нерекурсивным процедурам;

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

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

Практическая ценность заключается в следующем: -предложен конвейерный Пролог-процессор на основе однородной двухпроцессорной структуры с общей памятью и разделением 1агистралеЙ команд и данных;

-разработана и исследована программная модель процессора. Внедрение результатов работы осуществляется в рамках юкционного курса "Организация вычислительных процессов" кафедры ¡ычислительной Техники С.Пб.ГЭТУ.

Аппробация работы. Основные положения и результаты [иссергационной работы докладывались на иаутю-твтичвскпл :онференциях профессорско-преподавательского состава ЛЗТИ им. I.И.Ульянова /Ленина/ в 1991-1993 г.

Публикации. По материалам диссертационной работы опубликованы 1 статьи.

Структура и обьец-работы. Работа состоит из введения, четырех ■лав,' заключения, списка литературы, включающего 56 наименований, [ 6 приложений. Основная часть работы изложена на 98 страницах йшинописного текста. Работа содержит 27 рисунков и 8 таблиц.

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

Во введении обосновывается актуальность работы, формулируются ;ели и задачи исследования.

В первой главе на основе анализа способов, применяемых для гавышенин скорости выполнения Пролог -программ в современных еализация!, выявлены факторы, влшщив на »Кектитаость ялолнения программ. Это:

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

адекватность отображения вычислительной модели на выбранной архитектуре;

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

Существующие модели Пролог-вычислений могут быть разделены на

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

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

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

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

2. Уровень архитектуры. К этому уровню можно отнести решения, относящиеся к абстрактной малине: способы представления и манипуляции над данными; способы распределения и управления

памятью; способы выполнения команд.

3. Уровень структуры.

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

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

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

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

Ео второй главе решается задача построения модели вычислений Пролог-программ при использовании нового подхода к процедурной лнтерпретации к сценка эффективноега применения этого подхода, модель вычислений является исходной ступень» к построении архптеэтури прзаезеерз, Егасдняидего Пролог-прогрзты. Описано

- (. -

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

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

Рассмотрен метод, позволяющий исключить йзбытоФШ Действия управлении за счет детального анализа исходной программы на 'этап компиляции. Этот метод позволяет исключить сохранение адресо возврата не содержащих рекурсию и частично отказаться о сохранения для рекурсивных программ. Метод в начале рассмотре применительно к программам, не содержащим рекурсйй. Для этог построено, графическое изображение Пролог-прогрйМШ. Каждом клозу вида

А0 • ■*А |, Аг, ■ •., Ап« поставим в соответствие ш-1 вершин таким обраЗбЫ# Ч*обы вершина соответствующая заголовку А0 была расположена йауробне с нечетны номером к, а вершины, соответствующие символам Тела клоза был расположены на уровне с четным номерам 1с+1. Вершину соответствующую А0:- соединим с вершиной, сскдае^ствуюцей первого символу тела клоза, а все вершины, соо'йёТствущае остальны символам тела клоза соединим дугами, напрйМёнными от вершины меньшим номером к вершине с большим номером.

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

Грлф програшы является исходным для построения представлена

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

Чтобы перейти к блочному представлению введены четыре типа блоков. Первый тип поставлен в соответствии заголовкам клозов , второй тип - символам тел клозов, третий тип сопоставлен удачному завершению программы, четвертый - неудачному.

Блок заголовка HEAD соответствует выделению фрейма и унификации аргументов заголовка с аргументами цели (тела клоза). Обозначение входов и еыходов этого блока:

1.Вход по вызову (FIRSTJ3ALL).По этому входу происходит активация блока для унификации первой альтернативы из последовательности альтернативных клозов.

2.Вход по альтернативе (ALT). По этому входу активируется блок заголовка для каэдой альтернативы из последовательности альтернативных клозов кроме первой.

3.Выход TRUE соответствует удачному результату унификации аргументов цели и заголовка.

4.Выход FALSE соответствует неудачному результату унификации аргументов цели и заголовка.

Блок второго типа соответствует символу тела клоза (цели тела) и осуществляет подготовку аргументов цели тела к унификации. Назовем его. блоком цели: GOAL. Имеет один вход и один выход.

Обозначение входов и выходов этого блока :

Г.Вход в блок (NEXT). Осуществляется только после удачной унификации некоторого заголовка с предыдущей целью.

2.Выход CALL соответствует завершении подготовительных по отношению цели тела клоза.

Блоки третьего и четвертого типов соответствуют завершению программы. Эти блоки не имеют выходов, имеют по одному входу. Блок AHSWER должен приостановить выполнение программы и видать решение. Блок FAILURE ответствен за сообщение о неудачном завершении программы и приостановление вычислений.

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

Рассмотренный способ построения блочного представления программы, позволяет определить все возмоише п>зре?одц между блоками, поэтому мзкно утперадать, что ллхЗую Пролог-программу не

- a -

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

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

Чтобы учесть особенности выполнения рекурсивных программ, введены два дополнительных типа блоков. Блок рекурсивного вызов; REC_GOAb должен обеспечивать сохранение указателя на незавершенныЕ вычисления, путем записи его в стек, а блок сворачивания рекурсш HEAD_RET должен обеспечивать активизацию всех незавершенны: вычислений.

Для того чтобы выяснить эффективность рассмотренных метода! реализации Пролог-программ были рассмотрены несколько примеров, Эти примеры были записаны в начале с помощью команд Уоррена J системе команд процессора Intel 8086. Для примеров было подсчитанс время выполнения Т1. Затем в командах. были определены те действия, которые можно исключить, используя описанный способ.

Было подсчитано время выполнения таких программ Т2 после исключения этих действий. Отношение (Т1-Т2)/Т1 определяв1] ускорение выполнения программы. Кроме того, в рассмотрении: программах было определено время, затрачиваемое на управление 1 первом и втором случае. Отношение этих времен является показателе! сокращения затрат на управление при выполнении программы. Показан ускорение управления выполнением программы до 30SS, а общег< времени выполнения: до 2СМ

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

Блочная модель Пролог-программы дает представление о структуре

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

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

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

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

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

Особенности определенных структур данных:

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

2. Модифицированные фреймы, отличающиеся от фреймов - точек юзврата редуцированным числом управляющих ячеек, что |буславливает сокращение времени построения фреймов и занимаемой

ими памяти.

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

- Особенности полученной системы команд:

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

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

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

4. В случаях первого появления переменной в клозе и первой появления переменной в теле клоза предусматривается построение ее ячейки в аргументном "регистре, что предполагает более короткое время, чем загрузка ячейки из памяти (стека, кучи).

Из перечисленных особенностях 1-3 являются следствие» построения системы команд на основе блочной модели.

Полученная базовая архитектура, Пролог-процессора, характеризуется следующими особенностями:

1. Теговое представление данных, что является наиболее предпочтительным для термов Пролога с точки зрения скорост! выполнения программ и объема используемой памяти.

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

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

О '-¡¡птертой главе решается задача оценки эффективностс

- ll -

выполнения Пролог-программ йа полученной по блочной модели архитектуре и принятия решений для усовершенствования. Для базового варианта архитектуры предложена структура специализированного Пролог-гтроВД Ссора. Каждой команде абстрактной машины соответствует некоторая последовательность микрокоманд. Микрокоманда хранятся в памяти Микрокоманд блока управления, и доступ к ним осуществляется idJífcKo в режиме чтения. Предполагается, что- выполняется конвейеризация на уровне микрокоманд, в результате которой арифметико-логиче ские операции сложения и вычитания, регистровые передачи, инкрёМент, декремент,' сравнение, выполняются за один цикл процессора.

Базовый вариант предусматривает одну шину для кода й Дйнных.

Для получения характеристик выполнения программы архитектурой, реализованной по предложенной структуре, разраб05йна система моделирования, написанная на языке Паскаль объеМсзМ В»6 тыс. строк. Работа каждой команды абстрактной машины моделирУё¥6Я процедурой. Временное моделирование работы устройств выполйёйэ И8 уровне операций, выполняемых за один цикл процессора ЛфсШ временных характеристик выполнения предусмотрено МоДвЛНроЁзШд количества обращений к памяти; обращение к памяти В завйсШости от времени; обращение к областям памяти локального dtSitá, кучи, трейла; обращение к области памяти кода. С целЬЯ исследования времеемкости каждой команда система моделирования вырабатывает гистограмму команд, на которой показан удельный вес времени выполнения по спектру команд, выполняющих задачу. Анализ гистограммы команд способствует принятию решений об усовершенствовании на уровне модели и архитектуры.

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

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

С целью получения корректных оценок времени выполнен* программ в терминах логический вывод за секунду (LIPS) учитываете время нахождения всех решений задачи.

По результатам анализа программной модели Пролог-процессо| предложена последовательность усовершенствований на уровне мoдe^ вычислений, архитектуры и структуры. После каждого шаг усовершенствования проводилось моделирование и по результата анализа выполнения задач определялся следующий ие усовершенствования.

Анализ гистограммы команд подтверждает известные в литератур выводы о трудоемкости операций построения фрейма-точки возврата Для всех исследуемых задач выявляется общая харакерна особенность: команда cholce_p, выполняющая построение точн возврата, занимает 205& - 25% от общего времени выполнения задачи С целью оптимизации времени построения точки возврата предложен применение индексирования (селекции) клозов для усечени возможностей выбора альтернативных клозов. Первый ша усовершенствования предусматривает введение в систему коман команды:

select Cc.Cl.CI.Cs , выполняющую проверку та первого аргумента цели, находящегося аргументном регистре А1 и имеющую в качестве аргументов адрес кода программы, которым передается управление в зависимости о типа. Моделирование показывает ускорение выполнения программы д 1:,22 раза.

Анализ гистограмм команд после введения селекции клозо; показывают, что построение фреймов-точек возврата еще остается самой трудоемкой командой. Предложены команда re_cholce з rerr.ake_fr , 1ья:олняпцие модификацию точек возврата и фрейм; соотв-этсхвенно, вместо полного его построения. В отличии от всех

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

а) адрес следующей альтернативы;

б) адрес следующей цели т.е. продолжение программы.

Вследствии тог' , что эта адреса определены как переходы

кду блоками в случае: •

а) выход FAISE блока заголовка к входу АЪТ блока вариативного заголовка;

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

а) команд унификации - указывают адрес парехода в случае 'Дачи;

0) команды call - переход к следующей цели.

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

Применения этого подхода показывает хорошие результаты для ач, сокержэщих множества альтернативных клозов. Такой является ача раскраски карта: моделирование показывает ускорение олнения в 1,4 раза.

Анализ гистограмм операций еще базового варианта показывают актерную особенность' для выполнения всех задач: время тывания команд занимает до 20% от общего времени выполнения, дложэн способ решения этой • проблемы путем физического целения областей кода программы и данных и введение отдельной а для памяти данных. Это упрощает реализацию конвейеризации элнения команды и считывания следующей. Моделирование показало зрение выполнения программы в среднем в 1,22 раза.

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

- И -

встает проблема обращения к памяти ддаш.

Решением этой проблемы может Ончгь использование буферов да локального стека, кучи и трейла, использование быстрой аппаратного стека, использование каи-памяти. Однако исследован» локальности обращений к памяти данных на программной модел] показывает, что применительно к Прологу как первый, так и второ! способ имеют недостатки: возможно неприемлемое увеличение объем! кэша или к неприемлемая частота перекачки данных.Это утверждена основывается на том факте, что в любой момент выполнения программ мокет произойти обращение к любому участку памяти данных, в то| числе к данным, находящимся в глуОине стеков.

Последний шаг усовершенствования Пролог-процессора предлагав' решение задачи ускорения выполнения программ за счет конвейерной выполнения блоков команд в отличии от существующих разработо] Пролог-процессоров, в которых выполняется конвейеризация на боле! низких уровнях: уровни микрокоманд и команд. Конвейеризаци: выполняется двухпроцессорной однородной структурой с обще! памятью. Идея состоит.в следующем: возложить действия, рзализупц» управление выполнением программы, такие как построение фрейма построение точки возврата, актуализация указателей и переход 1 следующей цели на второй процессор. Назовем его для отличи! процессором управления, а процессор, выполняющий основну] программу назовем .процессором, унификации. Эти процессор однотипные, используют общую память, в которой размещаются стеки ] область кода программы. Доступ к памяти данных осуществляете! через буфер посредством собственных указателей стеков. Пере; началом унификации процессор управления пересылает процессор; унификации значения указателей. Таким образом решается проблем! работы с общими указателями в отек и следоватеоьно конфликт! обращения к памяти данных. Процессор унификации всегда работает I текущим фреймом и фреймом цели, а процессор управлени! подготавливает следующий фрейм за текущим, с которым буде: работать процессор унификации в в случае удачи текущей. Дл; команды re_chol.ce и с)ю1се_р заранее, до входа в процедуру, мота выполнить ззггас! значений аргументов цели на момент унификацш этих аргументов: по мере унификации процессор унификации передав'

процессору управления значения этих аргументов и второй по своим указателям записывает их в "будущий" фрейм. Таким образом команды cholce_p и re_cholce почти полностью (за исключением чтения) могут быть выполнены, параллельно процессу унификации предыдующей по отношению к ним цели. В настоящей работе моделирование конвейерного выполнения записи . аргументов следующей цели процессором управления не проводилось. Для ускорения обращения к памяти данных предложена организация расслоения доступа по Трем модулям памяти. Работа с каадам модулем управляется арбитром памяти.

Применение конвейеризации блоков кода является последним из нагов эволюции Пролог-процессора. Его производительность достигает 230 KLIPS при длительности цикла процессора 100 не и цикла памяти 300 не. Последовательность шагоЕ усовершенствований збеснечивает ускоренно выпотевая программ в среднем в 2,5 раза по сравнению с базовым вариантом.

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

В заключении приводятся основные научные н практические результаты 4

Основные результаты работы

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

2. Предложена модель представления . Пролог-вычислений на зенове этого способа.

3. Разработана архитектура процессора на основе предложенной «удели вычислений. Процессор" отличается конвейерным выполнением 5локов команд.

4. Разработана система прогргл^ого моделирования.