Dynamiczne uporz膮dkowanie zmiennych w diagramach辌yzyjnych 2


Krzysztof Grudzie艅 gr. 21

Referat

Dynamiczne porz膮dkowanie zmiennych w Diagramach Decyzyjnych

(Dynamic variable ordering in Decision Diagrams)

  1. Wst臋p

Najbardziej znanym sposobem przedstawienia funkcji logicznych jest przedstawienie ich za pomoc膮 tablicy prawdy, jednak jej rozmiar wzrasta wykladniczo wraz ze wzrostem ilo艣ci zmiennych. Najcz臋sciej, tam gdzie mamy do czynienia z du偶膮 ilo艣ci膮 zmiennych efektywniejszym sposobem reprezentacji s膮 diagramy decyzyjne (DD). Najbardziej popularn膮 struktur膮 s膮 uporz膮dkowane binarne diagramy decyzyjne.

Binarny diagram decyzyjny (BDD) reprezentuje zbi贸r binarnych decyzji. Wynikiem ostatecznej decyzji jest albo PRAWDA (1), albo FA艁SZ (0). Diagramy decyzyjne mo偶na przedstawi膰 w postaci drzew lub skierowanych graf贸w acyklicznych z korzeniem, gdzie decyzje s膮 zwi膮zane z wierzcho艂kami. BDD s膮 otrzymywane przez redukcj臋 binarnych drzew decyzyjnych.

Uporz膮dkowany binarny diagram decyzyjny opisuje funkcj臋 taka, 偶e:

gdzie index(v) jest wska藕nikiem do zmiennej wej艣ciowej oraz dw贸ch potomk贸w low(v) oraz high(v)

0x01 graphic

rys. 1 zredukowane, uporz膮dkowane BDD

dla funkcji

  1. Kolejno艣膰 zmiennych w diagramach decyzyjnych

Binarne diagramy decyzyjne (BDD) daj膮 kanoniczn膮 form臋 funkcji logicznych przy okre艣lonej kolejno艣ci zmiennych wej艣ciowych, jednak zmiana uporz膮dkowania zmiennych mo偶e powodowa膰 powstanie r贸偶nych BDD dla tej samej funkcji. Rezultat takiego sortowania zale偶y bezpo艣rednio od natury reprezentowanej funkcji i czasami rozmiary BDD mocno si臋 mi臋dzy sob膮 r贸偶ni膮. Zastosowanie odpowiedniej kolejno艣ci zmiennych jest bardzo wa偶nym problemem w technikach DD. Proces okre艣lenia najlepszego porz膮dku zmiennych w grafie nale偶y do proces贸w NP - trudnych, a najbardziej znany algorytm ma z艂o偶ono艣膰 O(), gdzie - liczba w臋z艂贸w. Istniej膮ce algorytmy ograniczaj膮 si臋 do ma艂ej ilo艣ci zmiennych. Trudnym zadaniem jest znalezienie najlepszej kolejno艣ci zmiennych dla wi臋kszych funkcji w rozs膮dnym czasie. Przy znajdowaniu najlepszego porz膮dku w grafie mo偶na pos艂u偶y膰 si臋 nastepuj膮cymi empirycznymi zasadami:

  1. Umiejscowienie obok siebie grup zmiennych blisko ze sob膮 powi膮zanych.

  2. Zmienne, kt贸re w du偶ym stopniu wp艂ywaj膮 na warto艣膰 funkcji powinny znale藕膰 si臋 na wy偶szych pozycjach.

Najbardziej obiecuj膮cymi metodami minimalizacji BDD s膮 metody oparte na dynamicznym porz膮dkowaniu zmiennych (Dynamic Variable Ordering - DVO), tzn. na poprawianiu rozmiaru grafu stosuj膮c wymiany s膮siednich zmiennych (variable exchanging).

  1. Wymiana s膮siednich zmiennych

Podstawow膮 operacj膮 dynamicznego porz膮dkowania zmiennych jest wymiana s膮siednich zmiennych(zmiennych na s膮siednich poziomach). Wymiana jest przeprowadzana bardzo szybko jako 偶e tylko na tych poziomach kraw臋dzie musz膮 by膰 przeadresowane. W ten spos贸b rozmiar jest optymalizowany bez ca艂kowitej rekonstrukcji BDD. Przeprowadzana jest tylko lokalna transformacja dla dw贸ch poziom贸w. Jest to spowodowane spostrze偶eniem, 偶e BDD s膮 form膮 kanoniczn膮. Wymiana dw贸ch zmiennych nie zmienia poddiagram贸w innych poziom贸w.

