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
Hi All,
I have searched long enough now with no luck, this should be trivial
for someone:
In the LUT4 instantiation below, what value should the LUT4 be
INITialized to in order to implement a 2-input MUX, with the inputs on
I0 and I1?
i_lut4 : LUT4 generic map( INIT => x"????")
port map(I0 => input1, I1 => input2, I2 => select, I3 => '0',
O => output);
Can someone please point me to a reference on how to calculate any INIT
value for any 4-input logic function.
Cheers,
Peter.
Article: 104926I don't understand the question. What does "perform" mean? Obviously not the response to the reset signal, which differs so dramatically that it cannot even be compared. So is it clock-to-Q or set-up time or hold time? Remember, in an FPGA you get a pre-designed flip-flop with well-documented worst-case performance parameters. So what is the intent of the question? Peter Alfke, Xilinx (from home) =============== Stanley Lee wrote: > Hi, all: > The FFs can be reset synchronously or asynchronously. And in ASIC > design, the FFs with asynchronous reset will be "smaller". But in FPGA > design, will the FFs with asynchronous reset perform better than the > ones with synchronous reset? Or, is the kind of reset just an "option" > for the FFs instantiated?Article: 104927
PeterC schrieb: > Hi All, > > I have searched long enough now with no luck, this should be trivial > for someone: > > In the LUT4 instantiation below, what value should the LUT4 be > INITialized to in order to implement a 2-input MUX, with the inputs on > I0 and I1? > > i_lut4 : LUT4 generic map( INIT => x"????") > port map(I0 => input1, I1 => input2, I2 => select, I3 => '0', > O => output); > > Can someone please point me to a reference on how to calculate any INIT > value for any 4-input logic function. > > Cheers, > Peter. think of the LUT as 16x1 bit RAM I0=ADDR0 I1=ADDR1 ... for 2:1 mux RAM values should be 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 so you get INIT=CACA what happens to be the correct value as much as I recall from memory Antti http://antti-brain.comArticle: 104928
Rob schrieb: > I didn't think that was the problem, but I thought I would throw it out > there. Bizarre problem indeed. Please post when you find the answer. > > "Antti" <Antti.Lukats@xilant.com> wrote in message > news:1152471480.276262.151590@35g2000cwc.googlegroups.com... > > Rob schrieb: [snip] > > 3) using the same bitstream and impact with configure, but no verify > > then first configuration attempts says configure error (CRC error) and > > after that the JTAG chain is reported as broken before the FPGA. The > > power supplies are still proper Voltage and stable and the FPGA does > > not get hot. But it needs to be power cycled for the JTAG TAP to come > > live again. > > > > I understand that power supply is the most likely issue but why doesnt > > the issue never happen when jtag operation is set to > > configure_and_verify? and locks up the jtag tap 100% when attempting to > > configure without verify? > > > > I bet this remains "Xilinx mystery" forever. > > > > Antti > > mystery solved ! The issue is the bug in ARM core netlist that is licensed by Atmel for the AT91SAM7S! The problem was in no way related to any issues with Xilinx FPGA or power supplies despite the weird 'Effect' that the issue was only visible whith one specific FPGA design and only with impact and only when configuration attempt was done with verify OFF setting. When the AT91SAM7S has PLL enabled the issue with the same 'bad' bitstream doesnt occour anymore. AnttiArticle: 104929
In the 1990s I used a Xilinx-only version of DOS Viewlogic, version 4 I think. Viewlogic was hacked so that schematic files created in the unrestricted version could not be opened in the restricted version(s). However, somebody developed a program called sneaky.exe which patched the schematic file, to enable it to be opened. I have been chucking out a large quantity of 5.25" disks with all sorts of stuff on them, and came across this. It is on a 360k disk which I can't read anymore (I can read 1.2MB ones) so if anybody wants this drop me an email with your mailing address. I recall it is a very small file, a few k. I also have cracks for those old versions of Viewlogic (Viewdraw), developed by some Russian programmer. These eliminate the Xilinx dongle. I know this worked on the Xilinx version of Viewdraw/Viewsim. I also have a crack for the old Xilinx XACT 6 program, which also worked. I have the manuals for it all, XACT (DS502) and also Alliance 1.3 and 1.4 (whatever they are) plus all the original dongles - all legitimate. But for that I would need a UPS or DHL account number to send it to - it's heavy. I am in the UK. I am getting rid off all this stuff and would like to give it a good home. FPGAs have moved on, technology has moved on, and I can't see myself ever getting into any of this stuff again. More to the point, I no longer have any need to open any of the designs I did 10-15 years ago. To run it properly one needs a DOS 6.2 PC with an 8514-emulating video card; e.g. an ATI Graphics Ultra Pro PCI card. Then you end up with a super schematic capture and digital simulation (Xilinx only) machine. email petexrh337@yahooxz.co.uk but remove the two "x" chars and the one "z" charArticle: 104930
Austin Lesea wrote: > Anti, > > All devices after Virtex E (Sparta 2E) have no extra current required > over that which is specified in the data sheet for minimum power on > current. > > Is it possible that the configuration you are loading requires more > power than you have available? > > I have seen DONE go high, only for the power supply to crash, fold back, > and the part starts to reconfigure again. > > As for the JTAG state machine, it is definitely possible for it to enter > a "bad" state from which it may never recover. It is only with Virtex > 4, and now Virtex 5, that we have worked carefully on the state machines > to harden them from soft errors, which might place them in an > unrecoverable state. Irradiation with neutrons can quickly find those > hidden bad states! > I am surprised there: I thought the JTAG standard had defined that state machine so that a limited number (5, by memory) of clocks with TMS=1 would force it out of anything.Article: 104931
"Zara" <dlm0-hbge@dea.spamcon.org> wrote in message news:9bn3b2tldn7odl44uegsabrfvc4jrpmdoh@4ax.com... > On Sat, 08 Jul 2006 21:36:22 -0000, gavin@allegro.com (Gavin Scott) > wrote: > >>So I've been on the mailing list for Xilinx's Xcell Journal glossy >>magazine for a year or two now, and something I've noticed is that >>EVERY issue I've received is trashed to one degree or another. The >>covers are torn, the corners crushed or completely folded over, etc. >> >> >>G. > > I receive my copy on Spain with no damage at all. I would blame your > postal service or postal office. > > Z. Guys, How quaint! Here in the UK we have this newfangled thing called 'the World Wide Web'. (From the name, I'd guess other countries may also have this?) It's very useful: I get every copy of Xcell in pristine condition from something Xilinx call their 'website'. HTH, Syms. ;-) p.s. Soz for the sarcasm; couldn't resist!Article: 104932
"Peter" <peter@peter2000.co.uk> wrote in message news:lr64b2t15fen9gf1n1pq33lbhh6krc4aie@4ax.com... > > I also have cracks for those old versions of Viewlogic (Viewdraw), > developed by some Russian programmer. These eliminate the Xilinx > dongle. I know this worked on the Xilinx version of Viewdraw/Viewsim. > I also have a crack for the old Xilinx XACT 6 program, which also > worked. > Hi Peter, You post reminded me of the old Xilinx dongle. It was a counter which changed state after getting 163 (or something like that) clock edges. I know someone who made one using a XC3020, just for irony's sake! Cheers, Syms.Article: 104933
David R Brooks schrieb: > Austin Lesea wrote: > > Anti, > > > > All devices after Virtex E (Sparta 2E) have no extra current required > > over that which is specified in the data sheet for minimum power on > > current. > > > > Is it possible that the configuration you are loading requires more > > power than you have available? > > > > I have seen DONE go high, only for the power supply to crash, fold back, > > and the part starts to reconfigure again. > > > > As for the JTAG state machine, it is definitely possible for it to enter > > a "bad" state from which it may never recover. It is only with Virtex > > 4, and now Virtex 5, that we have worked carefully on the state machines > > to harden them from soft errors, which might place them in an > > unrecoverable state. Irradiation with neutrons can quickly find those > > hidden bad states! > > > I am surprised there: I thought the JTAG standard had defined that state > machine so that a limited number (5, by memory) of clocks with TMS=1 > would force it out of anything. Hi David, yes you are correct - 5 times TCK when TMS=1 *MUST* transit to TLR state. but the issue was max TCK frequency that another JTAG device in the chain was able to handle. It happened to be 100KHz what should have make all JTAG comms to fail, but unfortunatly did not. Eg the 'BAD JTAG' device operated "good enough" in order not to disturb other devices unless some sequence that was dependant on the bitstream loaded to FPGA made it really upset. As I did not see any problems with several design I wrongly assumed the 'slow max TCK' device was working properly at TCK=200KHz (Impact Cable III) when the only command sent to it was BYPASS. This wasnt the case. A bitter experience - did cost me several hours wasted with uneneccary troubleshooting. So beware - if the JTAG chain includes devices with ARM core, then make sure the ARM clock is running at desired frequency in order for the JTAG to work properly. I think some newer ARM cores have that bug fixed, but there are several ARM licensors still using the Buggy ARM IP. AnttiArticle: 104934
"Stanley Lee" <lizhongqi@hotmail.com> wrote in message news:1152502503.121149.84260@m73g2000cwd.googlegroups.com... > But in FPGA > design, will the FFs with asynchronous reset perform better than the > ones with synchronous reset? Or, is the kind of reset just an "option" > for the FFs instantiated? > 'Better' I'm assuming to mean clock performance. If that's the case, then from what I've seen performance is not usually affected. Mike Tressler has also captured some performance numbers with a single design using various tools targetting a couple different devices (see link below, then click on 'Reference Design Source' and scroll down to the bottom). He has a bit of a problem in his methodology of obtaining the performance numbers but even there it seems to be a mixed bag as to whether synchronous or asynchronous is better. The important thing though is that it is attempting to fairly measure different techniques. http://home.comcast.net/~mike_treseler/ A lot of times, the logic preceeding a flip flop inside an FPGA can accomodate an extra input (i.e. reset) without impacing performance in any way simply because the final LUT has an otherwise unused input. In those cases, sync performance would be the same as async. On the other hand if there were no spare inputs into the final LUT (and nowhere upstream where it could be added either) than an extra level of logic would be required which would impact performance. On the async side, you're basically chewing up a routing resource and dedicating it exclusively to resetting flip flops. Generally this will tend to happen on some global routing resource so it won't much matter but other times that is not the case and it will impact performance for selected flops. From the perspective of timing analysis, since the reset input almost always needs to be synchronized to the clock(s) anyway (unless the clock is guaranteed to not be running at the conclusion of reset) then now you have the situation where the output of a flip flop can occur at two distinct times: one being the clock to output delay of the flop, the second being the reset to output delay of the flop....presumably the timing analysis software analyzes both paths. Over the years, I've also noticed that designers who perfer to use async resets tend to misuse them more than those who use sync resets. Misuse meaning not syncing reset up to the appropriate clock or not paying careful attention to how it is routed on a printed circuit board and picking up noise that resets things, or forgetting about the timing path through the flop in response to this reset signal (again from a board design perspective, inside an FPGA the timing analysis software 'should' know this). Since a designer can misuse a sync reset almost as easily, I'm not really sure why I've noticed this trend but I have. Even from the perspective of just writing the code, using async method and the generally used template presents some challenges that in certain cases can result in gated clocks being generated. The 'certain cases' being if you have a single VHDL process where some of the outputs are asynchronously resetable and other outputs are not. Peruse the comp.lang.vhdl discussion titled 'alternate synchronous process template' (starting on June 15, 2006) for more. The generally used template for synchronous resets does not have this problem. In most cases, there is no actual functional performance reason for using async or sync so either can be used. Some will argue that if there is no clock then you must use async but that is not really true...'specially when you remember that you'll probably have some form of shift register for synchronizing reset to the clock anyway. Then you can have the shift register be async resetable but the entire rest of the design be sync reset. Again, in that same comp.lang.vhdl thread you can read some back and forth about using one versus the other. Bottom line from what I've seen over the years is that in FPGAs, as a general rule it doesn't much matter. In a specific instance it might...but which way will be better in that specific instance is a coin toss. KJArticle: 104935
On 10 Jul 2006 11:48:22 +0200, "Symon" <symon_brewer@hotmail.com> wrote: >"Zara" <dlm0-hbge@dea.spamcon.org> wrote in message >news:9bn3b2tldn7odl44uegsabrfvc4jrpmdoh@4ax.com... >> On Sat, 08 Jul 2006 21:36:22 -0000, gavin@allegro.com (Gavin Scott) >> wrote: >> >>>So I've been on the mailing list for Xilinx's Xcell Journal glossy >>>magazine for a year or two now, and something I've noticed is that >>>EVERY issue I've received is trashed to one degree or another. The >>>covers are torn, the corners crushed or completely folded over, etc. >>> >>> >>>G. >> >> I receive my copy on Spain with no damage at all. I would blame your >> postal service or postal office. >> >> Z. > >Guys, >How quaint! Here in the UK we have this newfangled thing called 'the World >Wide Web'. (From the name, I'd guess other countries may also have this?) >It's very useful: I get every copy of Xcell in pristine condition from >something Xilinx call their 'website'. >HTH, Syms. ;-) >p.s. Soz for the sarcasm; couldn't resist! > Here we also have Internet, very useful to look at chicks in the screeen and not to work. Or so it seems some bosses think. It is better to receive magazines in paper, soas to read them and appear to be working when you are relaxing ;-) regards Z.Article: 104936
Hal Murray wrote: > >AH! We have the first condition for chaotic behaviour, sensitivity to > >initial conditions... When the input is near the balance point, the > >slightest difference will determine whether the output goes positive or > >negative. That is a very significant aspect of the circuit. > > When I think of chaos, I think of hard to predict systems. The classic > example is the earth's weather pattern. We think we can analyze the > local details but we can't predict anything long term. > > In the case of metastability, the system eventually stabilizes at > a 1 or 0. That's two possible states rather than zillions. > > Is it called "chaotic" if I can't predict when it will stabilize? I am looking for the possiblity that a FF Can be chaotic. I don't know the formal definition of chaotic so I don't know how to tell if a FF can behave chaotically or not. At least I didn't when I started this thread. I think that a chaotic system has to not settle and it seems clear at this point that the CMOS FF using pass transistors (if designed properly) will always settle. I was considering the possibility that if you balanced the FF close enough to the threshold that it may behave chaotically not too different from a damped, driven pendulum. I was not aware of this, but if you release the pendulum of your grandfather clock close enough to the threshold it will not settle into a period and it will not stop. Rather it will continue to swing in a non-periodic way. Another chaotic system is a dripping faucet. The dripping faucet was actually studied by some of the pioneers in chaos theory. Since the CMOS FF appears to be overdamped, it will not behave chaotically. But if the RC of the pass transistor does not adequately compensate for the gain of the inverters, it has a chance at chaos. But peroidic oscillations are not chaos either. So even then it may just be an oscillator.Article: 104937
PeterC wrote:
> Hi All,
>
> I have searched long enough now with no luck, this should be trivial
> for someone:
>
> In the LUT4 instantiation below, what value should the LUT4 be
> INITialized to in order to implement a 2-input MUX, with the inputs on
> I0 and I1?
>
> i_lut4 : LUT4 generic map( INIT => x"????")
> port map(I0 => input1, I1 => input2, I2 => select, I3 => '0',
> O => output);
>
> Can someone please point me to a reference on how to calculate any INIT
> value for any 4-input logic function.
LUT4 is a 16-1 look-up table. You can use the verilog equation below to
calculate INIT, where init=INIT, i[0] = I0, i[1]=I1, i[2]=I2, i[3]=I3
reg [4:0] i;
reg [15:0] init;
for (i = 0; i < 16; i = i+1) begin
init[i] = i[2] ? i[1] : i[0];
end
HTH,
Jim
http://home.comcast.net/~jimwu88/tools/
Article: 104938Subhasri krishnan wrote: > Nobody? The obvious is to check your wiring. "Unknown device" may mean that the TMS or TDI signal is not making it to the FPGA. Can you chain multiple devices together? If so do you still see the 3S1500? Do the 3S200's still show up as "unknown"? This would seem to point to the TMS signal. Are you using the latest version of iMPACT? HTH, GaborArticle: 104939
PeterC wrote:
> Hi All,
>
> I have searched long enough now with no luck, this should be trivial
> for someone:
>
> In the LUT4 instantiation below, what value should the LUT4 be
> INITialized to in order to implement a 2-input MUX, with the inputs on
> I0 and I1?
>
> i_lut4 : LUT4 generic map( INIT => x"????")
> port map(I0 => input1, I1 => input2, I2 => select, I3 => '0',
> O => output);
>
> Can someone please point me to a reference on how to calculate any INIT
> value for any 4-input logic function.
>
> Cheers,
> Peter.
>
Working in Verilog, I define parameters (or localparams) in my module as
parameter I0 = 16'haaaa,
I1 = 16'hcccc,
I2 = 16'hf0f0,
I3 = 16'hff00;
and generate my inits directly:
LUT4 #( .INIT( I2 & I1 | ~I2 & I0 ) )
MyMux ( .I0(input1), I1(input2), I2(select), I3(1'b0) );
While a LUT3 primitive would work fine, some synthesizers don't like a
16-bit INIT provided for an 8-bit target so the 4th input of 0 works for
more synthesizers. Plus, it's easier to "LOCK_PINS" to F4/G4 in a LUT3
if you actually instantiate a LUT4.
As Antti pointed out, the result would be 16'hcaca.
- John_H
Article: 104940KJ wrote: > 'Better' I'm assuming to mean clock performance. If that's the case, then > from what I've seen performance is not usually affected. Mike Tressler has > also captured some performance numbers with a single design using various > tools targetting a couple different devices (see link below, then click on > 'Reference Design Source' and scroll down to the bottom). He has a bit of a > problem in his methodology of obtaining the performance numbers but even > there it seems to be a mixed bag as to whether synchronous or asynchronous > is better. The important thing though is that it is attempting to fairly > measure different techniques. Yes, it is a collection of benchmarks from volunteers. Some is incomplete and some is from synthesis estimates, but I prefer to publish what I have, and verify it as I can. I agree that the reset pulse must be synchronized in any case and that utilization and performance has no strong correlation to reset style. -- Mike TreselerArticle: 104941
"gary" <rgarik@yahoo.com> wrote in message
news:lcidnVZfNa0MpC3ZRVn_vA@giganews.com...
> In my
> user_ip.vhd there are 2 process one for read & another for write, now i
> want to access my inverter i.e one i/p & one o/p. so i have to write like
> this (h<=slv_reg0;) in write process and (k<=slv_reg1;)in read process
> because iam intended to connect the h to my i/p(s) of inverter and k to
> o/p(t) of my inverter.
> Can u tell me is this right?
No, it's not. See below corrected write and read processes and assignement
for h.
======================================================
-- implement slave model register(s)
SLAVE_REG_WRITE_PROC : process( Bus2IP_Clk ) is
begin
if Bus2IP_Clk'event and Bus2IP_Clk = '1' then
if Bus2IP_Reset = '1' then
slv_reg0 <= (others => '0');
else
case slv_reg_write_select is
when "100" =>
for byte_index in 0 to (C_DWIDTH/8)-1 loop
if ( Bus2IP_BE(byte_index) = '1' ) then
slv_reg0(byte_index*8 to byte_index*8+7) <=
Bus2IP_Data(byte_index*8 to byte_index*8+7);
end if;
end loop;
when others => null;
end case;
end if;
end if;
end process SLAVE_REG_WRITE_PROC;
h <= slv_reg0;
-- implement slave model register read mux
SLAVE_REG_READ_PROC : process( slv_reg_read_select,h,k) is
begin
case slv_reg_read_select is
when "100" => slv_ip2bus_data <= h;
when "010" => slv_ip2bus_data <= k;
when others => slv_ip2bus_data <= (others => '0');
end case;
end process SLAVE_REG_READ_PROC;
======================================================
/Mikhail
Article: 104942Currently we use iMpact to create daisy-chain .bin file for our motherboard populated with plug-in cards, each with its own XC3S500E. The plug-in cards configuration can be changed on the field so the bin image must also be regenerated for the new configuraion. We need to build a new daisy chain .bin file inside our embedded system. I was trying to understand the file structure but all the descriptions of the bitstream structure I found in application notes don't correspond to the files generated by iMpact. Has anyone tried to build daisy-chain .bin file programmatically out from single-device .bin files? Thanks.Article: 104943
jack...@gmail.com schrieb: > Currently we use iMpact to create daisy-chain .bin file for our > motherboard populated with plug-in cards, each with its own XC3S500E. > The plug-in cards configuration can be changed on the field so the bin > image must also be regenerated for the new configuraion. We need to > build a new daisy chain .bin file inside our embedded system. I was > trying to understand the file structure but all the descriptions of the > bitstream structure I found in application notes don't correspond to > the files generated by iMpact. > > Has anyone tried to build daisy-chain .bin file programmatically out > from single-device .bin files? Thanks. yes anyone has done this. What impact does is 'merging' the slave .BIT inside the master bit by inserting the slave .BIT as single stream that written to LOUT register. Well at least that is how it work for serial configuration. I have tried to configure multiply devices in chain without the LOUT trick but with little luck, usually both master and slave release done, but only one of them actually starts, eg GHIGH of the slave doesnt assert. using impact to insert the second bit inside the master bit makes the second (slave) device also to start properly. I bet you are (will be) facing the same problem. inserting the slave streams into LOUT record isnt complicated but you need to parse the .BIT files in order to write out the resulting single binary image that you need. Antti http://antti-brain.comArticle: 104944
Hello, > Are newer/faster PCI systems limited to point-point links rather than > multi-drop busses? Both PCI and PCI-X are inherently multi-drop. The specification defines the component I/O timing and also defines how to "measure" the bus propagation. As a system designer, you are then free to make a number of tradeoffs, including the physical bus topology, the number of loads and connectors, and the bus frequency. > Are there requirements on the driving/source (termination) impedance to damp out multi-trip reflections? Both PCI and PCI-X drivers have AC performance specifications; there are also some pullups associated with the host bridge function for most of the "control" signals and the 64-bit extension to the datapath (I find this asymmetry odd...) Anyway, there isn't anything resembling termination schemes you reference. In fact, adding other components outside the "PCI(-X) device" is a violation of the specification. Now, PCI Express -- on the other hand -- is a completely different beast. PCI Express is point to point and there are requirements on transmitter and receiver impedance. EricArticle: 104945
I think what you are asking is why the maximum clock frequency is higher with an async reset than it is for a synchronous reset using the sync reset pin of the Xilinx FPGA ff's. If so, it is because of two things: first, the async resets are not included in the static timing analysis, so they are not limiting the clock performance when you've used async resets, and second the reset pin on the ff's is quite a bit slower than the path through the LUT and the D input. If you absorb the sync reset into your D input logic, (and take the steps to make sure the synthesizer isn't pulling it out and using the reset pin) you'll probably see the clock performance match the async performance unless adding the reset pushes the logic to more than 4 inputs.Article: 104946
Hi, I am trying to implement the sample design (Web server) that comes with the P160 communications module 3 from Avnet design. I have connected this module to the V2Pro7 FF672 board from Xilinx. When I run the tools-> buil applications, I get a series of errors: Running DRC Tcl procedures for OPTION IPLEVEL_DRC_PROC... ERROR:MDT - Unknown Tcl procedure ::hw_opb_emc_v1_10_b::check_iplevel_settings called ERROR:MDT - ERROR FROM TCL:- opb_emc_0 (opb_emc) - while executing "::hw_opb_emc_v1_10_b::check_iplevel_settings 37696248" ERROR:MDT - Errors occured while creating Hardware System make: *** [ppc405_i/lib/libxil.a] Error 2 Has anyone seen this?? any solutions?? VivekArticle: 104947
Thanks for all the pointers. I have a couple of questions/doubts: The Verilog implementation for the Ethernet connection is too good. However, what is the standard practice?? I have two options: 1. Implement the Ethernet module(fpgas4fun) and connect it as another I/O module to my design block and send the data to the buffers which in turn will be transmitted over the ethernet to the host PC. 2. Use the PowerPC which will send the data to the host PC through the ethernet module. This means tweaking the web server design that comes with the P160 comm3 module and then instantiating the system.xmp as a VHDL module in ISE. I presume that the module would have a valid 8-bit port that will accept the data from my design block and transmit it over the ethernet to the host PC. I would like to know which option is better. Has anyone done it this way. Any suggestions?? Thanks, VivekArticle: 104948
"Weng Tianxiang" <wtxwtx@gmail.com> wrote in message
news:1152314914.257969.13700@m79g2000cwm.googlegroups.com...
> Hi,
> I received a google warning message on key word "fastest sorting
> algorithm" this afternoon.
>
> The following is one of its message addresses:
> http://groups.google.com/group/rec.games.programmer/browse_thread/thread/89b0b172e3772006/78ac42b8a1c00578?q=fastest+sorting+algorithm&rnum=8#78ac42b8a1c00578
>
>
> "Why? It only takes that run to disprove your assertion.
> You claimed that the radix sort is the fastest algorithm, this example
> disproves that.
>
> 10 elements, qsort: ~2500 clocks, bucket: ~37500 clocks.
>
> FYI, with 1000 values, the times were: ~275000 for bucket, ~435000 for
> qsort."
>
> Unit is in clocks, it is easier for everyone to compare different
> sorting algorithms and I have a good taste on how fast a sorting
> algorithm runs.
>
> The message was in 1998, but it is still valid in the order.
Fastest is usually important in big data sets. In other words, if we have
10 elements, it does not matter much which sorting method is used. The sort
will be done much faster than we can sneeze.
And typically, sort algorithms fall back to routines that are O(f(n))
inferior but faster in practice for smaller sets.
For example, sorting a huge volume of data:
Start with MSD Radix sort at the top level (as a function of keysize and
rowcount).
Switch to Introspective sort when the set size is under some threshold
(keysize * set_rowcount * system_specific_constant > set_rowcount *
log2(set_rowcount)).
Switch to Insertion sort when the set size is very small (usually 20-30
elements or so).
Typically, if a dataset sorts in 10 milliseconds or 20 microseconds, we
won't care very much. If it is one day verses 1 hour, then it matters a
lot.
P.S.
Here's the world's fastest sort (it only works on sets that have 0 or 1
element):
void worlds_fastest_sort()
{
return;
}
> Weng
>
Article: 104949John_H wrote: > parameter I0 = 16'haaaa, > I1 = 16'hcccc, > I2 = 16'hf0f0, > I3 = 16'hff00; > > LUT4 #( .INIT( I2 & I1 | ~I2 & I0 ) ) > MyMux ( .I0(input1), I1(input2), I2(select), I3(1'b0) ); Very elegant! One question though, doesn't explicitly instantiating the LUT4 like this constrain the routing or is it smart enough to know that it can freely permute the pins with a suitable permutation of the initialization vector? Also, this trick should generalize nicely to a Xilinx LUT6, but what about the Stratix II ALMs? Tommy
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