Тема 03(2016)Анализ потока данных (1161798), страница 2

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

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

Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у). Утверждение. Определения 3.3.3.1 и 3.3.3.2 эквивалентны.243.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у). Утверждение. Определения 3.2.3.1 и 3.2.3.2 эквивалентны.Из определения 1 следует определение 2:х  у = inf(x, y)  х  у  х и х  у  у (1)f(х  у)  f(х) и f(х  у)  f(y) f(х  у) = inf(f(х),f(y)) = f(x)  f(у)Из определения 2 следует определение 1:х  у  х  у = х (опр2) f(x)  f(x)  f(у),f(x)  f(у) = inf(f(х), f(y))  f(y);  f(x)  f(у)253.3 Структура потока данных3.3.4 Дистрибутивные структурыОпределение.

Структура потока данных D, F, L, называется дистрибутивной, еслих, у  L, f  F: f(x  у) = f(x)  f(у).263.3 Структура потока данных3.3.4 Дистрибутивные структурыОпределение. Структура потока данных D, F, L, называется дистрибутивной, еслих, у  L, f  F: f(x  у) = f(x)  f(у).Утверждение. Если структура потока данных D, F, L, дистрибутивна, то она монотонна.а = b идемпотентность а  b = a  а  bf(x  у) = f(x)  f(у)  f(x  у)  f(x)  f(у)Обратное утверждение неверно.В качестве доказательства можно привести пример монотоннойструктуры потока данных, которая не дистрибутивна.273.3 Структура потока данных3.3.5.

Дистрибутивность структуры достигающих определенийУтверждение. Структура достигающих определенийRD = Forward, Gen-kill, ,  дистрибутивнау, z  RD, f(х) = G  (x – K)  Gen-kill.Докажем, чтоG  ((y  z) – K) = (G  (y – K))  (G  (z – K))(1) у, z  G: равенство выполняется, так как G входити в левую, и в правую его части.(2) у, z  G: G можно исключить из равенства:(y  z) – K = (y – K))  (z – K)Это равенство проверяется при помощи диаграмм Венна.283.3 Структура потока данных3.3.5.

Дистрибутивность структуры достигающих определенийУтверждение. Структура достигающих определенийRD = Forward, Gen-kill, ,  дистрибутивнау, z  RD, f(х) = G  (x – K)  Gen-kill.Докажем, чтоG  ((y  z) – K) = (G  (y – K))  (G  (z – K))(2) у, z  G: G можно исключить из равенства:(y  z) – K = (y – K))  (z – K)Это равенство проверяется при помощи диаграмм Венна.293.3 Структура потока данных3.3.6. Дистрибутивность структур живых переменных и доступныхвыраженийСледствие 1. Структура живых переменныхLV = Backward, Def-use, , дистрибутивнаf(х)  Def-use алгебраически подобна функции класса Gen-kill.Следствие 2. Структура доступных выраженийAE = Forward, Gen-kill, U, дистрибутивна303.4 Обобщенный итеративный алгоритм3.4.1 Описание алгоритма Алгоритм.

Итеративное решение задачи анализа потока данныхВход: граф потока управления,структура потока данных D, F, L, ,передаточная функция fВ  Fконстанта из l  L для граничного условияВыход: значения из L для In[B] и Out[В] для каждого блока Вв графе потока.Метод: если D = Forward выполнить программу (3.4.2);если D = Backward выполнить программу (3.4.3).313.4 Обобщенный итеративный алгоритм3.4.2 Решение задачи потока данных (D = Forward )Out[Entry] = l;for (each В  Entry) Out[В] = Т;while (внесены изменения в Out)for (each В  Entry) {InB  Λ PPred  B Out P Out B   f B InB}323.4 Обобщенный итеративный алгоритм3.4.3 Решение задачи потока данных (D = Backward)In[Exit] = l;for (each В  Exit) In[В] = Т;while (внесены изменения в In)for (each В  Exit) {OutB   Λ SSucc B  InS InB  f B OutB}333.5 Свойства итеративного алгоритма3.5.1 Сходимость к решениюУтверждение.