Mamy dane BDD dla funkcji z porz膮dkiem zmiennych , celem wymiany na pozycjach k, oraz k+1 jest , aby przekszta艂ci膰 do z porz膮dkiem zmiennych dla tej samej funkcji , gdzie i r贸偶ni膮 si臋 tylko na pozycjach k oraz k+1 tzn. oraz . Nazywamy t膮 operacje wymian膮 poziom贸w (Level Exchange -LE).

0x01 graphic

rys.2 zamiana s膮siednich zmiennych

Realizacj臋 LE wida膰 na rysunku 2. To, 偶e wymiana zmiennych jest poprawnie przeprowadzona przez wymian臋 oraz wynika bezpo艣rednio z dekompozycji Shannona. Wszystkie inne przypadki (np. ) mog膮 by膰 zredukowane do przypadku na rys. 2. Og贸lnie, wymiana poziomu oraz poziomu jest realizowana przez dost臋p do w臋z艂贸w poziomu i przeadresowanie odpowiadaj膮cych im wska藕nik贸w low oraz high. (Tutaj poziom oznacza zbi贸r w臋z艂贸w oznaczonych przez zmienn膮.) Operacja wymiany poziom贸w nie wp艂ywa na g贸rne i dolne cze艣ci BDD. Ponadto, ta metoda jest rozszerzalna do BDD zawieraj膮cych „comlemented edges” (CE) bez straty na efektywno艣ci.

Je偶eli zmienna jest bezpo艣rednio przed zmienn膮 i je艣li wszystkie wez艂y mog膮 zosta膰 odwiedzone w czasie liniowym (linear time), wtedy wymiana poziom贸w dla oraz mo偶e zosta膰 przeprowadzona w czasie

W艂asno艣膰 powy偶szego twierdzenia stosuje si臋 do wiekszo艣ci typ贸w DD. Ale istniej膮 typy DD, gdzie wymiana poziom贸w , nie jest ju偶 lokaln膮 operacj膮, np. w K*BMD.

  1. Permutacja okien (window permutation)

Algorytm permutacji okien:

Window_permutation (F,m.):

do

for (wszystkie okna m zmiennych)

wylicz maksymaln膮 redukcj臋 rozmiaru uzyskiwaln膮 przez permutacj臋;

przeprowad藕 permutacj臋 m zmiennych z maksymaln膮 redukcj膮;

while (mo偶liwa redukcja);

W algorytmie window permutation, okno o wyznaczonym rozmiarze m jest przenoszone na n zmiennych. Dla ka偶dej pozycji okna, rozwa偶ane s膮 wszystkie permutacje zmiennych i odpowiadaj膮ce im rozmiary BDD. Permutacja z maksymaln膮 redukcj膮 rozmiaru jest zapami臋tywana. Jest to wykonywane dla wszystkich n - m + 1 pozycji okna. Nastepnie jest przeprowadzana permutacja z maksymaln膮 redukci膮 rozmiaru. Proces jest powtarzany tak d艂ugo, a偶 mo偶na uzyska膰 redukcj臋 rozmiaru. (Nale偶y zauwazy膰, 偶e tylko okna zawieraj膮ce zmienn膮, kt贸ra zmieni艂a swoj膮 pozycj臋 musz膮 by膰 ponownie przeliczone.) Aby sprawdzi膰 wszystkie m! permutacji w zadanym oknie, stosowane s膮 transpozycje, tj. LE (level exchange), w z g贸ry ustalonym porz膮dku. Dla m=3, porz膮dek mo偶e by膰 wybrany jak poni偶ej:

0x08 graphic

Ta koncepcja mo偶e by膰 uog贸lniona dla ka偶dego m>3. Oczywi艣cie, wyb贸r m jest istotny dla jako艣ci wynik贸w minimalizacji, np. m=n odpowiada problemowi dok艂adnej minimalizacji (exact minimization), dlatego daje najlepsze wyniki, lecz jest niewykonalny z powodu wymaga艅 czasowych. Z drugiej strony m=2 prowadzi do bardzo efektywnego czasowo algorytmu, wymagaj膮cego poprawy rozmiaru dla ka偶dej wymiany poziom贸w (LE), co oznacza, 偶e mo偶e 艂atwo zosta膰 z艂apany przez lokalne minima.

W praktyce rozmiar okna m=3,4 jest wykonalny i prowadzi do poprawy w porz膮dku zmiennych .

