Главная » 2014 » Июнь » 28 » Скачать Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание. бесплатно
1:05 AM
Скачать Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание. бесплатно
Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание
Диссертация
Автор: Тапкинов, Батр Юрьевич
Название: Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание
Справка: Тапкинов, Батр Юрьевич. Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание : диссертация кандидата технических наук : 05.13.11 Ростов-на-Дону, 2006 120 c. : 61 07-5/2012
Объем: 120 стр.
Информация: Ростов-на-Дону, 2006
Содержание:
1 Введение
Глава
I Современное соеюяние иееледований в облаем и онтимизации и раепараллеливания программ
11 Различные нодходы к раенараллеливанию нрофамм
12 «Ручное» раснараллелииание
13 Автоматическое распараллеливание
14 Полуавтоматическое распараллеливание
15 Технологии нараллельно1 о программирования
16 Я?ыки иараллельпого программирования
17 Коммуникационные бибпио1еки и ин1ерфейсы параллельного программирования
18 СредеI ва ав1ома1ического распараллеливания профамм
19 Средс1ва создания и проекшровапия иараллельных программ Специализированные параллельные библиотеки
110 Различные вариан1ы внугреннего представления программ
I Угграв]гяюгций граф раф зависимости по данным Граф программггыч мвисимосгей Граф вы ювов процедур
111 Решетчатый граф
112 Граф вьгчислений программы Иерархический граф заданий
113 В ы в о д ы
Глава II Сгрукгурные предикативные грамматики и струкгурнглй граф
21 Формализмы для описания семангики языков программироваггия и построения семаггтической сгрукгургл ггрограмм Лтрибутггые грамматики DC-грамматики и DCG-нотация
22 Сгрук1урные предикативные фамматики
23 Реализация CTpyKiypiHix предикативных граммашк
24 Преде 1ав1ение структурною фафа
25 Реализация алюритма унификании верпшн структурного фафа и lepMOB
26 Преобразование нравил струк1уриои предикативной фаммагнки в иравила Пролога
27 Среде 1ва работы со струк1урным фафом
28 Выводы I лава
29 HcH0jn,30BaHne структурною графа для онтимизации и раснараллеливания программ
210 11роме/ку1 очное представление нрофаммы
211 Структура нромежуточною предсывлення
212 Элементарные преобразования
213 Построение информационных структур
214 1 Унравляющий граф
215 раф зависимос1ей но данным Граф вызовов нроцедур
216 Преобразования нрограмм
217 Про1Я1 ивание констант Удаление "мертвого" кода
218 Удаление недости/кимою кода
219 Упрощение арифмежческих выражений
220 Канонизация цикла
221 Разрезание цикла
222 7 Слияние циклов
223 Развертка цикла Результа1ы и выводы
Глава IV Структурно-предикативная система носгроения внутреннего представления нрофамм
31 Возможности сис1емы
32 Структура сис1емы
33 Рабошсо сфуктурно-нредикашвной сис1емой
34 Соноставление с ;ipyi ими системами
35 Выводы
Заключение Литература
Приложение А Онисание подмножес1в языков Си, Фортран и llacKajH Элементы языка Си Элементы языка Паскаль Элемен1ы я?ыка Фортран
Приложение В Реализация азноритмов на Прологе
Введение:
Актуальность темы. Развитие вычисли 1ельных сис1ем, появление новых апиаражых платформ и процессоров обуславливаю! необходимость разработки новых ком!!иляторов Рафаботка зффек!ивного ком!!илятора это !рудоемкий и дос1а1очно длите.чьный процесс. Од!!им из ответе!!5е!!ных этапов разработки компи.мя!ора являе1ся проектиро!за!1ие внутреннею !1редставле!!ия программ для исходного языка. От в!!у!реннего предс!ав:!ения будут зависеть важные С!зойства ком!!иля[ора, такие как переносимость !ia дру1 ие платформ!.!, модифицируемость, скорость работы, качес!во кода и т д. Су!цес1!зуе! бо1Ь!1!ое ко;!ичес!во моделей д]!я !!редставле!!ия программ, как ЧИС10 !еоретических, !ак и широко !!рименяемь!х на прак!ике: !!остфиксная !!О!ация; грехадресный код; синтаксическое дере!зо, другие гpaф-мoдeJ!и Вну!ренние представле!!ия в совреме!!!!!>!х ком!!И]!ягорах, как !!равило, реализу!отся в виде таких струк!ур, как списки и дерев!>я. В некоторых системах оптимиза!1ии и распара1лелива!!ия !!ро!рамм, таких как Polaris [9J, SUIF/SUIF2 [47], ОРС [96], вну!реннее представление !!ро[рамм реализовано в виде иерархии классов на объектно-орие!!тирова!!ном языке. Ос!1овное преимущество предста!зления в таком виде j o !!рос!ота проектиро!зания, модифицируемое 1ь и расширяемость. За преобразование исходной программы во в!!утре!!!!ее !1редставление отвечае! анализирующая часть ком!!иля!орс1 или парсер Разрабо!ка !!арсера с ну]!я является очень трудоемкой задачей и может занять М!!0!0 времени. Поэтому, чтобы ускорить и облегчить процесс е!0 разработки, как правило, ис!!ользуются специаль!!!.!е инс!румен!Ь!, так называемые !енераторы компиляторов (Lex/YACC [52], Flex/Bison [9]). Но даже при иепо.чьзовании гене5 раюров компи.1ягоров за рафабо1чиком царсера остется решение осцовнои задачи онисание сишаксиса и семаншки исходною языка с номощью некоторого формализма. Сегодня для решения этой задачи чаще всего исцоль5уются афибутные грамматики [73], которые нозвочяют онисыва1ь син1аксис и семантику языка блаюдаря наличию а1рибутов, связанных с каждым грамматическим символом, и семантических правил, вычисляющих эти атрибу1Ы. В атрибутной грамматике обяза1ельно доллсен бы1ь задан нравильный норядок вынолнения семаншческих правил, связанных с узлами дерева разбора. Установление э ю ю норядка являе1ся нефивиальной задачей, решение коюрой требуе1 oi программис1а донолпительных временных зафа1 и О1влекаето1 ре1иения основной задачи. Кроме того, при иснользовании афибутной граммашки построение BHyipeiHiero нредставления ирограммы, огличною от дерева разбора, нужно онисывать в нроцедурцом виде. В 1980 году Ф. Перейрой и Д. Уорреиом были оцисаиы 1рамматики DCG [35] (Definite Clause Grammars), О1носяш,иеся к классу логических грамматик Сейчас э т грамматики неизменно включаются во все развитые системы программирования на языке 11роло1 Э1и 1рамматики в оьчичие от атрибутных грамматик, не требую1 задания строгого порядка выполнения семантических правил Однако построение семанжческой структуры нрограммы с номощью DCG, как и в атрибу1ных 1рамматиках, нулсно онисывать в нроцедурном виде (ца языке Пролог) В 2003 году С II. Крицкий оиисал струк1урные предикативные фамматики [76] (СП-грамматики), основанные на нонятии струкгурною графа црограммы и расширяющие DCG цроцедурой уцификации вершин структурного графа и термов Эти грамматики обладаю! !зсеми возможностями DCG и нри этом позволяют онисывать ностроение сема!1тической сфук!уры программы и работу с ней в непроцедурном виде Одиако эти грамматики не нашли широкого применения из-за огсутствия и\ реа1иза!1ии, разработка которой предеывляется aKiyaibnoH задачей развития еие1ем пое1роеиия компилягоров. Цель раб()1ы и задачи исследования. Целью данной дисеертационной работы являетея реа.1ишция етрук1урных предикашвных грамматик и их использование для построения внутреннею представления программ, ориентированною на их оншмизацию и распараллеливание. Для достижения нос1авленной цели решаются следующие задачи: 1. Создание нрограммной реализации СП-фамматик, представления структурною графа и алгоритма унификации верншн структурного графа и термов. 2. Применение СП-граммажк дтя оиределения и нос1роения внуфеннего представления программ, наниса1Н1ы\ на нроцедурных языках, в виде структурною фафа. 3. Реализация с помощью средеiв работы со сфукгурным фафом алгори[мов построепия информационных сфуктур, иснользуемых при оп1имизации и расиаралпеливапии, а также набора ои1имизиру1О1Цих и распараллеливающих преобразований. 4. Разработка экспериментальной струк1урно-нредикативной системы для построепия внутреннего нредствления нро1рамм, ориеншрованного на их оптимизацию и распараплеливание. Методы исследований. В диссертациоппой pa6oie использовались методы 1еории трансляции и нреобразовании ирофамм, элемеип,1 1еории графов При реализации программпою обеспечения использовались принципы логического программирования Достоверность и обосиоваииость резулыаюв. Получе1Н1ые результаты прон]ли нроверку в ходе нрактического исиользования разработанного программного комплекса для проведепия многочисленных жснериментов с исходными текетами тестовых и реальных нрофамм. Научиая новизна. Иредюлены мегоды и а.чюришы автома1ического построения структуртюго фафа и преобразовапия правил СП-фамматики в правила Пролога. Предчожен способ испольюнания унификации вершин структурною графа и термов для построения, анализа и нреобравования внуфеннего нредсшвтения программ ripaKiHMecKavi ценность. В ходе исследовательской работы была разработана жснеримешальная сис1ема дня носiроения внуфеннего представления программ, когорое ориентировано на их опшмизацию и распараллеливание. Эта система может быть использована для обучения, исследований и зксиериментов в области нреобразований ирограмм. ripoipdMMHO реатизованные С11-1рамматики мо1ут бьпь иснользованы в качестве инструмен1а при разработке опшмизирующих и распараллеливающих компиляторов. Анробацня рсзультаюв работы. Основные резульгаты диссертаци01Н10Й работы докладывались и обсуждались на Всероссийской научной конференции "Научный сервис в сети Ин1ернет: техноло1ии параллельного программирования", г Новороссийск, 2006 г., на научно-методической конференции "Современные информационные 1ехнологии в образовании: Южный федеральный oKpyi", i Ростов-на-/1,ону, 2006г., на научных семинарах кафедр ИВЭ и АДМ MexMaia РГУ, на научно-исследова1ельском семинаре ЮГИНФО Р[ У, 2006 г. Публнканнн. По результатам выполненных исследований онубликовано 6 печатных работ, в том числе 2 в соавюрстве Пз них 3 статьи в российском рецензируемом журнале, 1 стагья в сборнике трудов асниранюв РГУ и 2 в 1езисах докладов всероссийской и pei иональной конференций. В совмесшых работах [77, 78] личный вклад авюра заключаегся в исследованиях и разработках, связанных с реализацией сфуктурных предикативных грамматик, представления струк1урно1О графа, ал1 ори гма унификации и экснериментальной сис1емы Объем и содержаннс работы. Диссерития состоит из введения, че1Ырех глав, заключения, сниска ли1ера1уры и нрилолсений.Во введении обоснована актуа-чьность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и нрактическая значимость резулыатов, укамны положения, выносимые иа. защиту, и KpaiKO аннотировано содержание глав Первая 1.1ава посвящена обзору современного состояния исследований в области оптимизации и распарач [еливапия нро1рамм. Рассма1риваются 3 осно1зиых нодхода к раснараллеливанию программ: «ручное», автоматическое и полуавтомажческое раснараллеливание. Приводится обзор различных техноло1ий параллельною программирования. Рассмафиваются расншрения фадиционтпх иоследовате-чьных языков, коммуникационные библиотеки и ин1ерфейсы параллельного профаммирования, специализированные параллельные библиотеки, среде 1ва автоматическою распараллеливания программ и средства создания и нроекшрования нараллельных программ. Приводится обзор и анализ различных вариантов внуфеннего представления программ. Вторая 1лава диссертации иосвящепа подробному описанию формализма СП-граммашк, их использованию для пос1роения семантической структуры программы, а 1ак л<е реализации 1их фамматик. Приводятся определения атрибуптой грамматики, 1рамма1ики DCG, сфук1урной предикативной грамматики и струк1урно1о графа, онисьнзае1ся алгориш унификации вершин структурною графа и термов 11роизводится сравнение описания семантической С1руктуры программ с помощью атрибушых и СП-фаммагик, коюрое показывает преимущество непроцедурпою описания с помоп1ью СП-грамматик Описывается профаммная реализация СП-грамматик. Третья