Если обобщенный итеративный алгоритмсходится, то получающийся результат является решениемуравнений потоков данных.D = Forward:Если после очередной итерации цикла while хотя бы дляодного В уравнение Out[В]= fВ(In[В]) не удовлетворяется,то для этого ВOutNew[В]  Out[В].Следовательно, в множество Out[В] будет внесеноизменение и change не позволит выйти из цикла.343.5 Свойства итеративного алгоритма3.5.1 Сходимость к решениюУтверждение. Если обобщенный итеративный алгоритмсходится, то получающийся результат является решениемуравнений потоков данных.D = Backward:Аналогичные рассуждения, только вместо множестваOut[В] рассматривается множество In[В].353.5 Свойства итеративного алгоритма3.5.2 Максимальная фиксированная точкаОпределение.

Максимальная фиксированная точкасистемы уравненийInB  Λ PPred  B OutPOutB  f B InBпредставляет собой решение {In[Вi]max, Out[Вi]max} этойсистемы, обладающее тем свойством, что для любого другогорешения {In[Вi], Out[Вi]} выполняются условияIn [Вi]  In[Вi]max и Out[Вi]  Out[Вi]maxгде  – полурешеточное отношение частичного порядка.363.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1. Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iИндукция по i.373.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1.

Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iИндукция по i.Основание:In[B]1  In[B]0иOut[B]1  Out[B]0,так как B  Entry: In[B]0 = Т и Out[B]0 = Т.383.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1.

Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iИндукция по i.Шаг: Пусть In[B]k In[B]k-1 и Out[B]k  Out[B]k-1393.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1. Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iИндукция по i.Шаг: Пусть In[B]k InBk 1In[B]k-1 и Out[B]k  Out[B]k-1 Λ PPred  B OutP  Λ PPred  B OutPkk 1 InBkтак как операция сбора монотонна.403.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1.

Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iИндукция по i.Шаг: Пусть In[B]k InBk 1In[B]k-1 и Out[B]k  Out[B]k-1 Λ PPred  B OutP  Λ PPred  B OutPkk 1 InBkтак как операция сбора монотонна.Out[В]k+1 = fВ(In[В]k+1)  fВ(In[В]k) = Out[В]k,так как передаточная функция fВ( x) монотонна.413.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 1. Пусть In[B]i и Out[B]i – значения In[B] и Out[B]после i-ой итерации. Если структура потока данных монотонна, тоIn[B]i+1  In[B]i и Out[B]i+1  Out[B]iСледствие. Для любого iIn[B]  In[B]iOut[B]  Out[B]i423.5 Свойства итеративного алгоритма3.5.3 Монотонность итерацийУтверждение 2.

Если структура потока данных монотонна, то решениесистемы уравнений (1), найденное с помощью итеративного алгоритма,является максимальной фиксированной точкой этой системы.Требуется доказать, что для всех jIn[Вj]  In[Вj]IA, Out[Вj]  Out[Вj]IA,где {In[Вj]IA, Out[Вj]IA} – решение системы (1), найденное спомощью итеративного алгоритма, {In[Вj], Out[Вj]} – любое другоерешение этой системы.Аналогично доказательству предыдущего утверждения.433.5 Свойства итеративного алгоритма3.5.4. Сходимость итеративного алгоритмаОпределение 1.

