1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр




Скачать 223.15 Kb.
Название1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр
Дата публикации02.03.2013
Размер223.15 Kb.
ТипДокументы
uchebilka.ru > Химия > Документы

Інструментальні засоби і середовища програмування




УДК 681.3
А.Е. Дорошенко, Е.А. Яценко
О синтезе программ на языке Java
по алгеброалгоритмическим спецификациям

Рассмотрены средства алгоритмических описаний для представления последовательных и асинхронных алгоритмов для их формализованного проектирования. Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программирования. Описан метод синтеза многопоточных программ на языке Java по схемам асинхронных алгоритмов.

Введение


Важной проблемой современного программирования является его математи­зация, разработка формализованных языков проектирования алгоритмов и программ, а также их абстрактных моделей. К средст­вам, ориентированным на решение проблем формализации, обоснования правильности, улучшения алгоритмов (по выбранным кри­териям) принадлежат алгебры алгоритмов. Украинской кибернетической школой вне­сен значительный вклад в разработку алгебр алгоритмов фундаментальными работами В.М. Глушкова, в русле которых была по­строена теория систем алгоритмических ал­гебр (САА) и их модификаций [1]. Аппарат САА стал основой метода многоуровневого структурного проектирования программ (МСПП). Начало инструментальным сред­ствам метода МСПП в свое время было по­ложено созданием системы МУЛЬТИПРО­ЦЕСИСТ, ориентированной на структурный синтез программ (на языках ПЛ/1, Фортран, Паскаль и др.) по их многоуровневым про­ектам, оформленным на входном языке про­ектирования САА/1 [2]. Развитие объектно-ориентированных технологий требует но­вых подходов к инструментальным средст­вам программирования, появились эффек­тивные языки проектирования и средства генерации программ в объектно-ориентиро­ванных средах (например, язык UML и его инструментарий [3]). С развитием Интер­нет-технологий возникли языки, ориентиро­ванные на разработку Web-приложений. Отметим также, что разработка современ­ного программного обеспечения тесно свя­зана с развитием и использованием моделей параллельных вычислений, которые прони­зывают большинство аспектов архитектуры и средств программирования современных компьютерных систем [4–6].

В данной работе описан разработан­ный интегрированный инструментарий, ориентированный на формализованное про­ектирование алгоритмов и синтез последо­вательных и параллельных программ в объ­ектно-ориентированных средах программи­рования (Java, С++ и др.). Рассмотрены средства распараллеливания и синхрониза­ции параллельных процессов в модифици­рованных САА. Описана реализация асин­хронных алгеброалгоритмических моделей вычислений с общей памятью средствами языка программирования Java с использова­нием интегрированного инструментария.
^

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр


В основу предлагаемых интегриро­ванных инструментальных средств проек­тирования и генерации программ положен аппарат САА и их модификаций [1]. Моди­фицированные САА (САА М) предназна­чены для формализации процессов мульти­обработки, возникающих, в частности, при конструировании программного обеспече­ния в мультипроцессорных системах.

САА являются двухосновной алгеб­рой < UB;  >, где U – множество опера­торов, B – множество логических условий [1]. Операторы представляют собой ото­бражения информационного множества (ИМ) в себя, логические условия являются отображениями множества ИМ в множество значений 3-значной логики E3 = {0, 1, ,}, где 0 – ложь; 1 – истина;  – неопределен­ность. Сигнатура операций САА  =  2 состоит из системы 1 логиче­ских операций, принимающих значения в множестве B, и системы 2 операций, при­нимающих значения в множестве операто­ров U. В САА < UB;  > фиксируется сис­тема образующих , представляющая собой конечную функционально полную совокуп­ность операторов и логических условий. С помощью этой совокупности посредством суперпозиции операций, входящих в , по­рождаются произвольные операторы и ло­гические условия из множеств U и B. К ло­гическим операциям системы 1 относятся обобщенные булевы операции: дизъюнкция (  ), конъюнкция (  ), отрицание (), а также операция  = ^ A левого умножения условия на оператор. К основным оператор­ным операциям системы 2 относятся: ком­позиция A * B, альтернатива (-дизъюнк­ция) ([] AB), цикл (-итерация) {[] A}. Представления в САА < UB;  > операто­ров из U посредством суперпозиций, вхо­дящих в сигнатуру , получили название регулярных схем (РС) [1].

