Algorytm symulowanego wyżarzania w projektowaniu układów VLSI

Raport z projektu wykonanego w ramach przedmiotu "Metody i algorytmy sztucznej inteligencji"

Autorzy: Artur Rudziński (133151), Grzegorz Stachowiak(133163)

Prowadzący: dr inż. Witold Paluszyński

Data: 21.06.2007 r.

Plan raportu

1. Opis zadania
   
2. Metoda rozwiązania problemu
   
3. Implementacja algorytmu symulowanego wyżarzania
   
4. Implementacja algorytmu NEH
   
5. Wyniki badań
   
6. Opracowanie wyników
   
7. Źródła
   

1. Opis zadania

Celem naszego projektu było zastosowanie algorytmu symulowanego wyżarzania oraz dowolnego innego algorytmu do optymalizacji układów VLSI. Dodatkowo mieliśmy porównać wyniki zwracane przez każdy z algorytmów z wynikami uzyskanymi przez dr inż. Andrzeja Kozika. Gdyby którykolwiek z algorytmów dawał o wiele gorsze wyniki od pozostałych, należałoby dokonać próby jego modyfikacji w taki sposób, aby otrzymywane wartości były zbliżone do siebie.

Optymalizacja układów VLSI polega na takim ułożeniu prostokątnych modułów elektronicznych, aby pole prostokąta utworzonego przez ich zewnętrzne krawędzie było jak najmniejsze. Idea ta przedstawiona jest na rysunku poniżej.

Szare prostokąty o numerach od 1 do 5 symbolizują moduły elektroniczne, natomiast obszar w kolorze białym to niewykorzystane miejsce w układzie. Przy projektowaniu układów VLSI należy dążyć do minimalizacji powierzchni właśnie tego obszaru.

2. Metoda rozwiązania zadania

W celu przeprowadzenia badań dokonaliśmy impelmentacji algorytmu symulowanego wyżarzania oraz algorytmu NEH w języku C++. Następnie przeprowadziliśmy testy wykorzystując standardowe pliki z danymi, które używane są w tego rodzaju problemach. Pliki pobraliśmy ze strony http://www.ee.utulsa.edu/~tmanikas/MCNC/MCNC_Benchmark_Netlists.html. Celem badań było określenie jakie parametry algorytmu symulowanego wyżarzania mają największy wpływ jakość otrzymywanych wyników (minimalizację rozmiarów układu). W algorytmie symulowanego wyżarzania po zmianie każdego z parametrów przeprowadzaliśmy sześciokrotnie pomiary a następnie obliczaliśmy na ich podstawie wartość średnia oraz wyznaczyliśmy wartości minimalną i maksymalną. Dla algorytmu NEH pomiary przeprowadzaliśmy jednokrotnie, ponieważ algorytm ten daje zawsze takie same wyniki.

Do reprezentacji ułożenia elementów użyliśmy tak zwanego "sequence pair". Są to dwie permutacje X oraz Y. Każda permutacja zawiera te same elementy , jednak w różnej kolejności. Dzięki temu można określić położenie każdego elementu na płytce.

• a) X = {.. a .. b ..}, Y = {.. a .. b ..}
• b) X = {.. a .. b ..}, Y = {.. b .. a ..}

W przykładzie a) oraz b) przedstawiono przykładowe permutacje X oraz Y. Dla przykładu a) można powiedzieć, że moduł b znajduje się conajmniej o wartość szerokości modułu na prawo od elementu a, natomiast w przykładzie b) element b znajduje się poniżej elementu a co najmniej o wartość wysokości elementu b. Aby określić położenie wszystkich elementów należy rozpatrzyć wzajemne położenie wszystkich par i na tej podstawie określić położenie lewego dolnego rogu każdego elementu. Do obliczania współrzędnych lewego dolnego rogu w oparciu o "sequence pair" można stosować wiele różnych podejść, np. można określić położenie każdego elementu na płytce.

• a) podejście grafowe, gdzie na podstawie grafu horyzontalnego oraz wertykalnego oblicza się najdłuższe ścieżki do danego elementu i dzięki temu uzyskuje się współrzędne x (graf horyzontalny), oraz y (graf wertykalny)
• b) podejście najdłuższej wspólnej podsekwencji do obliczania najdłuższej ścieżki do danego elementu

