Тема 07(2016)Анализ на основе областей (1161802), страница 3

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

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

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2: Восходящий просмотр для вычисления передаточныхфункций областей R1, R2, R3, R4, R5, R6, R7, R8Шаг 2a): вычисление передаточных функций областей-листьевR1, R2, R3, R4, R5f Ri , In[ Bi ] ( x)  I ,f Ri ,Out[ Bi ] ( x)  f Bi ( x)  genBi  ( x  killBi )BB1B2B3B4B5genB{d1,d2,d3}{d4}{d5}{d6}killB{d4,d5,d6}{d1}{d3}{d2}527.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3Шаг 2b): вычисление передаточной функцииобласти-тела R6Область R6 состоит из подобластей R2, R3 иR4.

Эти подобласти обрабатываются втопологическом порядке, построенном нашаге 1: R2, R3, R4.Подобласть R2: У R2 нет предшественниковв пределах R6, так как обратное ребро R4 R2 не принадлежит R6. Следовательноf R6 , In[ R2 ]  f R2 , In[ B2 ]  I ,f R6 ,Out[ B2 ]  f R2 ,Out[ B2 ]  f R6 , In[ R2 ]  f B2 I  f B2genR6 , In[ R2 ]  , killR6 , In[ R2 ]  genR6 ,Out[ R2 ]  genB2  {d 4 }, killR6 ,Out[ R2 ]  killB2  {d1}537.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2b): вычисление передаточнойфункции области-тела R6Подобласть R3: У R3 в пределах R6 одинпредшественник R2. Следовательноf R6 , In[ R3 ]  f R6 ,Out[ B2 ]  f B2f R6 ,Out[ B3 ]  f R3 ,Out[ B3 ]  f R6 , In[ R3 ]  f B3  f B2f R6 , In[ R3 ] ( x)  f R6 ,Out[ B2 ] ( x)  f B2 ( x)  ( x  kill B2 )  genB2f R6 ,Out[ B3 ] ( x)  f R3 ,Out[ B3 ]  f R6 , In[ R3 ] ( x)  ( f B3  f B2 )( x) ( genB3  ( genB2  kill B3 ))  ( x  (kill B3  kill B2 ))genR6 , In[ B3 ]  genB2  {d 4 }, kill R6 , In[ B3 ]  kill B2  {d1}genR6 ,Out[ B3 ]  genB3  ( gen B2  kill B3 )  {d 5 }  ({d 4 }  {d 3 })  {d 4 , d 5 }kill R6 ,Out[ B3 ]  kill B3  kill B2  {d 3}  {d1}  {d1 , d 3 }547.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2b): вычисление передаточнойфункции области-тела R6Подобласть R4: У R4 в пределах R6 двапредшественника R2 и R3. Следовательноf R6 , In[ R4 ]  f R6 ,Out[ B2 ]  f R6 ,Out[ B3 ]  f B2  f R6 ,Out[ B3 ]f R6 ,Out[ B4 ]  f R4 ,Out[ B4 ]  f R6 , In[ R4 ]  f B4  f R6 , In[ R4 ]557.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2b): вычисление передаточнойфункции области-тела R6Подобласть R4f R6 , In[ R4 ] ( x)  ( f R6 ,Out[ B2 ]  f R6 ,Out[ B3 ] )( x)  ( f B2  f R6 ,Out[ B3 ] )( x)f R6 ,Out[ B4 ] ( x)  ( f R4 ,Out[ B4 ]  f R6 , In[ R4 ] )( x)  ( f B4  f R6 , In[ R4 ] )( x)genR6 , In[ R4 ]  genB2  genR6 ,Out[ B3 ]  {d 4 }  {d 4 , d5}  {d 4 , d5}killR6 , In[ R4 ]  killB2  killR6 ,Out[ B3 ]  {d1}  {d1 , d3}  {d1}genR6 ,Out[ R4 ]  genR6 , In[ R4 ]  ( genB4  killR6 , In[ R4 ] )  {d 4 , d5}  ({d 6 }  {d1})  {d 4 , d5 , d 6 }killR6 ,Out[ R4 ]  killB4  killR6 , In[ R4 ]  {d 2 }  {d1}  {d1 , d 2 }567.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2с): вычисление передаточной функцииобласти-цикла R7Область R7 содержит только одну подобластьR6 (тело цикла). Обратному ребру B4  B2 кзаголовку R6 соответствует передаточнаяфункцияf R7 , In[ R6 ]  f R*6 ,Out[ B4 ]:Из области R7 имеется два выхода – базовые блоки B3 и B4.Поэтому для получения соответствующих передаточных функций R7нужно вычислить композиции f R7 , In [ R6 ] с f R6 ,Out[ B3 ] и с f R6 ,Out[ B4 ]f R7 ,Out[ B4 ]  f R6 ,Out[ B4 ]  f R7 , In[ R6 ]f R7 ,Out[ B3 ]  f R6 ,Out[ B3 ]  f R7 , In[ R6 ]577.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2с): вычисление передаточной функцииобласти-цикла R7(a) На входеПередаточная функция:f R7 , In [ R6 ] ( x)  f R*6 ,Out [ B4 ] ( x)Множества gen и killgenR7 , In [ R6 ]  genR6 ,Out [ B4 ]  {d 4 , d5 , d6 }killR7 , In [ R6 ]  587.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2с): вычисление передаточнойфункции области-цикла R7(b) На выходахПередаточные функции:f R7 ,Out[ B4 ] ( x)  ( f R6 ,Out[ B4 ]  f R7 , In[ R6 ] )( x)f R7 ,Out[ B3 ] ( x)  ( f R6 ,Out[ B3 ]  f R7 , In[ R6 ] )( x)Множества gen и killgenR7 ,Out[ B4 ]  genR7 , In[ R6 ]  ( genR6 ,Out[ B4 ]  killR7 , In[ R6 ] )  {d 4 , d5 , d 6 }  ({d 4 , d5 , d 6 }  )  {d 4 , d5 , d 6 }killR7 ,Out[ B4 ]  killR7 , In[ R6 ]  killR6 ,Out[ B4 ]    {d1 , d 2 }  {d1 , d 2 }genR7 ,Out[ B3 ]  genR7 , In[ R6 ]  ( genR6 ,Out[ B3 ]  killR7 , In[ R6 ] )  {d 4 , d5 , d 6 }  ({d 4 , d5}  )  {d 4 , d5 , d 6 }killR7 ,Out[ B3 ]  killR7 , In[ R6 ]  killR6 ,Out[ B3 ]    {d1 , d3}  {d1 , d3}597.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2d): вычисление передаточной функцииобласти-тела R8Подобластями области R8 (весь граф потока)являются (в топологическом порядке)R1, R7 и R5.Передаточные функции:1) для R1:f R8 , In[ R1 ] ( x)  I ( x)  xf R8 ,Out[ B1 ] ( x)  f B1 ( x)genR8 , In[ R1 ]  killR8 , In[ R1 ]  607.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2d): вычисление передаточной функцииобласти-цикла R82) для R7:Заголовок R7 (блок В2) имеет единственногопредшественника, В1.У R7 два выходных ребра (в блоках В3 и В4).Передаточные функции:f R8 , In[ R7 ]  f R8 ,Out[ B1 ]  f R1 ,Out[ B1 ]  f B1f R8 ,Out[ B3 ]  f R7 ,Out[ B3 ]  f R8 , In[ R7 ]  f R7 ,Out[ B3 ]  f B1f R8 ,Out[ B4 ]  f R7 ,Out[ B4 ]  f R8 , In[ R7 ]  f R7 ,Out[ B4 ]  f B1617.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2d): вычисление передаточной функцииобласти-цикла R82) для R7:Множества gen и killgenR8 , In[ R7 ]  genB1  {d1 , d 2 , d 3}killR8 , In[ R7 ]  killB1  {d 4 , d 5 , d 6 }genR8 ,Out[ B3 ]  genR7 ,Out[ B3 ]  ( genB1  kill R7 ,Out[ B3 ] )  {d 4 , d 5 , d 6 }  ({d1 , d 2 , d 3}  {d1 , d 3})  {d 2 , d 4 , d 5 , d 6 }kill R8 ,Out[ B3 ]  kill R7 ,Out[ B3 ]  kill B1  {d1 , d 3}  {d 4 , d 5 , d 6 }  {d1 , d 3 , d 4 , d 5 , d 6 }627.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2d): вычисление передаточной функцииобласти-цикла R83) для R5:У заголовка R5 (блок В5) два предшественника(В3 и В4), причемf B5  If R8 , In[ R7 ]  f R8 ,Out[ B1 ]  f R1 ,Out[ B1 ]  f B1f R8 ,Out[ B3 ]  f R7 ,Out[ B3 ]  f R8 , In[ R7 ]  f R7 ,Out[ B3 ]  f B1f R8 ,Out[ B4 ]  f R7 ,Out[ B4 ]  f R8 , In[ R7 ]  f R7 ,Out[ B4 ]  f B1637.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 2d): вычисление передаточной функции области-цикла R83) для R5:передаточные функцииf R8 , In[ B5 ] ( x)  f R8 ,Out[ B3 ]  f R8 ,Out[ B4 ] ( x)f R8 ,Out[ B5 ] ( x)  f R8 , In[ B5 ] ( x)Множества gen и kill (см 7.2.2.3)genR8 , In[ B5 ]  genR8 ,Out[ B3 ]  genR8 ,Out[ B4 ]  {d 2 , d 4 , d5 , d 6 }  {d3 , d 4 , d5 , d 6 }  {d 2 , d3 , d 4 , d5 , d 6 }killR8 , In[ B5 ]  killR8 ,Out[ B3 ]  killR8 ,Out[ B4 ]  {d1 , d3 , d 4 , d5 , d 6 }  {d1 , d 2 , d 4 , d5 , d 6 }  {d1 , d 4 , d5 , d 6 }genR8 ,Out[ B5 ]  genR8 , In[ B5 ]  {d 2 , d3 , d 4 , d5 , d 6 }killR8 ,Out[ B5 ]  killR8 , In[ B5 ]  {d1 , d 4 , d5 , d 6 }647.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Результаты шага 2657.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 3: Нисходящий просмотр для вычисления значений In[R] вначале каждой области:1) Для области R8In[R8] = , (граничное условие).2) Для подобластей области R8 :2.1) область R1In[ R1 ]  f R8 , In[ R1 ] ( In[ R8 ])  I ( In[ R8 ])  In[ R8 ]  2.2) область R7In[ R7 ]  f R8 , In[ R7 ] ( In[ R8 ])  f B1 ( In[ R8 ])  genB1  ( In[ R8 ]  killB1 )  (  {d 4 , d 5 , d 6 })  {d1 , d 2 , d3}  {d1 , d 2 , d3}2.3) область R5In[ R5 ]  f R8 , In[ R5 ] ( In[ R8 ])  genR8 , In[ R5 ]  ( In[ R8 ]  killR8 , In[ R5 ] ) {d 2 , d 3 , d 4 , d 5 , d 6 }  (  {d1})  {d 2 , d3 , d 4 , d5 , d 6 }667.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 3: Нисходящий просмотр для вычисления значений In[R] вначале каждой области:3) Для подобласти R6 области R7 :In[ R6 ]  f R7 , In[ R6 ] ( In[ R7 ])  gen R7 , In[ R6 ]  ( In[ R7 ]  killR7 , In[ R6 ] )  {d 4 , d 5 , d 6 }  ({d1 , d 2 , d 3}  )  {d1 , d 2 , d 3 , d 4 , d 5 , d 6 }677.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Шаг 3: Нисходящий просмотр для вычислениязначений In[R] в начале каждой области:4) Для подобластей области R6:4.1) область R4In[ R4 ]  f R6 , In[ R4 ] ( In[ R6 ])  genR6 , In[ R4 ]  ( In[ R6 ]  killR6 , In[ R4 ] ) {d 4 , d5 }  ({d1 , d 2 , d3 , d 4 , d5 , d 6 }  {d1})  {d 2 , d3 , d 4 , d5 , d 6 }4.2) область R3In[ R3 ]  f R6 , In[ R3 ] ( In[ R6 ])  genR6 , In[ R3 ]  ( In[ R6 ]  killR6 , In[ R3 ] ) {d 4 , d5 }  ({d1 , d 2 , d3 , d 4 , d5 , d 6 }  {d1})  {d 2 , d3 , d 4 , d5 , d 6 }4.3) область R2In[ R2 ]  f R6 , In[ R2 ] ( In[ R6 ])  genR6 , In[ R2 ]  ( In[ R6 ]  killR6 , In[ R2 ] )   ({d1 , d 2 , d 3 , d 4 , d5 , d 6 }  )  {d1 , d 2 , d3 , d 4 , d5 , d 6 }687.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Результаты шага 3Значения потока данных для достигающих определений:InR8   InR1   f R8 , In R1   InR8   InR7   f R8 , InR7   InR8   d1 , d 2 , d 3 InR5   f R8 , InR5   InR8   d 2 , d 3 , d 4 , d 5 , d 6 InR6   f R7 , InR6   InR7   d1 , d 2 , d 3 , d 4 , d 5 , d 6 InR4   f R6 , In R4   InR6   d 2 , d 3 , d 4 , d 5 , d 6 InR3   f R6 , In R3   InR6   d 2 , d 3 , d 4 , d 5 , d 6 InR2   f R6 , In R2   InR6   d1 , d 2 , d 3 , d 4 , d 5 , d 6 697.2.

Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Сравнение результатовМножества определений, достигающих входов в блоки B1, B2, B3, B4, B5,вычисленные с помощью алгоритма 7.2.3:In[ B1 ]  InR1   In[ B2 ]  InR2   d1 , d 2 , d 3 , d 4 , d 5 , d 6 In[ B3 ]  InR3   d 2 , d 3 , d 4 , d 5 , d 6 In[ B4 ]  InR4   d 2 , d 3 , d 4 , d 5 , d 6 In[ B5 ]  InR5   d 2 , d 3 , d 4 , d 5 , d 6 Множества определений, достигающих входов в блоки B1, B2, B3, B4, B5,вычисленные без выделения областей (слайд 49):In[ B1 ]  In[ B2 ]  d1 , d 2 , d 3 , d 4 , d 5 , d 6 In[ B3 ]  d 2 , d 3 , d 4 , d 5 , d 6 In[ B4 ]  d 2 , d 3 , d 4 , d 5 , d 6 In[ B5 ]  d 2 , d 3 , d 4 , d 5 , d 6 70.

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

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