Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms
An approach to formalized development of parallel programs using ontologies and algebra-algorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain – data, functions and relations between functions. Once...
Saved in:
| Date: | 2026 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
PROBLEMS IN PROGRAMMING
2026
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| _version_ | 1868747442291212288 |
|---|---|
| author | Doroshenko, A.Yu. Yatsenko, E.A. |
| author_facet | Doroshenko, A.Yu. Yatsenko, E.A. |
| author_institution_txt_mv | [
{
"author": "A.Yu. Doroshenko",
"institution": "Institute of Software Systems NAS of Ukraine"
},
{
"author": "E.A. Yatsenko",
"institution": "Institute of Software Systems NAS of Ukraine"
}
] |
| author_sort | Doroshenko, A.Yu. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-06-22T16:37:55Z |
| description | An approach to formalized development of parallel programs using ontologies and algebra-algorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain – data, functions and relations between functions. Once the skeleton of the program has been built, further development can be done in automated manner with the Integrated toolkit for Design and Synthesis developed by the authors, which is based on using algorithmic algebras facilities. The application of the approach is illustrated with an example of developing parallel MPI program in the subject domain of sorting algorithms.Problems in programming 2008; 4: 94-103 |
| first_indexed | 2026-06-23T01:00:39Z |
| format | Article |
| fulltext |
Інструментальні засоби і середовища програмування
94
УДК 681.3
А.Е. Дорошенко, Е.А. Яценко
СРЕДСТВА АВТОМАТИЗАЦИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ
ПРОГРАММ НА ОСНОВЕ ОНТОЛОГИЙ И АЛГЕБР
АЛГОРИТМОВ
Предложен подход к формализованной разработке параллельных программ на основе использования
онтологий и аппарата алгебры алгоритмов. С помощью онтологии описываются основные объекты раз-
рабатываемой программы из выбранной предметной области – данные, функции и взаимосвязи между
функциями. Дальнейшее проектирование приложения осуществляется в разработанном интегрирован-
ном инструментарии проектирования и генерации программ, основывающемся на системах алгоритми-
ческих алгебр. Подход проиллюстрирован на примере разработки параллельной MPI-программы
сортировки.
Введение
В последние годы онтологии широ-
ко используются для описания и синтеза
программ [1–3]. Отметим, что одной из
основных причин нарастающего интереса
к онтологиям является разработка Semantic
Web [4] и Semantic Grid [5], которая может
рассматриваться как управление знаниями
в глобальном масштабе. Онтологии по-
добны концептуальным методам модели-
рования, таким, как UML [6] или модель
типа “сущность–связь” [7]. Однако, онто-
логии как правило содержат в себе осно-
ванные на логике языки представлений с
формальной семантикой и выполнимыми
вычислениями. Последние позволяют про-
водить рассуждения и выполнять запросы
с использованием семантических описаний
на этапах разработки, развертывания или
выполнения программы. Выполнение рас-
суждений и запросов позволяют автомати-
зировать или, по крайней мере, облегчить
задачи управления разработкой програм-
мы, например, прогнозировать или наблю-
дать за взаимодействием, конфликтами
или поведением компонентов программы.
Алгеброалгоритмический метод, исполь-
зуемый в нашей работе [8], дополняет он-
тологии подробными высокоуровневыми
спецификациями программ, что обеспечи-
вает возможность синтеза программного
кода. В отличие от вышеупомянутых работ
по синтезу программ, разрабатываемые на-
ми инструментальные средства позволяют
разработчику в интерактивном режиме
осуществлять трансформации программ.
В данной работе предложен подход
к проектированию программ на основе он-
тологий и алгеброалгоритмического аппа-
рата. С помощью онтологии предметной
области описывается каркас разрабаты-
ваемого алгоритма – обрабатываемые дан-
ные; названия функций, их входные и вы-
ходные параметры, а также взаимосвязи
между функциями. В качестве средств раз-
работки онтологии были выбраны язык
OWL и система Protégé [9, 10]. Алгеброал-
горитмическую часть рассматриваемого
подхода составляет разработанный в ИПС
НАН Украины интегрированный инстру-
ментарий Проектирования и Синтеза про-
грамм (“ИПС”) [8]. Данный инструмента-
рий предназначен для проектирования ал-
горитмов в виде схем с использованием
систем алгоритмических алгебр Глушкова
(САА) [11, 12]. По схемам алгоритмов вы-
полняется генерация программного кода
на выбранном целевом языке программи-
рования (C++, Java). В данной работе раз-
работанная в Protégé онтология предмет-
ной области передается в инструментарий
“ИПС”, в котором осуществляется генера-
ция соответствующей каркасной схемы ал-
горитма для выполнения следующего эта-
па проектирования – наполнения функций
их алгоритмическим содержанием (дета-
лизации алгоритмов функций) и генерации
программы на языке программирования.
Подход проиллюстрирован на примере
разработки параллельной MPI-программы
сортировки.
Материал работы состоит из таких
разделов. В разделе 1 рассматривается
Інструментальні засоби і середовища програмування
95
применение аппарата онтологий для про-
ектирования алгоритмов на примере зада-
чи сортировки. Раздел 2 посвящен разра-
ботанному интегрированному инструмен-
тарию и его использованию для дальней-
шей разработки программ, описанных он-
тологиями, с применением средств алгебр
алгоритмов.
1. Проектирование программ с
использованием онтологий
Онтология представляет собой
формальное описание концепций (назы-
ваемых также классами) рассматриваемой
предметной области, свойств (слотов) ка-
ждой концепции, описывающих разнооб-
разные атрибуты концепции, а также огра-
ничений на свойства [13]. Она также мо-
жет содержать экземпляры – конкретные
объекты рассматриваемой предметной об-
ласти. Свойства представляют собой би-
нарные отношения между концепциями.
Различают так называемые объектные
свойства – отношения между “концепцией
и концепцией”, и свойства типов данных –
отношения между “концепцией и значени-
ем типа данных”. Онтология вместе с
множеством экземпляров классов состав-
ляют базу знаний. В данной работе экзем-
пляры использованы для представления
конкретных данных, обрабатываемых в
программе, а также структуры программы.
Различают онтологии предметных
областей и онтологии задач [5]. Онтологии
предметных областей представляют необ-
ходимые объекты, свойства и отношения
между объектами в определенной пред-
метной области (например, биоинформа-
тике, географии или медицине). Онтологии
задач содержат концепции задач и процес-
сов, их взаимосвязи и свойства. Например,
такие онтологии могут содержать сово-
купность описаний этапов химического
процесса, протокол зависимостей между
методами оптимизации и т.п.
В работах, посвященных использо-
ванию онтологий для спецификации, гене-
рации и синтеза программ [1, 2, 14], выде-
ляют два источника концепций, описы-
вающих объекты разрабатываемых про-
грамм – прикладную область (application
space) и область решений (solution space).
Прикладная область содержит все концеп-
ции, необходимые для описания приклад-
ных задач в выбранной предметной облас-
ти: типы данных, операции, преобразовы-
вающие данные и предикаты. Упомянутые
концепции задаются экспертами предмет-
ной области. Для концепций устанавлива-
ются связи с соответствующими представ-
лениями в языке спецификации, конструк-
циями в промежуточном языке програм-
мирования и конструкциями на целевом
языке программирования. Концепции из
прикладной области используются для со-
ставления спецификации решаемой зада-
чи. Область решений содержит все кон-
цепции, необходимые для формулирова-
ния программ, которые генерируются, –
элементы промежуточного языка или язы-
ков; элементы целевого языка и среды
программирования; алгоритмы и их со-
ставные части [2].
В данной работе аппарат онтологий
был применен для описания алгоритмов из
области сортировки массивов. В качестве
средств разработки онтологии был выбран
язык Web Ontology Language (OWL) и сис-
тема Protégé 3.2.1 [9, 10].
На рис. 1 показана иерархия клас-
сов разработанной онтологии. Подклассы
класса Data представляют различные
структуры данных, используемые в про-
граммах сортировки. Класс ArrayTo-
Process описывает сортируемый массив;
Pointer – указатель, перемещающийся в
процессе обработки по массиву, и отме-
чающий текущие обрабатываемые элемен-
ты сортируемого массива; Pointer-
Array – массив указателей (обращение к
конкретному указателю осуществляется по
его индексу в массиве). Подклассы класса
File отображают разновидности файлов,
которые могут использоваться в програм-
мах (входной, выходной и файл для реги-
страции времени выполнения программы).
Класс Variable предназначен для описа-
ния переменных, которые не относятся ни
к одной из вышеперечисленных категорий.
Parameter – формальные параметры со-
ставных операторов (функций), исполь-
зуемых в программе. Все подклассы класса
Data имеют свойство HasName – иденти-
фикатор переменной и свойство
IsOfType , связывающее экземпляр пере-
менной с определенным типом данных,
Інструментальні засоби і середовища програмування
96
представляющим собой экземпляр класса
DataType . Кроме того, класс Array и его
подклассы имеют дополнительное свойст-
во InitialSize , а класс Variable –
свойство InitialValue .
� Класс Operation представ-
ляет операции, применяемые к данным в
программе – операторы и предикаты. Опе-
рации могут быть базисными или состав-
ными. Базисный предикат или оператор –
первичная атомарная абстракция, исполь-
зуемая для построения схем алгоритмов.
Составные операторы и предикаты строят-
ся из элементарных посредством операций
последовательного и параллельного вы-
полнения операторов [12] (см. также раз-
дел 2). Понятие составного элемента соот-
ветствует понятию функции или метода в
программировании. Каждый базисный
элемент соответствует определенному ба-
зисному элементу в базе данных интегри-
рованного инструментария [8]. Все опера-
ции имеют такие свойства: HasName –
идентификатор операции; HasParameter
– свойство, связывающее операцию с эк-
земплярами класса Parameter ; Opera-
tionOutput – тип возвращаемого значе-
ния. Кроме того, базисные операции име-
ют дополнительное свойство HasSAAText
– запись операции на языке САА, соответ-
ствующая тексту этой операции в базе дан-
ных “ИПС”. Составные операции также
имеют дополнительное свойство
UsesOperation , в котором указываются
составные или базисные операторы, вызы-
ваемые в функции.
Класс PROGRAM предназначен для
спецификации экземпляров программ, ко-
торые используют данные, определенные
подклассами класса Data , и операции – эк-
земпляры класса Operation . Предполага-
ется, что онтология может содержать не-
сколько экземпляров класса PROGRAM.
Подкласс CurrentProgram класса
PROGRAM используется для того, чтобы
указать текущую программу, по которой в
интегрированном инструментарии необхо-
димо сгенерировать каркасную схему (см.
раздел 2). Класс ProgramGeneralDesc-
ription предназначен для задания допол-
нительных характеристик программы –
типа программы (обычная или MPI-
программа) и целевого языка программи-
рования. Свойства, ассоциированные с
классом PROGRAM рассматриваются далее в
примере 1.
Рис. 1. Онтология, описывающая концепции для решения задач сортировки
Інструментальні засоби і середовища програмування
97
Пример 1. На рис. 2 показан при-
мер созданного в Protégé экземпляра MPI-
программы адресной сортировки [8]. Поля
приведенной формы содержат значения
свойств программы. Свойство HasName
содержит название программы (алгорит-
ма). В свойстве UsesData указана сово-
купность переменных, которые использу-
ются в программе. Поле Includes-
CompoundOperation содержит названия
составных операторов алгоритма. В поле
ProgramCalls указываются составные
или базисные операторы, которые вызы-
ваются в основной функции (main ). Свой-
ство “rdfs:comment ” содержит коммен-
тарий к программе. В полях
ProgramLanguage и ProgramType указа-
ны целевой язык (C++) и тип програм-
мы (MPI) соответственно.
���� Рассмотрим основные данные и
составные операторы, используемые в ал-
горитме адресной сортировки. Алгоритм
вычисляет для каждого элемента входного
массива in_array его индекс (адрес) в
выходном (отсортированном) массиве
out_array . Входной массив считывается
из файла infile , а отсортированный за-
писывается в файл outfile . Функция
main выполняет сортировку входного мас-
сива, запуская для этого proc_num парал-
лельных процессов, каждый из которых
вызывает функцию sorting . В свою оче-
редь, sorting вызывает такие функции:
• initialize – функция, выпол-
няющая чтение входного массива из файла
и резервирование памяти для массивов,
используемых в алгоритме;
• calc_elem_pos – вычисляет вы-
ходные индексы элементов массива
in_array и сохраняет их в массиве
indexbuf ;
• confluence – осуществляет
вставку элементов массива in_array в
массив out_array , в соответствии с полу-
ченными выходными индексами.
Более подробно реализация данного
алгоритма рассматривается в разделе 2
(см. пример 2).
В табл. 1 приведено описание со-
ставного оператора sorting , используе-
мого в программе adr_sort . Данное опи-
сание было введено в Protégé с помощью
формы, аналогичной рис. 2. Столбцы таб-
лицы помечены названиями свойств со-
ставного оператора, назначение которых
рассматривалось выше. Отметим, что в
свойстве UsesOperation идентификато-
ры экземпляров базисных операторов за-
писаны с большой буквы (например,
Shift_pointer_to_the_right ), а со-
ставных – с малой. Аналогичным образом
описываются и другие составные операто-
ры рассматриваемого алгоритма.
Рис. 2. Экземпляр MPI-программы адресной сортировки, созданный в Protégé
Інструментальні засоби і середовища програмування
98
���� 2. Генерация кода алгоритма на
основе его онтологического
описания
Онтологическое описание програм-
мы, рассмотренное в предыдущем разделе,
далее используется для автоматической
генерации соответствующей каркасной
схемы алгоритма. Генерация осуществля-
ется с помощью разработанного интегри-
рованного инструментария [8], предназна-
ченного для диалогового конструирования
схем алгоритмов в САА и синтеза соответ-
ствующих программ на целевом языке
программирования. Каркасная схема затем
используется для более детального проек-
тирования алгоритма в “ИПС”. Конструи-
рование алгоритма в “ИПС” осуществля-
ется путем суперпозиции языковых конст-
рукций САА (операций САА, базисных
операторов и предикатов), которые поль-
зователь выбирает из списка. При этом на
каждом шаге проектирования “ИПС” пре-
доставляет пользователю только те конст-
рукции, вставка которых в дерево алго-
ритма не нарушает синтаксическую пра-
вильность схемы. По сконструированному
таким образом алгоритму “ИПС” выпол-
няет генерацию программы на целевом
языке программирования. Описание САА
операций и базисных элементов, а также
их отображение в язык программирования
хранится в базе данных “ИПС”.
К основным операциям САА отно-
сятся [12]:
• “op1” THEN “op2” (или “op1”
* “op2” ) – последовательное выполнение
операторов “op1” и “op2” ;
• IF ‘condition’ THEN “op1”
ELSE “op2” END IF – условное выпол-
нение операторов;
• WHILE NOT ‘condition’
CYCLE “op1” END OF CYCLE – цикл.
Текст базисных операторов в САА-
схемах заключается в двойные кавычки,
базисных предикатов – в одинарные.
БД “ИПС” содержит также допол-
нительные операции, предназначенные для
проектирования параллельных MPI-
программ [16]:
• PARALLEL_MPI(i = 0,..., m–
1) ( “op1” ) – операция, которая ини-
циализирует MPI вычисления и запускает
m процессов, каждый из которых выполня-
ет оператор “op1” , и завершает MPI вы-
числения после выполнения этого опера-
тора. Реализация этой операции на
языке программирования содержит вызо-
вы стандартных процедур MPI_Init и
MPI_Finalize [15];
• “Collect data (var1) of
type (data_type) with length (n)
from all processes to variable
(var2) of process with rank
(root_proc)” – базисный оператор, со-
ответствующий функции MPI_Gather
[15];
• базисные операторы, соответст-
вующие MPI функциям MPI_Send и
MPI_Receive [15, 16].
Для генерации каркасной САА схе-
мы по онтологии предметной области на
вход “ИПС” передается OWL файл онто-
логии, построенной в Protégé. В “ИПС”
осуществляется синтаксический анализ
данного файла, в процессе которого извле-
кается информация о таких элементах:
Таблица 1. Значения свойств составного оператора sorting
HasName OperationOutput HasParameter UsesOperation
sorting void – • initialize;
• Shift_pointer_to_the_right;
• calc_elem_pos;
• confluence;
• Output_array_to_file;
• Output_information_about_
time_expired.
Інструментальні засоби і середовища програмування
99
• классах онтологии и их подклас-
сах (иерархия классов) вместе с коммента-
риями (свойства “rdfs:comment ”);
• экземплярах классов, включая
значения ассоциированных с ними
свойств.
При построении онтологии в
Protégé для установления связи между эле-
ментами онтологии и соответствующими
элементами схемы алгоритма было ис-
пользовано свойство “rdfs:comment ”
(комментарий к классу). Так, для класса
Array строки комментария имеют вид
SAABinding
SAAType=“BasicOperator”
SAAText=“Declare an array
({HasName}) of type ({IsOfType})”
SAADBCode=“25”
Здесь SAABinding – ключевое сло-
во, указывающее на то, что комментарий
содержит информацию о привязке элемен-
та онтологии к элементу САА-схемы;
SAAType – тип элемента; SAAText – текст
элемента схемы, который необходимо сге-
нерировать; в фигурных скобках указаны
имена свойств, значения которых нужно
подставить в текст; SAADBCode – код ба-
зисного элемента в БД “ИПС”. В данном
случае приведенный комментарий означа-
ет, что для экземпляра класса Array необ-
ходимо сгенерировать базисный оператор
определения массива. Например, при зна-
чениях свойств HasName = “in_array” и
IsOfType = “int” , будет сгенерирован
такой базисный оператор:
“Declare an array (in_array)
of type (int)” ,
где в скобках указаны параметры базисно-
го элемента – идентификатор массива и
его тип.
Генерация каркасной САА-схемы
осуществляется по экземпляру класса
CurrentProgram (см. раздел 1). Основой
для генерации является файл с заранее
подготовленной шаблонной САА-схемой,
содержащей пустой блок описания гло-
бальных переменных и определение ос-
новного составного оператора (main ) схе-
мы без реализации. В случае, если в свой-
стве ProgramType указано значение
“MPI_program ”, то используется шаблон,
который дополнительно содержит опера-
цию инициализации MPI вычислений. В
упомянутый шаблон вставляются извле-
ченные из онтологии элементы. Вначале
обрабатываются значения свойства
UsesData – используемые в программе
экземпляры данных. Для каждого экземп-
ляра генерируется соответствующий ба-
зисный элемент определения данных, ко-
торый включается в блок описания гло-
бальных переменных схемы алгоритма. В
случае MPI-программы дополнительно ге-
нерируются определения переменных
myrank (номер текущего процесса) и
proc_num (количество процессов). Затем
обрабатывается свойство Includes-
CompoundOperation . Названия, парамет-
ры и начальная алгоритмическая реализа-
ция составных операций, перечисленных в
этом свойстве, вставляются в схему. Под
начальной алгоритмической реализацией
понимается последовательность вызовов
базисных и составных операторов, пере-
численных в свойстве UsesOperation со-
ставного элемента (см. раздел 1, табл. 1). В
конце генерации в составной оператор
main вставляются вызовы, перечисленные
в свойстве ProgamCalls .
Пример 2. Далее приведена кар-
касная схема, сгенерированная в “ИПС” по
онтологическому описанию программы,
приведенному в примере 1 раздела 1. Для
краткости, детализация составного опера-
тора calc_elem_pos не приводится.
SCHEME ADR_SORT ====
“Parallel MPI address sort.”
END OF COMMENTS
“GlobalData” =
==== “Declare a file variable
(regfile), file name
(sortreg.txt)”;
“Declare an array
(index_array) of type (int)”;
“Declare a file variable
(infile), file name
(sort_in.txt)”;
“Declare a variable (ar-
ray_size) of type (int)”;
Інструментальні засоби і середовища програмування
100
“Declare an array (indexbuf)
of type (int)”;
“Declare an array (in_array)
of type (int)”;
“Declare a file variable
(outfile), file name
(sort_out.txt)”;
“Declare an array
(out_array) of type (int)”;
“Declare a variable
(subarray_size) of type (int)”;
“Declare an array (pointer)
of type (int)”;
“Declare an array (myrank)
of type (int)”;
“Declare an array (proc_num)
of type (int)”
“initialize” =
==== “Read array (A) of type (T)
and size (N) from file (F)”
* “Allocate memory for array
(A) of type (T) and size (size)”
“sorting” =
==== “initialize”
* “Shift pointer P(k) on (n)
positions in (A) to the right”
* “calc_elem_pos(k)”
* “confluence”
* “Output array (m) of length
(n) to file (name)”
* “Output the time expired
from the start of processing and
write it to file (name)”
“confluence” =
==== “Collect data (var1) of type
(data_type) with length (n) from
all processes to variable (var2)
of process (proc_rank)”
* "Assign element (i) the val-
ue of element (j)"
“main” =
==== PARALLEL_MPI(i = 0,...,
proc_num–1)
(
“sorting”
)
END OF SCHEME ADR_SORT
В приведенной схеме начало реали-
зации составных операторов отмечено
символами “=”. Каждый составной опера-
тор содержит последовательность вызовов
операторов в соответствии с его онтологи-
ческим описанием (например, схема опе-
ратора sorting соответствует значениям
свойств, представленным в табл. 1). Далее
в ДСП-конструкторе необходимо продол-
жить проектирование алгоритма на основе
сгенерированной каркасной схемы. В дан-
ном случае необходимо установить пара-
метры базисных элементов и сконструиро-
вать алгоритмы функционирования со-
ставных операторов, используя присутст-
вующие в схеме вызовы операций, а также
выбирая другие операции из списка в
ДСП-конструкторе. Полная детализация
составных операторов initialize ,
sorting и confluence будет иметь такой
вид (функция main остается без измене-
ний):
“initialize” =
==== "Read array (in_array) of
type (int) and size (array_size)
from file (infile)"
* "(subarray_size) := (ar-
ray_size / proc_num)"
* "Allocate memory for array
(out_array) of type (int) and
size (array_size)"
* "Allocate memory for array
(indexbuf) of type (int) and size
(subarray_size)"
* IF 'Number of process = (0)'
THEN
"Allocate memory for ar-
ray (index_array) of type (int)
and size (proc_num *
subarray_size)"
END IF
“sorting” =
==== LocalData
(
“Declare a variable
(first_elem) of type (int)”;
“Declare a variable
(last_elem) of type (int)”
)
“initialize”
* (first_elem := myrank * su-
barray_size)
* IF ‘Rank of process =
(proc_num – 1)’
THEN
“(last_elem := array_size
– 1)”
Інструментальні засоби і середовища програмування
101
ELSE “(last_elem := (myrank
+ 1) * subarray_size – 1)”
END IF
* “Place pointer P(1) at posi-
tion (first_elem)”
* WHILE NOT ‘Pointer P(1)
reached position (last_elem + 1)
in array (in_array)’
CYCLE
“calc_elem_pos(P(1))”
* “Shift pointer P(1) on
(1) positions in array (in_array)
to the right”
END OF CYCLE
* “confluence”
* IF ‘Rank of process = (0)’
THEN
“Output array
(out_array) of length
(array_size) to file (outfile)”
* “Output the time expired
from the start of processing and
write it to file (regfile)”
END IF
“confluence” =
==== IF ‘Quantity of processes >
(1)’
THEN
“Collect data (indexbuf)
of type (MPI_INT) with length
(subarray_size) from all
processes to variable
(index_array) of process (0)”
* IF ‘Rank of process =
(0)’
THEN
FOR ‘(P(2)) from
(subarray_size) to
(array_size-1)’
* CYCLE
“Assign element
(out_array[index_array[P(2)]])
the value of element
(in_array[P(2)])”
END OF CYCLE
END IF
END IF
Выполнение вышеприведенного ал-
горитма ADR_SORT начинается с функции
main , которая запускает proc_num парал-
лельных процессов. Реализация кода каж-
дого процесса находится в функции
sorting . Оператор sorting вначале вы-
зывает функцию initialize , которая
считывает входной массив (in_array ) из
файла и резервирует память для массивов,
используемых в алгоритме. Затем массив
in_array разделяется на proc_num под-
массивов, каждый из которых обрабатыва-
ется отдельным процессом. Процесс для
каждого элемента подмассива, обозревае-
мого указателем P(1) , вычисляет его ин-
декс в отсортированном массиве с помо-
щью вызова функции calc_elem_pos
(P(1)) . Выходные индексы элементов со-
храняются в буферном массиве индексов
indexbuf . Далее выполняется функция
слияния результатов (confluence ), в ко-
торой процессы с номерами
1, ..., proc_num –1 передают массив
indexbuf в результирующий массив ин-
дексов index_array процесса 0. При этом
массивы indexbuf размещаются в масси-
ве index_array путем их конкатенации в
порядке номеров процессов (с помощью
стандартной функции MPI_Gather [15]).
После этого процесс 0 осуществляет встав-
ку элементов массива in_array в выход-
ной массив out_array в соответствии с
полученными индексами из массива
index_array . По схеме adr_sort в
“ИПС” была сгенерирована MPI-
программа на языке C.
В процессе конструирования схемы
алгоритма для выполнения ее автоматизи-
рованных преобразований совместно с
“ИПС” применяется система переписы-
вающих правил TermWare [17]. Трансфор-
мация основывается на применении к ал-
горитму, представленному в виде терма,
систем правил вида
f(x1, ..., xn) → g(x1, ..., xn),
где f и g – термы; xi – переменные термов.
В качестве примера выполним
трансформацию терма алгоритма
Root (
main (
serial_exec (
OutputArray(out_arr),
OutputTime
)
)
)
Інструментальні засоби і середовища програмування
102
Приведенный терм состоит из
функции main , выполняющей два опера-
тора, первый из которых выводит массив
out_arr , а второй выводит время выпол-
нения. (Аналогичная пара операторов при-
сутствует в функции sorting вышерас-
смотренного алгоритма ADR_SORT). Пусть
упомянутые операторы должны быть
включены в блок условного оператора та-
ким образом, чтобы они выполнялись
только процессом с нулевым номером. Для
этого необходимо к терму алгоритма при-
менить такое правило:
main (serial_exec($x1, $x2)) →
main (if (ZeroRankProcess,
serial_exec($x1, $x2)))
Результирующий терм будет иметь
вид
Root (
main (
if (ZeroRankProcess,
serial_exec (
OutputArray(out_arr),
OutputTime)
)
)
)
Заключение
В работе предложен подход к про-
ектированию параллельных программ на
основе использования онтологий и аппара-
та алгебры алгоритмов. Онтологии позво-
ляют описать основные объекты разраба-
тываемой программы из выбранной пред-
метной области – данные и обрабатываю-
щие их функции, а также взаимосвязи ме-
жду функциями. Разработан метод генера-
ции каркасной схемы алгоритма по онто-
логии предметной области. Метод реали-
зован в интегрированном инструментарии
проектирования и генерации программ. В
инструментарии осуществляется дальней-
шее наполнение сгенерированной каркас-
ной схемы с использованием операций
САА, а также трансформация алгоритма.
По схеме алгоритма затем осуществляется
генерация программы на выбранном языке
программирования.
К перспективам дальнейшего раз-
вития интегрированного инструментария
относится их настройка на разработку сер-
висно-ориентированных Grid программ.
1. Nistor E.C. Using Domain Models in Exten-
sible Schema-based Software Synthesis. –
NASA Ames Research Center, Technical Re-
port, 2004. – http://www.ics.uci.edu/
~enistor/research/nistor-report.pdf
2. Bureš T., Denney E., Fischer B., Nistor E.C.
The Role of Ontologies in Schema-based Pro-
gram Synthesis // In Workshop on Ontologies
as Software Engineering Artifacts, Vancou-
ver, Canada, 2004. – http://ti.arc.nasa.
gov/people/edenney/papers/ontologies.pdf
3. Waldinger R., Jarvis P., Dungan J. Program
Synthesis for Multi-Agent Question Answer-
ing // In International Symposium on Verifi-
cation (Theory and Practice). – Springer Ver-
lag, Lecture Notes in Computer Science. –
2003. – P. 747–761.
4. Fensel D., Lausen H., Polleres A., de Bruijn J.
et al. Enabling Semantic Web Services. The
Web Service Modeling Ontology. – Springer
Verlag, 2007. – 188 p.
5. de Roure D., Jennings N., Shadbolt N. Re-
search Agenda for the Semantic Grid: A Fu-
ture e-Science Infrastructure – Technical re-
port UKeS-2002-02, UK e-Science Technical
Report Series, National e-Science Centre, Ed-
inburgh, UK. – 2001. – 78 p.
6. OMG, Unified Modeling Language Specifica-
tion. – http://www.uml.org
7. Chen P.P. Entity-Relationship Modelling:
Historical Events, Future Trends, and Lessons
Learned. – Software pioneers: contributions to
software engineering. – Springer-Verlag, New
York. – 2002. – P. 296–310.
8. Андон Ф.И., Дорошенко А.Е., Цейтлин
Г.Е., Яценко Е.А. Алгеброалгоритмические
модели и методы параллельного програм-
мирования. – Киев: Академпериодика,
2007. – 631 с.
9. Protégé. – http://protege.stanford.edu
10. Protégé-OWL editor. – http://protege.stan
ford.edu/overview/protege-owl.html
11. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. – Ки-
ев: Наук. думка, 1989. – 376 с.
12. Цейтлин Г.Е. Алгебраическая алгоритми-
ка: теория и приложения // Кибернетика и
системный анализ. – 2003. – № 1. – С. 8–18.
13. Noy N.F., McGuinness D.L. Ontology Devel-
opment 101: A Guide to Creating Your First
Ontology. – Stanford Knowledge Systems
Laboratory Technical Report KSL-01-05 and
Stanford Medical Informatics Technical Re-
port SMI-2001-0880. – 2001. – 25 p.
14. Чарнецки К., Айзенекер У. Порождающее
программирование: методы, инструменты,
Інструментальні засоби і середовища програмування
103
применение. Для профессионалов. – СПб.:
Питер, 2005. – 731 с.
15. MPI: A Message-Passing Interface Standard.
– http://www-unix.mcs.anl.gov/mpi
16. Дорошенко А.Е., Жереб К.А., Яценко Е.А.
Средства синтеза параллельных MPI- про-
грамм // Проблемы программирования. –
2008. – № 2–3. – С. 595–604.
17. Дорошенко А.Е., Шевченко Р.С. Система
символьных вычислений для программи-
рования динамических приложений // Про-
блемы программирования. – 2005. – № 4. –
С. 718–727.
Получено 01.10.2008
Об авторах:
Дорошенко Анатолий Ефимович,
доктор физико-математических наук,
профессор, заведующий отделом теории
компьютерных вычислений,
Яценко Елена Анатольевна,
кандидат физико-математических наук,
старший научный сотрудник.
Место работы авторов:
Институт программных систем
НАН Украины.
Тел.: (044) 526 1538,
e-mail: dor@isofts.kiev.ua,
aiyat@i.com.ua aiyat@i.com.ua
|
| id | pp_isofts_kiev_ua-article-1019 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2026-06-23T01:00:39Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/f0/8857bb0265c9472c8ae7f386333491f0.pdf |
| spelling | pp_isofts_kiev_ua-article-10192026-06-22T16:37:55Z Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms Средства автоматизации разработки параллельных программ на основе онтологий и алгебр алгоритмов Засоби автоматизації розробки паралельних програм на основі онтологій та алгебр алгоритмів Doroshenko, A.Yu. Yatsenko, E.A. UDC 681.3 УДК 681.3 УДК 681.3 An approach to formalized development of parallel programs using ontologies and algebra-algorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain – data, functions and relations between functions. Once the skeleton of the program has been built, further development can be done in automated manner with the Integrated toolkit for Design and Synthesis developed by the authors, which is based on using algorithmic algebras facilities. The application of the approach is illustrated with an example of developing parallel MPI program in the subject domain of sorting algorithms.Problems in programming 2008; 4: 94-103 Предложен подход к формализованной разработке параллельных программ на основе использования онтологий и аппарата алгебры алгоритмов. С помощью онтологии описываются основные объекты разрабатываемой программы из выбранной предметной области – данные, функции и взаимосвязи между функциями. Дальнейшее проектирование приложения осуществляется в разработанном интегрированном инструментарии проектирования и генерации программ, основывающемся на системах алгоритмических алгебр. Подход проиллюстрирован на примере разработки параллельной MPI-программы сортировки.Problems in programming 2008; 4: 94-103 Запропоновано підхід до формалізованої розробки паралельних програм на основі використання онтологій та апарату алгебри алгоритмів. За допомогою онтології описуються основні об’єкти розроблюваної програми з обраної предметної області – дані, функції та взаємозв’язки між функціями. Подальше проектування програми виконується в розробленому інтегрованому інструментарії проектування і генерації програм, який ґрунтується на системах алгоритмічних алгебр. Підхід проілюстрований на прикладі розробки паралельної MPI програми сортування.Problems in programming 2008; 4: 94-103 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-22 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1019 PROBLEMS IN PROGRAMMING; No 4 (2008); 94-103 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2008); 94-103 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2008); 94-103 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1019/1087 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 681.3 Doroshenko, A.Yu. Yatsenko, E.A. Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title | Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title_alt | Средства автоматизации разработки параллельных программ на основе онтологий и алгебр алгоритмов Засоби автоматизації розробки паралельних програм на основі онтологій та алгебр алгоритмів |
| title_full | Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title_fullStr | Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title_full_unstemmed | Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title_short | Facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| title_sort | facilities for automation of development of parallel programs on the basis of ontologies and algebra of algorithms |
| topic | UDC 681.3 |
| topic_facet | UDC 681.3 УДК 681.3 УДК 681.3 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1019 |
| work_keys_str_mv | AT doroshenkoayu facilitiesforautomationofdevelopmentofparallelprogramsonthebasisofontologiesandalgebraofalgorithms AT yatsenkoea facilitiesforautomationofdevelopmentofparallelprogramsonthebasisofontologiesandalgebraofalgorithms AT doroshenkoayu sredstvaavtomatizaciirazrabotkiparallelʹnyhprogrammnaosnoveontologijialgebralgoritmov AT yatsenkoea sredstvaavtomatizaciirazrabotkiparallelʹnyhprogrammnaosnoveontologijialgebralgoritmov AT doroshenkoayu zasobiavtomatizacíírozrobkiparalelʹnihprogramnaosnovíontologíjtaalgebralgoritmív AT yatsenkoea zasobiavtomatizacíírozrobkiparalelʹnihprogramnaosnovíontologíjtaalgebralgoritmív |