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

В работе рассматриваются вопросы создания инструментария, ориентированного на разработку параллельных алгоритмов и программ. Предусматривается реализация системы в распределенной среде, предоставление ей Web-интерфейса и специализация системы в конкретных предметных областях, в которых алгебро-алгор...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2009
Автори:	Дорошенко, А.Е., Цейтлин, Г.Е., Иовчев, В.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут програмних систем НАН України 2009
Теми:	Моделі та засоби паралельних і розподілених програм
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/4420
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов / А.Е. Дорошенко, Г.Е. Цейтлин, В.А. Иовчев // Пробл. програмув. — 2009. — № 3. — С. 19-29. — Бібліогр.: 24 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-4420
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-44202025-02-23T18:06:03Z Высокоуровневые средства автоматизации проектирования параллельных алгоритмов Високорівневі засоби автоматизації проектування паралельних алгоритмів High level facilities for design automation of parallel programs Дорошенко, А.Е. Цейтлин, Г.Е. Иовчев, В.А. Моделі та засоби паралельних і розподілених програм В работе рассматриваются вопросы создания инструментария, ориентированного на разработку параллельных алгоритмов и программ. Предусматривается реализация системы в распределенной среде, предоставление ей Web-интерфейса и специализация системы в конкретных предметных областях, в которых алгебро-алгоритмические спецификации и превращения алгоритмов объединены с мощными средствами автоматизации и синтеза программ на основе Web 2.0. У роботі розглядаються проблеми створення інструментарію, що орієнтований на розробку паралельних алгоритмів та програм. Передбачається реалізація системи у розподіленому середовищі, надання їй Web-інтерфейсу та спеціалізації системи у конкретних предметних областях, в яких алгебро-алгоритмічні специфікації та перетворення алгоритмів об'єднано з потужними засобами автоматизації та синтезу програм на основі Web 2.0. particular subject domains in which algebraic-algorithmic specifications and transformations of algorithms are incorporated with powerful facilities of automation and synthesis of the programs on the basis of Web 2.0. 2009 Article Высокоуровневые средства автоматизации проектирования параллельных алгоритмов / А.Е. Дорошенко, Г.Е. Цейтлин, В.А. Иовчев // Пробл. програмув. — 2009. — № 3. — С. 19-29. — Бібліогр.: 24 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/4420 681.03 ru application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Моделі та засоби паралельних і розподілених програм Моделі та засоби паралельних і розподілених програм
spellingShingle	Моделі та засоби паралельних і розподілених програм Моделі та засоби паралельних і розподілених програм Дорошенко, А.Е. Цейтлин, Г.Е. Иовчев, В.А. Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
description	В работе рассматриваются вопросы создания инструментария, ориентированного на разработку параллельных алгоритмов и программ. Предусматривается реализация системы в распределенной среде, предоставление ей Web-интерфейса и специализация системы в конкретных предметных областях, в которых алгебро-алгоритмические спецификации и превращения алгоритмов объединены с мощными средствами автоматизации и синтеза программ на основе Web 2.0.
format	Article
author	Дорошенко, А.Е. Цейтлин, Г.Е. Иовчев, В.А.
author_facet	Дорошенко, А.Е. Цейтлин, Г.Е. Иовчев, В.А.
author_sort	Дорошенко, А.Е.
title	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
title_short	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
title_full	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
title_fullStr	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
title_full_unstemmed	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов
title_sort	высокоуровневые средства автоматизации проектирования параллельных алгоритмов
publisher	Інститут програмних систем НАН України
publishDate	2009
topic_facet	Моделі та засоби паралельних і розподілених програм
url	https://nasplib.isofts.kiev.ua/handle/123456789/4420
citation_txt	Высокоуровневые средства автоматизации проектирования параллельных алгоритмов / А.Е. Дорошенко, Г.Е. Цейтлин, В.А. Иовчев // Пробл. програмув. — 2009. — № 3. — С. 19-29. — Бібліогр.: 24 назв. — рос.
work_keys_str_mv	AT dorošenkoae vysokourovnevyesredstvaavtomatizaciiproektirovaniâparallelʹnyhalgoritmov AT cejtlinge vysokourovnevyesredstvaavtomatizaciiproektirovaniâparallelʹnyhalgoritmov AT iovčevva vysokourovnevyesredstvaavtomatizaciiproektirovaniâparallelʹnyhalgoritmov AT dorošenkoae visokorívnevízasobiavtomatizacííproektuvannâparalelʹnihalgoritmív AT cejtlinge visokorívnevízasobiavtomatizacííproektuvannâparalelʹnihalgoritmív AT iovčevva visokorívnevízasobiavtomatizacííproektuvannâparalelʹnihalgoritmív AT dorošenkoae highlevelfacilitiesfordesignautomationofparallelprograms AT cejtlinge highlevelfacilitiesfordesignautomationofparallelprograms AT iovčevva highlevelfacilitiesfordesignautomationofparallelprograms
first_indexed	2025-11-24T07:34:43Z
last_indexed	2025-11-24T07:34:43Z
_version_	1849656274532171776
fulltext	Моделі та засоби паралельних і розподілених програм 19 УДК 681.03 А.Е. Дорошенко, Г.Е. Цейтлин, В.А. Иовчев ВЫСОКОУРОВНЕВЫЕ СРЕДСТВА АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ В работе рассматриваются вопросы создания инструментария, ориентированного на разработку парал- лельных алгоритмов и программ. Предусматривается реализация системы в распределенной среде, предоставление ей Web-интерфейса и специализация системы в конкретных предметных областях, в которых алгебро-алгоритмические спецификации и превращения алгоритмов объединены с мощными средствами автоматизации и синтеза программ на основе Web 2.0. Введение Появление новых архитектур мик- ропроцессоров (таких как мультиядерных), а также новых классов и вычислительных систем (таких как кластеры, Р2Р, Грид- системы) обнаружило новые возможности для параллельных вычислений, и соответ- ственно, привело к потребности создания специальных инструментов для разработки (параллельного) программного обеспече- ния таких систем. Главным источником увеличения производительности программ для таких систем, как и раньше, остается эффективное использование возможностей распараллеливания операций. А именно операций разных уровней выполнения вы- числений в программах. Но проблема за- ключается не только в потребности созда- ния инструментов, которые конструируют новые классы параллельных программ, но и в обеспечении возможностей гибкого проектирования таких программ для их быстрой реинженерии на другие платформы. Индустриальный опыт параллель- ного программирования ориентирует ко- нечного пользователя на использование низкоуровневых средств на уровне языка программирования. Низкоуровневые инст- рументы обычно эффективны, однако их широкое применение вряд ли возможно именно ввиду их низкоуровневой приро- ды, поскольку они требуют много ручной работы и достаточно высокой квалифика- ции программиста. Фокусируя внимание на конечном этапе разработки – кодировке программы на языке программирования – эти средства лишь идентифицируют про- блемы и после анализа, и тестирования программы требуют повторного ручного изменения кода начальной программы для того, чтобы проанализировать его опять для нахождения новых ошибок и дефектов. Главные усилия исследователей в решении проблем мультипоточного про- граммирования, в настоящее время скон- центрированы на изобретении некоторых “простых и практических” общих меха- низмов, которые позволили бы решить во- прос мультиядерного выполнения про- грамм “почти” автоматически. Несмотря на рациональность этих подходов и при- меры их успешного применения, они не стали панацеей для универсального реше- ния названных проблем в силу того, что разработка эффективных программ для мультиядерной архитектуры оказалась очень сложной и масштабной научно- технической проблемой. Очевидно, их ус- пешное решение возможно на пути посте- пенного углубления и охвата этапов жиз- ненного цикла разработки программы с применением средств автоматизированного проектирования и программирования, от написания первичных спецификаций к ге- нерации выполняемого кода программы. Такой же, основанный на привлечении широких инженерных знаний о проекти- руемой распределенной системе, путь ка- жется перспективным и для автоматизации разработки параллельных кластерных сис- тем и Грид-программ. В Институте программных систем НАН Украины на протяжении длительного периода развивается теория, методология и инструментарий (система ИПС) для ав- томатизированного проектирования па- раллельных программ, основанные на © А.Е. Дорошенко, Г.Е. Цейтлин, В.А. Иовчев, 2009 ISSN 1727-4907. Проблеми програмування. 2009. № 3 Моделі та засоби паралельних і розподілених програм 20 средствах высокоуровневой алгебро- алгоритмической формализации и автома- тизации превращений программ [1–5]. Разработана экспериментальная инстру- ментальная система для конструирования и оптимизации параллельных программ [6–8]. Другая система символьных вычис- лений TermWare, создана на основе пара- дигмы переписывающих правил, дополня- ет возможности системы ИПС и использу- ется для автоматизации инженерии про- граммного кода параллельных программ [9–10]. Разрабатываемый ныне инстру- ментарий системы ИПС предназначен для проектирования параллельных программ для современных сред выполнения, в ко- торых алгебро-алгоритмические специфи- кации и превращения алгоритмов объеди- нены с мощными средствами автоматиза- ции и синтеза программ на основе Web 2.0. Отметим, что под современными средами выполнения понимаются мультиядерные, мультипотоковые, кластер, Грид-системы, облачные системы и т.д. Изложение материала работы под- чинено следующей структуре. В разделе 1 рассматривается использование равносиль- ных форм проектирования алгоритмов и программ. В разделе 2 изложена сущность аппарата ГСП, сочетающего понятия САА- М с проектированием алгоритмов в терми- нах грамматического вывода. Раздел 3 по- священ проектированию и синтезу парал- лельных объектно-ориентированных про- грамм. В разделе 4 приведена архитектура онлайнового инструментального средства проектирования алгоритмов и программ. Раздел 5 завершает работу описанием ре- зультатов и перспектив. 1. Использование равносильных форм проектирования алгоритмов и программ Примером открытых систем схем- ного проектирования классов алгоритмов и программ является синтезатор МУЛЬТИПРОЦЕССИСТ [11]. Данная сис- тема, используя алгоритмические проекты, оформленные на языке САА-схем, генери- рует тексты программ на целевых языках программирования (Ассемблер, Си, Пас- каль и др.). САА-схемы представляют со- бой естественно-лингвистические проекты алгоритмов, в основу которых положен аппарат систем алгоритмических алгебр (САА) Глушкова. В Украине первая алгеб- ра программ была построена В.М. Глуш- ковым в рамках работ по системам алго- ритмических алгебр [1] в середине 60-х годов, за несколько лет до того, как задача построения подобной алгебры была пред- ложена Э. Дейкстрой. Более того, еще в 1959 году в [12] Л.А. Калужнин предложил алгебру граф-схем как инструмент для ма- тематизации программирования, которая и стала отправной точкой для создания САА. В 1982 году была создана система синтеза программ МУЛЬТИПРОЦЕССИСТ [11, 13], в качестве входного языка была использована параллельная модификация САА– САА-М. Рассматриваемый инструментарий (в отличие от системы МУЛЬТИПРОЦЕССИСТ) состоит в интеграции всех трех представ- лений алгоритма [2]: аналитического (формула в избранной алгебре), естествен- но-лингвистического (САА-схемы) и гра- фового (граф-схемы Калужнина) при его конструировании. Аналитическое представление, как известно, базируется на алгебрах и являет- ся компактной записью алгоритма, на- правленной на его дальнейшее преобразо- вание (минимизация, оптимизация по раз- ным критериям) на базе аппарата соотно- шений и тождеств, развитых в алгебрах. Естественно-лингвистическое пред- ставление (в виде текста), также базирует- ся на аппарате алгебр, в процессе модифи- кации с помощью метаправил декомпози- руется на инвариантную часть (неинтер- претированную схему), которая представ- ляет собою верхний уровень проекта и собственно интерпретации (нижний уро- вень), зависящие от избранной предметной области. После свертки инвариантная часть может быть снова проинтерпретиро- вана, но уже с помощью других средств нижнего уровня. Графовое представление, главное преимущество которого – наглядность, также опирается на аппарат алгебр и ори- ентировано на визуализацию конструи- руемого алгоритма. Основой для построе- Моделі та засоби паралельних і розподілених програм 21 ния этого представления (для аналитиче- ского также) может быть выбрана инвари- антная часть САА-схемы с дальнейшей интерпретацией в соответствии c избран- ным нижним уровнем. Пример 1. Проблема синтаксиче- ского анализа состоит в установлении пра- вильности обрабатываемых символьных цепочек - их принадлежность к соответст- вующему входному языку (задача контро- ля) и определение синтаксической струк- туры анализируемых цепочек (задача ана- лиза). Для решения проблемы синтаксиче- ского анализа представлен известный метод Кока – Янгера – Касами (Cocke – Younger – Kasami), использующий контекстно- свободные грамматики, представленные в бинарной форме, для описания формальных языков. В качестве результата получаем ответ на вопрос, выводима или нет анали- зируемая терминальная цепочка символов в данной грамматике [14–16]. Алгоритм принимает на вход грамматику в бинарной форме. Заметим, что исходная грамматика не содержит бесполезных символов, это является обычным требованием к грамма- тикам, попадающим на вход алгоритмов синтаксического анализа. Последовательный CYK алгоритм затрачивает на разбор строки длинной n время O(n2,83) и память емкостью n2 на модели RAM [5]. Метод гарантирует вы- полнение той же работы для произвольной грамматики за время, пропорциональное кубу длины входной цепочки и, таким об- разом, является одним из методов «дина- мического программирования», где вы- числение последующих шагов опирается на значение, полученные на предыдущих. CYK алгоритм строит множества нетер- миналов, соответствующих некоторым участкам входной строки и, в результате, отвечает на вопрос, выводима ли данная строка в данной грамматике или нет. Метод работает следующим обра- зом. Пусть G(N,T,P,@) – КС-грамматика без e-правил в бинарной форме. Простое обобщение алгоритма работает и для грамматик, не находящихся в этой форме. Пусть w = a1…an – входная строка, которую нужно разобрать согласно грам- матике G. Предполагается, что ai принад- лежит T для 1 <= i <= n . Суть алгоритма состоит в построении треугольной табли- цы разбора, элементы которой обозначим Rij, где 1 <= j <= n – i + 1. Значениями элементов Rij будут подмножества множе- ства N. Нетерминальный символ A будет принадлежать Rij в случае, когда A →+ aiai+1…ai+j-1 , т.е. когда из A выводят- ся j входных символов, начиная с позиции i. В частности, входная строка w принад- лежит языку L(G) только в том случае, ес- ли @-аксиома принадлежит R1n. Таким образом, чтобы выяснить принадлежит ли строка w языку L(G), CYK-алгоритм вычисляет таблицу разбора для w и анализирует, принадлежит ли @-аксиома ее элементу R1n. При параллельном вычислении таб- лицы эффективно используется стратегия двусторонней символьной мультиобработ- ки. Естественно-лингвистическое пред- ставление последовательного CYK алго- ритма имеет вид: СХЕМА CYK==== "САА схема последовательного CYK ал- горитма" КОНЕЦ КОММЕНТАРИЯ "CYK" ===="СТАРТ" ЗАТЕМ ЦИКЛ ПОКА НЕ ‘Обработаны все диагонали (d = 1, …, n)’ ВЫЧИСЛИТЬ_ДИАГОНАЛЬ(d) КОНЕЦ ЦИКЛА ЗАТЕМ ЕСЛИ ‘Аксиома принадлежит элементу R[n, 1]’ ТОГДА СООБЩЕНИЕ «входная цепочка правильна» ИНАЧЕ СООБЩЕНИЕ «входная цепочка не правильна» КОНЕЦ ЕСЛИ ЗАТЕМ "ФИН" "ВЫЧИСЛИТЬ_ДИАГОНАЛЬ (d)" ===="СТАРТ" ЦИКЛ Моделі та засоби паралельних і розподілених програм 22 ПОКА НЕ ‘Обработаны все элементы диа- гонали (k = 1, …, n– d + 1)’ ВЫЧИСЛИТЬ_ЭЛЕМЕНТ(d, k) КОНЕЦ ЦИКЛА ЗАТЕМ "ФИН" "ВЫЧИСЛИТЬ_ЭЛЕМЕНТ (i, j)" ===="СТАРТ" ЗАТЕМ “Элемент R[i, j] = 0” ЗАТЕМ ЕСЛИ ‘Вычисление первой строки (i = 1)’ ТОГДА ЦИКЛ ПОКА ‘Существует правило A > aj’ “Поместить A в элемент R[i, j]” КОНЕЦ ЦИКЛА ИНАЧЕ “Установить указатель k на пер- вую диагональ (k = 1)” ЗАТЕМ ЦИКЛ ПОКА НЕ ‘Указатель k достиг i-ой диаго- нали’ ЦИКЛ ‘Для каждого нетерминала B из элемента R[k, j]’ ЦИКЛ ‘Для каждого нетерминала C из элемента R[i - k, j + k]’ ЕСЛИ ‘Если существует правило A > BC’ ТОГДА “Поместить A в элемент R[i, j]” КОНЕЦ ЕСЛИ КОНЕЦ ЦИКЛА КОНЕЦ ЦИКЛА КОНЕЦ ЦИКЛА КОНЕЦ ЕСЛИ ЗАТЕМ "ФИН" КОНЕЦ СХЕМЫ Аналитическое представление ал- горитма имеет следующий вид: CYK алгоритм = {[u1] B} * ([u2] A1, A2) u1 – условие: Обработаны все диа- гонали; B – оператор: ВЫЧИСЛИТЬ_ДИАГОНАЛЬ; u2 – условие: Аксиома принадлежит элементу R[n, 1]; A1 – СООБЩЕНИЕ «входная це- почка правильна»; A2 – оператор: СООБЩЕНИЕ «входная цепочка не правильна»; B = {[v1] C} v1 – условие: Обработаны все эле- менты диагонали; C – оператор: ВЫЧИСЛИТЬ_ЭЛЕМЕНТ; C = C1([w1] {[w2] C2}, C3 {[w3] {[w4] {[w5] ([w6] C4, E)}}}) C1 – оператор: Элемент R[i, j] = 0; w1 – условие: Вычисление первой строки; w2 – условие: Существует правило A > aj; C2 – оператор: Поместить A в эле- мент R[i, j]; C3 – оператор: Установить указа- тель k на первую диагональ; w3 – условие: Указатель k достиг i-ой диагонали; w4 – условие: Для каждого нетер- минала B из элемента R[k, j]; w5 – условие: Для каждого нетер- минала C из элемента R[i - k, j + k]; w6 – условие: Если существует пра- вило A > BC’; C4 – оператор: Поместить A в эле- мент R[i, j]”; E – оператор: Пустой. Граф-схема последовательного CYK алгоритма показана на рис. 1, и 2 ВЫЧИСЛИТЬ ДИАГОНАЛЬ (d), на рис. 3 ВЫЧИСЛИТЬ ЭЛЕМЕНТ (i, j): Рис. 1 Моделі та засоби паралельних і розподілених програм 23 Рис. 2 Рис. 3 СХЕМА CYK==== "САА схема CYK алгоритма синхронного вычисления элементов диагоналей" КОНЕЦ КОММЕНТАРИЯ "CYK" ===="СТАРТ" ЗАТЕМ ЦИКЛ ПОКА НЕ ’Обработаны все диагонали’ “Распределить количество элемен- тов, обрабатываемой диагонали, по n по- токам” ЗАПУСТИТЬ ВЕТВЬ(1, 2, ..., n) ОЖИДАТЬ ‘Все ветви обработали выде- ленные им элементы’ КОНЕЦ ЦИКЛА ЗАТЕМ “Проверить наличие аксиомы в элементе R[n, 1]” ЗАТЕМ "ФИН" "ЗАПУСТИТЬ ВЕТВЬ(i)" ===="СТАРТ" ЗАТЕМ ЦИКЛ ПОКА НЕ ‘Вычислены все элементы, вы- деленные для обработки’ “Вычислить элемент” КОНЕЦ ЦИКЛА "ФИН" КОНЕЦ СХЕМЫ В приведенной схеме выполняется равномерное распределение элементов, обрабатываемой диагонали, по всем пото- кам. Распределение предполагается прово- дить по следующей формуле: array[index] = count DIV proc; если index <= (count MOD proc), то- гда array[index] = array[index] + 1; где array – массив, в котором хра- нятся количества обрабатываемых элемен- тов, для каждого потока; index – порядко- вый номер потока; count – количество эле- ментов на обрабатываемой диагонали; proc – количество потоков; Аналитическое представление ал- горитма имеет следующий вид: CYK алгоритм = {[u] A1 * B \|\| C * S(v)} *A2 B = C = {[w] B1} u – условие: Обработаны все диаго- нали; Моделі та засоби паралельних і розподілених програм 24 v – условие: Все ветви обработали выделенные им элементы; w – условие: Вычислены все эле- менты, выделенные для обработки; A1 – оператор: Распределить коли- чество элементов, обрабатываемой диаго- нали, по n потокам; B, C – оператор: Запустить ветвь (i); A2 – оператор: Проверить наличие аксиомы в элементе R[n, 1]; B1 – оператор: Вычислить элемент. Граф-схема CYK алгоритма син- хронного вычисления элементов диагона- лей показана на рис. 4 и ЗАПУСТИТЬ ВЕТВЬ(i) на рис. 5. Рис. 4 Рис. 5 Использование в инструментарии всех трех форм представления дает более полную картину о конструируемом алго- ритме, чем любое из них по отдельности. Соответственно, что изменение любого из этих представлений в инструментарии ав- томатически приведет к соответствующе- му преобразованию остальных. 2. Грамматики структурного проектирования В основу проектирования алгорит- мов в алгебре алгоритмики положена кон- цепция матричных грамматик структурно- го проектирования, которые совмещают аппарат САА-M с теорией языковых муль- типроцессоров. Грамматики структурного проектирования (ГСП) [16, 17] были ори- ентированы на решение важных проблем синтаксиса (описание синтаксически пра- вильных цепочек), семантики (описание не только синтаксически, но и семантически правильных цепочек языка) и прагматики (практическое применение аппарата ГСП для разработки ряда конкретного про- граммного обеспечения). Под ГСП будем понимать некую формальную систему G = (T, N, R, Р, U), составляющими которой являются сле- дующие компоненты: • T – терминальный алфавит; • N – нетерминальный алфавит, кото- рому принадлежат метапеременные логиче- ские, операторные, объектные, АТД, АТП, характеризующие разные уровни проекти- рования; Моделі та засоби паралельних і розподілених програм 25 • U – механизм управления выво- дом; • R – принадлежит нетерминаль- ному алфавиту, это аксиома которая идентифицирует проектированный класс; • P – совокупность помеченных постановок логического, операторного, объектного типов, детализирующие АТП, АТД и используются при проекти- ровании алгоритмов и программ. Рассматриваемые терминальный алфавит, состоящий из совокупности ба- зисных условий, операторов, объектов, абстрактный тип данных (АТД), абст- рактный тип памяти (АТП), опреде- ляющие степень конкретизации проек- тированного класса алгоритмов и про- грамм. А так же совокупность разделите- лей – символов операций сигнатуры САА-М, скобок, ограничителей и др. Проектируемый класс программ L(G) = {X \| R => X} подмножество F(T), которые выводятся из аксиомы в ГСП, создает ассоциированный с классом язык, который порожден данной грамма- тикой. С помощью механизма U последо- вательного, параллельного или ком- бинированного управления выводом в ГСП, реализуются контекстные зависи- мости по памяти и данным между про- ектируемыми программными модулями. Следует заметить, что аппарат ГСП положе- но в основу метода МСПП и его инструмен- тария – системы МУЛЬТИПРОЦЕССИСТ. В развиваемом инструментарии в основу решения проблемы проектирования сложных программ, положены матричные ГСП (включая и метаправила их конструи- рования). С последовательным, парал- лельным или комбинированным примене- нием подстановок в обобщенных матрич- ных продукциях. При этом подстановки, которые применяются последовательно, записываются в строку и разделяются точ- кой с запятой, а параллельно – в столбец. Пример 2. Проиллюстрируем про- цесс взаимосвязанного проектирования структур управления, памяти и данных на примере вышеописанного CYK алгоритма синхронного вычисления элементов диа- гоналей с применением основы матричных ГСП. А именно П-программы которая по- рождает разные классы многоуровневых алгоритмов и программ [16, 17]. Суть мно- гоуровневой обработки состоит в распре- делении обрабатываемой диагонали на по- парно непересекающиеся подмассивы для одновременной обработки по параллель- ным ветвям Аi, и в дальнейшем получе- ниями промежуточных результатов. При этом воспользуемся параметрическим опи- санием продукций, который обеспечивает саморедактирование ГСП, поданной в схематической форме: наращивание па- раллельных ветвей и ассоциированных с ними переменных МАСі и Ф, выполняется с помощью изменения параметра і от і=1 до і = n. Схема ГСП П-Программы состоит из таких обобщенных матричных продукций: m0: R –> ПРС(МАС) x СБОРКА(Ф) МАС –> МАС1, МАС m1: ПРС –> А1(t) v ПРС; t –> МАС1 Ф –> Ф1, Ф МАС –> МАСі+1, МАС m2: Аі(МАСі) v ПРС –>Аі(МАСі) v Аі+1(t) v ПРС t –> МАСі+1 Ф –> Фі+1, Ф МАС –> МАСі+1 m3: Аі(МАСі) v ПРС –>Аі(МАСі) v Аі+1(t) t –> МАСі+1 Ф –> Ф і+1 Подключая к продукциям ГСП П- программы матричные продукции m3, m4 получаем ГСП порождающую алгоритм синхронного вычисления элементов диа- гоналей: m3: Ai(MACi)-> Вычислить элемент(MACi), MACi->Mi,Ф->Li m4: СБОРКА(L1,..,Lk)->Проверить наличие аксиомы в элементе(L1,..,Lk) где, «Вычислить элемент» и «Про- верить наличие аксиомы в элементе» – вышеспроектированы в разд. 1 Mi – часть диагонали обрабатываемая за Аi веткой, Li – обработанная часть диагонали за Аi вет- вью. «Проверить наличие аксиомы в эле- менте (L1,..,Lk)» – поиск аксиомы. В результате, имея вначале после- довательный алгоритм синтаксического анализа со сложностью n2,83 [15], получаем Моделі та засоби паралельних і розподілених програм 26 параллельный алгоритм синхронного вы- числения элементов диагоналей с линей- ной сложностью 2(n–1) [14] на модели PRAM [5]. 3. Средства проектирования и синтеза параллельных объектно- ориентированных программ Использование аппарата алгебры при разработке программного обеспечения является богатым источником для иссле- дования, благодаря его мощным матема- тическим основам, мощным средствам для использования абстракций программ и программных преобразований. В проекти- ровании параллельного программного обеспечения алгебраическая техника часто и прежде всего, используется для соответ- ствующей декомпозиции предметной об- ласти, с целью получения необходимых алгоритмических структур зависимостей в этой области. Для накопления и использо- вания знаний о предметной области, воз- можности манипулирования проблемно ориентированными объектами и автомати- зации генерации программного кода ис- пользуется алгебра алгоритмов [1–4], где детально разрабатываются полезные про- блемно ориентированные наборы действий, условий и абстракций для поддержки эта- пов жизненного цикла проектирования программного обеспечения. Главная идея использования алгеб- ры алгоритмов для проектирования про- грамм заключается в пошаговом описании схем алгоритмов сверху вниз, детализируя операции в терминах САА-М [3, 4]. На каждом шаге проектирования, система в диалоге с пользователем позво- ляет ему выбирать только те действия, вы- полнение которых в дереве алгоритма не нарушает синтаксической корректности схемы. После того, как алгоритм разрабо- тан, диалоговый конструктор может вы- полнять синтез программы. Это осуществ- ляется путем реализации элементарных операторов и условий на целевом языке программирования, а также других про- граммных фрагментов в дереве алгоритма. В процессе синтеза управляющие конст- рукции схемы отображаются в соответст- вующие операторы языка программирова- ния, а вместо базисных элементов под- ставляются их реализации на этом же язы- ке. На вход синтезатора поступает инфор- мация из базы данных алгебраических описаний, содержащий каркасное описа- ние основного класса приложения (без реализаций методов), в который выполня- ется подстановка синтезированного кода [18, 19]. База данных алгебраических описа- ний инструментария разработчика содер- жит следующие компоненты: 1) стратегии обработки (регулярные схемы, которые представляют классы ал- горитмов); 2) базовые предикаты и операторы, представленные в трех формах (алгебраи- ческой, естественно-лингвистической и графовой) и их реализация на необходи- мом целевом языке программирования; 3) метаправила для проектирования схем алгоритмов; 4) прикладные алгоритмы; 5) распределенные гиперсхемы. Базовые инструментальные средст- ва разработчика обеспечат основу для ви- зуального проектирования граф-схем ал- горитмов путем интерактивного конструи- рования синтаксически правильных про- грамм. В разрабатываемом инструмента- рии будут реализованы средства парамет- рического управления генерацией САА- схем на основе схем высшего уровня (ги- персхем) [7, 11, 20]. 4. Архитектура онлайнового инструментального средства проектирования параллельных и распределенных алгоритмов и программ Предлагаемый инструментарий со- стоит из компонентов, показанных на рис. 6. Как упоминалось ранее, с помощью инструментария осуществляется диалого- вое проектирование и синтез объектно- ориентированных параллельных алгорит- мов и программ с использованием элемен- тов базы знаний. А так же их последующая отладка, эксплуатация, реинженерия и т.д. Моделі та засоби паралельних і розподілених програм 27 Рис. 6 Отметим, что компоненты инстру- ментария автономны [21], гибко связанны и имеют согласованный протокол обмена данными, т. е. данная модель, по сути, яв- ляется сервисно-ориентированной [22]. Клиент представляет собой интер- фейс для диалогового взаимодействия пользователя с инструментарием и его ре- сурсами. А именно возможность проекти- рования последовательного или парал- лельного алгоритма в вышеупомянутых формах и синтеза исходного кода в целе- вом языке программирования, а так же его дальнейшей эксплуатации (запуск в дос- тупных современных вычислительных средах, распараллеливание и другое). Диспетчер – ядро инструментария, организовывающее связь между базой данных, генератором, расширениями, с помощью шлюза, с современными средами выполнения и пользователями (посредст- вом клиентов). Организовывает проекти- рование, синтез и выполнение (отладка, реинженерия) параллельных программ в современных средах выполнения. База данных состоит из: базы алго- ритмических знаний инструментария и технической базы данных. База алгоритмических знаний инст- рументария вмещает следующие разделы: • схемы алгоритмов (разработанные ал- горитмы из разных предметных областей); • стратегии обработки (схемы, которые описывают классы алгоритмов и подлежат дальнейшей детализации); • метаправила свертки, развертки и трансформации (обеспечивают абстраги- рование, детализацию и переинтерпрета- цию схем, а также содержат тождества и соотношения для преобразования схем); Моделі та засоби паралельних і розподілених програм 28 • базисные понятия и их программные реализации (ориентированные на проекти- рование алгоритмов и синтез программ в данной предметной области на избранном целевом языке); • графические элементы, используемые для представления граф-схем алгоритмов (различные виды стрелок, блоков и др.). Техническая база данных содержит настройки и данные пользователей инст- рументария, о зарегистрированных сред выполнения, расширений, а также на- стройки и стратегии работы инструмента- рия в целом. Генератор – это сервис, осуществ- ляющий синтез программ. А именно, по дереву, полученному в процессе конструи- рования алгоритмов, реализациями эле- ментарных операторов и условий целевого объектно-ориентированного языка про- граммирования и другими фрагментами. Интерфейс расширений – это сер- вис, ориентированный на расширение воз- можностей инструментария путем вклю- чения дополнительных сервисов для рабо- ты с алгоритмами и программами. На при- мер, оценка сложности алгоритма [23]. Редактор граф-схем ориентирован на визуальное представление алгоритмов. При этом изменения, внесенные во время редактирования, соответствующим обра- зом отобразятся на другие представления алгоритма. Параметрически управляемый гене- ратор САА-схем [24] ориентирован на синтез схем алгоритмов и программ. Посредством спецификаций более высокого уровня, назы- ваемых регулярными гиперсхемами (РГС) [11, 20]. РГС применяются, в частности, для представления алгоритмов управления выво- дом в грамматиках структурного проектиро- вания (ГСП) [16, 17]. Проектирование ги- персхем, как и САА-схем, выполняется в диалоговом режиме. Распараллеливатель – это сервис, ориентирован на реинженерию последова- тельных алгоритмов и программ с целью получения их параллельных версий. Шлюз – это сервис, обеспечиваю- щий запуск, анализ и получение результа- тов выполнения программ в современных средах выполнения. Заключение В данной работе предлагается кон- цепция развития инструментария, ориен- тированного на разработку параллельных алгоритмов и программ для современных параллельных сред выполнения. В основу проектирования алгоритмов в этом инст- рументарии положен аппарат алгебры ал- горитмики, а именно концепция грамматик структурного проектирования, которая со- вмещает модифицированные системы ал- горитмических алгебр с теорией языковых мультипроцессоров. Языковые мультипроцессоры спро- ектированы в форме грамматик структур- ного проектирования. В частности для ме- тода Кока – Янгера – Касами использова- ны матричные ГСП. Спроектирована архи- тектура онлайнового инструментального средства проектирования параллельных и распределенных алгоритмов. 1. Gluschkow, W.M., Zeitlin, G.E., Justchenko, J.L. Algebra. Sprachen. Programmierung. Akademie-Verlag, Berlin, 1980. – 340 p. 2. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера. – 1998. – 310 с. 3. Doroshenko A., Tseitlin G. Models and Paral- lel Programming Abstractions to Enhance Concurrency of Parallel Programs, Funda- menta Informaticae. – 2004. – Vol. 60, N. 1-4. – Р. 99–111. 4. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгеброалгоритмические модели и методы параллельного програм- мирования. – Киев: Академпериодика, 2007. – 634 с. 5. Дорошенко А.Е.. Математические модели и методы организации высокопроизводитель- ных параллельных вычислений. Алгеброди- намический подход. – Киев: Наук. думка, 2000. – 177 с. 6. Цейтлин Г.Е., Яценко Е.А. Элементы ал- гебраической алгоритмики и объектно- ориентированный синтез параллельных программ // Математические машины и системы. – 2003. – № 2. – С. 64–76. 7. Яценко Е.А. Алгебры гиперсхем и интегриро- ванный инструментарий синтеза программ в современных объектно-ориентированных средах // Кибернетика и системный анализ. – 2004. – № 1. – С. 47 – 52. Моделі та засоби паралельних і розподілених програм 29 8. Яценко О.А. Середовище конструювання алгоритмічних знань та інструментарій синтезу програм // Проблеми програму- вання. — 2006. — № 2-3. — С. 349–359. 9. Doroshenko, A.E., Shevchenko, R. A Rewrit- ing Framework for Rule-Based Programming Dynamic Applications // Fundamenta Infor- maticae. – 2006. – 72. – Р. 95–108. 10. TermWar – http://www.gradsoft.com.ua/ products/termware_rus.html 11. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий. – М.: Финансы и статистика, 1989. – 208 с. 12. Калужнин Л.А. Об алгоритмизации мате- матических задач // Проблемы кибернети- ки. – 1959. – Вып. 2. – С. 51–69. 13. Ющенко Е.Л., Цейтлин Г.Е., Галушка А.В. Алгебро-грамматические спецификации и синтез структурированных схем программ // Кибернетика. – 1989. – № 6. – С. 5–16. 14. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Методы символьной мультиобработки. – Киев: Наук. думка, 1980. – 252 с. 15. Янгер Д.Х. Распознавание и анализ контек- стно-свободных языков за время n3 // Про- блемы математической логики. – М.: Мир, 1970. – С. 344–362. 16. Цейтлин Г.Е., Иовчев В.А., Мусихин А.А. Ментальные аспекты методов символьной мультиобработки // Проблеми програму- вання. – 2008. – № 1. – Р. 60–67. 17. Цейтлин Г.Е., Суржко С.В., Ющенко К.Л., Шевченко А.И. Алгоритмические алгебры. – Киев, 1997. – 342 с. 18. Яценко Е.А., Мохница А.С. Инструменталь- ные средства конструирования синтаксиче- ски правильных параллельных алгоритмов и программ // Проблемы программирования. – 2004. – № 2-3. – С. 444 – 450. 19. Цейтлин Г.Е., Яценко Е.А. Элементы ал- гебраической алгоритмики и объектно- ориентированный синтез параллельных программ // Математические машины и системы. – 2003. – № 2. – С. 64 – 76. 20. Цейтлин Г.Е. Алгебры Глушкова и теория клонов // Кибернетика и системный ана- лиз. – 2003. – № 4. – С. 48–58. 21. IBM Autonomic Computing. — http://www.research.ibm.com/autonomic/ 22. Дорошенко А.Е., Алистратов О.В., Тырчак Ю.М., Розенблат А.П. Системы GRID- вычислений — перспектива для научных исследований // Проблеми програмування. – 2005. – № 1. – Р. 14–38. 23. Дорошенко А.Е., Жереб К.А., Яценко Е.А. Об оценке сложности и координации вы- числений в многопоточных программах // Проблеми програмування. – 2007. – № 2. – С. 41–55. 24. Яценко Е.А. Алгебры гиперсхем и интегри- рованный инструментарий синтеза программ в современных объектно-ориентированных средах. // Кибернетика и системный анализ. – 2004. – № 1. – С. 47–52. Получено 19.06.2009 Об авторах: Дорошенко Анатолий Ефимович, доктор физико-математических наук, профессор, заведующий отделом теории компьютерных вычислений, Цейтлин Георгий Евсеевич, доктор физико-математических наук, профессор, ведущий научный сотрудник, Иовчев Владимир Александрович, аспирант Института программных систем НАН Украины. Место работы авторов: Институт программных систем НАН Украины, 03680, Киев-187, Проспект Академика Глушкова, 40. e-mail: dor@isofts.kiev.ua, tseytlin@vikno.relc.com, iovchev.v@gmail.com

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

Репозитарії

Схожі ресурси