Анатомия источника знаний

Источники знаний представляются как объекты, процедуры, множества правил, логические утверждения, а в некоторых случалх и целые программы. Источники знаний включают часть условий и часть действий. Если «классная доска» содержит информацию, которая удовлетворяет части условий некоторого источника знаний, то его часть действий активизируется. Инглемор (Englemore) и Морган (Morgan) в своей работе [14] четко описывают обязанности источника знаний.

Каждый источник знаний отвечает за знание условий, при которых он может внести свой вклад в решение. Каждый источник знаний имеет предусловия, т.е. условия, которые должны быть записаны на «классной доске» и существовать до того, как будет активизировано тело источника знаний. Источник знаний можно рассматривать как большое правило. Главное, чем отличается правило от источника знаний, состоит в степени детализации знаний. Часть условий этого большого правила называется предусловием источника знаний, а часть действий — его телом.

Здесь Инглемор и Морган не определяют ни единой детали части условий или части действий источника знаний. Они представляют собой логические конструкции. Часть условий может иметь форму простого значения булевого флага на «классной доске» или сложной последовательности событий, поступающих в очередь событий в пределах определенного периода времени. Аналогично часть действий источника знаний может быть выражена простой инструкцией, выполняющей операцию присваивания переменной некоторого выражения, или механизмом прямого построения цепочки в экспертной системе. Это описание широты диапазона еще раз подчеркивает гибкость модели «классной доски». Для наших целей вполне достаточно конструкции С++-класса и понятия объекта. Каждый источник знаний должен быть объектом. Часть действий источника знаний должна быть реализована в виде методов объекта, а часть условий — в виде его членов данных. Если объект находится в определенном состоянии, то его часть действий должна быть активизирована. Проще говоря, мы реализуем источники знаний в виде потоков или процессов. Следовательно, для каждого потока и для каждого процесса должен существовать только один источник знаний. Применяя к «классной доске» PVM-механизм, источник знаний будет эквивалентом PVM-задачи. Логическая схема источника знаний показана на рис. 13.3.

Часть «Условия» каждого источника знаний обновляется «из закромов» «классной доски», а часть «Действия» источников знаний обновляет ее содержимое. Обратите внимание на то (см. рис. 13.3), что между пространством процесса и источником знаний (или между пространством потока и источником знаний) существует взаимно однозначное отношение. Важным атрибутом источника знаний является его автономность. Каждый источник знаний является специалистом в своей области и почти не зависит от других решателей задач. Это составляет одно из требуемых качеств для параллельной программы. В идеале задачи в параллельной программе могут выполняться одновременно, почти не нуждаясь во взаимодействии с другими задачами. Такое поведение в точности описывает схему модели «классной доски». Источники знаний действуют независимо, и любое взаимодействие осуществляется посредством «классной доски». Поэтому источник знаний (с его точки зрения) действует в одиночку, получал дополнительную информацию от «классной доски» и записывал на «классную доску» свои изыскания. О деятельности других источников знаний и их стратегиях поведения ему ничего не известно. В модели «классной доски» задача делится на ряд автономных или полуавтономных решателей задач. В этом и состоит преимущество модели «классной доски» перед другими моделями. В самой гибкой конфигурации источники знаний должны быть интеллектуальными агентами. Агент должен быть совершенно самодостаточным и способным действовать самостоятельно при минимальной потребности к взаимодействию с «классной доской». Именно интеллектуальный агент представляет самую грандиозную перспективу для реализации крупномасштабного параллелизма.

Стратегии управления для «классной доски»

В реализации модели «классной доски» прелусмотрено несколько уровней управления, обеспечивающих возможность параллельного функционирования источников знаний. На самом нижнем уровне их схемы синхронизации должны защищать целостность «классной доски». «Классная доска» является критическим разделом, поскольку она представляет собой совместно используемый модифицируемый ресурс. В параллельной среде доступ со стороны источников знаний для чтения и записи должен быть скоординирован и синхронизирован. Координация и синхронизация может включать блокировку файлов, семафоры, мьютексы и т.д. Этот уровень управления не включается непосредственно в решение, над которым работают источники знаний. Его можно назвать вспомогательным уровнем управления, и он не должен зависеть от специфики задачи, решаемой с помощью «классной доски». В нашем архитектурном подходе этот уровень управления реализуется интерфейсными классами (например, классами мьютекса и семафора, использованными в главе 11). Вспомните, что действия, инкапсулированные в этих классах, не зависят от приложения, в котором они используются. Для параллельных реализаций «классной доски» на этом уровне выбирается один (или больше) из четырех типов параллельного доступа, которыми должны обладать алгоритмы или эвристические правила источников знаний для физической реализации «классной доски». Другими словами, пользователи «классной доски» могут использовать EREW-, CREW-, ERCW- или CRCW-доступ. Именно характер доступа определяет, как будут использованы примитивы синхронизации. Описание упомянутых здесь типов доступа приведено в табл. 13.1.

Таблица 13.1. Четыре типа параллельного доступа, используемых в модели «классной доски»

EREW Exclusive Read Exclusive Write (монопольное чтение и монопольная запись)

