Способ распараллеливания программ в среде логического программирования в вычислительной системе Российский патент 2019 года по МПК G06F16/2458 G06F9/54 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

Известен способ автоматического распараллеливания цикловых областей в алгоритмической части программы (патент РФ №2411569, приоритет от 29.01.2009 г.), позволяющий максимизировать количество параллельных циклов путем применения межпроцедурных и внутрипроцедурных оптимизаций, характеризующийся встраиванием в программу динамических проверок на эффективность распараллеливания, включающий следующие шаги:

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

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

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

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

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

выполняют анализ операций доступа в массивы,

строят индексы доступа в массивы в виде канонических форм сумм произведений;

выполняют слияния циклов;

выполняют вынос инвариантных условий;

изменяют порядок обхода итерационного пространства циклов,

выполняют анализ параллельных циклов,

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

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

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

причем при построении канонических форм используют результаты анализа потока данных методом нумераций значений,

причем при анализе параллельных циклов дерево циклов

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

при этом выполняют следующие виды анализа:

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

анализ на наличие редукций цикла, распознанные редукции исключают при анализе межитерационных зависимостей;

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

анализ массивов на локальность,

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

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

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

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

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

Однако, известный способ имеет недостатки.

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

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

Известен также способ выполнения обработки данных в среде распределенной и параллельной обработки (патент США №9612883, приоритет от 06.12.2013 г.), который также иногда называют MapReduce.

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

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

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

определение, для входных файлов, множества задач обработки данных, включая множество данных, специфицирующих задачи отображения из входных файлов, которые будут обработаны [для получения] промежуточных значений данных, и множества задач сокращения, определяющие промежуточные значения данных, которые будут переработаны в финальные выходные данные;

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

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

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

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

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

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

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

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

Описанный способ принят за прототип.

Основным недостатками известного способа являются то, что известный способ подходит только для некоторых задач ИАД. При этом существуют алгоритмы ИАД, например, Apriori, PageRank и др., для которых данный способ не походит, так как алгоритмы не обладают списочным гомоморфизмом. Также данный способ не раскрывает подходов к реализации алгоритмов ИАД в средах логического программирования, в том числе как следует реализовать логическую программу для организации параллельного логического вывода с применением данного способа, как использовать базу знании среды логического программирования при решении задачи и др. [Gorlatch S. Extracting and Implementing List Homomorphisms in Parallel Program Development // Science of Computer Programming, 1999, v. 33, pp. 1-27; Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters // In Proceedings of the USENIX Symposium on Operating SystemsDesign & Implementation (OSDI), 2004, pp. 137-147; Harmelen F., Kotoulas S., Oren E., Urbani J. Scalable Distributed Reasoning using Map Reduce // Proceedings of the International Semantic Web Conference, 2009, v. 5823, pp. 293-309].

Алгоритмами не обладающие списочным гомоморфизмом являются алгоритмы, которые дают разные результаты, в случае, если применять их к полному набору данных, и в случае, если применять алгоритм к частям исходных данных с последующим объединением результатов. Если разделить исходные данные алгоритма ИАД, не обладающего списочным гомоморфизмом, на части, и далее применить алгоритм отдельно к полученным частям, а после получения результатов для отдельных частей исходных данных объединить полученные результаты, то финальные результаты будут некорректными [Gibbons J. The Third Homomorphism Theorem // Journal of Functional Programming, 1996, v. 6, pp. 657-665].

Раскрытие сущности изобретения

Техническим результатом является

1) расширение класса решаемых задач, включая задачи (алгоритмы), которые не обладают списочным гомоморфизмом,

2) снижение вероятности ошибки пользователя.

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

передачи данных из множества рабочих процессов в главный рабочий процесс,

приема данных в главном рабочем процессе из множества рабочих процессов,

определения номера рабочего процесса в системе,

выполнения множества рабочих процессов, в том числе главного рабочего процесса,

передачи рабочих процессов в системы для выполнения множества рабочих процессов, в том числе и главного рабочего процесса

