Elektroda.pl
Elektroda.pl
X
PCBway
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[VHDL] Implementacja dużego automatu w Quartusie

18 Cze 2010 17:13 2577 15
  • Poziom 10  
    Witam!
    Mam problem z implementacją naprawdę dużego automatu w VHDLu (77250 stanów). Przy kompilacji projektu dostaje zawsze komunikat: "Out of memory in module quartus_map.exe". Znalazłem informację, że pojawia się gdy mam za mało pamięci operacyjnej na PC. Ale zastanawiam się czy można to jakoś obejść? Np poprzez zastosowanie jakiegoś kodowania stanów automatu? Czy to może załatwić sprawę? Jeżeli tak to które kodowanie jest najbardziej efektywne- co polecacie?

    Mam też drugi problem związany właśnie z kodowaniem stanów w automacie. Konkretnie nie mogę znaleźć gdzie w Quartusie się to ustawia. W jakimś manualu była podana informacja, że należy szukać w Assigments->Settings->Analysis & Synthesis Settings ale w mojej wersji (9.1) Quartusa nic takiego nie mogę znaleźć.

    Byłbym bardzo wdzięczny za wszelką pomoc.
    Pozdrawiam
  • PCBway
  • Poziom 13  
    Witam

    Myslę że kodowanie Quartus sam przestawił na binarne, bo ONE-HOT bit stanowczo nie zdaje egzaminu w tak duzych maszynach stanów. Default'owo kodowanie maszyny stanu jest ustawione na AUTO, więc Quartus powinien sam zdecydować, że twoja maszyna stanów ma być kodowana jako binarna.

    Mozna to sprawdzić w ustawieniach. ( Syntezy i kompilacji )

    [VHDL] Implementacja dużego automatu w Quartusie

    pozdrawiam
    Bartek
  • Poziom 10  
    Wielkie dzięki- głupio się przyznać ale naprawdę nie mogłem znaleźć gdzie się ustawia kodowanie stanów automatu.

    Jednak problem nie został rozwiązany. Spróbowałem wszystkich rodzajów kodowania ale nie dało to oczekiwanego efektu (cały czas błąd o za małej ilości RAMu). Dlatego przesiadłem się na maszynę z 4GB ramu. Efekt ten sam. Mam wrażenie, że automat jest za duży lub (oby tak było jest nieefektywnie opisany). Czy znacie może jakiś efektywny sposób napisania funkcji przejść? Mój kod wygląda następująca:

    begin
    -- reset asynchroniczny i przechodzenie między stanami
    process (clk, rst)
    begin
    if (rst = '1') then
    state_reg <= s0;
    elsif rising_edge(clk) then
    if divideclk = '1' then
    state_reg <= state_next;
    divideclk <= '0';
    else
    divideclk <= '1';
    end if;
    end if;

    end process;

    -- funkcja przejść automatu
    process (state_reg, stream)
    begin
    found <= '0';
    case state_reg is
    when s0 =>
    found <= '0';
    if stream = "01010110" then
    state_next <= s1;
    fail_edge <= '0';
    elsif stream = "01000011" then
    state_next <= s21;
    fail_edge <= '0';
    elsif stream = "01000010" then
    state_next <= s38;
    fail_edge <= '0';
    elsif stream = "00110001" then
    state_next <= s61;
    fail_edge <= '0';
    elsif stream = "01001001" then
    state_next <= s77;
    fail_edge <= '0';
    elsif stream = "01001000" then
    state_next <= s104;
    fail_edge <= '0';
    elsif stream = "01110101" then
    state_next <= s116;
    fail_edge <= '0';
    ... itp itd- razem ok 700tys linii kodu
    Da się coś z tym zrobić?
    Proszę o każdą podpowiedź, która może naprowadzić mnie na właściwe rozwiązanie
    Pozdrawiam i dzięki za zainteresowanie!
  • PCBway
  • VIP Zasłużony dla elektroda
    Może opisz co próbujesz zrobić, bo na 90% da się to zrobić inaczej...
    Nie znając dokładnie problemu rozważyłbym:
    a) głębszą analizę kodowania stanów i zmiennych
    b) implementację w pamięci ROM (być może iteracyjną, jeśli wymagania czasowe na to pozwalają)

    Co do Twojego rozwiązania - jeśli możesz, to przejdź na opis typu
    Code:
    case stream is
    
        when abc =>
            next_state <= sabc;
        when xyz =>
            next_state <= sxyz;
        -- jeśli to możliwe, to omiń jakoś "when others", które generuje dużo logiki
        -- np. w pasujących branchach użyj update <= '1' i traktuj ten bit jako
        -- enable do procesu opisującego rejestr stanu
        when others =>
            next_state <= current_state;
    end case;

    Pozdrawiam,
    Dr.Vee
  • Poziom 30  
    Swego czasu natknąłem się na "złote zasady" w przypadku wyższej szkoły latania na miotle bez miotły za to używając języka VHDL :-)
    Jedno z nich to:
    "Do not use nested If Statements when a Case Statement can be used instead.

    Może zadziała. Natomiast ostatnio też walczyłem z Quartusem i muszę powiedzieć, że podobnie jak MAX+PLUS II jest wkurzający. Troszkę poprawili optymalizację jednak upakowanie projektu wykorzystującego 95% zasobów do scalaka to droga przez mękę i wymaga albo gigantycznej wiedzy skierowanej na konkretny układ scalony albo dużo szczęścia (czasem niewielka zmiana kodu nagle zwalania do 20% zasobów -> cały urok układów programowalnych).
  • Poziom 10  
    No to trochę szerzej opiszę problem. Ogólnie implementuje algorytm Aho-Corasick w VHDLu. Samego algorytmu opisywać nie będę bo nie jest taki prosty ale ogólnie chodzi o problem wyszukiwania wielu wzorców w pewnym tekście wejściowym (używany np w IDSach lub w analizie DNA). Moje zadanie sprowadza się do zaimplementowania pewnego automatu wykrywającego pewien zestaw sekwencji. Np ABBA BABA itp. Na wejście podaje po kolei każdą literę tekstu wejściowego (wejście stream 8 bit). Wewnątrz automat przechodzi po stanach aż dotrze do stanu akceptującego- wtedy na wyjście wyrzucana jest wartość found=1. Dodatkowo mam jeszcze wyjście fail_edge którego wartość wynika z działania algorytmu AC (dla danego stanu i wejścia ma wartość 1 lub 0). I teraz implementuje automat (jest on b. duży bo posiada 77250 stanów).
    state_reg- stan w którym się znajdujemy obecnie
    state_next - stan następny
    process (state_reg, stream)
    begin
    found <= '0';
    case state_reg is
    when s0 =>
    found <= '0';
    if stream = "01010110" then
    state_next <= s1;
    fail_edge <= '0';
    elsif stream = "01000011" then
    state_next <= s21;
    fail_edge <= '0';
    .
    .
    .i tu za pomocą elsif wyszczególnione wszystkie przejścia ze stanu s0 do możliwych stanów w zależności od wejścia stream

    when s1 =>
    found <= '0';
    if stream = "01101111" then
    state_next <= s2;
    fail_edge <= '0';
    elsif stream = "01100001" then
    state_next <= s729;
    fail_edge <= '0';
    elsif stream = "01000101" then
    state_next <= s981;
    fail_edge <= '0';
    elsif stream = "01100101" then
    state_next <= s2281;
    fail_edge <= '0';
    elsif stream = "01101001" then
    state_next <= s2543;
    fail_edge <= '0';
    elsif stream = "00001110" then
    state_next <= s17682;
    fail_edge <= '0';
    elsif stream = "01010010" then
    state_next <= s18574;
    fail_edge <= '0';
    elsif stream = "01110101" then
    state_next <= s18987;
    fail_edge <= '0';
    elsif stream = "01001001" then
    state_next <= s70996;
    fail_edge <= '0';
    else
    state_next <= s0;
    fail_edge <= '1';
    end if;
    .
    .
    . wyżej kompletna lista przejść dla stanu s1

    itd dla każdego z 77250 stanów. Pik zawierający opis automatu ma 700tys linii kodu :|

    No i jeszcze dla porządku proces odpowiadający za przechodzenie między stanami:
    process (clk, rst)
    begin
    if (rst = '1') then
    state_reg <= s0;
    elsif rising_edge(clk) then
    if divideclk = '1' then
    state_reg <= state_next;
    divideclk <= '0';
    else
    divideclk <= '1';
    end if;
    end if;

    end process;

    pojawia się sygnał divideclk- służy do tego żeby przejście między stanami odbywało się co drugi cykl zegara (bo przed automatem stoi nieco nietypowa kolejka FIFO jako pewnego rodzaju bufor- konieczne ze względu na naturę działania algorytmu AC)

    No i teraz pytanie- co z tym zrobić żeby jakoś to zmniejszyć?
    Każda uwaga będzie na wagę złota- z góry dziękuję!

    Proszę w swoich postach kod umieszczać w odpowiednich znacznikach!
    Robak
  • Poziom 27  
    podobnie jak Dr.Vee sadze, ze algorytm rozpoznawania
    ciagu powinien byc zaimplementowany w pamieci rom, nie jako fsm;
    jesli pierwsza 'literka' ciagu jednoznacznie okresla poszukiwany
    ciag, to sprawa jest prosta, problem sprowadza sie do tego,
    czy w fpga jaka masz do dyspozycji jest dosc pamieci;
    jesli na dana literke [np.] 'A' moze zaczynac sie kilka roznych
    ciagow to gorzej;
    jesli wyjasnisz te kwestie, bedziemy myslec dalej;
    nawiasem mowiac duze fsm [maszyne stanow] tez mozna
    efektywnie zaimplementwac jako rom;

    przy okazji do kemot55:
    jesli 'czasem niewielka zmiana kodu nagle zwalania do 20% zasobów'
    to raczej znaczy, ze kod jest zle napisany, a nie ze quartus ma
    kiepska synteze

    J.A

    Proszę poprawić pisownię.
    Robak
  • VIP Zasłużony dla elektroda
    Chyba zastosowałeś algorytm zoptymalizowany pod software, a nie hardware.

    Jeśli wyszukujesz w strumieniu x wzorców, to sugeruję implementację jako x równoległych automatów (być może zaimplementowanych jako ROM).

    Pozdrawiam,
    Dr.Vee
  • Poziom 10  
    Wzorców jest 9tys i nie ma żadnych wymagań typu, że zaczynają się od różnych liter. Mogą zaczynać się od tej samej, jeden wzorzec może być prefiksem drugiego, w jednym wzorcu może się zawierać kilka innych, które na dodatek zachodzą na siebie. Jednym słowem może dziać się wszystko. Dlatego jedynym logicznym rozwiązaniem jest użycie algorytmu Aho-Corasick (a przynajmniej jak na moją obecną wiedzę). Być może źle podchodzę do implementacji tego algorytmu ale też nie bardzo widzę inną możliwość.
    Szczerze mówiąc mam niewielkie doświadczenie jeśli chodzi o VHDL. Mówicie o implementacji w pamięci ROM. Macie może jakiś tutorial jak coś takiego się robi lub (leżeli to proste) możecie na szybko wyjaśnić?
    Ogólnie dziękuję bardzo za pomoc! Już to co dotąd powiedzieliście daje do myślenia!
    Z góry dzięki za wszelkie następne pomysły- każdy może się przydać.
    Pozdrawiam
  • Poziom 27  
    jesli nie ma zadnych ograniczen, wstepnych zalozen [rzeczywiscie mozliwych
    znakow jest 256 ?] to bedziesz potrzebowal sporej fpga;

    na szybko, w przerwie meczu - taka idea:
    robisz pamiec o 16 bitowym adresie i szerokosci slowa 10 bitow,
    przychodzacy symbol jest mlodsza czescia adresu pamieci, a zawartosc
    pamieci starsza czescia, tak zlozony adres przesuwa cie do nastepnej komorki
    rom'u;
    mlodszy z dwoch najstarszych bitow sygnalizuje, czy ciag nadal jest poprawny,
    najstarszy , ze ciag jest znaleziony i poszukiwanie zakonczone;
    JA
  • Poziom 10  
    A mógłbyś jakoś bardziej łopatologicznie to wytłumaczyć lub pismem obrazkowym ;p ? Bo nie bardzo rozumiem o co dokładnie chodzi?
  • Poziom 30  
    Oczywiście, że w większości przypadków niewiedza przy pisaniu kodu jest powodem tego, że coś jest nagle zbyt duże. Ale to co miałem na myśli dotyczyło w zasadzie ustawień konfiguracji Quartusa (np. domyślnie włączona jest optymalizacja prędkości a nie obszaru) i przestawień całych konstrukcji "if" wewnątrz procesu. Mam wrażenie, że chodzi tu o problemy z routerem i brakiem możliwości wykonania przejść - i tu właśnie kłania się optymalizacja. Ten sam kod w MAX +PLUS II 10 nie jest "fitowalny". W Quartusie zostaje jeszcze 10% zasobów. Tak czy inaczej żaden program nie zastąpi projektanta (ale oczekiwania cudów zawsze gdzieś tam głęboko pozostaną :-)).
    A wracając do tematu automatu stanu. Rozumiem, że kolega andysw używa wersji WEB Quartusa? Czy nie ma to jakiś ograniczeń co do wielkości kodu? Próbowałem znaleźć stosowną informację - niestety bez powodzenia.
  • Poziom 27  
    andysw napisał:
    A mógłbyś jakoś bardziej łopatologicznie to wytłumaczyć lub pismem obrazkowym

    nie jest to az tak proste, jak mi sie z poczatku wydawalo, mozliwe, ze uda
    mi sie to opisac 'obrazkowo' dopiero w przyszly weekend, mam nadzieje,
    ze mozesz tyle poczekac [mam swoja pilna robote];
    de facto mam na mysli realizacje dokladnie tej funkcji, ktora sam opisales
    w swoim poscie, tyle ze implementowanej z uzyciem wew. pamieci fpga
    jako rom [read only memory]
    JA
  • VIP Zasłużony dla elektroda
    Tak czy inaczej sądzę, że będziesz musiał jakoś "ręcznie" podzielić ten automat na równolegle działające mniejsze - tak, aby było to do strawienia przez narzędzia do syntezy.

    Mam nadzieję, że przejrzałeś już literaturę - wykrywanie stringów/regexpów w FPGA to dość długo wałkowany temat (analiza pakietów sieciowych), a dopasowywanie tekstu do zbioru wzorców to typowa aplikacja wyszukiwania białek...

    Zastanów się też, czy potrzebujesz aż 8 bitów na znak - może da się część odrzucić, a resztę np. przekodować na "gorącą jedynkę" i uprościć komparatory? Spróbuj może wykonać klika eksperymentów z syntezą dla zredukowanego rozmiaru problemu żeby znaleźć optymalne podejście i ocenić, czy dasz radę zmieścić ten układ do FPGA.

    Pozdrawiam,
    Dr.Vee
  • Poziom 27  
    nie da sie tego zrobic tak, jak proponowalem, przynajmniej ja nie
    widze takiej mozliwosci przy twoich zalozeniach;
    sugestie 'doktora' wydaja sie byc rozsadne;
    JA
  • Poziom 20  
    Takie pytanie trochę off-topic: jak szybko ma działać te wyszukiwanie? (tzn. jak szybko przychodzą dane na wejście stream?) Z Twoich fragmentów kodu wynika, że dałoby się to zrobić software'owo z całkiem przyzwoitą wydajnością.

    Pzdr
    TW