V. Przesiewanie (sifting)

Algorytm przesiewania bierze pod uwag臋 kolejno wszystkie zmiene diagramu decyzyjnego. Kiedy zmienna jest wybrana, celem jest znalezienie najlepszej pozycji dla zmiennej przyjmuj膮c, 偶e wzgl臋dny porz膮dek wszystkich innych zmiennych pozostaje bez zmian. W pierwszym kroku okre艣lony zostaje porz膮dek w kt贸rym zmienne maj膮 by膰 rozwa偶ane. Jest to dokonywane przez sortowanie poziom贸w wed艂ug ich rozmiar贸w zaczynaj膮c od najwi臋kszego. Aby znale藕膰 najlepsz膮 pozycj臋, zmienna jest przenoszona poprzez ca艂y diagram. Jest to wykonywane w trzech krokach:

  1. Zmienna jest zamieniana ze zmienn膮 b臋d膮c膮 jej nast臋pnikiem (successor) a偶 nie b臋dzie to ostatnia zmienna przy porz膮dkowaniu.

  2. Zmienna jest zamieniana ze swoim poprzednikiem (predocessor) a偶 nie b臋dzie to najwy偶sza zmienna.

  3. Zmienna jest przenoszona z powrotem do najbli偶szej pozycji kt贸ra prowadzi艂a do minimalnego rozmiaru BDD.

Zaproponowano tak偶e kilka udoskonale艅 do oryginalnego algorytmu przesiewania:

Podczas przesiewania chcemy zatrzyma膰 poruszanie si臋 zmiennej w danym kierunku tak wcze艣nie jak to tylko mo偶liwe, je偶eli nie mo偶emy osi膮gn膮膰 dalszej poprawy. W naszym podej艣ciu u偶yjemy efektywnej techniki obliczania dolnych granic (lower bounds computation), kt贸ra daje informacje o tym, czy dalsza redukcja rozmiaru BDD jest mo偶liwa.

Je艣li modyfikacja porz膮dku zmiennych nie jest ograniczona, wiadomo, 偶e mo偶liwa jest r贸偶nica nawet wyk艂adnicza. Jednak偶e je艣li rodzaj modyfikacji jest w jaki艣 spos贸b ograniczony ( co nast臋puje w przypadku u偶ycia podczas przesiewania, poniewa偶 tylko jedna zmienna mo偶e zmieni膰 swoj膮 lokacj臋), mo偶na zada膰 bardziej ograniczone dolne granice.

Dolna granica ma miejsce je艣li zmienne g贸rnej cze艣ci BDD pozostaj膮 niezmienione, ale porz膮dek zmiennych w dolnej cz臋艣ci mo偶e zosta膰 zmieniony dowolnie.

Je偶eli u偶yto tej techniki dla dok艂adnej minimalizacji BDD mo偶liwe s膮 znacz膮ce r贸偶nice w czasie przebiegu. Jednak je偶eli u偶yto jej do przesiewania to s膮 one zbyt og贸lne, by da膰 dobre oszacowania rozmiaru wynikowego BDD. Ponadto s膮 za bardzo czasoch艂onne, gdy偶 konieczne jest odwiedzenie ca艂ego grafu.

VI.Granice dla zamian mi臋dzypoziomowych (Bounds for Level Exchanges)

Sprawdzimy teraz wzrost ilo艣ci wez艂贸w dla wymiany poziom贸w.

Przyjmijmy, 偶e funkcja zale偶y od swoich wszystkich zmiennych.

Niech b臋dzie funkcj膮 boolowsk膮 reprezentowan膮 przez BDD. Oznaczmy ilo艣膰 w臋z艂贸w zwi膮zanych ze zmienn膮 jako . Dla podzbioru zmiennych ta definicja jest rozszerzona do .

Mamy nast臋puj膮ce twierdzenie:

Tw. 1

Niech . Je艣li poziomy i oraz i+1 s膮 zamieniane, wynikowe rozmiary s膮 ograniczone przez:

oraz:

Wszystkie inne poziomy pozostaj膮 niezmienione.

Dow贸d: Rozwa偶my cztery przypadki:

1: : Przyjmuj膮c, 偶e funkcja zale偶y od , musi istnie膰 co najmniej jeden w臋ze艂 na tym poziomie.

