EDK : FSL macros defined by Xilinx are wrong

[Stephen Williams]

Mike Treseler wrote:

GaLaKtIkUs™ wrote:

I wanted to use Icarus but I was confronted to a big problem (as a user
of Xilinx): in the simlation libraries there are specify blocs and
Icarus verilog doesn't support them.

Could you write your own code
and not use the libraries?

Ugh! There is no need for that. As I said already on this thread,
Icarus Verilog will (should) parse and ignore specify blocks and
the end result is a perfectly good simulation. All you miss in this
context is back-annotation support.

Any other problems simulating with Xilinx models should be posted
in the bug tracking database. I *will* fix such bugs, because I
do Xilinx work with Icarus Verilog regularly.

--
Steve Williams "The woods are lovely, dark and deep.
steve at icarus.com But I have promises to keep,
http://www.icarus.com and lines to code before I sleep,
http://www.picturel.com And lines to code before I sleep."

 

[Ron]

GaLaKtIkUs™ wrote:

Rewrite the whole libraries, which model Xilinx primitives for all
Xilinx FPGA/CPLD families and all speed grades?

Why not just rewrite the ones you need, instead of ALL of them?

 

[Mark McDougall]

Weng Tianxiang wrote:

Can I find a website that lists the time for sorting 1 million
64-bit/32-bit random data using the fastest software sorting algorithm
in a PC?

Given that you can't even find the relevant usenet newsgroup to ask this
question... I highly doubt it.

That aside...

The "fastest" algorithm is going to depend on a few things; for example
the actual 'randomness' of the data (its distribution), the format of
said data and the results (e.g. do you need to sort in-place?), and the
implementation of the algorithm (by which I mean, is the algorithm
optimal for implementation in a typical PC?).

You definitely won't find any answers on the absolute time required by a
"PC" - whatever that is. And even if you did, the answer would be
obsolete in about a week's time.

You really need to find one or two candidate algorithms and then
implement them on your chosen platform to get any meaningful solution to
your problem.

Regards,

--
Mark McDougall, Engineer
Virtual Logic Pty Ltd, <http://www.vl.com.au>
21-25 King St, Rockdale, 2216
Ph: +612-9599-3255 Fax: +612-9599-3266

 

[Symon]

"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.

 

[Jonathan Bromley]

On 12 Jul 2006 08:26:20 -0700, Brannon
<brannonking@yahoo.com> wrote:

Here's my FPGA solution. I have a bitonic sort core for an FPGA. Fill
up a large FPGA and it will do 64-bit by 64 rows every clock cycle

As a matter of interest, how big is the bitonic sort? I guess I'm
really asking "how many 64-bit magnitude comparators do you need",
although there's presumably some swap or routing logic also
associated with each comparator. (sorry, I'm not familiar with
the bitonic sort algorithm - must go look it up). And how many
levels of logic? I guess it's best to pipeline it...

TIA
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jonathan Bromley]

On Wed, 12 Jul 2006 16:51:40 +0100, Jonathan Bromley
<jonathan.bromley@MYCOMPANY.com> wrote:

As a matter of interest, how big is the bitonic sort? I guess I'm
really asking "how many 64-bit magnitude comparators do you need",
although there's presumably some swap or routing logic also
associated with each comparator. (sorry, I'm not familiar with
the bitonic sort algorithm - must go look it up). And how many
levels of logic? I guess it's best to pipeline it...

OK, so I looked it up... it's the same as the Batcher sort/merge
that I've played with before. Sorting 64 items requires 543
compare/swap blocks, and the longest path goes through
21 of these blocks. Each block consists of a 64-bit magnitude
comparator and two 64-bit 2:1 muxes to do the swap.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Weng Tianxiang]

Hi Jonathan,
Could you please give the paper address so that I am able to have a
look at the algorithm?

Thank you.

Weng

 

[Jonathan Bromley]

On 12 Jul 2006 10:05:52 -0700, Weng Tianxiang
<wtxwtx@gmail.com> wrote:

Could you please give the paper address so that I am able to have a
look at the algorithm?

This is where I found it...
http://www.nist.gov/dads/HTML/bitonicSort.html

and it references the same Knuth book that I used
to find out about Batcher sort.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Weng Tianxiang]

Hi Jonathan,
Thank you very much.

Weng

 

[Ron]

rickman wrote:

I think if upper management saw all of the posts that Austin makes they
would likely not be pleased by the way the company is presented. Or
maybe they wouldn't have a problem, I can't say. I do know that the
apperence is that Xilinx is a rather arrogant company, not unlike Intel
in the early days.