CREW Concurrent Read Exclusive Write (параллельное чтение и монопольная запись)

ERCW Exclusive Read Concurrent Write (монопольное чтение и параллельная запись)

CRCW Concurrent Read Concurrent Write (параллельное чтение и параллельная запись)

При разделении «классной доски» на части будет определено, какие из типов параллельности (см. табл. 13.1) подходят больше всего. Самый гибкий тип (CRCW) доступа может быть достигнут в зависимости от структуры «классной доски». Например, если используется 16 источников знаний, и каждый из них получает доступ к собственному сегменту «классной доски», то такие источники знаний могут параллельно считывать данные с «классной доски» и записывать их туда, не испытывал проблем «гонки» данных.

Следующий уровень управления включает выбор источников знаний. При этом определяется, какие из них следует включить в поиск решения и какие аспекты задачи им поручить. На этом уровне управления принимается решение перенести центр (фокус) внимания на ту или иную область задачи, что и определяет выбор соответствующих источников знаний. При решении задач любого типа всегда ставятся сле-лующие вопросы: «с чего начать?» и «что нужно для этого знать?». Уровень центра внимания отвечает за начальные условия задачи, а также определяет, какие источники знаний необходимо использовать и в какой момент они должны «вступить в игру». «Классной доске» должно быть известно, какими источниками знаний она может располагать, и обычно источники знаний принимают сообщения или параметры, которые предписывают, как им действовать или в какой области пространства решений следует начинать поиск. Для параллельных реализаций этот уровень управления определяет базовую модель параллелизма (распределение решателей задачи). Обычно для «классной доски» используется модель MPMD (Multiple Programs Multiple Data — множество программ и множество потоков данных), известнал также как MIMD (multiple-instruction, multiple-data — множество потоков команд и множество потоков данных), поскольку каждый источник знаний (решатель задачи) имеет собственную область специализации. Однако сама природа задачи иногда может дать право на использование такой популярной модели, как SPMD (Single Program Multiple Data —одна програ мм а, неско л ько потоков дан н ых). В это м с л учае урове н ь управ л е н ия породит N одинаковых источников знаний, но передаст им различные параметры.

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

Обратите внимание на то, что в первой из представленных конфигураций (см. рис. 13.4) механизм управления содержится в самой «классной доске», а не в отдельном модуле и не в источниках знаний. В этой конфигурации блок управления проектируется как часть класса «классной доски». Поскольку на уровнях 2 и 3 необходимо двустороннее взаимодействие, имеет смысл, чтобы «классная доска» порождала процессы или потоки, которые будут содержать источники знаний. Если «классная доска» порождает процессы или потоки, ей нетрудно получить доступ к идентификационному номеру любого потока или процесса. Это позволяет «классной доске» легко передавать сообщения источникам знаний и осуществлять управление процессами и потоками. Если «классной доске» по некоторой причине нужно прекратить деятельность конкретного источника знаний, то доступ к идентификатору потока или процесса делает эту задачу очень простой. Обратите внимание на то, что в одном из представленных на рис. 13.4 вариантов блок управления яв л яется внешни м по отношению к «к л ассной доске» и источника м зна н ий. В это м случае иде н тификационный но м ер потока и л и процесса должен быть явным образом связан с модулями управления.

Реализация модели «классной доски» с помощью CORBA-объектов

Вспомните, что CORBA-объект (см. главу 8) является независимым от платформы распределенным объектом. К CORBA -объектам могут получать доступ процессы, выполняющиеся на одном или на разных компьютерах, подключенных к сети. Это делает CORBA-объекты кандидатами для использования в PVM-средах, когда программа делится на ряд процессов, которые могут (или не могут) выполняться на одном и том же компьютере. Обычно PVM-среда используется для передачи сообщений при вторичной роли общей памяти (если она вообще существует). Введение понятия разделяемого и доступного по сети объекта существенно усиливает вычислительные мощности PVM-среды. Следует иметь в виду, что с помощью CORBA-объектов можно смоделировать все, что позволяют смоделировать не распределенные объекты. Это означает, что PVM-задачи, которые имеют совместный доступ к CORBA-объектам, могут получать доступ к контейнерным объектам, объектам оболочки, шаблонов, доменов и другим видам вспомогательных объектов. В данном случае мы хотели бы, чтобы PVM-задачи имели доступ к объектам «классной доски». Поэтому модель передачи сообщений мы дополняем совместным доступом к сложным объектам. Помимо PVM-задач, получающих доступ к распределенным CORBA-объектам, к ним также могут обращаться задачи, порожденные функциями posix_spawn() или fork-exec. Эти задачи выполняются в отдельных адресных пространствах одного и того же компьютера, но могут, тем не менее, связываться с CORBA-объектами, которые расположены либо на том же, либо на другом компьютере. Поэтому, несмотря на то что все задачи, созданные с помощью функций posix_spawn () или fork-exec, должны размещаться на одном компьютере, CORBA-объекты могут располагаться на любом компьютере.

Пример использования CORBA-объекта «классной доски»