2: : Ta nier贸wno艣膰 ma miejsce, poniewa偶 ka偶dy w臋ze艂 na poziomie , kt贸ry zale偶y od mo偶e prowadzi膰 do najwy偶ej dw贸ch w臋z艂贸w, dla ka偶dej mo偶liwej warto艣ci . Je偶eli w臋ze艂 nie zale偶y od , pozostaje niezmieniony.

3: : Ta nier贸wno艣膰 jest po prostu odwr贸ceniem poprzedniej. Wymiana dw贸ch poziom贸w dwa razy prowadzi do oryginalnej reprezentacji.

4: : Liczba wsp贸艂czynnik贸w, kt贸ra ma by膰 reprezentowana na poziomie nie mo偶e byc wi臋ksza ni偶 liczba wsp贸艂czynnik贸w kt贸re ju偶 s膮 reprezentowane na poziomach oraz .Poniewa偶 ka偶dy w臋ze艂 w BDD reprezentuje wsp贸艂czynnik w odniesieniu do wszystkich zmiennych w g贸rnej cz臋艣ci, ta liczba nie mo偶e si臋 zmieni膰 poprzez lokaln膮 operacj臋. Wszystkie wyniki dotycz膮 BDD z CE orez bez CE.

Przyk艂ad:

Rozwa偶my funkcj臋 przedstawion膮 na rysunku 3.

0x01 graphic

rys. 3

Je偶eli jest najwy偶sz膮 zmienn膮, rozmiar dw贸ch pierwszych poziom贸w wynosi 4, podczas gdy ilo艣膰 w臋z艂贸w jest zredukowana o dwa je偶eli dwie najwy偶sze zmienne s膮 zamienione.

Je艣li s膮siaduj膮ce poziomy nie oddzia艂uj膮 mi臋dzy sob膮, wynikowe rozmiary poziom贸w pozostaj膮 niezmienione, tzn. . Mo偶na to sprawdzi膰 za pomoc膮 macierzy incydencji.

VII. Dolne granice dla jednej zmiennej (Lower Bounds for one Variable)

Teraz rozwa偶ymy wp艂yw dolnych granic na rozmiar BDD je艣li pojedyncza zmienna jest przesuwana przy porz膮dkowaniu zmiennych, a wzgl臋dny porz膮dek wszystkich innych zmiennych pozostaje bez zmian.

Przyjmijmy, 偶e zmienna jest na poziomie . Przenosz膮c poziom w d贸艂 do poziomu , wszystkie w臋z艂y, kt贸re s膮 ponad poziomem (tzn. poziomy ), oraz wszystkie w臋z艂y poni偶ej poziomu (tzn. poziomy ) nie zmieniaj膮 si臋. Ponadto w臋z艂y, pomi臋dzy tymi poziomami, z kt贸rymi zmienna nie oddzia艂ywuje tak偶e si臋 nie zmieniaj膮. Tak wi臋c suma tych trzech liczb stanowi doln膮 granic臋 (lower bound). Lecz poniewa偶 ta technika sumuje tylko ilo艣膰 w臋z艂贸w kt贸re nie s膮 „dotkni臋te” przez przenoszon膮 zmienn膮, cz臋sto jest nieefektywna.

Aby udoskonali膰 t臋 technik臋, problem jest dalej dzielony na dwa przypadki , pierwszy, gdy zmienna jest przenoszona do g贸ry, drugi gdy jest przenoszona w przeciwnym kierunku.

Niech b臋dzie funkcj膮 boolowsk膮 reprezentowan膮 przez BDD. Przyjmijmy, 偶e pocz膮tkowy porz膮dek zmiennych jest . Z iteracyjnego zastosowania Tw. 1 otrzymujemy dwa nast臋puj膮ce wnioski:

Wniosek 1: Niech . Je偶eli poziom jest przeniesiony w d贸艂 do poziomu co powoduje porz膮dek zmiennych: , to dla rozmiaru wynikowego BDD mamy nier贸wno艣膰:

oraz:

gdzie , ,

Wniosek 2: Niech . Je偶eli poziom jest przeniesiony do g贸ry do poziomu co powoduje porz膮dek zmiennych: to dla rozmiaru wynikowego BDD otrzymujemy:

gdzie , ,

Ponadto, poziomy kt贸re nie oddzialywuj膮 z , mog膮 by膰 dodane do obu dolnych granic..

  1. Przesiewanie „lower bound” (Lower Bound Sifting)

