davidsen@crdos1.crd.ge.COM (Wm E Davidsen Jr) (03/12/91)
When I was doing some investigation of sort algorithms I noted that
many common algorithms (such as shellsort and quicksort) have jackpot
cases, where sorting of a certain number of items in a given order may
take far longer than N-1 or N+1 items. I hardware I notice the same
thing... certain programs run very slowly on certain machines, out of
all proportion to the predicted performance of the machine based on
benchmarks.
What do people who design chips for commercial use do to locate these
cases before releasing the chips? Or do they wait to press reviews or
nastygrams from users? For example, consider a graphics program which
ran on a VAX and Sun3. With much effort it was converted to do most of
the work using integer arithmetic. Then it was ported to a Sun4.
Briefly.
I'm not going to attack leaving divide, or even multiply, out of a
chip, but how do designers decide what the customer doesn't need in
order to optimize the cip for running benchmarks?
I have a set of benchmarks which look for just these jackpot cases,
measuring the speed of every arithmetic operation, and things like "test
and branch." Do others do that in order to warn their user community
that there are classes of problems which have greatly reduced
performance, or just run some "typical" stuff and pray that there are no
deep performance holes?
--
bill davidsen (davidsen@crdos1.crd.GE.COM -or- uunet!crdgw1!crdos1!davidsen)
"Most of the VAX instructions are in microcode,
but halt and no-op are in hardware for efficiency"