Nie będziemy tutaj opisywali tych metod, ponieważ jest to temat bardzo obszerny a nie to jest celem tego projektu. Zainteresowanych zachęcamy do zapoznania się z literaturą. Możemy natomiast powiedzieć, że w naszym projekcie wykorzystaliśmy algorytm obliczania najdłuższej wspólnej podsekwencji i na tej podstawie obliczaliśmy współrzędne każdego modułu. Metoda ta jest ona korzystniejsza jeżeli chodzi o złożoność obliczeniową (O(n²), gdzie n to liczba modułów w permutacji).

Dzięki "sequence pair" oraz algorytmowi obliczania współrzędnych lewego dolnego rogu mogliśmy obliczyć wartość funkcji celu, czyli pola płytki, na której znajdują się elementy.

3. Implementacja algorytmu symulowanego wyżarzania

Symulowane wyżarzanie jest algorytmem przybliżonym. Jest to rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Sposób działania symulowanego wyżarzania nieprzypadkowo przypomina zjawisko wyżarzania w metalurgii. Poniżej przedstawiony jest ten algorytm w pseudokodzie.

Algorytm symulowanego wyżarzania
(N - sąsiedztwo; f - funkcja celu)
01: wybierz rozwiązanie początkowe - startowe losowe X, Y;
02: ustaw temperatura początkowa t = t0; {t0 > 0}
03: przyjmij funkcje redukcji temperatury α;
04: repeat
05:    repeat
06:       w sposób losowy wybierz s należące do N(s0);
07:       δ = f(s) - f(s0);
08:       if δ < 0 then
09:          s0 = s;
10:       else
11:          wygeneruj losowa wartość x z przedziału (0, 1);
12:          if x < exp(-δ /t) then
13:             s0 = s;
14:          end if
15:       end if
16:    until liczba iteracji = n
17:    t = α(t);
18: until warunek zakończenia optymalizacji jest spełniony

W naszym problemie wybierając kolejną losową permutacje z sąsiedztwa permutacji bieżącej w danym momencie, stosowaliśmy 3 rodzaje ruchów:

• a) zamiana miejscami dwóch losowych elementów w obu permutacjach (w każdej zamieniane były te same elementy)
• b) zamiana wysokości z szerokością jednego elementu, czyli jego obrót o 90 stopni
• c) zamiana miejscami dwóch elementów ale tylko w permutacji X

Wartość losowa w naszym algorytmie jest losowana za pomocą standardowej funkcji rand(), a użytkownik aplikacji ma możliwość zmiany takich parametrów jak :

• temperatura początkowa
• temperatura końcowa
• ilość iteracji dla danego poziomu temperatury
• współczynnik redukcji temperatury, geometryczna redukcja temperatury

Algorytm jest algorytmem przybliżonym , tzn. dającym wyniki których jakość jest zależna od parametrów oraz od pewnego prawdopodobieństwa z którym akceptowane są gorsze rozwiązania.

4. Implementacja algorytmu NEH

NEH jest algorytmem deterministycznym czyli zawsze dającym te same wyniki dla danego zestawu danych. Idea algorytmu jest raczej prosta jednak jak się okazuje daje bardzo zadowalające wyniki w stosunkowo krótkim czasie a złożoność algorytmu wynosi O(n²). Dlatego zdecydowaliśmy się na wybór tego właśnie algorytmu

Poniżej przedstawiony został opis algorytmu w postaci pseudokodu

Algorytm NEH
X -- pierwsza permutacja (pusta), Y -- druga permutacja (pusta), Z -- tablica elementów do ułożenia
01: Posortuj Z pod względem pola elementu - malejąco
02: wstaw Z[0] do X oraz Y
02: for i=1 to liczba elementów
03:     for ii=0 to 1
04:       obróć Z[i] o 90 %
05:        for j=0 to i
06:          włóż Z[i] w miejsce X[j]
07:          for k=0 to i
08:             włóż Z[i] w miejsce Y[k]
09:             oblicz funkcje celu f
10:          end
11:       end
12:    end
13:    zapamiętaj taką permutacje X oraz Y, dla której f miała wartość minimalną
14: end

5. Wyniki badań

W tabeli poniżej przedstawiono podstawowe informacje dotyczące plików z danymi wejściowymi.

Poniżej przedstawiliśmy wyniki przeprowadzonych przez nas pomiarów.

Algorytm symulowanego wyżarzania

Plik ami49.yal

