А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 151

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 151)

9.3 Основы анализа потока данных Рассмотрев несколько практических примеров абстракций потока данных, перейдем к изучению схем потоков данных в общем виде. Мы формально ответим на ряд фундаментальных вопросов об алгоритмах потоков данных. Глава 9. Машинно-независимые оптимизации 1. При каких условиях корректен итеративный алгоритм, использующийся в анализе потока данных? 2. Насколько точно решение, полученное итеративным алгоритмом? 3. Будет ли сходиться итеративный алгоритм? 4.

Каков смысл решения уравнений? В разделе 9.2 мы неформально ответили на каждый из этих вопросов при изучении задачи о достигающих определениях. Вместо ответов на те же вопросы для каждой из последующих задач с нуля мы опирались на аналогию с уже рассмотренной задачей. Здесь же мы представим общий подход, который раз и навсегда отвечает на все поставленные вопросы для большого семейства задач потоков данных. Сперва мы определим желательные свойства схем потоков данных и докажем в качестве следствия этих свойств корректность, точность н сходимость алгоритма потока данных, а также выясним смысл его решения. Таким образом, чтобы понять старые алгоритмы или сформулировать новые, мы просто показываем, что предложенные определения задач потоков данных обладают рядом свойств, и тут же получаем ответы на все поставленные выше сложные вопросы.

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

Структура анализа потока данных (нага-йотг апа1уз)а 1гашец'огк) (Р, ); Л, Г) состоит из 1. направления потока данных Р, который может принимать значение "прямой" илн "обратный"„. 2. полурешетки (см. соответствующее определение в разделе 9.3.!), включающей область олределения значений $' и оператор сбора Л; 3. семейства г передаточных функций, областями определения и значений которых является 1'; зто семейство должно включать функции, подходящие для граничных условий и представляющие собой константные передаточные функции для входного и выходного узлов любого графа потока. 9.3.1 Полурешетки 1?олурешетка (аеш1!ап)се) представляет собой множество )' и бинарный оператор сбора Л, такой, что для всех х, р и х из Ъ' выполняются следующие соотношения.

745 9.3. Основы анализа потока данных 1. х Л х = х (идемпотеитиость) 2. х Л у = у Л х (коммутативиость) 3. хЛ (у Л л) = (х Л у) Л г (ассоциативиость) Полурешетка имеет верхний элемент, обозначаемый как Т, такой, что для всех х б 1' выполняется Т Л х = х Полурешетка может иметь (необязательио) нижний элемент, обозначаемый как 3, такой, что для всех х Е Ъ' выполняется 3 Л х = 3 Частичные порядки Как мы увидим, оператор сбора полурешетки определяет частичный порядок значений из области определения. Отношение < представляет собой частичный порядок (разт)а! оп!ег) иа множестве к', если для всех х, у и л из Ъ' выполняются следующие соотношения.

1. х < х (рефлексивиость) 2. Если х < у и у < х, то х = у (антисимметрив) 3. Если х < у и д < л, то х < г (транзитивность) Пара (1', <) называется частично упорядоченным множеством (рагйа!1у огдегес) зе1; сокрашеиио — рояе1в). Для частично упорядоченного множества удобно ввести также отношение <, определяемое как х < у тогда и только тогда, когда (х < у) и (х эе у) Частичный порядок в полурешетке Определим частичный порядок для полурешетки (Ъ; Л).

Дпя х и у из к' определим х < у тогда и только тогда, когда х Л у = х Поскольку оператор сбора Л идемпотеитеи, коммутативеи и ассоциативеи, определенный таким образом порядок < является рефлексивным, аитисимметричиым и траизитивиым. Чтобы понять, почему это так, заметим следующее. ° Рефлексивиоствс для всех х х < х. Доказательство этого факта основано иа том, что х Л х = х в силу идемпотеитиости оператора сбора. Мы не рискнули перевести это сокращение на русский язык, получив в результате "чум".— Прим. лер. 746 Глава 9. Машинно-независимые оптимизации ° Антисимметрия. Если х < д и д < х, то х = д. По определению х < д означает х Л д = х, а д < х означает д Л х = д. В силу коммутативности оператора Л получаем х = (х Л д) = (д Л х) = д. ° Транзитивность.

Если х < д и д < л, то х < л. По определению х < д и д < л означают х Л д = х и д Л л = д. Использование ассоциативности оператора сбора дает (х Л л) = Их Л д) Л л) = (х Л (д Л л)) = (х Л д) = х. Поскольку показано, что х Л л = х, получаем х < л, что и доказывает транзитивность. Пример 9.18.

