|
|
|

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 (2)
By Thorkil B. Rassmussen
Here we shall take a closer look at the Ada
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.
Ada model numbers
The model numbers are introduced in the Ada83
Reference Manual (ARM) in sections 3.5.6 and 3.5.7, and put some
constraints on the number of significant bits (B) with respect to
the maximum exponent, expressed as a power of 2. The binary
canonical form is
sign * mantissa * (2 ** exponent)
where sign is +1 or -1, and mantissa
is a value of the form 0.1xxxx... (except when the value is
zero).
The model numbers comprise all numbers where the
number of significant binary digits B obeys the constraint that the
exponent is in the range -4 * B .. 4 * B.
For 32 bit floats there are maximum 24 mantissa
bits, requiring a binary exponent range from -96 .. +96, and for 64
bit floats there are maximum 53 mantissa bits, requiring a binary
exponent range from -212..+212, both well within the maximum
exponent range for the float type.
Numbers are not model numbers when the
exponent exceeds the 4 * B range, but can still be within the safe
numbers with a maximum exponent E limited by an implementation
defined value larger than 4 * B; for 32 bit floats this value E is
125 and for 64 bit floats 1021.
The model numbers intend to provide a predictable
accuracy when doing floating operations, where the operands are
(each) within a model number interval, and the result within the
interval defined by the operand intervals applied to the operations.
The benefit of the model numbers is more
questionable, as floating point processors live up to the
requirements for model numbers (ARM section 4.5.7), so an
application need rarely be designed in terms of model numbers.
Floating point constants are always expressed as safe numbers and
rounded to the value of B in question and allowing a larger exponent
than 4 * B. A comparison of a float calculation to a float constant
should therefore consider that the result is not necessarily exact,
but may be in the model number interval around the float constant.
Using the 80x86 NPX processor for floating
point calculations
The 80x86 Ada compiler will generate floating point
instructions according to the float expressions required, but there
are some significant issues that must be considered. In a previous
article it was explained how the WAIT instructions must be used to
assure synchronization between the floating point coprocessor and
the > main integer=
processor, so that a result floating value is in fact in memory,
when the main processor needs it.
A further complication is tasking. When a task
relinquishes control asynchronously, e.g. as a result of preemption,
it may or may not have floating point processing undergoing. The
floating point state must therefore be preserved as well as restored
when the task is resumed. This may be a time consuming operation as
it involves a lot of floating point information that needs to be
saved and restored. For a 32 bit processor there are 108 bytes to
handle. Since presumably not many tasks actually do floating point
operations this is just slowing down the task switch operation.
Therefore the Ada RunTime System (RTS) employs a lazy
float handling strategy. The first time a task executes a
float operation it will trap through interrupt 7. This trap occurs
because each task switch operation enables the trapping situation by
setting the TS bit in the processor=s CR0 register. The only tasks that can be hit by interrupt 7 are
then those tasks that execute floating point operations after they
have gained control from another task.
The RTS therefore keeps track of which task is the
current owner of the floating point processor (NPX). There may be no
owner. If a task traps via interrupt 7 it has executed a float
operation, and there are several possibilities:
-
The task may be the current owner of the NPX, and can then
just remove the TS bit in CR0 and redo the float operation,
effectively resuming from last time the task was active
-
There is no owner of the NPX - here there are two
possibilities:
- This is this task=
s first NPX operation, so a fresh NPX state is loaded
- Restore a previously saved NPX state
In either case remove the TS bit in CR0 and mark
this task as the current owner and resume the operation again.
-
Another task is owner - the NPX state must be saved for this
other task first, and then the handling is as if there were no
owner.
With this scenario only tasks that do floating point
operations pay for saving and restoring the NPX, and other tasks can
be switched to without any extra overhead.
A special issue is executing floating point
operations within an interrupt. The interrupt routine is
running > on the back=
of the otherwise executing task which could be the NULL task. This
task could already be doing floating point operations at the point
of interrupt. Special RTS calls are required by the interrupt
routine to ensure that the current owner of the NPX is saved and the
owner switched to the interrupt code. Also, leaving the interrupt
routine a similar RTS call is required to assure that there is no
owner of the NPX anymore. We cannot use the interrupted task
directly, unless its possible use of the NPX has been saved first.
More importantly, when this task eventually resumes it should
continue with its proper NPX. Therefore it is vital that interrupt
code is not again interrupted, while the NPX owner is >
fake= .
In some contexts interrupts are unconditionally
enabled (e.g. when entering exception handling), so that poses an
extra problem that must be handled in the RTS for exception
management. But in general interrupt routines should be disabled for
as little as possible and do their potential floating point
operations within an NPX-safe region. Allowing exceptions during the
floating point operations must take the necessary precautions.
Optimal use of the 80x86 NPX floating point
processor
The 80x86 NPX works in stages, and parallelism is
achieved by assuring that each stage has something to do. A stage
can be to load a float value into the processor, to perform an
operation on already loaded value, or to store a result to memory.
To make a simple add of two floats: A := B + C;
will have to await the loading of B and C, the plus operation and
the store to A, in all 4 stages are required. There is not much to
do about that, except when such occurs in loops, where each loop
iteration is independent of the other:
-- a, b and c are
float arrays:
for i in 1..12 loop
a(i) := a(i) * b(i) + c(i);
end loop;
What would benefit this construct would be to unroll
the loop partially:
i:= 1;
loop
a(i) := a(i) * b(i) + c(i);
a(i+1) := a(i+1) * b(i+1) + c(i+1);
a(i+2) := a(i+2) * b(i+2) + c(i+2);
i := i + 3;
exit when i > 12;
end loop;
Though the code grows in size the application of /optim=speed
in the DACS-Pentium Ada83 compiler makes the compiler attempt to
spread the loading and storing of values in a more optimal way for
the NPX, so that several of the stages can effectively occur in
parallel. This of course leads to loaded values which are placed
improperly for certain operations, but here the >
price= for letting
operands change place on the float stack is free, so that does not
have to be a problem.
The unoptimized code looks like this:
--------------------------------------------------------------------------
7: loop
8: a(i) := a(i) * b(i) + c(i);
--------------------------------------------------------------------------
0000002D 8BB560FFFFFF MOV
ESI,[EBP-160]
00000033 D944B5C0
FLD dword ptr [EBP+ESI*4-64]
00000037 D84CB590
FMUL dword ptr [EBP+ESI*4-112]
0000003B D884B560FFFFFF FADD dword ptr [EBP+ESI*4-160]
00000042 D95CB5C0
FSTP dword ptr [EBP+ESI*4-64]
--------------------------------------------------------------------------
9: a(i+1) := a(i+1) * b(i+1) + c(i+1);
--------------------------------------------------------------------------
00000046 D944B5C4
FLD dword ptr [EBP+ESI*4-60]
0000004A D84CB594
FMUL dword ptr [EBP+ESI*4-108]
0000004E D884B564FFFFFF FADD dword ptr [EBP+ESI*4-156]
00000055 D95CB5C4
FSTP dword ptr [EBP+ESI*4-60]
--------------------------------------------------------------------------
10: a(i+2) := a(i+2) * b(i+2) + c(i+2);
--------------------------------------------------------------------------
00000059 D944B5C8
FLD dword ptr [EBP+ESI*4-56]
0000005D D84CB598
FMUL dword ptr [EBP+ESI*4-104]
00000061 D884B568FFFFFF FADD dword ptr [EBP+ESI*4-152]
00000068 D95CB5C8
FSTP dword ptr [EBP+ESI*4-56]
--------------------------------------------------------------------------
11: i := i + 3;
--------------------------------------------------------------------------
0000006C 838560FFFFFF03 ADD dword ptr [EBP-160],3
--------------------------------------------------------------------------
12: exit when i > 12;
After optimization for speed is
applied:
--------------------------------------------------------------------------
7: loop
8: a(i) := a(i) * b(i) + c(i);
--------------------------------------------------------------------------
0000002D 8BB560FFFFFF MOV ESI,[EBP-160]
00000033 D944B5C0
FLD dword ptr [EBP+ESI*4-64]
00000037 D84CB590
FMUL dword ptr [EBP+ESI*4-112]
0000003B D944B5C4
FLD dword ptr [EBP+ESI*4-60]
0000003F D84CB594
FMUL dword ptr [EBP+ESI*4-108]
00000043 D9C9
FXCH ST(1)
00000045 D884B560FFFFFF FADD dword ptr [EBP+ESI*4-160]
0000004C D944B5C8
FLD dword ptr [EBP+ESI*4-56]
00000050 D9CA
FXCH ST(2)
00000052 D884B564FFFFFF FADD dword ptr [EBP+ESI*4-156]
00000059 D9C9
FXCH ST(1)
0000005B D95CB5C0
FSTP dword ptr [EBP+ESI*4-64]
--------------------------------------------------------------------------
9: a(i+1) := a(i+1) * b(i+1) + c(i+1);
--------------------------------------------------------------------------
0000005F D9C9
FXCH ST(1)
00000061 D84CB598
FMUL dword ptr [EBP+ESI*4-104]
00000065 D9C9
FXCH ST(1)
00000067 D95CB5C4
FSTP dword ptr [EBP+ESI*4-60]
--------------------------------------------------------------------------
10: a(i+2) := a(i+2) * b(i+2) + c(i+2);
--------------------------------------------------------------------------
0000006B D884B568FFFFFF FADD dword ptr [EBP+ESI*4-152]
00000072 D95CB5C8
FSTP dword ptr [EBP+ESI*4-56]
--------------------------------------------------------------------------
11: i := i + 3;
--------------------------------------------------------------------------
00000076 83C603 ADD ESI,3
--------------------------------------------------------------------------
12: exit when i > 12;
--------------------------------------------------------------------------
00000079 89B560FFFFFF MOV [EBP-160],ESI
0000007F 83FE0C
CMP ESI,12
00000082
9B
WAIT
00000083 7F02
JG 00000087H
Notice the intermixing of float load and arithmetic
operations (plus the >
free= FXCHs) that execute
in parallel with each other as well as with non float operations,
and this reduces execution time by 33%.
It is important that only /optimize=speed is
used and not the general /optimize, unless the common
subexpression (cse) optimization is excluded explicitly (/optimize=all=on,cse=off,speed=on),
since cse-optimization may counteract the optimization for speed.
It is however not always easy to rewrite float
expressions, but often worthwhile as the example shows.
 |
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 ]
Unusual Solutions - Part
2
By Linda Rising
risingl@acm.org
www.lindarising.org
Last month (http://www.ddci.com/news_vol6num2.shtml),
I described the unusual solutions of survivors in Sri Lanka as they
faced the terrible tsunami in Southeast Asia. I think in any difficult
situation, there are those who conquer the complexity with intriguing
approaches. We can all learn from these exceptional individuals (or
animals).
In this article, I’m going to tell you about a trip I took to New
Mexico a few weeks ago. No—no tsunami hit that state, but New Mexico
is like many places that face a list of serious problems. Here are
some:
(1) They have an increasing number of
disadvantaged students who are smart and might be willing to pursue
college programs, but they face almost insurmountable obstacles such
as: lack of family support, single parent status, no viable source
of income, no encouragement from peers, inadequate educational
preparation for college.
(2) Many small companies don’t have
sufficient resources to take on extra work because they can’t just
run out and hire the extra people they need, perhaps they’re in a
small town or perhaps they haven’t extra capital to invest before
they are paid for the new work.
(3) Large companies are feeling pressure to outsource work
even when they can see that the costs are larger than those who
follow this path are willing to admit.
(4) There is a growing need in this country for well-trained
technical people, while enrollments in standard engineering programs
are decreasing because students feel that to choose these majors
means that their jobs will just be candidates for outsourcing.
New Mexico Highlands University (NMHU) is a 4-year public
university in Las Vegas, New Mexico. (Whatever joke you’re thinking
about for "Las Vegas," trust me, they’ve already heard
it!) The school is relatively new, founded in 1893. Students can get
Bachelor's and Master's degrees in a variety of subjects. There are
approximately 2,000 undergraduates and 800 graduate students. A little
over half are female and most are Hispanic.
Its mission statement has some twists that might prepare you for an
unusual solution or two:
NMHU is committed to excellence in teaching, discovering,
preserving and applying knowledge and responding to new
opportunities for teaching, learning, research, and public service
created by a changing environment.
NMHU provides personal attention to students from distinctive
cultural, socioeconomic, linguistic, geographic, religious, and
educational backgrounds.
NMHU offers sensitive admissions programs and challenging
academic programs that encourage all students to reach their full
potential.
NMHU is committed to programs that focus on its multiethnic
student body, especially the rich heritage of Hispanic and Native
American cultures and clearly perceives that its success depends
upon an appreciation of the region’s cultural and linguistic
identities.
NMHU began its focus in the 1920s as the first institution of
higher education serving the Hispanic population and remains true to
that mission today. NMHU was chartered to service the people of
northern New Mexico, which comprises a large rural population
characterized by diverse cultural, economic, linguistic, and
educational backgrounds, ranging from 82% Hispanic (Mora County) to
75% Native American (McKinley County). General poverty is a
fact of life for this region and its students. The 2000 US Census
ranked New Mexico as the poorest state in the nation, and the poverty
rate in San Miguel County, home of NMHU, is 24%—double the national
average. At 7.8%, unemployment is presently one fifth higher than the
US average (NM Dept of Labor 2003). Given these demographics, the
employment possibilities engendered by the program I visited offer
hope and recognition for the hard work the students will have
accomplished by the time they receive their degrees.
You can see more about this program on the NMHU web site: http://www.nmhu.edu/softwaredevelopment/
The average class size for undergraduates in the lower division is
an astounding 21.20 students per class; for undergraduates in the
upper division, 8.11 students per class, for graduate classes, 6.63
students per class. Think about those undergraduate classes you might
have had with hundreds of students packed into an auditorium and a
non-native-English-speaking graduate student lecturing in a whisper.
What a different learning environment!
This place sounds like a wonderful setting for students who might
not otherwise even dream of a college education. The mission of the
institution and the small class size would tend to attract those
faculty members who think about teaching rather than high-powered
research. This is a school where people care about the students.
But what about the other problems in the list? How can this special
school meet the needs of small companies, large companies, and what’s
the tie-in with outsourcing?
Let’s move down from the institutional level to one unique
department at this university and meet Dave West, former professor at
the University of St. Thomas in Minneapolis-St. Paul, MN. Dave moved
to NMHU to start a different kind of software development program. It
is an apprenticeship program where students are paid for working on
real projects for real customers. The emphasis is on competencies
instead of courses. The approach is agile, in the best sense, in that
it is people-centric. Everyone involved in this effort believes that
developers and users are people first.
The Bachelor of Software Development Apprenticeship (SDA) program
at NMHU is the realization of Dave’s long-held goal: teaching
students in a community to use software development as a lever to
change the world instead of using it as a tool for doing the same
things people have always done more quickly and accurately. This
reflects his belief that the key to improvement is better people
rather than more rigidly specified processes.
The SDA program, housed in the School of Business Administration,
started in August 2004, in a suite of three rooms optimized for agile
development. Start-up difficulties related to equipment, physical
facilities and staffing resulted in an attrition rate of almost 50%
that first semester. The nine apprentices who continued into the
second semester, however, have seen their numbers more than double and
have increased their mastery of technology through group learning
activities, interaction with customers, mentorship from
object-oriented professionals, and instruction from nationally-known
speakers.
They meet daily, often without faculty direction, to plan and
construct software that has been ordered by one of the program’s
three customers: New Mexico’s Office of the State Engineer Water
Rights Management program, Tapetes de Lana (a mini-conglomerate with a
comparable social focus), and the West Las Vegas School District. The
needs of these three projects drive the content presented to the
students and motivate the exercises assigned to them.
Now can you see the connection? The students do real work and are
paid to learn. They don’t earn a lot of money, but for this part of
the world and these individuals, it’s a strong incentive to stay
with the program. It helps them with their finances and provides a
clear path to a job.
Now, let’s look at small businesses in the area. Suppose you were
running a small software company and had a chance to pick up some new
work, but a couple of things were holding you back. (1) The new
project would require more people than you have on staff now. You don’t
want to run out and hire and train new people, since you’re not sure
how things will pan out. If things don’t go well, you sure don’t
need extra mouths to feed. (2) The new assignment involves Java. This
is a new, cool programming language, but no one in your small company
has any experience with it. Yes, you’d like to take the time to send
some of your folks for training, but you can’t afford that just now.
What if you, the small business owner, could find a near-by school
with an apprenticeship program where students are not experts, but
they’ve been learning the latest, coolest technologies. You can
employ them for the short-term and they are cheap. They’re
enthusiastic and energetic and this near-by school will even let you
come on-site a few days a week and work with the students. At the end
of the project, your developers will have learned alongside their
student colleagues—free training! To me, this looks like a win-win!
What about large companies? True, they might also have some of the
training and staffing issues and could take advantage of the
apprenticeship program, but large companies are facing the pressure to
outsource. This is one of those "everyone else is doing it, so we
might be missing out on something if we don’t get on board"
items. Every CEO of every major corporation has an outsourcing
proponent on his (or her) staff. The arguments never end.
Outsourcing is cheaper (look at costs for developers
in the U.S. as compared with developers in India or China). We can
not only cut costs, but we can also expand our market share. Think
of the incredible number of widgets we can sell in China!
It’s hard to find an answer for this. Unless you’ve been
looking carefully at the reports of the real costs of
outsourcing—it does appear on the surface—that it would lead to
significant savings. It’s hard to resist the siren call to line up
behind the others.
What if you were a large organization in the vicinity of
Albuquerque, New Mexico? Maybe a large government agency? What if a
near-by school offered you the chance to "outsource" your
work at essentially minimum wage but still keep that work within the
U.S.? Such a deal! Not only that, but by increasing the wage-earning
potential of communities in your state and thereby raising the
standard of living for residents, you might also increase your market
share right here at home!
Finally, let’s look at that last serious issue on the problem
list. As outsourcing robs resident technical employees of their jobs,
there is less incentive for college bound students to consider
technical areas that are the targets of this kind of job loss. In the
long run, who will suffer for this? If we outsource all our technical
needs, we put our country at tremendous risk. What goes around comes
around. Yes, there are discrepancies in the global market. I do
believe that we truly deal in a global marketplace. Inequities will
work themselves out. But we are suffering from inequities at home!
Surely those must be addressed by some kind of balancing act!
Just as we’ve seen that the solutions proposed for other global
problems are all technical, the solutions that are being proposed for
the outsourcing problem are technical and legal. Let’s just make
enough new rules to keep bad things from happening. We sure don’t
want things to be "looser"—when you turn people loose, who
knows what they will do!
I think Dave West is concerned about these inequities. I think that’s
why Dave West is giving his time and energy to this program. I think
that’s why Pam Rostal, one of Dave’s graduate students at St.
Thomas, moved to Las Vegas, leaving her family in Minneapolis for a
couple of years, to help jumpstart this program. I think that’s why
I went to visit NMHU to see for myself what unusual solution has been
implemented by a small handful of people who care.
The appealing essence of this solution is that it’s humane! It
speaks to my common sense. Instead of more rules, restrictions and
barriers, let’s do what we can to make the world a better place—for
all of us!
Just as I was finishing this article, I read "Made in
lower-cost America" in CNET news: http://news.com.com/Made+in+lower-cost+America/2100-1022_3-5562732.html
In this piece, I stumbled across the term "homeshoring"
to describe the use by IT companies of workers in smaller cities or
rural areas, where the cost of living and doing business is cheaper.
In fact, one company notes that "fees are about the same as the
overall cost of using an Indian outsourcer, if you consider factors
such as communication costs, travel expenses, and inconvenience."
Maybe this unusual solution isn’t so unusual after all!
I like that famous quote attributed to anthropologist Margaret
Mead: "Never doubt that a small, committed group of people will
change the world. Indeed, it's the only thing that ever has."
I had planned to end this series on unusual solutions with this
article, but I’ve been hearing from readers and uncovering even more
intriguing things to report, so perhaps I’ll do just one more column
on this! Keep those cards and letters coming! Thanks for your interest
and support!
 |
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. Follow this link for information regarding her
latest book "Fearless Change: patterns for introducing
new ideas".
http://www.cs.unca.edu/~manns/intropatterns.html |
[
Back to Top ]
|