WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 28 |
становится необязательным. Проводится обоснование алгоритма и рассматриваются его основные свойства.

Предисловие Во второй статье того же автора «Язык запросов к совокупности XMLдокументов, соединенных при помощи ссылок языка XLink» предлагается В сборнике представлены статьи сотрудников Института системного язык, который позволяет приложению прозрачным образом формулировать программирования и некоторых других организаций, описывающие научные запросы к ссылкам XLink и осуществлять переходы по определяемым этими результаты исследований, полученные в 2003-2004 гг. В статьях обсуждаются ссылками дугам. Язык инкапсулирует сложности синтаксиса XLink от как теоретические вопросы, так и проблемы реализации программных систем.

приложения и предоставляет более высокий уровень абстракции при обработке Во второй части сборника представлены 10 статей. совокупности XML-документов, соединенных ссылками языка XLink.

В статье П.М. Довгалюка «Анализ и оптимизация циклов с помощью В статье М.П. Рекуц «Виды ограничений целостности в базах XML-данных» на производящих функций» представлены усовершенствования метода основе анализа потребностей современных приложений, работающих с XMLраспространения констант, использующего GSA-представление (Gated Single СУБД, выявляются виды ограничений целостности, которые должны Assignment), позволяющие алгоритму находить большее количество констант, поддерживаться XML-СУБД, и предлагаются средства определения этих видов чем исходный алгоритм. ограничений с учетом специфики XML-модели данных и опыта, накопленного разработчиками реляционных СУБД. Работа выполнена при поддержке Во второй статье того же автора «Усовершенствованный алгоритм грантами РФФИ.

распространения констант с использованием GSA-представления» рассматривается метод анализа и оптимизации циклов с помощью В статье Г.И. Малашонка, А.И. Аветисяна, Ю.Д. Валеева и М.С. Зуева производящих функций, состоящий в поиске выражений для конечных «Параллельные алгоритмы компьютерной алгебры» рассматривается значений переменных, которые вычисляются в цикле и замене цикла разрабатываемая в рамках среды ParJava система компьютерной алгебры. Цель вычислениями по формуле. разрабатываемой системы – предоставить возможность эффективного использования параллельных вычислительных систем для проведения Статья В.А. Семенова, С.В. Морозова и С.А. Пороха «Стратегии объектноаналитических расчетов.

реляционного отображения: систематизация и анализ на основе паттернов» посвящена методам отображения прикладных объектно-ориентированных В статье С.С. Гайсаряна и П.Н. Яковенко «К вопросу о генерации начальных данных в реляционную модель. Проводится систематизация этих методов, а данных, обеспечивающих заданную трассу SPMD-программы» исследуется также их анализ на основе введенной системы паттернов. Задача проблема автоматизированной генерации входных данных для SPMDфункционально полного отображения моделей данных рассматривается на программы на основании ее исходного текста.

примере EXPRESS-нотации, получившей распространение в качестве Вторую часть сборника завершает статья А.В. Инюхина «Открытая Т–система:

стандартного средства информационного моделирования научных и распределённые вычисления в Internet», в которой рассмотрены возможности промышленных данных.

технологии автоматического динамического распараллеливания, В статье В.А. Семенова, С.В. Морозова и О.А. Тарлапана «Инкрементальная реализованные в открытой Т–системе для выполнения распределённых верификация объектно-ориентированных данных на основе спецификации вычислений в среде Internet, а также представлены результаты экспериментов, ограничений» рассматриваются задачи полной и инкрементальной иллюстрирующие перспективы подобных вычислений.

верификации объектно-ориентированных данных. На основе теории графов строится формальный аппарат, а также описываются разработанные методы Член-корреспондент РАН В.П. Иванников инкрементальной верификации, использующие статический анализ спецификации ограничений и позволяющие локализовать область потенциальных нарушений при изменении данных. Результаты этой и предыдущей статей получены при поддержке РФФИ (грант N 04-01-00527) и Фонда содействия отечественной науке.

