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

РГ 6 ОД

9 - ИАЙ Ш93

С ■■ '" САНКТ-ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ'УНИВЕРСИТЕТ

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

Танев Иван Танев

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ПРОЛОГА НА БАЗЕ ГЕТЕРОГЕННОГО МУЛЬТИПРОЦЕССОРА С.ОБЩЕЙ ПАМЯТЬЮ

Специальность: Об. 13.13 - Вычислительные машины, комплексы, системы и сети

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

Санкт-Петербург - 1993

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

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

Официальные оппоненты: доктор технических наук, профессор ТОРГАШЕБ В. А. кандидат технических наук, доцент СУЛЬПОВАР В. Л

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

Завдп-а диссертации состоится " ^ " 1993 г.

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

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

С диссертацией Аголшо ознакомиться в библиотеке университета. Автореферат разослан " ¥ " ¿-¿¿¿^_1ддд .

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

Балакин Е. К

- 1 -

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

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

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

На современных ЭШ один шаг логического вывода в силу большого семантического разрыва требует исполнения порядка 100. .1000 машинных команд. Производительность универсальных 'ЭВМ составляет .1.. 20 млн. кошанд/с . Следовательно, реализация Пролога на таких' универсальных ЭЕЫ обеспечит производительность порядка 1.. 200 к!ЛР5, что недостаточно для решения в реальном масштабе времени больших, требующих десятков и сотен миллионов логических выводов, задач Ш и 30.

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

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

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

- 'уровень компилятора : применение методов выделения параллелизма в исполняемом коде на этапе компиляции с испольво-

-'г -

ванием статического анализа зависимости по данным?

- уровень процессора : повышение тактовой чайтоты, уменьшение количества тактов на логическом выводе путем сокрашэния семантического разрыва, микропрограммная интерпретация W-кода, RISC;

- системный (межпроцессорный) уровень . . мультипроцессор-, ная или муяьтимашинная конфигурация системы с целью увеличения вычислительной мощности при помощи увеличения числа процессоров или ЭВМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

- Получены количественные оценки эффективности системы, которые позволяют сделать заключение о максимальной производительности порядка 1.05 №ЛРЗ при длительности цикла синхронизации £С0не, что соответствует выполнению одного логического вывода за 5 тактов.

Практическая ценность заключается в следующем:

- Разработано (в системе команд последовательного Я!5С-процессора с минимальным ее расширением командам! поддержки параллелизма) ядро системного программного обеспечения параллельной Пролог-системы;

- Предложена гетерогенная, мультипроцессорная, скльносва-аанная структура параллельной Пролог-системы с испольэованем р Качестве вычислительных узлов последовательных ШЗОПро-лог-процессоров с минимальным (ориентированным на параллелизм) расширением функциональных возможностей;

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

"Внедрение результатов работы осуществляется в рамках курса "Специализированные процессоры ЭВМ".

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

числительные системы с массовый параллелизмом", г. Санкт-Петера бург 1992 г.

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

Структура м обьем работы Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 68' наименований, и 27 приложений. Основная часть работы наложена на 145 страницах машинописного текста.- Работа содержит 27 рисунков и 15 таблиц.

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

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

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

Среди факторов, определяющих эффективность подобных систем можно выделить:

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

- способ декомпозиции задачи логического вывода на относительно наэависиыые подзадачи (процессы) -, фактор "Модель-процессов";

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

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

Согласно модели И/ИЛЙ-процессов в системе динамически создаются два типа процессов: И-процессы и ШШ-процессы, взаимодействие меяду которыми осуществляется через сообщения.

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

Модель И/ИЛИ-процессов Конери предполагает распределенную реализацию, что связано с большими затратам! времени исполнения либо на отдаленный доступ к распределенной среде связывания переменных, либо к затратами времени исполнения на ее замыкание и копирование.

Эти факторы являются apryi.ieHTa.in в пользу выбора в качестве базового, прототипа системы, реализующей модель, И/МИ-процессов Конери на сильносвязанной архитектуре.

