EDK : FSL macros defined by Xilinx are wrong

[John_H]

Weng Tianxiang wrote:

David Ashley wrote:
Weng Tianxiang wrote:

Weng,

Did you mean to post this to comp.arch.fpga?

It's an interesting problem and all, but...?

-Dave

--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture

Hi David,
Yes, I post it for comp.arch.fpga too.

1. comp.arch.fpga has a group of engineers who have many experiences
with logic design, are talent and should pay attention to the deepest
problem in computing complexity.

2. I dream someday we can design a NP machine that runs all NP problems
in polynomial time using a FPGA chip. Personally I think Turing machine
should be dying with powerful FPGA chips growing and the fact should be
reflected in computing theory.

3. The above posting is my a small step in a direction I am thinking is
right: first to design an algorithm that is not using brute force, but
some smart ideas of the special problem.

4. I select the minimum vertex cover because its memory will never be
expanded and it depends on a smarter selection to finish the cover.

5. At the current moment, I am devoting to design an algorithm that
works with minimum vertex cover.

6. If the algorithm works, all of us have a chance to finish a NP
machine with performance in polynomial time.

Thank you.

jWeng

If you had an amazing vacation planned and you knew the best way to
travel was by car and that car enthusiasts were very knowledgeable about
traveling, would you post about the vacation to an automotive design
bulletin board?

 

[David Ashley]

Weng Tianxiang wrote:

1. comp.arch.fpga has a group of engineers who have many experiences
with logic design, are talent and should pay attention to the deepest
problem in computing complexity.

2. I dream someday we can design a NP machine that runs all NP problems
in polynomial time using a FPGA chip. Personally I think Turing machine
should be dying with powerful FPGA chips growing and the fact should be
reflected in computing theory.
...

I understand your goal + hope you make progress. I've read
that all NP Complete problems can be mapped onto each
other, so that if you can solve one in faster than exponential
time, you can solve them all.

My personal feeling is throwing an fpga at the problem is
akin to throwing more computers at it. FPGA's grow in
2D though. Even if you could pack computers together
in 3D, the complexity of the problems is such that time to
solve them will grow faster than you can expand your 3D
matrix of computing fabric. It's hopeless...

What interesting problems would you want to solve in
polynomial time, anyway? The vertex coverage one doesn't
have in itself any useful application in my life. Perhaps
protein folding? AI in some way? Place + Route?

Speaking of which, here's a nobel prize winning idea.
Assuming the problem of protein folding is part of NP
complete, all you'd have to do is construct a DNA
sequence that encodes for a protein, and the protein
itself is equivalent to some OTHER NP problem you
want to solve. So you let the protein go and fold however
it wants to, and then you look at how it's folded, and you
have your answer. So you've managed to get the universe
to work for you.

Sorry for adding to this off-topic mayhem.

-Dave


--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture

 

[eKo1]

Let G be a tree of height h > 0. Say the root is at the level 0 of the
tree, its children at level 1, their children at level 2, etc.. If h is
odd, let V' be the set of vertices at the even levels of the tree. If h
is even, let V' be the set of vertices at the odd levels of the tree.
Is V' a minimum vertex cover?

 

[Weng Tianxiang]

David Ashley wrote:

Weng Tianxiang wrote:
1. comp.arch.fpga has a group of engineers who have many experiences
with logic design, are talent and should pay attention to the deepest
problem in computing complexity.

2. I dream someday we can design a NP machine that runs all NP problems
in polynomial time using a FPGA chip. Personally I think Turing machine
should be dying with powerful FPGA chips growing and the fact should be
reflected in computing theory.
...

I understand your goal + hope you make progress. I've read
that all NP Complete problems can be mapped onto each
other, so that if you can solve one in faster than exponential
time, you can solve them all.

My personal feeling is throwing an fpga at the problem is
akin to throwing more computers at it. FPGA's grow in
2D though. Even if you could pack computers together
in 3D, the complexity of the problems is such that time to
solve them will grow faster than you can expand your 3D
matrix of computing fabric. It's hopeless...

What interesting problems would you want to solve in
polynomial time, anyway? The vertex coverage one doesn't
have in itself any useful application in my life. Perhaps
protein folding? AI in some way? Place + Route?

Speaking of which, here's a nobel prize winning idea.
Assuming the problem of protein folding is part of NP
complete, all you'd have to do is construct a DNA
sequence that encodes for a protein, and the protein
itself is equivalent to some OTHER NP problem you
want to solve. So you let the protein go and fold however
it wants to, and then you look at how it's folded, and you
have your answer. So you've managed to get the universe
to work for you.

Sorry for adding to this off-topic mayhem.

-Dave


--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture

