Poniższy artykuł to swoista opowieść o podróży autora w tematykę algorytmów rozmieszczania elementów w układach programowalnych (FPGA). W trakcie tego procesu zaimplementowano prosty symulator optymalizacji rozmieszczania w FPGA w języku Rust. Temat ten rzadko jest wyjaśniany w jednym miejscu z odnośnikami i działającą implementacją, ze względu na swoją niszowość, choć jednocześnie jest fascynujący, jak zauważa autor. Stanowiło to dla niego motywację do stworzenia wpisu wprowadzającego, choć ostatecznie okazał się on znacznie dłuższy, niż planował. Zdaje on sobie sprawę, że każde zdanie w tym wpisie mogłoby być rozwinięte o dodatkowe konteksty i szczegóły, jednak zdecydowano się na stosunkową zwięzłość.
W ramach swojej pracy doktorskiej autor zajmuje się między innymi algorytmem rozmieszczania i trasowania w układach FPGA. Do tego celu wykorzystuje algorytmy głębokiego uczenia, które wspierają go w modelowaniu i rozwiązywaniu problemów w ww. zakresie. W tym procesie autor zgłębiał kod źródłowy narzędzia VPR oraz przeglądał najnowsze prace na temat elektrostatycznego rozmieszczania i trasowania, takie jak DreamPlace czy klasyk odnoszący się do routerów PathFinder. Analizując opublikowane badania, twórca zbudował swoje zrozumienie szczegółów technicznych i historii doświadczeń w tej dziedzinie. Rozważając możliwość nauczenia się, przy okazji, języka programowania Rust, postanowił połączyć to z implementacją tych algorytmów dla FPGA. Jest to szczególnie istotne, gdyż struktury danych i wydajność obliczeniowa są kluczowe dla realnych narzędzi do rozmieszczania i trasowania w FPGA, a Rust oferuje w tym zakresie bardzo dużo. Chcąc uniknąć błędów związanych z pamięcią czy typami, autor wybrał Rust uznawany za język dobrze sprawdzający się w tych obszarach. Chociaż potrzeba nauki Rusta z perspektywy pracy może nie być tak wartościowa, jak poznanie dla samego poznania, twórca projektu zdecydował się na to podwójne wyzwanie.
W każdym razie postanowił uczyć się Rusta, pisząc jednocześnie prosty symulator rozmieszczania elementów w FPGA oparty na symulowanym wyżarzaniu. Jeśli znany jest Wam ten wątek, to możecie przejść dalej, do części artykułu poświęconej implementacji, wynikom i do kodu źródłowego. Pozostali mogą przeczytać o podstawach w tym zakresie.
Czym jest algorytm rozmieszczania dla FPGA
Rozmieszczanie w FPGA jest bardzo łatwe do sformułowania, gdy można być cierpliwym i buduje się uproszczoną wersję problemu.
Mamy graf netlisty (listy sieci połączeń), który reprezentuje obwód, gdzie węzłami są różne jego elementy, a krawędzie to połączenia. Jest też układ FPGA — dwuwymiarowa siatka miejsc, gdzie można umieścić węzły. Każde miejsce może pomieścić tylko jeden element obwodu, a także tylko jeden jego rodzaj. W prototypowym modelu są tylko 4 ich typy: CLB, BRAM, DSP oraz IO. Każdy węzeł w grafie należy do jednego z nich, a każde miejsce na układzie FPGA może pomieścić tylko jeden z tych bloków. Dodatkowo niektóre miejsca w układzie FPGA są przeznaczone wyłącznie dla np. bloków wejść/wyjść (IO), gdzie można umieścić węzły IO z grafu netlisty.
Zazwyczaj wiemy, że układ FPGA będzie miał więcej miejsc, niż jest to nam potrzebne pod wszystkie węzły grafu. Gdyby tak nie było, nie można byłoby ich pomieścić w układzie FPGA. Moglibyśmy się na tym po prostu zatrzymać, informując użytkownika, że układ FPGA jest za mały lub ich netlista jest za duża.
Celem działania przedmiotowego algorytmu rozmieszczania jest odwzorowanie każdego węzła z netlisty na miejsce w układzie FPGA. Gdyby to było wszystko, można by zwyczajnie wymieniać miejsca, gdzie węzeł może zostać umieszczony i lokować go na pierwszym dostępnym. Następnie można to zrobić dla wszystkich węzłów, aż się skończą i gotowe.
W rzeczywistości po rozmieszczeniu trzeba połączyć węzły zgodnie z ich krawędziami w grafie netlisty. Router będzie używał wygenerowanego rozwiązania wyjściowego, aby następnie prowadzić sygnały przy użyciu zasobów routingu w FPGA między umieszczonymi węzłami na układzie programowalnym. Jeśli losowo ulokujemy dwa węzły daleko od siebie, które są połączone w grafie netlisty, będziemy musieli poprowadzić między nimi długi: „przewód”. To nie jest dobre z kilku powodów, w tym z uwagi na zależności czasowe i obciążenia prądowe. Z tego powodu chcemy dokonać tego działania, minimalizując: „odległości” umieszczonych węzłów, które są ze sobą połączone. Ten cel algorytmu sprawia, że rozlokowywanie bloków w układzie staje się problemem nietrywialnym.
Jak ugryźć kwestię rozmieszczania elementów w FPGA
Rozwiązanie liniowej optymalizacji mieszanej
Dane zbioru węzłów, które trzeba umieścić, miejsca, w których można to zrobić, ograniczenia dla mapowania 1-1 oraz te w oparciu o typ węzła, umożliwiają dosyć klarowne sformułowanie tego zagadnienia jako problemu mieszanej optymalizacji liniowej, który jest badany od wielu lat. Dostępne są więc solwery gotowe do użycia. Jedyną rzeczą, którą trzeba zrobić, to sformułować cel związany z długością przewodu jako równanie liniowe. Na szczęście możemy po prostu użyć odległości typu: „Manhattan” lub siatki do tego założenia (można też posiłkować się wartością bezwzględną w ramach optymalizacji liniowej w niektórych przypadkach przy pewnych transformacjach modelowania). Ostatecznym celem jest suma wszystkich odległości siatki między wszystkimi parami umieszczonych węzłów na dwuwymiarowym układzie FPGA, gdzie pary odpowiadają wszystkim krawędziom w grafie netlisty.
To podejście wydaje się dobre, ale w rzeczywistości nie jest ono skalowalne. Przyjmijmy, że mamy siatkę FPGA o rozmiarze 100 × 100 i listę 5000 węzłów, które mają zostać rozlokowane. Potrzebowalibyśmy zmiennej optymalizacji, która reprezentuje umieszczenie węzła na każdym miejscu. Spowodowałoby to problem optymalizacji o liczbie zmiennych równej 100 × 100 × 5000, co daje 50 milionów, a rzeczywiste układy FPGA i netlisty są znacznie większe. Dlatego wykorzystanie takiego solwera, z uwagi na czas działania, nie będzie zbyt dobrym pomysłem. Do tego stopnia, że jego zastosowanie do problemów o rzeczywistych rozmiarach nie ma sensu. Być może udałoby się przyspieszyć działanie tego algorytmu, rozważając nieliniowe formułowanie i relaksacje problemu, ale autor postanowił nie zajmować się tym tematem głębiej.
Symulowane wyżarzanie
W porównaniu z wcześniej opisanymi podejściami do rozmieszczenia, symulowane wyżarzanie (SA) podchodzi do tego mankamentu bardziej z góry, w sposób: „czarnej skrzynki”. W rzeczywistości nazwa: „symulowane wyżarzanie” to pewne nieporozumienie, ponieważ niepotrzebna jest naprawdę część: „wyżarzania”, aby działało to poprawnie.
W tradycyjnym kontekście optymalizacji omawiana operacja modeluje problem jako system z danym bieżącym rozwiązaniem. Następnie można przejść do innego i sprawdzić, czy jest lepsze. Jeśli nowe rozwiązanie spełnia to założenie, można je wybrać jako nowe bieżące. Termin: „przejście” użyty przez autora jest dość luźny. Prostą rzeczą do zrobienia jest losowe przechodzenie do innych rozwiązań i sprawdzanie, czy można uzyskać poprawę. Jednak bardziej inteligentnym pomysłem i rdzeniem symulowanego wyżarzania jest przypisanie prawdopodobieństw możliwym rozwiązaniom. Bliskie rozwiązania z małymi skokami mają większe szanse na wybranie niż skoki do dalekich. Na początku optymalizacji dalekie rozwiązania są definiowane jako bardziej prawdopodobne, co pozwala na skakanie po różnych miejscach. Jednak w miarę upływu czasu można sprawić, że skoki na daleką odległość będą stanowić coraz mniejszą ewentualność. A te, które podejmuje algorytm, staną się bardziej prawdopodobne do bliskich rozwiązań. To jest część: „wyżarzania” w symulowanym wyżarzaniu, której nazwa pochodzi od fizycznego procesu danego typu, czyli wielokrotnego ogrzewania i chłodzenia metalu.
W kontekście FPGA można modelować: „bieżące rozwiązanie” jako poprawną opcję umieszczenia wszystkich węzłów, a: „skok” jako dokonanie zmiany w aktualnym rozwiązaniu. Ta modyfikacja może polegać na wyborze spośród zestawu działań, takich jak zamiana miejscami lokalizacji dwóch losowych węzłów tego samego typu lub przeniesienie losowego węzła w inne prawidłowe. Obiekt nadal jest sumą długości przewodów wszystkich krawędzi w umieszczonym rozwiązaniu. Następnie można ocenić, czy zaakceptować, czy odrzucić dany ruch na podstawie tego, czy ten zmniejsza wartość naszej funkcji celu. Innymi słowy, jeśli ruch tworzy rozwiązanie o niższej wartości funkcji celu niż bieżące, akceptujemy go i kontynuujemy z nowymi. Jeśli buduje on rozwiązanie o wyższej wartości funkcji celu niż bieżące, odrzucamy go, zachowujemy aktualne i próbujemy innego posunięcia.
Część wyżarzania pojawia się przy określaniu, jak daleko przemieścić węzeł lub jak odległe są dwa węzły, które wybieramy do zamiany miejsc. Na początku można chcieć wykonywać posunięcia lub zamiany na duże odległości. Można chcieć zaakceptować pewien ich procent, który nie poprawia funkcji celu. Jednak w miarę upływu czasu chce się wykonywać mniejsze ruchy i ograniczać te, które nie optymalizują funkcji celu. To jest część: „wyżarzania” w kontekście rozmieszczenia FPGA. W tym przykładzie istnieje liniowy harmonogram wyżarzania z wyższą: „temperaturą” na początku i niższą na końcu. Temperatura w tym przypadku jest powiązana z prawdopodobieństwem zaakceptowania ruchu, który nie poprawia funkcji celu lub wykonywania tych robionych na bardzo duże odległości.
Jednak, jak się okazuje, technicznie niepotrzebna jest ta część algorytmu wyżarzania, aby działał algorytm rozmieszczenia w FPGA. Można po prostu losowo próbować różnych ruchów i akceptować lub odrzucać je w zależności od tego, czy poprawiają funkcję celu. To właśnie takie podejście zaimplementował autor w swoim uproszczonym rozwiązaniu.
VTR/VPR to popularne w kręgach akademickich narzędzie FPGA EDA (z syntezą, pakowaniem, rozmieszczeniem i trasowaniem w jednym pakiecie), które wykorzystuje symulowane wyżarzanie do rozlokowywania elementów w FPGA. Autorzy VPR mają na koncie wiele prac, które omawiają szczegóły wykorzystanej implementacji, takie jak opisy używanych działań czy sposób ustalania harmonogramów wyżarzania. Mają także bardziej złożony zestaw ruchów i sposobów ich wyboru między węzłami w określonej odległości od siebie. W ostatnich czasach eksplorowali oni także zastosowanie prostych technik uczenia się wzmocnionego. W szczególności po to, aby przeszkolić algorytm, jak wybierać, które ruchy wykonywać na każdym kroku.
Rozmieszczanie analityczne i elektrostatyczne
Analityczne rozmieszczanie jest eleganckim i praktycznym rozwiązaniem. Pochodzi od pomysłu zastąpienia zarówno funkcji celu długości przewodu, jak i ograniczeń niekolidującego rozmieszczenia równoważnymi ciągłymi formułami. Rozluźnia ono stałe ograniczenia natury problemu FPGA, gdzie lokalizacje i odległości mogą być wartościami ciągłymi. Dzięki temu możemy zdefiniować cel jako sumę odległości wszystkich węzłów, używając funkcji odległości, takiej jak odległość euklidesowa, lub nowych funkcji, takich jak odległość kwadratowa (przestrzeń L2). I sformułować ograniczenie niekolidującego rozmieszczenia jako kolejną funkcję celu, która modeluje gęstość, „nakładanie się” lub „bliskość” węzłów (istnieją różne sposoby modelowania tej składowej gęstości, ale to kolejna kwestia do zgłębienia). Ten cel nazywany jest karą za gęstość lub funkcją gęstości.
Aby rozwiązać problem rozmieszczenia, optymalizuje się nową funkcję celu, która jest równa funkcji celu długości przewodu plus pewnej funkcji gęstości z wagą lambda. Lambda kontroluje siłę funkcji gęstości, którą można kontrolować poprzez optymalizację, aby narzucić prawidłowe rozmieszczenie lub: „rozproszenie” węzłów. Ponieważ jest to problem ciągły, możemy użyć optymalizacji opartej na gradientach do jego rozwiązania. To również było badane przez długi czas i ma wiele gotowych do użycia solwerów. Współcześnie sporo specjalistów uznaje to podejście za: „analityczny algorytm rozmieszczania”. Jednak można pójść o krok dalej i uczynić go: „elektrostatycznym”. Modeluje on cały system jako elektrostatyczny, gdzie węzły są równoważne naładowanym dodatnio ładunkom, a funkcja gęstości jest równoważna potencjałowi elektrycznemu. Następnie można naprowadzić cząstki na miejsce, które minimalizuje potencjał elektryczny, używając samego pola elektrycznego jako gradientu, który: „popycha” węzły w pożądanym kierunku, aby się rozproszyć i ustabilizować w ostatecznym miejscu. Z tym podejściem składniki algorytmiczne są wplecione w sam algorytm. Elektrostatyczny algorytm rozmieszczania można użyć do uzyskania wystarczająco dobrych ciągłych rozwiązań, ale z pewnym nakładaniem się lub niepełnym dopasowaniem do dokładnych lokalizacji siatki FPGA. Następnie trzeba użyć narzędzia do korekcji tych niepoprawnych elementów, aby: „przytwierdzić” węzły do miejsc na siatce FPGA.
Autor nie zagłębiał się w więcej szczegółów, ale istnieje wiele prac dotyczących zarówno analitycznego, jak i elektrostatycznego rozmieszczania, a kolejne są nadal publikowane. Według jego najlepszego zrozumienia rozmieszczanie elektrostatyczne jest aktualnie uznawane za optymalne rozwiązanie, co najmniej w dziedzinie projektowania układów ASIC i FPGA.
Implementacja
Specyfikacja
Autor przyjął kilka uproszczeń problemu, aby łatwiej mu było stworzyć samodzielnie taki demonstracyjny algorytm:
* System uznaje tylko cztery typy elementów: CLB, BRAM, DSP oraz IO.
* Graf netlisty zawiera węzły i krawędzie: jeden z czterech rodzajów węzłów i połączenie między dwoma węzłami.
* Mapa rozmieszczenia w FPGA to dwuwymiarowa sieć, w której jedno miejsce może zajmować tylko jeden blok. Typ tego bloku jest ściśle określony i nie można umieścić tam innego jego rodzaju. Istnieją też bloki EMPTY, które należy pozostawić pustymi.
* Symulowany algorytm wyżarzania jest uproszczony i nie obejmuje samego procesu. Pozwala na trzy rodzaje ruchów: zamiana węzłów, przeniesienie na losowe miejsce tego samego rodzaju z ewentualnym uwzględnieniem centroidu wszystkich węzłów w grafie netlisty.
* Funkcją celu jest suma długości przewodów wszystkich krawędzi w grafie netlisty. Odległość jest liczona zgodnie z metryką Manhattan pomiędzy miejscami, na których są umieszczone.
* Ruch jest akceptowany, jeśli poprawia wartość funkcji celu. W każdym kroku algorytm testuje n_neighbors różnych losowych ruchów i wybiera najlepszy.
* Algorytm wymaga wprowadzenia losowego początkowego rozmieszczenia elementów.
Netlista
Autor na wstępie planował modelowanie netlisty jako skierowanego hipergrafu, ale ostatecznie zrezygnował z tego pomysłu z dwóch głównych powodów. Po pierwsze, aby zrobić to porządnie, musiałby radzić sobie z dodatkową złożonością węzłów z portami i krawędziami między węzłami, ale tylko do określonych portów. W cyfrowych obwodach, komponent taki jak 4-wejściowy LUT, posiada 5 portów, przez które linie mogą wchodzić i wychodzić. Chociaż można by było modelować go jako węzeł, to jednak krawędź łączyłaby się z portem na nim, a nie z całym. Decyzja, jak to odpowiednio zamodelować, może być dość złożona, a autor nie chciał zbytnio komplikować algorytmu. Po drugie, nie istniały biblioteki obsługujące skierowane hipergrafy lub przynajmniej nie były wystarczająco dobrze udokumentowane. Tak, aby odszukać skierowane wersje lub brakujące funkcje, które autor oczekiwałby znaleźć. Mimo przeglądania bibliotek, takich jak hipergraf i mhgl, nie mógł uzyskać wsparcia.
Powodem, dla którego autor chciał obsługiwać skierowane hipergrafy, było ewentualne modelowanie kierunku sygnału w przyszłości. Chciał, aby na przykład wyjściowy pin 4-wejściowego LUT był źródłem, a piny wyjściowe były źródłem w hiperkrawędzi. Mimo że nie był on pewien, czy to ma znaczenie dla problemu rozmieszczenia, chciał mieć to na uwadze, jeśli rozszerzy swój prototyp, aby obejmować również router. Zdecydował się w związku z tym na modelowanie netlisty jako grafu skierowanego z abstrakcyjnymi węzłami, obejmującymi 4 ich rodzaje zdefiniowane w jego specyfikacjach.
Autor korzystał z biblioteki petagraph do tworzenia samego grafu. To było miejsce, gdzie po raz pierwszy napotkał system typów w Rust działający w przyjemny sposób, dzięki tzw. generykom. Był w stanie przekazać parametr typu węzła do struktury Petagraph DiGraph. Co automatycznie narzucało ten rodzaj, a edytor uzupełniał kod do tego typu podczas dostępu do węzłów w grafie. Mimo że autor był przyzwyczajony do Pythona, zobaczenie tego działającego w Rust było dla niego naprawdę fajne, zwłaszcza biorąc pod uwagę fakt, że używa Mypy i wskazówek do podpowiadania typów w Pythonie. Dodatkowo dodał on kilka prostszych funkcji pomocniczych do uzyskiwania podsumowania węzłów.
Autor dodatkowo skorzystał z biblioteki rustworkx-core do generowania losowego grafu netlist w celu późniejszego przetestowania rozmieszczenia. Funkcja build_simple_netlist tworzy losowy graf Erdősa-Rényiego. Można parametryzować ten rodzaj liczbą węzłów i prawdopodobieństwem krawędzi między dwoma węzłami. Takie podejście nie odzwierciedla dokładnie właściwości rzeczywistych grafów netlist, ale jest dostateczne do przetestowania rozmieszczenia. W rzeczywistych grafach netlist mogą istnieć silnie połączone klastry węzłów, reprezentujące różne moduły sprzętowe w projekcie. Moduły te są ze sobą połączone za pomocą magistrali przewodów i wspólnie tworzą większą strukturę. Jednak nawet ta hierarchiczna struktura grafu: „modułów” na wysokim poziomie jest modyfikowana i optymalizowana w nowy graf po procesie syntezy i mapowaniu technologicznym. Niektóre nieistotne części kodu zostały pominięte w tym miejscu.
Algorytm
Autor stworzył układ FPGA jako typ FPGALayout, który obejmuje hashmapę typów FPGALayoutCoordinate do FPGALayoutType. Dzięki temu można odpytywać lokalizacje węzłów w układzie FPGA za pomocą ich współrzędnych. Okazało się to bardziej efektywne niż użycie ogromnej tablicy dwuwymiarowej lub wektora wektorów. Dodatkowo autor przechowuje szerokość i wysokość układu FPGA, co potrzebne jest do pracy funkcji pomocniczych, wykorzystywanych m.in. do odpytywania dowolnego punktu w układzie, z dodatkową logiką zwracającą FPGALayoutType::EMPTY, jeśli współrzędna nie znajduje się w hashmapie, lub None, jeśli współrzędna jest poza granicami.
W projekcie występują także funkcje pomocnicze do ustawiania różnych wzorców typów FPGALayoutType w układzie, takie jak config_corners, config_border i config_repeat. Ułatwiają one ustawianie wszystkich zewnętrznych krawędzi układu FPGA na FPGALayoutType::IO lub konfigurację powtarzającego się wzorca kolumn FPGALayoutType::BRAM w prosty sposób.
Stworzona została również prosta funkcja pomocnicza do generowania nieskomplikowanego, testowego układu FPGA z IO na zewnętrznych krawędziach (z wyjątkiem narożników), CLB wypełnionymi w środku i BRAM w środku co 10 kolumn.
Rozwiązanie rozmieszczania
Autor zdecydował się zamodelować rozwiązanie jako typ PlacementSolution, który zawiera odniesienie do wykresu listy sieci, odniesienie do układu FPGA i mapę łączącą NetlistNode z FPGALayoutCooperative. Rzeczywisty rdzeń rozwiązania leży w mapie skrótów. Jako że informuje ona, gdzie w układzie FPGA znajduje się każdy węzeł na liście sieci.
Zamiast pokazywać pełną implementację dla tego typu, autor zaprezentował jej wybrane fragmenty, które są istotne dla algorytmu. Mamy tu więc na wstępie akcje umieszczania i funkcje akcji.
Najprostsza akcja to przeniesienie węzła do losowego, wolnego miejsca:
Kolejna akcja to zamiana dwóch węzłów tego samego typu:
Ostatnia to przeniesienie węzła do położenia, które znajduje się bliżej centroidy wszystkich węzłów netlisty. Tutaj sytuacja jest już bardziej skomplikowana. W implementacji procesu rozmieszczania konieczne jest obliczenie centroidu, a następnie znalezienie najbliższego prawidłowego miejsca do niego. Ruch ten jest również kosztowny, co wpływa na spowolnienie działania programu. Niemniej może on przyspieszyć proces zbliżania algorytmu do lepszego rozwiązania. To dlatego, że przenoszenie węzłów do centroidu szybko i skokowo zmniejsza wartość funkcji celu, przynajmniej do pewnego momentu w trakcie optymalizacji.
Te akcje mogą być wywoływane za pomocą kolejnej funkcji pomocniczej:
Następnym istotnym aspektem rozmieszczania jest funkcja celu. Wspomniano o użyciu funkcji odległości do określania długości przewodów i sumowania wszystkich krawędzi w grafie netlisty.
Tradycyjnie termin: „siatka” odnosi się do hiperkrawędzi w hipergrafie. Abstrakcyjne: „połączenie” od pinu wyjściowego jednego węzła do wszystkich wejściowych innych węzłów może być nazwane siatką. Pojęcie to wynika z abstrakcji. Fizycznie można by narysować jedną giętą i rozgałęzioną ścieżkę w układzie scalonym, aby połączyć wszystkie piny, co będzie pełnić funkcję jednej abstrakcyjnej: „siatki”.
Poszczególne połączenia od pinu wyjściowego do wejściowego są rozumiane jako: „krawędź”. To bezpośrednio odnosi się do krawędzi w grafie, gdy rozmawiamy o abstrakcyjnych grafach w matematyce. Siatkę można przekształcić w zestaw krawędzi. Wystarczy wyliczyć wszystkie połączenia od źródła do ujścia w hiperkrawędzi siatki.
Generalnie pojedyncza: „siatka” zawiera wiele: „krawędzi”. A technicznie w przypadku rozmieszczenia ukierunkowanie obydwu nie ma znaczenia (przynajmniej w prostym problemie rozlokowywania, który został przedstawiony).
Niektóre funkcje celu są ukierunkowane na poziomie siatki. Jedną z popularnych funkcji celu, na poziomie siatki, jest Połowa Długości Obwodu Przewodów (HPWL), gdzie HPWL wynosi połowę długości obwodu otaczającego prostokątny obszar ograniczający siatkę:
$$HPWL_e = max_{i \epsilon n}(x_i) - min_{i \epsilon n}(x_i) + max_{i \epsilon n}(y_i) - min_{i \epsilon n}(y_i) \qquad (1) $$
gdzie n to krawędź, i to węzeł, a xi i yi to współrzędne x i y węzła i. Istnieje wiele proponowanych sposobów na rozluźnienie funkcji min i max, aby uczynić ją ciągłą, różniczkowalną i/lub pewną wersję wypukłą, a także inne związane cele na poziomie siatki.
Zakładając, że wszystkie siatki są po prostu dzielone na krawędzie, istnieje wiele celów na poziomie siatki, z których najprostszą klasą są funkcje odległości w przestrzeni euklidesowej. Odległość liczona jest zgodnie z metryką Manhattan, znaną również jako: „liniowy” model długości przewodu, ma na celu modelowanie optymalnego fizycznego prostokątnego układu przewodów w chipie. Jest to sformułowane jako:
$$d_{ij} = \left | x_k - x_j \right | \qquad (2)$$
a funkcja celu jako:
$$\sum_{e \epsilon E} d_e = \sum_{e \epsilon E} \left | x_k - x_j \right | + \left | y_k - y_j \right | \qquad (3) $$
Jednakże bardziej popularną miarą jest odległość kwadratowa lub „kwadratowy” model długości przewodu. Jest to sformułowane jako:
$$d_{ij} = (x_i - x_j)^2 /qquad (4) $$
a funkcja celu jako:
$$\sum_{e \epsilon E} d_e = \sum_{e \epsilon E} (x_i - x_j)^2 + (y_i - y_j)^2 \qquad (5) $$
W symulowanym algorytmie autor używa modelu liniowej długości przewodu w funkcji celu, przy czym wszystko jest modelowane jako zwykłe krawędzie, a nie siatki. Nazwa cost_bb jest nieco myląca, ponieważ nie są obliczane żadne wartości związane z prostokątną obwiednią siatki. Autor jedynie sumuje odległość zgodnie z wybraną metryką wszystkich krawędzi w grafie netlisty.
W implementacji dodano także dwie niezależne funkcje pomocnicze do generowania początkowych rozwiązań rozmieszczenia — podejście: losowe (gen_random_placement) i zachłanne (gen_greedy_placement). To ostatnie lokuje węzeł w pierwszym dostępnym miejscu w lewym górnym rogu układu FPGA. Pozwala to na umieszczenie wszystkich węzłów obok siebie w początkowym rozwiązaniu. Jednak prawdopodobnie sprawia to, że trudniej jest je zoptymalizować bardziej zwartym sposobem. Przynajmniej w porównaniu z początkowym rozwiązaniem, w którym węzły są ulokowane średnio daleko od siebie. Jednak są łatwiejsze do zoptymalizowania.
W implementacji rozwiązania rozmieszczenia znajdują się również dodatkowe funkcje, takie jak render_svg, służąca do generowania wizualizacji prezentowanych w tym wpisie, oraz typ Renderer z funkcją render_to_video, która korzysta z narzędzi imagemagick i ffmpeg do generowania filmów i plików GIF z procesu optymalizacji.
Algorytm rozmieszczania
Ostatnim elementem jest właściwy rozmieszczacz, który okazuje się zaskakująco prosty i zwarty jako pojedyncza funkcja. W tej implementacji badane są równolegle wielokrotne ruchy w każdym kroku, a następnie wybiera się najlepszy podjęty w danym etapie. Wykorzystywana jest także funkcja par_iter z biblioteki rayon do równoległego przetwarzania eksploracji ruchów w każdym kroku. To proste rozwiązanie pozwala przyspieszyć proces optymalizacji. Jednak może wymagać regulacji, ponieważ równoległa eksploracja ruchów może wprowadzić pewne nakłady związane z równoległym przetwarzaniem.
Idealnie byłoby znaleźć niebanalny kompromis między liczbą wszystkich posunięć podjętych a liczbą równoległych działań badanych w każdym etapie. Więcej działań na krok skutkuje lepszą okazją na znalezienie bardziej miarodajnego ruchu w danej fazie. Acz więcej kroków ogółem oznacza większą szansę na osiągnięcie stabilnego optymalnego rozwiązania, wszystko to przy koszcie całkowitego czasu działania. Być może w różnych momentach procesu optymalizacji chciałoby się dostosować liczbę równoległych działań badanych w każdym kroku. To coś, co autor chce zweryfikować w przyszłości i bezpośrednio wiąże się z aspektem: „wyżarzania” w tradycyjnym procesie danego typu. Zmiana wartości liczby działań badanych w każdym kroku nazywa się budowaniem harmonogramu wyżarzania. Ma to również pewne podobieństwo do wybierania harmonogramów współczynnika uczenia w głębokim uczeniu.
Rezultaty i wizualizacja
Autor do testów wykorzystał następujące dane:
* Netlistę zawierającą 300 węzłów: 10 IO, 100 BRAM i 190 CLB.
* FPGA o wielkości 64 × 64 bloków z miejscem dla IO przy krawędzi, CLB w środku i miejscem na moduły BRAM w kolumnach, co 10 kolumn.
* Algorytm optymalizacji rozmieszczenia uruchamiany był na 1000 kroków.
* Algorytm inicjowano z różnymi ustawieniami n_neighbors = [1, 4, 8, 16, 32, 64, 128, 256]; każda próba wykorzystywała to samo wstępne rozmieszczenie elementów.
Algorytm zadziałał poprawnie. Na ilustracji poniżej pokazano układ przed i po optymalizacji dla n_neighbors = 32.
Na filmie poniżej umieszczono animację, pokazującą działanie poszczególnych kroków w sekwencji:
Najbardziej zauważalnym aspektem tego algorytmu jest fakt, że wydaje się on mocno polegać na ruchach skierowanych, aby przenosić węzły do centroidu grafu netlisty. Prawdopodobnie zaczynając od losowego rozwiązania początkowego, ruchy te stają się najbardziej skuteczne w obniżaniu wartości funkcji celu. Z biegiem czasu, w miarę umieszczania coraz więcej węzłów w centrum, wpływa to na to, że ruchy skierowane przemieszczają je w miejsca, gdzie wszystkie znajdują się w środku. Jednak ruchy: losowe i zamiany wciąż są wartościowe dla algorytmu, aby badać optymalizację rozmieszczenia wejść/wyjść, ponieważ są one ograniczone do zewnętrznych krawędzi układu FPGA, a także dla bloków BRAM, jako że mają one duże skoki między kolumnami.
Dodatkowo, eksplorowano, jak liczba równoległych sąsiadów badanych w każdym kroku wpływa na proces optymalizacji. Wyniki przedstawiono poniżej na wykresie stworzonym przy użyciu gnuplot.
W zgodny z intuicją sposób, uruchomienie algorytmu z największą liczbą równoległych sąsiadów, którą można zbadać jednocześnie, nie jest najlepsze dla optymalizacji funkcji celu rozmieszczenia na przestrzeni całego procesu. Jednakże wydaje się, że jeśli chcemy przeszukiwać to z 4 lub więcej równoległymi sąsiadami, ponieważ przy 1 lub 2 nie jest to tak skuteczne.
Wygląda również na to, jak wskazuje autor, że może występować zjawisko kurczącego się zysku ze zmian i malejąca wartość funkcji celu zbiega do tej wartości ostatecznej w miarę zwiększania liczby równoległych sąsiadów do przeszukania. Jednak nie jest to jeszcze w pełni jasne ani nie ustalono, jaka jest optymalna wartość sąsiadów dla równoległego przeszukiwania w każdym kroku. Ten wynik jest również bardzo specyficzny dla tej netlisty i symulowanego układu FPGA, które zostały wykorzystane do przetestowania algorytmu. Potrzebne są bardziej zróżnicowane i kompleksowe eksperymenty, aby wyciągnąć bardziej ogólne wnioski, wskazuje autor.
Kod źródłowy i odtwarzalność
Cały kod źródłowy tego projektu można znaleźć tutaj. Pozwala to na zgłębienie szczegółów implementacji, które pominięto w tym poście, a także na eksperymentowanie z kodem i wypróbowywanie różnych pomysłów. Wygenerowane pliki danych (.CSV) i wizualizacje (.PNG, .MP4, .GIF) są również dostępne w repozytorium autora.
Podsumowanie
Po zakończeniu projektu, autor tego: „zabawkowego” algorytmu do rozmieszczania ma pewne refleksje na temat algorytmów EDA (Automatyzacji Procesu Projektowania) i badań w tej dziedzinie, które uznaje za istotne do wyrażenia.
Uważa on, że pomysły prezentowane w artykułach naukowych i konferencyjnych stają się znacznie bardziej zrozumiałe, gdy udaje się wyodrębnić ich główne idee i zacząć od podstaw. Zauważa jednak, że wiele opublikowanych tekstów technicznych dotyczących algorytmów EDA nie należy do przystępnych lub są zbyt zdawkowe. Dostrzega on, że podręczniki i wysokiej jakości materiały do nauki są przydatne do pogłębiania wiedzy poza powierzchowny poziom treści. Dodatkowo, uważa, że dostępne i wysokojakościowe (niekoniecznie: „badawcze”) kody źródłowe zaawansowanych algorytmów EDA są również trudne do znalezienia.
Po wykorzystaniu Rusta do zastosowań w EDA, autor ma wyższe oczekiwania i standardy dla oprogramowania EDA. Uznaje, że istnieją znaczne luki w wydajności nowoczesnych narzędzi i algorytmów EDA, które, dzięki większemu nakładowi na inżynierię oprogramowania i algorytmy, można by pokonać. Po zastosowaniu Rusta sądzi, że jest to jeden z najlepszych kandydatów do tego rodzaju oprogramowania, które opiera się na strukturach danych i algorytmach, przy wysokich standardach poprawności i niezawodności.
Marzeniem autora jest życie w idealnym świecie, w którym, aby w pełni syntetyzować, rozmieścić i trasować duży nowoczesny projekt dla współczesnego układu FPGA wystarczy mniej niż minuta. Po zakończeniu swojej pracy widzi oznaki nadziei na taką przyszłość, jednakże nie wskazuje, kiedy może to nastąpić.
Źródło: https://stefanabikaram.com/writing/fpga-sa-placer/
W ramach swojej pracy doktorskiej autor zajmuje się między innymi algorytmem rozmieszczania i trasowania w układach FPGA. Do tego celu wykorzystuje algorytmy głębokiego uczenia, które wspierają go w modelowaniu i rozwiązywaniu problemów w ww. zakresie. W tym procesie autor zgłębiał kod źródłowy narzędzia VPR oraz przeglądał najnowsze prace na temat elektrostatycznego rozmieszczania i trasowania, takie jak DreamPlace czy klasyk odnoszący się do routerów PathFinder. Analizując opublikowane badania, twórca zbudował swoje zrozumienie szczegółów technicznych i historii doświadczeń w tej dziedzinie. Rozważając możliwość nauczenia się, przy okazji, języka programowania Rust, postanowił połączyć to z implementacją tych algorytmów dla FPGA. Jest to szczególnie istotne, gdyż struktury danych i wydajność obliczeniowa są kluczowe dla realnych narzędzi do rozmieszczania i trasowania w FPGA, a Rust oferuje w tym zakresie bardzo dużo. Chcąc uniknąć błędów związanych z pamięcią czy typami, autor wybrał Rust uznawany za język dobrze sprawdzający się w tych obszarach. Chociaż potrzeba nauki Rusta z perspektywy pracy może nie być tak wartościowa, jak poznanie dla samego poznania, twórca projektu zdecydował się na to podwójne wyzwanie.
W każdym razie postanowił uczyć się Rusta, pisząc jednocześnie prosty symulator rozmieszczania elementów w FPGA oparty na symulowanym wyżarzaniu. Jeśli znany jest Wam ten wątek, to możecie przejść dalej, do części artykułu poświęconej implementacji, wynikom i do kodu źródłowego. Pozostali mogą przeczytać o podstawach w tym zakresie.
Czym jest algorytm rozmieszczania dla FPGA
Rozmieszczanie w FPGA jest bardzo łatwe do sformułowania, gdy można być cierpliwym i buduje się uproszczoną wersję problemu.
Mamy graf netlisty (listy sieci połączeń), który reprezentuje obwód, gdzie węzłami są różne jego elementy, a krawędzie to połączenia. Jest też układ FPGA — dwuwymiarowa siatka miejsc, gdzie można umieścić węzły. Każde miejsce może pomieścić tylko jeden element obwodu, a także tylko jeden jego rodzaj. W prototypowym modelu są tylko 4 ich typy: CLB, BRAM, DSP oraz IO. Każdy węzeł w grafie należy do jednego z nich, a każde miejsce na układzie FPGA może pomieścić tylko jeden z tych bloków. Dodatkowo niektóre miejsca w układzie FPGA są przeznaczone wyłącznie dla np. bloków wejść/wyjść (IO), gdzie można umieścić węzły IO z grafu netlisty.
Zazwyczaj wiemy, że układ FPGA będzie miał więcej miejsc, niż jest to nam potrzebne pod wszystkie węzły grafu. Gdyby tak nie było, nie można byłoby ich pomieścić w układzie FPGA. Moglibyśmy się na tym po prostu zatrzymać, informując użytkownika, że układ FPGA jest za mały lub ich netlista jest za duża.
Celem działania przedmiotowego algorytmu rozmieszczania jest odwzorowanie każdego węzła z netlisty na miejsce w układzie FPGA. Gdyby to było wszystko, można by zwyczajnie wymieniać miejsca, gdzie węzeł może zostać umieszczony i lokować go na pierwszym dostępnym. Następnie można to zrobić dla wszystkich węzłów, aż się skończą i gotowe.
W rzeczywistości po rozmieszczeniu trzeba połączyć węzły zgodnie z ich krawędziami w grafie netlisty. Router będzie używał wygenerowanego rozwiązania wyjściowego, aby następnie prowadzić sygnały przy użyciu zasobów routingu w FPGA między umieszczonymi węzłami na układzie programowalnym. Jeśli losowo ulokujemy dwa węzły daleko od siebie, które są połączone w grafie netlisty, będziemy musieli poprowadzić między nimi długi: „przewód”. To nie jest dobre z kilku powodów, w tym z uwagi na zależności czasowe i obciążenia prądowe. Z tego powodu chcemy dokonać tego działania, minimalizując: „odległości” umieszczonych węzłów, które są ze sobą połączone. Ten cel algorytmu sprawia, że rozlokowywanie bloków w układzie staje się problemem nietrywialnym.
Jak ugryźć kwestię rozmieszczania elementów w FPGA
Rozwiązanie liniowej optymalizacji mieszanej
Dane zbioru węzłów, które trzeba umieścić, miejsca, w których można to zrobić, ograniczenia dla mapowania 1-1 oraz te w oparciu o typ węzła, umożliwiają dosyć klarowne sformułowanie tego zagadnienia jako problemu mieszanej optymalizacji liniowej, który jest badany od wielu lat. Dostępne są więc solwery gotowe do użycia. Jedyną rzeczą, którą trzeba zrobić, to sformułować cel związany z długością przewodu jako równanie liniowe. Na szczęście możemy po prostu użyć odległości typu: „Manhattan” lub siatki do tego założenia (można też posiłkować się wartością bezwzględną w ramach optymalizacji liniowej w niektórych przypadkach przy pewnych transformacjach modelowania). Ostatecznym celem jest suma wszystkich odległości siatki między wszystkimi parami umieszczonych węzłów na dwuwymiarowym układzie FPGA, gdzie pary odpowiadają wszystkim krawędziom w grafie netlisty.
To podejście wydaje się dobre, ale w rzeczywistości nie jest ono skalowalne. Przyjmijmy, że mamy siatkę FPGA o rozmiarze 100 × 100 i listę 5000 węzłów, które mają zostać rozlokowane. Potrzebowalibyśmy zmiennej optymalizacji, która reprezentuje umieszczenie węzła na każdym miejscu. Spowodowałoby to problem optymalizacji o liczbie zmiennych równej 100 × 100 × 5000, co daje 50 milionów, a rzeczywiste układy FPGA i netlisty są znacznie większe. Dlatego wykorzystanie takiego solwera, z uwagi na czas działania, nie będzie zbyt dobrym pomysłem. Do tego stopnia, że jego zastosowanie do problemów o rzeczywistych rozmiarach nie ma sensu. Być może udałoby się przyspieszyć działanie tego algorytmu, rozważając nieliniowe formułowanie i relaksacje problemu, ale autor postanowił nie zajmować się tym tematem głębiej.
Symulowane wyżarzanie
W porównaniu z wcześniej opisanymi podejściami do rozmieszczenia, symulowane wyżarzanie (SA) podchodzi do tego mankamentu bardziej z góry, w sposób: „czarnej skrzynki”. W rzeczywistości nazwa: „symulowane wyżarzanie” to pewne nieporozumienie, ponieważ niepotrzebna jest naprawdę część: „wyżarzania”, aby działało to poprawnie.
W tradycyjnym kontekście optymalizacji omawiana operacja modeluje problem jako system z danym bieżącym rozwiązaniem. Następnie można przejść do innego i sprawdzić, czy jest lepsze. Jeśli nowe rozwiązanie spełnia to założenie, można je wybrać jako nowe bieżące. Termin: „przejście” użyty przez autora jest dość luźny. Prostą rzeczą do zrobienia jest losowe przechodzenie do innych rozwiązań i sprawdzanie, czy można uzyskać poprawę. Jednak bardziej inteligentnym pomysłem i rdzeniem symulowanego wyżarzania jest przypisanie prawdopodobieństw możliwym rozwiązaniom. Bliskie rozwiązania z małymi skokami mają większe szanse na wybranie niż skoki do dalekich. Na początku optymalizacji dalekie rozwiązania są definiowane jako bardziej prawdopodobne, co pozwala na skakanie po różnych miejscach. Jednak w miarę upływu czasu można sprawić, że skoki na daleką odległość będą stanowić coraz mniejszą ewentualność. A te, które podejmuje algorytm, staną się bardziej prawdopodobne do bliskich rozwiązań. To jest część: „wyżarzania” w symulowanym wyżarzaniu, której nazwa pochodzi od fizycznego procesu danego typu, czyli wielokrotnego ogrzewania i chłodzenia metalu.
W kontekście FPGA można modelować: „bieżące rozwiązanie” jako poprawną opcję umieszczenia wszystkich węzłów, a: „skok” jako dokonanie zmiany w aktualnym rozwiązaniu. Ta modyfikacja może polegać na wyborze spośród zestawu działań, takich jak zamiana miejscami lokalizacji dwóch losowych węzłów tego samego typu lub przeniesienie losowego węzła w inne prawidłowe. Obiekt nadal jest sumą długości przewodów wszystkich krawędzi w umieszczonym rozwiązaniu. Następnie można ocenić, czy zaakceptować, czy odrzucić dany ruch na podstawie tego, czy ten zmniejsza wartość naszej funkcji celu. Innymi słowy, jeśli ruch tworzy rozwiązanie o niższej wartości funkcji celu niż bieżące, akceptujemy go i kontynuujemy z nowymi. Jeśli buduje on rozwiązanie o wyższej wartości funkcji celu niż bieżące, odrzucamy go, zachowujemy aktualne i próbujemy innego posunięcia.
Część wyżarzania pojawia się przy określaniu, jak daleko przemieścić węzeł lub jak odległe są dwa węzły, które wybieramy do zamiany miejsc. Na początku można chcieć wykonywać posunięcia lub zamiany na duże odległości. Można chcieć zaakceptować pewien ich procent, który nie poprawia funkcji celu. Jednak w miarę upływu czasu chce się wykonywać mniejsze ruchy i ograniczać te, które nie optymalizują funkcji celu. To jest część: „wyżarzania” w kontekście rozmieszczenia FPGA. W tym przykładzie istnieje liniowy harmonogram wyżarzania z wyższą: „temperaturą” na początku i niższą na końcu. Temperatura w tym przypadku jest powiązana z prawdopodobieństwem zaakceptowania ruchu, który nie poprawia funkcji celu lub wykonywania tych robionych na bardzo duże odległości.
Jednak, jak się okazuje, technicznie niepotrzebna jest ta część algorytmu wyżarzania, aby działał algorytm rozmieszczenia w FPGA. Można po prostu losowo próbować różnych ruchów i akceptować lub odrzucać je w zależności od tego, czy poprawiają funkcję celu. To właśnie takie podejście zaimplementował autor w swoim uproszczonym rozwiązaniu.
VTR/VPR to popularne w kręgach akademickich narzędzie FPGA EDA (z syntezą, pakowaniem, rozmieszczeniem i trasowaniem w jednym pakiecie), które wykorzystuje symulowane wyżarzanie do rozlokowywania elementów w FPGA. Autorzy VPR mają na koncie wiele prac, które omawiają szczegóły wykorzystanej implementacji, takie jak opisy używanych działań czy sposób ustalania harmonogramów wyżarzania. Mają także bardziej złożony zestaw ruchów i sposobów ich wyboru między węzłami w określonej odległości od siebie. W ostatnich czasach eksplorowali oni także zastosowanie prostych technik uczenia się wzmocnionego. W szczególności po to, aby przeszkolić algorytm, jak wybierać, które ruchy wykonywać na każdym kroku.
Rozmieszczanie analityczne i elektrostatyczne
Analityczne rozmieszczanie jest eleganckim i praktycznym rozwiązaniem. Pochodzi od pomysłu zastąpienia zarówno funkcji celu długości przewodu, jak i ograniczeń niekolidującego rozmieszczenia równoważnymi ciągłymi formułami. Rozluźnia ono stałe ograniczenia natury problemu FPGA, gdzie lokalizacje i odległości mogą być wartościami ciągłymi. Dzięki temu możemy zdefiniować cel jako sumę odległości wszystkich węzłów, używając funkcji odległości, takiej jak odległość euklidesowa, lub nowych funkcji, takich jak odległość kwadratowa (przestrzeń L2). I sformułować ograniczenie niekolidującego rozmieszczenia jako kolejną funkcję celu, która modeluje gęstość, „nakładanie się” lub „bliskość” węzłów (istnieją różne sposoby modelowania tej składowej gęstości, ale to kolejna kwestia do zgłębienia). Ten cel nazywany jest karą za gęstość lub funkcją gęstości.
Aby rozwiązać problem rozmieszczenia, optymalizuje się nową funkcję celu, która jest równa funkcji celu długości przewodu plus pewnej funkcji gęstości z wagą lambda. Lambda kontroluje siłę funkcji gęstości, którą można kontrolować poprzez optymalizację, aby narzucić prawidłowe rozmieszczenie lub: „rozproszenie” węzłów. Ponieważ jest to problem ciągły, możemy użyć optymalizacji opartej na gradientach do jego rozwiązania. To również było badane przez długi czas i ma wiele gotowych do użycia solwerów. Współcześnie sporo specjalistów uznaje to podejście za: „analityczny algorytm rozmieszczania”. Jednak można pójść o krok dalej i uczynić go: „elektrostatycznym”. Modeluje on cały system jako elektrostatyczny, gdzie węzły są równoważne naładowanym dodatnio ładunkom, a funkcja gęstości jest równoważna potencjałowi elektrycznemu. Następnie można naprowadzić cząstki na miejsce, które minimalizuje potencjał elektryczny, używając samego pola elektrycznego jako gradientu, który: „popycha” węzły w pożądanym kierunku, aby się rozproszyć i ustabilizować w ostatecznym miejscu. Z tym podejściem składniki algorytmiczne są wplecione w sam algorytm. Elektrostatyczny algorytm rozmieszczania można użyć do uzyskania wystarczająco dobrych ciągłych rozwiązań, ale z pewnym nakładaniem się lub niepełnym dopasowaniem do dokładnych lokalizacji siatki FPGA. Następnie trzeba użyć narzędzia do korekcji tych niepoprawnych elementów, aby: „przytwierdzić” węzły do miejsc na siatce FPGA.
Autor nie zagłębiał się w więcej szczegółów, ale istnieje wiele prac dotyczących zarówno analitycznego, jak i elektrostatycznego rozmieszczania, a kolejne są nadal publikowane. Według jego najlepszego zrozumienia rozmieszczanie elektrostatyczne jest aktualnie uznawane za optymalne rozwiązanie, co najmniej w dziedzinie projektowania układów ASIC i FPGA.
Implementacja
Specyfikacja
Autor przyjął kilka uproszczeń problemu, aby łatwiej mu było stworzyć samodzielnie taki demonstracyjny algorytm:
* System uznaje tylko cztery typy elementów: CLB, BRAM, DSP oraz IO.
* Graf netlisty zawiera węzły i krawędzie: jeden z czterech rodzajów węzłów i połączenie między dwoma węzłami.
* Mapa rozmieszczenia w FPGA to dwuwymiarowa sieć, w której jedno miejsce może zajmować tylko jeden blok. Typ tego bloku jest ściśle określony i nie można umieścić tam innego jego rodzaju. Istnieją też bloki EMPTY, które należy pozostawić pustymi.
* Symulowany algorytm wyżarzania jest uproszczony i nie obejmuje samego procesu. Pozwala na trzy rodzaje ruchów: zamiana węzłów, przeniesienie na losowe miejsce tego samego rodzaju z ewentualnym uwzględnieniem centroidu wszystkich węzłów w grafie netlisty.
* Funkcją celu jest suma długości przewodów wszystkich krawędzi w grafie netlisty. Odległość jest liczona zgodnie z metryką Manhattan pomiędzy miejscami, na których są umieszczone.
* Ruch jest akceptowany, jeśli poprawia wartość funkcji celu. W każdym kroku algorytm testuje n_neighbors różnych losowych ruchów i wybiera najlepszy.
* Algorytm wymaga wprowadzenia losowego początkowego rozmieszczenia elementów.
Netlista
Autor na wstępie planował modelowanie netlisty jako skierowanego hipergrafu, ale ostatecznie zrezygnował z tego pomysłu z dwóch głównych powodów. Po pierwsze, aby zrobić to porządnie, musiałby radzić sobie z dodatkową złożonością węzłów z portami i krawędziami między węzłami, ale tylko do określonych portów. W cyfrowych obwodach, komponent taki jak 4-wejściowy LUT, posiada 5 portów, przez które linie mogą wchodzić i wychodzić. Chociaż można by było modelować go jako węzeł, to jednak krawędź łączyłaby się z portem na nim, a nie z całym. Decyzja, jak to odpowiednio zamodelować, może być dość złożona, a autor nie chciał zbytnio komplikować algorytmu. Po drugie, nie istniały biblioteki obsługujące skierowane hipergrafy lub przynajmniej nie były wystarczająco dobrze udokumentowane. Tak, aby odszukać skierowane wersje lub brakujące funkcje, które autor oczekiwałby znaleźć. Mimo przeglądania bibliotek, takich jak hipergraf i mhgl, nie mógł uzyskać wsparcia.
Powodem, dla którego autor chciał obsługiwać skierowane hipergrafy, było ewentualne modelowanie kierunku sygnału w przyszłości. Chciał, aby na przykład wyjściowy pin 4-wejściowego LUT był źródłem, a piny wyjściowe były źródłem w hiperkrawędzi. Mimo że nie był on pewien, czy to ma znaczenie dla problemu rozmieszczenia, chciał mieć to na uwadze, jeśli rozszerzy swój prototyp, aby obejmować również router. Zdecydował się w związku z tym na modelowanie netlisty jako grafu skierowanego z abstrakcyjnymi węzłami, obejmującymi 4 ich rodzaje zdefiniowane w jego specyfikacjach.
Kod: text
Autor korzystał z biblioteki petagraph do tworzenia samego grafu. To było miejsce, gdzie po raz pierwszy napotkał system typów w Rust działający w przyjemny sposób, dzięki tzw. generykom. Był w stanie przekazać parametr typu węzła do struktury Petagraph DiGraph. Co automatycznie narzucało ten rodzaj, a edytor uzupełniał kod do tego typu podczas dostępu do węzłów w grafie. Mimo że autor był przyzwyczajony do Pythona, zobaczenie tego działającego w Rust było dla niego naprawdę fajne, zwłaszcza biorąc pod uwagę fakt, że używa Mypy i wskazówek do podpowiadania typów w Pythonie. Dodatkowo dodał on kilka prostszych funkcji pomocniczych do uzyskiwania podsumowania węzłów.
Kod: text
Autor dodatkowo skorzystał z biblioteki rustworkx-core do generowania losowego grafu netlist w celu późniejszego przetestowania rozmieszczenia. Funkcja build_simple_netlist tworzy losowy graf Erdősa-Rényiego. Można parametryzować ten rodzaj liczbą węzłów i prawdopodobieństwem krawędzi między dwoma węzłami. Takie podejście nie odzwierciedla dokładnie właściwości rzeczywistych grafów netlist, ale jest dostateczne do przetestowania rozmieszczenia. W rzeczywistych grafach netlist mogą istnieć silnie połączone klastry węzłów, reprezentujące różne moduły sprzętowe w projekcie. Moduły te są ze sobą połączone za pomocą magistrali przewodów i wspólnie tworzą większą strukturę. Jednak nawet ta hierarchiczna struktura grafu: „modułów” na wysokim poziomie jest modyfikowana i optymalizowana w nowy graf po procesie syntezy i mapowaniu technologicznym. Niektóre nieistotne części kodu zostały pominięte w tym miejscu.
Kod: text
Algorytm
Autor stworzył układ FPGA jako typ FPGALayout, który obejmuje hashmapę typów FPGALayoutCoordinate do FPGALayoutType. Dzięki temu można odpytywać lokalizacje węzłów w układzie FPGA za pomocą ich współrzędnych. Okazało się to bardziej efektywne niż użycie ogromnej tablicy dwuwymiarowej lub wektora wektorów. Dodatkowo autor przechowuje szerokość i wysokość układu FPGA, co potrzebne jest do pracy funkcji pomocniczych, wykorzystywanych m.in. do odpytywania dowolnego punktu w układzie, z dodatkową logiką zwracającą FPGALayoutType::EMPTY, jeśli współrzędna nie znajduje się w hashmapie, lub None, jeśli współrzędna jest poza granicami.
W projekcie występują także funkcje pomocnicze do ustawiania różnych wzorców typów FPGALayoutType w układzie, takie jak config_corners, config_border i config_repeat. Ułatwiają one ustawianie wszystkich zewnętrznych krawędzi układu FPGA na FPGALayoutType::IO lub konfigurację powtarzającego się wzorca kolumn FPGALayoutType::BRAM w prosty sposób.
Kod: text
Stworzona została również prosta funkcja pomocnicza do generowania nieskomplikowanego, testowego układu FPGA z IO na zewnętrznych krawędziach (z wyjątkiem narożników), CLB wypełnionymi w środku i BRAM w środku co 10 kolumn.
Kod: text
Rozwiązanie rozmieszczania
Autor zdecydował się zamodelować rozwiązanie jako typ PlacementSolution, który zawiera odniesienie do wykresu listy sieci, odniesienie do układu FPGA i mapę łączącą NetlistNode z FPGALayoutCooperative. Rzeczywisty rdzeń rozwiązania leży w mapie skrótów. Jako że informuje ona, gdzie w układzie FPGA znajduje się każdy węzeł na liście sieci.
Kod: text
Zamiast pokazywać pełną implementację dla tego typu, autor zaprezentował jej wybrane fragmenty, które są istotne dla algorytmu. Mamy tu więc na wstępie akcje umieszczania i funkcje akcji.
Kod: text
Najprostsza akcja to przeniesienie węzła do losowego, wolnego miejsca:
Kod: text
Kolejna akcja to zamiana dwóch węzłów tego samego typu:
Kod: text
Ostatnia to przeniesienie węzła do położenia, które znajduje się bliżej centroidy wszystkich węzłów netlisty. Tutaj sytuacja jest już bardziej skomplikowana. W implementacji procesu rozmieszczania konieczne jest obliczenie centroidu, a następnie znalezienie najbliższego prawidłowego miejsca do niego. Ruch ten jest również kosztowny, co wpływa na spowolnienie działania programu. Niemniej może on przyspieszyć proces zbliżania algorytmu do lepszego rozwiązania. To dlatego, że przenoszenie węzłów do centroidu szybko i skokowo zmniejsza wartość funkcji celu, przynajmniej do pewnego momentu w trakcie optymalizacji.
Kod: text
Te akcje mogą być wywoływane za pomocą kolejnej funkcji pomocniczej:
Kod: text
Następnym istotnym aspektem rozmieszczania jest funkcja celu. Wspomniano o użyciu funkcji odległości do określania długości przewodów i sumowania wszystkich krawędzi w grafie netlisty.
Tradycyjnie termin: „siatka” odnosi się do hiperkrawędzi w hipergrafie. Abstrakcyjne: „połączenie” od pinu wyjściowego jednego węzła do wszystkich wejściowych innych węzłów może być nazwane siatką. Pojęcie to wynika z abstrakcji. Fizycznie można by narysować jedną giętą i rozgałęzioną ścieżkę w układzie scalonym, aby połączyć wszystkie piny, co będzie pełnić funkcję jednej abstrakcyjnej: „siatki”.
Poszczególne połączenia od pinu wyjściowego do wejściowego są rozumiane jako: „krawędź”. To bezpośrednio odnosi się do krawędzi w grafie, gdy rozmawiamy o abstrakcyjnych grafach w matematyce. Siatkę można przekształcić w zestaw krawędzi. Wystarczy wyliczyć wszystkie połączenia od źródła do ujścia w hiperkrawędzi siatki.
Generalnie pojedyncza: „siatka” zawiera wiele: „krawędzi”. A technicznie w przypadku rozmieszczenia ukierunkowanie obydwu nie ma znaczenia (przynajmniej w prostym problemie rozlokowywania, który został przedstawiony).
Niektóre funkcje celu są ukierunkowane na poziomie siatki. Jedną z popularnych funkcji celu, na poziomie siatki, jest Połowa Długości Obwodu Przewodów (HPWL), gdzie HPWL wynosi połowę długości obwodu otaczającego prostokątny obszar ograniczający siatkę:
$$HPWL_e = max_{i \epsilon n}(x_i) - min_{i \epsilon n}(x_i) + max_{i \epsilon n}(y_i) - min_{i \epsilon n}(y_i) \qquad (1) $$
gdzie n to krawędź, i to węzeł, a xi i yi to współrzędne x i y węzła i. Istnieje wiele proponowanych sposobów na rozluźnienie funkcji min i max, aby uczynić ją ciągłą, różniczkowalną i/lub pewną wersję wypukłą, a także inne związane cele na poziomie siatki.
Zakładając, że wszystkie siatki są po prostu dzielone na krawędzie, istnieje wiele celów na poziomie siatki, z których najprostszą klasą są funkcje odległości w przestrzeni euklidesowej. Odległość liczona jest zgodnie z metryką Manhattan, znaną również jako: „liniowy” model długości przewodu, ma na celu modelowanie optymalnego fizycznego prostokątnego układu przewodów w chipie. Jest to sformułowane jako:
$$d_{ij} = \left | x_k - x_j \right | \qquad (2)$$
a funkcja celu jako:
$$\sum_{e \epsilon E} d_e = \sum_{e \epsilon E} \left | x_k - x_j \right | + \left | y_k - y_j \right | \qquad (3) $$
Jednakże bardziej popularną miarą jest odległość kwadratowa lub „kwadratowy” model długości przewodu. Jest to sformułowane jako:
$$d_{ij} = (x_i - x_j)^2 /qquad (4) $$
a funkcja celu jako:
$$\sum_{e \epsilon E} d_e = \sum_{e \epsilon E} (x_i - x_j)^2 + (y_i - y_j)^2 \qquad (5) $$
W symulowanym algorytmie autor używa modelu liniowej długości przewodu w funkcji celu, przy czym wszystko jest modelowane jako zwykłe krawędzie, a nie siatki. Nazwa cost_bb jest nieco myląca, ponieważ nie są obliczane żadne wartości związane z prostokątną obwiednią siatki. Autor jedynie sumuje odległość zgodnie z wybraną metryką wszystkich krawędzi w grafie netlisty.
Kod: text
W implementacji dodano także dwie niezależne funkcje pomocnicze do generowania początkowych rozwiązań rozmieszczenia — podejście: losowe (gen_random_placement) i zachłanne (gen_greedy_placement). To ostatnie lokuje węzeł w pierwszym dostępnym miejscu w lewym górnym rogu układu FPGA. Pozwala to na umieszczenie wszystkich węzłów obok siebie w początkowym rozwiązaniu. Jednak prawdopodobnie sprawia to, że trudniej jest je zoptymalizować bardziej zwartym sposobem. Przynajmniej w porównaniu z początkowym rozwiązaniem, w którym węzły są ulokowane średnio daleko od siebie. Jednak są łatwiejsze do zoptymalizowania.
W implementacji rozwiązania rozmieszczenia znajdują się również dodatkowe funkcje, takie jak render_svg, służąca do generowania wizualizacji prezentowanych w tym wpisie, oraz typ Renderer z funkcją render_to_video, która korzysta z narzędzi imagemagick i ffmpeg do generowania filmów i plików GIF z procesu optymalizacji.
Algorytm rozmieszczania
Ostatnim elementem jest właściwy rozmieszczacz, który okazuje się zaskakująco prosty i zwarty jako pojedyncza funkcja. W tej implementacji badane są równolegle wielokrotne ruchy w każdym kroku, a następnie wybiera się najlepszy podjęty w danym etapie. Wykorzystywana jest także funkcja par_iter z biblioteki rayon do równoległego przetwarzania eksploracji ruchów w każdym kroku. To proste rozwiązanie pozwala przyspieszyć proces optymalizacji. Jednak może wymagać regulacji, ponieważ równoległa eksploracja ruchów może wprowadzić pewne nakłady związane z równoległym przetwarzaniem.
Idealnie byłoby znaleźć niebanalny kompromis między liczbą wszystkich posunięć podjętych a liczbą równoległych działań badanych w każdym etapie. Więcej działań na krok skutkuje lepszą okazją na znalezienie bardziej miarodajnego ruchu w danej fazie. Acz więcej kroków ogółem oznacza większą szansę na osiągnięcie stabilnego optymalnego rozwiązania, wszystko to przy koszcie całkowitego czasu działania. Być może w różnych momentach procesu optymalizacji chciałoby się dostosować liczbę równoległych działań badanych w każdym kroku. To coś, co autor chce zweryfikować w przyszłości i bezpośrednio wiąże się z aspektem: „wyżarzania” w tradycyjnym procesie danego typu. Zmiana wartości liczby działań badanych w każdym kroku nazywa się budowaniem harmonogramu wyżarzania. Ma to również pewne podobieństwo do wybierania harmonogramów współczynnika uczenia w głębokim uczeniu.
Kod: text
Rezultaty i wizualizacja
Autor do testów wykorzystał następujące dane:
* Netlistę zawierającą 300 węzłów: 10 IO, 100 BRAM i 190 CLB.
* FPGA o wielkości 64 × 64 bloków z miejscem dla IO przy krawędzi, CLB w środku i miejscem na moduły BRAM w kolumnach, co 10 kolumn.
* Algorytm optymalizacji rozmieszczenia uruchamiany był na 1000 kroków.
* Algorytm inicjowano z różnymi ustawieniami n_neighbors = [1, 4, 8, 16, 32, 64, 128, 256]; każda próba wykorzystywała to samo wstępne rozmieszczenie elementów.
Algorytm zadziałał poprawnie. Na ilustracji poniżej pokazano układ przed i po optymalizacji dla n_neighbors = 32.
Na filmie poniżej umieszczono animację, pokazującą działanie poszczególnych kroków w sekwencji:
Najbardziej zauważalnym aspektem tego algorytmu jest fakt, że wydaje się on mocno polegać na ruchach skierowanych, aby przenosić węzły do centroidu grafu netlisty. Prawdopodobnie zaczynając od losowego rozwiązania początkowego, ruchy te stają się najbardziej skuteczne w obniżaniu wartości funkcji celu. Z biegiem czasu, w miarę umieszczania coraz więcej węzłów w centrum, wpływa to na to, że ruchy skierowane przemieszczają je w miejsca, gdzie wszystkie znajdują się w środku. Jednak ruchy: losowe i zamiany wciąż są wartościowe dla algorytmu, aby badać optymalizację rozmieszczenia wejść/wyjść, ponieważ są one ograniczone do zewnętrznych krawędzi układu FPGA, a także dla bloków BRAM, jako że mają one duże skoki między kolumnami.
Dodatkowo, eksplorowano, jak liczba równoległych sąsiadów badanych w każdym kroku wpływa na proces optymalizacji. Wyniki przedstawiono poniżej na wykresie stworzonym przy użyciu gnuplot.
W zgodny z intuicją sposób, uruchomienie algorytmu z największą liczbą równoległych sąsiadów, którą można zbadać jednocześnie, nie jest najlepsze dla optymalizacji funkcji celu rozmieszczenia na przestrzeni całego procesu. Jednakże wydaje się, że jeśli chcemy przeszukiwać to z 4 lub więcej równoległymi sąsiadami, ponieważ przy 1 lub 2 nie jest to tak skuteczne.
Wygląda również na to, jak wskazuje autor, że może występować zjawisko kurczącego się zysku ze zmian i malejąca wartość funkcji celu zbiega do tej wartości ostatecznej w miarę zwiększania liczby równoległych sąsiadów do przeszukania. Jednak nie jest to jeszcze w pełni jasne ani nie ustalono, jaka jest optymalna wartość sąsiadów dla równoległego przeszukiwania w każdym kroku. Ten wynik jest również bardzo specyficzny dla tej netlisty i symulowanego układu FPGA, które zostały wykorzystane do przetestowania algorytmu. Potrzebne są bardziej zróżnicowane i kompleksowe eksperymenty, aby wyciągnąć bardziej ogólne wnioski, wskazuje autor.
Kod źródłowy i odtwarzalność
Cały kod źródłowy tego projektu można znaleźć tutaj. Pozwala to na zgłębienie szczegółów implementacji, które pominięto w tym poście, a także na eksperymentowanie z kodem i wypróbowywanie różnych pomysłów. Wygenerowane pliki danych (.CSV) i wizualizacje (.PNG, .MP4, .GIF) są również dostępne w repozytorium autora.
Podsumowanie
Po zakończeniu projektu, autor tego: „zabawkowego” algorytmu do rozmieszczania ma pewne refleksje na temat algorytmów EDA (Automatyzacji Procesu Projektowania) i badań w tej dziedzinie, które uznaje za istotne do wyrażenia.
Uważa on, że pomysły prezentowane w artykułach naukowych i konferencyjnych stają się znacznie bardziej zrozumiałe, gdy udaje się wyodrębnić ich główne idee i zacząć od podstaw. Zauważa jednak, że wiele opublikowanych tekstów technicznych dotyczących algorytmów EDA nie należy do przystępnych lub są zbyt zdawkowe. Dostrzega on, że podręczniki i wysokiej jakości materiały do nauki są przydatne do pogłębiania wiedzy poza powierzchowny poziom treści. Dodatkowo, uważa, że dostępne i wysokojakościowe (niekoniecznie: „badawcze”) kody źródłowe zaawansowanych algorytmów EDA są również trudne do znalezienia.
Po wykorzystaniu Rusta do zastosowań w EDA, autor ma wyższe oczekiwania i standardy dla oprogramowania EDA. Uznaje, że istnieją znaczne luki w wydajności nowoczesnych narzędzi i algorytmów EDA, które, dzięki większemu nakładowi na inżynierię oprogramowania i algorytmy, można by pokonać. Po zastosowaniu Rusta sądzi, że jest to jeden z najlepszych kandydatów do tego rodzaju oprogramowania, które opiera się na strukturach danych i algorytmach, przy wysokich standardach poprawności i niezawodności.
Marzeniem autora jest życie w idealnym świecie, w którym, aby w pełni syntetyzować, rozmieścić i trasować duży nowoczesny projekt dla współczesnego układu FPGA wystarczy mniej niż minuta. Po zakończeniu swojej pracy widzi oznaki nadziei na taką przyszłość, jednakże nie wskazuje, kiedy może to nastąpić.
Źródło: https://stefanabikaram.com/writing/fpga-sa-placer/
Fajne? Ranking DIY