Во второй главе приводится описание метода исследования. Аргументируется совершенствование базового прототипа в процессе его . эволюции в Первый прототип разрабатываемой Пролог-системы.

Метод исследования основывается на поэтапном совершенствовании разрабатываемых Пролог-систем путем выполнения рекурсивно вызываемых этапоЕ разработки-.

Этап 1 : Выявление узких мест и возможных способов повышения производительности;

Этап 2 : Разработка модели процессов;

Этап 3 : Разработка архитектуры системы;

Этап 4 : Программное моделирование.

• При этом, выполнение этапа 1 сводится к рекурсивному вызову выполнения ЭтапоЕ 1-4 на следующем по вложенности уровне. Каждый уровень вложенности ассоциируется с определенной степенью совершенства системы, с определенной степенью редукции требуемой сложности системы и наконец, с определенным хронологическим этапом выполнения работы. В диссертационной работе нашли отражения результаты работы двух, наиболее внешних уровней (соогЕетсвенно уровень 0 и уровень 1), поскольку именно эти уровни связаны с выполнением наиболее значительных шагов ка пути в поставленной цели.

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

уровне архитектуры системы.

На уровне модели процессов Первый прототип отличается от базового (т. е. от модели процессов Конери) способа?® решения основных проблем И-параллелизма и ИЛИ-параллелизма. Проблема И-параллеливма, которая заключается в обеспечении компромисса между степенью реализуемого в системе И-параллелизма и затратами времени исполнения на его выявление и реализацию решена путем применения И-параллелиамв бектрекинга, затраты времени Исполнения на которого полностью отсутствуют. Проблема. ИЖ-па-раллелизма заключается с эффективности поддёрдаи ■ дополнительных структур данных, обеспечивающих, одновременное хранение нескольких связываний (соответствующих равным путям логического вывода) одной и той же переменной. Данная проблема решена с использованием механизма хэш-окон.

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

- между выполнением логического вывода нг Пролог-процессорах (ПП) и обработкой межпроцессорных сообщений на процессорах обработки сообщений (НОС)-;

- к:ежду обработкой равных сообщений на разных ПОС. '

. Как ПП, так и ПСС являются RISC-прсдессорами, ориентированными на обработку самоопредедяемых (тегированных) данных, система команд которых расширена (по сравнению с системой команд разработанного автором последовательного интерпретатора языка. Пролог) - командами установки и проверки аппаратных флагов.

В'систему введен специальный блок синхронизации, осуществляющий аппаратную поддержу механизма взаимодействия между ПП и ПОС.

Б системе используется логически общэе адресное пространство, параллельный доступ к которому со стороны процессоров (как ПП, так и ЮС) осуществляется путем его тонкого расслоения среди физически отдельных модулей памяти. Связь процессоров с модулями памяти осуществляется через полный' матричный коммутатор.

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

с формальной стороны аргументируются принимаемые решения в процессе разработки Первого прототипа!

В третьей главе приводится подробное описание 'системы программного моделирования Первого прототипа параллельной Пролог-системы. Приводятся результаты моделирования исполнения 8-ми тестовых Пролог-программ. Выполнено сравнение времени исполнения одной 'и той же задачи на распределенной мультитранспьютерной системе и.на разработанном Первом прототипе.

Система программного 'моделирования (СПМ) предназначена для адекватной имитации исполнения Пролог-программы на разрабатываемой параллельной Пролог-с'йстеме путем моделирования по-тактного исполнения ее кода. СПМ выполняется в монопрограммной, однопроцессорной - среде (MS-DOS). Разработана с применением принципов модульного программирования и динамической загрузки модулей, с помощью Turbo Pascal 6.0 и библиотеки Turbo Professional. ' Обьем исходного текста составляет порядка 13000 строк, суммарный обьем исполнимых модулей - порядка 2Б0 кБ. Высокую степень адекватности СПМ обуславливает достоверность получаемых результатов моделирования, которые используются с ■ целью выявления, понимания и устранения причин, сдерживающих рост производительности разрабатываемых прототипов Пролсг-сис-темы в процессе ее эволюции. Степень адекватности СПМ определяется учетом всех непроизводительных затрат времени исполнения, вызванных:

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

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

