Лекция 03. Анализ потока данных (1157461), страница 2

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

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

Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у). Утверждение. Определения 3.2.3.1 и 3.2.3.2 эквивалентны.Из определения 2 следует определение 1:х  у  х  у = х (опр2) f(x)  f(x)  f(у),f(x)  f(у) = inf(f(х), f(y))  f(y);  f(x)  f(у)213.3 Структура потока данных3.3.4 Дистрибутивные структурыОпределение. Структура потока данных D, F, L, называется дистрибутивной, еслих, у  L, f  F:f(x  у) = f(x)  f(у).223.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(у)Обратное утверждение неверно.В качестве доказательства можно привести пример монотоннойструктуры потока данных, которая не дистрибутивна.233.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)Это равенство проверяется при помощи диаграмм Венна.243.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)Это равенство проверяется при помощи диаграмм Венна.253.3 Структура потока данных3.3.6. Дистрибутивность структур живых переменных и доступныхвыраженийСледствие 1.

Структура живых переменныхLV = Backward, Def-use, , дистрибутивнаf(х)  Def-use алгебраически подобна функции класса Gen-kill.Следствие 2. Структура доступных выраженийAE = Forward, Gen-kill, U, дистрибутивна263.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).273.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283.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293.5 Свойства итеративного алгоритма3.5.1 Сходимость к решениюУтверждение.

Если обобщенный итеративный алгоритмсходится, то получающийся результат является решениемуравнений потоков данных.D = Forward:Если после очередной итерации цикла while хотя бы дляодного В уравнение Out[В]= fВ(In[В]) не удовлетворяется,то для этого ВOutNew[В]  Out[В].Следовательно, в множество Out[В] будет внесеноизменение и change не позволит выйти из цикла.303.5 Свойства итеративного алгоритма3.5.1 Сходимость к решениюУтверждение. Если обобщенный итеративный алгоритмсходится, то получающийся результат является решениемуравнений потоков данных.D = Backward:Аналогичные рассуждения, только вместо множества Out[В]рассматривается множество In[В].313.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где  – полурешеточное отношение частичного порядка.323.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.333.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 = Т.343.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-1353.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так как операция сбора монотонна.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.Шаг: Пусть 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) монотонна.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Следствие. Для любого iIn[B]  In[B]iOut[B]  Out[B]i383.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]} – любое другоерешение этой системы.Аналогично доказательству предыдущего утверждения.393.5 Свойства итеративного алгоритма3.5.4. Сходимость итеративного алгоритмаОпределение 1.

Восходящейцепочкой в частично упорядоченном) называется последовательность его элементов,х1 < х 2 < … < х n .множестве (L,в которойОпределение 2. Высотой полурешетки называется наибольшееколичество отношений < в восходящих цепочках.Утверждение. Если полурешетка структуры монотонна и имеетконечную высоту, то итеративный алгоритм гарантированно сходитсяпосле количества итераций, не превышающего произведения высотыполурешетки на количество базовых блоков.403.5 Свойства итеративного алгоритма3.5.5 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)Итеративный алгоритм(1)посещает базовые блоки не в порядке их выполнения,а в порядке обхода ГПУ (на каждой итерации каждый узелпосещается только один раз)(2)в каждой точке сбора применяет операцию сборак значениям потока данных, полученным к этому моменту(3)иногда в пределах итерации базовый блок B посещается допосещения его предшественников (прямой обход)413.5 Свойства итеративного алгоритма3.5.5 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)(4)для процесса итерации необходимограничное условие,так как к блоку Entry передаточная функция неприменима.(5)в качестве «нулевой итерации» все Out[B]инициализируются значением T, которое, по определению,«не меньше» всех значений потока, и, следовательно, тогозначения, которое оно заменяет; при этом монотонностьпередаточных функций обеспечивает получение результата,«не меньшего», чем искомое решение:42.

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

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