Особенности реализации средств трансформационного синтеза параллельных алгоритмов
Рассмотрены особенности реализации средства трансформационного синтеза параллельных алгоритмов с применением последовательной рекурсивной декомпозиции на основе таблиц иерархии. Представлена архитектура соответствующего инструментария (Трансформатор). Розглянуто особливості реалізації засобу трансфо...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6577 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Особенности реализации средств трансформационного синтеза параллельных алгоритмов / А.С. Мохница, В.А. Иовчев, Е.А. Андрющенко // Пробл. програмув. — 2009. — № 4. — С. 24-32. — Бібліогр.: 31 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860131431174373376 |
|---|---|
| author | Мохница, А.С. Иовчев, В.А. Андрющенко, Е.А. |
| author_facet | Мохница, А.С. Иовчев, В.А. Андрющенко, Е.А. |
| citation_txt | Особенности реализации средств трансформационного синтеза параллельных алгоритмов / А.С. Мохница, В.А. Иовчев, Е.А. Андрющенко // Пробл. програмув. — 2009. — № 4. — С. 24-32. — Бібліогр.: 31 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрены особенности реализации средства трансформационного синтеза параллельных алгоритмов с применением последовательной рекурсивной декомпозиции на основе таблиц иерархии. Представлена архитектура соответствующего инструментария (Трансформатор).
Розглянуто особливості реалізації засобу трансформаційного синтезу паралельних алгоритмів з застосуванням послідовної рекурсивної декомпозиції на основі таблиць ієрархії. Представлена архітектура відповідного інструментарію (Трансформатор).
Paper examines the implementation of tools for transformational synthesis of parallel algorithms, which are using sequential recursive decomposition based on the tables of hierarchy. Architecture of the corresponding toolkit (Transformator) is presented.
|
| first_indexed | 2025-12-07T17:44:43Z |
| format | Article |
| fulltext |
Моделі та засоби паралельних і розподілених програм
24
УДК 681.3
А.С. Мохница, В.А. Иовчев, Е.А. Андрющенко
ОСОБЕННОСТИ РЕАЛИЗАЦИИ СРЕДСТВ
ТРАНСФОРМАЦИОННОГО СИНТЕЗА ПАРАЛЛЕЛЬНЫХ
АЛГОРИТМОВ
Рассмотрены особенности реализации средства трансформационного синтеза параллельных алгоритмов
с применением последовательной рекурсивной декомпозиции на основе таблиц иерархии.
Представлена архитектура соответствующего инструментария (Трансформатор).
Введение
К числу актуальных областей
современной компьютерной науки
относится алгебраическая алгоритмика
(АА) [1]. В последние годы за рубежом
была предложена концепция ментального
программирования (Intentional Program-
ming (IP)), которая неразрывно связана с
формализацией программирования [2].
Данная концепция основана на моделиро-
вании программных систем и их
реализации. В Украине исследования в
данной области восходят к фундаменталь-
ным работам В.М. Глушкова по теории
систем алгоритмических алгебр (САА) [3].
Дальнейшее развитие теории САА нашло
свое воплощение в алгебре алгоритмики
(<АА>) – в новом, интенсивно
развивающемся направлении украинской
алгебро-кибернетической школы [4].
Цель данной работы – осветить
особенности реализации средств транс-
формационного синтеза параллельных
алгоритмов.
1. Средства автоматизации
проектирования параллельных
алгоритмов
Рассмотрим концепции IP и САА в
их сравнительном анализе [1, 2, 5].
Основные принципы, на которых бази-
руется IP, можно сформулировать таким
образом:
− общие и предметно-ориентиро-
ванные абстракции;
− биология программирования;
− экология программирования.
Приведенные ранее принципы
соответствуют базовым составляющим
<АА>. Абстракции представляются в виде
взаимосвязанных форм проектирования
алгоритмов:
− аналитическая – позволяет описы-
вать алгоритмы в виде формул соответст-
вующих алгебр; является удобной для
трансформации, а именно для их
улучшения по выбранным критериям
(памяти, скорости и т. д.);
− текстовая (естественно-лингви-
стическая) – позволяет проектировать
алгоритмы на различных входных языках;
− визуальная – граф-схемная.
Биологическая компонента в <АА>
– теория клонов, используется для описа-
ния, построения и исследования семейств
алгебр [6]. При использовании теории
клонов можно описать различные языки,
принадлежащие выбранному семейству
алгебр. Примером служит язык САА и его
модификации.
Экологическая компонента в <АА>
представима в виде интегрированных
инструментальных средств разработки и
синтеза алгоритмов и программ в
объектных средах: МУЛЬТИПРОЦЕС-
СИСТ, САА-машина, ДСП-конструктор,
Трансформатор. Метод многоуровневого
структурного проектирования программ
(МСПП) объединяет алгебраический и
грамматический подходы по конструиро-
ванию программ.
Следует отметить, что основное
назначение языков проектирования схем
алгоритмов – представление алгоритмов в
форме, ориентированной на человека и
© А.С. Мохница, В.А. Иовчев, Е.А. Андрющенко, 2009
ISSN 1727-4907. Проблеми програмування. 2009. № 4
Моделі та засоби паралельних і розподілених програм
25
облегчающей процесс производства
программного обеспечения (ПО). Для
достижения цели возможно объединение
разных технических средств преобра-
зования и синтеза программ [7, 8].
Инструментальные средства МСПП
появились еще в 80-х годах при разработке
автоматизированной системы МУЛЬТИ-
ПРОЦЕССИСТ [7]. Данная система
проектировалась путем «самораскрутки».
Таким образом, компоненты системы, не
относящиеся к синтезированным, были
получены с помощью разработанных
компонент системы. К числу средств
инструментальной поддержки МСПП
относятся языки проектирования в
терминах САА-схем многоуровневых
формализованных проектов классов
алгоритмов и программ, структур данных
и памяти. Схемы допускают лингвисти-
ческие, аналитические и визуальные
представления в рамках интегрированной
технологии проектирования классов
алгоритмов и программ. Сама технология
базируется на соответствующих алгебрах
алгоритмов. Математическим базисом
данного языка является аппарат САА и его
модификации [3]. Метод МСПП реали-
зован в виде САА-машины, которая
является интерпретатором САА-схем,
предназначенных для отладки и
верификации [8]. ДСП-конструктор пред-
ставляет собой диалоговый конструктор
синтаксически правильных САА-схем [9–
11]. Трансформатор – инструмент для
преобразования аналитических специи-
фикаций алгоритмов с использованием
соотношений и тождеств соответствующей
алгебры [11].
Разрабатываемый в настоящее вре-
мя инструментарий предназначен для
проектирования параллельных программ
для современных сред выполнения, в
которых алгеброалгоритмические специ-
фикации и преобразования алгоритмов
объединены с мощными средствами авто-
матизации и синтеза программ на основе
Web 2.0. Отметим, что под современными
средами выполнения понимаются мульти-
ядерные, мультипотоковые, кластерные,
Грид-системы, облачные системы и
т. д. [12]. Данный инструментарий (в
отличие от системы МУЛЬТИПРОЦЕССИСТ)
состоит в интеграции всех трех
представлений алгоритма [13]: анали-
тического (формула в избранной алгебре),
естественно-лингвистического (САА-схе-
мы) и графового (граф-схемы Калужнина)
при его конструировании. Как следствие,
использование в инструментарии всех трех
форм представления дает более полную
картину о конструируемом алгоритме, чем
любое из них по отдельности. Изменение
любого из этих представлений в инстру-
ментарии автоматически приведет к
соответствующему преобразованию оста-
льных.
2. Архитектура
инструментальных средств
трансформации
Необходимо отметить, что задача
трансформации аналитических специфика-
ций алгоритмов и программ – не нова.
Тождественным преобразованиям алгорит-
мов символьной мультиобработки посвя-
щен ряд работ Г.Е. Цейтлина [13-15]. Не
менее важна проблема автоматизации
применения тождественных преобразова-
ний в САА. Работа [16] посвящена
тождественным преобразованиям недетер-
минированных схем алгоритмов и
программ. Доказательство тождеств в
аксиоматизированных САА рассматри-
вается в [17]. Проблема автоматизации
оптимизирующих преобразований – в [18].
Решение проблемы тупиков в парал-
лельных регулярных схемах программ с
помощью тождественных преобразований
приведено в [19].
Решение этих и ряда других важных
задач алгоритмики связано с разработкой
интегрированного инструментария <АА>.
В рамках работы над инструментальными
средствами синтеза алгоритмов и про-
грамм в объектных средах с помощью
аппарата <АА> был спроектирован и
реализован на языке программирования
Delphi инструментарий трансформации
схем алгоритмов и программ (Транс-
форматор) [20]. Внешний вид Трансфор-
матора показан на рис. 1.
Интерфейс приложения состоит из
следующих элементов:
Моделі та засоби паралельних і розподілених програм
26
Рис. 1. Главное окно инструментария трансформации схем алгоритмов и программ
− трансформации и хранящихся в
базе данных Трансформатора [20];
− поля редактирования, содержа-
щего трансформируемое аналитическое
выражение на данном этапе преобра-
зования, а также на все предыдущих
этапах;
− поля редактирования, отображаю-
щего информацию о правилах (соотно-
шениях), примененных к трансфор-
мируемому выражению для каждого этапа
процесса преобразования.
Кроме того, программа предлагает
отдельное окно для ввода новых или
редактирования существующих тождеств с
сохранением в базе тождеств и соотно-
шений.
Выше упоминалось, что первона-
чально Трансформатор базировался на
алгоритме последовательной статической
декомпозиции ДЕК/С [21], осуществляю-
щем посимвольный анализ входной
цепочки и накладываемой на нее формы с
последующей переинтерпретацией выход-
ной цепочки с помощью получивших зна-
чение переменных формы.
В настоящее время Трансформатор
использует более эффективный алгоритм
последовательной рекурсивной декомпо-
зиции на основе таблиц иерархии, предло-
женный авторами.
Рассмотрим архитектуру инстру-
ментальных средств трансформации, пока-
занную на рис. 2. Трансформатор состоит
из следующих функциональных блоков:
ядро – базовый блок Трансфор-
матора, управляет и обеспечивает
взаимодействие остальных блоков;
ИП – интерфейс пользователя,
отвечает за взаимодействие Трансфор-
матора с пользователем;
БСИ – функциональный блок
Трансформатора, отвечающий за связь с
инструментальными средствами <АА>;
редактор правил трансформации –
блок, предназначенный для редактиро-
вания правил (грамматики) и контекстов,
применяемых во время трансформации;
Моделі та засоби паралельних і розподілених програм
27
Рис. 2. Архитектура Трансформатора
монитор отслеживает и протоколи-
рует изменения на каждом шаге транс-
формации, благодаря чему можно отме-
нить текущее действие и вернуться на
предыдущий этап;
блок преобразований – производит
все действия по трансформации входной
цепочки с использованием правил.
3. Особенности реализации
инструментальных средств
трансформации
Пусть G = (Vт, Vн, n0, P) –
бесконтекстная грамматика и P(u) = Н u К
– разметка цепочки u, подлежащей
анализу, L(G) ∈ V*т – язык, порожденный
грамматикой G, где n из Vн – нетерминал, а
u из Vт – терминал.
ТРАНСФОРМАТОР :: == ИНИЦ *
*ПОКА НЕ[КОНЕЦ ТРАНСФОРМАЦИИ]
ЦИКЛ
СЖАТИЕ.ТФ(Ф0) * СЖАТИЕ.ТПл(П.Л0) *
*СЖАТИЕ.ТПп(П.П0) *
* ПРИМЕНЕНИЕ(u’) * РАСЖАТИЕ(Ф0)
КЦ.
Где ТФ (таблица иерархий форму-
лы), ТПл (таблица иерархий левой части
правила), ТПп (таблица иерархий правой
части правила) – очереди;
Ф – цепочка формулы, Фi – под-
цепочка, где і = 0, 1, 2, ..., m;
П.Л – цепочка, левая часть правила,
П.Лi – подцепочка, где і = 0, 1, 2, ..., m;
П.П – цепочка, правая часть
правила, П.Пi – подцепочка, где
і = 0, 1, 2, ..., m;
ИНИЦ – оператор выполняющий
разметку входящей цепочки формулы и
цепочки правила;
u’ – уникальный терминал;
[КОНЕЦ ТРАНСФОРМАЦИИ] –
предикат, истинный в случае успешного
завершения трансформации, или
обнаружения в процессе работы ошибок.
СЖАТИЕ(Цn) :: =
= ЕСЛИ [Ф(n) – форма-суперпозиция]
ТО ДЕК/С(u/Ф(n)) * ЗАП.Т[(n, u)] *
*СЖАТИЕ (Цn+1) КЕ.
/* В результате выполнения дан-
ного оператора осуществляется деком-
позиция подцепочки Цn по форме Ф(n) с
фиксацией пар (n1, u1), (n2, u2), … (nm, um),
сформировавшихся в процессе декомпози-
ции; генерируется соответствующее
количество дуг, исходящих из
обрабатываемого узла (n, u) к узлам,
помеченным указанными парами и
расположенными на следующем уровне
дерева формируемой таблицы иерархий.
При этом помечающие пары в указанном
Моделі та засоби паралельних і розподілених програм
28
порядке записываются оператором ЗАП.Т
[(n, u)] в соответствующую Т, где Т ∈ {Ф,
П.Л, П.П }. */;
Рекурсивные операторы
СЖАТИЕ.ТФ(Ф0) и СЖАТИЕ.ТПл(П.Л0),
СЖАТИЕ.ТПп(П.П0) по сути одинаковы,
отличаясь только тем, что СЖА-
ТИЕ.ТФ(Ф0) декомпозирует формулу и
записывает узлы в ТФ; СЖА-
ТИЕ.ТПл(П.Л0) и СЖАТИЕ.ТПп(П.П0)
соответственно левую и правую часть
правила.
ПРИМЕНЕНИЕ(u’) :: =
= ЕСЛИ НЕ [u’ = #] ТО ПОИСК.Т(u’) КЕ
ЕСЛИ [ПОЗ = #] ТО ПОИСК.П КЕ
ЕСЛИ НЕ[ПОЗ = #] ТО ПРАВКА(ПОЗ)
КЕ.
/*При заданном уникальном
терминале u’ выполняется оператор
ПОИСК.Т(u’), который ищет заданный
терминал в терминалах пар ТФ. Если
уникальный терминал u’ не задан и/или
ПОИСК.Т(u’) ничего не нашел, то ПОЗ=#.
Тогда выполняется следующий ПОИСК.П
по (n0, u0) из Т.Пл. И если позиция не
найдена, то предикат КОНЕЦ
ТРАНСФОРМАЦИИ становится истин-
ным, сообщая о невозможности примене-
ния данного правила. В противном случае,
если один из поисков нашел позицию
ПОЗ, то происходит выполнение опера-
тора ПРАВКА(t), который модифицирует
участок пар (n, u) из ТФ парами (j, k) из
Т.Пп.*/
ПОИСК.Т(u’) :: =
= ПОКА НЕ [ЧТЕ.ТФ(nm | У1) = (#)
И ПОЗ = #]
ЦИКЛ ЕСЛИ [ЧТЕ.ТФ(nm | У1) = u’]
ТО ЕСЛИ [РАВ] ТО ЗАП.ПОЗ(nm) КЕ
ИНАЧЕ Р(У) КЕ КЦ
ПОИСК.П :: =
= ПОКА НЕ [ЧТЕ.ТФ(nm | У2) = (#)
И ПОЗ = # ]
ЦИКЛ ЕСЛИ [ЧТЕ.ТФ(nm | У2) =
= ЧТЕ.ТПл(0)] ТО ЕСЛИ [РАВ] ТО
ЗАП.ПОЗ(nm) КЕ ИНАЧЕ Р(У) КЕ КЦ
ЧТЕ.Т – оператор чтения пары (n, u)
– содержимого Т по n, и вывода u; здесь
n ∈ Vн – нетерминал, u – терминальная
подцепочка.
РАВ – предикат, истинный, в
случае, если связанные пары (поддерево)
от найденной позиции и связанные пары
(дерево) левой части правила одинаковы
по структуре.
ЗАП.ПОЗ – оператор записи най-
денной позиции в ПОЗ.
РАСЖАТИЕ(Ф0) :: =
= ПОКА НЕ [d(У4, К)]
ЦИКЛ ЕСЛИ [(элем ∈ Vн | У4)]
ТО РАЗВЕР(элем) * УСТ(У4, Н)
ИНАЧЕ Р(У4) КЕ КЦ.
Оператор РАСЖАТИЕ(Ф0) при
выполнении производит развертку (n0, u0)
из Т.Ф в символьную цепочку заменяя все
нетерминалы терминалами. В результате
получаем новую формулу.
Таким образом, к особенностям
реализации приведенного алгоритма
можно отнести использование рекурсив-
ной декомпозиции цепочек на основе
таблиц иерархии (фактически восходящий
синтаксический анализ), позволяющей об-
рабатывать более сложные выражения по
сравнению с ДЕК\С. Кроме того, алгоритм
позволяет использовать многоразовое и
пакетное применение правил трансфор-
мации.
4. Пример функционирования
алгоритма трансформации
Как уже упоминалось ранее,
Трансформатор использует алгоритм
последовательной рекурсивной деком-
позиции на основе таблиц иерархии.
Рассмотрим данный алгоритм на
примере преобразования формулы
((A * B) * {[U1] (A * B)} * C * {[U2] (B2 *
* {[U3] (A3 * B3)} * C2)})
по правилу (A *{[U] A}) => {A [U]} с
контекстом для обеих частей равенства
@se = A,U; (означает, что A и U – состав-
ные элементы (конструкции)).
Шаг 1. Построение таблицы иерар-
хии по входной цепочке (по сути, пред-
ставляет собой восходящий синтакси-
ческий анализ).
Таблица иерархии имеет следую-
щую структуру:
Моделі та засоби паралельних і розподілених програм
29
− области имен – пар вида [абстрак-
ция, базовый (не составной) элемент];
− области структур – пар вида
[абстракция, конструкция (составной эле-
мент)].
В табл. 1 обозначение @operator
(@predicat) представляет собой базовый
оператор (предикат), @so (@sp) – состав-
ной оператор (предикат), х – уникальный
индекс, например,
@operator_01 => A,
@operator_02 => B,
@so_01 => (@operator_01 * @operator_02).
Данная таблица может быть пред-
ставлена деревом восходящего син-
таксического разбора, показанным на
рис. 3.
Таблица 1. Таблица иерархии формулы
@operator_x A
@operator_x B
@so_x (@operator_x*@operator_x)
@predicat_x U1
@sp_x @predicat_x
@operator_x A
@operator_x B
@so_x (@operator_x*@operator_x)
@so_x {[@sp_x]@so_x}
@predicat_x U2
@sp_x @predicat_x
@predicat_x U3
@sp_x @predicat_x
@operator_x A3
@operator_x B3
@so_x (@operator_x*@operator_x)
@so_x {[@sp_x]@so_x}
@operator_x B2
@operator_x C2
@so_x
(@operator_x*
@so_x*@operator_x)
@so_x {[@sp_x]@so_x}
@operator_x C
@so_x
(@so_x*@so_x*
@operator_x*@so_x)
Шаг 2. Построение таблицы
иерархии для левой и правой части
правила (см. табл. 2). Дерево в данном
случае будет иметь вид, показанный на
рис. 4.
Шаг 3. Далее осуществляется поиск
конструкции @so_x*@so_x, находящейся
в вершине дерева левой части правила, в
дереве формулы (а точнее в области
структур таблицы иерархии), причем
индекс x не учитывается. Если поиск
завершился успехом (см. рис. 5), проис-
ходит сравнение всех ветвей, исходящих
из данных вершин, на идентичность в
целом.
Таблица 2. Таблица иерархии правила
Левая часть правила
@so_x A
@sp_x U
@so_x A
@so_x {[@sp_x]@so_x }
@so_x @so_x*@so_x
Правая часть правила
@so_x A
@sp_x U
@so_x {@so_x [@sp_x]}
Кроме того, при наличии контекст-
ного аргумента @where = «уникальный
элемент» ведется поиск в найденной
подобной конструкции уникального эле-
мента (оператора, предиката). Если такой
элемент отсутствует, выдается сообщение
о невозможности трансформации. Также
сообщение выдается при отсутствии
подобной вершины.
Шаг 4. Чтобы осуществить разверт-
ку [20] (т. е., чтобы найденная структура
@so_x * @so_x приобрела вид
{@so_x [@sp_x]}), необходимо внести
поправки в таблицу иерархии формулы,
сопоставив соответствующие вершины
деревьев формулы и правил (см. табл. 3).
Внеся поправки и проинтер-
претировав правую часть правила на
основе полученных значений нетер-
миналов, получаем следующую цепочку:
({(A * B) [U1]} * C * {[U2] (B2 *
* {[U3] (A3 * B3)} * C2)}).
Моделі та засоби паралельних і розподілених програм
30
Рис. 4. Деревья для таблицы иерархии правила
Таблица 3. Формирование поправок для таблицы иерархии формулы
Правая часть
правила
Формула Поправка
@so_x’ A @so_x (@operator_x*@operator_x) @so_x’ (@operator_x*@operator_x)
@sp_x’ U @sp_x @predicat_x @sp_x’ @predicat_x
@so_x’
{@so_x
[@sp_x]}
@so_x
(@so_x*@so_x*
@operator_x*@so_x)
@so_x’
({@so_x*[@sp_x]}*
@operator_x*@so_x)
Рис. 3. Дерево для таблицы иерархии формулы
Моделі та засоби паралельних і розподілених програм
31
Рис. 5. Поиск конструкции и сравнение ветвей
Заключение
В данной работе представлена архи-
тектура инструментального средства для
трансформационного синтеза парал-
лельных программ, названного Трансфор-
матором. Рассмотрены особенности
реализации Трансформатора с примене-
нием алгоритма последовательной рекур-
сивной декомпозиции на основе таблиц
иерархии на примере одного шага пре-
образования (применения правила к
символьной последовательности). При-
ведена САА-схема данного алгоритма.
В перспективе планируется пере-
нести Трансформатор на язык Java, с
целью подключения к распределенной сис-
теме автоматизации проектирования
параллельных алгоритмов ОДСП [12].
Кроме того, планируется адаптация
интерфейса программы для пользователей
с проблемами зрения.
1. Ноден П., Китте К. Алгебраическая
алгоритмика. – М.: Мир. – 1999. – 720 с.
2. Чарнецкий К., Айзенекер У. Порождающее
программирование. Методы, инструменты,
применение. – Изд. дом. Питер, 2005. –
736 с.
3. Глушков В.М. , Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. –
Киев: Наук. думка, 1989. – 328 с.
4. Цейтлин Г.Е. Алгебры Глушкова и теория
клонов // Кибернетика и системный
анализ. – 2003. – № 4. – С. 48–58.
5. Цейтлин Г.Е., Иовчев В.А., Мусихин А.А.
Ментальные аспекты методов символьной
мультиобработки // Проблеми програму-
вання. – 2008. – № 1. – C. 60–67.
6. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П. и
др. Многоуровневое структурное проекти-
рование программ: Теоретические основы,
инструментарий. – М.: Финансы и
статистика, 1989. – 208 с.
7. Цейтлин Г.Е., Суржко С.В., Ющенко К.Л.,
Шевченко А.И. Алгоритмические алгебры.
– Киев: 1997. – 342 с.
8. Цейтлин Г.Е. Конструирование алгорит-
мов символьной обработки // Кибернетика
и системный анализ. – 1993. – № 2 –
С. 17 –30.
Моделі та засоби паралельних і розподілених програм
32
9. Яценко О.А. Інтегровані алгеброалгоритмічні
моделі мультиобробки // Вісн. Київськ.
нац. у-ту. Серія: фіз.-мат. науки. Спец.
випуск за матеріалами Міжнар. конф.
“Теоретичні та прикладні аспекти
побудови програмних систем”
(TAAPSD’2004). – 2004.
10. Яценко Е.А., Мохница А.С. Инструментальные
средства конструирования синтаксически
правильных параллельных алгоритмов и
программ // Проблемы программирования.
Спец. вып. по материалам 4-й Междунар.
научно-практической конф. по
программированию УкрПРОГ'2004. –
2004. – № 2/3. – С. 440–450.
11. Кнут Д. Искусство программирования для
ЭВМ // Сортировка и поиск. – 1978. – Т.3.–
824 с.
12. Дорошенко А.Е., Цейтлин Г.Е., Иовчев В.А.
Высокоуровневые средства автоматизации
проектирования параллельных алгоритмов
// Проблеми програмування. – 2009. – № 3.
– С. 19–30.
13. Цейтлин Г.Е. Проектирование последова-
тельных алгоритмов сортировки: клас-
сификация, трансформация, синтез // Про-
граммирование. – 1989. – № 3. – С. 3–24.
14. Цейтлин Г.Е. Проектирование алгоритмов
параллельной сортировки // Программи-
рование. – 1989. – № 6. – С. 4–19.
15. Цейтлин Г.Е. Проблема тождественных
преобразований схем структурированных
программ с замкнутыми логическими
условиями: ч. 1–3 // Кибернетика. – 1978. –
№ 3. – С. 50–57; № 4. – С. 10–18; 1979. –
№ 5. – С. 44–51.
16. Ющенко Ю.А. Проблема тождественных
преобразований недетерминированных
схем программ в системах алгоритми-
ческих алгебр // Кибернетика. – 1982. –
№ 3. – C. 58–64.
17. Кирсанов Г.М., Цейтлин Г.Е., Ющенко Е.Л.
АНАЛИСТ – пакет программ для
доказательства тождеств теорем в
аксиоматизированных САА // Киберне-
тика. – 1979. – № 4. – C. 28–33.
18. Петрушенко А.Н. Об одном подходе к
проблеме автоматизации оптимизирующих
преобразований алгоритмов и программ //
Кибернетика и системный анализ. – 1991. –
№ 5. – С. 127–137.
19. Панфиленко В.П. Проблема тупиков и
фиктивностей в спецификациях парал-
лельных программ // Кибернетика и сис-
темный анализ. – 1994. – № 5. – С. 142–
153.
20. Мохница А.С. Алгебра алгоритмики и
трансформационная сводимость схем
алгоритмов и программ // Проблемы про-
граммирования. Спец. вып. по материалам
6-й Междунар. научно-практической конф.
по программированию УкрПРОГ'2008. –
2008. – № 2/3. – С. 341–347.
21. Цейтлин Г.Е. Введение в алгоритмику. –
Киев: Сфера, 1998. – 310 с.
Получено 20.10.2009
Об авторах:
Мохница Александр Сергеевич,
младший научный сотрудник
Института программных систем
НАН Украины,
Иовчев Владимир Александрович,
аспирант Института программных систем
НАН Украины,
Андрющенко Екатерина Андреевна,
студентка 6-го курса, факультета
информатики и вычислительной техники
Национального технического
университета Украины «КПИ».
Место работы авторов:
Институт программных систем
НАН Украины,
03680, Киев-187,
Проспект Академика Глушкова, 40,
корп. 5,
Национальный технический университет
Украины «КПИ»,
ул. Политехническая, 41, корп. 18.
e-mail:
mohnitsa@isofts.kiev.ua,
iovchev.v@gmail.com,
ekaterina.andruschenko@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-6577 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T17:44:43Z |
| publishDate | 2009 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Мохница, А.С. Иовчев, В.А. Андрющенко, Е.А. 2010-03-09T12:24:30Z 2010-03-09T12:24:30Z 2009 Особенности реализации средств трансформационного синтеза параллельных алгоритмов / А.С. Мохница, В.А. Иовчев, Е.А. Андрющенко // Пробл. програмув. — 2009. — № 4. — С. 24-32. — Бібліогр.: 31 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/6577 681.3 Рассмотрены особенности реализации средства трансформационного синтеза параллельных алгоритмов с применением последовательной рекурсивной декомпозиции на основе таблиц иерархии. Представлена архитектура соответствующего инструментария (Трансформатор). Розглянуто особливості реалізації засобу трансформаційного синтезу паралельних алгоритмів з застосуванням послідовної рекурсивної декомпозиції на основі таблиць ієрархії. Представлена архітектура відповідного інструментарію (Трансформатор). Paper examines the implementation of tools for transformational synthesis of parallel algorithms, which are using sequential recursive decomposition based on the tables of hierarchy. Architecture of the corresponding toolkit (Transformator) is presented. ru Інститут програмних систем НАН України Моделі та засоби паралельних і розподілених програм Особенности реализации средств трансформационного синтеза параллельных алгоритмов Особливості реалізації засобів трансфор-маційного синтезу паралельних алгоритмів Features of implementation of toolkit for transformational synthesis of parallel algorithms Article published earlier |
| spellingShingle | Особенности реализации средств трансформационного синтеза параллельных алгоритмов Мохница, А.С. Иовчев, В.А. Андрющенко, Е.А. Моделі та засоби паралельних і розподілених програм |
| title | Особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| title_alt | Особливості реалізації засобів трансфор-маційного синтезу паралельних алгоритмів Features of implementation of toolkit for transformational synthesis of parallel algorithms |
| title_full | Особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| title_fullStr | Особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| title_full_unstemmed | Особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| title_short | Особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| title_sort | особенности реализации средств трансформационного синтеза параллельных алгоритмов |
| topic | Моделі та засоби паралельних і розподілених програм |
| topic_facet | Моделі та засоби паралельних і розподілених програм |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6577 |
| work_keys_str_mv | AT mohnicaas osobennostirealizaciisredstvtransformacionnogosintezaparallelʹnyhalgoritmov AT iovčevva osobennostirealizaciisredstvtransformacionnogosintezaparallelʹnyhalgoritmov AT andrûŝenkoea osobennostirealizaciisredstvtransformacionnogosintezaparallelʹnyhalgoritmov AT mohnicaas osoblivostírealízacíízasobívtransformacíinogosintezuparalelʹnihalgoritmív AT iovčevva osoblivostírealízacíízasobívtransformacíinogosintezuparalelʹnihalgoritmív AT andrûŝenkoea osoblivostírealízacíízasobívtransformacíinogosintezuparalelʹnihalgoritmív AT mohnicaas featuresofimplementationoftoolkitfortransformationalsynthesisofparallelalgorithms AT iovčevva featuresofimplementationoftoolkitfortransformationalsynthesisofparallelalgorithms AT andrûŝenkoea featuresofimplementationoftoolkitfortransformationalsynthesisofparallelalgorithms |