СПОСОБ РАСПАРАЛЛЕЛИВАНИЯ ПРОГРАММ В МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ Российский патент 2024 года по МПК G06F9/54 G06F9/50 

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

[5] Известен способ выполнения обработки данных в среде распределенной и параллельной обработки, раскрытый в патенте США № US 9612883 B2 (GOOGLE INC.), опубл. 04.04.2017, который также иногда называют MapReduce.

Способ включает:

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

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

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

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

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

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

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

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

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

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

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

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

[9] Основным недостатками известного способа являются то, что известный способ подходит только для некоторых задач ИАД. При этом существуют алгоритмы ИАД, например, 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).

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

[11] Известен способ распараллеливания программ в среде логического программирования в вычислительной системе, раскрытый в патенте РФ № RU 2691860 C1, опубл. 18.06.2019, позволяющий распараллеливать в среде логического программирования программы, реализующие алгоритмы, не обладающие списочным гомоморфизмом, а также уменьшающий вероятность ошибок пользователя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[15] Однако, известный способ имеет недостатки. Указанный способ предназначен для вычислительных систем, представляющих собой кластер из нескольких вычислительных систем, каждая из которых имеет один или несколько процессоров и память. При этом на каждой из вычислительных систем должно быть установлено и сконфигурировано программное обеспечение, предназначенное для обеспечения работы кластера, передачи данных по сети между вычислительными системами, входящими в кластер, для организации распределенных вычислений. Бывают условия, когда вычислительный кластер и соответствующее программное обеспечение отсутствуют. При этом доступна отдельная вычислительная машина с несколькими процессорами и установленной на ней операционной системой общего назначения, например, семейства Windows или Linux. Подобные отдельные вычислительные машины, обладают меньшей вычислительной мощностью, по сравнению с вычислительными кластерами. Тем не менее, параллельные программы на подобных отдельных многопроцессорных вычислительных машинах могут работать на порядок быстрее последовательных реализаций.

РАСКРЫТИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

[16] Технической проблемой (или технической задачей) в данном техническом решении является создание способа распараллеливания программ, связанных с алгоритмами интеллектуального анализа данных (ИАД), в том числе связанных с алгоритмами ИАД, не обладающими списочным гомоморфизмом, в отдельной вычислительной машине с несколькими процессорами и установленной на ней операционной системой общего назначения.

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

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

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

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

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

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

• запуска главного процесса в вычислительной машине,

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

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

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

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

• получают входные данные и приложение, реализующее алгоритм интеллектуального анализа данных (ИАД), предназначенное для обработки полученных входных данных;

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

• осуществляют декомпозицию приложения, реализующего алгоритм ИАД, в последовательность шагов;

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

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

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

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

• формируют рабочие процессы, реализующие шаги приложения алгоритма ИАД, выполненные с возможностью:

выполнять шаг приложения алгоритма ИАД;

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

• формируют главный процесс с возможностью выполнения:

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

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

передачи данных в по меньшей мере одно множество рабочих процессов;

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

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

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

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

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

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

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

запускают множество рабочих процессов;

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

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

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

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

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

получают финальную выходную модель знаний.

[20] Способ распараллеливания программ в многопроцессорной вычислительной машине подразумевает подход к параллелизации программ, реализующих алгоритмы интеллектуального анализа данных (ИАД) в отдельных многопроцессорных вычислительных машинах с использованием многопроцессности. Способ подразумевает использование параллельного программирования. Параллельное программирование - поход к программированию, который предполагает разработку одновременно работающих и взаимодействующих друг с другом программ. Одновременность или параллельность работы программ реализуется, например, путем запуска выполнения программ в разных процессах операционной системы. Многопроцессность является одним из распространенных средств организации параллельных вычислений на многопроцессорной вычислительной машине и поддерживается большим числом современных операционных систем общего назначения.

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

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

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

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

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

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

