Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data
The development of the algebra-algorithmic toolkit for designing and synthesis of programs for constructing of specifications of algorithms, which combine common definition of data and execution processes in algebra of algorithms with data, is proposed. The application of the proposed algebraic appr...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут програмних систем НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/137 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-137 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/e4/e88857ed65084720fb9f779efe2a36e4.pdf |
| spelling |
pp_isofts_kiev_ua-article-1372018-07-18T20:34:56Z Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data Реализация средств проектирования и генерации программ на основе алгебры алгоритмов с данными Реалізація засобів проектування та генерації програм на основі алгебри алгоритмів з даними Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. UDC 681.3 УДК 681.3 УДК 681.3 The development of the algebra-algorithmic toolkit for designing and synthesis of programs for constructing of specifications of algorithms, which combine common definition of data and execution processes in algebra of algorithms with data, is proposed. The application of the proposed algebraic approach and the toolkit is illustrated on the example of the development of sorting programs. Предложено развитие алгеброалгоритмического инструментария проектирования и синтеза программ для конструирования спецификаций алгоритмов, сочетающих совместное описание данных и потоков управления в алгебре алгоритмов с данными. Применение предложенных алгебраического подхода и инструментария проиллюстрировано на примере разработки программ сортировки. Запропоновано розвиток алгеброал-горитмічного інструментарію проектування та синтезу програм для конструювання специфікацій алгоритмів, що поєднують спільний опис даних і потоків управління в алгебрі алгоритмів з даними. Застосування запропонованих алгебраїчного підходу та інструментарію проілюстроване на прикладі розробки програм сорту-вання. Інститут програмних систем НАН України 2017-06-14 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/137 PROBLEMS IN PROGRAMMING; No 2 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2015) 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/137/130 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-18T20:34:56Z |
| collection |
OJS |
| language |
rus |
| topic |
UDC 681.3 |
| spellingShingle |
UDC 681.3 Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| topic_facet |
UDC 681.3 УДК 681.3 УДК 681.3 |
| format |
Article |
| author |
Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. |
| author_facet |
Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. |
| author_sort |
Akulovskiy, V.G. |
| title |
Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_short |
Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_full |
Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_fullStr |
Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_full_unstemmed |
Implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_sort |
implementation of tools for designing and generating of programs on the basis of algebra of algorithms with data |
| title_alt |
Реализация средств проектирования и генерации программ на основе алгебры алгоритмов с данными Реалізація засобів проектування та генерації програм на основі алгебри алгоритмів з даними |
| description |
The development of the algebra-algorithmic toolkit for designing and synthesis of programs for constructing of specifications of algorithms, which combine common definition of data and execution processes in algebra of algorithms with data, is proposed. The application of the proposed algebraic approach and the toolkit is illustrated on the example of the development of sorting programs. |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2017 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/137 |
| work_keys_str_mv |
AT akulovskiyvg implementationoftoolsfordesigningandgeneratingofprogramsonthebasisofalgebraofalgorithmswithdata AT doroshenkoayu implementationoftoolsfordesigningandgeneratingofprogramsonthebasisofalgebraofalgorithmswithdata AT yatsenkooa implementationoftoolsfordesigningandgeneratingofprogramsonthebasisofalgebraofalgorithmswithdata AT akulovskiyvg realizaciâsredstvproektirovaniâigeneraciiprogrammnaosnovealgebryalgoritmovsdannymi AT doroshenkoayu realizaciâsredstvproektirovaniâigeneraciiprogrammnaosnovealgebryalgoritmovsdannymi AT yatsenkooa realizaciâsredstvproektirovaniâigeneraciiprogrammnaosnovealgebryalgoritmovsdannymi AT akulovskiyvg realízacíâzasobívproektuvannâtageneracííprogramnaosnovíalgebrialgoritmívzdanimi AT doroshenkoayu realízacíâzasobívproektuvannâtageneracííprogramnaosnovíalgebrialgoritmívzdanimi AT yatsenkooa realízacíâzasobívproektuvannâtageneracííprogramnaosnovíalgebrialgoritmívzdanimi |
| first_indexed |
2025-07-17T09:43:44Z |
| last_indexed |
2025-07-17T09:43:44Z |
| _version_ |
1838409231203565568 |
| fulltext |
Інструментальні засоби та середовища програмування
© В.Г. Акуловский, А.Е. Дорошенко, Е.А. Яценко, 2015
ISSN 1727-4907. Проблеми програмування. 2015. № 2 41
УДК 681.3
В.Г. Акуловский, А.Е. Дорошенко, Е.А. Яценко
РЕАЛИЗАЦИЯ СРЕДСТВ ПРОЕКТИРОВАНИЯ
И ГЕНЕРАЦИИ ПРОГРАММ НА ОСНОВЕ
АЛГЕБРЫ АЛГОРИТМОВ С ДАННЫМИ
Предложено развитие алгеброалгоритмического инструментария проектирования и синтеза программ
для конструирования спецификаций алгоритмов, сочетающих совместное описание данных и потоков
управления в алгебре алгоритмов с данными. Применение предложенных алгебраического подхода и
инструментария проиллюстрировано на примере разработки программ сортировки.
Введение
Актуальной проблемой современ-
ного программирования является его фор-
мализация, разработка высокоуровневых
языков проектирования алгоритмов и про-
грамм на основе алгебраических средств.
В Институте программных систем НАН
Украины на протяжении длительного пе-
риода развивается теория, методология и
инструментарий для формализованного
проектирования параллельных программ,
основывающиеся на средствах алгебры ал-
горитмики [1]. Алгебра алгоритмики пред-
ставляет собой современное направление
компьютерной науки, восходящее к фун-
даментальным работам академика
В.М. Глушкова по теории систем алгорит-
мических алгебр (САА). Объектом иссле-
дования в ней являются высокоуровневые
модели алгоритмов, представленные в ви-
де схем. В предыдущих работах авторов
[2–4] были предложены формальные сред-
ства для разработки эффективных про-
грамм в модифицированных САА (САА-
М), ориентированных на формализацию
последовательных и параллельных вычис-
лений. На основе разработанной теории и
методологии создан интегрированный ин-
струментарий проектирования и синтеза
программ (ИПС).
Учитывая принципиальную важ-
ность роли данных в процессе разработки
алгоритмов и программ, в работах [5, 6]
результате модификации модели ЭВМ
Глушкова, предложена система алгорит-
мических алгебр с данными (САА\Д). Мо-
дификация заключается в дополнении мо-
дели внешней средой (ВС), представляю-
щей собой с одной стороны память и
внешние устройства, а с другой – множе-
ство данных ВСD . Сигнатура САА\Д вклю-
чает все операции алгебры Глушкова.
Принципиальное отличие предложенного
формального аппарата от алгебры алго-
ритмов Глушкова состоит в использовании
операторов вида )()( DOD , на входе и вы-
ходе которых специфицированы обраба-
тываемые данные и которые, учитывая это,
получили название Д-операторы. Данное
отличие обеспечило возможность описа-
ния управляющих структур и структур об-
рабатываемых данных в процессе проек-
тирования алгоритмов.
Цель данной работы состоит в
настройке инструментальной системы
ИПС на проектирование и синтез про-
грамм на основе схем, представленных в
алгебре алгоритмов с данными. Примене-
ние алгебраического аппарата и инстру-
ментария проиллюстрировано на примере
разработки последовательного и парал-
лельного алгоритмов сортировки.
Предлагаемый подход близок к ра-
ботам, относящимся к алгебраическому
программированию [7] и синтезу про-
грамм на основе спецификаций [8, 9]. От-
личие нашего подхода состоит в исполь-
зовании вышеупомянутых Д-операторов,
а также спецификаций алгоритмов, пред-
ставленных не только в алгебраической,
но и естественно-лингвистической форме,
облегчающей понимание алгоритмов и
достижение необходимого качества про-
грамм. Другим преимуществом разрабо-
танных инструментальных средств явля-
Інструментальні засоби та середовища програмування
42
ется применение метода диалогового кон-
струирования синтаксически правильных
программ, исключающего возможность
возникновения синтаксических ошибок в
процессе проектирования схем.
1. Операции алгебры
алгоритмов с данными
Алгебра алгоритмов с данными
представляет собой трехосновную алгеб-
раическую систему
САА\Д ::= ,};,,{ DLU
где U – множество Д-операторов, L –
множество логических условий, D – мно-
жество данных, – базовый набор опера-
ций алгебры, включающий операции 1 ,
определенные на множествах U , 2 , L ,
3 и D.
Д-операторы – это операторы вида
)()( DOD со специфицированными на
входе и выходе данными такими, что
ВСDD и
ВСDD . Д-оператор обрабаты-
вает данные, т. е. анализирует и преобра-
зует, изменяя их значения.
Предикат )()( αPD является одним
из типов Д-операторов. Он осуществляет
проверку заданного отношения D и про-
дуцирует логическое условие 1} {0,α , ко-
торое принимает истинное значение в слу-
чае, когда отношение D выполняется, и
ложное в противном случае.
Представление любого Д-оператора
посредством операций САА\Д и других
Д-операторов называется регулярной схе-
мой (РС) данного Д-оператора. Любой ал-
горитм может быть представлен в виде
Д-оператора.
Рассмотрим операции САА/Д,
определенные на множестве Д-операторов,
и используемые в данной работе.
Композиция Д-операторов
)()()()( 222111 DODDOD (1)
означает последовательное выполнение
вначале Д-оператора )()( 111 DOD , а затем
Д-оператора )()( 222 DOD .
Операция 2p -дизъюнкции
))()()()(( )]()[( 222111 DODDODαPD
,0 если ,)()(
1; если ),()(
222
111
αDOD
αDOD
состоит в выполнении Д-оператора
)()( 111 DOD в случае истинности условия
α , или оператора )()( 222 DOD в против-
ном случае. Здесь )()( αPD – предикат,
продуцирующий логическое условие α .
Операция последовательной филь-
трации (р-фильтр) является производной
от 2p -дизъюнкции и записывается в виде:
)).()(( )]()[( DODαPD (2)
Данная операция состоит в выпол-
нении Д-оператора )()( DOD в случае ис-
тинности условия α .
Операция f-итерации
} )()( {
)]()();()();()[(
DOD
DODPDDOD p
s
ppp
u
p
(3)
аналогична оператору for, который имеет
место в большинстве языков программи-
рования, и состоит в циклическом выпол-
нении Д-оператора )()( DOD до тех пор,
пока условие 1 , и завершается в про-
тивном случае. Здесь )()( p
u
p DOD –
Д-оператор, который устанавливает ис-
ходные значения данных pD – парамет-
ров цикла; )()( p
s
p DOD – Д-оператор, ко-
торый изменяет их, как правило, с задан-
ным шагом; )()( PDp – предикат, кото-
рый анализирует эти параметры, проверяя
условие выполнения цикла; )()( DOD –
тело цикла.
Пример 1. Частным случаем ис-
пользования операции f-итерации может
служить следующая РС:
)( : ),(;);( : [(0) istepinii
}, )()( { ii DOD
где )( : (0) i – базисный оператор, присва-
ивающий переменной i исходное значение
Інструментальні засоби та середовища програмування
43
0; ni – условие выполнения цикла;
)( : ),( istepi – оператор, увеличивающий
значение переменной i на значение step ;
)()( ii DOD – тело цикла.
Для описания параллелизма в
САА/Д используется операция асинхрон-
ной дизъюнкции Д-операторов
)()()()( 111 iiiiii DODDOD , состоящая в
их параллельном асинхронном выполне-
нии [6].
Для синхронизации параллельно
выполняемых Д-операторов в РС исполь-
зуются синхронизаторы и контрольные
точки.
Синхронизатор S)( задерживает
вычислительный процесс до тех пор, пока
условие , ложное в исходном состоянии,
не станет истинным. Установка условия
в истинное значение связана с прохожде-
нием контрольной точки, которая ассоци-
ирована с данным синхронизатором.
Контрольная точка )()( ST , где S –
ассоциированный с этой контрольной точ-
кой синхронизатор, изменяет значение ло-
гического условия соответствующего
синхронизатора, в результате чего “задер-
жанный” синхронизатором вычислитель-
ный процесс продолжает выполнение.
В работе [6] сформулированы необ-
ходимые и достаточные условия для па-
раллельного выполнения Д-операторов
)()()()( 111 iiiiii DODDOD в РС:
1) в результате параллельного вы-
полнения Д-операторов должны быть по-
лучены значения всех обрабатываемых
данных 11,,, iiii DDDD такие же, как и в
случае их последовательного выполнения
)()()()( 111 iiiiii DODDOD ;
2) параллельно выполняемые Д-опе-
раторы должны быть синхронизованы,
то есть завершение обоих этих Д-опера-
торов должно быть синхронизовано с
началом выполнения следующего за ними
Д-оператора, а операции ввода-вывода,
если они имеют место, в результате син-
хронизации должны принадлежать допу-
стимой для данного алгоритма последова-
тельности.
Учитывая приведенные условия, в
работе [6] доказана следующая теорема о
возможности параллельного выполнения
Д-операторов.
Теорема. Два Д-оператора могут
выполняться параллельно
)()()()( 111 iiiiii DODDOD ,
если они синхронизированы, и у них нет
непосредственных 1ii DD и обрат-
ных 1ii DD , 1ii DD связей, а
последовательность операций ввода-
вывода, если они имеют место, остается
допустимой.
Определим далее операцию асин-
хронной f-итерации (параллельного цик-
ла). Понятие параллельного цикла встре-
чается во многих системах параллельного
программирования (см., например, [10]),
и, как правило, состоит в следующем.
Пусть имеется цикл, витки (итерации) ко-
торого можно выполнять независимо, в
любом порядке или одновременно. Тогда в
параллельной программе можно распреде-
лить итерации такого цикла по отдельным
параллельным процессам.
Запишем операцию асинхронной
f-итерации в следующем виде:
}. )()( {
)]( : ),(;);( : )[(
ii DOD
istepiendiistart
(4)
Данная операция состоит в парал-
лельном выполнении витков f-итерации
(цикла), указанной после символа . Здесь
i – переменная цикла; start – начальное
значение переменной; endi – условие
выполнения цикла; )()( ii DOD – тело цик-
ла. Операторы )()( ii DOD должны удовле-
творять условиям для параллельного вы-
полнения операторов, рассмотренным
выше.
Пример 2. Частным случаем ис-
пользования операции асинхронной
f-итерации может служить следующая
схема алгоритма:
)]( : )1 ,(;);( : [(0) iinii
}. )()( { ii DOD
Данная схема состоит в асинхрон-
ном выполнении совокупности Д-опера-
торов
Інструментальні засоби та середовища програмування
44
).()( ... )()( )()( 111100 nn DODDODDOD
Целью данной работы является реа-
лизация средств САА\Д в инструменталь-
ной системе формализованного конструи-
рования алгоритмов и программ, которая
рассматривается в следующем разделе.
2. Инструментарий для
проектирования алгоритмов и
программ на основе САА\Д
В работах [1, 2] разработан инстру-
ментарий ИПС, обеспечивающий автома-
тизированное проектирование и синтез
программ по формализованным специфи-
кациям в САА-М. Инструментарий осно-
вывается на методе диалогового конструи-
рования синтаксически правильных про-
грамм (ДСП-методе), и использует раз-
личные формы представления алгоритмов
в процессе их проектирования – есте-
ственно-лингвистическую (САА-схемы),
алгебраическую (регулярные схемы) и
граф-схемную. В отличие от традицион-
ных синтаксических анализаторов, ДСП-
метод ориентирован не на поиск и исправ-
ление синтаксических ошибок, а на ис-
ключение возможности их появления в
процессе построения алгоритма. Основная
идея метода состоит в поуровневом кон-
струировании схем сверху вниз путем су-
перпозиции языковых конструкций алгеб-
ры алгоритмов. На каждом шаге конструи-
рования система в диалоге с пользовате-
лем предоставляет на выбор лишь те кон-
струкции, подстановка которых в форми-
руемый текст не нарушает синтаксическую
правильность схемы. На основе построен-
ной схемы алгоритма выполняется автома-
тическая генерация текста программы.
Отметим, что система ИПС может
быть настроена на требуемый входной
язык, представленный в алгебре алгорит-
мов, и выходной (целевой) язык програм-
мирования. В настоящее время система
поддерживает генерацию последователь-
ных и параллельных программ на языках
С, C++, Java, а также термов на языке си-
стемы TermWare [11]. Для генерации па-
раллельных программ были использованы
различные средства: потоки с использова-
нием функций WinAPI [2], операции MPI
(Message Passing Interface) [3], операции
языка C для CUDA [4] и др.
Архитектура инструментария пока-
зана на рис. 1. Основными компонентами
системы являются:
• диалоговый конструктор синтак-
сически правильных программ (ДСП-
конструктор), предназначенный для по-
строения схем алгоритмов и генерации
программ;
• редактор графового представле-
ния алгоритмов (граф-схем);
• генератор САА-схем по парамет-
ризованным схемам более высокого уров-
ня (гиперсхемам);
• база данных (БД), содержащая
описание операций алгебры алгоритмов,
базисных операторов и предикатов. Опи-
сание упомянутых элементов включает их
представление в алгебраической и есте-
ственно-лингвистической формах, а также
шаблон реализации на целевом языке про-
граммирования.
В основу функционирования ДСП-
Рис. 1. Архитектура системы ИПС
База данных
ДСП-конструктор
Редактор
граф-схем
Генератор
САА-схем
Інструментальні засоби та середовища програмування
45
конструктора положен диалоговый режим
с использованием списка алгоритмиче-
ских конструкций и дерева конструирова-
ния алгоритма. Выбранные пользователем
конструкции, а также операторные и ло-
гические переменные, входящие в них,
отображаются в дереве с дальнейшей де-
тализацией переменных. В зависимости
от типа выбранной переменной (опера-
торного или предикатного) система пред-
лагает соответствующий список операций
алгебры алгоритмов из базы данных. На
основе полученного в процессе конструи-
рования дерева алгоритма, инструмента-
рий ИПС выполняет синтез кода на вы-
бранном целевом языке программирова-
ния. В процессе синтеза управляющие
конструкции схемы алгоритма и базисные
операторы и предикаты отображаются в
соответствующие операторы языка про-
граммирования в соответствии с их опи-
санием (шаблоном) в БД. Составные опе-
раторы могут быть представлены как
подпрограммы (функции).
В работах [1–4] система ИПС была
применена для генерации многопоточных
и распределенных параллельных про-
грамм на основе спецификаций алгорит-
мов, представленных в САА-М. В данной
работе для ориентации инструментария на
конструирование схем алгоритмов, пред-
ставленных в САА\Д, в базу данных си-
стемы были добавлены описания опера-
ций, определения которых были рассмот-
рены в разделе 1. В табл. 1 приведены
спецификации некоторых операторных
операций САА\Д, которые были занесены
в базу данных инструментария. Алгебра-
ическая форма операций, по сравнению с
приведенной в разделе 1 (см. формулы
(1)–(4)), скорректирована с учетом тек-
стового представления спецификаций в
инструментарии. В частности, символ в
операции асинхронной f-итерации заме-
нен на символы. Строками "условие1",
“оператор1”, "переменная1" и т. п. обо-
значены различные операнды операций,
вместо которых подставляются базисные
предикаты, Д-операторы, идентификато-
ры переменных и прочее в процессе кон-
струирования схемы алгоритма. Для каж-
дой операции в таблице приведен шаблон
Таблица 1. Представление операторных операций САА\Д в алгебраической и
естественно-лингвистической форме, а также их реализации на языке C++
№ Название
операции
Алгебраическая
форма
Естественно-
лингвистическая форма
Шаблон реализации
на языке C++
1 Композиция “оператор1” *
“оператор2”
“оператор1”
ЗАТЕМ
“оператор2”
^оператор1^;
^оператор2^
2 Последова-
тельный
фильтр
['condition1']
"operator1"
ЕСЛИ ‘условие1’
ТО “оператор1”
КОНЕЦ ЕСЛИ
if (^условие1^)
{
^оператор1^
};
3 f-итерация ["оператор1";
'условие1';
"оператор2"]
{
"оператор3"
}
ДЛЯ ("оператор1";
'условие1';
"оператор2")
ЦИКЛ
"оператор3"
КОНЕЦ ЦИКЛА
for (int ^оператор1^;
^условие1^;
^оператор2^)
{
^оператор3^
}
4 Асинхронная
f-итерация
//["оператор1";
'условие1';
"оператор2"]
{
"оператор3"
}
ПАРАЛЛЕЛЬНО ДЛЯ
("оператор1"; 'условие1';
"оператор2")
"оператор3"
КОНЕЦ ПАРАЛЛЕЛЬНО
#pragma omp for
for (int ^оператор1^;
^условие1^;
^оператор2^)
{
^оператор3^
}
Інструментальні засоби та середовища програмування
46
реализации на целевом языке программи-
рования C++. Тексты реализаций содер-
жат строки ^условие1^, ^оператор1^,
^переменная1^ и т. п., вместо которых в
процессе генерации будут подставлены
тексты реализаций операндов.
В последнем столбце четвертой
строки таблицы приведен пример реализа-
ции операции асинхронной f-итерации на
языке C++ с использованием средств
OpenMP [10]. Отметим, что OpenMP пред-
ставляет собой совокупность директив
компилятора (прагм), библиотечных про-
цедур и переменных окружения, которые
предназначены для программирования
многопоточных приложений на многопро-
цессорных системах с общей памятью. В
данном случае для реализации параллель-
ного цикла используется директива omp
for, выполняющая распределение итераций
цикла for между потоками.
Применение рассмотренных опера-
ций САА\Д для проектирования программ
в системе ИПС продемонстрировано в
следующем разделе.
3. Пример использования
алгебраического аппарата и
инструментария
Проиллюстрируем применение
средств САА\Д и системы ИПС на приме-
ре распараллеливания алгоритма сорти-
ровки числовых массивов. В качестве ис-
ходного последовательного алгоритма рас-
сматривается схема алгоритма сортировки
методом пузырька.
В качестве обрабатываемых данных
будем рассматривать массив целых чисел
]M[n , где n – константа, задающая размер
массива. Доступ к элементам массива
осуществляется с помощью индексных пе-
ременных, т. е. идентификатор элемента
массива записывается в виде ]M[ j , где
M – идентификатор массива, j – индекс-
ная переменная. В частных случаях вместо
индексной переменной может использо-
ваться константа или выражение.
3.1. Последовательный алгоритм.
Регулярная схема последовательного алго-
ритма пузырьковой сортировки, построен-
ная в системе ИПС, имеет следующий вид:
])(M[ СОРТ ])(M[ nn
)]( + 1) ,( ); < ( );( := [(0) iinii
{
)]( + 1) ,( 1); - < ( );( := [(0) jjnjj
1]]+M[ > ][M[ { jj
1]))}+M[ ],(M[ П 1])+M[ ],((M[ jjjj
}
Данная схема представляет собой
две вложенные операции f-итерации (два
вложенных цикла). Кроме данных, специ-
фицированных на входе алгоритма, ис-
пользованы вспомогательные данные –
индексные переменные i и j . Исходные
значения переменных устанавливаются
Д-операторами )( := (0) i и )( := (0) j , на
входе которых специфицированы констан-
ты, определяющие эти исходные значения.
Индексные переменные изменяются с еди-
ничным шагом Д-операторами )( + 1) ,( ii и
)( + 1) ,( jj . В квадратные скобки заключе-
ны проверяемые отношения, а Д-оператор
П переставляет (меняет местами) элемен-
ты массива в случае, если в последова-
тельном фильтре логическое условие при-
нимает истинное значение.
Отметим, что по сравнению со схе-
мами алгоритмов сортировки, представ-
ленных в САА (см. например, [1]), полу-
ченная выше РС содержит больший объем
информации об алгоритме, и позволяет, в
частности, более эффективно выполнять
анализ информационных связей между
операторами в них. Это преимущество
обеспечивается за счет явного указания
поименованных исходных и результиру-
ющих данных на входе и выходе Д-
операторов.
3.2. Распараллеливание последо-
вательного алгоритма. Для преобразова-
ния последовательного алгоритма СОРТ в
параллельный выполним анализ информа-
ционных связей между Д-операторами
1])+M[ ],(M[ П 1])+M[ ],(M[ jjjj , после-
довательно выполняющимися во вложен-
ном цикле по переменной j .
Рассмотрим, например, первые две
итерации цикла, т. е. при 0j и 1j . В
Інструментальні засоби та середовища програмування
47
случае истинности условия 1]M[>]M[ jj ,
при 0j будет выполнен Д-оператор
M[1])(M[0], П M[1])],(M[0 , а при 1j –
M[2])(M[1], П M[2]) (M[1], . Таким обра-
зом, множества входных и выходных дан-
ных этих операторов пересекаются по эле-
менту массива M[1] . В соответствии с
теоремой, приведенной в разделе 1, дан-
ные операторы имеют непосредственные и
обратные связи, и не могут выполняться
параллельно.
Одним из возможных вариантов
распараллеливания последовательного ал-
горитма пузырьковой сортировки является
его преобразование в алгоритм чёт-
нечётной сортировки [12], а затем распа-
раллеливание вложенного цикла [13, 14].
Суть модификации состоит в том, чтобы в
зависимости от четности или нечётности
номера итерации i внешнего цикла обра-
батывать элементы с четными или нечёт-
ными индексами соответственно (при этом
сравнение выделяемых значений осу-
ществляется с их правыми соседними эле-
ментами).
Для преобразования алгоритма пу-
зырьковой сортировки СОРТ в последова-
тельный алгоритм чёт-нечётной сортиров-
ки выполним следующие замены (переин-
терпретацию) базисных операторов:
),( + 2) ,( )( + 1) ,(
),( % 2) , ( )( := (0)
jjjj
jij
где )( % 2) , ( ji – Д-оператор, вычисляю-
щий остаток от деления i на 2 и присваи-
вающий полученное значение перемен-
ной j .
Полученная в результате указанных
трансформаций РС имеет вид
}
1]))}+M[ ],(M[ П 1])+M[ ],((M[
1]]+M[ > ][M[ {
)]( + 2) ,( 1); - < ( );( % 2) , [( {
)]( + 1) ,( ); < ( );( := [(0)
])(M[ СОРТ2 ])(M[
jjjj
jj
jjnjji
iinii
nn
Рассмотрим вновь данные, обраба-
тываемые операторами П при 0j и
1j . В случае истинности условий филь-
тра, при 0j будет выполнен Д-оператор
M[1]) (M[0], П M[1]) ],0(M[ , а при 1j –
Д-оператор M[3]) (M[2], П M[3]) (M[2], .
Таким образом, множества входных
и выходных данных в указанных
Д-операторах не пересекаются, также как и
в операторах при других значениях j во
вложенном цикле. Операторы П являются
независимыми и могут выполняться па-
раллельно в рамках одной итерации внеш-
него цикла.
Для перехода к параллельному ал-
горитму чёт-нечётной сортировки необхо-
димо выполнить следующие трансформа-
ции схемы СОРТ2:
1) заменить вложенную f-итерацию
по переменной j на асинхронную
f-итерацию;
2) добавить контрольные точки и
синхронизаторы.
Результирующая параллельная РС
имеет вид
}
АКОНЧЕНА)(ВСЯ_ОБР_З * }
)( )( ЧЕНА)(ОБР_ЗАКОН
1]))+M[ ],(M[ П 1])+M[ ],((M[
1]]+M[ > ][M[ {
)]( + 2) ,( 1); - < ( );( := 2) % [(
{
)]( + 1) ,( ); < ( );( := [(0)
])(M[ СОРТ2_ПАР ])(M[
S
SjT
jjjj
jj
jjnjji
iinii
nn
В приведенной схеме контрольная
точка )( )( ЧЕНА)(ОБР_ЗАКОН SjT фик-
сирует момент завершения вычислений в
текущей параллельной ветви. Синхрониза-
тор S АКОНЧЕНА)(ВСЯ_ОБР_З выпол-
няет задержку вычислений в теле внешне-
го цикла до тех пор, пока обработка во
всех параллельных ветвях не будет завер-
шена.
Естественно-лингвистическая фор-
ма данного алгоритма, построенного в си-
стеме ИПС, имеет следующий вид:
"(M[n]) СОРТ2_ПАР (M[n])" ====
ДЛЯ ((0) := (i); (i < n); (i, 1) + (i))
ЦИКЛ
Інструментальні засоби та середовища програмування
48
ПАРАЛЛЕЛЬНО ДЛЯ
((i, 2) % (j); (j < n - 1); (j, 2) + (j))
EСЛИ (M[j] > M[j+1])
ТО
"(M[j], M[j+1]) ПЕРЕСТАВИТЬ
(M[j], M[j+1])"
КОНЕЦ EСЛИ
ЗАТЕМ
('Обработка в текущей ветви
закончена') КТ(j) (S)
КОНЕЦ ПАРАЛЛЕЛЬНО
ЗАТЕМ
('Обработка во всех ветвях
закончена') S
КОНЕЦ ЦИКЛА
На рис. 2 показана копия экрана
ДСП-конструктора инструментария ИПС с
построенной схемой СОРТ2_ПАР. Окно
ДСП-конструктора состоит из трех вло-
женных элементов-окон. Верхнее левое
окно предназначено для отображения и
выбора алгоритмических конструкций и
вставки их в дерево алгоритма. Дерево ал-
горитма отображается в окне, находящем-
ся в правой части ДСП-конструктора. Тре-
тье окно, находящееся слева внизу, пред-
назначено для отображения текста алго-
ритма в процессе его конструирования в
естественно-лингвистической (САА-
схема) или алгебраической форме (форму-
ла), в зависимости от установленной оп-
ции. В данном случае текст алгоритма
представлен в алгебраической форме.
3.3. Генерация текста на языке
программирования и результаты запус-
ка подпрограмм. На основе схем СОРТ и
СОРТ2_ПАР в системе ИПС была выпол-
нена генерация кода подпрограмм на язы-
ке С++ – SORT и SORT2_PAR, соответ-
ственно. Текст подпрограммы SORT2_PAR
сгенерирован с использованием средств
OpenMP, и имеет следующий вид:
void SORT2_PAR(int *M, int n)
{
#pragma omp parallel
{
for (int i = 0; i < n; i = i + 1)
{
#pragma omp for
Рис. 2. Фрагмент копии экрана системы ИПС с алгоритмом СОРТ2_ПАР
Інструментальні засоби та середовища програмування
49
for (int j = i % 2; j < n - 1; j = j + 2)
{
if (M[j] > M[j+1])
{
int tmp = M[j];
M[j] = M[j+1];
M[j+1] = tmp;
}
}
}
}
}
Для реализации асинхронной
f-итерации в приведенной подпрограмме
использована директива omp for, выпол-
няющая распределение итераций цикла for
между потоками в параллельной области
программы. По умолчанию в этой дирек-
тиве используется блочное распределение
итераций цикла, т. е., если количество ите-
раций цикла равно m , а количество парал-
лельных потоков – p , то поток с номером
0 выполнит первые p/m итераций цикла,
следующие p/m итераций будут назначе-
ны потоку 1, и т. д. Отметим, что в конце
параллельного цикла OpenMP осуществля-
ет неявную синхронизацию потоков, и по-
этому специально реализовывать кон-
трольные точки и синхронизаторы в дан-
ном случае нет необходимости. Парал-
лельная область программы обозначена с
помощью директивы omp parallel, выпол-
няющей создание потоков [10]. Заметим,
что в приведенном тексте директива omp
parallel приведена перед внешним циклом,
а не внутри его (перед директивой omp
for), так как такой подход позволяет избе-
жать системных издержек, связанных с
многократным созданием потоков в этом
цикле [13, 14].
Проведен эксперимент по выполне-
нию разработанных подпрограмм SORT и
SORT2_PAR на двух 8-ядерных процессо-
рах Intel Xeon E5-2670 (2.60 ГГц), которые
входят в состав суперкомпьютерного вы-
числительного комплекса СКИТ-4 Инсти-
тута кибернетики имени В.М. Глушкова
НАН Украины [15]. Эксперимент выпол-
нен для размера массивов n от 32000 до
576000 элементов.
На рис. 3 показан график зависимо-
сти времени выполнения (в секундах) от
размера входного массива n для следую-
щих подпрограмм:
1) подпрограммы последовательной
пузырьковой сортировки SORT;
2) параллельной подпрограммы чёт-
нечётной сортировки SORT2_PAR при ко-
личестве потоков 1;
3) подпрограммы SORT2_PAR, вы-
полненной при количестве потоков 16.
Как видно из графика, программа
SORT2_PAR в обоих случаях является бо-
Рис. 3. Зависимость времени выполнения подпрограмм сортировки от размера массива n
Інструментальні засоби та середовища програмування
50
лее эффективной по времени выполнения,
чем пузырьковая сортировка SORT.
На рис. 4 показан график зависимо-
сти мультипроцессорного ускорения для
параллельной подпрограммы SORT2_PAR
от размера массива n. Ускорение вычисле-
но по формуле ,
16
1
T
T
Sp где 1T – время
выполнения SORT2_PAR с 1 потоком; 16T
– время выполнения SORT2_PAR с 16 по-
токами. Максимальное значение ускоре-
ния при n = 576000 составляет 24.14Sp .
Эффективность использования процессо-
ров при этом равна 890
16
.
Sp
E .
Отметим также, что по сравнению с
подпрограммой последовательной пузырь-
ковой сортировки SORT, подпрограмма
чёт-нечётной сортировки SORT2_PAR при
использовании 16 потоков и указанном
выше максимальном значении n выполня-
ется быстрее в 17.26 раз.
Таким образом, система ИПС обес-
печивает построение спецификаций по-
следовательных и параллельных алгорит-
мов, представленных в алгебре алгоритмов
с данными, а также выполняет генерацию
соответствующего текста на целевом язы-
ке программирования. Преимуществом
использования средств САА\Д в системе
ИПС является возможность анализа связей
между операторами в схемах для их по-
следующей трансформации (например,
распараллеливания). Так, в данном разделе
на примере задачи сортировки показан пе-
реход от последовательного алгоритма к
параллельному. Выполнены преобразова-
ния исходного алгоритма к его последую-
щему варианту, содержащему меньшее ко-
личество связей, а затем введение парал-
лельных конструкций.
Заключение
Предложено развитие алгеброалго-
ритмического инструментария проектиро-
вания и синтеза программ для конструиро-
вания спецификаций алгоритмов, сочета-
ющих совместное описание данных и по-
токов управления на основе использования
алгебры алгоритмов с данными. Преиму-
ществом использования спецификаций,
основанных на САА\Д, в сравнении со
схемами, представленными в САА, состо-
ит в использовании операторов, на входе и
выходе которых специфицированы обра-
батываемые данные. За счет этого в
САА\Д более детально представлены ин-
формационные связи между частями алго-
ритма, позволяющие выполнять анализ и
преобразования схем с целью их улуч-
шения (в частности, распараллеливания).
Рис. 4. Зависимость мультипроцессорного ускорения Sp
параллельной подпрограммы SORT2_PAR от размера массива n
Інструментальні засоби та середовища програмування
51
Применение предложенного в рам-
ках САА\Д подхода к проектированию ал-
горитмов и инструментария проиллюстри-
ровано на примере разработки подпро-
грамм сортировки массивов. Проведен
эксперимент по выполнению разработан-
ных подпрограмм на мультипроцессорном
кластере, результаты которого демонстри-
руют хороший показатель эффективности
распараллеливания вычислений.
1. Андон Ф.И., Дорошенко А.Е., Цейт-
лин Г.Е., Яценко Е.А. Алгеброалгоритмиче-
ские модели и методы параллельного про-
граммирования. – Киев: Академпериодика,
2007. – 631 с.
2. Дорошенко А.Е., Жереб К.А., Яценко Е.А.
Формализованное проектирование эффек-
тивных многопоточных программ // Про-
блеми програмування. – 2007. – № 1. –
С. 17–30.
3. Дорошенко А.Е., Яценко Е.А., Жереб К.А.
Средства синтеза параллельных MPI-
программ // Проблеми програмування. –
2008. – № 2–3. – С. 595–604.
4. Дорошенко А.Ю., Бекетов О.Г., Же-
реб К.А., Яценко О.А. Формалізоване прое-
ктування та синтез паралельних програм
для відеографічних прискорювачів // Про-
блеми програмування. – 2013. – № 3. –
С. 38–46.
5. Акуловский В.Г. Алгебра алгоритмов, бази-
рующаяся на данных // Кибернетика и си-
стемный анализ. – 2012. – № 2. –
С. 151–166.
6. Акуловский В.Г., Дорошенко А.Е. Описание
параллелизма в алгоритмах информацион-
но-управляющих систем средствами ал-
гебраического аппарата // Проблеми про-
грамування. – 2013. – № 3. – С. 13–21.
7. Sannella D., Tarlecki A. Foundations of alge-
braic specification and formal software devel-
opment. – Berlin: Springer-Verlag, 2012. –
594 p.
8. Flener P. Achievements and prospects of
program synthesis // Lecture Notes in Artifi-
cial Intelligence. – 2002. – Vol. 2407. –
P. 310–346.
9. Gulwani S. Dimensions in program
synthesis // Proc. 12th Int. ACM SIGPLAN
symposium on Principles and Practice of De-
clarative Programming, Hagenberg, Austria
(26–28 July, 2010). – New York: ACM,
2010. – P. 13–24.
10. OpenMP Application Program Interface. –
http://www.openmp.org/mp-documents/
OpenMP4.0.0.pdf.
11. Doroshenko A., Shevchenko R. A rewriting
framework for rule-based programming dy-
namic applications // Fundamenta Informati-
cae. – 2006. – 72, N 1–3. – P. 95–108.
12. Odd–even sort. – http://en.wikipedia.org/wiki/
Odd–even_sort
13. Pacheco P. More about loops in OpenMP:
sorting // An introduction to parallel pro-
gramming. – Burlington: Morgan Kaufmann,
2011. – P. 232–236.
14. Parallel Computing Lecture 15: OpenMP
III. – http://cs.nyu.edu/courses/spring14/
CSCI-UA.0480-003/lecture15.pdf
15. Суперкомп'ютер ІК НАН України. –
http://icybcluster.org.ua.
Получено 11.02.2015
Об авторах:
Акуловский Валерий Григорьевич,
кандидат технических наук,
доцент кафедры информационных
систем и технологий,
Дорошенко Анатолий Ефимович,
доктор физ.-мат. наук, профессор,
заведующий отделом теории
компьютерных вычислений,
Яценко Елена Анатольевна,
кандидат физико-математических наук,
старший научный сотрудник.
Место работы авторов:
Академия таможенной службы Украины.
49000, Днепропетровск,
ул. Дзержинского 2/4.
E-mail: academy@amsu.dp.uа,
valeryakulovskiy@rambler.ru
Институт программных систем
НАН Украины.
03187, Киев,
проспект Академика Глушкова, 40.
Тел.: (044) 526 3559.
E-mail: doroshenkoanatoliy2@gmail.com,
oayat@ukr.net
http://icybcluster.org.ua/
mailto:oayat@ukr.net
|