Unusual Floating-Point Format Remembered?

This is not true in all cases. A logic section can connect to a bus or a MUX so that more than one thing can be routed onto its input.

I was in this case refering to a bit slice implementation that reused some of the hardware in strange ways.

You shift up by digits until the MSD is not zero.

This depends a lot on the number of points in the FFT. You can do a base ten FFT where one butterfly is a head spinning ten way combination. The FFT length needs to be a power of 10 in this case. The addressing ends up digit inverted. Nobody in their right mind would even think about implementing such a thing.

A decimal tree could be done with a HASH to quickly find the right branch. If you are going to go to ten on something like this you would be better off going to 11. The marketing is much better on things that go up to eleven.

=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF

We were talking of the case where you are doing an add. If the thing is hooked to a bus, the two uses can be done in turn as needed.

If you want to beat a more conventional processor you have to do many operations per cycle. If you can't do that, then there isn't much reason to use the FPGA. My preference is a systolic array, though there are other possibilities. The routing slows the FPGA down compared to a top end DSP, so you want at least

-- glen

In article , Jerry Avins writes: |> Nick Maclaren wrote: |> |> > |> Do decimal trees make as efficient use of time and space as binary |> > |> trees? What does it mean to branch on a digit? |> > |> > Irrelevant. Both of those are independent of the storage representation. |> |> So memory addresses are to remain binary? How do you expect pointer |> arithmetic to be implemented?

Eh? Why?

I am old enough to remember when the properties of branching were often tied to the representation, but there are getting decreasingly few people who are. Conditional branching almost always follows a comparison, and comparisons are as implementable in decimal as in binary.

Similarly, you can implement binary, decimal or ternary trees on computers with any pointer representation - INCLUDING ones where pointers are opaque objects and have NO representation as far as the program is concerned! And it's been done, too.

Regards, Nick Maclaren.

And in times past people would have been faster to notice that this exchange started on 1st April. :-) IEEE754R is real enough, though it seems to have had a checkered history.

I used to use a computer where floating point was floating hexadecimal. I can't remember which one it was, though. The greater lumpiness used to cause a few quirks in models that I don't tend to get with things like IEEE754 floating point. That might represent quirkiness of my models, rather than any serious disadvantage of floating hexadecimal, though.

Regards, Steve

Another reason is that you had something else to do that needed about

A FIR filter is very much a systolic array with some non-ALUed steps in it, so I suspect that you would find a huge number of folks who agree with you on that.

In article , glen herrmannsfeldt writes: |> |> I have seen designs for doing matrix multiplication, and I believe |> you could do matrix inversion in a systolic array. In those cases |> you would want a large number of multipliers and adders. You |> could also do an FIR in floating point, though believe fixed |> point makes more sense most of the time.

Dropping back a level, one of the reasons that I disbelieve in the current dogma that floating-point should be separated from integer arithmetic at the logical unit level is the following:

The most important basic floating-point primitives at a level above the individual operations are dense matrix multiply and FFT. Both have the property that their scaling can be generally determined in advance, and the classic approach of converting from and to floating- point at the beginning and end and actually doing the work in fixed- point loses no accuracy.

This would mean that only one set of arithmetic units was needed and SIGNIFICANTLY simplifies the logic actually obeyed, with the obvious reduction in time and power consumption. It used to be done, back in the days of discrete logic, and is really a return to regarding floating-point as scaled fixed-point!

Now, I think that you embedded DSP people can see the advantages of being able to do that, efficiently. The program gets the convenience of floating-point, but key library routines get the performance of fixed point, and the conversion isn't the major hassle that it usually is at present.

I don't expect to see it :-(

Regards, Nick Maclaren.

(I wrote)

Yes, you could do that. There are also processors designed for FPGA implementation, and many FPGAs now have processors (often more than one) built in as a configurable logic unit.

I have heard about running Linux on a processor inside an FPGA and reconfiguring other parts of the FPGA from that processor.

They can get a lot more interesting than that, but yes an FIR filter, and I believe even an IIR, would usually be implemented as a systolic array. (Feedback terms are allowed, and there are even some I know of with data going both directions.)

I have seen designs for doing matrix multiplication, and I believe you could do matrix inversion in a systolic array. In those cases you would want a large number of multipliers and adders. You could also do an FIR in floating point, though believe fixed point makes more sense most of the time.

-- glen

(snip)

I have heard discussion of block floating point, which as I understand it an array would have a single exponent that would be used for all operations on that array. I don't know that there is much hardware support for it, but that might be a good intermediate. It allows one to work with scientific and engineering data without worrying about the scale factor and get the right answer at the end. All calculations can be done in units of meters, even if the actual values are very large or small.

To me, scaled fixed point is applicable to problems that have an absolute error (uncertainty). That is, it (mostly) doesn't depend on the size of the value. Finance and typesetting are two examples. TeX uses fixed point values of printers points with 16 bits after the binary point for its calculations. That allows from smaller than the size of an atom to over 37 feet, which should be plenty for any typesetting problem. With 64 bit fixed point it should work for even more problems.

For FFT, where terms are added and subtracted throughout the calculation, the result usually will only be as good as the absolute precision of the largest value. It might just as well be done in fixed point! That might be slightly less true for matrix multiply, but likely for many other matrix operations.

I was really surprised when I started seeing floating point DSPs.

I don't either.

-- glen

In article , glen herrmannsfeldt writes: |> |> For FFT, where terms are added and subtracted throughout the |> calculation, the result usually will only be as good as the absolute |> precision of the largest value. It might just as well be done in |> fixed point! That might be slightly less true for matrix multiply, |> but likely for many other matrix operations.