[27] Здесь и далее для примеров будет использоваться нотация языка программирования С++ [http://www.cplusplus.com/doc/tutorial/].

[28] Набор входных данных (D) алгоритма ИАД удобно представить в виде списочных структур данных. На языке С++ набор входных данных (D) можно представить в виде структуры, содержащей в себе в качестве членов список атрибутов (attributes_list), список векторов (vectors_list) и список всех возможных классов целевого атрибута (class_list):

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

attributes_list = vector<AttrValList>(attr0,…attrK);

где

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

AttrValList attr0 = AttrValList(1.5, 5.0, 3.5, 1.4, 7.5);

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

vectors_list = vector<DataVector>(vector0, … vectorL);

где

vector <i> - структура (типа DataVector), которая состоит из списка конкретных значений каждого атрибута (поле attr_val_list) и значения целевого атрибута(поле target_attr_val). Значение i-го атрибута располагается на i-м месте в списке attr_val_list. Если значение целевого атрибута неизвестно, то оно может быть задано значением, которое специальным нужно выделелить для данной цели. Ниже приведен пример для вектора 0:

DataVector vector0 = {AttrValList(1.5, 4.0, 7.2, 3.5), 5.5};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• формируют рабочие процессы, реализующие шаги приложения алгоритма ИАД, выполненные с возможностью

выполнять шаг приложения алгоритма ИАД;

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

• формируют главный процесс с возможностью выполнения

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

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

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

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

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

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

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

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

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

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

[38] В качестве примера рассмотрен алгоритм построения полного дерева решений для алгоритма CART. (Деревья решений - CART математический аппарат. (Часть 1, статья по адресу: https://basegroup.ru/community/articles/math-cart-part1)

[39] Для реализации использовалась ОС Linuх, язык С++. Алгоритм построения полного дерева решений для алгоритма CART включает четыре основных шага:

• Строится корневой узел дерева, с которым ассоциируется все множество векторов V из набора входных данных D; в (1) множество векторов V задает vectors_list;

• Для каждого строящегося узла дерева решений и ассоциированного с ним множества векторов Vi выбирается атрибут А для разбиения.

• Пусть выбранный атрибут А принимает n значений A1, A2 … An. Тогда выбранный атрибут А разбивает множество векторов Vi на два подмножества Vi1, Vi2, при этом для данных множеств значения атрибута А входят в подмножества значений AVi1, AVi2, соответственно. При этом множества AVi1 и AVi2 не пересекаются и не являются пустыми.

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

[40] На втором шаге для выбора наиболее подходящего атрибута A, соответствующих ему множеств AVi1 и AVi2 используется максимальное значение следующего критерия:

где:

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

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

freq (Am, Vi1), freq (Am, Vi2)- количество векторов из множества векторов Vi1,Vi2, соответственно, для которых атрибут А имеет значение Am;

Vi1,Vi2 - подмножество данных Vi, для которых значения атрибута А входят в подмножества значений AVi1, AVi2, соответственно;

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

[41] Здесь и далее для примеров будет использоваться нотация языка программирования С++ [http://www.cplusplus.com/doc/tutorial/].

[42] Приложение, реализующее алгоритм построения полного дерева решений для алгоритма CART может быть представлен в виде:

[43] Функция Algorithm строит корневой узел дерева, с которым ассоциируется все множество векторов V из набора входных данных D. Выставляет корневой узел в качестве обрабатываемого узла. Данные действия осуществляются в конструкторе класса MP. Далее построенная промежуточная модель знаний MP передается в качестве параметра функциям в теле цикла while для выполнения шага. Шаги приложения реализуются в теле цикла while. После выполнения тела цикла while получает, промежуточную модель знаний MP. Далее функция set_best_attr из step_context, определенном в (2) получает список вычисленных критериев (3) для каждого атрибута, выбирает наиболее подходящий атрибут А, добавляет соответствующие значениям атрибута А узлы дерева решений к промежуточной модели МP. Далее функция Algorithm проверяет, существуют ли узлы дерева решений в промежуточной модели, для которых требуется раскрытие с помощью функции is_finished (d, mp). Если существую, то производится новый шаг в теле цикла while. Если такие узлы отсутствуют, то возвращает в качестве результата финальную выходную модель знаний m.

[44] get_not_handled_attr_list - функция, которая возвращает список атрибутов, которые еще не добавлены к дереву решений.

[45] calculate_attr_criterion - функция, которая вычисляет максимальный критерий из (3) для обрабатываемого атрибута A. Выполняет итерацию по возможным значениям атрибута A для вычисления максимального из (3), добавляет полученные результаты в промежуточную модель знаний.

[46] build_final_model - функция для формирования финальной выходной модели знаний из промежуточной модели знаний, полученной на последнем этапе.

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

[48] Для реализации алгоритма построения полного дерева решений для алгоритма CART введем следующее представление для входных данных:

где

attributes_list - список атрибутов, vectors_list - список векторов, class_list - список всех возможных классов целевого атрибута.

[49] Финальная выходная модель знаний (M) для алгоритма построения полного дерева решений для алгоритма CART представляется в виде дерева решений. Промежуточная модель знаний (MP) для алгоритма построения полного дерева решений для алгоритма CART представляется в виде неполного дерева решений rules_list в (2). Также промежуточная модель знаний включает список обработанных на данный момент атрибутов, список вычисленных на последнем шаге критериев (3) для атрибутов, обрабатываемый на данном шаге узел дерева решений. Данная часть промежуточной модели обозначена как step_context в (2).

[50] Дерево решений можно представить в виде структуры вложенных списков.

[51] В структуре TreeNode член attr_number содержит номер атрибута, которому соответствует данный узел. Члены структуры TreeNode sub_node1, sub_node2 содержат два дочерних узла для данного узла. Таким образом, финальную выходную модель знаний M можно определить как:

где

node_root - корневой узел дерева.

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

где

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

attr_N_value_list_1 - список значений атрибута, соответствующих следующему узлу дерева node_1

attr_N_value_list_2 - список значений атрибута, соответствующих следующему узлу дерева node_2.

[52] Узлы второго яруса дерева решений node_1 и node_2 определяются аналогично узлу node_root. Таким же образом определяются узлы всех последующих ярусов дерева решений.

[53] Для выполнения приложения в параллельном режиме в многопроцессорной вычислительной машине реализацию алгоритма построения полного дерева решений для алгоритма CART в (4) требуется трансформировать и представить в виде реализации рабочих процессов, реализующих шаги приложения и главного процесса. Для реализации главного процесса требуется добавление функционала разбиения данных и объединения результатов, полученных в разных рабочих процессах, реализующих шаг приложения. Указанный функционал реализуется на вычислительной машине, используя, по меньшей мере один, процессор вычислительной машины.

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

[55] Функция MainProc() является реализацией главного процесса для параллельного выполнения алгоритма с распараллеливанием по атрибутам. Функция MainProc() вызывается один раз после старта программы, реализующей главный процесс, при окончании работы функции программа прекращает выполнение.

[56] Функции is_finished, get_not_handled_attr_list, set_best_attr, build_final_model рассмотрены ранее. Функция load_data загружает входные данные из файлов или баз данных в экземпляр d класса D. divide_attr_parall - функция разбиения входных данных на части для работы одного из множества рабочих процессов. Функция MainProc() перед запуском множества рабочих процессов определяет количество процессоров в системе, на которых могут выполняться рабочие процессы. На основе полученного числа, вычисляется диапазон данных, который должен обработать каждый из множества рабочих процессов, реализующих шаг приложения. Далее в процессе работы MainProc() запускается множество рабочих процессов и сохраняется информация о запущенных рабочих процессах в специальных переменных. Также функция, посредством записи в специальные области памяти, разделяемой между процессами, передает каждому из множества запущенных рабочих процессов список атрибутов, предназначенный для обработки рабочим процессом. В примере для упрощения отсутствует реализация.

[57] merge_attr_parall - функция объединения результатов работы множества рабочих процессов в единую промежуточную модели знаний (mp) в виде структуры (2). В процессе ее работы происходит считывание, посредством чтения из специальных областей памяти, разделяемой между процессами, результатов работы каждого из множества рабочих процессов, реализующих шаг приложения. В промежуточную модель (mp) записывается значение из (3) для каждого обрабатываемого атрибута. При этом считывание из памяти, разделяемой между процессами, происходит после того, как все рабочие процессы, выполняющие текущий шаг завершили свою работу, и соответственно, каждый из них записал результаты своей работы в соответствующую область памяти, разделяемую между процессами.

[58] Если достигнут конец алгоритма, то функция build_final_model формирует финальную выходную модель знаний (m) в виде структуры (5).

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

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

[61] Предназначение функции load_data было рассмотрено ранее. Функция receive_attr_list_for_handle посредством чтения из специальной области памяти, разделяемой между процессами, получает от главного процесса список атрибутов, предназначенный для обработки данным рабочим процессом, и возвращает его в качестве результата. Входным параметром функции является переменная proc_number, которая содержит в себе номер процесса в системе. Этот параметр позволяет определить область памяти, разделяемой между процессами, предназначенной для данного рабочего процесса. При этом значение переменной proc_number является значением параметра запуска, который передается главным процессом при запуске программы рабочего процесса. Перед запуском рабочего процесса главный процесс, должен заранее записать данные в область памяти, разделяемой между процессами, которую будет использовать функция receive_attr_list_for_handle при выполнении рабочего процесса.

[62] Функция calculate_attr_criterion рассмотрена ранее. Функция send_results_to_main_proc служит для передачи результатов работы рабочего процесса в главный процесс. Ее реализация в примере для упрощения отсутствует.

[63] Таким образом, рассмотрена реализация распараллеливания по атрибутам алгоритма построения полного дерева решений для алгоритма CART на основе предложенного подхода в многопроцессорной вычислительной машине с установленной на ней операционной системой общего назначения Linux. Применение способа, рассмотренного в прототипе к данному алгоритму, не позволяет реализовать распараллеливание алгоритма на многопроцессорной вычислительной машине под управлением операционной системы общего назначения Linux.

[64] Если применить концепцию MapReduce к последовательному варианту реализации (4) алгоритма построения полного дерева решений для алгоритма CART для парализации по атрибутам, то на фазе Map входной набор атрибутов будет разбит на N частей, где N это количество рабочих процессов в системе. Каждая из N частей предназначена для обработки одним процессом на фазе Reduce. Таким образом, после завершения Reduce фазы будет получено N деревьев решений, при этом отсутствует возможность получить из этих N деревьев решений финальную выходную модель знаний, так как алгоритм построения полного дерева решений для алгоритма CART не обладает списочным гомоморфизмом. Отсюда следует, что применение концепции MapReduce к данному алгоритму не обеспечивает получение выходной модели данных, соответствующей указанному алгоритму, в отличии от предложенного способа, который позволяет получить выходную модель данных, соответствующую алгоритму, за счет осуществления предложенного технического решения, описанного выше.

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

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

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

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

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

• запуска главного процесса в вычислительной машине,

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

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

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

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

• получают входные данные и приложение, реализующее алгоритм интеллектуального анализа данных (ИАД), предназначенное для обработки полученных входных данных;

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

• осуществляют декомпозицию приложения, реализующего алгоритм ИАД, в последовательность шагов;

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

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

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

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

• формируют рабочие процессы, реализующие шаги приложения алгоритма ИАД, выполненные с возможностью:

выполнять шаг приложения алгоритма ИАД;

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

• формируют главный процесс с возможностью выполнения:

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

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

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

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

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

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

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

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

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

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

запускают множество рабочих процессов;

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

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

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

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

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

получают финальную выходную модель знаний.