Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Тапкинов, Батр Юрьевич

• Тапкинов, Батр Юрьевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Тапкинов, Батр Юрьевич

Введение.

Глава 1. Современное соеюяние исследований в облаем и оптимизации и распараллеливания программ.

1.1. Различные подходы к распараллеливанию профамм.

1.11. «Ручное» распараллеливание.

1.1.2. Автоматическое распараллеливание.

1.1.3. Полуавтоматическое распараллеливание.

1.2. Технологии параллельною программирования.

1 2.1. Яшки параллельного программирования.

1 2.2 Коммуникационные бибпиогеки и ишерфейсы параллельного программирования.

1.2.3. Среде 1ва автмажческого распараллеливания профамм.

1 2.4. Средсгва создания и проектирования параллельных программ.

1 2 5 Специализированные параллельные библиотеки.

1.3 Различные вариант внуфеннего представления профамм.

13 1. Управляющий граф.

13 2 1 раф зависимости по данным.

1 3 3 Граф программных зависимоеIей.

1 3 4 Граф вызовов процедур.

1.3.5. Решетчатый граф

1 3.6 Граф вычислений программы.

1 3 7 Иерархический граф заданий.

1.4 Выводы

Глава 2 Сфук1урные предикативные грамматики и струк1урный фаф.

2 1. Формализмы для описания семантики языков программирования и построения семантической арук1уры ирофамм

2 1 1 Атрибутные грамматики

2 1 2 ОС-грамматики и ОСС-нотация.

2.1.3. Структурные предикативные фамматики.

2 2. Реализация струюурных предикативных граммашк.

2.2.1. 11редс1авчение структурною фафа.

2.2.2. Реализация алюритма унификации вершин структурного графа и 1ермов.

2.2.3. Преобразование правил струк1урнои предикативной грамматики в правила Пролога.

2.2 4. Средства работы со струк1урным фафом.

2.3. Выводы.

I лава 3. Использование структурною фафа для оптимизации и распараллеливания программ.

3.1.11ромежу1 очное представление профаммы.

3.1.1. Структура промежуточною предеывления.

3.1.2. Элементарные преобразования.

3.2. Построение информационных структур.

3.2.1 Управляющий граф

3.2 2.1 раф зависимоеIей по данным.

3 2 3 Граф вызовов процедур

3 3. Преобразования программ.

3 3 1. Про 1Я1 ивание констант.

3 3 2 Удаление "мертвого" кода.

3 3.3. Удаление недостижимою кода.

3 3 4. Упрощение арифмежческих выражений.

3 3 5. Канонизация цикла

3.3 6 Разрезание цикла.

3.3.7 Слияние циклов

3 3.8 Развертка цикла

3 4 Результат и выводы

Глава 4 Структурно-предикативная система построения внутреннего представления профамм

4.1. Возможности сиаемы.

4.2 Структура сиаемы.

4.3. Рабош со сфуктурно-предикашвной сис1емой.

4.4. Сопоставление с дру1 ими системами.

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание»

Актуальность темы. Развитие вычисли ¡ельных сиаем, появление новых amiapaiHbix платформ и процессоров обуславливаю! необходимость разработки новых компиляторов Разработка эффекшвного компилятора - это фудоемкий и досшючно длительный процесс.

Одним из ответеiвенных этапов разработки компиляюра являемся проектирование внутреннею представления программ для исходного языка. От внуфеннего предаавления будут зависеть ва/Кные свойства компиляюра, такие как переносимость на дру1 ие платформы, модифицируемость, скорость работы, качес1во кода и т д.

Существуем ботьшое количество моделей для представления программ, как чисю ¡еоретических, ык и широко применяемых на пракшке:

• постфиксная ношция;

• грехадресный код;

• синтаксическое дерево,

• другие граф-модели