Операторы сбора, использованные в разделе 9.2, — это операторы объединения и пересечения множеств. Оба они идемпотентны, коммутативны и ассоциативны. Для объединения множеств верхним элементом является Я, а нижним — универсальное множество У, поскольку для любого подмножества х С У выполняются соотношения И 0 х = х и У 0 х = У.

В случае пересечения множеств Т представляет собой У, а 1 — О. Область определения значения полурешетки И в этом случае представляет собой множество всех подмножеств У, которое иногда называется показательным множеством (ротчег зег) У и обозначается как 2~. Для всех х и д из к' из соотношения хыд = х вытекает хДд; таким образом, частичный порядок, продиктованный объединением множеств, представляет собой Д, включение множества.

Соответственно, частичный порядок, продиктованный пересечением множеств, представляет собой С, содержание в множестве. Иначе говоря, для пересечения множеств множества с меньшим количеством элементов рассматриваются данным частичным порядком как меньшие. Однако в случае объединения множеств меньшими считаются множества с большим количеством элементов.

То, что ббльшие по размеру множества оказываются меньшими в частичном порядке, противоречит интуитивному взгляду, но эта ситуация — неизбежное следствие принятых определенийт. Как говорилось в разделе 9.2, обычно имеется много решений уравнений потоков данных, среди которых наибольшее решение (в смысле частичного порядка <) является наиболее точным. Например, для достигающих определений наиболее точным среди всех решений уравнений потоков данных является уравнение с наименьшим количеством определений, которое соответствует наибольшему элементу в частичном порядке, определенном оператором сбора — объединением.

В случае доступных выражений наиболее точным решением является решение с наибольшим количеством выражений. И вновь это решение является наибольшим в частичном порядке, определенном пересечением в качестве оператора сбора. а "Если определить частичный порядок не как <„а как >, то проблема останется, просто вместо пересечений проблемными окажутся объединения множеств. 747 9.3. Основы анализа потока данных Наибольшие нижние границы Существует еще одно полезное соотношение между оператором сбора и определяемым им частичным порядком.

Предположим, что (К, Л) — полурешетка. Иаибольшей нижней границей (йтеагез1 1оч ег Ьошк1 — я!Ь) области определения элементов х и у является элемент д, такой, что 1. д<х; 2. д<у; 3. если г — любой элемент, такой, что е < х и е < у, то е < д. Отсюда следует, что х Л у является их наибольшей нижней границей. Чтобы увидеть, почему это так, положим д = х Л у и рассмотрим следующую аргументацию. ° д < х, поскольку (х Л у) Л х = х Л у. Доказательство включает простое использование ассоциативности, коммутативности и идемпотентности: д Лх = ИхЛу) Лх) = (х Л (уЛх)) = = (х Л (х Л у)) = Цх Л х) Л у) = = (хЛу) =д в д < у доказывается аналогично. ° Предположим, что г представляет собой любой элемент, такой, что г < х и < у. Мы утверждаем, что е < д, а следовательно, е не может быть наибольшей нижней границей х и у, если только не равно д.

Вот доказательство этого утверждения: (г Лд) = (х Л (х Л у)) = Ие Лх) Л у). Поскольку г < х, мы знаем, что (гЛх) = г, так что (гЛд) = (еЛу). Так как е < у, нам известно, что е Л у = е, а следовательно, е Л д = ж Итак, мы доказали, что е < д, и делаем вывод, что д = х Л у является единственной наибольшей нижней границей х и у.

Диаграммы решеток Зачастую полезно изображать область определения г' в виде диаграммы решетки, представляющей собой граф, узлами которого являются элементы 1:, а ребра направлены вниз от х к у, если у < х. Например, на рис. 9.22 показано множество Ъ' для схемы потоков данных для достигающих определений, в которой имеются три определения: йь пз и пз. Поскольку < в данном случае — З, ребра направлены вниз от любого подмножества из этих трех определений к каждому из их надмножеств. В силу транзитивности < для удобства на диаграмме будут 148 Глава 9. Машинно-независимые оптимизации Объединения, наименьшие верхние границы и решетки Над элементами частично упорядоченного множссгва по аналогии с операцией наибольшей нижней границы можно определить наиченыаую верхнюю границу (!сам пррсг Ьоппд — !пЬ) элементов х и д как элемент Ь, такой, что х < 6, 8 < (), и если з — любой элемент, такой, что х < з и р < е, то 6 < з.

Можно показать, что если такой элемент б существует, то он единственный. В истинной решетке над элементами области определения су(цествует две операции — уже знакомая нам операция сбора д и оператор объединения, обозначаемый как Ч, который дает наименыпую верхнюю границу двух элементов (которая, следовательно, должна всегда существовать в решетке).

Характеристики

Список файлов книги