считывания из входных файлов или баз данных множества исходных данных, специфицирующих задачу,

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

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

получают входные данные и приложение для их обработки;

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

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

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

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

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

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

передачи данных во множество рабочих процессов,

приема данных в главном рабочем процессе,

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

объединения результатов работы множества рабочих процессов в единую промежуточную модель знаний;

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

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

разбиения исходных данных на части для работы одного из множества рабочих процессов;

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

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

обособленных предикатов, реализующих шаг алгоритма;

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

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

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

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

преобразуют исходные данные D из файлов или баз данных в факты базы знаний логической программы;

в процессе логического вызова удовлетворяют предикат, представляющий шаг алгоритма;

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

принимают данные из множества рабочих процессов в главном рабочем процессе;

помещают полученные факты в базу знаний логической программы главного рабочего процесса;

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

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

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

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

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

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

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

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

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

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

Одним из достоинств языков логического программирования при решении задач ИАД является возможность представления результатов работы в логической форме, что является более понятным и информативным, по сравнению с традиционным представлением результатов в числовом виде [Amanda С., King R. Data mining the yeast genome in a lazy functional language - статья по адресу: http://users.aber.ac.uk/afc/papers/ClareKingPADL.pdf]. Данные особенности могут снизить вероятность ошибки пользователя. Однако, отмечаются дополнительные временные затраты при решении задач, связанных с особенностью функционирования логических программ, а также необходимость принятия дополнительных мер для их минимизации, что можно отнести к недостаткам.

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

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

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

Алгоритмы ИАД на входе принимают набор входных данных, а результатом их работы является финальная выходная модель знаний. Таким образом, каждый алгоритм ИАД задает функцию, так как получает на вход набор входных данных и выдает результат применения алгоритма к входным данным в виде финальной выходной модели знаний. Следовательно, алгоритм ИАД можно представить в виде предиката логической программы, исходными данными для которого является набор входных данных D в виде фактов базы знаний логической программы, а результатом его удовлетворения в процессе логического вывода является построенная финальная выходная модель знаний М в виде фактов базы знаний логической программы.

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

Таким образом, алгоритм ИАД можно представить в виде предиката, являющегося левой частью правила, в правой части которого находятся предикаты, представляющие шаги алгоритма. Далее данные предикаты будут называться обособленными предикатами. Здесь и далее для примеров будет использоваться нотация языка логического программирования SWI Prolog [http://www.swi-prolog.org].

где algorithm_induce() - предикат, реализующий алгоритм НАД, в процессе логического вывода,

predicate_i - предикат, реализующий i-й шаг алгоритма ИАД, в процессе логического вывода при удовлетворении данного предиката используется набор исходных данных (D) алгоритма ИАД и промежуточная модель знаний в виде фактов базы знаний логической программы. При этом предикат predicate i, реализующий 1-й шаг алгоритма ИАД, использует только исходный набор данных в виде фактов базы знаний логической программы.

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

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

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

Набор исходных данных (D) алгоритма ИАД в базе данных Prolog-программы нужно представить несколькими видами предикатов, задающих список атрибутов и список векторов. На языке SWI Prolog набор исходных данных (D) можно представить в виде набора предикатов в базе данных логической-программы, задающих список атрибутов (предикат attr_list, attr_values), список век-торов (предикат db vector) и список всех возможных классов целевого атрибута (class_list):

Список из К атрибутов можно определить с помощью предиката attr_list еле-дующим образом

Ниже приведен пример для атрибута 1, который может иметь пять значений: attr_values(attr1, [5, 3, 4, 7, 2]).

Список из L векторов можно представить набором из L предикатов db vector в базе данных Prolog-программы. Предикат db vector имеет вид

Значение i-го атрибута располагается на i-м месте в списке attr_val_list. Ниже приведен пример для вектора 1:

где class<i> - имя i-го класса.

Структура промежуточной (MP) и финальной выходной модели знаний (М) зависит от алгоритма и функции, реализующей ИАД. Промежуточную (MP) и финальную выходную модель знаний (М) удобно представлять в виде предикатов, задающих списки. Например, распространенной среди алгоритмов ИАД является модель знаний в виде деревьев решений. Для деревьев решений узлы дерева и соответствующие им множества, можно представить в виде списков. В общем виде промежуточную модель знаний можно представить в виде множества предикатов в базе знаний логической программы, задающих параметры текущего шага step_context и множества предикатов правил rule.

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

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

Для параллельного выполнения приложения подход целесообразно добавление функций, которые позволит распараллеливать приложение для системы MPI [Message Passing Interface; http://parallel.ru/tech/tech_dev/mpi.html]. При этом правильно сконфигурированная MPI система, установленная на совокупность соединенных между собой систем, каждая из которых имеет один или несколько процессоров и память, обладает возможностью

передачи данных из множества рабочих процессов в главный рабочий процесс,

приема данных в главном рабочем процессе из множества рабочих процессов,

определения номера рабочего процесса в системе,

выполнения множества рабочих процессов, в том числе главного рабочего процесса

передачи рабочих процессов в системы для выполнения множества рабочих процессов, в том числе и главного рабочего процесса

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

осуществления процесса логического вывода;

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

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

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

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

предикат главного рабочего процесса, являющийся правой частью правила, при этом левая часть состоит из предикатов:

передачи данных во множество рабочих процессов,

приема данных в главном рабочем процессе,

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

объединения результатов работы множества рабочих процессов в единую промежуточную модель знаний;

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

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

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

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

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

обособленных предикатов, реализующих шаг алгоритма;

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

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

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

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

Осуществление изобретения

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

Для реализации способа достаточно реализовать выполнение предложенных операций на каком-либо языке логического программирования, например, на языке SWI Prolog [http://www.swi-prolog.org].

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

В качестве примера рассмотрен алгоритм С4.5 [Hssina В. et al. A comparative study of decision tree ID3 and C4.5, статья по адресу:

http://saiconference.com/Downloads/SpecialIssueNo10/Paper_3-A_comparative_study_of_decision_tree_ID3_and_C4.5.pdf;

Деревья решений - C4.5 математический аппарат. Часть 1, статья по адресу:

https://basegroup.ru/community/articles/math-c45-partl].

Для реализации использовалась ОС Linux, SWI Prolog 7.6.1, MPICH [http://www.mpich.org/downloads/]. Алгоритм базируется на теоретико-информационном подходе и является усовершенствованной версией алгоритма ID3 (Iterative Dichotomizer). Алгоритм включает четыре основных шага:

строится корневой узел дерева, с которым ассоциируется все множество векторов V из набора исходных данных D. Множество векторов V задает описанное ранее множество предикатов db vector в базе знаний логической программы;

для каждого формируемого узла дерева решений и ассоциированного с ним множества векторов V_i выбирается атрибут А для разбиения;

если выбранный атрибут А принимает n значений A₁, A₂ … A_n, то выбранный атрибут А разбивает множество векторов V_i на подмножества V_i1, V_i2 … V_in, при А равном, соответственно, A₁, A₂ … A_n;

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

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

Gain(A)=Info(V_i)-Info_A(V_i)

где А - атрибут по которому производится разбиение на текущем шаге;

n - количество значений независимого атрибута А;

t - количество значений зависимого атрибута - классов;

c_j - класс, для которого производится вычисление;

freq(c_j,V_i) - количество векторов из множества V_i, относящихся к классу c_j;

V_ir - подмножество данных V_i, у которых атрибут А имеет r-е значение;

V_i - подмножество векторов ассоциированных с текущим узлом дерева.

Здесь и далее для примеров будет использоваться нотация языка логического программирования SWI Prolog [http://www.swi-prolog.org]. Алгоритм С4.5 может быть представлен в виде:

Предикат algorithm() в процессе логического вывода задает корневой узел дерева константой root node. С корневым узлом ассоциируется все множество векторов V из набора исходных данных D. В правой части предиката algorithm() используется предикаты attr_list(ATTR LIST) и class_list(CLASS_LIST). Первый служит для конкретизации переменной ATTR_LIST множеством, состоящим из всех возможных входных атрибутов. С помощью следующего предиката findall обеспечивается цикл по всем векторам и построение из набора исходных данных D списка VECTORLIST содержащего все множество векторов V.

Далее процесс логически переходит к удовлетворению основного предиката, реализующего алгоритм build_tree и следующих обособленных предикатов (attrib-utes_cycle, calculate_attr_gain) для выполнения шага. После удовлетворения данных предикатов в базе знаний логической программы содержится промежуточная модель знаний MP в виде набора предикатов. При этом в базе знаний логической программы содержатся предикаты, описывающие вычисленные критерии (2) для каждого атрибута. Данные предикаты входят в множество предикатов step_context, описанное выше. В процессе логического вывода выбирается наиболее подходящий атрибут и конкретизируется его номером переменная CURATTR. Далее добавляются соответствующие значениям атрибута CUR ATTR узлы дерева решений к промежуточной модели MP.

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

attributes_cycle - обособленный предикат, в процессе удовлетворения которого выполняется итерацию по атрибутам,

calculate_attr_gain - обособленный предикат, в процессе удовлетворения которого производится вычисление Gain (А) из (2) для обрабатываемого атрибута А. Выполняется итерация по возможным значениям атрибута А для вычисления Info_A(V_i) из (2), а также, выполняет итерацию по всем классам для вычисления Info(V_i) из (2). Результат помещается в базу знаний логической программы.

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

Для реализации алгоритма С4.5 введем представление для входных данных в виде наборов предикатов в базе знаний логической программы. Предикаты attr_list, attr_values задают список атрибутов и их возможных значений. Предикаты db_vector определяют список векторов. Предикат class_list задает список всех возможных классов целевого атрибута

Финальная выходная модель знаний (М) для алгоритма С4.5 представляется в виде дерева решений, которое задает множество предикатов в базе знаний логической программы. Промежуточная модель знаний (MP) для алгоритма С4.5 представляется в виде неполного дерева решений. Также промежуточная модель знаний включает список обработанных на данный момент атрибутов, список вычисленных на последнем шаге критериев (2) для атрибутов, обрабатываемый на данном шаге узел дерева решений. Дерево решений можно представить в виде набора предикатов rule_tree. Данные предикаты входят во множество предикатов rule, описанное выше.

Предикат rule_tree задает узел дерева и имеет два вида:

Здесь константа node root задает корневой узел дерева.

Константа leaf позволяет определить, что предикат задает лист дерева, т.е. у данного узла нет дочерних узлов.

NODE_N - обозначает предикат rule_tree, описывающий дочерний узел. Таким образом, в базе данных может быть несколько одинаковых предикатов, отличающихся NODE_N. Данное множество предикатов описывает все дочерние узлы для узла, у которого атрибут имеет имя ATTR NAME и значение ATTR_VAL. При этом родительским узлом данного узла является узел PARENT NODE или корень дерева.

CLASS_NAME - имя класса, которое соответствует листу дерева.

PARENT_NODE - обозначает предикат rule_tree, описывающий родительский узел.

Корневой узел дерева node_root можно представить в виде набора предикатов:

Узлы второго яруса дерева решений NODE_1… NODE_K определяются аналогично узлу node root. Таким же образом определяются узлы всех последующих ярусов дерева решений, за исключением листов дерева. Определение листов дерева описано выше.

Для параллельного выполнения алгоритма реализацию алгоритма С4.5 в (3,4,5) требуется добавление функционала разбиения данных и объединения ре-зультатов, полученных в разных рабочих процессах.

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

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

Предикат главного процесса может быть определен в виде

где mpi_merge_attr_parall - предикат объединения результатов работы множества рабочих процессов. В процессе его удовлетворения происходит считывание результатов работы каждого рабочего процесса и в базу знаний логической программы главного рабочего процесса записывается значение Gain (А) из (2) для каждого обрабатываемого атрибута.

Остальные предложения языка SWI Prolog (3,4) с предикатом build tree в заголовке остаются аналогичными для предиката build_tree_parall.

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

Предикат рабочего процесса может быть определен в виде:

где attributes cycle и calculate_attr_gain - рассмотренные ранее обособленные предикаты; в примере предиката рабочего процесса для упрощения отсутствует функционал для передачи результатов работы обособленных предикатов в главный рабочий процесс, а также организация для mpi_work_process_predicate некоторого вида рекурсии, характерного для логических языков программирования; mpi_divide_attr_parall - предикат разбиения исходных данных на части для работы одного из множества рабочих процессов; при удовлетворении предиката переменная CUR_ATTR_LIST конкретизируется списком атрибутов предназначенным для данного рабочего процесса, на основании номера рабочего процесса в MPI системе, на котором в данный момент происходит резолюция.

Таким образом, рассмотрена реализация распараллеливания по атрибутам алгоритма С4.5 на основе предложенного подхода.

Если применить концепцию MapReduce без доработок к последовательному варианту (3,4,5) алгоритма С4.5 для парализации по атрибутам, то на фазе Map исходный набор атрибутов будет разбит на N частей, где N - это количество рабочих процессов в системе. Каждая из N частей предназначена для обработки одним процессом на фазе Reduce. После завершения фазы Reduce будет получено N деревьев решений, при этом отсутствует возможность получить из этих N деревьев решений финальную выходную модель знаний, так как алгоритма С4.5 не обладает списочным гомоморфизмом. Отсюда следует, что применение концепции MapReduce к данному алгоритму требует дополнительных методов.

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

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

Изобретение относится к способу распараллеливания программ в среде логического программирования. Технический результат заключается в обеспечении распараллеливания задач (алгоритмов) логического программирования, которые не обладают списочным гомоморфизмом. Формируют предикаты, при удовлетворении которых в процессе логического вывода исходные данные D из файлов или баз данных преобразуются в факты базы знаний логической программы. Осуществляют декомпозицию алгоритма на отдельные шаги, которые представляют собой предикаты, являющиеся левой частью правила логической программы, реализующей алгоритм. Формируют предикат для разбиения исходных данных на части для работы одного из множества рабочих процессов. Формируют предикат для объединения результатов работы множества рабочих процессов в единую промежуточную модель знаний в виде фактов базы знаний логической программы. Формируют предикат приема данных главного рабочего процесса, выполненный с возможностью принимать данные из множества рабочих процессов. Формируют предикат главного рабочего процесса, являющийся правой частью правила. Формируют предикаты рабочих процессов, при этом данные предикаты являются правой частью правил. Запускают на выполнение множество рабочих процессов и главный рабочий процесс, с помощью чего выполняют следующие действия: в процессе логического вывода последовательно удовлетворяют предикаты, представляющие шаги приложения, начиная с первого на множестве рабочих процессов.

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

передачи данных из множества рабочих процессов в главный рабочий процесс,

приема данных в главном рабочем процессе из множества рабочих процессов,

определения номера рабочего процесса в системе,

выполнения множества рабочих процессов, в том числе главного рабочего процесса,

передачи рабочих процессов в системы для выполнения множества рабочих процессов, в том числе и главного рабочего процесса,

считывания из входных файлов или баз данных множества исходных данных, специфицирующих задачу,

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

осуществления процесса логического вывода;

способ заключается в том, что

получают входные данные и приложение для их обработки;

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

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

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

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

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

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

передачи данных во множество рабочих процессов,

приема данных в главном рабочем процессе,

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

объединения результатов работы множества рабочих процессов в единую промежуточную модель знаний;

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

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

разбиения исходных данных на части для работы одного из множества рабочих процессов;

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

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

обособленных предикатов, реализующих шаг алгоритма;

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

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

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

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

преобразуют исходные данные D из файлов или баз данных в факты базы знаний логической программы;

в процессе логического вызова удовлетворяют предикат, представляющий шаг алгоритма;

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

принимают данные из множества рабочих процессов в главном рабочем процессе;

помещают полученные факты в базу знаний логической программы главного рабочего процесса;

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

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

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

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