Внуфенние представления в современных компиляторах, как правило, реализуются в виде таких струюур, как списки и деревья. В некоторых системах оптимизации и распаратлеливаиия ирофамм, таких как Polaris [9J, SUIF/SUIF2 [47], ОРС [96], внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке. Основное преимущество представления в таком виде - ло просюта проектирования, модифицируемость и расширяемость.

За преобразование исходной программы во внутреннее представление отвечае1 анализирующая часть компиляюра или парсер Разрабо1ка парсера с нуля является очень трудоемкой задачей и может занять мною времени. Поэтому, чтобы ускорить и облегчить процесс ею разработки, как правило, используются специальные инсфуменш, так называемые юнераторы компиляторов (Lex/YACC [52], Пех/Bison [9]). Но даже при использовании гене5 раюров компиляторов за разрабсмчиком парсера остется решение основной задачи - описание сишаксиса и семаншки исходною языка с помощью некоторого формализма.

Сегодня для решения этой задачи чаще всего используются афибутные грамматики [73], которые позвочяют описывав сишаксис и семантику языка блаюдаря наличию афибутов, связанных с каждым фамматическим символом, и семантических правил, вычисляющих эти атрибут. В атрибутной грамматике обяза1ельно должен бьпь задан правильный порядок выполнения семашических правил, связанных с узлами дерева разбора. Установление эюю порядка являйся нефивиалыюй задачей, решение коюрой требуе1 oi профаммис1а дополнительных временных зафа1 и о1влекаето1 решения основной задачи. Кроме того, при использовании афибутной граммашки построение внутреннего представления программы, отличною от дерева разбора, нужно описывать в процедурном виде.

В 1980 году Ф. Перейрой и Д. Уорреном были описаны фамматики DCG [35] (Definite Clause Grammars), оiносящиеся к классу логических грамматик Сейчас эш грамматики неизменно включаются во все развитые системы программирования на языке Проло1 Oi и фамматики в смличие от атрибутных грамматик, не требуки задания строгого порядка выполнения семантических правил Однако построение семашической структуры программы с помощью DCG, как и в атрибушых фамматиках, нужно описывать в процедурном виде (на языке Пролог)

В 2003 году С II. Крицкий описал струк1урные предикативные фамматики [76] (СП-грамматики), основанные на понятии структурною графа программы и расширяющие DCG процедурой унификации вершин структурного графа и термов Эти грамматики обладаюi всеми возможностями DCG и при этом позволяют описывать построение семантической счруюуры программы и работу с ней в непроцедурном виде Однако эти грамматики не нашли широкого применения из-за отсутствия и\ реашзации, разрабоиа которой преде ывляется ак1уа1ьной задачей развития сиаем пое1роения компиляторов.

Цель рабом»! и задачи исследования. Целью данной диссертационной работы является реализация струьпурных предикашвных грамматик и их использование для построения внутреннею представления программ, ориентированною на их ошимизацию и распараллеливание.

Для достижения нос явленной цели решаются следующие задачи:

1. Создание программной реализации СП-1 рамматик, представления структурною графа и алгоритма унификации вершин структурного графа и термов.

2. Применение СП-граммажк дпя определения и построения внуфеннего представления программ, написанных на процедурных языках, в виде структурною фафа.

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

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

Методы исследований. В диссертационной рабене использовались методы 1еории трансляции и преобразовании профамм, элемешы 1еории графов При реализации программною обеспечения использовались принципы логического программирования

Достоверность и обоснованность резулыатв. Полученные результаты прошли проверку в ходе практического использования разработанного программного комплекса для проведения многочисленных экспериментов с исходными текстами тесювых и реальных профамм.

Научная новизна. Предюжены методы и алюршмы автомашческого построения структурного фафа и преобразования правил С11-фамматики в правила Пролога. Предчожен способ использования унификации вершин структурною графа и термов для построения, анализа и преобразования внуфеннего преде1автения программ

Практическая ценность. В чоде исследовательской работы была разработана жепериметальная сиаема дня nocí роения внуфеннего представления программ, которое ориентировано на их ошимизацию и распараллеливание. Эта система может бьпь использована для обучения, исследований и экспериментов в области преобразований программ.

Профаммно реагж зованные CII-iрамматики мо!ут бьпь использованы в качестве инструмент при разработке ошимитирующих и распараллеливающих компиляторов.

Апробация результант работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети Ишернет: техиолоти параллельного программирования", г Новороссийск, 2006 г., на научно-методической конференции "Современные информационные 1ехнологии в образовании: Южный федеральный oKpyi", i Ростов-на-Дону, 2006г., на научных семинарах кафедр ИВЭ и АДМ мехма1а РГУ, на научно-исследова1ельском семинаре ЮГИНФО PÍ У, 2006 г.

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавюрстве Из них 3 статьи в российском рецензируемом журнале, 1 ста!ья в сборнике трудов аспиратов РГУ и 2 в 1езисах докладов всероссийской и peí иональной конференций.

В совместных работах [77, 78] личный вклад авюра заключается в исследованиях и разработках, связанных с реализацией сфуктурных предикативных грамматик, представления струю урною графа, алюригма унификации и экспериментальной сиаемы

Объем и содержание работы. Диссерищия состоит из введения, четырех глав, заключения, списка ли1ера/уры и приложений.

Во введении обоснована актуальность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и практическая значимость резулыатов, указаны положения, выносимые на защиту, и кра1к0 аннотировано содержание глав

Первая ¡лава посвящена обзору современного состояния исследований в области оптимизации и распарач 1еливания про1рамм. Рассмафивают-ся 3 основных подхода к распараллеливанию программ: «ручное», автоматическое и полуавтомашческое распараллеливание. Приводится обзор различных технолошй параллельною программирования. Рассмафиваются расширения фадиционных последовательных языков, коммуникационные библиотеки и ишерфейсы параллельного профаммирования, специализированные параллельные библиотеки, средсчва автоматическою распараллеливания программ и средства создания и проекшрования параллельных программ. Приводится обзор и анализ различных вариантов внуфеннего представления программ.

Вторая итва диссертации посвящена подробному описанию формализма СП-граммашк, их использованию для посфоения семантической структуры программы, а 1ак же реализации эшх фамматик. Приводятся определения атрибушой грамматики, фаммашки ОСС, смрук1урной предика-тивнои грамматики и струк1урною графа, описывайся алгориш унификации вершин структурною графа и термов 11роизводится сравнение описания семантической сфуктуры программ с помощью атрибушых и СГ1-фамма-гик, коюрое показывает преимущество непроцедурною описания с помощью СП-грамматик Описывается профаммная реализация СП-грамматик.

Третья глава посвящена использованию сфуюурного графа в качестве промежуточного предеывления программ, ориешированною на их оптимизацию и распараллеливание Описывайся разработанное единообразное внутреннее представчение профамм дчя подмножеспз языков Си, Паскаль и Фортран Приводятся алюритмы построения информационных структур, часто используемых при ошимизации и распараллеливании программ: управпяющего I рафа, графа зависимосчей поданным и графа вызовов процедур. Описывается реализация известных преобразований программ, протягивание консташ, удаление «мертвого» кода, удаление недостижимого кода, упрощение выражений, канонизация цикла, разрезание цикла, слияние цикла и развертка цикла.

В четвертой кшве описывается разрабо1анная структурно-предикативная система - про!раммныи комплекс, основанный на реализации СП-граммагик.

В заключении формулирую 1ся основные результаты рабош.

В приложении А приводи 1ся описание подмножеств языков Си, Паскаль и Фортран, для коюрых были разработаны С11-фамматики.

В приложении В приводятся реализации описанных в рабо1е алгоритмов на языке Пролог.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Тапкинов, Батр Юрьевич

4.5. Выводы

На основе реачизации СП-граммашк и средств работы со структурным графом разработана экспериментальная система для построения внутреннего представления программ, ориентированного на их оптимизацию и распараллеливание Основное назначение системы - это предоставление средств для разработки оптимизирующих и распараллеливающих компиляторов. Кроме этою, система может быть использована для обучения методам трансляции, а также для исследовании и экспериментов при разработке алюритмов и методов трансляции

Заключение

Данная диссертационная работа посвящена реализации структурных предикативных грамматик в системе построения внутреннего преде явления программ, ориентированного на их оптимизацию и распараллеливание

В paôoie рассмотрены современные технологии ошимизации и распараллеливания программ, различные варианты промежуточною представления программ, формализмы, используемые д гя описания семантики языков программирования и построения семашической структуры программ. Сделан вывод о целесообразности реализации сгрукгурных предикативных грамматик, позволяющих описывать построение внутреннею представления программ в непроцедурном виде.

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

Разрабогана программная реализация СП-граммагик, включающая в себя способ представления струюурного графа, реализацию алгоритма унификации вершин структурного графа и термов, интерпретацию правил СП-грамматики Показано, чт о прог раммно реал и зованные Cl I-i рамматики moi ут быть использованы в качестве инструмента при разработке оптимизирующих и распараллеливающих компиляторов.

Разработаны СП-грамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде структурного графа

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

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

Используемые в системе CI I-фамматики позволяют описывать по-ароение внуфеннего преаавления профамм и работу с ним в непроцедурном виде. За счет открытости дополнительных модулей, сиаема может легко расширяться пользователями путем добавления новых преобразований, средств анализа и визуализации, поддержки дру1их языков профаммирова-ния.

Итак, в ходе работы были получены следующие резулыаты:

1. Разработана профаммная реализация СП-грамма 1ик, включающая в себя способ представления структурного трафа, реализацию алгоритма унификации вершин аруктурного фафа и термов, интерпретацию правил CI 1-фаммагики.

2 Разработаны CII-фамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде аруктурного графа.

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

4. На основе реализации CII-фамматик и средств работы со структурным графом разработана экспериментальная сиаема для построения внутреннего представления программ, ориентированного на их оптимизацию и распараллеливание

Список литературы диссертационного исследования кандидат технических наук Тапкинов, Батр Юрьевич, 2006 год

1. Abramov S. М., Adamowitch A. 1., Nesterov I. A , Pimenov S. P., Shevchuk Yu V. Autotransformation of evaluation network as a basis for automatic dynamic parallelizing // NA1 UG'1993 Spring Meeting "Transputer: Reserch and Application", May 10-11, 1993.

2. Allen J. R., Kennedy K. Automatic Loop Interchange // Proc of ACM SIGPLAN'84. Symposium on Compiler Construction. Montreal, Canada. June 1984. SIGPLAN NOTICES 19. Vol.6. P.233-246.

3. Allen J.R., Baumgartner D., Kennedy К , Porterfield A. PTOOL: a semiautomatic parallel programming assistant // Int Conf. on Parallel Processing. Proc. 1986. Washington, D C. IFEE Сотр. Soc. Piess 1986. P. 164 170.

4. ANTLR (ANother Iool for Language Recognition) Reference Manual. httpV/www.antlr огц

5. Aztec. A Massively Parallel Iterative Solver Libraiy for Solving Sparse Linear Systems httpV/www cs.sandia gov/CRf/a/tecl html

6. Bacon D.F., Graham S.L. and Sharp O.J. Compiler Transformations for High Performance Computing Computer Science Division Iechnical Report UCB-CSD-93-781, U.C Berkeley, Oct 1993.

7. Banerjee U., Chen S. C., Kuck D., Towle R. 1 ime and Parallel Processor Bounds for Fortran-like I oops// IEEE Irans on Computers. 1979. C-28. No.9. P 660-670

8. Bison manual http //www gnu org/software/bison/manual/index.html

9. Blume W., Doallo R , Eigenmann R. a. o. Parallel programming with Polaris // Computer 1992 - Vol 29, N 12. - P. 78 - 82.

10. Brunei-J., Cheong H., Veidenbaum A., Yew P. C CIIIFF: a parallel simulation environment for parallel systems IJniv 111 CSRD Rep 1050, April 1991.

11. Butler R. and Lusk K Monitors, Messages, and Clusters: The P4 Parallel Programming System // Paiallel Computing 1994. No.20. P.547-564.

12. Calkin R., I lempel R., I loppe H. and Wypior P. Portable Programming with the PARMACS Message-Passing 1 ibrary // Parallel Computing. Special issue on massage-passing interfaces. 1994. No.20. P.615-632.

13. Callahan D., Cooper K., Hood R. T. a.o. Parallel programming support in ParaScope// Lect. Notes Comput. Sci. 1987. Vol.297. P.91 105.

14. Callahan D., Cooper K., Hood R T. a.o ParaScope: a parallel programming environment // The Int. J. of Supercomputer Appl. 1988. Vol.2, N4. P.84 99.

15. CreusiIIet B., Iiigoin F. Inteiprocedural analyses ofTortran programs. Kcole des Mines de Paris: lech. Rep , 1997.

16. Dongarra J. J., Duff 1. S., Sorencen D C., van der Vorst 11 A. Numerical Linear Algebra for High-Performance Computers. Philadelphia: SI AM. 1998. 342 P

17. ECLiPSe User Manuel. Release 4 2 London: Imperial College, 1999.

18. Eigenmann R., McClaughry P Practical tools for optimizing parallel programs. Univ. Ill CSRD Rep 1276, Jan. 1993.

19. Express User's Guide, version 3.2 5 , Monrovia, CA: Paiasoft Corporation . 1992

20. Ferrante J, Ottenstein K. J., Warien J. D. The Program Dependence Graph and Its Use in Optimization // ACM Transactions on Programming I anguages and Systems. 1987. Vol.9 No 3. P 319-349.

21. Geist A , Beguelin A , Dongana J, Jiang W., Manchek R. and Sunderarn V. PVM: A Users' Guide and Tutorial for Networked Parallel Computing. : MIT Press 1994

22. Gelernter D Parallel programming in I inda // Technical Report 359, Yale University Department ot Computer Science, Jan., 1985.

23. Girkar M., Polychronopouios C. D. I he HTG: An intermediate representation for progiam based on control and data dependencies IJrbana-Champaign: IJniv. of Illinois. May 1991 CSRD Rep 1046

24. Guarna V A., Jr., Gannon D., Jablonowski I), a.o. Faust An integrated environment for parallel programming // IEEE Software. July 1989. P.20 26.