Precisely.

Regards, Nick Maclaren.

Pointers being opaque is a property of a language. I think we are discussing the properties of future machines here. Regardless of what the programmer sees, pointers must be incremented, decremented, and indexed relative to. Do you expect the arithmetic that will that to be binary or decimal? Will memory addresses be binary?

I used a mainframe that did floating point in decimal (Spectra 70?). When a switch was made to a machine that did floating point in binary, an important program stopped working. Rather than take any chances with future chances, the program (including all the trig and arbitrary scaling) was rewritten in integer. The assumption was that integer arithmetic would remain binary. Is that still a good assumption?

Jerry

...

Don't frown. The dynamic range encountered in an FFT is predictable only within wide limits. Consider two 64K FFTs with input quantities in the same range. In one, the energy is spread over the entire spectrum, while with the other it is concentrated at a single frequency. Do you suggest providing 16 bits of headroom? It might be reasonable in some circumstances, but is it better than floating point?

Jerry

Well, integers are integers. It only starts to matter if you start using properties or operations that only make sense to binary representations, like bit-wise logical operations (and(x,n-1) instead of mod(x,n) for n a power of two and x positive, for example).

I really, really doubt that I'll ever see a DRAM manufacturer implement decimal addressing in a DRAM chip, though, and I have my doubts that we'll see cache memory with decimal dividers in the address path to parcel-up the sets and ways.

Since integers are integers, and since there really are a lot of useful things that you can do, and algorithms that can be easily implemented iff the representation is binary, I can't see that we will ever see decimal integer representations, particularly not for address arithmetic.

Cheers,

In article , Jerry Avins writes: |> |> Pointers being opaque is a property of a language. I think we are |> discussing the properties of future machines here.

Not on a capability machine!

|> Regardless of what |> the programmer sees, pointers must be incremented, decremented, and |> indexed relative to. Do you expect the arithmetic that will that to be |> binary or decimal? Will memory addresses be binary?

Eh? All of those properties are independent of the representation, so much so that they are equivalent even if the representation doesn't use a base! The binary/decimal issue is TOTALLY irrelevant to them.

|> I used a mainframe that did floating point in decimal (Spectra 70?). |> When a switch was made to a machine that did floating point in binary, |> an important program stopped working. Rather than take any chances with |> future chances, the program (including all the trig and arbitrary |> scaling) was rewritten in integer.

Without making any attempt to find out why it stopped working? Aw, gee. Look, I was writing, using and porting top-quality numerical software that was expected to work, source unchanged, on floating-point of any base from 2 to 256 (decimal included) since about 1970. It isn't hard to do - IF you know what you are doing.

Only a minority of the failures, then or later, with porting numerical codes are due to the base as such. It really ISN'T a big deal.

|> The assumption was that integer |> arithmetic would remain binary. Is that still a good assumption?

Yes.

Regards, Nick Maclaren.

In article , Jerry Avins writes: |> |> > Now, I think that you embedded DSP people can see the advantages of |> > being able to do that, efficiently. The program gets the convenience |> > of floating-point, but key library routines get the performance of |> > fixed point, and the conversion isn't the major hassle that it usually |> > is at present. |> > |> > I don't expect to see it :-( |> |> Don't frown. The dynamic range encountered in an FFT is predictable only |> within wide limits. Consider two 64K FFTs with input quantities in the |> same range. In one, the energy is spread over the entire spectrum, while |> with the other it is concentrated at a single frequency. Do you suggest |> providing 16 bits of headroom? It might be reasonable in some |> circumstances, but is it better than floating point?

That's not a wide limit :-) And the answer is "yes" - at the level of fundamental hardware design. The reason that it usually isn't on standard CPUs today is that they are optimised for floating-point and not at all for extensible fixed-point.

Regards, Nick Maclaren.

...

Phew! What a relief! :-)

Jerry

Not if the arithmetic is done in decimal and the result needs to be converted to binary to get a physical address for physical memory.

We knew exactly what the problem was: roundoff had changed. We were generating instructions for Gerber plotters serial numbers 1 and 2. They had beds of 40" by 60" IIRC, and 10,000 steps per inch in X and Y. We drew diagonal lines, circles, ellipses and logarithmic spirals all over the bed and expected to return home with no closure error. Since the output was necessarily integer to match the integer nature of stepper motors, it made sense to do all calculations with integers. Besides, floating-point math that was bit-reproducible across machines had not yet been even proposed.

...

Jerry

In article , Jerry Avins writes: |> |> We knew exactly what the problem was: roundoff had changed. We were |> generating instructions for Gerber plotters serial numbers 1 and 2. They |> had beds of 40" by 60" IIRC, and 10,000 steps per inch in X and Y. We |> drew diagonal lines, circles, ellipses and logarithmic spirals all over |> the bed and expected to return home with no closure error. Since the |> output was necessarily integer to match the integer nature of stepper |> motors, it made sense to do all calculations with integers. Besides, |> floating-point math that was bit-reproducible across machines had not |> yet been even proposed.

So?

That isn't hard to do in code that will run correctly on any reasonable floating-point system, with any base. I am one of many thousands of people who has done it. Using integers doesn't eliminate the problem - it merely means that you get the exact same movements on all systems - not a very useful property.

Regards, Nick Maclaren.

It may be easy to do with floating point, but I bet it's more likely to be bug free the first time around in integer, especially when the final result must be integer in either case.

If "you get the exact same movements on all systems" and there is no closure error ever -- if, in other words, the plotter is always on the grid point closest to the point calculated with infinite precision -- how does that not eliminate the problem?

Jerry