Maker Pro
Maker Pro

Unusual Floating-Point Format Remembered?

G

glen herrmannsfeldt

Jan 1, 1970
0
Jerry said:
glen herrmannsfeldt wrote:
But in either case, the granularity is much coarser than binary. That
was found to be unobjectionable in times past.

In the decimal case the granularity matches the visible
(in decimal printout) granularity. Hopefully (as has been discussed
on comp.arch.arithmetic, but maybe not cross posted) people still
remember what to do about that. Also, there are some useful algorithms
that pretty much work on the average precision of the underlying
arithmetic. (I believe that is true for successive over-relaxation
PDE solvers, for example.)

-- glen
 
M

MooseFET

Jan 1, 1970
0
MooseFET wrote: [....]
If you have a multiplier, it can be used to to the bit aligning and
the normalization steps of an add. Since one of the terms going to
the multiplier has only a single bit high, you can route either
through the FFT's bit order reverser if you need to shift in the
right(vs left) direction.

In many FPGA implementations, an adder or multiplier is used for one
task only. Think hardware. A gate can be used for many different tasks
before it is connected, but only one afterward.

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.


I understand normalizing binary with a barrel shifter. How is decimal
normalized?

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

FFTs in binary have reversed bit order addressing at one stage. What is
the storage order of a decimal FFT?

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.

Do decimal trees make as efficient use of time and space as binary
trees? What does it mean to branch on a digit?

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

MooseFET

Jan 1, 1970
0
MooseFET wrote:

(snip)


It can, if you don't need them for the multiply. Note that
you need both prenormalization (align the radix point before
add/subtract) and post normalization (remove high order
zero digits).

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

glen herrmannsfeldt

Jan 1, 1970
0
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.

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
20 or so operations per clock cycle per FPGA, more likely closer
to 100. You might do that with a bus and MUX, but that would
be rare.

-- glen
 
N

Nick Maclaren

Jan 1, 1970
0
|>
|> > |> 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.
 
S

Steve Underwood

Jan 1, 1970
0
Jerry said:
But in either case, the granularity is much coarser than binary. That
was found to be unobjectionable in times past.

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
 
M

MooseFET

Jan 1, 1970
0
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.

Another reason is that you had something else to do that needed about
1/2 of the FPGA you could buy and wanted a low chip/pin count. This is
more along the lines I was thinking of. Besides I was speaking of
what could be done not what was the best idea.

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
20 or so operations per clock cycle per FPGA, more likely closer
to 100. You might do that with a bus and MUX, but that would
be rare.

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

Nick Maclaren

Jan 1, 1970
0
|>
|> 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.
 
G

glen herrmannsfeldt

Jan 1, 1970
0
MooseFET wrote:

(I wrote)
Another reason is that you had something else to do that needed about
1/2 of the FPGA you could buy and wanted a low chip/pin count. This is
more along the lines I was thinking of. Besides I was speaking of
what could be done not what was the best idea.

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

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
 
G

glen herrmannsfeldt

Jan 1, 1970
0
Nick Maclaren wrote:

(snip)
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.

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

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.
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 was really surprised when I started seeing floating point DSPs.
I don't expect to see it :-(

I don't either.

-- glen
 
N

Nick Maclaren

Jan 1, 1970
0
|>
|> 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.
 
J

Jerry Avins

Jan 1, 1970
0
Nick said:
|>
|> > |> 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.

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
 
J

Jerry Avins

Jan 1, 1970
0
Nick Maclaren wrote:

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

Jerry
 
A

Andrew Reilly

Jan 1, 1970
0
The assumption was that integer
arithmetic would remain binary. Is that still a good assumption?

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,
 
N

Nick Maclaren

Jan 1, 1970
0
|>
|> 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.
 
N

Nick Maclaren

Jan 1, 1970
0
|>
|> > 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.
 
J

Jerry Avins

Jan 1, 1970
0
Andrew Reilly wrote:

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

Phew! What a relief! :)

Jerry
 
J

Jerry Avins

Jan 1, 1970
0
Nick said:
|>
|> 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.

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

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
 
N

Nick Maclaren

Jan 1, 1970
0
|>
|> 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.
 
Top