Przykładowe rozmieszczenie modułów z pliku ami49 (powierzchnia układu - 3824724μm²)

Plik ami33.yal

Przykładowe rozmieszczenie modułów z pliku ami33 (powierzchnia układu - 1217160μm²)

Plik apte.yal

Przykładowe rozmieszczenie modułów z pliku apte (powierzchnia układu - 50029640μm²)

Plik hp.yal

Przykładowe rozmieszczenie modułów z pliku hp (powierzchnia układu - 9031680μm²)

Plik xerox.yal

"Przykładowe rozmieszczenie modułów z pliku xerox (powierzchnia układu - 20954948μm²)

Algorytm NEH

Poniżej przedstawiono wyniki badań algorytmu NEH.

Rozmieszczenie elementów zwracane przez algorytm NEH dla plików: a) ami49; b) ami33; c) apte; d) hp; e)xerox.

Zestawienie otrzymanych wyników

W poniższej tabeli przedstawione zostały wartości powierzchni układów otrzymane w badaniach przeprowadzonych przez dr inż. Andrzeja Kozika, oraz minimalne wartości powierzchni jakie uzyskaliśmy podczas przeprowadzanych przez nas pomiarów.

W poniższej tabeli przedstawione zostały czasy działania poszczególnych algorytmów otrzymane w badaniach przeprowadzonych przez dr inż. Andrzeja Kozika, oraz podczas pomiarów przeprowadzonych przez nas.

Parametry komputerów przeznaczonych do testowania poszczególnych algorytmów: Enhanced O-Tree - Sparc Ultra60; TCG-S - Sparc Ultra60; Fast-SP - Sparc Ultra-I; SP/Parquet-1 - 800Mhz Pentium III/Linux; GIT i TSA - 1.1 Ghz Celeron/WindowsXP; Symulowane wyżarzanie - 1824MHz AMD AtlonXP 2500+/WindowsXP; NEH - 1824MHz AMD AtlonXP 2500+/WindowsXP.

6. Opracowanie wyników

Krótka charakterystyka działania obu algorytmów

Algorytm symulowanego wyżarzania jest algorytmem losowym, który z pewnym prawdopodobieństwem jest w stanie zaakceptować gorsze rozwiązanie, czyli wybrać takie permutacje X oraz Y z sąsiedztwa danego rozwiązania, które będzie charakteryzowało się gorszą wartością funkcji celu (pole płytki elektronicznej). Tak naprawdę im mniejsza jest temperatura tym mniejsze jest prawdopodobieństwo zaakceptowania stanu o gorszej wartości funkcji celu. Dlatego algorytm na początku "błądzi" po różnych rozwiązaniach lepszych i gorszych, jednak w miarę zmniejszania się temperatury "zagłębia" się w okolice pewnego ekstremum lokalnego, jednak z pewnym prawdopodobieństwem ciągle ma szanse wskoczyć w rozwiązanie gorsze, co nie zawsze oznacza, że w następnych iteracjach otrzymamy gorszy wynik. Jak wynika z idei algorytmu na ilość iteracji ma wpływ głównie temperatura początkowa, współczynnik redukcji, temperatura końcowa oraz ilość iteracji dla jednego poziomu temperatury. Jak łatwo stwierdzić są to prawie wszystkie parametry algorytmu. Dlatego algorytm daje średnio tym lepsze wyniki im więcej będzie iteracji. Nasza aplikacja ma temperaturę końcową ustawioną domyślnie na 10e^-10, dzięki czemu w końcowej fazie działania algorytmu tak naprawdę szukamy rozwiązania najlepszego w okolicach jednego ekstremum. Algorytm symulowanego wyżarzania jest algorytmem, który wykorzystuje w swojej idei pewną losowość dlatego aby uzyskać satysfakcjonujący nas wynik należy dany zestaw danych przebadać kilkakrotnie oraz zmieniać parametry.

Rysunek ideowy przedstawiający działanie algorytmu symulowanego wyżarzania