Восходящей цепочкой в частичноупорядоченном множестве (L, ) называетсяпоследовательность его элементов, в которойх1 < х 2 < … < х n .Определение 2. Высотой полурешетки называется наибольшееколичество отношений < в восходящих цепочках.Утверждение. Если полурешетка структуры монотонна и имеетконечную высоту, то итеративный алгоритм гарантированносходится после количества итераций, не превышающегопроизведения высоты полурешетки на количество базовыхблоков.443.5 Свойства итеративного алгоритма3.5.5 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)Итеративный алгоритм(1)посещает базовые блоки не в порядке их выполнения,а в порядке обхода ГПУ (на каждой итерации каждый узелпосещается только один раз)(2)в каждой точке сбора применяет операцию сборак значениям потока данных, полученным к этому моменту(3)иногда в пределах итерации базовый блок B посещается допосещения его предшественников (прямой обход)453.5 Свойства итеративного алгоритма3.5.5 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)(4)для процесса итерации необходимограничное условие,так как к блоку Entry передаточная функция неприменима.(5)в качестве «нулевой итерации» все Out[B]инициализируются значением T, которое, поопределению, «не меньше» всех значений потока, и,следовательно, того значения, которое оно заменяет;при этом монотонность передаточных функцийобеспечивает получение результата, «не меньшего»,чем искомое решение:463.5 Смысл решения уравнений потока данныхБез потери общности будем считать, что рассматривается прямая задача(обход графа потока от Entry к Exit).Обратная задача (обход графа потока от Exit к Entry) рассматриваетсяаналогично.3.5.1 Идеальное решениеf Bk – передаточная функция блока Bk в графе потока.Рассмотрим путь P = Entry  B1  B2  …  Bk-1  BkПусть(Путь P может содержать циклы: базовые блоки могут встречаться в немпо нескольку раз).По определению передаточнаяфункция пути Р:f P  f B1  f B2  ...

 f Bk 1( f B не является частью композиции, так как путь достигает начала блокаkBk, но не его конца). Значение потока данных, создаваемое этим путем,представляет собойfP(lEntry), где lEntry – граничное условие.473.5 Смысл решения уравнений потока данных3.5.1 Идеальное решениеПусть P= {P1, P2, …} – множество всех выполнимых путей отEntry до BkПуть P является выполнимым только тогда, когда известновыполнение программы (начальные данные), которое следует вточности по этому пути.Идеальным решением системы уравнений потока данных дляIn[Bk] будет:Ideal[Bk] = PP fP(lEntry).Решение Ideal[Bk] названо идеальным, так как(1) оно наиболее точное и(2) вычислить его почти никогда не удается, так как поисквсех возможных путей выполнения – задача неразрешимая.Следовательно, требуется поиск приближенного решения.483.5 Смысл решения уравнений потока данных3.5.2 Свойства решений уравнений потока данныхдля монотонных и дистрибутивных структурДобавление еще одного пути в сбор P Pделает решение«меньше» в смысле частичного порядка полурешетки Если просмотрены все выполнимые пути и ни одного лишнего,получается идеальное решение Ideal.Решение Sol1: Ideal  Sol1, получается, когда просмотрены не всевыполнимые пути.

Использовать решение Sol1 опасно, так как длянепросмотренных путей преобразования программы могут оказатьсяневерными (нарушается консервативность).493.5 Смысл решения уравнений потока данных3.5.2 Свойства решений уравнений потока данныхдля монотонных и дистрибутивных структурРешение Sol2: Sol2  Ideal обладает следующими свойствами:(1)Sol2 консервативно: оно содержит все выполнимые пути(2)Sol2 неточно: в нем не отсеяны «лишние» пути, т.е. либоне существующие в графе потока, либо существующие,но такие, по которым программа никогда не проследует.В результате:(1)Sol2 может запрещать некоторые из преобразований,разрешенных решением Ideal.(2)все преобразования, которые разрешает Sol2, корректныВ абстракции потока данных предполагается, что каждый путь вграфе потока может быть пройден.503.5 Смысл решения уравнений потока данных3.5.3 Решение сбором по всем путямРешение сбором по всем путям (MOP-решение)от Entry до входа в Bk определяется соотношением:MOP[Bk] =P Q fP(lEntry),где Q = {P1, P2, …} – множество всех путей от Entry до входав блок BkПути, рассматриваемые в MOP-решении, – это надмножествовсех выполнимых путей: MOP-решение собирает значенияпотоков данных как для всех выполнимых путей, так и дляпутей, которые не могут быть выполнены.

Следовательно, длявсех Bk выполняется соотношениеMOP[Bk]  Ideal[Bk].513.5 Смысл решения уравнений потока данных3.5.3 Решение сбором по всем путямЗамечание. Для прямой задачи MOP[Bk] дает значения дляIn[Bk]. Для обратной задачи MOP[Bk] дает значения для Out[Bk].Если рассматривается обратная задача, MOP-решениеопределяется соотношением :MOP[Bk] =P Q fP(lExit),где Q = {P1, P2, …} – множество всех путей от выхода из Bkдо Exit.Если в анализируемой программе есть циклы, количество всехпутей, рассматриваемых при построении MOP-решения,становится бесконечным.

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

Список файлов лекций