25. Iigh Performance Fortran. http.//www.cipc rice edu/HPri7home.html

26. Kuck D. J., Kuhn R.I I., Padua D.A , Leasure B., Wolfe M. Dependence graphs and compiler optimizations // 8th ACM Symp. on Ptinciples of Progr. Lang. Proc. Williamsburg, Va. Jan. 26-28. 1981. P.207-218

27. Kuck D. The structure of computers and computation. New York, NY: John Wiley and Sons, inc. 1978. Vol. 1.

28. Lamport L. I he coordinate method for the parallel execution of DO-loops. -Sagamore computer confetence on parallel processing, 1973.

29. Lamport L The parallel execution of DO loops // Commun. ACM. 1974. V. 17, N2 P 83 -93.

30. Message Passing Interface I orum MPI: A Message-Passing Interface Standard // Int J Supeicomputer Applications. 1994. No.8. (3/4). Special issue on MPI.

31. Message Passing Interface (MPI) Foium Home Page, http://www.mpi-forum org

32. Padua D I he Delta program manipulation system. Preliminary design. Univ. Ill CSRD Rep 880, June 1989.

33. Pereira F , Warren D Definite Clause Grammars for I anguage Analysis a Survey of Formalism and Comparison with Augment Transition Networks // Artificial Intelligence. 1980. V 13 P. 231-278.