С помощью СПМ выполнено моделирование исполнения 8-ми тестовых задач, отличающихся как степенью, так и типом внутреннего параллелизма. Максимальная производительность, достигаемая Первым.прототипом при длительности такта синхронизации EDO не составляет порядка 110 kLIPS.

В четвертой главе приводятся основные шаги эволюции Первого прототипа в конечную Пролог-систему. ■ Эти шаги заключаются в: •

- обнаружении (путем анализа результатов, полученных с по-

- а -

мощью ОШ) причин, сдерживающих рост произвдительностл;

- принятии решения на уровне модели процессов с целью ус-> гранения этих причин;

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

- программном моделировании системы.

Необходимо отметить, что эти этапы соответствуют выполнению этапов разработки 1-4, приведенных во второй глаЕе.

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

- наличием эффекта Гайдна в динамике освобождения, процеег-ссрое;

- наличием трэшинга ИЛИ-процесса (значительное увеличения доли времени на переключение контекста) при передачи ответа от его наследника к его предшественнику;

- Наличием большого временного интервала (50Х и более), S течении которого логические выводы не выполнятся, но осуществляется передача ответов-решений от процессов листьев к процессу-корню дерева процессов.

С целью устранения приведенных выше временных затрат не уровне модели процессов реализован механизм ускоренной передачи ответов совместно с компиляцией Пролог-программы в• дереве И/ИЛИ- процессов. Новизна механизма ускоренной передачи заключается в том, что ответ-решение передается' не непосредственно-иу-предиесжвеннику, а процессу-получателю ответа. Определение этого ¡процесса происходит на втапе компиляции и дополнительны* временных затрат не требует.