I totally agree and already reported both Austin and Peter to Xilinx
marketing as well as corporate management sometime ago via email. It
seemed to do no good whatsoever, so maybe Xilinx doesn't care. ...Or
maybe they just need more complaints, preferably via US postal mail on
company letterhead rather than email. Austin sure spews a lot of
marketing hype for an engineer who is ostensibly not in marketing.

-- Ron

 

[Weng Tianxiang]

Hi Jonathan,
It seems you are very familiar with Batcher algorithm.

1. I would like to know why you get 543 compare/swap blocks?

It has (lg N)*((lg N)+1)/2 stages based on formula of Knuth Vol 3,
p.113. For N= 64, it has 21 stages.

With n/2 comparators at each stage, it means it has 32 comparators at
each stage.

32*21 = 672 /= 543?

2. How did you get the conclusion: the longest path goes through 21 of
these blocks.

I think because it is pipelined, the longest path goes through only 1
block, why it is 21 blocks?

Thank you.

Weng

 

[Jonathan Bromley]

On 14 Jul 2006 05:48:43 -0700, Weng Tianxiang
<wtxwtx@gmail.com> wrote:

1. I would like to know why you get 543 compare/swap blocks?

It has (lg N)*((lg N)+1)/2 stages based on formula of Knuth Vol 3,
p.113. For N= 64, it has 21 stages.

Yes, that's where I get my figure for 21 levels of logic.

With n/2 comparators at each stage, it means it has 32 comparators at
each stage.

32*21 = 672 /= 543?

Not all levels have the maximum population of n/2 blocks.

2. How did you get the conclusion: the longest path goes through 21 of
these blocks.

By counting them See Knuth's algorithm. The little console-
mode C program, attached, implements the algorithm and shows you
the sorting network as ASCII-art. Make sure its output is rendered
in a fixed-width font.

I think it would be quite easy to modify the program
so that it writes a VHDL or Verilog netlist.

I think because it is pipelined, the longest path goes through only 1
block, why it is 21 blocks?

Of course, if you pipeline it then you can reduce the critical path
to only one level of compare/swap - but you then get 21 clocks
of latency. Your choice.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Batcher's merge-exchange sort
// Follows notation in Knuth, Sorting and searching, p112
//
// This is (nearly!) the best way to create a purely combinational
// sorting network, given that the basic available sorting operation
// is to compare two values and swap them if they are out of order.
// The hardware structures created by this program are easy to
// implement, and can readily be pipelined to improve throughput.
//
//
// Revision info:
//
// 1.0 Jonathan Bromley 18 Feb 2001
// first version
// 2.0 Jonathan Bromley 31 Jan 2002
// - improved argc/argv checking
// - added "usage" message if user supplies bad arguments
// - added statistics line
// - improved comments
// There's still a problem with wasteful use of space on
// lines where compare/exchange operations overlap.
// The program shows the correct set of swap operations,
// but it prints them in a slightly clumsy way in some situations.
// To fix this, we would need to gather up all the swaps
// at any given logic level, and sort them before printing.
// I can't be bothered doing that just now.


#include <stdio.h>
#include <stdlib.h>

// find /lg2\, i.e. number of bits needed to represent 0..n-1
//
int ceil_lg2(int n) {
int t=1;
n--;
while (n/=2) t++;
return t;
}


// print separator between sets of compare/exchange
//
void sep(int n, int p, int q, int r, int d) {
int i;
printf("p,q,r,d = %2d,%2d,%2d,%2d |", p,q,r,d);
for (i=1; i<n; i++) printf("-|");
printf("\n");
}


// Compare/exchange.
// Pro tem, it just prints a little graphic - no calculation.
// Arguments:
// n number of input elements (decides width of printed line)
// a,b index numbers of the two elements to compare/exchange
// Call with a=0 to print the trailing part of the line.
//
void compex(int n, int a, int b) {

int t; // swap a,b if necessary
static int i=0; // keeps track of how much of the
// current line is already occupied with text

if (i>=a) {
// Overlap! We need to start on a new line.
// Print to the end...
while (++i <= n) printf(" |");
printf("\n");
i=0; // Be sure to print the start of the next line
}

if (a>0) {
// Make sure a, b are in order (paranoia!!)
if (a>b) {
t=a;
a=b;
b=t;
}
// Leading spaces (left margin)
if (i==0) printf(" ");
// Move forward to the starting position, printing blanks
while (++i < a) printf(" |");
// Print starting position
printf(" O"); // leaves i==a
// Move forward to the end position, printing links
while (++i < b) printf("==");
// Print end position
printf("=O"); // leaves i==b
}
}