34. Pingali K Dependence flow giaphs: An algebraical approach to program dependencies Cornell Univ Dept Comp Sci. Tech. Rep. 90-152. Sept. 1990.

35. Polychronopoulos С. D., Kuck D. J , Padua D. Л. Execution of parallel loops on parallel processor systems // Proc. of International Conf. Parallel Process. 19-22 Aug. 1986 P.519-527.

36. Polychronopoulos C., Banerjee (J Processor allocation for hoii/ontal and vertical parallelizm and related speedup bounds // IEEE Iransactions on computers.1987. Vol.C-36. No.4. P. 410-420.

37. Wilson R.P., French R.S , Wilson C.S., a.o. SUIF: An infrastructure for research on parallelizing and optimizing compilers // SIGPLAN Not. 1994. -Vol 29, N 12 - P 31-37

38. Wolfe M , Banerjee U. Data Dependence and Its Application to Parallel Processing // International Journal of Parallel Programming. 1987. Vol.16. No.2. P 137-178

39. Аллеи P, Кеннеди К Ароматическая трансляция Фор фан-программ в векторную форму Векторизация профамм: теория, методы, реализация. Сб статей Москва Мир 1991. С 77 140.

40. Арапов Д. М., Калинов А. Я., Ласювенкий A. JI., Ледовских И. Н., По-сыпкин Н. А. Язык и система профаммирования для высокопроизводительных параллельных вычислений на неоднородных сетях // Программирование. 2000. N4. С. 55 80.

41. Ахо А.В, Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструменш.: Пер. с шил. М.: Издаюльский дом «Вильяме», 2001. -С. 500.

42. Ахо А В, Ульман ДД 1еория синтаксическою анализа, перевода и компиляции. 1.1. Синтаксический анализ. М.: Мир, 1978.

43. Бабичев А В., Лебедев В.Г Распараллеливание профаммных циклов // Программирование. 1983. N5 С.52-63.

44. ЬукаювА А., Дацюк В Н, Же гул о А И. Программирование многопроцессорных вычислительных сис1ем. Ростов-на-Дону: ЦВВР, 2003. С. 191 -206

45. Вальковский В. А. Распараллеливание алюришов и программ. Структурный подход. Москва: Радио и связь. 1989. 176 с.

46. Вальковский В. А. Параллельное выполнение циклов. Меюд параллелепипедов//Кибернетика 1982 N2 С. 51-62.

47. Вальковский В А Параллельное выполнение циклов. Метод пирамид // Кибернетика 1983 N5 С 51-55

48. Воеводин В В. Математические модели и методы в параллельных процессах Москва-Наука 1986 296 с

49. Воеводин В В, Воеводин Вл.В Параллельные вычисления. СПб.: БХВ-Петербург, 2003 с 436.

50. Воеводин Вл. В 1еория и практика исследования параллелизма последовательных программ //11рограммирование. 1992. № 3. С.38-54.

51. Евстигнеев В.А., Касьянов В.II. Инструмешальная сиаема для изучения преобразований программ // Интеллектуализация и качеаво программного обеспечения. Новосибирск- НСИ СО РАН, 1994. с. 90-99.

52. Евстигнеев В.А., Мирзуитова ИЛ. Анализ циклов выбор кандидатов на распараллеливание. Препринт ИСИ СО РАН. № 58. Новосибирск, 1999. -48 стр.

53. Евстигнеев В.А , Мирзуитова ИЛ. Иерархический граф заданий: свойства и алгоритм построения // Проблемы конструирования эффективных и надежных программ -Новосибирск: ИСИ СО РАН, 1995. С. 53 - 69.

54. Евстигнеев В.А., Спрогис С В Векторизация программ. Векторизация программ теория, меюды, реализация. Сб. статей. Москва: Мир. 1991. С 246-271.

55. Ершов А П. Современное состояние геории схем программ // Проблемы кибернетики. М : Наука, 1973. - Вып. 27. - С.87-110.

56. Жегуло О. А. Непроцедурное представление преобразований программ в системе поддержки распараллеливания // Компьютерное моделирование. Вычислительные технологии. Рос юв-на-Дону: ЦВВР, 2003. С. 27-40.

57. Касьянов ВН., Евстигнеев В А Графы в программировании: обработка, визуализация и применение СПб . БХВ-Петербург, 2003.

58. Касьянов В. Н. Оптимизирующие преобразования программ. Москва: Наука 1988 240 с71 .Касьянов В. H. Iеоретико-графовые задачи анализа управляющих графов транслируемых npoipaMM. Исследования по прикладной теории графов. Новосибирск:. 1986. С.9-26.

59. Касьянов В. П., 1рах1енброт М. Ь. Анализ струк1ур программ в 1лобаль-ной оптимизации // Всесоюзн. симпозиум по меюдам реализации новых алгоришических языков. Сб. трудов Новосибирск. 1975. часть 2. С. 143-159.

60. Кнут Д. Семаншка контекстно-свободных языков // Семантика языков программирования. М.: "Мир", 1980.-С. 137-161.

61. Колмогоров А.Н., Драгалин А Г. Матемашческая логика. М.: Изд-во МГУ, 2005.

62. Коновалов 11 А., Крюков В. А , 1 loi ребцов А А , Сазанов К). JL C-DVM -язык разрабо1ки мобильных параллельных профамм // Программирование. 1999. № 1. С. 20- 28.