Сигнатура ' модифицированных САА, кроме перечисленных конструкций, входящих в , содержит операции, предна­значенные для представления параллельных вычислений. К этим операциям относится, в частности, асинхронная дизъюнкция A  ^ B – бинарная операция на множестве U, со­стоящая в асинхронном применении опера­торов A и B. Суперпозиция бинарных опе­раций асинхронной дизъюнкции приводит к производной операции m-местной асин­хронной дизъюнкции , состоящей в параллельном выполнении m ветвей вычис­лений. Для синхронизации параллельных ветвей в САА М используются контрольные точки и синхронизаторы.

Контрольные точки представляют собой фиксированные позиции между опе­раторами в схеме [1]. С каждой контроль­ной точкой ^ T ассоциировано условие u, ложное до тех пор, пока процесс вычисле­ний не достиг точки T, истинное с момента достижения данной точки и неопределенное при наличии аварийных остановок на пути, ведущем к точке T данной схемы. Условие u называется условием синхронизации, ассо­циированным с точкой T, которая далее обозначается T(u).

Под синхронизатором понимается цикл S(u) = {[uE}, где u – логическая функция, зависящая от условий синхрони­зации, ассоциированных с некоторыми кон­трольными точками схемы [1]. Синхрониза­тор, установленный в некотором месте схемы, осуществляет задержку вычислений в данном месте схемы вплоть до момента, когда его условие синхронизации u (сопря­женное с прохождением соответствующих контрольных точек) станет истинным.

С помощью рассмотренных операций формализуется асинхронная мультиобра­ботка [1], состоящая в совместном функ­ционировании нескольких ветвей вычисле­ний, снабженных специальными каналами, реализующими, в случае необходимости, ожидания и обменные взаимодействия ме­жду параллельными ветвями. Представле­ния алгоритмов в САА М, специфицирую­щие асинхронные операторные взаимодей­ствия, называются параллельными регуляр­ными схемами (ПРС). Отметим, что САА М также содержит средства, необходимые для описания синхронных вычислений. В рабо­тах [1, 5, 7   10] аппарат САА М применен при решении задач символьной мультиоб­работки: последовательных и параллельных сортировок, поиска, языкового процессиро­вания и др. Проиллюстрируем рассмотрен­ные понятия на примере параллельной ад­ресной сортировки массива.

Пример 1. Суть адресной сорти­ровки состоит в вычислении для каждого из элементов входного (сортируемого) массива ^ M0 его индекса (адреса) в выходном массиве M. При этом вычисление индекса для каж­дого элемента входного массива является независимым. В рассматриваемом алго­ритме массив M0 длины n разбивается на m подмассивов (i = 1, ..., m), которые обрабатываются m параллельными ветвями (m  1). Ветвь с номером i осуществляет вы­числение выходных индексов элементов подмассива и их вставку в массив M. ПРС адресной сор­тировки имеет следующий вид:

где СТАРТ – оператор инициализации данных (ввод сортируемого массива); АДР_ВЕТВЬ(i) – ветвь, осуществляющая вставку элементов подмассива в выходной массив ^ М; ВЫЧ_ГР(im1m2) – вычисление границ (m1, m2) подмассива ; АДР_ВСТАВ(j) – составной оператор, вычисляющий индекс j-го элемента массива (j = 1, ..., m) в выходном массиве М, и выполняющий вставку этого элемента в массив М; – контрольная точка для фиксации момента завершения обработки в -й ветви; – синхронизатор по условию достижения контрольных точек во всех m параллельных ветвях; ФИН – заключительный оператор (вывод отсорти­рованного массива).

Смысл приведенного алгоритма состоит в параллельном функционировании ветвей вычислений , каждая из которых осуществляет вставку элементов подмассива в массив М с помощью оператора АДР_ВСТАВ(j). В операторе нахо­дится синхронизатор , выпол­няющий задержку вычислений до тех пор, пока все ветви не закончат обработку. После завершения выполнения синхрони­затора имеем отсортированный массив М. Более подробно метод параллельной адрес­ной сортировки описан в [7].
^

2. Разработка приложений в интегриро­ванном инструментарии проектирования и синтеза программ


В данном разделе рассматривается процесс автоматизированного проектирова­ния и генерации программ по формализо­ванным спецификациям в САА М с использованием разработанного в [11] интегрированного инструментария. Ин­струментарий основывается на методе диалогового конструирования синтакси­чески правильных программ [9] и ис­пользует различные формы представле­ния алгоритмов в процессе их проекти­рования – естественно-лингвистическую (САА-схемы), алгебраическую (регуляр­ные схемы) и граф-схемную. Отметим, что интегрированный инструментарий может быть настроен на требуемый входной язык, представленный в алгебре алгоритмов, и выходной (целевой) язык программирования. В настоящее время он поддерживает генерацию последова­тельных и параллельных (многопоточ­ных) программ на языке Java по САА-схемам алгоритмов. Для синтеза про­грамм совместно с интегрированным ин­струментарием используются средства визуализированного проектирования программ – язык UML и система Rational Rose. Интегрированный инструментарий состоит из следующих основных компо­нентов:

  • ДСП конструктора, предназначен­ного для диалогового проектирования син­таксически правильных схем алгоритмов и синтеза программ;

  • редактора граф-схем;

  • трансформатора, осуществляющего диалоговое преобразование регуляр­ных схем;

  • генератора САА-схем по распреде­ленным гиперсхемам;

  • среды конструирования алгеброал­горитмических описаний (СКАО) [10] сим­вольной мультиобработки, содержащей описание конструкций САА-М, базисных понятий и их программных реализаций; ме­таправила конструирования алгоритмов, схемы алгоритмов, стратегии обработки и гиперсхемы.

^ 2.1. Диалоговое конструирование схем алгоритмов. В основу функциониро­вания ДСП конструктора положен диалого­вый режим с использованием меню подста­новок и дерева конструирования алгоритма (рис. 1). Меню состоит из конструкций САА-М, суперпозиция которых позволяет создавать алгоритмы в упомянутых ранее формах. Выбранные пользователем конст­рукции, а также операторные и логические переменные, входящие в них, отображаются в дереве с дальнейшей детализацией пере­менных. В зависимости от типа выбранной переменной система предлагает соответст­вующий список операций САА М или ба­зисных понятий из СКАО. Отметим по­уро­вневый стиль конструирования алгорит­ма, а также возможность переходов на различ­ные уровни (узлы дерева) с продол­жением процесса диалогового конструирования.

Процесс построения дерева констру­ирования T для некоторого алгоритма мо­жет быть представлен следующей РС:
ДСП_НАБОР(T) = ИНИЦ(T) *

*{[КО­НЕЦ_ДСП(T)] ВНН * ВНК *

* ОБРАБОТКА_УЗЛА(^ T) * ВЫВОД},
где ИНИЦ(T) – формирование корневой вершины дерева T с названием первого сос-тавного оператора, а также его дочернего узла, помеченного именем операторной переменной; КОНЕЦ_ДСП(T) – условие, истинное, если все переменные констру­ируемой схемы проинтерпретированы; ВНН – оператор выбора нужной непроинтер­претированной переменной в дереве T; ВНК – выбор нужной конструкции САА М, базисного или составного элемента; ОБРАБОТКА_УЗЛА(T) – оператор, кото-рый формирует дочернюю вершину для те-кущего выбранного узла дерева и помечает ее текстом выбранного элемента меню, а также формирует вершины дерева с назва-ниями операторных или логических пере-менных (если выбранный элемент – опе-рация САА). В процессе ДСП конструи-рования операции ВНН и ВНК выпол-няются пользователем. По полученному те-кущему дереву конструирования T осу-ществляется вывод текста схемы алгоритма с помощью оператора ВЫВОД. Разра-ботанная схема ДСП_НАБОР(T) подобна схеме ДСП.БС, приведенной в [9]. В схеме ДСП.БС осуществлялась обработка пере-менных конструированной схемы лишь в одном направлении (слева направо) и вы-полнялся последовательный переход сверху вниз от предыдущего уровня дерева кон-струирования к следующему. В отличие от упомянутой схемы, в построенной РС ДСП_НАБОР(T) есть возможность выпол-нять конкретизацию переменных конструи-руемой схемы в произвольном порядке, переходя на различные уровни дерева T.

Пример дерева конструирования показан на рис. 1 в окне ДСП-конструктора. Отметим, что в ДСП конструкторе дерево для каждого из составных операторов схемы алгоритма приводитя на отдельной вкладке окна “Дерево алгоритма”. Текст САА-схемы, соответствующий дереву кон-струирования, отображается в отдельном текстовом окне в аналитической или естес-твенно-лингвистической форме в зависи-мости от установленной опции (левое ниж-нее окно в окне ДСП-конструктора).

2.2. Cинтез программ по схемам алгоритмов. По полученному в процессе конструирования алгоритма дереву, реали­зациями элементарных операторов и усло­вий на целевом объектно-ориентированном языке программирования, а также другими фрагментами, ДСП конструктор выполняет синтез программы. В процессе синтеза управляющие конструкции САА-схемы ал­горитма (асинхронная дизъюнкция, компо­зиция, альтернатива, цикл и др.) отобража­ются в соответствующие операторы языка программирования, а вместо базисных опе­раторов и предикатов подставляются их ре­ализации на этом же языке из СКАО. Соста­вные операторы могут быть представлены как подпрограммы (методы). На вход синтезатора поступает также файл, который содержит каркасное описание основного класса программы (без реализаций мето­дов), в который выполняется подстановка синтезированного кода. Проектирование классов программы и их взаимосвязей, а также генерация каркасного программного кода выполняется с помощью инструмента­рия Rational Rose. В файл, полученный в результате моделирования в Rational Rose, выполняется подстановка кода, сгенериро­ванного в предлагаемом инструментарии.

В табл. 1 приведено описание в СКАО [10] основных операторных опера­ций САА (композиции, альтернативы, цикла), реализации которых на языке Java используются в процессе генерации про­грамм. Приведенные реализации содержат строки “^оператор1^” и “^оператор2^”, вме­сто которых процессе синтеза будут подстав­лены тексты реализаций операндов этих
операций.

В табл. 2 приведены примеры описания в СКАО базисных элементов для алгоритмов сортировки. Естественно лингвисти­ческая и аналитическая формы описания базисного элемента содержат в себе имена формальных параметров в скобках. Фактические параметры, которые задаются в САА-схемах, заменяют при синтезе программы соответствую­щие формальные параметры в тексте реализации базисного понятия на языке программирования. Реализации базисных элементов написаны с использованием компонента повторного использования – класса Sorting, предназначенного для ре­шения различных задач сортировки (бо­лее подробно этот класс рассматривается далее в примере 2). Признаком формаль­ного параметра в реализации является символ “%”, за которым следует поряд­ковый номер параметра в тексте базис­ного оператора или предиката. Напри­мер, в базисном операторе “Переставить l, r по У(i) в (М)” присутствует параметр i – номер указателя. Значение этого па­раметра будет подставлено вместо соот­ветству­ющего формального параметра в реализации этого оператора, который имеет вид: s.transp(%1), где s – экземпляр класса Sorting; transp – метод данного класса, выполняющий перестановку элементов массива М, соседних с указате­лем. Реализация других базисных эле­ментов, приведенных в табл. 2, также яв­ляются вызовами методов класса Sorting. Отметим, что в процессе генерации про­граммы перед текстом реализации того или иного базисного элемента добавля­ется его название в виде комментария.

Отображение в языке программиро­вания для любого из элементов СКАО мо­жет содержать несколько вариантов, один из которых можно выбрать в зависимости от решаемой задачи. Например, базисный оператор инициализации (СТАРТ) имеет различные варианты реализации на язы­ке программирования для сортировки и
поиска.

В ДСП конструкторе есть воз­можность указать параметры генерации программы по схеме алгоритма. Данные параметры разделены на две группы: об­щие параметры и параметры генерации для составных элементов схемы. Общие параметры включают имя входного файла, содержащего каркасный про­граммный код, и имя результирующего файла генерации; параметры подста­новки сгенерированного кода во входной файл. Код может быть подставлен вместо указанной цепочки символов в файле (например, “// ”) или в тело ука­занной в параметрах функции, кото­рая описана во входном файле. В случае языка Java код обычно подставляется в метод main. В параметрах генерации для составных операторов и предикатов для каждого из них можно задать имя метода, в тело которого будет подставлен сгене­рированный для них код на языке про­граммирования.

Генерация кода в ДСП конструкторе осуществляется по дереву конструирования, все терминальные вершины которого явля­ются базисными операторами или предика­тами (т.е. все переменные сконструирован­ной схемы проинтерпретированы). В про­цессе генерации обход дерева конструиро­вания осуществляется в направлении слева направо. Обработка начинается с нижнего листа самой левой ветви дерева, затем обра­батываются все листья и узлы дерева так, что ветви рассматриваются слева направо, а узел обрабатывается лишь после обхода всех ветвей, которые исходят из него. Отме­тим, что такой обход дерева обычно исполь­зуется для получения постфиксной записи при трансляции выражений [12]. Обработка каждой вершины дерева конструирования осуществляется в зависимости от ее типа, а именно: базисное понятие, переменная, имя составного элемента или операция САА. Если текущий элемент дерева – базисный оператор или предикат, то осуществляется поиск реализации данного элемента на языке программирования в СКАО. Если найденная реализация содержит несколько возможных вариантов, то из них выделяется вариант, специально указанный пользовате­лем для текущего проекта или вариант по умолчанию (в случае, если вариант не был выбран пользователем). Затем осуществля­ется подстановка в реализацию значений фактических параметров базисного понятия. Далее перед полученной реализацией до­бавляется текст базисного элемента схемы в виде комментария и полученный текст за­писывается в стек. Если текущая вершина – операция САА, то в ее реализацию вместо строк, которые соответствуют именам пе­ременных, осуществляется подстановка реализаций ее операндов, которые последо­вательно изымаются из стека. Полученный текст записывается в стек. Если текущий обрабатываемый элемент дерева – перемен­ная некоторой операции САА, то вершина пропускается. Текущая вершина дерева также может быть именем составного опе­ратора или предиката, который соответст­вует отдельному поддереву конструирова­ния. В этом случае в стек записывается текст реализации данного элемента, полу­ченный при обработке его дерева конструи­рования и сохраненный в специальной таб­лице. Перед текстом составного элемента добавляется комментарий с информацией о том, что в данной части программы начина­ется код, соответствующий составному опе­ратору схемы алгоритма. Содержимое вер­шины стека после обработки корневой вер­шины дерева конструирования является ре­зультирующим программным кодом, кото­рый соответствует САА-схеме алгоритма. Полученный текст вставляется в требуемые позиции файла с каркасным программным кодом, поступающего на вход генератора программ перед началом генерации.

^ 2.3. Синтез параллельных много­поточных программ. Асинхронные алго­ритмы, представленные в САА М, в таких языках программирования, как Java, C++, Perl, Python, Delphi, могут быть реализо­ваны с помощью подпроцессов или потоков (threads). Поток в многопоточных операци­онных системах – наименьшая единица вы­полнения. Для каждого процесса (объекта, создаваемого при запуске программы) ОС создает один главный поток, который явля­ется потоком команд центрального процес­сора, которые выполняются поочередно. При необходимости главный поток может создавать другие потоки, пользуясь для этого программным интерфейсом ОС. Все потоки, созданные процессом, выполняются в адресном пространстве этого процесса и имеют доступ к его ресурсам. Если процесс создал несколько потоков, то все они вы­полняются параллельно, причем время цен­трального процессора (или нескольких цен­тральных процессоров в мультипроцессор­ных системах) распределяется между этими потоками. Каждому потоку дается опре­деленный интервал времени, на протя­жении которого он находится в активном
состоянии.

Текущая версия интегрированного инструментария обеспечивает синтез парал­лельных программ на языке программиро­вания Java [13]. Отметим, что Java поддер­живает многопоточность не только на уровне библиотек, но и на уровне самого языка, который значительно облегчает по­строение программ, которые надежно рабо­тают в многопоточном режиме. Java предоставляет возможность реализации подпроцессов с помощью класса Thread (из пакета java.lang), который содержит все средства, необходимые для создания потоков, управ­ления их состоянием и синхронизации. При этом для организации многопоточных про­грамм существует две возможности: первая предусматривает создание подкласса класса Thread, вторая – создание класса, который реализует интерфейс Runnable. В этих клас­сах переопределяется метод run, который содержит код, предназначенный для выпол­нения в рамках отдельного потока. Отме­тим, что метод main в программах Java по умолчанию является подпроцессом, и из него или из другого активного метода, мо­гут начинать свое выполнение другие под­процессы.

Потоки, работающие параллельно в многопоточной системе, могут обращаться одновременно к общим объектам в памяти, что может привести к неправильной работе программ. Решением этой проблемы явля­ется синхронизация потоков. Java обеспечи­вает два уровня синхронизации:

  • защита совместно используемых ресурсов;

  • сигнализация об изменениях в со­стояниях между процессами.

Для синхронизации фрагмента кода, осуществляющего доступ к разделяемым ресурсам, этот фрагмент включается в блок или метод, помеченный модификатором synchronized. Когда поток начинает выпол­нение синхронизированного фрагмента кода, этот фрагмент блокируется. До окон­чания выполнения синхронизированного фрагмента либо до тех пор, пока блокировка не будет явно отменена, ни один другой по­ток не может начать выполнение аналогич­ного фрагмента кода.

Другим важным аспектом процесса синхронизации в Java является передача подпроцессу сообщения, указывающего, что на данный момент уже выполнено условие, исполнения которого он “ждет” [13]. Если подпроцесс в определенный момент вычис­лений не может продолжать работу, так как объект, с которым он связан, не находится в надлежащем состоянии, он может вызвать метод wait, который переведет этот подпро­цесс в состояние ожидания. Ожидающий поток может быть вновь активирован в слу­чае, если другой поток вызовет для него ме­тод notify или notifyAll. Метод notify возоб­новляет работу одного потока, а метод notifyAll активирует все потоки, ожидаю­щие снятия блокировки, реализованной с помощью некоторого объекта. Как и вызов метода wait, вызовы методов notify и notifyAll могут быть исходить только из синхронизированного блока.

Методы wait, notify и notifyAll ис­пользованы в интегрированном инструмен­тарии для реализации средств синхрониза­ции САА-М (контрольных точек и синхро­низаторов), рассмотренных в разделе 2.

Пример 2. В качестве иллюстрации рассмотрим реализацию многопоточной программы на языке Java, сгенерированной по регулярной схеме параллельной адрес­ной сортировки (см. пример 1) с использо­ванием интегрированного инструментария и системы Rational Rose. На рис. 2 показана диаграмма классов UML с основными клас­сами разрабатываемого приложения. Класс Adrsort – основной класс программы адрес­ной сортировки. Выполнение программы начинается с метода main данного класса, в котором вводится сортируемый массив, вы­зываются m параллельных потоков, осуще­ствляется синхронизация (ожидание завер­шения вычислений во всех ветвях) и выво­дятся результаты сортировки. В методе ins находится реализация составного оператора АДР_ВСТАВ(j) схемы    . Данный метод в процессе сортировки вызывается парал­лельными потоками. В классе SortThread, наследующем класс Thread, находится опи­сание кода для i-го параллельного потока (i = 1, …, m). Классы Adrsort и SortThread используют методы изображенного на диа­грамме класса Sorting – повторно исполь­зуемого компонента для решения различ­ных задач сортировки (пузырьковой, чел­ночной, адресной и др.). Этот класс содер­жит описание данных – обрабатываемого массива, указателей, маркеров, контроль­ных точек, методы доступа к этим данным, а также методы остановки и возобновления работы главного потока и отсчета времени, истекшего с начала сортировки.

В Rational Rose для класса Adrsort была выполнена генерация файла с каркас­ным программным кодом, не содержащим реализаций методов main и ins. Дальнейшая разработка алгоритмов этих методов, а также синтез и подстановка кода, реали­зующего эти функции, выполнены в интег­рированном инструментарии. Генерация класса SortThread полностью осуществлена в ДСП конструкторе.

В процессе синтеза кода программа ДСП конструктора использует шаблоны программных реализаций конструкций САА и базисных понятий из СКАО, примеры ко­торых были приведены выше в табл. 1 и 2. Далее рассмотрены примеры программных реализаций операций, предназначенных для формализации параллельных вычислений: асинхронной дизъюнкции, синхронизатора, контрольных точек. Приводится естест­венно-лингвистическая форма представле­ния каждой из этих операций и их отобра­жение в текстовый шаблон на языке Java.

В СКАО интегрированного инстру­ментария для реализации операции m-мест­ной асинхронной дизъюнкции (есте­ственно-лингвистическая форма этой опе­рации – ПАРАЛЛЕЛЬНО (i = 1, ..., m)
(“оператор1”)) для рас­сматриваемой адресной сортировки был выбран следующий вариант шаблона на языке Java:


int m = s.getThreadNum();

for (int i = 1; i <= m; i++)

{

SortThread st = new SortThread(s, c, i);

}

// $classes

class SortThread extends Thread

{

Sorting s;

Adrsort c;

int n, m, i, j;

/* Конструктор класса */

SortThread(Sorting s, Adrsort c, int i)

{

this.s = s;

this.c = c;

this.i = i;

n = s.getDataLen();

m = s.getThreadNum();

new Thread(this).start(); /* Запустить поток на выполнение */

}

public void run()

{

^оператор1^

}

}


Приведенный фрагмент программ­мной реализации разделен на две части строкой “// $classes”. В первой части описан цикл, в котором создаются m параллельных потоков (объектов класса SortThread). Во второй части фрагмента приведен класс SortThread (наследующий класс Thread), в котором описан шаблон класса потока (без реализации метода run()). Конструктор класса SortThread выполняет инициализацию данных и запуск подпроцесса с помощью метода start(). Через параметры этому конструктору передается объект класса Sorting, экземпляр основного класса программы и номер i создаваемого потока. Метод run класса SortThread содержит строку “^оператор1^”, вместо которой в процессе генерации будет подставлен код реализации операнда асинхронной дизъюнкции. В результате синтеза в том месте программы Java, которое соответствует асинхронной дизъюнкции, будет приведен цикл создания потоков. Текст класса SortThread (с текстом реализации i-й ветви алгоритма) будет включен после текста основного класса программы. Вместо строк “This_class”, приведенных в данном фрагменте, в процессе синтеза подставляется имя основного класса, указанное в параметрах генерации кода (например, Adrsort – основной класс программы адресной сортировки).

Для реализации на языке Java операции синхронизатора (естественно-лингвистическая форма этой операции – ЖДАТЬ ‘условие1’) для рассматриваемого алгоритма сортировки в СКАО был выбран следующий вариант шаблона:

if (! (^условие1^))

s.waitMain(); // Приостановить работу
главного потока

Здесь waitMain – метод класса Sorting, выполняющий задержку вычислений в главном потоке программы, в случае, если условие ^условие1^ не выполнено. Вместо строки “^условие1^” для рассматриваемого алгоритма в процессе генерации будет подставлен вызов метода s.procEnd(), который возвращает истинное значение в случае, если все m параллельных ветвей завершили вычисления, и ложное в противном случае. Описание метода waitMain в классе Sorting имеет вид


public void waitMain()

{

notified = false; // Установить признак того,

// что поток mainThread находится

// в состоянии ожидания

synchronized (mainThread)

{

try { // Приостановить поток mainThread

mainThread.wait();

}

catch (InterruptedException e) { e.printStackTrace(); }

}

}


Здесь mainThread – переменная класса Thread, содержащая информацию о главном потоке выполняющейся программы. Поток mainThread в приведенном фрагменте переведен в состояние ожидания с помощью вызова стандартного метода wait().

Для реализации на языке Java оператора контрольной точки (естественно-лингвистическая форма этого оператора – КТ ‘условие1’) для случая рассмотренной адресной сортировки в СКАО был выбран следующий вариант шаблона:

^условие1^

if (s.procEnd())

s.notifyMain(); // Возобновить работу главного потока

Вместо строки “^условие1^” для рассматриваемого алгоритма в процессе генерации будет подставлена программная реализация базисного элемента ОБР_ЗАК(i), а именно, вызов метода s.setCtrlPoint(i, true) класса Sorting. Этот метод присваивает контрольной точке с номером i (соответствующим номеру потока) истинное значение. После выполнения этого метода проверяется истинность всех контрольных точек, ассоциированных с подпроцессами, с помощью вызова упомянутой выше функции s.procEnd(). После завершения вычислений во всех подпроцессах (s.procEnd() возвратила истинное значение) выполняется метод notifyMain() класса Sorting, возобновляющий работу главного потока. Описание этого метода имеет вид

public void notifyMain()

{

if (! (notified))

{

synchronized (mainThread)

{

/* Возобновить работу потока mainThread */

mainThread.notify();

// Установить признак того,

// что работа потока mainThread возобновлена

notified = true;

}

}

}

В приведенной функции работа по-тока mainThread возобновляется с помощью вызова стандартного метода notify().

Таким образом, по асинхронным алгоритмам, представленным в САА М, может быть синтезирован вручную или автоматизированным способом (с применением разработанного интегрированного инструментария) код на языках программирования, которые поддерживают создание многопоточных программ.

Заключение


В работе рассмотрены средства фор-мализованного проектирования и синтеза последовательных и асинхронных программ по их представлениям в алгебрах алгорит-мов. Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программи-рования. Описан метод синтеза многопоточ-ных программ на языке Java по асинхрон-ным алгоритмам, формализованным в
САА-М.

К ограничениям интегрированного инструментария можно отнести то, что в схемах алгоритмов не учитывается объек-тная ориентированность генерируемой про-граммы. Она присутствует лишь на уровне программных реализаций элементов схемы в среде конструирования алгеброалгори-тмических описаний инструментария, а также в каркасном файле, поступающим на вход синтезатора. Тем не менее, данная проблема может быть решена в дальнейшем путем настройки инструментария на объектные САА-схемы [14, 15].

К перспективам развития интегри-рованного инструментария следует отнести его настройку на синтез параллельных программ, использующих технологию MPI.


  1. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Методы символьной мультиобработки. – Киев: Наук. думка, 1980. – 252 с.

  2. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий // Е.Л. Ющенко, Г.Е. Цейтлин, В.П. Грицай, Т.К. Терзян. – М.: Финансы и статистика, 1989. – 208 с.

  3. Кватрани Т. Rational Rose 2000 и UML. Визуальное моделирование / Пер. с англ. – М.: ДМК, 2001. – 176 с.

  4. Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. Алгебродинамический подход. – Киев: Наук. думка, 2000. – 176 с.

  5. Дорошенко А.Ю., Фінін Г.С., Цейтлін Г.О. Алгеброалгоритмічні основи програмування. — К.: Наук. думка, 2004. — 458 c.

  6. Дорошенко А.Е., Цейтлин Г.Е. Алгеброавтоматные спецификации параллельных программ над общей и распределенной памятью // Проблемы программирования. – 2003. – № 3. – C. 24–33.

  7. Яценко Е.А. Регулярные схемы алгоритмов адресной сортировки и поиска // УСиМ. – 2004. – № 5. – С. 61 – 66.

  8. Цейтлин Г.Е. Проектирование алгоритмов параллельной сортировки // Программирование. – 1989. – № 6. – С. 4–19.

  9. Цейтлин Г.Е. Введение в алгоритмику. – Киев: Сфера. – 1998. – 310 с.

  10. Яценко О.А. Середовище конструювання алгоритмічних знань та інструментарій синтезу програм // Проблемы программирования. – 2006. – № 1–2. – С. 349–358.

  11. Яценко Е.А., Мохница А.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и программ // Проблемы программирования. – 2004. – № 2–3. – С. 444–450.

  12.  Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. – М.: Мир, 1973. – 1. – 612 с.

  13. Бишоп Д. Эффективная работа: Java 2. –
    Киев: BHV, 2002. – 592 с.

  14. Цейтлин Г.Е., Теленик С.Ф., Амонс А.А. Алгебро-логическая формализация в объектно-ориенти­рованных технологиях // Проблемы программирования. – 2002. – № 1–2. – С. 136–146.

  15. Doroshenko A.E., Ragozin D.V. Retargetable and tuneable code generation for high performance DSP // “Parallel Computing Technologies”, Proc. 7-th Int. Conf. PaCT’2003, LNCS, 2003. – 2763. – P. 452–466.



Получено 01.09.2006
Об авторах:
Дорошенко Анатолий Ефимович,

доктор физ.-мат. наук, профессор,

зав. отделом теории компьютерных
вычислений,

Яценко Елена Анатольевна,

кандидат физ.-мат. наук,

научный сотрудник.

Место работы авторов:
Институт программных систем
НАН Украины,

проспект Академика Глушкова, 40.

03680, Киев-187, Украина.

тел. (044) 526 1538

е-mail: dor@isofts.kiev.ua, aiyat@i.com.ua






© А.Е. Дорошенко, Е.А. Яценко, 2006

ISSN 1727-4907. Проблеми програмування. 2006. № 4

Добавить документ в свой блог или на сайт

Похожие:

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconМежгосударственный стандарт система проектной документации для строительства правила выполнения
Цниипроект), проектным институтом (Промстройпроект), Проектным институтом №2 (пи-2), Центральным научно-исследовательским и проектным...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconА. Ф. Манако Формализация ключевых понятий манок-систем
КИ); разработки формализованного представления S; разработки и реализации формализованного надлежащим образом инструментария для...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconМоделирование динамичекого портфеля заказов в производственно-экономических системах
Портфель имеет вид единого формализованного модуля, в котором учтена динамика колебаний внешней среды, а также изменение многообразных...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconСредства защиты информации в компьютерных системах
Технические методы и средства защиты целостности и бесперебойности функционирования компонентов кс 35

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconВ. В. Карасиков использование программ администрирования в процессе обучения
В зарубежной литературе используется термин «учитель-фасилитатор» (от анг. Facility –легкость). Источником знаний выступают технические...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconУправление временем и делопроизводством управление временем
Ональную рабочую среду и инструментальные средства. Мы предлагаем вам пакет программ, которые вы можете приспособить к вашим требованиям....

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconЛекция Объектно-ориентированное программирование Эволюция подходов...
Подходы к декомпозиции программ и накоплению компонент программ. Схемы программ. Свертка информационно-замкнутых конфигураций. Спецификация...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр icon1. 1 Оцифрованые карты
Более конктерно, мы рассмотрим случай нахождения оптимального пути для транспортного средства, перемещающегося по поверхности нашей...

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр iconО построении клонов алгебр функциональных
Очерчены одномерные и многомерные вычислительные структуры и ассоциированные с ними предметные области

1. Средства формализованного проекти­рования программ в системах алгорит­мических алгебр icon 11. Методы и средства защиты программ от компьютерных вирусов
...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<