Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
15 years ago

Problem witch implementing big automaton

Hi!

I have serious problem with implementing big automaton in VHDL (it has about 77250 states). When i try complie project in Quartus, everytime i get an error "Out of memory in module quartus_map.exe". Is someone can help me? I am thinking about changing state machine encoding but i don't have too much experience- i don't know witch encoding standard use and i don't know does the state encoding change can help?

I have also secound problem connected to encoding standards. I don't know where can i change encoding standards. In manuals i found information that it is in Assigments->Settings->Analysis & Synthesis Settings but in Quartus i use (version 9.1) there is nothing about states encoding.

16 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor

    first, remember the counter use is not going to solve your issue much since the associated logic is huge.

    However, in your case do this:

    
    --pseudocode
    -- divide clk process
    process
    begin
       wait until clk = '1';
       divideclk <= not divide clk;
    end process;
     
    then use that divideclk as enable:
    process
    ...clk edge ...etc
    if divideclk = '1' then
     
       fail_edge <= '0'; --default
       case count is
           when 0 =>
               if stream = "00101110" then
                  count <= 21;
               end if;
           when 1 => 
               if stream = ....
                  count <= 102;
                  fail-edge <= '1'; --non default
               end if;
     
    ...etc
    
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor

    I feel this is a case for a memory look-up approach. It looks like you have some 256 states checking a stream of 8bit input data. In stead of using logic we now need about 256 (states) * 256 (input stream) * 8 (next state) bits (or 524288 bits in total) of ram to just code the state machine. If you need to do some actions in some states you will have to add extra memory bits. Now the work will shift from writing case statements to fill the RAM. One disadvantage of using memory blocks is the latency as the next_address is registered inside the memory system. Writing the MIF file will be a lot less tedious then enumerating the 256 or so case statements.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor

    Hi!

    I would like to refresh topic. I had lot of work so my project has to wait a moment. I follow by yours advice by using counter instead of all states definition. It slove one problem but cause another. Now Quartus doesn't indicate out of memory problem but compilation takes ages... While i'am writting this post compilation lasts 30 minutes on fastest PC i have access to (Intel core i5 2,79 GHz, 4 GB RAM, 32 bit operating system). I was trying on slower machine and compilation takes 1,5 hours and hasn't stop.

    1.) Could you look on this project and give me some advaices how to optimize it? Link to file i will send in next post because now i don't have enought posts.

    2.) Do you have any tutorial how to use mif file? Because i have never use it and i know nothing about it.

    Thanks in advance for all your advices!
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor

    Hi,

    due to this long compilation if it was me, I will go for memory based design i.e. design a dedicated processor in effect.

    Your memory can be as wide as you need. The address first points to count 0 (or state 0). The content of the location will encode information e.g. 16 bits for next count, bits for actions. Decide how many actions you have, design rtl only for them to be enabled accordingly. add wait states to your address...so on. So much of the logic is precomputed and stored, relieving the burden on logic of FPGA.

    You will need mif or hex file. the easiest way is to go quartus,files => new => mif =>

    decide width and size then put few values, save. then look at it in an editor to see its format and then you can use any programming tool to generate the mif file for your data.

    I had posted recently a Matlab based approach to generate mif:

    http://www.alteraforum.com/forum/showthread.php?t=23628
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor

    I perused the automatTest.vhd file. It truly is a large state machine. I saw 71555 states. If you'd take the approach I suggested earlier you would need more memory bits that you could find in any FPGA: about (2^(17+8) )* 20 = 671 Mbit.

    So let's 'divide and conquer': most of the states are simple 'pass to next / jump on fail', a limited number of states have multiple jump targets so you could try to divide the decision-making over several RAM-lookup machines. This would limit the RAM-usage to about (2^17) * 27 = 3.6 Mbit

    I kind of like Kaz' idea to build a dedicated sequencer. It will have the advantage of being reasonably general (-> easy to change the state sequence etc.) but it will/can only examine one 'stream' condition per clock, unless you add separate 'stream' comparison blocks for the few 'multiple jump' cases which brings you back to the 'divide and conquer' approach.

    Being curious: what is the goal of this project?