В статье Д.А. Лизоркина «Оптимизация вычисления обратных осей языка XML Path при его реализации функциональными методами» предлагается алгоритм, позволяющий построить вычисление выражений XPath таким образом, что наличие указателей с дочерних узлов на родительские узлы в дереве документа 5 2. Алгоритм распространения констант, использующий GSA-представление Алгоритм распространения констант, описанный в [8], использует SSAпредставление (Static Single Assignment) программы. В SSA-форму программа Усовершенствованный алгоритм трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки распространения констант с объединения нескольких путей, то в точках объединения необходимо добавить использованием GSA-представления специальную форму присваивания, названную -функцией. -функция имеет форму V (R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке, и j-й П.М. Довгалюк операнд -функции ассоциируется с j-м предшественником узла. Если путь (Pavel.Dovgaluk@nov.astrosoft.ru) выполнения программы лежит через j-го предка узла, то переменная V Аннотация. В данной статье представлены усовершенствования метода распростра- получает значение, связанное с j-м аргументом. Каждое исполнение -функции нения констант, использующего GSA-представление (Gated Single Assignment), позвоиспользует только один из аргументов, но который именно – зависит от того, ляющие алгоритму находить большее количество констант, чем исходный алгоритм.



из которого узла получил управление данный узел.

В работе [8] алгоритмы распространения констант разделены на те, которые 1. Введение находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы.

Распространение констант – хорошо известная проблема глобального анализа Время работы такого алгоритма пропорционально размеру SSA-графа, и потока данных. Цель распространения констант состоит в обнаружении каждое SSA-ребро обрабатывается максимум два раза.

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

будет постоянным, то выполняемое ребро будет добавлено к рабочему списку.

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

неоднократному вычислению одних и тех же выражений.

Технологии распространения констант позволяют решить следующие задачи:

В методе, использующем GSA, если символ использует значение из точки - Выражения, вычисляемые на этапе компиляции не нужно вычислять в слияния, то вычисляется значение предиката и определяется путь, из которого процессе выполнения программы;

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

нужный аргумент -функции, а если нет, то самое лучшее, что можно получить - увеличение эффективности встраивания процедур.

с помощью данного метода – это взять функцию meet от -аргументов.

Распространение констант совместно со встраиванием процедур (когда многие Чтобы выполнить данную задачу, необходимо расширить SSA-представление параметры процедур являются константами) позволяет избежать разрастания до GSA (Gated Single Assignment), введенное в работе [3], которое позволяет кода, которое часто является результатом встраивания процедур в места из вычислять условные выражения, базирующиеся на предикатах. В данном предвызовов.

ставлении -функции заменяются на - и -функции. Большая часть -функций, расположенных в заголовках циклов переименовывается в -функции, тогда как 7 if lattice(predicate) = C then остальные преобразуются в -функции. -функция имеет вид: v = (P, v1, v2), lattice(t) = lattice value of -argument что означает, что v принимает значение v1, если P=true, и v2, если P=false. В corresponding to C такой форме -функция представляет собой конструкцию if-then-else, но она else lattice(t) = П of all -arguments of t может быть расширена для работы с более сложными условными конструendif кциями. Алгоритм для преобразования -функций в - и -функции -function: lattice(t) = представлен в работе [6].

-function: lattice(t) = lattice(-argument) В данном алгоритме используется представление программы в виде базовых default: lattice(t) = блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны end case между собой и вместе образуют граф потока данных. Кортежи имеют end propagate следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда, ssa_link – связь, порождаемая алгоритмом преобразования 4. Недостатки и предлагаемые изменения программы в SSA-форму. Поля left, right, ssa_link представляют собой В работе [7] показано, что арифметические и логические выражения, указатели на соответствующие кортежи. Каждая операция (кортеж) также включающие -функции, можно преобразовывать в несколько вложенных имеет ассоциированное значение – lattice, принадлежащее множеству значений -функций и арифметических выражений, что позволяет получать константные из решетки и представляющее собой результат выполнения операции, который выражения даже в тех случаях, когда аргументы исходного арифметического может быть получен на этапе компиляции.

или логического выражения не являются константами. Это видно по следующему примеру:

3. Исходный алгоритм if P then t tuples a1 = lattice(t) = T b1 = unvisited(t) = true else a2 = Visit all basic blocks B in the program b2 = Visit all tuples t within B endif if unvisited(t) then propagate(t) a3 = (P, a1, a2) b3 = (P, b2, b3) propagate (tuple t) if a3 > b3 then unvisited(t) = false...





if ssa_link(t) 0 then endif if unvisited(ssa_link(t)) В данном случае переменные a3 и b3 будут всегда равны независимо от then propagate(ssa_link(t)) значения предиката P. Алгоритм, предложенный в [5], не сможет определить lattice(t) = lattice(t) П lattice(ssa_link(t)) отношение значений переменных в данной ситуации.

endif Предлагаемые изменения алгоритма привели бы предикат a3 > b3 к виду: (P, if unvisited(left(t)) then propagate(left(t)) if unvisited(right(t)) then propagate(right(t)) a1 > b1, a2 > b2) = (P, true, true) = true.

case on type (t) Предлагаемые изменения алгоритма касаются обработки арифметических и constant C: lattice(t) = C логических выражений и состоят в следующем (E1, E2 – аргументы arithmetic operation:

арифметического (логического) оператора):

if all operands have constant lattice value 1. E1 и E2 не содержат -функций, либо обе содержат -функции с then lattice(t) = arithmetic result of lattice разными предикатами. Используется обычное правило для вычисления values of operands арифмети-ческих и логических выражений.

else lattice(t) = endif 2. Один из аргументов (E1 для определенности) содержит -функцию.

store: lattice(t) = lattice(RHS) Выполняется следующее преобразование:

-function: lattice(t) = П of -arguments of t (P, V1, V2) op E2 = (P, V1 op E2, V2 op E2).

-function:

9 if all operands have constant lattice value 3. E1 и E2 содержат в себе -функции с одинаковыми предикатами.

then lattice(t) = arithmetic result of lattice Выполняется следующее преобразование:

values of operands (P, V1, V2) op (P, V3, V4) = (P, V1 op V3, V2 op V4).

else lattice(t) = endif 5. Новый алгоритм store: lattice(t) = lattice(RHS) -function: lattice(t) = lattice(left(t)) П t tuples lattice(t) = T lattice(right(t)) -function:

propagate(predicate(t)) unvisited(t) = true if lattice(predicate(t)) = C then Visit all basic blocks B in the program lattice(t) = lattice value of -argument Visit all tuples t within B corresponding to C propagate(t) else lattice(t) = lattice(left(t)) П lattice(right(t)) propagate (tuple t) endif if not unvisited(t) return -function: lattice(t) = unvisited(t) = false -function: lattice(t) = lattice(-argument) label restart:

default: lattice(t) = if ssa_link(t) 0 then end case ssa_link(t) end propagate lattice(t) = lattice(t) П lattice(ssa_link(t)) Функция join_common_predicate объединяет две -функции с одинаковыми endif предикатами в одну:

if type(t) arithmetic operation join_common_predicate (tuple t) propagate(left(t)) propagate(right(t)) tuple new_t = new -function endif predicate(new_t) = predicate(left(t)) case on type (t) constant C: lattice(t) = C left(new_t) = new operation node, same as t arithmetic or logic operation: ssa_link(left(new_t)) = unvisited(left(new_t)) = true if type(left(t)) = -function lattice(left(new_t)) = T or (type(right(t)) = -function left(left(new_t)) = left(left(t)) then right(left(new_t)) = right(left(t)) if type(left(t)) = -function and (type(right(t)) = -function right(new_t) = new operation node, same as t or type(ssa_link(right(t))) = -function) ssa_link(right(new_t)) = and (predicate(left(t)) = predicate(right(t)) unvisited(right(new_t)) = true or type(ssa_link(left(t))) = -function) lattice(right(new_t)) = T then left(right(new_t)) = left(right(t)) join_common_predicate(t) right(right(new_t)) = right(right(t)) goto restart else t = new_t join_gamma_with_operand(t) ssa_link(t) = goto restart lattice(t) = T endif end join_common_predicate else Функция join_gamma_with_operand – объединяет -функцию и операнд, propagate(left(t)) который не является -функцией:

propagate(right(t)) endif 11 join_gamma_with_operand (tuple t) ветвления) или алгоритм классификации выражений, описанный в [2]. Первый tuple g, op вариант позволяет выполнить сравнения без значительных затрат времени.

tuple g_left = new operation node, same as t Второй позволяет найти одинаковые предикаты, которые не принадлежат tuple g_right = new operation node, same as t одному оператору ветвления, но требует дополнительных затрат времени на if type(left(t)) = -function then классификацию предикатов.

g = left(t) op = right(t) Литература left(g_left) = left(g) 1. А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструменты.:

left(g_right) = right(g) Пер. с англ. – М.: Издательский дом «Вильямс», 2001.

right(g_left) = op 2. B. Alpern, M. N. Wegman, F. K. Zadeck. Detecting equality of variables in programs, right(g_right) = op 1988.

else 3. R. A. Balance, A. B. Maccabe, and K. J. Ottenstein. The program dependence web: a op = left(t) representation supporting control-, data-, and demand-driven interpretation of imperative g = right(t) languages. In Proc. ACM SIGPLAN’90 Conf. on Programming Language Design and left(g_left) = op left(g_right) = op Implementation, June 1990.

right(g_left) = left(g) 4. S. Muchnick. Advanced compiler design and implementation, 1997.

right(g_right) = right(g) 5. E. Stoltz, M. Wolfe, M. P. Gerlek. Constant propagation: a fresh, demand-driven look, endif 1994.

left(g) = g_left 6. E. Stoltz, M. Wolfe, and M. P. Gerlek. Demand-driven constant propagation. Technical right(g) = g_right Report 93-023, Oregon Graduate Institute, 1993.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 28 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.