63. Крицкий С.П. Предикативные фамматики и аксиомашческое определение языков программирования и переводов // Компьютерное моделирование Вычисли 1ельные технологии. Росюв-на-Дону: ЦВВР, 2003. С. 67 -90.

64. Крицкий С. II, Тапкинов Б 10 Реализация оптимизирующих преобразований программ с помощью структурных предикативных грамма!ик // Приложение к журналу «Извес1ия вузов. Северо-Кавказский регион. Естественные науки», 2006, № 1, С 3-13.

65. Крицкии С П., Тапкинов Ь 10. Сиаема посфоения оптимизирующих и распараллеливающих компиляторов // Приложение к журналу «Известия вузов Северо-Кавказский регион. L ci ее i венные науки», 2006, №9, С. 2428

66. Лазарева С А. Использование многоуровневой) внуфеннею представления в автоматическом распараллеливании программ для мноюпроцессор-ных ЭВМ Дис к-та 1ехн наук. Ростов-на-Дону, 2000. - 157 с.

67. ВО.Малинина Ю.В. Информационная система I РАСНФОРМ но преобразованиям про1рамм. // Проблемы конструирования эффективных и надежных профамм. Новосибирск, 1995 - С 128-136.

68. Мартышок В.В. Об анализе графа переходов для операторной схемы // Журн. вычисл. математики и мат. фи зики. 1965. - Т. 5, № 2. - С. 298-310.

