From: elmoties@hotmail.com Newsgroups: comp.arch.fpga Subject: FSM encoding Date: Wed, 17 Jan 2001 07:11:11 GMT Organization: Deja.com Lines: 35 Message-ID: <943gid$9er$1@nnrp1.deja.com> NNTP-Posting-Host: 129.97.38.33 X-Article-Creation-Date: Wed Jan 17 07:11:11 2001 GMT X-Http-User-Agent: Mozilla/5.0 (X11; U; Linux 2.2.17-21mdk i686; en-US; 0.7) Gecko/20010105 X-Http-Proxy: 1.1 x73.deja.com:80 (Squid/1.1.22) for client 129.97.38.33 X-MyDeja-Info: XMYDJUIDelmoties Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newsfeed-zh.ip-plus.net!news.ip-plus.net!news.tesion.net!news.belwue.de!news.uni-ulm.de!rz.uni-karlsruhe.de!blackbush.xlink.net!newsfeed.germany.net!news.tele.dk!144.212.100.101!newsfeed.mathworks.com!news.maxwell.syr.edu!nntp2.deja.com!nnrp1.deja.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:3896 Hi, I'm designing an arithmetic accelerator for the Xilinx Virtex 50K. I'm having trouble synthsizing a design that I thought would fit with no problems. Xilinx's ISE 3.1i reports only using about 10500 gates but it requires 99% of the slices on the FPGA. The design is a large FSM that has about 30 states. There is four registers (idealing I want to have > 128 bit) that have operations performed between them (xor, shifting with feedback) in several of the states. Most of the other states just before trivial signaling for memory loading. Several of the states have case statements contained with-in them to determine when to peform specific operations. My questions: (I'm more than willing to post more information if somebody wants it) Do FPGA's have an inherently hard time laying out large FSM's? Is there a particular FSM encoding that is better than others for space considerations? Is having nested states (via cases statements inside a state) a bad thing for compact sythesizing? Is having nonstandard signal sizes that are quite large ( greater than 128 bit) really difficult to place and route on an FPGA Thanks, Jeff Elmot Sent via Deja.com http://www.deja.com/ ###### Message-ID: <3A665561.1942031F@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.73 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: FSM encoding References: <943gid$9er$1@nnrp1.deja.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 98 Date: Thu, 18 Jan 2001 02:27:46 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 979784866 24.13.238.93 (Wed, 17 Jan 2001 18:27:46 PST) NNTP-Posting-Date: Wed, 17 Jan 2001 18:27:46 PST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.direct.ca!look.ca!newshub2.rdc1.sfba.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:3943 elmoties@hotmail.com wrote: > > Hi, > > I'm designing an arithmetic accelerator for the Xilinx Virtex 50K. > > I'm having trouble synthsizing a design that I thought would fit with no > problems. Xilinx's ISE 3.1i reports only using about 10500 gates but it > requires 99% of the slices on the FPGA. > > The design is a large FSM that has about 30 states. There is four > registers (idealing I want to have > 128 bit) that have operations > performed between them (xor, shifting with feedback) in several of the > states. Most of the other states just before trivial signaling for > memory loading. > > Several of the states have case statements contained with-in them to > determine when to peform specific operations. > > My questions: (I'm more than willing to post more information if > somebody wants it) > > Do FPGA's have an inherently hard time laying out large FSM's? > Is there a particular FSM encoding that is better than others for space > considerations? THere are two things that need to be considered. First is the logic implementation, which for a FSM means reducing the equations to logic. This is a function of your coding style as well as of the synthesis and mapper algorithms. If you have nested ifs in your code, those will often generate many levels of logic, often shared. Signals that have more than one destination are harder to layout. I don't know that any one encoding is going to work out better space wise without knowing how many ins and outs to each state. The second is the placement. I am still not very impressed with the abilities of the automatic placer. Unfortunately, a synthesized FSM is very difficult to place by hand, and because it usually has several levels of combinatorial logic is subject to instance name changes when the design is iterated. > Is having nested states (via cases statements inside a state) a bad > thing for compact sythesizing? can be. > Is having nonstandard signal sizes that are quite large ( greater than > 128 bit) really difficult to place and route on an FPGA > No,not usually. The current FPGA placement tools do not seem to have much awareness of whether a signal is part of a bus or not. a few suggestions: 1) You might use the block rams in the XCV50 for the FSM, it will provide a faster machine, and alot less sensitivity to changes in the state machine definition. I think there may be a xilinx app-note on it. The BRAM is used as a ROM that outputs the next state, plus any decoded outputs as a function of the current (encoded) state and some inputs. If there are many inputs, they can usually be selected by a mux using the current state to reduce the number of address pins needed for the memory. 2) Break the state machine into several smaller linked state machines. It makes it easier for the synthesis and placement, and also has the advantage of usually making it easier for you to follow when you come back to it 6 months from now. It will most likely also reduce the number of inputs to at least some of the states. It sounds like you might have some data path mixed in with your state machine. That's the first place I'd look for subdividing. > Thanks, > > Jeff Elmot > > Sent via Deja.com > http://www.deja.com/ -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com or http://www.fpga-guru.com ###### From: Luis Yanes Newsgroups: comp.arch.fpga Subject: Re: FSM encoding Date: Fri, 19 Jan 2001 18:26:29 +0100 Organization: Escuela Superior de Ingenieros de Sevilla Lines: 31 Message-ID: References: <943gid$9er$1@nnrp1.deja.com> <3A665561.1942031F@andraka.com> NNTP-Posting-Host: 193-152-230-157.uc.nombres.ttd.es Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Newsreader: TIN 1.1 Beta Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!merapi!news-ge.switch.ch!naxos.belnet.be!news.belnet.be!news.rediris.es!newsfeed.mad.ttd.net!news.mad.ttd.net!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:3993 On Thu, 18 Jan 2001 02:27:46 GMT Ray Andraka wrote: >1) You might use the block rams in the XCV50 for the FSM, it will provide a >faster machine, and >alot less sensitivity to changes in the state machine definition. I think there >may be a >xilinx app-note on it. The BRAM is used as a ROM that outputs the next state, >plus any decoded outputs >as a function of the current (encoded) state and some inputs. If there are many >inputs, they can usually >be selected by a mux using the current state to reduce the number of address >pins needed for the memory. This is new way for the old style FSM made with a latch and EPROM as lookup table that fills the whole possible 'state space'. But with the distributed memory in the FPGA aproach there is holes in the 'state space', what hapens when an illegal state are reached? (due to noise, bug, etc.). There is a predictable way of recover?. I'm asking to implement the DCD DPLL FSM in FPGA I have in EPROM/lach. ( http://www.terra.es/personal2/melus0/gwlhw0n.html ). Sorry if this is a stupid question, I've only done small FSMs. And I know that when done with independent flip/flops something similar happens. (A 17 state machine with 16 flip/flops). 73's de Luis mail: melus0(@)teleline(.)es Ampr: eb7gwl.ampr.org http://www.terra.es/personal2/melus0/ <- PCBs for Homebrewed Hardware ###### From: Peter Alfke Newsgroups: comp.arch.fpga Subject: Re: FSM encoding Date: Fri, 19 Jan 2001 10:02:24 -0800 Organization: Xilinx Lines: 58 Message-ID: <3A688130.FE919325@xilinx.com> References: <943gid$9er$1@nnrp1.deja.com> <3A665561.1942031F@andraka.com> Reply-To: peter.alfke@xilinx.com NNTP-Posting-Host: peter.xsj.xilinx.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353" Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.7C-CCK-MCD {C-UDP; EBM-APPLE} (Macintosh; I; PPC) X-Accept-Language: en To: Luis Yanes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!nntp-out.monmouth.com!newspeer.monmouth.com!cpk-news-hub1.bbnplanet.com!washdc3-snh1.gtei.net!news.gtei.net!feeder.qis.net!ptdnetP!newsgate.ptd.net!attmtf.ip.att.net!attla1!ip.att.net!newsgate.xilinx.com!cliff.xsj.xilinx.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:4000 Maybe this is "old hat", but here are my suggestions for a brute-force table-look-up FSM in Virtex: Use the 4K bit RAM, properly initialized during configuration. So it really is a ROM, since you never write into it. Use it as 512 x 8 ROM. Feed 5 of the 8 outputs back to the input and use the remaining 4 inputs as control. You now have a 32-state FSM with 4 condition inputs, and 3 extra arbitrarily decoded outputs, beyond the 5 encoded outputs. You can define everything, like recovery from illegal states, etc. No holes. In Virtex-II the ROM is bigger, 18K bits. So you can have a 128-state FSM with 4 control inputs, with the ROMconfigured 2K x 9. Or 64 states with 5 control inputs. Since these are synchronous dual-ported ROMs, you don't need any extra output or input registers, and you can run at 200 MHz. Also, you automatically get two FSMs in the same memory, both with the identical transition table, but individual control inputs and individual clocking. It's all pretty obvious once you think about it... Peter Alfke, Xilinx Applications ======================================== Luis Yanes wrote: > On Thu, 18 Jan 2001 02:27:46 GMT Ray Andraka wrote: > > >1) You might use the block rams in the XCV50 for the FSM, it will provide a > >faster machine, and > >alot less sensitivity to changes in the state machine definition. I think there > >may be a > >xilinx app-note on it. The BRAM is used as a ROM that outputs the next state, > >plus any decoded outputs > >as a function of the current (encoded) state and some inputs. If there are many > >inputs, they can usually > >be selected by a mux using the current state to reduce the number of address > >pins needed for the memory. > > This is new way for the old style FSM made with a latch and EPROM as lookup > table that fills the whole possible 'state space'. > > But with the distributed memory in the FPGA aproach there is holes in the > 'state space', what hapens when an illegal state are reached? (due to > noise, bug, etc.). There is a predictable way of recover?. > > I'm asking to implement the DCD DPLL FSM in FPGA I have in EPROM/lach. > ( http://www.terra.es/personal2/melus0/gwlhw0n.html ). > > Sorry if this is a stupid question, I've only done small FSMs. And I know > that when done with independent flip/flops something similar happens. > (A 17 state machine with 16 flip/flops). > 73's de Luis > > mail: melus0(@)teleline(.)es > Ampr: eb7gwl.ampr.org > http://www.terra.es/personal2/melus0/ <- PCBs for Homebrewed Hardware ###### Message-ID: <3A68F01A.6560090E@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.73 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: FSM encoding References: <943gid$9er$1@nnrp1.deja.com> <3A665561.1942031F@andraka.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 49 Date: Sat, 20 Jan 2001 01:52:22 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 979955542 24.13.238.93 (Fri, 19 Jan 2001 17:52:22 PST) NNTP-Posting-Date: Fri, 19 Jan 2001 17:52:22 PST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.direct.ca!look.ca!newshub2.rdc1.sfba.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:4006 If you use the block RAM, it is the same as the old ROM based FSMs. The whole state space is covered, and in the VIrtex devices you have at least 8 address bits to deal with. If one is a muxed input, that leaves you with 128 states plus a control input. Change the BRAM to a handful of 4Kx1's and you get 2048 states plus one control. This ought to cover a large majority of the cases. Note, this is not your father's distribute ram, these are the blcok rams found in virtex and Altera 10 and 20K parts we're talking about in this case. (of course you could use the distributed RAM for smaller FSMs). Luis Yanes wrote: > > On Thu, 18 Jan 2001 02:27:46 GMT Ray Andraka ?ray@andraka.com? wrote: > > ?1) You might use the block rams in the XCV50 for the FSM, it will provide a > ?faster machine, and > ?alot less sensitivity to changes in the state machine definition. I think there > ?may be a > ?xilinx app-note on it. The BRAM is used as a ROM that outputs the next state, > ?plus any decoded outputs > ?as a function of the current (encoded) state and some inputs. If there are many > ?inputs, they can usually > ?be selected by a mux using the current state to reduce the number of address > ?pins needed for the memory. > > This is new way for the old style FSM made with a latch and EPROM as lookup > table that fills the whole possible 'state space'. > > But with the distributed memory in the FPGA aproach there is holes in the > 'state space', what hapens when an illegal state are reached? (due to > noise, bug, etc.). There is a predictable way of recover?. > > I'm asking to implement the DCD DPLL FSM in FPGA I have in EPROM/lach. > ( http://www.terra.es/personal2/melus0/gwlhw0n.html ). > > Sorry if this is a stupid question, I've only done small FSMs. And I know > that when done with independent flip/flops something similar happens. > (A 17 state machine with 16 flip/flops). > 73's de Luis > > mail: melus0(@)teleline(.)es > Ampr: eb7gwl.ampr.org > http://www.terra.es/personal2/melus0/ ?- PCBs for Homebrewed Hardware -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com or http://www.fpga-guru.com ###### Message-ID: <3A68F113.6A597FB4@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.73 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: FSM encoding References: <943gid$9er$1@nnrp1.deja.com> <3A665561.1942031F@andraka.com> <3A688130.FE919325@xilinx.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 77 Date: Sat, 20 Jan 2001 01:56:31 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@home.net X-Trace: news1.wwck1.ri.home.com 979955791 24.13.238.93 (Fri, 19 Jan 2001 17:56:31 PST) NNTP-Posting-Date: Fri, 19 Jan 2001 17:56:31 PST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.direct.ca!look.ca!newshub2.rdc1.sfba.home.com!news.home.com!news1.wwck1.ri.home.com.POSTED!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:4007 Peter Alfke wrote: > > Maybe this is "old hat", but here are my suggestions for a brute-force table-look-up > FSM in Virtex: > > Use the 4K bit RAM, properly initialized during configuration. So it really is a > ROM, since you never write into it. > Use it as 512 x 8 ROM. Feed 5 of the 8 outputs back to the input and use the > remaining 4 inputs as control. > You now have a 32-state FSM with 4 condition inputs, and 3 extra arbitrarily decoded > outputs, beyond the 5 encoded outputs. You can define everything, like recovery from > illegal states, etc. No holes. Peter, If you need more states, you can use a mux to select the appropriate condition input for a given state. In most cases, you can reduce your condition inputs to the ROM to only one or maybe two condition inputs. Additional outputs can be had by installing parallel ROMs for as many decoded outputs as you require. > > In Virtex-II the ROM is bigger, 18K bits. > So you can have a 128-state FSM with 4 control inputs, with the ROMconfigured 2K x > 9. > Or 64 states with 5 control inputs. > > Since these are synchronous dual-ported ROMs, you don't need any extra output or > input registers, and you can run at 200 MHz. Also, you automatically get two FSMs in > the same memory, both with the identical transition table, but individual control > inputs and individual clocking. > > It's all pretty obvious once you think about it... > Peter Alfke, Xilinx Applications > ======================================== > Luis Yanes wrote: > > ? On Thu, 18 Jan 2001 02:27:46 GMT Ray Andraka ?ray@andraka.com? wrote: > ? > ? ?1) You might use the block rams in the XCV50 for the FSM, it will provide a > ? ?faster machine, and > ? ?alot less sensitivity to changes in the state machine definition. I think there > ? ?may be a > ? ?xilinx app-note on it. The BRAM is used as a ROM that outputs the next state, > ? ?plus any decoded outputs > ? ?as a function of the current (encoded) state and some inputs. If there are many > ? ?inputs, they can usually > ? ?be selected by a mux using the current state to reduce the number of address > ? ?pins needed for the memory. > ? > ? This is new way for the old style FSM made with a latch and EPROM as lookup > ? table that fills the whole possible 'state space'. > ? > ? But with the distributed memory in the FPGA aproach there is holes in the > ? 'state space', what hapens when an illegal state are reached? (due to > ? noise, bug, etc.). There is a predictable way of recover?. > ? > ? I'm asking to implement the DCD DPLL FSM in FPGA I have in EPROM/lach. > ? ( http://www.terra.es/personal2/melus0/gwlhw0n.html ). > ? > ? Sorry if this is a stupid question, I've only done small FSMs. And I know > ? that when done with independent flip/flops something similar happens. > ? (A 17 state machine with 16 flip/flops). > ? 73's de Luis > ? > ? mail: melus0(@)teleline(.)es > ? Ampr: eb7gwl.ampr.org > ? http://www.terra.es/personal2/melus0/ ?- PCBs for Homebrewed Hardware -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com or http://www.fpga-guru.com