[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Innovative Systems FPE...

On 8/20/2010 9:03 AM, DaveSchmenk wrote:

On Aug 19, 1:33 am, "Michael J. Mahon"<mjma...@aol.com>  wrote:

DaveSchmenk wrote:

On Aug 17, 11:12 am, "Michael J. Mahon"<mjma...@aol.com>  wrote:



mdj wrote:



[snip]



Many FP implementations choose big-endian just because it's a lot
easier to visualize the shifts, etc., than in little-endian mode.  ;-)



;-) If one is prepared to visualise memory addresses bassackwards I
agree ;-)



I guess I don't see any "backwardness".  Little-endian has always seemed
"backward" to me, since in "real life" we always write numbers big-
endian.  (And the 68881 supports packed BCD extended FP numbers!)



My mental model of (computer) memory runs either left-right or bottom-
up so it feels natural to me to place higher order bytes in higher
order addresses. So if you consider for example addition on an
arbitrary length number, the code looks more 'right' to me in little-
endian. It's also a much more 'natural' fit for evolved architectures
where the word size has been increased through several generations.



Interesting.  I often envision it with increasing addresses going
down, as in a code listing or a memory dump--and, of course, left-
to-right within a line.



About the only time I might consider addresses to increase going "up"
would be a graphical memory map, but even then, I usually rotate it
so that addresses increase from left-to-right.  ;-)



I once had to deal with big endian graphics hardware connected to a
little endian machine.  I swore I'd never deal with a big endian
machine again after that. Graphics hardware seems to be the worst when
it comes to mixing byte and bit ordering into the least convenient
format.


A mixed-endian environment is always a problem...


Of course, ever since elementary school, numbers have been written
left-to-right and arithmetic operations have proceeded from right-
to-left and top-to-bottom.  ;-)



As an aside, I once programmed extensively on a machine (B3500) that
was a storage-to-storage BCD machine with variable field lengths.  It
addressed all fields in memory by their lowest-addressed digit, which
was the most significant digit, and even did all arithmetic from left-
to-right.



This sounds quite difficult until you realize that a carry out from a
later (lower-significance) digit can only propagate through a contiguous
string of 9s, so it is only necessary to keep a count of how many such
9s would have been produced until a digit less than 9 is produced, when
all the delayed result digits can be written as either 9, if no carry,
or 0 with the previous result incremented by one, if a carry occurred.



That said, I would happily agree that if one has the luxury of
designing a modern processor from scratch, I would favour big-endian
representation ;-)



On the occasions when I've been able to do that, I did!



I'm curious as to why?  I always preferred least significant values in
lower addresses.  Whenever dealing with smaller or larger sizes than
the native register width, little endian seams more natural to me.


A study of comparative computer architectures reveals something about
endianness and why particular choices are made.

As was noted earlier, any architecture that starts with a small "word"
length, like 8 bits, finds a need to deal with larger numbers, and
does that by using multiple-precision representation for numbers.  It
is "natural" to do multiple-precision arithmetic from low- to high-
significance, so little-endianness at the level of multi-byte numbers
arises.  Interestingly, it is quite unusual to represent the bits
within a word as little-endian--they always have their most significant
bit at the left end, just as we always write numbers that way.



As in shift left and shift right have always represented the value
with the MSB on the left.  No doubt tradition plays a large part.


No doubt.  All the early computers were big-endian--and some were
even decimal!


Architectures that start with large words, 32-bits and above, often
choose big-endian forms, since most data they process fits within a
single storage access.

It is certainly possible to twiddle the bytes on the way from memory
into the processor, and in fact, several modern architectures, facing
the inevitability of dealing with the predominant Intel architecture,
have arranged to handle both big-endian and little-endian data with
almost equal facility (at a small extra cost).

So the key is how much of a role multi-word arithmetic plays in a
system.  If it is frequent, the system tends toward little-endianness.
If the word is long enough that multi-word arithmetic is rare, then
big-endianness is often preferred.

Of course, we've been talking about addressing endianness.  There's
also "time-endianness" having to do with how data is transferred when
it is wider than the datapath over which it is being transferred.  But
that's a topic of more interest to hardware designers...

Danny Cohen wrote a great article on endianness in 1980: "On Holy Wars
and a Plea for Peace":

http://www.ietf.org/rfc/ien/ien137.txt



<snip>


I'm going to be looking at conversion of IEEE to/from Applesoft format,
and I expect it to involve a shift and a little bit fiddling, but not
too much to do on-the-fly.



The main pain comes from dealing with sign extension of the exponent
when moving to/from the larger double (or extended) precision
representation...



It's not too bad, since it's just replicating sign bits in front of
the sign to get the correct exponent length.  Then there's a small
"excess" adjustment.