Архитектура высокого уровня при этом представлена набороь процессов (представленных дескрипторами," кодами исполнения а. фреймами данных) и набором сообщений, с помощью которы;: осуществляется взаимодействие между процессами. Новизна на уровне архитектуры состоит в том, что процесс активируется не сообщением создания и активации CREATE, а сообщением активации потенциально созданного процесса - INVOKE. Новизной также является формат дескриптора, позволяющего определять поддеревья, процессы в которых являются потенциальными отправителями ответов- реизкий.

Анализ результатов моделирования показывает, что припеке-

bus механизма ускоренной передачи ответа совместно с компиля-. цией позволяет ускорить исполнение как параллельных задач, так и последовательных (таких, как APPEND, MEMEER) до 2.3 раза.

" При этом, основным препятствием к более эффективному исполнению Пролог-программ является большая доля времени исполнения, расходуемая на загрузку всех процессоров системы в процессе разрастания дерева процессов (на начальных стадиях исполнения). Эта доля при большом количестве Пролог-процессоров может составлять 60% 'и более. Причиной этому является сравнительно большой интервал времени между• активацией процесса и активацией этим процессом эго наследника. Этот интервал времени соответствует длительности унификации. С целью сокращения указанного интервала времени предлагаются два способа, первый из которых ориентирован на более глубокую степень параллелизма, второй - на применение дополнительного (вертикального) конвейера процессов.

Первый способ основывается на использовании параллелизма между унификациям! (ПЫУ) и заключается в параллельной унификации заданной цели с несколькими (пли всеми) заголовками правил-кандидатов на унификацию. На уровне модем: процессов этот спссоб представлен механизмом разщепления ЙЛИ-процесса, выполняющего унификацию заданной цели на процессы-двойники, выполняющие ровно одну унификацию-унификацию заданной цели с одним лишь заголовком правила-кандидата на унификацию. Количество активированных этаким образом двойников определяется значением min [количество альтернативных клозов-1,

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

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

исполнение на отдельных процессорах отдельных фрагментов кода одного' и того 'же процесса.

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

Ускорение в системе, достигаемое при моделировании исполнения задач с большой степенью ИЛИ-параллелизма с использованием ПНУ составляет порядка 1. 4 раза. Зто ускорение достигается за счет лучшей загрузки процессоров на начальных стадиях исполнения Пролог-программы.

Дальнейшее улучшение динамики загрузки Пролог-процессоров, а'также увеличение их количества в процессе исполнения, последовательных задач (й- и ИЛИ-параллелиэм в терминах процессов Конери в которых полностью отсутствует) может быть достигнуто путем конвейерной активации процессов-наследников (КАП). Этот способ основан на сокращении интервала времени Между двумя логическими выводами, выполняемыми на двух ИЛИ-процессах, находящихся в отношении предшественник-наследник. Этот интервал времени составляет

TQ+T1+T2+T3,

где

ТО-Бремя подготовки к унификации;

Т1-время.собственна унификации;

Т2-латентное время приема сообщения INVOKE;

ТЗ-время обработки сообщения INVOKE.

КАП основан на идее полного исключения из этой сум^ш времен времени унификации И. ■ Эта идея реализована путем активации процесса-наследника непосредственно после выполнения подготовки к унификации и задолго до ее завершения. Ускорение более чем в 2 раза возможно в случае, если

(TD+T1+T2+T3) /(TQ+T2+T3) >2 Т.е. Tl>TQ-+T2+T3.

Однако, именно при соблюдении данного условия возникает конфликт при доступе к совместно используемому фрейму - фрей-

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

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

На уровне архитектуры КАП представлен сообщением- С:, уникальной семантикой. - "активировать конвейерным образом .наследник" 1NV0KE_P1PE обработка которого (и соответственно, активация процесса-наследника) осуществляется только в-случае наличия в системе свободных Пролог-процесГсоров. Активация процесса в -^случае отсутствия свободных Пролог-процессоров во первых, противоречила бы смыслу конвейеризации, поскольку конвейер определен только'между активными, но не между готовыми к исполнению (и находящимися в очереди ) процессами; и во вторых, привела бы к большим временным затратам, связанным с поиском и исключением ив очереди-готового к исполнению конвейерного процесса в случае неудачной унификации в процессе-предшественнике. .

Реализация КАП приводит к ускорению исполнения параллельных задач до 30%, в то время- как исполнение последовательных вадач (таких, как APPEND и f.EMBER) сопровождается 5-кратным ускорением по сравнению с реализацией в системе без НАЛ. В последнем случае ускорение является следствием лучшей загрузки Пролог-процессоров, число которых составляет порядка 7-процес-соров. Исполнение же последовательных вадач в системе без КАП, в силу отсутствия как И-, так.и ШЩ-параллелизма сопровождает-

- 12 -

ся аагрувкой не более двух Пролог-процессоров.

Применение механизма КАП является последним на шагов эволюции Первого прототипа в Конечную Пролог-систему. Производительность Конечной Пролог-системы при репйнии параллельных задач, достигает порядка 1.0Б ML IPS при длительности такта синхронизации ?00не, что соответствует выполнению логического вывода за Б тактов работы системы.

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

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

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

1. Разработан механизм компиляции Пролог-программ в дерево процессов;

2. 'Разработан аффективный способ взаимодействия между процессами;

3. Предложен способ реализации глубокого уровня параллелизма и конвейерной активации процессов;

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

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

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

Публикации по теме диссертации

1. II Т., Тодорова Е. С. Интерпретатор языка Пролог £ системе команд RISC// Иэзестия ЛЭТИ. - 1391. - вып. 436 -

с. 130 -, 133.

2. Танев И. Т., ¡Ьэмичев Е. С. Параллельная мультипроцессорная Пролог-система//Известия ЛЭТИ. - 1992. - вып. 444 - с. 101 -106.