Custom Search
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Kenneth Porter wrote:
> Ashok Mahadevan <ashokm1@earthlink.net> wrote in
> <3A553937.7FB8DA30@earthlink.net>:
>
> >http://home.earthlink.net/~ashokm1/max7000_isa_bus.htm
>
> Nice web page!
Thank you!.....if only the circuit worked as nicely :o)
> One thing that jumps out at me is that you're using different edges of IOWR
> for different registers. Why? For an active low write signal, one usually
> clocks a register on the rising edge. Your registers at 300, 301, and 303
> are clocking on the falling edge of nIOWR.
Okay, from what I understand about the PC/104 bus, this is how the nIOWRsignal
works with the data bus SD7-SD0:
------------ ------------
nIOWR \ /
----------
-----------------
SDx -------< >-------
-----------------
The signals on the data bus are stable, then the nIOWR signal is asserted
for a period of time, and then brought back high. I can latch the data on
the first falling edge of nIOWR. Am I wrong here?
As to why I am using different edges of nIOWR for the latches, it was the
only way I could get them to latch!. I tried different edges, and this
seemed to work the best. The operation is not consistent however since it
works only on one 74373 latch and not the other. I am doing something
wrong, but am unable to find out what.
> The 245 structure looks ok. Are you running the latest Altera software?
I thought so too, but the warnings from the Compiler and the fact that
the setup does not work unless the 74245 section is disabled leads me to
believe that it is not an accepeted form of implementing a bi-directional
bus interface.
Has anybody implemented a 74245 in an Altera device that they would like
to share with me? I received a reply from another person who had done some
interfacing with the PC/104 bus, but he used an external 74245 chip in his
design.
I am using the student edition 9.23 of the Altera MAX+Plus II software.
This is not the latest (I believe version 10 is), but I think it is
recent enough and in fairly common use.
Thanks for your inputs.....
Ashok
Article: 28301Hello. DLL starts adjusting clock delay before configuration process of the FPGA is completed - your first clock doubler not running still. May be DLL will act correctly, if RST is connected to input pin and DLL resetted after configuration is completed? JaanArticle: 28302
In article <933shl$1h5a$1@node17.cwnet.frontiernet.net>, "Dennis O'Connor" <dmoc@primenet.com> wrote: (snip) > > "Nondeterministic" has nothing to do with randomness. > > A "Nondeterminsitic Finite State Machine" would not chose which > transition out of a state it would take: it takes all of them : that's > the "nondeterminstic" part of it. > (snip) The information that I found on the WWW indicates that only one of the branches is taken, not all of them at the same time. If it took all of the possible branches at the same time, then it would be deterministic, and would end up in multiple states simultaneously. I thought that each NFA set description in the configuration sequence indicates the set of possible states (only one of which is active) at that point in time. -- Greg Neff VP Engineering *Microsym* Computers Inc. greg@guesswhichwordgoeshere.com Sent via Deja.com http://www.deja.com/Article: 28303
Ashok Mahadevan <ashokm1@earthlink.net> wrote in <3A55F0E8.68DB6254@earthlink.net>: >Has anybody implemented a 74245 in an Altera device that they would like >to share with me? I received a reply from another person who had done some >interfacing with the PC/104 bus, but he used an external 74245 chip in his >design. I don't have access to the machine with the software right now, but I know our designs use a 245 to buffer our data bus. >I am using the student edition 9.23 of the Altera MAX+Plus II software. >This is not the latest (I believe version 10 is), but I think it is >recent enough and in fairly common use. I'd go ahead and download the latest (free) stuff from Altera's web site.Article: 28304
George Coulouris wrote: > > In article <934trg$p29$1@nnrp1.deja.com>, Greg Neff wrote: > >In article <933shl$1h5a$1@node17.cwnet.frontiernet.net>, > > "Dennis O'Connor" <dmoc@primenet.com> wrote: > >(snip) > >> > >> "Nondeterministic" has nothing to do with randomness. > >> > >> A "Nondeterminsitic Finite State Machine" would not chose which > >> transition out of a state it would take: it takes all of them : that's > >> the "nondeterminstic" part of it. > >> > >(snip) > > > >The information that I found on the WWW indicates that only one of the > >branches is taken, not all of them at the same time. If it took all of > >the possible branches at the same time, then it would be deterministic, > >and would end up in multiple states simultaneously. I thought that > >each NFA set description in the configuration sequence indicates the > >set of possible states (only one of which is active) at that point in > >time. > [snip] > > If any path puts the NFA in a final state, the input string is accepted. > You can visualize this as the NFA taking all paths simultaneously, or as the > NFA "choosing" the "right" path nondeterministically. Right. That property lets you create machines that accept certain classes of input strings (languages) with fewer states than normal deterministic FSMs, and possibly, I forget, creat machines that accept languages that deterministic FSMs can't distinguish. Now, will somebody please explain to me why NFSMs are worth talking about? I learned about and taught this gorp back in the late 60s. (I certainly wouldn't waste time doing so now.) It was sort of cute theory, not much content that I oculd see, with little to recommend it in practice. Can't say that I see much difference now, and there are lots more interesting things to talk about. Greg Pfister <not my employer's opinion>Article: 28305
NO! There are a few things the automatic placement is exceptionally poor at, with pin placement leading the list, followed by tbuf placement, and data-path placement. You should always specify the pin placement rather than letting the tools do it. Even a bad guess is likely to be better than the random placement generated by the tools, especially if you start itrating a design. See earlier posts in this thread for some guidelines on assigning pins. As for number of pins used, 100% is not a problem...most of the designs I touch have 100% of the pins defined. The only time 100% pin utilization becomes a problem is when you let the tools do the assigning! Jakab Tanko wrote: > > NO, pins are better left to be picked by the place&route tool. > At minimum I think you should put together a dummy design, > if you don't have time for a detailed one, do a quick place and route > and go with that. As for the pins 100% is 20% to many used pins, I > would select a larger device or different package to get more I/O pins. > This is of course just my opinion and I could be wrong, > > jakab > > Mikhail Matusov wrote: > > > Hi all, > > > > Egg-chicken kind of problem. I have to give my board design out to a layout > > person but I haven't yet had chance to start my FPGA work. Usually I do some > > draft FPGA design and run tools at least once to fix the pins before giving > > it out to do a layout but this time the schedule is really tight and if I go > > this route it will be too late. This is not a very demanding design neither > > in terms of complexity nor in terms of speed and I am using Spartan II > > family device. Scary part is that the pins utilization is almost 100%. > > > > Nonetheless, do you guys think that I can get away with pins fixed > > beforehand without too much thought (I put my clocks on global clock lines)? > > > > Thanks in advance, > > > > -- > > ============================ > > Mikhail Matusov > > Hardware Design Engineer > > Square Peg Communications > > Tel.: 1 (613) 271-0044 ext.231 > > Fax: 1 (613) 271-3007 > > http://www.squarepeg.ca -- -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.comArticle: 28306
YOu should be able to simulate if you include the unisim library in a use statement in your code. You may have to put synthesis translate off pragmas around the library reference to keep the synthesizer from going astray. hirsch_yoav@my-deja.com wrote: > > Thanks Ray for the answer. AFAIK I'm using the latest EXEMPLAR revision > (Version: v20001b.106). Unless there is a later revision. I'll try to > instance the SRL16E. Probably it will work, but simulating it in the INNOVEDA > Visual HDL, will be another story. Anyway, I've mailed also to EXEMPLAR > support about this, but no response so far. > > Thanks again, > > Yoav Hirsch > ECI TELECOM. > > 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.comArticle: 28307
Hal, Yes. I just can't say "go ahead" for all of the reasons I stated. Someday, some lot might be just a little too fast (even though it is pretty unlikely). Austin Hal Murray wrote: > [Context is wanting to run a DLL at 24 MHz when the min spec is 25.] > > > Now, I am assuming you are not going below 0C, so there will be some > > margin there. But if not, then definitely don't do it. > > In general, CMOS prop time is linear in temp and supply voltage. He's > only off by 4% so we should be able to draw the forbidden zone on a graph > with voltage on one axis and temp on the other. > > Does that sort of reasoning work with DLLs? > > > Doubling with a delay and an XOR is a common technique, and if you can > > take the delay element and place it off chip, you will not have to worry > > about it getting too fast due to the process/voltage/temperature > > variations in the FPGA. I used to use a small RC off chip that added to > > the delay and made this reliable (used in 100K+ units of a fiber optic > > transmission system). I lived through three process changes of Xilinx > > fpga's with this method, even though it is an asynchronous "no-no". > > I seem to remember an old APP note describing using an XOR for a clock > doubler and promising that the circuit would work. > > I think the trick was to use the clock on a FF that was inside the > clock generation path so the delay was sure to be long enough to clock > a FF on that chip and at that temp/voltage. > > Try this. The clock is the XOR of the input to a FF and it's output > and that clock clocks the FF. Then the pulse width will be whatever > the FF needs to get clocked plus some prop time for roundup. I can't > see any way that wouldn't work. Well, it might not run fast enough, > but that seems unlikely if the reason we are using this hack is > because the clock it too slow for the DLL. But we can check the > min time (worst case) and compare that to the spec sheet. > > I'd call a hack/kludge like this a non-prefered solution rather than a > no-no. The goal is to make designs that work solidly. Mostly, that > means meeting timings and that's obviously easier to check with clean > digital logic - we have tools that do most of the work for us. > > But there are things like metastability so you do have to think about > other issues. As long as there aren't many of them and they are around > the edges we can probably get the whole design right. > > I'll try reasonably hard to avoid things like the XOR doubler, but when > I run out of alternatives AND I think I can convince myself that it will > work reliabily then I'll use them. That convincing frequently involves > taking advantage of temp/voltage tracking to "prove" that the worst > case can't happen when it will hurt you. The reason to avoid them > is not that they don't work, but that it takes time to make sure they > will work. > > I can think of two risks when using a non-prefered technique. > > The first is that I'll overlook something significant. > > The second is that there is a flaw in my reasoning or my arithmetic. > This is the time when it's great to have smart friends who are willing > to look over your design and double check your reasoning. > > I'd probably be more worried about bypassing on the power planes > than something like an XOR clock doubler. > > Also note that the XOR doubler trick doesn't work if the design > needs the DLL to phase lock to the input clock as well as generate > faster clocks. > -- > These are my opinions, not necessarily my employers. I hate spam.Article: 28308
Felix, Try having your design RESET the DLL after the input is stable and running. If the DLL locked before the input was stable, it might have locked to the un-doubled input, Austin felix_bertram@my-deja.com wrote: > Hello everybody, > > first of all I'd like to thank you for your valuable input, > special thanks to Austin and Hal. > > I succeeded creating a 48MHz clock from the 24Mhz, using > an XOR and a FF. I can see the clock with my scope, > it is running at 48Mhz and is approx 4ns high (and 16ns low), > with my XC2S50-TQ144-5C. The signal I probed was CLK2x from > the code below. > > I did not succeed creating a 96MHz clock from the 48MHz > using a DLL. The signal probed at CLK4x is still 48MHz, > however with a duty cycle of 50%. > > I probed the DLL's LOCKED pin- it seems to be high. > > Hal, you wrote: > >>> > Also note that the XOR doubler trick doesn't work if the > design needs the DLL to phase lock to the input clock > as well as generate faster clocks > <<< > > I do not care about the phase of my 96MHz clock, so as > far as I understood things, everything should be fine. > Is there something obvious that I missed? > > Thanks again for your suggestions, > best regards > > Felix Bertram > > ---------------------------------------- > library IEEE; > use IEEE.std_logic_1164.all; > > entity Clk4x is > port( > CLKIN : in STD_LOGIC; -- driven by 24MHz quartz > CLK1x : out STD_LOGIC; -- BUFged CLKIN > CLK2x : out STD_LOGIC; -- 48MHz (small duty cycle) > CLK4x : out STD_LOGIC -- should be 96MHz... > ); > end Clk4x; > > architecture BHV of Clk4x is > > ---- Component declarations ----- > > component bufg > port ( > I : in std_ulogic; > O : out std_ulogic > ); > end component; > > component clkdll > port ( > CLKFB : in std_ulogic := '0'; > CLKIN : in std_ulogic := '0'; > RST : in std_ulogic := '0'; > CLK0 : out std_ulogic := '0'; > CLK180 : out std_ulogic := '0'; > CLK270 : out std_ulogic := '0'; > CLK2X : out std_ulogic := '0'; > CLK90 : out std_ulogic := '0'; > CLKDV : out std_ulogic := '0'; > LOCKED : out std_ulogic := '0' > ); > end component; > > component fd > port ( > C : in std_ulogic; > D : in std_ulogic; > Q : out std_ulogic > ); > end component; > > component inv > port ( > I : in std_ulogic; > O : out std_ulogic > ); > end component; > > component xor2 > port ( > I0 : in std_ulogic; > I1 : in std_ulogic; > O : out std_ulogic > ); > end component; > > ---- User defined diagram declarations ----- > > attribute dont_touch: STRING; > > ---- Constants ----- > constant GND_CONSTANT : STD_LOGIC := '0'; > > ---- Signal declarations used on the diagram ---- > > signal CLK1I : STD_LOGIC; -- 1x clock > signal CLK2I : STD_LOGIC; -- 2x clock > signal CLK4I : STD_LOGIC; -- 4x clock > signal DLLOUT : STD_LOGIC; -- 2x DLL output > signal Q : STD_LOGIC; -- FF Q output > signal QINV : STD_LOGIC; -- ... inverted > > ---- Ground signals declarations ----- > signal GND : STD_LOGIC; > > ---- Instance attributes ---- > > attribute dont_touch of U2 : label is "true"; > attribute dont_touch of U3 : label is "true"; > attribute dont_touch of U4 : label is "true"; > > begin > > ---- Component instantiations ---- > > U1 : bufg > port map( > I => dllout, > O => clk4i > ); > > U2 : xor2 > port map( > I0 => clk1i, > I1 => qinv, > O => clk2i > ); > > U3 : inv > port map( > I => q, > O => qinv > ); > > U4 : fd > port map( > C => clk2i, > D => qinv, > Q => q > ); > > U7 : bufg > port map( > I => CLKIN, > O => clk1i > ); > > U8 : clkdll > port map( > CLK2X => dllout, > CLKFB => clk4i, > CLKIN => clk2i, > RST => GND > ); > > ---- Power , ground assignment ---- > > GND <= GND_CONSTANT; > > ---- Terminal assignment ---- > > CLK1x <= clk1i; > CLK2x <= clk2i; > CLK4x <= clk4i; > > end BHV; > ---------------------------------------- > > Sent via Deja.com > http://www.deja.com/Article: 28309
In article <934trg$p29$1@nnrp1.deja.com>, Greg Neff wrote: >In article <933shl$1h5a$1@node17.cwnet.frontiernet.net>, > "Dennis O'Connor" <dmoc@primenet.com> wrote: >(snip) >> >> "Nondeterministic" has nothing to do with randomness. >> >> A "Nondeterminsitic Finite State Machine" would not chose which >> transition out of a state it would take: it takes all of them : that's >> the "nondeterminstic" part of it. >> >(snip) > >The information that I found on the WWW indicates that only one of the >branches is taken, not all of them at the same time. If it took all of >the possible branches at the same time, then it would be deterministic, >and would end up in multiple states simultaneously. I thought that >each NFA set description in the configuration sequence indicates the >set of possible states (only one of which is active) at that point in >time. [snip] If any path puts the NFA in a final state, the input string is accepted. You can visualize this as the NFA taking all paths simultaneously, or as the NFA "choosing" the "right" path nondeterministically. "It's only a model" -- Patsy -- George Coulouris - http://www.tc.cornell.edu/~glc5/Article: 28310
Hi Anthony - What is the exact error message that you are seeing? Obviously location constraints are supported and shouldn't be causing you so much grief. ArthurArticle: 28311
In article <9354to$dde$1@news01.cit.cornell.edu>, glc5@cornell.edu wrote: (snip) > > If any path puts the NFA in a final state, the input string is accepted. > You can visualize this as the NFA taking all paths simultaneously, or as the > NFA "choosing" the "right" path nondeterministically. > (snip) Okay, so if I had to implement this in hardware (as requested by the OP) then I can see two different approaches: 1) Follow all paths simultaneously. This is completely deterministic from an implementation perspective. In this case, multiple states can be active at the same time, and the final state *will* be active if the input string is acceptable. From a hardware perspective this is trivial, so I don't know why the OP would need assistance in implementing this. 2) Non-deterministically pick one path when more than one path is possible from each state. In this case, only one state will be active at any given point in time, and the final state *may* be active if the input string is acceptable. I'm thinking that this is what the OP was asking about, but I'm not sure. -- Greg Neff VP Engineering *Microsym* Computers Inc. greg@guesswhichwordgoeshere.com Sent via Deja.com http://www.deja.com/Article: 28312
Yes,No,Maybe, If you assign 100% the I/O pins that is plain bad design practice in my opinion, just consider what happens if you need an extra pin afterwards; As for the automatic pin placement it works fine except when you have one of those designs "from hell" (about 5% of all designs) that require extensive floor planing just to get the thing to work. In that case the wrong part was selected for the application or your project deadlines are different from mine because I never have time for doing the job of the P&R tool ....... Ray Andraka wrote: > NO! > > There are a few things the automatic placement is exceptionally poor at, with > pin placement leading the list, followed by tbuf placement, and data-path > placement. You should always specify the pin placement rather than letting the > tools do it. Even a bad guess is likely to be better than the random placement > generated by the tools, especially if you start itrating a design. See earlier > posts in this thread for some guidelines on assigning pins. > > As for number of pins used, 100% is not a problem...most of the designs I touch > have 100% of the pins defined. The only time 100% pin utilization becomes a > problem is when you let the tools do the assigning! > > Jakab Tanko wrote: > >> NO, pins are better left to be picked by the place&route tool. >> At minimum I think you should put together a dummy design, >> if you don't have time for a detailed one, do a quick place and route >> and go with that. As for the pins 100% is 20% to many used pins, I >> would select a larger device or different package to get more I/O pins. >> This is of course just my opinion and I could be wrong, >> >> jakab >> >> Mikhail Matusov wrote: >> >>> Hi all, >>> >>> Egg-chicken kind of problem. I have to give my board design out to a layout >>> person but I haven't yet had chance to start my FPGA work. Usually I do some >>> draft FPGA design and run tools at least once to fix the pins before giving >>> it out to do a layout but this time the schedule is really tight and if I go >>> this route it will be too late. This is not a very demanding design neither >>> in terms of complexity nor in terms of speed and I am using Spartan II >>> family device. Scary part is that the pins utilization is almost 100%. >>> >>> Nonetheless, do you guys think that I can get away with pins fixed >>> beforehand without too much thought (I put my clocks on global clock lines)? >>> >>> Thanks in advance, >>> >>> -- >>> ============================ >>> Mikhail Matusov >>> Hardware Design Engineer >>> Square Peg Communications >>> Tel.: 1 (613) 271-0044 ext.231 >>> Fax: 1 (613) 271-3007 >>> http://www.squarepeg.ca >>Article: 28313
I agree with Ray. Ray isn't telling anyone to use 100% of the pins, or
to *not* provide for any spare/unused pins, or to use 100% of the
CLBs/PFUs/LCs... he *is* saying it's a good idea to lock down all pins,
used and unused/spare pins alike. So Jakab, you're right, and Ray's
not wrong... (did I say that correctly?)
The compiler (placement tool) is completely ignorant of the board-level
layout or electrical considerations. The designer needs to provide that
intelligence.
Every "unused" pin should be declared, locked down, and represented on any
board-level schematic. In essence, there are no "unused" pins, just "spare"
pins that don't yet have a function assigned to them.
On many "new" designs, there will be *some* use made of some of the spare
pins. Designers are, sadly, all too human. So while we're specifying pinout
of all the "used" pins, depending upon the package being used, it is a good
idea to
A. route some spare pins to square pins or vias, for either probing or
hookup of new signals
and/or
B. assign some of those spare pins to corner pins (e.g. pins 1,52,53,...208
of a PQ208) so that soldering 30AWG wire to the pins by the board
assembler has a chance of success.
I do not apologize for specifying the pinout before the FPGA is fully
implemented, getting the board into layout, and then finishing the FPGA
implementation while the layout/fab/assembly is proceeding. It takes some
experience (and learning the hard way) to do this and come out smelling
like a rose, but that's why we get paid the big bucks. It also helps to
oversize the FPGA, using a footprint-compatible device, but that just buys
gates and routing resources, not extra pins.
So, Ray is right. Jakab is correct that using 100% of all the useable
pins is a risky business, but that doesn't contradict what Ray is
suggesting, in the slightest. Ray is recommending that all pinouts should
be specified by the designer (not the compiler), including the spare pins.
Ray *isn't* saying that there shouldn't be any spare pins.
Beating another trivial matter to death is what I do best...
Bob Elkind, eteam@aracnet.com
Jakab Tanko wrote:
>
> Yes,No,Maybe,
>
> If you assign 100% the I/O pins that is plain bad design practice in my
> opinion,
> just consider what happens if you need an extra pin afterwards;
> As for the automatic pin placement it works fine except when you have
> one of those designs
> "from hell" (about 5% of all designs) that require extensive floor
> planing just to get the thing
> to work. In that case the wrong part was selected for the application or
> your project
> deadlines are different from mine because I never have time for doing
> the job of the
> P&R tool .......
>
> Ray Andraka wrote:
>
> > NO!
> >
> > There are a few things the automatic placement is exceptionally poor at, with
> > pin placement leading the list, followed by tbuf placement, and data-path
> > placement. You should always specify the pin placement rather than letting the
> > tools do it. Even a bad guess is likely to be better than the random placement
> > generated by the tools, especially if you start itrating a design. See earlier
> > posts in this thread for some guidelines on assigning pins.
> >
<snip>
Article: 28314Del Cecchi wrote: > Yes, quite informative (what I understood of it), but disappointing. I thought we > would get to make state machines with little white noise generators in them to > aid in the control of the state transitions. :-) You could synthesize the NFA, and use Q-bits instead of flip-flops to hold the states. According to the theory of quantum computers, you should have an efficient hardware implementation of a NFA (i.e. you need just log2(n) Q-bits, even if the corresponding DFA requires 2^n states, and therefore at least n Flip-Flops). The labs at IBM seem to have produced some Q-bits lately. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://www.jwdt.com/~paysan/Article: 28315
Greg Pfister <pfister@us.ibm.com> writes: > Right. That property lets you create machines that accept certain > classes of input strings (languages) with fewer states than > normal deterministic FSMs, and possibly, I forget, creat machines > that accept languages that deterministic FSMs can't distinguish. > > Now, will somebody please explain to me why NFSMs are worth > talking about? I learned about and taught this gorp back in the > late 60s. (I certainly wouldn't waste time doing so now.) It was > sort of cute theory, not much content that I oculd see, with > little to recommend it in practice. Can't say that I see much > difference now, and there are lots more interesting things to > talk about. I'm not Mr. Hardware, but it occurs to me that there might be some use for networking gear - switches, routers, maybe firewalls. If I can add new MACs or IPs to a NFA instead of a flat table that I have to iterate through, it could be a speedup. Maybe CAMs make this moot, though. KellyArticle: 28316
> Try having your design RESET the DLL after the input is stable and > running. > > If the DLL locked before the input was stable, it might have locked to > the un-doubled input, That gatcha is covered in the Xilinx App Note on DLLs. -- These are my opinions, not necessarily my employers. I hate spam.Article: 28317
Hi all Thanks for all the feedback. I hope the following answers at least some of your questions. First of all, I use "nondeterministic" in the classical theory of computer science sense. It has nothing to do with white noise or probabilistic transitions. Below I elaborate on the "interesting" in my approach. It has to do with the structure as well as method of FSM construction. 1. Structure of the constructed FSM The idea is to extend the standard one-hot encoding (OHE) technique of implementing deterministic FSMs where one flip-flop is used per state and exactly one flip-flop stores a 1 at any time. The extension is to allow multiple flip-flops to store 1 with multiple state transitions every clock cycle thereby implementing a nondeterministic FSM. Not earth shattering at all I admit but I've not seen it done and I've searched a lot. Some of you pointed out that it has been done and I stand corrected. I would appreciate it if you could also point out any references to such work. It would help a lot. 2. Method of FSM construction The FSM needs to be built really fast (micro second range) for online applications. If used for text searching for example, the user won't be happy if the placed and routed FSM is blazingly fast but it takes minutes to place and route the FSM in the first place. The clock starts ticking the moment the user enters the regular expression. I have done some work on fast deterministic FSM construction using "self-reconfiguration". Essentially, it is proposed that the FPGA itself specializes the FSM template at runtime based on input text by generating appropriate config bits and using them to configure itself (if interested please see http://maarc.usc.edu/sidhu_fpga99.ps). I'm working on extending this by developing a simple, fast algorithm for nondeterministic FSM construction. Again, I would appreciate any feedback on fast algorithms for construction of nondeterministic FSMs. RegardsArticle: 28318
Greg Pfister <pfister@us.ibm.com> writes: > Now, will somebody please explain to me why NFSMs are worth > talking about? I learned about and taught this gorp back in the > late 60s. (I certainly wouldn't waste time doing so now.) It was > sort of cute theory, not much content that I oculd see, with > little to recommend it in practice. Can't say that I see much > difference now, and there are lots more interesting things to > talk about. Because regular expressions are (most of the time) the most straightforward way of describing the set you want to recognize (assuming a FSM can do it at all), and REs translate easily to NFSMs. Then you use a NFSM -> DFSM construction to get something executable. Also, of coures, it's intuitively obvious that NFSMs *have* to be more powerful than DFSMs, so the fact that the construction is so easy makes a good warmup for hitting the same fact later in Turing Machines. -- Joseph J. Pfeiffer, Jr., Ph.D. Phone -- (505) 646-1605 Department of Computer Science FAX -- (505) 646-1002 New Mexico State University http://www.cs.nmsu.edu/~pfeiffer VL 2000 Homepage: http://www.cs.orst.edu/~burnett/vl2000/Article: 28319
Greg Neff <gregneff@my-deja.com> writes: > Okay, so if I had to implement this in hardware (as requested by the OP) > then I can see two different approaches: > > 1) Follow all paths simultaneously. This is completely deterministic > from an implementation perspective. In this case, multiple states can > be active at the same time, and the final state *will* be active if the > input string is acceptable. From a hardware perspective this is > trivial, so I don't know why the OP would need assistance in > implementing this. This has to be what he meant. The thing is, a naive translation from NFSM to DFSM takes 2^N states, where N is the number of states in the NFSM. There are ways to reduce the number of states, but I don't know if there is any sort of proved optimum, in general. The OP's point was that he was looking for efficient representation. > > 2) Non-deterministically pick one path when more than one path is > possible from each state. In this case, only one state will be active > at any given point in time, and the final state *may* be active if the > input string is acceptable. I'm thinking that this is what the OP was > asking about, but I'm not sure. Unless the OP is using words in nonstandard ways, this just isn't possible. You see, it's not just that the automaton makes a choice, it always makes the *right* choice, based on information it doesn't have yet. Can't do that, sorry! -- Joseph J. Pfeiffer, Jr., Ph.D. Phone -- (505) 646-1605 Department of Computer Science FAX -- (505) 646-1002 New Mexico State University http://www.cs.nmsu.edu/~pfeiffer VL 2000 Homepage: http://www.cs.orst.edu/~burnett/vl2000/Article: 28320
now i've got the driver for the my ethernet card for Redhat 5.2
installed in my pc. (i know this version is.....)
The guidance for gettn the driver run and connect the pc to the internet
is as follows:
*****************************************************************************
*
*
* 32-Bit PCI Fast Ethernet Adapter
*
*
*
* Driver Installation for LINUX
*
*
*
*****************************************************************************
Below are the instructions for installing linux driver. You must complie the
source code to generate rtl8139.o and use "insmod" to insert rtl8139.o
as module.
You can use "netconfig" utilities to setup network parameters for the
driver.
Files Description:
==================
rtl8139.c The adapter source code. You can download the newest version from
http://cesdis.gsfc.nasa.gov/linux/drivers/rtl8139.html or
ftp://cesdis.gsfc.nasa.gov/pub/linux/drivers/rtl8139.c
trans Compile batch file.
linux.txt This file.
Installation:
=============
1. Plug 32-Bit PCI Fast Ethernet Adapter into PC's PCI-bus slot.
2. Boot into LINUX and keyin the following commands at the LINUX prompt.
Remember, LINUX is case sensitive.
mkdir /temp
mcopy a:/linux/rtl8139.c /temp
mcopy a:/linux/trans /temp
cd /temp
chmod 777 trans
3. Run trans file to complie and copy driver to linux source code:
/temp/trans
(rtl8139.o will be generated and be copied to /usr/src/linux/modules.)
4. Run netconfig (or netcfg) to set you network parameter (like ip,
gateway).
Slackware: Run "netconfig" to configure IP environment.
This will create '/etc/rc.d/rc.inet1' and 'rc.inet2' files.
netconfig
RedHat:
- Add "alias eth0 rtl8139" into the /etc/conf.modules file.
cd /etc
vi conf.modules
alias eth0 rtl8139
- Run "netcfg" in the xterm of X-window to configure IP environment.
startx
netcfg
(Configure IP of eth0 and enable "Activate interface at boot time".)
5. Use editor vi to modify 'rc.inet1'(or 'rc') in the /etc/rc.d directory to
insmod driver. This file will be run at boot time. You just add a line
at the beginning of 'rc.inet1'(or 'rc').
Slackware:
cd /etc/rc.d
vi rc.inet1
insmod /usr/src/linux/modules/rtl8139.o
RedHat: Add a line at the beginning of 'rc' file.
cd /etc/rc.d
vi rc
insmod /usr/src/linux/modules/rtl8139.o
6. Reboot the LINUX.
reboot ( or shutdown -r now )
When system boots, the driver will be loaded. Then the driver will
scan I/O port to see if a card is there.
(You can run 'dmesg' to see the boot message.)
7. Run 'ifconfig' or 'netstat -i' to see if there is a interface 'eth0'.
**********************************8
Questions:
a)
i've done step 1 & 2, when it comes to step number 3 -- /temp/trans
--- i got unsure cos after i key in
as root:
cd /temp
trans
it display "bad command or file name" -- kindly advise which command
code i should enter to execute "trans"??? pls help so that the .c file
could be compiled successfully. :-D
b) and what is "chmod 777" actually??
pls help.......tx in advance.
chilli ???????????
Sent via Deja.com
http://www.deja.com/
Article: 28321Hi all. I've created timing loops in my design. I've done that and got rid of them before, but these are more tricky. Timing loops are combinatorial paths, right? No clocks in it. Like two combinatorial blocks triggering eachother? I'm still trying to understand exactly *what* they are. Anyway: When I simulate the design previous timing loops caused the simulator to enter an infinite loop. This time they didn't, though. No sign at all. But when synthesizing - trying to - with synopsys, I tell it to compile the design(I don't have the scripts nearby right now. If some kind soul could help me with this I'll get the exact parameters). Synopsys then says 'allocating blocks for...', and when it does that for two of my submodules the hated 'Warning:Timing loop detected' pops up(and then 'disabling timing arc between cell x and y' a couple of times). I guess that means the timing loop(s) are in the submodules, right? But they are a simple counter and shift register(both clocked!)! Can there still be timing loops, or have I missed some fundamentals?? I tried to follow the signals in/out of these two modules one level up in the hierarchy. Some of them trigger other combinatorial blocks, but I can't see *loops* anywhere. One message from synopsys was 'Disabling timing arc between *cell*...U162.../DATA4_O and *cell*...U162.../Z_O'. Turning to design_analyzer I found a cell(a clb in the xc4062 that I'm targeting) called U162, but none of the pins/nets connected are even close to DATA4 or Z! So I don't have much of a clue how to locate these loops. Is there a timing analysis or anything where I can see timing loops? /TIA, TorbjörnArticle: 28322
> Hi, > I want to start with FPGA design. > I will appreciate any suggestions for good starter kit. > > Val Val, There's a list of boards at http://www.optimagic.com/boards.html It is a little out of date at this time, but it lists many companies of interest. Of course, I highly recommend the Burch Electronic Designs FPGA proto kits (because I sell these, so I am biassed :)). See http://www.burched.com.au/ The BED-SPARTAN2+ kits are hot at the moment: - 200,000 gates! - free Xilinx Webpack software CD included - introductory price US$120! Great for some serious prototyping, or for education. See http://www.burched.com.au/bedspartan2.html for full specs and secure online shop. You may also wish to check out the Plug-On modules. (SRAM, FPGA-CPU-IO, 7SEG-DISPLAYS, DIPSWITCH). http://www.burched.com.au/products.html International orders are welcome. Best regards Tony Burch http://www.burched.com.au/Article: 28323
Hi, Does anyone know what devices are supported by the free Altera development software? It is not clear on the Altera web pages, and I would know it before download a lot of MBytes. I'm specially interested in FLEX 8000 family. Thanks! LuigiArticle: 28324
I like this idea, and its practical applications -- and it seems novel to
me. One can be blinded by conventional wisdom -- I thought the best
(fastest) way to run an NFA in hardware is to convert it to a DFA (provided
the NFA is such that you don't suffer from exponential DFA size). (Hence
www.fpgacpu.org/usenet/re.html.) That may be so when you're stuck running
it in a conventional general purpose processor, but not so when you can make
'multiple hot' state machines in programmable logic.
A question is -- with this new perspective (direct implementation of NFAs),
is it better (faster) to build an NFA from the DFA and run that, or to run
the NFA directly. (Assuming the DFA doesn't blow up (the exponential set of
all subsets scenarios).) This is an interesting problem!
Here are some thoughts.
1. If the only measure of quality is machine construction time, let's look
at that:
Tfsm = Tprep + Treconfig
e.g. the time to build the machine is the sum of the time to figure out what
to build plus the time to reconfigure the hardware to implement it.
One easy DFA implementation is to use binary encoded states and inputs, and
use a RAM next-state lookup table for state transitions. Assuming 64 input
character classes and 64 states, you would need a 6-bit state, and a 2^(6+6)
x 6-bit table (6 block RAMs). Assuming 64 input classes and just 16 states,
you would need only a single block RAM configured as 2^(6+4)x4. Either way,
the FSM would run at well north of 100 MHz.
Here it would appear Tprep is expensive -- the subset construction can be
time consuming -- but Treconfig is is merely blasting a state transition
table into one or more block RAMs. Exploring this idea would give you a
benchmark against which to measure the NFA idea.
(Hey Xilinx/Altera -- a block RAM control to zero an entire block RAM or
'quadrant' thereof might have some applications...)
2. Thank you for identifying a good application of a small 100 MHz embedded
soft core CPU. Converting REs to NFAs to DFAs is an ideal small memory
footprint job for an embedded CPU running out of embedded block RAM.
If you use a soft CPU variant which uses just one port of the dual port
block RAM for its data (and perhaps its instruction) accesses, the other
port can be used for the DFA engine itself to run. So there need not be any
copying of the DFA next-state table after it is constructed.
3. For the suggested NFA implementation (multiply hot state machines), each
state flip-flop latches a sum of products of the current input and other
states. For example, state[1] is set if state[2] is set and input is in
{some subset of input values} or if state[1] is set and input is in {some
other subset} etc. In the worst case, this is densely populated, e.g.
state[i] is set if many other states see this input. You can also refactor
this. For example, for a given input or input value, set state[i] if one of
{some subset of states} is set.
I wonder if it is possible to employ a fixed interconnect scheme that routes
the state vector (multiple hot) and the input vector (one hot or binary
encoded) to some writeable-LUT sum-of-products structure at each state FF,
and then only reconfigure the 'sum of products' coefficients in the LUTs
themselves.
4. Software regexp packages have explored all corners of this space --
execute the NFA (with backtracking), build a DFA, hybrids, etc. Maybe
there's some ideas in there about building NFAs efficiently.
5. This multiple hot idea may suggest a novel (but probably bad) *software*
implementation of regexp, e.g. execute the NFA (sans backtracking) --
combine the idea of converting an RE to an NFA and implementing *that* with
a multiply-hot state machine, with the ideas in
www.fpgacpu.org/usenet/emulating_fpgas.html for fast software emulation of
programmable logic in general purpose CPUs, using bit-twiddling tricks. (I
wonder if I can figure out a way to build the routing fabric lookup tables
quickly.) Hmm.
> Again, I would appreciate any feedback on fast algorithms for construction
of nondeterministic FSMs.
What do you mean by construction? Do you mean mapping the RE into an FSM?
Do you mean data structures for representing the FSM?
I look forward to reading more about this fascinating idea.
Jan Gray, Gray Research LLC
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z