Back

ⓘ Граф контроле података




Граф контроле података
                                     

ⓘ Граф контроле података

Граф контроле података је у рачунарству и информатици, користећи нотацију графова, репрезентација свих путева кроз које је могуће проћи помоћу програма, током његовог извршавања. ГКП је кључан у многим оптимизацијама преводиоца и алатима за статичку анализу.

                                     

1. Дефиниција

У ГКП-у сваки чвор графа представља базични блок, тј. део кода без икаквих скокова или циљева скокова; циљеви скокова представљају почетке блокова а скокови представљају крајеве блокова. Усмерене ивице гране се користе за репрезентацију скокова у контроли тока. У већини представљања, постоје два специјална блока: улазни блок, кроз који контрола улази у граф, и излазни блок, кроз који контроле напуштају граф.

Због начина креирања, у ГКП-у, свака ивица A→B има својство да:

излазни степенA > 1 или излазни степенB > 1 или оба.

ГКП се дакле може добити, бар концептуално, од пуног графа неког програма тј. графа код кога сваки чвор представља индивидуалну инструкцију при примени редукције ивице за сваку ивицу за коју не важи претходно тврђење тј. редукција сваке ивице чији почетак има тачно један излаз и чији крај има тачно један улаз. Овакав алгоритам базиран на редукцији нема практичних примена, осим као визуелно помагало за разумевање ГКП конструкције, јер се ГКП може много ефикасније конструисати директно из програма скенирајући базичне блокове.

                                     

2. Пример

Посматрајмо следећи део кода:

0: A t0 = read_num 1: A if t0 mod 2 == 0 2: B print t0 + is even." 3: B goto 5 4: C print t0 + is odd." 5: D end program

Горе видимо 4 базична блока: А од 0 до 1, B од 2 до 3, C је на 4 и D је на 5. У овом случају, А је "улазни блок", D је "излазни блок" а линије 4 и 5 су циљеви скока. Граф настао од овог фрагмента кода има ивице од А до B, A до C, B до D и C до D.

                                     

3. Достижност

Достижност је својство графа које је јако корисно у оптимизацији.

Ако подграф није повезан са подграфом који садржи улазни блок, подграф је недостижан при сваком покретању програма као и одговарајући део кода; под нормалним околностима, тај део кода се може безбедно уклонити.

Ако пођемо од улазног блока и добијемо да је излазни блок недостижан, то значи да можда постоји бесконачна петља унутар кода. Није могуће детектовати све бесконачне петље. Може се десити да у том делу постоји и ред заустављања.

Недостижан део кода и бесконачне петље су могуће чак и када их програмер не искодира експлицитно: оптимизације као што су константна пропагација, константно паковање као и скакање по нитима могу да од више базичних блокова направе само један, чинећи да ивице нестану са ГКП-а итд., па и самим тим учине неке делове графа неповезаним.

                                     

4. Релације доминантности

Блок М доминира је надмоћнији над блоком N ако сваки пут од улазног блока до блока N мора да прође кроз блок M. Улазни блок доминира све блокове.

Кажемо да блок M непосредно доминира блок N ако М доминира N, и не постоји међублок P тако да M доминира P и P доминира N. Другим речима, М је последњи доминантни блок на свим путевима од улазног блока до блока N. Сваки блок има јединствени непосредни доминантни блок.

Дрво доминантности је помоћна структура података која осликава релације доминантности. Постоји грана од блока М до блока N ако је M непосредни доминантни блок за блок N. Овај граф је дрво, јер сваки блок има јединствени непосредни доминантни блок. Корен дрвета представља улазни блок. Дрво доминантности се ефикасно може срачунати помоћу Ленжер-Таржан-овог алгоритма.

                                     

5. Специјалне ивице

Задња ивица енг. back edge је она ивица која је повезана са блоком који је већ посећен обиласком графа у дубину. Ове ивице су карактеристичне за петље.

Критична ивица је она ивица која није нити једина ивица која напушта свој изворни блок, нити једина ивица која улази у свој циљни блок. Овакве ивице морају бити подељене: мора се креирати нови блок по средини ивице, да би се омогућила израчунавања на ивици без утицаја на остале ивице.

Абнормална ивица је она ивица чији је циљни блок непознат. Конструкције за управљање изузецима могу да их произведу. Често се овакве ивице користе при оптимизацији.

Немогућа ивица позната као и лажна ивица је она ивица која је додата графу једино да омогући својство да излазни блок буде подређен свим осталим блоковима. Оне се никад не могу обићи.

                                     

6. Обрада петљи

Глава петље често називан и улазни део петље је доминатор доминантан блок који је уједно и циљ задње ивице креиране од стране петље. Глава петље доминира над свим блоковима унутар тела петље. Блок може бити глава петље за више од једне петље. Петља може садржати више улаза, те у том случају кажемо да не постоји глава петље.

Претпоставимо да је блок M доминатор са неколико улазних ивица, при чему су неке ивице задње ивице дакле М је глава петље. Велику предност многим оптимизацијама представља могућност да се разбије блок М на два блока M pre and M loop. Садржај блока М и задњих ивица је смештен у M loop, а остатак ивица је смештен у M pre, и још се креира нова ивица од M pre до M loop тако да M pre је непосредни доминатор блока M loop. На почетку, M pre би био празан, али би га оптимизациони пролази испунили. M pre се зове надглава петље, а M loop је тада глава петље.

                                     

7. Спољашње везе

  • Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.
  • The Machine-SUIF Control Flow Graph Library
  • GNU Compiler Collection Internals
  • Avrora – Control Flow Graph Tool
                                     
  • скупова података Једна - инструкција - једни - подаци СИСД класификација је еквивалентна потпуно секвенцијалном програму. Једна - инструкција - више - података СИМД
  • или контрола конкуренције користе. Расподељени застоји могу бити детектовани или прављењем глобалног чекај - for графа или из локалног чекај - for графа у детектору
  • izomorfizma grafova je računarski problem utvrdivanja da li su dva konačna grafa izomorfna. Pored praktičnog značaja, problem izomorfizma grafova je veoma
  • меморијски капацитет рачунара се стално повећавају, али се повећава и количина података која се анализира. Ако алгоритми нису скалабилни, тада чак и јако велика
  • Braun - Forsajtov test, ili se grafički mogu procenjivati korišćenjem Q Q grafa Ako su veličine dve grupe uzoraka koje se uporeduju jednake, Studentov
  • River War: An Historical Account of the Reconquest of the Soudan. Carroll & Graf Publishers New York City ISBN 978 - 0 - 7867 - 0751 - 5 - Clammer, Paul 2005
  • часова и њиховим посадама дато је десет минута да напусте бродове ради контроле С обзиром да су британске контролне групе остале на Санта Исабели седам
  • Wirtschaftsverlag NW, Dortmund. 2002. ISBN 978 - 3 - 89701 - 822 - 8.. Alain Kiener, Maggie Graf Jürg Schiffer, Ernesta von Holzen Beusch, Maya Fahrni: Mobbing und andere
  • ISBN 978 - 0 - 11 - 621278 - 8. Oppenheimer, Stephen 2006 Origins of the British. Carroll & Graf ISBN 978 - 0 - 7867 - 1890 - 0. Pevsner, Nikolaus 1942 An outline of European

Users also searched:

...