Podczas przesiewania przemieszczanie zmiennej mo偶e zosta膰 zaniechane, je偶eli to nie mo偶e polepszy膰 ju偶 znanego, najlepszego rozmiaru BDD. Innymi s艂owy je偶eli wiadomo, 偶e rozmiar BDD nie mo偶e zosta膰 poprawiony przez dalsze przesiewanie zmiennej, mo偶na je zatrzyma膰. Aby zdecydowa膰 czy poprawa jest nadal mo偶liwa, u偶ywane s膮 dolne granice dla jednej zmiennej. W przypadku przenoszenia zmiennej w d贸艂 to daje:

gdzie , oraz oznaczaj膮ce BDD po przeniesieniu zmiennej na pozycj臋 . Je偶eli „lower bound” jest wi臋ksza ni偶 najlepszy wcze艣niej znaleziony rozmiar BDD, poruszanie si臋 w tym kierunku nie mo偶e prowadzi膰 do lepszej pozycji dla zmiennej. Analogicznie dolna granica jest liczona dla przenoszenia zmiennej w d贸艂. Obliczanie dolnej granicy mo偶e by膰 przeprowadzone lokalnie, co jest bardziej efektywne ni偶 przy dok艂adnej minimalizacji BDD, gdzie wymagane jest przechodzenie ca艂ego BDD.

Pseudokod dla algorytmu przesiewania w d贸艂 (sifting down-algorithm):

SiftingDown(i : level to sift)

lb = compute lower bound();

best = size of BDD();

while (i <nand lb _ best)

level exchange(i, i + 1);

lb = compute lower bound();

if (size of BDD() < best) best = size of BDD();

i = i + 1;

Ta technika nazywana jest lower bound sifting (lb-sifting). Nale偶y zauwa偶y膰, 偶e jako艣膰 (zmierzona przez liczb臋 w臋z艂贸w) lb-sifting jest taka sama jak dla „klasycznego” przesiewania (classical sifting), ale dzi臋ki dolnym granicom obliczenia s膮 znacznie przyspieszone, poniewa偶 musi zosta膰 przeprowadzonych o wiele mniej wymian.

Czas wykonywania si臋 dynamicznej zmiany porz膮dku zmiennych mo偶e by膰 bardziej skr贸cony, je艣li dolne granice zostan膮 obni偶one (relaxed): Jest nieprawdopodobnym, 偶eby podczas przesiewania po艂owa z w臋z艂贸w znika艂a w ka偶dym kroku. Dlatego rozwa偶amy nie tylko granic臋 , ale proste uog贸lnienie do . Oczywi艣cie nie jest to prawdziwa dolna granica, ale przez to rozszerzenie przesiewanie rozwa偶a tylko obszary poszukiwa艅, gdzie mo偶liwe s膮 znaczne zyski. Granica jest wykorzystywana do przemieszczania zmiennych do g贸ry i na d贸艂.

Okazuje si臋, 偶e u偶ycie granicy jest dobrym wyborem dla . W tym przedziale, obni偶ona dolna granica znacznie przyspiesza algorytm przesiewania bez zbytniego zwi臋kszania rozmiary wynikowego BDD.

  1. Wyniki eksperymentalne

W pierwszej serii eksperyment贸w, por贸wnujemy oryginalny algorytm przesiewania z algorytmem ulepszonym przez dolne granice (lb-sifting) . Przesiewanie lb (lb-sifting) wymaga 艣rednio 53.5% mniej wymian oraz wykonuje si臋 szybciej o 69.1%. W drugiej serii eksperyment贸w zmierzono wp艂yw obni偶onych dolnych granic. Por贸wnanie dla zwi臋kszaj膮cych si臋 warto艣ci b wykazuje, 偶e dla ma艂ych warto艣ci b, np. b=10, wzrost ilo艣ci w臋z艂贸w jest bardzo ma艂y, ale zysk jest znaczny, tzn. wi臋cej ni偶 7-krotny, w por贸wnaniu do klasycznego przesiewania.

0x01 graphic

0x01 graphic



Wyszukiwarka

Podobne podstrony:
zmienne dynamiczne
tp w 11 Wska藕niki i zmienne wskazywane Zmienne dynamiczne
003 zmienne systemowe
Diagram komunikacji
Dynamika1
Badanie korelacji zmiennych
pr膮d zmienny malej czestotliwosci (2)
Techniki wywierania wplywu oparte na dynamice interakcji
Analiza dynamiczna chodu w fazie podporu
Sie膰 dzia艂a艅(diagram strza艂kowy) v 2
8(45) Diagramy klas cz2
FiR Zmienne losowe1
Diagram Ellinghama
4 operacje na zmiennych I

wi臋cej podobnych podstron