The biggest problem is that the IEEE sign of the mantissa is stored
ahead of the exponent instead of in place of the implicit bit of the
mantissa.  That requires a shift of the mantissa.  ;-(



I have never understood why that was the case - perhaps a result of
never having designed a hardware FP multiply circuit ...



IEEE floating-point was definitely *not* designed with much hardware
input!  Kahan was a mathematician, and, like many others, just assumed
that Moore's "Law" would take care of all the heavy lifting.  In fact,
it took a decade to learn tricks to permit *fast* IEEE FP, as opposed
to the heavily microprogrammed "hardware" of FP coprocessors.



The only reason I could think of for putting the sign in the MSB was
to do "quick and dirty" tests using integer registers for greater-than-
zero, zero, and less-than-zero. As for hardware multipliers, they
could care less where the bits are - it's all just wires to them.


There is a longstanding tradition in large-word machines, of putting
the mantissa sign first, then the excess-representation exponent, then
the mantissa.  This format allows a standard integer compare to compare
two floating-point numbers.  It also allows a comparison to finish early
as soon as a bit difference is detected.



Interestingly, the IEEE (non-denormalized) format makes for a handy
sign magnitude representation of a linearly interpolated log function
of the number - in integer format.  Sometimes useful for quick and
dirty calculations.


If you mean doing approximate calculations on floating-point numbers
by doing fixed-point arithmetic on them, I've actually never seen that
done.  Just comparisons.


My comment about IEEE FP speed and complexity is more general than sign
notation, having much to do with all intermediate computation being done
in extended format and a rich repertoire of difficult features, like
having to correctly deal with denormalized numbers.

  From the point of view of the 6502, Applesoft's choice of putting the
mantissa sign in the place of the implicit 1 (the high bit of the
mantissa) makes handling very simple, since the sign can be separated
out and replaced with the implicit 1 and arithmetic can proceed without
any shifting or other preparation.  The exponent is complete in its
byte, so again, no other preparation.


Certainly, and Woz's FP routines are an amazing example of incredibly
tight code to pull off all the basic FP operations.  I had to really
check it out to make sure it did everything it claimed in such a small
amount code.  But an 8 bit software environment would have different
requirements than a 32 bit FP hardware.


And I note that he chose big-endian representation, too.  ;-)


As I'm considering how to exploit the FPE from Applesoft, however,
I find myself leaning toward simply CALLing small chunks of slow FP
computation (involving functions, etc.)--that would be both fast and
easy, with a small number of conversions from/to Applesoft format only
on entry and exit.



This would be a natural for matrix operations.  ;-)



A comprehensive solution would be great to have 'in theory' but since
any application that depended upon the additional speed is not
'portable' in practice I think your solution is more than adequate.



Sounds like a lot of fun to play with!



Just as I'd hoped.  ;-)



-michael



Do you have a purpose for your code?  Ray tracing in AppleSoft (oh,
the pain)?


Actually, my purpose is just to learn more about the 68881 and to
see how much practical speed a 12MHz 68881 can deliver to an Apple II.
Ease-of-use and space efficiency are also interesting to study.



When implementing FP for NV02, I did find that formatting the data
into something useable took up a majority of the code space - I did
unroll the code that pulled the operands off the stack and the
normalization of the results, though.  Single precision and not
dealing with denormalized numbers simplified it greatly.  Does the
68881 allow for any overlapped operations?  Might be a nice vector
processor for the Apple II.


In software FP, multiplication and division are usually require a lot
of instructions/cycles, just because of the N^2 nature of those ops.

However, for most other operations, "housekeeping"--loading and
unloading the FP "accumulator" (or stack) and shifting to denormalize
or renormalize wind up dominating the time requirement.

With the FPE, it's pretty fast to send an opcode to the 68881, and
it performs most operations pretty quickly at 12MHz--FDIV and FSQRT
are among the slowest at about 130 68881 cycles, or 11 Apple II cycles--
which is fast enough to make moving operands to and from the 68881 the
slowest part of the problem.  The only exception would be when a complex
expression is being evaluated from a limited number of operands--when
the data can fit in the eight FPE registers, the FPE really shines.

Occasionally, an entire critical loop's variables can fit in the 68881,
and then the Apple II can just keep pumping out operations at the rate
of about one op every 24 Apple II cycles (if you want to be safe and
verify that the 68881 is done before feeding it the next op) or one
per 12 Apple II cycles if you are willing to run it "open loop" (I'm
still too inexperienced with its timing precision to risk that).

Even with the overhead of moving operands in and out, it looks like
the FPE offers a significant speedup, but at the cost of programming
it in assembly for now...

As I've implied, the FPE calculations are overlapped with 6502 ops,
if you arrange to wait for all ops to complete before issuing another.
The more usual way to use it is to wait *after* issuing an op, so
very little overlap occurs.  However, this approach offers the
possibility of waiting only when a wait might be needed, which is
practically never for simple operations.  (The only ones that actually
may need a wait loop are operations on packed decimal operands and
function evaluations (except FSQRT, which is fast).

-michael

NadaNet 3.1 for Apple II parallel computing!
Home page:  http://home.comcast.net/~mjmahon/

"The wastebasket is our most important design
tool--and it's seriously underused."