69. Немнютин С. А., Слесик О. Л. Современный Фортран. Самоучитель. СПб.: БХВ-Петербур1, 2003. С. 353 365.

70. Падуа Д , Вольф М. Оптимизация в компиляторах для суперкомпьютеров. Векюризация профамм: теория, метды, реализация. Сб. статей. Москва: Мир. 1991. С. 7-47.

71. Пакулев В. В. Сложность анализа параллельных структур произвольных фортрановских циклов. Москва: ОВМ АН СССР. 1989. Препринт №225. 20 с.

72. Г1опосин И. В. К обоснованию алтршмов оптимизации программ // Программирование. 1979.№ 2

73. Поттосин И. В. О кошексгных условиях объединения и расчленения циклов. Сб Языки и системы программирования. Новосибирск: препринт ВЦ СО РАН 1979.

74. Поттосин И В. Оптимизирующие преобразования и их последовательность. Системное программирование Новосибирск: . 1973. часть 2. С. 128137

75. Поттосин И. В , Юршнова О. В Обоснование преобразования чистки циклов // Программирование. 1980. №.5. С.З-16.

76. Проблемы системного и теоретического программирования Сборник научных трудов Новосибирск. 1 НУ. 1984. 172 с.

77. Тапкинов Б 10 Преобразование правил структурной предикативной грамматики в правила ОС-грамматики // Груды аспирантов и соискателей Ростовского государственного университета, Ростов-на-Дону, 2005, т. XI, С 28-30

78. IaiiKHHOB Б. 10. Представчение струк1урною графа и реализация алгоритма унификации ею вершин и 1ермов // Приложение к журналу «Известия вузов. Северо-Кавказский peí ион. Естеа венные науки», 2006, № 1, С 30-36.

79. Штейнберг Б. Я Магматические методы распараллеливания рекурреш-ных циклов для суперкомпьютеров с распределенной памятью. Росюв-на-Дону Изд-во Рост Ун-1 а, 2004