Hi David,
The idea I tried to attack the minimum vertex cover has nothing to do
with its range of applications. Far beyond that, because all NP
problems are the same in computing complexity, I choose the simplest
one in concept and tried to attack it. If it could be resolved in
polynomial time, every other problem in NP class could be resolved too.
The minimum vertex cover is so simple that my algorithm lives only one
day and is dead now with a persuasive counterexample raised by
Patricia.

I have to read Cook's original paper once more.

Thank you, masters Cook and Karp, you had raised an open question for
all human to answer.

Weng

 

[Patricia Shanahan]

David Ashley wrote:
....

What interesting problems would you want to solve in
polynomial time, anyway? The vertex coverage one doesn't
have in itself any useful application in my life.
....

Suppose you have a set of nodes (computers, switches, memory modules...)
with point-to-point links between them, and want to instrument the
smallest possible subset of the nodes such that you can monitor traffic
on each point-to-point link.

Patricia

 

[Arthur J. O'Dwyer]

[followups set to comp.programming only]

On Tue, 26 Sep 2006, eKo1 wrote:

Let G be a tree of height h > 0. Say the root is at the level 0 of the
tree, its children at level 1, their children at level 2, etc.. If h is
odd, let V' be the set of vertices at the even levels of the tree. If h
is even, let V' be the set of vertices at the odd levels of the tree.
Is V' a minimum vertex cover?

No. Consider

4-----9-----11--12
| | |
2--3 7--8 10
| |
1 6

where 4 is the root. Your algorithm gives (4, 1, 3, 6, 8, 11) where the
real solution --- which can be found using the optimal "claw-removal"
part of the OP's algorithm, since it always works as long as you never
run out of claws --- is (4, 2, 6, 8, 11).

As Mark P, Patricia, and I have pointed out, and I think Weng finally
acknowledged, the problem with his algorithm is not with the "claw
removal" but with the fallback greedy algorithm. The solution is to
replace the fallback greedy algorithm with a fallback brute-force
algorithm.

-Arthur

 

[Ralph Hartley]

David Ashley wrote:

Speaking of which, here's a nobel prize winning idea.
Assuming the problem of protein folding is part of NP
complete, all you'd have to do is construct a DNA
sequence that encodes for a protein, and the protein
itself is equivalent to some OTHER NP problem you
want to solve. So you let the protein go and fold however
it wants to, and then you look at how it's folded, and you
have your answer. So you've managed to get the universe
to work for you.

Not a particularly new idea, I'm afraid. The problem is that the protein
corresponding to a hard problem will take nearly *forever* to fold.

It is not true that an arbitrary protein sequence will quickly fold into
a stable structure that is the same each time. In fact, most will *not*
do that. Biological proteins do (mostly), but they were selected for that.

Ralph Hartley

 

[Weng Tianxiang]

Ralph Hartley wrote:

David Ashley wrote:
Speaking of which, here's a nobel prize winning idea.
Assuming the problem of protein folding is part of NP
complete, all you'd have to do is construct a DNA
sequence that encodes for a protein, and the protein
itself is equivalent to some OTHER NP problem you
want to solve. So you let the protein go and fold however
it wants to, and then you look at how it's folded, and you
have your answer. So you've managed to get the universe
to work for you.

Not a particularly new idea, I'm afraid. The problem is that the protein
corresponding to a hard problem will take nearly *forever* to fold.

It is not true that an arbitrary protein sequence will quickly fold into
a stable structure that is the same each time. In fact, most will *not*
do that. Biological proteins do (mostly), but they were selected for that.

Ralph Hartley

Hi,
Here is a good introduction reference on the minimum vertex cover
problem:
http://www.cs.uu.nl/docs/vakken/amc/lecture03-4.pdf#search=%22minimum%20vertex%20cover%22

Weng

 

[Antti]

bart schrieb:

it's my humble understanding that Mico32 is truly RTL, i.e. we do not
use any library elements, so it should be portable. (although, of
course, we'd like for you to buy our chips!)
rgds,
Bart Borosky, Lattice, online marketing manager

Source yes, but not RTL. My guess it's lots of instantiated primitives,
thus not portable.

Bart,

please look at

http://latticeblogs.typepad.com/frontier/2006/09/soft_processor_.html#comments

its full of adult avertizing!

I was about to post a comment there, but when I see that spam there...
brr!

Antti

 

[Norbert Stuhrmann]

Hi Derek,

Derek Simmons wrote:

I'm looking for any helpful or constructive suggestions.

You might have a look at the cordic algorithms.

Regards,

Norbert Stuhrmann

 

[bart]

hi Antti, unfortunately, that's one of the downsides to accepting
comments instantly, without approval. you post a comment, it will be up
on our blog right away!

some people will spam. typepad isn't able to block all spam. we deleted
that "adult" spam comment this morning, right when we saw it. please do
not hesitate to add comments to our blog based on the actions of one
spammer.
http://latticeblogs.typepad.com/frontier/2006/09/soft_processor_.html#comments

if we continue to have issues with spam, we will have to pre-"approve"
all comments, but we aren't to that point yet! rgds, bart
---------
Bart Borosky
Manager, Online Marketing
Lattice Semiconductor

Bart,

please look at

http://latticeblogs.typepad.com/frontier/2006/09/soft_processor_.html#comments

its full of adult avertizing!

I was about to post a comment there, but when I see that spam there...
brr!

Antti

 

[Derek Simmons]

Norbert Stuhrmann wrote:

Hi Derek,

Derek Simmons wrote:
I'm looking for any helpful or constructive suggestions.

You might have a look at the cordic algorithms.

Regards,

Norbert Stuhrmann

The cordic projects on OpenCores were hits I found searching for
algorithms. Not that I'm able to connect, unless somebody recommends
otherwise I'm going to focus my investigation and research on them.

Thanks,
Derek

 

Get Pedia <cutemonication2@yahoo.com> wrote:

Bunch of ad-links..

 

[Jim Granville]

KJ wrote:

Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

any application where the FPGA is driving downstream power devices :
eg in Motor Drive applications.

That said, normally that type of hard reset, is normally done with
external logic devices that collect a number of 'OK' signals before
actually allowing the power devices to turn on...

-jg

 

[Bob Perlman]

On Mon, 09 Oct 2006 00:04:37 GMT, "KJ" <kkjennings@sbcglobal.net>
wrote:

"Andrew FPGA" <andrew.newsgroup@gmail.com> wrote in message
news:1160349835.918930.124340@i42g2000cwa.googlegroups.com...
If you take a step back and realize that you probably shouldn't expect
anything useful out of a part that is not receiving the proper inputs yet
(perhaps by design, after all it could be a power saving measure) then
the
outputs that do not actually reset themselves until the clock does start
up
is not really an issue.

Ok but what if those FPGA outputs can cause problems for other parts of
the system, say if the FPGA is on a bus. Maybe there are some bus
protocols out there where the bus clock can stop, and the peripheral
needs to be able to be reset by the bus master??
Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

How about TriState contention? If I'm controlling TriState buffers
with FFs that aren't initialized until the clock comes along, I run
the risk of turning on more than one set of TriStates on a signal or
bus. And when you're using high-current drivers, this can cause
smoke; I've seen it.

Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com

 

[Peter Alfke]

That's why (as I posted earlier) all Xilinx FPGA asynchronously
initiate all flip-flops as part of the initiating and configuration
process, and also keep the outputs 3-stated until configuration is
finished.
Nothing new for you, Bob, but somebody else may have forgotten.
Peter Alfke
====================
Bob Perlman wrote:

On Mon, 09 Oct 2006 00:04:37 GMT, "KJ" <kkjennings@sbcglobal.net
wrote:


"Andrew FPGA" <andrew.newsgroup@gmail.com> wrote in message
news:1160349835.918930.124340@i42g2000cwa.googlegroups.com...
If you take a step back and realize that you probably shouldn't expect
anything useful out of a part that is not receiving the proper inputs yet
(perhaps by design, after all it could be a power saving measure) then
the
outputs that do not actually reset themselves until the clock does start
up
is not really an issue.

Ok but what if those FPGA outputs can cause problems for other parts of
the system, say if the FPGA is on a bus. Maybe there are some bus
protocols out there where the bus clock can stop, and the peripheral
needs to be able to be reset by the bus master??
Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

How about TriState contention? If I'm controlling TriState buffers
with FFs that aren't initialized until the clock comes along, I run
the risk of turning on more than one set of TriStates on a signal or
bus. And when you're using high-current drivers, this can cause
smoke; I've seen it.

Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com

 

[KJ]

Jim Granville wrote:

KJ wrote:
Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

any application where the FPGA is driving downstream power devices :
eg in Motor Drive applications.

That said, normally that type of hard reset, is normally done with
external logic devices that collect a number of 'OK' signals before
actually allowing the power devices to turn on...

And if you're turning over control of the motor driver to a part that

is clocked, I would expect that 'clock is running' would be one of
those 'OK' signals. Furthermore, knowing that the clock is an input to
the motor driver function, I would guess that the PCBA design would not
even release reset to the FPGA until after the clock is actually
running. Or is that not typically how one would do it?

KJ

 

[KJ]

Bob Perlman wrote:

Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

How about TriState contention? If I'm controlling TriState buffers
with FFs that aren't initialized until the clock comes along, I run
the risk of turning on more than one set of TriStates on a signal or
bus. And when you're using high-current drivers, this can cause
smoke; I've seen it.

Those must be some hefty drivers if they can cause smoke in the

probably only a couple of milliseconds between when reset gets released
until the clock starts running (assuming that reset was even released
first, typically I wouldn't do that). I've seen bus driver TTL type
devices, which are relatively hefty drivers, shorted for several weeks
while waiting for the short on the board to be found and fixed without
any smoke occurring and marveled that devices can take such abuse and
still work. Probably cut into the shelf life of that board a bit but
this was an engineering prototype.

So is there some publicly available "high current tri-state bus where
reset releases before clock is running" you can refer to? Or was this
some internal proprietary bus?

KJ

 

[Bob Perlman]

On 9 Oct 2006 09:27:57 -0700, "KJ" <Kevin.Jennings@Unisys.com> wrote:

Bob Perlman wrote:
Like I said, I don't discount that there may be these cases...but have yet
to hear anyone actually name a specific case where the clock isn't running
but a specific reset condition is required.

Can anyone actually provide one? Hard to believe that such a case doesn't
exist, but also hard to believe that one hasn't been articulated
either....oh well.

How about TriState contention? If I'm controlling TriState buffers
with FFs that aren't initialized until the clock comes along, I run
the risk of turning on more than one set of TriStates on a signal or
bus. And when you're using high-current drivers, this can cause
smoke; I've seen it.

Those must be some hefty drivers if they can cause smoke in the
probably only a couple of milliseconds between when reset gets released
until the clock starts running (assuming that reset was even released
first, typically I wouldn't do that).

The drivers I'm referring to are chips like the ones you'd find in the
74ABT and 74LVT families. If memory serves, they source 32 mA HIGH
and sink 64mA LOW. If you have one 16-output buffer chip contending
with another, believe me, you will burn at least one of them out, and
it won't take long. And if you somehow manage to keep the contention
short enough to avoid burning them out immediately, you will shorten
their lives.

This is not conjecture; I've seen it happen in actual hardware. I
used to help design ultrasound machines, and I learned that if you
want to get a physician mad, make smoke come out of something his
clinic just paid $200K for. They are touchy like that.

As for releasing the reset after the clock starts running, yes, that's
what you want to do. But how does that prevent contention if the
resets are purely synchronous? You could gate every TriState enable
with the reset, but that slows down the enable path. Or you could
rely on the end-of-configuration reset to initialize the TriState
controls, but that's just another form of asynchronous reset.

And what if the clock doesn't start? It's OK for the system to
malfunction if the clock doesn't come up, but it's considered bad form
for the system to destroy itself.

I've seen bus driver TTL type
devices, which are relatively hefty drivers, shorted for several weeks
while waiting for the short on the board to be found and fixed without
any smoke occurring and marveled that devices can take such abuse and
still work. Probably cut into the shelf life of that board a bit but
this was an engineering prototype.

It's amazing how much you can abuse hardware and still have it
function, but that doesn't mean that hardware abuse is a good idea. I,
too, have seen single chip outputs shorted for long periods of time
without destroying the driver, but when you short multiple
high-current outputs, all bets are off.

And low-drive outputs aren't a guarantee of trouble-free contention,
either. In one system I worked on, we had a TriState bus with a RAM
on it, and the RAM's TriState enable was under software control.
Unfortunately, the software guys weren't aware that they were supposed
to disable the RAM at startup, resulting in a brief period of
contention every time the system booted. The RAM drivers were pretty
weak, maybe 4mA, so you wouldn't suspect that'd be a problem, but we
started getting boards back from the field with bad RAMs after 8 or 9
months.

Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com

 

[Bob Perlman]

On 9 Oct 2006 11:57:12 -0700, "KJ" <Kevin.Jennings@Unisys.com> wrote:

In any case, nobody has articulated yet the application that really
does require specified reset behaviour PRIOR to the clock starting thus
requiring use of the async reset (with the exception of the reset
signal synchronizer flip flop itself).

Uh, I did. Took me 20 minutes to type it up, too. I'm not exactly
sure what the disagreement is: if you have FFs controlling TriState
enables, you should initialize them asynchronously. Whether that's
done by an end-of-config reset or some other reset signal doesn't
really matter--you need the asynchronous reset.

And I didn't even get to the open-the-bomb-bay-doors and
throw-the-countermeasures-out-the-back-of-the-plane and
start-radiating-the-patient signals. Proper design etiquette demands
that they be initialized immediately, too. (Yes, those signals go
through other interlocks, but as soon as you rely on redundancy, it
ceases to exist.)

Bob Perlman
Cambrian Design Works
http://www.cambriandesign.com