|
|
Do you have a topic you'd like Thorkil to write about?
Click here to send a request. |
Floating Point Concepts
and the 80x86 Implementation
In pure math there is no limit to how precise
numbers are and mathematical formulas do not take such limitations
into account. But computers, of course, cannot use an arbitrary
precision in calculations, and today the IEEE standard for floating
point is followed by just about all processors.
Float Value Representation
The general way to represent mathematical real
values is to describe a value as a sign, a significand
and an exponent. The sign is a +1 or -1 value, the
significand is a value of the form x.bb...b (binary digits), and the
exponent a power of 2, so a value is represented as:
sign * significand * (2**exponent)
The value 1.0 is therefore 1.0 * (2**0). A number is
said to be normalized, when the first binary digit x in the
significand is 1. So though 1.0 also could be represented as e.g.,
0.0100...0 * (2**2), the proper normalized value should be 1.000...0
* (2**0).
IEEE 32 and 64 bit formats
The IEEE standard has two float formats, a 32 bit
format and a 64 bit format. The sign bit is the left most bit, then
follows the exponent, and the rest is used for the significand. The
exponent is represented as a biased value, such that the
exponent field of the format is not the exponent directly, but needs
be subtracted a bias to get the proper exponent value. Also
since numbers are normalized, the bit before the dot is always 1 and
is therefore implicit or hidden. This was done to get an
extra bit in the significand part.
For the two float formats the layout is the
following:
A B C
D
E
+-+----------+--------------------+
+S| Exponent | Significand
|
+-+----------+--------------------+
A is the most significant bit, also used for the
sign.
The exponent takes up the space from bit number
B to C and the significand the bits from D to E, which is the
least significant bit.
With bit numbers counted from right to left:
| 32 bit format: |
A=31, B=30, C=23,
D=22, E=0,
exponent: 8 bits, significand: 23 (24) bits, bias = 127,
range: 10**(-38) .. 10**(+38) (approx.) |
|
|
| 64 bit format: |
A=63, B=62, C=52,
D=51, E=0,
exponent: 11 bits, significand: 52 (53) bits, bias = 1023,
range: 10**(-308) .. 10**(+308) (approx.) |
Special values are infinity, where the
exponent bits are the largest possible and the significand=0, NaN's
(NaN=Not a Number), where the exponent bits are the largest possible
and the significand is non-zero, the denormalized numbers,
where the exponent bits are 0, and the significand part is non-zero,
and zero. The value zero has sign=0, exponent=0 and
significand=0 (all bits zero).
Rounding and precision
The IEEE standard also defines rules for rounding
and precision.
Rounding when the intermediate result is 1.xxx...xyyy...y,
and rounding starts with y:
Round to nearest or even (also called Banker=s
rounding) (sign symmetrical)
If the yyy...y is < 100...0 no rounding
If the yyy...y is > 100...0 rounding up
If the yyy...y is = 100...0 rounding up if last x
bit is 1, else no rounding
1.5 and 2.5 are rounded to 2, 3.5 and 4.5 rounded
to 4.
Round down (towards negative infinity)
-1.9 is rounded down to -2, 1.9 is rounded down
to 1
Round up (towards positive infinity)
-1.9 is rounded up to -1, 1.9 is rounded up to 2.
Chop (truncate towards zero) (sign
symmetrical)
-1.9 chops to -1, 1.9 chops to 1.
Precision may be 24 bits (32 bit format) or 53 bits
(64 bit formats). This is particularly relevant, if the floating
point instructions internally calculate in a higher precision (as
the 80x86 processors do), but each result should be confined to a
specific precision.
Improper operation
Control of improper operations may also be
exercised, either by having a numeric exception be generated that
the application can handle, or by having a default operation be
taken, e.g. if a result becomes denormalized (numeric underflow) the
default operation is to change the result to zero.
The IEEE standard does not dictate how a processor
implements the standard, whether normal machine registers are used
for floats in the instruction set (as PowerPC), or a separate
coprocessor is employed with its own stack (as 80x86). But with the
same control set up an arithmetic operation shall provide the same
resulting bit pattern regardless of processor.
The 80x86 Numeric Extension
After this brief presentation of parts of the IEEE
standard we shall next look into how the IEEE standard is
implemented in the 80x86 family of processors.
Floating point arithmetic was earlier comparatively
expensive to use in embedded applications. The original 8086
processor did not come with support for floating point, unless you
purchased and physically added a numeric extension chip 8087,
sometimes referred to as an NPX (Numeric Processor eXtension)
or more plainly as an FPU (Floating Point Unit). The NPX was
provided with the 80186 processor in the same form, but the 80286
processor required more involved NPX instructions to deal properly
with the new 16 bit protected mode concept (the 80287 chip). With
the 80386 the separate NPX (the 80387 chip) was still maintained
presumably for two reasons: one being the extra cost of the complex
chip, and second the higher power consumption that could require a
higher yielding power supply. Later processors complies to the
80387, but additionally introduce MMX and other extensions to the
NPX capability.
Since applications should not be prevented from
using the functionality of the NPX, when the chip was not present on
a target board, Intel provided emulation libraries instead, but with
a performance that could be prohibitive from practical use.
Common for all these NPX=es
is that the NPX provides 8 80 bit extended float registers for
internal calculations. The extended format has a larger exponent
field (15 bits) and the significand part is not only extended to 64
bits, but also has the hidden bit explicit.
A
B C
D
E
+-+----------+--------------------+
+S| Exponent |1 Significand |
(no hidden bit)
+-+----------+--------------------+
| 80 bit format: |
A=79, B=78, C=64, D=63, E=0,
exponent: 15 bits, significand: 64 bits, bias = 16383,
range: 10**(-308) .. 10**(+308) (approx.) |
The NPX registers may be used as a limited stack
where you push up to 8 values and reference other operands stack top
relative.
Since the NPX is a coprocessor synchronization with
the >main=
processor is required. The WAIT instruction is typically inserted in
front of every NPX instruction to ensure that the previous NPX
operation is completed. This has the side effect that if the
previous NPX instruction has a problem pending, the point of raise
of this will be at the next NPX or WAIT instruction being executed.
A code generator must be sure to have this synchronization done
reasonably close to the last NPX instruction, as e.g. the storing of
an NPX float register to memory is not guaranteed to be completed,
unless synchronization is made. An example could be a
round-to-integer of a float value, where the NPX instruction is
exactly such a convert-to-integer instruction to some memory
location. If the following instruction merely loads the memory
location, the result may or may not be correct, depending on how far
the NPX coprocessor is with the operation. A synchronizing WAIT
instruction will however assure that the value is present in memory,
when it is read. If the float value happened to be too large to be
converted, a numeric exception would be raised at the WAIT.
With the Pentium the NPX was no longer a separate
chip, but embedded in the Pentium CPU. It still however allows the
synchronization WAITs though they never really wait anything, except
for some special cases. As the Pentium uses two instruction pipes, U
and V, there is also an NPX pipe to execute the NPX instruction set.
Later than Pentium processors have MMX and other additions to the
instruction set that are built as extensions to the NPX concept.
In a later article we shall take a closer look on
the subset of float values that in Ada83 is called model numbers,
the problems with sharing the NPX between Ada tasks, use of NPX
inside interrupt handlers, and how to employ the NPX for maximum
performance.
 |
