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

Поэтому построить MOP-решение, какправило, не удается (невозможно учесть бесконечное множествопутей).523.5 Смысл решения уравнений потока данных3.5.4 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)Итеративный алгоритм(1)посещает базовые блоки не в порядке их выполнения(как при вычислении MOP-решения), а в порядке обходаграфа потока (на каждой итерации каждый узелпосещается только один раз)(2)в каждой точке слияния алгоритм применяет операциюсбора к значениям потока данных, полученным к этомумоменту(3)иногда в пределах итерации базовый блок B посещаетсядо посещения его предшественников (прямой обход)533.5 Смысл решения уравнений потока данных3.5.4 Решение, получаемое итеративным алгоритмом(максимальная фиксированная точка)Следовательно:необходимо граничное условие, так как к блоку Entryпередаточная функция не применяется.необходима инициализация потока данных для выходовиз базовых блоков: Out[B] инициализируется значениемT, которое, как известно, «не меньше» всех значенийпотока, и, следовательно, того значения, которое онозаменяет.при использовании T в качестве входных данныхмонотонность передаточных функций обеспечиваетполучение результата, «не меньшего», чем искомоерешение:MFP  MOP543.5 Смысл решения уравнений потока данных3.5.4 Решение, получаемое итеративным алгоритмом (максимальнаяфиксированная точка)Пример (см.

рисунок)Требуется вычислить значение In[B4].(1) MOP-решение:MOP[ B4 ]  (( f B1  f B3 )  ( f B2  f B3 ))(lEntry )(2) Итеративный алгоритм (узлы посещаютсяв порядке B1,B2, B3, B4)In[ B4 ]  f B3 (lEntry )  f B2 (lEntry )Операция сбора  в итеративном алгоритмеприменяется раньше, чем при вычисленииMOP-решения553.5 Смысл решения уравнений потока данных3.5.4 Решение, получаемое итеративным алгоритмом (максимальнаяфиксированная точка)Если структура потока данных дистрибутивна, тоIn[B4] = MOP[B4]если же структура потока данных монотонна,но не дистрибутивна, тоIn[B4]  MOP[B4]Следовательно, в обоих случаях приближенноерешение, представленное максимальнойфиксированной точкой (MFP-решение),удовлетворяет условию:MFP[B]  MOP[B]563.5 Смысл решения уравнений потока данных3.5.4 Решение, получаемое итеративным алгоритмом (максимальнаяфиксированная точка)Если структура потока данных дистрибутивна, то для всех BMFP[B] = MOP[B].В разделах 3.2.5 и 3.2.6 была установлена дистрибутивностьструктур достигающих определений (RD), живых переменных(LV) и доступных выражений (AE).Следовательно, в указанных случаях итеративный алгоритмпозволяет получить MOP-решение.573.5 Смысл решения уравнений потока данных3.5.5.

Консервативность MFP-решенияУтверждение. MFP-решение, получаемое итеративнымалгоритмом, всегда консервативноДоказательствоИндукция по i: значения, полученные итеративным алгоритмомпосле i итераций, не превосходят результата операции сбора повсем путям длины i.Итеративный алгоритм завершается только тогда, когда онполучает такой же ответ, как и при неограниченном количествеитераций.Следовательно, MFP  MOP.Но уже установлено: MOP Ideal.Следовательно (транзитивность ), MFP  Idealи MFP-решение консервативно.58.