// Print statistics info
//
void stats(int c, int l, int n) {
printf("\nSorted %d elements using:\n", n);
printf("%4d levels of logic;\n", l);
printf("%4d compare/exchange modules.\n\n", c);
}


// Main program
//
void Batcher( int N ) {

// Variables required by Batcher's algorithm.
// The very short names exactly match the names of
// variables in Knuth's description.
int t, p, q, r, d, i;

// Keep track of how many compares we did, and how many levels
// of logic it required
int comps=0;
int levels=0;


// M1: initialise p
t = ceil_lg2(N);
p = 1 << (t-1);

do {
// M2: initialise q,r,d
q = 1 << (t-1);
r = 0;
d = p;

do {
// M3: loop on i
sep(N,p,q,r,d);
levels++;
for (i=0; i < N-d; i++) if (( i & p ) == r) {
// M4: loop body
// Do a compare/exchange on the two elements.
compex(N, i+1, i+d+1);
comps++;
}
// Print any leftover bits of a line that we may need.
compex(N,0,0);
// M5: loop on q
i = q; // needed for "while" test!
d = q - p;
q /= 2;
r = p;
} while (i != p);
// M6: loop on p
} while (p /= 2);

// Tidy up and print statistics
stats(comps, levels, N);
}


// Command line driver
//
int main(int argc, char **argv) {

int n;

// Check the user supplied just one argument, a positive integer.
// If not, print usage message and exit.
if (
(argc != 2) // wrong number of args
|| ((n = atoi(argv[1])) <= 0) // arg isn't a positive int
) {
printf("BATCHER: Create a merge/exchange sort network.\n");
printf("=======\n");
printf("Usage:\n batcher <n>\n");
printf("<n> is the number of items to be sorted\n");
return 1;
}

// Command line had the correct form; go ahead.
printf("\n");
Batcher;
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[John_H]

"Ron" <News5@spamex.com> wrote in message news:zaHtg.779$RP7.677@fe02.lga...

rickman wrote:
I think if upper management saw all of the posts that Austin makes they
would likely not be pleased by the way the company is presented. Or
maybe they wouldn't have a problem, I can't say. I do know that the
apperence is that Xilinx is a rather arrogant company, not unlike Intel
in the early days.

I totally agree and already reported both Austin and Peter to Xilinx
marketing as well as corporate management sometime ago via email. It
seemed to do no good whatsoever, so maybe Xilinx doesn't care. ...Or maybe
they just need more complaints, preferably via US postal mail on company
letterhead rather than email. Austin sure spews a lot of marketing hype
for an engineer who is ostensibly not in marketing.

-- Ron

Resurrecting an old thread while so many people are off to vacation?

This forum would have significantly less traffic and the general quality of
information and help exchanged on this board would suffer if those two
Xilinx employees were told to stop posting here.

Austin can be as annoying at times when he's gung-ho about communicating the
things *he* believes in; they may seem like total marketing rubbage but it
seems to me he just has strong feelings on the matters. His interaction can
be caustic at times as well. But taking the good with the bad his presence
here has been invaluable, in my humble opinion.

Why you have issues with Peter Alfke is beyong me. Not only is he
professional, resourceful, and extremely helpful but he presents himself
here calmly and conservatively even in the face of dire flames and worse.
If more people could present his professionalism and the strong desire to
help that both these men contribute to this forum, I would be a happier
engineer.

I'm glad that I only have one person in my kill file considering how long
I've been interacting with the newsgroup. Feel free to add Ausitn, Peter,
even myself to your own kill file.

Many thanks to all the others who help make this a constructive place to
advance FPGA design.

- John Handwork

 

[Austin Lesea]

Gee,

Thanks. (Austin for Austin)

Peter is on vacation, so I will say thanks for him as well:

Danke,

Austin (for Peter)

 

[Dave]

On Fri, 14 Jul 2006 15:41:15 +0000, John_H wrote:

Resurrecting an old thread while so many people are off to vacation?

This forum would have significantly less traffic and the general quality of
information and help exchanged on this board would suffer if those two
Xilinx employees were told to stop posting here.

Austin can be as annoying at times when he's gung-ho about communicating the
things *he* believes in; they may seem like total marketing rubbage but it
seems to me he just has strong feelings on the matters. His interaction can
be caustic at times as well. But taking the good with the bad his presence
here has been invaluable, in my humble opinion.

Why you have issues with Peter Alfke is beyong me. Not only is he
professional, resourceful, and extremely helpful but he presents himself
here calmly and conservatively even in the face of dire flames and worse.
If more people could present his professionalism and the strong desire to
help that both these men contribute to this forum, I would be a happier
engineer.

I'm glad that I only have one person in my kill file considering how long
I've been interacting with the newsgroup. Feel free to add Ausitn, Peter,
even myself to your own kill file.

Many thanks to all the others who help make this a constructive place to
advance FPGA design.

- John Handwork

Exactly!


~Dave~

 

[Weng Tianxiang]

Hi Jonathan,
Thank you for your thorough understanding the Batcher algorithm and its
program in C.

Weng

 

[Eli Hughes]

Austin Lesea wrote:

Gee,

Thanks. (Austin for Austin)

Peter is on vacation, so I will say thanks for him as well:

Danke,

Austin (for Peter)

Add me to list.

While I have not always agreed with Austin, don't come here asking for
free help and then start crying 'Xilinx is the evil empire' when you
don't like the answer. Anytime there has been a serious problem on the
Xilinx side (like with incorrect documentation, bad chip, etc.) they
provide help. When it comes to design advice or something that is
screwed up (for any reason), don't expect a group of engineers to form a
consensus that you were the helpless victim of a bad chip or poor
documentation. Anytime you get lots of engineers together, there is
never agreement. Everyone thinks there way is better.

-Eli

 

[Weng Tianxiang]

Hi Jonathan,
"1. I would like to know why you get 543 compare/swap blocks?

It has (lg N)*((lg N)+1)/2 stages based on formula of Knuth Vol 3,
p.113. For N= 64, it has 21 stages.
Yes, that's where I get my figure for 21 levels of logic.
With n/2 comparators at each stage, it means it has 32 comparators at
each stage.
32*21 = 672 /= 543?
Not all levels have the maximum population of n/2 blocks. "

I read Knuth's Volumn Batcher's algorhtm and didn't find the formula
for the
number of comparators. Do you have a ready formula for it?

Thank you.

Weng

 

[Jonathan Bromley]

On Thu, 20 Jul 2006 17:07:53 -0700,
Mike Treseler <mike_treseler@comcast.net> wrote:

But if anyone writes a book like this it will fly off the shelves!

A few hundred copies would fly off the shelves.
[...]
Those are not numbers that would excite
a major publisher.
Writing and editing a book is two long years
of work, whatever the subject.

Agreed.

However... it seems to me that comp.lang.verilog/vhdl
and comp.arch.fpga represents a useful pool of
expertise. It's not part of *my* skill-set to do this,
but I wonder if someone could consider setting-up
a Wiki (freely-editable website) that could be used
as a readily accessible repository of this kind of
stuff? It would take a while before we got a
reasonable collection of material in it, but a couple
of evenings' work by each of a few dozen skilled
people might make for a great collection of ideas
and tips. And who knows, at some point it might
provide the source material for a real paper-and-ink
book that you could take on vacation to read at
the beach The Tcl/Tk Wiki is an alive-and-kicking
example: see http://wiki.tcl.tk/0

Here are some ramblings that convince me it's an
idea worth pursuing:

Our VHDL and Verilog courses teach language essentials
and coding style, and discuss some generally-applicable
design techniques such as FSMs, but to keep them generic
(and a reasonable length!) we don't discuss how to design
any specific kind of hardware. But we have often been
asked to create a course covering "the art of good RTL
design" or somesuch. What these customers seem
to want is something like "thirty years of design
experience in a three-day class". It's never been
feasible for us to do that, because the exact content
would be so specific to the particular needs of any
one customer. But an open, peer-moderated,
frequently-updated repository sounds like a good
idea to me. I don't mean a library of complete
ready-cooked designs like opencores.org; rather,
I'm thinking of a collection of "design patterns"
and shared experience.

Any takers?
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Symon]

"Jonathan Bromley" <jonathan.bromley@MYCOMPANY.com> wrote in message
news:djb0c2d96k2f7tjv3tg9k09dri31bb1gtk@4ax.com...

However... it seems to me that comp.lang.verilog/vhdl
and comp.arch.fpga represents a useful pool of
expertise. It's not part of *my* skill-set to do this,
but I wonder if someone could consider setting-up
a Wiki (freely-editable website) that could be used
as a readily accessible repository of this kind of
stuff?

Any takers?

I think the infrastructure is already available.

http://en.wikibooks.org/wiki/Wikibooks:Engineering_bookshelf
or even more appropriately:-
http://en.wikibooks.org/wiki/Programmable_Logic

Cheers, Syms.