Algorytm NEH jest natomiast algorytmem deterministycznym, który zawsze daje te same wyniki. Nie posiada żadnych parametrów, według których oblicza wartość funkcji celu. Jego zaletą a jednocześnie wadą jest z góry określony czas działania, który jest proporcjonalny do ilości danych. Możemy powiedzieć, że algorytm ten daje "zadowalające" wyniki z porównaniu z algorytmem symulowanego wyżarzania . Szczególnie dla dużej ilości danych, algorytm symulowanego wyżarzania musi wykonać odpowiednio dużo iteracji, co wpływa na czas jego działania, natomiast algorytm NEH działa stosunkowo krótko dając przy tym porównywalne wyniki. Jednak algorytm symulowanego wyżarzania ma tą przewagę, że zmieniając odpowiednio parametry można uzyskać tyle iteracji, iż w końcu znajdzie lepsze rozwiązanie (jeżeli oczywiście takie rozwiązanie istnieje).

Porównanie wyników

Dla naszych testów algorytm symulowanego wyżarzania okazał się lepszy dla danych z każdego pliku. Nie były to jednak duże różnice , np. dla pliku ami49 różnica pomiędzy najmniejszą wartości funkcji celu otrzymaną algorytmem wyżarzania i NEH wynosiła około 3%. W wielu przypadkach symulowane wyżarzanie dawało wyniki gorsze od algorytmu NEH, jednakże zależą one od wartości parametrów, których odpowiednia zmiana pozwoli w końcu uzyskać lepsze rozwiązanie niż NEH.

Na podstawie wyników pomiarów możemy stwierdzić, że na wartość funkcji celu ma wpływ wartość temperatury początkowej. Zauważyliśmy, że średnie wartości powierzchni obliczone na podstawie serii pomiarów zależą w niewielkim stopniu od temperatury początkowej, jednakże najmniejsze wartości powierzchni otrzymaliśmy przy najwyższej temperaturze początkowej. Na skrajnie złe wyniki obliczeń naszym zdaniem ma wpływ zbyt wysoka wartość temperatury końcowej. Najwięcej maksymalnych wartości pola układy zostało otrzymanych dla największej ustalonej przez nas temperatury końcowej 1e-4. Prawdopodobnie wynika to z faktu, iż dla niskiej temperatury algorytm szuka lepszego rozwiązania w obrębie jednego ekstremum i z bardzo małym prawdopodobieństwem przechodzi do innego ekstremum. Dlatego naszym zdaniem im mniejsza temperatura końcowa tym algorytm ma większą szanse, na zbliżenie się do minimum lokalnego, które w niektórych przypadkach może się okazać minimum globalnym. Współczynnik redukcji temperatury tak jak i ilość iteracji dla jednej temperatury zwiększa jedynie ilość przeszukanych rozwiązań, czyli wpływa tak naprawdę na ilość iteracji całego algorytmu. Im więcej iteracji dla jednego poziomu temperatury oraz im większy współczynnik redukcji tym wyniki będą lepsze.

W porównaniu naszych wyników do wyników opublikowanych w pracy doktorskiej dr inż. Andrzeja Kozika stwierdzamy, iż w większości przypadków algorytm symulowanego wyżarzania zaimplementowany przez nas plasował się mniej więcej w połowie jeżeli chodzi o minimalne znalezione rozwiązanie. Spośród wszystkich algorytmów uzyskał najlepszy wynik dla pliku xerox. Warto wspomnieć, że nigdy nie miał najgorszego rozwiązania. Algorytm NEH niestety wypadł trochę gorzej (różnice są rzędu kilku procent), w dwóch przypadkach miał wyniki lepsze od algorytmu GIT.

Czasy obliczeń uzyskiwane przez nasze algorytmy są zazwyczaj lepsze od czasów takich algorytmów jak Enh. O-Tree, TCG-S, FastSP czy SP (Parquet-1) jednak należy wspomnieć, że pomiary były przeprowadzane na różnym sprzęcie i w tym przypadku nie ma sensu ich porównywać.

7. Źródła

"Placement Constaraints in Floorplan Design" - Evangeline F. Y. Young, Chris C. N. Chu, and M. L. Ho (PDF)
"Fast Evaluation of Sequence Pair in Block Placement by Longest Common Subsequence Computation" - Xiaoping Tang, Ruiqi Tian, and D. F. Wong (PDF)
"My brief description of the YAL format" - Ted Manikas (PDF)
MCNC Benchmark Netlists for Floorplanning and Placement
"Metoda wstawień w klasycznych problemach szeregowania. Cz. I. Problem przepływowy" - Eugeniusz Nowicki, Mariusz Makuchowski

Aplikacje stworzone przez nas w ramach projektu zostały napisane w języku C++ przy użyciu darmowego oprogramowania firmy Borland dostępnego na stronie producenta.