Чтобы продемонстрировать наше представление о CORBA-ориентированной «классной доске», рассмотрим ее реализацию, предложенную разработчиками из компании Ctest Laboratories. И хотя полное описание этого варианта выходит за рамки нашей книги, мы все же остановимся на самых важных аспектах «классной доски» и источников знаний, имеющих отношение к нашему архитектурному подхолу к параллельному программированию. «Классная доска» реализует услуги программно-ориентированного консультанта по составлению расписания учебных курсов. «Классная доска» решает задачи планирования учебных курсов для студента типичного колледжа. Студенты часто сталкиваются с проблемой «неудобного» расписания занятий. Во время регистрации курсов всегда существует конкуренция за места в аудиториях. В какой-то момент важные для студента курсы попросту «закрываются». Ведь не зря существует печально известное правило, соответствующее дисциплине обслуживания очереди: «первым пришел — первым обслужен». Поэтому во время регистрации, когда десятки тысяч студентов пытаются записаться на ограниченное количество курсов, важным фактором выступает своевременность. Студент желает пройти курсы, которые дают право на получение диплома. В идеале эти курсы должны быть разнесены во времени. Кроме того, студент хотел бы поддерживать определенную учебную нагрузку и иметь свободное время для домашних и факультативных занятий.

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

Важно отметить, что «классная доска» имеет доступ реального времени к академической характеристике студента и текущим курсам (с открытым или закрытым приемом) в любой момент периода регистрации. Кроме того, «классная доска» имеет доступ к дипломному плану студента, академическим требованиям для реализации этого плана, расписанию «готовности» студента посещать занятия, данным о его целях и предпочтениях и т.д. Все эти элементы моделируются с помощью С++- и CORBA-классов и образуют компоненты «классной доски». Для упрощения нашего примера мы рассмотрим только следующие четыре источника знаний:

• консультант по общеобразовательным курсам;

• консультант по основным курсам;

• консультант по факультативным курсам;

• консультант по непрофилирующим курсам.

Итак, рассмотрим фрагмент CORBA-интерфейса «классной доски».

// Листинг 13.1. CORBA-объявления, необходимые для нашего // класса «классной доски»

typedef sequence< long> courses;

interface black_board{

//...

void suggestionsForMajor(in courses Major);

void suggestionsForMinor(in courses Minor);

void suggestionsForGeneral(in courses General);

void suggestionsForElectives(in courses Electives);

courses currentDegreePlan();

courses suggestedSchedule();

//...

};

Главная цель интерфейса black_board — обеспечить доступ для чтения и записи со стороны источников знаний. В данном случае при разделении «классной доски» необходимо предусмотреть сегменты для каждого источника знаний. [23]Это позволяет источникам знаний получать доступ к «классной доске» посредством CRCW-стратегии. Другими словами, несколько типов источников знаний могут получить доступ к «классной доске» одновременно, но источники знаний одинакового типа должны быть ограничены применением CREW-стратегии. Любой метод или функция-член, с помощью которого источники знаний будут получать доступ к»классной доске», должен быть определен в интерфейсном классе black_board. Класс courses объявляется с использованием типа CORBA, и поэтому его можно применять в качестве параметра и значений, возвращаемых методами при взаимодействии между источниками знаний и «классной доской». Поэтому эти объявления класса black_board

courses Minor; courses Major;

будут использованы для представления информации, которая либо записывается на «классную доску», либо считывается с нее. Тип courses — это синоним для CORBA-типа sequence< long>, полученный в результате использования typedef-объявления. Тип sequence< long> в CORBA представляет собой вектор (массив) переменной длины. Это означает, что переменные типа courses используются для хранения массива элементов типа long. Каждый long-элемент предназначен для хранения кода курса. Каждый код курса представляет курс обучения, предлагаемый в колледже. Поскольку С++ не имеет типа sequence, то объявление sequence< long> преобразуется в С++-класс. Этот класс имеет такое же имя, как sequence< long> typedef: courses. Процесс преобразования из CORBA-типов в типы С++ происходит во время IDL-компиляции при построении CORBA-приложения. IDL-компилятор должен перевести объявление sequence< long> в С++-код, С++-класс courses должен автоматически включать перечисленные ниже функции.

allocbuf() freebuf() get_buffer() length() operator[] release() replace() maximum ()

Источники знаний будут взаимодействовать с «классной доской» с помощью этих методов. Объявление sequence< long> «невидимо» для источников знаний; они «видят» только класс courses. Поскольку CORBA поддерживает такие типы данных, как структуры (struct), классы, массивы и последовательности, источники знаний могут обмениваться с «классной доской» высокоорганизованными объектами. Это позволяет программисту поддерживать объектно-ориентированное представление при обмене данными с «классной доской». Поддержка объектно-ориентированного представления (где это необходимо) является важным фактором понижения уровня сложности параллельного программирования. Способность просто считывать с «классной доски» и записывать на нее сложные объекты или даже иерархии объектов упрощает программирование в параллельных приложениях. Нет необходимости выполнять преобразование из примитивных типов данных в сложные объекты: можно совершать обмен сложными объектами напрямую.