About the Author
Thorkil Bjørn Rassmussen has worked with DDC-I for over 20
years. He has a Master of Science, Computer Science, from
University of Copenhagen. Thorkil has substantial experience
with all of the DACS tools and is the key individual
involved in all FAA certifications for the DACS product
line. Thorkil lives with his wife Jane and two children
Jonas and Tine, just outside of Copenhagen, Denmark.
|
[
Back to Top ]
Touching the Void
By Linda Rising
risingl@acm.org
www.lindarising.org
Usually I write an article after reading
something startling, but this time, I’d like to tell you about a
television program and how the lesson from this amazing story can be
useful in our current business environment.
A recent PBS special told the story of an
adventure that took place in 1985. British mountaineers Joe Simpson
and Simon Yates set out to climb the imposing snow-covered,
21,000-foot Siula Grande in the Peruvian Andes, one of the most
formidable peaks in the world. Their goal was to conquer the
notorious west face of the mountain, a nearly vertical ascent that
had been attempted without success by other professional climbers.
Simpson and Yates were confident they would succeed. They were young
(in their twenties), in tip-top shape, and experienced.
Their story has been captured in Simpson's book Touching
the Void, and in the PBS special (and DVD) by the same name.
Obviously, there were no cameras on the original climb, so actors
recreated the events while the real Simpson and Yates narrate. The
result is surprisingly dramatic. It is obvious that the climbers
survive, but with the tension of the ordeal you somehow forget that
the climbers are telling the story.
The climbing approach they used is called Alpine
style, which for us non-climbers, means they didn’t carry a lot of
stuff and there isn’t a series of base camps with emergency
supplies. The strategy is to move fast and not make any mistakes.
You can see it coming, can’t you?
The first part of the climb, the ascent, was
successful (read "they were lucky"). And then, on the
descent, luck ran out. Simpson fell and broke several bones in his
right leg. His lower leg pushed through his knee joint. It’s
horrible to imagine such an injury in any situation but at that
altitude and in those remote conditions, it was effectively a death
sentence.
With essentially no food or water, the climbers
had to get down—fast. They had made an agreement that if one of
them became injured, the other would leave him behind to save
himself, but Yates was determined to get his friend home, even
though a storm was moving in. Each climber carried 150 feet of rope,
so Yates tied these pieces together with the idea of lowering
Simpson down the mountain in increments of 300 feet. The only
complication was that Yates had to stop after the first 150 feet of
each repetition and signal for Simpson to give him enough slack so
that he could get the knot past his harness.
As you can imagine, rolling down the mountain was
agony for Simpson. In the film he cries as he bounces over the rough
terrain, but Yates has to ignore his partner's suffering. Both their
lives were at stake.
Things were progressing unexpectedly well when
after one slide down the mountain, Simpson did not respond. Yates
was stuck. He had no idea why Simpson was not giving him the slack
he needed, so Yates positioned himself against the mountain and
waited in a blinding storm. It took all his strength to hold onto
the rope, and he became increasingly aware that eventually his
muscles would fail and both men would plummet down the incline.
What Yates couldn't know was that Simpson had
fallen over the edge of a crevasse and was hanging in midair.
Simpson’s fingers were frostbitten and he was unable to climb back
up the rope and unable to communicate with Yates.
They remained like this for an hour, with Yates’
strength slowly ebbing away and Simpson's weight on the rope slowly
pulling him toward the edge of the cliff. Yates realized he was
facing an impossible dilemma: if he continued to hang on to the rope
until his strength gave out, Simpson’s weight would pull them both
down the mountain. On the other hand, if he let his friend go it
would surely mean Simpson’s death, but possibly saving his own
life. It also occurred to Yates at this point that Simpson might, in
fact, already have died. That would explain the lack of response and
the dead weight on the end of the rope.
Logic would suggest that it's better for only one
man to die rather than both—especially if the one is already past
hope. But for a climber, the biggest taboo is to cut the rope that
binds him to his partner. In fact, this tactic is anathema.
Yates is completely candid when discussing the
ethical dilemma of this decision for which he was nearly hounded out
of mountaineering and the reason Simpson wrote the book about the
event—in defense of Yates’ actions. In the film, 17 years after
the fact, Yates calmly states that when he realized that he had a
Swiss Army knife in his pack (and that he knew that sooner or later
he would be dragged off the cliff by the weight of his partner, whom
he had no way of helping) he decided 'fairly quickly' to cut the
rope.
This is the moment I call the first decision
point. We’ll return to this later in the article.
After Yates cut himself free, he must still make
his way down the mountain burdened with the immense guilt over what
he believes is the death of his friend.
When Yates cut the rope, he had no way of knowing
that not only was Simpson still alive, but that he survived the fall
when Yates cut the rope and landed inside the crevasse. Simpson’s
frostbitten fingers and the trauma of his injury have sapped his
strength. He was unable to climb the rope to get out of the
crevasse. He could only hang there, suspended, waiting to die.
As it got dark and he got tired of calling for
help that he really didn’t expect to arrive, he reached his own
decision point and also did the unthinkable. He cut himself loose.
His decision was, as Yates’, incredibly difficult but very
logical. Hanging there he was sure to die, and not a pleasant death.
If he cut the rope, he would fall further into the crevasse. One of
two things would happen: either he would further injure himself and
die sooner or, perhaps, he would discover a way out at the bottom.
Hope springs eternal. It’s like swimming against the current. You
can wear yourself out, fighting until you loose your strength or you
can go with the flow and see where it takes you while you are strong
enough to take advantage of it. Simpson made his decision.
This is the moment I call the second decision
point.
Since you know that both climbers tell their
stories in the documentary, you know that Simpson does find a way
out at the bottom of the crevasse. Even with his injury and no food
or water, he manages to find his way back down the mountain.
Luckily, Yates was still in the area, taking his time to recover
from his own ordeal and not wanting to give up completely on his
climbing partner.
Touching the Void is a gripping and
horrifying film. In 2004 it won Outstanding British Film of the
Year at the BAFTAs and Best Film of the Year from the
Evening Standard British Film Awards. It featured prominently in
both the Telluride and Toronto Film Festivals and has surpassed Bowling
for Columbine as the highest-grossing documentary in the UK. I
hope you’ll find it at your nearest video rental store or on-line.
Be aware that I haven’t given you enough information to spoil your
enjoyment of this production.
Now, let’s see what we can learn from this,
even though we may not be professional climbers! Since I’m a firm
believer in retrospectives—at an organizational and a personal
level (isn’t that what New Year’s resolutions are all about?)—I
examined this experience, especially the two critical decision
points, and asked what could be learned from this mesmerizing drama.
I believe that most viewers will be impressed
with the determination and the incredible will to survive
demonstrated by the two young men, especially Simpson. When we hear
stories like this—how people conquer incredible odds—we are
hopeful and uplifted by the display of courage. But I’d like to
focus on the two major decision points. (1) When Yates cut the rope
and later (2) when Simpson cut the rope.
At decision point one, when Yates cut the rope
that connected him to his injured partner, it was momentous for
several reasons. This action was unthinkable for a climber. Yes, you
could argue that logically it seemed the right thing to do. Yates
could only hold the rope so long before he would be pulled over the
cliff. By cutting the rope, he reasoned that he was increasing his
own chances of survival, while probably sending Simpson to his
death. Simpson, recall, was injured, and was only making progress
down the mountain because Yates was lowering him on the rope.
Recall, too, that Yates wasn’t sure that Simpson was still alive.
Lack of response could have indicated that Simpson has suffered a
fatal injury in the rapid descent. Cutting the rope meant increasing
the chances that at least one would survive. Better one climber
survives than no climbers survive. Seems simple.
However, the intriguing thing is, that not only
was this the logical thing to do, it was the only thing that
would, as it turned out, enable both men to survive. It was the only
way out. It was not on the list of accepted best practices for
climbers. In fact, some still say today that Yates violated the
rules that all climbers follow. Violating the rules is this case
enabled the survival of both men.
Luckily Yates was able to violate the climber’s
taboo and as he himself describes it "fairly quickly"
(after about an hour) cut the rope.
Now the second decision point. I don’t know
about you, but as I was agonizing with Simpson as he considered the
hopelessness of his situation, I was urging him on, "Cut the
rope! Cut the rope!" Easy for me, sitting in my living room,
but imagine hanging inside a crevasse with a broken leg, calling out
for help that doesn’t arrive, that couldn’t possibly arrive.
Simpson cried. He cursed. He called himself a host of names and
railed against his fate. It’s interesting that Simpson, raised as
a Catholic, never prayed to God for deliverance. Even in this most
dire of circumstances—perhaps that’s a true measure of how he
really was, literally, at the end of his rope (a little climbing
joke!). But cutting the rope would not mean the release of a burden,
as it did for Yates, not necessarily an increase in the odds for
survival. He was going to surely plummet further into the crevasse.
He was surely going to suffer more and probably increase the extent
of his already severely broken right leg. He was only able to do
this because he was out of options. This still isn’t an easy
situation.
I recall the story of Aron Ralston, a 27-year-old
climber who escaped danger by cutting off his arm. After being
pinned by a nearly 1,000-pound boulder for five days in a remote
slot canyon in eastern Utah, he cut off his pinned arm with a
pocketknife, rappelled down a rock wall and hiked until a search
helicopter found him. Ralston decided to sacrifice his arm to save
his life only after his water ran out and he realized that he would
not survive unless he took drastic action. He used his pocketknife
to amputate his right arm below the elbow and then applied a
tourniquet and administered first aid from a kit he had in his
backpack. He then rigged anchors and fixed a rope to rappel nearly
75 feet to the bottom of the canyon and hiked until a search
helicopter rescued him.
Yes, it’s clear how necessary these actions
were, but what courage it took and what a difficult decision it was
to make—even though it was the only way out of a life-threatening
situation.
It brings us up short to even draw a remote
comparison with the decisions we face. Yes, we work in an incredibly
dynamic, fast-paced economy. Just when you think you’ve got it all
figured out: how to organize your team or connect with your
customers, something unexpected and uncomfortable leaps out at you.
The advice seems to be the same. Let’s hear
from Richard Pascale. I’ve just finished reading his book Surfing
the Edge of Chaos: The Laws of Nature and the New Laws of Business
(Crown Business, 2000), where he and his coauthors Mark Millemann
and Linda Gioja describe a system of thinking and managing to help
companies adapt in this perilous environment.
Let's be clear. The idea of 'living systems'
isn't a metaphor for how human institutions operate. It's the way
they really are.
Rapid rates of change, an explosion of new
insights from the life sciences, and the insufficiency of the
old-machine model to explain how business today really works have
created a critical mass for a revolution in management thinking.
Pascale’s approach is the result of studying
current organizations and developing a set of laws that say that the
first rule of life is also the first rule of business: Adapt or die!
The first new law of life that leaders need to
recognize is that equilibrium equals death. We may enjoy a period of
time when following the established rules really works. It may give
us a dominant position. It may result in economic success. But it
also makes us increasingly vulnerable when the world changes. When
things change those rules we followed to success in the past become
our own worst enemy.
The question we have to ask ourselves is,
"Does the formula I have been following still work? Am I
becoming a victim of my own success? Has the world changed so that
my winning strategy is no longer the way to survive? Just as in
climbing, survival favors heightened adrenaline levels, wariness,
and experimentation—a willingness to violate the rules.
How do we pull back from the edge? First, members
of the organization must become innovators, champions of new ideas.
This is a perfect spot to give a shameless plug for my new book: Fearless
Change: patterns for introducing new ideas! People should be
encouraged, not just allowed, but encouraged to look for the next
big idea. In other words, to cut the rope!
Leaders can encourage this behavior by saying
that if an error occurs, it's everybody's fault. If everyone is
encouraged to come up with the next big idea, if something goes
wrong, then no one starts finger pointing and blaming. People in an
organization must see themselves as entrepreneurs who are
responsible for identifying and satisfying customer requests. They
must feel free to "cut the rope," if they see a way out of
a dilemma.
One way to see how this works is to consider a
bad example from Pascale’s book. In light of the recent travel
adventures over the holiday season, I thought it would be
appropriate to recall January 1999, when a blizzard closed Detroit
Metropolitan Airport and canceled outbound flights. Snowplows kept
the runways open, and a number of inbound planes were able to land
throughout the evening. Most carriers were able to bring their
planes to the gates to off-load their passengers but not Northwest
Airlines.
Northwest's ground staff seemed paralyzed by
indecision, held hostage by rigid policies and practices. Nearly
4,000 passengers were virtually imprisoned on 30 Northwest flights
for as long as eight hours without food, water, or working toilets.
Fights broke out. Passengers threatened to open emergency-exit
doors. Pilots yelled at ground staff over the radio to tow the
planes to the gates before they lost control of the situation.
Northwest's inflexibility in adhering to rules
and procedures for passenger safety caused them to overlook many
possible solutions to the problem. In other words, no one felt free
to "cut the ropes." They could have towed the planes close
to the gates and let passengers off on the tarmac. They could have
let them off on the runways and bused them to the terminal. They
could have brought service vehicles out to the planes. It could have
been a different scenario if leaders had told the staff, "We
have a huge disruption on our hands. Be innovative and imaginative,
and demonstrate to each other and to our customers that we can come
through when it counts." Instead, Northwest lacked the capacity
to violate the rules, cut the rope, and survive.
Remember, always carry that Swiss Army knife in
your pack and be prepared to break the rules when faced with a
potentially "life-threatening" dilemma. Your inventiveness
might help you survive!
 |
About the Author
http://www.lindarising.org
risingl@acm.org
Linda Rising has a Ph.D. from Arizona
State University in the area of object-based design metrics.
Her background includes university teaching as well as work
in industry in telecommunications, avionics, and strategic
weapons systems. She is the author of numerous articles and
has published three books: Design Patterns in
Communications, The Pattern Almanac 2000, and A Patterns
Handbook. She is currently writing a book with Mary Lynn
Manns: Fearless: Introducing New Ideas into Organizations, to appear in September 2004. |
[
Back to Top ]
|
