Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes
The approach to generation of terms by high-level specifications of algorithms is proposed. The generation is performed within the framework of joint use of symbolic computation system and algebro-algorithmic toolkit of program design and synthesis. The term rewriting system complements the algebro-...
Збережено в:
| Дата: | 2025 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2025
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/779 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-779 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/a0/ef5e2c451aaa773d2abe164087aceba0.pdf |
| spelling |
pp_isofts_kiev_ua-article-7792025-08-27T13:11:22Z Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes Интеграция инструментальных средств алгебры алгоритмов и переписывания термов для разработки эффективных параллельных программ Yatsenko, O.A. UDC 681.3 УДК 681.3 The approach to generation of terms by high-level specifications of algorithms is proposed. The generation is performed within the framework of joint use of symbolic computation system and algebro-algorithmic toolkit of program design and synthesis. The term rewriting system complements the algebro-algorithmic toolkit with means of transforming sequential and parallel algorithms aimed at their improvement.Problems in programming 2013; 2: 62-70 Предложен подход к генерации термов по высокоуровневым спецификациям алгоритмов. Генерация выполняется в рамках совместного использования системы символьных вычислений и алгеброалгоритмического инструментария проектирования и синтеза программ. Система переписывания термов дополняет алгеброалгоритмический инструментарий средствами преобразования последовательных и параллельных алгоритмов, направленных на их улучшение.Problems in programming 2013; 2: 62-70 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/779 PROBLEMS IN PROGRAMMING; No 2 (2013); 62-70 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2013); 62-70 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2013); 62-70 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/779/831 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-08-27T13:11:22Z |
| collection |
OJS |
| language |
Russian |
| topic |
UDC 681.3 |
| spellingShingle |
UDC 681.3 Yatsenko, O.A. Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| topic_facet |
UDC 681.3 УДК 681.3 |
| format |
Article |
| author |
Yatsenko, O.A. |
| author_facet |
Yatsenko, O.A. |
| author_sort |
Yatsenko, O.A. |
| title |
Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_short |
Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_full |
Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_fullStr |
Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_full_unstemmed |
Integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_sort |
integration of algorithm algebra and term rewriting tools for developing efficient parallel programmes |
| title_alt |
Интеграция инструментальных средств алгебры алгоритмов и переписывания термов для разработки эффективных параллельных программ |
| description |
The approach to generation of terms by high-level specifications of algorithms is proposed. The generation is performed within the framework of joint use of symbolic computation system and algebro-algorithmic toolkit of program design and synthesis. The term rewriting system complements the algebro-algorithmic toolkit with means of transforming sequential and parallel algorithms aimed at their improvement.Problems in programming 2013; 2: 62-70 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/779 |
| work_keys_str_mv |
AT yatsenkooa integrationofalgorithmalgebraandtermrewritingtoolsfordevelopingefficientparallelprogrammes AT yatsenkooa integraciâinstrumentalʹnyhsredstvalgebryalgoritmoviperepisyvaniâtermovdlârazrabotkiéffektivnyhparallelʹnyhprogramm |
| first_indexed |
2025-09-17T09:22:14Z |
| last_indexed |
2025-09-17T09:22:14Z |
| _version_ |
1850411424521650176 |
| fulltext |
Формальні методи розробки програмного забезпечення
© Е.А. Яценко, 2013
62 ISSN 1727-4907. Проблеми програмування. 2013. № 2
УДК 681.3
Е.А. Яценко
ИНТЕГРАЦИЯ ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ
АЛГЕБРЫ АЛГОРИТМОВ И ПЕРЕПИСЫВАНИЯ ТЕРМОВ
ДЛЯ РАЗРАБОТКИ ЭФФЕКТИВНЫХ
ПАРАЛЛЕЛЬНЫХ ПРОГРАММ
Предложен подход к генерации термов по высокоуровневым спецификациям алгоритмов. Генерация
выполняется в рамках совместного использования системы символьных вычислений и алгеброалгорит-
мического инструментария проектирования и синтеза программ. Система переписывания термов до-
полняет алгеброалгоритмический инструментарий средствами преобразования последовательных и па-
раллельных алгоритмов, направленных на их улучшение.
Введение
В наши дни однопроцессорные си-
стемы практически полностью вытеснены
многопроцессорными, позволяющими по-
лучать значительный прирост произво-
дительности программ. При этом ис-
пользование многопроцессорных систем
тесно связано с необходимостью распре-
деления вычислений на различные про-
цессоры и ядра, т. е., связано с распаралле-
ливанием программ [1]. Существуют биб-
лиотеки, такие как pthreads [2], OpenMP
[3], TBB [4] и др., позволяющие разра-
ботчикам создавать параллельные про-
граммы. При их использовании програм-
мист вручную производит разделение ко-
да на независимые составляющие, обес-
печивает обмен данными и синхрониза-
цию между ними (подход pthreads), либо
указывает компилятору, как и какие
участки кода нужно распараллеливать
(подход OpenMP). Однако у таких ручных
методов есть существенные недостатки, в
частности, связанные с внесением ошибок
в программу и временем, требуемым на
распараллеливание и отладку. Учитывая
процесс распараллеливания последова-
тельных программ целесообразно макси-
мально автоматизировать, а в идеале –
осуществлять полностью автоматически,
без участия программиста [5].
В предыдущих работах автора [6–8]
выполнено исследование проблемы авто-
матизации разработки эффективных про-
грамм для многоядерных архитектур с
использованием алгеброалгоритмического
Инструментария Проектирования и Синте-
за программ (ИПС). В основу автоматиза-
ции проектирования и программирова-
ния в рамках разработанного инстру-
ментария положена высокоуровневая фор-
мализация конструирования параллель-
ных алгоритмов и применение формаль-
ных трансформаций программ для опти-
мизации их производительности. Под
оптимизацией программ понимается до-
стижение требуемых качественных ха-
рактеристик программы по заданным
критериям (память, быстродействие, за-
грузка оборудования и др.). Система
ИПС базируется на представлении алго-
ритмов в системах алгоритмических ал-
гебр В.М. Глушкова (САА) [9] и выпол-
няет синтез последовательных и парал-
лельных (многопоточных) программ на
языках программирования Java, C++,
Cilk++ по схемам алгоритмов. Для авто-
матизации выполнения трансформаций
алгоритмов (программ) в работах [7, 8]
была использована система символьных
вычислений (на основе парадигмы перепи-
сывания термов) TermWare [10], которая
расширяет возможности системы ИПС и
позволяет автоматизировать решение за-
дач анализа и обеспечения надежности
программного кода. Отметим, что в [7, 8]
преобразование схем алгоритмов в тер-
мы производилось вручную. Данная ра-
бота посвящена разработке средств гене-
рации термов по спецификациям алго-
ритмов, представленным в САА. Подход
проиллюстрирован на параллельном алго-
ритме рекурсивной сортировки.
Формальні методи розробки програмного забезпечення
63
Материал работы имеет следую-
щую структуру. В разделе 1 рассматрива-
ются средства формализованного проек-
тирования алгоритмов, которые исполь-
зуются в системе ИПС. В разделе 2 крат-
ко охарактеризована система TermWare
и возможности ее применения с ИПС.
Раздел 3 посвящен рассмотрению про-
цесса генерации текстов программ и
термов по схемам алгоритмов в алгебро-
алгоритмическом инструментарии.
1. Средства формализованного
проектирования программ и
алгеброалгоритмический
инструментарий
В основу разработанного инстру-
ментария проектирования и синтеза про-
грамм положен аппарат САА и их моди-
фикаций [9]. Модифицированные САА
(САА-М) предназначены для формали-
зации процессов мультиобработки, кото-
рые возникают, в частности, при кон-
струировании программного обеспечения
в мультипроцессорных системах.
САА являются двухосновной ал-
геброй ;,BU , где U – множество
операторов, B – множество логических
условий. Операторы представляют собой
отображения информационного множе-
ства (ИМ) в себя, логические условия
являются отображениями множества ИМ в
множество значений 3-значной логики
3E = 0 , 1, , , где 0 – ложь; 1 – истина;
– неопределенность. Сигнатура опера-
ций САА 1 2 состоит из системы
1 логических операций, принимающих
значения в множестве B , и системы 2
операций, принимающих значения в мно-
жестве операторов U .
К логическим операциям системы
1 относятся обобщенные булевы опера-
ции: дизъюнкция, конъюнкция, отрицание,
а также операция левого умножения усло-
вия на оператор.
К основным операторным операци-
ям системы 2 относятся:
• “оператор1” ЗАТЕМ “опера-
тор2” – последовательное выполнение
операторов;
• оператор ветвления:
ЕСЛИ ‘условие’ ТО
“оператор1”
ИНАЧЕ
“оператор2”
КОНЕЦ ЕСЛИ;
• оператор цикла:
ПОКА НЕ ‘условие_окончания_
цикла’
ЦИКЛ “оператор”
КОНЕЦ ЦИКЛА;
• оператор цикла типа for:
ДЛЯ ("переменная1" ОТ
"выражение1" ДО
"выражение2")
ЦИКЛ
"оператор1"
КОНЕЦ ЦИКЛА
• асинхронное выполнение двух
операторов (данная операция называется
также асинхронной дизъюнкцией):
("оператор1"
ПАРАЛЛЕЛЬНО
"оператор2")
• синхронизатор, выполняющий за-
держку вычислений до тех пор, пока усло-
вие 'условие1' не станет истинным:
ЖДАТЬ 'условие1'
В работах [6, 9] аппарат САА-М
применен при решении задач символь-
ной мультиобработки: последовательных
и параллельных сортировок, поиска, язы-
кового процессирования и др.
В качестве примера далее приве-
дена САА-схема быстрой сортировки вхо-
дного массива A длины n. В данном
алгоритме вначале выполняется состав-
ной оператор "main", считывающий
размер входного массива и вызывающий
Формальні методи розробки програмного забезпечення
64
затем функцию "qmain(n)". Оператор
"qmain (n)" заполняет исходный мас-
сив A случайными значениями и вызы-
вает функцию "sample_qsort". Данная
функция сортирует подмассив, ограни-
ченный указателями begin и end, и
использует для этого стратегию “разде-
ляй и властвуй” [11].
СХЕМА QUICKSORT_SERIAL
"main" ====
===="Определить переменную (n)
типа (int) = (1000 * 10000)"
ЗАТЕМ
ЕСЛИ 'Количество параметров
командной строки больше (1)'
ТО "Присвоить переменной (n)
значение (1)-го параметра
командной строки"
КОНЕЦ ЕСЛИ
ЗАТЕМ
"qmain(n)"
"qmain(n)"
==== ЛОКАЛЬНЫЕ_ПЕРЕМЕННЫЕ
(
"Определить массив (A)
тип (int) размер (n)";
"Определить переменную (i)
тип (int)";
"Определить переменную (end)
тип (int)"
)
ЗАТЕМ
ДЛЯ (i ОТ 0 ДО n - 1)
ЦИКЛ
"A[i] := i"
КОНЕЦ ЦИКЛА
ЗАТЕМ
"Перемешать элементы массива
(A) длины (n) случайным обра-
зом"
ЗАТЕМ
"Начать отсчет времени"
ЗАТЕМ
(end := A + n)
ЗАТЕМ
"sample_qsort(A, end)"
ЗАТЕМ
"Закончить отсчет времени
и вывести результат"
ЗАТЕМ
"Проверить отсортированность
массива (A) длины (n)"
"sample_qsort(begin, end)"
==== ЕСЛИ НЕ('begin = end')
ТО "Уменьшить (end) на (1)"
ЗАТЕМ
"Переупорядочить массив (A)
с границами (begin)(end) так,
чтобы элементы, меньшие опорного
элемента (end), находились слева
от него, а большие находились
справа; сохранить позицию опорно-
го элемента в переменной
(middle)"
ЗАТЕМ
"sample_qsort(begin,
middle)"
"Увеличить (middle) на (1)"
ЗАТЕМ
"Увеличить (end) на (1)"
ЗАТЕМ
"sample_qsort(middle, end)"
КОНЕЦ ЕСЛИ
КОНЕЦ СХЕМЫ QUICKSORT_SERIAL
Интегрированный инструментарий
основывается на методе диалогового
конструирования синтаксически пра-
вильных программ [6] и использует раз-
личные формы представления алгоритмов
в процессе их проектирования – есте-
ственно-лингвистическую (САА-схемы),
алгебраическую (регулярные схемы) и
граф-схемную. Отметим, что интегриро-
ванный инструментарий может быть
настроен на требуемый входной язык,
представленный в алгебре алгоритмов, и
выходной (целевой) язык программиро-
вания. В настоящее время он поддержи-
вает генерацию последовательных и па-
раллельных программ на языках C++,
Java [6 – 8], Cilk++, а также термов (на
языке системы TermWare [10]) по САА-
Формальні методи розробки програмного забезпечення
65
схемам алгоритмов. Основными компо-
нентами интегрированного инструмента-
рия являются:
• ДСП-конструктор, предназначен-
ный для диалогового проектирования син-
таксически правильных схем алгоритмов и
синтеза программ;
• редактор граф-схем;
• трансформатор, осуществляющий
диалоговое преобразование регулярных
схем;
• генератор САА-схем по парамет-
ризованным схемам более высокого уров-
ня (гиперсхемам);
• база данных алгеброалгоритми-
ческих спецификаций, содержащая опи-
сание конструкций САА-М, базисных
(элементарных) операторов и предика-
тов, а также их отображение в язык про-
граммирования.
В основу функционирования ДСП-
конструктора положен диалоговый режим
с использованием меню подстановок и де-
рева конструирования алгоритма (см. при-
мер дерева конструирования в [6]). Меню
состоит из конструкций САА-М, суперпо-
зиция которых позволяет создавать алго-
ритмы в упомянутых ранее формах. Вы-
бранные пользователем конструкции, а
также операторные и логические пере-
менные, входящие в них, отображаются в
дереве с дальнейшей детализацией пере-
менных. В зависимости от типа выбран-
ной переменной (операторная или пре-
дикатная) система предлагает соответ-
ствующий список операций САА-М или
элементарных понятий из базы данных.
Отметим поуровневый стиль конструиро-
вания алгоритма, а также возможность
переходов на различные уровни (узлы
дерева) с продолжением процесса диало-
гового конструирования. Более подробно
процесс генерации программного кода
по схемам алгоритмов рассматривается в
разделе 3.
2. Система TermWare
Система TermWare направлена на
разработку высокодинамичных приклад-
ных систем, к которым предъявляются
повышенные требования, как к встроен-
ному интеллекту для обеспечения интер-
активности разрабатываемых систем, так
и удешевлению разработки, сокращению
сроков проектирования, улучшения ха-
рактеристик повторного их использова-
ния (реинжениринга) и сопровождаемости
[10]. Она отличается от большинства
других систем этого класса как назначе-
нием и семантикой используемых средств,
так и технологией их реализации. Язык
TermWare это координационный язык-
оболочка, предназначенный для написа-
ния предметно-ориентированных частей
приложений, встраиваемых в прикладную
систему для реализации функций взаимо-
действия этой системы с программным
окружением.
TermWare оформлена как библио-
тека языка Java, встраиваемая в про-
граммное приложение. Для разработчика
система термов выглядит как совокуп-
ность экземпляров класса ITermSystem,
с возможностью управления набором
правил и редуцирования термов. Набо-
ры правил описаны на языке TermWare
и хранятся в отдельных файлах. Осно-
вой языка являются термы, т. е. выраже-
ния вида ), ,( 1 nxxf . В качестве ато-
марных термов используются переменные
(которые записываются в виде $identi-
fier), а также константы определенных ти-
пов данных (числовых, логических, стро-
ковых и атомарного – неизменяемые
строки).
Набор правил содержит сами пра-
вила, а также дополнительную информа-
цию (название системы правил, исполь-
зуемая база фактов, применяемая страте-
гия). Типичное правило в TermWare за-
писывается следующим образом:
source condition
destination action ,
где используются четыре терма: source –
входной образец; destination – выходной
образец; condition – условие, определяю-
щее применимость правила; action – дей-
Формальні методи розробки програмного забезпечення
66
ствие, выполняемое при срабатывании
правила. Выполняемые действия и про-
веряемые условия в основном являются
вызовами методов в БД фактов. Таким
образом, осуществляется связь между
правилами на языке TermWare и кодом
на Java. Кроме того, возможно написа-
ние собственной стратегии, определяю-
щей порядок применения правил.
В простейшем случае переписыва-
ющее правило это выражение типа
x y , которое переписывает терм x в y .
Пусть, например, имеется терм plus ,x y ,
складывающий два числа. Тогда в резуль-
тате применения к нему набора из двух
правил
x y,
y z,
получим терм plus ,z z .
Основой функционирования си-
стемы TermWare в рамках совместного
использования с ИПС является создание
и применение систем правил. Каждая
система правил соответствует некоторо-
му преобразованию схемы алгоритма.
Кроме самих правил TermWare, система
правил может включать дополнительную
информацию, например, описание преоб-
разования или ссылки на другие систе-
мы правил, которые могут применяться
совместно с данной. Возможны также ин-
формационные системы правил, которые
не осуществляют преобразование схемы,
а вычисляют некоторые ее характеристи-
ки. Другие возможности совместного ис-
пользования более подробно рассмотре-
ны в работе [8]. Для интеграции с систе-
мой TermWare инструментарий ИПС
был дополнен средствами генерации
термов по схемам алгоритмов.
3. Генерация программ и термов
по схемам алгоритмов
По полученному в процессе кон-
струирования алгоритма дереву, а также в
соответствии с реализациями элементар-
ных операторов и условий на целевом
языке, инструментарий ИПС выполняет
генерацию кода на выбранном языке
программирования или термов TermWare.
В процессе синтеза управляющие кон-
струкции САА-схемы алгоритма и базис-
ные операторы и предикаты отображают-
ся в соответствующие операторы языка
программирования в соответствии с их
описанием в БД. Составные операторы
могут быть представлены как подпро-
граммы (методы). В случае генерации
объектно-ориентированной программы на
вход генератора поступает также файл,
который содержит каркасное описание
основного класса программы (без реали-
заций методов), в который выполняется
подстановка сгенерированного кода.
Для реализации параллельных про-
грамм в БД используются различные
средства:
потоки с использованием функ-
ций WinAPI [7, 12];
параллельные операции MPI [13],
ориентированные на обмен сообщениями
между процессами;
операторы языка параллельного
программирования Cilk++ [14].
Для распараллеливания рассмот-
ренного в разделе 1 алгоритма быстрой
сортировки был использован язык Cilk++,
так как он облегчает программирование
рекурсивных параллельных программ.
В табл. 1 приведено описание в БД
ИПС основных операторных операций
САА: композиции, альтернативы, цикла,
асинхронной дизъюнкции и синхрониза-
тора [9], реализации которых на языке
TermWare используются в процессе гене-
рации термов, а на языке Cilk++ – для ге-
нерации параллельных программ. Приве-
денные реализации содержат строки
^оператор1^ и ^оператор2^, вместо
которых в процессе генерации будут под-
ставлены тексты реализаций операндов
этих операций.
Формальні методи розробки програмного забезпечення
67
Таблица 1. Основные операторные операции САА и
их реализации на языках TermWare и C++
Естественно-
лингвистическая форма
Реализация на языке
TermWare
Реализация на языке Cilk++
“оператор1” ЗАТЕМ
“оператор2”
then (
^оператор1^,
^оператор2^)
^оператор1^;
^оператор2^
ЕСЛИ “условие1”
ТО “оператор1”
ИНАЧЕ “оператор2”
КОНЕЦ ЕСЛИ
IF (^условие1^,
^оператор1^,
ELSE (^оператор2^)
)
if (^условие1^)
{
^оператор1^
}
else { ^оператор2^ }
ПОКА НЕ ‘условие1’
ЦИКЛ
“оператор1”
КОНЕЦ ЦИКЛА
WHILE_NOT
(^условие1^,
^оператор1^
)
while (!(^условие1^))
{
^оператор1^
}
("оператор1"
ПАРАЛЛЕЛЬНО
"оператор2")
Parallel
( ^оператор1^,
^оператор2^
)
cilk_spawn ^оператор1^;
^оператор2^
ЖДАТЬ 'условие1' WAIT (^условие1^) cilk_sync;
В табл. 2 приведены примеры
описания в БД базисных элементов для
рассмотренного алгоритма быстрой сор-
тировки. Естественно-лингвистическая
форма описания базисного элемента со-
держит в себе имена формальных парамет-
ров в скобках. Фактические параметры,
которые задаются в САА-схемах, заменя-
ют при генерации программы соответ-
ствующие формальные параметры в тексте
реализации базисного понятия на языке
программирования. Признаком формаль-
ного параметра в реализации является
символ “%”, за которым следует порядко-
вый номер параметра в тексте базисного
оператора или предиката. Например, в ба-
зисном операторе "Увеличить (var_id) на
(value)" присутствует два параметра –
идентификатор переменной и значение, на
которое ее следует увеличить. Значение
этих параметров будет подставлено вместо
соответствующих формальных параметров
в реализации этого оператора.
Таблица 2. Примеры описания в БД базисных операторов
Естественно-
лингвистическая форма
Реализация на языке
TermWare
Реализация на языке C++
"Определить массив
(name) тип (type) размер
(size)"
Array(%1, %2, "%3") %2* %1 = new %2[%3];
"Определить переменную
(x) типа (тип)"
Variable(%1, %2) %2 %1;
"Увеличить (var_id) на
(value)"
Inc(%1, %2) %1 = %1 + %2;
"Перемешать массив
(name) длины (size) слу-
чайным образом"
ShuffleArrayRandomly
(%1, %2)
std::random_shuffle
(%1, %1 + %2);
Формальні методи розробки програмного забезпечення
68
В результате интеграции системы
TermWare и разработанного инструмента-
рия проектирования и синтеза программ, в
TermWare передается термальное пред-
ставление алгоритма, подлежащего транс-
формации и требуемые для этого равен-
ства. Затем по преобразованному в
TermWare алгоритму может быть произве-
дена генерация соответствующей про-
граммы на языке программирования.
Далее в качестве примера приведен
терм, сгенерированный по схеме последо-
вательного алгоритма быстрой сортиров-
ки, рассмотренной в разделе 1.
Root (
main(
then (
Variable(n, int,
"1000 * 10000"),
then (
IF (Greater(CmdLineParams,
1),
Assign(n, 1)),
CALL(qmain(n))))),
qmain(Params(n),
then (
Locals
(
Array(a, int, "n"),
Variable(i, int),
Variable(end, int)
),
then (
ForLoop(i, 0, Minus(n, 1),
AssignArrayElement
(a, i, i)
),
then (
ShuffleArrayRandomly(a, n),
then (
START_TIME,
then (
then (
Assign(end, Plus(a, n)),
sample_qsort(Params(begin, end),
IF (NOT(Equal(begin, end)),
then (
Dec(end, 1),
then (
Partition(a, begin, end,
end),
then (
CALL(sample_qsort(begin,
middle)),
then (
Inc(middle, 1),
then (
Inc(end, 1),
CALL(sample_qsort(middle,
end)
)))))))
)
)
Для распараллеливания приведен-
ного алгоритма в функцию sample_qsort
необходимо добавить операцию асинхрон-
ного выполнения операторов и синхрони-
затор (см. раздел 1). Для этого применяют-
ся следующие два правила:
1. then(CALL($x),
then ($y, $z)) ->
Parallel (
CALL($x),
then($y, $z))
2. then($x1,
Parallel($x2, $x3)) ->
then($x1,
then(Parallel($x2, $x3),
WAIT(AllThreadsCompleted(n))
))
В результате применения данных
правил функция sample_qsort будет
иметь вид:
sample_qsort( Params(begin,end),
IF(NOT(Equal(begin,end)),
then (
Dec(end,1),
then(
Partition(a,begin,end,end),
then(
Parallel(
CALL(sample_qsort
(begin,middle)),
then(
Inc(middle,1),
then(
Inc(end,1),CALL(sample_qsort
(middle,end))))
),
WAIT(AllThreads
Completed(n)))))))
Формальні методи розробки програмного забезпечення
69
Таким образом, в результате распа-
раллеливания в первой ветви операции
Parallel вызывается оператор
sample_qsort (begin,middle), а в
другой – sample_qsort(middle,end).
Ветви создаются рекурсивно; их коли-
чество в алгоритме явно не указано, и
задается при вызове программы. Синхро-
низатор AIT(AllThreadsCompleted(n))
выполняет задержку вычислений до тех
пор, пока все ветви не закончат вычис-
ления. Как уже упоминалось, для реали-
зации рассмотренного алгоритма сорти-
ровки был использован язык параллель-
ного программирования Сilk++. Полу-
ченная программа была выполнена на
многоядерной архитектуре Intel Core 2
Quad CPU, 2.51 ГГц. Время ее выполне-
ния показано на рисунке. Ускорение
при выполнении на 2, 3 и 4 процессо-
рах составило 2; 2.9 и 3.8 соответствен-
но, что свидетельствует о хорошей сте-
пени распараллеливаемости и масштаби-
руемости вычислений.
Рисунок. Время выполнения параллельной
программы быстрой сортировки
на 4-ядерном процессоре;
размер входного массива 5 10
7
элементов
Заключение
Предложен подход к генерации
термов по высокоуровневым специфика-
циям алгоритмов. Генерация выполняется
в рамках совместного использования си-
стемы символьных вычислений TermWare
и алгеброалгоритмического инструмента-
рия проектирования и синтеза программ
ИПС. Система TermWare дополняет ИПС
средствами преобразования последова-
тельных и параллельных алгоритмов,
направленных на их улучшение. Основой
функционирования системы TermWare в
рамках ИПС является создание и примене-
ние систем правил, каждая из которых со-
ответствует некоторой трансформации
схемы алгоритма. Отметим, что TermWare
также позволяет расширить возможности
ИПС в части автоматизации решения задач
анализа и обеспечения надежности про-
граммного кода.
Перспективами дальнейших иссле-
дований в данном направлении является
дополнение системы ИПС средствами об-
ратного преобразования термов в схемы
алгоритмов, а также настройка обоих си-
стем на генерацию программ в других
языках, поддерживающих распараллели-
вание.
1. Система автоматизации распараллелива-
ния программ на промежуточном пред-
ставлении LLVM. –
http://www.dataved.ru/2011/06/llvmautoparal
lelizer.html.
2. Multi-Threaded Programming With POSIX
Threads. – http://users.actcom.co.il/~choo./
lupg/tutorials/multi-thread/multi-thread.html.
3. OpenMP Application Program Interface. –
http://www.openmp.org/mp-documents/
spec30.pdf.
4. Intel Threading Building Blocks. –
http://threadingbuildingblocks.org
5. Клинов М.С., Крюков В.А. Автоматическое
распараллеливание Фортран-программ.
Отображение на кластер. –
http://www.ict.edu.ru/vconf/files/11879.pdf.
6. Дорошенко Е.А., Яценко Е.А. О синтезе
программ на языке Java по алгеброалго-
ритмическим спецификациям // Проблеми
програмування. – 2006. – № 4. – С. 58–70.
7. Дорошенко Е.А., Жереб К.А., Яценко Е.А.
Формализованное проектирование эффек-
тивных многопоточных программ // Про-
блеми програмування. – 2007. – № 1. –
С. 17–30.
8. Дорошенко А.Е., Жереб К.А., Яценко Е.А.
Об оценке сложности и координации вы-
числений в многопоточных программах //
Проблеми програмування. – 2007. – № 2. –
С. 41–55.
http://www.dataved.ru/
http://users.actcom.co.il/~choo./
http://www.openmp.org/mp-documents/
http://threadingbuildingblocks.org/
Формальні методи розробки програмного забезпечення
70
9. Андон Ф.И., Дорошенко А.Е., Цейт-
лин Г.Е., Яценко Е.А. Алгеброалгоритмиче-
ские модели и методы параллельного про-
граммирования. – Киев: Академпериодика,
2007. – 631 с.
10. Дорошенко А.Е., Шевченко Р.С. Система
символьных вычислений для программи-
рования динамических приложений // Про-
блеми програмування. – 2005. – № 4. –
С. 718–727.
11. Кнут Д. Искусство программирования для
ЭВМ. – М.: Мир, 1978. – Т. 3. – 843 с.
12. Guptha S. Multithreaded Programming in a
Microsoft Win32* Environment. –
http://eng.harran.edu.tr/~nbesli/SP/senkroniza
syon.pdf.
13. Writing Message-Passing Parallel Programs
with MPI. –
http://www.zib.de/zibdoc/mpikurs/mpicourse.
pdf.
14. Intel Cilk++ SDK Programmer's Guide. –
http://www.clear.rice.edu/comp422/resources/
Intel_Cilk++_Programmers_Guide.pdf.
Получено 20.07.2012
Об авторе:
Яценко Елена Анатольевна,
кандидат физико-математических наук,
старший научный сотрудник.
Место работы автора:
Институт программных систем
НАН Украины.
Тел.: (044) 424 4972,
E-mail: oayat@ukr.net
http://eng.harran.edu.tr/~nbesli/SP/senkronizasyon.pdf
http://eng.harran.edu.tr/~nbesli/SP/senkronizasyon.pdf
http://www.zib.de/zibdoc/
|